[关闭]
@qqiseeu 2015-07-03T06:12:43.000000Z 字数 5708 阅读 2469

Methods of Bounded Difference (1)

Conditional Expectation, Martingales, and Lipschitz condition

Mathematics 读书笔记 ConcentrationInequality


Overview

当随机变量X可表示成多个独立的有界随机变量之和时,可以用Chernoff-Hoeffding Bound为其给出很紧的concentration estimate,但是在很多实际应用中,
首先所研究的量未必能表示成多个随机变量之和的形式,其次随机变量间的独立性条件也未必满足:在更一般的情况中,我们感兴趣的变量Z是关于多个随机变量X1,,Xn的某个函数,
Z=f(X1,,Xn),注意这里Xi之间未必相互独立。当fXi满足某些条件时,可以利用一种称为bounded difference的技术给出concentration estimate,此时甚至不需要知道f的具体形式。
这个技巧的基本原理是用概率论中的一个叫做鞅(martingale)的概念来代替原本的独立性假设,因此先简要介绍鞅的一些性质,并从中出发得到一些初步的结果。

Conditional Expectation

条件期望就是对多个随机变量的函数求部分期望,即将某一部分随机变量视作已知值(即把它们“固定住”,又称conditioned on),然后对剩下的随机变量求期望。例如对函数f(X,Y),其中参数X,Y是随机变量, 要求X关于Y的条件期望(expectation of X conditioned on Y)就是EX[f(X,Y)|Y]这个期望的结果实际上还是一个随机变量——一个关于随机变量Y的函数。下面举几个条件期望的常用性质:

Martingales

所谓鞅(martingale)指的是满足一种“局部相关性”的随机变量序列,作为例子,考虑一个抛掷硬币的游戏:连续抛掷一枚均匀的硬币,若出现正面,则得分+1,反之得分-1,用Sn表示连续抛掷n次后的总得分,易见随机变量S0,S1,并不满足独立性假设,Sn是有之前n次抛掷后的得分S0,,Sn1及第n次抛掷的得分Xn决定,但仔细研究会发现,它们之间的相关性仅体现在某种局部的意义上:

E[Sn|S0,,Sn1]=E[Sn|Sn1]=E[Sn1+Xn|Sn1]=Sn1( E[Xn]=0)

事实上,序列S0,S1,就是一种鞅序列。如果把它看成一种随机游走,则从期望的意义上,该序列不会离它的出发点太远(准确地说是留在原地),这也暗示了鞅有concentration的性质。
下面给出几个后面要用到的定义

前面说过鞅“不会离它的出发点太远“,这个东西形式化一下就是下面的concentration inequality:

(Azuma-Hoeffding Inequality),设X0,X1,是一个鞅,且其满足bounded difference条件,则

Pr[Xn>X0+t],Pr[Xn<X0t]exp(2t2i[n](biai)2)

Generalized Martingales

本节把鞅的定义推广到一组随机变量依赖于另一组随机变量的情况,并给出推广后的Azuma-Hoeffding inequality。
若随机变量序列Y:=Y0,Y1,是关于另一组随机变量序列X:=X0,X1,的函数(精确地说就是存在函数gi使Yi=gi(Xi)),且

E[Yi|Xi1]=Yi1,i1

则称序列Y是关于序列X的鞅序列(martingale with respect to X

一个重要的例子就是所谓的Doob sequence,它是针对任意函数及任意一组随机变量序列所构造出的鞅,由于这个构造过程的普适性,在实际应用中常通过构造Doob序列来得到鞅。

(Doob sequence)任意一个n元函数f,视其n个参数为一个有限长的随机变量序列X1,,Xn,则定义

Yi:=E[f|Xi],0in

特别的,Y0=E[f],Yn=f(X1,,Xn)。称序列Y为函数f关于变量X1,,Xn的Doob序列。
可以证明Doob序列是一个鞅,即E[Yi|Xi1]=Yi1

上一节的Azuma-Hoeffding Inequality也可以推广到本节的generalized martingale上:

(Azuma-Hoeffding Inequality - general version),设Y0,Y1,是一个关于序列X0,X1,的鞅,且Y满足bounded difference条件,则

Pr[Yn>Y0+t],Pr[Yn<Y0t]exp(2t2i[n](biai)2)

鞅的引入是为了放松原本的随机变量X1,X2,间的独立性假设,在这个基础上研究Z=f(X1,,Xn)的concentration性质。由于f的定义可能非常复杂,为了处理一般的情况,我们再为f引入一个所谓的Lipschitz condition;当f满足该条件时,不管其具体形式如何,都有可能为之得到较好的concentration bound。

Lipschitz condition

直观上,Lipschitz condition表明一个函数的图像是比较平缓的,不会变化非常剧烈。由于这里f是一个关于一群随机变量的函数,因此本文中的Lipschitz condition的定义与传统定义略有不同,但含义基本一致。下面分别介绍常用的几种定义,以及在满足该定义的情况下,我们能得到何种concentration bound。

X1,,Xn是任意一组随机变量,f是关于它们的函数。

  1. Averaged bounded difference condition
    i[n],存在ci0使得

    |E[f|Xi]E[f|Xi1]|ci

    则称f满足averaged bounded difference condition.易看出这实际上就是上一节所说的Doob sequence的一种特殊情况:取Yi:=E[f|Xi]即可。而且上一节所给出的generalized Azuma-Hoeffding不等式也可以直接用在这里。设c:=ic2i,则有
    Pr[f>Ef+t],Pr[f<Eft]exp(2t2c)

  2. Averaged Lipschitz condition(ALC)
    若对随机变量Xi任意的两个可能取值ai,ai,存在ci0使

    |E[f|Xi1,Xi=ai]E[f|Xi1,Xi=ai]|ci

    则称f满足averaged Lipschitz condition。直观上说就是,固定前i1个变量,然后让第i个变量取任意的两个值,接着对剩下的变量求条件期望,这样得到的两个随机变量(回忆之前介绍条件期望时所说的,对部分变量求条件期望后得到的结果仍是随机变量)是uniformly bounded by ci.当f满足该条件时,可以得到同之前形式一样的bound:
    Pr[f>Ef+t],Pr[f<Eft]exp(2t2c)

  3. Lipshitz property (or bounded difference condition)
    这个条件一般来说是最容易验证的,因此实践中用的非常多。若对函数f(x1,,xn),存在常数di,i[n]使

    |f(a)f(a)|di

    (其中a,a仅在第i个坐标上的值不同),则称f具有Lipschitz property。此时,X1,,Xn相互独立,则又能得到一个非常面熟的bound:
    Pr[f>Ef+t],Pr[f<Eft]exp(2t2d)

    只是这里由c换成了d=id2i. 然而这个bound在应用时有两个缺点:第一,它要求f的各个参数之间相互独立,这一般需要对变量进行一些替换才能达到(将在下章介绍);第二,在该bounded difference condition中的参数di很可能会远大于前两个bound中的参数ci,导致得到的bound非常松,因而意义不大(易看出ALC条件下的参数ci是恒小于或等于di的).与此相反的是,average bounded difference condition中的参数总是小于ALC条件中的对应ci,因此从该条件出发得到的bound是上述三个bound中最紧的。

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注