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 🙂