人工無脳は考える
Google Could Platformでチャットボットを動かそう

アルゴリズムの分解

2018/03/24

今回のチャットボットのアルゴリズムはコーパスの中から最も似ている行を見つけ、 その次の行を返すというものです。いっぺんに考えようとすると複雑ですので、 これを次のように分解してみましょう。

すると、このアルゴリズムは「二つの文字列の類似度を算出する」方法があれば何とかなりそうだとわかります。 数学的には文字列を何らかの方法でベクトルとして表すことができれば類似度を計算することができます。 従って、先ほどの分解結果を改めて書いてみると以下のようになります。

  1. コーパスの各行をベクトルに変換する
  2. ユーザ入力を同じ方法でベクトルに変換する
  3. コーパス各行のベクトルとユーザ入力のベクトルについて類似度を計算する
  4. スコアの高い順にコーパスを並べ替える
  5. スコアの最も高い行の行番号 i を調べる
  6. コーパスの i+1 行目の内容を返答として返す
ここまで分解すれば各個撃破できそうです。順番に詳細を検討していきましょう。

1.コーパスの各行をベクトルに変換する

文字列をベクトルに変換するには、単語の個数を列挙する方法がよく知られています。 と言ってしまうと簡単そうですが、それは英語のように単語がスペースで区切られている言語の場合です。 日本語の場合は文字列を単語に区切る前処理が必要で、それには形態素解析や分かち書きと呼ばれる技術を使います。

形態素解析と分かち書き

形態素解析は文を品詞ごとに分解し、それぞれを動詞や名詞に分類する手法で、 日本語用では茶筅やmecabが有名です。mecabを用いると以下のような情報が得られます。

~$ mecab
様々なお祝いのシーンで喜ばれるフラワーギフトです

様々	名詞,形容動詞語幹,*,*,*,*,様々,サマザマ,サマザマ
な	助動詞,*,*,*,特殊・ダ,体言接続,だ,ナ,ナ
お祝い	名詞,サ変接続,*,*,*,*,お祝い,オイワイ,オイワイ
の	助詞,連体化,*,*,*,*,の,ノ,ノ
シーン	名詞,一般,*,*,*,*,シーン,シーン,シーン
で	助詞,格助詞,一般,*,*,*,で,デ,デ
喜ば	動詞,自立,*,*,五段・バ行,未然形,喜ぶ,ヨロコバ,ヨロコバ
れる	動詞,接尾,*,*,一段,基本形,れる,レル,レル
フラワー	名詞,一般,*,*,*,*,フラワー,フラワー,フラワー
ギフト	名詞,サ変接続,*,*,*,*,ギフト,ギフト,ギフト
です	助動詞,*,*,*,特殊・デス,基本形,です,デス,デス
EOS

分かち書きも同じように文を分解しますが、品詞の情報は得られません。

  マリーさんが外から呼ぶ声が聞こえる。返事をして庭に出ると、そこには二匹の猫がいた。

  マリー | さん | が | 外 | から | 呼ぶ声 | が | 聞こえる | 。
  | 返事 | を | して | 庭 | に | 出る | と | 、 | そこ | に | は | 二 | 匹 |
   の | 猫 | が | い | た | 。
 

今回はGAEスタンダード環境で作動することが条件で、かつ品詞の情報は当面使わないので、 Tinysegmenterという軽量かつネイティブコードを使わない分かち書きツールを利用します。

さて、以下の小さいコーパスをベクトル化してみます。

  アボカドのサラダ美味しいね。
  美味しい美味しい。サルサソース、いいね。
  フランスパンにもいいよ。
まずはこれを分かち書きします。
  アボカド の サラダ 美味しい ね 。
  美味しい 美味しい 。 サルサ ソース 、いい ね 。
  フランス パン に も いい よ 。

次にどの単語が何回現れるかを数えて行列にします。これを単語の出現回数行列と呼ぶことにします。

表 1. 出現回数行列
サラダアボカド美味しいサルサソースいいフランスパン
1111011100000000
2001121211100000
3000000100111111

この行列の列にはコーパスに出現する単語が全種類ならんでいます。大きなコーパスになると、 単語の種類は数千を超えても不思議はありません。ところが一つの行には数十の単語しかないわけなので、 この行列の全体を見ると大部分は 0 が並んでいるスカスカの行列になりそうです。メモリを食う効率の悪い表現方法と言えるでしょう。また元のコーパスの一行目をもう眺めてみましょう。 言葉の順番をランダムに入れ替えてみても得られる出現回数行列は変わりません。つまりこの方法では文における単語の並び順は情報として扱えないのです。 日常会話で言葉の順番を入れ替えてしまうと全く通じません。それでも問題にならないのでしょうか?今のところは、そういった特徴のある計算方法であることをとりあえず覚えておいてください。

次に、大きなコーパスから同じように単語の出現回数行列を作ったとすると、「美味しい」のように有用そうな単語がカウントされている一方「、」「も」「よ」 のように出現頻度がとても高いのに単独では意味がとれないノイズのような単語がたくさん混在していることがわかります。 ノイズ成分の方が有用な成分よりも多くなると、ちゃんとした検索結果を返しにくくなっていきます。 それでは有用な単語を残してノイズを軽減するにはどうしたらいいでしょうか。

TF-IDF

一般的には「を」とか「など」のようなありふれた単語ほど価値が低く、「サッカー」のように希少な単語ほど持っている情報の価値が高いと言えそうです。 TF-IDFはこのような単語の希少性を価値と読み替えて価値の高い単語を強調して扱う方法です。表1を見てください。 希少なものがたくさんあれば(a)、希少なものが少しだけある(b)のに比べて高いスコアであるべきなのは直観的にわかると思います。 同様にありふれたものがたくさんあれば(c)、ありふれたものが少しだけある(d)のに比べて高いスコアであるべきです。 そして、ありふれたものがたくさんある(c)よりも、希少なものがたくさんある(a)方がやはり高いスコアであるべきなわけです。

表 2. 希少性と頻度
(a)希少なものがたくさん(b)希少なものが少し (c)ありふれたものがたくさん(d)ありふれたものが少し
スコア大 ← → スコア小

さて、tfidfはtfとidfの単純な積で表されます。

ある単語が希少かどうかは一つの文を見ても分からないので、コーパス全域でその単語がどれくらい出現するかを考えます。 具体的にはコーパスに登場する単語tについて、文章頻度 Document Frequency (df)を以下のように定義します。

dfは 0 < df < 1 の値をとり、小さいほど希少であることを示します。今回は希少なほど高いスコアを与えたいので、dfの逆数(逆文書頻度 Inversed Document Frequency (idf))を利用します。

この式ではlogをとっていますが実際にはいろいろな形の式が考案されていて、それぞれの課題に一番高い性能を示したものが選ばれています。

単語の出現回数の方は単語の出現頻度 Term Frequency (tf)に置き換えます。 dfでは希少性を0~1で与えましたが、上の出現回数行列では長い文になるほど単純に出現回数が大きくなってしまい、 tfidfの計算でdfの項が効きにくくなってしまいます。そこで出現回数を文の長さで規格化して、それを防いでいます。

以上でtfidfの計算ができるようになりました。先ほどの例でためしに計算してみましょう。計算中は元の単語が何であったかを振り返る場面はありません。このコーパスは一行を一文書とします(文書数=3)ので、 各列について非ゼロである値の個数を3で割った数がdfになります。一列の出現回数の合計を3で割った数ではありません。

表 3. df, 出現回数行列tc
df0.330.330.670.330.670.671.000.330.330.670.330.330.330.330.33
tc1111011100000000
tc2001121211100000
tc3000000100111111

idfはdfの各数値をlog(1+1/df)としたものです。例えば df=0.33 のとき、idf=log(1+1/0.33) = 0.602 などです。

表 4. df, idf, 出現回数行列tc
df0.330.330.670.330.670.671.000.330.330.670.330.330.330.330.33
idf0.600.600.400.600.400.400.300.600.600.400.600.600.600.600.60
tc1111011100000000
tc2001121211100000
tc3000000100111111

tfは単語の出現回数をその行の出現回数の和で割ったものです。

