Luận văn 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

mẫu là học một một bộ phân tách tuyến tính cho các dữ liệu phân bố đều trên mặt cầu đơn vị. 3.2 Học tích cực với SVM 3.2.1 Giới thiệu Bộ phân loại SVM đã được sử dụng rộng rãi trong rất nhiều bài tốn phân lớp. Tuy nhiên chúng chỉ được sử dụng với tập dữ liệu huấn luyện đã được lựa chọn ngẫu nhiên. Trong mục này sẽ trình bày thuật tốn Active Support Vector Machines (Acitve SVM) cĩ thể làm giảm đi dung lượng cũng như sự cần thiết của tập dữ liệu huấn luyện. 3.2.2 Máy hỗ trợ vector 3.2.2.1 Máy vector hỗ trợ sử dụng phương pháp qui nạp Máy vector hỗ trợ [41] cĩ các cơ sở lý thuyết vững chắc và đạt được những thành cơng thực nghiệm xuất sắc. Chúng cũng được áp dụng cho những bài tốn như: nhận dạng số viết bằng tay [24], nhận dạng đối tượng [13], và phân lớp văn bản [37][33]. Hãy xét thuật tốn SVM cho bài tốn phân lớp nhị phân. Cho tập huấn luyện ; E   M là các vector trong khơng gian X⊆Rd và tập các nhãn ; E   M với yi∈ {-1,1}. Theo cách hiểu thơng thường nhất, thì SVMs là các siêu phẳng chia tập dữ liệu huấn luyện bằng một lề cực đại. Tất cả các vector nằm trên một mặt của siêu phẳng đều được gán nhãn là -1, và tất cả các 28 vector nằm trên mặt kia đều được gán nhãn là 1. Các vector huấn luyện gần siêu phẳng nhất gọi là vector hỗ trợ (support vector). Hình 3.5 (a) Máy hỗ trợ vector tuyến tính đơn giản. (b) Máy hỗ trợ vector (đường nét đứt) và máy hỗ trợ vector hồi quy (đường nét liền). Những vịng trịn biểu diễn dữ liệu chưa được gán nhãn. Nĩi chung, SVMs cho phép chiếu dữ liệu huấn luyện gốc trong khơng gian X sang một khơng gian đặc trưng F nhiều chiều hơn thơng qua một phép phân Mercer K. Nĩi cách khác chúng ta cĩ tập các bộ phân lớp như sau: (  +NOGP   M Q& R++++++++++++++++++++++++++++++++++++++3.S Khi K thỏa mãn điều kiện Mercer [12] thì PT U  +ΦT.ΦU trong đĩ Φ: X→Y và “⋅” là phép tích trong (inner product). Ta cĩ thể viết lại như sau: +(  V.Φ W BX+YZ++V OGΦ M Q& +++++++++++++++++++++++++3.[ Do vậy, bằng cách sử dụng K chúng ta cĩ thể ánh xạ dữ liệu huấn luyện sang một khơng gian đặc trưng (thường là nhiều chiều hơn). Siêu phẳng lề cực đại được chỉ ra trong biểu thức 3.8. Sau đĩ SVM tính các αi tương ứng với siêu phẳng cĩ lề cực đại trong khơng gian F. Khi chọn các hàm nhân khác nhau thì cĩ thể ánh xạ dữ liệu huấn luyện từ khơng gian X sang F sao cho các 29 siêu phẳng trong F sao cho các siêu phẳng trong F tương ứng với các đường biên quyết định phức tạp hơn trong khơng gian gốc X. Hai hàm nhân thường sử dụng là hàm nhân đa thức P\ #  \. # ] tạo ra đường biên đa thức bậc p trong khơng gian đầu vào X và hàm nhân radial basis fuction ^_ `  abcdbe.dbe tạo đường biên bằng cách định vị trọng số Gauss dựa trên các dữ liệu huấn luyện chính. Trong hình 3.6 minh họa đường biên quyết định trong khơng gian đầu vào X của một SVM sử dụng hàm nhân đa thức bậc 5. Đường biên quyết định được làm cong trong khơng gian X tương ứng với siêu phẳng lề cực đại trong tập thuộc tính F. Các tham số αi xác định SVM cĩ thể được tìm trong hàm đa thức thời gian bằng cách giải quyết bài tốn tối ưu lồi[42]:  f g G  ;Eg GGhhPi h (3.10) với : αi > 0 i=1…n 3.2.2.2 Máy vector hỗ trợ sử dụng phương pháp transduction Giả sử tập dữ liệu huấn luyện đã được gán nhãn và bài tốn đặt ra là tạo ra một bộ phân lớp thực hiện tốt trên tập dữ liệu kiểm tra chưa biết. Thêm vào trong phương pháp qui nạp thơng thường, SVMs cĩ thể sử dụng cho bài tốn transduction. Đầu tiên là cho tập dữ liệu đã gán nhãn và chưa gán nhãn. Bài tốn học là phải khai báo các nhãn tới các dữ liệu chưa gán nhãn càng chính xác càng tốt. SVMs cĩ thể thực hiện phương pháp transduction bằng cách tìm các siêu phẳng làm cực đại hĩa lề liên quan đến dữ liệu đã gán nhãn và chưa gán nhãn. Ví dụ được thể hiện ở hình 3.5b. Gần đây, các transduction SVM(TSVM) cịn được sử dụng để giải quyết bài tốn phâp lớp văn bản [37][38] đã đạt được một số tiến bộ trong việc thực hiện cân bằng tỉ số độ chính xác/độ hồi phục (precision/recall) trên các SVM qui nạp. 30 Hình 3.6 Máy hỗ trợ vector sử dụng hàm nhân đa thức bậc 5. Khơng giống SVM, TSVM cĩ độ phức tạp thời gian đa thức, chi phí để tìm được hướng giải quyết cho TSVM tăng lên theo hàm mũ cùng với sự tăng của dữ liệu chưa được gán nhãn. Bằng trực quan, ta phải gán tất cả các nhãn cĩ thể cho dữ liệu chưa gán nhãn, và mỗi một nhãn phải tìm một siêu phẳng cĩ lề cực đại. Do vậy sẽ sử dụng thuật tốn xấp xỉ thay thế. Ví dụ, Joachims sử dụng dạng tìm kiếm quỹ tích để gán nhãn và tái gán nhãn cho dữ liệu chưa được gán nhãn để cải tiến kích thước của lề. 3.2.3 Version space Cho tập dữ liệu huấn luyện đã gán nhãn và hàm nhân Mercer K, khi đĩ sẽ cĩ một tập các siêu phẳng chia dữ liệu thành vào khơng gian thuộc tính F. Tập các giả thuyết phù hợp như vậy gọi là version space [39]. Nĩi cách khác, giải thuyết f là trong version space nếu với mọi dữ liệu huấn luyện xi cĩ nhãn yi thì f(xi)>0 nếu yi=1 và f(xi)<0 nếu yi=-1. Tổng quát hơn: Định nghĩa 3.5.1: Cho tập các giả thuyết: j  k(<(  l.Φ DlD Lmn+YZ+l∈+op (3.11) Trong đĩ khơng gian tham số W sẽ tương ứng với khơng gian F. Version space q được định nghĩa như sau: q  (∈+j<∀∈( - ' (3.12) 31 Chú ý rằng khi j là tập các siêu phẳng, sẽ cĩ một song ánh giữa vector w vào giả thuyết f trong j. Do vậy q sẽ được định nghĩa lại như sau: q  rl∈o<+DlD   sl.Φt - '   u (3.13) Định nghĩa 3.5.2: Kích thước hay diện tích của version space Area(q) là diện tích bề mặt của siêu khối cầu khi D$D  . Lưu ý rằng version space chỉ tồn tại khi dữ liệu huấn luyện là tách rời tuyến tính trong khơng gian thuộc tính. Như đã đề cập trong phần 3.2.2.1, hạn chế này khơng giới hạn như lúc đầu ta tưởng. Tồn tại sự đỗi ngẫu giữa khơng gian thuộc tính F và khơng gian tham số v[43][28] mà chúng ta sẽ áp dụng cho phần sau: các điểm trong F tương ứng với các siêu phẳng trong W và ngược lại. Vì định nghĩa các điểm trong W tương ứng với các siêu phẳng trong F, ta sẽ quan sát một trường hợp dữ liệu huấn luyện xi trong version space giới hạn các siêu phẳng tách rời nhau vào những bộ mà phân lớp xi một cách chính xác. Thực tế, chúng ta cĩ thể chỉ ra rằng, tập các điểm cĩ thể cho phép w trong W bị giới hạn nằm trong một phía của một siêu phẳng trong W. Hơn nữa, để chỉ ra các điểm trong F tương ứng với siêu phẳng trong W, giả sử cho dữ liệu huấn luyện mới xi cĩ nhãn yi, sau đĩ bất kỳ siêu phẳng phân chia nào cũng phải thỏa mãn s$.Φt - '. Bây giờ thay vì chỉ coi w như là một vector trong siêu phẳng F thì ta nghĩ rằng Φ(xi) cũng là vector trong khơng gian W. Do đĩ s$.Φt - ' là nửa khơng gian trong W. Lại cĩ $.Φ  ' là một siêu phẳng trong W mà nĩ đĩng vai trị như một trong những đường biên của version space q. Lưu ý rằng version space là một miền đã được kết nối trên bề mặt của một siêu khối trong khơng gian tham số. Hình 3.7 là một ví dụ. 32 (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 tốn tối ưu này như sau: wmnxwyz {XV.Φ (3.14) với D$D  +`|+s$.Φt - '+   Vì cĩ điều kiện DVD   và s$.Φt - '+chúng ta đưa ra giải pháp trong version space. Bây giờ chúng ta coi bài tốn trên như tìm một điểm trên version space sao cho khoảng cách: {XV.Φ 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à DV.ΦD  λ 33 thì mỗi Φ } λ là một vector đơn vị của một siêu phẳng trong khơng gian đặc tính. Bởi vì s$.Φt - '   + nên mỗi siêu phẳng sẽ giới hạn version space. Biểu thức s$.Φt cĩ thể xem như sau: λ× khoảng cách giữa điểm w và siêu phẳng cĩ vector Φ 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 sV~.Φt với Φ là vector hỗ trợ. Bây giờ hãy coi w* là một vector đơn vị của SVM và Φ là các điểm trong khơng gian thuộc tính, chúng ta cĩ khoảng cách $~⋅Φ }λ  là: ; λ × khoảng cách giữa vector hỗ trợ Φ 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. 34 Đ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 tố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*∈v 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 qi, qi là version space cĩ được sau i câu truy vấn, q1 ⊃q2⊃q3… 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 ℓ, qi 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ĩ: qb  q ∩r$∈v< sV.Φ:;t - 'u (3.15) q:  q ∩r$∈v< sV.Φ:;t - 'u (3.16) Vì qb và q: là version space khi câu truy vấn tiếp theo xi+1 được gán nhãn là -1 hoặc +1. 35 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 j 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 tố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 tố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 tốn rõ ràng 36 được kích thước của version space mới q− và q+ (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 qi. Vị trí của wi trong version space qi phụ thuộc vào hình dạng của qi; 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 Φ và siêu phẳng wi trong F. Khoảng cách này được tính là: <$i.Φ<. 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. 37 • 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 qi 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 q− 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 q+ 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(q−) và Area(q+) là tương đương nhau. Bây giờ, hãy tính min(Area(q−),Area(q+)), nĩ sẽ là nhỏ nếu Area(q −) và Area(q+) 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 tố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 q− và q+. Tuy nhiên, thực tế ta sẽ cố gắng tính tốn version space qi lâu hơn và đối với vài 38 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 {X k−+ +−p là lớn nhất (xem hình 3.9(b)). 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 tố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 tố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. 39 Đố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 tốn học tích cực. Phần đầu của chương giới thiệu thuật tốn perceptron do Rosenblatt đề xuất. Tiếp theo là phương pháp cải tiến thuật tố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 tố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 tố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 tốn truy vấn bao gồm: Simple, MaxMin, Ratio Margin. 40 CHƯƠNG 4. ỨNG DỤNG HỌC TÍCH CỰC CHO BÀI TỐN LỌC THƯ RÁC 4.1 Giới thiệu Trong số các phương pháp lọc và ngăn chặn thư rác thơng dụng, phương pháp lọc theo nội dung cĩ một số ưu điểm quan trọng và hiện đang được sử dụng trong nhiều hệ thống lọc thư thương phẩm. Lọc theo nội dung hoạt động theo nguyên tắc phân loại thư điện tử thành hai nhĩm “thư rác” và “thư thường” bằng cách phân tích phần nội dung của thư. Trong nghiên cứu này, chúng tơi giới hạn việc phân loại thư cho trường hợp thư cĩ chứa văn bản. Như vậy, nội dung thư ở đây là phần văn bản trong thư. Chúng tơi cũng khơng xem xét tới cách định dạng trong thư khi phân loại, chẳng hạn thư cĩ được trình bày dưới dạng HTML hay khơng, mặc dù thơng tin về định dạng cĩ thể đĩng vai trị quan trọng trong việc phát hiện thư rác. Lọc thư rác theo nội dung là trường hợp riêng của bài tốn phân loại văn bản. Tuỳ theo nội dung, thư được phân thành hai loại: thư rác và thư bình thường. Việc phân loại tiến hành như sau. Trước tiên, nội dung thư được biểu diễn dưới dạng vector các đặc trưng hay các thuộc tính, mỗi đặc trưng thường là một từ hoặc cụm từ xuất hiện trong thư. Tiếp theo, trong giai đoạn huấn luyện, tập thư đã được gán nhãn {rác, bình thường} - gọi là dữ liệu huấn luyện hay dữ liệu mẫu - được sử dụng để huấn luyện một bộ phân lớp. Sau khi huấn luyện xong, bộ phân loại được sử dụng để xác định thư mới (thư chưa biết nhãn) thuộc vào loại nào trong hai loại nĩi trên. Trong cả giai đoạn huấn luyện và phân loại, thuật tốn phân loại chỉ làm việc với nội dung thư đã được biểu diễn dưới dạng vector. Cĩ nhiều phương pháp phân loại cĩ thể sử dụng để phân loại thư điện tử, luận văn này nghiên cứu phân loại dựa vào phương pháp học tích cực với hai thuật tốn xây dựng bộ học tích cực là thuật tốn Perceptron [17] và Acitve Support Vector Machines (Acitve SVM) [35]. 41 4.2 Học tích cực trong bài tốn lọc thư rác Nhiệm vụ của lọc thư rác là tự động tìm ra các thư điện tử khơng mong muốn, độc hại trước khi chúng được chuyển đến người sử dụng. Nhiệm vụ của lọc thư rác là một phạm vi ứng dụng quan trọng và cĩ qui mơ lớn trong lĩnh vực học máy. Phương pháp học tích cực đã được phát triển mạnh mẽ trong học máy để làm giảm đi chi phí gán nhãn bằng cách xác định các dữ liệu chứa thơng tin mà cĩ yêu cầu nhãn. Điều này được thể hiện trong thực tế rằng chỉ cĩ một phần nhỏ của tập dữ liệu chưa cĩ nhãn là cần phải được gán nhãn để huấn luyện bộ học tích cực sao cho đạt đến một hiệu suất đủ để ứng dụng trong việc phân loại. Với tốc độ học cao và yêu cầu ít các email đã gán nhãn để huấn luyện, chúng ta sẽ áp dụng phương pháp học tích cực ở trên vào bài tốn lọc thư rác. Phương pháp học tích cực cho phép chọn các mẫu huấn luyện một cách tự động. Sử dụng tri thức hiện tại, bộ học tích cực khơng thụ động nhận các mẫu huấn luyện mà lại tích cực lựa chọn các mẫu sao cho cĩ thể huấn luyện được một mơ hình tối ưu hơn. Kịch bản ý tưởng của học tích cực trong bài tốn lọc thư rác được thể hiện qua hình 4.1. Các thư điện tử được giả sử là đến theo luồng, nghĩa là tại một thời điểm chỉ cĩ một thư điện tử đến. Với mỗi một thư đến, bộ học sẽ đưa ra truy vấn để nhận được nhãn của thư bằng cách dự đốn đĩ là thư thường hay thư rác. Người dùng sẽ quan sát thư và nhãn của thư được bộ học dự đốn trước đĩ và thực hiện phản hồi đến bộ học tích cực, cung cấp nhãn thực sự của thư, thư đĩ thực sự là thư rác hay thư thường. Bộ lọc thư tích cực nhận phản hồi của người dùng sẽ xác định được sự dự đốn của mình về nhãn của thư là đúng hay sai. Nĩ học sẽ sử dụng nhãn thực sự của thư do người dùng phản hồi để cập nhật thêm vào tập huấn luyện, huấn luyện (cập nhật) lại mơ hình để cải thiện hiệu suất lọc thư hay cải thiện dự đốn nhãn cho các thư sau. Hình 4.1 Bộ l Cĩ nhiều thuật to hình như thuật tốn truy v mẫu khơng chắc chắn, truy v này đều đạt hiệu quả trong b chỉ áp dụng 2 thuật tốn dựng bộ học tích cực cho b Trong mơ hình b vào thuật tốn perceptron ho bày ở chương 3. Với bộ sẽ cho ta bộ lọc thư rác dựng dựa trên active SVM s thư rác tích cực này được vector hĩa và được trích đĩ được đưa vào bộ học học của bộ lọc thư điện bộ lọc đạt hiệu quả cao. 42 ọc thư rác áp dụng phương pháp học tích án được sử dụng để xây dựng bộ học ấn dựa vào hội động (Query by Committee), l ấn dựa vào tập dữ liệu ban đầu… C ài tốn lọc thư rác. Tuy nhiên trong lu học tích cực là Perceptron và active ài tốn lọc thư rác. ài tốn lọc thư rác bộ học tích cực được ặc thuật tốn học tích cực dựa vào họctích cực được xây dựng trên thuật tích cực perceptron. Bộ học tích tích ẽ thu được bộ lọc thư SVM tích thể hiện trong hình 4.2. Thư điện tử chọn các thuộc tính đặc trưng đại di tích cực (perceptron hoặc SVM active). Qu tử sẽ được lặp đi lặp lại nhằm mục đích cực tích cực, điển ấy ác thuật tốn ận văn này, SVM để xây xây dựng dưa SVM đã trình tốn perceptron cực được xây cực. Các bộ lọc khi đến sẽ được ện cho thư, sau á trình thu được một Hình 4.2 Bộ lọc th 4.3 Thử nghiệm và k Luận văn định hư thử nghiệm phân loại thư đi cả thư thườngvà thưc rác. Ph nghiệm mã nguồn mở chương ba là chương tr ActiveExperimenter do thu thập dữ liệu và xây d liệu về dạng dữ liệu đầ phân tích, đánh giá và nh 4.3.1. Cài đặt chươ 4.3.1.1. Chương tr 1. Giới thiệu chương tr Chương tr năm 1999, và các tiếp theo. Snow trên các thuật tốn 2. Down load Chương trình đượ 43 ư rác tích cực dựa trên Perceptron/SVM active ết quả ớng khai thác phần mềm mã nguồn m ện tử trên tập dữ liệu là các thư đi ần đầu của mục 4.3 sẽ giới thi cài đặt hai thuật tốn học tích cực đã tr ình Snow do Dan Roth xây dựng [46] Ran EL-Yaniv xây dựng [47]. Các ph ựng chương trình tiền xử lý dữ liệu và bi u vào cho các cơng cụ thực nghiệm. V ận xét thực nghiệm. ng trình thử nghiệm ình snow ình ình Snow được Ran Roth cài đặt phi phiên bản sau cũng được phát triển là chương trình học kiến trúc, là bộ h winnow, percepptron, nạve Bayer… c download trên trang web mã nguồn m ở để tiến hành ện tử bao gồm ệu hai tool thực ình bày trong và chương trình ần tiếp theo sẽ ểu diễn dữ à cuối cùng là ên bản đầu tiên trong nững năm ọc được cài đặt ở: 44 3. Cài đặt Chương trình được cài đặt trên máy tính cĩ cài hệ điều hành Linux, Trước tiên, cần giải nén file cài đặt bằng các lệnh sau: >tar –xvzf SNoW_v3.1.8.tar Sau đĩ nĩ sẽ tạo ra một thư mục cĩ tên là Snow_v3.1 chứa Makefile và các file nguồn. Chuyển đường dẫn vào thư mục vừađược tạo ra (Snow_v3.1) bằng lệnh > cd Snow_v3.1 Gõ lệnh: >makefile Chương trình sẽ tạo ra file thực thi Snow Quá trình thực thi này được sử dụng để huấn luyện, kiểm tra và đánh giá quá trình thực hiện. 4.3.1.2. Chương trình ActiveExperimenter 1. Giới thiệu chương trình ActiveExperiment là chương trình được cài đặt dựa trên bốn thuật tốn học tích cực dựa vào SVM, đĩ là thuật tốn Simple, Self-Conf, KFF và balanced. Chương trình được Ran EL-Yaniv xây dựng bằng ngơn ngữ java, cài đặt một số thuật tốn học tích cực. 2. Down load Người dùng cĩ thể download cơng cụ trên trang web: 3. Cài đặt Chương trình cĩ thể cài đặt trên máy tình cáo cài hệ điều hành Window hoặc Linux. Để chạy chương trình trước tiên phải cài java 1.4.2 hoặc phiên bản cao hơn. Cĩ thể download java trên trang web. Sau khi đã cài đặt mơi trường, giải nén file cài đặt AcitveExperimenter.zip, ta được thư mục AcitveExperimenter. Trong 45 thư mục cĩ chưa file experimenter.bat chính là file chạy của chương trình. 4.3.2. Thu thập và biểu diễn dữ liệu 1. Dữ liệu thử nghiệm Một khĩ khăn khi thử nghiệm lọc thư là hiện nay chưa cĩ những bộ dữ liệu mẫu chuẩn. Do vậy tác giả sẽ tự tiến hành xây dựng bộ dữ liệu thư để dùng trong thử nghiệm của mình. Thư rác được thu thập từ hai nguồn: nguồn thứ nhất là những thư rác mà các tác giả nhận được qua địa chỉ thư của mình tại Việt nam. Nguồn thứ hai là những thư rác do quản trị phát hiện tại mail server của cơng ty FPT (mail.fpt.com.vn). Thư bình thường là những thư mà các tác giả nhận được thơng qua hịm thư mail.gdt.gov.vn. Đối với các thư bình thường nhận được, trong trường hợp thư nhận từ cùng một nguồn qua nhiều phiên gửi và reply thì đối với những thư gửi sau sẽ được xố phần đã gửi từ trước, chỉ giữ lại nội dung thư nhận được cuối cùng. Đối với những thư bao gồm cả văn bản và hình ảnh, chỉ cĩ phần văn bản được sử dụng, phần hình ảnh bị bỏ qua khơng xem xét. Các thơng số chính về bộ dữ liệu được thống kê: Tổng thư: 700 Thư rác: 236 Thư thường: 464 2. Biểu diễn nội dung thư dưới dạng mơ hình boolean Để cĩ thể sử dụng kỹ thuật học máy và xác suất thống kê, nội dung thư cần được biểu diễn dưới dạng thuận tiện cho việc áp dụng thuật tốn học máy. Các phương pháp lọc thư bằng cách tự động phân loại theo nội dung đều sử dụng cách biểu diễn thư dưới dạng véctơ. Mặc dù cĩ nhiều cách xây dựng véctơ nhưng cách đơn giản nhất là mơ hình boolean. Nguyên tắc cơ bản của phương pháp này là khơng quan tâm tới vị trí xuất hiện các từ hay cụm từ 46 trong thư mà coi thư như một tập hợp khơng cĩ thứ tự các từ. Mỗi thư khi đĩ được biểu diễn bởi một véctơ. Số phần tử của véctơ bằng số lượng từ khác nhau trên tồn bộ tập dữ liệu huấn luyện. Cĩ nhiều cách tính giá trị các phần tử của vectơ. Cách đơn giản nhất là sử dụng giá trị nhị phân: mỗi phần tử của véctơ bằng 1 hay 0 tuỳ thuộc vào từ tương ứng cĩ xuất hiện trong thư tương ứng với véctơ hay khơng. Giả sử cĩ một tập gồm m văn bản   @; @E   @M. Mỗi văn bản gịm n từ khĩa €  L; LE   LM. Gọi   $h là ma trận trọng số, trong đĩ wij là trọng số của từ khĩa ti trong văn bản dj. Mơ hình Boolean là mơ hình đơn giản nhất, trong đĩ trọng số các từ trong văn bản là 0 hoặc 1. Khi đĩ, mỗi văn bản sẽ được biểu diễn dưới dạng tập hợp như sau: di={tij}, trong đĩ tij là từ ti cĩ trọng số wij trong văn bản dj là 1.[1] Các phương pháp phức tạp hơn thường dựa vào tần suất xuất hiện của từ trong thư. Từ xuất hiện càng nhiều thì phần tử tương ứng của vectơ cĩ giá trị càng lớn và ngược lại. Trên các tập dữ liệu mẫu thực, số lượng từ khác nhau cĩ thể lên tới hàng chục nghìn tương ứng với số lượng phần tử trong mỗi véctơ. Trong các phần sau sẽ đề cập tới kỹ thuật giảm bớt số lượng từ dùng để biểu diễn thư. Phương pháp biểu diễn thư sử dụng boolean trình bày ở trên bỏ qua thơng tin về vị trí xuất hiện và thứ tự các từ trong thư. Những thơng tin này cĩ thể cĩ giá trị quan trọng trong việc phát hiện thư rác. Tuy nhiên, do đơn giản, phương pháp boolean vẫn là phương pháp biểu diễn nội dung thư thơng dụng nhất, mặc dù cĩ nhược điểm vừa nêu. Trong nghiên cứu này, luận văn cũng sử dụng phương pháp boolean và các mở rộng của phương pháp này để biểu diễn nội dung thư điện tử: 47 Tập các từ trong tất cả tài liệu sẽ được sắp xếp thành từ điển và được đánh chỉ số theo thứ tự tăng dần. Thư sẽ được biểu diễn dưới dạng vector, biểu diễn thứ tự tăng dần các chỉ số của các từ cĩ trong thư đĩ. Dưới đây là một ví dụ đơn giản minh hoạ cho cách biểu diễn nội dung nĩi trên. Dữ liệu huấn luyện bao gồm bốn thư, trong đĩ hai thư là thư rác và hai là thư bình thường. Nội dung các thư được cho trong bảng 4.1. Trên bảng 4.3. là biểu diễn véctơ cho các thư trong bảng 4.1. Số TT Nội dung Nhãn 1 mua và trúng thưởng Rác 2 mua một tặng một Rác 3 anh mua rồi Bình thường 4 vừa gửi xong Bình thường Bảng 4.1. Ví dụ nội dung của 4 thư. Từ các thư trên ta sắp xếp các từ trong thư dưới sạng từ điển và đánh chỉ số như sau: Bảng 4.2 Từ điển từ và chỉ số cho dữ liệu trong bảng 4.1 Từ Chỉ số anh 1 gửi 2 một 3 mua 4 rồi 5 tặng 6 thưởng 7 trúng 8 và 9 vừa 10 xong 11 48 Số TT anh gửi một Mua rồi tặng thưởng Trùng và vừa xong 1 4 7 8 9 2 3 4 6 3 1 4 5 4 2 10 11 Bảng 4.3. Biểu diễn véctơ cho dữ liệu trong bảng 4.1 Như vậy các thư sẽ được biểu diễn như sau: Thư1 ={4, 7, 8, 9} Thư2={3, 4, 6} Thư3={1, 4, 5} Thư4={2, 10, 11} 4.3.3. Xây dựng chương trình biểu diễn và tiền xừ lý dữ liệu a. Mơi trường cài đặt: Chương trình được cài đặt trên các mơi trường ứng dụng sau: - Mơi trường cài đặt ứng dụng: Visual Studio .NET - Ngơn ngữ sử dụng: Visual C# b. Chức năng của chương trình: + Tiền xử lý dữ liệu: tách từ trong các thư thành các từ đơn, loại bỏ đi các ký tự đặc biệt, loại bỏ các từ dừng (stop-word). Đưa các từ vào trong từ điển, đánh chỉ số cho các từ. + Xử lý dữ liệu tạo file dữ liệu đầu vào cho các chương trình thực nghiệm. c. Kết quả cài đặt chương trình: 49 - Giao diện chính của chương trình: Hình 4.3. Giao diện chính của chương trình Lựa chọn thư mục chứa dữ liệu để lấy dữ liệu đưa vào chương trình xử lý: Hình 4.4 Giao diện lựa chọn thư mục chứa dữ liệu Nhấn nút “Làm sạch dữ liệu” để loại bỏ các ký tự đặc biệt trong thư: ký tự xuống dịng, loại bỏ các từ dừng (stop word). Quá trình làm sạch dữ liệu sau khi hồn thành sẽ thơng báo như trong hình 4.5 50 Hình 4.5 Thơng báo quá trình làm sạch dữ liệu đã thành cơng Bấm nút “Xứ lý” để biểu diễn dữ liệu về dạng vector thể hiện trong các file cĩ đuơi chấm là snow và libsvm. Trên màn hình chương trình cũng thể hiện dữ liệu huấn luyện và kiểm tra (hình 4.6). Trong file huấn luyện gồm cĩ 323 thư thường và 167 thư rác. Trong file kiểm tra cĩ 141 thư thường và 69 thư rác. Kết quả của chương trình là tạo ra các file cĩ đuơi .snow và .libsvm chính là dữ liệu thử nghiệm tương ứng cho các chương trình Snow và AcitveExperimenter. Dữ liệu ra được lưu trong thư mục đã chọn ở đầu chương trình. 51 Hình 4.6 Giao diện thơng báo kết quả xử lý dữ liệu 4.3.4. Kết quả thử nghiệm Hai phương pháp phân loại được thử nghiệm bao gồm chương trình Snow cài đặt perceptron và active SVM. Chương trình Snow Qua trìnhhử nghiệm được thực hiện qua hai bước: bước huấn luyện và bước kiểm tra. Bước huấn luyện gõ lệnh: ../snow –train –I traindata.snow –F NetworkFile.net –A archfile Bước kiểm tra gõ lệnh: ../snow –test –I testdata.snow – F NetworkFile.net Kết quả màn hình: kết quả của chương trình được thể hiện trong hình 4.7 52 Hình 4.7. Kết quả chạy thuật tốn Perceptron Chương trình ActiveExperimenter Thử nghiệm cũng được chia thành 2 giai đoạn: giai đoạn huấn luyện và kiểm tra. Thực nghiệm sử dụng phương pháp đánh giá 10 fold-cross validation: tồn bộ dữ liệu được chia ngẫu nhiên thành 10 nhĩm kích thước tương đương nhau. Bộ phân loại được huấn luyện trên chín nhĩm sau đĩ được kiểm tra trên một nhĩm cịn lại. Lặp lại 10 lần với 10 nhĩm dùng để kiểm tra, sau đĩ lấy trung bình cộng kết quả. Để chạy chương trình ta gõ lệnh: experimenter.bat thay đổi file dữ liệu hay các thơng số đầu vào chương trình ta cĩ thể sửađổi trong file config.xml trong thư mục ActiveExperimenter\Config. Trong file config.xml ta cĩ thể lựa chọn thuật tốn truy vấn là SIMPLE, SELF_CONF, KFF… Nếu để mặc định sẽ được hiểu là thuật tốn SIMPLE đã trình bày trong chương 3. File config.xml cĩ cấu trúc như trong hình 4.8: 53 Hinh 4.8 Cấu trúc file cấu hình của chương trình ActiveExperimenter Màn hình sau khi chạy chương trình với thuật tốn SIMPLE ta cĩ kết quả thể hiện trong hình 4.9 Hình 4.9. Kết quả chạy thuật tốn SIMPLE 54 Khi lựa chọn thuật tốn là thuật tốn SELF_CONF để thử nghiệm cũng trên tập dữ liệu đĩ, thu được kết quả ở hình 4.10: Hình 4.10. Kết quả chạy thuật tốn SELF_CONF 55 Khi sử dụng thuật tốn KFF ta thu được kết quả như hình 4.11. Hình 4.11. Kết quả chạy thuật tốn KFF Cuối cùng là chạy thử nghiệm trên thuật tốn BALANCE_EE ta thu được kết quả như hình 4.12: Hình 4.12. Kết quả chạy thuật tốn BALANCE_EE 56 Trong bốn thuật tốn đã sử dụng thực nghiệm trong chương trình ActiveExperiment thì cĩ ba thuật tốn đều cho kết quả cao và tương tự ngang nhau. Riêng thuật tốn KFF thì cho độ chính xác rất thấp chưa đạt 50%. Kết quả được thể hiện trong bảng 4.4 Ta cĩ bảng kết quả của các thuật tốn SVM active như trong bảng 4.4: Lần truy vấn SIMPLE SELF_CONF KFF BALANCE_EE 1 63.72 61.79 61.03 61.03 2 80.64 81.25 67.82 73.72 3 62.82 77.31 67.05 63.97 4 84.10 87.82 63.33 74.74 5 69.49 84.87 63.33 79.74 6 81.54 88.21 66.67 82.05 7 76.28 90.13 60.77 74.10 8 86.92 87.31 57.56 83.21 9 87.44 91.54 57.05 83.33 10 87.82 92.18 50.38 80.64 11 90.13 92.65 53.21 86.15 12 90.13 92.82 52.05 85.64 13 91.67 92.56 52.56 92.95 14 92.95 92.18 52.44 90.64 15 93.33 92.95 50.90 92.95 16 89.23 93.82 47.95 86.67 17 92.95 92.56 45.26 92.82 18 93.21 92.56 46.54 94.10 19 93.82 93.08 47.69 93.46 20 93.08 92.31 46.28 93.72 Bảng 4.4 Kết quả chạy qua 20 lần truy vấn của các thuật tốn Cả trong hai chương trình thực nghiệm bước truy vấn và phản hồi người dùng được chương trình hĩa trong quá trình thực nghiệm. Khi chương trình chọn một dữ liệu thư điện tử để truy vấn nhãn, thì nhận được sự phản hồi đã được thể hiện thơng qua là dữ liệu thư đĩ đã được gán nhãn sẵn trong tập dữ liệu huấn luyện. 57 4.5.2. Nhận xét về kết quả thử nghiệm Với dữ liệu huấn luyện trên đây, Snow đạt độ chính xác là 99%, cịn chương trình experimenter chỉ cho độ chính xác là 87,82% ở lần truy vấn thứ 10. Khi số lần truy vấn càng nhiều thì độ chính xác càng cao, thể hiện ở các lần truy vấn thứ 15-20 đạt độ chính xác là 93,08 %.Tuy nhiên điều này cũng đã khẳng định được tính hiệu quả cao của thuật tốn perceptron và acitve SVM. Trong số hai phương pháp phân loại được sử dụng, phương pháp perceptron cho kết quả tốt nhất, tuy nhiên phương pháp active SVM cĩ ưu thế hơn do cĩ độ phức tạp tính tốn thấp hơn nhiều. Thời gian chạy của chương trình snow qua một vịng huấn luyện, kiểm tra mất 1.37s, tuy nhiên với chương trình ActiveExperimenter chạy qua 10 vịng huấn luyện, mỗi vịng sẽ truy vấn 20 lần, thời gian chạy chỉ cĩ 0.91s, trung bình mỗi vịng mất khoảng 0.09s , điều này khẳng định độ phức tạp tính tốn thuật tốn của phương pháp active SVM thấp dù độ chính xác thì chưa cao nhất cĩ thể. Trong khi thuật tốn Perceptron cho độ chính xác cao, nhưng thời gian chạy cịn khá lâu. Đối với thuật tốn acitve SVM cĩ sự hạn chế là sử dụng hàm hàm nhân Radial basis function mà chưa sử dụng các hàm nhân khác, chẳng hạn như hàm nhân đa thức. Điều này cĩ thể là một trong những nguyên nhân dẫn đến độ chính xác của thuật tốn chưa được cao. 4.4 Kết luận Chương này đã giới thiệu bài tốn lọc thư rác và áp dụng phươg pháp học tích cực và trong bài tốn. Trong chương này cũng giới thiệu chương trình xử lý dữ liệu và chuẩn hĩa dữ liệu về dạng vector và đầu vào cho các tool thực nghiệm. Thực nghiệm các tool cĩ cài đặt các thuật tốn học tích cực trên tập dữ liệu tạo được. Phân tích đánh giá và nhận xét kết quả thực ngiệm. 58 KẾT LUẬN Những vấn đề đã được giải quyết trong luận văn Sau một thời gian thu thập tài liệu, khảo sát và phân tích nội dung một số bài báo được đề xuất trong lĩnh vực nghiên cứu về học máy, bản luận văn này là sự tổng hợp những nét chính trong học tích cực và là một hướng giải quyết cho bài tốn lọc thư rác. Sau đây là những điểm chính mà luận văn đã tập trung giải quyết. ü Tìm hiểu phương pháp học tích cực, so sánh với học thụ động, tìm ra ưu điểm của từng phương pháp và các trường hợp ứng dụng phù hợp. ü Tìm hiểu phương pháp học tích cực dựa vào perceptron, thuật tốn học perceptron đã được cải tiến của Dagupsta đề xuất năm 2005. Thuật tốn được xây dựng lên từ việc đưa sự cải tiến bước cập nhật perceptron của Morkin vào thuật tốn perceptron chuẩn cĩ 2 bước lọc và bước cập nhật. ü Tìm hiểu phương pháp học tích cực dựa vào SVM được Simon Tong đề xuất năm 2001, các thuật tốn truy vấn: Simple Margin, MaxMin Margin và Ratio Margin. ü Ứng dụng các phương pháp học tích cực đã tìm hiểu áp dụng vào bài tốn lọc thư rác, xây dựng mơ hình cho bài tốn lọc thư rác. Với các mơ hình khơng sử dụng phương pháp học tích cực (mơ hình thụ động), để huấn luyện được bộ học, cần một lượng lớn dữ liệu huấn luyện, vì vậy mà tốn kém trong chi phí và thời gian. Trong mơ hình lọc thư rác tích cực sẽ làm giảm được lượng dữ liệu huấn luyện này. Hơn nữa, mơ hình lọc thư thụ động sẽ phải mất chi phí nhiều hơn và phải được huấn luyện lại để cĩ thể phát hiện được các thư rác ngày một phát triển tinh vi hơn, thì bộ lọc thư tích cực lại cĩ khả năng tự cập nhật lại lại mơ hình khi nhận được thơng tin cần thiết từ việc đưa ra truy vấn cho dữ liệu đã được lựa chọn phù hợp từ truy vấn và câu phản hồi trước đĩ. Vì vậy mà bộ lọc thư tích cực sẽ khơng cần mất nhiều chi phí cho việc huấn luyện lại, và giảm tập dữ liệu huấn luyện cho mơ hình. Bộ lọc 59 thư rác đã trình bày trong luận văn đạt độ chính xác và hiệu quả cao. Thực nghiệm đạt 99% đối với thuật tốn perceptron và 93.7% đối với các thuật tốn active SVM. ü Thu thập dữ liệu thư, spam và xây dựng chương trình xử lý dữ liệu thực tế thành dữ liệu đầu vào cho các thử nghiệm. Luận văn xây dựng thử nghiệm trên các tool sẵn cĩ cài đặt các thuật tốn perceptron và active SVM mà luận văn đã giới thiệu. Cơng việc nghiên cứu trong tương lai Cải tiến thuật tốn active SVM để sử dụng các hàm nhân khác nhằm nâng cao chất lượng phân lớp. Tiếp tục tìm hiểu các phương pháp xử lý nhằm làm tăng chất lượng phân lớp, đồng thời xử lý các thư cĩ nội dung khơng phải là văn bản chằng hạn như hình ảnh, … Ứng dụng vào một hệ thống mail server trong một tổ chức để lọc thư cho cán bộ/nhân viên. 60 TÀI LIỆU THAM KHẢO Tiếng Việt [1] Hà Quang Thụy, Phan Xuân Hiếu, Đồn Sơn, Nguyễn Trí Thành, Nguyễn Thu Trang, Nguyễn Cẩm Tú (2009), Giáo trình khai phá dữ liệu Web, Nhà xuất bản giáo dục Việt Nam. [2] Nguyễn Thanh Thủy (2001), Khai phá dữ liệu, Nhà xuất bản Kỹ thuật và ứng dụng. Tiếng Anh [3] A. Wald (1950). Statistical decision functions. Wiley, New York [4] A. Blum, A. Frieze, R. Kannan, and S. Vempala (1996). A polynomial-time algorithm for learning noisy linear threshold functions. In Proc. 37th Annual IEEE Symposium on the Foundations of Computer Science. [5] B. Busser, R. Morante (2005) ‘Designing an active learning based system for corpus annotation’, In Procesamiento del Lenguaje Natural, núm. 35, pp. 375-381. [6] Burr Settles (2008) Curious Machines: Active Learning with Structured Instances. Ph.D. dissertation, University of Wisconsin–Madison, USA. [7] Burr Settles (2009) ‘Active learning literature survey’ Computer Sciences Technical Report 1648, University of Wisconsin–Madison. [8] Burr Settles, M. Craven (2008) ‘An analysis of active learning strategies for sequence labeling tasks’ In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 1069–1078. [9] DC.A. Thompson, M.E. Califf and R.J. Mooney (1999) ‘Active learning for natural language parsing and information extraction’, In Proceedings of the 16th International Conference on Machine Learning, pp. 406-414. [10] C. Campbell, N. Cristianini, & A. Smola (2000). Query learning with large margin classifiers. Proceedings of the Seventeenth International Conference on Machine Learning. [11] C. E. Shannon, (1948) ‘A mathematical theory of communication’ Bell System Technical Journal, 27:379-423,623-656. [12] C.J. Burges. A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery, 1999. [13] C. Nakajima, I. Norihiko, M. Pontil & Poggio (2000). Object recognition and detection by a combination of support vector machine and rotation 61 invariant phase only correlation. Proceedings of International Conference on Pattern Recognition. [14] D.D. Lewis, W. Gale (1994) ‘A sequential algorithm for training text classifiers’, In Proceedings of the ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 3-12. [15] D.D. Lewis, J. Catlett (1994) ‘Heterogeneous Uncertainty Sampling for Supervised Learning’ In Proceedings of the 11th International Conference on Machine Learning, pp.148-156. [16] D. Hakkani-Tür, G. Riccardi and A. Gorin (2002) ‘Active learning for automatic speech recognition’ In Proceedings of ‘International Conference on Acoustics, Speech and Signal Processing (ICASSP), Orlando, FL. [17] F. Rosenblatt (1958). The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65:386–407. [18] G. Tur, D. Hakkani-Tür and R.E. Schapire (2005) ‘Combining active and semisupervised learning for spoken language understanding’ Speech Communication, 45(2):171–186. [19] G. Tur, R.E. Schapire and D. Hakkani-Tür (2003) ‘Active learning for spoken language understanding’ In Proceedings of International Conference on Acoustics, Speech and Signal Processing (ICASSP), Hong Kong. [20] H. Seung, M. Opper & H. Sompolinsky (1992). Query by committee. Proceedings of Computational Learning Theory. [21] J. Baldridge, M. Osborne (2004) ‘Active learning and the total cost of annotation’, In Proceedings of the Conference on Empirical Methods in Natural Language Processing, Forum Convention Center, Barcelona, Spain, pp. 9-16 [22] J. Zhu, H. Wang, E. Hovy (2008a) ‘Learning a stopping criterion for active learning for word sense disambiguation and text classification’ In Proceedings of the 3rd International Joint Conference on NLP (IJNLP), Heydarabad, India. pp. 366-372. [23] J. Zhu, H. Wang, T. Yao and B. Tsou (2008b) ‘Active learning with sampling by uncertainty and density for word sense disambiguation and text classification’ In Proceedings of the 22nd International Conference on Computational Linguistics (CoLing) pp. 1137-1144. [24] LeCun, Jackel, Bottou, Brunot, A., Cortes, C., Denker, J. S., Drucker, H., Guyon, I., Muller, U. A., Sackinger, E., Simard, P., & Vapnik (1995). Comparison of learning algorithms for handwritten digit recognition. International Conference on Artificial Neural Networks, Paris. [25] M. Steedman, R. Hwax, S. Clark, M. Osborne, A. Sarkar, J. Hockenmaier, P. Ruhleny, S. Bakerz, J. Crimy (2003) ‘Example selection for bootstrapping statistical parsers’ In Proceedings of the Human Language Technology 62 Conference / North American Chapter of the Association for Computational Linguistics (HLT/NAACL), Edmonton, Canada. [26] R. Hwa, (2000) ‘Sample selection for statistical grammar induction’ In Proceedings of the 2000 Joint SIGDAT Conference on EMNLP and VLC, Hong Kong, China, pp. 45.52. [27] R. Hwa, M. Osborne and A. Sarkar and M. Steedman (2003) ‘Corrected cotraining for statistical parsers’ In Proceedings of the ICML Workshop: The Continuum from Labeled to Unlabeled Data. pp. 95-102. [28] R. Herbrich, T. Graepel, & C. Campbell (1999). Bayes point machines: Estimating the Bayes point in kernel space. International Joint Conference on Artificial Intelligence Workshop on Support Vector Machines. [29] R. Liere, P. Tadepalli (1997) ‘Active learning with committees for text categorization’ In Proceedings 14th Conference of the American Association for Artificial Intelligence (AAAI), pp. 591-596. [30] S. Agmon (1954). The relaxation method for linear inequalities. Canadian Journal of Math., 6(3):382–392. [31] S.C.H Hoi, R. Jin, M.R. Lyu (2006) ‘Large-scale text categorization by batch mode active learning’ In Proceedings of the International Conference on the World Wide Web, pp. 633–642. [32] S. Dasgupta (2005). Coarse sample complexity bounds for active learning. In Advances in Neural Information Processing Systems 18. [33] S. Dumais, J. Platt, D. Heckerman & M. Sahami (1999). Inductive learning algorithms and representations for text categorization. Proceedings of the Seventh International Conference on Information and Knowledge Management. ACM Press. [34] S. Hampson and D. Kibler (1999). Minimum generalization via reflection: A fast linear threshold learner. Machine Learning, 37(1):51–73. [35] S. Tong and D. Koller. Support vector machine active learning with applications to text classification. Journal of Machine Learning Research, 2:45–66, 2001. [36] S. Tong, (2001) Active Learning: Theory and Applications. Ph.D. dissertation, Stanford University. [37] T. Joachims. Text categorization with support vector machines. Proceedings of the European Conference on Machine Learning. Springer-Verlag, 1999. [38] T. Joachims. Transductive inference for text classification using support vector machines. Proceedings of the Sixteenth International Conference on Machine Learning. Morgan Kaufmann, 1999. 63 [39] T. Mitchell (1982). Generalization as search. Artificial Intelligence. [40] T.S. Motzkin and I.J. Schoenberg (194). The relaxation method for linear inequalities. Canadian Journal of Math., 6(3):393–404. [41] V. Vapnik. Estimation of dependences based on empirical data. Springer Verlag, 1982. [42] V. Vapnik. The nature of statistical learning theory. Springer, New York, 1995. [43] V. Vapnik, (1998). Statistical learning theory. Wiley. [44] Y. Baram, R. El-Yaniv and K. Luz (2004) ‘Online choice of active learning algorithm’ In Journal of Machine Learning Research 5, pp. 255-259 [45] Y. Freund, H. Seung, E. Shamir & N. Tishby (1992). Selective sampling using the Query by Committee algorithm. Machine Learning. Website: [46] [47]