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

Learn & Enjoy …

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

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

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

 
%d bloggers like this: