Week 5 Linear Models for Classification (Part A)

Week 5 Linear Models for Classification (Part A)
目录

一、线性分类的基本概念

1、回归与分类（Regression vs Classification）

2、从线性回归到线性分类

3、分类器（Classifier）

3、决策边界（Decision Boundary）

4、线性分类器（Linear Classifier）

5、广义线性模型（Generalised Linear Models）

编辑二、判别模型（Discriminative Models）

1、定义

2、两类判别函数（Two Class Discriminant Function）

3、泛化到多分类问题（Generalisation to Multiclass Problems）

4、常见的判别模型

三、生成模型（Generative Models）-以统计学和Bayes作为理论基础

1、定义

2、常见的生成模型

3、生成模型与判别模型的区别与联系

四、感知器算法（ Perceptron Algorithm）- 硬分类且属于判别模型

1、定义

2、感知机模型

3、感知机的损失函数

4、感知机的算法步骤

5、感知机的算法的例子

6、感知机一些重要性质

五、多层感知机（MLP）

1、多层感知机的结构图

2、多层感知机的算法流程

六、分类过程中如何预防过拟合问题（Tutorial）

1、交叉折叠验证

编辑2、使用更多数据进行训练

3、移除一些特征值

4、早点停止训练

5、正则化

6、Ensembling模型融合

一、线性分类的基本概念

1、回归与分类（Regression vs Classification）

（1）相同点：其实分类和回归的本质是一样的，都是对输入做出预测，其区别在于输出的类型。

（2）分类问题：分类问题的输出是离散型变量(如: +1、-1)，是一种定性输出。(预测明天天气是阴、晴还是雨)

生活中实际运用的例子：
- 将客户分为良好信用、不良信用或灰色
- 预测电子邮件是否为垃圾邮件，是否应发送到垃圾邮件文件夹
- 识别手写数字图像
（3）回归问题：回归问题的输出是连续型变量，是一种定量输出。(预测明天的温度是多少度)

生活中实际运用的例子：
- 根据房屋面积的增加预测房价
- 根据学习时间预测考试结果
- 根据推文的数量预测电影票的数量。
（4）两者的对比对比

2、从线性回归到线性分类

（1）线性分类的由来

线性回归经过一个激活函数然后根据一个阈值来获得分类的结果，如此就成为线性分类；
也可以理解为将 $w^{T}x+b$ 降维到一维而获得分类结果。

（2）激活函数

（3）硬分类和软分类

3、分类器（Classifier）

（1）分类器的作用：常规任务是利用给定的类别、已知的训练数据来学习分类规则和分类器，然后对未知数据进行分类（或预测）。逻辑回归（logistics）、SVM等常用于解决二分类问题，对于多分类问题（multi-class classification），比如识别手写数字，它需要10个分类，同样也可以用逻辑回归或SVM，只是需要多个二分类来组成多分类，但这样容易出错且效率不高，常用的多分类方法有softmax。

（2）分类算法的划分-基于概率密度的方法和基于判别函数的方法。
- 基于概率密度的分类算法通常借助于贝叶斯理论体系，采用潜在的类条件概率密度函数的知识进行分类；在基于概率密度的分类算法中，有著名的贝叶斯估计法、最大似然估计，这些算法属于有参估计，需要预先假设类别的分布模型，然后使用训练数据来调整概率密度中的各个参数。另外，如 Parzen窗、Kn邻近等方法属于无参估计，此类方法可从训练样本中直接估计出概率密度。基于判别函数的分类方法使用训练数据估计分类边界完成分类，无需计算概率密度函数。
- 基于判别函数的方法则假设分类规则是由某种形式的判别函数表示，而训练样本可用来表示计算函数中的参数，并利用该判别函数直接对测试数据进行分类。此类分类器中，有著名的感知器方法（感知器算法）、最小平方误差法、SVM法、神经网络方法以及径向基(RBF)方法等。
（3）分类算法的划分-根据监督方式划分分类算法，分类学习问题可分为三大类：有监督分类、半监督分类和无监督分类。
- 有监督分类是指用来训练分类器的所有样本都经过了人工或其他方式的标注，有很多著名的分类器算法都属于有监督的学习方式，如AdaBoost[51]，SVM，神经网络算法以及感知器算法。
- 无监督分类是指所有的样本均没有经过标注，分类算法需利用样本自身信息完成分类学习任务，这种方法通常被称为聚类，常用的聚类算法包括期望最大化（EM）算法和模糊C均值聚类算法等。
- 半监督分类指仅有一部分训练样本具有类标号，分类算法需要同时利用有标号样本和无标号样本学习分类，使用两种样本训练的结果比仅使用有标注的样本训练的效果更好。这类算法通常由有监督学习算法改进而成，如SemiBoost、流形正则化、半监督SVM等。
3、决策边界（Decision Boundary）

