CS Study Fun – Khoa học máy tính

Learn & Enjoy …

Bất đẳng thức xác suất (2) – Độ tập trung quanh kì vọng (concentration inequalities)

Posted by Trần Quốc Long on Tháng Sáu 21, 2009

Bất đẳng thức Chebyshev cho ta biết cận trên của xác suất một biến ngẫu nhiên nằm xa kì vọng của nó (tail bound):

\displaystyle \mathrm{Pr}\{|X-E[X]|\geq u\}\leq \frac{V[X]}{u^2}

Trong bài này ta sẽ tìm hiểu xác suất nằm gần kì vọng của biến \displaystyle \overline{X}=\frac{1}{n}\sum_{i=1}^n X_i với \displaystyle X_i là các biến ngẫu nhiên độc lập có cùng phân bố xác suất với biến ngẫu nhiên \displaystyle X (independent and identically distributed – i.i.d).

Từ bất đẳng thức Chebyshev

\displaystyle \mathrm{Pr}\{|\overline{X}-E[X]|\geq \epsilon\}\leq \frac{V[\overline{X}]}{\epsilon^2}=\frac{V[X]} {n\epsilon^2}\underset{n\rightarrow\infty}{\rightarrow} 0

Như vậy, khi \displaystyle n\rightarrow\infty, giá trị trung bình \displaystyle \overline{X} càng gần giá trị kì vọng \displaystyle E[X] (theo nghĩa xác suất).

Để bất đẳng thức chặt hơn, ta có thể dùng bất đẳng thức Chernoff

\displaystyle \mathrm{Pr}\{\overline{X}-E[X]\geq \epsilon\}=\mathrm{Pr}\left\{\sum_{i=1}^n X_i - nE[X]\geq n\epsilon\right\}

\displaystyle \leq e^{-sn\epsilon} E\left[e^{s\sum_{i=1}^n (X_i - E[X])}\right] = e^{-sn\epsilon} \prod_{i=1}^n E\left[e^{s(X_i-E[X_i])}\right]

Bổ đề (Hoeffding): Nếu \displaystyle X là biến ngẫu nhiên với \displaystyle a\leq X\leq b\displaystyle E[X]=0 thì

\displaystyle M_X(s) = E[e^{sX}]\leq e^{s^2(b-a)^2/8}

Chứng minh: Với mọi \displaystyle x, do \displaystyle e^{sx} là hàm lồi nên

\displaystyle e^{sx}=e^{\frac{x-a}{b-a}sb+\frac{b-x}{b-a}sa}\leq \frac{x-a}{b-a}e^{sb}+\frac{b-x}{b-a}e^{sa}

Lấy kì vọng hai vế suy ra

\displaystyle E[e^{sX}]\leq \frac{be^{sa}-ae^{sb}}{b-a}

Đặt \displaystyle \phi(s) = \log \frac{be^{sa}-ae^{sb}}{b-a} ta có

\displaystyle \phi(0) = 0, \phi'(0) = 0, \phi''(s) \leq \frac{(b-a)^2}{4},\forall s

Vậy \displaystyle \phi(s) \leq s^2(b-a)^2/8 (đpcm).

Tiếp tục áp dụng bổ đề Hoeffding cho biến ngẫu nhiên \displaystyle X_i-E[X_i] , nếu \displaystyle a\leq X_i\leq b,\forall i, ta được

\displaystyle \mathrm{Pr}\{\overline{X}-E[X]\geq \epsilon\}\leq e^{-sn\epsilon+ns^2(b-a)^2/8}, \forall s

Chọn \displaystyle s để tối thiểu hóa hàm \displaystyle -sn\epsilon+ns^2(b-a)^2/8 ta được

\displaystyle s = \frac{4\epsilon}{(b-a)^2}

\displaystyle \mathrm{Pr}\{\overline{X}-E[X]\geq \epsilon\}\leq e^{-\frac{2n\epsilon^2}{(b-a)^2}}

Vậy ta có định lý

Định lý (Hoeffding): Nếu \displaystyle X là biến ngẫu nhiên với \displaystyle a\leq X\leq b thì

\displaystyle \mathrm{Pr}\{\overline{X}-E[X]\geq \epsilon\}\leq e^{-\frac{2n\epsilon^2}{(b-a)^2}}

Tổng quát hơn, nếu \displaystyle X_i là các biến ngẫu nhiên độc lập và \displaystyle a_i\leq X_i\leq b_i thì

\displaystyle \mathrm{Pr}\{\overline{X}-E[\overline{X}]\geq \epsilon\}\leq e^{-\frac{2n^2\epsilon^2}{\sum_{i=1}^n(b_i-a_i)^2}}

\displaystyle \mathrm{Pr}\{|\overline{X}-E[\overline{X}]|\geq \epsilon\}\leq 2e^{-\frac{2n^2\epsilon^2}{\sum_{i=1}^n(b_i-a_i)^2}}

Bất đẳng thức Hoeffding thường được dùng khi đánh giá chất lượng phân lớp bởi giá trị hàm phân lớp thường bị chặn (ví dụ: \displaystyle \pm 1).

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

 
%d bloggers like this: