NLP 学習ノート（1）：テキスト処理と統計的手法 - Bojin Li

メルボルン大学で COMP90042（NLP）を受講したときの学習ノートです。本稿では、テキストの前処理、BPE、N-gram と平滑化、テキスト分類、品詞タグ付け、HMM、Viterbi を扱います。

1. テキストの前処理

1.1 基本的な定義

用語	定義
Word：単語	意味や文法上の機能を持つ文字の並び（a sequence of characters with a meaning and/or function）
Sentence：文	単語を文法規則に従って組み合わせ、一つのまとまった意味を表す単位。句読点や構造上の境界で終わる
Document：文書	ニュース記事やメールなど、複数の文からなる連続したテキストの単位
Corpus：コーパス	学習や評価のために一定の規模で収集したテキストの集合（単数形は corpus、複数形は corpora）
Word token：単語トークン（延べ語）	テキスト内の単語の一つひとつの出現を数えたもの。"to be or not to be" には 6 トークンある
Word type：単語タイプ（異なり語）	重複を除いた異なる単語。"to be or not to be" には 4 タイプある
Lexicon：語彙辞書	ある言語や分野に属する全単語タイプと、その語彙項目の情報の集合

覚えておくこと：トークン数 ≥ タイプ数。コーパスの規模は、一般に $\vert V\vert$ （語彙サイズ）と総トークン数で表す。

1.2 なぜ前処理が必要なのか

Language is compositional. 人間は文書を構成要素に分けて理解できる。コンピュータに言語を理解させるにも、同様の分解が必要になる。

前処理は、生の文字列をタスクに適した表現へ段階的に変換する。以下は従来型のテキスト処理の模式的な流れ。

TEXT

"<p> Hi there. I'm TARS. </p>"
  → 書式の除去      "Hi there. I'm TARS."
  → 文分割          ["Hi there.", "I'm TARS."]
  → 単語分割        [["Hi","there","."], ["I","'m","TARS","."]]
  → 正規化          [["hi","there","."], ["i","be","tars","."]]
  → ストップワード除去 [["hi","tars","."]]        （例）

1.3 前処理の 5 ステップ

どの処理を使うかはタスクに応じて選ぶ。すべてのモデルで全手順を実行するわけではない。言語モデルでは通常、句読点、語形、機能語を残す必要がある。現代の事前学習済みモデルでも、学習時と同じトークナイザを使うべきである。

図 1-1　テキスト前処理の 5 段階のパイプラインと、各段階での同じ文の形。

手順	英語名	目的
1	Remove unwanted formatting	HTML/XML タグ、Markdown 記法、余分な空白、エスケープ文字を取り除く
2	Sentence segmentation：文分割	文書を文に分割する
3	Word tokenisation：単語分割	文をトークンに分割する。BPE などのサブワード方式も含む
4	Word normalisation：単語の正規化	大文字・小文字、綴り、語形を統一する（見出し語化／ステミング）
5	Stopword removal：ストップワード除去	高頻度で情報量の少ない機能語を除く

ステップ 2：文分割（Sentence Segmentation）

単純なものから順に 4 つの方法がある。

句読点による分割：. ! ?で文を区切る。
- 問題：略語（Dr. Smith）、小数（3.14）、URL（example.com）を誤って分割してしまう。
正規表現による分割：パターンマッチングでよくある例外に対処する。例えば (?<!\bDr)\.\s+ を使ったり、ピリオドの後に大文字が続くことを条件にしたりする。
辞書を使う方法：略語や例外の辞書（Mr., Dr., U.S.A., e.g.）を用意し、一致した箇所では分割しない。
機械学習（系列ラベリング）：
- Method：各境界候補（通常は句読点）について、二値分類で「ここは本当に文境界か」を判断する。全体を系列ラベリング問題として扱うこともできる。
- Model：ロジスティック回帰／最大エントロピー／CRF／BiLSTM-CRF／小規模な Transformer 分類器。
- Features：
- - 句読点そのもの（. vs ? vs !）
  - 直前のトークンとその形態（略語か、数値か、長さ、大文字か）
  - 直後のトークンが大文字で始まるか、文頭によく現れる単語か
  - 句読点の直後に閉じ引用符や閉じ括弧などがあるか
  - 文脈ウィンドウ内のトークンの n-gram 特徴、略語辞書に含まれるか

ステップ 3：単語分割（Word Tokenisation）

英語：まず空白で区切り、次に句読点や短縮形・略語を処理する（Penn Treebank の規則の例：don't → do + n't、U.S. → U.S. は 1 トークンとして残す）。難しいのは what's a word?（New York は 1 語か 2 語か？）
中国語：単語間に空白がないため、単語分割が必要になる。MaxMatch（最大一致法）を参照。
サブワード（Subword）：BPE など。第 2 節を参照。

中国語の MaxMatch（最大一致法）

考え方：辞書を与え、左または右から貪欲に辞書中の最長一致文字列を単語として取り出す。

例：

TEXT

辞書：{去买新, 西兰花, 西兰花新}
入力文：去买新西兰花

前向き最大一致法（FMM、左から右へ、最長一致を優先）：
  位置 0："去买新" を試す（長さ 3、辞書にある）→「去买新」を取り出す
  位置 3："西兰花" を試す（長さ 3、辞書にある）→「西兰花」を取り出す
  結果：去买新 / 西兰花

要点と限界：

FMM（前向き最大一致法）と RMM（後ろ向き最大一致法）は結果が異なることがある。実際には両方を実行し、規則で曖昧性を解消することが多い。
貪欲法では大域最適解は保証されない。曖昧な文字列（「新西兰/花」と「新/西兰花」など）を誤分割しやすい。
辞書にない未知語（OOV）には対応できず、規則や統計モデル（HMM/CRF による分割、jieba など）との併用が必要。
利点：実装が非常に単純で高速。学習データが不要。

ステップ 4：単語の正規化（Word Normalisation）

目的：

語彙サイズを減らし（USA / U.S.A. / usa → 同じ単語）、データのスパース性を和らげる。
異なる語形を同じ意味単位に対応させ、限られたデータからより安定した統計量を学習できるようにする。
表記（大文字・小文字、全角・半角、綴りの異形）を統一し、照合や検索をしやすくする。

方法：

大文字・小文字の統一（case folding）：The → the（固有名詞や略語の情報が失われる点に注意）
綴りの正規化：colour → color、organise → organize
数値・日付の正規化：2024-01-01、3.14 の共通表記は <NUM>
語形の正規化：Lemmatisation または Stemming（下記参照）

Removing Morphology：2 種類の形態変化の違い

種類	Inflectional Morphology（屈折）	Derivational Morphology（派生）
意味	同じ単語の異なる文法形態	既存の単語から新しい単語を作る
例	名詞の複数形 +s、動詞の三人称単数形 +s、時制・相の形 +ed/+ing、形容詞の比較級 +er、最上級 +est	接尾辞による品詞の変化：person → personally、接頭辞による意味の変化：write → rewrite
品詞・意味が変わるか	変わらない	変わる

見出し語化とステミングの比較

観点	Lemmatisation（見出し語化）	Stemming（ステミング）
処理内容	屈折を取り除き、lemma（辞書の見出し語）に戻す	接尾辞を取り除き、語幹を残す
方式	Lexicon-based（辞書と品詞に依存）	Rule-based（通常は接辞を削除する規則の集合）
出力	意味を持つ実在の単語	実在の単語でない語幹になることがある（studies → studi）
速度	遅い（辞書・品詞情報の参照が必要）	速い
適したタスク	実在の語形が必要で、意味に敏感なタスク（生成や可読性を重視する処理など）	大規模な統計処理、検索、分類（語形が一貫していればよい場合）

Porter Stemmer

最も広く使われる英語のステミングアルゴリズム。Porter が 1980 年に提案した。規則と条件（尺度 $m$ ）に従って処理する。
処理順序：まず屈折接尾辞を除去（inflectional：-s, -es, -ed, -ing）、次に派生接尾辞を除去（derivational：-ational, -fulness, -ness, -ment）。
特徴：高速で辞書が不要。ただし、語幹を削りすぎたり、削り足りなかったりする（university → univers、generously → gener）。

ステップ 5：ストップワード除去（Stopword Removal）

定義：コーパス中に頻繁に現れるが、話題に関する情報をほとんど持たない語。例えば the, a, of, is, and, to。
目的：
- 特徴量の次元を減らし、計算・保存コストを抑える。
- ノイズを除き、モデルを内容語に集中させる。
- 一般に、検索や話題分類のタスクに有効。
選び方：
1. 閉じたクラスの語・機能語：限定詞、前置詞、接続詞、代名詞、助動詞など（closed-class words。語数が限られ、新語がほとんど加わらない）。
2. 高頻度語：コーパスの頻度を数え、上位 $k$ 語を選ぶ（not, no などの否定語を誤って除かないよう、人手で確認する）。
3. 既存のリスト：NLTK の stopwords、spaCy のストップワードリスト（言語ごとに読み込める）。
注意：感情分析、否定検出、構文解析などにストップワードリストをそのまま適用してはいけない。例えば not good から not を除くと意味が変わる。除去の可否はタスクと検証結果に基づいて決める。

2. BPE によるサブワード分割

2.1 動機

語彙サイズのジレンマ：大きすぎるとパラメータが膨大になり、データが疎になる。小さすぎると未知語（OOV）が増える。
サブワードはその折衷案。よく使う単語はそのまま残し、まれな単語は小さな意味のある断片に分割する。
- Colourless green ideas sleep furiously → [colour] [less] [green] [idea] [s] [sleep] [furious] [ly]

2.2 アルゴリズム（Byte-Pair Encoding）

学習（マージ規則の獲得）

すべての単語を 1 文字ずつの列に分解し、語末に終端記号 _（または </w>）を付けて単語頻度を数える。
すべての隣接する記号のペアの出現頻度を数える。
最も頻度の高いペアをマージして新しい記号にし、語彙に加える。
所定のマージ回数 $k$ （または語彙サイズ）に達するまで、手順 2〜3 を繰り返す。
出力：学習順に並べたマージ規則のリストと、最終的なサブワード語彙。

符号化（新しいテキストのトークン化）

学習したマージ順に従って規則を適用する。どの規則にも該当しない部分は 1 文字ずつ残る。そのため符号化は決定的であり、頻度を数え直す必要はない。

2.3 具体例

コーパス（語末は _ で表す）：

Corpus	Frequency
o l d _	7
o l d e r _	3
f i n e s t _	9
l o w e s t _	4

初期の隣接ペアの頻度

Pair	Count	内訳
(e, s)	13	finest_ 9 + lowest_ 4
(s, t)	13	finest_ 9 + lowest_ 4
(t, _)	13	finest_ 9 + lowest_ 4
(o, l)	10	old_ 7 + older_ 3
(l, d)	10	old_ 7 + older_ 3
(f, i)	9	finest_ 9
(i, n)	9	finest_ 9
(n, e)	9	finest_ 9
(d, _)	7	old_ 7
(l, o)	4	lowest_ 4
(o, w)	4	lowest_ 4
(w, e)	4	lowest_ 4
(d, e)	3	older_ 3
(e, r)	3	older_ 3
(r, _)	3	older_ 3

マージの過程（同頻度の場合の選択は実装上の規約による。最初に現れたものや辞書順で最小のものを選ぶ方法が一般的）

回	マージ	頻度	処理後のコーパス
1	e + s → es	13	o l d _(7) o l d e r _(3) f i n es t _(9) l o w es t _(4)
2	es + t → est	13	f i n est _(9) l o w est _(4)
3	est + _ → est_	13	f i n est_(9) l o w est_(4)
4	o + l → ol	10	ol d _(7) ol d e r _(3)
5	ol + d → old	10	old _(7) old e r _(3)
6	f + i → fi	9	fi n est_(9)
7	fi + n → fin	9	fin est_(9)
8	fin + est_ → finest_	9	finest_(9)
9	old + _ → old_	7	old_(7)

各行には、その回のマージで変わった単語だけを示す。それ以外の単語は変わらない。

最終語彙の一部：o, l, d, e, r, f, i, n, s, t, w, _, es, est, est_, ol, old, fi, fin, finest_, old_, …

図 2-1　BPE がコーパスから学習したマージ操作（r · → r·、l o → lo、lo w → low、e r· → er·）。ここでは論文の元の例を用いている。出典：Sennrich et al., Neural Machine Translation of Rare Words with Subword Units, ACL 2016, Figure 1。

2.4 要点と補足

