应用市场华为_有创意的广告图片及赏析_软文营销写作技巧有哪些?_下载百度极速版

Ch5 线性判别函数

引言：生成模型 vs判别模型

生成模型 vs 判别模型

在分类问题中，生成模型和判别模型是两种不同的建模方法：

生成模型	判别模型
直接建模类条件概率或联合分布	直接建模后验概率 $p(y|x)$ 或决策边界
通过贝叶斯公式计算后验概率 $p(y|x)=\frac{p(x,|y)p(y)}{p(x)}$	不需要假设数据的分布形式，直接关注分类任务
示例：朴素贝叶斯、隐马尔可夫模型（HMM）	示例：支持向量机、线性判别分析、神经网络
适用于需要生成数据的场景（例如语音识别、自然语言处理）	适合直接分类任务，通常分类性能较好

判别模型分类

判别模型根据复杂性和数据分布特点，可以分为以下几类：

线性判别函数	广义线性判别函数	非线性模型	非参数模型
假设数据是线性可分的，构造一个超平面来划分不同类别。	将数据映射到高维空间，使非线性问题变成线性问题。	不依赖数据的线性假设，适合处理复杂分布的数据。	不假设数据的分布形式。
简单、高效，适合高维空间。	使用核函数（kernel function）来处理非线性分布。	学习能力强，但计算复杂度较高。	分类直接依赖于训练样本，适合小样本场景。
感知器、支持向量机、Fisher线性判别函数	核学习机	神经网络、决策树	K近邻分类、高斯过程

假设有n个d维空间中的样本，每个样本的类别标签已知，且一共有c个不同的类别。

• 学习问题：假定判别函数的形式已知，采用样本来估计判别函数的参数。
• 推理、预测问题：对于给定的新样本$x\in {\mathbb{R}}^d$，用判别函数判定$x$属于${\omega }_1,{\omega }_2,\dots ,{\omega }_c$中的哪个类别。

	c>2(one-vs-all)	c=2
判别函数	每个类别对于判别函数$g_i(x),i=1,2,\dots ,c$, $g_i(x)$用于区分第 ${\omega }_i$ 类和其他$c-1$个类，其数值表示 $x$ 属于第 ${\omega }_i$ 类的概率、置信度、打分等.	$g(x)=g_1(x)-g_2(x)$
决策准则	$g_i(x)>g_j(x),\forall j\ne i$: $x$被分为${\omega }_i$类	$g(x)>0$: 分为第一类${\omega }_1$

线性判别函数与决策面

线性判别函数

线性判别函数定义为：
$$g(x)=\sum _{i=1}^d{w}_i{x}_i+w_0=w^{T}x+w_0$$

• $w$：权重向量，决定分类超平面的方向。
• $w_0$：偏移量（阈值），决定超平面的位置。

两类情况下的决策

决策依据判别函数 $g(x)$ 的符号：
$$\{\begin{array}{ll}x\in {\omega }_1,& \text{if }g(x)>0\\ x\in {\omega }_2,& \text{if }g(x)<0\\ \text{uncertain},& \text{if }g(x)=0\end{array}$$
两类问题中的决策面:

• $H$：$g(x)=0$，用于将特征空间分为两类区域：

• $R_1$：$g(x)>0$

• $R_2$：$g(x)<0$

超平面$H$的法向量为 $w$，垂直于决策面。

• 对于位于 $H$ 内的任意向量，其法向量满足： $w^T(x_1-x_2)=g(x_1)-g(x_2)=0$

• 对于任意样本/向量$x$，将其向决策面内投影，并写成两个向量之和：
  $$x=x_p+r\frac{w}{\Vert w\Vert }$$
  $x_p$是$x$在超平面$H$上的投影，$r$是点$x$到超平面$H$的代数距离。若$x\in R_1,r>0$.

多类问题下决策

在多类分类问题中，通常使用多个二分类器来解决问题。常见策略有：

一对多（One-vs-All）	一对一（One-vs-One）	多对多
每个类别与其余类别分别构造一个二分类器，共需构造 c 个二分类器。	每两个类别配对构造一个二分类器，共需构造 $\frac{c(c-1)}{2}$ 个二分类器。	—
预测时：若只有一个分类器的预测为正，其对应类别即为预测结果；若多个分类器的预测为正，则需要比较判别函数值。	预测时, 对测试样本使用投票法，预测得票最多的类别。	使用纠错编码（Error Correcting Output Codes, ECOC），实现层次化分类。

多类情形-线性机器

因为不使用判别函数的函数值、仅仅使用决策面进行分类，one-vs-all\one-vs-one都有可能存在不确定区域。

• 考虑one - vs - all情形，构建$c$个两类线性分类器：
  $$g_i(x)=W_i^{T}x+w_{i0},i=1,2,\cdots ,c$$

• 对样本$x$，可以采用如下决策规则（最大判别函数决策）：

  • 对$\forall j\ne i$，如果$g_i(x)>g_j(x)$，$x$则被分为${\omega }_i$类；否则不决策

  • $$g_i(x)=\underset{j=1,2,\cdots ,c}{\max }{g}_j(x)\Rightarrow x\in {\omega }_i$$

  • 线性机器将样本空间分为$c$个可以决策的区域$R_1,\cdots ,R_c$。

线性决策面优缺点

• 所有的决策区域都是凸的——便于分析
• 所有的决策区域都是单连通的——便于分析

• 凸决策区域：限制分类器的灵活性和精度
• 单连通区域：不利于复杂分布数据的分类（比如：分离的多模式分布）

广义线性判别函数

将原来的数据点 x通过一种适当的非线性映射将其映射为新的数据点 y, 从而在新的特征空间内应用线性判别函数方法。

例：二次判别函数

二次判别函数形式：
$$g(x)=w_0+\sum _{i=1}^d{w}_i{x}_i+\sum _{i=1}^d\sum _{j=1}^d{w}_{ij}{x}_i{x}_j$$
其中共有$\hat{d}=\frac{(d+1)(d+2)}{2}$个系数待估计（$w_{ij}=w_{ji}$），且$g(x)=0$为决策面，它是一个二次超曲面。

定义如下非线性变换$y(x)$，把$x$从$d$维变到$\hat{d}$维：
$$\begin{gathered} y_1(x)=1 \\ {y}_2(x)=x_1 \\ {y}_3(x)=x_2 \\ \dots \\ {y}_{d+1}(x)=x_d \\ {y}_{d+2}(x)=x_1^2 \\ {y}_{d+3}(x)=x_1{x}_2 \\ \dots \\ {y}_{\frac{(d+1)(d+2)}{2}}(x)=x_d^2 \end{gathered}$$
则有：
$$\begin{array}{rl}g(x)& =w_0+\sum _{i=1}^d{w}_i{x}_i+\sum _{i=1}^d\sum _{j=1}^d{w}_{ij}{x}_i{x}_j\\ & =\sum _{i=1}^{\hat{d}}{a}_i{y}_i(x)\end{array}$$
$y_i(x)$是变换函数、令$a=[a_1,a_2,\cdots ,a_{\hat{d}}{]}^T$，$y=[y_1,y_2,\cdots ,y_{\hat{d}}{]}^T$，可简写为：
$$g(x)=a^{T}y(x)$$
其中：

• $a$为广义权重向量，$y$是经由$x$所变成的新数据点。
• 广义判别函数$g(x)$对$x$而言是非线性的，对$y$是线性的。
• $g(x)$对$y$是齐次的，意味着决策面通过新空间的坐标原点。且任意点$y$到决策面的代数距离为$\frac{a^{T}y}{\Vert a\Vert }$。
• 当新空间的维数足够高时，$g(x)$可以逼近任意判别函数。
• 但是，新空间的维数远远高于原始空间的维数$d$时，会造成维数灾难问题。

例1: 1-D判别函数

设有一维样本空间$X$，我们期望如果$x<-1$或者$x>0.5$，则$x$属于${\omega }_1$类；如果$-1<x<0.5$，则属于${\omega }_2$类，请设计一个判别函数$g(x)$。

判别函数：
$$\begin{array}{rl}g(x)& =(x-0.5)(x+1)\\ & =-0.5+0.5x+x^2\\ & =a_1+a_{2}x+a_3{x}^2\end{array}$$
决策规则：
$$\begin{gathered} g(x)>0,x\in {\omega }_1 \\ g(x)<0,x\in {\omega }_2 \end{gathered}$$
映射关系：
$$y=\left(\begin{array}{c}1\\ x\\ x^2\end{array}\right):=\left(\begin{array}{c}{y}_1\\ y_2\\ y_3\end{array}\right)$$

感知准则函数

概念

线性可分性：来自两个类别的n个样本$y_1,y_2,\dots ,y_n$(齐次增广表示)。存在一个权向量$a$，对所有$y\in {\omega }_1$，均有$a^{T}y>0$;对所有$y\in {\omega }_2$，均有$a^{T}y<0$。

齐次增广->规范化增广

样本规范化：如果样本集是线性可分的，那么将属于${\omega }_2$的所有样本由$y$变成$-y$，对所有$n$样本，将得到$a^{T}y>0$。这样训练中就不需要考虑原来的样本类别。

规范化增广样本：1.将所有样本写成齐次增广形式；2.属于${\omega }_2$的所有样本由$y$变成$-y$

解向量与解区

解向量：线性可分的情况下，满足$a^T{y}_i>0,i=1,2,\dots ,n$的权向量$a$.

解向量 $a$ 是我们需要找到的“分类方向”，它保证所有样本点都在它的正确一侧。

**解区：**权向量$a$属于权空间中的一点，每个样本$y_i$对$a$的位置均起到限制作用($a^T{y}_i>0$)

• 任何一个样本点$y_i$均可以确定一个超平面$H_i:a^T{y}_i=0$($y_i$是法向量，所有与$y_i$垂直的属于$H_i$，且$y_i$决定了超平面的方向。)
• 如果解向量存在，那必在每个超平面的正侧($a^T{y}_i>0$); $n$个样本将产生$n$个超平面。每个超平面将空间一分为二。解向量存在于所有超平面正面的交集区域，此区域内的任意向量都是解向量。

**限制解区：**解向量存在的话，通常不唯一。根据经验越靠近区域中间的解向量，越能对新的样本正确分类，所以引入附加条件来限制解空间。

• way1: 寻找单位长度的解向量$a$，最大化样本到分界面的最小距离。

• way2: $\forall i$, 寻找满足$a^T{y}_i\ge b>0$的最小长度的解向量$a$, b:margin.

  

感知准则函数

现在考虑构造解线性不等式$a^T{y}_i>0$的准则函数问题。令$J(a;y_1,\dots ,y_n)$维被$a$错分的样本数。但这个函数是分段常数函数，对梯度搜索不友好。因此考虑感知器准则函数：
$$J_p(a)=\sum _{y\in \mathcal{Y}}(-a^{T}y)$$
$\mathcal{Y}$是错分样本集合。

当$y_i$被错分：$a^T{y}_i<0\Rightarrow -a^T{y}_i>0$，使$J_p(a)\ge 0$.

在可分情况下，当且仅当$\mathcal{Y}$是空集时$J_p(a)$将=0，此时不存在错分样本。

目标：${\min }_a{J}_p(a)$

梯度下降更新：$a_{k+1}$是当前迭代的结果，$a_k$是前一次迭代的结果，${\mathcal{Y}}_k$是被$a_k$ 错分的样本集合 ，${\eta }_k$为步长因子（更新动力因子，学习率）。
$$\begin{gathered} \frac{\partial J_p(a)}{\partial a}=-\sum _{y\in \mathcal{Y}}y \\ {a}_{k+1}=a_k-{\eta }_k\frac{\partial J_p(a)}{\partial a}{|}_{a=a_k}=a_k+{\eta }_k\sum _{y\in {\mathcal{Y}}_k}y \end{gathered}$$

算法收敛性

以固定增量单样本修正方法为例来说明算法的收敛性：

对于权向量 $a_k$，如果错分某样本，则将得到一次修正。由于在分错样本时 $a_k$才得到修正，不妨假定只考虑由错分样本组成的序列。即每次都只需利用一个分错样本来更正权向量。

记错分样本序列为 $y_1,y_2,\dots ,y_k,\dots$。考虑此情形的算法收敛性问题。

**收敛性定理：**在样本线性可分的情形下，固定增量单样本权向量修正方法收敛，并可得到一个可行解。

证明思路：设$a$是一个解向量，只需证明$\Vert a_{k+1}-a\Vert <\Vert a_k-a\Vert -C$即可。

• 算法每次迭代都会使权向量到解向量的距离减少1个常数C
• 假设$dst=\Vert a_1-a\Vert$,则dst在经过C次迭代后(计算了足够长的步数)，算法收敛。

感觉证明不考，因此略。

松驰方法

学习准则

在感知函数准则中，目标函数中采用了$-a^{T}y$ 的形式。实际上有很多其它准则也可以用于感知函数的学习。

线性准则	平方准则	松驰准则
$J_p(a)={\sum }_{y\in \mathcal{Y}}(-a^{T}y)$	$J_q(a)={\sum }_{y\in \mathcal{Y}}(a^{T}y{)}^2$	$J_r(a)=\frac{1}{2}{\sum }_{y\in \mathcal{Y}}(a^{T}y-b{)}^2/|y{|}^2$
$\mathcal{Y}$为错分样本集合	$\mathcal{Y}$为错分样本集合	$\mathcal{Y}$是$a^{T}y\le b$的样本集合
分段线性，梯度不连续	梯度连续，但目标函数过于平滑，收敛速度很慢。此外，目标和拿书过于受到最长样本的影响。	避免了线性准则和平方准则的缺点。$J_r(a)=0$时，对所有$y,a^{T}y>b$,意味着$\mathcal{Y}$是空集。

松弛准则的梯度下降：
$$\begin{gathered} \frac{\partial J_r(a)}{\partial a}=\sum _{y\in \mathcal{Y}}\frac{a^{T}y-b}{\Vert y{\Vert }^2}y \\ {a}_{k+1}=a_k-{\eta }_k\sum _{y\in \mathcal{Y}}\frac{a^{T}y-b}{\Vert y{\Vert }^2}y \end{gathered}$$

收敛性证明略。

最小平方误差（MSE）准则函数

前面考虑的准则函数都是只考虑被错分的样本。现在考虑一种包含所有样本的准则函数。

**动机：**对两类分问题，感知准则函数是寻找一个解向量 a，对所有样本 $y_i$，满足 $a^T{y}_i>0,i=1,2,\dots n$。或者说，求解一个不等式组，使满足 $a^T{y}_i>0$的数目最大，从而错分样本最少。
$$a^T{y}_i=b_i>0$$

其中，$b_i$是任意给定的正常数，通常取$b_i=1$，或者$b_i=\frac{n_i}{n}$。其中，$n_i$（$i=1$或$2$）为属于第$i$类样本的总数，且$n_1+n_2=n$。

线性判别函数的参数估计

可得一个线性方程组：$Ya=b$
$$
\begin{bmatrix}
y_{10} & y_{11} & \cdots & y_{1d}\
y_{20} & y_{21} & \cdots & y_{2d}\
\vdots & \vdots & \ddots & \vdots\
y_{n0} & y_{n1} & \cdots & y_{nd}
\end{bmatrix}
\begin{bmatrix}
a_0\
a_1\
\vdots\
a_d
\end{bmatrix}

\begin{bmatrix}
b_1\
b_2\
\vdots\
b_n
\end{bmatrix}
$$

• 如果$Y$可逆，则$a=Y^{-1}b$。
• 但通常情形下，$n\gg d+1$，因此，考虑定义一个误差向量：$e=Ya-b$，并使误差向量最小。

平方误差准则函数

$$J_s(a)=\Vert e{\Vert }^2=\Vert Ya-b{\Vert }^2=\sum _{i=1}^n(a^T{Y}_i-b_i{)}^2$$

对其求导：
$$\begin{gathered} \frac{\partial J_s(a)}{\partial a}=\sum _{i=1}^{n}2(a^T{Y}_i-b_i)Y_i=2Y^T(Ya-b)=0 \\ {Y}^{T}Ya=Y^{T}b\Rightarrow a=(Y^{T}Y{)}^{-1}{Y}^{T}b=Y^{†}b \end{gathered}$$

其中，$Y^{+}$为$Y$的伪逆。

实际计算（正则化技术）：$Y^{\dagger\approx(Y}T Y+\varepsilon I)^{-1}YT (\text{即回归分析方法}) $

梯度下降法

计算伪逆需要矩阵的逆，计算复杂度高。如果原始样本的维数很高，比如$d>5000$，将十分耗时。

• 批处理梯度下降：
  $$a_{k+1}=a_k+{\eta }_k{Y}^T(b-Y{a}_k)$$
  梯度下降法得到的$a_{k+1}$将收敛于一个解，该解满足方程：
  $$Y^T(b-Ya)=0$$

• 单样本梯度下降：此方法需要的计算存储量会更小（此时考虑单个样本对误差的贡献）
  $$a_{k+1}=a_k+{\eta }_k(b_k-(a_k{)}^T{y}^k)y^k$$
  

  

  

Ho-Kashyap方法

感知器和松弛法对线性可分样本集可找到分离向量，但对于不可分的情况就不收敛了。

MSE算法不管样本是否可分都能得到一个权向量，但并不能保证在可分的情况下这个向量一定是分类向量。

若margin $b$是任意选择的，MSE只是$\min \Vert Ya-b{\Vert }^2$,所得到的最优解并不需要位于可分超平面上。若训练样本刚好是线性可分的，那么存在$\hat{a},\hat{b}$满足：
$$Y\hat{a}=\hat{b}>0$$
当我们设置$b=\hat{b}$，利用MSE，就能找到一个分类向量。但是我们没法预知$\hat{b}$。

对MSE准则函数更新为：
$$J_s(a,b)=\Vert Ya-b{\Vert }^2$$

ps：直接优化$J_s(a,b)$将导致平凡解，所以需要给$b$添加约束条件：$b>0$.

此时$b$可以解释为margin.

梯度下降

$$\begin{gathered} \frac{\partial J_s(a,b)}{\partial a}=2Y^T(Ya-b),\frac{\partial J_s(a,b)}{\partial b}=-2(Ya-b) \\ {b}_{k+1}=b_k-{\eta }_k\frac{\partial J_s(a,b)}{\partial b} \end{gathered}$$

约束条件：$a=Y^{†}b$, $b>0$

因为$b_k\ge 0$,要使$b_{k+1}\ge 0$,可以要求$\frac{\partial J_s(a,b)}{\partial b}\le 0$:
$$b_{k+1}=b_k-{\eta }_k\frac{1}{2}\left(\frac{\partial J_s(a,b)}{\partial b}-|\frac{\partial J_s(a,b)}{\partial b}|\right)$$
更新$a,b$:
$$\begin{gathered} a_{k+1}=Y^{†}{b}_k \\ {b}_1>0,b_{k+1}=b_k+2{\eta }_k{e}_k^{†} \\ {e}_k^{†}=\frac{1}{2}\left((Y{a}_k-b_k)+|Y{a}_k-b_k|\right)\Leftarrow \frac{\partial J_s(a,b)}{\partial b}=-2(Ya-b) \end{gathered}$$

• 为了防止$b$收敛于$0$，可以让$b$从一个非负向量（$b_1>0$）开始进行更新。
• 由于要求$\frac{\partial J_s(a,b)}{\partial b}$等于$0$，在开始迭代时可令$\frac{\partial J_s(a,b)}{\partial b}$的元素为正的分量等于零，从而加快收敛速度。

伪算法

• 由于权向量序列 { a k } \{a_k\} {ak​}完全取决于 { b k } \{b_k\} {bk​}，因此本质上讲Ho - Kashyap算法是一个生成margin序列 { b k } \{b_k\} {bk​}的方法。
• 由于初始$b_1>0$，且更新因子$\eta >0$，因此$b_k$总是大于$0$。
• 对于更新因子$0<\eta \le 1$，如果问题线性可分，则总能找到元素全为正的$b$。
• 如果$e_k=Y{a}_k-b_k$全为$0$，此时，$b_k$将不再更新，因此获得一个解。如果$e_k$有一部分元素小于$0$，则可以证明该问题不是线性可分的。(证明略)
  

多类线性判别函数

决策规则: $\forall j\ne i,g_i(x)\ge g_j(x)$, $x$被分为${\omega }_i$类。

$x$被分为${\omega }_i$类的线性判别函数：
$$\forall j\ne i,a_i^{T}x+b_i\ge a_j^{T}x+b_j$$

方法一：MSE多类扩展

可以直接采用$c$个两类分类器的组合，且这种组合具有与两类分类问题类似的代数描述形式。

线性变换(注，此处不采用规范化增广表示)：
$$z=W^{T}x+b,W\in R^{d\times c},b\in R^c$$
决策准则：$\text{if}j=\arg \max (W^{T}x+b),\text{then}x\in {\omega }_j$

回归值的构造：one - hot编码

$$x\in {\omega }_j\Rightarrow z\in R^c,z_{ij}=\{\begin{array}{ll}1,& \text{if}i=j\\ 0,& \text{otherwise}\end{array}$$

若$x$属于${\omega }_j$类，则$x$的类别编码$z$为一个$c$维向量，其中第$j$个元素为$1$，其余为$0$。

目标函数

$$\underset{W,b}{\min }\sum _{i=1}^n\Vert W^T{x}_i+b-z_i{\Vert }_2^2$$

令：
$$W=\left[\begin{array}{c}{W}^T\\ b\end{array}\right]\in R^{(d+1)\times c},\hat{x}=\left[\begin{array}{c}x\\ 1\end{array}\right]\in R^{d+1},\hat{X}=({\hat{x}}_1,{\hat{x}}_2,\cdots ,{\hat{x}}_n)\in R^{(d+1)\times n}$$
则有：
$$\sum _{i=1}^n\Vert W^T{x}_i+b-z_i{\Vert }_2^2=\Vert {\hat{W}}^T\hat{X}-Z{\Vert }_F^2$$
$\Vert \cdot {\Vert }_F$为Frobenius范数。进而有：
$$\begin{gathered} \underset{W}{\min }\Vert {\hat{W}}^T\hat{X}-Z{\Vert }_F^2 \\ \hat{W}=(\hat{X}{\hat{X}}^T{)}^{-1}\hat{X}{Z}^T\in R^{(d+1)\times c} \end{gathered}$$
实际中：可能会遇到矩阵奇异或数值不稳定的问题。为此，我们引入正则化项（类似岭回归）
$$\hat{W}=(\hat{X}{\hat{X}}^T+\lambda I{)}^{-1}\hat{X}{Z}^T\in R^{(d+1)\times c}$$
$\lambda$: 正则化参数，通常取一个小正数。防止过拟合以及增强数值计算的稳定性。

R^{d + 1},\ \hat{X}=(\hat{x}_1,\hat{x}_2,\cdots,\hat{x}n)\in R^{(d + 1)\times n}
$$则有：$$
\sum{i = 1}^{n}|WT x_i + b - z_i|_2^2=|\hat{W}T\hat{X}-Z|F^2
KaTeX parse error: Can't use function '$' in math mode at position 2: $̲\|\cdot\|_F$为Fr…
\min{W}|\hat{W}^{T\hat{X}-Z|_F}2\
\hat{W}=(\hat{X}\hat{X}^T){-1}\hat{X}Z^T\in R^{(d + 1)\times c}\
$$实际中：可能会遇到矩阵奇异或数值不稳定的问题。为此，我们引入正则化项（类似岭回归）$$
\hat{W}=(\hat{X}\hat{X}^T+\lambda I)^{-1}\hat{X}ZT\in R^{(d + 1)\times c}
$$
$\lambda$: 正则化参数，通常取一个小正数。防止过拟合以及增强数值计算的稳定性。