249 Views
May 02, 24
スライド概要
AI・機械学習を勉強したい学生たちが集まる、京都大学の自主ゼミサークルです。私たちのサークルに興味のある方はX(Twitter)をご覧ください!
2024年度前期輪読会#2「ゼロから作るDeep Learning」 2章 パーセプトロン 2.4~2.7 京都大学総合人間学部 4回生 白石拓海 2024/05/02 0
2. 便利なテンプレ集 目次 ● パーセプトロンの限界 • パーセプトロンとR^2平面内の直線 • XORゲート ● 多層パーセプトロン • パーセプトロンの組み合わせ • パーセプトロンの実装の抽象化(脱線) • https://github.com/takumi-shrsh/KaiRA-reading-2024/ tree/main/week02 ● NAND論理の完全性 • AND, OR, NOTによる表現 • NANDからAND, OR, NOTを作る 1
パーセプトロンの限界 2
パーセプトロンの限界/パーセプトロンとR^2平面内の直線 パーセプトロンの式 パーセプトロン(ゲート) y = 0 (b + w1*x1 + w2*x2 <= 0) y = 1 (b + w1*x1 + w2*x2 >= 0) … (3.2) ● b, w1, w2 • • • ● x1, x2 • • ● 値は実数 bをバイアス、w1, w2を重みと呼んだ 定数:(x1, x2より先に)定めておく数 値は0または1 (独立)変数:値を取り得る範囲内で変えてみる数 y • • 値は0または1 従属変数:x1, x2の変化に応じた変化を見る数 3
パーセプトロンの限界/パーセプトロンとR^2平面内の直線 R^2平面内の直線 R^2平面内の直線の方程式 a*x1 + b*x2 + c = 0 ● a, b, cを決めると、直線が1つ定まった ● 直線はR^2平面全体を2つの領域A0, A1に分ける • 点(x1, x2)が a*x1 + b*x2 + c < 0 [> 0]を満たす ⇔点(x1, x2)はA0[A1]内にある • ただしここでは、c<0とし原点(0, 0)を含む方の領域をA0とした x2 A0 A1 O x1 4
パーセプトロンの限界/パーセプトロンとR^2平面内の直線 パーセプトロンと直線が作る領域との対応 パーセプトロン(ゲート) y = 0 (b + w1*x1 + w2*x2 <= 0) y = 1 (b + w1*x1 + w2*x2 >= 0) R^2平面内の直線によって作られる2つの領域A0, A1と点xの包含関係 x ∈ A0 (a*x1 + b*x2 + c < 0) x ∈ A1 (a*x1 + b*x2 + c > 0) パーセプトロン(ゲート)の定義域(変数x1, x2がとる値の範囲)を {0, 1}(0または1)からR(実数全体)へと拡張して考えると、 パーセプトロンは、直線w1*x1+w2*x2+b=0に対応する。 すなわち、パーセプトロンに与えると0[1]を返す点(x1, x2)の集合は、 直線w1*x1+w2*x2+b=0が作るA0[A1]内の点(x1, x2)の集合に一致する 5
パーセプトロンの限界/XORゲート XORゲートについて XORゲート(排他的論理和) x1 x2 y 0 0 0 1 0 1 0 1 1 1 1 0 左表を満たすパーセプトロンは存在するか? パーセプトロンのx1, x2の取り得る値を 実数全体へと拡張し、直線と対応させて考える R2平面を、 点(0, 0), (1, 1)を含む領域と 点(1, 0), (0, 1)を含む領域 に分ける直線は存在するか? 6
パーセプトロンの限界/XORゲート XORゲートに対応する直線は存在しない 直観的に条件を満たすような直線は存在しないと分かる。 x2 (0, 1) 証明) 背理法によって示す。 条件を満たすような直線 ax1 + bx2 + c = 0 が存在すると仮定する。 このとき次の条件が成り立つ。 (1, 1) c > 0, a + c < 0, b + c < 0, a + b + c > 0 または c < 0, a + c > 0, b + c > 0, a + b + c < 0 (1, 0) O x1 7
パーセプトロンの限界/XORゲート XORゲートに対応する直線は存在しない(2) (1, 1) c > 0 のとき、 a+c < 0, b+c < 0, a+b+c > 0 が成り立ち、 前の2式から a+b+2c < 0 が導ける。 このときc > 0より、 0 < a+b+c < a+b+2c < 0 となるがこれは矛盾。 (1, 0) c < 0 のときも同様に矛盾が生じる。 よって背理法により 条件を満たす a, b, c は存在しない。 すなわち条件を満たす直線は存在しない。 x2 (0, 1) O x1 2つの集合{(0, 0), (1, 1)}と{(1, 0), (0, 1)}は 線形分離不可能であるという。 8
パーセプトロンの限界/XORゲート XORゲートを表現する領域を作る曲線 2つの直線や、1つの曲線であれば分けられる。 →どのように表現するか? 9
多層パーセプトロン 10
多層パーセプトロン/パーセプトロンの組み合わせ パーセプトロンの出力を別のパーセプトロンに入力する パーセプトロンは、2つの入力を受け取り、1つの出力を返す関数であった。 あるパーセプトロンの出力を、そのまま別のパーセプトロンの入力にする ことを考える。(→「層を重ねる」という) x1 P1 s1 P x2 P2 y s2 s1 = P1(x1, x2) s2 = P2(x1, x2) y = P(s1, s2) 11
多層パーセプトロン/パーセプトロンの組み合わせ XORゲートの表現 層を重ねることにより、単層の(1つの)パーセプトロンでは表現出来なかった XORゲートを表現できる! x1 x2 s1 s2 y 0 0 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 0 1 0 s1 = NAND(x1, x2) s2 = OR(x1, x2) y = AND(s1, s2) 数学的表現 NAND, OR, AND:{0, 1}^2 → {0, 1}によって、 合成関数XOR:{0, 1}^2 → {0, 1}を次のよう定める。 XOR(x1, x2) := AND(NAND(x1, x2), OR(x1, x2)) 注)f:{0, 1}^2 → {0, 1}は、 fが2つの0または1を受け取り、 0または1を返す関数であるということを表す。 12
多層パーセプトロン/パーセプトロンの組み合わせ XORによる分類の図示 XOR(x1, x2) = AND(NAND(x1, x2), OR(x1, x2)) AND 両方で赤い点は赤、 他は青で。 1層目(NAND, OR)でよって境界を定め、 2層目(AND)で境界の選び取り方を決めている。 注)ANDは{0, 1}しか受け取らないため、 ANDのパラメータは、1層目で定まった境界の 選び方にしか関係しない。 パラメータ b w1 w2 NAND 0.7 -0.5 -0.5 OR -0.2 0.5 0.5 13
多層パーセプトロン/パーセプトロンの組み合わせ 多層パーセプトロンについての注 重みを持つ層は実質2層(第0層と第1層の間と第1層と第2層の間)なので、 2層のパーセプトロンと呼ぶ。 文献によっては、3層のパーセプトロンと呼ぶこともある。 x1 s1 P1 y P x2 第0層 P2 s2 第1層 第2層 14
多層パーセプトロン/パーセプトロンの実装の抽象化(脱線)
パーセプトロンのコードを書くことの解釈
パーセプトロンのコードを書くことは、
b, w1, w2∈Rを変数として、
「x1, x2∈{0, 1}を変数として、y∈{0, 1}を返す関数」を書いている
とも考えられる。
ほとんど同じ!
def NAND(x1, x2):
x = np.array([x1, x2])
w = np.array([-0.5, -0,5])
b = 0.7
tmp = np.sum(w * x) + b
if tmp <= 0:
return 0
else:
return 1
def OR(x1, x2):
x = np.array([x1, x2])
w = np.array([0.5, 0,5])
b = -0.2
tmp = np.sum(w * x) + b
if tmp <= 0:
return 0
else:
return 1
15
多層パーセプトロン/パーセプトロンの実装の抽象化(脱線)
単層パーセプトロンを抽象化した関数
b, w1, w2∈Rを変数として、
「x1, x2∈{0, 1}を変数として、y∈{0, 1}を返す関数」
を作るための関数perceptronを作る。
def perceptron(x1, x2, w1, w2, b):
return int(x1 * w1 + x2 * w2 + b > 0)
def NAND(x1, x2):
return perceptron(x1, x2, -0.5, -0.5, 0.7)
本質だけ与えれば十分
def OR(x1, x2):
return perceptron(x1, x2, 0.5, 0.5, -0.2)
def AND(x1, x2):
return perceptron(x1, x2, 0.5, 0.5, 0.7)
16
多層パーセプトロン/パーセプトロンの実装の抽象化(脱線) 単層パーセプトロンのクラス perceptronという設計図をもとに個々のパーセプトロンを作る。 →classの使いどころ class SimplePerceptron(): def __init__(self, w1, w2, b): self.w1 = w1 self.w2 = w2 self.b = b def apply(self, x1, x2): return int(x1 * self.w1 + x2 * self.w2 + self.b > 0) AND = Perceptron(0.5, 0.5, -0.7) print(AND.apply(1, 1)) #使い方が変わるので注意 17
多層パーセプトロン/パーセプトロンの実装の抽象化(脱線) クラスについて(Pythonの基礎) classという設計図をもとに作られた個々のものを「インスタンス」という。 インスタンスは、「インスタンス変数」(定数:予め定めておく数)と、 「インスタンスメソッド」(インスタンス変数を用いる関数)を持つ。 インスタンスがどのようなインスタンス変数とインスタンスメソッド を持つか決める(あるいは示す)のがclassの役割。 class SimplePerceptron(): def __init__(self, w1, w2, b): self.w1 = w1 self.w2 = w2 self.b = b def apply(self, x1, x2): return int(x1 * self.w1 + x2 * self.w2 + self.b > 0) AND = SimplePerceptron(0.5, 0.5, -0.7) print(AND.apply(1, 1)) #使い方が変わるので注意 18
多層パーセプトロン/パーセプトロンの実装の抽象化(脱線) 二層パーセプトロンのクラス class TwoLayersPerceptron(Perceptron): def __init__(self, p1, p2, p3): self.p1 = p1 self.p2 = p2 self.p3 = p3 def apply(self, x1, x2): s1 = self.p1.apply(x1, x2) s2 = self.p2.apply(x1, x2) return self.p3.apply(s1, s2) NAND = SimplePerceptron(-0.5, -0.5, 0.7) OR = SimplePerceptron(0.5, 0.5, -0.2) AND = SimplePerceptron(0.5, 0.5, -0.7) XOR = TwoLayersPerceptron(NAND, OR, AND) print(XOR.apply(1, 0)) さらに2層のパーセプトロンもclassにする。 Perceptronのインスタンスを3つ (定数として)予め受け取り、 「x1, x2という2つの変数を受け取り、 1つの出力を返すインスタンスメソッドを持つ インスタンスを作るクラスを書いた。 注)Perceptronというclassを SimplePerceptronと TwoLayersPerceptronの 親クラス(interface的)とするために作った XORは、SimplePerceptronのインスタンス NAND, OR, ANDから作られる TwoLayerPerceptronのインスタンス! 19
多層パーセプトロン/パーセプトロンの実装の抽象化(脱線) 多層パーセプトロンの例 classを駆使すれば、このような複雑なパーセプトロンも書きやすくなる! コード:https://github.com/takumi-shrsh/KaiRA-reading-2024/tree/main/week02 20
NAND論理の完全性 21
NAND論理の完全性/AND, OR, NOTによる表現 n変数パーセプトロン n個の0または1を受け取り、0または1を返す関数{0, 1}^n → {0, 1}を考える。 入力のパターンは2^n通りあり、各パターンで0を返すか1を返すかが 関数ごとに決まっているので、考えうる関数は2^(2^n)個ある。 これらすべてAND, OR, NOTゲートを重ね合わせることで表現出来る!! 2^n x1 x2 xn y 0 0 … 0 0または1 1 0 … 0 0または1 0 1 … 0 0または1 2 × 2 × = 2^(2^n) …… …… …… …… …… 1 1 … 1 …… 0または1 × 2 22
NAND論理の完全性/AND, OR, NOTによる表現 AND, OR, NOTの表現力 x1 x2 x3 y 0 0 0 1 1 0 0 0 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 1 1 1 1 0 例えばn=3として、左表のような値を取る関数を考える。 y=1となる行に着目し、 その行のx1, x2, x3を 1のときはそのまま、0のときはNOTをつけて ANDで繋ぐ。そして各行の論理式をORで繋ぐ。 今回の場合、(¬x1∧¬x2∧¬x3)∨(x1∧x2∧¬x3)∨ (x1∧¬x2∧x3)∨(¬x1∧x2∧x3)となる。 (ただしANDを∧、ORを∨、NOTを¬で表した。) これは左表の値通りの値を返す。 このような論理式をDNF(論理和標準形)という。 3個以上の∧および∨の連なりは、AND(AND(x1, x2), x3) のようにすると、ゲートの重ね合わせで表現出来る。 あるいは、3個以上の入力を受け取るパーセプトロンを考えれば、 2層で任意の関数を表現出来るといえる。 23
NAND論理の完全性/NANDからAND, OR, NOTを作る NANDからAND, OR, NOTを作る AND, OR, NOTで任意の関数{0, 1}^n → {0, 1}を表現出来ることが分かった。 ここでさらに、NANDでAND, OR, NOTを表現出来ることをみる。 NOT(x) = NAND(x, x) AND(x1, x2) = NAND(NAND(x1, x2), NAND(x1, x2)) = NOT(NAND(x1, x2)) OR(x1, x2) = NAND(NAND(x1, x1), NAND(x2, x2)) = NAND(NOT(x1), NOT(x2)) このことから、NANDだけでも任意の関数{0, 1}^n → {0, 1}を表現出来ることが分かる。こ のNANDの性質をNAND論理の完全性という。 24
NAND論理の完全性/NANDからAND, OR, NOTを作る NANDからAND, OR, NOTを作る(2) NOT(x) = NAND(x, x) AND(x1, x2) = NAND(NAND(x1, x2), NAND(x1, x2)) = NOT(NAND(x1, x2)) OR(x1, x2) = NAND(NAND(x1, x1), NAND(x2, x2)) = NAND(NOT(x1), NOT(x2)) NOT(x1) NOT(x2) NAND(x1, x1) NAND(x2, x2) AND(x1, x2) OR(x1, x2) NOT(NAND(x1, x2)) NAND(NOT(x1), NOT(x2)) x1 x2 NAND(x1, x2) 0 0 1 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 0 0 0 1 1 NOR(x1, x2) := NOT(OR(x1, x2))も完全性を持つ NOT(x) = NOR(x, x) AND(x1, x2) = NOR(NOR(x1, x2), NOR(x1, x2)) = NOR(NOT(x1), NOT(x2)) OR(x1, x2)= NOT(NOR(x1, x2)) = NOR(NOR(x1, x2), NOR(x1, x2)) 25
2. 便利なテンプレ集 まとめ 2変数単層パーセプトロンは、R^2空間内の向きを込めたある直線に対応する まとめ1 →n変数ならR^n空間内の超平面 → 線形領域しか表現出来ない 多層パーセプトロンは、R^2空間内の有限個の点を任意の2組に分割できる まとめ2 →理論上は、R^n空間内の有限個の点を任意のm組に分割できるらしい NAND回路だけで任意の関数{0, 1}^n → {0, 1}を表現出来る まとめ3 →コンピュータも作れるらしい 26
27