杨慧宇作者

掌握动态规划,助你成为优秀的算法工程师

1.导论

相信很多同学已经在为今年的校招做准备了,随着AI的火热,越来越多的同学涌入了算法的行当之中。那去年校招的算法岗是有多火热?在知乎上看到这么一条帖子,先不说内容哈,足足400w+的阅读量啊。
0 (1)
不光是计算机或软件专业的学生,很多电子,通信,自动化等相关专业的同学也吸引了进来。当然,这应该是件好事。但是相当一部分同学,在学习的过程中,尤其是刚入门的时候,可能会有这样一个疑问:算法工程师的算法,为什么不是指《算法导论》中的算法(以下称为经典算法,用以区分),而是指机器学习里的算法。都叫算法(Algorithm),但好像不是一回事啊,两者有什么关系,又有什么区别呢?
本文试图通过动态规划这一经典算法中的重要内容,同时又在机器学习算法中有着广泛的应用,来简单探讨一下这两种“算法”。

2.动态规划

首先,动态规划(Dynamic Programming)是《算法导论》中的重要章节,同时也是在机器学习算法中有着非常重要应用的一种优化算法。可以说是,无论是否是算法工程师都应该掌握的一种算法。再功利一点说,动态规划也是诸多面试官特别喜欢考的一种题型,下面就带大家稍微温故一下。

按照教材[1]的介绍,动态规划通常需要按如下4个步骤来进行设计:
  1. 刻画一个最优解的结构特征。
  2. 递归地定义最优解的值。
  3. 计算最优解的值,通常采用自底向上的方法。
  4. 利用计算出信息构造一个最优解。
简单点说,动态规划算法的核心就是大问题拆成重复的小问题,同时记住已经解决了的小问题的解。那如果你去网上搜搞ACM或者OI大神的说法,他们都会说动态规划是一个框,是一种解决问题的思想,而不是某种具体的算法。下面我们详细来看看,时髦的机器学习是怎么往动态规划这个框里填的。

2.1 编辑距离

说到编辑距离(Edit distance),大家可能都比较熟悉。在自然语言处理(Natural Language Processing,又NLP)中,编辑距离是计算文本相似度的一种基本距离计算方式。简单来说,就是只能通过替换,删除,插入操作,将一串字符串变为另一串字符串的操作数。而求最小编辑距离的过程,就是一个典型的动态规划的过程。
如果计算两个字符串的编辑距离,我们可以看做是父问题,那他的子问题自然就是如何求更小字符串之间的编辑距离。那上面提到,动态规划不仅要将父问题拆分成子问题,更要记下子问题的解,以达到节省空间和时间的效果。
下图可以看出,这个D矩阵,就是我们用来存储这个子问题解的空间,假设两个字符串的长度分别为mn。而D(i, j)如图所示,则是我们定义的最优解的结构特征,实际表示的就是长度为i和长度为j的两个子序列之间的最小编辑距离,我们把它从左至右,从下到上填到每个格子里,一直到矩阵的右上角,就可以得到我们要的最小编辑距离。那么最终我们的空间复杂度为O(mn),而时间复杂度同样为O(mn),相比采用分治的思想递归地进行求解还是要快很多。(这里篇幅有限,就不赘述代码了,有兴趣的同学可以自行网上搜索)
https://web.stanford.edu/class/cs124/lec/med.pdf

2.2 动态时间规整

说完NLP里的相似度计算,咱们再来看看语音识别里有没有类似的算法用到动态规划呢?答案是肯定的。这个算法就叫动态时间规整(Dynamic time warping),简称DTW,一听名字是不是感觉就很动态规划。DTW算法是传统语音识别中的重要方法,起初是用于孤立词的语音识别,判断两段语音是否为同一个单词。实际上,只要是时间序列,如下图[2],都可以用来计算相似度,不局限于语音识别当中,例如股市的交易策略,手势识别等等场景都有应用。
0 (1)
在语音信号中,有一个很大的问题就是,信号长度并不相等,即使是同一个人说同一个单词,也会有语速上的差别。那这个时候基于欧几里得距离(Euclidean Distance)的方法就不奏效了,但是两个时间序列形状上又非常的相似,于是我们就希望可以通过某种对齐的方式来衡量这两个时间序列的相似性。如上图所示,箭头代表了两个时间序列中的相似点。我们用所有相似点之间的距离和来表示这种相似度,称之为规整路径距离。
0 (2)
大家看到这个“棋盘”好像和我们上面讲到的编辑距离中的D矩阵很像。没错,假设n为序列A的长度,m为序列B的长度,D(m, n)就是上面这两个序列的规则路径距离。至于D(m, n)怎么求?又到了我们的动态规划发挥威力的时候。还是像求最小编辑距离一样,D(i, j)如下式所求,并且由左到右,由下到上填入D矩阵中,最终求得的右上角的值就是我们的规整路径距离。时间复杂度依然为O(mn)
0 (2)
说到这里,好像动态规划不就是画个矩阵,按照D(i, j)的计算方法填满矩阵,得到右上角的最终解。嗯,好像也有点道理。那我们接下来继续看看,这样说对不对。

2.3 维特比算法

如果说前面两种算法和机器学习只能算沾边的话,那我们现在要说的维特比算法(Viterbi Algorithm)可以说是动态规划机器学习当中的典范了,尤其如果是做自然语言处理方向的话,维特比算法更是不可不知,哪怕在如今deep learning当道的时代。在自然语言处理中,像分词、词性标注命名实体识别、输入法等等任务中都有非常重要的应用。
除了前面介绍的计算两个序列之间的距离以外,动态规划还有一个重要的应用场景,就是计算有向无环图(DAG)中两个节点间的最短路径,维特比算法就是针对篱笆网络(Lattice Network)这一特殊的有向无环图而提出的。
0 (4)
如上图所示,这是一个部分的篱笆网络,中间我们假设有N列,每列有4个节点,节点之间的权重我们暂时忽略。这个时候,网络的最左边有一个节点为S,最右端有一个节点为E。如果我想求SE之间的最短路径,理所当然,我们如果穷举出所有的路径进行比较,也就是4N条路径,自然可以得到结果,但如果层数很多或者每层的节点数很多的时候,这种方法就显得不够友好了。
既然穷举法太过暴力,自然我们想试试能不能用动态规划来解决。首先,篱笆网络有这么一个特点,就是假设我们从第一列走到最后一列,我们一定会经过其中的第i时刻的某个节点。这个当然是显而易见的,但给我们带来了一个好处,那就是当我们计算最终的最短路径时,假设第i列有k个节点,如果我们已经计算了从开头到第i列所有k个节点的最短路径,那最终的最短路径一定是经过其中之一。第二,如果说最短路径P经过某个节点xij,那么从起始节点S到节点xij的这段子路径Q,一定是从起始节点Sxij的最短路径,否则总路径P也不再是最短路径,这就自相矛盾了。
有了这两个特性,终于可以试试动态规划了。同样我们从最左边的S节点出发,到第1列的4个节点,因为各只有一段距离,那自然这4个距离d(S, x1i)为S节点到这4个节点的最短距离。当我们走到第2列时,根据之前的特性,一定会经过第1列的某个节点。此时的S节点到第2列某个节点的距离则为d(S, x2j)=d(S, x1i) + d(x1i, x2j)。而第1列有4个节点,所以d(S, x2j)应该是取4个距离中的最小值,当然在这一过程中,我们计算了4次,对于第2列的每个节点,我们都去进行如上的计算。所以在从第1列走到第2列的过程中,我们计算了4×4次,更关键的是我们把d(S, x2j)都要保存下来,作为我们下一次计算的基础。
而这个保存中间结果的过程,很明显地体现出了前文所述的动态规划的特点。接下来,我们继续走到第3列,同样的,S节点到第3列某个节点的距离为d(S, x3k)=d(S, x2j) + d(x2j, x3k)。这个时候我们发现,等式右边的第一项,可以直接取我们刚刚保存的中间结果。对于d(S, x3k),我们依然是计算4次,取最小值保存下来。同样,需要遍历第3列的4个节点,所以又是4×4次计算。也就是说,每往前走1列,我们就计算了4×4次。以此类推,到最右边的节点E的时候,我们需要计算42次,相比于穷举法的4N条路径,这个效率已经是非常大的进步,把指数级的复杂度降低到了多项式级别!

2.4 CYK算法

这个CYK算法大家可能会有点陌生,全名为Cocke–Younger–Kasami算法,是以三位作者的姓名共同命名的。这个算法其实是句法分析方向的一个经典算法,因为提出的时间是在基于规则的年代,所以即使是做NLP的同行,依然有很多同学并不了解。所以这里给大家多交代一些背景知识。
首先,CYK算法是基于乔姆斯基(Chomsky)范式的上下文无关语法(Context Free Grammar)。感觉越解释概念越多了哈。简单点说,乔姆斯基范式有两种形式。
0 (9)
这里,ABC都是非终结符,就是像名词短语(NP),动词短语(VP)等等,x是终结符,比如单词就是终结符。对于A这个非终结符,要么拆分成更小的2个非终结符,要么就到此为止,右边是一个单词。例如:”吃药“这个动词短语,就可以按下面的方式进行句法分析。
0 (10)
好了,介绍完了背景知识,我们的任务就是给定一个句法规则的集合,对于任意一个句子,将它按照这个句法规则集合进行解析。下图就是我们的一个句法解析树,也就是最终的一个结果。
0 (4)
对于一次解析来说,如果尝试去解析出所有的结果,那将是指数级的复杂度,而CYK算法就是利用动态规划的思想将复杂度降低到了多项式级。假设我们的句子的单词数为n,我们先画一个如下图的下三角矩阵,横坐标为位置i,纵坐标为跨度j
0 (3)
CYK算法过程如下:
0 (3)
http://ccl.pku.edu.cn/doubtfire/Course/Computational%20Linguistics/contents/CYK_parsing.pdf

其中最关键的就是步骤2中的最内层循环,对于一个跨度内所有分割点k。简单点说,就是在给定了位置和跨度的一个短语中,不断调整中间的分割点位置,使得分割点两边的短语子串能够符合给定的句法规则。当子串符合句法规则时,把对应的结果记录下来,并为后续的解析所用,这就体现了动态规划思想的核心!

2.5 分词

上面我们介绍过维特比算法,在分词任务中有重要的应用,但现在我们又要来提分词了,那这里的动态规划和维特比有什么不一样呢。首先,目前的分词的主流算法里有这么两种,一种是基于字的模型分词算法,还有一种则是基于词典的分词方法。前者,主要有基于隐马尔可夫(HMM)的生成式模型、基于条件随机场(CRF)的判别式模型以及基于神经网络的分词算法,在这些算法的解码部分,都可以使用维特比算法进行解码。那这节要说的动态规划则是基于词典的分词算法里用到的。
基于词典的分词算法是如何工作的呢?举一个简单的例子,"我来到达观数据"。首先,我们根据词典将句子进行简单的匹配,将句中匹配到的词典词和所有的单字组合起来,作为节点,构造成一个分词的词图,如下图所示(边的权重假设都为1)。那这个图里从S节点到E节点的每条路径,都代表这一种分词的结果。我们希望正确的分词结果,理应是一条概率最大的的路径,这样才能把一个语言学的问题转化成一个数学的问题,从而让计算机可以辅助我们得到正确的分词结果。
0 (5)
因为句子是顺序的,所以这个词图表现为一个有向无环图。还记得前面讲到的维特比算法是针对特殊的有向无环图来计算最短路径,这里的词图就显得更为一般些。如何求得有向无环图的最短路径呢,这个时候,我们需要先对词图进行拓扑排序,然后再利用动态规划求排序后的词图最大概率路径。拓扑排序的结果如下图:
0 (6)
有了拓扑排序的结果,我们就可以动态规划了。上面我们讲Viterbi算法的时候,提到这么一个性质,如果最终的最短路径P经过某个节点i,那么经过这个节点的子路径Q一定是起始节点S到节点i的最短路径,否则最短路径P一定有比它更短的路径存在。在这里,我们是求最大概率路径,其实原理是一样的。对于到最终节点E的路径Route(E),有:
0 (7)
实际上,我们可以一直写下去,而这些子路径就是动态规划中的最优子结构,我们只需要再求解这些子结构中的最优解即可。相比于,列举出所有的分词路径,这种计算方法是要快上很多。在计算最大概率的过程中,有不少小trick。期待后续的达观技术分享为大家详细介绍。

2.6 强化学习策略迭代

说到强化学习,这里不得不首先引用一下Sutton在《Reinforcement Learning: An Introduction》关于动态规划的一些表述。
DP provides an essential foundation for the understanding of the methods presented in the rest of this book. In fact, all of these methods can be viewed as attempts to achieve much the same effect as DP, only with less computation and without assuming a perfect model of the environment.
虽然动态规划在实际的强化学习中,有诸多的限制,但动态规划所具有的理论基础是强化学习必不可少的,可见动态规划之于强化学习的重要意义!
强化学习和大家熟悉的机器学习有着很大的不同,它没有用到标注数据进行supervise,而且当前的动作可能会影响到后续的结果。既然是动作,肯定会考虑到很多因素。那么在强化学习里,我们需要考虑哪些变量呢?首先肯定是回报了,这里用R来表示,不同的回报决定了不同的动作。回报又分为长期的和短期的,就好比做基础算法研究,短期看没什么回报,但长期来说就是技术的护城河。我们通过衰减系数𝛾来表示,0≤𝛾<1。除此以外,我们还要看当前所处的状态S来决定所做的动作。有了状态的集合,那自然要考虑状态之间的转移关系,就是我们的P,状态转移矩阵,但因为对于很多实际问题,状态实在太多,所以每个状态只能考虑前一个状态的相关情况,这样就大大简化了问题的复杂度,这种性质我们也叫马尔科夫性。最后,加上我们的一系列动作A,就有了马尔科夫决策过程(Markov Decision Process, MDP)。
0 (5)
http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/MDP.pdf
好了,现在有了这些基本要素了,下面要用这些要素做什么呢?比如机器学习里,我们希望是最小化损失函数。而在强化学习里,我们则是希望最大化的累积回报,比如下棋的时候,只要最终赢了即可,而不是要每步都要吃掉对方一些棋子。这时候,我们就先定义一下这个累积回报,假设从t时刻开始到最终时刻T,并且加上之前提到的衰减系数𝛾,则有:
0 (8)
既然这个G~t~是从t时刻到最终状态的累积回报,那就不光是一条路径的累积,而是所有的路径的总和,当状态过多的时候,我们就没法计算。这个时候需要引入一个状态值函数,作为从某状态开始的回报总和的期望。
0 (11)
这个状态值函数就是用来衡量某一个状态的好坏。除了我们上面提到的几个要素以外,我们在某个状态执行什么动作,并不是固定的,那就需要引入新的概念策略𝜋,作为动作关于状态的分布。则上式就变为:
0 (12)
问题又来了,这个期望其实也不太好算,因为其中一个状态的价值函数需要计算后续所有状态的回报。既然是马尔科夫决策过程,那自然会想到用迭代的思想去计算。得到其递归的形式Bellman方程,如下式(详细推导过程见7)
0 (13)
这样,在给定策略的情况下,我们就可以迭代地去求每一个状态的值函数了。从这个更新公式,也可以看出,强化学习里的动态规划将围绕状态值函数的更新这个最优子结构而做文章。
对于从v1到最终的v*的每次迭代vk,我们利用上式对值函数进行更新,直到收敛V*(证明略)。这一步就叫做策略评估。这时候,我们可以对于取得最大的动作值函数q而得到的新策略,对新的策略进行策略评估步骤。直到我们的策略不再变化,此时得到的策略即为最优策略。

3.总结

一下子说了那么多涉及到动态规划机器学习算法,相信读者朋友们还可以列举出更多(欢迎评论区留言)。我们在动态规划这个框里填了那么多机器学习算法,而机器学习算法也非常依赖动态规划的高效率,可谓是你中有我,我中有你。
从上面举的很多例子大家也可以看到,动态规划更侧重于对问题求解的优化,比如求最短距离,实际上是可以通过暴力方法进行求解的,而动态规划则是提高了求解的效率。但机器学习算法可不仅仅是对问题的求解进行优化,它要解决的问题往往没有精确解,同时也没法通过穷举等暴力方法进行求解。需要对问题进行清晰地定义并建模,重点在于学习的过程,基于对训练数据的拟合来预测新的样本。
而说完动态规划,大家很容易又联想贪心算法,同样也是经典算法中的一个重要的优化方法。比如word2vec中的霍夫曼树(Huffman Tree),比如seq2seq中需要用到的集束搜索(Beam Search),都是借鉴了贪心算法的思想。前面我们提到了求最短路径问题虽然是动态规划,这实际上又涉及到经典算法中图论里的内容,类似的还有一系列的概率图模型(Probabilistic Graphical Model)。事实上,还有很多机器学习算法运用到了经典算法里的内容,这里就不一一列举了。
总之,对于一名优秀的算法工程师来说,经典算法的掌握必不可少,对于机器学习算法的理解也有很大的帮助。希望大家能够认真掌握,"举一反三",在接下来的秋招中好好发挥。

参考资料

1.Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. "算法导论." 第 2 版 机械工业出版社 (2006).
2.Salvador, Stan, and Philip Chan. "FastDTW: Toward Accurate Dynamic Time Warping in Linear Time and Space."
3.吴军. 数学之美. 人民邮电出版社, 2012.
4.宗成庆. 统计自然语言处理. 清华大学出版社, 2013
5.黄海安. https://www.zybuluo.com/Team/note/1123968
6.Wiering, Marco, and Martijn Van Otterlo. "强化学习." 机械工业出版社.
7.http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/MDP.pdf

关于作者

杨慧宇:观数据NLP技术专家,负责达观数据底层NLP算法效果的优化,以及财务审核相关产品的研发工作。
达观数据
达观数据

达观数据是一家专注于文本智能处理技术的国家高新技术企业,获得2018年度中国人工智能领域最高奖项 “吴文俊人工智能科技奖”,也是本年度上海市唯一获奖企业。达观数据利用先进的自然语言理解、自然语言生成、知识图谱等技术,为大型企业和政府客户提供文本自动抽取、审核、纠错、搜索、推荐、写作等智能软件系统,让计算机代替人工完成业务流程自动化,大幅度提高企业效率。

入门维特比算法策略迭代强化学习机器学习动态规划
2
相关数据
达观数据机构

达观数据成立于2015年,是中国领先的文本智能处理企业,利用先进的文字语义自动分析技术,为企业、政府等各大机构提供文本自动抽取、审核、纠错、搜索、推荐、写作等智能软件系统,让计算机代替人工实现业务流程自动化,大幅度提高运营效率。 达观数据为企业提供完善的文本挖掘、知识图谱、搜索引擎和个性化推荐等大数据服务,是国内唯一一家将自动语义分析技术应用于企业数据化运营的人工智能公司。

http://www.datagrand.com/
统计自然语言处理技术

基于概率统计领域的理论进行自然语言处理, see NLP

动态规划技术

动态规划(也称为动态优化),是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划将复杂的问题分解成一系列相对简单的子问题,只解决一次子问题并存储它的解决方案(solution),下一次遇到同样的子问题时无需重新计算它的解决方案,而是简单地查找先前计算的解决方案,从而节省计算时间。动态规划适用于有最优子结构(Optimal Substructure)和重叠子问题(Overlapping Subproblems)性质的问题。

策略迭代技术

策略迭代算法直接操纵策略,而不是通过最优值函数间接找到策略。

权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

非终结符技术

终结符和非终结符在计算机科学和语言学的领域是用来指定推导规则的元素。在某个形式语法之中,终结符和非终结符是两个不交的集合。

维特比算法技术

维特比算法(英语:Viterbi algorithm)是一种动态规划算法。它用于寻找最有可能产生观测事件序列的维特比路径——隐含状态序列,特别是在马尔可夫信息源上下文和隐马尔可夫模型中。 术语“维特比路径”和“维特比算法”也被用于寻找观察结果最有可能解释相关的动态规划算法。例如在统计句法分析中动态规划算法可以被用于发现最可能的上下文无关的派生(解析)的字符串,有时被称为“维特比分析”。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

时间复杂度技术

在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。例如,如果一个算法对于任何大小为 n (必须比 n0 大)的输入,它至多需要 5n3 + 3n 的时间运行完毕,那么它的渐近时间复杂度是 O(n3)。

收敛技术

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

有向无环图技术

在图论中,如果一个有向图从任意顶点出发无法经过若干条边回到该点,则这个图是一个有向无环图(DAG图)。 因为有向图中一个点经过两种路线到达另一个点未必形成环,因此有向无环图未必能转化成树,但任何有向树均为有向无环图。

损失函数技术

在数学优化,统计学,计量经济学,决策理论,机器学习和计算神经科学等领域,损失函数或成本函数是将一或多个变量的一个事件或值映射为可以直观地表示某种与之相关“成本”的实数的函数。

词性标注技术

词性标注是指为分词结果中的每个单词标注一个正确的词性的程序,也即确定每个词是名词、动词、形容词或其他词性的过程。

