程序员的数学基础课
黄申
LinkedIn资深数据科学家
立即订阅
23478 人已学习
课程目录
已完结 57 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 作为程序员,为什么你应该学好数学?
免费
导读 (1讲)
导读:程序员应该怎么学数学?
基础思想篇 (18讲)
01 | 二进制:不了解计算机的源头,你学什么编程
02 | 余数:原来取余操作本身就是个哈希函数
03 | 迭代法:不用编程语言的自带函数,你会如何计算平方根?
04 | 数学归纳法:如何用数学归纳提升代码的运行效率?
05 | 递归(上):泛化数学归纳,如何将复杂问题简单化?
06 | 递归(下):分而治之,从归并排序到MapReduce
07 | 排列:如何让计算机学会“田忌赛马”?
08 | 组合:如何让计算机安排世界杯的赛程?
09 | 动态规划(上):如何实现基于编辑距离的查询推荐?
10 | 动态规划(下):如何求得状态转移方程并进行编程实现?
11 | 树的深度优先搜索(上):如何才能高效率地查字典?
12 | 树的深度优先搜索(下):如何才能高效率地查字典?
13 | 树的广度优先搜索(上):人际关系的六度理论是真的吗?
14 | 树的广度优先搜索(下):为什么双向广度优先搜索的效率更高?
15 | 从树到图:如何让计算机学会看地图?
16 | 时间和空间复杂度(上):优化性能是否只是“纸上谈兵”?
17 | 时间和空间复杂度(下):如何使用六个法则进行复杂度分析?
18 | 总结课:数据结构、编程语句和基础算法体现了哪些数学思想?
概率统计篇 (14讲)
19 | 概率和统计:编程为什么需要概率和统计?
20 | 概率基础(上):一篇文章帮你理解随机变量、概率分布和期望值
21 | 概率基础(下):联合概率、条件概率和贝叶斯法则,这些概率公式究竟能做什么?
22 | 朴素贝叶斯:如何让计算机学会自动分类?
23 | 文本分类:如何区分特定类型的新闻?
24 | 语言模型:如何使用链式法则和马尔科夫假设简化概率模型?
25 | 马尔科夫模型:从PageRank到语音识别,背后是什么模型在支撑?
26 | 信息熵:如何通过几个问题,测出你对应的武侠人物?
27 | 决策树:信息增益、增益比率和基尼指数的运用
28 | 熵、信息增益和卡方:如何寻找关键特征?
29 | 归一化和标准化:各种特征如何综合才是最合理的?
30 | 统计意义(上):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
31 | 统计意义(下):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
32 | 概率统计篇答疑和总结:为什么会有欠拟合和过拟合?
线性代数篇 (13讲)
33 | 线性代数:线性代数到底都讲了些什么?
34 | 向量空间模型:如何让计算机理解现实事物之间的关系?
35 | 文本检索:如何让计算机处理自然语言?
36 | 文本聚类:如何过滤冗余的新闻?
37 | 矩阵(上):如何使用矩阵操作进行PageRank计算?
38 | 矩阵(下):如何使用矩阵操作进行协同过滤推荐?
39 | 线性回归(上):如何使用高斯消元求解线性方程组?
40 | 线性回归(中):如何使用最小二乘法进行直线拟合?
41 | 线性回归(下):如何使用最小二乘法进行效果验证?
42 | PCA主成分分析(上):如何利用协方差矩阵来降维?
43 | PCA主成分分析(下):为什么要计算协方差矩阵的特征值和特征向量?
44 | 奇异值分解:如何挖掘潜在的语义关系?
45 | 线性代数篇答疑和总结:矩阵乘法的几何意义是什么?
综合应用篇 (6讲)
46 | 缓存系统:如何通过哈希表和队列实现高效访问?
47 | 搜索引擎(上):如何通过倒排索引和向量空间模型,打造一个简单的搜索引擎?
48 | 搜索引擎(下):如何通过查询的分类,让电商平台的搜索结果更相关?
49 | 推荐系统(上):如何实现基于相似度的协同过滤?
50 | 推荐系统(下):如何通过SVD分析用户和物品的矩阵?
51 | 综合应用篇答疑和总结:如何进行个性化用户画像的设计?
加餐 (3讲)
数学专栏课外加餐(一) | 我们为什么需要反码和补码?
数学专栏课外加餐(二) | 位操作的三个应用实例
数学专栏课外加餐(三):程序员需要读哪些数学书?
结束语 (1讲)
结束语 | 从数学到编程,本身就是一个很长的链条
程序员的数学基础课
登录|注册

24 | 语言模型:如何使用链式法则和马尔科夫假设简化概率模型?

黄申 2019-02-08
你好,我是黄申。
之前我给你介绍了用于分类的朴素贝叶斯算法。我们讲了,朴素贝叶斯算法可以利用贝叶斯定理和变量之间的独立性,预测一篇文章属于某个分类的概率。除了朴素贝叶斯分类,概率的知识还广泛地运用在其他机器学习算法中,例如语言模型、马尔科夫模型、决策树等等。
今天我就来说说,基于概率和统计的语言模型。语言模型在不同的领域、不同的学派都有不同的定义和实现,因此为了避免歧义,我这里先说明一下,我们谈到的语言模型,都是指基于概率和统计的模型。

语言模型是什么?

在解释语言模型之前,我们先来看两个重要的概念。第一个是链式法则,第二个是马尔科夫假设及其对应的多元文法模型。为什么要先说这两个概念呢?这是因为链式法则可以把联合概率转化为条件概率,而马尔科夫假设通过变量间的独立性来减少条件概率中的随机变量,两者结合就可以大幅简化计算的复杂度。

1. 链式法则

链式法则是概率论中一个常用法则。它使用一系列条件概念率和边缘概率,来推导联合概率,我用一个公式来给你看看它的具体表现形式。
其中, 表示了 n 个随机变量。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《程序员的数学基础课》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(20)

  • 枫林火山
    黄老师,一直没想明白多元文法里的前面N个词的是否有顺序。例如: 大家好, 家大好 。 这2种情况都符合三元文法中的P(xn|xn-2,xn-1)的统计条件吗?
    推广下 P(x1,x2,x3,x4….xn) 等于 P(xn,xn-1,xn-2,….,x4,x3,x2,x1) 吗?
    百度-联合概率是指在多元的概率分布中多个随机变量分别满足各自条件的概率。我的理解联合概率的条件是可以交换顺序的。
    所以从联合概率定义的角度理解是等于的, 但是从语法模型的角度理解,语法是有顺序的,那用联合概率表示对不对。
    本节讲的语法模型是把一句话当作有序队列去对待的还是无序集合对待的? 我听您的讲解是感觉是有序的,但是我理解公式从联合概率定义又感觉公式是在说一个无序的一组条件。 没法把这两者联系起来。
    以下两组公式,我只能知道当使用一元文法时,二者时相等的。二元以上有点懵!老师能不能讲解下
    P(x1,x2,x3,x4….xn) = P(x1)*P(x2|x1)*P(x3|x1,x2)*…….*P(xn|x1,x2,x3,x4….xn-1)
    P(xn,xn-1,xn-2,….,x4,x3,x2,x1) = P(xn)*P(xn-1|xn)*P(xn-2|xn,xn-1)*…….*P(x1|xn,xn-1,……,x2)

    作者回复: 联合概率是不考虑顺序的,而N元文法一般都是要考虑一点顺序的。所谓“一点”就如你所提到的,这是一个条件概率P(xn|xn-2,xn-1),顺序是指xn-2和xn-1都是在xn的前面出现,但是我们并不关心xn-2和xn-1之间的顺序。而另一方面,我们之前已经考虑了P(xn-1|xn-2, xn-3),你可以认为xn-1和xn-2之间的关系已经在这一步考虑了。
    至于你说的最后一点,P(x1,x2,x3,x4….xn) 和P(xn,xn-1,xn-2,….,x4,x3,x2,x1)理论上应该是一致的。但是n稍微大点,我们就无法直接求了,所以要使用马尔科夫假设进行近似。而马尔科夫假在一定程度上考虑了文本出现的顺序,所以不同顺序的x1,x2...xn就会影响近似的结果,所以有P(x1,x2,x3,x4….xn)约等于近似结果a,P(xn,xn-1,xn-2,….,x4,x3,x2,x1)约等于近似结果b,a和b都是同一个理论值的近似,但是由于马尔科夫假设的原因,两个近似值不一致。

    2019-04-11
    2
    6
  • 文本分类器,对给定文本进行判断。用特征词代表该文本。应该和上篇文章分类的计算有类似之处。计算每个特征词出现在该类文章的概率。然后根据权重分类?或者根据每个词的词频。
    (我也很迷糊)那中文中有时词的顺序错乱也能表达一个意思。
    比如,密码是123和321是密码;蹦迪坟头和坟头蹦迪。
    比如(相互和互相;代替和替代)比
    如,纳税可以是一个专有名词,也可以是人名,姓纳名税。还有那遇到多音字咋办?

    作者回复: 这个问题很好,确实中文比较特殊,和拉丁文不太一样。

    我觉得你的问题是:中文里的歧义或者分词错误,是不是会影响分类?
    你说的这几种情况,我简单分为以下几种:

    分词:如果我们能知道123或321代表一个字符串,而不是单个的数字,那么就不会切分它们。再例如“相互”也不会切为“相”和“互”。当然中文分词本身不是件容易的事情,我这里提到概率语言模型,如果语料里有相关的信息,那么可以在一定程度上提升分词效果。

    同义词:如果我们能正确切分出“相互”和“互相”,那么还需要把它们关联为同义词。基本的做法是使用词典。

    语义:“纳税”的问题就更复杂一些,需要计算机理解上下文关系和语义。从统计的角度而言,那还是要看语料里“纳税”这个词哪种情况的概率更高。

    所以,自然语言处理,尤其是中文的处理,是件相当复杂也是相当有趣的事情。“词包”模型只是最基本的模型,如果我们想优化它在分类问题上的表现,需要解决好中文分词、消除歧义、同义词/近义词等问题。每个问题都是值得研究,并且可以提升的。如果每个点都能得到优化,那么最终分类的效果也会得到优化。

    总结一下,文本分类涉及的面很广,不仅受到分类算法的影响,还受到其他许多自然语言处理的影响。由于这个系列专栏的主题是数学,所以我这讲只能把概率和相关分类算的核心思想体现出来。如果你对自然语言处理有兴趣,我可以在加餐或者其他专栏中和你分享。

    2019-02-08
    3
  • qinggeouye
    思考题:

    首先,利用语言模型进行中文分词,计算句子 S=使用纯净水源浇灌的大米,属于哪种分词结果 W(“使用|纯净|水源|浇灌|的|大米”、“使用|纯净水|源|浇灌|的|大米”)的概率最大?

    然后,回到上节的文本分类,再计算 分词结果W 属于哪种分类(“大米”、“纯净水”)的概率比较大?

    作者回复: 这是一种方法👌

    2019-03-05
    2
  • 唯她命
    已经求得p(q|d) = p(k1,k2,k3...,kn|d) = p(k1|d) * p(k2|k1,d) * p(k3|k2,k1,d) ....
    那么我们怎么求得 p(k2|k1,d) 和 p(k3|k2,k1,d)呢

    作者回复: 在实际项目中,可以通过大量的语料来统计,比如文档d中,在k1后面出现k2的次数,除以k1出现的次数,用来近似P(k2|k1,d)

    2019-02-26
    2
  • acheng
    换句话说:其实我是想问,如何能更好的利用全文或者说全部训练集的语义信息?

    作者回复: 如果是词包模型,确实对语义没有太多的理解。可以加入一些基于文法甚至是领域知识的语义分析,不过这个和具体的应用有关系,可能不是语法模型本身能很好解决的。例如,评论中的情感分析(sentiment analysis),我们可以考虑表达情感的词在否定句式中的表达等等。

    2019-02-16
    2
  • Paul Shan
    思考题
    原来中文分词的是一个句子在所有语料条件下成句的最大概率分词方法。如果语料足够多,可以计数在特定文章分类下的条件概率,然后取最大条件概率的分词方法。
    2019-09-05
    1
  • OP_未央
    思考题:
    可以增加类别的先验概率,P(w1,w2...wn|C)*P(C);或者已知大米广告的条件下,通过得到的不同分词计算所属类别的概率,选择属于大米概率大的那种分词?

    作者回复: 嗯,是的。可以对不同分类构建分类器,或者增加条件概率

    2019-04-04
    1
  • 炎发灼眼
    老师你好,文中P(q|d)通过链式法则推导的公式没看懂,联合概率的推导可以看懂,这种带了d的条件概率的推导没有看懂,望老师能给予解释。

    作者回复: 你是指p(q|d) = p(k1,k2,k3...,kn|d) = p(k1|d) * p(k2|k1,d) * p(k3|k2,k1,d)?

    先看链式法则,p(k1,k2,k3,...,kn|d) = p(k1|d) * p(k2|k1,d) * p(k3|k2,k1,d) * ... * p(kn|kn-1,kn-2,...,k2,k1,d),注意这里公式的成立是基于贝叶斯法则的,你可以用贝叶斯法则验证。

    然后,通过马尔科夫假设,当前词只和前若干词相关,这里假设前两个,那么上式子可以简化为
    p(q|d) = p(k1,k2,k3...,kn|d) = p(k1|d) * p(k2|k1,d) * p(k3|k2,k1,d) * p(k4|k3,k2,d) * ... * p(kn|kn-1,kn-2,d)

    2019-10-22
  • Paul Shan
    中文分词就是选用不同的分词,然后计算每个分词成句的概率大小来对分词作优劣判断。
    2019-09-05
  • Paul Shan
    信息检索是建立文章和查询的条件概率来判断查询和文章的紧密关系,这里查询当中一句句子来处理,然后用近似方法计算其在文中的概率,请问老师,查询里每个关键词的前后顺序和相邻都没什么关系,但是马尔可夫假设用到了前后和相邻关系,这样会不会造成较大误差?

    作者回复: 查询里的关键词有时候是存在一定的先后顺序,比如“相机镜头”和“带镜头的相机”,不过确实很多查询里的关键词都可以用词袋模型处理。当然,要精细化的提升查询的准确率,词袋就不够了。

    2019-09-05
  • Paul Shan
    链式法则和马尔可夫假设可以大大简化计算联合概率的复杂度。链式法则在数学上是等价。马尔可夫假设是不是基于这样的事实,文章中的单词和该单词前n个单词的关系较为紧密,但是和其他单词没什么关系,从另一个角度看,一个单词和紧接着的单词也有紧密关系,但这一层关系在马尔可夫假设里由后面的单词处理,请问老师是不是这样,多谢。

    作者回复: 是的,链式法则是等价的,马尔科夫假设用于简化

    2019-09-05
  • 楼外楼
    看完第二遍才搞清楚 P(x1,x2,...Xn)= P(x1)*P(x2|x1)*P(x3|x2)... 前提是: 各个条件都是独立的--参考一元文法;第二前提是: P(xn|x1,x2,...) = P(xn|xn-1,xn-2)
    2019-08-15
  • 凝神寂照
    老师您好,对于信息检索部分,计算 P(d|q)=P(q|d)P(d)/P(q)来对不同文档进行排序,P(q)是固定的我能理解,但是对于不同的文档P(d)应该是不同的吧,您为什么说P(d)是固定的呢?

    作者回复: 这里是假设每篇文章都出现了1/N次,N表示文章总数

    2019-07-20
  • 李斌
    查询文档相关性的部分,elasticsearch 里常用 TF-IDF 以及最新的 BM25,两者都用到了 IDF 信息,但是感觉基于概率的方法没有用到 IDF 的信息啊

    作者回复: 一般基于概率的不用TF-IDF,这主要是因为概率论有自己的理论体系,概率的估算是使用最大似然,而非TF-IDF。

    2019-07-14
  • jennbetty
    老师我不明白中文分词求出的三元文法P(s|D)是如何求出argmax(P(Wi|D))的呢?比如说P(w2|D), P(w3|D)是怎么求出来的呢

    作者回复: 你的意思是说,如何在三元文法的情况下,求解p(s|D)?基本还是一致的,只是把P(wn|D)改为P(wn|wn-1, wn-2, D)

    2019-06-02
  • 枫林火山
    明白这个顺序在哪里体现了,谢谢老师的耐心讲解👍🏻

    作者回复: 应该的,你这个问题很好,对其他人也有启发

    2019-04-12
  • 唯她命
    老师啊,中文分词,同一个句子,我们是不是把每种可能得分词 的ps都算出来啊,然后所有的ps求最大值,也就是这种分词的概率最大,然后我们就选择这种分词方法

    作者回复: 是的👍

    2019-02-27
  • 唯她命
    老师你好,p(K2 | k1,d) 指的是K2 | k1 和 d的联合概率
    还是指的是 在满足k1和d的条件下,出现k2的概率?

    作者回复: 是第二种,在满足k1和d的条件下,出现k2的概率

    2019-02-26
  • 唯她命
    老师,$P(w_{1}, w_{2}, …, w_{n})$ 要在集合中找到一模一样的句子,基本是不可能的

    不一定要找到一模一样的句子吧 例如abc 难道cab 这种打乱顺序的不行吗?

    作者回复: 如果是一元文法,词包模型,确实不需要一模一样。

    2019-02-26
  • acheng
    这篇文章和上篇文章中介绍的分类基本都是在假定文章中的词语相互独立的情况下进行的,虽然马尔科夫模型用到前面词的概率,这可以说是结合了部分上下文之间的语义关系,只使用了和前面词的语义关系,对文本分类其实效果已经很好,尤其是在语料充足的情况下可以使用机器学习的方法让分类模型自迭代优化,目前很多机器翻译就是这么干的。但是我想问下老师,针对语料不是很充足的文本集,如何使用全篇文章的语义(不只是前面词的上下文关系)来设计一个文本分类器?

    作者回复: 我想你所说的是针对分类问题对吧?那么语料不充足,是指只有少数的标注数据(文章),是吧?如果是这样,一种做法是增大ngram里面的n,因为标注数据不多,增加n不会增加太多的存储空间。另外,也可以使用少量数据训练得到的分类器,对新的数据进行分类,然后获得一些分类结果后,人工再进行复查,把正确的结果再次纳入训练数据。

    2019-02-15
收起评论
20
返回
顶部