1159242
Bổ đề Sauer–Shelah
https://vi.wikipedia.org/wiki?curid=1159242
Title: Bổ đề Sauer–Shelah
Bổ đề Sauer–Shelah (còn gọi là bổ đề hàm phá vỡ) là một mệnh đề toán học về số cách khác nhau một lớp giả thuyết với số chiều VC nhỏ có thể chia đôi một tập hợp cho trước. Bổ đề được chứng minh bởi Vapnik–Chervonenkis và sau đó được chứng minh lại bởi Sauer và Shelah.
Phát biểu.
Giả sử "H" là một lớp giả thuyết có số chiều VC bằng "d" (một giả thuyết là một hàm số nhận giá trị 0 hoặc 1). Định nghĩa hình chiếu của "H" trên tập hợp "S"={"x"1, "x"2..., "x"m}, ký hiệu là , là tập hợp các vectơ {⟨h(X1,X2...,Xm⟩|h∈H}. Một cách tương đương, có thể định nghĩa ΠH(S)={h∩S|h∈H}. Bổ đề Sauer–Shelah khẳng định rằng |ΠH(S)| ≤ O(md).
Chứng minh.
Có nhiều cách chứng minh bổ đề này. Dưới đây là một vài cách chứng minh phổ biến.
Chứng minh quy nạp.
Không mất tính tổng quát, chỉ cần xét lớp giả thuyết "H" gồm các tập hợp con của "S". Trong trường hợp này ΠH(S) = "H".