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

Learn & Enjoy …

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

Posted by Trần Quốc Long on Tháng Bảy 3, 2009

Một khái niệm quan trọng trong lý thuyết VC là khái niệm phá vỡ một tập hợp (shatter). Khái niệm này cho thấy khả năng thể hiện của một lớp khái niệm.

Định nghĩa: Cho không gian mẫu \displaystyle \mathbb{X}, tập \displaystyle S\subset \mathbb{X} và một lớp khái niệm \displaystyle \mathcal{C} trên \displaystyle \mathbb{X}. Đặt

\displaystyle \Pi_{\mathcal{C}}(S) = \{c\cap S:c\in \mathcal{C}\}

Có thể hiểu như sau: \displaystyle \Pi_{\mathcal{C}}(S) là tất cả các khả năng có thể có để một khái niệm \displaystyle c trong lớp khái niệm \displaystyle \mathcal{C} phân chia (phá vỡ) tập các mẫu \displaystyle S thành hai tập:

  • \displaystyle c\cap S thuộc \displaystyle c
  • \displaystyle S\setminus (c\cap S) không thuộc \displaystyle c.

Rõ ràng \displaystyle \Pi_{\mathcal{C}}(S) \subset 2^S, tập các tập con của \displaystyle S.

Định nghĩa (phá vỡ – shatter): Ta nói lớp khái niệm \displaystyle \mathcal{C} phá vỡ tập \displaystyle S nếu \displaystyle \Pi_{\mathcal{C}}(S) = 2^S.

Nghĩa là các khái niệm trong lớp khái niệm \displaystyle \mathcal{C} hoàn toàn phá vỡ tập \displaystyle S (thành mọi tập con có thể có của \displaystyle S).

Định nghĩa (chiều VC – VC dimension): Chiều VC của lớp khái niệm \displaystyle \mathcal{C}, kí hiệu \displaystyle \mathrm{VCD}(\mathcal{C}) là lực lượng lớn nhất của một tập hợp \displaystyle S\subset \mathbb{X} bị phá vỡ bởi \displaystyle \mathcal{C}.

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

Như vậy, chiều VC cho biết khả năng thể hiện của một lớp khái niệm, kích cỡ lớn nhất của một tập hợp mẫu mà các khái niệm nằm trong lớp khái niệm này có thể phân chia.

Nếu \displaystyle \mathrm{VCD}(\mathcal{C})<\infty, ta nói lớp khái niệm \displaystyle \mathcal{C}chiều VC hữu hạn. Ngược lại, ta viết \displaystyle \mathrm{VCD}(\mathcal{C})=\infty. Lưu ý rằng, \displaystyle \mathcal{C} có thể có chiều VC hữu hạn mặc dù bản thân \displaystyle \mathcal{C} vô hạn.

Để chứng minh \displaystyle \mathrm{VCD}(\mathcal{C}) = d, ta phải: (1) chỉ ra một tập \displaystyle S với \displaystyle |S|=d bị phá vỡ bởi \displaystyle \mathcal{C} và (2) chứng minh rằng mọi tập \displaystyle S'\displaystyle |S'|=d+1 không thể bị phá vỡ bởi \displaystyle \mathcal{C}.

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: