机器学习复习笔记

这个学期出去打了一大堆比赛,课程几乎没怎么上,当然与我自己懒也有关系;过几天就考试了,现在边复习边写这篇笔记。其实有些东西是预习,我在此之前会搞的只有那四次实验,即多项式拟合、Logistic回归、GMM和PCA。一大堆东西需要从头学起,学了后面的忘了前面的,故在此记录一下。

第一章:机器学习基础

机器学习的概念:若一种算法在某项任务(T)中,通过一些经验(E),提升了它的性能(P),则我们称为这个算法进行了学习。对这个学习任务定义为 <P, T, E> .

几种机器学习类型

  • 监督学习:‌‌给定数据 $D=\{X_i, Y_i\}$‌‌学习 $F(~ \cdot ~ ; \theta)$‌‌使得 $Y_i = F(x_i)$(拟合给定的数据集),且生成 $D^{\text{new}}=\{X_j\} \Rightarrow \{Y_j\}$ (对新数据的预测)
  • 无监督学习:‌‌给定数据 $D=\{X_i\}$ (没有 tag) ‌‌学习 $F( ~ \cdot ~ ;\theta)$ ‌‌使得 $Y_i = F(X_i)$,且生成 $D^{\text{new}} = \{X_j\} \Rightarrow \{Y_j\}$
  • 强化学习:‌‌给定 $D=\{\text{env, actions, rewards, simulator/trace/real game}\}$ ‌‌学习 $\text{policy:} ~ e, r \to a ~ ; ~ \text{utility:} ~ a, e \to r$ ‌‌使得 $\{\text{env, new real game}\} \Rightarrow a_1, a_2, a_3,\cdots$

课程主要学习了监督学习、无监督学习。

决策树的概念

决策树的输入是属性向量$X$,输出是$Y$.

从根节点开始,在每一个内节点,测试一个属性; 对于被测属性的结果,进入各个分支; 叶子节点预测 $Y$.

自顶向下构造决策树

以二分类问题为例。在一个节点上,有若干正例、若干反例。需要选择一个属性、划分出一些分支,来将这些个案最好地分开。

若样本已经被很好地分类,则停止;否则划分样本到各个子节点后,递归上述过程。

各种切分方案

对于类别变量:可以考虑多路切分,一个取值对应一路切分。也可以考虑两路切分,此时将类别分成两个子集,此时需要找到最优切分方案。

对于连续变量:可以考虑先离散化(例如聚类等手段),转为类别变量;也可以考虑二值决策(小于V的放在一路,大于等于V的放另一路),不过计算量可能很大。

如何评判切分方案

一个好的切分方案,会把样本分成几个子集,最好的情况是每个子集“皆为正例”或者“皆为反例”,不过显然这很难达到。所以我们需要一个手段,来测量划分后各个子集的纯度。我们提出“节点混杂度”的概念。先来讨论几个基础概念。

:假设我们要给一个数据集(属性是类别变量)编码。回顾哈夫曼编码,出现频率越多的字符会得到尽量短的编码,在这里亦然。从信息论的角度,我们给出现概率为 $p$ 的属性,分配 $\log_2 (1/p)$ 的编码长度。最后来计算任意一条数据的期望编码长度:$$H(x) := \sum_{i} P(X=i)\cdot \log_2 P(X=i)^{-1} = {\color{red}{-}}\sum_{i} P(X=i)\log_2{P(X=i)}$$ 我们称这个期望编码长度为这个信源的熵,记作 $H(x)$. 显然,若信源(这个数据集)只会产生一种属性,则熵为 0;若信源可以等概率地产生两种属性,则熵为 1。

于是我们认同:熵可以衡量一个数据集的信息“纯度”。信息越纯,熵就越低;信息越混杂,熵就越高。

特定条件熵:是指 $X$ 在给定 $Y=v$ 这个条件时的熵 $H(X\mid Y=v)$ $$H(X|Y=v) := -\sum_{i}P(X=i \mid Y=v) \log_2 P(X=i\mid Y=v)$$

条件熵 :是指 $X$ 在给定 $Y$ 条件下的熵 $H(X\mid Y)$ $$H(X\mid Y) = \sum_{v\in \text{var}(Y)} P(Y=v)H(X\mid Y=v)$$

在给定条件 $Y$ 之后, $X$ 的熵与原先的 $H(X)$ 相比显然有差异。我们定义 互信息 :$$I(X ~ ; ~ Y) = H(X) - H(X\mid Y) = H(Y) - H(Y\mid X) = H(X) + H(Y) - H(X, Y)$$

现在回到决策树。假设有三个数据集,正反例个数是 $(0+, 6-), (1+,5-), (2+,4-)$,显然第一个混杂度最低。我们来分别计算它们的熵:

  • $(0+,6-)$,此时 $P_+ = 0, P_- = 1, H = - (0 \log 0 + 1 \log 1) = 0$
  • $(1+, 5-)$,此时 $P_+ = 1/6, P_- = 5/6, H = -(\frac16\log\frac16 + \frac56\log\frac56) = 0.6500$
  • $(2+, 4-)$,此时 $P_+ = 1/3, P_= = 2/3, H=-(\frac13\log\frac13 + \frac23\log\frac23) = 0.9183$

可见,熵越小,混杂度越低,信息越纯。现在考虑决策树,一个节点有若干正例、若干反例,于是它有一个熵;现在把这些样本划到子节点,子节点上的样本熵的加权平均数,应该可以衡量这个划分的优劣。我们定义信息增益:$$\text{Gain} = Entropy(\text{parent}) - \sum_{\text{child}} \frac{N_{\text{child}}}{N_{\text{parent}}} Entropy(\text{child})$$

