回顾了概率论、信息论、支持向量机等简单知识点。
概率论
1.概率
- 非负性：$P(A)\geqslant0$
- 规范性：$P(\Omega)=1$
- 可列可加性：$P(\bigcup_{i=0}^{\infty}A_i)=\sum_{i=0}^{\infty}P(A_i)$
2.最大似然估计
如果${s_1,s_2,…,s_n}$是一个试验的样本空间，在相同的情况下重复实验N次，观察到样本$s_k(1\leqslant{k}\leqslant{n})$的次数为$n_N(s_k)$，那么$s_k$在这$N$次试验中的相对频率为：
\[\begin{equation} q_N(s_k)=\frac{n_N(s_k)}{N} \end{equation}\]由于$\sum_{k=1}^{n}n_N(s_k)=N$，因此，$\sum_{k=1}^{n}q_N(s_k)=1$。 当$N$越来越大时，相对频率作为概率的估计值。这种估计概率值的方法称为最大似然估计(maximum likelihood estimation)。
3.条件概率(conditional probability)
4.贝叶斯法则
贝叶斯公式：
全概率公式：
5.随机变量
随机变量(random variable)就是实验结果的函数。
设X为一离散随机变量，其全部可能的值为${a_1, a_2, …}$。那么：
\[\begin{equation} p_i=P(X=a_i), i=1, 2, ... \end{equation}\]称为$X$的概率函数。显然，${p_i}\geqslant{0}$，$\sum_{i=1}p_i=1$。有时式(5)也成为随机变量X的概率分布，此时，函数
\[\begin{equation} P({X}\leqslant{x})=F(x), -\infty<x<\infty \end{equation}\]称为$X$的分布函数。
6.二项式分布
假设某一事件A在一次试验中发生的概率为$p$，现把试验独立地重复进行n次。如果用变量X来表示A在这n次试验中发生的次数，那么，X的取值可能为${0,1,…,n}$。则：
\[\begin{equation} p_i=\tbinom{n}{i}p^i(1-p)^{n-i}, i=0,1,\dots,n \end{equation}\]$X$所遵从的这种概率分布称为二项式分布(binomial distribution)，并记为$B(n,p)$。如果随机变量$X$服从某种特定的分布$F$时，我们常用$X~F$表示。如果$X$服从二项式分布，可记为$X~B(n,p)$。
7.联合概率分布和条件概率分布
假设$(X_1, X_2)$为一个二维的离散型随机向量，$X_1$全部可能的取值为$a_1, a_2, \dots; X_2$全部可能的取值为$b_1, b_2, \dots$。那么，$(X_1, X_2)$的联合分布(joint distribution)为：
\[\begin{equation} p_{ij}=P(X_1=a_i,X_2=b_j), i=1,2,\dots; j=1,2,\dots \end{equation}\]一个随机变量或向量X的条件概率分布就是在某种给定的条件之下X的概率分布。考虑$X_1$在给定$X_2=b_j$条件下的概率分布，实际上就是求条件概率$P({X_1=a_i}\mid{X_2=b_j})$。根据条件概率的定义可得：
\[\begin{equation} P({X_1=a_1}\mid{X_2=b_j})=\frac{P({X_1=a_1},{X_2=b_j})}{P(X_2=b_j)}=\frac{p_{ij}}{P(X_2=b_j)} \end{equation}\]由于$P(X_2=b_j)=\sum_{k}p_{kj}$，故有：
\[\begin{equation} P({X_1=a_i}\mid{X_2=b_j})=\frac{p_{ij}}{\sum_{k}p_{ik}}, j=1,2,\dots \end{equation}\]类似地，
\[\begin{equation} P({X_2=b_j}\mid{X_1=a_i})=\frac{p_{ij}}{\sum_{k}{}p_{ik}}, j=1,2,\dots \end{equation}\]8.贝叶斯决策理论
贝叶斯决策理论(Bayesian decision theory)是统计方法处理模式分类问题的基本理论之一。假设研究的分类问题有c个类别，各类别的状态用$\omega_i$表示，$i=1,2,\dots,c$；对应于各个类别$\omega_i$出现的先验概率为$P(\omega_i)$；在特征空间已经观察到某一向量x，$x=[x_1,x_2,\dots,x_d]^T$是d维特征空间上的某一点，且条件概率密度函数$p({x}\mid{\omega_i})$是已知的。那么，利用贝叶斯公式我们可以得到后验概率$P({\omega_i}\mid{x})$如下：
\[\begin{equation} P({\omega_i}\mid{x})=\frac{p({x}\mid{\omega_i})P(\omega_i)}{\sum_{j=1}^{c}p({x}\mid{\omega_j})P(\omega_j)} \end{equation}\]基于最小错误率的贝叶斯决策规则为：
(1) 如果$P({\omega_i}\mid{x})=max_{j=1,2,\dots,c}P({\omega_j}\mid{x})$，那么，${x}\in{\omega_i}$
或者说，
(2) 如果$p({x}\mid{\omega_i})P(\omega_i)=max_{j=1,2,\dots,c}p({x}\mid{\omega_j})P(\omega_j)$，则${x}\in{\omega_i}$
如果类别只有两类时，即$c=2$，则有：
(3) 如果$l(x)=\frac{p({x}\mid{\omega_1})}{p({x}\mid{\omega_2})}>\frac{P(\omega_2)}{\omega_1}$，则${x}\in{\omega_1}$，否则${x}\in{\omega_2}$
其中，$l(x)$为似然比(likelihood ratio)，而$\frac{P(\omega_2)}{P(\omega_1)}$称为似然比阈值(threshold)。
9.期望和方差
期望值(expectation)是指随机变量所取值的概率平均。假设$X$为一随机变量，其概率分布为$P(X=x_k)=p_k, k=1,2,\dots$，若级数$\sum_{k=1}^{\infty}{x_k}{p_k}$绝对收敛，那么，随机变量$X$的数学期望或概率平均值为:
\[\begin{equation} E(X)=\sum_{k=1}^{\infty}{x_k}{p_k} \end{equation}\]一个随机变量的方差(variance)描述的是该随机变量的值偏离其期望值的程度。如果$X$为一随机变量，那么，其方差$var(X)$为：
\[\begin{equation} var(X)=E((X-E(X))^2)=E(X^2)-E^2(X) \end{equation}\]平方根$\sqrt{var(X)}$称为$X$的标准差。
信息论
1.熵
如果$X$是一个离散型随机变量，取值空间为$\mathbb{R}$，其概率分布为$p(x)=P(X=x),{x}\in{\mathbb{R}}$。那么，$X$的熵$H(X)$定义为：
\[\begin{equation} H(X)=-\sum_{ {x}\in{\mathbb{R}} }{p(x)log_{2}{p(x)}} \end{equation}\]其中，约定$0log0=0$。$H(X)$可以写为$H(p)$。该公式定义的熵的单位为二进制位（比特）。
熵又称为自信息(self-information)，可以视为描述一个随机变量的不确定性的数量。它表示信源$X$每发一个符号(不论发什么符号)所提供的平均信息量。一个随机变量的熵越大，它的不确定性越大，那么，正确估计其值的可能性就越小。月不确定的随机变量越需要打的信息量用以确定其值。
在自然语言处理中，通常的做法是，根据已知样本设计特征函数，假设存在$k$个特征函数$f_i(i=1,2,\dots,k)$，它们都在建模过程中对输出有影响，那么，所建立的模型应满足所有这些特征的约束，即所建立的模型$p$应该属于这$k$个特征函数约束下所产生的所有模型的集合$C$。使熵$H(p)$值最大的模型用来推断某种语言现象存在的可能性，或者作为进行某种处理操作的可靠性依据，即：
\[\begin{equation} \hat{p}=argmax_{p\in{C}}H(p) \end{equation}\]2.联合熵和条件熵
如果$X,Y$是一对离散型随机变量$X,Y~p(x,y)$，$X,Y$的联合熵(joint entropy)$H(X,Y)$定义为：
\[\begin{equation} H(X,Y)=-\sum_{x\in{X}}\sum_{y\in{Y}}logp(x,y) \end{equation}\]联合熵实际上就是描述一对随机变量平均所需要的信息量。
给定随机变量$X$的情况下，随机变量$Y$的条件熵(conditional entropy)定义如下：
\[\begin{equation} H(Y\mid{X})=\sum_{x\in{X}}p(x)[-\sum_{y\in{Y}}p(y\mid{x})logp(y\mid{x})]=-\sum_{x\in{X}}\sum_{y\in{Y}}p(x,y)logp(y\mid{x}) \end{equation}\]将式(17)中的联合概率$logp(x,y)$展开，可得：
\[\begin{equation} H(X,Y)=-\sum_{x\in{X}}\sum_{y\in{Y}}p(x,y)log[p(x)p(y\mid{x})]\\ =-\sum_{x\in{X}}\sum_{y\in{Y}}p(x,y)[logp(x)+logp(y\mid{x})]\\ =-\sum_{x\in{X}}\sum_{y\in{Y}}p(x,y)logp(x)-\sum_{x\in{X}}\sum_{y\in{Y}}p(x,y)logp(y\mid{x})\\ =-\sum_{x\in{X}}p(x)logp(x)-\sum_{x\in{X}}\sum_{y\in{Y}}p(x,y)logp(y\mid{x})\\ =H(X)+H(Y\mid{X}) \end{equation}\]我们称上式为熵的连锁规则(chain rule for entropy)。推广到一般情况，有：
\[\begin{equation} H(X_1,X_2,\dots,X_n)=H(X_1)+H(X_2\mid{X_1})+\dots+H(X_n\mid{X_1,\dots,X_{n-1}}) \end{equation}\]3.互信息
根据熵的连锁规则，有：
\[\begin{equation} H(X,Y)=H(X)+H(Y\mid{X})=H(Y)+H(X\mid{Y}) \end{equation}\]因此，
\[\begin{equation} H(X)-H(X\mid{Y})=H(Y)-H(Y\mid{X}) \end{equation}\]这个差叫做$X$和$Y$的互信息(mutual information, MI)，记作$I(X;Y)$。或者定义为：如果$(X,Y)~p(x,y)$，则$X,Y$之间的互信息$I(X;Y)=H(X)-H(X\mid{Y})$。
$I(X;Y)$反映的是在知道了$Y$的值以后$X$的不确定性的减少量。可以理解为$Y$的值透露了多少关于$X$的信息量。
如果将定义中的$H(X)$和$H(X\mid{Y})$展开，可得
\[\begin{equation} I(X;Y)=H(X)-H(X\mid{Y})\\ =H(X)+H(Y)-H(X,Y)\\ =\sum_{x}p(x)log\frac{1}{p(x)}+\sum_{y}p(y)log\frac{1}{p(y)}+\sum_{x,y}p(x,y)logp(x,y)\\ =\sum_{x,y}p(x,y)log\frac{p(x,y)}{p(x)p(y)} \end{equation}\]由于$H(X\mid{X})=0$，因此：
\[\begin{equation} H(X)=H(X)-H(X\mid{X})=I(X;X) \end{equation}\]这一方面说明了为什么熵又称为自信息，另一方面说明了两个完全相互依赖的变量之间的互信息并不是一个常量，而是取决于它们的熵。
实际上，互信息体现了两变量之间的依赖程度：如果$I(X;Y)\gg{0}$，表明$X$和$Y$是高度相关的；如果$I(X;Y)=0$，表明$X$和$Y$是相互独立的；如果$I(X;Y)\ll{0}$，表明$Y$的出现不但未使$X$的不确定性减小，反而增大了$X$的不确定性，常是不利的。平均互信息量是非负的。
同样，我们可以推导出条件互信息和互信息的连锁规则：
\[\begin{equation} I(X;Y\mid{Z})=I((X;Y)\mid{Z})=H(X\mid{Z})-H(X\mid{Y},Z)\\ I(X_{1n};Y)=I(X_1,Y)+\dots+I(X_n;Y\mid{X_1,\dots,X_{n-1}}) \end{equation}\] \[\begin{equation} =\sum_{i=1}^{n}I(X_i;Y\mid{X_1,\dots,X_{i-1}}) \end{equation}\]互信息在词汇聚类(word clustering)、汉语自动分词、词义消歧等问题的研究中具有重要用途。
4.相对熵
相对熵(relative entropy)又称Kullback-Leibler差异(Kullback-Leibler divergence)或简称KL距离，是衡量相同事件空间里两个概率分布相对差距的测度。两个概率分布$p(x)$和$q(x)$的相对熵定义为：
\[\begin{equation} D(p\Vert{q})=\sum_{x\in{X}}p(x)log\frac{p(x)}{q(x)} \end{equation}\]该定义中约定$0log(0/q)=0,plog(p/0)=\infty$。表示成期望值为:
\[\begin{equation} D(p\Vert{q})=E_{p}(log\frac{p(X)}{q(X)}) \end{equation}\]显然，当两个随机分布完全相同时，即$p=q$，其相对熵为0。当两个随机分布的差别增加时，其相对熵期望值也增大。
互信息实际上就是衡量一个联合分布与独立性差距多大的测度：
\[\begin{equation} I(X;Y)=D(p(x,y)\Vert{p(x)p(y)}) \end{equation}\]证明：
\(I(X;Y)=H(X)-H(X\mid{Y})\)
\(=-\sum_{x\in{X}}p(x)logp(x)+\sum_{x\in{X}}\sum_{y\in{Y}}p(x,y)logp(x\mid{y})\)
\(=\sum_{x\in{X}}\sum_{y\in{Y}}p(x,y)log\frac{p(x\mid{y})}{p(x)}\)
\(=\sum_{x\in{X}}\sum_{y\in{Y}}p(x,y)log\frac{p(x,y)}{p(x)p(y)}\)
\(=D(p(x,y)\Vert{p(x)p(y)})\)
同样，我们也可以推导出条件相对熵和相对熵的连锁规则：
\[\begin{equation} D(p(x\mid{y})\Vert{q(y\mid{x})})=\sum_{x}p(x)\sum_{x}p(y\mid{x})log\frac{p(y\mid{x})}{q(y\mid{x})} \end{equation}\] \[\begin{equation} D(p(x,y)\Vert{q(x,y)})=D(p(x)\Vert{q(x)})+D(p(y\mid{x})\Vert{q(y\mid{x})}) \end{equation}\]5.交叉熵
熵是一个不确定性的测度，交叉熵的概念就是用来衡量估计模型与真实概率分布之间差异情况的。
如果一个随机变量$X~p(x),q(x)$为用于近似$p(x)$的概率分布，那么，随机变量$X$和模型$q$之间的交叉熵(cross entropy)定义为：
\[\begin{equation} H(X,q)=H(X)+D(p\Vert{q}) =-sum_{x}p(x)logq(x) =E_p(log\frac{1}{q(x)}) \end{equation}\]由此，可以定义语言$L=(X_i)~p(x)$与其模型$q$的交叉熵为：
\[\begin{equation} H(L,q)=-lim_{n\to{\infty}}\frac{1}{n}\sum_{x_{1}^{n}}logq(x_{1}^{n}) \end{equation}\]其中，$x_{1}^{n}=x_1,x_2,\dots,x_n$为$L$的语句，$p(x_1^n)$为$L$中$x_1^n$的概率，$q(x_1^n)$为模型$q$对$x_1^n$的概率估计。至此，由于我们不知道真实概率$p(x_1^n)$，因此无法计算这个语言的交叉熵。我们可以假设这种语言是“理想”的，即$n$趋于无穷大时，其全部“单词”的概率和为1。也就是说，根据信息论的定理：假设语言$L$是稳态(stationary)遍历的(ergodic)随机过程，$L$与其模型$q$的交叉熵计算公式就变为：
\[\begin{equation} H(L,q)=-lim_{n\to{\infty}}\frac{1}{n}logq(x_1^n) \end{equation}\]由此，可以根据模型$q$和一个含有大量数据的$L$的样本来计算交叉熵。在设计模型$q$时，目的是使交叉熵最小，从而使模型最接近真实的概率分布$p(x)$。一般的，在$n$足够大时，我们近似的采用如下计算方法：
\[\begin{equation} H(L,q)\thickapprox{-\frac{1}{n}logq(x_1^n)} \end{equation}\]交叉熵与模型在测试语料中分配给每个单词的平均概率所表达的含义正好相反，模型的交叉熵越小，模型的表现越好。
6.困惑度
在设计语言模型时，我们通常用困惑度(perplexity)来替代交叉熵衡量语言模型的好坏。给定语言$L$的样本$l_1^n=l_1\dots{l_n}$，$L$的困惑度$PP_q$定义为：
\[\begin{equation} PP_q=2^{H(L,q)}\thickapprox{2^{-\frac{1}{n}logq(l_1^n)}=[q(l_1^n)]^{-\frac{1}{n}}} \end{equation}\]同样的，语言模型设计的任务就是寻找困惑度最小的模型，使其最接近真实语言的情况。在自然语言处理中，我们所说的语言模型的困惑度通常是指语言模型对于测试数据的困惑度。一般情况下将所有数据分成两部分，一部分作为训练数据，用于估计模型的参数；另一部分作为测试数据，用于评估语言模型的质量。
7.噪声信道模型
信息熵可以定量的估计信源每发送一个符号所提供的平均信息量，但对于通信系统来说，最根本的问题还在于如何定量地估算从信道输出中获取多少信息量。
噪声信道模型(noisy channel model)，其目标就是优化噪声信道中信号传输的吞吐量和准确率，其基本加黑色是一个信道的输出以一定的概率依赖于输入。
信号传输过程中都要进行双重性处理：一方面要对编码进行压缩，尽量消除所有的冗余；另一方面又要通过增加一定的可控冗余以保障输入信号经过噪声信道传输以后可以很好地恢复原状。这样，信息编码时要尽量少占用空间，但又必须保持足够的冗余以便能够检测和校验传输造成的错误。信道输出信号解码后应该尽量恢复到原始输入状态。这个过程如下图所示：
一个二进制对称信道(binary symmetric channel,BSC)的输入符号集为$X=\lbrace{0,1}\rbrace$，输出符号集为$Y=\lbrace{0,1}\rbrace$。在传输过程中如果输入符号被误传的概率为$p$，那么，被传输的概率就是$1-p$。这个过程可以用一个对称图形表示，如下图所示：
信息论中另一个重要的概念是信道容量(capaity)，其基本思想是想用降低传输速率来换取高保真通信的可能性。其定义可以根据互信息给出：
\[\begin{equation} C=max_{p(X)}I(X;Y) \end{equation}\]根据这个定义，如果能够设计一个输入编码$X$，其概率分布为$p(X)$，使其输入与输出之间的互信息达到最大值，那么，我们的设计就达到了信道的最大传输容量。上式所表示的信道容量$C$就是平均互信息量的最大值。
在自然语言处理中不需要进行编码，一种自然语言的句子可以视为已编码的符号序列，但需要进行解码，使观察到的输出序列更接近于输入。因此我们可以用下图来表示这个噪声信道模型：
模拟信道模型，在自然语言处理中，很多问题都可以归结为在给定输出$O$(可能含有误传信息)的情况下，如何从所有可能的输入$I$中求解最有可能的那个，即求出使$p(I\mid{O})$最大的$I$作为输入$\hat{I}$。根据贝叶斯公式有：
\[\begin{equation} \hat{I}=argmax_{I}p(I\mid{O})=argmax_{I}\frac{p(I)p(O\mid{I})}{p(O)}\\ =argmax_{I}p(I)p(O\mid{I}) \end{equation}\]上式中有两个概率分布需要考虑，一个是$p(I)$，称为语言模型(language model)，是指在输入语言中“词”序列的概率分布；另一个是$p(O\mid{I})$，称为信道概率(channel probability)。
噪声信道模型在自然语言模型处理中有着非常广泛的用途，除了机器翻译以外，还用于词性标注、语音识别、文字识别等很多问题的研究。