PGM 读书笔记节选(七)

和 Koller 的 video 最大的不同莫过于书上讲 LBP 的角度不是 procedural 的,而是原理性的。我们先看个 procedural 的,在一般的 cluster graph 上的 BP 改进版即 loopy belief propagation 先将所有的 message 初始化为 1,然后依照原先的策略进行消息传递,直到收敛为止。这里面收敛很可能不是所有的消息都能收敛,同时传递消息的顺序一般比较 tricky,过去认为有效的同步传递方式已经被搞清楚很多情况下不能收敛到合理的解了。另外一旦收敛了,我们可以证明得到的结果是 calibrated。问题是我们就算了解了这些过程性的东西,仍然无法弄清楚 LBP 究竟在干啥,有的 margin 似乎能收敛到正确的,有的却不行。

为此我们需要换一个角度来理解 LBP,这也就是这部分我们讨论的重点。值得注意的是很多方法上的东西的确在历史上出现在前,但是“换思路”有时候才能揭示一些更深层的东西。这里的思路就是把 inference 通过 optimization 的形式表述出来,这样我们就得到了 LBP 的另外一种 interpretation:使用 fixed point 优化这个近似的目标函数。这也提供给我们了一些其他的思路,比如 expectation propagation 使用的仍然是精确的目标函数,但是传递的是近似的消息。又比如 mean field approximation,这也是用的精确的目标函数,但是将约束松弛到一族给定了分解形式的分布上。

那么问题就来了,如何能把 inference 转换到 optimization 上来呢?这就要借助前面讨论的 I-projection 和 M-projection 了。咋一看似乎前面的讨论偏向 M-projection,但实际上却不是,因为 D(P_\Phi \| Q) 需要计算在 P_\Phi 下的矩,这意味着我们仍然得回答这个分布下的 inference 问题,因此 I-projection 实际用的反而更多。有了目标函数以后,第二个问题是我们找到的分布 Q 需要满足什么条件。假设我们根据一个 clique tree(满足 RIP 和 family preserving property)存在一个 belief 参数化的 Q,即

\displaystyle Q(\mathcal{X}) = \frac{\displaystyle \prod \beta_i}{\displaystyle\prod_{i \sim j\atop i< j} \mu_{i, j}}

这势必要求我们找到的 \beta_i\mu_{i, j} 满足类似的 consistency 约束,

\displaystyle\sum_{c_i} \beta_i (c_i) = 1, \sum_{C_i - S_{i, j}} \beta_i (c_i) = \mu_{i, j}

一个要求 \beta_i 的确是边际分布,一个要求具有 consistency。有了这几点我们就可以得到一个 constrained optimization:我们希望找到对应的 \beta_i\mu_{i, j} 使得对真实分布 I-projection 最小,同时满足以上两个约束的 Q。事实上,上篇里面的 BP 算法找到的就是这个优化问题的唯一最优解。

我们进一步讨论关于能量函数 D(Q \| P_\Phi),容易证明它等价于 \log Z - F[\tilde{P}_\Phi, Q],即最大化 Helmholtz free energy,其中自由能 F[\tilde{P}_\Phi, Q] = \mathbb{E}_Q \Big[ \log \tilde{P}_\Phi\Big] + H_Q,注意这里由于 \log \tilde{P}_\Phi 可以利用其分解拆成每个 factor 上的期望,计算可望得以简化。而如果 Q 存在类似的分解,我们也可以想象 H_Q 也是容易计算的。我们一般称这个自由能为 energy functional,容易看出来其值被 \log Z 所 bound。由于这是一个函数优化问题,我们常使用变分方法求解(variational methods)。

为了进行求解,我们需要将 \tilde{P}_\PhiQ 的具体形式代入以上目标函数,这样我们就获得(如果 Q 是 calibrated,这样保证最后关于 sep set 的熵是合法的)

