【隨筆】神經網路應用:來分類質數吧!

  • 90
  • 0

之前和朋友閒聊時,談到一些機器學習的話題,朋友問道:
你應該也有聽過 fizz buzz 的笑話吧,不知道改成質數行不行欸?

若讀者沒有聽過 fizz buzz 的笑話,夏恩簡單講一下:
fizz buzz 是一個蠻常見的白板題,題目是:

請輸入 0~100 的數字,
若該數字為 3 的倍數時,輸出 Fizz;
若該數字為 5 的倍數時,輸出 Buzz;
若該數字同時為 3 和 5 的倍數時,輸出 FizzBuzz。

一般的解法是這樣:

# -*- coding: utf-8 -*-
# Fizz Buzz example
#
# Shayne

def fizz_buzz(n): 
    for i in range(1, n+1):
        result = ''
        if i%3 == 0:
            result += 'Fizz'
        if i%5 == 0:
            result += 'Buzz'
        if len(result)>0:
            print(result)
        else:
            print(i)

# fizz_buzz(25) 輸出結果
# 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz
# 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 
# Buzz Fizz 22 23 Fizz Buzz ...

笑話的本身則來自於 google 的軟體工程師 Joel Grus 的部落格。

順帶一提,Joel Grus 是 Data Science from Scratch 一書的作者,
其博客來書店的作者簡介如下,有興趣的讀者也可以買來看。

是一位目前任職於Google的一位軟體工程師,之前也曾在幾家新創公司擔任過資料科學家的工作。目前住在西雅圖,愉快地從事著資料科學方面的工作。他會不定期進行更新部落格 joelgrus.com,推特帳號是@joelgrus。


Joel Grus 分享自己面試的經驗,面試官考他 fizz buzz 的實作,對話大概是這樣:

面試官:請問你熟悉 fizz buzz 嗎?
Joel Grus:我不敢相信你會問我這個問題...

面試官:[開始介紹 fizz buzz 問題...]
Joel Grus:好吧,我很熟悉。

面試官:太棒了,那麼請你實作一下 fizz buzz 吧。
Joel Grus:......

Joel Grus:[看著白板思考了幾分鐘]

面試官:需要給你一點提示嗎?
Joel Grus:呃...不用,我很好...恩,首先我要 import numpy,
Joel Grus:然後 import tensorflow。

面試官:欸?等等,你知道我的問題是 fizz buzz 對嗎?
Joel Grus:是的,我知道,再來我們談談模型,需要一個帶有一層隱藏層的多層感知機。

面試官:...感知機?
Joel Grus:然後把每個 input 的數字改成二進制。

面試官:[凝視白板一分鐘]
Joel Grus:output 要改成獨熱編碼。

面試官:好了,這樣就可以了。
Joel Grus:您說得對,這樣的確可以了,接著要生成一些訓練數據,101~1024,

面試官:......
Joel Grus:隱藏層的神經元大概設 10 個...或是 100 個更好,反正可以改。

面試官:......
Joel Grus:然後定義激活函數為 ReLU,損失函數為 softmax cross-entropy。

面試官:......
Joel Grus:訓練時迭代 1000 次,噢...或許 10000 次會更好。

面試官:......
Joel Grus:這樣大概就可以得到您要的  fizz buzz  了。

面試官:......

最後 Joel Grus 沒有得到這份工作。
根據本人的說法,他認為下次應該要使用更深的神經網路來做這件事情。

原文:Fizz Buzz in Tensorflow 

= = = = = = = = = = = = = = = = = = = = 

不知道您看完有什麼想法,夏恩第一次看到時,笑得停不下來。
Joel Grus 從頭到尾都在嘲諷面試官,這位大神真的太有趣了!

既然 fizz buzz 都可以用神經網路來實現,那弄個質數分類器也可以吧!
為了回答朋友的提問,夏恩花了大約十分鐘的時間實作。

Step 0

第一步當然是先 import 套件啦!

import numpy as np
from tensorflow.keras import Sequential
from tensorflow.keras.layers import Dense

Step 1

首先做一個質數產生器,根據國中數學告訴我們的結論:
判斷 N 是否為質數只需要計算 2~根號N 的所有質數即可。
若無可以整除的對象,則 N 為質數。

例如:計算101是否為質數,那只需計算 2、3、5、7 能否整除 101 即可判斷。

def get_prime(n):
    prime_list = []
    for i in range(2, n+1):
        is_prime = True  
        j_max = np.sqrt(i)
        for j in prime_list:
            if i%j == 0:
                is_prime = False
                break            
            if j > j_max:
                break
        
        if is_prime:
            prime_list.append(i)
            
    return prime_list

# get_prime(50) 輸出結果為
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Step 2

製作資料,需要對數字做二進制編碼,例如:

原值  | 質數 [ 否 , 是 ]  |     編碼
   1    |         [ 1, 0 ]       |  [ 0, 0, 1]
   2    |         [ 0, 1 ]       |  [ 0, 1, 0]
   3    |         [ 0, 1 ]       |  [ 0, 1, 1]
   4    |         [ 1, 0 ]       |  [ 1, 0, 0]
   5    |         [ 0, 1 ]       |  [ 1, 0, 1]
   6    |         [ 1, 0 ]       |  [ 1, 1, 0]
   7    |         [ 0, 1 ]       |  [ 1, 1, 1]
   8    |      依此類推...

