scouty AI LAB

HR TECH・AI企業であるscoutyが、自社で利用しているAI技術や話題のAIテクノロジーを紹介していきます。

ニューラルネットによる構文解析 ー Dependency Parsingについて

scouty代表の島田です。 実はscoutyではサービス上で実用するに至れていませんが、技術選定の段階で調査したので、最近人気も出ているニューラルネットによる Dependency Parsing についてまとめてみました。 前半は、自然言語処理の基本となる大きな流れに関しても触れていますので、NLPに詳しくなくてもご理解いただけると思います!

自然言語処理の基礎:意味解析とは?

f:id:scouty:20170908171350p:plain

そもそも自然言語処理といってもいろいろな分野があります。ミクロな部分に入る前に、まずは全体の流れを理解しましょう。 自然言語処理は、大まかに上の図のような流れになっています。これは日本語に限らずどの言語にも通ずる一般的なプロセスになっています。各プロセスは次の通りです:

  • 形態素解析:まずは、与えられた文章の単語を分かち書き、品詞を推定する(厳密には、品詞だけではなく時制なども判断します。)
  • 構文解析:品詞の上位に存在する主部・述部・名詞句・動詞句などの構造を発見する
  • 意味解析:文内の主体や動作の対象はなにかという意味を推定する

つまり、自然言語処理における構文解析とは、単語ごとの粒度で文章に木構造のような意味解析を行うのに都合の良い構造を見出すことです。 最も代表的かつ一般的な構文解析は、次の図のような文の構成要素(名詞句・動詞句・・とか)・品詞に基づいた構文解析でしょう。これは文脈自由文法(「文→名詞句 動詞句」「名詞句→冠詞 名詞 | 代名詞 | ..」のような生成規則を逆向きに適用して木を作る)を使って構成されます。

スクリーンショット 2016-04-08 17.29.15

Dependency Parsing とは?

構成要素ベースの構文解析では名詞句・動詞句のような構成要素を仮定しなければいけませんが、これは完全に言語依存で、言語によっては存在しない構成要素や品詞がある(日本語には冠詞や前置詞が無いとか)ため、言語横断的に適用することができません。

 

スクリーンショット 2016-04-08 17.43.11

そこで使えるのが上のような Dependeny Parsing (DP) です。Dependency Parsing は文中の依存関係 Dependency に基いて構文解析を行います。これの何が有益かというと、構文解析下流工程である意味解析が非常に行いやすいことです!つまり、例えば動詞の部分では関係に方向がついているので、何が動作の主体で何が客体か、などのような関係を捉えやすい。

ただし、Dependency Parsing においては、以下の3つの条件を満たすことが約束されなければいけません:

  1. 各ノード(単語)の流入エッジは必ずひとつでなければいけない(流出エッジは何個でも良い)
  2. よって非環式である(循環閉路がない)
  3. 連結グラフである

なお、上のように表した時に枝が交差しないように描けるとき、その Dependency Tree は Projective(投影性?)である、と表現します。英語に対する Dependency Tree は基本的に Projective になります(が、他の言語では成立しないことがある)。

 

ニューラルネットによる Dependency Parsing

Dependency Parsing の手法として、最大全域木問題(Maximum Spanning Tree)を解くことで Dependency Tree を求めるという非ニューラルネットな手法があります。つまり、スコア(あらかじめ人間が作ったスコアのルールに基いて木にスコアをつける)を最大化する木構造を探し、それを Dependency Tree とする方法(2005年頃にアルゴリズムができている)がありました。しかし、これは人間が作ったルールに基づくので恣意的であり、そのルールに性能が依存する上それは言語依存の部分があるので、近年(2014年頃)ニューラルネットワークで自動的に Dependency Parsing を行う手法が提案されました。

それは MALT パーサーと呼ばれていて、基本構造はよくコンパイラなどで使われるのと同じ Shift-Reduce 型のパーサーです。つまり、下図のように文頭からスタックにどんどん単語を追加していき(SHIFT)、Dependency を発見したらスタックから単語を取り除いて(REDUCE)A に Dependencyを 追加する(A は Dependency の集合)という仕組みです。 スクリーンショット 2016-04-08 21.08.13 遷移(Transition: SHIFT か REDUCE かの判断)は手作りの特徴とルールに基いて行われるのが伝統的なやり方でしたがが、これをニューラルネットワーク(NN)によって自動化しよう、というのが ニューラルネットワーク による Dependency Parsing の基本的なアイディアです。

 

基本構造:もう少し詳しく

学習の目的は $i$ 番目の正しい遷移 $t_i\in T$ を予測することであり、その際に使えるのは以下のような情報です。なお、これらを configuration ($c_i$)と表します。

  • 対象単語とその品詞
  • Dependency の矢印の先の単語と、そのラベル
  • スタックとバッファでの単語の位置

これをニューラルネットによって判断するにはどうすればよいでしょうか? 単純に、それらのベクトル表現をすべてくっつけたものを入力にしてやれば良いのです!

ss

つまり、入力ベクトルは $[\boldsymbol{x}^w, \boldsymbol{x}^t, \boldsymbol{x}^l ]$ となり(それぞれ順に単語・品詞タグ・枝ラベル)、隠れ層は以下の式で表されます:

$$\boldsymbol{h} = {(\boldsymbol{W}^w_1\boldsymbol{x}^w+\boldsymbol{W}^t_1\boldsymbol{x}^t+\boldsymbol{W}^l_1\boldsymbol{x}^l+\boldsymbol{ b}_1)}^3$$

面白いのは、活性化関数に3乗(立方)を使っていることです。NNでは一般的ではありませんが、このタスクでは一番性能が良かったようです[1]。 出力レイヤーは通常通りソフトマックスを用います。出力レイヤーの次元数は遷移の数(ラベルも加味した遷移なので、SHIFT と REDUCEの2種だけということではなく、REDUCE の場合は上図のように LEFT-ARC (n-subj) や LEFT-ARC (amod) など、結構多い)で、一番値の大きかったノードの遷移を選択する、という仕組みです。

単語・品詞タグ・枝ラベルはすべて埋め込み表現 (embedding. 分散表現の一種) で表されている。品詞タグの分散表現というのは、単語の類似度と同じように例えば「"複数名詞"は"冠詞"より"単数名詞"に近い」などのような類似度が反映されたベクトル表現のことです。ただし、この embedding は通常の単語表現の embedding とは異なり、対象単語だけではなくスタック・バッファ内の数語を混ぜあわせて作られた表現です。詳しくは[1]参照。 品詞を embedding として表現してしまうの発想として新しいですね。品詞を one-hot として表すよりも。類似度も定義できるので精度が上がりそうです。

正しい遷移とconfigurationのペア $(c_i, t_i)$ のデータセットから得て、入力 $c_i$ から出力 $p_{t_i}$ を順伝播で作成し ($p_{t_i}$ は遷移 $t_i$ が起こる確率)、誤差を次の式で計算します(普通のクロスエントロピー)。

$$L(\theta)=-\sum_i\log p_{t_i} + \frac{\lambda}{2}||\theta||^2$$

$\theta$ はパラメータ、二項目はL2正則化項、学習方法は普通のNNと同じバックプロパゲーションを使います。

 

まとめ

スクリーンショット 2016-04-08 22.38.05

[1]から引用したパーシングの結果は上の表の通りです。 伝統的なMALTパーサー(人間のてづくり特徴ベース)よりも、過去のいずれのパーサーよりも良い結果(遅いですが……)を出しているのがわかります。

また、今回は扱わないですが、上述の最大全域木 MST ベースのパーサーの(特徴ベースでなく)NN 版もあるようです(これは2015年に出たもので、比較的新しい)。 ニューラルネットDeep Learning(本例は1層なので深層ではないが)が人間のつくった特徴量ベースの手法を蹂躙するという構図は画像認識の領域のみならずいろいろなところで起こっているということが理解できますね。 scoutyでも、高度な意味解析を要する場面では今後使っていく可能性は高いですね。

 

参考文献

[1] Chen, Danqi, and Christopher D. Manning, 2014, A fast and accurate dependency parser using neural networks, In Proceedings of the Conference on Empirical Methods in Natural Language Processing, 740–750. Doha. http://cs.stanford.edu/people/danqi/papers/emnlp2014.pdf

トピックモデルで単語の分散表現 – 実装編

scouty代表の島田です。 前回の記事 トピックモデルで単語の分散表現 – 理論編 では、トピックモデル・LDA(Latent Dirichlet Allocation)の基本構造とアイディアを、非エンジニアにも比較的わかりやすく説明しました。 今回はPythonで実際にトピックモデルを使って単語の分散(ベクトル)表現を作ってみます。エンジニア向けの記事ですが、最後の性能比較の部分はエンジニアでなくても、前回紹介した「分散表現」と「局所表現」の違いが理解できるかと思います。

 

自然言語処理ライブラリgensim

今回はフルスクラッチではなく、LDAやLSAやWord2vecが簡単に使えるPython用ライブラリgensimを利用します。gensimは、scoutyの実際のシステム内でも使われています。 gensimをインストール後(インストール方法は本家のWEBサイトを御覧ください)、

from gensim.models.ldamodel import LdaModel

でgensimのLDAModelをimportします。

以下の関数は、単語の共起表現ベクトルのリストvectorsを受け、gensimの関数LdaModelを用いてLDAモデルを学習(これにはデータサイズに依るが数十分の時間がかかります)し、指定したmodel_nameでモデルを保存する関数です。

def lda(vectors, word_mapping, model_name):

    # Convert to sparse vectors
    sparse_vectors = [convert_to_sparse(vector) for vector in vectors]

    trained_model = LdaModel(sparse_vectors, num_topics=NUM_OF_TOPICS, id2word=word_mapping, update_every=0)

    print("Saving Model to {0} ..".format(model_name))
    trained_model.save(model_name)

    return trained_model

第一引数のvectors、第二引数のword_mappingの形式は、以下のようになります。

word_mapping = {0: "have", 1: "get", 2: "house", 3: "home"}
vectors = [[0, 10, 12, 3], [10, 0 11, 5], [12, 11, 0, 21], [3, 5, 21, 0]

vectorsは共起表現を表す2次元ベクトルです。各単語が他のどの単語と一緒に生起しやすいかを、回数で表します。 vectorsの各行が各単語を表していて(これがトピックモデルでいう「文書」に対応します)、各列がその行の単語と各インデックスの単語との共起回数を表します。つまり、i 行 j 列目はインデックスi の単語とjの単語の共起回数ということです。たとえば、上の例では、ID0のhaveとID1のgetの共起回数は10回、という具合です。

このデータは文書集合から自分で作るも良し、どこかのソースから取ってくるもよし、とにかく自分で用意しなければいけません。(つまりここではLDAはベクトルの次元縮約として働く、というわけです) このベクトルは当然スパースになるので、gensimではスパースコーディングで渡す必要があります。つまり、0でない成分のインデックスとその成分の組のリストとして渡します。つまり、[1,0,0,4,0,0,8]は[(0,1), (3,4), (6,8)]と表されます。

word_mappingはオプションで、キーが単語ID、バリューが単語となっているディクショナリです。 トピックベクトルを表示するときなどに単語を表示させることが出来て便利 という程度のものなので面倒くさければ必要ありません。

普通のリストをスパースコーディングに変換する関数は、例えば以下のように書けます。

def convert_to_sparse(dense_vector):
    is_sparse = lambda vector: isinstance(vector[0], tuple)
    if not is_sparse(dense_vector):
        return [(i,v) for i,v in enumerate(dense_vector) if v > 0]
    else:
        return dense_vector

LdaModelのnum_topicsに指定するのはベクトルの次元数(=トピック数)で、大きければ表現力は上がる一方オーバーフィットしやすく計算量は増すので、100〜300くらいがちょうどよいでしょう。

gensimのLdaModelオブジェクト標準のメソッドsaveでモデルが保存できるので、一度学習して保存しておけば次回以降はすぐに読み込んでモデルを利用することができます。便利!

 

類似度比較

最も簡単な応用例として、類似度比較を試してみます。今回は得られたベクトルを使って単語 home, house, timeの類似度を測ってみました。類似度は次のコサイン類似度を用いています。(この類似度が大きいほど両者の単語が似ているということ)

$ cos(\boldsymbol{u}, \boldsymbol{v}) = \frac{\boldsymbol{u}\cdot\boldsymbol{v}}{|\boldsymbol{u}||\boldsymbol{v}|} $

以下がLDAの結果(トピック数100)です。

Similarity between house.n and home.n is 0.432761038721
Similarity between house.n and time.n is 0.248780840955
Similarity between home.n and time.n is 0.21364984806

直観に違わず、homeとhouseの類似度がtimeとhouseの類似度を大きく上回っていることがわかります

ちなみに、学習に使った共起表現の生ベクトル vectors(ボキャブラリーサイズ=ベクトルの次元数=2000)で同じく類似度を計った結果が以下です。

Similarity between house.n and home.n is 0.812743856464
Similarity between house.n and time.n is 0.82359219053
Similarity between home.n and time.n is 0.818144793373

ベクトルが長く、スパース過ぎて0がほとんどなため、コサイン相関だと差がほとんど表れません。 上2つを比較すれば、いかにLDAの次元圧縮が効いているかわかりますね。

前回の記事 トピックモデルで単語の分散表現 – 理論編 の「局所表現と分散表現」で説明したように、このように局所表現(スパースなベクトル、下の例)だとベクトルがほとんど0で埋まってしまって精度が出にくくなるので、トピックモデルやWord2Vecなどの分散表現が必要、ということですね。

自然言語処理に強いエンジニア募集!

scoutyでは、上記のようなトピックモデルやWord2vec, Doc2vecやRNNとアテンション、といった自然言語処理を使って退職率予測アルゴリズムや企業と人のマッチングアルゴリズムをつくる機械学習エンジニアを探しています! Pythonでバリバリ自然言語処理を使ってサービスに使っていきたいと考えている方がいたら、一度お話しましょう! www.wantedly.com

トピックモデルで単語の分散表現 - 理論編

こんにちは。代表の島田です。 最近はDeepLearningがホットなキーワードになっていますが、トピックモデルという自然言語処理における手法も、少し前に注目を集めました。聞いたことはあるけど何なのかわからない、という方のために、今回はトピックモデルに関して説明します。 Pythonなどの言語ではライブラリが利用できますが、トピックモデルなどの原理を知っておくことでパラメータチューニングが思いのままにできるようになります。

LDAやトピックモデルについては最新の技術!というわけではないので他にも解説記事があると思いますが、今回は「流行りの単語がとりあえず何なのか知る」ということを目的に、前半は機械学習エンジニアではない方にもわかりやすく解説しようと思います。

モチベーション

単語をベクトルで表したい!

自然言語データを使ったレコメンドエンジンの構築やテキストの分類などで、単語をクラスタリング(意味の似ているグループごとに分ける)や DeepLearningを使って識別したいというシーンはよく見かけます。 しかし、「りんご」「コンピューター」といった単語そのままという形では、DeepLearningなどのような手法に入力することが出来ません。そこで、コンピューターでもわかるように単語を「ベクトル」という形式に変換してあげる必要があります。その形に変換することで、いろんな分析手法を適用することができますが、その方法は簡単ではありません。研究者によっていろいろな方法が提案されてきました。

f:id:scouty:20170802223219p:plain

局所表現と分散表現

Deep Learningの登場以前は、単語をベクトルで表す方法は、ボキャブラリーサイズ(扱う全単語の数)の次元数を持ち、該当インデックスだけ1で他の値が0というone-hotベクトル(1つの概念を1つの成分で表すので局所表現という)が使われていました。 次に、「もし、2つの単語が似ている文脈(つまりその単語の周りの単語のこと)で使われているなら、その単語は似ている」というDistributional Hypothesis に基いて、単語を、その単語と同時に使われる単語たちの生起回数でベクトル表現する(これは複数の成分で概念を表現しているので分散表現という)という共起表現が現れましたが、この方法でもベクトルの次元が(同じくボキャブラリーサイズなので)大きくなりすぎ、かつスパース(0が多すぎる)になってしまうため問題がありました。

そこで、せいぜい100〜200次元くらいの低次元ベクトルでひとつの単語の意味を表現するにはどうしたら良いか?という問が生まれ、Deep Learningの流行と相まって近年いろいろな手法が生まれました。Word2Vecで使われているSkip-Gramなどは主流ですが、このシリーズ記事では、そのやり方の一つであるトピックモデル(とLDA)を用いて単語の分散表現を作ることについて解説します。今回の理論編では、トピックモデルとLDAの基礎理論について解説します。

f:id:scouty:20170802223205p:plain

 

トピックモデル・LDAとは

トピックモデルは、大雑把に言い表わせば文書にトピック(その文書のジャンル・カテゴリ)を教師無しで割り当てる手法のことです。 トピックモデルにおいては、予め指定しておかなければならない変数はトピックの数のみで、それぞれのトピックが何なのか(「政治」とか「スポーツ」とか)は指定したり登録したりする必要が無いので、非常に便利です。なぜなら、トピックというのは「政治」とか「スポーツ」とかいった人間からみたジャンルではなく、単語の分布として表わされるからです。

cited from [2]

上図([1] より引用)では1番目のTopic(黄色) が gene, dna, genetic という単語をトップに含んでいるトピック(つまり遺伝子関係のトピック)で、3番めのTopic(緑)がbrain, neuron, nerveを含んでるトピック(脳に関するトピック)を表す。左に出ているのがすべてのトピックなら、トピック数は4で、この文書は4次元のベクトルで表されます。

つまり、各トピックは、感覚的には「単語のブレンド」という感じで表されます。そして、各単語は、各トピックにどれくらいの確率で属すか?という「トピックのブレンド」で表されます

LDA(Latent Dirichlet Allocation)とは、トピックモデルに用いられる代表的な確率モデルで、LDAそのものは文書生成モデルです。この確率分布を使って文書にトピックを教師なしで割り当てるのが、トピックモデルです。

 

基本構造:もう少し詳しく

LDAそのものは文書の生成モデルです。つまり、与えられた文書がLDAによって生成されると仮定したときのその文書の生成確率を計算したいために、生成モデルを考える必要がある、ということです。 LDAでは以下の流れで文書を生成します。

  1. 文書の単語数Nとトピックの数Tを決める
    例) N=4, T=2
  2. 各トピック$j$ごとの単語の分布 $\boldsymbol{\phi^{(j)}}$をDirichlet分布$Dir(\beta)$ に従って決める。
  3. 各文書$d$における(単語の)トピックの分布$\boldsymbol{\theta}^{(d)}$をDirichlet分布(ディリクレ分布) $Dir(\alpha)$に従って決める
    例) 1/2 の確率でfoodカテゴリ, 1/2の確率でanimalカテゴリになる分布とする
  4. 以下の手順で文書d内のN個の単語を生成
    1. トピック分布$\boldsymbol{\theta}^{(d)}$に従ってd内の単語のトピックを、T個のトピックの中から1個選ぶ
      例) T1 = food, T2=animal, T3=animal, T4=food
    2. $\boldsymbol{\phi}^{(j)}$に従って、先の手順で選んだ各トピックに基いて文書内の単語を決める。
      例) w1=broccoli, C2=panda, C3=bird, C4=eating

Dirichlet分布はベータ分布の多変数版にあたる分布で、適当なパラメータを与えて分布を生成できるので、確率分布の確率分布として扱われます。一般式は次のように与えられます。

$ P(\boldsymbol{\theta}) = \frac{1}{Z}\prod_{j=1}^K \theta_j^{\alpha_j -1} $

また、表記上、$Dir(\alpha, \cdots, \alpha) = Dir(\alpha)$ と書きます。 $\alpha$は文書中のトピック分布を平滑化する役割を持っていて、小さいほど(0.01~0.1)分布が際立ち、大きいほど(10〜)分布がなめらかになる(トピックごとの確率差がなくなる)。

そして、上でいう$\boldsymbol{\theta}, \boldsymbol{\phi}$は次の学習プロセス、従ってデータから学習することで得ることができます。

  1. 各文書を見ていき、その文書の中の単語をひとつづつランダムにT個のトピックのうちどれかに割り当てる。(初期値として)
  2. 各文書を見ていき、その文書$d$の中の単語$w$と各トピック$t$について、以下を計算する
    • $p(t|d)$: 文書d中のトピック$t$の単語数 / 文書$d$の全単語数。 つまり $\boldsymbol{\theta}^{(d)}_j$ にあたる。
    • $p(w|t)$:トピック$t$内での単語$w$の数 / トピック$t$の全単語数。 つまり$\boldsymbol{\phi}^{(j)}_i$ にあたる。
  3. 手順2で計算した確率の積 $p(w|t) * p(t|d)$ が、 をもとに、$w$に新しいトピックを割り当てていく。
  4. 2の確率が変化しなくなるまで2と3を十分繰り返す。

