プログラミングと絵と音楽

コンピューター科学を専攻し、絵と音楽を趣味とするエンジニアのブログです。

質問応答システムの実装と考察:BOWとTFIDFによる検索

まずはシンプルな手法として、文章を語句に分割し、それを比較する計算を行い、最もスコアの高い Wikipedia 記事のタイトルを回答として出力してみようと思います。

ここでは、 Bag of Words と TF-IDF法を用います。

キーワード

  • Bag of words (BOW)
  • TF-IDF

回答の候補となる記事を絞る

これからやる手法では、238万の記事を全部調べるには相当な時間がかかるため、用意した質問の正解となる記事と前後100記事で、約1600の記事に絞りました。現実的な時間で238万記事から正解を導き出すには、PCのスペックを上げたり、複数の計算機で並列に動作させる必要があります。

質問文章の分解

文章を語句に分割します。私は今まで MeCab という形態素解析器を使っていましたが、コマンドライン1行で導入できる janome を使ってみました。

shell$ pip install janome

janomeで単語に分割し、それぞれが何回出現したかと一緒に記録しておきます。

入力

戦国時代の武将であり、本能寺で織田信長を討ったのは誰?

Bag of Words

{'戦国': 1, '時代': 1, 'の': 2, '武将': 1, 'で': 2, 'あり': 1, '、': 1, '本能寺': 1, '織田': 1, '信長': 1, 'を': 1, '討っ': 1, 'た': 1, 'は': 1, '誰': 1, '?': 1}

候補となる記事を抽出

質問を分解した中で出てきた単語と、各記事の文章を分解した中で出てきた単語のうち、共通する単語を含むものを全て回答の候補として抽出します。上記の質問であれば、単語「戦国」含む記事、単語「時代」を含む記事、以下同様というようにです。

しかし、これでは殆どの記事が助詞「で」、「は」などを含んでいるため、それら全てが候補になってしまい、候補が激増してしまいます。

そこで、記事全体のX%以上に含まれる単語は、候補の検索から除外しました。具体的な値は何通りか試しましたが、X=40 (%) だと助詞とかがちょうどよく消えてくれました。

スコアの計算

検索した各記事に対して、類似度を計算します。

記事のそれぞれの単語 w_i について、次のようにTFとIDFを計算します。

Term Frequency

式だと次のようになります。
\displaystyle \mathrm{TF}(w_i) = \frac{w_i}{\sum w_i}

例えば、全部で100単語からなる文章で、「りんご」という単語が3回出てくる場合、「りんご」のTFは3/100ということになります。

これは、同一文章でよく現れる単語は重要度が高いという概念の数値化です。

Inverse Document Frequency

 \displaystyle \mathrm{IDF}(w_i) = \log \frac{D}{| \{ d\, | \, d \ni w_i \} |}

Dは記事の全体数、dは各記事になります。対数の中の分母は、単語w_iを含む記事数です。

例えば、今回使う1600記事の中で、「りんご」という単語が31記事に含まれていた場合、「りんご」のIDFはlog(1600/31)となります。

これは、特定の記事でしか出ない珍しい単語ほど重要度が高いという概念の数値化です。
一例として、助詞「で」「は」などは沢山の記事で出現するため、値が小さくなります。

コサイン類似度

各文章を、各単語を一つの次元とするベクトルとみなし、次の計算をします。

\displaystyle \cos{\theta} = \frac{\overrightarrow{q}\cdot \overrightarrow{e}}{|\overrightarrow{q}||\overrightarrow{e}|}

この cos θ の値をスコアとします。

実験

さて、質問を入力してみましょう。

> 戦国時代の武将であり、本能寺で織田信長を討ったのは誰?

スコアの上位5つが次のようになりました。

明智光秀 0.1510266237438856
1559年 0.13835019894259815
藤堂高則 0.1237466003784546
大永 0.11303296823717446
今川義元 0.10349135728955096

約1600記事の中のランキングではありますが、明智光秀を回答候補の1位として得ることができました。これは理想的な結果です。

もう一つ質問を入力してみます。

> 任天堂が2017年3月3日に発売した、据置でも携帯でも使えるゲーム機は何?

スコア上位5つ

コンピュータゲーム 0.28347233252398524
ゲーム 0.2329463227350586
Nintendo Switch 0.1985601368230161
ゲームのタイトル一覧 0.16659560167400825
はむばね 0.09190483488140566

期待した回答である Nintendo Switch は3位にきました。他の候補は、ゲームの中でも抽象的な単語が来ています。これは理想的な結果ではありません。

今後の課題

時間がかかる

一つの質問をするだけで1分以上かかってしまいます。約1600記事でこれですから、全体の238万記事になると現実的な時間で終わりそうにありません。

今の動作環境が 4 core 2.5 GHz, 4 GB RAM で貧弱であるのもありますが、現実的な拡張でも速度2~8倍が限度だと思いますので、アルゴリズムを根本的に変える必要があります。

文脈を考慮できていない

質問文を単語に分割し、比較するという手法をとっています。BOWでは順番などは考慮されていないため、語の形容や、主述の関係は消滅しています。これにより、例えば、織田信長を討った明智光秀か、織田信長が討った今川義元かを判別できません。連続するn語を塊として考えるn-gramというのもありますが、それで大幅に精度が向上するかは微妙なところです。

表記ゆれを考慮できていない

現状、表記ゆれを考慮していません。例として、「1000」と「千」などを同じにすべきなのか、別のものと考えるのかも困難な課題です。どちらも数値であれば同じものとしても良さそうですし、漢字の方が名前の一部であれば別のものと考えるべきです。

記事のタイトルしか回答候補に挙がらない

例えば、「1/10」という記事はありますので、「1割はいくら」という質問には正解できる可能性がありますが、「8%」というタイトルの記事はありませんから、「元号が令和に変わったときの消費税率はいくら?」という質問に正解できることはありません。

次にやること

上記の課題点を考慮し、別のアルゴリズムでの実験をしてみます。