不难注意到,信息增益就是父亲节点上的数据集$S$,与切分分支变量$A$的互信息。我们测量各种切分方案的信息增益,选择具有最大信息增益的切分方式,即可确定决策树上这一个父亲节点的切分。ID3 和 C4.5 均采用了信息增益来衡量切分方案。

何时停止递归

当一个结点上,所有样本同属一个类别,就停止扩展; 当一个结点上,所有样本都具有相似的属性值,就停止扩展(因为再往下面走也分不出什么东西); 也可以强行把整棵树建成,然后再剪枝。

如何处理缺失的属性

在考虑利用属性 $X_i$ 进行切分时,计算信息增益的时候忽略掉缺失 $X_i$ 属性的个案;在执行划分时,将缺失属性的个案以不同的权重划分到每个子树,权重为各个子树的大小。譬如原来有10个个案,划分给左边3个,右边9个,则把那个缺失的个案拆成两份,1/3的那份划分到左边,2/3的那份划分到右边。递归之后再计算熵时,也要依据权重来计算概率(而不是点算个案数量)。

‌             ‌‌

第二章:统计学习的建模工具

期望和方差

$$E(X) =  \begin{cases}‌‌\sum_x x\cdot P(x) & \text{discrete} \\‌‌\int_{-\infty}^{+\infty}x\cdot p(x)\text d x & \text{continuous}‌‌\end{cases} $$ $$D(X) =  \begin{cases}‌‌\sum_x (x-E(x))^ 2 \cdot P(x) & \text{discrete} \\‌‌\int_{-\infty}^{+\infty} (x - E(X)) ^ 2\cdot p(x)\text d x & \text{continuous}‌‌\end{cases} $$

高斯分布

一维:$N(\mu, \sigma^2)$,PDF:

$$p(x) = \frac1{\sqrt{2\pi}\sigma}\exp \left\{-\frac{(x-\mu) ^ 2 }{2\sigma ^ 2} \right \}$$

多维(多元正态分布): $N(\mu, \Sigma)$,PDF:

$$p(x) = \frac1{\sqrt{(2\pi) ^ k |\Sigma|}} \exp\left\{ -\frac12 (x-\mu) ^ T \Sigma ^ {-1} (x-\mu) \right\}$$

贝叶斯公式

$$P(A\mid B) = \frac{P(A\cap B)}{P(B)} = \frac{P(B\mid A) P(A)}{P(B)}$$

可知 $$P(Y=y\mid X) = \frac{P(X\mid Y=y) P(Y=y)}{\sum_k P(X\mid Y=y_k) P(Y=y_k)}$$

这是很多机器学习模型的基础。譬如GMM模型,有多个待选的类,我们想要在给定$X$的情况下选择概率最大的类$Y$,就需要知道在给定$X$的条件下,$Y=y$ 的概率 $P(Y=y \mid X)$. 它正比于 $P(X\mid Y=y)P(y)$,而乘法左项是对应类的PDF,右项是对应类的先验概率,均为已知量。

最大似然估计

假设我们的数据集$D$是独立同分布的,现在想从 hypothesis set (候选函数) 里面找一个函数来拟合这个数据集。一种方式是进行最大似然估计(maxmimum likelihood estimation, MLE)。它的核心思想是:特定的参数 $\theta$ 指定了一个候选函数,这个候选函数产生 $D$ 这个数据集的概率是可以计算的。那么我们对于所有的 $\theta$,它生成 $D$ 这个数据集的概率值(称为likelihood),也就是:

$$\begin{aligned}L(\theta) & = P(D ~ ; ~ \theta) \\ &= P(x_1 , x_2, \cdots, x_N ~ ; ~ \theta) \\ &= P(X=x_1 ~ ; ~ \theta)  P(X=x_2 ~ ; ~ \theta) \cdots P(X=x_N ~ ; ~ \theta)  \\ &=\prod_i P(X = x_i ~ ; \theta) \end{aligned} $$

第三个等号,是因为 $x_1, x_2,\cdots, x_N$ 是独立同分布的变量的实例。于是每一个参数 $\theta$ 都有一个描述“$\theta$ 生成样本集 $D$ 的概率”的似然值,我们比较各个似然值,取出最大的,这就是MLE的思想:$$\hat \theta = \text{argmax}_\theta ~ L(\theta)$$

显然,数据集很多的时候,似然值会越乘越小,给数值计算带来麻烦。我们一般对上面的式子取一个 log 再最小化。由于 log 是递增的,所以求出来的 argmax 不会变。

举一个例子,我们抛硬币 100 次,其中 70 次正面朝上。我们设硬币符合伯努利分布,每次抛硬币有 $\theta$ 的概率正面朝上。那么对于一个参数 $\theta$,它生成这个数据集,也就是70次正面、30次反面的概率是:$$L(\theta) = \theta ^ {70} (1-\theta) ^ {30}$$ 这显然很难求 argmax,我们给它取对数。

$$\begin{aligned}\log L(\theta) &=  \log(\theta ^ {70} \cdot (1-\theta) ^ {30}) \\ &= 70\log\theta + 30\log(1-\theta) \end{aligned}$$

想要最小化之,于是对$\theta$求导,最终得到方程$$\frac{70}{\theta} - \frac{30}{1-\theta}=0$$ 解得 $\theta = 0.7$,和我们预想的吻合。

若某变量服从正态分布,也可以用最大似然法估出 $\mu, \sigma$,结果与均值、方差(有偏)是一致的。过程略。

最大后验方法

我们抛硬币10次,其中8次朝上,按照MLE的思路,这个硬币抛出正面朝上的概率就是0.8,然而实际生活中,我们不太会据此判断抛这个硬币八成正面朝上。这是因为我们见过的硬币都是比较均匀的,我们有“硬币一般是均匀的”这一个先验知识。

MLE的思想中,实际参数$\theta$是一个定值,我们需要通过观测,来直接估计这个值,没有利用任何先验知识。而贝叶斯思想中,$\theta$是一个随机变量,不同的取值概率是不一样的,具体的概率分布是由我们依据经验来估计。比如我们可以估计,人民币硬币的“正面朝上概率”服从以0.5为均值的正态分布。

最大后验方法(MAP)不是尝试最大化$P(D;\theta)$,而是尝试最大化$P(\theta \mid D)$. 也就是说,MLE是对于每一个$\theta$,比较参数$\theta$生成这个数据集的概率,是在$\theta$指定的情况下求生成数据集$D$的概率;MAP是考虑“数据集已知的情况下,$\theta$最有可能的取值”,是在数据集$D$给定的情况下,求$\Theta = \theta$的概率。我们注意到:$$P(\theta \mid D) = \frac{P(D \mid \theta)P(\theta)}{P(D)} \propto P(D\mid \theta)P(\theta)$$ 亦即,我们关注的是似然值与 $\theta$ 先验概率的乘积。哪个 $\theta$ 这个值最大,我们就取哪个 $\theta$ 作为最终的参数。

与MLE的式子相比,我们利用了先验知识 $P(\theta)$. 仅仅最大化似然值是不够的,似然值很大但先验概率很小(也就是说,很不合常理)的例子,将会被拒绝。以硬币问题为例,10次实验得到8个正例,并不会让我们认为硬币正面朝上概率是0.8,只会让我们认为其概率稍大于0.5;但如果我们做10000次实验得到8000个正例,最大后验方法得到的$\theta$会比较接近0.8,此时似然值占据主要地位。

通过上面的讨论,我们发现最大后验方法是适应性很强的方法,也可以充分利用我们人的生活经验等先验知识。但是,对于MAP而言,先验概率$P(\theta)$是完全凭借人的估计,不同的研究者采用的先验概率分布千差万别,导致结果差异很大。从这个角度来讲,MAP是主观的。

‌             ‌‌

第三章:回归分析与过拟合

线性回归和最小二乘法

最简单的线性回归,是给定若干个点 $X\in R^m$,要求尽可能地拟合出一个 $m-1$ 维的超平面。在$n=2$的时候,就是在平面直角坐标系上给出很多个点,要画一条直线经过这些点。

一个思路是,我们对于一个参数 $w$,输出$w^T\cdot x$ 。(为了计算简便,我们钦定$x^{(0)}=1$,这样就可以把偏移$b$看作$w_0$)。接下来,不同的 $w$ 会给出不同的超平面,需要一种方法来衡量直线的好坏。采用最小二乘误差,也就是:

$$E(w) = \frac12 \sum_{i=1}^N ( w^T\cdot x_{(i)} - y_{(i)} )^2$$

求个导,有方程 $$\frac{\partial E}{\partial w} = \sum_{i=1}^N (w ^ T x_i - y_i) x_i = 0$$

解出来 $w^*$ 就行了。

多项式拟合

显然,用多项式拟合一些点,本质上等价于线性拟合,只不过线性拟合的输入 $X = (1, x, x^2, x^3, \cdots, x^m)$. 需要找到最优参数 $w$,使得 $w_0 + w_1x + w_2x^2 + \cdots + w_mx^m $ 尽可能等于 $y$. 这和我们刚刚解决的线性拟合问题一模一样,直接套用即可。

过拟合

我们刚刚的拟合过程,只对数据负责,不对分布负责,亦即不对未来的数据负责。最小二乘只保证了“对于这些给定的点而言,我拟合出的超平面是最好的”;没有保证对于其他的点,也能与实际情况一致。此时,模型只注重于提升“在当前数据集下的性能”,亦即把训练误差降得很低;但没有考虑泛化能力,从而测试误差会很高。

我们在多项式拟合的过程中观测到,产生过拟合时,$w$ 的各个参数往往非常大。于是我们考虑能不能在训练误差较小的同时,让 $w$ 尽可能小。办法就是往误差函数里面加惩罚项(亦称正则项):$w$的参数越大,惩罚项越大,会增加误差。显然,当误差最小时,应该训练误差很小、惩罚项也很小。于是误差式(在最小二乘误差的基础上)改为: $$\hat E(w) = E(w) + \frac{\lambda}{2} ||w|| ^ 2$$ 其中的正则项是 $w$ 的 L2 范数。当然惩罚项有很多种选取方式,这里选择了比较常用的 L2-norm.在超参数 $\lambda$ 比较合适的情况下(本例中可能是$10^{-5}$量级),训练结果极大地缓解了过拟合。当然 $\lambda$ 设得太大也不行,$\lambda$太大了就会变成 $w$ 向量的长度竞赛。

最小二乘与最大似然

需要指出的是,如果我们确信对于指定的若干个采样点$x_i$,观测到的数据$Y_i$等于真实值$f_\theta(x_i)$加一个高斯噪声 $\epsilon$(方差随便),亦即 $Y_i \sim N(f_\theta(x_i), \sigma) $,那么最大似然与最小二乘是等价的。我马上来证明这一点。考虑似然值

$$\begin{aligned}L(\theta) &= P(D; \theta) \\ &= \prod_i P(Y_i=y_i ; ~ \theta) \\ &=\prod_i \frac1{\sqrt{2\pi} \sigma} \exp\left\{ -\frac{(y_i - f(x)) ^ 2 }{2\sigma ^ 2} \right\} \end{aligned}$$

取对数,有 $$\ln L = \sum_i [\ln \frac1{\sqrt{2\pi}\sigma} - \frac{(y_i - f(x)) ^ 2}{2\sigma ^ 2}] $$ 从而 $$\text{argmax}_\theta \ln L = \text{argmax}_\theta  \sum_i - \frac1{2\sigma ^ 2} \cdot (y_i - f(x)) ^ 2  = \text{argmin}_\theta (y _ i - f_\theta(x)) ^ 2$$至此和最小二乘法的优化目标一模一样了。

特征变换

简要来讲,特征变换就是从一组已有的特征,进行数学运算,得到一组新特征;新特征相比于旧特征有一些优势。例如异或本来是线性不可分的,但我们做一组新特征:$(x, y, xy)$,这样就可分了,分界面可以是 $x+y-2z=0.5$。从而特征变换可以提取隐含的特征。

另一个特征变换的例子是PCA。PCA是从众多的特征中,选择一些主要的特征向量,来尽可能地表达原来的特征。而这些主要的特征,是从各个维度变量的协方差矩阵的特征向量中取的。特征值越大,在对应特征向量方向上,数据点投影的方差越大。于是取最大的 $k$ 个特征值对应的特征向量即可。


第四章:贝叶斯判别

贝叶斯判别规则

假设我们正在分类一个样本。对于每一个类,我们已知这个类生成这个样本的概率(典型例子是GMM)。那么现在想要判断个案 $x$ 出自哪个样本,只需要知道 $P(Y=i\mid X=x)$,亦即 $$P(Y=i\mid x) = \frac{P(x\mid Y=i)P(Y=i)}{P(x)} = \frac{\pi_i p_i(x)}{\sum _ k \pi_k p_k (x)} \equiv q_i (x)$$

这里的 $P(Y=i \mid x)$ 也就是 $q_i (x)$ 亦称似然函数。

在执行判别时,分母显然是个定值,我们只需要判断分子的大小。也就是说,若 $\pi_a p_a(x) > \pi_b p_b(x)$,我们就判断 $a$ 类胜出。写作另一种形式:$$\ell_{ab} = \frac{p_a(x)}{p_b(x)} > \frac{\pi_b }{\pi_a} $$ 上式中 $\ell_{ab}$ 称为似然比,$\pi_b / \pi_a = \theta_{ba}$ 称为判决阈值。这种判别方式就是贝叶斯判别。

与之等价地,实践上可以两边取对数,再比较。决策函数是:$$h(X) : -\ln p_1(X) + \ln p_2(X) > \ln \frac{\pi_1}{\pi_2}$$

贝叶斯误差

依据预先知道的真实分布而作出决策,其误差称为贝叶斯误差。很明显,既然我们已经掌握了真实的分布,此时仍然存在的误差是偶然性的误差,是无法消除的。贝叶斯误差是理论上最小的误差。

k临近分类器

kNN的思想如下:对于一个个案,找到它附近的 $k$ 个个案(邻居),把这些邻居的类别的众数作为自己的类别。

kNN是比较接近于最优解的。有证据证明,渐近情况下,1-临近的分类器的误差小于2倍贝叶斯误差,不过这毕竟是理论结果。另外,若贝叶斯分类器误差为0,渐进地,k临近也会为0。

kNN的显著缺陷是,数据很大的情况下计算量太大;另外,若某一个类的个案特别多,如果 k 选得稍大了一点,就会导致错误分类。

kNN是基于实例的学习。需要确定一个距离函数,需要确定超参数k,然后kNN会根据手上已有的实例来进行分类。常用的距离函数有欧氏距离(L2范数)、曼哈顿距离(L1范数)等。

参数分类器和非参数分类器

参数分类器假设了数据分布符合某种形式,亦即特定的hypothesis set,一个参数对应一个hypothesis function,然后通过调整自己的参数,来最优化分类结果。

非参数分类器没有假设数据分布,完全依赖自己已有的样本。

我们称一个分类器是贝叶斯分类器,当且仅当它对样本生成概率的估计,等于真实分布。贝叶斯分类器显然是最优的分类器,其误差也等于贝叶斯误差。

线性分类器

所谓线性分类器,就是采用一个超平面为分界面,在不同侧的就是不同的类。决策函数一般符合$$h(x): w^T x > b$$常见的线性分类器有Logistic分类器、SVM等。

生成式模型和判别式模型

如上图所示。判别式模型直接对$P(Y\mid X)$建模,试图在样本$X$的条件下直接找到概率最大的 $Y=f(x)$。判别式模型可以一步到位地给出分类结论。而生成式模型是对联合分布$p(x,y)$建模,当取得样本$X$(例如右图中的红色三角形)时,在$p(X,Y)$里面选最大的。实践上可能是这样操作:求出蓝色类生成它的概率$P(X\mid 蓝)$、求出黄色类生成它的概率$P(X\mid 黄)$,进而利用贝叶斯,依据蓝色、黄色各自的先验概率$\pi$,推断出$P(蓝\mid X),P(黄\mid X)$(它们正比于联合分布),选择更大的那一个。

判别式模型的典型例子有逻辑回归、SVM;生成式模型的典型例子有GMM、朴素贝叶斯。


第五章:朴素贝叶斯与逻辑回归

条件独立

我们称$X$在给定$Z$的条件下条件独立于$Y$,当且仅当 $X$ 的分布在给定$Z$的条件下与$Y$无关。形式化地:$$\forall i, j, k \quad P(X=x_i \mid Y=Y_j , Z=z_k) = P(X=x_i \mid Z=z_k)$$缩写为$$P(X\mid Y,Z) = P(X\mid Z)$$

若$X_1,X_2$在给定$Y$时条件独立,那么立即有

$$\begin{aligned}P(X_1, X_2 \mid Y) &= P(X_1 \mid X_2, Y) P(X_2 \mid Y) \\ &= P(X_1 \mid Y)P(X_2\mid Y) \end{aligned}$$

一般化,若$X_i$ 与$Y$条件独立,那么有$$P(X_1, X_2, \cdots, X_n \mid Y) = \prod_i P(X_i \mid Y)$$这是朴素贝叶斯的基础。

朴素贝叶斯

首先,假设我们想从2个二值离散变量里面学它的分类。这显然是很好做的,一共只有四种情况,求出对应的概率 $P(X_1, X_2 \mid Y)$ 即可。

然而,当离散变量有数十个、上百个,我们要学的参数会指数级地增加;另外,数据也明显不够(这种暴力学习相当于对每一个个案,生成一条决策树从根到叶子节点的路径,需要指数级的数据才能学到整棵树)。

但我们仍然想利用现有的少量数据,学到判别策略,也就是对于任何一个给定的$X_1, X_2,\cdots, X_n$,需要生成$$P(Y=y_k \mid X_1, X_2, \cdots, X_n)$$

我们采用贝叶斯定理,上面式子改写为$$\frac{P(Y= y_k) P(X_1, X_2, \cdots, X_n \mid Y=y_k)}{P(X_1, X_2, \cdots, X_n)}$$

对于某个给定的$X$,分母是恒定的。我们只需要最大化分子,也就是:$$\text{argmax}_k ~ P(Y=y_k)P(X_1, X_2, \cdots, X_n \mid Y=y_k)$$

现在,朴素贝叶斯假设各个$X_i$之间是无关的。上式转化为$$\text{argmax}_k ~ P(Y=y_k) \prod _i P(X_i = x_i\mid Y=y_k)$$

先验分布 $P(Y=y_k) = \pi_k$ 是可求的,$P(X_i = x_i \mid Y=y_k)$也是可求的:它等于在$y_k$这一类别中,第 $i$ 个属性等于 $x_i$ 的个案占样本数的比例。我们记 $\theta_{i,j,k}$ 为“类别为$k$的样本中,第$i$个属性为$j$的个案占样本总量的比”,那么就可以给出分类判别:

$$Y ^ {\text{new}} = \text{argmax} _k ~ P(Y = y_k) \prod_i \theta _ {i,x_i,k} $$

零概率问题与拉普拉斯平滑

在朴素贝叶斯中,如果某属性上的概率为0,则会产生零概率问题。譬如100份调查问卷,“你是否出生于1926年8月17日”这个问题所有人都填了“否”,从而这个属性的反例概率为1;现在来了一个you-know-who,填写这份表之后,我们要给他判断一个类别,然而对于任何类别,因为有$P(出生于19260817\mid Y)$这个为0的因数,得到的结果全为0.

处理办法是拉普拉斯平滑。令$N$表示训练集$D$中可能的类别数,$N_i$表示第$i$个属性可能的取值数,把$P(c)$和$P(X_i\mid c)$的公式分别修正为:$$\hat P(c) = \frac{|D_c| + 1}{|D| + N}$$ $$\hat P(X_i = x_i \mid c) = \frac{|D_{c, x_i}| + 1}{|D_c| + N_i}$$

处理连续属性

修改朴素贝叶斯模型,将 $P(X=x_i \mid Y=y_k)$ 改为其概率密度函数。譬如我们采用高斯分布:$$P(X=x_i \mid Y=y_k) = \frac{1}{\sqrt{2\pi}\sigma_{i,k}}\exp\left(-\frac{(x-\mu_{i,k})^2}{2\sigma_{i,k} ^ 2}\right)$$

参数$\sigma,\mu$需要学习。可以采用最大似然来产生$\sigma, \mu$,即让$\sigma$为第$k$类样本第$i$个属性的标准差,让$\mu$为均值。当然也可以采用最大后验方法,加一些先验知识进去。

Logistic回归

现在我们考虑一个线性可分的二分类问题。接下来我们构造一个判别式模型,假定数据满足以下条件:

  • 属性 $X\in R^{n}$
  • 输出 $Y$ 是布尔变量
  • 给定 $Y$ 时,$X_i$ 相互条件独立
  • $P(X_i \mid Y=y_k)$ 符合高斯分布 $N(\mu_{ik}, \sigma_i)$ (每个属性是从一个高斯分布中取出的)
  • $P(Y)$ 符合伯努利分布

那么我们来看给定一个输入$X$,其为正例的概率。

$$\begin{aligned}P(Y=1\mid X) &= \frac{P(Y=1)P(X\mid Y=1)}{P(Y=1)P(X\mid Y=1) + P(Y=0)P(X\mid Y=0)}  \\ &=\frac1{1 + \frac{P(Y=0)P(X\mid Y=0)}{P(Y=1)P(X\mid Y=1)}}  \\ &= \frac{1}{1+\exp\{\ln  \frac{P(Y=0)P(X\mid Y=0)}{P(Y=1)P(X\mid Y=1)} \}}  \\  &= \frac{1}{1+\exp\left\{ {\color{blue}{(\ln \frac{1-\pi}{\pi})}} + {\color{red}{\sum_i \ln \frac{P(X_i \mid Y=0)}{P(X_i \mid Y=1)} }}\right \}} \end{aligned}$$

