scouty AI LAB

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

AIビジネスのレシピ:AIビジネスを成功に導くアルゴリズムマネージャ

scouty代表の島田です。 今回の記事は、2017年9月21日に scouty ✕ talentio ✕ eureka で行われた下記の 「Ventures Engineer MeetUp #02 - AI & Server Side」というイベントで発表した「アルゴリズムマネジメント&デザイン 〜機械学習の技術選定とマネジメントについて〜」という発表を記事化したものです。(当日は、自分が突如入院してしまったのでリードエンジニアの showwinに代理登壇してもらいました) eure.connpass.com

今回は、scoutyで実際にAIを用いたアルゴリズム開発を例に、「AIビジネスを成功に導くにはどうすればよいか」という問の下、アルゴリズムのプロダクトマーケットフィットの確認のほか、事前リサーチやアルゴリズムの仕様決定や技術選定を行なう「アルゴリズムマネージャ」という役割とその必要性について説明します。 画像は、主にイベントのスライドから抜粋したものになります。

本記事でのAIの定義

本記事でいうAIおよび人工知能という言葉は、人工知能分野に含まれる研究や技術のことを指します。次の図(ML, DM, and AI Conference Map より引用)における Artificial Intelligence をはじめ、 Artificial Intelligence の領域と接している Computer VisionNLP、Data Mining、Machine Learning などの分野を含む広い領域がこれに該当します。

f:id:scouty:20171204163755p:plain:w580

AIビジネスというのは、事業のコア課題の解決の手法として上記でいうAIを利用しているビジネスのことを指します。

何故アルゴリズムマネージャが必要か

まず、本題に入る前に伝えたいことは、AI分野の研究とAIビジネスは全く別物だということです。 AI分野の中でも特に機械学習分野の研究では、一般に新しい手法を使って既存手法よりも高い数値を叩き出すことが大きな目標となっています。 そのためエンジニアとしては、少し精度を改善しただけで悦に浸りたくなります(実際、こういった瞬間はとても嬉しいものです):

f:id:scouty:20171202231943p:plain:w280

しかし、ビジネスの世界では精度の向上が必ずしも事業上のKGIの向上に繋がるとは限りません。

また、実際、上のようなタイプのエンジニアよりも、現実として見かけるのは次のようなエンジニアです:

f:id:scouty:20171202231957p:plain:w280

自分もエンジニアなのでよくわかりますが、エンジニアはHOWにこだわる生き物です。問題をどうスマートに、どうエレガントに(そして時には派手な手法を使って)解決することができるかに関心を払います。つまり、手法にこだわります。しかし、研究(あるいは趣味)と ビジネスの最大の違いは、顧客がいることです。 ルールベース(人工無能)だろうが人工知能だろうが、顧客の課題を解決できなければビジネスでは意味が無いのです。

つまり、エンジニアに丸投げしても、良いAIビジネスは生まれません。おそらく、この業界で蔓延しているひとつの大きな誤解は、「優秀な機械学習エンジニアがいればAIビジネスはうまくいく」という考え方でしょう。

それでは、ビジネスを一番良くわかっているCEOに聞いてみましょう:

f:id:scouty:20171202232007p:plain:w280

やはりダメでした。以前より「何でもかんでもディープラーニングを使えばいいわけじゃない」という考え方は浸透してきたものの、依然としてこれに近いことを言っている経営者やマネージャは多いものです。つまり、良いAIビジネスを作るためには、技術とビジネスの間に立つ人が必要なのです。

では、正しい問いはどのようなものになるのでしょうか。おそらく、それは次のようなものです:

f:id:scouty:20171202233030p:plain:w310

つまり、アルゴリズムがプロダクトマーケットフィットしているか(つまり、顧客が求めているか)を検証することがもっとも重要なのです。これを行なう人を、scoutyではアルゴリズムマネージャと呼んでいます。アルゴリズムマネージャはいわばアルゴリズムのプロダクトマネージャです。一般的なCTOの仕事とは守備範囲が異なりますが、多くの組織ではCTOが似たような役割を兼任していることが多いでしょう。 「顧客が必要としているの?」と問うこと自体はたとえ非技術者でもセンスがあればCEOでもできることですが、アルゴリズムを実際に顧客が必要とするものにすることは、技術的知識が無いとできません。次のセクションで、実際にアルゴリズムマネージャどんな仕事をするのか見てみましょう。

アルゴリズムマネージャの仕事

scoutyは、2017年11月8日に転職可能性予測アルゴリズムのβ版を発表しました。(下記参照)

scouty.co.jp

この転職可能性予測アルゴリズムの開発を例にとり、アルゴリズムマネージャの実際の仕事を次の各項目に整理しました。

  • システムダイナミクスマップの構築
  • メトリクス定義と評価
  • ロードマップ構築
  • 事前リサーチ
  • 技術選定
  • オペレーションの設計

各項目で用いられている図は、説明用に作成されたものなので、実際のアルゴリズム開発で用いられたものとは異なります。

システムダイナミクスマップの構築

システムダイナミクスマップは、「アルゴリズムの精度が1%上がると、ビジネスKGIがどのくらい伸びるのか?」ということを規定します。図中では、ビジネスKGIとKPI、アルゴリズムのメトリクスを抜き出し、正の因果関係がある要素ごとに矢印を張り、それぞれの強度を矢印の太さで表しています。scoutyの転職可能性予測(退職率予測)アルゴリズムでの例は次のようになります。

f:id:scouty:20171203014332p:plain:w680

このマップを描く際のコツは、マップを右(ゴール)から描くということです。売上を最大化しようとした結果実は機械学習がいらなかった、ということもあるので、ビジネス成果にこだわるのであればソリューションドリブン(解決策・アルゴリズムから考える)なやり方よりも、課題やゴールから出発したほうが有効でしょう。 このマップを正確に持つために、アルゴリズムマネージャは日々顧客のところに行ったり、現場の人と喋ったり、開発以外のことをしなければいけません。

メトリクス定義と評価

アルゴリズムは、改善のPDCAを回すにあたって評価することが必須になります。そこで、評価の指標となるメトリクスを定義します。 メトリクスは一般にアルゴリズムの精度に近いものをとりますが、一口に精度といっても、Precision、Recall、F値、平均二乗誤差などいろいろな指標があるので、そのどれを使って評価を行なうかを定義します。次の画像は、scoutyの転職可能性予測(退職率予測)アルゴリズムにおける評価軸の一例です。

f:id:scouty:20171203014121p:plain:w680

