雅格布森通信模型:
通信六要素
发送者(信息源)
信道
接收者
信息
上下文
编码
HMM: 隐马尔可夫模型
s 是可见的 - 信源
o 是不可见的(输出) - 信宿
通信就是要根据观测到的 o 恢复出 s
对于翻译问题, 汉译英: 英语是 s, 汉语是 o, 根据 s 推断 o
TF-IDF
TF: 词频
IDF: 逆文本频率指数
IDF 就是关键词的权重, 越能表示一个文档主题的词, 其权重越高
最大熵原则
以条件随机场为例, 希望找到一个符合所有边缘分布的概率分布函数.
根据最大熵原则: 希望找到一个符合所有边缘分布并使熵达到最大的模型, 数学上可以证明, 这个模型就是指数函数.
详见: https://www.cnblogs.com/sddai/p/11346872.html
最大熵模型, 逻辑回归模型都是指数模型, 训练方法类似: EM 算法(通用迭代算法 GIS, 改进的迭代算法 IIS)
最大熵模型的数学推导(参考[2])
对于给定的训练数据集 T={(x1,y1),(x2,y2),(x3,y3)...(xn,yn)}以及特征函数 fi(x,y),i=1,2,3...n, 最大熵模型的学习等价于约束的最优化问题:
引入朗格朗日算子 W, 定义拉格朗日函数 L(P,w)
最优化的原始问题:
对偶问题是:
由于 L(P,W)是 P 的凸函数, 原始问题的解与对偶问题的解是等价的. 这里通过求对偶问题的解来求原始问题的解.
第一步求解内部极小化问题, 记为:
通过微分求导, 得出 P 的解是:
第二步求外部的极大化问题:
最后的解记为:
第三步可以证明对偶函数的极大化等价于第一步求解出的 P 的极大似然估计, 所以将最大熵模型写成更一般的形式.
From <https://www.cnblogs.com/sddai/p/11346872.html>
对 EM 算法的理解
类比 K-Means 算法:
条件随机场
HMM 和 CRF 的区别
上述模型参数众多, 因此只能找出其中一些边缘分布, 例如 P(x_1), P(x_2, y_3)等, 再根据最大熵原则找到一个满足所有边缘分布并且使熵最大的模型.
这个模型就是指数函数
计算复杂度
P 问题:
非多项式问题:
在非多项式问题中, 有一类称之为非确定的多项式问题(NP 问题)
P 不等于 NP
如果一个问题, 能在多项式复杂度的时间内证实一个答案正确与否, 则称为 NP 问题(无论当前是否有多项式复杂度算法)
NPC:NP-complete 问题, 所有 NP 问题都可以在多项式时间内规约到 NPC 问题, 如果 NPC 问题找到了多项式算法, 则 NP=P
计算复杂度至少是 NPC 甚至是更大的问题, 称之为 NP-Hard 问题
篱笆网络 (lattice) 和维特比算法
SVD 的物理含义
矩阵 A: 用来表示文章和词的关联性, A 的一行对应一篇文章, A 的一列对应一个词
A 中元素为去加权词频(例如 TF-IDF)
2019 年 8 月 15 日 夜
于南湖畔
来源: http://www.bubuko.com/infodetail-3157283.html