Jordan Lecture Note-1: Introduction

     Jordan Lecture Note-1： Introduction

     第一部分要整理的是Jordan的讲义，这份讲义是我刚进实验室时我们老师给我的第一个任务，要求我把讲义上的知识扩充出去，然后每周都要讲给他听。如果有需要这份讲义的话，请留言，我会用邮件发给你。

    首先，我来说说机器学习这个东西。刚进实验室，我根本连什么是机器学习都不知道，听到这个名词后的第一反应是机器人，心想估计是搞硬件的。后来才发现其实机器学习更偏向于后面两个字，也就是“学习”。打个不恰当的比方吧，人类在婴儿时期，还无法对世上的东西进行识别，比如小汽车跟货车有什么区别？这时，婴儿的父母就会指着小汽车对他说，这是个小汽车，它有四个小轮子，四个门等等；指着货车对他说，这是货车，它有六个大轮子，两个门等等。当婴儿接受到这些信息后，就会在脑中对汽车和货车的一些属性特征进行抽象，从而能够得出一个能够识别汽车和货车的模型。其实机器学习也类似吧，把人类抽象出的一些特征信息作为机器学习的“资料”，术语称之为训练集，有了这些“资料”后，我们在给定一个学习算法，这个学习算法针对这个“资料”就能学习出一个模型，而这个模型就是机器最后用来决策的根据。

     然后，我在说说机器学习中最简单的二分类问题。 所谓二分类问题就是让机器来识别出 A 和 B。假设训练集 $\{x_i,y_i\}_{i=1}^N$ ，其中 $x_i\in\mathbb{R}^d$ 成为输入特征，d为特征的维度， $y\in\{0,1\}$ 称为 label。每一个输入数据 $x_i$ 都对应着一个输出的label $y_i$ ，而我们的目标是通过给定的这个训练集，学习出一个模型，这个模型能够尽可能正确的判断出这个输入的数据是属于哪一个label。这类问题有很多实际应用，比如人脸识别，垃圾邮件过滤等等。很显然，更一般的多分类问题指的是label的数量大于2.

    接下来，我简单的介绍四种二分类的方法，分类是1）感知器（Perceptron）2）逻辑斯回归（Logistic Regression）3）线性判别分析（Linear Discriminant Analysis）4）支撑向量机（Support Vector Machine）。

 一 Perceptron

    1）感知器算法

 step 1：

       初始化 $w=w_0$

 step 2：

     for $i=1,2, ... ,n$

           计算 $w_jx_i$ ，若 $w_jx_i>0$ ，则set $y=1$ ，否则 $y=0$

       更新权重 $w=w + \lambda(y_i-y)x_i$ ，

     end for

step 3:

     若step 2中的权重都没有被更新的话说明算法已经收敛，返回权重 $w$ ；否则转step 2.

step 4: 

     最终的判断函数为 $f(x)=w^Tx$ ，若 $f(x)>0$ ，则 $y$ 为1；否则 $y$ 为0.

 2） 感知器算法的收敛定理

   如果数据是线性可分的话（也就是存在的一个线性函数 $f(x)$ 能使所有的 $x$ 所对应的label都能通过上述决策准则得到），那么算法就一定收敛，既存在有限次数能找到权重 $w$ .

 证明：由于数据是线性可分的，那么一定存在一个权向量 $w^*$ 能够正确的决策出所有的数据label，既对于label 1有 $w^Tx>0$ ，对于label 2 有 $w^Tx<0$ 。对 $w^*$ 进行归一化使得 $\|w^*\|=1$ ，将属于label 2 的数据 $x_i$ 做乘-1处理,得到新的数据 $x_k$ 。于是必存在一个正数 $d$ ，使对所有的样本有 $w^*x_k\geq d$ 。任意权向量与最优权向量 $w^*$ 的余弦角 $\mathop{cos}\alpha=\frac{w^*\cdot w}{\|w^*\|\|w\|}$ 。

    设感知器在训练过程中的判错模式依次为 $x_{i_1},x_{i_2}, ..., x_{i_t}, ...$ ，则每一个判错模式都对应的对权重的更新：

\[

w_{k+1} = w_k + \lambda x_{i_k}

\]

其中 $\lambda$ 为学习系数。由 $w^*\cdot w_{k+1}=w^*[w_k+\lambda x_{i_k}]=w^*\cdot w_k+\lambda w^*\cdot x_{i_k}\geq w^*\cdot w_k+\lambda d$ ，迭代计算下去得：

 \[

w^*\cdot w_{k+1} \geq w^*\cdot w_0 + k\lambda d

\]

 选择 $w_0\in\{x_k\}$ ，必满足 $w^*\cdot w_0>0$ ，所以 $w^*\cdot w_k\geq k\lambda d$ 。

     在 $w_k$ 为收敛到 $w_*$ 时，对于判错模式必有 $w_k\cdot x_{i_k} < 0$ ，所以

\begin{align*}

 \|w_{k+1}\|^2 &= [w_k+\lambda x_{i_k}]\cdot[w_k+\lambda x_{i_k}] \\

                        &= \|w_k\|^2 + 2\lambda w_k\cdot x_{i_k} + \lambda^2\|x_{i_k}\|^2 \\

                        &\leq \|w_k\|^2 + \lambda^2

\end{align*}

 迭代计算可得： $\|w_k\|^2\leq \|w_0\|^2 + k\lambda^2 = C + k \lambda^2$ ，其中 $C$ 为常数。

 当 $w_k=w^*$ 时， $\mathop{cos}\alpha=1$ ，故

\[

 1=\frac{w^*\cdot w_k}{\|w^*\|\|w_k\|}\geq\frac{k\lambda d}{\sqrt{C+k\lambda^2}}

\]

  $\Longrightarrow$

\[

 k\leq\frac{\lambda^2+\sqrt{\lambda^2+4\lambda^2 d^2}}{2\lambda^2 d^2}.

\]

Jordan Lecture Note-1: Introduction

原文：http://www.cnblogs.com/boostable/p/lec_introduction.html