Month: October 2019

• 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.