机器学习的困惑及历史的启示

1、机器学习的困惑机器学习的困惑与历史的启示与历史的启示王珏王珏第九届机器学习第九届机器学习及其应用研讨会及其应用研讨会2011年年11月，清华大学月，清华大学自自然然模模型型采样采样样本集样本集模型模型算法算法 交叉验证交叉验证 假设假设iid 统计机器学习的麻烦统计机器学习的麻烦？ 设计实验设计实验 问题：问题：模型是自然模型吗？模型是自然模型吗？统计机器学习统计机器学习如果数据不充分，在大变量集合下，如果数据不充分，在大变量集合下，如何设计实验，获得新数据。如何设计实验，获得新数据。统计机器学习的困难：实验设计存在组合问题。统计机器学习的困难：实验设计存在组合问题。iid成为与自然模成为与自

2、然模型无关的假设！型无关的假设！特殊函数的逼近特殊函数的逼近社会的需求社会的需求生物、网络、金融、经济和安全等众多领域，生物、网络、金融、经济和安全等众多领域，大变大变量集合量集合的海量数据不断涌出，社会迫切需要分析与的海量数据不断涌出，社会迫切需要分析与处理这些数据的有效理论、方法与技术。处理这些数据的有效理论、方法与技术。寻找分析与处理大变量集合海量数据的新理念、理寻找分析与处理大变量集合海量数据的新理念、理论、方法与技术成为当前迫切的任务。论、方法与技术成为当前迫切的任务。历史的故事历史的故事线性感知机线性感知机基于最小二乘的基于最小二乘的Rosenblatt的感的感知机知机(1956)

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

4、面临的选择统计优化统计优化(平均平均)：线性感知机线性感知机统计模式识别统计模式识别复杂信息系统复杂信息系统(结构结构)：专家系统专家系统句法模式识别句法模式识别选择选择非线性问题非线性问题计算效率计算效率专家系统合理专家系统合理复杂问题求解复杂问题求解实现智能系统的理想实现智能系统的理想Duda and Hart73从从Bayes判别判别(分类分类)，引入损失函数，变为正引入损失函数，变为正则化问题则化问题If D=0 G=A thenL=0If I=0 G=A thenL=0If D=1 I=1 G=A then L=1AI1969年，年，M.Minsky发表颠覆性的报告，发表颠覆性的报告

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

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

7、8，89统计机器学习统计机器学习1991年，年，Vapnik借用在借用在AI中的中的PAC，给出基于，给出基于iid的误差界，的误差界，基于基于PAC的统计开始成为主流的统计开始成为主流1986年，年， Remulhart发表发表PDP报告，包含非线性报告，包含非线性BP算法，解决算法，解决XOR,逼逼近非线性函数。学术价值不大，人们开始重新尝试近非线性函数。学术价值不大，人们开始重新尝试“平均平均”方法。方法。从从ANN到到SML，发展得力于对字符识别的成功，发展得力于对字符识别的成功神经网络神经网络基于基于PAC的机器学习的机器学习基于统计学的机器学习基于统计学的机器学习贡献贡献: (1)

8、基于基于iid的的误差界指导算法设误差界指导算法设计，计，(2)算法设计返回感知机，线性算法设计返回感知机，线性算法，寻找线性空间算法，寻找线性空间(核映射核映射)。基于基于PAC理论，误差界以理论，误差界以1- 概率成立。这个参数在泛化意义下的解释：概率成立。这个参数在泛化意义下的解释：理想，理想， 应该趋于应该趋于0，但是，误差界将趋于无穷，成为平凡界。，但是，误差界将趋于无穷，成为平凡界。新世纪开始，统计学家加入新世纪开始，统计学家加入SML，完全放弃，完全放弃PAC(Hastie)。维数灾难维数灾难高维空间上的统计理论，多重积分是麻烦，补充高维空间上的统计理论，多重积分是麻烦，补充“合

9、适合适”样本是麻烦。样本是麻烦。“同分布同分布”只能停留在假设上，无法实施。只能停留在假设上，无法实施。在高维空间在高维空间(成百上千成百上千)建模，最大的危险就是空间大建模，最大的危险就是空间大的程度使得再多的样本，在这个空间上也是稀疏的。的程度使得再多的样本，在这个空间上也是稀疏的。由于困难具有本质性，平均遇到大麻烦！由于困难具有本质性，平均遇到大麻烦！概率图模型概率图模型将平均放在局部，避免了维数灾问题，同时保证了泛化和将平均放在局部，避免了维数灾问题，同时保证了泛化和模型的可解释性，关键是结构，将局部的平均构造起来。模型的可解释性，关键是结构，将局部的平均构造起来。基于平均的研究已经过

10、去基于平均的研究已经过去20余年，余年，2009年，年，Koller出版巨出版巨著著(近近1200页页)，概率图模型。，概率图模型。结构结构(全局全局) + 平均平均(局部局部)将问题考虑为求解将问题考虑为求解Bayes问题问题 一、表示一、表示 二、推断二、推断 三、学习三、学习概率图模型的三个要素概率图模型的三个要素表示表示-I-mapP(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)P(I)P(L|G) P(S|I)DIGSLP(D)P(L, I|G)=P(L|G)P(I|G) I

11、与与D相互独立相互独立L只与只与G有关，与其他独立有关，与其他独立S只与只与I有关，与其他独立有关，与其他独立P(I)P(G|I,D)D I 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范畴，范畴，

12、Markov网成为求解网成为求解Bayes问题的一个方法。问题的一个方法。求解求解Bayes问题有两个途径问题有两个途径：(1)直接求解，困难；直接求解，困难；(2)变换为变换为Markov网，网，使用优化方法求解。使用优化方法求解。(与与Duda & Hart的思考一致的思考一致)。推断推断-Bayes问题问题推断，概率查询推断，概率查询(Y边缘边缘)：根据：根据给定图给定图，计算，计算P(Y | E = e)。在证据在证据E=e条件下，条件下，Y出现的概率出现的概率(边缘概率边缘概率)。(1)根据给定根据给定BN，计算联合分布：，计算联合分布：P( ) = P(Xi | PaXi)

13、(2)计算在计算在E下变量下变量Y的边缘分布：的边缘分布：P(Y | E) = X-Y-EP( )计算是计算是NPC问题问题(或多重积分，或多重积分，Bayes问题问题)。求解求解Bayes问题的两条路线问题的两条路线(Duda(1973), Koller(2009)：(1)直接求解：动态规划、直接求解：动态规划、Clique树，蒙特卡洛等。树，蒙特卡洛等。(2)变分求解：设定目标函数变分求解：设定目标函数(损失损失)，化为正则化问题。，化为正则化问题。学习学习假设：给定结构且样本完整假设：给定结构且样本完整(所有变量被赋值所有变量被赋值)。任务：学习参数，参数估计。任务：学习参数，参数估计。

14、CPD方法：方法：(1)最大似然估计最大似然估计, (2)Bayes预测预测假设：结构未知，但是，样本完整。假设：结构未知，但是，样本完整。任务：学习结构和参数。任务：学习结构和参数。考虑一个可能考虑一个可能结构的假设空间结构的假设空间，结构选择变为优化问题。，结构选择变为优化问题。假设：样本不完整，或某些变量未知。假设：样本不完整，或某些变量未知。任务：发现非显现表现的变量，知识发现。任务：发现非显现表现的变量，知识发现。 学习结构的两种策略学习结构的两种策略DACBE假设空间：对结构，就是变量连接的全组合。假设空间：对结构，就是变量连接的全组合。学习结构：根据某种准则，求出学习结构：根据某

15、种准则，求出I-map准则：对某个结构准则：对某个结构的评价的评价-评分。评分。I(G)=A BI(G)=A CI(G)=A EI(G)=A E，B E， C D， A C目标目标:从假设空间中选择似从假设空间中选择似然最大的模型然最大的模型(结构和参数结构和参数)更为重要的是：通过知识库建立结构更为重要的是：通过知识库建立结构(或减小假设空间或减小假设空间)。历史进程历史进程-20年河东，年河东，20年河西？年河西？1986-今天今天平均平均(数值计算数值计算)统计机器学习统计机器学习1943-1969平均平均(数值计算数值计算)感知机感知机2000-今后今后平均平均+结构结构?概率图模型概

16、率图模型？1956-1986结构结构(符号计算符号计算)人工智能人工智能M. Minsky等等 Perceptrons: An introduction to computational geometry. 1969D. Rumelhart等等, Parallel Distributed Processing, 1986 V. Vapnik, The nature of statistical learning theory, 1995T.Hastie等等, The Elements of Statistical Learning, 2003D. Koller等等Probabilistic G

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

18、核心，她的宗旨与AI相似。相似。前途：前途：“预测预测”与与“描述描述”预测与描述是数据挖掘提出的两个任务，但是，数据挖掘的描述预测与描述是数据挖掘提出的两个任务，但是，数据挖掘的描述任务一直开展不好任务一直开展不好(啤酒和尿布啤酒和尿布)。被嘲笑！。被嘲笑！图模型既可以消除噪音且表示紧凑图模型既可以消除噪音且表示紧凑(相对相对AI的穷举的穷举)，还可以对模，还可以对模型的各个部分可解释。前者是预测型的各个部分可解释。前者是预测(泛化泛化)，后者是描述，后者是描述(发现发现)。金融和生物等领域，计算机科学有两个策略：其一，代替领域专金融和生物等领域，计算机科学有两个策略：其一，代替领域专家家(