Tamflexの貯蔵庫

やる気のない備忘録

形態素解析 memo

自然言語とは

形態素解析について

形態素解析 = 単語分割 + 系列ラベリング
  • 私は猫が好きだ

  ↓単語分割

  • 私/は/猫/が/好きだ

  ↓系列ラベリング

  • 私[名詞]/は[助詞]/猫[名詞]/が[助詞]/好きだ[形容動詞]

統計的アプローチ

隠れマルコフモデル(Hidden Markov Model, HMM)

 S:隠れ状態の有限集合
   \{1,2,\dots k\}
 \Sigma:出力記号集合
  e.g., \{A,B,C\dots\}
 \pi_k:文頭が状態kになる確率(初期値の確率)
 a_{t,k}:状態tから状態kへの遷移確率
  i.e., \sum_{k\in S}a_{t,k}=1
 a_{k,o}:状態kにおける記号oの出力確率
  i.e., \sum_{o\in \Sigma}b_{k,o}=1

隠れマルコフモデル - Wikipedia
http://www.iba.t.u-tokyo.ac.jp/~iba/SE/HMM/HMM.pdf

e.g.
 S = \{名詞,動詞,形容詞,冠詞,前置詞 \}
 \Sigma = \{"time","like","arrow",\dots\}

HMMによる品詞タグ付けの探索問題

観測系列 o_{1:T}と状態系列 s_{1:T}の同時確率分布は

 P(o_{1:T},s_{1:T})=P(s_1)\prod_{t=1}^{T}P(s_{T+1}|s_t)P(o_t|s_t)

解きたい問題: \max_{s_{1:T}}P(o_{1:T},s_{1:T})

ビタビ(Viterbi)アルゴリズム

動的計画法O(KT^2)の一種
 t+1までの観測系列 o_{1:t+1}において、 s_{t+1}=kに至る状態系列の最大確率を

 q_{t+1}(k)=\max_{s_{1:T}}P(o_{1:T},s_{1:T})
とすると以下のように再帰的にかける
 q_{t+1}(k)=\max_i[q_t(i)a_{i,k}]b_k(o_{t+1})

1. 各状態 k=1,2,\dots Kに対して初期化:

 q_1(k)=\pi_k b_k(o_1), \xi_i(k)=0

2.  t=1,2,\dots T,k=1,2,\dots Kに対する再帰計算:

 q_{t+1}(k)=max_i[q_t(i)a_{i,k}b_k(o_{t+1}]

 \xi_{t+1}(k)=argmax_i [q_t(i)a_{i,k}]

3. 再帰計算終了時の確率を計算

 q^{\ast}=max_k q_T(k) (q_T(k)=\max_{s_{1:T-1}}P(o_{1:T},s_T=k, s_{1:T-1}))

 s_T^{\ast}=argmax_k q_T(k)

4. バックトラック:

 s_t^{\ast}=\xi_{t+1}(s_{t+1}^{\ast})

HMMによる品詞タグ付け

  • 品詞タグ付けコーパスを用意する
  •  \pi,a,bからコーパスを推定する
  •  \pi,a,bから確率が最も高くなる品詞タグを推定する