（1）输入空间：每个输入数据点由输入空间中的一个向量表示

（2）决策边界：决策区域由决策边界分隔
（3）决策区域：根据类标签，将输入空间划分为决策区域，每个区域对应一个类标签

（3）线性模型的决策边界：决策边界是输入向量的线性函数。
- 如果输入空间是 D 维的，则决策边界将是一个 (D-1) 维超平面（hyperplane）
注：这个平面由两个性质定义：1、方程是线性的，是由空间点的各分量的线性组合。2、方程数量是1。这个平面是建立在“三维”上的。如果我们撇开“维度”这个限制，那么就有了超平面的定义。实际上，超平面是纯粹的数学概念，不是物理概念，它是平面中的直线、空间中的平面的推广，只有当维度大于3，才称为“超”平面。它的本质是自由度比空间维度小1。自由度的概念可以简单的理解为至少要给定多少个分量的值才能确定一个点. 例如, 三维空间里的(超)平面只要给定了(x,y,z)中任意两个分量, 剩下的一个的值就确定了. 先确定值的两个分量是自由的, 因为它们想取什么值就能取什么值;剩下的那个是"不自由的", 因为它的值已经由另外两确定了. 二维空间里的超平面为一条直线. 一维空间里超平面为数轴上的一个点。

（4）线性可分性：类可以被线性决策面精确分离的数据集被称为线性可分的

4、线性分类器（Linear Classifier）

（1）线性分类器定义：在二维空间中的一个数据集，如果他正好能够被一条直线分成两类，那么我们称它为线性可分数据集，这条直线就是一个线性分类器。

（2）线性分类器例子

5、广义线性模型（Generalised Linear Models）

我们可以重用回归学习模型来学习分类模型：

（1）线性回归模型

（2）分类模型（通过激活函数或者称step function将线性模型转化为分类模型）

二、判别模型（Discriminative Models）

1、定义
- 从概率分布的角度考虑，对于一堆样本数据，每个均有特征对应分类标记 $y_i$ 。
- 学习得到条件概率分布P(y|x)，即在特征x出现的情况下标记y出现的概率。(判别模型就是直接学习条件概率分布P(y∣x))
- 这类模型的典型代表是logistic回归和softmax回归，它们直接对p(y∣x)建模，而不对p(x,y)建模，即每一假设x服从何种概率分布。logistic回归用于二分类问题，它直接根据样本x估计出它是正样本的概率。
2、两类判别函数（Two Class Discriminant Function）

（1）决策边界

Linear :

（2） 几何特征（期末考试可能会考证明题）
- 决策面垂直于权重向量 w ，也可以说是超平面（决策面）的法向量
证明：设A和B为决策面上的不同的两个点和（≠），则有:

两式相减可得：

由于和均为向量，所以设他们之间的夹角为 $\theta$ ,所以我们有：

$\left \| w \right \|\times\left \| (x_A-x_B) \right \|\times\cos \theta = 0$

而（≠），所以 $\cos \theta = 0$ ，则 $\theta = 90^{\circ}$ ，所以决策面垂直于权重向量 w 。

证毕。
- 输入向量在在权重向量上的投影大小为 $-\frac{w_0}{\left \| w \right \|}$
证明：

$P_{rojw}x = \cos \theta \left \| x \right \| = \frac{w^Tx}{\left \| w \right \|\left \| x \right \|} \times \left \| x \right \| = \frac{w^Tx}{\left \| w \right \|} = -\frac{w_0}{\left \| w \right \|}$
- 输入向量到决策面的距离向量为 $\frac{y(x)}{\left \| w \right \|}$ ,决策面为 = 0即
证明：

我们设这个距离向量为,原点与交点的连线为向量t,作图如下：

我们有有向量的相加性可得：

$\vec{x} = \vec{t} + \vec{v}\frac{\vec{w} }{\left | w \right |}$

注： $\frac{\vec{w}}{\left | w \right |}$ 是 $\vec{w}$ 方向的单位向量，且 $\vec{v}$ 与 $\vec{w}$ 平行同向

在原有的等式基础上左乘并加上,可得：

$w_0+w^Tx = w^Tt+w_0 + v\frac{w^tw}{\left | w \right |}$

又因为向量t在决策平面上，所以有：

所以我们可以化简式子为：

$y(x) = v\frac{w^tw}{\left | w \right |} = v\frac{\left \| w \right \|}{\left | w \right |}^2 = v\left | w \right | \Rightarrow v = \frac{y(x)}{\left \| w \right \|}$

证毕。

3、泛化到多分类问题（Generalisation to Multiclass Problems）

（1）One-versus-the-rest classifier（一对多法分类器）

训练时依次把某个类别的样本归为一类,其他剩余的样本归为另一类，这样k个类别的样本就构造出了k个SVM。分类时将未知样本分类为具有最大分类函数值的那类。

举个例子：

假如我有四类要划分（也就是4个Label），它们是A、B、C、D。于是我在抽取训练集的时候，分别抽取A所对应的向量作为正集，B,C,D所对应的向量作为负集；B所对应的向量作为正集，A,C，D所对应的向量作为负集；C所对应的向量作为正集， A,B,D所对应的向量作为负集；D所对应的向量作为正集，A,B,C所对应的向量作为负集，这四个训练集分别进行训练，然后的得到四个训练结果文件，在测试的时候，把对应的测试向量分别利用这四个训练结果文件进行测试，最后每个测试都有一个结果f1(x),f2(x),f3(x),f4(x).于是最终的结果便是这四个值中最大的一个。

这种方法有种缺陷,因为训练集是1:M,这种情况下存在biased.因而不是很实用.

（2）One-versus-one classifier（一对一法分类器）

其做法是在任意两类样本之间设计一个SVM，因此k个类别的样本就需要设计k(k-1)/2个SVM。当对一个未知样本进行分类时，最后得票最多的类别即为该未知样本的类别。Libsvm中的多类分类就是根据这个方法实现的。

举个例子：

投票是这样进行的：A=B=C=D=0;
(A, B)-classifier 如果是A win,则A=A+1;otherwise,B=B+1;
(A,C)-classifer 如果是A win,则A=A+1;otherwise, C=C+1;
...
(C,D)-classifer 如果是A win,则C=C+1;otherwise,D=D+1;
The decision is the Max(A,B,C,D)

这种方法虽然好,但是当类别很多的时候,model的个数是n*(n-1)/2,代价还是相当大的.

4、常见的判别模型
- K近邻
基于已知样本，对未知样本进行预测时，找到对应的K个最近邻，通过多数表决进行预测。没有显式的学习过程。
- SVM
SVM分为线性可分支持向量机 (硬间隔最大化)、线性支持向量机 (软间隔最大化)、非线性支持向量机 (核函数)三种。目的是最大化间隔，这是和感知机最大的区别。
- 决策树
- 感知机（Perceptron）
- 线性判别分析（LDA）
- 线性回归
- 传统的神经网络
- 逻辑斯蒂回归
- boosting
通过改变训练样本的权重，训练多个分类器，将分类器进行线性组合，提升分类性能。AdaBoost采用加权多数表决的方法。
- 条件随机场（conditional random field, CRF）、
给定一组输入随机变量条件下另一组输出随机变量的条件概率分布模型，其特点是假设输出随机变量构成马尔可夫随机场。可应用于标注问题。

三、生成模型（Generative Models）-以统计学和Bayes作为理论基础

1、定义

从概率分布的角度考虑，对于一堆样本数据，每个均有特征对应分类标记 $y_i$ 。

学习得到联合概率分布P(x,y)，即特征x和标记y共同出现的概率，然后求条件概率分布。能够学习到数据生成的机制。(生成模型就是要学习x和y的联合概率分布P(x,y)，然后根据贝叶斯公式来求得条件概率P(y∣x)，预测条件概率最大的y)。

2、常见的生成模型
- 朴素贝叶斯
- 隐马尔可夫模型
由隐藏的马尔可夫链随机生成观测序列，是生成模型。HMM是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程。包含三要素：初始状态概率向量pie，状态转移概率矩阵A，观测概率矩阵B。
- 高斯混合模型
- 文档主题生成模型（LDA）
- 限制玻尔兹曼机
3、生成模型与判别模型的区别与联系

四、感知器算法（ Perceptron Algorithm）- 硬分类且属于判别模型

1、定义

感知机的输入为样本的特征向量，输出为样本的类别，取+1和-1二值。具体方法为：给样本的每一维特征引入一个相乘的权重来表达每个特征的重要程度，然后对乘积求和后加上偏置项。将结果送入符号函数，利用符号函数的二值特性将样本划分为两类。所以，训练感知机的目标可以概括为：寻找合适的权值和偏置，使得符号函数能够将样本尽量准确地分成两类。

2、感知机模型

（1）结构图

（2）参数解释

假设现在有 $\tiny N$ 个训练样本，每个样本都有 $\tiny D$ 个属性（即 $\tiny D$ 维特征）和一个类别标签，那么样本的特征空间可以表示为：

$\left \{ \boldsymbol{x}_{1},\boldsymbol{x}_{2},\cdots,\boldsymbol{x}_{N} \right \}=\begin{pmatrix} x_{11} & x_{21}& \cdots& x_{N1}\\ x_{12}& x_{22}& \cdots& x_{N2}\\ \vdots& \vdots& \ddots & \vdots\\ x_{1D}& x_{2D}& \cdots & x_{ND}\end{pmatrix}$

样本的类别标签向量可以表示为： $\boldsymbol{y}^{T}=\left \{ y_{1},y_{2},\cdots,y_{N} \right \}$ ，由于感知机解决的是二分类问题，所以， $y_{i}\in\left \{ +1,-1 \right \}$ 。

让我们以样本的特征空间为输入空间，以样本的类别标签向量为输出空间，定义如下函数：

$\large {\color{DarkRed} f(\boldsymbol{x}_{i})=sign (\boldsymbol{w}^{T}\cdot \boldsymbol{x}_{i}+b)=sign(w_{1}x_{i1}+w_{2}x_{i2}+\cdots+w_{N}x_{iN}+b)}$

这个函数就被称为感知机模型，下图展示的是它的图形化理解。其中，w和b是感知机模型的参数，w是权值向量，b是偏置项，step function是感知机模型的激活函数sign。
由于使用符号函数作为激活函数，所以我们可以认为分类阈值是，即： $\boldsymbol{w}^{T}\cdot \boldsymbol{x}+b=0$ 是一个分界。我们的目标是：寻找合适的w和b，尽量使得所有 $y_{i}=+1$ 的样本i，都有 $\boldsymbol{w}^{T}\cdot \boldsymbol{x}_{i}+b> 0$ ；所有 $y_{i}=-1$ 的样本i，都有 $\boldsymbol{w}^{T}\cdot \boldsymbol{x}_{i}+b< 0$ 。而 $\boldsymbol{w}^{T}\cdot \boldsymbol{x}+b=0$ 对应着特征空间中的一个超平面，其中w是超平面的法向量，b是超平面的截距。

由此，我们可以总结出感知机模型的几何意义：在特征空间中寻找一个分离超平面，这个超平面将特征空间划分成两个部分，并且类+1和类-1样本点尽量位于超平面的两侧。如果想要类+1和类-1样本严格位于超平面两侧，特征空间需要满足线性可分。

3、感知机的损失函数