解析树技术

解析树是一个内部结构,由编译器或解释器在解析一些语言结构时创建,解析也被称为“语法分析”。

神经网络技术

(人工)神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型,那时候研究者构想了「感知器(perceptron)」的想法。这一领域的研究者通常被称为「联结主义者(Connectionist)」,因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型,它们都是前馈神经网络:卷积神经网络(CNN)和循环神经网络(RNN),其中 RNN 又包含长短期记忆(LSTM)、门控循环单元(GRU)等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习,但也有一些为无监督学习设计的变体,比如自动编码器和生成对抗网络(GAN)。

欧几里得距离技术

在数学中,欧几里得距离或欧几里得度量是欧几里得空间中两点间“普通”(即直线)距离。 使用这个距离,欧氏空间成为度量空间。

命名实体识别技术

命名实体识别(NER)是信息提取(Information Extraction)的一个子任务,主要涉及如何从文本中提取命名实体并将其分类至事先划定好的类别,如在招聘信息中提取具体招聘公司、岗位和工作地点的信息,并将其分别归纳至公司、岗位和地点的类别下。命名实体识别往往先将整句拆解为词语并对每个词语进行此行标注,根据习得的规则对词语进行判别。这项任务的关键在于对未知实体的识别。基于此,命名实体识别的主要思想在于根据现有实例的特征总结识别和分类规则。这些方法可以被分为有监督(supervised)、半监督(semi-supervised)和无监督(unsupervised)三类。有监督学习包括隐形马科夫模型(HMM)、决策树、最大熵模型(ME)、支持向量机(SVM)和条件随机场(CRF)。这些方法主要是读取注释语料库,记忆实例并进行学习,根据这些例子的特征生成针对某一种实例的识别规则。

图论技术

图论是以“图”为研究对象的一个数学分支,是组合数学和离散数学的重要组成部分。图是用来对对象之间的成对关系建模的数学结构,由“顶点”(又称“节点”或“点”)以及连接这些顶点的“边”(又称“弧”或“线”)组成。值得注意的是,图的顶点集合不能为空,但边的集合可以为空。图可能是无向的,这意味着图中的边在连接顶点时无需区分方向。否则,称图是有向的。

条件随机场技术

条件随机场(conditional random field,简称 CRF),是一种鉴别式机率模型,是随机场的一种,常用于标注或分析序列资料,如自然语言文字或是生物序列。 如同马尔可夫随机场,条件随机场为无向性之图模型,图中的顶点代表随机变量,顶点间的连线代表随机变量间的相依关系,在条件随机场当中,随机变量 Y 的分布为条件机率,给定的观察值则为随机变量 X。原则上,条件随机场的图模型布局是可以任意给定的,一般常用的布局是链接式的架构,链接式架构不论在训练(training)、推论(inference)、或是解码(decoding)上,都存在有效率的算法可供演算。 条件随机场跟隐马尔可夫模型常被一起提及,条件随机场对于输入和输出的机率分布,没有如隐马尔可夫模型那般强烈的假设存在。 线性链条件随机场应用于标注问题是由Lafferty等人与2001年提出的。

语音识别技术

自动语音识别是一种将口头语音转换为实时可读文本的技术。自动语音识别也称为语音识别(Speech Recognition)或计算机语音识别(Computer Speech Recognition)。自动语音识别是一个多学科交叉的领域,它与声学、语音学、语言学、数字信号处理理论、信息论、计算机科学等众多学科紧密相连。由于语音信号的多样性和复杂性,目前的语音识别系统只能在一定的限制条件下获得满意的性能,或者说只能应用于某些特定的场合。自动语音识别在人工智能领域占据着极其重要的位置。

word2vec技术

Word2vec,为一群用来产生词向量的相关模型。这些模型为浅而双层的神经网络,用来训练以重新建构语言学之词文本。网络以词表现,并且需猜测相邻位置的输入词,在word2vec中词袋模型假设下,词的顺序是不重要的。 训练完成之后,word2vec模型可用来映射每个词到一个向量,可用来表示词对词之间的关系。该向量为神经网络之隐藏层。 Word2vec依赖skip-grams或连续词袋(CBOW)来建立神经词嵌入。Word2vec为托马斯·米科洛夫(Tomas Mikolov)在Google带领的研究团队创造。该算法渐渐被其他人所分析和解释。

