Chiều VC (VC dimension) (3) – Hàm tăng trưởng (growth function) « CS Study Fun

Tháng Bảy 2009
T2	T3	T4	T5	T6	T7	CN
« Tháng 6
	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	31

Chiều VC (VC dimension) (3) – Hàm tăng trưởng (growth function)

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

Định nghĩa: Đặt $\displaystyle G_{\mathcal{C}}(m) = \max \{|\Pi_{\mathcal{C}}(S)| : |S|=m\}, m = 1,2,\ldots$ , tức là $\displaystyle G_{\mathcal{C}}(m)$ bằng số cách lớn nhất có thể có để lớp khái niệm $\displaystyle \mathcal{C}$ phân chia tập $\displaystyle S$ bất kì có $\displaystyle m$ phần tử. Ta gọi $\displaystyle G_{\mathcal{C}}(m)$ là hàm tăng trưởng (growth function) của lớp khái niệm $\displaystyle \mathcal{C}$ .

Dễ thấy rằng, do $\displaystyle \Pi_{\mathcal{C}}(S)\subset 2^S$ , ta có $\displaystyle G_{\mathcal{C}}(m)\leq 2^m$ với mọi lớp khái niệm $\displaystyle \mathcal{C}$ . Đặc biệt $\displaystyle G_{\mathcal{C}}(m)= 2^m$ khi và chỉ khi lớp khái niệm $\displaystyle \mathcal{C}$ phá vỡ một tập $\displaystyle S$ có $\displaystyle m$ phần tử nào đó. Tuy nhiên, giáo sư Vapnik chỉ ra rằng, nếu chiều VC của $\displaystyle \mathcal{C}$ hữu hạn, $\displaystyle \mathrm{VCD}(\mathcal{C})=d$ , hàm tăng trưởng $\displaystyle G_{\mathcal{C}}(m)$ sẽ bị chặn trên bởi một đa thức bậc $\displaystyle d$ của $\displaystyle m$ .

Xét hàm $\displaystyle \Phi_d(m)$ định nghĩa như sau:

$\displaystyle \Phi_d(0)=\Phi_0(m)=1,\forall d,m=1,2,\ldots$ .
$\displaystyle \Phi_d(m)=\Phi_d(m-1)+\Phi_{d-1}(m-1)$ .

Bổ đề: Nếu $\displaystyle \mathrm{VCD}(\mathcal{C})=d$ thì $\displaystyle G_{\mathcal{C}}(m)\leq \Phi_d(m)$ .

Chứng minh: Bằng quy nạp. Trường hợp $\displaystyle d=0$ , $\displaystyle \mathcal{C}$ không thể phá vỡ tập nào, suy ra $\displaystyle G_{\mathcal{C}}(m) = 0\leq 1 = \Phi_0(m),\forall m$ . Trường hợp $\displaystyle m=0$ , rõ ràng $\displaystyle \Pi_{\mathcal{C}}(0) = 0\leq 1 = \Phi_d(0),\forall d$ .

Giả sử bổ đề đúng với mọi cặp $\displaystyle m',d'$ sao cho $\displaystyle m'\leq m, d'\leq d$ và hai đẳng thức không xảy ra đồng thời (tức là hoặc $\displaystyle m'<m$ hoặc $\displaystyle d'<d$ ), ta sẽ chứng minh bổ đề cũng đúng với cặp $\displaystyle m, d$ .

Thật vậy, xét tập $\displaystyle S$ bất kì có $\displaystyle m$ phần tử. Chọn một phần tử $\displaystyle x\in S$ . Ta có

$\displaystyle c\cap S =c\cap(S\setminus \{x\}) \cup (c\cap\{x\})$

Do đó, nếu $\displaystyle x\notin c$ thì $\displaystyle c\cap S = c\cap(S\setminus \{x\}) = (c\cup \{x\}) \cap(S\setminus \{x\})$ . Suy ra

$\displaystyle |\Pi_{\mathcal{C}}(S)| = |\Pi_{\mathcal{C}}(S\setminus \{x\})| + |\mathcal{C}'|$ với $\displaystyle \mathcal{C}'=\{c\in \Pi_{\mathcal{C}}(S): x\notin c, c \cup \{x\}\in \Pi_{\mathcal{C}}(S)\}$

Để ý là $\displaystyle \mathcal{C}'=\Pi_{\mathcal{C}'}(S\setminus \{x\})$ vì các khái niệm trong $\displaystyle \mathcal{C'}$ đều nằm trong $\displaystyle S\setminus \{x\}$ . Hơn nữa, ta còn có $\displaystyle \mathrm{VCD}(\mathcal{C}')\leq d-1$ . Thật vậy, nếu tập $\displaystyle S'\subset S\setminus \{x\}$ bị phá vỡ bởi $\displaystyle \mathcal{C}'$ thì $\displaystyle S'\cup \{x\}$ bị phá vỡ bởi $\displaystyle \mathcal{C}$ , suy ra $|S'\cup \{x\}| \leq d$ hay $\displaystyle |S'|\leq d-1$ .

Vậy ta có

$\displaystyle |\Pi_{\mathcal{C}}(S)| = |\Pi_{\mathcal{C}}(S\setminus \{x\})| + |\mathcal{C}'| = \Pi_{\mathcal{C}}(S\setminus \{x\})| + |\Pi_{\mathcal{C}'}(S\setminus \{x\})|$

$\displaystyle \leq \Pi_{\mathcal{C}}(m-1)+\Pi_{\mathcal{C}'}(m-1)\leq \Phi_d(m-1)+\Phi_{d-1}(m-1)=\Phi_d(m)$

Bổ đề: $\displaystyle \Phi_d(m)=\sum_{i=0}^d C_{i}^m$ ,

trong đó $\displaystyle C_i^m$ là số tổ hợp chập $\displaystyle i$ của $\displaystyle m$ phần tử.

$\displaystyle C_i^m = \begin{cases} \frac{m!}{i!(m-i)!} & 0\leq i\leq m \\ {0} & i<0, i > m\end{cases}$

Chứng minh: Bằng quy nạp và hằng đẳng thức $\displaystyle C_i^m = C_i^{m-1}+C_{i-1}^{m-1}$ .

Từ bổ đề trên ta có:

Nếu $\displaystyle m\leq d$ , $\displaystyle \Phi_d(m) = 2^m$ .
Nếu $\displaystyle m > d$ , ta có $\displaystyle d/m < 1$
$\displaystyle \Phi_d(m) = \left(\frac{m}{d}\right)^d\sum_{i=0}^d (d/m)^dC_i^m$
$\displaystyle \leq (m/d)^d \sum_{i=0}^d (d/m)^i C_i^m\leq (m/d)^d\sum_{i=0}^m (d/m)^i C_i^m$
$\displaystyle =(m/d)^d (1+d/m)^m\leq (m/d)^d e^d=\left(\frac{em}{d}\right)^d$

Nghĩa là $\displaystyle G_{\mathcal{C}}(m)\leq\Phi_d(m)= O(m^d)$ .

Bài viết này được đăng vào Tháng Bảy 5, 2009 lúc 8:00 sáng và tập tin được lưu ở Lý thuyết học máy. Tagged: chiều VC, growth function, hàm tăng trưởng, khái niệm, lớp khái niệm, phá vỡ, shatter, VC dimension. 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

« Chiều VC (VC dimension) (2) – Phá vỡ một tập hợp (shatter)

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 »

	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

Chiều VC (VC dimension) (3) – Hàm tăng trưởng (growth function)

Để lại hồi âm