传统方法是对 loss function 求导并检验 stationary point，但此处使用传统方法无法得到最优解，since it’s NP-hard to solve or approximate.

Finding Weights (Related Assumptions)

尽管问题是 NP-hard，我们可以通过做出进一步的合理假设来简化问题，使得 weight 可以被估计。例如，我们可以假设 training data 是线性可分的（linear separable）。

Linear Separability

假设：存在一条线性的 linear decision boundary 完美地对 training data 进行分类。

现在给定 labeled training data:

希望判断：是否存在 (vec{w}) such that:

注意上式中 (y_{i} (vec{w} cdot vec{x_{i}}) geq 0) 说明 (y_{i}) 和 ((vec{w} cdot vec{x_{i}})) 符号相同，即代表分类正确。

这等价于：training data 是否 linearly separable？

由于存在 (d+1) 个变量（指 (vec{x_{i}} in mathbb{R}^{d})，即 (vec{x_{i}} = big( x_{i, 1}, ~ x_{i, 2}, ~ ldots, ~x_{i, d} big)) 所对应的 (d) 个权重与 (w_{0})），以及 (|S| = n) 个 constraints，通过一个 constraint optimization program 将优化问题解出是可能的。

The Perceptron Algorithm

感知机算法如下：

Definition. (Margin of a Hyperplane)

一个数据集所属空间中的一个超平面的 margin 是距离超平面最近的数据点到超平面的距离。

Definition. (Margin of a Dataset)

一个数据集的 margin (记作 (gamma)) 是对于这个数据集而言，使用任意的权重向量 (weight vector) 分别点乘每一个数据点，其新数据集在新空间内所尽可能达到的最大 margin (of the hyperplane)。

• 换言之，margin of hyperplane 是一个 (min) 的概念，而 margin of dataset 是一个 (maxmin) 的概念。并且，对于 margin of dataset 的定义，假设初始 feature dataset 为 (mathcal {X} = left{vec{x_{1}}, vec{x_{2}}, ldots, vec{x_{n}} right})，对于每一个数据点 (vec{x}_{i})，点乘以一个任意的权重向量 (vec{w})，得到新的一组 feature dataset (mathcal{X}^{star} = left{ vec{w} cdot vec{x_{1}}, vec{w} cdot vec{x_{2}}, ldots, vec{w} cdot vec{x_{n}} right})，再配对以各自的 label 得到二维平面上的新数据集 (mathcal{X}^{star} times mathcal{Y} = left{ (vec{w} cdot vec{x_{1}}, y_{1}), (vec{w} cdot vec{x_{2}}, y_{2}), ldots, (vec{w} cdot vec{x_{n}}, y_{n}) right})。在这个二维空间内根据给定的 hyperplane （即一根直线），求出使得 margin of the dataset (mathcal{X}^{star} times mathcal{Y}) 最大的上述 (vec{w})。

Perceptron Algorithm Guarantee

Theorem. (Perceptron Mistake Bound)

假设存在一个 (vec{w}^{*}) （单位长度为 (1)），使 (text{margin} = gamma) 的 training sample 变得 linear separable。令 (R = maxlimits_{vec{x} in mathcal{X}} ||vec{x}||)，那么 perceptron algorithm 最多会犯 (T = big(frac{R}{gamma}big)^{2}) 次错误。

Proof.

证明的关键点在于说明：经过第 (t) 次遍历后得到的 (vec{w}^{(t)}) 和 (vec{w}^{*}) 相差多少？

假设 perceptron algorithm 在第 (t) 次遍历时犯了一个错误，那么：

上面最后一个不等式的推导，我后面会解释。简单来说，这是因为 data is separable by a margin (gamma)。

同时，我们有：

