首页

隐形马尔科夫模型

发表于2017年02月27日 分类: statistical learning 标签: statistical learning

Table of Contents

  1. 马尔科夫模型的基本概念
    1. 隐马尔科夫模型的定义
    2. 观测序列的生成过程
    3. 隐形马尔科夫模型的3个基本问题
  2. 概率计算算法
    1. 直接计算法
    2. 前向算法
    3. 后向算法
    4. 一些概率与期望值的计算
  3. 学习算法
    1. 监督学习方法
    2. Baum-Welch算法(EM算法)
    3. Baum-Welch 模型参数估计公式
  4. 预测算法
    1. 近似算法
    2. 维特比算法

隐形马尔科夫模型可用于标注问题的统计学习的模型,描述由隐形的马尔科夫链随机生成观测序列的过程,属于生成模型。在语音识别、自然语言处理、生物信息、模式识别等领域有广泛的应用。

马尔科夫模型的基本概念

隐马尔科夫模型的定义

定义:隐马尔科夫模型是关于时序的概率模型,描述由一个隐藏的马尔科夫链随机生产不可观测的状态随机序列,再由各个状态生成一个观测而产生观测随机序列的过程。隐形的马尔科夫链随机生成的状态的序列,称为状态序列;每个状态产生一个观测,而由此产生的观测的随机序列,称为观测序列。序列的每一个位置又可以看作一个时刻。 隐形马尔科夫模型由初始概率分布、状态转移概率分布、以及观测概率分布确定。 形式定义: Q是所有可能的状态的集合,V是所有可能的观测的集合。 2017-2-27-隐形马尔科夫模型_8463bc759c7c2fac8534fe1c8291477cb50456b6.png N:可能的状态数 M:可能的观测数 I是长度为T的状态序列,O是对应的观测序列。 2017-2-27-隐形马尔科夫模型_185f55b0a68ebb75e26dc45f5ad9de439a9e448a.png A是状态转移概率矩阵: 2017-2-27-隐形马尔科夫模型_3048d7fda76f96879e094a31bd673b48ed23d0e3.png 其中, 2017-2-27-隐形马尔科夫模型_45bebe573a62ce03964b793767716935433d77c1.png 是在时刻t处于状态 2017-2-27-隐形马尔科夫模型_8d1a360a01ef9cfa6433364278b9a4a486502a8c.png 在时刻t+1跳转到状态 2017-2-27-隐形马尔科夫模型_aae3a7507303976062dd39e1bb55303f9e62b279.png 的概率。 B是观测概率矩阵: 2017-2-27-隐形马尔科夫模型_5570231a15237cef88aa5dabdc1b5efaffbb9468.png 其中, 2017-2-27-隐形马尔科夫模型_7c404e736d752a107272614ca93abacf0c26153e.png 是在时刻t处于状态 2017-2-27-隐形马尔科夫模型_aae3a7507303976062dd39e1bb55303f9e62b279.png 的条件下生成观测 2017-2-27-隐形马尔科夫模型_0ef7621b0f59aa9014652db2c57407215b3d66af.png 的概率。 2017-2-27-隐形马尔科夫模型_3a63c89be79dcc184e5bc475de58f9d32fb52f31.png 是初始状态概率向量: 2017-2-27-隐形马尔科夫模型_8a84154234f371df06c99cc2ed40e8ed98069fc1.png 其中, 2017-2-27-隐形马尔科夫模型_41446038165d49d7b93710b0ec0ccc7296aade0c.png 是在时刻t=1处于状态 2017-2-27-隐形马尔科夫模型_8d1a360a01ef9cfa6433364278b9a4a486502a8c.png 的慨率。

隐形马尔科夫模型由初始概率向量 2017-2-27-隐形马尔科夫模型_3a63c89be79dcc184e5bc475de58f9d32fb52f31.png 、状态转移概率矩阵A和观测概率矩阵B决定。2017-2-27-隐形马尔科夫模型_3a63c89be79dcc184e5bc475de58f9d32fb52f31.png 和A决定状态序列,B决定观测序列。因此,隐形马尔科夫模型 2017-2-27-隐形马尔科夫模型_568ed94cb36075c6be20d509eb03cff3c86e8a60.png 可以用三元符号表示,即 2017-2-27-隐形马尔科夫模型_d200d373f707f2209b79e35442208e07bf344a02.png 2017-2-27-隐形马尔科夫模型_9105d8035faa739534b7fbdaf37eb665361ac4d3.png 称为隐形马尔科夫模型的三要素。 齐次马尔可夫假设:每一时刻只依赖于前一时刻 观测独立性假设:观测只依赖于马尔科夫链的状态

观测序列的生成过程

隐形马尔科夫模型的3个基本问题

(1)概率计算问题 给定模型 2017-2-27-隐形马尔科夫模型_568ed94cb36075c6be20d509eb03cff3c86e8a60.png 和观测序列O,计算 2017-2-27-隐形马尔科夫模型_2009f811a11697fdd4969db54d5f0ffe83bc5730.png 。 (2)学习问题 已知观测序列O,估计模型 2017-2-27-隐形马尔科夫模型_568ed94cb36075c6be20d509eb03cff3c86e8a60.png 参数, 使 2017-2-27-隐形马尔科夫模型_2009f811a11697fdd4969db54d5f0ffe83bc5730.png 最大 2017-2-27-隐形马尔科夫模型_5277789cde70eaf6c909158945d887691f7e86f7.png 极大似然估计 。 (3)预测问题 给定模型 2017-2-27-隐形马尔科夫模型_568ed94cb36075c6be20d509eb03cff3c86e8a60.png 和 观测序列 2017-2-27-隐形马尔科夫模型_6825b011ad1c17bc5b6bc41833a104a5a27bacfa.png , 求最有可能的对应的状态序列 2017-2-27-隐形马尔科夫模型_2c22f477e59e4c40702072a716a680f53b0e0a50.png

概率计算算法

前向算法、后向算法

直接计算法

概念上可行,计算上不可行 按概率公式直接计算,计算量大, 2017-2-27-隐形马尔科夫模型_5215ff30e691c840cafdfd70d3d7d1c64cb6ac25.png 阶。

前向算法

前向概率定义:给定马尔科夫模型,定义到时刻t部分观测序列为 2017-2-27-隐形马尔科夫模型_73b362cf807efa284043e130b33a7893753e861a.png 且状态为 2017-2-27-隐形马尔科夫模型_8d1a360a01ef9cfa6433364278b9a4a486502a8c.png 的概率为前向概率,记作 2017-2-27-隐形马尔科夫模型_8ea9501e8d367760a0969d7962d29e291fa8918a.png 可以递归地求出前向概率 2017-2-27-隐形马尔科夫模型_8f6b6cc401382ec0bbb24f23532ac484c5bdabf1.png 及观测序列概率 2017-2-27-隐形马尔科夫模型_2009f811a11697fdd4969db54d5f0ffe83bc5730.png

观测序列概率的前向算法 (1)初值 2017-2-27-隐形马尔科夫模型_1e8f867680362fe91a5ed12148caed5aa9d9df16.png (2)递推 对 t = 1,2,…, T -1 2017-2-27-隐形马尔科夫模型_89ed5ca2e718a40fa355f3af5620148ecaaf3df7.png (3)终止 2017-2-27-隐形马尔科夫模型_fc5ced9248ac998cb14cad30db3cbbd0a1116f56.png 每一次计算直接引用前一个时刻的计算结果,避免重复计算。 计算量 2017-2-27-隐形马尔科夫模型_9b6e2ffe20a8e2974adafe175db824ebe31ec3d1.png 阶,直接计算是2017-2-27-隐形马尔科夫模型_5215ff30e691c840cafdfd70d3d7d1c64cb6ac25.png 阶。

