WEB+DB PRESS plusシリーズ日本語入力を支える技術
―変わり続けるコンピュータと言葉の世界

書籍の概要

この本の概要

コンピュータと人を結ぶ窓口である入力プログラム(IME)は一見シンプルですが,その言語,特に日本語の扱いにはソフトウェアレベルの数多くの工夫が詰まっています。本書では,いまどきの日本語入力システムで利用されている変換アルゴリズムや機械学習といった技術を紐解きます。また,かな漢字変換エンジンの実装を通じて,いかにして変換精度を向上させるか,効率よく日本語を入力するかを丁寧に解説。広くソフトウェア開発者,プログラマの方々へ,新たな技術が続々と取り込まれているIMEのいま知っておきたい基本を紹介します。

こんな方におすすめ

  • 日本語入力ソフトの仕組みや実装に興味のある方
  • 自然言語処理のアルゴリズムやデータ構造に興味のあるプログラマ

著者の一言

日本語入力というのは日本語を使う人にとっては非常に重要な機能ですが,その中身は意外と知られていません。特に,90年代後半以降では統計・機械学習の分野の技術が取り入れられてきましたが,そういったトレンドについて,これまで専門家以外に向けてあまり詳しい解説がありませんでした。

本書では,日本語入力,その中でも特にかな漢字変換について,どうやって作るのかをサンプルコードなどを用いながら噛み砕いて紹介しました。プログラミングを一通り覚えた方であれば実際にプログラムが書けることを目指しました。

本書で紹介したダブル配列やLOUDSといったデータ構造や,条件付き確率場や構造化SVMといった機械学習アルゴリズムは,日本語入力のみならず,読者の方がさまざまなプログラミングの機会に応用が効くものと信じています。日本語入力に興味がある方にはもちろんですが,自然言語処理や機械学習に興味があって一度具体的な応用に触れてみたい,という人にもぜひ読んでいただきたいと考えています。

本書に関するお知らせ

本書に関連する記事を公開しております。

この書籍に関連する記事があります!

新たな技術が続々と取り込まれている日本語入力のいま
みなさんは日々,パソコン,携帯電話,スマートフォンなどで日本語の入力を行っていることと思いますが,それがどのようなしくみでできているのか,考えてみたことはありますか?

目次

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

著者プロフィール

徳永拓之(とくながひろゆき)

日本語入力に興味を持つプログラマ。大阪大学 基礎工学部システム科学科、東京大学大学院 情報理工学系研究科卒業。

ヤフー(株)を経て、現在は(株)Preferred Infrastructureにて自然言語処理や機械学習に関する業務に携わっている。

趣味はカレーの食べ歩き。2012年はもう少し摂取カロリーの低い趣味も見つけたいと考えている。