Đề tài Phân lớp tài liệu Web độc lập ngôn ngữ

a entropy cực đại là ta phải xây dựng được một phân phối thoả mãn các ràng buộc và gần nhất với phân phối đều. Vấn đề đặt ra ở đây là làm thế nào để ta tối ưu được 13 các ràng buộc, tức tìm ra được *p C∈ làm cực đại ( )H p . Trong những trường hợp đơn giản, chúng ta dễ dàng tìm ra mô hình phù hợp bằng các phương pháp giải tích. Tuy nhiên trong thực tế, số các ràng buộc là rất lớn và chồng chéo nhau. Vì vậy, chúng ta sẽ giải bài toán này theo một hướng tiếp cận khác. Với mỗi một đặc trưng if , ta đưa vào một tham số iλ là một thừa số nhân Lagrange. Hàm Lagrange ( ),p λΛ được định nghĩa như sau: ( ) ( ) ( ), i p i p i i p H p E f E fλ λΛ ≡ + −∑ % (7) Theo lý thuyết thừa số Lagrange, phân phối xác suất ( | )p y x làm cực đại độ đo entropy ( )H p và thoả mãn tập ràng buộc C thì cũng làm cực đại hàm ( ),p λΛ trên không gian phân phối xác xuất P. Gọi pλ là mô hình làm cực đại hàm Lagrange ( ),p λΛ , và ( )λΨ là giá trị cực đại. ( )argmax , p P p pλ λ∈= Λ (8) ( ) ( ),pλλ λΨ = Λ (9) Ta gọi ( )λΨ là hàm đối ngẫu (dual function). Các hàm pλ , ( )λΨ đã được tính toán, chúng có công thức như sau: ( ) ( ) 1( | ) exp ,i i i p y x f x y Z xλ λ λ⎛ ⎞= ⎜ ⎟⎝ ⎠∑ (10) ( ) ( ) ( )log i p i x i p x Z x E fλλ λΨ = − +∑ ∑ %% (11) Trong đó ( )Z xλ là thừa số chuẩn hoá để thoả mãn ( )| 1 y p y xλ =∑ đối với mọi x: ( ) ( )iexp ,i y i Z x f x yλ λ⎛ ⎞= ⎜ ⎟⎝ ⎠∑ ∑ Cuối cùng thay cho việc phải tìm phân phối thoả mãn tập ràng buộc lớn và phức tạp làm cực đại độ đo entropy, ta đưa về bài toán chỉ cần tìm tập tham số *λ làm cực đại hàm đối ngẫu ( )λΨ không còn ràng buộc. 14 Kết quả này có một ý nghĩa quan trọng. Khi đó, bất kì một thuật toán tìm cực đại *λ cho hàm ( )λΨ có thể sử dụng để tìm ra phân phối cực đại *p của ( )H p thoả mãn *p C∈ . 2.2.2.5. Mối quan hệ với Maximum Likelihood Maximum likelihood là một phương pháp thống kê cổ điển, tư tưởng của nó là làm cực đại độ đo likelihood giữa phân phối mô hình và phân phối thực nghiệm. Hàm log-likelihood ( )pL p% của phân phối thực nghiệm p% được định nghĩa: ( ) ( ) ( ) ( ) ( ), ,, log | , log |p x yp x yx y L p p y x p x y p y x≡ =∑∏ %% % (12) Gọi pλ là mô hình làm cực đại hàm likelihood ( )pL p% , thay (10) vào phương trình (12) ta thu được biểu thức nằm bên vế phải của phương trình (11). Từ đó ta có: ( ) ( )pL pλλΨ = % Đến đây với kết quả từ phần trước, ta kết luận được rằng: “Mô hình *p C∈ với entropy cực đại là mô hình dưới dạng tham số ( )|p y xλ làm cực đại likelihood trên mẫu dữ liệu huấn luyện”. Sự tương đương này cung cấp một phương pháp mới cho phép ước lượng tham số cho các phân phối mô hình dựa trên nguyên lý entropy cực đại bằng cách sử dụng các phép ước lượng tham số cho likelihood cực đại. 2.2.2.6. Các thuật toán ước lượng tham số Có nhiều thuật toán dùng để ước lượng tham số, điển hình là các thuật toán GIS, IIS, L-BFGS. Trong khoá luận này, chúng tôi xin giới thiệu thuật toán L-BFGS là thuật toán ước lượng tập tham số hiệu quả nhất hiện nay. Cho tập dữ liệu huấn luyện ( ) ( ){ }1 1, ,..., ,N NT x y x y= . Phân phối mũ: ( ) ( ) 1( | ) exp ,i i i p y x f x y Z xλ λ λ⎛ ⎞= ⎜ ⎟⎝ ⎠∑ Huấn luyện mô hình entropy cực đại chính là ước lượng tập trọng số { },...,i kλ λ λ= để phân phối mũ ở trên đạt cực đại cao nhất. 15 Thuật toán L-BFGS là phương pháp giới hạn bộ nhớ cho phương pháp quasi- Newton (Limited memory BFGS). Phương pháp này cung cấp khả năng tối ưu hàng triệu tham số với tốc độ rất nhanh vì vậy trong các nghiên cứu mới đây nó được đánh giá là hiệu quả hơn các phương pháp khác. Viết lại hàm log-likelihood khi thay ( )|p y xλ từ () vào (): ( ) ( ) ( ) 1 1 1 1 , log exp , N k N k j j i i j j i i j i a A j L p f x y f y xλ λ λ = = = ∈ = ⎛ ⎞= − ⎜ ⎟⎝ ⎠∑∑ ∑ ∑ ∑ Tư tưởng của thuật toán là sử dụng phương pháp leo đồi tìm kiếm cực đại toàn cục. Vì bề mặt của hàm ( )L pλ là lồi nên hoàn toàn có thể thực hiện được điều này. Các thủ tục lặp được sử dụng để tiến gần đến tối ưu toàn cục của hàm ( )L pλ . Tại mỗi bước lặp ta tìm vec-tơ gradient nào có hướng tiến tới cực đại toàn cục nhất. Trên bề mặt của một hàm lồi, vec-tơ gradient thoả mãn điều kiện đó sẽ có giá trị bằng 0 r . Với mỗi một vec-tơ gradient ( ) ( ) 1 ,..., N L p L pλ λ λ λ ∂ ∂⎛ ⎞⎜ ⎟∂ ∂⎝ ⎠ hiện tại xác định cho ta một tập các trọng số. Thành phần thứ i của vec-tơ gradient của ( )L pλ là: ( ) ( ) ( )( ) ( )( )( ) ( ) ( ) ( ) ( ) ( ) n i=1 n 1 1 i=1 1 1 exp , , , exp , , | , , , N N i i j j jy Y i j j j ji i i jy Y N N i j j j i j j j y Y p i p i f y x f y xL p f x y f y x f x y p y x f y x E f x y E f x yλ λ λ λ λ λ ∈ = = ∈ = = ∈ ∂ = −∂ = − = − ∑ ∑∑ ∑ ∑ ∑ ∑ ∑∑ % Trong mỗi bước lặp thủ tục L-BFGS yêu cầu giá trị hiện tại của ( )L pλ và vec-tơ gradient hiện tại. Sau đó nó tính toán để cập nhật giá trị mới cho tập tham số { }1,..., Nλ λ . Cuối cùng, ta thu được tập trọng số tối ưu { }* *1 ,..., Nλ λ sau một số hữu hạn các bước lặp. ( ) ( ) ( )( ) | | p x y p y p y x p x = 16 2.3. Tổng kết chương Trong chương này chúng ta đã xem xem xét các vấn đề cơ bản của nguyên lý entropy cực đại theo hướng ứng dụng vào bài toán phân lớp văn bản. Chúng ta đã hiểu được tư tưởng chủ đạo của nguyên lý entropy, thấy được khả năng cho phép tích hợp được hàng nghìn đặc trưng của mô hình này. Chương này cũng trình bày được mối liên hệ giữa lilelihood cực đại và entropy cực đại, đó là sự tương đương trong ước lượng tham số cho mô hình tối ưu. Thuật toán ước lượng L-BFGS là phương pháp ước lượng tham số tối ưu thông qua log-likelihood cũng đã được trình bày ở đây. Điều đó khẳng định sức mạnh của phương pháp entropy cực đại, đặc biệt là khi ứng dụng vào bài toán phân lớp văn bản. Chương đầu đã giới thiệu về bài toán phân lớp văn bản độc lập ngôn ngữ nói chung và bài toán phân lớp tài liệu web độc lập ngôn ngữ nói riêng. Chương tiếp theo sẽ đề cập đến bài toán chính của khoá luận một cách chi tiết, phân tích những vấn đề sẽ gặp phải với bài toán phân lớp văn bản độc lập ngôn ngữ. Và cũng trong chương tới, chúng ta sẽ xem xét việc xây dựng bộ phân lớp tài liệu web độc lập ngôn ngữ với mô hình entropy cực đại. 17 Chương 3 PHÂN LỚP TÀI LIỆU WEB ĐỘC LẬP NGÔN NGỮ VỚI MÔ HÌNH ENTROPY CỰC ĐẠI 3.1 Giới thiệu Trong chương 1, chúng ta đã giới thiệu một cách tổng quát về bài toán phân lớp văn bản độc lập ngôn ngữ, về các những nhu cầu thực tế, ứng dụng cũng như ý nghĩa của bài toán. Chương này trình bày việc giải quyết bài toán phân lớp độc lập ngôn ngữ, phân tích đầy đủ các vấn đề là thách thức đối với bài toán, và đưa ra các cách giải quyết cho các vấn đề đó. Trong đó có đề xuất một chiến lược loại bỏ stop- word trong n-gram khá hiệu quả. Đồng thời, trong chương này cũng trình bày được các bước xây dựng bộ phân lớp ứng dụng nguyên lý entropy cực đại. Đặc biệt ở phần cuối chương chúng tôi đề xuất cách xây dựng một bộ phân lớp văn bản có khả năng đặc biệt, cho phép phân lớp và nhận dạng ngôn ngữ cho văn bản mà không cần sử dụng công cụ nhận dạng. 3.2. Bài toán phân lớp văn bản độc lập ngôn ngữ Như đã phân tích ở chương 1, nhu cầu phân lớp và lọc các tài liệu web đa ngôn ngữ hiện nay là rất cần thiết. Vì vậy bài toán phân lớp văn bản cho nhiều ngôn ngữ ra đời. Kèm theo đó là những vấn đề mà bài toán phân lớp văn bản đa ngôn ngữ nói chung, bài toán phân lớp văn bản độc lập ngôn ngữ nói riêng cần phải giải quyết. Hai vấn đề quan trọng nhất: 9 Sự nhập nhằng ngôn ngữ: giữa hai hay nhiều ngôn ngữ có từ trùng nhau - vấn đề này chưa hề xuất hiện trong các bài toán phân lớp văn bản trên một ngôn ngữ. 9 Số lượng đặc trưng vô cùng lớn có thể dẫn tới bùng nổ tổ hợp. Vì vậy nhiệm vụ cốt lõi cho bài toán là phải có những chiến lược trích chọn đặc trưng tốt. 3.2.1. Vấn đề nhập nhằng ngôn ngữ Trường hợp xuất hiện các từ giống nhau giữa hai ngôn ngữ không phải hiếm, trong khoá luận này tạm gọi đó là hiện tượng nhập nhằng ngôn ngữ. Ở đây đã loại trừ 18 trường hợp hai chữ khác nhau của hai ngôn ngữ có mã giống nhau vì Unicode đã hỗ trợ khả năng mã hoá và nhận diện được chúng. Ở một số ngôn ngữ có số lượng từ trùng nhau nhiều nhưng nghĩa của chúng lại gần như tương đồng. Ví dụ, chữ Trung Quốc và Nhật Bản cùng sử dụng một lượng lớn chữ Kanji nhưng nghĩa lại hoàn toàn giống nhau. Hoặc với tiếng Anh, Pháp, Đức là ba ngôn ngữ có hệ từ vựng khá giống nhau, các từ giống nhau thì nghĩa cũng khá giống nhau. Các trường hợp nêu trên thường chỉ xảy ra với các ngôn ngữ cùng một Hệ chữ viết. Còn trong trường hợp các ngôn ngữ khác hệ chữ viết, có khi cả các ngôn ngữ trong cùng một Hệ chữ viết vẫn xảy ra sự nhập nhằng. Ví dụ: chữ “can” trong tiếng Việt có nghĩa hoàn toàn khác với chữ “can” trong tiếng Anh. Nếu xét về bản chất, vấn đề này giống như hiện tượng đồng âm khác nghĩa của từ trong bài toán phân lớp văn bản đơn ngôn ngữ. Do đó nghĩa của từ dễ dàng được xác định khi có sự hỗ trợ của các từ xung quanh. Rõ ràng “can_nước” khác với “can_you” nên đặc trưng của các N- gram này có độ tin cậy cao khi phân lớp. Mà xu thế những đặc trưng có đô tin cậy cao thì được gán trọng số lớn hơn trong quá trình học. Như vậy, qua đây có thể khẳng định vấn đề nhập nhằng ngôn ngữ không ảnh hưởng đến độ chính xác của bộ phân lớp, nếu có cũng chỉ là rất nhỏ. 3.2.2. Vấn đề bùng nổ đặc trưng Trong các bài toán phân lớp văn bản trên một ngôn ngữ thì giai đoạn lựa chọn đặc trưng luôn được coi là một nhiệm vụ quan trọng. Đặc trưng càng được lựa chọn tinh tế thì độ chính xác và tốc độ của bộ phân lớp càng tăng. Với bài toán phân lớp văn bản đa ngôn ngữ nói chung và bài toán phân lớp văn bản độc lập ngôn ngữ nói riêng còn xảy ra hiện tượng bùng nổ đặc trưng: số lượng các đặc trưng quá lớn. Ví dụ, giả sử một văn bản có độ dài trung bình là 2.000 từ, giả sử ta dùng n-gram với n= 1, 2, 3 thì với 16.000 văn bản Anh, Pháp và Việt số đặc trưng sẽ xấp xỉ 96 triệu. Đây quả là một con số khổng lồ, đòi hỏi phải thao tác trên máy tính có hiệu năng rất lớn. Với tập các đặc trưng lớn như vậy còn nảy sinh hai vấn đề: dữ liệu thưa và overfitting. Dữ liệu thưa tồn tại các đặc trưng xuất hiện rất ít, hoặc rất nhiều. Overfitting là hiện tượng tương đối đặc biệt và ít gặp trong thực tế. Vì vậy có thể nói, nhiệm vụ lựa chọn đặc trưng là một nhiệm vụ quan trọng trong bài toán phân lớp đa ngôn ngữ. 19 Để giải quyết vấn đề này, trong khoá luận chúng tôi cố gắng một cách tối đa loại bỏ những đặc trưng không quan trọng. Điều này được thực hiện trong các bước xây dựng mô hình như lọc các nhiễu một cách triệt để, đưa ra và sử dụng các chiến lược lựa chọn đặc trưng như: loại bỏ các n-gram chứa stop-word, đặt ngưỡng, sử dụng trọng số TF.IDF. 3.3. Quy trình xây dựng bộ phân lớp Các bước xây dựng bộ phân lớp được tiến hành theo một quy trình như sau: Xử lý dữ liệu Dữ liệu huấn luyện Sinh N-gram Xây dựng đặc trưng Lựa chọn đặc trưng Huấn luyện mô hình Tập trọng số Văn bản mới Văn bản được phân lớp Hình 2. Mô tả các bước xây dựng bộ phân lớp 3.3.1. Tiền xử lý dữ liệu 3.3.1.1. Lọc nhiễu Tập dữ liệu huấn luyện trong các kĩ thuật học máy giám sát luôn đòi hỏi phải được làm sạch trước khi đưa vào huấn luyện. Trên Internet có rất nhiều thông tin xuất hiện dưới nhiều dạng khác nhau. Loại bỏ đi những thông tin dưới dạng hình ảnh, âm thanh, quảng cáo, thông tin không nằm trong phần nội dung của trang web, các thẻ html,… được gọi là lọc nhiễu. 20 Làm sạch dữ liệu cho bài toán phân lớp không phải là một việc dễ dàng, và với bài toán phân lớp nhiều ngôn ngữ thì còn đòi hỏi nhiều công sức hơn. Thông thường ta lấy dữ liệu từ nhiều nguồn, nên mỗi một trang sẽ có một bố cục khác nhau, điều này gây khó khăn cho chúng ta khi muốn xây dựng một công cụ lọc nhiễu áp dụng cho tất cả các trang web. 3.3.1.2. Cây phân lớp chuẩn Cũng như các mô hình phân lớp văn bản đơn ngôn ngữ, mô hình phân lớp văn bản độc lập ngôn ngữ cũng phải xây dựng một cây phân lớp chuẩn. Cây phân lớp chuẩn là tập các lớp mà ta muốn xếp văn bản vào. Với mỗi một ứng dụng cụ thể ta phải xây dựng những cây phân lớp khác nhau. Ví dụ, cây phân lớp cho bộ lọc thư rác là: Spam, non-Spam, Warning; cây phân lớp cho bộ phân lớp lĩnh vực sách giáo khoa: Toán học, Vật lý, Hoá học,… Cây phân lớp phải đảm bảo tính toàn vẹn và tính tách rời. Một văn bản bất kì phải được phân vào một trong các lớp của cây. 3.3.2. Xây dựng đặc trưng Chúng tôi sử dụng mô hình ngôn ngữ N-gram để xây dựng các mệnh đề thông tin ngữ cảnh, từ đó xây dựng các đặc trưng trước khi đưa vào huấn luyện mô hình. 3.3.2.1. Mô hình ngôn ngữ N-gram Xét trong một văn bản, N-gram là một cụm từ gồm N từ liên tiếp cùng xuất hiện trong văn bản đó. Nếu độ dài tính theo từ của một văn bản là L, thì số N-gram sinh ra là 2 )1(* +− NLL . Như vậy N càng lớn thì số lượng N-gram sinh ra càng lớn. Qua quá trình thử nghiệm, xây dựng đặc trưng với 1, 2, 3, 4N = và với 1, 2, 3N = chúng tôi nhận thấy với cách sử dụng tối đa 3N = thời gian huấn luyện và thời gian phân lớp nhanh hơn so với cách sử dụng tối đa 4N = , trong khi đo độ chính xác mô hình là gần như nhau. Vì vậy chúng tôi sử dụng 1, 2, 3N = . 3.3.2.2. Đặc trưng Có được tập hợp các N-gram, ta tiến hành xây dựng các mệnh đề thông tin ngữ cảnh. Mệnh đề mô tả thông tin ngữ cảnh là một mệnh đề chỉ ra văn bản hiện tại chứa một N-gram nào đó. Ví dụ, [document has giá_xăng_dầu] 21 Theo cách mà nguyên lý Entropy đã cung cấp để xây dựng đặc trưng: một đặc trưng là sự kết hợp giữa mệnh đề mô tả thông tin ngữ cảnh ( )cp x và nhãn của lớp tương ứng với văn bản. Ví dụ, với 'y là lớp “bss” (business) ta có một đặc trưng như sau: ( ) ⎩⎨ ⎧ === 0 ___andif1 ,,___ truedauxanggiahasdocumentbssy yxf bssdauxanggiahasdocument Đặc trưng này sẽ có giá trị đúng nếu văn bản hiện tại chứa cụm từ “giá xăng dầu” và nó được gán nhãn “bss”. Cần chú ý rằng, số lượng các mệnh đề thông tin ngữ cảnh sinh ra nhỏ hơn số lượng các N-gram (vì có những N-gram trùng nhau cũng xuất hiện trong một văn bản), và cũng không bằng số lượng các đặc trưng. 3.3.3. Lựa chọn đặc trưng 3.3.3.1. Chiến lược loại bỏ stop-word Bản chất của các ngôn ngữ tự nhiên là luôn có các từ xuất hiện nhiều, nhưng không mang nhiều ý nghĩa để phân loại. Trong tiếng Anh gọi đó là stop-word. Ngôn ngữ nào cũng có stop-word, tuy nhiên do tiếng Anh được xử lý nhiều nên người ta xây dựng danh sách stop-word cho nó khá rõ ràng. Ở một số ngôn ngữ khác, ví dụ như tiếng Việt cũng sẽ có danh sách stop-word cụ thể như tiếng Anh nếu được xử lý nhiều trong tương lai [2]. Stop-word không những dư thừa, khi kết hợp với các từ khác để xây dựng đặc trưng chúng còn gây ra hiện tượng overfitting. Qua thử nghiệm trên một bộ phân lớp văn bản trên tiếng Anh, sau khi lọc stop-word độ chính xác huấn luyện (trainning accuracy) tăng lên đáng kể. Vì vậy loại bỏ stop-word là rất cần thiết. Tuy nhiên, nếu đối với bài toán phân lớp văn bản trên nhiều ngôn ngữ, loại bỏ stop-word cho văn bản thì nghiễm nhiên các văn bản đã mất đi sự bình đẳng. Nói cách khác, các văn bản đòi hỏi được nhận dạng ngôn ngữ. Bài toán phân lớp trong Khóa luận không hướng tới việc nhận dạng ngôn ngữ để loại bỏ stop-word nhưng làm thế nào để loại bỏ chúng. Ở đây, chúng tôi đề xuất một phương pháp khá hiệu quả: vẫn tận dụng được đặc điểm về ngôn ngữ mà vẫn giữ tính độc lập ngôn ngữ của bài toán. Phương pháp này áp dụng sau khi sinh n-gram, và loại bỏ theo hai quy tắc sau: - Loại bỏ các 1-gram, 2-gram, 3-gram là stop-word: điều này có lợi với các ngôn ngữ mà đơn vị nhỏ nhất không phải là từ. Ví dụ, với tiếng Việt đơn vị nhỏ nhất là âm tiết: từ “có_thể” rõ ràng là một stop-word. 22 - Loại bỏ 2-gram, 3-gram mà mỗi gram là một stop-word. Ví dụ, câu “he is in Hanoi” sinh ra 2-gram “is_in” chứa 2 stop-word là “is” và “in”. Qua thực nghiệm mà chúng tôi tiến hành, phương pháp này làm giảm đi 31,7% tổng số đặc trưng so với loại stop-word từ văn bản trước khi sinh n-gram là 33%. Như vậy đây thực sự là chiến lược tốt. 3.3.3.2. Đặt ngưỡng Thực tế cho thấy, có những mệnh đề thông tin ngữ cảnh xuất hiện nhiều lần trong một văn bản và những mệnh đề thông tin ngữ cảnh xuất hiện rất ít lần. Ví dụ trong câu “Giá dầu đang ngày một leo thang”: [document has dầu_đang_ngày] Để loại bỏ những mệnh đề thông tin ngữ cảnh không có nhiều ý nghĩa này, chiến lược lọc đặt ngưỡng chỉ đơn giản đặt ngưỡng cho sự xuất hiện của một mệnh đề thông tin ngữ cảnh trong toàn bộ tập mệnh đề thông tin ngữ cảnh: nếu số lần xuất hiện nằm ngoài một khoảng nào đó thì bị loại bỏ. 3.3.3.3. TF.IDF TF.IDF là một kĩ thuật thống kê đánh giá ý nghĩa, độ quan trọng của một cụm từ đối với một văn bản, hoặc một lớp. TF (term frequency) là độ đo tần số: tần suất xuất hiện của cụm từ trong một văn bản: i kk ntf n = ∑ in là số lần xuất hiện của cụm từ trong toàn bộ văn bản. IDF (inverse document frequency) là độ đo tổng quát độ quan trọng của cụm từ: Trọng số TF.IDF được tính bằng công thức: ( ). log j i D tf idf tf d t ⎛ ⎞⎜ ⎟= × ⎜ ⎟⊃⎝ ⎠ trong đó, - D: là số các văn bản trong tập dữ liệu huấn luyện. - ( )ij td ⊃ : là số các văn bản mà cụm từ ti xuất hiện thoả mãn in khác 0. 23 Một cụm từ t xuất hiện nhiều lần trong văn bản, và xuất hiện ít lần trong các văn bản khác của tập dữ liệu mẫu thì có trọng số TF.IDF cao. Với tính chất như vậy, TF.IDF có ý nghĩa trong việc lọc bỏ các cụm từ chung. Chúng ta cũng có thể sử dụng phương pháp này để tìm những cụm từ mang ý nghĩa phân lớp cao bằng cách đánh trọng số của từ trên một lớp. 3.3.4. Huấn luyện mô hình Sau khi đã xây dựng được tập các đặc trưng ta tiến hành huấn luyện mô hình. Ở bước này chính là lúc áp dụng các thuật toán ước lượng tham số để tìm ra tập trọng số λ (mỗi một đặc trưng if sẽ được gán một trọng số iλ ). Một văn bản mới có một tập các đặc trưng, chính tập trọng số sẽ quyết định mức độ quan trọng của các đặc trưng và chúng ảnh hưởng trực tiếp đến quá trình phân lớp cho văn bản mới, từ đó dự đoán một cách chính xác lớp cho văn bản đó. Trong quá trình huấn luyện mô hình, chúng ta cần tiến hành đánh giá độ chính xác của bộ phân lớp. Nói cách khác, trong quá trình này cần đánh giá khả năng đoán nhận của mô hình thông qua độ chính xác (accuracy) của quá trình huấn luyện. 3.3.5. Phân lớp văn bản mới Với một văn bản mới, bộ phân lớp sẽ thực hiện tính toán xác suất trên từng lớp của văn bản. Tổng các giá trị xác suất này bằng 1. Lớp nào có giá trị cao nhất, văn bản sẽ thuộc lớp đó. Lớp cho văn bản mới được tính theo công thức sau: * argmax ( | ) y y p y xλ= trong đó, *y là lớp tương ứng với xác suất ( )xyp |λ cao nhất. Hàm argmax là hàm cực đại đối số, nó trả về giá trị của argument (ở đây là y) mà tại đó hàm đạt max. Rõ ràng, những đặc trưng quan sát được trong văn bản mới mà không có trong mô hình, tức là không quan sát thấy trong tập dữ liệu huấn luyện sẽ nhận giá trị sai, xem như là không có vì vậy chúng không làm ảnh hưởng đến xác suất của văn bản trên từng lớp. Chỉ những đặc trưng có giá trị là đúng mới có ý nghĩa quan trọng quyết định văn bản đó thuộc lớp nào. Thực tế, tính tách rời của cây phân lớp chuẩn khó có thể được đảm bảo, vì có rất nhiều văn bản có thể được chia vào nhiều lớp. Trong trường hợp này, chúng ta sẽ sử dụng chiến lược phân đa lớp dựa trên độ lệch chuẩn đã đề xuất tại [1]. 24 3.4. Đánh giá độ chính xác của bộ phân lớp Bên cạnh việc xây dựng một bộ phân lớp hoàn chỉnh thì việc đánh giá ước lượng độ chính xác của bộ phân lớp đó không kém phần quan trọng. Trên cơ sở đó mới so sánh được chất lượng của các bộ phân lớp khác nhau (trên cùng một tập dữ liệu thử nghiệm). Đã có rất nhiều các phương pháp ước lượng độ chính xác của một bộ phân lớp, ví dụ như: handout method, ước lượng chéo trên k tập con (k-fold cross validation), hay leave-one-out cross validation,… Trong khoá luận, chúng tôi sử dụng phương pháp ước lượng chéo trên k tập con. Ý nghĩa của phương pháp này là để đo độ chính xác của mô hình trên toàn tập dữ liệu; có nghĩa là đánh giá mức độ thích ứng cũng như sức mạnh phân lớp của mô hình một cách chính xác hơn, toàn diện hơn. 3.4.1. Các độ đo Độ hồi tưởng, độ chính xác, độ đo F1 là các độ đo cơ bản trong lý thuyết nhận thông tin (Information Retrival). 2* * num_of_matchprecision num_of_model num_of_matchrecall num_of_manual precision recallF1 precision recall = = = + trong đó, - num_of_match: số lượng văn bản trùng hợp mà mô hình và con người cùng phân lớp vào một lớp nào đó. - num_of_model: số lượng văn bản mà mô hình đã gán cho một lớp nào đó. - num_of_manual: số lượng văn bản được con người (gán bằng tay) gán vào một lớp nào đó. Độ chính xác mà chúng ta sử dụng để đánh giá mô hình được tính là số lượng văn bản được phân lớp đúng bởi mô hình chia cho tổng số lượng văn bản. Vì vậy nếu xét trên tổng thế thì độ chính xác, precision, recall, F1 có cùng giá trị. 25 3.4.2. Áp dụng phương pháp ước lượng chéo trên k tập con Tư tưởng của phương pháp ước lượng chéo trên k tập con là phương pháp đánh giá độ chính xác của hệ thống thông qua việc tính toán độ chính xác trung bình trên k tập con. Ưu điểm của phương pháp này là toàn bộ tập dữ liệu huấn luyện đều được lấy làm tập kiểm tra [21]. Trong khoá luận, chúng tôi sử dụng k = 10 là giá trị phổ biến để có được một ước lượng chính xác. Hệ thống chia dữ liệu thực nghiệm thành 10 phần bằng nhau một cách ngẫu nhiên. Quá trình huấn luyện được thực hiện 10 lần. Tại lần huấn luyện thứ i ( 0 < i < 10), tập con thứ i được chọn làm tập kiểm tra, 9 tập còn lại được trộn lại với nhau làm tập huấn luyện. Cũng trong mỗi lần huấn luyện này, sau mỗi bước lặp tập trọng số λ được cập nhật, hệ thống tiến hành phân lớp tập dữ liệu kiểm tra, rồi tính toán độ chính xác của mô hình. 3.5. Xây dựng bộ phân lớp trên cây phân lớp thông minh Phần 3.2 và 3.3 đã trình bày về cách giải quyết khó khăn cho bài toán phân lớp văn bản độc lập ngôn ngữ, và cách xây dựng bộ phân lớp cho bài toán này. Tuy nhiên, có thể thấy rằng ứng dụng cho bài toán này là các bài toán không đòi hỏi nhận diện ngôn ngữ cho văn bản. Trong thực tế, có thể thấy rất nhiều ứng dụng phân lớp văn bản đòi hỏi nhận diện được ngôn ngữ. Ví dụ, bộ phân lớp sách thay cho công việc của một thủ thư kho sách điện tử cần xếp sách vào lớp với ngôn ngữ tương ứng, hay các tin bài của các hãng tin lớn cần được xếp vào chuyên mục tin của ngôn ngữ tương ứng. Tuy nhiên nếu sử dụng thêm một bộ nhận dạng ngôn ngữ tốn kém và làm chậm quá trình phân lớp. Xuất phát từ nhu cầu đó, và hướng tới các ứng dụng nhỏ khoá luận đề xuất xây dựng một bộ phân lớp văn bản độc lập ngôn ngữ trên cây phân lớp thông minh. Quá trình xây dựng bộ phân lớp này hoàn toàn giống với quá trình xây dựng bộ phân lớp trong phần 3.3. Điểm khác duy nhất nằm ở cây phân lớp. Giả sử trong cây phân lớp chuẩn của bộ phân lớp L ngôn ngữ có N lớp, thì ở cây phân lớp thông minh sẽ có L N× lớp. 26 Bảng 1. Cây phân lớp thông minh tổng quát STT lang1 lang2 … langL 1 lang1_class1 lang2_class1 … langL_class1 2 lang1_class2 lang2_class3 … langL_class2 … N lang1_classN lang2_classN … langL_classN Bộ phân lớp xây dựng trên cây phân lớp thông minh, vừa có khả năng phân lớp văn bản, vừa có khả năng nhận dạng văn bản được viết bởi nhưng ngôn ngữ nào. Đây là một ví dụ cây phân lớp thông minh cho bài toán phân lớp tác phẩm văn học: giả sử chỉ lấy trên 3 lớp là: Thơ, Truyện, Tuỳ bút đối với 2 ngôn ngữ là tiếng Anh và tiếng Trung. Bảng 2. Bảng ví dụ cho cây phân lớp thông minh STT Anh Trung Quốc Mô tả 1 en_po cn_po tác phẩm là thơ 2 en_st cn_st tác phẩm là truyện, truyện ngắn, tiểu thuyết,… 3 en_dl cn_dl tác phẩm là kí sự, tuỳ bút,… 3.5.1. Bản chất bài toán Xét hai bài toán phân lớp văn bản trên nhiều ngôn ngữ, và bài toán nhận dạng ngôn ngữ. Điểm chung giữa hai bài toán này là đều có thể sử dụng chung một tập dữ liệu chú ý rằng đây không phải là tập dữ liệu huấn luyện. Với bài toán phân lớp thì gán nhãn văn bản theo lớp, bài toán nhận dạng ngôn ngữ gán nhãn văn bản theo ngôn ngữ. Lợi dụng điều này, ta sẽ gán nhãn văn bản theo cả lớp và ngôn ngữ. Trong ví dụ trên en_po là nhãn cho lớp thơ và ngôn ngữ là tiếng Anh. Như vậy, thực chất nhãn trong cây phân lớp thông minh là bao gồm nhiều nhãn, cụ thể ở đây là: nhãn lớp (lĩnh vực) và nhãn ngôn ngữ. Chính vì lý do này, chúng tôi gọi cây phân lớp như vậy là cây phân lớp thông minh. 3.5.2. Phân lớp cho văn bản mới Với một văn bản mới, bộ phân lớp tiến hành phân lớp cho văn bản. Các bước thực hiện giống như việc phân lớp văn bản của bộ phân lớp trên cây phân lớp chuẩn. Nếu văn bản được viết bởi 1 ngôn ngữ, các n-gram sinh ra sẽ mang đặc trưng của ngôn ngữ. Nên sác xuất của văn bản đó sẽ có xu hướng nghiêng hẳn về một lớp. Với trường hợp lĩnh vực của văn bản có sự nhập nhằng ta sẽ sử dụng chiến lược phân 27 đa lớp cho văn bản. Nếu văn bản được phân vào lớp en_st tức là văn bản thuộc thể loại Truyện nhưng viết bằng tiếng Anh. Nếu văn bản được phân vào lớp cn_st và cn_dl thì văn bản được phân vào cả hai lớp Truyện và Tuỳ bút nhưng nó được viết bằng tiếng Trung. Nếu văn bản được viết bởi nhiều ngôn ngữ, sẽ xuất hiện n-gram sinh ra đặc trưng cho nhiều ngôn ngữ khác nhau. Đến đây là tiếp tục sử dụng chiến lược phân đa lớp để tìm lớp cho văn bản. Nếu văn bản được phân vào hai lớp: en_dl và cn_dl có nghĩa là văn bản thuộc lĩnh vực Tuỳ bút nhưng được viết bởi cả hai ngôn ngữ Anh và Trung. 3.5.3. Nhận xét về phương pháp Thời gian huấn luyện bằng với thời gian huấn luyện của bộ phân lớp văn bản độc lập ngôn ngữ trên cây phân lớp chuẩn. Nhưng thời gian phân lớp thì lâu hơn. Nguyên nhân là do sự kết hợp giữa tập mệnh đề thông tin ngữ cảnh và số các lớp làm số lượng đặc trưng tăng gấp L lần (số các ngôn ngữ). Do đó một lần nữa chúng ta khẳng định lại rằng, bộ phân lớp này phù hợp cho các ứng dụng nhỏ. 3.6. Tổng kết chương Chương này đã xem xét các khía cạnh điển hình về bài toán phân lớp văn bản độc lập ngôn ngữ cũng như cách xây dựng bộ phân lớp với việc ứng dụng mô hình Entropy cực đại. Đặc biệt, hai vấn đề nhập nhằng ngôn ngữ và bùng nổ đặc trưng là những khó khăn thách thức đối với bài toán phân lớp văn bản độc lập ngôn ngữ đã được phân tích và giải quyết bằng các phương pháp cụ thể. Khóa luận đã có một đề xuất lựa chọn đặc trưng rất ý nghĩa là phương pháp loại bỏ stop-word trong n-gram khá hiệu quả. Và cuối cùng một đề xuất có ý nghĩa ứng dụng và tính thực tế cao đó là việc xây dựng bộ phân lớp trên cây phân lớp thông minh. Bộ phân lớp như vậy rất hiệu quả trong việc giải quyết các bài toán phân lớp văn bản và muốn nhận dạng ngôn ngữ mà không cần sử dụng một bộ nhận dạng ngôn ngữ nào khác. Bài toán này rất phù hợp cho các ứng dụng nhỏ. Chương tiếp theo trình bày các thử nghiệm thực tế các nghiên cứu lý thuyết trên tập dữ liệu cụ thể được lấy từ các hãng tin cho hai ngôn ngữ Anh, Việt và đánh giá kết quả thu được. 28 Chương 4 KẾT QUẢ THỬ NGHIỆM VÀ ĐÁNH GIÁ 4.1. Môi trường thử nghiệm 4.1.1. Môi trường phần cứng Bài toán được thử nghiệm trên máy chủ IBM có cấu hình như sau: Bảng 3. Cấu hình hệ thống chạy thử nghiệm Thành phần Chỉ số CPU 2 Xeon 3.00GHz RAM 4096MB HDD 4 x 36.4 GB OS Debian 3.1 (Sarge) 4.1.2. Công cụ phần mềm Tồn tại một số phần mềm nguồn mở đối với bài toán phân lớp văn bản sử dụng MEM như FlexME, MaxEnt... Chúng tôi chọn lựa công cụ mã mở MaxEnt của tác giả Zhang Le tại Centre for Speech Technology Research, University of Edinburgh. Đây là một bộ công cụ ứng dụng entropy cực đại viết trên nền Python và C++. Ngoài ra, khoá luận sử dụng một số công cụ phần mềm hỗ trợ trong quá trình thử nghiệm được mô tả trong bảng sau: Bảng 4. Danh sách phần mềm sử dụng để thử nghiệm STT Tên phần mềm Nguồn 1 Offline Explorer Enterprise 2 PHP 3 Debian 3.1 Trong quá trình chuẩn bị dữ liệu, đối với mỗi ngôn ngữ tự nhiên, chúng tôi viết một số công cụ chạy trên nền Linux và bộ thông dịch PHP. 29 Bảng 5. Danh sách công cụ sử dụng để thử nghiệm STT Tên công cụ Mô tả 1 gethtml.php Thu thập các file HTML trong thư mục lưu trang Web của phần mềm Explorer Offline. 2 html2text.php Công cụ lọc nhiễu và chuyển đổi biểu diễn kí tự Unicode (NCR sang UTF-8). Công cụ này trích phần tiêu đề và nội dung bài báo. 3 text2ngram.php Công cụ sinh n-gram từ các file text do html2text.php sinh ra. Có loại bỏ các từ phổ biến. 4 maketrain.php Công cụ tạo file train từ các file n-gram do text2ngram.php sinh ra có gán nhẵn lớp tương ứng. 5 maketest.php Công cụ tạo file kiểm tra trực tiếp từ file html bất kì (có loại các thẻ HTML và chuyển đổi biểu diễn kí tự Unicode). 4.2. Dữ liệu kiểm thử Dữ liệu dùng để huấn luyện mô hình là các tin bài được lấy từ các trang báo điện tử của hai ngôn ngữ Anh và Việt. Đây đều là những hãng tin có uy tín về nội dung tin bài cũng như độ tin cậy của các chuyên mục tin được phân chia. Tiếng Anh: Tiếng Việt: Trong khoá luận chúng tôi tiến hành thử nghiệm trên từng bộ phân lớp đơn ngôn ngữ, và trên bộ phân lớp kết hợp ngôn ngữ. 4.2.1. Tiền xử lý dữ liệu Hình 3. Trang tin tức tiếng Việt VnExpress.net 30 Hình 4. Trang tin tức tiếng Anh BBC News Trong hình 3 và hình 4, chúng ta cần lấy phần “Nội dung cần lấy”, các phần còn lại được gọi là nhiễu và sẽ bị loại bỏ bằng quá trình tiền xử lý trong công cụ html2text.php. Mỗi một ngôn ngữ có một công cụ html2text.php riêng. Sau khi đã thu được các file text do html2text.php sinh ra, ta tiến hành xây dựng tập dữ liệu huấn luyện theo định dạng mà thư viện MaxEnt hỗ trợ bằng hai công cụ sau: text2ngram.php và maketrain.php. Khi đó, tệp tin sinh ra chưa dữ liệu huấn luyện theo định dạng được biểu diễn như sau: Trên một dòng, đầu dòng là nhãn của văn bản. Tiếp theo là tất cả các n-gram được sinh ra bởi văn bản đó do công cụ text2gram.php sinh ra. Cũng trong công cụ sinh n-gram từ file text (công cụ text2gram.php) chúng tôi tiến hành lọc bỏ các n-gram bằng phương pháp loại bỏ stop-word trong n-gram (giảm được ~32% tổng số n-gram). Điều này đã làm giảm đáng kể các đặc trưng không có ích. 4.2.2. Cây phân lớp Quan sát hai hình vẽ trên, ta nhận thấy rõ ràng hai cây phân lớp này không giống nhau, và việc để tìm ra một cây phân lớp chung cho chúng không dễ dàng. Nói như vậy, để khẳng định một điều rằng: tìm cây phân lớp chuẩn cho bài toán phân lớp văn bản độc lập ngôn ngữ gặp nhiều khó khăn. 31 Sau khi quan sát và nghiên cứu các trang tin, chúng tôi đưa ra cây phân lớp tin tức như sau: Bảng 6. Cây phân lớp thông tin STT Tên Nhãn Mô tả 1 Kinh tế bss Các nội dung liên quan đến thị trường, kinh doanh,… 2 Giáo dục edu Các nội dung liên quan đến giáo dục. 3 Văn hoá / Giải trí ent Các nội dung liên quan đến nghệ thuật, âm nhạc, điện ảnh. 4 Sức khoẻ hel Các nội dung liên quan đến sức khoẻ. 5 Chính trị / Xã hội plt Các nội dung liên quan đến tình hình chính trị, xã hội,… 6 Khoa học sci Các nội dung liên quan đến khoa học. 7 Thể thao spt Các nội dung liên quan đến thể thao 8 Công nghệ tec Các nội dung liên quan đến công nghệ Ở tập dữ liệu huấn luyện trên từng bộ phân lớp cho một ngôn ngữ, mỗi lớp ta chọn 800 văn bản. Ở tập dữ liệu huấn luyện cho bộ phân lớp hai hoặc ba ngôn ngữ kết hợp, ta chọn mỗi lớp 600 văn bản. 4.3. Kết quả thử nghiệm Tiến hành thử nghiệm trên tập dữ liệu tiếng Anh, tập dữ liệu tiếng Việt và tập dữ liệu trộn lẫn nhau của hai ngôn ngữ Anh và Việt. 4.3.1. Quá trình huấn luyện Thông tin về tập các thông tin ngữ cảnh và các đặc trưng đối với cả 3 mô hình: Bảng 7. Tập dữ liệu huấn luyện của cả 3 mô hình Mô hình Mệnh đề thông tin ngữ cảnh Đặc trưng Tiếng Anh 3.127.333 3.709.185 Tiếng Việt 2.806.899 3.686.768 Anh – Việt 4.743.595 5.860.664 Sau 10 lần huấn luyện trên tập dữ liệu 6207 văn bản tiếng Anh, 6400 văn bản tiếng Việt và 12607 văn bản cho cả hai ngôn ngữ Anh và Việt, độ chính xác được cho trong bảng sau. Mỗi lần huấn luyện ta chỉ lấy kết quả của lần lặp có độ chính xác (accuracy) cao nhất. 32 Bảng 8. Độ chính xác 10 lần huấn luyện của tiếng Anh Fold Highest Log-likelihood Accuracy Time (s) 0 -1.447281E-04 98.55% 117.31 1 -1.435894E-04 98.39% 121.36 2 -1.450561E-04 98.07% 102.54 3 -1.433849E-04 98.87% 109.57 4 -1.425671E-04 98.07% 110.98 5 -1.455252E-04 99.19% 122.17 6 -1.444749E-04 97.90% 143.42 7 -1.450292E-04 99.19% 95.54 8 -1.417561E-04 97.74% 111.57 9 -1.440164E-04 97.26% 114.22 Trung bình -1.440127E-04 98.32% 114.87 Bảng 9. Độ chính xác 10 lần huấn luyện của tiếng Việt Fold Highest Log-likelihood Accuracy Time (s) 0 -3.056967E-04 92.19% 154.26 1 -3.048419E-04 90.31% 157.51 2 -2.988322E-04 92.03% 160.89 3 -2.722667E-04 91.25% 148.85 4 -2.994259E-04 90.63% 146.56 5 -3.022941E-04 91.25% 147.26 6 -3.152480E-04 92.03% 157.12 7 -3.350586E-04 91.88% 150.19 8 -3.773065E-04 91.56% 153.25 9 -2.782285E-04 92.50% 154.72 Trung bình -3.089199E-04 91.56% 153.06 Bảng 10. Độ chính xác 10 lần huấn luyện kết hợp Anh-Việt Fold Highest Log-likelihood Accuracy Time (s) 0 -3.278943E-04 95.21% 193.22 1 -2.680606E-04 96.04% 197.82 2 -3.204758E-04 94.27% 221.17 3 -2.829994E-04 94.06% 183.24 4 -2.668655E-04 94.17% 187.87 5 -3.191257E-04 92.92% 187.89 6 -3.248740E-04 94.90% 184.76 7 -2.815305E-04 94.38% 187.32 8 -2.663499E-04 94.79% 172.98 9 -2.792563E-04 96.25% 195.85 Trung bình -2.937432E-04 94.70% 191.21 33 84.00% 86.00% 88.00% 90.00% 92.00% 94.00% 96.00% 98.00% 100.00% 0 1 2 3 4 5 6 7 8 9 Lần huấn luyện (Fold) Đ ộ ch ín h xá c Tiếng Anh Tiếng Việt Anh - Việt Hình 5. Độ chính xác của 3 bộ phân lớp trong 10 lần huấn luyện Hình 5 là biểu đồ biểu diễn độ chính xác của 3 mô hình: Anh, Việt, Anh-Việt trên 10 fold. Mỗi fold ta chọn ra độ chính xác ở lần lặp cao nhất của mỗi mô hình. Các bảng số liệu, đồ thị biểu diễn các kết quả thử nghiệm đã trình bày ở trên cho thấy kết quả thử nghiệm rất khả quan. - Độ chính xác của bộ phân lớp tiếng Anh là: 98.32%. - Độ chính xác của bộ phân lớp tiếng Việt là: 91.56%. - Độ chính xác của bộ phân lớp tiếng Anh-Việt là: 94.70%. Biểu đồ 5 biễu diễn độ chính xác của 3 mô hình sau 10 lần huấn luyện ta nhận thấy có sự chênh lệch giữa độ chính xác của mô hình tiếng Anh và mô hình tiếng Việt, mặc dù tập dữ liệu của tiếng Việt lớn hơn của tiếng Anh (6400 văn bản và 6207 văn bản). Sở dĩ như vậy là vì, tập các đặc trưng của mô hình phân lớp tiếng Anh được lọc tinh tế hơn của tiếng Việt. Trong quá trình xử lý dữ liệu trước khi đưa vào huấn luyện, chúng tôi sử dụng công cụ text2ngram.php và làm giảm được 32% tổng số đặc trưng cho mô hình phân lớp tiếng Anh, và giảm 6% tổng số đặc trưng cho mô hình phân lớp tiếng Việt. Vì vậy, từ kết quả hai bộ phân lớp trên hai ngôn ngữ Anh và Việt chúng ta có kết luận như sau: - Khẳng định tính đúng đắn của kết luận trong lý thuyết rằng đặc trưng được chọn lọc càng tinh tế thì độ chính xác càng tăng. - Sử dụng phương pháp lọc bỏ stop word đã đề xuất ở phần lý thuyết cho kết quả tốt. Do tiếng Anh được xử lý nhiều nên danh sách stop word khá đầy đủ, việc lọc bỏ sẽ dễ dàng và đạt hiệu quả cao. Trong khoá luận chúng tôi 34 đưa ra thống kê chưa đầy đủ các stop word trong tiếng Việt nên kết quả có phần hạn chế. Cũng trên hình 5, chúng ta có sự so sánh độ chính xác giữa 3 mô hình: Anh, Việt và Anh-Việt. Độ chính xác của mô hình Anh-Việt luôn nằm giữa hai độ chính xác của mô hình tiếng Anh và mô hình tiếng Việt. Rõ ràng sự nhập nhằng của hai ngôn ngữ Anh và Việt không ảnh hưởng nhiều đến độ chính xác của mô hình Anh-Việt. Và kết quả của mô hình này cho thấy rõ điều đó: 94.70%. Quan sát các bảng 8, 9 và 10, ta dễ dàng nhận thấy thời gian huấn luyện rất nhanh. Trung bình một lần huấn luyện trên bộ phân lớp văn bản tiếng Anh là 114.87 (s). Đến đây ta khẳng định sức mạnh của phương pháp entropy cực đại bằng kết quả của các con số: tích hợp gần 6 triệu đặc trưng vào mô hình và chỉ huấn luyện trong 32 phút (mô hình Anh-Việt). 4.3.2. Lần lặp cho độ chính xác cao nhất 0.00% 20.00% 40.00% 60.00% 80.00% 100.00% 120.00% 0 5 10 15 20 25 30 Bước lặp Đ ộ ch ín h xá c Tiếng Anh Tiếng Việt Anh-Việt Hình 6. Sự phụ thuộc độ chính xác theo bước lặp của cả 3 mô hình Hình vẽ trên biểu diễn sự phụ thuộc độ chính xác theo bước lặp của cả 3 mô hình. Số liệu dùng để vẽ đồ thị được lấy từ thông số của lần huấn luyên có độ chính xác cao nhất tại mỗi mô hình. Từ đồ thị trên ta có nhận xét rằng tốc độ tăng của độ chính xác tại mỗi bước lặp là không đều nhau. Điều này có thể lý giải được bằng hiện tượng overfitting. Tức là, ngay trên chính tập dữ liệu huấn luyện, những đặc trưng xuất hiện trong 1 phần kiểm tra không xuất hiện trong tập dữ liệu học của 9 phần sẽ không được nhận biết. 35 4.3.3. Kết quả kiểm tra trên dữ liệu mới Tập dữ liệu kiểm tra bao gồm 400 văn bản tiếng Anh, 400 văn bản tiếng Việt được lấy từ nhiều nguồn. Number of Predicates: 4743595 Number of Parameters: 5860664 Optimized version iter loglikelihood training accuracy heldout accuracy ================================================================== 0 -2.079442E+00 12.500% 12.500% 1 -1.566180E+00 67.656% 44.250% 2 -9.132070E-01 84.167% 59.750% 3 -7.543474E-01 87.490% 66.625% 4 -5.646942E-01 91.479% 71.875% 5 -4.754881E-01 92.323% 74.500% 6 -3.445148E-01 93.906% 81.250% 7 -2.715653E-01 94.385% 80.875% 8 -1.921838E-01 95.823% 82.750% 9 -1.628873E-01 96.448% 83.125% 10 -1.205699E-01 97.260% 83.625% 11 -9.134130E-02 97.781% 85.500% 12 -7.489992E-02 98.240% 85.750% 13 -5.539846E-02 98.740% 85.625% 14 -2.927394E-02 99.365% 85.250% 15 -1.338378E-02 99.698% 85.625% 16 -6.036523E-03 99.896% 85.250% 17 -4.328826E-03 99.938% 85.250% 18 -1.414540E-03 100.000% 84.875% 19 -9.727452E-04 100.000% 84.875% 20 -7.786723E-04 100.000% 85.000% 21 -5.644801E-04 100.000% 84.500% 22 -4.865722E-04 100.000% 84.375% 23 -4.318329E-04 100.000% 84.125% 24 -4.265314E-04 100.000% 84.125% 25 -4.217743E-04 100.000% 84.125% 26 -4.120439E-04 100.000% 84.125% 27 -3.779965E-04 100.000% 83.875% 27 -3.889546E-04 100.000% 83.625% 28 -3.629248E-04 100.000% 83.750% 29 -3.607414E-04 100.000% 83.875% 30 -3.365570E-04 100.000% 83.875% Maximum numbers of 30 iterations reached in 199.81 seconds Highest log-likelihood: -3.365570E-04 Accuracy: 83.875% Hình 7. Kết quả kiểm tra bộ dữ liệu độc lập Anh-Việt Đây là kết quả xuất ra của quá trình kiểm tra mô hình Anh-Việt trên nguồn dữ liệu hoàn toàn mới. Kết quả nhận được là: 83.875%. Kết quả này rất có ý nghĩa, nó thể hiện sức mạnh thực sự của mô hình, nó nói lên khả năng đoán nhận của mô hình với dữ liệu mới. Cột log likelihood là giá trị của hàm log likelihood tại lần lặp hiện tại. Cột training accuracy là độ chính xác huấn luyện được tính bằng độ chính xác (precision). 36 Trong quá trình thử nghiệm trên nhiều tập kiểm tra, kết quả thực nghiệm cho thấy rằng một mô hình có mạnh hay không còn phụ thuộc vào nguồn dữ liệu huấn luyện. Dữ liệu huấn luyện được thu thập càng phong phú, khả năng đoán nhận của mô hình với dữ liệu mới càng tăng. Chúng tôi đã tiến hành thử nghiệm mô hình tiếng Anh trên hai tập kiểm tra. Một tập được lấy từ các nguồn tin bài rất lạ, là các trang tin bài của Mỹ (New York Times, Washington Post,…) và một tập là trên các trang tin của Anh (Guaridan Unlimited). Kết quả test tương ứng là 52.23% và 96.75%. Có sự chênh lệch này là do tập dữ liệu huấn luyện của mô hình tiếng Anh không đủ phong phú để cho phép mô hình đoán nhận dữ liệu “lạ”. Vì vậy chúng ta có kết luận rằng muốn xây dựng một bộ phân lớp có khả năng đoán nhận một cách toàn diện phải xây dựng một tập dữ liệu huấn luyện đủ lớn, đủ phong phú. 4.4. Tổng kết chương Trong chương này chúng ta đã xem xét những kết quả của quá trình huấn luyện và kiểm tra mô hình phân lớp tài liệu web ứng dụng mô hình entropy cực đại. Tập dữ liệu huấn luyện của mô hình được xây dựng công phu từ 6207 văn bản tiếng Anh và 6400 văn bản tiếng Việt. Chúng ta cũng đã xem xét những đánh giá về kết quả thực nghiệm và đưa ra những kết luận khẳng định mạnh mẽ hơn tính đúng đắn cho những nghiên cứu lý thuyết ở ba chương trước. Qua kết quả thử nghiệm và những đánh giá đó chúng ta nhận thấy rằng với khả năng đoán nhận lên tới 94.70%, bài toán phân lớp văn bản độc lập ngôn ngữ nói chung và bài toán phân lớp tài liệu web độc lập ngôn ngữ nói riêng rất có triển vọng áp dụng vào các ứng dụng trong tương lai. 37 KẾT LUẬN Khoá luận đã tìm hiểu và nghiên cứu về bài toán phân lớp văn bản độc lập ngôn ngữ. Các vấn đề cơ bản của bài toán đã được trình bày, phân tích và đưa ra các hướng giải quyết cụ thể. Khoá luận đã sử dụng tiếp cận entropy cực đại là một phương pháp rất phù hợp với những bài toán có số lượng đặc trưng lớn như bài toán phân lớp văn bản nói chung và bài toán phân lớp văn bản độc lập ngôn ngữ nói riêng. Những kết quả chính mà khoá luận đạt được: - Đề xuất xây dựng một bộ phân lớp văn bản cho nhiều ngôn ngữ mà không cần nhận biết ngôn ngữ sử dụng phương pháp entropy cực đại. - Phân tích và đưa ra các phương pháp nhằm khắc phục hai vấn đề cơ bản của bài toán phân lớp văn bản độc lâp ngôn ngữ: sự nhập nhằng ngôn ngữ và sự bùng nổ đặc trưng. - Đưa ra một phương pháp lựa chọn đặc trưng một cách khá hiệu quả. - Đề xuất xây dựng bộ phân lớp trên cây phân lớp thông minh với khả năng nhận diện ngôn ngữ và phân lớp cho các ứng dụng vừa và nhỏ. - Kiểm thử trên một tập dữ liệu lớn của hai ngôn ngữ Anh và Việt, và đã cho kết quả khả quan. Kết quả thực nghiệm trên tập dữ liệu trộn văn bản của hai ngôn ngữ Anh và Việt cho thấy rất khả quan và có nhiều triển vọng ứng dụng thực tế cao với độ chính xác huấn luyện lên tới xấp xỉ 95%. Do khuôn khổ có hạn về thời gian cũng như lượng kiến thức có được và gặp khó khăn trong quá trình thu thập dữ liệu thử nghiệm nên còn một số vấn đề mà khoá luận phải tiếp tục hoàn thiện và phát triển trong thời gian tới: - Thử nghiệm trên một tập dữ liệu lớn hoàn chỉnh, phong phú về ngôn ngữ. - Xây dựng các phương pháp hiệu quả hơn trong việc khắc phục vấn đề bùng nổ đặc trưng: ví dụ như trừu tượng hoá dữ liệu là số và ngày tháng. Tích hợp mô hình vào mô-đun bộ lọc nội dung và mô-đun phân lớp của máy tìm kiếm Vinahoo. 38 Phụ lục DANH SÁCH STOP-WORD Danh sách các stop word của tiếng Anh có trong [23]: a's able about above according accordingly across actually after afterwards again against ain't all allow allows almost alone along already also although always am among amongst an and another any anybody anyhow anyone anything anyway anyways anywhere apart appear appreciate appropriate are aren't around as aside ask asking associated at available away awfully be became because become becomes becoming been before beforehand behind being believe below beside besides best better between beyond both brief but by c'mon c's came can can't cannot cant cause causes certain certainly changes clearly co com come comes concerning consequently consider considering contain containing contains corresponding could couldn't course currently definitely described despite did didn't different do does doesn't doing don't done down downwards during each edu eg eight either else elsewhere enough entirely especially et etc even ever every everybody everyone everything everywhere ex exactly example except far few fifth first five followed following follows for former formerly forth four from further furthermore get gets getting given gives go goes going gone got gotten greetings had hadn't happens hardly has hasn't have haven't having he he's hello help hence her here here's hereafter hereby herein hereupon hers herself hi him himself his hither hopefully how howbeit however i'd i'll 39 i'm i've ie if ignored immediate in inasmuch inc indeed indicate indicated indicates inner insofar instead into inward is isn't it it'd it'll it's its itself just keep keeps kept know knows known last lately later latter latterly least less lest let let's like liked likely little look looking looks ltd mainly many may maybe me mean meanwhile merely might more moreover most mostly much must my myself name namely nd near nearly necessary need needs neither never nevertheless new next nine no nobody non none noone nor normally not nothing novel now nowhere obviously of off often oh ok okay old on once one ones only onto or other others otherwise ought our ours ourselves out outside over overall own particular particularly per perhaps placed please plus possible presumably probably provides que quite qv rather rd re really reasonably regarding regardless regards relatively respectively right said same saw say saying says second secondly see seeing seem seemed seeming seems seen self selves sensible sent serious seriously seven several shall she should shouldn't since six so some somebody somehow someone something sometime sometimes somewhat somewhere soon sorry specified specify specifying still sub such sup sure t's take taken tell tends th than thank thanks thanx that that's thats the their theirs them themselves then thence there there's thereafter thereby therefore therein theres thereupon these they they'd they'll they're they've think third this thorough thoroughly those though three through throughout thru 40 thus to together too took toward towards tried tries truly try trying twice two un under unfortunately unless unlikely until unto up upon us use used useful uses using usually value various very via viz vs want wants was wasn't way we we'd we'll we're we've welcome well went were weren't what what's whatever when whence whenever where where's whereafter whereas whereby wherein whereupon wherever whether which while whither who who's whoever whole whom whose why will willing wish with within without won't wonder would would wouldn't yes yet you you'd you'll you're you've your yours yourself yourselves zero Danh sách stop word của tiếng Việt được thống kê trong [2]: và còn hay hoặc không không những không chỉ mà còn nếu thì nên hễ tuy nhưng vả lại giá vì bởi tại do song dầu mặc dầu dù dẫu dẫu cho chẳng lẽ làm như thế mà vậy mà có điều hơn nữa huống hồ huống gì huống nữa ngay cũng chính cả 41 TÀI LIỆU THAM KHẢO [1] Nguyễn Việt Cường, Bài toán lọc và phân lớp tài liệu Web tiếng Việt với hướng tiếp cận entropy cực đại, Luận văn tốt nghiệp đại học, Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội, 2005. [2] Nguyễn Đức Dân, Lô gich ngữ nghĩa cú pháp, NXB ĐH&TH chuyên nghiệp, Hà Nội, 1987. [3] Nguyễn Cẩm Tú, Nhận biết các loại thực thể trong văn bản tiếng Việt nhằm hỗ trợ Web ngữ nghĩa và tìm kiếm hướng thực thể, Luận văn tốt nghiệp đại học, Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội, 2005. [4] Berger, A., Della Pietra, S., and Della Pietra, V. A maximum entropy approach to natural language processing. Computational Linguistics, volume 22, number 1, 1996, pages 39-71. [5] Cavnar, W. B. and Trenkle, J. M. N-Gram-Based Text Categorization. Proceedings of {SDAIR}-94, 3rd Annual Symposium on Document Analysis and Information Retrieval, 1994, pages 161-175. [6] Darroch, J. and Ratcliff, D. Generalized iterative scaling for log-linear models. Annals Mathematical Statistics, volume 43, number 5, 1972, pages 1470–1480. [7] Fuchen, P., Dale, S. and Shaojun, W. Language and Task independent text categorizationg with simple language models, Proceedings of HLT-NAACL, 2003 [8] Jaynes, E. R. (1957). Information Theory and Statistical Mechanics. Physic Review, volume 106, 1957, pages 620-630. [9] Joachims, T. Text Classification with Support Vector Machines: Learning with many relevant features. Machine Learning: ECML-98, Tenth European Conference on Machine Learning, 1998, pages 137-142. [10] Liu, D. C. and Nocedal J. On the limited memory BFGS method for large scale optimization. Mathematical Programming, volume 45, number 3, 1989, pages 503-528. 42 [11] Malouf, R. A comparison of algorithms for maximum entropy parameter estimation. Proceedings of the Sixth Conference on Natural Language Learning (CoNLL-2002), 2002, pages 183-186. [12] Nigam, K., Lafferty, J. and McCallum, A. Using maximum entropy for text classification. IJCAI-99 Workshop on Machine Learning for Information Filtering, 1999, pages 61-67. [13] Nigam K., McCallum, A., Thrun S. and Mitchell, T. Text Classification from Labeled and Unlabeled Documents using EM. Machine Learning, volume 39, number 2/3, 2000, pages 103-134. [14] Ratnaparkhi, A. A Maximum Entropy Part-Of-Speech Tagger. Proceedings of the Empirical Methods in Natural Language Processing Conference, May 17-18, 1996. [15] Ratnaparkhi, A. A simple introduction to maximum entropy models for natural language processing. Technical Report 97-08, Institute for Research in Cognitive Science, University of Pennsylvania, 1997. [16] Ratnaparkhi, A. Maximum Entropy Models for Natural Language Ambiguity Resolution. Ph.D. thesis, University of Pennsylvania, Philadelphia, PA, 1998. [17] Rosenfeld, R. A maximum entropy approach to adaptive statistical language modeling. Computer, Speech, and Language, volume 10, 1996, pages 187-228. [18] Zhang, L., Maximum Entropy Modeling Toolkit for Python and C++, 2004. [19] Website: [20] Website: [21] Website: [22] Website: [23] Website: