ChillyRain's Blog

语法解析问题

语法解析问题是比词性标注更高层的问题， 它以一个完整的句子做为输入， 以一棵对应的语法解析树作为输出。语法解析树中不仅反应了各个单词的词性， 也反应出了各个词之间的关系，比如短语（动词短语，名词短语等）甚至句子中的主谓关系等。举个课程中的例子：

语法解析通常都会被表达成监督学习问题，而训练数据集可以是WSJ Treebank(for English)；

语法树可以传达的信息：1. POS; 2. Phrase(VP, NP); 3. subject-verb；应用场景可以是机器翻译中，将源语言中单词间的顺序调换成目标语言中的词顺序。

上下文无关语法（Context-free grammer）

上下文无关语法对语言的一种形式化描述，具体表示为四元组\( G = (N, \Sigma, R, S) \)，其中N表示非终结符，\(\Sigma\)表示终结符，S为特殊的开始符号，R则表示规则，即\(X \rightarrow Y_1 \dots Y_n, X \in N, Y_i \in (N+\Sigma), n \ge 0\)。例如：

最左推导：最左推导是一个序列\(s_1, ..., s_n\)，序列的开头是\(s_1 = S\)，其后的每一个元素\(s_i\)都是取前一个元素\(s_{i-1}\)中从左边数第一个非终结符，对其按照R中的某个规则进行展开而得到的结果，序列的结尾是一个全部由终结符构成的字符串，即\(s_n \in \Sigma^{*}\)，例如，[S] [NP VP] [D N VP] [the N VP] [the man VP] [the man Vi] [the main sleeps]。

一个推导(derivation)实际就对应着一棵语法解析树，而推导最终的结果（终结符串）就是一个句子。一个CFG对应的所有推导结果的并集就是这个CFG所定义的语言；每个语言中的字符串有可能对应着不同的推导过程，因此一个句子可能对应着多棵语法树，这在一定程度上产生了歧义。比如，he drove down the street in the car这句话就可能有多种解析，in the car这个短语可以修饰drove形成动词短语，也可以修饰the street以形成名语短语，虽然第一种选择看起来更合理一些，但是CFG是无法区分出来的。

下面再给出几个可能出现的歧义情况

1. POS歧义：her duck (NN, Vi)
2. 介词短语所修饰的内容：比如前面提到的in the car
3. 名词定语：the fast car mechanic (fast car -> mechanic, fast -> car mechanic)

PS: 这里本来还有一节是介绍英语语法的，这里先略过，后面如果有用到的话再说明。

概率上下文无法语法(Probabilistic Context-free grammer)

这个语法是为了解决上面提到的一个句子可能有多棵语法解析树的问题，这为每棵语法树赋予一个对应的概率值，而概率值最大的那个就被认为是这个句子的语法解析树。

实现上，它是对规则集R中的每条规则都赋予一个概率p，而一个推导实际就是从开始符S开始应用一系列规则最终生成非终结符串的过程，因此这个推导（或者说这棵对应的语法树）的概率就是在此过程中应用的所有规则概率的乘积，即

这个由部分概率（规则概率）到整体概率（语法树概率）的过程也是使用了独立性假设（与概率的链式规则做对比），即在推导的初始阶段应用的规则不依赖于后面应用到的规则，特别地，不依赖于最终的word。这也是后面提出lexicalized PCFG的动机。

当我们已经使用上面的方法为给定句子所对应的所有语法树都赋予了一个概率之后，下面要做的，就是取那个概率最大的语法树做为输出：

\[ opt\_tree = argmax_{t \in T(s)} p(t)\]

根据上面的流程，我们有两个问题需要解决：1. 如何为每个规则赋予一个概率值；2. 一个句子对应的可能的语法树是指数级别的，如何高效地为一个句子找到概率最大的语法树。

PCFG的参数估计

PCFG的参数就是每个规则的概率，当给定一个treebank之后，我们要做的实际跟N-gram类似：计数＋MLE

\[ q_{ML}(\alpha \rightarrow \beta) = \frac{Count(\alpha \rightarrow \beta)}{Count(\alpha)}\]

如果训练数据确实是由PCFG生成的，那么当训练数据足够多时，MLE给出的结果将收敛于true PCFG。

PCFG解析

为了能多项式复杂度解决这个为给定句子找出最佳语法树的任务，还需要对PCFG加一些额外的约束，即要求语法G满足Chomsky Normal Form，简单来说就是要求四元组中的R只能取以下两种形式之一

1. \(X \rightarrow Y_1 Y_2, X \in N, Y \in N\)
2. \(X \rightarrow Y, X \in N, Y \in \Sigma\)

然后，使用一种称为CKY的算法来做这个解析工作，它的本质也是一种动态规划算法，如下

其中定义\(\pi (i, j, X)\)表示以非终结符X为root的覆盖word[i...j]的最佳语法树所对应的概率是多少。动态规划的过程是从长度最短的子句（单词，长度为1）开始，自底逐步向上，直至开始符S覆盖整个句子作为终结。每一步需要考虑覆盖的字句的长度以及对应的非终结符，计算复杂度为\(O(n^3N^3)\)。

标注问题

应用：词性标注，命名实体标注，命名实体抽取，中文分词等

目标：从训练数据中获取一个函数或者算法，使得它在接收一个句子作为输入时能产出一个标注序列。

约束：local（一般来说，单词can更可能是一个动词而不是名词），contextual（the后面的更可能是一个名词，而不是动词）

生成模型和判别模型

监督学习：给定一个训练集\((x_i, y_i), i = 1...n\)，得到一个从y到x的映射关系\(f(x)\)。

判别模型：从训练集出发，获得一个条件概率分布\(p(y|x)\)；对于任何一个测试样本x，定义\(f(x) = argmax_y p(y|x)\)。

生成模型：从训练集出发，获得一个联合概率分布\(p(x, y) = p(y)p(x|y)\)。

生成模型比判别模型拥有更多的信息，因为任何条件概率分布都可以由联合分布通过边缘化得到。

\[p(y|x) = \frac{p(y)p(x|y)}{p(x)} = \frac{p(y)p(x|y)}{\sum_y p(y)p(x|y)}\]

对于测试样本x，生成模型要做的跟判别模型本质上是一样的

\[f(x) = argmax_y p(y|x) = argmax_y p(y)p(x|y)\]

其中分母\(p(x)\)不影响argmax_y，所以可以被忽略掉。

隐马尔科夫模型HMM

基本定义

HMM是一种生成模型，对于任意一个单词序列\(x_1, ..., x_n\)，任意一个标记序列\(y_1, ..., y_n\)，HMM定义的是一个联合分布

\[p(x_1, ..., x_n, y_1, ..., y_n)\]

而当给定这个分布，同样再给出测试样本\(x_1, ..., x_n\)时，我们要做的就是找到能最大化联合分布的那一个\(y_1, ..., y_n\)

\[argmax_{y_1, ..., y_n} p(x_1, ..., x_n, y_1, ..., y_n)\]

跟第二章讲的一样，HMM为了简化计算都会有一个对上下文长度约束的假设。Trigram的假设是说

\[p(x_1, ..., x_n, y_1, ..., y_{n+1}) = \Pi_{i=1...n+1} q(y_i|y_{i-2}, y_{i-1}) \Pi_{i=1...n} e(x_i|y_i)\]

其中\(x_1, ..., x_n \in V, y_1, ..., y_n \in S, y_{n+1} = STOP, y_{-1} = y_0 = *\)。所以这个模型的参数就是

\[q(s|u, v), s \in S \cup \{STOP\}, u, v \in S \cup \{*\}\]

\[e(x|s), s \in S, x \in V\]

回过头来再看前面这个联合分布，等号右侧的第二项实际就是\(p(x|y)\)，而第一项就是\(p(y)\)，所以说HMM是生成模型。

参数估计

要想使用这个模型就得先把q和e这两套参数先从训练数据中搞出来：

对于q参数，可以直接借鉴上一章中language model里的smooth estimation方法，比如线性插值（就是带\(\lambda\)的那套方法）；

对于e参数，最直接的方法就是MLE，然后我们又遇到了同样的问题：Sparse Data，肿么办？

