专家学习

问题提出

我们需要解决一个在线预测问题. 整个过程持续\(T\)的时间点, 可以想象成\(T\)轮预测. 有\(n\)个不同的专家, 他们的编号从\(A_1\)到\(A_n\), 在每个时间步, 每个专家都会给出一个建议. 在每个时间步\(t\), 算法\(A\)会收到来自所有专家的建议, 表示为\(v_{1, t}, v_{2, t}, ..., v_{n, t}\), 每个建议\(v_{i, t}\)的取值是\(0\)或者\(1\). 算法\(A\)会根据它所接受到的专家建议以及可能利用的历史信息, 输出一个子集的预测\(\hat{u}^t\), 其取值也是\(0\)或者\(1\). 在算法做出预测之后, 会揭晓真实数值\(u_t\), 其取值同样也是\(0\)或者\(1\). 算法在每个时间步\(t\)产生的成本定义为一个指示函数\(1_{\hat{u}_t\neq u_t}\). 这意味着如果算法的预测\(\hat{u}_t\)和真实值\(u_t\)不相等(预测错误), 则成本\(c_t\)为\(1\); 如果预测正确, 则成本为\(0\).

至于假设... 我们对真实值\(u_t\)和专家们的行为没有任何预先的假设, 真实值可以是相关的, 独立的. 专家们也可能传统, 随机给出建议. 对算法本身也没有很强的限制. 它可以拥有任意大的内存, 可以进行复杂的计算, 甚至可以非常低效. 唯一的限制是算法在时间步\(t\)做出预测时, 无法预知未来的信息, 只能依赖于过去时间步的信息以及当前时间步接受到的专家建议. 问题的核心是如何最小化总成本\(C(T)=\sum_{t=1}^T c_t\). 这表示在整个\(T\)个时间步内, 算法预测错误的次数的总和应该尽可能的小.

那么, 最小化总成本到底意味着什么呢? 如何使用数学的语言来描述这个目标. 也就是, 我们是否能找到算法, 使得总成本\(C(T)\)相较于时间步\(T\)来说增长得非常慢. 我们是否能找到算法, 使总成本\(C(T)\)相对于时间步数\(T\)来说增长得非常慢, 例如\(C(T)=o(T)\)(次线性增长, 意味着平均错误率趋近于\(0\))或者\(C(T)=O(\log T)\)(对数级增长, 错误次数增长非常缓慢).

然而, 有一些坏消息.

坏消息

真相56.1: 对于任何确定性算法\(A\), 以及任何\(n\)个专家的几何, 都存在一个真实值序列\(u_1, ..., u_T\), 使得算法\(A\)的总成本\(C(T)=T\).

证明56.1: 证明非常简单, 因为在每个时间步\(t\), 算法\(A\)会根据过去的信息和当前的专家建议输出一个确定的预测\(\hat{u}^t\)(其值为\(0\)或者\(1\)). 我们可以设置真实的标签\(u_t\)为算法的预测相反的值, 即\(u_t=1-\hat{u}^t\). 这样, 在每个时间步\(t\), 算法的预测都必然是错误的, 因此成本\(c_t=1_{\hat{u}_t\neq u_t}=1\). 将所有时间步的成本加起来, 总成本\(C(T)=\sum_{t=1}^T c_t = T\).

所以, 任何确定性的在线预测算法, 都存在一些情况, 使得算法在所有时间步都犯错, 导致最大的可能成本为\(T\). 当然, 这仅仅适用于确定性算法这些弱者, 随机性算法的表现怎么样呢?

真相56.2: 对于任何算法\(A\)(包括确定性算法和随机性算法), 以及任何\(n\)个专家的几何, 都存在一个真实值序列的分布, 使得算法\(A\)的期望总成本\(E[C(T)]\geq \frac{T}{2}\).