模式识别课程(四)-线性分类器/线性判别函数

作者: 阿瑟_TJRS | 来源:发表于2019-11-04 19:00 被阅读0次

模式识别第四五章线性分类器非线性判别函数
模式识别课程(四)-线性分类器/线性判别函数
线性分类模型(一)——线性判别函数
损失函数
BAT机器学习面试1000题系列（第31~40题）
基于sklearn的线性回归器
三、线性分类器
逻辑回归总结
cs231n - Section#2
机器学习之支持向量机

确定性简单模式
从要解决的问题和训练样本出发，直接求出判别函数。
有些方法可事先确定判别函数的形式，通过训练样本确定其中的参数。如：SVM ，神经网络
也称为基于数据的模式识别方法(或统计模式识别的几何方法)

线性判别函数

基于样本直接设计分类器的三个基本要素

确定分类器即判别函数的类型
确定分类器设计的目标或准则
设计算法利用样本数据寻找最优的函数参数
形式化定义：
在判别函数集 $\{g(\theta),\theta \in \Theta \}$ 中，确定待定参数 $\theta ^{*}$ ，使得目标函数 $L(\theta)$ 最小/大：
$L(\theta ^{*})=\underset{\theta}{min}L(\theta)$

判别函数的定义

直接用来对样本进行分类判决的函数
若两类样本可以用一个方程 $g(x)=0$ 来划分，则 $g(x)$ 为判别函数/决策函数/判决函数， $g(x)=0$ 为决策面

如上图：

一般形式

线性判别函数由输入向量x的各分量的线性组合构成
矩阵形式表示为： $g(X)=W^TX+W_0$ , $W_0$ 称为偏置
$X=\begin{bmatrix} x_1\\ x_2\\ ...\\ x_d \end{bmatrix},W=\begin{bmatrix} W_1\\ W_2\\ ...\\ W_d \end{bmatrix}$
如果将偏置项也整合到矩阵中的话，可以表示为： $g(X)=W^T$ ，称为增广表示形式
$X=\begin{bmatrix} 1\\ x_1\\ x_2\\ ...\\ x_d \end{bmatrix},W=\begin{bmatrix} W_0\\ W_1\\ W_2\\ ...\\ W_d \end{bmatrix}$
关于判别函数存在以下两种情况

针对二分类问题，即类别有2个如上图，对于d维数据， $d-1$ 维的超平面把 $d$ 维输入空间中归为 $w_1$ 的点与归为 $w_2$ 的点分开。
权向量的性质： $W$ 和决策面正交，确定了决策面的方向。 对任一点X及其在决策面上的投影 $X_{\perp}$ ，有:
$X=X_{\perp}+r\frac{W}{||W||}$ , $g(X)=W^TX+W_0$ ,
且 $g(X_{\perp})=W^TX_{\perp}+W_0$
将X代入函数式中：
$g(X)=W^T(X_{\perp}+r\frac{W}{||W||})+W_0$
$=W^TX_{\perp}+r\frac{W^TW}{||W||}+W_0$
$=r||W||$
$r=\frac{g(x)}{||W||}$
其中 $r$ 是 $X$ 到决策面的垂直距离， $\frac{W}{||W||}$ 是 $W$ 方向上的单位向量。
任一点到决策面的垂直距离维 $r=\frac{g(x)}{||W||}$
$\color{red}{g(x)给出了点到判别面的距离的度量}$
原点到决策面的垂直距离为 $-\frac{W_0}{||W||}$
$\color{red}{w_0决定了判别面的位置}$
多类问题
给定c(c>2)个类别的样本集合，三种划分方式：

$\color{red}{1对其他 (one-versus-the-rest)}$ ,转化为c个两分类问题 存在不能确定区域
$\color{red}{1对1 (one-versus-one)}$ ，c(c-1)/2个二元判别函数
c类判别函数

广义线性判别函数