\displaystyle \tilde{F}[\tilde{P}_\Phi, Q] = \sum_{i \in \mathcal{V}} \mathbb{E}_{C_i\sim \beta_i} \log \psi_i + \sum_{i \in \mathcal{V}} H_{\beta_i} (C_i) - \sum_{(i, j)\in \mathcal{E}} H_{\mu_{i, j}} (S_{i, j})

(注:对一般的 cluster graph 一般说来 F\tilde{F} 并不相等,这里假定了是一个 calibrated clique tree 的 Q)在有约束的情况下我们一般使用 Lagrange multiplier 写出 Lagrange function,

\displaystyle\mathcal{J} = \tilde{F} [\tilde{P}_\Phi, Q] - \sum_{i \in \mathcal{V}} \lambda_i \left(\sum_{c_i} \beta_i(c_i) - 1 \right) - \sum_i \sum_{j \sim i} \sum_{s_{i, j}} \lambda_{j\to i}(s_{i, j})\left( \sum_{C_i - S_{i, j}} \beta_i(c_i) - \mu_{i, j}(s_{i, j})\right)

这样我们分别计算对 \beta_i\mu_{i, j} 的变分可以得到

\displaystyle\frac{\partial \mathcal{J}}{\partial \beta_i(c_i)} = \log \psi_i(c_i) - \log \beta_i (c_i) - 1 - \lambda_i - \sum_{j \sim i} \lambda_{j \to i}(s_{i, j})

\displaystyle\frac{\partial \mathcal{J}}{\partial \mu_{i, j} (s_{i, j})} = \log \mu_{i, j}(s_{i, j}) + 1 + \lambda_{i \to j} (s_{i, j})

如果令 \delta_{i, j}(s_{i, j}) = \exp\left( -\lambda_{i \to j}(s_{i, j} - \frac{1}{2})\right) 这样我们就得到了 belief update 里面的参数,我们将其该写成 \delta_{i\to j} 就得到了 message passing 里面的形式,但额外乘以某个常数。至此我们说明了,所得分布 Q 是 stationary point 的充要条件,

\displaystyle \delta_{i\to j} \propto \sum_{C_i - S_{i, j}} \psi_i \left( \prod_{k \sim i} \delta_{k \to i}\right)

这个条件由于对应的是 fixed point 方程的一个迭代解法,这导致了我们一般 LBP 算法的另一个 interpretation。对 tree 结构而言,迭代一次后 message 就收敛了(没有 loop 的原因)。事实上,在 cluster graph 上沿袭 clique tree 的算法,也可以类似的应用到 \beta_i\mu_{i, j} 的参数化(belief update)上,我们可以证明它仍然保证了分布的不变性(cluster graph invariance),从这个角度来说它就是试图使用另外的方式组织 factor 使得该表示更加有用。

为了研究 LBP 的近似程度,我们可以在 cluster graph 选择一个子树,如果原图是 calibrated,我们的这棵子树也将是 calibrated,我们可以检查其上的 belief 是否和其上的 marginal 一致,事实上存在一致的也存在不一致的情形。对收敛性的分析一般在 synchronous 更新上比较容易做(但是 synchronous 效果很差,不建议使用),使用的技巧是 \alpha contraction。

和 clique tree 类似,选择合理的 cluster graph 意味着对计算精度和效率的 tradeoff,常用的一种选择是 Bethe cluster graph,这似乎就是 Frey 所说的 factor graph:每个 phi_i 对应一个顶点,每个变对应一个顶点,然后按照关联关系加边,这个二分图上做 LBP 就是 Frey 同志所说的 factor graph 上做 inference 的策略了。我们可以说明一下为什么这是一个 cluster graph(验证一下比如 family preserving,RIP 等)。Bethe cluster graph 比较容易 missing 的是两个变量的相互作用,因为 cluster 之间的关系只能通过单个变量来进行。

