机器学习及其Python实践 (6).pdf

机器学习及其Python实践第6章 概率图模型与概率推理第6章 概率图模型与概率推理所有人都会死（大前提）。一般知识（相当于模型）苏格拉底是人（小前提），所以苏格拉底会死（结论）。将一般知识运用于个体（相当于使用模型对样本进行预测）逻辑推理 使用谓词逻辑（predicate logic）进行形式化描述 使用计算机进行自动化的逻辑推理，例如机器定理证明 ：是人。：会死。.苏格拉底，苏格拉底第6章 概率图模型与概率推理 如果知识、条件都是确定的，那就可以使用逻辑推理推导出确定性的结论。逻辑推理的整个过程都是确定的 而对于随机现象则需要用概率模型来描述知识，用随机变量表示已知条件和未知结论，然后通过概率演算由已知概率分布计算出未知概率分布，这就是概率推理 可以用有向图或无向图来描述概率模型，这就是概率图模型6.1 贝叶斯网 为实际问题建立概率模型，如果问题具有比较明确的诱因-结果关系（简称因果关系，或依赖关系），则可以使用有向无环图（Directed Acyclic Graph，缩写DAG）来描述这样的概率模型 使用有向无环图描述的概率模型被称作贝叶斯网（Bayesian network）例如在疾病诊断问题中，病因（诱因）与症状（结果）之间就具有比较明确的因果关系，其概率模型可以使用贝叶斯网来描述6.1 贝叶斯网 联合概率分布及其推理 联合概率分布,边缘概率分布 和 条件概率分布|和|,=|=|.（6 2）=1,2,，=1,2,=|=|.（6 3）,=,|=,|=,|.（6 4）,=,=,=,.（6 5）6.1 贝叶斯网 联合概率分布及其推理 联合概率分布,概率推理已知联合概率分布，求边缘概率、条件概率 简化概率符号将离散型概率分布 =或连续型概率密度 统一记作 =，=,，|=|.=，,=,，=|.=,;,;,;.6.1 贝叶斯网 联合概率分布及其推理 联合概率分布,概率推理已知联合概率分布，求边缘概率、条件概率 求边缘概率：求和消元 =,，=,.（6 6）=,，同理可求 、.（6 7）6.1 贝叶斯网 联合概率分布及其推理 联合概率分布,概率推理已知联合概率分布，求边缘概率、条件概率 求边缘概率：求和消元 求条件概率：贝叶斯公式|=,=|=,=|.（6 8）6.1 贝叶斯网 联合概率分布及其推理 条件概率的计算技巧|=,=|=,=|.（6 8）|=,=，对所有的 =1,=1 .（6 9）,或 ，对所有的 .=,=.计算|，6.1 贝叶斯网 相互独立与条件独立6.1 贝叶斯网 生成式或判别式模型 生成式（generative）模型指的是联合概率分布，例如,、,等，它完整描述了随机变量间的概率分布 判别式（discriminative）模型指的是某个特定的条件概率分布（或与其等价的判别函数），例如|、,|，或者如支持向量机中的分类决策（或称判别）函数 =+等6.1 贝叶斯网 贝叶斯网的定义与概率推理 贝叶斯网是一个有向无环图，由结点及结点间的有向边组成 结点 结点到的有向边 条件概率分布|X1X2X1X2X3P(X1)P(X2|X1)P(X2|X1)P(X1)P(X3|X2)X2X1X3P(X2)P(X1|X2)P(X3|X2)X1P(X1)X3P(X3)X2P(X2|X1,X3)1,2,=1|.6.1 贝叶斯网 贝叶斯网的定义与概率推理 贝叶斯网中的条件独立定理6-1 贝叶斯网中的每个结点在给定父结点时，都将条件独立于它的非后代结点（其中包括其父结点的父结点，但不包括子结点的子结点）X1X2XX5X6X4X3X7X86.1 贝叶斯网 贝叶斯网的定义与概率推理 贝叶斯网中的条件独立定理6-2 贝叶斯网中结点的父结点、子结点以及子结点的父结点所构成的集合，被称为结点的马尔可夫覆盖（Markov blanket），记作 。若给定结点的马尔可夫覆盖 ，则与非 中的结点条件独立，即X1X2XX5X6X4X3X7X8,|=|=|，.6.1 贝叶斯网 贝叶斯网的定义与概率推理 贝叶斯网中的条件独立6.1 贝叶斯网 贝叶斯网的构造 首先，对问题进行分析并发现其中存在哪些随机变量，为每个随机变量建立一个结点；然后找出各结点之间的依赖关系，为存在直接依赖关系（即直接因果关系）的结点添加有向边；最后再确定各结点的概率分布，无父结点时为先验概率，有父结点时为条件概率|。结点及其依赖关系被称作贝叶斯网的结构，各结点的概率分布被称作贝叶斯网的参数 人工构造贝叶斯网的结构，然后通过样本数据估计各结点的概率分布，这被称作参数学习。也有人在尝试通过样本数据自动学习贝叶斯网的结构，即结构学习6.1 贝叶斯网 贝叶斯网的推理贝叶斯公式、求和消元法、和-积消元算法、信念传播算法6.1 贝叶斯网 贝叶斯网的推理 基于联合概率计算条件概率 贝叶斯公式 也可以将条件概率的计算问题，转化成边缘概率的计算问题阚道宏6.1 贝叶斯网 贝叶斯网的推理 基于联合概率计算条件概率 贝叶斯公式 也可以将条件概率的计算问题，转化成边缘概率的计算问题6.1 贝叶斯网 贝叶斯网的推理 基于联合概率计算边缘概率：求和消元法 给定联合概率分布,，计算边缘概率 =,，对所有的 .（6 19）X1X2X3X5X4 1,2,3,4,5=15|=1 21 32 43 53.（6 20）6.1 贝叶斯网 贝叶斯网的推理 基于联合概率计算边缘概率：求和消元法X1X2X3X5X4 1,2,3,4,5=15|=1 21 32 43 53.（6 20）5=1,2,3,4 1,2,3,4,5=4321 1,2,3,4,5=4321 1 21 32 43 53.（6 21）6.1 贝叶斯网 贝叶斯网的推理 基于联合概率计算边缘概率：求和消元法X1X2X3X5X4 1,2,3,4,5=15|=1 21 32 43 53.（6 20）2,3=1,4,5 1,2,3,4,5=541 1,2,3,4,5=541 1 21 32 43 53.（6 22）阚道宏6.1 贝叶斯网 贝叶斯网的推理 基于联合概率计算边缘概率：求和消元法 2,3=541 1 21 32 43 53=325 534 431 1 21=325 534 43122注：记 122=1 1 21=321225 534 43注：提取公因子122=321224335 53注：记 433=4 43=32122433533注：记 533=5 53.（6 27）和-积消元算法、信念传播（belief propagation）算法：提取公因子，并运用动态规划思想对联合概率进行求和消元。6.2 MCMC算法基础 马尔可夫链蒙特卡罗（Markov Chain Monte Carlo，缩写MCMC）算法 MCMC采样算法 MCMC最优化算法 MCMC互评算法等 MCMC算法的算法基础是马尔可夫链和蒙特卡罗仿真6.2 MCMC算法基础 蒙特卡罗仿真（Monte Carlo simulation）通过大量试验，然后对试验数据进行统计分析，发现客观规律性 蒙特卡罗仿真就是一种统计模拟方法，其含义是按给定概率分布 在计算机上模拟采样，每次采样相当于一次随机试验，然后对所生成的样本数据进行统计分析 为问题建立概率模型，该模型的统计量与问题的解之间存在某种对应关系 按照概率模型在计算机上模拟采样，然后通过样本数据的统计量求得问题的近似解6.2 MCMC算法基础 蒙特卡罗仿真（Monte Carlo simulation）举例：求圆周率 ，进而求得：=4 .=扇形面积正方形面积=14 1212=14.通过伪随机数技术让计算机随机生成个位于正方形区域内的样本点,，然后统计落在扇形区域内的样本点个数6.2 MCMC算法基础 蒙特卡罗仿真（Monte Carlo simulation）应用蒙特卡罗仿真方法的三个主要步骤 构造与待求解问题等价的概率模型 按照概率模型（即概率分布）进行模拟采样 通过样本统计量求得问题的近似解 常用模拟采样算法给定某个概率分布 ，如何通过伪随机数技术在计算机上模拟采样，生成一个样本容量为且符合给定概率分布的数据集=1,2,呢？6.2 MCMC算法基础 蒙特卡罗仿真（Monte Carlo simulation）常用模拟采样算法 0,1 区间的均匀分布，记作(0,1)正态分布（或称高斯分布）,、,区间的均匀分布(,)线性同余法（linear congruential method）马特赛特旋转（Mersenne Twister）伪随机数函数：random()Box-Muller算法Python语言random模块提供的采样函数：gauss()、uniform()6.2 MCMC算法基础 蒙特卡罗仿真（Monte Carlo simulation）离散型概率分布：二项分布、多项分布阚道宏6.2 MCMC算法基础 蒙特卡罗仿真（Monte Carlo simulation）离散型概率分布：二项分布、多项分布阚道宏6.2 MCMC算法基础 蒙特卡罗仿真（Monte Carlo simulation）离散型概率分布：二项分布、多项分布p1=0.3p2=0.5 p3=0.2s10.3s00s20.8s31p1=0.3p2=0.5p3=0.2s00s10.3s20.8轮盘指针轮盘赌采样算法：=1+1+，=1,2,.阚道宏6.2 MCMC算法基础 蒙特卡罗仿真（Monte Carlo simulation）离散型概率分布：二项分布、多项分布p1=0.3p2=0.5 p3=0.2s10.3s00s20.8s31p1=0.3p2=0.5p3=0.2s00s10.3s20.8轮盘指针轮盘赌采样算法：=1+1+，=1,2,.6.2 MCMC算法基础 蒙特卡罗仿真（Monte Carlo simulation）常用模拟采样算法 正态分布（或称高斯分布）,、,区间的均匀分布(,)二项分布、多项分布 复杂的连续型概率分布？阚道宏6.2 MCMC算法基础 蒙特卡罗仿真（Monte Carlo simulation）常用模拟采样算法 正态分布（或称高斯分布）,、,区间的均匀分布(,)二项分布、多项分布 复杂的连续型概率分布？接受-拒绝采样算法阚道宏6.2 MCMC算法基础 蒙特卡罗仿真（Monte Carlo simulation）常用模拟采样算法 正态分布（或称高斯分布）,、,区间的均匀分布(,)二项分布、多项分布 复杂的连续型概率分布？接受-拒绝采样算法6.2 MCMC算法基础 贝叶斯网的近似推理 包含个结点 1,2,的贝叶斯网，它所描述的是个随机变量 1,2,的联合概率分布 1,2,依据联合概率分布，查询其中某个或某几个随机变量的边缘概率或条件概率，这就是贝叶斯网的概率推理 在面对复杂概率模型和多变量概率推理时，精确推理的复杂度会呈指数增长，因此需要设计能够在较低复杂度下求得近似解的近似推理方法6.2 MCMC算法基础 贝叶斯网的近似推理 换一种符号来标记随机变量 1,2,，用表示待查询的变量、表示给定的证据变量、表示剩余的其他变量 概率推理就是给定联合概率分布,，希望查询随机变量的边缘概率 或条件概率|6.2 MCMC算法基础 贝叶斯网的近似推理 贝叶斯网的直接采样 对于多变量联合概率分布 1,2,，该如何进行模拟采样呢？一轮采样：对个随机变量 1,2,逐个采样，然后才能得到一个样本数据=1,2,1,2,=1|.数据集=1,2,=1,2,，=1,2,.6.2 MCMC算法基础 贝叶斯网的近似推理 贝叶斯网的直接采样 式6-37中的各概率项需通过联合概率分布 1,2,计算出来，这样的计算往往太过复杂 贝叶斯网是个例外，它非常适合使用直接采样法进行采样，因为贝叶斯网的联合概率分布 1,2,天生就是由依赖关系建立起来的 1,2,=1|.1,2,=1 1 21 1.（6 37）6.2 MCMC算法基础 贝叶斯网的近似推理 贝叶斯网的直接采样 查询边缘概率？查询条件概率|=？1,2,=1|.数据集=1,2,=1,2,，=1,2,.阚道宏6.2 MCMC算法基础 贝叶斯网的近似推理 贝叶斯网的吉布斯采样 1 1+1=|6.2 MCMC算法基础 贝叶斯网的近似推理 贝叶斯网的吉布斯采样 查询条件概率|=？吉布斯采样的初始样本0是任意设定的，它能收敛吗？6.2 MCMC算法基础马尔可夫链 给定随机变量及其概率分布 ，在此基础上引入时间维度，观测随机变量随时间变化的过程 随机变量序列=1,2,+1,被称作是一个以为参数的随机过程（stochastic process）广义上，随机过程被定义为一组随时间（或空间，或某种参数）变化的随机变量的全体 平稳过程（stationary process）独立同分布采样P(X 1)P(X 2)P(X t)X 1 X 2X tX t+1P(X t+1)1=2=+1=.6.2 MCMC算法基础 马尔可夫链阚道宏6.2 MCMC算法基础 马尔可夫链阚道宏6.2 MCMC算法基础 马尔可夫链状态转移矩阵6.2 MCMC算法基础 马尔可夫链=,1=1=1=.（6 38a）6.2 MCMC算法基础 马尔可夫链阚道宏6.2 MCMC算法基础 马尔可夫链 举例：股票市场，马尔可夫链,01上涨2平盘3下跌p11p13p12p22p33p31p21p23p32阚道宏6.2 MCMC算法基础 马尔可夫链 举例：股票市场，马尔可夫链,06.2 MCMC算法基础 马尔可夫链 马尔可夫链的收敛性31246.2 MCMC算法基础 马尔可夫链 马尔可夫链的收敛性阚道宏6.2 MCMC算法基础 马尔可夫链 马尔可夫链的收敛性=，=1,2,（6 39）6.2 MCMC算法基础 马尔可夫链 马尔可夫链的收敛性=，=1,2,（6 39）=.6.2 MCMC算法基础 马尔可夫链 随机向量的马尔可夫链一组随机变量=1,2,可被称作是一个维随机向量（random vector）X 0X 1 P(X 1|X 0)=AP(X 0)X t+1P(X t+1|X t)=A 0P(X 0)1P(X 1)=A 0X tP(X t|X t-1)=A tP(X t)=A t-1 t+1P(X t+1)=A tX t-1P(X t-1|X t-2)=A t-1P(X t-1)=A t-2阚道宏6.2 MCMC算法基础 马尔可夫链 随机向量的马尔可夫链一组随机变量=1,2,可被称作是一个维随机向量（random vector）X 0X 1 P(X 1|X 0)=AP(X 0)X t+1P(X t+1|X t)=A 0P(X 0)1P(X 1)=A 0X tP(X t|X t-1)=A tP(X t)=A t-1 t+1P(X t+1)=A tX t-1P(X t-1|X t-2)=A t-1P(X t-1)=A t-26.2 MCMC算法基础 马尔可夫链 随机向量的马尔可夫链 构建随机向量的平稳马尔科夫链 构造可遍历且满足细致平稳条件（或平稳分布条件）的状态转移概率（也即状态转移矩阵）逐次转移法或转移接受-拒绝法 1=1,2,11211.6.2 MCMC算法基础 马尔可夫链 随机向量的马尔可夫链 逐次转移法构建随机向量的平稳马尔科夫链 1=1,2,11211.X1t.Xkt.X1t+1.P(X1|.)Xdt.P(X1|.)P(Xk|.)P(Xd|.)Xdt-1.X t-1 t-1=A t-2X t t=A t-1P(Xd|.)6.2 MCMC算法基础 马尔可夫链 随机向量的马尔可夫链 转移接受-拒绝法构建随机向量的平稳马尔科夫链 1=1,2,11211.6.2 MCMC算法基础 马尔可夫链 随机向量的马尔可夫链 转移接受-拒绝法构建随机向量的平稳马尔科夫链 1=1,2,11211.6.2 MCMC算法基础 马尔可夫链 随机向量的马尔可夫链 转移接受-拒绝法构建随机向量的平稳马尔科夫链 1=1,2,11211.6.3 MCMC算法家族 基于马尔可夫链和蒙特卡罗仿真 Markov Chain Monte Carlo，缩写MCMC6.3 MCMC算法家族 基于马尔可夫链和蒙特卡罗仿真 Markov Chain Monte Carlo，缩写MCMC MCMC采样算法（例如MH采样算法）MCMC最优化算法（例如模拟退火算法）MCMC互评算法（例如PageRank网页排名算法）6.3 MCMC算法家族 MCMC采样算法（例如MH采样算法）6.3 MCMC算法家族 MCMC采样算法（例如MH采样算法）按边缘概率 对马尔可夫链进行采样：独立采样 独立-同分布采样X 0X 1 P(X 1|X 0=x0)P(X 0)X tP(X t|X t-1=xt-1)X 2P(X 2|X 1=x1)P(X 1)P(X 2)P(X t)X 1=x1X 2=x2X t=xtX 0=x0X 1=x1X 2=x2X t=xt=1=1=，=1,2,1=2=.6.3 MCMC算法家族 MCMC采样算法（例如MH采样算法）按转移概率|1对马尔可夫链进行采样：非独立采样 平稳马尔可夫链？X 0X 1 P(X 1|X 0=x0)P(X 0)X tP(X t|X t-1=xt-1)X 2P(X 2|X 1=x1)P(X 1)P(X 2)P(X t)X 1=x1X 2=x2X t=xtX 0=x0X 1=x1X 2=x2X t=xt=1=1=，=1,2,6.3 MCMC算法家族 MCMC采样算法（例如MH采样算法）按转移概率|1对马尔可夫链进行采样：非独立采样 平稳马尔可夫链？X 0X 1 P(X 1|X 0=x0)P(X 0)X tP(X t|X t-1=xt-1)X 2P(X 2|X 1=x1)P(X 1)P(X 2)P(X t)X 1=x1X 2=x2X t=xtX 0=x0X 1=x1X 2=x2X t=xt=1=1=，=1,2,6.3 MCMC算法家族 MCMC采样算法6.3 MCMC算法家族 MCMC采样算法算法第一步：使用逐次转移法构建平稳马尔可夫链的MCMC采样算法被称作吉布斯采样（Gibbs sampling）；使用转移接受-拒绝法构建平稳马尔可夫链的MCMC采样算法被称作MH采样（Metropolis-Hastings sampling）。6.3 MCMC算法家族 MCMC采样算法 使用MCMC采样算法对联合概率分布 =1,2,采样，得到一个样本容量为的数据集=1,2,概率近似推理：估计边缘概率或条件概率 估计某个函数 在概率分布 上的数学期望 应用于最优化问题：求目标函数 在定义域上的最优解 =1=1.min min，或 max max.6.3 MCMC算法家族 MCMC最优化算法 设目标函数 的定义域为，求 在上最小值（或最大值）的问题被称作最优化问题 定义域 被称作最优化问题的解空间（或称作解的状态空间）如果解空间是离散且有限的，则最优化问题被称为组合优化问题（注：连续解空间问题可通过离散化将其转成组合优化问题）对于组合优化问题，由于其解空间是有限的，因此理论上总可以通过穷举法（或称状态空间搜索）求得最优解 当解空间较大时，穷举法因算法复杂度过大而变得难以求解，这就需要寻求能在较低复杂度下求得近似解的方法6.3 MCMC算法家族 MCMC最优化算法 MCMC最优化算法就是一种能在较低复杂度下求得组合优化问题近似解的方法 为什么目标函数 会与概率分布 存在负相关呢？6.3 MCMC算法家族 MCMC最优化算法 三种特殊的马尔可夫链,0 等概率转移马尔可夫链=1 1 1 1 1 1 1 1 1.0=1 1 1 1 1 1 1 1 1 01020=1 1 1 .6.3 MCMC算法家族 MCMC最优化算法 三种特殊的马尔可夫链,0 等概率转移马尔可夫链 仅在相邻状态间转移的马尔可夫链120.10.50.930.50.540.50.10.9=11211222314132421323142433433444=0.90.50.10000.5000.50000.10.50.9.=0.41666667,0.08333333,0.08333333,0.41666667.6.3 MCMC算法家族 MCMC最优化算法 三种特殊的马尔可夫链,0 等概率转移马尔可夫链 仅在相邻状态间转移的马尔可夫链 固体退火过程6.3 MCMC算法家族 MCMC最优化算法 三种特殊的马尔可夫链,0 等概率转移马尔可夫链 仅在相邻状态间转移的马尔可夫链 固体退火过程6.3 MCMC算法家族 MCMC最优化算法 三种特殊的马尔可夫链,0 等概率转移马尔可夫链 仅在相邻状态间转移的马尔可夫链 固体退火过程6.3 MCMC算法家族 MCMC最优化算法 三种特殊的马尔可夫链 等概率转移马尔可夫链 仅在相邻状态间转移的马尔可夫链 固体退火过程6.3 MCMC算法家族 MCMC最优化算法 三种特殊的马尔可夫链 模拟退火算法（simulated annealing algorithm）6.3 MCMC算法家族 MCMC最优化算法 三种特殊的马尔可夫链 模拟退火算法（simulated annealing algorithm）遗传算法（Genetic Algorithm，缩写GA）6.3 MCMC算法家族 MCMC最优化算法 三种特殊的马尔可夫链 模拟退火算法（simulated annealing algorithm）遗传算法（Genetic Algorithm，缩写GA）6.3 MCMC算法家族 MCMC最优化算法 三种特殊的马尔可夫链 模拟退火算法（simulated annealing algorithm）遗传算法（Genetic Algorithm，缩写GA）求函数 =15+2 在0,1)区间的最大值6.3 MCMC算法家族 MCMC最优化算法 三种特殊的马尔可夫链 模拟退火算法（simulated annealing algorithm）遗传算法（Genetic Algorithm，缩写GA）求函数 =15+2 在0,1)区间的最大值6.3 MCMC算法家族 MCMC最优化算法 三种特殊的马尔可夫链 模拟退火算法（simulated annealing algorithm）遗传算法（Genetic Algorithm，缩写GA）求函数 =15+2 在0,1)区间的最大值6.3 MCMC算法家族 MCMC最优化算法 三种特殊的马尔可夫链 模拟退火算法（simulated annealing algorithm）遗传算法（Genetic Algorithm，缩写GA）求函数 =15+2 在0,1)区间的最大值6.3 MCMC算法家族 MCMC最优化算法 三种特殊的马尔可夫链 模拟退火算法（simulated annealing algorithm）遗传算法（Genetic Algorithm，缩写GA）直观理解MCMC最优化算法 确定性迭代和随机迭代是两大类不同的迭代算法 MCMC最优化算法属于随机迭代算法，其算法基础是马尔可夫链和蒙特卡罗仿真xf(x)6.3 MCMC算法家族 MCMC互评算法 =1 =2 =12=112112221212=1=2=16.3 MCMC算法家族 MCMC互评算法 PageRank网页排名算法.s.si.s有链接无链接Li个链接网页总数为n阚道宏6.3 MCMC算法家族 MCMC互评算法 PageRank网页排名算法.s.si.s有链接无链接Li个链接网页总数为n6.3 MCMC算法家族 MCMC互评算法 PageRank网页排名算法.s.si.s有链接无链接Li个链接网页总数为n6.3 MCMC算法家族 MCMC互评算法 PageRank网页排名算法 PageRank马尔可夫链的收敛性6.3 MCMC算法家族 MCMC互评算法 PageRank网页排名算法 PageRank马尔可夫链的收敛性=1 ，到没有链接+1 ，到有链接6.4 隐马尔可夫模型HMMHMM概率模型 一组随时间变化且不可观测的状态变量（或称作隐变量），记作1,2,一组对状态变量的观测变量，记作 1,2,状态仅条件依赖于其前一个状态1且条件概率|1不随时间变化 观测变量仅条件依赖于当前时刻的状态变量且条件概率|不随时间变化X1P(Y1)X2P(Y2|Y1)XtP(Yt|Yt-1)Y1 Y2YtP(X1|Y1)P(X2|Y2)P(Xt|Yt)XNP(YN|YN-1)YNP(XN|YN)XtP(Yt|Yt-1)YtP(Xt|Yt)1,2,1,2,=1 11=2 1.（6 53）你好你早我好特征 x1.xN特征 x1.xN特征 x1.xN音素 y1.yN音素 y1.yN音素 y1.yN6.4 隐马尔可夫模型HMM HMM概率模型 HMM形式化表示：,状态空间：=1,2,观测空间：=1,2,状态转移矩阵（状态转移概率）：=，=|1=状态观测矩阵（状态观测概率）：=，=|=状态的初始概率分布：=1,2,，1=X1P(Y1)X2P(Y2|Y1)XtP(Yt|Yt-1)Y1 Y2YtP(X1|Y1)P(X2|Y2)P(Xt|Yt)XNP(YN|YN-1)YNP(XN|YN)XtP(Yt|Yt-1)YtP(Xt|Yt)=,6.4 隐马尔可夫模型HMM HMM概率模型 HMM形式化表示：,HMM观测样本的生成过程：=,X1P(Y1)X2P(Y2|Y1)XtP(Yt|Yt-1)Y1 Y2YtP(X1|Y1)P(X2|Y2)P(Xt|Yt)XNP(YN|YN-1)YNP(XN|YN)XtP(Yt|Yt-1)YtP(Xt|Yt)6.4 隐马尔可夫模型HMM HMM概率模型 HMM形式化表示：,HMM观测样本的生成过程：=,HMM的三个基本问题：1,2,1,2,X1P(Y1)X2P(Y2|Y1)XtP(Yt|Yt-1)Y1 Y2YtP(X1|Y1)P(X2|Y2)P(Xt|Yt)XNP(YN|YN-1)YNP(XN|YN)XtP(Yt|Yt-1)YtP(Xt|Yt)6.4 隐马尔可夫模型HMM HMM概率模型 HMM形式化表示：,HMM观测样本的生成过程：=,HMM的三个基本问题：1,2,1,2,X1P(Y1)X2P(Y2|Y1)XtP(Yt|Yt-1)Y1 Y2YtP(X1|Y1)P(X2|Y2)P(Xt|Yt)XNP(YN|YN-1)YNP(XN|YN)XtP(Yt|Yt-1)YtP(Xt|Yt)6.4 隐马尔可夫模型HMM HMM概率模型 HMM形式化表示：,HMM观测样本的生成过程：=,HMM的三个基本问题：1,2,1,2,X1P(Y1)X2P(Y2|Y1)XtP(Yt|Yt-1)Y1 Y2YtP(X1|Y1)P(X2|Y2)P(Xt|Yt)XNP(YN|YN-1)YNP(XN|YN)XtP(Yt|Yt-1)YtP(Xt|Yt)阚道宏6.4 隐马尔可夫模型HMM HMM概率模型 HMM形式化表示：,HMM观测样本的生成过程：=,HMM的三个基本问题：1,2,1,2,数学符号X1P(Y1)X2P(Y2|Y1)XtP(Yt|Yt-1)Y1 Y2YtP(X1|Y1)P(X2|Y2)P(Xt|Yt)XNP(YN|YN-1)YNP(XN|YN)XtP(Yt|Yt-1)YtP(Xt|Yt)6.4 隐马尔可夫模型HMM HMM的三个基本算法6.4 隐马尔可夫模型HMM HMM的三个基本算法 评估问题：前向算法或后向算法6.4 隐马尔可夫模型HMM HMM的三个基本算法 评估问题：前向算法或后向算法6.4 隐马尔可夫模型HMM HMM的三个基本算法 评估问题：前向算法或后向算法6.4 隐马尔可夫模型HMM HMM的三个基本算法 评估问题：前向算法或后向算法 解码问题：Viterbi算法阚道宏6.4 隐马尔可夫模型HMM HMM的三个基本算法 评估问题：前向算法或后向算法 解码问题：Viterbi算法 学习问题：Baum-Welch算法6.4 隐马尔可夫模型HMM HMM的三个基本算法 评估问题：前向算法或后向算法 解码问题：Viterbi算法 学习问题：Baum-Welch算法6.4 隐马尔可夫模型HMM HMM的三个基本算法 评估问题：前向算法或后向算法 解码问题：Viterbi算法 学习问题：Baum-Welch算法6.4 隐马尔可夫模型HMM HMM建模与实验 HMM建模过程中需考虑的问题 状态空间=1,2,观测空间=1,2,状态观测概率=序列长度：,，1,2,s1s2s3s1s2s36.4 隐马尔可夫模型HMM HMM建模与实验 HMM建模过程中需考虑的问题 搭建HMM实验环境 开源的HMM类库hmmlearn pip install hmmlearn 三个HMM类 MultinomialHMM：状态的观测值为离散型，其观测概率为多项分布 GaussianHMM：状态的观测值为连续型，其观测概率为高斯分布 GMMHMM：状态的观测值为连续型，其观测概率为混合高斯分布 三个方法 score()：计算观测序列的生成概率，即评估问题 predict()：预测观测序列背后的状态序列，即解码问题 fit()：使用观测序列训练HMM参数，即学习问题6.5 无向图模型概率图模型 用有向图或无向图的形式来描述一组随机变量=1,2,的概率模型，即概率图模型 每个结点对应一个随机变量，每条边表示两端结点所对应的随机变量之间存在某种依赖关系（可表示成条件概率的形式）或相关关系（可表示成联合概率的形式）如果随机变量之间存在明确的依赖关系，则可以使用有向无环图描述其概率模型，即贝叶斯网 如果随机变量之间存在相关性但没有明确的依赖关系，则可以使用无向图（有环或无环均可）描述其概率模型，这种无向图概率模型被称作马尔可夫网（Markov network）马尔可夫网中两种常用的模型：马尔可夫随机场（Markov Random Field，缩写MRF）和条件随机场（Conditional Random Field，缩写CRF）6.5 无向图模型 概率图模型 马尔可夫随机场 马尔可夫随机场是一种无向图，可记作 每个结点对应一个随机变量，将结点集合记作=1,2,每条边表示两端结点所对应的随机变量、之间存在相关性，可用某种函数,表示相关性并将图中边的集合记作=,|,X1X2X3X4X2X1X312(X1,X2)23(X2,X3)123(X1,X2,X3)34(X3,X4)12(X1,X2)13(X1,X3)23(X2,X3)X1X2X3X4X0X5X6X7X80i(X0,Xi),i=2,4,5,7.6.5 无向图模型 概率图模型 马尔可夫随机场 无向图中的术语X1X2X3X4X2X1X312(X1,X2)23(X2,X3)123(X1,X2,X3)34(X3,X4)12(X1,X2)13(X1,X3)23(X2,X3)6.5 无向图模型 概率图模型 马尔可夫随机场 无向图中的术语X1X2X3X4X2X1X312(X1,X2)23(X2,X3)123(X1,X2,X3)34(X3,X4)12(X1,X2)13(X1,X3)23(X2,X3)6.5 无向图模型 概率图模型 马尔可夫随机场X1X2X3X4X2X1X312(X1,X2)23(X2,X3)123(X1,X2,X3)34(X3,X4)12(X1,X2)13(X1,X3)23(X2,X3)6.5 无向图模型 概率图模型 马尔可夫随机场 吉布斯分布6.5 无向图模型 概率图模型 马尔可夫随机场 吉布斯分布X1X2X3X4X2X1X312(X1,X2)23(X2,X3)123(X1,X2,X3)34(X3,X4)12(X1,X2)13(X1,X3)23(X2,X3)1,2,3=1121,2131,3，=1,2,3121,2131,3.1,2,3,4=1121,2131,3232,3343,4.=1,2,3,4121,2131,3232,3343,4.1,2,3,4=11231,2,3343,4.=1,2,3,41231,2,3343,4.6.5 无向图模型 概率图模型 马尔可夫随机场 常用势函数阚道宏6.5 无向图模型 概率图模型 马尔可夫随机场 MRF的建模与概率推理 =1.（6 67）6.5 无向图模型 概率图模型 条件随机场CRFY2Y1YkX=(X1,X2,Xn)C(Yi,N(Yi),X)Y3Y11Y12Y1nY21Y22Y2nYm1Ym2YmnX11X12X1nX21X22X2nXm1Xm2Xmn6.5 无向图模型 概率图模型 条件随机场CRFY2Y1YkX=(X1,X2,Xn)C(Yi,N(Yi),X)Y3Y11Y12Y1nY21Y22Y2nYm1Ym2YmnX11X12X1nX21X22X2nXm1Xm2Xmn6.5 无向图模型 概率图模型 条件随机场CRFY2Y1YkX=(X1,X2,Xn)C(Yi,N(Yi),X)Y3Y11Y12Y1nY21Y22Y2nYm1Ym2YmnX11X12X1nX21X22X2nXm1Xm2Xmn|=1=11,+1,=1,.（6 73）6.5 无向图模型 概率图模型 条件随机场CRFY2Y1YkX=(X1,X2,Xn)C(Yi,N(Yi),X)Y3Y11Y12Y1nY21Y22Y2nYm1Ym2YmnX11X12X1nX21X22X2nXm1Xm2Xmn|=1=1=11,+1,=11=1,+1,=1=1,.（6 74）6.5 无向图模型 概率图模型 条件随机场CRF 常用势函数Y2Y1YkX=(X1,X2,Xn)C(Yi,N(Yi),X)Y3Y11Y12Y1nY21Y22Y2nYm1Ym2YmnX11X12X1nX21X22X2nXm1Xm2Xmn6.5 无向图模型 概率图模型 条件随机场CRF 常用势函数Y2Y1YkX=(X1,X2,Xn)C(Yi,N(Yi),X)Y3Y11Y12Y1nY21Y22Y2nYm1Ym2YmnX11X12X1nX21X22X2nXm1Xm2Xmn第6章 概率图模型与概率推理 本章学习要点 逻辑推理与概率推理、生成式与判别式模型、贝叶斯网及其精确推理、和-积消元算法、信念传播算法 蒙特卡罗仿真、马尔可夫链、轮盘赌采样算法、直接采样法、吉布斯采样、MH采样、平稳马尔科夫链及其充分条件、Metropolis准则、模拟退火算法、遗传算法、PageRank网页排名算法、概率向量与随机矩阵 隐马尔可夫模型HMM、前向算法与后向算法、Viterbi算法、Baum-Welch算法 马尔可夫随机场MRF、条件随机场CRF