统计学习方法笔记03

李航. 统计学习方法[M]. 清华大学出版社, 2012.

2.2 感知机学习策略

定义2.2（数据集的线性可分性）：如果存在某个超平面S能够将数据集的正实例点和负实例点完全正确地划分到超平面的两侧，则称数据集T为线性可分数据集(linearly separable data set)，否则称数据集T线性不可分。

感知机的学习目标：找到完全正确分开的分离超平面。

损失函数定义为误分类点到超平面S的总距离（不考虑 $\dfrac{1}{||\omega||}$ ）：

$L(\omega,b) = - \sum_{x_i\in M} y_i(\omega\cdot x_i + b)$

这个损失函数就是感知机学习的经验风险函数。

2.3 感知机学习算法

感知机学习算法的原始形式

感知机算法是对损失函数求极小化问题的解：

$\min_{\omega,b} L(\omega,b) = - \sum_{x_i\in M} y_i(\omega\cdot x_i+b)$

感知机学习算法是误分类驱动的，具体采用随机梯度下降法(stochastic gradient descent)。即首先任取 $\omega_0,b_0$ ，然后用梯度下降法不断极小化目标函数，极小化过程中一次随机选取一个误分类点使其梯度下降。假设误分类点集合M是固定的，那么损失函数 $L(\omega,b)$ 的梯度为：

$\nabla_{\omega} L(\omega,b) = - \sum_{x_i\in M} y_i x_i$

$\nabla_{b} L(\omega,b) = - \sum_{x_i\in M} y_i$

随机选取一个误分类点 $(x_i,y_i)$ ，对 $\omega,b$ 进行更新：

$\omega \leftarrow \omega + \eta y_i x_i$

$b \leftarrow b + \eta y_i$

式中 $\eta \in (0,1]$ 是步长，在统计学习中又称为学习率(learning rate)。感知机学习算法由于采用不同的初值或者不同的误分类点，解可以不同。

定理2.1（Novikoff）感知机算法收敛

令 $\hat{\omega} = (\omega^T,b)^T$ ， $\hat{x} = (x^T,1)^T$ ，则 $\hat{\omega} \cdot \hat{x} = \omega\cdot x + b$ 。

设训练数据集 $T = \{ (x_1,y_1),(x_2,y_2),\dots,(x_N,y_n) \}$ 是线性可分的，其中 $x_i \in \mathcal{X} = \mathbb{R}^n$ ， $y_i \in \mathcal{Y} = \{-1,+1\}$ ， $i = 1,2,\dots,N$ ，则

(1) 存在满足条件 $||\hat{\omega}_{opt}|| = 1$ 的超平面 $\hat{\omega}_{opt} \cdot \hat{x} = \omega_{opt}\cdot x + b_{opt} = 0$ 将训练数据集完全正确分开；且存在 $\gamma >0$ ，对所有 $i = 1,2,\dots,N$

$y_i (\hat{\omega}_{opt} \cdot \hat{x}) = y_i(\omega_{opt}\cdot x + b_{opt}) \geq \gamma$

(2) 令 $R = \max_{1\leq i\leq N} ||\hat{x}_i||$ ，则感知机算法在训练数据集上的误分类次数k满足不等式

$k \leq \left(\dfrac{R}{\gamma}\right)^2$

【证明】

(1) 仅证明存在性，由线性可分数据集定义即证。并取

$\gamma = \min_{i} \{y_i (\omega_{opt} \cdot x_i + b_{opt})\}$

作为数据集中所有样本距超平面的最小距离。

(2) 根据感知机算法，参数 $\omega$ 和 $b$ 的更新规则是

$\hat{\omega}_k = \hat{\omega}_{k-1} + \eta y_i \hat{x}_i$

于是我们有如下两个不等式：

$\begin{aligned}\hat{w}_k \cdot \hat{w}_{k-1} &= \hat{w}_{k-1} \cdot \hat{w}_{opt} + \eta y_i \hat{\omega}_{opt} \cdot \hat{x}_i \\&\geq \hat{w}_{k-1} \cdot \hat{w}_{opt} + \eta \gamma \\&\geq \hat{w}_{k-2} \cdot \hat{w}_{opt} + 2\eta \gamma \\&\geq \dots \\&\geq k\eta\gamma\end{aligned}$

和

$\begin{aligned}||\hat{w}_k||^2 &= ||\hat{w}_{k-1}||^2 + 2\eta y_i \hat{\omega}_{k-1} \cdot \hat{x}_i + \eta^2 ||\hat{x}_i||^2 \\&\leq ||\hat{w}_{k-1}||^2 + \eta^2 ||\hat{x}_i||^2 \\&\leq ||\hat{w}_{k-2}||^2 + 2\eta^2 ||\hat{x}_i||^2 \\&\leq \dots \\&\leq k\eta^2 R^2\end{aligned}$

综合以上两个不等式，得

$k\eta\gamma \leq \hat{\omega}_k \cdot \hat{\omega}_{opt} \leq ||\hat{\omega}_k|| \; ||\hat{\omega}_{opt}|| =||\hat{\omega}_k|| \leq \sqrt{k}\eta R$

