TỔNG QUAN
Bài toán gán nhãn từ loại
Gán nhãn từ loại là quá trình xác định chức năng ngữ pháp của từ trong câu, gán từng từ với các đánh dấu từ loại hoặc cấu trúc ngữ pháp Đây là bước quan trọng trước khi thực hiện phân tích cú pháp hoặc xử lý ngôn ngữ phức tạp Một từ có thể đảm nhận nhiều chức năng ngữ pháp khác nhau, như trong câu “con ngựa đá đá con ngựa đá”, từ “đá” lần lượt giữ vai trò danh từ và động từ.
Gán nhãn từ loại là mức thấp nhất của phân tích ngữ nghĩa
Xác định từ loại là yếu tố quan trọng trong phân tích cú pháp văn bản, giúp giải quyết vấn đề đa nghĩa của từ và hỗ trợ các hệ thống rút trích thông tin theo hướng ngữ nghĩa.
John/ NNP saw/ VBD the/ DT saw/NN and/CC decided/VBD to/TO take/VB it/PRP to/IN the/DT table/N
Loan/Np muốn/V đi/V du lịch/V Huế/Np
Trong đó các nhãn NNP, Np, NN, N: danh từ VBD, V: động từ DT: từ hạn đinh IN, TO: giới từ.
Tổng quan về cách tiếp cận giải bài toán
1.2.1 Quá trình gán nhãn từ loại
Gán nhãn từ loại là một quá trình gồm 3 bước xử lý:[2]
Bước đầu tiên trong quá trình tiền xử lý là phân tách xâu kí tự thành chuỗi các từ, với độ phức tạp phụ thuộc vào ngôn ngữ và từng đơn vị từ vựng Đối với tiếng Anh và tiếng Pháp, việc phân tách chủ yếu dựa vào ký tự trắng, mặc dù vẫn có những cụm từ ghép và cụm từ công cụ gây tranh cãi Ngược lại, trong tiếng Việt, dấu trắng không phải là dấu hiệu xác định ranh giới từ vựng do tần suất xuất hiện của từ ghép rất cao.
Bước 2 trong quá trình gán nhãn tiên nghiệm liên quan đến việc xác định tất cả các nhãn từ loại có thể cho mỗi từ Tập nhãn này có thể được thu thập từ cơ sở dữ liệu từ điển hoặc từ kho văn bản đã được gán nhãn bằng tay Đối với những từ mới chưa có trong cơ sở dữ liệu, có thể sử dụng nhãn ngầm định hoặc gán cho chúng tất cả các nhãn có thể Trong các ngôn ngữ có hình thái biến đổi, việc xác định lớp từ loại của từ cũng thường dựa vào hình thái của từ đó.
Bước 3 trong quy trình gán nhãn là quyết định kết quả cuối cùng, nơi loại bỏ những nhầm lẫn Giai đoạn này yêu cầu lựa chọn một nhãn phù hợp nhất cho mỗi từ, dựa trên ngữ cảnh trong tập nhãn tiên nghiệm.
1.2.2 Ngữ liệu Để thực hiện gán nhãn từ loại ta phải có kho ngữ liệu[2], chúng có thể là:
- Từ điển và các văn phạm loại bỏ nhập nhằng
- Kho văn bản đã gán nhãn, có thể kèm theo các quy tắc ngữ pháp xây dựng bằng tay
Kho văn bản chưa gán nhãn chứa các thông tin ngôn ngữ quan trọng, bao gồm tập từ loại và mô tả mối quan hệ giữa từ loại và hậu tố.
- Kho văn bản chƣa gán nhãn, với tập từ loại cũng đƣợc xây dựng tự động nhờ các tính toán thống kê Trong trường hợp này khó có thể
1.2.3 Các tiếp cận giải bài toán
Chúng ta có hai tiếp cận chính cho gán nhãn từ loại tự động:[19]
- Tiếp cận có hướng dẫn
- Tiếp cận không hướng dẫn
Bộ gán nhãn có hướng dẫn sử dụng kho ngữ liệu đã được gán nhãn để phát triển các công cụ hỗ trợ quá trình gán nhãn Các công cụ này bao gồm từ điển bộ gán nhãn, tần suất từ/nhãn, xác suất chuỗi nhãn và tập hợp các luật.
Các mô hình không hướng dẫn không cần kho dữ liệu đã gán nhãn, mà sử dụng các thuật toán phức tạp để tự động tạo ra các nhóm từ Những nhóm từ này được dùng để tính toán thông tin xác suất cho các bộ gán nhãn thống kê hoặc để xây dựng các luật ngữ cảnh cho các hệ thống dựa trên luật.
Sự khác nhau giữa hai tiếp cận thể hiện trong bảng sau:
Không hướng dẫn Có hướng dẫn
- Lựa chọn tập văn đã gán nhãn/tập nhãn
- Rút ra tập nhãn sử dụng dữ liệu huấn luyện chƣa gán nhãn
- Tạo ra các từ điển sử dụng tập văn đã gán nhãn
- Xây dựng từ điển sử dụng dữ liệu huấn luyện chƣa gán nhãn
- Tính toán các công cụ khử nhập nhằng, có thể bao gồm:
+ Các xác suất chuỗi nhãn
- Quy nạp các công cụ khử nhập nhằng, có thể bao gồm:
+ các tần suất từ + Các xác suất chuỗi nhãn
Tuy có nhiều sự khách nhau nhƣng chúng cũng có những điểm giống nhau là:
- Gán nhãn dữ liệu sử dụng thông tin từ điển đã xây dựng
- Khử nhập nhằng bằng các tiếp cận dựa vào thống kê, dựa trên luật hoặc lai các tiếp cận trên
Để làm rõ vấn đề khử nhập nhằng, chúng ta sẽ xem xét các phương pháp tiếp cận khác nhau, bao gồm các phương pháp dựa trên luật, thống kê và sự kết hợp của cả hai.
1.2.5 Gán nhãn dựa trên luật
Bộ gán nhãn dựa trên luật sử dụng các quy tắc được lập trình sẵn để phân biệt và xử lý sự nhầm lẫn trong việc gán nhãn, đồng thời loại bỏ những nhãn không phù hợp.
Gán nhãn dựa trên luật sử dụng từ điển giúp xác định các từ loại cho từ, thông qua việc áp dụng các quy tắc ngữ nghĩa Ví dụ, công thức như det - X - n = X/adj cho thấy cách mà hàng trăm ràng buộc có thể được thiết kế thủ công để tạo ra ý nghĩa chính xác.
Các tiếp cận gán nhãn dựa trên luật sử dụng thông tin ngữ cảnh để xác định nhãn cho các từ chưa biết hoặc nhập nhằng Những luật này, thường được gọi là luật khung ngữ cảnh, giúp phân loại từ dựa trên vị trí của chúng trong câu Chẳng hạn, nếu một từ chưa biết hoặc nhập nhằng X xuất hiện sau một từ hạn định và trước một danh từ, nó sẽ được gán nhãn là tính từ.
Nhiều bộ gán nhãn sử dụng thông tin hình thái học để bổ sung ngữ cảnh trong quy trình khử nhập nhằng Chẳng hạn, nếu một từ nhập nhằng hoặc chưa biết có đuôi “ing” và đứng sau một động từ, thì nhãn của từ đó sẽ được xác định là động từ, theo lý thuyết ngữ pháp.
Một số hệ thống vượt qua việc sử dụng thông tin ngữ cảnh và hình thái bằng cách xây dựng các quy tắc liên quan đến các yếu tố như chữ hoa (được xác định là danh từ riêng) và hệ thống dấu chấm câu Loại thông tin này có thể thay đổi kích thước tùy thuộc vào ngôn ngữ được gán nhãn.
Các bộ gán nhãn dựa trên luật thường yêu cầu huấn luyện có hướng dẫn, nhưng gần đây, việc quy nạp tự động các luật đã thu hút nhiều sự quan tâm Một phương pháp để xây dựng luật tự động là chạy văn bản chưa gán nhãn qua bộ gán nhãn và đánh giá hiệu suất của nó Sau đó, một người sẽ xem xét và chỉnh sửa các từ bị gán nhãn sai Văn bản đã được gán nhãn đúng sẽ được đưa vào bộ gán nhãn để giúp nó học quy tắc sửa lỗi thông qua việc so sánh hai tập dữ liệu.
Bộ gán nhãn thống kê đơn giản nhất giải quyết sự nhập nhằng của các từ bằng cách dựa vào xác suất xuất hiện của một từ với nhãn đặc biệt Cụ thể, nhãn thường gặp nhất trong tập huấn luyện sẽ được gán cho một thể hiện không rõ ràng của từ đó Tuy nhiên, phương pháp này có nhược điểm, vì nó có thể gán nhãn hợp lệ cho một từ nhưng cũng có khả năng tạo ra chuỗi nhãn không hợp lệ.
Một phương pháp thay thế cho tiếp cận tần số từ là tính toán xác suất của chuỗi nhãn đã cho, thường được gọi là tiếp cận N-gram Phương pháp này xác định nhãn tốt nhất cho một từ dựa trên xác suất xuất hiện của nó với N nhãn trước đó Thuật toán Viterbi là thuật toán phổ biến nhất áp dụng tiếp cận N-gram, giúp tối ưu hóa quá trình tìm kiếm bằng cách giảm thiểu độ phức tạp của tìm kiếm theo chiều rộng thông qua việc sử dụng các ước lượng khả năng cực đại của N nhãn tốt nhất.
Bài toán gán nhãn từ loại tiếng Việt
Trong lĩnh vực ngôn ngữ học, việc gán nhãn từ loại cho tiếng Anh đã đạt được nhiều thành tựu, trong khi tiếng Việt cũng đã có nhiều nghiên cứu và phương pháp để giải quyết vấn đề này Tuy nhiên, tiếng Việt vẫn gặp nhiều thách thức, đặc biệt là trong việc phân loại từ, do còn nhiều tranh cãi và thiếu một chuẩn mực thống nhất.
Theo khảo sát các nghiên cứu gần đây về gán nhãn từ loại trong tiếng Việt, có hai dạng tập nhãn từ loại phổ biến thường được áp dụng cho các công cụ gán nhãn.
Dạng thứ nhất của tập nhãn từ loại tiếng Việt được xây dựng từ 8 nhãn cơ bản (danh từ, động từ, tính từ, đại từ, phụ từ, kết từ, trợ từ, cảm từ) và phân nhỏ thành các tiểu từ loại nhằm tạo ra một tập nhãn “mịn” hơn Việc phân loại này dựa trên cuốn Ngữ pháp tiếng Việt của Ủy ban khoa học xã hội Việt Nam, xuất bản năm 1983, với việc bổ sung một số nhãn để tránh nhầm lẫn khi một từ có thể mang nhiều nhãn khác nhau Tùy thuộc vào ứng dụng cụ thể, việc xác định tập nhãn từ loại có thể dừng lại ở mức thô hoặc mịn, dựa trên yêu cầu thông tin cú pháp và từ vựng.
Hiện nay, tại Việt Nam, đã có một số tập nhãn từ loại được phát triển, chủ yếu ở mức thô Điển hình là bộ nhãn VnPOStag của Trần Thị Oanh với 14 nhãn, 1 nhãn không xác định và các nhãn ký hiệu đặc biệt khác Ngoài ra, bộ VietTreeBank cũng được xây dựng với 16 nhãn và 1 nhãn cho từ không phân loại được Tập nhãn lớn nhất hiện nay là của nhóm tác giả Nguyễn Thị Minh Huyền, sử dụng cho công cụ VnQtag, bao gồm 48 nhãn và 1 nhãn không xác định.
Dạng thứ hai của tập nhãn tiếng Việt được hình thành thông qua việc xây dựng kho ngữ liệu song ngữ Anh-Việt, trong đó các câu tiếng Việt được gán nhãn từ loại chính xác Quá trình này dựa vào kết quả liên kết từ Anh-Việt và phép chiếu từ loại từ Anh sang tiếng Việt.
Tập nhãn từ loại tiêu biểu được sử dụng trong nghiên cứu “Gán nhãn từ loại tự động cho Tiếng Việt” của nhóm tác giả Đinh Điền được xây dựng dựa trên tập nhãn tiếng Anh, cụ thể là Brown Corpus.
Bài toán gán nhãn từ loại cho tiếng Việt đang thu hút sự quan tâm nghiên cứu, nhưng vẫn còn nhiều thách thức và tiềm năng phát triển Các nghiên cứu hiện tại chủ yếu mang tính cá nhân, thiếu sự đối chiếu và thống nhất về bộ nhãn giữa các nhà ngôn ngữ Hơn nữa, chưa có bộ nhãn đủ lớn để đạt được độ chính xác cao trong việc gán nhãn tiếng Việt Luận văn này sẽ nghiên cứu các phương pháp học máy không có hướng dẫn đã thành công ở các ngôn ngữ khác nhằm giải quyết vấn đề xác định từ loại trong gán nhãn tiếng Việt Chương này sẽ tổng quan về gán nhãn từ loại và hiện trạng khó khăn của bài toán này, sau đó sẽ tiếp tục với cơ sở toán học để áp dụng phương pháp học máy không có hướng dẫn.
CƠ SỞ TOÁN HỌC
Định lý Bayes
Định lý Bayes cho phép tính xác suất xảy ra của một sự kiện ngẫu nhiên
Xác suất có điều kiện, ký hiệu là P(A|B), thể hiện xác suất xảy ra của sự kiện A khi biết rằng sự kiện B đã xảy ra Nó được gọi là xác suất hậu nghiệm vì giá trị của nó phụ thuộc vào thông tin đã cho từ sự kiện B.
Theo định lí Bayes, xác suất xảy ra A khi biết B sẽ phụ thuộc vào 3 yếu tố:
Xác suất xảy ra A của riêng nó, không quan tâm đến B Kí hiệu là
Xác suất P(A) là xác suất của sự kiện A, được gọi là xác suất biên duyên hay xác suất tiên nghiệm Khái niệm này được hiểu là "tiên nghiệm" vì nó không dựa vào bất kỳ thông tin nào liên quan đến sự kiện B.
Xác suất xảy ra B của riêng nó, không quan tâm đến A Kí hiệu là
P(B) được đọc là "xác suất của B" và được biết đến như là hằng số chuẩn hóa, vì nó luôn giữ giá trị không thay đổi, không phụ thuộc vào sự kiện A mà chúng ta đang quan tâm.
Xác suất xảy ra B khi biết A xảy ra Kí hiệu là P(B|A) và đọc là
"xác suất của B nếu có A" Đại lƣợng này gọi là khả năng
Xác suất xảy ra B khi biết A đã xảy ra được gọi là likelihood Cần phân biệt rõ giữa khả năng xảy ra A khi biết B và xác suất xảy ra A khi biết B Khi đã biết ba đại lượng này, xác suất của A khi biết B được tính theo công thức: likelihood nhân với prior và chia cho normalizing constant.
Thuật toán cực đại hóa kỳ vọng (EM)
Thuật toán EM (Expectation Maximization) là một phương pháp được sử dụng để ước lượng các tham số tối đa trong các mô hình xác suất, đặc biệt là những mô hình phụ thuộc vào các biến ẩn chưa được quan sát Thuật toán này được coi là một kỹ thuật dựa trên mô hình, giúp cải thiện độ chính xác của các dự đoán trong các tình huống có dữ liệu thiếu.
Sau khi khởi tạo, thuật toán sẽ trải qua hai bước xử lý chính: đầu tiên là đánh giá dữ liệu chưa được gán nhãn (bước E), tiếp theo là đánh giá các tham số của mô hình và khả năng lớn nhất có thể xảy ra (bước M).
Bước E:Tính toán các giá trị dự kiến của các biến chưa biết dựa trên các ƣớc lƣợng tham số hiện thời
Bước M: Tính toán lại các giá trị tham số nhằm ước lượng khả năng cực đại cho các biến chưa biết đã được xác định trong bước E.
Lặp lại bước E và bước M cho đến khi đạt được kết quả.
Mô hình Markov ẩn
Mô hình Markov ẩn (Hidden Markov Model - HMM) là một phương pháp thống kê, trong đó hệ thống được coi là một quá trình Markov với các tham số chưa biết Nhiệm vụ chính của HMM là xác định các tham số ẩn từ các quan sát có được Các tham số này sau khi được rút ra có thể được sử dụng cho các phân tích tiếp theo, chẳng hạn như trong các ứng dụng nhận dạng mẫu.
Trong mô hình Markov điển hình, trạng thái được quan sát trực tiếp, với xác suất chuyển tiếp trạng thái là các tham số chính Ngược lại, trong mô hình Markov ẩn (HMM), mỗi trạng thái có xác suất phân bổ cho các biểu hiện đầu ra khác nhau, dẫn đến việc dãy biểu hiện không thể trực tiếp chỉ ra dãy trạng thái tương ứng.
Hình 2.3 Minh họa hoạt động của mô hình Markov ẩn
Trong mô hình Markov, x_i đại diện cho một trạng thái, trong khi a_ij là xác suất để trạng thái x_j xuất hiện sau trạng thái x_i, ký hiệu là p(x_j | x_i) Bên cạnh đó, b_i(o_j) thể hiện xác suất quan sát được o_j tại trạng thái t_i, được ký hiệu là p(o_j | i) Cuối cùng, o_i là dữ liệu quan sát được trong mô hình.
2.3.1 Ba bài toán cơ bản của HMM
Để tính xác suất của một dãy đầu ra cụ thể, chúng ta cần cung cấp cho mô hình các tham số và áp dụng thuật toán tiến-lùi Cụ thể, với chuỗi quan sát O = {o1, o2, , oT} và mô hình λ = {A, B}, mục tiêu là tính xác suất có điều kiện P(O|λ) cho chuỗi quan sát này.
Xác suất P(O/λ) =? Để tính đƣợc xác suất này ta sử dụng thuật toán tiến hoặc thuật toán lùi
Xác suất tiến α t (i): Xác suất ở trạng thái s i , cho trước sự quan sát một phần o 1 ,…,o t
Xác suất lùi β t (j): Xác suất ở trạng thái s i , cho trước sự quan sát một phần ot+1,…,oT
Cung cấp cho mô hình các tham số, mục tiêu là tìm dãy trạng thái ẩn Q={q 1 , q 2 , ,q T } có xác suất điều kiện P(O|λ) cực đại, dựa trên chuỗi quan sát O={o 1 ,o 2 , ,o T } và mô hình λ = {A, B}.
Để giải quyết bài toán này ta sử dụng thuật toán viterbi:
Để tối ưu hóa mô hình, cần cung cấp dãy đầu ra và xác định tập hợp chuyển tiếp trạng thái cùng với các xác suất đầu ra Cụ thể, với chuỗi quan sát O = {o1, o2, , oT} và mô hình λ = {A, B}, mục tiêu là đánh giá lại các thông số của mô hình nhằm tối đa hóa xác suất có điều kiện P(O|λ), tức là tìm λ' sao cho argmax (|λ).
Để giải quyết bài toán này chúng ta sử dụng thuật toán forward- backward hoặc Baum-Welch
Thuật toán tiến-lùi (forward-backward) là một biến thể đặc biệt của thuật toán Expectation-Maximization (EM) Thuật toán này cho phép ước lượng khả năng cực đại và ước lượng mode hậu nghiệm cho các tham số, bao gồm xác suất đầu ra và xác suất chuyển tiếp của mô hình Markov ẩn (HMM), chỉ dựa trên dữ liệu đầu ra đã được cung cấp trong quá trình huấn luyện Ý tưởng chính của thuật toán tiến-lùi là tận dụng thông tin từ cả hai phía của chuỗi dữ liệu để cải thiện độ chính xác của các ước lượng.
1 Bắt đầu với 1 mô hình λ bất kỳ, tính toán P(O huấn luyện/ λ)
2 Đoán ra các chuyển tiếp trạng thái và đầu ra đƣợc sử dụng nhiều nhất trong tính toán P(O/λ)
3 Tăng xác suất của chúng, mà sẽ mang lại 1 mô hình mới với 1 xác suất P(O/λ) cao hơn
4 Lặp lại cho đến khi 1 giá trị cực đại đạt đƣợc
Ba tham số cần đƣợc ƣớc lƣợng lại:
- Phân phối trạng thái ban đầu: i
Xác suất đầu ra được biểu thị bằng b i (o t ), trong đó Ƣớc lƣợng xác suất chuyển tiếp được định nghĩa là t (i, j) = P(q t = s i , q t + 1 = s j | O, ) Đây là xác suất chuyển tiếp từ trạng thái i sang trạng thái j tại thời điểm t, dựa trên mô hình hiện tại và các tham số đã cho.
Bằng trực quan ta có công thức ƣớc lƣợng lại xác suất chuyển tiếp là:
Số dự kiến chuyển tiếp từ trạng thái s i sang s j chia cho số dự kiến chuyển tiếp từ trạng thái s i trong O
Định nghĩa: là xác suất chuyển tiếp từ trạng thái s i trong O
Ta có thể tính đƣợc:
Ƣớc lƣợng xác suất trạng thái ban đầu:
- Phân phối trạng thái ban đầu i là xác suất mà si là một trạng thái bắt đầu
- Ta có thể ƣớc lƣợng lại một cách dễ dàng: ˆ i 1 ( i ) Ƣớc lƣợng xác suất đầu ra
Xác suất đầu ra đƣợc ƣớc lƣợng lại nhƣ sau:
) ˆ ( k b i Số lần dự kiến trong trạng thái s i và ký tự quan sát V k / số lần dự kiến tại trạng thái si
Trong đó δ(o t ,v k ) = 1 nếu o t = v k và = 0 nễu ngƣợc lại
Mô hình đã đƣợc cập nhật
Xuất phát từ ( A , B , ) Chúng ta tạo đƣợc mô hình ' ( A ˆ , B ˆ , ˆ )theo các luật cập nhật sau: j a ˆ i ,
Mô hình n-gram là một phương pháp dự đoán từ tiếp theo dựa trên n-1 từ trước đó, tính toán xác suất của từ tiếp theo bằng cách xem xét số lượng từ có liên quan chặt chẽ với nhau Đây là một mô hình Markov bậc n-1, giúp phân tích và xử lý ngôn ngữ tự nhiên hiệu quả.
Mô hình trigram là mô hình Markov bậc 2
Chuối nhãn thích hợp nhất t 1 , t N đƣợc chọn để cực đại công thức trên t 0 , t -1 , và t n+1 là các dấu bắt đầu và kết thúc chuỗi
Xác suất đƣợc ƣớc lƣợng từ việc đếm tần suất quan hệ (khả năng cực đại), ví dụ:
Phương pháp ước lượng khả năng cực đại cho nhiều xác suất bằng 0 trong các kết quả trigrams yêu cầu sử dụng thuật toán làm mịn bằng phương pháp nội suy để tránh tình trạng này.
Các hệ số cũng đƣợc ƣớc lƣợng từ dữ liệu huấn luyện.
Phân cụm
Phân cụm (clustering) là quá trình chia các đối tượng thành các nhóm, trong đó các đối tượng trong cùng một nhóm có độ tương tự cao hơn so với các nhóm khác Độ tương tự này được đánh giá thông qua các chỉ số khoảng cách Phân cụm là một trong những bài toán quan trọng trong phân tích dữ liệu thống kê, thường được áp dụng trong các lĩnh vực như học máy và khai phá dữ liệu, bao gồm nhận dạng mẫu và phân tích ảnh.
Phân cụm là một công cụ độc lập để xem xét phân bố dữ liệu, và làm bước tiền xử lí cho các thuật toán khác
2.4.2 Các yêu cầu của phân cụm
- Có thể thay đổi kích thước cụm
- Khả năng làm việc với các loại thuộc tính khác nhau
- Khám phá đƣợc các cụm có hình dạng bất kì
- Khả năng làm việc với dữ liệu có chứa nhiễu
- Không phụ thuộc vào thứ tự các bản ghi nhập vào
- Khả năng làm việc với dữ liệu nhiều chiều
- Có thể diễn giải và khả dụng
2.4.3 Các phương pháp phân cụm
Có nhiều phương pháp phân cụm khác nhau, và việc lựa chọn phương pháp phù hợp phụ thuộc vào kiểu dữ liệu, mục tiêu và ứng dụng cụ thể Nhìn chung, các phương pháp này có thể được chia thành nhiều loại khác nhau.
Cho một cơ sở dữ liệu D chứa n đối tƣợng, tạo phân hoạch thành tập có k cụm sao cho:
- Mỗi cụm chứa ít nhất một đối tƣợng
- Mỗi đối tƣợng thuộc về một cụm duy nhất
- Cho trị k, tìm phân hoạch có k cụm sao cho tối ƣu hoá tiêu chuẩn phân hoạch đƣợc chọn
Các phương pháp phân hoạch điển hình được biết đến là k-means và k- medoids
Một biến thể của K-means cho phép sự chồng lặp của các phân cụm là C-means mờ (FCM: Fuzzy C-means) Khác với các quan hệ thành viên nhị phân, FCM cho phép các cấp độ thành viên khác nhau giữa các đối tượng và phân cụm Krishnapuram đã phát triển phiên bản FCM sửa đổi được gọi là Fuzzy C-Medoids (FCMdd), trong đó các ý nghĩa được thay thế bằng ngữ cảnh Thuật toán này có tốc độ nhanh hơn với độ phức tạp O(n²), mang lại hiệu suất hoạt động vượt trội so với FCM.
Phân cấp là phương pháp tổ chức dữ liệu theo cụm mà không yêu cầu số lượng cụm ban đầu, khác với phân hoạch Phương pháp này sử dụng ma trận khoảng cách để xác định các cụm, đồng thời có thể áp dụng điều kiện dừng như số lượng cụm để kết thúc quá trình phân tích.
Phân cấp cụm thường được biểu diễn dưới dạng cây các cụm, trong đó:
- Các lá của cây biểu diễn từng đối tƣợng
- Các nút trong biểu diễn các cụm
Có hai phương pháp tạo cây phân cấp là từ dưới lên và từ trên xuống
Phương pháp từ dưới lên (bottom up) bắt đầu bằng việc đặt mỗi đối tượng vào một cụm riêng biệt Sau đó, quá trình diễn ra bằng cách lần lượt kết hợp hai cụm tương đồng nhất cho đến khi chỉ còn lại một cụm duy nhất hoặc đạt được một điều kiện nhất định nào đó.
Phương pháp từ trên xuống (top-down) bắt đầu bằng cách xác định cụm lớn nhất chứa tất cả các đối tượng Tiếp theo, nó chia cụm có độ phân biệt cao nhất thành các cụm nhỏ hơn và tiếp tục quá trình này cho đến khi đạt được số lượng cụm mong muốn hoặc thỏa mãn điều kiện dừng.
2.4.3.3 Phương pháp dựa trên mật độ
Gom cụm dựa trên sự liên thông địa phương và hàm mật độ, cho phép nhóm các điểm có mật độ cao vào cùng một cụm Phương pháp này đặc trưng bởi khả năng xác định các khu vực có sự phân bố dày đặc, giúp phân loại dữ liệu một cách hiệu quả.
- Phát hiện ra các cụm có hình dạng bất kì
2.4.3.4 Phương pháp dựa trên mô hình
Một mô hình giả thuyết được xây dựng cho từng cụm, sau đó điều chỉnh các thông số để đảm bảo mô hình phù hợp nhất với cụm dữ liệu hoặc đối tượng tương ứng.
Một yếu tố quan trọng trong kỹ thuật phân cụm là lựa chọn độ đo khoảng cách để xác định sự tương đồng giữa các phần tử Độ đo này sẽ ảnh hưởng đến hình thái của các cụm, vì một phần tử có thể gần với một phần tử khác theo một độ đo nhưng lại xa hơn theo một độ đo khác.
Trong không gian 2 chiều, khoảng cách giữa điểm (x=1,y=0) và điểm gốc (x=0,y=0) luôn là 1 theo tiêu chuẩn thông thường Ngược lại, khoảng cách giữa điểm (x=1,y=1) và điểm gốc (x=0,y=0) có thể lên tới 2.
√2, hoặc 1 nếu bạn tuần tự theo tiêu chuẩn 1, tiêu chuẩn 2 hoặc khoảng cách tiêu chuẩn vô cự
Dữ liệu thống kê được tổ chức thành ma trận np, với n đại diện cho số lượng bộ dữ liệu và p là số lượng thuộc tính Mỗi phần tử xij trong ma trận thể hiện giá trị đo lường của thuộc tính j trong bộ dữ liệu i.
Khoảng cách các bộ dữ liệu được lưu trong ma trận nn trong đó dij đo khoảng cách giữa bộ dữ liệu i và bộ dữ liệu j
Tùy theo loại giá trị thuộc tính dữ liệu (số, nhị phân, tên), người ta định nghĩa một độ đo khoảng cách phù hợp [31].
Phân tích giá trị kỳ dị
Phân tích giá trị kì dị (Singular value decomposition - SVD) có thể đƣợc nhìn vào từ ba quan điểm sau [34]:
Đầu tiên, chúng ta có thể xem đây là một phương pháp giúp chuyển đổi các biến có mối tương quan thành một tập hợp các biến không tương quan, từ đó thể hiện rõ hơn mối quan hệ khác nhau giữa các phần tử dữ liệu ban đầu.
SVD là một phương pháp hiệu quả để xác định và sắp xếp các chiều véc tơ, giúp phát hiện những điểm khác biệt lớn nhất trong dữ liệu Góc nhìn thứ ba về SVD nhấn mạnh tầm quan trọng của việc phân tích và tổ chức thông tin một cách tối ưu.
SVD là một phương pháp hiệu quả để giảm số chiều dữ liệu, cho phép xác định sự chênh lệch lớn nhất và tìm ra xấp xỉ tốt nhất cho các điểm dữ liệu ban đầu bằng cách sử dụng kích thước nhỏ hơn.
Phương pháp SVD dựa trên định lý trong đại số tuyến tính cho rằng bất kỳ ma trận A có kích thước MxN với M >= N đều có thể được phân tích thành tích của ba ma trận: ma trận U trực giao theo cột kích thước MxN, ma trận chéo W kích thước NxN với các giá trị không âm trên đường chéo, và ma trận chuyển vị của một ma trận trực giao V kích thước NxN.
Ma trận U và ma trận V được coi là trực giao khi các cột của chúng vuông góc với nhau, với điều kiện rằng δ kn = 1 nếu k = n và δ kn = 0 nếu k khác n Điều này có thể được biểu diễn dưới dạng ma trận.
Vì V là ma trận vuông nên V đồng thời là ma trận trực giao theo hàng: V.V T =1
Nếu ký hiệu u i và v i tương ứng là các cột của U và V, thì :
Các giá trị kỳ dị của ma trận A, ký hiệu là w_i, được sắp xếp theo thứ tự giảm dần với điều kiện w_1 >= w_2 >= >= w_n >= 0.
Chương này đã trình bày kiến thức về xác suất, các mô hình học, thuật toán và phương pháp sử dụng trong luận văn Tiếp theo, chương sau sẽ giới thiệu ứng dụng của những kiến thức này trong các tiếp cận học máy không có hướng dẫn, nhằm giải quyết bài toán gán nhãn từ loại tiếng Việt.
MỘT SỐ PHƯƠNG PHÁP TIẾP CẬN KHÔNG CÓ HƯỚNG DẪN CHO GÁN NHÃN TỪ LOẠI
Gán nhãn sử dụng kỹ thuật Cực đại hóa kỳ vọng
Bài toán gán nhãn từ loại được thực hiện thông qua mô hình Markov ẩn (HMM), trong đó các nhãn từ loại được xem như các trạng thái ẩn, còn các từ trong văn bản là đầu ra, hay trạng thái quan sát được.
Trong mô hình Markov, các thành phần chính bao gồm nhãn từ loại x_i, xác suất chuyển tiếp a_ij = p(x_j | x_i), thể hiện xác suất xuất hiện của nhãn x_j sau nhãn x_i Bên cạnh đó, b_i(o_j) = p(o_j | i) là xác suất quan sát từ y_j tại trạng thái nhãn i, phản ánh các xác suất đầu ra Cuối cùng, o_i đại diện cho dữ liệu quan sát được, cụ thể là các từ trong mô hình.
Giải quyết bài toán gán nhãn từ loại bằng mô hình HMM yêu cầu xác định chuỗi nhãn cho các từ trong văn bản, với mục tiêu tối đa hóa xác suất của chuỗi nhãn tương ứng với chuỗi từ Để thực hiện điều này, ta cần giải quyết bài toán thứ hai của mô hình HMM.
Chiến lược EM sử dụng thuật toán tiến lùi dựa trên sự ước lượng khả năng cực đại để đánh giá các tham số cho mô hình, bao gồm xác suất chuyển tiếp và xác suất đầu ra Phương pháp này đặc trưng bởi việc sử dụng kho từ vựng hoặc từ điển đã gán nhãn, cho phép dễ dàng trích xuất từ một từ điển chuẩn Nghiên cứu hiệu quả của EM trên độ chính xác gán nhãn được thực hiện khi dữ liệu huấn luyện bao gồm cả văn bản gán nhãn và chưa gán nhãn HMM trigram được xác định thông qua hai phương pháp huấn luyện: có hướng dẫn, với việc đếm tần số quan hệ nội suy, và không có hướng dẫn, sử dụng khả năng cực đại Kho từ vựng đầy đủ, bao gồm các từ từ cả tập văn huấn luyện và thử nghiệm, được dùng để ước lượng xác suất đầu ra, dẫn đến việc các cặp nhãn-từ không có trong kho từ vựng sẽ có xác suất 0.
3.1.1 Huấn luyện mô hình Trigram
Chúng ta xem xét hai loại huấn luyện khác nhau:
- Huấn luyện tần số quan hệ (Relative Frequency RF)
- Huấn luyện khả năng cực đại (Maximum Likelihood ML) bằng thuật toán tiến-lùi
3.1.1.1 Huấn luyện tần số quan hệ
Nếu có sẵn một lượng văn bản đã được gán nhãn, chúng ta có thể tính toán tần suất xuất hiện của một từ w với nhãn t, cụ thể là số lần N(w,t) mà từ đó xuất hiện.
Trong văn bản này, chuỗi N(t 1, t 2, t 3) với các tham số t 1, t 2 và t 3 xuất hiện Chúng ta có thể ước lượng xác suất h và k thông qua việc tính toán tần suất quan hệ của các sự kiện tương ứng trên dữ liệu này.
Những ước lượng này gán xác suất 0 cho bất kỳ chuỗi nhãn nào không xuất hiện trong dữ liệu huấn luyện, dẫn đến việc các liên kết chứa chuỗi này cũng nhận xác suất 0, làm cho mô hình trở nên vô ích Để khắc phục vấn đề này, chúng ta áp dụng nội suy với các phân phối đều, từ đó xác định mô hình nội suy.
W T : là số từ chứa nhãn T
Hệ số nội suy λ đƣợc tính toán nhờ thủ tục nội suy, cũng gọi là “Làm mịn”
Làm mịn đƣợc thực hiện nhƣ sau:
Một số văn bản đã được gán nhãn trong tập dữ liệu huấn luyện không được sử dụng khi tính toán tần số quan hệ, và những dữ liệu này được gọi là dữ liệu tách riêng.
- Hệ số λ đƣợc chọn để cực đại hoá xác suất đầu ra của dữ liệu tách riêng bằng mô hình đã nội suy
Sự cực đại hóa có thể được thực hiện thông qua thuật toán FB chuẩn, trong đó λ và 1 – λ được coi là các xác suất chuyển trong mô hình Markov.
3.1.1.2 Huấn luyện khả năng cực đại (ML)
Sử dụng một mô hình trigram M, có thể tính toán xác suất của bất kỳ chuỗi các từ W theo mô hình này: p ( W ) p ( W , T )
Tổng đƣợc lấy từ tất cả các liên kết khả dụng, trong khi huấn luyện ML nhằm tìm ra mô hình M tối đa hóa xác suất của văn bản huấn luyện.
Trong đó, tích đƣợc lấy trên tất cả các câu W trong văn bản huấn luyện Đây là vấn đề của huấn luyện một mô hình Markov ẩn
3.1.2 Kết quả thử nghiệm với tiếng Anh
[14] sử dụng dữ liệu Penn treebank gồm có 42186 đã đƣợc gán nhãn một cách thủ công (khoảng 1 triệu từ)
Sử dụng 159 các nhãn khác nhau để gán nhãn cho Penn treebank
Xây dựng từ điển bằng cách đƣa tất cả các từ xuất hiện trong văn bản cùng với tất cả các nhãn đƣợc gán ở trong văn bản
Chia dữ liệu thành hai phần:
- Một tập gồm 40186 câu đã gán nhãn, dữ liệu huấn luyện, đƣợc sử dụng để xây dựng mô hình
- Một tập gồm 2000 câu đã gán nhãn, dữ liệu huấn luyện, đƣợc sử dụng để thử nghiệm chất lƣợng các mô hình
3.1.3 Các thí nghiệm cơ bản
Thí nghiệm sử dụng thuật toán gán nhãn Viterbi và huấn luyện RF
Trong thí nghiệm, chúng tôi đã trích xuất N câu từ dữ liệu huấn luyện để tính toán tần số quan hệ và xây dựng một mô hình đã được làm mịn Mô hình này được áp dụng để gán nhãn cho 2000 câu thử nghiệm Kết quả cho thấy khi tăng kích cỡ dữ liệu huấn luyện, hệ số nội suy cũng tăng theo, dẫn đến việc cải thiện chất lượng gán nhãn.
Thí nghiệm sử dụng thuật toán gán nhãn Viterbi và huấn luyện ML
Trong huấn luyện ML, người ta tận dụng tất cả các dữ liệu có sẵn nhưng chỉ sử dụng chuỗi các từ, không dùng đến các nhãn liên quan
Mô hình được xây dựng dựa trên phân phối đều, với các ràng buộc từ giá trị k(w/t) bằng 0 khi nhãn t không thể gán cho từ w Kết quả cho thấy việc huấn luyện máy học (ML) cải thiện độ phức tạp của mô hình và giảm tỷ lệ lỗi gán nhãn, tuy nhiên tỷ lệ lỗi này vẫn cao hơn so với huấn luyện rừng ngẫu nhiên (RF) trên 100 câu đã gán nhãn Mô hình ban đầu được giữ lại và huấn luyện ML được áp dụng để gán nhãn chuỗi từ Kết quả chỉ ra rằng với ít dữ liệu đã gán nhãn, mô hình RF không đạt hiệu quả tốt, nhưng huấn luyện ML có thể cải thiện kết quả Ngược lại, khi số lượng dữ liệu đã gán nhãn tăng lên, mô hình RF cho kết quả chính xác hơn, và huấn luyện ML có thể làm giảm độ chính xác gán nhãn khi sử dụng hơn 5000 câu đã gán nhãn.
Gán nhãn từ loại bằng kỹ thuật phân cụm
Trong phương pháp này, các thuộc tính phân phối và từ tương tự trong ngữ cảnh giống nhau được sử dụng để tính toán véc tơ ngữ cảnh của từng từ, từ đó gom cụm các từ thành các nhóm có thể gán nhãn từ loại Kỹ thuật phân cụm này cho phép xây dựng nhãn từ loại trên dữ liệu chưa gán nhãn, tạo nên một đặc trưng nổi bật của phương pháp gán nhãn từ loại phân phối Việc gom cụm từ và xây dựng các tên lớp trên các cụm tổng hợp thay thế cho các mô hình Markov và các thuật toán ước lượng tham số ẩn của mô hình.
Các đặc điểm quan trọng của véc tơ ngữ cảnh bao gồm định nghĩa, kích thước (số chiều), thước đo tính toán độ tương tự để tạo cụm, và cách xây dựng nhãn cùng lớp từ vào các nhóm Sự phân loại từ hiếm và nhập nhằng, cùng với dữ liệu thưa, là những trở ngại chính cho chiến lược này.
Giả thuyết cho thuật toán cho rằng hành vi cú pháp của một từ được thể hiện qua các từ đồng xuất hiện, phản ánh rõ ràng trong ngữ cảnh bên trái và bên phải của từ đó.
Láng giềng trái ↔ TỪ ↔ Láng giềng phải
Véc tơ ngữ cảnh trái Véc tơ ngữ cảnh phải
Các véc tơ ngữ cảnh chứa số lần xuất hiện của mỗi từ trong 250 từ xuất hiện nhiều nhất trong kho văn bản
Để đo độ tương tự giữa hai từ dựa trên hành vi cú pháp của chúng, người ta sử dụng phương pháp đếm các láng giềng và kết hợp vào một véc tơ Hệ số cosin được áp dụng để đo sự tương tự: giá trị cosin gần 1 cho thấy hai từ có nhiều láng giềng chung, trong khi giá trị gần 0 chỉ ra rằng chúng không có láng giềng nào chung.
Việc đo sự tương tự phân phối của các láng giềng chung không hiệu quả khi dữ liệu huấn luyện thưa thớt Khi xem xét hai tính từ không thường xuyên xảy ra để sửa đổi các danh từ khác nhau trong tập văn, sự tương tự bên phải của chúng theo độ đo cosin là 0 Ngay cả với các từ tần suất cao như “a” và “an”, hai mạo từ này cũng không chia sẻ bất kỳ láng giềng bên phải nào, dẫn đến sự tương tự theo độ đo cosin cũng bằng 0 Kết quả này cho thấy sự sai lệch trong việc đo lường.
Giải pháp cho vấn đề này là áp dụng phương pháp phân tích giá trị kỳ dị (SVD) cho ma trận C, trong đó các véc tơ ngữ cảnh của từ được biểu diễn dưới dạng các hàng của ma trận C.
Bảng 3.2.1 Thể hiện các láng giềng gần nhất của 2 từ “onto” và
4 thí nghiệm suy luận nhãn khác nhau là:
- Suy luận dựa trên loại từ
- Suy luận dựa trên loại từ và ngữ cảnh
- Suy luận dựa trên loại từ và ngữ cảnh, hạn chế các ngữ cảnh tự nhiên
- Suy luận dựa trên loại từ và ngữ cảnh, sử dụng các véc tơ ngữ cảnh trái và phải tổng quát hoá
3.2.2 Suy luận dựa trên từ loại
Véc tơ ngữ cảnh của một từ thể hiện sự phân bố của các từ láng giềng bên trái và bên phải, với sự kết hợp của hai véc tơ này có thể đại diện cho phân phối của từ đó Trong nghiên cứu, 47,025 từ từ tập văn Brown đã được sử dụng để cấu tạo các véc tơ ghép nối Các véc tơ ngữ cảnh có chiều số 250 được áp dụng SVD với ma trận có kích thước tương ứng.
Họ thu được 50 véc tơ giảm chiều từ 47025 véc tơ ban đầu bằng phương pháp SVD và phân lớp chúng thành 200 lớp thông qua thuật toán phân cụm Sự phân loại này là nền tảng cho việc gán nhãn từ loại dựa trên phân phối, trong đó tất cả sự xuất hiện của một từ được gán vào một lớp Tuy nhiên, vấn đề trở nên phức tạp đối với các từ có tính nhập nhằng.
3.2.3 Suy luận dựa trên loại từ và ngữ cảnh
Vai trò cú pháp của một từ phụ thuộc vào thuộc tính cú pháp của các từ láng giềng và mối quan hệ giữa chúng Do đó, chúng ta sẽ xem xét sự xuất hiện của một từ w thông qua việc ghép nối bốn véc tơ ngữ cảnh.
- Véc tơ ngữ cảnh phải của từ đứng trước
- Véc tơ ngữ cảnh trái của từ w
- Véc tơ ngữ cảnh phải của từ w
- Véc tơ ngữ cảnh trái của từ theo sau
SVD được áp dụng để giải quyết vấn đề thưa thớt và tổng quát trong ngữ nghĩa Bộ ba từ được chọn ngẫu nhiên từ tập văn bản để tạo ra bốn véc tơ ngữ cảnh Thực hiện SVD trên ma trận có kích thước 20,000, sau khi giảm số chiều từ 1,000 xuống còn 50 Cuối cùng, các từ được phân cụm dựa trên các véc tơ đã giảm chiều thành các lớp.
Thủ tục này gặp phải một số hạn chế, bao gồm việc các lỗi từ không có sự phụ thuộc ngữ pháp với các dấu trong câu, điều này trái ngược với sự phụ thuộc mạnh mẽ giữa các từ kề nhau Bên cạnh đó, các ngữ cảnh chứa từ hiếm (xuất hiện ít hơn 10 lần) cũng bị loại trừ, vì ngữ cảnh trái và phải của chúng cung cấp ít thông tin cho việc phân loại cú pháp.
3.2.4 Suy luận dựa trên loại từ và ngữ cảnh, sử dụng các véc tơ ngữ cảnh trái và phải tổng quát hoá
Các véc tơ ngữ cảnh chỉ sử dụng thông tin từ 250 từ phổ biến nhất để phân tích sự tương tác phân phối Việc áp dụng trực giác có thể nâng cao độ chính xác trong việc gán nhãn bằng cách sử dụng thông tin từ nhiều từ hơn Một phương pháp hiệu quả là cho phép véc tơ ngữ cảnh ghi lại các lớp của véc tơ ngữ cảnh trái xuất hiện bên phải một từ Nguyên tắc cơ bản là các từ có ngữ cảnh trái tương tự thường mô tả các từ bên phải của chúng theo cách giống nhau, ví dụ như “seemed” và “would” có ngữ cảnh trái tương tự và chúng mô tả các ngữ cảnh phải của “he”.
"Firefighter" có tiềm năng thể hiện một hình thái động từ biến cách Nó không chỉ bao gồm các hạng tử riêng biệt mà còn có vai trò quan trọng trong ngữ cảnh, như với từ "seemed".
"Would" và "likes" có thể được mô tả thông qua một hạng tử tổng quát hóa, giúp hình thái động từ biến cách xuất hiện thường xuyên bên phải.
Vấn đề này đƣợc giải quyết bằng việc sử dụng SVD cho ma trận cỡ
Véc tơ ngữ cảnh trái và phân cụm véc tơ ngữ cảnh kết quả được chia thành 250 lớp, với véc tơ ngữ cảnh v tổng quát hoá cho từ w bằng cách đếm tần suất xuất hiện của các từ trong 250 lớp bên phải w Hạng tử w i đại diện cho số lần một từ từ lớp i xuất hiện bên phải w trong tập văn, trái ngược với số lần mà một từ với hạng tần số i xuất hiện bên phải w Véc tơ ngữ cảnh trái được tổng quát hoá thông qua một quy trình tương tự sử dụng véc tơ ngữ cảnh phải dựa trên từ, trong khi thông tin về véc tơ ngữ cảnh trái và phải được giữ riêng biệt trong quá trình tính toán.
Đề xuất phương pháp không hướng dẫn cho bài toán gán nhãn từ loại tiếng Việt
Gán nhãn từ loại bằng phương pháp có hướng dẫn đã được nghiên cứu nhiều, nhưng thường cần một kho ngữ liệu đã được gán nhãn thủ công Tuy nhiên, sự thiếu thống nhất trong các nhãn giữa các nhà ngôn ngữ khiến việc xây dựng kho ngữ liệu chuẩn trở nên khó khăn, tốn thời gian, nhân lực và chi phí Do đó, luận văn này đề xuất việc sử dụng tập nhãn tiếng Việt để tiết kiệm thời gian và chi phí gán nhãn thủ công thông qua phương pháp không hướng dẫn.
Gán nhãn từ loại bằng phương pháp không hướng dẫn có năm tiếp cận, trong đó tiếp cận sử dụng kỹ thuật phân cụm là nổi bật nhất Phương pháp này cho phép xây dựng các loại từ mà không cần văn bản đã gán nhãn, tiết kiệm thời gian và giải quyết vấn đề phân loại từ trong tiếng Việt chưa thống nhất Tuy nhiên, nó cũng gặp khó khăn với dữ liệu thưa và từ nhập nhằng, dẫn đến độ chính xác chưa cao Gán nhãn từ loại dựa vào các thuộc tính chung của văn bản mà không cần kiến thức tiên nghiệm về ngữ pháp, làm nổi bật sự nhập nhằng từ loại phổ biến là một thách thức lớn.
Nghiên cứu phương pháp gán nhãn từ loại đã cho thấy rằng việc sử dụng véc tơ ngữ cảnh và từ loại với giới hạn ngữ cảnh mang lại độ chính xác cao nhất Do đó, trong đề xuất này, chúng tôi sẽ tính toán độ tương tự của hai từ dựa trên véc tơ ngữ cảnh tự nhiên, vì không có phụ thuộc ngữ pháp rõ ràng giữa các từ và dấu câu.
Bước 1: loại bỏ các dấu trong câu cùng với các từ có tần suất xuất hiện thấp (dưới 10 lần)
Bước 2: tính véc tơ ngữ cảnh trải và phải của một từ như sau:
Tính véc tơ ngữ cảnh của một từ chứa số lần suất hiện của mỗi từ trong
250 từ xuất hiện nhiều nhất trong kho văn bản
Ví dụ: a1, a2, ,a250 là 250 từ xuất hiện nhiều nhất trong kho văn bản Xét từ w: a1: xuất hiện n1 lần bên phải a2: xuất hiện n2 lần bên phải
a250: xuất hiện n250 lần bên phải
(n1,n2, n250) là véc tơ ngữ cảnh phải của từ
Véc tơ ngữ cảnh trái tính tương tự
Vì vai trò cú pháp của một từ dựa trên:
- Các thuộc tính cú pháp các láng giềng của từ đó
- Các mối quan hệ cú pháp với các láng giềng này
Sau khi tính toán xong hai véc tơ ngữ cảnh trái và phải của một từ, chúng ta sẽ tiến hành tính véc tơ ngữ cảnh tổng quát của từ w bằng cách kết hợp bốn véc tơ ngữ cảnh đã thu được.
- Véc tơ ngữ cảnh phải của từ đứng trước
- Véc tơ ngữ cảnh trái của từ w
- Véc tơ ngữ cảnh phải của từ w
- Véc tơ ngữ cảnh trái của từ theo sau
Cuối cùng đo độ tương tự của hai từ ta sẽ sự dụng độ đo cosin để tính toán dựa vào các véc tơ ngữ cảnh đƣợc tính ở trên
Bước 3: Sử dụng thuật toán phân cụm để phân thành các nhóm dựa vào các độ đo đƣợc tính ở trên
Vậy thứ tự để thực hiện gán nhãn sẽ nhƣ sau:
1 Tính toán tần số xuất hiện của mỗi từ trong kho ngữ liệu Loại ra các từ có tần suất xuất hiện quá nhiều Tìm ra 250 từ xuất hiện nhiều nhất còn lại
2 Tính toán các véc tơ ngữ cảnh trái và phải của một từ
3 Xây dựng một ma trận ngữ cảnh C nhƣ sau: Mỗi hàng của ma trận gồm véc tơ ngữ cảnh của một từ w đƣợc kết nối từ 4 véc tơ ngữ cảnh (véc tơ ngữ cảnh phải của từ đứng trước, véc tơ ngữ cảnh trái của từ w, véc tơ ngữ cảnh phải của từ w, véc tơ ngữ cảnh trái của từ theo sau)
4 Sử dụng giải pháp SVD để giảm số chiều ma trận C
5 Tính độ đo tương tự của các từ dựa trên ma trận C đã giảm số chiều sử dụng độ đo cosin
6 Phân cụm dựa vào độ đo đã tính ở trên sử dụng thuật toán phân cụm mờ
7 Sau khi thực hiện phân cụm ta đã xây dựng đƣợc tập nhãn Sử dụng tập nhãn này để xây dựng một kho ngữ liệu gán nhãn bằng tay
8 Để thực hiện gán nhãn ta sẽ sử dụng mô hình Markov ẩn, và theo nghiên cứu ở trên gán nhãn sử dụng mô hình Markov đạt độ chính xác cao khi kho ngữ liệu gán nhãn bằng tay nhỏ thì sẽ sử dụng huấn luyện ML để thực hiện
Phần cuối này trình bày chi tiết giải thuật bước 2
Giải thuật tính véc tơ ngữ cảnh trái và phải của một từ sử dụng các tệp văn bản đã được tách từ Đầu vào của quá trình này là các tệp văn bản, trong khi đầu ra là véc tơ ngữ cảnh trái và phải tương ứng với các từ trong những tệp đó.
Bước 1: Lưu lại tất cả các từ xuất hiện trong toàn bộ các tệp văn bản và số lần xuất hiện tương ứng của mỗi từ
Dùng 1 bảng băm(Hashing) để lưu trữ dữ liệu về các từ và số lần xuất hiện (tần suất) tương ứng của mỗi từ trong toàn bộ các tệp văn bản for mỗi tệp trong
Mở tệp và chuyển con trỏ đến dòng đầu tiên Trong khi còn dữ liệu, đọc dòng văn bản tại vị trí con trỏ Đối với mỗi từ trong dòng văn bản, nếu từ đó tồn tại trong bảng băm, tăng giá trị tần suất của từ lên 1 Nếu không, khởi tạo giá trị tần suất của từ là 1 Sau đó, chuyển con trỏ đến dòng tiếp theo cho đến khi hết dữ liệu.
Bước 2 Tìm 250 từ có tần suất xuất hiện cao nhất:
Duyệt toàn bộ bảng băm và đưa dữ liệu vào 1 mảng.Mỗi phần tử của mảng chứa 2 thuộc tính: từ và tần suất xuất hiện của từ
Sắp xếp mảng theo thứ tự giảm dần tần suất xuất hiện của từ và loại bỏ các phần tử có tần suất quá cao Sau đó, lấy 250 phần tử đầu tiên từ mảng đã được xử lý Những từ này chính là 250 từ có tần suất xuất hiện nhiều nhất Cuối cùng, đưa 250 từ này vào một tập hợp gọi là topset.
Bước 3 Xây dựng dữ liệu trung gian Đưa ra thêm 2 đối tượng lưu trữ dữ liệu mới như sau:
- 1 bảng băm chứa tất cả các từ bên trái từ đó và tần suất xuất hiện tương ứng (tạm gọi là bảng băm láng giềng trái)
- 1 bảng băm phải chứa tất cả các từ bên phải từ đó và tần suất xuất hiện tương ứng (tạm gọi là bảng băm láng giềng phải)
Lưu 250 từ và 250 bảng băm láng giềng trái tương ứng vào một bảng băm (tạm gọi là Tâp hợp bảng băm láng giềng trái)
Lưu 250 từ và 250 bảng băm láng giềng phải tương ứng vào một bảng băm (tạm gọi là Tập hợp bảng băm láng giềng phải)
Sau đây là giải thuật xây dựng Tập hợp bảng băm láng giềng trái và Tập hợp bảng băm láng giềng phải
Bước 1: Khởi tạo Tập hợp bảng băm láng giềng trái và Tập hợp bảng băm láng giềng phải
Mỗi tập hợp bảng băm bao gồm 250 khóa từ trong topSet, với dữ liệu tương ứng cho mỗi khóa là một bảng băm trống Chúng ta sẽ cập nhật dữ liệu cho các bảng băm trống này, biến chúng thành bảng băm láng giềng trái và bảng băm láng giềng phải.
Bước 2: Xây dựng Tập hợp bảng băm láng giềng trái và Tập hợp bảng băm láng giềng phải
For mỗi tệp trong
Mở tệp Đưa con trỏ đọc tệp vào dòng đầu tiên Đọc dòng đầu tiên
Tách các từ trong văn bản thành tập hợp từ riêng lẻ, thường được cấu trúc thành mảng để dễ dàng truy cập Nếu từ nằm trong 250 từ có tần suất xuất hiện cao nhất và có láng giềng trái, lấy từ bên trái và cập nhật tần suất xuất hiện trong bảng băm láng giềng trái Tương tự, nếu từ có láng giềng phải, lấy từ bên phải và cập nhật tần suất trong bảng băm láng giềng phải Quá trình này giúp theo dõi và phân tích tần suất xuất hiện của các từ trong văn bản.
Di chuyển con trỏ đọc tệp đến dòng kể tiếp
Bước 4: Tìm véc tơ ngữ cảnh trái của một từ (ngữ cảnh phải làm tương tự)
/*Bây giờ ta đã có 2 đối tƣợng dữ liệu cần thiết tập hợp bảng băm láng giềng trái và Tập hợp bảng băm láng giềng phải
Với mỗi từ bất kỳ, giả sử là word, thuật toán tìm láng giềng trái nhƣ sau (Tương tự đối với láng giềng phải) */
Khởi tạo một vector ngữ cảnh trái với 250 chiều, tất cả các phần tử đều là 0 Đối với mỗi từ (topWord) trong tập hợp topSet, lấy bảng băm láng giềng phải tương ứng Sau đó, xác định tần suất xuất hiện của từ trong bảng băm láng giềng phải Nếu tần suất xuất hiện của từ tồn tại trong bảng băm, gán giá trị tần suất cho phần tử tương ứng trong vector ngữ cảnh trái của từ đó Đối tượng lưu trữ dữ liệu sử dụng bảng băm, có kích thước tỷ lệ thuận với số lượng từ khác nhau trong toàn bộ các tệp văn bản.
Chương trình xử lý tệp tuần tự với kích thước nhỏ, chỉ cần không gian bộ nhớ hạn chế, ngoại trừ đối tượng bảng băm Luận văn đã đề xuất giải pháp cho vấn đề bộ từ loại trong gán nhãn từ loại tiếng Việt Cuối cùng, chúng ta sẽ tổng kết nội dung luận văn và định hướng phát triển tiếp theo.