Category: Machine Learning

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 🙂

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

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 🙂