ランダム化加重多数決アルゴリズム

ランダム化加重多数決アルゴリズムは、機械学習理論における一連の意思決定問題に対する専門家の予測を集約するためのアルゴリズムです。 ^{[ 1 ]}これは、決定論的加重多数決アルゴリズムの誤り限界 を改善する加重投票に基づくシンプルで効果的な方法です。実際、極限においては、その予測率は最も優れた予測を行う専門家の予測率に任意に近づけることができます。

毎朝、株式市場が開く前に、各「専門家」から株価が上昇するか下落するかの予測を受け取ると想像してみてください。私たちの目標は、これらの予測を何らかの方法で組み合わせ、その予測に基づいてその日の売買判断を行う単一の予測を作成することです。主な課題は、どの専門家の予測がより正確で、どの専門家の予測がより不正確か分からないことです。RWMAは、この予測を組み合わせることで、後から考えると最も正確な予測をした単一の専門家の予測とほぼ同等の予測精度を実現する方法を提供します。

機械学習において、重み付き多数決アルゴリズム（WMA）は、専門家の予測を集約するための決定論的なメタ学習アルゴリズムです。擬似コードで表すと、WMAは次のようになります。

すべてのエキスパートの重みを1に初期化します。 各ラウンドについて： 各専門家の予測した選択肢に対するそれぞれの重みを加算する 加重合計が最大となる選択肢を予測する 予測を誤ったすべての専門家の重みを乗算する${\displaystyle {\frac {1}{2}}}$

仮に${\displaystyle n}$専門家と最高の専門家が${\displaystyle m}$間違い。次に、加重多数決アルゴリズム（WMA）は最大で${\displaystyle 2.4(\log _{2}n+m)}$間違い。この上限は、非常に間違いやすい専門家の場合には非常に問題があります。たとえば、最高の専門家が20%の確率で間違いを犯すとします。つまり、${\displaystyle N=100}$ラウンドを使用する${\displaystyle n=10}$専門家、最高の専門家が${\displaystyle m=20}$間違い。すると、重み付き多数決アルゴリズムは上限のみを保証します。${\displaystyle 2.4(\log _{2}10+20)\approx 56}$間違い。

これは重み付き多数決アルゴリズムの既知の制限であるため、依存度を改善するためにさまざまな戦略が検討されてきました。${\displaystyle m}$特に、ランダム化を導入することで、より良い結果が得られるだろう。

乗法重み更新法アルゴリズムからヒントを得て、専門家が過去に行ったパフォーマンスに基づいて確率的に予測を行います。WMAと同様に、専門家が誤った予測を行うたびに、その専門家の重みを減らします。MWUMを模倣して、重みを使用してアクションの確率分布を作成し、この分布からアクションを選択します（WMAのように決定論的に多数決を選択するのではなく）。^{[ 2 ]}

ランダム化加重多数決アルゴリズムは、WMA の誤差範囲の依存性を改善しようとする試みである。${\displaystyle m}$多数決に基づいて予測するのではなく、各ラウンドで専門家を選択する確率として重みが使用され、時間の経過とともに更新されます（そのため、ランダム化加重多数決と呼ばれます）。

正確には、もし${\displaystyle w_{i}}$専門家の重み${\displaystyle i}$、 させて${\displaystyle W=\sum _{i}w_{i}}$専門家の指示に従います${\displaystyle i}$確率で${\displaystyle {\frac {w_{i}}{W}}}$その結果、以下のアルゴリズムが得られます。

すべてのエキスパートの重みを1に初期化します。 各ラウンドについて： すべての専門家の重みを合計して、総重みを求めます。${\displaystyle W}$ 専門家を選ぶ${\displaystyle i}$確率でランダムに${\displaystyle {\frac {w_{i}}{W}}}$ 選ばれた専門家が予測するように予測する 予測を誤ったすべての専門家の重みを乗算する${\displaystyle \beta }$

目標は、コイン投げを行う前に攻撃者がいずれかの回答を正解として選択しなければならないと仮定した場合の、最悪の場合の予想される間違いの数を制限することです。これは、例えば上記の株式市場の例において妥当な仮定です。株価の変動は、個人の売買決定に影響を与える専門家の意見に依存しないはずなので、価格変動は専門家がその日の推奨を行う前に決定されたものとして扱うことができます。

