Xử lý Văn bản và NLP Kinh điển

Xử lý văn bản biến đổi các ký tự thô thành các biểu diễn có cấu trúc mà mô hình có thể tiêu thụ. File này bao gồm tokenisation (từ, dưới từ, BPE, WordPiece), chuẩn hoá văn bản, khoảng cách sửa (edit distance), TF-IDF, mô hình ngôn ngữ n-gram, gán nhãn từ loại (POS tagging), nhận dạng thực thể tên (NER), và phân tích cảm xúc — pipeline NLP kinh điển vẫn là nền tảng cho các hệ thống hiện đại.

• Văn bản thô rất lộn xộn. Trước khi bất kỳ mô hình NLP nào có thể làm việc với ngôn ngữ, văn bản phải được làm sạch, chuẩn hoá và chuyển đổi thành biểu diễn có cấu trúc. File này bao gồm pipeline từ ký tự thô đến các đặc trưng mà mô hình có thể tiêu thụ, cùng với các thuật toán NLP kinh điển thống trị trước thời học sâu.

• Chuẩn hoá văn bản (Text normalisation) biến đổi văn bản thô thành một dạng chuẩn mực. Mục tiêu là giảm thiểu các biến thiên không liên quan để "Hello", "hello", "HELLO" và "héllo" được xử lý phù hợp.

• Chuyển đổi chữ hoa/chữ thường (Case folding) chuyển văn bản thành chữ thường. Điều này gộp "The" và "the" thành một token. Nó hữu ích cho hầu hết các tác vụ, nhưng đôi khi phá hỏng thông tin hữu ích: "US" (nước Mỹ) so với "us" (chúng ta), hoặc "Apple" (công ty) so với "apple" (quả táo).

• Chuẩn hoá Unicode giải quyết thực tế là cùng một ký tự có thể được mã hoá theo nhiều cách. Ký tự "é" có thể là một code point đơn (U+00E9) hoặc một chữ "e" nền cộng với dấu kết hợp (U+0065 + U+0301). Chuẩn hoá NFC gộp chúng thành một code point; NFD tách chúng ra. Nếu không chuẩn hoá, hai chuỗi trông giống hệt nhau có thể không khớp.

• Khoảng cách sửa (Edit distance) đo độ khác nhau giữa hai chuỗi. Khoảng cách Levenshtein đếm số lượng tối thiểu các thao tác chèn, xoá và thay thế ký tự đơn lẻ để biến một chuỗi thành chuỗi kia. "kitten" → "sitting" có khoảng cách sửa là 3 (k→s, e→i, chèn g).

• Khoảng cách sửa được tính bằng quy hoạch động (chúng ta xem lại trong chương thuật toán). Định nghĩa \(D[i][j]\) là khoảng cách giữa \(i\) ký tự đầu của chuỗi \(s\) và \(j\) ký tự đầu của chuỗi \(t\):

\[ D[i][j] = \begin{cases} j & \text{nếu } i = 0 \\ i & \text{nếu } j = 0 \\ D[i{-}1][j{-}1] & \text{nếu } s[i] = t[j] \\ 1 + \min(D[i{-}1][j], \; D[i][j{-}1], \; D[i{-}1][j{-}1]) & \text{trường hợp khác} \end{cases} \]

• Khoảng cách sửa hỗ trợ sửa lỗi chính tả, so khớp mờ (fuzzy matching), và căn chỉnh chuỗi DNA. Trong NLP, nó được dùng để xử lý lỗi đánh máy và tìm các từ tương tự.

• Tokenisation chia văn bản thành các đơn vị rời rạc (token) mà mô hình có thể xử lý. Đây là bước tiền xử lý đầu tiên và có thể nói là quan trọng nhất. Lựa chọn chiến lược tokenisation ảnh hưởng sâu sắc đến hành vi của mô hình.

• Tokenisation bằng khoảng trắng (Whitespace tokenisation) tách dựa trên dấu cách. Đơn giản nhưng ngây thơ: "New York" thành hai token, "don't" là một token (hoặc bị tách thành "don" và "'t" tuỳ bộ tách), và các ngôn ngữ như tiếng Trung, tiếng Nhật hoàn toàn không có dấu cách giữa các từ.

