Tag: PAC

UML 3.2.1 Mô hình học Agnostics PAC

This entry is part 2 of 3 in the series understanding machine learning chapter 3
  • 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.1 – Mô hình học PAC

This entry is part 1 of 3 in the series understanding machine learning chapter 3
  • 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    \]