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}](http://s2.wordpress.com/latex.php?latex=%5Cdisplaystyle+%5Cmathrm%7BPr%7D%5C%7B%7CX-E%5BX%5D%7C%5Cgeq+u%5C%7D%5Cleq+%5Cfrac%7BV%5BX%5D%7D%7Bu%5E2%7D&bg=fafcff&fg=2a2a2a&s=0 "\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 
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](http://s3.wordpress.com/latex.php?latex=%5Cdisplaystyle+%5Cmathrm%7BPr%7D%5C%7B%7C%5Coverline%7BX%7D-E%5BX%5D%7C%5Cgeq+%5Cepsilon%5C%7D%5Cleq+%5Cfrac%7BV%5B%5Coverline%7BX%7D%5D%7D%7B%5Cepsilon%5E2%7D%3D%5Cfrac%7BV%5BX%5D%7D+%7Bn%5Cepsilon%5E2%7D%5Cunderset%7Bn%5Crightarrow%5Cinfty%7D%7B%5Crightarrow%7D+0&bg=fafcff&fg=2a2a2a&s=0 "\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 E[X]](http://s3.wordpress.com/latex.php?latex=%5Cdisplaystyle+E%5BX%5D&bg=fafcff&fg=2a2a2a&s=0 "\displaystyle E[X]")
Để 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\}](http://s1.wordpress.com/latex.php?latex=%5Cdisplaystyle+%5Cmathrm%7BPr%7D%5C%7B%5Coverline%7BX%7D-E%5BX%5D%5Cgeq+%5Cepsilon%5C%7D%3D%5Cmathrm%7BPr%7D%5Cleft%5C%7B%5Csum_%7Bi%3D1%7D%5En+X_i+-+nE%5BX%5D%5Cgeq+n%5Cepsilon%5Cright%5C%7D&bg=fafcff&fg=2a2a2a&s=0 "\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]](http://s2.wordpress.com/latex.php?latex=%5Cdisplaystyle+%5Cleq+e%5E%7B-sn%5Cepsilon%7D+E%5Cleft%5Be%5E%7Bs%5Csum_%7Bi%3D1%7D%5En+%28X_i+-+E%5BX%5D%29%7D%5Cright%5D+%3D+e%5E%7B-sn%5Cepsilon%7D+%5Cprod_%7Bi%3D1%7D%5En+E%5Cleft%5Be%5E%7Bs%28X_i-E%5BX_i%5D%29%7D%5Cright%5D&bg=fafcff&fg=2a2a2a&s=0 "\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 E[X]=0](http://s2.wordpress.com/latex.php?latex=%5Cdisplaystyle+E%5BX%5D%3D0&bg=fafcff&fg=2a2a2a&s=0 "\displaystyle E[X]=0")
![\displaystyle M_X(s) = E[e^{sX}]\leq e^{s^2(b-a)^2/8}](http://s3.wordpress.com/latex.php?latex=%5Cdisplaystyle+M_X%28s%29+%3D+E%5Be%5E%7BsX%7D%5D%5Cleq+e%5E%7Bs%5E2%28b-a%29%5E2%2F8%7D&bg=fafcff&fg=2a2a2a&s=0 "\displaystyle M_X(s) = E[e^{sX}]\leq e^{s^2(b-a)^2/8}")
Chứng minh: Với mọi 
Lấy kì vọng hai vế suy ra
![\displaystyle E[e^{sX}]\leq \frac{be^{sa}-ae^{sb}}{b-a}](http://s1.wordpress.com/latex.php?latex=%5Cdisplaystyle+E%5Be%5E%7BsX%7D%5D%5Cleq+%5Cfrac%7Bbe%5E%7Bsa%7D-ae%5E%7Bsb%7D%7D%7Bb-a%7D&bg=fafcff&fg=2a2a2a&s=0 "\displaystyle E[e^{sX}]\leq \frac{be^{sa}-ae^{sb}}{b-a}")
Đặt 
Vậy 
Tiếp tục áp dụng bổ đề Hoeffding cho biến ngẫu nhiên ![\displaystyle X_i-E[X_i]](http://s2.wordpress.com/latex.php?latex=%5Cdisplaystyle+X_i-E%5BX_i%5D&bg=fafcff&fg=2a2a2a&s=0 "\displaystyle X_i-E[X_i]")
![\displaystyle \mathrm{Pr}\{\overline{X}-E[X]\geq \epsilon\}\leq e^{-sn\epsilon+ns^2(b-a)^2/8}, \forall s](http://s1.wordpress.com/latex.php?latex=%5Cdisplaystyle+%5Cmathrm%7BPr%7D%5C%7B%5Coverline%7BX%7D-E%5BX%5D%5Cgeq+%5Cepsilon%5C%7D%5Cleq+e%5E%7B-sn%5Cepsilon%2Bns%5E2%28b-a%29%5E2%2F8%7D%2C+%5Cforall+s&bg=fafcff&fg=2a2a2a&s=0 "\displaystyle \mathrm{Pr}\{\overline{X}-E[X]\geq \epsilon\}\leq e^{-sn\epsilon+ns^2(b-a)^2/8}, \forall s")
Chọn 
![\displaystyle \mathrm{Pr}\{\overline{X}-E[X]\geq \epsilon\}\leq e^{-\frac{2n\epsilon^2}{(b-a)^2}}](http://s2.wordpress.com/latex.php?latex=%5Cdisplaystyle+%5Cmathrm%7BPr%7D%5C%7B%5Coverline%7BX%7D-E%5BX%5D%5Cgeq+%5Cepsilon%5C%7D%5Cleq+e%5E%7B-%5Cfrac%7B2n%5Cepsilon%5E2%7D%7B%28b-a%29%5E2%7D%7D&bg=fafcff&fg=2a2a2a&s=0 "\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
Tổng quát hơn, nếu 
![\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}}](http://s2.wordpress.com/latex.php?latex=%5Cdisplaystyle+%5Cmathrm%7BPr%7D%5C%7B%5Coverline%7BX%7D-E%5B%5Coverline%7BX%7D%5D%5Cgeq+%5Cepsilon%5C%7D%5Cleq+e%5E%7B-%5Cfrac%7B2n%5E2%5Cepsilon%5E2%7D%7B%5Csum_%7Bi%3D1%7D%5En%28b_i-a_i%29%5E2%7D%7D&bg=fafcff&fg=2a2a2a&s=0 "\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}}](http://s3.wordpress.com/latex.php?latex=%5Cdisplaystyle+%5Cmathrm%7BPr%7D%5C%7B%7C%5Coverline%7BX%7D-E%5B%5Coverline%7BX%7D%5D%7C%5Cgeq+%5Cepsilon%5C%7D%5Cleq+2e%5E%7B-%5Cfrac%7B2n%5E2%5Cepsilon%5E2%7D%7B%5Csum_%7Bi%3D1%7D%5En%28b_i-a_i%29%5E2%7D%7D&bg=fafcff&fg=2a2a2a&s=0 "\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ụ: 
