著者|周志華

編集者 | Cong Mo

機械学習の専門家であり、南京大学人工知能学院長でもある周志華教授が執筆した本稿は、機械学習理論における重要な問題の探求プロセスを、一般的な物語を用いて詳述するものです。読者は、機械学習における理論的探求の困難さと挑戦性を理解し、アルゴリズム設計における理論的進歩の重要性を理解することができるでしょう。

1. 発生源の追跡

1989 年、ハーバード大学のレスリー・ヴァリアント (計算学習理論の創始者であり、2010 年の ACM チューリング賞受賞者) と彼の学生マイケル・カーンズ (後にベル研究所の人工知能研究部門のディレクターとなる) は、「弱い学習可能性は強い学習可能性と同等か?」という未解決の問題を提起しました。

質問は大まかに言うと次のようになります。機械学習タスクに「ランダムな推測」よりもわずかに優れた「弱い学習アルゴリズム」がある場合、そのタスクには必ず任意に高い精度（問題の理論上の上限に任意に近い）を備えた「強い学習アルゴリズム」があるのでしょうか。

直感的には、この質問への答えはおそらく「いいえ」です。なぜなら、現実世界のタスクでは、ランダムな推測よりもわずかに優れたアルゴリズム（たとえば、精度 51% など）は簡単に見つけられますが、非常に高い精度のアルゴリズム（たとえば、精度 95% など）を見つけるのは難しいからです。

驚くべきことに、1990年にMITのロバート・シャピレ氏が権威ある学術誌『機械学習』に論文を発表し、この問題の答えが「YES」であることを証明しました。さらに驚くべきことに、彼の証明は建設的でした。

言い換えれば、シャーバーは、直接実行することで弱い学習アルゴリズムを強い学習アルゴリズムにアップグレードできるプロセスを提供しました。このプロセスの鍵となるのは、一連の「ベース学習者」を考慮し、「新規学習者」が「先行学習者」がエラーを起こしやすい部分に集中できるようにし、これらのベース学習者を組み合わせることです。

残念ながら、このプロセスは理論上のものであり、実際に実行できる実用的なアルゴリズムではありません。問題を解決する前に、その最適な解決策がどれほど優れているかを知る必要があるなど、実際には事前に入手することが難しい情報を知る必要があるためです。

その後、シャパーはニュージャージー州のベル研究所に移り、そこでカリフォルニア大学サンタクルーズ校卒業生のヨアブ・フロイントと出会いました。偶然にも、フロイントは以前、複数の学習器の組み合わせを研究していました。二人は共同研究を始めました。そしてついに1995年、彼らはヨーロッパ計算学習理論会議（注：この会議は後にCOLTに統合されました）で実用的なアルゴリズムを発表し、その完全版は1997年にJournal of Computer and System Sciences誌に掲載されました。これが有名なAdaBoostです。シャパーとフロイントはこの研究により、2003年のゲーデル賞と2004年のACMパリ・カネラキス理論・実践賞を受賞しました。

AdaBoostのアルゴリズムは驚くほどシンプルです。Schaber氏自身の言葉によれば、「わずか10行程度のコード」で済みます。しかし、非常に効果的で、改良を加えれば幅広いタスクに適用できます。例えば、「初のリアルタイム顔検出装置」として高く評価され、2011年のロンゲ＝ヒギンズ賞を受賞したViola-Jones検出器は、AdaBoostをベースとしています。AdaBoostは後に、機械学習における「アンサンブル学習」の代表的な手法として主流となっているBoostingと呼ばれる大規模なアルゴリズムファミリーを生み出しました。今日の「ディープラーニング時代」においても、Boostingは重要な役割を果たし続けています。例えば、多くのデータ分析コンテストでディープニューラルネットワークに勝利を収めているXGBoostは、Boostingファミリーに属するGradientBoostアルゴリズムの効率的な実装です。

今日の話は、ブースティング学習理論の探求についてです。

2. 異常

機械学習コミュニティでは、単一のアルゴリズムが普遍的に適用可能ではないことは古くから知られています（注：有名な「ノー・フリーランチ」定理については、周志華著『機械学習』（清華大学出版、2016年、第1.4節を参照）。したがって、アルゴリズムを実験的にテストするだけでなく、理論的な分析を行うことも不可欠です。明確な理論的説明があって初めて、特定の機械学習アルゴリズムがいつ、なぜ機能するのかを理解することができ、単なる運任せに頼るのではなく、理解することができます。

1997年、シャベルとフロイントはAdaBoostの最初の理論的分析を行いました。彼らは、AdaBoostの学習誤差が学習エポック数とともに指数関数的に減少することを証明しました。これは、アルゴリズムが急速に収束することを意味します。最も重要な汎化性能、つまり新しい未知のデータを処理する際のアルゴリズムの性能に関して、彼らはAdaBoostの汎化誤差が…という結論に達しました。

トレーニングエラー

（

(その他の比較的重要度の低い用語は省略されています。) ここで、m はトレーニング サンプルの数、T はトレーニング エポックの数です。

これは、大まかに言えば、ベース学習器の複雑さとして理解できます。AdaBoostは各学習エポックでベース学習器を追加するため、…

これは、最終的なアンサンブル学習器の複雑さとほぼ同等です。したがって、この理論的な結果は、トレーニングサンプルが多いほど良く、モデルの複雑さが低いほど良いことを示しています。

大量のトレーニングサンプルが求められるのは理解しやすいでしょう。では、なぜモデルの複雑度が低い方が望ましいのでしょうか？これは、機械学習における「過学習」という現象によるものです。簡単に言えば、モデルがトレーニングデータから「あまりにも良く」学習すると、実際には誤りを犯す可能性があります。例えば、図2で「葉」について学習する際に、学習者が鋸歯がないということは葉ではないと誤って認識した場合、これは過学習です。過学習の重要な原因の一つは、モデルが複雑すぎるために「過学習」に陥り、サンプル全体の「共通点」ではなく、本来学習すべきではないトレーニングサンプルの「特徴」を獲得してしまうことだと一般的に考えられています。

明らかに、Chabel と Freund の 1997 年の研究の理論的意味は機械学習の分野における常識と一致しており、したがって容易に受け入れられます。

しかし、AdaBoost は実際には特異な現象を示します。それは、過剰適合を回避しているように見えることです。

図3に示すように、トレーニング誤差が0に達した後もトレーニングを継続すると、モデルの複雑さは増加しますが、一般化誤差は減少し続けます。

科学的発見における基本的な方法論は、複数の理論的仮説が実験観察と一致する場合、最も単純な仮説を選択するというものです。これは「オッカムの剃刀」として知られています。この原則は、多くの分野の歴史において重要な役割を果たしてきました。しかし、AdaBoostの挙動を詳しく調べると、それがいかに異なるかが明らかになります。

図3に示すように、10回目と1000回目の学習で形成された仮説（アンサンブル学習器）は「実験観測」（学習データ）と一致しており、前者は10個の基本学習器のみを含み、後者は1000個の基本学習器を含んでいます。オッカムの剃刀に従えば、前者を選択すべきであることは明らかですが、実際には後者の方が優れています。

つまり、AdaBoost の動作は機械学習の分野の常識に反するだけでなく、より広い視点から見ると、基本的な科学的原理にさえ違反しているのです。

したがって、AdaBoostの特異性の背後にある理由を理解することは、私たちの好奇心を満たすだけでなく、機械学習におけるこれまで知られていなかった秘密を明らかにし、アルゴリズム設計の新たな扉を開く可能性を秘めています。「なぜAdaBoostは過学習を起こさないのか？」これは、ブースティングにおける最も重要かつ興味深い基礎理論的問いとして、多くの著名な学者の注目を集めています。

3. 昆虫の目覚め

シャーバーとフロイントは1997年の理論の問題点をすぐに認識しました。1998年、彼らは後にバークレーの著名なシモンズ理論計算研究所を率いるピーター・バートレットとウィー・サン・リーと共同で、「マージン」に基づく新しい理論を発表しました。

