Tìm đường dẫn đầu - k viterbi trong HMM

Question

Tôi cần viết một thuật toán tìm đường dẫn viterbi đầu trong một HMM (sử dụng thuật toán viterbi thông thường để tìm đường đi tốt nhất). Tôi nghĩ rằng tôi có thể cần phải lưu một danh sách V_t, N của kích thước k cho mỗi tiểu bang N có chứa các đường dẫn top-K mà kết thúc trong N nhà nước, nhưng tôi không chắc chắn như thế nào để theo dõi danh sách đó. bất kỳ ý tưởng nào? Cảm ơn

Answer 1

Chúng tôi có thể giải quyết vấn đề này với một số dịch vụ chăm sóc. Nó là dễ dàng nhất để xem bằng cách nhìn vào cấu trúc lưới mắt cáo của hmm:

Trong ví dụ này, trạng thái ẩn là 00, 01, 10, 11, biểu thị tập hợp bốn như S. Các quan sát là không được hiển thị, nhưng giả sử chúng là 0,1.

Giả sử chúng ta có Matrix chuyển đúng:

transition[4][4] 

thải xác suất:

emissions[4][2] 

Và xác suất ban đầu:

p[2] 

Vì vậy, mỗi cột thể hiện các trạng thái ẩn, và mục tiêu của Viterbi là tính toán trình tự trạng thái ẩn có khả năng nhất cho t anh ta quan sát. Bây giờ, hãy để alpha (i, t) = xác suất lớn nhất mà trình tự trạng thái ẩn nằm trong trạng thái i (i là một trong 00, 01, 10, 11), tại thời điểm t, tại thời điểm t là o_t (o_t là một của 0, 1). Hãy để quan sát đầu tiên được biểu thị o_1. Nó có thể được tính toán một cách hiệu quả như:

alpha(i, 1) = p[i] * emissions[i][o_1] 
alpha(i, t) = emissions[i][o_t] * max_{k in states} (alpha(k, t-1) * transition[k][i]) 

Để tìm ra con đường tốt nhất, chúng tôi tiếp tục con trỏ ngược trong alpha (i, t) bước, để tình trạng đó tối đa hóa chức năng tối đa trong ở trên. Cuối cùng, chúng tôi chỉ kiểm tra tất cả các alpha (i, T) và cho tôi ở các bang, và tìm cái nào là lớn nhất, sau đó theo nó trở lại để có được chuỗi trạng thái có khả năng nhất.

Bây giờ, chúng tôi cần mở rộng mục này để lưu trữ k-đường dẫn hàng đầu. Hiện tại ở mỗi alpha (i, t), chúng tôi chỉ lưu trữ một phụ huynh. Tuy nhiên, giả sử chúng tôi lưu trữ những người tiền nhiệm hàng đầu. Vì vậy, mỗi alpha (i, t) không chỉ tương ứng với một giá trị có khả năng nhất và nút mà nó chuyển đổi từ đó, nhưng một danh sách các nút k đầu nó có thể đã chuyển từ và giá trị của chúng theo thứ tự sắp xếp.

Điều này rất dễ thực hiện, thay vì làm tối đa, và chỉ lấy một nút trước, chúng tôi lấy k đầu trước và lưu chúng. Bây giờ đối với trường hợp cơ sở, không có nút trước nào để alpha (i, 1), vẫn chỉ là một giá trị duy nhất. Khi chúng tôi đến một cột tùy ý (nói t) và muốn tìm các đường dẫn top-k kết thúc tại một nút (i) trong cột đó, chúng ta phải tìm ra những người tiền nhiệm hàng đầu để đến và các đường dẫn đầu để lấy từ chúng. Điều này giống như chúng ta có vấn đề sau đây, ma trận, m, với kích thước 4 x, trong đó một hàng đại diện cho một trạng thái trước và m [trạng thái] biểu thị các xác suất k đầu cho các đường dẫn kết thúc ở đó. Do đó mỗi hàng của m được sắp xếp theo lớn nhất đến nhỏ nhất, vấn đề bây giờ trở thành tìm:

Best_K_Values(t, i) = Top K over all i,preceding_state,k (emissions[i][o_t] * m[preceding_state][k] * transition[preceding_state][i]) 

Bây giờ điều này có vẻ khó khăn nhưng mất một thời gian để hiểu được nó, chúng ta có thể giải quyết được k đầu từ vấn đề ma trận được sắp xếp sử dụng một đống trong O (4 log k) hoặc O (numStates log k) nói chung.

Xem biến thể nhỏ này Kth smallest element in sorted matrix, chỉ cần lưu ý rằng trong trường hợp của chúng tôi, các cột không được sắp xếp, nhưng ý tưởng vẫn áp dụng.

Nếu bạn vẫn đang đọc, hãy lưu ý rằng độ phức tạp tổng thể của phương pháp này là O ((numStates log k) * numStates * t) = O (numStates^2 * t * log k) (Tôi tin rằng đó là sự phức tạp chính xác).

Điều này có thể khó thực hiện, nhưng vui lòng cho tôi biết nếu bạn có bất kỳ câu hỏi nào hoặc tôi đã làm điều gì đó không chính xác.

Answer 2

Có tài liệu thực sự mở rộng về vấn đề này. Phải mất một số đào, nhưng tôi thấy điều này.

Danh sách Viterbi Decoding thuật toán với các ứng dụng

http://www.ensc.sfu.ca/people/faculty/cavers/ENSC805/readings/42comm02-seshadri.pdf