IT

【Python】パーセプトロンアルゴリズムを用いて論理回路を実装する

「パーセプトロン」とは、今流行りのディープラーニングの起源とも言えるアルゴリズムであり、1957年にアメリカ心理学者フランク・ローゼンブラットが開発したものである。ディープラーニングの歴史も結構長いことが分かる。

この記事ではパーセプトロンアルゴリズムを活用して簡単な論理回路を実装する方法について解説する。

パーセプトロンのしくみ

パーセプトロンは、複数の入力信号を受け取り、一つの信号を出力するというものである。入力信号・出力信号共に、0か1の値を持つ1ビット信号である。

最も簡単な、入力信号の数が2つの場合で説明しよう。動作原理を数式で表すと、

となる。それぞれのパラメータについて説明すると

  • 入力:x1,x2(0 or 1)
  • 出力:y(0 or 1)
  • パーセプトロンのパラメータ:w1, w2, θ(任意の値)

である。w1, w2, θをいじることで、入力に対する出力のパターンを決定することが出来る。図で考えると次のような感じだろう。

基本的な論理回路の実装

今までの説明だけでは、まだ分かりにくいかもしれない。このアルゴリズムにを使って何かを作ってみると、パーセプトロンを理解するのに役に立つ。

パーセプトロンを使って作るものと言えば、論理回路だ。そこで実際に簡単な論理回路を実装してみた。

ANDやORといった基本的なものから、XORやRSフリップフロップといったちょっとした応用まで実装してみた。

実装の際にはPython3使用した。ソースコードと実行結果について書いていこうと思う。

ANDゲートの実装

AND回路の真理値表は次の通り

2つの入力が共に1の場合のときだけ1を出力し、それ以外のときは0を出力する。

この真理値表を実現するためのパーセプトロンのパラメータ(w1, w2, θ)を考える。

(w1, w2, θ) = (0.5, 0.5, 0.7)

の時に条件を満たしそうだ。実際にパーセプトロンの動作原理の式に値を入れてみると次のようになる。

パワメータの値は(w1, w2, θ) = (0.5, 0.5, 0.7)以外にも無限に存在する。たとえば(w1, w2, θ) = (1.0, 1.0, 1.2)とかでもいい。

pythonで実装する

【入力コード】

def AND(x1, x2):
    w1 = 0.5
    w2 = 0.5
    θ  = 0.7

    z = x1*w1 + x2*w2

    if z <= θ:
        return 0
    elif z > θ:
        return 1

print("AND(0, 0)=" ,AND(0,0))
print("AND(1, 0)=" ,AND(1,0))
print("AND(0, 1)=" ,AND(0,1))
print("AND(1, 1)=" ,AND(1,1))

【出力結果】

AND(0, 0)= 0
AND(1, 0)= 0
AND(0, 1)= 0
AND(1, 1)= 1

zのパラメータは w1x1 + w2x2 の計算結果を格納するためのもの。そしてzとθの値を比較して、「z ≦ θ」なら0を「z > θ」なら位置を出力する。

出力結果を確認してみると、ちゃんとANDゲートの真理値と一致していることが分かる。

NANDゲートの実装

NANDゲートの真理値表は以下の通り

これはANDゲートとは完全に逆の出力をするものである。

この真理値表を実現するためのパーセプトロンのパラメータ(w1, w2, θ)は、ANDゲートで使用したパラメータの正負を逆転させれば良い。なので

(w1, w2, θ) = (-0.5, -0.5, -0.7)

としてみよう(もちろんこれも無限の選択肢がある)。代入して成立するかどうか確認する作業は省略する。気になる人はANDゲートの時と同じ様にやってみてほしい。

pythonで実装

【入力コード】

def NAND(x1, x2):
    w1 = -0.5
    w2 = -0.5
    θ  = -0.7

    z = x1*w1 + x2*w2

    if z <= θ:
        return 0
    elif z > θ:
        return 1

print("NAND(0, 0)=" ,NAND(0,0))
print("NAND(1, 0)=" ,NAND(1,0))
print("NAND(0, 1)=" ,NAND(0,1))
print("NAND(1, 1)=" ,NAND(1,1))

【出力結果】

NAND(0, 0)= 1
NAND(1, 0)= 1
NAND(0, 1)= 1
NAND(1, 1)= 0

ANDの場合と比べて変更した点は、関数の名前をイジった以外は、w1, w2, θの値にそれぞれ-を付けただけ。

ORゲートの実装

ORゲートの真理値表は以下の通り。

ORゲートは、入力に一つでも1が含まれていれば、出力も1にするという論理回路である。

これを実現するには、例えば

(w1, w2, θ) = (-1, -1, 0.5)

にすれば良い。

pythonで実装

【入力コード】

def OR(x1, x2):
    w1 = -1
    w2 = -1
    θ  = 0.5

    z = x1*w1 + x2*w2

    if z <= θ:
        return 0
    elif z > θ:
        return 1

print("OR(0, 0)=" ,OR(0,0))
print("OR(1, 0)=" ,OR(1,0))
print("OR(0, 1)=" ,OR(0,1))
print("OR(1, 1)=" ,OR(1,1))

【出力結果】

OR(0, 0)= 0
OR(1, 0)= 1
OR(0, 1)= 1
OR(1, 1)= 1

NORゲートの実装

NORゲートの真理値表は以下の通り。

こちらもORとは逆の出力になる論理回路。入力に1が一つでもあれば0を出力する。

パラメータ設定についても、NANDのときと同様で、ORゲートのパラメータの正負を逆転させればNORゲートになる。なので次の値を用いる。

(w1, w2, θ) = (1, 1, -0.5)

Pythonで実装

【入力コード】

def NOR(x1, x2):
    w1 = 1
    w2 = 1
    θ  = -0.5

    z = x1*w1 + x2*w2

    if z <= θ: 
        return 0 
    elif z > θ:
        return 1

print("NOR(0, 0)=" ,NOR(0,0))
print("NOR(1, 0)=" ,NOR(1,0))
print("NOR(0, 1)=" ,NOR(0,1))
print("NOR(1, 1)=" ,NOR(1,1))

【出力結果】

NOR(0, 0)= 1
NOR(1, 0)= 0
NOR(0, 1)= 0
NOR(1, 1)= 0

応用的な論理回路の実装(多層パーセプトロンによる実装)

いままでは一層のパーセプトロンで論理回路の実装をしてきた。しかし、パーセプトロンのすごい所は、層を重ねてありとあらゆる論理回路を実現できるところである。

そこで、まずは多層パーセプトロンを活用して、XOR回路を実装してみる。

XORゲートの実装

XORゲートの真理値表は以下の通り。

2つの入力が同じなら0を、2つの入力が異なれば1を出力する。

先程までと対して変わらないような気がするが、なぜ応用的としたのか。実は今までと同様のやり方ではXORゲートを実装することはできないからだ。

この真理値表通りに出力するためのパラメータの組み合わせが存在しないのだ。つまり、(w1, w2, θ) をどの様な値に設定してもうまくいかないのである。「ホントかよ~」と思う方はいろんな値を入れて試してみて。

じゃあ、パーセプトロンでXORゲートを実装できないのか?

最初に答えを言ってしまうと、決してそうではない。

論理回路の場合、先に紹介したAND、NAND、ORなどのゲートを組み合わせてXORゲートを作ることが出来る。例えばこんな感じだ。


図 XORゲート

x1とx2の入力がNANDゲートとORゲートに入っていき、NANDからs1、ORからS2が出力される。そうしたら今度はs1とs2がANDゲートに入っていき最終的にyが出力される。

パーセプトロンの場合でも、パーセプトロンを組み合わせることでいろいろな論理回路を作ることが出来る。これが多層パーセプトロンの考え方だ。

当然XORゲートだって作ることが出来る。

pythonで実装

先程のXORゲートの図に基づき実装してみる。

【入力コード】

def AND(x1, x2):
    w1 = 0.5
    w2 = 0.5
    θ  = 0.7

    z = x1*w1 + x2*w2

    if z <= θ: 
        return 0 
    elif z > θ:
        return 1
    
def NAND(x1, x2):
    w1 = -0.5
    w2 = -0.5
    θ  = -0.7

    z = x1*w1 + x2*w2

    if z <= θ:
        return 0 
    elif z > θ:
        return 1

def OR(x1, x2):
    w1 = 1
    w2 = 1
    θ  = 0.5

    z = x1*w1 + x2*w2

    if z <= θ:
        return 0 
    elif z > θ:
        return 1
    
def XOR(x1, x2):
    s1 = NAND(x1, x2)
    s2 = OR (x1, x2)
    y = AND(s1, s2)
    return y


print("XOR(0, 0)=" ,XOR(0,0))
print("XOR(1, 0)=" ,XOR(1,0))
print("XOR(0, 1)=" ,XOR(0,1))
print("XOR(1, 1)=" ,XOR(1,1))

【出力結果】

XOR(0, 0)= 0
XOR(1, 0)= 1
XOR(0, 1)= 1
XOR(1, 1)= 0

入力コードの赤い部分がXORゲートの主要コードである。それより上の部分はAND、NAND、ORの定義。省略しても良かったかもな。

NANDの出力をs1、ORの出力をs2と定義し、この2つの値をANDの入力として最終出力yを得る。

半加算器の実装

もう一つ応用的な例として、半加算器を実装してみたいと思う。

半加算器とは繰り上がりのない2進数どうしの加算を行う回路である。繰り上がりがある場合、繰り上がりを出力することが出来る。もっと高性能な加算器を作る際にも基礎となる回路である。

半加算器の真理値表は以下の通り。繰り上がりCと加算結果Sの2つの出力を持つ。

これは、次のような論理回路で実現することが出来る。

XORの記号をうまく作図できなかったため、wikipediaの「加算器」のページから画像を借りてきて加工した。画像がぼやけているのは、そのせいである。

この回路は出力が2種類ある。多層化することでこのようなことも可能になる。

pythonによる実装

【入力コード】

//(XORとANDの定義部分は省略)

def Hadd(x1, x2):
    S = XOR(x1, x2)
    C = AND(x1, x2)
    return(C, S)
    
print("Hadd(0, 0)=" ,Hadd(0,0))
print("Hadd(1, 0)=" ,Hadd(1,0))
print("Hadd(0, 1)=" ,Hadd(0,1))
print("Hadd(1, 1)=" ,Hadd(1,1))

【出力結果】

Hadd(0, 0)= (0, 0)
Hadd(1, 0)= (0, 1)
Hadd(0, 1)= (0, 1)
Hadd(1, 1)= (1, 0)

「Hadd」という関数名は、半加算器を英語で「Half adder」と言うところから名付けた。

XORゲートとANDゲートは既に作ってあるので、楽ちんである。

パーセプトロンでコンピュータを作ることだって出来るという話

NANDゲートだけを用いて、あらゆる組合せ論理回路の論理を実装できるというのは有名な話だ。つまり、NANDゲートをパーセプトロンで実装できたのだから、パーセプトロンによってあらゆる論理回路を作ることが出来るのだ。

今日のコンピュータは論理回路でできている。もちろん、この記事で扱った物とは比べ物にならないくらい複雑ではあるが、全てはANDやORといった単純な回路の組み合わせでできている。

「複雑な論理回路」とはパーセプトロンで言えば「超多層化」された回路ということである。論理回路やパーセプトロンは多層化することで、豊かな表現力を得ることが出来る。

また、冒頭でも述べたとおり、パーセプトロンはニューラルネットワークの起源であり、基礎となる分野である。これから機械学習が流行っていくにつれて、こういった基礎を学ぶことの重要性は増していくと考えられる。

論理回路もIT系で働くなら基礎になる学問分野である。パーセプトロンと論理回路をまとめて勉強しておけば、今後役に立つ可能性は高いと思う。