UML 6.1 Tập giả thuyết vô hạn học được (PAC learnable)

This entry is part 1 of 6 in the series understanding machine learning chapter 6
\(\)

Như chúng ta đã biết ở các chương trước, còn một số vấn đề mà chúng ta cần tập trung giải quyết, đó là:

Mục tiêu của chúng ta là tìm ra tính chất của tập \(\mathcal{H}\) đảm bảo học được (PAC learnable). Các chương trước chúng ta đã thấy rằng một tập giả thuyết \(\mathcal{H}\) hữu hạn thì học được. Vậy liệu một tập giả thuyết \(\mathcal{H}\) vô hạn có học được hay không và đặc điểm để một lớp giả thuyết \(\mathcal{H}\) học được là gì?

Ở chương này chúng ta sẽ chứng minh rằng một tập giả thiết \(\mathcal{H}\) vô hạn thì vẫn có thể học được. Chúng ta cũng đưa ra 1 điều kiện đủ để học được là \(\mathcal{H}\) có chiều VC hữu hạn.

Ví dụ về Tập giả thuyết vô hạn học được

Để chứng minh 1 tập giả thiết vô hạn \(\mathcal{H}\) mà vẫn học được, ta xem ví dụ như sau:

Bổ đề 6.1: Tập giả thuyết \(\mathcal{H}\) gồm các hàm ngưỡng \[\mathcal H = \{h_a: h_a(x) = \mathbb 1_{x\leq a}\}\] là tập giả thuyết học được (PAC learnable).

Chứng minh cho Bổ đề 6.1:

Giả sử \(a^*\) là ngưỡng của hàm giả thuyết tốt nhất \(h^*(x) = 1_{x<a^*}\), tức là \(L_D(h^*) = 0 \). Gọi \(\mathcal{D}_x\) là phân phối trên miền \(\mathcal{X}\) và \(a_0 < a^* < a_1\) sao cho
\[\underset{ x \sim \mathcal{D}_x}{\mathbb{P}}[x \in (a_0,a^*)] = \underset{ x \sim \mathcal{D}_x}{\mathbb{P}} [x \in (a^*,a_1)] = \epsilon \]

Cho 1 tập huấn luyện \(\mathcal{S}\), gọi \(b_0 = \max\{x:(x,1) \in \mathcal{S} \}\) và \(b_1 = \min\{x:(x,0) \in \mathcal{S} \}\) (\(b_0\) là giá trị lớn nhất của các dữ liệu có nhãn 1, \(b_1\) là giá trị nhỏ nhất của các dữ liệu có nhãn 0).

Gọi \(b_s\) là ngưỡng tìm được khi sử dụng thuật toán ERM, ứng với hàm \(h_S\), suy ra \(b_S \in (b_0,b_1)\). Do đó điều kiện đủ để \(L_D(h_S) \leq \epsilon \) là \(b_0 \geq a_0\) và \(b_1 \leq a_1\).

\[\underset{ S \sim \mathcal{D}^m}{\mathbb{P}}[L_\mathcal{D}(h_S) > \epsilon]
\leq
\underset{ S \sim \mathcal{D}^m}{\mathbb{P}}[b_0 < a_0 \vee b_1 > a_1 ] \]

hay có thể viết lại

\[\underset{ S \sim \mathcal{D}^m}{\mathbb{P}}[L_\mathcal{D}(h_S) > \epsilon]
\leq
\underset{ S \sim \mathcal{D}^m}{\mathbb{P}}[b_0 < a_0] + \underset{ S \sim \mathcal{D}^m}{\mathbb{P}}[b_1 > a_1]
\]

Mà biến cố \(b_0 < a_0\) xảy ra khi và chỉ khi S không thuộc vào khoảng \((a_0,a^*)\), mà mật độ xác suất trên khoảng đó là \(\epsilon\), ta có:

\[\underset{ S \sim \mathcal{D}^m}{\mathbb{P}}[b_0 < a_0] =
\underset{ S \sim \mathcal{D}^m}{\mathbb{P}}[\forall (x,y) \in S,x \notin (a_0,a^*)] = (1-\epsilon)^m \leq \epsilon^{-\epsilon m}
\]
Nếu ta chọn \(m > \log(2/\delta)/\epsilon\) thì biểu thức trên sẽ bé hơn \(\delta/2\). Tương tự với số hạng còn lại ta được \(\underset{ S \sim \mathcal{D}^m}{\mathbb{P}}[L_\mathcal{D}(h_S) > \epsilon]
\leq \delta \) tức là \(\mathcal H\) học được.

Ví dụ trên cho thầy 1 tập giả thuyết vô hạn vẫn có thể học được hay tính hữu hạn của tập giả thuyết không phải là điều kiện cần để học được.

UML 6.2. Chiều VC của tập giả thuyết

This entry is part 2 of 6 in the series understanding machine learning chapter 6
\(\)

