【AI】机器学习—

文章目录

- 4.1 感知机基本概念
- 4.2 策略
- - 4.2.1 数据集的线性可分性
  - 4.2.2 学习策略
  - - 目标
    - 损失函数的构造
    - - 关于距离的解释
- 4.3 算法
- - 4.3.1 原始形式
  - - 损失函数的梯度下降法
  - 4.3.2 PLA例题
  - 4.3.3 算法收敛性
- 4.4 PLA对偶形式
- - 4.4.1 原始PLA分析
  - 4.4.2 PLA对偶形式
  - 4.4.3 优点

4.1 感知机基本概念

解决二分类问题，属于 线性分类模型——判别模型

目标：求出将训练数据进行线性划分的分离超平面

基本思想：导入五分类的损失函数，利用梯度下降法对损失i函数极小化，求得感知机模型

输入： $x\in \mathcal{X}\subseteq R^n$ 表示实例的特征向量， $y\in \mathcal{Y}=\{+1, -1\}$

输出： $\hat{\omega},\hat{b}$

模型——决策函数
$f(x)=sign(\omega^Tx+b)=\begin{cases} +1&,\omega^Tx> 0\\ -1&,\omega^Tx<0 \end{cases}$
假设空间：定义在特征空间中的所有线性分类模型
$\{f\vert f(x)=\omega^Tx+b\}$
几何理解： $\omega^Tx+b=0$ 在空间中为一个超平面 $S$ ， $\omega$ 为法向量， $b$ 为截距

在这里插入图片描述

上图中超平面 $S:\omega_1x^{(1)}+\omega_2x^{(2)}+b=0$ ，这个超平面将特征空间分为 $+ 1, - 1$ 类

4.2 策略

损失函数的定义，并将 $J(\omega)$ 最小化

4.2.1 数据集的线性可分性

对于数据集
$D=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}\\ x_i\in \mathcal{X}\subseteq R^n,y_i\in\mathcal{Y}=\{+1,-1\},i=1,2,\cdots,N$
若存在某个超平面 $S$ ： $\omega^Tx+b=0$ ，将数据正负两类完全划分到超平面两侧

对于正例： $y_i=+1$ ，有 $\omega^Tx+b>0$
对于负例： $y_i=-1$ ，有 $\omega^Tx+b<0$

4.2.2 学习策略

目标

假设数据集D线性可分，找到将数据集D正负两例完全正确分开的超平面S，即确定参数 $\hat{\omega},\hat{b}$

损失函数的构造

可选择

误分类点的总数，但不关于 $\omega,b$ 可导，是离散的
误分类点到超平面 $S$ 的距离和

点 $x_i$ 到平面 $S$ 的总距离
$\frac{\omega^Tx_i+b}{\Vert \omega\Vert_2}$
对于误分类点有 $y_i\cdot(\omega^Tx_i+b)<0\iff -y_i\cdot(\omega^Tx_i+b)>0$

对于误分类点，到超平面的几何距离为
$-\frac{1}{\Vert \omega\Vert_2}y_i\cdot(\omega^Tx_i+b)$
若所有误分类点集合为 $M$ ，则误分类点到 $S$ 的距离和为
$-\frac{1}{\Vert \omega\Vert_2}\sum\limits_{x_i\in M}y_i\cdot(\omega^Tx_i+b)$
故将感知机（损失函数）定义为经验风险函数
$R_{emp}(f)=L(\omega,b)=-\sum\limits_{x_i\in M}y_i\cdot(\omega^Tx_i+b)$
策略为 在假设空间中选取使损失函数 $L(\omega,b)$ 最小的模型参数 $\omega,b$

损失函数非负
误分类点数量越少越好
误分类点离超平面越近越好
$L(\omega,b)$ 是连续可导的

关于距离的解释

$-\frac{1}{\Vert \omega\Vert_2}y_i\cdot(\omega^Tx_i+b)$ 为几何距离

$-y_i\cdot(\omega^Tx_i+b)$ 为函数距离

几何距离的系数 $\frac{1}{\Vert \omega\Vert_2}$ 可以抵消系数同时放大的影响，如 $a X + bY + c = 0$ 与 $2 a X + 2 bY + 2 c = 0$

但会增加梯度下降法计算的复杂度

PLA的目标是使误分类点个数最小， $\frac{1}{\Vert \omega\Vert_2}$ 对分类结果无影响

选取不同的初始 $\omega,b$ ，最终会迭代出不同的超平面

在这里插入图片描述

4.3 算法

用随机梯度下降法，求解损失函数最优化问题

4.3.1 原始形式

输入：训练数据集
$D=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}，\\ x_i\in \mathcal{X}\subseteq R^n,y_i\in \mathcal{Y}=\{+1,-1\},i=1,2,\cdots,N$
输出： $\hat{\omega},\hat{b}$

模型
$f(x)=sign(\omega^Tx+b)=\begin{cases} +1&,\omega^Tx+b>0\\ -1&,\omega^Tx+b<0\\ \end{cases}$
策略
$arg\min\limits_{\omega,b}L(\omega,b)=-\sum\limits_{x_i\in M}y_i\cdot(\omega^Tx_i+b)$
步骤

