Dirichlet Follow-the-Leader Closes the Gap in Simultaneous Multiclass U-Calibration

あなたは気象予報士だと想像してください。ただし、そこには一つの「ひねり」があります。あなたは、誰が自分の予報を聞いているのか、そして彼らが何を重視しているのかを知りません。例えば、ある聞き手は、あなたが完璧に雨を予測できた時だけ報酬を得る農家かもしれませんし、別の聞き手は、太陽光パネルの所有者で、あなたが日光を予測することだけを気にしているかもしれません。機械学習の世界では、これを「U-キャリブレーション（U-calibration）」と呼びます。これは予測器にとって究極のテストです。あらゆる「良さ」の尺度に関わらず、すべての人に対してうまく機能する単一の予測シーケンスを作ることができるか？という問いです。

長い間、科学者たちはこれはトレードオフのゲームだと考えてきました。もし、あなたが（急激で鋭い変化を扱う）農家に対して完璧であろうとすれば、あなたは（緩やかで漸進的な変化を好む）太陽光パネルの所有者のために予測を行う際に躓いてしまうかもしれません。それはまるで、岩の多い場所を走るのにも完璧で、かつ氷の上を滑るのにも完璧な靴を履こうとするようなものです。通常、どちらか一方を選び、もう一方を犠沢することになります。大きな疑問は、「両方の地形を同時に完璧にこなす魔法の靴が存在するのか？」ということでした。

この論文は、「はい、存在します」と述べています。著者であるパハン・デワスレンドラ（Pahan Dewasurendra）は、「ディリクレ・フォロー・ザ・リーダー（Dirichlet Follow-the-Leader）」と呼ばれる、驚くほどシンプルな手法を紹介しています。これは、料理人がスープを味わった後、硬直したレシピに基づいて次の材料を推測するのではなく、すでに使った材料をひと掴み手に取り、それらに少しのランダム性（鍋を新しく振るようなもの）を加えてブレンダーに入れ、それを次の予測として提供するようなものです。この手法は、本質的に過去の結果の「新鮮なベイズ・ブートストラップ（fresh Bayesian bootstrap）」であり、あらゆるタイプの損失関数に適応するために複雑で重厚な機械が必要なのではなく、単に何が起きたかの履歴を見て、各結果がどの程度出現したかに基づいて新しい予測を導き出せばよいことを証明しています。その結果、どのような地形を好むかを事前に知ることなく、両方の地形に対して数学的に最適であると証明された予測器が得られます。

問題点：「万人に適合しない」ジレンマ

あなたは、$K$ 個の異なる色のボールのうち、次にどの色が引かれるかを予測しなければならないゲームをしていると想像してください。各予測の後、真の色が判明します。しかし、ここでの落とし穴は、あなたがゲームのルールを知らないことです。あなたが正解した時に得られる「スコア」は、対戦相手によって選ばれた秘密の数式に依存します。

いくつかの数式は「粗い（rough）」ものです。たとえわずかな間違いであっても、崖のように厳しく罰を与えます。他の数式は「滑らか（smooth）」です。緩やかな斜面のように、小さなミスを許容します。長年、研究者たちは、粗い崖（スコアが $T$ 回目のラウンド数 $T$ に対して $\sqrt{T}$ で改善する）に優れた予測器と、緩やかな斜面（スコアが $\log T$ で改善する）に優れた予測器を構築する方法は知っていました。しかし、これらを一つにまとめて、あらゆる数式を扱える「スーパー予測器」を作ろうとすると、壁に突き当たりました。彼らができた最善の策は、不格好な妥協案であり、それは $K$（色の数）に応じて複雑に増大するペナルティを伴う、必要以上に遅いものでした。それはまるで、レーシングカーであり、かつ戦車でもあるような車を運転しようとしているようで、結果としてどちらの目的にも適さない、鈍重で遅い乗り物になってしまったのです。

解決策：「新鮮なブートストラップ」のシェフ

この論文が導入する戦略は、驚くほどシンプルです。粗いエッジを滑らかにしたり、柔らかい部分を鋭くしたりするために複雑な数学を用いる代わりに、アルゴリズムは次のように行います：

1. 集計を保持する： 色が描かれるたびに、アルゴリズムはその色のバケツに「カウント」を加算します。
2. 魔法のドロー： 次の予測を行うために、アルゴリズムは単に最も一般的な色を選ぶのではありません。代わりに、現在のカウントを「レシピ」として扱い、「ディリクレ分布」に基づいて新しい予測を生成します。

これを可視化するために、これまで見た色の数を示すマーブル（ビー玉）が入った袋を想像してください。もし赤が5回、青が3回出現していたら、5個の赤と3個の青を袋に入れます。さて、次の予測を行うとき、アルゴリズムはその袋からマーブルをひと掴み取り出し、そのひと掴みの「平均的な」色がどのようなものかを確認します。しかし、ここでのひねりは、予測を行うたびに、アルゴリズムは現在のカウントで袋を「リセット」し、新鮮なひと掴みを取り出すということです。取り出したマーブルを保持し続けるのではなく、そのひと掴みの「概念」を使用して予測を行うのです。

これは著者が「新鮮なベイズ・ブートストラップ」と呼んでいるものです。これは、毎回の食事の後に、使った材料を取り出し、新しいボウルの中で混ぜ合わせ、少し異なるバージョンの料理を提供していくシェフのようなものです。この「混ぜ合わせ」はランダムですが、履歴に基づいているため、予測は自然と「フォロー・ザ・リーダー（最も一般的な結果）」の周りに漂いながらも、他の選択肢を探求するために適度に揺れ動きます。

なぜ機能するのか：二つの秘密

この論文の素晴らしさは、このシンプルな「混ぜ合わせ」が、なぜ粗いゲームと滑らかなゲームの両方で機能するのかを証明している点にあります。著者は、これを可能にする二つの隠れた幾何学的事実を発見しました。

1. 粗いゲームのための「カウントの安定性（Count Stability）」
粗い、崖のような数式の場合、鍵となるのは「安定性」です。ある色が何度も出現している場合（例えば100回）、この「混ぜ合わせ」による変動は非常に小さくなります。アルゴリズムは自信を持っています。逆に、ある色が一度しか出現していない場合、混ぜ合わせは非常に大きくなり、アルゴリズムに柔軟性を与えます。論文は、この「混ぜ合わせ」による平均損失が、特定の「ベイズ・リスク（最善のスコア）」の差と正確に等しいという特定の数学的恒等式を証明しています。この恒等式により、数学的な計算が「望遠鏡（telescope）」のように機能し、煩雑な中間項がすべて打ち消し合い、最終的に非常に小さく管理可能な誤差だけが残ります。誤差は、クラスが観察された回数の平方根（$1/\sqrt{m}$）として減少します。これは、粗い崖に対処するためのまさに正しい速度です。

2. 滑らかなゲームのための「中心半径（Centered Radius）」
滑らかな、緩やかな斜面の数式の場合、鍵となるのは、予測が真実から離れすぎないことです。「混ぜ合わせ」による予測には特別な性質があります。その平均は正確に「フォロー・ザ・リーダー（経験的平均）」であり、その「半径（どれだけ逸脱できるか）」は、時間ステップ $t$ に対して $1/t$ として完璧に収束していきます。これは、滑らかな数式に対して、アルゴリズムがほぼ完璧な学習者として振る舞い、誤差が対数的（$\log T$）に減少することを意味します。

結果：ギャップを閉じる

この論文は、この単一のシンプルなアルゴリズムが、両方のタイプのゲームに対して同時に最高のパフォーマンスを達成することを証明しています。

• 任意の有界な適切な損失（粗い崖）に対して： レグレット（アルゴリズムと、事後的に判明した最善の策とのスコアの差）は、最大で $4\sqrt{S_T T}$ です（ここで $S_T$ はこれまでに観察された異なる結果の数）。これは可能な限り最速のレートです。
• 任意の $\beta$-滑らかな適切な損失（緩やかな斜面）に対して： レグレットは最大で $\frac{5}{2}\beta(1 + \log T)$ です。これもまた、最速のレートです。

決定的なのは、このアルゴリズムが、ゲームが「粗い」か「滑らか」かを事前に知る必要がないことです。調整すべき「学習率」も必要ありませんし、何ラウンド（$T$）行われるかを知る必要もありません。ただ履歴を見、袋を振り、予測するだけです。

これが否定したもの

この論文は、この結果を得るために複雑で次元に依存するペナルティが必要であるという考えを明確に否定しています。以前の手法は、「自己共役な摂動（self-concordant perturbations）」を用いて、$K^{5/4}$ で増大するペナルティ項を加えていましたが、これは色の数が多い場合に処理が遅くなる原因となっていました。本論文は、そのようなペナルティは不要であることを示しています。ディリクレ分布の幾何学が、自然に複雑さを処理してくれるからです。

また、このアルゴリズムは「期待レグレット（期待値としてのレグレット）」において最適であることは示していますが、単一の実行において、すべての可能な損失関数に対して同時に「ワーストケース・レグレット」においても最適であるとは主張していません（それはより強力で、おそらく不可能な保証を必要とします）。しかし、この分野で使用される標準的な定義である U-キャリブレーションにおいては、これがゴールドスタンダードとなります。

まとめ

結局のところ、この論文は、時には最も強力なツールは最もシンプルなものであるということを思い出させてくれます。過去を新鮮なランダムなひねりを加えて再サンプリングするという単純な方法によって、「ディリクレ・フォロー・ザ・リーダー」アルゴリズムは完璧なカメレオンになることができます。それは、靴を履き替える必要さえなく、険しい岩場にも滑らかな氷の上にも適応します。それは、粗い損失と滑らかな損失の間のトレードオフが、宇宙の根本的な法則ではなく、単に「袋をどう振るか」という理解の欠如であったことを証明しています。