nlp算法（nlp算法是什么意思）

大家好！今天讓創(chuàng)意嶺的小編來大家介紹下關于nlp算法的問題，以下是小編對此問題的歸納整理，讓我們一起來看看吧。

開始之前先推薦一個非常厲害的Ai人工智能工具，一鍵生成原創(chuàng)文章、方案、文案、工作計劃、工作報告、論文、代碼、作文、做題和對話答疑等等

只需要輸入關鍵詞，就能返回你想要的內容，越精準，寫出的就越詳細，有微信小程序端、在線網頁版、PC客戶端

官網：https://ai.de1919.com。

創(chuàng)意嶺作為行業(yè)內優(yōu)秀的企業(yè)，服務客戶遍布全球各地，如需了解SEO相關業(yè)務請撥打電話175-8598-2043，或添加微信：1454722008

本文目錄:

• 1、自然語言處理（NLP）知識整理及概述（一）

• 2、自然語言處理基礎 - NLP

• 3、常用NLP模型的簡介

• 4、NLP第九篇-句法分析

一、自然語言處理（NLP）知識整理及概述（一）

這是我在留學期間選修的課程 ：natura language process。 這篇文章主要是為了大致的梳理這門課上的知識點，方便日后復習。因此，語言處理的主體對象是English。

簡單來說，語言模型就是一個對于不同單詞出現概率的統(tǒng)計。

然而，對于英語來說，每個單詞可能有不同的時態(tài)和單復數等形態(tài)變化。因此，在做統(tǒng)計前，需要先對原始數據進行預處理和歸一化。

分割句子后，每句話應該作為一個元素單獨存儲。

一般來說，常用的是 unigram, bigram 和trigram, 即以1-3 個詞作為一個對象來統(tǒng)計。n 越大， 統(tǒng)計結果也越稀疏。一個七八個詞的組合重復出現的概率，顯然遠低于2-3個詞的組合。 另一方面，根據馬爾科夫鏈， 一個單詞的出現，可以認為僅跟前一個詞有關系，所以也沒有太大必要追求過大的n。

n-gram 是一個重要的基礎概念， 它所提供的概率分析可以做到很多事情， 例如機器翻譯“請給我打電話”：P(“please call me”) > P("please call I ")。 又比如拼寫糾正：基于概率， “its 5pm now” → 糾正為 “it's 5pm now”

沒有比較就沒有傷害。 對于語言模型的評估， 也需要有一個比較的對象。因此，要用兩種方法建立不同的語言模型（當然也可以對比前人的工作成果）。顯然，任意給一個測試用的句子，如果在某一模型中的出現概率都比較大，那么這個模型顯然更好。 具體來說， 評估方法有兩種：

首個單詞問題 ：對于一個基于bigram或trigram的模型，在計算一個句子的perplexity時，前1或2個單詞需要不能直接得到，依賴于句子開頭的標識符。也即是說，在訓練 n-gram 模型時， 對于每個句子，分別在開頭和結尾填充n-1個<s>。從而保證在計算perplexity的時候能夠正確地從第一個單詞開始計算。這也是為什么前面 sentence segmentation 的時候要將句子區(qū)別存儲的原因。

顯然，無論用來生成LM的corpus多么龐大，總會有些單詞沒有被包含其中（稱為out of vocabulary， OOV）。 解決方法有兩種， 一是實現設定一個固定的字典，在訓練LM過程中，所有不在字典中的單詞統(tǒng)一轉換成 token <UNK>， 另一種是將LM中出現頻率小于n次的單詞當作 <UNK>，剩下的作為字典。 根據字典對測試數據做相同操作，就可以避免OOV的問題。

在處理完OOV問題后，還有一個問題需要處理：所有單詞都在字典中，但是單詞的組合并沒有在LM中出現這一情況。 此時就需要對基于bigram或trigram的LM進行smooth操作，規(guī)避這一問題。Smoothing過程有1點需要注意，就是smooth之后的模型，其所有概率加起來，必須仍然為1。常見的smoothing方法有：

特別的，工程上最適合的應該是 stupid backoff algorithm, 這一算法并不確保整體概率為1。僅僅是在回退時乘以系數0.4計算。即如果trigram沒有找到，就使用0.4×P(bigram)， 如果bigram還是沒找到， 就是要 0.4×0.4×P(unigram)。由于OOV問題已解決，所以對于任意一個詞，必然能計算出其概率。

相關閱讀： Large Language Models in Machine Translation

二、自然語言處理基礎 - NLP

什么是自然語言處理

自然語言處理 （英語：natural language processing，縮寫作 NLP） 是人工智能和語言學領域的分支學科。此領域探討如何處理及運用自然語言；自然語言認知則是指讓電腦“懂”人類的語言。自然語言生成系統(tǒng)把計算機數據轉化為自然語言。自然語言理解系統(tǒng)把自然語言轉化為計算機程序更易于處理的形式。

自然語言處理有四大類常見的任務

什么是命名實體識別

命名實體識別（NER）是信息提?。↖nformation Extraction）的一個子任務，主要涉及如何從文本中提取命名實體并將其分類至事先劃定好的類別，如在招聘信息中提取具體招聘公司、崗位和工作地點的信息，并將其分別歸納至公司、崗位和地點的類別下。命名實體識別往往先將整句拆解為詞語并對每個詞語進行此行標注，根據習得的規(guī)則對詞語進行判別。這項任務的關鍵在于對未知實體的識別?；诖?，命名實體識別的主要思想在于根據現有實例的特征總結識別和分類規(guī)則。這些方法可以被分為有監(jiān)督（supervised）、半監(jiān)督（semi-supervised）和無監(jiān)督（unsupervised）三類。有監(jiān)督學習包括隱形馬科夫模型（HMM）、決策樹、最大熵模型（ME）、支持向量機（SVM）和條件隨機場（CRF）。這些方法主要是讀取注釋語料庫，記憶實例并進行學習，根據這些例子的特征生成針對某一種實例的識別規(guī)則。

什么是詞性標注

詞性標注 (pos tagging) 是指為分詞結果中的每個單詞標注一個正確的詞性的程序，也即確定每個詞是名詞、動詞、形容詞或其他詞性的過程。

什么是文本分類

該技術可被用于理解、組織和分類結構化或非結構化文本文檔。文本挖掘所使用的模型有詞袋（BOW）模型、語言模型（ngram）和主題模型。隱馬爾可夫模型通常用于詞性標注（POS）。其涵蓋的主要任務有句法分析、情緒分析和垃圾信息檢測。

GLUE benchmark

General Language Understanding Evaluation benchmark，通用語言理解評估基準，用于測試模型在廣泛自然語言理解任務中的魯棒性。

LM：Language Model

語言模型，一串詞序列的概率分布，通過概率模型來表示文本語義。

語言模型有什么作用？通過語言模型，可以量化地衡量一段文本存在的可能性。對于一段長度為n的文本，文本里每個單詞都有上文預測該單詞的過程，所有單詞的概率乘積便可以用來評估文本。在實踐中，如果文本很長，P(wi|context(wi))的估算會很困難，因此有了簡化版：N元模型。在N元模型中，通過對當前詞的前N個詞進行計算來估算該詞的條件概率。

重要文獻與資料

https://segmentfault.com/a/1190000015460828

https://segmentfault.com/a/1190000015284996

https://segmentfault.com/a/1190000015285996

我們介紹詞的向量表征，也稱為 word embedding 。詞向量是自然語言處理中常見的一個操作，是搜索引擎、廣告系統(tǒng)、推薦系統(tǒng)等互聯(lián)網服務背后常見的基礎技術。

在這些互聯(lián)網服務里，我們經常要比較兩個詞或者兩段文本之間的相關性。為了做這樣的比較，我們往往先要把詞表示成計算機適合處理的方式。最自然的方式恐怕莫過于向量空間模型(vector space model)。 在這種方式里，每個詞被表示成一個實數向量（one-hot vector），其長度為字典大小，每個維度對應一個字典里的每個詞，除了這個詞對應維度上的值是1，其他元素都是0。

One-hot vector雖然自然，但是用處有限。比如，在互聯(lián)網廣告系統(tǒng)里，如果用戶輸入的query是“母親節(jié)”，而有一個廣告的關鍵詞是“康乃馨”。雖然按照常理，我們知道這兩個詞之間是有聯(lián)系的——母親節(jié)通常應該送給母親一束康乃馨；但是這兩個詞對應的one-hot vectors之間的距離度量，無論是歐氏距離還是余弦相似度(cosine similarity)，由于其向量正交，都認為這兩個詞毫無相關性。 得出這種與我們相悖的結論的根本原因是：每個詞本身的信息量都太小。所以，僅僅給定兩個詞，不足以讓我們準確判別它們是否相關。要想精確計算相關性，我們還需要更多的信息——從大量數據里通過機器學習方法歸納出來的知識。

在機器學習領域里，各種“知識”被各種模型表示，詞向量模型(word embedding model)就是其中的一類。通過詞向量模型可將一個 one-hot vector映射到一個維度更低的實數向量（embedding vector），如embedding(母親節(jié))=[0.3,4.2,−1.5,...],embedding(康乃馨)=[0.2,5.6,−2.3,...]。在這個映射到的實數向量表示中，希望兩個語義（或用法）上相似的詞對應的詞向量“更像”，這樣如“母親節(jié)”和“康乃馨”的對應詞向量的余弦相似度就不再為零了。

詞向量模型可以是概率模型、共生矩陣(co-occurrence matrix)模型或神經元網絡模型。在用神經網絡求詞向量之前，傳統(tǒng)做法是統(tǒng)計一個詞語的共生矩陣X。

X是一個|V|×|V| 大小的矩陣，Xij表示在所有語料中，詞匯表V(vocabulary)中第i個詞和第j個詞同時出現的詞數，|V|為詞匯表的大小。對X做矩陣分解（如奇異值分解），得到的U即視為所有詞的詞向量：

但這樣的傳統(tǒng)做法有很多問題：

基于神經網絡的模型不需要計算和存儲一個在全語料上統(tǒng)計產生的大表，而是通過學習語義信息得到詞向量，因此能很好地解決以上問題。

神經網絡

當詞向量訓練好后，我們可以用數據可視化算法t-SNE[ 4 ]畫出詞語特征在二維上的投影（如下圖所示）。從圖中可以看出，語義相關的詞語（如a, the, these; big, huge）在投影上距離很近，語意無關的詞（如say, business; decision, japan）在投影上的距離很遠。

另一方面，我們知道兩個向量的余弦值在[−1,1]的區(qū)間內：兩個完全相同的向量余弦值為1, 兩個相互垂直的向量之間余弦值為0，兩個方向完全相反的向量余弦值為-1，即相關性和余弦值大小成正比。因此我們還可以計算兩個詞向量的余弦相似度。

模型概覽

語言模型

在介紹詞向量模型之前，我們先來引入一個概念：語言模型。 語言模型旨在為語句的聯(lián)合概率函數P(w1,...,wT)建模, 其中wi表示句子中的第i個詞。語言模型的目標是，希望模型對有意義的句子賦予大概率，對沒意義的句子賦予小概率。 這樣的模型可以應用于很多領域，如機器翻譯、語音識別、信息檢索、詞性標注、手寫識別等，它們都希望能得到一個連續(xù)序列的概率。 以信息檢索為例，當你在搜索“how long is a football bame”時（bame是一個醫(yī)學名詞），搜索引擎會提示你是否希望搜索"how long is a football game", 這是因為根據語言模型計算出“how long is a football bame”的概率很低，而與bame近似的，可能引起錯誤的詞中，game會使該句生成的概率最大。

對語言模型的目標概率P(w1,...,wT)，如果假設文本中每個詞都是相互獨立的，則整句話的聯(lián)合概率可以表示為其中所有詞語條件概率的乘積，即：

然而我們知道語句中的每個詞出現的概率都與其前面的詞緊密相關, 所以實際上通常用條件概率表示語言模型：

N-gram neural model

在計算語言學中，n-gram是一種重要的文本表示方法，表示一個文本中連續(xù)的n個項?；诰唧w的應用場景，每一項可以是一個字母、單詞或者音節(jié)。 n-gram模型也是統(tǒng)計語言模型中的一種重要方法，用n-gram訓練語言模型時，一般用每個n-gram的歷史n-1個詞語組成的內容來預測第n個詞。

Yoshua Bengio等科學家就于2003年在著名論文 Neural Probabilistic Language Models [ 1 ] 中介紹如何學習一個神經元網絡表示的詞向量模型。文中的神經概率語言模型（Neural Network Language Model，NNLM）通過一個線性映射和一個非線性隱層連接，同時學習了語言模型和詞向量，即通過學習大量語料得到詞語的向量表達，通過這些向量得到整個句子的概率。因所有的詞語都用一個低維向量來表示，用這種方法學習語言模型可以克服維度災難（curse of dimensionality）。注意：由于“神經概率語言模型”說法較為泛泛，我們在這里不用其NNLM的本名，考慮到其具體做法，本文中稱該模型為N-gram neural model。

在上文中已經講到用條件概率建模語言模型，即一句話中第t個詞的概率和該句話的前t−1個詞相關。可實際上越遠的詞語其實對該詞的影響越小，那么如果考慮一個n-gram, 每個詞都只受其前面n-1個詞的影響，則有：

給定一些真實語料，這些語料中都是有意義的句子，N-gram模型的優(yōu)化目標則是最大化目標函數:

其中f(wt,wt−1,...,wt−n+1)表示根據歷史n-1個詞得到當前詞wt的條件概率，R(θ)表示參數正則項。

Continuous Bag-of-Words model(CBOW)

CBOW模型通過一個詞的上下文（各N個詞）預測當前詞。當N=2時，模型如下圖所示：

具體來說，不考慮上下文的詞語輸入順序，CBOW是用上下文詞語的詞向量的均值來預測當前詞。

其中xt為第t個詞的詞向量，分類分數（score）向量 z=U∗context，最終的分類y采用softmax，損失函數采用多類分類交叉熵。

Skip-gram model

CBOW的好處是對上下文詞語的分布在詞向量上進行了平滑，去掉了噪聲，因此在小數據集上很有效。而Skip-gram的方法中，用一個詞預測其上下文，得到了當前詞上下文的很多樣本，因此可用于更大的數據集。

如上圖所示，Skip-gram模型的具體做法是，將一個詞的詞向量映射到2n個詞的詞向量（2n表示當前輸入詞的前后各n個詞），然后分別通過softmax得到這2n個詞的分類損失值之和。

我們介紹了詞向量、語言模型和詞向量的關系、以及如何通過訓練神經網絡模型獲得詞向量。在信息檢索中，我們可以根據向量間的余弦夾角，來判斷query和文檔關鍵詞這二者間的相關性。在句法分析和語義分析中，訓練好的詞向量可以用來初始化模型，以得到更好的效果。在文檔分類中，有了詞向量之后，可以用聚類的方法將文檔中同義詞進行分組，也可以用 N-gram 來預測下一個詞。希望大家在本章后能夠自行運用詞向量進行相關領域的研究。

參考： https://www.paddlepaddle.org.cn/documentation/docs/zh/user_guides/simple_case/word2vec/README.cn.html

三、常用NLP模型的簡介

符號統(tǒng)一：X即樣本矩陣

LSI：即SVD（奇異值）分解，X≈UΣVT（VT代表V的轉置），設X為n×m矩陣，共m個文檔，每個文檔由n個詞構成，而Σ為s×s矩陣，代表s個主題，V為m×s，每行代表每個文檔分別和每個主題的相似度。通常文本分類用到V矩陣。U矩陣即n×s，每行代表每個詞和每個主題的相似度。U和V分別成為左、右奇異矩陣。PS：我們知道PCA是對XTX求特征值和特征向量，設X=UΣVT，由于U和V都是正交陣，則XTX=VΣ²VT，即右奇異矩陣就是PCA分解后的特征矩陣，XXT→左奇異矩陣也是同理。

