ローリングコンバットピッチなう!

AIとか仮想化とかペーパークラフトとか

ディープラーニングの限界?

[technology]chainerでニューラルネットワークを使ったソートアルゴリズムもどきを作ってみる

最近、以下の「ディープラーニングの限界」という記事を読みました。

postd.cc

自分は線形代数とかは苦手で、ディープラーニング周りの数式もきちんと理解しておらず、ニューラルネットワークの動きも直感的にしか理解していないのですが、ここ3か月くらいchainer使って遊んできた感触と、概ね上記の記事は合っています。

なんですが、

たとえ、どれほどのデータを入力しても。ディープニューラルネットワークを使ってソートアルゴリズムを学習することさえ、途方もなく困難なのです。

この記述が少し気になってしまいました。
あまり考えた事はなかったのですが、例えば10個の入力ノードと10個の出力ノードを持つニューラルネットワークに、入力値の大きい順に並べ替えた同じ値を出力ノードに出すことは出来るのだろうか?経験的には重み調整の誤差でピッタリ同じ値を大きい順に出すというのは難しそうです。

では出力ノードの各値に対して入力ノードの±数%の誤差を許容するとかだったら出来るだろうか?これは別途試そうと思いますが、とりあえず考えた事は、10個の入力にランダムに値を入れる。通常の分類器の要領で出力ノード側は入力ノードの中で一番大きい値に対応するノードを反応させる。

例えば入力が、[0.1,0.75,0.5,0.4,0.2,0.9,0.8,0.22,0.3,0.45,0.01]だとすると、0オリジンで5番目にあたる0.9が一番大きいので、出力ノードの5番目が強く反応するように訓練する。これなら通常の分類器と同じ様に正解ラベルを与えて作れそうです。

# -*- Coding: utf-8 -*-

# Numpy
import numpy as np
from numpy.random import *
# Chainer
import chainer
import chainer.links as L
import chainer.functions as F
from chainer import Chain,optimizers,Variable

# Neural Network

class DNN(Chain):
    def __init__(self):
        super(DNN, self).__init__(
            l1 = L.Linear(None,100),
            l2 = L.Linear(None,100),
            l3 = L.Linear(None,100),
            l4 = L.Linear(None,10)
        )
    def forward(self,x):
        h1 = F.relu(self.l1(x))
        h2 = F.relu(self.l2(h1))
        h3 = F.relu(self.l3(h2))
        h4 = self.l4(h3)
        return h4

n_epoch = 20000
batch_size = 1000
test_size = 100

model = DNN()
# Set optimizer
optimizer = optimizers.Adam()
optimizer.setup(model)

for epoch in range(0,n_epoch):
    sum_loss = 0
    x_train = np.array(rand(batch_size,10),dtype=np.float32)
    t_train = []
    for i in range(0,batch_size):
        maxindex = np.argmax(x_train[i])
        t_train.append(maxindex)

    t_train = np.array(t_train,dtype=np.int32)
    x = Variable(x_train)
    t = Variable(t_train)
    y = model.forward(x)
    model.cleargrads()
    loss = F.softmax_cross_entropy(y, t)
    loss.backward()
    optimizer.update()
    print("epoch: {}, mean loss: {}".format(epoch, loss.data))


x_test = np.array(rand(test_size,10),dtype=np.float32)
t_test = []

ok_cnt = 0
for i in range(0,test_size):
    maxindex = np.argmax(x_test[i])

    x = Variable(np.array([x_test[i]],dtype=np.float32))
    y = model.forward(x)
    y = np.argmax(y.data[0])
    if y == maxindex:
        ok_cnt += 1
    print("x_test[{}]={}, y={}".format(i,x_test[i],y))

print("Ok = {}/Total = {}".format(ok_cnt,test_size))

早速chainerで書いてみました。隠れ層の段数とかノード数は良く判らないので適当です。
0.0〜1.0までの値をランダムに持つ10次元のベクトルに対して、np.argmaxで最大値を持つインデックスを調べて、これを正解ラベルにします。
1000セット×20000エポックくらい学習し、100パターン試験した結果では98〜99%の正解率。

最大値を持つノードのインデックス番号に反応させるという学習がうまく行っている様に見えます。ソースにバグがあったらご指摘ください。

さて、次に、正解ラベルを最大値ではなく、生成した10次元のベクトルのうち2番目に大きい物に変えてみます。

# -*- Coding: utf-8 -*-

# Numpy
import numpy as np
from numpy.random import *
# Chainer
import chainer
import chainer.links as L
import chainer.functions as F
from chainer import Chain,optimizers,Variable

# Neural Network

class DNN(Chain):
    def __init__(self):
        super(DNN, self).__init__(
            l1 = L.Linear(None,100),
            l2 = L.Linear(None,100),
            l3 = L.Linear(None,100),
            l4 = L.Linear(None,10)
        )
    def forward(self,x):
        h1 = F.relu(self.l1(x))
        h2 = F.relu(self.l2(h1))
        h3 = F.relu(self.l3(h2))
        h4 = self.l4(h3)
        return h4

n_epoch = 20000
batch_size = 1000
test_size = 100

model = DNN()
# Set optimizer
optimizer = optimizers.Adam()
optimizer.setup(model)

for epoch in range(0,n_epoch):
    sum_loss = 0
    x_train = np.array(rand(batch_size,10),dtype=np.float32)
    t_train = []
    for i in range(0,batch_size):
