数学之美的随笔记录

《数学之美》看完后，第一感觉就是的确是一本好书，谢谢推荐。像我这种不懂数学的更应该多看看，还得多看几遍。

下面是看书的时候，随手记下的：

 

-----------------------------------------------------------------------------------------------------------------------------------------------

 

离散数学： 数理逻辑（基于布尔运算，0 + 1二进制）、集合论、图论、近世代数、概率论、统计学。

 

搜索核心： 下载网页 + 索引 + 排序。

 

网络爬虫的本质： 对超链接图的一种遍历算法。其中，使用散列表（哈希表）来记录已经下载过的网页信息。

 

在处理分类时：可先使用奇异值分解（粗分类，不需要一次次迭代，节约时间） +  再使用向量余弦距离自底向上分类（细分类，多次迭代）。

 

信息指纹： 用来检查元素是否存在。如：判断两篇文章是否抄袭，分别将两篇文章切成小片，取其特征词集合，计算指纹。

 

加密算法：Rabin + RSA。

 

搜索基础：单文本词频/逆文本频率指数(TF-IDF) + 网页排名(PageRank)

 

最大熵模型：属于专用来处理同时满足很多（成千上万）不同条件时，最小风险的一种数学模型。

 

布隆过滤器：

比如过滤垃圾邮件，使用8个固定的R随机器将email地址转换成对应的8个指纹信息，再使用G随机器将这8个指纹随机对应到向量链中的

8个元素，将这8个元素设置为1（其他所有都默认设置的是为0）。当一条垃圾邮件过来时，先使用8个R随机器将其转换成对应的8个指纹

信息，再将这8个指纹与向量链中的被标记元素作对比，若每个指纹对应的元素都为1即为垃圾邮件。

 

贝叶斯网络：

在马尔科夫成立的条件下，若一个状态只与其直接相连的状态有关，而与其间接相连的状态无直接相关，则为贝叶斯网络（信念网络）。

通用的贝叶斯网络工具包，在图像处理、文字处理、决策等应用可以很多。

 

 

逻辑回归模型，可用作广告业务的搜索。

 

分冶算法，最经典的应用就是MapReduce：将大任务分拆成很多小的任务独立计算，再合并数据。

 

好方法在形式上常常是简单的！

 

背景知识：

概率论、信息论、统计学、线性代数、布尔代数、计算机算法、数值分析、费尔马小定律（密码学）、机器学习、模式分类（神经网络）。

 

 

1、自然语言的处理实际上是一种基于概率统计的数学模型算法。

2、在语料库的选择上，也要选择合适的语料库。

3、隐含马尔可夫模型： 鲍姆-韦尔奇算法 + 维特比算法。

4、熵、条件熵（适于高阶语言模型）、相对熵（适于在真实的语料训练中有概率偏差）、信息熵。

5、布尔代数：搜索引擎的核心最终还是使用的是更多的布尔运算。

6、网络爬虫的下载：

1）爬虫不仅仅局限于BFS + DFS的下载方式，更重要的是有一个管理下载优先级的调度系统，来根据网页重要性权重等决定下载顺序。

2）解析页面中的JS脚本来获取数据。

3）使用哈希表来存储已下载过的网页URL，为减少通讯损耗，可以分批次批量的询问哈希表或更新哈希表中的内容。其中，爬虫中用到的就是图论技术。

7、PageRank：网页排名算法（投票选举）。通过矩阵的线性代数运算，来收敛差异，获得网页之间的链接关系。

8、TD-IDF：衡量词的词频权重。

9、有限状态机：属于一种单向的有向图，只允许往一个方向寻找。

      动态规划：指在加权图（指在连接图像节点的弧上添加一些权重说明）上寻找最短路径。

      有限状态机 + 动态规划的适用范围：地址识别、导航、语音识别、拼写、语法纠错、拼音输入法、工业控制、生物序列。

10、向量余弦定理：

通过余弦值来分析夹角判断新闻（或其他）的相似性。其中，对特殊位置（标题/最后一段…）可使用加权操作来提升分类的准确性。

11、信息指纹：通过伪随机数算法来生成网页的指纹信息。可对视频信息的关键帧做信息指纹，通过判断信息指纹来反盗版。

12、在密码学中，一般是找两个很大的素数。

13、最大熵模型：应用于词性标注、句法分析、股票预测等等。最大熵模型早期使用的是GIS迭代算法，之后改进为IIS迭代算法。

14、拼音输入法：对拼音编码 + 消除歧义性编码。

        在编码上：可对常见字进行短编码、对不常见子进行长编码。（词库越大，在上下文处理方面越好）

        拼音转汉字：根据输入的拼音会有很多不同的概率事件，其中需要找到最大的概率的汉字，也就相当于寻找最短路径（动态规划）。

15、文法分析：让被分析的句子的语法树概率达到最大。其中，对一个句子，每扫描一次使用括号做一次语义分割。

条件随机场：属于一种特殊的概率图模型，随机变量之间需要遵守马尔可夫假设，且每个状态的转移概率只取决于相邻的状态。

       与贝叶斯网络不同的是：条件随机场是无向图，而贝叶斯网络是有向图。

       条件随机场是一种灵活的预测统计模型，非常适用于预测和统计方面。

16、维特比算法：属于应用最广的动态规划算法，可以和隐含马尔可夫链很好的结合。

 

17、期望最大化算法：EM算法，定义最大化函数最重要。

-----------------------------------------------------------------------------------------------------------------------------------------------

 

《算法导论》可以看看。