Chúng ta sẽ tiếp cận điều kiện cần cho PAC learnable bằng định nghĩa về giới hạn \(\mathcal{H}\) vào \(\mathcal{C}\) và tính khả tách.

Định nghĩa 6.2 (Giới hạn \(\mathcal{H}\) vào \(\mathcal{C}\)): Giả sử \(\mathcal{H}\) là một tập giả thuyết (ánh xạ từ \(\mathcal{X}\) sang \(\{0,1\}\) và gọi \(\mathcal{C} = \{ c_1,….c_m \} \in \mathcal X\) là một tập các mẫu dữ liệu từ \(\mathcal X\). Giới hạn \(\mathcal{H}\) vào \(\mathcal{C}\) là tập các phần tử của \(\{0,1\}^m\) có được khi sử dụng các giả thuyết trong \(\mathcal H\) trên các mẫu dữ liệu trong \(\mathcal C\)
\[ \mathcal{H}_{\mathcal C} = \{(h(c_1),…,h(c_m)): h \in \mathcal{H}\} \subseteq \{0,1\}^m\]

Định nghĩa 6.3 (Tính khả tách): Tập giả thuyết \(\mathcal{H}\) chia tách được tập hữu hạn \(\mathcal{C} \subset \mathcal{X}\) nếu giới hạn của \(\mathcal{H}\) vào \(\mathcal{C}\) là tất cả các chuỗi nhị phân có độ dài \(m\). Tức là

\[ \mathcal{H}_{\mathcal C} = \{0,1\}^m\]

Ví dụ 6.2. Gọi \(\mathcal{H}\) là tập các hàm ngưỡng trên \(\mathbb{R}\).

  • Xét tập dữ liệu có 1 phần tử, \(\mathcal{C} = \{c_1\}\). Nếu lấy \(a = c_1 + 1\) thì \(h_a(c_1) = 1\). Nếu lấy \(a = c_1 – 1\) thì \(h_a(c_1) = 0\) nên \(\mathcal{H}_{\mathcal C} = \{0,1\}\). Tức là \(\mathcal{H}\) chia tách được \(\mathcal{C}\).
  • Xét tập dữ liệu có 2 phần tử, \(\mathcal{C} = \{c_1,c_2\}\) và \(c_1 < c_2\). Dễ thấy không tồn tại hàm \(h \in \mathcal{H}\) để \( (h(c_1), h(c_2)) = (0,1) \). Vì nếu hàm \(h\) cho \(h(c_1) = 0\) thì rõ ràng \(h(c_2) = 0\). Do đó \(\mathcal{H}\) không chia tách được \(\mathcal{C}\).

VC Dimension – No Free Lunch

Chúng ta sẽ kết hợp VC-Dimension và định lý no free lunch ở chương trước, đầu tiên chúng ta sẽ nhắc lại định lý no free lunch

No free lunch: Với thuật toán học \(\mathcal A\) bất kỳ trên tập tất cả các giả thuyết, gọi \(m\) là số nhỏ hơn một nửa số phần tử của \(\mathcal{X}\), là kích thước tập huấn luyện. gọi \(\mathcal{D}\) là phân bố \(\mathcal{X}\) \times \{0,1\} sao cho:

        1. Tồn tại hàm \(f:\mathcal{X} \rightarrow \{0,1\}\) mà hàm lỗi \(\mathcal{L}_D(f) = 0\)
        2. Với xác suất ít nhất 1/7 có thể chọn được tập \(\mathcal S\) từ \(\mathcal{D}^m\) sao cho \(\mathcal{L}_D(A(S)) \geq 1/8\)

Chứng minh của định lý cho thấy không thể học một tập \(\mathcal{C}\)  có kích thuớc \(2m\) nếu tập huấn luyện của nó chỉ có kích thước là \(m\).

Bây giờ chúng ta sẽ phát biểu lại định lý no free lunch với tính khả tách của \(\mathcal{H}\).

Hệ quả 6.4 (Định lý No Free Lunch): Gọi \(\mathcal{H}\) là một tập giả thuyết ánh xạ từ \(\mathcal{X}\) sang \(\{0,1\}\) và \(m\) là kích thước tập huấn luyện. Giả sử có tập \(\mathcal{C} \subset \mathcal{X}\) có kích cỡ \(2m\) có thể chia tách được bởi \(\mathcal{H}\). Với mọi thuật toán học, \(\mathcal A\), tồn tại phân bố \(\mathcal{D}\) trên \(\mathcal{X} \times \{0,1\}\) và hàm gắn nhãn \(h \in \mathcal{H}\) sao cho \(L_\mathcal{D}(h) = 0\) nhưng với xác suất ít nhất 1/7 có thể chọn được tập \(\mathcal S\) từ \(\mathcal{D}^m\) sao cho \(\mathcal{L}_D(A(S)) \geq 1/8\)

Định lý cho thấy \(\mathcal{H}\) không thể học được  khi \(\mathcal{H}\) chia tách được \(\mathcal{C}\) có kích thước 2m với kích thước tập huấn luyện là \(m\).

Định nghĩa 6.5 (chiều VC – Vapnik–Chervonenkis Dimension): Chiều VC của tập giả thiết \(\mathcal{H}\), ký hiệu \(\mathrm{VCdim}(\mathcal{H})\), là kích thước tối đa của tập \(\mathcal{C} \subset \mathcal{X}\) có thể chia tách được bởi \(\mathcal{H}\). Nếu \(\mathcal{H}\) có thể chia tách được mọi tập \(\mathcal C\) thì ta nói \(\mathcal{H}\) có chiều VC vô hạn.

Định lý 6.6: Nếu \(\mathcal{H}\) có chiều VC vô hạn thì \(\mathcal{H}\) không học được.

Chứng minh: Vì (\(\mathcal{H}\)) có chiều VC vô hạn, bất kỳ tập huấn luyện có kích thước \(m\) nào thì luôn có tập phân tách được có kích thước \(2m\), do hệ quả 6.4 (No Free Lunch), ta có điều phải chứng minh.

Phần sau sẽ chứng minh rằng nếu hữu hạn VC-dim thì (\(\mathcal{H}\)) PAC learnable.

Một số ví dụ về chiều VC của một tập giả thuyết

Để tính \(\mathrm{VCdim}(\mathcal{H})\) ta thực hiện 2 bước:

    1. Chỉ ra rằng có một tập \(\mathcal{C}\) kích thước \(m\) mà \(\mathcal{H}\) chia tách được
    2. Mọi tập \(\mathcal{C}\) kích thước \(m+1\) thì \(\mathcal{H}\) không chia tách được.

Ví dụ về hàm ngưỡng. Ví dụ 6.2 cho thấy tập \(\mathcal H\) các hàm ngưỡng có chiều VC bằng 1.

Ví dụ hàm khoảng (interval). Gọi \(\mathcal{H}\) là tập các hàm khoảng trên \(\mathbb{R}\), \(\mathcal{H} = \{h_{a,b}: a,b \in \mathbb{R}, a < b\}\) sao cho \(h_{a,b}(x) = 1_{x\in(a,b)}\).

Khi \(\mathcal{C} = \{c_1,c_2\}\)

      •  \(h_{c_1-2,c_1-1}\) cho \((0,0)\)
      • \(h_{(c_1+c_2)/2, c_2+1}\) cho \((0,1)\)
      • \(h_{c_1-1, (c_1+c_2)/2}\) cho \((1,0)\)
      •  \(h_{c_1-1, c_2+1}\) cho \((1,1)\)

Tức là \(\mathcal{H}\) chia tách được \(\mathcal{C}\) bất kỳ có kích thước bằng 2 hay \(\mathrm{VCdim}(\mathcal{H}) \geq 2\)

Tuy nhiên với \(\mathcal{C} = \{c_1,c_2,c_3\}\) thì \(\mathcal{H}\) không  thể ánh xạ \(\mathcal{C} \rightarrow \{1,0,1\}\) nên \(\mathcal{H}\) không phân tách được \(\mathcal{C}\) có 3 phần tử.

Kết luận: chiều VC của lớp các hàm khoảng bằng 2.

Chiều VC và số tham số của mô hình

Ta thường thấy \(\mathrm{VCdim}(\mathcal{H})\) thường bằng số tham số của \(\mathcal{H}\). Tuy nhiên điều này không phải lúc nào cũng đúng, một ví dụ là khi \(\mathcal{X} = \mathbb{R}\) với \(\mathcal{H} = \{h_{\theta} = \lceil 0.5 sin(\theta x)\rceil: \theta \in \mathbb R\} \) thì \(\mathcal H\) có chiều VC vô hạn.

UML6.4 Định lý cơ bản của Học máy thống kê

This entry is part 3 of 6 in the series understanding machine learning chapter 6

Định lý 6.7 – Định lý cơ bản của Học máy thống kê

Phiên bản gốc

Giả sử ta có một lớp giả thiết \({\cal{H}}\) và một hàm lỗi \(0-1\). Khi đó, ta có các mệnh đề sau là tương đương:

      • \({\cal{H}}\) có thuộc tính hội tụ đều
      • Các thuật toán ERM (Tối thiểu lỗi thực nghiệm) là thuật toán học agnostic PAC cho \({\cal{H}}\)
      • \({\cal{H}}\) có tính chất học được kiểu agnostic PAC
      • \({\cal{H}}\) có tính chất học được kiểu PAC
      • Các thuật toán ERM là thuật toán học PAC cho \({\cal{H}}\).
      • \({\cal{H}}\) có VC-dimension hữu hạn

Phiên bản định lượng

Giả sử lớp giả thiết \({\cal{H}}\) có VC-dimension là \(d < \infty\), khi đó độ phức tạp mẫu để \({\cal{H}}\) có tính chất hội tụ đều, cũng như agnostic PAC learnability là \(\Theta(\frac{d + \log (1/\delta)}{\epsilon^2})\) với \((1 – \delta)\) và \(\epsilon\) lần lượt là “độ tự tin” và “tỉ lệ lỗi” mong muốn.

Bên cạnh đó, độ phức tạp mẫu để \({\cal{H}}\) có tính chất PAC learnability, biết trước rằng giả thiết tối ưu trong \({\cal{H}}\) có tỉ lệ lỗi bằng \(0\), là \(\Theta(\frac{d + \log (1/\delta)}{\epsilon})\).

LƯU Ý

  • Định lý cơ bản về học máy thống kê nêu trên có thể thỏa mãn đối với một số các bài toán học máy khác, bên cạnh bài toán phân lớp nhị phân, tuy nhiên không phải thỏa mãn đối với tất cả bài toán học máy.
  • Khả năng học (learnability) đôi khi cũng có thể xảy ra khi lớp giả thiết không có tính chất hội tụ đều.
  • Trong một số trường hợp, ERM rule có thể thất bại, tuy nhiên khả năng học (learnability) vẫn hoàn toàn có thể xảy ra đối với các mô hình học máy (learning rule) khác.

Nhắc lại kiến thức

Hàm lỗi \(0-1\):

Trong bài toán phân lớp nhị phân, giả sử ta có giá trị dự đoán \(h\) và giá trị thực tế \(y\), hàm lỗi \(0-1\) được định nghĩa như sau:

\(L(y, h) = \begin{cases} 0 & y = h \\ 1 & y \neq h\end{cases}\)

Đối với một tập các giá trị thực và giá trị dự đoán tương ứng \(S = \{(y^{(i)}, h^{(i)})\}_{i=1}^n\), hàm lỗi \(0-1\) được định nghĩa như sau:

\(L(S) = \frac{1}{n} \sum_i L(y^{(i)}, h^{(i)})\)

Tức, trung bình cộng của các \(L(y^{(i)}, h^{(i)})\) trong tập \(S\).

Mô hình Empirical Risk Minimization (ERM)

Đây là mô hình tối ưu với mục đích là tìm ra giả thiết tối ưu trong tập \({\cal{H}}\) đối với dữ liệu huấn luyện \(S\). Trong bài này, chúng ta giả sử rằng giả thiết tối ưu \(h_S\), đối với tập \(S\), trong \({\cal{H}}\) luôn được tìm thấy bởi mô hình ERM.

\(h_S = \arg\min_{h\in\mathcal H} L_S(h)\)

Xem chi tiết tại đây

Định lý “không có bữa trưa miễn phí”

Theo định lý “Không có bữa trưa miễn phí”, nếu một lớp giả thiết \({\cal{H}}\) (VD: một mô hình mạng nơ-ron nhân tạo) có VC-dimension vô hạn thì tập giả thiết này không thể học được (not learnable).

Xem chi tiết tại đây

Tính chất  hội tụ đều của lớp giả thiết

Một lớp giả thiết \({\cal{H}}\) được cho là có tính chất hội tụ đều nếu khi kích thước tập dữ liệu huấn luyện đạt tới một mức nào đó thì, với xác suất cao là \(1 – \delta\), ta sẽ có được một tập dữ liệu \(S\) phản ánh được khả năng của \({\cal{H}}\) trên phân bố dữ liệu \(\mathcal D\), hay còn gọi là tập đại diện \(\epsilon\). Nói cách khác, \(|L_{\cal{D}}(h) – L_S(h)| \leq \epsilon\) với mọi giả thuyết \(h \in \mathcal H\), trong đó có \(h_S\) là giả thiết được tìm ra bởi một mô hình học ERM.

Xem chi tiết tại đây

PAC learnability – khả năng học “có thể gần đúng”

Học được kiểu PAC (Probably Approximate Correct learnable) – khả năng học có thể gần đúng (viết tắt là học được) là một tính chất quan trọng của một lớp giả thuyết. Nó cho biết với xác suất cao, chúng ta có thể học được giả thiết xấp xỉ giả thuyết tốt nhất \(h^*\) với lớp giả thiết \({\mathcal{H}}\) hay không.

Agnostic PAC learnability (khả năng học có thể gần đúng trong trường hợp bất khả tri): khả năng học được một giả thiết tốt nhất, hoặc xấp xỉ tốt nhất, trong tập các giả thiết \({\cal{H}}\) hay không.

PAC learnability (khả năng học có thể gần đúng) là trường hợp đặc biệt của Agnostic PAC learnability, khi này, chúng ta đưa ra thêm giả định rằng giả thiết tối ưu trong tập \({\cal{H}}\) có thể đưa ra dự đoán chính xác 100% với mọi dữ liệu thực tế, tức hàm lỗi thực tế bằng \(0\).

Xem chi tiết tại đây và đây

Chiều VC

VC-dimension của một lớp giả thiết \({\cal{H}}\) được định nghĩa là số điểm dữ liệu tối đa mà tập giả thuyết \({\cal{H}}\) có thể chia tách được, sử dụng một trong những giả thiết trong \({\cal{H}}\).

Xem chi tiết tại đây.

UML6.5 Chứng minh định lý cơ bản của học máy thống kê

This entry is part 4 of 6 in the series understanding machine learning chapter 6

Chứng minh định lý cơ bản của học máy thống kê – phần 1

Nhắc lại định lý cơ bản của học máy thống kê, ta đánh số các mệnh đề lần lượt từ (1) đến (6). Ta có thể chứng minh đơn giản một số mối quan hệ kéo theo (implication) giữa các mệnh đề như sau:

      • Mệnh đề (1) kéo theo mệnh đề (2): theo các chương trước, nếu \({\cal{H}}\) có tính chất hội tụ đều tức là với xác suất cao là chúng ta sẽ có một bộ dữ liệu huấn luyện đại diện. Vì vậy, khi áp dụng ERM rule để tối thiểu hàm lỗi trên bộ dữ liệu này, chúng ta sẽ có được một giả thiết \(h_S\) thỏa mãn hàm lỗi huấn luyện (training loss) \(L_S(h_S)\) không quá chênh lệch so với hàm lỗi tổng quát (generalization loss) \(L_{\cal{D}}(h_S)\). (xem lại các chương trước). Điều này tương đương với mệnh đề (2)
      • Mệnh đề (2) kéo theo mệnh đề (3): theo định nghĩa của agnostic PAC learnability
      • Mệnh đề (3) kéo theo mệnh đề (4): do PAC learnability là trường hợp đặc biệt của agnostic PAC learnability, khi tồn tại một giả thiết \(h\) trong \({\cal{H}}\) với hàm lỗi tổng quát \(L_{\cal{D}}(h)\) mang giá trị \(0\)
      • Mệnh đề (4) kéo theo mệnh đề (5): theo định nghĩa của PAC learnability
      • Mệnh đề (5) kéo theo mệnh đề (6): theo định lý “không có bữa trưa miễn phí”, nếu lớp giả thiết \({\cal{H}}\) của chúng ta có VC-dimension vô hạn thì \({\cal{H}}\) sẽ không có tính chất PAC learnability cũng như agnostic PAC learnability, kéo theo là không có ERM rule nào là một PAC learner thành công với \({\cal{H}}\). Do vậy, nếu mệnh đề (5) đúng thì buộc mệnh đề (6) phải đúng.

Vậy chúng ta đã chứng minh được các quan hệ kéo theo (1) \(\to\) (2), (2) \(\to\) (3), (3) \(\to\) (4), (4) \(\to\) (5), và (5) \(\to\) (6). Để hoàn tất chứng minh định lý cơ bản của học máy thống kê, ta cần chứng minh mối quan hệ kéo theo (6) \(\to\) (1).

Chứng minh định lý cơ bản của học máy thống kê – phần 2

Tiếp theo ta cần chứng minh mối quan hệ kéo theo (6) \(\to\) (1). Để chứng minh được mối quan hệ kéo theo này là một chặng đường rất dài và gian nan. Chúng ta sẽ bắt đầu từ các kiến thức nền trước.

Ý tưởng của chúng ta là:

      • Bước 1: chứng minh rằng nếu \(\text{VCdim}({\cal{H}}) = d\) thì khi chúng ta giới hạn \({\cal{H}}\) vào một tập hữu hạn các điểm dữ liệu \(C \subset {\cal{X}}\), thì kích thước của \({\cal{H}}_C\) (effective size của \({\cal{H}}\)) sẽ có giá trị không quá lớn khoảng \(O(|C|^d)\).
      • Bước 2: Khi các tập giả thuyết \({\cal{H}}\) thỏa mãn \({\cal{H}}_C \in O(|C|^d)\) như trên, tức là \(|{\cal{H}}_C|\) chỉ tăng theo hàm đa thức của \(|C|\), ta sẽ chứng minh rằng \({\cal{H}}\) có tính chất hội tụ đều.

Kiến thức nền tảng

Định nghĩa 6.9 (Hàm tăng trưởng – growth function): Hàm tăng trưởng của một lớp giả thiết \({\cal{H}}\) là

\(\tau_{\cal{H}}(m) = \max_{C \subset {\cal{X}}:|C| = m} |{\cal{H}}_C|\)

Nói cách khác, \(\tau_{\cal{H}}(m)\) là số cách tối đa để đánh nhãn \(m\) điểm dữ liệu bất kì (khác với restriction là số cách đánh nhãn \(m\) điểm dữ liệu cố định). Hàm tăng trưởng được dùng để đánh giá độ phức tạp của một lớp giả thiết \({\cal{H}}\).

Lưu ý rằng, khi \(\text{VCdim}({\cal{H}}) = d\) thì \(\tau_{\cal{H}}(m) = 2^m~\forall m \leq d\). Cụ thể, khi \(m \leq d\) thì lớp giả thiết \(\mathcal H\) có thể đánh nhãn ít nhất một tập \(m\) điểm dữ liệu một cách tùy ý.

Bổ đề 6.10 (Sauer-Shelah-Perles): nếu \(\text{VCdim}({\cal{H}}) \leq d < \infty\) thì \(\tau_{\cal{H}}(m) \leq \sum_{i=0}^d C(m, i) \forall m\) với \(C(m, i)\) là số tổ hợp chập \(i\) của \(m\). Đặc biệt, khi \(m < d+1\) thì \(\tau_{\cal{H}}(m) \leq (\frac{e m}{d})^d\).

Hệ quả của bổ đề Sauer chính là điều cần chứng minh ở bước 1. Cụ thể, khi \(\text{VCdim}({\cal{H}})\) hữu hạn, thì effective size của \({\cal{H}}\) sẽ nhỏ, và tăng theo hàm đa thức của \(m\), tức kích cỡ mẫu.

Chứng minh: Xem ở đây

Hội tụ đều cho các lớp giả thiết với hàm tăng trưởng nhỏ

Ta có một định lý như sau (tạm gọi là “Định lý về hội tụ đều cho các lớp giả thiết với effective size nhỏ”).

Định lý 6.11: Giả sử \({\cal{H}}\) là một lớp giả thiết và \(\tau_{\cal{H}}\) là hàm tăng trưởng của \({\cal{H}}\). Khi đó, với mọi phân phối dữ liệu \({\cal{D}}\) và \(\delta \in (0, 1)\), thì với xác suất ít nhất là \(1 – \delta\) trên các tập huấn luyện \(S \sim {\cal{D}}^m\), ta có

\(|L_{\cal{D}}(h) – L_S(h)| \leq \frac{4 + \sqrt{\log (\tau_{\cal{H}}(2m))}}{\delta \sqrt{2m}}\)

Chứng minh định lý 6.11: Xem ở đây

Định lý cơ bản của học máy thống kê (định lý 6.7) là hệ quả của định lý 6.11.

Chứng minh định lý 6.7: Ý tưởng chung của chứng minh là

\(m_{\cal{H}}^\text{UC} \leq 4 \frac{16d}{(\delta \epsilon)^2} \log (\frac{16d}{(\delta \epsilon)^2}) + \frac{16d \log (2e/d)}{(\delta \epsilon)^2}\)

Từ bổ đề Sauer, ta có: với \(m > d\), thì \(\tau_{\cal{H}}(2m) \leq (2em/d)^d\). Kết hợp với kết của của “Định lý về  hội tụ đều cho các lớp giả thiết có effective size nhỏ”, ta có:

\(P[|L_S(h) – L_{\cal{D}}(h)| \leq \frac{4 + \sqrt{d \log(2em/d)}}{\delta \sqrt{2m}}] \geq 1-\delta\)

Giả sử rằng \(\sqrt{d \log (2em/d)} \geq 4\) (nhằm đơn giản hóa bài toán), ta có:

\(\frac{4 + \sqrt{d \log(2em/d)}}{\delta \sqrt{2m}} \leq \frac{2 \sqrt{d \log(2em/d)}}{\delta \sqrt{2m}}\)

Vì vậy,

\(|L_S(h) – L_{\cal{D}}(h)| \leq \frac{1}{\delta} \sqrt{\frac{2d \log(2em/d)}{m}}\)

Để đảm bảo rằng \(\frac{1}{\delta} \sqrt{\frac{2d \log(2em/d)}{m}}\) đạt tối đa là \(\epsilon\), ta cần:

\(m \geq \frac{2d \log(m)}{(\delta \epsilon)^2} + \frac{2d \log (2e/d)}{(\delta \epsilon)^2}\)

Điều kiện cần để bất đẳng thức trên thỏa mãn là

\(m \geq 4 \frac{2d}{(\delta \epsilon)^2} \log (\frac{2d}{(\delta \epsilon)^2}) + \frac{4 d \log(2e/d)}{(\delta \epsilon)^2} \hspace{1.0cm}\) (4)

LƯU Ý

Cận trên được triển khai cho \(m^\text{UC}_{\cal{H}}\) vừa rồi không phải là cận trên chặt nhất

 

Chứng minh bất phương trình (4)

Giả sử \(a \geq 1\) và \(b > 0\). Khi đó, \(x \geq 4 a \log (2 a) + 2 b\) sẽ kéo theo \(x \geq a \log(x) + b\)

Chứng minh: đề nghị mọi người xem sách – Lemma A.2 🙂

UML6.5.1 Chứng minh bổ đề Sauer

This entry is part 5 of 6 in the series understanding machine learning chapter 6
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\}: {\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}= |\{B \subseteq C’: {\cal{H}}’ \text{ shatters } B \cup c_1\}|\)

