An Optimal Agnostic PAC Algorithm

ロボットに猫と犬を見分ける方法を教えようとしている場面を想像してみてください。あなたは数千枚の写真をロボットに見せますが、世界は混沌としています：時には猫が暗闇に隠れていたり、時には犬が帽子を被っていたり、時にはあなたが与えたラベル自体がそもそも間違っていたりします。これは機械学習、特に統計的学習理論と呼ばれる分野の世界です。ここでの大きな疑問は、ロボットが優れた推論ができるようになるには、どれだけの例を見る必要があるのか？ということです。

この問いに答えるために、科学者たちはVC次元（VapnikとChervonenkisにちなんで名付けられました）という概念を用います。VC次元とは、ロボットの脳がいかに「混乱しやすい」か、あるいは「複雑」かを示す尺度だと考えてください。耳の形だけを見る単純な脳はVC次元が低くなります。一方で、あらゆるピクセルを注視する超複雑な脳はVC次元が高くなります。目標は、ロボットが役に立つほど速く学習しつつ、学習用の写真そのものを丸暗記してしまうほど複雑になりすぎないような「スイートスポット」を見つけることです。何十年もの間、数学者たちは、特定の数の例と一定の複雑さに対し、ロボットが「絶対的に最高のロボット」と比較してどれだけの「追加の誤差」を生じるかを正確に伝える完璧な公式を見つけようと試みてきました。

長い間、知識の空白がありました。データが完璧な場合（ラベルに間違いがない場合）の最適な学習速度は分かっていましたし、データが非常に乱れている場合の速度も分かっていました。しかし、その中間はどうなのでしょうか？もしデータが少しだけノイズを含んでいるとしたら？これまでの試みは、重いバックパックを背負ってレースをしているようなものでした。彼らは惜しいところまで行ってはいましたが、必要以上に遅くなる「対数的（logarithmic）」な重みを背負っていました。大きな疑問はこうです：データのノ礫さがどの程度であっても、その余計な重みを背負うことなく、絶対的に最速のスピードで走れる学習器を構築できるのでしょうか？

「An Optimal Agnostic PAC Algorithm」と題されたこの論文は、その問いに対して、力強い「イエス」という回答を出しています。著者であるMarkus Engelund Mathiasen、Jian Qian、そしてNikita Zhivotovskiyは、統計的に最適なリスク境界を実現する特定の学習アルゴリズムを構築しました。平易な言葉で言えば、彼らは、可能な限り間違いを最小限に抑える分類器を構築する方法を見つけ出し、どのような固定されたノイズレベルに対しても、他のいかなる手法も（いくつかの普遍的な定数を除いて）彼らを打ち負かすことはできないことを数学的に証明したのです。彼らは単に推測したのではなく、証明したのです。

彼らがどのように行ったのかを、非常に整理された図書館と、巧妙な「ワン・インクルージョン（One-inclusion）」ゲームの物語を用いて説明します。

問題：ノイズの多い図書館

巨大な図書館を想像してください。そこにあるすべての本は画像であり、すべての本の背表紙には「猫」または「犬」というラベルが付いています。しかし、司書は少し不器用です。時々、本に誤ったラベルを貼ったり、本が損傷していたりします。あなたは、ラベルのない新しい本を見て、そのラベルを正しく推測できるシステムを作りたいと考えています。

「最高に優れた」システム（これをオラクルと呼びましょう）は、宇宙の真のルールを知っています。たとえオラクルであっても、司書のラベルが間違っていることがあるため、いくらかのミスは避けられません。この最小エラー率は $L^*$ と呼ばれます。あなたの目標は、図書館から限られた数の本（$n$）を用いて、オラクルのパフォーマンスに限りなく近づくシステムを構築することです。

この論文は、彼らの新しいシステム（ザ・オプティマイザーと呼びましょう）のエラー率（$L(\hat{h})$）が次のように制限されることを証明しています：
$$L(\hat{h}) \le L^* + 7 \cdot 10^8 \left( \sqrt{\frac{L^*(d + \log(1/\delta))}{n}} + \frac{d + \log(1/\delta)}{n} \right)$$
数学を怖がらないでください。鍵となるのは平方根の項です。この式は、追加のミス（「超過リスク」）が本の数（$n$）が増えるにつれて減少すること、そして確率の法則によって許容される最も速いスピードで減少することを意味しています。以前の手法には、彼らのスピードを遅らせる余分な因子（$\log(n)$ など）がありましたが、ザ・オプティマイザーはそれらを排除しています。

秘伝のソース：立方体と方向付け

彼らはどのようにしてそれを成し遂げたのでしょうか？彼らは、**ワン・インクルージョン・グラフ（One-Inclusion Graph）とサフィックス・アベレージング（Suffix Averaging）**という2つのアイデアを巧みに組み合わせて使用しました。