后向算法

一些概率与期望值的计算

学习算法

根据训练数据包含观测序列和对应的状态序列还是只有观测序列,可以分别由监督学习和非监督学习实现。

监督学习方法

用极大似然估计来估计隐马尔科夫模型的参数。 1.转移概率 $aij $ 的估计 设样本中时刻t处于状态i,时刻t+1转移到状态j的频数为 2017-2-27-隐形马尔科夫模型_0deb4ba363bdf126e4502d61196f11cf6c59c2e6.png ,那么状态转移概率 2017-2-27-隐形马尔科夫模型_9f0d9e3f7723b661ab3e9e2e4bbbe3b933359782.png 的估计是 2017-2-27-隐形马尔科夫模型_dbc7b5bb1d8408044511f336bf7b4bf258fa7c8f.png 2.观测概率 2017-2-27-隐形马尔科夫模型_32069b30e31b77a3ace29bca851e8ff86895a900.png 的估计 设样本中的状态为j并观测为k的频数为 2017-2-27-隐形马尔科夫模型_cc3914705a76a72c294416f59aeb17994f273299.png ,那么状态为j观测为k的概率为 2017-2-27-隐形马尔科夫模型_5afb243660b53f92c113452918c18d1fc0b267b2.png 3.初始状态概率的估计 2017-2-27-隐形马尔科夫模型_fac62c74574b636f1427c2ca62b2940a02c1958a.png 作为S个样本中初始状态为 2017-2-27-隐形马尔科夫模型_8d1a360a01ef9cfa6433364278b9a4a486502a8c.png 的频率。

Baum-Welch算法(EM算法)

人工标记代价高 非监督学习方法

给定观测序列,无状态序列,目标:学习隐马尔科夫模型的参数。 EM算法学习实现: 观测数据:观测序列数据O 不可观测隐数据:状态序列数据I 对数似然函数:2017-2-27-隐形马尔科夫模型_3d4c64285d5b32440d665d6e05b2adc3a6289cf1.png

EM算法的E步:求Q函数 2017-2-27-隐形马尔科夫模型_ff3abd06fd9823cec0db8efdc941c0ca09985000.png 。 EM算法的M步:极大化Q函数求 2017-2-27-隐形马尔科夫模型_3af3c2035e0f8216d366d9b85d2155ea0b4bc0ff.png

Baum-Welch 模型参数估计公式

预测算法

近似算法

在每一时刻,选择最有可能发生的状态,作为预测结果。 优点:计算简单 缺点:不能保证预测的状态序列整体是最有可能的状态序列。

维特比算法

用动态规划解隐马尔科夫模型预测问题。 部分最优路径唯一,通过递推分割由部分最优达到全局最优。

定义在时刻t状态为i的所有单个路径 2017-2-27-隐形马尔科夫模型_d123074378f06ca200da5d328cc4a576d48b9d5c.png 中概率最大值为 2017-2-27-隐形马尔科夫模型_f0a49ab6beabc8ab4ef2be457e83f0f84fbca5b4.png 由定义可得变量 2017-2-27-隐形马尔科夫模型_f22fd3a6889db2cd67b760ea5e15db8e753b9230.png 的递推公式: 2017-2-27-隐形马尔科夫模型_c6c8b79c3a9a100d36151bd87a65967a71aa703a.png 2017-2-27-隐形马尔科夫模型_145206b627d5a1c2838312d68315e45b26c07d08.png 定义在时刻t状态为i的所有单个路径中概率最大的路径的第t-1个结点为 2017-2-27-隐形马尔科夫模型_32b0b929f2f69a5494fd7cd90ede50bb9ef326cf.png :用于找出最优路径的各个结点。 2017-2-27-隐形马尔科夫模型_9b6f48c529eda85a477acc53631a1eda4167855f.png

算法 (1)初始化 (2)递推 (3)终止 (4)最优路径回溯

更多

逻辑斯蒂回归与最大熵模

发表于2017年02月27日 分类: statistical learning 标签: statistical learning

Table of Contents

  1. 逻辑斯蒂回归
    1. 逻辑斯蒂分布
    2. 二项逻辑斯蒂回归模型
    3. 模型参数估计
    4. 多项logistic regression
  2. 最大熵模型
    1. 最大熵原理
    2. 最大熵模型的定义
    3. 最大熵模型的学习
    4. 极大似然估计
  3. 模型学习的最优化算法
    1. 改进的迭代尺度法(IIS)
    2. 拟牛顿法

逻辑斯蒂回归与最大熵模型都属于对数线性模型

逻辑斯蒂回归

逻辑斯蒂分布

二项逻辑斯蒂回归模型

定义: 2017-2-27-逻辑斯蒂回归与最大熵模_b1bbf718f3b4268d322b5cc5bd1ae5b163f0a6b8.png 2017-2-27-逻辑斯蒂回归与最大熵模_2b28c027c5bc123608b4d16a2108e5afe5b3a501.png 比较两个条件概率的大小,将实例x分到条件概率值较大的那一类。 对数几率或logit函数是: 2017-2-27-逻辑斯蒂回归与最大熵模_cd843a5826291e85c7d07abd2acb8fb4a0e161ac.png 在logistic regression模型中,输出 Y=1 的对数几率是输入x的线性函数 2017-2-27-逻辑斯蒂回归与最大熵模_f515955531cc0ee1764e3d5c43d4095f0c3d5fbd.png

模型参数估计

应用极大似然估计法估计模型的参数 设: 2017-2-27-逻辑斯蒂回归与最大熵模_e3f2942f868f086781262fcd64e9ba1fcab52748.png 似然函数为: 2017-2-27-逻辑斯蒂回归与最大熵模_47d27633eb99affbfe48da8090f3bfee08820542.png 对数似然函数为: 2017-2-27-逻辑斯蒂回归与最大熵模_3408934bb87076c3bbea1869ac696ef8d52b2fd3.png 对对数似然函数求极大值,得到 2017-2-27-逻辑斯蒂回归与最大熵模_1ee5b3f866f25c1f47294cec3665c01aa14c1ade.png 的估计值。 问题变成以对数似然函数为目标函数的最优化问题。 通常采用梯度下降法和拟牛顿法。

多项logistic regression

最大熵模型

由最大熵推导实现

最大熵原理

假设离散随机变量X的概率分布为P(X),则其熵为: 2017-2-27-逻辑斯蒂回归与最大熵模_378c3df25d6fa0d66906575d63c90a5093753ef5.png 熵最大的模型为最好的模型。 最大熵原理通过熵的最大化来表示等可能性。

最大熵模型的定义

对于给定的输入X,以条件概率P(Y|X)输出Y。 学习的目标:用最大熵原理选择最好的分类模型。 最大熵模型 定义在条件概率分布P(Y|X)上的条件熵为: 2017-2-27-逻辑斯蒂回归与最大熵模_74ab4a04812c4f695c1e391ebda845a408d8579b.png 则满足所有约束条件的模型集合为C中条件熵H(P)最大的模型称为最大熵模型。

最大熵模型的学习

