1、机器学习的困惑与历史的启示,王珏,第九届机器学习及其应用研讨会2011年11月，清华大学,自然模型,采样,样本集,模型,算法,交叉验证,假设iid,统计机器学习的麻烦,？,设计实验,问题：模型是自然模型吗？,统计机器学习,如果数据不充分，在大变量集合下，如何设计实验，获得新数据。,统计机器学习的困难：实验设计存在组合问题。iid成为与自然模型无关的假设！,特殊函数的逼近,社会的需求,生物、网络、金融、经济和安全等众多领域，大变量集合的海量数据不断涌出，社会迫切需要分析与处理这些数据的有效理论、方法与技术。,寻找分析与处理大变量集合海量数据的新理念、理论、方法与技术成为当前迫切的任务。,历史的故
2、事,线性感知机,基于最小二乘的Rosenblatt的感知机(1956)，其本质是多变量空间上的平均(回归)。,1902年，James的神经元相互连接1943年，McCulloch和Pitts的神经元工作方式1949年，Hebb的学习律。,贡献是：多变量回归的计算方法(神经网络)。,基函数：L = 1D + 2I + 3G + 4S设计算法，确定，获得模型,疑问是：只能解决线性问题，不能满足实际的需要。埋下被批评的口实。,20世纪70年代面临的选择,统计优化(平均)：线性感知机统计模式识别,复杂信息系统(结构)：专家系统句法模式识别,选择,非线性问题计算效率,专家系统合理复杂问题求解实现智能系统
3、的理想,Duda and Hart73,从Bayes判别(分类)，引入损失函数，变为正则化问题,If D=0G=A thenL=0If I=0G=A thenL=0If D=1I=1G=A then L=1,AI,1969年，M.Minsky发表颠覆性的报告， “Perceptron”。表象是以XOR问题向以平均为基础的感知机发难，本质是试图以结构方法代替平均。全书使用拓扑作为工具。,1956年，以复杂信息处理为契机，提出AI。其动机有二：其一，发展处理符号的方法，其二，处理非线性问题。,过分强调独立性，使得描述任何一个问题，需要穷举出所有可能。80年代，耗资巨大的CYC“失败”了。,需要统计
4、方法成为共识。,20世纪80年代面临的选择,概率图模型(Bayes学派):Markov随机场Bayes网,人工神经网络(频率学派):BP统计机器学习,选择,结构学习的困难先验的结构先验概率分布推断是NPC,字符识别，网络数据建模误差界指导算法设计算法基于线性感知机无需先验知识，无推断考虑泛化为核心,Gibbs1902, Wright1935Clifford1971Pearl1988，89,统计机器学习,1991年，Vapnik借用在AI中的PAC，给出基于iid的误差界，基于PAC的统计开始成为主流,1986年， Remulhart发表PDP报告，包含非线性BP算法，解决XOR,逼近非线性函数
5、。学术价值不大，人们开始重新尝试“平均”方法。,从ANN到SML，发展得力于对字符识别的成功,神经网络基于PAC的机器学习基于统计学的机器学习,贡献: (1)基于iid的误差界指导算法设计，(2)算法设计返回感知机，线性算法，寻找线性空间(核映射)。,基于PAC理论，误差界以1-概率成立。这个参数在泛化意义下的解释：理想，应该趋于0，但是，误差界将趋于无穷，成为平凡界。,新世纪开始，统计学家加入SML，完全放弃PAC(Hastie)。,维数灾难,高维空间上的统计理论，多重积分是麻烦，补充“合适”样本是麻烦。“同分布”只能停留在假设上，无法实施。,在高维空间(成百上千)建模，最大的危险就是空间大
6、的程度使得再多的样本，在这个空间上也是稀疏的。,由于困难具有本质性，平均遇到大麻烦！,概率图模型,将平均放在局部，避免了维数灾问题，同时保证了泛化和模型的可解释性，关键是结构，将局部的平均构造起来。,基于平均的研究已经过去20余年，2009年，Koller出版巨著(近1200页)，概率图模型。,结构(全局) + 平均(局部),将问题考虑为求解Bayes问题,一、表示 二、推断 三、学习,概率图模型的三个要素,表示-I-map,P(I,D,G,L,S)=,P(I),P(D | I),P(G | I, D),P(L | I, D, G),P(S | I, D, G, L),P(D, I)=P(D)
7、P(I),P(L|G),P(S|I),P(D),P(L, I|G)=P(L|G)P(I|G),I与D相互独立,L只与G有关，与其他独立,S只与I有关，与其他独立,P(I),P(G|I,D),DI,L I,L D,S D,S G,S L,I-map=,P(L, D|G)=P(L|G)P(D|G),求解Bayes问题的策略,使用Markov网表示Bayes问题。,(1)连接的节点保持连接。(2)X与Y有共同子孙，X与Y连接。,由于Bayes网可以简单地转化为Markov网，因此，在统计上，这个方法可以归入Bayes范畴，Markov网成为求解Bayes问题的一个方法。,求解Bayes问题有两个途径
8、：(1)直接求解，困难；(2)变换为Markov网，使用优化方法求解。(与Duda & Hart的思考一致)。,推断-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)变分求解：
9、设定目标函数(损失)，化为正则化问题。,学习,假设：给定结构且样本完整(所有变量被赋值)。任务：学习参数，参数估计。CPD方法：(1)最大似然估计, (2)Bayes预测,假设：结构未知，但是，样本完整。任务：学习结构和参数。考虑一个可能结构的假设空间，结构选择变为优化问题。,假设：样本不完整，或某些变量未知。任务：发现非显现表现的变量，知识发现。,学习结构的两种策略,D,A,C,B,E,假设空间：对结构，就是变量连接的全组合。,学习结构：根据某种准则，求出I-map,准则：对某个结构的评价-评分。,I(G)=A B,I(G)=A C,I(G)=A E,I(G)=A E，B E， C D， A
10、 C,目标:从假设空间中选择似然最大的模型(结构和参数),更为重要的是：通过知识库建立结构(或减小假设空间)。,历史进程-20年河东，20年河西？,1986-今天平均(数值计算)统计机器学习,1943-1969平均(数值计算)感知机,2000-今后平均+结构?概率图模型？,1956-1986结构(符号计算)人工智能,M. Minsky等 Perceptrons: An introduction to computational geometry. 1969,D. Rumelhart等, Parallel Distributed Processing, 1986 V. Vapnik, The n
11、ature of statistical learning theory, 1995T.Hastie等, The Elements of Statistical Learning, 2003,D. Koller等Probabilistic Graphical Models: Principles and Techniques, 2009,总结：我们的纠结,统计机器学习以“泛化”为核心。,泛化：大量不确定观察的平均是确定的，排中。iid,难以割舍:,(1)大量实际问题需要建立的模型是可泛化的；,(2)泛化使得建立的模型是实际问题有依据的近似；,(3)不知什么新的标准可以代替泛化。,Koller这
12、本书并没有以泛化为核心，她的宗旨与AI相似。,前途：“预测”与“描述”,预测与描述是数据挖掘提出的两个任务，但是，数据挖掘的描述任务一直开展不好(啤酒和尿布)。被嘲笑！,图模型既可以消除噪音且表示紧凑(相对AI的穷举)，还可以对模型的各个部分可解释。前者是预测(泛化)，后者是描述(发现)。,金融和生物等领域，计算机科学有两个策略：其一，代替领域专家(从数据建立可靠(泛化)的模型)，其二，为领域提供工具，简化专家的工作(知识发现)。对这些领域，描述可能更好。对网络、语言、图像等领域，泛化是重要的，但是，发现同样重要。,概率图模型为“描述”与“描述后的预测”提供基础。,谢 谢,愚者浅谈，不足为凭痴人梦语，切勿轻信,旧路沿袭，艰难度日新盘洞察，激动人心,
