# Chứng minh hội sự hội tụ của PLA

Hồi trước mình đọc về PLA ở [blog của thầy Tiệp](https://) mình đã không thể hiểu rõ về cách chứng minh sự hội tụ lắm, chỉ là chấp nhận về mặt toán học chỉ nhìn vào các công thức mà thôi. Hôm nay khi đọc lại, mình đã có một cái nhìn rõ hơn về công thức chứng minh, mình sẽ note lại trong bài viết này, kèm theo đó mình sẽ sử dụng kí hiệu giống như trong blog của thầy Tiệp vì mình muốn note để nhớ chứ không phải tạo ra một cái gì đó riêng biệt, sử dụng ký hiệu chung cũng góp phần cho việc ghi nhớ dễ hơn.

Nhắc lại : chúng ta cần phân lớp 2 tập điểm với giả thiết 2 tập này là Linearly Separable, tức luôn tồn tại một siêu phẳng phân chia 2 lớp riêng biệt này. Thuật toán PLA hoạt động như sau :

Kí hiệu $y_i$ là phân lớp thực sự của điểm dữ liệu $\textbf{x}_i$, nhận 1 trong 2 giá trị $-1$ hoặc $1$ tương ứng với 2 class và $\textbf{w}$ là ma trận trọng số.

Ta chọn loss function là :
$$
J(\textbf{w}) = \sum_{i\in\mathcal{M}} -y_i\textbf{w}^T\textbf{x}_i \qquad(1)
$$

Với $\mathcal{M}$ là tập index các điểm bị misclassifed. Nhìn vào biểu thức trên, nếu $\textbf{x}_i$ bị phân lớp nhầm, rõ ràng $y_i$ và $\textbf{w}^T\textbf{x}_i$ trái dấu, do đó $(1)$ sẽ mang dấu dương. Hơn nữa hàm Loss này sẽ đánh phạt rất nặng những điểm bị phân nhầm sâu vào biên của lớp khác (càng sâu càng nặng).

Đạo hàm của $J(\textbf{w})$ chỉ **với một điểm dữ liệu** là :

$$
\nabla J(\textbf{w})=-y_i\textbf{x}_i \qquad(2)
$$

Vậy ta cần tối ưu hàm Loss theo Gradient Descend, công thức cập nhật là :

\begin{align*}
\textbf{w}_{new} & =\textbf{w}_{old} - \eta \nabla J(\textbf{w}_{old}) \\ & = \textbf{x}_i+ \eta y_i \textbf{x}_i \quad (3)
\end{align*}

Ta có một nhận xét sau :

Xét một điểm dữ liệu $\textbf{x}_i$ bị phân lớp nhầm, theo $(3)$, ta có :

$$
\textbf{w}_{new} = \textbf{w}_{old} + \eta y_i \textbf{x}_i
$$

Để xem việc cập nhật tác động thế nào đến việc phân lớp cho $\textbf{x}_i$, ta sẽ xem $\textbf{w}_{new}$ đem đến dự đoán như thế nào cho $\textbf{x}_i$ :

\begin{align*}
\hat{y}_{new} &= \textbf{w}_{new}^T \textbf{x}_i \\
&=(\textbf{w}_{old} + \eta y_i \textbf{x}_i) \textbf{x}_i \\
&=\textbf{w}_{old}^T \textbf{x}_i + \eta y_i \Vert \textbf{x}_i \Vert_2^2 \quad (4)
\end{align*}

Ta so sánh $(4)$ với dự đoán ban đầu, tức là phân lớp của $\textbf{x}_i$ với $\textbf{w}_{old}$ :

Ta có :

$$
\hat{y}_{old} = \textbf{w}_{old}^T \textbf{x}_i \quad (5)
$$

Vậy :

\begin{align}
\hat{y}_{new} - \hat{y}_{old} &= \textbf{w}_{old}^T \textbf{x}_i + \eta y_i \Vert \textbf{x}_i \Vert_2^2 - \textbf{w}_{old}^T \textbf{x}_i \\
&= \eta y_i \Vert \textbf{x}_i \Vert _2^2 \quad (6)
\end{align}

Giả sử $\textbf{x}_i$ thuộc lớp $-1$ tức là $y_i=-1$, ta thấy $(6)$ là một số âm (xin nhắc lại $\eta$ là learning rate và là một hằng số dương), tức là nếu $y_i=-1$ và $\textbf{x}_i$ đang bị phân lớp nhầm, đồng nghĩa với việc $\hat{y}_{old} > 0$, bước cập nhật $(3)$ sẽ khiến cho $\hat{y}_{old}$ phải cộng thêm một lượng thực âm nữa, tức là ta đang ép siêu phẳng phân cách dời về hướng làm cho $\textbf{x}_i$ được phân lớp đúng. Suy luận tương tự khi $y_i=1$.

Tại mỗi bước, thuật toán sẽ chọn ra ngẫu nhiên một điểm bị misclassifed, cập nhật lại $\textbf{w}$ như trong $(3)$, cho đến khi không còn điểm nào bị misclassifed nữa. Tuy nhiên nếu như cập nhật riêng rẽ từng điểm như vậy thì có thể một điểm nào đó đang được phân loại đúng, sau bước cập nhật thì nó lại bị phân loại sai, thế là thành 1 vòng vô hạn các bước.

Vậy câu hỏi đặt ra là thuật toán có hội tụ không? Tức là chúng ta sẽ tìm ra được một siêu phẳng phân lớp cho toàn bộ điểm dữ liệu sao cho không có điểm dữ liệu nào bị phân lớp nhầm sau một số hữu hạn các bước lặp như trên hay không?

Đáp án là có : Thuật toán sẽ tìm ra được một siêu phẳng như vậy sau một số hữu hạn bước!

Chúng ta sẽ chứng minh nó ngay sau đây.

### Chứng minh sự hội tụ

Nhận thấy khi $\textbf{w}^*$ là một nghiệm thì $\alpha \textbf{w}^*$ cũng là nghiệm, để cho dễ hình dung thì $\textbf{w}^*$ là vector chỉ phương của siêu phẳng ta đang tìm, điều ta cần quan tâm đó là phương của vector này chứ không phải độ dài của nó. Do đó, ta sẽ lấy một vector làm chuẩn cho các vector còn lại, tức là ta có thể biểu diễn các vector khác (cùng phương) với vector chuẩn đó bằng cách nhân một lượng $\alpha$ như ở trên. Vậy ta có thể biểu diễn nghiệm dưới dạng $\alpha \textbf{w}^*$

Gọi $\textbf{w}_t$ là ma trận trọng số mà ta đang cố gắng tối ưu ở thời điểm $t$, ta đang muốn xem xem liệu ta còn cách nghiệm thực sự của bài toán (tức $\alpha \textbf{w}^*$) bao xa nữa, ta sẽ định nghĩa khoảng cách đó như sau :

$$
u(t) = \Vert \textbf{w}_t - \alpha \textbf{w}^* \Vert_2^2
$$

Lý do cho việc chọn norm 2 của hiệu 2 vector như thế này là nếu vector $\textbf{a}$ càng giống vector $\textbf{b}$ thì $\Vert \textbf{a} - \textbf{b}\Vert_2^2$ càng bé.

Xét ở thời điểm $t+1$, ta xét xem liệu ta có tiến gần đến nghiệm như thế nào :

\begin{align*}
u(t + 1) &= \Vert \textbf{w}_{t + 1} - \alpha \textbf{w}^* \Vert_2^2 \\
&= \Vert \textbf{w}_t + y_i \textbf{x}_i - \alpha \textbf{w}^* \Vert_2^2 \\
&= \Vert \textbf{w}_t - \alpha \textbf{w}^* \Vert_2^2 + y_i^2\Vert \textbf{x}_i \Vert_2^2 + 2 y_i \textbf{x}_i^T (\textbf{w}_t - \alpha \textbf{w}^*) \\
& \leq u(t) + \Vert \textbf{x}_i \Vert_2^2 - 2 \alpha y_i \textbf{x}_i^T \textbf{w}^* \\
\end{align*}

Dấu $\leq$ ở dòng cuối là do $2 y_i \textbf{x}_i^T \textbf{w}_t < 0$ vì điểm $\textbf{x}_i$ đang bị phân lớp sai

Đặt $\beta^2 = \max\limits_{i=1,2,3...N}(\Vert \textbf{x}_i \Vert_2^2)$ và $\gamma = \min\limits_{i=1,2,3...N}(2 y_i \textbf{x}_i^T \textbf{w}^*)$

Ta có :

\begin{align*}
u(t + 1) \leq u(t) + \beta^2 - 2 \alpha \gamma
\end{align*}

Vậy nếu nghiệm $\alpha \textbf{w}^*$ ta đang tìm có dạng là $\frac{\beta^2}{\gamma} \textbf{w}^*$, tức là $\alpha = \frac{\beta^2}{\gamma}$ thì :

\begin{align*}
u(t+1) \leq u(t) - \beta^2
\end{align*}

Tức là tại thời điểm $t + 1$ thì $\textbf{w}_{t+1}$ sẽ gần nghiệm $\alpha \textbf{w}^*$ hơn là $\textbf{w}_t$ mà cụ thể là "gần" hơn một lượng là $\beta^2$. Do $u(t)$ là norm 2 của một vector nên $u(t) \ge 0$, hơn nữa $\beta^2 > 0$ vậy thì $u(t)$ phải là một dãy số hữu hạn. Vậy tức là thuật toán hội tụ. Đã chứng minh xong!