人工知能・機械学習・自然言語処理周辺の技術情報

研究ブログ
2018-04-09

【研究】技術的側面からの検索エンジンの考察 ~第1回 テキストマイニングの基本中の基本、形態素解析とBOWとは~

「検索エンジンのアルゴリズムを技術的に紐解いてみたい」というモチベーションで、当連載を始めることにしました。

とはいえ、中々これは壮大な取り組みになります。先がどうなるかわからないです。しかし、なにごともとにかく触れてみるやってみる、すなわちハンズオンが重要です。

そのため、初期の三部作だけ予告して、連載を始めてみたいと思います。
とにかく初期の三部作では、「テキストマイニングの知見から検索エンジンのアルゴリズム変遷を振り返る」ものとしたいと思います。それぞれの回では、

第1回 テキストマイニングの基本中の基本、形態素解析とBOWとは

第2回 テキストマイニングの基本的手法(TFIDF、LSI、LDA

第3回  検索エンジンのアルゴリズム変遷まとめ~テキストマイニングの手法に基づいたロジックの推定

をテーマとしたいと思います。

あまりこれまで行われてこなかった取り組みだと思いますので、非常に面白いものになると確信しています。読み応えのある連載にできるよう、頑張っていきたいと思いますので今後ともよろしくお願いします。

以下が第1回記事の目次です。

テキストマイニングとは、鍵を握る技術:形態素解析

最初にテキストマイニングとは何かについて認識合わせをしましょう。

Wikipediaのテキストマイニングのページには、

テキストマイニング(text mining)は、文字列を対象としたデータマイニングのことである。通常の文章からなるデータを単語や文節で区切り、それらの出現の頻度や共出現の相関、出現傾向、時系列などを解析することで有用な情報を取り出す、テキストデータの分析方法である。

テキストデータの多くは形式が定まっておらず、また日本語は英語などと比べて単語の境界判別の必要性(→わかち書き)や文法ゆらぎが大きい点において形態素解析が困難であったが、自然言語処理の発展により実用的な水準の分析が可能となった。テキストマイニングの対象としては、顧客からのアンケートの回答やコールセンターに寄せられる質問や意見、電子掲示板やメーリングリストに蓄積されたテキストデータなどがある。

とあります。小難しい話なのでざっくりまとめると、日本語のテキストマイニング(文章の分析)は、分かち書き(文を最小の単位、単語)に分けて記述することです。

「僕はジョンに会った」なら「僕|は|ジョン|に|会っ|た」になる。)による形態素解析が鍵になるということです。形態素解析とは文を構成する最小の構成要素に分割するという手法のことです。文の最小単位を形態素と読んでいます。

形態素解析をコンピュータで行うには形態素解析用のソフトが必要になります。その中でも、著者が毎回使用しているのはmecabというオープンソフトウェアです。

mecabを実際に使用してみたい方は、以下のURLのサイトから無料でダウンロードすることが可能です。

http://mecab.googlecode.com/svn/trunk/mecab/doc/index.html#download

たとえば、「すもももももももものうち」においてmecabを用いた結果は、

のようになります。実際にうまくいっています。偶然なのではないか思う方もおられると思いますので、もう少し具体例で実験してみます。

  • 隣の客はよく柿食う客だ
  • 明日からよろしくお願いします。
  • 諦めたらそこで試合終了ですよ。

どれもうまく分割できています。このように分割した形態素を元に、様々な手法で分析するのがテキストマイニングです。(TFIDF、LSI、LDAなどの統計解析手法に関しては、紙面の都合上次回といたします。)

形態素解析の仕組み

形態素解析って不思議なものです。「どうやって分割しているのだろうか」と気になる方は多いのではないかと思います。

昔に流行った堺正章のさらば恋人の「さよならとかいたてがみ」が「さよなら|と|かいた|てがみ」ではなく「さよなら|とかい|たてがみ」と聞き間違いをしていた人が多いというのは有名な話です。そこで、「さよならとかいたてがみ」を形態素解析してみました。

結果としては上記です。「た」が助詞、「てがみ」が名詞ではなく、「たてがみ」で一つの名詞として検出されています。ただここで少し立ち止まって考えてみると、全て平仮名で書いてあるということに気づきます。

人間が目で見ても平仮名の場合は読み違える可能性があります。なので、漢字に変更したりしなかったりのパターンでいくつか試してみました。

  1. 「かいた」を漢字、「てがみ」を漢字
  2. 「かいた」を漢字、「てがみ」を平仮名
  3. 「かいた」を平仮名、「てがみ」を漢字

結果としては、①と③が成功で②が失敗でした。これはどういうことなのでしょうか。

原因としては、mecabのロジックにあります。

http://chasen.naist.jp/chaki/t/2009-09-30/doc/mecab-cabocha-nlp-seminar-2009.pdf

上記URLは実際にmecabを作成した、奈良先端科学技術大学院大学出身でgoogleソフトウェアエンジニアのキャリアを持つ工藤氏がmecabのロジックについて解説したものです。こちらの資料は情報量が多く読むにはつらいと思いますので、一部抜粋してお伝えします。

(詳細が気になる方は上記URLの先の資料をご確認ください)

mecabの仕組みを知るために理解するとよいのは、

  • 単語辞書
  • 形態素ラティス
  • 最小コスト法

の三つです。これらについて以下で説明します。

・単語辞書

形態素解析を行うにあたり、文章から単語を分かち書きしなくてはなりません。その際にどこで切ればよいかというのがまず一つの課題です。前述の例の「さよならとかいたてがみ」のように文には様々な分け方が存在しますが、まず全てのありうる結果を抽出することを考えましょう。そこで必要になるのが単語の辞書です。

それぞれの品詞に対して、名詞なら「さよなら」、「とかい」、「たてがみ」だし、助詞なら「て」、「に」、「を」、「は」、「と」です。動詞だと「書く」です。動詞は文中に原型でない形で出現することが多いので、原型で管理します。

また、辞書というのは単語リストを想像される方が多いかもしれませんが、単語は10万以上にもわたり、これらを毎回検索していては計算時間が膨大にかかってしまいます。そのため、以下のような辞書の持ち方をして、管理をします。


出典: http://chasen.naist.jp/chaki/t/2009-09-30/doc/mecab-cabocha-nlp-seminar-2009.pdf

上図のように、一文字目、二文字目とたどっていけるような辞書になっています。白丸は次がある場合、赤丸は単語の終了として意味が通じるものを表しています。上図例だと、一文字目が「あ」の場合は、「あわ」、「あら」、「あらし」、「あらまき」を辞書として持っているということを意味しています。

上記の辞書を用いて、形態素解析の結果としてありうる全パターンを抽出します。

・形態素ラティス

形態素ラティスとは、前述の辞書を用いて抽出したすべてのありうる分かち書きの結果をグラフで表現した構造のことを指します。


出典: http://chasen.naist.jp/chaki/t/2009-09-30/doc/mecab-cabocha-nlp-seminar-2009.pdf

たとえば、「東京都に住む」であれば、形態素ラティスは上図のようになります。このように、ありうる分かち書きの結果を全てグラフで表現したのが形態素ラティスになります。

・最小コスト法

最小コスト法とは、形態素ラティスの中でどれが一番正しいと思われる分かち書きの仕方なのかを判断するために用います。

コストとは具体的には、

  • 二つの単語のつながりにくさ(連接コスト)
  • 一つの単語の出現しやすさ(生起コスト)

の二つのことです。これらを各単語の辞書とともに持つことで、計算できるようにしておきます。(コストに関しては、文末のトリビア(リンクで飛ばす)のところでまとめているのでそちらをご確認下さい)

出典: http://chasen.naist.jp/chaki/t/2009-09-30/doc/mecab-cabocha-nlp-seminar-2009.pdf

上図が、「東京都に住む」の形態素ラティスに対し、連接コストと生起コストを記してみたものになります。上図では、「東京|都|に|住む」のコストが

10+2+20+10+0+5+5+10+5=67(緑の枠でくくった数字の和)

となり、他と比べ最小となっています。

