SDSC6007 课程 3-Tutorial与隐马尔可夫模型

#sdsc6007

English / 中文

Tutorial 1

问题设定

• 动态系统: $x_{k+1} = x_k + u_k + w_k$, $k = 0,1,2,3$

• 初始状态: $x_0 = 5$

• 成本函数: $\sum_{k=0}^{3}(x_k^2 + u_k^2)$

• 状态空间: $S_k = \{0,1,2,3,4,5\}$

• 控制约束: $U_k(x_k) = \{u | 0 \leq x_k + u \leq 5, u \in \mathbb{Z}\}$

• 随机干扰:

  • 如果 $0 < x_k + u_k < 5$: $w_k = \begin{cases} -1 & \text{概率} \frac{1}{2} \\ 1 & \text{概率} \frac{1}{2} \end{cases}$
  • 如果 $x_k + u_k = 0$ 或 $x_k + u_k = 5$: $w_k = 0$ (概率1)

动态规划递推公式

定义价值函数 $V_k(x_k)$ 为从状态 $x_k$ 在时刻 $k$ 开始的最小期望成本。

Bellman方程:

$$V_k(x_k) = \min_{u_k \in U_k(x_k)} \left\{ x_k^2 + u_k^2 + E[V_{k+1}(x_k + u_k + w_k)] \right\}$$

边界条件: $V_4(x_4) = 0$ (问题结束)

步骤1: 时刻 k=3 (最后一步)

$$V_3(x_3) = x_3^2 + \min_{u_3 \in U_3(x_3)} u_3^2$$

对每个状态计算:

$x_3$	$U_3(x_3)$	最优 $u_3^*$	$V_3(x_3)$
0	{0,1,2,3,4,5}	0	$0^2 + 0^2 = 0$
1	{-1,0,1,2,3,4}	0	$1^2 + 0^2 = 1$
2	{-2,-1,0,1,2,3}	0	$2^2 + 0^2 = 4$
3	{-3,-2,-1,0,1,2}	0	$3^2 + 0^2 = 9$
4	{-4,-3,-2,-1,0,1}	0	$4^2 + 0^2 = 16$
5	{-5,-4,-3,-2,-1,0}	0	$5^2 + 0^2 = 25$

结果: $u_3^*(x_3) = 0$ 对所有 $x_3$

步骤2: 时刻 k=2

$V_2(x_2) = \min_{u_2 \in U_2(x_2)} \left\{ x_2^2 + u_2^2 + E[V_3(x_2 + u_2 + w_2)] \right\}$

期望值计算:

• 如果 $0 < x_2 + u_2 < 5$: $E[V_3] = \frac{1}{2}V_3(x_2 + u_2 - 1) + \frac{1}{2}V_3(x_2 + u_2 + 1)$

• 如果 $x_2 + u_2 = 0$ 或 $x_2 + u_2 = 5$: $E[V_3] = V_3(x_2 + u_2)$

$x_2 = 0$:

$u_2$	$x_2+u_2$	$E[V_3]$	总成本 $0^2 + u_2^2 + E[V_3]$
0	0	$V_3(0) = 0$	$0 + 0 + 0 = 0$
1	1	$\frac{1}{2}(0) + \frac{1}{2}(4) = 2$	$0 + 1 + 2 = 3$
2	2	$\frac{1}{2}(1) + \frac{1}{2}(9) = 5$	$0 + 4 + 5 = 9$
3	3	$\frac{1}{2}(4) + \frac{1}{2}(16) = 10$	$0 + 9 + 10 = 19$
4	4	$\frac{1}{2}(9) + \frac{1}{2}(25) = 17$	$0 + 16 + 17 = 33$
5	5	$V_3(5) = 25$	$0 + 25 + 25 = 50$

$V_2(0) = 0$, $u_2^*(0) = 0$

$x_2 = 1$:

$u_2$	$x_2+u_2$	$E[V_3]$	总成本 $1^2 + u_2^2 + E[V_3]$
-1	0	$V_3(0) = 0$	$1 + 1 + 0 = 2$
0	1	$\frac{1}{2}(0) + \frac{1}{2}(4) = 2$	$1 + 0 + 2 = 3$
1	2	$\frac{1}{2}(1) + \frac{1}{2}(9) = 5$	$1 + 1 + 5 = 7$
2	3	$\frac{1}{2}(4) + \frac{1}{2}(16) = 10$	$1 + 4 + 10 = 15$
3	4	$\frac{1}{2}(9) + \frac{1}{2}(25) = 17$	$1 + 9 + 17 = 27$
4	5	$V_3(5) = 25$	$1 + 16 + 25 = 42$

$V_2(1) = 2$, $u_2^*(1) = -1$

