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 « CS Study Fun

Tháng Sáu 2009
T2	T3	T4	T5	T6	T7	CN
« Tháng 1		Tháng 7 »
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

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

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

$\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)$ là

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

trong đó $\displaystyle L(y',y)$ là 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 mũ (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

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.
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)$ là 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.

Bài viết này được đăng vào Tháng Sáu 25, 2009 lúc 8:00 sáng và tập tin được lưu ở Học thống kê, Lý thuyết học máy. Tagged: almost surely, confidence, empirical risk, empirical risk minimization, ERM, expected risk, gần như chắc chắn, rủi ro kì vọng, rủi ro thực nghiệm, tối thiểu rủi ro thực nghiệm, đảm bảo xác suất. Bạn có thể theo dõi các phản hồi của bài viết này thông qua RSS 2.0 dòng thông tin. Bạn có thể bỏ qua phần còn lại và gửi phản hồi. Ping đã bị khóa.

Để lại hồi âm

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

Nguyên tắc tối thiểu hóa rủi ro thực nghiệm (2) – Tập mẫu học giản lược »

	Khuyen Nguyen trong bài Phân lớp bằng siêu phẳng (1) …
	tqlong trong bài Phân lớp bằng siêu phẳng (1) …
	Khuyen Nguyen trong bài Phân lớp bằng siêu phẳng (1) …
	tqlong trong bài Bất đẳng thức xác suất (1) …
	H.T.D. trong bài Bất đẳng thức xác suất (1) …

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

Learn & Enjoy …

Phân loại

Lưu trữ

Thống kê

Bài gần đây

Lời bình gần đây

Trang

Blogroll

Quản trị

Lịch

Theo dõi

Blog D.Q. Huy

Các phương pháp điểm trong

Xem nhiều nhất

Từ khóa

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

Để lại hồi âm