その数値が上がると、必ずKGIが上がり、
かつ測定しやすいもの をメトリクスとして定めると良いでしょう。しっかりとマップを見ながらKGIに結びつくものを決定します。

ロードマップ構築

最初から完璧なversion1はありません。最初から完璧なものを作るよりも、どのようなマイルストーンをどういうスケジュールで達成していくかというロードマップを構築することが重要となります。 例えば、次のようなスケジューリングが考えられます:

f:id:scouty:20171205150722p:plain:w680

これは短期的なスケジュールの例ですが、次にどのような条件が揃えば次のバージョンがリリースできるのか等、長期的なロードマップを作ることも重要です。 scoutyでは、「ルールベースレベル」「ライブラリ適用レベル」「最先端技術適用レベル」のような形で各アルゴリズムをレベル分けし、それぞれがどのフェーズにいるかを確認できるシートを作っています。フェーズごとに求められるエンジニアや技術の種類が全く異なるので、アルゴリズムがどのフェーズにいるかを常に把握しておく必要があります。

ロードマップやスケジュールに精度を含めるかに関しては、議論の余地があります。精度を含めても、単純に機械学習系のタスクは「〜〜をすると◯%上がる」といった単純な世界ではないので、結局設定した精度に達しない(そのための施策もわからない)、ということになり無意味なスケジュールとなってしまいます。「ビジネス上◯%までいかないと使えないから、◯%までいかなければ開発を辞める / リリースをしない」といった判断は可能かもしれませんが、「△ヶ月後に◯%まで伸ばす」というスケジュールはナンセンスなものになりがちです。したがって、「いつまでに◯◯を行なう」という施策ベースでスケジュールを立てるほうが現実的かもしれません。

事前リサーチ

事前リサーチをすることで、アルゴリズム開発の後工程が数倍楽になります。 事前リサーチをする主な目的は、「仮説を事前検証することで実装工数を減らすこと」と言って良いでしょう。実際のアルゴリズムを実装しながら、「あれも効果ない、これも効果ない」などとやっていては、工数がかさみます。

scoutyは、Jupyter Notebookで雑でもいいので特徴量ごとに転職年数分布の有意差が出そうかを実験してまとめていました。実際にリサーチを行ってまとめる人はアルゴリズムマネージャでなくても構いません(scoutyでもリサーチ業務はインターンが担当)が、リサーチ項目を決めたり仮設を立てたりする部分はアルゴリズムマネージャが率先してやるべきでしょう。 転職可能性予測アルゴリズムでは、「使用プログラミング言語ごとに勤務年数分布が変わるんじゃないか?」という仮説が出たので、実際のアルゴリズムに組み込む前に雑に集計を採りプロットをしました。結果、グラフは以下のようになり(横軸が勤務年数、縦軸が割合)、大きな差が無いことが確認できたので、アルゴリズムに取り込むことは止めました。

f:id:scouty:20171203180935p:plain:w490
使用プログラミング言語ごとの勤務年数分布

逆に、分布に大きな差があるために積極利用していこうと確認できた属性は、「所属会社規模」で、下記のようにグラフごとに分布の差があることが確認できます。

f:id:scouty:20171204155339p:plain:w490
所属会社規模ごとの勤務年数分布

技術選定

技術選定自体は、実装するエンジニアとのディスカッションを通じて行われるべきですが、可能な選択肢のリサーチやそれぞれのメリット・デメリットの整理などはアルゴリズムマネージャが中心となってやるべきタスクとなります。 技術選定の基準は様々ですが、自分は以下の4つの基準を用いることが多いという印象です。(広告業界だと実行速度といった指標も入れるべきなので、ここはケースバイケースです)

f:id:scouty:20171203190227p:plain:w540

もちろん、手法インプットとアウトプットが解きたい課題にフィットしているということが前提となります。学習データ量によっても手法ごとにパフォーマンス違う(少なくてもそこそこの精度が出る手法も、一定精度出すまでにかなりのデータがいる手法もある)ので、そういった点も考慮して手法を選定できればベストでしょう。 ビジネスでは必要なデータが貯まるまでに時間もかかったりもするので、「いついつまでに◯◯という手法を使い、その後は△△を使った実装に着手する」といったロードマップと合わせて検討するのが良いでしょう。

オペレーションの設計

新しいアルゴリズムを作ると、それに伴い実際のビジネスのオペレーションが変化します。例えば何かを自動化するアルゴリズムだとしたら、人手が不要になるので、その後の人の采配や、自動化した部分をどう運用していくかを考えなければいけません。転職可能性予測アルゴリズムの例では、「ラベル付けされた転職可能性で絞り込む」作業が顧客に発生するので、カスタマーサポートチームにその工程のサポートを加える必要がありました。(せっかく作ったアルゴリズムが顧客に利用されなければ無意味なので) アルゴリズムの開発に常にオペレーションの変化が発生するとは限りませんが、発生する場合は、アルゴリズムマネージャが率先してビジネス側の担当者とオペレーションを設計し、運用していかなければなりません。 また、アルゴリズムの保守の部分もアルゴリズムマネージャが担わなければいけません。データが変遷するとアルゴリズムの中身も変えなければいけないので、運用の型作りも作らなければいけません。(このあたりは手法が確立されている領域ではないので、作っていきたいですね)

アルゴリズムマネージャに必要な能力

以上をふまえて、アルゴリズムマネージャにとって必要なスキルセットは以下のようなものとなるでしょう。

  • 各手法に関しての広い知識 (できれば実装経験があり、工数や必要なデータ量の肌感が掴めるのが望ましい)
  • AI / ML系のライブラリ・クラウドサービスなどの広い知識(実装しなくて済む部分と実装が必要な部分の理解)
  • CRISP-DM などのデータ分析のプロセスモデルへの理解
  • クライアント・ユーザとの対話能力
  • 経営や事業上のKPIへの理解
  • 実装するエンジニアのマネジメント能力

知識が無いから、実装が苦手だからマネージャになるわけではありません。アルゴリズムマネージャがミスをすると、ビジネス上結果につながらないことを工数をかけて実行するといったことが発生するなど経営的にも大きなロスになるので、むしろ一番経験がある人がやるべきでしょう。

scoutyでは、アルゴリズムマネージャを募集しています。

データサイエンティストという職業はここ数年で浸透しましたが、アルゴリズムマネージャないしそれに類する役割は未だ必要性や仕事内容が認知されていませんし、仕事内容も曖昧なままです。scoutyでは、アルゴリズムマネージャの仕事をこなすと同時に、他社にも活かせる一般的な型やフローを構築し、それを世の中に発信していける人材を探しています。 現在は代表の島田がこれにあたる役割を兼任していますが、今後アルゴリズムも増えるにあたって専任の方を募集していく予定ですので、興味のある方は、下記のリンクから応募をお願いします!

