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 (4) – Ước lượng kì vọng Rademacher, chiều VC

Posted by Trần Quốc Long trên Tháng Bảy 7, 2009

Bài trước cho thấy mối quan hệ giữa \displaystyle R(\widehat{f}) và \displaystyle R(f^*) liên quan đến kỳ vọng Rademacher \displaystyle \mathcal{R}_n(L_{\mathcal{F}}) của lớp hàm \displaystyle L_{\mathcal{F}} = \{L(f(x),y), \forall f\in \mathcal{F}\}.

Định lý: Nếu \displaystyle f(x)\in \{+1,-1\} và hàm lỗi \displaystyle L(y',y) là hàm lỗi 0-1,

\displaystyle L(y',y) = I(y=y') = (1-yy')/2,

ta có \displaystyle \mathcal{R}_n(L_{\mathcal{F}}) = \frac{1}{2} \mathcal{R}_n(\mathcal{F}).

Chứng minh: Theo định nghĩa

\displaystyle \mathcal{R}_n(L_{\mathcal{F}}) = E_{X,Y,\epsilon}\left[\sup_{f \in \mathcal{F}}\frac{1}{n}\sum_{i=1}^n \epsilon_i\frac{1-Y_if(X_i)}{2} \right]

\displaystyle =\frac{1}{2} E_{X,Y,\epsilon}\left[\sup_{f \in \mathcal{F}}\frac{1}{n}\sum_{i=1}^n (\epsilon_i Y_i) f(X_i)\right] (do \displaystyle E[\epsilon_i] = 0)

\displaystyle = \frac{1}{2} E_{X,\epsilon}\left[\sup_{f \in \mathcal{F}}\frac{1}{n}\sum_{i=1}^n \epsilon_i f(X_i)\right] = \frac{1}{2}\mathcal{R}_n(\mathcal{F}) (do \displaystyle \epsilon_i có cùng phân bố với \displaystyle \epsilon_iY_i)

Nhận xét: Định lý cho phép liên hệ giữa kì vọng Rademacher của lớp hàm \displaystyle L_{\mathcal{F}} và kì vọng Rademacher của \displaystyle \mathcal{F}.

Nếu đặt \displaystyle \Pi_{\mathcal{F}}(X) = \{(f(X_1), \ldots, f(X_n)|f\in \mathcal{F}\}\subset \{+1,-1\}^n là tập tất cả các khả năng phân lớp của lớp hàm \displaystyle \mathcal{F} trên tập mẫu học \displaystyle X_1,\ldots,X_n (Ta đã biết đây chính là khái niệm phá vỡ (shatter) đã giới thiệu trong bài này). Ta có

\displaystyle \sup_{f \in \mathcal{F}}\frac{1}{n}\sum_{i=1}^n \epsilon_i f(X_i)=\sup_{a\in \Pi_{\mathcal{F}}(X)}\epsilon_i a_i

tức là đại lượng này không phụ thuộc vào số lượng hàm trong \displaystyle \mathcal{F} mà phụ thuộc vào việc lớp hàm này có thể phá vỡ (shatter) tập mẫu học \displaystyle X_1,\ldots, X_n đến mức nào.

Để ước lượng \displaystyle \mathcal{R}_n(\mathcal{F}) ta có bổ đề sau:

Bổ đề lớp hữu hạn Massart (Massart’s finite class lemma): Cho \displaystyle \mathcal{A}\subset \mathbb{R}^n là một tập hữu hạn, \displaystyle \epsilon_1,\ldots,\epsilon_n là các biến ngẫu nhiên Rademacher, ta có

\displaystyle E_\epsilon\left[\sup_{a\in \mathcal{A}}\frac{1}{n}\sum_{i=1}^n\epsilon_i a_i \right]\leq \frac{r\sqrt{2\log |\mathcal{A}|}}{n} .

trong đó \displaystyle r = \max_{a\in \mathcal{A}}\|a\|.

Chứng minh: Xét đại lượng \displaystyle R = E_\epsilon\left[\sup_{a\in \mathcal{A}}\sum_{i=1}^n\epsilon_i a_i \right]. Với mọi \displaystyle s\in \mathbb{R}, ta có

\displaystyle e^{s R}\leq E_\epsilon\left[\exp \left(\sup_{a\in \mathcal{A}}s\sum_{i=1}^n\epsilon_i a_i\right) \right] (bất đẳng thức Jensen, do hàm \displaystyle e^x là hàm lồi)

\displaystyle = E_\epsilon\left[\sup_{a\in \mathcal{A}}\exp \left(s\sum_{i=1}^n\epsilon_i a_i\right) \right] (do \displaystyle e^x là hàm đồng biến)

\displaystyle \leq E_\epsilon\left[\sum_{a\in \mathcal{A}}\exp \left(s\sum_{i=1}^n\epsilon_i a_i\right) \right] (do \displaystyle e^x>0,\forall x)

\displaystyle = \sum_{a\in \mathcal{A}}E_\epsilon\left[\exp \left(s\sum_{i=1}^n\epsilon_i a_i\right) \right] (do \displaystyle E[X+Y]=E[X]+E[Y])

\displaystyle = \sum_{a\in \mathcal{A}} \prod_{i=1}^n E_{\epsilon_i}\left[e^{s\epsilon_i a_i}\right] (do \displaystyle \epsilon_1,\ldots,\epsilon_n độc lập)

\displaystyle = \sum_{a\in \mathcal{A}} \prod_{i=1}^n \frac{e^{sa_i}+e^{-sa_i}}{2} (do \displaystyle \epsilon_i là biến Rademacher)

\displaystyle \leq \sum_{a\in \mathcal{A}} \prod_{i=1}^n e^{s^2a_i^2/2} (do \displaystyle \cosh(x)=\frac{e^x+e^{-x}}{2}\leq e^{x^2/2}, tra Wikipedia để biết khai triển Taylor của hàm \displaystyle \cosh(x) rồi so sánh với khai triển Taylor của \displaystyle e^{x^2/2})

\displaystyle = \sum_{a\in \mathcal{A}} e^{s^2\|a\|^2/2} \leq |\mathcal{A}| e^{s^2r^2/2}

Lấy loga cả hai vế ta được \displaystyle R\leq \frac{\log|\mathcal{A}|}{s}+sr^2/2. Chọn \displaystyle s để tối thiểu hóa vế phải ta được \displaystyle s = \frac{\sqrt{2\log|\mathcal{A}|}}{r} và \displaystyle R\leq r\sqrt{2\log|\mathcal{A}|} (đpcm).

Bổ đề Massart giúp ta ước lượng \displaystyle \mathcal{R}_n(\mathcal{F}) qua định lý sau

Định lý: Với lớp hàm phân lớp \displaystyle \mathcal{F} mà \displaystyle f(x)\in \{+1,-1\},\forall f\in \mathcal{F} và \displaystyle G_{\mathcal{F}}(n) là hàm tăng trưởng (growth function) của \displaystyle \mathcal{F} ta có

\displaystyle \mathcal{R}_n(\mathcal{F})\leq \sqrt{\frac{2\log G_{\mathcal{F}}(n)}{n}}.

Chứng minh: Ta có

\displaystyle \mathcal{R}_n(\mathcal{F}) = E_{X,\epsilon}\left[\sup_{f \in \mathcal{F}}\frac{1}{n}\sum_{i=1}^n \epsilon_i f(X_i)\right]

\displaystyle = E_X\left[E_\epsilon\left[\left.\sup_{f \in \mathcal{F}}\frac{1}{n}\sum_{i=1}^n \epsilon_i f(X_i)\right|X\right]\right]

\displaystyle \leq E_X\left[\frac{r_X\sqrt{2\log|\Pi_{\mathcal{F}}(X)|}}{n}\right]

\displaystyle \leq E_X\left[\sqrt{\frac{2\log G_{\mathcal{F}}(n)}{n}}\right] = \sqrt{\frac{2\log G_{\mathcal{F}}(n)}{n}} (do \displaystyle r_X\leq \sqrt{n} và định nghĩa của hàm tăng trưởng (growth function))

Hệ quả: Nếu chiều VC của lớp hàm \displaystyle \mathcal{F} hữu hạn thì \displaystyle \mathcal{R}_n(\mathcal{F})=O\left(\sqrt{\frac{\log n}{n}}\right) \rightarrow 0 khi \displaystyle n\rightarrow\infty.

Chứng minh: Thật vậy, nếu chiều VC của lớp hàm \displaystyle \mathcal{F} hữu hạn và bằng \displaystyle d thì ta đã biết \displaystyle G_{\mathcal{F}}(n)=O(n^d) hay \displaystyle \log G_{\mathcal{F}}(n)=O(\log n).

Nhận xét: Kết quả này chứng tỏ

  1. Nguyên tắc tối thiểu hóa rủi ro thực nghiệm khả thi vì \displaystyle R(\widehat{f})\rightarrow R(f^*) với xác suất cao khi số mẫu học \displaystyle n\rightarrow\infty do ta đã biết ở bài trước

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

    nghĩa là rủi ro kì vọng của \displaystyle \widehat{f} xấp xỉ rủi ro kì vọng thấp nhất có thể được với xác suất cao.

  2. Ước lượng \displaystyle \mathcal{R}_n(\mathcal{F}) bị giới hạn bởi hàm tăng trưởng \displaystyle G_{\mathcal{F}}(n). Hàm tăng trưởng lại bị giới hạn bởi chiều VC. Vì vậy, chiều VC là một thuộc tính quan trọng cần xét đến khi học trên lớp hàm \displaystyle \mathcal{F}. Ước lượng cận trên của chiều VC của một lớp hàm hoặc chỉ ra nó vô hạn sẽ giúp ta xác định có nên áp dụng nguyên tắc tối thiểu hóa rủi ro thực nghiệm hoặc phải cẩn trọng khi áp dụng nguyên tắc này hay không.
  3. Tại sao phải cẩn trọng khi áp dụng nguyên tắc tối thiểu hóa rủi ro thực nghiệm (ERM) khi chiều VC vô hạn hoặc rất lớn ? Bởi vì khi một lớp hàm \displaystyle \mathcal{F} có chiều VC vô hạn (hoặc rất lớn)  có nghĩa là với mọi tập mẫu học (và mọi cách phân chia nó), luôn có một hàm phân lớp \displaystyle \widehat{f} thuộc \displaystyle \mathcal{F}  thỏa mãn cách phân chia này. Nếu ta áp dụng ERM, ta sẽ tìm ra hàm \displaystyle \widehat{f} chứ không phải hàm \displaystyle f^* mà ta muốn (mặc dù rủi ro thực nghiệm (số lỗi) trên tập mẫu học bằng 0). Đây chính là hiện tượng học quá (overfitting) khi sử dụng các lớp hàm có khả năng biểu diễn mạnh (ví dụ: mạng nơron – neural network).

This entry was posted on Tháng Bảy 7, 2009 lúc 10:13 chiều and is filed under Học thống kê, Lý thuyết học máy. Thẻ: , , , , , , , , , , , , , , . You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.

Bình luận về bài viết này

«
»