HMM_understand

why it could be defined as below:

$\boldsymbol{z}_{n} = [0, 0, ..., 1, ..., 0]^T$ $K$ $z_{nk} = 1$ $p$ , random variable

\begin{matrix} p (z_{1} | π) = \prod_{k = 1}^{K} π_{k}^{z_{1 k}} \\ p (z_{n} | z_{n - 1}, A) = \prod_{j = 1}^{K} \prod_{k = 1}^{K} A_{j, k}^{z_{n - 1, j} z_{n k}} \\ p (x_{n} | z_{n}, ϕ) = \prod_{j = 1}^{K} \prod_{t = 1}^{a n y d i m e n s i o n} {ϕ_{j} (t)}^{z_{n j} x_{n} (t)} \end{matrix}

Define $\vec{p}$ constant matrix

\begin{matrix} \vec{p} (z_{n} | θ) \equiv [\begin{matrix} p (z_{n} | θ) | z_{n} = state 1 \\ ⋮ \\ p (z_{n} | θ) | z_{n} = state K \end{matrix}] = [\sum_{z_{n}} p (z_{n} | X, θ^{old}) z_{n}] state k : z_{n} = [\begin{matrix} 0 \\ ⋮ \\ 1 \\ ⋮ \\ 0 \end{matrix}] \\ \vec{p} (z_{1} | θ) = π \\ \vec{p} (z_{n} | z_{n - 1}, θ) \equiv [p (z_{n} | z_{n - 1}, A) | z_{n} = state i, z_{n - 1} = state j] = A \\ \vec{p} (x_{n} | z_{n}, θ) \equiv [p (x_{n} | z_{n}, ϕ) | x_{n} = state i, z_{n} = state j] = ϕ \end{matrix}

$\vec{p}(\boldsymbol{z_n}) \equiv \vec{p}(\boldsymbol{z_n} | \boldsymbol{\theta}), \vec{p}(\boldsymbol{x_n}) \equiv \vec{p}(\boldsymbol{x_n} | \boldsymbol{\theta})$

\begin{matrix} \vec{p} (z_{1}) = π \\ \vec{p} (z_{n}) = A \vec{p} (z_{n - 1}) \\ \vec{p} (x_{n}) = ϕ \cdot \vec{p} (z_{n}) \end{matrix}

$p(\boldsymbol{x}_{\boldsymbol{n}}|\boldsymbol{\phi})$ $any\space dimension \times K$ $\boldsymbol{\phi} = [\phi_1, \phi_2, ...,\phi_j, ...\phi_K]$

$\phi_k$ $k$ $any\space dimension \times 1$

$\boldsymbol{x}_{\boldsymbol{n}}$ $any\space dimension \times 1$

$\boldsymbol{z}_{\boldsymbol{n}}$ $K \times 1$

$z$ is observation value;

$z_n = Az_{n-1}$ $z$ is random variable;

Thus

p (x_{n} | z_{n}, ϕ) = \prod_{j = 1}^{K} \prod_{t = 1}^{a n y d i m e n s i o n} {ϕ_{j} (t)}^{z_{n j} x_{n} (t)}

Goal

\begin{matrix} p (x_{1}, . . ., x_{n}, z_{1}, . . ., z_{n} | π, A, ϕ) = p (x_{1}, . . ., x_{n}, z_{1}, . . ., z_{n} | θ) \\ = p (x_{n} | x_{1}, . . ., x_{n - 1}, z_{1}, . . ., z_{n}, θ) \cdot p (x_{1}, . . ., x_{n - 1}, z_{1}, . . ., z_{n} | θ) \\ = [p (x_{n} | z_{n}, ϕ)] \cdot p (x_{1}, . . ., x_{n - 1}, z_{1}, . . ., z_{n} | θ) \\ = [p (x_{n} | z_{n}, ϕ)] \cdot p (z_{n} | x_{1}, . . ., x_{n - 1}, z_{1}, . . ., z_{n - 1}, θ) \cdot p (x_{1}, . . ., x_{n - 1}, z_{1}, . . ., z_{n - 1} | θ) \\ = [p (x_{n} | z_{n}, ϕ)] \cdot [p (z_{n} | z_{n - 1}, A)] \cdot p (x_{1}, . . ., x_{n - 1}, z_{1}, . . ., z_{n - 1} | θ) \end{matrix}

thus we get

\begin{matrix} p (x_{1}, . . ., x_{n}, z_{1}, . . ., z_{n} | θ) = [p (x_{n} | z_{n}, ϕ)] \cdot [p (z_{n} | z_{n - 1}, A)] \cdot p (x_{1}, . . ., x_{n - 1}, z_{1}, . . ., z_{n - 1} | θ) \end{matrix}

p (X, Z | θ) \equiv p (x_{1}, . . ., x_{N}, z_{1}, . . ., z_{N} | θ) = [\prod_{n = 1}^{N} p (x_{n} | z_{n}, ϕ)] \cdot [\prod_{n = 2}^{N} p (z_{n} | z_{n - 1}, A)] \cdot p (z_{1} | π)

Here

\begin{matrix} p (x_{n} | z_{n}, ϕ) = \prod_{j = 1}^{K} \prod_{t = 1}^{a n y d i m e n s i o n} {ϕ_{j} (t)}^{z_{n j} x_{n} (t)} \\ p (z_{n} | z_{n - 1}, A) = \prod_{j = 1}^{K} \prod_{k = 1}^{K} A_{k, j}^{z_{n - 1, j} z_{n k}} \\ p (z_{1} | π) = \prod_{k = 1}^{K} π_{k}^{z_{1 k}} \end{matrix}

