- 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 \]
Series: understanding machine learning chapter 3
UML 3.2.1 Mô hình học Agnostics PAC
- Trong các bài toán thực tế, mô hình học PAC dựa trên giả định khả thi (định nghĩa 2.1, tồn tại \(h^* \in \mathcal{H} \) mà \(\underset{x \sim \mathcal D} {\mathbb P} [ h^* (x) = f(x)] = 1\) ) rất khó đạt được, do vậy chúng ta sẽ chuyển sang một mô hình thực tế hơn – mô hình học Agnostics PAC mà bỏ qua giả định khả thi trên.
- Với \(\mathcal{D} \) là phân bố trên \(\mathcal{X} \times \mathcal{Y} \), \(\mathcal{X}\) là miền giá trị đầu vào và \(\mathcal{Y}\) là miền giá trị nhãn.; khi đó lỗi thật (true error) và rủi ro thực nghiệm (empirical risk) dựa trên giả thuyết \(h\) được xác định như sau:
- Lỗi thật: \[ L_{D}(h) = \underset{ (x, y) \sim \mathcal D} {\mathbb P} [h(x) \neq y] \qquad (3.1) \]
- Rủi ro thực nghiệm: \[ L_{S}(h) = \frac{| \lbrace i \in [m] : h(x_i) \neq y_i \rbrace | }{m} \]
- Mục tiêu: Tìm một số giả thuyết \(h : \mathcal{X} \rightarrow \mathcal{Y} \) mà lỗi thật \(L_{D}(h)\) là nhỏ nhất có thể.
- Hàm dự đoán tối ưu Bayes: Với phân bố \(\mathcal{D}\) trên \(\mathcal{X} \times \lbrace 0,1 \rbrace \) hàm ánh xạ tốt nhất từ \(\mathcal{X} \) sang \( \lbrace 0,1 \rbrace \) như sau:\[ f_{\mathcal{D} }(x) = \begin{cases} 1& \mbox{nếu } \mathbb{P}[y = 1 | x ] \geq 1/2 \\ 0& \textit{các trường hợp còn lại} \end{cases} \]
- Định nghĩa 3.3 (Học Agnostics PAC): Một tập giả thuyết \(\mathcal{H}\) là được coi là Agnostics 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} \times \mathcal{Y} \) thì 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}} (h) \leq \underset{ h’ \in \mathcal {H} }{\min L_{\mathcal D } (h’) } + \epsilon \]
UML3.2.2 Phạm vi áp dụng các mô hình học
- Các mô hình học có thể được áp dụng rất da dạng trong các bài toán. Sau đây là một số ví dụ về các bài toán:
- Phân lớp đa nhãn: Trong thực tế, nhiều bài toán phân nhãn không chỉ dừng lại ở phân nhãn 2 lớp. Ví dụ bài toán phân loại văn bản: Với một văn bản cho trước và cần xác định chủ đề của văn bản đó (chẳng hạn như: tin tức, thể thao, y tế, giáo dục,…). Mỗi chủ đề ở đây được hiểu là một lớp trong bài toán phân nhãn. Văn bản thường được biểu diễn bằng tập các đặc trưng (features) như số lượng từ khóa khác nhau trong văn bản, kích thước văn bản, nguồn gốc,…
- Hồi quy: Có nhiều bài toán đòi hỏi tìm mẫu (pattern) của dữ liệu – hàm quan hệ giữa \(\mathcal{X}\) và \(\mathcal{Y}\). Ví dụ: Tìm hàm tuyến tính dự đoán cân nặng của em bé dựa vào các phép đo trong siêu âm như: chu vi đầu, chu vi bụng, chiều dài xương đầu. Khi đó \(\mathcal{X} \) là tập con của \(\mathbb{R}^3 \) và \(\mathcal{Y}\) là tập các số thực (cân nặng theo gam). Lúc này, việc đánh giá hàm giả thuyết: \(h: \mathcal{X} \rightarrow \mathcal{Y} \) dựa trên trung bình bình phương sai số (expected square difference, mean square error) giữa cân nặng thực tế và cân nặng dự đoán từ giả thuyết: \[ L_{ \mathcal{D} }(h) = \underset{ (x, y) \sim \mathcal D} {\mathbb E} {(h(x) \mbox{ – } y)}^2.\qquad (3.2) \]
- Hàm lỗi tổng quát (Generalized Loss Functions): Để đánh giá giả thuyết \(h\) chúng ta sử dụng hàm lỗi. Tùy theo bài toán mà hàm mất mát này thay đổi theo.
- Hàm lỗi (loss function): Với bất kì tập \(\mathcal{H} \) (tập các giả thuyết) và miền Z, coi \(\ell \) là bất kì hàm ánh xạ từ \(\mathcal{H} \times Z \) sang tập các số thực không âm, \(\ell: \mathcal{H} \times Z \rightarrow \mathbb{R}_+ \) được gọi là hàm lỗi.
- Lưu ý: Trong các bài toán dự đoán thì \(Z = \mathcal{X} \times \mathcal{Y} \), tuy nhiên kí hiệu Z trong hàm lỗi có thể là bất kì miền nào. Ví dụ, trong bài toán học không giám sát (unsuprevised learning) thì Z không được lấy giá trị từ \(\mathcal{X} \) và \(\mathcal{Y} \).
- Hàm rủi ro (risk functinon): kì vọng lỗi của bộ phân nhãn, với \(h \in \mathcal{H} \) tương ứng với phân bố D trên Z: \[ L_{ \mathcal{D} }(h) = \underset{ z \sim \mathcal D} {\mathbb E} {[ \ell (h, z) ] }. \qquad (3.3) \]
- Hàm rủi ro thực nghiệm (empirical risk): kì vọng rủi ro trên tập dữ liệu huấn luyện \(S = (z_1,…, z_m) \in Z^m \) : \[ L_{S}(h) = \frac{1}{m} \sum_{i=1}^{m} \ell (h, z_i) . \qquad (3.4) \]
- Các hàm lỗi cho bài toán phân nhãn và hồi quy như sau:
Với một biến ngẫu nhiên z được lấy từ tập \(\mathcal{X} \times \mathcal{Y} \) ta có hàm lỗi như sau:
-
- 0-1 loss được được sử dụng trong các bài toán phân lớp: \[\ell_{0-1} (h, (x, y) ) = \begin{cases} 0 & \text{nếu } h(x) = y \\ 1 & \text{nếu } h(x) \neq y \end{cases} \]
- Square loss được sử dụng trong các bài toán hồi quy: \[\ell_{sq} (h, (x, y) ) = (h(x) \text{ – } y)^2 \]
- Từ đó ta có định nghĩa của học PAC với các hàm lỗi như sau:
Định nghĩa 3.4 (Học Agnostic PAC với hàm lỗi): Một tập giả thuyết \(\mathcal{H}\) là được coi là Agnostics PAC với miền Z và hàm lỗi \(\ell: \mathcal{H} \times Z \rightarrow \mathbb{R}_+ \) 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 Z thì 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}} (h) \leq \underset{ h’ \in \mathcal {H} }{\min L_{\mathcal D } (h’) } + \epsilon, \] trong đó \( L_{ \mathcal{D} }(h) = \underset{ z \sim \mathcal D} {\mathbb E} {[ \ell (h, z) ] }. \)
- Ghi chú 3.1 (Measurability): Trong các định nghĩa, \(\forall h \in \mathcal{H} \) chúng ta dùng hàm \(\ell(h, .) : Z \rightarrow \mathbb{R}_+ \) như một biến ngẫu nhiên và \( L_{ \mathcal{D} }(h) \) là giá trị kì vọng cho biến ngẫu nhiên này. Do vậy hàm \(\ell(h, .)\) là hàm measurable.
Giả sử có \(\sigma – algebra\) là tập con của Z được định nghĩa qua phân bố \(\mathcal{D} \) mà the preimage of every initial segment in \(R_+ \) is in this \(\sigma – algebra\). Trong bài toán phân lớp 2 nhãn với 0-1 loss, \(\sigma – algebra\) trên \(\mathcal{X} \times \lbrace 0, 1 \rbrace \) và giả định trên \(\ell \) là tương đương với giả định với mọi \(h\), tập \(\lbrace (x, h(x)) : x \in \mathcal{X} \rbrace \) trong \(\sigma – algebra\)
- Ghi chú 3.2 (Proper versus Representation-Independent Learning): Trong các định nghĩa trước thuật toán trả về một giả thuyết từ tập \(\mathcal{H} \) . Trong rất nhiều tình huống \(\mathcal{H} \) là tập con của \(\mathcal{H}’ \), do đó hàm mất mát được mở rộng trên \(\mathcal{H}’ \times Z \). Trong trường hợp này chúng ta có thể trả về một giả thuyết \(h’ \in \mathcal{H}’ \) sao cho điều kiện \(L_{\mathcal{D}} (h’) \leq \underset{ h \in \mathcal {H} }{\min L_{\mathcal D } (h) } + \epsilon, \) được thỏa mãn. Thuật toán mà trả về giả thuyết từ tập \(\mathcal{H}’ \) được gọi là học representation independent, trong khi việc học đúng phải trả về một giả thuyết \(h \in \mathcal{H} \). Học representation independent đôi khi còn được gọi là học không đúng cách (improper learning) mặc dù không có gì không đúng trong việc học.