1. After reading about the Y combinator in the book The Little Schemer, simply staring at its code becomes a great way to kill time. In the past few days, whenever I got bored (or need an excuse for procrastination), I spent hours trying to make sense out of its mysterious implementation. It’s like monad: everybody has a hard time reaching that "Eureka" moment, but once he finally groks it, he believes that he can explain it more clearly than the tutorial he read (which is often not the case).

So here I am writing yet another Y combinator tutorial. I think the reason why Y combinator is so hard to fathom is that when you read the code, you are facing its entire complexity. In fact, however, its derivation can be broken into a few fairly intuitive steps, and if each step is well-motivated, we no long need a "Eurika" to understand the whole thing.

The code snippets in this tutorial are written in Racket, but it should be trivial to translate them into other Lisp dialects or other dynamic functional languages. 

## Y? Why?

Before deriving the Y combinator, let see what it is about. Consider the following ...

2. There’s an increasingly heated debate about Scala’s complexity. A recent post talks about Scala’s "true complexity": the terrifying intricacy you will encounter, if you try to extend Scala’s Collections Library with a method that achieves the "perfect" behavior.

Yet it also might be worth asking: what are the motivations of these "perfect" behaviors? Are they always desirable?

One important aspect of the "perfect" collection behavior is the magical uniform return type principle. Sloppily speaking, this means that transforming a collection should give you another collection of the same kind. For instance:

// Filtering a List gives you a filtered List
scala> List(1,2,3,4).filter(_%2==0)
res: List[Int] = List(2, 4)

// Mapping a Set gives you a mapped Set
scala> Set(1,2,3,4).map(1+)
res: scala.collection.immutable.Set[Int] = Set(2, 3, 4, 5)

// Uniform return type at both compile time and runtime
scala> val iterable : Iterable[Int] = Set(1,2,3,4)
iterable: Iterable[Int] = Set(1, 2, 3, 4)

scala> iterable.map(1+)
res: Iterable[Int] = Set(2, 3, 4, 5)

