logo资料库

林达华数学博文选集.pdf

第1页 / 共78页
第2页 / 共78页
第3页 / 共78页
第4页 / 共78页
第5页 / 共78页
第6页 / 共78页
第7页 / 共78页
第8页 / 共78页
资料共78页,剩余部分请下载后查看
概率模型与计算机视觉
图谱马尔可夫过程聚类结构
和机器学习和计算机视觉相关的数学
介绍几本数学书
Learning中的代数结构的建立
关注数学,解决learning问题
拓扑:游走于直观与抽象之间
Learning和Vision中的小进展和大进展
Notes on Martingales, Random Walks, and Brownian Motion
Book List Updated
空间点过程与随机测度(二):测度的故事
空间点过程与随机测度(一):从数星星说起
关于高性能数值运算
上完第一次数学课
Some recommendations
三月杂记
运动的解释
我的PhD生活
千里积于跬步——流,向量场,和微分方程
在数学的海洋中飘荡
为什么要深入数学的世界
集合论:现代数学的共同基础
分析:在极限基础上建立的宏伟大厦
代数:一个抽象的世界
现代概率论:在现代分析基础上再生
飞雪中迎来2009
Updated math book list
永不消逝的浪漫:Programming Languages and Haskell
MATLAB Implementation: light-weight vs. heavy-weight
高维高斯模型的pdf计算
大量低维高斯模型的pdf计算
Research and Application
变换不变性
MATLAB 2008b
Maths Book List
无处不在的线性分解
关于Alan
概率漫谈
Computer Vision的尴尬
林达华数学博文选集 ©matheecs 编 August 12, 2017 Contents 1 概率模型与计算机视觉 2 图 谱 马尔可夫过程 聚类结构 3 和机器学习和计算机视觉相关的数学 4 介绍几本数学书 5 Learning 中的代数结构的建立 6 关注数学,解决 learning 问题 7 拓扑:游走于直观与抽象之间 8 Learning 和 Vision 中的小进展和大进展 9 Notes on Martingales, Random Walks, and Brownian Motion 10 Book List Updated 11 空间点过程与随机测度(二):测度的故事 12 空间点过程与随机测度(一):从数星星说起 1 3 6 10 11 14 18 21 23 24 25 26 29
13 关于高性能数值运算 14 上完第一次数学课 15 Some recommendations 16 三月杂记 17 运动的解释 18 我的 PhD 生活 19 千里积于跬步——流,向量场,和微分方程 20 在数学的海洋中飘荡 20.1 为什么要深入数学的世界 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20.2 集合论:现代数学的共同基础 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20.3 分析:在极限基础上建立的宏伟大厦 . . . . . . . . . . . . . . . . . . . . . . . . . . . 20.4 代数:一个抽象的世界 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20.5 现代概率论:在现代分析基础上再生 . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 飞雪中迎来 2009 22 Updated math book list 23 永不消逝的浪漫:Programming Languages and Haskell 24 MATLAB Implementation: light-weight vs. heavy-weight 24.1 高维高斯模型的 pdf 计算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24.2 大量低维高斯模型的 pdf 计算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Research and Application 2 34 37 38 39 40 42 44 48 48 48 49 52 54 54 55 56 59 59 62 63
26 变换不变性 27 MATLAB 2008b 28 Maths Book List 29 无处不在的线性分解 30 关于 Alan 31 概率漫谈 32 Computer Vision 的尴尬 1 概率模型与计算机视觉 64 66 67 68 72 73 76 上世纪 60 年代, Marvin Minsky 在 MIT 让他的本科学生 Gerald Jay Sussman 用一个暑假的时间 完成一个有趣的 Project: “link a camera to a computer and get the computer to describe what it saw”。从那时开始,特别是 David Marr 教授于 1977 年正式提出视觉计算理论,计算机视觉已经 走过了四十多年的历史。可是,从今天看来,这个已入不惑之年的学科,依然显得如此年轻而朝气 蓬勃。 在它几十年的发展历程中,多种流派的方法都曾各领风骚于一时。最近二十年中,计算机视觉发展 最鲜明的特征就是机器学习与概率模型的广泛应用。在这里,我简单回顾一下对这个领域产生了重 要影响的几个里程碑: • 1984 年:Stuart Geman 和 Donald Geman 发表了一篇先驱性的论文:Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images. 在这篇文章里,两位 Geman 先生引入了一系列对计算机视觉以后的发展具有深远影响的概念和方法:Markov Random Field (MRF), Gibbs Sampling,以及 Maximum a Posteriori estimate (MAP estimate)。这篇 论文的意义是超前于时代的,它所建立的这一系列方法直到 90 年代中后期才开始被广泛关 注。 • 1991 年:Matthew Turk 和 Alex Pentland 使用 Eigenface 进行人脸分类。从此,以矩阵的代 数分解为基础的方法在视觉分析中被大量运用。其中有代表性的方法包括 PCA, LDA,以及 ICA。 • 1995 年:Corinna Cortes 和 Vladimir Vapnik 提出带有 soft margin 的 Support Vector Machine (SVM) 以及它的 Kernel 版本,并用它对手写数字进行分类。从此,SVM 大受欢迎,并成为 各种应用中的基准分类器。 3
• 1996 年:Bruno Olshausen 和 David Field 提出使用 Overcomplete basis 对图像进行稀疏编 码 (Sparse coding)。这个方向在初期的反响并不热烈。直到近些年,Compressed Sensing 在 信号处理领域成为炙手可热的方向。Sparse coding 在这一热潮的带动下,成为视觉领域一个 活跃的研究方向。 • 90 年代末:Graphical Model 和 Variational Inference 逐步发展成熟。1998 年,MIT 出版社出 版了由 Michale Jordan 主编的文集:Learning in Graphical Models。这部书总结了那一时期 关于 Graphical Model 的建模,分析和推断的主要成果——这些成果为 Graphical Model 在 人工智能的各个领域的应用提供了方法论基础。进入 21 世纪,Graphical Model 和 Bayesian 方法在视觉研究中的运用出现了井喷式的增长。 • 2001 年:John Lafferty 和 Andrew McCallum 等提出 Conditional Random Field (CRF)。CRF 为结构化的分类和预测提供了一种通用的工具。此后,语义结构开始被运用于视觉场景分析。 • 2003 年:David Blei 等提出 Latent Dirichlet Allocation。2004 年:Yee Whye Teh 等提出 Hierarchical Dirichlet Process。各种参数化或者非参数化的 Topic Model 在此后不久被广泛 用于语义层面的场景分析。 • 虽然 Yahn Lecun 等人在 1993 年已提出 Convolutional Neural Network,但在 vision 中的应用 效果一直欠佳。时至 2006 年,Geoffrey Hinton 等人提出 Deep Belief Network 进行 layer-wise 的 pretraining,应用效果取得突破性进展,其与之后 Ruslan Salakhutdinov 提出的 Deep Boltzmann Machine 重新点燃了视觉领域对于 Neural Network 和 Boltzmann Machine 的热 情。 时间进入 2013 年,Probabilistic Graphical Model 早已成为视觉领域中一种基本的建模工具。 Probabilistic Graphical Model 的研究涉及非常多的方面。限于篇幅,在本文中,我只能简要介绍 其中几个重要的方面,希望能为大家提供一些有用的参考。 Graphical Model 的基本类型 基本的 Graphical Model 可以大致分为两个类别:贝叶斯网络 (Bayesian Network) 和马尔可夫随机 场 (Markov Random Field)。它们的主要区别在于采用不同类型的图来表达变量之间的关系:贝叶 斯网络采用有向无环图 (Directed Acyclic Graph) 来表达因果关系,马尔可夫随机场则采用无向图 (Undirected Graph) 来表达变量间的相互作用。这种结构上的区别导致了它们在建模和推断方面的 一系列微妙的差异。一般来说,贝叶斯网络中每一个节点都对应于一个先验概率分布或者条件概率 分布,因此整体的联合分布可以直接分解为所有单个节点所对应的分布的乘积。而对于马尔可夫 场,由于变量之间没有明确的因果关系,它的联合概率分布通常会表达为一系列势函数(potential function)的乘积。通常情况下,这些乘积的积分并不等于 1,因此,还要对其进行归一化才能形成 一个有效的概率分布——这一点往往在实际应用中给参数估计造成非常大的困难。 值得一提的是,贝叶斯网络和马尔可夫随机场的分类主要是为了研究和学习的便利。在实际应用中 所使用的模型在很多时候是它们的某种形式的结合。比如,一个马尔可夫随机场可以作为整体成为 一个更大的贝叶斯网络的节点,又或者,多个贝叶斯网络可以通过马尔可夫随机场联系起来。这种 混合型的模型提供了更丰富的表达结构,同时也会给模型的推断和估计带来新的挑战。 Graphical Model 的新发展方向 在传统的 Graphical Model 的应用中,模型的设计者需要在设计阶段就固定整个模型的结构,比如 它要使用哪些节点,它们相互之间如何关联等等。但是,在实际问题中,选择合适的模型结构往往 4
是非常困难的——因为,我们在很多时候其实并不清楚数据的实际结构。为了解决这个问题,人们 开始探索一种新的建立概率模型的方式——结构学习。在这种方法中,模型的结构在设计的阶段并 不完全固定。设计者通常只需要设定模型结构所需要遵循的约束,然后再从模型学习的过程中同时 推断出模型的实际结构。 结构学习直到今天仍然是机器学习中一个极具挑战性的方向。结构学习并没有固定的形式,不同的 研究者往往会采取不同的途径。比如,结构学习中一个非常重要的问题,就是如何去发现变量之间 的内部关联。对于这个问题,人们提出了多种截然不同的方法:比如,你可以先建立一个完全图连 接所有的变量,然后选择一个子图来描述它们的实际结构,又或者,你可以引入潜在节点 (latent node) 来建立变量之间的关联。 Probabilistic Graphical Model 的另外一个重要的发展方向是非参数化。与传统的参数化方法不同, 非参数化方法是一种更为灵活的建模方式——非参数化模型的大小(比如节点的数量)可以随着 数据的变化而变化。一个典型的非参数化模型就是基于狄利克莱过程 (Dirichlet Process) 的混合模 型。这种模型引入狄利克莱过程作为部件 (component) 参数的先验分布,从而允许混合体中可以 有任意多个部件。这从根本上克服了传统的有限混合模型中的一个难题,就是确定部件的数量。在 近几年的文章中,非参数化模型开始被用于特征学习。在这方面,比较有代表性的工作就是基于 Hierarchical Beta Process 来学习不定数量的特征。 基于 Graphical Model 的统计推断 (Inference) 完成模型的设计之后,下一步就是通过一定的算法从数据中去估计模型的参数,或推断我们感兴趣 的其它未知变量的值。在贝叶斯方法中,模型的参数也通常被视为变量,它们和普通的变量并没有 根本的区别。因此,参数估计也可以被视为是统计推断的一种特例。 除了最简单的一些模型,统计推断在计算上是非常困难的。一般而言,确切推断 (exact inference) 的复杂度取决于模型的 tree width。对于很多实际模型,这个复杂度可能随着问题规模增长而指数 增长。于是,人们退而求其次,转而探索具有多项式复杂度的近似推断 (approximate inference) 方 法。 主流的近似推断方法有三种: (1) 基于平均场逼近 (mean field approximation) 的 variational inference。这种方法通常用于由 Exponential family distribution 所组成的贝叶斯网络。其基本思想就是引入一个 computationally tractable 的 upper bound 逼近原模型的 log partition function,从而有效地降低了优化的复杂度。 大家所熟悉的 EM 算法就属于这类型算法的一种特例。 (2)Belief propagation。这种方法最初由 Judea Pearl 提出用于树状结构的统计推断。后来人们直接 把这种算法用于带环的模型(忽略掉它本来对树状结构的要求)——在很多情况下仍然取得不错 的实际效果,这就是 loop belief propagation。在进一步的探索的过程中,人们发现了它与 Bethe approximation 的关系,并由此逐步建立起了对 loopy belief propagation 的理论解释,以及刻画出 它在各种设定下的收敛条件。值得一提的是,由于 Judea Pearl 对人工智能和因果关系推断方法上 的根本性贡献,他在 2011 年获得了计算机科学领域的最高奖——图灵奖。 基于 message passing 的方法在最近十年有很多新的发展。Martin Wainwright 在 2003 年提出 Tree- reweighted message passing,这种方法采用 mixture of trees 来逼近任意的 graphical model,并利 用 mixture coefficient 和 edge probability 之间的对偶关系建立了一种新的 message passing 的方法。 这种方法是对 belief propagation 的推广。Jason Johnson 等人在 2005 年建立的 walk sum analysis 5
为高斯马尔可夫随机场上的 belief propagation 提供了系统的分析方法。这种方法成功刻画了 belief propagation 在高斯场上的收敛条件,也是后来提出的多种改进型的 belief propagation 的理论依 据。Thomas Minka 在他 PhD 期间所建立的 expectation propagation 也是 belief propagation 的 在一般 Graphical Model 上的重要推广。 (3) 蒙特卡罗采样 (Monte Carlo sampling)。与基于优化的方法不同,蒙特卡罗方法通过对概率模 型的随机模拟运行来收集样本,然后通过收集到的样本来估计变量的统计特性(比如,均值)。采样 方法有三个方面的重要优点。第一,它提供了一种有严谨数学基础的方法来逼近概率计算中经常出 现的积分(积分计算的复杂度随着空间维度的提高呈几何增长)。第二,采样过程最终获得的是整 个联合分布的样本集,而不仅仅是对某些参数或者变量值的最优估计。这个样本集近似地提供了对 整个分布的更全面的刻画。比如,你可以计算任意两个变量的相关系数。第三,它的渐近特性通常 可以被严格证明。对于复杂的模型,由 variational inference 或者 belief propagation 所获得的解一 般并不能保证是对问题的全局最优解。在大部分情况下,甚至无法了解它和最优解的距离有多远。 如果使用采样,只要时间足够长,是可以任意逼近真实的分布的。而且采样过程的复杂度往往较为 容易获得理论上的保证。 蒙特卡罗方法本身也是现代统计学中一个非常重要的分支。对它的研究在过去几十年来一直非常活 跃。在机器学习领域中,常见的采样方法包括 Gibbs Sampling, Metropolis-Hasting Sampling (M-H), Importance Sampling, Slice Sampling, 以及 Hamiltonian Monte Carlo。其中,Gibbs Sampling 由 于可以纳入 M-H 方法中解释而通常被视为 M-H 的特例——虽然它们最初的 motivation 是不一样 的。 Graphical Model 以及与它相关的 probabilistic inference 是一个非常博大的领域,远非本文所能涵 盖。在这篇文章中,我只能蜻蜓点水般地介绍了其中一些我较为熟悉的方面,希望能给在这方面有 兴趣的朋友一点参考。 2 图 谱 马尔可夫过程 聚类结构 题目中所说到的四个词语,都是 Machine Learning 以及相关领域中热门的研究课题。表面看属于 不同的 topic,实际上则是看待同一个问题的不同角度。不少文章论述了它们之间的一些联系,让 大家看到了这个世界的奇妙。 从图说起 这里面,最简单的一个概念就是“图”(Graph),它用于表示事物之间的相互联系。每个图有一批节 点 (Node),每个节点表示一个对象,通过一些边 (Edge) 把这些点连在一起,表示它们之间的关系。 就这么一个简单的概念,它对学术发展的意义可以说是无可估量的。几乎所有领域研究的东西,都 是存在相互联系的,通过图,这些联系都具有了一个统一,灵活,而又强大的数学抽象。因此,很 多领域的学者都对图有着深入探讨,而且某个领域关于图的研究成果,可以被其它领域借鉴。 矩阵表示:让代数进入图的世界 在数学上,一种被普遍使用的表达就是邻接矩阵 (Adjacency Matrix)。一个有 N 个节点的图,可 以用一个 N x N 的矩阵 G 表示,G(i, j) 用一个值表示第 i 个节点和第 j 个节点的联系,通常来说 这个值越大它们关系越密切,这个值为 0 表示它们不存在直接联系。这个表达,很直接,但是非 6
常重要,因为它把数学上两个非常根本的概念联系在一起:“图”(Graph) 和“矩阵”(Matrix)。矩 阵是代数学中最重要的概念,给了图一个矩阵表达,就建立了用代数方法研究图的途径。数学家们 几十年前开始就看到了这一点,并且开创了数学上一个重要的分支——代数图论 (Algebraic Graph Theory)。 代数图论通过图的矩阵表达来研究图。熟悉线性代数的朋友知道,代数中一个很重要的概念叫做 “谱”(Spectrum)。一个矩阵的很多特性和它的谱结构——就是它的特征值和特征向量是密切相关 的。因此,当我们获得一个图的矩阵表达之后,就可以通过研究这个矩阵的谱结构来研究图的特性。 通常,我们会分析一个图的邻接矩阵 (Adjacency Matrix) 或者拉普拉斯矩阵 (Laplace Matrix) 的 谱——这里多说一句,这两种矩阵的谱结构刚好是对称的。 谱:“分而治之”的代数 谱,这个词汇似乎在不少地方出现过,比如我们可能更多听说的频谱,光谱,等等。究竟什么叫 “谱”呢?它的概念其实并不神秘,简单地说,谱这个概念来自“分而治之”的策略。一个复杂的东 西不好直接研究,就把它分解成简单的分量。如果我们把一个东西看成是一些分量叠加而成,那么 这些分量以及它们各自所占的比例,就叫这个东西的谱。所谓频谱,就是把一个信号分解成多个频 率单一的分量。 矩阵的谱,就是它的特征值和特征向量,普通的线性代数课本会告诉你定义:如果 A v = c v,那 么 c 就是 A 的特征值,v 就叫特征向量。这仅仅是数学家发明的一种数学游戏么?——也许有些 人刚学这个的时候,并一定能深入理解这么个公式代表什么。其实,这里的谱,还是代表了一种分 量结构,它为使用“分而治之”策略来研究矩阵的作用打开了一个重要途径。这里我们可以把矩阵 理解为一个操作 (operator),它的作用就是把一个向量变成另外一个向量:y = A x。对于某些向 量,矩阵对它的作用很简单,A v = cv,相当于就把这个向量 v 拉长了 c 倍。我们把这种和矩阵 A 能如此密切配合的向量 v1, v2, ... 叫做特征向量,这个倍数 c1, c2, ... 叫特征值。那么来了一个新 的向量 x 的时候,我们就可以把 x 分解为这些向量的组合,x = a1 v1 + a2 v2 + ...,那么 A 对 x 的作用就可以分解了:A x = A (a1 v1 + a2 v2 + ...) = a1 c1 v1 + a2 c2 v2 ... 所以,矩阵的谱就 是用于分解一个矩阵的作用的。 这里再稍微延伸一点。一个向量可以看成一个关于整数的函数,就是输入 i,它返回 v( i )。它可以 延伸为一个连续函数(一个长度无限不可数的向量,呵呵),相应的矩阵 A 变成一个二元连续函数 (面积无限大的矩阵)。这时候矩阵乘法中的求和变成了积分。同样的,A 的作用可以理解为把一个 连续函数映射为另外一个连续函数,这时候 A 不叫矩阵,通常被称为算子。对于算子,上面的谱 分析方法同样适用(从有限到无限,在数学上还需要处理一下,不多说了)——这个就是泛函分析 中的一个重要部分——谱论(Spectral Theory)。 马尔可夫过程——从时间的角度理解图 回到“图”这个题目,那么图的谱是干什么的呢?按照上面的理解,似乎是拿来分解一个图的。这 里谱的作用还是分治,但是,不是直观的理解为把图的大卸八块,而是把要把在图上运行的过程分 解成简单的过程的叠加。如果一个图上每个节点都有一个值,那么在图上运行的过程就是对这些值 进行更新的过程。一个简单,大家经常使用的过程,就是马尔可夫过程 (Markov Process)。 学过随机过程的朋友都了解马尔可夫过程。概念很简单——“将来只由现在决定,和过去无关”。考 虑一个图,图上每个点有一个值,会被不断更新。每个点通过一些边连接到其它一些点上,对于每 个点,这些边的值都是正的,和为 1。在图上每次更新一个点的值,就是对和它相连接的点的值加 7
权平均。如果图是联通并且非周期(数学上叫各态历经性, ergodicity),那么这个过程最后会收敛到 一个唯一稳定的状态(平衡状态)。 图上的马尔可夫更新过程,对于很多学科有着非常重要的意义。这种数学抽象,可以用在什么地方 呢?(1) Google 对搜索结果的评估 (PageRank) 原理上依赖于这个核心过程,(2) 统计中一种广泛 运用的采样过程 MCMC,其核心就是上述的转移过程,(3) 物理上广泛存在的扩散过程(比如热扩 散,流体扩散)和上面的过程有很重要的类比,(4) 网络中的信息的某些归纳与交换过程和上述过 程相同 (比如 Random Gossiping),还有很多。非常多的实际过程通过某种程度的简化和近似,都 可以归结为上述过程。因此,对上面这个核心过程的研究,对于很多现象的理解有重要的意义。各 个领域的科学家从本领域的角度出发研究这个过程,得出了很多实质上一致的结论,并且很多都落 在了图的谱结构的这个关键点上。 图和谱在此联姻 根据上面的定义,我们看到邻接矩阵 A 其实就是这个马尔可夫过程的转移概率矩阵。我们把各个 节点的值放在一起可以得到一个向量 v,那么我们就可以获得对这个过程的代数表示,v(t+1) = A v(t)。稳定的时候,v = A v。我们可以看到稳定状态就是 A 的一个特征向量,特征值就是 1。这里 谱的概念进来了。我们把 A 的特征向量都列出来 v1, v2, ...,它们有 A vi = ci vi。vi 其实就是一 种很特殊,但是很简单的状态,对它每进行一轮更新,所有节点的值就变成原来的 ci 倍。如果 0 < ci < 1,那么,相当于所有节点的值呈现指数衰减,直到大家都趋近于 0。 一般情况下,我们开始于一个任意一个状态 u,它的更新过程就没那么简单了。我们用谱的方法来 分析,把 u 分解成 u = v1 + c2 v2 + c3 v3 + ... (在数学上可以严格证明,对于上述的转移概率 矩阵,最大的特征值就是 1,这里对应于平衡状态 v1,其它的特征状态 v2, v3, ..., 对应于特征值 1 > c2 > c3 > ... > -1)。那么,我们可以看到,当更新进行了 t 步之后,状态变成 u(t) = v1 + c2t v2 + c3t v3 + ...,我们看到,除了代表平衡状态的分量保持不变外,其它分量随着 t 增长而指数 衰减,最后,其它整个趋近于平衡状态。 从上面的分析看到,这个过程的收敛速度,其实是和衰减得最慢的那个非平衡分量是密切相关的, 它的衰减速度取决于第二大特征值 c2,c2 的大小越接近于 1,收敛越慢,越接近于 0,收敛越快。 这里,我们看到了谱的意义。第一,它帮助把一个图上运行的马尔可夫过程分解为多个简单的字过 程的叠加,这里面包含一个平衡过程和多个指数衰减的非平衡过程。第二,它指出平衡状态是对应 于最大特征值 1 的分量,而收敛速度主要取决于第二大特征值。 我们这里知道了第二大特征值 c2 对于描述这个过程是个至关重要的量,究竟是越大越好,还是越 小越好呢?这要看具体解决的问题。如果你要设计一个采样过程或者更新过程,那么就要追求一个 小的 c2,它一方面提高过程的效率,另外一方面,使得图的结构改变的时候,能及时收敛,从而保 证过程的稳定。而对于网络而言,小的 c2 有利于信息的迅速扩散和传播。 聚类结构——从空间的角度理解图 c2 的大小往往取决于图上的聚类结构。如果图上的点分成几组,各自聚成一团,缺乏组与组之间的 联系,那么这种结构是很不利于扩散的。在某些情况下,甚至需要 O(exp(N)) 的时间才能收敛。这 也符合我们的直观想象,好比两个大水缸,它们中间的只有一根很细的水管相连,那么就需要好长 时间才能达到平衡。有兴趣的朋友可以就这个水缸问题推导一下,这个水缸系统的第二大特征值和 水管流量与水缸的容积的比例直接相关,随比例增大而下降。 对于这个现象进行推广,数学上有一个重要的模型叫导率模型 (Conductance)。具体的公式不说了, 8
分享到:
收藏