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

Learn & Enjoy …

Archive for Tháng Bảy 9th, 2009

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 »