- 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