继续计算其他状态:

$x_2 = 2$: $V_2(2) = 7$, $u_2^*(2) = -1$

$x_2 = 3$: $V_2(3) = 15$, $u_2^*(3) = -2$ (或 $-1$)

$x_2 = 4$: $V_2(4) = 25$, $u_2^*(4) = -2$

$x_2 = 5$: $V_2(5) = 39$, $u_2^*(5) = -3$ (或 $-2$，都得到相同成本)

步骤3: 时刻 k=1

使用已计算的 $V_2$ 来计算 $V_1(x_1)$。

$x_1 = 0$:

$u_1$	$x_1+u_1$	$E[V_2]$	总成本 $0^2 + u_1^2 + E[V_2]$
0	0	$V_2(0) = 0$	$0 + 0 + 0 = 0$
1	1	$\frac{1}{2}V_2(0) + \frac{1}{2}V_2(2) = \frac{1}{2}(0) + \frac{1}{2}(7) = 3.5$	$0 + 1 + 3.5 = 4.5$

$V_1(0) = 0$, $u_1^*(0) = 0$

$x_1 = 1$:

$u_1$	$x_1+u_1$	$E[V_2]$	总成本
-1	0	$V_2(0) = 0$	$1 + 1 + 0 = 2$
0	1	$\frac{1}{2}(0) + \frac{1}{2}(7) = 3.5$	$1 + 0 + 3.5 = 4.5$

$V_1(1) = 2$, $u_1^*(1) = -1$

$x_1 = 2$:

$u_1$	$x_1+u_1$	$E[V_2]$	总成本
-2	0	$V_2(0) = 0$	$4 + 4 + 0 = 8$
-1	1	$\frac{1}{2}(0) + \frac{1}{2}(7) = 3.5$	$4 + 1 + 3.5 = 8.5$

$V_1(2) = 8$, $u_1^*(2) = -2$

$x_1 = 3$:

$u_1$	$x_1+u_1$	$E[V_2]$	总成本
-3	0	$V_2(0) = 0$	$9 + 9 + 0 = 18$
-2	1	$\frac{1}{2}(0) + \frac{1}{2}(7) = 3.5$	$9 + 4 + 3.5 = 16.5$
-1	2	$\frac{1}{2}(2) + \frac{1}{2}(15) = 8.5$	$9 + 1 + 8.5 = 18.5$

$V_1(3) = 16.5$, $u_1^*(3) = -2$

$x_1 = 4$:

计算后得到 $V_1(4) = 28.5$, $u_1^*(4) = -3$

$x_1 = 5$:

计算后得到 $V_1(5) = 42.5$, $u_1^*(5) = -3$

时刻1的完整价值函数:

$x_1$	$V_1(x_1)$	$u_1^*(x_1)$
0	0	0
1	2	-1
2	8	-2
3	16.5	-2
4	28.5	-3
5	42.5	-3

步骤4: 时刻 k=0

对于初始状态 $x_0 = 5$，计算 $V_0(5)$:

$V_0(5) = \min_{u_0 \in U_0(5)} \left\{ 25 + u_0^2 + E[V_1(5 + u_0 + w_0)] \right\}$

$U_0(5) = \{-5,-4,-3,-2,-1,0\}$

$u_0$	$x_0+u_0$	$E[V_1]$	总成本
-5	0	$V_1(0) = 0$	$25 + 25 + 0 = 50$
-4	1	$\frac{1}{2}V_1(0) + \frac{1}{2}V_1(2) = \frac{1}{2}(0) + \frac{1}{2}(8) = 4$	$25 + 16 + 4 = 45$
-3	2	$\frac{1}{2}V_1(1) + \frac{1}{2}V_1(3) = \frac{1}{2}(2) + \frac{1}{2}(16.5) = 9.25$	$25 + 9 + 9.25 = 43.25$
-2	3	$\frac{1}{2}V_1(2) + \frac{1}{2}V_1(4) = \frac{1}{2}(8) + \frac{1}{2}(28.5) = 18.25$	$25 + 4 + 18.25 = 47.25$
-1	4	$\frac{1}{2}V_1(3) + \frac{1}{2}V_1(5) = \frac{1}{2}(16.5) + \frac{1}{2}(42.5) = 29.5$	$25 + 1 + 29.5 = 55.5$
0	5	$V_1(5) = 42.5$	$25 + 0 + 42.5 = 67.5$

结果: $V_0(5) = 43.25$, $u_0^*(5) = -3$

最优策略总结

从初始状态 $x_0 = 5$ 开始的最优策略:

时刻	状态	最优控制	说明
$k=0$	$x_0 = 5$	$u_0^* = -3$	将状态向2方向引导
$k=1$	依赖于 $w_0$	查表$u_1^*$	从价值函数表查找
$k=2$	依赖于 $w_0,w_1$	查表$u_2^*$	从价值函数表查找
$k=3$	依赖于路径	$u_3^* = 0$	无论什么状态都选0

最小期望总成本: $43.25$

策略特点:

• 倾向于将状态引导向较小值（因为状态成本 $x_k^2$ 在0处最小）

• 需要权衡控制成本和未来期望成本

• 随机干扰使得策略需要考虑所有可能的未来状态

---

隐马尔可夫模型 (HMM)

模型描述

• 一个平稳的有限状态马尔可夫链，状态间转移概率为 $p_{ij}$。

• 状态是隐藏的（无法直接观测）。初始状态 $x_0$ 为 $i$ 的概率是 $\pi_i$。

• 每次状态转移后，观测到一个值 $z$。给定从状态 $i$ 转移到状态 $j$，观测到 $z$ 的概率为 $r(z; i, j)$。

• 观测值相互独立。

• 转移概率 $p_{ij}$ 和观测概率 $r(z; i, j)$ 被假设为相互独立。

符号解释与模型理解

• $p_{ij}$: 从状态 $i$ 转移到状态 $j$ 的概率（如天气从"晴"转"雨"的概率）

• $\pi_i$: 系统初始状态为 $i$ 的概率（如第一天是"晴"的概率）

• $r(z; i, j)$: 在 $i→j$ 转移时观测到 $z$ 的概率（如"晴转雨"时观测到"湿度高"的概率）

• 独立性假设: 观测值 $z_k$ 仅取决于当前状态转移 $(x_{k-1},x_k)$，与历史状态和观测无关

目标

给定观测序列 $Z_N = \{z_1, \dots, z_N\}$，估计最可能的状态序列 $\hat{X}_N = \{\hat{x}_0, \dots, \hat{x}_N\}$。

方法

为估计 $\hat{X}_N$，最大化条件概率 $P(X_N \mid Z_N)$。由于：

$$P(X_N \mid Z_N) = \frac{P(X_N, Z_N)}{P(Z_N)}$$

最大化 $P(X_N \mid Z_N)$ 等价于最大化联合概率 $P(X_N, Z_N)$，因为 $P(Z_N)$ 对于给定观测序列是常数。

联合概率推导

状态序列 $X_N = \{x_0, x_1, \dots, x_N\}$ 和观测序列 $Z_N = \{z_1, \dots, z_N\}$ 的联合概率 $P(X_N, Z_N)$ 推导如下：

$$P(X_N, Z_N) = P(x_0, x_1, \dots, x_N, z_1, \dots, z_N)$$

利用链式法则和独立性假设：

$$\begin{align*} = & \pi_{x_0} P(x_1, \dots, x_N, z_1, \dots, z_N \mid x_0) \\ = & \pi_{x_0} p_{x_0 x_1} r(z_1; x_0, x_1) P(x_2, \dots, x_N, z_2, \dots, z_N \mid x_0, x_1, z_1) \end{align*}$$

基于马尔可夫性质和观测独立性，递归简化得：

$$P(X_N, Z_N) = \pi_{x_0} \prod_{k=1}^N p_{x_{k-1} x_k} r(z_k; x_{k-1}, x_k)$$

推导过程详解

1. 链式分解:

   $$P(X_N, Z_N) = P(x_0) \prod_{k=1}^N P(x_k, z_k | x_{0:k-1}, z_{1:k-1})$$

2. 马尔可夫性应用:
   未来状态仅依赖当前状态：

   $$P(x_k | x_{0:k-1}) = P(x_k | x_{k-1})$$

3. 观测独立性:
   观测 $z_k$ 仅由当前转移决定：

   $$P(z_k | x_{0:k}, z_{1:k-1}) = r(z_k; x_{k-1}, x_k)$$

4. 联合概率:

   $$P(x_k, z_k | x_{0:k-1}, z_{1:k-1}) = p_{x_{k-1}x_k} \cdot r(z_k; x_{k-1}, x_k)$$

5. 最终形式:
   递归代入得 $\pi_{x_0} \prod_{k=1}^N p_{x_{k-1}x_k} r(z_k; x_{k-1}, x_k)$

解释:

• $\pi_{x_0}$: 起始状态 $x_0$ 的概率。
• $p_{x_{k-1} x_k}$: 在步骤 $k$ 时，从状态 $x_{k-1}$ 转移到 $x_k$ 的概率。
• $r(z_k; x_{k-1}, x_k)$: 给定从 $x_{k-1}$ 到 $x_k$ 的转移，观测到 $z_k$ 的概率。
• 乘积 $\prod_{k=1}^N$ 捕捉了状态转移和观测的序列，利用独立性将联合概率分解为乘积形式。

等价优化问题

最大化 $P(X_N, Z_N)$ 等价于最小化负对数似然：

$$\min\left( -\log(\pi_{x_0}) - \sum_{k=1}^N \log\left( p_{x_{k-1} x_k} r(z_k; x_{k-1}, x_k) \right) \right)$$

负对数转换原理

1. 单调性原理:

   • $\log$ 函数单调递增，最大化 $f(x)$ 等价于最大化 $\log f(x)$
   • 最小化 $-\log f(x)$ 等价于最大化 $f(x)$

2. 乘积转求和:

   $$\arg\max \prod p_i = \arg\min \left( -\sum \log p_i \right)$$

3. 数值稳定性:

   • 概率乘积易导致浮点数下溢
   • 对数求和避免小数值相乘

4. 优化优势:

   • 求和形式适合动态规划
   • 可视为"路径成本"的累加

注意: 此转换将概率乘积转化为对数项的和，便于优化（例如，使用动态规划算法如维特比算法）。最小化该和可找到最能解释观测的状态序列。

将寻找最可能状态序列（例如在隐马尔可夫模型中）的问题转化为带正权值的最短路径问题，可通过以下图结构实现：

1. 添加虚拟节点：

   • 添加源节点 s与 t。

2. 初始状态弧：

   • 创建从 $s$ 到初始状态 $x_0$ 的弧。

   • 赋予其长度：

     $$\ell(s, x_0) = -\log(\pi_{x_0})$$

     其中 $\pi_{x_0}$ 是状态 $x_0$ 的初始概率。负对数将最大化初始概率转化为最小化正成本。

3. 状态转移弧：

   • 对每个时间步 $k$ $(k = 1, ..., N)$ 上可能的有效状态转移 $(x_{k - 1}, x_k)$：
     • 创建从状态 $x_{k - 1}$ 到状态 $x_k$ 的弧。
     • 赋予其长度：

       $$\ell(x_{k-1}, x_k) = -\log \left( p_{x_{k-1} x_k} \cdot r(z_k; x_{k-1}, x_k) \right)$$

       其中 $p_{x_{k-1} x_k}$ 是从状态 $x_{k - 1}$ 转移到 $xₖ$ 的概率，$r(z_k; x_{k - 1}, x_k)$ 是在给定 $x_{k - 1}$ 到 $x_k$ 转移下观测到 $z_k$ 的概率（似然）。负对数将最大化转移概率与发射概率的乘积转化为最小化正成本。

   • 注意： 若转移概率 $p_{x_{k - 1} x_k} = 0$，则不创建对应弧。

4. 终止状态弧：

   • 创建从每个可能的终止状态 $x_N$ 到汇节点 $t$ 的弧。
   • 赋予其长度：

     $$\ell(x_N, t) = 0$$

     此设定使在任何有效终止状态 $x_N$ 结束路径的成本为零。

求解： 在此构造的图中，从源节点 s 到汇节点 t 的最短路径即对应最可能的状态序列。图中所有弧长均为非负（除终止弧为零外，其余为正）。

图结构等价性证明

1. 路径成本计算:

   • 路径总成本 = $\ell(s,x_0) + \sum_{k=1}^N \ell(x_{k-1},x_k) + \ell(x_N,t)$

   $$= -\log\pi_{x_0} - \sum_{k=1}^N \log(p_{x_{k-1}x_k}r_k) + 0$$

   $$= -\log\left( \pi_{x_0} \prod_{k=1}^N p_{x_{k-1}x_k}r_k \right)$$

2. 等价关系:

   $$\min\left(\text{路径成本}\right) \iff \min\left(-\log P(X_N,Z_N)\right) \iff \max\left(P(X_N,Z_N)\right)$$

3. 非负权重保证:

   • 因 $0 < p_{ij}, r \leq 1$，故 $-\log(\cdot) \geq 0$
   • 满足Dijkstra等最短路径算法要求

4. 动态规划优势:

   • 维特比算法复杂度 $O(N|S|^2)$
   • 避免穷举 $|S|^N$ 种可能路径

前向DP算法（维特比算法）

核心公式

1. 初始状态概率

$$D_0(x_0) = -\log(\pi_{x_0})$$

• 意义：在时间步 $t=0$ 时，状态 $x_0$ 的负对数初始概率。

• $\pi_{x_0}$：初始状态 $x_0$ 的概率。

• 负对数转换：将概率最大化问题转化为最小化代价问题。

2. 递推关系

$$D_{k+1}(x_{k+1}) = \min_{x_k} \left[ D_k(x_k) - \log P(x_{k+1} \mid x_k) - \log P(z_k \mid x_k) \right]$$

