UML3.2.2 Phạm vi áp dụng các mô hình học

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

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    \]

UML2.3 – Cực tiểu hóa sai số thực nghiệm trên không gian giả thiết rút gọn

This entry is part 3 of 3 in the series understanding machine learning chapter 2
  • Như đã được trình bày trong phần trước, nguyên tắc cực tiểu hóa sai số thực nghiệm (ERM) có thể dẫn đến hiện tượng overfitting , vì vậy chúng ta cần một số cải tiến cho thuật toán học sử dụng luật ERM. Chúng ta sẽ tìm kiếm hàm dự đoán từ luật ERM mà không dẫn tới hiện tượng overfitting, tức là hàm dự đoán này hoạt động tốt trên cả tập huấn luyện và trên phân bố dữ liệu \(\mathcal D\).
    Một cách làm phổ biến là xây dựng không gian giả thuyết rút gọn và cho thuật toán tìm hàm giả thuyết tối ưu trong không gian đó. Không gian này gọi là lớp các hàm giả thuyết (hypothesis class), kí hiệu là \(\mathcal H\). Mỗi hàm \(h \in \mathcal H\) là hàm ánh xạ \(\mathcal X\) đến \(\mathcal Y\).
  • Ví dụ: một cách rút gọn không gian giả thuyết hay dùng là: trong tất cả các hàm dự đoán, ta chỉ tìm các hàm dự đoán dạng ngưỡng tuyến tính \(\mathcal H = \{w\cdot x + b \geq 0, w \in \mathbb R^n, b\in \mathbb R\}\)
  • Cho lớp các hàm dự đoán \(\mathcal H\) và bộ dữ liệu huấn luyện \(S\), thuật toán học \(\mathit{ERM}_{\mathcal H}\) sẽ sử dụng luật ERM chọn hàm dự đoán \(h \in \mathcal H\) sao cho lỗi trên bộ huấn luyện \(S\) là nhỏ nhất:

    \(\begin{align} \mathit{ERM}_{\mathcal H}(S) \in \underset{h \in \mathcal H}{\arg\min L_S(h)} \end{align}\)

    Ta sử dụng kí hiệu \(h_{\mathcal{S}}\) cho kết quả hàm giả thiết sau khi áp dụng \(ERM_{\mathcal{H}}\), như vậy \(h_{\mathcal{S}} \in \underset{h \in \mathcal H}{\arg\min\ L_S(h)} \) .

  • Định nghĩa 2.1 (Giả thuyết tính khả thi – realizability) :
    Tồn tại \(h^* \in \mathcal H\) sao cho \(L_{\mathcal D, f}(h^*) = 0\). Giả định này giả định rằng với tập dữ liệu \(\mathcal S\), được lấy mẫu từ phân phối \(\mathcal D\) và được đánh nhãn bởi hàm \(f\) thì \(L_{S}(h^*) = 0\), vì \(h^*\) đã dự đoán đúng hết trên cả phân phối của dữ liệu.
    Giả thuyết trên ngụ ý rằng, với mọi giả thuyết ERM ta đều có thể có được \(L_S(h_S) = 0\). Tuy nhiên chúng ta quan tâm đến rủi ro thực tế của \(h_S\), \(L_{(\mathcal D, f)}(h_S)\) chứ không phải là lỗi thực nghiệm trên tập huấn luyện.
  • Giả thuyết tất cả các dữ liệu được lấy mẫu độc lập với nhau trong tập \(\mathcal D\) – i.i.d. assumption. \(S \mbox{~} \mathcal D^m\) với \(m\) là  số lượng mẫu học có \(S\), ta kí hiệu \(\mathcal D^m\) là xác suất của \(S\) gồm \(m\) mẫu học được chọn độc lập với nhau.
    Như vậy tập \(S\) như một cửa sổ nhỏ để ta nhìn được một phần phân bố của dữ liệu học, cửa số càng to đồng nghĩa với tập \(S\) càng lớn thì việc học của ta càng sát với dữ liệu thực.
  • Khi ta chọn tập \(S\), sẽ có một xác suất nào đó để tập \(S\) được chọn không phản ánh hay thể hiện đúng phân phối \(\mathcal D\). Ta kí hiệu \(\delta\) là xác suất để chọn một tập học không phản ánh đúng phân phối dữ liệu như vậy và \(1-\delta\) đại diện cho sự tự tin của ta đối với hàm dự đoán \(h_S\). Ta kí hiệu \(\epsilon\) tượng trưng cho độ chính xác của mô hình dự đoán, khi đó nếu \(L_{\mathcal D, f}(h_S) < \epsilon\) chứng tỏ hàm dự đoán thu được hoạt động tốt, có thể chấp nhận dùng \(h_S\), ngược lại, nếu \(L_{\mathcal D, f}(h_S) > \epsilon \) chứng tỏ việc học thất bại.
  • Ta cần tìm xác suất cận trên của việc lấy mẫu \(m\) dữ liệu dẫn đến việc học thất bại. Giả sử, \(S|_x= (x_1, …, x_m)\) là một tập dữ liệu huấn luyện. Vậỵ ta cần tìm :

    \(\mathcal D^m(\{S|_x : L_{(\mathcal D, f)}(h_S) > \epsilon\})\)

  • Giả sử \(\mathcal H_B\) là tập các hàm giả thiết cho kết quả kém:

    \(\mathcal H_B = \{h \in \mathcal H | L_{(\mathcal H, f)}(h) > \epsilon\}\)

  • \(M = \{S|_x : \exists h \in \mathcal H_B, L_S(h) = 0\}\) là tập các bộ dữ liệu huấn luyện có thể lừa thuật toán học (misleading set), ta có \(\{S|_x: L_{(\mathcal D, f)}(h_S)> \epsilon \}\subseteq M\).
    Vậy : \(\mathcal D^m(\{S|_x: L_{(\mathcal D, f)}(h_S)> \epsilon\}) \leq \mathcal D^m(M) = \mathcal D^m(\{S|_x: \exists h \in \mathcal H_B, L_S(h)=0\})\) (1)
  • Ta có \(M = \cup_{h \in \mathcal H_B}\{S|_x: L_S(h)=0\}\)
    Suy ra, \(\mathcal D^m(M) = \mathcal D^m( \cup_{h \in \mathcal H_{\mathcal B}}\{S|_x: L_S(h)=0\})\).
    Theo Union Bound, \(\mathcal D(A \cup B) \leq \mathcal D(A) + \mathcal D(B)\), nên ta có :
    \( \mathcal D^m( \cup_{h \in \mathcal H_B}\{S|_x: L_S(h)=0\}) \leq \sum_{h \in \mathcal H_B} \mathcal D^m(\{S|_x: L_S(h) = 0\})\) (2)
    Vì \(S_x\) là tập \(m\) mẫu huấn luyện, nên để \(L_S(h) = 0\) khi và chỉ khi \(h\) dự đoán đúng trên từng mẫu \(x_i\). Hay :
    \(\mathcal D^m(\{S|_x: L_S(h) = 0\}) = \prod_{i=1}^m\mathcal D(\{x_i: h(x_i)=f(x_i)\})\)
    Hơn nữa, \(\mathcal D(\{x_i: h(x_i)=f(x_i)\}) = 1 – L_{\mathcal D, f}(h) \leq 1 – \epsilon\), nên: \(\mathcal D^m(\{S|_x: L_S(h) = 0\}) \leq (1-\epsilon)^m\) (3)
    Từ (1), (2) và (3): \(\mathcal D^m(\{S|_x: L_{(\mathcal D, f)}(h_S) > \epsilon \}) \leq |\mathcal H_B| (1- \epsilon)^m\leq |\mathcal H| (1- \epsilon)^m \leq |\mathcal H| e^{-m\epsilon}\)
  • Để thuật toán \(\mathit{ERM}_{\mathcal H}\) có độ tự tin cao, ta cho vế phải chặn trên bởi \(\delta\), suy ra khi
    \[m\geq \frac{\log(|\mathcal H|/\delta)}{\epsilon}\]
    thì với xác suất nhỏ hơn \(\delta\), thuật toán \(\mathit{ERM}_{\mathcal H}\) tìm ra hàm dự đoán \(h_S\) kém, tức là có rủi ro kỳ vọng \(L_{\mathcal D,f}(h_S) > \epsilon\).
  • Hay nói ngược lại, khi số mẫu dữ liệu
    \[m\geq \frac{\log(|\mathcal H|/\delta)}{\epsilon}\]
    thì với độ tự tin ít nhất \(1-\delta\), thuật toán \(\mathit{ERM}_{\mathcal H}\) cho hàm dự đoán \(h_S\) tốt, tức là có rủi ro kỳ vọng \(L_{\mathcal D,f}(h_S) < \epsilon\)
  • Trong chương này, ta giả sử không gian giả thuyết rút gọn \(\mathcal H\) là hữu hạn. Tuy nhiên, từ các công thức trên, có thể thấy số mẫu dữ liệu cần thiết tỉ lệ thuận với \(\log |\mathcal H|\), tức là rất nhỏ so với tổng số giả thiết của \(\mathcal H\).

 

