***

# HMM 模型在自然語言處理的應用實作課程

## 課程簡介

Hidden Markov Model (HMM) 是一種統計模型,廣泛應用於自然語言處理領域,特別是詞性標註(POS Tagging)和命名實體識別(Named Entity Recognition)等序列標註任務。

***

## 第一部分:HMM 理論基礎

### HMM 的核心概念

- 隱馬可夫模型（Hidden Markov Model, HMM）就是馬可夫鏈的延伸。
- 馬可夫鏈的意義:當一個隨機過程在給定現在狀態及所有過去狀態情況下（連續事件），其未來狀態的條件機率分布僅依賴於當前狀態。
- 也就是說當前狀態取決於前一狀態之內容。
- 這個想法沒錯，但是太過簡單了，會忽略其他事情的影響，在這個過程中有什麼東西被「隱藏」了，卻仍然默默的影響每個狀態。
- 什麼『原因』導致這樣的『表現』？
- 把這些被「隱藏」起來的特徵（原因）計算進去就是所謂的隱馬可夫模型。

### HMM 的生活例子

小美每天放學時會去買紅茶、珍珠奶茶或咖啡。如果把小美每天買的飲料記錄下來就是她「買飲料」這個事件的馬可夫鏈，這是我們（或小美的同學？）可以觀察的到的現象。然後，我們又依照過去的經驗，得知小美在不同疲憊程度的狀況下買不同飲料的機率，那麼我們是不是就能透過我們已知的觀察和知識，去推測小美的疲憊程度這種隱藏的影響力呢？

在這個例子裡，依照馬可夫鏈的邏輯會有 2 個不同的鏈（序列），一個是我們所觀察得到的，小美每天買的飲料；另一個是我們看不到的（隱藏的），小美的疲憊程度。由於我們知悉這 2 個馬可夫鏈之間的關係，所以我們便可以由其中一個馬可夫鏈的狀態，去預測另一個馬可夫鏈的狀態。所謂「隱馬可夫模型」便是描述這樣兩個序列關係的統計模型。所以說，HMM 就是以「看得到的」連續現象去探究及預測另一個「看不到的」連續現象為目的而產生的模型。

### HMM 的名詞

HMM是一種概率圖模型,用於建模具有隱藏狀態的序列數據。模型包含以下核心要素:

- **隱藏狀態(Hidden States)**: 不可直接觀測的內部狀態
- **觀測序列(Observations)**: 可觀測的輸出符號
- **轉移機率(Transition Probability)**: 狀態之間轉換的機率
- **發射機率(Emission Probability)**: 在特定狀態下產生觀測值的機率
- **初始機率(Initial Probability)**: 初始狀態的機率分布

### HMM 的應用場景

HMM在自然語言處理中有多種應用:

1. **詞性標註(POS Tagging)**:
- 標記句子中每個詞的詞性(名詞、動詞等)
- 是什麼「文字」是已知的序列，詞性會因為句型、位置、時態等等有所變化，所以我們會透過已知的文字序列背後所包含的所有資訊去推估詞性這個隱藏序列，進而達成詞性標記。
3. **命名實體識別(NER)**: 識別文本中的人名、地名、組織名等
4. **語音識別**:
- 語音辨識系統，人說話的聲音以音節（syllable）來標記，所以理論上，我們如果有一段錄音，只要能清楚分辨每一個音節發的音是哪些母音與子音，就能夠辨識出這個人所說的話並轉換成文字。
- 語音這個「音節序列」是看得到的訊號，而語音辨識系統想要做的正好是 HMM 所模擬的狀況，推測出與其相對應看不到的「文字序列」。

***

## 第二部分:Python 套件介紹

### 主要 Python 套件

在Python生態系統中,有多個套件可實作HMM:

#### 1. hmmlearn

**特點**:
- 基於NumPy、SciPy和scikit-learn構建
- 支援高斯HMM和多項式HMM
- 簡單易用的API
- 適合初學者和簡單任務

**安裝方式**:

pip install hmmlearn

#### 2. NLTK

