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

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

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

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

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

4 历史的故事

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

6 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判别(分类)，引入损失函数，变为正则化问题 选择 非线性问题 计算效率 专家系统合理 复杂问题求解 实现智能系统的理想

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

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

9 统计机器学习 从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，发展得力于对字符识别的成功

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

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

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

13 表示---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 }

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

15 计算是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)变分求解：设定目标函数(损失)，化为正则化问题。

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

17 更为重要的是：通过知识库建立结构(或减小假设空间)。
学习结构的两种策略 假设空间：对结构，就是变量连接的全组合。 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 更为重要的是：通过知识库建立结构(或减小假设空间)。

18 历史进程---20年河东，20年河西？ M. Minsky等 1943-1969 平均(数值计算) 感知机 1956-1986
Perceptrons: An introduction to computational geometry. 1969 平均(数值计算) 感知机 结构(符号计算) 人工智能 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-今天 平均(数值计算) 统计机器学习

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

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

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