条件最大熵（20191029）
有向图模型
- 有向图模型的分解
一阶马尔科夫模型也是有向图模型，是链式的
HMM也是，
无向图模型
团（全连通子图）、最大团（不被其他团所包含的团）
- 势函数：把团映射为正实数，团中不同的取值组合映射到不同的正实数上。
- 以团为单位，把联合概率分解为势函数的乘积，需要归一化
- 为保证为正数，可以利用指数势函数
有向图vs无向图
- 同：把联合分布分解为多个因子
- 不同：
有向图：因子是概率，不需要归一；不需要归一，训练相对高效
无向图：因子是势函数，需要归一；灵活，但全局归一代价高
条件随机场模型（无向图）
略
20191119 句法分析
NP，名词短语；VP，动词性短语
CFG（上下文无关句法分信息）
上下文无关文法的用法
- 生成装置。生成语言中的句子 book that flight，不断替换NP为noun等等。枚举，穷举，派生出来。
- 识别装置。判断句子合法
- 分析装置。判断合法+产生句法结构
句法树（parse）
主要问题：歧义
如何消除歧义？（句法分析）
- 人工语言的语法分析
没有歧义，打多基于上下文无关的算法（LL分析法，LR分析法）
由于歧义，对于自然语言，不能直接用，句法分析。 - 句法分析算法
大多基于上下文无关算法
（1）自顶向下的句法分析“周瑜打败了曹操”
从开始符号S出发，不断使用不同规则，如果能推到出来，是一个句子。（正向）
（2）自底向上，逆向规约
先分词，不断使用规则规约，越来越完整的结构。从叶子结点开始构造句法树。
分析算法的确定性
自顶向下，左部相同的重写规则。
自底向下，出租汽车。
回溯慢，重复分析。
Earley算法
- Predictor()：作用于点号时非终结符号的状态，产生新状态
- Scanner()：点号后是中介状态，扫描
- Completer()：一个子树完成分析
广义LR算法
- 标准算法
https://www.jianshu.com/p/dd89025f95c1 - 广义算法
遇到多个动作，单个分析进程分裂为多个进程，栈顶分裂为多个栈顶。
存储结构：子树共享
局部歧义压缩：把发生局部歧义子树的根节点合并为一个（收集结点）。
压缩共享森林
