[我们在投资时常常讲不要把所有鸡蛋放在个篮子里这样可以降低风险在信息处理中这个原理同样适用在数学上这个原理称为最大熵原理(the maximum entropy principle)这是个非常有意思题目但是把它讲清楚要用两个系列篇幅]

　　前段时间Google 中国研究院刘骏总监谈到在网络搜索排名中用到信息有上百种更普遍地讲在自然语言处理中我们常常知道各种各样但是又不完全确定信息我们需要用个统模型将这些信息综合起来如何综合得好是门很大学问

　　让我们看个拼音转汉字简单例子假如输入拼音是"wang-xiao-bo"利用语言模型根据有限上下文(比如前两个词)我们能给出两个最常见名字“王小波”和“王晓波”至于要唯确定是哪个名字就难了即使利用较长上下文也做不到当然我们知道如果通篇文章是介绍文学作家王小波可能性就较大；而在讨论两岸关系时台湾学者王晓波可能性会较大在上面例子中我们只需要综合两类区别信息即主题信息和上下文信息虽然有不少凑合办法比如:分成成千上万种区别主题单独处理或者对每种信息作用加权平均等等但都不能准确而圆满地解决问题这样好比以前我们谈到行星运动模型中小圆套大圆打补丁思路方法在很多应用中我们需要综合几十甚至上百种区别信息这种小圆套大圆思路方法显然行不通

　　数学上最漂亮办法是最大熵(maximum entropy)模型它相当于行星运动椭圆模型“最大熵”这个名词听起来很深奥但是它原理很简单我们每天都在用说白了就是要保留全部不确定性将风险降到最小让我们来看个实际例子

　　有次我去 AT&T 实验室作有关最大熵模型报告我带去了个色子我问听众“每个面朝上概率分别是多少”所有人都说是等概率即各点概率均为1/6这种猜测当然是对我问听众们为什么得到回答是致:对这个“无所知”色子假定它每个朝上概率均等是最安全做法(你不应该主观假设它象韦小宝色子样灌了铅)从投资角度看就是风险最小做法从信息论角度讲就是保留了最大不确定性也就是说让熵达到最大接着我又告诉听众我这个色子被我特殊处理过已知 4点朝上概率是 3分的在这种情况下每个面朝上概率是多少？这次大部分人认为除去 4点概率是 1/3其余均是 2/15也就是说已知条件( 4点概率为 1/3)必须满足而对其余各点概率仍然无从知道因此只好认为它们均等注意在猜测这两种区别情况下概率分布时大家都没有添加任何主观假设诸如 4点反面定是 3点等等(事实上有色子 4点反面不是 3点而是点)这种基于直觉猜测的所以准确是它恰好符合了最大熵原理

　　最大熵原理指出当我们需要对个随机事件概率分布进行预测时我们预测应当满足全部已知条件而对未知情况不要做任何主观假设(不做主观假设这点很重要)在这种情况下概率分布最均匀预测风险最小这时概率分布信息熵最大所以人们称这种模型叫“最大熵模型”我们常说不要把所有鸡蛋放在个篮子里其实就是最大熵原理个朴素说法当我们遇到不确定性时就要保留各种可能性

　　回到我们刚才谈到拼音转汉字例子我们已知两种信息第根据语言模型wang-xiao-bo 可以被转换成王晓波和王小波；第 2根据主题王小波是作家黄金时代作者等等而王晓波是台湾研究两岸关系学者因此我们就可以建立个最大熵模型同时满足这两种信息现在问题是这样个模型是否存在匈牙利著名数学家、信息论最高奖香农奖得主希萨(Csiszar)证明对任何组不自相矛盾信息这个最大熵模型不仅存在而且是唯而且它们都有同个非常简单形式 -- 指数下面公式是根据上下文(前两个词)和主题预测下个词最大熵模型其中 w3 是要预测词(王晓波或者王小波)w1 和 w2 是它前两个字(比如说它们分别是“出版”和“”)也就是其上下文个大致估计subject 表示主题



　　我们看到在上面公式中有几个参数 lambda 和 Z 他们需要通过观测数据训练出来

　　最大熵模型在形式上是最漂亮统计模型而在实现上是最复杂模型的我们在将下个系列中介绍如何训练最大熵模型诸多参数以及最大熵模型在自然语言处理和金融方面很多有趣应用

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

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

　　最原始最大熵模型训练思路方法是种称为通用迭代算法 GIS(generalized iterative scaling) 迭代 算法GIS 原理并不复杂大致可以概括为以下几个步骤:

　　1. 假定第零次迭代模型为等概率均匀分布

　　2. 用第 N 次迭代模型来估算每种信息特征在训练数据中分布如果超过了实际就把相应模型参数变小；否则将它们便大

　　3. 重复步骤 2 直到收敛

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

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

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

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



　　最大熵模型可以说是集简和繁于体形式简单实现复杂值得提是在Google很多产品中比如机器翻译都直接或间接地用到了最大熵模型

　　讲到这里读者也许会问当年最早改进最大熵模型算法达拉皮垂兄弟这些年难道没有做任何事吗？他们在 9十年代初贾里尼克离开 IBM 后也退出了学术界而到在金融界大显身手他们两人和很多 IBM 语音识别同事同到了家当时还不大但现在是世界上最成功对冲基金(hedge fund)公司----文艺复兴技术公司 (Renaissance Technologies)我们知道决定股票涨落原因可能有几十甚至上百种而最大熵思路方法恰恰能找到个同时满足成千上万种区别条件模型达拉皮垂兄弟等科学家在那里用于最大熵模型和其他些先进数学工具对股票预测获得了巨大成功从该基金 1988 年创立至今它净回报率高达平均每年 34%也就是说如果 1988 年你在该基金投入块钱今天你能得到 200 块钱这个业绩远远超过股神巴菲特旗舰公司伯克夏哈撒韦(Berkshire Hathaway)同期伯克夏哈撒韦总回报是 16 倍

　　值得提是信息处理很多数学手段包括隐含马尔可夫模型、子波变换、贝叶斯网络等等在华尔街多有直接应用由此可见数学模型作用