目次

第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によるオーバーフローの回避