Theo quan điểm của hệ quả 4.4, mọi lớp giả thuyết hữu hạn \(\mathcal H\) đều có thể học agnostic PAC sau khi chúng ta thiết lập được tính chất hội tụ đều cho nó.
Trong phần này, để chứng minh tính hội tụ đều cho lớp giả thuyết hữu hạn \(\mathcal H\), chúng ta thực hiện theo hai bước
Bước thứ nhất áp dụng union bound
Bước thứ hai sử dụng một bất đẳng thức đo mức độ tập trung quanh kỳ vọng của biến ngẫu nhiên – measure concentration inequality.
Với \(\epsilon, \delta\) cho trước, chúng ta cần tìm tập mẫu kích thước \(\mathcal{m}\) đảm bảo rằng với bất kỳ \(\mathcal{D}\), với xác xuất ít nhất \(1-\delta\) khi chọn \(S=(z_1,…,z_m)\) ngẫu nhiên từ \(\mathcal{D}\), sao cho \(\forall h \in \mathcal{H}, |L_S(h)-L_\mathcal{D}(h)| \leq \epsilon\) .
Lúc đó, ta có:
\[\mathcal{D^m}(\{S: \forall h \in \mathcal{H}, |L_S(\mathcal{h})-L_\mathcal{D}(h)| \leq \epsilon\} ) \geq 1- \delta \]
Tương đương với,
\[A = \mathcal{D^m}(\{S: \exists h \in \mathcal{H}, |L_S(h)-L_\mathcal{D}(h)| > \epsilon\} ) < \delta \qquad \textbf{(4.0)} \]
Khai triển:
\[\{ S:\exists h \in \mathcal{H}, |L_S(h)-L_\mathcal{D}(h)| > \epsilon \} = \cup_{h \in \mathcal H} \{S: |L_S(h)-L_\mathcal{D}(h)| > \epsilon\}\]
Áp dụng bổ đề 2.2 (union bound), ta có:
\[A \leq \sum_{h \in \mathcal H} \mathcal{D^m}(\{S: |L_S(h)-L_\mathcal{D}(h)| > \epsilon\} ) \qquad \textbf{(4.1)} \]
Ý tưởng ở đây là, khi \(m\) đủ lớn và giả thuyết \(h\) cố định, mỗi số hạng bên vế phải, tức là khoảng cách giữa rủi ro kỳ vọng và rủi ro thực nghiệm \(|L_S(h)-L_\mathcal{D}(h)|\), sẽ nhỏ theo bất đẳng thức Hoeffding sau.
Bổ đề 4.5 (Bất đẳng thức Hoeffding-Hoeffding’s Inequality) Với \(\theta_1,…, \theta_m\) là chuỗi biến ngẫu nhiên độc lập, và giả sử rằng với mọi \(\mathcal{i}\), \(\mathbb E[\theta_i]=\mu\) và \(\mathbb P[a \leq \theta_i \leq b] =1\). Thì với bất kỳ \(\epsilon > 0\):
\[\mathbb P\left[ \left| \frac{1}{m}\sum_{i=1}^m\theta_i -\mu \right| > \epsilon \right] \leq 2 \exp\left(-2\frac{m\epsilon^2}{(b-a)^2}\right)\]
(Ý nghĩa: Xác suất để trung bình cộng cách xa kì vọng là rất nhỏ)
Với \(\theta_i \) là biến ngẫu nhiên \(\ell(h,z_i) \in [0,1]\), \(L_S(h)=\frac{1}{m}\sum_{i=1}^{m}\theta_i\) và \(L_\mathcal{D}(h)=\mu\). Áp dụng bổ đề 4.5, với mọi giả thuyết \(h\) cho trước:
\[\mathcal{D^m}(\{S:|L_S(h)-L_\mathcal{D}(h)| > \epsilon\} ) =\mathbb P\left[ \left| \frac{1}{m}\sum_{i=1}^m\theta_i -\mu \right| > \epsilon \right] \leq 2 \exp\left(-2m\epsilon^2\right) \qquad \textbf{(4.2)} \] Kết hợp với biểu thức (4.1), ta có
\[ A \leq \sum_{h \in \mathcal H} 2 \exp\left(-2m\epsilon^2\right) = 2| \mathcal H| \exp\left(-2m\epsilon^2\right) < \delta \]
Nếu chọn
\[m \geq \frac{\log(2|\mathcal{H}|/\delta)}{2\epsilon^2}\]
thì
\[\mathcal{D^m}(\{S: \exists h \in \mathcal{H}, |L_S(h)-L_\mathcal{D}(h)| > \epsilon\} ) \leq \delta \]
Hệ quả 4.6 Với lớp giả thuyết hữu hạn \(\mathcal{H} \), miền \(\mathcal{Z}\) và hàm lỗi \(\ell: \mathcal{H} \times \mathcal{Z} \rightarrow [0,1]\), thì \(\mathcal{H} \) có thuộc tính hội tụ đều với độ phức tạp mẫu
\[\mathcal{m}_\mathcal{H}^{UC} (\epsilon, \delta) \leq \lceil \frac{\log(2|\mathcal{H}|/\delta)}{2\epsilon^2} \rceil \]
Hơn nữa, \(\mathcal{H}\) có thể học agnostic PAC bằng thuật toán ERM với độ phức tạp mẫu
\[\mathcal{m}_\mathcal{H} (\epsilon, \delta) \leq \mathcal{m}_\mathcal{H}^{UC} (\epsilon/2, \delta) \leq \lceil \frac{2\log(2|\mathcal{H}|/\delta)}{\epsilon^2} \rceil\]
Chú ý 4.1: Mọi mô hình có \(d\) tham số (số thực 64 bit) đều đại diện cho không gian giả thuyết hữu hạn \(|\mathcal H| = 2^{64d}\), do đó mô hình đó có thể học Xấp xỉ đúng với xác suất cao (PAC learnable).
