Bài này chúng ta tìm hiểu ứng dụng của MWU (Multiplicative Weight Update) trong thuật toán Winnow [1] một thuật toán phân loại (classifier) trong machine learning. Mình khuyến khích bạn đọc xem lại hai bài đã viết trước đây về nền tảng của MWU (ở đây và ở đây).

Bài toán phân loại

Cho trước một tập $m$ điểm dữ liệu có nhãn $\mathcal{X} = \{(\mathbf{x}_1,y_1),\ldots, (\mathbf{x}_m,y_m)\}$, trong đó, mỗi $\mathbf{x}_j$ là một vector thuộc tính (feature vector) trong không gian $n$ chiều $\mathbb{R}^n$ và mỗi $y_j \in \{-1,1\}$ được gọi là nhãn của điểm dữ liệu $\mathbf{x}_j$, $1 \leq j \leq m$.

Giả sử tập dữ liệu $\mathcal{X}$ là linearly separable, có nghĩa là tồn tại một hyperplane $\mathbf{w}$ sao cho $y_j = \mathrm{sign}( \langle \mathbf{w}, \mathbf{x}_j\rangle)$. Nói cách khác:

$y_j (\langle \mathbf{w}, \mathbf{x}_j\rangle) $ > $0 \quad \forall 1\leq j\leq m \qquad (1)$

Bài toán đặt ra là tìm một hyperplane $\mathbf{w}$ thỏa mãn (1).

Thuật toán Winnow

Trong thuật toán Winnow, ngoại trừ giả sử dữ liệu linearly separable, ta còn giả sử thêm tồn tại một hyperplane $\mathbf{w}$ mà mọi phần tử đều không âm.

Với mỗi $\mathbb{x}_j \in \mathcal{X}$, ta gán lại $\mathbb{x}_j \leftarrow y_j \cdot \mathbb{x}_j$. Do đó, bài toán $(1)$ được quy về tìm $\mathbf{w}$ sao cho:

$\begin{array} {l}\langle \mathbf{w}, \mathbf{x}_j \rangle &\mbox{ > } 0 \quad \forall 1\leq j\leq m \\ \mathbf{w}[i]& \geq 0 \end{array} \qquad (2)$

Do ta nhân hai vế của bất đẳng thức trong $(2)$ với hằng số dương bất kì không làm đổi dấu của bất đẳng thức, ta có thể quy $(2)$ về bài toán tìm $\mathbf{w}$ sao cho:

$\begin{array} {l}\langle \mathbf{w}, \mathbf{x}_j \rangle &\mbox{ > } 0 \quad \forall 1\leq j\leq m \\ \sum_{i=1}^n \mathbf{w}[i]& = 1 \\ \mathbf{w}[i]& \geq 0 \end{array} \qquad (3)$

Không khó để thấy (3) có thể giải bằng quy hoạch tuyến tính (linear programming). Ở đây ta sẽ tìm một xấp xỉ $\mathbf{w}$ thỏa mãn (3) sử dụng MWU.

Ta giả sử bài toán (3) tồn tại một hyperplane $\mathbf{w}^*$ và một số $\eta$ > $0$ sao cho:

$\langle \mathbf{w}^{*}, \mathbf{x}_j\rangle $ > $\eta \quad \forall 1\leq j\leq m \qquad (4)$

Ta nói hyperplane $\mathbf{w}^{*}$ có margin $\eta$. Số $\eta$ sẽ đặc trưng cho độ khó của bài toán: hai lớp dữ liệu càng tách biệt thì càng dễ tìm được hyperplane chia hai lớp này thành hai phần riêng biệt.

Giải thuật MWU: Ta sẽ coi mỗi thuộc tính (feature) như một "chuyên gia" và vector $\mathbf{w}^{*}$ như phân phối của các chuyên gia trong chiến lược tối ưu. Ban đầu, mỗi chuyên gia sẽ được coi như nhau, và đều có trọng số $1$, tương ứng với một phân phối đều $\mathbf{w}_1 = [1/N, \ldots, 1/N]$. Trong mỗi vòng chơi, ta sẽ thay đổi trọng số của các chuyên gia sao cho các vòng sau đó, lợi nhuận thu được là lớn nhất. Ta định nghĩa lợi nhuận của chuyên gia thứ $i$ đối với điểm dữ liệu $j$ là $\mathbf{w}[i] \mathbb{x}_j[i]$. Nếu lợi nhuận này nhỏ hơn $0$, ta cần phải giảm trọng số của chuyên gia $i$ (giảm $\mathbf{w}[i]$) và ngược lại.

