習題2.1

感知機模型的函式表示為 \(f(x) = sign(w*x+b)\)

其中， \(sign(x)=\begin{cases} +1, & x \geq 0 \\ -1, & x < 0 \end{cases}\)

用表格列出異或（XOR）關系

假設存在這樣的超平面 \(w*x+b=0\) 可以對異或關系進行分隔，它應該滿足：

（1）根據 \(x_1=0, x_2=0\) ，則 \(w_1 *0 + w_2 * 0 + b <0\) ，得到 \(b <0\)

（2）根據 \(x_1=0, x_2=1\) ，則 \(w_1 *0 + w_2 * 1 + b \ge 0\) ，由（1）可得 \(w_2 \ge -b >0\)

（3）根據 \(x_1=1, x_2=0\) ，則 \(w_1 *1 + w_2 * 0 + b \ge 0\) ，由（1）可得 \(w_1 \ge -b >0\)

基于這三個不等式，代入第四個點，

根據 \(x_1=1, x_2=1\) ，則 \(w_1 *1 + w_2 * 1 + b <0\) ，然而由（1）-（3）可知，\(w_1+w_2+b \ge (-b) + (-b) + b = -b > 0\) ，產生矛盾，

因此，不存在這樣的超平面 \(w*x+b=0\) ，感知機不能表示異或，

習題2.2

略

習題2.3

證明以下定理：

樣本集線性可分的充分必要條件是正實體點集所構成的凸殼與負實體點集所構成的凸殼互不相交

定義 \(S\) 的凸殼 \(conv(S)\) 為

解釋幾個含義：

（1）線性可分：根據書中定義，存在一個超平面 \(w*x+b=0\) 使得特征空間分為兩部分，兩部分的點被分為正、負兩類

（2）凸殼：見定義

（3）正實體點構成的凸殼：\(conv(S^+) = \{ x^+= \sum \lambda_i x^{(i)} | \sum \lambda_i = 1, \lambda_i \ge 0, x_i \in \{x^{(i)}|y^{(i)}=1\}\}\)

（4）負實體點構成的凸殼：\(conv(S^-) = \{ x^- = \sum \lambda_i x^{(i)} | \sum \lambda_i = 1, \lambda_i \ge 0, x_i \in \{x^{(i)}|y^{(i)}=-1\}\}\)

先證必要性：線性可分 -> 互不相交

因為樣本集線性可分，所以存在一個超平面 \(w*x+b=0\) ，使得 \(\begin{cases} w*x^{(i)} \ge -b & x^{(i)} \in \{x^{(i)}|y^{(i)}=1\} \\ w*x^{(i)} < -b & x^{(i)} \in \{x^{(i)}|y^{(i)}=-1\}\end{cases}\) ，

對于正實體點集中任意一個點有 \(w*x^+ = w * \sum \limits_{x^{(i)} \in \{x^{(i)}|y^{(i)}=1\}} \lambda_i x^{(i)} = \sum \limits_{x^{(i)} \in \{x^{(i)}|y^{(i)}=1\}} \lambda_i w x^{(i)} \ge \sum \lambda_i*(-b) = -b\)

同理，對于負實體點集中任意一個點有 \(w*x^- = w * \sum \limits_{x^{(i)} \in \{x^{(i)}|y^{(i)}=-1\}} \lambda_i x^{(i)} = \sum \limits_{x^{(i)} \in \{x^{(i)}|y^{(i)}=-1\}} \lambda_i w x^{(i)} < \sum \lambda_i*(-b) = -b\)

所以 \(w*x^+ +b \ge 0\) 而 \(w*x^- +b < 0\) ，所以正實體點集所構成的凸殼與負實體點集所構成的凸殼落在超平面兩邊，互不相交，

再證充分性：互不相交 -> 線性可分

假設兩個點的距離為：\(L_2(x^{(i)}, x^{(j)}) = \left \| x^{(i)} - x^{(j)} \right\|_2\)

定義 \(conv(S^+)\) 與 \(conv(S^-)\) 的距離為 \(L_2(conv(S^+), conv(S^-)) = min (\left \| s^{+} - s^{-} \right\|_2)\) ，其中 $s^+ \in conv(S^+) , s^- \in conv(S^-) $

假設在正實體點凸殼與負實體點凸殼里各取兩個點，使得 \(x_{min}^+ \in conv(S^+) , x_{min}^- \in conv(S^-)\) 并且 \(L_2(x_{min}^+, x_{min}^-) = L_2(conv(S^+), conv(S^-))\)

因此，對于任意正實體點 \(x^+\) ，使得 \(L_2(x^+ , x_{min}^-) \ge L_2(x_{min}^+, x_{min}^-)\)

同理，對于任意負實體點 \(x^-\) ，使得 \(L_2(x^- , x_{min}^+) \ge L_2(x_{min}^+, x_{min}^-)\)

由于兩個凸殼互不相交，以 向量 \((x_{min}^+ - x_{min}^-)\) 作為法向量，過兩點中點 \(\frac{x_{min}^+ + x_{min}^-}{2}\) 做超平面\(w*x+b = 0\)，（簡而言之，以這兩個點為線段，做垂直平分面），其中 \(w = 2(x_{min}^+ - x_{min}^-)\)， \(b = (x_{min}^-)^2 - (x_{min}^+)^2\)

以中點 \(\frac{x_{min}^+ + x_{min}^-}{2}\) 為球心，\(\frac{L_2(x_{min}^+, x_{min}^-)}{2}\) 為半徑，過 \(x_{min}^+ - x_{min}^-\) 兩點做超球，

對于任意的正實體點 \(x^+\) ，\(w*x^+ + b = 2(x_{min}^+ - x_{min}^-)*x^+ + (x_{min}^-)^2 - (x_{min}^+)^2 = \left \| x_{min}^- - x^+ \right\|_2^2 - \left \| x_{min}^+ - x^+ \right\|_2^2 = L_2^2(x^+ , x_{min}^- ) - L_2^2(x^+ , x_{min}^+ )\)

用反證法證明 \(L_2(x^+ , x_{min}^- ) > L_2(x^+ , x_{min}^+ )\)

如果，\(L_2(x^+ , x_{min}^- ) \le L_2(x^+ , x_{min}^+ )\) ，根據 \(L_2(x^+ , x_{min}^-) \ge L_2(x_{min}^+, x_{min}^-)\) ，在以 $x^+ , x_{min}^- , x_{min}^+ $ 三個點構造的三角形中（三點可在一條直線上，只要滿足前面的不等式即可），最短邊為 \((x_{min}^+, x_{min}^-)\)， 最長邊為\((x_{min}^+, x^+)\) ，且 \(x_{min}^+\) 位于超球外，

假設最長邊 \((x_{min}^+, x^+)\) 與超球交于 \(x_r^+\) 點，根據凸殼具有凸性可知， \(x_r^+\) 也位于正實體點凸殼中，且該點距離 \(x_{min}^-\) 更近，產生矛盾，

所以 \(w*x^+ + b > 0\)

同理，對于任意負實體點 \(x^-\) 亦可得出類似結論，

所以充分性得證，

標籤：其他

上一篇：微軟官方 Win 11 “體檢工具”太爛了？開發者自己做了一個

下一篇：《統計學習方法》第3章習題