「マージン」は機械学習において重要な概念です。図4に示すように、異なるクラスのサンプルを分離するために分離超平面を用いる場合、サンプル点の超平面からの「距離」は、そのサンプル点の超平面に対する「マージン」となります。この超平面に対するすべてのサンプル点の「最小マージン」を考慮して、「超平面のマージン」を定義します。機械学習でよく知られているサポートベクターマシン（SVM）は、最適化手法を用いてマージンが最大となる分離超平面を見つけます。言い換えれば、超平面に対するサンプル点の「最小マージン」を最大化しようとします。

Schaberらによる新しい理論では、AdaBoostの汎化誤差境界にマージンに関する閾値項θが含まれており、θは分母に現れます。これは、マージンが大きいほど、汎化誤差が小さくなる可能性が高いことを意味します。この理論は、AdaBoostが過学習を起こさない理由を巧みに説明しています。これは、トレーニング誤差が0に達したとしても、マージンがさらに増加できるためです。図4に示すように、超平面Bは2つのトレーニングサンプルポイントのクラスを完全に分離しており、そのトレーニング誤差は0です。トレーニングを続けると、トレーニング誤差が依然として0である超平面Aが見つかる可能性がありますが、AのマージンはBよりも大きいため、汎化誤差をさらに低減できます。

この理論は1998年に発表されました。同年、ドルトムント大学のThorsten Joachims氏は、ヨーロッパ機械学習会議において、サポートベクターマシン（SVM）がテキスト分類タスクにおいて優れた性能を示したことを報告し、機械学習における「統計学習の時代」の到来を正式に告げました。「マージン」はSVMの中核概念です。AdaBoostの挙動をマージンの観点から説明することは、機械学習における2つの主要な学派、「アンサンブル学習」と「統計学習」を暗黙のうちに結びつけることになります。

興味深いことに、統計学習の創始者であり、サポートベクターマシンの発明者であるウラジミール・N・ヴァプニクは、1990年（ソ連崩壊の前年）にソ連を離れ、ニュージャージー州のベル研究所で働きました。シャベルとフロイントはヴァプニクと共同研究していた当時は同僚であり、ヴァプニクの影響を受けた可能性があります。

4. アナと雪の女王

1998年の論文の末尾で、シャベルらはレオ・ブレイマンとの「胸を打つ」やり取りがあったと述べています。学術的なコミュニケーションを表現するのに、この言葉が使われることは稀です。この胸を打つような感情を彼らにもたらしたのは、カリフォルニア大学バークレー校のブレイマン教授でした。彼は「20世紀最高の統計学者」の一人と称されています。彼は統計学の巨匠であるだけでなく、機械学習における有名なアンサンブル学習法であるバギングとランダムフォレストの発明者でもあります。

1999年、ブレイマンは独立執筆した論文で新たな理論を提唱しました。この理論もAdaBoostを「マージン」に基づいて特徴づけていますが、1998年のシャベルらの理論とは異なり、ブレイマンの理論は「最小マージン」に焦点を当てています。このマージン物理量に基づいて、ブレイマンはシャベルらの理論よりも「厳密な」汎化誤差限界を導き出し、ブースティングマージン理論における新たなマイルストーンとなりました。

学習理論において、「より厳しい境界」は通常、「より基本的な物理量」を意味します。前のセクションで述べたように、「最小マージン」は分割超平面に最も近いサンプル点に依存し、有名なサポートベクターマシン（SVM）は「最小マージン」を最大化する分割超平面を見つけようとします。したがって、Brehmanの理論は「最小マージン」がAdaBoostの鍵でもあることを明らかにしており、これは非常に啓発的です。

ここまではすべて順調です。ブースティング間隔理論の鍵は「最小間隔」にあることを認識する必要があります。

しかし、ブレマンは優れた理論学者であっただけでなく、機械学習アルゴリズムの発明にも情熱を注いでいました。「最小マージン」が鍵であることが証明され、AdaBoostと最小マージンの関係が複雑な理論的分析によって発見された（つまり、AdaBoostは最小マージンを「直接」最適化するわけではない）のであれば、最小マージンを直接最適化する新しいブースティングアルゴリズムを発明するのは当然のことでしょう。理論的には、このアルゴリズムはAdaBoostよりも強力になるはずです。

