<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Supervised learning for classification
給一堆 $x$, 和他的分類，我們找出計算 x 的分類的方式
One hot encoding
如果我們有三類種類別， 我們可以來編碼這三個類別
* $(1,0,0)$
* $(0,1,0)$
* $(0,0,1)$
問題
為什麼不直接用 1,2,3 這樣的編碼呢？
Softmax Regression 的模型是這樣的
我們的輸入 $x=\begin{pmatrix} x_0 \ x_1 \ x_2 \ x_3 \end{pmatrix} $ 是一個向量，我們看成 column vector 好了
而 Weight
Step1:  任務：計算最後的猜測機率 $q$
Hint
Step2:  練習
設計一個網路
Step3:  練習
設計一個網路
Step4:  Gradient descent
誤差函數
為了要評斷我們的預測的品質，要設計一個評斷誤差的方式
假設輸入值 $x$ 對應到的真實類別是 $y$, 那我們定義誤差函數
$ loss = -\log(q(y))=- \log(Predict(Y=y|x, W,b)) $
其實比較一般但比較複雜一點的寫法是
$ loss = - \sum_i p(i)\log(q(i))  $
其中 $i$ 是所有類別， 而 $ p(i) = \Pr(Y=i|x) $ 是真實發生的機率
但我們目前 $x$ 對應到的真實類別是 $y$， 所以直接 $p(y)=1$
想辦法改進。
我們用一種被稱作是 gradient descent 的方式來改善我們的誤差。
因為我們知道 gradient 是讓函數上升最快的方向。所以我們如果朝 gradient 的反方向走一點點（也就是下降最快的方向），那麼得到的函數值應該會小一點。
記得我們的變數是 $W$ 和 $b$ (裡面有一堆 W_i,j b_i 這些變數)，所以我們要把 $loss$ 對 $W$ 和 $b$ 裡面的每一個參數來偏微分。
還好這個偏微分是可以用手算出他的形式，而最後偏微分的式子也不會很複雜。
$loss$ 展開後可以寫成
$loss = -\log(q(y)) = \log(\sum_j d_j) - d_i \
= \log(\sum_j e^{W_j x + b_j}) - W_i x - b_i$
注意 $d_j = e^{W_j x + b_j}$ 只有變數 $b_j, W_j$ 
對 $k \neq i$ 時, $loss$ 對 $b_k$ 的偏微分是 
 $$ \frac{e^{W_k x + b_k}}{\sum_j e^{W_j x + b_j}} = q(k)$$
對 $k = i$ 時, $loss$ 對 $b_k$ 的偏微分是 
$$ q(k) - 1$$
對 $W$ 的偏微分也不難
對 $k \neq i$ 時, $loss$ 對 $W_{k,t}$ 的偏微分是 
 $$ \frac{e^{W_k x + b_k} W_{k,t} x_t}{\sum_j e^{W_j x + b_j}} = q(k) x_t$$
