Thuật toán Simulated Annealing để tránh local minima

Trong các bài toán, ví dụ ta sử dụng k-means algorithm trong clusering, ta sẽ rất dễ bị local minima, dẫn đến thuật toán có thể converge nhưng không thể tìm ra giá trị tốt nhất.

Annealing xuất phát từ thuật ngữ là quá trình hình thành của pha lê (crystal formation process). Cụ thể, nhiệt độ sẽ giảm một cách rời rạc (không liên tục) trong một thời gian dài, quá trình này gọi là quá trình làm lạnh, quá trình được tiếp tục cho đến khi pha lê được hình thành tại một nhiệt độ T cố định.

Bình thường, ta biểu diễn local minima(minimum) như sau:

Giả sử ta đang từ từ phải sang trái và đang tiến đên local minima, rõ ràng, khi ta chạm đến điểm này, ta có thể dừng lại, nhưng global minima mới là điểm cho ta kết quả tốt nhất. Khi đó, làm sao ta biết ta nên đi tiếp lên từ điểm local minima  để đến global minima hay không.

Việc quyết định này được quyết định bởi một xác suất p:

Thuật toán SA với k-means được trình bày như sau:
1. Khởi tạo một giá trị T ngẫu nhiên và k clusters ngẫu nhiên.
2. Lặp lạo cho đến khi T chạm điểm cực tiểu
- Lặp n lần:
     + Ta xáo đổi các phần tử của các cluster một cách ngẫu nhiên
     + So sánh error của tập cluster mới và tập cluster cũ. Nếu tập cluster mới là tốt hơn, ta sẽ dùng tập       cluster mới với xác suất là p.
- Giảm giá trị của T [T = 0.9T]
3. Dừng thuật toán và trả về bộ clusters

Ở công thức tính p trên ta thấy, khi T lớn, xác suất p sẽ lớn, do đó xác suất chuyển sẽ lớn và ngược lại khi T nhỏ.

[Natural Language Processing] Giới thiệu về RNN trong xử lý ngôn ngữ tự nhiên

RNN là một biến thể của mạng neuron (Neraul Network) trong đó ta có thể xử lý các chuỗi dữ liệu liên quan tới nhau ví dụ trong các ứng dụng như nhận dạng giọng nói, mô hình hóa ngôn ngữ, dịch ngôn ngữ hay viết tiêu đề cho ảnh tự động.

Ta có thể thấy tại mỗi bước của RNN, chúng đều sử dụng chung tham số U (ma trận trọng số cho input), W (ma trận chuyển trạng thái) và vocabulary V. Ta thấy rằng, mỗi state sẽ phụ thuộc vào kết quả của state trước đó, nhưng việc ta xử lý 1 chuỗi dữ liệu dài trong thực tế là rất khó.

Do đó, ta sẽ phải sử dụng các kiến trúc khác nhau là biến thể của RNN ví dụ như LSTM để giải quyết vấn đề này.

Để hiểu rõ hơn, ta có ví dụ như sau:

Trong ví dụ này, V là [h,e,l,o] gồm 4 phần tử mà training sequence của ta là từ "hello". Khi này, với một kí tự ví dụ như 'h', ta thu được đầu ra là từ 'e', từ 'e' này lại là đầu vào để dự đoán từ tiếp theo trong chuỗi. Quá trình này kết thúc, ta thu được từ 'hello'.

Hình dưới đây thể hiện rõ hơn quá trình hoạt động của RNN.

Trong hình trên, Lt-1, Lt và Lt+1 là thứ tự của các layer.

Output của trạng thái trước sẽ là input của trạng thái sau, ví dụ như Ot-1 sẽ tương ứng với xt.

[Natural Language Processing] Embeddings

Embedding of Words

Word2Vec ta có 2 phương pháp:


- Skip-gram: Từ 1 word trong câu (target word), dự đoán các context word xung quanh từ đó.

- CBOW (Continuous Bag of Words): Từ các context word, dự đoán target word.

Embeddings of Sentences and Paragraphs

PV (Paragraph Vector): Từ một đoạn text có chiều dài cố định là k, ta chuyển thành một vector có số chiều nhất định với unsupervised learning.

Ta có 2 phương pháp để tìm ra PV.

- PV - DM (Distributed Memory):

- PV - DBOW (Distributed Bag of Words): 

[Natural Language Processing] Word2Vec sử dụng Skip-Gram model

Trong Skip-Gram model, ta sử dụng một hidden layer cho mạng neuron, nhưng khác với các mô hình khác khi mà mục tiêu của ta là đầu ra của mạng neuron, trong Skip-Gram model, mục tiêu của ta là weights của hidden layer đó. Ta sẽ thấy rõ được mục tiêu của mô hình Skip-Gram dưới đây nhưng trước tiên ta cần nhắc lại một chút lý thuyết.

Trong mô hình Skip-Gram, input là một từ ở giữa 1 câu (input word), ta phải tìm kiếm những từ xung quanh từ này trong câu đó, giả sử câu là chưa biết, ta chỉ biết từ đó là ở giữa câu. Khi này, ta cần tính toán xác xuất cho tất cả các từ trong vocabulary để các từ đó nằm cùng trong câu với input word.

Lý thuyết thì nghe có vẻ lằng nhằng, hãy nhìn vào một ví dụ sau đây.
Input word là từ "Soviet", khi này, bằng trực giác, ta thấy rằng xác xuất cho từ "Union" hay "Russia" chắc chắn sẽ cao hơn những từ có vẻ không liên quan đến "Soviet" - input word như "watermelon" hay "kangaroo".

Để train mô hình Skip-Gram, ta đưa vào các cặp từ trong training documents. Ví dụ trong 1 document ta có câu sau: “The quick brown fox jumps over the lazy dog.” Khi này, và ta đang sử dụng cửa sổ có chiều dài là 2, với mỗi từ trong câu ta có các cặp như hình dưới đây để đưa vào mô hình cho việc training.

Ta thấy các cặp từ được trích xuất ra ở đây, và chúng sẽ là cơ sở cho việc lựa chọn đầu ra của Skip-Gram model. Ví dụ trong khi training, ta không có cặp (cat,boy), khi đó, xác suất để "boy" nằm xung quanh từ "cat" - input word sẽ là nhỏ.

Tiếp theo ta sẽ nói về weights, bản chất của Word2Vec là ta muốn biểu diễn một từ thành một vector với size cố định.

Ở hình dưới, input word là "ant" là một vector one-hot (ví dụ trong vocabulary có 10000 từ và từ ant nằm ở vị trí thứ 100), thì "ant" sẽ được biểu diễn là 1 vector 10000 phần tử và tất cả các phần tử đều là giá trị không ngoại trừ giá trị tại vị trí thứ 100 sẽ là 1. 

Như ta đã biết, đầu ra của mô hình này là các từ xung quanh từ "ant", và cá từ này cũng sẽ được biểu diễn bằng 1 vector one-hot với 1 xác suất đi kèm.

Ta lưu ý rằng ở đây ta sẽ có 2 ma trận trong số W1 (input - hidden layer) và W2 (hidden layer - output), và không có activation function cho hidden layer, nhưng output layer sẽ sử dụng softmax function.

Trong hình dưới, ta đang sử dụng 300 features (số features là không cố định và có thể tùy biến), do đó ma trận W1 sẽ có size là (1000x300), 10000 ứng với 10000 phần tử của input vector và 300 là số features. 300 features được Google sử dụng trong Google new dataset, số features này là một hyperparameter và chúng biến động với tập dữ liệu và ứng dụng khác nhau.

Đặc biệt, nếu ta nhìn vào 1 hàng của ma trận W1, đó sẽ là word vector ứng với 1 từ.

Do đó nếu "ant" ở vị trí thứ 100, thì hàng thứ 100 của vector màu xanh trên có size là 1x300 chính là biểu diễn dưới dạng vector của từ này trong vocabulary.

[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