なんというか、クラスタリングに似ていますね。この手順で最終的に得られた$p(t|d)$と$p(w|t)$は、先に説明した手順の生成モデルで文章が生成されると仮定されたときのトピック分布と単語の分布ということになります。この$p(t|d)$が、文書を表すトピックのベクトル(次元数はトピックの数に等しい)となります。

 

LDAでどう単語の分散表現を作るのか?

LDAは、文書(単語の集合)が与えられた時に、その文書が属するトピックを推測するものでした。従って、クラスタリングに用いられることが多いのですが、これを使って単語の分散表現を作ることもできます。 LDAが文書に対する手法ならば、ある単語の共起表現ベクトル(一緒に使われた回数を格納したベクトル。次元数は単語数)を一つの文書(頻度と同じ数だけ単語が含まれている文章。単語順は考慮しない。)と見立て、それに対しLDAを適用すればよいということです。共起表現ベクトルはそのままだと次元数が巨大過ぎてスパースになりやすいですが、LDAを使えば適当な次元(100~500くらい?)に次元縮約することができる。つまり、トピックモデルをBoWや共起表現ベクトルに使うことによって、次元縮約器としてはたらく、ということになります!

次回記事では、Pythonのライブラリgensimを用いて、この方法によって実際に分散表現を作ることを解説します。

 

参考文献

[1] Griffiths, Thomas L., Mark Steyvers, and Joshua B. Tenenbaum. 2007. Topics in semantic representation. Psychological Review 114(2):211–244.

CNNで文の識別タスクを解く

代表の島田です。 今回は、今後scoutyでもスカウトメールの返信率予測などに利用していこうと考えているCNN(畳み込みニューラルネットワーク)の自然言語処理分野への応用をご紹介します。 画像認識に使われることも多いCNNですが、最近は自然言語処理への応用もさかんです。

 

CNNとは

畳み込みニューラルネットワーク(Convolutional Neural Network:以下CNN)は、画像認識でハイパフォーマンスを叩きだしたことで知られるネットワークアーキテクチャで(1999年ごろから存在はしたが、注目を集めたのは2012年以降?)、画像認識で用いられてきましたが自然言語にも応用することができます。というか、マトリックスを入力とする問題には基本すべて応用できます。

CNN自体を解説したソースは他にたくさんあるので、CNNに関してはそちらを参照するほうが早いでしょう。ただ、ものすごく簡単に言うと従来のニューラルネットワークは下図のようなフルコネクト(隠れ層のどのユニットも入力層のすべてのユニットに接続されている)であり、画像のような2次元の入力も無理やり1次元のベクトルに引き伸ばして扱っていたのに対して、

スクリーンショット 2016-04-16 20.55.32

CNNでは、隠れ層のある一点が入力のある領域に対応しているという重みを持っています。

スクリーンショット 2016-04-16 20.56.01

これによって、平行移動にロバストになるという特徴がある。重みの形からネットワークアーキテクチャまで全く通常のNNと異なります。詳しくは 定番のConvolutional Neural Networkをゼロから理解する - DeepAge などの記事を参照しましょう。

 

CNNを自然言語処理に応用する

畳み込みニューラルネットワーク自然言語処理に応用するには、文をマトリックスに見立てます。つまり、単語を適当な分散表現で表せば単語はすべて同じ次元のベクトルで表せますが、これを単に文に登場する順番に並べてやれば、下図のように文をマトリックスとして表現できるというわけです。

スクリーンショット 2016-04-16 21.02.32

dは単語のembeddingの次元数で、通常はもっと大きいはずですがここでは簡単のため5とします。マトリックスの高さは文の中の単語数と等しくなるので、文ごとにマトリックスのサイズは異なります。

