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

确定性简单模式
从要解决的问题和训练样本出发，直接求出判别函数。
有些方法可事先确定判别函数的形式，通过训练样本确定其中的参数。如：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和感知机法则，两个算法思路简单清晰，实现起来也比较容易，是后续复杂算法的基础。对于线性判别函数，需要掌握其基本的形式和构建思想即可。

最后编辑于：2019.11.09 20:51:50

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 218,122评论 6赞 505
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 93,070评论 3赞 395
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 164,491评论 0赞 354
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,636评论 1赞 293
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,676评论 6赞 392
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,541评论 1赞 305
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,292评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,211评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,655评论 1赞 314
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,846评论 3赞 336
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,965评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,684评论 5赞 347
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,295评论 3赞 329
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,894评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,012评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,126评论 3赞 370
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,914评论 2赞 355

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

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

目录

前言

概念回顾

生成模型

判别模型

线性判别函数

判别函数的定义

一般形式

广义线性判别函数

Fisher线性判别分析

练习

感知机算法

感知机准则总结

总结

推荐阅读更多精彩内容