\begin{matrix} \ln p (X, Z | θ) \\ = \sum_{n = 1}^{N} \sum_{j = 1}^{K} \sum_{t = 1}^{a n y d i m e n s i o n} z_{n j} x_{n} (t) \ln ϕ_{j} (t) + \sum_{n = 2}^{N} \sum_{k = 1}^{K} \sum_{j = 1}^{K} z_{n - 1, j} z_{n, k} \ln A_{k j} + \sum_{k = 1}^{K} z_{1 k} \ln π_{k} \\ = \sum_{n = 1}^{N} z_{n}^{T} < \ln ϕ, x_{n} > + \sum_{n = 2}^{N} z_{n - 1}^{T} \ln A^{T} \cdot z_{n} + \ln π^{T} \cdot z_{1} \end{matrix}

$t$ is continuous

\begin{matrix} < \ln ϕ, x_{n} >= \int_{- \infty}^{+ \infty} \ln ϕ (t) \cdot x_{n} (t) d t \\ ϕ = [\begin{matrix} ϕ_{1} (t) \\ ϕ_{2} (t) \\ ⋮ \\ ϕ_{K} (t) \end{matrix}] \end{matrix}

if m is discrete

\begin{matrix} < \ln ϕ, x_{n} >= \ln ϕ^{T} \cdot x_{n} \\ ϕ = {[\begin{matrix} ϕ_{11} & \dots & ϕ_{1 m} & \dots ϕ_{1 M} \\ ϕ_{21} & \dots & ϕ_{2 m} & \dots ϕ_{2 M} \\ ⋮ & ⋮ \\ ϕ_{K 1} & \dots & ϕ_{K m} & \dots ϕ_{K M} \end{matrix}]}^{T} M \times K matrix \\ x_{n} : M \times 1 matrix \end{matrix}

Only $\boldsymbol{x}_{\boldsymbol{n}}$ $n \in \{1,..., N\}$

$X$ $Y\equiv f(X)$ $P(X=x) \equiv p(x)$

then

\begin{matrix} P (Y = y) d y \equiv P (X = x) d x = p (x) d x, y = f (x) \\ ⟹ P (Y = y) = p (x) \frac{d x}{d f (x)} \\ ⟹ E [Y] = \int_{- \infty}^{+ \infty} y \cdot P (Y = y) d y = \int_{- \infty}^{+ \infty} f (x) p (x) d x \end{matrix}

期望最⼤化算法，或者EM算法

max \ln p (X | θ) = L (q, θ) + KL (q ∥ p)

where

\begin{array}{r} L (q, θ) = \sum_{Z} q (Z) \ln {\frac{p (X, Z | θ)}{q (Z)}} \\ KL (q ∥ p) = - \sum_{Z} q (Z) \ln {\frac{p (Z | X, θ)}{q (Z)}} \end{array}

Where

$q(\boldsymbol{Z})$ $\forall$ $\boldsymbol{Z}$
$\mathcal{L}(q, \boldsymbol{\theta})$ $q(\boldsymbol{Z})$ $\boldsymbol{\theta}$ 函数
$\mathrm{KL}(q \| p)$ $q(\boldsymbol{Z})$ $\boldsymbol{\theta}$ $p(Z|X, \theta),\space q(Z)$ $\geq 0$

\begin{matrix} \ln p (X | θ) \geq L (q, θ) = \sum_{Z} q (Z) \ln {\frac{p (X, Z | θ)}{q (Z)}}, \forall q (Z) \\ if q (Z) \Leftarrow p (Z | X, θ), here KL (q ∥ p) = 0 \\ \ln p (X | θ) = L (q, θ) = \sum_{Z} p (Z | X, θ) \ln {\frac{p (X, Z | θ)}{p (Z | X, θ)}} \end{matrix}

notice: $X$ $Z, \theta$ $q(Z), \theta$ 替代；

调整法

\ln p (X | θ) = L (q, θ) + KL (q | p)

$\theta$ $q(Z)$ [E步骤]

\begin{matrix} q (Z) \Leftarrow p (Z | X, θ) \\ \ln p (X | θ) = L (q, θ) + KL (q | p) = const 与q无关 \\ KL (q | p) ↓\Leftarrow 0, update L (q, θ) ↑ \\ \ln p (X | θ) == L (q, θ) \\ θ^{old} \Leftarrow θ \end{matrix}

$q(Z)$ $\theta$ [M步骤]

$\theta$ $\mathrm{KL}(q | p)=-\sum\limits_{\boldsymbol{Z}} q(\boldsymbol{Z}) \ln \left\{\frac{p(\boldsymbol{Z} | \boldsymbol{X}, \boldsymbol{\theta})}{q(\boldsymbol{Z})}\right\}$

\begin{matrix} L (q, θ) = \sum_{Z} q (Z) \ln {\frac{p (X, Z | θ)}{q (Z)}} \\ = \sum_{Z} p (Z | X, θ^{old}) \ln {\frac{p (X, Z | θ)}{p (Z | X, θ^{old})}} \\ = \sum_{Z} p (Z | X, θ^{old}) \ln p (X, Z | θ) - const \end{matrix}

set

Q (θ, θ^{old}) \equiv \sum_{Z} p (Z | X, θ^{old}) \ln p (X, Z | θ)

get

\begin{matrix} θ \Leftarrow \underset{\overset{―}{θ}}{argmax} L (q, \overset{―}{θ}) \\ = \underset{\overset{―}{θ}}{argmax} Q (\overset{―}{θ}, θ^{old}) \\ update L (q, θ) ↑ \end{matrix}

update

\begin{matrix} KL (q | p) ↑= - \sum_{Z} q (Z) \ln {\frac{p (Z | X, θ)}{q (Z)}} > 0 \\ \ln p (X | θ) ↑= L (q, θ) ↑ + KL (q | p) ↑ \end{matrix}

Conclusion

$\space \mathcal{L}(q, \boldsymbol{\theta}) \uparrow$ 均上升;

$\ln p(\boldsymbol{X} | \boldsymbol{\theta})=\mathcal{L}(q, \boldsymbol{\theta})\uparrow + 0\downarrow= \text{const}$

$\ln p(\boldsymbol{X} | \boldsymbol{\theta}) \uparrow= \mathcal{L}(q, \boldsymbol{\theta})\uparrow+\mathrm{KL}(q | p)\uparrow$

$\ln p(\boldsymbol{X} | \boldsymbol{\theta}) \uparrow$ $\space \mathcal{L}(q, \boldsymbol{\theta}) \uparrow$

$Q(\theta^{old}, \theta)$

$\sum$ $\sum\limits_{z_1} p(z_1, z_2) = P(z_2)$

$X$ is fix observation value;

$Z$ $\ln p(X, Z|\theta)$ is random variable

$\sum_\limits{\boldsymbol{Z}} p\left(\boldsymbol{Z} | \boldsymbol{X}, \boldsymbol{\theta}^{\text { old }}\right)$ of $Z$ [probability distribution] random variable

\begin{aligned} Q (θ, θ^{old}) & \equiv \sum_{Z} p (Z | X, θ^{old}) \ln p (X, Z | θ) \\ = \sum_{Z} p (Z | X, θ^{old}) {\sum_{n = 1}^{N} z_{n}^{T} < \ln ϕ, x_{n} > + \sum_{n = 2}^{N} z_{n - 1}^{T} \ln A^{T} \cdot z_{n} + \ln π^{T} \cdot z_{1}} \\ = {\sum_{z_{n}} p (z_{n} | X, θ^{old}) \sum_{n = 1}^{N} z_{n}^{T} < \ln ϕ, x_{n} >} \\ + {\sum_{z_{n - 1}, z_{n}} p (z_{n - 1}, z_{n} | X, θ^{old}) \sum_{n = 2}^{N} z_{n - 1}^{T} \ln A^{T} \cdot z_{n}} \\ + {\sum_{z_{1}} p (z_{1} | X, θ^{old}) z_{1}^{T} \ln π} \\ = {\sum_{n = 1}^{N} [\sum_{z_{n}} p (z_{n} | X, θ^{old}) z_{n}^{T}] < \ln ϕ, x_{n} >} \\ + {\sum_{n = 2}^{N} \sum [\sum_{z_{n - 1}, z_{n}} z_{n - 1} p (z_{n - 1}, z_{n} | X, θ^{old}) z_{n}^{T}] ⊙ \ln A^{T}} \\ + {[\sum_{z_{1}} p (z_{1} | X, θ^{old}) z_{1}^{T}] \ln π} \\ = \sum_{n = 1}^{N} γ_{n}^{T} < \ln ϕ, x_{n} > + \sum_{n = 2}^{N} tr (ξ_{n}^{T} \ln A) + γ_{1}^{T} \ln π \end{aligned}

where

\begin{aligned} \sum_{z_{n - 1}, z_{n}} p (z_{n - 1}, z_{n} | X, θ^{old}) \sum_{n = 2}^{N} z_{n - 1}^{T} \ln A^{T} \cdot z_{n} \\ = \sum {p (z_{n - 1}, z_{n} | X, θ^{old}) ⊙ \sum_{n = 2}^{N} [z_{n - 1}^{T} \ln A^{T} \cdot z_{n}]} \\ = \sum_{n = 2}^{N} tr (p (z_{n - 1}, z_{n} | X, θ^{old}) {[z_{n - 1}^{T} \ln A^{T} \cdot z_{n}]}^{T}) \\ = \sum_{n = 2}^{N} tr ([z_{n - 1} p (z_{n - 1}, z_{n} | X, θ^{old}) z_{n}^{T}] \cdot \ln A) \\ = \sum_{n = 2}^{N} \sum {[z_{n} p (z_{n - 1}, z_{n} | X, θ^{old}) z_{n - 1}^{T}] ⊙ \ln A} \end{aligned}

$X, \theta^{\text{old}}$ 分别为已知、固定在 M步骤

$\boldsymbol{\gamma_n} \equiv \left[\sum_{\boldsymbol{z_n}} p\left(\boldsymbol{z_n} | \boldsymbol{X}, \boldsymbol{\theta}^{\text { old }}\right)\boldsymbol{z_{n}} \right]$ $E[\boldsymbol{z_n} | \boldsymbol{X}, \boldsymbol{\theta}^{\text { old }}]$ $K\times 1$

$\boldsymbol{\xi_n} \equiv [\boldsymbol{z_{n}}p\left(\boldsymbol{z_{n-1},z_n} | \boldsymbol{X}, \boldsymbol{\theta}^{\text { old }}\right) \boldsymbol{z_{n-1}}^T]$ $E[\boldsymbol{z_{n}z_{n-1}^T} | \boldsymbol{X}, \boldsymbol{\theta}^{\text { old }}]$ $K\times K$

