乗法重み更新法

敵対者と N 人の専門家から助言を受ける集約者との間で行われる逐次ゲームにおいて、集約者の目標はできるだけ少ない間違いを犯すことである。N 人の専門家の中に、常に正しい予測をする専門家がいると仮定する。半減アルゴリズムでは、一貫性のある専門家のみが保持される。間違いを犯した専門家は除外される。集約者は、すべての決定において、残りの専門家の多数決によって決定する。したがって、集約者が間違いを犯すたびに、残りの専門家の少なくとも半分が除外される。集約者は最大で log ₂ ( N )回の間違いを犯す。^{[ 2 ]}

出典: ^{[ 1 ] [ 7 ]}

間違いを犯した専門家を排除する半減アルゴリズムとは異なり、加重多数決アルゴリズムは彼らの助言を割り引きます。同じ「専門家の助言」設定が与えられた場合、n 個の決定があり、各ループで 1 つの決定を選択する必要があるとします。各ループでは、すべての決定にコストが発生します。すべてのコストは選択後に明らかになります。専門家が正しい場合はコストは 0、そうでない場合は 1 です。このアルゴリズムの目標は、累積損失を最良の専門家とほぼ同じに制限することです。各反復で多数決に基づいて選択を行う最初のアルゴリズムは、専門家の大多数が毎回一貫して間違っている可能性があるため機能しません。加重多数決アルゴリズムは、コストを 1 または 0 に固定する代わりに専門家の重みを保持することにより、上記の自明なアルゴリズムを修正します。^{[ 1 ]}これにより、半減アルゴリズムと比較して間違いが少なくなります。

初期化： 修正する${\displaystyle \eta \leq 1/2}$各専門家について、重みを関連付けます。${\displaystyle {w_{i}}^{1}}$≔1. の場合${\displaystyle t}$=$\displaystyle {\mathit {1}}}$、$\displaystyle {\mathit {2}}}$、...、${\displaystyle T}$1.専門家の予測の重み付けに基づき、加重多数決によって得られた予測を採用する。$\displaystyle \mathbb {w_{1}} ^{t},...,\mathbb {w_{n}} ^{t}}$1. つまり、どちらの予測を支持する専門家の総重みが高いかに応じて、0 または 1 を選択します (同点の場合は任意に決定)。 2.予測を誤った専門家 i については、次のラウンドでの重みを (1-η) 倍して減らします。 ${\displaystyle w_{i}^{t+1}}$=${\displaystyle (1-\eta )w_{i}^{t}}$（ルールの更新）

もし${\displaystyle \eta =0}$専門家の助言の重みは変わりません。${\displaystyle \eta }$が増加すると、専門家の助言の重みは減少します。一部の研究者は、${\displaystyle \eta =1/2}$加重多数決アルゴリズムにおいて。

後${\displaystyle T}$ステップ、${\displaystyle m_{i}^{T}}$専門家 i の間違いの数を とし、${\displaystyle M^{T}}$を、我々のアルゴリズムが犯した間違いの数とする。すると、すべてのに対して次の境界が得られる。${\displaystyle i}$:

$\displaystyle M^{T}\leq 2(1+\eta )m_{i}^{T}+{\frac {2\ln(n)}{\eta }}}$。

特に、これは最良の専門家である i に当てはまります。最良の専門家は最も少ない${\displaystyle m_{i}^{T}}$これにより、アルゴリズム全体が犯した間違いの数について、最良の上限値が得られます。

このアルゴリズムは次のように理解できます。^{[ 2 ] [ 8 ]}

N人の専門家による同じ設定を考えます。重みを考慮した上で、肯定と否定を予測する専門家の割合がどちらも50%に近いという特殊な状況を考えてみましょう。この場合、同率になる可能性があります。重み付き多数決アルゴリズムの重み更新ルールに従うと、アルゴリズムによる予測はランダム化されます。アルゴリズムは、専門家が肯定または否定を予測する確率を計算し、計算された割合に基づいてランダムな決定を行います。

予測する

${\displaystyle f(x)={\begin{cases}1&{\text{確率}}{\frac {q_{1}}{W}}\\0&{\text{それ以外の場合}}\end{cases}}}$

どこ

${\displaystyle W=\sum _{i}{w_{i}}=q_{0}+q_{1}}$。

ランダム化加重多数決アルゴリズムによる誤りの数は、以下のように制限される。

$\displaystyle E\left[\#{\text{学習者の間違い}}\right]\leq \alpha _{\beta }\left(\#{\text{最優秀者の間違い}}\right)+c_{\beta }\ln(N)}$

どこ ${\displaystyle \alpha _{\beta }={\frac {\ln({\frac {1}{\beta }})}{1-\beta }}}$そして ${\displaystyle c_{\beta }={\frac {1}{1-\beta }}}$。

学習アルゴリズムのみがランダム化されていることに注意してください。基本的な仮定は、例と専門家の予測はランダムではないということです。唯一のランダム性は、学習者が独自の予測を行う際のランダム性です。このランダム化されたアルゴリズムでは、${\displaystyle \alpha _{\beta }\rightarrow 1}$もし${\displaystyle \beta \rightarrow 1}$重み付きアルゴリズムと比較すると、このランダム性によってアルゴリズムが犯す間違いの数が半分になった。^{[ 9 ]}ただし、いくつかの研究では、人々が定義していることに注意する必要がある。${\displaystyle \eta =1/2}$加重多数決アルゴリズムで許可し、${\displaystyle 0\leq \eta \leq 1}$ランダム化加重多数決アルゴリズムにおいて。^{[ 2 ]}

出典: ^{[ 1 ] [ 9 ]}

分布が与えられたと仮定します${\displaystyle P}$専門家について。${\displaystyle A}$= 有限2人ゼロサムゲームの利得行列、${\displaystyle n}$行。

列のプレーヤー${\displaystyle p_{r}}$計画を使用する${\displaystyle i}$そしてコラムプレーヤー${\displaystyle p_{c}}$計画を使用する${\displaystyle j}$プレイヤーの報酬${\displaystyle p_{c}}$は${\displaystyle A\left(i,j\right)}$≔${\displaystyle A_{ij}}$仮定すると${\displaystyle A\left(i,j\right)\in \left[0,1\right]}$。

プレイヤーが${\displaystyle p_{r}}$行動を選択する${\displaystyle i}$分布から${\displaystyle P}$行を順に見ていくと、プレイヤーの期待される結果が${\displaystyle p_{c}}$アクションの選択${\displaystyle j}$は${\displaystyle A\left(P,j\right)=E_{i\in P}\left[A\left(i,j\right)\right]}$。

最大化するために${\displaystyle A\left(P,j\right)}$、プレイヤー${\displaystyle p_{c}}$プランを選択する必要があります${\displaystyle j}$同様に、プレイヤーの期待収益は${\displaystyle p_{l}}$は${\displaystyle A\left(i,P\right)=E_{j\in P}\left[A\left(i,j\right)\right]}$プランの選択${\displaystyle i}$この利益を最小化します。ジョン・フォン・ノイマンのミニマックス定理により、次の式が得られます。

${\displaystyle \min _{P}\max _{j}A\left(P,j\right)=\max _{Q}\min _{i}A\left(i,Q\right)}$

ここで、Pとiは行の分布に応じて変化し、Qとjは列の分布に応じて変化する。

それから、${\displaystyle \lambda ^{*}}$は上記の量の共通値を表し、「ゲームの値」とも呼ばれる。${\displaystyle \delta >0}$は誤差パラメータとする。 の加法誤差によって制限されるゼロサムゲームを解くには、${\displaystyle \delta }$、

${\displaystyle \lambda ^{*}-\delta \leq \min _{i}A\left(i,q\right)}$${\displaystyle \max _{j}A\left(p,j\right)\leq \lambda ^{*}+\delta }$

つまり、O( log ₂ ( n ) /を用いて、δ の加法係数までゼロサムゲームを解くアルゴリズムが存在する。${\displaystyle \delta ^{2}}$ORACLEへの呼び出しは、呼び出しごとにO(n)の追加処理時間を要する^{[ 9 ]。}

ベイリーとピリオウラスは、乗法重み更新の時間平均挙動はゼロサムゲームにおけるナッシュ均衡に収束するものの、日々の（最後の反復）挙動はそこから乖離することを示した。^{[ 10 ]}

機械学習において、LittlestoneとWarmuthはwinnowアルゴリズムを重み付き多数決アルゴリズムに一般化した。^{[ 11 ]}その後、FreundとSchapireはそれをhedgeアルゴリズムの形で一般化した。^{[ 12 ]} Yoav FreundとRobert Schapireによって定式化されたAdaBoostアルゴリズムも乗法重み更新法を採用している。^{[ 1 ]}

${\displaystyle \forall j=1,2,{\text{…}},m:a_{j}x\geq 0}$、 ${\displaystyle 1*x=1}$、 ${\displaystyle \forall i:x_{i}\geq 0}$。

${\displaystyle \sum _{t\leq T}p^{t}m^{t}\leq \sum _{t\leq T}m_{i}^{t}+{\frac {\ln(N)}{\eta }}+\eta T}$

 1. 分布を選択する${\displaystyle p_{i}^{t}={\frac {w_{i}^{t}}{\Phi t}}}$どこ${\displaystyle \Phi t=\sum _{i}w_{i}^{t}}$。 2. 意思決定のコストを観察する${\displaystyle m^{t}}$。 3. セット ${\displaystyle w_{i}^{t+1}=w_{i}^{t}\exp(-\eta m_{i}^{t}}$)

入力： シーケンス${\displaystyle N}$ラベル付き例（${\displaystyle x_{1}}$、${\displaystyle y_{1}}$),...,(${\displaystyle x_{N}}$、${\displaystyle y_{N}}$） 分布${\displaystyle D}$オーバー${\displaystyle N}$例 弱学習アルゴリズム「WeakLearn」 整数${\displaystyle T}$反復回数を指定する 重みベクトルを初期化する:${\displaystyle w_{i}^{1}=D(i)}$のために${\displaystyle i=1,2,...,N}$. する${\displaystyle t=1,2,...,T}$1.セット${\displaystyle p^{t}={\frac {w^{t}}{\sum _{i=1}^{N}w_{i}^{t}}}}$2. WeakLearnを呼び出し、分布を指定します。${\displaystyle p^{t}}$仮説を返す${\displaystyle h_{t}:X\rightarrow }$[0,1]. 3.誤差を計算します${\displaystyle h_{t}:\epsilon _{t}=\sum _{i=1}^{N}p_{i}^{t}|h_{t}(x_{i})-y_{i}|}$4. セット​${\displaystyle \beta _{t}={\frac {\epsilon _{t}}{1-\epsilon _{t}}}}$5. 新しい重みベクトルを次のように設定します。${\displaystyle w_{i}^{t+1}=w_{i}^{t}\beta _{t}^{1-|h_{t}(x_{i})-y_{i}|}}$。 仮説を出力します。

${\displaystyle f(x)=h_{f}(x)={\begin{cases}1&{\text{if}}\sum _{t=1}^{T}(\log(1/\beta _{t}))h_{t}(x)\geq {\frac {1}{2}}\sum _{t=1}^{T}\log(1/\beta _{t})\\0&{\text{otherwise}}\end{cases}}}$

出典: ^{[ 14 ]}

${\displaystyle \exists ?x:Ax\geq b}$ （１）

${\displaystyle \exists ?x:p^{\textsf {T}}\!\!Ax\geq p^{\textsf {T}}\!b}$ （２）

進化ゲーム理論

乗法重み更新は、進化ゲーム理論でよく使われるモデルであるレプリケーター方程式（レプリケーターダイナミクス）の離散時間版です。混雑ゲームに適用すると、ナッシュ均衡に収束します。^{[ 15 ]}

オペレーションズリサーチとオンライン統計的意思決定

オペレーションズリサーチやオンライン統計的意思決定問題の分野では、加重多数決アルゴリズムとそのより複雑なバージョンが独立して発見されている。 ^{[ 1 ]}

計算幾何学

乗法重みアルゴリズムは計算幾何学でも広く応用されており、^{[ 1 ]}線形時間で変数の数に制限のある線形計画法 (LP)に対するClarksonのアルゴリズムなどがある。 ^{[ 4 ] [ 5 ]}その後、Bronnimann と Goodrich は類似の方法を用いて、 VC 次元が小さいハイパーグラフの集合被覆を見つけた。^{[ 6 ]}

勾配降下法^{[ 1 ]}

行列乗法重みの更新^{[ 1 ]}

Plotkin、Shmoys、TardosによるLPのパッキング/カバーリングのフレームワーク^{[ 1 ]}

複数商品フロー問題の近似^{[ 1 ]}

多くのNP困難問題に対するO(logn)近似^{[ 1 ]}

学習理論とブースティング^{[ 1 ]}

ハードコアセットとXOR補題^{[ 1 ]}

ハナンのアルゴリズムと乗法重み^{[ 1 ]}

オンライン凸最適化^{[ 1 ]}