# x_train[i]をソートして、大きい方から2番目の値を探して、その値をもつx_train[i]のインデックスを取り出す
        sorted_x = np.sort(x_train[i])
        second_index = np.where(x_train[i] == sorted_x[8])[0][0]
        t_train.append(second_index)

    t_train = np.array(t_train,dtype=np.int32)
    x = Variable(x_train)
    t = Variable(t_train)
    y = model.forward(x)
    model.cleargrads()
    loss = F.softmax_cross_entropy(y, t)
    loss.backward()
    optimizer.update()
    print("epoch: {}, mean loss: {}".format(epoch, loss.data))


x_test = np.array(rand(test_size,10),dtype=np.float32)
t_test = []

ok_cnt = 0
for i in range(0,test_size):
    sorted_x = np.sort(x_test[i])
    second_index = np.where(x_test[i] == sorted_x[8])[0][0]

    x = Variable(np.array([x_test[i]],dtype=np.float32))
    y = model.forward(x)
    y = np.argmax(y.data[0])
    if y == second_index:
        ok_cnt += 1
    print("x_test[{}]={}, y={}".format(i,x_test[i],y))

print("Ok = {}/Total = {}".format(ok_cnt,test_size))

同じ学習回数だと正解率が最大値に反応させる場合より少し落ちます。
テストの終わりの方の出力例です。

x_test[92]=[0.15238822 0.04593173 0.42803174 0.59043413 0.49013025 0.5451933
 0.9741593  0.32178774 0.7393287  0.22745539], y=8
x_test[93]=[0.7939154  0.13732575 0.22902003 0.06100857 0.47835788 0.74606586
 0.58519465 0.9250756  0.28504363 0.7720018 ], y=0
x_test[94]=[0.92711467 0.04576679 0.55188817 0.13352332 0.01223279 0.100926
 0.9210719  0.01820461 0.25785106 0.874551  ], y=6
x_test[95]=[0.38990566 0.33312613 0.7056679  0.78758067 0.7442032  0.86883146
 0.604757   0.68619037 0.40011367 0.97221524], y=5
x_test[96]=[0.8824228  0.48281756 0.12201603 0.26073322 0.7207669  0.51385
 0.34171596 0.50454575 0.84036064 0.36611024], y=8
x_test[97]=[0.08147321 0.21478944 0.01034194 0.8224558  0.52376133 0.63343114
 0.32268345 0.20628476 0.19218668 0.5707661 ], y=5
x_test[98]=[0.63491964 0.21061036 0.2051737  0.71735775 0.9481192  0.8545518
 0.04858703 0.9421137  0.06096161 0.31315166], y=7
x_test[99]=[0.9099687  0.8951598  0.7375997  0.98928666 0.5902716  0.4710128
 0.7191486  0.9958038  0.7403231  0.83657   ], y=3
Ok = 96/Total = 100

このパターンを組み合わせて3番目に大きい値のインデックスを学習するニューラルネットワーク、4番目に大きい値のインデックスを学習するニューラルネットワークと、順番に作っていけば、実質的にニューラルネットワークでソートが出来る気がします。
もちろん、これは人間が手順を分解してニューラルネットワークが解けそうな問題まで変換したからで、ニューラルネットワーク自身がソートアルゴリズムを学習したわけではないのですが。

もちろんソートがしたいのなら、普通にソートアルゴリズムを使った方が効率的です。ニューラルネットワークを使うは無駄の極みですが、まあ単なる実験ということで。
ちなみにn_epoch=100000にしたら少し正解率上がりました。

x_test[95]=[0.20272237 0.03843876 0.27152908 0.4094007  0.7855973  0.2899839
 0.8210693  0.5381341  0.7489075  0.9750773 ], y=6
x_test[96]=[0.28830436 0.30088127 0.07026242 0.05803379 0.58405113 0.7540929
 0.41671592 0.5648262  0.7284789  0.3085925 ], y=8
x_test[97]=[0.46263587 0.7656766  0.0066483  0.89934444 0.07683764 0.13267313
 0.52822393 0.1156532  0.9866427  0.89893526], y=3
x_test[98]=[0.52061874 0.02893524 0.29534477 0.37659898 0.6030606  0.25403515
 0.36348864 0.66296124 0.3832098  0.14724611], y=4
x_test[99]=[0.45118698 0.4618951  0.1864166  0.7442942  0.9235456  0.84616077
 0.05625276 0.24095121 0.55030423 0.7583295 ], y=5
Ok = 98/Total = 100

追記:
色々調べていたら、ニューラルチューリングマシンとか、メモリ付ニューラルネットワーク的なものがあるのですね。
動かしてみたいけど、その前にRNNとかLSTMをお勉強します。

追記2: (2018/10/28)
最初の試行ではあまり深く考えずに隠れ層を3層にしたのですが、隠れ層を1層だけにして、最大値検出をやってみました。
学習後の試験数も100回→1000回に変更。

  • 20,000エポックで正解率98.5%
  • 30,000エポックで正解率99.5%
  • 100,000エポックで正解率99.0%(下がっちゃった...)
どうやら入力10ノードくらいだと隠れ層は1層で十分な様です。100とか1000とかにするとまた違ってくるのかな?

追記3: (2018/10/30)
githubにソースを上げておきました。
github.com