[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 đó.

[Natural Language Processing] Đánh giá chất lượng của Clustering bằng Rand Index

Trong phương pháp này, ta sẽ đánh giá dựa trên decision với hai tiêu chí như sau. Giả sử ta có N documents:
- Ta so sánh similarity giữa từng cặp documents trong số N docs này với nhau.
- Hai docs giống nhau sẽ thuộc về cùng một cluster
- Số quyết định là tổ hợp chập 2 của N. N(N-1)/2

Khi đưa ra một quyết định, ta sẽ có 4 trường hợp sau đây:

- True Positive (TP): Hai docs giống nhau thuộc về cùng 1 cluster
- True Negative (TN): Hai docs khác nhau khác cluster
- False Postive (FP): Hai docs khác nhau thuộc về cùng 1 cluster (error)
- False Negative (FN): Hai docs giống nhau khác cluster (error)

Khi đó, chỉ số RI (Rand Index) được định nghĩa như sau:

Giả sử ta có observation như hình dưới đây:

Khi đó, ta có thể tính được TP với 3 class là:

TP = tổ hợp chập 2 của 5 + tổ hợp chập 2 của 4 + tổ hợp chập 2 của 3 và tổ hợp chập 2 của 2(có thành phần này vì ta cần quan tâm đến 2 objects đỏ trong cluster 3, RI quan tâm đến 2 docs giống nhau cùng 1 cluster) = 5*4/2 + 4*3/2 + 3*2/2 + 2*1/2 = 10 + 6 + 3 + 1 = 20. (1)

TP + FP được tính là tổng của các quyết định liên quan tới hai docs giống nhau cùng 1 cluster và hai docs khác nhau cùng 1 cluster.
Ta có: TP + FP = tổ hợp chập 2 của 6 + tổ hợp chập 2 của 6 + tổ hợp chập 2 của 5 = 6*5/2 + 6*5/2 + 5*4/2 = 40 (2)

Từ (1) và (2) ta có FP = 20. (3)

Ta có tổng TP + FN là số cặp document giống nhau (có thể chung 1 cluster hoặc khác cluster).

TP + FN = Tổ hợp chập 2 của 8 (vì có 8 chấm đỏ) + tổ hợp chập 2 của 5 (5 chấm xanh) + tổ hợp chập 2 của 4 (4 chấm xanh lá) = 8*7/2 + 5*4/2 + 4*3/2 = 44 (4)

Từ (3) và (4) ta có FN = 24. (5)

Số quyết định trên cả tập là : FN + FP + TN + TP = tổ hợp chập 2 của (8 + 5 + 4) = 136 (6)

Từ (1) (3) (5) và (6) ta có TN = 136 - 24 - 20 - 20 = 72

Từ đó chỉ số RI = (TP+TN)/(TP+TN+FP+FN) = 92/136 ~ 0.68

[Natural Language Processing] LDA trong Xử lý ngôn ngữ tự nhiên

Latent Dirichlet Allocation (LDA)

Quá trình tạo ra một document d trong collection D được định nghĩa như sau (||D|| là số documents trong collection):

Với α là tham số đặc trưng cho sự phân bố của các topic trên mỗi document

(Ví dụ document d có 0.1 là topic 1, 0.4 topic 2, 0.05 topic 3 ...). Do đó nếu ta có 10 topic, vector α sẽ có 10 thành phần. Ví dụ 4 topic. α = (0.4,0.1,0.3,0.2)

β là tham số đặc trưng cho sự phân bố của các word trong một vocabulary V trên một topic

(Ví dụ topic 1 có 0.01 là từ "computer", 0.04 là từ "human" ...). Do đó nếu số lượng từ trong vocabulary là ||V|| thì đó cũng là số thành phần của vector β. β = (β1,β2, .... β||V||)

 ${\displaystyle \varphi }$ (hay đọc là phi, biểu diễn hơi khác trong công thức trên 1 chút do hơi khó biểu diễn khi viết blog) được tính là phân bố Dirichlet của β. Nghĩa là với K topic, ta sẽ có K phân bố trên vocabulary, và   đại diện cho phân bố của các term trên 1 topic

$$
{\displaystyle \theta } được tính là phân bố Dirichlet của α. Do đó ta sẽ có ||D|| phân bố trên các topic, và  đại diện cho phân bố của các topic trên 1 document

Tiếp theo đó, Zi được tính là phân bố Mutinomial (trong công thức biểu diễn là Discrete) của , lúc này Zi là chỉ số của topic của từ thứ i trong document d. Ví dụ Zi = 1 tức là từ thứ i trong document d thuộc về topic thứ 1.

Wi cũng tương tự nhưng được tính bởi , Wi là từ thứ i trong vocabulary. Ví dụ từ thứ 5 trong vocab là "cat" thì W5 sẽ là "cat"

Quá trình trên hay còn được biểu diễn như sau:

Posterior Inference

Ta cũng có thể biểu diễn LDA như sau:

Tuy nhiên, ta không thể tính toán với công thức trên được vì p(w|α, β) không thể tính toán được một cách chính xác. Ta phải dùng công thức xấp xỉ để có thể giải được công thức này, một trong số đó là Gibbs Sampling.

Với công thức xấp xỉ này, ta có thể tính xác suất xấp xỉ như sau:

Ở đây ta đang tính xác suất để từ có vị trí thứ i trong 1 document thuộc topic k, lưu ý rằng ta sẽ phải tính xác suất này cho tất cả các topic k thuộc K.

Tôi tham khảo ở đây:

http://www.ccs.neu.edu/home/vip/teach/DMcourse/5_topicmodel_summ/notes_slides/sampling/darling-lda.pdf

[Python Programming] Các kiểu dữ liệu thường dùng trong Python

Khi mới bắt đầu làm việc với Python, bởi vì Python là một ngôn ngữ rất mạnh trong việc biểu diễn số liệu do đó kiểu dữ liệu trong Python cũng phức tạp hơn nhiều so với các ngôn ngữ khác, nên tôi nghĩ việc viết một bài về các kiểu dữ liệu vừa là để giúp bản thân ghi nhớ các kiểu dữ liệu cho đỡ mất công đọc lại mỗi khi làm việc, vừa giúp tôi hiểu rõ hơn về các kiểu dữ liệu này.

Đầu tiên là tuple:
Tuple: Tuple là kiểu dữ liệu thường dùng trong python có kiểu đánh index giống với list nhưng khác với list là các phần tử trong Tuple không thay đổi được còn List lại thay đổi được. Ngoài ra tuple được biểu diễn bởi () chứ không phải [] như list
thistuple = ("apple", "banana", "cherry")

List: Xem Tuple để hiểu về List
thislist = ["apple", "banana", "cherry"]

Set: Set là kiểu dữ liệu không thể index và sắp xếp. Các phần tử trong set là unique. Ta có thể thay đổi nội dung của set
thisset = {"apple", "banana", "cherry"}

Dataframe - pandas: Đây là một kiểu dữ liệu mà python thừa kế từ ngôn ngữ R, gồm các hàng và các cột như một ma trận nhưng cách index lại khác.

Dictionary: thisdict = {
  "brand": "Ford",
  "model": "Mustang",
  "year": 1964
}

Bao gồm key và value

Thiểm Tây - Trung Quốc 2018