- 浏览: 2591114 次
- 来自: 杭州
文章分类
- 全部博客 (1190)
- webwork (4)
- 网摘 (18)
- java (104)
- hibernate (1)
- Linux (85)
- 职业发展 (1)
- activeMQ (2)
- netty (15)
- svn (1)
- webx3 (12)
- mysql (81)
- css (1)
- HTML (6)
- apache (3)
- 测试 (2)
- javascript (1)
- 储存 (1)
- jvm (5)
- code (13)
- 多线程 (12)
- Spring (18)
- webxs (2)
- python (119)
- duitang (0)
- mongo (3)
- nosql (4)
- tomcat (4)
- memcached (20)
- 算法 (28)
- django (28)
- shell (1)
- 工作总结 (5)
- solr (42)
- beansdb (6)
- nginx (3)
- 性能 (30)
- 数据推荐 (1)
- maven (8)
- tonado (1)
- uwsgi (5)
- hessian (4)
- ibatis (3)
- Security (2)
- HTPP (1)
- gevent (6)
- 读书笔记 (1)
- Maxent (2)
- mogo (0)
- thread (3)
- 架构 (5)
- NIO (5)
- 正则 (1)
- lucene (5)
- feed (4)
- redis (17)
- TCP (6)
- test (0)
- python,code (1)
- PIL (3)
- guava (2)
- jython (4)
- httpclient (2)
- cache (3)
- signal (1)
- dubbo (8)
- HTTP (4)
- json (3)
- java socket (1)
- io (2)
- socket (22)
- hash (2)
- Cassandra (1)
- 分布式文件系统 (5)
- Dynamo (2)
- gc (8)
- scp (1)
- rsync (1)
- mecached (0)
- mongoDB (29)
- Thrift (1)
- scribe (2)
- 服务化 (3)
- 问题 (83)
- mat (1)
- classloader (2)
- javaBean (1)
- 文档集合 (27)
- 消息队列 (3)
- nginx,文档集合 (1)
- dboss (12)
- libevent (1)
- 读书 (0)
- 数学 (3)
- 流程 (0)
- HBase (34)
- 自动化测试 (1)
- ubuntu (2)
- 并发 (1)
- sping (1)
- 图形 (1)
- freemarker (1)
- jdbc (3)
- dbcp (0)
- sharding (1)
- 性能测试 (1)
- 设计模式 (2)
- unicode (1)
- OceanBase (3)
- jmagick (1)
- gunicorn (1)
- url (1)
- form (1)
- 安全 (2)
- nlp (8)
- libmemcached (1)
- 规则引擎 (1)
- awk (2)
- 服务器 (1)
- snmpd (1)
- btrace (1)
- 代码 (1)
- cygwin (1)
- mahout (3)
- 电子书 (1)
- 机器学习 (5)
- 数据挖掘 (1)
- nltk (6)
- pool (1)
- log4j (2)
- 总结 (11)
- c++ (1)
- java源代码 (1)
- ocr (1)
- 基础算法 (3)
- SA (1)
- 笔记 (1)
- ml (4)
- zokeeper (0)
- jms (1)
- zookeeper (5)
- zkclient (1)
- hadoop (13)
- mq (2)
- git (9)
- 问题,io (1)
- storm (11)
- zk (1)
- 性能优化 (2)
- example (1)
- tmux (1)
- 环境 (2)
- kyro (1)
- 日志系统 (3)
- hdfs (2)
- python_socket (2)
- date (2)
- elasticsearch (1)
- jetty (1)
- 树 (1)
- 汽车 (1)
- mdrill (1)
- 车 (1)
- 日志 (1)
- web (1)
- 编译原理 (1)
- 信息检索 (1)
- 性能,linux (1)
- spam (1)
- 序列化 (1)
- fabric (2)
- guice (1)
- disruptor (1)
- executor (1)
- logback (2)
- 开源 (1)
- 设计 (1)
- 监控 (3)
- english (1)
- 问题记录 (1)
- Bitmap (1)
- 云计算 (1)
- 问题排查 (1)
- highchat (1)
- mac (3)
- docker (1)
- jdk (1)
- 表达式 (1)
- 网络 (1)
- 时间管理 (1)
- 时间序列 (1)
- OLAP (1)
- Big Table (0)
- sql (1)
- kafka (1)
- md5 (1)
- springboot (1)
- spring security (1)
- Spring Boot (3)
- mybatis (1)
- java8 (1)
- 分布式事务 (1)
- 限流 (1)
- Shadowsocks (0)
- 2018 (1)
- 服务治理 (1)
- 设计原则 (1)
- log (0)
- perftools (1)
最新评论
-
Aqu415:
,默认是netty还是hassion?
dubbo入门 -
siphlina:
课程——基于Python数据分析与机器学习案例实战教程分享网盘 ...
Python机器学习库 -
san_yun:
leibnitz 写道hi,我想知道,无论在92还是94版本, ...
hbase的行锁与多版本并发控制(MVCC) -
leibnitz:
hi,我想知道,无论在92还是94版本,更新时(如Puts)都 ...
hbase的行锁与多版本并发控制(MVCC) -
107x:
不错,谢谢!
Latent Semantic Analysis(LSA/ LSI)算法简介
2006年10月8日 上午 07:27:00
发表者:Google 研究员,吴军
[我们在投资时常常讲不要把所有的鸡蛋放在一个篮子里,这样可以降低风险。在信息处理中,这个原理同样适用。在数学上,这个原理称为最大熵原理 (the maximum entropy principle)。这是一个非常有意思的题目,但是把它讲清楚要用两个系列的篇幅。]
前段时间,Google 中国研究院的刘骏总监谈到在网络搜索排名中,用到的信息有上百种。更普遍地讲,在自然语言处理中,我们常常知道各种各样的但是又不完全确定的信息,我们需要用一个统一的模型将这些信息综合起来。如何综合得好,是一门很大的学问。
让 我们看一个拼音转汉字的简单的例子。假如输入的拼音是"wang-xiao-bo",利用语言模型,根据有限的上下文(比如前两个词),我们能给出两个最 常见的名字"王小波"和"王晓波"。至于要唯一确定是哪个名字就难了,即使利用较长的上下文也做不到。当然,我们知道如果通篇文章是介绍文学的,作家王小 波的可能性就较大;而在讨论两岸关系时,台湾学者王晓波的可能性会较大。在上面的例子中,我们只需要综合两类不同的信息,即主题信息和上下文信息。虽然有 不少凑合的办法,比如:分成成千上万种的不同的主题单独处理,或者对每种信息的作用加权平均等等,但都不能准确而圆满地解决问题,这样好比以前我们谈到的 行星运动模型中的小圆套大圆 打补丁的方法。在很多应用中,我们需要综合几十甚至上百种不同的信息,这种小圆套大圆的方法显然行不通。
数学上最漂亮的办法是最大熵(maximum entropy)模型,它相当于行星运动的椭圆模型。"最大熵"这个名词听起来很深奥,但是它的原理很简单,我们每天都在用。说白了,就是要保留全部的不确定性,将风险降到最小。让我们来看一个实际例子。
有 一次,我去 AT&T 实验室作关于最大熵模型的报告,我带去了一个色子。我问听众"每个面朝上的概率分别是多少",所有人都说是等概率,即各点的概率均为1/6。这种猜测当然 是对的。我问听众们为什么,得到的回答是一致的:对这个"一无所知"的色子,假定它每一个朝上概率均等是最安全的做法。(你不应该主观假设它象韦小宝的色 子一样灌了铅。)从投资的角度看,就是风险最小的做法。从信息论的角度讲,就是保留了最大的不确定性,也就是说让熵达到最大。接着,我又告诉听众,我的这 个色子被我特殊处理过,已知四点朝上的概率是三分之一,在这种情况下,每个面朝上的概率是多少?这次,大部分人认为除去四点的概率是 1/3,其余的均是 2/15,也就是说已知的条件(四点概率为 1/3)必须满足,而对其余各点的概率因为仍然无从知道,因此只好认为它们均等。注意,在猜测这两种不同情况下的概率分布时,大家都没有添加任何主观的假 设,诸如四点的反面一定是三点等等。(事实上,有的色子四点反面不是三点而是一点。)这种基于直觉的猜测之所以准确,是因为它恰好符合了最大熵原理。
最 大熵原理指出,当我们需要对一个随机事件的概率分布进行预测时,我们的预测应当满足全部已知的条件,而对未知的情况不要做任何主观假设。(不做主观假设这 点很重要。)在这种情况下,概率分布最均匀,预测的风险最小。因为这时概率分布的信息熵最大,所以人们称这种模型叫"最大熵模型"。我们常说,不要把所有 的鸡蛋放在一个篮子里,其实就是最大熵原理的一个朴素的说法,因为当我们遇到不确定性时,就要保留各种可能性。
回 到我们刚才谈到的拼音转 汉字的例子,我们已知两种信息,第一,根据语言模型,wang-xiao-bo 可以被转换成王晓波和王小波;第二,根据主题,王小波是作家,《黄金时代》的作者等等,而王晓波是台湾研究两岸关系的学者。因此,我们就可以建立一个最大 熵模型,同时满足这两种信息。现在的问题是,这样一个模型是否存在。匈牙利著名数学家、信息论最高奖香农奖得主希萨(Csiszar)证明,对任何一组不 自相矛盾的信息,这个最大熵模型不仅存在,而且是唯一的。而且它们都有同一个非常简单的形式 -- 指数函数。下面公式是根据上下文(前两个词)和主题预测下一个词的最大熵模型,其中 w3 是要预测的词(王晓波或者王小波)w1 和 w2 是它的前两个字(比如说它们分别是"出版",和""),也就是其上下文的一个大致估计,subject 表示主题。
我们看到,在上面的公式中,有几个参数 lambda 和 Z ,他们需要通过观测数据训练出来。
最大熵模型在形式上是最漂亮的统计模型,而在实现上是最复杂的模型之一。我们在将下一个系列中介绍如何训练最大熵模型的诸多参数,以及最大熵模型在自然语言处理和金融方面很多有趣的应用。
我们上次谈到 用最大熵模型可以将各种信息综合在一起。我们留下一个问题没有回答,就是如何构造最大熵模型。我们已经所有的最大熵模型都是指数函数的形式,现在只需要确定指数函数的参数就可以了,这个过程称为模型的训练。
最原始的最大熵模型的训练方法是一种称为通用迭代算法 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 工作站,仍然计算了三个月。由此可见最大熵模型的复杂的一面。最大熵模型快速算法的实现很复杂,到今天为止,世界上能有效实现这些算法的人也不到一百人。 有兴趣实现一个最大熵模型的读者可以阅读我的论文 。
最大熵模型,可以说是集简与繁于一体,形式简单,实现复杂。值得一提的是,在Google的很多产品中,比如机器翻译,都直接或间接地用到了最大熵模型。
讲 到这里,读者也许会问,当年最早改进最大熵模型算法的达拉皮垂兄弟这些年难道没有做任何事吗?他们在九十年代初贾里尼克离开 IBM 后,也退出了学术界,而到在金融界大显身手。他们两人和很多 IBM 语音识别的同事一同到了一家当时还不大,但现在是世界上最成功对冲基金(hedge fund)公司----文艺复兴技术公司 (Renaissance Technologies)。我们知道,决定股票涨落的因素可能有几十甚至上百种,而最大熵方法恰恰能找到一个同时满足成千上万种不同条件的模型。达拉皮 垂兄弟等科学家在那里,用于最大熵模型和其他一些先进的数学工具对股票预测,获得了巨大的成功。从该基金 1988 年创立至今,它的净回报率高达平均每年 34%。也就是说,如果 1988 年你在该基金投入一块钱,今天你能得到 200 块钱。这个业绩,远远超过股神巴菲特的旗舰公司伯克夏哈撒韦(Berkshire Hathaway)。同期,伯克夏哈撒韦的总回报是 16 倍。
值得一提的是,信息处理的很多数学手段,包括隐含马尔可夫模型、子波变换、贝叶斯网络等等,在华尔街多有直接的应用。由此可见,数学模型的作用。
发表评论
-
ConcurrentHashMap 的实现原理
2016-06-12 15:37 571概述 我们在之前的博文中了解到关于 HashMap 和 ... -
BloomFilter——大规模数据处理利器
2016-04-25 15:09 565参考:http://www.cnblogs.com/hea ... -
Base64笔记
2014-05-08 16:32 642原文:http://www.ruanyif ... -
运算符的优先级
2014-02-21 22:06 938很久没有去深究运算符的优先级了,今天写SQL解析思考了一下。 ... -
beansdb使用的压缩算法-Quicklz压缩算法
2014-02-09 20:17 0据这里http://blog.yufeng.i ... -
跳表SkipList的原理和实现
2014-02-07 17:29 984参考:跳表SkipList的原理和实现 -
一种高效无锁内存队列的实现
2014-02-06 10:59 1966原文:http://www.searchtb. ... -
拆分文件统计topN的问题
2014-01-20 18:48 986如果对一个只包含ip地址文件进行统计,需要求出频率最高的前 ... -
Integer的numberOfLeadingZeros方法解释
2014-01-13 20:42 1062int numberOfLeadingZeros(int i ... -
rank排名算法整理
2014-01-07 13:44 10951.Delicious.com 热门书签排行榜 按照&q ... -
利用switch判断各种case
2013-12-27 16:35 0String env = "daily" ... -
如何创建一个短链服务
2013-12-26 16:23 0参考: http://stackoverflow.com ... -
HAProxy的独门武器:ebtree
2013-12-07 18:57 966原文:http://tech.uc.cn/?p= ... -
统计单词出现频率
2013-10-07 20:58 885这里有一个大文本,文件请从 http://10.125.9 ... -
Reddit评论排名算法
2013-03-16 00:48 1525上一篇文章介绍了Reddit的排名算法,今天继续上一篇文章 ... -
大数据量,海量数据 处理方法总结
2013-01-13 23:46 1096大数据量的问题是很多面试笔试中经常出现的问题,比如bai ... -
STL系列
2013-01-13 23:42 896STL系列之一 deque双向队列 STL系 ... -
java Map排序(按key和按value)
2012-12-10 15:54 93111、按照key排序 对于java中Map的排序,有排序Map ... -
算法文档集合
2012-11-24 15:59 854Treelink算法介绍 一些基础算法介绍 ... -
各种进制基础知识
2012-11-06 14:37 96010进制是人类最熟悉的数字计算 2进制是机器最基本的单位 ...
相关推荐
由于最大信息熵模型利用二值特征函数来表达和处理符号特征,而KDD99数据集中存在多种连续型特征,因此采用基于信息熵的离散化方法对数据集进行预处理,并利用CFS算法选择合适的特征子集,形成训练数据集合。...
基于模糊粗糙集的信息熵模型提出最大互信息最大相关熵标准,并根据该标准设计了一种新的特征选择方法,能同时处理离散数据、连续数据和模糊数据等混合信息。经UCI数据集试验,表明该算法与其他算法相比,具有较高的...
为研究煤岩截割破碎载荷谱特征及性能的评价方法,通过对实验瞬态载荷谱及其细观特征量的提取,提出载荷谱能量积聚段梯度、幅值增量和能量的3种特征量的...提出的载荷谱熵模型与算法可作为截割性能评价的一种有效方法。
由于最大信息熵模型利用二值特征函数来表达和处理符号特征,而KDD99数据集中存在多种连续型特征,因此采用基于信息熵的离散化方法对数据集进行预处理,并利用CFS算法选择合适的特征子集,形成训练数据集合。最后利用BLVM...
针对正弦Gordon模型研究了Brane World熵信息,因此Brane World熵信息量度被证明是一种准确的方法,尤其是从物理信息量的角度出发,它为AdS曲率的最大范围提供了最合适的范围。 解决方案。 此外,对于正弦-戈登模型...
采用信息熵方法对各安全资源指标进行定量化计算分析,构建了基于最大信息熵的安全资源配置模型,研究了安全资源的合理优化配置问题。实例应用结果表明,运输子系统及排水子系统属于重点增加安全资源投入的子系统,开采子...
针对Markowitz的均值-方差模型的缺陷,用信息熵代替方差度量风险,用反映资金的增值速度的增值熵代替均值,提出了一种新型投资组合模型――最小信息熵-最大增值熵模型,并通过多目标决策方法中的模糊集理论对模型...
最大熵模型(Maximum Entropy Model,以下简称MaxEnt),MaxEnt 是概率模型学习中一个准则,其思想为:在学习概率模型时,所有可能的模型中熵最大的模型是最好的模型;若概率模型需要满足一些约束,则最大熵原理就是...
引入拉格朗日乘子,对由路段观测流量反推交通出行矩阵的极大熵模型进行变换,将优化问题转换为非线性方程组的求解。并提出一种遗传算法求解方法。该方法以非线性方程组的待求量为决策变量,方程组两端向量的均方差...
化学需氧量)总量分配为例,充分考虑各区域自然和经济等因素的客观差异,选取与水污染物COD排放紧密相关的各项指标并将其量化,利用熵值法确定各指标权重,建立单位指标负荷污染物量的信息熵加权和最大的目标规划模型,...
基于负熵最大的独立分量分析,本科毕设要求参见标准测试模型,进行逐步线性回归,实现典型相关分析,重要参数的提取,一些自适应信号处理的算法。
最后建立煤粉尘颗粒的信息熵模型,存储信息熵并实现对分割阈值的提取。结果表明:依据模糊属性约简的互异重要度可实现多属性约简;并确定煤粉尘图像模块区域的最大信息熵分割阈值。所建立模型可删除冗余属性,选择出对...
基于模糊粗糙集的信息熵模型提出最大互信息最大相关熵标准,并根据该标准设计了一种新的特征选择方法,能同时处理离散数据、连续数据和模糊数据等混合信息。经UCI数据集试验,表明该算法与其他算法相比,具有较高的...
利用灰色关联熵理论分析影响因素与突出危险性的关联度,得到各影响因素的权重及关联度排序,并结合概率神经网络(PNN)原理,构建基于灰色关联熵的煤与瓦斯突出PNN预测模型。用煤与瓦斯突出样本数据,对影响因素加权...
步骤2 读入优化参数,如最大优化迭代步 数、优化终止条件. 初始化设计变量,如弹性模量、 泊松比、约束和载荷. 步骤3 用Matlab 程序编写的有限元求解 器求解位移场和应力场,或通过ANSYS 的有限 元求解器求解位移场和...
依据最优化理论中的KKT互补条件建立了广义支持向量机的无约束优化模型,并给出了一种有效的光滑化近似解法极大熵方法,为求解支持向量机优化问题提供了一种新途径....
在这张照片中,拓扑有序系统的纠缠谱对系统的准粒子涨落进行编码,并且纠缠熵测量EB上的最大准粒子涨落。 结果,纠缠熵对应于在纠缠边界上的无限温度下的准粒子的热熵。 我们通过有/无边界的量子双模型中的显式计算...
机器学习,统计学习,统计学习方法,如涉及侵权内容,资源将被移除