第九届机器学习 及其应用研讨会 2011年11月，清华大学 机器学习的困惑 与历史的启示 王珏

统计机器学习的麻烦 自 然 模 型 [采样] 统计机器学习 样本集 [算法] [交叉验证] 模型 [设计实验] 假设iid ？？？？？ 特殊函数的逼近 [设计实验] 如果数据不充分，在大变量集合下，如何设计实验，获得新数据。 问题：模型是自然模型吗？ 统计机器学习的困难：实验设计存在组合问题。iid成为与自然模型无关的假设！

社会的需求 生物、网络、金融、经济和安全等众多领域，大变量集合的海量数据不断涌出，社会迫切需要分析与处理这些数据的有效理论、方法与技术。 寻找分析与处理大变量集合海量数据的新理念、理论、方法与技术成为当前迫切的任务。

历史的故事

线性感知机 1902年，James的神经元相互连接 1943年，McCulloch和Pitts的神经元工作方式 1949年，Hebb的学习律。 基于最小二乘的Rosenblatt的感知机(1956)，其本质是多变量空间上的平均(回归)。 基函数： L = 1D + 2I + 3G + 4S 设计算法，确定，获得模型 贡献是：多变量回归的计算方法(神经网络)。 疑问是：只能解决线性问题，不能满足实际的需要。埋下被批评的口实。

20世纪70年代面临的选择 选择 统计优化(平均)： 线性感知机 统计模式识别 复杂信息系统(结构)： 专家系统 句法模式识别 非线性问题 Duda and Hart[73] If [D=0][G=A] then[L=0] If [I=0][G=A] then[L=0] If [D=1][I=1][G=A] then [L=1] 从Bayes判别(分类)，引入损失函数，变为正则化问题 选择 非线性问题 计算效率 专家系统合理 复杂问题求解 实现智能系统的理想

AI 1956年，以复杂信息处理为契机，提出AI。其动机有二：其一，发展处理符号的方法，其二，处理非线性问题。 1969年，M.Minsky发表颠覆性的报告， “Perceptron”。表象是以XOR问题向以平均为基础的感知机发难，本质是试图以结构方法代替平均。全书使用拓扑作为工具。 过分强调独立性，使得描述任何一个问题，需要穷举出所有可能。80年代，耗资巨大的CYC“失败”了。 需要统计方法成为共识。

20世纪80年代面临的选择 选择 结构学习的困难 字符识别，网络数据建模 先验的结构 误差界指导算法设计 先验概率分布 算法基于线性感知机 概率图模型(Bayes学派): Markov随机场 Bayes网 人工神经网络(频率学派): BP 统计机器学习 Gibbs[1902], Wright[1935] Clifford[1971] Pearl[1988，89] 选择 结构学习的困难 先验的结构 先验概率分布 推断是NPC 字符识别，网络数据建模 误差界指导算法设计 算法基于线性感知机 无需先验知识，无推断 考虑泛化为核心

统计机器学习 从ANN到SML，发展得力于对字符识别的成功 神经网络基于PAC的机器学习基于统计学的机器学习 1986年， Remulhart发表PDP报告，包含非线性BP算法，解决XOR,逼近非线性函数。学术价值不大，人们开始重新尝试“平均”方法。 1991年，Vapnik借用在AI中的PAC，给出基于iid的误差界，基于PAC的统计开始成为主流 贡献: (1)基于iid的误差界指导算法设计，(2)算法设计返回感知机，线性算法，寻找线性空间(核映射)。 基于PAC理论，误差界以1-概率成立。这个参数在泛化意义下的解释：理想，应该趋于0，但是，误差界将趋于无穷，成为平凡界。 新世纪开始，统计学家加入SML，完全放弃PAC(Hastie)。 从ANN到SML，发展得力于对字符识别的成功

维数灾难 由于困难具有本质性，平均遇到大麻烦！ 在高维空间(成百上千)建模，最大的危险就是空间大的程度使得再多的样本，在这个空间上也是稀疏的。 高维空间上的统计理论，多重积分是麻烦，补充“合适”样本是麻烦。“同分布”只能停留在假设上，无法实施。 由于困难具有本质性，平均遇到大麻烦！

概率图模型 结构(全局) + 平均(局部) 将问题考虑为求解Bayes问题 基于平均的研究已经过去20余年，2009年，Koller出版巨著(近1200页)，概率图模型。 结构(全局) + 平均(局部) 将平均放在局部，避免了维数灾问题，同时保证了泛化和模型的可解释性，关键是结构，将局部的平均构造起来。 将问题考虑为求解Bayes问题

