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

Learn & Enjoy …

Posts Tagged ‘compression set’

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

Posted by Trần Quốc Long trên 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.

Posted in Học thống kê, Lý thuyết học máy | Thẻ: , , , , , , | Leave a Comment »