www.wantedly.com

また、今回のテーマ+α の内容は再度外部のイベントで発表予定です。イベントを共催してくれるの企業の方や、発表内容のリクエストなど、連絡やコメントお待ちしております!

RNNで言語モデルを作る - 実装編

代表の島田です。前回の記事 RNNで言語モデルを作るための理論 では、言語モデルを作るという目的で一般的なRNNの構造についての解説を行いました。それを踏まえて、今回の記事では Python で実際に言語モデルを実装し、その言語モデルを用いて自動で生成された文章の内容を確認してみます。 scoutyでもRNNは今後文生成や、スカウトメールの文面と返信率の相関性検証などに使っていこうと考えている技術です。

今はフルスクラッチで書かなくても、Chainerのような便利なライブラリがあるので、実践で使うならそちらの方が便利でしょう。 ただ、実際にフルスクラッチで実装することで、中身の原理を理解し、チューニングすることも自分でできるようになるので、今回はそういった趣旨でRNNの実装を行ってみます。

モジュール構成

一般的なNNと同様、以下のようなモジュール構成になります:

  • predict: Forward Propagation を行う関数
    • 入力 x: 文(単語 $x^{(t)}$  を並べた1次元配列)
      • e.g., "I have a" を表現する [0, 4, 2]
    • 出力 y: 予測値(単語 $y^{(t)}$ を並べた1次元配列)
      • e.g., "have a pen" を表現する [4, 2, 3]
    • 出力 s: 隠れ層
  • compute_mean_loss: 損失関数
    • 入力 X: 訓練データ(文 $\boldsymbol{x}$ を並べた2次元配列)
      • e.g., "I have a" と "You want to" を表現する [[0, 4, 2], [1, 3, 0]]
    • 入力 D: 教師データ(文 $\boldsymbol{d}$ を並べた2次元配列)
      • e.g., "have a pen" と "want to make" を表現する [[4, 2, 3], [3, 0, 3]]
    • 出力 mean_loss: XD から計算された損失関数の値
  • acc_deltas_bptt: 重み更新値(デルタ)を計算する関数
    • 入力 x: 文(単語 $x^{(t)}$ を並べた1次元配列)
    • 入力 d: 教師データ(単語 $d^{(t)}$ を並べた1次元配列)
    • 入力 y: 予測値(単語 $y^{(t)}$ を並べた1次元配列)
    • 入力 s: 隠れ層
    • 入力 steps: BPTTで遡るタイムステップ数
  • train: トレーニングを実行する関数
    • 入力は数が多いので省略します(コード内の docstring をご参照ください)

なお、もちろんこれは実装の一例であり、入出力や関数の切り分けパターンは他にも存在します。

各モジュール

今回の実装では、以下のように RNN クラスのインスタンス変数として重みや重み更新値を設定します:

class RNN(object):
    def __init__(self, vocab_size, hidden_dims):
        self.vocab_size = vocab_size
        self.hidden_dims = hidden_dims 
        
        # matrices
        # V (input -> hidden)
        self.V = random.randn(self.hidden_dims, self.vocab_size) * sqrt(0.1)
        # W (hidden -> output)
        self.W = random.randn(self.vocab_size, self.hidden_dims) * sqrt(0.1)
        # U (hidden ->; hidden)
        self.U = random.randn(self.hidden_dims, self.hidden_dims) * sqrt(0.1)
        
        # aggregated weight changes for V, W, U
        self.deltaV = zeros((self.hidden_dims, self.vocab_size))
        self.deltaW = zeros((self.vocab_size, self.hidden_dims))
        self.deltaU = zeros((self.hidden_dims, self.hidden_dims))

predict の実装

Forward Propagation, つまり入力(例えば "The bank went bankrupt")から次単語列(例えば "bank went bankrupt again")の予測を行う関数 predict は、次のように実装されます:

def predict(self, x):
    '''
    Args:
        x: list of words, as indices (e.g.: [0, 4, 2])
    Returns:
        y: matrix of probability vectors for each input word
        s: matrix of hidden layers for each input word
    '''
    # NOTE: in this implement, s[0] = [0. 0. ... 0.]
    #       and s[t+1] is the hidden layer corresponding to y[t]
    s = zeros((len(x) + 1, self.hidden_dims))
    y = zeros((len(x), self.vocab_size))

    for t in range(len(x)):
        x_vector = self.get_one_hot_vector(x[t])

        net_in = dot(self.V, x_vector) + dot(self.U, s[t])
        s[t + 1] =  sigmoid(net_in)

        net_out = dot(self.W, s[t + 1])
        y[t] = softmax(net_out)

    return y, s

前回記事の図に示したように、単語の長さに応じてレイヤーの枚数が変わっていくようなイメージです。

$t$ 番目の単語を one-hot ベクトル $\boldsymbol{x}^{(t)}$ で表した場合は文の表現は行列になりますが、本記事の実装では $\boldsymbol{x}^{(t)}$ のうち1となっているインデックスだけを整数で表すことで、文を1次元のベクトルで表現することとします。つまり、 predict の引数 x は1次元配列 (list) になります。

損失関数 compute_loss, compute_mean_loss の実装

今回の実装では、損失関数として Cross Entropy Loss を用います。このとき、文一つの損失 $J$ は各単語の損失 $J^{(t)}$ の和*1として、次のように表されます:

\begin{align} J^{(t)} &= -\sum^{|V|}_{j=1} d^{(t)}_j \log y_j^{(t)}\\ J &= \sum^{n}_{t=1} J^{(t)} \end{align}

今回はデータセットの評価にはmean_loss関数、つまり、データ全体でみた損失関数の単語ごとの平均を用いました。

def compute_loss(self, x, d):
    y, s = self.predict(x)
    loss_t = zeros(len(y))

    for t in range(len(y)):
        d_t_vector = self.get_one_hot_vector(d[t])
        y_t_vector = y[t]

        # dot product works as product & summation
        loss_t[t] = -dot(d_t_vector, log(y_t_vector)) 

    # combined loss is summation of loss over t
    loss = sum(loss_t)

    return loss

