一、课程介绍
斯坦福大学于2012年3月在Coursera启动了在线自然语言处理课程,由NLP领域大牛Dan Jurafsky 和 Chirs Manning教授授课:
链接地址
以下是本课程的学习笔记,以课程PPT/PDF为主,其他参考资料为辅,融入个人拓展、注解,抛砖引玉,欢迎大家在“我爱公开课”上一起探讨学习。
课件汇总下载地址:斯坦福大学自然语言处理公开课课件汇总
二、最小编辑距离
1)定义
编辑距离(Minimum Edit Distance,MED),又称Levenshtein距离,是指两个字符串之间,由一个转成另一个所需要的最少编辑操作次数。允许的编辑操作包括:将一个字符替换成另一个字符(substitution,s),插入一个字符(insert,i)或者删除一个字符(delete,d),如下图所示:
在大学算法设计相关课程上,想必大家都已经学习过使用动态规划算法解最小编辑距离,形式化定义如下:
最终求得D(n,m)即为字符串X[0...n]与Y[0...m]之间的最小编辑距离。
2)应用
最小编辑距离通常作为一种相似度计算函数被用于多种实际应用中,详细如下: (特别的,对于中文自然语言处理,一般以词为基本处理单元)
- 拼写纠错(Spell Correction):又拼写检查(Spell Checker),将每个词与词典中的词条比较,英文单词往往需要做词干提取等规范化处理,如果一个词在词典中不存在,就被认为是一个错误,然后试图提示N个最可能要输入的词——拼写建议。常用的提示单词的算法就是列出词典中与原词具有最小编辑距离的词条。
这里肯定有人有疑问:对每个不在词典中的词(假如长度为len)都与词典中的词条计算最小编辑距离,时间复杂度是不是太高了?的确,所以一般需要加一些剪枝策略,如:
- 因为一般拼写检查应用只需要给出Top-N的纠正建议即可(N一般取10),那么我们可以从词典中按照长度依次为len、len-1、len+1、len-2、len-3、...的词条比较;
- 限定拼写建议词条与当前词条的最小编辑距离不能大于某个阈值;
- 如果最小编辑距离为1的候选词条超过N后,终止处理;
- 缓存常见的拼写错误和建议,提高性能。
- DNA分析:基因学的一个主要主题就是比较 DNA 序列并尝试找出两个序列的公共部分。如果两个 DNA 序列有类似的公共子序列,那么这些两个序列很可能是同源的。在比对两个序列时,不仅要考虑完全匹配的字符,还要考虑一个序列中的空格或间隙(或者,相反地,要考虑另一个序列中的插入部分)和不匹配,这两个方面都可能意味着突变(mutation)。在序列比对中,需要找到最优的比对(最优比对大致是指要将匹配的数量最大化,将空格和不匹配的数量最小化)。如果要更正式些,可以确定一个分数,为匹配的字符添加分数、为空格和不匹配的字符减去分数。
全局序列比对尝试找到两个完整的序列 S1和 S2之间的最佳比对。以下面两个 DNA 序列为例:
S1= GCCCTAGCG
S2= GCGCAATG
如果为每个匹配字符一分,一个空格扣两分,一个不匹配字符扣一分,那么下面的比对就是全局最优比对:
S1'= GCCCTAGCG
S2'= GCGC-AATG
连字符(-)代表空格。在 S2'中有五个匹配字符,一个空格(或者反过来说,在 S1'中有一个插入项),有三个不匹配字符。这样得到的分数是 (5 * 1) + (1 * -2) + (3 * -1) = 0,这是能够实现的最佳结果。
使用局部序列比对,不必对两个完整的序列进行比对,可以在每个序列中使用某些部分来获得最大得分。使用同样的序列 S1和 S2,以及同样的得分方案,可以得到以下局部最优比对 S1''和 S2'':
S1 = GCCCTAGCG
S1''= GCG
S2''= GCG
S2 = GCGCAATG
这个局部比对的得分是 (3 * 1) + (0 * -2) + (0 * -1) = 3。
- 命名实体抽取(Named Entity Extraction):由于实体的命名往往没有规律,如品牌名,且可能存在多种变形、拼写形式,如“IBM”和“IBM Inc.”,这样导致基于词典完全匹配的命名实体识别方法召回率较低,为此,我们可以使用编辑距离由完全匹配泛化到模糊匹配,先抽取实体名候选词。
具体的,可以将候选文本串与词典中的每个实体名进行编辑距离计算,当发现文本中的某一字符串的编辑距离值小于给定阈值时,将其作为实体名候选词;获取实体名候选词后,根据所处上下文使用启发式规则或者分类的方法判定候选词是否的确为实体名。
- 实体共指(Entity Coreference):通过计算任意两个实体名之间的最小编辑距离判定是否存在共指关系?如“IBM”和“IBM Inc.”, "Stanford President John Hennessy "和"Stanford University President John Hennessy"。
- 机器翻译(Machine Translation):
- 识别平行网页对:由于平行网页通常有相同或类似的界面结构,因此平行网页在HTML结构上应该有很大近似度。首先将网页的HTML标签抽取出来,连接成一个字符串,然后用最小编辑距离考察两个字符串的近似度。实际中,此策略一般与文档长度比例、句对齐翻译模型等方法结合使用,以识别最终的平行网页对。
- 自动评测:首先存储机器翻译原文和不同质量级别的多个参考译文,评测时把自动翻译的译文对应到与其编辑距离最小的参考译文上,间接估算自动译文的质量,如下图所示:
- 字符串核函数(String Kernel):最小编辑距离作为字符串之间的相似度计算函数,用作核函数,集成在SVM中使用。
3)变形
在基本的编辑距离基础上,结合实际应用,往往需要做一些变形或改进,如某些拼写错误相对其他更容易发生,同义词替换、虚词或修饰成分被删除(或插入)应该得到较小的惩罚,等等。
改进后的最小编辑距离公式如下所示:
三、参考资料
- Lecture Slides: Minimum Edit Distance
- http://en.wikipedia.org
- 双语平行网页挖掘系统的设计与实现
- 机器翻译系统评测规范
- Improved-Edit-Distance Kernel for Chinese Relation Extraction
http://www.aiuxian.com/article/p-1035687.html
大家可以加我个人微信号:scccdgf
相关推荐
最小编辑距离,计算字符串的相似度,最小编辑距离,计算字符串的相似度最小编辑距离,计算字符串的相似度最小编辑距离,计算字符串的相似度最小编辑距离,计算字符串的相似度最小编辑距离,计算字符串的相似度
斯坦福NLP工具包(0.1.0):基于UD v2和Python CoreNLP接口提供53种语言的本地化、(PyTorch)神经网络实现的词条化、词性标记和依存解析
斯坦福nlp课程,ppt和pdf格式均包括在内
原网站:https://stanfordnlp.github.io/CoreNLP/ 里面的language support,考虑到需要支持中文的自然语言处理, 但是很难下载下来? 2020/02/28下载。
C#下调用Stanford CoreNLP,实现中文分词,命名实体识别,词性判断.附件中只包含如何调用,需自行从stanford官网下载模型和语料
## 使用Stanfordnlp和nltk进行**依存句法分析**,提取动名词短语 分词之后名词动词合并成chunking短语 主函数:sentenceSplit_host.py 输入:text.txt 输出:dependency.txt ## 主要步骤 通过读取text.txt文本...
《NLP汉语自然语言处理原理与实践》(郑捷著)是一本专业研究自然语言处理的书籍,本文作者在阅读这本书,调试其中的程序代码时,发现由于版本升级,导致其中的某些程序无法执行。本文针对书中第24页“安装Stanford...
stanford课程-----自然语言处理中的深度学习 课件2-15
斯坦福大学IOS教程:Stanford CS193P 第三课 网易教程上的PDF文档,希望对大家有用
Introduction to NLP What is Natural Language Processing? Question answering, information extraction, sentiment analysis, machine translation and etc. are all applications of NLP.
第1章 中文语言的机器处理 11.1 历史回顾 21.1.1 从科幻到现实 21.1.2 早期的探索 31.1.3 规则派还是统计派 31.1.4 从机器学习到认知计算 51.2 现代自然语言系统简介 61.2.1 NLP流程与开源框架 61.2.2...
stanford斯坦福NLP相关jar包2018,自然语言处理,由于大小限制缺少stanford-corenlp-3.9.2-models.jar,接下来会单发一下
Stanford NLP core nlp java包
授课老师是大名鼎鼎的Christopher Manning教授,他是两本书的第一作者:一本是《统计自然语言处理基础》(Foundations of Statistical Natural Language Processing),另一本是《信息检索导论》(Introduction to ...
NLP项目基于OpenNLP和StanfordNLP的文本标记器此应用程序可以读取您的字符串数据(最好是一列短语),并使用POS-tagger / Coreference解析器对其进行处理。 在处理结束时,该程序将创建一个具有解析结果的相应“ ....
iOS7应用开发Machismo(Stanford iOS7)第三节课课堂代码 Swift实现
授课老师是大名鼎鼎的Christopher Manning教授,他是两本书的第一作者:一本是《统计自然语言处理基础》(Foundations of Statistical Natural Language Processing),另一本是《信息检索导论》(Introduction to ...
一款轻量级的自然语言处理(NLP)工具包自然语言处理(NLP)工具包是一种用于处理和分析人类语言的软件。它包括许多不同的工具和技术,可以帮助计算机理解和处理语言。 NLP工具包通常包括以下功能: - 分词:将...
格式为java源文件 打开方式想必不用我多说
Python-直接在spaCy中使用最新的StanfordNLP研究模型