TCO2018 Marathon Round3 – InvestmentAdvice回顾 12月 15, 2018
contest
0 条评论

原题链接

TCO2018 Marathon Round3 问题InvestmentAdvice。

问题简述：

问题描述非常简单，大致说一下背景：就是你要做$rounds$轮投资，每轮投资都会有$N$个基金经理人给你建议（且每一轮之前都是这$N$个基金经理人给你建议）。每个经理人$export_i$在$round_j$轮之前会预测你把钱放在他这一轮（$round_j$轮）结束后他会给你带来$advice[export_i][round_j]$的投资百分比收益，这个收益可正可负。每轮（$round_j$轮）结束后，也会告知你这一轮你的实际收益（如果你投了钱给对应的经理人），对于每个经理人会收到数据$recent[export_i][round_j]$，这个数据指这轮你投的钱导致你这轮结束后获得的利息（同样也有正负）。问题来了，一开始给了你$100w$的启动基金，运行你玩$Rounds$轮，每一轮给每个经理人最多$40w$的投入，那么希望你结束时手上的钱尽可能多。（上轮的利息，下轮就可以做本金了）

主要的信息集中在模拟器的描述上：

  • 每场游戏（$Rounds$轮算一场）中，每个基金经理人$export_i$，会初始化两个参数$(accuracy_i, stDev_i)$，其中$accuracy_i$是该经理人的对大盘判断力准确性，$stDev_i$则是其对大盘收益的精确预测能力的标准差。这两个参数整场比赛中不会改变，但是这两个参数是隐藏的你无法直接观测到，只能通过算法推算而已。
  • 每一轮游戏前会对每个经理人所在的领域进行一次收益随机，这次收益率的随机方案:<code>Gaussian with mean 0 and stDev 10, capped to be within [-100, 100]</code>。就是均值是0，标准差是10，并缩放到区间[-100,100]之间，并最终得到真实收益$real[round_j][export_i]$。
  • 那么每个经理人的$advice[export_i][round_j]$是如何给出的呢？ 分两部分：
    • 经理人有$accuracy_i$的概率能理解大盘，并按均值为$real[round_j][export_i]$,标准差为$stDev_i$的高斯分布给出他对大盘的预测结果；
    • 经理人有$1.0 - accuracy_i$的概率完全理解错大盘，那么他给出的预测就是以均值为0，标准差为10直接随机出一个结果。
  • 总结就是你拿到的$advice[export_i][round_j]$有很大的概率是系统瞎给的，和$real[round_j][export_i]$完全没任何相关性。

计分方法：

非常简单，谁最后手上钱多就赢了。

赛程回顾：

怎么说呢，这场和round1那场有点相似之处，就是随机度有点大，可以掩盖掉你的优化的提升。即在比赛大后期，如果你修改了算法的一部分策略或参数，会发现有微弱的提升，但是你却无法评估这个提升是策略或参数的有效性带来的，还只是运气好产生的。（即无法区分过拟合是否发生）。不过反正我加班比较多，后期根本没有时间优化，所以这个特性似乎对我没啥影响，呵呵。

总得来说这是我做的最轻松的一场马拉松，因为我似乎一下子就找到了问题最最关键的一部分，利用贝叶斯方法获取每个经理人的$(accuracy_i, stDev_i)$参数分布，并根据这个分布做贪心投资。事实表明这个策略虽然非常简单，但是却足够优秀，最后之比最好的方案少万分之五的分数。最后排17名拿了十多分的积分，虽然不多但是能进Leaderboard了，十分开心。

思路整理：

这次的思路比较简单，如果了解贝叶斯方法的话。为了简化说明，不妨假设只有一个经理人（毕竟经理人之间是相互独立的）。
我们定义：

  • $pro(ith, acc, st)$为经过$ith$轮实验，得知该经理人$(accuracy=acc, stDev=st)$的概率分布。当然，为了便于工程计算，我们将$(acc,st)$离散化，比如我就用了$10 * 10$的粒度来计算的。
  • $exp(rep, acc, st)$表示一个经理人在$(accuracy=acc, stDev=st)$的前提下，向你汇报下个季度的市场收益$report=rep$时，实际上期望能得到的收益。

OK，如果这两个数据都是已知的话，那么当前第$ith$轮经理人告知你下个季度收益为$report=rep$，那么，可以求出其实际收益的期望为：
$$Exp(rep)=\sum{acc} \sum{st} pro(ith-1, acc, st) * exp(rep, acc, st)$$

是不是很简单！

下面介绍这两个数据怎么求：

$pro(ith, acc, st)$：用贝叶斯公式有

$$\begin{equation}\begin{split}
pro(ith, acc, st) &= P(acc,st|report{list})\\
&\simeq P(report{list}|acc,st) P0(acc, st)\\
&= \prod{v=1}^{ith} P((rep_v, real_v)|acc,st) P0(acc, st)\\
&= pro(ith-1, acc, st) * P((rep{ith}, real_{ith})|acc,st)
\end{split}\end{equation}$$

有

$$\begin{equation}\begin{split}
P((rep{ith}, real{ith})|acc,st) = & (1-acc) Gaussian(real_{ith},\mu=0,\sigma=10)\\
& + acc Gaussian(rep{ith},\mu=real{ith},\sigma=st)
\end{split}\end{equation}$$

其中，$real_{ith}$是第$ith$轮的实际观测值。
$P_0(acc, st)$是一开始的先验分布（因为没有数据，所以是条件参数的边缘分布），显然就是比赛$accuracy$与$stDev$的随机分布咯。

策略上，每次至少给每个经理人100块的投资经费，就可以稳定获得观测的数据了。（由于收益是均值为0的高斯分布生成的，所以每人100块的投资期望收益是0，也就是不会亏钱！）

$exp(rep, acc, st)$这个怎么求？

其实可以动态规划来求解，推导写公式不是很好写，就不介绍了。毕竟这个玩意可以直接离线打表，还不容易出错。

剩下的策略超级简单，每轮给每个经理人至少100块，剩下的钱直接按照希望收益从高到低尽可能多的给每个经理人发投入。当然前提是这个经理人的期望收益是正的。
至此，基本已经能够拿到很高的分数了。

如果还想拿更高的分数，那么就需要分析如何规避早期因为观测数据量小而产生的系统级误差问题了。这个思路就不介绍了，因为我也不是很擅长，呵呵!

Post Views: 4,433