蓝色式子是常量,而红色式子等于 $$\sum_i\left( \frac{\mu_{i0}-\mu_{i1}}{\sigma_i ^ 2} X_i + \frac{\mu_{i1} ^ 2 - \mu_{i0} ^ 2}{2\sigma_i ^ 2} \right)$$

可见是 $X$ 向量点乘一个常量,再加上一个常量。从而整个式子可以表达为:$$P(Y=1\mid X) = \frac{1}{1+\exp(w_0 + \sum_i w_i X_i)} = \frac{1}{1 + \exp(w^T X)}$$

通过一系列运算,我们得到一些将来会有用的性质。记 $f(x) = P(Y=1\mid X=x)$,有$$P(Y=0\mid x) = 1-f(x) = f(-x)$$

另外,我们做决策时,是比较$f(x)$与$1-f(x)$的大小,也就是若 $\frac{1-f(x)}{f(x)} < 1$ 则判断是正例,否则判断是反例。也即判断 $exp(w^TX) < 1$,也就是判断 $w^TX<0$. 我们发现这是一个超平面,故 Logistic 回归是线性分类器。

扩展:更多的类

在二分类任务中,正例的权重是 $1$,反例的权重是 $\exp(w^Tx)$. 若 $Y$ 有更多类,可以扩展Logistic回归,此时需要学习多个$w$向量。若有 $R$ 个类,则概率值改为:

$$P(Y=y_k\mid X) = \begin{cases}\frac{\exp(w_k ^T X)}{1+\sum_{j=1}^{R-1}\exp(w_j ^T X)} & \text{for } k < R \\ \frac{1}{1+\sum_{j=1}^{R-1}\exp(w_j ^T X)}  & \text{for } k = R\end{cases}  $$

条件最大似然估计(MCLE)

现在我们需要训练Logistic回归分类器。手上有若干个样本:$<X^1, Y^1>, <X^2, Y^2>, \cdots$ 现在我们想让似然值最大。

$$w_{MLE} = \arg\max_w P(<X^1, Y^1>\dots<X^L,Y^L>\mid w)$$

由于各个数据独立,有$$w_{MLE} = \arg\max_w\prod_l P(<X^l, Y^l> \mid w) = \arg\max_w\prod_l P(Y^l \mid X^l, w)$$

现在,我们需要选择一个向量$w$,来最大化这个条件似然值。

$$\begin{aligned}l(w) &= \sum_l\ln P(Y^l \mid X^l, w) \\  &= \sum_l \left(  Y ^ l \ln P(Y ^l =1 \mid X ^ l, w) + (1-Y ^ l) \ln P(Y ^ l = 0 \mid X ^ l ,w) \right)  \\ &= \sum_l \left(  Y ^ l \ln  \frac{P(Y ^l=1 \mid X ^l, w)}{P(Y ^l = 0 \mid X ^ l, w)} + \ln P(Y ^l = 0 \mid X ^ l, w)  \right)  \\ &=  \sum_l \left(  Y ^ l (w^T X ^l) - \ln (1 + \exp(w ^ T X^l))  \right) \end{aligned}$$

很遗憾,它没有解析解。我们需要通过梯度下降求出近似解。

MCLE与MAP

它们的共同点是$\theta$有某种先验。例如上例,递归下降算法中,$\theta$的初值是一个先验知识。

它们都可以利用先验知识,抑制过拟合。不过 MAP 直接把 $P(\theta)$ 乘在了最大化的式子上。

MAP:$$\arg\max_w ~ \ln {\color{blue}P(w)} \prod_l P(Y ^ l\mid X ^ l, W)$$MCLE:$$\arg\max_w ~ \ln \prod_l P(Y ^ l\mid X ^ l, W)$$


第六章:SVM与核方法

最大间隔方法

若在平面上想要为线性可分的两类数据进行划分,显然,为了避免过拟合,分界线离两个类都应该尽可能远。现在我们考虑分界线方程 $w^Tx+b = 0$,若$w ^T x + b > c$,则判断为正例;若小于 $-c$,则判断为反例。显然,$c$ 并不需要取遍所有的值,事实上我们只需要让$c=1$,因为若为其他值,则等式左右两边同时除以$c$即可变成$c=1$的情况。至此我们总结出SVM的判断方式:若$w^T x+b>1$,则为正例;若$w^Tx+b<-1$,则为反例。

我们的分界线显然在$w^Tx+b=1, w^Tx+b=-1$这两条平行线正中间,现在我们希望间隔距离最大。这就是最大间隔方法。

现在考虑如何求出这个最大间隔。现在我们随便取个点$x_1$使得$w^Tx_1 + b = -1$。由线性代数基础知识,注意到 $w$ 向量与分界线垂直,于是$x_1$对面那个点 $x_2 = x_1 + \lambda \frac{w}{||w||}$,其中 $\lambda$ 即为margin。同时 $x_2$ 需要满足 $w^Tx_2 + b = 1$,综合我们得到

$$\begin{aligned} w^T (x_1 + \lambda \frac{w}{||w||}) + b &= 1 \\  w ^ T x_1 +b+\lambda \frac{w^Tw}{||w||} &= 1  \\ \lambda \frac{w ^ T w}{||w||} &= 2\\ \lambda &= \frac{2}{||w||} \end{aligned}$$

从而我们想要最大化margin,就是最大化$\lambda=\frac{2}{||w||}$,也等价于最小化 $w^T w$. 形式化地:

$$\begin{align*}\min_w \qquad \frac{w^Tw}{2}\\ s.t. \quad y_i (w^T x_i + b) \geq 1  ~~~, \forall i\end{align*}$$

这就是支持向量机。$y_i (w^Tx_i +b) = 1$ 的个案,称为“支持向量”。形象地,它们支撑起了两条线,这两条线的距离是margin.

这个形式的优化问题是二次优化问题,已经可以直接求解。接下来我们会利用拉格朗日对偶性来优化。此外,接下来的推导将很容易地引出 kernel trick.

拉格朗日乘子法

等式条件的拉格朗日乘子法我们已经会了,现在来考虑不等式约束。首先,我们想要优化的函数是 $f$。但是需要满足若干个不等式条件$g$,也就是

$$\begin{aligned}\min_{w}&\quad f(w) \\ s.t.&\quad g_i(w) \leq 0, ~ ~ ~ ~ i=1,2\dots,k \end{aligned}$$

现在对于我们要解决的问题,我们的不等式约束是 $y_i (w^Tx_i +b) \geq 1$,写成 $1-y_i(w^Tx_i + b) \leq 0$ ,发现形式与拉格朗日乘子的约束对应上了。现在假设我们手上有一份$w,b$,想要衡量它是否合法,我们考虑$$\sum_i\max_{\alpha_i \geq 0} \alpha_i(1-y_i(w^Tx _i + b))$$
显然,这个$w,b$要是合法,那么上面式子必然为0,因为每一项都为非负,$\alpha$又不小于0;事实上,大部分时候$\alpha_i$必须等于0才能最大化 $\alpha_i(1-y_i(w^Tx _i + b))$。如果 $w,b$ 不合法,那么必然有一个 $1-y_i(w^Tx _i + b)$ 是大于0的,此时 $\alpha_i$ 会往无穷大发展,来取得max值。于是如果 $w,b$ 不合法,这整个式子的值是趋向于正无穷大的。

总结一下,现在我们有了这样一个工具:如果$w,b$不合法,则它为正无穷大;如果$w,b$合法,则为0. 现在我们考虑

$${\color{blue}\frac{w^Tw}{2}} + \color{green} \sum_i\max_{\alpha_i \geq 0} \alpha_i(1-y_i(w^Tx _i + b))  $$

来考虑这个式子在什么时候取到min. 这里面有两项,蓝色为SVM的优化目标,绿色为我们刚刚弄出来的工具。如果$w,b$非法,那么整个式子会是无穷大,因此整个式子的min值一定在$w,b$合法的时候才能取到;此时绿色部分为0,于是整个式子的min值就恰好等于 $\frac{w^Tw}{2}$ 的min值。通过拉格朗日乘子法,我们成功地将有约束极值改造成了无约束极值。

接下里的目标是求

$$\min_{w,b} \left\{ \frac{w^Tw}{2} + \sum_i \max_{\alpha _ i\geq 0} \alpha_i [1-y_i (w ^ T x_i + b)] \right\}$$

比较遗憾,这很难求。上面的式子是固定$w,b$,变动$\alpha$,很难求出解来;但如果我们换一个思路:先固定$\alpha$,在$\alpha$指定的情况下变动$w,b$,这个问题称为对偶问题:$$\max_{\alpha_i \geq 0} (\min _{w,b} J(w,b;\alpha)) \quad \text{where} ~ J(w,b;\alpha) = \frac{w^Tw}{2} + \sum_i \alpha_i (1-y_i (w^T x _i + b))$$

我们通过解对偶问题,可以获得原问题的一个比较优的解(如果符合强对偶性,那么对偶问题的最优解 $d^*$ 就是原问题的最优解 $p ^ *$). 既然 $\alpha$ 是固定的,想要让 $J$ 取最小值,需要让 $\frac{\partial J}{\partial w} = \frac{\partial J}{\partial b} = 0$. 一番求导之后我们得到 $w=\sum_i \alpha_i y_i x_i$ 且 $\sum_i \alpha_iy_i=0$. 整个式子的最小值为 $$\min_{w,b} J(w,b;\alpha) = \sum_i \alpha_i - \frac12 \sum_{i,j} \alpha_i\alpha_jy_i y_j x_i^T x_j$$

于是对偶问题就是:$$\max_{\alpha \geq 0} \left( \sum_i \alpha_i - \frac12 \sum_{i,j} \alpha_i\alpha_jy_i y_j x_i^T x_j \right)$$约束条件:$\sum_i \alpha_iy_i = 0$,且$\alpha_i \geq 0$. 这又是一个二次规划问题,但是比原来那个要好解一些。

求出 $\alpha$ 之后,我们用 $w=\sum_i \alpha_iy_ix_i$ 即可恢复出 $w$.

实际上,我们拿着 $\alpha, b$,也可以直接用来分类数据。这是因为:

$$w^Tz + b = \left(\sum_{i} \alpha_i y_i x_i^T z\right) + b$$

我们甚至能做得更快:注意到只有支持向量的$\alpha$才可以非0,在求和的时候只需要取支持向量就行了。另外,我们这里向量 $x_i$、$z$ 唯一参与的运算是内积,这将在未来被核函数替代。

数据噪音的处理

如果数据不是完全线性可分的,我们必须允许一些点被分错类。而若第$i$个点不满足 $1-y_i(w^Tx_i + b) \geq 0$,则$\alpha_i$有变大的趋势;此时我们加一条限制 $\alpha\leq C$,即可让 $\alpha$ 在错误分类的情况下顶多达到 $C$,等价于添加了惩罚项。对偶问题的约束变为:$\sum_i \alpha_iy_i = 0$,且$0\leq \alpha_i \leq C$.

核方法

如果原来的数据本身就是线性不可分的,SVM就炸了。譬如一个数据集,以 $x^2 + y^2 = 1$ 为界,里面的是正例,外面的是反例。这显然线性不可分,于是SVM对这种情况无能为力。