形式化为约束最优化问题,将约束最优化问题转换为无约束最优化的对偶问题,通过解对偶问题求解原问题。 最大熵模型: 2017-2-27-逻辑斯蒂回归与最大熵模_3741c4a2dee3b3b6e3c6221aa7f4ea08b82ee980.png 其中, 2017-2-27-逻辑斯蒂回归与最大熵模_f80ed5aa77eddc6c0d63a4b8dc8b7da93b778b7a.png 特征函数为 2017-2-27-逻辑斯蒂回归与最大熵模_f80054f79b9e053b45a466d689ca3e695a90af87.png2017-2-27-逻辑斯蒂回归与最大熵模_960ad8bef55aa259b22a4296ec2b54c50da0e41a.png 称为规范化因子, n为特征函数的个数, 2017-2-27-逻辑斯蒂回归与最大熵模_c75933d854b6531563fa6d0eb304d82e7543525a.png 为特征的权值。

极大似然估计

证明了最大熵模型学习中的对偶函数的极大化等价于最大熵模型的极大似然估计 最大熵模型的一般形式 2017-2-27-逻辑斯蒂回归与最大熵模_dbb0ac09f0a44d1920b2e8c6c7fd904f8b80e3ff.png 其中 2017-2-27-逻辑斯蒂回归与最大熵模_1c35edeeeb722036f21d64c623c39989bd41a397.png 这里 2017-2-27-逻辑斯蒂回归与最大熵模_a2cea2b163856fa1013931c25d6fa509f795750f.png 为输入, 2017-2-27-逻辑斯蒂回归与最大熵模_9fba271638fba6e14af1e2dead49c6ae4df85649.png 为输出, 2017-2-27-逻辑斯蒂回归与最大熵模_7cfa0cd194b195c271a0dec2ce7aa5116c9d9576.png 为权值向量,2017-2-27-逻辑斯蒂回归与最大熵模_2e62312bafce782bf399c6debb54b0b89fcecc40.png 为任意实值特征函数。

模型学习的最优化算法

logistic regression、最大熵模型学习归结为以似然函数为目标函数的最优化问题,通常通过迭代法求解。能保证找到全局最优解,牛顿法和拟牛顿法收敛速度快。

改进的迭代尺度法(IIS)

当前的参数向量是 2017-2-27-逻辑斯蒂回归与最大熵模_d4d1aed1667079a50cac8b266a4019c8e334bb24.png,找到一个新的参数向量 2017-2-27-逻辑斯蒂回归与最大熵模_c981a0e7c5537fa8dc6c1e4a62764df1e3dfaf92.png,使得模型的对数似然函数增大,重复这一过程,直至找到对数似然函数的最大值。

拟牛顿法

最大熵模型: 2017-2-27-逻辑斯蒂回归与最大熵模_13765d87a07c223ae17d27fb724368090b700bfb.png 目标函数(熵最大化): 2017-2-27-逻辑斯蒂回归与最大熵模_0690f6e456e7330faf849bfd3b11049677530b38.png 梯度: 2017-2-27-逻辑斯蒂回归与最大熵模_96494c3f5dd43a7d6f61addb6d1f7fd70751a6d0.png

算法: (1)选定初始点 2017-2-27-逻辑斯蒂回归与最大熵模_8c14eebbdbbd1e3f19b909346fc19677886c2ecc.png ,取 2017-2-27-逻辑斯蒂回归与最大熵模_4c85bbab3d2e8df7d9116248dfc821b278921d8a.png 为正定对称矩阵,置k=0 (2)计算 2017-2-27-逻辑斯蒂回归与最大熵模_5f23d048cf4bd44b9dec160a65d93e3f439c094b.png , 若 2017-2-27-逻辑斯蒂回归与最大熵模_52208d17c6a1d7caed54b8c95bbe44cab95897d1.png ,则停止计算, 得 2017-2-27-逻辑斯蒂回归与最大熵模_6bd939fc663996285d191e53d6686b7b193f4ee8.png ; 否则转到(3) (3)由 2017-2-27-逻辑斯蒂回归与最大熵模_859373274a327881176aa0395585c94984b3f03f.png 求出 2017-2-27-逻辑斯蒂回归与最大熵模_56808d3531da4eb8f2400f55871a590ca59ce58f.png 。 (4)一维搜索:求 2017-2-27-逻辑斯蒂回归与最大熵模_ab5a0f30ecb47b4de509542acb725ad0c94ae751.png 使得 2017-2-27-逻辑斯蒂回归与最大熵模_b3c8957a068a91e54dc4f1b58f445948e36eebd8.png (5)置 2017-2-27-逻辑斯蒂回归与最大熵模_0f81f2bd92b3395101ed6b5d9277b25ba8a0569b.png (6)计算 2017-2-27-逻辑斯蒂回归与最大熵模_5dad521fa134343994117f6f9a10efe50d9b52e6.png , 若 2017-2-27-逻辑斯蒂回归与最大熵模_1a8b9f47734649c06ae2362ace72958e76a930f4.png , 则停止计算, 得 2017-2-27-逻辑斯蒂回归与最大熵模_8e113342fd7c9825266774bb60fbea8716c56f77.png ; 否则, 按下式求出 2017-2-27-逻辑斯蒂回归与最大熵模_6459c9a652a0fd515bfca8acfd8ccd52a6ba27ce.png : 2017-2-27-逻辑斯蒂回归与最大熵模_8fe0d4776ba9ceb28a068892351c8d660cd50fd6.png 其中, 2017-2-27-逻辑斯蒂回归与最大熵模_7cff8a01599cc14b3d396aad91ec6efe5968a1d6.png (7)置 k = k +1, 转(3).

更多

统计学习

发表于2017年02月27日 分类: statistical learning 标签: statistical learning

Table of Contents

  1. 生成模型和判别模型
  2. 分类问题
  3. 标注问题
  4. 回归问题

生成模型和判别模型

监督学习方法:生成方法、判别方法 生成方法:给定输入X产生输出Y的生成关系, 典型:朴素贝叶斯、隐马尔科夫 优点:可以还原出联合概率分布,学习收敛速度快,存在隐变量时,仍可以用 判别方法:直接学习决策函数或者条件概率分布作为预测的模型 优点:学习的准确率高,可以对数据进行抽象、定义并使用特征,简化学习问题

分类问题

包含学习和分类两个过程。 评价分类器的指标:分类准确率 二分类问题:精确率和召回率

标注问题

可以看作分类问题的一个推广,结构预测问题的简单形式 包含学习和标注两个过程。 常用方法:隐马尔科夫模型、条件随机场

回归问题

预测输入变量和输出变量之间的关系 函数拟合 最常用损失函数:平方损失函数 用最小二乘法求解

更多

牛顿法和拟牛顿法

发表于2017年02月27日 分类: statistical learning 标签: statistical learning

Table of Contents

  1. 牛顿法
  2. 拟牛顿法的思路
  3. DFP算法
  4. BFGS算法
  5. Broyden算法

牛顿法

将f(x) 在 2017-2-27-牛顿法和拟牛顿法_281b400f7263a26ab318c145541032dac00d2629.png 处附近进行二阶泰勒展开,并令其一阶导数为0,求的 2017-2-27-牛顿法和拟牛顿法_ee4661fe719c9e8063102ea69c4b59303852b328.png

拟牛顿法的思路

在牛顿法的迭代过程中,需要计算海塞矩阵的逆矩阵,计算复杂,考虑用n阶矩阵来近似替代。 每次迭代选择更新矩阵 $Gk+1$: 2017-2-27-牛顿法和拟牛顿法_11a935b21285a1b23c9423c6f2474be125fab447.png

DFP算法