UML2.2 – Nguyên tắc cực thiểu rủi ro thực nghiệm

This entry is part 2 of 3 in the series understanding machine learning chapter 2
    • Như chương trước đã đề cập, thuật toán học dựa vào tập dữ liệu \(S\) được lấy mẫu từ tập \(\mathcal D\) và được đánh nhãn bởi hàm \(f\), thuật toán này sẽ cho đầu ra là hàm \(h_S: \mathcal{X} \rightarrow \mathcal{Y}\) (kí hiệu \(h_S\) nhấn mạnh hàm dự đoán \(h_S\) chỉ phụ thuộc vào bộ dữ liệu \(S\)). Mục tiêu là cần tìm hàm \(h_S\) cực tiểu sai số của dữ liệu được sinh ra từ phân phối \( \mathcal D\) và hàm đánh nhãn \(f\).
    • Do ta không biết được phân phối \(\mathcal D\) cũng như hàm đánh nhãn \(f\) vì thế chúng ta không thể tính được lỗi thật \(L_{D, f}\). Do đó để xấp xỉ, ta sử dụng lỗi trên tập dữ liệu huấn luyện (training error) để tính toán lỗi cho hàm dự đoán:

      \(\begin{align}L_S(h) = \frac{|i \in [m] : h(x_i) \neq y_i|}{m}\end{align}\)

      với \( [m] = \{1, \ldots, m\} \). Lỗi này còn được gọi là lỗi thực nghiệm (empirical error) hay rủi ro thực nghiệm (empirical risk). Vì tập dữ liệu huấn luyện được lấy mẫu trên phân bố thực tế \(\mathcal D\), cực tiểu hóa \(L_S(h)\) có thể làm giảm rủi ro kỳ vọng \(L_{D, f}\). Nguyên tắc này được gọi là cực tiểu rủi ro thực nghiệm, viết tắt là ERM (Empirical Risk Minimization).

    • Mặc dù luật ERM có vẻ rất hợp lý, nhưng nếu sử dụng nó một cách bất cẩn, ta có thể gặp phải những lỗi sai lớn. Ví dụ, giả sử có bài toán dự đoán đu đủ xem một quả đu đủ đã chín hay chưa dựa vào 2 yếu tố (features) là độ mềm (softness) và màu sắc (color). Giả sử dữ liệu dữ liệu được mô tả như dưới hình vẽ sau:

      Giả sử phân phối \(\mathcal D\) là các dữ liệu được phân bố đều trong ô màu xám, hàm \(f\) gán nhãn 1 cho tất cả dữ liệu nằm trong hình vuông nét đứt (các điểm màu xanh), còn nhãn 0 là những điểm dữ liệu còn lại (màu đỏ). Diện tích hình vuông nét liền là 2, diện tích hình vuông nét đứt là 1. Nếu ta có hàm dự đoán \(h_S\) như sau:

      \(\begin{align}h_S(x) = \begin{cases} y_i & \mbox{nếu } \exists i \in [m] \mbox{ sao cho } x_i = x \\ 0 & \mbox{các trường hợp còn lại}\end{cases} \end{align}\)

    • Như vậy với bất kì mẫu \(S\) nào, hàm dự đoán \(h_S\) luôn có sai số trên tập huấn luyện \(S\) là 0. Theo nguyên tắc ERM, ta có thể chọn hàm dự đoán này vì hàm này có sai số thực nghiệm nhỏ nhất. Nhưng trên toàn bộ phân phối \(\mathcal D\) lỗi thực (rủi ro kỳ vọng) được tính trên những điểm dữ liệu có nhãn là 1, như vậy trong trường hợp này sai số thực tế là 1/2 (vì dữ liệu được phân bố đều).
    • Như vậy, trong trường hợp trên, hàm dự đoán hoạt động rất tốt trên tập huấn luyện, nhưng trên bộ dữ liệu thực tế thì hoạt động rất kém, hay còn gọi thuật toán học bị học quá (overfitting).