• Tokenisation dựa trên quy tắc (Rule-based tokenisation) dùng các mẫu được viết tay (biểu thức chính quy) để xử lý các trường hợp co rút (contractions), dấu câu và các trường hợp đặc biệt. "I'm" → "I" + "'m", "U.S.A." vẫn là một token. Mỗi ngôn ngữ cần bộ quy tắc riêng, rất tốn công sức.

• Tokenisation dưới từ (Subword tokenisation) là giải pháp hiện đại. Thay vì tách ở ranh giới từ, nó học một bộ từ vựng gồm các đơn vị dưới từ phổ biến từ dữ liệu. Điều này xử lý một cách tinh tế các từ chưa biết: nếu "unhappiness" không có trong từ vựng, nó có thể được tách thành "un" + "happi" + "ness", bảo toàn cấu trúc hình thái.

• 

• Byte-Pair Encoding (BPE) bắt đầu với từng ký tự riêng lẻ làm từ vựng. Nó liên tục tìm cặp ký tự liền kề xuất hiện nhiều nhất và gộp chúng thành một token mới. Sau đủ số lần gộp, các từ thông dụng trở thành token đơn và các từ hiếm được tách thành các mảnh dưới từ phổ biến.

• Thuật toán BPE:

  1. Khởi tạo từ vựng với tất cả các ký tự riêng lẻ trong kho ngữ liệu huấn luyện
  2. Đếm tần suất của mọi cặp token liền kề
  3. Gộp cặp xuất hiện nhiều nhất thành một token mới
  4. Lặp lại bước 2-3 cho đến số lần gộp mong muốn (kích thước từ vựng)

• Ví dụ, bắt đầu với "l o w" (5 lần), "l o w e r" (2 lần), "n e w e s t" (6 lần): cặp xuất hiện nhiều nhất có thể là "e s" → gộp thành "es". Rồi "es t" → "est". Rồi "n e w" → "new". Từ vựng cuối cùng chứa cả từ đầy đủ và các mảnh dưới từ.

• WordPiece (được BERT dùng) tương tự BPE nhưng chọn các lần gộp dựa trên hợp lý (likelihood) thay vì tần suất. Nó gộp cặp làm tăng hợp lý của mô hình ngôn ngữ trên dữ liệu huấn luyện nhiều nhất. Các token dưới từ không đứng đầu từ được thêm tiền tố "##" (ví dụ: "playing" → "play" + "##ing").

• Unigram (được SentencePiece dùng) tiếp cận ngược lại: bắt đầu với một từ vựng lớn và loại bỏ dần các token mà việc loại bỏ chúng ít làm tổn hại hợp lý của dữ liệu huấn luyện nhất. Từ vựng cuối cùng là tập các đơn vị dưới từ giải thích tốt nhất kho ngữ liệu.

• SentencePiece là thư viện tokenisation độc lập ngôn ngữ, xử lý đầu vào như một luồng byte thô (không qua tiền tokenisation dựa trên khoảng trắng). Nó hoạt động được với mọi ngôn ngữ, kể cả những ngôn ngữ không có dấu cách. SentencePiece triển khai cả thuật toán BPE và Unigram.

• Kích thước từ vựng là một siêu tham số quan trọng. Lựa chọn điển hình từ 30.000 đến 100.000 token. Từ vựng lớn hơn đồng nghĩa với ít token hơn trên mỗi chuỗi (hiệu quả hơn) nhưng bảng embedding lớn hơn. Từ vựng nhỏ hơn đồng nghĩa với nhiều mảnh dưới từ hơn và chuỗi dài hơn.

• Cả hai kỹ thuật đều rút gọn từ về dạng cơ bản, nhưng khác nhau về cách tiếp cận.

• Rút gọn (Stemming) cắt bỏ hậu tố bằng các quy tắc thô. Bộ rút gọn Porter biến "running" thành "run", "happiness" thành "happi", và "studies" thành "studi". Nó nhanh nhưng thiếu chính xác: "university" và "universe" đều thành "univers" dù không liên quan.

• Lemmatisation dùng từ vựng và phân tích hình thái để tìm dạng từ điển thực sự (lemma). "Running" → "run", "better" → "good", "mice" → "mouse". Nó đòi hỏi biết từ loại: "saw" là động từ thì lemma thành "see", nhưng là danh từ thì giữ nguyên "saw".

• Tokenisation dưới từ hiện đại đã phần lớn thay thế stemming và lemmatisation trong NLP nơ-ron, nhưng chúng vẫn hữu ích trong truy xuất thông tin và khi làm việc với các mô hình nhỏ hơn hoặc dữ liệu hạn chế.