• 解释：

  上面最后一个不等式的推导意味着：(2 y (vec{w}^{(t-1)} cdot vec{x}) + ||y vec{x}||^{2} leq R^{2} = maxlimits_{x in mathcal{X}} || vec{x} ||^{2})。这是因为，perceptron algorithm 仅在分类错误的时候对权重向量 (vec{w}) 进行更新，由我们上述的假设，即第 (t) 次遍历的时候出现分类错误，这意味着：

  [y (vec{w}^{(t-1)} cdot vec{x})

  代表着 label (y) 与 (vec{w}^{(t-1)} cdot vec{x}) 异号。

  由于label (y) 为标量，则 (||y vec{x}||^{2} = y^{2} ||vec{x}||^{2})，且由于 (y in left{ -1, 1 right})，则：

  [||y vec{x}||^{2} = ||vec{x}||^{2} leq maxlimits_{vec{x} in mathcal{X}} ||vec{x}||^{2}
  ]

  自然成立。

  ---

  那么，由上我们证得：

  [vec{w}^{(t)} leq ||vec{w}^{(t-1)}||^{2} + R^{2}
  ]

  对于每次遍历 (1, 2, ldots, t)，由上式，有：

  [begin{cases}
  vec{w}^{(t)} cdot vec{w}^{*} geq vec{w}^{(t-1)} + gamma \
  \
  ||vec{w}^{(t)}||^{2} leq ||vec{w}^{(t-1)}||^{2} + R^{2}
  end{cases}
  ]

  因此，在 (T) 次遍历后：

  [begin{align*}
  T gamma & leq vec{w}^{T} cdot vec{w}^{*} \
  & leq ||vec{w}^{(T)}|| cdot ||vec{w}^{*}|| \
  & leq R sqrt{T}
  end{align*}
  ]

  ---

  • 解释：

    • 第一个不等式可以 recursively 得到，即：

      [begin{align*}
      vec{w}^{(T)} cdot vec{w}^{*} & geq vec{w}^{(T-1)} cdot vec{w}^{*} + gamma \
      & geq vec{w}^{(T-2)} cdot vec{w}^{*} + 2gamma \
      & geq vec{w}^{(T-3)} cdot vec{w}^{*} + 3gamma \
      & ; ; vdots quad text{recursively} \
      & geq T gamma

      end{align*}
      ]

    • 第二个不等式则是因为：

      [vec{w}^{(T)} cdot vec{w}^{*} = cos langle vec{w}^{(T)}, vec{w}^{*} rangle cdot ||vec{w}^{(T)} || cdot ||vec{w}^{*}||
      ]

      而 (cos langle vec{w}^{(T)}, vec{w}^{*} rangle in [-1, 1])。

    • 第三个不等式同样可以 recursively 得到，即：

      [begin{align*}
      & vec{w}^{(0)} = vec{0}, text{ recursively: } \
      & ||vec{w}^{(1)}||^{2} leq R^{2} \
      & ||vec{w}^{(2)}||^{2} leq ||vec{w}^{(1)}||^{2} + R^{2} leq 2 R^{2} \
      & vdots \
      & ||vec{w}^{(T)}||^{2} leq ||vec{w}^{(T-1)}||^{2} + R^{2} leq ||vec{w}^{(T-2)}||^{2} + 2R^{2} leq cdots leq T R^{2}
      end{align*}
      ]

  ---

  因此，我们得到：

  [T gamma leq R sqrt{T}
  ]

  即：

  [T leq Big( frac{R}{gamma} Big)^{2}
  ]

  Why we have: (y vec{x} cdot vec{w}^{*} geq gamma)?

  首先，(gamma) 为 sample dataset 的 margin，它的含义如上文所述，其代表对于任意可能的权重向量，能使经权重向量变换后的数据集中离超平面最近的数据点到超平面的这段 “最小距离” 最大的距离（比较拗口，注意理解）。即：

  [maxlimits_{vec{w}} big( minlimits_{vec{x} in mathcal{X}} D big)
  ]

  现在，由于假设了存在 (vec{w}^{*}) 使超平面将 sample dataset 线性区分，则超平面的解析式为：

  [y (vec{w}^{*} cdot vec{x}) = 0
  ]

  对于任意的数据点 (vec{x_{0}})，其到超平面的距离为：

  [begin{align*}
  frac{|y(vec{w}^{*} cdot vec{x_{0}})|}{sqrt{||vec{w}^{*}||^{2}}} & = |y(vec{w}^{*} cdot vec{x_{0}})| \
  & = y (vec{w}^{*} cdot vec{x_{0}})
  end{align*}
  ]

  其中第一个等式的成立是因为有假设： (||vec{w}^{*}||^{2} = 1)，第二个等式的成立同样因为假设：(y (vec{w}^{*} cdot vec{x_{0}}) geq 0)。

  然而，即使 (gamma) 代表的是 “最大的最小距离”，即 (maxlimits_{vec{w}} big( minlimits_{vec{x} in mathcal{X}} D big))，在给定的 (vec{w}) 下，(gamma) 所代表的依然是在这种选择 (vec{w}) 下的、对于所有 (vec{x} in mathcal{X}) 的最小距离，即一个 lower bound。

  那么给定 (vec{w}^{*}) 下，(gamma) 即为给定的 (vec{w}^{*}) 下的超平面的 margin，而非数据集的 margin，这意味着：

  [forall vec{x_{0}} in mathcal{X}: ~ y(vec{w}^{*} cdot vec{x_{0}}) = y vec{w}^{*} cdot vec{x_{0}} geq gamma
  ]