第17章 自然语言处理
早期依赖语言学家的文法，后来依赖统计模型，基础是语料库语言模型。n元语料库，一般是三元模型，计算当前词与前面两个词同时出现的及自己单独出现的概率。这个概率可以统计很多文章，通过tf-idf加权矩阵来计算每个词的加权概率。
为了防止出现零概率，可以用古德-图灵估计里为零概率的词赋很小的概率，这个概率来自低词频贡献，词频越低，对其他零词频词的概率贡献越多。也就是设定一个词频阈值，阈值之上不对概率扣减，阈值之下概率进行古德-图灵估计，零概率的均分前面打折省下来的概率。另一个思路是低元模型对高元模型的线性插值。
分词问题，可以用语料库计算出现某个序列的概率，概率最大的分词方法被选用。分词可以采用层级模型，颗粒度不同的分词存在各自最适用的应用场景。
隐马尔可夫模型（HMM），这是一个信号模型，给定一组状态序列，寻找对应的信号序列，例如翻译与语音识别。本质上是寻找产生最大概率的那一组信号，通过贝叶斯定理可以转换为寻找并最大化某信号下状态的条件概率与该信号合理出现概率的乘积。在HMM下，通过马尔可夫假设，我们只考虑每个信号前面的一个信号之间条件概率（也就是前面的语言模型）与当前信号状态条件概率乘积的连乘，然后用维特比算法（线性规划）找出最大值，也就是给定模型与输出信号，计算最可能出现的状态（语音识别问题）。同时，HMM可以解决给定参数后，计算某个输出序列的概率（输入法）。但HMM本身也需要进行参数估计，可以采用标注数据但成本高，也可以用EM的方法，先假设一个随机模型可以产生输出序列，前后转移概率随机，两两含义对应概率也随机，然后用数据输入模型计算所有路径概率，此时相当于标注了数据，用其计算最大似然度下的最优参数，然后再输入新参数，不断迭代直到新参数比旧参数对数据没有更高的最大似然输出概率
信息量比特数跟发生可能性的对数有关，信息量与发生概率的乘积的累积总和就是信息熵，信息熵越大，均质性越强，不确定性越高；反之，高概率信息的引入会降低不确定性，系统内额外相关的信息总会不增加不确定度（条件信息熵），由额外信息减少的信息熵是互信息，取值01之间，越大额外信息与原始信息越相关取值越高，可用来消除语言二意性。相对熵用来衡量两个文本信息熵的大小。自然语言处理考虑上下文是考虑了条件熵，考虑语境就是考虑了相对熵，语言复杂度就是给定上下文每个位置可选择的单词数量，语料库引入可提高模型准确度。
布尔逻辑可用来进行索引表的检索，图论与深度／广度优先算法，爬虫找到页面，提取链接，构建哈希表存储，可采取异步分批存储与定向发送（网页聚类），pagerank 通过计算网页链入链出的数量与质量迭代来确定网页的重要程度，在进行关键词检索时，首先依赖词频，但要去掉高频词，同时如果某个词词频高但出现在独立网页中比较多时（类高频词）可以用逆词频，也就是网页总数除以出现该词的页面数的对数来对词频加权，如果在独立网页中出现概率高，信息量大，其总排序要靠前，这样可以筛选出跟查询词比较接近的语境（TF-IDF）
语音识别需要用到动态规划与有限状态机来降低计算／搜索成本
高维相似度可以用余弦定理来计算，首先得到每个样本的特征向量，然后计算相似度，高的归为一类，然后同一类中计算余弦相似度不断归类。不同的相似度可以用不同的权重来表示
同时，也可以用矩阵计算来进行分类，对矩阵进行奇异值分解，左边酉矩阵可以提取特征跟主题相关性，右边则可提取主题与样本相关性，可快速进行较粗的分类，而余弦定理就需要不断迭代。
相似哈希表可用来快速比较相似度
费马小定理可用来进行基于质数的加密
最大熵模型可用来计算存在影响因素下（或者说特定语境下）的出现概率问题，这是一个指数模型，需要训练的参数非常多，但也可以用em方法求解训练。
输入法可通过动态规划方法求解备选词，同时可以用余弦定理来构建个人语言模型与整体语言模型的插值模型，这是一个最大熵与通用的折衷方案，其实也是最优的
布隆过滤器，对字符随机转换为8个数字，然后构建一个二进制长向量，将8个数字对应的位置设为1，如果某个地址出现同样位置为1，那么过滤掉，用较小的空间对比较大的数目，比计算哈希值省空间，可用来快速过滤垃圾邮件
贝叶斯网络，条件概率的网络，训练出的模型可以预测其中变量间关系，然后可以反过来调整模型结构，例如我们可以知道文本对应的主题，也可以知道主题对应的文本，这样在主题跟文本还有关键词间可以构建一个有向网络来探索其之间的相互关系
如果关系是无向的贝叶斯网络那就是条件随机场，可用来解决句法分析问题