统计学习方法

第一版

第二版

第 1 章 统计学习及监督学习概论

统计学习的主要特点是

  1. 统计学习以计算机及网络为平台,是建立在计算机及网络之上的;
  2. 统计学习以数据为研究对象,是数据驱动的学科;
  3. 统计学习的目的是对数据进行预测与分析;
  4. 统计学习以方法为中心,统计学习方法构建模型并应用模型进行预测与分析;
  5. 统计学习是概率论、统计学、信息论、计算理论、最优化理论及计算机科学等多个领域的交叉学科,并且在发展中逐步形成独自的理论体系与方法论。

假设空间(hypothesis space)
H={f(x;θ)θRD}orF={PP(YX;θ),θRD}\mathcal H = \{ f(x;\theta) | \theta \in \mathbb{R}^D\} \\ or \quad \mathcal F = \{P|P(Y|X;\theta),\theta \in \mathbb{R}^D\}
其中f(x;θ)f(x; \theta)是参数为θ\theta 的函数(决策函数),也称为模型(Model),参数向量θ\theta取值与DD维欧式空间RD\mathbb{R}^D,也称为参数空间(parameter space),DD 为参数的数量(维度)

模型的假设空间(hypothesis space)包含所有可能的条件概率分布或决策函数

特征空间(feature space)
每个具体的输入是一个实例(instance),通常由特征向量(feature vector)表示。这
时,所有特征向量存在的空间称为特征空间(feature space)。特征空间的每一维对应于
一个特征。

输入空间中的一个输入向量x=(x1,x2)x = (x_1,x_2),在多项式模型中特征向量是(x12,x1x2,x22,...x_1^2,x_1x_2,x_2^2,...)
一般说的线性模型,指的是特征向量的线性组合,而不是指输入向量,所以说模型都是定义在特征空间上的

统计学习的三要素

  1. 模型的假设空间(hypothesis space),简称:模型(model)。假设空间即我们对模型形式的先验假设,最终我们求得的模型必定符合我们对模型形式的先验假设。
  2. 模型选择的准则(evaluation criterion),简称:策略(strategy)或者学习准则。即我们用什么标准来评价一个模型的好坏。策略决定了我们从假设空间中选择模型的偏好。
  3. 模型学习的算法(algorithm),简称:算法(algorithm)。优化算法指的是通过什么样的方式调整我们的模型结构或模型超参数取值,使得模型的目标函数取值不断降低。优化算法决定了我们用什么样的步骤在假设空间中寻找合适的模型。

以线性回归(Linear Regression)为例:
模型: f(x;w,b)=wTx+bf(x;w,b) = w^Tx +b
策略(strategy)或者学习准则: 平方损失函数 L(y,y^)=(yf(x,θ))2\mathcal L(y,\hat{y}) = (y-f(x,\theta))^2
算法:解析解 analytical solution(闭式解 closed-form solution)和数值解 numerical solution,如:closed-form 的最小二乘的解以及梯度下降法

机器学习的定义

graph LR; F(["未知的目标函数(理想中完美的函数):𝑓: 𝒙⟶𝑦"])-->D["训练样本D:{(𝒙¹,𝑦¹),...,(𝒙ⁿ,𝑦ⁿ)}"]; D-->A{{"算法"}} H{{"假设空间"}}-->A A-->G["模型 g≈f"]