下面求解

\begin{aligned} max_{θ} Q (θ, θ^{old}) & \equiv \sum_{Z} p (Z | X, θ^{old}) \ln p (X, Z | θ) \\ = \sum_{n = 1}^{N} γ_{n}^{T} < \ln ϕ, x_{n} > + \sum_{n = 2}^{N} tr (ξ_{n}^{T} \ln A) + γ_{1}^{T} \ln π \end{aligned}

subject to

\begin{matrix} s.t. γ_{n}^{T} \cdot 1. = 1 tr (ξ_{n}^{T} \cdot 1.) = 1 \\ {1.}^{T} \cdot ϕ = {1.}^{T} {1.}^{T} \cdot A = {1.}^{T} {1.}^{T} \cdot π = 1 \end{matrix}

with Lagrange method:

\begin{aligned} L & \equiv {\sum_{n = 1}^{N} γ_{n}^{T} < \ln ϕ, x_{n} > + \sum_{n = 2}^{N} tr (ξ_{n}^{T} \ln A) + γ_{1}^{T} \ln π} \\ - \sum_{t = 1}^{a n y d i m e n s i o n} u_{t} {{1.}^{T} \cdot < ϕ, δ (t) > - 1} \\ - \sum_{k = 1}^{K} v_{k} {{1.}^{T} A \cdot σ_{k} - 1} \\ - w_{1} {{1.}^{T} π - 1} \end{aligned}

$\sigma_k = \begin{bmatrix} 0\\ \vdots\\ 1\\ \vdots\\ 0 \end{bmatrix}$ $1 \times K$

$t$ is discrete, $any \space dimenstion = M$

$\delta(t) = \begin{bmatrix} 0\\ \vdots\\ 1\\ \vdots\\ 0 \end{bmatrix}$ $1 \times M$ ,

$<\ln \boldsymbol{\phi}, \boldsymbol{x_{n}}>=\ln \boldsymbol{\phi}^T \cdot \boldsymbol{x_{n}}$

$<\boldsymbol{\phi} , \delta(t)>=\boldsymbol{\phi}^T \cdot \delta(t)$

\begin{aligned} \frac{\partial Q}{\partial ϕ} & = {\sum_{n = 1}^{N} [γ_{n} \cdot x_{n}^{T}]}^{T} ⊙ \frac{1}{ϕ} - \sum_{t = 1}^{M} u_{t} \cdot 1. δ (t)^{T} \\ = {\sum_{n = 1}^{N} [x_{n} \cdot γ_{n}^{T}]} ⊙ \frac{1}{ϕ} - [\begin{array}{c} u_{1} & \dots & u_{t} \dots & u_{M} \\ u_{1} & \dots & u_{t} \dots & u_{M} \\ ⋮ & ⋮ \\ u_{1} & \dots & u_{t} \dots & u_{M} \end{array}] = 0 \\ \frac{\partial Q}{\partial A} & = [\sum_{n = 2}^{N} ξ_{n}] ⊙ \frac{1}{A} - \sum_{k = 1}^{K} v_{k} \cdot 1. σ_{k}^{T} \\ = [\sum_{n = 2}^{N} ξ_{n}] ⊙ \frac{1}{A} - [\begin{array}{c} v_{1} & \dots & v_{k} \dots & v_{K} \\ v_{1} & \dots & v_{k} \dots & v_{K} \\ ⋮ & ⋮ \\ v_{1} & \dots & v_{k} \dots & v_{K} \end{array}] = 0 \\ \frac{\partial Q}{\partial π} & = γ_{1} ⊙ \frac{1.}{π} - w_{1} \cdot 1. = 0 \end{aligned}

\begin{aligned} \frac{{\sum_{n = 1}^{N} [x_{n} \cdot γ_{n}^{T}]}_{i j}}{ϕ_{i j}} = u_{j} \\ ⟹ \sum_{i = 1}^{K} \frac{{\sum_{n = 1}^{N} [x_{n} \cdot γ_{n}^{T}]}_{i j}}{u_{j}} = \sum_{i = 1}^{K} ϕ_{i j} = 1 \\ ⟹ u_{j} = \sum_{i = 1}^{K} {\sum_{n = 1}^{N} [x_{n} \cdot γ_{n}^{T}]}_{i j} \\ ⟹ ϕ_{i j} = \frac{{\sum_{n = 1}^{N} [x_{n} \cdot γ_{n}^{T}]}_{i j}}{\sum_{i = 1}^{K} {\sum_{n = 1}^{N} [x_{n} \cdot γ_{n}^{T}]}_{i j}} \\ ⟹ ϕ = {\sum_{n = 1}^{N} [x_{n} \cdot γ_{n}^{T}]} ⊙ \frac{1.}{1. \cdot {1.}^{T} {\sum_{n = 1}^{N} [x_{n} \cdot γ_{n}^{T}]}} \\ ⟹ ϕ = {\sum_{n = 1}^{N} [x_{n} \cdot γ_{n}^{T}]} ⊙ \frac{1.}{1. {[\sum_{n = 1}^{N} γ_{n}]}^{T}} \\ \frac{[\sum_{n = 2}^{N} ξ_{n}]_{i j}}{A_{i j}} = v_{j} \\ ⟹ \sum_{i = 1}^{K} \frac{[\sum_{n = 2}^{N} ξ_{n}]_{i j}}{v_{j}} = \sum_{i = 1}^{K} A_{i j} = 1 \\ ⟹ v_{j} = \sum_{i = 1}^{K} [\sum_{n = 2}^{N} ξ_{n}]_{i j} \\ ⟹ A_{i j} = \frac{[\sum_{n = 2}^{N} ξ_{n}]_{i j}}{\sum_{i = 1}^{K} [\sum_{n = 2}^{N} ξ_{n}]_{i j}} \\ ⟹ A = [\sum_{n = 2}^{N} ξ_{n}] ⊙ \frac{1.}{1. \cdot {1.}^{T} [\sum_{n = 2}^{N} ξ_{n}]} \\ \frac{[γ_{1}]_{i}}{π_{i}} = w_{1} \\ ⟹ \sum_{i = 1}^{K} \frac{[γ_{1}]_{i}}{w_{1}} = \sum_{i = 1}^{K} π_{i} = 1 \\ ⟹ w_{1} = \sum_{i = 1}^{K} [γ_{1}]_{i} \\ ⟹ π_{i} = \frac{[γ_{1}]_{i}}{\sum_{i = 1}^{K} [γ_{1}]_{i}} \\ ⟹ π = γ_{1} ⊙ \frac{1.}{1. \cdot {1.}^{T} γ_{1}} \end{aligned}