• Gán nhãn từ loại (POS tagging) gán một phạm trù ngữ pháp cho mỗi từ: danh từ, động từ, tính từ, từ hạn định, v.v. Đây là một trong những bài toán NLP lâu đời nhất và là nền tảng cho phân tích cú pháp.

• Bộ nhãn Penn Treebank là phổ biến nhất cho tiếng Anh, với 36 nhãn (NN cho danh từ số ít, NNS cho danh từ số nhiều, VB cho động từ nguyên thể, VBD cho quá khứ, JJ cho tính từ, v.v.).

• POS tagging rất khó vì nhiều từ đa nghĩa từ loại. "Book" có thể là danh từ ("the book") hoặc động từ ("book a flight"). "Run" có hàng chục nghĩa trải khắp các từ loại. Ngữ cảnh là yếu tố then chốt.

• Các bộ gán nhãn đầu tiên dùng Mô hình Markov Ẩn (HMM) từ chương 05. Các trạng thái ẩn là các nhãn từ loại, các quan sát là các từ. Xác suất chuyển tiếp nắm bắt chuỗi nhãn (một từ hạn định thường được theo sau bởi danh từ hoặc tính từ), và xác suất phát xạ nắm bắt từ nào xuất hiện với nhãn nào. Thuật toán Viterbi tìm chuỗi nhãn có khả năng nhất.

• Mô hình HMM cho POS tagging:

\[\\hat{t}_{1:n} = \\arg\\max_{t_{1:n}} \\prod_{i=1}^{n} P(w_i \\mid t_i) \\cdot P(t_i \\mid t_{i-1})\]

• Các bộ gán nhãn POS hiện đại dùng mạng nơ-ron (BiLSTM hoặc transformer) và đạt độ chính xác trên 97% cho tiếng Anh, tiệm cận hiệu suất con người.

• Nhận dạng thực thể tên (NER) xác định và phân loại tên riêng và các thực thể đặc thù khác trong văn bản: người, tổ chức, địa điểm, ngày tháng, số tiền, v.v.

• Trong "Apple CEO Tim Cook announced the event in Cupertino on Monday," một hệ thống NER cần xác định: Apple (ORG), Tim Cook (PER), Cupertino (LOC), Monday (DATE).

• NER thường được đóng khung như gán nhãn chuỗi (sequence labelling) dùng BIO tagging (còn gọi là IOB tagging). Mỗi token nhận một nhãn:

  • B-TYPE: bắt đầu một thực thể loại TYPE
  • I-TYPE: bên trong (tiếp theo của) một thực thể loại TYPE
  • O: nằm ngoài mọi thực thể

• "Tim Cook visited New York" thành: Tim/B-PER Cook/I-PER visited/O New/B-LOC York/I-LOC. Nhãn B đánh dấu nơi một thực thể mới bắt đầu, rất quan trọng khi hai thực thể cùng loại nằm cạnh nhau.

• 

• NER kinh điển dùng Trường Ngẫu nhiên Có điều kiện (Conditional Random Fields - CRFs) từ chương 05, mô hình hoá xác suất có điều kiện của toàn bộ chuỗi nhãn dựa trên đầu vào. Không giống HMM là mô hình sinh (generative, \(P(x, y)\)), CRF là mô hình phân biệt (discriminative) và mô hình \(P(y \mid x)\) trực tiếp. Một linear-chain CRF định nghĩa:

\[P(y_{1:n} \mid x_{1:n}) = \frac{1}{Z(x)} \exp\!\left(\sum_{i=1}^{n} \left[\sum_k \lambda_k f_k(y_i, x, i) + \sum_j \mu_j g_j(y_i, y_{i-1}, x, i)\right]\right)\]

• Ở đây \(f_k\) là đặc trưng phát xạ (emission features) (khả năng nhãn \(y_i\) xuất hiện với đầu vào tại vị trí \(i\)) và \(g_j\) là đặc trưng chuyển tiếp (transition features) (khả năng nhãn \(y_i\) xuất hiện sau nhãn \(y_{i-1}\)).

• Hàm phân hoạch \(Z(x) = \sum_{y'} \exp(...)\) tính tổng trên mọi chuỗi nhãn có thể để chuẩn hoá phân bố. Huấn luyện cực đại hoá log-hợp lý có điều kiện (conditional log-likelihood), đòi hỏi tính \(Z(x)\) hiệu quả dùng thuật toán forward (chương 05).

• Lợi thế chính so với phân loại từng token độc lập: các đặc trưng chuyển tiếp của CRF thực thi các ràng buộc cấu trúc (ví dụ: I-PER chỉ nên theo sau B-PER hoặc I-PER, không bao giờ xuất hiện sau O).

• NER hiện đại xếp một CRF lên trên một bộ mã hoá nơ-ron (BiLSTM-CRF hoặc BERT-CRF), trong đó mạng nơ-ron tạo ra điểm phát xạ (emission scores) và lớp CRF học cấu trúc chuyển tiếp.

• Phân tích cú pháp (Syntactic parsing) chuyển đổi một câu thành cấu trúc cú pháp của nó, hoặc là cây cấu thành hoặc cây phụ thuộc (cả hai từ file 01).

• Thuật toán CYK (Cocke-Younger-Kasami) phân tích câu với văn phạm phi ngữ cảnh bằng quy hoạch động.

• Nó yêu cầu văn phạm ở Dạng Chuẩn Chomsky (Chomsky Normal Form) (mọi luật đều có hai phi kết thúc hoặc một kết thúc ở vế phải). Nó điền một bảng tam giác theo chiều từ dưới lên: các ô biểu diễn các đoạn của câu, và mỗi ô lưu các ký hiệu phi kết thúc có thể sinh ra đoạn đó.

• CYK chạy trong thời gian \(O(n^3 \cdot |G|)\), với \(n\) là độ dài câu và \(|G|\) là kích thước văn phạm. Giải pháp chính xác nhưng chậm với văn phạm lớn.

• Phân tích Shift-reduce xử lý câu từ trái sang phải, duy trì một ngăn xếp. Ở mỗi bước, nó hoặc shift (đẩy từ tiếp theo vào ngăn xếp) hoặc reduce (lấy các phần tử từ ngăn xếp và thay thế bằng một cụm từ). Một bộ phân loại đã huấn luyện quyết định hành động tại mỗi bước. Phương pháp này chạy trong \(O(n)\), nhanh hơn CYK nhiều.

• Phân tích cú pháp phụ thuộc (Dependency parsing) hiện phổ biến hơn phân tích cấu thành trong thực tế. Các bộ phân tích phụ thuộc dựa trên chuyển trạng thái (transition-based, như shift-reduce) và dựa trên đồ thị (graph-based, tính điểm cho mọi cạnh có thể và tìm cây bao trùm lớn nhất) là hai phương pháp chính. Các bộ phân tích phụ thuộc nơ-ron dùng BiLSTM hoặc transformer đạt kết quả hiện đại nhất.

• Trước thời embedding, NLP biểu diễn tài liệu thành vector bằng các phương pháp đếm đơn giản.

• Mô hình túi từ (Bag-of-words - BoW) biểu diễn một tài liệu thành vector đếm từ, bỏ qua hoàn toàn thứ tự từ. Nếu từ vựng có \(V\) từ, mỗi tài liệu là một vector trong \(\mathbb{R}^V\) (kết nối trở lại không gian vector từ chương 01). Giá trị cho từ \(w\) là số lần \(w\) xuất hiện trong tài liệu.

• 

• BoW đơn giản nhưng hiệu quả bất ngờ cho các tác vụ như phân loại tài liệu và lọc thư rác. Điểm yếu chính là nó coi mọi từ quan trọng như nhau: "the" và "revolutionary" có trọng số ngang nhau.

• TF-IDF (Tần suất Thuật ngữ - Nghịch đảo Tần suất Tài liệu) khắc phục điều này bằng cách gán trọng số cho từ dựa trên mức độ thông tin của chúng. Những từ xuất hiện thường xuyên trong một tài liệu nhưng hiếm trên toàn bộ kho ngữ liệu thường quan trọng cho tài liệu đó.

\[\text{TF-IDF}(t, d) = \text{TF}(t, d) \times \text{IDF}(t)\]

• Tần suất thuật ngữ (Term frequency) \(\text{TF}(t, d)\) thường là số đếm thô của thuật ngữ \(t\) trong tài liệu \(d\) (hoặc log của nó: \(1 + \log(\text{count})\)).

• Nghịch đảo tần suất tài liệu (Inverse document frequency) \(\text{IDF}(t) = \log\frac{N}{|\{d : t \in d\}|}\), với \(N\) là tổng số tài liệu. Các từ xuất hiện trong mọi tài liệu (như "the") có IDF gần bằng 0. Từ hiếm có IDF cao.

• Các vector TF-IDF có thể được so sánh bằng độ tương tự cosine (từ chương 01) để đo độ tương tự giữa các tài liệu. Đây là nền tảng của truy xuất thông tin kinh điển và các công cụ tìm kiếm.

• Mô hình ngôn ngữ (Language model) gán xác suất cho một chuỗi từ. Nó trả lời: câu này khả dĩ đến đâu? Mô hình ngôn ngữ là trung tâm của dịch máy, nhận dạng giọng nói, sửa lỗi chính tả và sinh văn bản.

• Xác suất của một câu \(w_1, w_2, \ldots, w_n\), theo quy tắc dây chuyền xác suất (chương 05):

\[P(w_1, w_2, \ldots, w_n) = \prod_{i=1}^{n} P(w_i \mid w_1, \ldots, w_{i-1})\]

• Điều này chính xác nhưng không khả thi: bạn cần lưu xác suất cho mọi lịch sử có thể có. Giả định Markov (chương 05) cắt ngắn lịch sử chỉ còn \(k-1\) từ cuối cùng, cho ra mô hình n-gram (với \(n = k\)).

• Mô hình bigram (\(n = 2\)) chỉ phụ thuộc vào từ trước đó:

\[P(w_i \mid w_1, \ldots, w_{i-1}) \approx P(w_i \mid w_{i-1})\]

• Mô hình trigram (\(n = 3\)) phụ thuộc vào hai từ trước đó. Xác suất n-gram được ước lượng bằng cách đếm trong kho ngữ liệu:

\[P(w_i \mid w_{i-1}) = \frac{\text{count}(w_{i-1}, w_i)}{\text{count}(w_{i-1})}\]

• Độ rối (Perplexity) đo mức độ tốt của mô hình ngôn ngữ khi dự đoán một tập kiểm tra. Nó là xác suất nghịch đảo của tập kiểm tra, được chuẩn hoá theo số lượng từ:

\[\text{PPL} = P(w_1, \ldots, w_N)^{-1/N} = \exp\!\left(-\frac{1}{N} \sum_{i=1}^{N} \log P(w_i \mid w_{<i})\right)\]

• Độ rối thấp hơn có nghĩa mô hình ít "bị bất ngờ" bởi dữ liệu kiểm tra và do đó tốt hơn. Một mô hình gán xác suất đều cho từ vựng 10.000 từ có độ rối là 10.000. Một mô hình bigram tốt có thể đạt độ rối khoảng 200. Mô hình ngôn ngữ nơ-ron hiện đại đạt độ rối dưới 20.

• Lưu ý độ rối chính là entropy chéo được lấy mũ (từ lý thuyết thông tin chương 05). Cực tiểu hoá mất mát entropy chéo trong huấn luyện tương đương với cực tiểu hoá độ rối.

• Làm mịn (Smoothing) xử lý vấn đề xác suất không: nếu một n-gram chưa bao giờ xuất hiện trong huấn luyện, mô hình gán cho nó xác suất 0, làm cho xác suất của toàn bộ câu bằng 0. Làm mịn Laplace (add-1) thêm một số đếm nhỏ cho mọi n-gram:

\[P_{\text{Laplace}}(w_i \mid w_{i-1}) = \frac{\text{count}(w_{i-1}, w_i) + 1}{\text{count}(w_{i-1}) + V}\]

• Phương pháp này quá mạnh với từ vựng lớn (nó lấy quá nhiều xác suất từ các n-gram đã thấy). Làm mịn Kneser-Ney là tiêu chuẩn vàng cho mô hình n-gram. Nó kết hợp hai ý tưởng: chiết khấu tuyệt đối (absolute discounting) và xác suất tiếp nối (continuation probability) cho backoff.

• Đầu tiên, chiết khấu tuyệt đối trừ một chiết khấu cố định \(d\) (thường \(d \approx 0.75\)) từ mỗi số đếm đã thấy, thay vì thêm các số đếm giả. Khối lượng xác suất được giải phóng được phân phối lại cho các n-gram chưa thấy. Dạng nội suy là:

\[P_{\text{KN}}(w_i \mid w_{i-1}) = \frac{\max(\text{count}(w_{i-1}, w_i) - d, \; 0)}{\text{count}(w_{i-1})} + \lambda(w_{i-1}) \cdot P_{\text{cont}}(w_i)\]

• trong đó \(\lambda(w_{i-1})\) là hằng số chuẩn hoá phân phối khối lượng chiết khấu. Cải tiến chính là xác suất tiếp nối (continuation probability) \(P_{\text{cont}}(w_i)\), đo lường số lượng ngữ cảnh khác nhau mà \(w_i\) xuất hiện, thay vì tần suất tổng thể:

\[P_{\text{cont}}(w_i) = \frac{|\{w' : \text{count}(w', w_i) > 0\}|}{|\{(w', w'') : \text{count}(w', w'') > 0\}|}\]

• Tử số đếm số từ riêng biệt đứng trước \(w_i\) trong kho ngữ liệu. Một từ như "Francisco" xuất hiện trong rất ít ngữ cảnh (hầu như luôn sau "San"), vì vậy dù "San Francisco" rất phổ biến, "Francisco" vẫn có xác suất tiếp nối thấp và sẽ không bị dự đoán sai ở các ngữ cảnh khác.

• Ngược lại, các từ phổ biến như "the" xuất hiện sau nhiều từ khác nhau và có xác suất tiếp nối cao. Điều này nắm bắt trực giác rằng tính linh hoạt (versatility) của một từ quan trọng hơn tần suất thô của nó cho ước lượng backoff.

• Mô hình n-gram đã là công nghệ hiện đại nhất trong nhiều thập kỷ. Chúng nhanh, dễ diễn giải và không cần huấn luyện (chỉ đếm). Nhưng chúng gặp khó khăn với các phụ thuộc xa (ví dụ: "The keys that I left on the table are missing" đòi hỏi biết chủ ngữ "keys" là số nhiều, nằm xa động từ). Các mô hình ngôn ngữ nơ-ron, bắt đầu với RNN và đỉnh cao là transformer, giải quyết hạn chế này.

Bài tập Lập trình (dùng CoLab hoặc notebook)

1. Triển khai khoảng cách sửa Levenshtein bằng quy hoạch động. Kiểm tra trên các cặp từ và dùng nó cho sửa lỗi chính tả đơn giản.

   import jax.numpy as jnp
   
   def edit_distance(s, t):
       """Tính khoảng cách Levenshtein bằng DP."""
       m, n = len(s), len(t)
       D = [[0] * (n + 1) for _ in range(m + 1)]
   
       for i in range(m + 1):
           D[i][0] = i
       for j in range(n + 1):
           D[0][j] = j
   
       for i in range(1, m + 1):
           for j in range(1, n + 1):
               if s[i-1] == t[j-1]:
                   D[i][j] = D[i-1][j-1]
               else:
                   D[i][j] = 1 + min(D[i-1][j], D[i][j-1], D[i-1][j-1])
   
       return D[m][n]
   
   # Kiểm tra
   pairs = [("kitten", "sitting"), ("sunday", "saturday"), ("hello", "hallo")]
   for s, t in pairs:
       print(f"d('{s}', '{t}') = {edit_distance(s, t)}")
   
   # Sửa lỗi chính tả đơn giản
   dictionary = ["the", "their", "there", "then", "than", "this", "that", "these", "those"]
   misspelled = "thier"
   corrections = sorted(dictionary, key=lambda w: edit_distance(misspelled, w))
   print(f"\nGần nhất với '{misspelled}': {corrections[:3]}")
   

2. Triển khai tokenisation BPE từ đầu. Bắt đầu với token cấp ký tự và lặp việc gộp các cặp xuất hiện nhiều nhất.

   from collections import Counter
   
   def get_pairs(corpus):
       """Đếm các cặp token liền kề trên mọi từ."""
       pairs = Counter()
       for word, freq in corpus.items():
           symbols = word.split()
           for i in range(len(symbols) - 1):
               pairs[(symbols[i], symbols[i+1])] += freq
       return pairs
   
   def merge_pair(pair, corpus):
       """Gộp mọi xuất hiện của một cặp trong kho ngữ liệu."""
       new_corpus = {}
       bigram = ' '.join(pair)
       replacement = ''.join(pair)
       for word, freq in corpus.items():
           new_word = word.replace(bigram, replacement)
           new_corpus[new_word] = freq
       return new_corpus
   
   # Kho ngữ liệu huấn luyện với tần suất từ
   text = "low low low low low lower lower newest newest newest newest newest newest"
   word_freqs = Counter(text.split())
   # Khởi tạo: tách mỗi từ thành các ký tự với ký tự kết thúc từ
   corpus = {' '.join(word) + ' _': freq for word, freq in word_freqs.items()}
   
   print("Kho ngữ liệu ban đầu:")
   for word, freq in corpus.items():
       print(f"  {word}: {freq}")
   
   # Chạy BPE cho 10 lần gộp
   for i in range(10):
       pairs = get_pairs(corpus)
       if not pairs:
           break
       best_pair = max(pairs, key=pairs.get)
       corpus = merge_pair(best_pair, corpus)
       print(f"\nGộp {i+1}: {best_pair} (freq={pairs[best_pair]})")
       for word, freq in corpus.items():
           print(f"  {word}: {freq}")
   

3. Xây dựng mô hình ngôn ngữ bigram và tính độ rối (perplexity) trên một câu kiểm tra. Thử nghiệm với làm mịn Laplace.

   from collections import Counter, defaultdict
   import math
   
   # Kho ngữ liệu huấn luyện
   train = """the cat sat on the mat . the dog chased the cat .
   the cat ran from the dog . a dog sat on a mat .""".split()
   
   # Đếm bigram và unigram
   bigrams = Counter(zip(train[:-1], train[1:]))
   unigrams = Counter(train)
   vocab_size = len(set(train))
   
   def bigram_prob(w2, w1, alpha=0):
       """P(w2 | w1) với làm mịn Laplace tuỳ chọn."""
       return (bigrams[(w1, w2)] + alpha) / (unigrams[w1] + alpha * vocab_size)
   
   # Tính độ rối
   test = "the cat sat on a mat .".split()
   
   for alpha in [0, 1, 0.1]:
       log_prob = 0
       for w1, w2 in zip(test[:-1], test[1:]):
           p = bigram_prob(w2, w1, alpha=alpha)
           if p > 0:
               log_prob += math.log(p)
           else:
               log_prob += float('-inf')
   
       ppl = math.exp(-log_prob / (len(test) - 1)) if log_prob > float('-inf') else float('inf')
       print(f"Làm mịn α={alpha}: độ rối = {ppl:.2f}")
   

4. Triển khai TF-IDF từ đầu và dùng độ tương tự cosine để tìm tài liệu tương tự nhất với một truy vấn.

   import jax.numpy as jnp
   import math
   from collections import Counter
   
   documents = [
       "the cat sat on the mat",
       "the dog chased the cat around the park",
       "a mat was placed on the floor by the door",
       "the quick brown fox jumped over the lazy dog",
   ]
   
   # Xây dựng từ vựng
   vocab = sorted(set(word for doc in documents for word in doc.split()))
   word_to_idx = {w: i for i, w in enumerate(vocab)}
   V = len(vocab)
   N = len(documents)
   
   # Tính ma trận TF-IDF
   doc_freq = Counter()
   for doc in documents:
       for word in set(doc.split()):
           doc_freq[word] += 1
   
   tfidf_matrix = jnp.zeros((N, V))
   for i, doc in enumerate(documents):
       word_counts = Counter(doc.split())
       for word, count in word_counts.items():
           tf = 1 + math.log(count)
           idf = math.log(N / doc_freq[word])
           j = word_to_idx[word]
           tfidf_matrix = tfidf_matrix.at[i, j].set(tf * idf)
   
   # Truy vấn
   query = "cat on the mat"
   query_vec = jnp.zeros(V)
   query_counts = Counter(query.split())
   for word, count in query_counts.items():
       if word in word_to_idx:
           tf = 1 + math.log(count)
           idf = math.log(N / doc_freq.get(word, 1))
           query_vec = query_vec.at[word_to_idx[word]].set(tf * idf)
   
   # Độ tương tự cosine (từ chương 01)
   def cosine_sim(a, b):
       return jnp.dot(a, b) / (jnp.linalg.norm(a) * jnp.linalg.norm(b) + 1e-8)
   
   print(f"Truy vấn: '{query}'\n")
   for i, doc in enumerate(documents):
       sim = cosine_sim(query_vec, tfidf_matrix[i])
       print(f"  Văn bản {i} (sim={sim:.3f}): '{doc}'")