Bài 11: Thuật Toán Support Vector Machine
Thuật toán Support Vector Machine có nhiều điểm tương tự như Logistic Regression nhưng tính toán đơn giản và có nhiều cách tối ưu giúp nó thực hiện nhanh chóng hơn.
Khi sử dụng khái niệmkernel, Support Vector Machine trở nên rất mạnh mẽ để giải quyết các bài toán phân loại có Decision Boundary phức tạp.
Với những ưu điểm của mình, nó là một trong những thuật toán Machine Learning phổ biến nhất hiện nay.
Nhắc lại thuật toán Logistic Regression
Xét đồ thị phân bố dữ liệu dưới đây
Thuật toán Logistic Regression giúp ta tìm ra phương trình đường Decision Boundary $x^{T}w = 0$ phân chia các điểm dữ liệu có output 0 và các điểm dữ liệu có output 1 với w =$\begin{bmatrix}w_{0} \\ w_{1} \\ \\ w_{n} \end{bmatrix} $ và x =$\begin{bmatrix}1 \\ x_{1} \\ \\ x_{n} \end{bmatrix}$.
Phương trình giả thuyết chính là khả năng một input có output tương ứng là 1
$\widehat{y} = \frac{1}{1 + e^{-x^{T}w}}$
Hàm mất mát sử dụng hàm Sigmoid
$J[w] = -\frac{1}{m} \sum_{i=1}^{m} [y^{[i]}ln [\widehat{y}^{[i]}] + [1 - y^{[i]}]ln [1 - \widehat{y}^{[i]}]] + \frac{\lambda}{2m}\sum_{j=1}^{n} w^{2}_{j}$
Ở đây $-ln [\widehat{y}^{[i]}]$ là phần mất mát mỗi input đóng góp khi output thực tế là 1 và $-ln [1 - \widehat{y}^{[i]}]$ là phần mất mát mỗi input đóng góp khi output thực tế là 0.
Thuật toán Support Vector Machine
Mô hình toán học
Support Vector Machine không đưa ra khả năng output bằng 1 như Logistic Regression, thay vào nó nó chỉ đơn thuần dự đoán output bằng 0 hay bằng 1.
$\widehat{y} =\begin{cases}1 & khi\ x^{T}w \geq 0\\0 & khi\ x^{T}w < 0\end{cases}$
Độ chính xác của phương trình giả thuyết
Trong Support Vector Machine, phần mất mát mỗi input đóng góp có dạng hàm hinge loss
$cost[x] = \begin{cases}max[0, k[1 - x^{T}w]] & khi\ y = 1\\max[0, k[1 + x^{T}w]] & khi\ y = 0\end{cases}$
với k là số dương bất kỳ.
Khi y = 1, cost[x] = 0 nếu $x^{T}w \geq 1$ và cost[x] tăng dần nếu $x^{T}w < 1$ và tiến tới âm vô cực.
Khi y = 0, cost[x] = 0 nếu $x^{T}w \leq -1$ và cost[x] tăng dần nếu $x^{T}w > -1$ và tiến tới dương vô cực.
Hàm mất mát của Support Vector Machine
$J[w] = C \sum_{i=1}^{m} [y^{[i]}max[0, k[1 - x^{[i]T}w]] + [1 - y^{[i]}]max[0, k[1 + x^{[i]T}w]]] + \frac{1}{2}\sum_{j=1}^{n} w^{2}_{j}$
Ở đây hằng số C đóng vai trò như $\frac{1}{\lambda}$ là độ chính quy hóa của hàm mất mát giúp kiểm soát sai lầm của phương trình giả thuyết. Khi xảy ra underfitting, ta cần tăng C. Khi xảy ra overfitting, ta cần giảm C.
Nghiệm của thuật toán Support Vector Machine
Ta có thể tìm điểm cực tiểu của hàm mất mát bằng thuật toán Gradient Descent với các biến đổi
$w_{0} := w_{0} - \alpha C \sum_{i=1}^{m} [y^{[i]}[x^{[i]T}w \geq 1\ ?\ 0:-k] + [1 - y^{[i]}][x^{[i]T}w \geq -1\ ?\ k:0]]$
$w_{1} := w_{1}[1 - \alpha] - \alpha C \sum_{i=1}^{m} [y^{[i]}[x^{[i]T}w \geq 1\ ?\ 0:-kx_{1}^{[i]}] + [1 - y^{[i]}][x^{[i]T}w \geq -1\ ?\ kx^{[i]}_{1}:0]]$
$w_{n} := w_{n}[1 - \alpha] - \alpha C \sum_{i=1}^{m} [y^{[i]}[x^{[i]T}w \geq 1\ ?\ 0:-kx_{n}^{[i]}] + [1 - y^{[i]}][x^{[i]T}w \geq -1\ ?\ kx^{[i]}_{n}:0]]$
Một đặc điểm của Support Vector Machine là nó luôn cố gắng tìm nghiệm sao cho Dicision Boundary cách xa các điểm dữ liệu nhất cho thể. Trong hình dưới đây, thuật toán có xu hướng chọn phương án A thay vì phương án B vì nó cách xa các điểm dữ liệu hơn. Điều này có thể dẫn tới overfitting và ta có thể làm giảm xu hướng này bằng cách giảm C.
Việc tìm nghiệm của thuật toán Support Vector Machine tương đối phức tạp nếu cài đặt thủ công. Có rất nhiều thư viện đã được cài đặt sẵn Support Vector Machine và ta nên dùng chúng vì chẳng những giúp tiết kiệm thời gian mà các thư viện đó còn được áp dụng nhiều kỹ thuật tối ưu hóa để thuật toán chạy nhanh hơn.