To sum up

\begin{aligned} ϕ & = {\sum_{n = 1}^{N} [x_{n} \cdot γ_{n}^{T}]} ⊙ \frac{1.}{1. {[\sum_{n = 1}^{N} γ_{n}]}^{T}} \\ A & = [\sum_{n = 2}^{N} ξ_{n}] ⊙ \frac{1.}{1. \cdot {1.}^{T} [\sum_{n = 2}^{N} ξ_{n}]} \\ π & = γ_{1} ⊙ \frac{1.}{1. \cdot {1.}^{T} γ_{1}} \end{aligned}

How to calculate $\boldsymbol{\gamma_n}, \boldsymbol{\xi_n}$

$\boldsymbol{\gamma_n} \equiv \left[\sum_\limits{\boldsymbol{z_n}} p\left(\boldsymbol{z_n} | \boldsymbol{X}, \boldsymbol{\theta}^{\text { old }}\right)\boldsymbol{z_{n}} \right]$ $E[\boldsymbol{z_n} | \boldsymbol{X}, \boldsymbol{\theta}^{\text { old }}]$ $K\times 1$

$\boldsymbol{\xi_n} \equiv [\sum_\limits{\boldsymbol{z_{n-1}, z_n}} \boldsymbol{z_{n}}p\left(\boldsymbol{z_{n-1},z_n} | \boldsymbol{X}, \boldsymbol{\theta}^{\text { old }}\right) \boldsymbol{z_{n-1}}^T]$ $E[\boldsymbol{z_{n}z_{n-1}^T} | \boldsymbol{X}, \boldsymbol{\theta}^{\text { old }}]$ $K\times K$

similarly get：

\begin{matrix} γ_{n} \equiv \vec{p} (z_{n} | X, θ^{old}) \equiv [\begin{matrix} p (z_{n} | X, θ^{old}) | z_{n} = state 1 \\ ⋮ \\ p (z_{n} | X, θ^{old}) | z_{n} = state K \end{matrix}] \\ ξ_{n} \equiv \vec{p} (z_{n - 1}, z_{n} | X, θ^{old}) \equiv [p (z_{n - 1}, z_{n} | X, θ^{old}) | z_{n} = state i, z_{n - 1} = state j] \\ the same size as z_{n} z_{n - 1}^{T} \end{matrix}

\begin{aligned} γ_{n} & \equiv \vec{p} (z_{n} | X, θ^{old}) \\ = \vec{p} (z_{n}, X | θ^{old}) ⊙ \frac{1.}{\vec{p} (X | θ^{old})} \\ = \vec{p} (z_{n}, x_{1}, . . ., x_{n} | θ^{old}) ⊙ \vec{p} (x_{n + 1}, . . ., x_{N} | z_{n}, x_{1}, . . ., x_{n}, θ^{old}) ⊙ \frac{1.}{\vec{p} (X | θ^{old})} \\ = \vec{p} (z_{n}, x_{1}, . . ., x_{n} | θ^{old}) ⊙ \vec{p} (x_{n + 1}, . . ., x_{N} | z_{n}, θ^{old}) ⊙ \frac{1.}{\vec{p} (X | θ^{old})} \\ = α_{n} ⊙ β_{n} ⊙ \frac{1.}{\vec{p} (X | θ^{old})} \\ ξ_{n} & \equiv \vec{p} (z_{n - 1}, z_{n} | X, θ^{old}) \\ = \vec{p} (z_{n - 1}, z_{n}, X | θ^{old}) ⊙ \frac{1.}{\vec{p} (X | θ^{old})} \\ = \vec{p} (z_{n - 1}, x_{1}, . . ., x_{n - 1} | θ^{old}) \\ ⊙ \vec{p} (z_{n}, x_{n}, . . ., x_{N} | z_{n - 1}, x_{1}, . . ., x_{n - 1}, θ^{old}) \\ ⊙ \frac{1.}{\vec{p} (X | θ^{old})} \\ = \vec{p} (z_{n - 1}, x_{1}, . . ., x_{n - 1} | θ^{old}) \\ ⊙ \vec{p} (z_{n}, x_{n}, . . ., x_{N} | z_{n - 1}, θ^{old}) \\ ⊙ \frac{1.}{\vec{p} (X | θ^{old})} \\ = \vec{p} (z_{n - 1}, x_{1}, . . ., x_{n - 1} | θ^{old}) \\ ⊙ \vec{p} (z_{n} | z_{n - 1}, θ^{old}) \\ ⊙ \vec{p} (x_{n}, . . ., x_{N} | z_{n - 1}, z_{n}, θ^{old}) \\ ⊙ \frac{1.}{\vec{p} (X | θ^{old})} \\ = \vec{p} (z_{n - 1}, x_{1}, . . ., x_{n - 1} | θ^{old}) \\ ⊙ \vec{p} (z_{n} | z_{n - 1}, θ^{old}) \\ ⊙ \vec{p} (x_{n}, . . ., x_{N} | z_{n}, θ^{old}) \\ ⊙ \frac{1.}{\vec{p} (X | θ^{old})} \\ = \vec{p} (z_{n - 1}, x_{1}, . . ., x_{n - 1} | θ^{old}) \\ ⊙ \vec{p} (z_{n} | z_{n - 1}, θ^{old}) \\ ⊙ \vec{p} (x_{n} | z_{n}, θ^{old}) \\ ⊙ \vec{p} (x_{n + 1}, . . ., x_{N} | z_{n}, x_{n}, θ^{old}) \\ ⊙ \frac{1.}{\vec{p} (X | θ^{old})} \\ = \vec{p} (z_{n - 1}, x_{1}, . . ., x_{n - 1} | θ^{old}) \\ ⊙ \vec{p} (z_{n} | z_{n - 1}, θ^{old}) \\ ⊙ \vec{p} (x_{n} | z_{n}, θ^{old}) \\ ⊙ \vec{p} (x_{n + 1}, . . ., x_{N} | z_{n}, θ^{old}) \\ ⊙ \frac{1.}{\vec{p} (X | θ^{old})} \\ = [1. \cdot α_{n - 1}^{T}] ⊙ A ⊙ [[ϕ^{T} \cdot x_{n}] ⊙ β_{n} \cdot {1.}^{T}] ⊙ \frac{1.}{\vec{p} (X | θ^{old})} \\ = \frac{1}{p (X | θ^{old})} {[[ϕ^{T} \cdot x_{n}] ⊙ β_{n}] \cdot α_{n - 1}^{T}} ⊙ A \end{aligned}

$p(\boldsymbol{X} | \boldsymbol{\theta}^{\text { old }})=\sum_\limits{Z_N}p(\boldsymbol{z_N}, \boldsymbol{X} | \boldsymbol{\theta}^{\text { old }})=\sum \boldsymbol{\alpha_N}=1.^T\cdot \boldsymbol{\alpha_N}$ is constant

\begin{aligned} \vec{p} (X | θ^{old}) & = p (X | θ^{old}) \cdot 1. \\ p (X | θ^{old}) & = {1.}^{T} \cdot p (z_{N}, X | θ^{old}) \\ = {1.}^{T} \cdot α_{N} \end{aligned}

$\boldsymbol{\alpha_n}, \boldsymbol{\beta_n}$ $\boldsymbol{\gamma_n}, \boldsymbol{\xi_n}$

\begin{matrix} α_{n} \equiv \vec{p} (z_{n}, x_{1}, . . ., x_{n} | θ^{old}) \\ β_{n} \equiv \vec{p} (x_{n + 1}, . . ., x_{N} | z_{n}, θ^{old}) \end{matrix}

How to obtain $\boldsymbol{\alpha_n}, \boldsymbol{\beta_n}$

$\boldsymbol{\alpha_n}$ , initial value:

\begin{aligned} α_{1} & = \vec{p} (z_{1}, x_{1} | θ^{old}) \\ = \vec{p} (x_{1} | z_{1}, θ^{old}) ⊙ \vec{p} (z_{1} | θ^{old}) \\ = [ϕ^{T} \cdot x_{1}] ⊙ π \end{aligned}

Recurrence relation

\begin{aligned} α_{n} & \equiv \vec{p} (z_{n}, x_{1}, . . ., x_{n} | θ^{old}) \\ = \vec{p} (z_{n} | θ^{old}) ⊙ \vec{p} (x_{n} | z_{n}, θ^{old}) ⊙ \vec{p} (x_{1}, . . ., x_{n - 1} | z_{n}, x_{n}, θ^{old}) \\ = \vec{p} (z_{n} | θ^{old}) ⊙ \vec{p} (x_{n} | z_{n}, θ^{old}) ⊙ \vec{p} (x_{1}, . . ., x_{n - 1} | z_{n}, θ^{old}) \\ = \vec{p} (x_{n} | z_{n}, θ^{old}) ⊙ \vec{p} (z_{n}, x_{1}, . . ., x_{n - 1} | θ^{old}) \\ = \vec{p} (x_{n} | z_{n}, θ^{old}) ⊙ {\vec{p} (z_{n - 1}, z_{n}, x_{1}, . . ., x_{n - 1} | θ^{old}) \cdot 1.} \\ = \vec{p} (x_{n} | z_{n}, θ^{old}) ⊙ {[\vec{p} (z_{n - 1}, z_{n} | θ^{old}) ⊙ \vec{p} (x_{1}, . . ., x_{n - 1} | z_{n - 1}, z_{n}, θ^{old})] \cdot 1.} \\ = \vec{p} (x_{n} | z_{n}, θ^{old}) ⊙ {[(1. \cdot \vec{p} (z_{n - 1} | θ^{old})^{T}) ⊙ \vec{p} (z_{n} | z_{n - 1}, θ^{old}) ⊙ (1. \cdot \vec{p} (x_{1}, . . ., x_{n - 1} | z_{n - 1}, θ^{old})^{T})] \cdot 1.} \\ = \vec{p} (x_{n} | z_{n}, θ^{old}) ⊙ {[\vec{p} (z_{n} | z_{n - 1}, θ^{old}) ⊙ (1. \cdot \vec{p} (z_{n - 1}, x_{1}, . . ., x_{n - 1} | θ^{old})^{T})] \cdot 1.} \\ = [ϕ^{T} \cdot x_{n}] ⊙ {[A ⊙ (1. \cdot α_{n - 1}^{T})] \cdot 1.} \\ = [ϕ^{T} \cdot x_{n}] ⊙ [A \cdot α_{n - 1}] \end{aligned}