课程中给出了一个word class的方法：简单来说就是高频词直接MLE（比如出现次数大于等于5的），低频词则按照一定的特征划分到有限个类别中，类别可以是twoDigitNum, containDigitAndSlash, allCaps等，通常需要人工指定规则，划分之后针对\(e(wordClass|y)\)来做统计，而不是原来的\(e(word|y)\)，以丢失word中一些信息为代价来保证有估计得到的参数足够的统计意义。

Viterbi算法

假设使用前面的方法已经获得了想要的参数，那么HMM就已经构造完成了，后面就是看怎么用这个模型来对测试样本做标注了，即

\[argmax_{y_1, ..., y_{n+1}} p(x_1, ..., x_n, y_1, ..., y_n)\]

其中\(y_{n+1} = STOP, y_{-1} = y_0 = *\)。首先说暴力方法是行不通的，因为需要\(O(|S|^{n})\)，指数级别，会被搞死的。。。

下面要说Viterbi算法就是利用动态规划的思想来解决这个标注问题的，懒得费劲了直接上图。

其中递归式\(\pi(k, u, v)\)表示的是"maximum probability of a tag sequence ending in tags u, v at position k"，bp里面存在是回溯指针，用于循环结束后向回寻找最优的tag sequence。

由于Viterbi算法计算每个\(\pi(k, u, v)\)项需要遍历所有\(S_{k-2}\)，而一共有n*|S|*|S|个项需要计算，所以其算法复杂度为\(O(n|S|^3)\)，比指数级别的暴力搜索要强很多。

这个算法的优点是简单，而且在一些应用中也表现得很好，缺点就是前面所说的e参数不好估计。

PS：这个课程里讲的HMM其实并不全面，HMM相关的有三类问题

1. 给定模型，它能产出给定x序列的可能性是多大（forward算法）
2. 给定模型，给定x序列所对应的最可能的y序列是啥（这个就是课程里讲的标注问题，Viterbi算法）
3. 非监督条件下如何估计参数，即训练数据中没有y的情况下怎么搞（forward-backward算法，本质是EM）

52nlp网站中有一系列很赞的文章《HMM学习最佳范例》，里面讲得更加细致全面一些，所以把相关的链接放在这里，就当是备忘吧。

语言模型问题的定义

词汇表：\(V \) = {the, man, telescope, ...}

语句：\(V^{+}\)，无限多个，由词汇表中的若干个词加上结尾处的STOP标记组成；例如，the fan saw Beckham STOP，甚至the the the STOP也属于这其中。

输入：训练样本，各种各样实际中使用的句子，可以从报纸来，也可以从网页来。

输出：一个面向语句的概率分布，满足以下条件；实际表达的意义就是让像人话的句子概率更高，反之则更低。

\[ p(x) >= 0, \sum_{x \in V^{+}} p(x) = 1\]

这个模型有啥用

原始的出发点是语音识别，因为一段语音通常可以被识别成不同的句子，例如，recognize speech vs wrench a nice beach，但是前者明显更像人话，这时应用语言模型就可以辨识出这段话是前者的可能性更大。

另外，语言模型中的估计方法（estimation/smoothing method）也会很广泛地应用到NLP的其它问题之中，这也算是一个用途吧。

一个简单的方法

想解决语言模型问题，实际就是想得到一个合适的\(p(x)\)，如何做呢？一个简单的方法就是记数，假设训练样本的规模是N，统计下训练样本中每个x出现的次数，然后\( p(x) = C(x) / N\)。但是这样做的问题是，如果有一个训练样本中从未出现的句子，那么它的概率就是0了，也就是说这个未出现的句子无论具体内容是啥，\( p(x)\)都认为它不是人话。

马尔科夫模型

马尔科夫模型假设第n个词出现的可能性只依赖于它的前k个词，即第n-1至第n-k个词。由于后面要讲是三元模型，所以这里用的是就三阶马尔科夫模型。具体来说，

\[p(x_1, ..., x_n) = p(x_1)*p(x_2|x_1)*p(x_3|x_1, x_2)*...*p(x_n|x_1, ..., x_{n-1})\]

这个是没有加入马尔科夫的链式规则，精确的等式，但是如果我们想用这个来算语言模型的话，就得从训练数据中估计出每个\(p(x_i|x_1, x_2, ..., x_{i-1}) \)，这样我们就需要估计出\(O(|V|^{n})\)个参数。参数太多显然是没法搞的，因为参数越多，需要的训练数据就越多，否则就是造成参数极不稳定，甚至没什么意义。

如果加入前面提到的三阶马尔科夫假设的话，问题就简化了

\[p(x_1, ..., x_n) = p(x_1)*p(x_2|x_1)*p(x_3|x_1, x_2)*...*p(x_n|x_{n-2}, x_{n-1})\]

这样参数的个数就降到了\(O(|V|^3)\)（其实这个量级仍然太大，后面会讲到解决方法）。如果我们假设\(x_{-1} = x_0 = *\)，表示开始符号，那么就可以将上式写成

\[p(x_1, ..., x_n) = \Pi_{i=1...n} p(x_i|x_{i-2}, x_{i-1})\]

还有个问题，就是上式只能表示长度为n的句子，而我们想要的是对任意长度的任意句子都有效的分布p。实际上，融合我们前面的定义\(x_n = STOP\)，我们已经可以表示任意的句子了。

三元语法模型

把前面的三阶马尔科夫模型直接应用，就是三元语法模型，它包括以下两个部分

• 一个有限的词汇表\(V\)
• 对每个\(w \in V \cup {STOP}, u, v \in V \cup {*}\)，都有一个参数\(q(w|u, v)\)

于是对任何一个句子\(x_1, ..., x_n\)，其中\(x_1, ..., x_{n-1} \in V, x_n = STOP\)，都可以直接它所对应的概率

\[p(x_1, ..., x_n) = \Pi_{i=1,...,n} q(x_i|x_{i-2}, x_{i-1})\]

举个例子，

\[p(the dog barks STOP) = q(the|*, *) * q(dog|*, the) * q(barks|the, dog) * q(STOP|dog barks)\]

好了，到这里，剩下的最后一个问题就是参数\(q(w|u, v)\)怎么从训练数据中估计出来了，最简单的方式就是MLE（极大似然估计法），即

\[q(x_i|x_{i-2}, x_{i-1}) = \frac{Count(x_{i-2}, x_{i-1}, x_i)}{Count(x_{i-2}, x_{i-1})}\]

正如前面所述的，这里参数的个数是\(O(|V|^3)\)，依然不少，要使用这种方法得到稳定的参数估计值就需要使用大量的数据。否则的话，上式的分子分母都极有可能是零，那么得到的参数意义就不大了。

使用Perplexity对模型进行评估

假设我们除了有用于训练模型参数的训练数据之外，还有一些测试数据，表示为\(s_1, s_2, ..., s_m\)，那么就可以用这些测试数据来评估训练得到的模型的可用性。这里定义了perplexity这个概念，本质上就是模型对这些测试数据的对数似然性：

\[Perplexity = 2^{-l}, where l = \frac{1}{M} \sum_{i=1...m} log p(s_i)\]

其中M表示测试数据是总的单词数据，因此l代表的就是模型对单个词的似然性；测试数据与模型的适应程度越好，似然性越大，perplexity就越小。

下面是对几个模型的比较

• 均匀分布：\(q(w|u, v) = \frac{1}{|V|+1}\)，无论上下文是啥，也不管当前词是啥，这个概率值总是固定的，这是一个很粗的模型，所以perplexity也很高为\(|V|+1\)；
• 一元语法模型：也就是unigram，就是在训练数据上记数，完全不管上下文，在Goodman的实验中（|V|=50000），它的perplexity为955；
• 二元语法模型：就是只考虑前一个单词对当前词的影响，同一个实验中perplexity为137；
• 三元语法模型：就是前面花大篇幅讲的那个模型，考虑当前词前面两个单的影响，perplexity为74；这已经是足够好的效果了。

但是三元语法模型也有它的不足，它无法捕获长距离的依赖关系，但是考虑的上下文太多了，就又会出现sparse data的问题，使参数估计很困难。其实这里也就是一个bias-variance tradeoff，上下文考虑得多，自然bias就小，但是由于训练数据相对不足，variance就大了；相反地，如果上下文考虑得少，variance小，但是bias就大了，所以不得不做一些折衷， 讲师说trigram的方法就是一个比较好的折衷。

