TensorFlowでズンドコキヨシ

（追記） TensorFlow じゃないですが Chainer でより華麗に解かれているのを発見しました。
LSTMを使ってズンドコキヨシを学習する

---

ブームに乗り遅れてしまった感がありますが、最近 TensorFlow を触っているので、 TensorFlow で__畳み込みニューラルネットワーク（ CNN, ConvNet: Convolutional neural network ）__ を使ってズンドコキヨシを解いてみました。もはやズンドコキヨシを解くのに人類の知力を費やす必要すらありません。

コードの全体はこちらです。

問題設定

まず、ニューラルネットワークにズンドコキヨシの何を解かせるのかを考えなくてはいけません。

例えば、ズンドコリスト（「ズン」と「ドコ」がランダムに格納されたリスト）から 5 要素を切り出してそれが「ズン、ズン、ズン、ズン、ドコ」かを判定させることもできますが、それでは問題設定として簡単すぎて面白みがありません。ニューラルネットワークを持ち出すまでもなく、 $2^5 = 32$ 通りのパターンしかないので、機械学習というより全パターン覚えるだけで事足ります。

とは言え、無限ズンドコリストを入力としてニューラルネットワークに渡すうまい方法は思いつきませんでした。そういうわけで、要素数 100 のズンドコリストを渡して、「ズン、ズン、ズン、ズン、ドコ」の最初の「ズン」が初めて現れるインデックスを返すという問題にしてみます。例えば、「ズン、ドコ、ズン、ズン、ズン、ズン、ドコ、・・・」というズンドコリストに対しては 2 を返すのが正解です。要素数 100 なので 0 から 95 までの解があり得ます。また、「ズン、ズン、ズン、ズン、ドコ」が現れなかった場合は 96 を返すものとしましょう。これは、 0 から 96 のクラスに識別する 97 クラスの識別問題だと考えられます。これなら $2^100$ のパターンがあるので全パターンを学習させることはできません。機械学習で判定ロジックを学習する必要があります。

ニューラルネットワークで扱いやすいように、入力のズンドコリストは「ズン」を -1.0 、「ドコ」を 1.0 で表し、出力は TensorFlow のチュートリアルでやっているように one-hot vector で表します。つまり、「ズン、ドコ、ズン、ズン、ズン、ズン、ドコ、・・・」というズンドコリストに対しては [-1.0, 1.0, -1.0, -1.0, -1.0, -1.0, 1.0, ...] が入力として、 [0.0, 0.0, 1.0, 0.0, ...] が出力として学習させます。

学習データ

ズンドコリストは入力と出力の関係が分かっているので学習データは無限に生成できます。機械学習で一番辛いポイントの一つである、学習データを集める部分がクリアされているのはうれしいですね！

まずは、ランダムにズンドコリストを生成する関数 make_zundoko_list と、それを解く関数 solve_zundoko_list を作りましょう。

from random import choice

zun = -1.0
doko = 1.0
zun_length = 4
zundoko_length = zun_length + 1

def make_zundoko_list(length):
    return [choice([zun, doko]) for _ in range(length)]

def solve_zundoko_list(zundoko_list, index=0, zun_count=0):
    if len(zundoko_list) == 0:
        return index - zun_length
    elif zun_count >= zun_length and zundoko_list[0] == doko:
        return index - zun_length
    else:
        return solve_zundoko_list(zundoko_list[1:], index + 1, zun_count + 1 if zundoko_list[0] == zun else 0)

しかし、ランダムに生成されたズンドコリストを学習データにすると、出力が偏ってしまうためよろしくありません。 0 から 96 まで均等に学習させたいので、解を指定してズンドコリストを生成する関数 make_solved_zundoko_list も作りましょう。

def make_solved_zundoko_list(length, answer):
    zundoko_list = make_zundoko_list(length)
    while True:
        solved_answer = solve_zundoko_list(zundoko_list)
        if solved_answer >= answer:
            break
        zundoko_list[solved_answer] = doko
    if answer + zundoko_length <= length:
        zundoko_list[answer:answer + zundoko_length] = [zun for _ in range(zun_length)] + [doko]
    return zundoko_list

前述の通り、解は one-hot vector に変換しないといけないので、そのための関数 dense_to_one_hot も作っておきましょう。

def dense_to_one_hot(index, num_classes):
    return [(1.0 if i == index else 0.0) for i in range(num_classes)]

これを使って、学習データとテストデータを用意します。学習データは 10 万件、テストデータは 1000 件としましょう。

学習データでは make_solved_zundoko_list を、テストデータでは make_zundoko_list を使っていることに注意して下さい。

list_length = 100
num_classes = list_length - zundoko_length + 1 + 1

zundoko_lists = [make_solved_zundoko_list(list_length, i % num_classes) for i in range(100000)]
zundoko_answers = [dense_to_one_hot(solve_zundoko_list(z), num_classes) for z in zundoko_lists]

test_zundoko_lists = [make_zundoko_list(list_length) for _ in range(1000)]
test_zundoko_answers = [dense_to_one_hot(solve_zundoko_list(z), num_classes) for z in test_zundoko_lists]

畳み込みニューラルネットワーク

ここからが本題です。ここまではただ Python でズンドコキヨシしてるだけです。

ズンドコキヨシはリスト中で隣接したパターン（「ズン、ズン、ズン、ズン、ドコ」）を検出したいので 畳み込みニューラルネットワーク（以下、 CNN ） が適しています。 TensorFlow の二番目のチュートリアルが CNN の例になっているので、これを参考に書いていきましょう。

CNN はよく画像認識に利用されます。画像は二次元なので画像認識では二次元の畳み込みが行われます。しかし、ズンドコリストは一次元のデータ列なので一次元の畳み込みを行う必要があります。今検出したいパターンは「ズン、ズン、ズン、ズン、ドコ」なので、サイズが 5 のカーネルで畳み込めば良さそうです。

しかし、 TensorFlow の API リファレンスを調べても一次元の畳み込みを行う関数が見つかりませんでした¹。仕方がないのでズンドコリストは 100 × 1 に、カーネルは 5 × 1 に reshape して、二次元の値として扱います。これで、二次元の畳み込み conv2d を使って疑似的に一次元の畳込みを実現できます。

入力層から畳み込みを行う部分は次のようになります。

x = tf.placeholder(tf.float32, [None, list_length])
x_reshaped = tf.reshape(x, [-1, list_length, 1, 1])
W1 = tf.Variable(tf.truncated_normal([5, 1, 1, 1], stddev=0.1))
b1 = tf.Variable(tf.truncated_normal([1], stddev=0.1))
h1_reshaped = tf.nn.relu(tf.nn.conv2d(x_reshaped, W1, strides=[1, 1, 1, 1], padding='SAME') + b1)
h1 = tf.reshape(h1_reshaped, [-1, list_length])

この畳み込みでは「ズン、ズン、ズン、ズン、ドコ」のパターンを検出することが期待されます。普通、 CNN では畳込みのあとにプーリングを行いますが、今回は畳み込みの結果が直接「ズン、ズン、ズン、ズン、ドコ」を検出したかを表すだろうということでプーリングは行っていません。

さて、畳み込みで「ズン、ズン、ズン、ズン、ドコ」のパターンが検出できてもそれだけではダメです。例えば「ズン、ドコ、ズン、ズン、ズン、ズン、ドコ、ズン、ズン、ズン、ズン、ドコ、・・・」というインプットが渡されると、 2 に加えて 7 も検出してしまうと予想されます。しかし、畳込みで 2 だけを検出するというのは仕組み上困難です。なので、もう一つ層を加えて 7 のような値を除去してもらいましょう。

畳み込みでそのような計算を表現するのは難しいので次の層は全結合にします。しかし、 2 を残しつつ 7 だけを除去するという計算は複雑そうです。全結合（行列をかけるだけ）でそれだけの表現能力があるでしょうか？そもそも実現したい計算をその数式で表現できないのであれば、どうやっても学習させることはできません。

