| はじめに 1 |
| 1.1 コンピュータが学習すること 2 |
| 1.2 歴史的背景 5 |
| 1.3 基本的定義 6 |
| 1.3.1 学習の用語 7 |
| 1.3.2 形式言語 7 |
| 1.3.3 表現クラスと帰納的可算クラス 10 |
| 1.4 計算論的学習の情報源 12 |
| 1.5 本書の構成 14 |
| 2 極限における学習 17 |
| 2.1 極限における学習モデル 17 |
| 2.2 枚挙による学習 19 |
| 2.3 有限オートマトンの学習 21 |
| 2.3.1 接頭辞木オートマトン 22 |
| 2.3.2 代表例集合と有限オートマトンの探索空間 23 |
| 2.3.3 DFAの極限学習アルゴリズム 26 |
| 2.3.4 状態の統合順序について 30 |
| 2.4 正例からの学習 34 |
| 2.5 パターン言語の正例からの学習 35 |
| 2.5.1 パターン言語とMINL戦略 35 |
| 2.5.2 パターン言語のいくつかの性質 38 |
| 2.5.3 minlアルゴリズムの正当性 40 |
| 2.5.4 MINL戦略がPATを極限学習すること 42 |
| 2.6 MINL戦略による正例からの学習 43 |
| 2.7 ゼロリバーシブル言語の正例からの学習 45 |
| 2.7.1 MINL(S,RεV0)を出力すること 50 |
| 2.7.2 RεV0が特徴例集合をもつこと 51 |
| 2.8 1変数パターン言語の正例からの学習 52 |
| 2.8.1 無矛盾なパターンを求める際の問題点 54 |
| 2.8.2 パターンオートマトンの交わり 54 |
| 2.8.3 語wを生成するパターンの分割 55 |
| 2.8.4 minl手続き 58 |
| 2.8.5 minl手続きの計算時間の解析 61 |
| 2.9 正例からの学習の特徴付け 61 |
| 2.9.1 有限証拠集合 61 |
| 2.9.2 枚挙に基づくMINL戦略 63 |
| 2.9.3 条件EC1の十分性 64 |
| 2.9.4 条件EC1の必要性 65 |
| 2.10 正例から学習可能であるための十分条件 67 |
| 2.10.1 条件C4を満たすならば条件C3も満たすこと 68 |
| 2.10.2 条件C3を満たすならば条件C2も満たすこと 68 |
| 2.10.3 条件C2を満たすならば条件EC1も満たすこと 69 |
| 2.10.4 各条件に関する補足 70 |
| 2.11 文脈自由文法の学習 70 |
| 2.11.1 木と導出木 71 |
| 2.11.2 木オートマトン 75 |
| 2.11.3 ゼロリバーシブル木オートマトン 78 |
| 2.11.4 ゼロリバーシブル文脈自由文法 79 |
| 2.11.5 正の構造例からの学習 80 |
| 2.11.6 基礎木オートマトンの構成 80 |
| 2.11.7 ゼロリバーシブル木オートマトンの学習 82 |
| 2.12 さらなる研究話題(文献ノート) 85 |
| 3 確率的近似学習 87 |
| 3.1 確率的近似学習(PAC)モデル 88 |
| 3.2 PAC学習モデルにおける基本的手法 90 |
| 3.3 ブール式の学習 94 |
| 3.3.1 ブール式 94 |
| 3.3.2 さまざまなブール式の学習 95 |
| 3.4 決定木の学習 98 |
| 3.4.1 決定木 98 |
| 3.4.2 矛盾しない決定木を求める学習アルゴリズム 99 |
| 3.4.3 決定木のPAC学習可能性 102 |
| 3.5 VC次元 105 |
| 3.5.1 VC次元と学習可能性 105 |
| 3.5.2 ニューラルネットワークの学習可能性への応用 108 |
| 3.6 PAC学習可能性に関する主な結果 110 |
| 3.7 ノイズを含んだ例からの学習 112 |
| 3.7.1 分類ノイズモデル 112 |
| 3.7.2 分類ノイズモデルにおける基本的手法 113 |
| 3.7.3 決定木の学習への応用 117 |
| 3.8 弱PAC学習とブースティング 120 |
| 3.8.1 弱PAC学習 121 |
| 3.8.2 ブースティング 122 |
| 3.9 さらなる研究話題(文献ノート) 128 |
| 4 質問を用いた学習 131 |
| 4.1 質問学習モデル 131 |
| 4.2 ブール関数の学習 132 |
| 4.2.1 ブール関数に対する所属質問と等価性質問 132 |
| 4.2.2 単項式の学習 134 |
| 4.2.3 K項式の学習 136 |
| 4.3 オートマトンの学習 147 |
| 4.3.1 MAT学習における2つの基本戦略 148 |
| 4.4 他の学習モデル-制限と拡張 155 |
| 4.5 さらなる研究話題(文献ノート) 158 |
| 5 応用 161 |
| 5.1 テキストデータベースからの知識獲得 162 |
| 5.1.1 文字列上の属性を扱う決定木と文書データの分類 162 |
| 5.1.2 文書分類木を学習するノイズに強いアルゴリズム 164 |
| 5.1.3 実験と考察 166 |
| 5.1.4 キーワード自動抽出としての文書分類木の学習 170 |
| 5.1.5 百人一首での実験 171 |
| 5.1.6 課題 172 |
| 5.2 遺伝子解析への応用 173 |
| 5.2.1 確率文法の学習の応用 173 |
| 5.2.2 確率文法によるモデル化の手法 176 |
| 5.2.3 確率文脈自由文法によるRNA配列のモデル化と実験 182 |
| 5.2.4 局所的言語の学習とその応用 187 |
| 5.3 さらなる研究話題(文献ノート) 199 |
| 参考文献 201 |
| 索引 210 |