参数平滑方法

我觉得下面这些内容才是这段课程的重点，就是怎样解决前面提到的由于数据稀疏问题而造成的MLE估计不可靠的问题。课程里介绍了两个方法，一种是线性插值，另一种是katz-backoff的类递归方法。实际上还有很多其它的方法，可以参考Foundations of Statistical Natural Language Processing中的第6章，也许未来这章的内容我也会总结一下写在blog上。

线性插值

这个方法的动机就是上一小节最后提到的bias-variance trade-off，既然unigram的variance小，而trigram的bias小，为啥不想个办法整合一下呢？于是就有了

\[q(w_i|w_{i-1}, w_{i-2}) = \lambda_1 \dot q_{ML}(w_i|w_{i-1}, w_{i-2}) + \lambda_2 \dot q_{ML}(w_i|w_{i-1}) + \lambda_3 q_{ML}(w_i)\]

\[\lambda_1 + \lambda_2 + \lambda_3 = 1, \lambda_i >=0\]

容易证明这个线性插值所产生的\(q(w_i|w_{i-1}, w_{i-2})\)也是一个合法的概率分布，符合归一化及>=0的条件。

各个\(q_{ML}\)都可以从训练数据中直接计算得到，那么剩下的事就是如何计算\(\lambda_i\)了。这里使用的方法是搞一份validation data，记这份数据中各个三词序列出现次数为\(c'(w_1, w_2, w_3)\)，那么log-likelihood的表达式即为

\[L(\lambda_1, \lambda_2, \lambda_3) = \sum_{w_1, w_2, w_3} c'(w_1, w_2, w_3)logq(w_3|w_1, w_2)\]

表达式中未知参数只有\(\lambda_i\)，所以使用这个表达式对其求偏导应该就可以了。另外，前面提到的perplexity实际就是log-likelihood的变形，所以这种方法就也是在寻找一组参数，使perplexity最大化。

再进一步，前面这种方式得到是一个不依赖于具体\(w_1, w_2\)的\(\lambda_i\)。极端情况下，如果我们已知\(w_1, w_2\)出现的次数足够多，还不如直接用trigram就好了（\(\lambda_3 = 1\)，其它两个为0），相反地如果\(w_1, w_2\)出现极少，那么\(\lambda_1\)就应该相应的更重一些。总结一下就是说，最好是能让\(\lambda_i\)能随着具体\(w_1, w_2\)出现的次数而变化。于是就出现了下面\(\Pi(w_{i-2}, w_{i-1})\)这个东西

\[C(w_{i-2}, w_{i-1}) = 0, \Pi(w_{i-2}, w_{i-1}) = 1\]

\[1 <= C(w_{i-2}, w_{i-1})  <= 2, \Pi(w_{i-2}, w_{i-1}) = 2\]

\[3 <= C(w_{i-2}, w_{i-1})  <= 5, \Pi(w_{i-2}, w_{i-1}) = 3\]

\[C(w_{i-2}, w_{i-1}) >= 5, \Pi(w_{i-2}, w_{i-1}) = 4\]

再然后就是依赖于\(\Pi(w_{i-2}, w_{i-1})\)的\(q\)

\[q(w_i|w_{i-1}, w_{i-2}) = \lambda^{\Pi(w_{i-2}, w_{i-1})}_1 q_{ML}(w_i|w_{i-1}, w_{i-2}) + \lambda^{\Pi(w_{i-2}, w_{i-1})}_2 q_{ML}(w_i|w_{i-1}) + \lambda^{\Pi(w_{i-2}, w_{i-1})}_3 q_{ML}(w_i)\]

实际上就是按照每个\(w_i\)的context出现的次数，即\(C(w_{i-2}, w_{i-1})\)，来对\(w_i\)分组，每组使用一套\(\lambda\)参数。

Katz Back-off Model

这种方法的动机的是从训练数据里得到的ML估计是对存于在训练数据里的词的过高估计（尤其是对仅出现一次的词），而对未登陆词的过低估计（ML估计都是0），所以需要从已有词的概率中抽取出一部分，分给这些未登陆词。以bigram为例，已存在词的次数被折掉了一部分(0.5这个数是个经验值，也可以使用前面的validation set方法来估计出来)，

\(Count^{*}(w_{i-1}, x) = Count(w_{i-1}, x) - 0.5\)

而折掉的概率一共是

\[\alpha(w_{i-1}) = 1 - \sum_{w} \frac{Count^{*}(w_{i-1}, w)}{Count(w_{i-1})}\]

这些概率会根据unigram中各个x的概率比例再重新分配。具体如下：定义两个集合，\(A(w_{i-1}) = \{w: Count(w_{i-1}, w) > 0\}, B(w_{i-1}) = \{w: Count(w_{i-1}, w) = 0\}\)，则有

\[q_{BO}(w_i|w_{i-1}) = Count^{*}(w_{i-1}, w_i) / Count(w_{i-1}), w_i \in A(w_{i-1})\]

\[q_{BO}(w_i|w_{i-1}) = \alpha(w_{i-1}) \frac {q_{ML}(w_i)} {\sum_{B}q_{ML}{w_j}}, w_i \in B(w_{i-1})\]

也就是说如果\(w_i\)出现在了训练语料中就使用高阶模型，否则的话就回退到低阶的模型中，在bias和variance中取一个折衷。基于上面bigram的定义，可以继续定义trigram模型，使未登陆词回退到bigram中。

最后是说可能对trigram模型的进一步改进方法，包括topic model，语法模型等，但是"It's generally hard to improve on trigram models though!!"

之前在Coursera上找到了一门NLP的课，也跟过一段时间，但是没跟完。。。本来想再开课时再跟一次，但是从网站上看貌似是短期内不会重开了，好在教学视频都在，只好自学一下了，顺便把笔记记在这里。

第一周的课分成了三个部分，这里是第一部分，对NLP的简单介绍，由于不涉及具体的NLP算法，所以我也只是简单带过了。

什么是自然语言处理

• NLU：自然语言理解，把languge作为computer的输入，让后者理解输入的是啥；
• NLG：自然语言生成，把language作为computer的输出，即让后者生成自然语言；个人感觉这应该是在NLU的基础上才能做的。

具体应用的举例

• 机器翻译：理解源语言，生成目标语言，这个应该是NLU＋NLG。
• 信息抽取：从一段非结构化的自然语言的文本中抽取出关键信息，如这段话描述的时间，位置，事件等结构化信息（这些结构后信息通常存于db中），换句话说就是想把一段文本对应到一条数据库记录上。应该场景可以是复杂的search query或者statistical query。
• 摘要：同样也是NLU＋NLG。需要先理解这段文本的意思，然后进行压缩，输出摘要内容。
• 对话系统：接受自然语言的问题，理解之，再做出回答，也是NLU＋NLG。

基础的NLP问题：这些问题是解决上面具体应用的基石

• Tagging：标注问题，把一段文本做为输入，为每个单位打上一个标记，输出对应的标记序列。包括POS Tagging（词性标注），Named Entity Recognition（命名实体识别）。
• Parseing：解析问题，以一句话做为输入，辨识出它的语法结构，输出是一棵语法树。这两个问题后面都有章节具体地讲。

为什么NLP是个难题

一句话可能有各种层次上的歧义，包括acoustic level（like your vs lie cured），syntactic level（不同的语法树，从而造成不同的意义），semantic level（一词多义）, discourse level（指代不明）。

课程包含的内容

• NLP问题：POS tagging，parsing，词义消歧
• 机器学习技术：PCFG，HMM，EM，log-linear model，estimation/smoothing techniques
• 应用：信息抽取，机器翻译等

在微博上看到的，还没下载，先写在这儿share出来，也当留个备份。貌似是百度的余凯和张瞳讲的。

下载地址

上一节提到的Conditional Probability Query和MAP中最关键的点就是要算贝叶斯公式中的分子，这个有了之后要么归一化要么取最大值，这事就搞定了。所以本节的这个VE算法就是用来算这个分子的。

Variable Elimination Algorithm

这个算法超级简单，就是每一步都尝试去掉其中的一个变量，方式是把所有与这个变量相关的factor都搞在一起，然后marginalize，生成的结果记作一个新的factor；然后选择另一个变量去重复上面的步骤，直至所有无关变量会都被eliminate掉了，这个事也就搞定了。直接给个例子，我们想算下面这个BN中P(J)的分布：

先把P(J)写成factor product的形式

\[\hat P(J) = \sum_{L,S,G,H,I,D,C} \phi_J(J,L,S) \phi_L(L, G) \phi_S(S, I) \phi_G(G, I, D) \phi_H(H, G, J) \phi_I(I) \phi_D(C, D) \phi_C(C)\]

假设我们按照C, D, I, H, G, S, L的顺序来依次做variable elmination，先来搞C，把所有跟C相关的factor放在一起，并把对C的求和push进去，形成

\[\hat P(J) = \sum_{L,S,G,H,I,D} \phi_J(J,L,S) \phi_L(L, G) \phi_S(S, I) \phi_G(G, I, D) \phi_H(H, G, J) \phi_I(I) \sum_C \phi_D(C, D) \phi_C(C)\]

重新定义一个新的factor，\(\tau_1(D) = \sum_C \phi_D(C, D) \phi_C(C)\)，代进去，得到

\[\hat P(J) = \sum_{L,S,G,H,I,D} \phi_J(J,L,S) \phi_L(L, G) \phi_S(S, I) \phi_G(G, I, D) \phi_H(H, G, J) \phi_I(I) \tau_1(D)\]

这样我们就成功把C去掉了，或者说marginalize C。下一步要去掉是D，同样的定义\(\tau_2(G, I) = \sum_D \phi_G(G, I, D)\tau_1(D)\)，代入上式中得到

\[\hat P(J) = \sum_{L,S,G,H,I} \phi_J(J,L,S) \phi_L(L, G) \phi_S(S, I) \phi_H(H, G, J) \phi_I(I) \tau_2(G, I)\]

这样D也被干掉了。后面的工作以此类推，直到把等式右边非J的变量都干掉了，计算就结束了，我把最后一步写出来。

\[\hat P(J) = \sum_{L,S} \phi_J(J,L,S) \tau_5(L, J, S)\]

如果有Evidence咋办？凉拌！

\[\hat P(J, I=i, H=h) = \sum_{L,S,G,D,C} \phi_J(J,L,S) \phi_L(L, G) \phi_S(S, I=i) \phi_G(G, I=i, D) \phi_H(H=h, G, J) \phi_I(I=i) \phi_D(C, D) \phi_C(C)\]

就这么简单！

贝叶斯公式的分子算完了，如果想得到\(P(J|I=i, H=h)\)呢？正如前面所述，renormalize就可以了，归一化常量就是\(P(H=h, I=i)\)。

前面这个例子是BN，对MN其实也一样，都是对factor做处理，就不多费话了。

再来两张图，总结一下VE算法的关键步骤：

简单来说，把所有与变量Z相关的facor乘在一起，通过marginalize把Z干掉，得到的结果变成一个新的factor参与到下次的计算中；重复以上步骤即可。

Complexity Analysis

这部分是对VE算法的复杂度分析，比较无趣，但是跟后面的知识也有些关联，还是得写写。

VE算法执行的每一步由两部分组成：factor product + marginalization。先来看看每部分的有哪些工作量。

\[\psi_k(X_k) = \Pi_{i=1}^{m_k} \phi_i\]

这个是factor product的步骤，它把\(m_k\)个factor相乘。对于\(X_k\)的每一个assignment，需要每个factor都参与相乘，因此共有\(m_k - 1\)次乘法操作。而\(X_k\)有多少assignment呢？记这个数为\(N_k = |Val(X_k)|\)，于是这个factor product的步骤需要\((m_k-1)N_k\)次乘法。

\[\tau_k(X_k - \{Z\}) = \sum_Z \psi_k(X_k)\]

这个是marginalization的步骤，令\(N_k\)的定义不变，由于\(X_k\)的每一个assignment都要参与且仅一次参与marginalization求和的操作，因此这步需要花费掉\(N_k\)个加法操作。

ok，现在来看整个算法执行过程中的花费。假设有n个变量，m个factor（对于BN来说，m<=n，因为每个变量都有一个factor，如果算上evidence，那么有m<n的可能；而对于MN，通常有m > n，因为MN的factor可能是多个变量的组合，如pairwise factor）。在VE的每一次eliminate时，算法会生成一个新的factor，同时会eliminate至少一个变量。我们一共只有n个变量，所以至多会有n个eliminate的步骤，而总的factor数量\(m^* <= m + n\)，这里小于就是因为至多n次eliminate而生成新factor。

取VE执行过程中最大的factor的assignment数量为\(N = max(N_k)\)，于是

• Product operations: \(\sum_k (m_k-1)N_k <= N\sum_k(m_k-1)\)，而由于每个factor最多只参与一次factor product就被融入新生成factor之中了，所以上式至多为\(Nm^*\)；
• Sum operations: \(\sum_k N_k <= N*n\)，因为至多只有n次elimination操作。

这样看来，所有的花费相对于N, m, n都是线性的，但是N实际上相对于变量个数是指数级的，所以我们白高兴了。

从上面这些分析来看，m和n不可变的情况下，我们要尽量不要在VE的执行过程中生成太大的factor，因为在变量的cardinality不可变的情况下，我们只能让factor不要包含太多的变量。而从一些例子中可以发现，Elimination Order对于控制N有着很大的作用，举一个比较极端的例子，下图中先去掉A时会生成一个包含k个变量的factor，而先去掉各个B时，生成factor只会包含2个变量。

Graph-Based Perspective

这一小节的内容核心是Induced Graph，先给出定义，然后再给例子。

定义于factors \(\Phi\)和elimination order  \(\alpha\)的Induced Graph \(I_{\Phi, \alpha}\)满足：1. 无向图；2. 如果两个变量\(X_i, X_j\)在按照\(\alpha\)来执行VE过程中出现在同一个factor中，而且原图上不存在边的话，那么它们之间就被连上一条filling edge。

换句话说，原图由于VE按照某种顺序执行过程而添加上一些边，这个生成的新图就是Induced Graph。原图是啥呢？就是由factors induce出来的MN，这个前面的章节里已经提过了。

下面给例子，先是原图，这个是通过BN->factors->MN来得到的。

如果按照C, D, I的顺序来执行VE的话，那么干掉I之后就需要在G和S之间添加上一条边了，因为它们会同时出现在一个新的factor之中。

这个图跟VE的复杂性有啥关系吗？必须有！

Theorem: Every factor produced during VE is a clique in the induced graph.

clique就是一个maximal fully connected subgraph，也就是任意两个结点之间都一条边相连，而添加任意一个其实变量都不能使这个条件满足。结合clique的概念，其实上面这个定理很好理解，之所以生成一个新的factor是由于我们把与某个变量Z相连的所有factor都搞到一起了，而生成新的factor之后，Z的邻居们也肯定都有边相连（没有的都会被补上filling edge）。因为我们已经把Z的所有邻居都找来了，任意一个非Z邻居的变量都不可能加入这个clique，因为它至少无法与Z相连。

Theorem: Every clique in the induced graph is a factor produced during VE.

这个也很好理解，先给定出组成一个clique的K个变量，那么肯定会有一个变量在VE的过程中首先会被eliminate掉。因为在eliminate之后就不可能再有其它结点能与之相连了，所以此时它应该已经与clique中其它的K-1个变量都直接相连了。而在eliminate之后生成的新factor中，这K-1个变量必须都在其中，因此它们之间都会有边相连形成fully connected，所以此时这个clique就已经形成了。

然后就是Induced Width的概念：这个值就是Induced Graph中最大的clique的包含的结点个数-1。为啥减1呢？因为clique中实际是包含了被eliminate掉的那个变量，而生成的新factor则不包含这个变量，而前面一个小节也提到了VE的执行效率很大程度上受制于VE过程中最大的factor包含的变量个数（记作factor size），所以这样就有Induced Width = factor size。

因此最小化factor size等价于最小化induced width，于是就有了minimal induced width的概念：\(min_{\alpha}(width(I_{K, \alpha}))\)；它实际上就直接对应了一个VE算法执行效率的下界。

Finding Elimination Orderings

Theorem: 对于一个图H，判断是否存在一个elimination ordering使用得induced width <= k还是一个NP-complete问题。这日子没法过了！

另外注意的是，这个NP-hardness与inference问题的NP-hardness是独立的，也就是说，即使给出了一个最优的ordering，用它去做inference也同样是指数级的。

好吧，既然如此，我们只能求助于Greedy Search方法了，即每个步都优先干掉最小cost的那个变量，咋定义cost呢？

• min-neighbors: 当前图中的邻居数量
• min-weight: 新生成的factor的assignment数量
• min-fill: 最小数量的filling-edge，讲师说这个function效果好
• weighted min-fill: 新的filling edge的weight之和，每边edge的weight为其相联的两个node的weight的乘积。

Theorem: The induced graph is triangulated –  No loops of length > 3 without a “bridge”。这个定理不知道干啥用的，后面也没讲。。。

最后Robot Localization的例子，在这个MN中先eliminate landmards还是poses会形成两个密度差异很大的induced graph，而密度越大说明对应的factor包含的变量越大，VE执行起来也就越慢。

前面都是讲PGM的representation，从这里开始，后面讲的是Inference，即当我们有了一个完整的PGM之后，如何使用它来回答一些问题。这一小节就是在说有哪几种类型的“问题”。

Conditional Probability Queries

说白了，就是在给定一个PGM的情况下，要算\(P(Y|E=e)\)的概率分布是啥；其中E=e称为Evidence，也就是已知的某些变量的取值，而Y为Query，也就是我们的目标变量。

不幸的是，给定一个PGM \(P_{\Phi}\)，一个变量X及其某个取值x，想要计算其概率\(P(X=x)\)或者判断是否满足\(P(X=x) > 0\)都是NP-hard；更不幸的是，即使我们降低要求，只想要一个近似解，那么这个问题也是NP-hard。万幸的是，这些都只是worst case，对于general case还是有希望能得到efficient solution的。

计算Conditional Probability Query的通用方式称为Sum-Product，在介绍之前需要先声明一下：后面所有的操作都是针对factor来做的，对于MN这样毫无问题，因为factor原来就是MN的component；而对于BN，其原始component是条件分布\(\hat P(X|Par_X)\)(注意这里是unormalized measure)，所以需要做一个定义，即\(\phi(X, Par_X) = \hat P(X|Par_X)\)，这样BN也可以使用factor来表示了。

Sum-Product实际上工作就是把所有的factor做product，然后marginalize所有无关变量，比如说像下面这个BN中计算\(P(J)\)例子：

这里忽略了一点，就是这里没有Evidence。如果要计算的是\(P(J, D=d)\)怎么办？很简单，实际就是直接把D=d代入到上面那个等式中，变成了

\[P(J, D=d) = \sum_{C,I,G,S,L,H} \phi_C(C) \phi_D(C, d) \phi_I(I) \phi_G(G, I, d)...\]

这里需要注意一点，通常factor product出来的是\(\hat P\)而不是\(P\)，需要再normalize，这个例子是BN，它的factor对应条件概率分布，也就没有这个问题了。

\(P(J, D=d)\)是算出来了，但是它不是Conditional Probability Query啊，我们的任务是计算形为\(P(J|D=d)\)的分布吧？下面给出通用步骤。

定义Y为目标变量，E=e为Evidence，令\(W = \{X_1,...,X_n\} - Y - E\)，即余下的所有变量，有如下等式

\[P(Y|E=e) = \frac{P(Y, E=e)}{P(E=e)}\]

这个就是贝叶斯公式

\[P(Y, E=e) = \sum_W P(Y, W, E=e) = \sum_W \frac{1}{Z} \Pi_k \phi_k(D_k, E = e) = \sum_W \frac{1}{Z} \Pi_k \phi^{'}_k(D^{'}_k)\] 

这个其实就是上面那个Sum-Product+Renormalize

\[P(E = e) = \sum_Y P(Y, E=e)\]

把后面那个两个计算式代入贝叶斯公式，发现归一化常量Z是可以被约掉的，所以我们要做的其实就是计算\(\sum_W\Pi_k \phi^{'}_k(D^{'}_k)\)，也就是Sum-Product，然后再做一次renormalize就完事了。注意这里的renormalize使用的归一化常量跟上面第二行公式后注的那个不一样。