Về mặt trực quan, giá trị của $\mathbf{w}[i]$ hiện tại làm cho tích $\mathbf{w}[i] \mathbb{x}_j[i]$ âm, trong khi ta muốn tìm $\mathbf{w}$ sao cho $\sum_i \mathbf{w}[i] \mathbb{x}_j[i]$ > $0$. Do đó, ta cần phải giảm $\mathbf{w}[i]$. Ta có thể coi mỗi $\mathbb{x}_j$ như một hàm lợi nhuận.

Trong vòng dự đoán thứ $t$, lợi nhuận trung bình mà phân phối hiện tại $\mathbf{w}_t$ mang lại đối với hàm lợi nhuận $\mathbb{x}_j$ là $ \langle \mathbf{w}_t,x_j\rangle$. Nếu tồn tại một hàm lợi nhuận $\mathbb{x}_{j_t}$ sao cho lợi nhuận trung bình này âm, ta sẽ cập nhật lại $\mathbf{w}_t$ theo hàm lợi nhuận $\mathbb{x}_{j_t}$ và tiếp tục vòng dự đoán tiếp theo. Ngược lại, với mọi hàm lợi nhuận $\mathbb{x}_{j_t}$ mà lợi nhuận trung bình đều không âm, ta đã tìm được một $\mathbf{w}_t$ thỏa mãn (3) và ta sẽ dừng thuật toán.

 
Chứng minh: Theo Corollary 2 của bài trước, sau $T$ vòng chơi, ta có:

$ \sum_{t=1}^T\langle \mathbf{x}_{j_t},\mathbf{w}_t \rangle \geq \sum_{t=1}^T\langle \mathbf{x}_{j_t},\mathbf{w}^*\rangle - \epsilon \sum_{t=1}^T\langle |\mathbf{x}_{j_t}|,\mathbf{w}^*\rangle - \frac{\ln n\rho}{\epsilon} \qquad (6)$

Chú ý, ta có thêm nhân tử $\rho$ trong vế phải của (6) là do các phần tử của vector lợi nhuận $\mathbf{x}_{j_t}$ thuộc $[-\rho, \rho]$ thay vì $[-1,1]$. Do $\langle \mathbf{x}_{j_t},\mathbf{w}^*\rangle \geq \eta$, $\langle |\mathbf{x}_{j_t}|,\mathbf{w}^*\rangle \leq \rho$ và $\langle \mathbf{x}_{j_t},\mathbf{w}_t \rangle$ < 0, từ (6) ta suy ra:

$ T\eta - \epsilon T\rho - \frac{\ln n\rho}{\epsilon}$ < $0$

Chọn $\epsilon = \frac{\eta}{2\rho}$, ta suy ra điều phải chứng minh.

Remarks: Từ phương trình (5) ta có thể suy ra một số nhận xét sau. Thứ nhất, số vòng lặp của giải thuật Winnow phụ thuộc vào $\ln n$ và $\rho$, ở đây $n$ là số chiều của điểm dữ liệu và $\rho$ là giá trị lớn nhất trong các thuộc tính. Điều đó làm cho giải thuật Winnow phù hợp với dữ liệu có số chiều cao và phần lớn các giá trị của thuộc tính là nhỏ. Thứ hai, cũng chính vì phụ thuộc vào $\rho$ nên thuật toán Winnow khá nhạy cảm với outlier. Chỉ cần một vài điểu dữ liệu outlier cũng có thể làm thuật toán rất lâu hội tụ.

Tha khảo

[1] S. Arora and E. Hazan and S. Kale. The Multiplicative Weights Update Method: a Meta-Algorithm and Applications. Theory of Computing 8.1 (2012): 121-164.
[2] N. Littlestone. Learning Quickly when Irrelevant Attributes Abound: a New Linear-threshold Algorithm. Machine learning 2.4 (1988): 285-318.
[3] M. Balcan. The Winnow Algorithm, Machine Learning Theory Lecture Note, Fall 2011. Accessed 01/24.