Galapagos Tech Blog

株式会社ガラパゴスのメンバーによる技術ブログです。

TensorFlowでXOR問題を考察してみた

はじめに

こんにちは、Webチームの@vanhuyzです。

最近、暇なときにディープラーニングを勉強したり、TensorFlowをいじったりしています。 今回はまず簡単な問題を例に、理論と実際を比較しようと思います。

TensorFlowでXOR問題を解く

目的

XORをフィットさせたい

理論

XORとは

  • XOR(排他的論理和)とは、与えられた2つの命題のいずれかただ1つのみが真であるときに真となる論理演算です。
  • 真理値表:
 x_1  x_2   y
0 0 0
0 1 1
1 0 1
1 1 0

数式*1

  • フィットしたい関数 (正解関数):  y = f(\mathbf{x})
  • データから予測する仮説関数:  y = \hat{f}(\mathbf{x};\mathbf{\theta})
    今回の目的は  \hat{f} fに近づけるようなパラメータ \mathbf{\theta}を求めることです。正解関数  fが未知ですが、点数が4つしかないので、とりあえず \hat{f}が全部の点を通ったら良いです。これが回帰問題ですね。

  • 入力と出力を行列・ベクトルでまとめると、

$$ \mathbf{X} = \begin{bmatrix} 0 & 0 \\ 0 & 1 \\ 1 & 0 \\ 1 & 1
\end{bmatrix}, \mathbf{y} = \begin{bmatrix} 0 \\ 1 \\ 1 \\ 0
\end{bmatrix} $$

になります。

  • ロス関数:できるだけシンプルにしたいため、平均二乗誤差(mean squared error - MSE)を採用します。

$$ J(\mathbf{\theta}) = \frac{1}{4} \sum_{\mathbf{x} \in \mathbf{X}} (f(\mathbf{x}) - \hat{f}(\mathbf{x};\mathbf{\theta}))^2 $$

  • ネットワークの構成

単純なニューラルネットワークを構成しましょう。以下の図のように、入力層・2つユニットの隠れ層・出力層があります。XORは非線形のため、入力層から隠れ層まで活性化関数としてReLU関数を適応します。昔、線形から非線形に変換するのはよくシグモイド関数を使われていましたが、最近ほとんどの場合ReLUを使うようになりました。ReLU関数は単純に  \textrm{relu}(t) = \max(0,t) です。

f:id:glpgsinc:20160727225009p:plain

(各層のユニットと重みのイメージです。バイアス項を省略しています)

まず、隠れ層の式は:

$$ \mathbf{h} = \begin{bmatrix} h_1 \\ h_2 \end{bmatrix} = \textrm{relu}\Big( \begin{bmatrix} w_1^{11}x_1 + w_1^{21}x_2 \\ w_1^{12}x_1 + w_1^{22}x_2 \end{bmatrix} + \begin{bmatrix} b_1^1 \\ b_1^2 \end{bmatrix}\Big) = \textrm{relu}(\mathbf{W_1}^\top \mathbf{x} + \mathbf{b_1}) $$

ここで、 \mathbf{W_1}, \mathbf{b_1} は入力層から隠れ層までの重み、バイアスです。

最後に、出力  y は:

$$ y = w_2^1 h_1 + w_2^2 h_2 + b_2 = \mathbf{W_2}^\top \mathbf{h}+ b_2 $$

になります。ここで、 \mathbf{W_2} = [w_2^1, w_2^2]^\top です。

全部まとめますと、関数 \hat{f}は以下のようになります。

$$ \hat{f}(\mathbf{x};\mathbf{W_1},\mathbf{b_1},\mathbf{W_2},b_2) = \mathbf{W_2}^\top \textrm{relu}(\mathbf{W_1}^\top\mathbf{x} + \mathbf{b_1}) + b_2 $$

  • では、このニューラルネットワークが本当にXORにフィットできるかどうかかを確認しましょう。そこで、1つの解を示します。 例えば、

$$ \mathbf{W_1} = \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}, \mathbf{b_1} = \begin{bmatrix} 0 \\ -1 \end{bmatrix}, \mathbf{W_2} = \begin{bmatrix} 1 \\ -2 \end{bmatrix}, b_2 = 0 $$

全部の入力 \mathbf{X}をまとめて計算します。まず、

$$ \mathbf{X}\mathbf{W_1} = \begin{bmatrix} 0 & 0 \\ 0 & 1 \\ 1 & 0 \\ 1 & 1
\end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} = \begin{bmatrix} 0 & 0 \\ 1 & 1 \\ 1 & 1 \\ 2 & 2
\end{bmatrix} $$

バイアス \mathbf{b_1}を足すと、

$$ \begin{bmatrix} 0 & -1 \\ 1 & 0 \\ 1 & 0 \\ 2 & 1
\end{bmatrix} $$

になります(ここで全部入力をまとめて計算したため、プラス演算子はブロードキャストです)。そして、ReLUを適応すると、

$$ \begin{bmatrix} 0 & 0 \\ 1 & 0 \\ 1 & 0 \\ 2 & 1
\end{bmatrix} $$

になります。最後に \mathbf{W_2}をかけると、

\begin{bmatrix} 0 \\ 1 \\ 1 \\ 0
\end{bmatrix}

の結果が得られます。これは \mathbf{y}と一緒ですね。

以上の構成したニューラルネットワークがXORにフィットできることを確認できました。次に、TensorFlowでそれぞれのパラメータ(重みとバイアス)を求めていきたいと思います。

実装

import numpy as np
import tensorflow as tf

# 学習データセットとラベルを定義
train_dataset = np.array([[0,0],[0,1],[1,0],[1,1]]).astype(np.float32)
train_labels = np.array([[0],[1],[1],[0]]).astype(np.float32)

# フィードフォワードにて予測値を計算
def tf_prediction(X,W1,b1,W2,b2):
    h = tf.nn.relu(tf.matmul(X,W1) + b1)
    return tf.matmul(h,W2) + b2

# 学習グラフを構成
graph = tf.Graph()
with graph.as_default():
    # 入力と出力を宣伝
    X = tf.placeholder(tf.float32, shape=[4,2])
    y = tf.placeholder(tf.float32, shape=[4,1])

    # パラメータを初期化:重みが[-1.0,1.0]の間のランダムな値、バイアスが全て0.0
    W1 = tf.Variable(tf.random_uniform([2,2], -1.0, 1.0))
    b1 = tf.Variable(tf.zeros([2]))

    W2 = tf.Variable(tf.random_uniform([2,1], -1.0, 1.0))
    b2 = tf.Variable(tf.zeros([1]))

    # 予測値を計算
    y_predict = tf_prediction(X,W1,b1,W2,b2)
    
    # 平均2乗誤差を計算
    loss = tf.reduce_mean(tf.square(y_predict - y))
    
    # 平均2乗誤差を最小化
    optimizer = tf.train.GradientDescentOptimizer(0.1).minimize(loss)

# 学習させる
with tf.Session(graph=graph) as sess:
    sess.run(tf.initialize_all_variables())
    feed_dict = {X : train_dataset, y : train_labels}

    for step in range(1001):
        _, l, predictions = sess.run([optimizer, loss, y_predict], feed_dict=feed_dict)

        if step % 200 == 0:
            print('Loss at step %d: %f ' % (step,l))

# 最後の予測出力をプリント
print("Final predictions:")
print(predictions)

結果

パラメータの初期値がランダムなのでロスがいろいろな値に収束しました。

うまくいく例

Loss at step 0: 0.500307 
Loss at step 200: 0.232446 
Loss at step 400: 0.157888 
Loss at step 600: 0.004861 
Loss at step 800: 0.000007 
Loss at step 1000: 0.000000 
Final predictions:
[[  1.38186124e-06]
 [  9.99999106e-01]
 [  9.99999106e-01]
 [  4.06278104e-07]]

最後の予測値は [0,1,1,0]と非常に近いですね。

求めた関数  \hat{f}を図形してみます。

f:id:glpgsinc:20160728173727p:plain

ちゃんと全ての入力点を通っているようにみえますね!

うまくいかない例

一番確率高いのはロスが0.25に収束しました。

Loss at step 0: 0.500088 
Loss at step 200: 0.250000 
Loss at step 400: 0.250000 
Loss at step 600: 0.250000 
Loss at step 800: 0.250000 
Loss at step 1000: 0.250000 
Final predictions:
[[ 0.49999994]
 [ 0.49999994]
 [ 0.49999994]
 [ 0.49999994]]

予測結果が全て0.5になりますね。求めた関数  \hat{f}を図形すると、こうなります。

f:id:glpgsinc:20160728174457p:plain

入力依存せず全て0.5を出力する関数ですね。

他の収束値もいろいろありました。

Loss at step 0: 0.499994 
Loss at step 200: 0.183986 
Loss at step 400: 0.125485 
Loss at step 600: 0.125000 
Loss at step 800: 0.125000 
Loss at step 1000: 0.125000 

Final predictions:
[[  4.99999911e-01]
 [  4.99999911e-01]
 [  9.99999881e-01]
 [  1.78813934e-07]]
Loss at step 0: 0.500204 
Loss at step 200: 0.249998 
Loss at step 400: 0.249468 
Loss at step 600: 0.188922 
Loss at step 800: 0.166667 
Loss at step 1000: 0.166667 
Final predictions:
[[  6.66666329e-01]
 [  6.66666329e-01]
 [  6.66666329e-01]
 [  5.36441803e-07]]
Loss at step 0: 0.499941 
Loss at step 200: 0.188342 
Loss at step 400: 0.166667 
Loss at step 600: 0.166667 
Loss at step 800: 0.166667 
Loss at step 1000: 0.166667 
Final predictions:
[[ 0.33333343]
 [ 1.        ]
 [ 0.33333343]
 [ 0.33333343]]

考察

いろいろ試した結果、ロスの最小値は0.0だとわかりました。但し、最小点以外に停留点がたくさんありますね。 では、ロス関数を振り返しますと、

$$ J(\mathbf{\theta}) = \frac{1}{4} \sum_{\mathbf{x} \in \mathbf{X}} (f(\mathbf{x}) - \hat{f}(\mathbf{x};\mathbf{\theta}))^2 $$

なので、偏微分

$$ \frac{\partial J(\mathbf{\theta})}{\partial \theta_i} = \frac{1}{2} \sum_{\mathbf{x} \in \mathbf{X}} (\hat{f}(\mathbf{x};\mathbf{\theta} - f(\mathbf{x}))) \frac{\partial \hat{f}(\mathbf{x};\mathbf{\theta})}{\partial \theta_i} $$

になります。 \hat{f}(\mathbf{x};\mathbf{\theta}) = 0.5 \forall (\mathbf{x},\mathbf{\theta}) なら、 \frac{\partial f}{\partial \theta_i} = 0 \forall i になり、 \frac{\partial J(\mathbf{\theta})}{\partial \theta_i} が0になることがわかります。勾配が0になると、最急降下法でパラメータの更新ができなくなりますね。その結果、停留点に止まります。運がよければ最小点に止まるし、運が悪ければ他の点に止まります。

最初に停留点は極小点だと思いましたが、この論文*2によると、XOR問題のロス関数には最小点以外の停留点は全て鞍点だそうです。