def get_dataset(n):
    # 取得值域為 0~n 的資料集
    
    # 計算最大值所需位元數
    n_bits = len(bin(n))-2
    
    # 計算資料數
    n_data = n+1
    
    # 產生 x,y 資料集
    x_dataset = np.zeros((n_data, n_bits))
    y_dataset = np.zeros((n_data, 2))
    
    # x_dataset binary encode
    for i, N in enumerate(range(0, n_data)):
        x_dataset[i,] = np.array(list(bin(N)[2:].zfill(n_bits)))
    
    # y_dataset one-hot encode
    # step1: assign prime to [0, 1]
    prime_list = get_prime(n)
    y_dataset[prime_list,] = np.array([0, 1])
    # step2: other numbers assign to [1, 0]
    idx = np.invert((np.sum(y_dataset, 1)).astype(np.bool))
    y_dataset[idx,] = np.array([1, 0])
    
    return y_dataset, x_dataset

# get_dataset(10) 輸出值為
# x_dataset
#  array([[0., 0., 0., 0.],
#         [0., 0., 0., 1.],
#         [0., 0., 1., 0.],
#         [0., 0., 1., 1.],
#         [0., 1., 0., 0.],
#         [0., 1., 0., 1.],
#         [0., 1., 1., 0.],
#         [0., 1., 1., 1.],
#         [1., 0., 0., 0.],
#         [1., 0., 0., 1.],
#         [1., 0., 1., 0.]])
#
# y_dataset
#  array([[1., 0.],
#         [1., 0.],
#         [0., 1.],
#         [0., 1.],
#         [1., 0.],
#         [0., 1.],
#         [1., 0.],
#         [0., 1.],
#         [1., 0.],
#         [1., 0.],
#         [1., 0.]])

Step 3

寫支主程式來取資料:

# get dataset
y_dataset, x_dataset = get_dataset(10000)

# 第 101 筆資料之後皆為訓練集
x_train = x_dataset[101:,]
y_train = y_dataset[101:]

# 第 1 至 100 筆資料為測試集
x_test = x_dataset[1:101,]
y_test = y_dataset[1:101]

接著建一個模型,這裡用 Keras 來協助我們,
使用兩個隱藏層的神經網路進行二元分類。

# setting model
model = Sequential([
    Dense(input_dim=x_dataset.shape[1], units=256, activation='relu'),
    Dense(units=512, activation='relu'),
    Dense(2, activation='softmax') ])

model.compile(optimizer='rmsprop',
              loss='binary_crossentropy',
              metrics=['acc'])

訓練參數也要調整一下:
打亂數據 shuffle=True、批次量 batch_size=128、迭代次數:epochs=300

# training model
model.fit(x_train, y_train, shuffle=True, batch_size=128, epochs=300)

從上圖可以看到,訓練的正確率可達 99.5% 呢!

最後實際計算數字 1~100 的分類效果:

test_loss, test_acc = model.evaluate(x_test, y_test, batch_size=100)
print('\nTest accuracy:', test_acc)

如上圖,正確率差了一些,約 87%。(模型表示:不能再高了。)

稍微計算一下,小於 100 的質數總共有 25 個。
意思就是說模型全部都猜「非質數」,正確率也有 75%!
這個模型只有好一點點而已,看來夏恩去面試的話應該也不會被錄取...

這模型改進的方向應該可以從 imbalanced dataset 下去著手。
把質數與非質數的資料調整為一致,效果也許會更好。

後記

好的,回到最一開始的問題:
神經網路可以做質數分類器嗎?

答案是:可以唷!

朋友得知結果後兩手一攤:你真的...超級無聊欸!

恩...好吧。

附錄

# -*- coding: utf-8 -*-

import numpy as np
from tensorflow.keras import Sequential
from tensorflow.keras.layers import Dense

def get_prime(n):
    prime_list = []
    for i in range(2, n+1):
        is_prime = True  
        j_max = np.sqrt(i)
        for j in prime_list:
            if i%j == 0:
                is_prime = False
                break            
            if j > j_max:
                break
        
        if is_prime:
            prime_list.append(i)
            
    return prime_list

def get_dataset(n):
    # 取得值域為 0~n 的資料集
    
    # 計算最大值所需位元數
    n_bits = len(bin(n))-2
    
    # 計算資料數
    n_data = n+1
    
    # 產生 x,y 資料集
    x_dataset = np.zeros((n_data, n_bits))
    y_dataset = np.zeros((n_data, 2))
    
    # x_dataset binary encode
    for i, N in enumerate(range(0, n_data)):
        x_dataset[i,] = np.array(list(bin(N)[2:].zfill(n_bits)))
    
    # y_dataset one-hot encode
    # step1: assign prime to [0, 1]
    prime_list = get_prime(n)
    y_dataset[prime_list,] = np.array([0, 1])
    # step2: other numbers assign to [1, 0]
    idx = np.invert((np.sum(y_dataset, 1)).astype(np.bool))
    y_dataset[idx,] = np.array([1, 0])
    
    return y_dataset, x_dataset

def main():
    # get dataset
    y_dataset, x_dataset = get_dataset(10000)
    
    x_train = x_dataset[101:,]
    y_train = y_dataset[101:]
    
    x_test = x_dataset[1:101,]
    y_test = y_dataset[1:101]
    
    # setting model
    model = Sequential([
        Dense(input_dim=x_dataset.shape[1], units=256, activation='relu'),
        Dense(units=512, activation='relu'),
        Dense(2, activation='softmax') ])
    
    model.compile(optimizer='rmsprop',
                  loss='binary_crossentropy',
                  metrics=['acc'])
    
    model.fit(x_train, y_train, shuffle=True, batch_size=128, epochs=300)
    
    test_loss, test_acc = model.evaluate(x_test, y_test, batch_size=100)
    print('\nTest accuracy:', test_acc)

if __name__ == "__main__":
    main()