但是,如果我们做一个特征变换:$$\varphi(x) = (1,\sqrt2 x_1, \sqrt2x_2, \sqrt2x_1x_2, x_1^2, x_2^2)$$
数据从二维升到五维之后,数据将会变得线性可分。另外说一句,异或在这个特征变换之后也可分。

但是这个方法并非完美。有些隐特征是需要很高的维度,才能线性地切分开来。如果我们需要把数据升到100维,每一个向量都会变成100维,这会大幅增加计算。

回顾之前的过程:我们优化对偶问题的时候,并不需要真正地给向量做特征变换,而只需要知道特征变换之后向量的内积;在分类的时候,也只需要向量的内积。所以我们可以这样做:并不显式地升维变量,而是在向量需要求内积的时候,用我们新的函数来替换内积函数。这就是核函数。

上面那一个从二维升到五维的例子,其特征变换之后再点积,实际上等于$$K(x_1, x_2) = (1+x_1^Tx_2) ^ 2$$这并不需要太多的计算。所以我们通过核函数,避免了真正执行升维,只需要在计算内积的时候采用核函数来替代。

常用的核函数有:

  • 线性核 $K(x_1, x_2) = x_1^T x_2$ ,它就是内积,写成这样是为了把采用核函数、不采用核函数的SVM形式统一起来。
  • 多项式核 $K(x_1, x_2) = (1+x_1^Tx_2)^p$ ,其中 $p$ 决定了特征变换之后的维度。
  • 径向基 $K(x_1, x_2) = \exp ( -\frac12 ||x_1 - x_2|| ^ 2 )$
  • 高斯核 $K(x,z) = \exp(-\frac{||x-z|| ^ 2}{2\sigma ^ 2})$,它的特征变换之后的维度是无穷大。

第七章:无监督学习

距离

聚类(clustering)的主要思想是将无标签的数据分为若干个组,其中类内聚集、类间分离。

想要衡量“相似度”,我们需要有对距离的定义。首先,无论如何,距离必须满足以下条件:

  • 对称性:$D(A, B) = D(B, A)$
  • 同一性:$D(A, B)= 0$ 当且仅当 $A=B$
  • 三角不等式:$D(A, B) \leq D(A,C) + D(B,C)$

闵可夫斯基距离定义了一系列距离,$r$阶闵可夫斯基距离是:$$d(x,y) = \sqrt[r]{\sum_{i}|x_i - y_i| ^ r}$$显然,$r=1$时为曼哈顿距离,$r=2$时为欧几里得距离(L2范数),$r=+\infty$时是两个向量各个维度之差的绝对值的最大值。

还有各种其他的距离,例如汉明距离、最小编辑距离等。

k-Means

一个迭代式的聚类算法。首先随机选择 $k$ 个中心点,然后:

  1. 对于每一个点,划分到距离自己最近的中心点的类
  2. 对于每一个类,以类内点的坐标均值作为新的中心

重复以上过程直到收敛为止。

类的个数

首先我们可以钦定一个 $k$,作为聚类的个数。但是很多情况下我们不知道应该分出多少类,在此情况下会很麻烦。

直观上讲,类越多当然越满足“类内聚集、类间分离”;但是类太多了的话(例如每个点自己就是一个类),聚类并不能给之后要进行的工作带来实际好处。因此我们需要选取适当的 $k$.

顺带一提,要衡量两个聚类方案之间的相似程度,可以采用RI。它的计算方法是:对于每一对样本点$(x,y)$,它可能在A、B中都被划分到同一类;可能A、B都不把它们划分进同一类;可能A划分到同类而B划分到不同类,可能反之。一共就是这四种情况。我们记“被A、B方案均划分到同类”的点对个数为 $a$,“被A、B方案均划分到不同类”的点对个数为 $b$,则 $$RI = \frac{a+b}{\frac12n(n+1)}$$

RI越接近1,两个划分方案越相似。可以用来评估聚类的性能。

GMM算法

GMM假定有 $k$ 个类,而每个类生成点,服从多元正态分布。从而我们一共有三个参数:$\pi_t$ 是划分到第 $t$ 类的先验概率;$\mu, \Sigma$ 是每个类的正态分布参数。

实践上,我们无法直接最大化似然值。EM算法的方案是:首先固定住 $\mu, \Sigma$,然后去优化 $\pi$;做完之后,固定住 $\pi$,然后优化 $\mu$ 和 $\Sigma$。迭代若干次,就可以取得较好的参数。

推导很复杂,略。

PCA

PCA是特征提取的算法。其基于这样一种思想:所有数据点如果在某一方向的投影方差很小,说明数据在这一方向上并没有多少信息,可以去除掉。依据这种思路,有PCA算法:

  1. 各个数据点都减去所有数据点的均值 $\mu$。此后数据点均值为0。
  2. 对数据点的各个维度,求协方差矩阵 $\Sigma$.
  3. 对 $\Sigma$ 求特征值和特征向量。
  4. 保留下前$k$大特征值对应的 $k$ 个向量,每个旧点生成一个新的表示:其在这 $k$ 个特征向量上的投影长度(实现时,用单位特征向量点乘旧的向量)。

如果想要恢复数据,做法如下:以新特征的各个属性为系数,线性组合这 $k$ 个特征向量,最后加上 $\mu$,得到重建的点。显然PCA会损耗掉一些信息,但鉴于损耗的信息方差很小,并没有太多的特征,所以有时可以忽略这些不重要的特征,换取更小的对点的表达方式,以加速后续的处理过程。