语义分析的一些方法
语义分析的一些方法(上篇)
人工智能林 17小时前70℃0评论
作者：火光摇曳
念。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重要性的标注，得到的训练数据将综合亿级用户的“标注结果”，覆盖面更广，且来自于真实搜索数据，训练结果与标注的目标集分布接近，训练数据更精确。下面列举三种方法(除此外，还有更多可以利用的方法)：
o从搜索session数据里提取训练数据，用户在一个检索会话中的检索核心意图是不变的，提取出核心意图所对应的term，其重要性就高。
o从历史短串关系资源库里提取训练数据，短串扩展关系中，一个term出现的次数越多，则越重要。
o从搜索广告点击日志里提取训练数据，query与bidword共有term 的点击率越高，它在query中的重要程度就越高。
通过上面的方法，可以提取到大量质量不错的训练数据（数十亿级别的数据，这其中可能有部分样本不准确，但在如此大规模数据情况下，绝大部分样本都是准确的）。
有了训练数据，接下来提取特征，基于逻辑回归模型来预测文本串中每个term的重要性。所提取的特征包括：
o term的自解释特征，例如term专名类型，term词性，term idf，
位置特征，term的长度等；
o term与文本串的交叉特征，例如term与文本串中其他term的字
面交叉特征，term转移到文本串中其他term的转移概率特征，term的
文本分类、topic与文本串的文本分类、topic的交叉特征等。
核心词、关键词提取
?短文本串的核心词提取。对短文本串分词后，利用上面介绍的term
weighting方法，获取term weight后，取一定的阈值，就可以提取出短文本串的核心词。
?长文本串(譬如web page)的关键词提取。这里简单介绍几种方法。想了解更多，请参考文献[69]。
o采用基于规则的方法。考虑到位置特征，网页特征等。
o基于广告主购买的bidword和高频query建立多模式匹配树，在长
文本串中进行全字匹配找出候选关键词，再结合关键词weight，以及某
些规则找出优质的关键词。
o类似于有监督的term weighting方法，也可以训练关键词
weighting的模型。
o基于文档主题结构的关键词抽取，具体可以参考文献[71]。
参考文献
1.Term-weighting approaches in automatic text retrieval，Gerard
Salton et.
2.New term weighting formulas for the vector space method in
information retrieval
3.A neural probabilistic language model 2003
4.Deep Learning in NLP-词向量和语言模型
5.Recurrent neural network based language models
6.Statistical Language Models based on Neural Networks，mikolov博
士论文
7.Rnnlm library
8.A survey of named entity recognition and classification
9.Deep learning for Chinese word segmentation and POS tagging
10.Max-margin tensor neural network for chinese word segmentation
11.Learning distributed representations of concepts
12.Care and Feeding of Topic Models: Problems, Diagnostics, and Improvements
13.LightLda
14.word2vec
15.Efficient Estimation of Word Representations in Vector Space
16.Deep Learning实战之word2vec
17.word2vec中的数学原理详解出处2
18.斯坦福课程-语言模型
19.Translating Videos to Natural Language Using Deep Recurrent Neural Networks
20.Distributed Representations of Sentences and Documents
21.Convolutional Neural Networks卷积神经网络
22.A New, Deep-Learning Take on Image Recognition
23.Spatial Pyramid Pooling in Deep Convolutional Networks for Visual Recognition
24.A Deep Learning Tutorial: From Perceptrons to Deep Networks
25.Deep Learning for Computer Vision
26.Zero-shot leanring by convex combination of semantic embeddings
27.Sequence to sequence learning with neural network
28.Exploting similarities among language for machine translation
29.Grammar as Foreign Language Oriol Vinyals, Lukasz Kaiser, Terry Koo, Slav Petrov, Ilya Sutskever, Geoffrey Hinton, arXiv 2014
30.Deep Semantic Embedding
31.张家俊. DNN Applications in NLP
32.Deep learning for natural language processing and machine translation
33.Distributed Representations for Semantic Matching
34.distributed_representation_nlp
35.Deep Visual-Semantic Alignments for Generating Image Descriptions
36.Convolutional Neural Networks for Sentence Classification
37.Senna
38.ImageNet Large Scale Visual Recognition Challenge
39.Krizhevsky A, Sutskever I, Hinton G E. ImageNet Classification with Deep Convolutional Neural Networks
40.Gradient-Based Learning Applied to Document Recognition
41.Effetive use of word order for text categorization with convolutional neural network，Rie Johnson
42.Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation
43.Show and Tell: A Neural Image Caption Generator
44.Deep Image: Scaling up Image Recognition
https://www.sodocs.net/doc/1e14677733.html,rge-Scale High-Precision Topic Modeling on Twitter
46.A. Krizhevsky. One weird trick for parallelizing convolutional neural networks. arXiv:1404.5997, 2014
47.A Brief Overview of Deep Learning
48.Going deeper with convolutions. Christian Szegedy. Google Inc. 阅读笔记
49.Long Short-Term Memory Recurrent Neural Network Architectures for Large Scale Acoustic Modeling
50.Semi-Supervised Learning Tutorial
51.https://www.sodocs.net/doc/1e14677733.html,/question/24904450
52.LONG SHORT-TERM MEMORY BASED RECURRENT NEURAL NETWORK ARCHITECTURES FOR LARGE VOCABULARY SPEECH RECOGNITION
53.LSTM Neural Networks for Language Modeling
54.LONG SHORT-TERM MEMORY
55.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
56.AliasLDA
57.Gibbs sampling for the uninitiated
58.Learning classifiers from only positive and unlabeled data
59.TF-ICF: A New Term Weighting Scheme for Clustering Dynamic Data Streams
60.LDA数学八卦
61.Chinese Word Segmentation and Named Entity Recognition Based on Conditional Random Fields Models
62.Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data
63.Chinese Segmentation and New Word Detection using Conditional Random Fields
64.Gregor Heinrich. Parameter estimation for text analysis
65.Peacock：大规模主题模型及其在腾讯业务中的应用
66.L. Yao, D. Mimno, and A. McCallum. Efficient methods for topic model inference on streaming document collections. In KDD, 2009.
67.David Newman. Distributed Algorithms for Topic Models
68.Xuemin. LDA工程实践之算法篇
69.Brian Lott. Survey of Keyword Extraction Techniques
70.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.
71.刘知远. 基于文档主题结构的关键词抽取方法研究
72.Hinton. Reducing the Dimensionality of Data with Neural Networks
73.Samaneh Moghaddam. On the design of LDA models for aspect-based opinion mining；
74.The FLDA model for aspect-based opinion mining: addressing the cold start problem
75.Ross Girshick et. Rich feature hierarchies for accurate object
detection and semantic segmentation
76.J. Uijlings, K. van de Sande, T. Gevers, and A. Smeulders.
Selective search for object recognition. IJCV, 2013.
77.Baidu/UCLA: Explain Images with Multimodal Recurrent Neural
Networks
78.Toronto: Unifying Visual-Semantic Embeddings with Multimodal
Neural Language Models
79.Berkeley: Long-term Recurrent Convolutional Networks for Visual
Recognition and Description
80.Xinlei Chen et. Learning a Recurrent Visual Representation for
Image Caption Generation
81.Hao Fang et. From Captions to Visual Concepts and Back
82.Modeling Documents with a Deep Boltzmann Machine
83.A Deep Dive into Recurrent Neural Nets
84.Xiang zhang et. Text Understanding from Scratch
文章出处：语义分析的一些方法(一)
语义分析的一些方法(中篇)
人工智能林 16小时前192℃0评论
作者：火光摇曳
2 文本语义分析
前面讲到一些文本基本处理方法。一个文本串，对其进行分词和重要性打分后（当然还有更多的文本处理任务），就可以开始更高层的语义分析任务。
2.1 Topic Model
首先介绍主题模型。说到主题模型，第一时间会想到pLSA，NMF，LDA。关于这几个目前业界最常用的主题模型，已经有相当多的介绍了，譬如文献[60，64]。在这里，主要想聊一下主题模型的应用以及最新进展(考虑到LDA是pLSA的generalization，所以下面只介绍LDA)。
LDA训练算法简单介绍
LDA的推导这里略过不讲，具体请参考文献[64]。下面我们主要看一下怎么训练LDA。
在Blei的原始论文中，使用variational inference和EM算法进行LDA推断(与pLSA的推断过程类似，E-step采用variational inference)，但EM算法可能推导出局部最优解，且相对复杂。目前常用的方法是基于gibbs sampling来做[57]。
?Step1: 随机初始化每个词的topic，并统计两个频率计数矩阵：
Doc-Topic 计数矩阵N(t,d)，描述每个文档中的主题频率分布；Word-Topic 计数矩阵N(w,t)，表示每个主题下词的频率分布。
?Step2: 遍历训练语料，按照概率公式(下图所示)重新采样每个词所对应的topic, 更新N(t,d)和N(w,t)的计数。
?Step3: 重复 step2，直到模型收敛。
对文档d中词w的主题z进行重新采样的公式有非常明确的物理意义，表示为
P(w|z)P(z|d)，直观的表示为一个“路径选择”的过程。
图10. gibbs sampling过程图
以上描述过程具体请参考文献[65]。
对于LDA模型的更多理论介绍，譬如如何实现正确性验证，请参考文献[68]，而关于LDA模型改进，请参考Newman团队的最新文章《Care and Feeding of Topic Models》[12]。
主题模型的应用点
?在广点通内部，主题模型已经在很多方面都得到成功应用[65]，譬如文本分类特征，相关性计算，ctr预估，精确广告定向，矩阵分解等。具体来说，基于主题模型，可以计算出文本，用户的topic分布，将其当作pctr，
relevance的特征，还可以将其当作一种矩阵分解的方法，用于降维，推荐等。不过在我们以往的成功运用中，topic模型比较适合用做某些机器学习任务的特征，而不适合作为一种独立的方法去解决某种特定的问题，例如触发，分类。Blei是这样评价lda的：it can easily be used as a module in more complicated models for more complicated goals。
?为什么topic model不适合作为一种独立的方法去解决某种特定的问题(例如分类，触发等)。
o个人总结，主要原因是lda模型可控性可解释性相对比较差：对于
每个topic，不能用很明确的语义归纳出这个topic在讲什么；重新训
练一遍lda模型，每个topic id所对应的语义可能发生了变化；有些
topic的准确性比较好，有些比较差，而对于比较差的topic，没有特
别好的针对性的方法去优化它；
o另外一个就是topic之间的重复，特别是在topic数目比较多的情
况，重复几乎是不可避免的，当时益总(yiwang)在开发peacock的时候，
deduplicate topic就是一个很重要的任务。如果多个topic描述的意
思一致时，用topic id来做检索触发，效果大半是不好的，后来我们
也尝试用topic word来做，但依旧不够理想。
主题模型最新进展
首先主题模型自PLSA, LDA后，又提出了很多变体，譬如HDP。LDA的topic number 是预先设定的，而HDP的topic number是不固定，而是从训练数据中学习得到的，这在很多场景是有用的，具体参考hdp vs lda。想了解更多LDA模型的升级，请参考文献[73,74]。
深度学习方面，Geoff Hinton及其学生用Deep Boltzmann Machine研究出了类似LDA的隐变量文本模型[82]，文章称其抽取的特征在文本检索与文本分类上的结果比LDA好。heavenfireray在其微博评论道：lda结构是word-hidden topic。类lda结构假设在topic下产生每个word是条件独立而且参数相同。这种假设导致参数更匹配长文而非短文。该文章提出word-hidden topic-hidden word，其实是(word,hidden word)-hidden topic，增加的hidden word平衡了参数对短文的适配，在分类文章数量的度量上更好很自然。
其次，随着目前互联网的数据规模的逐渐增加，大规模并行PLSA，LDA训练将是主旋律。大规模主题模型训练，除了从系统架构上进行优化外，更关键的，还需要在算法本身上做升级。variational方法不太适合并行化，且速度相对也比较慢，这里我们着重看sampling-base inference。
?collapsed Gibbs sampler[57]：O(K)复杂度，K表示topic的总个数。
?SparseLDA[66]：算法复杂度为O(Kd + Kw)，Kd表示文档d所包含的topic 个数，Kw表示词w所属的topic个数，考虑到一个文档所包含的topic和一个词所属的topic个数是有限的，肯定远小于K，所以相比于collapsed Gibbs，复杂度已有较大的下降。
?AliasLDA[56]：利用alias table和Metropolis-Hastings，将词这个维度的采样复杂度降至O(1)。所以算法总复杂度为O(Kd)。
?Metropolis-Hastings sampler[13]：复杂度降至O(1)。这里不做分析了，具体请参考文献[13]
主题模型并行化
在文献[67]中，Newman团队提出了LDA算法的并行化版本Approximate distributed-LDA，如下图所示：
图11. AD-LDA算法
在原始gibbs sampling算法里，N(w,t)这个矩阵的更新是串行的，但是研究发现，考虑到N(w,t)矩阵在迭代过程中，相对变化较小，多个worker独立更新
N(w,t)，在一轮迭代结束后再根据多个worker的本地更新合并到全局更新
N(w,t)，算法依旧可以收敛[67]。
那么，主题模型的并行化(不仅仅是主题模型，其实是绝大部分机器学习算法)，主要可以从两个角度来说明：数据并行和模型并行。
?数据并行。这个角度相对比较直观，譬如对于LDA模型，可以将训练数据按照worker数目切分为M片(M为worker数)，每个worker保存一份全局的N(w,t)矩阵，在一轮迭代里，各个worker独立计算，迭代结束后，合并各个worker的本地更新。这个思路可以借用目前通用的并行计算框架，譬如Spark，Hadoop，Graphlab等来实现。
?模型并行。考虑到矩阵N(w,t)在大规模主题模型中相当巨大，单机内存不可能存下。所以直观的想法，可以将N(w,t)也切分成多个分片。N(w,t)可以考虑使用全局的parameter server来存储，也可以考虑存储在不同
worker上，利用MPI AllReduce来通信。
数据与模型并行，可以形象的描述为一个棋盘。棋盘的行按照数据划分，棋盘的列按照模型划分。LDA的并行化，就是通过这样的切分，将原本巨大的，不可能
在单机存储的矩阵切分到不同的机器，使每台机器都能够将参数存储在内存。再接着，各个worker相对独立计算，计算的过程中不时按照某些策略同步模型数据。
最近几年里，关于LDA并行化已有相当多的开源实现，譬如：
?PLDA，PLDA+
?Yahoo LDA
?Parameter server
最近的并行LDA实现Peacock[70,65]和LigthLda[13]没有开源，但我们可以从其论文一窥究竟，总体来说，并行化的大体思路是一致的。譬如LightLDA[13]，下图是实现架构框图，它将训练数据切分成多个Block，模型通过parameter server来同步，每个data block，类似于sliding windows，在计算完V1的采样后，才会去计算V2的采样(下图中V1,V2,V3表示word空间的划分，即模型的划分)。
图12. LightLda并行结构图
2.2 词向量，句向量
词向量是什么
在文本分析的vector space model中，是用向量来描述一个词的，譬如最常见的One-hot representation。One-hot representation方法的一个明显的缺点是，词与词之间没有建立关联。在深度学习中，一般用Distributed Representation来描述一个词，常被称为“Word Representation”或“Word Embedding”，也就是我们俗称的“词向量”。
词向量起源于hinton在1986年的论文[11]，后来在Bengio的ffnnlm论文[3]中，被发扬光大，但它真正被我们所熟知，应该是word2vec[14]的开源。在ffnnlm 中，词向量是训练语言模型的一个副产品，不过在word2vec里，是专门来训练词向量，所以word2vec相比于ffnnlm的区别主要体现在：
?模型更加简单，去掉了ffnnlm中的隐藏层，并去掉了输入层跳过隐藏层直接到输出层的连接。
?训练语言模型是利用第m个词的前n个词预测第m个词，而训练词向量是用其前后各n个词来预测第m个词，这样做真正利用了上下文来预测，如下图所示。
图13. word2vec的训练算法
上图是word2vec的两种训练算法：CBOW(continuous bag-of-words)和
Skip-gram。在cbow方法里，训练目标是给定一个word的context，预测word 的概率；在skip-gram方法里，训练目标则是给定一个word，预测word的context 的概率。
关于word2vec，在算法上还有较多可以学习的地方，例如利用huffman编码做层次softmax，negative sampling，工程上也有很多trick，具体请参考文章[16][17]。
语义分析
语义分析 1.语义分析？ 机器机和人不一样的地方是人可以直接理解词的意思，文章的意思，机器机不能理解。 人看到苹果这两个字就知道指的是那个圆圆的，挺好吃的东西，搜索引擎却不能从感性上理解。但搜索引擎可以掌握词之间的关系，这就牵扯到语义分析。 可参考：https://www.sodocs.net/doc/1e14677733.html,/dispbbs.asp?boardID=2&ID=74541 2.为什么要使用语义分析？ 我国中文自然语言处理普遍采用西基于拉丁语系的“关键词”技术，以此来分析理解中文。然而，中文本身的特点决定它与西语之间巨大的区别，所以从汉语信息处理的需要看，当前急迫需要突破的是语义问题。 可参考： https://www.sodocs.net/doc/1e14677733.html,/dicksong2008/blog/item/88fb751e9ac9501a4134 17f4.html 2.1中文与西语不同决定我们无法采用西语的架构体系来处理中文，具体区别在于： 西语词间有间隔，汉语词间无间隔。众所周知，英文是以词为单位的，词和词之间是靠空格隔开，而中文是以字为单位，句子中所有的字连起来才能描述一个意思。 例如，英文句子I am a student，用中文则为：“我是一个学生”。计算机可以很简单通过空格知道student是一个单词，但是不能很容易明白“学”、“生”两个字合起来才表示一个词。把中文的汉字序列切分成有意义的词，就是中文分词，有些人也称为切词。 “我是一个学生”，分词的结果是：“我是一个学生”。中文分词就成了计算机处理的难题。 汉语形态不发达，句尾没有形态标记。英语动词、名词很清楚，加上词尾可以是副词；西语有时态，过去式、现在式等等非常清楚，中文则依靠词语或者依靠自己的判断来确定时态。 同音字多增加了机器识别的难度。 汉语语义灵活，由于形态不发达，所以语序无规律。在一次学术会议上，一位著名的人工智能专家说：“按…主－谓－宾?或…名－动－名?这一规则，计算机可显出…牛吃草?，也可显出…草吃牛?。从语法格式上看，…草吃牛?也不错，但这句话是说不通的。 人依靠自己的经验可以判断，机器如何来判断呢？
编译原理语义分析实验报告——免费!
语义分析实验报告 一、实验目的： 通过上机实习，加深对语法制导翻译原理的理解，掌握将语法分析所识别的语法成分变换为中间代码的语义翻译方法。 二、实验要求： 采用递归下降语法制导翻译法，对算术表达式、赋值语句进行语义分析并生成四元式序列。 三、算法思想： 1、设置语义过程。 （1）emit(char *result,char *ag1,char *op,char *ag2) 该函数的功能是生成一个三地址语句送到四元式表中。 四元式表的结构如下： struct { char result[8]; char ag1[8]; char op[8]; char ag2[8]; }quad[20]; (2) char *newtemp() 该函数回送一个新的临时变量名，临时变量名产生的顺序为T1，T2，… char *newtemp(void) { char *p; char m[8]; p=(char *)malloc(8); k++; itoa(k,m,10); strcpy(p+1,m); p[0]=’t’; return(p); } 2、函数lrparser 在原来语法分析的基础上插入相应的语义动作：将输入串翻译成四元式序列。在实验中我们只对表达式、赋值语句进行翻译。
四、源程序代码： #include
编译原理知识点汇总
编译原理的复习提纲 1.编译原理=形式语言+编译技术 2.汇编程序： 把汇编语言程序翻译成等价的机器语言程序 3.编译程序： 把高级语言程序翻译成等价的低级语言程序 4.解释执行方式： 解释程序，逐个语句地模拟执行 翻译执行方式： 翻译程序，把程序设计语言程序翻译成等价的目标程序 5.计算机程序的编译过程类似，一般分为五个阶段： 词法分析、语法分析、语义分析及中间代码生成、代码优化、目标代码生成 词法分析的任务： 扫描源程序的字符串，识别出的最小的语法单位（标识符或无正负号数等） 语法分析是： 在词法分析的基础上的，语法分析不考虑语义。语法分析读入词法分析程序识别出的符号，根据给定的语法规则，识别出各个语法结构。 语义分析的任务是检查程序语义的正确性，解释程序结构的含义，语义分析包括检查变量是否有定义，变量在使用前是否具有值，数值是否溢出等。
语法分析完成之后，编译程序通常就依据语言的语义规则，利用语法制导技术把源程序翻译成某种中间代码。所谓中间代码是一种定义明确、便于处理、独立于计算机硬件的记号系统，可以认为是一种抽象机的程序 代码优化的主要任务是对前一阶段产生的中间代码进行等价变换，以便产生速度快、空间小的目标代码 编译的最后一个阶段是目标代码生成，其主要任务是把中间代码翻译成特定的机器指令或汇编程序 编译程序结构包括五个基本功能模块和两个辅助模块 6.编译划分成前端和后端。 编译前端的工作包括词法分析、语法分析、语义分析。编译前端只依赖于源程序，独立于目标计算机。前端进行分析 编译后端的工作主要是目标代码的生成和优化后端进行综合。独立于源程序，完全依赖于目标机器和中间代码。 把编译程序分为前端和后端的优点是： 可以优化配置不同的编译程序组合，实现编译重用，保持语言与机器的独立性。 7.汇编器把汇编语言代码翻译成一个特定的机器指令序列 第二章 1.符号，字母表，符号串，符号串的长度计算P18，子符号串的含义，符号串的简单运算XY，Xn， 2.符号串集合的概念，符号串集合的乘积运算，方幂运算，闭包与正闭包的概念P19，P20A0 ={ε} 3.重写规则，简称规则。非xx（V
句法结构中的语义分析
句法结构中的语义分析 学习要点：掌握句法结构分析中运用语义关系、语义指向、语义特征三种语义分析方法，并且能够运用这些分析法解释一些常见的语言现象。 句法结构是句法形式和语义内容的统一体。对句法结构不仅要做形式分析，如句法层次分析、句法关系分析、以及句型分析等，还要做种种语义分析。句法结构中的语义分析主要指语义关系、语义指向、语义特征三种分析法。 一、语义关系 （一）句法关系和语义关系 在句法结构中，词语与词语之间不仅发生种种语法关系，主谓、述补、述宾、偏正、联合等，而且发生种种语义关系。语义关系，语义学中指语言成分所表示的客观对象之间的关系，我们所说的语义关系是指动作和动作者、动作和受动者、动作和工具、动作和处所、事物和事物之间的关系等。句法关系和语义关系可能一致，也可能不一致。 ⑴吃面条。/削苹果。(句法、语义关系一致。) ⑵我吃完了。/饼干吃完了。/文章写好了。(句法、语义关系不一致) 前者“我”与“吃”是动作者（施事）和动作的关系，后者“饼干”和“吃”是受动者（受事）和动作的关系，结果和动作的关系。 一种句法结构关系，可能包含着多种语义关系，如：修理家具。/挖了一个坑。/来了一个客人。/写毛笔。(述宾关系，受事、结果、施事、工具。)反之，一种语义关系也可能构成多种句法结构关系。 ⑶沙发上坐着一个人。 ⑷那个人坐在沙发上。 ⑸那个人在沙发上坐着。 这几个句法结构的语义关系基本相同，“人”“沙发上”与“坐”之间都是“施事”“处所”与“动作”的关系；但句法结构关系却不一样。 （二）动词和名词语义关系的类别 汉语句法结构中的语义关系是多种多样的，句法分析的重点是动词跟名词性词语之间的语义关系。在各种语义关系中，名词性成分担任了一定的语义角色，如“受事、结果、施事、工具”等，这实际上也就是揭示了名词性成分跟动词之间的关系。名词性词语经常担任的语义角色主要有： 1、施事：指动作的发出者（可用介词“被、叫、让、给”引进） 他在看书。/小狗啃完了骨头。/敌人被我们打败了。 2、受事：指动作行为的承受者（可用介词“把、将”引进）。 小牛吃草。/张三修桌子。/毛把花瓶打碎了。 3、系事：指连系动词联接的对象（？） 我们是教师。/小王成了大学生。 4、与事：指动作行为的间接的承受者（送、还？）（可用介词“给”引进）。 张三还李四一支笔。/我给兰兰送去一些巧克力。 5、结果：指动作行为产生的结果。 编草帽。/烙饼。/做烟斗。/打毛衣。/盖大楼。
基于潜在语义分析的JAVA类库检索方法
文章编号:10035850(2006)03004302 基于潜在语义分析的Java类库检索方法Java Class Library Retrieval Method based on Latent Semantic Analysis 刘 磊 (大连理工大学软件学院 大连 116023) 【摘 要】为了更精确、有效地检索Jav a类库,应用潜在语义分析的理论,设计了基于潜在语义分析的Java类库的检索方法,提高了对Java类库的检索质量。基于潜在语义分析的理论和方法可以适用于大多数的检索系统,对提高检索系统的检索精确性有很大的帮助。 【关键词】潜在语义分析,信息检索,Jav a类库检索方法 中图分类号:T P312 文献标识码:A ABSTRACT Fo r sear ching in jav a class libr ary mo re accur ately,this paper designs a r etr ieval method o f jav a class librar y based on L SA(L at ent sem ant ic A naly sis)o n the basis of semantic ana ly sis theor y.T his method impr oves t he sear ching quality of jav a class librar y and can be used in mo st of sear ching system,and is helpful to impro ve the sear ching accur acy o f retr iev al sy st em. KEYWORDS L SA,infor matio n retr iev al,java libr ary ret riev al method 信息的检索一直是大家研究的热门话题,人们对如何实现快捷准确的搜索功能进行了广泛的研究。本文探讨搜索对象Java类库是Java开发平台提供的开发文档,也是学习Java语言的主要文档。Jav a类库有着非常规则的结构,这对非常熟悉Java的开发人员来说是非常便利的,但是对于初学者来说,如何找到相应类的介绍却是非常困难的。所以快速高效率的Java类库检索方法有一定的现实实用价值。 传统的查询方法基于文本关键字的向量空间模型VSM(Vector Space M odel),是用m个关键字维构成的文档向量D i={d1i,d2i,...,d mi}表示文档集中的一个文档,并基于此进行文档过滤,检索的处理。它将非结构化的文本表示成向量的形式,使得各种数学处理成为可能。它的优点是简单、快捷。但是向量空间模型关于词间相互独立的假设很难满足,文中出现的词往往存在一些相关性,在某种程度上影响计算结果,同时,这种基于关键字的处理方法主要依据词频信息,两个文本的相似度取决于它们拥有的共同词汇的数量,因而无法分辨自然语言的语义模糊性[2]。 参考文献[1]中采用了上面的VSM方法表示Java 类库各可复用模块的语义,本文采用基于潜在语义分析的Java类库检索方法,对其进行改进。 潜在语义分析的出发点就是文本中词与词之间存在某种联系,及存在某种潜在的语义结构,这种潜在的语义结构隐含在文本中词语的上下文使用模式中,因此采用统计计算的方法,对文本进行分析,寻找这种潜在的语义结构,不需要确定语义的编码,仅依赖于上下文中事务的联系,并用语义结构表示词和文本,达到消除词之间的相关性简化文本向量的目的。 三维潜在语义空间示例如图1 所示。 传统的空间向量方法假设词语语义是相互独立的,每个词语被看作向量空间中的一个正交基本向量,实际上词语之间存在着很强的关联性及出现“斜交”的现象,影响文本处理的结果。LSA利用这种关联性,通过对文本集中词语的上下文的使用模式进行统计转换,获得一个新的、低维的语义空间[3]。SVD是目前普遍使用的典型的LSA空间构造方法。它通过对文本集的词-文本矩阵的奇异值分解计算,提取k个最大的奇异值及其对应的奇异矢量构成新矩阵来近似表示原文本集的词条-文本矩阵。具体步骤如下: 首先,构造一个训练集m*n词条-文本矩阵A=[a ij]mn,其中a ij=L(i,j)*G(i),L(i,j)是单词i在文本j中的局部权重,G(i)是单词i在文本集中的全局权重,m为提取单词数,n为文本数。 其次,对A进行截取SVD分解(设m>n, rank(A)=r,存在k,k 现代汉语语法的五种分析方法 现代汉语语法的五种分析方法 很有用，请好好学习之。 北语之声论坛专业精华转贴 现代汉语语法的五种分析方法是语法学基础里 很重要的一个内容,老师上课也会讲到,我在这 里把最简略的内容写在下面，希望能对本科生的专业课学习有所帮助 详细阐释中心词分析法、层次分析、变换分析法、语义特征分析法和语义指向分析的具体内涵：一. 中心词分析法： 分析要点： 1．分析的对象是单句； 2．认为句子又六大成分组成——主语、谓语（或述语）、宾语、补足语、形容词附加语（即定语）和副词性附加语（即状语和补语）。 这六种成分分为三个级别：主语、谓语（或述语）是主要成分，宾语、补足语是连 带成分，形容词附加语和副词性附加语是附加成分； 3．作为句子成分的只能是词； 4．分析时，先找出全句的中心词作为主语和谓 语，让其他成分分别依附于它们； 5．分析步骤是，先分清句子的主要成分，再决定有无连带成分，最后指出附加成分。 标记： 一般用║来分隔主语部分和谓语部分，用══标注主语，用——标注谓语，用~~~~~~标注宾语，用（）标注定语，用[ ]标注状语，用< >标注补语。 作用： 因其清晰明了得显示了句子的主干，可以一下子把握住一个句子的脉络，适合于中小学语文教学，对于推动汉语教学语法的发展作出了很大贡献。 还可以分化一些歧义句式。比如：我们五个人一组。 （1）我们║五个人一组。（2）我们五个人║一组。 总结：中心词分析法可以分化一些由于某些词或词组在句子中可以做不同的句子成分而造成的歧义关系。 局限性： 1．在一个层面上分析句子， 层次性不强； 2．对于一些否定句和带有修饰成分的句子，往往难以划分； 如：我们不走。≠我们走。 封建思想必须清除。≠思想清除。 3. 一些由于句子的层次关系 不同而造成的歧义句子无法分析； 如：照片放大了一点儿。咬死了猎人的狗。 二. 层次分析： 含义： 在分析一个句子或句法结构时，将句法构造的层次性考虑进来，并按其构造层次逐层进行分析，在分析时，指出每一层面的直接组成成分，这种分析就叫层次分析。 朱德熙先生认为，层次分析不能简单地将其看作是一种分析方法，而是应当看做一种分析原则，是必须遵守的。（可以说说为什么） 层次分析实际包含两部分内容：一是切分，一是定性。切分，是解决一个结构的直接组成成分到底是哪些；而定性，是解决切分所得的直接组成成分之间在句法上是什么关系。 自动浅层语义分析 车万翔，刘挺，李生 （哈尔滨工业大学计算机学院信息检索实验室，哈尔滨 150001） E-mail: {car, tliu, lisheng}@https://www.sodocs.net/doc/1e14677733.html, 摘要 全自动的语义分析一直是自然语言理解的主要目标之一。通过深层语义分析，可以将自然语言转化为形式语言，从而使计算机能够与人类无障碍的沟通。为达此目的，人们已经进行了多年的努力，然而目前取得的效果并不理想。浅层语义分析是对深层语义分析的一种简化，它只标注与句子中谓词有关的成份的语义角色，如施事、受事、时间和地点等。其能够对问答系统、信息抽取和机器翻译等应用产生推动作用。语义角色标注是浅层语义分析的一种实现方式，具有定义清晰，便于评价的优点。本文描述了浅层语义分析现有的语料库资源，各种分析方法，以及我们的工作等。并提出了对该任务一些难点问题的解决方案和对浅层语义分析发展的一个初步展望。 关键词：自然语言理解；浅层语义分析；语义角色标注； Shallow Semantic Parsing Wanxiang Che, Ting Liu, Sheng Li （Information Retrieval Lab, School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001） Abstract: Automatic semantic parsing is one of the main tasks for the natural language understanding. The natural language sentences can be translated into formal language by deep semantic paring. Consequently computer and human beings can communicate with each other freely. In order to achieve the dream, people have done lots of efforts for many years. However the results are not up to much. Shallow semantic parsing is a simplified form of deep semantic parsing. It only labels the constituents with semantic roles which have direct relation with the predicate in a sentence. The semantic roles include Agent, Patient, Temporal, Locative and so on. In addition, it can give great support to many NLP applications, such as information extraction, question and answering, machine translation and so on. Semantic role labeling (SRL) is one kind of shallow semantic paring. It is currently a well defined task with a substantial body of work and comparative evaluation. In the paper, we investigate the corpus for SRL, the paring methods, and our previous work. At last, some proposals to solving the difficulties in shallow semantic parsing and some future work are given. Kerwords: Natural language understanding; Shallow semantic parsing; Semantic role labeling 词法分析 #include ch=s[--p]; syn=10; for(n=0;n<6;n++) if(strcmp(token,r[n])==0) { syn=n+1; break; } } void digit(bool positive)//数字的判断{ len=sum=0; ch=s[p]; while(ch>='0' && ch<='9') { sum=sum*10+ch-'0'; ch=s[++p]; } if(ch=='.') { dsum=sum; ch=s[++p]; pos=0.1; while(ch>='0' && ch<='9') { dsum=dsum+(ch-'0')*pos; pos=pos*0.1; ch=s[++p]; } if(ch=='e') { index[len++]=ch; ch=s[++p]; if(ch=='-' || ch=='+') { index[len++]=ch; ch=s[++p]; } if(!(ch>='0' && ch<='9')) { syn=-1; } else 语义分析的一些方法 语义分析的一些方法(上篇) 5040 语义分析，本文指运用各种机器学习方法，挖掘与学习文本、图片等的深层次概念。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. “南京市长江大桥”语言模型得分 义素分析法分析“看的方式”语义场 摘要：“看的方式”的语义场可以归为同义语义场。通过义素分析的方法，并写出 每个词的基本义的义素表达式，来分析该语义场内的词之间的异同。词不仅有理 性意义还有感性意义，通过感性意义能更好的区别和运用同义词。 关键字：义素分析法，同义词辨析，看的方式 一、义素分析法在同义词辨析中的运用 同义词辨析一直以来都是语言研究的重要方面，不仅是在语言研究，还是在 语言运用中，甚至在语言的教学中都具有特殊的意义。义素分析法是准确描写和 掌握词义的有效方法。词义并不是一个整体，而是有若干层次的结构，义素是构 成词义的最小意义单位。将义素分析法引入对外汉语词汇教学，可以对词义的微 观层面进行准确有效的分析，把词义分割成若干个义素的组合，不仅有利于准确 掌握同义词之间的大同小异，还能提高人们对语言的运用能力，有利于第二语言 学习者在语言学习中理解两个及两个以上抽象的同义词，加深对汉语词汇的理解 和运用。 本文主要通过义素分析法来分析比较“看的方式”的语义场，来说明义素分析 法在同义词比较中的运用。运用义素分析法的表达式来研究“看的意义相同或相近的词”。本文研究的看的方式词有：看、望、顾、瞪、瞥、瞅、盯、窥、伺、瞟、瞰。 二、“看的方式”的语义场义素分析的方法和步骤 1.确立语义场 语义场是通过不同词之间的对比，根据它们词义的共同特点或关系划分出来 的类。同义语义场相当于一些论著中讲的一组广义的同义词（即不包括等义词），它所包括的各个义位间大同小异。所谓的同，表现为基本义相同或者是基本义有 一部分相同。所谓的异，就是附加义不同，或者是基本义有一部分不同，又或是 不只是基本义有一部分不同附加义也不一样。“看的方式”语义场内的词是眼部动 作描写都有“用眼睛看”这一基本义项，因此，这些看的方式词都可以看作是“看” 这个词的同义词。那么“看的方式”就构成了一个眼部动作的同义语义场。根据义 素分析法的分析并通过表达式的比较，可以准确的辨析出同义语义场内各个词之 间的细微区别，有利于第二语言的学习。 2.通过义素的具体对比分析“看的方式：看、望、顾、瞪、瞥、瞅、盯、窥、伺、瞟、瞰”的异同。 这些字从现代汉语词典第七版中查到“看的方式”词的意义如下所示： (1)看： [动] 使视线接触人或物：~书|~电影|~了他一眼。 [动] 观察并加以判断：我~他是个可靠的人l你~这个办法好不好。 [动] 取决于；决定于：这件事能 不能成功全~你了|飞机能否准时起飞，要~天气如何。 [动] 访问；探望：~望|~朋友。 [动] 对待：~待|另眼相~|别拿我当外人~。 [动] 诊治：王大夫把我的病~好了。照料：照~l衣帽自~。 [动] 用在表示动作或变化的词或词组前面，表示预见到某 种变化趋势，或者提醒对方注意可能发生或将要发生的某种不好的事情或情况： 行情~涨|别跑！~摔着！|~饭快凉了，快吃吧。 [助] 用在动词或动词结构后面， 表示试一试（前面的动词常用重叠式）：想想~I找找~|等一等~l评评理~先做几 天~。 (2)望： [动] 向远处看：登山远~|一~无际的稻田。观看；察看：~风！观~|~ 闻问切。探望：拜~|看~。盼望；希望①：~子成龙l~准时到会。盼头；希望②： 三、词法、语法、语义分析结合 一、实验目的与要求 在实现词法、语法分析程序的基础上，编写相应的语义子程序，进行语义处理，加深对语法制导翻译原理的理解，进一步掌握将语法分析所识别的语法范畴变换为某种中间代码（四元式）的语义分析方法，并完成相关语义分析器的代码开发。 二、实验内容 语法制导翻译模式是在语法分析的基础上，增加语义操作来实现的。对于给定文法中的每一产生式，编写相应的语义子程序。在语法分析过程中，每当用一个产生式进行推导或归约时，语法分析程序除执行相应的语法分析动作之外，还要调用相应的语义子程序，以便完成生成中间代码、查填有关表格、检查并报告源程序中的语义错误等工作。每个语义子程序需指明相应产生式中各个符号的具体含义，并规定使用该产生式进行分析时所应采取的语义动作。这样，语法制导翻译程序在对源程序从左到右进行的一遍扫描中，既完成语法分析任务，又完成语义分析和中间代码生成方面的工作。 输入：包含测试用例，如由无符号数和+、?、*、/、(、)构成的算术表达式的源程序文件。 输出：将源程序转换为中间代码形式表示，并将中间代码序列输出到文件中。若源程序中有错误，应指出错误信息。 三、实验设计 语法制导翻译模式实际上是对前后文无关文法的一种扩展。一般而言，首先需要根据进行的语义工作，完成对文法的必要拆分和语义动作的编写，从而为每个产生式都配备相应的语义子程序，以便在进行语法分析的同时进行语义解释。要求从编译器的整体设计出发，重点通过对实验二中语法分析程序的扩展，完成一个编译器前端程序的编写、调试和测试工作，形成一个将源程序翻译为中间代码序列的编译系统。 对文法G3[<算术表达式>]中的产生式添加语义处理子程序，完成无符号数的四则运算的计值处理，将输入的四则运算转换为四元式形式的中间代码。本实验只进行了算术表达式四元式的翻译。 四、源代码 1、在.h文件中添加了 //语义分析部分 #define PMAX 5//define 后面不加括号，定义产生式符号属性字符串的长度 int NXQ=0; /*全局变量NXQ用于指示所要产生的下一个四元式的编号*/ int NXTemp=1;//整型变量NXTemp指示临时变量的编号 int SentenceCount=1;//存放文件中句子的个数 struct QUATERNION /*四元式表的结构*/ { char op[PMAX]; /*操作符*/ char arg1[PMAX]; /*第一个操作数*/ char arg2[PMAX]; /*第二个操作数*/ char result[PMAX]; /*运算结果*/ }pQuad[256]; /*存放四元式的数组*/ char EBracket_Place[PMAX];//(E)的语义属性 《编译原理》总复习-07级 第一章编译程序的概述 （一）内容 本章介绍编译程序在计算机科学中的地位和作用，介绍编译技术的发展历史，讲解编译程序、解释程序的基本概念，概述编译过程，介绍编译程序的逻辑结构和编译程序的组织形式等。 （二）本章重点 编译（程序），解释（程序），编译程序的逻辑结构。 （三）本章难点 编译程序的生成。 （四）本章考点 全部基本概念。 编译程序的逻辑结构。 （五）学习指导 引论部分主要是解释什么是编译程序以及编译的总体过程。因此学习时要对以下几个点进行重点学习：翻译、编译、目标语言和源语言这几个概念的理解；编译的总体过程：词法分析，语法分析、语义分析与中间代码的生成、代码优化、目标代码的生成，以及伴随着整个过程的表格管理与出错处理。 第三章文法和语言课外训练 （一）内容 本章是编译原理课程的理论基础，主要介绍与课程相关的形式语言的基本概念，包括符号串的基本概念和术语、文法和语言的形式定义、推导与归约、句子和句型、语法分析树和二义性文法等定义、文法和语言的Chomsky分类。 （二）本章重点 上下文无关文法，推导，句子和句型，文法生成的语言，语法分析树和二义性文法。（三）本章难点 上下文无关文法，语法分析树，文法的分类。 （四）本章考点 上下文无关文法的定义。 符号串的推导。 语法分析树的构造。 （五）学习指导 要构造编译程序，就要把源语言用某种方式进行定义和描述。学习高级语言的语法描述是学习编译原理的基础。上下文无关文法及语法树是本章学习的重点。语法与语义的概念；程序的在逻辑上的层次结构；文法的定义，文法是一个四元组：终结符号集，非终结符号集，开始符号、产生式集；与文法相关的概念，字符，正则闭包，积（连接），或，空集，产生式，推导，直接推导，句子，句型，语言，最左推导，最右推导（规范推导）；学会用文法来描述语言及通过文法能分析该文法所描述的语言；语法树及二义性的概念、能通过画语法树来分析一个文法描述的语言是否具有二义性；上下文无关文法的定义和正规文法的定义，能判断一个语言的文法是哪一类文法。 附训练试题： 《编译原理》课后习题答案第一章 第 1 章引论 第 1 题 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 答案： （1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2）源程序：源语言编写的程序称为源程序。 （3）目标程序：目标语言书写的程序称为目标程序。 （4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。 （6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第 2 题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程 序的总体结构图。 答案： 一个典型的编译程序通常包含 8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机表达形式。 语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。 中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式 的中间语言代码，如三元式或四元式。 中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。 目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。 表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的 各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。 错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源 上海电力学院 编译原理 课程实验报告 实验名称：实验三自下而上语法分析及语义分析 院系：计算机科学和技术学院 专业年级： 学生姓名：学号： 指导老师： 实验日期： 实验三自上而下的语法分析 一、实验目的： 通过本实验掌握LR分析器的构造过程，并根据语法制导翻译，掌握属性文法的自下而上计算的过程。 二、实验学时： 4学时。 三、实验内容 根据给出的简单表达式的语法构成规则（见五），编制LR分析程序，要求能对用给定的语法规则书写的源程序进行语法分析和语义分析。 对于正确的表达式，给出表达式的值。 对于错误的表达式，给出出错位置。 四、实验方法 采用LR分析法。 首先给出S-属性文法的定义（为简便起见，每个文法符号只设置一个综合属性，即该文法符号所代表的表达式的值。属性文法的定义可参照书137页表6.1），并将其改造成用LR分析实现时的语义分析动作（可参照书145页表6.5）。 接下来给出LR分析表。 然后程序的具体实现： ● LR分析表可用二维数组（或其他）实现。 ●添加一个val栈作为语义分析实现的工具。 ●编写总控程序，实现语法分析和语义分析的过程。 注：对于整数的识别可以借助实验1。 五、文法定义 简单的表达式文法如下： (1)E->E+T (2)E->E-T (3)E->T (4)T->T*F (5)T->T/F (6)T->F (7)F->(E) (8)F->i 状态ACTION（动作）GOTO（转换） i + - * / ( ) # E T F 0 S5 S4 1 2 3 1 S6 S1 2 acc 2 R 3 R3 S7 S13 R3 R3 3 R6 R6 R6 R6 R6 R6 4 S 5 S4 8 2 3 5 R8 R8 R8 R8 R8 R8 6 S5 S4 9 3 7 S5 S4 10 8 S6 R12 S11 9 R1 R1 S7 S13 R1 R1 10 R4 R4 R4 R4 R4 R4 11 R7 R7 R7 R7 R7 R7 12 S5 S4 14 3 13 S5 S4 15 14 R2 R2 S7 S13 R2 R2 15 R5 R5 R5 R5 R5 R5 五、处理程序例和处理结果例 示例1：20133191*(20133191+3191)+ 3191# 舆情监控--语义分析解决方案概述 舆情监控中极为关键的一个环节是进行语义分析，只有让计算机能“理解”从各目标网站上抓取的内容，才有可能得出对有关舆情的正确判断；从广义上来说，这项技术可归属于计算机人工智能技术领域；本团队在此领域有独到的优势，在借鉴行业内各种流行方案的基础上，融合了团队在实际开发过程中积累的经验。 整体上说，舆情监控中的语义分析涉及到的关键技术环节有以下两个： 1 中文分词 中文分词的主要困难在于分词歧义，例如：“结婚的和尚未结婚的”，应该分成“结婚／的／和／尚未／结婚／的”，还是“结婚／的／和尚／未／结婚／的”？人来判断很容易，要交给计算机来处理就麻烦了。问题的关键就是，“和尚未”里的“和尚”也是一个词，“尚未”也是一个词，从计算机的角度看上去，两者似乎都有可能。对于计算机来说，这样的分词困境就叫做“交集型歧义”。计算机分词中所遭遇的困境除了“交集型歧义”外，还有许许多多；相应的解决方案也数不胜数，如“最大匹配法”、“自动分词法”、“特殊规则修正法”等，但这些算法大多都是从语言学的角度对分词进行研究，对划分方案的评价标准都是基于每个词固有的性质，完全不考虑相邻词语之间的影响；因而一旦涉及到组合型歧义的问题，最大匹配、最少词数、概率最大等所有策略都不能实现具体情况具体分析，分词效果存在明显缺陷； 本团队在实际开发中采用的是该领域最新的研究成果，即Google 黑板报上提到的统计语言模型算法，对于任意两个词语w1、w2，统计在语料库中词语w1后面恰好是w2的概率P(w1, w2) 。这样便会生成一个很大的二维表。再定义一个句子的划分方案的得分为P(?, w1) · P(w1, w2) · … · P(w n-1, wn) ，其中w1, w2, …, w n依次表示分出的词。我们同样可以利用动态规划求出得分最高的分词方案。 2 内容语义的解析 在上述对内容分词的基础之上，进行话题发现与追踪、内容倾向性分析；这两个部分分别概述如下： （1）网民讨论的话题繁多，涵盖社会方方面面，如何从海量信息中找到热点、敏感话题，并对其趋势变化进行追踪成为研究热点。早期的Allan James、J. Allan、G.Hulten、Qiaozhu Mei等人的研究思路是基于文本聚类，即文本的关键词作为文本的特征。这种方法虽然能将一个大类话题下的文本进行聚合，但没有保证话题的可读性与准确性。本团队在此思路的基础上进行改进，实现了话题发现与追踪：即将文本聚类问题转换为话题特征聚类问题，并依据事件对语言文本信息流进行重新组织与利用。 （2）网络舆情倾向性分析技术：通过倾向性分析可以明确网络传播者所蕴涵的感情、态度、观点、立场、意图等主观反映。对舆情文本进行倾向性分析，实际上就是用计算机实现根据文本的内容提炼出文本作者的情感方向的目标。本团队致力于网络舆情文本的倾向性分析技术：通过判断网络环境下倾向性特征词的特点和类型，并进行语气极性判别和标注，从而构建一个面向互联网的倾向性语气词典，建设一定规模的标准数据集，为中文倾向性分 语义特征分析 一、含义 ?语义特征是语言单位之间相互联系或相互区别的语义要素，它很大程度上制约着语言单位相互组合的可能性以及组合的方式，反映了语言单位的组织形式跟现实世界的对应关系。 ?语义特征分析为进一步分化同形句式，为根据句法研究的需要对同一类实词划分小类，提供了更为可靠的句法、语义依据，因此语义特征分析无疑使语法研究朝着形式和意义相结合的方式迈出了更可喜的一步 二、作用 ?语义特征分析能够促使语法研究的精密化，从而使语法研究更具解释力。20世纪80年代以来，语义特征分析在汉语语法研究中得到了广泛的运用。除朱德熙以外，陆俭明、邢福义、马庆株、邵敬敏等都是积极实践者。概括起来，语义特征分析在以下诸多方面有很强的解释力，具有广泛的实践价值。 ?（一）语义特征分析能够较好的揭示一个句法组合能否成立的原因。“香蕉、苹果、梨子、杨桃”因为共有[＋水果]的范畴特征而被认为是有意义的组合，而“香蕉、石子、泉水、黄土”因为缺乏共同的范畴特征而不被理解。“笔墨纸砚”、“桌椅板凳”、“锅碗瓢盆”、“油盐酱醋”都是这种类型的并列。“吃馒头”可说而“喝馒头”不能被接受，同样“喝汤”可说而“吃汤”不能被接受。“吃”和“喝”的这种对立可以用语义特征表示为：吃[＋施事；＋固体食物；＋咀嚼；＋吞咽]，喝[＋施事；－固体食物；－咀嚼；＋吞咽]。 ?（二）语义特征分析可以揭示某些词语的比较隐蔽的语义特征。例如“写、搛、留、舀”等动词本身并不包含“给予”的意义。但当说到“写信、搛菜、舀汤、留座位”的时候，就有可能取得“给予”的意义[6]。这时，它们可以跟“卖、送、递、让”等本身包含“给予”意义的动词一样，可以出现在“V＋NP（受）＋给＋NP（与）”或“V＋给＋NP（与）＋NP（受）”格式中。例如：?（2）写一封信给老王? 写给老王一封信 ?舀一瓢水给小张（喝）? 舀给小张一瓢水（喝） ?留一个座位给老大爷? 留给老大爷一个座位 ?“写、搛、留、舀”等的这种特性使它们有别于其他行为动词，如“看、读、撞、拉”等。?（三）语义特征分析可以揭示某些句式能否成立的语义依据。例如，现代汉语里有一种由形容词加“（一）点儿”构成的祈使句：形容词＋（一）点儿！可是，并不是所有的形容词都能进入该句式[7]。试比较： ?（3）A. 虚心点儿！积极点儿！坚强点儿！ ?主动点儿！灵活点儿！大方点儿！ ?B. 粗一点儿！近一点儿！高一点儿！ ?浓一点儿！大一点儿！慢一点儿！ ?C. *骄傲点儿！*悲观点儿！*罗嗦点儿！ ?*胆小点儿！*嘈杂点儿！*蛮横点儿！ ?D. *可爱点儿！*健康点儿！*伟大点儿！ ?*优秀点儿！*美丽点儿！*高尚点儿！ ?（3）中四组格式中的形容词的语义特征可以用矩阵图区别如下： ?（3'）形A：[＋褒义，－贬义，＋可控] ?形B：[－褒义，－贬义，＋可控] ?形C：[－褒义，＋贬义，±可控] ?形D：[＋褒义，－贬义，－可控] ?可见，只有同时具备[－贬义]和[＋可控]两项语义特征的形容词才能够进入以上格式。?（四）语义特征分析能够较好地解释某些看似狭义同构的句式的内部差异，同时为词类的进一步细分提供“最可靠的语法、语义依据”[4]。例如：现代汉语语法的五种分析方法
浅层语义分析
编译原理--词法分析,语法分析,语义分析(C语言)
语义分析的一些方法
义素分析法分析“看的方式”语义场
语义分析
《编译原理》总复习-07级
编译原理第二版课后习答案
编译原理实验三-自下而上语法分析及语义分析.docx
语义识别技术方案简要说明 (1)
语义特征分析