概要

確率を武器にする乱択アルゴリズムの理論的基礎を習得する

想定読者

アルゴリズム理論と数学的素養をすでに持つ大学院生・研究者、および高度な確率的手法を実装に取り込みたい上級エンジニア

こんな人には向いていない

• アルゴリズム入門レベルの読者。確率論・線形代数・グラフ理論の基礎が前提となるため、これらを未修得の段階では読み進めるのが困難
• 乱択アルゴリズムを既に研究・実装している研究者。本書は入門から中級の理論整理を目的としており、最先端論文の網羅は意図していない
• コーディング課題やコンテスト対策が主目的の読者。実装よりも数学的解析と設計原理の掘り下げに重点が置かれている

読了後にできるようになること

• 乱択化の3類型(Las Vegas / Monte Carlo / 期待値解析)の違いと使い分けを説明できる
• クイックソートや凸包構成における平均化効果を確率解析で定量化できる
• 標本乱択の理論(ε標本・ε網)を用いて最小全域木の線形時間アルゴリズムを導出できる
• くじ引き型アルゴリズム(素数性判定・関数同一性検証)の成功確率増幅の仕組みを理解できる
• マルコフ連鎖を設計して計数問題の近似アルゴリズムを構成できる
• 脱乱択化(条件付き確率法・確率空間の縮小)によって乱択アルゴリズムを決定性に変換できる

本書のキー概念(章解説)

• 第 1 章 導入 — 乱択化の動機と分類、確率的解析の準備を整理する章。後続章の参照起点になるので最初に精読する
• 第 2 章 平均化効果を利用する乱択アルゴリズム — クイックソートと低次元線形計画法を題材に、期待値解析の基本パターンを習得できる
• 第 3 章 標本乱択を利用するアルゴリズム — ε標本とε網の理論が最小全域木の線形時間アルゴリズムに接続される。本書の理論的核心
• 第 4 章 くじ引き型のアルゴリズム — 素数性判定と関数同一性検証を具体例に、成功確率増幅の設計パターンを学べる
• 第 5 章 その他の種類の乱択アルゴリズム — 制約充足と乱歩を扱う。他章と独立して参照可能
• 第 6 章 マルコフ連鎖を用いた標本乱択 — MCMC の理論的基盤。定常分布への収束速度の解析手法は機械学習との接点でも有用
• 第 7 章 脱乱択化 — 条件付き確率の方法と確率空間縮小。乱択アルゴリズムを決定性化する技法を体系的に習得できる

ハイライト

• アルゴリズムの振舞いを乱数に依存させる乱択アルゴリズムが流用されており、単にアルゴリズムといえば、今日では乱択アルゴリズムを含んでいると考えるのが普通である(乱択手法がすでにアルゴリズムの標準的な道具立てである、という現状認識を端的に示す冒頭の動機づけ)
• 少数の乱択アルゴリズムを例として基本的な考え方のパターンを掘り下げる方針を採った(網羅より深堀りを優先した編集方針を表明しており、読者が何を期待すべきかを絞り込む)

編集メモ

Qiita 言及記事 0 件 / 楽天ランキング履歴なし。2008年刊の大学院向け専門書であり、一般的な実務エンジニア向けの言及は少ない。アルゴリズム・サイエンスシリーズ第4巻という位置付けから、シリーズ読者には有用な選択肢

読む前に押さえておきたいこと

• 確率論の基礎(確率変数・期待値・マルコフ不等式・チェルノフ限界)
• グラフ理論と計算量理論(O記法、多項式時間と指数時間の区別)
• 線形計画法の基本概念(実行可能解・最適解・双対性)
• アルゴリズム設計の基礎(分割統治・動的計画法・貪欲法)を一通り経験していること

学習のコツ

• 1章で定義する3類型(Las Vegas / Monte Carlo / 期待値解析)の違いを整理してから各章に進むと、章ごとの手法の位置付けが明確になる
• 2章(平均化効果)と3章(標本乱択)は本書の理論的核心。数式展開を省略せずに手を動かして追うことで、後続の応用章の吸収率が上がる
• 6章(マルコフ連鎖)はMCMCの理論的下地として機械学習の文脈でも参照価値がある。独立して読む場合は1章の確率的解析の準備を先に通しておく
• 7章(脱乱択化)は単独では難解に見えるが、2〜4章の例題と対応させて読むと、乱択アルゴリズムの設計から決定性化までの流れを一貫して把握できる