---
# System prepended metadata

title: Learning 8-bit parity checking problem with MLP
tags: [Fundamental Deep Learning Assignments 2019]

---

DeeplearnHW01 410535020 資管四 葉松
###### tags: `Fundamental Deep Learning Assignments 2019`

# Learning 8-bit parity checking problem with MLP
---
<!-- ![downloads](https://img.shields.io/github/downloads/atom/atom/total.svg)
![build](https://img.shields.io/appveyor/ci/:user/:repo.svg)
![chat](https://img.shields.io/discord/:serverId.svg)
 -->
# 目錄

[TOC]

<!-- ## Beginners Guide

If you are a total beginner to this, start here!

1. Visit hackmd.io
2. Click "Sign in"
3. Choose a way to sign in
4. Start writing note!
 -->
 
# 1.問題
---
In this assignment, you are required to design a multilayer perceptron (MLP) to learn the **8-bit parity check** (8BPC） problem. The 8BPC problem is to generate a single parity bit from an 8-bit (1-byte) binary input. The generated parity bit must be one if the number of 1's in the binary input is odd. Otherwise, the generated parity bit must be zero. 

# 2.解決步驟
---
Step 1 : 建構MLP函式及激勵函數的的init,forward及backward(詳細請見完整程式碼)

Step 2 : 建立標本集與對應答案集
```python=
#建立00000000~11111111的8*256陣列(0~255轉8bit)，擺放訓練資料
x = [[a,b,c,d,e,f,g,h] for a in range(2) for b in range(2)for c in range(2)for d in range(2)for e in range(2)for f in range(2)for g in range(2)for h in range(2) ]
x = np.array(x)
#建立一個 1*256 陣列作答案集，擺放每筆訓練資料對應的答案
#dec2bin()將數字轉二進位字符串
#count_one()計算字串中包含幾個1，如為奇數個回傳1，偶數個則回傳0
y=[[count_one(dec2bin(i))]for i in range(256)]
y = np.array(y)
```
Step 3 : 使用**Step1**定義的MLP函式建立神經網絡model

在主程式中，你可以呼叫剛剛定義的MLP函式來建構你的神經網絡模型

**MLP( 輸入層輸入神經數, [各層的激勵函數], [隱藏層各層輸出神經數] )**

下面範例中，數字8的位置為模型輸入的神經元數量(**此數必須與你訓練資料陣列的行數一致，使得運算可以成立**)，['relu', 'sigmoid']則是你每層所要疊加的激勵函數，[10, 1]則是各層隱藏層輸出的神經元數量，目前此MLP中**各層的激勵函數**可以擺放的函數有以下四種
 
 **激勵函數**
- [x] Tanh
- [x] relu
- [x] Sigmoid
- [x] linear

```python=
mlp2 = MLP(8, ['relu', 'sigmoid'], [10,1])
mlp3 = MLP(8, ['linear', 'relu', 'sigmoid'], [10,5,1])
mlp4 = MLP(8,['Tanh','linear','relu','Sigmoid'],[5,8,10,1])
```

Step 4 : 設定參數(學習數率,批次數量,批次週期等......

**eta**學習數率(太大可能會導致梯度來回跳，無法降到低點，太小則學習較慢
**alpha**用來避免收斂震盪
```python=
max_epoch,chk_epoch=25000,1000
eta,alpha=0.01,0.7
```
Step 5 : 批次執行MLP

```python=
for e in range(max_epoch):
  model.forward(x)
  model.backward(y)
  model.update(eta,alpha)
  #顯示推估出的y及loss
  if(e+1)%chk_epoch==0:
    print(model.ybar.T)
    print('Epoch %3d: loss=%6f'%(e+1,model.L))
```

# 3.效能評估

嘗試了多組不同激勵函數的神經網路組合，二層的神經網絡學習速率普遍較慢，且若選擇的激勵函數不當，有時會導致梯度消失的問題，三層的普遍表現較佳，其中以依序使用relu,Tanh,Sigmoid激勵函數的model為其中之最，而後嘗試四層的神經網絡，雖然層數更多，但是loss下降的速度卻反而比三層model的差，由此可見，神經網路的層數未必越多越好，選擇合適的才能得到較好的結果

```python=
model=MLP(8,['relu','Tanh','Sigmoid'],[8,8,1])
```

![](https://i.imgur.com/MEwg45y.png)


[[5.91653736e-03 9.84475521e-01 9.96057226e-01 1.53485355e-04
  9.90910329e-01 1.21258674e-02 5.68945452e-03 9.99948005e-01
  9.85418739e-01 1.11931922e-02 1.12002326e-02 9.78898246e-01
  8.82169099e-03 9.90343636e-01 9.92583657e-01 1.15519361e-02
  9.80220695e-01 2.16835044e-04 6.73914184e-03 9.84631409e-01
  1.05356701e-02 9.85250031e-01 9.91207426e-01 1.20930362e-02
  2.56481527e-02 9.85830428e-01 9.85515381e-01 1.11891952e-02
  9.76515770e-01 1.21787610e-02 9.07803431e-03 9.90599860e-01
  9.96159092e-01 9.08847844e-05 6.22195508e-04 9.95258466e-01
  7.35040825e-03 9.99997827e-01 9.91036702e-01 3.72058449e-03
  4.61965623e-03 9.91038300e-01 9.98644893e-01 3.04319170e-04
  9.87403966e-01 3.52423221e-02 4.97534226e-03 9.90589925e-01
  4.65209431e-03 9.83667432e-01 9.95641933e-01 1.21531083e-04
  9.89123803e-01 1.38633731e-02 6.24918475e-03 9.99997983e-01
  9.82494473e-01 8.73440380e-03 4.59822201e-03 9.91219066e-01
  1.02940958e-02 9.85006169e-01 9.86991418e-01 3.50654721e-02
  9.96059098e-01 1.53773162e-04 5.90701636e-08 9.83794898e-01
  5.69568524e-03 9.99948127e-01 9.98503997e-01 1.02582214e-02
  1.12003709e-02 9.78902757e-01 9.74260091e-01 5.67902916e-05
  9.92590934e-01 1.15519028e-02 2.06201256e-02 9.74669202e-01
  6.72755372e-03 9.84631507e-01 9.95766966e-01 1.16449208e-04
  9.91204982e-01 1.20934950e-02 4.79925161e-03 9.99962082e-01
  9.85512864e-01 1.11891929e-02 1.11952515e-02 9.78306272e-01
  9.07551130e-03 9.90600717e-01 9.92595746e-01 1.16945452e-02
  6.22718518e-04 9.95257357e-01 9.97133930e-01 9.20168940e-02
  9.91052730e-01 3.72516137e-03 2.98716330e-03 9.96124416e-01
  9.98644947e-01 3.06019508e-04 5.42917368e-08 9.87095063e-01
  4.98085282e-03 9.90587421e-01 9.98681536e-01 3.35414487e-04
  9.95650733e-01 1.21076452e-04 5.85852918e-04 9.96483105e-01
  6.25583977e-03 9.99997981e-01 9.90173945e-01 3.37887464e-03
  4.59672906e-03 9.91218829e-01 9.98638744e-01 2.09258535e-04
  9.86987638e-01 3.50669962e-02 4.74783378e-03 9.90330606e-01
  9.80234150e-01 2.09257645e-04 6.71401979e-03 9.84627264e-01
  1.05263627e-02 9.85271298e-01 9.91206007e-01 1.20898638e-02
  2.57030335e-02 9.85833812e-01 9.85506138e-01 1.11892182e-02
  9.76376369e-01 1.21171972e-02 9.05783845e-03 9.90603707e-01
  6.41173335e-02 9.81391424e-01 9.82462900e-01 5.73941253e-04
  9.86093387e-01 6.93898020e-03 1.06885073e-02 9.84732779e-01
  9.28313797e-01 6.32727213e-02 2.38112847e-02 9.85954176e-01
  2.09306278e-02 9.86295403e-01 9.77697667e-01 1.23493252e-02
  4.60407505e-03 9.83646043e-01 9.95659873e-01 1.19502107e-04
  9.89123778e-01 1.38598796e-02 6.26252608e-03 9.99997976e-01
  9.82441988e-01 8.71924816e-03 4.59431735e-03 9.91217743e-01
  1.02845903e-02 9.85000443e-01 9.86984284e-01 3.50754113e-02
  9.84114419e-01 5.72949387e-03 5.62718258e-03 9.83983373e-01
  1.02997357e-02 9.83811790e-01 9.89744248e-01 1.39560902e-02
  3.86214867e-02 9.86056538e-01 9.82777629e-01 8.99780272e-03
  9.82236242e-01 1.59600611e-02 1.03927949e-02 9.85846680e-01
  6.70282285e-03 9.84627343e-01 9.95750571e-01 1.17069981e-04
  9.91203559e-01 1.20903361e-02 4.81137705e-03 9.99962191e-01
  9.85503526e-01 1.11892190e-02 1.11955849e-02 9.78323018e-01
  9.05531629e-03 9.90604548e-01 9.92595753e-01 1.16931262e-02
  9.82472005e-01 5.67284063e-04 7.49491734e-03 9.84749536e-01
  1.06857304e-02 9.84740346e-01 9.91447763e-01 1.21587238e-02
  2.38126135e-02 9.85955157e-01 9.85525166e-01 1.11877038e-02
  9.77678066e-01 1.23299543e-02 9.29126657e-03 9.90828836e-01
  9.95668596e-01 1.19059452e-04 5.87358866e-04 9.96475943e-01
  6.26919910e-03 9.99997974e-01 9.90205924e-01 3.45799130e-03
  4.59283969e-03 9.91217505e-01 9.98639181e-01 2.12909615e-04
  9.86980507e-01 3.50769499e-02 4.75979086e-03 9.90327064e-01
  5.60949718e-03 9.83977049e-01 9.94761452e-01 1.65466126e-04
  9.89739257e-01 1.39590434e-02 7.67250820e-03 9.99998094e-01
  9.82766695e-01 8.99328447e-03 4.57160573e-03 9.91376334e-01
  1.03916846e-02 9.85847129e-01 9.86529079e-01 3.49706722e-02]]
  Epoch 25000: loss=0.061685


    
# 4.完整Code
```python=
import numpy as np

x=np.array(([0,0],[0,1],[1,0],[1,1]))
x = [[a,b,c,d,e,f,g,h] for a in range(2) for b in range(2)for c in range(2)for d in range(2)for e in range(2)for f in range(2)for g in range(2)for h in range(2) ]
x = np.array(x)
y=[[count_one(dec2bin(i))]for i in range(256)]
y = np.array(y)

#print (x)
#print (y)

#model=MLP(8,['Sigmoid'],[1])
#model=MLP(8,['relu','Sigmoid'],[15,1])
#model=MLP(8,['linear','relu','Sigmoid'],[15,15,1])

model=MLP(8,['relu','Tanh','Sigmoid'],[15,15,1])

#model=MLP(8,['Tanh','relu','Sigmoid'],[5,10,1])
#model=MLP(8,['Tanh','linear','relu','Sigmoid'],[5,8,10,1])
max_epoch,chk_epoch=25000,1000
eta,alpha=0.01,0.7


for e in range(max_epoch):
  model.forward(x)
  model.backward(y)
  model.update(eta,alpha)
  if(e+1)%chk_epoch==0:
    print(model.ybar.T)
    print('Epoch %3d: loss=%6f'%(e+1,model.L))


class MLP:
  def __init__(self,m,n,o):
    #設self.t為MLP層數
    self.t=len(n)
    #設e[]為輸入的激勵函數陣列
    e=[]
    #out[]為輸入的每層輸出神經元數量陣列
    out=[]
    for i in range (len(n)):
      e.append(n[i])
      out.append(o[i])
    #設self.linear[]保存每層 Linear(輸入神經元,輸出神經元)
    self.linear=[]
    #設self.act[]保存每層激勵函數
    self.act=[]

    for i in range (len(n)):
      #一開始有m個輸入,之後中間層的輸入/出數量看out[]
      if(i==0):
        self.linear.append(Linear(m,out[i]))
      else:
        self.linear.append(Linear(out[i-1],out[i]))
      #逐一檢索e[]中每層的激勵函數為何，而後加到act[]中
      if(e[i]=='relu'):
        self.act.append(ReLU())
        print ('第',i+1,'層激勵函數ReLU()')
      elif(e[i]=='Sigmoid'):
        self.act.append(Sigmoid())
        print ('第',i+1,'層激勵函數Sigmoid()')
      elif(e[i]=='Tanh'):
        self.act.append(Tanh())
        print ('第',i+1,'層激勵函數Tanh()')
      elif(e[i]=='linear'):
        #設沒有激勵函數為''
        self.act.append('')
        print ('第',i+1,'層無激勵函數')

#設定使用的Loss Function
    self.loss=Loss()

    self.last_dW=[]
    self.last_db=[]
    for i in range (len(n)):
      self.last_dW.append(0)
      self.last_db.append(0)

  def forward(self,x):
    for i in range (self.t):
      x=self.linear[i].forward(x)
      #沒有激勵函數則跳過
      if(i==self.t-1):
        if(self.act[i]==''):
          self.ybar=x
        else:
          self.ybar=self.act[i].forward(x)
      elif(self.act[i]==''):
        continue
      else:
        x=self.act[i].forward(x)
    return self.ybar

  def backward(self,y):
    self.L=self.loss.forward(y,self.ybar)
    g=self.loss.backward(1)
    for i in range (self.t-1,-1,-1):
      #沒有激勵函數則跳過
      if(self.act[i]!=''):
        g=self.act[i].backward(g)
      g=self.linear[i].backward(g)

  def update(self,eta,alpha):
    for i in range (self.t):
      self.linear[i].W=self.linear[i].W-eta*self.linear[i].dW+alpha*self.last_dW[i]
      self.linear[i].b=self.linear[i].b-eta*self.linear[i].db+alpha*self.last_db[i]
      self.last_dW[i]=eta*self.linear[i].dW
      self.last_db[i]=eta*self.linear[i].db


class Linear:
  def __init__(self,m,n):
    self.W,self.b=np.random.randn(m,n),np.random.randn(1,n)
    self.dW,self.db=None,None
  def forward(self,x):
    self.x=x
    out=np.dot(x,self.W)+self.b
    return out
  def backward(self,dout):
    dx=np.dot(dout,self.W.T)
    self.dW=np.dot(self.x.T,dout)
    self.db=np.sum(dout,axis=0)
    return dx


class ReLU:
  def __init__(self):
    pass
  def forward(self,x):
    self.mask=(x<0)
    out=x
    out[out<=0]=0
    return out
  def backward(self,dout):
    dx=dout
    dx[self.mask]=0
    return dx

class Sigmoid:
  def __init__(self):
    pass
  def forward(self,x):
    out=1/(1+np.exp(-x))
    self.o=out
    return out
  def backward(self,dout):
    dx=dout*self.o*(1-self.o)
    return dx

class Tanh:
    def __init__(self):
      pass
    def forward(self,x):
      out=np.tanh(x)
      self.o=out
      return out
    def backward(self,dout):
      dx =dout*(1-(self.o)**2)
      return dx

class Loss:
  def __init__(self):
    pass
  def forward(self,y,ybar):
    self.ybar=ybar
    return np.sum((y-ybar)**2)
  def backward(self,dout):
    dy=-(2*(y-self.ybar))
    return dy

import os,sys
#數字轉2進位
def dec2bin(num):
  l = []
  if num < 0:
    return 0
  while True:
    num, remainder = divmod(num, 2)
    l.append(str(remainder))
    if num == 0:
      return ''.join(l[::-1])
#計算字串中有幾個1，大於1等於則回傳1，反之回傳0
def count_one(s):
  times =0
  for i in range(len(s)):
    if(s[i]=='1'):
      times=times+1
  if(times%2==1):
    return 1
  else :
    return 0 