x_{n}^{T} \cdot ϕ \cdot A \cdot α_{n - 1}

$\boldsymbol{\beta_n}$ , last initial value:

\begin{aligned} β_{N} & = \vec{p} (1 | z_{N}, θ^{old}) = 1 \end{aligned}

Recurrence relation

\begin{aligned} β_{n} & \equiv \vec{p} (x_{n + 1}, . . ., x_{N} | z_{n}, θ^{old}) \\ = {\vec{p} (z_{n + 1}, x_{n + 1}, . . ., x_{N} | z_{n}, θ^{old})^{T} \cdot 1.} \\ = {[\vec{p} (z_{n + 1} | z_{n}, θ^{old}) ⊙ \vec{p} (x_{n + 1}, . . ., x_{N} | z_{n}, z_{n + 1}, θ^{old})]^{T} \cdot 1.} \\ = {[\vec{p} (z_{n + 1} | z_{n}, θ^{old}) ⊙ (\vec{p} (x_{n + 1}, . . ., x_{N} | z_{n + 1}, θ^{old}) \cdot {1.}^{T})]^{T} \cdot 1.} \\ = {[\vec{p} (z_{n + 1} | z_{n}, θ^{old}) ⊙ ([\vec{p} (x_{n + 1} | z_{n + 1}, θ^{old}) ⊙ \vec{p} (x_{n + 2}, . . ., x_{N} | z_{n + 1}, x_{n + 1}, θ^{old})] \cdot {1.}^{T})]^{T} \cdot 1.} \\ = {[\vec{p} (z_{n + 1} | z_{n}, θ^{old}) ⊙ ([\vec{p} (x_{n + 1} | z_{n + 1}, θ^{old}) ⊙ \vec{p} (x_{n + 2}, . . ., x_{N} | z_{n + 1}, θ^{old})] \cdot {1.}^{T})]^{T} \cdot 1.} \\ = {[A ⊙ ([[ϕ^{T} \cdot x_{n + 1}] ⊙ β_{n + 1}] \cdot {1.}^{T})]^{T} \cdot 1.} \\ = A^{T} \cdot ([ϕ^{T} \cdot x_{n + 1}] ⊙ β_{n + 1}) \end{aligned}

To sum up

\begin{aligned} α_{1} & = [ϕ^{T} \cdot x_{1}] ⊙ π \\ α_{n} & = [ϕ^{T} \cdot x_{n}] ⊙ [A \cdot α_{n - 1}] \\ β_{N} & = 1. \\ β_{n} & = A^{T} \cdot ([ϕ^{T} \cdot x_{n + 1}] ⊙ β_{n + 1}) \end{aligned}

Then

\begin{aligned} γ_{n} & = α_{n} ⊙ β_{n} ⊙ \frac{1.}{\vec{p} (X | θ^{old})} \\ = \frac{1}{{1.}^{T} \cdot α_{N}} [α_{n} ⊙ β_{n}] \\ ξ_{n} & = \frac{1}{p (X | θ^{old})} {[[ϕ^{T} \cdot x_{n}] ⊙ β_{n}] \cdot α_{n - 1}^{T}} ⊙ A \\ = \frac{1}{{1.}^{T} \cdot α_{N}} {[[ϕ^{T} \cdot x_{n}] ⊙ β_{n}] \cdot α_{n - 1}^{T}} ⊙ A \end{aligned}

$\boldsymbol{\alpha_N}, \boldsymbol{\beta_1}$ are so small

$p(\boldsymbol{X} | \boldsymbol{\theta}^{\text { old }})$ into 2 part

\begin{aligned} p (X | θ^{old}) & = p (x_{1}, \dots, x_{n} | θ^{old}) p (x_{n + 1}, \dots, x_{N} | x_{1}, \dots, x_{n}, θ^{old}) \end{aligned}

define

\begin{aligned} {\hat{α}}_{n} & \equiv \frac{1}{p (x_{1}, \dots, x_{n} | θ^{old})} α_{n} = \vec{p} (z_{n} | x_{1}, \dots, x_{n}, θ^{old}) \\ = {\prod_{k = 1}^{n} p (x_{k} | x_{1}, \dots, x_{k - 1}, θ^{old})} α_{n} \\ = {\prod_{k = 1}^{n} c_{k}} α_{n} notice {1.}^{T} {\hat{α}}_{n} = \sum_{z_{n}} p (z_{n} | x_{1}, \dots, x_{n}, θ^{old}) = 1 \end{aligned}

the other way

