読者です 読者をやめる 読者になる 読者になる

めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

TensorFlow Tutorialの数学的背景 − Vector Representations of Words

何の話かというと

本シリーズでは、これまで、CNNによる画像分類タスクを中心に解説してきました。ここでは、少し方向性を変えて、NLP(Natural Language Processing/自然言語処理)のタスクを取り上げます。Tutorialでは、Vector Representations of Wordsとして取り上げられているものです。

特徴ベクトルと「意味」の関係

本題に入る前に、「特徴ベクトル」について復習しておきます。

enakai00.hatenablog.com

上記の記事では、データを分類する際は、データそのものを見るのでなく、データから得られる「特徴変数」を見るとうまくいくことを説明しました。一般に特徴変数は複数あるので、これらを並べたベクトルを考えて、「特徴ベクトル」と言ってもよいでしょう。そして、特徴ベクトルの値によってデータがうまく分類できるということは、特徴ベクトルの値が近い場合は、データに「意味上の」類似性が高いと考えることができます。

ここで、「意味上の」という言葉を付け加えたのには、理由があります。たとえば、「画像の種類を識別する」という目的でトレーニングされたCNNが抽出する特徴ベクトルの場合、当然ながら、同じ種類の物体の画像は、類似した特徴ベクトルを持っているはずです。ただし、これは、事前に物体の種類のラベルをつけた画像を大量に与えてトレーニングすることが前提となります。どのような観点で画像を分類したいか、つまり、それぞれの画像にどういう「意味」を与えるかを人間が事前に決めておくことによって、その意味を抽出する特徴ベクトルを得る手続きが、教師あり学習に他なりません。

それでは、いよいよ本題に入ります・・・。

単語の「意味」の定義方法

自然言語処理の世界では、1つ1つの「単語」に、その「意味」を表す特徴ベクトルを割り当てるという手法があります。非常に陳腐で作為的な例ですが、手作業で特徴ベクトルを与えるならば、次のような例が考えられます。

king = (1,2)
queen = (-1,2)
man = (1,0)
woman = (-1,0)
prince = (1,1)
princess = (-1,1)
ruler = (0,2)
civilian = (0,-1)

この例では、直接計算ですぐにわかるように、有名な方程式「king - man + woman = queen」が成立します。あるいは、「king = ruler + man」「queen = ruler + woman」なども成立しています。さらに、ベクトルの内積をとると、「king・ruler = 4」「king・civilian=-2」というように、内積の値が大きいほど、意味上の類似性が高いことも確認できます。

実際のところ、これは何をしているのかというと・・・

上図からわかるように、横軸は「性別」を±1で表示して、縦軸は「支配力」を適当に数値化して与えています。つまり、「性別」と「支配力」という2種類の特徴変数で単語の「意味」を表現しているわけです。もちろんこれは、対象とする単語が非常に限定的(かつ作為的に選別したもの)だからできることで、世の中にある膨大な数の単語に対して、手作業で特徴ベクトルを割り当てることは現実的ではありません。また、この例における「性別」「支配力」のような特徴量として、どのようなものを使えばよいかも自明ではありません。

「解くべき問題」のCNNとの類似性

とはいえ、この状況は、ある意味では、画像分類問題とさほど変わりはありません。CNNによる画像分類のネットワークを思い出してみましょう。

前段のフィルター部分で特徴変数を抽出して、後段のSoftmax関数で分類処理を行っていますが、前段のフィルターはどのようにして決定したかを思い出してください。

最初に説明した単純な図形の分類では、「縦棒」「横棒」というフィルターを手作業で用意しましたが、より本格的な処理では、フィルターそのものも機械学習で決定するということを行いました。

これと同様に、何らかの方法で「単語をその意味で分類する問題」を設定して、その分類を実施するネットワークを次のように構成します。

