Algorithm

Online Prediction Problem-在线预测算法

该文章是MIT课程 Learning-Augmented Algorithms, lecture 21的学习笔记。课程slides[10],讲义[11].

本文主要介绍国内cs 课程较少涉及的online algorithm(在线算法),首先介绍下基本概念

在线算法和离线算法

离线算法

算法设计策略都是基于在执行算法前输入数据已知的基本假设,也就是说,对于一个离线算法,在开始时就需要知道问题的所有输入数据,而且在解决一个问题后就要立即输出结果,通常将这类具有问题完全信息前提下设计出的算法成为离线算法(off line algorithms),如果常见的一些排序算法。

在线算法

在计算机科学中,一个在线算法是指它可以以序列化的方式一个个的处理输入,也就是说在开始时并不需要已经知道所有的输入。相对的,对于一个离线算法,在开始时就需要知道问题的所有输入数据,而且在解决一个问题后就要立即输出结果。例如,选择排序在排序前就需要知道所有待排序元素,然而插入排序就不必。 还比如经典的秘书问题,秘书问题可以衍生出如何找最佳男女友的算法 [13]

因为在线算法并不知道整个的输入,所以它被迫做出的选择最后可能会被证明不是最优的,对在线算法的研究主要集中在当前环境下怎么做出选择。对相同问题的在线算法和离线算法的对比分析形成了以上观点。如果想从其他角度了解在线算法可以看一下 流算法(关注精确呈现过去的输入所使用的内存的量),动态算法(关注维护一个在线输入的结果所需要的时间复杂度)和在线机器学习。

Bit Prediction

Majority Algorithm

考虑一个简单的在线预测问题,Bit Prediction:有一个二进制序列(即序列由0、1组成),每个时刻会知道该序列的一个值,我们需要在该值出现前进行预测如何预测会有较高的准确率?这里实际包含两个部分:根据历史信息得到预测策略、根据每个时刻的预测和结果的比较,修正我们的策略

如果这个序列是独立(iid.)的且服从参数为p的伯努利分布。 那么一个最佳的策略就是根据历史信息(已知的部分序列),如果其中1多,我们就预测整个序列是1;反之亦然。假设时刻t的序列真值为y_t,前t个时刻序列平均值为\overline{y}_t,设时刻t预测的正确率为\overline{c}_t,那我们有:

这个结论来源于广为人知的中心极限定理。这个方法被称为majority algorithm. 这个是很简单的预测策略,从这个例子出发,我们可以声称:

  • 对于任意的随机二进制序列,都有一个方法,其预测准确性可以和序列中0和1数量不均衡的情况一样好

即,只要序列是不平衡的,我们就有至少一种方法以50%以上的准确率预测它。上述给出的声明并没有错误,问题是找到这样的方法并非总是很容易的(在上述Bit Prediction问题中,我们对问题加了很强的约束:iid和服从伯努利分布)。显然majority algorithm在很多情况下都很难达到50%以上的准确率,比如0和1交替出现的一个序列;或是先验知识中的majority和整个序列的majority不相同的情况。

note: 关于Bit Prediction的majority algorithm,这里有一个小游戏 Mind Reader Bot,游戏规则是:人类选手和计算机比赛赛跑,每次我们选择一个action,向左或是向右,计算机会预测我们的行动,如果预测成功,计算机前进一步;反之我们前行一步。

这个游戏人类很难获胜,为了战胜计算机,人类选手使用平衡序列(0和1的数量是均衡的)策略是有利的,否则计算机可以利用这种不平衡。然而这总是不易做到的

David Blackwell’s solution:贝叶斯预测

在Majority Algorithm中,我们并没有充分利用已知的历史信息,从而使得Majority Algorithm仅适用于一些特殊情况。对此,有更好的解决方案:Bayes Prediction [1],令

\text { Let } \mathrm{L}_{\mathrm{t}}=\left(\overline{\mathrm{y}}_{\mathrm{t}}, \overline{\mathrm{c}}_{\mathrm{t}}\right)=(\text { prop. of } 1\text { ‘s so far ; prop. of correct so far). }

注意:

  • \overline{y}_t代表到时刻t,出现1的概率
  • \overline{c}_t代表到时刻t,我们预测正确的概率

利用上述坐标画一个二维坐标图;我们的策略由L_t 所处的象限所决定。

  • 上方:c_t>max(\overline{y}_t,1−\overline{y}_t),我们当前的策略是较好的
  • 左方:当前正确率小于1出现的概率, 下一个位置预测0
  • 右方:当前正确率小于1出现的概率, 下一个位置预测1
  • 下方:我们预测序列下一个值为1的概率是:从点(0.5,0.5)画一条线到L_t,预测1的概率等于直线与y = 0的交点

