- 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 \]
Skip to content