（2）コスト推定，関連技術

今日の内容
自然言語処理
Natural Language Processing
第５回
2014/10/22
• 形態素解析（２）コスト推定，関連技術
– 形態素解析のためのコスト推定
• 単語 N-gram
• Markov モデルに基づくコスト推定
• 隠れ Markov モデル（HMM）に基づくコスト推定
– 形態素解析ツール紹介： MeCab
芝浦工業大学工学部情報工学科
– 形態素解析の関連技術：かな漢字変換，音声認識
杉本徹
– 第２回課題：形態素解析ツールを使ってみよう
復習：接続コスト最小法
• 各単語および単語どうしの接続にコストを課す．
合計コストが最小の単語分割を求めるのが目標
形態素解析のためのコスト推定
文 S = w1 w2 … wk （wi: 単語）
cost(w1 w2 … wk) =
cost(w1) + cost(w2) + … + cost(wk) +
cost(w1,w2) + cost(w2,w3) + … + cost(wk-1,wk)
• 単語コスト cost(w)
– 単語 w の出現頻度が小さいほど大きな値とする
• 接続コスト cost(w, w’)
– 単語 w と w’ が接続しにくいほど大きな値とする
前回説明した解析例
7(8)
12(25)
日本
出発
1
5
1
1
(36)
3(33)
10(22) 3(12) 7(22) 10(40)
3
8
1
文頭
を
出
発 5 する
文末
8(9) 3 本
3
1 日 8(20) 1
14(39)
3
3
3 本
発する
• 赤線の経路が最小コストの経路（解析結果）となる
前回の宿題
• 単語辞書，単語コスト，接続コストが以下のように
与えられるとき，「すもももももです」という文を
コスト最小法によって形態素解析しなさい．
• 単語辞書・コスト
表層形
品詞
コスト
すもも
名詞
12
もも
名詞
12
も
助詞
です
助動詞
接続コスト
左＼右名詞助詞動詞助動詞文末
文頭
1
10
5
10
－
名詞
3
1
5
5
10
助詞
1
5
3
10
8
4
動詞
3
3
3
1
3
4
助動詞
3
3
10
3
1
1
単語コスト・接続コストの設定
• 直感に基づき手作業で設定するのは大変
コーパスにおける単語や単語連鎖の出現頻度
に基づき，適切なコストを導出する（統計的手法）
1. Markov モデル ← 単語 N-gram
2. 隠れMarkov モデル（HMM）
単語 N-gram データの例
• Google Web 日本語 N-gram
– Google がクロールした Web ページに含まれる
日本語文を形態素解析し，1-gram ～ 7-gram の
出現回数を集計・記録したもの
– 約200億文，2550億単語
1-gram（続き）
情報
商品
ページ
ブログ
表示
検索
利用
サイト
コメント
登録
・・・
約5.4億
約5.1億
約3.5億
約3.3億
約3.3億
約2.9億
約2.5億
約2.4億
約2.3億
約2.2億
・・・
単語 N-gram
• 文中に連続して出現する単語の N個組
（w1, w2, …, wN）
• 例：「ラーメンを食べる」という文において
– 1-gram (unigram) （ラーメン），（を），（食べる）
– 2-gram (bigram) （ラーメン，を），（を，食べる）
– 3-gram (trigram) （ラーメン，を，食べる）
• 与えられたコーパスにおける N-gram （w1, w2,
…, wN）の出現回数を C(w1, w2, …, wN) で表す
1-gram
の
に
を
は
て
が
た
で
と
し
・・・
約125億
約65億
約62億
約55億
約55億
約50億
約44億
約40億
約32億
約31億
・・・
1-gram（続き）
ラーメン
野菜
ケーキ
カレー
うどん
寿司
フルーツ
チョコレート
ステーキ
アイスクリーム
・・・
約2000万
約2000万
約1500万
約1400万
約1200万
約800万
約600万
約500万
約300万
約200万
・・・
2
2-gram
ラーメン屋
ラーメンを
ラーメンの
ラーメンは
ラーメンが
ラーメン店
ラーメンと
ラーメンに
ラーメン食べ
ラーメンしょうゆ
・・・
3-gram
約180万
約140万
約130万
約80万
約70万
約50万
約50万
約40万
約40万
約40万
・・・
N-gram 確率
• N-1 個の単語 w1, w2, …, wN-1 がこの順で出現
するという条件の下で，その次に単語 wN が来る
条件付き確率 P(wN｜w1, w2, …, wN-1)
• コーパスに基づく N-gram 確率の最尤推定
C(w1, w2, …, wN-1, wN)
P(wN｜w1, w2, …, wN-1) =
C(w1, w2, …, wN-1)
※ 最尤推定：標本データ（コーパス）の生起確率を
最大化するように確率モデルのパラメータ値を決める
1-gram 確率（続き）
ラーメン
野菜
ケーキ
カレー
うどん
寿司
フルーツ
チョコレート
ステーキ
アイスクリーム
・・・
0.000077
0.000077
0.000061
0.000054
0.000049
0.000032
0.000022
0.000019
0.000011
0.000007
・・・
ラーメンを食べ
ラーメンを食べる
ラーメンを検索
ラーメンを注文
ラーメンを含む
ラーメンを作っ
ラーメンを作る
ラーメンを中心
ラーメンを食す
ラーメンを頼ん
・・・
約43万
約8万
約6万
約5万
約4万
約3万
約2万
約1万
約1万
約1万
・・・
1-gram 確率
の
に
を
は
て
が
た
で
と
し
・・・
0.049
0.025
0.024
0.021
0.021
0.020
0.017
0.016
0.013
0.012
・・・
2-gram 確率
ラーメン屋
ラーメンを
ラーメンの
ラーメンは
ラーメンが
ラーメン店
ラーメンと
ラーメンに
ラーメン食べ
ラーメンしょうゆ
・・・
0.089
0.070
0.064
0.040
0.036
0.026
0.025
0.021
0.021
0.019
・・・
3
3-gram 確率
ラーメンを食べ
ラーメンを食べる
ラーメンを検索
ラーメンを注文
ラーメンを含む
ラーメンを作っ
ラーメンを作る
ラーメンを中心
ラーメンを食す
ラーメンを頼ん
・・・
単語 N-gram モデル
0.31
0.06
0.05
0.04
0.03
0.02
0.01
0.01
0.01
0.01
・・・
N-gram モデルは近似
• 例： w1 = 「ラーメン」 w2 = 「を」 w3 = 「食べる」
P(w1, w2, w3) = P(w1)×P(w2｜w1)×P(w3｜w1,w2)
0.0000003
0.00008
0.07
0.06
– 1-gram モデル
P(w1, w2, w3) = P(w1) × P(w2) × P(w3)
0.0000000001
0.00008
0.02
0.00008
– 2-gram モデル
P(w1, w2, w3) = P(w1) × P(w2｜w1) × P(w3｜w2)
0.000000003
0.00008
0.07
0.0006
• 近似としては N の値が大きいほど良いが，N≧4 だとコーパ
ス中の各 N-gram の出現回数が減り，出現確率の推定値の
信頼性が低くなるため，応用では N = 2, 3 がよく用いられる
再掲：接続コスト最小法
• 各単語および単語どうしの接続にコストを課す．
合計コストが最小の単語分割を求めるのが目標
文 S = w1 w2 … wk （wi: 単語）
cost(w1 w2 … wk) =
cost(w1) + cost(w2) + … + cost(wk) +
cost(w1,w2) + cost(w2,w3) + … + cost(wk-1,wk)
• 単語コスト cost(w)
– 単語 w の出現頻度が小さいほど大きな値とする
• 接続コスト cost(w, w’)
• 言語の確率モデルの一種であり，文中の各単語の
出現確率は直前の N-1 個の単語の組み合わせに
依存して決定する（N-1重Markov過程）と見なす
• 例： 1-gram モデル
（文中の各単語の出現確率は，直前の単語に依存しない）
P(w1, w2, …, wk) = P(w1)×P(w2)×…×P(wk)
• 例： 2-gram モデル
（単語の出現確率は，直前の1単語に依存して決まる）
P(w1, w2, …, wk) = P(w1)×P(w2｜w1)×P(w3｜w2)
×…×P(wk｜wk-1)
Markovモデルに基づく形態素解析
• 解析結果候補の中から，単語N-gramモデルにより
求められる確率が最大の候補を選ぶ
• 2-gram モデルの場合
文 S = w1 w2 … wk （wi: 単語）
P(w1, w2, …, wk) = P(w1)×P(w2｜w1)×P(w3｜w2)
×…×P(wk｜wk-1)
この式の値が最大となる解析候補を選ぶ
Markovモデルと接続コスト最小法の関係
• コーパスから最尤推定により得られる 2-gram 確率
を用いて，接続コストを以下のように設定する
cost(w, w’) = －log P(w’｜w)
このとき，
cost(w1,w2) + cost(w2,w3) + … + cost(wk-1,wk)
= －log P(w2｜w1)－log P(w3｜w2)－…－log P(wk｜wk-1)
= －log (P(w2｜w1)×P(w3｜w2)×…× P(wk｜wk-1))
つまり，単語列 w1 w2 … wk の接続コストの和の最小化は
生起確率の最大化とほぼ一致する
– 単語 w と w’ が接続しにくいほど大きな値とする
4
続き
隠れMarkovモデルに基づく形態素解析
• 形態素解析結果の候補の中から，HMM によって
求められる確率が最大の候補を選ぶ
• 言語の隠れMarkovモデル
（Hidden Markov Model, HMM）
– 文中の各単語 wi は，Markov過程に従い遷移する（観測
不可能な）内部状態 tj から確率的に生成されると考える
• 文 S = w1 w2 … wk （wi: 単語）に対し，
k
P(w1, w2, …, wk) = Π P(ti｜ti-1) P(wi｜ti)
i=1
– 内部状態 tj として，通常は品詞を考える
= P(t1)×P(t2｜t1)×…×P(tk｜tk-1)
×P(w1｜t1)×…×P(wk｜tk)
p．．
内部状態
（品詞）
q1
出力
（単語）
t
p12 2 p．．
t1
t
p13
p34 4
t3
p35
t
q2 q3
5
q4
この式の値が最大となる解析候補を選ぶ
• 品詞2-gram確率の最尤推定 P(ti｜ti-1) ＝ C(ti-1, ti) ／ C(ti-1)
• 品詞ごとの単語出現確率の最尤推定 P(wi｜ti)＝C(wi, ti)／C(ti)
w1 w2 w3 w4
例
HMM と接続コスト最小法の関係
• w1 = 「ラーメン」 w2 = 「を」 w3 = 「食べる」
P(ラーメン, を, 食べる)
= P(名詞) × P(助詞｜名詞) × P(動詞｜助詞)
×P(ラーメン｜名詞)×P(を｜助詞)×P(食べる｜動詞)
例えば P(助詞｜名詞) は，名詞の次の語が助詞である確率
P(ラーメン｜名詞）は，任意に選んだ名詞が「ラーメン」である確率
P(名詞）
名詞
P(ラーメン | 名詞）
助詞
P(助詞 | 名詞）
このとき，単語列 w1 w2 … wk の単語コストと接続コストの和
の最小化はHMMにおける生起確率の最大化とほぼ一致する
動詞
P(動詞 | 助詞）
を
食べる
例：短い文章からの接続コスト推定
重ね着
名
する
動
を
助
し
動
て
助
暖房
名
を
助
ウォームビズ
が
助
１日
名
スタート
し
動
名
名
名
に
助
た
。
控えめ
助動
国内
名
で
助
稼働
名
する
動
原子力
発電所
名
名
中
名
環境省
電力
名
使用
名
を
助
抑えよ
う
名
は
助
動
助動
と
助
室温
名
を
助
２０度
名
に
助
保つ
動
よう
名
に
助
呼びかけ
て
助
いる
動
。
動
cost(w)
= －log P(w｜t)
cost(w, w’) = －log P(t’｜t)
（t, t’ は単語 w, w’ の品詞）
P(食べる | 動詞）
P(を | 助詞）
ラーメン
• コーパスから最尤推定により得られる確率を用いて，
単語コストと接続コストを以下のように設定する
が
助
品詞間の接続コストの推定
• 文章中の出現回数
C(t, t’)
ない
形容
出典：読売新聞 2013/11/1
左＼右名詞助詞動詞助動詞文末
文頭
2
名詞
4
助詞
7
動詞
3
助動詞
• cost(t, t’)
= －log P(t’｜t)
C(t, t’)
= －log
C(t)
11
2
6
2
2
1
1
1
左＼右名詞助詞動詞助動詞文末
文頭
0
∞
∞
∞
∞
名詞
2.1
0.6
3.1
∞
∞
助詞
0.9
∞
1.1
∞
∞
動詞
1.4
2
∞
2
3
助動詞
∞
1
∞
∞
1
5
形態素解析ツールの例
• MeCab （工藤拓，2006～）
形態素解析ツールの紹介
– 条件付き確率場（CRF）を用いたコスト推定
– ChaSen より高速に動作
• ChaSen （奈良先端大，1997～）
– HMM を用いた単語コスト・接続コストの自動推定
• JUMAN（京都大，1993～）
– 単語コスト・接続コストは人手で設定
– MeCab, ChaSen と異なり，益岡・田窪文法に基づく辞書を使用
– 代表表記や意味情報など，出力される単語情報が充実
• Yahoo! 日本語形態素解析API
– Web 上で形態素解析を実行できる Web サービス
MeCab の特徴
MeCab のインストール方法
詳しくは，MeCab のホームページ参照
• オープンソースの形態素解析ツール
• 解析手法
–
–
–
–
接続コスト最小法（単語コスト＋接続コスト）
条件付き確率場（CRF）を用いたコスト推定
Viterbi アルゴリズムを用いた解探索
辞書検索は，Trie構造をダブル配列で実装
• 辞書，コーパスに依存しない汎用の設計
– 異なる品詞体系をもつ複数の辞書に対応
– ユーザが用意したコーパスからのコスト推定も可能
• Windows
– MeCab のホームページからバイナリパッケージ（辞書
内蔵）をダウンロードしてインストール
– 学情の環境では不可
• UNIX
– ソースコードと辞書をダウンロードし，ホームページの
説明を参考に，それぞれコンパイル，インストールする
– インストール時の設定により，学情のUNIXサーバにも
インストール可能（次ページ以降で説明）
参考：学情UNIXサーバでのインストール手順
• 一般ユーザは学情システムのシステムディレクトリにソフトウェア
をインストールする権限がないため，インストール先をデフォルト
のシステムディレクトリから自分のホームディレクトリ内の適当な
場所（今回の説明では，ホームディレクトリ下の usr という名前の
ディレクトリとする）に変更してインストール処理を実行する
手順１まず mecab-0.996.tar.gz を適当なディレクトリへダウンロードする
手順２ダウンロードしたディレクトリに移動し，以下のコマンドを順に実行
tar zxfv mecab-0.996.tar.gz
cd mecab-0.996
./configure --prefix=$HOME/usr --with-charset=utf8
make
make check
make install
続き
手順３次に，辞書をインストールする．mecab-ipadic-2.7.0-（略）.tar.gz
をダウンロードし，以下のコマンドを順に実行する
tar zxfv mecab-ipadic-2.7.0-（略）.tar.gz
cd mecab-ipadic-2.7.0-（略）
./configure --prefix=$HOME/usr （次の行に続く）
--with-charset=utf8 （次の行に続く）
--with-mecab-config=$HOME/usr/bin/mecab-config
make
make install
手順４インストールが終わったので，MeCab を起動する
～/usr/bin/mecab
※ ~/usr/bin を環境変数 PATH に追加しておくと楽
6
MeCab の使い方
• MeCab を起動し，解析したい文を標準入力から入力する
入力文
品詞（4階層）
ラーメンを食べた。
ラーメン名詞,一般,*,*,*,*,ラーメン,ラーメン,ラーメン
を
助詞,格助詞,一般,*,*,*,を,ヲ,ヲ
食べ
動詞,自立,*,*,一段,連用形,食べる,タベ,タベ
た
助動詞,*,*,*,特殊・タ,基本形,た,タ,タ
。
記号,句点,*,*,*,*,。,。,。
EOS
% mecab
形態素解析の関連技術
• かな漢字変換
• または，解析したい文章を１文ずつ行に区切ってテキストファイ
ルに保存し，そのファイル名を引数として MeCab を実行する
• 音声認識
• コマンドオプションなどの詳細は，MeCab ホームページまたは
ヘルプを参照
かな漢字変換
参考：確率的言語モデル
• 入力：ひらがな列 → 出力：かな漢字列
• 任意の単語列 w1, w2, …, wk に対して，その単語列
が実際に使用される（出現する）確率を割り当てる
例： P(太郎, は, 大学生, です) = ？
P(太郎, は, 芝浦工大, の, 三年生, です) = ？
• 確率的言語モデルの例
「きょうはあめ」 → 「今日は雨」？「京は飴」？
• 変換手法
– ２文節最長一致法（ATOK など）
• 文の先頭から，連続する２文節の長さの和が最長の候補を選んで
進めていく
– コスト最小法（MS-IME など）
• 単語コストと接続コストの和が最小の候補を選ぶ
• Viterbi アルゴリズムによる探索
☆単語 N-gram モデル
1-gram モデル
P(w1, w2, …, wk) = P(w1)×P(w2)×…×P(wk)
2-gram モデル
– 統計的手法
• 事後確率が最大の単語列を求める
P(w1, w2, …, wk) = P(w1)×P(w2｜w1)×…×P(wk｜wk-1)
参考文献：「日本語入力を支える技術」徳永，技術評論社
音声認識
統計的手法に基づくかな漢字変換
問題：入力ひらがな列 X に対する事後確率 P(W｜X)
が最大となる単語列 W を見つける
• Bayesの法則により
P(W | X ) 
• 入力：音声信号 → 出力：単語列
「豊洲の天気」
P( X | W )  P(W )
P( X )
• 近年は，統計的手法が主流
なので，P(X｜W)×P(W) が最大となる W を見つければよい
– P(X｜W）単語列 W の読みが X である確率
– P(W)
単語列 W が出現する確率
• 分類
– 単語認識 vs 連続音声（単語列）認識
– 特定話者 vs 不特定話者
7
統計的手法に基づく音声認識
問題：入力音声 X に対する事後確率 P(W｜X)
が最大となる単語列 W を見つける
• Bayesの法則により
P( X | W )  P(W )
P(W | X ) 
P( X )
なので，P(X｜W)×P(W) が最大となる W を見つければよい
– P(X｜W）単語列 W の音声（の特徴量）が X である確率
（音響モデルの確率）
– P(W)
単語列 W が発言される確率（言語モデルの確率）
音声認識システムの構成
入力音声
音声分析
X
単語辞書
音響モデル
P(X｜W)
探索
P(W)
P(W｜X) ∝ P(X｜W)・P(W)
言語モデル
認識結果 W = argmax P(W｜X)
レポート課題
第２回課題
形態素解析ツールを使ってみよう
• まず，異なる文体の文章を２つ（それぞれ100文字以上）
自由に選ぶ．これをテキストA，テキストBと呼ぶ
– 新聞記事，ブログ，twitter，小説など
• テキストＡとテキストＢを同じ形態素解析ツール（MeCab
を推奨するが，それ以外も可）で解析する
– 複数文からなるテキストを解析する際，1文ずつに分けて形態素
解析ツールに与える
• 解析結果を分析する
分析１：自分の目でチェックして，解析の誤りがないか確認する
分析２：テキストＡ，テキストＢそれぞれにおける各品詞の出現割合
（例：テキストＡの全単語中△□%が名詞）を求めて，比較する
レポートの形式，期限，提出方法
• 形式：電子ファイル（MS Word の doc/docx，またはPDF）
• 内容構成：レポートの内容に，下記の①②③④を
含めること
①方法の説明
②選んだ文章と，ツールによる解析結果
③分析結果（必要に応じて表やグラフを用いる）
④結果についての考察
• 期限： 11月11日（火）
• 提出方法：電子メールで杉本宛（sugimoto@～）
8

Download Report