Word2Vec: 最常用的自然語言的數字化表達，簡而言之就是若共100篇文章，vocabulary_size=10000，那么每個詞都可以用10000維的one-hot向量表達，而經過word2vec的embedding后，每個詞都可以用例如300維向量表示，不僅降了維度，而且相似詞義的詞將擁有更接近的向量表示。word2vec分為兩種模型，CBOW - 根據上下文預測詞語，SkipGram - 根據詞語預測上下文。

CBOW：對C個上下文的詞語每個詞用C組不同的權重W全連接映射到一個N維的隱層上，得到C個N維隱層值，取平均，再對這個平均的N維隱層用權重W'的全連接+softmax對V個詞語賦予概率值，V即vocabulary_sizee。W和W'分別是V×N和N×V的矩陣（全連接↔左乘權重矩陣的轉置），假設某詞word是Vocabulary的第j個詞，那么W的第j行稱為word的輸入詞向量，W'的第j列向量為word的輸出詞向量。 點此 查看原論文，不過我沒看懂所謂的word embedding最終輸出的到底是哪個向量，輸入、輸出、還是隱層。

SkipGram: CBOW的反向操作。

兩者都是用BP算法更新。

LSTM：假設輸入一句話長度10，每個詞用32維向量展示，則LSTM將這個[10, 32]的向量轉化為[k]的輸出（hidden state），k可以是小于32的任意整數。也可輸出每個time_step的輸出（[10,32]），和最后的cell state。并可對輸出的k維向量加一個全連接降維或再加一個softmax實現分類。LSTM和RNN的區(qū)別在于有門控制，主要是通過忘記門來保留長期記憶，避免梯度消失。

Seq2Seq：Seq2Seq本來有著非常廣闊的定義，但通常是指一個基于神經網絡與 LSTM 的 經典seq2seq模型 ，后續(xù)流行的Transformer、BERT、GPT3等都是基于此。大致功能是實現機器翻譯，通過encoder將原文轉換為一個理解的矩陣后，用decoder一詞一詞地根據這個理解輸出目標語言對應的句子。結構大致是先將原文每個詞embedding后輸入一個名為encoder的LSTM，并將其輸出（即LSTM的最后一個cell的h和c）作為對原文的理解。然后一個名為decoder的LSTM會將這個理解轉化為答案，decoder用BOS代表句子開始，EOS代表結束。訓練時，例如將“我愛你”翻譯為“I love you”，第一個輸入是BOS，embedding后經過cell（用之前得到的h和c初始化）后用softmax激活得到第一個輸出“I”，“I”作為第二個輸入再次embedding經過cell后softmax激活得到第二個輸出“l(fā)ove”，同理得到第三個輸出“you”，最后得到EOS。通過BP梯度下降訓練完成后，以同樣的方式完成機器翻譯的預測任務。

Attention：最早用于Seq2Seq模型。例如要將“我愛你”翻譯為“I love you”時，首先根據encoder獲得對原文每個詞的理解，即encoder_output。decoder每次輸出時，對當前輸入找一個合適的attention分布，即權重（所謂更注意的地方，即權重更高的地方），該權重點乘encoder_output后求和即經過注意力機制后當前的輸入。簡而言之，在decoder每次輸出時，會根據輸入對encoder_output給予一個不同的attention分布。（ 此段話尚未驗證，需讀過論文后修正 ）

