ACM_ICPCER

話說Fizz Buzz是什么鬼？

Fizz Buzz是洋人小朋友在學(xué)除法時常玩的游戲，玩法是：從1數(shù)到100，如果遇見了3的倍數(shù)要說Fizz，5的倍數(shù)就說Buzz，如果即是3的倍數(shù)又是5的倍數(shù)就說FizzBuzz。

最后演變?yōu)橐粋€編程面試題：寫一個程序輸出1到100，但是如果遇到數(shù)字為3的倍數(shù)時輸出Fizz，5的倍數(shù)輸出Buzz，既是3的倍數(shù)又是5的倍數(shù)輸出FizzBuzz。

面試中

面試官：你好，在開始面試之前要不要來杯水或來杯咖啡提提神。

我：不用，咖啡啥的我已經(jīng)喝的夠多了，三鹿也喝了不少。

面試官：很好，很好，你不介意在小白板上寫代碼吧。

我：It’s the only way I code!

面試官：….

我：那只是個笑話。

面試官：好吧，你是否熟悉”fizz buzz”。

我：….

面試官：你到底知不知道”fizz buzz”？

我：我知道”fizz buzz”，我只是不敢相信這么牛叉的IT巨頭竟然問這個問題。

面試官：OK，我要你現(xiàn)在寫一個程序輸出1到100，但是遇到數(shù)字為3的倍數(shù)時輸出Fizz，5的倍數(shù)輸出Buzz，既是3的倍數(shù)又是5的倍數(shù)輸出FizzBuzz。

我：額，這個，我會！

面試官：很好，我們發(fā)現(xiàn)不會解這個問題的人不能勝任我們這里的工作。

我：….

面試官：這是板擦和馬克筆。

我：[想了幾分鐘]

面試官：需不需要幫忙。

我：不，不用。首先先容我導(dǎo)入一些標(biāo)準(zhǔn)庫：

import numpy as np

import tensorflow as tf

面試官：你知道我們的問題是”fizz buzz”吧？

我：當(dāng)然，現(xiàn)在讓我們來討論一下模型，我正在想一個簡單的只有一個隱藏層的感知器。

面試官：感知器？

我：或神經(jīng)網(wǎng)絡(luò)，不管你怎么叫它。給它輸入數(shù)字，然后它能給我們輸出數(shù)字對應(yīng)的”fizz buzz”。但是，首先我們需要把數(shù)字轉(zhuǎn)為向量，最簡單的方法是把數(shù)字轉(zhuǎn)換為二進(jìn)制表示。

面試官：二進(jìn)制？

我：你懂的，就是一堆0和1，像這樣：

def binary_encode(i, num_digits):

return np.array([i >> d & 1 for d in range(num_digits)])

面試官：[盯著小白板看了一分鐘]

我：輸出應(yīng)該用one-hot編碼表示”fizz buzz”：

def fizz_buzz_encode(i):

if  i % 15 == 0: return np.array([0, 0, 0, 1]) # FizzBuzz

elif i % 5  == 0: return np.array([0, 0, 1, 0]) # Buzz

elif i % 3  == 0: return np.array([0, 1, 0, 0]) # Fizz

else:            return np.array([1, 0, 0, 0])

面試官：等一等，夠了！

我：沒錯，基本的準(zhǔn)備工作已經(jīng)完成了。現(xiàn)在我們需要生成一個訓(xùn)練數(shù)據(jù)，我們不用1到100訓(xùn)練，為了增加難度，我們使用100-1024訓(xùn)練：

NUM_DIGITS = 10

trX = np.array([binary_encode(i, NUM_DIGITS) for i in range(101, 2 ** NUM_DIGITS)])

trY = np.array([fizz_buzz_encode(i)          for i in range(101, 2 ** NUM_DIGITS)])

面試官：….

我：現(xiàn)在就可以使用TensorFlow搭模型了，我還不太確定隱藏層要使用多少”神經(jīng)元”，10，夠不？

面試官：….

我：100也許要好點，以后還可以再改：

NUM_HIDDEN = 100

定義輸入和輸出：

X = tf.placeholder("float", [None, NUM_DIGITS])

Y = tf.placeholder("float", [None, 4])

面試官：你到底要搞哪樣。

我：哦，這個網(wǎng)絡(luò)只有兩層深，一個隱藏層和一個輸出層。下面，讓我們使用隨機(jī)數(shù)初始化“神經(jīng)元”的權(quán)重：

def init_weights(shape):

return tf.Variable(tf.random_normal(shape, stddev=0.01))

w_h = init_weights([NUM_DIGITS, NUM_HIDDEN])

w_o = init_weights([NUM_HIDDEN, 4])

現(xiàn)在我們可以定義模型了，就像我前面說的，一個隱藏層。激活函數(shù)用什么呢，我不知道，就用ReLU吧：

def model(X, w_h, w_o):

h = tf.nn.relu(tf.matmul(X, w_h))

return tf.matmul(h, w_o)

我們可以使用softmax cross-entrop做為coss函數(shù)，并且試圖最小化它。

py_x = model(X, w_h, w_o)

cost = tf.reduce_mean(tf.nn.softmax_cross_entropy_with_logits(py_x, Y))

train_op = tf.train.GradientDescentOptimizer(0.05).minimize(cost)

面試官：….

我：當(dāng)然，最后還要取概率最大的預(yù)測做為結(jié)果：

predict_op = tf.argmax(py_x, 1)

面試官：在你偏離軌道過遠(yuǎn)之前，我要提醒你，我們的問題是生成1到100的”fizz buzz”。

我：哦，沒錯，現(xiàn)在predict_op輸出的值是0-3，還要轉(zhuǎn)換為”fizz buzz”輸出：

def fizz_buzz(i, prediction):

return [str(i), "fizz", "buzz", "fizzbuzz"][prediction]

面試官：….

我：現(xiàn)在我們可以訓(xùn)練模型了，首先創(chuàng)建一個session并初始化變量：

with tf.Session() as sess:

tf.global_variables_initializer().run()

就訓(xùn)練1000個大周天吧。

面試官：….

我：也許不夠，為了保險就訓(xùn)練10000個大周天。我們的訓(xùn)練數(shù)據(jù)是生成的序列，最好在每個大周天隨機(jī)打亂一下：

for epoch in range(10000):

p = np.random.permutation(range(len(trX)))

trX, trY = trX[p], trY[p]

每次取多少個樣本進(jìn)行訓(xùn)練，我不知道，128怎么樣？

BATCH_SIZE = 128

訓(xùn)練：

for start in range(0, len(trX), BATCH_SIZE):

end = start + BATCH_SIZE

sess.run(train_op, feed_dict={X: trX[start:end], Y: trY[start:end]})

我們還能看準(zhǔn)確率：

print(epoch, np.mean(np.argmax(trY, axis=1) == sess.run(predict_op, feed_dict={X: trX, Y: trY})))

面試官：你是認(rèn)真的嗎？

我：是，看準(zhǔn)確率提升曲線非常有幫助。

面試官：….

我：模型訓(xùn)練完了，現(xiàn)在是fizz buzz時間。給模型輸入1-100的二進(jìn)制表示：

numbers = np.arange(1, 101)

teX = np.transpose(binary_encode(numbers, NUM_DIGITS))

預(yù)測fizz buzz，大功告成：

teY = sess.run(predict_op, feed_dict={X: teX})

output = np.vectorize(fizz_buzz)(numbers, teY)

print(output)

面試官：….

我：這就是你要的”fizz buzz”。

面試官：夠了，我們會再聯(lián)系你。

我：聯(lián)系我！這可真喜人。

面試官：….

后記

我沒有得到offer，于是我運(yùn)行了一下這個代碼，事實證明有一些輸出是錯的。感謝機(jī)器學(xué)習(xí)十八代！！