2017-2-27-牛顿法和拟牛顿法_79647fc07ad8f484c8a06cc752232ce431f82de7.png 可以证明,若初始矩阵 2017-2-27-牛顿法和拟牛顿法_7802d7f85eefddaaee8c0be2209d79469bd85855.png 是正定的,则在迭代过程中的每个矩阵 2017-2-27-牛顿法和拟牛顿法_e5e7e3a1828a3e61bdce2d070572ce46b5044986.png 都是正定的。

BFGS算法

最流行的拟牛顿算法 2017-2-27-牛顿法和拟牛顿法_349802c5e7dc6f3afb0204c8bd788ceda7cbb92a.png 可以证明,若初始矩阵 2017-2-27-牛顿法和拟牛顿法_4c85bbab3d2e8df7d9116248dfc821b278921d8a.png 是正定大的,则迭代过程中的每个矩阵 2017-2-27-牛顿法和拟牛顿法_b0ecfb442714422d9e452bd65c6fff208e402b9c.png 都是正定的。

Broyden算法

更多

条件随机场

发表于2017年02月27日 分类: statistical learning 标签: statistical learning

Table of Contents

  1. 概率无向图模型
    1. 模型定义
    2. 概率无向图的因式分解
  2. 条件随机场的定义和形式
    1. 条件随机场的定义
    2. 条件随机场的参数化形式
    3. 条件随机场的简化形式
    4. 条件随机场的矩阵形式
  3. 条件随机场的概率计算问题
    1. 前向-后向算法
    2. 概率计算
    3. 期望值计算
  4. 条件随机场的学习算法
    1. 改进的迭代尺度法
    2. 拟牛顿法
  5. 条件随机场的预测算法

条件随机场(CRF)是给定一组输入随机变量条件下另一组输出随机变量的条件概率分布模型。 特点:假设输出随机变量构成马尔科夫随机场。 主要讲述线性链条件随机场

概率无向图模型

又称为马尔科夫随机场,可以由无向图表示的联合概率分布。

模型定义

无向图表示的随机变量之间存在成对马尔科夫性、局部马尔可夫性、全局马尔科夫性。 成对马尔可夫性:u,v是没有边连接的结点,O是其他结点,给定随机变量组 2017-2-27-条件随机场_4a831fbef4abf7e0cd7968b6458561d7c8632fe1.png 的条件下随机变量 2017-2-27-条件随机场_c94f8838a6534d5a2711efde75ccda99471d718f.png2017-2-27-条件随机场_73b9ae721c423f44c19762be3a2807416ae46d88.png 是条件独立的。 局部马尔可夫性:W是与v有边连接的结点,O是其他结点,给定随机变量组 2017-2-27-条件随机场_6a97cc585aa41dad97931ec4a2a1c3a2ef4c679c.png 的条件下随机变量 2017-2-27-条件随机场_73b9ae721c423f44c19762be3a2807416ae46d88.png2017-2-27-条件随机场_4a831fbef4abf7e0cd7968b6458561d7c8632fe1.png 是条件独立的。 全局马尔可夫性:点集合A,B是被C分开的任意结点集合,给定随机变量组 2017-2-27-条件随机场_fbf8b5564fb3243b6330a9af4de350e34c699f7d.png 的条件下随机变量组 2017-2-27-条件随机场_cb82b849e9b26b702b5333d4b4ea30eb856178c3.png2017-2-27-条件随机场_c29ed803e6c6a636cb6723164005f7054ae7f93c.png 是条件独立的。

概率无向图模型定义: 结点表示随机变量,边表示依赖关系。若联合概率分布P(Y)满足成对马尔可夫性、局部马尔可夫性、全局马尔可夫性,就称此联合概率分布为概率无向图模型,或马尔科夫随机场。 求解马尔科夫模型:将联合概率进行因式分解。

概率无向图的因式分解

定义团和最大团 概率无向图的因式分解:将无向图模型的概率分布表示为最大团上的随机变量函数的乘积形式 给定无向图概率模型,设其无向图为G,C为G上的最大团,2017-2-27-条件随机场_fbf8b5564fb3243b6330a9af4de350e34c699f7d.png 表示C对应的随机变量。那么概率无向图模型的联合概率分布P(Y)可写作图中所有最大团C上的函数 2017-2-27-条件随机场_8862280522686b44956b276f3b5c4f7c2897543d.png 的乘积形式,即 2017-2-27-条件随机场_f236d194d06a12cc480bc131e253f0b1f8b4d068.png 其中, Z是规范化因子,由式 2017-2-27-条件随机场_03cb43782a39c196d4af28da551eb0ee0ee2b714.png 给出。保证P(Y)构成一个概率分布。函数 2017-2-27-条件随机场_8862280522686b44956b276f3b5c4f7c2897543d.png 称为势函数,要求势函数严格为正。

条件随机场的定义和形式

条件随机场的定义

条件随机场(CRF)是给定随机变量X的条件下,随机变量Y的马尔科夫随机场。 线性链条件随机场: 用于标注等问题 条件概率模型P(Y|X),Y是输出变量(状态序列), X是输入变量(观测序列)。学习时,通过(正则化)极大似然估计得到条件概率P(Y|X)。预测时,对于给定的输入序列x,求出条件概率 2017-2-27-条件随机场_4a35f0675648b167bc58593e26cc84b0183589ab.png 最大的输出序列 2017-2-27-条件随机场_60b47932d78a19e4e3a3f2edab1d0a74fc1b64b6.png . 条件随机场的定义 设X与Y是随机变量,P(Y|X)是在给定X的条件下Y的条件概率分布,若随机变量Y构成一个由无向图G=(V,E)表示的马尔科夫随机场,则称条件概率分布P(Y|X)为条件随机场。 定义中未要求X和Y有相同的结构,现实中一般假设有相同的图结构。

线性链条件随机场的定义 设 2017-2-27-条件随机场_299fdd039b942f17e3b8f26533ba8b0b4ca64a8e.png2017-2-27-条件随机场_39325e970b788748a30248f0fe10513fb2f41622.png 均为线性链表示的条件随机序列,若给定条件随机序列X的条件下,随机变量序列Y的条件分布序列 2017-2-27-条件随机场_723307fd51f606cf46f7fdc012dbc985bc14657c.png 构成条件随机场,即满足马尔可夫性,则称P(Y|X)为线性链条件随机场。

条件随机场的参数化形式

设P(Y|X)为线性链条件随机场,则在随机变量X取值为x的条件下,随机变量Y取值为y的条件概率具有如下形式: 2017-2-27-条件随机场_3d0a7a44223b03e0d733263c7854ef64a51768e5.png 其中, 2017-2-27-条件随机场_990f59c1577641ab274dcb428d9f239d7dd5ded2.png 2017-2-27-条件随机场_4471d55b568a72cc7e720c1652ae059efa574c6a.png 为转移特征, 2017-2-27-条件随机场_468ad6c3d81dfe7c69c83167f6ccfee98dac528e.png 为状态特征,取值为0或者1; 2017-2-27-条件随机场_aad0f9d9fa1a208c2031d830b4023b6190e85744.png 为对应的权值。 例11.1 1+ 0.2 + 1 + 0.5 + 0.5 = 3.2

条件随机场的简化形式

同一特征在各个位置都有定义,对同一特征在各个位置求和,将局部特征函数转化成一个全局特征函数,将条件随机场写成权值向量和特征向量的内积形式。 先将转移特征和状态特征用统一的符号 2017-2-27-条件随机场_d1d74a100b20d3994d937a0cc9c550d152c20243.png 表示。 然后,对转移和状态特征在各个位置上求和。 接着用统一的符号 2017-2-27-条件随机场_fb66f8c89dcbb64abffbe441745e539d03dee7ba.png 表示特征 2017-2-27-条件随机场_1c58a3acadc74c87c7e8a525bc08ec129d499255.png 的权值。 于是,条件随机场可以表示为: 2017-2-27-条件随机场_1b068b4513c0f32aab6b2af3f4aa07f68b4d84a1.png 2017-2-27-条件随机场_b2477891ee5d3d224aea12fb6874c2a3d7085875.png 若以向量表示为: 2017-2-27-条件随机场_a273e0e6a16daf3c5f2a2b101853cf76d1141721.png

条件随机场的矩阵形式

条件随机场的概率计算问题

给定条件随机场P(Y X),输入序列x和输出序列y,计算条件概率 2017-2-27-条件随机场_7b966ea6915e248b4b60fd42d7d3353e83ab5ccd.png 以及相应的数学期望的问题。

前向-后向算法

定义前向变量 2017-2-27-条件随机场_cdbf14c6301edd02f022392ef5a754385c3be19e.png , 2017-2-27-条件随机场_137bbad0b3ef42cb4591d7f38ca892952e9740e9.png 表示在位置i的标记是 2017-2-27-条件随机场_74eddcc60ec92ca5a89ba849486ccde9dcbe5a2a.png 并且到位置i 的前部分标记序列的非规范化概率。 2017-2-27-条件随机场_74eddcc60ec92ca5a89ba849486ccde9dcbe5a2a.png 可取m个, 2017-2-27-条件随机场_cdbf14c6301edd02f022392ef5a754385c3be19e.png 是m维向量。 定义后向变量 2017-2-27-条件随机场_3bcb4c9e9afccda014003b22d3b9f310810c644c.png , 2017-2-27-条件随机场_ba379713b6883ffe40af14fd42ab81dfcb64cea1.png 表示在位置i的标记为 2017-2-27-条件随机场_74eddcc60ec92ca5a89ba849486ccde9dcbe5a2a.png 并且从 i+1 到 n的后部分标记序列的非规范化概率。

可得: 2017-2-27-条件随机场_38bf0e0c7849d2edd0c0a8f5ed87f8d3c18cb666.png

概率计算

2017-2-27-条件随机场_f8adc3cc7ceef2b33a32e7a2c9e1bf1594184a61.png 2017-2-27-条件随机场_06c8cb55f6aafddac4306fc0d7f2490044ce97c4.png

期望值计算

条件随机场的学习算法

模型:定义在时序数据上的对数线性模型 学习方法:(正则化的)极大似然估计

改进的迭代尺度法

拟牛顿法

条件随机场的预测算法

维特比算法

更多

朴素贝叶斯法

发表于2017年02月27日 分类: statistical learning 标签: statistical learning

Table of Contents

  1. 朴素贝叶斯法的学习和分类
    1. 基本方法
  2. 朴素贝叶斯法的参数估计
    1. 极大似然估计
    2. 学习和分类算法

朴素贝叶斯法:基于贝叶斯定理与特征条件独立假设的分类方法 首先,根据特征条件独立假设学习输入/输出的联合概率分布 然后,基于模型,对给定的x,利用贝叶斯定理求出后验概率最大的输出y

实现简单,学习和预测的效率高

朴素贝叶斯法的学习和分类

基本方法

通过训练集数据学习联合概率分布P(X, Y), 学习: 先验概率分布: 2017-2-27-朴素贝叶斯法_319090e51f4568bd82b1ccd54c30f3381e956446.png 条件概率分布:2017-2-27-朴素贝叶斯法_2992411d09e6976db226dc9ac2d0434bfe90bd6f.png

做了条件独立性的假设,因而得名朴素。 学习生成数据的机制,因而属于生成模型。

根据学得的模型,对给定输入x,将后验概率最大的类作为x的类输出。

朴素贝叶斯法的参数估计

极大似然估计

应用极大似然估计法估计相应的概率: 2017-2-27-朴素贝叶斯法_5d1171df71735a7de69fe5b343b246316d019baa.png2017-2-27-朴素贝叶斯法_def0514562b3c063498aa02b24be8b6979ffe788.png 先验概率 2017-2-27-朴素贝叶斯法_5d1171df71735a7de69fe5b343b246316d019baa.png 的极大似然估计是 2017-2-27-朴素贝叶斯法_705196d28fc740ad02da43ba257fc1f7639da504.png 2017-2-27-朴素贝叶斯法_2c22f477e59e4c40702072a716a680f53b0e0a50.png : 指示函数,表示有哪些元素属于某一子集A。

学习和分类算法

计算条件概率分布和先验概率分布,对于给定的x,将后验概率最大的类作为x的类输出。

条件概率的贝叶斯估计:解决极大似然估计出现的概率值为0的情况。

若假设条件之间存在概率依存关系,朴素贝叶斯模型将变成贝叶斯网络。

更多

支持向量机

发表于2017年02月27日 分类: statistical learning 标签: statistical learning

Table of Contents

  1. 线性可分支持向量机和硬间隔最大化
    1. 线性可分支持向量机
    2. 函数间隔和几何间隔
    3. 间隔最大化
      1. 最大间隔分离超平面
      2. 支持向量和间隔边界
      3. 学习的对偶算法
  2. 线性支持向量机与软间隔最大化
    1. 线性支持向量机
    2. 学习的对偶算法
    3. 支持向量
    4. 合页损失函数
  3. 非线性支持向量机和核函数
    1. 核技巧
    2. 正定核
    3. 常用核函数
    4. 非线性支持向量分类机
  4. 序列最小最优化算法
    1. 两个变量二次规划的求解方法
    2. 变量选择的方法

在特征空间间隔最大大的线性分类器。 核技巧,非线性分类器 学习策略:间隔最大化m 学习算法是求解凸二次规划的最优化算法

模型:线性可分支持向量机、线性支持向量机、非线性支持向量机(由简到繁) 训练数据线性可分 硬间隔最大化 线性可分支持向量机 训练数据近似可分 软间隔最大化 线性支持向量机 训练数据线性不可分 核技巧和软间隔最大化 非线性支持向量机

输入空间是欧式空间或者离散集合、特征空间是希尔伯特空间时,核函数:将输入从输入空间映射到特征空间得到特征向量之间的内积。 核方法是比支持向量机更为一般的机器学习方法。

线性可分支持向量机和硬间隔最大化

线性可分支持向量机

利用间隔最大化求最优分离超平面,解唯一。

函数间隔和几何间隔

函数间隔 样本点 2017-2-27-支持向量机_06641331faffdb0a4e8760a85a6d0c89574f04bb.png 的函数间隔: 2017-2-27-支持向量机_559b642e9d888554d42575a5ab5ae8288367d330.png 关于训练集的函数间隔: 2017-2-27-支持向量机_8f9b67efe53f2cd4f570c12c4efb53adedb5ec3b.png 对w进行约束,||w|| = 1,函数间隔变成几何间隔

间隔最大化

最大间隔分离超平面

线性可分支持向量机学习的最优化问题: 2017-2-27-支持向量机_2f65496992913f181d0cd625bf0bd0976aeba7b0.png 2017-2-27-支持向量机_7c0ec6c18c2ffff85b660f13d18c96170101d77d.png 最大间隔分离超平面的存在具有唯一性

支持向量和间隔边界

