在之前关于经验过程和经验风险最小化的文章中,我们提到了这样一个例子:如果我们想要通过最小化经验风险\(\frac{1}{n}\sum_{i=1}^n\ell(y_i,f(x_i))\) 来最小化实际的风险 \(\mathbb{E}\ell(Y,f(X))\),通常是用一个叫“悔恨”的量来刻画这个经验风险最小化的函数的实际损失的. 而对它的控制实际上是通过 \[ \mathcal{R}(\widehat{f})-\mathcal{R}(f^*)\leq 2\sup_{f\in\mathcal{F}}|(P_n-P)f| \] 实现的. 那么在这篇文章中, 我们就来说明如何控制上式的右端项,并得到“悔恨”的收敛速度. 这里用的核心技术就是Rademacher 复杂度. 在这篇文章中,我们主要要把这个右端项和Rademacher复杂度联系起来,来说明为什么通过Rademacher复杂度的收敛,我们可以得到悔恨的收敛阶.
集中不等式(3):鞅差序列与McDiarmid不等式
在前两篇关于集中不等式的文章中,我们从Markov不等式开始,通过Chernoff 界的方法得到了Berstein, Hoeffding不等式等结果,并定义了次高斯、次指数分布的概念. 假设现在观测到了i.i.d.的数据点\(X_1,\cdots, X_n\). 之前我们得到的集中不等式,更多的是在非渐近观点下看到的大数定律的表现. 也就是说,这些不等式更多刻画了样本均值如何集中在总体均值的附近. 如果我们把样本均值看成是样本(数据点的函数),即令\(f(x_1,\cdots,x_n)=n^{-1}\sum_{i=1}^nX_i\), 那么之前的不等式刻画了如下的概率 \[ P(|f(X_1,\cdots,X_n)-\mathbb{E}f(X_1,\cdots,X_n)|>t) \] 对这一表达式,我们能否针对给广泛的函数类型\(f\)给出类似Hoeffding不等式这样的结果呢?答案是可以的!
集中不等式(2):次高斯、次指数分布
我们继续讨论关于集中不等式的相关问题. 在前一篇文章中我们已经介绍了基本的集中不等式(Markov,Chebyshev等等)以及在其它一些更加复杂的集中不等式:Bernstein,Efron-Stein不等式等等. 本文将从次高斯(sub-Gaussian),次指数(sub-Exponential)分布的情形入手,来说明这些指数衰减不等式是如何得到的.
经验过程与经验风险最小化
从这篇文章开始,是我在UW学习高等统计推断课的第二学期的总结. 这个学期的课程中我收获最大的内容就是关于经验过程。这一工具对于有些理论问题,有时甚至有着降维打击的功效. 这我想要从比较高的观点上理解经验过程理论的相关内容,作为这学期期末考试的复习提纲.
从MDS到Isomap
我们继续介绍流形学习相关的内容. 在这篇文章里我们首先讲一个非常经典的算法,MDS(Multidimensional Scaling), 即所谓的多维尺度分析. 接下来我们再对流形学习里非常经典的Isomap做一个介绍. 事实上Isomap是Tenenbaum在MDS的理论框架上进行一定的改进得到的算法. 这篇文章我们主要参考的是《多元统计分析》课程的讲义和Tenenbaum的Isomap原论文.
Donald-Rubin潜在结果模型
从本文开始我们正式进入因果推断的内容.本文我们将要介绍的是因果推断的著名模型Donald-Rubin模型. 因果推断的发展历史悠久,从统计学的两个始祖Pearson和Fisher开始就受到关乎.本文我们将简单介绍因果推断的基本框架. 这篇文章参考的是丁鹏老师的讲义和Imbens 和 Rubins的课本.
马尔可夫链与蒙特卡洛(MCMC)
随着计算机技术的发展,随机模拟成为了人类科学发展的重要工具。从1946年最早的简单版本的Monte-Carlo算法诞生开始,随机模拟方法就开始吸引人们的注意,并在20世纪产生了丰富且深刻的应用结果。被评为20世纪的十大算法之一。随着普通Monte-Carlo算法的不断发展,特别是1970年提出的Metropolis算法促进了这一算法的极大繁荣。1980年代,两个重要的MCMC算法出现在计算机视觉和人工智能领域的研究当中。直至1990年,MCMC算法开始在统计学中有重要影响。现在MCMC算法已经广泛应用在统计学,经济学,计算机科学等各个学科当中. MCMC算法经常被用来解决在高维空间中的积分和优化问题。这两类问题也在现代的机器学习,物理学,统计学,经济学,决策分析等领域扮演着基础性的角色. 本文将对MCMC算法的动机、原理做一些基本介绍,主要参考的是C.Andrieu,N.De Freitas, A. Doucet, M.I.Jordan的一个综述性的介绍文章 An introduction to MCMC for machine learning.
稳健回归
我们考虑残差独立同分布于某个密度函数\(f(\cdot)\)的线性回归模型: \[\begin{equation} Y_i=\mathbf{x}_i'\mathbf{\beta}+\varepsilon_i,\quad \varepsilon_i \ iid \sim f(\cdot) \label{model} \end{equation} \]
其中\(\mathbf{x}_i\)是第\(i\)条记录,它包含了\(p\)个变量,\(\beta\)中包含了截距项的存在. 在使用普通的最小二乘法进行线性回归建模时,我们经常假设\(f\)是正态分布的密度函数. 但是这个假设在实际数据中经常是不能满足的. 例如,如果真实的残差项是厚尾分布的,LSE的结果就会有巨大的偏差. 此时我们就要寻求更加稳健的方法来估计线性回归模型中的参数. 稳健回归的主要思路是降低具有较大残差的项在最小化过程中的权重,从而降低他们对于回归的影响. 在此基础上,产生了一系列的稳健回归方法. 本文主要讨论了M估计,中位数回归等方法,并给出了若干应用的例子. 主要参考线性回归的课本 Applied Regression Analysis 作者是 Norman R. Draper 和 Harry Smith. 第25章。