スクリーンショット 2016-04-16 21.07.43

フィルター(重み)を上図のように適当な長さに定めてマトリックスを上からスキャンすることで通常のCNNと同じように特徴マップ(Feature Map)を作ることができます。フィルターのウィンドウサイズ(フィルタリングする領域の長さ、上図では3)は特徴マップごとに変更します。つまり、ウィンドウサイズ2の特徴マップ、ウィンドウサイズ3の特徴マップ、ウィンドウサイズ4の特徴マップ… などのように複数作ることでマップごとに異なる特徴を学習することができます。 ところで、ウィンドウサイズはN-gramのNに当たります。つまり、サイズ2はbi-gram, サイズ3はtri-gramに対応するということですね。 ネットワーク全体のアーキテクチャは以下のような形になります。

スクリーンショット 2016-04-16 21.15.20

フィルター(2列目)と入力(1列目)を畳み込んでつくった特徴マップ(左から3列目)をプーリングし、各プーリング層を連結させてひとつのベクトルを得る。これが文の分散表現Embeddingになります。これの後ろのレイヤーに何層か挟んで、最終出力のレイヤーをクラスの確率分布とすれば、文を入力としてクラスを出力とする識別器をつくることもできます。

 

まとめと性能

[1]の実験によると、CNNによるモデルは、映画レビューや製品レビュー文のセンチメント解析(ポジティブ/ネガティブの解析)において、下図のような結果を出しています。この研究では、CNNを従来の他モデルすべてと比較しています。

スクリーンショット 2016-04-16 21.28.28

MR, SST, TREC, CR ..などは各タスクで、数字が精度(100%中)です。左列がモデルで、上段の4つのCNNは、CNNバージョンの異なるモデルを表しています(たとえば単語の分散表現のモデルの違いや、プリトレーニングの有無など)。7タスク中4つでCNNが最高の成果を出す結果となっています。

つまり、現状文の分散表現にはいろいろなモデルがありますが、2014年の時点ではそれらを含めて基本的にCNNがベスト(あくまでクラス識別問題ですが)である、ということですね。

 

scoutyでの応用例

scoutyでは今後、スカウトメールの文面を今回紹介したような方法でマトリックス化し、

  • そのメールの開封有無
  • そのメールの返信有無
  • そのメールを受け取った人が実際に転職に繋がったか

のようなデータを教師データとして、CNNなどの手法を使って返信率等を予測する、といった事にチャレンジしていこうと思っています。それを使って、スカウトメールの自動レビューや自動添削などに活かして行こうと考えています。 今回紹介したのは単語単位でのCNNですが、日本語の場合だと文字のone-hotベクトルをつなぎ合わせてインプットをつくるという文字単位のCNNもあるようです。言語や問題に応じてどのCNNモデルが適切か、実際のデータを使って比較してみたいですね。

 

参考文献

[1] Yoon Kim, Convolutional Neural Networks for Sentence Classification, EMNLP-2014 http://emnlp2014.org/papers/pdf/EMNLP2014181.pdf

クロスエントロピーで名前から国籍判定する

scouty代表の島田です。
「競合優位性に関わる技術でない限り技術情報をオープンにしていく」というポリシーのもと、今回は、scoutyのサービス内で実際に使われている、「名前の文字列からその人の国籍を判定する」というアルゴリズムを紹介します。
初回ということもあり、非技術者の方にもわかりやすくscoutyで使っている技術をご紹介したいと思います。

アルゴリズム概要

平たく言うと、今回ご紹介するのはアルファベットで表記された名前の文字列を受け取って、その名前の人物の国籍を推定するというアルゴリズムです。下記のように動作します。

f:id:scouty:20170513142035p:plain:w600

上記の例は英語圏の名前か(English)日本の名前(Japan)かを判定しています。実際のモジュールでは非英語圏(ロシア語など)やマルチバイトの名前(漢字で表記されていた場合の、中国人 / 日本人 判定)も判定できますが、今回は割愛します。

サービス上では 誤判定に高いペナルティを与えている という理由で、自信が無ければ "Unknown" と表示される仕様になっています。「Bohnam」のような珍しい名前には "Unknown"が返されています。
ネット上に自分の国籍(人間にとっては自明だったりするので)をアップしている人は多くはありません。scoutyはオープンデータから情報を取っているという性質上、scoutyサービスでは国籍を自動的に予測しなければ膨大なデータから日本人をフィルタリングすることはできません。この技術は下記のような検索時に実際に使われています。

f:id:scouty:20170513143123p:plain

基本原理

ズバリ、このアルゴリズムの基本原理は 「各国籍の名前の集合をひとつの言語 と見立てその言語モデルを作り、そのモデルで与えられた名前の生起確率を計算し、それをもとに判定を行なう」というものです。

言語モデルとは?

自然言語処理NLP) の基礎を復習しましょう。言語モデルとは、「その言語において与えられた単語や文(章)が発生する確率を与えてくれるもの」です。たとえば、"This is a pen." と "This is pen."という文章なら、前者の方が発生確率が大きいはずです(後者は文法のミスがあるので)。これは


 P(This\ is\ a\ pen) > P(This\ is\ pen)

