数学
上一次修改时间：2016-08-22 10:44:49

数学之美笔记

  1. 校难码

    例如手动抄写一本书时，可以给每个文字加上一个笔划数，然后每行的最后是这行的笔划数的总和，抄写完成后，对比每行的笔划总数，即可校该行文字是否正确；如不正确，再对笔该行上每列的数字，从而快速确定错误的所在；


  2. 统计语言模型

  3. 任何一种语言都是一种编码方式，而语言的语法规则是编解码的算法。我们把一个要表达的意思，通过某种语言的一句话表达出来，就是用这种语言的编码方式对头脑中的信息做了一次编码，编码的结果就是一串文字。而如果对方懂得这门语言，他或者她就可以用这门语言的解码方法获得说话人要表达的信息。这就是语言的数学本质；

  4. 现在通用的计算机处理自然语言方法，基本都是基于统计的自然语言处理方法，该方法在数学模型上和通信是相通的，甚至就是相同的；(非传统的基于规则的方法，即单纯的句法分析和语义理解)

  5. 统计语言模型中，语料库的选取和模型应用的领域不能脱节，否则模型的效果通常要大打折扣。比如建立一个应用是网页搜索的语言模型，它的训练数据(语料库)应该是杂乱的网页数据和用户输入的搜索串，而不是传统的、规范的新闻稿，虽然前者夹杂着噪音和错误，但在网页搜索应用中，效果也比后者好；


  6. 中文分词

  7. 分词器示意图

    QQ图片20160807200659.png

    分词器的准确率是相对的，不能说一个准确率为97%的分词器就一定比另一个准确率为95%的要好，因为这要看它们选用的所谓正确的人工分词的数据是如何得来的(人工分词的数据也因人而异，没有绝对的准确性，如清华大学，有人会认为是一个词，有人会认为要分成两个词)，所以只能讲某个分词器和另一个相比，与人工分词的结果吻合度稍微高一点而已。另外，目前的中文分词按上面的统计语言模型的方法，提高的空间已经微乎其微了，近年来中文分词主要花费精力的地方是做数据挖掘的工作，不断完善复合词的词典；


  8. 隐含马尔可夫模型

  9. 隐含马尔可夫模型最初应用于通信领域，继而推广到语音和语言处理中，成为连接自然语言处理和通信的桥梁。同时，隐含马尔可夫模型也是机器学习主要工具之一。和几乎所有的机器学习的模型工具一样，它需要一个训练算法(鲍姆-韦尔奇算法)和使用时的解码算法(维特比算法)；


  10. 信息的度量和作用

  11. QQ图片20160808112445.png

  12. 一个事物(比如二战时日本内阁的战略决定)内部会存在着随机性(对苏联来说有可能是北上和苏联做战，也有可能是南下和美国开战)，也就是不确定性，假定为U，而从外部消除这个确定性唯一的办法就是引入信息I(苏联传奇间谍佐尔格向莫斯科发去了日本将南下的情报),而需要引入的信息量取决于这个不确定性的大小，即I>U才行(消除不确定性后，苏联将中苏边界上的60万大军调往欧洲做战)。当I<U时，这些信息可以消除一部分不确定性，也就是说新的不确定性U` = U - I;

  13. 几乎所有的自然语言处理、信息与信号处理的应用都是一个消除不确定性的过程；


  14. 布尔代数和搜索引擎的索引

  15. 数据库查询语句(SQL)支持各种复杂的逻辑组合，但背后的基本原理是基于布尔运算的；

  16. 目前的搜索引擎会自动把用户的查询语句转换成布尔运算的算式。搜索引擎的索引也可以用一长串二进制表示，0表示没有该关键词，1表示有该关键词；

  17. 图论和网络爬虫

  18. 网络爬虫的原理就是图的遍历；互联网上的每个网页可以看作是图中的一个节点，网页中的超链接可以当作连接网页的弧。有了超链接，我们可以从任何一个网页出发，用图的遍历算法，自动地访问到每一个网页并把它们存起来为。完成这个功能的程序就叫网络爬虫。

  19. 实际的网络爬虫程序中，还需要使用个哈希表来存储、查询将要访问的网页是否已经访问过。

  20. 目前的互联网网页数量十分庞大，例如Google在2010年时整个的索引大小有5000亿个网页，即使更新最频繁的基础索引也有100亿个网页，假如下载一个网页需要一秒钟，下载这100亿个网页需要317年，如果下载5000亿个网页则需要16000年左右，是我们人类有文字记载历史的三倍时间。因此，一个商业的网络爬虫需要有成千上万个服务器并通过调速网络连接起来协调工作；

  21. 网络爬虫对网页遍历的次序不是简单的BFS(广度优先搜索)或者DFS(深度优先搜索)，而是有一个复杂的下载优先级排序的方法。管理这个优先级排序的子系统一般称为调度系统(Scheduler);


  22. PageRank(网页排名算法，发明该算法的是Google的创始人拉量.佩奇和谢尔盖.布林)

  23. 核心思想：在互联网上，如果一个网页被很多其它网页所链接，说明它受到普遍的承认和依赖，那么它的排名就高；(百度和Google的排名排名权重)

  24. 核心问题：计算搜索结果的网页排名过程中需要用到网页本身的排名，这是一个类似"先有鸡还是先有蛋"的问题。这个问题可以变成一个二维矩阵相乘的问题，先假设所有网页的排名是相同的，并且根据这个初始值，算出各个网页的第一次迭代排名，然后再根据第一次迭代排名算出第二次的排名。


  25. 如何确定网页和查询的相关性

  26. 度量网页和查询的相关性，有一个简单的方法，就是直接使用各个关键词在网页中出现的总词频(总词频为单词频的和，单词频为关键词与网页上所有词的总和，的比值)。

  27. 总词频的注意事项：1)要去掉停止词，如汉语中的"的","是","和","地"等；2)需要对汉语中的每一个词一个权重，该词预测主题的能力越强，权重越大，反之，权重越小。3)停止词的权重为零；4)如果一个关键词只在很少的网页中出现，通过它就容易锁定搜索目标，它的权重也就应该大，反之，如果一个词在大量网页中出现，看到它仍然不很清楚要找什么内容，因此它的权重就应该上；


  28. 地图与本地搜索的最基本的技术

  29. 有限状态机和动态规划的应用非常广泛，远远不止识别地址、导航等地图相关领域。它们在语音识别、拼写和语法纠错、拼音输入法、工业控制和生物的序列分析等领域都有着极其重要的应用；


  30. 余弦定理和新闻的分类

  31. 所谓新闻的分类，或者更广义地讲任何文本的分类，无非是要把相似的新闻放到同一类中。为了让计算机能够"算"新闻(而不是读新闻)，就要求我们首先把文字的新闻变成可以计算的一组数字，然后再设计一个算法来算出任意两篇新闻的相似性；

  32. 我们可以把一篇篇文字的新闻变成按词典顺序组织起来的数字(特征向量，向量的夹角可以来衡量组成该夹角的两个向量的相近程度，即余弦值)，计算其它相似性；


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

  34. 相比利用文本特征向量余弦的距离自底向上的分类方法，矩阵计算的奇异值分解的优点是能较快的得到结果(在实际应用中)，因为它不需要一次次的迭代。但是这种方法得到的分类结果略显粗糙，因此，它适合处理超大规模文本的粗分类。在实际工作中，可以先进行奇异值分解，得到粗分类结果，再利用计算向量余弦的方法，在粗分类结果的基础上，进行几次迭代，得到比较精确的结果；

  35. 奇异值分解的一个大问题是存储量较大，因为整个矩阵都需要存在内存里，而利用余弦定理的聚类则不需要；


  36. 信息指纹及其应用

  37. 信息指纹可以理解成将一段信息(文字、图片、音频、视频等)随机映射到一个多维二进制空间中的一个(比如一个32位的二进制数)。只要这个随机函数做得好(例如md5,sha-1)，那么不同信息对应的这些点不会重合，因此这些二进制的数字就成了原来信息所具有的独一无二的指纹；

  38. 信息指纹应用1：网络爬虫中维护的判断下一个要抓取的网页，是否已经抓取过的哈希表；因网址有可能会比较长，占用较多的磁盘空间(哈希表中存储地址的变量类型要取最长的网址长度)，可以将网址变成一个信息指纹(如md5算法,sha-1算法)，然后对比指纹；

  39. 信息指纹应用2：判定集合相同，在网页搜索时，有时需要判断两个查询用词是否完全相同(但次序可能不同)，比如"北京 中关村 星巴克"，"星巴克 北京 中关村"，循环一一做比较时，时间复杂度为O(N^2)，排序后比较的时间复杂度为O(NlogN)，都不是太好，使用哈希表时，时间复杂度为O(N)，达到了最佳，但额外使用了O(N)的空间，而且代码复杂，不完全。完美的做法是计算出这两个集合的指纹，然后直接进行比较，时间复杂度为O(N)，而且不需要额外的空间；

  40. 信息指纹应用3：判定集合是否基本相同，即在多大程度上相同；例如从两封邮件中，通过信息指纹(比如找出邮件中IDF最大的几个词，并且算出它们的信息指纹)，就能判断出两封邮件的相似程度；另外，能过从两个视频中提取出的关键帧，然后计算出关键帧的信息指纹，也可以判断出两个视频的相似程度；


  41. 信息论时代的密码学

  42. 密码原则：密码分布均匀并且统计独立；分布均匀可以使敌人无从统计，统计独立可以保证看到一个密码的明码的对照文本后，不能利用该信息，破译出其它的密码；

  43. 禁忌：密码更迭时，新老密码同时使用，因为老密码可能有部分被破解，通过已破译的部分，对照新老密码，可以很容易破解出新密码；例如罗赛塔石碑；

  44. 公开密钥的原理：(略)