语义分析,本文指运用各种机器学习方法,挖掘与学习文本、图片等的深层次概念。wikipedia上的解释:In machine learning, semantic analysis of a corpus is the task of building structures that approximate concepts from a large set of documents(or images)。
工作这几年,陆陆续续实践过一些项目,有搜索广告,社交广告,微博广告,品牌广告,内容广告等。要使我们广告平台效益最大化,首先需要理解用户,Context(将展示广告的上下文)和广告,才能将最合适的广告展示给用户。而这其中,就离不开对用户,对上下文,对广告的语义分析,由此催生了一些子项目,例如文本语义分析,图片语义理解,语义索引,短串语义关联,用户广告语义匹配等。
接下来我将写一写我所认识的语义分析的一些方法,虽说我们在做的时候,效果导向居多,方法理论理解也许并不深入,不过权当个人知识点总结,有任何不当之处请指正,谢谢。
本文主要由以下四部分组成:文本基本处理,文本语义分析,图片语义分析,语义分析小结。先讲述文本处理的基本方法,这构成了语义分析的基础。接着分文本和图片两节讲述各自语义分析的一些方法,值得注意的是,虽说分为两节,但文本和图片在语义分析方法上有很多共通与关联。最后我们简单介绍下语义分析在广点通“用户广告匹配”上的应用,并展望一下未来的语义分析方法。
1 文本基本处理
在讲文本语义分析之前,我们先说下文本基本处理,因为它构成了语义分析的基础。而文本处理有很多方面,考虑到本文主题,这里只介绍中文分词以及Term Weighting。
1.1 中文分词
拿到一段文本后,通常情况下,首先要做分词。分词的方法一般有如下几种:
- 基于字符串匹配的分词方法。此方法按照不同的扫描方式,逐个查找词库进行分词。根据扫描方式可细分为:正向最大匹配,反向最大匹配,双向最大匹配,最小切分(即最短路径);总之就是各种不同的启发规则。
- 全切分方法。它首先切分出与词库匹配的所有可能的词,再运用统计语言模型决定最优的切分结果。它的优点在于可以解决分词中的歧义问题。下图是一个示例,对于文本串“南京市长江大桥”,首先进行词条检索(一般用Trie存储),找到匹配的所有词条(南京,市,长江,大桥,南京市,长江大桥,市长,江大桥,江大,桥),以词网格(word lattices)形式表示,接着做路径搜索,基于统计语言模型(例如n-gram)[18]找到最优路径,最后可能还需要命名实体识别。下图中“南京市 长江 大桥”的语言模型得分,即P(南京市,长江,大桥)最高,则为最优切分。
图1. “南京市长江大桥”语言模型得分
- 由字构词的分词方法。可以理解为字的分类问题,也就是自然语言处理中的sequence labeling问题,通常做法里利用HMM,MAXENT,MEMM,CRF等预测文本串每个字的tag[62],譬如B,E,I,S,这四个tag分别表示:beginning, inside, ending, single,也就是一个词的开始,中间,结束,以及单个字的词。 例如“南京市长江大桥”的标注结果可能为:“南(B)京(I)市(E)长(B)江(E)大(B)桥(E)”。由于CRF既可以像最大熵模型一样加各种领域feature,又避免了HMM的齐次马尔科夫假设,所以基于CRF的分词目前是效果最好的,具体请参考文献[61,62,63]。除了HMM,CRF等模型,分词也可以基于深度学习方法来做,如文献[9][10]所介绍,也取得了state-of-the-art的结果。
图2. 基于深度学习的中文分词
上图是一个基于深度学习的分词示例图。我们从上往下看,首先对每一个字进行Lookup Table,映射到一个固定长度的特征向量(这里可以利用词向量,boundary entropy,accessor variety等);接着经过一个标准的神经网络,分别是linear,sigmoid,linear层,对于每个字,预测该字属于B,E,I,S的概率;最后输出是一个矩阵,矩阵的行是B,E,I,S 4个tag,利用viterbi算法就可以完成标注推断,从而得到分词结果。
一个文本串除了分词,还需要做词性标注,命名实体识别,新词发现等。通常有两种方案,一种是pipeline approaches,就是先分词,再做词性标注;另一种是joint approaches,就是把这些任务用一个模型来完成。有兴趣可以参考文献[9][62]等。
一般而言,方法一和方法二在工业界用得比较多,方法三因为采用复杂的模型,虽准确率相对高,但耗时较大。
1.2 语言模型
前面在讲“全切分分词”方法时,提到了语言模型,并且通过语言模型,还可以引出词向量,所以这里把语言模型简单阐述一下。
语言模型是用来计算一个句子产生概率的概率模型,即P(w_1,w_2,w_3…w_m),m表示词的总个数。根据贝叶斯公式:P(w_1,w_2,w_3 … w_m) = P(w_1)P(w_2|w_1)P(w_3|w_1,w_2) … P(w_m|w_1,w_2 … w_{m-1})。
最简单的语言模型是N-Gram,它利用马尔科夫假设,认为句子中每个单词只与其前n–1个单词有关,即假设产生w_m这个词的条件概率只依赖于前n–1个词,则有P(w_m|w_1,w_2…w_{m-1}) = P(w_m|w_{m-n+1},w_{m-n+2} … w_{m-1})。其中n越大,模型可区别性越强,n越小,模型可靠性越高。
N-Gram语言模型简单有效,但是它只考虑了词的位置关系,没有考虑词之间的相似度,词语法和词语义,并且还存在数据稀疏的问题,所以后来,又逐渐提出更多的语言模型,例如Class-based ngram model,topic-based ngram model,cache-based ngram model,skipping ngram model,指数语言模型(最大熵模型,条件随机域模型)等。若想了解更多请参考文章[18]。
最近,随着深度学习的兴起,神经网络语言模型也变得火热[4]。用神经网络训练语言模型的经典之作,要数Bengio等人发表的《A Neural Probabilistic Language Model》[3],它也是基于N-Gram的,首先将每个单词w_{m-n+1},w_{m-n+2} … w_{m-1}映射到词向量空间,再把各个单词的词向量组合成一个更大的向量作为神经网络输入,输出是P(w_m)。本文将此模型简称为ffnnlm(Feed-forward Neural Net Language Model)。ffnnlm解决了传统n-gram的两个缺陷:(1)词语之间的相似性可以通过词向量来体现;(2)自带平滑功能。文献[3]不仅提出神经网络语言模型,还顺带引出了词向量,关于词向量,后文将再细述。
图3. 基于神经网络的语言模型
从最新文献看,目前state-of-the-art语言模型应该是基于循环神经网络(recurrent neural network)的语言模型,简称rnnlm[5][6]。循环神经网络相比于传统前馈神经网络,其特点是:可以存在有向环,将上一次的输出作为本次的输入。而rnnlm和ffnnlm的最大区别是:ffnnmm要求输入的上下文是固定长度的,也就是说n-gram中的 n 要求是个固定值,而rnnlm不限制上下文的长度,可以真正充分地利用所有上文信息来预测下一个词,本次预测的中间隐层信息(例如下图中的context信息)可以在下一次预测里循环使用。
图4. 基于simple RNN(time-delay neural network)的语言模型
如上图所示,这是一个最简单的rnnlm,神经网络分为三层,第一层是输入层,第二层是隐藏层(也叫context层),第三层输出层。 假设当前是t时刻,则分三步来预测P(w_m):
- 单词w_{m-1}映射到词向量,记作input(t)
- 连接上一次训练的隐藏层context(t–1),经过sigmoid function,生成当前t时刻的context(t)
- 利用softmax function,预测P(w_m)
参考文献[7]中列出了一个rnnlm的library,其代码紧凑。利用它训练中文语言模型将很简单,上面“南京市 长江 大桥”就是rnnlm的预测结果。
基于RNN的language model利用BPTT(BackPropagation through time)算法比较难于训练,原因就是深度神经网络里比较普遍的vanishing gradient问题[55](在RNN里,梯度计算随时间成指数倍增长或衰减,称之为Exponential Error Decay)。所以后来又提出基于LSTM(Long short term memory)的language model,LSTM也是一种RNN网络,关于LSTM的详细介绍请参考文献[54,49,52]。LSTM通过网络结构的修改,从而避免vanishing gradient问题。
图5. LSTM memory cell
如上图所示,是一个LSTM unit。如果是传统的神经网络unit,output activation bi = activation_function(ai),但LSTM unit的计算相对就复杂些了,它保存了该神经元上一次计算的结果,通过input gate,output gate,forget gate来计算输出,具体过程请参考文献[53,54]。
1.3 Term Weighting
Term重要性
对文本分词后,接下来需要对分词后的每个term计算一个权重,重要的term应该给与更高的权重。举例来说,“什么产品对减肥帮助最大?”的term weighting结果可能是: “什么 0.1,产品 0.5,对 0.1,减肥 0.8,帮助 0.3,最大 0.2”。Term weighting在文本检索,文本相关性,核心词提取等任务中都有重要作用。
- Term weighting的打分公式一般由三部分组成:local,global和normalization [1,2]。即
TermWeight=L_{i,j} G_i N_j。L_{i,j}是term i在document j中的local weight,G_i是term i的global weight,N_j是document j的归一化因子。
常见的local,global,normalization weight公式[2]有:图6. Local weight formulas
图7. Global weight formulas
图8. Normalization factors
Tf-Idf是一种最常见的term weighting方法。在上面的公式体系里,Tf-Idf的local weight是FREQ,glocal weight是IDFB,normalization是None。tf是词频,表示这个词出现的次数。df是文档频率,表示这个词在多少个文档中出现。idf则是逆文档频率,idf=log(TD/df),TD表示总文档数。Tf-Idf在很多场合都很有效,但缺点也比较明显,以“词频”度量重要性,不够全面,譬如在搜索广告的关键词匹配时就不够用。
除了TF-IDF外,还有很多其他term weighting方法,例如Okapi,MI,LTU,ATC,TF-ICF[59]等。通过local,global,normalization各种公式的组合,可以生成不同的term weighting计算方法。不过上面这些方法都是无监督计算方法,有一定程度的通用性,但在一些特定场景里显得不够灵活,不够准确,所以可以基于有监督机器学习方法来拟合term weighting结果。
图9. Okapi计算公式
- 利用有监督机器学习方法来预测weight。这里类似于机器学习的分类任务,对于文本串的每个term,预测一个[0,1]的得分,得分越大则term重要性越高。既然是有监督学习,那么就需要训练数据。如果采用人工标注的话,极大耗费人力,所以可以采用训练数据自提取的方法,利用程序从搜索日志里自动挖掘。从海量日志数据里提取隐含的用户对于term重要性的标注,得到的训练数据将综合亿级用户的“标注结果”,覆盖面更广,且来自于真实搜索数据,训练结果与标注的目标集分布接近,训练数据更精确。下面列举三种方法(除此外,还有更多可以利用的方法):
- 从搜索session数据里提取训练数据,用户在一个检索会话中的检索核心意图是不变的,提取出核心意图所对应的term,其重要性就高。
- 从历史短串关系资源库里提取训练数据,短串扩展关系中,一个term出现的次数越多,则越重要。
- 从搜索广告点击日志里提取训练数据,query与bidword共有term的点击率越高,它在query中的重要程度就越高。
通过上面的方法,可以提取到大量质量不错的训练数据(数十亿级别的数据,这其中可能有部分样本不准确,但在如此大规模数据情况下,绝大部分样本都是准确的)。
有了训练数据,接下来提取特征,基于逻辑回归模型来预测文本串中每个term的重要性。所提取的特征包括:
- term的自解释特征,例如term专名类型,term词性,term idf,位置特征,term的长度等;
- term与文本串的交叉特征,例如term与文本串中其他term的字面交叉特征,term转移到文本串中其他term的转移概率特征,term的文本分类、topic与文本串的文本分类、topic的交叉特征等。
核心词、关键词提取
- 短文本串的核心词提取。对短文本串分词后,利用上面介绍的term weighting方法,获取term weight后,取一定的阈值,就可以提取出短文本串的核心词。
- 长文本串(譬如web page)的关键词提取。这里简单介绍几种方法。想了解更多,请参考文献[69]。
- 采用基于规则的方法。考虑到位置特征,网页特征等。
- 基于广告主购买的bidword和高频query建立多模式匹配树,在长文本串中进行全字匹配找出候选关键词,再结合关键词weight,以及某些规则找出优质的关键词。
- 类似于有监督的term weighting方法,也可以训练关键词weighting的模型。
- 基于文档主题结构的关键词抽取,具体可以参考文献[71]。
参考文献
- Term-weighting approaches in automatic text retrieval,Gerard Salton et.
- New term weighting formulas for the vector space method in information retrieval
- A neural probabilistic language model 2003
- Deep Learning in NLP-词向量和语言模型
- Recurrent neural network based language models
- Statistical Language Models based on Neural Networks,mikolov博士论文
- Rnnlm library
- A survey of named entity recognition and classification
- Deep learning for Chinese word segmentation and POS tagging
- Max-margin tensor neural network for chinese word segmentation
- Learning distributed representations of concepts
- Care and Feeding of Topic Models: Problems, Diagnostics, and Improvements
- LightLda
- word2vec
- Efficient Estimation of Word Representations in Vector Space
- Deep Learning实战之word2vec
- word2vec中的数学原理详解 出处2
- 斯坦福课程-语言模型
- Translating Videos to Natural Language Using Deep Recurrent Neural Networks
- Distributed Representations of Sentences and Documents
- Convolutional Neural Networks卷积神经网络
- A New, Deep-Learning Take on Image Recognition
- Spatial Pyramid Pooling in Deep Convolutional Networks for Visual Recognition
- A Deep Learning Tutorial: From Perceptrons to Deep Networks
- Deep Learning for Computer Vision
- Zero-shot leanring by convex combination of semantic embeddings
- Sequence to sequence learning with neural network
- Exploting similarities among language for machine translation
- Grammar as Foreign Language Oriol Vinyals, Lukasz Kaiser, Terry Koo, Slav Petrov, Ilya Sutskever, Geoffrey Hinton, arXiv 2014
- Deep Semantic Embedding
- 张家俊. DNN Applications in NLP
- Deep learning for natural language processing and machine translation
- Distributed Representations for Semantic Matching
- distributed_representation_nlp
- Deep Visual-Semantic Alignments for Generating Image Descriptions
- Convolutional Neural Networks for Sentence Classification
- Senna
- ImageNet Large Scale Visual Recognition Challenge
- Krizhevsky A, Sutskever I, Hinton G E. ImageNet Classification with Deep Convolutional Neural Networks
- Gradient-Based Learning Applied to Document Recognition
- Effetive use of word order for text categorization with convolutional neural network,Rie Johnson
- Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation
- Show and Tell: A Neural Image Caption Generator
- Deep Image: Scaling up Image Recognition
- Large-Scale High-Precision Topic Modeling on Twitter
- A. Krizhevsky. One weird trick for parallelizing convolutional neural networks. arXiv:1404.5997, 2014
- A Brief Overview of Deep Learning
- Going deeper with convolutions. Christian Szegedy. Google Inc. 阅读笔记
- Long Short-Term Memory Recurrent Neural Network Architectures for Large Scale Acoustic Modeling
- Semi-Supervised Learning Tutorial
- http://www.zhihu.com/question/24904450
- LONG SHORT-TERM MEMORY BASED RECURRENT NEURAL NETWORK ARCHITECTURES FOR LARGE VOCABULARY SPEECH RECOGNITION
- LSTM Neural Networks for Language Modeling
- LONG SHORT-TERM MEMORY
- Bengio, Y., Simard, P., Frasconi, P., “Learning long-term dependencies with gradient descent is difficult” IEEE Transactions on Neural Networks 5 (1994), pp. 157–166
- AliasLDA
- Gibbs sampling for the uninitiated
- Learning classifiers from only positive and unlabeled data
- TF-ICF: A New Term Weighting Scheme for Clustering Dynamic Data Streams
- LDA数学八卦
- Chinese Word Segmentation and Named Entity Recognition Based on Conditional Random Fields Models
- Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data
- Chinese Segmentation and New Word Detection using Conditional Random Fields
- Gregor Heinrich. Parameter estimation for text analysis
- Peacock:大规模主题模型及其在腾讯业务中的应用
- L. Yao, D. Mimno, and A. McCallum. Efficient methods for topic model inference on streaming document collections. In KDD, 2009.
- David Newman. Distributed Algorithms for Topic Models
- Xuemin. LDA工程实践之算法篇
- Brian Lott. Survey of Keyword Extraction Techniques
- Yi Wang, Xuemin Zhao, Zhenlong Sun, Hao Yan, Lifeng Wang, Zhihui Jin, Liubin Wang, Yang Gao, Ching Law, and Jia Zeng. Peacock: Learning Long-Tail Topic Features for Industrial Applications. TIST’2015.
- 刘知远. 基于文档主题结构的关键词抽取方法研究
- Hinton. Reducing the Dimensionality of Data with Neural Networks
- Samaneh Moghaddam. On the design of LDA models for aspect-based opinion mining;
- The FLDA model for aspect-based opinion mining: addressing the cold start problem
- Ross Girshick et. Rich feature hierarchies for accurate object detection and semantic segmentation
- J. Uijlings, K. van de Sande, T. Gevers, and A. Smeulders. Selective search for object recognition. IJCV, 2013.
- Baidu/UCLA: Explain Images with Multimodal Recurrent Neural Networks
- Toronto: Unifying Visual-Semantic Embeddings with Multimodal Neural Language Models
- Berkeley: Long-term Recurrent Convolutional Networks for Visual Recognition and Description
- Xinlei Chen et. Learning a Recurrent Visual Representation for Image Caption Generation
- Hao Fang et. From Captions to Visual Concepts and Back
- Modeling Documents with a Deep Boltzmann Machine
- A Deep Dive into Recurrent Neural Nets
- Xiang zhang et. Text Understanding from Scratch
相关推荐
实验中提到的“递归下降语法制导翻译法”是一种常用的语义分析方法。递归下降分析基于语法的递归性质,将每个非终结符对应一个函数,当遇到语法分析树的一个节点时,调用相应的函数进行处理。而“语法制导翻译”则是...
词法分析、SLR语法分析和SLR语义分析是编译器设计与实现的关键步骤,让我们逐一深入探讨这些概念。 首先,词法分析(Lexical Analysis)是编译过程的第一步。它将源代码按照字符流进行扫描,识别出有意义的符号单元...
递归下降分析是一种自顶向下的语法分析方法,它利用递归函数来匹配输入的语法结构。在语义分析阶段,我们会插入适当的语义动作,这些动作将与语法分析同时进行,以便生成表示程序操作的四元式。 1. 语义过程的设置...
四元式生成就是语义分析的一个重要部分,它将抽象语法树转化为中间代码(四元式)的形式,这种形式便于优化和目标代码生成。 四元式是一种通用的中间表示(IR),它通常包含运算符、操作数和结果。例如,对于表达式...
本文将详细探讨"简单C语言语义分析"这一主题,包括C语言的基本特性,编译器的工作原理,以及词法分析、语法分析和语义分析的关键步骤。 C语言是一种强大的、广泛使用的编程语言,它以其简洁、高效和灵活性著称。...
在计算机科学领域,编译器设计是一门至关重要的课程,其中语法分析和语义分析是编译器构建的核心环节。本文将深入探讨“二---十进制”的语法分析及语义分析程序设计,特别是基于LR文法的方法。LR文法是一种自底向上...
语义分析是编译原理中的一个重要组成部分,它在编译器的设计与实现中扮演着至关重要的角色。编译原理是计算机科学的一个核心领域,主要研究如何将高级编程语言转换为机器可理解的低级指令。在这个过程中,语义分析是...
语义分析分为静态语义分析和动态语义分析。静态语义分析主要在编译时进行,包括类型检查、作用域检查、常量折叠等。例如,检查变量是否在使用前已定义,类型是否匹配,表达式是否合法等。动态语义分析则发生在程序...
语义分析是编译器设计中的一个重要环节,其主要任务是对源程序进行更深层次的语法检查,并在这一过程中收集类型信息等数据,为后续的代码生成和优化做准备。本次实验通过一个简单的示例程序实现了基于C语言的语义...
2. **类型检查**:语义分析首要任务之一就是确保操作数和运算符之间的类型匹配。例如,在C++中,加法操作符“+”要求两边的操作数都是数值类型。如果语义分析发现类型不匹配,就会报告错误。 3. **常量表达式计算**...
总之,这个"语音和语义分析demo"是一个理想的入门项目,可以帮助初学者掌握语音识别和语义分析的基本原理和实现方法。通过这个项目,他们可以了解到Java在AI领域的应用,以及如何利用现有库来处理和理解自然语言。...
这些代码可能采用了递归下降解析、自底向上或自顶向下的方法来实现语法分析,也可能包含了词法分析的扫描器和语义分析的验证函数。 通过深入理解这三个分析阶段,开发者能够更好地设计和优化编译器,提高程序的效率...
总的来说,这个课程设计提供了一个全面的编译器构造体验,涵盖了从词法分析到语义分析的完整流程,并且具有跨平台的潜力。对任何计算机科学专业的学生来说,这都是一个宝贵的实践机会,有助于深化对编译器工作的理解...
LL(1)分析是一种高效的分析方法,它基于一个预测解析表,该表指示了在当前输入符号和当前非终结符号下应该选择哪个产生式进行推导。为了构建这个表,我们需要计算每个非终结符号的首符号集(First集合)和向前看集...
在编译原理的学习过程中,语义分析是至关重要的一个环节。它主要负责检查源程序是否有语义错误,并收集类型信息供后面的代码生成阶段使用。在本篇文档中,我们将详细介绍如何使用 C++ 来实现一个简单的语义分析器,...
本次实验要求学生采用递归下降的方法实现语法制导翻译法,针对算术表达式与赋值语句进行语义分析,并生成相应的四元式序列。 #### 输入与输出 **输入:** 输入是一段由语法分析器提供的正确单词序列,这些单词构成...
语义分析是自然语言处理(NLP)领域中的一个重要环节,它是计算机理解人类语言的关键步骤。在编程领域,尤其是在开发编译器或解释器时,语义分析是必不可少的。"09语义分析.rar" 是一个与VC++(Visual C++)相关的...
例如,在C++中,如果声明了一个整型变量,然后试图赋给它一个字符串,语义分析器就会报错。在实验中,你可能会实现一个简单的类型系统和类型检查规则,以确保程序的语义正确性。 实验报告通常会包含以下几个部分: ...
语义分析是编译器的另一关键阶段,其任务是检查源代码的语义正确性,并为其生成中间代码或目标代码。对于布尔表达式,这包括类型检查(如确保所有操作数都是布尔类型)、运算符的适用性检查以及常量折叠(如在编译时...