线性判别函数 $g(X)=W_0+\sum_{i=1}^dw_ix_i$ ：加入更高次的项，得到多项式判别函数： $g(x)=\sum_{i=1}^{\hat{d}}w_iy_i(X),g(X)=W^Ty$
$y=\sum w_{ij}x_ix_j$
$y_i(X)$ 将d维空间上的点映射到 $\hat{d}$ 维的y空间上的点，
导致维度灾难： $\hat{d}>d$ ，即向高维空间映射，
相应补救措施：强制加入大的 margin( 或训练样本之间的“间隔等措施，如支持向量机。这样处理基于假设：映射到高维空间并不给数据附加任何错误的结构及相关性）

Fisher线性判别分析

1936年R.A.Fisher提出线性判别分析(Linear Discriminant Analysis,LDA),从降低维度的角度考察线性分类模型。

目标：寻找有利于分类的投影方向.通过调整权向量w ，我们可以选择让类别之间分开最大的一个投影。
对于二分类问题，其思想是选择投影方向，使投影后两类相隔尽可能远，而同时每一类内部的样本又尽可能聚集。
在原样本空间中(二分类)，两类的类均值向量：

$m_2=\frac{1}{n_2}\sum_{X_i \in D_2}X_i$
当使用权重向量 $W$ 投影时， $类间分离程度$ 的最简单度量方式是 $类均值投影之后的距离$
$\widetilde{m_1}-\widetilde{m_2}=W^T(m_1-m_2)$ ,最大化该距离即可
$\widetilde{m_k}=\sum_{X_i \in D_i}W^TX_i$ 表示投影后的类均值向量，
均值投影的问题在于没有考虑类内的数据离散度
Fisher提出：通过最大化一个函数，使投影后的类间分离性最大，同时又能使每类的类内分离性较小。
投影后的类内离散度(使用方差表示)如下：
$\widetilde{s_k^2}=\sum_{X_i \in D_k}(W^TX_i-\widetilde{m_k})$
类内的总离散度是 $\widetilde{s_1^2}+\widetilde{s_2^2}$
$\color{red}{Fisher 准则函数定义为类间离散度与类内离散度之比。}$
$J_F(W)=\frac{(\widetilde{m_1}-\widetilde{m_2})^2}{\widetilde{s_1^2}+\widetilde{s_2^2}}$
将公式转换成为原空间的表示
$J_F(W)=\frac{W^TS_BW}{W^TS_WW}$
$S_B=(m_2-m_1)(m_2-m_1)^T$ 表示原空间类间离散度矩阵
$S_W=\sum_{i=1}^2\sum_{X\in D_i}(X-m_i)(X-m_i)^T$ 表示原空间类内离散度矩阵
$W^*=\underset{W}{argmax}J_F(W)=S_W^{-1}(m_2-m_1)$
对于准则函数 $J_F(W)$ 求其最大值，对W求导并令其等于0：

相应判别函数为：
若

练习

利用Fisher判别解决二分类

感知机算法

Rosenblatt于1962年提出，是一个二分类的线性模型，输入特征向量X，输出类别[t],分别为+1和-1
$y(X)=f(W^T\phi(X))$
非线性激活函数f()： $f(a)=\left\{\begin{matrix} +1,a\geqslant 0\\ -1,a<0 \end{matrix}\right.$

某错分样本对误差函数的贡献是
w 的线性函数，而对于正确分类的样本，误差函数等于零。总的误差函数是分段线性的。
对于该误差函数使用随机梯度下降法进行迭代更新：权向量的迭代公式为：

感知机算法的可收敛性：

感知机准则总结

优点：简单、便于实现
缺点：结果不唯一，在线性不可分的情况下不收敛
然而感知机算法是神经网络，深度学习发展的基础。

总结

本篇笔记记录了线性分类器的基本知识，主要介绍了Fisher和感知机法则，两个算法思路简单清晰，实现起来也比较容易，是后续复杂算法的基础。对于线性判别函数，需要掌握其基本的形式和构建思想即可。

模式识别第四五章线性分类器非线性判别函数
title: 模式识别第四五章线性分类器非线性判别函数date: 2017-03-26 18:47:50c...
模式识别课程(四)-线性分类器/线性判别函数
目录前言概念回顾生成式模型判别式模型线性判别函数 Fisher线性判别分析感知机法则总结前言本笔记是...
线性分类模型(一)——线性判别函数
本文首发与我的个人博客Suixin's Blog 线性分类模型主要有四种不同的方法，线性判别函数、生成式模型、判别...
损失函数
线性分类器简介线性评分函数阐明线性分类器损失函数多分类SVMsoftmax分类器SVM和softmax的比较...
BAT机器学习面试1000题系列（第31~40题）
31.线性分类器与非线性分类器的区别以及优劣如果模型是参数的线性函数，并且存在线性分类面，那么就是线性分类器，否则...
基于sklearn的线性回归器
理论线性回归器相比于线性分类器，线性回归器更加自然。回归任务的label是连续的变量（不像分类任务label是...
三、线性分类器
3.1 线性分类器的数学定义线性分类器：其中，代表图片向量（将二维图片转为一维向量），维度为，为分类器的参数，...
逻辑回归总结
一、逻辑回归来源据线性可分可以使用线性分类器，如果数据线性不可分，可以使用非线性分类器，这里似乎没有逻辑回...
cs231n - Section#2
一、线性分类Linear Classification 线性分类器中的score function完成下面的函数映...
机器学习之支持向量机
SVM可以做线性或者非线性的分类，回归，甚至异常值检测。 1. 线性SVM分类左图显示了三种可能的线性分类器的判...

模式识别课程(四)-线性分类器/线性判别函数

目录

前言

概念回顾

生成模型

判别模型

线性判别函数

判别函数的定义

一般形式

广义线性判别函数

Fisher线性判别分析

练习

感知机算法

感知机准则总结

总结

相关文章

模式识别第四五章线性分类器非线性判别函数

模式识别课程(四)-线性分类器/线性判别函数

线性分类模型(一)——线性判别函数

损失函数

BAT机器学习面试1000题系列（第31~40题）

基于sklearn的线性回归器

三、线性分类器

逻辑回归总结

cs231n - Section#2

机器学习之支持向量机

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

大数据，机器学习，人工智能

机器学习与数据挖掘

Machine Learning & Recommendation & NLP & DL

大数据