Online Passive-Aggressive Algorithm

(Crammer et al., 2006). Online Passive-Aggressive Algorithm

Trong các bài toán phân lớp, vấn đề đảm bảo cực đại lề là một vấn đề quan trọng. Crammer et. al (2006) trình bày một họ các thuật toán online dựa trên cực đại lề. Trong các thuật toán online learning, hàm ranking thường được dựa trên một vector trọng số w. Khi bộ phân lớp hiện thời đoán sai nhãn cho một instance hiện tại, vector trọng số sẽ được cập nhật. Chiến lược cập nhật thường là cố gắng tăng trọng số đối với các feature “tốt” và giảm trọng số đối với feature “xấu”. Ngoài ra bộ phân lớp mới phải càng gần bộ phân lớp hiện tại càng tốt (để giữ được các thông tin học từ các vòng trước), và phải đảm bảo hàm mất mát tích lũy (cumulative loss) phải là cực tiểu.

Crammer đã giải quyết bài toán tối ưu nói trên và đưa ra cách tính cho tham số deltal trong công thức update vector trọng số. Công thức tính delta thay đổi trong ba phiên bản khác nhau của thuậ toán PA.

Có ba phiên bản là standard PA algorithm, PA-1 và PA-2; trong đó PA-1 và PA-2 được đề xuất để giải quyết các bài toán machine learning với dữ liệu có nhiễu (noisy data), bằng cách điều chỉnh hằng số C.

Các thực nghiệm được tiến hành với một loạt các bài toán: phân lớp nhị phân, phân lớp đa lớp, bài toán gán nhãn cho chuối (Sequence learning) và chứng tỏ các thuật toán Passive-Aggressive outperform so với thuật toán Perceptron chuẩn.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: