存档

文章标签 ‘machine learning’

online random forest

2010年5月26日 44 条评论

一直忽悠cvchina,心有歉意。第一次发文,简单写点online learning的东西。

传统的SVM和adaboost都是batch mode learning. 所谓的batch mode learning, 简单说,就是所有的训练数据都是available的(或则说所有训练数据都已经在内存中)。这种方法主要有2个缺点:

1)  有时候数据量太大,在内存中放不下,处理起来不方便

2)  由于应用环境限制,有时候无法在训练之前得到所有训练数据

而Online learning, 他的数据是come in sequence,也就是说traning sample 是一个一个来,或则是几个几个来,然后classifer 根据新来的samples进行更新。Online learning是比较困难的,主要原因是你无法知道将来的训练数据是如何的。显然adaboost和svm是行不通的。最近几年也有一些人做online learning的研究,主要方法还是集中在online boosting这一块。推荐2篇不错的文章:

1)  online adaboost [1], 并把他用在object tracking等方面。这篇文章发表于CVPR2006引用率蛮高。这几年的cvpr上的几篇做tracking的文章以这个idea为基础。tracking的方法是用最近比较流行的tracking-by-detection的方法。简答的说就是在tracking的时候,observation model这一块是用一个在线训练的分类器。tracking的过程如下图所示(图中还有一步是用跟踪的结果作为训练器的新的输入):

这篇文章online 训练的时候,用tracking 的结果作为online classifier的positive samples。显然这种数据是有噪声的,最后tracking会drift掉。而且需要指出的是,这种方法没有严格证明,只是模仿batch mode adaboost. 我把这个算法用在uci的训练数据上,效果不是很好。作者的主页是:http://www.vision.ee.ethz.ch/~hegrabne/. 这个是他用online learning 做tracking的项目主页:http://www.vision.ee.ethz.ch/boostingTrackers/。 有现成代码和demo。

2)  去年的一篇论文是关于online random forest[2]。网上有现成的代码。我跑了一下,挺牛逼的,效果没比offline mode差不多。如果你需要做online learning的话十分推荐。

[1].On-line Boosting and Vision. 06CVPR.

[2]. . 09ICCV workshop on online .

PS:code的原始链接失效了,我传了一份到everbox。下载链接
如果不能下载,请通过该链接注册后下载。

 

 

ZZ:machine learning 大家

2010年5月12日 5 条评论

陈年老帖,翻出来共享一下,本人才疏学浅,不做评价。来源

闲着无事,想写点一些我所了解的machine learning大家。由于学识浅薄,见识有限,并且仅局限于某些领域,一些在NLP及最近很热的生物信息领域活跃的学者我就浅陋无知,所以不对的地方大 家仅当一笑。

大家(1):M. I. Jordan

在我的眼里,M Jordan无疑是武林中的泰山北斗。他师出MIT,现在在berkeley坐镇一方,在附近的两所名校(加stanford)中都可以说无出其右 者,stanford的Daphne Koller虽然也声名遐迩,但是和Jordan比还是有一段距离。

Jordan身兼 stat和cs两个系的教授,从他身上可以看出Stat和ML的融合。

Jordan 最先专注于mixtures of experts,并迅速奠定了自己的地位,我们哈尔滨工业大学的校友徐雷跟他做博后期间,也在这个方向上沾光不少。Jordan和他的弟子在很多方面作出 了开创性的成果,如spectral , Graphical model和nonparametric Bayesian。现在后两者在ML领域是非常炙手可热的两个方向,可以说很大程度上是Jordan的lab一手推动的。

更难能 可贵的是, Jordan不仅自己武艺高强,并且揽钱有法,教育有方,手下门徒众多且很多人成了大器,隐然成为江湖大帮派。他的弟子中有10多人任教授,个人认为他现 在的弟子中最出色的是stanford的Andrew Ng,不过由于资历原因,现在还是assistant professor,不过成为大教授指日可待;另外Tommi Jaakkola和David Blei也非常厉害,其中Tommi Jaakkola在mit任教而David Blei在cmu做博后,数次获得NIPS最佳论文奖,把SVM的最大间隔方法和Markov network的structure结构结合起来,赫赫有名。还有一个博后是来自于toronto的Yee Whye Teh,非常不错,有幸跟他打过几次交道,人非常nice。另外还有一个博后居然在做生物信息方面的东西,看来jordan在这方面也捞了钱。这方面他有 一个中国学生Eric P. Xing(清华大学校友),现在在cmu做assistant professor。

