Hatena::ブログ(Diary)

Mi manca qualche giovedi`? このページをアンテナに追加 RSSフィード

2017-09-12 trainer フレームワークを使ってないのは、手抜きではない(重要)

End-to-End Memory Networks を実装してみた


久しぶりの更新。


学生さんが好きなものを開発するのを支援するサイボウズ・ラボユースという制度が始まってもう7年目。

先日、4年ぶりにラボユース合宿が開催された。



詳しくはリンク先の記事を見てもらいたいが、要は、泊まり込みで朝から晩までみっちりコードを書きまくり、夜も思う存分プログラミング談義な合宿に参加できるということ。朝昼晩のごはんもついてる。温泉もある(※開催地による)。もちろん費用はサイボウズ持ち。


サイボウズ・ラボユースは通年募集、まだまだ応募できる。興味あればぜひ。宣伝終わり。


さて、合宿にはサイボウズ・ラボの社員ものこのこついていく。

いろいろ話したり、指導したりもするのだが、やっぱりコードを書いている時間が一番長い。

しかしせっかくの合宿という場なのに、いつもと同じコードを書くのは芸がない。

そこで Memory Networks を実装してみることにした。


実は Memory Networks が、あまり好きではない。むしろ嫌いかもw。

だからこそ、食わず嫌いに陥らないために、いつもと違う雰囲気の中で実装してみようという志なわけだ。

と偉そうに言ってみたが、論文をろくに精読もしていない状態から3日間で実装するのはさすがに無謀で、合宿後も結構みっちりコード書いたり実験したりする羽目に(苦笑)。


Memory Networks とは、記憶した知識から質問にふさわしい情報を取り出し、回答を生成するモデル。

直接的には質問応答問題だが、汎用人工知能に発展させたいという野望が見え隠れしている。

日本語ならこちらのブログ記事か、MLP シリーズの「深層学習による自然言語処理」か。



前者はかなり詳しいが、さすがにこの記事だけで実装できるわけではなく、元論文を読む必要がある。

代表的な論文はこちらの3本だろう。


  • Weston, Jason, Sumit Chopra, and Antoine Bordes. "Memory networks." arXiv preprint arXiv:1410.3916 (2014).
  • Sukhbaatar, Sainbayar, Jason Weston, and Rob Fergus. "End-to-end memory networks." Advances in neural information processing systems. 2015.
  • Kumar, Ankit, et al. "Ask me anything: Dynamic memory networks for natural language processing." International Conference on Machine Learning. 2016.

素の Memory Networks は、「記憶にあるどの知識を参照するべきか」という情報が質問に付いているという前提のモデルである。

さすがにそれはちょっとなー、という人には、「どの知識を参照するべきか」も一緒に学習する End-to-End Memory Networks がある。

ネットワークの大きさも手頃で、3日間で実装するにはちょうどいいだろう(できなかったが)。


さらに発展した Dynamic Memory Networks では、「人間の推論はいきなり回答が出てくるのではなく、段階を踏んでいる」ことをモデルに組み込んだ。

End-to-End Memory Networks を実装してみて、その苦手なタスクを目の当たりにすれば、なるほど、そっちへ発展させたくなる気持ちがよくわかる。


End-to-End Memory Networks


ここで End-to-End Memory Networks の詳細に踏み込んだら、いつまでたっても実装の話に入れない。

社内勉強会用に End-to-End Memory Networks の資料を作ったので、モデルの概略は後ほどそちらを公開するときに語ることにする。

ここではモデルは既知として、実装によって確認できた知見をメインにしよう。


End-to-End Memory Networks のモデルそのものはシンプルかつ小さいので、モデルを記述するだけなら、どの深層学習ライブラリでも 10行ちょいで書けるだろう。

ただし、それだけでは全く性能が出ない。そこでさまざまな「工夫」を追加で施すことになる。


  • Temporal Encoding
  • Random Noise
  • Position Encoding
  • Linear Start
  • 勾配の切り詰め

素朴な End-to-End Memory Networks では、知識は記憶に追加されるだけであり、質問との関連を推定するときに時刻は考慮しない。

しかしそれでは、"Sandra moved to the garden." と "Sandra journeyed to the bathroom." という2つの知識の記憶があるとき、"Where is Sandra?" と質問されても、どっちの知識が今の Sandra の情報を表しているのかわからない。

そこで「記憶の知識の時刻と、質問時の時刻の差」の情報を組み込むのが Temporal Encoding だ。

これを入れないと、笑っちゃうくらい性能が出ない(タスクによってはランダムと同等まで落ちる)ので、Temporal Encoding は必須である。


ただし、Memory Networks の理想の姿であれば、知識が入ってきたときに「Sandra は garden に行った」という記憶を「 garden に行った後、bathroom に行った」に更新(Generalization)するべきなのだろう。

そこをモデル化していないツケを Temporal Encoding というヒューリスティックで払ってるわけだ。


Random Noise は、記憶の系列に 10% の確率で 0 ベクトルを挿入して時刻をずらすことで、Temporal Encoding が特定の訓練データに過適合するのを防ぐ。

論文ではかなり効果があるようだが、手元の実験ではいくつかのタスクで汎化性能がちょっこり上がった? くらいの印象。


素朴な End-to-End Memory Networks では「単語ベクトルの総和」を文のベクトルとするのだが、それだけでは "Mary handed the football to John." と "John passed the football to Mary." がほとんど区別できない。Position Encoding は単語ベクトルを加算するときに、ベクトルの要素ごとに単語の文中の位置に応じた重みを与えることで、単語の位置の情報を文ベクトルに落とし込む。


m_{ik}=¥sum_j ¥left¥{¥left(1-¥frac jJ¥right)-¥frac kd¥left(1-¥frac{2j}J¥right)¥right¥}¥left({¥bf A}{¥bf x}_{ij}¥right)_k


ここで x_ij は i 番目の文の j 番目の単語(1-hot vector)、A は単語を分散表現ベクトルに変換する行列、J は文長(単語数)、d は分散表現の次元、k=1,…,d は分散表現ベクトルの要素インデックス

この式は次のように変形することで、固定長の演算に落とし込むことができる。


m_{ik}=¥left(1-¥frac kd¥right)¥left({¥bf A}¥sum_j{¥bf x}_{ij}¥right)_k+¥left(¥frac{2k}d-1¥right)¥left({¥bf A}¥sum_j¥frac jJ{¥bf x}_{ij}¥right)_k


データに対しては、単語頻度行列を単純和 ¥sum_j{¥bf x}_{ij} と重み付き和 ¥sum_j¥frac jJ{¥bf x}_{ij} の2つをあらかじめ計算しておけばよい。

文を RNN とかでベクトル化すればこんな工夫はしなくていいだろうが、学習がテキメンに重くなる。

この手法ならネットワークの大きさを固定できるので、速度的には大幅に有利だろう。


Linear Start は、質問と各記憶の関連度を確率に落とし込むソフトマックス層がネットワークの中間にあるのだが、これを学習の初期に取り除いてしまうという手法。

学習が早くなり、local minimum に捕まりにくい……と論文は言うのだが、正直効果は実感できなかった。

validation loss が上昇したらソフトマックス層を挿入して本来のモデルに戻すので、Linear Start するしないはせいぜい初期値の影響程度。上述の固定長で実装すればかなり高速に学習できてしまうので、初期値を変えて何回かトライする&ちょっと長めに Epoch 回すくらいで十分 Linear Start を上回れるんじゃないの?


学習については、"No momentum or weight decay was used." と書かれており、生 SGD を使うことが明示されている。

しかし学習率を 1e-5 以下にしても、かなりの頻度であっさり inf に飛ぶ。特に上の Linear Start を組み込んだら、inf に飛ばずに学習できる方がまれになる。そこで、backward 後に、各パラメータごとに勾配のノルムが 40 を超えていたら、スカラー倍して 40 に納める、という強引な変換を入れる。

こんなの初めて見たんだけど、アリなのかな? GAN の学習が不安定なのとか、これでうまくいく割合が増えたり?


ただ、そんな勾配の切り詰めなんかしなくても、Adam でさっくり学習できたりする(苦笑)*1。まあ、Momentum 系特有の乱高下はちょいちょい起きるけど。


あとは学習率を細かく変えるとか、ミニバッチは 32 とか、指定されてるけど、そのへんはネグった。

というわけで実装はこちら。



当初、ベクトルを計算するところで文の長さに応じた処理が必要になると思って Chainer を選んだのだが、固定長で済むので Tensorflow と使うべきだった。スパース行列もサポートしているし。無念。

Chainer から Tensorflow への移植がどんなものかという興味もあるので、気が向いたら Tensorflow で実装し直すかもしれない。たぶん、そんなに大変じゃない。


bAbI データセット
https://research.fb.com/downloads/babi/

データセットは bAbI。Facebook が Memory Networks のために作った?

ごくごく単純な文法と、ごくごく小さな語彙セットで構成され、しかも回答は1単語という、名前の通りとても簡単な質問応答データセット。20 のタスクが用意されているが、否定文を含むのはその中の1つだけだったり。

リンク先から bAbI Tasks Data 1-20 (v1.2) をダウンロードして展開(ファイル名は tasks_1-20_v1-2.tar.gz )、e2emn.py を実行すると Task 1 で学習・推論する。

他のタスクに変えたり、上述の工夫を On/Off したり、Adam で学習したりもできるので、ヘルプ見て。


Task 1〜20 それぞれについて、初期値を変えて5回学習、それぞれ一番良いエラー率を拾ったものがこちら。

論文に合わせて、BoW(Temporal Encodingのみ)と、Position Encoding, Linear Start, Random Noise を順に有効にしていったものについて実験している。

大勢には影響ないだろうと思って validation=test にしてる。手抜き。


f:id:n_shuyo:20170912193931p:image


細かいところは色々違ってるが、かなり論文に近い結果が再現できた?

違いを産んでいるのは、やっぱりミニバッチを実装していないことかもしれない。

トライしなかったわけではないのだが、ソフトマックス層の幅がデータごとに違うのをうまく実装するのがめんどくさくなって、半日くらいであきらめてしまった。

*1:Adam の本来のアルゴリズムのおかげなのか、Chainer の Adam 実装のおかげなのかはわかってない。

2015-06-04 パラメータの試行錯誤は楽しいが、無駄なことしてるな感も強い

Python Lasagne でニューラルネットするチュートリアル その 2

昨日の記事の続き。

まずは、Lasagne のハマリポイントを紹介しながらコードの説明。

そのあと、ディープラーニング? ディープニューラルネットワーク? どちらの呼び名が正しいのかビミョウに自信ないが、要は畳み込み& max-pooling &ドロップアウトを織り交ぜたモデルを学習させようとするとハマリポイントが増えるので、そのあたりの注意点とサンプルコード。


def digits_dataset(test_N = 400):
    import sklearn.datasets
    data = sklearn.datasets.load_digits()

    numpy.random.seed(0)
    z = numpy.arange(data.data.shape[0])
    numpy.random.shuffle(z)
    X = data.data[z>=test_N, :]
    y = numpy.array(data.target[z>=test_N], dtype=numpy.int32)
    test_X = data.data[z<test_N, :]
    test_y = numpy.array(data.target[z<test_N], dtype=numpy.int32)
    return X, y, test_X, test_y

データセットづくり。

ありきたりなコードだが、ここにすでに一つハマリポイントが隠されている。

特徴量 X の方は特筆することはなく、レコード数×次元のシンプルな ndarray でいいのだが。

Lasagne の出力層の非線形関数に softmax を指定した場合、出力層に与える正解ラベル y の型は暗黙に int32 が要求される。

うっかりここに普通の int の ndarray とか渡したりすると、

TypeError: ('Bad input argument to theano function with name "****.py:**" at index 1(0-based)', 'TensorType(int32, vector) cannot store a value of dtype int64 without risking loss of precision. If you do not mind this loss, you can: 1) explicitly cast your data to int32, or 2) set "allow_input_downcast=True" when calling "function".', array([...

と怒られて、どこのことを指しているのか見当つかず悩むハメになる。

このエラーが出たときは、正解ラベル y を numpy.array(*, dtype=numpy.int32) でくるむといい。


#### model
n_classes = 10
batch_size=100

l_in = lasagne.layers.InputLayer(
    shape=(batch_size, input_dim),
)
l_hidden1 = lasagne.layers.DenseLayer(
    l_in,
    num_units=512,
    nonlinearity=lasagne.nonlinearities.rectify,
)
l_hidden2 = lasagne.layers.DenseLayer(
    l_hidden1,
    num_units=64,
    nonlinearity=lasagne.nonlinearities.rectify,
)
model = lasagne.layers.DenseLayer(
    l_hidden2,
    num_units=n_classes,
    nonlinearity=lasagne.nonlinearities.softmax,
)

モデルの定義は入力層 lasagne.layers.InputLayer から始めて、lasagne.layers.* の第一引数に前の層を指定しながらつないでいき、最後に適当な出力層を宣言すると、それがそのままモデルの参照となる。


入力層は shape で入力層の次元を指定するのは自然だが、一度に入力するデータのレコード数もこのモデルを定義する段階で指定する必要がある。これがハマリポイントその……いくつ目だっけ?

おそらく実装上の都合だろうが、適当な batch_size を決めて、入力データを batch_size 件ずつに分けて学習を回すのが Lasagne 流になる。ここで shape の値に、入力データの全データ件数を指定すると、学習のところでデータを分割して回す必要がなくなってコードの一部がすっきりするのだが、(おそらく)最急降下法相当になり、足がめちゃめちゃ遅くなる。

というわけで適当な batch_size を指定する必要がある。あまり小さいと速度が落ちるし、学習が落ち着かずに loss や accuracy が跳ねまわる。大きいと足が遅くなるし、余りのデータが無駄になる。

十分大きいデータなら 500 前後がほどよい印象( mnist.py は batch_size=600 になっている)。このサンプルコードでは、データが 2000件にも満たないので batch_size=100 にしている。


出力層は、ニューラルネットワークで何が作りたいかによって変わるだろうが、いちばん一般的な他クラス分類器なら、サンプルにある通り lasagne.layers.DenseLayer を使って、 num_units にクラス数を、 nonlinearity に lasagne.nonlinearities.softmax を指定すればいい。

クラス数は y.max()+1 とかしてもよかったけど、わかりきってるのでリテラル書いちゃった。


#### loss function
objective = lasagne.objectives.Objective(model,
    loss_function=lasagne.objectives.categorical_crossentropy)

X_batch = T.matrix('x')
y_batch = T.ivector('y')
loss_train = objective.get_loss(X_batch, target=y_batch)

定義したニューラルネットワークモデルから目的関数を生成してくれるところが Lasagne の真骨頂である。

ああ、あとおそらくこの Objective をインスタンス化するまでのどこかのタイミングに、パラメータを格納する SharedVariable も用意してくれている。


loss_train は Theano の expression になっているので、theano.function に食わせれば実行コードにコンパイル済みの関数が得られる。Theano すげー。

あとは、この loss_train を使って、必要な関数や処理を作っていくことになる。


#### update function
learning_rate = 0.01
momentum = 0.9
all_params = lasagne.layers.get_all_params(model)
updates = lasagne.updates.nesterov_momentum(
    loss_train, all_params, learning_rate, momentum)

#### training
train = theano.function(
    [X_batch, y_batch], loss_train,
    updates=updates
)

Lasagne における学習は、Theano の updates の仕組みを使ってパラメータを更新する。

updates に渡す更新関数も、適切な lasagne.updates.* を呼べば Lasagne が作ってくれる。

Lasagne には単純な SGD も用意されているが、lasagne.updates.nesterov_momentum は Nesterov Moment を使った SGD になる。これは、「パラメータを前回動かした方向にしばらく動かす & 勾配を取る点も前回動かした方向に少しずらす」というもの。DNN 向けに SGD を改良したもので、収束が速くなる……のかな? mnist.py がこれを使っていたので、ここのサンプルもそれに倣った。


lasagne.layers.get_all_params は、前回の最後にもチラッと出ていたが、パラメータを格納した SharedVariable のリストを返すものである。

更新関数はもちろん対象となるそのパラメータたちを知らなければならないので必要性はわかるのだが、それをユーザが書かなければならないところには納得いかない(苦笑)。


学習率や Nesterov Moment の moment パラメータが固定で与えられているのは違和感があるかもしれない。

これを T.dscalar にして、theano.function の引数で与えるようにすれば可変にもできることは確認した。が、生 SGD より制御が難しく、結果をうまく改善できなかったので、mnist.py と同じように固定で与えている。


mnist.py では、この train 関数はデータを SharedVariable に置いて givens で渡す形で書かれている。そして引数はそのデータの中でその呼出で対象となる範囲を指すインデックスのみを指定する。特に GPU を用いる場合はデータの転送コストが一番高いわけで、そうすると mnist.py と同じ方式のほうが確実に効率いいだろう。

このサンプルでは簡素なコードを優先したことと、Lasagne を試している環境が GPGPU を利用できないものだったので(笑)、データを引数で渡すシンプルな形にした。


#### prediction
loss_eval = objective.get_loss(X_batch, target=y_batch,
                               deterministic=True)
pred = T.argmax(
    lasagne.layers.get_output(model, X_batch, deterministic=True),
    axis=1)
accuracy = T.mean(T.eq(pred, y_batch), dtype=theano.config.floatX)
test = theano.function([X_batch, y_batch], [loss_eval, accuracy])

予測のための関数を定義しているところ。

deterministic というパラメータは、おそらく、Dropout などのノイズ層にスルーで渡されて、True のときにはランダムに捨てるのをやめる(学習時のみドロップアウトする)という制御のためだと思われる。

それ以外には特に疑問はないだろう。


#### inference
numpy.random.seed()
nlist = numpy.arange(N)
for i in xrange(100):
    numpy.random.shuffle(nlist)
    for j in xrange(N / batch_size):
        ns = nlist[batch_size*j:batch_size*(j+1)]
        train_loss = train(X[ns], y[ns])
    loss, acc = test(test_X, test_y)
    print("%d: train_loss=%.4f, test_loss=%.4f, test_accuracy=%.4f" % (i+1, train_loss, loss, acc))

ようやく準備が全て終わって推論である。が、batch_size ずつしか訓練に与えることができないので、ここでも自前でコードをちょいと書く必要がある。といっても、読めばわかるレベルなので大丈夫だろう。

せっかく引数でデータを渡すのだから、渡すデータの順序がランダムになるようにした。batch_size に対して余る分はそのイテレーションでは使われないわけだが、ランダムにしておくことで使われないデータの偏りをなくすことも期待している。

テストデータの評価の方は batch_size に分ける必要がないので、一発呼び出しで済んでいる(このときは……)。


以上、これが一番シンプルな Lasagne の使い方。

でも、Lasagne でもっとディープラーニングっぽい画像処理したいという場合にはもう二手間くらい必要になる。

サンプルで使っているデータセット digits は 8x8 の画像なので、これを入力とした畳み込み& max-pooling &ドロップアウトを織り交ぜたモデルのサンプルコードがこちら。


import numpy
import lasagne
import theano
import theano.tensor as T

# dataset
def digits_dataset(input_width, input_height, test_N = 400):
    import sklearn.datasets
    data = sklearn.datasets.load_digits()
    N = data.data.shape[0]
    X = data.data.reshape(N, 1, input_width, input_height)
    y = numpy.array(data.target, dtype=numpy.int32)

    numpy.random.seed(0)
    z = numpy.arange(data.data.shape[0])
    numpy.random.shuffle(z)
    test_X = X[z<test_N]
    test_y = y[z<test_N]
    X = X[z>=test_N]
    y = y[z>=test_N]
    return X, y, test_X, test_y

n_classes = 10
input_width = input_height = 8
X, y, test_X, test_y = digits_dataset(input_width, input_height)
N = X.shape[0]
test_N = test_X.shape[0]
print(X.shape, test_X.shape)


#### model
batch_size=100

l_in = lasagne.layers.InputLayer(
    shape=(batch_size, 1, input_width, input_height),
)
l_conv1 = lasagne.layers.Conv2DLayer(
    l_in,
    num_filters=8,
    filter_size=(3, 3),
    nonlinearity=lasagne.nonlinearities.rectify,
    W=lasagne.init.GlorotUniform(),
    )
l_pool1 = lasagne.layers.MaxPool2DLayer(l_conv1, pool_size=(2, 2))

l_hidden1 = lasagne.layers.DenseLayer(
    l_pool1,
    num_units=256,
    nonlinearity=lasagne.nonlinearities.rectify,
)
l_hidden1_dropout = lasagne.layers.DropoutLayer(l_hidden1, p=0.2)
l_hidden2 = lasagne.layers.DenseLayer(
    l_hidden1_dropout,
    num_units=64,
    nonlinearity=lasagne.nonlinearities.rectify,
)
model = lasagne.layers.DenseLayer(
    l_hidden2,
    num_units=n_classes,
    nonlinearity=lasagne.nonlinearities.softmax,
)

#### loss function
objective = lasagne.objectives.Objective(model,
    loss_function=lasagne.objectives.categorical_crossentropy)

X_batch = T.tensor4('x')
y_batch = T.ivector('y')
loss_train = objective.get_loss(X_batch, target=y_batch)

#### update function
learning_rate = 0.01
momentum = 0.9
all_params = lasagne.layers.get_all_params(model)
updates = lasagne.updates.nesterov_momentum(
    loss_train, all_params, learning_rate, momentum)

#### training
train = theano.function(
    [X_batch, y_batch], loss_train,
    updates=updates
)

#### prediction
loss_eval = objective.get_loss(X_batch, target=y_batch,
                               deterministic=True)
pred = T.argmax(
    lasagne.layers.get_output(model, X_batch, deterministic=True),
    axis=1)
accuracy = T.mean(T.eq(pred, y_batch), dtype=theano.config.floatX)
test = theano.function([X_batch, y_batch], [loss_eval, accuracy])


#### inference
numpy.random.seed()
nlist = numpy.arange(N)
for i in xrange(100):
    numpy.random.shuffle(nlist)
    for j in xrange(N / batch_size):
        ns = nlist[batch_size*j:batch_size*(j+1)]
        train_loss = train(X[ns], y[ns])
    result = []
    for j in xrange(test_N / batch_size):
        j1, j2 = batch_size*j, batch_size*(j+1)
        result.append(test(test_X[j1:j2], test_y[j1:j2]))
    loss, acc = numpy.mean(result, axis=0)
    print("%d: train_loss=%.4f, test_loss=%.4f, test_accuracy=%.4f" % (i+1, train_loss, loss, acc))

元のサンプルコードとよく似ているが、細かいところが結構違うので、そのあたりを中心に説明して Lasagne チュートリアルを終わろう。

  • 2次元データを入力に使うときは、4次元テンソルで渡す必要がある。 digits_dataset() で X を reshape している行を見てもらえば手っ取り早いが、その形も (データ件数, 1, 横次元, 縦次元) と、2次元目がなぜか 1 でないといけない(理由は調べてない。 Theano の制限?)
  • モデルの定義で Conv2DLayer や MaxPool2DLayer や DropoutLayer で畳み込みや max-pooling やドロップアウトを記述できるが、これはコードを見ればわかると思うので説明略。
  • loss function の定義で、入力データを表す変数 X_batch が、1次元のときは T.matrix だったが、2次元では T.tensor4 とする。
  • 1次元のときは updates 関数だけが batch_size のしばりがあったのだが、2次元では loss function そのものにも batch_size のしばりが及ぶようになる。つまり test も一発呼び出しができなくなるので、こちらでも分割してループして結果を平均、といった処理を行う必要がある。テストは訓練と違ってランダムサンプリングするわけにはいかないので、テストデータのサイズは batch_size の整数倍であることが望ましい。

2015-05-27 PRML 13章はよく書けてるな、と改めて実感

「続・わかりやすいパターン認識」の8章「隠れマルコフモデル」の問題点 2つ #ぞくパタ

【追記】

本記事の内容は公式の正誤表ですでに修正済みです。第1版第4刷以降が出ることがあれば、そちらに反映されていることが期待されます。

【/追記】


昨日は ぞくパタ読書会 にのこのこ行ってきた。主催者、発表者、参加者の皆さん、会場を提供してくださったドワンゴさんに感謝。


「続・わかりやすいパターン認識」(以降「ぞくパタ」)の8章「隠れマルコフモデル」を読んだわけだが、この章には理解のさまたげになりうる問題点が大きく2つあると感じた。


  • 自明ではない条件付き独立性を、言及なく使っている
  • ビタービアルゴリズムで求める ψ_t(j) の定義が明記されていない

前者は読書会でも突っ込んだのだが、残念ながらピンときている人はいない様子だった? 式変形を追えばそこで詰まると思うのだが……いや、全員まったく問題なく式変形できた可能性もまだ残っている。

まあそれはともかく。簡単に問題点を整理・フォローしてみる。


自明ではない条件付き独立性を、言及なく使っている

書籍の中で対象となるのは次の番号の式。


  • (8.6)
  • (8.10) 前向きアルゴリズム更新式
  • (8.16) 後ろ向きアルゴリズム更新式
  • (8.24) ビタービ更新式
  • (8.40) バウム・ウェルチのξ(正規化前)

見ればわかるが「隠れマルコフで重要な式のほぼ全て」である。

それもそのはず、そもそも隠れマルコフの仮定はまさにその条件付き独立性を得るため導入されており、その条件付き独立性のおかげでこのモデルは計算できるようになっているのだから。


ぞくパタはグラフィカルモデルをやってなく、グラフィカルモデルなしでモデルに含まれる条件付き独立性を導出するのは面倒なので、ネグったのだろう。そこまでは理解できるのだが、条件付き独立性を使っていることを言いもしないのはさすがにまずい。

「この式変形では、隠れマルコフの仮定から導かれる 〜 という条件付き独立性を用いている」と一言あるだけでも、無条件で成立するものではないと知れるし、ちゃんと式の導出を追っかけたいと思った人は条件付き独立性について調べ考える機会が与えられる。

今の状態では、隠れマルコフの仮定がいかにして強力な枠組みを生み出しているのか、その様子を目の当たりにすることもできない。


もったいない。


確かに何もかも理解するのは難しいし、そんな必要なんてないという意見もあるだろう。

が、捨てる順番的には、確率モデルで一番大切な条件付き独立性は最後ちゃうかなあ、と個人的には強く思う。


というわけで、使われている条件付き独立性を紹介し、それを使って実際に式変形する。

式変形は全部ではなくあえて 1つだけにしておくので、興味があれば残りはぜひ自力で。


まずは条件付き独立性。

つか一応「条件付き独立性」って何ってところからやっとくか。

ぞくパタ 7ページに書いてあるのをそのまま引くと、「 S が与えられた下で事象 X, Y は条件付き独立である」とは次のいずれかが成り立つこと。


  • P(X|Y,S)=P(X|S)
  • P(Y|X,S)=P(Y|S)
  • P(X,Y|S)=P(X|S)P(Y|S)

ぞくパタ では「事象」になっているが「確率変数」に対しても同様に定義する。


そして「S が与えられた下で X, Y は条件付き独立である」ことを X¥perp Y | S と書くことにする。

本来なら条件付き独立性の ⊥ の縦棒は2本なのだが、はてダの環境では出ないので1本にさせてもらってる。手抜きですまん。


さて、隠れマルコフモデルでは以下のような条件付き独立性が成立する。記号はぞくパタのままなので、notation は省略。


  • (1) x_1,¥cdots,x_t¥;¥perp¥;x_{t+1},¥cdots,x_n¥;|¥;s_t
  • (2) x_1,¥cdots,x_t ¥;¥perp¥;s_{t+1}¥;|¥;s_t
  • (3) x_1,¥cdots,x_{t-1},s_{t-1} ¥;¥perp¥; x_t ¥;|¥;s_t

他にもあるのだが、とりあえず。

導出は……省略(苦笑)。上にも書いた通り、隠れマルコフの仮定から導出できなくないのだが、めんどくさすぎる。

ここでの主眼は「条件付き独立性を示す」ことではなく「条件付き独立性を使っていることを言う」なので、いいのだ(開き直り)。


ちなみにグラフィカルモデルは、そのめんどくさすぎる条件付き独立性の導出を「見ただけでわかる」ようにしてくれる強力なツールである。

興味があれば PRML 8章などをどうぞ。


さて条件付き独立性を使って上の式の 1つをやっつけよう。前向きアルゴリズム更新式 (8.10) あたりでいいか。

  • ¥alpha_t(j)¥;=¥;¥left{¥sum_{i=1}^c¥alpha_{t-1}(i)¥;a_{ij}¥right}¥;b(¥omega_j,x_t)   (8.10)

a とかαとかをもとの確率になおす。

  • P(x_1,x_2,¥cdots,x_t,s_t=¥omega_j)¥¥ ¥;=¥;¥left{¥sum_{i=1}^c P(x_1,x_2,¥cdots,x_{t-1},s_{t-1}=¥omega_i) ¥;P(s_t=¥omega_j|s_{t-1}=¥omega_i) ¥right}¥;P(x_t|s_t=¥omega_j)

長い。


x_1,x_2,¥cdots,x_{t-1} はセットでしか動かさないので、それを {¥bf x}_1^{t-1} と書くことにする。

また s_t=¥omega_js_{t-1}=¥omega_i は常に値が指定されているものとして、それぞれ単に s_t, s_{t-1} と記す。

それだけだと右辺の sum のインデックス i の指すものが行方不明になるので、sum は s_{t-1} についてとる形で表す。


  • P({¥bf x}_1^{t-1},x_t,s_t)¥;=¥;¥left{¥sum_{s_{t-1}} P({¥bf x}_1^{t-1},s_{t-1}) ¥;P(s_t|s_{t-1}) ¥right}¥;P(x_t|s_t)

見通しが良くなった。これを示す。

確率の加法定理から

  • P({¥bf x}_1^{t-1},x_t,s_t)¥;=¥;¥sum_{s_{t-1}} P({¥bf x}_1^{t-1},x_t,s_t,s_{t-1})

である。s_{t-1} を増やして消しただけ。

右辺の sum の中身を、乗法定理を2回使って変形する。

  • P({¥bf x}_1^{t-1},x_t,s_t,s_{t-1})
  • =P(x_t|{¥bf x}_1^{t-1},s_t,s_{t-1})¥;P({¥bf x}_1^{t-1},s_t,s_{t-1})
  • =P(x_t|{¥bf x}_1^{t-1},s_t,s_{t-1})¥;P(s_t|{¥bf x}_1^{t-1},s_{t-1})¥;P({¥bf x}_1^{t-1},s_{t-1})

¥alpha_{t-1}(i)=P({¥bf x}_1^{t-1},s_{t-1}) なので、分解の3項目は片付いた。

(ここまでは乗法・加法定理しか使っていないので、隠れマルコフでなくても成立する)


1項目は上の条件付き独立性の (3) x_1,¥cdots,x_{t-1},s_{t-1}¥;¥perp¥;x_t¥;|¥;s_t を使うと、

  • P(x_t|{¥bf x}_1^{t-1},s_t,s_{t-1})=P(x_t|,s_t)

となり、これは b(¥omega_j,x_t) である。

2項目は同じく条件付き独立性 (2) x_1,¥cdots,x_t¥;¥perp¥;s_{t+1}¥;|¥;s_t から

  • P(s_t|{¥bf x}_1^{t-1},s_{t-1})=P(s_t|s_{t-1})

となり、a_{ij} である。これで (8.10) が示された。


ここで一番大事なことは、「前向きアルゴリズムやビタービを導出するには隠れマルコフの仮定がちゃんと必要だった」とわかること。

これらのアルゴリズムは隠れマルコフ以外でも出てくるので、そのときになんで使えるかもこの辺りを理解していれば納得しやすい。


ビタービアルゴリズムで求める ψ_t(j) の定義が明記されていない

ビタービは、ψ_t(j) という値を再帰的に求めることで状態の系列を推定するアルゴリズムだが、その ψ_t(j) について、ぞくパタでは次のように説明している。


「ある時点 t で状態 ω_j に到達し、かつ x_t が観測される確率を考える。その確率は、1時点前の状態が ω_1〜ω_c のいずれであるかによって異なり、c 種存在する。その中で最大となる確率を ψ_t(j) で表す」


正直、この説明では ψ_t(j) がなんなのかわからなかった。

ψ_t(j) が何かわからなくても、(8.24) 式では漸化式が与えられるので、それを認めれば計算はできる。

が、その ψ_t(j) で最適な状態の系列が推定できることはなぜわかるのだろう?


ψ_t(j) が定義されていれば、漸化式はそこから導ける(ここでも条件付き独立性を使う)し、それを求められれば最適系列を与えることもわかる。問題解決。

というわけで定義をしよう。*1


  • ¥psi_t(j)¥;:=¥;¥max_{s_1,¥cdots,s_{t-1}}¥;P(x_1,¥cdots,x_t,s_1,¥cdots,s_{t-1},s_t=¥omega_j)

ちなみに Ψ_t(j) の方は、この最大値を与えるときの s_{t-1}=¥omega_iインデックス i である。このことをふまえると、Ψ を逆向きにたどると最適系列を得られることも間違いなく理解できる。


条件付き独立性についてはグラフィカルモデルをやってないという同情点があったが、こちらは単なる定義の明記漏れである。

次版があるならぜひ改善してほしい……と思うが、話を聞くとそういったフィードバックは受け付けられにくそうな雰囲気なので、期待はしない。


次回読書会参加は……ツッコミの反応イマイチだったし、11章のディリクレ過程と、あともしかして行くとしたら12章かなあ。

teramonagi さんと sfchaos さんはガチツッコミしてもいいと聞いているのでw

*1:この定義を見ると、本の「説明」が実はまずいということもわかる

2013-08-05 さりげに自分で実装してないモデルはこのブログで初めて

Active Learning を試す(Uncertainly Sampling 編)

教師あり学習の教師データの作成はとても大変。例えば、twitter 言語判定のために、訓練・テストデータあわせて70万件のツイートに言語ラベルを振った人もいたりいなかったり。


Active Learning(能動学習) はそんな教師データ作成のコストを抑えながらモデルの性能向上を測るアプローチの1つ。

具体的には、正解なしデータの中から「こいつの正解がわかれば、モデルが改善する(はず)」というデータを選び、Oracle と呼ばれる「問い合わせれば正解を教えてくれる何か(ヒント:人間)」にそのデータを推薦、得られた正解付きデータを訓練データに追加して、以下繰り返し。


しかし「こいつの正解がわかれば、モデルが改善」を選び出す基準なんて素人考えでも何通りも思いつくわけで、実際 Active Learning のやり口は幾通りもある。

Active Learning Literature Survey (Settle 2009) ではその戦略を大きく6つに分類している。


  • 1. Uncertainly Sampling
  • 2. Query-By-Committee
  • 3. Expected Model Change
  • 4. Expected Error Reduction
  • 5. Variance Reduction
  • 6. Density-Weighted Methods

この記事では、まず 1. Uncertainly Sampling を試す。

これは「現時点のモデルで『最も不確かなデータ』を選ぶ」、柔らかく言うと「分類予測に最も自信がないものを選ぶ」ということ。

代表的な Uncertainly Sampling として、(Settle 2009) では 3 つの方法が紹介されている。ああ、ここでは教師あり学習一般ではなく、分類問題をターゲットに説明していく。


Least Confident
「最も確率の低いラベル」の確率が最も高いデータを選ぶ
Margin Sampling
(「1番目に確率の高いラベル」−「2番目に確率の高いラベル」)が最も小さいデータを選ぶ
Entropy-based Approach
予測分布のエントロピーが最も大きいデータを選ぶ

いずれも、どれか1つのラベルの確率が 1.0 であるデータは最も選ばれにくいし、全てのラベルの確率が等しいデータは最も選ばれやすい。まあ、いずれも至極妥当な印象がある。

線形分類器でこれらの戦略を取ると、選ばれるデータ点は分類平面周辺にもっぱら集中することになる。


Active Learning は理論的な評価も一部行われてはいるが、基本はヒューリスティックなアプローチということもあり、やっぱり実際に試さないことにはよくわからない。そこでまずは簡単な例としてロジスティック回帰に適用してみる。

ちなみに、2値分類ではこの3つの手法は同じデータを選択することになる(ことに気づかず、しばらく2値分類で頑張っていたのはナイショ)ので、多クラス分類をターゲットとする。


以下の様な設定で Uncertainly Sampling に分類される3手法 Least Confident, Margin Sampling, Entropy-based Approach と、baseline としてランダムにデータを選択する Random を比較した。

まずデータは再現実験しやすいよう NLTK の Reuters コーパスにて、crude, money-fx, trade, interest, ship, wheat, corn の 7 カテゴリを選び、この中の 2 つ以上のカテゴリに同時に属する文書を除外した 2256 文書を使った。

学習器は自分で実装してもいいが、何十回も学習することを考えると高速なものがいいので scikit-learn を使う。特徴量は単語(小文字化 & lemmatized)の出現数とした。 tf-idf の結果も一応見てみたが、精度に誤差程度の差しかなかったのでシンプルな方を採用した。


ここからそれぞれの戦略に従って選んだデータを訓練データに加えていくわけだが、最初に各カテゴリに1つ以上のデータがないと scikit-learn の分類器が学習してくれないので、初期データとしてランダムに1つずつ選ぶ。ちなみに、baseline(ランダム) 以外の3手法は初期値から後の選択は決定的である(評価値が同じ場合、numpy の arg 系はインデックスの一番若いものを取る)。

選択するデータは訓練データ数が 300 になるまでとし、残りのデータの正解率を毎回算出していった。


と、設定話はこれくらいにして、いよいよお楽しみの結果。

実装したスクリプトと、1回実行した時の正解率の推移グラフを挙げておく。

f:id:n_shuyo:20130805193233j:image


初期値依存なので細かい結果は毎回違うわけだが、このグラフから読み取れる通り、


  • Margin Sampling は精度が最も高く、かつほぼ安定している
  • Least Confident は最終的に Margin Sampling に近い精度に達するが、若干不安定
  • Entropy-based Approach はかなり不安定で、その精度は他の2つどころか Random を下回ることも珍しくない

という傾向は何回実行しても同じだった。

実行する前は Entropy-based に期待していたので、この結果は正直ショック。

Margin Sampling は実は ldig で訓練データを作る際にラベル付けするデータの選択(手動)にまさにこの指標を使っていたので、この指標が一番成績がいいのは少し嬉しくはある。


データやモデルにも強く依存するので、この傾向が常に成り立つとかそんなことは言えない。なんてわざわざ釘を刺す必要もないくらいだろうが、念のため。

次は Query-By-Committee を試す予定。


【追記】

ちょっとわかりにくいかなーと思ったので、訓練データ 100個までの推移を拡大した図を追加。

f:id:n_shuyo:20130805200558j:image

【/追記】


参考文献

2011-11-04 明日は WebDB Forum 2011。

「数式を numpy に落とし込むコツ」を HMM に当てはめてみる


という発表を Tokyo.SciPy #2 でさせてもらったのだが、発表&資料作成の時間の関係で、実際に数式を解釈する例を2つしか入れられなかったのが残念なところ。

今、社内 PRML 読書会で 13章の隠れマルコフをやっつけていて、その Baum-Welch の更新式がちょうどいい題材になっていることに気付いたので、ここで取り上げてみる。


  • ¥alpha(¥bf{z}_n)=p(¥bf{x}_n|¥bf{z}_n)¥sum_{¥bf{z}_{n-1}}¥alpha(¥bf{z}_{n-1})p(¥bf{z}_n|¥bf{z}_{n-1})   (PRML 式 13.36)

結構複雑な印象のある数式だが、こいつも資料の流れに従えば簡単に実装できてしまうことを見ていこう。

  1. 数式を読み解く
  2. 数式を書き換える
  3. numpy に「逐語訳」する

というわけでまず「読み解き」だが、これが一番重要なステップ。

特に今回の式の場合は ¥alpha(¥bf{z}_n), p(¥bf{x}_n|¥bf{z}_n), p(¥bf{z}_n|¥bf{z}_{n-1}) の正体をちゃんと見極めておかないといけない。

「正体」とは、つまりスカラーベクトルか行列か、ベクトルや行列ならその次数は何か、そしてその要素はどのように書けるか、という点だ。


まず ¥alpha(¥bf{z}_n) は次のように定義されている。

  • ¥alpha(¥bf{z}_n)=p(¥bf{x}_1,¥cdots,¥bf{x}_n,¥bf{z}_n)   (PRML 式 13.34)

x_n たちは観測値で固定されていて、z_n は 1-of-K 表現で K 通りの値を取り得る。

というわけで ¥alpha(¥bf{z}_n) は K 次のベクトルであることわかる。

z_n は本来 1-of-K 表現だが、z_n の k 番目だけが 1 であることを "z_n=k" と書くことにすると、

  • ¥alpha(¥bf{z}_n)_k = p(¥bf{x}_1,¥cdots,¥bf{x}_n,¥bf{z}_n=k) ¥hspace{20} (k=1,¥cdots,K)

となる。

alpha(z_n) なんて書き方では、とてもベクトルには見えないが実はベクトルだ、と言っても紛らわしいだけなので、今後 ¥bf{¥alpha}^{(n)}=¥alpha(¥bf{z}_n) と書くことにする。その k 番目の要素は ¥alpha_k^{(n)} と書けて、わかりやすい。




次に p(¥bf{z}_n|¥bf{z}_{n-1}) の定義は

  • p(¥bf{z}_n|¥bf{z}_{n-1},¥bf{A})=¥prod_{k=1}^K¥prod_{j=1}^K A_{jk}^{z_{n-1,j}z_{nk}}   (PRML 式 13.7)

と書かれている。

これは 1-of-K 表現のせいで多項分布がややこしく表現されてしまっているだけで、上の記法を許せば、以下のように書ける。

  • p(¥bf{z}_n=k|¥bf{z}_{n-1}=j,¥bf{A})=A_{jk} ¥hspace{20} (j=1,¥cdots,K,¥;k=1,¥cdots,K)

つまり p(¥bf{z}_n|¥bf{z}_{n-1},¥bf{A}) は K×K 行列であったことがわかる。


最後に p(¥bf{x}_n|¥bf{z}_n) だが、今回は出力分布に多項分布を使うことにすると、その定義は (PRML 式 13.22) に書かれているが、それは上の p(z_n|z_{n-1}) と全く同じ形なので、同様に次の形になることがわかる。

  • p(¥bf{x}_n=i|¥bf{z}_n=k)=¥mu_{ik} ¥hspace{20} (i=1,¥cdots,D,¥;k=1,¥cdots,K)

ここから p(¥bf{x}_n|¥bf{z}_n) は D×K 行列だったわけだ。

どうだろう、ここまで読み解いただけでも、最初の式がすでにだいぶ簡単に見えてきたのではないだろうか。


読み解きステップが終わったので、数式を書き換えよう。

資料から、書き換え方針について書いたページを引用してみる。


f:id:n_shuyo:20111104145227p:image


ベクトル・行列の積の数式は、このように要素の数式に書き換えて、上の3種類の形に当てはめてあげたらいい。

元の数式を要素の形に書き換えるには、まず左辺が K 次のベクトルだったことを思い出し、その k 番目の要素 ¥alpha_k^{(n)} を求める式を立てることを考える。このとき ¥alpha_k^{(n)} = p(¥bf{x}_1,¥cdots,¥bf{x}_n,¥bf{z}_n=k) だったので、z_n=k を右辺に当てはめる。

次に z_{n-1} で和を取っているところがある。これは 1 から K まで動くということなので、z_{n-1}=j とおいて、j が 1 から K まで動くことにしよう。もちろん z_{n-1}=j も右辺に当てはめてあげる。

すると次の式が得られた。

  • ¥alpha_k^{(n)}=p(¥bf{x}_n|¥bf{z}_n=k)¥sum_{j=1}^K ¥alpha_j^{(n-1)}p(¥bf{z}_n=k|¥bf{z}_{n-1}=j) ¥hspace{20} (k=1,¥cdots,K)

x_n は観測値なので、今その与えられた値を i と書くことにすれば、p(x|z) たちの定義から、この式はさらに次のようになる。

  • ¥alpha_k^{(n)}=¥mu_{ik}¥sum_{j=1}^K ¥alpha_j^{(n-1)}A_{jk} ¥hspace{20} (k=1,¥cdots,K)

さあ、どんどん簡単になってきた。ここで上の書き換え方針を思いだそう。

今、数式の中でΣがわざとらしいくらい目立っているので、2番目の行列積の形に当てはめたくなる。


行列積にするには、和を取っているインデックスの j が真ん中でペアになるようにすればいいんだけど、ベクトルは K×1 次元の行列とみなすんだったことを忘れずに(資料の他のページにはちゃんと書いてあるよ)。

というわけで、転置をうまく使って添え字の順番を入れ替えることで

  • ¥alpha_k^{(n)}=¥mu_{ik}¥sum_{j=1}^K (¥bf{A}^T)_{kj}¥alpha_j^{(n-1)} ¥hspace{20} (k=1,¥cdots,K)

となる。

¥sum_{j=1}^K (¥bf{A}^T)_{kj}¥alpha_j^{(n-1)} がまさに行列積を表しているので、 ¥bf{b}=¥bf{A}^T¥bf{¥alpha}^{(n-1)} とおけば、 b は K 次のベクトルで、 b_k=¥sum_{j=1}^K (¥bf{A}^T)_{kj}¥alpha_j^{(n-1)} であることがわかる。

上の式の該当部分を b_k に置き換えると、さらに簡単になる。

  • ¥alpha_k^{(n)}=¥mu_{ik}b_k ¥hspace{20} (k=1,¥cdots,K)

これを上の方針と見比べると、全ての項が k という一つのインデックスにしか依存していない(i と n は固定)ので、今度は要素積の形をしていることがわかる。

要素積は数式の記号がないので、とりあえず * と書くことにすると、最初の数式は実は次のように書き換えられることがわかった。

  • ¥bf{¥alpha}^{(n)} = ¥bf{¥mu}_i * (¥bf{A}^T¥bf{¥alpha}^{(n-1)})

これを実装するのは、もうかんたん。alpha, A, mu がそれぞれ適当なベクトルや行列であれば、

alpha[n] = mu[i,:] * numpy.dot(A.T, alpha[n-1])

でおしまい。


読み解きと書き替えは特に numpy に限った話ではないし、この「逐語訳」はほとんどの行列ライブラリでできるレベル。

もちろん R でも簡単に実装できる。


βの更新式 (PRML 式 13.38) も同様に書き換えれば、やはり誰でも実装できるので、練習問題でやってみるとおもしろいかも。