ハイパーパラメータ：マージ回数／目標語彙サイズ。「単語」と「文字」の粒度のトレードオフを決める。
利点：語彙サイズを制御できる。高頻度語は単語のまま残し、低頻度語はサブワードに分けてスパース性を緩和できる。必要な文字が初期文字集合に含まれていれば分割を続けられるが、含まれない文字は未知記号になる可能性がある。byte-level BPE や byte fallback は、この問題への追加の対処法になる。
限界：意味ではなく頻度に基づく分割なので、境界が不自然になることがある。異なるコーパスや分野では異なる分割が学習される。
代表的な方式：BPE、WordPiece（BERT が使用）と Unigram（T5 が使用）。SentencePiece はツールキットであり、BPE や Unigram などを実装している。空白で事前に単語分割せず、生のテキストを直接処理できる。ツールの名称を、特定のアルゴリズムの同義語として扱ってはいけない。

3. N-gram 言語モデル

3.1 タスク

言語モデル（Language Model, LM）は、単語列に確率 $P(w_1, w_2, \dots, w_m)$ を割り当てる。

文を生成するには： $P(w_t \mid w_{<t})$ から順にサンプリングするか argmax を取り、1 語ずつ生成する。これを <eos> まで続ける。
文の良さを比較するには：モデルが与える文全体の確率、対数確率、パープレキシティを比べる。同じモデルとトークン化規則の下では、確率が高いほど学習データの分布に沿う傾向がある。異なる長さの文を比べる場合は、長さによる正規化にも注意が必要。

3.2 応用

綴り訂正／入力候補の順位付け（I have a gu → guy? gun? gut?）
音声認識（同音異義語の識別）
機械翻訳（より流暢な訳文の選択）
文章生成や要約の流暢さの評価

3.3 N-gram とは

N-gram：連続する $n$ 個のトークンからなる部分列。

$n$	名称	例（the dog barks）
1	unigram	the / dog / barks
2	bigram	the dog / dog barks
3	trigram	the dog barks

N-gram 言語モデルの仮定：位置 $t$ の単語は、直前の $n-1$ 語だけに依存する。

3.4 N-gram を支える 3 つの概念・仮定

(a) 同時確率から条件付き確率へ（連鎖律）

例として I like apple を考える。

同時確率： $P(\text{I like apple}) = P(\text{I}) \cdot P(\text{like} \mid \text{I}) \cdot P(\text{apple} \mid \text{I like})$
連鎖律（任意の長さで成立）：

P(w_1, w_2, \dots, w_m) = \prod_{i=1}^{m} P(w_i \mid w_1, \dots, w_{i-1})

問題：後ろの条件付き確率ほど条件となる履歴が長くなり、コーパスからの推定が困難になる（データのスパース性）。文が長くなると、パラメータ数も指数的に増える。
条件付き確率： $P(A\mid B) = \dfrac{P(A,B)}{P(B)}$ 。

(b) マルコフ仮定（Markov Assumption）

全履歴ではなく、直前の $n-1$ 語だけに依存すると仮定する。

P(w_1, \dots, w_m) \approx \prod_{i=1}^{m} P(w_i \mid w_{i-n+1}, \dots, w_{i-1})

$n$	モデル	式
1	unigram	$P(w_1,\dots,w_m) = \prod_{i=1}^{m} P(w_i)$
2	bigram	$P(w_1,\dots,w_m) = \prod_{i=1}^{m} P(w_i \mid w_{i-1})$
3	trigram	$P(w_1,\dots,w_m) = \prod_{i=1}^{m} P(w_i \mid w_{i-2}, w_{i-1})$

相対頻度を使って条件付き確率を推定する。

P(w_i \mid w_{i-1}) = \frac{C(w_{i-1}, w_i)}{C(w_{i-1})}, \qquad P(w_i) = \frac{C(w_i)}{M}

ここで $C(\cdot)$ はカウント、 $M$ は総トークン数。

手計算の例

コーパス（2 文。文頭と文末の記号は <s> <eos>）：

TEXT

<s> yes no no no no yes <eos>
<s> no no no yes yes no <eos>

確率	計算	結果
$P(\text{yes} \mid \text{<s>})$	$1 / 2$	0.5
$P(\text{no} \mid \text{yes})$	$2 / 4$	0.5
$P(\text{no} \mid \text{no})$	$5 / 8$	0.625
$P(\text{yes} \mid \text{no})$	$2 / 8$	0.25
$P(\text{<eos>} \mid \text{yes})$	$1 / 4$	0.25
$P(\text{<eos>} \mid \text{no})$	$1 / 8$	0.125

コーパス中で yes は 4 回、no は 8 回現れる。同じ先行語に続く候補には、文末記号も含める必要がある。例えば no に続く語の確率の和は $5/8+2/8+1/8=1$ 。

3.5 N-gram の 3 つの問題

問題	現象	対処法
a) 長距離依存	直前の $n-1$ 語しか見ないため、離れた文脈を無視する（"The trophy would not fit in the suitcase because it was too big" の it の照応先を決めるには長距離の情報が必要）	次数 $n$ を増やす（ただしスパース性が増す）、キャッシュモデル、RNN/Transformer
b) 確率が非常に小さい	値が $<1$ の数を数十個掛けると、アンダーフローして 0 になりうる	計算には対数確率を足し合わせる： $\log P = \sum \log P(w_i\mid\cdot)$ 。パープレキシティの計算でも、まず負の対数確率の平均を求める
c) 未出現の N-gram（ゼロ確率）	学習データにない n-gram はカウントが 0 → 文全体の確率も 0 になる	平滑化（Smoothing）。第 4 節を参照

4. 平滑化（Smoothing）

目的：未出現の n-gram にも非ゼロの確率を割り当てつつ、確率の和を 1 に保つ（確率質量の保存）。

4.1 Add-one（Laplace）平滑化

基本的な考え方：すべての n-gram が少なくとも 1 回は現れたと仮定し、すべてのカウントに $+1$ を加える。

P_{\text{add1}}(w_i) = \frac{C(w_i) + 1}{M + \vert V\vert } \qquad\text{(unigram)}

P_{\text{add1}}(w_i \mid w_{i-1}) = \frac{C(w_{i-1} w_i) + 1}{C(w_{i-1}) + \vert V\vert } \qquad\text{(bigram)}

分母に $\vert V\vert$ を加えるのは、確率の和を 1 に保つため（ $\vert V\vert$ 個の候補それぞれに 1 回分を加えたため）。

問題： $+1$ は低頻度語や疎なコーパスには「多すぎる」。未出現の事象に大量の確率質量を配り、既出の n-gram の確率を大きく下げてしまうため、歪みが大きい。

4.2 Add-k（Lidstone）平滑化

P_{\text{add-}k}(w_i \mid w_{i-2}, w_{i-1}) = \frac{C(w_{i-2}, w_{i-1}, w_i) + k}{C(w_{i-2}, w_{i-1}) + k\,\vert V\vert }

