クロスエントロピーで名前から国籍判定するクロスエントロピーで名前から国籍判定する2017-05-20|情報理論,自然言語処理scouty代表の島田です。「競合優位性に関わる技術でない限り技術情報をオープンにしていく」というポリシーのもと、今回は、scoutyのサービス内で実際に使われている、「名前の文字列からその人の国籍を判定する」というアルゴリズムを紹介します。初回ということもあり、非技術者の方にもわかりやすくscoutyで使っている技術をご紹介したいと思います。平たく言うと、今回ご紹介するのはアルファベットで表記された名前の文字列を受け取って、その名前の人物の国籍を推定するというアルゴリズムです。下記のように動作します。上記の例は英語圏の名前か(English)日本の名前(Japan)かを判定しています。判定)も判定できますが、今回は割愛します。表示される仕様になっています。"Unknown"が返されています。ネット上に自分の国籍(人間にとっては自明だったりするので)をアップしている人は多くはありません。scoutyはオープンデータから情報を取っているという性質上、scoutyサービスでは国籍を自動的に予測しなければ膨大なデータから日本人をフィルタリングすることはできません。この技術は下記のような検索時に実際に使われています。見立てその言語モデルを作り、そのモデルで与えられた名前の生起確率を計算し、それをもとに判定を行なう」というものです。基礎を復習しましょう。言語モデルとは、「その言語において与えられた単語や文(章)が発生する確率を与えてくれるもの」です。pen."という文章なら、前者の方が発生確率が大きいはずです(後者は文法のミスがあるので)。pen)$$と表せます。この確率を与えてくれるのが言語モデルで、上の例のように言語モデルは文法チェックやスペルチェックに使われます。1つの文の生起確率は、下記のように分解して考えることができます。"this"のあとに"is"が続く確率を表していて、これらをすべて掛け合わせることで、その文の生起確率が計算できます。上記を名前に応用してみます。英語の名前でつくった言語モデルです。英語の名前で起こりやすい文字列に対して、高い確率を返します。P_e(y|d)$$と表せます。この例からわかるように、ひとつの名前の生起確率は、それを構成している各文字の連続の生起確率によって表されます。P_j(y|d)$$となります。実際に作ってみるどうやって言語モデルを作るか?この言語モデルをどう作るかというと、極めてシンプルで、ただ教師データの中に出てきたサンプル数の数で割り算をするだけです。単純に下のように求められます。"dy"が現れた数、"d"が現れた数です。(実際は分母や分子が0の場合を考えてSmoothingという処理をかける必要がありますが、割愛)このようにしてすべての2文字の組み合わせについてこの確率を計算し、保存したものが言語モデルにほかなりません。(組み合わせが膨大なので、学習には時間がかかります。)実際、Ngram以外にも言語モデルを作るやり方はたくさんあります。ような数字を得るため、日本人の名前を大量に集めたデータと、英語圏の人の名前を大量に集めたデータが必要になります。scoutyは、オープンデータから情報を取得しているので、そこに蓄積した情報を使って教師データを作成しました。いる人の名前集合」を作成しました。これは厳密には国籍ではない(日本在住の外国人もいるかもしれない)ですが、データ量を増やすことでそういったノイズを軽減し、近似することができます。今回は、英語圏と日本合わせて約8万件のデータを使って学習しました。言語モデルはただの生起確率を表しますが、もう少し良い指標があります。それがエントロピーです。-P(x)\log_2{P(x)}$$と表されます。数式は直感的でないですが、エントロピーは不確かさの尺度を表します。エントロピーを利用したほうが計算がしやすくなります。1)の掛け算が続くので、生起確率は小さくなります(エントロピーは大きくなります)。それでは本質的ではないので、これを名前全体の文字数でならした指標を使います(※定義ではありません)。それがクロスエントロピーです。クロスエントロピーはもちろん、言語モデルによって変わります。名前中の\(i\)番目の文字にあたります。言語モデルAでのクロスエントロピーが大きいほど、その名前がその言語Aで起こりにくいことを示します。従って、クロスエントロピーがある一定のしきい値より低いかどうかで、その名前がその国籍かどうかを判定します。(あるいは、複数のモデルでエントロピーを計算して、その値が最も小さいモデルの国籍だと判定することもできます。今回の記事ではコードを公開することは趣旨とは異なるので、簡単に実装方針に触れるだけに留めておきます。いうクラスを使うことで、比較的簡単にNgramによる言語モデルを実装することができます。entropyというメソッドを使って言語モデルに対してクロスエントロピーを計算することもできます。日本人の名前で言語モデルを作成し、エントロピーの閾値を設定してそれ以下なら日本人、それ以外なら外国人と定めます。閾値は、サービスの誤判定に対する許容度に応じて、ヒューリスティックに設定します。低ければ低いほど精度は上がりますが(Precisionは上がるがRecallは下がる)Unknownと判定されることが多くなります。英語圏の人の名前でモデルを作り、同様に計算することで判定アルゴリズムを作ります。複数のモデルの結果を使って、判定器を作ります。上記のアルゴリズムの精度を検証してみます。日本にいる人1000件とアメリカ・イギリスにいる人1000件のデータ2000件でテストした結果です(データに偏りをなくすため同一数でサンプリング)。教師データは、モデルを作った手法と同じように、Locationで作成している上、テストデータにはニックネームも多く含まれているので、あくまで参考程度の値となります。正:756(うち日本人と判断されたのが385、英語圏と判断されたのが371)Unkwnon:1220誤:24Precision:96.9%Recall:37.8%F:0.537サービスとしてPrecision(適合率)の方が重視されているので、閾値を厳し目にして、わからないものはUnknownに判断するような仕組みにしています。名前以外の情報からも国籍を判定しているので、実際の精度はこの値よりも高くなります。これからやろうとしていることscoutyでは、今回の記事で紹介したこと以外にも、今後以下のようなことにチャレンジしていきます。別なモデルとの精度を比較すること。場合によっては違うモデルを複合させたほうが精度が出るかも。N-gram以外の手法(RNNなど)で言語モデルを構築し、本手法と比較すること。終わる名前が多いといった特徴があるので、同じ原理を使えば、日本人の名前から性別推定も可能。名前だけではなく、投稿の言語や投稿のロケーションにより国籍を特定すること。言語モデルとエントロピーを使う方法は、手法としては新しくはないですが、学習モデルを変えることによりいろいろなことに応用ができるので、実用では非常に有用です。LABでは、このようなことを継続的に行って、競合優位性に関わる技術でない限りオープンにしていこうと考えています。scoutyでは上記のような技術課題にチャレンジしたいという機械学習エンジニアを募集しています。