[Natural Language Processing] Phân biệt ba mô hình HMM (Hidden Markov Model) - MEMM (Maximum Entropy MM) và CRF (Conditional Random Fields)

Trong bài này, tôi sẽ trình bày những hiểu biết của tôi một cách sơ lược nhất, tất nhiên để hiểu cả 3 mô hình này bạn phải đọc những bài báo nguyên gốc của Mc. Calumn hay Laferty. Dưới đây chỉ là những điểm quan trọng nhất khi ta muốn phân biệt 3 mô hình này dựa trên sự hiểu biết của tôi.

Đầu tiên là HMM và MEMM

Fig 1

HMM

Khi này, ta phải tìm xác suất sau:

Fig 2

Ta thấy rằng yếu điểm của HMM là nó không thể tận dụng được observation (trong Fig1, observation là các từ của câu ví dụ: is, expected ...) Ngoài ra, bài toán tìm xác suất của trạng thái kế tiếp lại trở thành bài toán tìm observation khi biết trước trạng thái, và ta có thể nhận xét rằng HMM chỉ phụ thuộc vào trạng thái trước đó, không tận dụng được observation.

MEMM
Trong MEMM, ta phải tính xác suất dưới đây:

Công thức trên là chỉ tính cho 1 observation, ví dụ "is". Muốn tính cho cả bộ observation, công thức được viết lại như sau:

Ở đây ta có phép nhân ngoài cùng có t chạy từ 1 đến số lượng của observation, ví dụ như trong Fig 1 thì t chạy từ 1 đến 6. Cũng giống như HMM thôi, ta phải tìm trạng thái cho từng bước, và để đi từ trạng thái 1 đến trạng thái 6 (đủ cả 1 câu trong Fig 1), ta phải tính tích các xác suất chuyển trạng thái đó.

Z là hệ số chuẩn hóa, để đảm bảo tổng các xác suất chuyển trạng thái luôn bằng 1. Để hình dung rõ hơn về Z, ta xem hình dưới đây:

Fig 3

Từ trạng thái số 0, nếu observation là r, ta sẽ có 2 cách chuyển trạng thái là đến 1 hoặc 4, khi đó số trạng thái có thể chuyển từ 0 là 2. Khi này, Z sẽ đảm bảo việc tổng các trạng thái đi từ 1 đến các trạng thái khác luôn bằng 1, và Z là hệ số chuẩn hóa cho việc chuyển trạng thái (normalizer for state transition probability). Cũng từ công thức MEMM, lambda k là hệ số học được từ việc training.

Vậy training ở trong MEMM là gì? Trong MEMM, ta cũng có các feature, ví dụ như cả câu này bao nhiêu từ, chữ cái là viết hoa hay thường, số dấu cách trong câu là bao nhiêu ... và training input là các observation. Hàm f(s,o) là một hàm chỉ nhận giá trị 0 và 1 ứng với feature k và observation o. Ví dụ ta có 1 feature là chữ cái đầu tiên là viết hoa, và observation là Secretariat, thì giá trị hàm này là 1, nhưng với feature cả observation là chữ hoa, với cùng observation, giá trị hàm này là 0. Vậy ở trên hàm mũ e, giá trị trong là tổng qua các feature đối với observation o ở trạng thái s.

MEMM có 1 vấn đề gọi là Label bias.
Để hiểu về vấn đề này, ta sẽ xem trong Fig 3.

Bạn có thể đọc từ trên xuống dưới và thấy sự bất hợp lý khi mà Pr(2|1,o) = Pr(2|1,i), vấn đề này xảy ra là do khi ở trạng thái số 1, nếu muốn qua trạng, chỉ có 1 đường duy nhất, do đó mà việc chuyển trạng thái không quan tâm đến observation là i hay là o. Khi đọc bài báo về MEMM, vấn đề này còn được đề cập như local decision, tức là MEMM chỉ quan tâm observation ở trạng thái đó mà không quan tâm đến observation khác.

Để kế thừa MEMM và giải quyết label bias, ta cùng tìm hiểu CRF

CRF

Fig 4

Với CRF, trạng thái sẽ phụ thuộc vào toàn bộ observation để tránh label bias (local descision), do đó ta sẽ không thấy các mũi tên từ observation đến state hoặc state đến state nữa.
Khi này, hệ số chuẩn hóa sẽ trên cả tập observation, lí do là bởi ta ở 1 trạng thái, hàm f có thể nhận đầu vào là cả chuỗi observation chứ không phải 1 observation đơn lẻ giống MEMM nữa.
Nhưng vấn đề ở đây làm liệu ta có cần quan tâm đến hệ số chuẩn hóa cho việc chuyển trạng thái giống MEMM không khi mà trong công thức ta không thấy hệ số đó. Câu hỏi là phải chăng trong CRF, ta chỉ có 1 trạng thái duy nhất để chuyển tới nên không có normalizer cho state transition?

Ngoài ta, hệ số lambda cũng thu được từ việc training giống MEMM, hàm f khi này sẽ phụ thuộc vào cả trạng thái trước đó.