那么从算法上对 BP 的修正意味着对目标函数如何的变化呢?注意前面的目标函数(自由能)虽然并不方便(计算难),我们仍然可以使用 factorized 的版本 \tilde{F}(\tilde{P}_\Phi, Q)(因为已经不是 calibrated cluster tree,两者并不相等)近似,因此此时的 Q 也不再是和原先的 margin 一一对应,而是所谓的 pseudo margin(我们把前面那些约束统称为 local consistency polytope), 这样,尽管我们求解的形式完全一样,但是优化的目标出现了近似,这也导致我们的选择的 belief 变成了 pseudo margin。

当我们选择 Bethe cluster graph 时对应的 energy functional 也称为 Bethe free energy,其中熵的部分可以写成

\displaystyle \sum_{\phi \in \Phi} H_{\beta_\phi} (C_\phi) - \sum_{i} (d_i - 1) H_{\beta_i} (X_i)

其中 d_iX_i 出现在 factor 中的次数。那么一种可能的近似是将 r.v.s 放在 region 里面,然后也有对应的数数,,这称为 weighted approximate entropy。另一种策略就是通过调整前面的 weight 使得最后这部分是一个“凹函数”(因为是 maximize free energy),这种策略看起来不错但是实际操作上如果 LBP 收敛了其效果和性能都不如 LBP,而如果 LBP 失败了则会有一定的优势。从划分 region 的想法还会导致所谓的 region graph(抛弃 cluster graph 的 idea,这是一个 nested 结构)。region graph 是个有向图,每个 node 表示一个 r.v.s 的子集,而边表示子集的包含关系(父节点也是父集),每个 region 都有自己的 counting number,一般记为 \kappa_r(不见得是正整数),这个可以类似的定义 family preserving property,也可以定义 energy functional,

\displaystyle\tilde{F} [\tilde{P}_\Psi, Q] = \sum_r \kappa_r \mathbb{E}_{C_r} \log \psi_r + \tilde{H}_Q (\mathcal{X})

类似我们也能定义 calibration,另外我们为了在合适的 region graph 上导出对应的 message passing 以及对应的 fixed point equations,还需要

  • variable connectedness:一个 r.v. 对应的顶点形成一个联通分支
  • factor connected ness:对每个 factor \phi_i 也形成联通分支
  • factor preservation:\sum_{r \in \alpha(\phi)} \kappa_r = 1
  • RIP,对每个变量 \sum_{r \in R_i} \kappa_r = 1

关于 LBP 一个很重要的应用是 turbocodes 里面,我们知道解码往往就是通过观测到被污染的编码后的信息解析出来生成这个编码的数据(因为我们知道原始数据和编码方式,我们可以简单的用这个手段分析一个编码的优劣,并且 Shannon 同志已经搞定了理论下界,我们只需要想办法接近它就行),turbocodes 通过两个 codec 并且在两部分 inference 进行 LBP 这获得了非常接近理论界的 codec。这个发现也使得本来已经停滞不前的 approximate inference 研究重新审视 LBP。

从 Koller 的 video 里面我们还知道下面几个东西:

  • LBP 很可能出现问题的情况是 tight loop,strong potential 且 conflicting message
  • LBP 的 convergence 是 local property,有的就是不会收敛,通常实现的时候达到迭代次数后就会停止
  • LBP 的 message passing order 很重要,常用的有 tree reparameterization(TRP),选择一个树,然后在该结构上做一次(因为收敛了),然后不停的重复,尽量选大的树(如 expanding tree);residual belief prpagation(RBP),选择在 sepset 上 disagree 最多的 cluster 进行消息传递
  • 加速 LBP 的策略还有 damping:和上次的 message 凸组合。

后面我们讨论另外两种 approximate inference 的策略。

——————
And yet indeed she is my sister; she is the daughter of my father, but not the daughter of my mother; and she became my wife.

PGM 读书笔记节选(七)

PGM 读书笔记节选(六)

有个比较有意思的想法是编码理论的反问题是 machine learning,这也是这部分学习的一个收获。这个其实很奇怪,编码理论其实是有 ground truth 的,然后通过编码产生“冗余”,这样才能通过含有噪声的信道后仍然能够被正确的解码(比较好的是相关的理论上界和最优编码已经非常接近了),这个问题的本质其实也是 inference。那为什么我说 machine learning 是它的反问题呢?我们通常会假定数据本身具有“结构”,尽管我们看到的数据是来自某个高维的空间,但是往往有某些内在的东西能够简化我们的模型、表示等等。这意味着我们假定数据是“冗余”的,我们寻求的往往是没有冗余的表示,在这个基础上我们的分类也好还是别的什么会有较好的效果,难度在于我们没有 ground truth。这两者的关系看起来就跟概率论与统计一样。这一方面也激发了我后面看完这部分,希望能扫一遍 David McKay 的那本书的欲望。

这部分本质上是一个比较大的 topic,message passing/belief propagation,每个人的讲法可能不大一样,当时大概先看的 Jordan 的写法觉得有点难懂,这次 Koller 同志的 video 倒是比较容易让人接受(先讲 general case 的 LBP 算法,点出一些核心的性质,然后在特定的图上说明对应的的确是精确解,获得该算法与 independency、消元法之间的关系,然后回到一般情况下介绍一些思路进行优化和推广),不过似乎她的书上并不是这个顺序讲述的。我们这里沿用她书上的思路。

前面讲了消元法(variable elimination,简写为 VE),我们这里将每一步分解:首先我们选择了某个 r.v.s 进行消除,这时我们做的是将相关的 factor 放在一起,我们将这个 factor 记为 \psi_i(这部分是 product),这时我们通过 sum/integral 得到了一个新的 factor 记为 \tau_i,那么我们不断的消元过程中就会得到一系列的 \psi_i,而我们可以将其与一个 graph 关联起来,这就是所谓的 cluster graph。

cluster graph 的每个顶点是一个随机变量的子集(记为 C_i),这个graph 与一个 factorization 相关,我们称这个性质为 family preserving,即每个顶点对应的子集必须可以用若干个 factor 对应的 r.v.s 获得,且每两个顶点不共用 factor,且任意一个 factor 必须属于某个顶点。这里顶点之间的边我们称为 sep set(记为 S_{i, j}),对应的也是一个随机变量子集,且 S_{i, j} \subseteq C_i \cap C_j

事实上给定一个 factorization 可以有多个 cluster graph,而 VE 导致的 cluster graph 却有着重要的作用:我们在 C_iC_j 之间有边,当且仅当 \tau_i(即 \psi_i 消掉某个变量后的 message)用来计算了 \tau_j。这样一来我们每个节点 C_i 最多存在一个(如果当成有向关系的话)父节点,这说明获得的图是一个 tree。我们将最后一个获得的 cluster 称为这棵树的根节点。这里我们说明了 VE 可以诱导出 cluster graph 的一个特例,即 cluster tree。

一般的 cluster graph 未必是 tree,但是后面的讨论,特别是所谓的 running intersection property(RIP)成立情况下,我们的算法可以推广,这部分将在后面的笔记详细讨论,这将导致所谓的 loopy belief propagation(LBP)以及 approximate inference。

RIP 一个 cluster graph 具有 RIP 当且仅当对任意 r.v.,X \in C_i, C_j,则 X 会出现在连接 C_iC_j 的(唯一)路径上每一个顶点和 sep set 里。

定理 VE 所诱导的 cluster tree 满足 RIP。

由于现在已经是一棵树了,所以这条连接 C_iC_j 的路经一定存在且唯一,我们只需要说明 X 出现在这条路径上了。我们可以借助另外一个 clutser,即 X 被 eliminate 掉的,不妨设为 C_X,这样我们可以证明 C_iC_X 的路径上都含有 X,这是因为 X 在到达 C_X 之前不可能消失,之后不可能存在。所以这个结论其实非常显然。同时我们也可以断言 X 也必须存在于中间的 sep set 中(即对应的 \tau_k 里)。这也告诉我们其实 \alpha (\tau_i) = C_i \cap C_j,这告诉我们可以将 \tau_i 当做是 C_i 发送给 C_j 的 message。

