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

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