と表せます。この確率を与えてくれるのが言語モデルで、上の例のように言語モデルは文法チェックやスペルチェックに使われます。

1つの文の生起確率は、下記のように分解して考えることができます。


 
P(this\ is\ a\ pen) = P(this | \mathrm{head}) × P(is|this) × P(a|is) × P(pen| a)

 P(is|this) は "this"のあとに"is"が続く確率を表していて、これらをすべて掛け合わせることで、その文の生起確率が計算できます。(この例は直前1単語を見ていますが、直前 $n$ 単語を見ることで精度を上げることも出来ます)

 \mathrm{head} は文頭を表す。

名前の例

上記を名前に応用してみます。
下記、$P_e$ は英語の名前でつくった言語モデルです。つまり、英語の名前で起こりやすい文字列に対して、高い確率を返します。この場合、"Andy" という名前の起こる確率は


 
P_e(Andy) = P_e(A|\mathrm{head}) × P_e(n|A) × P_e(d|n) × P_e(y|d)

と表せます。 この例からわかるように、ひとつの名前の生起確率は、それを構成している各文字の連続の生起確率によって表されます。
ここで、日本語名の言語モデルを$P_j$ とすれば、

 
P_e(y|d) > P_j(y|d)

となります。なぜなら日本語の名前では "d"のあとに"y"が続く名前なんて極めてレア(というか存在しないのでは?)なのに対し、英語では "Andy" やら "Sindy" やらいろいろあるからです。

実際に作ってみる

どうやって言語モデルを作るか?

この言語モデルをどう作るかというと、極めてシンプルで、ただ教師データの中に出てきたサンプル数の数で割り算をするだけです。
これは言語モデルを作る上で最も単純なNgramというやり方ですが、例えば上の例で出た $P(y|d)$ は単純に下のように求められます。


 \displaystyle
P(y|d) = \frac{C(dy)}{C(d)}

$C(dy)$、$C(d)$ はそれぞれ、学習データの中で "dy"が現れた、"d"が現れたです。(実際は分母や分子が0の場合を考えてSmoothingという処理をかける必要がありますが、割愛)
このようにしてすべての2文字の組み合わせについてこの確率を計算し、保存したものが言語モデルにほかなりません。(組み合わせが膨大なので、学習には時間がかかります。)

実際、Ngram以外にも言語モデルを作るやり方はたくさんあります。
(RNNというDeepLearning のアーキテクチャを使って作るやり方を今後紹介したいと思います)

教師データ

上記の$C(dy)$ や $C(d)$ などのような数字を得るため、日本人の名前を大量に集めたデータと、英語圏の人の名前を大量に集めたデータが必要になります。
scoutyは、オープンデータから情報を取得しているので、そこに蓄積した情報を使って教師データを作成しました。

国籍を公開している人は少ないですが、SNS上に各人が公開しているLocation情報を使って、「日本にいる人の名前集合」「英語圏にいる人の名前集合」を作成しました。
これは厳密には国籍ではない(日本在住の外国人もいるかもしれない)ですが、データ量を増やすことでそういったノイズを軽減し、近似することができます。
今回は、英語圏と日本合わせて約8万件のデータを使って学習しました。

クロスエントロピー

言語モデルはただの生起確率を表しますが、もう少し良い指標があります。それがエントロピーです。
文字列$\boldsymbol{X}$のエントロピー$H(\boldsymbol{X})$は一般に、


 \displaystyle
H(\boldsymbol{X}) = - \sum_x -P(x)\log_2{P(x)}

と表されます。数式は直感的でないですが、エントロピー不確かさの尺度を表します。エントロピーを利用したほうが計算がしやすくなります。

また、もうひとつの問題として、上の計算方法では単純に単語が長くなればなるほど、確率(少数 < 1)の掛け算が続くので、生起確率は小さくなります(エントロピーは大きくなります)。
それでは本質的ではないので、これを名前全体の文字数でならした指標を使います(※定義ではありません)。それがクロスエントロピーです。クロスエントロピーはもちろん、言語モデルによって変わります。


 \displaystyle
H(w_1, \cdots, w_n) = - \frac{1}{n}\log_2{P(w_1, \cdots, w_n)}

$w_i$ は、名前中の$i$番目の文字にあたります。

つまり、言語モデルAでのクロスエントロピー大きいほど、その名前がその言語Aで起こりにくいことを示します。
従って、クロスエントロピーがある一定のしきい値より低いかどうかで、その名前がその国籍かどうかを判定します。(あるいは、複数のモデルでエントロピーを計算して、その値が最も小さいモデルの国籍だと判定することもできます。)

実装方針

今回の記事ではコードを公開することは趣旨とは異なるので、簡単に実装方針に触れるだけに留めておきます。
PythonではNLTK(Natural Language Tool Kit)という自然言語処理ライブラリがあり、この NgramModel というクラスを使うことで、比較的簡単にNgramによる言語モデルを実装することができます。 entropyというメソッドを使って言語モデルに対してクロスエントロピーを計算することもできます。