计算条件概率的算法有很多，课件中列了一些，在后面课程中都会讲到，包括Variable Elimination，Message Passing以及Random Sampling instantiations。

MAP Inference

这个是第二类问题，给定Evidence E=e，希望能得所有其它变量Y的一个conherent assignment y，使得\(P(Y=y|E=e)\)最大。应用场景包括Message decoding（最可能的原信息），Image segmentation（superpixels上最可能的label assignment）。

MAP is not equal to Max over Marginals! 其实这是句费话，学过点概率统计的应该都知道。

不幸的消息又来了，找使用\(P(X)\)最大的x也是NP-hard问题，甚至于判断\(P(x) > p\)是否成立也是NP-hard的。好在它仍然只在worst case下成立，在average case下还是有希望的。

与Sum-Product相对应的，解决MAP问题使用的方式是Max-Product，而且计算更简单。根据前面写的贝叶斯公式，我们知道选择最优的y只需要考虑分子，因为分母是与Y无关的，而进一步地

\[P(Y, E=e) = \frac{1}{Z} \Pi_k \phi^{'}_k(D^{'}_k) \propto \Pi_k \phi^{'}_k(D^{'}_k)\]

最后一步同样是因为，归一化常量并不影响y之间的相对大小，因此可以忽略。于是我们要得到的就是让最后一个表达式最大的y。

