Trong chương trước chúng ta chỉ ra rằng với tập giả thuyết \(\mathcal{H}\) hữu hạn thì quy tắc ERM trên tập \(\mathcal{H}\) này khi áp dụng trên tập huấn luyện đủ lớn (kích thước của tập huấn luyện độc lập với phân bố \(\mathcal{D}\) cũng như hàm sinh nhãn \(f\) ) thì kết quả của giả thuyết \(h\) sẽ là xấp xỉ đúng với xác suất cao (Probably Approximately Correct – PAC). Dưới đây chúng ta sẽ làm rõ định nghĩa học PAC.
Định nghĩa 3.1 (Học PAC): Một tập giả thuyết \(\mathcal{H}\) là được coi là PAC nếu tồn tại hàm \(m_\mathcal{H} ( \epsilon, \delta) : (0, 1)^2 \rightarrow \mathbb{N} \) thoả mãn tính chất sau:
Với mọi \(\epsilon, \delta \in (0, 1) \), với mọi phân bố \(\mathcal{D}\) trên \(\mathcal{X} \) và mọi hàm sinh nhãn \(f : \mathcal{X} \rightarrow \lbrace 0, 1 \rbrace \), nếu giả định khả thi (định nghĩa 2.1) đúng trên \(\mathcal{H}, \mathcal{D}, f \) thì khi sử dụng thuật toán với điều kiện \(m \geq m_\mathcal{H} ( \epsilon, \delta) \) , thuật toán trả về một giả thuyết \(h\) mà với xác suất ít nhất là \(1 – \delta \) sao cho \(L_{(\mathcal{D}, f)} (h) \leq \epsilon \)
Trong định nghĩa học PAC có 2 tham số ta cần quan tâm:
Độ chính xác \(\epsilon \) (accuracy parameter) : giới hạn xác suất của lỗi thật (true error, generalization error) với một giả thuyết \(h\)
Độ tin cậy \(\delta \) (confidence parameter): xác suất mà giả thuyết \(h\) đáp ứng được độ chính xác \(\epsilon\)
Độ phức tạp mẫu (Sample Complexity): số mẫu cần có để đảm bảo được tính chất của bộ học PAC. Độ phức tạp mẫu được tính dựa trên tham số độ chính xác \(\epsilon \) và độ tin cậy \(\delta \) ở trên. Ngoài ra thì nó cũng phụ thuộc vào tính chất của tập giả thuyết \(\mathcal{H}\), ví dụ như ta đang xét với một tập hữu hạn \(\mathcal{H}\) thì độ phức tạp mẫu còn phụ thuộc vào log kích thước của \(\mathcal{H}\).
Hệ quả 3.2: Với một tập giả thuyết \(\mathcal{H}\) hữu hạn là PAC ta có độ phức tạp mẫu sau: \[m_\mathcal{H} ( \epsilon, \delta) \leq \lceil { \frac{\log ( |\mathcal{H}|/ \delta ) }{\epsilon} } \rceil \]
