自然語言處理課堂筆記 / 期末復習

課程基本信息

考試

內容來自PPT、課上提問

10選（10分）

8簡（90分）每個 2-3小問

（CNN、RNN、Transformer、Bayes每章都有，緒論基本概念也有）

其他

虞劍飛

助教：宋曉（單）

10%課堂+40%實踐+50%期末

20分課后作業

基于CNN的文本分類
基于RNN的命名實體識別
基于transformer的機器翻譯（英譯中）

代碼+文檔報告（方法、實驗結果、分析）+1~2分鐘的程序演示視頻

20分期末項目

針對某個NLP任務復現最新論文中的算法
結合最新NLP技術提升其他研究方向任務的性能

項目報告+源代碼+PPT+10-15分鐘PPT演講+答辯

教材

Foundations of Statistical Natural Language Processing
統計自然語言處理宗成慶
文本數據挖掘宗成慶

PPT主要基于宗成慶（中科院自動化所）、張家俊

網課

cs4705(columbia)
Christopher Manning(cs224n)
Dan Jurafsky

會議

ACL (Annual Meeting of the Association for Computational Linguistics)
COLING (International Conference on Computational
Linguistics)
EMNLP (Conference on Empirical Methods in Natural Language
Processing)
NAACL (Annual Conference of the North American Chapter of the Association for Computational Linguistics)

期末沖刺

1 概念

語言學：研究語言的本質、結構、發展規律
計算語言學 CL
自然語言理解 NLU 概念來自達特茅斯會議 1956

回顧會議參與人員：

約翰·麥卡錫（John McCarthy）、馬文·閔斯基（Marvin Minsky，人工智能與認知學專家）、克勞德·香農（Claude Shannon，信息論的創始人）、艾倫·紐厄爾（Allen Newell，計算機科學家）、赫伯特·西蒙（Herbert Simon，諾貝爾經濟學獎得主）、所羅門諾夫、Arthur Samuel（搞國際象棋的）、奧利弗·塞爾弗里奇（Oliver Selfridge，提出了Pandemonium）、羅切斯特（Nathaniel Rochester，計算機設計）、 Trenchard More

自然語言處理 NLP
人類語言技術 HLT 最大的一個概念

語言的一種分類

屈折語（英語）
黏著語（日語）
孤立語/分析語（漢語）

學科發展：

基于模板—基于規則—基于統計—深度學習

理性主義—經驗主義—連結主義

研究內容大致可分為：

分類、序列標注、生成、結構預測（如依存句法分析）

任務

機器翻譯
信息檢索
自動文摘
問答系統
信息過濾
信息抽取
文檔分類
情感分類
文字編輯和自動校對
文字識別 CR
語音識別 ASR
語音合成 TTS
說話人識別

基本問題

Morphology形態學問題

研究詞 (word) 是如何由有意義的基本單位詞素 (morphemes) 構成的。
Syntax句法問題
Semantics語義學問題
Pragmatics語用學問題
Phonetics語音學問題

主要困難

歧義ambiguity
未知語言現象

基本方法

規則方法
統計機器翻譯方法
神經機器翻譯方法

自然語言通常是指一種自然地隨文化演化的語言。世界語則為人造語言，即是一種為某些特定目的而創造的語言。

2 基于規則的方法

例子：Text2SQL

規則方法可以用于詞法分析、句法分析、語義分析等

詞法分析包括：

形態還原（針對英語等），把句子中的詞還原成它們的基本詞形即原形
分詞（針對漢語、日語等）

信息處理用現代漢語分詞規范：GB-13715

切分歧義問題

依據詞典庫和規則庫的匹配分詞方法，具體包括FMM、RMM、BMM等

具體算法參考：

自然語言處理-中文分詞相關算法(MM、RMM、BMM、HMM)_在自然語言處理中,基于機器學習算法的中文分詞算法包括-CSDN博客

利用歧義字串前驅字串和后繼字串的句法語義和語用信息分詞
詞性標注，為句子中的詞標上預定義類別集合中的類

按句法相關性+語義相關性分類

兼類詞問題

規則方法、統計方法、基于轉換的錯誤驅動方法
命名實體識別

匹配方法，即依賴詞典、模板、正則表達式

機器翻譯之規則翻譯：

? 分析、轉換、生成

基于詞的
基于句法結構轉換的
基于語義轉換的
基于中間語言的

3 文本分類

將給定的文本文檔或句子分類為預定義的類別

單標簽多類別文本分類
多標簽多類別文本分類

基準公開數據集：SST、IMDb Review等

傳統機器學習方法

文本表示

向量空間模型（vector space model, VSM），核心是將文本視為特征項的集合

特征項： VSM 中最小的語言單元，可以是字、詞、短語等。

特征項權重：用??表示特征項??的權重，相應地，文本可以表示為 (??1:??1,??2:??2,…,????:????)或(??1,??2,…,????)，可以是
- 布爾變量
- 詞頻tf
  
  （權重通常取log）
- 逆文檔頻率idf = log(N/df)
- TF-IDF = tf*idf
特征選擇
- 文檔頻率df：文檔集中含有該特征的文檔數目
- 互信息MI
  
  互信息MI是點式互信息PMI的期望。
- 信息增益IG
分類算法
- 樸素貝葉斯（多項式分布版）【重要！】
- 線性判別
- SVM
- 最大熵模型
- 無監督
- 半監督

性能評估：召回率、精確率和 ??1值

宏平均
微平均

在二分類且類別互斥的情況下，??????????_??、??????????_??、??????????_????都與正確率 ??????相等。

ROC、AUC

4 語言模型

n元文法模型（n-gram model）

希望計算一段文字的概率。

n元文法模型基于一個假設：第n個詞出現與前n-1個詞相關，而與其他任何詞不相關。

語句 $ s = w_1w_2 \ldots w_m $ 的先驗概率： $$ p(s) = p(w_1) \times p(w_2|w_1) \times p(w_3|w_1w_2) \times \cdots \times p(w_m|w_1 \ldots w_{m-1}) $$ $$ p(s) = \prod_{i=1}^{m} p(w_i|w_1 \ldots w_{i-1}) $$

說明：

$ w_i $ 可以是字、詞、短語或詞類等，統稱為統計基元。通常以“詞”(token)代之；
$ w_i $ 的概率取決于 $ w_1, \ldots, w_{i-1} $，條件序列 $ w_1, \ldots, w_{i-1} $ 稱為 $ w_i $ 的歷史(history)。

問題：歷史基元越來越長，參數量迅速增長

解決：將兩個歷史映射到同一個等價類當且僅當這兩個歷史中的最近???1個基元相同，即只考慮歷史基元與當前詞構成??元詞序列，又被稱為n-1階馬爾可夫鏈

可以在句子首尾兩端增加兩個標志$w_0=<BOS>,w_{m+1}=<EOS>$

應用示例音字轉換問題/拼音輸入法

那么n-gram的參數怎么計算呢？

最大似然估計

說白了是用頻率替換概率
數據平滑方法

調整最大似然估計得到的概率值使零概率增值使非零概率下調劫富濟貧消除零概率

目標：降低困惑度

困惑度就是在測試集上對語言模型的評價

測試語料 $ T $ 由 $ l_T $ 個句子構成：$ (s_1, s_2, \cdots, s_{l_T}) $，共含 $ w_T $ 個詞（是總詞數），那么，整個測試集的概率為： $$ p(T) = \prod_{i=1}^{l_T} p(s_i) $$ 困惑度： $$ PP_P(T) = 2^{-\frac{1}{w_T} \log_2 p(T)} $$

數據平滑方法：加1法（重要！）

神經語言模型

n-gram的問題：訓練用數據稀疏、忽略語義相似性

前饋神經網絡語言模型

在使用網絡之前要進行詞向量表示 Word Embeddings

【詞表規模的確定： 1 . 訓練數據中所有詞； 2 頻率高于某個閾值的所
有詞； 3 前 V 個頻率最高的詞】

