目次
第1章 日本語と日本語入力システムの歩み
1.1 コンピュータで日本語を扱うということ
- 文字とは何か
- 文字の定義
- 文字と文字でない記号の境目
- 文字同士の境目
- コンピュータ上で文字を表現する
- 文字コードとは
1.2 日本語を入力するということ
- 日本語入力ソフトウェアの特異性
- 日本語入力の難しさ
- キー入力と文字の対応が複雑
1.3 日本語入力とかな漢字変換
- かな漢字変換エンジンとかな漢字変換器
1.4 日本語入力のはじまり
- 黎明期のさまざまな日本語入力方式
- 漢字直接入力方式
- ペンタッチ方式
- 手書き文字認識
1.5 かな漢字変換のはじまり
1.6 単文節変換から連文節変換へ
- n文節最長一致法
- 2文節最長一致法の展開例
- n文節最長一致法の問題点
- n文節最長一致法は何をしているのか？
- 単語間のつながりやすさを考慮したかな漢字変換
- 接続強度法の考え方
- 接続強度法の展開例
- 最適解を求めるかな漢字変換
- ビタビアルゴリズムを用いた最適解の探索
- パラメータをどうやって調節するのか
1.7 2強時代の到来～統計・機械学習ベースのアルゴリズムへ
- Microsoft IMEとATOK
- Microsoft IMEの統計・機械学習への対応
- ATOKの統計・機械学習への対応
1.8 Web検索各社のかな漢字変換エンジンへの参入
- Google日本語入力とは
- Baidu IMEとは
- なぜ検索エンジン各社がかな漢字変換エンジンを作るのか
1.9 携帯電話における日本語入力
- 予測入力の普及
- 予測入力とかな漢字変換の違い
- 予測入力の精度向上のための工夫
- 履歴から予測する
- 文脈から予測する
- 状況に応じて予測する
1.10 まとめ
- 【コラム】かな漢字変換と形態素解析
第2章 日本語入力システムの概観
2.1 ユーザ側から見た日本語入力
- 日本語入力には状態がある
- ひらがなを入力している状態
- IMEによって変換された漢字かな交じり文を修正している状態
- 状態を持つことでどのような問題が出てくるか
- ユーザの入力から学習する
- ユーザ側から見た日本語入力の特徴
2.2 システム側から見た日本語入力
- 日本語入力システムを分解する
- GUIツールキット
- 文字入力フレームワーク
- アプリケーション
- IME
- システム側から見た日本語入力の状態
- 日本語入力を実現するうえで大事なこと
- 特定の言語に依存しない
- プリエディット文字列と候補ウィンドウ
- 入力イベントの処理
2.3 ひらがなの入力方法
- ローマ字入力とQWERTY配列キーボード
- ローマ字からひらがなへの変換
- かな入力とJIS配列キーボード
- ローマ字入力とかな入力の比較
2.4 文字入力フレームワークのアーキテクチャ
- 文字入力フレームワークの役割
- 文字入力フレームワークの種類
- Windows
- Mac OS X
- Linux / Unix
- フレームワークによる設計の違い
- アプリケーションとIMEを同一プロセスで動作させるか
- 別プロセスにするメリット
- 別プロセスにするデメリット
- IME側でどうやってイベントを受け取るか
- プロセス間通信をどうするか
- プリエディット文字列をどのコンポーネントが描画するか
- プリエディット文字列の描画スタイル
- キャレット周辺文字列をどうやって参照させるか
- 【コラム】歴史的な文字入力のアーキテクチャ
2.5 かな漢字変換エンジンのユーザインタフェース
2.6 かな漢字変換エンジンのモジュール構成
2.7 かな漢字変換器の作り方
- かな漢字変換器を構成する3つの大事な要素
- データ構造
- デコーダ
- 学習アルゴリズム
- デコーダと学習アルゴリズムの関係
- なぜ機械学習を使うのか
- 機械学習の応用事例
2.8 まとめ
第3章 かな漢字変換エンジンに用いられるデータ構造
3.1 かな漢字変換とデータ構造
3.2 データ構造とは
- データ構造を分類して考える
- セットとマップ
- 動的と静的
- 抽象的と具体的
- 可変長と固定長
- 配列について
- 配列とベクター
- 配列の応用
- 配列と行列
3.3 かな漢字変換に用いるデータ構造
- 辞書を実現するデータ構造
- いろいろな情報を保持するデータ構造
- データ構造と効率的な辞書引きとの関係
- すべての部分文字列で辞書引きする方法
- 共通接頭辞検索を用いる方法
- その他の効率的な辞書引き手法
3.4 ハッシュテーブル
- ハッシュテーブルの基本
- ハッシュテーブルへの要素の挿入
- ハッシュテーブルでの要素の探索
- オープンアドレス法によるハッシュ値衝突の処理
- 線形探査法による空き領域の探索
- 実装時の注意点
- リハッシュ
- ハッシュ関数に求められる条件
- よく使われるハッシュ関数
- FNVハッシュ
- murmurハッシュ
- ハッシュテーブルの速度はいつ劣化するか
3.5 カッコウハッシュ
- カッコウハッシュでの要素の挿入
- カッコウハッシュでの要素の探索
- カッコウハッシュの考え方
3.6 トライ
- トライの要求を満たすためには
- テーブルによるトライの実装
3.7 ダブル配列
- ダブル配列の概要
- ダブル配列の例
- ダブル配列はトライの条件を満たすか
- ダブル配列での子ノードへの移動
- ダブル配列での共通接頭辞検索
- ダブル配列の構築
- 静的な構築
- 動的な構築
- 構築の高速化
3.8 LOUDS
- LOUDSの概要
- LBSによるツリーの表現
- LBSからツリーを復元する
- 簡潔ビットベクター
- rankの概要
- selectの概要
- rankの高速化
- selectの高速化
- LBSに対するツリー操作
- LBSの基礎知識
- 親ノードのIDの取得
- 子ノードのIDリストの取得
- LOUDSによるトライの実装例
- LOUDSの利点と欠点
3.9 その他データ構造のテクニック
- キーに対して任意の値を登録する
- トライを使う
- 簡潔データ構造を応用する
- 疎行列とその表現法
3.10 ライブラリの入手について
-
- Darts
- Darts-clone
- Tx
- Rx
- Ux
- marisa-trie
3.11 まとめ
第4章 かな漢字変換システムの実装
4.1 かな漢字変換をどうやって実現するか
- グラフの最短経路問題として解くメリットとデメリット
4.2 グラフの作成
- グラフとは
- グラフの最短経路問題
- 【コラム】鉄道の乗換案内
- かな漢字変換の問題をグラフとして表現する
- グラフを構築する
- 単語の辞書引き
- 共通接頭辞検索による辞書引きの高速化
- 辞書引きの結果を使ってグラフを作る
4.3 最短経路問題を解く
- ビタビアルゴリズムで最短経路を求める
- ビタビアルゴリズムの動作
- 【コラム】ビタビアルゴリズムの歴史
- 再帰で最短経路を求める
- 再帰という考え方
- メモ化を使って高速化する
- ビタビアルゴリズムと動的計画法
- 動的計画法の指すところ
- メモ化再帰と雪だるま方式の比較
- メモ化再帰の問題点
- 速度の比較
- 【コラム】再帰でのスタック溢れ対策
- ビタビアルゴリズムの適用範囲
- ビタビアルゴリズムが適用できるグラフとは
- 有向非循環グラフとトレリス
- ラティスと半環
4.4 単語間の線の距離を決める
- コストとスコア
- どう学習すればよいのか
- スコアの計算にどのような情報を使うか
- 構造化パーセプトロンの考え方
4.5 学習用のデータを作る
- 文章をどこから入手するか
- どのようにデータを処理するか
4.6 まとめ
第5章 統計・機械学習のアルゴリズムとその応用
5.1 機械学習とは
- なぜ機械に学習させるのか
5.2 二値分類
- 二値分類とは
- 二値分類で用いる学習用のデータ
- 入力データをベクトルに変換する
- bag of wordsによるデータの表現
- ベクトルをプログラム上で表現する
- 線形識別器について
- 線形識別器が働くメカニズム
- 線形分離について
- パーセプトロン
- サポートベクターマシン（SVM）
- SVMにおける学習の目標
- SVMの目的関数のプログラムとしての表現
- 式の意味を考える
- なぜ正解しても損失項が0より大きくなるのか
- 劣勾配法によるSVMの学習
- 最小値を探すことは極値を探すことと同じ
- 勾配と勾配法
- 学習率の設定
- 凸であるということ
- 劣勾配と劣勾配法
- SVMの（劣）勾配の求め方
- 【コラム】劣勾配とは
- 経験損失と期待損失
- 過学習と正則化
- 過学習の例
- 正則化とは
- FOBOSによるSVMの学習
- FOBOSの特徴
- FOBOSの正則化項の意図
- FOBOSによるL1正則化
- FOBOSの高速化
- 性能をどうやって評価するか
- 正解率
- 適合率
- 再現率
- F値
- 適合率 - 再現率曲線
- 収束の判定
5.3 構造学習とかな漢字変換
- 構造学習とは
- 構造学習問題の解き方
- かな漢字変換を構造学習としてとらえる
- 素性関数とは
- スコア計算の効率化と素数関数への制限
5.4 構造化SVM
- 構造化SVMのアイデア
- 構造化SVMの目的関数
- リスク項が0となる場合
- リスク項は常に0以上の値をとる
- リスク項の意味
- 構造化SVMにおける損失関数
- 構造化SVMの学習
- 構造化SVMにおけるリスク項の勾配の導出
- 構造化SVMのFOBOSによる実装
5.5 条件付き確率場（CRF）
- CRFの目的関数
- CRFの式は何を意味しているか
- CRFの学習
- CRFのための前向き後ろ向きアルゴリズム
- 前向き後ろ向きアルゴリズムの目的
- 効率よくZを計算する
- 前向きと後ろ向きに分けて考える
- さらに効率よくするためには
- 前向き後ろ向きアルゴリズムに対する制限
- 前向き後ろ向きアルゴリズムのまとめ
- CRFの更新式はどのような動作をするか
5.6 統計的かな漢字変換とは
- どのように実装するか
- ビタビアルゴリズムで確率最大のパスを求めるためには
- 積を和に変換する
5.7 言語モデル
- 単語Nグラムによる言語モデル
- ゼロ頻度問題とスムージング
- 加算スムージング
- Kneser-Neyスムージング
- PPM
- PPM-B
- クラスNグラムによる言語モデル
- クラス遷移確率と単語生成確率
- クラスNグラムモデルと隠れマルコフモデル
5.8 かな漢字モデル
5.9 変換精度を評価する
- 適合率と再現率による評価
- 最長共通部分列の計算
- 評価の難しさ
- 評価用のデータの問題
- どこまでを間違いとするか
- 人間の主観との食い違い
- Nベスト解の評価
- どれぐらいの精度が出るのか
- 変換精度以外の評価項目
5.10 変換誤りへの対処
- 前向きDP後ろ向きA*アルゴリズムによるNベスト解の求め方
- ノードクラスへの追加要素
- 優先度付きキュー
- アルゴリズムの概要
- どのような動きをするか
5.11 まとめ
第6章 日本語入力のこれから
6.1 日本語入力の未来予想
- パソコン上での日本語入力の進化
- ユーザインタフェースの改良
- 変換精度の向上
- モバイルデバイスでの日本語入力の進化
- タッチスクリーンからの入力
- 音声認識
- 音声入力の難しさ
6.2 予測入力
- 予測入力のメリットとデメリット
- 機器によって違う予測入力の重要さ
- 予測入力の簡単な実装方法
- 予測候補のランキング方法
- 予測入力と言語モデル
- キャッシュモデル
- トリガーモデル
- トピックモデル
- Nグラムモデルとの組み合わせ方
- この候補を提示すべきか
- よりよい予測入力のために
6.3 かな漢字変換器の改良に向けて
- ビタビアルゴリズムのトライグラムへの拡張
- トライグラムビタビの高速化
- リランキング
- フェーズ分割
- パイプライン化と結合学習
6.4 今後の学習に向けて
- 参考書
- 会議と論文誌
- 国内の主要な学会
- 海外の主要な学会
- 論文誌
- その他の情報源
- ブログ，Twitter
- 勉強会
6.5 まとめ
付録
A.1 数学的な基礎知識
- 数式を読む際の心構え
- 数式とプログラム
- 数式はときにいいかげんである
- 数式について
- 数値の表記方法について
- ベクトルについて
- 総和記号
- 最小値，最大値，argmin，argmax
- 絶対値
- ノルム
- 指数関数
- 計算量について
- 計算量の表記
- 計算量を計算する
A.2 確率の基礎知識
- 確率と確率分布
- 確率とは何か
- 確率的事象は存在しない？
- サイコロの出目は本当にどれも等確率か？
- 確率分布
- 期待値
- 確率や確率分布の表記法
- 確率の便利な性質
- 条件付き確率と同時確率
- 条件付き確率
- 同時確率
- ベイズの定理
- 確率論と統計学
A.3 学習アルゴリズムの歴史
- 歴史的な登場順
- 1990年代以前のモデル
- 統計的手法の導入時期
A.4 機械学習を分類する
- データの性質による分類
- 教師あり学習と教師なし学習
- コーパス
- 教師あり学習/教師なし学習以外のデータの与え方
- 強化学習
- 能動学習
- 解くべき問題による分類
- 最適化の基準による分類
- 良いパラメータとは
- オンライン学習とバッチ学習
- 両者の比較
A.5 いろいろな学習アルゴリズム
- パーセプトロン
- SVM
- マージン最大化からSVMの目的関数の導出
- SVMの最適化アルゴリズム
- SVMとカーネルトリック
- ロジスティック回帰
- パッシブアグレッシブ
- PAのノイズ対策
- PAとパーセプトロンやSVMとの比較
- その他最近の学習アルゴリズム
- Confidence Weighted
- Adaptive Regularization of Weight Vectors
- 学習アルゴリズムをどのように使い分けるか
- おすすめの適用順序
- 状況別の使い分け
A.6 CRFの目的関数の勾配の導出
- logsumexpによるオーバーフローの回避
