数学之美 系列十六 (下)- 不要把所有的鸡蛋放在一个篮子里 最大熵模型

发表者:Google 研究员,吴军

我们上次谈到用最大熵模型可以将各种信息综合在一起。我们留下一个问题没有回答,就是如何构造最大熵模型。我们已经所有的最大熵模型都是指数函数的形式,现在只需要确定指数函数的参数就可以了,这个过程称为模型的训练。

最原始的最大熵模型的训练方法是一种称为通用迭代算法 GIS(generalized iterative scaling) 的迭代 算法。GIS 的原理并不复杂,大致可以概括为以下几个步骤:1. 假定第零次迭代的初始模型为等概率的均匀分布。2. 用第 N 次迭代的模型来估算每种信息特征在训练数据中的分布,如果超过了实际的,就把相应的模型参数变小;否则,将它们便大。3. 重复步骤 2 直到收敛。

GIS 最早是由 Darroch 和 Ratcliff 在七十年代提出的。但是,这两人没有能对这种算法的物理含义进行很好地解释。后来是由数学家希萨(Csiszar)解释清楚的,因此,人们在谈到这个算法时,总是同时引用 Darroch 和Ratcliff 以及希萨的两篇论文。GIS 算法每次迭代的时间都很长,需要迭代很多次才能收敛,而且不太稳定,即使在 64 位计算机上都会出现溢出。因此,在实际应用中很少有人真正使用 GIS。大家只是通过它来了解最大熵模型的算法。

八十年代,很有天才的孪生兄弟的达拉皮垂(Della Pietra)在 IBM 对 GIS 算法进行了两方面的改进,提出了改进迭代算法 IIS(improved iterative scaling)。这使得最大熵模型的训练时间缩短了一到两个数量级。这样最大熵模型才有可能变得实用。即使如此,在当时也只有 IBM 有条件是用最大熵模型。

由于最大熵模型在数学上十分完美,对科学家们有很大的诱惑力,因此不少研究者试图把自己的问题用一个类似最大熵的近似模型去套。谁知这一近似,最大熵模型就变得不完美了,结果可想而知,比打补丁的凑合的方法也好不了多少。于是,不少热心人又放弃了这种方法。第一个在实际信息处理应用中验证了最大熵模型的优势的,是宾夕法尼亚大学马库斯的另一个高徒原 IBM 现微软的研究员拉纳帕提(Adwait Ratnaparkhi)。拉纳帕提的聪明之处在于他没有对最大熵模型进行近似,而是找到了几个最适合用最大熵模型、而计算量相对不太大的自然语言处理问题,比如词性标注和句法分析。拉纳帕提成功地将上下文信息、词性(名词、动词和形容词等)、句子成分(主谓宾)通过最大熵模型结合起来,做出了当时世界上最好的词性标识系统和句法分析器。拉纳帕提的论文发表后让人们耳目一新。拉纳帕提的词性标注系统,至今仍然是使用单一方法最好的系统。科学家们从拉纳帕提的成就中,又看到了用最大熵模型解决复杂的文字信息处理的希望。

但是,最大熵模型的计算量仍然是个拦路虎。我在学校时花了很长时间考虑如何简化最大熵模型的计算量。终于有一天,我对我的导师说,我发现一种数学变换,可以将大部分最大熵模型的训练时间在 IIS 的基础上减少两个数量级。我在黑板上推导了一个多小时,他没有找出我的推导中的任何破绽,接着他又回去想了两天,然后告诉我我的算法是对的。从此,我们就建造了一些很大的最大熵模型。这些模型比修修补补的凑合的方法好不少。即使在我找到了快速训练算法以后,为了训练一个包含上下文信息,主题信息和语法信息的文法模型(language model),我并行使用了 20 台当时最快的 SUN 工作站,仍然计算了三个月。由此可见最大熵模型的复杂的一面。最大熵模型快速算法的实现很复杂,到今天为止,世界上能有效实现这些算法的人也不到一百人。有兴趣实现一个最大熵模型的读者可以阅读我的论文。

[…]

关于Gmail改变”更多选项”设计的问题

1、上午和GOOGLE的一位PM在聊天中得知Gmail一点新的UI变化  x: "Gmail界面有一点点update",  b: "我早上来了之后一直在用。 但我用的是中文版本 好像还没有看到"  x: "回信由链接便成图标了。    哦!有可能要过几天"