使用训练数据来计算接近目标 𝑓 的假设(hypothesis )g (来自:Machine Learning Foundations(机器学习基石)- the learning problem,25 页

监督学习
监督学习(supervised learning)是指从标注数据中学习预测模型的机器学习问题。本质是学习输入到输出的映射的统计规律

输入变量与输出变量均为连续变量的预测问题称为回归问题
输出变量为有限个离散变量的预测问题称为分类问题
输入变量与输出变量均为变量序列的预测问题称为标注问题(分类问题的推广,如:隐马尔可夫模型 HMM,条件随机场 CRF)。

监督学习的模型可以是概率模型或非概率模型,由条件概率分布P(YX)P(Y|X)决策函数(decision function)Y=f(X)Y=f(X)表示,随具体学习方法而定。对具体的输入进行相应的输出预测时,写作P(yx)P(y|x)Y=f(x)Y=f(x)
y=arg maxyP(yx)y =\displaystyle\argmax_{y} P(y|x)

联合概率分布
监督学习假设输入与输出的随机变量 X 和 Y 遵循联合概率分布P(X,Y)P(X,Y)P(X,Y)P(X,Y)表示分布函数,或分布密度函数。注意,在学习过程中,假定这一联合概率分布存在,但对学习系统来说,联合概率分布的具体定义是未知的。训练数据与测试数据被看作是依联合概率分布P(X,Y)P(X,Y)独立同分布产生的
统计学习假设数据存在一定的统计规律,XXYY具有联合概率分布的假设就是监督学习关于数据的基本假设。

非监督学习
非监督学习(unsupervised learning)是指从无标注数据中学习预测模型的机器学习问题。本质是学习数据中的统计规律或潜在结构

非监督学习的模型可以表示为函数z=g(x)z = g(x)或者条件概率分布P(zx)P(z|x) (输出zz可以是聚类或者降维
z=arg maxzP(zx)z =\displaystyle\argmax_{z} P(z|x)
以及 条件概率分布P(xz)P(x|z) (用来做概率密度估计,比如 GMM 中P(xz)P(x|z)属于高斯分布,如果假设知道数据来自哪个高斯分布,即知道zz,我们可以用极大似然估计来估计相关参数)。

核密度估计 Kernel Density Estimation. - 应用密度估计检测离群值(outlier)的LocalOutlierFactor

概率模型(probabilistic model)与非概率模型(non-probabilistic model)或者确定性模型(deterministic model)

概率模型(probabilistic model)- 条件概率分布 P(y|x)和 非概率模型(non-probabilistic model) - 函数 y=f(x)可以相互转化,条件概率分布最大化后得到函数,函数归一化后得到条件概率分布。所以概率模型与非概率模型的区别不在于输入输出之间的映射关系,而在于模型的内部结构:概率模型一定可以表示为联合概率分布的形式,而非概率模型则不一定存在这样的联合概率分布。

概率模型的代表是概率图模型(probabilistic graphical model)参考文献[13]^{参考文献[1-3]},联合概率分布可以根据图的结构分解为因子乘积的形式,可以用最基本的加法规则和乘法规则进行概率推理:
P(x)=yP(x,y)P(x,y)=P(x)P(yx)P(x) = \sum_yP(x,y) \\ P(x,y) = P(x)P(y|x)

参数化模型(parametric model)和非参数化模型(non-parametric model)

参数化模型假设模型参数的维度固定,模型可以由有限维参数完全刻画,不随数据点的变化而变化。(如:感知机、GMM、logistic regression、朴素贝叶斯、k 均值聚类、潜在语义分析、概率潜在语义分析、潜在狄利克雷分配)
非参数化模型假设模型参数的唯独不固定或者说无穷大,随着训练数据量的增加而不断增大。(如:决策树、支持向量机、AdaBoost、k 近邻)

非参数化模型意味着决策树没有假设空间分布和分类器结构?

在线学习(online learning)和批量学习(batch learning)

在线学习每次接受一个样本,预测后学习模型,并不断重复该操作。
批量学习一次接受所有数据,学习模型之后进行预测。

在线学习比批量学习更难,因为每次模型更新中可利用的数据有限。

贝叶斯学习(Bayesian learning)/ 贝叶斯推理(Bayesian inference)
Bayes  Rule:P(XY)posterior=P(YX)likelihoodP(X)priorP(Y)evidence=P(YX)likelihoodP(X)priorxP(YX)P(X)evidence\mathrm{Bayes \; Rule:} \\ \underbrace{P(X|Y)}_{\mathrm{posterior}} = \frac{\overbrace{P(Y|X)}^{\mathrm{likelihood}}\overbrace{P(X)}^{\mathrm{prior}}}{\underbrace{P(Y)}_{\mathrm{evidence}}} = \frac{\overbrace{P(Y|X)}^{\mathrm{likelihood}}\overbrace{P(X)}^{\mathrm{prior}}}{\underbrace{\sum_{x}P(Y|X)P(X)}_{\mathrm{evidence}}}

核技巧(kernel trick)/ 核方法(kernel method)

核方法是一类把低维空间的非线性可分问题,转化为高维空间的线性可分问题的方法。
核技巧是一种利用核函数直接计算 ϕ(x),ϕ(z)\lang \phi(x),\phi(z) \rang ,以避开分别计算 ϕ(x)\phi(x)ϕ(z)\phi(z) ,从而加速核方法计算的技巧。

核函数Kernel function
X\mathcal X 是输入空间(即 xiXx_i \in \mathcal XX\mathcal XRn\mathbb R^n 的子集或离散集合 ),又设 H\mathcal H 为特征空间(​ 希尔伯特空间附加知识:各种空间介绍^{附加知识:各种空间介绍}),如果存在一个从 X\mathcal XH\mathcal H 的映射

ϕ(x):XH\phi(x) : \mathcal X \to \mathcal H

使得对所有 x,zXx,z \in \mathcal X ,函数 K(x,z)K(x,z) 满足条件

K(x,z)=ϕ(x).ϕ(z)=ϕ(x),ϕ(z)K(x,z) = \phi(x).\phi(z) = \lang \phi(x),\phi(z) \rang

则称 K(x,z)K(x,z) 为核函数。其中 ϕ(x)\phi(x) 为映射函数, ϕ(x),ϕ(z)\lang \phi(x),\phi(z) \rang 为内积。

核技巧的想法是,在学习和预测中只定义核函数 K(x,z)K(x,z) ,而不显式地定义映射函数 ϕ\phi。通常直接计算K(x,z)K(x,z)比较容易,而通过ϕ(x)\phi(x)ϕ(z)\phi(z)计算K(x,z)K(x,z)并不容易。

注意:ϕ\phi是输入空间Rn\mathbb{R}^n到特征空间H\mathcal H的映射,特征空间H\mathcal H一般是高维的,甚至是无穷维的。所以ϕ\phi不好计算,甚至会带来维度灾难又称维度诅咒(Curse of Dimensionality)附加知识:维度诅咒^{附加知识:维度诅咒}

附加知识

正则化

正则化符合奥卡姆剃刀(Occam's razor)原理。

参考:L1L2 正则化和凸优化

模型选择

参考:模型选择

生成模型和判别模型

参考:生成模型和判别模型

各种空间介绍

线性空间就是定义了加法和数乘的空间(空间里的一个元素就可以由其他元素线性表示)。


度量空间就是定义了距离的空间(曼哈顿距离,欧氏距离,闵可夫斯基距离,马氏距离,切比雪夫距离)。
定义距离时,有三条公理必须遵守:

  1. 非负性、同一性:dist(xi,xj)0dist(x_i,x_j) \geq 0(非负性),dist(xi,xj)=0dist(x_i,x_j) = 0当且仅当xi=xjx_i=x_j(同一性)
  2. 对称性:dist(xi,xj)=dist(xj,xi)dist(x_i,x_j) = dist(x_j,x_i)
  3. 三角不等式(也叫直递性):dist(xi,xj)dist(xi,xk)+dist(xk,xj)dist(x_i,x_j) \leq dist(x_i,x_k) + dist(x_k,x_j)
    希尔伯特空间(Hilbert)

    文字解释:【两点之间距离不为负;两个点只有在 空间 上重合才可能距离为零;a 到 b 的距离等于 b 到 a 的距离;a 到 c 的距离加上 c 到 b 的距离大于等于 a 直接到 b 的距离;】


赋范空间就是定义了范数的空间。
x 的范数||x||就是 x 的长度。那么这里的长度和上一节中说的距离到底有什么区别呢。距离的概念是针对两个元素来说的,例如 d(x,y)指的是 x 与 y 两个元素之间的距离,而范数是针对一个元素来说的,每一个元素都对应一个范数,可以将范数理解为一个元素到零点的距离(这只是一种理解,并不是定义),也就是它自己的长度。
定义:
称 映射.:RnR||.|| : \mathbb{R}^n \to \mathbb{R}Rn\mathbb{R}^n 上的范数,当且仅当:

  1. 非负性: xRn,x0\forall x \in \mathbb{R}^n ,||x|| \geq 0 ,x=0||x|| = 0当且仅当x=0x=0
  2. 数乘:xRn,aRn,ax=a.x\forall x \in \mathbb{R}^n ,a \in \mathbb{R}^n, ||ax|| = |a|.||x||
  3. 三角不等式: x,yRn,x+yx+y\forall x,y \in \mathbb{R}^n ,||x+y|| \leq ||x|| + ||y||

如果我们定义了范数,可以在这基础上定义距离:dist(x,y)=||x-y||。根据范数的三条性质,我们可以证明我们这样定义的距离也满足距离的定义,聪明的你可以自己证明一下(对称性的证明,提一个-1 出来,一加绝对值就是 1 了)。

也就是说范数其实是一个更加具体的概念,有了范数一定能利用范数定义距离,但是有距离不能定义范数

也许你会问,你不是说理解范数就是一个元素到零点的距离吗,那定义范数为||x||=dist(x,0) 不就行了吗。这样的话,对于范数的第二条性质就不一定会满足,||ax||=dist(ax,0),而 dist(ax,0)不一定等于|a|dist(x,0),具体等不等于还要看你的距离是怎么定义的。

例如:Lp范数
欧式距离对应 L2 范数
曼哈顿距离对应 L1 范数
切比雪夫距离对应 L∞ 范数
Lp范数:当 p>=1 时,向量的 Lp范数是凸的。(这也是为什么一般不用 L0 范数的原因之一)


线性赋范空间就是定义了加法、数乘和范数的空间。


巴拿赫空间就是完备的赋范线性空间。(Banach space)
完备的空间的定义:如果一个空间是完备的,那么该空间中的任何一个柯西序列都收敛在该空间之内。

首先来说一下柯西序列是什么,柯西序列就是随着序数增加,值之间的距离越来越小的序列。换一种说法是,柯西序列可以在去掉有限个值之后,使任意两个值之间的距离\underline{\mathrm{距离}}都小于任意给定正常数(其实这就是定义了一个极限而已)。

那么任意一个柯西序列都收敛在该空间内是什么意思呢,举个例子你就明白了。

设定义在有理数空间 Q 上的序列:xn=[2n]nx_n = \frac{[\sqrt{2}n]}{n},其中[x]表示 x 取整数部分。
对于这个数列来说,每一个元素的分子分母都是整数,所以每一个xnx_n都在有理数空间 Q 上,那这个序列的极限呢,稍有常识的人都能看出,这个序列的极限是2\sqrt{2},而这并不是一个有理数,所以这个柯西序列的极限不在该空间里面,也就是说有理数空间 Q 是不完备的。

所以完备的意义我们可以这样理解,那就是在一个空间上我们定义了极限,但是不论你怎么取极限,它的极限的值都不会跑出这个空间,那么这个空间就是完备空间

另外,不知道你有没有发现,上面在解释什么是柯西序列的时候,有一个词我加了下划线,那就是距离,也就说说在定义完备空间之前,要先有距离的概念。所以完备空间,其实也是完备度量空间

所以,巴拿赫空间满足几条特性呢:距离、范数、完备。


内积空间就是定义了内积的空间。Inner product space
有时也称准希尔伯特空间。
内积就是我们所说的点乘、标积,它的定义方式也不是唯一的,但如同距离范数的定义一样,内积的定义也要满足某些条件,不能随便定义。

定义映射.,.:V×VF\lang .,. \rang : V \times V \to \mathbb{F}, 其中VV是向量,F\mathbb{F}是标量
x,y,zV,sFx,y,z \in V ,s \in \mathbb{F},那么内积满足

  1. 第一个参数中的线性:
    sx,y=sx,yx+y,z=x,z+y,z0,x=0\lang sx,y \rang = s\lang x,y \rang \\ \lang x+y,z \rang = \lang x,z \rang + \lang y,z \rang \\ \lang 0,x \rang = 0

  2. 共轭对称:x,y=y,x\lang x,y \rang = \overline{\lang y,x \rang }

  3. 正定性:x,x>0if  x0\lang x,x \rang > 0 \quad\mathrm{if}\; x \neq 0

  4. 正半定性或非负定性:x,x,x0\forall{x}, \lang x,x \rang \geq 0

  5. 确定性:x,x=0必然有x=0\lang x,x \rang = 0 必然有 x=0

3,4,5 可以跟上面定义范数和距离一样写成一个

例子-欧几里得向量空间:
x,yRn,x,y=xTy=_i=1nxiyix,y \in \mathbb{R}^n , \lang x,y \rang = x^Ty=\sum\_{i=1}^n{x_iy_i}

只有定义了内积,才会有夹角的概念,才会有正交的概念,另外内积也可以定义范数,也就是说内积是比范数更具体的一个概念。


欧式空间就是定义了内积的有限维实线性空间。


希尔伯特空间就是完备的内积空间。(Hilbert space)
希尔伯特空间中的元素一般是函数,因为一个函数可以视为一个无穷维的向量。

graph LR; LS(("Linear Space"))-->NLS(("Normed Linear Space")); NLS-->BS(("Banach Space")) NLS-->IPS(("Inner Product Space")) IPS-->HS(("Hilbert Space")) IPS-->ES(("Euclid Space"))

参考:一片文章带你理解再生核希尔伯特空间(RKHS)以及各种空间

维度诅咒

维度诅咒通常是指在涉及到向量的计算的问题中,随着维数的增加,计算量呈指数倍增长的一种现象。高维度有更大的特征空间,需要更多的数据才可以进行较准确的估计。

若特征是二值的,则每增加一个特征,所需数据量都在以 2 的指数级进行增长,更何况很多特征不只是二值的。

几何角度 1:

background Layer 1 0.5

上图表示一个多维空间(以二维为例),设正方形边长为 1,则其内切圆半径为r=0.5r=0.5,则正方形面积为 1,内切圆面积为π(0.5)2\pi(0.5)^2 。若将此变为三维情况下,正方体体积为 1,内切球体积为43π(0.5)3\frac{4}{3}\pi(0.5)^3

因此球体的体积可以表示为V(d)=πd/2Γ(d2+1)0.5d=k(0.5)dV(d) = \frac{\pi^{d/2}}{\varGamma(\frac{d}{2}+1)}0.5^d = k(0.5)^d(d 为维度),则 limdk(0.5)d=0\lim_{d \to \infty}k(0.5)^d = 0,其内切超球体的体积为 0。由此可知,高维情况下,数据大都分布在四角(正方形内,内切圆外),稀疏性太大,不好分类。

维度越大,超球体体积越小。说明落在超球体内的样本越少,因为超球体是超立方体的内切球。不在球内,那只能在角落!

几何角度 2:

background Layer 1

上图也表示一个多维空间(以二维为例),则其中图形的体积有如下关系:外圆半径r=1r=1,内圆半径为rεr−\varepsilon 。同样在高维情况下,外圆体积为V外圆=k.1d=kV_{外圆} = k.1^d = k,中间的圆环体积为V圆环=kk(1ε)dV_{圆环} = k - k(1-\varepsilon)^d,则:
limdV圆环V外圆=limdkk(1ε)dk=limd(1(1ε)d)=1\lim_{d \to \infty}\frac{V_{圆环}}{V_{外圆}} = \lim_{d \to \infty}\frac{ k - k(1-\varepsilon)^d}{k} = \lim_{d \to \infty}(1-(1-\varepsilon)^d) = 1

高维情况下,无论ε\varepsilon多小,只要 d 足够大,圆环几乎占据了整个外圆,内圆体积趋向于 0,导致数据稀疏

参考:
The Curse of Dimensionality in classification
机器学习-白板推导系列(五)-降维(Dimensionality Reduction)

不等式(Inequality)

所有不等式 以及所有概率(Probabilistic)不等式

由 KL divergence 就能证明
DKL(PQ)i=1npilogpiqi0.{\displaystyle D_{\mathrm {KL} }(P\|Q)\equiv \sum _{i=1}^{n}p_{i}\log {\frac {p_{i}}{q_{i}}}\geq 0.}

概率不等式 Probabilistic inequalities

参考:初等数学学习笔记

参考文献

[1-1] Hastie T,Tibshirani R,Friedman J. The Elements of Statistical Learning: DataMining,Inference,and Prediction. Springer. 2001(中译本:统计学习基础——数据挖掘、推理与预测。范明,柴玉梅,昝红英等译。北京:电子工业出版社,2004)

[1-2] Bishop M. Pattern Recognition and Machine Learning. Springer,2006

[1-3] Probabilistic Graphical Models: Principles and Techniques by Daphne Koller, Nir Friedman from The MIT Press

[1-4] Deep Learning (Ian Goodfellow, Yoshua Bengio, Aaron Courville)

[1-5] Tom M Michelle. Machine Learning. McGraw-Hill Companies,Inc. 1997(中译本:机器学习。北京:机械工业出版社,2003)

[1-6] Bayesian Reasoning and Machine Learning by David Barber 2007–2020 ,other version

[1-7] Reinforcement Learning:An Introduction (second edition 2020) by Richard S. Sutton and Andrew G. Barto ,other version

[1-8] 周志华,机器学习,清华大学出版社 (手推笔记 以及 公式推导解析)

[1-9] Lecture Notes in MACHINE LEARNING Dr V N Krishnachandran

第 2 章 感知机

判别模型

感知机Perceptron神经网络支持向量机的基础。最早在 1957 年由 Rosenblatt 提出参考文献[21]^{参考文献[2-1]}。Novikoff参考文献[22]^{参考文献[2-2]},Minsky 与 Papert参考文献[23]^{参考文献[2-3]}等人对感知机进行了一系列理论研究。感知机的扩展学习方法包括口袋算法(pocket algorithm)参考文献[24]^{参考文献[2-4]}、表决感知机(voted perceptron)参考文献[25]^{参考文献[2-5]}、带边缘感知机(perceptron with margin)参考文献[26]^{参考文献[2-6]}等。
Brief History of Machine Learning

要求:数据集线性可分(linearly separable data set)

感知机是一种线性分类模型,属于判别模型。感知机模型的假设空间是定义在特征空 间中的所有线性分类模型(linear classification model)或线性分类器(linear classifier),即 函数集合{ff(x)wx+b}\{f|f(x)=w·x+b\}

超平面 S:w.x+b=0w.x+b = 0,其中ww是 S 的法向量,bb是 S 的截距,超平面 S 称为分离超平面(separating hyperplane)

函数间隔:y(w.x+b)y(w.x + b)
几何间隔:1ww.x+b\frac{1}{||w||}|w.x + b| (在上面的 loss function 中没有考虑1w\frac{1}{||w||})

  1. 初始化参数(随机法):w0,b0w_0,b_0
  2. 选取数据(xi,yi)(x_i,y_i)
  3. 如果(xi,yi)(x_i,y_i)是误分类点,也就是yi(w.xi+b)0y_i(w.x_i + b) \leq 0,则对w,bw,b进行更新
    (xi,yi)点处梯度为:wL(w,b)=yixibL(w,b)=yi更新wwk+1wk+ηyixi更新bbk+1bk+ηyi其中学习率η(0,1]在(x_i,y_i)点处梯度为:\\ \nabla_wL(w,b) = -y_ix_i \\ \nabla_bL(w,b) = -y_i\\ 更新w:w_{k+1} \gets w_{k}+\eta y_ix_i \\ 更新b:b_{k+1} \gets b_{k}+\eta y_i \\其中学习率\eta \in (0,1]
  4. 循环 2-3,直到训练集中没有误分类点。

Novikoff 定理:
设训练集T={(x1,y1),...,(xN,yN)}T = \{(x_1,y_1),...,(x_N,y_N)\}是线性可分的,

  1. 设完美超平面w^opt.x^=0,w^opt=1\hat{w}_{opt}.\hat{x} = 0 , ||\hat{w}_{opt}||=1 将训练集完全正确分开(简化起见 w^opt.x^=wopt.x+b\hat{w}_{opt}.\hat{x} = w_{opt}.x +b),存在γ>0\gamma >0 ,对所有点有yi(w^opt.xi^)γy_i(\hat{w}_{opt}.\hat{x_i}) \geq \gamma

  2. R=max1iNxi^R = \max_{1\leq i\leq N}||\hat{x_i}||,则算法会在有限步 k 满足不等式k(Rγ)2k \leq (\frac{R}{\gamma})^2

证明(注意:带 hat 的表示扩充向量):

  1. 因为数据线性可分,对于所有点yi(w^opt.xi^)>0y_i(\hat{w}_{opt}.\hat{x_i}) > 0,所以存在
    γ=miniyi(w^opt.xi^)yi(w^opt.xi^)(2-1)\gamma = \min_i{y_i(\hat{w}_{opt}.\hat{x_i})} \leq {y_i(\hat{w}_{opt}.\hat{x_i})} \label{2-1}\tag{2-1}
    所以这里的γ\gamma代表了所有点离完美超平面的最小距离;

  2. 为了方便计算 设 扩充向量w^=(wT,b)T\hat{w} = (w^T,b)^T, 有
    w^k=w^k1+ηyixi^(2-2)\hat{w}_{k} = \hat{w}_{k-1}+\eta y_i\hat{x_i} \label{2-2}\tag{2-2}

  3. 推导不等式
    w^k.w^optkηγ(2-3)\hat{w}_{k}.\hat{w}_{opt} \geq k\eta\gamma \label{2-3}\tag{2-3}

(2-1)\eqref{2-1}(2-2)\eqref{2-2}
w^k.w^opt=w^k1.w^opt+ηyiw^opt.xi^w^k1.w^opt+ηγw^k2.w^opt+2ηγkηγ\hat{w}_{k}.\hat{w}_{opt} = \hat{w}_{k-1}.\hat{w}_{opt} + \eta{y_i}\hat{w}_{opt}.\hat{x_i} \\ \geq \hat{w}_{k-1}.\hat{w}_{opt} + \eta\gamma \\ \geq \hat{w}_{k-2}.\hat{w}_{opt} + 2\eta\gamma \\ \geq k\eta\gamma

  1. 推导不等式
    w^k2kη2R2(2-4)||\hat{w}_{k}||^2 \leq k\eta^2R^2 \label{2-4}\tag{2-4}
    (2-2)\eqref{2-2}
    w^k2=w^k1+ηyixi^2=w^k12+2ηyiw^k1.x^i+η2x^i2||\hat{w}_{k}||^2=||\hat{w}_{k-1}+\eta y_i\hat{x_i}||^2 = ||\hat{w}_{k-1}||^2 + 2\eta{y_i}\hat{w}_{k-1}.\hat{x}_{i} + \eta^2||\hat{x}_{i}||^2
    假设 k 次完全分对,那么 k-1 次有误分类点,则yiw^k1.x^i0{y_i}\hat{w}_{k-1}.\hat{x}_{i} \leq 0
    所以
    w^k2=w^k12+2ηyiw^k1.x^i+η2x^i2w^k12+η2x^i2w^k12+η2R2w^k22+2η2R2...kη2R2||\hat{w}_{k}||^2 =||\hat{w}_{k-1}||^2 + 2\eta{y_i}\hat{w}_{k-1}.\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-1}||^2 + \eta^2R^2 \\ \leq ||\hat{w}_{k-2}||^2 + 2\eta^2R^2 \leq ... \\ \leq k\eta^2R^2

  2. (2-3)\eqref{2-3}(2-4)\eqref{2-4}

kηγw^k.w^optw^k.w^opt=1柯西-施瓦茨 (Cauchy–Schwarz) 不等式kηR  k2γ2kR2k(Rγ)2k\eta\gamma \leq \underbrace{\hat{w}_{k}.\hat{w}_{opt} \leq ||\hat{w}_{k}||.\underbrace{||\hat{w}_{opt}||}_{=1} }_{\text{柯西-施瓦茨 (Cauchy–Schwarz) 不等式}} \leq \sqrt{k} \eta R \\ \; \\ \Rightarrow k^2\gamma^2 \leq kR^2 \\ \Rightarrow k \leq (\frac{R}{\gamma})^2

也就是说 k 是有上界的。

书中还介绍了原形式的对偶形式,也就是等价形式(SVM 中 7.2.2 节 127 页也是等价的意思,区别于拉格朗日对偶),这两个地方的等价都是经过基本推导,求出 w 参数,然后对原问题进行了替换。

参考文献

[2-1] Rosenblatt, F. (1958). The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65(6), 386–408.

[2-2] Novikoff, A. B. (1962). On convergence proofs on perceptrons. Symposium on the Mathematical Theory of Automata, 12, 615-622. Polytechnic Institute of Brooklyn.

[2-3] Minsky M L and Papert S A 1969 Perceptrons (Cambridge, MA: MIT Press)

[2-4] Gallant, S. I. (1990). Perceptron-based learning algorithms. IEEE Transactions on Neural Networks, vol. 1, no. 2, pp. 179-191.

[2-5] Freund, Y. and Schapire, R. E. 1998. Large margin classification using the perceptron algorithm. In Proceedings of the 11th Annual Conference on Computational Learning Theory (COLT' 98). ACM Press.

[2-6] Li YY,Zaragoza H,Herbrich R,Shawe-Taylor J,Kandola J. The Perceptron algorithmwith uneven margins. In: Proceedings of the 19th International Conference on MachineLearning. 2002,379–386

[2-7] Widrow, B., Lehr, M.A., "30 years of Adaptive Neural Networks: Perceptron, Madaline, and Backpropagation," Proc. IEEE, vol 78, no 9, pp. 1415-1442, (1990)。

[2-8] Cristianini N,Shawe-Taylor J. An Introduction to Support Vector Machines and OtherKernelbased Learning Methods. Cambridge University Press,2000

第 3 章 k 近邻法

判别模型

k 近邻法(k-nearest neighbor,k-NN)1968 年由 Cover 和 Hart 提出,是一种基本分类与回归方法。本书只讨论分类问题中的 k 近邻法。
k 值的选择、距离度量及分类决策规则是 k 近邻法的三个基本要素。
最后讲述 k 近邻法的一个实现方法——kd 树,介绍构造 kd 树和搜索 kd 树的算法

k 近邻法的三个基本要素
k 值的选择:超参数,可以使用交叉验证法来选取最优 k 值
距离度量:L2L_2距离/欧氏距离,LpL_p距离/Minkowski 距离
分类决策规则:多数表决(0-1 损失也就是指示函数)

附加知识

距离度量

Distance

sklearn.neighbors.DistanceMetric

Distance computations(scipy.spatial.distance)

24 种距离度量小结

先了解度量空间和赋范空间

实值向量空间的度量:

实值向量空间的度量(scipy):

整数值向量空间的度量:

布尔值向量空间的度量:

经纬度距离:

其它:

参考文献

[3-1] Cover T,Hart P. Nearest neighbor pattern classification. IEEE Transactions onInformation Theory,1967

[3-2] Hastie T,Tibshirani R,Friedman J. The Elements of Statistical Learning: DataMining,Inference,and Prediction,2001(中译本:统计学习基础——数据挖掘、推理与预测。范明,柴玉梅,昝红英等译。北京:电子工业出版社,2004)

[3-3] Friedman J. Flexible metric nearest neighbor classification. Technical Report,1994

[3-4] Weinberger KQ,Blitzer J,Saul LK. Distance metric learning for large margin nearestneighbor classification. In: Proceedings of the NIPS. 2005

[3-5] Samet H. The Design and Analysis of Spatial Data Structures. Reading,MA: Addison-Wesley,1990

第 4 章 朴素贝叶斯法

朴素贝叶斯(Naïve Bayes)法是基于贝叶斯定理特征条件独立假设(Naive 天真的)的分类方法。
对于给定的训练数据集,首先基于特征条件独立假设学习输入/输出的联合概率分布;然后基于此模型,对给定的输入 x,利用贝叶斯定理求出后验概率最大的输出 y。
朴素贝叶斯法实现简单,学习与预测的效率都很高,是一种常用的方法。并且支持 online learning(有 partial_fit 方法)。

朴素贝叶斯法是典型的生成学习方法。生成方法由训练数据学习联合概率分布 P(X,Y),然后求得后验概率分布 P(Y|X)。具体来说,利用训练数据学习 P(X|Y)和 P(Y)的估计,得到联合概率分布:P(X,Y)= P(Y)P(X|Y) ;概率估计方法可以是极大似然估计或贝叶斯估计。

贝叶斯定理(Bayes' theorem)
P(AB)=P(BA)P(A)P(B)P(A|B) = \frac{P(B|A)P(A)}{P(B)}

特征条件独立假设
条件独立
(ABC)    P(AB,C)=P(AC)(ABC)    P(A,BC)=P(AC)P(BC)(A\perp B|C) \iff P(A|B,C) = P(A|C) \\ (A\perp B|C) \iff P(A,B|C) = P(A|C)P(B|C)

特征条件独立假设就是已知 y 的情况下,x 中每个特征相互独立。

数据集T={(x1,y1),...,(xN,yN)}T = \{(x_1,y_1),...,(x_N,y_N)\}KK为类别个数,其中xix_i是 n 维向量xi=(xi(1),...,xi(n))Tx_i = (x_i^{(1)},...,x_i^{(n)})^T

附加知识

参数估计

参数估计(Parameter Estimation) 有点估计(point estimation)和区间估计(interval estimation)两种

点估计法:

共轭先验(Conjugate prior:如果先验分布 prior 和后验分布 posterior 属于同一分布簇,则 prior 称为 likehood 的共轭先验
likehood 为高斯分布,prior 为高斯分布,则 posterior 也为高斯分布。
likehood 为伯努利分布(二项式分布),prior 为 beta 分布,则 posterior 也为 beta 分布。
likehood 为多项式分布,prior 为 Dirichlet 分布(beta 分布的一个扩展),则 posterior 也为 Dirichlet(狄利克雷)分布。beta 分布可以看作是 dirichlet 分布的特殊情况。

最小二乘估计(Least squares estimation, LSE)

矩估计(Method of moments estimators)

区间估计法:
区间估计最流行的形式是置信区间 confidence intervals (一种频率论方法)和 可信区间 credible intervals(一种贝叶斯方法),此外还有预测区间(Prediction interval)等

采样法: 贝叶斯估计,近似推断
马尔可夫链蒙特卡罗法 Markov chain Monte Carlo, MCMC

参考文献

[4-1] Mitchell TM. Chapter 1: Generative and discriminative classifiers: Naïve Bayes andlogistic regression. In: Machine Learning. Draft,2005.

[4-2] Hastie T,Tibshirani R,Friedman J. The Elements of Statistical Learning. DataMining,Inference,and Prediction. Springer-Verlag,2001(中译本:统计学习基础——数据挖掘、推理与预测。范明,柴玉梅,昝红英等译。北京:电子工业出版社,2004)

[4-3] Bishop C. Pattern Recognition and Machine Learning,Springer,2006

第 5 章 决策树

判别模型

决策树(decision tree)是一种基本的分类与回归方法,具有良好的可解释性(可视化),通常包括 3 个步骤:特征选择、决策树的生成和决策树的修剪

特征选择
特征选择在于选取对训练数据具有分类能力的特征。(sklearn 中可以返回 feature_importances_特征重要性,属性越重要,特征空间划分的面积越大)

也就是计算每个特征的(信息增益,基尼指数)来选择特征(作为根节点)进行特征空间划分,注意:划分后再次计算每个特征的(信息增益,基尼指数),除非该特征所在的空间就只有一类了(也就是该特征不可分了,那么就直接生成叶子节点);

特征选择的准则:

决策树的生成
常见算法(参见:Decision tree learning以及Tree algorithms):

决策树的修剪 Decision tree pruning
修剪是机器学习和搜索算法中的一种数据压缩技术,它通过删除树中对分类实例不重要和冗余的部分来减小决策树的大小。剪枝降低了最终分类器的复杂度,从而通过减少过拟合来提高预测精度。

统计学习方法三要素:

Overview of Decision Trees

Decision Tree

Decision Trees

附加知识

信息论(Information Theory

Entropy, Relative Entropy, Cross Entropy

熵(Entropy

在信息论中,熵用来衡量一个随机事件的不确定性。也叫香农熵 Shannon's(人名) entropy。
H(X)=Ep(x)[I(X)]=Ep(x)[logp(x)]=i=1np(xi)logp(xi)=Xp(x)logp(x)dxH(X) = E_{p(x)}[I(X)] = E_{p(x)}[-\log {p(x)}] \\= -\sum_{i=1}^n {p(x_i)} \log {p(x_i)} \\= -\int_{X} {p(x)} \log {p(x)} dx
其中I(X)=logp(x)I(X) = -\log {p(x)} 称为自信息Self Information),是一个随机事件所包含的信息量。一个随机事件发生的概率越高,其自信息越低。如果一个事件必然发生,其自信息为 0。
在自信息的定义中,对数的底可以使用 2、自然常数 𝑒 或是 10。当底为 2 时,自信息的单位为 bit;当底为 𝑒 时,自信息的单位为 nat。

熵越高,则随机变量的信息越多(不确定性越大,系统越复杂);熵越低,则随机变量的信息越少。


求最大熵:假设概率分布

X 1 2 ... n
p(x) p₁ p₂ ... pⁿ

maxH(p)=maxi=1npilogpis.t.i=1npi=1\max H(p) = \max -\sum_{i=1}^n p_i \log p_i \\ s.t. \sum_{i=1}^n p_i = 1

由拉格朗日乘数法(Lagrange Multiplier),最大变最小时去掉负号
L(p,λ)=i=1npilogpi+λ(1i=1npi)偏导:Lpi=logpi+pi.1piλ令偏导为0得:pi=exp(λ1)\mathcal L(p,\lambda) = \sum_{i=1}^n p_i \log p_i + \lambda(1-\sum_{i=1}^n p_i) \\偏导:\frac{\partial\mathcal L}{\partial p_i} = \log p_i + p_i.\frac{1}{p_i} - \lambda \\ 令偏导为0得:p_i^*=exp(\lambda-1)

因为λ\lambda是一个超参数(常数),所以pip_i^*是一个常数,所以 p1=p2=...=pn=1np_1^*=p_2^*=...=p_n^*=\frac{1}{n}

所以概率分布为一个均匀分布,则熵最大,由此性质我们来证明熵的取值范围:设 p 是一个均匀分布p=1np = \frac{1}{n}
H(p)=i=1n1nlog1n=i=1n1nlogn1=i=1n1nlogn=lognH(p) = -\sum_{i=1}^n \frac{1}{n} \log \frac{1}{n} \\= -\sum_{i=1}^n \frac{1}{n} \log n^{-1} \\= \sum_{i=1}^n \frac{1}{n} \log n \\= \log n
所以:0H(p)logn0 \leq H(p) \leq \log n


已知连续随机变量的均值为μ\mu,方差为σ2\sigma^2,求熵最大对应的概率分布:
arg maxp(x)p(x)logp(x)dxs.t.p(x)dx=1xp(x)dx=μ(xμ)2p(x)dx=σ2\argmax_{p(x)} -\int p(x)\log p(x)dx \\ s.t. \int p(x)dx =1 \\ \int xp(x)dx = \mu \\ \int (x-\mu)^2p(x)dx=\sigma^2
拉格朗日函数
L(p(x),λ1,λ2,λ3)=p(x)logp(x)dx+λ1(p(x)dx1)+λ2(xp(x)dxμ)+λ3((xμ)2p(x)dxσ2)L(p(x),\lambda_1,\lambda_2,\lambda_3) = -\int p(x)\log p(x)dx +\lambda_1(\int p(x)dx - 1)+\lambda_2(\int xp(x)dx - \mu) +\lambda_3(\int (x-\mu)^2p(x)dx - \sigma^2)
F(p)=(logp(x)+λ1+λ2x+λ3(xμ)2)p(x)F(p)=(-\log p(x) + \lambda_{1} +\lambda_{2}x+ \lambda_{3}(x-\mu)^{2})p(x)
求偏导并令其为0(可以把求积分当做求和,这样求偏导就容易想象了)
Lp(x)=[logp(x)+1]+λ1+λ2x+λ3(xμ)2\frac{\partial L}{\partial p(x)} = -[\log p(x)+1]+\lambda_1+\lambda_2x+\lambda_3(x-\mu)^2

p(x)=exp{λ11+λ2x+λ3(xμ)2}p(x) = \exp\{\lambda_1-1+\lambda_2x+\lambda_3(x-\mu)^2\}
把跟x有关的保留,其它的设为常数,有
p(x)=exp{λ11+λ2x+λ3(xμ)2}=e1+λ1eλ2x+λ3(xμ)2=Ceλ2x+λ3(xμ)2=Ceλ3(x22(μλ22λ3)x+u2)=Ceλ3(xμ+λ22λ3)2=C.exp{λ3(xμ+λ22λ3)2}p(x) = \exp\{\lambda_1-1+\lambda_2x+\lambda_3(x-\mu)^2\}\\ =e^{-1+\lambda_{1}}\cdot e^{\lambda_{2}x+ \lambda_{3}(x-\mu)^{2}}=C e^{\lambda_{2}x+ \lambda_{3}(x-\mu)^{2}} \\ = Ce^{\lambda_{3}(x^{2} -2(\mu-\frac{\lambda_{2}}{2\lambda_{3}})x+ u^{2})} = C e^{\lambda_{3}(x -\mu+ \frac{\lambda_{2}}{2\lambda_{3}})^{2}} \\= C.\exp\{\lambda_3(x-\mu+\frac{\lambda_2}{2\lambda_3})^2\}

根据(xμ+λ22λ3)2(x-\mu+\frac{\lambda_2}{2\lambda_3})^2得到p(x)p(x)关于μλ22λ3\mu - \frac{\lambda_{2}}{2\lambda_{3}}对称(偶函数关于x=0对称p(x)=p(x)p(x) = p(-x)),所以E[p(x)]=μλ22λ3=μE[p(x)] = \mu - \frac{\lambda_{2}}{2\lambda_{3}} = \mu,得λ2=0\lambda_{2} = 0

那么
p(x)=Ceλ3(xμ)2p(x)= C e^{\lambda_{3}(x -\mu)^{2}}
因为 p(x)>0p(x)>0 ,所以 C>0,λ3<0C>0,\lambda_{3}<0
λ=λ3\lambda = -\lambda_3
根据积分为1的约束 以及ex22dx=2π\int e^{-\frac{x^2}{2}}dx = \sqrt{2\pi},得:
p(x)dx=1=Ceλ(xμ)2dx=Cπλ\int p(x)dx = 1 = C\int e^{-\lambda(x -\mu)^{2}} dx = C\sqrt{\frac{\pi}{\lambda}}