Tìm hiểu phương pháp học tích cực và ứng dụng cho bài toán lọc thư rác

(a) (b)

Hình 3.7 (a) Tính đối ngẫu trong version space. Bề mặt của siêu khối biểu diễn các vector trọng số đơn vị. Mỗi một trong hai siêu phẳng tương ứng với dữ liệu huấn luyện đã gán nhãn. Mỗi siêu phẳng giới hạn diện tích trên siêu khối mà trong đó chứa các giả thiết. Ở đây, version space là các đoạn bề mặt của siêu khối gần với camera nhất.

(b) Một bộ phân lớp SVM trên một version space. Khối bị chìm tối là khối có bán kính lớn nhất mà tâm của nó nằm trên version space và bề mặt của nó không cắt siêu phẳng. Tâm của khối bị chìm tương ứng với SVM, mà bán kính của nó tương đương với lề của SVM trong F và điểm huấn luyện tương ứng với các siêu phẳng mà nó tiếp xúc là các vector hỗ trợ.

Các SVM tìm siêu phẳng mà siêu phẳng đó cực đại hóa lề trong không gian đặc tính F. Một cách để đưa ra bài toán tối ưu này như sau:

i i

argmax(min{y (w. (x ))}) (3.14)

wCF

Có thể bạn quan tâm!

Xem toàn bộ 65 trang tài liệu này.

với "w" = 1 và yi(w. (xi)) Σ 0 i = 1 … n

Vì có điều kiện "w" = 1 và yi(w. (xi)) Σ 0 chúng ta đưa ra giải pháp trong version space. Bây giờ chúng ta coi bài toán trên như tìm một điểm trên version space sao cho khoảng cách: min{yi(w. (xi))} là cực đại. Từ tính đối ngẫu giữa không gian thuộc tính với không gian tham số và "w. (xi)" = ,



thì mỗi (si)

là một vector đơn vị của một siêu phẳng trong không gian đặc

tính. Bởi vì yi(w. (xi)) Σ 0, i = 1 … n nên mỗi siêu phẳng sẽ giới hạn version space. Biểu thức yi(w. (xi)) có thể xem như sau:

 khoảng cách giữa điểm w và siêu phẳng có vector (xi)

Do đó, muốn tìm điểm w* trong version space mà làm cực đại khoảng cách cực tiểu tới bất kỳ siêu phẳng đã mô tả nào. Nghĩa là, các SVM tìm tâm của các siêu khối có bán kính lớn nhất, siêu khối mà tâm của nó được đặt trong version space và bề mặt của nó không cắt siêu phẳng sẽ tương ứng với dữ liệu đã gán nhãn, như trong hình 3.7(b).



Các pháp tuyến của khối là khoảng cách từ tâm của khối tới một trong những siêu phẳng yi (w×. (xi)) với (xi) là vector hỗ trợ. Bây giờ hãy coi w* là một vector đơn vị của SVM và (xi) là các điểm trong không gian thuộc tính, chúng ta có khoảng cách yi (w×(si)) là:



1 khoảng cách giữa vector hỗ trợ (xi) và siêu phẳng có vector đơn vị w, Đó là lề của siêu phẳng bị chia bởi . Do đó, bán kính của siêu khối tương ứng với lề của SVM.

3.2.4 Học tích cực với SVM‌

Trong học tích cực dựa trên tập dữ liệu ban đầu đã có một lượng lớn dữ liệu chưa gán nhãn. Giả sử dữ liệu x được phân phối tương tự và độc lập, các nhãn của nó cũng được phân phối theo bộ phân phối điều kiện P(Y|x).

Cho dữ liệu chưa gán nhãn U, bộ học tích cực SVM ℓ gồm ba thành phần: (f,q,X). Thành phần đầu tiên là một bộ phân lớp SVM f: X[-1,+1] đã huấn luyện trên tập dữ liệu hiện thời X đã được gán nhãn (cũng có thể là tập dữ liệu chưa gán nhãn U). Thành phần thứ hai q(X) là hàm truy vấn, đưa ra tập dữ liệu hiện tại X đã gãn nhãn sẽ quyết định dữ liệu nào trong U là câu truy vấn tiếp theo. Bộ học tích cực có thể đưa ra bộ phân lớp f sau mỗi câu truy vấn (học trực tuyến – online learning) hoặc sau một số câu truy vấn nhất định.