然后拼接條件詞向量送入網絡，輸出下一個詞的概率分布（本質是多分類問題）

問題：還是僅對小窗口的歷史信息進行建模，n-gram 語言模型僅考慮了前面???1個詞的歷史信息
循環神經網絡語言模型

5 文本表示

簡單的向量空間模型有很多問題。下面介紹表示學習模型。

兩種代表性學習方法：文本概念表示模型（LSA、LDA）、深度表示學習模型

詞語

基于語言模型的方法
- NNLM
  
  《A Neural Probabilistic Language Model（2003）》
  
  詞向量表示用look-up表，也是參數的一部分！所以可以認為，詞的表示是這個神經網絡的副產品。
直接學習法【重點？】
- C&W Model（Collobert & Weston Model）
  
  《Natural Language Processing (Almost) from Scratch（2011）》
  
  負采樣，詞向量優化的過程中，C&W模型希望每一個正樣本應該比對應的負樣本打分高至少1分。
  
  $(w_i, C)=$...
  
  以及loss的公式要會寫。
- CBOW（Continuous Bag of Words，連續詞袋模型） and SG（Skip gram Model，跳字模型）
  
  由Tomas Mikolov等人在2013年提出，均在Word2Vec框架下實現。
  
  CBOW利用上下文詞語預測中心詞語。
  
  SG采用中心詞語預測所有上下文詞語。
  
  缺陷：不能處理多義詞、無法建模詞序信息、靜態詞向量、難以處理 OOV（Out-of-Vocabulary）詞......
- GloVe（Global Vectors for Word Representation）
  
  相比上面兩個模型，考慮到了全局信息。
- 字-詞混合的表示學習
  
  詞語由字或字符構成，詞語可以獲得一個表示，詞語作為字的組合，通過字的表示也可以獲得一個表示，兩種表示結合得到更優表示。

短語

詞袋：直接詞嵌入求平均
遞歸自動編碼器

掌握結構、誤差函數
雙語約束模型

重構誤差+語義誤差

句子

詞袋：直接詞嵌入求平均
PV-DM

Paragraph Vector with sentence as Distributed Memory

是 CBOW 的擴展，建模P的時候增加一個SenId嵌入即可
PV-DBOW

Distributed Bag of Words version of Paragraph Vector

是 SG 的擴展，該模型以
句子為輸入，以句子中隨機抽樣的詞語為輸出，即要求句子能夠預測句中的任意詞語。
gram 模型相同
Skip-Thought

類似于 PV-DBOW，但不同于它利用句子預測句中的詞語， Skip Thought 利用當前句子預測前一個句子與后一個句子 ????+1。
CNN

順序地對上下文窗口進行卷積總結局部信息，并利用池化層 Pooling 提取全局的重要信息，再經過其他網絡層卷積池化層、Dropout 層、線性層等得到固定維度的句子向量表達

文檔

詞袋
層次化模型

CNN / LSTM提取特征，然后送入雙向LSTM，最后不同時刻輸出取平均，再softmax

6 卷積神經網絡

三層前向神經網絡

可以改善句子模型無法考慮到詞序的問題

可以用于情感分類

問題：參數量太大、很難捕獲局部不變性特征

解決：共享參數，且讓每個隱藏層神經元只與局部輸入相連，如2-gram

卷積神經網絡

在早期的文獻中，卷積一般默認為窄卷積。而目前的文獻中，卷積一般默認為等寬卷積（通過padding）

結構特性：權重共享、局部連接、空間或時間上的次采樣

文本CNN

N-gram特征（如句子中的長為3的詞組有哪些）——希望用CNN提取

一維卷積練習

博客：一維卷積練習理解

句子：(N, D) 卷積核：(K, D) ，D是詞嵌入的維度，N是句子長度

代碼實現

PPT代碼實現有誤，conv1接受的輸入，應該為 (1, 4, 7)，即長度在最后，通道數在中間。

應用：情感分類

TextCNN 是利用卷積神經網絡對文本進行分類的算法，由 Yoon Kim 在 “Convolutional Neural Networks for Sentence Classification” 一文中提出. 是2014年的算法.

PPT那個經典示意圖則來自另一篇論文：

Zhang, Ye, and Byron Wallace. "A sensitivity analysis of (and practitioners' guide to) convolutional neural networks for sentence classification."

利用多個不同size的kernel來提取句子中的關鍵信息（類似于多窗口大小的n-gram），從而能夠更好地捕捉局部相關性。

其他應用如：

自然語言推斷（Natural Language Inference），輸入兩個句子，判斷句子之間的關系（蘊含、對立、中立），解決這個問題的模型有BCNN、Pyramid

老師還補充講了Q-Q Matching相關的研究

Q-Q Matching（Query-Query Matching）

泛指對兩個 query 級別的文本（如句子、短語）進行語義對齊與相似度計算的研究方向，廣泛應用于：問答系統中的問題相似匹配（類似問題推薦）、語義檢索（Query-Query Retrieval）、文本蘊含（兩個句子是否有邏輯關系）

常用方法：

Siamese（孿生）結構：兩個句子共享編碼器，輸出嵌入后計算距離（如余弦相似）。

交互式結構：MatchPyramid、BCNN

BCNN（Bilateral Convolutional Neural Network）

出處：
Yin et al., “ABCNN: Attention-Based Convolutional Neural Network for Modeling Sentence Pairs”, 2016

輸入兩個句子 A 和 B。分別通過共享卷積層和池化層提取局部表示。在多個層次上計算兩句話之間的交互信息。
雙向匹配（Bilateral Matching）：不僅 A->B，還 B->A。
拼接各層特征，送入全連接分類層。

比Siamese CNN 強。

Pyramid Matching

出處：
Pang et al., “Text Matching as Image Recognition”, AAAI 2016

輸入兩個句子，計算它們的詞與詞之間的相似度（例如余弦相似），構造一個相似度矩陣（match matrix）。
把這個矩陣看作一張“圖片”。
用多層 CNN（帶池化）提取空間（匹配模式）信息，從局部到全局，形成金字塔結構。
最后將提取的特征送入全連接層分類。

7 RNN

可以直接應用于

情感分類（序列到類別，可以只取最后一個隱層，也可以取所有隱層平均）
分詞（同步的序列到序列）
機器翻譯（異步的序列到序列）（這個之前不知道誒）

反向傳播公式要會推。

訓練算法：BPTT

變體們：

門控循環單元（Gated Recurrent Unit, GRU）
長短期記憶神經網絡（Long Short-Term Memory, LSTM）
深度循環神經網絡（堆疊、雙向）
遞歸神經網絡（Recursive Neural Network, RvNN）

讓神經網絡按指定結構理解信息，比如指定語法樹。

遞歸神經網絡具有更為強大的表示能力，但是在實際應用中并不太流行。一個主要原因是，遞歸神經網絡的輸入是樹/圖結構，而這種結構需要花費很多人工去標注。

適用于遞歸神經網絡的訓練算法：BPTS算法。
- Syntactically-Untied RvNN：不同的句法成分類別對應不同的聚合函數
- Matrix-Vector Recursive Neural Network (Richard Socher et al, 2012)：每個節點由一個向量和一個矩陣來共同表示
- Recursive Neural Tensor Network (Richard Socher et al, 2013)：聚合時引入張量運算
Attentions
- 軟性注意力機制（soft attention mechanism）
  
  兩個步驟是？
- 常見注意力模型：
  - 句子分類
  - 文檔分類（Hierarchical Attention Network）
  - 機器翻譯

RNN的應用

序列標注任務
- 中文分詞 CWS
  
  S：single
  
  B / M / E：begin / middle / end
- 詞性標注POS Tagging
- 命名實體識別NER
  
  B / I：begin / inside
  
  包括實體檢測、實體分類
  
  給了一個雙向LSTM的例子
  
  F1要會算，記住是逐實體統計TP、FP、FN，調和平均別算錯
機器閱讀理解

了解數據集 SQuAD（Stanford Q A Dataset 2016）

10w個（問題，原文，答案）三元組，答案出現在原文中，每個問題含有3個Ground-Truth答案

指標：EM(exact match)、F1要會算，記住是分別和3個Ground-Truth匹配算F1，取最好結果。

2.0版不是所有問題都能在原文找到答案，模型回答no answer才算對（即EM、F1=1）。

解決該問題的模型：
- Match-LSTM 運用attention和ptr
- BiDAF
- R-Net
了解Open-Domain Question Answering（2017）
自然語言推斷

Natural Language Inference

輸出前提P、假設H兩個句子，輸出三個關系之一：蘊含E、對立C、中立N

解決該問題的典型模型：BiLSTM、ESIM
文本生成：作詩、機器翻譯、看圖說話（Image Captioning）

Visual Question Answering (VQA)

8 Transformer

自注意力機制（略）

Transformer架構（略）

回顧神經語言模型的缺陷（不能處理一詞多義）

Embeddings from Language Model （ELMo，2018）

采用多層BiLSTM

詞向量會被輸入到一個多層的雙向LSTM中。每一層的輸出都是整個句子的一個表示。對于每個詞，ELMo將該詞對應的所有LSTM層的輸出（包括原始詞嵌入、前向LSTM的最后一層輸出和后向LSTM的最后一層輸出）進行加權求和，權重是在實際任務中學習得到的，以適應不同的下游任務需求。

預訓練任務，采用了獨特的雙向訓練方法：給定一個詞序列，模型嘗試預測序列中每個位置的下一個詞。與傳統的單向語言模型不同，它會同時訓練兩個方向的LSTM，一個是正向（從前往后）預測，另一個是反向（從后往前）預測。

GLUE（略）

BERT（略）

BART（略）

T5（略）

基于Transformer的文本-視覺預訓練模型

Masked Language Modeling (MLM)
Masked Region Modeling (MRM)
Image-Text Matching (ITM)
CLIP（略）

9 信息抽取

定義(Grishman, 1997)

從自然語言文本中抽取指定類型的實體、關系、事件等事實信息，并形成結構化數據輸出的文本處理技術

目標：從非結構化的文本內容中提取特定的信息。

總之要點是結構化的數據

主要任務：

– 命名實體識別（Named Entity Recognition，NER）
– 實體鏈接（Entity Linking, EL）
– 關系抽取（Relation Extraction，RE）
– 事件抽取（Event Extraction）
– 時間表達式識別（Temporal Expression）
– 模板填充（Template Filling）
– 話題檢測于跟蹤（Topic Detection and Tracking，TDT ）

命名實體識別

基于規則的
基于有監督機器學習的
- 基于HMM的
  
  給定一個待標注的句子$?? = ??_0???_T$（稱為觀測值），序列標注模型
  希望搜索一個標簽序列$?? = ??_0???_T$（稱作狀態值），使得后驗概率
  ??(??|??)最大。
  
  建模過程：頻率替代概率
  
  利用維特比算法解碼最可能的隱狀態
- 基于CRF的
- 基于深度神經網絡的：CNN、BiLSTM、BERT、BART、LLM

實體消歧

分為共指消解（Coreference Resolution）、實體鏈接（Entity Linking）

個人區分方法：哪些（待處理文本）指你？你是（先驗知識中的）哪個？

共指消解的目標就是將文檔中所有指稱進行聚類，將指向同一實體的所有指稱歸為一類

實體鏈接的目標是學習一個映射函數，把文檔中每一個實體指稱$?? = {??_1, ??_2, ? , ??_??} $準確鏈接到實體概念集合$?? = {??_1, ??_2, ? , ??_?? }$中的某個實體

實體鏈接步驟

確定候選實體概念集合

方法：構造“指稱、實體概念”詞典
候選實體概念排序，可分為基于局部的實體排序和基于全局的實體排序（基于全局的就是幾個指稱同時進行實體鏈接）
- 基于局部的：
  
  上下文+指稱詞語送入模型作為特征，實體類別+實體詞語送入另一個模型作為特征，求余弦相似度。
