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

Learn & Enjoy …

Chiều VC (VC dimension) (4) – Một số lớp hàm đơn giản

Đăng bởi tqlong on Tháng Bảy 9, 2009

Ta tìm hiểu chiều VC của một số lớp hàm đơn giản trong bài này. Theo định nghĩa, chiều VC của một lớp khái niệm là số phần tử lớn nhất của một tập có thể bị phá vỡ (shatter) bởi lớp khái niệm này.

\displaystyle \mathrm{VCD}(\mathcal{C}) = \max \{|S|: \Pi_{\mathcal{C}}(S)=2^S\}

Để chỉ ra chiều VC của một lớp khái niệm bằng \displaystyle d ta phải chứng minh:

  1. \displaystyle \mathrm{VCD}(\mathcal{C})\geq d: bằng cách chỉ ra một tập có số phần tử bằng \displaystyle d bị phá vỡ bởi \displaystyle \mathcal{C}.
  2. \displaystyle \mathrm{VCD}(\mathcal{C})< d+1: bằng cách chỉ ra với mọi tập có số phần tử  nhiều hơn \displaystyle d thì \displaystyle \mathcal{C} không thể phá vỡ được (thường khó hơn mệnh đề trên).

Trong một số trường hợp, ta chỉ xác định được mệnh đề 1 hoặc mệnh đề 2.

Ví dụ 1: Lớp các khoảng đóng trên trục số \displaystyle \mathbb{R}

Lớp khái niệm đoạn đóng

Xét lớp khái niệm \displaystyle \mathcal{C}=\{[a,b]:a\leq b\}. Đối với lớp khái niệm này, phá vỡ có nghĩa là gì ? Một tập hợp điểm \displaystyle \{x_1,\ldots, x_n\} bị phá vỡ bởi lớp các khoảng đóng nếu với mọi cách đánh dấu tập điểm này bằng các dấu \displaystyle +,-, ta đều có thể tìm được một khoảng đóng chỉ chứa các điểm được đánh dấu \displaystyle +.

Ta sẽ chứng minh \displaystyle \mathrm{VCD}(\mathcal{C})=2. Thật vậy, đầu tiên dễ thấy rằng mọi tập 2 điểm \displaystyle \{x,y\} trên trục số đều có thể bị phá vỡ bởi \displaystyle \mathcal{C} (với cả 4 cách đánh dấu \displaystyle +,- cho \displaystyle x,y ta đều có thể vẽ một khoảng đóng chỉ chứa các điểm có dấu \displaystyle +).  Do đó \displaystyle \mathrm{VCD}(\mathcal{C})\geq 2.

Tuy nhiên, với mọi tập 3 điểm (phân biệt) \displaystyle x<y<z, nếu ta đánh dấu \displaystyle x,z thuộc lớp \displaystyle +1, còn \displaystyle ylà \displaystyle -1 thì không thể có khoảng đóng nào chứa \displaystyle x,z mà không chứa \displaystyle y. Do đó \displaystyle \mathcal{C} không thể phá vỡ tập 3 điểm bất kì (do không có khái niệm nào chứa \displaystyle x,z mà không chứa \displaystyle y). Vậy \displaystyle \mathrm{VCD}(\mathcal{C})< 3 hay \displaystyle \mathrm{VCD}(\mathcal{C})= 2.

Ví dụ 2: Lớp các hình chữ nhật có cạnh song song với 2 trục của mặt phẳng

Lớp khái niệm hình chữ nhật

Xét lớp khái niệm \displaystyle \mathcal{C}=\{[a,b]\times[c,d]\subset \mathbb{R}^2:a\leq b,c\leq d\}. Một tập bị phá vỡ bởi \displaystyle \mathcal{C} nghĩa là với mọi cách đánh dấu \displaystyle +,- các điểm của tập này ta đều có một hình chữ nhật chỉ chứa các điểm được đánh dấu \displaystyle +.

Ta sẽ chứng minh \displaystyle \mathrm{VCD}(\mathcal{C})=4. Thật vậy, đầu tiên ta cần chỉ ra một tập có 4 điểm thuộc \displaystyle \mathbb{R}^2 bị phá vỡ bởi \displaystyle C. Xét tập 4 điểm gồm 4 đỉnh của một hình thoi có các trục song song với hai trục X, Y. Rõ ràng với mọi cách đánh dấu \displaystyle +,- ta đều có thể vẽ 1 hình chữ nhật chỉ chứa các dấu \displaystyle +. Suy ra \displaystyle \mathrm{VCD}(\mathcal{C})\geq 4.

