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

Learn & Enjoy …

Nguyên tắc tối thiểu hóa rủi ro thực nghiệm (3) – Kì vọng Rademacher

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

Trong bài trước, ta đã biết ước lượng rủi ro kì vọng trong trường hợp lớp hàm \displaystyle \mathcal{F} hữu hạn. Trong bài này, ta sẽ tìm hiểu một công cụ để ước lượng rủi ro kì vọng trong trường hợp \displaystyle \mathcal{F} là tập vô hạn.

Định nghĩa (biến ngẫu nhiên Rademacher): Biến ngẫu nhiên \displaystyle \epsilon\in \{+1,-1\}biến ngẫu nghiên Rademacher nếu \displaystyle \mathrm{Pr}\{\epsilon=+1\}=\mathrm{Pr}\{\epsilon=-1\}=1/2\displaystyle \epsilon độc lập với tất cả các sự kiện ngẫu nhiên khác.

Biến ngẫu nhiên Rademacher có thể coi như là một loại nhiễu (noise).

Để ước lượng chênh lệch giữa rủi ro kì vọng và rủi ro thực nghiệm, ta cần ước lượng

\displaystyle \mathrm{Pr}\left\{\sup_{f\in \mathcal{F}} \left(R(f)-\widehat{R}(f)\right)\geq C\right\}

Ta thấy \displaystyle R(f) = E[L(f(X),Y)], để phân tích tổng quát, ta xét lớp hàm \displaystyle L_{\mathcal{F}}=\{g(z)=g(x,y)=L(f(x),y)|\forall f\in \mathcal{F}\}. Như vậy, với mọi \displaystyle f\in \mathcal{F}, có một hàm \displaystyle g\in L_{\mathcal{F}} tương ứng để \displaystyle R(f)=E[g(Z)]\displaystyle \widehat{R}(f) = \frac{1}{n}\sum_{i=1}^ n g(z_i), z_i=(x_i,y_i), \forall i=1,\ldots,n.

Như vậy, ta cần ước lượng

\displaystyle \mathrm{Pr}\left\{\sup_{g\in L_{\mathcal{F}}} \left(E[g(Z)]- \frac{1}{n}\sum_{i=1}^ n g(Z_i)\right)\geq C\right\}

Để ý là hàm \displaystyle \sup_{g\in L_{\mathcal{F}}} \left(E[g(Z)]- \frac{1}{n}\sum_{i=1}^ n g(Z_i)\right) = d(Z_1,\ldots,Z_n) là một hàm của \displaystyle n biến ngẫu nhiên độc lập \displaystyle Z_1,\ldots,Z_n. Do đó nếu \displaystyle g(z)=L(f(x),y) bị chặn trong khoảng \displaystyle [a,b], theo bất đẳng thức McDiarmid, theo nghĩa xác suất, giá trị này phải gần với kì vọng của nó.

Áp dụng bất đẳng thức McDiarmid, do thay đổi \displaystyle Z_i chỉ làm hàm này thay đổi nhiều nhất \displaystyle (b-a)/m nên

\displaystyle \mathrm{Pr}\left\{d-E[d]\geq\epsilon\right\}\leq \exp\left\{-\frac{2n\epsilon^ 2}{(b-a)^ 2}\right\}=\delta

Chọn \displaystyle \epsilon=(b-a)\sqrt{\frac{\log\frac{1}{\delta}}{2n}} ta được

\displaystyle \mathrm{Pr}\left\{d-E[d]\leq(b-a)\sqrt{\frac{\log\frac{1}{\delta}}{2n}}\right\}\geq 1-\delta

Để tiếp tục ta cần ước lượng giá trị kì vọng

\displaystyle E[d] = E\left[\sup_{g\in L_{\mathcal{F}}} \left(E[g(Z)]- \frac{1}{n}\sum_{i=1}^ n g(Z_i)\right)\right]

trong đó giá trị kì vọng được tính trên các biến ngẫu nhiên \displaystyle Z_1,\ldots,Z_n.

Định lý: Gọi \displaystyle \epsilon_1,\ldots,\epsilon_n là các biến ngẫu nhiên Rademacher. Với mọi lớp hàm \displaystyle \mathcal{G} ta có

