Khóa luận Mô hình maximum entropy và ứng dụng

a & Vincent J. Della Pietra, 1996] và một số nguồn khác. Dưới đấy là những cơ sở lý thuyết cơ bản về mô hình cực đại entropy. Về cách xây dựng mô hình, nguyên lý cực đại entropy, cách tính các phân phối xác suất và thuật toán tính trọng số cũng như lựa chọn các đặc trưng cho bài toán phân loại văn bản. 3.1 Tổng quát mô hình cực đại entropy Giả thiết rằng chúng ta muốn mô hình hóa một hệ thống dịch tự động bằng việc lựa chọn những từ thích hợp trong tiếng Pháp mà nó được dịch với nghĩa là “in” trong tiếng Anh. Xác suất mô hình (p) của hệ thống dịch tự động cho mỗi từ hay cụm từ tiếng Pháp f là một ước lượng p(f) của xác suất mà hệ thống sẽ lựa chọn f được dịch với nghĩa là “in” trong tiếng Anh. Để ước lượng được giá trị của p, chúng ta tập hợp một số lượng lớn các mẫu điển hình của hệ thống. Mục đích cuối cùng là thu được tập các sự kiện tạo lên quyết định từ những mẫu ở trên (nhiệm vụ đầu tiên), tập các sự kiện đó sẽ giúp chúng ta xây dựng mô hình cho bài toán này (nhiệm vụ thứ hai). Chúng ta có thể tập hợp được một danh sách các khả năng có thể được dịch từ mẫu điển hình. Ví dụ như, chúng ta có thể tìm ra được những từ (cụm từ) mà hệ thống dịch luôn luôn lựa chọn trong số 5 từ (cum từ) tiếng Pháp sau đây: dans, en, à, au cours de, pendant. Với những thông tin này, chúng ta có thể dùng làm ràng buộc đầu tiên trong xác suất mô hình (p) của chúng ta: p(dans) + p(en) + p(à) + p(au cours de) + p(pendant) = 1 Phương trình này thể hiện tính thống kê đầu tiên trong bài toán của chúng ta; bây giờ chúng ta đã có thể xử lý để tìm ra mô hình phù hợp mà nó tuân theo phương trình này. Tất nhiên, có vô số các xác suất mô hình (p) mà nó thỏa mãn ràng buộc trên. Một mô hình mà thỏa mãn ràng buộc trên có thể là p(dans) = 1; nói cách khác, mô hình luôn luôn dự đoán đó là “dans”. Mô hình khác tuân theo ràng buộc này dự đoán “pendant” với xác suất là ½, và “à” với xác suất là ½. Nhưng theo cảm giác của chúng ta thì cả hai mô hình này đều không ổn cho lắm: hệ thống dịch luôn luôn lựa chọn 1 trong số 5 từ (cụm từ) tiếng Pháp, và làm thế nào chúng ta có thể chứng minh mỗi phân phối xác suất đó là đúng? Mỗi mô hình mới chỉ dừng lại ở mức thừa nhận, mà không có sự chứng minh bằng thực nghiệm rằng điều đó là đúng. Theo cách khác, có 2 mô hình cho rằng có nhiều hơn so với những gì chúng ta thực sự biết về bài toán tạo lên hệ thống dịch. Tất cả những gì chúng ta biết là cái mà hệ hệ thống lựa chọn loại trừ trong số 5 từ (cụm từ) tiếng Pháp; với cách này, tất cả những mô hình mang tính trực giác là như sau: p(dans) = 1/5 p(en) = 1/5 p(à) = 1/5 p(au cours de) = 1/5 p(pendant) = 1/5 Với mô hình này, nó phân bố tổng xác suất ngang bằng nhau trong số 5 từ (cụm từ) có thể được lựa chọn để dịch, là mô hình đều nhất phụ thuộc vào các hiểu biết của chúng ta. Tuy nhiên không phải là giống nhau hoàn toàn; mà mô hình sẽ cấp một xác suất ngang nhau cho mọi từ (cụm từ) tiếng Pháp có thể được dịch. Chúng ta có thể hy vọng rằng có thể tổng hợp được nhiều hơn những thông tin xung quanh hệ thống dịch từ mẫu điển hình của chúng ta. Giả thiết rằng chúng ta nhận thấy hệ thống dịch lựa chọn mỗi từ (cụm từ) “dans” hay “en” là 30% trong mỗi lần lựa chọn. Chúng ta có thể sử dụng thông tin này cho việc cập nhập mô hình của chúng ta trong bài toán dịch bằng cách yêu cầu xác suất mô hình (p) thỏa mãn 2 ràng buộc sau: p(dans) + p(en) = 3/10 p(dans) + p(en) + p(à) + p(au cours de) + p(pendant) = 1 Một lần nữa có nhiều phân phối xác suất phù hợp với 2 ràng buộc trên. Trong trường hợp không có sự hiểu biết nào khác, một sự lựa chọn hợp lý cho xác suất mô hình (p) là ngang bằng nhau nhất có thể, sự phân phối mà nó phân bố các xác suất ngang bằng nhất có thể, phụ thuộc vào các ràng buộc sau: p(dans) = 3/20 p(en) = 3/20 p(à) = 7/30 p(au cours de) = 7/30 p(pendant) = 7/30 Chúng ta kiểm tra lại dữ liệu nhiều lần, và lần này nhận thấy sự kiện sau: trong một nửa các trường hợp, hệ thống dịch lựa chọn cả hai từ (cụm từ) “dans” hay “à”. Chúng ta có thể kết hợp thông tin này vào mô hình của chúng ta như một ràng buộc thứ 3: p(dans) + p(en) = 3/10 p(dans) + p(en) + p(à) + p(au cours de) + p(pendant) = 1 p(dans) + p(à) = ½ Chúng ta có thể một lần nữa tìm ra các xác suất mô hình (p) ngang bằng nhau hơn ứng với các ràng buộc trên, nhưng bây giờ việc lựa chọn không còn là hiển nhiên nữa. Khi chúng ta thêm những ràng buộc phúc tạp, chúng ta gặp phải 2 khó khăn. Thứ nhất, điều đó thực sự là phép lấy trung bình bằng cách ngang bằng nhau, và làm thế nào mà có thể đo được sự ngang bằng nhau của mô hình? Thứ hai, phải xác định được những câu trả lời phù hợp với những câu hỏi, làm thế nào mà tìm được mô hình ngang bằng nhau nhất phụ thuộc vào tập các ràng buộc giống như chúng ta đã miêu tả? Phương pháp cực đại entropy trả lời cho cả 2 câu hỏi trên, chúng ta sẽ chứng minh trong những phần sau. Bằng trực giác, nguyên lý rất đơn giản: toàn bộ mô hình là đã biết và được thừa nhận không có điều gì là chưa biết. Nói một cách khác, cho một tập các sự kiện, lựa chọn một mô hình mà nó phù hợp với tất cả các sự kiện, mặt khác ngang bằng nhất có thể. Điều này gần giống như việc chúng ta lựa chọn các xác suất mô hình (p) tại mỗi bức như chúng ta đã làm trong ví dụ trên. ...sự kiện mà một phân phối xác suất nào đó làm tăng entropy phụ thuộc vào các ràng buộc nào đó đặc trưng cho thông tin chưa đầy đủ của nó, là thuộc tính cơ bản mà nó chứng minh ích lợi của việc phân phối cho các suy luận là đúng; nó phù hợp với mọi thứ mà nó biết, nhưng tránh những suy luận mà nó không rõ. Nó là một sự sao chép thành các phép toán học của những nguyên lý cổ xưa một cách khôn ngoan... 3.2 Mô hình cực đại entropy Chúng ta xem xét một bài toán bất kỳ nó cho ra một giá trị output y, là một thành phần của tập hữu hạn Y. Với ví dụ về hệ thống dịch, bài toán sinh ra một khả năng có thể được dịch của từ “in”, và output y có thể là bất kỳ từ nào trong tập {dans, en, à, au cours de, pendant}. Với việc sinh ra y, bài toán này có thể bị tác động bởi thông tin ngữ cảnh x, là một thành phần của tập hữu hạn X. Trong ví dụ, thông tin này có thể bao gồm những từ trong câu tiếng Anh xung quanh từ “in”. Nhiệm vụ của chúng ta là xây dựng mô hình có tính ngẫu nhiên thống kê mà nó miêu tả chính xác các hành vi của bài toán bất kỳ. Vì vậy mô hình là một phương thức của việc xác định xác suất có điều kiện mà trong đó, cho ngữ cảnh x, với output là y. Chúng ta sẽ biểu diễn bằng xác suất p(y|x) mà mô hình ấn định y trong ngữ cảnh x. Chúng ta cũng sẽ sử dụng p(y|x) để biểu diễn cho toàn bộ phân phối xác suất có điều kiện bởi mô hình. Việc giải thích chính xác sẽ được làm sáng tỏ từ ngữ cảnh. Chúng ta sẽ ký hiệu P là tập toàn bộ các phân phối xác suất có điều kiện. Như vậy một xác suất mô hình p(y|x) chính là một thành phần của P. 3.2.1 Dữ liệu huấn luyện Để nghiên cứu về bài toán, chúng ta theo rõi cách xử lý của một bài toán bất kỳ trong một vài lần, sẽ tập hợp được một số lượng lớn các mẫu (x1,y1), (x2,y2), (x3,y3),...., (xN,yN). Trong ví dụ, chúng ta đã thấy rằng, mỗi mẫu sẽ gồm có một nhóm x chứa các từ xung quanh “in”, cùng với một khả năng được dịch y của từ “in” mà bài toán đưa ra. Bây giờ chúng ta có thể tưởng tượng rằng những mẫu huấn luyện đó có thể được sinh ra bởi một nhà chuyên gia người đã đưa ra con số ngẫu nhiên cho các cụm từ chứa “in” và câu trả lời cho lựa chọn dịch tốt nhất trong mỗi lần nghiên cứu. Chúng ta có thể tổng hợp mẫu huấn luyện liên quan tới chính phân phối xác suất thực nghiệm của nó p̃, được định nghĩa như sau: (số luần xuất hiện của cặp (x,y) trong mẫu) Trường hợp đặc biệt là cặp (x,y) sẽ không xuất hiện trong toàn bộ mẫu, hay sẽ xuất hiện trong toàn bộ mẫu. 3.2.2 Thống kê, đặc trưng và ràng buộc Mục đích của chúng ta là xây dựng một mô hình thống kê của bài toán mà nó phát sinh xác suất p̃(x,y) mẫu huấn luyện. Khối kiến trúc của mô hình này sẽ là một tập các thống kê của mẫu huấn luyện. Trong ví dụ, chúng ta đã dùng một số thống kê: tần số mà từ “in” được dịch thành “dans” hay “en” là 3/10; tần số mà nó được dịch thành “dans” hay “au cours de” là ½; vân vân. Những thống kê đặc biệt là thống kê độc lập với ngữ cảnh, nhưng chúng ta cũng có thể coi như những thống kê đó là phụ thuộc vào thông tin điều kiện x. Ví dụ, chúng ta có thể nhận thấy rằng, trong mẫu huấn luyện, nếu “April” là từ đi sau “in”, thì việc dịch từ “in” là “en” sẽ có tần số là 9/10. Để biểu diễn sự kiện mà “in” được dịch là “en” khi “April” là từ đi theo sau, chúng ta có thể sử dụng hàm để biểu diễn như sau: nếu y = “en” và “April” theo sau “in” còn lại Giá trị kỳ vọng của f liên quan tới phân phối thực nghiệm p̃(x,y) chính là thống kê mà chúng ta đã nhắc tới. Chúng ta biểu diễn giá trị kỳ vọng này bởi: với mọi cặp (x,y) (1) Chúng ta có thể biểu diễn bất kỳ thống kê nào của mẫu huấn luyện như giá trị kỳ vọng của hàm nhị phân (f) thích hợp. Chúng ta gọi hàm đó là hàm đặc trưng hay đặc trưng. (Như vậy với các phân phối xác suất, chúng ta sẽ dùng ký hiệu và sử dụng hàm f(x,y) để biểu diễn giá trị của f với mỗi cặp (x,y) riêng biệt cũng như toàn bộ hàm f). Khi chúng ta tìm hiểu về thống kê sẽ thấy sự hữu ích của nó, chúng ta có thể thấy được tầm quan trọng của nó bằng cách làm cho những gì có trong mô hình của chúng ta phù hợp với nó. Chúng ta làm điều này bằng các ràng buộc các giá trị kỳ vọng mà mô hình ấn định cho các hàm đặc trưng (f) tương ứng. Giá trị kỳ vọng của f quan hệ với xác suất mô hình p(y|x) như sau: với mọi cặp (x,y) (2) Trong đó: p̃(x) là phân phối thực nghiệm của x trong mẫu huấn luyện. Chúng ta ràng buộc giá trị kỳ vọng này bằng với giá trị kỳ vọng của f trong mẫu huấn luyện: (3) Từ (1), (2) và (3) ta có: Chúng ta gọi (3) là phương trình ràng buộc hay đơn giản là ràng buộc. Bằng cách thu hẹp sự chú ý tới những xác suất mô hình, p(y|x), như trong công thức (3), chúng ta loại trừ các mô hình được xem xét mà nó không thích hợp với mẫu huấn luyện dựa vào cách thông thường mà output của bài toán sẽ đưa ra đặc trưng f. Tóm lại, chúng ta có được giá trị trung bình cho các thống kê tương ứng với các hiện tượng tồn tại trong dữ liệu mẫu, Ẽ(f), và cũng là giá trị trung bình yêu cầu mà mô hình của bài toán đưa ra các hiện tượng đó (E(f) = Ẽ(f)). Cần phân biệt rõ ràng 2 khái niệm về đặc trưng và ràng buộc: một đặc trưng là một hàm nhận giá trị nhị phân của cặp (x,y); một ràng buộc là một phương trình giữa giá trị kỳ vọng của hàm đặc trưng trong mô hình và giá trị kỳ vọng của nó trong dữ liệu huấn luyện. 3.2.3 Nguyên lý cực đại entropy Giả thiết rằng chúng ta có n hàm đặc trưng fi, nó quyết định những thống kê mà chúng ta cảm thấy là quan trọng trong quá trình mô hình hóa. Chúng ta muốn mô hình của chúng ta phù hợp với những thống kê đó. Vì vậy, chúng ta sẽ muốn p hợp lệ trong tập con C của P được định nghĩa bởi: C = {p € P | E(fi) = Ẽ(fi) for i € {1,2,...,n}} (4) Trong số các mô hình p € C, triết lý cực đại entropy yêu cầu rằng chúng ta lựa chọn phân phối mà ngang bằng nhau nhất. Nhưng hiện tại chúng ta đối diện với câu hỏi rằng: ngang bằng nhau ở đây có nghĩa là gì? Trong phạm vi toán học ngang bằng nhau của phân phối có điều kiện p(y|x) được cung cấp bởi entropy có điều kiện: (5) Entropy là bị chặn dưới bởi 0, entropy của mô hình không có sự không chắc chắn nào, và chặn trên bởi log|Y|, entropy của phân phối ngang bằng nhau trên toàn bộ các giá trị có thể |Y| của y. Với định nghĩa này, chúng ta đã sẵn sàng để biểu diễn nguyên lý của cực đại entropy: Để lựa chọn mô hình từ một tập C các phân phối xác suất được chấp nhận, lựa chọn mô hình p* € C với cực đại entropy H(p): với p € C (6) Điều đó thể hiện rằng p* luôn luôn xác định; vì vậy, luôn luôn tồn tại một mô hình duy nhất p* với cực đại entropy trong bất kỳ tập ràng buộc C nào. 3.2.4 Tham số hình thức Nguyên lý cực đại entropy đưa ra vấn đề tối ưu các ràng buộc: tìm p* € C mà nó cực đại H(p). Trường hợp đơn giản, chúng ta có thể tìm được giải pháp cho vấn đề này theo phép phân tích. Điều này đúng cho ví dụ được nói đến trong phần 1 khi chúng ta áp dụng 2 ràng buộc đầu tiên lên p. Tiếc là, giải pháp này đối với bài toán cực đại entropy tổng quát không thể viết ra được một cách rõ ràng, và chúng ta cần nhiều phép tính gần đúng gián tiếp. Để giải quyết vấn đề cho bài toán tổng quát, chúng ta áp dụng phương pháp của đa thức Lagrange từ học thuyết tối ưu hóa cưỡng chế. Chúng ta sẽ quy về bài toán tối ưu hóa các ràng buộc ban đầu, với p € C như bài toán căn bản. Với mỗi đặc trưng fi chúng ta đưa ra một tham số λi (một đa thức Lagrange). Chúng ta định nghĩa Lagrangian (p,λ) bởi: (7) Giữ cho λ cố định, chúng ta tính cực đại không có ràng buộc của đang thức Lagrangian (p,λ) trên toàn bộ p € P. Chúng ta biểu diễn pλ là xác suất (p) trong đó (p,λ) đạt được giá trị cực đại và ψ(λ) là giá trị cực đại đó. với p € P (8) (9) Chúng ta gọi ψ(λ) là hàm đỗi ngẫu. Hàm pλ và ψ(λ) có thể được tính toán cụ thể sử dụng các phép tính đơn giản. Chúng ta tìm được: (10) (11) Trong đó Zλ(x) là hằng số chuẩn hóa được quyết định bởi yêu cầu Σypλ(y|x) = 1 cho toàn bộ x: (12) Cuối cùng, chúng ta đưa ra bài toán tối ưu hóa đối ngẫu không ràng buộc: Thoáng qua điều đó có vẻ không đạt được những đòi hỏi đã đề ra ban đầu. Tuy nhiên, nguyên lý cơ bản trong học thuyết đa thức Lagrange, được gọi là định lý Kuhn-Tucker tổng quát, khảng định rằng những thừa nhận dưới đây, những bài toán nền tảng và đối ngẫu là có liên quan chặt chẽ. Đây là cách trong hoàn cảnh hiện tại. Giả thiết rằng λ* là giải pháp cho bài toán đối ngẫu. Khi đó pλ* là giải pháp cho bài toán nền tảng; đó là pλ* = p*. Nói cách khác, Mô hình cực đại entropy đưa ra các ràng buộc C có dạng tham số pλ* trong công thức (10), trong đó giá trị λ* có thể được tính bằng cách cực đại hóa hàm đối ngẫu ψ(λ). Hệ quả thực tế quan trọng nhất của kết quả này là thuật toán cho việc tìm cực đại λ* của ψ(λ) có thể được dùng để tìm ra cực đại p* của H(p) cho p € C. 3.2.5 Mối quan hệ với cực đại Likelihood Log-likelihood Lp̃(p) của phân phối thực nghiệm p̃ như được dự đoán trước bởi xác suất mô hình p được định nghĩa như sau: (13) Dễ dang có thể kiểm tra được rằng hàm đối ngẫu ψ(λ) của phần trước chính là log-likelihood hàm số mũ của xác suất mô hình pλ: (14) Với cách giải thích này, kết quả của phần trước có thể được viết lại như sau: Mô hình p* € C với cực đại entropy là mô hình trong đó họ tham số pλ(y|x) mà nó cực đại likelihood của xác suất mẫu huấn luyện p̃. Kết quả này giúp làm tăng thêm tính đúng đắn cho nguyên lý cực đại entropy: khi quan niệm việc lựa chọn xác suất mô hình p* trên cơ sở cực đại entropy là không đủ sức thuyết phục, điêu xảy ra với cùng một xác suất p* là một mô hình mà nó, trong số toàn bộ các mô hình của cùng một dạng tham số (10), có thể là sự miêu tả tốt nhất cho mẫu huấn luyện. 3.2.6 Tính các tham số Với tất cả những bài toán kể cả đơn giản nhất, thì λ* mà cực đại ψ(λ) là không thể tính toán được theo phép phân tích. Thay vào đó, chúng ta phải dùng đến một số các phương thức khác. Hàm ψ(λ) được xử lý tốt, khi làm mịn giá trị λ.Do đó, có nhiều phương thức khác nhau có thể được dùng để tính giá trị λ*. Một phương thức đơn giản là tăng phối hợp có kinh nghiệm, trong cách này λ* được tính bằng cách lặp đi lặp lại cực đại ψ(λ) một cách phối hợp tại mỗi lần. Khi được áp dụng vào bài toán cực đại entropy, kỹ thuật này sẽ mang lại thuật toán tổng quát Brown (Brown 1959). Các phương thức tổng quát khác có thể được dùng để cực đại ψ(λ) bào gồm chuẩn gradient và liên hợp gradient. Một phương thức tối ưu hóa đặc trưng của tailor cho bài toán cực đại entropy là thuật toán “improved iterative scaling” của Darroch và Ratcliff (1972). Thuật toán có thể áp dụng được bất cứ khi nào miễn là các hàm đặc trưng fi(x,y) không âm: fi(x,y) >= 0 với mọi i, x và y (15) Điều này là luôn đúng bởi vì giá trị của hàm đặc trưng có thể nhận chỉ là giá trị nhị phân (0, 1): Σifi(x,y) = 1 với mọi x,y Thuật toán 1: Improved Iterative Scaling (IIS) Input: hàm đặc trưng f1, f2,..., fn; phân phối thực nghiệm p̅(x,y) Ouput: Giá trị tham số tối ưu λ*i; xác suất mô hình tối ưu pλ* Bắt đầu với λi = 0 với mọi i € {1, 2,..., n} Với mọi i € {1, 2,..., n} Sử dụng ∆λi để tính: (16) Trong đó: (17) Cập nhập giá trị của λi: λi = λi + ∆λi Lặp lại bước 2 nếu tất cả λi chưa hội tụ Bước quan trọng nhất trong thuật toán là bước 2.a, việc tính toán độ chênh lệch ∆λi được sử dụng cho phương trình (16). Nếu f#(x,y) là hằng số (f#(x,y) = M với mội x,y) thì ∆λi được tính như sau: Nếu f#(x,y) không phải là hằng số, khi đó ∆λi phải được tính toán số học. Cách đơn giản và hiệu quả của trường hợp này là phương thức của Newton. Phương thức này tính α* của phương trình g(α*) = 0 lặp đi lặp lại bằng phép truy hồi: (18) với sự lựa chọn thích hợp cho α0 và chú ý tới sự phù hợp với phạm vi của g. 3.3 Lựa chọn đặc trưng Từ những phần trước chúng ta đã chia bài toán mô hình hóa thống kê thành 2 bước: bước thứ nhất là tìm các sự kiện thích hợp về dữ liệu; bước thứ hai là kết hợp chặt chẽ các sự kiện vào mô hình. Tiếp theo chúng ta sẽ tìm cách để giải quyết bước thứ nhất bằng cách này hay cách khác. Với ví dụ đơn giản trong phần 2, chúng ta không có phát biểu rõ ràng về cách chúng ta lựa chọn các ràng buộc đặc trưng. Vì vậy, tại sao sự kiện “dans” hay “à” được chọn bởi hệ thống dịch là 50% tại mỗi lần lựa chọn là quan trọng hơn sơ với tất cả các sự kiện khác trong dữ liệu? Thực vậy, nguyên lý của cực đại entropy không trực tiếp liên quan tới việc lựa chọn đặc trưng: nó chỉ đơn thuần cung cấp công thức cho việc kết hợp các ràng buộc vào mô hình. Nhưng bài toán lựa chọn đặc trưng lại có vấn đề, khi các ràng buộc có thể là các đặc trưng trong hàng nghìn hay hàng triệu các sự kiện. Trong phần này chúng tôi giới thiệu phương thức cho việc lựa chọn tự động các đặc trưng trong mô hình cực đại entropy, việc lựa chọn đặc trưng được thực hiện tốt sẽ giúp giảm bớt gánh nặng cho việc tính toán. 3.3.1 Ý nghĩa của việc lựa chọn đặc trưng Chúng ta bắt đầu bằng cách chỉ rõ bộ sưu tập lớn F các đặc trưng ứng cử. Chúng ta không yêu cầu bất ky một ưu tiên nào đối với các đặc trưng mà những đặc trưng đó đều được lựa chọn như là các đặc trưng ứng cử. Thay vào đó, chúng ta chia thành những tập dữ liệu có độ lớn có thể tính toán được. Chỉ một tập con của tập các đặc trưng sẽ được sử dụng vào mô hình cuối cùng của chúng ta. Nếu chúng ta có mẫu huấn luyện có kích thước vô hạn, chúng ta có thể quyết định giá trị kỳ vọng thích hợp cho mỗi đặc trưng ứng cử f € F bằng cách tính các sự kiện nhỏ trong mẫu mà nó có f(x,y) = 1. Trong các ứng dụng thực tế, chúng ta được cung cấp với chỉ một mẫu nhỏ N sự kiện, nó không thể tin cậy để đặc trưng cho toàn bộ bài toán và là đúng đắn. Rõ ràng, chúng ta không thể mong chờ rằng với mọi đặc trưng f € F, ước lượng Ẽ(f) chúng ta nhận được từ mẫu sẽ hạn chế giá trị của nó trong một giới hạn khi n tăng dần. Sử dụng một mẫu lớn dữ liệu với cùng một bài toán có thể dẫn đến các ước lượng Ẽ(f) khác nhau với các đặc trưng ứng cử. Một cách ngắn gọn, chúng ta muốn thêm vào mô hình chỉ một tập con S của toàn bộ tập đặc trưng ứng cử F. Chúng ta sẽ gọi S là tập đặc trưng có hiệu lực. Việc lựa chọn S phải lấy được thật nhiều thông tin về bài toán bất kỳ càng nhiều càng tốt, tuy nhiên chỉ thêm các giá trị kỳ vọng của các đặc trưng có thể ước lượng đáng tin cậy. Để tìm tập S, chúng ta chọn gần đúng tăng dần cho việc lựa chọn đặc trưng, giống như chiến lược được áp dụng cho việc phát triển cây quyết định (Bahl et al 1989). Ý tưởng là xây dựng tập con S bằng cách thêm lần lượt các đặc trưng. Với mỗi lựa chọn đặc trưng được thêm vào tại mỗi bước được quyết định bởi dữ liệu huấn luyện. Bây giờ chúng ta biểu diễn tập mô hình được xây dựng bởi các đặc trưng của tập S là C(S). Mỗi khi thêm một đặc trưng f phải thỏa mãn phương trình Ẽ(f) = E(f). Chỉ các thành phần của C(S) sẽ thỏa mãn phương trình này; những đặc trưng đó được biểu diễn bởi C(Sυf). Như vậy, mỗi lần một đặc trưng ứng cử được nối tiếp vào S, ràng buộc tuyến tính khác được áp dụng lên không gian C(S) của mô hình được cho phép bởi các đặc trưng trong tập S. Như vậy kết quả là, C(S) được rút gọn lại; xác suất mô hình p* trong C với entropy lớn nhất phản ánh sự hiểu biết tăng mãi mãi và vì vậy việc miêu tả bài toán sẽ trở nên chính xác hơn.Điều này giúp cho không gian chấp nhận được của các mô hình được thu hẹp hơn. Có lẽ trực quan hơn, chúng ta có thể miêu tả nó bằng một loạt các tập con được đạt vào P như hình sau: Hình 3.1: Lựa chọn đặc trưng (trích dẫn: trang 12 quyển A Maximum Entropy Approach to Natural Language Processing) 3.3.2 Cơ sở lựa chọn đặc trưng Cơ sở của thủ tục tăng dần có thể được phác thảo như sau. Với mọi giai đoạn của bài toán được xác định rõ đặc điểm bởi tập các đặc trưng có hiệu lực S. Điều đó quyết định không gian của mô hình: C(S) = {p € P | E(f) = Ẽ(f) với mọi f € S} (19) Mô hình tối ưu trong không gian này, được biểu diễn bởi pS, là mô hình với entropy lớn nhất: (20) Bằng cách thêm đặc trưng f̃ vào tập S, chúng ta thu được tập mới với các đặc trưng có hiệu lực Sυf̃. Như công thức (19), tập đặc trưng này quyết định tập các mô hình: C(S U f̃) = {p € P | E(f) = Ẽ(f) với mọi f € S U f̃} (21) Mô hình tối ưu trong không gian mô hình này là: (22) Thêm đặc trưng f̃ cho phép mô hình psυf̃ tính toán tốt hơn với mẫu huấn luyện; điều này dẫn đến việc thu được ∆L(S,f̃) từ log-likelihood của dữ liệu huấn luyện. (23) Tại mỗi giai đoạn của bài toán xây dựng mô hình, mục đích của chúng ta là lựa chọn được đặc trưng ứng cử f̃ € F mà nó giúp tăng ∆L(S,f̃); vì vậy, chúng ta lựa chọn đặc trưng ứng cử, khi nối tiếp vào tập đặc trưng có hiệu lực S, nó giúp tăng đáng kể likelihood trong mẫu huấn luyện. Chiến lược này được thực thi trong thuật toán sau: Thuật toán 2: Input: tập hợp F của các đặc trưng ứng cử; phân phối thực nghiệm p̃(x,y) Output: tập S các đặc trưng có hiệu lực; xác suất mô hình pS hợp nhất các đặc trưng. Bắt đầu với S= Θ; vì vậy pS là giống nhau Với mỗi đặc trưng ứng cử f € F: Tính xác suất mô hình PSυf sử dụng thuật toán 1 Tính lượng gia tăng của log-likelihood từ những đặc trưng được thêm vào sử dụng công thức (23) Kiểm tra điều kiện kết thúc Lựa chọn đặc trưng f̃ với độ tăng tối đa ∆L(S,f̃) Nối liền f̃ vào tập S Tính xác suất pS sử dụng thuật toán 1 Lặp lại bước 2 Có thể thấy được, chúng ta sẽ muốn một điều kiện dừng giúp bài toán dừng một cách chính xác khi toàn bộ các đặc trưng hữu ích đã được lựa chọn. 3.3.3 Giá trị gần đúng Thuật toán 2 không phải là phương thức thực tế cho việc lựa chọn đặc trưng tăng dần. Với mỗi đặc trưng ứng cử f € F được xem xét trong bước 2, chúng phải tính xác suất mô hình pSυf, đó là công việc rất tốn kém trong việc tính toán ngay cả với thuật toán iis. Bởi vậy chúng tôi giới thiệu một thuật toán cải tiến, đó là thuật toán tham ăn có tính khả thi hơn. Chúng ta thay vì tính toán độ gia tăng ∆L(S,f̃) của một đặc trưng f với phép tính xấp xỉ, thì chúng ta biểu diễn bằng ~∆L(S,f̃). Nhắc lại rằng một xác suất mô hình pS có tập các tham số λ, với mỗi đặc trưng trong tập S. Xác suất mô hình pSυf chứa tập các tham số này, cộng với tham số mới α, tương ứng với f. Với cấu trúc này, chúng ta có thể hy vọng rằng giá trị tối ưu của λ sẽ không thay đổi khi đặc trưng f được nối tếp vào tập S. Trường hợp này, khi sử dụng thêm ràng buộc sẽ yêu cầu tham số tối ưu α làm tăng liklihood. Thực vậy, khi một ràng buộc mới được sử dụng, các giá trị tối ưu của toàn bộ các tham số sẽ thay đổi. Tuy nhiên, để dễ dàng tính toán được thứ hạng của các đặc trưng, chúng ta xấp xỉ chúng, những đặc trưng thêm vào f chỉ tác động tới α, những giá trị λ còn lại được kết hợp với những đặc trưng khác không thay đổi. Vì vậy, khi quyết định độ gia tăng trên xác suất mô hình pS, chúng ta ràng buộc rằng mô hình tốt nhất chứa các đặc trưng Sυf phải có dạng như sau: với các giá trị thật của α (24) Trong đó (25) Chỉ duy nhất tham số mà nó phân biệt được các mô hình có dạng (24) là α. Trong số các mô hình đó, chúng ta quan tâm tới mô hình mà nó làm tăng tính gần đúng. (26) Chúng ta sẽ biểu diễn sự tăng thêm của mô hình này bởi: (27) và mô hình tối ưu bởi: trên pαS,f (28) Tính toán giá trị gần đúng trong likelihood từ việc thêm các đặc trưng f vào pS đã đưa bài toán tối ưu về dạng 1 chiều đơn giản hơn với một tham số α, nó có thể được giải quyết bởi bất kỳ kỹ thuật tìm kiếm tuyến tính thông thường nào (chẳng hạn như phương thức của Newton). Điều đó giúp tránh được những phép tính phức tạp và tăng độ chính xác của bài toán, một bài toán tối ưu n chiều yêu cầu nhiều phương thức phức tạp hơn như gradient liên hợp. Nhưng việc tiết kiệm chi phí đó: với một đặc trưng riêng biệt f nào đó, chúng ta hầu như đánh giá thấp giá trị của nó, và điều đó giúp chúng ta lựa chọn đặc trưng f mà giá trị gần đúng ~∆L(S,f) của nó là cao nhất thông qua đặc trưng f với việc tăng tối đa giá trị ∆L(S,f). Log-likelihood được biểu diễn như một hàm lồi tùy ý với 2 tham số (như hình vẽ): λ tương ứng với tham số cũ, và α ứng với tham số mới. Giữ cố định giá trị λ và thay đổi α để tăng log-likelihood bao gồm việc tìm kiếm trên toàn bộ không gian (λ,α). Hình 3.2: log-likelihood được biểu diễn như hàm lồi 2 tham số (trích dẫn: trang 15 quyển A Maximum Entropy Approach to Natural Language Processing) Chương 4: Thực nghiệm phân loại văn bản 4.1 Thống kê kết quả thực nghiệm Dữ liệu được sử dụng trong huấn luyện và kiểm thử là những bài báo được lọc ra từ trang web bao gồm 6 chủ đề: kinh doanh, pháp luật, thể thao, văn hóa, vi tính và xã hội. Mỗi chủ đề tương ứng với một thư mục với tên: kinh_doanh, phap_luat, the_thao, van_hoa, vi_tinh và xa_hoi. Với dữ liệu huấn luyện: kinh_doanh có 540 file, phap_luat có 240 file, the_thao có 660 file, van_hoa có 360 file, vi_tinh có 660 file và xa_hoi có 300 file. Với dữ liệu kiểm thử: kinh_doanh có 423 file, phap_luat có 179 file, the_thao có 450 file, van_hoa có 294 file, vi_tinh có 524 file và xa_hoi có 219 file. Số lượng file của dữ liệu huấn luyện: Tên chủ đề Số lượng file kinh_doanh 540 phap_luat 240 the_thao 660 van_hoa 360 vi_tinh 660 xa_hoi 300 Bảng 4.1: Số lượng file của dữ liệu huấn luyện Số lượng file của dữ liệu kiểm thử: Tên chủ đề Số lượng file kinh_doanh 423 phap_luat 179 the_thao 450 van_hoa 294 vi_tinh 524 xa_hoi 219 Bảng 4.2: số lượng file của dữ liệu kiểm thử Từ tập dữ liệu huấn luyện và kiểm thử thô ban đầu này, trước khi được sử dụng để huấn luyện và kiểm thử cần qua một số bước lọc bỏ các đặc trưng không tốt. Bước thứ nhất, lọc bỏ các từ vô nghĩa (stop word), các ký tự đặc biệt như {‘!’ ‘@’ ‘,’ ‘.’ ‘:’ ‘;’ ....} và gom nhóm các từ vào cùng một nhóm có tính chất giống nhau. Ví dụ như gom các giá trị số đếm, ngày tháng năm... vào nhóm number. Trong bước này, danh sách từ vô nghĩa được xác định bằng thuật toán TFIDF dựa trên tập dữ liệu huấn luyện và danh sách từ vô nghĩa mẫu. Bước tiếp theo là lọc bỏ các đặc trưng theo tần số. Những đặc trưng có tần số xuất hiện trong dữ liệu huấn luyện thấp hơn một giá trị nào đó (mặc định là 10) sẽ bị loại bỏ. Bước cuối cùng được thực hiện sau khi đã gán các trọng số cho từng đặc trưng. Tại bước này, những đặc trưng nào không làm tăng entropy của mô hình thì sẽ bị loại bỏ. Với chức năng huấn luyện của chương trình phân loại văn bản. Người dùng có thể khởi tạo giá trị cho một số biến điều khiển như sau: lựa chọn feature (lọc bỏ những đặc trưng có tần số nhỏ hơn giá trị được khởi tao), khởi tạo giá trị ban đầu cho λ, khởi tạo giá trị hội tụ Δλ trong thuật toán IIS. Với cùng một tập dữ liệu huấn luyện và kiểm thử như trên, tiến hành thực nghiệm với các giá trị khởi tạo khác nhau ta thu được những thống kê sau: Với các giá trị khởi tao: lựa chọn feature = 10, khởi tạo lamda = 0, giá trị hội tụ = 0. Chương trình chạy chức năng huấn luyện với thời gian 6 phút 41 giây. Với chức năng kiểm thử, tỉ lệ gán nhãn đúng trung bình là 98.19%. Trong đó tương ứng với từng chủ đề tỷ lệ gán nhãn đúng được biểu diễn như trong biểu đồ sau: Với các giá trị khởi tao: lựa chọn feature = 20, khởi tạo lamda = 0, giá trị hội tụ = 0. Chương trình chạy chức năng huấn luyện với thời gian 2 phút 40 giây. Với chức năng kiểm thử, tỉ lệ gán nhãn đúng trung bình là 98.19%. Trong đó tương ứng với từng chủ đề tỷ lệ gán nhãn đúng được biểu diễn như trong biểu đồ sau: Với các giá trị khởi tao: lựa chọn feature = 10, khởi tạo lamda = 0.3, giá trị hội tụ = 0. Chương trình chạy chức năng huấn luyện với thời gian 7 phút 00 giây. Với chức năng kiểm thử, tỉ lệ gán nhãn đúng trung bình là 98.43%. Trong đó tương ứng với từng chủ đề tỷ lệ gán nhãn đúng được biểu diễn như trong biểu đồ sau: Qua đó rút ra nhận xét rằng, kết quả của việc huấn luyện phụ thuộc phần nào vào việc khởi tạo giá trị lựa chọn lamda (lọc bỏ những đặc trưng có tần số nhỏ hơn mức tối thiểu), vào giá trị khởi tạo λ và gí trị hội tụ của Δλ. Cặp giá trị khởi tạo này có thể tốt với tập dữ liệu huấn luyện này nhưng lại là không tốt với tập dữ liệu khác. Do đó làm thế nào có thể tìm được những giá trị khởi tạo tốt nhất cho từng tập dữ liệu huấn luyện riêng là điều rất khó. Điều đó đòi hỏi nhiều kinh nghiệm trong quá trình xử lý với những tập dữ liệu huấn luyện khác nhau. 4.2 Các thành phần và chức năng của chương trình Chương trình phân loại văn bản với mục đích kiểm nghiệm phương pháp phân loại văn bản cực đại entropy với tiếng Việt và đồng thời cũng là cơ sở để tích hợp vào hệ thống chặn nội dung web. Với tập dữ liệu huấn luyện tiếng Việt. Chương trình dựa vào phương pháp phân loại cực đại entropy để huấn luyện đưa ra tập dữ liệu đã được huấn luyện. Dữ liệu này sẽ được sử dụng cho việc kiểm thử, gán nhãn cho văn bản cần phân loại. Chương trình gồm 3 chức năng chính: chức năng huấn luyện, chức năng kiểm thử và chức năng gán nhán. 4.2.1 Chức năng huấn luyện Giao diện chính của chức năng như sau: Hình 4.1: Giao diện chức năng huấn luyện Bảng mô tả các chức năng của giao diện huấn luyện: Stt Mô tả 1 Trả lại giá trị mặc định của chức năng huấn luyện 2 Bắt đầu huấn luyện 3 Thoát khỏi chương trình 4 Lựa chọn đường dẫn thư mục 5 Chọn giá trị lọc feature (lọc bỏ các feature có tần số <10) 6 Gán giá trị khởi tạo lamda cho thuật toán iis 7 Gán giá trị hội tụ trong thuật toán iis 8 Lựa chọn có ghi file tần số hay không 9 Lựa chọn ngôn ngữ của tập dữ liệu huấn luyện Bảng 4.3: Mô tả giao diện huấn luyện Mục Chọn đường dẫn có 3 đường dẫn cần lựa chọn. Thứ nhât, đường dẫn tới nơi lưu dữ liệu huấn luyện cần huấn luyện. Thứ hai, là đường dẫn lưu dữ liệu sau khi được huấn luyện. Thứ ba, là đường dẫn lưu file tần số. Đường dẫn này chỉ được lựa chọn khi nút checkbox ghi file tần số được đánh dấu. Bảng thông báo kết quả huấn luyện có dạng như sau: Stt Tên nhãn Số lượng file Số lượng feature 1 kinh_doanh 540 1328 2 phap_luat 240 648 3 the_thao 660 1911 4 van_hoa 360 949 5 vi_tinh 660 1653 6 xa_hoi 300 1031 Bảng 4.4: Kết quả huấn luyện Với bài toán phân loại văn bản, việc định nghĩa các đặc trưng được dựa trên các từ xuất hiện trong một chủ đề nào đó. Theo đó, nếu từ đó xuất hiện trong chủ đề thì đặc trưng đó được bật giá trị là 1 và ngược lại giá trị là 0. Ví dụ: xuất hiện từ “tiền” trong chủ đề là “kinh doanh” thì đặc trưng f(tiền, kinh_doanh) = 1 còn f(đá_bóng, kinh_doanh) = 0. 4.2.2 Chức năng kiểm thử Giao diện chính chức năng kiểm thử: Hình 4.2: Giao diện chức năng kiểm thử Bảng mô tả các chức năng của giao diện kiểm thử: Stt Mô tả 1 Trả lại giá trị mặc định của chức năng huấn luyện 2 Bắt đầu kiểm thử 3 Thoát khỏi chương trình 4 Lựa chọn đường dẫn thư mục 5 Danh sách cách nhãn có thể được gán ứng với dữ liệu huấn luyện được chọn Bảng 4.5: Mô tả chức năng kiểm thử Bảng thông báo kết quả kiểm thử có dạng như sau: Stt Tên nhãn Số lượng file Số lượng feature 1 kinh_doanh 423 0 2 phap_luat 197 13 3 the_thao 450 10 4 van_hoa 423 0 Bảng 4.6: Kết quả kiểm thử 4.2.3 Chức năng gán nhãn Giao diện chính chức năng gán nhãn Hình 4.3: Giao diện chức năng gán nhãn Các thành phần của chức năng gán nhãn tương tự như chức năng kiểm thử. Bảng thông báo kết quả gán nhãn có dạng như sau: Stt Tên file Gán nhãn 1 file1.txt kinh_doanh 2 file2.txt phap_luat 3 file3.txt kinh_doanh 4 file4.txt the_thao 5 file5.txt van_hoa 6 file6.txt the_thao Bảng 4.7: Kết quả gán nhãn Cuối cùng là giao diện giới thiệu về chương trình: Hình 4.4: Giao diện giới thiệu 4.3 Ứng dụng chặn nội dung web Nhiệm vụ của chương trình là kiểm soát nội dung của những trang web được người dùng truy cập và mạng Internet thông qua trình duyệt (Internet Explorer). Mỗi khi người dùng nhập một địa chỉ url của một trang web vào trình duyệt. Chương trình sẽ bắt url và sử dụng địa chỉ url đó để lấy nội dung của trang web đó về. Sau đó xử lý nội dung, lọc bỏ những đoạn mã HTML để lấy những nội text của trang web (chính là những dòng text hiển thị trên màn hình khi trang web được load về máy người dùng). Nội dung đó sẽ được qua xử lý lọc bỏ các ký tự vô nghĩa và một số thao tác tiền xử lý. Dựa vào hệ thống phân loại văn bản đã được kiểm thử ở trên, nội dung của trang web được tải về sẽ được phân loại vào chủ đề cụ thể. Qua việc phân loại đó giúp ta quyết định được với địa chỉ trang web đó có được cho phép hay bị chặn lại. 4.3.1 Kỹ thuật lọc web Blue Coat Kỹ thuật lọc web Blue Coat là một giải pháp lọc nội dung web thông qua một “proxy”. Nó giúp cho các tổ chức kinh doanh cũng như các nhà cung cấp các dịch vụ mạng bảo vệ cho những người dùng và hệ thống của họ khỏi những mối đe dọa tới từ Internet. Những mối đe dọa có thể là các phần mềm gián điệp (spyware), các vụ tấn công lừa đảo... Blue Coat bao gồm hơn 15 triệu các phạm trù, đại diện cho hàng tỉ các trang web, được sắp xếp theo các phạm trù hữu ích nhất. Để đảm bảo độ chính xác, mỗi trang web có thể được phân thành nhiều phạm trù, nó cũng cho phép khách hàng xác định một số lượng không hạn chế các phạm trù được cho phép truy cập hay bị chặn để phù hợp với từng yêu cầu cụ thể (ví dụ như chặn các trang web được phân loại là thể thao hoặc vi tính). Đối với những trang web chưa được phân loại vào các phạm trù ở trên, thì việc cho phép hay chặn dựa trên kỹ thuật Dynamic Real-Time Rating (DRTR) là một kỹ thuật phân loại các trang web khi người dùng cố gắng truy cập. Độ bao phủ của cơ sở dữ liệu: Độ bao phủ của cơ sở dữ liệu là khả năng xác định trang web được phân loại vào một phạm trù nhất định. Để đánh giá độ bao phủ của cơ sở dữ liệu chúng ta xét ví dụ sau: Trong số 100 trang web thuộc phạm trù thể thao được sử dụng để đánh giá độ bao phủ của cơ sở dữ liệu. Với cơ sở dữ liệu đó, nó phân loại bao nhiêu trang web vào phạm trù thể thao. Khi đó số lượng những trang web được phân loại đúng càng cao thì độ bao phủ của cơ sở dữ liệu đó càng lớn. Để có độ bao phủ của cơ sở dữ liệu, bộ lọc web phải có khả năng sau: Đánh giá tên miền (thay vì url hay địa chỉ ip) khi thích hợp: Một tên miền cá nhân có thể có hàng ngàn các url. Url mới có thể được thêm vào các phạm trù (trong cơ sở dữ liêu) hàng ngày. Đối với các tên miền đồng nhất, thì việc đánh giá theo tên miền sẽ có nhiều lợi ích hơn so với url hay ip. Bằng cách đánh giá theo tên miền, tất cả những url mới được thêm vào tên miền trên ngay lập tức được kiểm soát. Tỷ lệ các trang web tập hợp được chủ yếu từ yêu cầu của người sử dụng: Không nhà cung cấp nào có thể đánh giá được tất cả 16 tỷ các trang web và cũng không cần thiết phải làm điều đó. Một tỷ lệ lớn các trang web này có thể đã không còn tồn tại. Blue Coat ưu tiên những trang web mà người dùng truy cập đã được phân loại trong cơ sở dữ liệu. Điều này được được thực hiện bởi kỹ thuật Dynamic Real-Time Rating (DRTR). Sau những lần truy cập và phân tích các trang web. Những thông tin đó sẽ được cập nhập cho cơ sở dữ liệu. Cập nhập cơ sở dữ liệu: Như đã nói ở trên, để tăng hiệu quả về mặt thời gian thực Blue Coat sẽ tự động cập nhập những thông tin đã được phân tích của các trang web sau khi người dùng truy cập. Những dữ liệu cập nhập này được gọi là cơ sở dữ liệu địa phương. Chúng được cập nhập thường xuyên để đảm bảo các trang web đó vẫn còn hoạt động bình thường. Tính năng này giống như việc cập nhập giá cả. 4.3.2 Chức năng ứng dụng chặn nội dung web Giao diện chính chương trình chặn nội dung web: Hình 4.5: Giao diện chặn nội dung web Bảng mô tả các chức năng của giao diện chặn nội dung web: Chức năng Mô tả Stop Dừng việc phân tích url được nhập vào trình duyệt Start Bắt đầu phân tích bắt và phân tích url nhập vào trình duyệt Refresh Khởi tạo các giá trị mặc địch cho các textfield Close Thoát hoàn toàn khởi chương trình Setting Cửa sổ cài đặt đối với dữ liệu phân lớp và chỉ ra những nội dung web bị chặn About Cửa sổ giới thiệu về chương trình Phân tích Thực hiện việc phân tích địa chỉ url được nhập vào textfield tương ứng để thực hiện việc cho phép hoặc chặn truy cập với url đó Cho phép Cho phép địa chỉ url được nhập vào text field tương ứng được truy cập Chặn Chặn địa chỉ url được nhậpvào text field tương ứng không được truy cập Danh sách url cho phép truy cập Một danh sách gồm những địa chỉ url đã được phân tích là thuộc vào những url được phép truy cập Danh sách url bị chặn truy cập Một danh sách gồm những địa chỉ url đã được phân tích là thuộc vào những url bị chặn không được truy cập Bảng 4.8: Chức năng giao diện chặn nội dung web Tại giao diện chính khi người dùng tắt cửa sổ bằng button close của cửa sổ có hình x thì cửa sổ sẽ được thu nhỏ xuống thanh system tray. Nếu muốn hiển thị lại người dùng chỉ việc nhấp chuột phải vào biểu tượng chương trình tại thanh system tray rồi chọn show. Ngoài lựa chọn show bạn có thể chọn start, stop hay exit. Tiếp theo là giao diện chắc năng setting dùng để cài đặt dữ liệu phân lớp như sau: Hình 4.6: Cửa sổ setting Chức năng setting rất đơn giản như sau: mặc định ban đầu khi bạn cài đặt chương trình chặn nội dung web đã có dữ liệu phân lớp. Nếu như bạn muốn sử dụng dữ liệu phân lớp nào khác thì có thể dùng button “...” để chỉ ra đường dẫn tới thư mục chứa dữ liệu phân lớp mới của bạn. Sau khi lựa chọn xong dữ liệu phân lớp, tất cả các chủ đề của dữ liệu được liệt kê trong Danh sách các chủ đề phân lớp như hình vẽ. Trong số các chủ đề đó, bạn có thể chọn 1 hay nhiều chủ đề sẽ bị chặn truy cập và nhấp vào button “=>” để chuyển vào danh sách các chủ đề bị chặn. Sau khi đã cài đặt xong bạn nhấp vào button Lưu để lưu lại những thay đội hoặc Thoát để trở lại với cài đặt trước đấy. Và cuối cùng là cửa sổ About giới thiệu về chương trình: Hình 4.7: Cửa sổ giới thiệu Chương 5: Kết luận 5.1 Kết quả đạt được Thông qua việc tìm hiểu và nghiên cứu một số phương pháp phân loại văn bản như: Naïve Bayes, k-Nearest Neighbor, Linear Least Squares Fit, Support Vector Machine, mô hình cực đại Entropy giúp hiểu rõ về các phương pháp phân loại văn bản, những ưu nhược điểm của từng phương pháp. Qua việc phân tích ưu nhược điểm này giúp lựa chọn phương pháp phân loại văn bản tốt nhất cho bài toán phân loại văn bản, phục vụ cho mục đích cuối cùng của luận văn. Với ưu điểm mềm dẻo và linh hoạt của mô hình cực đại entropy, luận văn sử dụng mô hình cực đại entropy để giải quyết bài toán phân loại văn bản. Lý thuyết mô hình cực đại entropy được trình bày chi tiết tại chương 3 với những khái niệm về dữ liệu huấn luyện, thống kê, đặc trưng và các ràng buộc. Nguyên lý hoạt động của mô hình cực đại entropy với bài toán phân loại văn bản. Cách tính các tham số với thuật toán IIS và cơ sở lựa chọn các đặc trưng. Dựa trên những cơ sở lý thuyết của mô hình cực đại entropy để phát triển chương trình phân loại văn bản. Chương trình được viết bằng ngôn ngữ lập trình Java với giao diện tiện dụng và đầy đủ các chức năng (huấn luyện, kiểm thử và gán nhãn). Chương trình chặn nội dung web là một ứng dụng của bài toán phân loại văn bản. Chương trình dựa trên nội dung của trang web và chương trình phân loại văn bản ở trên để phân loại trang web theo các chủ đề. Bên cạnh tính năng phân loại, chương trình có khả năng chặn truy cập những trang web theo một số chủ đề nào đó được chỉ ra bởi người quản trị. Điều đó giúp quản lý việc truy cập Internet có hiệu quả hơn và tránh được những trang web có nội dung không tốt. Toàn bộ mã nguồn của chương trình phân loại văn bản và chặn nội dung web được sử dụng trong luận văn đều được xây dựng và phát triển từ đầu. Về mặt thực nghiệm, những kết quả thực nghiệm của chương trình chặn nội dung web được thống kê chi tiết tại chương 4. Theo đó, về mặt thời gian huấn luyện cũng như tỷ lệ gán nhãn thành công trong kiểm thử của chương trình đạt kết quả rất tốt. Tỷ lệ gán nhãn đúng trong kiểm thử qua nhiều lần thực nghiệm hơn 98%. Kết quả này còn được cải thiện tốt hơn với việc thay đổi các tham số điều khiển như: khởi tạo λ, lựa chọn đặc trưng và giá trị hội tụ của Δλ. Với chương trình chặn nội dung web, chương trình được kiểm tra với trình duyệt Internet Explorer. Chương trình tự động kiểm tra những địa chỉ url mà người dùng nhập vào trình duyệt. Sau đó phân tích nội dung của trang web đó. Nếu nội dung thuộc chủ đề được phép truy cập chương trình sẽ cập nhập địa chỉ url vào danh sách các địa chỉ url được phép truy cập trên giao diện chương trình. Điều đó tương ứng với địa chỉ url bị chặn, chỉ khác ở chỗ địa chỉ url bị chặn sẽ được đưa vào danh sách url bị chặn của ip-sec của window thông qua các luật. Ngoài chức năng phân tích tự động thông qua trình duyệt Internet Explorer, người quản trị cũng có thể phân tích trực tiếp một địa chỉ url nào đó từ chương trình chặn nội dung web thông qua giao diện cũng như trực tiếp cho phép truy cập hay chặn truy cập với một url nào đó. 5.2 Những hạn chế và hướng giải quyết Qua những thống kê thực nghiệm của chương trình phân loại văn bản. Một hướng giải quyết mới giúp nâng cao khả năng gán nhãn sẽ là việc thay đổi các tham số điều khiển (khởi tạo λ, lựa chọn đặc trưng và giá trị hội tụ của Δλ). Bằng việc thay đổi đó sẽ giúp tìm ra được mô hình hoàn thiện nhất ứng với những tập dữ liệu huấn luyện khác nhau. Do thời gian có hạn nên trong khuôn khổ luận văn mới chỉ phát triển được những tính năng cở bản của chương trình chặn nội dung web nhằm ứng dụng bài toán phân loại văn bản. Chương trình vẫn còn nhiều hạn chế như: chương trình mới chỉ làm việc trên trình duyệt Internet Explorer và cơ chế chặn truy cập hoạt động chưa được tốt. Tài liệu tham khảo Tài liệu tiếng Anh [1] Adam Berger; The Improved Iterative Scaling Algorithm: A Gentle Introduction; 1997 [2] Adam L. Berger & Stephen A. Della Pietra & Vincent J. Della Pietra; A Maximum Entropy Approach to Natural Language Processing; 1996 [3] Adwait Ratnaparkhi; A Simple Introduction to Maximum Entropy Models for Natural Language Processing; 1997 [4] Adwait Ratnaparkhi; Maximum Entropy Models for Natural Language Ambiguity Resolution; 1998 [5] Blue Coat; Blue Coat WebFilterTMTechnology. [6] Christopher D. Manning & Hinrich Schutze; Foundations of Statistical Natural Language Processing; 1999; 612 - 645 [7] Jeffrey C. Reynar & Adwait Ratnaparkhi; A Maximum Entropy Approach to identifying sentence boundaries; 1997. [8] Jun’ichi Kazama & Jun’ichi Tsujii; Evaluation and Extension of Maximum Entropy Models with Inequality Constraints; 2003 [9] Kamal Nigam & John Lafferty & Andrew McCallum; Using Maximum Entropy for Text Classification [10] Radu Ioan Bot & Sorin Mihai Grad & Gert Wanka; Maximum Entropy Optimization for Textclassification problems; 1999 [11] RobertMalouf; A comparison of algorithms for maximum entropy parameter estimation [12] Ronald Rosenfeld; A Maximum Entropy Approach to Adaptive Statistical Language Modeling [13] Stanley F. Chen & Ranald Rosendfeld; A Gausan Prior for smoothing Maximum Entropy Models; 1999 [14] Thorsten Joachims; A probabilistic analysis of the Rocchio algorithm with TFIDF for text categorization; 1997 Tài liệu tiếng Việt [1] Hồ Quốc Bảo, Đông Thị Bích Thủy; Ứng dụng xử lý ngôn ngữ tự nhiên trong tìm kiếm thông tin trên văn bản tiếng việt; [2] Nguyễn Lính Gian, Nguyễn Mạnh Hiển; Phân loại văn bản tiếng việt với bộ phân loại vector hỗ trợ SVM; 2005 [3] Nguyễn Thị Ngọc Hợp; Phân loại văn bản sử dụng hạt nhân của chuỗi; [4] Vũ Thanh Nguyên, Trang Nhật Quang; Ứng dụng thuật toán phân lớp rút trích thông tin văn bản FSVM trên Internet; 2008 [5] Đỗ Phúc, Mai Xuân Hùng, Nguyễn Thị Kim Phụng; Gom cụm đồ thị và ứng dụng vào việc rút trích nội dung chính của khối thông điệp trên diễn đàn thảo luận; 2008 [6] Phạm Thị Thơm; Ứng dụng phương pháp phân loại văn bản Naive Bayes vào việc xây dựng chương trình mail client với khả năng lọc thư rác tự động; 2006 Phụ lục Chức năng của các các lớp sử dụng trong chương trình phân loại văn bản: Tên lớp Mô tả EmpiricalDistribution Lớp bao gồm các hàm: get_distribution_xy, get_distribution_x. Được dùng để tính xác suất thực nghiệm và xác suất ngữ cảnh Feature Lớp bao gồm các hàm: set_feature, get_c. Dùng để gán giá trị {0,1} cho các đặc trưng và tính giá trị C (giá trị tổng các đặc trưng của từng nhãn lớn nhất) IIS Lớp bao gồm các hàm: get_z, get_p_yx, get_empirical_expectation, get_model_expectation, delta_lamda, lamda, write_lamda, write_all. Dùng để cài đặt thuật toán IIS cho việc tính toán trọng số cho từng đặc trưng InputFile Lớp bao gồm các hàm: read_input, write_input, set_lamda, set_model_distribution. Dùng để tính trọng số của từng đặc trưng cho file cần gán nhãn và đưa ra tên nhãn được gán LamdaFile Lớp bao gồm các hàm: cut_tag_name, read_lamda_file, read_all. Dùng để đọc nội dung của các file đã được huấn luyện gồm các từ và trọng số vào các mảng NonsensicalWord Lớp bao gồm các hàm: read_nonsensical_word, nonsensical_word. Dùng để đọc vào nội dung file chứa các từ stop-word và kiểm tra một từ nào đó có phải là stop-wrod hay không Test Lớp bao gồm các hàm: cut_tag_name, test_event, set_tag. Dùng để kiểm thử dữ liệu đã được huấn luyện và gán nhãn cho văn bản bất kỳ Training Dùng cho chức năng huấn luyện TrainingFile Lớp bao gồm các hàm: cut_tag_name, read_training, read_all, set_frequency, set_frequency_all_data, feature_selection, write_train, write_all, update_training. Dùng để đọc nội dung các file trong dữ liệu huấn luyện, gán tần số xuất hiện cho từng từ và lọc những từ có tần số nhỏ hơn mức tối thiểu (mặc định là 10) Main Lớp là giao diện đồ họa của chương trình, xử lý các sự kiện ứng với từng chức năng của chương trình Chức năng các hàm cụ thể được sử dụng trong chương trình phân loại văn bản: Tên hàm Mô tả double get_distribution_xy(int context_arg, int tag_arg) Tính xác suất thực nghiệm của cặp ngữ cảnh (context_arg, tag_arg) và kết quả trả lại kiểu double double get_distribution_x(int context_arg, int tag_arg) Tính xác suất ngữ cảnh của ngữ cảnh contex_arg void set_feature() Hàm gán giá trị cho mảng đặc trưng. Có giá trị 1 nếu đặc trưng xuất hiện trong dữ liệu huấn luyện, 0 nếu ngược lại double get_c() Trả lại giá trị tổng các đặc trưng của từng nhãn lớn nhất double get_z() Trả lại giá trị Z trong công thức tính các giá trị tham số của thuật toán IIS double get_p_yx(int tag) Trả lại giá trị xác suất p(y|x) double get_empirical_expectation(int tag, int context) Trả lại giá trị kỳ vọng thực nghiệm ứng của cặp đặc trưng với nhãn tag và ngữ cảnh context double get_model_expectation(int tag, int context) Trả lại giá trị kỳ vọng mô hình của cặp đặc trưng với nhãn tag và ngữ cảnh context double delta_lamda(int tag, int context) Trả lại giá trị Δλ của cặp đặc trưng (tag, context) void lamda(double delta_lamda_init, int loop) Tính trọng số λ cho các cặp đặc trưng với giá trị hội tụ là delta_lamda_init và số lần lặp tối đa là loop void write_lamda(String path_lamda, ArrayList variable, ArrayList lamda_arg) Ghi 2 mảng variable (các từ) và mảng trọng số lamda_arg thành file với đường dẫn là path_lamda write_all(String path_lamda) Ghi toàn bộ các giá trị trọng số ứng với từng cặp đặc trưng thành file với đường dẫn path_lamda boolean read_input(String path_test_file, boolean tieng_viet) Đọc file đầu vào cần gán nhãn. Trong đó path_test_file là đường dẫn của file đầu vào và tieng_viet là biến điều khiển dữ liệu đầu vào là tiếng việt (nếu true) hay tiếng anh. Trả lại là true nếu tồn tại file và false nếu ngược lại void set_lamda(LamdaFile lamda_arg) Gán giá trị trọng số λ cho từng đặc trưng tương ứng của văn bản cần gán nhãn void set_model_distribution(LamdaFile lamda_arg) Tính xác suất mà file đầu vào cần gán nhãn thuộc vào các các nhãn tương ứng. Và đưa ra nhãn có xác suất là lớn nhất. Nghĩa là nhãn được gán cho văn bản đó void cut_tag_name(String path) Từ đường dẫn path (chỉ ra các file đã được huấn luyện), hàm sẽ gán tên các nhãn có thể được gán cho văn bản cần phân loại vào một mảng boolean read_lamda_file(String path_lamda_file, int tag_arg) Đọc file đã được huấn luyện với đường dẫn path_lamda_file và có nhãn là tag_arg rồi lưu vào mảng void read_all() Đọc tất cả các file đã được huấn luyện với đường dẫn tới các file huấn luyện đã được chỉ ra boolean read_nonsensical_word(String fileName) Đọc file stop-word với đường dẫn file stop-word là fileName boolean nonsensical_word(String word) Kiểm tra xem từ word có phải là stop-word không. Nếu đúng kết quả trả lại là true và false nếu ngược lại void test_event() Thực hiện chức năng kiểm thử void set_tag() Thực hiện chức năng gán nhãn boolean read_training(String path, ArrayList variable, boolean tieng_viet) Đọc file có trong dữ liệu huấn luyện với đường dẫn path vào mảng variable void read_all(String path, boolean tieng_viet) Đọc toàn bộ các file có trong dữ liệu huấn luyện với đường dẫn path. Biến tieng_viet để thông báo dữ liệu huấn luyện là tiếng việt (true) hay tiếng Anh (false) void set_frequency(ArrayList tag_arg, ArrayList frequency_arg) Gán giá trị tần số cho từng từ trong dữ liệu huấn luyện void set_frequency_all_data() Gán giá trị tần số cho toàn bộ các nhãn trong tập dữ liệu huấn luyện void feature_selection(double feature_selection) Lọc bỏ những đặc trưng có tần số xuất hiện nhỏ hơn feature_selection void write_all(String path_frequency) Ghi các giá trị tần số ứng với các đặc trưng ra file