• 意义：计算在时间步 $t=k+1$ 到达状态 $x_{k+1}$ 的最小累积代价。

• $D_k(x_k)$：前一状态 $x_k$ 的最小累积代价。

• $P(x_{k+1} \mid x_k)$：状态转移概率（从 $x_k$ 到 $x_{k+1}$）。

• $P(z_k \mid x_k)$：观测概率（在状态 $x_k$ 下观测到 $z_k$）。

• 最小化操作：遍历所有可能的前一状态 $x_k$，选择最优路径。

3. 回溯最优路径

$$x_k^* = \argmin_{x_k} \left[ D_k(x_k) - \log P(x_{k+1}^* \mid x_k) - \log P(z_k \mid x_k) \right]$$

• 意义：从最终状态反向回溯，确定全局最优状态序列 $\{x_0^*, x_1^*, \dots, x_T^*\}$。

• $x_{k+1}^*$：已确定的后一最优状态。

补充说明

• 维特比算法本质：动态规划求解隐马尔可夫模型（HMM）的最可能状态序列（即最大后验概率路径）。
• 负对数转换目的：将概率乘积的极大化问题转化为对数和的极小化问题，避免浮点数下溢。
• 复杂度：$O(T \cdot N^2)$（$T$ 为时间步数，$N$ 为状态数）。

隐马尔可夫模型示例：卷积编码与解码

背景故事

杨博士将祖母的食谱存储为二进制序列（如 $\{0, 1, 0, 0, 1, \ldots\}$），并使用卷积编码保护数据，防止他人（如 6007🧑‍🏫）窃取。数据通过噪声信道传输给 曾博士，接收序列 $\{z_k\}$ 与发送序列 $\{y_k\}$ 不同。目标是从 $\{z_k\}$ 解码恢复原始序列 $\{w_k\}$。

卷积编码过程

• 输入：源二进制序列 $\{w_1, w_2, \ldots\}$，其中 $w_k \in \{0, 1\}$。

• 输出：编码序列 $\{y_1, y_2, \ldots\}$，每个 $y_k$ 是 $n$ 维二进制向量（码字）。

• 状态方程（使用模 2 运算）：

  $$y_k = C x_{k-1} + d w_k, \quad k = 1, 2, \ldots$$

  $$x_k = A x_{k-1} + b w_k, \quad k = 1, 2, \ldots$$

  其中：

  • $x_k$ 是隐藏状态向量（维度 $m \times 1$），初始状态 $x_0$ 给定（如 $x_0 = \begin{bmatrix} 0 \\ 0 \end{bmatrix}$）。
  • $A$ 是状态转移矩阵（$m \times m$），$C$ 是输出矩阵（$n \times m$），$b$ 和 $d$ 是权重向量（维度分别为 $m \times 1$ 和 $n \times 1$）。
  • 参数设置：

    $$C = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{bmatrix}, \quad A = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}, \quad d = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \quad b = \begin{bmatrix} 0 \\ 1 \end{bmatrix}, \quad x_0 = \begin{bmatrix} 0 \\ 0 \end{bmatrix}$$

    说明：$y_k$ 是 3 维向量（$n=3$），$x_k$ 是 2 维向量（$m=2$）。模 2 运算确保所有值为二进制（0 或 1）。$d$ 和 $b$ 的维度需匹配输出和状态维度，此处 $d$ 为 3x1，$b$ 为 2x1。

示例计算

• 输入序列：$\{w_1, w_2, w_3, w_4\} = \{1, 0, 0, 1\}$。

• 状态和输出序列计算：

  • $k=1$：$x_1 = A x_0 + b w_1 = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 0 \\ 0 \end{bmatrix} + \begin{bmatrix} 0 \\ 1 \end{bmatrix} \cdot 1 = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$，$y_1 = C x_0 + d w_1 = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 0 \\ 0 \end{bmatrix} + \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} \cdot 1 = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}$。
  • $k=2$：$x_2 = A x_1 + b w_2 = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 0 \\ 1 \end{bmatrix} + \begin{bmatrix} 0 \\ 1 \end{bmatrix} \cdot 0 = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$，$y_2 = C x_1 + d w_2 = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 0 \\ 1 \end{bmatrix} + \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} \cdot 0 = \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix}$。
  • $k=3$：$x_3 = A x_2 + b w_3 = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 1 \end{bmatrix} + \begin{bmatrix} 0 \\ 1 \end{bmatrix} \cdot 0 = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$，$y_3 = C x_2 + d w_3 = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 1 \end{bmatrix} + \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} \cdot 0 = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}$。
  • $k=4$：$x_4 = A x_3 + b w_4 = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \end{bmatrix} + \begin{bmatrix} 0 \\ 1 \end{bmatrix} \cdot 1 = \begin{bmatrix} 0 \\ 1 \end{bmatrix} + \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}$（模 2），$y_4 = C x_3 + d w_4 = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \end{bmatrix} + \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} \cdot 1 = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} + \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix}$（模 2）。

