[ML] 機器學習基石：第十二講 Nonlinear Transformation

ML：基礎學習
課程：機器學習基石
簡介：第十二講 Nonlinear Transformation

利用轉換空間，從非線性變到線性

$$\begin{array}{rl}\mathbf{x}\in \mathbf{X}& \stackrel{\mathrm{\Phi }}{\to }\mathbf{z}\in \mathbf{Z}\\ {\mathrm{\Phi }}_2(\mathbf{x})& =(1,x_1,x_2,x_1^2,x_1{x}_2,x_2^2)\\ \stackrel{\mathbf{~}}{\mathbf{w}}& =(\widetilde{w_0},\widetilde{w_1},\widetilde{w_2},\widetilde{w_3},\widetilde{w_4},\widetilde{w_5})\\ H_{{\mathrm{\Phi }}_2}& =\{h(\mathbf{x}):h(\mathbf{x})=\tilde{h}({\mathrm{\Phi }}_2(\mathbf{x}))forsomelinear\tilde{h}on\mathbf{Z}\}\end{array}$$

${\mathrm{\Phi }}^{-1}$ 不一定存在，所以實際上是將點對應過去確認輸出，再畫回來

事實上，特徵的轉換 $\mathrm{\Phi }$ 也是一種轉換
若轉換為二次式 ${\mathrm{\Phi }}_2$，$\mathbf{x}\in {\mathbb{R}}^d$，請問 ${\mathrm{\Phi }}_2$ 的 dimension 為多少？
二次項：$(\genfrac{}{}{0ex}{}{d}{2})+d$
一次項：$d$
常數項：1
總共：$\frac{d^2}{2}+\frac{3d}{2}+1$

$\mathrm{\Phi }$ 的代價

$$\begin{array}{rl}{\mathrm{\Phi }}_Q(\mathbf{x})=(& 1,\\ & x_1,x_2,\cdots ,x_d,\\ & x_1^2,x_1{x}_2,\cdots ,x_d^2,\\ & \cdots \\ & x_1^Q,x_1^{Q-1}{x}_2,\cdots ,x_d^Q)\end{array}$$ 如下，共有這麼多項 $\mathbf{z}={\mathrm{\Phi }}_Q(\mathbf{x}),\stackrel{\mathbf{~}}{\mathbf{w}}$ 需要計算與儲存
所以 Q 變大，會導致計算效率變低與儲存空間變大
$$\underset{\widetilde{w_0}}{\underbrace{1}}+\underset{others}{\underbrace{\tilde{d}}}=(\genfrac{}{}{0ex}{}{Q+d}{Q})=(\genfrac{}{}{0ex}{}{Q+d}{d})=O(Q^d)$$

重複組合排列概念

簡單來說
先用 d = 3, Q = 2 的 2 次方項來看
$x_1^m\ast x_2^n\ast x_3^o$
也就是有 3(d) 個空箱是放逗號
有 2(Q) 個空箱是放次方
而 $m+n+o\le Q=2$
可能為常數或一次方，故多個放多餘次方的項 p
$m+n+o+p=Q=2$
故想像 (m,n,o,p)

空空空空空
xx,,, => $x_1^2$
x,x,, => $x_1{x}_2$
x,,x, => $x_1{x}_3$
x,,,x => $x_1$
,xx,, => $x_2^2$
,x,x, => $x_2{x}_3$
,x,,x => $x_2$
,,xx, => $x_3^2$
,,x,x => $x_3$
,,,xx => $1$

所以從 5 個空箱 (Q + d)
挑出 3 個空箱 (d) 來擺放逗號
或是
所以從 5 個空箱 (Q + d)
挑出 2 個空箱 (Q) 來擺放次方

$\stackrel{\mathbf{~}}{\mathbf{w}}=\tilde{d}+1=O(Q^d)\approx d_{VC}(H_{{\mathrm{\Phi }}_Q})$
有其上限
$d_{VC}(H_{{\mathrm{\Phi }}_Q})\le \tilde{d}+1$
因 $\tilde{d}+2$ 在 $\mathbf{Z}$ 無法 shatter
所以 $\tilde{d}+2$ 在 $\mathbf{X}$ 必定無法 shatter
所以 Q 變大，會導致 $d_{VC}$ 變大，使得複雜度變高

• $E_{in}$ 會變小
• $E_{out}$ 卻遠離 $E_{in}$ 

如何挑選 Q ？

用眼睛挑選嗎？
考慮以下這張圖，以下步驟 $d_{VC}$ 看似在減少

1.  ${\mathrm{\Phi }}_2:\mathbf{z}=(1,x_1,x_2,x_1^2,x_1{x}_2,x_2^2),d_{VC}=6$
2. 那是不是可以改為 $\mathbf{z}=(1,x_1^2,x_2^2),d_{VC}=3$ 
3. 或者 $\mathbf{z}=(1,x_1^2+x_2^2),d_{VC}=2$ 
4. 甚至 $\mathbf{z}=(sign(0.6-x_1^2-x_2^2)),d_{VC}=1$

實際上你的腦中已做了計算，這些計算實際上也是個複雜的 model，所以也需考慮進去
為了 VC-safely，$\mathrm{\Phi }$ 需要在偷看資料前就被決定，不然很可能被人為所影響

簡單範例

Q = 50, $\mathbf{x}\in {\mathbb{R}}^2$，請問 $\tilde{d}$為多少？
$\tilde{d}=(\genfrac{}{}{0ex}{}{Q+2}{2})-1=\frac{52\ast 51}{2}-1=1325$
可以發現轉換導致 dimension 變超大，那麼要考慮是否有足夠資料可使用？

$\mathrm{\Phi }$ 相互間的關係

$$\begin{array}{rl}{\mathrm{\Phi }}_0(\mathbf{x})& =(1)\\ {\mathrm{\Phi }}_1(\mathbf{x})& =({\mathrm{\Phi }}_0(\mathbf{x}),x_1,x_2,\cdots ,x_d)\\ {\mathrm{\Phi }}_2(\mathbf{x})& =({\mathrm{\Phi }}_1(\mathbf{x}),x_1^2,x_1{x}_2,\cdots ,x_d^2)\\ \\ {\mathrm{\Phi }}_3(\mathbf{x})& =({\mathrm{\Phi }}_2(\mathbf{x}),x_1^3,x_1^2{x}_2,\cdots ,x_d^3)\\ \\ ⋮& =⋮\\ {\mathrm{\Phi }}_Q(\mathbf{x})& =({\mathrm{\Phi }}_{Q-1}(\mathbf{x}),x_1^Q,x_1^{Q-1}{x}_2,\cdots ,x_d^Q)\end{array}$$

$$\begin{gathered} g_i=argmi{n}_{h\in H_i}{E}_{in}(h) \\ \begin{array}{ccccccccc}{H}_0& \subset & H_1& \subset & H_2& \subset & H_3& \subset & \cdots \\ d_{VC}(H_0)& \le & d_{VC}(H_1)& \le & d_{VC}(H_2)& \le & d_{VC}(H_3)& \le & \cdots \\ E_{in}(g_0)& \ge & E_{in}(g_1)& \ge & E_{in}(g_2)& \ge & E_{in}(g_3)& \ge & \cdots \end{array} \end{gathered}$$

如下圖，所以使用高維度 $H_{1126}$ 不見得會比較好

安全做法：不要一開始就套進高維度轉換

1.  從 $H_1$ 開始試
1. 假如 $E_{in}(g_1)$ 足夠小，那麼就 ok，且又安全
2. 不夠小，那麼再慢慢地增加維度，唯一浪費的只有計算量而已

線性 model 優先：
簡單，有效率，安全，做得還不錯