01 / 読書ガイド
読書ガイド
引用
Mitzenmacher, M., & Upfal, E. (2017). Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis (2nd ed.). Cambridge University Press.
章の要約
各章は一つの確率的手法を扱い、乱択アルゴリズムの解析や、ランダムな入力に対するアルゴリズムの解析を例にしてその手法を説明する。アスタリスクの付いた節は発展的な内容で、各章は演習問題で終わる。序文は、本書を中核部分（第1〜7章）と、ほぼ独立して読める章（第8〜17章）に分けて説明している。
第1章：事象と確率
多項式恒等式の検証、行列積の検証、ナイーブベイズ分類器、乱択最小カットアルゴリズムといった応用を通して初等的な確率論を復習する。確率の公理もこれらの例とあわせて導入される。
第2章：離散確率変数と期待値
確率変数と期待値（期待値の線形性とイェンセンの不等式を含む）、ベルヌーイ変数と二項変数、条件付き期待値、幾何分布を扱う。主な応用は、クーポン収集家問題とクイックソートの期待実行時間である。
第3章：モーメントと偏差
マルコフの不等式、分散とモーメント、チェビシェフの不等式、中央値と平均値の関係を導入し、中央値を求める乱択アルゴリズムで終わる。
第4章：チェルノフ限界とヘフディング限界
モーメント母関数からチェルノフ限界を導き、ポアソン試行の和に適用する。特殊な場合のより鋭い限界、集合のバランシング、ヘフディング限界も扱う。章末の発展的な節では、ハイパーキューブとバタフライ網での置換ルーティングを論じる。序文は、後の内容の大半にこの章が必要だと述べている。
第5章：玉、箱、ランダムグラフ
誕生日のパラドックスと玉と箱のモデルから始め、ポアソン分布とポアソン近似を展開する。応用はバケットソート、連鎖法ハッシュ、ブルームフィルタ、ランダムグラフにおけるハミルトン閉路である。章末にはプログラミングを伴う探究課題がある。
第6章：確率的方法
基本的な数え上げの議論、期待値の議論、サンプルと修正、第二モーメント法、条件付き期待値不等式によって存在を証明する。続いて条件付き期待値を用いた脱乱択と、ロヴァースの局所補題を扱い、一般の場合とアルゴリズム版は発展的な節で論じられる。
第7章：マルコフ連鎖とランダムウォーク
マルコフ連鎖を定義し、2-充足可能性と3-充足可能性の乱択アルゴリズムに用いる。さらに状態の分類、定常分布、無向グラフ上のランダムウォーク（s–t 連結性のアルゴリズムを含む）を扱い、パロンドのパラドックスで終わる。
第8〜9章：連続分布とポアソン過程；正規分布
第8章は連続確率変数、一様分布と指数分布、ポアソン過程、連続時間マルコフ過程、マルコフ型の待ち行列を扱う。第9章は正規分布、中心極限定理、多変量正規分布を扱い、正規乱数の生成、最尤推定、混合ガウス分布のための EM アルゴリズムへと応用する。
第10〜12章：エントロピー、ランダム性、情報；モンテカルロ法；マルコフ連鎖のカップリング
第10章はエントロピー関数、圧縮、シャノンの符号化定理を導入する。第11章はモンテカルロ法、DNF の数え上げ、近似サンプリングから近似的な数え上げへの移行、メトロポリスのアルゴリズムを含むマルコフ連鎖モンテカルロ法を扱う。第12章は全変動距離、混合時間、カップリングを展開し、パスカップリングと適正彩色のサンプリングも含む。序文は第11章と第12章を併せて教えることを勧めている。
第13章：マルチンゲール
マルチンゲールと停止時間を定義し、ワルドの等式を証明して、とりわけアズマ＝ヘフディングの不等式などの裾の不等式を導く。応用はパターンマッチング、玉と箱、彩色数である。
第14章：標本複雑度、VC 次元、ラデマッハー複雑度
第2版で新しく加わった章である。学習の設定と VC 次元を導入し、ε-ネット定理と ε-標本定理を扱って、PAC 学習、不可知学習、データマイニングを応用とし、最後にラデマッハー複雑度で終わる。
第15〜17章：対独立性と普遍ハッシュ関数；べき乗則と関連する分布；均衡配置とカッコウハッシュ
第15章は対独立性、脱乱択、普遍ハッシュ関数族、完全ハッシュ、データストリームにおけるヘビーヒッターを扱う。第16章（この版で新設）はべき乗則、ジップの法則、優先的選択、対数正規分布などの関連分布を扱う。第17章は2択のべき乗とカッコウハッシュを、削除、失敗、変種とともに扱う。
主要概念
第1〜3章：初等的な道具
- 期待値の線形性：和の期待値は期待値の和であり、変数が独立かどうかに依存しない。
- マルコフとチェビシェフの不等式：平均、次いで分散を用いた最初の裾の限界。
第4〜7章：中核となる手法
- チェルノフ限界：独立な試行の和に対する、モーメント母関数から得られる指数的に小さい裾の限界。
- 玉と箱：誕生日のパラドックス、ハッシュ、負荷の問題の背後にあるモデル。
- 確率的方法：ランダムな対象が正の確率で必要な性質を持つことを示して、対象の存在を示す方法。
- 定常分布：マルコフ連鎖の長期的な振る舞い。
第8〜14章：さらなる話題
- ポアソン過程：連続時間でのランダムな到着で、待ち行列の例の基礎になる。
- エントロピー：ランダム性の尺度で、圧縮や符号化と結びつく。
- カップリングと混合時間：マルコフ連鎖が定常分布に速く近づくことを示す道具。
- アズマ＝ヘフディングの不等式：マルチンゲールに対する集中不等式。
- VC 次元：集合族の容量の尺度で、標本数の限界の背後にある。
第15〜17章：ハッシュとデータ構造
- 普遍ハッシュ族：少ないランダム性で、衝突について証明可能な保証を持つハッシュ関数。
- 2択のべき乗：ランダムな2つの箱のうち空いているほうを選ぶと、最大負荷が大きく下がる。
批判的分析
長所
- 手法を軸にした構成。 序文は、個別の応用ではなく確率的な手法とパラダイムに重点を置くと述べており、各章が一つの手法を扱い、例は主にネットワーキングから取られている。
- 全体を通じた厳密さ。 わずかな例外を除いて主張には完全な証明が付く。序文は、モンテカルロ法のようなヒューリスティクスを適切に使うには基礎となる理論の確かな理解が必要だと述べて、この方針を擁護している。
- 明確な道しるべ。 最初の7章が中核とされ、発展的な節にはアスタリスクが付き、後の章はほぼ独立していると説明され、序文は別の章の順序も提案している。
- データ駆動の仕事に合わせた更新。 第2版は、大規模データと機械学習を受けて、正規分布、べき乗則、標本複雑度の章とカッコウハッシュの節を加えた。
- 演習と課題。 各章に演習があり、第5章と第11章にはプログラミングを伴う探究課題がある。
短所
- 演習は理論的なものが中心。 序文によれば演習の大半は理論的で、プログラミングはその一部にとどまるため、実装の練習は読者が自分で補う必要がある。
- ヒューリスティクスは設計上除外されている。 厳密に解析できる手法に限っているため、実用的なモンテカルロのヒューリスティクスは数学的な基礎を通してしか扱われない。
- 原典への案内が少ない。 著者らは原論文を引用しないことにし、代わりに「Further Reading」で背景となる書籍の短い一覧を示している。
- 序文が完全には更新されていない。 第1版の序文は今も本書が14章からなると述べているが、この版は17章である。
コースにおける位置づけ
アルゴリズムのコースの中で、本書は乱択と確率的解析を扱う専門的な教科書である。Introduction to Algorithms、Algorithm Design Manual、Algorithms Illuminated、Algorithms Unlocked は設計と解析を一般的に教えるのに対し、Mitzenmacher と Upfal は乱択アルゴリズムの背後にある確率論に集中する。そのため、一般的なアルゴリズムの授業の代わりではなく、その後に読む本である。
Vazirani の Approximation Algorithms と、Williamson と Shmoys の The Design of Approximation Algorithms は、隣接する大学院レベルの話題を扱う。そこで乱択の手法に出会う読者にとって、本書の第4章と第6章の裾の限界や確率的方法は有用な背景になるだろう。
本書の使い方
本書は、計算機科学と応用数学の上級学部生や大学院初年度の学生向けに書かれている。序文が前提とするのは、計算機科学者向けの離散数学の授業程度の確率論の基礎知識と、完全な証明を読む意欲である。
1学期の計画としては、第1〜7章を中核として読む。確率に慣れていれば第1〜3章は速く進めてよく、初回はアスタリスクの付いた節を飛ばす。後半の章は関心に応じて選ぶ。連続確率とエントロピーなら第8章と第10章、モンテカルロ法とカップリングなら第11章と第12章をまとめて、マルチンゲールなら第13章、脱乱択とハッシュなら第15章、学習理論なら第14章である。第4章は後の内容の大半の前提になる。
証明が要点なので、鉛筆を手に演習を解くこと。限界が実際にどう働くかを見るために、第5章と第11章の二つの探究課題にも取り組むとよい。ハッシュを復習するときは、第5.5節、第15.3節、第17章をあわせて読む。