對 $k = i$ 時, $loss$ 對 $W_{k,t}$ 的偏微分是 
$$ q(k) x_t - x_t$$
實做部份
Step5:  問題
W, b 的 size 為什麼要這樣設定？
任務： 隨便設定一組 x, y, 我們來跑跑看 gradient descent
Step6:  步驟：計算 q
Step7:  步驟： 計算 loss
Step8:  步驟：計算對 b 的 gradient
Step9:  步驟：計算對 W 的 gradient
Step10:  步驟：更新 W, b  各減掉 0.5 * gradient， 然後看看新的 loss 是否有進步了？
Step11:  一次訓練多組資料
上面只針對一組 x (i=14) 來訓練，如果一次對所有 x 訓練呢？
通常我們會把組別放在 axis-0
Step12:  任務： 將訓練向量化
Step13:  對照
python
d = np.exp(W @ x + b)
q = d/d.sum()
q
Step14:  對照
python
loss = -np.log(q[y])
loss
Step15:  對照
python
grad_b = q - np.eye(3)[y][
Step16:  對照
python
grad_W = grad_b @ x.T
Step17:  任務：全部合在一起
設定 W,b
設定 X
訓練三十次
計算 q 和 loss    
計算 grad_b 和 grad_W
更新 W, b
看看準確度
<ASSISTANT_TASK:>
Python Code:
# Weight
W = Matrix([1,2],[3,4], [5,6])
W
# Bias
b = Vector(1,0,-1)
b
# 輸入
x = Vector(2,-1)
x
Explanation: Supervised learning for classification
給一堆 $x$, 和他的分類，我們找出計算 x 的分類的方式
One hot encoding
如果我們有三類種類別， 我們可以來編碼這三個類別
* $(1,0,0)$
* $(0,1,0)$
* $(0,0,1)$
問題
為什麼不直接用 1,2,3 這樣的編碼呢？
Softmax Regression 的模型是這樣的
我們的輸入 $x=\begin{pmatrix} x_0 \ x_1 \ x_2 \ x_3 \end{pmatrix} $ 是一個向量，我們看成 column vector 好了
而 Weight: $W = \begin{pmatrix} W_0 \ W_1 \ W_2 \end{pmatrix} =
\begin{pmatrix} W_{0,0} & W_{0,1} &  W_{0,2} & W_{0,3}\ 
 W_{1,0} & W_{1,1} &  W_{1,2} & W_{1,3} \ 
 W_{2,0} & W_{2,1} &  W_{2,2} & W_{2,3} \end{pmatrix} $
Bias: $b=\begin{pmatrix} b_0 \ b_1 \ b_2 \end{pmatrix} $ 
我們先計算"線性輸出"  $ c = \begin{pmatrix} c_0 \ c_1 \ c_2 \end{pmatrix} =  Wx+b =
\begin{pmatrix} W_0 x + b_0 \ W_1 x + b_1 \ W_2 x + b_2 \end{pmatrix}   $， 然後再取 $exp$ (逐項取)。 最後得到一個向量。
$d = \begin{pmatrix} d_0 \ d_1 \ d_2 \end{pmatrix} = e^{W x + b} = \begin{pmatrix} e^{c_0} \ e^{c_1} \ e^{c_2} \end{pmatrix}$
將這些數值除以他們的總和。
我們希望出來的數字會符合這張圖片是這個數字的條件機率。
$q(i) = Predict_{W,b}(Y=i|x)  = \frac {e^{W_i x + b_i}} {\sum_j e^{W_j x + b_j}} = \frac {d_i} {\sum_j d_j}$
問題
為什麼要用 $exp$?
先隨便算一個 $\mathbb{R}^2 \rightarrow \mathbb{R}^3$ 的網路
End of explanation
# 參考答案
# Wx+b
c = W @ x + b
# d = exp(Wx+b)
d = np.exp(c)
# q = d/sum(d)
q = d/d.sum()
Explanation: 任務：計算最後的猜測機率 $q$
Hint: np.exp 可以算 $exp$
End of explanation
# Hint 下面產生數字 i 的 2 進位向量
i = 13
x = Vector(i%2, (i>>1)%2, (i>>2)%2, (i>>3)%2)
x
# 參考答案
W = Matrix([-1,-1,0,0], [1,-1,0,0], [-1,1,0,0], [1,1,0,0])
b = Vector(0,0,0,0)
for i in range(16):
    x = Vector(i%2, (i>>1)%2, (i>>2)%2, (i>>3)%2)
    r = W @ x + b
    print("i=", i, "predict:", r.argmax(), "ground truth:", i%4)
Explanation: 練習
設計一個網路:
* 輸入是二進位 0 ~ 15
* 輸出依照對於 4 的餘數分成四類
Hint: 可以參考上面 W, b 的設定方式
End of explanation
# 參考答案
W = Matrix([0,0,0,0], [1,-1,1,-1], [-1,1,-1,1])
b = Vector(0.1,0,0)
for i in range(16):
    x = Vector(i%2, (i>>1)%2, (i>>2)%2, (i>>3)%2)
    r = W @ x + b
    print("i=", i, "predict:", r.argmax(), "ground truth:", i%3)
Explanation: 練習
設計一個網路:
* 輸入是二進位 0 ~ 15
* 輸出依照對於 3 的餘數分成三類
Hint: 不用全部正確，用猜的，但正確率要比亂猜高。可以利用統計的結果猜猜看。
End of explanation
# 先產生隨機的 W 和 b
W = Matrix(np.random.normal(size=(3,4)))
b = Vector(np.random.normal(size=(3,)))
W
b
Explanation: Gradient descent
誤差函數
為了要評斷我們的預測的品質，要設計一個評斷誤差的方式
假設輸入值 $x$ 對應到的真實類別是 $y$, 那我們定義誤差函數
$ loss = -\log(q(y))=- \log(Predict(Y=y|x, W,b)) $
其實比較一般但比較複雜一點的寫法是
$ loss = - \sum_i p(i)\log(q(i))  $
其中 $i$ 是所有類別， 而 $ p(i) = \Pr(Y=i|x) $ 是真實發生的機率
但我們目前 $x$ 對應到的真實類別是 $y$， 所以直接 $p(y)=1$
想辦法改進。
我們用一種被稱作是 gradient descent 的方式來改善我們的誤差。
因為我們知道 gradient 是讓函數上升最快的方向。所以我們如果朝 gradient 的反方向走一點點（也就是下降最快的方向），那麼得到的函數值應該會小一點。
記得我們的變數是 $W$ 和 $b$ (裡面有一堆 W_i,j b_i 這些變數)，所以我們要把 $loss$ 對 $W$ 和 $b$ 裡面的每一個參數來偏微分。
還好這個偏微分是可以用手算出他的形式，而最後偏微分的式子也不會很複雜。
$loss$ 展開後可以寫成
$loss = -\log(q(y)) = \log(\sum_j d_j) - d_i \
= \log(\sum_j e^{W_j x + b_j}) - W_i x - b_i$
注意 $d_j = e^{W_j x + b_j}$ 只有變數 $b_j, W_j$ 
對 $k \neq i$ 時, $loss$ 對 $b_k$ 的偏微分是 
 $$ \frac{e^{W_k x + b_k}}{\sum_j e^{W_j x + b_j}} = q(k)$$
對 $k = i$ 時, $loss$ 對 $b_k$ 的偏微分是 
$$ q(k) - 1$$
對 $W$ 的偏微分也不難
對 $k \neq i$ 時, $loss$ 對 $W_{k,t}$ 的偏微分是 
 $$ \frac{e^{W_k x + b_k} W_{k,t} x_t}{\sum_j e^{W_j x + b_j}} = q(k) x_t$$
對 $k = i$ 時, $loss$ 對 $W_{k,t}$ 的偏微分是 
$$ q(k) x_t - x_t$$
實做部份
End of explanation
i = 14
x = Vector(i%2, (i>>1)%2, (i>>2)%2, (i>>3)%2)
y = i%3
Explanation: 問題
W, b 的 size 為什麼要這樣設定？
任務： 隨便設定一組 x, y, 我們來跑跑看 gradient descent
End of explanation
# 參考答案
# Wx+b
c = W @ x + b
# d = exp(Wx+b)
d = np.exp(c)
# q = d/sum(d)
q = d/d.sum()
Explanation: 步驟：計算 q
End of explanation
# 參考答案
loss = -np.log(q[y])
loss
Explanation: 步驟： 計算 loss
End of explanation
#參考答案
%run -i  softmax_compute_grad_b.py
grad_b
Explanation: 步驟：計算對 b 的 gradient
End of explanation
# 參考答案
grad_W =   q @ x.T
grad_W[y] -= x.ravel()
# or 
grad_W = grad_b @ x.T
grad_W
Explanation: 步驟：計算對 W 的 gradient
End of explanation
# 參考答案
%run -i softmax_update_Wb.py
# 原先的 q
q
# 原先的 loss
loss
# 現在的 loss
%run -i softmax_compute_q.py
%run -i softmax_compute_loss1.py
loss
q
Explanation: 步驟：更新 W, b  各減掉 0.5 * gradient， 然後看看新的 loss 是否有進步了？
End of explanation
X = np.array([Vector(i%2, (i>>1)%2, (i>>2)%2, (i>>3)%2) for i in range(16)])
for i in range(4):
    print("i=", i)
    display(X[i])
X
# 對應的組別 
y = np.array([i%3 for i in range(16)])
y
Explanation: 一次訓練多組資料
上面只針對一組 x (i=14) 來訓練，如果一次對所有 x 訓練呢？
通常我們會把組別放在 axis-0
End of explanation
# 請在這裡計算
# 參考解答如後
Explanation: 任務： 將訓練向量化
End of explanation
d = np.exp(W @ X + b)
q = d/d.sum(axis=(1,2), keepdims=True)
q
Explanation: 對照
python
d = np.exp(W @ x + b)
q = d/d.sum()
q
End of explanation
loss = -np.log(q[range(len(y)), y])
loss
# 用平均當成我們真正的 loss
loss.mean()
Explanation: 對照
python
loss = -np.log(q[y])
loss
End of explanation
# fancy indexing :p
one_y = np.eye(3)[y][..., None]
grad_b_all = q - one_y
grad_b = grad_b_all.mean(axis=0)
grad_b
Explanation: 對照
python
grad_b = q - np.eye(3)[y][:, None]
End of explanation
grad_W_all = grad_b_all @ X.swapaxes(1,2)
grad_W = grad_W_all.mean(axis=0)
grad_W
W -=  0.5 * grad_W
b -=  0.5 * grad_b
# 之前的 loss
loss.mean()
d = np.exp(W @ X + b)
q = d/d.sum(axis=(1,2), keepdims=True)
loss = -np.log(q[range(len(y)), y])
loss.mean()
Explanation: 對照
python
grad_W = grad_b @ x.T
End of explanation
# 在這裡計算
# 參考答案
%run -i softmax_train.py
# 畫出 loss 的曲線
%matplotlib inline
import matplotlib.pyplot as plt
plt.plot(loss_history);
# 對答案
display((W @ X + b).argmax(axis=1).ravel())
display(y)
Explanation: 任務：全部合在一起
設定 W,b
設定 X
訓練三十次
計算 q 和 loss    
計算 grad_b 和 grad_W
更新 W, b
看看準確度
End of explanation
<END_TASK>