不确定性越大 信息熵越大，信息的作用就是消除不确定性
信息熵
“信息墒” 由香农1948年提出，指一个事物包含的信息量。一元信息墒的计算方式如下$p_n$代表事物n的概率
$$
H(U) = -\sum_{k=1}^n {p_n*log p_n}
$$
变量p的不确定性越大，墒也就越大，信息量也就越大
条件熵
对两个随机事件相关性的度量
确定其中一个随机事件的条件下，对消除另一个随机事件不确定性所提供的信息量
相对熵（交叉熵）
衡量两个取值为正数的函数的相似性
描述两个随机分布的差异性
语言的构成
语法+语义 = 语言
自然语言的发展有两种不同的方式，基于规则和基于统计两种处理方式
前期： 基于规则
最开始基于规则的方法 分析语法树。但是随着句子长度的增加，使用语法树，面临着高额的计算要求。
但是基于语义，对于严重依赖上下文和基本常识的信息的多义性 无法还好的解决
目前：基于统计
以语言纠错为例子
我有一个梦想
梦想又一个我
上述两个句子我们是如何判断对错的呢，其实我们判断对错的方法就是 在日常生活中 第一个句子出现的次数更多。类推，我们只要统计出句子(S=w1,w2,w3)出现的概率，就可以判断句子的对错。但是古往今来有那么多的句子，我们根本没办法计算。如何精简：
第一步：记录词与句子的概率，这样我们就不用存储固定句子的概率。但依然庞大
$$
P(S) = P(w_1,w_2,w_3)=P(w_1)*P(w_2|w_1)*P(w_3|w_1,w_2)
$$
第二步：马尔可夫对上述描述方法进一步进行了简化，只需要记录当前词与其前一个词一起出现的概率 即可
$$
P(S) = P(w_1)*P(w_2|w_1)*P(w_3|w_2)*P(w_i|w_{i-1})
$$
$$
P（w_i|w_{i-1}）= \frac{P(w_i,P(w_{i-1}))}{P(w_{i-1})}
$$
只需要计算联合概率$P(w_{i-1},w_i)$和边缘概率$P(w_{i-1})$即可.
在统计模型中处理零概率问题
为什么会有零概率？
当一个词不在数据中出现 就会导致该词的概率为0
零概率的影响？
零概率并不是意味着就不会发生
零概率会导致模型的不平滑
处理零概率
古德图灵估计：从概率的总量中分配很小的一部分给概率为0的事件
公式为：
$$
d_r=(r+1)\cdot N_{r+1}/N_r
$$
r是出现的次数
$d_r$是出现了r次的词的修改后次数
$N_{r+1}$ 是出现r+1次的词的数量
$N_r$ 是出现r次的词的数量
马尔可夫链
为了解决随机过程的问题
马尔可夫假设：随机过程中各个状态$S_t$的概率分布只与它前一个状态$S_{t-1}$有关
马尔可夫链：
这样我们就可以根据状态序列来推测 状态转移概率
隐马尔可夫
为了解决无法观察到状态序列的时候 推测状态转移概率
独立输出假设：每个时刻t会输出一个随机符号 $O_t$， 仅和$S_t$相关
隐马尔可夫模型：
如何训练模型？
估计模型的参数
转移概率$P(S_t|S_{t-1})=P(S_t,S_{t-1})/P(S_{t-1})$
生成概率$P(O_t|S_t) = P(O_t,S_t)/P(S_t)$
如果有足够的标记数据，我们就可以计算出模型的参数。人工标记 成本过高
鲍姆-韦尔奇算法，通过观测大量的$O_t$，来推测转移概率和生成概率
鲍姆-韦尔奇算法步骤：
- 找到一组能够输出序列O的模型参数（随机数），模型记为$
M_{\theta0}$
💡 概率均匀分布时，可以产生任何输出
可以算出$
M_{\theta0}$产生序列O的概率（forward-backward算法），状态转移路径，状态输出现在将步骤2 的数据 当作 标注数据，重新计算新的模型参数，模型记为$
M_{\theta1}$不断迭代，直到模型不在有明显的提高。期望最大化（EX。维比特算法）。局部最优
搜索的本质
下载，索引，排序
爬虫
BFS (广度) 重要信息在首页，以及首页所链接的页面。 比如新闻网站
DFS (深度) 不同的页面，需要建立多次握手，耗费大量的资源。比如维基百科
PageRank算法
PageRank主要解决排序问题。
思想：投票机制，如果一个网页没其他很多网页链接，那么该网页的排名将会提高。为了更加准确，可以对来源网页进行权重的分配。
现实中一般还会将用户的点击行为添加进去计算排名，准确度更高
问题：
如何计算排名？
解：
假设每个网页的排名都是$1/N$,则所有网页的排名
$$
B_0=[\frac{1}{N},\frac{1}{N},...\frac{1}{N}]
$$
网页间的邻接矩阵为
$$
A=\begin{bmatrix}
a_{11} &\cdots & a_{1n} \
\vdots & \ddots & \vdots \
a_{m1} & \cdots & a_{mn}
\end{bmatrix}
$$
则，$B_i$为当前的网页的排名
$$
B_i=A \cdot B_{i-1}
$$
继续迭代，直到收敛，$B=B\times A$，一般来讲。只需要迭代10次即可
但是由于矩阵A非常的庞大，计算难度大，并且由于A 中很多数值都是0，所以可以采用稀疏矩阵进行平滑处理
$$
B_i=[\frac{\alpha}{N} \cdot I+(1-\alpha) \cdot B_{i-1}]
$$
其中$\alpha$为 一个较小的常数，N为网页的数量，$I$为单位矩阵
TF-IDF（相关性计算）
词频$TF=D_w/D$
逆文本频率$IDF=log(D/D_w)$ 这里使用log是指。一个特定条件下关键词的概率分布
D为总数，$D_w$为出现的次数
$$
TF-IDF=I(w)-TF(w)log \frac{M}{C(w)}
$$
I(w)为词的信息量，由大量文本训练得到
文本分类
首先TF-IDF 标记标记文本，后计算两个文本之间的余弦相似度。对于文本不同的部分，采用不同的权重，比如文本的标题和首尾段一般会比本体 提供更多的信息量
问题一：如何确定分类的特征文本？
人工标记，耗时耗力。采用自下而上不断合并的方法
计算所有文本两两之间的相似度，把相似度达到阈值的文档划分为一个小类
将分好后的小类各自合并，再在小类之间计算相似度，重复1 2 步骤
迭代，直到某一个类的数量很大的时候停止
问题二：文本多，计算量大，如果减少复杂度？
去除文中的虚词
只考虑非零元素
SVD算法 奇异值分解
将矩阵分解为,其中（文本分类中的意义）
A为完整的矩阵
X矩阵为 每行代表一个词，每列代表一个语义相近的词类，值为词为和词类的相关性（近义词分类）
B矩阵为 表示词的类和文章的类的关系
Y矩阵为 每行代表一个主题，每列代表一个文本，值为文本和主题的相关性（找到每列值最大的行，就是该文本的分类）
数学中的意义
X 为一个酉矩阵
Y 为酉矩阵的共轭矩阵
B 为对角矩阵
$$
A_{MN}=X_{MM} \times B_{MN} \times Y_{NN}
$$
地址的识别和导航
地址的识别一般采用 有限状态机
- 对于输入的错别字，采用基于概率的有限状态机
导航一般采用 动态规划
最大熵模型
在已知条件的概率模型集合中，找到熵最大的模型（即能包含所有事件的模型）
求解可以采用EM算法
贝叶斯网络
是一个概率图模型，且符合马尔可夫假设的有向图
条件随机场
是一个概率图模型，且符合马尔可夫假设的无向图
维特比算法
本质上也是一个动态规划的问题，通过局部最优，得到全局最优
凡是使用了隐含马尔可夫模型描述的问题 都可以用维特比算法解码
逻辑回归
一个事件出现的概率逐渐适应到一条逻辑曲线（S函数）上
$$
P=\frac{1}{\beta_0+\beta_1X_1+\beta2X_2}
$$
其中X为影响因素，$\beta$为参数值，可以通过IIS和GIS算法计算
期望最大化算法（EM）
将矩阵映射到N维空间
随机指定几个点设为中心点，计算所有点到中心点的距离，最近的划为一个类
对已划分的每个类，重新计算类的中心点，使中心点到类中的每个其他点距离最小（中心点移动）
重复2，3过程，直到 中心点的偏移很小（收敛）