NLP301c - Phần 6: Gán nhãn từ loại và mô hình Markov ẩn

Đáp án đúng: "Decoding problem". HMM (Hidden Markov Model, mô hình Markov ẩn) có ba bài toán cơ bản theo cách trình bày kinh điển của Rabiner: tính xác suất chuỗi quan sát, tìm chuỗi trạng thái ẩn tốt nhất, và học tham số. Bài toán giải mã (decoding) chính là tìm chuỗi trạng thái có xác suất cao nhất đã sinh ra chuỗi quan sát, giải hiệu quả bằng thuật toán Viterbi dùng quy hoạch động với độ phức tạp O(N²T) thay vì duyệt cả N^T chuỗi khả dĩ. "Evaluation problem" là bài toán tính P(O|λ), xác suất mô hình sinh ra chuỗi quan sát, giải bằng thuật toán forward, chỉ trả về một con số chứ không trả về chuỗi trạng thái. "Likelihood estimation problem" là tên gọi khác của chính bài toán đánh giá đó (tính likelihood, độ hợp lý của quan sát), nên cũng không cho ra chuỗi trạng thái. "Learning problem" là ước lượng ma trận chuyển trạng thái và ma trận phát xạ từ dữ liệu, thường bằng thuật toán Baum-Welch (forward-backward), tức điều chỉnh mô hình chứ không giải mã một chuỗi quan sát cụ thể.

Đáp án đúng: "All of the others". Sequential labeling (gán nhãn chuỗi) là bài toán nhận vào một chuỗi đơn vị và gán cho mỗi đơn vị một nhãn, trong đó nhãn của phần tử này phụ thuộc vào ngữ cảnh và nhãn lân cận; các mô hình điển hình là HMM, CRF và RNN/LSTM. "POS tagging" gán cho từng token một nhãn từ loại như NN, VB, JJ, là ví dụ kinh điển của gán nhãn chuỗi. "Named Entity Recognition" gán cho từng token nhãn dạng BIO như B-PER, I-PER, O để khoanh vùng thực thể, cũng là gán nhãn chuỗi. "Speech recognition" theo cách tiếp cận cổ điển dùng HMM để gán cho chuỗi khung âm thanh một chuỗi trạng thái âm vị rồi giải mã bằng Viterbi, nên cũng thuộc cùng họ kỹ thuật. Mỗi tác vụ này đứng riêng đều đúng nhưng chỉ là một phần, nên phương án bao gồm cả ba mới là câu trả lời đầy đủ.

Đáp án đúng: "that". Conjunction (liên từ) ở đây là liên từ đẳng lập (coordinating conjunction), loại từ nối hai thành phần ngang hàng như hai từ, hai cụm hay hai mệnh đề; trong bộ nhãn Penn Treebank chúng mang nhãn CC. "that" chủ yếu đóng vai từ hạn định hay đại từ chỉ định (that book, nhãn DT), đại từ quan hệ (the book that I read, nhãn WDT); khi đứng đầu mệnh đề bổ ngữ như I think that he left thì nó là từ dẫn mệnh đề phụ thuộc, không nối hai vế ngang hàng, nên nó không thuộc nhóm liên từ đẳng lập mà câu hỏi nhắm tới. "but" là liên từ đẳng lập biểu thị sự đối lập, như cheap but good. "and" là liên từ đẳng lập biểu thị sự cộng gộp, như cats and dogs. "or" là liên từ đẳng lập biểu thị sự lựa chọn, như tea or coffee. Cả ba đều là liên từ thật nên không được chọn.

Đáp án đúng: "4, 4, 2". Trong câu I am planning to visit New Delhi to attend Analytics Vidhya Delhi Hackathon, các động từ là am, planning, visit, attend nên B = 4; các từ xuất hiện nhiều hơn một lần là to (hai lần) và Delhi (hai lần) nên C = 2. Riêng giá trị A là chỗ tranh cãi: nếu coi mỗi tên riêng nhiều chữ là một danh từ (New Delhi, Analytics Vidhya, Delhi, Hackathon) và không tính đại từ I thì A = 4, khớp trọn "4, 4, 2"; còn nếu đếm từng token I, New, Delhi, Analytics, Vidhya, Delhi, Hackathon thì A = 7 và không phương án nào khớp đủ ba số. Dù đếm cách nào, "4, 4, 2" vẫn là phương án duy nhất đúng cả B = 4 lẫn C = 2. "5, 5, 2" sai ở số động từ, câu chỉ có bốn động từ chứ không phải năm. "5, 5, 0" sai cả số động từ lẫn số từ lặp, vì bỏ qua việc to và Delhi đều xuất hiện hai lần. "7, 5, 1" có giá trị A trùng cách đếm token nói trên nhưng đếm thừa một động từ và chỉ thấy một từ lặp, nên sai hai trong ba số.

