最近两周在拜读吴军的《数学之美》，对NLP中的一些“道”了解了一下，感受到了数学的强大，其中有一些名词很有代表性，特此记录，以免遗忘。
注：本文中大部分内容都摘自《数学之美》，特此说明！
实际应用：语音识别
马尔科夫提出了一种假设：随机过程中各个状态St的概率分布，只与它的前一个状态St-1有关。比如天气预报，硬性假定今天的气温只跟昨天有关而与前天无关。这个假设被命名为马尔科夫假设，符合这个假设的随机过程则被称为马尔科夫过程，也称为马尔可夫链。
从一种状态变换为另一种状态的概率，就是转移概率。
举例： 比如今天天气很潮湿，明天下雨的概率为90%，不下雨的概率为10%，则从“天气潮湿”——>“明天下雨”的转移概率就是90%。
隐含马尔可夫模型是马尔可夫链的一个扩展：任一时刻t的状态St是不可见的。所以观察者没法通过观察到一个状态序列S1,S2,S3,…Sr来推测转移概率等参数。但是，隐含马尔可夫模型在每个时刻t会输出一个符号Ot，而且Ot跟St相关且仅跟St相关。这个被称为独立输出假设。隐含马尔可夫模型的结构如下：其中隐含的状态S1，S2, S3,…是一个典型的马尔可夫链。
个人理解： 现实生活中，很多事物会有正反两面，我们能看到的往往只是正面（表面），但是真正能说明事物的其实是反面（里面），但是我们只能得到正面无法得到反面，所以假设每一个反面对应的正面也是符合马尔可夫链的。
实际应用：NLP（自然语言处理）
信息熵，也就是将信息的量（或价值）统计出来。
H(x) = E[I(xi)] = E[ log(2,1/P(xi)) ] = -∑P(xi)log(2,P(xi)) (i=1,2,…n)
举例： 比如世界杯结束了，我一场都没看过，我要从32支队伍中猜测哪只队伍获胜了，那对我来说“最后谁得了冠军”这条信息的价值就是-A队获胜的概率log(A队获胜的概率)-B队获胜的概率log(B队获胜的概率)…
如果对我来说32支队伍的获胜概率都是一样的，也就是1/32，那么信息熵就是-32*(1/32)*log(1/32)=5
实际应用：NLP（自然语言处理）
简单来说，图论就是把物与物之间的关系用图和线条结合并展示出来。
里面有2种遍历算法：
1）、广度优先搜索（Breadth-First Search，简称BFS）
是指把与其直接相连的节点先走一遍，然后再依次再子节点中再遍历一次。比如很多卖保险的，都会先从身边人开始销售，等身边人销售完了，再通过某个好友发展下线继续来一遍。
2）、深度优先搜索（Depth-First Search，简称DFS）
一条路走到黑，走得通最好，走不通就换条路继续走。
是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。只要做好散列表，那么查找的时间就只有O(1)
实际应用：搜索引擎网页排名
PageRank是Google所有引擎中网页排名的算法。
当你在使用搜索引擎时，什么内容会放在前面，什么内容会放在后面呢？排除广告不说，只有把用户想要的东西放在前面，这样用户才会喜欢上这个搜索引擎。PageRank的做法就是民主表决，比如有100个人搜索“数学之美”，有1000个网站与之有关，其中80个人认为A网站符合自己的需求，那么A的排名就最高。
实际应用：搜索引擎网页查找
PageRank是用来对相关的网页进行排名的算法，而TF-IDF则用来把相关联的网页给找出来。
比如一段文字有100个字，其中大数据出现3次，那么它的tf就是0.03
当一个词在很多网页中都出现过，说明这个词“不值钱”，比如“我”、“和”这种停用词（stopwords），越专业的词才会在越少的词中出现。
假设一个关键词w在Dw个网页中出现过，那么Dw越大，w的权重越小，IDF就是来计算w的权重的。
公式为log(D/Dw)，其中D是全部网页数
比如假定中文网页数为D=10亿，其中包含专用词“大数据”的网页数为200万，即Dw=200万，
则它的权重IDF=log(100000/200)=log(500)=8.96
知道了TF和IDF，就可以计算出该网页和搜索内容的相关性了。
比如我要搜“大数据和云计算”，则TF-IDF的计算结果就是：
TF(大数据)*IDF(大数据)+TF(云计算)*IDF(云计算)
实际应用：地址快速匹配（如快递）
有限状态机是一个特殊的有向图，包括一些状态（节点）和连接这些状态的有向弧。
每一个有限状态机都有一个开始状态和一个终止状态，以及若干中间状态。每一条弧上带有从一个状态进入下一个状态的条件。当其获得一个输入字符时，将从当前状态转换到另一个状态，或者仍然保持在当前状态。
比如：一串地址“上海市浦东新区春晓路100号”，当进行到“市”后，自动进入下一步“区”进行匹配，这样就可以把地址进行快速的分解和匹配。
实际应用：地图最短路径
比如要找从北京到广州的最短路线，假设北京到广州之间有20个城市，那么最傻瓜的做法就是把所有可能的线路看一遍，然后找到最优的，这样的计算量是指数级的增长，明显不可取。
动态规划的方法，就是把北京和广州之间横切几刀（比如3刀），从北往南数第一刀之上，假设有3个城市，分别是A、B、C，因为要找到北京和广州之间的最短路径，不论如何总会经过A、B、C三个城市中间的一个（乘飞机的滚开！），那么北京到A、B、C三个城市的最短路径肯定也是包含在北京和广州之间的最短路径里的。比如找到了北京和A的距离是最短的，然后在找城市A和第2刀之间的几个城市中的最短路径，以此类推，一直到广州为止，这样的计算量大概是傻瓜办法的万亿被之一。
实际应用：大数据处理
之前有提到过根据余弦定理来计算文章和词之间的关联性，但实际操作中，往往是成千上万篇文章和几十上百万个词的关联性计算，这样的话数据量会非常非常大。在这个矩阵中，每一行对应一篇文章，每一列对应一个词，如果有N个词，M篇文章，则得到一个M X N的矩阵。其中，第i行、第j列的元素aij，是字典中第j个词在第i篇文章中出现的加权词频（比如用词的TF-IDF值），比如M=1000000,N=500000,100万乘50万，即5000亿个元素。
奇异值分解，就是把上面这样一个大矩阵，分解成三个小矩阵相乘。
第一个矩阵X是对词进行分类的一个结果。它的每一行表示一个词，每一列表示一个语义相近的此类，或者简称语义类。这一行的每个非零元素表示这个词在每个语义类中的重要性（或者说相关性），数值越大越相关。
第三个矩阵Y是对文本的分类结果。它的每一列对应一篇文章，每一行对应一个主题。这一列中的每个元素表示这篇文本在不同主题中的相关性。
中间的矩阵则表示词的类和文章的类之间的相关性。
只要对关联矩阵A进行一次奇异值分解，就可以同时完成近义词分类和文章的分类。另外，还能得到每个主题和每个词的语义类之间的相关性！
实际应用：唯一性判断（识别盗版）
任何一段信息（包括文字、语音、视频、图片等），都可以对应一个不太长的随机数，作为区别这段信息和其他信息的指纹。只要算法设计得好，任意两端信息的指纹都很难重复，就如同人类的指纹一样。信息指纹在加密、信息压缩和处理中有着广泛的应用。
信息指纹的一个特征是其不可逆性，即无法根据信息指纹推出原有信息。
通过该算法可以将任意很长的整数转换成特定长度的伪随机数。
常用的算法有MD5（很熟悉，有没有！）或者SHA-1等标准。
实际应用：NLP、金融等
论及投资，人们常说不要把所有的鸡蛋放在一个篮子里，这样可以降低风险。在数学上，这个原理称为最大熵原理（The Maximum Entropy Principle）。
最大熵模型，就是要保留全部的不确定性，将风险降到最小。
最大熵原理指出，对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设。
对于一个信息，任何编码的长度都不小于它的信息熵。
实际应用：词分类
每一个状态只跟与其直接相连的状态有关，而跟与它间接相连的状态没有直接关系，就是贝叶斯网络。
实际应用：句法分析
自然语言的句法分析（Sentence Parsing）一般是指根据文法对一个句子进行分析，建立这个句子的语法树，即文法分析（Syntactic Parsing）。
实际应用：各种模型的核心
在一般性的问题中，如果有非常多的观测数据（点），让计算机不断迭代来学习一个模型。首先，根据现有的模型，计算各个观测数据输入到模型中的计算结果，这个过程称为期望值计算过程（Expectation），或E过程；接下来，重新计算模型参数，以最大化期望值。这个过程为最大化的过程（Maximization），或M过程。这一类算法就称为EM算法。
之前介绍的很多算法，其实都是EM算法，比如隐含马尔科夫模型的训练方法Baum-Welch算法，以及最大熵模型的训练方法GIS算法。
实际应用：现在的AI大多就是是ANN
人工神经网络是一个分层的有向图，第一层（一般图中会展示为最下方或最左方）用来接受输入的信息，也称为输入层。来自这些点的数值按照它们输出的弧的权重，根据G=w0+X1W1+X2W2+…XnWn进行线性加权得到G，然后再做一次函数变化f(G)，赋给第二层的节点Y。
第二层的节点照此将数值向后面传递，直到第三层节点，如此一层层传递，直到最后一层，最后一层又被称为输出层。
在模式分类时，一个模型（图像、语音、文字等）的特征值（比如坐标），从输入层开始，按照上面的规则和公式一层层向后传递。最后在输出层，哪个节点的数值最大，输入的模式就被分在哪一类。
在人工神经网络中，需要设计的部分只有两个，一个是它的结构，即网络分几层、每层几个节点、节点之间如何连接，等等；第二就是非线性函数f()的设计，常用的函数是指数函数，即
f(G)=e(G次方)
成本函数需要遵循这样一个原则：既然人工神经网络解决的是分类问题，那么我们希望分完类之后，同一类样本（训练数据）应该相互比较靠近，而不同类的样本应该尽可能地原理。
Google大脑，说穿了是一种大规模并行处理的人工神经网络。
Google大脑采用人工神经网络而不是其他机器学习的技术原因：通用性、稳定性和易并行化。
Google大脑采用了随机梯度下降法（Stochastic Gradient Descent），这种算法在计算成本函数时不需要像梯度下降法那样对所有的样本都计算一遍，而只需要随机抽取少量的数据来计算成本函数，这样可以大大降低计算量，当然会牺牲一点准确性。
在现实生活中，真正能够通用的工具在形式上必定是简单的！
实际应用：Everywhere