2 と 7 が検出された状態（ [0, 0, 1, 0, 0, 0, 0, 1, 0, ...] ）で、どのような行列をかければ 2 だけを検出した結果（ [0, 0, 1, 0, 0, 0, 0, 0, ...] ）を得ることができるでしょうか？例えば、次のような行列を（右から）かければ最初に検出した「ズン、ズン、ズン、ズン、ドコ」以外は負の値に飛ばすことができそうです。検出したい値とそうでない値を分離できれば、後は活性化関数でなんとでもなるでしょう。

\left(\begin{matrix}
   1.0 &   -1.0 &   -1.0 & \cdots \\
   0.0 &    1.0 &   -1.0 & \cdots \\
   0.0 &    0.0 &    1.0 & \cdots \\
\vdots & \vdots & \vdots & \ddots \\
\end{matrix}\right)

これで、行列をかけるだけでも 7 のような値を除去するのに十分な表現能力を持っていることがわかりました。表現能力があるからといって学習がうまくいくとは限りませんが、ひとまず 100 × 97 の行列をかけて（バイアスや softmax も挟んで）出力としてみましょう。 Dropout は問題の性質上（ニューラルネットワークの構成上？）相性が良くなさそうだったので省いています。

W2 = tf.Variable(tf.truncated_normal([list_length, num_classes], stddev=0.1))
b2 = tf.Variable(tf.truncated_normal([num_classes], stddev=0.1))
y = tf.nn.softmax(tf.matmul(h1, W2) + b2)

学習

あとはチュートリアルと同じように Cross entropy を最小化するように最適化して W1, b1, W2, b2 を求めます。

y_ = tf.placeholder(tf.float32, [None, num_classes])

cross_entropy = -tf.reduce_sum(y_ * tf.log(tf.clip_by_value(y, 1e-10, 1.0)))

train_step = tf.train.GradientDescentOptimizer(1e-5).minimize(cross_entropy)

answer = tf.argmax(y, 1)

init = tf.initialize_all_variables()

sess = tf.Session()
sess.run(init)

for i in range(1000):
    sess.run(train_step, feed_dict={x: zundoko_lists, y_: zundoko_answers})

毎ステップ全学習データで学習させたり、 GradientDescentOptimizer を使っていたりと細かい部分は色々とチュートリアルから変更しています。 cross_entropy については StackOverflow のこちらの回答を参考に修正しました。

結果表示

最後に、学習したニューラルネットワークにズンドコキヨシを表示させれば完了です。

zundoko_list = make_zundoko_list(list_length)
zundoko_answer = sess.run(answer, feed_dict={x: [zundoko_list]})[0]
zundoko_string_list = ['ズン' if zundoko == zun else 'ドコ' for zundoko in zundoko_list]
zundoko_string_list = zundoko_string_list[:min(zundoko_answer + zundoko_length, len(zundoko_string_list))]
for zundoko_string in zundoko_string_list:
    print(zundoko_string)
if zundoko_answer + zundoko_length == len(zundoko_string_list):
    print('キ・ヨ・シ！')

ズン
ドコ
ズン
ドコ
ドコ
ズン
ドコ
ドコ
ドコ
ズン
ズン
ドコ
ズン
ドコ
ドコ
ドコ
ドコ
ズン
ズン
ズン
ズン
ドコ
キ・ヨ・シ！

おお！！ちゃんと表示されました！

しかし、少しパラメータを変えたりして何度か試してみましたが、テストデータにおける正答率は最大で 98% しか達成できませんでした。やる前は、これくらいの単純なロジックなら 100% も達成できるんじゃないかと考えていましたが、なかなか難しいですね。今の構成ではすべての（解のインデックスと、無視されるその後のインデックスの）組み合わせが学習データに含まれていないと厳しいと思うので、層を増やすなど、より抽象的な特徴を表現できるようにすると良かったのかもしれません。

---

1. conv でざっと検索しただけなので、もしかしたら何か見逃しているだけかもしれません。 ↩