Topics
• NLP与随机过程的关系(背景)
• 最大熵模型的介绍(熵的定义、最大熵
模型)
• 最大熵模型的解决(非线性规划、对偶
问题、最大似然率)
• 特征选取问题
• 应用实例
• 总结与启发
NLP与随机过程
NLP:已知一段文字:x1x2…xn(n个词)
标注词性y1y2…yn
标注过程:
已知:x1x2…xn
已知:x1x2…xn y1
已知:x1x2…xn y1 y2
已知:x1x2…xn y1 y2 y3
…
求:y1
求:y2
求:y3
求:y4
NLP与随机过程
yi可能有多种取值,yi被标注为a的概率有多少?
随机过程:一个随机变量的序列。
x1x2…xn
x1x2…xn y1
x1x2…xn y1 y2
x1x2…xn y1 y2 y3
…
p(y1=a|x1x2…xn)
p(y2=a|x1x2…xn y1)
p(y3=a|x1x2…xn y1 y2)
p(y4=a|x1x2…xn y1 y2 y3)
NLP与随机过程
问题:
• p(yi=a|x1x2…xn y1y2…yi-1)怎么求?
• yi与x1x2…xn y1y2…yi-1的关系?
x1x2…xn
x1x2…xn y1
x1x2…xn y1 y2
x1x2…xn y1 y2 y3
…
p(y1=a|x1x2…xn)
p(y2=a|x1x2…xn y1)
p(y3=a|x1x2…xn y1 y2)
p(y4=a|x1x2…xn y1 y2 y3)
NLP与随机过程
问题:
• p(yi=a|x1x2…xn y1y2…yi-1)怎么求?
• yi与x1x2…xn y1y2…yi-1的关系?
一个直观的解决:
(
yp
i
..
yyxxa
..
|
1
1
n
)
n
(
yp
..
n
i
(
..
yyxxp
..
,
yyxxa
..
)
1
1
1
)
n
n
1
n
问题again!
• (x1x2…xn y1y2…yi-1)?
What’s Entropy?
An Example:
• 假设有5个硬币:1,2,3,4,5,其中一个是假的,比其
他的硬币轻。有一个天平,天平每次能比较两堆硬币,
得出的结果可能是以下三种之一:
• 左边比右边轻
• 右边比左边轻
• 两边同样重
问:至少要使用天平多少次才能保证找到假硬币?
(某年小学生数学竞赛题目:P)
称硬币(cont.)
• 答案:2次
• 一种方法:
• Why最少2次?
1+2 ? 3+4
<
>
=
5
1 ? 2
>
2
<
1
3 ? 4
>
4
<
3