数字の羅列でわかりにくいので、他の5パターンについても検証してみます。

  • 東京|都|に(動詞)|住む           : 10+2+20+10+5+30+10+10+5=102
  • 東|京|都|に|住む                  : 10+5+10+5+20+10+0+5+5+10+5=85
  • 東|京|都|に(動詞)|住む    : 10+5+10+5+20+10+5+30+10+10+5=120
  • 東|京都|に|住む                     : 10+5+10+5+20+5+5+10+5=75
  • 東|京都|に(動詞)|住む       : 10+5+10+5+10+30+10+10+5=95

確かに、「東京|都|に|住む」のコストが一番小さいという結果でした。

そのため、このケースにおけるmecabの出力は「東京|都|に|住む」になります。

このような方法で、mecabは入力文に対し、分かち書きの結果を返しています。

あくまで、最もそうだと思われるパターンを返しているに過ぎないので、「さよならとかいたてがみ」のように場合によっては間違った結果が出力されることもあるのです。

(ただし、平仮名で書いてあるケースは人間でも読み違えるのだから、これに関してはある程度は仕方がないのではないかとも思います。)

形態素解析による分かち書きから行列変換(BOW)まで

テキストマイニングにおいては、構造化(行列化)されていないデータを用います。反面、統計解析の手法は基本的に行列化されているデータを用いるので、統計的な手法をテキストデータに適用するには、テキストデータを行列化してやらなければなりません。

そのためテキストを行列化された中間表現に変更する前処理が必要です。

上図は文書群を構造化し行列に落としたもの(Bag Of Words)です。ここでいうDは文書群、Nは各文書、Wは単語を意味しています。

このように形態素解析をおこなった文もしくは文章を行列化したものがBOW(Bag Of Words)です。

ここまでの話だけだと抽象的過ぎてわかりにくいので、具体的なケースに基づいて振り返ってみます。

==========================
◆元文書
文書1 私の名前はジョンだ。
文書2 私は車を買った。ジョンはそれを羨ましげに見ている。
文書3 ジェファーソンは私に対して腹を立てている。
==========================

上記の三つの文章があった際に、それぞれの文章に対してmecabを用いて形態素解析を行うと、

==========================
◆形態素解析後
文書1 私|の|名前|は|ジョン|だ。
文書2 私|は|車|を|買っ|た。ジョン|は|それ|を|羨まし|げ|に|見|て|いる。
文書3 ジェファーソン|は|私|に対して|腹|を|立て|て|いる。
==========================

のようになります。図2はこの形態素解析結果をBOWの形に変換したものです。(助詞、助動詞は意味をなさないことが多いのでここでは一度省きました。)

このように作成したBOWという文書と単語の行列を用いて、様々な統計解析の手法を行うことができます。次回では、よく使われている手法である、「TFIDF法」、「LSI」、「LDA」の三つの手法について解説します。

トリビア(読まなくても次回以降は理解できます)

以下は、上でも紹介した、

http://chasen.naist.jp/chaki/t/2009-09-30/doc/mecab-cabocha-nlp-seminar-2009.pdf

から、面白いと思ったことをトリビア的に抜粋しました。

・研究変遷

形態素解析については、様々なツールがこれまでに開発されており、奈良先端科学技術大学院大学の松本研究室で開発された”ChaSen”や前述の工藤氏が開発した”MeCab”などが有名です。


出典: http://chasen.naist.jp/chaki/t/2009-09-30/doc/mecab-cabocha-nlp-seminar-2009.pdf

上記が形態素解析の研究の変遷になります。それぞれの違いなどについて詳しく知りたい方は元資料の方を参照下さい。

・コストの決定方法

90年代始めのJUMANの時代は、辞書作成をなんと人手で行っていたそうです。単語の数は膨大だから、それに一つ一つコストをつけていくと考えるとなんとも凄まじい作業ですね。客観的な評価が難しいから試行錯誤の連続だったようです。

さすがにそれは大変だということで、最近では大量の生テキストに対し正解データを人手で作成し、データから推定ということを行っています。

ちなみにmecabではCRF(Conditional Random Fields)というアルゴリズムが用いられています。計算方法は元資料の19~24ページにまとまっているので、ご興味のある方はそちらを確認してみて下さい。

[writer-mieruca]

関連記事はこちら