こんにちは、買物情報事業部の荒引 (@a_bicky) です。 前回、「検索結果の疑問を解消するための検索の基礎」で単語単位でインデキシングする前提で説明しましたが、今回は文などを単語単位で分割するために使う技術である形態素解析について触れます。 形態素解析器には色々ありますが、中でもメジャーと思われる MeCab の仕組みについて説明します。
MeCab の解析精度を上げるために辞書に単語を追加したことのある方もいると思いますが、動作原理を理解することで単語を追加する際に適切な生起コストを設定できるようになったり、学習の際に適切なパラメータを設定できるようになったりするはずです。
なお、MeCab は汎用テキスト変換ツールとしても使用できます が、簡単のため MeCab + IPA 辞書のデフォルト設定前提で説明します。
アジェンダ
- 形態素解析とは
- MeCab における最適な解析結果の推定
- ラティスの構築と最適パスの選択
- 未知語処理
- 共通接頭辞検索 (common prefix search)
- MeCab におけるコストの算出
- CRF によるモデル化
- 素性関数
- モデルから生起コストと連接コストへの変換
- 最後に
「MeCab における最適な解析結果の推定」では、形態素解析する際に MeCab が内部でどのようなことを行っているかについて説明します。「MeCab におけるコストの算出」は辞書を独自で追加したりモデルを再学習させたりする人向けの内容で、ある程度機械学習の知識を持っていることを前提として MeCab がどのようにコストを決定しているかについて説明します。
形態素解析とは
日本語の形態素解析では一般的に次の 2 つのことを行います。
- 単語分割*1
- 品詞付与
次の結果は「東京都に住む」を MeCab で形態素解析した結果です。入力文が適切に分割され、適切な品詞が割り当てられています。
% echo 東京都に住む | mecab 東京 名詞,固有名詞,地域,一般,*,*,東京,トウキョウ,トーキョー 都 名詞,接尾,地域,*,*,*,都,ト,ト に 助詞,格助詞,一般,*,*,*,に,ニ,ニ 住む 動詞,自立,*,*,五段・マ行,基本形,住む,スム,スム EOS
MeCab における最適な解析結果の推定
本節では MeCab を使って形態素解析する際に内部でどのようなことが行われているかを説明します。 単純化すると、最適な解析結果を求めるには次の 2 つのことを行います。
- ラティスを構築する
- ラティスから最適なパスを選択する
ラティスとは、考えられる全ての解を表現したデータ構造で、例えば次のようなデータです。
BOS は beginning of sentence で文頭、EOS は end of sentence で文末を意味しています。 各ラティスのノードには単語の生起コスト、エッジには品詞の連接コスト*2が割り当てられています。 最適なパスを選択する際には累積コストを最小にするパスを選択します。
累積コストを最小にするパスは動的計画法により効率的に求めることができます（ビタビアルゴリズム）。
ラティスの構築と最適パスの選択
ラティスを構築してから最適なパスを選択すると前述しましたが、実際にはラティスの構築と累積コストの計算は同時に行われ、ラティスの構築が完了した時点で最適パスが求まる形になっています。 具体的には次の手順によってラティスの構築と最適パスの選択を行います。
- n = 1 とする
- 入力文の n 文字目において分割候補になり得る単語を辞書から全て取得する (共通接頭辞検索)
- カタカナ等同じ文字の種類の連続をひとまとめにした単語を未知語として候補に追加することもある
- 取得した全ての単語に関して、累積コストが最小になるエッジとその累積コストを求める
- n を +1 して入力文の末尾に到達するまで 2, 3 を繰り返す
- 末尾から先頭に向かって累積コストを最小にするパスをたどる（これが最適パス）
なお、単語の生起コストは sys.dic 等の辞書に、品詞の連接コストは matrix.bin (matrix.def) に保存されています。
上記の処理は次のスライドを見てもらうとイメージが付きやすいと思います。太いエッジは、右側のノード（単語）にとって累積コストが最小になるパスを意味しています。 左文脈 ID、右文脈 ID は特殊な使い方をしない限りは品詞 ID のようなものと理解しておけば大丈夫です。前件文脈 ID は連接する左側の単語の右文脈 ID、後件文脈 ID は右側の単語の左文脈 ID です。
実際に生起コストや連接コストを出してみるとスライドのとおりになっていることがわかります。-F オプションで出力形式を指定することで、デフォルトの内容に加えて生起コスト、連接コスト、累積コストも表示しています。
% # 表層形\t素性\t生起コスト,連接コスト,累積コスト % echo 東京都に住む | mecab -F '%m\t%H\t%pw,%pC,%pc\n' -E 'EOS\t%pw,%pC,%pc\n' 東京 名詞,固有名詞,地域,一般,*,*,東京,トウキョウ,トーキョー 3003,-310,2693 都 名詞,接尾,地域,*,*,*,都,ト,ト 9428,-9617,2504 に 助詞,格助詞,一般,*,*,*,に,ニ,ニ 4304,-3573,3235 住む 動詞,自立,*,*,五段・マ行,基本形,住む,スム,スム 7048,-3547,6736 EOS 0,-409,6327
未知語処理
ラティスを構築する際、辞書に登録されている単語しか考慮しない場合、例えば次のように任意の数字を処理するには考えうる全ての値を辞書に登録しておかなければ正しく解析できません。
% echo 1234個 | mecab 1234 名詞,数,*,*,*,*,* 個 名詞,接尾,助数詞,*,*,*,個,コ,コ EOS
辞書に存在しない単語（未知語）にも対応するため、MeCab では同じ文字の種類 (e.g. KATAKANA) でまとめて 1 つの単語とみなすようにしています。これによって、ラティスを構築する際に未知語のノードを追加し、未知語を含んだ解を選択することも可能になります。 未知語の生起コストに関しては文字の種類に応じて unk.dic (unk.def) に定義されています。
ラティスに未知語を追加するかどうかは char.def で制御されています。以下は char.def の該当部分です。
# CHARACTER CATEGORY DEFINITION # # CATEGORY_NAME INVOKE GROUP LENGTH # # - CATEGORY_NAME: Name of category. you have to define DEFAULT class. # - INVOKE: 1/0: always invoke unknown word processing, evan when the word can be found in the lexicon # - GROUP: 1/0: make a new word by grouping the same chracter category # - LENGTH: n: 1 to n length new words are added # DEFAULT 0 1 0 # DEFAULT is a mandatory category! SPACE 0 1 0 KANJI 0 0 2 SYMBOL 1 1 0 NUMERIC 1 1 0 ALPHA 1 1 0 HIRAGANA 0 1 2 KATAKANA 1 1 2 KANJINUMERIC 1 1 0 GREEK 1 1 0 CYRILLIC 1 1 0
2, 3, 4 列目が未知語処理に関する設定で、それぞれ次のような意味を持っています。
| 列数 | 名前 | 意味 |
|---|---|---|
| 2 | INVOKE | 1 であれば常に未知語を追加する。0 であれば、候補となる単語が見つからなかった場合にのみ未知語を追加する |
| 3 | GROUP | 1 であれば同じ種類の文字を最大 max-grouping-size 文字まとめて 1 つの未知語として追加する |
| 4 | LENGTH | 現在の位置から 1 〜 LENGTH 文字の部分文字列全てを未知語として追加する |
GROUP と LENGTH の設定は互いに独立です。例えば、「ホゲホゲ」の 1 文字目の位置で単語を追加する場合、KATAKANA は GROUP が 1 なので「ホゲホゲ」という未知語を追加します。また、LENGTH が 2 なので、「ホ」と「ホゲ」という未知語も追加します。2 文字目の位置で未知語を追加する場合も同様に「ゲホゲ」、「ゲ」、「ゲホ」という未知語を追加します。
% echo ホゲホゲ | mecab ホゲホゲ 名詞,固有名詞,組織,*,*,*,* EOS
漢字は INVOKE が 0 で、単語が辞書にある場合は未知語を追加しないので、漢字で構成される固有名詞の解析は上手くいかないことが多いです。
% echo 荒引 | mecab 荒 名詞,固有名詞,人名,姓,*,*,荒,アラ,アラ 引 名詞,固有名詞,組織,*,*,*,* EOS
共通接頭辞検索 (common prefix search)
ラティスを構築する上で、該当位置において候補となり得る全ての単語を辞書から取得する必要があります。
common_prefix_search("東京都に住む") # => ["東", "東京"]
common_prefix_search("京都に住む") # => ["京", "京都"]
common_prefix_search("都に住む") # => ["都（名詞）", "都（接尾辞）"]
このような用途の検索は共通接頭辞検索 (common prefix search) と呼ばれています。共通接頭辞検索を高速に行うためには TRIE というデータ構造を利用するのが一般的です。 MeCab では TRIE の中でもダブル配列という実装を採用しています*3。ダブル配列については非常にわかりやすいエントリーがあるので興味のある方は次のエントリーを参照してみてください。
MeCab におけるコストの算出
形態素解析時には生起コストや連接コストは与えられている状態ですが、本節ではそれらのコストを事前にどのように決定しているかについて説明します。 コストの算出には大きく 2 つの手順があります。
- CRF によるモデル化
- モデルからコストの算出
MeCab には新しい単語を追加する際に自動で生起コストを推定する機能がありますが、モデルファイルが必要なのは、1 が終わった状態で 2 を行うためです。
余談ですが、あるドメインに頻出する単語を新しく辞書に追加する際、生起コストを自動推定しても実際よりも高くなることがあるはずです。 モデルはどの品詞が出現しやすいか、どの文字種が出現しやすいか、どの原形が出現しやすいか等の情報を保持していますが、新しく追加する単語の原形などの出現しやすさについての情報を持っていないからです。 個人的には、自動推定するよりも、同じぐらいの頻度で出現すると思われる単語の生起コストを新しく追加する単語に割り当てる方が確実だと思います。
それでは、モデル化からコストの算出まで説明していきます。
CRF によるモデル化
MeCab では生起コストと連接コストを決定する上で Conditional Random Fields (CRF) を使ってモデル化しています。CRF は系列ラベリングの一手法で、系列データが与えられると対応する系列ラベルを出力します。 MeCab の場合、入力の系列データは単語分割済みの文字列の配列、出力は品詞情報などを保持したオブジェクトの配列です。
CRF のモデルは次の式で表すことができます。φは素性関数で詳細は後述します。Z は確率の総和を 1 にするための正規化項です。
MeCab では、人手等で形態素解析した x, y の組み合わせに対し、正則化項も追加して次の目的関数を最小とするパラメータαを求め、αの値を基にコストを決定しています。
なお、MeCab ではモデルを再学習させることもできますが、その場合の目的関数は次のようになっています。
これは、元のモデルのパラメータから変化量が大きいと損失が大きくなるので、元のモデルをできる限り変化させないように最適化することを意味しています。
これらの目的関数は凸関数であり、MeCab では L-BFGS（準ニュートン法の一種）で解を求めています。
CRF については「言語処理のための機械学習入門」の 5 章「系列ラベリング」に非常にわかりやすくまとまっているので、詳細を知りたい方はそちらを参照してください。
素性関数
素性関数は、引数がその素性関数の条件を満たす場合に 1、そうでない場合に 0 を返す関数です。 MeCab で採用している CRF は次のグラフィカルモデルのように、t 番目の y は 1 つ前の y と現在の x にしか依存しないことを仮定しています。
よって、
と表すことができます。
素性関数の内容は feature.def を基に決定されます。それ故、feature.def の内容は素性テンプレートと呼ばれます。 feature.def には unigram feature（現在の単語にしか依存しない素性）と bigram feature（現在と 1 つ前の単語に依存する素性）が定義されています。
ここで、例として素性テンプレートが次の場合を考えます。
UNIGRAM W0:%F[6] BIGRAM B00:%L[0]/%R[0]
%F[6] は処理対象の単語の7番目の素性、%L[0] は処理対象の単語の前の単語（左側の単語）の1番目の素性、%R[0] は処理対象の単語（右側の単語）の1番目の素性を意味しています。
学習データは MeCab の出力と同じ形式のものを用意します。左の列が表層形で右の列が単語の素性です。 素性の内容は左から順に、品詞、品詞細分類1、品詞細分類2、品詞細分類3、活用型、活用形、原形、読み、発音になっています。
東京 名詞,固有名詞,地域,一般,*,*,東京,トウキョウ,トーキョー 都 名詞,接尾,地域,*,*,*,都,ト,ト に 助詞,格助詞,一般,*,*,*,に,ニ,ニ 住む 動詞,自立,*,*,五段・マ行,基本形,住む,スム,スム EOS
処理対象が「住む」の場合、素性テンプレートとテンプレートを基に生成される素性は次のとおりです。
| 素性テンプレート | 素性 |
|---|---|
| W0:%F[6] | W0:住む |
| B00:%L[0]/%R[0] | B00:助詞/動詞 |
素性テンプレートから生成された素性から、素性関数は次のように定義できます。
モデルから生起コストと連接コストへの変換
前述のとおり、feature.def には unigram feature と bigram feature が定義されています。 生起コストは unigram feature に属する素性関数を使って次のように算出されます。x は y の表層形、cost factor は dicrc に定義されている cost-factor です。
連接コストは bigram feature に属する素性関数を使って次のように算出されます。x は yjの表層形です。
mecab-ipadic の feature.def の bigram feature は品詞の情報しか使っていないため、MeCab の連接コストは品詞の情報しか考慮されていないことになります。よって、本エントリーでは連接コストのことを品詞の連接コストと呼んでいました。
以上の方法で算出した生起コストと連接コストがそれぞれ sys.dic と matrix.bin に保存されています。
最後に
以上、MeCab がどのように形態素解析しているかについて説明しました。 本エントリーを通じて、自然言語処理を応用した各種サービスの精度向上に少しでも貢献できれば幸いです。
追記：興味のある方はこちらもどうぞ