['buzz' '2' 'fizz' 'buzz' 'buzz' 'fizz' '7' '8' 'fizz' 'buzz' '11' 'fizz'

'13' '14' 'fizzbuzz' 'fizz' '17' 'fizz' '19' 'buzz' 'fizz' '22' '23'

'fizz' 'buzz' '26' 'fizz' '28' '29' 'fizzbuzz' '31' '32' 'fizz' '34'

'buzz' 'fizz' '37' '38' 'fizz' 'buzz' '41' 'fizz' '43' '44' 'fizzbuzz'

'46' '47' 'fizz' 'fizz' 'buzz' 'fizz' '52' 'fizz' 'fizz' 'buzz' '56'

'fizz' '58' '59' 'fizzbuzz' '61' '62' 'fizz' '64' 'buzz' 'fizz' '67' '68'

'fizz' 'buzz' '71' 'fizz' '73' '74' 'fizzbuzz' '76' '77' 'fizz' '79'

'buzz' 'fizz' '82' '83' 'fizz' 'buzz' '86' 'fizz' '88' '89' 'fizzbuzz'

'91' '92' 'fizz' '94' 'buzz' 'fizz' '97' '98' 'fizz' 'buzz']

也許我應(yīng)該使用更深的網(wǎng)絡(luò)。

這當(dāng)然是嘲笑搞深度學(xué)習(xí)的同學(xué)過于教條主義的一個笑話。。。但是我們仔細(xì)思考，究竟能不能用深度學(xué)習(xí)獲得100%的準(zhǔn)確率？

import tensorflow as tf
from keras.layers.normalization import BatchNormalization
from keras.models import Sequential
from keras.layers.core import Dense,Dropout,Activation
from keras.optimizers import SGD,Adam
from keras.regularizers import l2
import numpy as np
import os
os.environ["TF_CPP_MIN_LOG_LEVEL"]='3'
def fizzbuzz(start,end):
    x_train,y_train=[],[]
    for i in range(start,end+1):
        num = i
        tmp=[0]*10
        j=0
        while num :
            tmp[j] = num & 1#這位是1嗎
            num = num>>1#右移一位
            j+=1
        x_train.append(tmp)
        if i % 3 == 0 and i % 5 ==0:
            y_train.append([0,0,0,1])
        elif i % 3 == 0:
            y_train.append([0,1,0,0])
        elif i % 5 == 0:
            y_train.append([0,0,1,0])
        else :
            y_train.append([1,0,0,0])
    return np.array(x_train),np.array(y_train)

x_train,y_train = fizzbuzz(101,1000) #打標(biāo)記函數(shù)
x_test,y_test = fizzbuzz(1,100)

model = Sequential()
model.add(Dense(input_dim=10,output_dim=1000))#100個neuron(hidden layer)
model.add(Activation('relu'))
'''
#model.add(Dense(input_dim=10,output_dim=100,kernel_regularizer=l2(0.0003)))#100個neuron(hidden layer)
model.add(Dense(input_dim=10,output_dim=200))#100個neuron(hidden layer)
model.add(Dropout(0.4))
model.add(Activation('relu'))
#model.add(Dense(input_dim=10,output_dim=100,kernel_regularizer=l2(0.0003)))#100個neuron(hidden layer)
model.add(Dense(input_dim=10,output_dim=100))#100個neuron(hidden layer)
model.add(Dropout(0.3))
model.add(Activation('relu'))
'''
model.add(Dense(output_dim=4))#4種情況
model.add(Activation('softmax'))
model.compile(loss='categorical_crossentropy',optimizer='adam',metrics=['accuracy'])

model.fit(x_train,y_train,batch_size=20,nb_epoch=100)

result = model.evaluate(x_test,y_test,batch_size=1000)

print('Acc：',result[1])

 嗯，沒毛病！

原文：https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/