Perceptron Learning Algorithm

Một trong những nhiệm vụ quan trọng nhất của ML là phân loại (tiếng Anh - classification).

Perceptron là thuật toán phân loại cho trường hợp đơn giản nhất khi có hai lớp. Nếu ta có các điểm dữ liệu cho trước trong không gian \(d\) chiều, ta muốn tìm một siêu phẳng (hình học affine gọi là \((d-1)\)-phẳng) chia các điểm dữ liệu đó thành hai phần. Sau đó khi có một điểm dữ liệu mới ta chỉ cần bỏ nó vào bên này hoặc bên kia của siêu phẳng.

Trong dạng này, mỗi điểm dữ liệu được biểu diễn ở dạng cột của ma trận. Giả sử các điểm dữ liệu là \(\bm{x}_1\), \(\bm{x}_2\), ..., \(\bm{x}_N\), với \(\bm{x}_i \in \mathbb{R}^d\), thì ma trận dữ liệu là

\[\bm{X} = \begin{pmatrix} \bm{x}_1^\top & \bm{x}_2^\top & \cdots & \bm{x}_N^\top \end{pmatrix}.\]

Ta gọi nhãn tương ứng với \(N\) điểm dữ liệu trên là vector \(\bm{y} = (y_1, y_2, \ldots, y_N)\) với \(y_i = 1\) nếu \(\bm{x}_i\) thuộc class xanh, và \(y_i = -1\) nếu \(\bm{x}_i\) thuộc class đỏ.

Một siêu phẳng có phương trình là

\[f_{\bm{w}} (\bm{x}) = w_0 + w_1 x_1 + \ldots + w_d x_d = \bm{w} \cdot \bm{x}^\top.\]

Một điểm thuộc nửa không gian (tạm gọi là bên này) đối với siêu phẳng thì \(f_{\bm{w}} (\bm{x}) < 0\), nếu thuộc nửa bên kia thì \(f_{\bm{w}} (\bm{x}) > 0\), nếu nằm trên phẳng thì bằng \(0\).

Gọi \(\mathrm{label} (\bm{x})\) là nhãn của điểm \(\bm{x}\). Khi đó điểm \(\bm{x}\) thuộc một trong hai bên của phẳng nên \(\mathrm{label} (\bm{x}) = \mathrm{sgn} (\bm{w} \cdot \bm{x}^\top)\) với \(\mathrm{sgn}\) là hàm dấu. Ta quy ước \(\mathrm{sgn} (0) = 1\).

Khi một điểm bị phân loại sai class thì ta nói điểm đó bị misclassified. Ý tưởng của thuật toán là làm giảm thiểu số lượng điểm bị misclassified qua nhiều lần lặp. Đặt

\[J_1 (\bm{w}) = \sum_{\bm{x}_i \in \mathcal{M}} (-y_i \cdot \mathrm{sgn} (\bm{w} \cdot \bm{w}_i^\top)),\]

trong đó \(\mathcal{M}\) là tập các điểm bị misclassified (tập này sẽ thay đổi theo \(\bm{w}\)).

Nếu \(\bm{x}_i\) bị misclassified thì \(y_i\) và \(\mathrm{sgn} (\bm{w} \cdot \bm{x}_i^\top)\) ngược dấu nhau. Nói cách khác, \(-y_i \cdot \mathrm{sgn} (\bm{w} \cdot \bm{x}_i^\top) = 1\). Từ đó \(J_1(\bm{w})\) là hàm đếm số lượng điểm bị misclassified. Ta thấy rằng \(J_1(\bm{w}) \geqslant 0\) nên ta cần tối ưu để hàm này đạt giá trị nhỏ nhất bằng \(0\). Khi đó không điểm nào bị misclassified.

Tuy nhiên có một vấn đề. Hàm \(J_1(\bm{w})\) là hàm rời rạc (hàm \(\mathrm{sgn}\)) nên rất khó tối ưu vì không thể tính đạo hàm. Do đó chúng ta cần một cách tiếp cận khác, một hàm mất mát khác tốt hơn.

Nếu ta bỏ đi hàm \(\mathrm{sgn}\) thì có hàm

\[J(\bm{w}) = \sum_{\bm{x}_i \in \mathcal{M}} (-y_i \cdot \bm{w} \cdot \bm{x}^\top).\]

Nhận xét. Một điểm bị misclassified nằm càng xa biên giới (siêu phẳng) thì giá trị \(\bm{w} \cdot \bm{x}_i^\top\) càng lớn, tức là hàm \(J\) đi ra xa so với giá trị nhỏ nhất. Hàm \(J\) cũng đạt min ở \(0\) nên ta cũng có thể dùng hàm này để loại bỏ các điểm bị misclassified.

Lúc này hàm \(J(\bm{x})\) khả vi nên ta có thể dùng GD hoặc SGD để tìm nghiệm cho bài toán.

Nếu xét tại một điểm thì

\[J(\bm{w}, \bm{x}_i, y_i) = -y_i \cdot \bm{w} \cdot \bm{x}_i^\top \Rightarrow \dfrac{\partial J}{\partial \bm{w}} = -y_i \bm{x}_i.\]

Khi đó quy tắc để cập nhật là \(\bm{w} = \bm{w} + \eta \cdot y_i \cdot \bm{x}_i\) với \(\eta\) là learning rate (thường chọn bằng \(1\)). Nói cách khác ta đang xây dựng dãy \(\{ \bm{w}_n \}\) hội tụ lại nghiệm bài toán với công thức \(\bm{w}_{i+1} = \bm{w}_i + \eta \cdot y_i \cdot \bm{x}_i\).

Thuật toán Perceptron Learning Algorithm (PLA) có thể được mô tả như sau:

  1. Chọn ngẫu nhiên vector \(\bm{w}\) với \(w_i\) xấp xỉ \(0\).

  2. Duyệt ngẫu nhiên qua các \(\bm{x}_i\):

    • nếu \(\bm{x}_i\) được phân lớp đúng, tức \(\mathrm{sgn} (\bm{w} \cdot \bm{x}_i^\top) = y_i\) thì ta không cần làm gì;

    • nếu \(\bm{x}_i\) bị misclassified, ta cập nhật \(\bm{w}\) theo công thức \(\bm{w} = \bm{w} + \eta \cdot y_i \cdot \bm{x}\).

  3. Kiểm tra xem có bao nhiêu điểm bị misclassified. Nếu không còn điểm nào thì ta dừng thuật toán, ngược lại thì quay lại bước 2.