Chứng minh bổ đề Sauer cho trường hợp tổng quát
Ý tưởng của việc chứng minh bổ đề Sauer là
\(\forall {\cal{H}}, |{\cal{H}}_C| \leq |\{B \subseteq C: {\cal{H}} \text{ shatters } B\}| \leq \sum_{i=0}^d C(m, i) \hspace{2.0cm} \) (1)
Chúng ta sẽ chứng minh mệnh đề trên bằng quy nạp toán học. Cụ thể như sau:
Trường hợp cơ bản (base case): trong trường hợp \(m = 1\), bất phương trình (1) đúng
Quy nạp (inductive procedure): giả sử phương trình (1) và bổ đề Sauer đúng với mọi \(k < m\). Khi đó
Giả sử \(C’ = \{c_2, …, c_m\}\) là tập con của \(C\).
Giả sử \(Y_0 = \{(y_2, …, y_m):(0, y_2, …, y_m) \in {\cal{H}}_C \lor (1, y_2, …, y_m) \in {\cal{H}}_C\}\), nói cách khác \(Y_0\) là tập các cách đánh nhãn \(C’\) bằng tập \({\cal{H}}\), không quan tâm giá trị của \(c_1\) là gì. Quy chung, \(|{\cal{H}}_{C’}| = |Y_0|\).
Giả sử \(Y_1 = \{(y_2, …, y_m):(0, y_2, …, y_m) \in {\cal{H}}_C \land (1, y_2, …, y_m) \in {\cal{H}}_C\}\) và \({\cal{H}}’ = \{h \in {\cal{H}}:\exists h’ \in {\cal{H}} \text{ s.t. } (1 – h'(c_1), h'(c_2), …, h'(c_m)) = (h(c_1), h(c_2), …, h(c_m))\}\). Cụ thể \({\cal{H}}’\) chứa các cặp các giả thiết \(h, h’\) giống nhau về cách đánh nhãn \(C’\) nhưng khác nhau về cách đánh nhãn \(c_1\). Ta dễ thấy \(|{\cal{H}}’_{C’}| = |Y_1|\).
Ta có quan sát rằng \(|{\cal{H}}_C| = |Y_0| + |Y_1|\). Do đó, để đưa ra cận trên cho \(|{\cal{H}}_C|\), ta có thể đưa ra cận trên cho \(Y_0\) và \(Y_1\).
Ta có:
- \(|Y_0| = |{\cal{H}}_{C’}|\) (dựa vào suy luận ở trên)
- \(|{\cal{H}}_{C’}| \leq |\{B \subseteq C’:{\cal{H}} \text{ shatters } B\}|\)
\(\hspace{1.5cm}= |\{B \subseteq C:c_1 \notin B \land {\cal{H}} \text{ shatters } B\}|\).
Ta cũng có:
- \(|Y_1| = |{\cal{H’}}_{C’}|\) (dựa vào suy luận ở trên)
- \(|{\cal{H}}’_{C’}| \leq |\{B \subseteq C’: {\cal{H}}’ \text{ shatters }B\}|\)
\(\hspace{1.5cm}\leq |\{B \subseteq C: c_1 \in B \land {\cal{H}} \text{ shatters } B\}|\).
Từ các quan sát trên, ta thấy \(|{\cal{H}}_C| \leq |\{B \subseteq C: c_1 \notin B \land {\cal{H}} \text{ shatters } B\}| + |\{B \subseteq C: c_1 \in B \land {\cal{H}} \text{ shatters } B\}|\).
Kết luận: \(|{\cal{H}}_C| \leq |\{B \subseteq C: {\cal{H}} \text{ shatters } B\}|\).
Chứng minh bổ đề Sauer cho trường hợp đặc biệt
Xét trường hợp \(m > d+1\), tức \(m – 2 \geq d\). Ta sẽ chứng minh \(\sum_{k=0}^d C(m, k) \leq (\frac{e m}{d})^d\) bằng phương pháp quy nạp toán học.
Trường hợp cơ bản (base case): với \(d = 1\), bất đẳng thức trên là đúng
Quy nạp (inductive procedure): giả sử bất đẳng thức trên thỏa mãn với một số \(d\), ta xét trường hợp \(d + 1\). Ta có:
\(\sum_{k=0}^{d+1} C(m, k) = \sum_{k=0}^d C(m, k) + C(m, d+1)\)\(\hspace{3.1cm} \leq (\frac{e m}{d})^d + C(m, d+1)\)
\(\hspace{3.1cm} = (\frac{e m}{d})^d (1 + (\frac{d}{e m})^d \cdot \frac{m (m – 1) … (m – d)}{(d + 1) d!})\)
\(\hspace{3.1cm} = (\frac{e m}{d})^d (1 + (\frac{d}{e})^d \cdot \frac{m – d}{(d + 1) d!})\) (vì \(\frac{m}{m} \cdot \frac{m-1}{m} … \cdot \frac{m-d+1}{m} \leq 1\))
Đến đây, ta áp dụng phép xấp xỉ Stirling chuyên dùng để xấp xỉ hàm giai thừa \(n!\), cụ thể, phép xấp xỉ này có dạng \(n! \approx \sqrt{2 \pi n} (\frac{n}{e})^n\). Để tìm hiểu thêm, các bạn tham khảo tại đây. Cụ thể, ta xấp xỉ \(d! \approx \sqrt{2 \pi d} (\frac{d}{e})^d\)
Khi đó,
\(\sum_{k=0}^{d+1} C(m, k) \leq (\frac{e m}{d})^d (1 + (\frac{d}{e})^d \frac{m – d}{(d + 1) \sqrt{2 \pi d} (d / e)^d})\)\(\hspace{3.4cm} = (\frac{e m}{d})^d \cdot (1 + \frac{m – d}{\sqrt{2 \pi d} (d + 1)})\)
\(\hspace{3.4cm} = (\frac{e m}{d})^d \cdot \frac{d + 1 + (m – d) / \sqrt{2 \pi d}}{d + 1}\)
\(\hspace{3.4cm} \leq (\frac{e m}{d})^d \cdot \frac{d + 1 + (m – d)/2}{d + 1}\) (vì \(2 < \sqrt{2 \pi d}\))
\(\hspace{3.4cm} = (\frac{e m}{d})^d \cdot \frac{d/2 + 1 + m/2}{d + 1}\)
\(\hspace{3.4cm} \leq (\frac{e m}{d})^d \cdot \frac{m}{d + 1}\) (vì \(d \leq m – 2\))
Mặt khác, \((\frac{e m}{d})^d \cdot \frac{m}{d + 1} \leq (\frac{e m}{d + 1})^{d+1}\) vì
\((\frac{e m}{d+1})^{d+1} = (\frac{e m}{d})^d \cdot \frac{e m}{d + 1} \cdot (\frac{d}{d+1})^d \)\(\hspace{2.0cm} = (\frac{e m}{d})^d \cdot \frac{e m}{d + 1} \cdot (\frac{1}{1+1/d})^d\)
\(\hspace{2.0cm} = (\frac{e m}{d})^d \cdot \frac{e m}{d + 1} \cdot \frac{1}{(1+1/d)^d}\)
Vì \(e = \lim_{n \to \infty} (1 + \frac{1}{n})^n\) theo định nghĩa của exponential function. Bên cạnh đó \(f(x) = (1 + \frac{1}{x})^x\) là hàm đơn điệu tăng (chứng minh xem tại đây). Vì vậy,
\((\frac{e m}{d+1})^{d+1} \geq (\frac{e m}{d})^d \cdot \frac{e m}{d + 1} \cdot \frac{1}{e}\)
\(\hspace{2.0cm} = (\frac{e m}{d})^d \cdot \frac{m}{d + 1}\)
Vậy, ta kết luận \(\sum_{k=0}^{d+1} C(m, k) \leq (\frac{e m}{d+1})^{d+1}\)