《数学之美》摘要与心得

注:【】部分为笔者心得,非原文摘抄。

  • 假定文本中的每个词W_i和前面N-1个词有关,而与更前面的词无关,这样当前词W_i的概率只取决于当前N-1个词P(W_{i-N+1},W_{i-N+2},…,W_{i-1})。因此P(W_i|W_1,W_2,…,W_{i-1})=P(W_i|W_{i-N+1},W_{i-N+2},…,W_{i-1})称为N-1阶马尔科夫假设,对应的语言模型称为N元模型(N-Gram Model)。
  • 在实际中应用最多的N=3的三元模型。
  • N元模型的大小(或者说空间复杂度)几乎是N的指数函数,即O(|V|^{N-1})。当N从1到2,再从2到3时,模型的效果上升显著。而当模型从3到4时,效果的提升就不是很显著了,而资源的耗费却增加得非常快。
  • Google的罗塞塔翻译系统和语音搜索系统,使用的是四元模型。
  • 马尔科夫假设的局限性:在自然语言中,上下文之间的相关性可能跨度非常大。
  • 对于没有看见的事件,不能认为它发生的概率就是零,(应该)从概率的总量(Probability Mass)中,分配一个很小的比例给这些没有看见的事件。
  • 在实际的自然语言处理中,一般对出现次数超过某个阈值的词,频率不下调,只对出现次数低于这个阈值的词,频率才下调,下调得到的频率总和给未出现的词。
    • 阈值一般在8-10左右。
  • 如果训练语料和模型应用的领域相脱节,那么模型的效果往往会大打折扣。
  • 在训练数据和应用数据一致并且训练量足够大的情况下,训练语料的噪音高低也会对模型的效果产生一定的影响。
  • 马尔科夫假设:随机过程中各个状态S_t的概率分布,只与它的前一个状态S_{t-1}有关,即P(S_t|S_1,S_2,S_3,…,S_{t-1})=P(S_t|S_{t-1})
    • 符合这个假设的随机过程则称为马尔科夫过程,也称为马尔科夫链。
  • 隐含马尔科夫模型是马尔科夫链的一个扩展:任一时刻t的状态S_t是不可见的。观察者没法通过观察得到一个状态序列S_1,S_2,S_3,…,S_T来推测转移概率等参数。隐含马尔科夫模型在每个时刻t会输出一个符号O_t,而且O_tS_t相关且仅与S_t相关。这个被称为独立输出假设。
  • 从前一个状态S_{t-1}进入当前状态S_t的概率P(S_t|S_{t-1})称为转移概率(Transition Probability),状态S_t产生相应输出符号O_t的概率P(O_t|S_t)称为生成概率(Generation Probability)。
  • 数据是人工标注的,称为有监督的训练方法(Supervised Training),前提是需要大量人工标注的数据。
  • 信息熵(Entropy)一般用符号H表示,单位是比特。
  • 对于任意一个随机变量X,它的熵定义如下:
    H(X)=-\sum_{x \in X}P(x)logP(x)
  • 变量的不确定性越大,熵也就越大,要把它搞清楚,所需信息量也就越大。
  • 几乎所有的自然语言处理、信息与信号处理的应用都是一个消除不确定性的过程。
  • 信息的作用在于消除不确定性。
  • 两个事件相关性的量化度量,就是在了解了其中一个Y的前提下,对消除另一个X不确定性所提供的信息量。互信息是一个去只在0min(H(X), H(Y))之间的函数:
    I(X;Y)=H(X)-H(X|Y)
  • 互信息被广泛用于度量一些语言现象的相关性。
  • 一个人要想在自己的领域做到世界一流,他的周围必须有非常多的一流人物。
  • 技术分为术和道两种,具体的做事方法是术,做事的原理和原则是道。追求术的人一辈子工作很辛苦。
  • 对于一个特定的查询,搜索结果的排名取决于两组信息:关于网页的质量信息,以及这个查询与每个网页的相关性信息。
  • PageRank的核心思想:如果一个网页被很多其它网页所链接,说明它受到普遍的承认和信赖,那么它的排名就高。
  • 给定一个查询,有关网页的综合排名大致由相关性和网页排名的乘积决定。
  • 采用动态规划可以大大降低最短路径的计算复杂度。
  • 语音识别解码器基本上是基于有限状态机的原理。
  • 有限状态传感器(Finite State Transducer)的特殊性在于,有限状态机中的每个状态由输入和输出符号定义。
  • 在语音识别中,每个被识别的句子都可以用一个WFST(加权的有限状态传感器,Weighted Finite State Transducer)来表示,其中概率最大的那条路径就是这个句子的识别结果。
  • 在计算机科学领域,一个好的算法应该向AK-47那样:简单、有效、可靠性好而且容易读懂(或者说易操作),而不应该是故弄玄虚。
  • 在工程上,简单实用的方法最好。
  • 先帮助用户解决80%的问题,再慢慢解决剩下的20%问题。
  • 相比利用文本特征向量余弦的距离自底向上的分类方法,奇异值分解的优点是能较快地得到结果,因为它不需要一次次地迭代。但是用这种方法得到的分类结果略显粗糙,因此,它适合处理超大规模文本的粗分类。在实际应用中,可以先进行奇异值分解,得到粗分类结果,再利用计算向量余弦的方法,进行几次迭代,得到比较精确的结果。
  • 加密函数不应该通过几个自变量和函数值就能推出函数本身。
  • 从广义上讲,只要噪音不是完全随机并且前后有相关性,就可以检测到并且消除。
  • 最大熵原理指出,对一个随机事件的概率分布进行预测时,我们的预测应当满足全部已知的条件,而对未知的情况不要做任何主观假设。
  • 香农第一定律:对于一个信息,任何编码的长度都不小于它的信息熵。
  • 把各种特征综合在一起最好的办法是采用最大熵模型。
  • 好办法在形式上应该是简单的。
  • 贝叶斯网络:每一个状态只跟与其直接相连的状态有关,而跟与它间接相连的状态没有直接关系。
  • 由于每条弧都有一个可信度(即权重),贝叶斯网络也被称作信念网络(Belief Networks)。
  • 贝叶斯网络不受马尔科夫链的链状结构约束,因此可以更准确地描述事件之间的关联性。
  • 条件随机场是无向图,而贝叶斯网络是有向图。
  • 扩频传输(Spread-Spectrum Transimission)和固定频率的传输相比,有三点优势:
    1. 抗干扰能力极强;
    2. 信号很难被截获(能量非常低);
    3. 利用带宽更充分。
  • 频分多址是对频率进行切分,每一路通信使用一个不同的频率。相邻频率会互相干扰,因此每个信道要有足够的带宽。
  • 时分多址是将同一频带按时间分成很多份,每个人的(语音)通信数据在压缩后只占用这个频带传输的1\over N时间,这样同一个频带可以被多个人同时使用。
  • 码分多址是指接收者在接到不同信号时,通过密码过滤掉自己无法解码的信号,留下和自己密码对应的信号即可。
  • 训练最大熵模型的IIS方法(Improved Iterative Scaling,改进的迭代尺度法)可以直接用于训练逻辑回归函数的参数。
  • 分治算法的基本原理是:将一个复杂的问题,分成若干个简单的子问题进行解决。然后,对子问题的结果进行合并,得到原有问题的解。
  • 人工神经网络是一种特殊的有向图,其特殊性可以概括为:
    1. 所有节点都是分层的,每一层节点可以通过有向弧指向上一层节点,但是同一层节点之间没有弧互相连接,而且每一个节点不能越过一层连接到上上层的节点上。理论上,人工神经网络的层数可以是任意的。只是在实际应用中一般不会有人设计超过5层的网络,因为网络的层数越多,计算就越复杂;
    2. 每一条弧上有一个值(称为权重或者权值),根据这些值,可以算出它们所指节点的值。
  • 人工神经网络擅长模式分类。
  • 人工神经网络节点(即神经元)的取值是用一个非线性函数计算出来的,这个函数被称为神经元函数。
  • 在人工神经网络中,规定神经元函数只能对输入变量线性组合后的结果进行一次非线性变换。
  • 没有数据支持的决策常常不准确,而且个别成功案例的影响在人们心中会被放大,而风险则被缩小。
  • 如果一个散户投资人能真正做到“用数据说话”,只需奉行一条投资决策,那就是买指数基金。
  • 统计样本数量不充分,则统计数字毫无意义。
  • 除了要求数据量必须足够多,统计还要求采样的数据具有代表性。
  • 在搜索用到的诸多种数据中,最重要的数据有两类,即网页本身的数据和用户点击的数据。
  • 大数据更重要的在于它的多维度和完备性,有了这两点才能将原本看似无关的事件联系起来,恢复出对事物全方位完整的描述。
  • 只有当一些随机事件的组合一同出现了很多次以后,才能得到有意义的统计规律。
  • 无论在什么领域,从事什么样的工作,谁懂得数据的重要性,谁会在工作中善用数据,就更有可能获得成功。
  • 如果两个计算机算法在大O概念下相同,只相差一个常数,我们则认为它们的计算复杂度相同。
  • 如果一个算法的计算量不超过N的多项式函数(Polynomial Function),那么称这个算法是多项式函数复杂度的。如果一个问题存在一个多项式复杂度的算法,这个问题称为P问题。这类问题被认为是计算机可以“有效”解决的。
  • 如果一个问题,我们能够在多项式复杂度的时间里证实一个答案的正确与否,则不论目前这个问题是否能找到多项式复杂度的算法,都称这个问题为NP问题。
  • P问题是NP问题的一个特殊的子集。
  • NPC(NP-Complete,NP完备)问题是NP问题中最难的问题,因为如果任何一个NPC问题找到了多项式算法,那么所有的NP问题都可以用这个算法解决了,也即NP=P
  • NP-Hard问题:计算复杂度至少是NP-Complete甚至更大的问题。
  • 数学在计算机科学中的一个重要作用,就是找到计算复杂度尽可能低的解。同时,对于那些NP-Complete或者NP-Hard的问题,找到近似解。

《数学之美》(第二版)