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

Learn & Enjoy …

Archive for the ‘Công cụ xác suất’ Category

« Những bài viết trước

Độ tập trung quanh kì vọng (concentration inequalities) (2) – McDiarmid inequality

Đăng bởi tqlong on Tháng Sáu 23, 2009

Tổng quát hóa bất đẳng thức Hoeffding cho lớp hàm bị chặn ta được bất đẳng thức McDiarmid như sau

Định lý (McDiarmid): Nếu hàm \displaystyle f: \mathbb{R}^n \rightarrow R sao cho

\displaystyle f(x_1,\ldots,x_i,\ldots, x_n) - f(x_1,\ldots,x_i',\ldots, x_n) \leq c_i,\forall x_1,\ldots, x_n, x_i', \forall i

và các biến \displaystyle X_1,\ldots,X_n độc lập xác suất thì

\displaystyle \mathrm{Pr}_{X_1,\ldots,X_n}\{f - E[f]\geq\epsilon\}\leq \exp \left\{-\frac{2\epsilon^2}{\sum_{i=1}^n c_i^2} \right\}

Ta thấy bất đẳng thức Hoeffding là hệ quả của bất đẳng thức McDiarmid với hàm \displaystyle f(X_1,\ldots,X_n) = \frac{1}{n}\sum_{i=1}^n X_i.

Chứng minh: Đặt \displaystyle Z_i = E[f(X_1,\ldots,X_n)|X_1,\ldots, X_i] là kì vọng của hàm \displaystyle f nếu biết trước giá trị của \displaystyle i biến đầu tiên. Như vậy

\displaystyle Z_0 = E[f], Z_n = f

\displaystyle f - E[f] = Z_n - Z_0 = \sum_{i=1}^n Z_i - Z_{i-1}

Theo bất đẳng thức Chernoff, với mọi \displaystyle s ta có

\displaystyle \mathrm{Pr}\{f - E[f]\geq \epsilon\} = e^{-s\epsilon}E\left[\exp \left\{s \sum_{i=1}^n Z_i - Z_{i-1}\right\}\right]

\displaystyle = e^{-s\epsilon}E\left[E\left[\left.\exp \left\{s \sum_{i=1}^n Z_i - Z_{i-1}\right\}\right|X_1,\ldots,X_{n-1}\right]\right]

\displaystyle = e^{-s\epsilon}E\left[\exp \left\{s \sum_{i=1}^{n-1} Z_i - Z_{i-1}\right\}E\left[\left.e^{s(Z_n - Z_{n-1}) }\right|X_1,\ldots,X_{n-1}\right]\right]

Bây giờ ta đánh giá \displaystyle E\left[\left.e^{s(Z_n - Z_{n-1}) }\right|X_1,\ldots,X_{n-1}\right] bằng bổ đề Hoeffding.

Đặt \displaystyle Y = Z_n - Z_{n-1}|X_1,\ldots,X_{n-1}. Ta có

\displaystyle E[Y] = E[Z_n - Z_{n-1}|X_1,\ldots,X_{n-1}] = 0

Đặt

\displaystyle U_n = \sup_u E[f|X_1,\ldots,X_{n-1},u]-E[f|X_1,\ldots,X_{n-1}]

\displaystyle L_n = \inf_u E[f|X_1,\ldots,X_{n-1},u]-E[f|X_1,\ldots,X_{n-1}]

Ta có \displaystyle L_i\leq Y\leq U_i và \displaystyle U_n-L_n\leq c_n

Vậy \displaystyle E[e^{sY}]\leq e^{s^2 c_n^2/8}.

Tiếp tục ta được

\displaystyle \mathrm{Pr}\{f - E[f]\geq \epsilon\}\leq e^{-s\epsilon}E\left[\exp \left\{s \sum_{i=1}^{n-1} Z_i - Z_{i-1}\right\}\right] e^{s^2 c_n^2/8}

\displaystyle \leq \exp\left\{-s\epsilon+\frac{1}{8}s^2\sum_{i=1}^nc_i^2\right\}

Chọn \displaystyle s để cực tiểu hóa hàm \displaystyle -s\epsilon+\frac{1}{8}s^2\sum_{i=1}^nc_i^2 ta được điều phải chứng minh.

Đăng trong Công cụ xác suất | Tagged: , | Leave a Comment »

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

Đăng bởi tqlong 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 và \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} và

\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).

Đăng trong Công cụ xác suất | Tagged: , , | Leave a Comment »

« Những bài viết trước