Self-Attention: 第一次出現在Transformer，由于Transformer沒有使用傳統(tǒng)s2s所用的RNN或LSTM，所以自稱Attention is all you need (You don't need RNN or LSTM)。Self-Attention和Attention的區(qū)別有很多，首先對它而言可以不需要decoder直接在encoder內完成自注意力，其次它沒有關注序列信息，因此需要額外先進行Positional Encoding，添加序列信息。它的重點在于在關注一個詞時，可以將它和上下文的其他詞聯(lián)系到一起計算，對關聯(lián)較大的詞賦予更多的關注（權重）。計算方法是通過三個不同的權重矩陣來乘輸入X，獲得Q K V三個矩陣，即將原文X拆分為了3部分：問題、目錄、內容，通過QKT除以一個常數（原論文是根號dk，這個數越大則概率分布越平均，越小則越極端，也會導致梯度消失）后softmax，來找到和Q對應的K，再通過這個K找到相應的V，即代表此時的關注的內容。

Transformer（ 論文 及 較好的一篇介紹 ）: 雖然也有encoder和decoder，但后續(xù)的發(fā)展改進通常只用encoder，而encoder的主要部分是self-attention。整體結構是6個encoder層接6個decoder層。每個encoder層大致結構是輸入X經Positional Encoding后，經self-attention加工和自身殘差連接后相加并norm（所謂殘差連接相當于給了X兩個通道，一個是直接輸入，一個是經過attention輸入），隨后再通過前向網絡分別對每個輸出全連接處理后（一方面避免直接concat維度太大，一方面可以并行計算）與自身殘差相加并norm。decoder大致相同，就在中間多了一個Mask的Self Attention來接受encoder的輸入，mask是因為decoder按順序輸出，需要把后面的mask掉。

四、NLP第九篇-句法分析

句法分析的基本任務是確定句子的 語法結構 或句子中 詞匯之間的依存關系 。句法分析不是一個自然語言處理任務的最終目標，但它往往是實現最終目標的關鍵環(huán)節(jié)。

句法分析分為 句法結構分析 和 依存關系分析 兩種。以獲取整個句子的句法結構為目的的稱為 完全句法分析 ，而以獲得局部成分為目的的語法分析稱為 局部分析 ，依存關系分析簡稱 依存分析 。

一般而言，句法分析的任務有三個：

判斷輸出的字符串是否屬于某種語言

消除輸入句子中詞法和結構等方面的歧義

分析輸入句子的內部結構，如成分構成、上下文關系等。

第二三個任務一般是句法分析的主要任務。

一般來說，構造一個句法分析器需要考慮兩部分工作：一部分是語法的形式化表示和詞條信息描述問題，形式化的語法規(guī)則構成了規(guī)則庫，詞條信息等由詞典或同義詞表等提供，規(guī)則庫與詞典或同義詞表構成了句法分析的知識庫；另一部分就是基于知識庫的解析算法了。

語法形式化屬于句法理論研究的范疇，目前在自然語言處理中廣泛使用的是上下文無關文法（CFG）和基于約束的文法，后者又稱合一文法。

簡單的講，句法結構分析方法可以分為基于規(guī)則的分析方法和基于統(tǒng)計的分析方法兩大類。

基于規(guī)則的句法結構分析方法的基本思路是，由人工組織語法規(guī)則，建立語法知識庫，通過條件約束和檢查來實現句法結構歧義的消除。

根據句法分析樹形成方向的區(qū)別，人們通常將這些方法劃分為三種類型：自頂向下的分析方法，自底向上的分析方法和兩者相結合的分析方法。自頂向下分析算法實現的是規(guī)則推導的過程，分析樹從根結點開始不斷生長，最后形成分析句子的葉結點。而自底向上分析算法的實現過程恰好想法，它是從句子符號串開始，執(zhí)行不斷規(guī)約的過程，最后形成根節(jié)點。

基于規(guī)則的語法結構分析可以利用手工編寫的規(guī)則分析出輸入句子所有可能的句法結構；對于特定領域和目的，利用有針對性的規(guī)則能夠較好的處理句子中的部分歧義和一些超語法（extra-grammatical）現象。

但對于一個中等長度的輸入句子來說，要利用大覆蓋度的語法規(guī)則分析出所有可能的句子結構是非常困難的，而且就算分析出來了，也難以實現有效的消歧，并選擇出最有可能的分析結果；手工編寫的規(guī)則帶有一定的主觀性，還需要考慮到泛化，在面對復雜語境時正確率難以保證；手工編寫規(guī)則本身就是一件大工作量的復雜勞動，而且編寫的規(guī)則領域有密切的相關性，不利于句法分析系統(tǒng)向其他領域移植。

基于規(guī)則的句法分析算法能夠成功的處理程序設計語言的編譯，而對于自然語言的處理卻始終難以擺脫困境，是因為程序設計語言中使用的知識嚴格限制的上下文無關文法的子類，但自然語言處理系統(tǒng)中所使用的形式化描述方法遠遠超過了上下文無關文法的表達能力；而且人們在使用程序設計語言的時候，一切表達方式都必須服從機器的要求，是一個人服從機器的過程，這個過程是從語言的無限集到有限集的映射過程，而在自然語言處理中則恰恰相反，自然語言處理實現的是機器追蹤和服從人的語言，從語言的有限集到無限集推演的過程。

完全語法分析

基于PCFG的基本分析方法

基于概率上下文無關文法的短語結構分析方法，可以說是目前最成功的語法驅動的統(tǒng)計句法分析方法，可以認為是規(guī)則方法與統(tǒng)計方法的結合。

PCFG是CFG的擴展，舉個例子：

PCFG

當然，同一個符號不同生成式的概率之和為1。NP是名詞短語、VP是動詞短語、PP是介詞短語。

基于PCFG的句法分析模型，滿足以下三個條件：

位置不變性：子樹的概率不依賴于該子樹所管轄的單詞在句子中的位置

上下文無關性：子樹的概率不依賴于子樹控制范圍以外的單詞

祖先無關性：子樹的概率不依賴于推導出子樹的祖先節(jié)點

根據上述文法，『He met Jenny with flowers』有兩種可能的語法結構：

而且我們可以通過將樹中的所有概率相乘，得到兩棵子樹的整體概率，從中選擇概率更大的子樹作為最佳結構。

與HMM類似，PCFG也有三個基本問題：

給定一個句子W＝w1w2…wn和文法G，如何快速計算概率P(W|G)

給定一個句子W＝w1w2…wn和文法G，如何選擇該句子的最佳結構？即選擇句法結構樹t使其具有最大概率

給定PCFG G和句子W＝w1w2…wn，如何調節(jié)G的概率參數，使句子的概率最大

首先是第一個問題，HMM中我們用的是前向算法和后向算法來計算觀察序列O概率，相似的，這里我們用的是內向算法和外向算法來計算P(W|G) 。

首先我們定義內向變量αij(A)，與前向變量相似但又有不同，αij(A)即非終結符A推導出W中字串wiw(i+1)…wj的概率。那P(W|G)自然就等于α1n(S)了，S是起始符號，計算的就是由起始符號S推導出整個句子W=w1w2…wn的概率。

所以只要有αij(A)的遞歸公式就能計算出P(W|G)，遞歸公式如下：

根據定義，αii(A)自然就等同于符號A輸出wi的概率；而αij(A)的計算思路是，這個子串wiw(i+1)…wj可以被切成兩部分處理，前一部分wiw(i+1)…wk由非終結符號B生成，后一部分wkw(k+1)…wj由非終結符號C生成，而BC由A生成。這樣將概率依次相乘，即可將一個大問題劃分為兩個小問題處理，兩個小問題又可以進一步劃分直到不能劃分為止，然后遞歸回來得到結果。

這里給一張內向變量計算方法示意圖：

這個問題也可以用外向算法來解決。

首先定義外向變量，βij(A)是，初始符號S在推導出語句W=w1w2…wn的過程中，產生符號串w1w2…w(i-1)Aw(j+1)…wn的概率（隱含著A會生成wiw(i+1)…wj）。也就是說βij(A)是S推導出除了以A節(jié)點為根節(jié)點的子樹以外的其他部分的概率。

《統(tǒng)計自然語言處理（第二版）》這本書里講錯了，這里我給出我自己的理解，書里給的算法步驟如下：

很明顯的錯誤，初始化都把結果初始化了，那這個算法還算什么，直接等于1就完了唄。

這是作者對外向變量定義理解模糊的問題，上面給了外向變量的定義，里面有一句話『隱含著A會生成wiw(i+1)…wj』，那問題在于，A會生成wiw(i+1)…wj，這到底算是條件還是推論。

看這個算法的初始化的意思，說β1n(A)，在A=S的時候，為1，不等于S為0，意思是什么？意思就是『隱含著A會生成wiw(i+1)…wj』這句話是條件，β1n(S)已經隱含了S生成W＝w1w2…wn了，所謂的w1w2…w(i-1)Aw(j+1)…wn也就不存在了，只剩下一個S->S了，所以概率自然為1。

但是在第三步這個地方，作者理解成什么意思了呢？作者又把『隱含著A會生成wiw(i+1)…wj』這句話當成推論了，認為在β1n(S)，里S會生成W＝w1w2…wn是推論，那真是就正好了，要求的結果就是S生成W＝w1w2…wn，這不就結束了嗎，結果就導致了這個算法第一步初始化都把結果初始化了。

那我的理解是什么呢，通過這個公式計算出來的β1n(S)，確實是正確的，意義實際上也是包含了『隱含著A會生成wiw(i+1)…wj』這句話是推論，但是右側式子里由于不斷遞歸而產生的β1n(S)，是把『隱含著A會生成wiw(i+1)…wj』這句話當條件的，所以計算上沒有問題。

我傾向于為第三步中的β1n(S)加一個星號，以表明意義的不同。

書中還給了個外向變量的計算方法示意圖，我覺得也是莫名其妙：

他說βij(A)是這兩種情況的概率和，這我們知道j比i大，那這圖里這個k既比i小又比j大，這不是搞笑嗎。只能說圖上這倆C就不是一個C，k也不是一個k。

那我為什么會理解成一個呢，除了字母相同，他前面還這么講『必定運用了形如B->AC或者B->CA的規(guī)則』、『運用B->AC或者B->CA兩種規(guī)則的情況』，這明顯就是給人以順序交換的誤解。

另外，還在內向變量的使用上前后不一，可以說這本書里對外向算法的講解是非常失敗的。而且對外向算法的計算仍然需要用到內向算法的遞歸，那真的直接用內向算法就好了，外向算法還要多定義變量。

然后是第二個問題，選擇句子的最佳結構，也即給定一個句子W＝w1w2…wn和文法G，

選定擁有最大概率的語法結構樹。這一問題與HMM中類似，仍然采用動態(tài)規(guī)劃的思想去解決。最后利用CYK算法去生成擁有最大概率的語法結構樹。

第三個問題是給定PCFG G和句子W＝w1w2…wn，如何調節(jié)G的概率參數，使句子的概率最大，與HMM相對的，PCFG這里采用的算法名叫內外向算法。與前后向算法相同，也屬于一種EM算法，其基本思想是，首先給G的產生式隨機地賦予一個概率值（滿足歸一化條件），得到文法G0，然后根據G0和訓練數據，可以計算出每條規(guī)則使用次數的期望值，用期望值進行最大似然估計，得到語法G的新參數值，新的語法記作G1，然后循環(huán)執(zhí)行該過程，G的參數概率將收斂于最大似然估計值。

PCFG只是一種特殊的上下文無關文法模型，根據PCFG的模型和句子，具體去對句子做語法分析，生成語法結構樹，靠的是還是CYK算法。CYK算法是一個用來判定任意給定的字符串W是否屬于一個上下文無關文法的算法。

基于PCFG的句法分析模型存在有許多問題，比如因為PCFG沒有對詞匯進行建模，所以存在對詞匯信息不敏感的問題。因此人們提出了詞匯化的短語結構分析器，有效的提升了基于PCFG的句法分析器的能力。

而且，我們上面也提到了PCFG的三個獨立性假設，這也導致了規(guī)則之間缺乏結構依賴關系（就像HMM的三個假設也不完全合理一樣），而在自然語言中，生成每個非終結符的概率往往是與其上下文結構有關系的，所以有人提出了一種細化非終結符的方法，為每個非終結符標注上其父節(jié)點的句法標記信息。

D. Klein提出了帶有隱含標記的上下文無關文法（PCFG with latent annotations，PCFG-LA），使得非終結符的細化過程可以自動進行，并且在使用EM算法優(yōu)化時，為避免到達局部最優(yōu)，對其進行了改進，提出了一種層次化的『分裂-合并』策略，以期獲取一個準確并且緊湊的PCFG-LA模型?；赑CFG-LA的Berkeley Parser作為非詞匯化句法分析器的代表，無論是性能表現還是運行速度，都是目前開源的短語結構分析器中最好的。其語法樹如下圖：

普通句法樹與PCFG-LA句法樹對照實例

這個x就是隱含標記，xi的取值范圍一般是人為設定的，一般取1~16之間的整數。而且PCFG-LA也類似于HMM模型，原始非終結符對應HMM模型中的觀察輸出，而隱含標記對應HMM模型中的隱含狀態(tài)。

淺層語法分析（局部語法分析）

由于完全語法分析要確定句子所包含的全部句法信息，并確定句子中各成分之間的關系，這是一項十分苦難的任務。到目前為止，句法分析器的各方面都難以達到令人滿意的程度，為了降低問題的復雜度，同時獲得一定的句法結構信息，淺層句法分析應運而生。

淺層語法分析只要求識別句子中的某些結構相對簡單的獨立成為，例如非遞歸的名詞短語、動詞短語等，這些被識別出來的結構通常稱為語塊（chunk）。

淺層句法分析將句法分析分解為兩個主要子任務，一個是語塊的識別和分析，另一個是語塊之間的依附關系分析。其中，語塊的識別和分析是主要任務。在某種程度上說，淺層句法分析使句法分析的任務得到了簡化，同時也有利于句法分析系統(tǒng)在大規(guī)模真實文本處理系統(tǒng)中迅速得到應用。

基本名詞短語（base NP）是語塊中的一個重要類別，它指的是簡單的、非嵌套的名詞短語，不含有其他子項短語，并且base NP之間結構上是獨立的。示例如下：

base NP識別就是從句子中識別出所有的base NP，根據這種理解，一個句子中的成分和簡單的分為baseNP和非base NP兩類，那么base NP識別就成了一個分類問題。

base NP的表示方法有兩種，一種是括號分隔法，一種是IOB標注法。括號分隔法就是將base NP用方括號界定邊界，內部的是base NP，外部的不屬于base NP。IOB標注法中，字母B表示base NP的開端，I表示當前詞語在base NP內，O表示詞語位于base NP之外。

基于SVM的base NP識別方法

由于base NP識別是多值分類問題，而基礎SVM算法解決的是二值分類問題，所以一般可以采用配對策略（pairwise method）和一比其余策略（one vs. other method）。

SVM一般要從上下文的詞、詞性、base NP標志中提取特征來完成判斷。一般使用的詞語窗口的長度為5（當前詞及其前后各兩個詞）時識別的效果最好。

基于WINNOW的base NP識別方法

WINNOW是解決二分問題的錯誤驅動的機器學習方法，該方法能從大量不相關的特征中快速學習。

WINNOW的稀疏網絡（SNoW）學習結構是一種多類分類器，專門用于處理特征識別領域的大規(guī)模學習任務。WINNOW算法具有處理高維度獨立特征空間的能力，而在自然語言處理中的特征向量恰好具有這種特點，因此WINNOW算法也常用于詞性標注、拼寫錯誤檢查和文本分類等等。

簡單WINNOW的基本思想是，已知特征向量和參數向量和實數閾值θ，先將參數向量均初始化為1，將訓練樣本代入，求特征向量和參數向量的內積，將其與θ比較，如果大于θ，則判定為正例，小于θ則判定為反例，將結果與正確答案作比較，依據結果來改變權值。

如果將正例估計成了反例，那么對于原來值為1的x，把它的權值擴大。如果將反例估計成了正例，那么對于原來值為1的x，把它的權值縮小。然后重新估計重新更改權重，直到訓練完成。

這其實讓我想到了LR算法，因為LR算法也是特征向量與參數向量的內積，最后將其送到Sigmoid函數中去拿到判定結果，然后大于0.5的為正例，小于0.5的為反例，實際上只要反過來，Sigmod函數輸出0.5時候的輸入就是WINNOW算法里的那個實數閾值θ。但是區(qū)別在于WINNOW算法只判定大小，不判定概率，而LR利用Sigmoid函數給出了概率。LR利用這給出的概率，通過使訓練集的生成概率最大化來調整參數，而WINNOW則是直接樸素的錯誤情況來增大或縮小相關參數。目測LR因為使用了梯度下降，它的收斂速度要快于WINNOW，而WINNOW的優(yōu)勢則在于可以處理大量特征。

基于CRF的base NP識別方法

基于CRF的base NP識別方法擁有與SVM方法幾乎一樣的效果，優(yōu)于基于WINNOW的識別方法、基于MEMM的識別方法和感知機方法，而且基于CRF的base NP識別方法在運行速度上較其他方法具有明顯優(yōu)勢。

依存語法理論

在自然語言處理中，我們有時不需要或者不僅僅需要整個句子的短語結構樹，而且要知道句子中 詞與詞之間的依存關系 。用詞與詞之間的依存關系來描述語言結構的框架成為依存語法，又稱從屬關系語法。利用依存語法進行句法分析也是自然語言理解的重要手段之一。

有人認為，一切結構語法現象可以概括為關聯(lián)、組合和轉位這三大核心。句法關聯(lián)建立起詞與詞之間的從屬關系，這種從屬關系由 支配詞 和 從屬詞 聯(lián)結而成， 謂語中的動詞是句子的中心并支配別的成分，它本身不受其他任何成分支配 。

依存語法的本質是一種結構語法，它主要研究以謂詞為中心而構句時由深層語義結構映現為表層語法結構的狀況及條件，謂詞與體詞之間的同現關系，并據此劃分謂詞的詞類。

常用的依存于法結構圖示有三種：

計算機語言學家J. Robinson提出了依存語法的四條公理：

一個句子只有一個獨立的成分

句子的其他成分都從屬于某一成分

任何一個成分都不能依存于兩個或兩個以上的成分

如果成分A直接從屬于成分B，而成分C在句子中位于A和B之間，那么，成分C或者屬于成分A，或者從屬于B，或者從屬于A和B之間的某一成分。

這四條公理相當于對依存圖和依存樹的形式約束：單一父節(jié)點、連通、無環(huán)和可投射，由此來保證句子的依存分析結果是一棵有根的樹結構。

這里提一下可投射，如果單詞之間的依存弧畫出來沒有任何的交叉，就是可投射的（參考上面的兩個有向圖）。

為了便于理解，我國學者提出了依存結構樹應滿足的5個條件：

單純結點條件：只有終結點，沒有非終結點

單一父結點條件：除根節(jié)點沒有父結點外，所有的結點都只有一個父結點

獨根結點條件：一個依存樹只能有一個根結點，它支配其他結點

非交條件：依存樹的樹枝不能彼此相交

互斥條件：從上到下的支配關系和從左到右的前于關系之間是相互排斥的，如果兩個結點之間存在著支配關系，它們就不能存在于前于關系

這五個條件是有交集的，但它們完全從依存表達的空間結構出發(fā)，比四條公理更直觀更實用。

Gaifman 1965年給出了依存語法的形式化表示，證明了依存語法與上下文無關文法沒有什么不同..

類似于上下文無關文法的語言形式對被分析的語言的投射性進行了限制，很難直接處理包含非投射現象的自由語序的語言。20世紀90年代發(fā)展起來了約束語法和相應的基于約束滿足的依存分析方法，可以處理此類非投射性語言問題。

基于約束滿足的分析方法建立在約束依存語法之上，將依存句法分析看做可以用約束滿足問題來描述的有限構造問題。

約束依存語法用一系列形式化、描述性的約束將不符合約束的依存分析去掉，直到留下一棵合法的依存樹。

生成式依存分析方法、判別式依存分析方法和確定性依存分析方法是數據驅動的統(tǒng)計依存分析中具有代表性的三種方法。

生成性依存分析方法

生成式依存分析方法采用聯(lián)合概率模型生成一系列依存語法樹并賦予其概率分值，然后采用相關算法找到概率打分最高的分析結果作為最后輸出。

生成式依存分析模型使用起來比較方便，它的參數訓練時只在訓練集中尋找相關成分的計數，計算出先驗概率。但是，生成式方法采用聯(lián)合概率模型，再進行概率乘積分解時做了近似性假設和估計，而且，由于采用全局搜索，算法的復雜度較高，因此效率較低，但此類算法在準確率上有一定優(yōu)勢。但是類似于CYK算法的推理方法使得此類模型不易處理非投射性問題。

判別式依存分析方法

判別式依存分析方法采用條件概率模型，避開了聯(lián)合概率模型所要求的獨立性假設（考慮判別模型CRF舍棄了生成模型HMM的獨立性假設），訓練過程即尋找使目標函數（訓練樣本生成概率）最大的參數θ（類似Logistic回歸和CRF）。

判別式方法不僅在推理時進行窮盡搜索，而且在訓練算法上也具有全局最優(yōu)性，需要在訓練實例上重復句法分析過程來迭代參數，訓練過程也是推理過程，訓練和分析的時間復雜度一致。

確定性依存方法

確定性依存分析方法以特定的方向逐次取一個待分析的詞，為每次輸入的詞產生一個單一的分析結果，直至序列的最后一個詞。

這類算法在每一步的分析中都要根據當前分析狀態(tài)做出決策（如判斷其是否與前一個詞發(fā)生依存關系），因此，這種方法又稱決策式分析方法。

通過一個確定的分析動作序列來得到一個唯一的句法表達，即依存圖（有時可能會有回溯和修補），這是確定性句法分析方法的基本思想。

短語結構與依存結構之間的關系

短語結構樹可以被一一對應地轉換成依存關系樹，反之則不然。因為一棵依存關系樹可能會對應多棵短語結構樹。

以上就是關于nlp算法相關問題的回答。希望能幫到你，如有更多相關問題，您也可以聯(lián)系我們的客服進行咨詢，客服也會為您講解更多精彩的知識和內容。

推薦閱讀：

listenup怎么讀（listenl怎么讀）

百度nlp（百度nlp面經）

下載ourchat這個軟件（download our app）

淘寶最近某個商品搜索量（淘寶最近某個商品搜索量低）

抖音團購券怎么上架（抖音團購券怎么上架商品鏈接）