乗法的重み更新方法

乗法重み更新法は、意思決定と予測に最も一般的に使用されるアルゴリズム手法であり、ゲーム理論とアルゴリズム設計にも広く採用されています。最も単純な使用例は、専門家のアドバイスからの予測の問題であり、意思決定者は、アドバイスに従うべき専門家を繰り返し決定する必要があります。この方法は、エキスパートに初期重み（通常は同一の初期重み）を割り当て、エキスパートのパフォーマンスのフィードバックに従って、これらの重みを乗法的および反復的に更新します。パフォーマンスが悪い場合はそれを減らし、そうでなければそれを増やします。機械学習（AdaBoost、Winnow、Hedge）、最適化（線形プログラムの解決）、理論的コンピューターサイエンス（LPおよびSDPの高速アルゴリズムの考案）、ゲーム理論など、非常に多様な分野で繰り返し発見されました。

名前

「乗法の重み」は、乗法の重み更新方法から派生したアルゴリズムで使用される反復規則を意味します。発見または再発見されたフィールドごとに異なる名前が付けられています。

歴史と背景

この手法の最も初期の既知のバージョンは、1950年代初期のゲーム理論で提案された「架空のプレイ」という名前のアルゴリズムにありました。 GrigoriadisとKhachiyanは、「架空のプレイ」のランダム化されたバリアントを適用して、乗法の重みアルゴリズムを使用して2人のゼロサムゲームを効率的に解決しました。この場合、プレーヤーはより良い結果が得られたアクションにより高い重みを割り当て、これらの重みに基づいて戦略を選択します。機械学習では、Littlestoneは、Minsky and Papertの以前のパーセプトロン学習アルゴリズムに似た、有名なwinnowアルゴリズムで乗法重み更新ルールの最も早い形式を適用しました。その後、彼はwinnowアルゴリズムを重み付き多数決アルゴリズムに一般化しました。フロイントとシャピレは彼の手順に従い、winnowアルゴリズムをヘッジアルゴリズムの形式で一般化しました。

乗法重みアルゴリズムは、線形時間の変数の数が制限されている線形計画法（LP）のクラークソンのアルゴリズムなど、計算幾何学にも広く適用されています。後に、ブロンニマンとグッドリッチは類似の方法を使用して、VC次元が小さいハイパーグラフの集合カバーを見つけました。

運用研究およびオンライン統計的意思決定問題の分野では、加重多数決アルゴリズムとそのより複雑なバージョンが独立して発見されています。

コンピューターサイエンスの分野では、異なるコンテキストで使用される乗法的更新アルゴリズム間の密接な関係を以前に観察した研究者もいます。ヤングは、高速LPアルゴリズムと、ランダム化された丸めアルゴリズムのランダム化解除のための悲観的推定量のRaghavanの方法との類似性を発見しました。 KlivansとServedioは、学習理論のブースティングアルゴリズムをYaoのXOR補題の証明にリンクしました。 GargとKhandekarは、サブケースとしてGarg-KonemannとPlotkin-Shmoys-Tardosを含む凸最適化問題の共通フレームワークを定義しました。

一般的なセットアップ

関連する見返りを得るには、n人の専門家の意見に基づいてバイナリの決定を行う必要があります。最初のラウンドでは、すべての専門家の意見は同じ重みを持っています。意思決定者は、専門家の予測の大部分に基づいて最初の決定を行います。その後、各決定ラウンドで、意思決定者は、各専門家の以前の予測の正確さに応じて、各専門家の意見の重みを繰り返し更新します。実際の例には、明日雨が降るかどうか、または株式市場が上下するかどうかを予測することが含まれます。

アルゴリズム分析

アルゴリズムの半分

敵とN人の専門家から助言を受けたアグリゲーターとの間で連続したゲームをプレイする場合、アグリゲーターができる限りミスを少なくすることが目標です。 N人の専門家の中に、常に正しい予測をする専門家がいると仮定します。半分のアルゴリズムでは、一貫した専門家のみが保持されます。間違いを犯した専門家は解雇されます。アグリゲーターは、すべての決定について、残りの専門家の間で多数決投票を行うことにより決定します。したがって、アグリゲーターがミスをするたびに、残りのエキスパートの少なくとも半分が解雇されます。アグリゲーターは最大でログ2 （ N ）の間違いを犯します。

重み付き多数決アルゴリズム

ミスを犯した専門家を解任するアルゴリズムを半分にするのとは異なり、重み付き多数決アルゴリズムはアドバイスを無視します。同じ「専門家のアドバイス」の設定を考えて、n個の決定があり、ループごとに1つの決定を選択する必要があるとします。各ループでは、すべての決定にコストがかかります。選択後、すべての費用が明らかになります。エキスパートが正しければコストは0で、そうでなければ1です。このアルゴリズムの目標は、累積損失を最高の専門家とほぼ同じに制限することです。反復のたびに多数決に基づいて選択する最初のアルゴリズムは機能しません。なぜなら、専門家の大多数は常に一貫して間違っている可能性があるからです。重み付き多数決アルゴリズムは、コストを1または0に固定するのではなく、専門家の重みを維持することにより、上記の自明なアルゴリズムを修正します。これにより、アルゴリズムを半分にするよりもミスが少なくなります。

初期化 ：η≤1/ 2 {\ displaystyle \ eta \ leq 1/2}を修正します。エキスパートごとに、重みwi1 {\ displaystyle {w_ {i}} ^ {1}}≔1を関連付けます。 T {\ displaystyleさt} の 1 {\ displaystyle {\ mathit {1}}}、{2 \ displaystyle {\ mathit {2}}}、...、T {\ displaystyleのT} = 1。 weightsw1t、...、wnt {\ displaystyle \ mathbb {w_ {1}} ^ {t}、...、\ mathbb {w_ {n}に基づいて、専門家の予測の加重大部分によって与えられた予測を行います} ^ {t}}。つまり、アドバイスする専門家の総重みが高い予測に応じて、0または1を選択します（関係を任意に解除します）。 2 。誤って予測したすべての専門家iに対して、次のラウンドの係数に（1-η）を掛けて重みを減らします。wit + 1 {\ displaystyle w_ {i} ^ {t + 1}} =（1−η ）wit {\ displaystyle（1- \ eta）w_ {i} ^ {t}}（更新ルール）

η= 0 {\ displaystyle \ eta = 0}の場合、専門家のアドバイスの重みは変わりません。 η{\ displaystyle \ eta}が増加すると、専門家のアドバイスの重みは減少します。一部の研究者は、重み付き多数決アルゴリズムのη= 1/2 {\ displaystyle \ eta = 1/2}を修正していることに注意してください。

T {\ displaystyle T}ステップの後、miT {\ displaystyle m_ {i} ^ {T}}をエキスパートiのミスの数とし、MT {\ displaystyle M ^ {T}}をアルゴリズムのミスの数とします製。次に、すべてのi {\ displaystyle i}に対して次の境界があります。

MT≤2（1 +η）miT +2ln⁡（n）η{\ displaystyle M ^ {T} \ leq 2（1+ \ eta）m_ {i} ^ {T} + {\ frac {2 \ ln（ n）} {\ eta}}}。

特に、これは最高の専門家であるiに当てはまります。最高のエキスパートは最小のmiT {\ displaystyle m_ {i} ^ {T}}を持っているので、アルゴリズム全体で行われたミスの数の最高の限界を与えます。

ランダム化された重み付き多数決アルゴリズム

N人の専門家と同じセットアップを考えます。重みを数えて、正と負を予測する専門家の割合が両方とも50％に近い特別な状況を考えてみましょう。次に、ネクタイがあります。重み付き多数決アルゴリズムの重み更新規則に従って、アルゴリズムによって行われた予測はランダム化されます。アルゴリズムは、正または負を予測する専門家の確率を計算し、計算された割合に基づいてランダムな決定を行います。