\begin{aligned} c_{n} {\hat{α}}_{n} & = p (x_{n} | x_{1}, \dots, x_{n - 1}, θ^{old}) \vec{p} (z_{n} | x_{1}, \dots, x_{n}, θ^{old}) \\ = \vec{p} (z_{n}, x_{n} | x_{1}, \dots, x_{n - 1}, θ^{old}) \\ = \vec{p} (z_{n} | x_{1}, \dots, x_{n - 1}, θ^{old}) ⊙ \vec{p} (x_{n} | z_{n} θ^{old}) \\ = [\vec{p} (z_{n}, z_{n - 1} | x_{1}, \dots, x_{n - 1}, θ^{old}) \cdot 1.] ⊙ \vec{p} (x_{n} | z_{n} θ^{old}) \\ = [[1. \cdot \vec{p} (z_{n - 1} | x_{1}, \dots, x_{n - 1}, θ^{old})^{T}] ⊙ \vec{p} (z_{n} | z_{n - 1}) \cdot 1.] ⊙ \vec{p} (x_{n} | z_{n} θ^{old}) \\ = [\vec{p} (z_{n} | z_{n - 1}) \vec{p} (z_{n - 1} | x_{1}, \dots, x_{n - 1}, θ^{old})] ⊙ \vec{p} (x_{n} | z_{n} θ^{old}) \\ = [A \cdot {\hat{α}}_{n - 1}] ⊙ [ϕ^{T} \cdot x_{n}] \\ = [ϕ^{T} \cdot x_{n}] ⊙ [A \cdot {\hat{α}}_{n - 1}] \end{aligned} c_{n} = {1.}^{T} c_{n} \cdot α_{n} = {1.}^{T} \cdot {[ϕ^{T} \cdot x_{n}] ⊙ [A \cdot {\hat{α}}_{n - 1}]}

\begin{aligned} {\hat{α}}_{n} & \equiv \frac{1}{c_{n}} [ϕ^{T} \cdot x_{n}] ⊙ [A \cdot {\hat{α}}_{n - 1}] \\ = \frac{1}{{1.}^{T} \cdot {[ϕ^{T} \cdot x_{n}] ⊙ [A \cdot {\hat{α}}_{n - 1}]}} [ϕ^{T} \cdot x_{n}] ⊙ [A \cdot {\hat{α}}_{n - 1}] \\ {\hat{α}}_{1} & = \frac{1}{{1.}^{T} \cdot {[ϕ^{T} \cdot x_{n}] ⊙ π}} [ϕ^{T} \cdot x_{n}] ⊙ π \end{aligned}

thesame

\begin{aligned} \frac{{\hat{β}}_{n}}{{\hat{β}}_{n + 1}} & \equiv \frac{β_{n}}{β_{n + 1}} \cdot \frac{\frac{1}{p (x_{n + 1}, \dots, x_{N} | x_{1}, \dots, x_{n}, θ^{old})}}{\frac{1}{p (x_{n + 2}, \dots, x_{N} | x_{1}, \dots, x_{n + 1}, θ^{old})}} \\ = \frac{β_{n}}{β_{n + 1}} \cdot \frac{p (x_{1}, \dots, x_{n} | θ^{old})}{p (x_{1}, \dots, x_{n + 1} | θ^{old})} \\ = \frac{β_{n}}{β_{n + 1}} \cdot \frac{1}{p (x_{n + 1} | x_{1}, \dots, x_{n}, θ^{old})} \\ = \frac{β_{n}}{β_{n + 1}} \cdot \frac{1}{c_{n + 1}} \end{aligned}

the

\begin{aligned} {\hat{β}}_{n} & \equiv \frac{1}{p (x_{n + 1}, \dots, x_{N} | x_{1}, \dots, x_{n}, θ^{old})} β_{n} \\ = \frac{1}{p (x_{n + 1}, \dots, x_{N} | x_{1}, \dots, x_{n}, θ^{old})} \vec{p} (x_{n + 1}, . . ., x_{N} | z_{n}, θ^{old}) \\ = \frac{1}{c_{n + 1}} A^{T} \cdot ([ϕ^{T} \cdot x_{n + 1}] ⊙ {\hat{β}}_{n + 1}) \\ {\hat{β}}_{N} & = 1. \end{aligned}

then

\begin{aligned} γ_{n} & = [{\hat{α}}_{n} ⊙ {\hat{β}}_{n}] \\ ξ_{n} & = \frac{1}{c_{n}} {[[ϕ^{T} \cdot x_{n}] ⊙ {\hat{β}}_{n}] \cdot {\hat{α}}_{n - 1}^{T}} ⊙ A \end{aligned}

α_{N}

\begin{aligned} \vec{p} (X | θ^{old}) & = p (X | θ^{old}) \cdot 1. \\ p (X | θ^{old}) & = {1.}^{T} \cdot p (z_{N}, X | θ^{old}) \\ = {1.}^{T} \cdot α_{N} \end{aligned}

\begin{aligned} ϕ & = {x_{n} \cdot [\sum_{n = 2}^{N} γ_{n}]^{T}} ⊙ \frac{1.}{1. \cdot {1.}^{T} {x_{n} \cdot [\sum_{n = 2}^{N} γ_{n}]^{T}}} \\ A & = [\sum_{n = 2}^{N} ξ_{n}] ⊙ \frac{1.}{1. \cdot {1.}^{T} [\sum_{n = 2}^{N} ξ_{n}]} \\ π & = γ_{1} ⊙ \frac{1.}{1. \cdot {1.}^{T} γ_{1}} \end{aligned}

Goal

期望最⼤化算法，或者EM算法

consider Q(θold,θ)Q(\theta^{old}, \theta)

$Q(\theta^{old}, \theta)$