《机器学习》西瓜书学习笔记（五）

2017-10-24 本文已影响0人 hmta_dhs

上一篇笔记在这里：《机器学习》西瓜书学习笔记（四）

第七章贝叶斯分类器

7.1 贝叶斯分类器

假设有N种可能的类别标记，即Y={c₁,c₂,...,c_N},λ_ij是将一个真实标记为c_j的样本误分类为c_i所产生的损失。在样本x上的“条件风险”是

我们的任务是寻找一判定准则h：X→Y以最小化总体风险

可以看出，要想最小化总体风险，仅需最小化条件风险，即

h^*称为贝叶斯最优分类器，与之对应的总体风险R(h^*)称为贝叶斯风险。1-R(h^*)反映了最好性能。

若最小化分类错误率，则误判损失λ_ij可写为

此时条件风险

于是，最小化分类错误率的贝叶斯最优分类器是

贝叶斯定理

7.2 极大似然估计

记关于类别c的类条件概率为P(x|c)，假设P(x|c)具有确定的形式并且被参数向量θ_c唯一确定，则我们的任务就是利用训练集D估计参数θ_c。为明确起见，将P(x|c)记为P(x|θ_c)。

令D_c表示训练集D中第c类样本组成的集合，假设这些样本是独立同分布的，则参数θ_c对于数据集D_c的似然是

对θ_c进行极大似然估计，就是去寻找能最大化似然P(D_c|θ_c)的参数值^θ_c。

连乘操作容易产生下溢，通常使用对数似然（log-likelihood）

例如，在连续属性条件下，假设概率密度函数P(x|c)~N(μ_c,σ_c²)，则极大似然估计为

7.3 朴素贝叶斯分类器

朴素贝叶斯分类器（Naive Bayes Classifier）采取了“属性条件独立性假设”（attribute conditional independence assumption）：对已知类别，假设所有属性相互独立，有

朴素贝叶斯分类器的表达式

训练过程如下：
令D_c表示训练集D中第c类样本组成的集合，若有充足的独立同分布样本，则可容易地估计类先验概率

对离散属性而言，令D_{c,x_i}表示D_c中在第i个属性为x_i为样本组成的集合，则条件概率P(x_i|c)可估计为

对连续属性可考虑概率密度函数，假定p(x_i|c)~N(μ_c,i,σ_c,i²)，其实μ_c,i和σ_c,i²分别是第c类样本在第i个属性上取值的均值和方差，则有

拉普拉斯修正（Laplacian correction）：
若某个属性值在训练集中没有于某个类同时出现过，直接算的话就为0了。为了避免这个情况，要有一个修正：

N表示D中可能的类别数，N_i表示第i个属性可能的取值数。

7.4 半朴素贝叶斯分类器

半朴素贝叶斯分类器的基本想法是适当考虑一部分属性间的相互依赖信息。“独依赖”就是假设每个属性在类别之外最多仅依赖于一个其他属性，即

其中pa_i为属性x_i所依赖的属性，称为x_i的父属性。
最直接的做法是假设所有属性都依赖于同一个属性，称为“超父”（super-parent），然后通过交叉验证等模型选择方法来确定超父属性，由此形成了SPODE（Super-Parent ODE）方法。

TAN（Tree Augmented naive Bayes）则是在最大带权生成树算法的基础上，有以下步骤：

计算任意两个属性之间的条件互信息（conditional mutual information）

以属性为结点构建完全图，任意两个结点之间边的权重设为I(x_i,x_j|y)；
构建次完全图的最大带权生成树，挑选根变量，将边置为有向；
加入类别结点y，增加从y到每个属性的有向边。

AODE（Averaged One-Dependent Estimator）是一种基于集成学习机制、更为强大的独依赖分类器。

其中D_{x_i}是在第i个属性上取值为x_i的样本的集合，m'为阈值常数。显然，AODE需估计P(c,x_i)和P(x_j|c,x_i)

7.5 贝叶斯网

贝叶斯网亦称“信念网”，借助有向五环图来刻画属性之间的依赖关系。

7.2 西瓜问题的一种贝叶斯网结构

7.5.1 结构

以上图为例，联合概率分布定义为

贝叶斯网中三个变量之间的典型依赖关系

“有向分离”：

找出有向图中所有V型结构，在V型结构的两个父结点之间的加上一条无向边。
将所有有向边变成无向边。

由此产生的无向图称为“道德图”，该过程称为“道德化”。

图7.2对应的道德图

7.5.2 学习

评分函数：给定训练集D={x₁,x₂,...,x_m}，贝叶斯网B={G,Θ}在D上的评分函数可写为

其中，|B|是贝叶斯网的参数个数；f(θ)表示描述每个参数θ所需的字节数；而

是贝叶斯网B的对数似然。评分函数的第一项是计算编码贝叶斯网B所需的字节数，第二项是计算B所对应的概率分布P_B对D描述得有多好。我们要做的是寻找一个贝叶斯网B使评分函数s(B|D)最小。

若f(θ)=1，即每个参数用1字节描述，则得到AIC（Akaike Information Criterion）评分函数

若f(θ)=(1/2)log(m)，即每个参数用(1/2)log(m)字节描述，则得到BIC（Bayesian Information Criterion）评分函数

若f(θ)=0，则学习任务退化为极大似然估计。

7.5.3 推断

7.6 EM算法

隐变量：未观测变量。
令X表示已观测变量集，Z表示隐变量集，Θ表示模型函数。若欲对Θ做极大似然估计，则应最大化对数似然

然而由于Z是隐变量，上式无法直接求解。此时我们可通过对Z计算期望，来最大化已观测数据的对数“边际似然”（marginal likelihood）

EM算法：若参数Θ已知，则可根据训练数据推断出最优隐形变量Z的值（E步）；反之，若Z的值已知，则可方便地对参数Θ做极大似然估计（M步）。
以初始值Θ⁰为起点，对上式可迭代执行以下步骤直至收敛：

基于Θ^t推断隐变量Z的期望，记为Z^t；
基于已观测变量X和Z^t对参数Θ做极大似然估计，记为Θ^t+1

进一步，若我们不是取Z的概率分布P(Z|X,Θ^t)，则EM算法的两个步骤是：

E步（Expectation）：以当前参数Θ^t推断变量分布P(Z|X,Θ^t)，并计算对数似然LL(Θ|X,Z)关于Z的期望

M步（Maximization）：寻找参数最大化期望似然，即

第十四章概率图模型

14.1 概率图模型

推断（inference）：利用已知变量推测未知变量的分布，其核心是如何基于可观测变量推测出未知变量的条件分布。
假定所关心的变量集合为Y，可观测变量集合为O，其他变量的集合为R，“生成式”（generative）模型考虑联合分布P(Y,R,O)，“判别式”（discriminative）模型考虑条件分布P(Y,R|O).给定一组观测变量值，推断就是要由P(Y,R,O)或P(Y,R|O)得到条件概率分布P(Y|O).
直接利用概率求和的方法消去变量R的复杂度是O(2^|Y|+|R|)
概率图模型（probabilistic graphical model）是一类用图来表达变量相关关系的概率模型。结点表示随机变量，边表示变量之间的概率关系。有向图称为贝叶斯网（Bayesian network），无向图称为马尔科夫网（Markov network）。
隐马尔科夫模型（Hidden Markov Model，简称HMM）是结构最简单的动态贝叶斯网（dynamic Bayesian network），这是一种著名的有向图模型，主要用于时序数据建模。

隐马尔科夫模型中的变量可分为两组：第一组状态变量{y₁,y₂,...,y_n}，其中y_i∈Y表示第i时刻的系统状态。通常假定状态变量是隐藏的，亦称隐变量；第二组观测变量{x₁,x₂,...,x_n}，其中x_i∈X表示第i时刻的观测值。在隐马尔科夫模型中，系统通常在多个状态{s₁,s₂,...,s_N}之间转换，因此状态空间Y通常是离散的，而X可以是离散的也可以是连续的，为便于讨论，我们仅考虑离散性观测变量。
马尔科夫链（Markov chain）：系统下一时刻的状态仅由当前状态决定，不依赖于以往的任何状态。基于这种依赖关系，所有变量的联合概率分布为

14.2 马尔科夫随机场

马尔科夫随机场（Markov Random Field，MRF）是典型的马尔科夫网，结点表示变量，边表示变量之间的依赖关系。
势函数（potential functions）或因子（factor）：定义在变量子集上的非负实函数，用于定义概率分布函数。

团（clique）：任意两结点都有边连接的节点子集。
极大团（maximal clique）：在一个团中加入另外任何一个结点都不再形成团。
在马尔科夫随机场中，联合概率分布基于团分解成多个因子的乘积。对于n个变量x={x₁,x₂,...,x_n}，所有团构成的集合为C，与团Q∈C对应的变量集合记为x_Q，则联合概率P(x)定义为