$k$ は人が選ぶ必要があるハイパーパラメータ。 $0<k<1$ は通常 $k=1$ より良い結果になる。最適な $k$ は検証データで実験して決める。
限界：
1. ハイパーパラメータ $k$ を選ぶ必要があり、 $k$ の値によって平滑化の効果が大きく異なる。
2. 同じ文脈では、未出現のすべての n-gram に同じ確率を割り当てる。ゼロカウント同士を区別せず、「ありそうだが未出現」と「ほぼありえない」を分けられない。
3. 元のカウント間の比率が変わる。

4.3 Absolute Discounting（絶対ディスカウント法）

考え方：既出の各単語のカウントから固定量 $d$ （例えば $d=0.1$ ）を「借り」、その確率質量を未出現の単語に配る。

P_{\text{abs}}(w_i \mid w_{i-1}) = \frac{C(w_{i-1}, w_i) - d}{C(w_{i-1})}, \quad \text{ただし } C(w_{i-1},w_i) > 0

例（context = alleged、既出の bigram が 5 個、未出現の bigram が 2 個）

単語	counts	平滑化前の確率	Add-α (α=0.1) の有効カウント	Add-α の平滑化後の確率	Discounting (d=0.1) の有効カウント	Discounting の平滑化後の確率
impropriety	8	0.4	7.826	0.391	7.9	0.395
offense	5	0.25	4.928	0.246	4.9	0.245
damage	4	0.2	3.961	0.198	3.9	0.195
deficiencies	2	0.1	2.029	0.101	1.9	0.095
outbreak	1	0.05	1.063	0.053	0.9	0.045
infirmity	0	0	0.097	0.005	0.25	0.013
alleged	0	0	0.097	0.005	0.25	0.013
合計	20	1.0	20	1.0	20	1.0

ディスカウント後の既出語のカウントは $8-0.1=7.9$ 、 $5-0.1=4.9$ …となり、合計で $5\times0.1=0.5$ の有効カウントを「借りる」。対応する確率質量は $0.5/20=0.025$ 。
借りた $0.5$ の有効カウントを、未出現の 2 語に等分する： $0.5/2 = 0.25$ （有効カウント）。正規化後は $0.25/20=0.0125\approx0.013$ 。

4.4 Katz Backoff（バックオフ）

考え方：既出ならディスカウントした確率を使い、未出現なら lower-order model（低次モデル）に従って確保した確率質量を再配分する。

P_{\text{katz}}(w \mid h) = \begin{cases} \dfrac{C^*(h,w)}{C(h)}, & \text{if } C(h,w) > 0 \\[2mm] \alpha(h)\,P_{\text{lower}}(w), & \text{otherwise} \end{cases}

ここで $h=w_{i-1}$ は文脈、 $C^*(h,w)$ はディスカウント後のカウント。Katz では通常 Good–Turing に基づくディスカウントを使い、すべての既出カウントから同じ定数を引くわけではない。バックオフの重みは次のとおり。

\alpha(h)=\frac{1-\sum_{w:C(h,w)>0}C^*(h,w)/C(h)}{\sum_{w:C(h,w)=0}P_{\text{lower}}(w)}

分子は高次モデルが残した確率質量。分母は、現在の文脈で未出現の単語について低次確率を合計したもの。これにより最終的な分布を正規化する。

Katz の問題

バックオフでは低次モデルの生の確率だけを見るが、この確率だけでは、その単語が新しい文脈にどれだけ現れやすいかを表せない。
模式的な例：I can not see without my reading ______
- 直感的な答え：glasses（reading glasses：読書用の眼鏡）
- 仮に reading glasses と reading Kong がともに未出現で、コーパスでは King Kong が頻出すると仮定する。unigram だけを見ると、 $P(\text{Kong})$ が $P(\text{glasses})$ を上回り、Kong がほぼ常に King の後にしか現れなくても、誤って選ばれる可能性がある。
- 根本的な問題：unigram 確率が高いことは、reading の後に適していることを意味しない。Kneser–Ney は継続確率（continuation probability）でこれを修正する。

4.5 Kneser–Ney 平滑化

考え方：ディスカウントした質量を、生のカウントではなく多様性（versatility）、つまりその単語が何種類の異なる語の後に現れるかに応じて配分する。

多様性は低いが高頻度：Francisco が San の後にしか現れないなら、総頻度が高くても継続カウントは 1 にすぎない。未出現の文脈を補完するときに、単語頻度の高さだけで高確率を与えるべきではない。
多様性が高い：glasses は reading, sun, wine, beer, eye… の後に現れうる → 継続カウントが多く、バックオフ時にも選ばれやすくなるため、Katz の例の問題を修正できる。

式：補間型

以下は一般的な補間型 Kneser–Ney。低次分布は高次カウントがゼロの場合だけ使うのではなく、ディスカウント後の高次確率に加算する。

P_{KN}(w_i \mid w_{i-1}) = \frac{\max(C(w_{i-1},w_i)-D,0)}{C(w_{i-1})} +\lambda(w_{i-1})\,P_{\text{cont}}(w_i)

P_{\text{cont}}(w_i)= \frac{\vert\{u:C(u,w_i)>0\}\vert}{\vert\{(u,v):C(u,v)>0\}\vert},\qquad \lambda(h)=\frac{D\,\vert\{v:C(h,v)>0\}\vert}{C(h)}

分子：異なる先行語のうち、その後に $w_i$ が現れたものの数（ $w_i$ の「文脈タイプ数」）。
分母：全単語の文脈タイプ数の合計（正規化のため）。
$\lambda(h)$ ：文脈 $h$ でディスカウントした確率質量の合計。 $0<D<1$ なら、既出の各後続語が $D/C(h)$ ずつ寄与する。高次分布と低次分布を加えても、確率の和は 1 のまま。

4.6 Interpolation（補間）

考え方：どちらか一方にバックオフするのではなく、次数の異なる n-gram モデルを重み付きで混合する。重みはホールドアウトデータで調整・学習する。

P_{IN}(w_i \mid w_{i-1}, w_{i-2}) = \lambda_3 P_3(w_i \mid w_{i-2}, w_{i-1}) + \lambda_2 P_2(w_i \mid w_{i-1}) + \lambda_1 P_1(w_i)

\sum_k \lambda_k = 1, \qquad \lambda_k \ge 0