Khả năng phá vỡ của lớp các hình chữ nhật

Xét một tập 5 điểm (phân biệt) bất kì trên mặt phẳng. Như vậy tồn tại một điểm không phải là điểm trái nhất hoặc phải nhất hoặc cao nhất hoặc thấp nhất. Đánh dấu điểm này bằng dấu \displaystyle - còn 4 điểm còn lại bằng dấu \displaystyle + (như hình trên). Hình chữ nhật bao được 4 dấu  \displaystyle + bắt buộc phải chứa cả dấu \displaystyle -. Do đó tập 5 điểm không thể bị phá vỡ. Suy ra \displaystyle \mathrm{VCD}(\mathcal{C})< 5 hay \displaystyle \mathrm{VCD}(\mathcal{C})= 4.

Ví dụ 3: Lớp các nửa không gian (phân cách bằng siêu phẳng):

half-space-concept

Xét lớp khái niệm \displaystyle \mathcal{C}= \{ H_{w,b},\forall w\in \mathbb{R}^d,b\in \mathbb{R}\} là tập tất cả các nửa không gian

\displaystyle H_{w,b} = \{x\in \mathbb{R}^d: \langle w,x\rangle-b \geq 0\}

xác định bởi véctơ pháp tuyến (normal) \displaystyle w và ngưỡng (threshold) \displaystyle b. Đây là một lớp khái niệm rất quan trọng vì rất nhiều hàm phân lớp là hàm phân lớp tuyến tính (perceptron, SVM, RBF).

Ta sẽ chứng minh \displaystyle \mathrm{VCD}(\mathcal{C})=d+1 với \displaystyle d là số chiều của không gian.

Để chứng minh \displaystyle \mathrm{VCD}(\mathcal{C})\geq d+1 ta cần chỉ ra một tập có \displaystyle d+1 phần tử bị phá vỡ bởi \displaystyle \mathcal{C}. Xét tập điểm sau \displaystyle 0, e_1, \ldots, e_d với \displaystyle 0 là gốc tọa độ, \displaystyle e_1,\ldots, e_d là các véc tơ cơ sở trực chuẩn ta vẫn thường sử dụng \displaystyle e_i = (0,\ldots,0,1,0,\ldots,0). Bây giờ ta xét một cách đánh dấu bất kì các điểm này. Do tính đối xứng của nửa không gian, không mất tính tổng quát giả sử các điểm được đánh dấu \displaystyle + có điểm \displaystyle 0 và các véctơ được đánh dấu \displaystyle + là \displaystyle 0, e_1,\ldots, e_k với \displaystyle k\leq d. Nếu nửa không gian \displaystyle H_{w,b} chỉ chứa các điểm có dấu \displaystyle + thì

\displaystyle \langle w,0\rangle -b\geq 0 \Rightarrow b \leq 0

\displaystyle \langle w,e_i\rangle -b\geq 0,\forall i\leq k \Rightarrow w_i \geq b,\forall i\leq k

\displaystyle \langle w,e_i\rangle -b< 0,\forall i> k \Rightarrow w_i < b,\forall i> k

Có rất nhiều cách để chọn \displaystyle w,b như trên. Ví dụ \displaystyle b = -1, w_i = \begin{cases}0 & i\leq k\\ -2 & i>k\end{cases}. Vậy tập điểm trên bị phá vỡ bởi \displaystyle \mathcal{C}.

Để chứng minh \displaystyle \mathrm{VCD}(\mathcal{C})<d+2, ta sử dụng định lý Radon. Theo đó, một tập điểm bất kì gồm \displaystyle d+2 điểm phân biệt có thể tách thành 2 tập con có bao lồi giao nhau. Đánh dấu một tập con bằng dấu \displaystyle + và tập còn lại bằng dấu \displaystyle -. Giả sử có một nửa không gian \displaystyle H nào đó chứa và chỉ chứa tất cả các điểm có dấu \displaystyle +. Suy ra \displaystyle H  chứa bao lồi các điểm này (do \displaystyle H là tập lồi), còn \displaystyle \mathbb{R}^d\setminus H chứa bao lồi của các điểm có dấu \displaystyle -. Suy ra bao lồi của hai tập điểm này không giao nhau, mâu thuẫn với định lý Radon.

Đăng trong Lý thuyết học máy | Tagged: , , , , , , , , , | Leave a Comment »

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

Đăng bởi tqlong on 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).

Đăng trong Học thống kê, Lý thuyết học máy | Tagged: , , , , , , , , , , , , , , | Leave a Comment »

« Những bài viết trước