• 结果：

  • 状态序列：$\{x_0, x_1, x_2, x_3, x_4\} = \left\{ \begin{bmatrix} 0 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ 0 \end{bmatrix}, \begin{bmatrix} 0 \\ 0 \end{bmatrix} \right\}$（或 $\{00, 01, 11, 10, 00\}$）。
  • 输出序列：$\{y_1, y_2, y_3, y_4\} = \left\{ \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} \right\}$（或 $\{111, 011, 111, 011\}$）。

噪声信道与概率模型

• 传输过程：编码序列 $\{y_k\}$ 通过噪声信道，接收序列为 $\{z_k\}$（$z_k$ 也是二进制向量）。

• 错误模型：给定条件概率 $p(z_k | y_k)$，表示接收 $z_k$ 给定发送 $y_k$ 的概率。

• 独立性假设：错误独立，联合概率为：

  $$P(Z_N | Y_N) = \prod_{k=1}^N p(z_k | y_k)$$

  说明：$Z_N = \{z_1, \ldots, z_N\}$，$Y_N = \{y_1, \ldots, y_N\}$。该模型假设每个码字的错误发生独立。

错误模型的符号解释、原理推导和实际意义

• 符号解释：

  • $z_k$：接收到的码字（维度与 $y_k$ 相同），可能因噪声而错误（如 $y_k = 111$ 但 $z_k = 101$）。
  • $p(z_k | y_k)$：条件概率密度函数，表示给定发送 $y_k$ 时接收到 $z_k$ 的概率（例如，如果信道有错误率 $\epsilon$，则 $p(z_k | y_k)$ 可能定义为 $\epsilon$ 当 $z_k \neq y_k$，$1-\epsilon$ 当 $z_k = y_k$）。实际意义：量化传输错误的可能性（如比特翻转概率）。

• 联合概率的独立性原理推导：

  • 推导：假设信道错误在每个时间步 $k$ 独立发生（即噪声不影响相邻传输）。因此，联合概率 $P(Z_N | Y_N)$ 是边缘概率的乘积：$P(Z_N | Y_N) = P(z_1 | y_1) P(z_2 | y_2) \cdots P(z_N | y_N) = \prod_{k=1}^N p(z_k | y_k)$。这源于概率论中的独立性定义（如果事件独立，联合概率为乘积）。
  • 实际意义：简化模型计算（如解码时只需处理单个码字的错误），适用于许多实际信道（如 AWGN 信道在低相关噪声下）。
  • 举例：如果 $N=2$，$p(z_1 | y_1) = 0.9$（正确接收），$p(z_2 | y_2) = 0.1$（错误），则 $P(Z_2 | Y_2) = 0.9 \times 0.1 = 0.09$。比喻：就像多个独立抛硬币，每个结果不影响其他。

解码问题公式化

• 目标：最小化负对数似然，以恢复最可能的序列 $\{y_k\}$：

  $$\min \sum_{k=1}^N -\log p(z_k | y_k)$$

  其中优化变量是所有可能的 $\{y_1, \ldots, y_N\}$。

• 依赖隐藏状态：由于 $y_k = C x_{k-1} + d w_k$，解码需同时找到状态序列 $\{x_0, \ldots, x_N\}$。

  说明：这等价于隐马尔可夫模型（HMM）的解码问题，状态为 $x_k$，观测为 $z_k$。动态规划方法（如 Viterbi 算法）可用于高效求解，通过状态转移优化序列。

解码目标的原理推导、符号解释和等价于 HMM 的推导

• 最小化负对数似然的原理推导：

  • 推导：目标是最大化观测序列 $Z_N$ 的似然概率 $P(Z_N | Y_N)$。由于似然是乘积形式（$P(Z_N | Y_N) = \prod_{k=1}^N p(z_k | y_k)$），最大化似然等价于最大化对数似然（因为对数函数单调递增）：

    $$\max \log P(Z_N | Y_N) = \max \sum_{k=1}^N \log p(z_k | y_k)$$

    等价于最小化负对数似然：$\min \sum_{k=1}^N -\log p(z_k | y_k)$。实际意义：将概率最大化转化为数值稳定的优化问题（负对数似然常作为损失函数）。
  • 符号解释：$-\log p(z_k | y_k)$ 可视为"错误代价"，值越小表示 $y_k$ 与 $z_k$ 越匹配（如 $p(z_k | y_k)$ 高时，$-\log p$ 低）。
  • 举例：如果 $p(z_k | y_k) = 0.9$，则 $-\log p \approx 0.105$；如果 $p = 0.1$，则 $-\log p \approx 2.3$。最小化和相当于找到最匹配的序列。

