【正文】 Sofer) ? 《 高等數(shù)學(xué) 》 ? 《 運籌學(xué) 》 ? 《 數(shù)據(jù)結(jié)構(gòu) 》 Qamp。（概率論與隨機過程、最優(yōu)化問題、圖形學(xué) …… ） “All Models are wrong. Some are useful.” 參考文獻(xiàn) 1. A maximum entropy approach to natural language processing (Adam Berger) 2. A Brief MaxEnt Tutorial (Adam Berger) 3. Learning to parse natural language with maximum entropy models (Adwait Ratnaparkhi) 4. A simple Introduction to Maximum Entropy Models for Natural Language Processing (Adwait Ratnaparkhi) 參考文獻(xiàn) (Cont) ? Elements of Information Theory (Cover amp。 X可能是： ? TAG, CHUNK, BUILD/CHECK ?最優(yōu)解求法： GIS（ General Iterative Scaling Algorithm “一般梯度算法 ” ？） ?特征選?。褐蝗〕霈F(xiàn)次數(shù)大于等于 5的所有特征（比較簡單，但因此計算量也少多了） 應(yīng)用實例 ? 實驗結(jié)果： ?Upenn的 Corpus作為訓(xùn)練集合 ?Wall Street Journal上的句子作為測試對象 ?準(zhǔn)確率： 90%左右 應(yīng)用實例 分析： ?三層 Parser功不可沒（上層 Parser看到的是下層 Parser的所有信息 —包括處理點之前和之后的信息） ?MaxEnt模型提供了比較準(zhǔn)確的評價模型（不然三層 Parser會比單層 Parser引起更大的誤差累積， “ 失之毫厘謬以千里 ” ） 相關(guān)項目 ? CMU: Adam Berger ? U Penn: Adwait Ratnaparkhi ? Source Fe: opennlp. MAXENT ? …… 總結(jié)與啟發(fā) ? MaxEnt已經(jīng)是比較成功的一個 NLP模型，并獲得廣泛應(yīng)用 ? 從信息論獲得啟發(fā)（ 1948）：自然語言處理也是信息處理的一種。 ?得到概率分布： pX*(a|c)。 ? ? ? ?pHpH ?*敏感度分析與特征提取 Sensitivity ? How to work on insufficient data set? 最終結(jié)論應(yīng)該是約束條件越確定（ _p(x)越大）， lambda越大。 ? “ 有用？ ” 使到走這一步后熵減少最多 算法步驟 ? 有效特征集合 E={} //這個時候 p均勻分布 ? 計算最大熵 H(p*)。 直觀的過程： ? 什么特征都不限定：熵最大 ? 加一個特征：熵少一點（ .） ? 加的特征越多，熵越少 …… 特征選取算法 ? 目標(biāo)：選擇最有用的Ｋ個特征（知識） ? “ 最 ” ？－－全局的最優(yōu)解幾乎不可能 ? 可行的方法：逐步選擇最有用的信息。進(jìn)一步證明了最大熵模型的合理性。 ? ?37 1 ppP ??? ? 37101m a xm a x ppPp????? 最優(yōu)解是： p= ? 似然率的一般定義： ? ? ? ???xxpp xpL? ?? ?是實驗結(jié)果的分布模型是估計的概率分布xpxp最大似然率 Maximum Likelihood ? 似然率的一般定義： ? ? ? ???xxpp xpL? 似然率的對數(shù)形式： ? ? ? ? ? ? ? ??? ????????xxxpp xpxpxpL l ogl og? ?? ?是實驗結(jié)果的分布模型是估計的概率分布xpxp最大似然率 Maximum Likelihood ? 在 NLP里面，要估計的是： ? ?語法標(biāo)注上下文::|yxxyp? 似然率是： ? ? ? ? ? ?? ? ? ? ? ?? ?? ? ? ? ? ? ? ????????yxyxyxyxpxpyxpxypyxpxypxpyxpyxpyxppL,l o g,|l o g,|l o g,l o g,是常數(shù)，可以忽略 ? ? ? ? ? ?? ??yxxypxpyxp,|log,最大似然率 Maximum Likelihood ? 在 NLP里面，要估計的是： ? ?語法標(biāo)注上下文::|yxxyp? 似然率可以定義為： ? ? ? ? ? ???yxp xypyxppL,|log,? 通過求值可以發(fā)現(xiàn)，如果 p(y|x)的形式是最大熵模型的形式的話，最大熵模型與最大似然率模型一致。 10次拋硬幣的結(jié)果是： 畫畫字畫畫畫字字畫畫 假設(shè) p是每次拋硬幣結(jié)果為 “ 畫 ” 的概率。 馬鞍點： yxyxyx CCCyx *,**,*,|*)*,( ??非線性規(guī)劃中的對偶問題 )(m a x pH ? ? ii bpCki ??? :1拉格朗日函數(shù)： ? ? ? ? ? ?? ??????kiiii bpCpHpL1, ??于是： ? ??? ,m inm a x pLp ? ? ? ? ? ?? ???????????iiiibpCibpCipHpL::::,m in ??因此，為了盡量大， p的選取必須保證 ? ? 滿足約束ppHpLp |)(m a x,m i nm a x ???? ? ii bpCki ???? :1考慮： 對偶問題與拉格朗日函數(shù)： )(m a x pH ? ? ii bpCki ??? :1同時： ? ? ? ? ? ?? ??????kiiiip bpCpHpL1,m inm a x ???等價于： ? ? ? ??? ?? ,m a xm i n,m i nm a x pLpL pp ?而 ? ? ? ??? *,m a x pLpLp ??? iii yxfexZxyp),()(1)|(* ?對偶問題與拉格朗日函數(shù)： ? ? ? ?? ?? ???????*,m i n,m axm i n,m i nm axm axppLpLpLpHpp???滿足約束?? iii yxfexZxyp),()(1)|(* ???梯度遞減法 ? ? ? ? ? ? ? ? ? ? ? ?? ?? ? ? ? ? ? ? ?? ? ? ? ? ?? ?? ? ? ? ? ? ? ? ? ?? ?? ? ? ?? ? ? ? ? ? ? ? ? ?? ?? ? ? ? ? ? ? ??????? ????????????????????????????????????xyxyxyxyxki yxiixZxpyxyxpyxyxpxZxypxpyxyxpyxxZyxxypxpyxyxpyxxypxypxpyxpxypxpyxfpHpLl o g,l o g|,l o g,|,|l o g|,|,*,,1 ,??把 p*代入 L，得到： 令： ? ? ? ?????kiii yxfyx1, ?梯度遞減法 求導(dǎo)，計算 L的梯度： ? ? ? ? ? ? ? ? ? ??? ????xyxxZxpyxyxppL l o g,*,?? ? ? ?????kiii yxfyx1, ?? ?? ? ? ? ? ? ? ?? ? ? ? ? ?? ?? ??