まずは日本人の名前で言語モデルを作成し、エントロピー閾値を設定してそれ以下なら日本人、それ以外なら外国人と定めます。
閾値は、サービスの誤判定に対する許容度に応じて、ヒューリスティックに設定します。低ければ低いほど精度は上がりますが(Precisionは上がるがRecallは下がる)Unknownと判定されることが多くなります。
さらに、英語圏の人の名前でモデルを作り、同様に計算することで判定アルゴリズムを作ります。 
複数のモデルの結果を使って、判定器を作ります。

実際に使ってみる

精度

上記のアルゴリズムの精度を検証してみます。
日本にいる人1000件とアメリカ・イギリスにいる人1000件のデータ2000件でテストした結果です(データに偏りをなくすため同一数でサンプリング)。
教師データは、モデルを作った手法と同じように、Locationで作成している上、テストデータにはニックネームも多く含まれているので、あくまで参考程度の値となります。

正:756(うち日本人と判断されたのが385、英語圏と判断されたのが371)
Unkwnon:1220
誤:24

Precision:96.9%
Recall:37.8%
F:0.537

サービスとしてPrecision(適合率)の方が重視されているので、閾値を厳し目にして、わからないものはUnknownに判断するような仕組みにしています。

※ Recall, Precision, F値に関してはこちら:F値 - 機械学習の「朱鷺の杜Wiki」
※ 実際のサービスでは 名前以外の情報からも国籍を判定しているので、実際の精度はこの値よりも高くなります。

これからやろうとしていること

scoutyでは、今回の記事で紹介したこと以外にも、今後以下のようなことにチャレンジしていきます。

  • Recallの改善
  • 今回は 2gram (前後2文字のつながりを見る) のみのモデルを作ったが、3gram, 4gram などの別なモデルとの精度を比較すること。場合によっては違うモデルを複合させたほうが精度が出るかも。
  • N-gram以外の手法(RNNなど)で言語モデルを構築し、本手法と比較すること。
  • 別モデルで学習して、ニックネームと本名の判別のほか、
  • 女性の名前では ko や mi や e で終わる名前が多いといった特徴があるので、同じ原理を使えば、日本人の名前から性別推定も可能。
  • 名前だけではなく、投稿の言語や投稿のロケーションにより国籍を特定すること。

言語モデルエントロピーを使う方法は、手法としては新しくはないですが、学習モデルを変えることによりいろいろなことに応用ができるので、実用では非常に有用です。

scouty AI LABでは、このようなことを継続的に行って、競合優位性に関わる技術でない限りオープンにしていこうと考えています。
また、scoutyでは上記のような技術課題にチャレンジしたいという機械学習エンジニアを募集しています。
我こそは!という方は、こちら からご連絡ください。単なるディスカッションでも歓迎です!

scouty AI LAB について

株式会社scoutyについて

皆様、はじめまして。株式会社scouty 代表取締役 島田寛基と申します。

弊社は、2016年5月に創業したばかりのHR Tech(人材分野の問題をテクノロジーで解決しようとする分野)のスタートアップで、機械学習自然言語処理・統計やデータマイニングをはじめとする人工知能技術の力で採用を効率化し、IT企業の採用活動をお手伝いするサービスを提供しております。

私代表の島田は京大工学部情報学科で人工知能・マルチエージェントシステム専攻で学士号を取得し、エディンバラ大学院で自然言語処理・知識表現専攻で修士号(MSc of Artificial Intelligence)を取得したのち、弊社を創業致しました。

2017年5月現在では、京大卒の正社員3名、東大・東工大インターン5名で構成されており、全員がPythonやAI(人工知能)についての知見を持っています。

scoutyは、日本初の登録不要のAIヘッドハンティングサービスを提供しているHR Techカンパニーです。インターネット上に公開された情報を元に、エンジニアの方々にマッチしたスカウトを1通1通手書きでお届けします。

scouty AI LABについて

現在世の中ではAI(人工知能)という言葉が流行っていますが、多くの場合、それらは人工知能ではなく、単なるルールを使う処理(人工無能)です。あるいは、人工知能を導入していても、実際にサービスのコアとなる価値にその技術を上手く利用できている企業は少ないのが現状です。

そんな中私たちscoutyは、本当の意味での技術に基づいたサービスを提供してまいります。

scouty A LAB では、「競合優位性に関わる技術でない限り技術情報をオープンにしていく」という理念のもと、技術者の方を対象に、

  • scoutyに実際に使われている技術やアルゴリズム人工知能関連のものが中心ですが、人工知能分野以外のものも含みます)の紹介
  • 最新技術・話題の技術の掘り下げや解説

を中心とした情報を皆様にシェアしていきたいと思っています。


姉妹メディア scouty HR TECH LAB では、scoutyに溜まったデータから得られた知見の公表や、他のHR Tech事例の紹介 を中心情報を発信していきます。