Beauty of Methematics

语言和数学的产生都是为了同一个目的——记录和传播信息

隐含马尔科夫模型

发送者---编码S--->信息----解码O--->接受者
根据观测信号o推测信号源发送的信息s，只需要找出最有可能的信息
已知$o_1,o_2...$求条件概率$P(s_1,s_2,...|o_1,o_2...)达到最大值的s_1,s_2,...$
利用贝叶斯公式，上述公式等价为

$${P(o_1,o_2...|s_1,s_2...)P(s_1,s_2...)\over P(o_1,o_2...)}$$
一旦信息产生，它就不会变了，所以$P(o_1,o_2...)$是一个可以忽略的常数
所以上式变为
$${P(o_1,o_2...|s_1,s_2...)P(s_1,s_2...)}$$
用Hidden Markov Model估计
马尔科夫假设：随机过程中的每个状态$S_t$的概率分布，只与它的前一个状态$S_{t-1}$有关，即 $$P(S_t|s_1,s_2...s_{t-1}) = P(s_t|s_{t-1})$$
符合该假设的过程称为马尔科夫过程，也称马尔科夫链
隐含马尔科夫链是马尔科夫链的一个扩展：任意时刻的状态$s_t$是不可见的。
所以没法通过观察状态序列推测转移概率。
独立输出假设：隐含马尔科夫模型每个时刻输出一个仅与当前状态有关的符号$o_t$

基于马尔科夫假设和独立输出假设，有

$$P(s_1,s_2..,o_1,o_2...)=\prod_t{P(s_t|s_{t-1})P(o_t|s_t)}$$
于是解码问题可以用隐含马尔科夫模型解决
$${P(o_1,o_2...|s_1,s_2...)P(s_1,s_2...)}\ =\prod_t{P(o_t|s_t)}P(s_t|s_{t-1})$$

隐马尔科夫模型三个基本问题：
1. 给定一个模型，计算某个特定输出序列的概率；（forward-backward算法）
2. 给定一个模型盒某个输出序列，找到最有可能产生这个输出序列的状态序列；（维特比算法）
3. 给定足够量的数据，估计隐含马尔科夫模型的参数；

参数：
转移概率Transition Probability $P(s_t|s_{t-1}) = {P(s_{t-1},s_t) \over P(s_{t-1})}$
生成概率 Generation Probability $P(o_t|s_t) = { P(0_t,s_t) \over P(s_t)}$

用人工标注的数据估计状态输出概率——Supervised Training
$P(o_t|s_t) = {经过状态s_t输出o_t的次数 \over 经过状态s_t的次数 }$
但是成本高

无监督训练算法——鲍姆-韦尔奇算法 Baum-Welch Algorithm
1. 找到一组能够产生输出序列O的模型参数
2. 算出该模型产生输出出O的概率$P(O|M_{\theta0})$（问题1），找到产生O的所有可能的路径和路径的概率（问题2）——可以看成标记的训练数据。
3. 根据转移概率和生成概率的公式，算出一组新的模型参数$\theta_1$，可以证明

$$P(O|M_{\theta1}) > P(O|M_{\theta0})$$
4. 重复迭代下去，直到模型质量没有明显提升。

属于**期望最大化算法**Expectation Maximization Algorithm
上帝的算法：训练数据 + 最大化函数
E过程：计算各个观测数据输入到模型中的结果或期望
M过程：每一次迭代估计新的模型参数，使得期望值最大化
EM 过程保证算法收敛到局部最优点，如果目标函数是凸函数就可以找到全局最佳值。
隐含马尔科夫模型的训练方法Baum-Welch算法，最大熵模型的训练方法GIS方法，文本自收敛分类法

Baum-Welch算法中，E过程是根据当前模型计算状态转移次数和输出次数，M过程就是重新估计隐含马尔科夫模型的参数。

参考文献：
《数学之美》第五章，第27章
Baum,L.E;Eagon,J.A.(1967) "An inequality with application to statistical estimation for probability functions of Markov process and to a model for ecology"
Baum,L,E;Petrie,T. 1966 Statistical inference for probabilitysic functions of finite state markov chains
Baum,L,E.... A maximization technique occurring in the statistical analysis of probabilistic functions of markov chains

维特比算法

来自科学家和商人Andrew Viterbi
针对篱笆网络的有向图的最短路径问题的动态规划算法
可见的输入序列是$y_1,y_2... y_n$， 产生他们的隐含序列是$x_1,x_2... x_n$，状态的值可以变化，$x_{ij}$表示状态$x_i$的第j个可能的值。形成从$x_{1?}$到$x_{n?}$的有向图。从第一个状态到最后一个状态的任意一条路径都有可能产生观察到的输出序列。算法目的就是寻找概率最大的一条路径。

