chapter 3

汉语的词汇量大致在200k最有，训练一个三元模型就有200K^3 的参数，即使将整个互联网的全部中文内容用作训练，很可能只有10^13。如果只用比例来计算概率，大部分的条件概率仍然为0，这样的模型被我们称之为 不平滑 的模型。

使用古德-图灵（Good-Turing Estimate）去估算，即从概率的总量中分配一个很小的比例给那些没有看见的事件。即使得看见的事件的概率总量之和小于1。然而需求调多少的比例，就要根据古德-图灵公式去估算。
定义语料库中出现了r次的词为Nr个，总量很自然的用r*Nr的总和，但是这时为了使平滑，所以r不用r，定义一个新的dr来代替r

由于Zipf定律，即r越大，词的数量Nr越小，即可以保证d0>0。

在二元模型中，则是用卡茨退避法(Katz backoff)来进行平滑，同样的，内伊(Herman Nay)在此基础上优化了卡茨退避法。

chapter 4

分词法的发展：

1. 查字典的方法
2. 引入了统计语言模型解决语义中的二义性问题 （维特比算法）
3. 现代分词器的颗粒度问题以及选用的语料库的区别

chapter 5

在通信模型中引入隐马尔科夫模型(Hidden Markov Models)

1. 针对已知 观测序列，求最大可能的 隐含序列的问题。在不同的领域中有着不同的名字，在语音识别中被称为 声学模型(Acoustic Model)，在机器翻译中是 翻译模型(Translation Model)，而在拼写校正中则是 纠错模型(Correction Model)。
2. 简单描述了隐马尔科夫模型中基本的 三个问题
3. 主要描述了HMM的训练过程，其中分为有监督的训练方法和无监督的训练方法(Baum-Welch Algorithm)。是一个EM(Expectation-Maximization)算法的过程。

chapter 6

信息论的基本概念
包括信息熵的基础，公式，讲解
条件熵的概念，用以说明为什么相关的信息可以用来消除不确定性。
即通过相关的信息来消除模型中的不确定性
互信息的概念，度量两个随机事件“相关性”的量化衡量
相对熵（交叉熵Kullback-Leibler Divergence）：同样地，是用来衡量相关。但不同于互信息，是用来衡量两个取值为正数的函数的相似性

1. 对于两个完全相同的函数，他们的相对熵等于0
2. 相对熵越大，两个函数差异越大
3. 对于概率分布或者概率密度函数，如果取值均大于0，相对熵可以度量两个随机分布的差异性
4. 相对熵是不对称的。

后有人从条件上和相对熵出发，定义了一个称谓语言模型复杂度（Perplexity）的概念，直接衡量语言模型的好坏。即在给定上下文的条件下，句子中每个位置平均可以选择的单词的数量。
信息的作用：在于消除不确定性，自然语言处理的大量问题在于寻找相关信息。

chapter 8

关于搜索
一个搜索引擎需要做的事情：

1. 自动下载尽可能多的网页
2. 建立快速有效的索引
3. 根据相关性对网页进行公平准确的排序。

如何在搜索系统的索引中使用布尔运算。对每次的搜索，可以在数据库中所有的网页生成一个长度为网页数量的二进制字符串。通过布尔运算中的AND OR进行计算，从而大大减少时间。

chapter 9

图论中的遍历算法

1. BFS（Breadth-First Search）
2. DFS（Depth-First Search）

工程上说，由于大部分网页最重要的为首页，所以其实BFS比DFS在实际上更常用一点。但DFS的请求次数会比BFS的少很多。
当然工程上的网络爬虫，对网页遍历的次序不是简单的BFS或者DFS，而是一个有着相对复杂下载优先级排序的方法，而管理这个优先级排序的子系统一般称为调度系统（Scheduler）

chapter 10

Google 的PageRank算法（民主表决式的网页排名技术）
搜索结果的排名取决于两个信息

1. 关于网页的质量信息（Quality）
2. 查询用词与每个网页的相关性信息（Relevance）

