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

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 🙂

Series Navigation

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