Series: understanding machine learning chapter 2

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

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.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\).