维特比算法的基础：
1. 最短路径的子路径一定是最短路径。
2. 从起点到终点的路径必然经过第i时刻的某个状态。
3. 假设从起点到状态$x_i$的各个节点的最短路径已经找到，那么从起点到状态$x_{i+1}$的最短路径，只需考虑$x_i$上的最短路径和从$x_i到x_{i+1}$的距离。

算法步骤：
1. 从起点S出发，到第一个状态的各个节点的距离就是最短距离
2. $d(S -> x_{(i+1)j}) = min_{\forall k}d(S->x_{ik}) + d(x_{ik}->x_{(i+1)j})$

每一步计算复杂度都与相邻状态的节点数乘积成正比。
整个维特比算法复杂度为$O(网格的长度\times 宽度)$

参考资料：
《数学之美》第二十六章

贝叶斯网络

马尔科夫链的扩展，满足马尔科夫假设，有向弧上有权重（Belief），也称为信念网络
可以使用贝叶斯公式算各种概率
训练贝叶斯网络的拓扑结构和参数，理论上是NP-Complete问题
训练拓扑结构的方法：贪婪法（沿箭头方向寻找有限步，会陷入局部最优解）、蒙特卡洛方法（用许多随机数在网络中试一试，计算量很大）、利用信息论（计算节点之间的互信息，保留互信息较大的节点之间的链接，再进行完备搜索）。
训练参数的方法：EM方法
结构训练和参数训练交替进行

参考资料：
《数学之美》第24章
http://ssli.ee.washington.edu/~biilmes/pgs/sort_data.html

自然语言处理

从规则到统计 词的多义性解读严重依赖上下文，所以基于规则的自然语言处理走不通
贾尼尼可的统计模型：一个句子是否合理，看看可能性大小
设$S$是由一连串特定顺序排列的词$w_1,w_2...w_n$组成的有意义的句子。那么$S$在文本中出现的可能性是

$$P(S)=P(w_1,w_2...w_n)=P(w_1)P(w_2|w_1)P(w_3|w_1,w_2)...P(w_n|w_1,w_2...w_{n-1})$$
使用马尔科夫假设： $$= P(w_1)P(w_2|w_1)P(w_3|w_2)...P(w_n|w_{n-1})$$
对应的模型叫二元模型Bigram Model
用大数定理和语料库进行估计： $$P(w_i|w_{i-1}) = {w_i w_{i-1}相邻出现次数 \over w_{i-1} 出现次数 }$$

统计语言模型的工程诀窍：
1. 高阶语言模型
N元模型：每个词只和前面N-1个词有关，N-1阶马尔科夫假设
N一般取3
马尔科夫假设的缺陷：上下文的关联跨度可能非常大
2. 零概率问题的平滑方法
某些词出现次数太少导致概率很极端
使用Good-Turing估计法：相信可靠数据，对不可靠数据打折扣并给予Unseen Events
从概率总量中分配一小部分给看不见事件
假设大小为N的语料库中出现r次的词有$N_r$个，$N = \sum_r^{\inf}rN_r$，出现r次的词在整个语料库的相对频度为r/N
Zipf定律：出现次数小的不同词语的数量多
当r很小时，$N_r$很接近$N$，应把r换成$d_r = (r+1)N_{r+1} \over N_r$
$\sum_rd_rN_r=N$
对出现次数低于某个阀值的词进行概率下调，把下调的概率总和分给未出现的词

卡茨退避法 二元模型

$$P(w_i|w_{i-1}) =\begin{cases} f(w_i|w_{i-1}) &(w_i, w_{i-1})\geq T \\\ f_{gt}(w_i|w_{i-1}) & (w_i, w_{i-1}) < T \\\ Q(w_{i-1})f(w_i) &otherwise \end{cases}$$
$f_{gt}(w_i|w_{i-1})$表示经过古德图灵估计后的相对频度
$Q(w_{i-1}) = {1-\sum_{w_i seen}P)w_i|w_{i-1}) \over \sum_{w_i unseen}f(w_i)}$保证等式$\sum_{w_i\in V}P(w_i|w_{i-1}) = 1$成立。
T一般取8-10.

Frederek Jelinek 约翰霍普金斯大学
教父Mitch Marcus 建立LDC语料库 Linguistic Data Consortium

参考资料：
《数学之美》第2，3，7，22章
Frederick Jelinek. Statistical methods for speech recognition. 1998 MIT press

最大熵模型

保留全部的不确定性，把风险降到最小
对一个随机事件的概率分布做出预测时，预测应当满足全部的呃已知条件，而对未知的情况不做任何主观假设。
形式简单（指数函数），实现复杂

$$P(w_3|w_1,w_2,S) = {{1\over {Z(w_1,w_2,S) }}e^{\lambda_1(w_1,w_2,w_3)+\lambda_2(S,w_3)}}$$
Z是归一化因子
训练方法：Generalized Iterative Scaling
1. 假设第零次迭代的初始模型为等概率均匀分布
2. 用第N次迭代的模型估算每种信息特征在训练数据中的分布，如果超过实际的就把相应模型参数变小；否则变大。
3. 重复上一步直到收敛。