\(\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}\)

UML6.5.2 Chứng minh định lý 6.11 cho hàm tăng trưởng nhỏ

This entry is part 6 of 6 in the series understanding machine learning chapter 6
Chứng minh định lý về hội tụ đều cho các lớp giả thiết có effective size nhỏ

Ta sẽ chứng minh \(E_{S \sim {\cal{D}}^m} [\sup_{h \in {\cal{H}}} |L_{\cal{D}}(h) – L_S(h)|] \leq \frac{4 + \sqrt{\log \tau_{\cal{H}}(2m)}}{\sqrt{2m}} \).

Với hai bộ dữ liệu \(S = z_1, …, z_m\) và \(S’ = z’_1, …, z’_m\), với các điểm dữ liệu của hai tập được lấy mẫu i.i.d (i.e. phân bố độc lập giống nhau), và mọi giả thiết \(h \in {\cal{H}}\).

Ta có một số quan sát như sau:

  • \(E_{S \sim {\cal{D}}^m} [\sup_{h \in {\cal{H}}} |L_{\cal{D}}(h) – L_S(h)|] = E_{S \sim {\cal{D}}^m} [\sup_{h \in {\cal{H}}} |E_{S’ \sim {\cal{D}}^m} L_{S’}(h) – L_S(h)|]\)
    • Giải thích: theo công thức \(E(X) = E(\bar{X}_n)\)
  • \(|E_{S’ \sim {\cal{D}}^m} [L_{S’}(h) – L_S(h)]| \leq E_{S’ \sim {\cal{D}}^m} |L_{S’}(h) – L_S(h)|\)
    • Giải thích: theo công thức \(|E(X)| \leq E(|X|)\)
    • Hệ quả: \(\sup_{h \in {\cal{H}}} |E_{S’ \sim {\cal{D}}^m} [L_{S’}(h) – L_S(h)]| \leq \sup_{h \in {\cal{H}}} E_{S’ \sim {\cal{D}}^m} |L_{S’}(h) – L_S(h)|\)
  • \(\sup_{h \in {\cal{H}}} E_{S’ \sim {\cal{D}}^m} |L_{S’}(h) – L_S(h)| \leq E_{S’ \sim {\cal{D}}^m} [\sup_{h \in {\cal{H}}} |L_{S’}(h) – L_S(h)|]\)
    • Giải thích: theo công thức \(\sup E(X) \leq E(\sup X)\)

Quy chung,

\(E_{S \sim {\cal{D}}^m} [\sup_{h \in {\cal{H}}} |L_{\cal{D}}(h) – L_S(h)|] \leq E_{S, S’ \sim {\cal{D}}^m} [\sup_{h \in {\cal{H}}} |L_{S’}(h) – L_S(h)|]\)

\(\hspace{7.2cm} = E_{S, S’ \sim {\cal{D}}^m} [\sup_{h \in {\cal{H}}} \frac{1}{m} |\sum_{i=1}^m (l(h, z’_i) – l(h, z_i))|] \hspace{1.0cm}\) (2)

Xét hiệu của hai hàm mất mát \([l(h, z’_i) – l(h, z_i)]\). Ta có, vì các điểm dữ liệu trong \(S\) và \(S’\) được lấy mẫu độc lập giống nhau, nên nếu ta thay \([l(h, z’_i) – l(h, z_i)]\) bằng \([l(h, z_i) – l(h, z’_i)] = – [l(h, z’_i) – l(h, z_i)]\) vào bất phương trình (2) thì kết quả vẫn không thay đổi. Do đó, với mọi \(\sigma_i \in \{-1, +1\}\), ta có vế phải của bất phương trình (2) sẽ bằng:

\(E_{S, S’ \sim {\cal{D}}^m} [\sup_{h \in {\cal{H}}} \frac{1}{m} |\sum_{i=1}^m \sigma_i[l(h, z’_i) – l(h, z_i)]|]\)