- 基于全局的：
  
  包含兩個步驟
  1. 為文檔中的指稱及其對應的候選實體概念集合構建語義相關圖
    （Referent Graph，RG）
    
    加權無向圖?? =
    (??, ??)，其中??包含所有指稱與候選實體，??中包括兩類邊，“指稱-實體”，“實體-實體”邊
  2. 在相關圖RG上進行實體鏈接的全局推斷

實體鏈接評價

要會算F1！先算指稱集合M的交集，在這個交集的基礎上，再計算實體鏈接結果E的交集，此時剩下的個數就是TP。P和R的分母則分別是|E’|和|E|

系統結果（M, E）：

實體1 -> ID1

實體2 -> ID2

實體3 -> ID3

實體4 -> ID4

人工標注結果（M', E'）：

實體1 -> ID1

實體2 -> ID2

實體5 -> ID5

Precision = |E*| / |E'|

= 2 / 4 = 0.5 （正確匹配的實體ID數 / 系統給出的所有實體ID數）

Recall = |E*| / |E|

= 2 / 3 = 0.67 （正確匹配的實體ID數 / 人工標注的所有實體ID數）

關系抽取

定義：識別文本中的實體并判別實體間關系

??-元關系

關系抽取形式化

關系類別繁多，故探討限定領域給定關系類別集合下的關系識別任務。
基于深度神經網絡的關系分類方法
- 基于分布式表示的關系分類
  
  早期分布式方法的核心思想：
  1. 所有特征采用分布式表示，以克服數據稀疏與語義鴻溝問題
  2. 采用局部表示捕捉實體對周圍的上下文詞匯化特征；
  3. 采用卷積神經網絡捕捉實體對所在句子全局信息。
  詞匯化分布式表示考慮三類特征：
  1. 實體對(??_1, ??_2)自身；
  2. 兩個實體的上下文詞匯；
  3. 實體對在語義知識庫（例如英文的WordNet、中文的HowNet等）中的上位詞。（如姚明->男人）
  具體模型如基于CNN的、基于RvNN的、基于BiLSTM的、基于BERT的、基于LLM的

自動評價

會算F1！

事件抽取

定義：針對特定領域的事件進行事件元素的抽取

事件抽取旨在抽取表明事件類型的觸發詞及其對應的事件元素（或者說是事件參與者和事件屬性）

ACE中定義了8大類33子類的事件類型。

ACE是Automatic Content Extraction（自動內容抽取）的縮寫，它是一個旨在開發和標準化信息抽取技術的項目，特別是針對事件、關系和實體的自動識別與分類。ACE項目由美國國家標準與技術研究院（NIST）發起并維護。

每種類型的事件可以通過一個模板表示，該模板可以是通用模板，也可以是事件類型相關的特定模板。通用模板包含36個槽位，其中一個槽位需要填充觸發詞，其余槽位對應35個角色（事件屬性）

基于聯合模型的事件抽取
基于分布式模型的事件抽取方法

具體模型包括基于CNN的、基于BiGRU的、基于Seq2Seq的、基于LLM的

自動評價

幾乎所有模型都將事件抽取任務分解為：觸發詞識別、事件角色分類

其中，觸發詞識別又分為觸發詞定位、事件類型分類

事件角色分類又分為事件元素識別、角色分類

客觀評測一般對四個子任務分別進行測試。

押題

1. 概念

一些定性的解答

2. 基于規則的方法

分詞算法、一些定性的解答

3. 文本分類

特征選擇相關計算、多項式貝葉斯分類、F1等計算

4. 語言模型

n-gram相關計算

FNN偽代碼/計算

5. 文本表示

幾個模型的細節，loss計算等

小概率考短語和句子的模型

6.CNN

一維卷積計算

7. RNN

各種模型的公式、RNN的反向傳播

8. Transformer

Transformer相比CNN、RNN的優勢？

自注意力機制計算

transformer結構

一些關于transformer的經典問題

ELMo的結構

9. 信息抽取

