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 , tập
và một lớp khái niệm
trên
. Đặt
Có thể hiểu như sau: là tất cả các khả năng có thể có để một khái niệm
trong lớp khái niệm
phân chia (phá vỡ) tập các mẫu
thành hai tập:
thuộc
và
không thuộc
.
Rõ ràng , tập các tập con của
.
Định nghĩa (phá vỡ – shatter): Ta nói lớp khái niệm phá vỡ tập
nếu
.
Nghĩa là các khái niệm trong lớp khái niệm hoàn toàn phá vỡ tập
(thành mọi tập con có thể có của
).
Định nghĩa (chiều VC – VC dimension): Chiều VC của lớp khái niệm , kí hiệu
là lực lượng lớn nhất của một tập hợp
bị phá vỡ bởi
.
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 , ta nói lớp khái niệm
có chiều VC hữu hạn. Ngược lại, ta viết
. Lưu ý rằng,
có thể có chiều VC hữu hạn mặc dù bản thân
vô hạn.
Để chứng minh , ta phải: (1) chỉ ra một tập
với
bị phá vỡ bởi
và (2) chứng minh rằng mọi tập
mà
không thể bị phá vỡ bởi
.
Trả lời