乘法权重更新法

乘法权重更新法是一种最常用于决策和预测的算法技术，也被广泛用于博弈论和算法设计。最简单的用例是根据专家建议进行预测的问题，在这个问题上，决策者需要反复决定一个专家的建议。该方法为专家分配初始权重（通常是相同的初始权重），并根据专家表现的反馈信息对这些权重进行乘法和迭代更新：在表现不佳时减少权重，否则增加权重。它被反复发现于不同的领域，如机器学习（AdaBoost、Wnow、Hedge）、优化（解决线性程序）、理论计算机科学（设计LP和SDP的快速算法）和博弈论。

乘法权重意味着从乘法权重更新方法衍生的算法中使用的迭代规则。在它被发现或重新发现的不同领域，它被赋予了不同的名字。

这一技术的最早版本是在20世纪50年代初博弈论中提出的一种名为”虚构游戏”的算法。Grigoriadis和Khachiyan应用虚构游戏的随机变体，用乘法权重算法有效地解决双人零和游戏。在这种情况下，玩家将更高的权重分配给有更好结果的行动，并根据这些权重来选择他的策略。在机器学习中，Littlestone在他著名的winnow算法中应用了最早的乘法权重更新规则，该算法类似于Minsky和Papert早期的感知器学习算法。后来，他将绞杀算法推广到加权多数算法。Freund和Schapire跟随他的步骤，以对冲算法的形式概括了绞肉算法。乘法权重算法也被广泛应用于计算几何学中，如KennethClarkson的线性编程（LP）算法，该算法在线性时间内有一定数量的变量。后来，Bronnimann和Goodrich采用类似的方法来寻找具有小VC维度的超图的集合覆盖。

在运筹学和在线统计决策问题领域，加权多数算法及其更复杂的版本已被独立发现。在计算机科学领域，一些研究者先前已经观察到不同背景下使用的乘法更新算法之间的密切关系。Young发现了快速LP算法和Raghavan的悲观估计者方法之间的相似性，用于随机取整算法的去随机化；Klivans和Servedio将学习理论中的提升算法与Yao的XOR法则的证明联系起来；Garg和Khandekar定义了一个凸优化问题的共同框架，其中包含Garg-Konemann和Plotkin-Shmoys-Tardos作为子例。Hedge算法是镜像下降法的一个特例。

需要根据n个专家的意见做出一个二元决定，以获得相关的报酬。在xxx轮中，所有专家的意见都有相同的权重。决策者将根据大多数专家的预测做出xxx个决定。然后，在每个连续的回合中，决策者将根据他先前预测的正确性，反复更新每个专家意见的权重。现实生活中的例子包括预测明天是否下雨或股市是否会上涨或下跌。

给定一个对手和一个由N个专家提供建议的聚合者之间进行的连续游戏，目标是让聚合者尽可能少犯错误。假设在N个专家中，有一个专家总是给出正确的预测。