1 Thuật toán Perceptron (PLA)

PLA là thuật toán classification nền tảng của các model Neuron Network và deeplearning. Ý tưởng cơ bản của thuật toán đó là với các classes khác nhau, hãy tìm các đường biên để phân chia các classes này thành những vùng diện tích tách biệt. Trường hợp đơn giản nhất của thuật toán này là phân chia nhị phân (binary classification) bằng những đường biên tuyến tính. Bài toán được phát biểu như sau: Cho 2 class được dán nhãn khác nhau, tìm một đường thẳng sao cho toàn bộ các điểm thuộc class 1 nằm về 1 phía của đường thằng và toàn bộ các điểm thuộc class 2 sẽ nằm về phía còn lại với giả định luôn tồn tại 1 đường thẳng như thế (không rơi vào trường hợp 2 class nằm chồng lấn lên nhau dẫn tới không tồn tại đường biên).

Cũng giống như các thuật toán của machine learning, PLA cũng đi tìm biên phân chia bằng cách tối thiểu một hàm mất mát. Việc xây dựng hàm mất mát của PLA phải thỏa mãn hàm số phải khả vi (nhằm mục đích có thể tính được đạo hàm bậc nhất) và từ đó sử dụng gradient descent để tìm nghiệm global minimum.

2 Phát biểu toán học

Giả sử \(\mathbf{X} = [\mathbf{x}_{1},\mathbf{x}_{2},...,\mathbf{x}_{N}] \in \mathbb{R}^{d \times N }\) là matrix chứa các cột \(\mathbf{x}_{i} \in \mathbb{R}^{d \times 1}\) là các quan sát trong không gian d chiều. Các điểm được gán nhãn \(y=[y_{1},y_{2},\dots,y_{N}] \in \mathbb{R}^{1 \times N}\) với \(y_{i} = 1\) nếu thuộc class 1 và \(y_{i} = -1\) nếu thuộc class 2. Tại một thời điểm phương trình đường thẳng biên có dạng:

\[\begin{eqnarray} f_{\mathbf{w}}(\mathbf{x}) &=& w_{1}x_{1} + w_{2}x_{2}+\dots + w_{d} x_{d} + w_{0} \\ & = & \mathbf{w}^{T}\mathbf{x} = 0 \end{eqnarray}\]

Trong đó \(\mathbf{w}^{T}=[w_{1},w_{2},\dots,w_{N}]\) là vector chuyển vị của vector hệ số. Từ phương trình đường thẳng biên ta sẽ xác định được dấu của một điểm dữ liệu \(\mathbf{x_i}\) bất kì. nếu \(f_{\mathbf{w}}(\mathbf{x_i}) \geq 0\) thì \(y_i\) sẽ được gán nhãn là 1. Trái lại nếu \(f_{\mathbf{w}}(\mathbf{x_i}) < 0\) thì \(y_i\) sẽ được gán nhãn là -1. Ta gọi phương trình xác định dấu của \(\mathbf{x_i}\) như sau:

\[sign(\mathbf{x_i}) = 1 \space nếu \space f_{\mathbf{w}}(\mathbf{x_i}) \geq 0 \\\] \[sign(\mathbf{x_i}) = -1 \space nếu \space f_{\mathbf{w}}(\mathbf{x_i}) < 0\]

Mục đích của chúng ta là xây dựng được một đường thẳng biên sao cho số điểm bị phân loại sai là ít nhất có thể. Do đó khi xây dựng hàm mất mát chỉ cần quan tâm đến những điểm bị phân loại sai. Gọi \(\mathcal{M}\) là tợp hợp những điểm bị phân loại sai. Khi đó dấu của nó với nhãn thực sự của phương trình biên là trái nhau. Hay nói cách khác \(y_i.sign(\mathbf{x_i}) = -1\). Phương trình hàm mất mát có dạng \[J(\mathbf{w}) = \sum_{\mathbf{x_i} \in \mathcal{M}} -y_i.sign(\mathbf{x_i}) \]