可能會考信息抽取、實體消歧、關系抽取、事件抽取的基本概念。

實體鏈接的基本方法描述。

關系抽取的方法特點。

事件抽取的步驟。

F1的計算。

很小概率考維特比算法。

其他

用反向傳播公式推導解釋RNN解決不了長程依賴的原因？

（略）
目前中文分詞的難點？

分詞歧義消解、錯別字諧音字規范化、分詞問題。

不包括未登錄詞的識別？

（答案可能有誤）
Bert輸入為什么要進行位置標注？

詞在語句中的位置非常重要。使用同樣的詞語，排列位置不同，語義可能不同。Bert使用堆疊的雙向Transformer Encoder，Transformer主要核心是attention注意力機制，attention機制無法捕捉詞順序，類似一個升級版的“詞袋”模型。故需要進行位置標注添加位置信息。
隱馬爾可夫研究的三大問題：評估問題，解碼問題，學習問題

解決隱馬爾可夫評估問題的方法：前向算法，后向算法

解決隱馬爾可夫解碼問題的方法：維特比算法

解決隱馬爾可夫無法利用上下文信息的方法：最大熵模型

解決隱馬爾可夫輸出之間獨立問題的方法：條件隨機場CRF
Transformer的根號d

點積結果除以根號d的原因是為了防止內積結果過大導致梯度消失或爆炸。具體來說：當輸入向量維度d較大時，點積結果的模長可能變得非常大；過大的值經過softmax函數會導致梯度趨近于0（因為softmax在極端值處導數小）；除以√d可以使得輸入到softmax的值方差保持穩定，緩解上述問題。

維特比算法

維特比算法（Viterbi Algorithm）是用于隱馬爾可夫模型（HMM）中解碼問題的一種動態規劃算法。它的目標是：給定一個觀察序列和HMM參數，找出最有可能生成這個觀察序列的隱藏狀態序列。

給定一個觀測序列 O = {o?, o?, ..., o?}，我們要找出對應的最優狀態序列 Q = {q?, q?, ..., q?}，使得該狀態序列在所有可能的狀態序列中，產生這個觀測序列的概率最大。

定義 δ(t, i) 表示在時間 t 處于狀態 i 時，前 t 個觀測序列為 o?~o? 的最大概率路徑的概率值。

遞推公式如下：

\[\delta(t, i) = \max_{1 \leq j \leq N} [\delta(t-1, j) \cdot A[j][i]] \cdot B[i][o_t] \]

假設我們有兩個天氣狀態（晴天 sunny 和雨天 rainy），以及三種活動（walk, shop, clean）。根據天氣決定活動。

初始概率 π：

π[Sunny] = 0.6
π[Rainy]  = 0.4

狀態轉移矩陣 A：

          Sunny   Rainy
Sunny     0.7      0.3
Rainy     0.4      0.6

觀測概率矩陣 B：

           Walk   Shop   Clean
Sunny      0.5     0.4     0.1
Rainy      0.1     0.3     0.6

給定觀測序列 O：

O = [Walk, Shop, Clean]

我們要求出最有可能的狀態序列 Q。

對于第一個觀測 Walk：

\[\delta(1, Sunny) = \pi(Sunny) \cdot B(Sunny, Walk) = 0.6 \cdot 0.5 = 0.3 \\ \delta(1, Rainy) = \pi(Rainy) \cdot B(Rainy, Walk) = 0.4 \cdot 0.1 = 0.04 \]

ψ(1, Sunny) = None
ψ(1, Rainy) = None

步驟 2：遞推（t=2）

當前觀測為 Shop。

對于 Sunny 狀態：

\[\begin{align*} \text{From Sunny: } & \delta(1, Sunny) \cdot A(Sunny→Sunny) \cdot B(Sunny, Shop) = 0.3 \cdot 0.7 \cdot 0.4 = 0.084 \\ \text{From Rainy: } & \delta(1, Rainy) \cdot A(Rainy→Sunny) \cdot B(Sunny, Shop) = 0.04 \cdot 0.4 \cdot 0.4 = 0.0064 \\ \Rightarrow \delta(2, Sunny) &= \max(0.084, 0.0064) = 0.084 \\ \psi(2, Sunny) &= \text{Sunny} \end{align*} \]