2、把语言改成英文后我看到: 3、对比一下尚未升级的中文版本可以发现:  a 左下角的"回复"、"转发"加了图标,用户可以更加方便的找到这两个操作;  b 取消了原来的"更多选项"。  c 在右上角显示"回复"功能,并把取消了的"更多选项"在此"回复"后面用需要触发"下箭头"的下拉菜单显示。

4、对于这个改变我的第一反应是"太棒了,这个改变很好! 我喜欢.." 但细看以后,我只能给它打70分!(另外的30分在下面5、6、7三点中有说明) 我想说"改动大的初衷很好,想法也很棒。 但是不少细节的东西需要继续斟酌.."

5、把"更多选项"改成需要触发"下箭头"的下拉菜单显示是一个小冒险,表现上也有些牵强.因为老用户并不能立即从很容易看到的"文字"过渡到"躲在没有明显标示的箭头后面的下拉菜单"。  a单就"用户想用某个功能如何很快找到"的问题,这个改变对于Gmial所针对对的典型用户群来说并不是什么大的问题,因为这部分人大都是"高级用户"。而且除去"回复"后,另外的那些更多选项其实非常不常用。  b但,这里也会引起一个歧义:在没有展开菜单的时候,可能会有用户认为:"这个下箭头是'回复'的其他高级选项,而不会认为这里是'更多选项'"。因为不是所有用户都明白"回复加下箭头其实就是原来的'更多选项'"。  c特别是当他可以在同一个界面中看到"回复""转发"两个选项的时候,他甚至会认为"Gmail现在改的只有这两个操作并没有其他操作功能了"  e更多时候这种设计的预设逻辑是:"回复和下箭头是一起的同类操作,他们表示这里有很多类似的“回复”选择,'回复'只是其中的某个默认项"。但这里"回复"和那些展开的功能严格来说不能属于一项,放到一起有些牵强。  f fliker把它的搜索这么做了,但那些选项都同属于搜索一类的,所以他的做法我很喜欢(如果可以记录我上次搜索选项的判断就更好了)。  g所以,单就细节来说这个地方可以把"下箭头"处理成文字或者文字加ICON的形式更合适一点。

6、 通过上面这张图我们不难看出: 在同一个界面中,很近的两个地方出现了同样的一个功能,而且这两个地方相对于整个界面来说都很明显。 这一点我以前说过hotmail作的很有技巧。 就算非得要两个选项(很多时候我认为上边没有放操作选项的必要,但这好像已经成了一种大家都这么干的规矩,所以就不去过多计较了),这里也完全可以做一个判断,当字数少于多少时左下角的两个选项不显示。 而且更多时候大概没有多少人在中途回复或者转发,他们是要看到最下面的一个才去回复或者转发。 所以一般情况下有右上角的那个选项就可以做到了,只有当邮件很长 用户不方便把滚动条拖上去操作的时候左下角的操作才最有作用。

7、 这里就更奇怪了,一眼看上去有三个地方是同样一个功能,而且这三个地方都很突出。 (右上角"回复"、左下脚"回复"、"输入框"点一下也是回复)! 其实道理一样,最后一个栏目左下角的"回复""转发"完全没有必要!把它们去掉保留输入框其实就可以了。点下去以后出来现在一样的效果。默认是"回复",如果用户需要"转发"只切换一下TAB就可以了。

8、另外一个问题:下图中GMAIL这种GOOGLE式的问答逻辑也很奇怪 A我一直说:这样的问答式逻辑其实是带着用户绕弯子。无缘无故给他们带去了很多的问号! B我选择“是”还是“不希望”呢? 选择“是”是不是就意味着我所有的语言都是英文没法再看到中文了? 选择“不希望”是不是我刚才的语言设计不会起效果呢? 这句话到底如何理解呢??? 。。。 C其实完全没有必要显示这一步,直接成为默认就可以了,如果用户不需要可以改回去嘛。已经从中文改到英文了,如果他再想用中文的时候改回去应该是很熟练的事情了。 D或者正如maomaoma所说:在语言设置的源头上就把这个选择题让用户作了,是个很好的办法。如,在用户选择语言的同时用checkbox或者下拉选项让他可以选择语言应用的范围(其实更多时候用户只是去看一下默认的那个 选项而已)。 E就算非得用再次提示用户选择这一步,也许可以有别的方式更合适点。 […]

Category

Archives