通过初始化一个排名，然后每次使用这个排名及其相应的链接权重去重新计算排名，不断迭代后可以收敛到一个真实的排名。

通过稀疏矩阵相乘的方法优化过于巨大的矩阵相乘。

影响搜索引擎质量的因素

1. 用户的点击数据
2. 完备的索引
3. 对网页质量的度量
4. 用户偏好
5. 确定一个网页和某个查询相关性的方法

chapter 11

确定相关性

1. 归一化网页-->避免长内容网页跟短内容网页的bias
2. 计算关键词出现次数/网页的总字数
3. 即查询一个网页中N个关键词的出现频率，即TF（Term Frequency，即词频）
4. 不同的查询词得到权重也是不一样的，甚至于一些语气词的权重应该是0
5. 权重中使用最多的权重即 “逆文本频率指数”IDF（Inverse Document Frequency）

若该关键词只在很少的网页中出现，则权重大。

4. 使用TF-IDF，相关性就从TF的累加，变成了TF*IDF的累加。
5. 有人指出IDF其实就是一个在特定条件下关键词的概率分布的交叉熵。

chapter 12

特殊的上下文识别，地址。

最有效的识别分析方法------有限状态机

有限状态机：一个特殊的有向图，具有一个开始和一个终止状态，点之间的链接具有方法，代表状态转移的条件(类似于树结构)。若能从开始状态走到终止状态，这说明该地址有效。

为解决模糊匹配的地址的问题，提出了一个基于概率的有限状态机，类似于离散的马尔科夫链。

全球导航(动态规划 Dynamic Programming)

在一个加权无向图上规划一个最短路径

该处动态规划的原理： 假设寻找北京到广州的最短路径，在北京到广州的中点城市中遍历，若为最短路径，那么北京到中点城市的路径必然也是最短。从而将一个全局的最短路径问题不断的分块成一个局部的最短路径问题。

有限状态传感器的拓展

在语音识别和自然语言理解中也有该模型的利用。但未一种特殊的有限状态机---加权的有限状态传感器(Weighted Finite State Transducer) WFST。
特殊之处在于每个状态由输入和输出的符号来定义，其中输入和输出都具有多个，如：某个状态可以为输入为is或者are，输出为better或者worse，并且具有对应的权重，通过动态规划去找到一个概率最大的路径，从而找到一个概率最大的识别到的句子。

chapter 14

新闻的自动分类 ---> 余弦定理
建立一个特征变量，从建立的字典集中计算每一个词的TF-IDF值，从而形成一个一维向量/文章。衡量两篇文章的相似度可以用计算两篇文章特征向量的夹角的值，夹角越小则说明其相似度越大。

这样的方法既可以用有监督的训练方法，也可以用无监督的阈值来不断的聚类，直到不存在低于该阈值的两个小类。

算法本身的优化：

1. 删除虚词
2. 储存向量长度
3. 删除为0的元素，只计算非零元素
4. 位置的加权 （标题的词比文中的词重要，开头结尾的词也更重要）

chapter 15

矩阵运算和文本处理中的两个分类问题

同样为前一章的问题，如果不想两两计算文章之间的相似度(因为在复杂度很高)，能否一次性算出所有文章的相关性。 使用奇异值分解(Singular Value Decomposition)可以做到
每一行代表一篇文章，每一列代表一个词在对应文章中的TF-IDF，则可以构造出一个巨大的Matrix。

然后通过奇异值分解分成三个小矩阵相乘。

这个地方吴军老师似乎写错了，我这里加以改正

1. 第一个矩阵则为对文章进行分类的结果，每一行表示一篇文章，每一列代表一个分类结果。值是这一篇文章跟这个分类的相近程度。
2. 第三个矩阵则为对词进行的分类结果，每一列代表一个词，每一行为一个语义类，对应的，该词与这个语义类的相关程度。
3. 第二个矩阵则为语义类和文章分类的相关程度的矩阵。

但SVD的方法较上篇两两计算的方法粗糙，所以可以基于SVD的结果上去进行余弦计算的迭代。

chapter 16

信息指纹的存在

相似哈希--一类特殊的信息指纹

1. 假定一个网页中有若干个词，先计算出它们的权重(例如TF-IDF的值)，再计算这些词的信息指纹，若用8位二进制来记录。
2. 扩展：将原先的8位的信息指纹扩展成8个实数，若w1的指纹第一位为1，则第一个实数+w1，反之则-w1,。如此拓展，用若干个词的权重的加减分别构成8个实数。
3. 收缩：把8个实数变回一个8位的二进制数，如果大于0，就为1，否则就为0。这样得到一个8位的二进制数字。

从而我们可以用一个简单的相似哈希来代表一个网页，然后比较两个相似哈希就可以比较相似程度。

chapter 17

对于凯撒加密法之类的，可以通过统计词频，可以轻易的破解这种加密方式。由于这些词频在加密前后没有发生任何改变，只是进行了转变

RSA算法的加密

1. 任意找两个很大的质数P，Q进行相乘
   N = P * Q;
M = （P-1）*（Q - 1）
2. 找一个和M互素的整数E
3. 找一个整数D，使得E * D 除以 M 余 1。
   其中E是公钥，D是私钥。
   加密： X^E mod N = Y ，Y即加密内容，X为待加密内容。
   解密：Y^D mod N = X

chapter 18

搜索引擎的反作弊：防止部分网站通过一些作弊手段提高在搜索引擎中的排名。

搜索结果的权威性：PageRank的算法无法保证搜索结果的权威性，许多排名高的网站可能只是主流更关注的网站而非更权威的网站。所以需要引入提及（Mention）的概念，如果多篇文章或者网站在提及同一个话题时，提及的组织或个人很多，那么我们会倾向于使用这些组织或个人的搜索记录排在前面。

计算权威度的步骤：

1. 对网页的内容进行句法分析，以及对信息源的提及
2. 利用互信息，找到短语与信息源之间的相关性。
3. 对短语进行聚类，
4. 对信息源的网页的子网页和子目录进行聚类

chapter 19

天文学上，古埃及人是根据天狼星和太阳在一起的位置来判断一年中的时间和节气

美索不达米亚文明兴起时，古巴比伦人的历法中产生了月和四季的概念，并且观测到了五大行星不是简单的围绕地球转，而是波浪形的运动。所以，行星（Planet）即指飘移的星球

托勒密发明了球坐标，赤道和零度经线在内的经纬线，提出了黄道，发明了弧度制，用40-60个大圆套小圆的方法精确计算了所有行星运动的轨迹。。。(害怕)....制定了儒略历（即每年365天，每4年为一个闰年，多一天）。后来被教皇格里高利十三世改正。

开普勒的日心说刚开始，计算出来的行星运动轨迹反而没有托勒密的高。

chapter 20

最大熵原理：对一个随机事件的概率分布进行预测时，预测应当满足全部已知条件，对于未知的情况不要做任何的主观假设，使用概率分布最均匀的模式，可以使得概率分布的信息熵最大。

最原始的最大熵模型的训练方法是一种称为通用迭代算法（Generalized Iterative Scaling）GIS的迭代算法。是一种EM算法。后来提出了改进迭代算法IIS。

chapter 23

布隆过滤器

原理：在于两个完全随机的数字相冲突的概率很小，所以可以在很小的误识别率的条件下，用很少的空间储存大量信息。
优点：只需要散列表1/8-1/4左右的大小就能解决同样的问题
做法：若储存1亿个邮件地址，只需要准备16亿个全部为0比特位(2亿个字节)，对每个点以邮件，使用8个不同的随机数产生器，产生8个信息指纹，再用一个随机数产生器把这8个信息指纹映射到1-16亿的8个自然数，现在将这8个位置全部设为1,。由此往复。

这样给一个电子邮件Y，只需要检查对应8个位置是否为1。即可。

缺点：存在误分类，可能把错误认为该Y邮件地址已经存在。

chapter 25

文法分析