clique tree 我们称一个 factorization 导致的 cluster tree 如果满足 RIP 为一个 clique tree,类似的名字还有 junction tree 和 join tree。

关于 RIP 的另一个重要的结论是与 independency 的关系:一个 cluster tree 满足 RIP 当且仅当 C_i - S_{i, j} \perp C_j - S_{i, j} \mid S_{i, j},由于我们是在 MRF 里面讨论的(BN 可以通过 moralization 转换成对应的 MRF),这等价于要求 S_{i, j} 能够分离 C_i - S_{i, j}C_j - S_{i, j}

至此为止我们对 clique tree 的理解还停留在 VE 所需要的结果上(VE 能做一个/组 variable 的 inference query),我们其实能够借助 clique tree 解决更多的问题,比如我们花两倍的计算代价就能计算任意一个/组 variable 的 inference query 了!这个工具就是前面抽象出来的 message,那个地方我们是按照 upstream 的方向(也就是 VE)计算了 C_i 发送给 C_j 的消息,即 \delta_{i\to j} = \tau_i,事实上我们如果逆转按照 downstream 的方向计算相应的 message 之后我们就会有很多新的发现。这仍然将我们的算法局限在 VE 的基础上,我们下面抛开 VE。

我们将 upstream 的逻辑整理一下,一个具有多个 child 的节点只有收到了所有的 child 的 message 才可能继续它自己的 elimination;换言之对于(无向图)每一个 cluster 收到了其他相邻的 cluster 的 message 之后就可以向尚未收到信息的那个发出消息:

\displaystyle \delta_{i\to j} = \sum_{C_i - S_{i, j}} \psi_i \prod_{k \sim i\atop k \neq j} \delta_{k\to i}

像叶子节点由于只有一条边,所以对上一级发出的消息就是 \psi_i 将不必要的变量 sum out。这就是所谓的 sum-product message passing。我们可以为每个 cluster 定义所谓的 belief(从有向情况下的 root 来看,它收到了所有的 message 后),

\displaystyle\beta(C_i) = \psi_i \prod_{j \sim i} \delta_{j \to i}

不难猜测 \beta(C_i) = \Pr (C_i) 即为对应的 margin distribution。可以证明这个策略的确能够得到我们需要的效果,这只需要我们证明每个 message 是什么

\displaystyle \delta_{i \to j} = \sum_{<(i, j)} \prod_{\phi \in \mathcal{F}_{<(i, j)}} \phi

这里 <(i, j) 表示边一侧的所有相关的 r.v.s,而 \mathcal{F}_{<(i, j)} 是这侧 cluster 相关的 factor 的并集。

calibration 如果一个 cluster graph 的两个相邻的 cluster 获得的 belief 对 sep set 是一致的,我们称这个 belief 是 calibrated。

首先我们说明一下这个的必要性,这相当于保证不同的 cluster 在 shared r.v.s 的 margin 至少是 agree with each other 的,没有矛盾。下面我们会发现我们的算法给出的 belief 的确是 calibrated:这我们只需要证明 \beta(C_i) = \Pr(C_i) = \sum_{\mathcal{X} - C_i} \Pr(X_1, \ldots, X_n)

有了这些结果之后我们可以给出不使用 \phi_i 参数化原分布的另一种参数化形式,这个形式依赖于所有的 margin,即这里的 beliefs \beta(C_i)\mu_{i, j}(S_{i, j}) = \delta_{i \to j} \delta_{j \to i},我们可以简单的推导发现

\displaystyle \Pr(\mathcal{X}) = \prod_{i = 1}^K \phi_i = \frac{\displaystyle \prod \beta(C_i)}{\displaystyle\prod_{i \sim j\atop i < j} \mu_{i, j}} (S_{i, j})

这仍然是一组乘积。事实上,对于 calibrated clique tree 而言两者相等,当且仅当每个 belief 正比与 margin。这样做参数化的好处是在于对应的 message passing 要更为“随意”。初始情况下 \beta(C_i) 就是对应的 \psi_i,而 \mu_{i, j} = 1,从 C_iC_j 发送消息不需要等候,而只需要计算 $\sigma_{i\to j} = \sum_{C_i – S_{i, j}} \beta_i$,然后更新 \beta_j \gets \beta_j \cdot \frac{\sigma_{i\to j}}{\mu_{i, j}},然后 \mu_{i, j} \gets \sigma_{i, j} 即可,每条边两个方向走一遍即可(似乎有点不对 -,-b)。这个策略称为 belief update,sum-product-divide message passing scheme 或者 Lauritzen-Spiegelhalter 算法。

下面我们讨论如何利用 message passing/belief propagation 解决 inference query。如果 query 是有 evidence,我们需要将部分相关的 message 重新计算一下;如果 query 的变量在一个 clique 里面我们显然可以用对应的 belief 进行 elimination 得到需要的结果;如果 query 的变量在两个 clique 里面,我们可以选择一个子树包含所有 query 中的 r.v.s.,然后将这个子树里面的 belief 和 message 转换(首先随便选一个作为根节点,用对应的 \beta 与父节点传递的消息除一下)成为一个新的 factor graph,在这里面做消元法。

最后我们讨论如何构造 clique tree,显然前面 VE 的一些 trick 可以使用(一般 VE 的结果还可以剪枝,即将全部是子集的 path collapse 掉),另外一种思路是从 chordal graph(记得 induced width 决定了复杂度),在这种 graph 上的 maximal clique 问题是容易的,我们只需要按照前面的 maximal cardinality 做法就能找到了。

——————
And Abimelech said to Abraham, What saw you, that you have done this thing?

PGM 读书笔记节选(六)

Photography 笔记(十)

摄影历史

观片。主要是从摄影技术的成熟走到对美国的记录,世界范围内的普及,在工业、科学研究上的应用等等。

全景相片

早期有通过 swing-lens cam 拍摄全景图,swing lens 可以绕 nodel point 旋转。为了避免 parallax error,要求相机要按照 center of perspective 来进行旋转,接片的时候其实本质上也是通过对相片做 perspective transform 获得的结果。

其实很多搞摄影也比较喜欢通过透视产生一些滑稽的效果。

研究多个场景不同的 perspective 在给定的投影中心的对齐是 homography 研究的内容,一般来说分下面几步:

  1. 在图片上找 feature,并且获得不同图片上 feature 的对应关系
  2. 将一个图片上的 feature 通过变换到另一个图片上
  3. 将图片 warp 然后产生重叠,对齐
  4. 进行 blending

一种选择是不将图片直接投影在平面上,而是按照柱面进行拼接,然后将柱面展开,这种拼接最好每张图的视角较小,这样造成的 distortion 比较小。还有一种策略是球面投影,但这样的话拼出来的每张矩形图片都需要被形变,

camera 2.0

Marc 同志认为提高像素基本到头,现在增加的应该是计算能力来扩大相机的作用,这就是他号称的 camera 2.0,不过大牛也拿业界吐槽,

相机产业太机密,只卖硬件,软件不公开,计算的功能尚不稳定。

不过现在 face detection、HDR、全景接片等等已经开始普及了。在他所倡导的 cam2.0 里面有不少是结构上的东西,软件的 API 是 C++,感觉挺有意思的,不过估计只能玩 Nokia N900 上面的东西了。

摄影历史

继续看片,这部分罗列了很多 ism:

主义啊主义

——————
And the younger, she also bore a son, and called his name Benammi: the same is the father of the children of Ammon to this day.

Photography 笔记(十)