Điểm khác biệt chính giữa bộ học tích cực và bộ học thụ động là thành phần truy vấn q. Thành phần này cho ta biết dữ liệu chưa gán nhãn nào để hỏi tiếp theo dữ liệu nào sẽ đưa tới cách thiết kế một hàm như vậy. Chúng ta sẽ sử dụng phương pháp chung của học tích cực trong phần 2.2. Đầu tiên chúng ta sẽ định nghĩa mô hình và chất lượng mô hình. Sau đó chúng ta sẽ lựa chọn dữ liệu để cải thiện chất lượng của mô hình.

3.2.6.1 Mô hình và hàm tổn thất (Loss)

Chúng ta sử dụng version space làm mô hình của bài toán, và kích thước của mô hình như là độ tổn thất của mô hình. Do vậy, chúng ta sẽ chọn để hỏi dữ liệu, các dữ liệu mà cố gắng làm giảm kích thước của version space càng nhiều càng tốt. Tại sao nên lựa chọn tốt mô hình và loss mô hình? Giả sử rằng w*W là một vector tham số tương ứng với SVM sao cho có thể biết được các nhãn thực của tất cả dữ liệu. Biết rằng w* phải thuộc version space Vi, Vi là version space có được sau i câu truy vấn, V1 V2V3… Do đó, bằng việc rút gọn kích thước của version space càng nhiều càng tốt với mỗi câu truy vấn, ta có thể càng làm giảm nhanh kích thước của không gian chứa w*. SVM mà chúng ta học được từ một số lượng giới hạn các câu truy vấn sẽ gần tới w*.

Định nghĩa 3.6.1: Cho một bộ học tích cực ℓ, Vi là version space của ℓ sau i câu truy vấn được đưa ra. Bây giờ khi cho câu truy vấn thứ i+1 của dữ liệu xi+1 ta có:

V– = Vi {wW| — (w. (xi+1)) Σ 0}, (3.15)

V+ = Vi {wW| + (w. (xi+1)) Σ 0} (3.16)

Vì V– và V+ là version space khi câu truy vấn tiếp theo xi+1 được gán nhãn là

i i

-1 hoặc +1.

Chúng ta mong muốn giảm kích thước của version space càng nhanh càng tốt. Cách tốt nhất để có được điều này là lựa chọn một câu truy vấn làm giảm nửa kích thước của version space.

Hình 3.8 (a) Lề đơn giản truy vấn b (b)Lề đơn giản truy vấn a

Hình 3.9 (a) Lề MaxMin truy vấn b. Hai SVM có lề m- và m+ cho b được chỉ ra.

(b) Lề MaxRatio truy vấn e. Hai SVM có lề m- và m+ cho e cũng được chỉ ra.

Seung và cộng sự [20] cũng sử dụng một phương pháp để truy vấn các điểm sao cho đạt được giảm kích thước của version space càng nhiều càng tốt. Nếu người ta muốn chấp nhận rằng có một giả thuyết ở trong 1 mà tạo ra dữ liệu thì giả thiết đó đó là xác định và dữ liệu là những điểm tự do, sau đó sự thực hiện tổng quát các thuộc tính của thuật toán mà chia nửa version space được đưa ra [45]. Ví dụ, có thể chỉ ra rằng lỗi tổng quát giảm số các câu truy vấn theo cấp số nhân.

3.2.6.2 Các thuật toán truy vấn

Ở phần trước chúng ta đã cung cấp một phương pháp truy vấn dữ liệu để chia version space hiện tại thành hai phần tương đương nhau càng nhanh càng tốt. Khi cho dữ liệu x chưa gán nhãn, thực tế là chưa tính toán rõ ràng

được kích thước của version space mới Vvà V+ (các version space thu được khi x được gán nhãn tương ứng là -1 và +1). Dưới đây là ba phương pháp cũng gần giống phương phương trên:

 Simple Margin (Lề đơn giản): Cho tập dữ liệu {x1,…,xi} và các nhãn tương ứng {y1,…,yi} vector đơn vị SVM wi có được từ tập dữ liệu này là tâm của siêu khối lớn nhất nằm vừa khít trong version space Vi. Vị trí của wi trong version space Vi phụ thuộc vào hình dạng của Vi; tuy nhiên nó thường nằm ngay trong tâm của version space. Bây giờ chúng ta có thể kiểm tra mỗi dữ liệu chưa gán nhãn x để biết xem từ sự tương ứng với các siêu phẳng trong W đến việc wi được đặt đúng tâm như thế nào. Siêu phẳng W càng gần điểm wi, thì nó càng được đặt gần đúng tâm của version space hơn và nó càng cắt đôi version space. Do vậy, với dữ liệu chưa gán nhãn thì siêu phẳng của chúng trong W gần vector wi nhất. Mỗi một dữ liệu chưa gán nhãn x, khoảng cách ngắn nhất giữa siêu phẳng của nó trong không gian W và vector wi chính là khoảng cách giữa vector đặc tính (x) và siêu phẳng wi trong F. Khoảng cách này được tính là: |wi. (x)|. Kết quả này theo một quy luật rất tự nhiên: học một SVM trên tập dữ liệu gán nhãn đã có trước và chọn dữ liệu tiếp theo để truy vấn sao cho nó gần siêu phẳng trong F nhất.

Hình 3.8(a) là một ví dụ minh họa. Trong bức ảnh cách điệu, chúng ta đã trải phẳng bề mặt của siêu khối vector đơn vị có trọng số xuất hiện trong hình 3.7(a). Vùng trắng là version space wi được bao quanh bởi các đường nét liền tương ứng với trường hợp dữ liệu có nhãn. Năm đường nét đứt biểu diễn cho các trường hợp dữ liệu chưa gán nhãn. Hình tròn biểu diễn hình cầu có bán kính lớn nhất mà có thể vừa khít trong version space. Lưu ý rằng đường viền của hình tròn không chạm vào đường nét liền - giống như những hình cầu tối trong hình 3.7 (b) không tiếp xúc được các siêu phẳng trên bề mặt của hình cầu lớn hơn (chúng sẽ tiếp xúc một điểm nào đó trên bề mặt). Trường hợp dữ liệu b là gần với SVM wi nhất và vì vậy sẽ chọn b để truy vấn.

 MaxMin Margin (Lề MaxMin): Phương pháp lề Simple có thể là một xấp xỉ gần đúng. Nó dựa trên giả định rằng version space là đối xứng và wi được đặt ở tâm. Trong lý thuyết và thực tế đã chứng minh rằng các giả định này có thể không chính xác [28]. Thật vậy, nếu không cẩn thận sẽ rất có thể truy vấn một trường hợp dữ liệu mà siêu phẳng của nó thậm chí không giao nhau với version space. Xấp xỉ MaxMin được thiết kế để khắc phục phần nào những vấn đề này. Cho dữ liệu {x1,…,xi} và nhãn

{y1,…,yi}, các vector đơn vị SVM wi là tâm của hình cầu có bán kính lớn nhất mà vừa khít trong version space Vi và bán kính mi của hình cầu tương ứng với kích thước lề của wi. Có thể sử dụng bán kính mi là biểu thị cho kích thước của version space [43]. Giả sử chúng có một trường hợp dữ liệu tiềm năng chưa gán nhãn x. Chúng ta có thể ước lượng tương đối kích thước của các version space Vbằng cách ghi nhãn cho dữ liệu x là -1, sau khi thêm x vào dữ liệu huấn luyện đã gán nhãn thì tìm SVM và kích thước lề mcủa nó. Chúng ta có thể thực hiện một phép tính tương tự cho V+ bằng cách gán lại nhãn cho x là +1 và tìm được SVM kết quả để có được lề m+.

Khi tách version space, ta thường muốn Area(V) và Area(V+) là tương

đương nhau. Bây giờ, hãy tính min(Area(V),Area(V+)), nó sẽ là nhỏ nếu Area(V ) và Area(V) là khác nhau. Vì vậy chúng ta sẽ xem xét min(m,m+) là một xấp xỉ và chúng ta sẽ chọn để truy vấn x sao cho min(m,m+) là lớn nhất. Do đó, các thuật toán truy vấn MaxMin là như sau: đối với mỗi trường hợp dữ liệu chưa gán nhãn x, tính các lề mvà mcủa các SVM thu được khi x được gán nhãn tương ứng là -1 và 1, sau đó chọn để truy vấn trường hợp dữ liệu chưa gán nhãn sao cho min(m,m) là lớn nhất.

Hình 3.8(b) và 3.9(a) chỉ ra một ví dụ so sánh giữa hai phương pháp lề Simple và lề MaxMin.

 Ratio Margin: Phương pháp này tương tự phương pháp lề MaxMin. Ta cũng sử dụng mvà mbiểu thị cho kích thước của Vvà V. Tuy nhiên, thực tế ta sẽ cố gắng tính toán version space Vi lâu hơn và đối với vài

trường hợp dữ liệu x thì cả hai mvà mcó thể là nhỏ vì hình khối của version space. Do vậy thay vì tìm kích thước tương ứng của mvà m, ta sẽ

chọn để truy vấn x sao cho min {m, m} là lớn nhất (xem hình 3.9(b)).

mm

Ba phương thức trên xấp xỉ với thành phần truy vấn mà luôn chia nửa version space. Sau khi thực hiện một số truy vấn để trả về một bộ phân lớp bằng cách học một SVM với các trường hợp dữ liệu có nhãn. Phương pháp Simple có độ tính toán chuyên sâu ít đầy đủ hơn hai phương pháp còn lại bởi vì nó cần học chỉ một SVM cho mỗi vòng truy vấn, trong khi hai phương pháp MaxMin và MaxRatio cần phải học hai SVMs cho mỗi trường hợp dữ liệu trong suốt mỗi vòng truy vấn. Chú ý rằng không nhất thiết dùng một trong những phương pháp này cho tất cả các vòng truy vấn. Vì lý do tính toán, sẽ có thể rất có lợi khi thay đổi giữa các phương pháp khác nhau sau khi một số truy vấn đã được hỏi: phương pháp truy vấn này được gọi là phương pháp Hybird.

Chúng ta đưa ra giả định đã có các vector đặc tính huấn luyện với các modun cố định. Các khái niệm về version space và kích thước của nó vẫn đúng. Hơn nữa, lề của SVM có thể được sử dụng như là một dấu hiệu kích thước của version space mà không cần quan tâm đến vector đặc tính có các modun cố định hay không. Do đó, sự giải thích cho các phương pháp MaxMin và MaxRatio vẫn đúng thậm chí không có các hạn chế trên các module của vector đặc tính huấn luyện.

Sự giả thiết về các Modun cố định là cần thiết cho việc xem version space trên phương diện hình học là đúng. Các phương pháp Simple vẫn có thể được sử dụng khi các vector huấn luyện đặc trưng không có module cố định, nhưng sự giải thích không còn đúng kể từ khi SVM không còn thể được xem như là tâm của hình cầu lớn nhất cho phép. Tuy nhiên, đối với phương pháp Simple, các hướng thay thế khác đã được Campbell, Cristianini và Smola đề xuất [10] mà không yêu cầu sự cố định trên các module.

Đối với học quy nạp, sau khi thực hiện một số câu truy vấn, sau đó sẽ trả về một bộ phân lớp bằng cách học một SVM với các trường hợp dữ liệu có nhãn. Đối với học hồi quy, sau khi truy vấn một số trường hợp dữ liệu sau đó sẽ trả về một bộ phân lớp bằng cách học một SVM hồi quy với các trường hợp dữ liệu có nhãn và không có nhãn.

3.3 Kết luận‌

Trong chương này đã nghiên cứu và trình bày tập trung vào hai thuật toán học tích cực. Phần đầu của chương giới thiệu thuật toán perceptron do Rosenblatt đề xuất. Tiếp theo là phương pháp cải tiến thuật toán perceptron của Dasgupta. Dasgupta cải tiến bước cập nhật của perceptron để thu được một thuật toán đơn giản hơn, sử dụng dữ liệu đã gán nhãn ít hơn và đạt được lỗi mục tiêu .

Phần tiếp theo của chương trình bày học tích cực dựa vào SVM, đưa ra khái niệm không gian version space, và coi đó là mô hình của học tích cực dựa vào SVM, trong đó bề mặt của version space đươc coi như là độ tổn thất của mô hình. Phần cuối của chương giới thiệu một số thuật toán truy vấn dữ liệu để có thể làm giảm không gian version space càng nhanh càng tốt. Khi đó độ tổn thất của mô hình sẽ giảm càng nhanh hơn. Các thuật toán truy vấn bao gồm: Simple, MaxMin, Ratio Margin.