そこで、1999年にBrehmanは新しいアルゴリズムArc-gvを発明しました。このアルゴリズムは最適な最小マージンを実現できることは理論的に証明されています。さらに、Brehmanによる広範な実験では、このアルゴリズムに対応する「最小マージン」は常にAdaBoostのそれよりも大きいことが検証されました。しかし、実験ではArc-gvの汎化誤差がAdaBoostよりも大きいことが示されています。

これは奇妙です。ブースティングマージン理論の鍵は「最小マージン」であることが証明されており、Arc-GVの「最小マージン」は理論的にも実験的にもAdaBoostよりも優れています。では、Arc-GVの汎化性能はもっと優れているはずではないでしょうか？なぜAdaBoostより劣っているのでしょうか？

証明は正しい。これは、「間隔」を基礎として用いることが間違っていることを意味する。したがって、ブレマンの研究はブースティング間隔理論の「死刑宣告」を宣告するに等しい。

こうしてブースティングマージン理論は「凍結時代」に入りました。研究者たちは他の理論体系に目を向けました。その中で最も重要なのは、スタンフォード大学の三教授であり、著名な著書『統計学習の要素』の著者でもあるジェローム・フリードマン、トレバー・ハスティー、ロバート・ティブシラニが提唱した「統計的視点」理論です。この学派にも論争があり、特にAdaBoostが過学習を起こさない理由を明確に説明できないことが問題となっています。しかしながら、少なくともこの理論は「生きていて」、改善の余地があると考えられています。一方、マージン理論は、その洗練された幾何学的直感にもかかわらず、本質的に「死んでいる」のです。

5.寿命を延ばす

7年後、2006年の国際機械学習会議（ICML）で、プリンストン大学のチャールズ・シャッパー教授とイェール大学のレヴ・レイジン学生が「優秀論文賞」を受賞しました。受賞論文の成果はただ一つ、ブレマンの1999年の実験を再現したことでした。

ブースティングマージン理論は、マージン自体に加えて、トレーニングサンプル数とモデルの複雑さが不可避的に関係していることが知られています。マージンが汎化誤差に与える影響を議論するには、トレーニングサンプル数とモデルの複雑さを「固定」する必要があります。前者はトレーニングサンプル数を指定するだけで簡単ですが、後者は特別な処理が必要です。

決定木モデルの複雑さは、一般的に葉ノードの数によって決まると考えられています。そのため、Brehmanは1999年の実験で、同じ葉ノード数の決定木を使用しました。ReinとSchaberはBrehmanの実験を繰り返し、AdaBoost決定木はArc-gv決定木と同じ葉ノード数であるにもかかわらず、層数が多いことを発見しました。そのため、ReinとSchaberは、これらの決定木の複雑さが異なる可能性があると推測しました。

この発見は容易ではありませんでした。なぜなら、これらの決定木間の高さの差は有意ではなかったからです。例えば、それぞれ300本の決定木を使用した場合、AdaBoostの決定木の平均高さは約10.5で、Arc-gvの決定木よりわずか1レベル程度高かったのです。膨大な実験データからこのような小さな差を観察するには、非常に鋭い観察力が必要です。

ReinとSchaberは、2つのリーフノードのみを持つ単層決定木（「決定木」とも呼ばれる）をベース学習器として用いて、実験を再実行した。彼らは、Arc-gvの最小マージンは常にAdaBoostよりも大きかったものの、全体のサンプルサイズを考慮すると、AdaBoostのマージンがArc-gvよりもわずかに大きいことを発見した。例えば、図6はAdaBoostの曲線がより「右」に寄っていることを示している。これは、より多くのサンプルポイントでより大きなマージン値が得られることを意味する。したがって、ReinとSchaberは、「最小マージン」はブースティングマージン理論の鍵ではなく、重要なのはマージン全体の分布であると主張した。彼らは「平均マージン」または「中央値マージン」が重要な物理量である可能性を推測したが、理論的な証明は示さなかった。

今日の平均的な読者はこの論文にかなり驚くかもしれません。この論文は新しい理論も、新しいアルゴリズムも、新しいアプリケーションも提案していないのに、この「3つのノー」の論文が ICML 優秀論文賞を受賞したのです。