Chúng ta phải đổi dấu của \(y_i.sign(\mathbf{x_i})\) là để hàm \(J(\mathbf{w})\) đạt giá trị nhỏ nhất khi số điểm bị phân loại nhầm là nhỏ nhất. Tuy nhiên ta nhận thấy rằng xét trên tập hợp các điểm bị phân loại nhầm \(\mathcal{M}\) thì hàm \(J(\mathbf{w})\) không liên tục tại mỗi điểm \(\mathbf{x_i}\) (chỉ nhận 2 giá trị là -1 và 1). Do đó không thể sử dụng \(J()\) để tối ưu hóa hàm số theo gradient descent. Chúng ta phải chuyển sang một hàm tối ưu khác tạm gọi là \(J_{1}()\) như sau: \[J_{1}(\mathbf{w}) = \sum_{\mathbf{x_i} \in \mathcal{M}} -y_i.\mathbf{w}^T\mathbf{x_i} \] Hàm \(J_{1}()\) ưu việt hơn \(J()\) ở chỗ với mỗi điểm bị phân loại nhầm sẽ được đánh trọng số bằng khoảng cách của nó với đường thẳng biên (\(\mathbf{w}^T\mathbf{x_i}\)). Do đó \(J_{1}()\) sẽ phạt rất nặng những điểm nằm lấn sâu sang biên giới của class khác trong khi \(J()\) sẽ đánh đồng tất cả các điểm bị phân loại nhầm với trọng số bằng 1. Và hơn nữa \(J_{1}()\) là hàm tuyến tính liên tục và khả vi đối với \(\mathbf{w}\) nên ta hoàn toàn có thể đi theo gradient descent tại một điểm \(\mathbf{x_i}\) để xác định global minimum. Hàm gradient descent tại điểm \(\mathbf{x_i}\) được tính như sau:

\[\nabla_{\mathbf{w}}J(\mathbf{w}; \mathbf{x}_i; y_i) = -y_i\mathbf{x}_i\] Và sau mỗi vòng lặp thì \(\mathbf{w}\) sẽ được cập nhật: \[\mathbf{w}_{t+1} = \mathbf{w}_{t} + \eta \space y_i\mathbf{x_i}\]

Trong đó \(\eta\) là learning rate có giá trị lớn hơn 0. Lưu ý rằng:

\[\begin{eqnarray}\mathbf{w_{t+1}}^{T}\mathbf{x_i} &=& (\mathbf{w_t} + \eta \space y_{i}\mathbf{x_i})^{T} \mathbf{x_i} \\&=& \mathbf{w_t}^{T}\mathbf{x_i} + \eta \space y_i\mathbf{x_i}^{T}\mathbf{x_i} \\ &=& \mathbf{w_t}^{T}\mathbf{x_i} + \eta \space y_{i} ||\mathbf{x_i}||_{2}^{2} \end{eqnarray}\] Trong trường hợp \(\mathbf{w_t}^{T}\mathbf{x_i} \geq 0\) do \(\mathbf{x_i}\) bị phân loại sai nên \(y_{i} = -1\) kết hợp với \(\eta \geq 0\) và \(||\mathbf{x_i}||_{2}^2 \geq 0\) Ta suy ra  \[\mathbf{w_t}^{T}\mathbf{x_i} \geq \mathbf{w_t}^{T}\mathbf{x_i} + \eta \space y_{i}||\mathbf{x_i}||_{2}^2 = \mathbf{w_{t+1}}^{T}\mathbf{x_i} \]

Điều đó có nghĩa là sau khi cập nhật theo công thức trên thì \(\mathbf{w}\) luôn đi theo hướng làm cho điểm bị phân loại sai giảm khoảng cách đối với biên, tức là đi về phía lớp được phân loại đúng. Điều tương tự cũng xảy ra đối với \(\mathbf{w_t}^{T}\mathbf{x_i} < 0\)

Đến đây ta có thể hình dung được phần nào về ý tưởng của thuật toán PLA. Ban đầu thuật toán chấp nhận biên mà tại đó điểm bị phân loại sai và tìm cách điều chỉnh biên này về hướng điểm bị phân loại sai nhằm mục đích kéo điểm đó về đúng class của nó. Quá trình này sẽ lặp lại đến một lúc nào đó toàn bộ các điểm đều phân loại đúng vào lớp của nó với giả định rằng luôn tồn tại 1 biên như vậy.

