Miề N Ứ Ng D Ụ Ng C Ủ A H Ọ C Tích C Ự C ‌

toán. Để làm được việc lựa chọn mẫu, có một số phương pháp truy vấn độc lập với kịch bản học tích cực đã giới thiệu giới thiệu ở trên.

Trong số các phương pháp truy vấn được sử dụng trong các ứng dụng khác nhau của phương pháp học tích cực, Settles [6][7] đã trình bày việc phân loại hoàn chỉnh nhất và toàn diện nhất cho các phương pháp truy vấn này. Trong đó có hai phương pháp được sử dụng rộng rãi nhất đó là lấy mẫu không chắc chắn và truy vấn dựa trên hội đồng (Query by committee).

2.4.1 Lấy mẫu không chắc chắn‌

Phương pháp lựa chọn mẫu nổi tiếng nhất và đơn giản là "lấy mẫu không chắc chắn" (Uncertainty Sampling) được giới thiệu bởi Lewis và Gale [14]. Trong phương pháp này, bộ học tích cực đưa ra các mẫu tới người sử dụng là không chắc chắn. Xét các dự đoán của bộ phân lớp cho dữ liệu không có nhãn, ta sẽ có một đường biên giữa các mẫu không có thông tin và các mẫu có chứa thông tin. Các mẫu không có thông tin là những mẫu cần có sự dự đoán chắc chắn cao nhất cho việc gán nhãn; vì thế các mẫu kiểu này không phải là hữu ích cho học tích cực và cũng không cần thiết để hỏi nhãn cho chúng. Các mẫu có thông tin là các mẫu mà bộ phân lớp không cần phải có một dự đoán tốt cho việc gán nhãn với sự tự tin cao. Do vậy những dữ liệu có độ chắc chắn thấp hơn sẽ hữu ích cho bộ học tích cực.

Đường biên giữa các mẫu chứa thông tin và mẫu không chứa thông tin có thể được định nghĩa với một số điểm như độ tin cậy của bộ phân lớp cho các nhãn mà nó đã gán. Trong thực tế ‘độ tin cậy’ là sự dự đoán của bộ phân lớp với xác suất cao nhất cho các nhãn của mẫu [5]. Vì nó có thể được nhận ra, nên trong việc lấy mẫu không chắc chắn chỉ có một bộ phân lớp là cần thiết cho mô hình [21].

Có một số cách tính độ tin cậy mà bộ phân lớp sử dụng. Trong số đó, có ‘entropy’ được Shannon [11] đề xuất là một trong những cách phổ biến nhất. Sử dụng entropy là độ tin cậy, các mẫu có entropy cao sẽ là các mẫu chứa thông tin nhiều nhất vì dự đoán của bộ phân lớp cho các mẫu đó là thấp

và các mẫu này sẽ là các ứng cử viên tốt nhất được lựa chọn và đưa ra cho người sử dụng gán nhãn.

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

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

2.4.2 Truy vấn dựa vào hội đồng‌

Seung cùng cộng sự [20] và Freund cùng cộng sự [45] đề xuất một phương pháp truy vấn được sử dụng rộng rãi được gọi là truy vấn dựa vào hội đồng (query by committee). Trong phương pháp này nhiều hơn một bộ phân lớp được sử dụng và mỗi bộ phân lớp cố gắng để lấy các mẫu chứa nhiều thông tin nhất. Trong số các mẫu chứa thông tin được lựa chọn cho mỗi bộ phân lớp, các mẫu mà có độ bất đồng lớn nhất giữa các bộ phân lớp sẽ được lựa chọn và đưa ra cho người sử dụng gán nhãn.

2.5 So sánh học tích cực học thụ động

Bộ học

Một bộ học tích cực thu thập thông tin bằng cách đưa ra các câu truy vấn và nhận lại các câu trả lời. Sau đó nó đưa ra bộ phân lớp hoặc mô hình có thể sử dụng được cho bài toán của mình. Bộ học tích cực khác với bộ học thụ động ở chỗ bộ học thụ động nhận thông tin một cách ngẫu nhiên và sau đó đưa ra bộ phân lớp và mô hình. Một điểm khác nữa là bộ học thụ động chuẩn giống như một sinh viên thu thập thông tin bằng cách chỉ ngồi và lắng nghe giáo viên trong khi bộ học tích cực là người đặt ra câu hỏi cho giáo viên, nghe câu trả lời và hỏi thêm dựa trên câu trả lời của giáo viên. Rất hợp lý khi đưa ra câu hỏi dựa trên câu trả lời trước đó sẽ cho phép bộ học tích cực thực hiện tốt hơn bộ học thụ động.

Thành phần truy vấn

Điểm khác chủ yếu giữa bộ học tích cực và bộ học thụ động là khả năng đặt câu hỏi vào câu hỏi và câu trả lời trước. Khái niệm về câu hỏi và câu trả lời chính xác là gì sẽ phụ thuộc vào các bài toán cụ thể tiếp theo. Khả năng sử dụng phương pháp học tích cực sẽ được lựa chọn tùy vào từng trường hợp, từng bài toán cụ thể.

2.6 Miền ứng dụng của học tích cực‌

Học tích cực được áp dụng trong rất nhiều ứng dụng khác nhau, nhưng đặc biệt gần đây người ta lại chú ý đến phương pháp học tích cực trong lĩnh vực xử lý ngôn ngữ tự nhiên. Ngoài ra học tích cực cũng được sử dụng trong nhiều ứng dụng như:

 Nhận dạng giọng nói (Hakkani-Tür et al., 2002), hiểu ngôn ngữ nói (Tur et al., 2003; 2005).

 Phân tích cú pháp (Thompson và cộng sự, 1999; Hwa, 2000; Tang và cộng sự, 2002;. Hwa và cộng sự, 2003;. Steedman và cộng sự, 2003;. Baldbridge và Osborne, 2003; 2004; 2006; Osborne và Baldridge, 2004, Becker và Osborne, 2005)

 Khai thác thông tin (Thompson et al., 1999; Settles and Craven, 2008), tìm kiếm thông tin (Zhang and Chen, 2002; Yu, 2005),

 Phân lớp tài liệu (Schohn and Cohn, 2000; Roy and McCallum, 2001),

 Lọc thư rác (Sculley, 2008)

 Tìm kiếm hình ảnh (Tong, Simon Tong 2001)

 Phân lớp văn bản (Lewis and Gale, 1994; McCallum and Nigam, 1998; Tong and Koller, 2001; Zhu et al., 2003; Baldbridge and Osborne, 2006; Zhu et al., 2008ab, Lewis and Catlett, 1994; Liere and Tadepalli, 1997; Hoi et al., 2006),

 Phân đoạn tài liệu (Settles and Craven, 2008),

 Phân đoạn từ vựng (Sassano, 2002), word sense disambiguation (Fujii et al., 1998; Dang, 2004; Chen et al., 2006; Chan and Ng, 2007; Zhu and Hovy, 2007; Zhu et al., 2008ab),

 Nhận dạng chữ số viết tay (Zhu et al., 2003),

 Dịch máy (machine translation) (Haffari and Sarkar, 2009; Haffari et al., 2009),

 Nhận dạng thực thể ghi tên (Shen et al., 2004; Laws and Schütze, 2008),

2.7 Kết luận‌

Trong chương này đã trình bày cơ sở lý thuyết của học tích cực. Giới thiệu học tích cực là gì, phương pháp học tích cực, các kịch bản và các phương pháp truy vấn.

Tóm lại, phương pháp học tích cực được tóm tắt lại như sau: Đầu tiên chúng ta chọn một mô hình và độ tổn thất mô hình thích hợp với bài toán học. Sau đó chúng ta cũng chọn một phương pháp cho việc tính độ tổn thất mô hình tiềm năng đưa ra câu truy vấn tiềm năng. Với mỗi câu truy vấn chúng ta đánh giá độ tổn thất tiềm năng và chúng ta lựa chọn để đưa ra câu truy vấn, câu truy vấn này sẽ đưa ra được độ tổn thất mô hình tiềm năng thấp nhất.

CHƯƠNG III - MỘT SỐ THUẬT TOÁN HỌC TÍCH CỰC‌

Chương này sẽ giới thiệu một số thuật toán học tích cực. Cụ thể sẽ đi vào giới thiệu hai thuật toán phổ biến là perceptron và Active SVM.

3.1 Học tích cực dựa trên perceptron‌

3.1.1 Giới thiệu‌

Một trong những phương pháp tiếp cận ra đời sớm nhất cho vấn đề phân lớp tuyến tính trong học máy là thuật toán Perceptron. Perceptron được Rosenblatt đề xuất năm 1958 [17], chiếm một vị trí quan trọng trong lịch sử của các thuật toán nhận dạng mẫu.Perceptron là một bộ phân lớp tuyến tính và là một phần của học máy kể từ những năm 1958 và đã có nhiều phân tích lý thuyết về nó. Phần này sẽ trình bày thuật toán học tích perceptron chuẩn và thuật toán perceptron tích cực có cải tiến bước cập nhật do Dasgupta đề xuất năm 2005 [32].

3.1.2 Thuật toán perceptron‌

Cho tập dữ liệu học D = {(xi, yi), i = 1, … , n} với xi C Rmvà yi C

{—1, +1} là một số nguyên xác định xi là dữ liệu dương (+1) hay âm (-1). Một tài liệu xi được gọi là dữ liệu dương nếu nó thuộc lớp ci; xi được gọi là dữ liệu âm nếu nó không thuộc lớp ci. Bộ phân lớp tuyến tính được xác định bằng siêu phẳng chia dữ liệu thành vào các lớp thuộc tính. Tập các giả thiết như vậy ta có:

{x: r(x) = wT x + wO = 0} (3.1)

Trong đó w C Rmvà wO C R là các hệ số có thể điều chỉnh đóng vai trò là tham số của mô hình. Hàm phân lớp nhị phân h: Rm → {0,1}, có thể thu

được bằng cách xác định dấu của ƒ(x):

1 nếu r(x) Σ 0

