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 🙂

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 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.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.