解决MAP的算法也列出一些：Variable Elimination, Message Passing, integer programming, graph-cut method(for some networks), combinatorial search。

如前面提到的，Python的对象可分为可变对象与不可变对象，从另一个角度又可以分为变长对象和定长对象。前一章中的PyIntObject属于不可变对象+定长对象，而本章中的PyStringObject则是不可变对象+变长对象。也就是说，一个Python字符串的长度是非固定的（不同的字符串长度很可能不一样），而当它创建起来之后，就不可以再修改了（因此也可以作为dict的键）。这种不可变性也会使某些字符串操作的效率降低，比如多个字符串的拼接就不得不生成若干的中间对象。

PyStringObject的定义如下

typedef struct {
    PyObject_VAR_HEAD
    long ob_shash;
    int ob_sstate;
    char ob_sval[1];
} PyStringObject;

PyObject_VAR_HEAD宏展开后有一个名为ob_size的变量，它记录了这个字符串的元素个数，而这个字符串的起始位置是由ob_sval指针来指向。这两个指变共同定义了这个字符串，由于有ob_size这个变量，所以可以允许ob_sval到ob_sval+ob_size之间存在'\0'，但是这段内存也必须满足ob_sval[ob_size] == '\0'。另外的两个变量，ob_shash缓存了该对象hash值，初始值为-1；ob_sstate标记了该对象是否已经过intern机制的处理，这个后面会提到。

PyStringObject对应的类型对象是PyString_Type，它也是PyTypeObject的一个实例。其中的tp_itemsize记录了元素的单位长度（即所占用的内存大小），这个tp_itemsize和字符串对象中的ob_size共同决定了这个字符串所占用的内存大小。

字符串的创建有两个方式，PyString_FromString以及PyString_FromStringAndSize，前者要求传入一个以'\0'结尾的字符串，后者则还要传入一个字符串的长度，因此可以允许字符串中包括'\0'。两者差不多，主要看PyString_FromString。

PyObject* PyString_FromString(const char* str)
{
    register size_t size;
    register PyStringObject* op;
    size = strlen(str);
    if(size > PY_SSIZE_T_MAX) {
        return NULL;
    }
    if(size == 0 && (op = nullstring) != NULL) {
        return (PyObject*) op;
    }
    if(size == 1 && (op = characters[*str & UCHAR_MAX]) != NULL) {
        return (PyObject*) op;
    }
    op = (PyStringObject*) PyObject_MALLOC(sizeof(PyStringObject) + size);
    PyObject_INIT_VAR(op, &PyString_Type, size);
    op->ob_shash = -1;
    op->sstate = SSTATE_NOT_INTERNED;
    memcpy(op->ob_sval, str, size+1);
    ...
    return (PyObject*) op;
}