\displaystyle E_Z\left[\sup_{g\in \mathcal{G}} \left(E[g(Z)]- \frac{1}{n}\sum_{i=1}^ n g(Z_i)\right)\right]\leq 2 E_{Z,\epsilon}\left[\sup_{g\in \mathcal{G}} \frac{1}{n}\sum_{i=1}^ n\epsilon_i g(Z_i)\right]

trong đó \displaystyle \mathcal{R}_n(\mathcal{G})=E_{Z,\epsilon}\left[\sup_{g\in \mathcal{G}} \frac{1}{n}\sum_{i=1}^ n\epsilon_i g(Z_i)\right] gọi là kỳ vọng Rademacher của lớp hàm \displaystyle \mathcal{G}. Kì vọng này được tính trên các biến ngẫu nhiên \displaystyle Z_i,\epsilon_i,i=1,\ldots,n. Kỳ vọng Rademacherthuộc tính của một lớp hàm chứ không phải thuộc tính của một hàm cụ thể.

Ta thấy đại lượng \displaystyle \sum_{i=1}^ n\epsilon_i g(Z_i) là tích vô hướng của 2 véctơ \displaystyle (\epsilon_1,\ldots,\epsilon_n)\displaystyle (g(Z_1),\ldots,g(Z_n). Như vậy, kì vọng Rademacher đánh giá sự “giống nhiễu” của lớp hàm \displaystyle \mathcal{G}.

Chứng minh: Sử dụng một kỹ thuật gọi là tập mẫu giả (ghost sample). Ta xét các biến ngẫu nhiên \displaystyle Z_1',\ldots, Z_n' độc lập có cùng phân bố với \displaystyle Z_1,\ldots,Z_n.

\displaystyle E_Z\left[\sup_{g\in \mathcal{G}} \left(E[g(Z)]- \frac{1}{n}\sum_{i=1}^ n g(Z_i)\right)\right]

\displaystyle = E_Z\left[\sup_{g\in \mathcal{G}} \left(\frac{1}{n}\sum_{i=1}^ n E[g(Z)]-g(Z_i)\right)\right]

\displaystyle =E_Z\left[\sup_{g\in \mathcal{G}} \left(\frac{1}{n}\sum_{i=1}^ n E_{Z'}[g(Z_i')]-g(Z_i)\right)\right]

\displaystyle =E_Z\left[\sup_{g\in \mathcal{G}} \left(\frac{1}{n}\sum_{i=1}^ n E_{Z'}[g(Z_i')-g(Z_i)~ |~ Z]\right)\right]

\displaystyle \leq E_Z\left[E_{Z'}\left[\left.\sup_{\mathcal{G}} \left(\frac{1}{n}\sum_{i=1}^ n g(Z_i')-g(Z_i) \right)\right| Z\right]\right] (do \displaystyle \sup E[\cdot] \leq E[\sup [\cdot]])

\displaystyle =E_{Z,Z'}\left[\sup_{g\in \mathcal{G}} \frac{1}{n}\sum_{i=1}^ n g(Z_i')-g(Z_i)\right] (quá trình biến đổi đến đây còn gọi là quá trình đối xứng hóasymmetrization).

\displaystyle =E_{Z,Z',\epsilon}\left[\sup_{g\in \mathcal{G}} \frac{1}{n}\sum_{i=1}^ n \epsilon_i(g(Z_i')-g(Z_i))\right]
(do \displaystyle \epsilon_i(g(Z_i')-g(Z_i)) có cùng phân bố với \displaystyle g(Z_i')-g(Z_i) )

\displaystyle \leq E_{Z',\epsilon}\left[\sup_{g\in \mathcal{G}} \frac{1}{n}\sum_{i=1}^ n\epsilon_i g(Z_i')\right] + E_{Z,\epsilon}\left[\sup_{g\in \mathcal{G}} \frac{1}{n}\sum_{i=1}^ n\epsilon_i g(Z_i)\right]

\displaystyle = 2E_{Z,\epsilon}\left[\sup_{g\in \mathcal{G}} \frac{1}{n}\sum_{i=1}^ n\epsilon_i g(Z_i)\right] = 2 \mathcal{R}_n(\mathcal{G})

