统计学习方法 十到十六章笔记

第十章 隐马尔可夫模型

10.1 隐马尔可夫模型的定义

隐马尔可夫模型包含观测，状态和相应的转移，具体的记号不在给出。只给出其性质：其中i是状态而o是观测：

HMM可以用来标注，这个时候状态就是标记。标注问题是给定观测的序列，预测对应的标记序列。 HMM的一个比较易懂的例题在P195。 HMM的具体问题在下面三个章节分别讲述。

10.2 概率计算算法

这里解决的问题是，给定模型和观测序列，计算在这个模型下观测序列出现的概率。 暴力的话，方法如下： a是状态转移概率，是初始状态的概率，b是给定的状态下得到相应观测的概率。

但是这里有很多这样的状态，随着时间T跳转，计算量是的，因为每次求和是的，然后给定时间，每一个时刻可以选择个状态里面的一个。 这个时间复杂度太高了，想办法改进，使用前向-后向算法。

前向算法中，定义前向概率： 注意，这里的前向概率都是已经看到了、给出来的，而不是排列的那种t!种可能性然后都算一次的东西。以及，这里就单纯是，在已经观测得的内容里，t时刻的状态是第i个状态这个意思。 因此有了前向算法：

(2)式琢磨一下，也可以很容易推出来。(3)式想到的意义，也就是对已经观测到的O，最后一个状态是什么都有可能，所以从1到N累加。时间复杂度为，因为每个给定的时间t的某个节点都会看前面N个节点，当前层又有N个节点，一共T层。 前向算法的例子在课本P200。

后向算法中和前向算法相反，定义后向概率： 就是在t时刻的第i个状态，会让它后面发生这样的观测的概率。

有了前向概率和后向概率，可以得到一些公式：

• 给定模型和观测，求某时刻状态的概率：公式见课本P202，这种东西不好推导。
• 给定模型和观测，求某时刻状态和下一个时刻的状态分别为给定的, 的概率。
• 在给定观测下状态出现的期望值、由状态转移的期望值和由状态i转移到j的期望值

10.3 学习算法

上面一节是给定了参数，跑预测用的。我们可能更希望有方法估计参数。 可以直接用极大似然估计，但是这样的估计需要大量标注，下面介绍无监督学习的算法，称为Baum-Welch算法。 课本这里一笔带过了，推导估计也不是很简单的事情，这里就贴个结论吧。

10.4 预测算法

预测算法中，有两个算法可以估计中间某个状态的概率。 在近似算法中，

这个公式来自10.2节里面的P202公式。但是里面的状态序列未必会全部发生。

维特比算法是一种dp的思路，

这里的是当前从0看到t时刻的观测下（t-1和从前的时刻也是已知的）t时刻有最大概率的状态，而记录了从哪里跳到这个在看的i节点。换句话说，负责找到最大的概率，而负责找到这个概率对应的位置。注意，这里差一个。 例子见课本P210。

第十一章 条件随机场

11.1 概率无向图模型

概率无向图模型也叫马尔可夫随机场。 这一节都是一些定义的内容，知道就可以了。

• 成对马尔可夫性：在无向图中两个不相邻的节点u，v，别的节点是O，对应的随机变量表示为Y，满足：
• 局部马尔可夫性：给定任一节点v，W是一个和v相连的节点，O是除v和W外的节点，满足：，看起来好像是，给定一个节点的时候，他的相邻节点和另外的节点独立；以及在时，满足
• 全局马尔可夫性：取节点集合A，B，C，其中C把A，B分开，也就是不连通，满足

这三个性质等价。 对于联合分布，如果满足三个之中的一个，就是概率无向图模型。 对于概率无向图模型，可以进行因子分解，也就是团。团就是离散数学里面的，里面各个节点两两连接。当无向图里面的团C不能再加入G的其他节点使之变大，那么这个团C称为最大团。 有了最大团，联合概率分布可以写成所有最大团的乘积，也就是，其中Z是归一化因子，即，让这个式子变成一个概率分布。这里的叫做势函数，通常定义为。

11.2 CRF的定义与形式

一般的CRF，满足，是和v相连的节点w。 定义里面不要求X和Y有相同结构，不过一般都使用相同结构的X和Y。 在课本中，使用线性链CRF，也就是只有相邻的和是相连的。公式上，也就是：，而且在两侧只考虑单边，图：

线性链CRF的参数化形式如下：

课本的例子在P220。 线性链CRF可以用简化形式或者矩阵形式表示。 CRF中，表示在观测序列x下，标记序列为y的条件概率。 这里写出矩阵形式的公式，简化形式看课本吧。 ，其中的规范化因子所有矩阵乘积的元素。 矩阵形式下的例子在课本P224，较易看懂。

11.3 CRF的概率计算问题

这里解决的是给定CRF，输入序列x和输出序列y，计算各个位置的条件概率和期望。可以使用前向-后向算法。 前向向量：初始化： 递推： 也有后向概率：初始化： 递推： 同样的，这里的概率公式和期望值都可以算出来，在课本P225。这里不再给出。

11.4 CRF的学习算法

这个东西我不想看。

11.5 CRF的预测算法

使用的是维特比算法。

例子在P234。 这里的特征函数就是t和算一次加权，s和算一次加权，具体的特征函数式子在上面。这里的start只是一个记号，并不需要管是什么。也就是，这个维特比算法是在让i增加的过程中跑出最后的结果。

第十四章 聚类方法

14.1 聚类的基本概念

聚类的核心是相似度。就像第三章里面说的，可以使用闵可夫斯基距离，找到合适的p值就可以。不过还有另外的一些指标：

• 马哈拉诺比斯距离：给定样本集合X = [x_{ij}]{m \times n}，这里竖向是一个样本的各个维度上的特征，把的协方差矩阵记作，样本x_i和x_j之间的马氏距离为d{ij} = ((x_i - x_j)^T S^{-1} (x_i - x_j))^{\frac{1}{2}}，其中x_i = (x_{1i}, x_{2i},…, x_{mi})^T。当S是单位矩阵时，也就是各个分量相互独立且各个分量的方差=1的时候，马氏距离就是欧氏距离。
• 相关系数：r_{ij} = \frac{\sum\limits_{k=1}^m (x_{ki} - \bar{x}i)(x{kj} - \bar{x}j)}{(\sum\limits{k=1}^m (x_{ki} - \bar{x}i)^2 \sum\limits{k=1}^m (x_{kj} - \bar{x}_j)^2)^\frac{1}{2}}，其中bar是把特征取平均。这里r越大越相似。
• 夹角余弦。也就是向量之间的cos角，公式懒得写了。

聚类有硬聚类和软聚类之分，其中硬聚类就是每个样本只能有一个类，软聚类反之。课本只介绍了硬聚类。 对所有点，其中的一个子集G，如果任意两个样本和都有成立，T是给定的正数，那么G就是一个类或者簇。 对于类（一堆样本）这个尺度，还有一些别的性质：

• 类的均值，或者叫类的中心：\bar{x}G = \frac{1}{n_G} \sum\limits{i=1}^{n_G}x_i
• 类的直径：
• 类的样本散布矩阵：
• 类的样本协方差矩阵：，m是样本维数

然后对于类之间，还有另外的一些定义（比较好理解）：

14.2 层次聚类

也就是对某一个层次聚类，然后合并或者继续分裂。 聚合聚类算法：

这里的距离矩阵D是一个对称矩阵，而且对角线上元素为0。 这个过程完全就是遍历贪心，课本例子很直观。

14.3 k-means聚类

这里的聚类事实上是一种划分，即不重不漏的分类。可以用一个函数来建模这个关系，即。i是样本index，l是类别index。 k-means方法使用的损失函数是各个类到类中心的l2距离之和。算法为：

课本的例子很容易理解。

k-means的特点：

• 基于划分；
• 实现指定类别数；
• 使用欧氏距离表示样本之间的距离，使用样本均值表示类别；
• 算法是迭代的，是一种启发式方法，不保证是全局最优；
• 聚类结果和初始选择是相关的，不同的初始选择可以得到不同的聚类结果；
• 这个k值一般需要搜索，满足这样的关系：

第十五章 奇异值分解

终于到了这个耳熟能详但是又不会用的东西了。

15.1 SVD的定义与性质

对实矩阵的SVD，就是对一个矩阵进行因子分解，其中A的形状是(m, n)：，V是n阶正交矩阵，是降序排列的非负的对角线元素组成的(m, n)形状的矩形对角矩阵，这里的各个矩阵满足如下性质：

这里的称为矩阵A的奇异值，U的列向量叫左奇异向量，V的列向量叫右奇异向量。而且SVD不要求A是方阵。注意这里的并不一定要填满p这么多个对角元素，后面几个元素是0也可以的。

不过一般常用的是紧奇异值分解和截断奇异值分解，其中紧奇异值分解和原来的SVD（又称完全奇异值分解）等价，而截断SVD比原始矩阵低秩。SVD的提出就是为了对矩阵进行压缩，其中截断SVD就是有损压缩。

紧奇异值分解的矩阵可以比完全SVD更小，紧的SVD的矩阵大小是和待分解矩阵的秩相关的。对于矩阵A，，那么有，其中的形状是(m, r)，的形状是(n, r)，是r阶方阵，其中是完全SVD的前r列的列向量组成的，同理，是前r个元素组成的对角阵。其中。

截断奇异值分解和紧奇异值分解类似，不过会让，其中。这里的k也是取定的，的取法也是类似的。

SVD的几何解释也是有意义的。对于一个给定的矩阵A，形状是(m, n)，可以考虑变换，这里是一个到的空间映射，这一个映射可以分解成三个步骤，对应SVD的三个矩阵：一个坐标系的旋转或反射变换、一个坐标轴的缩放变换和另一个坐标系的旋转或反射变换。 在SVD中，U和V都是正交矩阵，那么V的列向量构成了空间里的一组正交基，U同理。所以这里都表示旋转或反射变换。对于，是一组非负实数，表示各个轴上的缩放变换。 SVD的几何解释可以对标准正交基进行变换看效果，课本的例子比较直观。 而且SVD直觉上，感觉像对A做行变换之后得到的奇异值对角阵，因为这两个东西秩相等。

SVD还有一些相关的性质：

• 和的SVD也是存在的，而且和A的SVD结果相关，具体不在这里给出。
• 对于，右乘得到，考察矩阵的第j列，就有：，那么类似地取个转置，就有和。
• SVD中的是唯一的，而U和V不唯一，也就是给定一个A，那么对应的唯一。
• A和的秩相等，也和的正奇异值个数相等（包括重复的奇异值）。
• 课本这里还有一个很长的性质，不知道能干嘛。

15.2 SVD的计算

SVD的求法看起来比较机械化。步骤为：

1. 求的特征值和特征向量。也就是，求解，把里面的特征值从大到小排列。然后把代入得到特征向量。
2. 把特征向量单位化之后横向拼起来，得到正交矩阵V：
3. 构造全0矩阵，形状为(m, n)，对角元素填入，得到
4. U分成两部分，对于前r个特征值，有，然后对于后面的m-r个特征值，求出的零空间(Null)的一组标准正交基（其中，也就是，要求的零空间标准正交基，解出来之后单位化即可）。把两个得到的这一堆列向量都横向拼起来就是U。

课本有一个SVD的计算，把那个掌握了之后应该就会计算SVD了。不过这里的SVD计算是理论上的，工程上的计算并不是这样算的。课本没给出来。

15.3 SVD与矩阵近似

矩阵的F范数就是各个位置平方，然后全局求和后取开方。这里有一个引理，对于A和他的各个奇异值，有： 课本这里给出了两个相关的定理，证明了在把秩压缩之后存在F范数意义下的最有近似矩阵，证明较长。

对于SVD，把写到列向量里面，也就是，然后把按行向量写成 那么就有，如果A的秩=n，那么这个式子也可以表示为，通过控制n值来降秩，达到近似效果，课本有例题。

第十六章 PCA

16.1 总体PCA

数据的变量（特征）之间存在相关性会带来难度，PCA用了少数不相关的变量来代替这些变量。PCA先把数据在原来的各个轴上规范化处理，然后对原来的坐标轴做旋转变换，其中第一坐标轴是方差最大的方向，其余坐标轴方差逐渐变小（当然也是找最大，不过和前面的方向相比更小）。

PCA的定义：对于m维的随机变量，均值向量，协方差矩阵，这里的方差。考虑一个对x的线性变换，即：。如果这个线性变换满足一定的要求，就是PCA。这些要求是：

• 是单位向量，也就是满足。
• 和不相关，也就是。
• 是x的所有线性变换中方差最大的。是与不相关的x的所有线性变换中方差最大的，以此类推。

课本这里给出了一个定理和一种求PCA的方法，对于协方差矩阵，拿到它的特征值，对应的单位特征向量是，那么x的第k主成分就是， 这个第k主成分的方差是，也就是协方差矩阵的第k个特征值。

根据这个定理，有一个推论可以判断一个和x同维（当然也可以不同维，同维的时候叫总体主成分）的随机变量是不是x的主成分，也就是从1到m分别是第一主成分到第m主成分：

1. ，A是一个正交矩阵。
2. y的协方差矩阵是一个对角矩阵，且对角上的元素单调不增。易知，这里的对角上的元素就是协方差矩阵的特征值。

对总体主成分y，有一些性质：

• y的协方差矩阵是对角矩阵。
• y的方差之和=x的方差之和，即，其中这里的就是协方差矩阵的特征值。
• 第k个主成分和变量（x的第i维）的相关系数称为因子负荷量，即

那么怎么定主成分个数k？课本给出了两个定理，不管了。直接看到指标，方差贡献率定义为，也就是第k个成分和其他方差之和的比；k个主成分的累计方差贡献率定义为，累计方差贡献率反映了主成分保留信息的比例，但不能反映对某个原有的维度保留信息的比例，这个时候定义一个专门第k个主成分对原有变量的贡献率，即。一般可以考虑累计方差贡献率达到一定程度的前k个主成分，比如70%。

一般PCA还会在用之前对各个维度做归一化，然后总体主成分的性质就会更好一点，变成：（懒得打了）

16.2 样本PCA

前面说的总体PCA是对所有样本的，一般来说没有这么大量的数据，就做n次独立观测得到样本\bm{x}i，样本均值向量\bar{\bm{x}} = \frac{1}{n}\sum\limits{j=1}^n \bm{x}j，样本协方差矩阵S=[s{ij}]{m \times m}\ where\ s{ij} = \frac{1}{n-1}\sum\limits_{k=1}^n (x_{ik} - \bar{x}i)(x{jk} - \bar{x}j)。考虑回线性变换，这里的和上面总体的不一样，这里是对总体里面的各个维度做线性变换，而这里是直接对各个样本做线性变换，即\bm{y}i = a_i^T \bm{x} = a{1i}\bm{x_1} + a{2i}\bm{x_2} + … + a_{mi}\bm{x_m}，那么这里的的样本均值\bar{y}i = \frac{1}{n}\sum\limits{j=1}^n a_i^T \bm{x}_j = a_i^T \bar{\bm{x}}，样本方差var(y_i) = a_i^T S a_i，cov(y_i, y_k) = a_i^T S a_k。样本主成分的定义类似，不再给出。

PCA有两种方法，传统方法使用相关矩阵的特征值分解算法，现在常用数据矩阵的奇异值分解算法。

在传统方法中，步骤为：

1. 各个维度内归一化；
2. 计算样本相关矩阵：R = [r_{ij}]{m \times m} = \frac{1}{n-1}XX^T,\ where\ r{ij} = \frac{1}{n-1}\sum\limits_{l=1}^n x_{il}x_{lj}
3. 求出R的k个特征值和对应的特征向量。即，求解，得到的各个解按大到小排列，求方差贡献率达到要求对应的k值，对应的特征向量就是，这是个列向量。
4. 求出k个样本的主成分，也就是对应的线性变换，这里并没有代入具体观测到的样本
5. 计算k个主成分和原变量的相关系数，以及k个主成分对原变量的贡献率
6. 把规范化的样本代入，即对第j个样本（样本是列向量）的第i个主成分是，这里是个数，因为是列向量。

课本的例题把这个过程走了一遍。

数据矩阵的奇异值分解算法中，