intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Máy học và mạng neural: Bài 5 - TS. Vũ Đức Lung

Chia sẻ: Ngocnga Ngocnga | Ngày: | Loại File: PDF | Số trang:28

Thêm vào BST
Báo xấu
112
lượt xem 21
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài 5 cung cấp những kiến thức về mô hình Markov ẩn (Hidden Markov Model). Các nội dung chính được trình bày trong chương này gồm có: Các khái niệm, ba bài toán cơ bản của HMM, thuộc tính Markov, thuật toán lan truyền xuôi,...và những nội dung khác.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Máy học và mạng neural: Bài 5 - TS. Vũ Đức Lung

  1. 07/08/2013 Máy học và mạng neural (Machine Learning and Neural Network) Giảng viên: TS. Vũ Đức Lung Email: lungvd@uit.edu.vn 1 Bài 05 – Mô hình Markov ẩn Hidden Markov Model 2 1
  2. 07/08/2013 Nội dung bài 04 – HMM  Các khái niệm  Thuộc tính Markov  Ba bài toán cơ bản của HMM  Thuật toán lan truyền xuôi  Thuật toán lan truyền ngược  Thuật toán lan truyền xuôi-ngược  Thuật toán Viterbi  Thuật toán Baum-Welch  Một số thuật toán khác  Ví dụ ứng dụng tổng hợp và nhận dạng giọng nói 3 Định nghĩa  Mô hình Markov ẩn (tiếng Anh là Hidden Markov Model - HMM) là mô hình thống kê trong đó hệ thống được mô hình hóa được cho là một quá trình Markov với các tham số không biết trước và nhiệm vụ là xác định các tham số ẩn từ các tham số quan sát được, dựa trên sự thừa nhận này. Các tham số của mô hình được rút ra sau đó có thể sử dụng để thực hiện các phân tích kế tiếp, ví dụ cho các ứng dụng nhận dạng mẫu. 4 2
  3. 07/08/2013 Tại sao dùng mô hình Markov ẩn? • Nhiều bài toán thực tế được biểu diễn dưới mối quan hệ nhân quả, nhưng chỉ quan sát được phần quả còn phần nhân thì ẩn. • HMM dùng để giải quyết các bài toán xác lập mối nhân quả cục bộ (Fragmentation, Classification, Similarity Search). 1 2 K … 5 Ứng dụng của mô hình Markov ẩn • Nhận dạng tiếng nói. • Nhận dạng chữ viết tay. • Xử lý ngôn ngữ thống kê. • Dịch máy. • Tin sinh học: – Khớp xấp xỉ nhiều chuỗi. – Tìm Motif. – Tìm kiếm tương tự. 6 3
  4. 07/08/2013 Thuộc tính Markov Một dãy trạng thái ngẫu nhiên gọi là có thuộc tính Markov nếu như xác suất chuyển sang trạng thái tiếp theo chỉ phụ thuộc vào trạng thái hiện tại và quá khứ. – Dãy chuyển trạng quan sát được → Xích Markov. – Dãy chuyển trạng không quan sát được → Mô hình Markov ẩn. 7 Chuỗi(Xích) Makov - N là số lượng trạng thái trong chuỗi Makov (ở đây N=5), mỗi trạng thái được đánh số từ (1..N) - St là trạng thái của hệ thống ở thời điểm t - aij là xác suất chuyển trạng thái với các tính chất sau : tổng tất cả a =1, aij >=0 - Aij=P[qt=j|qt-1=i] 8 4
  5. 07/08/2013 Ví dụ Mô hình biểu diễn thời tiết - Mưa : Trạng thái 1 - Mây : Trạng thái 2 - Nắng : Trạng thái 3 - Ma trận xác suất chuyển trạng thái Hỏi : Xác suất để thời tiết 4 ngày liên tiếp : Nắng, Mưa, Mây, Nắng là bao nhiêu? Trả lời : Dãy quan sát O là : (Nắng, Mưa, Mây, Nắng) P(O) = P[3,1,2,3] =P[3]. P[1|3]. P[2,1]. P[3,2] 9 =1 * a31 * a12 * a23 (P[j|i]=aij) Chuỗi(Xích) Makov  Ví dụ: mô hình Markov bậc 1:  Ví dụ: mô hình Markov bậc 2: 10 5
  6. 07/08/2013 Ví dụ một mô hình Makov ẩn  Giả sử tôi có một người bạn sống ở rất xa.  Hàng ngày chúng tôi gọi điện thoại cho nhau và anh ta kể cho tôi nghe anh ta đã làm gì trong ngày.  Người bạn tôi chỉ có 3 công việc mà anh thích làm là 1) đi dạo, 2) đi chợ và 3) dọn phòng.  Hiển nhiên là sự lựa chọn phải làm gì thì phụ thuộc trực tiếp vào thời tiết hôm đấy thế nào.  Như vậy, tôi không nhận được thông tin cụ thể về thời tiết nơi anh bạn tôi sống nhưng tôi lại biết về xu hướng chung.  Dựa vào lời kể của công việc hàng ngày của anh ta, tôi có thể đoán về thời tiết hôm đó. 11 Ví dụ một mô hình Makov ẩn  Thời tiết được vận hành như một chuỗi Markov cụ thể  Có 2 trạng thái thời tiết, "Mưa" và "Nắng", nhưng tôi không quan sát trực tiếp, do đó, chúng là ẩn đối với tôi  Dựa vào lời kể các hoạt động của anh bạn mà ta có thể dự đoán được thời tiết hôm đó là như thế nào. Toàn bộ quá trình này là một mô hình Makov ẩn. Lời kể các hoạt động của anh bạn là dữ liệu quan sát 12 6
  7. 07/08/2013 Ví dụ một mô hình Makov ẩn  trạng thái = ('Mưa', 'Nắng')  dữ liệu quan sát = ('đi dạo', 'đi chợ', 'dọn phòng')  khả_năng_ban_đầu = {'Mưa': 0.6, 'Nắng': 0.4}  khả_năng_chuyển_dịch = { 'Mưa' : {'Mưa': 0.7, 'Nắng': 0.3}, 'Nắng' : {'Mưa': 0.4, 'Nắng': 0.6}, }  khả_năng_loại_bỏ = { 'Mưa' : {'đi dạo': 0.1, 'đi chợ': 0.4, 'dọn phòng': 0.5}, 'Nắng' : {'đi dạo': 0.6, 'đi chợ': 0.3, 'dọn phòng': 0.1}, } 13 Ví dụ một mô hình Makov ẩn 14 7
  8. 07/08/2013 Ví dụ: nhận dạng tiếng nói 15 Ví dụ: nhận dạng tiếng nói 16 8
  9. 07/08/2013 Mô hình Markov ẩn - HMM • qt - Trạng thái ở thời điểm t. • S={1, 2,..., N} - Tập tất cả các trạng thái ẩn. • ot= (ký hiệu) Quan sát tại thời điểm t. • V={1,2, ...,M} Tập tất cả các ký hiệu quan sát được. • A= [aij] xác suất chuyển trạng thái. • B=[bij] xác suất nhả ký hiệu. = [i] xác suất khởi trạng 17 Tiến trình thực hiện của HMM 18 9
  10. 07/08/2013 Ba bài toán cơ bản của HMM Bài toán 1: (Evaluation problem) Cho dãy quan sát O=o1o2...oT và HMM -  hãy xác định xác suất sinh dãy từ mô hình – P(O| ). 19 Ba bài toán cơ bản của HMM q1 q2 b11 b23 b21 b12 b22 b13 o1 o3 o2 10
  11. 07/08/2013 Ba bài toán cơ bản của HMM Bài toán 2: (Decoding problem) Cho dãy quan sát O=o1o2...oT và HMM -  hãy xác định dãy chuyển trạng Q=q1q2...qT cho xác suất sinh O lớn nhất (optimal path). 21 Ba bài toán cơ bản của HMM q1 q2 b11 b23 b21 b12 b22 b13 o1 o3 o2 Ví dụ bài toán 2: (Bài toán giải mã – nhận dạng) Giả sử ta có dãy quan sát O = Walk, Shop, Walk, Clean … và HMM -  hãy xác định dãy chuyển trạng Q = Rainy, Sunny, Rainny … nào đó mà nó cho xác suất sinh dãy quan sát O lớn nhất (optimal path). 11
  12. 07/08/2013 Ba bài toán cơ bản của HMM Bài toán 3: (Learning problem) Hiệu chỉnh HMM -  để cực đại hoá xác suất sinh O – P(O| ) (tìm mô hình “khớp” dãy quan sát nhất. 23 Ba bài toán cơ bản của HMM q1 q2 b11 b23 b21 b12 b22 b13 o1 o3 o2 12
  13. 07/08/2013 Ba bài toán cơ bản của HMM Bài toán 1: (Evaluation problem) Tuy nhiên có NT dãy chuyển trạng 25 Thuật toán lan truyền xuôi 26 13
  14. 07/08/2013 Thuật toán lan truyền xuôi 27 Thuật toán lan truyền xuôi 28 14
  15. 07/08/2013 Thuật toán lan truyền xuôi Độ phức tạp thời gian: O(N2T) Độ phức tạp không gian: O(NT) 29 Ví dụ thuật toán lan truyền xuôi q1 q2 b11 b23 b21 b12 b22 b13 o1 o3 o2 a11 Rain Rain Rain a12 a21 Sun Sun Sun a22 B = [Bik]I,k walk clean shop 15
  16. 07/08/2013 Thuật toán lan truyền ngược Độ phức tạp thời gian: O(N2T) Độ phức tạp không gian: O(NT) 31 Thuật toán lan truyền xuôi-ngược 32 16
  17. 07/08/2013 Bài toán 2 - Thuật toán Viterbi 33 Thuật toán Viterbi – Giải quyết bài toán 2 • Ý tưởng chung: Nếu xác suất tốt nhất ở trạng thái cuối cùng qk=Sj có đi qua trạng thái qk-1=Si thì xác suất tại trạng thái qk-1=Si cũng phải tốt nhất qk-1 qk s1 a1j si aij sj a sN Nj • k(i) = max P(q1… qk-1 , qk= sj , o1 o2 ... ok) = maxi [ aij bj (ok ) max P(q1… qk-1= si , o1 o2 ... ok-1) ] • Sau khi chọn được xác suất tốt nhất ở vị trí cuối cùng qk=Sj thì quay lui lại để tìm được chuỗi Q cho ra xác suất sinh dãy quan sát O lớn nhất 17
  18. 07/08/2013 Thuật toán Viterbi 35 Thuật toán Viterbi 36 18
  19. 07/08/2013 Thuật toán Viterbi 37 Thuật toán Viterbi 38 19
  20. 07/08/2013 Thuật toán Viterbi 39 Ví dụ thuật toán Viterbi Bước 1 : Tại thời điểm t = 1 Tính tất cả xác suất các q sinh ra o1. Ở đây ta tính: q1 q2 P(q1|o1) hay là P (Rain|Walk) b11 b23 b21 P(q2|o1) hay là P (Sun|Walk) b22 b13 b12 Sau đó chọn xác suất cao nhất. Ở đây o1 o3 giả sử P(Sun|Walk) là max. o2 Bước 2 : Cũng tính tất cả xác suất q sinh ra o2 nhưng chỉ dựa vào xác suất a11 max của trạng thái ở bước 1. Rain Rain Rain Tiếp theo, làm tương tự cho tới bước a12 MAX thứ T. MAX a21 Cuối cùng, tại trạng thái ở thời điểm T MAX Sun a22 Sun Sun ta quay lui lại thì tìm được chuỗi Q có xác suât sinh ra O lớn nhất. B = [Bik]I,k Ở ví dụ này, chuỗi Q = Sun, Rain,… Sun walk clean shop có xác suất sinh ra chuỗi quan sát chuỗi O = Walk, Clean,… Shop là lớn nhất 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2