NLPJob

标签热度

机器学习 coursera 斯坦福大学 公开课 斯坦福 深度学习 自然语言处理 python 数据科学 andrew ng 数学 nlp 数据分析 数据挖掘 神经网络 大数据 计算机科学 英语 deep learning 统计学 算法 课件 数据可视化 机器学习公开课 机器学习笔记 google 机器学习视频 计算机 推荐系统 数据结构 商业 r语言 java 密码学 udacity 金融 免费电子书 电子书 公开课笔记 计算机视觉 商务英语 学术英语 python数据可视化 机器学习课程 机器人 ted 文本挖掘 r 视频 java编程 回归模型 excel 深度学习课程 mysql cousera公开课 统计 大数据公开课 ted公开课 ted演讲 线性回归 mit 概率图模型 领导力 金融市场 tensorflow 学习英语 物联网 大数据专项课程 python入门 大数据课程 英语写作 英语学习 算法课程 强化学习 高级机器学习 kaggle 文本分析 机器学习资料 函数式编程 scala 游戏设计 cousera 机器学习系统 机器人公开课 开源代码 人工智能 普林斯顿大学 machine learning 线性代数 代价函数 软件工程 javascript 伯克利 市场营销 财务会计 沃顿商学院 网页开发 网站开发 web开发 网络安全 python数据科学 商业分析 非对称密码学 对称密码学 应用密码学 大规模数据科学 英语听说 概率 机器学习基石 python机器学习 算法公开课 源代码 数学思维 社交网络分析 微积分公开课 杜克大学 机器学习公开课视频 公开课视频 coursera公开课视频 coursera公开课 贝叶斯 信息论 离散数学 宾夕法尼亚大学 neural networks 伯克利大学 密歇根大学 成本函数 梯度下降 云计算 编译器 自动机 cs101 daphne koller spark 软件 管理 会计 英语交流 商业策略 风险管理 资产管理 地理信息系统 gis 卷积神经网络 面向对象编程 序列模型 移动应用开发 数据库 计算机通信 敏捷开发 高级商务分析 商务分析 商务英语课程 c语言 数据管理 投资 计算原理 计算基础 推荐系统导论 学术英语写作 android应用开发 android开发 android 机器人课程 机器人学 数据科学竞赛 yandex 深度学习公开课 深度学习书籍 数据集 机器学习资源 分布式 微积分 大规模机器学习系统 统计推断 数据科学公开课 游戏 数学思维公开课 机器学习课件 数学公开课 微积分公开课视频 微积分公开课下载 mit微积分 mit公开课 龙星计划 神经网络公开课 coursera视频 斯坦福公开课 windows ios udacity公开课 无人驾驶汽车 人机交互公开课 人机交互 正则化 过拟合 逻辑回归 模型思维 网易公开课 acl net 逻辑 cmu 情感分析 我爱公开课 引言 普林斯顿 经济 saas 52opencourse 逻辑导引 图模型 chirs manning dan jurafsky ppt 时间序列 go语言课程 go语言 工程师 语法 区块链基础 区块链 软件开发 商务基础 运营管理 商务 机器学习实战 数据系统 投资管理 swift 计算机安全与系统管理 系统管理 计算机安全 seo策略 seo工具 seo 组织领导力 css3 html5 会计基础 c sharp 英语沟通 并发 并行 全栈开发 数据仓库 商业智能 投资策略 金融基础 数据工程 python零基础 安全系统 现代密码学 硬件安全 软件安全 网络安全基础 递归神经网络 信息检索 云计算网络 云计算应用 云计算基础 云计算概念 分组交换网络 局域网 创意写作 写作 数学基础 台湾大学 基因序列 生物信息学 斯坦福算法课程 软件架构 软件设计 java程序设计 r语言基础 图论 组合数学 python数据表示 python基础 深度学习专项课程 游戏设计与开发 游戏开发 游戏设计概念 游戏设计艺术 angular 恐龙古生物学 恐龙 古生物学 推荐系统评价 jquery 英语语法 c# 高级算法 算法专项 iot python专项课程 python入门课程 商务英语交流技巧 商务英语交流 python社交网络分析 python文本挖掘 机器学习专项 金融价值 金融决策 金融公开课 数据结构与算法 大数据机器学习 大数据分析 商业与金融建模 金融建模 c++ 学术英语听说 数据分析工具 编程入门 编程 编程基础 算法思维 计算机基础 秘钥管理 hdfs 数据工程师 hive 3d交互设计 3d建模 虚拟现实 vr 洛桑联邦理工学院 函数式编程入门 数据科学课程 数据科学专项课程 学术英语课程 学术英语写作课程 斯坦福算法专项课程 斯坦福算法 python数据分析 英文简历 英文面试 英文写作 贝叶斯方法 商业分析技术 大数据建模 数据获取 数据清洗 文本挖掘课程 聚类分析 python公开课 python课程 主成分分析 深度学习资料 词意消歧 词义消歧 推荐系统入门 python书籍 机器学习算法 数据结构课程 图像处理 贝叶斯方法实战 深度学习源代码 sibyl p2p 机器学习书籍 数据结构资料 凸优化 推荐系统入门资料 数据科学导论 可视化 机器学习开源工具包 jane mcgonigal 公开课社区 挖课 courseminer 文本情感分析 多变量微积分 社会计算 数学分析公开课 概率图模型公开课 百度 吴恩达 香港科技大学 函数式语言 scala公开课 class2go coursera无法连接 coursera打不开 keith devlin 数学思维简介 社交网络 余凯 张潼 机器人视频 robert sedgewick 算法上 多伦多大学 莱斯大学 华盛顿大学 佐治亚理工学院 神经网络视频 矩阵 coursera在线视频

