2016年7月27日 星期三
2016年7月12日 星期二
[SL] Perceptron
在 Feature Space 中，如果有一個 Hyperplane $H$ 使得 Data Set 在線性可分的前提下，能夠完全的正確分開；找出這個 Hyperplane 即為 Perceptron 的意義。
給一個二維 Data Set 的例子，假設有 2 個 Feature $ X = \{ X_{1},X_{2} \} $ 皆為一個 $ n \times 1 $ 的向量，而 $ Y = \{ y_{1},y_{2},...,y_{n} \}^{T} \in \{-1,+1\} $
也為一個 $ n \times\ 1 $ 的向量，其中 $Y$ 即為我們的 Response Variable，並且 Label 不是 $-1$ 就是 $+1$。
假設這個 Feature Space 中，有一條直線 $H$，可以將 Response 完美的分開，這條直線就是由 Feature Space 所生成的 Hyperplane，
所以，設定這個 Hyperplane 的法向量(係數/Feature 的權重) 為 $W = (w_{1},w_{2})$ 是一個 $ 2 \times 1 $ 的向量 ，若某一筆資料 $X_{i} = (x_{1i},x_{2i})$ 與 $W$ 的內積大於 0，
表示此筆資料與 Hyperplane 的法向量同側，藉由測試 $ H(x_{i}) = \beta_{0} + W \cdot X_{i} $ 為大於 0 或 小於等於 0，作為分類的依據。
所以，若 $ H(x_{i}) > 0 $ 時，假設代表 $x_{i}$ 這個點應該要被分到 $+1$，但若實際上，$y_{i}$ 卻是 $-1$，即分類錯誤的情況，此時 $ y_{i} \times H(x_{i}) \leq 0 $；
由於一開始的假設，在這個 Data Set 一定可以找到一個線性的 Hyperplane 可以完全的正確分類，因此碰到分類錯誤的情況，只要調整 Hyperplane 的法向量 $W$ 即可進行調整，
所以需要測試 $ y_{i} \times \beta_{0} + W \cdot X_{i} = y_{i} \times [ sign ( H(x_{i}) ) ]$，並將此作為 Loss Function 來幫助優化模型，
但因為使用了 sign 函數取值，不像傳統的 Mean Squared Loss Function 可以使用微積分進行處理，因此採用 Gradient Descent 來進行疊代調整 Hyperplane 的法向量。
而 Novikoff Theorem 表示，如果在 Feature Space 中，有一個 "線性的" Hyperplane 可以完全正確分開 Response Variable，
這樣 Perceptron 在 Training Data Set 所犯下的分類錯誤次數是有上限的，意即採 Gradient Descent 疊代調整的 Perceptron 的法向量最終會收斂。
假設我們有一組滿足上面假設的 Dataset $D = (x_1,y_1), (x_2,y_2), ... ,(x_n,y_n) ,\: x_i \in {\rm I\!R}^{p} ,\: y_i \in \{-1,+1\} $，Novikoff Theorem 中包含兩點 :
1. 令此 Hyperplane $H$ ，並滿足 $\|H\|=1$，且存在 $\gamma \geq 0$ ，對所有 $ i = 1,2,...,n $ 而言， $ y_{i}(W_{H} \cdot x_{i} + \beta_{H}) \geq \gamma $
2. 令 $ R = max \| x_i \|, \forall i $ ， $k$ 為 Perceptron 在 Training Data Set 所犯下的分類錯誤次數，其滿足 : $ k \leq (\, \dfrac{R}{\gamma} )\,^{2} $
以 Weight Vector 尚未收斂的 Hyperplane $ W_{k-1} \cdot x +\beta_{k-1} $ 而言 (疊代到 k-1 次)，若對某一個 $y_{i}$ 進行了錯誤分類 $\hat{y}_i$，代表 $y_{i} \times \hat{y}_{i} = y_{i}(W_{k-1} \cdot x_{i} + \beta_{k-1}) \leq 0 $，
所以我們可以了解，若疊代到收斂後，形成一個可完美分類的 Hyperplane， $ y_{i}( W_{H} \cdot x_{i} + \beta_{H} ) > 0 , \forall i$ ， 至少一定會有一個極小值 $\gamma$，
滿足 $\gamma = min_{i} \, y_{i}( W_{H} \cdot x_{i} + \beta_{H} ) $，因此可以很直觀的看出 $ y_{i}( W_{H} \cdot x_{i} + \beta_{H} ) \geq \gamma $
第 2 點的證明可以參考 Andrew Ng 的 Lecture notes : http://cs229.stanford.edu/notes/cs229-notes6.pdf
需要注意的地方包括 :
(1) Perceptron 是使用分類錯誤來進行驅動(疊代)的演算法。
(2) $ x \cdot y \leq \|x\| \|y\| $
(3) $ \| W_{H} \| = 1 $ (這點很重要，我想了半小時才突然發現有這條件 XD)
暫時貼上自己寫的陽春版 Perceptron Demo :
給一個二維 Data Set 的例子，假設有 2 個 Feature $ X = \{ X_{1},X_{2} \} $ 皆為一個 $ n \times 1 $ 的向量，而 $ Y = \{ y_{1},y_{2},...,y_{n} \}^{T} \in \{-1,+1\} $
也為一個 $ n \times\ 1 $ 的向量，其中 $Y$ 即為我們的 Response Variable，並且 Label 不是 $-1$ 就是 $+1$。
假設這個 Feature Space 中，有一條直線 $H$，可以將 Response 完美的分開，這條直線就是由 Feature Space 所生成的 Hyperplane，
所以，設定這個 Hyperplane 的法向量(係數/Feature 的權重) 為 $W = (w_{1},w_{2})$ 是一個 $ 2 \times 1 $ 的向量 ，若某一筆資料 $X_{i} = (x_{1i},x_{2i})$ 與 $W$ 的內積大於 0，
表示此筆資料與 Hyperplane 的法向量同側，藉由測試 $ H(x_{i}) = \beta_{0} + W \cdot X_{i} $ 為大於 0 或 小於等於 0，作為分類的依據。
所以，若 $ H(x_{i}) > 0 $ 時，假設代表 $x_{i}$ 這個點應該要被分到 $+1$，但若實際上，$y_{i}$ 卻是 $-1$，即分類錯誤的情況，此時 $ y_{i} \times H(x_{i}) \leq 0 $；
由於一開始的假設，在這個 Data Set 一定可以找到一個線性的 Hyperplane 可以完全的正確分類，因此碰到分類錯誤的情況，只要調整 Hyperplane 的法向量 $W$ 即可進行調整，
所以需要測試 $ y_{i} \times \beta_{0} + W \cdot X_{i} = y_{i} \times [ sign ( H(x_{i}) ) ]$，並將此作為 Loss Function 來幫助優化模型，
但因為使用了 sign 函數取值，不像傳統的 Mean Squared Loss Function 可以使用微積分進行處理，因此採用 Gradient Descent 來進行疊代調整 Hyperplane 的法向量。
而 Novikoff Theorem 表示，如果在 Feature Space 中，有一個 "線性的" Hyperplane 可以完全正確分開 Response Variable，
這樣 Perceptron 在 Training Data Set 所犯下的分類錯誤次數是有上限的，意即採 Gradient Descent 疊代調整的 Perceptron 的法向量最終會收斂。
假設我們有一組滿足上面假設的 Dataset $D = (x_1,y_1), (x_2,y_2), ... ,(x_n,y_n) ,\: x_i \in {\rm I\!R}^{p} ,\: y_i \in \{-1,+1\} $，Novikoff Theorem 中包含兩點 :
1. 令此 Hyperplane $H$ ，並滿足 $\|H\|=1$，且存在 $\gamma \geq 0$ ，對所有 $ i = 1,2,...,n $ 而言， $ y_{i}(W_{H} \cdot x_{i} + \beta_{H}) \geq \gamma $
2. 令 $ R = max \| x_i \|, \forall i $ ， $k$ 為 Perceptron 在 Training Data Set 所犯下的分類錯誤次數，其滿足 : $ k \leq (\, \dfrac{R}{\gamma} )\,^{2} $
以 Weight Vector 尚未收斂的 Hyperplane $ W_{k-1} \cdot x +\beta_{k-1} $ 而言 (疊代到 k-1 次)，若對某一個 $y_{i}$ 進行了錯誤分類 $\hat{y}_i$，代表 $y_{i} \times \hat{y}_{i} = y_{i}(W_{k-1} \cdot x_{i} + \beta_{k-1}) \leq 0 $，
所以我們可以了解，若疊代到收斂後，形成一個可完美分類的 Hyperplane， $ y_{i}( W_{H} \cdot x_{i} + \beta_{H} ) > 0 , \forall i$ ， 至少一定會有一個極小值 $\gamma$，
滿足 $\gamma = min_{i} \, y_{i}( W_{H} \cdot x_{i} + \beta_{H} ) $，因此可以很直觀的看出 $ y_{i}( W_{H} \cdot x_{i} + \beta_{H} ) \geq \gamma $
第 2 點的證明可以參考 Andrew Ng 的 Lecture notes : http://cs229.stanford.edu/notes/cs229-notes6.pdf
需要注意的地方包括 :
(1) Perceptron 是使用分類錯誤來進行驅動(疊代)的演算法。
(2) $ x \cdot y \leq \|x\| \|y\| $
(3) $ \| W_{H} \| = 1 $ (這點很重要，我想了半小時才突然發現有這條件 XD)
暫時貼上自己寫的陽春版 Perceptron Demo :
 |
| (1-1) 使用 Perceptron 對 iris 部份資料集進行分類 |
訂閱：
文章 (Atom)