ランダム化アルゴリズムは、最悪の場合、決定論的アルゴリズム（加重多数決アルゴリズム）よりも優れています。後者の場合、最悪のケースは重みが50/50に分割されたときでした。しかし、ランダム化バージョンでは、重みが確率として使用されるため、正解する確率は依然として50/50です。さらに、誤った専門家の重みを乗算することに一般化します。${\displaystyle \beta <1}$厳密にではなく${\displaystyle {\frac {1}{2}}}$依存度とトレードオフを可能にする${\displaystyle m}$そして${\displaystyle \log _{2}n}$このトレードオフについては、分析セクションで定量的に説明します。

させて${\displaystyle W_{t}}$ラウンドにおける全専門家の総重みを表す${\displaystyle t}$また、${\displaystyle F_{t}}$ラウンドで間違った答えを予測した専門家に与えられた重みの割合を表す${\displaystyle t}$最後に、${\displaystyle N}$プロセスにおけるラウンドの総数とする。

定義により、${\displaystyle F_{t}}$アルゴリズムがラウンドで間違いを犯す確率${\displaystyle t}$期待値の線形性から、もし${\displaystyle M}$は、全プロセス中に発生したミスの総数を表します。${\displaystyle E[M]=\sum _{t=1}^{N}F_{t}}$。

ラウンド後${\displaystyle t}$総重量は減少します${\displaystyle \ (1-\beta )F_{t}W_{t}}$間違った答えに対応するすべての重みは、${\displaystyle \ \beta <1}$すると、${\displaystyle W_{t+1}=W_{t}(1-(1-\beta )F_{t})}$伸縮により、${\displaystyle W_{1}=n}$したがって、プロセス終了後の総重量は次のようになる。

${\displaystyle {\begin{aligned}W=n\prod _{t=1}^{N}(1-(1-\beta )F_{t}).\end{aligned}}}$

一方、${\displaystyle \ m}$これは、最も優れたパフォーマンスを発揮した専門家が犯したミスの数です。最終的に、この専門家は重みを持ちます。$\displaystyle \ \beta ^{m}}$したがって、総重量は少なくともこれだけである。言い換えれば、${\displaystyle \ W\geq \beta ^{m}}$この不等式と上記の結果は、

${\displaystyle {\begin{aligned}n\prod _{t=1}^{N}(1-(1-\beta )F_{t})\geq \beta ^{m}.\end{aligned}}}$

両辺の自然対数を取ると、

${\displaystyle {\begin{aligned}\ln n+\sum _{t=1}^{N}\ln(1-(1-\beta )F_{t})\geq m\ln \beta .\end{aligned}}}$

さて、自然対数のテイラー級数は

${\displaystyle {\begin{aligned}\ln(1-x)=-x-{\frac {x^{2}}{2}}-{\frac {x^{3}}{3}}-\cdots \end{aligned}}}$

特に、次のことが導かれる。${\displaystyle \ \ln(1-(1-\beta )F_{t})<-(1-\beta )F_{t}}$。したがって、

${\displaystyle {\begin{aligned}\ln n-(1-\beta )\sum _{t=1}^{N}F_{t}\geq m\ln \beta .\end{aligned}}}$

思い出すと${\displaystyle E[M]=\sum _{t=1}^{N}F_{t}}$そして並べ替えると、

${\displaystyle {\begin{aligned}E[M]\leq {\frac {m\ln(1/\beta )+\ln(n)}{1-\beta }}={\frac {\ln(1/\beta )}{1-\beta }}m+{\frac {1}{1-\beta }}\ln(n).\end{aligned}}}$

さて、${\displaystyle \beta \to 1}$下から見ると、最初の定数は${\displaystyle 1}$;ただし、2番目の定数は${\displaystyle +\infty }$このトレードオフを定量化するために、${\displaystyle \varepsilon =1-\beta }$予測を間違えた場合のペナルティとする。次に、自然対数のテイラー級数を再び適用すると、

${\displaystyle {\begin{aligned}{\frac {\ln(1/\beta )}{1-\beta }}=-{\frac {\ln(\beta )}{1-\beta }}={\frac {-\ln(1-\varepsilon )}{\varepsilon }}={\frac {\varepsilon +{\frac {\varepsilon ^{2}}{2}}+{\frac {\varepsilon ^{3}}{3}}+\cdots }{\varepsilon }}=1+{\frac {\varepsilon }{2}}+O(\varepsilon ^{2})\end{aligned}}}$

