理論計算機科学教科書

付録G: AI/ML と理論計算機科学の接続

本付録は、機械学習（ML）を「理論計算機科学（TCS）の言葉」で位置づけ直すための概説です。目的は、学習の現象を断定することではなく、仮定（分布・仮説クラス・計算資源）を明示した上で議論できるようにすることです。

G.1 3つの軸（学習の理論を分解する）

MLを理論的に扱うとき、少なくとも次の3軸に分解すると見通しが良くなります。

  1. 表現力（モデルクラス）: どのような関数/規則を表現できるか（仮説クラス）。
  2. 統計的困難さ（標本数）: どれだけのデータがあれば汎化できるか（サンプル複雑性）。
  3. 計算的困難さ（計算量）: 学習/推論を計算可能・現実的な時間で実行できるか（計算複雑性）。

このうち 2 は計算資源を無視した「情報理論的」な議論、3 は計算資源を組み込んだ「計算量的」な議論として整理できます。

G.2 PAC学習（概説）

PAC（Probably Approximately Correct）学習は、学習を「確率つきの近似」として定式化します。代表的には以下の要素で構成されます。

  • 入力空間 X、ラベル空間 Y（例: {0,1}）
  • データ生成分布 D（X×Y 上の分布）
  • 仮説クラス H（候補となる予測規則の集合）
  • 誤り率（一般化誤差）: 分布 D に関する期待値として定義

典型的な主張は「所与の H と精度 ε・信頼度 δ に対して、十分な標本数 m を取れば、経験誤差最小化（ERM）などで得られる仮説の一般化誤差が高確率で小さくなる」という形です。

ここで重要なのは、PACは D を仮定する（固定の分布から独立同分布にサンプルされる等）点と、H を仮定する点です。仮定が変わると結論（必要標本数、成立する境界）も変化します。

G.3 VC次元とサンプル複雑性（概説）

VC次元は、仮説クラス H の「識別能力（複雑さ）」を測る代表的な指標です。直観的には「どれくらい多様なラベル付けを実現できるか」を表します。

  • VC次元が小さい: 少ない標本でも汎化しやすい傾向
  • VC次元が大きい: 過学習リスクが増え、より多い標本が必要になりやすい傾向

代表的な境界（概説）では、VC次元 d の仮説クラスに対して、精度 ε・信頼度 δ を達成するために必要な標本数 m が d と 1/ε、log(1/δ) の関数として上界付けされます（実現可能/非実現可能などの前提で形は変わります）。

G.4 学習の計算量（「学べる」と「効率よく学べる」は別）

サンプル複雑性で「学べる」ことが示せても、実際に学習を実行できるとは限りません。ここで第5章（計算複雑性理論）の観点が効きます。

  • 情報理論的に学習可能: 十分なデータがあれば一般化できる（計算時間は問わない）。
  • 計算量的に効率よく学習可能: 多項式時間など、現実的な計算資源で学習できる。

この差は、例えば「最適な仮説（経験誤差最小）を探索する問題」が計算量的に困難な場合に顕在化します。学習アルゴリズムの設計は、ここで近似・緩和・ヒューリスティック・確率的手法（第6章）と接続します。

G.5 最適化と計算量（概説）

多くの学習は「損失関数の最小化」として定式化されますが、損失関数の形（凸/非凸）、制約（離散/連続）、データの性質により難易度は大きく変わります。

  • 凸最適化: 一定の仮定の下で大域最適や収束保証が議論しやすい。
  • 非凸最適化: 一般には大域最適を保証しにくく、最悪計算量と実務上の経験則が乖離しやすい。

「最悪ケースの計算量」と「実データ上の振る舞い」を区別し、仮定を明示して議論することが重要です。

G.6 情報理論との接続（概説）

学習では、確率分布や不確実性が本質的に関与します。第10章（情報理論）で扱う概念は、以下の観点で再登場します。

  • 交差エントロピー / KLダイバージェンス: 目的関数（損失）として現れることが多い
  • 相互情報量: 「入力がどれだけ出力を説明するか」という尺度として、表現学習や一般化解析の道具になる

ただし、これらの概念を用いた一般化の議論は前提条件に敏感です（独立性、分布仮定、ノイズモデル等）。

G.7 本書内の導線と参考文献

本書内の導線

参考文献（代表例）

以下は代表的な入門文献です（詳細は各版の目次・前提を確認してください）。

  • Shalev-Shwartz, Ben-David, Understanding Machine Learning: From Theory to Algorithms.
  • Vapnik, The Nature of Statistical Learning Theory.
  • Kearns, Vazirani, An Introduction to Computational Learning Theory.
Edit this page on GitHub