自然语言处理技术

自然语言处理(英语:natural language processing,缩写作 NLP)是人工智能和语言学领域的分支学科。此领域探讨如何处理及运用自然语言;自然语言认知则是指让电脑“懂”人类的语言。自然语言生成系统把计算机数据转化为自然语言。自然语言理解系统把自然语言转化为计算机程序更易于处理的形式。

贪心算法技术

贪心法,又称贪心算法、贪婪算法、或称贪婪法,是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法。比如在旅行推销员问题中,如果旅行员每次都选择最近的城市,那这就是一种贪心算法。

概率图模型技术

在概率论和统计学中,概率图模型(probabilistic graphical model,PGM) ,简称图模型(graphical model,GM),是指一种用图结构来描述多元随机 变量之间条件独立关系的概率模型

强化学习技术

强化学习是一种试错方法,其目标是让软件智能体在特定环境中能够采取回报最大化的行为。强化学习在马尔可夫决策过程环境中主要使用的技术是动态规划(Dynamic Programming)。流行的强化学习方法包括自适应动态规划(ADP)、时间差分(TD)学习、状态-动作-回报-状态-动作(SARSA)算法、Q 学习、深度强化学习(DQN);其应用包括下棋类游戏、机器人控制和工作调度等。

联想机构

联想集团是1984年中国科学院计算技术研究所投资20万元人民币,由11名科技人员创办,是中国的一家在信息产业内多元化发展的大型企业集团,和富有创新性的国际化的科技公司。 从1996年开始,联想电脑销量一直位居中国国内市场首位;2005年,联想集团收购IBM PC(Personal computer,个人电脑)事业部;2013年,联想电脑销售量升居世界第一,成为全球最大的PC生产厂商。2014年10月,联想集团宣布了该公司已经完成对摩托罗拉移动的收购。 作为全球电脑市场的领导企业,联想从事开发、制造并销售可靠的、安全易用的技术产品及优质专业的服务,帮助全球客户和合作伙伴取得成功。联想公司主要生产台式电脑、服务器、笔记本电脑、智能电视、打印机、掌上电脑、主板、手机、一体机电脑等商品。 自2014年4月1日起, 联想集团成立了四个新的、相对独立的业务集团,分别是PC业务集团、移动业务集团、企业级业务集团、云服务业务集团。2016年8月,全国工商联发布“2016中国民营企业500强”榜单,联想名列第四。 2018年12月,世界品牌实验室编制的《2018世界品牌500强》揭晓,排名第102。

知乎机构

知乎作为中文互联网知名知识内容平台,致力于构建一个人人都可接入的知识分享网络,让人们便捷地与世界分享知识、经验和见解,高效获得可信赖的解答。 目前,知乎已经覆盖「问答」社区、一站式知识服务平台「知乎大学」、短内容分享功能「想法」等一系列产品和服务,并建立了包括音频、视频在内的多元媒介形式。截止 2018 年 8 月底,知乎用户数已突破 2 亿,回答数超过 1.2 亿。未来,知乎进一步加大对 AI 技术和应用的投入,构建一个由 AI 驱动的智能社区,让知识普惠每一个人。

https://www.zhihu.com
语言学技术

每种人类语言都是知识和能力的复合体,语言的使用者能够相互交流,表达想法,假设,情感,欲望以及所有其他需要表达的事物。语言学是对这些知识体系各方面的研究:如何构建这样的知识体系,如何获取,如何在消息的制作和理解中使用它,它是如何随时间变化的?语言学家因此关注语言本质的一些特殊问题。比如: 所有人类语言都有哪些共同属性?语言如何不同,系统的差异程度如何,我们能否在差异中找到模式?孩子如何在短时间内获得如此完整的语言知识?语言随时间变化的方式有哪些,语言变化的局限性是什么?当我们产生和理解语言时,认知过程的本质是什么?语言学研究的就是这些最本质的问题。

命名实体识技术

命名实体识别(英语:Named Entity Recognition,简称NER),又称作专名识别、命名实体,是指识别文本中具有特定意义的实体,主要包括人名、地名、机构名、专有名词等,以及时间、数量、货币、比例数值等文字。指的是可以用专有名词(名称)标识的事物,一个命名实体一般代表唯一一个具体事物个体,包括人名、地名等。

暂无评论
暂无评论~