**特點**:
- 自然語言處理的經典工具包
- 內建HMM類別用於POS標註
- 提供豐富的語料庫資源

**安裝方式**:

pip install nltk

#### 3. pomegranate

**特點**:
- 支援多種類型的HMM(離散、高斯、混合模型)
- 使用Cython優化,效能優異
- 支援平行化訓練
- 適合進階HMM任務

**安裝方式**:

pip install pomegranate

***

## 實作範例一 - 使用 hmmlearn 進行天氣預測

### 實作目標

建立一個簡單的HMM模型,根據歷史天氣資料預測未來天氣狀態。

### 完整程式碼

import numpy as np
from hmmlearn import hmm
import matplotlib.pyplot as plt

# 設定隨機種子以確保結果可重現
np.random.seed(42)

# 定義模型參數
# 隱藏狀態: 0=晴天, 1=雨天
n_states = 2
# 觀測值: 0=乾燥, 1=潮濕, 2=濕透
n_observations = 3

# 建立高斯混合HMM模型
model = hmm.CategoricalHMM(n_components=n_states, n_features=n_observations)

# 設定初始機率 (起始狀態的機率分布)
model.startprob_ = np.array([0.6, 0.4])  # 60%機率晴天開始

# 設定轉移機率矩陣
# [晴天->晴天, 晴天->雨天]
# [雨天->晴天, 雨天->雨天]
model.transmat_ = np.array([
    [0.7, 0.3],  # 晴天有70%維持晴天, 30%轉為雨天
    [0.4, 0.6]   # 雨天有40%轉晴天, 60%維持雨天
])

# 設定發射機率矩陣
# 每個狀態產生各種觀測值的機率
model.emissionprob_ = np.array([
    [0.7, 0.2, 0.1],  # 晴天: 70%乾燥, 20%潮濕, 10%濕透
    [0.1, 0.3, 0.6]   # 雨天: 10%乾燥, 30%潮濕, 60%濕透
])

# 生成觀測序列
observations = np.array([[0], [1], [2], [1], [0], [1], [2], [2], [1], [0]]).reshape(-1, 1)

# 使用Viterbi算法預測最可能的隱藏狀態序列
logprob, hidden_states = model.decode(observations, algorithm="viterbi")

print("觀測序列:", observations.flatten())
print("預測的隱藏狀態:", hidden_states)
print("序列對數機率:", logprob)

# 將數字轉換為標籤
obs_labels = ['乾燥', '潮濕', '濕透']
state_labels = ['晴天', '雨天']

print("\n=== 預測結果 ===")
for i, (obs, state) in enumerate(zip(observations.flatten(), hidden_states)):
    print(f"時刻 {i+1}: 觀測={obs_labels[obs]}, 預測天氣={state_labels[state]}")

### 執行結果分析

程式執行後會輸出:
- 觀測序列: 每個時間點的觀測值
- 預測的隱藏狀態: 使用Viterbi算法推斷的最可能天氣狀態
- 序列對數機率: 該狀態序列的機率值

***

### Viterbi Algorithm

是一種用於隱馬可夫模型（HMM）中解碼問題的動態規劃演算法，目的是找到給定觀測序列條件下，最可能的隱藏狀態序列。

其主要特色是將整個隱藏狀態序列作為一體來考慮，通過逐步遞推計算每一時間點各狀態的最大概率路徑，並用記錄的路徑資訊進行最後的回溯，從而找到全局最優的狀態序列。

維特比算法的核心步驟包括：

1. **初始化**：計算在第一個時間點所有狀態的概率，結合模型的初始狀態概率及該狀態產生第一個觀測值的機率。
2. **遞推**：對每個時間點和每個狀態，計算從上一時間點所有可能狀態轉移而來的最大概率乘以當前狀態對應觀測概率，選出最大者。
3. **終止**：在最後一個時間點選擇最大概率的狀態作為結尾。
4. **回溯**：根據記錄的最大概率狀態路徑，從末端到起始端回溯，得到最可能的隱狀態序列。

維特比算法在自然語言處理（如詞性標註）、語音識別、基因序列分析等領域有廣泛應用。

簡單說，維特比算法幫助我們精確找出最可能隱藏在觀測資料背後的狀態序列，而非只考慮每個時刻最可能的單一狀態，避免了可能的不一致路徑或無效轉移。

演算法最終透過回溯找到最大概率的隱狀態序列。

這樣的流程確保找到的是全局最優解，不是分時刻獨立選擇的局部最優解。

***

## 實作範例二 - 使用 NLTK 進行詞性標註

### 實作目標

使用Penn Treebank(PTB)語料庫訓練HMM模型進行英文詞性標註。

[Penn Treebank P.O.S. Tags](https://www.ling.upenn.edu/courses/Fall_2003/ling001/penn_treebank_pos.html)

treebank.tagged_sents()[:1] # list Brown corpus 中的前兩個標記句子

[[('Pierre', 'NNP'),
('Vinken', 'NNP'),
(',', ','),
('61', 'CD'),
('years', 'NNS'),
('old', 'JJ'),
(',', ','),
('will', 'MD'),
('join', 'VB'),
('the', 'DT'),
('board', 'NN'),
('as', 'IN'),
('a', 'DT'),
('nonexecutive', 'JJ'),
('director', 'NN'),
('Nov.', 'NNP'),
('29', 'CD'),
('.', '.')],

### 完整程式碼

import nltk
from nltk.corpus import treebank
from nltk.tag import hmm

# 下載必要的語料庫 (首次執行需要)
try:
    nltk.data.find('corpora/treebank')
except LookupError:
    nltk.download('treebank')

# 載入Penn Treebank資料集
print("載入語料庫...")
corpus = treebank.tagged_sents()
print(f"總句子數: {len(corpus)}")

# 分割訓練集與測試集
train_size = int(len(corpus) * 0.8)
train_data = corpus[:train_size]
test_data = corpus[train_size:]

print(f"訓練集大小: {len(train_data)} 句")
print(f"測試集大小: {len(test_data)} 句")

# 訓練HMM詞性標註器
print("\n開始訓練HMM模型...")
trainer = hmm.HiddenMarkovModelTrainer()
hmm_tagger = trainer.train_supervised(train_data)

# 評估模型
print("評估模型準確度...")
test_accuracy = hmm_tagger.accuracy(test_data)
print(f"測試集準確度: {test_accuracy:.4f} ({test_accuracy*100:.2f}%)")

# 測試單句標註
from nltk import word_tokenize # 斷詞系統
test_sentence = word_tokenize("I've learned how to use Brown corpus to train an HMM tagger.")
test_sentence = ["The", "economy", "is", "strong", "."]
print(f"\n測試句子: {' '.join(test_sentence)}")

# 進行詞性標註
tagged_sentence = hmm_tagger.tag(test_sentence)
print("\n詞性標註結果:")
for word, tag in tagged_sentence:
    print(f"  {word:15s} -> {tag}")

# 顯示部分標籤說明
tag_explanation = {
    'DT': '限定詞 (Determiner)',
    'NN': '名詞-單數 (Noun-singular)',
    'NNS': '名詞-複數 (Noun-plural)',
    'VBZ': '動詞-第三人稱單數 (Verb-3rd person singular)',
    'VBP': '動詞-非第三人稱單數 (Verb-non-3rd person)',
    'JJ': '形容詞 (Adjective)',
    '.': '句號 (Period)'
}

print("\n=== 標籤說明 ===")
for word, tag in tagged_sentence:
    if tag in tag_explanation:
        print(f"{tag}: {tag_explanation[tag]}")

### 程式說明

這個範例展示了監督式學習的HMM應用:
1. 使用已標註的語料庫進行訓練
2. 自動學習詞性轉移機率和詞彙發射機率
3. 對新句子進行詞性標註預測

***

## 實作範例三 - 使用 pomegranate 進行命名實體識別

### 實作目標

實作簡單的BIO標註系統進行命名實體邊界識別。

### 完整程式碼

import numpy as np
from pomegranate import *

# 定義訓練語料 (簡化版)
# 格式: (詞彙, BIO標籤)
# B: 實體開始, I: 實體內部, O: 非實體
train_sentences = [
    [('John', 'B-PER'), ('lives', 'O'), ('in', 'O'), ('New', 'B-LOC'), ('York', 'I-LOC'), ('.', 'O')],
    [('Mary', 'B-PER'), ('works', 'O'), ('at', 'O'), ('Google', 'B-ORG'), ('.', 'O')],
    [('Apple', 'B-ORG'), ('is', 'O'), ('in', 'O'), ('California', 'B-LOC'), ('.', 'O')],
    [('Tom', 'B-PER'), ('visited', 'O'), ('Paris', 'B-LOC'), ('last', 'O'), ('year', 'O'), ('.', 'O')],
]

# 建立詞彙表和標籤集
vocab = set()
tags = set()
for sentence in train_sentences:
    for word, tag in sentence:
        vocab.add(word)
        tags.add(tag)

vocab = sorted(list(vocab))
tags = sorted(list(tags))

print(f"詞彙量: {len(vocab)}")
print(f"標籤集: {tags}")

# 建立詞彙和標籤的索引映射
word2idx = {w: i for i, w in enumerate(vocab)}
tag2idx = {t: i for i, t in enumerate(tags)}
idx2tag = {i: t for t, i in tag2idx.items()}

# 準備訓練數據
X_train = []
y_train = []

for sentence in train_sentences:
    words = [word for word, tag in sentence]
    labels = [tag2idx[tag] for word, tag in sentence]
    X_train.append(words)
    y_train.append(labels)

print(f"\n訓練句子數: {len(X_train)}")

# 手動計算轉移機率和發射機率
# 計算標籤轉移次數
tag_transitions = np.zeros((len(tags), len(tags)))
tag_counts = np.zeros(len(tags))

for labels in y_train:
    for i in range(len(labels)):
        tag_counts[labels[i]] += 1
        if i > 0:
            tag_transitions[labels[i-1]][labels[i]] += 1

# 計算轉移機率 (加入平滑)
transition_prob = (tag_transitions + 0.01) / (tag_counts[:, np.newaxis] + 0.01 * len(tags))

# 計算發射機率
emission_counts = {}
for sentence, labels in zip(X_train, y_train):
    for word, label in zip(sentence, labels):
        if label not in emission_counts:
            emission_counts[label] = {}
        emission_counts[label][word] = emission_counts[label].get(word, 0) + 1

print("\n=== 轉移機率矩陣 (部分) ===")
print(f"{'':10s}", end='')
for tag in tags[:4]:
    print(f"{tag:10s}", end='')
print()
for i, tag in enumerate(tags[:4]):
    print(f"{tag:10s}", end='')
    for j in range(min(4, len(tags))):
        print(f"{transition_prob[i][j]:10.4f}", end='')
    print()

# 測試句子
test_sentence = ["Tom", "lives", "in", "Paris", "."]
print(f"\n=== 測試句子 ===")
print(f"輸入: {' '.join(test_sentence)}")

# 簡化版Viterbi解碼
def simple_viterbi_decode(sentence, transition_prob, emission_counts, tag2idx, idx2tag, vocab):
    n_tags = len(tag2idx)
    n_words = len(sentence)
    
    # 初始化機率矩陣
    viterbi = np.zeros((n_tags, n_words))
    backpointer = np.zeros((n_tags, n_words), dtype=int)
    
    # 初始化
    for t in range(n_tags):
        word = sentence[0]
        if t in emission_counts and word in emission_counts[t]:
            emit_prob = emission_counts[t][word] / sum(emission_counts[t].values())
        else:
            emit_prob = 0.0001  # 未見過的詞
        viterbi[t][0] = (1.0 / n_tags) * emit_prob
    
    # 前向傳播
    for w in range(1, n_words):
        word = sentence[w]
        for t in range(n_tags):
            if t in emission_counts and word in emission_counts[t]:
                emit_prob = emission_counts[t][word] / sum(emission_counts[t].values())
            else:
                emit_prob = 0.0001
            
            max_prob = -1
            max_state = 0
            for prev_t in range(n_tags):
                prob = viterbi[prev_t][w-1] * transition_prob[prev_t][t] * emit_prob
                if prob > max_prob:
                    max_prob = prob
                    max_state = prev_t
            
            viterbi[t][w] = max_prob
            backpointer[t][w] = max_state
    
    # 回溯
    best_path = [0] * n_words
    best_path[-1] = np.argmax(viterbi[:, -1])
    
    for w in range(n_words-2, -1, -1):
        best_path[w] = backpointer[best_path[w+1]][w+1]
    
    return [idx2tag[t] for t in best_path]

# 執行預測
predicted_tags = simple_viterbi_decode(
    test_sentence, transition_prob, emission_counts, 
    tag2idx, idx2tag, vocab
)

print("\n=== 預測結果 ===")
for word, tag in zip(test_sentence, predicted_tags):
    print(f"{word:15s} -> {tag}")

### 程式重點說明

這個範例實作了NER的核心概念:
- BIO標註格式用於標記實體邊界
- 計算標籤間的轉移機率
- 計算詞彙在各標籤下的發射機率
- 使用Viterbi算法進行解碼

---

### Viterbi 算法詳解

Viterbi算法是HMM解碼的核心:

def viterbi_algorithm_explained(observations, states, start_prob, trans_prob, emit_prob):
    """
    Viterbi算法的詳細實作
    
    參數:
        observations: 觀測序列
        states: 隱藏狀態列表
        start_prob: 初始機率
        trans_prob: 轉移機率矩陣
        emit_prob: 發射機率矩陣
    
    返回:
        最可能的狀態序列
    """
    V = [{}]  # Viterbi表格
    path = {}  # 路徑記錄
    
    # 初始化 (t=0)
    for state in states:
        V[0][state] = start_prob[state] * emit_prob[state][observations[0]]
        path[state] = [state]
    
    # 動態規劃 (t=1 to T)
    for t in range(1, len(observations)):
        V.append({})
        new_path = {}
        
        for curr_state in states:
            # 計算所有可能前狀態的機率
            (prob, prev_state) = max(
                (V[t-1][prev] * trans_prob[prev][curr_state] * 
                 emit_prob[curr_state][observations[t]], prev)
                for prev in states
            )
            
            V[t][curr_state] = prob
            new_path[curr_state] = path[prev_state] + [curr_state]
        
        path = new_path
    
    # 找出最可能的最終狀態
    (prob, final_state) = max((V[len(observations)-1][state], state) 
                               for state in states)
    
    return path[final_state], prob

# 使用範例
states = ('晴天', '雨天')
observations = ('乾燥', '潮濕', '濕透')

start_prob = {'晴天': 0.6, '雨天': 0.4}

trans_prob = {
    '晴天': {'晴天': 0.7, '雨天': 0.3},
    '雨天': {'晴天': 0.4, '雨天': 0.6}
}

emit_prob = {
    '晴天': {'乾燥': 0.7, '潮濕': 0.2, '濕透': 0.1},
    '雨天': {'乾燥': 0.1, '潮濕': 0.3, '濕透': 0.6}
}

obs_sequence = ['乾燥', '潮濕', '濕透']
path, prob = viterbi_algorithm_explained(obs_sequence, states, start_prob, trans_prob, emit_prob)

print("觀測序列:", obs_sequence)
print("最可能的狀態序列:", path)
print("路徑機率:", prob)

***

### 核心知識回顧

- HMM的理論基礎與核心概念
- Python主要HMM套件的使用(hmmlearn, pomegranate, NLTK)
- 實作詞性標註和命名實體識別
- Viterbi算法的原理與實作
- 模型評估與優化技巧

### 延伸學習資源

1. **條件隨機場(CRF)**: HMM的判別式模型版本
2. **深度學習方法**: LSTM、BERT等現代NLP模型
3. **語音識別**: HMM在語音領域的應用
4. **生物資訊學**: DNA序列分析中的HMM應用

## 參考資料

- NLTK官方文件: https://www.nltk.org/
- hmmlearn文件: https://hmmlearn.readthedocs.io/
- pomegranate文件: https://pomegranate.readthedocs.io/

***