自然语言中的句法分析一般指根据文法对一个句子进行分析，建立这个句子的语法树，即文法分析（Synatctic Parsing）。

对一个句子中各成分的语义进行分析，得到对这个句子语义的一种描述，即语义分析（Semantic Parsing）。

传统的文法分析是基于规则的方法，不断地使用规则将树的末端节点逐级往上合并，直到合并出根节点。

后来发展出另外的方法：

1. 先进行分词
2. 从左到右用括号括起来，进行分组
3. 给每个括号一个句子成分，重复括括号的过程
4. 直到整个句子被一个大括号覆盖。每个括号，就是句子的一个成分，括号之间的嵌套关系，就是不同层面的句子成分的构成关系。

每次从左到右扫描词或者成分时，只需要判断进行三个操作之一。

1. 是否开一个新括号
2. 是否继续留在这个括号中
3. 是否结束一个括号

并且在判断哪个操作之前，建立了一个统计模型P（A|prefix），prefix表示了从句子开头到目前位置所有的词和其语法成分。使用最大熵模型实现。
优点：从左往右的一个扫描过程大大减少了分析的时间，将算法的复杂度降到了句子长度的对数函数的级别，从算法的计算时间上来说已经是一个最优的算法
缺点：对于语义语法严谨的报刊文句，正确率可以达到80%以上，但是如果需要分析网文的语义语法，就会非常的差。但鉴于自然语言处理的实际应用中，也只需要对语句进行浅层的分析。

后来采用了一种新的数学模型工具---条件随机场（CRF Conditional Random Field）

CRF

属于一种 HMM（Hidden Markov Models）的拓展，所以也要符合马尔科夫假设，同样的也属于一种特殊的概率图模型（PGM）。

与HMM不同的地方在于，观察层不仅与当前的隐含状态有关，还可能会与前后的隐含层相关。，当然隐含层自身还是一个马尔科夫链。

使用最大熵模型的训练方法去求得边缘概率，从而求得联合概率。

chapter 26

维特比算法

略

CDMA技术

频分多址、时分多址、码分多址。

1. 对频率进行切分，每一路通信使用一个不同的频率
2. 将同一频带按时间分成很多份。
3. 将很多细分的频带合在一起，很多路信息同时传输，应该可以提高带宽的利用率。可以根据密码去过滤无法解码的信号，从而实现码分多址

chapter 27

EM算法（Expectation Maximization Algorithm）

相比于

1. 预先设定好的类别和文本中心进行聚类

2. 自底向上地将文本两两比较进行聚类

EM算法可以随机设定一些中心点，然后进行多次迭代后即可收敛到少数的类。
前提是距离函数要足够的好，保证同一类相对距离较近，不同类的相对距离较远。

若扩展到其它机器学习的问题中。

1. 期望值计算过程：计算各个观测数据输入到模型中的计算结果
2. 最大化的过程：重新计算模型参数，以最大化期望

缺点：如果优化的目标函数是一个凸函数，那么一定能保证得到全剧最优解，但如果优化的目标函数不能保证为凸函数，则不能保证为全局最优解

chapter 28

Logistic Regression & 定向广告

通过逻辑回归模型，假设有k个影响点击率的变量x1,x2,x3,...,xk。用线性组合的方法组合起来，这个和的结果作为逻辑回归模型的自变量。将其代入逻辑回归模型后即可得到一个概率。（由于一个逻辑回归模型定义域为所有实数，值域只在0-1间。）

将k个变量与其系数作为每一个用户得到定制标准，并且根据数据挖掘专家来处理分析，即可得到每个人定制化得到对特定广告的点击率，从而实现定向广告的目的。

通过最大熵模型的IIS方法可以直接训练逻辑回归函数的参数

chapter 30

人工神经网络

特殊性

1. 所有的节点都是分层的，每一层节点可以通过有向弧指向上一层节点，同一层节点之间没有弧相互连接，且每一个节点不能越过一层连接到上上层的节点上。
   2.每个弧上有一个权重。

一般不会超过五层的网络

擅长于在多维空间进行模式分类的问题。