Homework 1 1. Theory of Hard-Margin Support Vector Machines ( a ) (a) ( a ) Show the Equation
can be rewritten as the dual optimization problem:
max λ i ≥ 0 ( ∑ i = 1 n λ i − 1 4 ∑ i = 1 n ∑ j = 1 n λ i λ j y i y j X i ⋅ X j ) subject to ∑ i = 1 n λ i y i = 0. (4) \max_{\lambda_i \ge 0}\;\left(\sum_{i=1}^n \lambda_i - \frac{1}{4}\sum_{i=1}^n\sum_{j=1}^n \lambda_i\lambda_j y_i y_j X_i\cdot X_j\right) \quad\text{subject to}\quad \sum_{i=1}^n \lambda_i y_i = 0. \tag{4} λ i ≥ 0 max ( i = 1 ∑ n λ i − 4 1 i = 1 ∑ n j = 1 ∑ n λ i λ j y i y j X i ⋅ X j ) subject to i = 1 ∑ n λ i y i = 0. ( 4 ) p r o o f : proof: p roo f :
我们对原始拉格朗日表达式求偏导，令参数偏导为 0：
∂ L ∂ w = 2 w − ∑ i = 1 n λ i y i X i = 0 ⇒ w = 1 2 ∑ i = 1 n λ i y i X i (1-1) \frac{\partial L}{\partial w} = 2w - \sum_{i=1}^n λ_i y_i X_i=0\Rightarrow w=\frac{1}{2}\sum_{i=1}^n λ_i y_i X_i\tag{1-1} ∂ w ∂ L = 2 w − i = 1 ∑ n λ i y i X i = 0 ⇒ w = 2 1 i = 1 ∑ n λ i y i X i ( 1-1 ) ∂ L ∂ α = − ∑ i = 1 n λ i y i = 0 (1-2) \frac{\partial L}{\partial \alpha} = - \sum_{i=1}^n λ_i y_i = 0 \tag{1-2} ∂ α ∂ L = − i = 1 ∑ n λ i y i = 0 ( 1-2 ) 我们将 ( 1 − 1 ) (1-1) ( 1 − 1 ) ∥ w ∥ 2 = w ⋅ w T \|w\|^2=w \cdot w^T ∥ w ∥ 2 = w ⋅ w T L L L
L = ∑ i = 1 n λ i + ( 1 2 ∑ i = 1 n λ i y i X i ) ( 1 2 ∑ i = 1 n λ i y i X i ) T − ∑ i = 1 n λ i y i x i ⋅ ( 1 2 ∑ i = 1 n λ i y i X i ) L=\sum_{i=1}^n \lambda_i + (\frac{1}{2}\sum_{i=1}^n λ_i y_i X_i)(\frac{1}{2}\sum_{i=1}^n λ_i y_i X_i)^T - \sum_{i=1}^n \lambda_iy_ix_i \cdot (\frac{1}{2}\sum_{i=1}^n λ_i y_i X_i) L = i = 1 ∑ n λ i + ( 2 1 i = 1 ∑ n λ i y i X i ) ( 2 1 i = 1 ∑ n λ i y i X i ) T − i = 1 ∑ n λ i y i x i ⋅ ( 2 1 i = 1 ∑ n λ i y i X i ) 将点成转换成双重求和即可得到待证式子。
( b ) (b) ( b ) Suppose we know the values λ i ∗ λ^*_i λ i ∗ α ∗ α^* α ∗ ( 3 ) (3) ( 3 )
r ( x ) = { + 1 , if w ⋅ x + α ≥ 0 , − 1 , otherwise. r(x)= \begin{cases} +1, & \text{if }\ \mathbf{w}\cdot\mathbf{x}+\alpha \ge 0,\\[4pt] -1, & \text{otherwise.} \end{cases} r ( x ) = { + 1 , − 1 , if w ⋅ x + α ≥ 0 , otherwise. can be written
r ( x ) = { + 1 , if α ∗ + 1 2 ∑ i = 1 n λ i ∗ y i X i ⋅ x ≥ 0 , − 1 , otherwise. r(x)= \begin{cases} +1, & \text{if }\ \alpha^{*} + \dfrac{1}{2}\sum_{i=1}^n \lambda_i^{*}\,y_i\,\mathbf{X}_i\cdot\mathbf{x} \ge 0,\\[6pt] -1, & \text{otherwise.} \end{cases} r ( x ) = ⎩ ⎨ ⎧ + 1 , − 1 , if α ∗ + 2 1 ∑ i = 1 n λ i ∗ y i X i ⋅ x ≥ 0 , otherwise. p r o o f : proof: p roo f : ( a ) (a) ( a ) w w w
( c ) (c) ( c ) Applying KKT conditions, any pair of optimal primal and dual solutions w ∗ w^∗ w ∗ α ∗ α^∗ α ∗ λ ∗ λ^∗ λ ∗
λ i ∗ ( y i ( X i ⋅ w ∗ + α ∗ ) − 1 ) = 0 ∀ i ∈ { 1 , … , n } λ^∗_i (y_i(X_i \cdot w^∗ + \alpha^∗) − 1) = 0 \quad \forall i \in \lbrace 1, \dots , n \rbrace λ i ∗ ( y i ( X i ⋅ w ∗ + α ∗ ) − 1 ) = 0 ∀ i ∈ { 1 , … , n } This condition is called complementary slackness. Explain what this implies for points corresponding to λ i ∗ > 0 λ^∗_i > 0 λ i ∗ > 0
A n s w e r : Answer: A n s w er : λ i ∗ < 0 \lambda^*_i \lt 0 λ i ∗ < 0 λ i ∗ ( y i ( X i ⋅ w ∗ + α ∗ ) − 1 ) = 0 λ^∗_i (y_i(X_i \cdot w^∗ + \alpha^∗) − 1) = 0 λ i ∗ ( y i ( X i ⋅ w ∗ + α ∗ ) − 1 ) = 0 y i ( X i ⋅ w ∗ + α ∗ ) − 1 = 0 y_i(X_i \cdot w^∗ + \alpha^∗) − 1 = 0 y i ( X i ⋅ w ∗ + α ∗ ) − 1 = 0 这个点落在我们的分割边界上 。
( d ) (d) ( d ) The training points X i X_i X i λ i ∗ > 0 λ^∗_i > 0 λ i ∗ > 0
A n s w e r : Answer: A n s w er : ( b ) (b) ( b )
r ( x ) = { + 1 , if α ∗ + 1 2 ∑ i = 1 n λ i ∗ y i X i ⋅ x ≥ 0 , − 1 , otherwise. r(x)= \begin{cases} +1, & \text{if }\ \alpha^{*} + \dfrac{1}{2}\sum_{i=1}^n \lambda_i^{*}\,y_i\,\mathbf{X}_i\cdot\mathbf{x} \ge 0,\\[6pt] -1, & \text{otherwise.} \end{cases} r ( x ) = ⎩ ⎨ ⎧ + 1 , − 1 , if α ∗ + 2 1 ∑ i = 1 n λ i ∗ y i X i ⋅ x ≥ 0 , otherwise. 对于求和中的每一项 λ i ∗ y i X i ⋅ x λ^*_i y_i \mathbf{X_i} \cdot \mathbf{x} λ i ∗ y i X i ⋅ x X i \mathbf{X_i} X i λ ∗ i = 0 λ*_i = 0 λ ∗ i = 0 对最终的求和结果没有任何贡献 。因此，决策规则的求和部分实际上可以简化为只对支持向量进行求和：
∑ i = 1 n λ i ∗ y i X i ⋅ x = ∑ i ∈ V λ i ∗ y i X i ⋅ x \sum_{i=1}^n λ^*_i y_i \mathbf{X_i} \cdot \mathbf{x} = \sum_{i \in V} λ^*_i y_i \mathbf{X_i} \cdot \mathbf{x} i = 1 ∑ n λ i ∗ y i X i ⋅ x = i ∈ V ∑ λ i ∗ y i X i ⋅ x
Comments