Sơ lược về Perceptron Learning Algorithm

Để tiếp nối các bài viết trước đây, tuần này em tiếp tục giới thiệu 1 trong những thuật toán cơ bản của Machine Learning - Perceptron Learning Algorithm (PLA), 1 thuật toán phân loại điển hình.

Do là 1 thuật toán đơn giản nên PLA chỉ hoạt động được trong 1 trường hợp rất cụ thể đó là dữ liệu chỉ có thể phân chia thành 1 trong 2 lớp, hơn nữa 2 lớp này phải là linearly separable (có thể phân chia tuyến tính hay nói cách khác là có thể dùng đường thẳng, mặt phẳng… để phân chia vùng được), ví dụ như trong hình sau:


Hình bên trái là ví dụ về dữ liệu phù hợp cho thuật toán PLA, ta nhận thấy là dữ liệu này có thể tồn tại đường thẳng giống trong hình bên phải để phân chia thành 2 loại dữ liệu, từ đó phân định được xem dữ liệu cần dự đoán (kí hiệu hình tam giác) được phân chia thành loại dữ liệu nào.

PLA chính là thuật toán đi tìm thành phần tuyến tính để phân chia vùng của 2 lớp dữ liệu sao cho toàn bộ dữ liệu thuộc lớp đều ở trong cùng 1 vùng. Tùy vào số chiều của dữ liệu mà thành phần tuyến tính cần tìm có thể là đường thẳng (2 chiều), mặt phẳng (3 chiều) hay siêu mặt phẳng (nhiều chiều).

“Sai đâu sửa đấy, cuối cùng sẽ thành công” chính là ý tưởng của thuật toán này. Về cơ bản ta sẽ cho tìm thử 1 nghiệm, nếu như không thỏa mãn, ta tiếp tục vòng lặp để cập nhật nghiệm đến 1 vị trí tốt hơn, cứ như thế cho đến khi tìm được nghiệm thật sự (cách làm này hoàn toàn có thể bởi bài toán này được chứng minh là có hữu hạn số lần thử, do đó luôn luôn tìm được nghiệm thật sự sau 1 khoảng thời gian lặp).

Để cho dễ hiểu thì trong ví dụ chúng ta sẽ xét dữ liệu có 2 chiều.
r
Giả sử đường thẳng w1*x1 + w2*x2 + w0 = 0 chính là nghiệm cần tìm như hình bên trên đây. Khi đó các điểm nằm cùng 1 vùng sẽ có giá trị w*x mang cùng dấu, ví dụ như vùng màu xanh thì giá trị đó của các điểm đều dương. Do vậy nếu ta dùng 1 nhãn y để phân loại dữ liệu x (y = 1 nếu x thuộc lớp 1 (lớp xanh) và y = -1 nếu x thuộc lớp 2 (lớp hồng)) thì nghĩa là nếu w*x >= 0 thì y = 1 và nếu w*x < 0 thì y = -1.

Vậy y = sgn(w*x) với sgn chính là hàm dấu, sgn(0) = 1.

Sau khi xác định được công thức của y ta đi tìm hàm mất mát và tối thiểu nó (Nhắc lại: hàm mất mát là hàm xác định độ lệch giữa giá trị dự đoán của ta và giá trị thực tế, và đương nhiên chúng ta muốn nó nhỏ nhất có thể).
t
Với cách làm là thử nghiệm 1 đường thẳng ban đầu có w bất kì, hầu như là chắc chắn ta sẽ có những điểm dữ liệu bị sai vùng như ở hình bên trên, vậy hàm mất mát ta xét chính là tổng số các điểm bị nhầm vùng này. Tuy nhiên việc xét hàm dấu khá khó khăn, ta sẽ xét hàm mất mát chính là tổng giá trị dữ liệu của các điểm bị nhầm vùng. Hàm mất mát mới này vẫn có giá trị tối thiệu giống hàm cũ (bằng 0 bởi ta phải chia sao cho không có dữ liệu nào nằm sai vùng). Đây là công thức của hàm mất mát:
x với M là tập các điểm bị nhầm vùng.
Ta áp dụng Stochastic Gradient Descent (SGD) để tối ưu hàm mất mát này, thay vì xét tất cả các điểm, ta chỉ xét từng điểm nhầm vùng 1 và cập nhật hệ số w của đường thẳng, và cứ xét như vậy cho đến khi tìm được w thỏa mãn, hay chính là tìm ra đường thẳng phân chia được dữ liệu đầu vào.

Tổng kết lại, PLA hoạt động như sau:

  1. Chọn ngẫu nhiên một vector hệ số w với các phần tử gần 0 (chọn ngẫu nhiên 1 đường thẳng).

  2. Duyệt ngẫu nhiên qua từng điểm dữ liệu x:

  • Nếu dữ liệu x được phân lớp đúng, tức sgn(w*x) = y, chúng ta không cần làm gì.
  • Nếu dữ liệu x bị nhầm vùng, cập nhật w theo công thức:w = w + y*x
  1. Kiểm tra xem có bao nhiêu điểm bị nhầm vùng. Nếu không còn điểm nào, dừng thuật toán. Nếu còn, quay lại bước 2.

Đây là hình ảnh minh họa thuật toán trong ví dụ ta vừa xét:
pla_vis

Có 1 điểm lưu ý là:
bn
Như ta thấy bên trên, có rất nhiều đường thẳng thỏa mãn phân chia dữ liệu thành 2 vùng đúng với 2 lớp, và các nghiệm này ảnh hưởng đến việc phân loại của dữ liệu mới cần xét, đây chính là 1 trong những khuyết điểm của PLA, bởi nó k xét đến đường thẳng đúng nhất phù hợp nhất, mà nó chỉ xét đến đường thẳng đúng mà nó tìm được đầu tiên, thuật toán sẽ dừng lại.

Hơn nữa, như ta đã biết, PLA yêu cầu rất khắt khe trong việc dữ liệu phải có thể phân chia tuyến tính, dù 1 trường hợp ngoại lệ cũng không. Do vậy có 1 thuật toán cải tiến của nó, tên là Pocket Algorithm, thuật toán này vẫn sẽ tìm thành phần tuyến tính để phân chia dữ liệu, tuy nhiên nó có thể làm với trường hợp có 1 số ít dữ liệu bị lẫn vào vùng khác (còn được gọi là nhiễu), giống như hình dưới đây:
z
Về cơ bản nó sẽ thêm 1 thứ gọi là Pocket (túi), và sẽ nhét số lượng nhiễu vào trong túi, chỉ thay đổi túi nếu số lượng nhiễu xét lúc sau nhỏ hơn ở trong túi. Đến cuối cùng khi hoàn thành thuật toán ta sẽ tìm được cách phân chia có ít nhiễu nhất. Nhờ Pocket Algorithm mà ta có thể khắc phục được 1 điểm yếu đáng kể của PLA.

Bài viết trên được tham khảo từ link: https://machinelearningcoban.com/2017/01/21/perceptron/