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 trên 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 và
  • \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} 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' mà \displaystyle |S'|=d+1 không thể bị phá vỡ bởi \displaystyle \mathcal{C}.

Advertisements

This entry was posted on Tháng Bảy 3, 2009 lúc 8:00 sáng and is filed under Lý thuyết học máy. Tagged: , , , , , , , . You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.

Trả lờ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:

Gravatar
WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com ( Đăng xuất /  Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ ( Đăng xuất /  Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter ( Đăng xuất /  Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook ( Đăng xuất /  Thay đổi )

w
Hủy bỏ

Connecting to %s

«
»
 
%d bloggers like this: