最大熵模型(matlab应用)

最大熵模型与自然语言处理MaxEntModel NLP laputac liu01 NLPGroup AILab TsinghuaUniv Topics NLP与随机过程的关系 背景 最大熵模型的介绍 熵的定义 最大熵模型 最大熵模型的解决 非线性规划 对偶问题 最大似然率 特征选取问题应用实例总结与启发 NLP与随机过程 NLP 已知一段文字 x1x2 xn n个词 标注词性y1y2 yn标注过程 已知 x1x2 xn求 y1已知 x1x2 xny1求 y2已知 x1x2 xny1y2求 y3已知 x1x2 xny1y2y3求 y4 NLP与随机过程 yi可能有多种取值 yi被标注为a的概率有多少 随机过程 一个随机变量的序列 x1x2 xnp y1 a x1x2 xn x1x2 xny1p y2 a x1x2 xny1 x1x2 xny1y2p y3 a x1x2 xny1y2 x1x2 xny1y2y3p y4 a x1x2 xny1y2y3 NLP与随机过程 x1x2 xnp y1 a x1x2 xn x1x2 xny1p y2 a x1x2 xny1 x1x2 xny1y2p y3 a x1x2 xny1y2 x1x2 xny1y2y3p y4 a x1x2 xny1y2y3 问题 p yi a x1x2 xny1y2 yi 1 怎么求 yi与x1x2 xny1y2 yi 1的关系 NLP与随机过程 问题 p yi a x1x2 xny1y2 yi 1 怎么求 yi与x1x2 xny1y2 yi 1的关系 一个直观的解决 问题again x1x2 xny1y2 yi 1 What sEntropy AnExample 假设有5个硬币 1 2 3 4 5 其中一个是假的 比其他的硬币轻 有一个天平 天平每次能比较两堆硬币 得出的结果可能是以下三种之一 左边比右边轻右边比左边轻两边同样重问 至少要使用天平多少次才能保证找到假硬币 某年小学生数学竞赛题目 P 称硬币 cont 答案 2次一种方法 Why最少2次 称硬币 cont Let x是假硬币的序号 Let yi是第i次使用天平所得到的结果 用天平称n次 获得的结果是 y1y2 yny1y2 yn的所有可能组合数目是3n我们要通过y1y2 yn找出x 所以 每个y1y2 yn组合最多可能有一个对应的x取值 因为x取X中任意一个值的时候 我们都要能够找出x 因此对于任意一个x的取值 至少要有一个y1y2 yn与之对应 根据鸽笼原理 称硬币 cont Let x是假硬币的序号 Let Yi是第i次使用天平所得到的结果 用y1y2 yn表达x 即设计编码 x y1y2 ynX的 总不确定度 是 Y的 表达能力 是 至少要多少个Y才能准确表示X 称硬币 cont Why 为什么用log 表达能力 与 不确定度 的关系 称硬币 cont 为什么用log 假设一个Y的表达能力是H Y 显然 H Y 与Y的具体内容无关 只与 Y 有关 两个Y 就是 y1y2 的表达能力是多少 y1可以表达三种情况 y2可以表达三种情况 两个并列 一共有 3 3 9种情况 乘法原理 因此 称硬币 cont 表达能力 与 不确定度 的关系 都表达了一个变量所能变化的程度 在这个变量是用来表示别的变量的时候 这个程度是表达能力 在这个变量是被表示变量的时候 这个程度是不确定度 而这个可变化程度 就是一个变量的熵 Entropy 显然 熵与变量本身含义无关 仅与变量的可能取值范围有关 称硬币 Version 2 假设有5个硬币 1 2 3 5 其中一个是假的 比其他的硬币轻 已知第一个硬币是假硬币的概率是三分之一 第二个硬币是假硬币的概率也是三分之一 其他硬币是假硬币的概率都是九分之一 有一个天平 天平每次能比较两堆硬币 得出的结果可能是以下三种之一 左边比右边轻右边比左边轻两边同样重假设使用天平n次找到假硬币 问n的期望值至少是多少 不再是小学生问题 P 称硬币 Version 2 因为第一个 第二个硬币是假硬币的概率是三分之一 比其他硬币的概率大 我们首先 怀疑 这两个 第一次可以把这两个做比较 成功的概率是三分之二 失败的概率是三分之一 如果失败了 第二次称剩下的三个 所以 期望值是 称硬币 Version 2 数据结构 Huffman编码问题 称硬币 Version 2 数据结构 Huffman编码问题 称硬币 Version 2 数据结构 Huffman编码问题 用反证法可以证明 这个是最小值 假设第一个和第二个硬币中有一个要称两次的话 称硬币 Version 2 数据结构 Huffman编码问题 称硬币 Version 3 4 更广泛地 如果一个随机变量x的可能取值为X x1 x2 xk 要用n位y y1y2 yn表示 每位y有c种取值 n的期望值至少为 一般地 我们令c为2 二进制表示 于是 X的信息量为 What sEntropy 定义 X的具体内容跟信息量无关 我们只关心概率分布 于是H X 可以写成 熵的性质 第一个等号在X为确定值的时候成立 没有变化的可能 第二个等号在X均匀分布的时候成立 熵的性质 证明 熵的性质 证明 详细证明略 求条件极值就可以证明了 求偏导数 条件是 所有的概率之和为1 结论 均匀分布的时候 熵最大 ConditionalEntropy 有两个变量 x y 它们不是独立的 已知y x的不确定度又是多少呢 ConditionalEntropy ConditionReducesEntropy C R E 知识 Y 减少不确定性 X 证明 略 用文氏图说明 已知与未知的关系 对待已知事物和未知事物的原则 承认已知事物 知识 对未知事物不做任何假设 没有任何偏见 已知与未知的关系 例子 已知 学习 可能是动词 也可能是名词 可以被标为主语 谓语 宾语 定语 令x1表示 学习 被标为名词 x2表示 学习 被标为动词 令y1表示 学习 被标为主语 y2表示被标为谓语 y3表示宾语 y4表示定语 得到下面的表示 如果仅仅知道这一点 根据无偏见原则 学习 被标为名词的概率与它被标为动词的概率相等 已知与未知的关系 例子 已知 学习 可能是动词 也可能是名词 可以被标为主语 谓语 宾语 定语 学习 被标为定语的可能性很小 只有0 05 除此之外 仍然坚持无偏见原则 我们引入这个新的知识 已知与未知的关系 例子 已知 学习 可能是动词 也可能是名词 可以被标为主语 谓语 宾语 定语 学习 被标为定语的可能性很小 只有0 05当 学习 被标作动词的时候 它被标作谓语的概率为0 95 除此之外 仍然坚持无偏见原则 我们尽量使概率分布平均 但问题是 什么是尽量平均的分布 引入这个新的知识 最大熵模型MaximumEntropy 概率平均分布 熵最大我们要一个x和y的分布 满足 同时使H Y X 达到最大值 最大熵模型MaximumEntropy 最大熵模型MaximumEntropy WhatisConstraints 模型要与已知知识吻合Whatisknown 训练数据集合 一般模型 P p p是X上满足条件的概率分布 特征 Feature 特征 x y y 这个特征中需要确定的信息x 这个特征中的上下文信息注意一个标注可能在一种情况下是需要确定的信息 在另一种情况下是上下文信息 x1x2 xnp y1 a x1x2 xn x1x2 xny1p y2 a x1x2 xny1 样本 Sample 关于某个特征 x y 的样本 特征所描述的语法现象在标准集合里的分布 xi yi pairsyi是y的一个实例xi是yi的上下文 x1 y1 x2 y2 x3 y3 特征与样本 已知 学习 可能是动词 也可能是名词 可以被标为主语 谓语 宾语 定语 学习 被标为定语的可能性很小 只有0 05特征 当 学习 被标作动词的时候 它被标作谓语的概率为0 95 x是什么 y是什么 样本是什么 特征与样本 已知 学习 可能是动词 也可能是名词 可以被标为主语 谓语 宾语 定语 特征 学习 被标为定语的可能性很小 只有0 05当 学习 被标作动词的时候 它被标作谓语的概率为0 95 x是什么 y是什么 样本是什么 特征与样本 特征函数 对于一个特征 x0 y0 定义特征函数 特征函数期望值 对于一个特征 x0 y0 在样本中的期望值是 是 x y 在样本中出现的概率 条件 Constraints 条件 对每一个特征 x y 模型所建立的条件概率分布要与训练样本表现出来的分布相同 假设样本的分布是 已知 特征f在模型中的期望值 最大熵模型MaximumEntropy NLP模型 P p p是y x的概率分布并且满足下面的条件 对训练样本 对任意给定的特征fi 最大熵模型MaximumEntropy NLP模型 最大熵模型的解决 问题 已知若干条件 要求若干变量的值使到目标函数 熵 最大数学本质 最优化问题 OptimizationProblem 条件 线性 等式目标函数 非线性非线性规划 线性约束 non linearprogrammingwithlinearconstraints 非线性规划基本概念NonlinearProgramming 解决的思路 非线性规划问题 带约束 拉格朗日法 非线性规划问题 不带约束UnconstrainedProblem 求偏导数法 解决不带约束求解问题 解方程 求出原问题的解法 非线性规划基本概念NonlinearProgramming p m维向量 H p 关于p的非线性函数A n m常数矩阵 b n维向量 如何去掉约束 抽象问题 假设 A的行向量线性无关 确定了m维空间里面n个方向上 就是与Ap b确定的m n个方向 垂直 的n个方向 的取值 p只能在剩下的r m n个方向上面移动 非线性规划基本概念NonlinearProgramming 假设Z是跟Ap b垂直的方向量 Z m m n 常数矩阵 就是p能够自由活动的所有空间了 v m n维变量于是有 非线性规划基本概念NonlinearProgramming p m维向量 H p 关于p的非线性函数A n m常数矩阵 b n维向量 如何去掉约束 抽象问题 Z m m n 常数矩阵v m n维变量 极值条件 Z m m n 常数矩阵v m n维变量 极值条件 把分解成Z方向向量和A方向向量 极值条件 Z m m n 常数矩阵v m n维变量 极值条件 p m维向量 H p 关于p的非线性函数A n m常数矩阵 b n维向量 令 假设 A的行向量线性无关 拉格朗日算子LagrangeMultiplier 一般地 对于k个限制条件的ConstrainedOptimization问题 拉格朗日函数为 其中引入的拉格朗日算子 拉格朗日算子LagrangeMultiplier 拉格朗日函数 可能的最优解 Exponential 最优解的存在性 一阶导数为零 二阶导数小于零 所得到的是最大值 最优解形式 Exponential 最优解 Exponential 最优解 Exponential 能不能找到另一种逼近 比如 等价成求某个函数的最大 最小值 几乎不可能有解析解 包含指数函数 近似解不代表接近驻点 对偶问题Duality 对偶问题的引入 Alice和Bob的游戏 有一个2 2的矩阵 每次Alice挑一个数x x 1或者2 Bob也挑一个数y y 1或者2 两人同时宣布所挑的数字 然后看Cx y是多少 Bob要付AliceCx y块钱 如果Cx y是负数 Alice给Bob钱 矩阵 如下 对偶问题AlicevsBob 假设 Alice和Bob都是聪明而贪得无厌的人 而且他们都清楚对方也很聪明和很贪心 Alice的策略 找一个x 无论Bob怎么挑y Cx y要尽量大 Bob的策略 找一个y 无论Alice怎么挑x Cx y要尽量小 双方都很聪明 双方都对对方有 最坏打算 对偶问题AlicevsBob Alice的选择 x 2Bob的选择 y 2 AlicevsBobVersion 2 Alice的选择 x 1Bob的选择 y 2 对偶问题AlicevsBob Version1 Alice的估计 结果 Bob的估计Version2 Alice的估计 结果 Bob的估计一般情况 Alice的估计 结果 Bob的估计 定理 当存在马鞍点 SaddlePoint 的时候 等号成立 并且结果 马鞍点的值 马鞍点 非线性规划中的对偶问题 拉格朗日函数 于是 因此 为了尽量大 p的选取必须保证 考虑 对偶问题与拉格朗日函数 同时 等价于 而 对偶问题与拉格朗日函数 梯度递减法 把p 代入L 得到 令 梯度递减法 求导 计算 L的梯度 梯度递减法 递推公式 收敛问题 最大似然率MaximumLikelihood 最大似然率 找出与样本的分布最接近的概率分布模型 简单的例子 10次抛硬币的结果是 画画字画画画字字画画假设p是每次抛硬币结果为 画 的概率 则 得到这样的实验结果的概率是 最大似然率MaximumLikelihood 最大似然率 找出与样本的分布最接近的概率分布模型 最优解是 p 0 7似然率的一般定义 最大似然率MaximumLikelihood 似然率的一般定义 似然率的对数形式 最大似然率MaximumLikelihood 在NLP里面 要估计的是 似然率是 是常数 可以忽略 最大似然率MaximumLikelihood 在NLP里面 要估计的是 似然率可以定义为 通过求值可以发现 如果p y x 的形式是最大熵模型的形式的话 最大熵模型与最大似然率模型一致 最大似然率 为书写方便 令 最大似然率 最大似然率MaximumLikelihood 结论 最大熵的解 无偏见地对待不确定性 同时是最吻合样本数据分布的解 进一步证明了最大熵模型的合理性 偶然 必然 Itsohappensthat 熵 不确定度似然率 与知识的吻合度最大熵 对不确定度的无偏见分配最大似然率 对知识的无偏见理解知识 不确定度的补集 特征选取问题 问题 所有知识可信吗 所有知识都有用吗 太多知识怎么办 在NLP里面 上下文信息可以很多很多种 那些是有用呢 特征选取问题 Remind 熵是描述不确定度的 知识是不确定度的补集 不确定度越小 模型越准确 直观的过程 什么特征都不限定 熵最大加一个特征 熵少一点 C R E 加的特征越多 熵越少 特征选取算法 目标 选择最有用的 个特征 知识 最 全局的最优解几乎不可能可行的方法 逐步选择最有用的信息 每一步用 贪心 原则 挑选 现在看来 最有用的那个特征 有用 使到走这一步后熵减少最多 算法步骤 有效特征集合E 这个时候p均匀分布计算最大熵H p 显然 对以下步骤循环K次 对每个不在E里面的特征fi 把E fi 作为有效特征 计算最大熵Hi pi 假设Hm pm 最小 则 E E fm 敏感度分析与特征提取Sensitivity Howtoworkoninsufficientdataset 最终结论应该是约束条件越确定 p x 越大 lambda越大 应用实例 AdwaitRatnaparkhi s LearningtoParseNaturalLanguagewithMaximumEntropyModels 创新点 用MaxEnt模型辅助Shift reduceParsing 应用实例 Parser的特点 三层ParserK BFS搜索 每层只搜索最好的K个方案 derivations 最好 概率最大概率 最大熵模型得到的概率分布 应用实例 数据流 应用实例 概率 最大熵模型得到的概率分布事先对每类Parsing都训练一个最大熵模型 得到概率分布 pX a c a是action c是上下文 X可能是 TAG CHUNK BUILD CHECK最优解求法 GIS GeneralIterativeScalingAlgorithm 一般梯度算法 特征选取 只取出现次数大于等于5的所有特征 比较简单 但因此计算量也少多了 应用实例 实验结果 Upenn的Corpus作为训练集合WallStreetJournal