即

$k \leq \left(\dfrac{R}{\gamma}\right)^2$

感知机学习算法的对偶形式

对偶形式的基本想法是将 $\omega$ 和 $b$ 表示为实例 $x_i$ 和标记 $y_i$ 的线性组合的形式，通过求解其系数而求得 $\omega$ 和 $b$ 。对于原始形式中的算法， $\omega,b$ 关于 $(x_i,y_i)$ 的增量分别是 $\alpha_i y_i x_i$ 和 $\alpha_i y_i$ ，其中 $\alpha_i = \eta n_i$ ， $n_i$ 是点 $(x_i,y_i)$ 由于误分类而进行更新的次数。故最后学习到的参数为

$\omega = \sum_{i=1}^N \alpha_i y_i x_i$

$b = \sum_{i=1}^N \alpha_i y_i$

在感知机学习算法的对偶形式中，输出的感知机模型 $f(x) = sign \left( \sum_{j=1}^N \alpha_j y_j x_j \cdot x +b \right)$ ，其中 $\alpha = (\alpha_1,\alpha_2,\dots,\alpha_N)^T$ 。感知机学习算法的对偶形式算法如下：

(1) $\alpha \leftarrow 0, b \leftarrow 0$

(2) 在训练数据集中选取数据 $(x_i,y_i)$

(3) 如果 $y_i \left( \sum_{j=1}^N \alpha_j y_j x_j \cdot x_i +b \right) \leq 0$ ，则

$\alpha_i \leftarrow \alpha_i + \eta$

$b \leftarrow b + \eta y_i$

(4) 转至(2)直到没有误分类数据

第3章 k近邻法

3.2 k近邻模型

模型

特征空间中，对每个训练实例点 $x_i$ ，距离该点比其他点更近的所有点组成一个区域，叫作单元(cell)。

距离度量

设特征空间 $\mathcal{X}$ 是n维实数向量空间 $\mathbb{R}^n$ ， $x_i,x_j \in \mathcal{X}$ ， $x_i = (x_i^{(1)},x_i^{(2)},\dots,x_i^{(n)})^T$ ， $x_i,x_j$ 的 $L_p$ 距离或Minkowski距离定义为：

$L_p(x_i,x_j) = \left(\sum_{i=1}^n |x_i^{(l)}-x_j^{(l)}|^p \right)^{\frac{1}{p}}$

* $$p=1$$时，曼哈顿距离(Manhattan distance)
* $$p=2$$时，欧氏距离(Euclidean distance)
* $$p=\infty$$时，表示各个坐标的最大值

k值的选择

选择较小的k值：近似误差(approximation error)会减小，估计误差(estimation error)会增大
选择较大的k值：估计误差小，近似误差大

3.3 k近邻的实现：kd树

kd树是二叉树，表示对k维空间的一个划分。利用kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量。

构造平衡kd树算法：

输入：k维空间数据集 $T=\{x_1,x_2,\dots,x_N\}$ ， $x_i = (x_i^{(1)},x_i^{(2)},\dots,x_i^{(k)})^T$ ， $i=1,2,\dots,N$

输出：kd树

(1) 开始：构造根结点，根结点对应于包含T的k维空间的超矩阵区域。

选择 $x^{(1)}$ 为坐标轴，以T中所有实例的 $x^{(1)}$ 坐标的中位数为切分点，将根结点对应的超矩阵区域切分为两个子区域。切分由通过切分点并与坐标轴 $x^{(1)}$ 垂直的超平面实现。

由根结点生成深度为1的左、右子结点：左子结点对应坐标 $x^{(1)}$ 小于切分点的子区域，右子结点对应于坐标 $x^{(1)}$ 大于切分点的子区域。

(2) 重复：对深度为j的结点，选择 $x^{(l)}$ 为切分的坐标轴， $l = j(mod \; k)+1$ ，以该结点的区域中所有实例的 $x^{(l)}$ 坐标的中位数为切分点，将该结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴 $x^{(l)}$ 垂直的超平面实现。

将落在切分超平面上的实例点保存在该结点。

(3) 直到两个子区域没有实例存在时停止，从而形成kd树的区域划分。

用kd树的最近邻搜索： $O(\log N)$

输入：已构造的kd树，目标点x

输出：x的最近邻

(1) 在kd树中找出包含目标点x的叶结点；从根结点出发，递归地向下访问kd树。若目标点x当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点。直到子结点为叶结点为止。

(2) 以此叶结点为“当前最近点”

(3) 递归地向上回退，在每个节点进行以下操作：

(a) 如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”。

(b) 当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点的父结点的另一个子结点对应的区域是否有更近的点。具体地，检查[其兄弟结点对应的区域]是否与[以目标点为球心、以目标点到“当前最近点”间的距离为半径的超球体]相交：

            * 如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点。接着递归地进行最近邻搜索；
            * 如果不想交，向上回退。

(4) 当回退到根结点时，搜索结束。最后的“当前最近点”即为x的最近邻点。

第4章朴素贝叶斯法