予測する

f（x）= {1with probabilityq1W0otherwise {\ displaystyle f（x）= {\ begin {cases} 1＆{\ text {with potential}} {\ frac {q_ {1}} {W}} \\ 0＆{\ text {そうでなければ} \ end {cases}}}

どこ

W = ∑iwi = q0 + q1 {\ displaystyle W = \ sum _ {i} {w_ {i}} = q_ {0} + q_ {1}}。

ランダム化された重み付き多数決アルゴリズムによるミスの数は、次のように制限されます。

E≤αβ（＃最高の専門家の間違い）+cβln⁡（N）{\ displaystyle E \ left \ leq \ alpha _ {\ beta} \ left（\＃{\ text {最高の専門家の間違い}} \ right ）+ c _ {\ beta} \ ln（N）}

ここで、αβ=ln⁡（1β）1-β{\ displaystyle \ alpha _ {\ beta} = {\ frac {\ ln（{\ frac {1} {\ beta}}）} {1- \ beta}}}およびcβ=11-β{\ displaystyle c _ {\ beta} = {\ frac {1} {1- \ beta}}}。

学習アルゴリズムのみがランダム化されることに注意してください。基本的な前提は、例と専門家の予測はランダムではないということです。唯一のランダム性は、学習者が自分で予測するランダム性です。このランダム化アルゴリズムでは、β→1 {\ displaystyle \ beta \ rightarrow 1}の場合、αβ→1 {\ displaystyle \ alpha _ {\ beta} \ rightarrow 1}です。重み付きアルゴリズムと比較して、このランダム性は、アルゴリズムが行う間違いの数を半減させました。ただし、いくつかの研究では、人々は重み付き多数決アルゴリズムでη= 1/2 {\ displaystyle \ eta = 1/2}を定義し、0≤η≤1{\ displaystyle 0 \ leq \ eta \ leqを許可することに注意することが重要です1}ランダム化重み付き多数決アルゴリズム。

用途

乗法重み法は、通常、制約付き最適化問題を解決するために使用されます。各専門家を問題の制約とし、イベントは関心領域のポイントを表します。エキスパートの処罰は、イベントによって表されるポイントで対応する制約がどれだけ満たされるかに対応します。

ゼロサムゲームのおおよその解決（Oracleアルゴリズム）：

専門家の分布P {\ displaystyle P}が与えられたとします。 A {\ displaystyle A} = n {\ displaystyle n}行の有限2人プレーヤーのゼロサムゲームのペイオフマトリックスとします。

行プレーヤーpr {\ displaystyle p_ {r}}がプランi {\ displaystyle i}を使用し、列プレーヤーpc {\ displaystyle p_ {c}}がプランj {\ displaystyle j}を使用する場合、プレーヤーpc {\ displaystyle p_ {c}}はA（i、j）{\ displaystyle A \ left（i、j \ right）}≔Aij{\ displaystyle A_ {ij}}です。A（i、j）∈{\ displaystyle A \ left（i、j \ right）\ in \ left}。

プレーヤーpr {\ displaystyle p_ {r}}が行の分布P {\ displaystyle P}からアクションi {\ displaystyle i}を選択した場合、アクションjを選択したプレーヤーpc {\ displaystyle p_ {c}}の期待される結果{\ displaystyle j}はA（P、j）=Ei∈P{\ displaystyle A \ left（P、j \ right）= E_ {i \ in P} \ left}です。

A（P、j）{\ displaystyle A \ left（P、j \ right）}を最大化するには、プレーヤーpc {\ displaystyle p_ {c}}がプランj {\ displaystyle j}を選択する必要があります。同様に、プレーヤーpl {\ displaystyle p_ {l}}に期待されるペイオフは、A（i、P）=Ej∈P{\ displaystyle A \ left（i、P \ right）= E_ {j \ in P} \ leftです。 }。プランi {\ displaystyle i}を選択すると、この見返りが最小限に抑えられます。ジョンフォンノイマンの最小-最大定理により、次のようになります。

minPmaxjA（P、j）= maxQminiA（i、Q）{\ 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 ^ {*}}が上記の量の一般的な値を示し、「ゲームの値」とも呼ばれます。 δ> 0 {\ displaystyle \ delta> 0}をエラーパラメーターとします。 δ{\ displaystyle \ delta}の加法誤差によって制限されたゼロサムゲームを解決するには、

λ∗ −δ≤miniA（i、q）{\ displaystyle \ lambda ^ {*}-\ delta \ leq \ min _ {i} A \ left（i、q \ right）} maxjA（p、j）≤λ ∗ +δ{\ displaystyle \ max _ {j} A \ left（p、j \ right）\ leq \ lambda ^ {*} + \ delta}

そのため、O（log 2 （ n ）/δ2{\ displaystyle \ delta ^ {2}}）をORACLEに呼び出し、追加の処理時間O（ n）コールごと

ベイリーとピリオウラスは、乗法の重み更新の時間平均の振る舞いはゼロサムゲームでナッシュ均衡に収束するが、日々の（最後の反復）振る舞いはそれから離れることを示した。

機械学習

機械学習では、LittlestoneとWarmuthはwinnowアルゴリズムを重み付き多数決アルゴリズムに一般化しました。その後、フロイントとシャピレはそれをヘッジアルゴリズムの形で一般化しました。 Yoav FreundとRobert Schapireによって定式化されたAdaBoostアルゴリズムも、乗法的重み更新法を採用しました。

Winnowアルゴリズム

アルゴリズムの現在の知識に基づいて、乗数の重みの更新方法がリトルストーンのwinnowアルゴリズムで最初に使用されました。機械学習で線形プログラムを解くために使用されます。

m {\ displaystyle m}というラベルの付いた例（a1、l1）、…、（am、lm）{\ displaystyle \ left（a_ {1}、l_ {1} \ right）、{\ text {…}}、\ left（a_ {m}、l_ {m} \ right）}ここで、aj∈Rn{\ displaystyle a_ {j} \ in \ mathbb {R} ^ {n}}は特徴ベクトルであり、lj∈{-1,1,1 } {\ displaystyle l_ {j} \ in \ left \ {-1,1 \ right \} \ quad}はラベルです。

目的は、すべての例で、特徴の重み付き組み合わせの符号がそのラベルと一致するように、負でない重みを見つけることです。つまり、すべてのj {\ displaystyle j}に対してljajx≥0{\ displaystyle l_ {j} a_ {j} x \ geq 0}が必要です。一般性を失うことなく、総重量が1であると仮定して、分布を形成します。したがって、表記上の便宜上、aj {\ displaystyle a_ {j}}をljaj {\ displaystyle l_ {j} a_ {j}}に再定義すると、問題は次のLPの解を見つけることになります。

∀j= 1,2、…、m：ajx≥0{\ displaystyle \ forall j = 1,2、{\ text {…}}、m：a_ {j} x \ geq 0}、1 ∗ x = 1 {\ displaystyle 1 * x = 1}、∀i：xi≥0{\ displaystyle \ forall i：x_ {i} \ geq 0}。

これはLPの一般的な形式です。

ヘッジアルゴリズム

ヘッジアルゴリズムは、重み付き多数決アルゴリズムに似ています。ただし、それらの指数関数的な更新ルールは異なります。一般に、リソースの異なる部分をN個の異なるオプションに割り当てる必要があるバイナリ割り当ての問題を解決するために使用されます。すべてのオプションでの損失は、すべての反復の終わりに利用可能です。目標は、特定の割り当てで被る総損失を減らすことです。その後、乗算更新を使用して、現在の反復で被った合計損失に基づいて、次の反復の割り当てが修正されます。

分析

学習率η> 0 {\ displaystyle \ eta> 0}を想定し、t∈{\ displaystyle t \ in}の場合、pt {\ displaystyle p ^ {t}}がHedgeによって選択されます。次に、すべてのエキスパートi {\ displaystyle i}に対して、

∑t≤Tptmt≤∑t≤Tmit +ln⁡（N）η+ηT{\ displaystyle \ sum _ {t \ leq T} p ^ {t} m ^ {t} \ leq \ sum _ {t \ leq T } m_ {i} ^ {t} + {\ frac {\ ln（N）} {\ eta}} + \ eta T}

初期化 ：η> 0 {\ displaystyle \ eta> 0}を修正します。各専門家のために、体重WI1を関連付ける{\ displaystyle W_ {I} ^ {1}}≔1T に対する = 1,2、...、T。

1.分布pit =witΦt{\ displaystyle p_ {i} ^ {t} = {\ frac {w_ {i} ^ {t}} {\ Phi t}}}を選択します。ここで、Φt= ∑iwit {\ displaystyle \ Phi t = \ sum _ {i} w_ {i} ^ {t}}。 2.決定のコストmt {\ displaystyle m ^ {t}}を観察します。 3. wit + 1 =witexp⁡（−ηmit {\ displaystyle w_ {i} ^ {t + 1} = w_ {i} ^ {t} \ exp（-\ eta m_ {i} ^ {t}}）を設定します。AdaBoostアルゴリズム

このアルゴリズムは、トレーニング例の重みのセットwt {\ displaystyle w ^ {t}}を維持します。すべての反復t {\ displaystyle t}で、分布pt {\ displaystyle p ^ {t}}はこれらの重みを正規化して計算されます。この分布は、弱学習器WeakLearnに供給されます。WeakLearnは、分布に関して（できれば）誤差が小さいという仮説ht {\ displaystyle h_ {t}}を生成します。新しい仮説ht {\ displaystyle h_ {t}}を使用して、AdaBoostは次の重みベクトルwt + 1 {\ displaystyle w ^ {t + 1}}を生成します。プロセスが繰り返されます。このようなT回の反復の後、最終仮説hf {\ displaystyle h_ {f}}が出力になります。仮説hf {\ displaystyle h_ {f}}は、重み付き多数決を使用してT個の弱い仮説の出力を結合します。

入力 ：N {\ displaystyle N}のラベルが付いた例のシーケンス（x1 {\ displaystyle x_ {1}}、y1 {\ displaystyle y_ {1}}）、…、（xN {\ displaystyle x_ {N}}、yN {\ displaystyle y_ {N}}）N {\ displaystyle N}の例での分布D {\ displaystyle D}例反復学習の数を指定する弱学習アルゴリズム「 'WeakLearn」'整数T {\ displaystyle T}重みベクトルを初期化します：wi1 = D （i）{\ displaystyle w_ {i} ^ {1} = D（i）} for i = 1 {\ displaystyle i = 1}、...、N {\ displaystyle N}。トンのために行う = 1 {\ displaystyleトン= 1}、...、N {\ displaystyle N} 1。 pt = wt∑i = 1Nwit {\ displaystyle p ^ {t} = {\ frac {w ^ {t}} {\ sum _ {i = 1} ^ {N} w_ {i} ^ {t}}}を設定します}。 2 。 WeakLearnを呼び出して、配布pt {\ displaystyle p ^ {t}}を提供します。仮説ht：X→{\ displaystyle h_ {t}：X \ rightarrow}を取得します。 ３ 。 ht：ϵt = ∑i = 1Npit {\ displaystyle h_ {t}：\ epsilon _ {t} = \ sum _ {i = 1} ^ {N} p_ {i} ^ {t}} | htの誤差を計算します（xi）{\ displaystyle h_ {t}（x_ {i}）}。 4 。 βt= ϵt1−ϵt {\ displaystyle \ beta _ {t} = {\ frac {\ epsilon _ {t}} {1- \ epsilon _ {t}}}}を設定します。 5 。新しい重みベクトルをwit + 1 = witβt1− | ht（xi）−yi | {\ displaystyle w_ {i} ^ {t + 1} = w_ {i} ^ {t} \ beta _ {t} ^に設定します{1- | h_ {t}（x_ {i}）-y_ {i} |}}。仮説を出力します：f（x）= {1if∑t =1Tlog⁡（1 /βt）ht（x）≥12∑t =1Tlog⁡（1 /βt）q1W0otherwise {\ displaystyle f（x）= {\ begin {ケース} 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}）{\ frac {q_ {1}} {W}} \\ 0＆{\ text {otherwise}} \ end {cases}}}

線形計画をほぼ解く

問題

am×n {\ displaystyle m \ times n}行列A {\ displaystyle A}およびb∈Rn{\ displaystyle b \ in \ mathbb {R} ^ {n}}が与えられた場合、ax {\ displaystyle x}はAx≥b{\ displaystyle Ax \ geq b}？

∃？x：Ax≥b{\ displaystyle \ exists？x：Ax \ geq b}（1）仮定

エラーパラメーターϵ> 0 {\ displaystyle \ epsilon> 0}でゼロサム問題を解決するためにOracleアルゴリズムを使用すると、出力はAx≥b−ϵ {\ displaystyleのような点x {\ displaystyle x}になります。 Ax \ geq b- \ epsilon}またはx {\ displaystyle x}が存在しないという証明。つまり、この不等式の線形システムに対する解決策はありません。

解決

ベクトルp∈Δn{\ displaystyle p \ in \ Delta _ {n}}が与えられた場合、次の緩和された問題を解きます

∃？x：pTAx≥pTb{\ displaystyle \ exists？x：p ^ {\ textsf {T}} \！\！Ax \ geq p ^ {\ textsf {T}} \！b}（2）

（1）を満たすaxが存在する場合、xはすべてのp∈Δn{\ displaystyle p \ in \ Delta _ {n}}について（2）を満たします。この声明の反対も事実です。 oracleがap {\ displaystyle p}の実行可能な解を返す場合、それが返す解x {\ displaystyle x}が幅maxi |（Ax）i-bi |≤1{\ displaystyle \ max _ {i} | { （Ax）} _ {i} -b_ {i} | \ leq 1}。 （1）の解決策がある場合、その出力xが2ϵ {\ displaystyle 2 \ epsilon}の加算誤差までシステム（2）を満たすアルゴリズムがあります。アルゴリズムは、最大でln⁡（m）ϵ2 {\ displaystyle {\ frac {\ ln（m）} {\ epsilon ^ {2}}}}を呼び出して、問題の幅に制限のあるoracleを呼び出します（2）。反陽性も同様です。この場合、乗算更新がアルゴリズムに適用されます。

その他の用途

進化ゲーム理論

乗法的重みの更新は、進化ゲーム理論で一般的に使用されるモデルであるレプリケーター方程式（レプリケーターダイナミクス）の離散時間バリアントです。輻輳ゲームに適用すると、ナッシュ均衡に収束します。

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

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

計算幾何学

乗法重みアルゴリズムは、線形時間での変数の境界数を持つ線形プログラミング（LP）のクラークソンのアルゴリズムなど、計算幾何学にも広く適用されます。後に、ブロンニマンとグッドリッチは、VC次元が小さいハイパーグラフのセットカバーを見つけるための類似の方法を採用しました。

勾配降下法行列乗法重みの更新LPをパッキング/カバーするためのPlotkin、Shmoys、Tardosフレームワークおよび乗法の重みオンライン凸最適化