NLP Homework 03 ——冯煜博

题目描述

（盒子和球模型）假设有3个盒子，每个盒子里装有红白两种颜色的球，盒子里的红白球有下表列出，初始状态分布。

解答

1. 给出HMM模型 \(\mu=(A, B,\pi)\)

A，“状态转移矩阵”如下：
\[
\begin{array}{c|lcr}
A & \text{box1} & \text{box2} & \text{box3} \\
\hline
box1 & 0.5 & 0.2 & 0.3 \\
box2 & 0.3 & 0.5 & 0.2 \\
box3 & 0.2 & 0.3 & 0.5
\end{array}
\]

B，“符号发射概率”如下矩阵：
\[
\begin{array}{c|lcr}
B & \text{red} & \text{white} \\
\hline
box1 & \frac{1}{2} & \frac{1}{2} \\
box2 & \frac{2}{5} & \frac{3}{5} \\
box3 & \frac{7}{10} & \frac{3}{10}
\end{array}
\]

\(\pi\)，“初始状态的概率分布”如下矩阵
\[
\begin{array}{c|cr}
& \text{box1} & \text{box2} & \text{box3} \\
\hline
\pi & 0.2 & 0.4 & 0.4
\end{array}
\]

2. 试用前向算法计算观测序列概率：{红，白，红}

O = {红， 白， 红}

step 1 初始化

\(a_{红}(box1) = \pi_{box1} b_{box1}(红) = 0.2 \times \frac{1}{2} = 0.1\)

\(a_{红}(box2) = \pi_{box2} b_{box2}(红) = 0.4 \times \frac{2}{5} = 0.16\)

\(a_{红}(box3) = \pi_{box3} b_{box3}(红) = 0.4 \times \frac{7}{10} = 0.28\)

step 2 归纳计算

\[
\begin{align}
a_{红白}(box1) & = \left[ \sum_{i=1}^{3} a_{红}(box_{i})a_{box_{i} box_{1}} \right] b_{box_{1}}(白) \\
& =\left[ a_{红}(box1) \times 0.5 + a_{红}(box2) \times 0.3 + a_{红}(box3) \times 0.2 \right] \times \frac{1}{2} \\
& = 0.077
\end{align}
\]

\[
\begin{align}
a_{红白}(box2) & = \left[ \sum_{i=1}^{3} a_{红}(box_{i})a_{box_{i} box_{2}} \right] b_{box2}(白) \\
& = \left[ a_{红}(box1) \times 0.2 + a_{红}(box2) \times 0.5 + a_{红}(box3) \times 0.3 \right] \times \frac{3}{5} \\
& = 0.1104
\end{align}
\]

\[
\begin{align}
a_{红白}(box3) & = \left[ \sum_{i=1}^{3} a_{红}(box_{i})a_{box_{i} box_{3}} \right] b_{box_{3}}(白) \\
& = \left[ a_{红}(box1) \times 0.3 + a_{红}(box2) \times 0.2 + a_{红}(box3) \times 0.5 \right] \times \frac{3}{10} \\
& = 0.0606
\end{align}
\]

\[
\begin{align}
a_{红白红}(box1) & = \left[ \sum_{i=1}^{3} a_{红白}(box_{i}) a_{box_{i}box1} \right] b_{box1}(红) \\
& = \left[ a_{红白}(box1) \times 0.5 + a_{红白}(box2) \times 0.3 + a_{红白}(box3) \times 0.2 \right] \times \frac{1}{2} \\
& = 0.04187
\end{align}
\]

\[
\begin{align}
a_{红白红}(box2) & = \left[ \sum_{i=1}^{3} a_{红白}(box_{i}) a_{box_{i}box2} \right] b_{box2}(红) \\
& = \left[ a_{红白}(box1) \times 0.2 + a_{红白}(box2) \times 0.5 + a_{红白}(box3) \times 0.3 \right] \times \frac{2}{5} \\
& = 0.035512
\end{align}
\]

\[
\begin{align}
a_{红白红}(box3) & = \left[ \sum_{i=1}^{3} a_{红白}(box_{i}) a_{box_{i}box3} \right] b_{box3}(红) \\
& = \left[ a_{红白}(box1) \times 0.3 + a_{红白}(box2) \times 0.2 + a_{红白}(box3) \times 0.5 \right] \times \frac{7}{10} \\
& = 0.052836
\end{align}
\]

step 3 求和终结

\[
\begin{align}
P(O | \mu) & = \sum_{i=1}^{3}a_{红白红} (box_{i}) \\
& = a_{红白红}(box1) + a_{红白红}(box2) + a_{红白红}(box3) \\
& = 0.04187 + 0.035512 + 0.052836 \\
& = 0.130218
\end{align}
\]

3. 试用维特比算法，求解观测序列{红，白，红}的最优状态序列。 （要求给详细计算过程）

假设从盒子中取球是放回抽样概率模型。

step 1 初始化

\(\delta_{红}(box1) = \pi_{box1}b_{box1}(红) = 0.2 \times \frac{1}{2} = 0.1\)

\(\delta_{红}(box2) = \pi_{box2}b_{box2}(红) = 0.4 \times \frac{2}{5} = 0.16\)

\(\delta_{红}(box3) = \pi_{box3}b_{box3}(红) = 0.4 \times \frac{7}{10} = 0.28\)

\(\varphi_{红}(box1) = 0\)

\(\varphi_{红}(box2) = 0\)

\(\varphi_{红}(box3) = 0\)

step 2 归纳计算 1