is the true label , $w\phi (x_n)$ 是预测的label,两者的取值都在｛1，-1｝，M is the set of misclassified examples。
- 错误分类的情况：
- 损失函数的公式：
4、感知机的算法步骤

（1）用随机值初始化权重向量 $\vec{w}$

（2）重复下面的操作，直到所有数据点正确分类或错误＜ $\varepsilon$

对于每个训练点x，执行以下操作:
- 计算激活函数：
我们用随机梯度下降法更新参数，我们并不是一次使中所有误分类样本点的梯度都下降，而是一次随机选取一个误分类点使其梯度下降。
- 如果y = t（分类正确），则不更新权重 $\vec{w}$
- 否则，更新权重 $\vec{w}$ ：
有的算法里偏差也要更新： $w_0\leftarrow w_0+\eta t_n$

5、感知机的算法的例子

6、感知机一些重要性质
- 如果数据是线性可分离的，则感知器可以确保找到完美的权重向量。然而，可能需要对数据进行太多迭代才能收敛到完美的权重向量
- 如果数据不是线性可分离的，感知器可能不会收敛。在这种情况下，它可以循环通过一些权重向量而不停止
- 感知器对初始化敏感。如果算法的两次运行以不同的顺序访问训练集中的训练示例，则它们可能收敛到不同的完美权重。
五、多层感知机（MLP）

1、多层感知机的结构图

2、多层感知机的算法流程

MLP详细知识点参照：多层感知机(MultiLayer Perceptron)以及反向传播算法(Backpropagation)_迷雾总会解的博客-CSDN博客_multilayer perceptron

六、分类过程中如何预防过拟合问题（Tutorial）

1、交叉折叠验证

使用初始训练数据生成多个迷你列车测试分割。使用这些分割来调整模型

2、使用更多数据进行训练

3、移除一些特征值

4、早点停止训练

5、正则化

6、Ensembling模型融合

（1）bagging：相同模型不同参数结果的平均，典型例如：random forest

（2）boosting：基于上一个模型的结果生成下一个模型和权重，分为weight based和residual based
- weight based：计算上一个模型的误差，给误差大的行提高权重，计算下一个模型，例如AdaBoost
- esidual based：计算上一个模型的误差，作为下一个模型的目标值，例如：Xgboost、Lightgbm、H2Os FBM、CatBoost
相关阅读:
新人FPGA验证书籍推荐
 rpc error: code = Unimplemented desc =
基于模糊逼近系统不确项的滑模自适应控制
 Docker搭建Mongdb Replica Set集群+主主高可用+多台机器
 CIE 化学选择题真题解析
 使用Arrays.asList与不使用的区别
 2022，软件测试行业岗位细分，薪资分布
 携创教育：成人高考理工类只能理科生报考吗
 羊了个羊的接口测试
 miRNA测序数据生信分析——第一讲，总结概述
原文地址：https://blog.csdn.net/wangjian530/article/details/125904588

一、线性分类的基本概念

1、回归与分类（Regression vs Classification）

2、从线性回归到线性分类

3、分类器（Classifier）

3、决策边界（Decision Boundary）

4、线性分类器（Linear Classifier）

5、广义线性模型（Generalised Linear Models）

二、判别模型（Discriminative Models）

1、定义

2、两类判别函数（Two Class Discriminant Function）

3、泛化到多分类问题（Generalisation to Multiclass Problems）

4、常见的判别模型

三、生成模型（Generative Models）-以统计学和Bayes作为理论基础

1、定义

2、常见的生成模型

3、生成模型与判别模型的区别与联系

四、感知器算法（ Perceptron Algorithm）- 硬分类且属于判别模型

1、定义

2、感知机模型

3、感知机的损失函数

4、感知机的算法步骤

5、感知机的算法的例子

6、感知机一些重要性质

五、多层感知机（MLP）

1、多层感知机的结构图

2、多层感知机的算法流程

六、分类过程中如何预防过拟合问题（Tutorial）

1、交叉折叠验证

2、使用更多数据进行训练

3、移除一些特征值

4、早点停止训练

5、正则化

6、Ensembling模型融合