h = {

0 nếu r(x) € 0

(3.2)

Như vậy việc học mô hình phân lớp chính là việc xác định siêu phẳng từ dữ liệu. Với thuật toán này, mỗi dữ liệu được xem là một điểm trong mặt phẳng. Dữ liệu học là tách rời tuyến tính (linearly separable) nếu tồn tại một siêu phẳng sao cho hàm phân lớp phù hợp với tất cả các nhãn, tức là yi r(xi) Σ 0 với mọi i = 1,...,n. Với giả thuyết này, Rosenblatt đã đưa ra một

thuật toán lặp đơn giản để xác định siêu phẳng:

Mục đích của thuật toán Perceptron là tìm ra được một siêu phẳng bằng cách làm giảm thiểu đi khoảng cách của các điểm dữ liệu phân lớp nhầm (misclassified) tới đường biên quyết định. Nó bắt đầu với việc dự đoán các tham số ban đầu cho mặt phẳng phân cách, và sau đó khi có những sai lầm xảy ra thì nó cập nhật lại việc dự đoán trước đó.

Perceptron

Khởi tạo các giả thiết ban đầuv0

For t=0 to n do

Dự đoán: if rt. xt≤ 0 then y^t= SGN(rt. xt) else y^t= —SGN(rt. xt)

Bước lọc: quyết định hỏi nhãn yt của điểm xt

Cập nhật:

If yt(rt. xt) ≤ 0 then rt+1 = rt + yt. xt Bước lọc phù hợp

else rt+1 = rt

Hình 3.1 Thuật toán perceptron chuẩn [32]

Thuật toán chọn tập các giả thiết như là mô hình của thuật toán và lỗi tổng quát của mỗi giả thiết làm độ tổn thất của mô hình. Với giả thiết r bất kỳ thuộc Rd sẽ có miền lỗi = {x C S|SGN(rt. x) G SGN(u. x)}, u là vector đơn vị. Do đó thuật toán sẽ lựa chọn các dữ liệu sao cho giảm miền lỗi của giả thiết càng nhiều càng tốt.

Bước cập nhật

Rosenblatt [17] là người đầu tiên phân tích hoạt động hội tụ của bước cập nhật perceptron, nó bao gồm qui tắc đơn giản sau đây:

if (xt, yt) bị phân lớp nhầm (misclassiﬁed), then rt+1 = rt + ytxt.

Vì vậy, thay vì sử dụng một biến của nguyên tắc cập nhật, theo Motzkin và Schoenberg [40] đã cải tiến bước cập nhật theo quy tắc sau:

if (xt, yt) bị phân lớp nhầm, then vt+1 = vt −2(vt . xt)xt

Giả sử xt đã chuẩn hóa theo đơn vị chiều dài. Lưu ý rằng bản cập nhật cũng có thể viết như vt+1 = vt+2yt|vt . xt| xt, chỉ khi bản cập nhật được thực hiện trên những sai lầm, trong trường hợp này theo định nghĩa yt SGN (vt . xt). Vì vậy Motzkin và Schoenberg [40] đang chia mức độ các bản cập nhật sau của perceptron chuẩn theo một thừa số 2|vt .xt| để tránh những dao động gây ra bởi các điểm gần một nửa không gian đại diện bởi các giả thuyết hiện thời. Motzkin và Schoenberg đã giới thiệu quy tắc này, trong bối cảnh giải quyết các bất đẳng thức tuyến tính, và gọi nó là phương pháp "phản xạ" (Reflexion). Sau đó, Hampson và Kibler [34] áp dụng nó để học tập bộ phân tách tuyến tính, trong một khuôn khổ phân tích khác với chúng ta. Cùng một quy tắc, nhưng không có tham số 2, đã được sử dụng trong nhiều nghiên cứu trước đây [4] nghiên cứu về việc học các bộ phân lớp tuyến tính từ dữ liệu nhiễu, trong một thiết lập khối. Hai ông có thể chỉ ra rằng công thức của họ có sự thực hiện tổng quát trong một thiết lập giám sát (không tích cực).

Bước lọc

Với giới hạn mà thuật toán đã đưa ra, thì luật lọc tự nhiên là truy vấn các điểm xt khi |vt . xt| nhỏ hơn ngưỡng st. Sự lựa chọn st là rất quan trọng. Nếu nó là quá lớn, sau đó chỉ một phần nhỏ rất ít các điểm đã truy vấn sẽ thực sự bị phân lớp sai - hầu như tất cả các nhãn sẽ bị lãng phí. Nói cách khác, nếu st quá bé, thì thời gian chờ đợi cho một truy vấn có thể khá cao, và khi một bản cập nhật thực sự được thực hiện, thì độ lớn của nó có thể lại rất nhỏ.

Vì vậy, tác giả thiết lập ngưỡng cho phù hợp: tác giả bắt đầu với st có giá trị cao, và chia nó cho 2 cho đến khi đạt được mức mà có đủ bộ phân lớp sai các điểm đã truy vấn. Áp dùng chiến lược này vào bản cập nhật Perceptron đã chỉnh sửa, chúng ta nhận được một thuật toán học tích cực (hình 3.5) với

độ phức tạp nhãn 0˜(d log 1), tạo ra 0˜(d log 1) lỗi và có lỗi ≤ε.

s s

3.1.3 Cải tiến bước cập nhật perceptron‌

Phần này mô tả một thuật toán Perceptron đã đượcc cải tiến. Không giống như Perceptron chuẩn, thuật toán Perceptron cải tiến đảm bảo rằng vt.u tăng nghĩa là lỗi của vt giảm đơn điệu. Một sự khác biệt nữa của bản cải tiến chuẩn (so với các bản khác) là độ lớn của các giả thuyết hiện thời luôn luôn là

1. Điều này rất thuận lợi cho việc phân tích.

Perceptron cải tiến

chiều d và số lần cập nhật M

r1 = x1. y1 --với dữ liệu đầu tiên (x1, y1)

For t=1 to M:

(xt, yt) là dữ liệu tiếp theo với y(x, rt) € 0 rt+1 = rt — 2(rt. xt)xt

Hình 3.2 Thuật toán cải tiến percepron chuẩn