数学之美笔记
一、统计语言模型
利用数学犯法来解决自然语言处理问题，而非传统的语法分析。基于概率的模型
P(S)=P(w1)P(w2|w1)P(w3|w1&w2)…P(wn|w1&w2…&wn-1)
利用马尔可夫假设，可以简化为：
P(S)=P(w1)P(w2|w1)P(w3|w2)…P(wi|wi-1)
二、谈谈中文分词
1.查字典法,最大匹配->最小分割法。但对于二义性无能为力
2.最大概率分词法。用统计语言模型计算出每种分词后句子出现的概率，并找出其中概率最大的。
找到复合词的嵌套结构
三、隐含马尔科夫模型在语言处理中的应用
(s1 s2 s3)->(o1 o2 o3)
求P(s1,s2,s3|o1,o2,o3)最大，利用贝叶斯公式：
P(o1,o2,o3,…|s1,s3,s3)*P(s1,s2,s3)
做两个假设：
- s1,s2,s3,..是一个马尔科夫链,即，si只由si-1决定
- 第i时刻的接受信号oi只由发送信号si决定,又称独立输出假设,即P(o1,o2,o3..|s1,s2,s3,..)=P(o1|s1)* P(o2|s2) * P(o3|s3)…
四、怎么度量信息？
香农：信息熵。
一条信息的信息量大小和它的不确定性有直接关系。它越不确定，信息量越大。
用bit的概念来度量信息量
$$ H(X)=- \sum_{x}P(x)\log_2[P(x)] $$
实际信息的表示和信息熵的差距称作"冗余度"(redundancy)
五、简单之美：布尔代数和搜索引擎的索引
最简单的索引是用一个很长的二进制数，每一位代表一个关键词，如果有，则为1，否则为0
六、图论和网络爬虫
BFS和DFS
网络爬虫，通过hash来判断是否爬过
七、信息论在信息处理中的应用
不确定性越小，模型越好。信息熵可以直接用于衡量统计语言模型的好坏。
两个概念：“互信息”(Mutual Information)和"相对熵"(Kullback-Leibler Divergence)
- 互信息:是对两个随机事件相关性的度量。可以很好地解决二义性
- 相对熵：衡量两个正函数是否相似。对于两个完全相同的函数，它们的相对熵等于零。
八、贾里尼克的故事和现代语言处理
九、如何确定网页和查询的相关性
对关键词次数进行归一化(否则长文章占优),即求频次：称为”关键词频率“或“单文本词汇频率”(Term Frequency)
还有要去除介词等"应删除词"(Stopwords)，
对不同的关键词给予不同的权重，如专业词比通用词权重高。有下面两个条件：
-
一个词预测主题能力越强，权重越大，反之越小
-
应删除词权重为零
使用最多的权重是”逆文本频率指数(Inverse document frequency)“: log(D/Dw),D为全部网页数
所以计算公式为：TF1 * IDF1 + TF2 * IDF2+.. + TFN * IDFN
给定查询，网页的综合排名由相关性和网页排名乘积决定
IDFN的计算公式为什么取log有待学习
十、有限状态机和地址识别
类似于时序逻辑里的状态转移
为了能进行模糊匹配，提出基于概率的有限状态机，和离散的马尔科夫链基本等效
十二、余弦定理和新闻的分类
基于TF/IDF，生成新闻的特征向量，用余弦定理计算它们的夹角，计算它们的相似度。
疑问：关于同义词、近义词是否有很好的映射工具
十三、信息指纹及其应用
其实就是hash函数，如MD5,SHA1等
十四、浅谈数学模型的重要性
- 一个正确的数学模型应当在形式上是简单的。
- 一个正确的模型在它开始的时候可能还不如一个精雕细琢的错误的模型来的准确，但是，如果我们认定大方向是对的，就应该坚持下去。
- 大量准确的数据对研发很重要。
- 正确的模型也可能受噪音干扰，而显得不准确：这时我们不应该用一种凑合的修正方法来弥补它，而是要找到噪音的根源，这也许能通往重大发现。
十六(上)、不要把所有的鸡蛋放在一个篮子里–谈谈最大熵模型
最大熵原理：要保留全部的不确定性，将风险降到最小。
最大熵原理指出，当我们需要对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设。
希萨证明，对任何一组不自相矛盾的信息，这个最大熵模型不仅存在，而且是唯一的，都有同一个非常简单的形式–指数函数。
$$ P(w3|w1,w2,subject)=\frac{e^{\lambda_1(w1,w2,w3)+\lambda_2(subject,w3)}}{Z(w1,w2,subject)}$$
$\lambda$ 和 Z需要通过观测数据训练出来。
十六(下)、不要把所有的鸡蛋放在一个篮子里–最大熵模型
最原始的最大熵模型的训练方法是一种称为通用迭代算法GIS(Generalized iterative scaling)的迭代算法。分为以下几个步骤
- 假定第零次迭代的初始模型为等概率的均匀分布。
- 用第N次迭代的模型来估算每种信息特征在训练数据中的分布，如果超过了实际的，就把相应的模型参数变小；否则，将它们变大。
- 重复步骤2直到收敛
实际应用中很少用，只是通过它了解最大熵模型的算法，迭代时间长，次数多，不太稳定，容易溢出
后来有很多改进工作
十七、闪光的不一定是金子，谈谈搜索引擎作弊问题(Search Engine Anti_SPAM)
常见作弊方法：增加关键词，创建专门放链接的网站
相当于声音中加入了噪音，而混入噪音，在数学上相当于两个信号做卷积。噪音消除的过程就是解卷积的过程。
十八、矩阵运算和文本处理中的分类问题
分类需要计算相关性，而用内积方法的话，两两配对，计算量很大
另一种方法是利用矩阵运算中的奇异值分解(Single Value Decomposition 简称SVD)：大矩阵拆分成小矩阵
十九、马尔科夫链的扩展–贝叶斯网络(Bayesian Networks)
把有向图看成一个网络，就是贝叶斯网络，每个圆圈代表状态，状态之间的连线表示它们的因果关系。这些关系都有一个可以量化的可信度(belief)
贝叶斯网络的训练是NP-complete问题。
二十一、布隆过滤器(Bloom Filter)
实际上是一个很长的二进制向量和一系列随机映射函数。
n个随机函数选择位，然后设为1。
有误判概率
二十二、由电视剧《暗算》所想到的-谈谈密码学的数学原理
RSA加密