首先检查字符串长度，太大的话拒绝创建；nullstring是一个特殊的字符串对象，表示空串。第一次创建空字符串对象时，nullstring为NULL，所以会走正常流程创建一个PyStringObject，并通过intern机制共享出来，未来再有要求创建长度为0的字符串时就直接返回它了。最后面的一段是真正的创建字符串对象，为PyStringObject及其内部的字符串数组申请内存并初始化，包括对ob_shash和sstate的初始化。

实际上，在return之前，函数内部还做一个intern的动作：

PyObject *t = (PyObject*)op;
PyString_InternInPlace(&t);
op = (PyStringObject*)t;

字符串在被intern之后，整个程序运行期间就只有唯一一个PyStringObject与这个字符串对应，不节省了空间，又简化了对PyStringObject的比较。下面就是这个intern具体的工作：

void PyString_InternInPlace(PyObject** p)
{
    register PyStringObject *s = (PyStringObject*)(*p);
    PyObject* t;
    if(!PyString_CheckExact(s)) {
        return;
    }
    if(PyString_CHECK_INTERNED(s)) {
        return;
    }
    if(interned == NULL) {
        interned = PyDict_New();
    }
    t = PyDict_GetItem(interned, (PyObject*)s);
    if(t) {
        Py_INCREF(t);
        Py_DECREF(*p);
        *p = t;
        return;
    }
    PyDict_SetItem(interned, (PyObject*)s, (PyObject*)s);
    s->ob_refcnt -= 2
    PyString_CHECK_INTERNED(s) = SSTATE_INTERNED_MORTAL;
}

首先要检查传入的对象必须是一个严格的PyStringObject对象，甚至它的派生类都不会做intern。然后，检查这个对象是否已经被intern过了，如果是的话，直接返回，啥都不会干了。再后面就看到，这个intern机制实际就是维护了一个Python dict，它的key和val都是PyObject*类型的。

通过对引用计数的调整也可以看出，这个dict内对字符串对象的引用是不算在引用计数里面的，否则这个对象一旦被intern了，就永远无法释放了。而当一个字符串对象的引用计数降为0时，在string_dealloc销毁这个对象本身的同时，也是清除掉其在interned结构中的指针。

当有一个相同的字符串创建请求时，无论如何会创建出对应的PyStringObject，因为interned这个dict本身就需要以PyStringObject*作为key的。但是如果在intern检查已存在这个对应的PyStringObject，那么会返回intern中的对象，而刚刚创建的那个临时字符串对象就会被瞬间销毁了。

还有一点，被intern的字符串有两种状态：SSTATE_INTERNED_MORTAL, SSTATE_INTERNED_IMMORTAL，区别在于string_dealloc后者是永远不会被销毁的。PyString_InternInPlace只能创建前者，而后则需要调另外的函数接口PyString_InternImmortal，而它实际就是在调用了PyString_InternInPlace之后强制把状态改成了SSTATE_INTERNED_IMMORTAL。

前面在介绍PyString_FromString创建字符串对象时，漏掉了一个地方，就是当size == 1时的情况，此时会用上一个characters的静态数组

static PyStringObject* charaters[UCHAR_MAX+1];

创建之前会先检查要创建的这个字符串对象是否已经存在于characters这个数组中了，如果是的话就直接返回了，不需要再往下执行了。而这个数组是如何创建的呢？实际也在这个PyString_FromString之中，如下

PyStringObject *t = (PyObject*)op;
PyString_InternInPlace(&t);
op = (PyStringObject*)t;
characters[*str&UCHAR_MAX] = op;
Py_INCREF(op);

也就是说，单个字符的PyStringObject在创建后，像其它字符串一样被intern，接下来又被放入了characters这个数组中。就像PyIntObject的小整数对象一样，既在small_ints数据中，也在block_list管理的结构之中。

最后是关于效率的一点提示，由于PyStringObject是不可变对象，因此当有N个字符串连接时，就必须N-1次的内存申请及内存搬运工作，这必然会影响执行效率。官方推荐的方法是先把这些字符串放到一个list或者tuple中，然后使用join操作，这样就只分配一次内存即可。

Python的对象由前面提到的知识可以分为定长对象和变长对象，同时从另一个角度上，Python的对象也可以分为可变对象和不可变对象。本章中的PyIntObject就是一个定长对象+不可变对象。

由于Python的程序中一般会对整数对象的使用极重，如果频繁地创造和销毁是极其影响效率的，因此Python的设计者给出了“整数对象池”这个概念，作为整数对象的缓冲池机制。言归正传，下面是PyIntObject的定义

[intobject.h]
typedef struct {
    PyObject_HEAD
    long ob_ival;
} PyIntObject;

而正如第一章所述，PyObject_HEAD中实际是一个类型对象指针和一个引用计数。PyIntObject对应的类型对象就是PyInt_Type，其就是PyTypeObject的一个实例。

这 个类型对象内容太多，我就不copy了，主要的内容包括名称，大小等基本属性以及一些函数集指针。函数集指针又包括了int_dealloc, int_free, int_repr，int_compare, int_as_number等。特别是最后一个，它定义了作为数值对象的所有可选操作，像int_add, int_sub等。

在Python的实现中，对于一些执行频繁的代码，都同时提供了函数和宏两个版本，比如PyInt_AS_LONG（宏）, PyInt_AsLong（函数），调用者需要在安全和性能上做出选择。

创建一个PyIntObject对象可有三种途径，对应三种不同的输入参数类型，如下，但是实际上这里应用了Adpator Pattern的思想，后两个实际最终都只是通过在接口上做了转换后调用了PyInt_FromLong。

PyObject* PyInt_FromLong(long ival)
PyObject* PyInt_FromString(char* s, char** pend, int base)
PyObject* PyInt_FromUnicode(Py_UNICODE* s, int length, int base)

程序在运行期间，Python的整数对象并不是孤立存在地，而是形成了一个整数对象系统。先来看小整数对象。

由 于Python对象在运行期间都在存活在系统堆上的，因此如果没有优化机制，而是对这些频繁使用的小整数对象进行malloc和free，那么不仅降低运 行效率，也会造成内存碎片。因此小整数对象使用了对象池技术，同时由于整数对象是不可变对象，所以对象池中的对象都是被任意共享的。