// Works for Strings, too
scala> "E is the most frequent letter in English".map(
|    c ...
3. Probabilistic latent semantic analysis (概率潜在语义分析，pLSA) 是一种 Topic model，在99年被 Thomas Hofmann 提出。它和随后提出的 LDA 使得 Topic Model 成为了研究热点，其后的模型大都是建立在二者的基础上的。

我们有时会希望在数量庞大的文档库中自动地发现某些结构。比如我们希望在文档库发现若干个“主题”，并将每个主题用关键词的形式表现出来。 我们还希望知道每篇文章中各个主题占得比重如何，并据此判断两篇文章的相关程度。而 pLSA 就能完成这样的任务。

我之前取了 Wikinews 中的 1000 篇新闻，试着用 pLSA 在其中发现 K=15 个主题。比如一篇关于 Wikileaks 的阿萨奇被保释消息的新闻，算法以 100% 的概率把它分给了主题 9，其关键词为：

media phone hacking wikileaks assange australian stated information investigation murdoch

可以看到这个主题的发现还是非常靠谱的。又比如这条中国人民的老朋友威胁要大打打核战争 的新闻。 算法把它以 97.7% 的概率分给了主题 3，2.3% 的概率分给了主题 7。主题 3 的关键词是：

south north court china military death tornado service million storm

主题 7 的关键词是：

nuclear plant power japan million carbon radiation china water minister

可以看到这条新闻和主题 3 中的“南北”、“军事”、“中国”、“死亡”这些信息联系在一起，和主题 7 中的“核”、“中国”联系在一起。 应该是因为我的数据集中与北朝鲜核问题相关的新闻只有不到 10 条，而 10 个主题的划分并不够细致，所以关于“朝核问题”或者“核武器”的这样的主题并没能被分离出来。但可以看到即使是这样结果也是很 make sense 的。

那我们就来看看 pLSA 模型是怎么回事吧。和很多模型一样，pLSA 遵从 bag-of-words 假设， 即只考虑一篇文档中单词出现的次数，忽略单词的先后次序关系，且每个单词的出现都是彼此独立的。 这样一来，我们观察到的其实就是每个单词 $$w \in W$$ 在每篇文档 $$d \in D$$ 中出现的次数 $$n(w,d)$$。 pLSA 还假设对于每对出现的 $$(d,w)$$ 都对应着一个表示“主题”的隐藏变量 $$z \in Z$$。 pLSA 是一个生成模型，它假设 $$d$$$$w$$$$z$$ 之间的关系用贝叶斯网络表示是这样的（从 [Blei03] 偷的图）： 实心的节点 $$d$$$$w$$ 表示我们能观察到的文档和单词，空心的 $$z$$ 表示我们观察不到的隐藏变量，用来表示隐含的主题。图中用了所谓的“盘子记法”， 即用方框表示随机变量的重复。这里方框右下角的字母 $$M$$$$N$$ 分别表示有 $$M$$ 篇文档，第 $$j$$ 篇文档有 $$N_j$$ 个单词。每条有向边表示随机变量间的依赖关系 ...

4. Expectation-Maximization 算法是统计学中用来给带隐含变量的模型做最大似然（和最大后验概率）的一种方法。EM 的应用特别广泛，经典的比如做概率密度估计用的 Gaussian Mixture Model。这两天我或许还会写 p 的笔记放上来，也是 EM 应用的例子。

下面我会先解释 EM 算法要解决的问题，然后直接给出算法的过程，最后再说明算法的正确性。

## 问题

首先我们定义要解决的问题。给定一个训练集 $$X=\{x^{(1)},…,x^{(m)}\}$$，我们希望拟合包含隐含变量 $$z$$ 的模型 $$P(x,z;\theta)$$ 中的参数 $$\theta$$。根据模型的假设，每个我们观察到的 $$x^{(i)}$$ 还对应着一个我们观察不到的隐含变量 $$z^{(i)}$$，我们记 $$Z=\{z^{(1)},…,z^{(m)}\}$$。做最大对数似然就是要求 $$\theta$$ 的“最优值”：

\begin{equation*} \theta=\arg\max_\theta{L(\theta;X)} \end{equation*}

其中

\begin{equation*} L(\theta;X)=log{P(X;\theta)}=\log{\sum_Z P(X,Z;\theta)} \end{equation*}

想用这个 $$\log$$$$\sum$$ 的形式直接求解 $$\theta$$ 往往非常困难。而如果能观察到隐含变量 $$z$$ ，求下面的似然函数的极大值会容易许多：

\begin{equation*} L(\theta;X,Z)=\log{P(X, Z;\theta)} \end{equation*}

问题是实际上我们没法观察到 $$z$$ 的值，只能在给定 $$\theta$$ 时求 $$z$$ 的后验概率 $$P(z|x;\theta)$$ EM 算法就可以帮我们打破这样的困境。

## 算法

下面给出 EM 算法的过程。其中 $$\theta_t$$ 是第 t-1 次迭代时算出的 $$\theta$$ 值；$$\theta_0$$ 为任意初值。

Repeat until converge {

1. (E-step) 计算 $$P(Z|X;\theta_t)$$ 以得到

\begin{align*} E_{Z|X;\theta_t}[L(\theta;X,Z)] &:= E_{Z|X;\theta_t}[\log{P(X,Z;\theta)}] \\ &= \sum_Z P(Z|X;\theta_t) \log{P(X,Z;\theta)} \end{align*}
2. (M-step)

\begin{equation*} \theta_{t+1} := \arg\max_\theta E_{Z|X;\theta_t}[\log{P(X,Z;\theta)}] \end{equation*}

}

对，就这么短 ...

5. 谢谢你，因为这183天中的每时每刻，因为那所有的一切。

别了。

Page 1 / 9