$\lambda$ はホールドアウトデータで学習する（EM またはグリッドサーチ）。勘で決めるわけではない。
利点：高次モデルの精密さを保ちつつ低次モデルで補えるため、通常は純粋なバックオフより良い。

4.7 平滑化手法の比較

手法	基本的な考え方	利点	限界
Add-1	すべてのカウントに +1	最も単純。非ゼロかつ正規化された確率になる	疎なデータには加算量が多すぎ、既出確率を大きく下げる
Add-k	すべてのカウントに +k	add-one より穏やか	ハイパーパラメータ $k$ の調整が必要。未出現語の確率はすべて同じ。元の比率が変わる
Absolute Discounting	既出カウントから一律に $d$ を引き、残りを未出現語に配る	単純で add-k より良い結果	低次文脈が持つ情報量を区別しない
Katz Backoff	未出現なら低次モデルにバックオフ	高次の精密さを保持	生の確率でバックオフし、文脈の多様性を無視する（reading Kong の問題）
Kneser-Ney	低次分布の継続確率でディスカウントした質量を配分	古典的な n-gram モデルの強力なベースライン	式が複雑で、2 種類のカウントが必要
Interpolation	異なる次数のモデルを重み付き混合	安定し、バックオフを上回ることが多い	ホールドアウトデータで調整する重みは $\lambda$

5. テキスト分類

5.1 タスクの定義

入力：文書 $d$ （通常は特徴ベクトル（vector of features）として表す）と、固定されたクラス集合 $C=\{c_1, c_2, \dots, c_k\}$ （カテゴリ値。連続値でも順序付きの値でもない）。
出力：予測クラス $\hat{c} \in C$ 。

5.2 応用

Topic classification：話題分類（経済／政治／スポーツ）
Sentiment analysis：感情分析
Native-language identification：母語識別（外国語で書かれた文章から書き手の母語を推定するなど）
Natural language inference：自然言語推論（含意／矛盾／中立）
Automatic fact-checking：自動ファクトチェック
Paraphrase：言い換え判定

5.3 標準的な流れ

Identify a task of interest —— タスクを決める
Collect an appropriate corpus —— 適切なコーパスを集める
Carry out annotation —— 人手でアノテーションする
Select features —— 特徴量を選ぶ（BoW、n-gram、TF-IDF、埋め込みなど）
Choose a machine learning algorithm —— モデルを選ぶ
Train model and tune hyper-parameters using held-out development data —— 開発データでハイパーパラメータを調整する
Repeat earlier steps as needed —— 必要に応じて前の手順を繰り返す
Train final model —— 最終モデルを学習する
Evaluate model on held-out test data —— テストデータで評価する

5.4 手法を選ぶ際の観点

観点	意味
Bias：バイアス	モデルの制約や単純化した仮定が生む系統的な誤差。仮定が実データと合わないと、大きなバイアスにつながる
Variance：分散	モデルが学習データにどれほど敏感か。敏感なほど、別の標本で学習した際の結果の変動が大きい（過学習しやすい）
前提となる仮定	特徴の独立性、線形境界、距離の意味など、モデルが依拠する条件。満たされない場合、性能に影響しうる
計算量	学習・推論の時間とメモリのコスト。大規模データに拡張できるか
速度	学習と予測の遅延が運用上の要件を満たすか

バイアスと分散のトレードオフ：高バイアスは適合不足、高分散は過学習に対応することが多い。二乗損失では、予測誤差の期待値はバイアスの二乗、分散、不可約なノイズに分解できる。分類でもこの枠組みを使ってモデルの取捨選択を考えられる。

5.5 代表的なアルゴリズムの比較

(1) Naïve Bayes

基本的な考え方：ベイズの定理を使い、事後確率が最大のクラスを選ぶ。

P(C\mid F) \propto P(F\mid C)\,P(C)

つまり「クラスの事前確率 × そのクラスの下でこれらの特徴が現れる確率」。

ナイーブな仮定：特徴同士は条件付き独立：

P(F \mid C) = \prod_{f \in F} P(f \mid C)

Pro：非常に高速。学習はカウントだけで済む。少量データや高次元の疎な特徴に強く、多クラス分類と逐次更新にも対応しやすい。
Con：単語間には強い相関があり、独立性の仮定はほぼ成立しない。確率の較正が悪く、0 や 1 に近い極端な値を出しやすい。ゼロ確率への平滑化も必要。

(2) Logistic Regression（ロジスティック回帰／最大エントロピー）

名前に regression とあるが、分類器である。
線形モデルであり、softmax で線形スコアを有効な確率に変換する。