1. ワン・インクルージョン・グラフ（立方体のゲーム）
サンプルに含まれる本がラベル付けされる可能性のあるすべてのパターンを想像してください。もし $n$ 冊の本があれば、$2^n$ 通りのラベルの組み合わせが存在します。これらの組み合わせは、巨大な多次元立方体（「ブール立方体」）の角として可視化できます。

• 二つの角は、一冊の本のラベルだけが異なる場合に、エッジ（辺）で結ばれます。
• 「オラクル」（最善のルール）はこの立方体のどこかに存在しています。
• 目標は、角に立っているときに、どの方向に進めばオララーに近づけるかを判断することです。

著者らは、**方向付け（orientation）**と呼ばれるテクニックを使用しています。想像してみてください、あなたは立方体の角に立っています。どの方向へ進むべきかを決める必要があります。論文では、Lemma 2.1と呼ばれる新しい数学的ツールを導入しています。これは「クラス依存型のエッジ・アイソペリメトリック不等式」です。私たちの図書館の比喩で言えば、これは「正しい方向を見つけるためにチェックすべき経路の数は、あなたがオラクルからどれだけ離れているか、そして図書館がいかに複雑であるかに依存する」というルールのようなものです。

彼らは、この巨大な立方体のすべてのエッジに対して方向を割り当てることができ、それによって、どこからスタートしたとしても、最善の答えに近づくために特定のステップ数以上を費やす必要がないことを証明しています。このステップは極めて重要です。なぜなら、これにより、混沌とした推測ゲームが決定論的な経路へと変わるからです。

2. サフィックス・アベレージング（委員会の投票）
この完璧な方向付けが得られたら、次にそれを実際の予測へと変える必要があります。彼らはサフィックス・アベレージングというトリックを使用します。
あなたは専門家チームを作っていると考えてください。一人の専門家に意見を求めるだけではありません。代わりに、データの量がわずかに異なる、一連の専門家に意見を求めます。

• 専門家1は、最初の $k$ 冊の本を見てきました。
• 専門家2は、最初の $k+1$ 冊の本を見てきました。
• ...
• 専門家 $m$ は、最初の $2k-1$ 冊の本を見てきました。

最終的な予測は、これらすべての専門家の意見の平均です。これは強力です。なぜなら、ランダム性を平滑化してくれるからです。もし一人の専門家がノイズの多い本によって運が悪かったとしても、他の専門家がそれを補います。論文は、この平均化プロセスが、完璧な方向付けと組み合わさることで、データにノイズがあってもエラー率を低く保つことを証明しています。

3. 仕上げ：閾値処理（スレッショルディング）
平均化された結果は、-1 から 1 の間の数値（「スコア」）です。最終的な「猫」か「犬」かの答えを得るために、彼らは**閾値（しきいち）**を使用します。彼らは、別の検証用書籍セットを使用して、いくつかの異なるカットオフポイントをテストし、最もうまく機能するものを選びます。このステップにより、最終的な結果が、曖昧な確率ではなく、単純で決定論的なルール（バイナリ分類器）になることが保証されます。

なぜこれが重要なのか

この論文の前では、もし最速の学習率を求めたければ、「完璧なデータに対してうまく機能する方法」と「乱れたデータに対してうまく機能する方法」のどちらかを選ばなければなりませんでした。両方の良いとこ取りをするには、ペナルティを支払う必要があったのです。

この論文は、あなたが両方の良いとこ取りができることを示しています。彼らは以下の特性を持つ学習器を構築しました：

1. ノイズのレベルを知る必要がない： データがどれほど乱れているか（$L^*$）や、どの程度の信頼度を求めるか（$\delta$）を知らなくても動作します。
2. 最適である： Devroye、Györfi、Lugosi といった先行研究によって確立された理論的な下限（学習の速度制限）に一致しています。
3. 決定論的である： 運に左右されません。同じデータに対して実行すれば、常に同じ答えを出します。

著者らは、アグノスティック（未知のノイズがある）設定において、最適（オプティマル）な結果を得るために「ポリログ（polylogarithmic）」因子（それらの余計な減速要因）が必要であるという考えを明確に否定しました。彼らは、それらの因子は不要であることを証明しています。また、単純な多数決のような従来の手法は、完璧なデータに対してはうまく機能しますが、ノイズが導入されると最適な速度を維持できないことも示しています。

要約すると、この論文は機械学習理論の歴史における長い一章を締めくくるものです。それは、現実の世界（データが決して完璧ではない世界）におけるバイナリ分類のための「完璧な」アルゴリズムを提供しています。それはまるで、道にどれほど穴が開いていても、最小のステップ数で宝物に到達することを保証する地図を見つけたようなものです。著者たちは、それが可能であると示唆しただけでなく、実際にその地図を作り上げ、それが機能することを証明したのです。