Text Summarization

Keyword Extraction

Text Processing

Word Similarity

Best Coursera Course

+6 投票

一、课程介绍

斯坦福大学于2012年3月在Coursera启动了在线自然语言处理课程,由NLP领域大牛Dan Jurafsky 和 Chirs Manning教授授课:
https://class.coursera.org/nlp/

以下是本课程的学习笔记,以课程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)都与词典中的词条计算最小编辑距离,时间复杂度是不是太高了?的确,所以一般需要加一些剪枝策略,如:

  1. 因为一般拼写检查应用只需要给出Top-N的纠正建议即可(N一般取10),那么我们可以从词典中按照长度依次为len、len-1、len+1、len-2、len-3、...的词条比较;
  2. 限定拼写建议词条与当前词条的最小编辑距离不能大于某个阈值;
  3. 如果最小编辑距离为1的候选词条超过N后,终止处理;
  4. 缓存常见的拼写错误和建议,提高性能。
  • DNA分析:基因学的一个主要主题就是比较 DNA 序列并尝试找出两个序列的公共部分。如果两个 DNA 序列有类似的公共子序列,那么这些两个序列很可能是同源的。在比对两个序列时,不仅要考虑完全匹配的字符,还要考虑一个序列中的空格或间隙(或者,相反地,要考虑另一个序列中的插入部分)和不匹配,这两个方面都可能意味着突变(mutation)。在序列比对中,需要找到最优的比对(最优比对大致是指要将匹配的数量最大化,将空格和不匹配的数量最小化)。如果要更正式些,可以确定一个分数,为匹配的字符添加分数、为空格和不匹配的字符减去分数。

全局序列比对尝试找到两个完整的序列 S1S2之间的最佳比对。以下面两个 DNA 序列为例:

S1= GCCCTAGCG

S2= GCGCAATG

如果为每个匹配字符一分,一个空格扣两分,一个不匹配字符扣一分,那么下面的比对就是全局最优比对:

S1'= GCCCTAGCG

S2'= GCGC-AATG

连字符(-)代表空格。在 S2'中有五个匹配字符,一个空格(或者反过来说,在 S1'中有一个插入项),有三个不匹配字符。这样得到的分数是 (5 * 1) + (1 * -2) + (3 * -1) = 0,这是能够实现的最佳结果。

使用局部序列比对,不必对两个完整的序列进行比对,可以在每个序列中使用某些部分来获得最大得分。使用同样的序列 S1S2,以及同样的得分方案,可以得到以下局部最优比对 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):
  1. 识别平行网页对:由于平行网页通常有相同或类似的界面结构,因此平行网页在HTML结构上应该有很大近似度。首先将网页的HTML标签抽取出来,连接成一个字符串,然后用最小编辑距离考察两个字符串的近似度。实际中,此策略一般与文档长度比例、句对齐翻译模型等方法结合使用,以识别最终的平行网页对。
  2. 自动评测:首先存储机器翻译原文和不同质量级别的多个参考译文,评测时把自动翻译的译文对应到与其编辑距离最小的参考译文上,间接估算自动译文的质量,如下图所示:
  • 字符串核函数(String Kernel):最小编辑距离作为字符串之间的相似度计算函数,用作核函数,集成在SVM中使用。

3)变形

在基本的编辑距离基础上,结合实际应用,往往需要做一些变形或改进,如某些拼写错误相对其他更容易发生,同义词替换、虚词或修饰成分被删除(或插入)应该得到较小的惩罚,等等。

改进后的最小编辑距离公式如下所示:

三、参考资料

  1. Lecture Slides: Minimum Edit Distance
  2. http://en.wikipedia.org
  3. 双语平行网页挖掘系统的设计与实现 
  4. 机器翻译系统评测规范
  5. Improved-Edit-Distance Kernel for Chinese Relation Extraction
分类:自然语言处理 | 用户: (2.4k 分)
修改于 用户:

1个回答

0 投票
谢谢fandy,太高效了!
用户: (24.9k 分)
...