Một câu hỏi đặt ra là có khi nào thuật toán sẽ không hội tụ đến biên phân chia không? Điều này có nghĩa rằng luôn tồn tại một điểm \(\mathbf{x_i}\) sao cho thuật toán bị phân loại sai. Giả định \(\mathbf{w^*}\) là nghiệm của hàm mất mát và không đi qua bất kì một điểm nào (Do ban đầu ta đã giả định là luôn tìm được 1 đường thẳng phân chia 2 class tách biệt nhau). Xét một chuỗi \(u_{\alpha}(t)\) không âm có phương trình \[u_{\alpha}(t+1) = ||\mathbf{w_{t+1}}-\alpha \mathbf{w^*}||_{2}^2 \space (1)\] Trong đó \[\mathbf{w}_{t+1} = \mathbf{w}_{t} + \space y_i\mathbf{x_i} \space (2)\]

Và \(\alpha\) là tham số do ta lựa chọn. Ta sẽ chứng minh \(u_{\alpha}(t)\) là chuỗi giảm và bị chặn dưới. Thay (2) vào (1) ta có: \[\begin{eqnarray} &&u_{\alpha}(t+1) = ||\mathbf{w_t}+y_i \space \mathbf{x_i} - \alpha \mathbf{w^*}||_{2}^2 \\ &=& ||\mathbf{w_t} - \alpha \mathbf{w^*}||_2^2 + 2\space (\mathbf{w_t}-\alpha\mathbf{w^*})^{T} y_i\mathbf{x_i}+ ||y_i\mathbf{x_i}||_2^2 \\ &=& u_{\alpha}(t) + 2\space y_i\mathbf{w_t}^{T} \mathbf{x_i} -2\space \alpha y_i\mathbf{w^*}^{T} \mathbf{x_i} + ||y_i\mathbf{x_i}||_2^2 \end{eqnarray}\]

Tại điểm \(\mathbf{x_i}\) ta có:
\(y_i \space \mathbf{w^*}^T\mathbf{x_i} > 0\) (do \(\mathbf{w^*}\) phân loại đúng mọi điểm và biên có hệ số \(\mathbf{w^*}\) không đi qua \(\mathbf{x_i}\))
\(y_i \space \mathbf{w_t}^T\mathbf{x_i} < 0\) (do \(\mathbf{x_i}\) bị phân loại sai).
Do đó:

\[\begin{eqnarray} &&u_{\alpha}(t+1) \leq u_{\alpha}(t) -2\space \alpha y_i\mathbf{w^*}^{T} \mathbf{x_i} + ||y_i\mathbf{x_i}||_2^2 \end{eqnarray}\]

Đặt \(||y_i\mathbf{x_i}||_2^2 = \beta^2\) , \(y_i\mathbf{w^*}^{T} \mathbf{x_i} = \gamma\) , \(\alpha = \frac{\beta^2}{\gamma}\). Suy ra:

\[\begin{eqnarray} &&0 < u_{\alpha}(t+1) \leq u_{\alpha}(t) -2\space \alpha y_i\mathbf{w^*}^{T} \mathbf{x_i} + ||y_i\mathbf{x_i}||_2^2 \\ &=& u_{\alpha}(t) -2\space \alpha \gamma + \beta^2\\ &=& u_{\alpha}(t) - \beta^2 < u_{\alpha}(t) \end{eqnarray}\]

\(u_{\alpha}(t)\) là chuỗi giảm không âm và bị chặn dưới nên hội tụ về 0. Do đó:

\[\begin{eqnarray}&&\lim \limits_{t \rightarrow \infty}{u_{\alpha}(t)} = \lim \limits_{t \rightarrow \infty}{||\mathbf{w_t}-\alpha \mathbf{w^*}||_{2}^2} = 0 \\ &\Rightarrow&\lim \limits_{t \rightarrow \infty}{\mathbf{w_t}} = \alpha\lim \limits_{t \rightarrow \infty}{\mathbf{w^*}} \end{eqnarray}\]

Tức là khi số vòng lặp là vô hạn thì \(\mathbf{w^*}\) luôn hội tụ về nghiệm và khi đó tất cả các điểm đều được phân loại đúng class của nó trong điều kiện giả định rằng luôn tồn tại đường biên phân loại đúng.

3 Tóm tắt các bước chính của PLA

Bước 1: Chọn một vector hệ số khởi tạo \(\mathbf{w}\) và xác định biên.

Bước 2: Xác định các điểm bị phân lớp sai. Từ đó update lại vector hệ số khởi tạo \(\mathbf{w}\) theo phương Gradient descent của lần lượt các điểm dữ liệu \(\mathbf{x_i}\) nằm trong tợp hợp phân lớp sai \(\mathcal{M}\)

Bước 3: Kiểm tra các điểm dữ liệu sau khi update đường biên đã được phân vào đúng lớp. Nếu vấn tồn tại điểm bị phân lớp sai thì lặp lại bước 2.

4 Ví dụ về thuật toán PLA:

Bên dưới ta sẽ tạo ngẫu nhiên 40 điểm dữ liệu thuộc 2 class là 1 và -1 tách biệt nhau (nghĩa là luôn tồn tại một đường thẳng phân chia các điểm dữ liệu này về đúng 2 class tương ứng).

library(ggplot2)
library(tidyverse)
library(dplyr)
library(MASS)
set.seed(123)
cov <- matrix(c(0.2,0,0,0.2), ncol = 2)
mean_1 <- c(2,2)
mean_2 <- c(4,4)

#Khởi tạo 2 class C1, C2 có trung bình là các mean_1,2 và matrix covariance bằng nhau và bằng cov

C1 <- mvrnorm(n = 20, mu = mean_1, Sigma = cov)
C2 <- mvrnorm(n = 20, mu = mean_2, Sigma = cov)

data <- data.frame(C1) %>% mutate(label = 1) %>% 
  rbind(data.frame(C2) %>% mutate(label = -1))

head(data)
#Visualization 2 class này
data %>% mutate(label = as.character(label)) %>% ggplot() + 
  geom_point(aes(x = X1, y = X2, color = label, shape = label)) +
  xlim(0,6) +
  ylim(0,6)

Các hàm được sử dụng:

f_sign : Trả về dấu của các điểm dữ liệu dựa trên vector hệ số \(\mathbf{w}\).

f_converged : Kiểm tra điều kiện hội tụ dựa trên nhãn của các điểm dữ liệu sau khi update \(\mathbf{w}\). Trả về giá trị TRUE nếu tất cả các điểm được phân loại đúng và FALSE nếu vẫn tồn tại điểm bị phân loại sai.

f_perceptron : Hàm chính chứa vòng lặp để tìm biên phân loại đúng các class.

y <- data$label
X <- rep(1, nrow(C1)) %>% cbind(.,rbind(C1, C2)) %>% t()

f_sign <- function(X, w){
  t(w) %*% X %>% sign()
}

f_converged <- function(X, y, w){
  label = f_sign(X, w)
  all(label == y)
}

f_perceptron <- function(X, y, w_init){
  w_list <- w_init
  mis_points <- matrix()
  epochs = 0
  while(TRUE){
    epochs = epochs + 1
    mix_index = sample(1:ncol(X), ncol(X), replace = FALSE)
    for (i in 1:ncol(X)){
      Xi = matrix(X[,mix_index[i]], nrow = nrow(X))
      yi = y[mix_index[i]]
      w = w_list[,ncol(w_list)]
      #Check những điểm misclassify
      if(f_sign(Xi, w) != yi){
        mis_points <- rbind(mis_points, mix_index[i])
        #Update w
        w_new = w + yi*Xi
        w_list <- cbind(w_list, w_new)
      }
    }
    if(f_converged(X, y, w_new)) {break}
  }
  return(list(w_list = w_list, epochs = epochs, mis_points = mis_points))
}

