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

Coding Memos

try {coding} catch {questions}

単層パーセプトロンが表現しきれないもの【ゼロ作DL_8】

ゼロ作DL 学習ログ Deep Learning

少しずつDeep Learningの核心に迫ってるようで、面白くなって来ました。

本稿の学習記録は、パーセプトロンの限界という項目について。

AND, NAND, ORはパーセプトロンで表現できた

ここまでに、論理ゲートのAND, NAND, ORは表現できたのですが、基本情報技術者試験をちょろっと勉強した時に、 そういえばXORとかもあったような・・・と思いました。

Wikipedia論理回路のページを覗いてみると、確かにXOR(Exclusive OR: 排他的論理和)はあります。

論理回路 - Wikipedia

他にも、NOT, NORなどがありますが、NANDが実装できているわけですから、NOTもORにNOTを組み込んだNORも原理的には実装できるはずです。({w_n}{b} の符号を反転すれば。)

ここで異色なのがXORということになるでしょうね。 ここで、XORはExclusive ORですから、ORをもとに、どうExclusiveなのかまとめておきます。

OR

$$x_1$$ $$x_2$$ $$y$$
0 0 0
0 1 1
1 0 1
1 1 1

ORの場合は一つでも1の入力があれば、1が出力されるのでした。

対してXORは

XOR

$$x_1$$ $$x_2$$ $$y$$
0 0 0
0 1 1
1 0 1
1 1 0

入力のうちひとつが、1の場合のみ、出力が1になるという論理回路です。自分以外の1を認めないあたり、排他的です。ね。

この論理回路ってどんなときにそうかなーと考えたのですが、 ちょうど電車の分岐点がXORゲートかなぁと感じました。

f:id:codingmemos:20170302013214j:plain

{x_1}{x_2}から同時に電車が進入する時、分岐点で確実に衝突しますよね。どちらか一方からしか電車は進入できないので、ちょうどこれはXORゲートと同様の入出力形態になるかなと考えました。

XORが表現できない

本書では可視化されててわかりやすいので、買ってみてくださいw

つまり、線形ではXORを境界で分けられず、曲線(非線形)ではわけられると書かれています。

じゃあ多層だ

というわけで、一回パーセプトロンアルゴリズムに通すだけでは、XORは表現できないので、二回以上でできないかなと考えるわけですね。

$$x_1$$ $$x_2$$ $$s_1$$ $$s_2$$ $$y$$
0 0 ? ? 0
0 1 ? ? 1
1 0 ? ? 1
1 1 ? ? 0

ちょっと試しにAND, OR, NANDのゲートを入れ込んでみましょう。物は試しですしね。

{AND(s_1, s_2) \to y}

{NAND(s_1, s_2) \to y}

{OR(s_1, s_2) \to y}

のどれか。

*下表中のorで区切られたセルは、左側を選ぶなら、どのセルもorの左側を選ぶように読んでいただければと思います。(逆も然り)

ANDの場合(入力がともに1の場合のみ1を出力)

$$s_1$$ $$s_2$$ $$y$$
0 or 1 1 or 0 0
1 1 1
1 1 1
1 or 0 0 or 1 0

NANDの場合(入力が1、1以外の場合は1を出力)

$$s_1$$ $$s_2$$ $$y$$
1 1 0
1 or 0 0 or 1 1
0 or 1 1 or 0 1
1 1 0

ORの場合(少なくとも入力のどちらかが1であれば1を出力)

$$s_1$$ $$s_2$$ $$y$$
0 0 0
1 or 0 0 or 1 1
0 or 1 1 or 0 1
0 0 0

{s_1, s_2} ともに、さらにその前段階で、論理ゲートを通ってくるわけですから、NANDとORの{s_1, s_2}は、このような値を取らないことがわかると思います。このような出力パターンをみせる論理ゲートはありませんでしたね。

codingmemos.hatenablog.com

なので、

{AND(s_1, s_2) \to y}

が第二層目のパーセプトロンだとわかります。

では第一層目は何かというと{s_1, s_2}のパターンを見れば見当がつきます。

上記AND表の、or左側を選んだパターンだとすると、

$$s_1$$ $$s_2$$ $$y$$
0 1 0
1 1 1
1 1 1
1 0 0

ですから、

{OR(x_1, x_2) \to s_1}

{NAND(x_1, x_2) \to s_2}

となりますね。(数学的に矢印の使い方など間違ってたらすみません・・・イメージで矢印使ってます。)

なので、二層パーセプトロンであればXORはあらわせそうです。

むりやり押し込むと、

{AND\left(OR(x_1, x_2), NAND(x_1, x_2)\right) \to y}

となります。これをこのままスクリプトで書けばいいですね。

# arraylogiccircuit.py
import numpy as np

def AND(x1, x2):
  x = np.array([x1, x2])
  w = np.array([.5, .5])
  b = -.7
  tmp = np.sum(x*w) + b
  if tmp <= 0:
    return 0
  elif tmp > 0:
    return 1

def NAND(x1, x2):
  x = np.array([x1, x2])
  w = np.array([-.5, -.5])
  b = .7
  tmp = np.sum(x*w) + b
  if tmp <= 0:
    return 0
  elif tmp > 0:
    return 1

def OR(x1, x2):
  x = np.array([x1, x2])
  w = np.array([1, 1])
  b = -.7
  tmp = np.sum(x*w) + b
  if tmp <= 0:
    return 0
  elif tmp > 0:
    return 1

def XOR(x1, x2):
  s1 = OR(x1, x2)
  s2 = NAND(x1, x2)
  y = AND(s1, s2)
  return y

として

>>> import arraylogiccircuit as alc
>>> alc.XOR(0,0)
0
>>> alc.XOR(0,1)
1
>>> alc.XOR(1,0)
1
>>> alc.XOR(0,0)
0

とちゃんとXORゲートが表現できていますね!

やったぜ。

というわけで、層が深くなると、パーセプトロンは基本的な論理ゲートを網羅することができると言えそうです。

余談として?

NANDゲートでコンピュータは作られてるらしい。 ちょっとこの辺も本書が終わった後にしらべたいところです。 これ↓がオススメされてた。次の課題になりそうです。