def compute_mean_loss(self, X, D):
    '''
    Args:
        X: a list of input vectors   (e.g., [[0, 4, 2], [1, 3, 0]]
        D: a list of desired outputs (e.g., [[4, 2, 3], [3, 0, 3]]
    Returns:
        mean_loss
    '''
    sum_of_loss = 0
    sum_of_length = 0

    for i in range(len(X)):
       sum_of_loss += self.compute_loss(X[i], D[i])
       sum_of_length += len(X[i])

    # loss per word = total loss in the dataset devided by total number of words in the dataset.
    mean_loss = sum_of_loss / float(sum_of_length)

    return mean_loss

重み更新値デルタ関数 acc_deltas_bptt の実装

前回記事の更新式をそのままコードにすることで、重み更新値デルタを計算する関数 acc_deltas_bptt を以下のように実装できます:

def acc_deltas_bptt(self, x, d, y, s, steps):
    '''
    Args:
        steps: number of time steps to go back in BPTT
    Return:
        None
    '''

    net_out_grad = ones(len(x))
    net_in_grad = array([s_t * (ones(len(s_t)) - s_t) for s_t in s])
    sum_deltaW = zeros((self.vocab_size, self.hidden_dims))
    sum_deltaV = zeros((self.hidden_dims, self.vocab_size))
    sum_deltaU = zeros((self.hidden_dims, self.hidden_dims))

    # NOTE: in this implement, s[0] = [0. 0. ... 0.] 
    #       and s[t+1] is the hidden layer corresponding to y[t] (same in net_in_grad)
    for t in reversed(range(len(x))):
        d_t_vector = self.get_one_hot_vector(d[t])
        delta_out_t = (d_t_vector - y[t]) * net_out_grad[t]
        sum_deltaW += outer(delta_out_t, s[t + 1])

        delta_in = zeros((len(x), self.hidden_dims))

        for tau in range(0, 1 + steps):
            if t - tau < 0:
                break
            if tau == 0:
                delta_in[t - tau] = dot(self.W.T, delta_out_t) * net_in_grad[t + 1]
            else:
                delta_in[t - tau] = dot(self.U.T, delta_in[t - tau + 1]) * net_in_grad[t - tau + 1]
            sum_deltaV += outer(delta_in[t - tau], x[t - tau])
            sum_deltaU += outer(delta_in[t - tau], s[t - tau])

    # multiply learning rate when actually applying delta
    self.deltaW = sum_deltaW
    self.deltaV = sum_deltaV
    self.deltaU = sum_deltaU

遡るタイムステップを指定する引数 steps はハイパーパラメータで、 steps を大きくすれば大きくするほど計算結果は正確になりますが、計算量も大きくなります。

train の実装

トレーニングの際には、「エポック」という単位で処理を繰り返します。各エポックでは、まずトレーニングセンテンスごとに acc_delta_bptt を実行し、誤差逆伝搬でデルタを計算します。デルタの計算が終わると重みを更新し、次のエポックに移り、これを繰り返す流れです。 ここで、重みの更新の大きさをコントロールする 学習率 というパラメータがありますが、学習率は各エポックごとにだんだん小さくしていくのが一般的です。学習率をどのように変化させて行くかもハイパーパラメータのひとつとして実装者が決定します。今回の実装では、  m エポック目での学習率  \eta_m を以下のように定義します:

 \eta_m = \eta_0 \frac{r}{m + r}.

$r$ は実数の定数で、今回は $r=5$ としています。 train は以下のように実装します:

def train(self, X, D, X_dev, D_dev, epochs, learning_rate, anneal, back_steps, batch_size, min_change):
    '''
  
    Args:
        X: a list of input vectors       e.g., [[0, 4, 2], [1, 3, 0]]
        D: a list of desired outputs     e.g., [[4, 2, 3], [3, 0, 3]]
        X_dev: a list of input vectors   e.g., [[0, 4, 2], [1, 3, 0]]
        D_dev: a list of desired outputs e.g., [[4, 2, 3], [3, 0, 3]]
        epochs: maximum number of epochs (iterations) over the training set
        learning_rate: initial learning rate for training
        anneal: positive integer. if > 0, lowers the learning rate in a harmonically after each epoch.
                higher annealing rate means less change per epoch.
                anneal=0 will not change the learning rate over time
        back_steps: positive integer. number of timesteps for BPTT. if back_steps < 2, standard BP will be used
        batch_size: number of training instances(sentence?) to use before updating the RNN's weight matrices.
                    if set to 1, weights will be updated after each instance. if set to len(X), weights are only updated after each epoch
        min_change: minimum change in loss between 2 epochs. if the change in loss is smaller than min_change, training stops regardless of
                    number of epochs left

    Returns:
        None
    '''

    print("Training model for {0} epochs\ntraining set: {1} sentences (batch size {2})".format(epochs, len(X), batch_size))
    print("Optimizing loss on {0} sentences".format(len(X_dev)))
    print("Vocab size: {0}\nHidden units: {1}".format(self.vocab_size, self.hidden_dims))
    print("Steps for back propagation: {0}".format(back_steps))
    print("Initial learning rate set to {0}, annealing set to {1}".format(learning_rate, anneal))
    print("\ncalculating initial mean loss on dev set")

    initial_loss = self.compute_mean_loss(X_dev, D_dev)
    print("initial mean loss: {0}".format(initial_loss))

    prev_loss = initial_loss
    loss_watch_count = -1
    min_change_count = -1

    a0 = learning_rate

    best_loss = initial_loss
    bestU, bestV, bestW = self.U, self.V, self.W
    best_epoch = 0

    for epoch in range(epochs):
        t0 = time.time()
        
        if anneal > 0:
            learning_rate = a0 / ((epoch + 0.0 + anneal) / anneal)
        else:
            learning_rate = a0
        print("\nepoch %d, learning rate %.04f" % (epoch + 1, learning_rate))

        count = 0

        # use random sequence of instances in the training set (tries to avoid local maxima when training on batches)
        for i in random.permutation(range(len(X))):
            count += 1
            stdout.write("\r\tpair {0}".format(count))

            x_i = X[i]
            d_i = D[i]
            y_i, s_i = self.predict(x_i)
            if back_steps < 2:
                self.acc_deltas(x_i, d_i, y_i, s_i)
            else:
                self.acc_deltas_bptt(x_i, d_i, y_i, s_i, back_steps)

            if count % batch_size == 0:
                self.deltaU /= batch_size
                self.deltaV /= batch_size
                self.deltaW /= batch_size
                self.apply_deltas(learning_rate)

        if count % batch_size > 0:
            self.deltaU /= (count % batch_size)
            self.deltaV /= (count % batch_size)
            self.deltaW /= (count % batch_size)
            self.apply_deltas(learning_rate)

        print("\n\tcalculating new loss on dev set")
        loss = self.compute_mean_loss(X_dev, D_dev)
        print("\tmean loss: {0}".format(loss))
        print("\tepoch done in %.02f seconds" % (time.time() - t0))
        
        if loss < best_loss:
            best_loss = loss
            bestU, bestV, bestW = self.U.copy(), self.V.copy(), self.W.copy()
            best_epoch = epoch

        # make sure we change the RNN enough
        if abs(prev_loss - loss) < min_change:
            min_change_count += 1
        else:
            min_change_count = 0
        if min_change_count > 2:
            print("\ntraining finished after {0} epochs due to minimal change in loss".format(epoch + 1))
            break

        prev_loss = loss
    print("\ntraining finished after reaching maximum of {0} epochs".format(epochs))
    print("best observed loss was {0}, at epoch {1}".format(best_loss, (best_epoch + 1)))
    print("setting U, V, W to matrices from best epoch")

    self.U, self.V, self.W = bestU, bestV, bestW

トレーニング結果と文章生成結果

今回の実装では、隠れ層のユニット数 $D_h$, BPTTにおいて遡るタイムステップ数  \tau, 学習率の初期値  \eta_0 をそれぞれ以下のような範囲で変更しました:

  • $D_h \in \{10,\ 50,\ 100\}$
  •  \tau \in \{0,\ 3,\ 10\}
  •  \eta_0 \in \{0.5,\ 0.1,\ 0.05\}

パラメータの組み合わせは計27通りです。実験のためのデータセットとして Penn Treebank の WSJ Corpus を利用しています。

まず、ハイパーパラメータのチューニングを行います。このとき、全てのデータを利用するとトレーニングに時間がかかるので、トレーニングに用いるセンテンスを1000個に絞ります。なお、絞られたデータセットでのボキャブラリーサイズ $|V|$ は $|V| = 2000$ であり、エポック数は25として実験を行いました。 各パラメータに対する最終的な平均損失 (mean loss) の値は以下の表1のようになりました:

表1: `train` の際の mean loss の一覧表。  \tau を定めたときの mean loss を  \mathcal{L}(\tau) とすると、各セルの中の値はそれぞれ ( \mathcal{L}(0),  \mathcal{L}(3),  \mathcal{L}(10)) を表す。
表1

今回の実装で試したパラメータでは、  \eta_0 = 0.5, $D_h = 50$,  \tau = 5.94 が最も良い組み合わせだとわかりました。

次に、このハイパーパラメータの組み合わせを固定してフルトレーニングセット(6万件くらい)でネットワークのトレーニングをやり直し*2、できた言語モデルを使って自動で文章を生成させてみました。文章を作成する関数 generate_sequence のコードは以下のようになります:

def generate_sequence(self, start, end, maxLength):
    sequence = [start]
    loss = 0.
    x = [start]
    while True:
        # predict next word from current sequene x
        y,s = self.predict(x)

        # generate next word by sampling the word  according to the last element of y
        word_index = multinomial_sample(y[-1])

        x.append(word_index)
        sequence.append(word_index)
        pointwise_loss = -log(y[-1][word_index])
        loss += pointwise_loss

        if word_index == end or len(sequence) > maxLength:
            break

    return sequence, loss

文頭記号 <s> から出発し、 predict 関数を使って $\boldsymbol{y}^{(t)}$ ベクトルを計算し、その確率分布に応じて次の単語を選択、今までのセンテンスと結合させて、再度 predict 関数で次の単語を推定する... という流れで文章を作り、文末記号 </s> に到達したらセンテンスを返す、という処理です。

出力結果のうち、特に mean loss の小さかった例が以下になります。

mean loss: 3.36850018043
[’<s>’, ’for’, ’offered’, ’market’, ’.’, ’,’, ’that’, ’says’, ’,’, ’</s>’] 

mean loss: 3.63943955362
[’<s>;’, ’net’, ’was’, ’to’, ’share’, ’the’, ’</s>’]

mean loss: 3.78469000827
[’<s>;’, ’these’, ’has’, ’the’, ’resources’, ’the’, ’he’, ’,’, ’.’, ’it’,
’which’, ’fund’, ’</s>’]

意味の無い文が多くなっていますが、今回はデータセットも絞った上でハイパーパラメータのチューニングもまだ十分にできていなかったので、改善の余地はありそうです。 ", that says," や "was to share" といった部分的に意味の通っている表現は見受けられるものの、全体を通しては意味不明な文章が多いですね。この精度であればマルコフ連鎖モデル(品詞 → 品詞の遷移 (transition) 確率と、品詞 → 単語の emission 確率を組み合わせるモデル)などを用いる方がいいかもしれません。 意味不明な文章が生成されてしまった原因のひとつとして考えられるのは、ボキャブラリーサイズ2000のデータセットに対して one-hot ベクトルを使うことで、単語を表現するベクトル空間がスパースになってしまっていることです。 $\boldsymbol{y}^{(t)}$ ベクトルの一番大きな値でも0.01か0.02(つまり一番出やすい単語でも1%か2%の確率、他が0.5%くらい)というケースが多く、この分布に従ったらほとんどランダムに単語をピックアップしているようなものです。ピックアップのアルゴリズム(例えば上位100単語だけ見て確率を正規化し直すとか)を変えるだけで性能は向上するかもしれません。 今回は実験と原理理解のために実装した形なので、精度向上に関しての考察はこのあたりに留めておきます。

まとめ

言語モデルにおいて最も伝統的なNgramは、直前N個の単語まで考慮してコーパス内の単語のつながりをカウントし、単にカウントとカウントの割り算で確率を計算する、というシンプルなモデルでした。 このモデルの問題点は、コーパスにある単語のつながりしかカウントできないので、実際には出現する可能性があってもコーパスに出ていないというだけで単語の生起確率が0になってしまう、というものです。 これを解消する手法が単語カウントに他の単語カウントから得られた適当な数を足して0をなくすというSmoothingですが、これにもいろいろな問題があります(ここでは省略します)。端的に言うと、Ngramは汎化能力が低いという弱みがあります。

この点、RNNは単語をカウントしているのではなく、重みを学ぶことで単語と単語のつながり方を学習しているようなものなので、汎化能力が相対的に高いのです。つまり、コーパスに無い初見の単語でも確率0を与えないような出力を行うことができます。 しかし、今回のようなモデルでは one-hot ベクトルを利用するという性質上ベクトルがスパースになるという(おなじみの)問題は避けられません。今回のRNNアーキテクチャは単語の分散表現 (embedding) ベクトルでも応用可能なのか、少し考えてみる必要はあるかもしれません。

また、RNNは言語以外のシーケンシャルなデータに対しても応用できます。例えば、各タイムステップでの画像を入力にして動画を解析したり、株価の推移やFX取引のアルゴリズムとして使うことが可能です。

*1:あるいは平均を用いることもできます

*2:筆者の環境では1エポックに30分近くかかりました。

RNNで言語モデルを作るための理論

代表の島田です。scoutyでは、10/14 と 10/28 に下記の機械学習講習会を行いました。機械学習講習会#1は、このブログで紹介した言語モデルの基礎とNgramによる実践を半日で行うイベントです。
講習会の際に、RNNによる言語モデルについて教えて欲しいといった意見が多く頂きましたので、今回の記事ではRNNによる言語モデルを扱います。

scouty.connpass.com

今回は、ニューラルネットワークの拡張型RNNを用いて、ある文が与えられたときその次に来る単語の確率を与える言語モデルを作る過程を紹介します。この記事は、言語モデルに関わらずRNNの一般的な構造を取り扱うので、言語モデル以外にも応用することができます(間違いなどがあればコメントでお知らせください)。
RNNによる言語モデルは、scoutyにおいてもスカウトメールの解析などで使っていこうとしている技術のひとつです。

言語モデルとは

言語モデルとは、クロスエントロピーで名前から国籍判定する - scouty AI LAB の記事でご紹介したように、ある文が(学習元となったデータにおいて)生起する確率を与えるモデルで、例えば、以下のような関係を知ることができます。
$$
P(\mathrm{the\ cat\ slept\ peacefully}) > P(\mathrm{slept\ the\ peacefully\ cat})
$$

言語モデルがあることで、どの文章がより起こりやすいか=どの文章がより自然か を知ることができるので、機械翻訳音声認識など応用範囲は様々です。
これを応用すると、ある文 $x_t, \cdots ,x_1$ ($x_i$ は文内 $i$ 番目の単語)が与えられたとき、その次に続く単語として何が続くかを予測することができます。これを数式で表すと以下のようになります:
$$
P(x_{t+1} =v_j |x_t, \cdots ,x_1).
$$
つまり、言語モデルは ある単語の列 {x_t, \cdots , x_1} が与えられた時の次の単語(あるいは単語の列){x_{t+1}}{v_j} である確率を与えます。条件を付さなければ上のように、純粋に文章が生起する確率が得られます。

RNNとは

RNN (Recurrent Neural Network) とは、通常のフィードフォワード型のニューラルネットワークの拡張で、時系列データ(各時間でのスナップショットのシーケンス)や文(単語のシーケンス)のようなシーケンスを扱うことができるようにしたものです。各時刻 $t$ での隠れ層は、時刻 $t$ でのインプットに加え、時刻 $t-1$ の隠れ層を受け取り、両者の和をとります。基本的な構造は以下のようになります:


スクリーンショット 2016-03-25 0.35.02
画像は[1]より引用

言語モデルを作る場合、{\boldsymbol{x}(t)} は 文中 $t$ 番目の単語の one-hot ベクトル*1になります。そして、予測すべきは $\boldsymbol{x}(t)$ の次に来る単語で、これを $\boldsymbol{y}(t)$ として吐き出させることで、RNNで言語モデルを構築することができます。
実際に、$\boldsymbol{s}(t-1)$の先にも同じように $\boldsymbol{y}(t-1)$ の出力がついていて、これは $\boldsymbol{x}(t-1)$ の次に来る単語、つまり $\boldsymbol{x}(t)$ を予測するという構造になっています。

RNNでも重み行列を学習しますが、通常のNNでの学習と異なるのは3種類の異なる重みの推定を行うという点です。本記事では、3種類の重みを以下のように定義することとします:

  • $\boldsymbol{U}$: 隠れ層 → 隠れ層 の重み
  • $\boldsymbol{V}$: インプット → 隠れ層 の重み
  • $\boldsymbol{W}$: 隠れ層 → 出力 の重み

図中では同じ $\boldsymbol{U}$ がたくさん現れていますが、これらはすべて同じ行列を表しています。ある単語の次にどの単語が来るかは、単語の絶対的な位置に依存しないので、重み行列は同じであって当然という前提に基づきます。

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

入力 $\boldsymbol{x}^{(t)}$ に対して、出力 $\boldsymbol{y}^{(t)}$ を計算する Forward Propagation は次のようになります*2:


\begin{align}
\boldsymbol{\mathrm{net}}^{(t)}_{\mathrm{in}} &= \boldsymbol{Vx}^{(t)} + \boldsymbol{Us}^{(t-1)},\\\\
\boldsymbol{s}^{(t)} &= \mathrm{sigmoid}(\boldsymbol{\mathrm{net}}^{(t)}_{\mathrm{in}}),\\\\
\boldsymbol{\mathrm{net}}_{\mathrm{out}}^{(t)} &= \boldsymbol{W}\boldsymbol{s}^{(t)}, \\\\
\boldsymbol{y}^{(t)} &= \mathrm{softmax}(\boldsymbol{\mathrm{net}}^{(t)}_{\mathrm{out}}).
\end{align}


これを $t=0$ から $t=n-1$ まで順に計算してやればよいわけです。

$\boldsymbol{y}^{(t)}$ ベクトルは $t$ 番目の単語の次にくる予測単語の確率を表しています。ある単語のベクトル表現を $\boldsymbol{w}_j$ とすると、 $\boldsymbol{w}_j$ は $j$ 番目の要素が1、他が0のベクトルとなります。 $\boldsymbol{w}_j$ が $t + 1$ 番目の単語として出現する確率 $y^t_j$ は次のように表されます:
\begin{eqnarray*}
P(\boldsymbol{x}^{(t+1)}=\boldsymbol{w}_j|\boldsymbol{x}^{(t)}, \cdots, \boldsymbol{x}^{(1)}) = y^t_j.
\end{eqnarray*}

$\boldsymbol{x}^{(t)}$ は $t$ 番目の単語の one-hot ベクトルであるように、 $\boldsymbol{y}^{(t)}$ は次元数が全単語数のベクトルで、softmax 関数を使っているので全要素の和が1になります。

ボキャブラリーサイズ(全単語数)を $|V|$, 隠れ層 $\boldsymbol{s}$ の次元数を $D_h$*3 としたとき、各重み行列は以下のような形をとります:

\begin{align}
\boldsymbol{U} \in \mathbb{R}^{D_h \times D_h}, \
\boldsymbol{V} \in \mathbb{R}^{D_h \times |V|}, \
\boldsymbol{W} \in \mathbb{R}^{|V| \times D_h}.
\end{align}


学習アルゴリズム:BPTT

通常のNNでは Back Propagation (誤差逆伝播法)が学習アルゴリズムに用いられますが、RNNでは Back Propagation Through Time (BPTT) というアルゴリズムが用いられます。基本アイディアは同じで、出力層の誤差を重みを通じて伝播させていきますが、BPTTでは出力層 $\boldsymbol{y}^{(t)}$ での誤差のみならず、一つの前の時刻 $t-1$ の誤差を加算するという点が異なります。もちろん、一つだけとは言わず任意のタイムステップ  \tau だけ遡った誤差を加味してもよいでしょう。ただし、  \tau を大きくすれば当然計算量は増えます。例えば、10ステップ前の誤差まで加味するRNNはレイヤー数の10の FeedFoward NN の計算量に匹敵するので、適切な  \tau を設定する必要があります(これもまたハイパーパラメータ)。遡るタイムステップ数  \tau を限定したBPTTを Truncated BPTT といいます。また、多層NNと同じ理由で Vanishing Gradient Problem も発生します*4

以下が、各重みの更新式となります。添字 $p$ は、データ内から取ってきたセンテンス $p$ を表します。$\boldsymbol{x}_p^{(t)}$ は $p$ 内の $t$ 番目の単語です。$\boldsymbol{d}_p^{(t)}$ は教師データ (desired vector)、つまり、$\boldsymbol{x}_p^{(t)}$ の次に実際に来る単語です。通常、$\boldsymbol{d}_p^{(t)} = \boldsymbol{x}_p^{(t+1)}$ となります。

\begin{align}
\boldsymbol{\delta}_{\mathrm{out},\ p}^{(t)} &= (\boldsymbol{d}_p^{(t)} - \boldsymbol{y}_p^{(t)})g'(\boldsymbol{\mathrm{net}}_{\mathrm{out},\ p}^{(t)})\\
\Delta\boldsymbol{W}_p^{(t)} &= \boldsymbol{\delta}_{\mathrm{out},\ p}^{(t)}\ \boldsymbol{s}_p^{(t)} \\
\end{align}

$\boldsymbol{W}$ は純粋にアウトプットのエラー($\boldsymbol{d}_p^{(t)}$ と $\boldsymbol{y}_p^{(t)}$ の差)だけに影響を受けるので、タイムステップを遡る必要はありません。

\begin{align}
\boldsymbol{\delta}_{\mathrm{in},\ p}^{(t-k)} &= \begin{cases}
\boldsymbol{W}^T\boldsymbol{\delta}_{\mathrm{out},\ p}^{(t)}\ f'(\boldsymbol{\mathrm{net}}_{\mathrm{in},\ p}^{(t)}) & (k=0) \\
\boldsymbol{U}^T\boldsymbol{\delta}_{\mathrm{in},\ p}^{(t-k+1)} f'(\boldsymbol{\mathrm{net}}_{\mathrm{in},\ p}^{(t-k)}) & (k>0)
\end{cases}\\
\Delta\boldsymbol{V}_p^{(t-k)} &= \boldsymbol{\delta}_{\mathrm{in},\ p}^{(t-k)} \otimes \boldsymbol{x}_p^{(t-k)}\\
\Delta\boldsymbol{U}_p^{(t-k)} &= \boldsymbol{\delta}_{\mathrm{in},\ p}^{(t-k)} \otimes \boldsymbol{s}_p^{({t-k}-1)}
\end{align}

なお、$\otimes$は直積 (outer product) を表します。
今回は損失関数に Cross Entropy Loss を使用し、活性化関数に sigmoid と softmax を利用しているので、それらの微分は次のようになります:
\begin{align}
g'(\boldsymbol{\mathrm{net}}_{\mathrm{out},\ p}^{(t)}) &= \boldsymbol{I},\\
f'(\boldsymbol{\mathrm{net}}_{\mathrm{in},\ p}^{(t)}) &= \boldsymbol{s}_p^{(t)} ( \boldsymbol{I} - \boldsymbol{s}_p^{(t)}).
\end{align}

$\boldsymbol{I}$ は成分がすべて1である適当な長さのベクトルです。なお、断りがない限りベクトルどうしの積は対応要素ごとの積を並べたベクトルとします。

これを遡るタイムステップ  \tau ぶんと、全データ $N$ について足し合わせればよいというわけです。つまり、重みの更新式は以下のようになります:


 \boldsymbol{W} \leftarrow \boldsymbol{W} + \eta \sum_{p}^{N} \sum_{t=1}^{n} \Delta\boldsymbol{W}p^{(t)}.

ネットワークの形は異なりますが、学習や順伝播など、基本的なアイディアはほとんど通常のニューラルネットワークと同じですね。
希望が多ければ、次回の scouty 機械学習講習会イベントのテーマにすることも検討しています。

参考文献

[1] Guo, Jiang. "Backpropagation through time." Unpubl. ms., Harbin Institute of Technology, 2013.
https://pdfs.semanticscholar.org/c77f/7264096cc9555cd0533c0dc28e909f9977f2.pdf

[2] Frank Keller, Natural Language Understanding - Lecture 11 Recurrent Neural Network, University of Edinburgh, 2016.

*1:次元数=全単語数で、そのベクトルが表現する単語の成分だけ1,他が0になっているベクトル。

*2:$t$ に関する表記法が [1] とやや異なりますが、本記事の以降の部分はこちらのノーテーションに従うこととします。

*3:$D_h$は自由に決められるハイパーパラメータの一つです。

*4:その解決策がいわゆるLSTMです。

Recursive Autoencoder で文の分散表現

scouty 代表の島田です。 トピックモデルで単語の分散表現 - 理論編 - scouty AI LAB では、局所表現・分散表現の違いに関して説明しましたが、「単語の分散表現と同じように、文*1の分散表現を作るにはどうすればよいか?」というのが今回のテーマです。 CNNで文の識別タスクを解く - scouty AI LAB でもCNNによって文の分散表現を作る方法を扱いましたが、本記事では Recursive Autoencoder によって文の分散表現を作る方法をご紹介します。

Autoencoder とは何か

Recursive Autoencoder は、 Autoencoder (オートエンコーダー)を組み合わせることによって文の意味表現をひとつのベクトルとして表そうとするモデルです。 Autoencoder というのは、入力ベクトルを受け取ったら、入力ベクトルと全く同一のベクトルを出力することを目的として学習を行う特殊なニューラルネットワークモデルのひとつで、次のような図で表されます。

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