UML2.1 – Học thống kê

This entry is part 1 of 3 in the series understanding machine learning chapter 2

Học thống kê

  • Đầu vào của bộ học (learner):
    • Miền giá trị đầu vào (input): \(\mathcal{X}\)
    • Miền giá trị nhãn (label): \(\mathcal{Y}\). Ví dụ: \(\mathcal{Y} = \{0,1\}\), \(\mathcal{Y} = \{-1,+1\}\), \(\mathcal{Y} = \{0,1,2,3,4,5,6,7,8,9\}\), \(\mathcal{Y} = \mathbb{R}^+\)
    • Dữ liệu huấn luyện (training data, training set): \(S = ((x_1, y_1),\ldots,(x_m, y_m))\) với mỗi mẫu huấn luyện (training example) \((x_i, y_i)\in\mathcal{X}\times\mathcal{Y}\)
  • Đầu ra của bộ học: một ánh xạ hoặc hàm \( h: \mathcal{X}\rightarrow \mathcal{Y} \). Ánh xạ này được gọi là giả thuyết (hypothesis) hoặc hàm dự đoán (predictor) hoặc bộ phân lớp (classifier)
  • Mô hình sinh dữ liệu: Trong học thống kê, ta giả sử dữ liệu được sinh ra từ một mô hình (phân bố) xác suất nào đó mà bộ học không biết trước. Ví dụ, dữ liệu đầu vào có phân bố \(\mathcal{D}\), còn giá trị nhãn được sinh bởi một hàm sinh nhãn \(y = f(x)\) sao cho \(y_i = f(x_i)\). Như vậy, mỗi mẫu huấn luyện sẽ được lấy mẫu \(x_i\) từ phân bố \(\mathcal D\) và tính \(y_i = f(x_i)\).
  • Độ đo đánh giá hàm dự đoán: Lỗi của hàm dự đoán được đánh giá bằng xác suất xảy ra lỗi khi dự đoán trên phân bố \(\mathcal D\). Tức là \[L_{D,f}(h) = \underset{x \sim \mathcal D}{\mathbb P} [h(x)\neq f(x)].\]Đánh giá \(L_{D,f}(h)\) được gọi là lỗi thật (true error) hoặc lỗi tổng quát (generalization error) hoặc rủi ro kỳ vọng (expected risk).
  • Nhiệm vụ của bộ học: Bộ học không được biết phân bố \(\mathcal D\) và hàm sinh nhãn \(f\). Nhiệm vụ của nó là từ tập huấn luyện \(S\) tìm ra một giả thuyết \(h\) tốt nhất có thể được theo nghĩa tối thiểu hóa rủi ro kỳ vọng \(L_{D,f}(h)\).

Ví dụ 1

Để phân biệt cam và chanh ta có thể dựa vào hai đặc trưng là kích thước (size) là đường kính của quả và màu sắc (color) của quả. Bảng sau cho thấy một bộ dữ liệu huấn luyện

001.orange_lemon.csv

 size (cm)colortype
7yelloworange
8yelloworange
4yelloworange
5greenlemon
4greenlemon
3greenlemon

Ví dụ 2

Trên thực tế, hiếm khi có thể phân biệt rõ ràng màu sắc của các loại hoa quả. Khi ghi nhận trên máy ảnh kỹ thuật số, mỗi màu được mô tả bằng ba số nguyên từ 0 đến 255 đại diện cho ba kênh màu Đỏ (red), Xanh lục (green), Xanh da trời (blue). Các mẫu huấn luyện ở ví dụ trên có thể trở thành bảng sau (+1 là orange, -1 là lemon)

002.orange_lemon.csv

 size (cm)redgreenbluetype
720024220+1
823019434+1
419421544+1
53220120-1
43519219-1
32724031-1