【正文】 ? ? ? ? ?? ?? ?? ?? ? ? ? ? ?? ?? ?????? ?????????????????????????x yjipx yjyxfyxix iyxixyxkjjjiiyxfxypxpfEyxfexZxpyxfyxpxZxZxpyxfyxpxZxpyxfyxpLkjjj,|*,1,1,l o g,1, 1?????? ??yyxfiiiexZ ),()( ?梯度遞減法 遞推公式： ? ? ? ? ? ? ? ???????yxjipiyxfxypxpfEL,|*?? ? ? ? ? ? ? ? ? ?????????? ??yxjipnini yxfxypxpfEc,1 ,|*??收斂問題 …… 最大似然率 Maximum Likelihood ? 最大似然率：找出與樣本的分布最接近的概率分布模型。 yxCA l i c eB obyB obxA l i c eC ,:::3421??????? ??雙方都很聰明：雙方都對對方有 “ 最壞打算 ” yxxy C ,m a xm inyxyx C ,m inm a x對偶問題 Alice vs Bob yxCA l i c eB obyB obxA l i c eC ,:::3421??????? ??yxxyCy ,m axm inar g* ?yxyxCx ,m inm a xa r g* ?? Alice的選擇： x*=2 ? Bob的選擇： y*=2 ????????31m in, yxy C? ?34ma x , ?yxx C3: 2,2 ?? CAl i c eBo bAlice vs Bob yxCA l i c eB obyB obxA l i c eC ,:::2421??????????yxxyCy ,m axm inar g* ?yxyxCx ,m inm a xa r g* ?? Alice的選擇： x*=1 ? Bob的選擇： y*=2 ?????????21m in, yxy C? ?24ma x , ?yxx C2: 2,1 ?? CAl i c eBo b對偶問題 Alice vs Bob Version 1: Alice的估計 =結果 =Bob的估計 Version 2: Alice的估計 結果 =Bob的估計 一般情況 :Alice的估計 =結果 =Bob的估計 yxxyyxyx CC , m a xm i nm i nm a x ?定理：當存在馬鞍點（ Saddle Point）的時候，等號成立。 Alice的策略： 找一個 x，無論 Bob怎么挑 y， Cx,y 要盡量大。矩陣Ｃ如下： ?????? ??3421C對偶問題 Alice vs Bob 假設： Alice和 Bob都是聰明而貪得無厭的人。然后看 Cx,y是多少， Bob要付 Alice Cx,y塊錢。每次 Alice挑一個數(shù) x (x=1或者 2)， Bob也挑一個數(shù) y (y=1或者 2)。 )(?f對偶問題 Duality 對偶問題的引入。)( ** 極值條件 0)()( ** ????? pLApH T ?? p: m維向量； H(p): 關于 p的非線性函數(shù) ? A: n*m常數(shù)矩陣； b: n維向量 bAppH?)(m a x令： 假設： A的行向量線性無關。)(***??????????????? TTTTTAZZvZpHZvHAZvpH?? TTAxHZvAZvpH??????????)(039。??????????ZvZvZAZAZZvZ TTTT ?039。039。()( *2*2** ??????把 分解成 Z方向向量和 A方向向量： )( *pH??TAZvpH ??? 39。 ? Z: m*(mn)常數(shù)矩陣 ) bpAZvpp???就是 p能夠自由活動的所有空間了。 p只能在剩下的 r=mn個方向上面移動。 出現(xiàn)的概率xxp ?)(在樣本中的期望值特征 ffp ?)(假設樣本的分布是（已知）： 出現(xiàn)的概率xyyxp ?),(特征 f在模型中的期望值： ? ? ? ?? ?? ? ? ? ? ?? ?? ? ? ? ? ?? ???????iiiiiiyxiiiiiyxiiiiiyxiiiiyxfxpxypyxfxpxypyxfyxpfp,|,|,)()()( fpfp ?最大熵模型 Maximum Entropy )|(* m a xa r g XYHpPp ??NLP模型： P={p|p是 y|x的概率分布并且滿足下面的條件 } 對訓練樣本，對任意給定的特征 fi： )()( ii fpfp ?最大熵模型 Maximum Entropy ? ?? ? ? ?? ?? ?? ?? ? ??????????????????????yyxiyxiixypxyxfyxpyxfxpxypfxypP1|:),(,),(|:|,NLP模型： ? ? ? ? ? ?? ????yxPp xypxpxypp, |1l og|* m a xa rg最大熵模型的解決 ?問題： 已知若干條件，要求若干變量的值使到目標函數(shù) （熵）最大 ?數(shù)學本質： 最優(yōu)化問題（ Optimization Problem） ? 條件：線性、等式 ? 目標函數(shù)：非線性 非線性規(guī)劃（線性約束） (nonlinear programming with linear constraints) 非線性規(guī)劃基本概念 Nonlinear Programming ? 解決的思路： 非線性規(guī)劃問題（帶約束） （拉格朗日法） 非線性規(guī)劃問題（不帶約束 Unconstrained Problem） （求偏導數(shù)法） 解決不帶約束求解問題 （解方程） 求出原問題的解法 非線性規(guī)劃基本概念 Nonlinear Programming p: m維向量； H(p): 關于 p的非線性函數(shù) A: n*m常數(shù)矩陣； b: n維向量 bAppH?)(m a x如何去掉約束？抽象問題： 假設： A的行向量線性無關?？梢员粯藶橹髡Z、謂語、賓語、定語 …… “ 學習 ” 被標為定語的可能性很小，只有 特征：當 “ 學習 ” 被標作動詞的時候，它被標作謂語的概率為 x是什么 ? y是什么 ? 樣本是什么 ? 特征與樣本 已知： “ 學習 ” 可能是動詞，也可能是名詞。可以被標為主語、謂語、賓語、定語 …… “ 學習 ” 被標為定語的可能性很小，只有 當 “ 學習 ” 被標作動詞的時候，它被標作謂語的概率為 除此之外，仍然堅持無偏見原則，我們盡量使概率分布平均。 1)()( 21 ?? xpxp 1)(41???iiyp)()()()( 4321 ???? ypypypyp已知與未知的關系 —例子 已知： “ 學習 ” 可能是動詞，也可能是名詞。 令 y1表示 “ 學習 ”被標為主語， y2表示被標為謂語， y3表示賓語， y4表示定語