したがって、小さな誤差範囲は${\displaystyle \varepsilon }$は、次の形式で記述できます。${\displaystyle \ \left(1+{\frac {\epsilon }{2}}+O(\varepsilon ^{2})\right)m+\epsilon ^{-1}\ln(n)}$。

英語では、専門家の間違いに対するペナルティが少ないほど、追加の専門家は初期段階で間違いを起こしやすくなりますが、時間が経つにつれて、最良の専門家の予測精度に近づいていきます。特に、十分に低い値の場合、${\displaystyle \varepsilon }$十分なラウンド数を経れば、ランダム化加重多数決アルゴリズムは、最良の専門家の正答率に限りなく近づくことができる。

特に、${\displaystyle m}$に比べて十分に大きい${\displaystyle \ln(n)}$（その比率が十分に小さいように）

$\displaystyle {\begin{aligned}\varepsilon ={\sqrt {\frac {\ln(n)}{m}}}\end{aligned}}}$

間違いの数の上限は次のように得られます。

${\displaystyle {\begin{aligned}m+O({\sqrt {m\ln(n)}}).\end{aligned}}}$

これは、アルゴリズムの「後悔限界」（つまり、最良のエキスパートよりもどれだけパフォーマンスが劣るか）が、${\displaystyle O({\sqrt {m\ln(n)}})}$。

ランダム加重多数決アルゴリズムの動機は、最良の専門家が20%の確率で間違いを犯すという例によって与えられたことを思い出してください。正確には、${\displaystyle N=100}$ラウンド、${\displaystyle n=10}$専門家、最高の専門家が${\displaystyle m=20}$間違いの場合、決定論的加重多数決アルゴリズムは上限のみを保証します。${\displaystyle 2.4(\log _{2}10+20)\approx 56}$上記の分析から、最悪の場合の予想ミスの数を最小化することは、関数を最小化することと同等であることがわかる。

${\displaystyle {\begin{aligned}{\frac {\ln(1/\beta )}{1-\beta }}20+{\frac {1}{1-\beta }}\ln(10).\end{aligned}}}$

計算方法によると、最適値はおおよそ${\displaystyle \beta \approx 0.641}$これにより、最悪の場合の予想されるミスの最小数は${\displaystyle E[M]\approx 31.19}$ラウンド数を増やすと（例えば、${\displaystyle N=1000000}$）最良の専門家の精度率を同じに保ったまま改善はさらに劇的になる可能性がある。加重多数決アルゴリズムは最悪の場合の誤り率を48.0%しか保証しないが、ランダム化加重多数決アルゴリズムは、最適な値に適切に調整すると、${\displaystyle \varepsilon \approx 0.0117}$最悪の場合の誤り率は20.2%となる。

ランダム加重多数決アルゴリズム（RWMA）は、複数のアルゴリズムを組み合わせるために使用でき、その場合、RWMAは結果的に元のアルゴリズムの中で最も優れたものとほぼ同等の性能を発揮することが期待できます。RWMAは、二値的な誤り変数を持たない問題にも一般化できるため、幅広い問題クラスに適用可能です。

さらに、ランダム加重多数決アルゴリズムは、専門家が選択する選択肢を組み合わせることができない（または容易に組み合わせることができない）状況にも適用できます。例えば、RWMAは繰り返しゲームプレイやオンライン最短経路問題に適用できます。オンライン最短経路問題では、各専門家が通勤経路をそれぞれ異なる方法で提案します。あなたはRWMAを使用して1つの経路を選択します。その後、提案されたすべての経路を使用した場合にどれだけうまくいったかを調べ、適切にペナルティを課します。目標は、期待損失が最良の専門家の損失とそれほど変わらないようにすることです。

• 多腕バンディット問題。
• 専門家が多数いる場合など、特定のケースにおいて効率的なアルゴリズム。
• 睡眠の専門家／「スペシャリスト」がいる環境。

• 機械学習
• 加重多数決アルゴリズム
• ゲーム理論
• 多腕強盗

• 加重多数決とランダム加重多数決
• アヴリム・ブルム（2004）機械学習理論
• ロブ・シャピアー著『機械学習の基礎』（2006年）
• 専門家の助言に基づく予測
• ウリ・ファイギ、ロビ・クラウスゲーマー、モニ・ナオール。アルゴリズムゲーム理論
• ニカ・ハグタラブ 2020 機械学習の理論的基礎（ノート）