この研究の重要性は、ブースティング理論の探究という全体的な文脈の中で検討されなければなりません。それは、少なくとも実験部分において「具体的に証明」されなかったブースティング間隔理論システムに対するブレイマンの致命的な打撃を示しています。

では、ラインとシャーバーの研究は「ブースティングギャップ理論を復活させた」と言えるだろうか？まだそうではない。ブレイマンの主な攻撃は理論的な結果に基づくものであり、実験は「検証」の役割しか果たしていなかったからだ。したがって、ブースティングギャップ理論が生き残るためには、「最小ギャップ」を超えるギャップ量に基づいて、ブレイマンの理論よりも厳密な一般化誤差限界を示す新たな理論が必要となる。

6. 研磨

2008年、北京大学の王立偉博士、馮聚富教授、そして学生の楊成氏、そして後に理化学研究所人工知能研究センター長となる杉山将氏は、著者と共同でCOLT会議で論文を発表しました。この論文では「均衡マージン」という概念が提示され、それに基づいてブレマンの一般化誤差よりも厳密な一般化誤差限界が証明されました。「均衡マージン」は最小マージンとは異なるため、多くの学者はブースティングの理論的課題は解決されたと考えました。

しかし、いくつか懸念事項があります。まず、「平衡区間」理論の証明に用いられた情報はシャベルとブレーマンのものと異なり、対応する結果を直接比較することはできない可能性があります。また、より重要なのは、「平衡区間」は数学的な定義に「無理やり押し込まれた」概念であり、その直感的な物理的意味を明確に説明できないことです。

ブースティング理論を研究し始めた当初の動機は、AdaBoostが過学習を起こさない理由を理解することで、新しい機械学習アルゴリズムの設計にインスピレーションを得ることでした。新しい理論の主要概念が直感的な物理的意味を欠いている場合、アルゴリズム設計のインスピレーションを得ることは困難です。そのため、私はこの問いについて考え続けました。

2008年、南開大学組合せ数学研究センターの学生だった高偉（現在は南京大学人工知能学院准教授）が博士号取得を目指して私に連絡を取り、私は彼をAdaBoost問題に引き入れました。当時、私はこの問題を1年で解決できると見積もっていました。しかし、困難は予想をはるかに超え、3年後、わずかな逸脱に基づいて学会論文を1本発表しただけでした。博士課程の学生にはどうしても論文というプレッシャーがあり、彼は「途方に暮れていた」と語っています。私も非常に不安でしたが、それでも気を引き締めなければなりませんでした。幸いにも、私は別の重要な理論的問題を抱えており、高偉はこの問題に関する非常に影響力のあるCOLT論文を発表していたので、プレッシャーはいくらか軽減され、研究を続けることができました。

幾度かの改良を経て、ついに2013年にArtificial Intelligence誌に新たな理論を発表しました。この理論に対応する一般化誤差の境界はChabelとBreimanの理論よりも厳密であり、「最小マージン」がブースティングマージン理論における重要な物理量ではないことが確認されました。興味深いことに、これまで重要なマージン物理量は「1つ」であると考えられていましたが、私たちの新しい理論では、「平均マージン」を最大化し、「マージン分散」を最小化する必要があることが明らかになりました。つまり、重要な物理量は1つではなく、2つあるということです。

なぜAdaBoostは過学習を回避できたのでしょうか？学習誤差がゼロに達した後も、なぜより優れた汎化性能を達成できたのでしょうか？新しい理論がその答えを示しています。学習中、AdaBoostはエポック数の増加に伴い、平均マージンだけでなくマージン分散も増加させるからです。しかし、これは同時に、AdaBoostが最終的に過学習する可能性もあることを意味します。ただし、それは平均マージンをこれ以上増加できず、マージン分散をこれ以上減少させることもできない、非常に遅い段階になってからになります。