Khẳng định trên vẫn giữ nguyên nếu chúng ta lấy mẫu \(\sigma_i\) i.i.d từ phân phối đều (uniform distribution) trên hai giá trị \(1\)  và \(-1\), gọi là \(U_{\pm}\).  Khi đó, vế phải của bất phương trình (2) trở thành:

\(E_{\sigma \sim U^m_{\pm}} E_{S, S’ \sim {\cal{D}}^m} [\sup_{h \in {\cal{H}}} \frac{1}{m} |\sum_{i=1}^m \sigma_i[l(h, z’_i) – l(h, z_i)]|]\)

\(= E_{S, S’ \sim {\cal{D}}^m} E_{\sigma \sim U^m_{\pm}} [\sup_{h \in {\cal{H}}} \frac{1}{m} |\sum_{i=1}^m \sigma_i[l(h, z’_i) – l(h, z_i)]|]\)

Phương trình trên dựa trên tính tuyến tính của phép lấy trung bình giá trị biến ngẫu nhiên. Cố định \(S\) và \(S’\), giả sử \(C = S \cup S’\), khi đó:

\(E_{\sigma \sim U^m_{\pm}} [\sup_{h \in {\cal{H}}} \frac{1}{m} |\sum_{i=1}^m \sigma_i[l(h, z’_i) – l(h, z_i)]|]\)

\(= E_{\sigma \sim U^m_{\pm}} [\max_{h \in {\cal{H}}_C} \frac{1}{m} |\sum_{i=1}^m \sigma_i[l(h, z’_i) – l(h, z_i)]|]\)

Cố định một giả thiết \(h \in {\cal{H}}_C\) và kí hiệu \(\theta_h = \frac{1}{m} \sum_{i=1}^m \sigma_i [l(h, z’_i) – l(h, z_i)]\). Ta có \(E[\theta_h] = 0\), do cả \(l(h, z’_i), l(h, z_i)\) đều có cùng phân phối, và \(\theta_h\) là giá trị trung bình của các biến ngẫu nhiên độc lập với khoảng giá trị \([-1, 1]\). Ta áp dụng bất đẳng thức Hoeffding: cho mọi \(\rho > 0\),

\(P[|\theta_h| > \rho] \leq 2 \exp(-2 m \rho^2)\)

Áp dụng union bound cho mọi \(h \in {\cal{H}}_C\), ta có: cho mọi \(\rho > 0\),

\(P[\max_{h \in {\cal{H}}_c} |\theta_h|  > \rho] \leq 2 |{\cal{H}}_C| \exp(-2 m \rho^2)\)

Ta suy ra:

\(E[\max_{h \in {\cal{H}}_C} |\theta_h|] \leq \frac{4 + \sqrt{\log |{\cal{H}}_C|}}{\sqrt{2m}} \hspace{1.0cm}\) (3)

Kết hợp tất cả, kèm theo định nghĩa \(\tau_{\cal{H}} = \max_{C \subset {\cal{X}}:|C| = m} |{\cal{H}}_C|\), và giả thiết \(|C| = |S| + |S’| = 2m\) ta có:

\(E[\max_{h \in {\cal{H}}_C} |\theta_h|] \leq \frac{4 + \sqrt{\log(\tau_{\cal{H}} (2m))}}{\sqrt{2m}}\)

Mà \(E[\max_{h \in {\cal{H}}_C} |\theta_h|] \geq E_{S \sim {\cal{D}}^m} [\sup_{h \in {\cal{H}}} |L_{\cal{D}}(h) – L_S(h)|]\) dựa vào phương trình (2). Nên ta có:

\(E_{S \sim {\cal{D}}^m} [\sup_{h \in {\cal{H}}} |L_{\cal{D}}(h) – L_S(h)|] \leq \frac{4 + \sqrt{\log(\tau_{\cal{H}} (2m))}}{\sqrt{2m}}\)

Tiếp theo, ta áp dụng bất đẳng thức Markov cho xác suất thống kê. Cụ thể, do \(\sup_{h \in {\cal{H}}} |L_{\cal{D}}(h) – L_S(h)|\) là một biến ngẫu nhiên mang giá trị dương, nên ta hoàn toàn có thể áp dụng bất đẳng thức \(P(X \geq a) \leq \frac{E(X)}{a}\).

\(P(|L_{\cal{D}}(h) – L_S(h)| \geq \frac{4 + \sqrt{\log(\tau_{\cal{H}} (2m))}}{\delta \sqrt{2m}}) \leq P(\sup_{h \in {\cal{H}}} |L_{\cal{D}}(h) – L_S(h)| \geq \frac{4 + \sqrt{\log(\tau_{\cal{H}} (2m))}}{\delta \sqrt{2m}})\)

\(\hspace{7.0cm} \leq \frac{E_{S \sim {\cal{D}}^m} [\sup_{h \in {\cal{H}}} |L_{\cal{D}}(h) – L_S(h)|]}{\frac{4 + \sqrt{\log(\tau_{\cal{H}} (2m))}}{\delta \sqrt{2m}}}\)

\(\hspace{2.3cm} \leq \delta\)

Vì vậy, \(P(\sup_{h \in {\cal{H}}} |L_{\cal{D}}(h) – L_S(h)| \leq \frac{4 + \sqrt{\log(\tau_{\cal{H}} (2m))}}{\delta \sqrt{2m}}) \geq 1 – \delta\). Đây chính là điều cần chứng minh.

Chứng minh bất phương trình (3)

Giả sử \(X\) là một biến ngẫu nhiên và \(x’ in \textbf{R}\) là một sclar. Giả sử rằng tồn tại một số \(a > 0\) sao cho với mọi \(t \geq 0\), \(P[|X – x’| > t] \leq 2 e^{-t^2/a^2}\). Khi đó \(E[|X – x’|] \leq 4 a\)

Chứng minh: đề nghị mọi người xem sách – Lemma A.4 🙂