训练样本点与分离超平面距离最近的实例为支持向量

学习的对偶算法

优点:对偶问题往往更容易求解、自然引入核函数,推广到非线性分类 根据拉格朗日对偶性,原始问题的对偶问题是极大极小问题: 2017-2-27-支持向量机_8077e9c9e260e46abca2b8a12bfb975279ba18dd.png 为了得到对偶问题的解,需要先求 2017-2-27-支持向量机_b2cec238c8109bf32e9d6910ce5cb62ed42c9520.png2017-2-27-支持向量机_6aec663a7b5fc0a127e006e60dd936cd3ed09608.png的极小化,接着求对2017-2-27-支持向量机_36c9f1cf2d465863a352295f59745d756d2755d9.png的极大化。 与之等价的对偶最优化问题: 2017-2-27-支持向量机_37dabe1df4096ca2a63dc833d24baa65704f132d.png 2017-2-27-支持向量机_498620a70976e7db4cde2290f61e7b79287676c7.png 分类决策函数只依赖于输入x和训练样本输入的内积

对于给定的线性可分训练集,通过对偶问题求得w,b, 得到分离超平面和分类决策函数。这种方法是线性可分支持向量机的基本学习算法。

w,b只依赖于训练样本中对应于 $αi > 0 $ 的样本点,将这样的点称为支持向量。

线性支持向量机与软间隔最大化

线性支持向量机

引入松弛变量 2017-2-27-支持向量机_978c0a1eafcf1d96f20e2bfe2802e51f6c29fe37.png,使函数间隔加上松弛变量大于等于0,约束条件变为: 2017-2-27-支持向量机_8b783a7cbf9575fbe2b1a1aafa3aaa8c179f1579.png 目标函数变为: 2017-2-27-支持向量机_bc4dd45fdedc9a5554fcea053ffb2cc9d68befaa.png C > 0称为惩罚参数 使 2017-2-27-支持向量机_28f6a9d10c1da6fd17c6ee33726bcd8fc98cc608.png 尽量小即间隔尽量大,使误分类的额个数尽量小 线性不可分的线性支持向量机学习的原始问题: 2017-2-27-支持向量机_b30ef9b05dc0f5f8bfbb8c7c358c29ed1e9250ff.png 2017-2-27-支持向量机_a8d7dab134b616bcc85853bbdcfbedbd7838ff9a.png 2017-2-27-支持向量机_602d1e28601cf5b4ff1635d6e940f5db616ce408.png 可以证明w的解是唯一的,b的解不唯一,存在一个区间

学习的对偶算法

原始问题对应的对偶问题不变,满足的条件发生改变 $ 0<= αi <= C, i=1,2,…N$

支持向量

软间隔的支持向量或者在间隔的边界上,或者在间隔边界与分离超平面之间,或者在分离超平面误分类一侧。

合页损失函数

线性支持向量机学习,模型:分离超平面及决策函数,学习策略:软间隔最大化,学习算法:凸二次规划 另一种解释,最小化如下目标函数: 2017-2-27-支持向量机_83557b19037795b72f07e94e4281b3aedf718c53.png 目标函数的第一项称为经验损失,第一项称为合页损失函数,第二项是正则化项。

非线性支持向量机和核函数

核技巧

核技巧通过一个非线性变换将输入空间对应与一个特征空间。分类任务在特征空间求解线性支持向量机。 存在输入空间到特征空间的映射 2017-2-27-支持向量机_d9ed44c1610ed37daed21280d67702dce2a93254.png 使得对所有的 2017-2-27-支持向量机_369cb860fae4fad95f7b85b4ab1a2e5f5e460458.png ,函数K(x,z)满足条件 2017-2-27-支持向量机_3ca3fdce302f1310a11f37340d2fdf1c40282a35.png 则称K(x,z)为核函数(任意两个输入变量在高维映射中的内积), 2017-2-27-支持向量机_2fbc620054b0ff515a7017aaf8518b24b8ee6a88.png 为映射函数。 核技巧:只定义核函数,而不显示地定义映射函数。直接计算核函数容易,而通过映射函数计算复杂。 对于给定的核函数,特征空间和映射函数大的取法不唯一。

核技巧在支持向量机中的应用 在对偶的目标函数中的内积 2017-2-27-支持向量机_a2373338fa8171a53759ca14621b684e848676c6.png 可以用核函数 2017-2-27-支持向量机_a6770573de71a948cc75d392deb4fe867079047f.png 来代替,同时分类决策函数中的内积也可以用核函数来代替。

正定核

K(x,z)为对称函数,则K(x,z)为正定核函数的充要条件是对任意的 2017-2-27-支持向量机_35aaa76d2e72b779acf94a700591d60f57d4b151.png K(x,z)对应的Gram矩阵: 2017-2-27-支持向量机_7e29e571fd19c8065bc4c5715cfc5dc52063306c.png 是半正定矩阵。 检验是否是正定核函数并不容易。

常用核函数

多项式核函、高斯核函数、字符串核函数 字符串核函数:两个字符串相同的子串越多,他们就越相似,字符串核函数的值就越大。可以由动态规划快速计算。

非线性支持向量分类机

将线性支持向量机扩展到非线性支持向量机,只需将线性支持向量机对偶形式中的内积换成核函数。

非线性支持向量机学习算法 (1)选取适当的核函数K(x,z)和适当的参数C,构造并求解最优化问题 2017-2-27-支持向量机_e94711550889e309aff6cf25b36d9d0f32a1a50b.png 2017-2-27-支持向量机_6aaaaf06104a21f86908edd6468cac770b94a0c6.png 2017-2-27-支持向量机_31ae134fdb0e07e886f4137af93fb56dc0207ebc.png 求得最优解 2017-2-27-支持向量机_231cf4839fcc74685657e05a251db207471d292d.png 选取 2017-2-27-支持向量机_123ff64bf05f6b7f3a0eb1734f377bb15651ab29.png2017-2-27-支持向量机_1bc907774f5bddc35539a5e8d59a650dff6b234d.png 构造决策函数 2017-2-27-支持向量机_e75c6aa9291868b86c4d5d3da58eefa6125a73d2.png

序列最小最优化算法

SMO算法:若所有变量的解都满足KKT条件,则解就得到了;否则,选择两个变量,固定其他变量,构建二次规划问题并求解,将原问题不断分解为子问题并对子问题求解,进而求解原问题。 包含:求解两个变量二次规划的解析方法、选择变量的启发式方法

两个变量二次规划的求解方法

变量选择的方法

第1个变量的选择 外层循环选取违背KKT条件最严重的点,首先遍历在间隔边界上的支持向量的点,检验是否满足条件,若都满足条件,则遍历整个训练集,检验是否满足条件。 第2个变量的选择 选择的标准,使第二个变量有足够大的变化

更多

提升方法

发表于2017年02月27日 分类: statistical learning 标签: statistical learning

Table of Contents

  1. 提升方法AdaBoost算法
    1. 提升方法的基本思路
    2. Adaboost算法
    3. Adaboost的例子
  2. Adaboost算法的训练误差分析
  3. Adaboost算法的解释
    1. 前向分布算法
    2. 前向分布算法与Adaboost
  4. 提升树
    1. 提升树模型
    2. 提升树算法
    3. 梯度提升

在分类中,boosting 通过改变训练样本的权重,学习多个分类器,并将这些分类器进行线性组合,提高分类的性能。

提升方法AdaBoost算法

提升方法的基本思路

PAC(probably approximately correct)概率近似正确 强可学习和弱可学习等价 将弱可学习算法提升为强可学习算法, adaboost 提升方法从弱学习算法出发,反复学习,得到一系列弱分类器(基本分类器),然后组合弱分类器,构成一个强分类器。大多数的提升方法都是改变训练数据的概率分布,针对不同的数据分布学得不同的弱学类器。

如何改变训练数据的权值和概率分布 Adaboost:提高那些被前一轮弱分类器错误分类样本的权值,而降低那些被正确分类样本的权值。

如何将弱分类器组合成一个强分类器 Adaboost:加权多数表决,加大分类误差率小的弱分类器的权值,减小分类误差率大的权值。

Adaboost算法

Adaboost的例子

Adaboost算法的训练误差分析

Adaboost的训练误差是以指数速率下降的。具有适应性,能适应弱分类器各自的训练误差率。

Adaboost算法的解释

另一种解释,模型为加法模型,损失函数为指数函数、学习算法为前向分布算法的二类分类学习方法。

前向分布算法

前向分布算法与Adaboost

提升树

以分类树或者回归树为基本分类器的提升方法。

提升树模型

可以表示为决策树的加法模型: 2017-2-27-提升方法_fa84f011f36eaa8ef81f4a3e245c4687c29787fd.png 其中,T表示决策树,2017-2-27-提升方法_d80ab66136717dd20d39dc6a799385298f5f3523.png 为决策树参数; M为树的个数。

提升树算法

采用前向分步算法。 首先确定初始提升树 2017-2-27-提升方法_d072100a9cebb980e5211d4c99fa170a0520aa38.png,第m步的模型是: 2017-2-27-提升方法_cdcc29baafc742d2d6efb543afeb94027cf8f014.png 通过经验风险极小化确定下一棵决策树的参数 2017-2-27-提升方法_dde260c3dec8112efe6d4831e260c9535e8a9d2a.png. 树的线性组合能很好地拟合训练数据,提升树是一个高功能算法。 不同的提升树算法,其区别是损失函数不同。 回归问题:使用平方误差损失函数 分类问题:使用指数损失函数 一般决策问题:一般损失函数

二类分类问题,将adaboost中的基本分类器限定为二类分类器,提升树是Adaboost的特殊情况。 回归问题的提升树只需简单地拟合当前模型的残差。

回归问题的提升树算法: 输入:训练数据集 2017-2-27-提升方法_7736cf7c93fe10a64dff67b6d33adfe96f3477bb.png 输出:提升树 2017-2-27-提升方法_5aa73699b6229cf3d86fb71bebf4dcc4490a387a.png (1)初始化 2017-2-27-提升方法_0ca2dd7515ac19576ea98095a3fd74276c781f8c.png (2)对m=1,2,…,M (a)计算残差 2017-2-27-提升方法_3c6b89d824865dcde2d24b6cdcdbd7d568cab2ca.png (b)拟合残差$rmi$学习一个回归树,得到T (c)更新fm(x) = fm-1(x) + T (3)得到回归问题提升树 2017-2-27-提升方法_b394553a6c373d3a7ef0e5187d0caa70e4694548.png

梯度提升

对一般损失函数,提升树的优化并不容易。梯度提升,利用最速下降法的近似方法,利用损失函数的负梯度在当前模型的值 2017-2-27-提升方法_906d46cab55ade93540e209996ba0aeb07a98466.png 作为回归问题提升树算法中残差的近似值,拟合一个回归树。

算法步骤: (1)初始化:估计使损失函数极小化的常数值,是只有根结点的树。 (2a)计算损失函数的负梯度在当前模型的值,将它作为残差的估计。 (2b)估计回归树叶结点区域,以拟合残差的近似值。 (2c)利用线性搜索估计叶节点区域的值,使损失函数极小化。 (2d)更新回归树 (3)得到最终模型

更多

感知机

发表于2017年02月27日 分类: statistical learning 标签: statistical learning

Table of Contents

  1. 感知机模型
  2. 感知机学习策略
    1. 数据集的线性可分性
    2. 感知机学习策略
  3. 感知机学习算法
    1. 感知机学习算法的原始形式
    2. 算法的收敛性

二类分类的线性分类模型 输入:实例的特征向量 输出:实例的类别

感知机模型

f(x) = sign(w*x + b) if(x >= 0) sign(x) = 1; else sign(x) = -1;

感知机学习策略

数据集的线性可分性

感知机学习策略

确定学习策略,即定义损失函数并使损失函数最小化 感知机采用损失函数输入特征:误分类点到超平面的距离 感知机损失函数定义: 2017-2-27-感知机_ab7214279dec2ff9cd602f6693b6cc27b8fc3624.png 其中,M是误分类点的集合。 给定数据集T,损失函数是w,b的连续可导函数

感知机学习算法

求解损失函数的最优化问题的方法。 梯度下降法, 原始形式、对偶形式

感知机学习算法的原始形式

误分类驱动 梯度下降法 一次随机选取一个误分类点使其梯度下降 随机选取一个误分类点 2017-2-27-感知机_06641331faffdb0a4e8760a85a6d0c89574f04bb.png , 对w,b进行更新: 2017-2-27-感知机_5bf47d31598ba1e635ab0bb53b944075b0517561.png 采用不同的初值或者选取不同的分类点,解可以不同。

算法的收敛性

当训练数据集线性可分时,感知机学习算法原始形式是迭代收敛的,当不可分时,迭代不收敛

更多

决策树

发表于2017年02月27日 分类: statistical learning 标签: statistical learning

Table of Contents

  1. 决策树模型与学习
    1. 决策树模型
    2. 决策树与if-then规则
    3. 决策树与条件概率分布
    4. 决策树学习
  2. 特征选择
    1. 特征选择问题
    2. 信息增益
    3. 信息增益比
  3. 决策树的生成
    1. ID3算法
    2. C4.5的生成算法
  4. 决策树的剪枝
  5. CART算法
    1. CART的生成
    2. CART剪枝

呈树形,基于特征对实例进行分类的过程。可以认为是if-then 规则的集合,或者在类空间和概率空间的条件概率分布。 通常包含3个步骤:特征选择、决策树的生成、决策树的修剪。

决策树模型与学习

决策树模型

决策树由结点和有向边组成。 结点:内部结点、叶结点 内部结点表示一个特征或属性,叶结点表示一个类。 将实例分到叶结点的类中。

决策树与if-then规则

if-then规则的一个重要的性质:互斥并且完备

决策树与条件概率分布

决策树还可以表示给定特征条件下类的条件概率分布。 决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。

决策树学习

本质:归纳出一组分类规则。 由训练数据集归纳出条件概率模型,得到的模型应该对未知数据有较好的预测。 决策树学习的损失函数:对数似然损失 策略:以损失函数为目标函数的最小化 启发式学习方法 次最优 递归地选择最优特征,对训练数据进行分割 过拟合 剪枝 泛化能力 学习算法包含:特征选择、决策树的生成、决策树的剪枝 常用算法:ID3、C4.5、CART

特征选择

特征选择问题

特征选择的准则:信息增益和信息增益比。

信息增益

熵:随机变量不确定性的度量 设X是一个取有限个值的离散随机变量,其概率分布为: 2017-2-27-决策树_041f24293b7b0bbf732a7c4d9376417250ac8e15.png 则随机变量X的熵定义为: 2017-2-27-决策树_d4b9650a614f375e28c3e10281e82c1ad81a939c.png 熵只依赖于X的分布,而与X的取值无关,可将X的熵记为H(p) 熵越大,随机变量的不确定性越大

条件熵H(Y X)表示在已知随机变量X的条件下随机变量Y的不确定性。

当熵和条件熵中的概率由数据估计得到时,所对应的熵和条件熵分别称为经验熵和经验条件熵。

信息增益表示得知特征X的信息而得到类Y的不确定性减少的程度。 定义为集合D的经验熵H(D)与特征A给定的条件下D的经验条件熵H(D|A)之差(互信息): 2017-2-27-决策树_26f30d0cf3d3c1ef50650af20f8da83c255913cc.png 决策树学习应用信息增益准则来选取特征,表示在特征A给定的条件下对数据集D进行分类的不确定性。 特征选择方法:计算各特征的信息增益,选择信息增益最大的特征。

信息增益比

以信息增益作为划分训练数据集的特征,存在偏向于选择取值较多的特征的问题,使用信息增益比进行校正。 信息增益比 2017-2-27-决策树_10445678d0a9813ba868decad122f274b97fa47d.png 定义为信息增益 2017-2-27-决策树_ab2256b4db499108f049723c3d98caffc9bd27df.png 与训练数据集关于特征A的值的熵 2017-2-27-决策树_447e4dd719a832a0d1b99a2e3aa67a2c691808ea.png 之比。其中, 2017-2-27-决策树_6e68810bfaf60ee190a5339b85c71a6b877053ce.png

决策树的生成

ID3算法

核心:在决策树各个结点上应用信息增益准则选取特征,递归得构建决策树。 ID3相当于用极大似然法进行概率模型的选择。 只有树的生成,容易产生过拟合。

C4.5的生成算法

对ID3进行改进,用信息增益比选择特征。

决策树的剪枝

通过极小化决策树整体的损失函数或代价函数来实现。 决策树的损失函数可以定义为: 2017-2-27-决策树_07fa0fe8f67668bd89638490dc40e5b6385543a5.png 其中经验熵: 2017-2-27-决策树_3876201b5a5befdf7fa16eab241cea3003d57822.png 2017-2-27-决策树_60c84728a9febe85f5af2f2382a1b5500727be7b.png : 叶结点有 2017-2-27-决策树_60c84728a9febe85f5af2f2382a1b5500727be7b.png 个样本点。 树T的叶结点个数为|T| 损失函数的极小化等价于正则化的极大似然估计

树的剪枝算法 递归地从叶结点向上回缩,若损失函数减小,则进行剪枝。 计算可在局部进行,可由动态规划算法实现。

CART算法

CART 分类与回归树 CART:在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。 包含两个步骤:决策树的生成、决策树剪枝

CART的生成

回归树:平方误差最小化 分类树:基尼系数最小化

回归树的生成 假设将输入空间划分为M个单元,每个单元上有一个固定的输出值2017-2-27-决策树_ae381398bf16c77a77b6832258535f28861edd81.png,于是回归模型可表示为: 2017-2-27-决策树_1d0b015eddd48bed7495ab0bc8b21a28f2d7f3f3.png 当输入空间划分确定时,可以用平方误差 2017-2-27-决策树_9cfe2b5fc1e7e416b9e18d49c2ace086fe95b2b4.png 来表示回归树对于训练数据的预测误差,用平方误差最小原则求解每个单元的最优输出值。 单元 2017-2-27-决策树_ce9af233aee92c58dd2661cf06439ace14fcebde.png 上的 2017-2-27-决策树_ae381398bf16c77a77b6832258535f28861edd81.png 的最优值 2017-2-27-决策树_76c4e28e101531a19a0c2773d6d2af3fc89f831d.png2017-2-27-决策树_ce9af233aee92c58dd2661cf06439ace14fcebde.png 上的所有输入实例 2017-2-27-决策树_c7757f6fab91f9a49d7e8b923e19c0e9d2d2d951.png 输出的均值。 2017-2-27-决策树_9ffe697165c838ad5e2e0c0d0daa33cb12f7b355.png 对输入空间进行划分,启发式: 选择第j个变量 2017-2-27-决策树_92b50a292cabc9dcb086dc7d8f71cd31fe8fac57.png 和它取的值s,作为切分变量和切分点,寻找最优的切分变量和切分点,将输入空间划分为两个区域,对每个子区域重复上述过程,直至满足条件。

分类树的生成 定义基尼指数: 2017-2-27-决策树_47f2157b2961621b5faf8591df19687a53de773b.png 对于给定的样本集合D,其基尼指数为 2017-2-27-决策树_5a31aa7a33433ba64cde5cd5f8a118468bc29d00.png 2017-2-27-决策树_bd9a5830dfaea38af701c8e1e1238699a78485c2.png 是D中属于第k类的样本子集, K是类的个数。 若样本集合根据特征A是否取a被划分为 2017-2-27-决策树_4801c53c85c8839a8653d1a96c710048745525b3.png2017-2-27-决策树_91a236f4e678ab468afe3e899da1c85003f00c64.png ,则在特征条件A下,集合D的基尼指数定义为: 2017-2-27-决策树_017ce2832bf3c2027818291f2fa887214685a63a.png 基尼指数表示集合的不确定性,基尼指数越大,集合的不确定性越大。 基尼指数和熵之半的曲线很接近,都可以近似地代表分类的误差率。

CART生成算法 对所有特征的每个取值计算基尼指数,选择基尼指数最小的特征及其所对应的切分点作为最优特征和最优切分点,将训练数据分为两个子结点中。重复直至满足条件。

CART剪枝

从完全生长的决策树底端剪去一些子树。 由两步组成: 从底端开始不断剪枝,直到根结点,形成子树序列; 通过交叉验证法在独立的验证集上对子序列进行测试,从中选取最优子树。

1.剪枝,形成一个子树序列 2017-2-27-决策树_e25d6a35e2f86790a57930d0da6dbe958739cf4b.png 2017-2-27-决策树_6d4e8a9e0b8a5bb0f177e969f78933884dbd0d3d.png 为对训练数据的预测误差(如基尼指数), 2017-2-27-决策树_4916c4cf173f815aa198299f3d52c84cedd6b199.png 为子树的叶结点的个数, 2017-2-27-决策树_f06f20dee81ab8248628631211abcbe3c7ee9a80.png 为权衡训练数据拟合程度和模型复杂度,2017-2-27-决策树_aaf6ce0a87df002be31d0e7e8c2225917d33a2ad.png 为参数为 2017-2-27-决策树_f06f20dee81ab8248628631211abcbe3c7ee9a80.png 时的子树T的整体损失。 用递归的方法进行剪枝,将 2017-2-27-决策树_f06f20dee81ab8248628631211abcbe3c7ee9a80.png 从小增大,得到临界点的 2017-2-27-决策树_3f81ed7f09456cd50a14ee8e86d3eafe9f5ff930.png 的值, 2017-2-27-决策树_187b09d9e1825d76ad3a4d448fd867fa96d2f013.png, 产生一系列的区间 2017-2-27-决策树_70ed1cd43c4d0a6cf8f5bdb4df61ea2c7f63a8c4.png, 对应的最优子树序列 2017-2-27-决策树_993456aaadecd17d864553e51e44159e75118591.png 。 2.在剪枝得到的子树序列张通过交叉验证选取最优子树 2017-2-27-决策树_595e6e3de328bf92029264e481c113c1c9deb4c4.png 利用独立数据集,测试子树序列的平方误差或基尼系数,最小的决策树被认为是最优的决策树。

更多