よく知られているように、サポートベクターマシン（SVM）に代表される統計学習手法の多くは、「最小マージン」の最大化を目指します。この新しい理論は、「平均マージン」を最大化し、「マージン分散」を最小化できれば、より優れた学習器が得られることを明らかにしています。そこで、私の博士課程の学生である張騰（現在は華中科技大学コンピュータサイエンス学院の教員）をはじめとする研究者たちは、この分野の研究を始めました。2014年から5年間かけて、「最適マージン分布マシン（ODM）」と呼ばれる新しいアルゴリズム群を開発しました。このアルゴリズムには、2値分類、多クラス分類、クラスタリング、半教師あり学習などのアルゴリズムが含まれています。この新しい理論に着想を得たこれらのアルゴリズムは、本論文の焦点では​​ないため、ここでは詳しく説明しません。

7. 結論

2013年のこの研究は大きな話題を呼びました。例えば、2014年の国際人工知能会議（AAAI）では、人工知能協会会長でありカーネギーメロン大学機械学習学科長でもあるマヌエラ・ベローゾ教授が基調講演で、この研究を人工知能分野における重要な進歩として紹介し、「区間理論を復活させた」こと、「学習アルゴリズムの設計に新たな知見をもたらした」と述べました。

しかし、まだいくつか懸念事項があります。2013年の理論に対応する一般化誤差の境界は当時最も厳しかったものの、将来、他の区間物理量に基づいてより厳密な境界が得られ、「AdaBoostが過適合しなかった理由」に対する私たちの答えや、「区間分散を最小化しながら平均区間を最大化する」というアルゴリズムの指針が覆される可能性はあるでしょうか。

6年後の2019年後半のNeurIPSカンファレンスで、デンマークのオーフス大学のAllan Grønlund、Kasper G. Larsen、Lior Kamma、Alexander Mathiasenが、カリフォルニア大学バークレー校のJelani Nelsonと共同で論文を発表しました（図7を参照）。Nelsonは大統領メダルとスローン研究フェローシップの受賞者であり、LarsenはSTOCとFOCSで最優秀学生論文賞を2度受賞した理論計算機科学の注目株です。Kammaはイスラエルの計算機科学の主要センターであるワイツマン科学研究所を卒業しています。近年、機械学習の理論的問題に取り組む理論計算機科学者は重要なトレンドとなっています。この論文は最終的に、2013年に示された一般化誤差の上限がすでにほぼ可能な限り狭く、最大で対数係数の改善しか必要としないこと、そしてこの上限がすでに下限と一致しているため、これより良い結果は理論的に不可能であることを証明しました。

やっと気持ちが楽になりました。

8. 終わり

1998年にAdaBoost区間理論が登場してから、数々の議論と挫折を経て2013年に結論に至るまで、15年が経過しました。最終的な結論に至るまでにはさらに6年を要しました。物語の始まりである1989年から数えると、実に30年が経過しました。レオ・ブレマンをはじめとする物語の重要人物は亡くなり、当時の大学院生は教授になっています。最後に、本稿では、この物語における最も重要な3つの理論的成果を、説明なしに、追悼として列挙します（図8参照）。

図8. この論文で言及されている3つの主要な理論的結果。

参考文献

[1]周ZH.大マージン分布学習[C]// ANNPR 2014.(基調講演)

[2]張T、周ZH.最適マージン分配マシン[J]。IEEE Transactions on Knowledge and Data Engineering、DOI:10.1109/TKDE.2019.2897662。

[3]Grønlund A, Kamma L, Larsen KG, et al. ブースト分類器のマージンベース一般化下限[C]// NeurIPS 2019.

注: 理論的な内容に興味のある読者は、[1]で主要な文献を見つけることができます。ODMアルゴリズムに興味のある読者は[2]を参照してください。[3]は「結論」のセクションで説明されている最新の研究です。

著者について

周志華はCCFフェロー兼エグゼクティブ・ディレクターです。南京大学教授、コンピュータサイエンス学科長、人工知能学院学長、コンピュータソフトウェア新技術国家重点実験室執行副所長を務めています。ACM/AAAS/AAAI/IEEE/IAPRフェロー、欧州科学アカデミー外国人会員でもあります。主な研究分野は、人工知能、機械学習、データマイニングです。

https://www.toutiao.com/i6816265295964045832/