- Như đã được trình bày trong phần trước, nguyên tắc cực tiểu hóa sai số thực nghiệm (ERM) có thể dẫn đến hiện tượng overfitting , vì vậy chúng ta cần một số cải tiến cho thuật toán học sử dụng luật ERM. Chúng ta sẽ tìm kiếm hàm dự đoán từ luật ERM mà không dẫn tới hiện tượng overfitting, tức là hàm dự đoán này hoạt động tốt trên cả tập huấn luyện và trên phân bố dữ liệu \(\mathcal D\).
Một cách làm phổ biến là xây dựng không gian giả thuyết rút gọn và cho thuật toán tìm hàm giả thuyết tối ưu trong không gian đó. Không gian này gọi là lớp các hàm giả thuyết (hypothesis class), kí hiệu là \(\mathcal H\). Mỗi hàm \(h \in \mathcal H\) là hàm ánh xạ \(\mathcal X\) đến \(\mathcal Y\). - Ví dụ: một cách rút gọn không gian giả thuyết hay dùng là: trong tất cả các hàm dự đoán, ta chỉ tìm các hàm dự đoán dạng ngưỡng tuyến tính \(\mathcal H = \{w\cdot x + b \geq 0, w \in \mathbb R^n, b\in \mathbb R\}\)
- Cho lớp các hàm dự đoán \(\mathcal H\) và bộ dữ liệu huấn luyện \(S\), thuật toán học \(\mathit{ERM}_{\mathcal H}\) sẽ sử dụng luật ERM chọn hàm dự đoán \(h \in \mathcal H\) sao cho lỗi trên bộ huấn luyện \(S\) là nhỏ nhất:
\(\begin{align} \mathit{ERM}_{\mathcal H}(S) \in \underset{h \in \mathcal H}{\arg\min L_S(h)} \end{align}\)
Ta sử dụng kí hiệu \(h_{\mathcal{S}}\) cho kết quả hàm giả thiết sau khi áp dụng \(ERM_{\mathcal{H}}\), như vậy \(h_{\mathcal{S}} \in \underset{h \in \mathcal H}{\arg\min\ L_S(h)} \) .
- Định nghĩa 2.1 (Giả thuyết tính khả thi – realizability) :
Tồn tại \(h^* \in \mathcal H\) sao cho \(L_{\mathcal D, f}(h^*) = 0\). Giả định này giả định rằng với tập dữ liệu \(\mathcal S\), được lấy mẫu từ phân phối \(\mathcal D\) và được đánh nhãn bởi hàm \(f\) thì \(L_{S}(h^*) = 0\), vì \(h^*\) đã dự đoán đúng hết trên cả phân phối của dữ liệu.
Giả thuyết trên ngụ ý rằng, với mọi giả thuyết ERM ta đều có thể có được \(L_S(h_S) = 0\). Tuy nhiên chúng ta quan tâm đến rủi ro thực tế của \(h_S\), \(L_{(\mathcal D, f)}(h_S)\) chứ không phải là lỗi thực nghiệm trên tập huấn luyện. - Giả thuyết tất cả các dữ liệu được lấy mẫu độc lập với nhau trong tập \(\mathcal D\) – i.i.d. assumption. \(S \mbox{~} \mathcal D^m\) với \(m\) là số lượng mẫu học có \(S\), ta kí hiệu \(\mathcal D^m\) là xác suất của \(S\) gồm \(m\) mẫu học được chọn độc lập với nhau.
Như vậy tập \(S\) như một cửa sổ nhỏ để ta nhìn được một phần phân bố của dữ liệu học, cửa số càng to đồng nghĩa với tập \(S\) càng lớn thì việc học của ta càng sát với dữ liệu thực. - Khi ta chọn tập \(S\), sẽ có một xác suất nào đó để tập \(S\) được chọn không phản ánh hay thể hiện đúng phân phối \(\mathcal D\). Ta kí hiệu \(\delta\) là xác suất để chọn một tập học không phản ánh đúng phân phối dữ liệu như vậy và \(1-\delta\) đại diện cho sự tự tin của ta đối với hàm dự đoán \(h_S\). Ta kí hiệu \(\epsilon\) tượng trưng cho độ chính xác của mô hình dự đoán, khi đó nếu \(L_{\mathcal D, f}(h_S) < \epsilon\) chứng tỏ hàm dự đoán thu được hoạt động tốt, có thể chấp nhận dùng \(h_S\), ngược lại, nếu \(L_{\mathcal D, f}(h_S) > \epsilon \) chứng tỏ việc học thất bại.
- Ta cần tìm xác suất cận trên của việc lấy mẫu \(m\) dữ liệu dẫn đến việc học thất bại. Giả sử, \(S|_x= (x_1, …, x_m)\) là một tập dữ liệu huấn luyện. Vậỵ ta cần tìm :
\(\mathcal D^m(\{S|_x : L_{(\mathcal D, f)}(h_S) > \epsilon\})\)
- Giả sử \(\mathcal H_B\) là tập các hàm giả thiết cho kết quả kém:
\(\mathcal H_B = \{h \in \mathcal H | L_{(\mathcal H, f)}(h) > \epsilon\}\)
- \(M = \{S|_x : \exists h \in \mathcal H_B, L_S(h) = 0\}\) là tập các bộ dữ liệu huấn luyện có thể lừa thuật toán học (misleading set), ta có \(\{S|_x: L_{(\mathcal D, f)}(h_S)> \epsilon \}\subseteq M\).
Vậy : \(\mathcal D^m(\{S|_x: L_{(\mathcal D, f)}(h_S)> \epsilon\}) \leq \mathcal D^m(M) = \mathcal D^m(\{S|_x: \exists h \in \mathcal H_B, L_S(h)=0\})\) (1) - Ta có \(M = \cup_{h \in \mathcal H_B}\{S|_x: L_S(h)=0\}\)
Suy ra, \(\mathcal D^m(M) = \mathcal D^m( \cup_{h \in \mathcal H_{\mathcal B}}\{S|_x: L_S(h)=0\})\).
Theo Union Bound, \(\mathcal D(A \cup B) \leq \mathcal D(A) + \mathcal D(B)\), nên ta có :
\( \mathcal D^m( \cup_{h \in \mathcal H_B}\{S|_x: L_S(h)=0\}) \leq \sum_{h \in \mathcal H_B} \mathcal D^m(\{S|_x: L_S(h) = 0\})\) (2)
Vì \(S_x\) là tập \(m\) mẫu huấn luyện, nên để \(L_S(h) = 0\) khi và chỉ khi \(h\) dự đoán đúng trên từng mẫu \(x_i\). Hay :
\(\mathcal D^m(\{S|_x: L_S(h) = 0\}) = \prod_{i=1}^m\mathcal D(\{x_i: h(x_i)=f(x_i)\})\)
Hơn nữa, \(\mathcal D(\{x_i: h(x_i)=f(x_i)\}) = 1 – L_{\mathcal D, f}(h) \leq 1 – \epsilon\), nên: \(\mathcal D^m(\{S|_x: L_S(h) = 0\}) \leq (1-\epsilon)^m\) (3)
Từ (1), (2) và (3): \(\mathcal D^m(\{S|_x: L_{(\mathcal D, f)}(h_S) > \epsilon \}) \leq |\mathcal H_B| (1- \epsilon)^m\leq |\mathcal H| (1- \epsilon)^m \leq |\mathcal H| e^{-m\epsilon}\) - Để thuật toán \(\mathit{ERM}_{\mathcal H}\) có độ tự tin cao, ta cho vế phải chặn trên bởi \(\delta\), suy ra khi
\[m\geq \frac{\log(|\mathcal H|/\delta)}{\epsilon}\]
thì với xác suất nhỏ hơn \(\delta\), thuật toán \(\mathit{ERM}_{\mathcal H}\) tìm ra hàm dự đoán \(h_S\) kém, tức là có rủi ro kỳ vọng \(L_{\mathcal D,f}(h_S) > \epsilon\). - Hay nói ngược lại, khi số mẫu dữ liệu
\[m\geq \frac{\log(|\mathcal H|/\delta)}{\epsilon}\]
thì với độ tự tin ít nhất \(1-\delta\), thuật toán \(\mathit{ERM}_{\mathcal H}\) cho hàm dự đoán \(h_S\) tốt, tức là có rủi ro kỳ vọng \(L_{\mathcal D,f}(h_S) < \epsilon\) - Trong chương này, ta giả sử không gian giả thuyết rút gọn \(\mathcal H\) là hữu hạn. Tuy nhiên, từ các công thức trên, có thể thấy số mẫu dữ liệu cần thiết tỉ lệ thuận với \(\log |\mathcal H|\), tức là rất nhỏ so với tổng số giả thiết của \(\mathcal H\).
