Author: Hoàng Đình Thắng

UML4.2 – Các lớp hữu hạn có thể học Agnostic PAC

This entry is part 2 of 2 in the series understanding machine learning chapter 4
  • 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
    1. Bước thứ nhất áp dụng union bound
    2. 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).

 

UML4.1- Hội tụ đều là điều kiện đủ cho khả năng học

This entry is part 1 of 2 in the series understanding machine learning chapter 4
  • Một số ký hiệu dùng trong phần này
    \(Z\) – tập các mẫu dữ liệu
    \(\mathcal H\) – không gian giả thuyết rút gọn (mô hình của hàm dự đoán \(h\))
    \(\ell\) – hàm lỗi \(\ell: \mathcal H \times Z \rightarrow \mathbb R^+\)
    \(\mathcal D\) – phân bố trên \(Z\) của dữ liệu
    \(L_S(h)\) – rủi ro thực nghiệm (lỗi) trên tập dữ liệu \(S\)
    \(L_{\mathcal D}(h)\) – rủi ro kỳ vòng trên phân bố dữ liệu \(\mathcal D\)
  • Chương trước đã chỉ ra rằng với giả định khả thi (realizability assumption), tập giả thuyết hữu hạn bất kỳ nào cũng có thể học được PAC (PAC learnable).
  • Trong chương này, sẽ giới thiệu một công cụ tổng quát -hội tụ đều (uniform convergence) và áp dụng nó để chỉ ra rằng bất kỳ tập giả thuyết hữu hạn nào cũng có thể học được trong mô hình agnostic PAC với hàm lỗi tổng quát, khi phạm vi hàm lỗi bị giới hạn.
  • Với một tập giả thuyết \(\mathcal{H}\), mô hình học ERM hoạt động như sau: Với một tập huấn luyện, thuật toán huấn luyện \(A\) đánh giá rủi ro thực nghiệm (hoặc lỗi) của mỗi hàm dự đoán (giả thuyết) \(h\) trong \(\mathcal{H}\) trên tập huấn luyện \(S\) và đưa ra một phần tử \(A(S) \in \mathcal{H}\) tối thiểu hóa rủi ro thực nghiệm này.
    Chúng ta muốn khi hàm dự đoán \(h\) giảm thiểu rủi ro thực nghiệm đối với \(S\) thì \(h\) cũng làm giảm thiểu rủi ro kỳ vọng trên phân bố dữ liệu \(\mathcal D\). Nói cách khác, rủi ro thực nghiệm cần phải gần với rủi ro kỳ vọng trên tất cả các giả thuyết trong tập giả thuyết.
  • Định nghĩa 4.1 (\(\epsilon\)-representative sample-mẫu \(\epsilon\)-đại diện):  Một tập huấn luyện \(S\) được gọi là \(\epsilon\)-đại diện (đối với miền \(Z\), tập giả thuyết \(\mathcal{H}\), hàm lỗi \(\ell \) và phân bố \(\mathcal{D}\)) nếu: \[\forall h \in \mathcal{H}, |L_S(h)-L_D(h)| \leq \epsilon \]
  • Bổ đề sau chỉ ra rằng, bất cứ khi nào mẫu huấn luyện là (\(\frac{\epsilon}{2}\) – đại diện), thì thuật toán học ERM đảm bảo trả về một hàm dự đoán (giả thuyết) tốt.
  • Bổ đề 4.2 Giả sử rằng một tập huấn luyện \(S\) là \(\frac{\epsilon}{2}\)-đại diện đối với \(\langle Z, \mathcal{H}, \ell, \mathcal{D}\rangle\), thì kết quả của thuật toán học \(ERM_{\mathcal H}\): \(h_S \in \underset{h \in \mathcal H}{\arg\min\ L_S(h)}\), thỏa mãn\[L_{\mathcal{D}} (h_S)  \leq \underset{ h \in \mathcal  {H} }{\min L_{\mathcal D } (h) } + \epsilon\]

Chứng minh: với mọi \(h \in \mathcal{H}\),
\(L_{\mathcal{D}} (h_S)  \leq L_{S} (h_S) + \frac{\epsilon}{2}  \leq L_{S} (\mathcal{h}) + \frac{\epsilon}{2}  \leq L_{\mathcal{D}} (h) + \frac{\epsilon}{2} + \frac{\epsilon}{2} = L_{\mathcal{D}} (h) + \epsilon \) 
– Bất đẳng thức 1 và 3 là do giả định \(S\) là  \(\frac{\epsilon}{2} \)-đại diện
– Bất đẳng thức thứ 2 là do \(h_S\) là một dự đoán \(ERM\) thì \(L_{S} (h_S) \leq L_{S} (h)\)

  • Định nghĩa 4.3 (Hội tụ đều): Một tập giả thuyết \(\mathcal{H}\)  có tính chất hội tụ đều đối với \(\langle Z, \ell\rangle \) nếu tồn tại một hàm \(m_\mathcal{H}^{UC}: (0,1)^2 \rightarrow \mathbb{N}\)  sao cho với mọi \(\epsilon, \delta \in (0, 1)\) và với mọi phân bố xác xuất \(\mathcal{D}\) trên \(Z\), nếu \(S\) là tập mẫu của \(m \geq \mathcal{m}_{H}^{UC} (\epsilon, \delta)\) phần tử được lấy độc lập với nhau trong tập \(\mathcal{D}\) thì với xác xuất ít nhất \(1-\delta\), \(S\) là tập \(\epsilon\)-đại diện.
  • Hệ quả 4.4 Nếu \(\mathcal H\) có thuộc tính hội tụ đều với hàm \(m_\mathcal{H}^{UC}\) thì có thể học Xấp xỉ đúng với xác xuất cao (Agnostically PAC learnable) với độ phức tạp mẫu \(m_\mathcal{H} (\epsilon, \delta) \leq m_\mathcal{H}^{UC} (\frac{\epsilon}{2}, \delta)\). Hơn nữa, trong trường hợp này, thuật toán học \(ERM_\mathcal{H}\) là thuật toán học agnostic PAC trên \(\mathcal{H}\).