本文内容主要来自M. Nikos Paragios和M. Pawan Kumar的课程《Discrete Inference & Learning in Artificial Vision》的第2节“Reparameterization and dynamic programming”。
基本模型
一、马尔可夫随机场
图$\mathbf G$由顶点集$\mathbf V$以及连接顶点的边集$\mathbf E$构成。计算机视觉中最流行的模型之一是马尔可夫随机场（MRF，markov random field）。在MRF中，图的顶点用随机变量$\mathbf X$代替，边表示随机变量间的关系。
在MRF中，随机变量表示系统输出。在图像分割中，随机变量表示图像分割的标签。边连接的顶点表示相邻的随机变量。随机变量$X_p$的取值或标签$x_p$来自有限离散集合$\mathbf L=\{l_1,l_2,\ldots,l_h\}$。$\mathbf X$表示取值未知的随机变量，$\mathbf x$表示它的某种赋值（某实例的特定输出）。对$n$个随机变量，每个变量$h$种取值，共$h^n$种赋值方式。
MRF取得特定输出的概率为$P(\mathbf x)$。MRF假定$P(\mathbf x)$具有马尔可夫属性。$X_p$有条件独立于其所有邻居$X_q$。根据Hammersley-Clifford定理，概率$P(\mathbf x)$可以分解为团的势（clique potential）。势为非负实数，$x_1$和$x_2$的势为$\Psi_{12}(x_1, x_2)$，$x_5$和$x_6$的势为$\Psi_{56}(x_5, x_6)$。概率$P(\mathbf x)$与$\prod_{(p,q)}\Psi_{pq}(x_p,x_q)$成比例。
$\mathbf d$表示观测数据，数据可以是MRI扫描片这样的图像。每个数据点关联一个随机变量，这些连接也确定了一个团的势。例如$x_1$连接$d_1$，这将确定一个势，记为$\Phi_1$。根据贝叶斯规则，$\mathbf x$和$\mathbf d$的联合分布的概率为
\begin{equation} P(\mathbf x,\mathbf d)={\prod_p\Psi_p(x_p,d_q)\prod_{(p,q)}\Psi_{pq}(x_p,x_q)\over Z}， \end{equation}
$Z$是归一化常数，称为划分函数（partition function），使得概率和为1。上式既包含一元势（unary potential），也包含二元势（pairwise potential）。复杂的连接对应着更复杂的势。
二、条件随机场
条件随机场（CRF，conditional random field）假设$P(\mathbf x|\mathbf d)$具有马尔可夫属性。根据Hammersley-Clifford定理，概率$P(\mathbf x|\mathbf d)$为
\begin{equation} P(\mathbf x|\mathbf d) = {\prod_p\Psi_p(x_p;\mathbf d)\prod_{(p,q)}\Psi_{pq}(x_p,x_q;\mathbf d)\over Z}， \end{equation}
团的势依赖于数据。对于MRF和CRF，都有
\begin{equation} P(\mathbf x)={\prod_p\Psi_p(x_p)\prod_{(p,q)}\Psi_{pq}(x_p,x_q)\over Z}， \label{eq:p-x-1} \end{equation}
MRF和CRF都依赖于一元和二元的势。
三、指数族
$P(\mathbf x)$来自于指数族（exponential family），\eqref{eq:p-x-1}改写为如下形式
\begin{equation} P(\mathbf x)={\exp(-E(\mathbf x))\over Z}， \end{equation}
$\mathbf x$的定义域为所有可能的标签集合，$E(\mathbf x)$称为MRF或CRF的能量函数，
\begin{equation} E(\mathbf x)=\sum_p\theta_p(x_p)+\sum_{(p,q)}\theta_{pq}(x_p,x_q)， \end{equation}
$\theta_p(x_p)＝-\log(\Psi_p(x_p))$，$\theta_{pq}(x_p,x_q)＝-\log(\Psi_{pq}(x_p,x_q))$。 低能量对应于高概率，能量最小化就是概率最大化。
问题描述
图：两标签模型，4个随机变量$X_p,X_q,X_r,X_s$，2个标签$1_0,1_1$。红色标记随机变量的一组取值$\mathbf x$。节点处的值表示一元势，节点间连线上的值表示二元势。$X_p$取$l_1$和$X_q$取$l_0$时，$X_p,X_q$之间的二元势为1；$X_p$和$X_q$都取$l_1$时，$X_p,X_q$之间的二元势为0。
一、能量最小化
模型如上图，能量函数记为
\begin{equation} E(\mathbf x;\mathrm{\boldsymbol\theta})=\sum_p\theta_p(x_p)+\sum_{(p,q)}\theta_{pq}(x_p,x_q)。 \end{equation}
按上图标签的能量为$E(\mathbf x;\mathrm{\boldsymbol\theta})=2+1+2+1+3+1+3=13$。能量最小化就是
\begin{equation} \mathbf x^\ast=\arg\min_\mathbf x E(\mathbf x;\boldsymbol\theta)， \end{equation}
能量的最小值为$e^\ast = \min_\mathbf x E(\mathbf x;\boldsymbol\theta)=E(\mathbf x^\ast;\boldsymbol\theta)$，上图中，$\mathbf x^\ast=\{1,0,0,1\}$，$e^\ast=13$。
二、最小边界
上图中，最小边界$e_p(i)$就是固定$x_p$取值（其它可以任意取值）的最小能量
\begin{equation} \mathbf x^\ast=\arg\min_\mathbf x E(\mathbf x;\boldsymbol\theta)\text{ such that }x_p=i， \end{equation}
$e_p(0)=15,e_p(1)=13$，两个最小边界中的最小值就是最小能量，这并非偶然，这是最小边界的性质。
任意随机变量最小边界的最小值就是最小能量。
重参数化
$\boldsymbol\theta’$是$\boldsymbol\theta$的重参数化（reparameterizaiton），有时记为$\boldsymbol\theta’\equiv\boldsymbol\theta$，当且仅当
\begin{equation} E(\mathbf x;\boldsymbol\theta’) = E(\mathbf x;\boldsymbol\theta)\text{ for all }\mathbf x， \end{equation}
等价于
\begin{equation} \begin{aligned} \theta_p’(i) &= \theta_p(i) + M_{qp}(i) \\ \theta_q’(k) &= \theta_q(k) + M_{pq}(k) \\ \theta_{pq}’(i, k) &= \theta_{pq}(i, k) - M_{pq}(k) - M_{qp}(i) \end{aligned}， \end{equation}
这是有效的重参数化的唯一算数运算[1]。
重参数化一：所有的$\theta_p(i)$加上一个常数，所有的$\theta_q(k)$减去一个常数。
重参数化二：某个$\theta_q(k)$加上一个常数，对所有$i$，所有的$\theta_{pq}(i,k)$减去一个常数。
重参数化三：三标签重参数化。
动态规划
对任意给定的图和标签，能量最小化问题非常困难。对某些特定的情况，可以高效的解决，比如动态规划可以找到链的最优能量标签，树也同样可以。
动态规划就是进行明智的重参数化，关键在于找到重参数化常量，使得$\theta_q’(k)=e_q(k)$。
一、两变量
上图子图的两变量模型。
当$X_q$取标签$l_0$时，重参数化$\theta_q(0)$需要增加的量为
\[ M_{pq}(0) = \min\{\theta_p(0) + \theta_{pq}(0,0),\theta_q(1) + \theta_{pq}(1,0)\}＝\min\{5+0, 2+1\}=3。 \]
同理可得$M_{pq}(1)=2$，那么有$\theta_q’(0)=5,\theta_q’(1)=6$。
经过重参数化，至少有一条路径上（红色）的势之和为0，其余的和至少为0。
对$h$个标签，需要计算$h$个不同的重参数化常量。每个常量的计算复杂度为$O(h)$。因此，全部计算的复杂度为$O(h^2)$，和暴力穷举的复杂度一样。
二、三变量
上图子图两变量重参数化之后的结果。
在两变量重参数化结果基础之上，三变量的计算和两变量一样。如果确定了$X_q$的标签，根据图中红色路径（沿该路径势之和为0），那么就可确定$X_p$的标签。
继续对边$(q,r)$重参数化，最终得到能量最小化时标签$x_r=0, x_q=0, x_p=1$。
重参数化使得当前变量只与前一个变量相关，省去了复杂的回溯过程。
对$h$个标签，需要计算$2h$个不同的重参数化常量。每个常量的计算复杂度为$O(h)$。因此，全部计算的复杂度为$O(2h^2)$，也就是$O(h^2)$，低于暴力穷举的复杂度$O(h^3)$。
三、链与树
对于链模型，首先从左到右依次最小化，然后选择最右变量的最小边界，最后回溯可到最优标签$\mathbf x$。对$h$个标签，$n$个变量需计算$(n-1)h$个重参数化常量。每个常量的计算复杂度为$O(h)$。因此，全部计算的复杂度为$O(nh^2)$，远低于暴力穷举的复杂度$O(h^n)$。
对于树模型，从叶子出发向树根优化，回溯得到最佳标签集$\mathbf x$。事实上，链是特殊的树，$n$个随机变量的树也是$n-1$条边，计算复杂度仍为$O(nh^2)$。
参考资料
- [1]V. Kolmogorov, “Convergent tree-reweighted message passing for energy minimization,” Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 28, no. 10, pp. 1568–1583, 2006.
