条件随机场-详细

条件随机场conditionalrandomfields条件随机场模型是Lafferty于2001年，在最大熵模型和隐马尔科夫模型的基础上，提出的一种判别式概率无向图学习模型，是一种用于标注和切分有序数据的条件概率模型。条件随机场概述CRF最早是针对序列数据分析提出的，现已成功应用于自然语言处理(NaturalLanguageProcessing，NLP）、生物信息学、机器视觉及网络智能等领域。序列标注标注：人名地名组织名观察序列：毛泽东标注：名词动词助词形容词副词……观察序列：今天天气非常好！实体命名识别汉语词性标注四、隐马尔可夫模型（HiddenMarkovModel，HMM）一、产生式模型和判别式模型（Generativemodelvs.Discriminativemodel）二、概率图模型（GraphicalModels）五、最大熵模型（MaximumEntropyModel，MEM）七、条件随机场（conditionalrandomfields，CRF）三、朴素贝叶斯分类器（NaiveBayesClassifier）六、最大熵马尔可夫模型（MEMM）一、产生式模型和判别式模型（Generativemodelvs.Discriminativemodel）•产生式模型：构建o和s的联合分布p(s,o)，因可以根据联合概率来生成样本，如HMM，BNs，MRF。产生式模型：无穷样本==》概率密度模型=产生模型==》预测判别式模型：有限样本==》判别函数=预测模型==》预测•判别式模型：构建o和s的条件分布p(s|o)，因为没有s的知识，无法生成样本，只能判断分类，如SVM，CRF，MEMM。o和s分别代表观察序列和标记序列一个举例：(1,0),(1,0),(2,0),(2,1)产生式模型：P(x,y)：P(1,0)=1/2,P(1,1)=0,P(2,0)=1/4,P(2,1)=1/4.判别式模型：P(y|x)：P(0|1)=1,P(1|1)=0,P(0|2)=1/2,P(1|2)=1/2两种模型比较：Generativemodel：从统计的角度表示数据的分布情况，能够反映同类数据本身的相似度，不关心判别边界。优点:•实际上带的信息要比判别模型丰富，研究单类问题比判别模型灵活性强•能更充分的利用先验知识•模型可以通过增量学习得到缺点：•学习过程比较复杂•在目标分类问题中易产生较大的错误率Discriminativemodel：寻找不同类别之间的最优分类面，反映的是异类数据之间的差异。优点:•分类边界更灵活，比使用纯概率方法或生产模型得到的更高级。•能清晰的分辨出多类或某一类与其他类之间的差异特征•在聚类、viewpointchanges,partialocclusionandscalevariations中的效果较好•适用于较多类别的识别缺点：•不能反映训练数据本身的特性。•能力有限，可以告诉你的是1还是2，但没有办法把整个场景描述出来。二者关系：由生成模型可以得到判别模型，但由判别模型得不到生成模型。二、概率图模型（GraphicalModels）(,)GVE:V顶点/节点，表示随机变量:E边/弧两个节点邻接：两个节点之间存在边，记为，不存在边，表示条件独立~ijXX路径：若对每个i，都有，则称序列为一条路径1iiXX1,...,NXX概率图模型：是一类用图的形式表示随机变量之间条件依赖关系的概率模型，是概率论与图论的结合。图中的节点表示随机变量，缺少边表示条件独立假设。根据图中边有无方向，常用的概率图模型分为两类：有向图：最基本的是贝叶斯网络(BayesianNetworks,BNs)年龄Age职业Occupation气候Climate疾病Disease症状Symptoms举例(,,,,)PAOCDSM()()()(,,,)(,)PAMPOMPCMPDAOCMPSDM有向图模型的联合概率分解1X2X3X4X5X121(,)(())NNiiiPXXXpXX，，1251213242534(,)()()()()()PXXXpXpXXpXXpXXpXXX，，每个节点的条件概率分布表示为：P(当前节点|它的父节点)联合分布：无向图：马尔可夫随机场(MarkovRandomFields,MRF)马尔可夫随机场模型中包含了一组具有马尔可夫性质的随机变量，这些变量之间的关系用无向图来表示(,),ijijijpxxjipxxxx马尔科夫性：举例团(clique)：任何一个全连通（任意两个顶点间都有边相连）的子图最大团(maximalclique)：不能被其它团所包含的团X1X2X3X4例如右图的团有C1={X1,X2,X3}和C2={X2,X3,X4}无向图模型的联合概率分解势函数（potentialfunction）():iiC是关于上随机变量的函数iC1211(,)()NNiiiPXXXCZ，，12,1()NNiiXXXiZC，，123411232234123411232234,,,(,,)(,,)(,,,)(,,)(,,)XXXXXXXXXXpXXXXXXXXXX设x∈Ω是一个类别未知的数据样本，Y为类别集合，若数据样本x属于一个特定的类别yj，那么分类问题就是决定P(yj|x)，即在获得数据样本x时，确定x的最佳分类。所谓最佳分类，一种办法是把它定义为在给定数据集中不同类别yj先验概率的条件下最可能的分类。贝叶斯理论提供了计算这种可能性的一种直接方法。三、朴素贝叶斯分类器（NaiveBayesClassifier）如果没有这一先验知识，那么可以简单地将每一候选类别赋予相同的先验概率。不过通常我们可以用样例中属于yj的样例数|yj|比上总样例数|D|来近似，即P(yj)代表还没有训练数据前，yj拥有的初始概率。P(yj)常被称为yj的先验概率(priorprobability)，它反映了我们所拥有的关于yj是正确分类机会的背景知识，它应该是独立于样本的。jj|y|P(y)=|D|()()()()jjjpxypypyxpx()()()()jjjpxypypyxpx是联合概率，指当已知类别为yj的条件下，看到样本x出现的概率。()()jjpxypy若设12(,,,)mxaaa则12()(,,,)jmjpxypaaay条件独立性：(,)()()pabcpacpbc在给定随机变量C时，a，b条件独立。假定：在给定目标值yj时，x的属性值之间相互条件独立。12()(,,,)jmjpxypaaay1p(|)mijiayP(yj|x)被称为Y的后验概率（posteriorprobability），因为它反映了在看到数据样本x后yj成立的置信度。()()()()jjjpxypypyxpx是后验概率，即给定数据样本x时yj成立的概率，而这正是我们所感兴趣的。()jpyx123argmax()argmax(,,)jjjjpyxpyxxx()()()()jjjpypxypyxpx1,jY后验概率123123(,,)()argmax(,,)jjjpxxxypypxxx123argmax(,,,)jjpxxxy基本假设31argmax()()ijjjipxypy朴素贝叶斯分类器的概率图表示jyjy123123(,,,)()()()()jjjjjPxxxypypxypxypxyjyx隐马尔可夫模型的概率图表示11(,)()()niiiiipyxpyypxyjyx三、隐马尔可夫模型（HiddenMarkovModel,HMM）马尔可夫模型：是一个三元组λ=(S,,A)其中S是状态的集合，是初始状态的概率,A是状态间的转移概率。S0S1ST-1ST一阶马尔可夫链晴云雨0.500.3750.1250.250.1250.6250.250.3750.375todaysuncloudrainyesterdaysuncloudrain（1，0，0）123,,Ssss晴云雨一阶马尔可夫模型的例子问题：假设今天是晴天，请问未来三天的天气呈现云雨晴的概率是多少？隐马尔可夫模型(HMM)0.050.150.200.600.250.250.250.250.50.350.100.05soggydampdryishdrysuncloudrainHMM是一个五元组λ=(Y,X,,A,B)，其中Y是隐状态（输出变量）的集合，）X是观察值（输入）集合，是初始状态的概率，A是状态转移概率矩阵，B是输出观察值概率矩阵。0.500.3750.1250.250.1250.6250.250.3750.375todaysuncloudrainyesterdaysuncloudrainHMM实例实验进行方式如下：•根据初始概率分布，随机选择N个缸中的一个开始实验•根据缸中球颜色的概率分布，随机选择一个球，记球的颜色为x1，并把球放回缸中•根据缸的转移概率分布，随机选择下一口缸，重复以上步骤。UrnNUrn1Urn2ObservedBallSequence最后得到一个描述球的颜色的序列x1,x2,…称为观察值序列X。问题2：给定观察序列以及模型λ，如何选择一个对应的状态序列，使得Y能够最为合理的解释观察序列X？12,,,TXxxx12(,,,)NYyyy问题1：给定观察序列以及模型,计算(,,)AB()PX12,,,TXxxx问题3：给定观察序列，调整模型参数,使最大？12,,,TXxxx(,,)AB()PX评价问题解码问题参数学习问题(/)PX(/,)PXY(/)PYY所有0.60.40.90.1RG120.30.20.70.8=[0.50.5]TRRG①①①0.50.30.30.60.60.4①①②①②①基本算法：问题1：给定观察序列以及模型,计算(,,)AB()PX12,,,TXxxx12()(,,,)1tttiPxxxyitT　　　11()()1iiibxtT　　　111()[()]()11,1NttijjtijiabxtTjN　　　1(/)()NTiPXi终结：递归：定义前向变量：初始化：前向算法：前向算法举例：.6.2.2.2.5.3.0.3.7RGB123.5.6.4.4.1=[100]TRRGB1231×.6.60×.2.00×.0.0.5×.6.18.6×.2.048.0.4×.2.1×.0.4×.0.5×.2.018.6×.5.0504.01116.4×.5.1×.3.4×.3.5×.2.0018.6×.3.01123.01537.4×.3.1×.7.4×.71...tt+1...a1jt1yN.yi.yj..y1tNtiaNjaij1jt前向法示意图后向法定义后向变量12()(,,,/)11tttTtiPxxxyitT　　　终结：递归：初始化：()11TiiN　　　111()()()1,2,...,1,1NtijjttjiabxjtTTiN　11(/)()NiPXi问题2：给定观察序列以及模型λ，如何选择一个对应的状态序列，使得Y能够最为合理的解释观察序列X？12,,,TXxxx12(,,,)NYyyy1211,2,()[...,,]ttttiPyyyyixxx…定义：要找的就是T时刻所代表的那个状态序列()Tiargmax(|)YPYXViterbi算法：11()()iiibx111()max()()ttijjtiNjiabx)(max1iPTNi111()argmax()()ttijjtiNjiabx1argmax()TTiNyi11(),1,,1tttyytT0)(1iViterb