Khóa luận Phân lớp tài liệu web độc lập ngôn ngữ

rác (non-Spam), để xem xét (warning). Quan sát từ tập dữ liệu mẫu là 1.000 thư đã được gán nhãn, ta có nhận xét như sau: “nếu thư có chứa cụm từ “sản phẩm mới”, thì xác suất thư đó là thư rác là 80%”. Đây chính là một thống kê. Trong [4] đưa ra cách biểu diễn sự kiện “thư có chứa cụm từ “sản phẩm mới” là thư rác” như sau: ( ), 1 if and, 0document_has san_pham_moi Spam y Spam document_has san_pham_moi true f x y = =⎧= ⎨⎩ Gọi hàm f được biểu diễn như trên là hàm đặc trưng hay đặc trưng. Giá trị kì vọng của f đối với phân phối thực nghiệm ( , )p x y% là giá trị thống kê được một cách chính xác (trong ví dụ trên thì đó là: 0,8): số lần xuất hiện của f trong tập dữ liệu huấn luyện. Nó được biểu diễn như sau: ( ) ( ) , , ,p i i x y E f p x y f x y=∑% % (4) Bất kì thống kê nào sinh ra từ tập dữ liệu mẫu cũng có thể được biểu diễn một hàm kì vọng của đặc trưng f theo quy tắc như trên. Trong [16] cung cấp một cách có hệ thống cách xây dựng hàm đặc trưng. Thông tin “thư có chứa cụm từ “sản phẩm mới”” được xây dựng thành một mệnh đề thông tin ngữ cảnh: [document_has sản phẩm mới] → { },true false kí hiệu là ( )cp x , hàm này là một ánh xạ cặp ( ),x y một giá trị trong tập { },true false . Nó có dạng tổng quát như sau: ( ) { }: ,cp x X true false→ Trong [16] biễu diễn hàm đặc trưng dạng tổng quát: ( ) ( ), ' 1 ', 0cp y y y cp x true f x y = =⎧= ⎨⎩ nÕu vµ ng−îc l¹i 11 Hàm đặc trưng là hàm kiểm tra sự xuất hiện đồng thời của mệnh đề thông tin ngữ cảnh và lớp được dự đoán. Thống kê vừa nêu trong ví dụ ở phần trước là một thông tin quan trọng: xác suất xuất hiện lên tới 80%. Trong quá trình quan sát tập dữ liệu, ta sẽ nhận được rất nhiều thống kê hữu ích. Vì thế, nếu coi đó là một điều kiện mà mô hình phải tuân theo thì sẽ giúp mô hình dự đoán được lớp của văn bản một cách chính xác hơn. Biểu diễn theo toán học, ta có phương trình như sau: p i p iE f E f=% (5) Phương trình này được gọi là ràng buộc, gọi đầy đủ là phương trình ràng buộc, trong đó: ( ) ( ) ( ) , | ,p i i x y E f p x p y x f x y=∑ % (6) p iE f là kì vọng của f đối với mô hình ( )|p y x Từ (4), (5) và (6) ta có: ( ) ( ) ( ) ( ) ( ) , , , , | ,i i x y x y p x y f x y p x p y x f x y=∑ ∑% % Thêm một ràng buộc có nghĩa là đã loại bỏ bớt đi những mô hình không tuân theo dữ liệu mẫu, điều này được biễu diễn một cách hình học ở Hình 1. Đến đây, chúng ta thấy được ý nghĩa của việc biễu diễn các cứ liệu thống kê được từ dữ liệu mẫu (chính là p iE f% ), và ý nghĩa của việc ràng buộc mô hình của chúng ta tuân theo những sự kiện đó (chính là p i p iE f E f=% ). 2.2.2.3. Nguyên lý entropy cực đại Giả sử quá trình thống kê từ tập dữ liệu huấn luyện sinh ra n đặc trưng if , mỗi đặc trưng này sẽ xác định một ràng buộc. Gọi P là không gian của tất cả các phân phối xác suất, C là tập con của P sẽ được mô tả như sau: { }{ }| 1,2,..,p i p iC p P E f E f i n≡ ∈ = ∈víi% Hình 1 mô tả 4 trường hợp tập C khi có các ràng buộc. P biểu diễn không gian của tất cả các phân phối xác suất. Ở hình (a), không có ràng buộc nào, tất cả các Pp∈ đều thoả mãn. Ở hình (b), C1 cắt bớt đi một phần các mô hình p có thể. Đến hình (c), mô hình của ta chỉ còn nằm trong phần giới hạn bởi C1 và C2: 21 CCp ∩∈ . Trong 12 hình (d), hai ràng buộc C1 và C3 mâu thuẫn ( 1 3C C∩ =∅ ), không có Pp∈ nào thoả mãn cả hai ràng buộc đó. (a) (b) (c) (d) P P P C1 C1 C2 C1 C3 Hình 1. Tập ràng buộc C Nguyên lý entropy cực đại được phát biểu rằng: “Từ tập các phân bố xác suất có thể được là C, sẽ tìm ra được một mô hình *p C∈ thoả mãn điều kiện làm cực đại độ đo entropy H(p): ( )* argmax p C p H p ∈ = Dễ dàng chỉ ra rằng *p luôn luôn xác định và trong bất kì một tập C nào, cũng chỉ có duy nhất một mô hình *p làm cực đại entropy [4]. 2.2.2.4. Dạng tham số Từ nguyên lý entropy cực đại ta có thể phát biểu lại rằng: tư tưởng chủ đạo củ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