PGM 读书笔记节选(十一)

这里简要的讨论 hybrid network 与一些时序数据的分析。

hybrid network 指网络中存在离散随机变量与连续随机变量,这种情况下一般非常麻烦,这主要是因为连续型随机变量需要使用某个参数族来进行刻画,某些情况下对应的 margin 却不属于给定的参数族。常用的处理手段是离散化,即将某些连续分布离散化成为离散随机变量,这样虽然处理起来容易,但是会丢失非常多的信息,也引入了一个也非常困难的问题,如何离散化才有意义?很显然离散化只是为了计算效率进行近似的折衷。因此关于 hybrid network 的讨论其实主要集中在一些特殊情况。前面讲过的 Gaussian network 是一种分析性质良好的连续 r.v.s.,我们首先讨论一下前面一些技术在它上面的应用,继而讨论上面 hybrid network 的性质、近似与精确 inference 的策略。

我们首先引入所谓的 canonical form,这其实和 exponential family 的有一定相似

\displaystyle \mathcal{C} (X ; K, h, g) = \exp\left( -\frac{1}{2} X^\top K X + h^\top X + g\right)

我们不难获得这些参数与矩参数 \mu, \Sigma 之间的关系,在这种表示下,相乘相除的 factor 就可以通过这些系数的相加相减进行计算了。这样 sum-product 进行 VE 的时候每一步其实都是 well-define 并且非常容易计算(传递的就是二次型的系数)。如果使用 belief update 的 parameterization,根据前面的说法其实仍然是二次型(该算法里面多出来一个相除,对应就是系数相减),也是一个容易计算的过程。在有环的情形下,可以证明 LBP 如果收敛,则能够收敛到正确的 mean,但是对方差的估计往往过于确定(方差偏小)。

在引入了离散随机变量后 Gaussian network 的表示往往都是随变量个数增加,参数指数的增加(表示就困难了),因此也很容易证明,此类问题下即便网络是 polytree,甚至离散的是二值的 r.v.s. 问题都将成为 NP-hard。一种直接的想法就是将 message 进行简化,我们知道某些 Gaussian 在 marginalize 掉离散变量后就成为了 mixture of Gaussians,这时我们需要进行近似避免该 message 过于复杂,这一般是使用单个的 Gaussian 进行 M-projection。这样做虽然是一种“可行”的策略,但是往往获得的 Gaussian 并非“正常的”(负方差)。这时有一类所谓 Lauritzen 算法,可以提供正确性和计算有效性上的折衷(看来这个 Lauritzen 算法总是要好好研究下的)。

如果 r.v.s. 之间的关系不再是 linear 情形(比如前面的 CLG),我们往往需要对这类后验关系进行近似,最常见的做法就是所谓的 Laplace approximation,即用一个 Gaussian 去逼近后验。更一般的想法是使用 Taylor 展开,进行更高阶的近似。Laplace approximation 可以认为是使用二阶在 M-projection 下进行的近似。对某些情况下的积分虽然是没有解析解,但是由于是 Gaussian 下积分,我们仍然可以用一些数值解法获得相对精确的解。另外一种思路自然是借助 sampling,这类 network 往往 forward sampling 容易进行,另外 MCMC 与 collapsed sampling 也容易应用到这类问题上,总算是提供了一种“万能”的笨办法。

在时序问题中,最常见的是下面三类 inference 问题:

  • filtering/tracking,给定到现在为止的观测,当前最可能的状态是什么 \max \Pr (s_t \mid o_{1, \ldots, t})
  • prediction,给定到现在为止的观测,下面最可能发生的状态是什么 \max \Pr(s_{t + 1} \mid o_{1, \ldots, t})
  • smoothing/decoding,给定观测求最可能的状态序列 \Pr (s_{1, \ldots, t} \mid o_{1, \ldots, t})

前两者的计算其实是耦合在一起的,因为我们可以利用前者推出后者,

\displaystyle\Pr(s_{t + 1} \mid o_{1, \ldots, t}) = \sum_{s_t} \Pr(s_{t + 1} \mid s_t) \Pr (s_t \mid o_{1, \ldots t})

而后者到前者,我们只需要用一下 Bayesian 公式

\Pr (s_{t + 1} \mid o_{1, \ldots, t+1}) \propto \Pr (s_{t + 1}, o_{t + 1} \mid o_{1, \ldots t}) = \Pr (o_{t + 1} \mid o_{1, \ldots t}) \Pr(o_{t + 1} \mid s_{t + 1})

smoothing 的计算一般也并不麻烦,我们只需要使用 dynamic programming 即可(这是标准的 MAP)。说穿了这都是常见的 inference 问题,如果我们不考虑时序结构直接应用前面的算法势必会比较麻烦。比较理想的情况就是根据这个时间关系进行求解。但要注意,很多情况下可能会出现 entanglement 导致这类做法变得复杂起来,也就是 state 之间还存在另外的路径,可以证明所谓的 fully persistent BN 是不可能单独 track 当前状态的分布的(entanglement theorem),由于存在 entanglement,我们只能用整个联合分布来表达。其实我们使用的不少模型都是避免了 entanglement,当 entanglement 存在的时候我们常见的策略就是使用近似:

  • EP:尽管 entanglement 存在,但是影响的回路较长,我们是否可以用简化的 message 来处理呢?容易发现 prediction 那部分计算的概率正好是我们的 message,而 filtering 部分对应的是 belief。
  • particle-based:针对时序数据,我们可以做 sequential importance sampling。

对连续变量来说,常见的就是 LDS 这种 model 了,其中的重要算法包括 Kalman filter、pariticle filtering。

我们后面将对一些常用的模型(如 HMM、LDS 和 chain CRF)进行相关的推导,这三者是不需要近似算法的。

—————–
And Sarah said, God has made me to laugh, so that all that hear will laugh with me.

Advertisements
PGM 读书笔记节选(十一)

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s