11. Hidden Markov Model HMMs

Mở đầu

Hidden Markov Model (HMMs)

Mục đích: thường dùng để dự đoán các phần chưa biết của state dựa vào observer hoặc ngược lại (reforcement learning?)

Trước đây, model này thường chỉ dùng cho speech processing

Key unsupervised learning algorithm: the Forward-Backward algorithm

Markov chain: dự đoán tương lai mà chỉ dựa vào các điều kiện đều ở hiện tại, không dựa vào bất cứ gì khác (không xét quá khứ)

Ví dụ:

- Dự đoán mai mưa nắng dựa vào hôm nay

- Dự đoán chữ tiếp theo trong câu dựa vào chữ hiện tại

Vì chỉ quan tâm giá trị gần nhất nên

Hidden: các giá trị không được label rõ ràng

-> Hidden Markov Model : nói về cả observed events và hidden events để xây dựng nên yếu tố nhân quả cho model xác suất

Mô hình dựa vào 2 giả thiết:

- Chỉ phụ thuộc vào bước trước đó

- Xác xuất 1 đầu ra chỉ phụ thuộc trạng thái tạo ra nó

Từ đó, dẫn đến 3 bài toán liên quan đến HMMs

1. Likelihood Computation: The Forward Algorithm

Giả sử ta biết thời tiết, dự đoán số kem Jason sẽ ăn

Chi tiết hơn, khi ta có dữ liệu Jason ăn 3, 1, 3 kem với thời tiết hot, hot, cold

Áp dụng

Vậy:

=> Forward algorithm: ( O(N^2*T)) (dynamic programming) dùng table để lưu trữ các giá trị trung gian (thành phần tọa xác suất observation). Thuật toán tính tổng xác suất của mọi trạng thái ẩn mà có thể dẫn đến observation, mỗi cái được biểu diễn là 1 single forward trellis

at(j) là xác suất state j sau khi qua t observation đầu tiên. Mỗi at(j) là tổng xác suất mọi path dẫn tới. qt = j tức là state thứ t là state j. Vì vậy:

Ví dụ tính 3 1 (H) ở state 2, có 2 path từ state 1, ta có 2 path: a1(1) x P(H|C) x P(1|H) và a1(2) x P(H|H) x P(1|H)

2. Decoding: The Viterbi Algorithm
Nhiệm vụ của Decoding là xác định những chuỗi (sequence) giá trí nào là nguyên nhân chính của observation. Ví dụ: có sequence 3 1 3, thì decoder tìm best hidden state sequence (H H H). Theo mặt toán học:

Cách làm là với mỗi hidden state sequence (HHH, HHC, HCH, ...), tính likelihood của nó với sequence observation đang xét rồi tìm max.

Tuy nhiên cách này có lượng tính toán quá lớn => Viterbi Algorithm

Viterbi algorithm: rất gống (minimum edit distance algorithm)

Là 1 dynamic programming algorithm theo kiểu đệ quy

Gần giống Forward algorithm chỉ đổi sum thành max, tuy nhiên có 1 điểm mới mấu chốt làm nên sự khác biệt ở backpointers. Lí do là ta cần quay lại điểm starting bằng best path (Viberbi backtrace)

3. HMM Training: The Forward-Backward Algorithm

Chúng ta chuyển bài toán parameters của HMM về 2 matrix A và B
Learning: chuỗi observation O và tập hidden state HMM, xác định các parameter trong matrix A và B
Forward-backward (Baun-Welch, special case of Expectation-Maximization (EM): (iterative algorithm) lặp đi lặp lại việc estimate xác suât.

- Ví dụ cơ bản nhất: toàn bộ weather và số ice-cream đều được hiện rõ -> Dễ tính được HMM parameters bởi maximum likelihood estimation:

- Tuy nhiên, trong những trường hợp khác (not full visible), ta không biết rõ path nào đã được sử dụng.

+ Nếu chỉ missing 1 day, ta có thể dựa vào tối ưu model Bayesian arithmetic để tính.

+ Nhưng nếu ta không biết bất cứ một hidden state nào?

-> Baum-Welch: tính forward probability cho 1 observation -> chia probabilty cho tất cả các path liên quan. Dễ hiểu hơn, ta định nghĩa backward probability beta là xác suất xảy ra observations từ t+1 đến cuối, tại state i, lần t (automaton lambda)

Vậy ta có estimate cho weight aij:

Tức nếu ta biết aij trong từng trường hợp t cụ thể. Ta có thể tổng mọi t lại làm đáp số cho transition i -> j.

Mà (Naive Bayes): P(X,Y,Z)/P(Z) = P(X,Y|Z) và P(Y,Z) = P(Y|Z)P(Z)

Và

(Nhắc lại)

=> final equation:

total expected number of transitions from state i:

Để recomputing xác suất observation:

Với tập vk, ta có:

Vậy để re-estimate matrix transtition A và matrix observation B từ sequence O: có estimate trước của A và B (HMM parameters lambda = (A,B) -> forward-backward algorithm gồm 2 step: expectation (E-step) và maximization (M-step)