Đáp án đúng: "Temporal model". Hidden Markov Model (mô hình Markov ẩn) là một mô hình xác suất theo thời gian: thế giới được chia thành các lát thời gian rời rạc, và ở mỗi lát t mô hình thêm vào một biến trạng thái ẩn X_t cùng một biến quan sát E_t, nối với nhau bằng mô hình chuyển trạng thái P(X_t | X_t−1) và mô hình cảm biến P(E_t | X_t). Việc bổ sung biến theo từng bước thời gian chính là đặc trưng của temporal model. "Reality model" không phải khái niệm có trong lý thuyết HMM hay suy luận xác suất. "Probability model" đúng ở chỗ HMM là mô hình xác suất, nhưng một mô hình xác suất nói chung (như Naive Bayes) có tập biến cố định, không có trục thời gian để thêm biến theo từng lát, nên không trả lời được chỗ các biến bổ sung nằm ở đâu. "All of the others" sai vì kéo theo cả "Reality model", vốn không tồn tại.

Đáp án đúng: "HMM". Hidden Markov Model (mô hình Markov ẩn) là một mô hình thống kê cụ thể, rất phổ biến trong NLP truyền thống: nó coi nhãn (như từ loại) là chuỗi trạng thái ẩn theo giả định Markov và từ là quan sát sinh ra từ trạng thái, được dùng cho gán nhãn từ loại, nhận dạng thực thể, nhận dạng tiếng nói, giải mã bằng thuật toán Viterbi. "Stochastic" là tính từ "ngẫu nhiên", mô tả một hướng tiếp cận dựa trên xác suất nói chung, không phải tên một mô hình. "Hybrid" chỉ hướng tiếp cận lai, kết hợp luật viết tay với thống kê, cũng là một chiến lược chứ không phải mô hình thống kê. "Lengustic" ám chỉ hướng tiếp cận dựa trên tri thức ngôn ngữ học và luật, vốn là đối cực của cách tiếp cận thống kê, nên không thể là mô hình thống kê được dùng thường xuyên.

Đáp án đúng: "Part-of-speech tagging.". Duck có thể là danh từ (con vịt) hoặc động từ (cúi né) và chỉ ngữ cảnh mới quyết định, như trong câu I saw her duck. POS tagging (gán nhãn từ loại) gán cho mỗi từ trong câu một nhãn như NN hay VB dựa trên các từ xung quanh, bằng HMM, CRF hay mạng nơ-ron, nên giải đúng loại nhập nhằng từ loại này. "Lexical analysis" là mức tách từ, nhận diện từ vựng và hình thái; nó có thể cho biết duck có hai từ loại khả dĩ trong từ điển nhưng không chọn từ loại theo ngữ cảnh. "Semantic analysis" xử lý nghĩa của câu, đứng sau bước xác định từ loại và dựa vào kết quả đó. "Pragmatic analysis" diễn giải ý định của người nói trong tình huống, là mức cao nhất, không phải nơi xác định một từ là danh từ hay động từ.

Đáp án đúng: "Survivors". Thuật toán Viterbi là quy hoạch động để tìm chuỗi trạng thái ẩn có xác suất cao nhất trong HMM; tại mỗi bước thời gian, với từng trạng thái, nó chỉ giữ lại một đường đi tốt nhất dẫn tới trạng thái đó (lưu xác suất lớn nhất cùng con trỏ quay lui) và loại bỏ mọi đường đi kém hơn. Những đường đi được giữ lại ấy gọi là đường sống sót (survivor paths), và khi tới bước cuối, lần ngược theo con trỏ của survivor tốt nhất sẽ ra chuỗi nhãn tối ưu. "Defenders" không phải thuật ngữ dùng trong Viterbi hay lý thuyết giải mã. "Destroyers" cũng không có nghĩa kỹ thuật nào; các đường bị loại chỉ đơn giản là bị bỏ, không có tên riêng. "Carriers" trong viễn thông chỉ sóng mang, còn trong Viterbi không có khái niệm này để gọi các đường được chọn.

Đáp án đúng: "Hidden markov model". Suy luận xác suất theo thời gian (temporal probabilistic reasoning) là việc ước lượng trạng thái thế giới thay đổi qua các bước thời gian dựa trên chuỗi quan sát nhiễu, gồm các tác vụ lọc (filtering), dự báo (prediction), làm trơn (smoothing) và tìm chuỗi giải thích hợp lý nhất. Mô hình Markov ẩn biểu diễn đúng điều này bằng trạng thái ẩn, xác suất chuyển trạng thái và xác suất quan sát, với các thuật toán forward–backward và Viterbi. "Hill-climbing search" là tìm kiếm cục bộ để tối ưu một hàm mục tiêu, luôn đi tới trạng thái lân cận tốt hơn, không có mô hình xác suất hay trục thời gian. "Depth-first search" là tìm kiếm mù duyệt sâu trên không gian trạng thái xác định. "Breadth-first search" duyệt theo từng mức độ sâu, cũng là tìm kiếm mù trên đồ thị xác định, không xử lý sự bất định của quan sát.

Đáp án đúng: "Part of Speech". POS tagging là Part-of-Speech tagging (gán nhãn từ loại): gán cho mỗi token trong câu một nhãn từ loại như danh từ, động từ, tính từ, giới từ, theo bộ nhãn như Penn Treebank (NN, VBZ, JJ, IN); việc gán phải dựa vào ngữ cảnh vì một từ như book có thể là danh từ hoặc động từ, nên thường dùng mô hình chuỗi như HMM với Viterbi hay CRF. "Part of Sentence" sai vì nhãn gán cho từng từ theo loại từ, không phải cho các thành phần câu như chủ ngữ, vị ngữ. "Parsing of Sentence" là phân tích cú pháp, một tác vụ khác dựng cấu trúc cây cho cả câu, thường dùng kết quả gán từ loại làm đầu vào. "Position of Syntax" không phải thuật ngữ trong NLP, chữ P và S trùng nhưng ý nghĩa không tương ứng với tác vụ nào.

Đáp án đúng: "Probability of the best tag sequence given a word sequence". Trong gán nhãn từ loại bằng HMM, thuật toán Viterbi dùng quy hoạch động để tìm chuỗi nhãn T có xác suất cao nhất cho chuỗi từ W đã cho, tức argmax P(T | W); nó trả về chuỗi nhãn tốt nhất đó cùng xác suất của nó (về kỹ thuật là xác suất đồng thời P(T, W), tỉ lệ thuận với P(T | W) vì P(W) cố định). "Probability of word sequence given a particular tag sequence" là P(W | T), tích các xác suất phát xạ, chỉ là một thành phần trong công thức, không phải đầu ra; còn nếu cần xác suất của chuỗi từ thì đó là việc của thuật toán forward. "Optimal transition and observation probabilities for HMM" là kết quả của bước huấn luyện tham số, bằng đếm tần suất trên ngữ liệu có nhãn hoặc thuật toán Baum-Welch, không phải của giải mã Viterbi. "None of the others" sai vì đã có một mô tả đúng đầu ra.

Đáp án đúng: "Smoothing adjusts probabilities to prevent zero values, improving model generalization". Ma trận chuyển trạng thái của HMM hay mô hình n-gram ước lượng bằng đếm, nên cặp nhãn chưa từng gặp trong ngữ liệu huấn luyện nhận xác suất 0 và làm cả chuỗi có xác suất 0. Smoothing (làm trơn) lấy bớt một phần xác suất của sự kiện đã thấy chia cho sự kiện chưa thấy; ví dụ Laplace cộng một: P(t_i|t_i-1) = (C(t_i-1, t_i) + 1) / (C(t_i-1) + V), với V là số trạng thái, nên không ô nào bằng 0 và mô hình khái quát tốt hơn trên dữ liệu mới. "Smoothing increases the size of the transition matrix by adding more rows and columns" sai vì kích thước ma trận do số trạng thái quyết định, làm trơn chỉ đổi giá trị các ô. "Smoothing removes any negative probabilities from the transition matrix." sai vì xác suất ước lượng từ đếm không bao giờ âm. "Smoothing converts all transition probabilities to equal values" sai vì làm mọi ô bằng nhau sẽ xoá sạch thông tin học được; làm trơn chỉ dời một ít xác suất.

Đáp án đúng: "Single discrete random variable". Hidden Markov Model là mô hình xác suất theo thời gian, trong đó trạng thái của quá trình tại mỗi thời điểm được mô tả bằng một biến ngẫu nhiên rời rạc duy nhất, nhận giá trị trong một tập hữu hạn trạng thái ẩn, ví dụ tập nhãn từ loại trong gán nhãn từ loại; nhờ vậy xác suất chuyển trạng thái biểu diễn được bằng một ma trận chuyển. "Single random variable" quá rộng vì không nói biến rời rạc, nếu trạng thái là biến liên tục thì mô hình trở thành bộ lọc Kalman hay hệ động lực tuyến tính chứ không phải HMM. "Literal" (hằng mệnh đề) là khái niệm của logic, như một biến mệnh đề hay phủ định của nó, không dùng để mô tả trạng thái của quá trình ngẫu nhiên. "None of the mentioned" sai vì đã có mô tả chính xác là một biến ngẫu nhiên rời rạc duy nhất.

Đáp án đúng: "N gram and Naive bayes". Bộ gán nhãn HMM chọn chuỗi nhãn t1…tn làm cực đại tích các P(wi | ti) × P(ti | ti−1): thừa số P(ti | ti−1) là xác suất chuyển trạng thái, chính là một mô hình bigram trên chuỗi nhãn, còn P(wi | ti) là xác suất phát ra (emission), tính đúng theo kiểu likelihood của Naive Bayes khi áp dụng định lý Bayes và giả định mỗi từ chỉ phụ thuộc nhãn của nó. Vì vậy công thức HMM là sự kết hợp giữa n-gram và Naive Bayes. "Logistic regression" là mô hình phân biệt (discriminative) ước lượng trực tiếp xác suất nhãn khi biết đặc trưng, gần với MEMM hay CRF chứ không phải HMM vốn là mô hình sinh. "SVM" tìm siêu phẳng có lề cực đại, không có xác suất chuyển hay xác suất phát ra nào. "Euclidean distance between words" là độ đo khoảng cách giữa vectơ, không xuất hiện trong công thức xác suất của HMM.