MIT+ML02:LinearClassifiersandPerceptrons

阅读数: 6次 2020-08-04

Outline

Linear model for classification
Perceptrons:感知器是人们成功使用的最简单的神经网络模型:

单个神经元的神经网络

notation

Data:x x $\in$ X

Label:y

如何理解supervised learning 呢？

我们有一堆(data，label)，然后根据这个(data，label)我们选择合适的f，然后我们又 $x_{new}$ ，我们响应的获得 $y_{predict}$ ，这就是监督学习

$H$ :hypothesis class：the set from which we want to draw a classifier（f)

model doesn’t go fully blind,即CV中卷积比较多，这个就相当于hypothesis class了

二分问题encode

可以使用+1/-1

exercise inductive bias.

Learning:Perceptron–find the hyperplane

超平面的应用：
- halfspaces
- logistic regression classifier
These are instances of a linear hypothesis class composed with a suitable scalar function

这里scalar function是什么呢？是Sgn/sigmoid

使用超平面概念的linear二分类classifer

超平面相关的数学基础：

定义： $\theta/w(weight)$ [vector]， $\theta_0$ [offset/bias]

这个超平面，由所有满足 $\theta^T x+\theta_0$ =0的向量 $x$ 组成。

$x=[x_1,x_2,…,x_d]$ , $\theta_1x_1+\theta_2x_2+\theta_3x_3+…+\theta_dx_d+\theta_0=0$

这里，向量 $\theta$ 是该超平面的法向量，也即normal vector.
判定给定一个向量 $v=[v_1,v_2,…,v_d]$ 是否垂直于超平面：即判断该向量是否与该超平面的法向量平行或共线。
求向量在超平面上的投影：

设投影是 $v_p$ ,则
$v_p·\theta+\theta_0=0(投影属于该超平面)\ v-v_p=v_{perpendicular}=\lambda \theta(与法向量共线)$
如果向量 $x_1$ , $x_2$ 都属于该超平面，那么二者的差 $x_1-x_2$ 与法向量 $\theta$ 点乘为0，即与该法向量垂直
求向量(point)到超平面的signed distance

规定：

向量x与 $\theta$ 同方向，则sign=+1;

向量x与 $\theta$ 反方向，则sign=-1;

signed distance= $\frac{｜\theta x+\theta_0｜}{||\theta||}$

Linear hypothesis class

这里，我们把超平面分类器的 $\theta$ 看成我们在ML中普适性的weight $w$

Decision boundary

$\theta·x+\theta_0=0$

ML：perceptron:自动学习如何寻找correct差平面的机器学习模型

核心是错了就correct，不断调参。

How to adjust the hyperplane?

结合二图可以很好的理解perceptron Algorithm

超平面与超平面的linear separability—Proof of convergence

讨论perceptron正确学习所有训练数据所花费的步骤：

Assume: $||x^{(i)}||\le R,1\le i \le n$ ，Augment data as (x,1) to absorb the $w_0$ term，即不考虑offset?即 $w^Tx/\theta^Tx$ 表示了hyperplane.同时，假设存在单位向量 $u$ ,使得 $y_{true}(u^Tx^{(i)})\ge \gamma$ ,满足对于所有训练样本都同时满足该条件。

Observe: linear separability assumption gives us such uand $\gamma$

是linear separable 的性质保证我们可以找到u和 $\gamma$

我们将证明，在这种情况下，我们的perceptron模型只需要 $(R/\gamma)^2$ 步来正确学习所有训练数据。这里 $\gamma$ 表示训练样本vector到达超平面的signed distance.

Convergence i.e. it is gonna be bounded

Convergence theorem:

无论训练的次序如何，最终会有convergence的这一天，且在 $(R/\gamma)^2$ 步以内
the bound is independent of dimensionality of the feature space.

What if the data is not separable?

this method never stop.

converge to some suboptimal.

More than one “correct hyperplane”–zero error Problem.

Exercise:

The order in which the data and the labels are presented impacts the number of updates it takes for the percptron algorithm to converge.

How we can do to make the perceptron go through every training data point and make an update?(in other words: maximize the error the perceptron makes?)

超平面的另一种形象理解

对Feature vector赋予不同权重的线性组合。

Chi xinning