• 等价于隐马尔可夫模型（HMM）的推导：

  • 推导：在 HMM 中，解码问题涉及找到最可能的状态序列给定观测序列。这里：
    • 隐藏状态：$x_k$（定义状态转移 $x_k = A x_{k-1} + b w_k$）。
    • 观测：$z_k$（给定状态或输出，但 $y_k$ 依赖于 $x_{k-1}$ 和 $w_k$）。
      由于 $y_k$ 是 $x_{k-1}$ 和 $w_k$ 的函数，且 $w_k$ 隐含在状态转移中，观测概率 $p(z_k | y_k)$ 可映射到 HMM 的发射概率 $p(z_k | x_k)$（通过 $y_k$ 链接）。优化目标 $\min \sum -\log p(z_k | y_k)$ 对应 HMM 的 Viterbi 算法路径代价。实际意义：允许使用高效算法（如 Viterbi）处理长序列。
  • 比喻：就像在迷宫中找最短路径（状态序列），每个步骤的"代价"由观测匹配度决定。

---

卷积编码状态转移图（Mermaid）

图注：

• 节点表示状态（如 “00” 表示 $x_k = \begin{bmatrix}0\\0\end{bmatrix}$）

• 箭头标签格式：输入/输出（如 “w=1/y=111”）

• 基于示例参数计算的状态转移关系

• 虚线框表示可能的初始状态

Viterbi算法解码过程（Mermaid）

图注：

• 每个节点表示时间步k的状态和累积代价

• δ(z_k, y_k) = -log p(z_k|y_k) 表示步骤代价

• 粗线框表示当前最优路径（需根据实际z_k计算）

• 算法原理：保留到每个状态的最小代价路径，逐步扩展

---

最短路算法

标签校正法 (Label Correcting Methods)

动机

• 动态规划 (DP) 算法需计算每个状态 $x_k$ 在每个时段 $k$ 的成本函数 $J_k$，计算所有节点和弧的代价高昂。

• 核心思想：通过排除不相关节点来优化计算 → 最短路径算法。

关键点：当状态空间庞大时，DP 计算量过大，需更高效的路径搜索方法。

---

设置

• 起点 (Origin)：节点 $s$

• 终点 (Destination)：节点 $t$

• 子节点 (Child)：若存在弧 $(i,j)$，则节点 $j$ 是节点 $i$ 的子节点

• 假设：所有弧长 $a_{ij} \geq 0$（非负权重）

---

核心思路

• 为每个节点 $i$ 维护标签 $d_i$，记录从起点 $s$ 到 $i$ 的当前最短路径长度。

• 算法执行中 $d_i$ 动态递减。

• 当 $d_i$ 更新时，检查其子节点 $j$ 是否需要修正。

• 当终点标签 $d_t$（记为 UPPER）等于真实最短路径长度时，问题得解。

直观理解：UPPER 是当前找到的 $s$ 到 $t$ 的最短路径上界，算法通过不断修正标签降低此上界。

---

算法步骤

1. 初始化：

   • $d_s \leftarrow 0$
   • $d_i \leftarrow \infty, \forall i \neq s$
   • OPEN 集合初始仅含 $s$
   • UPPER $\leftarrow \infty$

2. 迭代更新：

   • 从 OPEN 中移除一个节点 $i$
   • 对 $i$ 的每个子节点 $j$：
     • 若 $d_i + a_{ij} < \min\{d_j, \text{UPPER}\}$：
       • $d_j \leftarrow d_i + a_{ij}$
       • 设置 $i$ 为 $j$ 的父节点
       • 若 $j \neq t$ 且 $j \notin \text{OPEN}$，将 $j$ 加入 OPEN
       • 若 $j = t$，更新 $\text{UPPER} \leftarrow d_t$

3. 终止条件：OPEN 为空时停止；否则重复步骤 2。

---

注意事项：

• OPEN 集合：存储待检查节点，确保仅需更新受影响节点。

• 非负权重：保证算法正确性（无负权环）。

• 效率提升：通过 UPPER 剪枝，避免无效计算。

---

标签校正法：正确性证明

命题

若存在从起点 $s$ 到终点 $t$ 的路径，算法终止时 UPPER 等于最短路径长度；否则终止时 UPPER = ∞。

---

证明

1. 算法必然终止

• 关键观察：

  • 节点 $j$ 每次加入 OPEN 时，$d_j$ 严格递减且始终表示某条 $s→j$ 路径的长度。
  • 设 $d_j^0$ 为 $j$ 首次加入 OPEN 时的 $d_j$ 值（有限）。

• 非负权重保证：

  $$\text{路径数有限} + \text{无负权环} \implies d_j \text{ 的下降次数有限}$$

• 结论：OPEN 集合终将为空，算法终止。

核心：非负弧长确保路径长度有下界，标签值 $d_j$ 不会无限下降。

---

2. 无路径情况：UPPER = ∞

• 反证法：

  • 假设存在弧 $(i,t)$（即 $t$ 有前驱节点 $i$）。
  • 若 $i$ 曾进入 OPEN → 存在 $s→i$ 路径 → 存在 $s→t$ 路径（矛盾）。

• 推论：

  • $i$ 无法进入 OPEN → $d_t$ 不会被更新
  • 由初始化 $d_t = \infty$ 得 $\text{UPPER} = \infty$

---

3. 有路径情况：UPPER 等于最短路径长度

设最短路径 $P^* = (s, j_1, ..., j_k, t)$，长度为 $d^*$。

• 子路径最优性：

  $$P^* \text{ 的任意子路径 } (s, j_1, ..., j_m) \text{ 也是 } s→j_m \text{ 的最短路径}$$

• 反证假设：若算法终止时 $\text{UPPER} > d^*$，则全程有：

  $$\text{UPPER} > \text{子路径 } (s, j_1, ..., j_m) \text{ 的长度}, \quad \forall m=1,...,k$$

• 递推矛盾：

  1. 节点 $j_k$ 无法以最优 $d_{j_k}$ 进入 OPEN（否则 $d_{j_k} + a_{j_kt} < \text{UPPER}$ 会更新 $\text{UPPER} = d^*$）
  2. 同理，$j_{k-1}$ 无法以最优 $d_{j_{k-1}}$ 进入 OPEN
  3. 递推至 $j_1$：
     • 但初始化时 $j_1$ 会以 $d_{j_1} = a_{s j_1}$（即 $s→j_1$ 最优值）加入 OPEN
     • 矛盾！

结论：$\text{UPPER}$ 必收敛至 $d^*$。

标签校正法的具体实现策略

常用策略对比

1. 广度优先搜索 (BFS) / Bellman-Ford 方法

• 队列策略：先进先出 (FIFO)

• 操作规则：

  • 从 OPEN 顶部移除节点
  • 新节点加入 OPEN 底部

• 特点：

  • 适用于含负权边的图（但当前场景要求非负权重）
  • 时间复杂度：$O(|V| \cdot |E|)$

---

2. 深度优先搜索 (DFS)

• 队列策略：后进先出 (LIFO)

• 操作规则：

  • 从 OPEN 顶部移除节点
  • 新节点加入 OPEN 顶部

• 特点：

  • 内存占用较低（不存储所有层级节点）
  • 可能优先探索长路径，效率不稳定

---

3. 最佳优先搜索 (Dijkstra 算法)

• 选择策略：选取 OPEN 中标签最小的节点

  $$\text{移除节点 } i \quad \text{其中} \quad d_i = \min_{j \in \text{OPEN}} d_j$$

• 特点：

  • 关键性质：每个节点最多进入 OPEN 一次
  • 开销：需维护最小堆，每次操作 $O(\log n)$
  • 时间复杂度：$O(|E| + |V| \log |V|)$（非负权重下最优）

优势：非负权重图中效率最高

---

4. 混合优化策略

(1) 小标签优先 (SLF)

• 操作规则：

  • 从 OPEN 顶部移除节点
  • 新节点 $i$ 加入位置取决于：
    • 若 $d_i \leq d_{\text{top}}$（顶部节点标签），加入顶部
    • 否则加入底部

• 目标：近似 Dijkstra 效果，但避免排序开销

(2) 大标签后移 (LLL)

• 增强策略（常与 SLF 联用）：

  1. 计算 OPEN 中标签平均值 $\bar{d} = \frac{1}{|\text{OPEN}|} \sum_{j} d_j$
  2. 若顶部节点标签 $d_{\text{top}} > \bar{d}$，则将其移至底部
  3. 重复直至顶部节点标签 $\leq \bar{d}$

• 目标：延迟处理大标签节点，提升收敛速度

---

策略选择总结

策略	时间复杂度	优势	适用场景
BFS (Bellman-Ford)	$O(|V|{\cdot}|E|)$	处理负权边	稀疏图或含负权图
DFS	不稳定	低内存消耗	深度路径优先的探索
Dijkstra	$O(|E|{+}|V|\log|V|)$	非负权重最优解	非负权重图的标准选择
SLF+LLL	接近 Dijkstra	低开销近似最优解	大规模图的高效启发式方案