入力次元よりも隠れ層の次元が大きければ入力 $x_i$ をただ単に出力 $\hat{x}_i$ に受け流すという自明な解が存在してしまうので、一般的には隠れ層の次元は入力層の次元より小さく設定します。学習が終了したのちに何らかのベクトルを入力すると、隠れ層の値は入力ベクトルの圧縮表現になっています。つまり、隠れ層は「学習した重みと掛け合わせることで入力が再現できるベクトル」であり、隠れ層の次元は入力ベクトルの次元より小さくなっているので、 Autoencoder はベクトルの次元縮約器であると解釈することができます*2

Autoencoder では入力ベクトルを再現するように学習を行うため、教師データが必要ありません。そのため、 Autoencoder は教師なし学習に分類されます。$d$ 次元の入力ベクトル $\boldsymbol{x} = (x_1, \dots, x_d)^T$ に対する Autoencoder の出力を $\boldsymbol{\hat{x}} = (\hat{x}_1, \dots, \hat{x}_d)^T$ とすると、$\boldsymbol{\hat{x}}$ は以下のように表されます。

$$ \boldsymbol{h} = \boldsymbol{f}(\boldsymbol{W_1}\boldsymbol{x} + \boldsymbol{b_1}),\\ \boldsymbol{\hat{x}} = \boldsymbol{f}(\boldsymbol{W_2}\boldsymbol{h} + \boldsymbol{b_2}). $$

ここで、 $\boldsymbol{h}$ は隠れ層を表すベクトル、$\boldsymbol{b_1}$, $\boldsymbol{b_2}$ はバイアスを表すベクトル、 $\boldsymbol{W_1}$, $\boldsymbol{W_2}$ は重みを表す行列です。 また、$\boldsymbol{f}$ は sigmoid などの活性化関数であり、上式では、ベクトルを入力として同次元のベクトルを出力するものとして定式化しています。

Autoencoder の二乗誤差は

$$L(\boldsymbol{x}, \boldsymbol{\hat{x}}) = ||\boldsymbol{x} - \boldsymbol{\hat{x}}||^2 $$

Cross Entropy 誤差は

$$L(\boldsymbol{x}, \boldsymbol{\hat{x}}) = -\sum_{k=1}^d x_k \log \hat{x}_k + (1-x_k) \log(1-\hat{x}_k)$$

と表され、トレーニングなどは通常のNNと同じように行われます。 ちなみに、Autoencoder の最も代表的な使いみちは Recursive Autoencoder ではなく、深層学習のプレトレーニングで使われる Stacked Autoencoder でしょう。こちらに関しては既に扱っている文献が多いので、そちらを参照することをおすすめします。

Recursive Autoencoder

Recursive Autoencoder は、Autoencoder を次のように積み上げます。

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

一番下の各 $\boldsymbol{x}$ は、文内の各単語の分散表現になります。まず文章内の単語を二分木で表すのが第一ステップです。$[\boldsymbol{x}_3; \boldsymbol{x}_4]$ は、ベクトル $\boldsymbol{x}_3$ と $\boldsymbol{x}_4$ を単に縦に連結させたベクトルです。この2つのベクトルを Autoencoder で圧縮し、その隠れ層をベクトル $\boldsymbol{y}_1$ とします*3。次に、 $\boldsymbol{x}_2$ と $\boldsymbol{y}_1$ の連結を圧縮し、$\boldsymbol{y}_2$ を作ります。このように単語を再帰的に圧縮していってできた最後のベクトル $\boldsymbol{y}_3$ が、この文の分散表現となります

文から上図のような二分木を作る手法は様々ですが、次のような greedy な手法が用いられることが多いようです。

  1. 文中の単語数を $n$ 個として、隣り合う $n-1$ 個のペアを考える。
  2. それぞれのペアの Reconstruction Error を計算する。
  3. その中で一番小さいエラーのペアを選択し、実際にペアを作る。
  4. ペアをひとつの単語(ノード)に見立てて、1〜3を繰り返す。 隣り合う単語しか見ないので完全なアルゴリズムではありませんが、妥当な時間でそこそこ良い結果を与えることが知られています。

Recursive Autoencoder の性能の尺度である Reconstruction Error (ノード $y_k$ のエラー) $E_{\mathrm{rec}}(k)$ は次のように表されます。

$$E_{\mathrm{rec}}(k) = \frac{n_i}{n_i + n_j} ||x_i - \hat{x}_i||^2 + \frac{n_j}{n_i + n_j} ||x_j - \hat{x}_j||^2$$

$n_i$ はノード $i$ に含まれている単語数。長い単語の連続ほど再現が難しくなるので、重みをつけています。また、全ツリーのコストは単にこれらのエラーの和とすればよいです。

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

これを使って文のクラス識別器を作る場合、上図のように最終的に得られた $n-1$ 個の隠れ層 $y_k$ を入力として、各クラスの確率分布を出力とするニューラルネットを新たに作れば良いわけです。各 $y_k$ のラベルはすべて文のクラス(ラベル)と同じとします。教師データは該当クラスが1、他が0になっているベクトルになります。 これはあくまでクラス識別や類似性評価に使うものであるので、このベクトル自体から文の意味を抽出して推論などができるかと言われれば、それはできません。しかし、Recursive Autoencoder を使えば文のクラス識別を、人間の手作りの特徴(e.g.センチメント解析ならポジティブ・ネガティブを表す特徴語)を使うことなく行うことができるという点では非常に便利なモデルであると言えるでしょう。

ただし、実運用においては、2017年10月時点では便利なライブラリが無いため、実際にビジネスの場で利用するのは難しそうです。 CNNによる文の分散表現のほうが一般的に文識別などでは精度が高いことが知られていますが、実際に実装する場合を考えたら、Recursive Autoencoder の方が実装コストは少なくて済むでしょう。 Autoencoder は、今回の例のように文だけでなく一般的な次元圧縮器になるので、自然言語処理のみならず幅広く応用することができると考えられます。

詳細のアーキテクチャや説明は、こちらの論文 に詳しく書かれていますので、詳細が気になった方はそちらをご覧ください。

*1:"I saw him swimming." など、連続した単語のピリオドまでのまとまりのこと。

*2:アウトプットは特に重要ではないので捨てちゃうのが普通。

*3:出力はいらないので無視。

ニューラルネットによる構文解析 ー 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

そこで使えるのが上のような Dependency 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.