4.1 朴素贝叶斯法的学习与分类

基本假设：

所有特征条件独立，即

$P(X^{(1)}=x^{(1)},X^{(2)}=x^{(2)},\dots,X^{(n)}=x^{(n)}|Y=c_k) = \prod_{j=1}^{n} P(X^{(j)}=x^{(j)}|Y=c_k)$

基本思路：

通过训练数据集联合概率分布 $P(X,Y)$ ，学习先验概率 $P(Y=c_k)$ 和 $P(X=x|Y=c_k)$ ，后经过贝叶斯定理计算后验概率 $P(Y=c_k|X=x)$ 。

推导过程：

根据贝叶斯定理，有后验概率

$\begin{aligned}P(Y=c_k|X=x) &= \dfrac{P(X=x|Y=c_k) P(Y=c_k)}{\sum_{k'} \left[ P(X=x|Y=c_{k'}) P(Y=c_{k'}) \right] } \\&= \dfrac{P(Y=c_k) \left[ \prod_j P(X^{(j)}=x^{(j)}|Y=c_k) \right] }{\sum_{k'} \left[ P(Y=c_{k'}) \prod_j P(X^{(j)}=x^{(j)}|Y=c_k) \right] }\end{aligned}$

于是朴素贝叶斯分类器可表示为

$\begin{aligned}y=f(x)&=\arg\max_{c_k} P(Y=c_k|X=x) \\&= \arg\max_{c_k} \dfrac{P(Y=c_k) \left[ \prod_j P(X^{(j)}=x^{(j)}|Y=c_k) \right] }{\sum_{k'} \left[ P(Y=c_{k'}) \prod_j P(X^{(j)}=x^{(j)}|Y=c_k) \right] }\end{aligned}$

由于对任意一个类别 $c_k$ ，上式分母均相同，故可省略，即

$y = \arg\max_{c_k} \left[P(Y=c_k) \left( \prod_j P(X^{(j)}=x^{(j)}|Y=c_k) \right)\right]$

后验概率最大化的含义：

朴素贝叶斯法将实例分到后验概率最大的类别中，等价于选择0-1损失函数作为损失函数时的期望风险最小化。

【证明】已知0-1损失函数：

$L(X,f(X)) = \begin{cases}1, & Y\neq f(X)\\0, & Y = f(X)\end{cases}$

此时，期望风险函数为

$\begin{aligned}R_{exp}(f) &= E[L(X,f(X))] \\ &= E_X \left[ \sum_{i=1}^K L[c_k,f(X)] P(c_k|X) \right]\end{aligned}$

为了使期望风险最小化，只需对 $X=x$ 逐个极小化，由此得到：

$\begin{aligned}f(x) =\arg\min_{y\in\mathcal{Y}} R_{exp}(f) &= \arg\min_{y\in\mathcal{Y}} \left( \sum_{k=1}^K L(c_k,y) P(c_k|X=x) \right) \\ &= \arg\min_{y\in\mathcal{Y}} \sum_{k=1}^K P(y\neq c_k|X=x) \\&= \arg\min_{y\in\mathcal{Y}} \left[ 1- P(y=c_k|X=x) \right] \\&= \arg\max_{y\in\mathcal{Y}} P(y=c_k|X=x) \\&= \arg\max_{c_k} P(c_k|X=x)\end{aligned}$

4.2 朴素贝叶斯法的参数估计

即求先验概率 $P(Y=c_k)$ 和 $P(X=x|Y=c_k)$ 。

极大似然估计

$P(Y=c_k) = \dfrac{\sum_{i=1}^N \mathbb{I}(y_i=c_k)}{N}$

$P(X^{(j)}=a_{jl} | Y=c_k) = \dfrac{\sum_{i=1}^N \mathbb{I}(x_i^{(j)}=a_{jl},y_i=c_k)}{\sum_{i=1}^N \mathbb{I}(y_i=c_k)}$

贝叶斯估计

用极大似然估计可能会出现所要估计的概率值为0的情况，影响到后验概率的计算结果，使分类产生偏差。解决这一问题的方法是采用贝叶斯估计：

$P_{\lambda}(Y=c_k) = \dfrac{\sum_{i=1}^N \mathbb{I}(y_i=c_k)+\lambda}{N+K\lambda}$

$P_{\lambda}(X^{(j)}=a_{jl} | Y=c_k) = \dfrac{\sum_{i=1}^N \mathbb{I}(x_i^{(j)}=a_{jl},y_i=c_k) + \lambda}{\sum_{i=1}^N \mathbb{I}(y_i=c_k)+ S_j\lambda}$

上式中 $\lambda\geq 0$ 。等价于在随机变量各个取值的频数上赋予一个正数 $\lambda > 0$ 。当 $\lambda = 0$ 时就是极大似然估计。常取 $\lambda = 1$ ，这时称为拉普拉斯平滑(Laplacian smoothing)。显然，对任何l和k，有 $P_{\lambda} > 0$ 和 $\sum P_{\lambda} = 1$ 。

最后编辑于：2021.05.20 20:10:20

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