概率图模型的三个要素 一、表示 二、推断 三、学习

表示---I-map I-map={ DI L  I L  D S  D S  G S  L } P(I,D,G,L,S)= P(G|I,D) P(L|G) P(S|I) P(I) P(D | I) I与D相互独立 P(G | I, D) P(L | I, D, G) L只与G有关，与其他独立 P(S | I, D, G, L) S只与I有关，与其他独立 P(D, I)=P(D)P(I) P(L, I|G)=P(L|G)P(I|G) P(L, D|G)=P(L|G)P(D|G) I-map={ DI L  I L  D S  D S  G S  L }

求解Bayes问题的策略 使用Markov网表示Bayes问题。 (1)连接的节点保持连接。(2)X与Y有共同子孙，X与Y连接。 由于Bayes网可以简单地转化为Markov网，因此，在统计上，这个方法可以归入Bayes范畴，Markov网成为求解Bayes问题的一个方法。 求解Bayes问题有两个途径：(1)直接求解，困难；(2)变换为Markov网，使用优化方法求解。(与Duda & Hart的思考一致)。

计算是NPC问题(或多重积分，Bayes问题)。 推断，概率查询(Y边缘)：根据给定图，计算P(Y | E = e)。在证据E=e条件下，Y出现的概率(边缘概率)。 (1)根据给定BN，计算联合分布：P() =  P(Xi | PaXi) (2)计算在E下变量Y的边缘分布：P(Y | E) = X-{Y}-EP() 计算是NPC问题(或多重积分，Bayes问题)。 求解Bayes问题的两条路线(Duda(1973), Koller(2009))： (1)直接求解：动态规划、Clique树，蒙特卡洛等。 (2)变分求解：设定目标函数(损失)，化为正则化问题。

学习 假设：给定结构且样本完整(所有变量被赋值)。 任务：学习参数，参数估计。CPD 方法：(1)最大似然估计, (2)Bayes预测 假设：结构未知，但是，样本完整。 任务：学习结构和参数。 考虑一个可能结构的假设空间，结构选择变为优化问题。 假设：样本不完整，或某些变量未知。 任务：发现非显现表现的变量，知识发现。

更为重要的是：通过知识库建立结构(或减小假设空间)。 学习结构的两种策略 假设空间：对结构，就是变量连接的全组合。 A 学习结构：根据某种准则，求出I-map I(G)={A  B} I(G)={A  C} I(G)={A  E} B C I(G)={A  E，B  E， C  D， A  C} 准则：对某个结构的评价---评分。 目标:从假设空间中选择似然最大的模型(结构和参数) D E 更为重要的是：通过知识库建立结构(或减小假设空间)。

历史进程---20年河东，20年河西？ M. Minsky等 1943-1969 平均(数值计算) 感知机 1956-1986 Perceptrons: An introduction to computational geometry. 1969 1943-1969 平均(数值计算) 感知机 1956-1986 结构(符号计算) 人工智能 D. Rumelhart等, Parallel Distributed Processing, 1986 V. Vapnik, The nature of statistical learning theory, 1995 T.Hastie等, The Elements of Statistical Learning, 2003 2000-今后 平均+结构? 概率图模型？ D. Koller等 Probabilistic Graphical Models: Principles and Techniques, 2009 1986-今天 平均(数值计算) 统计机器学习

总结：我们的纠结 统计机器学习以“泛化”为核心。 泛化：大量不确定观察的平均是确定的，排中。iid 难以割舍: (1)大量实际问题需要建立的模型是可泛化的； (2)泛化使得建立的模型是实际问题有依据的近似； (3)不知什么新的标准可以代替泛化。 Koller这本书并没有以泛化为核心，她的宗旨与AI相似。

概率图模型为“描述”与“描述后的预测”提供基础。 前途：“预测”与“描述” 预测与描述是数据挖掘提出的两个任务，但是，数据挖掘的描述任务一直开展不好(啤酒和尿布)。被嘲笑！ 图模型既可以消除噪音且表示紧凑(相对AI的穷举)，还可以对模型的各个部分可解释。前者是预测(泛化)，后者是描述(发现)。 金融和生物等领域，计算机科学有两个策略：其一，代替领域专家(从数据建立可靠(泛化)的模型)，其二，为领域提供工具，简化专家的工作(知识发现)。对这些领域，描述可能更好。对网络、语言、图像等领域，泛化是重要的，但是，发现同样重要。 概率图模型为“描述”与“描述后的预测”提供基础。

愚者浅谈，不足为凭 痴人梦语，切勿轻信 旧路沿袭，艰难度日 新盘洞察，激动人心 谢 谢