C ÁC VẤN ĐỀ LIÊN QUAN KHÁC

Chương 1 MÔ HÌNH MARKOV ẨN VÀ CÁC VẤN ĐỀ LIÊN QUAN

1.3. C ÁC VẤN ĐỀ LIÊN QUAN KHÁC

Phương pháp Monte carlo là một lớp các thuật toán để giải quyết nhiều bài toán thường gặp bằng cách sử dụng các số ngẫu nhiên, ngược lại với các thuật toán tất định.

Thuật toán Monte carlo là phương pháp tính bằng số hiệu quả cho nhiều bài toán liên quan đến nhiều biến số mà không dễ dàng giải đƣợc bằng các phương pháp khác. Hiệu quả của phương pháp này so với các phương pháp khác tăng lên khi số chiều của bài toán tăng.

Phương pháp Monte carlo thường được thực hiện lặp lại một số lượng lớn các bước đơn giản, song song với nhau, một phương pháp phù hợp cho máy tính. Kết quả của phương pháp này càng chính xác khi số lượng lặp các bước tăng.

Để hiểu hơn về phương pháp Monte carlo ta xét ví dụ sau.

Ví dụ 1.3.1.1. Mô phỏng phân phối đều trên 0,1

Sử dụng các hàm sinh ngẫu nhiên đã đƣợc cài đặt trên máy tính. Dù dùng bảng số ngẫu nhiên hay sử dụng các hàm sinh số ngẫu nhiên đƣợc cài đặt trên máy tính ta cũng lấy ra hoặc tính đƣợc liên tiếp các số ngẫu nhiên xi trong 0,1

với i1, 2, ,n.

Tần số các giá trị này rơi vào k khoảng nhỏ với độ dài bằng nhau 1

k đƣợc chia ra từ  0,1 là gần nhƣ nhau n

k

 

 

 . Với n lớn thì tần số đó càng sát gần n k . Vì vậy ta coi các giá trị phát sinh đƣợc là các thể hiện của biến ngẫu nhiên X tuân theo phân phối đều trên 0,1. Trong trường hợp cần mô phỏng biến Y phân phối đều trên a b,  ta có:

 

i i

y   a b a x

Chú ý rằng, để phát sinh các số ngẫu nhiên nhận giá trị nguyên 0,1, 2, , N chỉ cần áp dụng công thức

  1    

ar ar i 1 i

V Y n n v Y y  N x  .

14

1.3.2. Thuật toán EM (Expectation Maximization)

Mô hình Markov ẩn tuy đơn giản nhƣng vấn đề ở chổ khó ƣớc lƣợng các tham số trong mô hình. Trong luận văn này tôi trình bày thuật toán EM để ƣớc lƣợng tham số mô hình khi và chỉ khi biết đƣợc dãy kết quả có đƣợc từ việc quan sát. Giả sử ta có đƣợc dãy quan sát các trạng thái là x x1, 2, ,xn.

1.3.2.1. Kì vọng có điều kiện a) Tích phân Radon-Nikodym

Định nghĩa: ChoXL1 và M là một trường--con của . Nếu X không âm và khả tích thì chúng ta sử dụng Rando-Nikodym để suy ra sự tồn tại của một độ đo biến ngẫu nhiên M , đƣợc kí hiệu bởi E X M , đƣợc xác định nhƣ sau

A XdPAE X M dP  . (1.6) với mọi AM.

 

E X M đƣợc gọi là xác suất có điều kiện của X cho bởi M.

b) Bất đẳng thức Jensen

Cho ,F P,  là một không gian xác suất và G là một trường con của F. Giả sử :RR là lồi và X là một biến ngẫu nhiên khả tích sao cho  X

khả tích. Khi đó ta có

E X G  E X G. (1.7) c) Công thức Bayes có điền kiện

Cho ,F P,  là một không gian xác suất và GF là một trường-- con. Giả sử P là một độ đo xác suất nào đó liên tục tuyệt đối đối với P, và đạo hàm Radon-Nikodym dP dP/  . Khi đó nếu  là biến ngẫu nhiên khả tích bất kì P thì

.

E  G   (1.8) Trong đó

E G

E G

    

 

  nếu E G  0,

15

 0 nếu E G  0. 1.3.2.2. Hàm hợp lí log-likelihood

Thuật toán EM cung cấp một phương pháp số lặp đi lặp lại có thể được sử dụng để tạo ra một dãy  p ,p0 cho việc cập nhật ƣớc lƣợng ML của vector tham số . Trước hết chúng ta xét hàm log-likelihood sau

  log time .

E dP Y dP

       (1.9) Nhờ vào tính đơn điệu của hàm loga nên giá trị cực đại của   tương đương với giá trị cực đại của L  , trong đó L  là hàm likelihood được xác định nhƣ sau

  time .

L E dP Y

dP

    

 

Và MLE arg maxL 



 



 là ƣớc lƣợng likelihood cực đại của .

Giả sử Py kí hiệu sự hạn chế của P đến Ytime. Điều đó có thể đƣợc chứng minh nhƣ sau

,

y y time

dP dP

E Y

dP dP

 



 

   

  

 

Khi đó

     log yy log yy log yy ,

dP dP dP

dP dP dP

  



 

  

và

     log time .

E dP Y dP

 



  

  

 

Theo bất đẳng thức Jensen thì

     log time .

E dP Y

dP

 



  

  

 

16

Vì vậy, với mọi  , , ta nhận đƣợc

     Q , .

Khi đó, nếu và chỉ nếu    thì hàm log-likelihood đƣợc định nghĩa nhƣ sau

 ,  log time, time.

Q   E  Y (1.10)

với

, .

time

time

G

dP dP

 



  



1.3.2.3. Thuật toán

Thuật toán đƣợc bắt đầu với một tập tham số khởi điểm  0 , mỗi lần lặp của thuật toán EM bao gồm 2 bước sau

Bước 1. E-Step (Expectation step): bước này chúng ta sẽ tính kỳ vọng của hàm hợp lý log-likelihood.

Đặt    p và tính hàm giả log-likelihood

 ,  p   p log time,  p time .

Q    E    Y 

Bước 2. M-Step (Maximization step): ước lượng giá trị tham số để cực đại hóa các đại lƣợng ở E-step.

Tìm p1argmax Q   ,  p .

(1.11) Lặp lại từ E-step với p p 1, đến khi điều kiện dừng ở (1.11) đƣợc thỏa mãn thì thuật toán kết thúc.

17