选取随机的 $\omega_0,b_0$
在训练集中选数据 $x_i,y_i)$ ，将误分类点作为训练数据，即满足 $\omega^Tx_i+b<0$ 的条件的点
$\omega^{[t+1]}\leftarrow\omega^{[t]}-\eta\frac{\partial L}{\partial \omega}=\omega^{[t]}+\eta y_ix_i\\ b^{[t+1]}\leftarrow b^{[t]}-\eta\frac{\partial L}{\partial b}=b^{[t]}+\eta y_i$
转至 $2$ 步，直至 $D$ 中无误分类点

损失函数的梯度下降法

$\begin{cases} \bigtriangledown_{\omega}L(\omega,b)=-\sum\limits_{x_i\in M}y_ix_i\\ \bigtriangledown_{b}L(\omega,b)=-\sum\limits_{x_i\in M}y_i\\ \end{cases}$

前提是误分类点集合是固定的 ，才可进行梯度下降法最优化
$\begin{cases} \omega\leftarrow \omega-\eta\bigtriangledown_{\omega}L\\ b\leftarrow b-\eta\bigtriangledown_{b}L \end{cases}$
这种做法：

计算量大
且调整参数 $\omega,b$ 后，误分类点集可能会发生变化，故用随机梯度下降法

直观理解

当一个样本点被误分类时，调整 $\omega,b$ 的值，使超平面 $S$ 向该误分类点的一侧移动，减少该误分类点与 $S$ 的距离，直至超平面越过此点（分类正确）

4.3.2 PLA例题

$x_1=(3,3)^T,y_1=+1\\ x_2=(4,3)^T,y_2=+1\\ x_3=(1,1)^T,y_3=-1\\$

模型：
$f(x)=sign(\omega^Tx+b)=\begin{cases} +1&,\omega^Tx+b>0\\ -1&,\omega^Tx+b<0 \end{cases}\\ \omega=\left( \begin{aligned} \omega_1\\ \omega_2 \end{aligned} \right)$
PLA策略为
$\min\limits_{\omega,b}L(\omega,b)=-\sum\limits_{x_i\in M}y_i(\omega^T\cdot x+b)$
算法：

取初值， $\omega_0=\left(\begin{aligned}0\\0\end{aligned}\right)$ ， $b_0=0$ ， $\eta=1$
对 $x_1=(3,3)^T$ ，有 $y_1(\omega_1^{[0]}x_1^{(1)}+\omega_2^{[0]}x_1^{(2)}+b^{[0]})=0$

未分类正确，故更新
$\begin{cases} \omega^{[1]}\leftarrow\omega^{[0]}-\eta\frac{\partial L}{\partial \omega}=\omega^{[0]}+\eta y_ix_i= \left( \begin{aligned} 0\\0 \end{aligned} \right)+\left( \begin{aligned} 3\\3 \end{aligned} \right)=\left( \begin{aligned} 3\\3 \end{aligned} \right)\\ b^{[1]}\leftarrow b^{[0]}-\eta\frac{\partial L}{\partial b}=b^{[0]}+\eta y_i=0+1\cdot 1=1 \end{cases}$
故有线性模型
$\omega_1^{T}\cdot x+b_1=3x^{(1)}+3x^{(2)}+1$
对 $x_2=(4,3)^T,(\omega_1^{[1]}x_2+\omega_2^{[1]}x_2+b^{[1]})y_2>0$ ，正确分类

$x_3=(1,1)^T,(\omega_1^{[1]}x_3+\omega_2^{[1]}x_3+b^{[1]})y_3<0$ ，误分类。用 $x_3,y_3)$ 更新模型参数
$\begin{cases} \omega^{[2]}\leftarrow\omega^{[1]}-\eta\frac{\partial L}{\partial \omega}=\omega^{[1]}+\eta y_3x_3= \left( \begin{aligned} 3\\3 \end{aligned} \right)+(-1)\left( \begin{aligned} 1\\1 \end{aligned} \right)=\left( \begin{aligned} 2\\2 \end{aligned} \right)\\ b^{[1]}\leftarrow b^{[0]}-\eta\frac{\partial L}{\partial b}=b^{[0]}+\eta y_3=1+1\cdot (-1)=0 \end{cases}$
有线性模型
$\omega^{[2]}_1x_1+\omega^{[2]}_2x_2=0\iff 2x_1+2x_2=0\iff x_1+x_2=0$
对 $x_1,y_1),(x_2,y_2),(x_3,y_3)$ 代入线性模型，反复迭代

直至无误分类样本点，有
$\omega^{[7]}=\left( \begin{aligned} 1\\1 \end{aligned} \right),b^{[7]}=-3$
超平面为 $x^{(1)}+x^{(2)}-3=0$

4.3.3 算法收敛性

对于线性可分的训练数据集，经过有限次迭代(PLA可以在有限步终止) ，可以得到一个将训练数据集完全正确划分的超平面 $S$

定理

训练集 $D=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$ ，对于二分类模型， $x_i\in \mathcal{X}\subseteq R^n$ ， $y_i\in \mathcal{Y}=\{+1,-1\}$ $,i=1,2,\cdots,N$

一定存在 $\Vert \hat{\omega}_*\Vert=1$ 的超平面 $\hat{\omega}_*x^T=0$ ，将数据完全正确划分，且存在 $\gamma >0$ ，使
$y_i(\hat{\omega}_*x^T)\ge \gamma\\ \hat{\omega}=\left(\begin{aligned} \omega_*\\ b_* \end{aligned} \right),x=\left( \begin{aligned} x\\1 \end{aligned} \right)$
证：由于线性可分，则可找到一个超平面 $S:\hat{\omega}_*x^T=0$ ，使所有数据 $y_i(\hat{\omega}_*x^T)>0$ 分类正确

可取 $\gamma=\min\limits_{i}\{y_i(\hat{\omega}_*x^T)\}$ ，距离超平面最近的点
令 $R=\max\limits_{1\le i\le N}\Vert x_i\Vert_2$ ，样本特征值最大的二范数，则PLA在训练数据集上误分类次数 $k$ 满足 $K\le \left(\frac{R}{\gamma}\right)^2$

即离超平面越近的点越难分

感知机存在许多解，依赖于初值的选择

即误分类点的选择次序会影响最终的结果

4.4 PLA对偶形式

4.4.1 原始PLA分析

在原始 PLA 算法中， $\omega_0,b_0=0$ ， $L(\omega,b)=-\sum\limits_{x_i\in M}y_i(\omega^T\cdot x+b)$ ，采用随机梯度下降算法，取一个误分类点 $x_i,y_i)$ 作为学习数据， $\eta\in(0,1]$ 为学习率
$\begin{cases} \omega^{[t+1]}\leftarrow\omega^{[t]}-\eta\frac{\partial L}{\partial \omega}=\omega^{[t]}+\eta y_ix_i\\ b^{[t+1]}\leftarrow b^{[t]}-\eta\frac{\partial L}{\partial b}=b^{[t]}+\eta y_i \end{cases}$
可见

$\omega$ 更新至于误分类点有关

某个点使用次数越多，距超平面越近，越难正确分类
假设 $x_i,y_i)$ 被误分类 $n_i$ 次，则 $\omega$ 在 $x_i,y_i)$ 上的累积量为
$\begin{cases} \omega_i\leftarrow n_i\eta y_ix_i=\alpha_iy_ix_i\\ b_i\leftarrow n_i\eta y_i=\alpha_iy_i \end{cases}$
且对于正确分类的点 $n_i=0$ ，故原始PLA参数可表示为
$\begin{cases} \omega\leftarrow \sum\limits_{j=1}^Nn_j\eta y_j\cdot x_j\\ b\leftarrow \sum\limits_{j=1}^N n_j\eta y_j \end{cases}$

4.4.2 PLA对偶形式

输入： $D=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\},x_i\in \mathcal{X}\subseteq R^n,y_i\in \mathcal{Y}=\{+1,-1\},i=1,2,\cdots,N$

$\eta\in (0,1]$

模型
$\begin{aligned} f(x)&=sign[(\sum\limits_{j=1}^Nn_j\eta y_j\cdot x_j)^T\cdot x+\sum\limits_{j=1}^N n_j\eta y_j]\\ &=sign[\sum\limits_{j=1}^N\alpha_j y_j(x_j\cdot x)^T+b] \end{aligned}$
输出： $\alpha,b$ $\alpha=\left(\begin{aligned}\alpha_1\\\alpha_2\\\vdots\\\alpha_N\end{aligned}\right)$ ， $\alpha_i=n_i\eta$ ， $n_i$ 为 $x_i,y_i)$ 被误分类的次数

步骤

$\forall n_i=0$ ，即 $\alpha=0,b=0$
选取 $x_i,y_i)$ ，若 $y_i[\sum\limits_{j=1}^Nn_j\eta y_j(x_j^T\cdot x)+\sum\limits_{j=1}^N n_j\eta y_j]\le 0$ ，则令
$n^{[t+1]}\leftarrow n^{[t]}+1\\ \alpha^{[t+1]}\leftarrow \alpha^{[t]}+\eta\\ b^{[t+1]}\leftarrow b^{[t]}+\eta y_i$
转至 $2.$ 直至没有误分类点

由于样本点只以内积形式出现，可计算 Gram矩阵
$G=[x_i\cdot x_j]_{N\times N}=\left[\begin{matrix} (x_1,x_1)&(x_1,x_2)&\cdots&(x_1,x_N)\\ (x_2,x_1)&(x_2,x_2)&\cdots&(x_2,x_N)\\ \vdots&\vdots&\ddots&\vdots\\ (x_N,x_1)&(x_N,x_2)&\cdots&(x_N,x_N) \end{matrix} \right]$