\[
\begin{align}
\delta_{红白}(box1) & = max \left[ \delta_{红}(box1)a_{box1box1} , \delta_{红}(box2)a_{box2box1} , \delta_{红}(box3)a_{box3box1} \right] b_{box1}(白) \\
& = 0.28 \times 0.2 \times \frac{1}{2} \\
& = 0.028
\end{align}
\]

\[
\begin{align}
\delta_{红白}(box2) & = max \left[ \delta_{红}(box1)a_{box1box2} , \delta_{红}(box2)a_{box2box2} , \delta_{红}(box3)a_{box3box2} \right] b_{box1}(白) \\
& = 0.28 \times 0.3 \times \frac{3}{5} \\
& = 0.0504
\end{align}
\]

\[
\begin{align}
\delta_{红白}(box3) & = max \left[ \delta_{红}(box1)a_{box1box3} , \delta_{红}(box2)a_{box2box3} , \delta_{红}(box3)a_{box3box3} \right] b_{box3}(白) \\
& = 0.28 \times 0.5 \times \frac{3}{10} \\
& = 0.042
\end{align}
\]

记忆回退路径 1

\[
\begin{align}
\varphi_{红白}(box1) & = argmax \left[ \delta_{红}(box1)a_{box1box1} , \delta_{红}(box2)a_{box2box1} , \delta_{红}(box3)a_{box3box1} \right] b_{box1}(白) \\
& = \frac{1}{2} \delta_{红}(box3)a_{box3box1}
\end{align}
\]

\[
\begin{align}
\varphi_{红白}(box2) & = argmax \left[ \delta_{红}(box1)a_{box1box2} , \delta_{红}(box2)a_{box2box2} , \delta_{红}(box3)a_{box3box2} \right] b_{box2}(白) \\
& = \frac{3}{5} \delta_{红}(box3) a_{box3box2}
\end{align}
\]

\[
\begin{align}
\delta_{红白}(box3) & = argmax \left[ \delta_{红}(box1)a_{box1box3} , \delta_{红}(box2)a_{box2box3} , \delta_{红}(box3)a_{box3box3} \right] b_{box3}(白) \\
& = \frac{3}{10} \delta_{红}(box3)a_{box3box3} \\
\end{align}
\]

归纳计算 2

\[
\begin{align}
\delta_{红白红}(box1) & = max \left[ \delta_{红白}(box1)a_{box1box1} , \delta_{红白}(box2)a_{box2box1} , \delta_{红白}(box3)a_{box3box1} \right] b_{box1}(红) \\
& = 0.0504 \times 0.3 \times \frac{1}{2} \\
& = 0.0756
\end{align}
\]

\[
\begin{align}
\delta_{红白红}(box2) & = max \left[ \delta_{红白}(box1)a_{box1box2} , \delta_{红白}(box2)a_{box2box2} , \delta_{红白}(box3)a_{box3box2} \right] b_{box1}(红) \\
& = 0.0504 \times 0.5 \times \frac{2}{5} \\
& = 0.01008
\end{align}
\]

\[
\begin{align}
\delta_{红白红}(box3) & = max \left[ \delta_{红白}(box1)a_{box1box3} , \delta_{红白}(box2)a_{box2box3} , \delta_{红白}(box3)a_{box3box3} \right] b_{box3}(红) \\
& = 0.042 \times 0.5 \times \frac{7}{10} \\
& = 0.0147
\end{align}
\]

记忆回退路径 2

\[
\begin{align}
\varphi_{红白红}(box1) & = argmax \left[ \delta_{红白}(box1)a_{box1box1} , \delta_{红白}(box2)a_{box2box1} , \delta_{红白}(box3)a_{box3box1} \right] b_{box1}(红) \\
& = \frac{1}{2} \delta_{红}(box2)a_{box2box1}
\end{align}
\]

\[
\begin{align}
\varphi_{红白红}(box2) & = argmax \left[ \delta_{红白}(box1)a_{box1box2} , \delta_{红白}(box2)a_{box2box2} , \delta_{红白}(box3)a_{box3box2} \right] b_{box2}(红) \\
& = \frac{2}{5} \delta_{红白}(box2) a_{box2box2}
\end{align}
\]

\[
\begin{align}
\delta_{红白红}(box3) & = argmax \left[ \delta_{红白}(box1)a_{box1box3} , \delta_{红白}(box2)a_{box2box3} , \delta_{红白}(box3)a_{box3box3} \right] b_{box3}(白) \\
& = \frac{7}{10} \delta_{红白}(box3)a_{box3box3} \\
\end{align}
\]

step 3 终结

\[
\begin{align}
\hat{Q}_{红白红} & = argmax \left[ \delta_{红白红}(box1) , \delta_{红白红}(box2) , \delta_{红白红}(box3) \right] \\
& = \delta_{红白红}(box3)
\end{align}
\]

\[
\begin{align}
\hat{P}(\hat{Q}_{红白红}) & = max \left[ \delta_{红白红}(box1) , \delta_{红白红}(box2) , \delta_{红白红}(box3) \right] \\
& = 0.0147
\end{align}
\]

step 4 路径（状态序列)回溯

\[
\begin{align}
\hat{q}_{红白} = \varphi_{红白红}(\hat{q}_{红白红}) = \varphi_{红白红} \left[ \delta_{红白红}(box3) \right]
\end{align}
\]

\[
\begin{align}
\hat{q}_{红} = \varphi_{红白}(\hat{q}_{红白}) = \varphi_{红白} \left[ \delta_{红白}(box2) \right]
\end{align}
\]

\[
\begin{align}
\hat{q} = \varphi_{红}(\hat{q}_{红}) = \varphi_{红} \left[ \delta_{红}(box3) \right]
\end{align}
\]