局所的な極小点・鞍点に収束するのは最急降下法の古典な問題で、回避するために、複数の初期値から探索を行うなどの対策が必要です。例えば、

 \mathbf{W_1} = [[0.1,0.0],[0.0,0.1]], \mathbf{W_1} = [[0.1],[0.0]]、バイアスが全て0に初期化したら、

Loss at step 0: 0.495050 
Loss at step 100: 0.250069 
Loss at step 200: 0.250051 
Loss at step 300: 0.250039 
Loss at step 400: 0.250031 
Loss at step 500: 0.250025 
Loss at step 600: 0.249973 
Loss at step 700: 0.245165 
Loss at step 800: 0.185728 
Loss at step 900: 0.080708 
Loss at step 1000: 0.000572 
Loss at step 1100: 0.000001 
Loss at step 1200: 0.000000 
Loss at step 1300: 0.000000 
Loss at step 1400: 0.000000 
Loss at step 1500: 0.000000 

ちゃんと最小点までに行けました。

ところで、この結果のステップ100~700を注目してください。ロスがずっと0.25周辺に、下がる速度が非常に遅いです。上の失敗結果を参考に、この0.25は恐らく鞍点だと思われます。今の初期値で、鞍点から脱出できましたが、非常に時間がかかるのがわかりました。

局所的な極小点・鞍点は小次元パラメータ空間では難問ですが、幸いにも高次元パラメータ空間では問題にならないようです。まぁ、学習速度が落ちるだけです。 この論文*3によると、大きいネットワークだと、ほとんどの局所的な極小点はテストデータセットに対して大体同じ性能がでます。さらに、"悪い"極小点に収束確率はネットワークサイズと逆比例だそうです。さらに、面白いことに、最小点に収束すると過学習になるケースが多いようです。

そこで、ネットワークサイズを上げてみます。隠れ層を1つ増やして2層になり、ユニット数がどちらも128にしました。パラメータの初期値を変えずに (重みは[-0.1, 0.1]の間のランダム、バイアスは全て0) 毎回ロスが0.0に行けました。最小値に行きやすくなるのが実感できました。もちろん、局所的な極小点・鞍点問題は完全に解決できないです。例えば、重みが全部0より大きい値に初期化すると、また0.25に収束します。初期値によって収束先が全然違いますので、やはり初期値の選び方が大事ですね!

他の局所的な極小点・鞍点問題対策として、(バッチ)勾配降下法の代わりに確率的勾配降下法がります。それを使うと、計算量が減る、かつ、局所的な極小点・鞍点から脱出できるという説があります。但し、今回の学習データは非常に少なく、あまり役に立ちませんでした。

まとめ

今回はXOR問題をTensorFlowで考察しました。XOR問題は単純ですが、小さいニューラルネットワークだと鞍点に収束しやすいのがわかりました。また、ディープラーニングの実装で、初期値は凄く大事だと実感できました。

最近、ガラパゴス社内では

All you need is a good init!*4

という句が流行っています。初期値は重要なハイパーパラメータだと考えられます。

以上となります。

今回のソースコードは全てGitHubに公開しました。

最後に、株式会社ガラパゴスでは、新しい技術が好きな方を絶賛大募集中です!

RECRUIT | 株式会社ガラパゴス iPhone/iPad/Androidのスマートフォンアプリ開発

参考文献

*1:Goodfellow et al. Deep Learning Book p170-176, 2016. http://www.deeplearningbook.org/

*2:Ida Sprinkhuizen-Kuyper et al. The error surface of the 2-2-1 XOR network: The finite stationary points. Neural networks: the official journal of the International Neural Network Society 11(4) p683-690, July 1998. https://www.researchgate.net/publication/10832860_The_error_surface_of_the_2-2-1_XOR_network_The_finite_stationary_points

*3:Anna Choromanska et al. The Loss Surfaces of Multilayer Networks, 2014. https://arxiv.org/abs/1412.0233

*4:Dmytro Mishkin et al. All you need is a good init, 2015. http://arxiv.org/abs/1511.06422