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

Archive for Tháng Sáu, 2009

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

Đăng bởi tqlong 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\}$ là biến ngẫu nghiên Rademacher nếu $\displaystyle \mathrm{Pr}\{\epsilon=+1\}=\mathrm{Pr}\{\epsilon=-1\}=1/2$ và $\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)]$ và $\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 Rademacher là thuộ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)$ và $\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óa – symmetrization).

$\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)$ và $\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^ *)$ và $\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}$ và $\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.

Đăng trong Học thống kê, Lý thuyết học máy | Tagged: empirical distribution function, ghost sample, rademacher, tập mẫu giả, tối thiểu rủi ro thực nghiệm | Leave a Comment »

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

Đăng bởi tqlong on Tháng Sáu 27, 2009

Trong một số trường hợp, thuật toán học máy không cần xem xét toàn bộ tập mẫu học mà vẫn cho ra kết quả hàm phân lớp giống như khi thuật toán chạy trên toàn bộ tập mẫu học. Ví dụ, trong trường hợp perceptron, các mẫu học được sử dụng là các mẫu học bị phân lớp sai trong quá trình học. Trong trường hợp máy học sử dụng véc tơ hỗ trợ (SVM), các mẫu học cần thiết là các véctơ hỗ trợ. Trong bài này, ta sẽ đánh giá độ chính xác của các thuật toán học như vậy.

Để cho tiện, xét tập mẫu học $\displaystyle D =\{ (x_1,y_1),\ldots,(x_n,y_n)\}$ gồm $\displaystyle n$ mẫu học. Đặt $\displaystyle [n] = \{1,\ldots,n\}$ là tập tất cả các chỉ số. Nếu $\displaystyle I\subset [n]$ là một tập chỉ số nào đó, $\displaystyle I = \{i_1,\ldots,i_{n_I}\}$ , thì $\displaystyle D_I$ là các mẫu học $\displaystyle D_I = \{(x_{i_1}, y_{i_1}),\ldots,(x_{i_{n_I}}, y_{i_{n_I}})\}$ . Kí hiệu $\displaystyle -I = [n]\setminus I$ là tập các chỉ số không nằm trong $\displaystyle I$ .

Một thuật toán học $\displaystyle \mathcal{A}$ là một hàm từ tập mẫu học của nó đến một hàm phân lớp thuộc lớp hàm $\displaystyle \mathcal{F}$ , hay $\displaystyle \mathcal{A}(D)\in \mathcal{F}$ .

Định nghĩa (tập mẫu học giản lược): Xét $\displaystyle I\subset [n]$ , ta nói $\displaystyle D_I$ là tập mẫu học giản lược (compression set) của $\displaystyle D$ nếu

$\displaystyle \mathcal{A}(D_I) = \mathcal{A}(D)$

Gọi

$\displaystyle R(\mathcal{A}(D))$ là rủi ro kì vọng của thuật toán $\displaystyle \mathcal{A}$ sau khi học trên tập mẫu học $\displaystyle D$ .
$\displaystyle R(\mathcal{A}(D_I))$ là rủi ro kì vọng của thuật toán $\displaystyle \mathcal{A}$ sau khi học trên tập mẫu học $\displaystyle D_I$ (nếu $\displaystyle D_I$ giản lược thì $\displaystyle R(\mathcal{A}(D)) = R(\mathcal{A}(D_I))$ ).
$\displaystyle \widehat{R}_I(f) = \frac{1}{n_I}\sum_{i\in I} L(f(x_i), y_i)$ là rủi ro thực nghiệm của hàm $\displaystyle f$ trên tập mẫu học $\displaystyle D_I$ .

Ta thấy trong trường hợp Perceptron và SVM, nếu $\displaystyle D_I$ là tập mẫu học giản lược thì $\displaystyle \widehat{R}_{-I}(\mathcal{A}(D_I)) = 0$ (số lỗi trên tập các mẫu học còn lại bằng 0). Trường hợp Perceptron, $\displaystyle -I$ là tập các mẫu học được phân lớp đúng. Trường hợp SVM, $\displaystyle -I$ là tập các mẫu học không phải là véctơ hỗ trợ. Ta có định lý sau ước lượng xác suất lỗi cho các trường hợp này.

Định lý (ước lượng xác suất cho tập mẫu học giản lược – compression bound): Xét trường hợp hàm lỗi bị chặn trong khoảng $\displaystyle [0,1]$ và thuật toán học máy $\displaystyle \mathcal{A}$ trên tập mẫu học $\displaystyle D$ . Với mọi tập mẫu học giản lược $\displaystyle D_I$ mà $\displaystyle \widehat{R}_{-I}(\mathcal{A}(D_I)) = 0$ ta có

$\displaystyle \mathrm{Pr}\left\{R(\mathcal{A}(D)) \leq \frac{1}{n-n_I}\left((n_I+1)\log n + \log \frac{1}{\delta}\right)\right\}\geq 1-\delta$

Định lý cho thấy nếu tập mẫu học có tập giản lược nhỏ thì rủi ro kì vọng càng nhỏ (theo nghĩa xác suất).

Chứng minh: Ta cần đánh giá xác suất để tồn tại một tập mẫu học $\displaystyle D_I$ là tập giản lược, đồng thời $\displaystyle \widehat{R}_{-I}(\mathcal{A}(D_I)) = 0$ nhưng rủi ro kì vọng $\displaystyle R(\mathcal{A}(D_I))\geq\epsilon$ . Tức là

$\displaystyle \mathrm{Pr}\left\{\exists I: D_I \textrm{ is a compression set } \wedge \widehat{R}_{-I}(\mathcal{A}(D_I)) = 0 \wedge R(\mathcal{A}(D_I))\geq\epsilon\right\}$

Quá trình ước lượng như sau: đầu tiên ta ước lượng xác suất với một tập giản lược cụ thể $\displaystyle I$ có kích cỡ $\displaystyle n_I$ . Sau đó dùng ước lượng xác suất tổng để ước lượng xác suất của một tập giản lược bất kì có kích cỡ $\displaystyle n_I$ . Sau đó tiếp tục dùng ước lượng xác suất tổng để ước lượng xác suất của một tập giản lược bất kì (có kích cỡ bất kì từ $\displaystyle 1$ đến $\displaystyle n$ ).

Bắt đầu, xét một tập $\displaystyle I$ có kích thước $\displaystyle n_I$ . Ta có

$\displaystyle \mathrm{Pr}\left\{|I| = n_I\wedge D_I \textrm{ is a compression set } \wedge \widehat{R}_{-I}(\mathcal{A}(D_I)) = 0 \wedge R(\mathcal{A}(D_I))\geq\epsilon\right\}\leq \mathrm{Pr}\left\{|I| = n_I\wedge \widehat{R}_{-I}(\mathcal{A}(D_I)) = 0 \wedge R(\mathcal{A}(D_I))\geq\epsilon\right\}\leq (1-\epsilon)^{n-n_I}$

vì $\displaystyle \widehat{R}_{-I}(\mathcal{A}(D_I))=0$ nghĩa là $\displaystyle L(f_I(x_i), y_i)=0,\forall i\in -I$ (có $\displaystyle n-n_I$ phần tử) và bổ đề sau.

Bổ đề: Biến ngẫu nhiên $\displaystyle X\in [0,1]$ có $\displaystyle E[X]\geq\epsilon$ thì $\displaystyle \mathrm{Pr}\left\{X=0\right\}\leq 1-\epsilon$ hay $\displaystyle \mathrm{Pr}\left\{X>0\right\}\geq \epsilon$ .

Chứng minh bổ đề: $\displaystyle \epsilon\leq E[X]=\mathrm{Pr}\left\{X>0\right\}E[X|X>0]\leq \mathrm{Pr}\left\{X>0\right\}$ .

Áp dụng bổ đề, ta có $\displaystyle E[L(f_I(x_i), y_i)]=R(\mathcal{A}(D_I))\geq\epsilon$ , suy ra $\displaystyle \mathrm{Pr}\left\{L(f_I(x_i), y_i)=0\right\}\leq 1-\epsilon$ và có tất cả $\displaystyle n-n_I$ mẫu học như vậy.

Tiếp tục, dùng ước lượng xác suất tổng, ta có

$\displaystyle \mathrm{Pr}\left\{\exists I: |I| = n_I\wedge D_I \textrm{ is a compression set } \wedge \widehat{R}_{-I}(\mathcal{A}(D_I)) = 0 \wedge R(\mathcal{A}(D_I))\geq\epsilon\right\}$

$\displaystyle \leq \sum_{I\subset [n],|I|=n_I}\mathrm{Pr}\left\{|I| = n_I\wedge D_I \textrm{ is a compression set } \wedge \widehat{R}_{-I}(\mathcal{A}(D_I)) = 0 \wedge R(\mathcal{A}(D_I))\geq\epsilon\right\}$

$\displaystyle \leq \sum_{I\subset [n],|I|=n_I} (1-\epsilon)^{n-n_I}$

$\displaystyle \leq n^{n_I}(1-\epsilon)^{n-n_I}$

$\displaystyle \leq n^{n_I}e^{-(n-n_I)\epsilon}=\delta(n_I)$ do $\displaystyle 1-\epsilon\leq e^{-\epsilon}$ (khai triển Taylor của $\displaystyle e^x$ ).

Nếu chọn $\displaystyle \delta(n_I) = \delta/n$ thì $\displaystyle \epsilon = \frac{1}{n-n_I}\left((n_I+1)\log n + \log \frac{1}{\delta}\right)$ .

Tiếp tục áp dụng ước lượng xác suất tổng

$\displaystyle \mathrm{Pr}\left\{\exists I: D_I \textrm{ is a compression set } \wedge \widehat{R}_{-I}(\mathcal{A}(D_I)) = 0 \wedge R(\mathcal{A}(D_I))\geq\epsilon\right\}$

$\displaystyle \leq \sum_{n_I=1}^n \mathrm{Pr}\left\{\exists I: |I| = n_I\wedge D_I \textrm{ is a compression set } \wedge \widehat{R}_{-I}(\mathcal{A}(D_I)) = 0 \wedge R(\mathcal{A}(D_I))\geq\epsilon\right\}$

$\displaystyle \leq \sum_{n_I=1}^n\delta/n =\delta$ .

Ta có điều phải chứng minh.

Đăng trong Học thống kê, Lý thuyết học máy | Tagged: compression set, empirical risk minimization, máy phân lớp sử dụng véctơ hỗ trợ, perceptron, SVM, tập mẫu học giản lược, tối thiểu rủi ro thực nghiệm | Leave a Comment »

« Những bài viết trướ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

Archive for Tháng Sáu, 2009

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

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