前段は、単語から特徴ベクトルを抽出する処理で、後段は、特徴ベクトルから「意味」を予想するという処理です。沢山並んだ意味の候補のそれぞれについて、その意味を持つ「確率」が計算されます。あとは、(単語, 意味)のペアーの膨大なトレーニングセットを与えて学習させれば、前段の「特徴ベクトル変換器」が自動的に生み出されることになります。

「単語の意味」をどう定義するか

ただし、画像分類問題と異なるのは、「単語の意味」をどのように与えるかが、それほど自明ではないという点です。画像分類では、画像の意味は「ネコ」「犬」「車」など、分類したい興味の対象によって、ある程度、自明に決定することができました。一方、「単語の意味」はどのように決めればよいのでしょうか?

ここでおもむろに登場するのが、「前後の単語で、単語の意味を定義する」という、一見アバウトのようでこれがなかなかうまく行ってしまう、「コロンブスの卵」的な手法です。Tutorialの説明では、次のような文章が例として登場します。

 "the quick brown fox jumped over the lazy dog"

これを見ると、「quick」という単語の前後には、「the」と「brown」という単語があります。そこで、「quick」には、「the」と「brown」という2つの意味があるとみなして、次のようなトレーニングデータを用意します。

 (単語, 意味)= (quick, the), (quick, brown)

もちろん、これは、前後の単語そのものが「意味」を表しているわけではなく、「同じ意味の単語は、前後に現れる単語が(だいたい)同じである」という仮説をおいているものと考えてください。これにより、前後の単語(ここでは、「文脈語」と呼ぶことにします)が間接的に、その単語の意味に対応すると考えているわけです。

他の単語についても順番に見ていくと、(両端の単語は抜きにして)全体として、次のトレーニングセットが得られます。ここでは、「意味」というまぎらわしい表現はやめて、「文脈語」と記載しています。

 {(単語, 文脈語)} = {(quick, the), (quick, brown), (brown, quick), (brown, fox), (fox, brown), (fox, jumped), (jumped, fox), (jumped, over), (over, jumped), (over, the), (the, over), (the, lazy), (lazy, the), (lazy, dog)} ――― (1)

これを用いて、ある単語から、その「文脈語」を予測するネットワークをトレーニングしていきます。

具体的には、次のようなネットワークを構成します。

これに、たとえば、単語「quick」を入力すると、P(the), P(quick), P(brown), P(fox), P(jumped)・・・など、それぞれの単語が文脈語として登場する確率が計算されます。そして、先ほどのトレーニングセットを見ると、実際に登場する文脈語は、「the」と「brown」ですので、P(the)とP(brown)の値が大きくて、その他の値が小さくなるようにネットワークを最適化していくわけです。実際には、すべてのトレーニングセットに対して、全体的な正解率が最大になるように最適化していきますので、たとえば、トレーニングセットの中に、(quick, the) というデータが (quick, brown) よりも沢山含まれる場合、入力「quick」に対して、P(the) は、P(brown) よりも大きな値になります。

単語の「意味」を予測する代わりに、「ある単語に対する文脈語を予測する」という問題を設定した所がポイントとなります。

それでは、この手続きを計算式で、正確に書いていくことにしましょう。

文脈語の予測計算

はじめに、すべての単語に通し番号(インデックス番号)を振っておき、それぞれの単語は、インデックス番号で表記することにします。単語は全部でN個あるとして、n=1,\cdots ,N をインデックス番号とします。

次に、入力する単語 n^{\rm in} に対して、前段で計算される特徴ベクトルを

 {\mathbf x}(n^{\rm in}) = (x_1,\cdots,x_M) ――― (2)

と記載します。単語からベクトルをどうやって計算するのか不思議に思うかもしれませんが、ここでは単純に、すべての単語に対して、対応するベクトルを割り当てる、ハッシュ(対応表)を用意しておきます。つまり、N × M 行列 {\mathbf C} を用意しておき、次式で n から {\mathbf x} に変換します。

  {\mathbf x}(n) = (C_{n1},\cdots,C_{nM}) ――― (3)

ここでは、特徴ベクトルは、M次元ベクトルとしています。

続いて、下記の記事で紹介した線形多項分類器で、対応する文脈語の確率を計算します。

enakai00.hatenablog.com

はじめに、特徴ベクトル (x_1,\cdots,x_M) の一次関数として、分類関数 f_n\,\,(n=1,\cdots,N) を定義します。

 (f_1,\cdots,f_N) = (x_1,\cdots,x_M)
\left(
\begin{array}{rr}
w_{11} & w_{12} & \cdots & w_{1N} \\
w_{20} & w_{22} & \cdots & w_{2N} \\
\vdots \\
w_{M0} & w_{M2} & \cdots & w_{MN}\\
\end{array}
\right)+ (b_1,\cdots,b_N) ――― (4)

そして、softmax関数で、それぞれの文脈語の確率を計算します。インデックス番号表記で、対応する文脈語が n^{\rm out} である確率は次になります。

 P(n^{\rm out}\mid n^{\rm in}) = \exp\left\{f_{n^{\rm out}}(n^{\rm in})\right\} / \sum_{n'=1}^N \exp\left\{ f_{n'}(n^{\rm in})\right\}

  = \exp E(n^{\rm out}\mid n^{\rm in}) / \sum_{n'=1}^N \exp E(n'\mid n^{\rm in}) ――― (5)

ここでは、記号を見やすくするために  E(n'|n)=f_{n'}(n) と置いています。(2)(4)より、f_{n^{\rm out}}n^{\rm in} の関数になっている点に注意してください。

ここで、トレーニングセット(1)のすべてのデータについて、「正解」が得られる確率(もしくは、トレーニングセットのそれぞれの入力値 {n_i^{\rm in}} に対して、この予測器で文脈語をランダムに選んだ時に、トレーニングセットと同じデータが再現される確率)を考えます。i番目のトレーニングデータをインデックス番号表記で (n^{\rm in}_i, n^{\rm out}_i) として、次がその確率(尤度関数)になります。

 P = \prod_i P(n^{\rm out}_i\mid n^{\rm in}_i)

例によって、尤度関数の対数(対数尤度関数)を最大化するという方針に従うので、まずは、対数尤度関数を計算します。

 \log P = \sum_i \left\{ E(n_i^{\rm out}|n_i^{\rm in}) - \log \sum_{n'=1}^N \exp E(n'|n_i^{\rm in})\right\} ――― (6)

そして、(6)が最大になるようにパラメーターを調整するわけですが、(6)に含まれるパラメーターには、何があるでしょうか? ここでは、特徴ベクトルの抽出方法も学習させる前提なので、(3)の行列成分 C_{nm}、および、(4)に含まれる、ウェイト w_{nm} とバイアス b_n がパラメーターとなります。これらのパラメーターをまとめて {\theta} と記載して、あるパラメーターによる偏微分係数は次になります。

 \frac{\partial \log P}{\partial \theta} = \sum_i\left\{
\frac{\partial E(n_i^{\rm out}\mid n_i^{\rm in})}{\partial \theta}-\sum_{n'=1}^N\frac{\exp E(n' \mid n_i^{\rm in})}{\sum_{n=1}^N \exp E(n \mid n_i^{\rm in})}\frac{\partial E(n'\mid n_i^{\rm in})}{\partial \theta}
\right\}

  = \sum_i\left\{
\frac{\partial E(n_i^{\rm out}\mid n_i^{\rm in})}{\partial \theta}-{\mathbb E_i}\left[\frac{\partial E(n\mid n_i^{\rm in})}{\partial \theta}\right]
\right\}
 ――― (7)

ここで、第2項に含まれる \frac{\exp E(n' \mid n_i^{\rm in})}{\sum_{n=1}^N \exp E(n \mid n_i^{\rm in})} は、{n_i^{\rm in}} が与えられた時の文脈語が n' である確率になっていることから、第2項全体は、{n_i^{\rm in}} が与えられた時の \frac{\partial E(n\mid n_i^{\rm in})}{\partial \theta} の期待値になることを用いています。

これで、数学的にはすべての準備が整いました。(7)に従って、勾配降下法を用いて、対数尤度が増加する方向にパラメーター \theta を調整していくことができます。ただし、まともに(7)を計算しようとすると膨大な計算量がかかるので、これを近似計算で置き換えていきます。ここでは、2種類の近似方法を紹介します。まずは、1つ目です。

Importance Sampling

はじめに、確率的勾配降下法の考え方で、(7)の \sum_i (すべてのトレーニングセットに対する合計)をいくつかのバッチに分けます。少数のトレーニングデータの和で(7)を計算して、\thetaを修正して、また、次の少数のトレーニングデータの和で(7)を計算して・・・、ということを繰り返していきます。

次に、(7)の第2項に含まれる期待値の計算を近似します。期待値を計算するには、\sum_{n'=1}^N つまり、「すべての単語についての和」の計算が必要になります。膨大な数の単語について、これを計算するのは現実的ではありません。(この計算は、1回限りではなく、トレーニングセットからの個々の入力 n_i^{\rm in} について、すべて個別に計算する必要があります。)

そこで、少し大胆な発想ですが、すべての単語についての期待値の代わりに、「ランダムに選んだ少数の単語群についての期待値」でこれを近似してしまいます。ランダムに選んだ単語の集合を V として、次の近似を行います。

 {\mathbb E_i}\left[\frac{\partial E(n\mid n_i^{\rm in})}{\partial \theta}\right]
\approx \sum_{n'\in V} \frac{\exp E(n' \mid n_i^{\rm in})}{\sum_{n \in V} \exp E(n \mid n_i^{\rm in})} \frac{\partial E(n\mid n_i^{\rm in})}{\partial \theta}

この緩い意味での期待値を \tilde{\mathbb E}_i と記載して、最終的に次が得られます。

 \frac{\partial \log P}{\partial \theta}\approx \sum_{i \in I}\left\{
\frac{\partial E(n_i^{\rm out}\mid n_i^{\rm in})}{\partial \theta}-\tilde{\mathbb E}_i\left[\frac{\partial E(n\mid n_i^{\rm in})}{\partial \theta}\right]
\right\}

ここでは、一回のバッチに含まれるトレーニングデータを I と記載しています。実は、この結果は、(6)の対数尤度関数を次で近似することと同値になります。(計算すると分かります。)

 \log P \approx \sum_{i\in I} \left\{ E(n_i^{\rm out}|n_i^{\rm in}) - \log \sum_{n'\in V} \exp E(n'|n_i^{\rm in})\right\} ――― (8)

そこで、確率的勾配降下法を用いて、(8)を最大化するようにパラメーターを調整していきます。これは、「Importance Sampling」と呼ばれる手法になります。

参考:On Using Very Large Target Vocabulary for Neural Machine Translation

Negative Sampling / Noise Contrastive Estimation (NCE)

(8)を用いることで計算量は減少しますが、ここでは、さらに大胆な発想で、対数尤度関数 \log P をさらに簡単にする近似方法を紹介します。

まず、元々のSoftmax関数は、次の(5)で与えられました。

 P(n^{\rm out}\mid n^{\rm in}) = \exp E(n^{\rm out}\mid n^{\rm in}) / \sum_{n'=1}^N \exp E(n'\mid n^{\rm in}) ――― (5)

これは、N個あるすべての単語の中で、n^{\rm out} が文脈語として選ばれる確率を表します。一方、先ほどの近似計算では、「すべての単語の代わりにランダムに選んだ少数の単語群を使う」という発想で計算を簡単にしました。そこで、この発想にヒントを得て、(5)の確率を次の様な思考実験における確率に置き換えてしまいます。

まず、注目する単語 n^{\rm in} に対して、適当な単語 n が文脈語の候補として提示された際に、これを文脈語と判断する確率を p(n) = \sigma(E(n \mid n^{\rm in})) とします(\sigma はロジスティックシグモイド関数)。次に、正解となる文脈語 n^{\rm out} を1つだけ含む、文脈語の候補群  \{n^{\rm out}\} \cup V が与えられて、1つづつ順番に文脈語かどうか判断していった際に、すべてを正しく判断できる確率は、次式になります。

 P = p(n^{\rm out}) \times \prod_{n' \in V} (1-p(n')) = \sigma(E(n^{\rm out} \mid n^{\rm in})) \times \prod_{n' \in V} \sigma(- E(n' \mid n^{\rm in}))

(2つめの等号では、1-\sigma(x)=\sigma(-x) という関係を使っています。)

これを尤度関数として採用すると、特定のトレーニングデータに対する、対数尤度関数は次になります。

 \log P = \log\sigma(E(n^{\rm out} \mid n^{\rm in})) + \sum_{n' \in V} \log\sigma(- E(n' \mid n^{\rm in})) ――― (9)

もしくは、バッチ I でまとめて考えると、次が得られます。

 \log P = \sum_{i\in I}\left\{\log\sigma(E(n^{\rm out} \mid n^{\rm in})) + \sum_{n' \in V} \log\sigma(- E(n' \mid n^{\rm in}))\right\} ――― (10)

(10)を対数尤度関数として、これを最大化するように、確率的勾配降下法でパラメーターを修正していきます。これは、「Negative Sampling」と呼ばれる手法になります。(8)と(10)を比較した場合、見かけ上の複雑さはそれほど変わらないようにも思われますが、ロジスティックシグモイド関数 \sigma は微分が簡単に計算できるという性質があるため、確率的勾配降下法の計算は、(10)の方がより簡単で、さらに、経験的にこちらの方がトレーニングの精度がよくなることが知られています。

参考:Distributed Representations of Words and Phrases and their Compositionality (PDF)

ちなみに、近似前の(6)と近似後の(10)がどこまで一致するかが気になるかも知れませんが、ここでの目的は、あくまで、「正しい文脈語を選ぶ確率が、正しくない文脈語を選ぶ確率よりも大きくなるようにパラメーターを調整する」ということですので、その目的を達成する意味では、(10)は妥当な性質を持っています。線形多項分類器の観点では、正しい文脈語に対する E(n^{\rm out} \mid n^{\rm in}) の値が、正しくない文脈語に対する E(n' \mid n^{\rm in}) の値よりも大きくなることが重要です。(10)を大きくすることで、確かに、この目的を達成できることができます。

そして、TensorFlowでは、これを拡張した、「Noise Contrastive Estimation (NCE)」と呼ばれる関数が tf.nn.nce_loss() として用意されています。これは、文脈語の候補群  \{n^{\rm out}\} \cup V をランダムに選ぶ際の確率分布に応じて、計算式を補正する効果を取り入れたものになります。この後のサンプルコードでは、一様分布を用いているので、本質的には (10) と同じ(補正効果は入らない)になります。tf.nn.nce_loss() で(10)の符号違いが計算できるものと考えておいてください。

参考:Noise-contrastive estimation: A new estimation principle for unnormalized statistical models

サンプルコードの解説

それでは、Tutorialで紹介されているコード word2vec_basic.py の内容をざっと確認してみます。

はじめにトレーニング用のデータ(文章)をダウンロードして、文章内の単語をインデックス番号表記に変換したデータを用意します。

data, count, dictionary, reverse_dictionary = build_dataset(words)

data は、単語をインデックス番号表記におきかえた文章の全体です。形式としては、インデックス番号のリストになっています。dictionary, reverse_dictionaryは、インデックス番号と実際の単語を相互変換する辞書です。countは、文書内に出現する個々の単語数を収めたデータです。

なお、build_dataset()でこれらのデータを作成する際に、出現数が少ない単語は、すべてまとめて、「'UNK'」という単語に置き換えることで、全体の単語数が極端に膨大にならないように調整しています。置き換えた後の単語数は、下記の部分で指定されています。

vocabulary_size = 50000

次に、このデータを用いて、1回のバッチ用のトレーニングデータを用意します。

batch, labels = generate_batch(batch_size=8, num_skips=2, skip_window=1)

batchが入力語 n^{\rm in} のリストで、labelsが対応する文脈語 n^{\rm out} のリストになります。各引数の意味は次のようになります。

batch_sizeは、batchとlabelsの大きさです。この例では、8個の (n^{\rm in},n^{\rm out}) の組を1回のバッチで使用します。

skip_windowは、注目する単語の両側で、何個分の単語を文脈語とするかを指定します。先ほどの説明では、前後1個づつの単語を文脈語としましたが、たとえば、skip_window=2 とすると、前後2個づつの単語を文脈語として採用します。つまり、文脈語は4個得られます。ただし、これらの4個のすべてをトレーニングセットとして採用するのではなく、ここからランダムに選んだ何個かをトレーニングセットとして採用することも可能です。generate_batch()では、num_skips で指定された個数のトレーニングセットを選択します。上記の例では、skip_window=1 かつ num_skips=2 なので、前後1個づつ、つまり2個の文脈語に対して、それらすべてをトレーニングセットして採用します。

続いて、トレーニングに使用する変数を用意していきます。

次は、1回のバッチで使用する n^{\rm in}n^{\rm out} を格納するプレースホルダーです。

  train_inputs = tf.placeholder(tf.int32, shape=[batch_size])
  train_labels = tf.placeholder(tf.int32, shape=[batch_size, 1])

次は、単語と特徴ベクトルを変換する行列 {\mathbf C} に対応する変数です。初期値は乱数で決定しています。

    embeddings = tf.Variable(
        tf.random_uniform([vocabulary_size, embedding_size], -1.0, 1.0))

次は、バッチに含まれる n^{\rm in} を対応する特徴ベクトルに変換する処理です。embedは、(4)に代入するべき特徴ベクトル (x_1,\cdots,x_M) のリストになります。

    embed = tf.nn.embedding_lookup(embeddings, train_inputs)

次は、(4)に含まれるウェイト w_{nm} とバイアス b_n に対応する変数です。ウェイトの初期値は乱数で決定しています。

    nce_weights = tf.Variable(
        tf.truncated_normal([vocabulary_size, embedding_size],
                            stddev=1.0 / math.sqrt(embedding_size)))
    nce_biases = tf.Variable(tf.zeros([vocabulary_size]))

ここまでの準備ができると、tf.nn.nce_loss() を用いて、(10)の近似された対数尤度(の符号違い)が計算できます。

  loss = tf.reduce_mean(
      tf.nn.nce_loss(nce_weights, nce_biases, embed, train_labels,
                     num_sampled, vocabulary_size))

nce_withgts, nce_biases(一次関数のパラメーター)と embed(特徴ベクトル)が調整するべきパラメーターになります。num_sampled と vocabulary_size は、期待値を計算する単語をランダムに選ぶために必要な値です。n=1,\cdots,voccabulary_size の範囲から num_sampled 個の値をランダムに選ぶことで、インデックス表記で単語が選ばれたことになります。また、(10)では、バッチに含まれる単語についての和をとっていますが、ここでは、tf.reduce_mean()で平均をとっています。(最小化するようにパラメーターを調整するという目的では、和でも平均でも違いはありませんね。)

そして、この値を最小化するアルゴリズムとして、確率的勾配降下法を指定します。

  optimizer = tf.train.GradientDescentOptimizer(1.0).minimize(loss)

この後は、トレーニングセットからバッチを取り出して、パラメーターを修正する処理を何度も繰り返していくことになります。