P(y=c \mid x) = \frac{\exp(w_c^\top x + b_c)}{\sum_{c'} \exp(w_{c'}^\top x + b_{c'})}

学習目標：学習データの尤度を最大化する（交差エントロピーの最小化と同値）。さらに正則化を加え、小さい重みや疎な重みを促す。
Pro：確率出力を解釈でき、学習が速い。L1/L2 正則化を特徴選択に利用でき、線形モデルは大規模コーパスにも適用しやすい。
Con：学習できるのは線形の決定境界だけで、非線形性には手作業の交差特徴などが必要。特徴量のスケールに敏感。極端なクラス不均衡には重みの調整が必要。

(3) Support Vector Machine (SVM)

定義：学習データを分離し、マージンが最大となる超平面を見つける。

\min_{w,b}\ \tfrac{1}{2}\Vert w\Vert ^2 \quad \text{s.t.}\quad y_i(w^\top x_i + b) \ge 1

Pro：高次元で疎なテキストに強く、テキスト分類の古典的な強力なベースライン。最大マージンによる汎化性能が期待でき、カーネルで非線形性にも対応できる。
Con：基本は二値分類で、多クラスには one-vs-rest などが必要。カーネル SVM は大標本で学習コストが高く、較正された確率を直接出力しない。ただし線形 SVM には効率的な最適化法があり、計算量を一括りにはできない。

(4) K-Nearest Neighbour (KNN)

定義：特徴空間で最も近い $k$ 個の学習例を探し、その多数派クラスで分類する。
「近さ」の定義は選べる：ユークリッド距離、コサイン距離（長さではなく方向を見るため、テキストでよく使う）。
Pro：学習処理が不要（遅延学習）。多クラスに自然に対応し、決定境界は強い非線形性を持てる。実装も容易。
Con：予測時に全例との距離を計算するため、推論が遅く、メモリを多く使う。特徴量のスケールと距離尺度に非常に敏感。高次元では距離が有効に働きにくい（次元の呪い）。クラス不均衡では多数派が有利。

(5) Decision Tree

定義：内部ノードで単一の特徴を検査し、葉で最終クラスを返す木を作る。情報利得や Gini 不純度などの基準で貪欲に分割を選ぶ。
Pro：規則を読み取れて解釈しやすい。特徴量のスケーリングが不要。非線形性や特徴間の相互作用を扱え、学習も速い。
Con：過学習しやすく、枝刈りや深さ制限が必要。貪欲な分割は局所最適にすぎない。データの変動に不安定（高分散）で、値の種類が多い特徴を優先しやすい。

(6) Random Forest

定義：アンサンブル分類器。複数の決定木を、異なる学習部分集合（ブートストラップ標本）と異なる特徴部分集合で学習し、最終結果を多数決で決める。
Pro：分散を大きく減らし、過学習を抑える。一般にノイズに比較的頑健で、特徴重要度も得られる。ただし木の深さや葉の大きさなどはタスクに応じて調整する必要があり、欠損値への対応は実装による。
Con：単一の木ほど解釈しやすくない。モデルが大きく、推論も単一の木より遅い。高次元で疎なテキストでは線形モデルほど効率的でない。

(7) Neural Network

定義：相互接続されたノードの集合。通常は入力層（特徴）、出力層（クラス確率）、複数の隠れ層に分かれる。各ノードは前の層の入力を線形に重み付けし、活性化関数を通して次の層に渡す。
Pro：特徴表現を自動で学べ、表現力が高い。end-to-end 学習が可能で、大規模データや事前学習にも拡張できる。
Con：多量のデータと計算資源が必要。ハイパーパラメータが多く、解釈が難しい。過学習への正則化や dropout が必要で、少量データでは線形モデルを上回るとは限らない。

5.6 ハイパーパラメータの調整と評価

Hold-out（ホールドアウト法）：データを train / dev（validation）/ test に分割する。ハイパーパラメータは dev で選び、test は最終結果を報告する際に一度だけ使う。

混同行列（二値分類の例）

	Classified As A	Classified As B
True A	79 (TP)	13 (FN)
True B	8 (FP)	10 (TN)

評価指標の計算

Accuracy：正解率

\text{Accuracy} = \frac{TP + TN}{N} = \frac{79+10}{110} = 0.809

Precision：適合率：陽性と予測したもののうち、実際に陽性である割合

P = \frac{TP}{TP + FP} = \frac{79}{79+8} = 0.908

Recall：再現率：実際の陽性のうち、検出できた割合

R = \frac{TP}{TP + FN} = \frac{79}{79+13} = 0.859

F1-Score：適合率と再現率の調和平均

F_1 = \frac{2PR}{P+R} = \frac{2 \times 0.908 \times 0.859}{0.908 + 0.859} = 0.883

なぜ算術平均ではなく調和平均を使うのか？調和平均は小さい方の値に引き下げられる。P と R の両方が高い場合にだけ F1 も高くなり、再現率だけ高く適合率が低い場合や、その逆の場合が高得点になるのを防げる。

多クラス分類の指標

指標	方法	特徴
Macro-average	クラスごとに P/R/F1 を計算し、その後クラス間で算術平均を取る	各クラスの重みが等しい。少数クラスの影響が相対的に大きく、ロングテールの性能低下を見つけやすい
Micro-average	全クラスの TP/FP/FN を合算してから P/R/F1 を一度計算する	各サンプルの重みが等しく、大きなクラスが支配的。単一ラベルの多クラス分類では micro-F1 = accuracy

6. 品詞タグ付け（POS Tagging）

6.1 POS とは

定義：文中の各単語に文法カテゴリ（品詞）を付与すること。

例：Janet/NNP will/MD back/VB the/DT bill/NN

この文の back は動詞（支持する）であり、名詞や副詞ではない。品詞は文脈で決まる。

応用：

Constituency parsing（句構造解析）の前処理：品詞情報を使って句構造を組み立てる。
Information extraction（情報抽出）の前処理：実体や関係の特定に品詞を利用する（NN/NNP の句だけを抽出するなど）。
特徴としての利用：NER、感情分析、翻訳などに言語学的特徴を与える。
音声合成（発音・強勢の決定）、辞書編纂、文章校正。

6.2 品詞の分類

開いたクラス（Open class）：新語が加わり、古い語が使われなくなることがある

大分類	下位分類
Nouns：名詞	Proper：固有名詞（Melbourne）／Common：普通名詞。普通名詞はさらに Mass：不可算名詞（water）／Count：可算名詞（chair）に分かれる
Lexical verbs：語彙動詞	屈折形が豊富（sing/sang/sung）。用法により他動詞と自動詞に分かれる
Adjectives：形容詞	Gradable：段階性がある（very tall）／Non-gradable：段階性がない（dead）
Adverbs：副詞	Locative：場所（here, there）／Degree：程度（very, extremely）

閉じたクラス（Closed class）：比較的固定され、語が増減しにくい

Preposition：前置詞（of, in, on）
Particles：小辞（up, off。例：give up）
Determiners：限定詞（the, a, this）
Pronouns：代名詞（he, they, who）
Conjunctions：接続詞（and, but, because）
Auxiliary / Modal Verbs：助動詞・法助動詞（be, have, do, can, must, should。具体的な分類はタグ体系による）

6.3 課題：曖昧性（Ambiguity）

同じ語形が複数の品詞に対応し、その分布も非常に偏っている。

back：名詞（背中）／動詞（支持する）／副詞（後ろへ）／形容詞
flies：名詞の複数形（ハエ）／動詞の三人称単数形（飛ぶ）
like：前置詞（〜のように）／動詞（好む）

単純なベースラインは、各単語に学習データで最も多い品詞を付ける方法。この偏りは利用できるが、現在の文脈による曖昧性解消はできない。正解率はコーパスと未知語の扱いに依存する。

6.4 POS Tagsets：品詞タグ集合

タグ集合	タグ数	特徴
Brown	87	初期のコーパスタグ集合の一つで、細かい分類
Penn Treebank (PTB)	45	NLP で最も広く使われるタグ集合。例：NN, NNS, NNP, VB, VBD, VBG, JJ, RB, IN, DT, MD, CC, PRP…
CLAWS5 / BNC	61	CLAWS の一つの版。タグ数は版によって異なる
初期の Universal Tagset	12	NOUN, VERB, ADJ, ADV, PRON, DET, ADP, NUM, CONJ, PRT, ., X。Universal Dependencies の 17 分類の UPOS と混同しないこと

古典的な曖昧性の例（Penn Treebank のタグ）

TEXT

Time  flies like an arrow
Time/NN  flies/VBZ  like/IN  an/DT  arrow/NN

Fruit flies like a banana
Fruit/NN  flies/NNS  like/VBP  a/DT  banana/NN

同じ flies でも、1 文目では動詞（時が飛ぶように過ぎる）、2 文目では名詞（ショウジョウバエ）。文脈を見なければ判断できない。

7. 隠れマルコフモデル（HMM）

7.1 なぜ HMM が必要なのか

タスク：POS tagging。単語列 $W = w_1 \dots w_n$ 全体に対して最適なタグ列 $T = t_1 \dots t_n$ を求める。

既存手法の問題：各単語を独立に予測するとタグ間の依存関係を利用できない。直前までの予測タグに依存する貪欲な分類器では、先行する誤りが後続の予測に影響する誤り伝播が起こりうる。

新しい考え方：文全体をモデルに渡し、タグ列全体を出力させる。

新たな問題：文の長さは一定でなく、可能なタグの組合せ数は $\vert T\vert ^n$ 、指数的で、全列挙はできない。

解決策：単語単位でモデル化しながら、学習と予測では文全体を一つの単位として扱う。これを sequence labelling、または structured prediction と呼ぶ。

HMM の動作：文（単語列）を与え、すべての候補タグ列の中から確率が最大のものを見つける。

利点：

手作業の規則設計が不要（データ駆動）
単語ごとの貪欲な選択ではなく、大域的に最適なタグ列を考える
アノテーション済みコーパスからパラメータを学べる（data-informed）

7.2 式

\hat{T} = \arg\max_{T} P(T \mid W) = \arg\max_{T} \frac{P(W \mid T)\,P(T)}{P(W)} = \arg\max_{T} P(W \mid T)\,P(T)

（ $P(W)$ は $T$ に依存しないため無視できる。これはベイズの定理を使って分母を取り除く操作）

図 7-1　HMM の確率的グラフィカルモデル。実線は状態遷移 $P(t_i\mid t_{i-1})$ （行列 A）、破線は出力 $P(w_i\mid t_i)$ （行列 O）を表す。

7.3 2 つの仮定

仮定	内容	役割
Output independence（出力の独立性）	位置 $i$ の単語は、位置 $i$ のタグだけに依存し、他の単語やタグには依存しない： $P(W\mid T)=\prod_i P(w_i\mid t_i)$	タグ列を条件とする文全体の確率を、単語ごとの確率の積に分解する
Markov assumption（マルコフ仮定）	現在のタグは直前のタグだけに依存する： $P(T)=\prod_i P(t_i \mid t_{i-1})$	タグ列の確率を、1 次の遷移確率の積に分解する

したがって、

\hat{T} = \arg\max_{T} \prod_{i=1}^{n} \underbrace{P(w_i \mid t_i)}_{\text{emission}} \cdot \underbrace{P(t_i \mid t_{i-1})}_{\text{transition}}

HMM が生成モデルである理由もここにある。同時確率 $P(W,T) = P(T)P(W\mid T)$ をモデル化している。

7.4 学習：2 つの確率表を求める

パラメータ	名称	意味
$P(w_i \mid t_i)$	Emission（出力・観測）確率 O	あるタグがある単語を生成する確率
$P(t_i \mid t_{i-1})$	Transition（遷移）確率 A	直前のタグの後に、あるタグが続く確率

推定方法：ここでも最尤推定（MLE）、つまりカウントを使う。

P(w_i \mid t_i) = \frac{\text{Count}(w_i, t_i)}{\text{Count}(t_i)}, \qquad P(t_i \mid t_{i-1}) = \frac{\text{Count}(t_{i-1}, t_i)}{\text{Count}(t_{i-1})}

最初のタグの確率はどうするか？各文の前に特別な開始記号 <s> を置くと、最初の項は $P(t_1 \mid \text{<s>})$ ：

P(t_1 \mid \text{<s>}) = \frac{\text{Count}(\text{<s>}, t_1)}{\text{Count}(\text{<s>})}

同様に文末に </s> を置き、 $P(\text{</s>} \mid t_n)$ も学習可能な遷移にする。前述の積では簡潔さのためこの文末因子を省いたが、完全な経路確率にはこの因子も掛ける。

未知語はどうするか？ここでも平滑化（第 4 節）を使う。出力確率表に add-k / add-one を適用するか、低頻度語を <UNK> にまとめ、<UNK> の出力確率を低頻度語全体で共有する。

7.5 予測

学習済み HMM（2 つの表：遷移行列 A と出力確率行列 O）から、入力文のタグ列を予測する。

基本的な考え方：すべてのタグの組合せから、同時確率が最大のものを選ぶ。

\hat{t} = \arg\max_{t} P(W \mid t)\,P(t) = \arg\max_{t} \prod_{i=1}^{n} P(w_i \mid t_i)\,P(t_i \mid t_{i-1})

なぜ 1 語ずつ予測しないのか？（貪欲復号の限界）

単語ごとに argmax を取る方法は局所最適にすぎない。現在の単語に最適なタグが、次の単語に最適なタグを非常に低確率にしてしまう場合がある。
文全体の最適化は大域的な問題であり、前後の選択を同時に考慮する必要がある。
ただし $\vert T\vert ^n$ 個の列挙は非現実的 → Viterbi の動的計画法で大域最適解を求める。タグ集合の大きさが固定なら、実行時間は文長に対して線形に増える。

7.6 生成モデルと識別モデル

観点	Generative（HMM）	Discriminative（CRF／分類器）
モデル化するもの	同時確率 $P(X, Y)$	条件付き確率 $P(Y \mid X)$ （または $P(T\mid W)$ ）
主な用途	言語の生成が可能。HMM は教師なし学習にも対応	分類、予測、系列ラベリング
学習方式	通常は教師あり・半教師あり。EM による教師なし学習も可能	通常は教師あり学習
特徴	観測自体の出力確率を用いるため、特徴に制約がある	接頭辞・接尾辞、語形、文脈語、外部辞書など豊富な特徴を使える
データ量	単純な構造の仮定は、少量データでの学習に有利な場合がある	データと特徴が十分なら予測性能が高い傾向があるが、タスクとモデルに依存する
代表例	Naïve Bayes、HMM。ニューラル言語モデルも生成的にモデル化できる	ロジスティック回帰、CRF、SVM、分類用ニューラルネットワーク

識別モデルは「入力が与えられたときの出力の予測」を直接最適化し、入力分布 $P(W)$ を明示的にモデル化する必要がない。予測タスクに集中できるが、どちらが良いかはタスク・データ・モデルによる。

8. Viterbi アルゴリズム

8.1 基本的な考え方

「現在の単語の最良タグ」だけでなく、「各候補タグで終わる最良経路のスコア」を保持し、次の単語へ進む際にすべての組合せを考える。

各位置 $t$ と各タグ $j$ について、タグ $j$ で終わる最適経路の累積スコア $\delta_t(j)$ とバックポインタ $\psi_t(j)$ を記録する。

8.2 漸化式

\delta_1(j) = P(t_1 = j \mid \text{<s>}) \cdot P(w_1 \mid j)

\delta_t(j) = \max_{i \in T}\Big[\delta_{t-1}(i)\cdot P(j \mid i)\Big]\cdot P(w_t \mid j)

\psi_t(j) = \arg\max_{i \in T}\Big[\delta_{t-1}(i)\cdot P(j\mid i)\Big]

終了処理：

\hat{t}_n = \arg\max_{j}\big[\delta_n(j)\,P(\text{</s>}\mid j)\big], \qquad \hat{t}_{t} = \psi_{t+1}(\hat{t}_{t+1}) \ \text{（バックトラック）}

明示的な文末状態がないモデルでは、終了時に $\delta_n(j)$ を直接比較すればよい。以下の 2 例はいずれもこの簡略化を使う。

直感的な例：Can Play

単語 can について、MD（法助動詞）と NN（名詞）のスコアをそれぞれ記録する。
次の単語 play を処理するとき、各候補タグ（VB、NN）：
- 「can の各タグのスコア × 遷移確率 × 出力確率」を組み合わせる。
- 経路全体の確率が最大のものを探す。
最後に各終端タグの累積スコアを比較し、最大のものから逆向きにたどって経路全体を復元する。

8.3 例 1：Janet will back the bill

遷移行列（一部抜粋。行が条件となる事象 $P(\cdot\mid \text{row})$ ）

	NNP	MD	VB	JJ	NN	RB	DT
<s>	0.2767	0.0006	0.0031	0.0453	0.0449	0.0510	0.2026
NNP	0.3777	0.0110	0.0009	0.0084	0.0584	0.0090	0.0025
MD	0.0008	0.0002	0.7968	0.0005	0.0008	0.1698	0.0041
VB	0.0322	0.0005	0.0050	0.0837	0.0615	0.0514	0.2231
JJ	0.0366	0.0004	0.0001	0.0733	0.4509	0.0036	0.0036
NN	0.0096	0.0176	0.0014	0.0086	0.1216	0.0177	0.0068
RB	0.0068	0.0102	0.1011	0.1012	0.0120	0.0728	0.0479
DT	0.1147	0.0021	0.0002	0.2157	0.4744	0.0102	0.0017

（データは Jurafsky と Martin の Speech and Language Processing 第 18 章 Figure 18.12 による。WSJ コーパスに基づき、平滑化はしていない。タグの一部だけを示しているため、各行の和は 1 とは限らない。正規化されるのは完全な遷移分布。）

出力確率行列（Emission Matrix、Speech and Language Processing、Figure 18.13）

	Janet	will	back	the	bill
NNP	0.000032	0	0	0.000048	0
MD	0	0.308431	0	0	0
VB	0	0.000028	0.000672	0	0.000028
JJ	0	0	0.000340	0	0
NN	0	0.000200	0.000223	0	0.002337
RB	0	0	0.010446	0	0
DT	0	0	0	0.506099	0

手順： $\vert T\vert \times n$ のトレリスを作り、列ごとに $\delta$ を埋める。各セルには「前の列のどのタグから来たか」を記録し、最終列の最大値から逆向きにたどる。

8.4 例 2：they fish（手計算で確認できる）

これは動的計画法を示すためだけの 2 状態のトイモデルで、数値は人工的に設定したもの。N と V は状態ラベルであり、実際の英語で they が動詞になることを意味しない。

出力確率

	they	fish
N	0.7	0.3
V	0.4	0.6

遷移確率

	N	V
<s>	0.6	0.4
N	0.8	0.2
V	0.7	0.3

図 8-1　they fish の Viterbi トレリス。各セルには「そのタグで終わる最良接頭経路のスコア」 $\delta$ だけを残す。赤は逆向きにたどって得た最適経路 they/N → fish/N を示す。

全 4 経路の列挙

経路	計算	確率
N N	$0.6\times0.7 \times 0.8\times0.3$	0.1008 ✅ 最適
N V	$0.6\times0.7 \times 0.2\times0.6$	0.0504
V N	$0.4\times0.4 \times 0.7\times0.3$	0.0336
V V	$0.4\times0.4 \times 0.3\times0.6$	0.0288

結果：they/N fish/N。fish の出力確率だけを見ると、 $P(\text{fish}\mid V)=0.6$ が $P(\text{fish}\mid N)=0.3$ より大きい。しかし遷移確率を加えると、最適経路は N で終わる。出力確率はタグの事後確率ではなく、それだけでタグは選べない。この例は遷移情報の役割を示すが、遷移も逐次考慮する貪欲復号が必ず失敗することを示す例ではない。

8.5 アルゴリズムの性質

性質	説明
時間計算量	$O(T^2 N)$ ： $T$ = タグ集合の大きさ、 $N$ = 系列長。位置は全部で $N$ 個あり、各位置の $T$ 種類のタグそれぞれについて、前の位置の全 $T$ タグと比較する
空間計算量	最適スコアだけなら 2 列を交互に保持でき、必要な空間は $O(T)$ 。経路全体の復元には $O(TN)$ 個のバックポインタを保存する
正しく解ける理由	最適部分構造：位置 $t$ のタグ $j$ に至る最適経路の接頭部分は、位置 $t-1$ のいずれかのタグに至る最適経路でなければならない（そうでなければ接頭部分を置き換えて改善できる）。マルコフ性：現在のタグが与えられれば、未来はそれ以前の履歴に依存しない。各セルで最良の接頭経路スコアだけを残し、劣る経路を安全に捨てられる
数値アンダーフロー	確率を掛け続けるとすぐに 0 になる。実装ではすべて対数確率を使う（乗算が加算になり、 $O(T^2N)$ は変わらない）
高次の変種	例えばタグの trigram（2 次 HMM）： $P(t_i \mid t_{i-2}, t_{i-1})$ と、interpolation による平滑化を使う。計算量は $O(T^3 N)$