总的说来,我 觉得 Jordan现在做的主要还是graphical model和Bayesian learning,他去年写了一本关于graphical model的书,今年由mit press出版,应该是这个领域里程碑式的著作。3月份曾经有人答应给我一本打印本看看,因为Jordan不让他传播电子版,但后来好像没放在心上(可见 美国人也不是很守信的),人不熟我也不好意思问着要,可以说是一大遗憾. 另外发现一个有趣的现象就是Jordan对hierarchical情有独钟,相当多的文章都是关于hierarchical的,所以能 hierarchical大家赶快hierarchical,否则就让他给抢了。

用我朋友话说看jordan牛不牛,看他主页下 面的Past students and postdocs就知道了。

Machine Learning大家(2):D. Koller

D. Koller是1999年美国青年科学家总统奖(PECASE)得主,IJCAI 2001 Computers and Thought Award(IJCAI计算机与思维奖,这是国际人工智能界35岁以下青年学者的最高奖)得主,2004 World Technology Award得主。

最先知道D koller是因为她得了一个大奖,2001年IJCAI计算机与思维奖。Koller因她在概率推理的理论和实践、、计算博弈论等领域的重要贡 献,成为继Terry Winograd、David Marr、Tom Mitchell、Rodney Brooks等人之后的第18位获奖者。说起这个奖挺有意思的,IJCAI终身成就奖(IJCAI Award for Research Excellence),是国际人工智能界的最高荣誉; IJCAI计算机与思维奖是国际人工智能界35岁以下青年学者的最高荣誉。早期AI研究将推理置于至高无上的地位; 但是1991年牛人Rodney Brooks对推理全面否定,指出机器只能独立学习而得到了IJCAI计算机与思维奖; 但是koller却因提出了Probabilistic Relational Models 而证明机器可以推理论知而又得到了这个奖,可见世事无绝对,科学有轮回。

D koller的Probabilistic Relational Models在nips和icml等各种牛会上活跃了相当长的一段时间,并且至少在实验室里证明了它在信息搜索上的价值,这也导致了她的很多学生进入了 google。虽然进入google可能没有在牛校当faculty名声响亮,但要知道google的很多员工现在可都是百万富翁,在全美大肆买房买车的 主。

Koller的研究主要都集中在probabilistic graphical model,如Bayesian网络,但这玩意我没有接触过,我只看过几篇他们的markov network的文章,但看了也就看了,一点想法都没有,这滩水有点深,不是我这种非科班出身的能趟的,并且感觉难以应用到我现在这个领域中。

Koller 才从教10年,所以学生还没有涌现出太多的牛人,这也是她不能跟Jordan比拟的地方,并且由于在stanford的关系,很多学生直接去硅谷赚大钱去 了,而没有在学术界开江湖大帮派的影响,但在stanford这可能太难以办到,因为金钱的诱惑实在太大了。不过Koller的一个学生我非常崇拜,叫 Ben Taskar,就是我在(1)中所提到的Jordan的博后,是好几个牛会的最佳论文奖,他把SVM的最大间隔方法和Markov network结合起来,可以说是对structure data处理的一种标准工具,也把最大间隔方法带入了一个新的热潮,近几年很多牛会都有这样的workshop。 我最开始上Ben Taskar的在stanford的个人网页时,正赶上他刚毕业,他的顶上有这么一句话:流言变成了现实,我终于毕业了!可见Koller是很变态的,把 自己的学生关得这么郁闷,这恐怕也是大多数女faculty的通病吧,并且估计还非常的push!

Machine learning 大家(3):J. D. Lafferty

大家都知道NIPS和ICML向来都是由大大小小的山头所割据,而 John Lafferty无疑是里面相当高的一座高山,这一点可从他的publication list里的NIPS和ICML数目得到明证。虽然江湖传说计算机重镇CMU现在在走向衰落,但这无碍Lafferty拥有越来越大的影响力,翻开AI兵 器谱排名第一的journal of machine learning research的很多文章,我们都能发现author或者editor中赫然有Lafferty的名字。

Lafferty给人 留下的最大的印象似乎是他2001年的conditional random fields,这篇文章后来被疯狂引用,广泛地应用在语言和图像处理,并随之出现了很多的变体,如Kumar的discriminative random fields等。虽然大家都知道discriminative learning好,但很久没有找到好的discriminative方法去处理这些具有丰富的contextual inxxxxation的数据,直到Lafferty的出现。

