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 (1) – Rủi ro thực nghiệm và rủi ro kì vọng

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

Nguyên tắc tối thiểu hóa rủi ro thực nghiệm được giới thiệu trong bài trước. Trong bài này ta sẽ xem xét kĩ hơn tính khả thi của nguyên tắc này. Nhắc lại, ta có giá trị rủi ro kì vọng (expected risk) của hàm phân lớp \displaystyle f:\mathbb{X}\Rightarrow \mathbb{Y}

\displaystyle R(f) = \int_{\mathbb{X}} L(f(x),y) p(x,y)dxdy = E[L(f(X),Y)]

còn giá trị rủi ro thực nghiệm (empirical risk) trên tập mẫu học \displaystyle (x_1,y_1),\ldots, (x_n,y_n)

\displaystyle \widehat{R}_n(f) = \frac{1}{n}\sum_{i=1}^n L(f(x_i), y_i)

trong đó \displaystyle L(y',y)hàm lỗi khi phân đối tượng thuộc lớp \displaystyle y vào lớp \displaystyle y'. Có nhiều dạng hàm lỗi, ví dụ:

Với \displaystyle \mathbb{Y}=\{+1,-1\} (bài toán phân 2 lớp – classification)

  • Hàm lỗi 0-1 (0-1 loss): \displaystyle L(y',y) = I\{y=y'\} = \begin{cases}1& y= y'\\ 0& y\neq y'\end{cases}.
  • Hàm lỗi bản lề (hinge loss): \displaystyle L(y',y) = \max\{0,1-yy'\}.
  • Hàm lỗi (exponiental loss): \displaystyle L(y',y) = e^{-yy'}.
  • Hàm lỗi logitic (logistic loss): \displaystyle L(y',y) = \ln(1+e^{-yy'}).

Với \displaystyle \mathbb{Y}=\mathbb{R} (bài toán xấp xỉ – regression)

  • Hàm lỗi \displaystyle \ell_2 sai số bình phương: \displaystyle L(y',y) = (y-y')^2.
  • Hàm lỗi  \displaystyle \ell_1 sai số tuyệt đối: \displaystyle L(y',y) = |y-y'|.

Một thuật toán học máy tuân theo nguyên tắc tối thiểu hóa rủi ro thực nghiệm từ đầu vào là tập mẫu học \displaystyle (x_1,y_1),\ldots, (x_n,y_n) (giả sử độc lập có cùng phân bố – i.i.d), sau khi tính toán cho ra một hàm phần lớp \displaystyle \widehat{f}^* nằm trong lớp hàm \displaystyle \mathcal{F} cho trước sao cho giá trị rủi ro thực nghiệm được tối thiểu hóa. Xét các giá trị sau:

\displaystyle\widehat{f}=\arg\min_{f\in \mathcal{F}}\widehat{R}(f), \widehat{R}^* = \min_{f\in \mathcal{F}} \widehat{R}(f)

\displaystyle f^* = \arg\min_{f\in \mathcal{F}} R(f), R^* = \min_{f\in \mathcal{F}} R(f)

Như vậy, \displaystyle \widehat{f} là kết quả của thuật toán học máy, hàm này tối thiểu hóa giá trị rủi ro thực nghiệm \displaystyle \widehat{R}(f). Còn \displaystyle f^* là hàm phân lớp tốt nhất có thể trong lớp hàm \displaystyle \mathcal{F}, hàm này tối thiểu hóa giá trị rủi ro kì vọng \displaystyle R(f).

Ta cần xác định

  1. Chênh lệch giữa rủi ro thực nghiệm và rủi ro kì vọng của \displaystyle \widehat{f}:

    \displaystyle |\widehat{R}(\widehat{f})-R(\widehat{f})|=|\widehat{R}^*-R(\widehat{f})|

    Đánh giá đại lượng này được  tiến hành qua các bất đẳng thức tập trung phân bố quanh kì vọng.

  2. Chênh lệch giữa rủi ro kì vọng của \displaystyle \widehat{f}  và rủi ro kì vọng tốt nhất có thể được:

    \displaystyle R(\widehat{f})-R(f^*)=R(\widehat{f})-R^*

Định lý sau cho ta biết mối quan hệ giữa hai đại lượng này:

Định lý: Nếu với mọi hàm phân lớp \displaystyle f\in \mathcal{F} ta có

\displaystyle |\widehat{R}(f)-R(f)|\leq \epsilon hay \displaystyle \sup_{f\in \mathcal{F}}|\widehat{R}(f)-R(f)|\leq \epsilon

thì \displaystyle R(\widehat{f})-R^* \leq 2\epsilon.

Chứng minh:

\displaystyle R(\widehat{f})-R^* = R(\widehat{f})-R(f^*)

\displaystyle \leq R(\widehat{f})-\widehat{R}(f^*)+\epsilon do \displaystyle R(f^*)\geq \widehat{R}(f^*)-\epsilon

\displaystyle \leq R(\widehat{f})-\widehat{R}(\widehat{f})+\epsilon do \displaystyle \widehat{R}(\widehat{f})\leq \widehat{R}(f^*)

\displaystyle \leq 2\epsilon do \displaystyle R(\widehat{f})-\widehat{R}(\widehat{f})\leq\epsilon

Định lý cho phép ta ước lượng \displaystyle R(\widehat{f})-R^* nếu ta ước lượng được \displaystyle \sup_{f\in \mathcal{F}} |\widehat{R}(f)-R(f)|.

Ví dụ: Trường hợp \displaystyle \mathcal{F} hữu hạn, \displaystyle |\mathcal{F}|<\infty, ta có:

\displaystyle \mathrm{Pr}\{\sup_{f\in \mathcal{F}}|\widehat{R}(f)-R(f)|\geq\epsilon\}=\mathrm{Pr}\{\exists f\in \mathcal{F}: | \widehat{R}(f)-R(f)| \geq\epsilon\}

\displaystyle\leq \sum_{f\in \mathcal{F}} \mathrm{Pr}\{|\widehat{R}(f)-R(f)|\geq\epsilon\} (bất đẳng thức tổng xác suất)

Giả sử hàm \displaystyle L(y',y)hàm lỗi 0-1, áp dụng bất đẳng thức Hoeffding ta được

\displaystyle\mathrm{Pr}\{|\widehat{R}(f)-R(f)|\geq\epsilon\}\leq 2e^{-2n\epsilon^2}

Vậy tiếp tục ta có

\displaystyle \mathrm{Pr}\{\sup_{f\in \mathcal{F}}|\widehat{R}(f)-R(f)|\geq\epsilon\} \leq 2|\mathcal{F}|e^{-2n\epsilon^2}

Đặt \displaystyle \delta = 2|\mathcal{F}|e^{-2n\epsilon^2} hay \displaystyle \epsilon = \sqrt{\frac{\ln 2|\mathcal{F}|+\ln \frac{1}{\delta}}{2n}}, ta suy ra

\displaystyle \mathrm{Pr}\left\{\sup_{f\in \mathcal{F}}|\widehat{R}(f)-R(f)|\leq\sqrt{\frac{\ln 2|\mathcal{F}|+\ln \frac{1}{\delta}}{2n}}\right\}\geq 1-\delta

Từ định lý trên ta kết luận

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

trong đó \displaystyle 1-\delta gọi là đảm bảo xác suất (confidence). Ta còn nói, gần như chắc chắn \displaystyle R(\widehat{f})\rightarrow R^* khi \displaystyle n\rightarrow\infty  (asymptotically almost surely).

Như vậy, nếu số mẫu học càng lớn thì giá trị rủi ro kì vọng của \displaystyle \widehat{f} càng gần giá trị rủi ro thấp nhất có thể được (theo nghĩa xác suất). Nghĩa là trong trường hợp này, tối thiểu hóa rủi ro thực nghiệm hay ERM đem lại hàm phân lớp tốt (gần tối ưu) với xác suất cao. Công thức trên còn cho thấy, để tăng đảm bảo xác suất từ \displaystyle 90\% hay \displaystyle \delta=10\% lên \displaystyle 99\% hay \displaystyle \delta=1\%, ta chỉ cần tăng số mẫu học \displaystyle n lên 2 lần.

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: