Blog Khoa Học Máy Tính

Bổ đề Sauer

Ngô Quang Hưng | 11 tháng 11, 2008 | Bản để in

Bài học máy qua góc nhìn của lý thuyết tính toán số 4 có chứng minh bổ đề Sauer (bổ đề 5.2) bằng quy nạp. Tuy nhiên, một chứng minh bằng quy nạp không hay lắm vì nó “giấu” trực quan của chứng minh. Trong bài này, chúng ta sẽ chứng minh bổ đề Sauer bằng một kỹ thuật rất phổ biến trong extremal combinatorics gọi là kỹ thuật shifting. Xem các tham khảo sau đây để biết thêm về kỹ thuật shifting:

[1] P. Frankl: The shifting technique in extremal set theory, in Surveys in Combinatorics 1987 (C Whitehead, ed.), London Math. Soc. Lecture Note Series 123, Cambridge University Press (1987), 81–110.

[2] B. Bollobás, Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability. Cambridge University Press 1986.

Rất nhiều định lý cổ điển như định lý Erdos-Ko-Rado (đã chứng minh trên blog này bằng kỹ thuật định trị hai cách) hay định lý Kruskal-Katona đều chứng minh được bằng kỹ thuật shifting. Kỹ thuật này cũng được ứng dụng gần đây trong nhánh phân tích các hàm Boolean. Nhánh này liên hệ mật thiết đến computational learning theory, coding theory, approximation algorithms, và complexity theory: toàn là các đề tài trung tâm của theoretical CS hiện nay.

Ta sẽ phát biểu lại bổ đề Sauer. Gọi $\mathcal H$ là một lớp các hàm số từ $\Omega$ vào $\{0,1\}$ . Có thể hiểu $\mathcal H$ là một bộ các tập con của $\Omega$ . Chú ý rằng cả $\mathcal H$ lẫn $\Omega$ đều có thể vô hạn (thậm chí không đếm được). Với một tập con hữu hạn $S \subseteq \Omega$ , định nghĩa projection của $\mathcal H$ lên như sau: $\Pi_{\mathcal H}(S) = \{ h \cap S \ | \ h \in \mathcal H\}$ . Trong ngữ cảnh “học máy” thì projection của lớp giả thuyết $\mathcal H$ lên một tập hữu hạn các mẫu là bộ tất cả các cách mà các giả thuyết này phân lớp các mẫu này.

Một tập bị băm nát bởi $\mathcal H$ nếu $\Pi_{\mathcal H}(S)$ chính là tập tất cả các tập con của . VC-dimension của $\mathcal H$ là kích thước lớn nhất của một tập con của $\Omega$ bị băm nát bởi $\mathcal H$ . Nếu $\mathcal H$ băm nát một tập con có kích thước lớn tùy ý thì VC-dimension của $\mathcal H$ là vô hạn.

Bổ đề Sauer:

Giả sử $\mathcal H$ có VC-dimension hữu hạn, bằng . Xét một tập con bất kỳ của $\Omega$ . Ta có,

$|\Pi_{\mathcal H}(S)| \leq \sum_{i=0}^d \binom m i$

Chứng minh. Đặt $\mathcal F = \Pi_{\mathcal H}(S)$ . Dĩ nhiên $\mathcal F$ là hữu hạn, và là một bộ các tập con của . Không mất tính tổng quát, ta có thể giả sử m>d . Do $\mathcal H$ không băm nát bất kỳ tập con nào có kích thước $\geq d+1$ , dễ thấy rằng $\mathcal F$ cũng không băm nát bất kỳ tập con nào của với kích thước $\geq d+1$ . Ta sẽ dùng tính chất này để chặn trên $|\mathcal F|$ .

Chúng ta sẽ “xê dịch” (shift) $\mathcal F$ từ từ để thành một bộ $\mathcal G$ các tập con mới của thỏa mãn các điều kiện sau đây:

$|\mathcal G| = |\mathcal F|$
Nếu $A \subset S$ bị băm nát bởi $\mathcal G$ thì cũng bị băm nát bởi $\mathcal F$ .
$\mathcal G$ là một ideal của Boolean lattice trên , nghĩa là nếu $G\in \mathcal G$ thì tất cả các tập con của đều là thành viên của $\mathcal G$ .

Giả sử ta tìm được $\mathcal G$ thỏa mãn các điều kiện trên, thì một tập con của bị $\mathcal G$ băm nát nếu và chỉ nếu $A \in \mathcal G$ . Nhưng $\mathcal G$ không băm nát bất kỳ tập con nào có kích thước $\geq d+1$ . Do đó, tất cả các thành viên của $\mathcal G$ đều có kích thước $\leq d$ . Vì thế $|\mathcal G| \leq \sum_{i=0}^d \binom m i$ .

Đến đây, ta mô tả phép “dịch chuyển” $\mathcal F$ thành $\mathcal G$ thỏa mãn các điều kiện 1, 2, 3 ở trên bằng một thuật toán. Giả sử $S = \{1, 2, \dots, m\}$ .

1. For ( to ) do
2.    Foreach () do
3.        If ( and ), then
4.            Replace  by 
5.        Endif
6.    Endfor
7. Endfor
8. Repeat 1--7 until  no longer changes. Call this final collection

Với mỗi vòng lặp 1–7, nếu bộ $\mathcal F$ không đổi thì thuật toán kết thúc, còn nếu có đổi thì một thành viên nào đó của $\mathcal F$ bị giảm kích thước. Kích thước của các thành viên của $\mathcal F$ không thể giảm mãi (mà $\mathcal F$ vẫn thay đổi), do đó thuật toán sẽ kết thúc.

Bây giờ ta chứng minh rằng $\mathcal G$ thỏa mãn ba điều kiện 1, 2, và 3 ở trên.

Điều kiện 1 đã rõ ràng, vì ta chỉ biến thành $F \setminus \{i\}$ khi $F \setminus \{i\} \notin \mathcal F$
Ta chứng minh rằng tính chất này bất biến sau mỗi lần ta thực hiện vòng lặp 2–6 với một phần tử bất kỳ trong thuật toán trên. Giả sử $\mathcal F$ là bộ tập hợp trước khi vòng lặp này được thực hiện, và $\mathcal F'$ là bộ tập hợp sau khi vòng lặp này được thực hiện.
Giả sử $A\subseteq S$ bị băm nát bởi $\mathcal F'$ . Nếu $i \notin A$ thì dĩ nhiên đã bị băm nát trước thay đổi. Do đó, có thể giả sử $i \in A$ .

Xét một tập con $R\subseteq A$ nào đó. Ta cần chứng minh rằng $R = A \cap F$ với $F \in \mathcal F$ . Do bị băm nát sau vòng lặp, $R = A \cap F'$ với $F' \in \mathcal F'$ . Nếu $i \in R$ thì cũng thuộc $\mathcal F$ . Bây giờ xét trường hợp $i \notin R$ . Tồn tại $T\in \mathal F'$ sao cho $T \cap A = R \cup \{i\}$ . Rõ ràng là cũng thuộc $\mathcal F$ . Nhưng “còn sống sót” sau vòng lặp chứng tỏ là $T \setminus \{i\} \in \mathcal F$ , và do đó $R = A \cap (T \setminus \{i\})$ .
Tính chất này đã rõ.