这种方法由David Blackwell在1995年提出,被称为bayes prediction,这种方法有很多优点:

  • 几乎对所有的序列都适用
  • 可以很容易证明该方法具有很好的收敛性

但同时该方法同样无法处理一些特定序列,比如0和1交替出现的序列

一个好的在线算法应当适用于任意序列,Bayes Prediction相较于majority algorithm更好,但仍然不是我们想要的最终结果。

Potential-based Methods

online supervised learning

对于一个预测问题而言,预测正确率很大程度上取决于对先验知识的运用。如果一个问题是离线的,我们有离线的数据集,那么可以用机器学习的方式建模数据,然后利用模型来预测;而对于在线预测问题,我们需要其他的策略来建模先验知识。

movie matrix completion problem. 假设有一个二维矩阵决定一个user何时会喜欢一个电影

我们会对用户是否喜欢某部电影进行连续预测(1代表喜欢,-1代表不喜欢),并根据每个时刻的真值来实时纠正我们的错误。在预测过程中,是否由可以遵循的准则呢?一个显然的准则是:因为用户之间的相似性,最终的矩阵很可能接近一个低秩矩阵。问题是我们如何使用这样的“先验知识”?

我们先考虑online supervised learning的一般情况:我们需要在时刻t做出预测,预测结果\hat{y}_t\in {y_1,y_2,\cdots,y_n}。注意在t时刻做出预测前我们能观察到side information x_t (如推荐问题中,用户和电影的画像数据,比如性别、年龄、地域、电影类型、导演等)。同时预测结束后我们能知道真值y_t.

如果我们预测的序列是有规律的(如果序列是完全随机的,那么也没有预测的必要了),那么预测误差\sum_{t=1}^{n}\left|\hat{y}_{t}-y_{t}\right|需要比较小。

对一个问题设计其算法时,我们总是希望能给出bound,由此我们将问题的目标形式化一下,希望能设计一个于预测序列相关的函数\phi,预测误差的上界是\phi\left(x_{1}, y_{1}, \dots, x_{n}, y_{n}\right)

\sum_{t=1}^{n}\left|\hat{y}_{t}-y_{t}\right| \leq \phi\left(x_{1}, y_{1}, \dots, x_{n}, y_{n}\right)

由于基本的概率论原则:一个策略在某些序列上预测结果较好,那么必然会对其他某些序列预测结果较差

对于前文提到的low-rank movie matrix问题,我们可以得到\phi的形式:
\sum_{t=1}^{n}\left|\hat{y}_{t}-y_{t}\right| \leq \min _{w \in \mathcal{F}} \sum_{t=1}^{n}\left|\left\langle w, x_{t}\right\rangle- y_{t}\right|+\mathcal{C}_{n}\left(\mathcal{F} ; x_{1}, \ldots, x_{n}\right)

其中:

  • 第一项用来捕获x/y之间的关系:w是根据历史数据找出的最佳的低秩矩阵,\left\langle w, x_{t}\right\rangle 代表根据wx_t得到预测结果。
  • 第二项\mathcal{C}_{n}\left(\mathcal{F} ; x_{1}, \ldots, x_{n}\right)代表得出side information x的复杂度

Potential functions.

形式化问题之后,可以利用martingale inequalities[3] 得出最优预测的形式:
\hat{y}_{t}=\frac{1}{2}\left(\left(U\left(x_{1}, y_{1}, \ldots, x_{t},+1\right)-U\left(x_{1}, y_{1}, \ldots, x_{t},-1\right)\right)\right.

其中:

  • U是势函数,我们将取值为1和-1时解的和求平均,即最优预测结果(公式中的减号来源于-1)

这个方法的好处是:

  • 相比于如SVM这样的学习算法,无需优化求解的过程
  • 对于任意长度的数据都适用
  • 不依赖于i.i.d假设,更贴近真实世界的数据

对于movie matrix completion problem.,对于任意的user-move pairs and ratings,我们都可以给出一个统计意义上的误差上界:

其中:

  • d_1是用户数量,d_2是电影数量
  • N_c和N_r是出现频率最高的电影和用户

如果采样足够均匀,那么上述式子是满足i.i.d假设的统计意义的上界.

Note: 如果对AI相关的online learning感兴趣,参考 [12].

online linear optimization

在online linear optimization中,很时候是没有side information的(如online decision problem [2])。我们需要预测一个向量\hat{y}_{t} \in \mathcal{K} \subset \mathbb{R}^{d},同上,我们也可以给出误差的上界:
\sum_{t=1}^{n}\left\langle\hat{y}_{t}, y_{t}\right\rangle \leq \min _{w \in \mathcal{K}} \sum_{t=1}^{n}\left\langle\mathbf{w}, y_{t}\right\rangle+\mathcal{C}_{n}\left(\mathcal{K} ; y_{1}, \ldots, y_{n}\right)
Example. 根据d个专家意见的加权来做预测,其中:

  • \overline{y}_t代表d个专家意见的分布;\mathcal{K}是simplex;y_t是loss.

No-Regret Methods

在上述公式中,存在函数\mathcal{C},我们可以通过修改函数\mathcal{C},从而在过程中加入机器学习算法

No-regret dynamics for zero-sum two-player games

zero-sum two-player games和No-regret dynamics 都是博弈论中的概念:

  • zero-sum two-player games:双人零和博弈,又称零和游戏,与非零和博弈相对,是博弈论的一个概念,属非合作博弈。它是指参与博弈的各方,在严格竞争下,一方的收益必然意味着另一方的损失,博弈各方的收益和损失相加总和永远为“零”,双方不存在合作的可能。
  • No-regret dynamics:是指在知道对手策略的情况下,博弈者也不会有动力改变当前策略,即达到了纳什均衡 [4]

Note: 对于零和而言,在某个状态下计算所有可能的action时,对于某一方,总有一系列后续的应对策略,能够达到最终胜利(或者至少平局);也就是有所谓的“必胜策略”。这一点一开始会让人觉得有点反直觉:是不是某些状态下,我们无法确认能够有必胜策略呢?答案是否定的。如果我们并不能找到这样一个必胜策略,就意味着无论如何选择action,对手总有办法阻止你必胜,由于游戏是零和的,这也意味着对手有必胜策略 [5]

求解零和博弈,我们常用Minimax算法 [6],即极小化极大算法,是一种找出失败的最大可能性中的最小值的算法。Minimax算法常用于棋类等由两方较量的游戏和程序,这类程序由两个游戏者轮流,每次执行一个步骤。我们众所周知的五子棋、象棋等都属于这类程序,所以说Minimax算法是基于搜索的博弈算法的基础。该算法是一种零总和算法,即一方要在可选的选项中选择将其优势最大化的选择,而另一方则选择令对手优势最小化的方法:

  • minimax是一种悲观算法,即假设对手每一步都会将我方引入从当前看理论上价值最小的格局方向,即对手具有完美决策能力。因此我方的策略应该是选择那些对方所能达到的让我方最差情况中最好的,也就是让对方在完美决策下所对我造成的损失最小。
  • Minimax不找理论最优解,因为理论最优解往往依赖于对手是否足够愚蠢,Minimax中我方完全掌握主动,如果对方每一步决策都是完美的,则我方可以达到预计的最小损失格局,如果对方没有走出完美决策,则我方可能达到比预计的最悲观情况更好的结局。总之我方就是要在最坏情况中选择最好的。

在双人零和博弈中,令

  • M_{i, j} (d_1 \times d_2的矩阵) 代表player 1: 在自己选择action i,player 2选择action j时的代价
  • -M_{i, j}代表player 2的代价

博弈的每一步,player 1选择q_{t} \in \triangle_{d_{1}};player 2选择p_{t} \in \triangle_{d_{2}} (一个是行,一个是列);player 1 得到收益M p_{t},player 2 得到收益q_{t} M,那么有minimax value:
\min _{q \in \Delta_{d_{1}}} \max _{j \in\left[d_{2}\right]} q^{T} M e_{j}=\max _{p \in \Delta_{d_{2}}} \min _{i \in\left[d_{1}\right]} \frac{T}{i} M p=\min _{q \in \Delta_{d_{1}}} \max _{p \in \Delta_{d_{2}}} q^{T} M p

如果两个player 都选择no-regret策略,可以得到:
\frac{1}{n} \sum_{t=1}^{n} q_{t}^{\top} M p_{t}-\min _{q \in \Delta_{d}} \frac{1}{n} \sum_{t=1}^{n} q^{\top} M p_{t} \leq \frac{1}{n} \operatorname{Reg}_{n}^{(1)}
和:
\frac{1}{n} \sum_{t=1}^{n}\left(-q_{t}^{\top} M\right) p_{t}-\min _{p \in \Delta_{d_{2}}} \frac{1}{n} \sum_{t=1}^{n}\left(-q_{t}^{\top} M\right) p \leq \frac{1}{n} \operatorname{Reg}_{n}^{(2)}
两式相加:
\max _{\mathbf{p} \in \Delta_{\mathrm{d}_{2}}} \overline{\mathbf{q}}^{\top} M p-\min _{\mathbf{q} \in \Delta_{\mathrm{d}_{1}}} \mathbf{q}^{\top} M \overline{\mathbf{p}} \leq \frac{1}{n}\left(\operatorname{Reg}_{n}^{(1)}+\operatorname{Reg}_{n}^{(2)}\right)
从零和博弈中,我们可以知道“先验”:
\min _{q \in \Delta_{d_{1}}} q^{T} M \bar{p} \leq \max _{p \in \Delta_{d_{2}}} \min _{q \in \Delta_{d_{1}}} q^{T} M p=\min _{p \in \Delta_{d_{1}}} \max _{p \in \Delta_{d_{2}}} q^{T} M p \leq \max _{p \in \Delta_{d_{2}}} \bar{q}^{T} M p
由minimax算法,可以知道(\bar{q}, \bar{p})\frac{1}{n}\left(\operatorname{Reg}_{n}^{(1)}+\operatorname{Reg}_{n}^{(2)}\right)之内。由此可以认为(\bar{q}, \bar{p})接近纳什均衡。

上述过程,直观上来讲:博弈开始时,均等的考虑二者获胜的可能性;然后随着回合的进行更新想法,在每回合中,M p_{t}都会被传递,同时可以看到每个可选action的预期成本。最终(\bar{q}, \bar{p})接近纳什均衡。

上述过程通常的收敛速度是\frac{1}{\sqrt{n}},根据Daskalakis, Deckelbaum, Kim, 2011 [7]的研究,我们可以通过uncoupled dynamics达到更快的收敛速度\frac{\log (n)}{n}。该项研究不好的一点是,需要一个较为复杂的结构才能实现更快的收敛速度。

在博弈的过程中,一个player可以得到哪些额外信息?通常可以对每一回合进行缩放,如果n->\sqrt{n};如果work harder,可以变成\sqrt{\sum_{t=1}^{n}\left|y_{t}\right|^{2}}。考虑到y_t的额外信息:序列中的下一个元素,我们可以得到:
\sqrt{\sum_{t=1}^{n}\left|y_{t}-\mathcal{M}_{t}\right|^{2}}

这里之所以可以将下一个元素作为额外信息,来源于player在博弈过程中实际上是做缓慢的优化:So the previous move is a good proxy for the next move.

Optimistic Mirror Descent

Optimistic Mirror Descent是优化的update method,具体过程:
\begin{aligned} g_{t+1} &=\operatorname{argmin}_{v \in \mathcal{K}} \eta\left\langle v, y_{t}\right\rangle+ D_{\phi}\left(v, g_{t}\right) \\ \hat{y}_{t+1}=& \operatorname{argmin}_{v \in \mathcal{K}} \eta\left\langle v, M_{t+1}\right\rangle+ D_{\phi}\left(v, g_{t+1}\right) \end{aligned}
如果\mathcal{M}_{t}充满信息,那么优化过程可以做得更好;实际上可以在更新过程融入任何知识。有很多关于\mathcal{M}_{t}选择的paper。

Optimistic Mirror Descent的一些相关应用 [8] [9]:

  • can be related to Mirror Prox of Nemirovskii when applied to structured optimization (saddle point optimization)
  • results extend to partial information settings
  • application to smooth convex programming and MaxFlow
  • recent applications to GAN training

Reference

  1. Minimax vs. Bayes Prediction
  2. online decision problem
  3. Online Learning: Sufficient Statistics and the Burkholder Method
  4. 纳什均衡
  5. 浅述:从 Minimax 到 AlphaZero,完全信息博弈之路(1)
  6. Minimax算法及实例分析
  7. Mirror Prox Algorithm for Multi-Term Composite Minimization and Semi-Separable Problems
  8. Optimization, Learning, and Games with Predictable Sequences
  9. Online Learning with Predictable Sequences
  10. Online Prediction slide
  11. Online Prediction讲义
  12. 在线学习(Online Learning)导读
  13. 单身狗速进!如何科学有效地脱单?

发表评论

电子邮件地址不会被公开。 必填项已用*标注