机器学习研究进展 周志华 http://cs.nju.edu.cn/people/zhouzh/ Email: zhouzh@nju.edu.cn 南京大学计算机软件新技术国家重点实验室

提纲 国际动向 我们的一些工作

机器学习 机器学习是人工智能的核心研究领域之一 经典定义：利用经验改善系统自身的性能 随着该领域的发展，主要做智能数据分析 典型任务：根据现有数据建立预测模型

机器学习的重要性 生物 信息学 计算 金融学 分子 生物学 行星 地质学 …… 工业过程控制 机器人 遥感信 息处理 信息安全 机 器 学 习 美国航空航天局JPL实验室的科学家在《Science》（2001年9月）上撰文指出：机器学习对科学研究的整个过程正起到越来越大的支持作用，……，该领域在今后的若干年内将取得稳定而快速的发展

机器学习的重要性 美国航空航天局JPL实验室的科学家在《Science》（2001年9月）上撰文指出：机器学习对科学研究的整个过程正起到越来越大的支持作用，……，该领域在今后的若干年内将取得稳定而快速的发展

例1:网络安全 如何检测？ 入侵检测： 历史数据：以往的正常访问模式及其表现、以往的入侵模式及其表现…… 对当前访问模式分类 是否是入侵？是何种入侵？ 这是一个典型的机器学习问题 常用技术： 神经网络 决策树 支持向量机 贝叶斯分类器 k近邻 序列分析 聚类 …… ……

例2:生物信息学 常用技术： 神经网络 支持向量机 隐马尔可夫模型 贝叶斯分类器 k近邻 决策树 序列分析 聚类 …… ……

例3:搜索引擎 机器学习技术正在支撑着各类搜索引擎 Google的成功，使得Internet 搜索引擎成为一个新兴的产业 不仅有众多专营搜索引擎的公司出现（例如专门针对中文搜索的就有百度、慧聪等），而且Microsoft等巨头也开始投入巨资进行研发 Google掘到的第一桶金，来源于其创始人Larry Page和Sergey Brin提出的PageRank算法 机器学习技术正在支撑着各类搜索引擎

美国的PAL计划 DARPA 2003年开始启动PAL（Perceptive Assistant that Learns）计划 5年期，首期（1-1.5年）投资2千9百万美元 以机器学习为核心的计划（涉及到AI的其他分支，如知识表示和推理、自然语言处理等）；包含2个子计划 总目标： “is expected to yield new technology of significant value to the military, business, and academic sectors” “develop software that will help decision-makers manage their complex worlds of multiple simultaneous tasks and unexpected events”

美国的PAL计划: RADAR子计划 RADAR (Reflective Agents with Distributed Adaptive Reasoning)，承担单位为CMU， 首期7百万美元 目标：“the system will help busy managers to cope with time-consuming tasks” “RADAR must learn by interacting with its human master and by accepting explicit advice and instruction”

美国的PAL计划: CALO子计划(1) CALO (Cognitive Agent that Learns and Observes)， 承担单位为SRI，首期2千2百万美元 除SRI外，这个子计划的参加单位有20家： Boeing, CMU, Dejima Inc., Fetch Tech Inc., GATech, MIT, Oregon HSU, Stanford, SUNY-Stony Brook, UC Berkeley, UMass, UMich, UPenn, Rochester, USC, UT Austin, UW, Yale, … CALO无疑是PAL中更核心的部分

美国的PAL计划: CALO子计划(2) 从CALO的目标来看，DARPA已经开始把机器学习技术的重要性放到了国家安全的角度来考虑 目标： “the name CALO was inspired by the Latin word ‘calonis’, which means ‘soldier’s assistant’” “the CALO software, which will learn by working with and being advised by its users, will handle a broad range of interrelated decision-making tasks … It will have the capability to engage in and carry out routine tasks, and to assist when the unexpected happens” 从CALO的目标来看，DARPA已经开始把机器学习技术的重要性放到了国家安全的角度来考虑

美国的PAL计划: CALO子计划(3)

我们最近关于集成学习的一些工作 为什么要研究集成学习?

泛化能力(generalization ability)表征了学习系统对新事件的适用性 泛化能力是机器学习关注的一个根本问题 泛化能力(generalization ability)表征了学习系统对新事件的适用性 泛化能力越强越好 提高泛化能力是机器学习永远的追求

集成学习 集成学习(Ensemble Learning)是一种机器学习范式，它使用多个学习器来解决同一个问题 … ... 由于集成学习可以有效地提高学习系统的泛化能力，因此它成为国际机器学习界的研究热点 “当前机器学习四大研究方向之首” [T.G. Dietterich, AIMag97]

我们的一些工作 选择性集成 集成可理解性 多示例集成 应用

1. 选择性集成 既然多个学习器的集成比单个学习器更好，那么是不是学习器越多越好? 个体的增加将使得个体间的差异越来越难以获得 更多的个体意味着： 在预测时需要更大的计算开销，因为要计算更多的个体预测 更大的存储开销，因为有更多的个体需要保存 个体的增加将使得个体间的差异越来越难以获得 [A. Krogh & J. Vedelsby, NIPS94]

1. 选择性集成 (con’t) 提出了选择性集成(Selective Ensemble) 证明了 “Many Could be Better Than All” Theorem 在有一组个体学习器可用时，从中选择一部分进行集成，可能比用所有个体学习器进行集成更好 in classification in regression Z.-H. Zhou, J. Wu, and W. Tang. Ensembling neural networks: many could be better than all. Artificial Intelligence, 2002, 137(1-2): 239-263. 据ISI统计, 该文被引次数在2002年1月以来该刊发表的所有论文(共278篇)中排第4 Z.-H. Zhou, J.-X. Wu, Y. Jiang, and S.-F. Chen. Genetic algorithm based selective neural network ensemble. In: Proc. IJCAI'01, Seattle, WA, pp.797-802.

1. 选择性集成 (con’t) 提出了GASEN算法 显示出选择性集成理论的可操作性 使用少得多的个体学习器，取得了比Bagging和Boosting更高的精度 分类: 36% 回归: 19% Z.-H. Zhou, J. Wu, and W. Tang. Ensembling neural networks: many could be better than all. Artificial Intelligence, 2002, 137(1-2): 239-263. 据ISI统计, 该文被引次数在2002年1月以来该刊发表的所有论文(共278篇)中排第4 Z.-H. Zhou, J.-X. Wu, Y. Jiang, and S.-F. Chen. Genetic algorithm based selective neural network ensemble. In: Proc. IJCAI'01, Seattle, WA, pp.797-802.

1. 选择性集成 (con’t) 选择性集成思想的一般性：利用多个个体，并对个体进行选择，可以获得更好的结果 问题 … ... 个体解 选择性集成的思想可以用到更多的领域中去 选择的基本原则：个体的效用高、差异大

1. 选择性集成 (con’t) 国际上的一些研究： 基于选择性集成的时序预报 [S. Chiewchanwattana et al., ICONIP’02] GASEN的Grid实现 [T.K. Vin et al., IEEE ICDFMA’05] 新的选择性集成方法 [N. Garcia-Pedrajas, TEC’05] … …

1. 选择性集成 (con’t) top 1% cited paper since 2000 -ISI “非常重要，非常新颖” (“very significant, very original”) – IJCAI’01 Review “优秀论文” (“excellent paper”) – 《AIJ》 editor “最佳论文之一” (“one of the best papers” ) – 《IJCIA》 editor “了不起的是，该方法比以往著名的集成方法性能更好，而且只用了较小的计算代价” (“It is remarkable that this strategy performs better than well-established ensembling approaches,…, at a much lower computational cost”) – C. Torras “开辟了广阔的领域” (“opens a wide field” ) – N. Garcia-Pedrajas 《IEEE Trans. EC》

2. 集成可理解性 理想的学习系统 强泛化能力 好可理解性 (comprehensibility) 在很多应用中，学习系统只是一种辅助手段，最终的决策还是需要由用户来做 “增强集成可理解性是一个有待研究的问题” [T.G. Dietterich, AIMag97]

2. 集成可理解性 (con’t) 提出了REFNE方法 从功能分析的角度出发 可以从集成中抽取符号规则， 使得集成的功能可以由符号规 则来描述 Z.-H. Zhou, Y. Jiang, and S.-F. Chen. Extracting symbolic rules from trained neural network ensembles. AI Communications, 2003, 16(1): 3-15. 据ISI统计, 该文被引次数在2003年1月以来该刊发表的所有论文(共67篇)中排第1

2. 集成可理解性 (con’t) 提出了二次学习 (twice-learning) 提出了C4.5Rule-PANE算法 获得： 强泛化能力 + 好可理解性 Z.-H. Zhou and Y. Jiang. Medical diagnosis with C4.5 rule preceded by artificial neural network ensemble. IEEE Transactions on Information Technology in Biomedicine, 2003, 7(1): 37-42. 据ISI统计, 该文被引次数在2003年1月以来该刊发表的所有论文(共160篇)中排第5

2. 集成可理解性 (con’t) 提出了NeC4.5算法 从理论上分析了二次学习奏效的原因，推导出条件 数据中包含噪音 数据没有完全表达目标分布 直接用L1学得结果的泛化能力显著优于用L2学得的结果 Z.-H. Zhou and Y. Jiang. NeC4.5: neural ensemble based C4.5. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(6): 770-773.

2. 集成可理解性 (con’t) “总之，C4.5Rule-PANE应被视为追求完美规则抽取技术这一圣杯的人的武器” (“In summary, C4.5 Rule-PANE should be viewed as yet another weapon in the armoury of those seeking the holy grail of a perfect rule extraction technique” ) - M. Pennington’s thesis supervised by A.J.C. Sharkey Free C4.5Rule-PANE package: http://cs.nju.edu.cn/people/zhouzh/zhouzh.files/publication/annex/C45Rule-PANE.htm Free NeC4.5 package: http://cs.nju.edu.cn/people/zhouzh/zhouzh.files/publication/annex/NeC45.htm

3. 多示例集成 集成学习的以往研究集中在监督学习框架下 三种机器学习框架: 监督学习(supervised learning) 所有训练样本都有标记(label) 非监督学习(unsupervised learning) 所有训练样本都没有标记 强化学习(reinforcement learning) 延迟标记(延迟奖赏) 集成学习的以往研究集中在监督学习框架下

3. 多示例集成 一种新的学习框架：多示例学习 (multi-instance learning) Supervised learning [T.G. Dietterich et al., AIJ97] Supervised learning Unsupervised learning all training examples are with concept labels all training examples are without concept labels Reinforcement learning training examples are with delayed concept labels Multi-instance learning training instances are without concept labels training bags are with concept labels no delay

3. 多示例集成 (con’t) 以往学习框架： 多示例学习框架： “能否为常用的机器学习算法设计其多示例版本？” [T. G. Dietterich et al., AIJ97]

3. 多示例集成 (con’t) 提出了监督学习算法向多示例学习转化的一般准则 提出了多示例集成 用集成学习技术来解决多示例学习问题 “Shift the focuses of supervised learning algorithms from the discrimination on the instances to the discrimination on the bags” 提出了多示例集成 用集成学习技术来解决多示例学习问题 在基准测试上获得了迄今为止最高的精度记录 Z.-H. Zhou and M.-L. Zhang. Ensembles of multi-instance learners. In: Proc. ECML'03, Cavtat-Dubrovnik, Croatia, pp.492-502.

3. 多示例集成 (con’t) “关于一个重要话题的写得非常好的文章” (“Very well written paper on an important topic”) “其新思想和观点有助于机器学习界更好地理解多示例学习涉及的问题” (“New ideas and points of view that help the community to better understand the issues involved in multi-instance learning”) “该工作是创新的并且很可能被其他研究者进行跟随研究” (“The work is original and likely to give rise to follow-up papers”) - ECML’03 Reviewer

3. 多示例集成 (con’t) 我们使用多示例学习器来构建多示例集成，论文 发表半年后，机器学习工具库WEKA的创始人、著名学者 E. Frank 的研究组在我们工作的基础上做了进一步的工作 [X. Xu & E. Frank, PAKDD’04] ，使用单示例学习器来构建多示例集成，也获得了很好的结果

4. 应用 关键： 总误识率 假阴性率 ?

4. 应用 假阴性率降低意味着漏诊的病人减少，对肺癌早期诊断很重要 单一学习器： 误识率45.5% 假阴性率 17.4%, 二级集成方法： 误识率11.6% 假阴性率 2.7% (552幅真实图像) 假阴性率降低意味着漏诊的病人减少，对肺癌早期诊断很重要 Z.-H. Zhou, Y. Jiang, Y.-B. Yang, and S.-F. Chen. Lung cancer cell identification based on artificial neural network ensembles. Artificial Intelligence in Medicine, 2002, 24(1): 25-36. 据ISI统计, 该文被引次数在2002年1月以来该刊发表的所有论文(共201篇)中排第1

4. 应用 “这篇文章的质量给我留下了非常深刻的印象。我发现它非常有趣、信息丰富，我真的很享受阅读这篇文章” (“The quality of the article impressed me very much. I found the article very interesting and informative and, indeed, enjoyed reading it.” ) - M.R. Graczynski, editor of 《Medical Science Monitor》 “您的杰出工作及研究兴趣与Artificial Intelligence in Medicine非常相关，您的支持将极大地促进该刊的发展” (“Your outstanding work and research interests are very close to the various areas of artificial intelligence in medicine. I am sure your support will greatly enhance the AIM journal.” ) - P. Adlassnig, editor of 《AIM》

小结 近5年来: 国际刊物/会议论文60+篇，其中重要国际刊物（IEEE Trans或相当）15+篇 授权专利4项，另有2项正在受理 包括权威国际刊物AIJ、TKDE、权威国际会议IJCAI等 授权专利4项，另有2项正在受理 据不完全统计，被国际同行他引170余次（其中SCI他引 近90次），一些工作得到国际同行好评，产生了一定影响 应邀担任：6家国际刊物的副编辑/编委/客座编辑 20余国际会议顾问委员/程序委员 荷兰国家科学基金等一些境外基金机构特邀评审 20余国际刊物（包括AIJ和9种IEEE Trans）的审稿专家

下一步的工作 非经典条件下对泛化能力的追求 标记缺乏 代价敏感 不平衡 高维 ……

请各位专家 批评指正!