Hệ quả 1: Do \displaystyle \mathcal{R}_n(\mathcal{G}) = \mathcal{R}_n(-\mathcal{G}) nên

\displaystyle E_Z\left[\sup_{g\in \mathcal{G}} \left(\frac{1}{n}\sum_{i=1}^ n g(Z_i)-E[g(Z)]\right)\right]\leq 2 \mathcal{R}_n(\mathcal{G})

Hệ quả 2: Tiếp tục phân tích bên trên ta được

\displaystyle \mathrm{Pr}\left\{\sup_{g\in L_{\mathcal{F}}} \left(E[g(Z)]- \frac{1}{n}\sum_{i=1}^ n g(Z_i)\right)\leq 2\mathcal{R}_n(L_{\mathcal{F}})+ (b-a)\sqrt{\frac{\log\frac{1}{\delta}}{2n}}\right\}\geq 1-\delta

hay, tương đương với

\displaystyle \mathrm{Pr}\left\{\sup_{f\in \mathcal{F}}\left(R(f) - \widehat{R}(f)\right)\leq 2\mathcal{R}_n(L_{\mathcal{F}})+ (b-a)\sqrt{\frac{\log\frac{1}{\delta}}{2n}}\right\}\geq 1-\delta

Bây giờ xét hàm \displaystyle \widehat{f}=\arg\min_{f\in \mathcal{F}}\widehat{R}(f)\displaystyle f^ *=\arg\min_{f\in \mathcal{F}}R(f) , ta có

Với xác suất ít nhất \displaystyle 1-\delta:

\displaystyle R(\widehat{f}) \leq\widehat{R}(\widehat{f}) + 2\mathcal{R}_n(L_{\mathcal{F}})+ (b-a)\sqrt{\frac{\log\frac{1}{\delta}}{2n}}

\displaystyle \leq \widehat{R}(f^ *) + 2\mathcal{R}_n(L_{\mathcal{F}})+ (b-a)\sqrt{\frac{\log\frac{1}{\delta}}{2n}} (do \displaystyle \widehat{R}(\widehat{f})\leq\widehat{R}(f^ *) )

Áp dụng bất đẳng thức McDiarmid một lần nữa với hàm \displaystyle \widehat{R}(f^ *)\displaystyle E[\widehat{R}(f^ *)]=R(f^ *) ta được, với xác suất ít nhất \displaystyle 1-\delta:

\displaystyle \widehat{R}(f^ *)\leq R(f^ *) + (b-a)\sqrt{\frac{\log\frac{1}{\delta}}{2n}}

Kết hợp lại ta có định lý sau

Định lý: Với hàm lỗi bị chặn trong khoảng \displaystyle [a,b] ta có

\displaystyle \mathrm{Pr}\left\{R(\widehat{f})-R(f^ *)\leq 2\mathcal{R}_n(L_{\mathcal{F}})+ 2(b-a)\sqrt{\frac{\log\frac{1}{\delta}}{2n}}\right\}\geq 1-2\delta

Chứng minh: Xác suất để sự kiện \displaystyle R(\widehat{f})\leq \widehat{R}(f^ *) + 2\mathcal{R}_n(L_{\mathcal{F}})+ (b-a)\sqrt{\frac{\log\frac{1}{\delta}}{2n}} không xảy ra nhiều nhất là \displaystyle \delta. Xác suất để sự kiện \displaystyle \widehat{R}(f^ *)\leq R(f^ *) + (b-a)\sqrt{\frac{\log\frac{1}{\delta}}{2n}} không xảy ra nhiều nhất là \displaystyle \delta. Như vậy, xác suất để một trong hai sự kiện không xảy ra nhiều nhất là \displaystyle 2\delta (ước lượng xác suất tổng). Nghĩa là xác suất để cả hai sự kiện cùng xảy ra ít nhất là \displaystyle 1-2\delta.

Như vậy chênh lệch rủi ro kì vọng của \displaystyle \widehat{f}\displaystyle f^ * phụ thuộc vào kỳ vọng Rademacher của lớp hàm \displaystyle L_{\mathcal{F}}. Trong bài sau ta sẽ tìm cách ước lượng kì vọng này.

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: