條件最大熵（20191029）
有向圖模型
- 有向圖模型的分解
一階馬爾科夫模型也是有向圖模型，是鏈式的
HMM也是，
無向圖模型
團（全連通子圖）、最大團（不被其他團所包含的團）
- 勢函數(shù)：把團映射為正實數(shù)，團中不同的取值組合映射到不同的正實數(shù)上。
- 以團為單位，把聯(lián)合概率分解為勢函數(shù)的乘積，需要歸一化
- 為保證為正數(shù)，可以利用指數(shù)勢函數(shù)
有向圖vs無向圖
- 同：把聯(lián)合分布分解為多個因子
- 不同：
有向圖：因子是概率，不需要歸一；不需要歸一，訓練相對高效
無向圖：因子是勢函數(shù)，需要歸一；靈活，但全局歸一代價高
條件隨機場模型（無向圖）
略
20191119 句法分析
NP，名詞短語；VP，動詞性短語
CFG（上下文無關(guān)句法分信息）
上下文無關(guān)文法的用法
- 生成裝置。生成語言中的句子 book that flight，不斷替換NP為noun等等。枚舉，窮舉，派生出來。
- 識別裝置。判斷句子合法
- 分析裝置。判斷合法+產(chǎn)生句法結(jié)構(gòu)
句法樹（parse）
主要問題：歧義
如何消除歧義？（句法分析）
- 人工語言的語法分析
沒有歧義，打多基于上下文無關(guān)的算法（LL分析法，LR分析法）
由于歧義，對于自然語言，不能直接用，句法分析。 - 句法分析算法
大多基于上下文無關(guān)算法
（1）自頂向下的句法分析“周瑜打敗了曹操”
從開始符號S出發(fā)，不斷使用不同規(guī)則，如果能推到出來，是一個句子。（正向）
（2）自底向上，逆向規(guī)約
先分詞，不斷使用規(guī)則規(guī)約，越來越完整的結(jié)構(gòu)。從葉子結(jié)點開始構(gòu)造句法樹。
分析算法的確定性
自頂向下，左部相同的重寫規(guī)則。
自底向下，出租汽車。
回溯慢，重復(fù)分析。
Earley算法
- Predictor()：作用于點號時非終結(jié)符號的狀態(tài)，產(chǎn)生新狀態(tài)
- Scanner()：點號后是中介狀態(tài)，掃描
- Completer()：一個子樹完成分析
廣義LR算法
- 標準算法
http://www.itdecent.cn/p/dd89025f95c1 - 廣義算法
遇到多個動作，單個分析進程分裂為多個進程，棧頂分裂為多個棧頂。
存儲結(jié)構(gòu)：子樹共享
局部歧義壓縮：把發(fā)生局部歧義子樹的根節(jié)點合并為一個（收集結(jié)點）。
壓縮共享森林
