机器学习复习笔记

这个学期出去打了一大堆比赛，课程几乎没怎么上，当然与我自己懒也有关系；过几天就考试了，现在边复习边写这篇笔记。其实有些东西是预习，我在此之前会搞的只有那四次实验，即多项式拟合、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$ 个中心点，然后：

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

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

类的个数

首先我们可以钦定一个 $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算法：

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

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