那么多小的整数才算是小整数呢？默认范围是[-5, 257），当然也可以改，但是就得自己重新编译一遍源码了。

#define NSMALLPOSINTS 257
#define NSMALLNEGINTS 5
#if NSMALLPOSINTS + NSMALLNEGINTS > 0
    static PyIntObject* small_ints[NSMALLPOSINTS + NSMALLNEGINTS];
#endif

对于大整数对象了，Python运行环境提供一块内存，这些内存由大整数轮流使用，从而避免了不断malloc的工作。而 这块内存也是有自己的结构的，它是由一个称为block_list的指针维护的一个单向链表，其中每一个结点称为一个PyIntBlock，而每个 block中又维护着N_INTOBJECTS个PyIntObject对象，即objects数组。

struct _intblock {
    struct _intblock *next;
    PyIntObject objects[N_INOBJECTS];
};
typedef struct _intblock PyIntBlock;

static PyIntBlock* block_list = NULL;
static PyIntObject* free_list = NULL;

在Python运行的某个时刻，通常有一些block中的某些object正在被使用，而其它的则处于空闲状态，为了把这些空闲object组织起来，就有了free_list，它作为链表的表头，把所有空闲内存串成另一个单链表。

PyIntObject的创建过程中，上面的结构是如何起作用的呢？

首先，程序会检查是否有小整数对象池，如果有的话再检查要创建的这个PyIntObject是不是在小整数范围内，如果是的话，直接返回；如果上面的条件无法满足，那么就会求助于block_list和free_list，寻找一块可用的PyIntObject对象的内存。

if(free_list == NULL) {
    if((free_list = fill_free_list()) == NULL)
        return NULL;
}

v = free_list;
free_list = (PyIntObject*)v->ob_type;
PyObject_INIT(v, &PyInt_Type);
v->ob_ival = ival;
return (PyObject*) v;

当第一次调用PyInt_FromLong时，free_list是空（另外，当没有空闲block时它也是空），那么就会调用fill_free_list函数来创建新的内存。

// fill_free_list
PyIntObject *p, *q;
p = (PyIntObject*) PyMem_MALLOC(sizeof(PyIntBlock));
((PyIntBlock*)p)->next = block_list;
block_list = (PyIntBlock*) p;

p = &((PyIntBlock*)p)->objects[0];
q = p + N_INTOBJECTS;
while(--q > p)
    q->ob_type = (struct _typeobject*)(q-1);
q->ob_type = NULL;
return p + N_INTOBJECTS -1;

实际工作就是加一块block，放在block_list的头部，所以block_list总是会指向最新创建的PyIntBlock对象；然后对于其内部的所有PyIntObject，利用ob_type从后到前串起来， 最后返回最后一个object的位置作为free_list的赋值。

此时free_list只管理了一个block下的所有空闲 objects，block之间的objects如何关联呢？这发生在一个PyIntObject的引用计数减少到0的时候：在int_dealloc内，它会将自己的ob_type指针原free_list，再将free_list指向这个刚刚销毁的object。从这里也能看出，如果一块内存被申请 用作PyIntObject，那么它就永远不会归还给OS，而是一直保留着，因此PyIntObject占用的内存大小与同时共存的整数个数最大值有关。

如果要删除的对象是一个整数的派生类对象，那么int_dealloc也不会做任何动作，只是调用其类型对象中的tp_free。

最后要看的是小整数对象的创建时机：它们是在python初始化的时候，调用_PyInt_Init时被调用的。small_ints中保存的object 也是被block_list和free_list来管理的，只不过它们是永生不灭的，因此small_ints中总会贡献一次引用计数。

Pairwise Markov Networks

前面的讲的Bayesian Network是有向图，这节说的Markov Networks是无向图。从最简单的pairwise的case说起。

有向图的局部结构所表达的意义很明确，比如从A到B的结构，表示的就是\(P(B|A)\)，而无向图则因为没有方向的概念，它就没有直接且有意义的概率分布来表示，所以只好用factor的概念来做抽象描述。

（我发现我越来越懒了，各种截图）

上面是一个例子，每个变量取值非零即一，而每条边上对应的factor，比如\(\phi (A,B)\)就表示这两个变量在各种取值下的权重，这里A和B取值相等时权重更高，表示这两个变量是比较正相关的。但是需要注意的是，每个factor都只是一个局部信息，它不会直接对应到我们最终得到的联合概率分布，甚到不能直接对应到与这两个变量相关的边缘分布或者条件分布上。这一点与Bayesian Network非常不同，用后面的例子一看就清晰了。

在有了这些factors之后，我们想要算这些变量的联合分布，做法就是直接利用factor product（如下），然后normalize一下就哦了。

\[ P(A,B,C,D) = \phi_1(A,B) * \phi_2(B,C) * \phi_3(C,D) * \phi_4(A,D)\]

有了联合分布，自然可以算出一个边缘分布来，上面这个表格就是计算出来的\(P(A,B)\)，对比一下包含局部信息的\(\phi(A,B)\)，可以发现两者有天壤之别。原因就在于前面关于A和B的整体信息（实际上是受了C，D之间强烈取值不一致权重高的影响），而后者只是局部信息。

下面就是Pairwise Markov Networks的定义：一个包含结点\(X_1,...,X_n\)和边\(X_i, X_j\)的无向图，每条边上都有一个\(\phi_{ij}(X_i, X_j)\)，这个东西就是Pairwise Markov Networks。这里的Pairwise体现在，每个factor的domain只有两个变量。

General Gibbs Distribution

书接上回，前面提到了Pairwise的case中，每个factor中只涉及两个变量，它的表达能力足够了吗？我们考虑一个fully connected的pairwise MN，即任意两个变量之间都有一个factor，假设共有N个变量，且每个变量可以有d个取值，那么这些factor的product可以产生的组合数就是\(O(n^2d^2)\)，而实际上这N变量的联合概率分布应该是有\(O(d^n)\)个组合，二者之间还有有很大差距，这说明pairwise MN的表达能力并不足够。

为解决这个问题，就有人提出了Gibbs Distribution的概念，即定义一些General Factor \(\phi_i(D)\)，其中每个D可能包含一个或者多个变量（而不是pairwise中的2个变量），把这些factors集中在一起表示为\(\Phi = {\phi_i(D_i)}\)，后面的就都一样了，factor product+normalization，不费话了。所以实际上Gibbs Distribution所做的就是对每个factor的domain中的变量个数扩展到了任意个，同样的问题，这样表达能力就足够了吗？必须的，因为定义一个包含所有变量的factor都是可行的。

但是这种一个factor中有多个变量的形式，如何对应到Markov Network上呢，这个图咋画呢？结论就是Induced Markov Network，即当存在一个\(\phi_m \in \Phi\)，使得\((X_i, X_j) \in D_m\)时，就在这两个结点之间连上一条边，画上所有的这些边，就形成了Induced Markov Network。

有了分布P，又有个图H，那么就可以把BN的那套东西搞过来了。

首先是Factorizatioin的概念，当存在一个factor的集合\(\Phi\)，使用得\(P = P_{\Phi}\)并且H是\(\Phi\)的Induced graph时，就说P factorizes over H。实际上就是以\(\Phi\)作为中介，把P和H联系起来了。因为不同的\(\Phi\)可能会生成相同的H，所以H并不能完整表达P中的信息。

Flow of Influence：这个比BN要简单得多，没有什么v-structure这么变态的东西，只有在两个变量之间有一条active trail（即这条路径上没变量是被observed），那就这条influence就是通的。而且，两个变量间influence可能有多条活跃路径。最后，这种influence只依赖于这个graph，不依赖于factors。

Conditional Random Field

这东西跟前面的Gibbs Distribution很类似但是归一化方式不同，这也造就了它独特的地方和应用场景，当在做某些预测Y的任务而不想关心X_i之间的关联时还是很有用的。

假设有一组变量\(X_1,...,X_n\)，以及一个目标变量Y，我们想做就是找到从X到Y之间的条件分布\(P(Y|X)\)，以帮忙我们通过观测到一系列X来预测未知的Y。在图像实体识别中，X可以是图像中的元素值，Y可以是object label；在文本处理的例子中，X可以是句子中的各个word，而Y则是POS tag。

CRF具体形式与Gibbs分布几乎就是一样的，给定\(\Phi\)，然后利用factor product来得到unormalized measure，表示为\(\hat P\)。不同之处在于，后面归一化项（或者称为partition function）是不同的，如下

For Gibbs Distribution: \(Z = \sum_{X,Y} \hat P(X, Y)\)

For CRF: \(Z(X) = \sum_{Y} \hat P(X, Y)\)

前者归一化后得到的是联合概率分布\(P(X, Y)\)，而后者得到的则是条件概率分布\(P(Y|X)\)。

这个玩意儿有什么用处呢？假设所有factors的形式都是\(\phi(X_i, Y)\)，即没有任何的X变量之间的信息，如何我们使用这些factors来计算联合分布的话，实际上我们就做出了如朴素贝叶斯般的假设，即所有的X之间是独立的，显然这种假设在某些情况下是很粗暴的。而像前面提的这种通过X预测Y的场景下，X之间有啥关系我们是不关心的，我们只是想了解它们如何影响Y的取值，这种情况下利用CRF计算得到的条件概率分布就足够满足我们了，而不用去关心X之间会有什么联系。换个角度来说，前者计算出的联合分布实际是一个信息最全的分布，因为通过联合分布可以计算任意的条件分布和边缘分布，包括X之间的关联，但是有些信息我们实际是不关心的，也没有必要去model的；而条件概率分布虽然信息不如联合分布全（比如它就没有X之间关系的信息），但是对于我们的预测任务来说是足够的了。

课程中又提到CRF跟很多现有模型是有非常强的关联的，比如，Logistic Model就是CRF的一种特殊形式，很有意思，但是推导过程我就不写了，贴个图了事。

最后抄一句话做总结：CRF allows models with highly expressive features, without worrying about wrong independencies.

Independecies in Markov Networks

从这里开始会有一些很概念性的东西，虽然挺烦，但还是得写写。多数概念都是BN那边迁移过来的。

Seperation in MN: X and Y are separated in H given Z if there is no active trail in H between X and Y given Z.

I-Map：MN中的独立性集合表示为\(I(H) = {(X \perp Y| Z): sep_H(X, Y|Z)}\)，如果P满足这个\(I(H)\)，那么就说H是P的一个I-map。

Factorization => Indepedencies: If P factorizes over H, then H is an I-map of P. (If P factorizes over a graph H, we can read from the graph independencies that must hold in P (an independency map).)

Factorization <= Indepedencies: For a positive distribution P, if H is an I-map for P, then P factorizes over H.

我的一点理解是，H中的信息总是P的一个子集，P能够factorization不代表它所有的信息都能表达在H中。

I-maps and Perfect Maps

如果我们把一个概率分布P中所有的独立性约束都提取出来，表示为\(I(P)\)，那么对于P的任意一个I-map来说，都有\(I(G) \in I(P)\)，而反向则并不总是成立的。换句话说，G中的独立性约束总是P的一个子集，可能无法完整表达P中蕴含的信息。

当然，理想情况下，对于一个P，我们希望能得到一个能表达其完整的独立性信息的图G，因为这样的话，G中就包含了所有P中的独立性条件，图不但会更加informative，也会变得更加稀疏（因此也就会有更少的参数）。我们定义当满足\(I(G) = I(P)\)时，就称它为Perfect Map。

理想很丰满，但现实很骨感，对于一个P来说，想得到它的Perfect Map通常是很难的。举几个例子，

• 假设一个pairwise MN，而P是由它导出的一个包含其所有独立性信息的概率分布，我们希望得到一个BN的使其成为Perfect Map。事实证实，找不到这个样Perfect Map。
• 反过来，假设v-structure的BN，而P是由它导出的，我们希望能得一个包含Perfect Map的MN，事实证实，也是找不到的。
• 另外还有一个XOR的例子，我就不多说了。

前两个例子也说明，BN与MN之间的等价转换有时是不可行的，总是可能会丢失掉一些原有的信息。

更加让人崩溃的是，即使我们找到一个P对应的Perfect Map，也不能保证它是唯一的。比如，最简单BN模型，A->B, A<-B两个图的所表达的独立性信息就是相同的（实际都是空集）；再比如，三个变量的情况，除了v-structure中的X->Y<-Z之后，另外的三种图也是表达了相同的独立性信息。当两个图G,H中所包含的独立性信息相同，即\(I(G) = I(H)\)，那么就称二者是I-equivalent。多数图都有对应的很多I-equivalent变种。

Log-Linear Models

对于MN，除了使用factor product+normalize来表达联合概率分布外，还可以使用log-linear model来实现，表达式为

Factor Product: \(\hat P = \Pi_i \phi_i(D_i)\)

Log-linear Representation: \(\hat P = exp(-\sum_j w_j f_j(D_j)) = \Pi_j exp(-w_j f_j(D_j))\)

每个i表示factor的索引，每个\(D_i\)是相对于这个对应的factor来说的；相应地，每个j是feature的索引，所以\(w_j, D_j\)都是相对于这个feature的，也就是说每个feature会有一个对应的权重及它的scope。而不同的feature也可以有相同的scope。另外，需要注意一点，factor的scope和feature的scope甚至可以是不相关，因为feature和factor可以不存在一一对应的关系，从这个意义上讲，Log-linear Representation中的最后一个表达式中，每个\(exp(-w_j f_j(D_j))\)可以看作是重新定义的一个factor。

上面是两种不同的对联合分布的表示方法，所以需要首先证明Factor方式是可以等价地表达后Log-linear方式的。

假设有一个\(\phi(X_1, X_2), X_i \in {0, 1}\)，这个factor的取值分别为\(a_{00}, a_{01}, a_{10}, a_{11}\)，其中每个\(a_{ij} = \phi(X_1 = i, X_2 = j)\)。现在我们定义4个feature，分别为

\[f_1 = I\{X_1 = 0, X_2 = 0\}\]

\[f_2 = I\{X_1 = 0, X_2 = 1\}\]

\[f_3 = I\{X_1 = 1, X_2 = 0\}\]

\[f_4 = I\{X_1 = 1, X_2 = 1\}\]

其中I表示indicator function。于是，我们得到如下等式\(\phi(X_1, X_2) = exp(-\sum_k w_k f_k(X_1, X_2))\)，其中\(w_k\)为对应的\(a_{ij}\)的对数的相反数。这4个feature的scope是相等的，也对应了前面所说的“不同的feature也可以有相同的scope”。

后面就是一些应用的例子了。

首先是对于单词的注标问题，X表示当前的单词，Y表示这个单词的label。基于对这个领域的理解，我们可以定义如下的features

\[f_1(Y, X) = I\{Y = B\_PER, X~is~capitalized\}\]

\[f_2(Y, X) = I\{Y = B\_LOC, X~appears~in~atlas\}\]

......

然后就可使用这些features去构建一个log-linear model，表达对应的联合概率分布\(P(Y, X)\)。

第二个例子是Ising Model，没听懂具体是干什么用的，它的结构是pairwise MN，每个变量\(X_i \in {-1, +1}\)，定义两种features，一种是单变量的\(f_i(X_i) = u_i X_i\)，另一种是双变量的feature，即\(f_{i, j}(X_i, X_j) = X_i * X_j\)，其中\(f_{i, j}\)是说这个feature只会应用于\(X_i, X_j\)这两个变量上（scope），后面的内容会对它做扩展，这里先不管。对应的联合分布的表达式为

\[P(X) = exp(-\frac{1}{T} E(X))\]

\[E(X) = -\sum_{i<j} w_{ij} X_i X_j - \sum_i u_i X_i\]

最后一个例子是Metric MRF。一种被特别提到很常用feature称为metric，而它所对应的MN被称为metric MRF。在使用metric MRF的应用中，通常都希望相连的两个变量有相似的取值。

metric实际就是一个距离函数\(\mu : V * V \to R^{+}\)，其中V是每个变量\(X_i\)的取值空间。这个距离函数要求满足三个基本属性：自反性，对称性以及三角不等式条件。

\[f_{i, j}(X_i, X_j) = \mu (X_i, X_j)\]

\[P(X) = exp(-\sum_{i, j} w_{i, j} f_{i, j}(X_i, X_j))\]

这样就满足了当有边相联的两个变量取值不相似（即距离较远时），它会拉低这个assignment整体的联合概率。

一些常用的metric函数定义

第一个定义就是说，只有当两个变量的取值相等时，距离为0，否则就为1；应用场景可以是image segmentation，它要求相邻的superpixel要共享同一个object label。

第二个定义就是取两个变量取值的差的绝对值，但是正如左下方的那图示意的一样，这个距离值可能是无界的，所以可以像右下角那样做一个truncate。对应的例子是图像除噪，假设有一幅有噪声的图像，其像素值表示为\(X_i\)，我们希望得到的是除噪后的图像，其像素表示为\(Y_i\)，约束条件是每个\(Y_i\)要与\(X_i\)接近，并且\(Y_i\)也要与它的邻像素值接近。如果采用未作truncate的metric函数，那么可能过于严苛，造成\(Y_i\)也要与它的邻像素值过于接近，而实际上这个局部特点并不是那么要严格遵守的，像物体边界上的像素值是有可能与其邻像素不一样的。这种应用场景下，truncate后的metric函数就更合适。

但是它相对于factor形式有什么优势呢？我的理解是，它可能更有利于adapt到某个特殊的领域，可以人工设计一些feature并很方便地将它们融入到模型中。

Shared Features in Log-Linear Models

回到刚才的Ising Model，当时就提了一下“\(f_{i, j}\)是说这个feature只会应用于\(X_i, X_j\)这两个变量上”，实际上这个feature可以不局限于仅仅是这两个特定的变量，可以是任何两个相邻的变量，同时这个feature对应的权重\(w_{ij}\)也是可以共享的。

\[-\sum_{i, j} w_{i, j} f_{i, j}(X_i, X_j) \to -\sum_{i, j} w f(X_i, X_j)\]

同样方式可以用到单词标注的问题上，对于任意的\(X_i, Y_i\)都可以定义通用的feature，而不必每一对变量都定义一个。Image Segmentation的例子也是如此。

因此，我们只需要为每个feature \(f_k\)定义一组scopes，表示为\(Scopes[f_k]\)，然后就有\(w_k \sum_{D_k in Scopee[f_k]} f_k(D_k)\)。

总之，相同的参数和结构模板可以同一个MN中复用（同一句话中不同的word及对应的label），同时也可以在不同的MN中复用（不同的句子中）。

(END OF THIS SECTION)