而现在Lafferty做的东西好像很 杂,semi-supervised learning, kernel learning,graphical models甚至manifold learning都有涉及,可能就是像武侠里一样只要学会了九阳神功,那么其它的武功就可以一窥而知其精髓了。这里面我最喜欢的是semi- supervised learning,因为随着要处理的数据越来越多,进行全部label过于困难,而完全unsupervised的方法又让人不太放心,在这种情况下 semi-supervised learning就成了最好的。这没有一个比较清晰的认识,不过这也给了江湖后辈成名的可乘之机。到现在为止,我觉得cmu的semi- supervised是做得最好的,以前是KAMAL NIGAM做了开创性的工作,而现在Lafferty和他的弟子作出了很多总结和创新。

Lafferty 的弟子好像不是很多,并且好像都不是很有名。不过今年毕业了一个中国人,Xiaojin Zhu(上海交通大学校友),就是做semi-supervised的那个人,现在在wisconsin-madison做assistant professor。他做了迄今为止最全面的Semi-supervised learning literature survey,大家可以从他的个人主页中找到。这人看着很憨厚,估计是很好的陶瓷对象。另外我在(1)中所说的Jordan的牛弟子D Blei今年也投奔Lafferty做博后,就足见Lafferty的牛了。

Lafferty做NLP是很好的,著名的Link Grammar Parser还有很多别的应用。其中language model在IR中应用,这方面他的另一个中国学生ChengXiang Zhai(南京大学校友,2004年美国青年科学家总统奖(PECASE)得主),现在在uiuc做assistant professor。

Machine learning 大家(4):

鄙人浅薄之见,Jordan 比起同在berkeley的Peter Bartlett还是要差一个层次。Bartlett主要的成就都是在learning theory方面,也就是ML最本质的东西。他的几篇开创性理论分析的论文,当然还有他的书Neural Network Learning: Theoretical Foundations。

UC Berkeley的统计系在强手如林的北美高校中一直是top3,这就足以证明其肯定是群星荟萃,而其中,Peter L. Bartlett是相当亮的一颗星。关于他的研究,我想可以从他的一本书里得到答案:Neural Network Learning: Theoretical Foundations。也就是说,他主要做的是Theoretical Foundations。基础理论虽然没有一些直接可面向应用的算法那样引人注目,但对科学的发展实际上起着更大的作用。试想vapnik要不是在VC维 的理论上辛苦了这么多年,怎么可能有SVM的问世。不过阳春白雪固是高雅,但大多数人只能听懂下里巴人,所以Bartlett的文章大多只能在做理论的那 个圈子里产生影响,而不能为大多数人所广泛引用。

Bartlett在最近两年做了大量的Large margin classifiers方面的工作,如其convergence rate和generalization bound等。并且很多是与jordan合作,足见两人的工作有很多相通之处。不过我发现Bartlett的大多数文章都是自己为第一作者,估计是在教育 上存在问题吧,没带出特别牛的学生出来。

Bartlett的个人主页的talk里有很多值得一看的slides,如Large Margin Classifiers: Convexity and Classification;Large Margin Methods for Structured Classification: Exponentiated Gradient Algorithms。大家有兴趣的话可以去下来看看。

Machine learning 大家(5): Michael Collins

(http://people.csail.mit.edu/mcollins/
自然语言处理(NLP)江湖的第一高人。出身Upenn,靠 一身叫做Collins Parser的武功在江湖上展露头脚。当然除了资质好之外,其出身也帮了不少忙。早年一个叫做Mitchell P. Marcus的师傅传授了他一本葵花宝典-Penn Treebank。从此,Collins整日沉迷于此,终于练成盖世神功。

学成之后,Collins告别师傅开始闯荡江湖,投入了一个叫AT&T Labs Research的帮会,并有幸结识了Robert Schapire、Yoram Singer等众多高手。大家不要小瞧这个叫AT&T Labs Research的帮会,如果谁没有听过它的大名总该知道它的同父异母的兄弟Bell Labs吧。

言归正传,话说 Collins在这里度过了3年快乐的时光。其间也奠定了其NLP江湖老大的地位。并且练就了Discriminative Reranking, Convolution Kernels,Discriminative Training Methods for Hidden Markov Models等多种绝技。然而,世事难料,怎奈由于帮会经营不善,这帮大牛又不会为帮会拼杀,终于被一脚踢开,大家如鸟兽散了。Schapire去了 Princeton, Singer 也回老家以色列了。Collins来到了MIT,成为了武林第一大帮的六袋长老,并教授一门叫做的Machine Learning Approaches for NLP
(http://www.ai.mit.edu/courses/6.891-nlp/ 的功夫。虽然这一地位与其功力极不相符,但是这并没有打消Collins的积极性,通过其刻苦打拼,终于得到了一个叫Sloan Research Fellow的头衔,并于今年7月,光荣的升任7袋Associate Professor。

在其下山短短7年时间 内,Collins共获得了4次世界级武道大会冠军(EMNLP2002, 2004, UAI2004, 2005)。相信年轻的他,总有一天会一统丐帮,甚至整个江湖。

看过Collins和别人合作的一篇文章,用 conditional random fields 做object recogntion。还这么年轻,admire to death!

ZZ from 丕子: Mahout 0.3: 机器学习开源项目

2010年5月4日 没有评论
Apache Mahout

萎缩的项目logo。。。

有关机器学习的开源项目Apache Mahout三月份的时候推 出了它的0.3版本,这个新版本在之前的基础上添加了一些新功能,比之前的版本更为稳定,性能也有相应的提升。InfoQ采访了Apache Mahout项目的开发者Grant IngersollTed Dunning,其中Grant Ingresoll也是该项目的创始人之一。

过去十年里,从大 量原始数据中解析出相关信息的需求急剧增长,以致于聚类()、协同过滤()和分类()等机器学习技术的需 求也是呈稳定增长势态。

Grant Ingersoll这样介 绍 项目:

  • 将已知方法语境中的文档聚类 (Clustering)有助于把注意力集中到某些特定的聚类和内容上,从而避免在无关的内容上浪费精力。
  • 推荐算法(协同过滤推荐算法 -Collaborative Filtering)常常用来向用户推荐书籍、音乐、电影等内容,也可以用于多用户协作的应用中精简所需关注的数 据。
  • 模式匹配(朴素贝叶斯分类器 -Naïve Bayes Classifier等分类算法)可用于归类之前没有见过的文档。归类新文档时,算法在模式中查找文档中涉及的词汇, 计算该文档属于各个模式的概率,最后文档将归于概率最大的模式,输入的结果往往都以数值来表示算法本身对这个结果的正确与否有多大的把握。
  • Mahout 项目通过Apache Hadoop的支持来获 得伸缩性。

Mahout另一个重点是,它提供一系列工 具把文本数据表示成矩阵形式。这也是采用Mahout机器学习算法来处理数据的首要任务。

Mahout项目是由Apache Lucene(开 源搜索项目)社区几 个热衷于聚类、分类等机器学习算法的技术人员所发起。社区最初的开发“追随”于Ng et al.发表的论文“支 持多核之 上的机器学习Map- Reduce框架(Map-Reduce for on Multicore)”,自项目启动以来,社区也致力于各 种机器学习算法、模式的开发

最新Apache Mahout版本的亮点有:

在问到这个版本中最激动人心的特性 时,Ingersoll这样回答:

新添加的分布式奇异值分解(Singular Value Decomposition)计算非常令人期待,此外,还有那些方便用户把内容导入到Mahout的诸多工具。其中,最激动人心的其实并不是有形的,而是 Mahout社区的成长。社区目前已吸引到数量客观的贡献者和用户。任何开源项目的发展过程当中,最初阶段往往都很惨淡,工作常常只有一两个人去做,一旦 当中有人离开甚至只是减缓开发速度,整个项目都有可能中途夭折。但我相信Mahout已经通过了这样的考验,现在已经有非常多非常活跃的社区成员正努力把 它变成一个真正令人激动的项目。

Mahout项目的未来计划包括:

和SVM的实现将适宜于文档挖掘以及其它一些与文本或重复归类数据相关的应用。尤其令人期待的是SGD系统将引入在线创建互动变量的 能力。

查看英文原文:Mahout 0.3: Open Source Machine Learning

来源

强推:ML评测网站

2010年4月15日 1 条评论

Program_img2

这个必须要推荐一下了。

MLComp是一个公开Machine Learning算法评测网站。你可以在MLComp上做两件事情:

1. 上传你的算法,用公开的数据库来测试性能。

2.上传你的数据库,用公开的算法来测试性能。

就像一个免费的运算集群,没有运算资源的研究者有福了。

更爽的是,任何用户都随意使用别的用户的算法和数据集。

虽然我没用过,个人感觉此网站必火。学术也可以云计算,哈哈, in the cloud。

网站的创建者是UC Berkeley的两个博士,目前网站还在Alpha版本,希望可以健康发展。

MLcomp is under active development.  Currently, seven machine learn task types (classification, regression, , sequence tagging, etc.) are supported, with hundreds of standard programs and datasets already online.

另外,这个网站让我想起了另外一个AlphaMatting的网站,可以上传程序在公开的测试集上测试比较性能。

最后畅想一下,也许有一天,民间科学家可以购买一坨虚拟主机来做并行科学运算啦。