#Khởi tạo vector hệ số
w_init <- matrix(c(1,1,1))
result <- f_perceptron(X, y, w_init)

Kết quả các lần update \(\mathbf{w}\) cho thấy xuất phát từ w_init cần tới 35 vòng lặp thì mới hội tụ đến biên phân loại đúng.

result$w_list
##      [,1]      [,2]       [,3]      [,4]      [,5]       [,6]      [,7]
## [1,]    1  0.000000  1.0000000 2.0000000  1.000000  2.0000000 3.0000000
## [2,]    1 -2.830220 -1.2229333 0.3767543 -3.487504 -1.5560941 0.9528962
## [3,]    1 -2.689318 -0.6398188 1.5394117 -1.958319 -0.5240715 1.1687586
##           [,8]        [,9]    [,10]     [,11]      [,12]    [,13]
## [1,]  2.000000  3.00000000  2.00000  3.000000  4.0000000 5.000000
## [2,] -3.354791 -0.60047839 -5.14640 -3.118712 -1.4266815 1.032162
## [3,] -2.730274  0.03672681 -4.22472 -3.104218 -0.3050865 2.391989
##          [,14]     [,15]     [,16]     [,17]       [,18]     [,19]
## [1,]  4.000000  5.000000  4.000000  5.000000  6.00000000  5.000000
## [2,] -3.285003 -1.187521 -4.270695 -1.811852 -0.05957183 -4.376736
## [3,] -2.220068 -0.323007 -4.285723 -1.588648  0.63399784 -3.978060
##          [,20]      [,21]     [,22]     [,23]      [,24]     [,25]
## [1,]  6.000000  7.0000000  6.000000  7.000000  8.0000000  7.000000
## [2,] -2.751406 -0.6194458 -4.538364 -2.931078 -0.9996682 -5.545590
## [3,] -1.771932  0.3889819 -3.666407 -1.616909 -0.1826611 -4.444108
##          [,26]      [,27]     [,28]     [,29]      [,30]     [,31]
## [1,]  8.000000  9.0000000  8.000000  9.000000 10.0000000  9.000000
## [2,] -3.793309 -1.6231575 -5.453378 -3.853690 -1.3446996 -5.472054
## [3,] -2.221463 -0.4329016 -4.122219 -1.942989 -0.2501587 -3.557535
##          [,32]      [,33]     [,34]     [,35]
## [1,] 10.000000 11.0000000 10.000000 11.000000
## [2,] -2.994509 -0.2401965 -3.781547 -1.684066
## [3,] -1.808188  0.9588127 -3.719374 -1.822312

Số epochs điều chỉnh dữ liệu là 3.

result$epochs
## [1] 3

Số thứ tự các điểm bị phân lớp sai sau mỗi lần cập nhật \(\mathbf{w}\)

result$mis_points %>% t()
##      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13]
## [1,]   NA   21   14   13   26    8    9   35    6    38    18    16     3
##      [,14] [,15] [,16] [,17] [,18] [,19] [,20] [,21] [,22] [,23] [,24]
## [1,]    34     2    30     3    17    34     7    12    39    14     8
##      [,25] [,26] [,27] [,28] [,29] [,30] [,31] [,32] [,33] [,34] [,35]
## [1,]    38    17    20    21    13     9    37     1     6    36     2

Visualization đường biên cuối cùng phân loại đúng tất cả các điểm dữ liệu:

w <- result$w_list
w <- w[, ncol(w)]
x1_bdr = c(0,6) 
x0_bdr = -(w[1]+w[3]*x1_bdr)/w[2]

df_boundary <- data.frame(x1 = x0_bdr[1], x2 = x0_bdr[2], y1 = x1_bdr[1], y2 = x1_bdr[2])

data %>% mutate(label = as.character(label)) %>% ggplot() + 
  geom_point(aes(x = X1, y = X2, color = label, shape = label)) +
  geom_segment(aes(x = x1, y = y1, xend = x2, yend = y2), color = 'black', size = 1, data = df_boundary)

Bài viết tham khảo:

Wiki

Toward datascientist

Blog machine learning cơ bản

Applied Go