- XORってなに？
- 単層のパーセプトロンだとXORを表現できないの？
- 2層のパーセプトロンでXORを表現したい…
こんにちは！しゅんです！
今回はXORについて解説していきます！またpythonでの実装方法についても解説します！
それではやっていきましょう！
普段は組合せ最適化の記事を書いてたりします。
ぜひ他の記事も読んでみてください！
このブログの簡単な紹介はこちらに書いてあります。
興味があったら見てみてください。
このブログでは経営工学を勉強している現役理系大学生が、経営工学に関することを色々話していきます！
ぼくが経営工学を勉強している中で感じたことや、興味深かったことを皆さんと共有出来たら良いなと思っています。
そもそも経営工学とは何なのでしょうか。Wikipediaによると
経営工学（けいえいこうがく、英: engineering management）は、人・材料・装置・情報・エネルギーを総合したシステムの設計・改善・確立に関する活動である。そのシステムから得られる結果を明示し、予測し、評価するために、工学的な分析・設計の原理・方法とともに、数学、物理および社会科学の専門知識と経験を利用する。
引用元 : 経営工学 – Wikipedia
長々と書いてありますが、要は経営、経済の課題を理系的な観点から解決する学問です。
パーセプトロンってなに？
ここでは2変数の論理演算をパーセプトロンで表現することに関係する内容を中心に説明します。パーセプトロンのより詳しい説明は別の記事でしているので、気になる方はぜひそちらも見てみてください！
\\\ パーセプトロンの詳しい解説はこちらから！ ///
入力が2つの場合のパーセプトロン
例えば\(x_1,x_2\)の2つがパーセプトロンに入力されたとします。このときパーセプトロンではこの2つの入力に、自分で設定した重み\(w_1,w_2\)を掛け算して足します。
この計算で得られたものを\(a\)とすると
\(a = w_1x_1+w_2x_2\)
となります。例えば\((x_1,x_2)=(1,2)\)が入力され、重みを\((w_1,w_2)=(3,4)\)と設定したとき
\(a = 3\times1+4\times2=11\)
と計算できます。そしてこの\(a\)が、自分で設定する\(\theta\)より大きかったら1、そうでなかったら0を返すのがパーセプトロンです。例えば\(a=11\)で\(\theta = 8\)と設定したとき
\(a = 11 > 8 = \theta\)
となるのでパーセプトロンは1を返します。
\( a = w_1x_1 + w_2x_2\)なので
\( w_1x_1+w_2x_2 > \theta \; \to 1\text{を返す}\)
\( w_1x_1+w_2x_2 \leq \theta \; \to 0\text{を返す}\)
となります。ここで\(\theta\)を右辺に移項すると
\( w_1x_1+w_2x_2-\theta > 0 \; \to 1\text{を返す}\)
\( w_1x_1+w_2x_2-\theta \leq 0 \; \to 0\text{を返す}\)
となります。さらに\(-\theta = b\)とすると
\( w_1x_1+w_2x_2+b > 0 \; \to 1\text{を返す}\)
\( w_1x_1+w_2x_2+b \leq 0 \; \to 0\text{を返す}\)
となります。ここで登場する\(b\)はバイアスと呼ばれます。この後pythonで実装するときは\(\theta\)ではなく\(b\)を使って実装していきます。
パーセプトロンで論理演算を表現できる
パーセプトロンを使えばいくつかの論理演算は表現することができます。
\((w_1,w_2)=(5,5), b = -7\)
\((w_1,w_2)=(5,5), b = -2\)
上図の左側はパーセプトロンでANDを表現した図で、右側はパーセプトロンでORを表現した図です。それぞれ重みとバイアスを
\(\text{AND} \to (w_1,w_2)=(5,5), b = -7\)
\(\text{OR} \to (w_1,w_2)=(5,5), b = -2\)
と設定すればANDとORを実装することができます。このように重みとバイアスを適切に設定することで、いくつかの論理演算はパーセプトロンで表現することができます。より正確に説明すると
直線で演算結果を分離できる論理演算は（単層の）パーセプトロンで表現できる
となります。ANDとORは上図から分かるように直線で演算結果を分離できていますね。
\\\ 詳しい話は下の記事で解説しています！ ///
XORってなに？
XORは論理演算の1つ
XOR（排他的論理和）は0か1しか取らない \(x_1,x_2\) を入力したときに上図のように出力をする論理演算です。具体的には
\((x_1,x_2)=(0,0)\text{を入力} \to 0\text{を返す}\)
\((x_1,x_2)=(1,0)\text{を入力} \to 1\text{を返す}\)
\((x_1,x_2)=(0,1)\text{を入力} \to 1\text{を返す}\)
\((x_1,x_2)=(1,1)\text{を入力} \to 0\text{を返す}\)
という演算です。これは\(x_1,x_2\)が異なる値を取るときに1を返し、同じ値を取るときに0を返すという演算を表しています。
上図はXORをグラフで表したものです。\((x_1,x_2)=(1,0)\)または\((x_1,x_2)=(0,1)\)のとき1で青〇になっていますが、\((x_1,x_2)=(0,0)\)のときまたは\((x_1,x_2)=(1,1)\)のとき0で赤×になっています。
\\\ XOR（排他的論理和）の詳しい説明はこちらから！ ///
XORは単層のパーセプトロンでは表現できない
単層のパーセプトロンを使えば領域を直線で分離することができます。しかしXORの演算結果を考えてみると、どんな直線でも演算結果を分離することができないことが分かります。
しかし単層のパーセプトロンは直線での分離しかできないので、上図のような曲線をパーセプトロンで表現することはできません。
数式を使って単層のパーセプトロンでXORを表現することができないことを確かめてみましょう。今重みを\((w_1,w_2)\)、バイアスを\(b\)とします。XORは\((x_1,x_2)\)を入力したときの出力値がそれぞれ
\((x_1,x_2)=(0,0) \to 0\text{を出力}\)
\((x_1,x_2)=(1,0) \to 1\text{を出力}\)
\((x_1,x_2)=(0,1) \to 1\text{を出力}\)
\((x_1,x_2)=(1,1) \to 0\text{を出力}\)
となります。またパーセプトロンの出力値は
\(w_1x_1+w_2x_2+b >0 \to 1\text{を出力}\)
\(w_1x_1+w_2x_2+b \leq0 \to 0\text{を出力}\)
となります。従ってXORを単層のパーセプトロンで表現するためには
\((x_1,x_2)=(0,0) \to w_1\times0+w_2\times0+b=b\leq0\)
\((x_1,x_2)=(1,0) \to w_1\times1+w_2\times0+b=w_1+b>0\)
\((x_1,x_2)=(0,1) \to w_1\times0+w_2\times1+b=w_2+b>0\)
\((x_1,x_2)=(1,1) \to w_1\times1+w_2\times1+b=w_1+w_2+b\leq0\)
の4つの不等式を満たす\(w_1,w_2,b\)を見つける必要があります。2つ目の式の\(w_1+b>0\)より\(w_1>-b\)、3つ目の式の\(w_2+b>0\)より\(w_2>-b\)が成立します。よって4つ目の式は
\(0\geq w_1+w_2+b>-b-b+b=-b\)
となるので\(b>0\)が成立する必要があります。一方で1つ目の式から\(b\leq0\)が成り立つ必要があり、この2つの式を同時に満たす\(b\)は存在しません。
以上のことからXORを単層のパーセプトロンで表現できないことが示せました。
\\\ 詳しいことはこの記事で話しています！ ///
論理演算を組み合わせてXORを表現する
この記事の目的はXORを2層のパーセプトロンで表現することですが、それを達成するために
単層のパーセプトロンで表現できる論理演算を組み合わせてXORを表現する
ということをやっていきます。
例えば論理演算1と論理演算2の結果を使って論理演算3を実行したらXORを表現することができたとします。もしこれらの論理演算が全て単層のパーセプトロンで表現できる場合、上図のように
第0層～第1層：論理演算1と論理演算2を実装
第1層～第2層：論理演算3を実装
という構造にすることで、2層のパーセプトロンでXORを表現することができます。
パターン 1
例えば上図のように、まずORとNANDを計算します。ORとNANDの演算結果はそれぞれ
ORの演算結果
\((x_1,x_2)=(0,0)\to0\text{を返す}\)
\((x_1,x_2)=(0,1)\to1\text{を返す}\)
\((x_1,x_2)=(1,0)\to1\text{を返す}\)
\((x_1,x_2)=(1,1)\to1\text{を返す}\)
NANDの演算結果
\((x_1,x_2)=(0,0)\to1\text{を返す}\)
\((x_1,x_2)=(0,1)\to1\text{を返す}\)
\((x_1,x_2)=(1,0)\to1\text{を返す}\)
\((x_1,x_2)=(1,1)\to0\text{を返す}\)
となります。そしてこのORとNANDの演算結果を使ってANDを計算すると
\((x_1,x_2)=(0,0) \to (\text{OR},\text{NAND})=(0,1) : \text{AND} \to 0\text{を返す}\)
\((x_1,x_2)=(1,0) \to (\text{OR},\text{NAND})=(1,1) : \text{AND} \to 1\text{を返す}\)
\((x_1,x_2)=(0,1) \to (\text{OR},\text{NAND})=(1,1) : \text{AND} \to 1\text{を返す}\)
\((x_1,x_2)=(1,1) \to (\text{OR},\text{NAND})=(1,0) : \text{AND} \to 0\text{を返す}\)
となりXORを表現できていることが分かります。ORもNANDもANDも単層のパーセプトロンで表現できるので、1層目でORとNAND、2層目でANDを計算すれば2層のパーセプトロンでXORを表現することができるはずです。
XOR（排他的論理和）を論理和\(\vee\)と論理積\(\wedge\)と否定\(\bar{x}\)を使って表すと
\((x_1\wedge\bar{x}_2)\vee(\bar{x}_1\wedge x_2)\)
となります。またORとNANDはそれぞれ
OR : \(x_1\vee x_2\)
NAND : \(\overline{x_1\wedge x_2}=\bar{x}_1\vee\bar{x}_2\)
とります。従ってORとNANDの演算結果をANDでくっつけると
\((x_1\vee x_2)\wedge(\bar{x}_1\vee\bar{x}_2)\)
\(=(x_1\wedge\bar{x}_1)\vee(x_1\wedge\bar{x}_2)\vee(\bar{x}_1\wedge x_2)\vee(\bar{x}_2\wedge x_2)\)
\(=0\vee(x_1\wedge\bar{x}_2)\vee(\bar{x}_1\wedge x_2)\vee0\)
\(=(x_1\wedge\bar{x}_2)\vee(\bar{x}_1\wedge x_2)\)
となりXORを表現できることが分かりました。
パターン 2
例えば上図のように、まずNORとANDを計算します。NORとANDの演算結果はそれぞれ
NORの演算結果
\((x_1,x_2)=(0,0)\to1\text{を返す}\)
\((x_1,x_2)=(0,1)\to0\text{を返す}\)
\((x_1,x_2)=(1,0)\to0\text{を返す}\)
\((x_1,x_2)=(1,1)\to0\text{を返す}\)
ANDの演算結果
\((x_1,x_2)=(0,0)\to0\text{を返す}\)
\((x_1,x_2)=(0,1)\to0\text{を返す}\)
\((x_1,x_2)=(1,0)\to0\text{を返す}\)
\((x_1,x_2)=(1,1)\to1\text{を返す}\)
となります。そしてこのNORとANDの演算結果を使ってNORを計算すると
\((x_1,x_2)=(0,0) \to (\text{NOR},\text{AND})=(1,0) : \text{NOR} \to 0\text{を返す}\)
\((x_1,x_2)=(1,0) \to (\text{NOR},\text{AND})=(0,0) : \text{NOR} \to 1\text{を返す}\)
\((x_1,x_2)=(0,1) \to (\text{NOR},\text{AND})=(0,0) : \text{NOR} \to 1\text{を返す}\)
\((x_1,x_2)=(1,1) \to (\text{NOR},\text{AND})=(0,1) : \text{NOR} \to 0\text{を返す}\)
となりXORを表現できていることが分かります。NORもANDも単層のパーセプトロンで表現できるので、1層目でNORとAND、2層目でNORを計算すれば2層のパーセプトロンでXORを表現することができるはずです。
XOR（排他的論理和）を論理和\(\vee\)と論理積\(\wedge\)と否定\(\bar{x}\)を使って表すと
\((x_1\wedge\bar{x}_2)\vee(\bar{x}_1\wedge x_2)\)
となります。またNORとANDはそれぞれ
NOR : \(\overline{x_1\vee x_2}=\bar{x}_1\wedge\bar{x}_2\)
AND : \(x_1\wedge x_2\)
とります。従ってNORとANDの演算結果をNORでくっつけると
\(\overline{(\bar{x}_1\wedge \bar{x}_2)\vee(x_1\wedge x_2)}\)
\(=\overline{(\bar{x}_1\wedge \bar{x}_2)}\wedge\overline{(x_1\wedge x_2)}\)
\(=(x_1\vee x_2)\wedge(\bar{x}_1\vee \bar{x}_2)\)
\(=(x_1\wedge\bar{x}_1)\vee(x_1\wedge\bar{x}_2)\vee(\bar{x}_1\wedge x_2)\vee(\bar{x}_2\wedge x_2)\)
\(=0\vee(x_1\wedge\bar{x}_2)\vee(\bar{x}_1\wedge x_2)\vee0\)
\(=(x_1\wedge\bar{x}_2)\vee(\bar{x}_1\wedge x_2)\)
となりXORを表現できることが分かりました。
XORを2層のパーセプトロンで表現する
それでは第5章で紹介した2つのパターンを実際にパーセプトロンで表現していきます。具体的には
1つ目の論理演算：\(w_{11}^{(1)},w_{21}^{(1)}\) 及びバイアス \(b_1^{(1)}\) を使って表現
2つ目の論理演算：\(w_{12}^{(1)},w_{22}^{(1)}\) 及びバイアス \(b_2^{(1)}\) を使って表現
3つ目の論理演算：\(w_{1}^{(2)},w_{2}^{(2)}\) 及びバイアス \(b^{(2)}\) を使って表現
上記のことを考えていきます。それではXORを表現できるように重みとバイアスをそれぞれ設定していきましょう。
パターン1
パターン1で使う論理演算は
1つ目の論理演算：OR
2つ目の論理演算：NAND
3つ目の論理演算：AND
でした。それぞれ重みとバイアスを設定していきます。結論以下のように重みとバイアスを設定すればXORを表現できます。
1つ目：\((w_{11}^{(1)},w_{21}^{(1)})=(5,5),b_1^{(1)}=-2\)
2つ目：\((w_{12}^{(1)},w_{22}^{(1)})=(-2,-2),b_2^{(1)}=3\)
3つ目：\((w_{1}^{(2)},w_{2}^{(2)})=(5,5),b^{(2)}=-7\)
1つずつ解説していきます。
1つ目の論理演算：ORを表現する
ORを表現するためには例えば
\((w_{11}^{(1)},w_{21}^{(1)})=(5,5),b_1^{(1)}=-2\)
とすれば良いです。このとき直線の方程式は
\(w_{11}^{(1)}x_1+w_{21}^{(1)}x_2+b_1^{(1)}=0 \to 5x_1+5x_2-2=0\)
となります。4点をそれぞれ入力してみると
\((x_1,x_2)=(0,0) : 5\times0+5\times0-2=-2\leq0 \to 0\text{を返す}\)
\((x_1,x_2)=(1,0) : 5\times1+5\times0-2=3>0 \to 1\text{を返す}\)
\((x_1,x_2)=(0,1) : 5\times0+5\times1-2=3>0 \to 1\text{を返す}\)
\((x_1,x_2)=(1,1) : 5\times1+5\times1-2=8>0 \to 1\text{を返す}\)
となり、ORを実装できています。\((w_{1}^{(2)},w_{2}^{(2)})=(5,5),b^{(2)}=-7\) のときの境界をグラフにすると下図のようになります。
2つ目の論理演算：NANDを表現する
NANDを表現するためには例えば
\((w_{12}^{(1)},w_{22}^{(1)})=(-2,-2),b_2^{(1)}=3\)
とすれば良いです。このとき直線の方程式は
\(w_{12}^{(1)}x_1+w_{22}^{(1)}x_2+b_2^{(1)}=0 \to -2x_1-2x_2+3=0\)
となります。4点をそれぞれ入力してみると
\((x_1,x_2)=(0,0) : -2\times0-2\times0+3=3>0 \to 1\text{を返す}\)
\((x_1,x_2)=(1,0) : -2\times1-2\times0+3=1>0 \to 1\text{を返す}\)
\((x_1,x_2)=(0,1) : -2\times0-2\times1+3=1>0 \to 1\text{を返す}\)
\((x_1,x_2)=(1,1) : -2\times1-2\times1+3=-1\leq0 \to 0\text{を返す}\)
となり、NANDを実装できています。\((w_{12}^{(1)},w_{22}^{(1)})=(-2,-2),b_2^{(1)}=-3\) のときの境界をグラフにすると下図のようになります。
3つ目の論理演算：ANDを表現する
ANDを表現するためには例えば
\((w_{1}^{(2)},w_{2}^{(2)})=(5,5),b^{(2)}=-7\)
とすれば良いです。このとき直線の方程式は
\(w_{1}^{(2)}x_1+w_{2}^{(2)}x_2+b^{(2)}=0 \to 5x_1+5x_2-7=0\)
となります。4点をそれぞれ入力してみると
\((x_1,x_2)=(0,0) : 5\times0+5\times0-7=-7\leq0 \to 0\text{を返す}\)
\((x_1,x_2)=(1,0) : 5\times1+5\times0-7=-2\leq0 \to 0\text{を返す}\)
\((x_1,x_2)=(0,1) : 5\times0+5\times1-7=-2\leq0 \to 0\text{を返す}\)
\((x_1,x_2)=(1,1) : 5\times1+5\times1-7=3>0 \to 1\text{を返す}\)
となり、ORを実装できています。\((w_{11}^{(1)},w_{21}^{(1)})=(5,5),b_1^{(1)}=-2\) のときの境界をグラフにすると下図のようになります。
パターン2
パターン2で使う論理演算は
1つ目の論理演算：NOR
2つ目の論理演算：AND
3つ目の論理演算：NOR
でした。それぞれ重みとバイアスを設定していきます。結論以下のように重みとバイアスを設定すればXORを表現できます。
1つ目：\((w_{11}^{(1)},w_{21}^{(1)})=(-2,-2),b_1^{(1)}=1\)
2つ目：\((w_{12}^{(1)},w_{22}^{(1)})=(5,5),b_2^{(1)}=-7\)
3つ目：\((w_{1}^{(2)},w_{2}^{(2)})=(-2,-2),b^{(2)}=1\)
考え方はパターン1と同じなので説明は省略します。
XORをpythonで実装する
それでは最後にXORをpythonで実装していきましょう。結論以下のコードでXORを実装することができます。
## 事前準備
import numpy as np # numpyをインポート
## XORの定義
def XOR(x):
# OR用の重みとバイアスを設定
w_OR = np.array([5,5]) # 重みを設定
b_OR = -2 # バイアスを設定
# NAND用の重みとバイアスを設定
w_NAND = np.array([-2,-2]) # 重みを設定
b_NAND = 3 # バイアスを設定
# AND用の重みとバイアスを設定
w_AND = np.array([5,5]) # 重みを設定
b_AND = -7 # バイアスを設定
# 1層目の計算
weighted_sum_OR = np.dot(w_OR, x) + b_OR # OR用の重み付き和を計算
weighted_sum_NAND = np.dot(w_NAND, x) + b_NAND #NAND用の重み付き和を計算
y_OR = 1 if weighted_sum_OR > 0 else 0 # OR用の重み付き和が0より大きかったら1、そうでないなら0を返す
y_NAND = 1 if weighted_sum_NAND > 0 else 0 # NAND用の重み付き和が0より大きかったら1、そうでないなら0を返す
y = np.array([y_OR, y_NAND]) # 1層目の計算結果を保存
# 2層目の計算
weighted_sum_AND = np.dot(w_AND, y) + b_AND # AND用の重み付き和を計算
return 1 if weighted_sum_AND > 0 else 0 # AND用の重み付き和が0より大きかったら1、そうでないなら0を返す
## 結果の確認
x_list = [np.array([0,0]),np.array([0,1]),np.array([1,0]),np.array([1,1])]
for x in x_list:
print(f"(x1, x2) = {(x[0],x[1])}：{XOR(x)}を返す")
このコードを実行したら上図の結果が得られました。1つずつ解説していきます。
コードの解説
事前準備
## 事前準備
import numpy as np # numpyをインポート
事前準備としてnumpyをインポートします。numpyは数値計算を高速に行うために使います。
XORの定義
## XORの定義
def XOR(x):
# OR用の重みとバイアスを設定
w_OR = np.array([5,5]) # 重みを設定
b_OR = -2 # バイアスを設定
# NAND用の重みとバイアスを設定
w_NAND = np.array([-2,-2]) # 重みを設定
b_NAND = 3 # バイアスを設定
# AND用の重みとバイアスを設定
w_AND = np.array([5,5]) # 重みを設定
b_AND = -7 # バイアスを設定
# 1層目の計算
weighted_sum_OR = np.dot(w_OR, x) + b_OR # OR用の重み付き和を計算
weighted_sum_NAND = np.dot(w_NAND, x) + b_NAND #NAND用の重み付き和を計算
y_OR = 1 if weighted_sum_OR > 0 else 0 # OR用の重み付き和が0より大きかったら1、そうでないなら0を返す
y_NAND = 1 if weighted_sum_NAND > 0 else 0 # NAND用の重み付き和が0より大きかったら1、そうでないなら0を返す
y = np.array([y_OR, y_NAND]) # 1層目の計算結果を保存
# 2層目の計算
weighted_sum_AND = np.dot(w_AND, y) + b_AND # AND用の重み付き和を計算
return 1 if weighted_sum_AND > 0 else 0 # AND用の重み付き和が0より大きかったら1、そうでないなら0を返す
2行目でXORを関数として定義しています。関数の名前は「XOR」、引数は「x」です。
4～5行目ではORを表現するための重み「w_OR」とバイアス「b_OR」を設定しています。
7～8行目ではNANDを表現するための重み「w_NAND」とバイアス「b_NAND」を設定しています。
10～11行目ではANDを表現するための重み「w_AND」とバイアス「b_AND」を設定しています。
12～16行目でパーセプトロンの1層目を設定しています。具体的には
12行目：OR用の重み付き和を計算
13行目：NAND用の重み付き和を計算
14行目：OR用の重み付き和が0より大きかったら1、そうでないなら0を返す
15行目：NAND用の重み付き和が0より大きかったら1、そうでないなら0を返す
ということを行っています。
18～19行目でパーセプトロンの2層目を設定しています。具体的には
18行目：AND用の重み付き和を計算
19行目：AND用の重み付き和が0より大きかったら1、そうでないなら0を返す
ということを行っています。
結果の確認
## 結果の確認
x_list = [np.array([0,0]),np.array([0,1]),np.array([1,0]),np.array([1,1])]
for x in x_list:
print(f"(x1, x2) = {(x[0],x[1])}：{XOR(x)}を返す")
2行目でXOR関数に入力する値をリスト形式で設定しています。リストの名前は「x_list」で、各要素は左から順に\((x_1,x_2)=(0,0),(0,1),(1,0),(1,1)\)を表しています。
3行目ではfor文を使ってx_list中の要素を1つずつ取り出しています。取り出した要素は「x」としています。具体的には
1回目の反復：「x = np.array(0,0)」
2回目の反復：「x = np.array(0,1)」
3回目の反復：「x = np.array(1,0)」
4回目の反復：「x = np.array(1,1)」
となります。
4行目で結果を出力しています。
結果の解釈
上記のコードを実行したら上図のような結果が得られました。これを見ると
\((x_1,x_2)=(0,0)\text{を入力} \to 0\text{を返す}\)
\((x_1,x_2)=(0,1)\text{を入力} \to 1\text{を返す}\)
\((x_1,x_2)=(1,0)\text{を入力} \to 1\text{を返す}\)
\((x_1,x_2)=(1,1)\text{を入力} \to 0\text{を返す}\)
となり、これはXORの演算結果と一致していますね。ということでXORを表現することができました。
おわりに
いかがでしたか。
今回の記事ではXORと多層パーセプトロンについて解説しました。
今後もこのようなAIに関する記事を書いていきます！
最後までこの記事を読んでくれてありがとうございました。
参考文献