然而该方法不稳定，有改进的迭代算法IIS
http://www.cs.jhu.edu/~junwu/publications.html

《数学之美》第20章

分类问题

Term frequency单文本词频： 某单词在某网页上出现的频率
停止词：对确定主题没帮助
inverse document frequency逆文本频率指数：以权重表示预测主题的能力 $log({全部网页数\over出现某个关键词的网页数})$
相关性计算就是词频的加权求和$\sum_iTF_i\times IDF_i$

TF-IDF的信息论推导：
$I(w) = -P(w)logP(w) = -{TF(w)\over N}log({TF(w)\over N}) = {TF(w)\over N}log({N\over TF(w)})$
忽略语料库大小常数N，${TF(w)}log({N\over TF(w)})$ D是文章篇数
假设每篇文献大小基本相同，均为$M = \frac N D = {\sum_wTF(w)\over D}$个词，而且一个关键词在文本中一旦出现，不论次数多少贡献等同。这样的词在一个文献中要么不出现，要么出现$c(w) = {TF(w)\over D(w)}$次
${TF(w)\over N}log({N\over TF(w)}) = {TF(w)\over N}log({MD \over c(w)D(w)}) = {TF(w)\over N}log(\frac D D(w) \frac M c(w))$
所以

$$TF-IDF(w) = TF(w)log(\frac D {D(w)}) = I(w) - TF(w)log(\frac M {c(w)})$$
一个词信息量越多，在命中的文献中出现次数越多，它的TF-IDF值越大。

高维空间向量夹角的余弦定理的分类
自底向上的合并方法：计算余弦相似性，超过阀值就合并，重复小类合成大类
大数据量时采取的优化：
1. 保存向量长度，不必重复计算
2. 向量内积只考虑非零元素
3. 删除虚词
根据关键词在文章出现的位置进行加权

**矩阵奇异值分解**Singular Value Decomposition
适合超大规模文本粗分类
超大矩阵每行对应一篇文章，每列对应一个词，元素是TF-IDF值
将它分解成三个小矩阵的积，大大减小储存量和计算量
$A_{M\times N} = X_{M\times n} \times B_{n\times n}\times Y_{n\times N}$
物理意义：矩阵X是对词进行分类的结果，每行对应一个词，每列对应一个语义相近的词类（语义类），元素表示某个词在某个语义类的重要性（相关性）
矩阵Y是对文本的分类结果，每列对应一个文本，每行对应一个主题，元素表示某个文本在某个主题的相关性。
中间的矩阵B表示词类与文章的类的相关性。

分解方法：
X是酋矩阵Unitary Matrix，Y是某个酋矩阵的共轭矩阵。酋矩阵是与自己的共轭矩阵的转置相乘等于单位阵的方阵。由于B矩阵上很多数很小可以忽略，所以超大矩阵变成三个小矩阵。
1. 矩阵A变换成双对角矩阵，利用稀疏性缩短计算时间
2. 奇异值分解

《数学之美》第11，14，15章
Tomas M Cover 信息论基础，清华大学出版社

PageRank算法

民主表决
如果一个网页被很多其他网页链接，那么它的排名高；排名高的网站的链接的权重大。
把问题转化为二维矩阵相乘的迭代方法，先假设各个网页的排名相同，根据初始值开始迭代，一定会收敛到真实排名。
稀疏矩阵的化简技巧 + MapReduce并行计算工具

设向量$B = (b_1,b_2...b_N)^T$是N个网页的排名。矩阵A储存从一个网页指向另一个网页的连接数。
令$B_0 = (\frac1 N, \frac1 N... \frac1 N)$，根据$B_{i+1} = A\times B_{i}$迭代直到收敛。
对零概率进行平滑处理$B_i = [\frac \alpha N \times I + (1-\alpha)A]\times B_{i-1}$
N是互联网网页数，I是单位矩阵。

《数学之美》第10章
http://infolab.stanford.edu/~backrub/google.html

有限状态机

有限状态机是一个五元组$(\sum, S, s_0,\sigma, f)$，其中
$\sum$是输入符号的集合
S是非空有限状态的集合
$s_0$是S中的起始状态
$\sigma$是从$S\times\sum$到$S$的映射函数
f是终止状态

加权有限状态传感器Weighted Finite State Transducer
每个状态由输入和输出符号定义，输入输出的可能性是权重

《数学之美》第12章

公开密钥

原理：
1. 找两个很大的质数P和Q，计算N= PQ，M= (P-1)(Q-1)
2. 找一个和M互质的整数E
3. 找一个整数D，使得EDmodM = 1
E是公钥，D是私钥，N公开
对明码X加密得到密码Y
$X^EmodN = Y$
根据费马小定理，从密码得到明码必须知道D
$Y^DmodN = X$