對于 Rainy 狀態：

\[\begin{align*} \text{From Sunny: } & \delta(1, Sunny) \cdot A(Sunny→Rainy) \cdot B(Rainy, Shop) = 0.3 \cdot 0.3 \cdot 0.3 = 0.027 \\ \text{From Rainy: } & \delta(1, Rainy) \cdot A(Rainy→Rainy) \cdot B(Rainy, Shop) = 0.04 \cdot 0.6 \cdot 0.3 = 0.0072 \\ \Rightarrow \delta(2, Rainy) &= \max(0.027, 0.0072) = 0.027 \\ \psi(2, Rainy) &= \text{Sunny} \end{align*} \]

步驟 3：遞推（t=3）

當前觀測為 Clean。

對于 Sunny 狀態：

\[\begin{align*} \text{From Sunny: } & \delta(2, Sunny) \cdot A(Sunny→Sunny) \cdot B(Sunny, Clean) = 0.084 \cdot 0.7 \cdot 0.1 = 0.00588 \\ \text{From Rainy: } & \delta(2, Rainy) \cdot A(Rainy→Sunny) \cdot B(Sunny, Clean) = 0.027 \cdot 0.4 \cdot 0.1 = 0.00108 \\ \Rightarrow \delta(3, Sunny) &= \max(0.00588, 0.00108) = 0.00588 \\ \psi(3, Sunny) &= \text{Sunny} \end{align*} \]

對于 Rainy 狀態：

\[\begin{align*} \text{From Sunny: } & \delta(2, Sunny) \cdot A(Sunny→Rainy) \cdot B(Rainy, Clean) = 0.084 \cdot 0.3 \cdot 0.6 = 0.01512 \\ \text{From Rainy: } & \delta(2, Rainy) \cdot A(Rainy→Rainy) \cdot B(Rainy, Clean) = 0.027 \cdot 0.6 \cdot 0.6 = 0.00972 \\ \Rightarrow \delta(3, Rainy) &= \max(0.01512, 0.00972) = 0.01512 \\ \psi(3, Rainy) &= \text{Sunny} \end{align*} \]

找到最終時刻（t=3）的最大概率狀態：

\[\max(\delta(3, Sunny), \delta(3, Rainy)) = \max(0.00588, 0.01512) = 0.01512 \]

所以最后狀態是 Rainy。

然后根據 ψ 指針回溯：

ψ(3, Rainy) = Sunny
ψ(2, Sunny) = Sunny
ψ(1, Sunny) = None

所以最優狀態序列是：

Q = [Sunny, Sunny, Rainy]

posted @ 2025-07-01 17:42 藤君閱讀(292) 評論(0) 收藏舉報

刷新頁面返回頂部

藤君的小窩

自然語言處理課堂筆記 / 期末復習

課程基本信息

考試

其他

期末沖刺

1 概念

2 基于規則的方法

3 文本分類

4 語言模型

n元文法模型（n-gram model）

神經語言模型

5 文本表示

詞語

短語

句子

文檔

6 卷積神經網絡

三層前向神經網絡

卷積神經網絡

7 RNN

RNN的應用

8 Transformer

9 信息抽取

命名實體識別

實體消歧

關系抽取

事件抽取

押題

其他

維特比算法

公告

藤君的小窩

自然語言處理 課堂筆記 / 期末復習

課程基本信息

考試

其他

期末沖刺

1 概念

2 基于規則的方法

3 文本分類

4 語言模型

n元文法模型（n-gram model）

神經語言模型

5 文本表示

詞語

短語

句子

文檔

6 卷積神經網絡

三層前向神經網絡

卷積神經網絡

7 RNN

RNN的應用

8 Transformer

9 信息抽取

命名實體識別

實體消歧

關系抽取

事件抽取

押題

其他

維特比算法

公告

自然語言處理課堂筆記 / 期末復習