\begin{align} \newcommand{\cS}{\mathcal{S}} \newcommand{\bt}{\mathbf{t}} \newcommand{\bx}{\mathbf{x}} \newcommand{\by}{\mathbf{y}} \newcommand{\bw}{\mathbf{w}} \newcommand{\bQ}{\mathbf{Q}} \newcommand{\b}[1]{\mathbf{#1}} \newcommand{\bo}[1]{\boldsymbol{#1}} \newcommand{\old}{\mathrm{old}} \newcommand{\new}{\mathrm{new}} \newcommand{\bphi}{\boldsymbol{\phi}} \newcommand{\balpha}{\boldsymbol{\alpha}} \newcommand{\bbeta}{\boldsymbol{\beta}} \newcommand{\bgamma}{\boldsymbol{\gamma}} \newcommand{\bxi}{\boldsymbol{\xi}} \newcommand{\bSigma}{\boldsymbol{\Sigma}} \nonumber \end{align}

Baum-Welchアルゴリズム

条件付き独立性

Baum-Welchアルゴリズムの導出過程で必要となる条件付き独立性の式を示す．ここではPRMLの1つ目の条件付き独立性のみ示しておく．

fig1

$\b{x}_{1:n}$から$\b{x}_{n + 1:N}$への経路は$\b{z}_{n}$によって遮断されている．よって条件付き独立性により$p(\b{x}_{1:N} | \b{z}_n) = p(\b{x}_{1:n} | \b{z}_n) p(\b{x}_{n + 1:N} | \b{z}_n)$が成り立つ．

他の条件付き独立性は以下の通り．

  • $p(\b{x}_{1:n - 1} | \b{x}_n, \b{z}_n) = p(\b{x}_{1:n - 1} | \b{z}_n)$
  • $p(\b{x}_{1:n - 1} | \b{z}_{n - 1}, \b{z}_n) = p(\b{x}_{1:n - 1} | \b{z}_{n - 1})$
  • $p(\b{x}_{n + 1:N} | \b{z}_n, \b{z}_{n + 1}) = p(\b{x}_{n + 1:N} | \b{z}_{n + 1})$
  • $p(\b{x}_{n + 2:N} | \b{z}_{n + 1}, \b{x}_{n + 1}) = p(\b{x}_{n + 2:N} | \b{z}_{n + 1})$
  • $p(\b{x}_{1:N} | \b{z}_{n - 1}, \b{z}_n) = p(\b{x}_{1:n - 1} | \b{z}_{n - 1}) p(\b{x}_n | \b{z}_n) p(\b{x}_{n + 1:N} | \b{z}_n)$
  • $p(\b{x}_{N + 1} | \b{x}_{1:N}, \b{z}_{N + 1}) = p(\b{x}_{N + 1} | \b{z}_{N + 1})$
  • $p(\b{z}_{N + 1} | \b{z}_N, \b{x}_{1:N}) = p(\b{z}_{N + 1} | \b{z}_N)$

$\alpha(\b{z}_n) := p(\b{x}_{1:n}, \b{z}_n), \beta(\b{z}_n) := p(\b{x}_{n + 1:N} | \b{z}_n)$と定義すると，

\begin{align} \gamma(\b{z}_n) &= p(\b{z}_n | \b{x}_{1:N}) = \frac{p(\b{z}_n, \b{x}_{1:N})}{p(\b{x}_{1:N})} = \frac{p(\b{x}_{1:N} | \b{z}_n) p(\b{z}_n)}{p(\b{x}_{1:N})} = \frac{p(\b{x}_{1:n} | \b{z}_n) p(\b{x}_{n + 1:N} | \b{z}_n) p(\b{z}_n)}{p(\b{x}_{1:N})} \newline &= \frac{\overbrace{p(\b{x}_{1:n}, \b{z}_n)}^{= \alpha(\b{z}_n)} \overbrace{ p(\b{x}_{n + 1:N} | \b{z}_n)}^{= \beta(\b{z}_n)} }{p(\b{x}_{1:N})} = \frac{\alpha(\b{z}_n) \beta(\b{z}_n)}{p(\b{x}_{1:N})} \end{align}

である．さらに$\alpha, \beta$について再帰式を導出する．

\begin{align} \alpha(\b{z}_n) &= p(\b{x}_{1:n}, \b{z}_n) = p(\b{x}_{1:n} | \b{z}_n) p(\b{z_n}) = p(\b{x}_n | \b{z}_n) \underbrace{p(\b{x}_{1:n - 1} | \b{x}_n, \b{z}_n)}_{= p(\b{x}_{1:n - 1} | \b{z}_n)} p(\b{z}_n) = p(\b{x}_n | \b{z}_n) p(\b{x}_{1:n - 1} | \b{z}_n) p(\b{z}_n) \newline &= p(\b{x}_n | \b{z}_n) p(\b{x}_{1:n - 1}, \b{z}_n) = p(\b{x}_n | \b{z}_n) \sum_{\b{z}_{n - 1}} p(\b{x}_{1:n - 1}, \b{z}_n, \b{z}_{n - 1}) = p(\b{x}_n | \b{z}_n) \sum_{\b{z}_{n - 1}} p(\b{x}_{1:n - 1}, \b{z}_n, \b{z}_{n - 1}) \newline &= p(\b{x}_n | \b{z}_n) \sum_{\b{z}_{n - 1}} p(\b{x}_{1:n - 1}, \b{z}_n | \b{z}_{n - 1}) p(\b{z}_{n - 1}) = p(\b{x}_n | \b{z}_n) \sum_{\b{z}_{n - 1}} \underbrace{p(\b{x}_{1:n - 1}, | \b{z}_n, \b{z}_{n - 1})}_{= p(\b{x}_{1:n - 1}, | \b{z}_{n - 1})} p(\b{z}_n | \b{z}_{n - 1}) p(\b{z}_{n - 1}) \newline &= p(\b{x}_n | \b{z}_n) \sum_{\b{z}_{n - 1}} p(\b{x}_{1:n - 1}, | \b{z}_{n - 1}) p(\b{z}_n | \b{z}_{n - 1}) p(\b{z}_{n - 1}) \newline &= p(\b{x}_n | \b{z}_n) \sum_{\b{z}_{n - 1}} \underbrace{p(\b{x}_{1:n - 1}, \b{z}_{n - 1})}_{= \alpha(\b{z}_{n - 1})} p(\b{z}_n | \b{z}_{n - 1}) = p(\b{x}_n | \b{z}_n) \sum_{\b{z}_{n - 1}} \alpha(\b{z}_{n - 1}) p(\b{z}_n | \b{z}_{n - 1}) \end{align}

したがって，$\alpha$について再帰的な式を得る． \begin{align} \alpha(\b{z}_n) = p(\b{x}_n | \b{z}_n) \sum_{\b{z}_{n - 1}} \alpha(\b{z}_{n - 1}) p(\b{z}_n | \b{z}_{n - 1}) \end{align}

$\beta$については

TODO: $\beta$についての再帰式の導出を追加する

となるので，$\beta(\b{z}_N) = 1$である．

実装用の変形．対数をとった形で求める．

Tags: