添付ファイル '15�m�_�V�X�e���_�m�[�g�i��11��j.html'

ダウンロード

1/5知能システム論ノート（第11回）

  • 隠れマルコフモデル（メイン）
    • 系列ラべリング
      • 入力：文字列（単語列）、出力：ラベル
        • 前回の機械学習よりちょっと複雑
      • 系列構造をもった問題に適用される
        • 音声
        • 品詞タグ付け
        • かな漢字変換
        • 動画認識
          • John[N] bought[V] a[冠詞] book[N]
    • 隠れマルコフモデル(HMM)
      • 状態遷移を表す確率モデル
      • 状態を移動しながら、各状態から記号を出力する
        • 状態列：s = s1, ・・・, sn
        • 記号列：w = w1, ・・・, wn
          • 名詞　動詞　　冠詞　名詞　（状態列s）
          • John  bought  a 　　book　（記号列w）
      • 非決定性有限状態オートマトンに確率がついたものだと考えられる。
      • 遷移確率：状態を移動する確率
      • 出力確率：記号を出力する確率
      • 単語列w, 品詞列sの同時確率
        • p(w, s) = Π{t = 1 to n} (PT(s[t] | s[t-1]) * PE(w[t] | s[t]))
        • PT(s[t] | s[t-1]) : 遷移確率
        • PE(w[t] | s[t]) : 出力確率
        • いろいろ独立性が仮定されている
        • 現在の品詞が来る確率は直前の品詞にのみ依存し、現在の単語は現在の品詞にのみ依存すると仮定
        • s[0]は別途定義する
      • 定式化
        • 隠れマルコフモデルM=<Q, Σ, q0, pT, pE>
          • Q:状態集合
          • Σ:記号の集合
          • q0:初期状態
          • pT(a|b):状態bから状態aに遷移する確率
          • pE(o|a):状態aから記号oを出力する確率
        • 状態・記号列の確率
          • p(w, s) = Π{t = 1 to n} (pT(s[t] | s[t-1]) * pE(w[t] | s[t]))
      • HMMの諸問題
        • HMMをどうやって系列ラべリングに適用するのか？
        • HMMのパラメータはどうやって学習するのか？
    • HMMを用いたラべリング
      • 単語列wが与えられたとき、確率最大の状態列ｓを求める
        • s^ = argmax{s} p(s|w) = argmax{s} p(s,w)/p(w) ∝ argmax{s} p(s,w) = argmax{s} Π{t = 1 to n} pT(s[t]|s[t-1])pE(w[t]|s[t])
      • すべての状態列を列挙し、確率最大の状態列ｓを出力すればよい＝＞が、難しい（計算量的に）
      • 指数爆発
        • 状態列sの数は、単語数に対して指数爆発してしまう。
        • 品詞が10個だと20単語だと10^20 = 1がい
      • 動的計画法で解く
        • 指数爆発しないように確率値や状態列を計算
        • ビタビアルゴリズム：確率最大の状態列を求める動的計画法

  • ビタビ(Viterbi)アルゴリズム
    • トレリス
      • 状態を縦に並べ遷移可能な状態の間を結ぶ
      • トレリス上の遷移系列＝状態列
      • 画像はググれ（http://t3.gstatic.com/images?q=tbn:ANd9GcTvLspLQE5mqtZiv7nTdfOpa05LBn8nAEXHSEY0vRrzj35gmqnqOA）
      • まずはp(w, s)の最大値を求める問題を考える
      • 左から順番に、各状態までの確率の最大値を計算する
      • i単語目の品詞がtになる品詞列s[1], ・・・, s[i]の確率の最大値を考える
        • δ[i](t) = max{s[1], ・・・s[i-1]} p(w[1]・・・w[i], s[1]・・・s[t-1]s[i]=t)(s[i]がｔとなるような品詞列)
          •  = max (p(w[i]|s[i]=t) p(s[t]=t|s[i-1]) p(w[1]・・・w[i-1], s[1] ・・・s[i-1]))
          •  = p(w[i]|s[i]=t) max (s[i-1]p(s[i]=t|s[i-1])δ[i-1](s[i-1]))
      • for i = 1 to n
        • for t = t1 to tk（品詞）
          • δ[i](t) = p(w[i]|s[i]=t) max{s[i-1]} p(s[i] = t| s[i-1]) δ[i-1](s[i-1])
      • 計算量 = n * k^2　(単語数 * 品詞数^2)
  • 教師あり学習・教師なし学習
    • パラメータの学習
      • どうやって遷移確率・出力確率を決めるのか
      • 教師あり学習：正解つきのデータから確率を学習する
      • 教師なし学習：正解なしデータ（ただの記号列）から確率を学習する。
    • 教師あり学習
      • タグ付きコーパス：人手で正解を付与したデータ
      • 教師あり学習＝品詞タグ付きコーパスから最尤推定（C：Count？）
        • 遷移確率：品詞の並び<t, s>を数える
          • pT(t|s) = C(t,s)/C(s)
        • 推移確率：単語と品詞のペア<w, s>を数える
          • pE(w|s) = C(w,s)/C(s)
      • スムージングしないといけない？
    • 教師なし学習
      • タグなしコーパス（唯のテキストデータ）ｋらパラメータを学習
      • タグなしコーパスは最優推定法では無理
  • EMアルゴリズム
    • Expectation-Maximizationアルゴリズム
    • 不完全データから確率を推定する手法
    • アルゴリズム
      • パラメータをランダムに初期化
      • Eステップ：現在のパラメータで期待値を計算
      • Mステップ：期待値を使ってパラメータを更新
      • 収束するまでE・Mステップを繰りかえす
    • Eステップ
      • 各遷移の・各出力の期待値を計算
      • E[s[t-1]=ρ, s[t]=τ] = Σ{w, s}p(w, s) = Σp(w[1]・・・w[n], s1・・・s[t-2]ρτs[t+1]・・・s[n])
      • E[s[t]=τ, s[t]=ω] = Σ{w, s when s[t] = τ, w[t] = ω}p(w, s)
      • = Σp(w[1], ・w[t-1]ωw[t+1]・・w[n], s1 ・・・s[t-1]τs[t+1]・・・s[n])
      • その期待値を使ってパラメータを計算
        • pT(s'|s) = E[s',s]/E[s]
        • pE(w|s) = E[w,s]/E[s]
    • 期待値の計算
      • 遷移・出力の期待値をどうやって計算する・
    • 状態を満たすすべての状態列を列挙すると、指数爆発する
    • Baum-Welchアルゴリズム
      • 前向き・後ろ向きアルゴリズム：前向き・後ろ向き確率を効率的に計算する動的計画法
      • Baum-Welchアルゴリズム：前向き・後ろ向き確率を使ったEMアルゴリズム
  • 前向き・後向き確率
    • 前向き確率
      • s[t] = τとなるすべての状態列s[1]、・・・、s[t]の確率の和
        • φ[t](τ) = Σp(w[1]・・・w[t], s[1]・・・s[t-1]τ)
          •  = Σp(w[t]|τ)p(τ|s[t-1])p(w[1]・・・w[t-1], s[1]・・・s[t-1])
          •  = p(w[t]|τ) Σp(τ|s[t-1])φ[t-1](s[t-1])
    • 後ろ向き確率
      • s[t] = τとなるすべての状態列s[ｔ]、・・・、s[ｎ]の確率の和
        • ψ[t](τ) = ・・・ = p(w[t]|τ) Σp(s[t+1]|τ)ψ[t+1](s[t+1])
    • 期待値の計算
      • E[s[t-1]=ρ, s[t]=τ] = Σp(w[1]・・・w[n], s[1]・・・s[t-2]ρτs[t+1]・・s[n])=φ[t-1](ρ)pE(w[t]|τ)ψ[t](τ）　＜＝なんか違うらしい
    • 動的計画法のポイント
      • 分配法則によって積の和を和の積にする
        • X1A + X2A + X3A = (X1 + X2 + X3)A
        • X1AY1 + X2AY1 + X3AY1 + X1AY2 + X2AY2 + X3AY2 + X1AY3 + X2AY3 + X3AY3 = (X1 + X2 + X3)A(Y1 + Y2 + Y3)
    • 確率モデルや線形分類器で使われる動的計画法は、ほとんどこの形
  • EMアルゴリズムの特徴
    • パラメータ更新ごとに尤度が上がる
    • 目的関数は突ではない
      • 局所最適値がある（最適とは限らない）
      • EMの収束値は初期値に依存する
  • ビタビアルゴリズムと前向き・後ろ向きアルゴリズムの関係
    • これらのアルゴリズムはほとんど同じ
      • ビタビ：積の最大値
        • δ[t](τ) = p(w[t]|τ)max{s[t-1]}p(τ|s[t-1])δ[t - 1](s[t-1])
      • 前向き・後ろ向き：積の和
        • φ[t](τ) = p(w[t]|τ)Σ{s[t-1]}p(τ|s[t-1])φ[t - 1](s[t-1])
    • 両方とも分配法則を利用している
      • max(AX, AY) = A max(X, Y)
      • sum(AX, AY) = A sum(X, Y)

          




















添付ファイル

添付ファイルを参照するには、(下のファイル一覧にあるように)attachment:filenameと記述します。 [get]リンクのURLは変更される可能性が高いので、利用しないでください。

ファイルを添付する権限がありません。