表 5. df, idf, tf行列
df0.330.330.330.330.670.671.000.330.330.670.330.330.330.330.33
idf0.600.600.600.600.400.400.300.600.600.400.600.600.600.600.60
tf10.170.170.1700.170.170.1700000000
tf2000.100.100.200.100.200.100.100.1000000
tf30000000.14000.140.140.140.140.140.14

最後に各tfの値とidfの積を計算します。

表 6. df, idf, tfidf行列
df0.330.330.330.330.670.671.000.330.330.670.330.330.330.330.33
idf0.600.600.600.600.400.400.300.600.600.400.600.600.600.600.60
tfidf10.100.100.1000.070.070.0500000000
tfidf2000.060.060.080.040.060.060.060.0400000
tfidf30000000.04000.080.080.080.080.080.08

得られたtf行列(表 5)とtfidf行列(表 6)を比べると、tfの一行目(tf1)は0.17と0だけが並んでいて登場する単語はすべて1つずつだということが分かりますが、 tfidfの一行目(tdidf1)は列によって値が異なります。このように単語ごとの価値によって重み付けがされるわけです。

まとめると、この章では日本語の文字列をベクトルに変形する方法を検討しました。 そこでまず分かち書きを行って文字列を単語にわけ、TF-IDF行列を計算しました。TF-IDF行列の行はコーパスの各行に対応していて、行の成分が文字列の表現になっています。 例に用いたコーパスの場合、「アボカドのサラダ美味しいね 。」という文字列は(0.10,0.10,0.10,0,0.07,0.07,0.05,0,0,0,0,0,0,0,0)というベクトルに変換されました。

2.ユーザ入力を同じ方法でベクトルに変換する

基本的にはこれまでと同じ手順で計算を行います。しかしユーザから入力される文字列はコーパスに含まれる単語だけでおさまっているとは限りません。先ほどのコーパスの続きを想像して、

  アボカド の サラダ 美味しい ね 。
  美味しい 美味しい 。 サルサ ソース 、いい ね 。
  フランス パン に も いい よ 。
  サルサ ソース ?

と答えが返ってきたら、コーパスにない"?"をハンドリングする必要が出てきます。 コーパスにこの行を加えてtfidf行列を計算しなおす手もあるのですが、入力のたびに巨大な計算を実行するのは効率的ではありませんし、 そもそも新しい単語について他の行の成分はすべて0と同じですから類似性の優劣を比較してもあまり意味はありません。 そこで、運用時はコーパスに既存の単語だけについてtfidfを計算するなどの工夫が必要になります。

3. コーパス各行とユーザ入力の類似度を計算する

コーパスのある行とユーザ入力という二つの文字列の類似度を求めるという問題は、 TF-IDF行列の導入によって二つのベクトルの類似度を求めるという問題に置き換えることができました。 以下、簡単のため2次元ベクトルで類似度を求める方法を検討します。

図1 Xに似ているのはAかBか

図1のベクトルXに対してベクトルAとベクトルBのどちらがより似ているかを表す方法に、 cos類似度があります。cosθは以下の式で定義されます。ここでABはAとBの内積、||A||はAの長さ(またはNorm)を示します。

cosθは二つのベクトルのなす角によって変化する関数で、ベクトルの向きが一致していれば1、90°なら0、真逆だと-1の値をとります。 ということは、cosθ類似度ではベクトルの長さは考慮しないということです。図を見るとXと長さが近いBの方が短いAよりもビジュアル的に似ているような気もしますが、 それでよいのでしょうか?

ベクトルの長さが有利に働く他の類似度もあります。例えば内積ABです。極端な例として(2,5)と(1200,500)の内積は 2×1200 + 5×500 9900 のようになり、 大きなベクトルになると向きが多少違っていても大きな値になってしまいます。文字列に読み替えると、長い文字列同士ほど内容と関係なく一致しやすくなることになります。一方cosθは内積を各ベクトルの長さで規格化したもので、行の長さの影響を受けにくくなっていると言えます。

HOME ◀ 2 PREV NEXT 4 ▶

人工無脳は考える by 加藤真一 2016-2018