统计学习方法 十到十六章笔记
第十章 隐马尔可夫模型
10.1 隐马尔可夫模型的定义
隐马尔可夫模型包含观测,状态和相应的转移,具体的记号不在给出。只给出其性质:其中i是状态而o是观测:
HMM可以用来标注,这个时候状态就是标记。标注问题是给定观测的序列,预测对应的标记序列。
HMM的一个比较易懂的例题在P195。
HMM的具体问题在下面三个章节分别讲述。
10.2 概率计算算法
这里解决的问题是,给定模型
暴力的话,方法如下:
a是状态转移概率,
但是这里有很多这样的状态,随着时间T跳转,计算量是
这个时间复杂度太高了,想办法改进,使用前向-后向算法。
前向算法中,定义前向概率:
注意,这里的前向概率
因此有了前向算法:
(2)式琢磨一下,也可以很容易推出来。(3)式想到
前向算法的例子在课本P200。
后向算法中和前向算法相反,定义后向概率:
就是在t时刻的第i个状态,会让它后面发生这样的观测的概率。
有了前向概率和后向概率,可以得到一些公式:
- 给定模型
和观测 ,求某时刻 状态的概率:公式见课本P202,这种东西不好推导。 - 给定模型
和观测 ,求某时刻 状态和下一个时刻 的状态分别为给定的 , 的概率。 - 在给定观测下状态出现的期望值、由状态转移的期望值和由状态i转移到j的期望值
10.3 学习算法
上面一节是给定了参数,跑预测用的。我们可能更希望有方法估计参数。
可以直接用极大似然估计,但是这样的估计需要大量标注,下面介绍无监督学习的算法,称为Baum-Welch算法。
课本这里一笔带过了,推导估计也不是很简单的事情,这里就贴个结论吧。
10.4 预测算法
预测算法中,有两个算法可以估计中间某个状态的概率。
在近似算法中,
这个公式来自10.2节里面的P202公式。但是里面的状态序列未必会全部发生。
维特比算法是一种dp的思路,
这里的
例子见课本P210。
第十一章 条件随机场
11.1 概率无向图模型
概率无向图模型也叫马尔可夫随机场。
这一节都是一些定义的内容,知道就可以了。
- 成对马尔可夫性:在无向图中两个不相邻的节点u,v,别的节点是O,对应的随机变量表示为Y,满足:
- 局部马尔可夫性:给定任一节点v,W是一个和v相连的节点,O是除v和W外的节点,满足:
,看起来好像是,给定一个节点的时候,他的相邻节点和另外的节点独立;以及在 时,满足 - 全局马尔可夫性:取节点集合A,B,C,其中C把A,B分开,也就是不连通,满足
这三个性质等价。
对于联合分布,如果满足三个之中的一个,就是概率无向图模型。
对于概率无向图模型,可以进行因子分解,也就是团。团就是离散数学里面的
有了最大团,联合概率分布可以写成所有最大团的乘积,也就是
11.2 CRF的定义与形式
一般的CRF,满足
定义里面不要求X和Y有相同结构,不过一般都使用相同结构的X和Y。
在课本中,使用线性链CRF,也就是只有相邻的
线性链CRF的参数化形式如下:
课本的例子在P220。
线性链CRF可以用简化形式或者矩阵形式表示。
CRF中,
这里写出矩阵形式的公式,简化形式看课本吧。
矩阵形式下的例子在课本P224,较易看懂。
11.3 CRF的概率计算问题
这里解决的是给定CRF
前向向量:初始化:
递推:
也有后向概率:初始化:
递推:
同样的,这里的概率公式和期望值都可以算出来,在课本P225。这里不再给出。
11.4 CRF的学习算法
这个东西我不想看。
11.5 CRF的预测算法
使用的是维特比算法。
例子在P234。
这里的特征函数就是t和
第十四章 聚类方法
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,如果任意两个样本
对于类(一堆样本)这个尺度,还有一些别的性质:
- 类的均值,或者叫类的中心:$\bar{x}G = \frac{1}{n_G} \sum\limits{i=1}^{n_G}x_i$
- 类的直径:
- 类的样本散布矩阵:
- 类的样本协方差矩阵:
,m是样本维数
然后对于类之间,还有另外的一些定义(比较好理解):
14.2 层次聚类
也就是对某一个层次聚类,然后合并或者继续分裂。
聚合聚类算法:
这里的距离矩阵D是一个对称矩阵,而且对角线上元素为0。
这个过程完全就是遍历贪心,课本例子很直观。
14.3 k-means聚类
这里的聚类事实上是一种划分,即不重不漏的分类。可以用一个函数来建模这个关系,即
k-means方法使用的损失函数是各个类到类中心的l2距离之和。算法为:
课本的例子很容易理解。
k-means的特点:
- 基于划分;
- 实现指定类别数;
- 使用欧氏距离表示样本之间的距离,使用样本均值表示类别;
- 算法是迭代的,是一种启发式方法,不保证是全局最优;
- 聚类结果和初始选择是相关的,不同的初始选择可以得到不同的聚类结果;
- 这个k值一般需要搜索,满足这样的关系:
第十五章 奇异值分解
终于到了这个耳熟能详但是又不会用的东西了。
15.1 SVD的定义与性质
对实矩阵的SVD,就是对一个矩阵进行因子分解,其中A的形状是(m, n):
这里的
不过一般常用的是紧奇异值分解和截断奇异值分解,其中紧奇异值分解和原来的SVD(又称完全奇异值分解)等价,而截断SVD比原始矩阵低秩。SVD的提出就是为了对矩阵进行压缩,其中截断SVD就是有损压缩。
紧奇异值分解的矩阵可以比完全SVD更小,紧的SVD的矩阵大小是和待分解矩阵的秩相关的。对于矩阵A,
截断奇异值分解和紧奇异值分解类似,不过会让
SVD的几何解释也是有意义的。对于一个给定的矩阵A,形状是(m, n),可以考虑变换
在SVD中,U和V都是正交矩阵,那么V的列向量构成了
SVD的几何解释可以对标准正交基进行变换看效果,课本的例子比较直观。
而且SVD直觉上,感觉像对A做行变换之后得到的奇异值对角阵
SVD还有一些相关的性质:
和 的SVD也是存在的,而且和A的SVD结果相关,具体不在这里给出。 - 对于
,右乘 得到 ,考察矩阵的第j列,就有: ,那么类似地取个转置,就有 和 。 - SVD中的
是唯一的,而U和V不唯一,也就是给定一个A,那么对应的 唯一。 - A和
的秩相等,也和 的正奇异值个数相等(包括重复的奇异值)。 - 课本这里还有一个很长的性质,不知道能干嘛。
15.2 SVD的计算
SVD的求法看起来比较机械化。步骤为:
- 求
的特征值和特征向量。也就是,求解 ,把里面的特征值从大到小排列。然后把 代入得到特征向量。 - 把特征向量单位化之后横向拼起来,得到正交矩阵V:
- 构造全0矩阵,形状为(m, n),对角元素填入
,得到 - U分成两部分,对于前r个特征值,有
,然后对于后面的m-r个特征值,求出 的零空间(Null)的一组标准正交基(其中 ,也就是,要求 的零空间标准正交基,解出来 之后单位化即可)。把两个得到的这一堆列向量都横向拼起来就是U。
课本有一个SVD的计算,把那个掌握了之后应该就会计算SVD了。不过这里的SVD计算是理论上的,工程上的计算并不是这样算的。课本没给出来。
15.3 SVD与矩阵近似
矩阵的F范数就是各个位置平方,然后全局求和后取开方。这里有一个引理,对于A和他的各个奇异值,有:
课本这里给出了两个相关的定理,证明了在把秩压缩之后存在F范数意义下的最有近似矩阵,证明较长。
对于SVD,把
那么就有
第十六章 PCA
16.1 总体PCA
数据的变量(特征)之间存在相关性会带来难度,PCA用了少数不相关的变量来代替这些变量。PCA先把数据在原来的各个轴上规范化处理,然后对原来的坐标轴做旋转变换,其中第一坐标轴是方差最大的方向,其余坐标轴方差逐渐变小(当然也是找最大,不过和前面的方向相比更小)。
PCA的定义:对于m维的随机变量
是单位向量,也就是满足 。 和 不相关,也就是 。 是x的所有线性变换中方差最大的。 是与 不相关的x的所有线性变换中方差最大的,以此类推。
课本这里给出了一个定理和一种求PCA的方法,对于协方差矩阵
根据这个定理,有一个推论可以判断一个和x同维(当然也可以不同维,同维的时候叫总体主成分)的随机变量
,A是一个正交矩阵。 - y的协方差矩阵是一个对角矩阵,且对角上的元素单调不增。易知,这里的对角上的元素就是协方差矩阵的特征值。
对总体主成分y,有一些性质:
- y的协方差矩阵是对角矩阵。
- y的方差之和=x的方差之和,即
,其中这里的 就是协方差矩阵的特征值。 - 第k个主成分和变量
(x的第i维)的相关系数称为因子负荷量,即
那么怎么定主成分个数k?课本给出了两个定理,不管了。直接看到指标,方差贡献率定义为
一般PCA还会在用之前对各个维度做归一化,然后总体主成分的性质就会更好一点,变成:(懒得打了)
16.2 样本PCA
前面说的总体PCA是对所有样本的,一般来说没有这么大量的数据,就做n次独立观测得到样本$\bm{x}i
样本主成分的定义类似,不再给出。
PCA有两种方法,传统方法使用相关矩阵的特征值分解算法,现在常用数据矩阵的奇异值分解算法。
在传统方法中,步骤为:
- 各个维度内归一化;
- 计算样本相关矩阵:$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}$
- 求出R的k个特征值和对应的特征向量。即,求解
,得到的各个解按大到小排列,求方差贡献率达到要求对应的k值,对应的特征向量就是 ,这是个列向量。 - 求出k个样本的主成分,也就是对应的线性变换
,这里并没有代入具体观测到的样本 - 计算k个主成分
和原变量 的相关系数 ,以及k个主成分对原变量 的贡献率 - 把规范化的样本代入,即对第j个样本(样本是列向量)的第i个主成分是
,这里是个数,因为 是列向量。
课本的例题把这个过程走了一遍。
数据矩阵的奇异值分解算法中,