Tài liệu Nhận dạng tiếng nói việt nam từ vựng lớn

Nhận dạng tiếng nói Việt Nam từ vựng lớn Trang - i LỜI MỞ ĐẦU 1. Giới thiệu. Ngày nay, cùng với sự phát triển của ngành điện tử và tin học, các hệ thống máy tự động đã dần thay thế con người trong nhiều công đoạn của công việc. Máy có khả năng làm việc hiệu quả và năng suất cao hơn con người rất nhiều. Song cho đến nay, vấn đề giao tiếp người – máy tuy đã được cải thiện nhiều nhưng vẫn còn rất thủ công: thông qua bàn phím và các thiết bị nhập dữ liệu khác. Giao tiếp với thiết bị máy bằng tiếng nói sẽ là phương thức giao tiếp văn minh và tự nhiên nhất, dấu ấn giao tiếp người – máy sẽ mất đi mà thay vào đó là cảm nhận của sự giao tiếp giữa người với người, nếu hoàn thiện thì đây sẽ là một phương thức giao tiếp tiện lợi và hiệu quả nhất. Do có sự khác biệt về mặt ngữ âm giữa các ngôn ngữ nên ta không thể áp dụng các chương trình nhận dạng khác để nhận dạng tiếng Việt. Một hệ thống nhận dạng tiếng nói ở nước ta phải được xây dựng trên nền tảng của tiếng nói tiếng Việt. Vấn đề nhận dạng tiếng nói tiếng Việt chỉ mới được quan tâm nghiên cứu trong những năm gần đây và chưa có một chương trình nhận dạng hoàn chỉnh nào được công bố. Trên thế giới đã có rất nhiều hệ thống nhận dạng tiếng nói (tiếng Anh) đã và đang được ứng dụng rất hiệu quả như: Via Voice của IBM, Spoken Toolkit của CSLU (Central of Spoken Laguage Under-standing)… nhưng trong tiếng Việt thì còn rất nhiều hạn chế. 2. Mục tiêu của đề tài. Đề tài này nghiên cứu thử nghiệm một hướng nhận dạng tiếng nói - tiếng Việt Nam dựa trên việc trích đặc trưng của tiếng nói bằng phương pháp MFCC (Mel-Frequency Ceptrums Coefficients), và nhận dạng bằng mô hình HMM (Hidden Markov Models). Đồng thời, một mô hình điều khiển bằng tiếng nói – tiếng Việt được xây dựng với bộ từ vựng nhỏ, thiết lập hệ thống điều khiển bằng tiếng nói với một tập lệnh cố định. Tập lệnh này dùng để điều khiển chương trình, cụ thể là chương trình demo đọc số được thực hiện trong đề tài. Nhận dạng tiếng nói Việt Nam từ vựng lớn Trang - ii MỤC LỤC LỜI MỞ ĐẦU..........................................................................................................i 1. Giới thiệu. ............................................................................................................i 2. Mục tiêu của đề tài. .............................................................................................i LỜI CẢM ƠN.........................................................Error! Bookmark not defined. NHẬN XÉT ............................................................Error! Bookmark not defined. MỤC LỤC ..............................................................................................................ii DANH MỤC CÁC HÌNH .......................................................................................iv DANH SÁCH CHỮ VIẾT TẮT............................................................................... v CHƯƠNG 1: TỔNG QUAN VỀ NHẬN DẠNG TIẾNG NÓI .................................1 1.1 Giới thiệu..................................................................................................1 1.2 Công thức cơ bản ......................................................................................3 1.3 Các thành phần của một bộ nhận dạng tiếng nói........................................4 1.3.1 Xử lý cú âm ...............................................................................4 1.3.2 Mô hình cú âm ...........................................................................5 13.3 Mô hình ngôn ngữ.......................................................................5 1.3.4 Tìm kiếm giả định ......................................................................6 1.4. Mô hình Markov ẩn..................................................................................6 1.4.1 Giới thiệu chuỗi Markov ............................................................ 6 1.4.2 Cơ bản về mô hình Markov ẩn ...................................................8 1.4.3 Tìm chuỗi chuyển trạng thái tốt nhất - Thuật toán Viterbi ........13 1.4.4 Ước lượng các tham số xác suất cho HMM – Thuật toán BaumWelch 16 1.5. Biến đổi Fourier rời rạc. ......................................................................... 19 1.5.1 Giới thiệu.................................................................................19 1.5.2 Cơ bản về biến đổi Fourier rời rạc............................................20 1.5.3 Cửa sổ Hamming ..................................................................... 23 1.5.4 Biến đổi Fourier nhanh và thuật toán Butterfly:........................24 1.5.5 Cài đặt thuật toán biến đổi Fourier nhanh.................................28 CHƯƠNG 2 :HUẤN LUYỆN TIẾNG VIỆT NAM ...............................................30 2.1 Bộ từ điển Lexicom.................................................................................30 2.2 Dữ liệu ....................................................................................................31 Nhận dạng tiếng nói Việt Nam từ vựng lớn Trang - iii 2.2.1 Dữ liệu văn bản........................................................................31 2.2.2 Dữ liệu âm thanh......................................................................32 2.2.3 Tiếng ồn và nhiễu trong dữ liệu âm thanh ................................ 34 2.3 Huấn luyện tiếng Việt .............................................................................34 2.3.1 Chuẩn bị dữ liệu....................................................................... 34 2.3.2 Các bước trong quá trình học tiếng Việt ..................................38 CHƯƠNG 3: DEMO ĐỌC SỐ...............................................................................50 3.1.Chương trình demo đọc số liên tục..........................................................50 3.2.Zip City...................................................................................................50 CHƯƠNG 4: TẠO MODEL DÙNG CHO SPHINX-4 ...........................................53 4.1 Tạo model dùng cho sphinx-4. ................................................................ 53 4.2 Audio Tool.............................................................................................. 57 CHƯƠNG 5: KẾT QUẢ ĐẠT ĐƯỢC ...................................................................62 Nhận dạng tiếng nói Việt Nam từ vựng lớn Trang - iv DANH MỤC CÁC HÌNH Hình 1.1: Sơ đồ tổng quát hệ thống nhận dạng tiếng nói....................................2 Hình 1.2: Tổng quan về các thành phần chính trong nhận dạng tiếng nói..........2 Hình 1.3: Các thành phần cơ bản của một hệ thống nhận dạng tiếng nói............4 Hình 1.4: Mô hình HMM trái phải với 6 trạng thái ............................................8 Hình 2.3 Câu "tôi đi" khi đọc quá nhanh..........................................................33 Hình 2.4 Chữ “tôi” khi đọc ngân dài................................................................ 33 Hình 2.5 Câu “ba bốn bảy” thu âm bị ồn và nhiễu ...........................................34 Hình 3.1: Màn hình ban đầu của demo đọc số .................................................50 Hình 3.2:Màn hình sau khi nhận dạng một câu đọc số ..................................... 50 Hình 3.3: Màn hình ZipCity khi nhận dạng ..................................................... 52 Hình 4.1 Màn nhìn cấu hình ghi âm.................................................................58 Hình 4.2 Màn hình ghi âm...............................................................................59 Hình 4.3 Màn hình của player khi mới khởi động............................................60 Hình 4.4 Màn hình kiểm tra dữ liệu .................................................................61 Nhận dạng tiếng nói Việt Nam từ vựng lớn DANH SÁCH CHỮ VIẾT TẮT HMM Hidden Markov Model. FFT Fast Fourier Transform. Trang - v Nhận dạng tiếng nói Việt Nam từ vựng lớn Trang - 1 CHƯƠNG 1: TỔNG QUAN VỀ NHẬN DẠNG TIẾNG NÓI 1.1 Giới thiệu Nhận dạng tiếng nói là một quá trình nhận dạng mẫu, với mục đích là phân lớp. thông tin đầu vào là tín hiệu tiếng nói thành một dãy các tuần tự các mẫu đã được huấn luyện trước đó và đã được lưu vào trong bộ nhớ.Các mẫu là các đơn vị nhận dạng chúng có thể là các từ hoặc các âm vị. Nếu các mẩu này là bất biến và không thay đổi thì công việc nhận dạng thật đơn giản bằng cách so sánh dữ liệu tiếng nói cần nhận dạng với các mẩu đã được huấn luyện và được lưu trong bộ nhớ.Khó khăn cơ bản của nhận dạng tiếng nói là tiếng nói luôn biến đổi theo thời gian và có sự khác biệt lớn giữa tiếng nói của những người nói khác nhau, về tốc độ nói, ngữ cảnh và môi trường âm học khác nhau.Xác định những thông tin biến thiên nào của tiếng nói là có ích và những thông tin nào là không có ích đối với nhận dạng tiếng nói là rất quan trọng. Đây là một nhiệm vụ rất khó khăn mà ngay cả với các kỹ thuật xác suất thống kê mạnh cũng khó khăn trong việc tổng quát hoá từ các mẫu tiếng nói những biến thiên quan trọng cần thiết trong nhận dạng tiếng nói. Các nghiên cứu về nhận dạng tiếng nói dựa trên ba nguyên tắc cơ bản:    Tín hiệu tiếng nói được biểu diễn chính xác bởi các giá trị phổ trong một khung thời gian ngắn (short-term amplitude spectrum). Nhờ vậy ta có thể trích ra các đặc điểm tiếng nói từ những khoảng thời gian ngắn và dùng các đặc điểm này làm dữ liệu để nhận dạng tiếng nói. Nội dung của tiếng nói được biểu diễn dưới dạng chữ viết, là một dãy các ký hiệu ngữ âm. Do đó ý nghĩa của một phát âm được bảo toàn khi chúng ta phiên âm phát âm thành dãy các ký hiệu ngữ âm. Nhận dạng tiếng nói là một quá trình nhận thức. Thông tin về ngữ nghĩa (semantics) và suy đoán (pragmatics) có giá trị trong quá trình nhận dạng tiếng nói, nhất là khi thông tin về âm học là không rõ ràng. Một hệ thống nhận dạng nói chung thường bao gồm hai phần: phần huấn luyện (training phase) và phần nhận dạng (recognition phase). “Huấn luyện” là quá trình hệ thống “học” những mẫu chuẩn được cung cấp bởi những tiếng khác nhau (từ hoặc âm), để từ đó hình thành bộ từ vựng của hệ thống. “Nhận dạng” là quá trình quyết định xem từ nào được đọc căn cứ vào bộ từ vựng đã được huấn luyện. Sơ đồ tổng quát của hệ thống nhận dạng tiếng nói được thể hiện trên hình 1.1 . Nhận dạng tiếng nói Việt Nam từ vựng lớn Trang - 2 Hình 1.1: Sơ đồ tổng quát hệ thống nhận dạng tiếng nói Để thuận tiện cho việc kiểm tra và đánh giá kết quả, từ sơ đồ trên chúng ta chia chương trình nhận dạng thành ba mô-đun riêng biệt:  Mô-đun 1: Thực hiện việc ghi âm tín hiệu tiếng nói, tách tiếng nói khỏi nền nhiễu và lưu vào cơ sở dữ liệu.  Mô-đun 2: Trích đặc trưng tín hiệu tiếng nói đã thu ở mô-đun 1 bằng phương pháp MFCC, đồng thời thực hiện ước lượng vector các vector đặc trưng này.  Mô-đun 3: Xây dựng mô hình Markov ẩn với 6 trạng thái, tối ưu hóa các hệ số của HMM tương ứng với từng từ trong bộ từ vựng, tiến hành nhận dạng một từ được đọc vào micro. Hình 1.2: Tổng quan về các thành phần chính trong nhận dạng tiếng nói Nhận dạng tiếng nói Việt Nam từ vựng lớn Trang - 3 1.2 Công thức cơ bản Trong phần này sẽ giới thiệu một số ký hiệu sử dụng và một số công thức cơ bản. Gọi A là tập hợp các cú âm để bộ nhận dạng dùng để xác định từ nào đã được nói. A là một chuỗi các kí tự trong bảng alphabet A: A = a1, a2, …, a m ai  A Gọi W = w1, w2, …, wn wi  W (1.1) (1.2) là một tập n chữ, những chữ này nằm trong một bộ từ vựng cố định cho trước. P(W|A) là xác suất để tập chữ W được nói khi chuỗi cú âm quan sát được là A. Từ tập chữ W bộ nhận dạng sẽ xác định một chuỗi chữ tốt nhất Ŵ để cho ra chuỗi quan sát là A, tức là: Ŵ = argmaxWP(W|A) (1.3) Theo công thức Bayes ta có: (1.4) Trong đó P(W) là xác suất để chuỗi W được nói, P(A|W) là xác suất quan sát được A khi đọc chuỗi W, và P(A) là xác suất trung bình A được quan sát. P(A) được tính theo công thức: (1.5) Vì A là cố định nên từ (1.3) và (1.5) ta có: Ŵ = argmaxWP(W)P(A|W) Theo công thức 1.6 thì bài toán nhận dạng tiếng nói (nhận ra chuỗi từ Ŵ) chính là phải xác định được các xác suất P(W) và P(A|W). P(W) được tính thông qua mô hình ngôn ngữ, còn xác suất P(A|W) được tính thông qua mô hình cú âm. Ngoài ra còn một số công thức về xác suất khác: (1.6) Nhận dạng tiếng nói Việt Nam từ vựng lớn Trang - 4 P(x, y|z) = P(x|y, z)P(y|z) (1.7) Công thức Bayes: (1.8) 1.3 Các thành phần của một bộ nhận dạng tiếng nói Hình 1.3: Các thành phần cơ bản của một hệ thống nhận dạng tiếng nói. Ở phần 1.1 đã giới thiệu một quá trình nhận dạng tiếng nói, phần này sẽ giới thiệu về bộ nhận dạng tiếng nói trong quá trình đó. Về cơ bản thì bộ nhận dạng tiếng nói gồm hai phần: xử lý cú âm và giải mã. Trong đó bộ giải mã được cài đặt nhiều thành phần khác nhau. Trong phần này sẽ giới thiệu về mô hình cú âm, mô hình ngôn ngữ và tìm kiếm giả định. 1.3.1 Xử lý cú âm Công việc đầu tiên của một bộ nhận dạng tiếng nói là xác định dữ liệu cú âm được quan sát A. Bộ phận làm việc này gọi là front end, front end sẽ chuyển đổi âm thanh (dưới dạng sóng) thành các ký tự ai. Việc xử lý tín hiệu âm thanh liên quan nhiều đến lĩnh vực vật lý và sẽ không được nói sâu trong phạm vi của đế tài. Nhận dạng tiếng nói Việt Nam từ vựng lớn Trang - 5 1.3.2 Mô hình cú âm Quay trở lại công thức 1.6, bộ nhận dạng cần phải tính được P(A|W) là xác suất khi người nói nói chuỗi từ W thì bộ phân tích cú âm phân tích được chuỗi cú âm A. Để phục vụ công việc nhận dạng, chúng ta cần phải tính P(A|W) của tất cả các cặp A, W có thể. Điều này khó có thể thực hiện được, vì số lượng rất lớn. Và nếu có tính hết được thì cũng rất khó có thể tìm kiếm được cặp A, W phù hợp. Vì vậy để tính P(A|W) chúng ta cần một mô hình xác suất cú âm của chuỗi từ mà người nói đã nói. Số lượng mô hình phụ thuộc vào cách mà người nói nói chuỗi từ đó, vào nhiễu (tiếng ồn, tiếng vọng …), vị trí và các đặc tính của microphone, và việc xử lý cú âm của front end. Mô hình cú âm được sử dụng rộng rãi nhất trong các bộ nhận dạng tiếng nói hiện nay là mô hình Markov ẩn (HMM), sẽ được thảo luận ở chương tiếp. Ngoài ra còn nhiều loại mô hình khác, chúng có thể dựa vào thuật toán mạng nơron (artificial neural networks) hoặc thuật toán qui hoạch động (dynamic time warping). Những phương pháp này không được đề cập tới trong đề tài. 13.3 Mô hình ngôn ngữ Công thức 1.6 cũng yêu cầu phải tính xác suất các chuỗi chữ W để tìm ra chuỗi chữ có xác suất tốt nhất mà người dùng muốn nói chuỗi chữ W. Công thức Bayes cho phép có nhiều cách khác nhau để phân tích P(W). Nhưng bởi vì bộ nhận dạng muốn truyền đạt chuỗi văn bản một cách “tự nhiên” như những gì con người nói, vì thế chúng ta sử dụng cách phân tích: (1.9) Bộ nhận dạng phải ước lượng xác suất P(wi|w1,…, wi-1). Chúng ta phải ước lượng bởi vì dù với một giá trị n vừa phải và kích thước từ vựng hợp lý, thì xác suất P(wi|w1,…, wi-1) có rất nhiều đối số. Nhận dạng tiếng nói Việt Nam từ vựng lớn Trang - 6 Tuy nhiên, thật là vô lý nếu cho rằng việc lựa chọn chữ thứ i của người nói phụ thuộc vào tất cả i-1 chữ trước trong toàn bộ những lời mà anh ta đã nói. Vì vậy, chúng ta sẽ cho những chữ trước vào các lớp tương đối Ф(wi|w1,…, wi-1), công thức 1.9 trở thành: (1.10) Sự khác biệt giữa các mô hình ngôn ngữ khác nhau chính là việc xác định Ф phù hợp và một phương pháp để ước lượng P(wi| Ф(w1,…, wi-1)). Việc xây dựng mô hình ngôn ngữ chỉ phụ thuộc vào bộ văn bản sử dụng, hoàn toàn không phụ thuộc vào tiếng nói (không phụ thuộc vào việc ghi âm cho học). 1.3.4 Tìm kiếm giả định Cuối cùng, trong công thức 1.6, để tìm chuỗi chữ mong đợi chúng ta cần phải tìm trong tất cả các chuỗi chữ W có thể để tìm ra chuỗi có xác suất tốt nhất. Chúng ta không thể tìm kiếm vét cạn vì số chuỗi chữ W cần tìm kiếm rất lớn. Chúng ta cần phải tìm kiếm giả định, không xem xét toàn bộ các chuỗi chữ W mà chỉ khảo sát các chuỗi chữ được gợi ý bởi mô hình cú âm A. Hiện nay có nhiều cách để cài đặt tìm kiếm giả định. Trong chương 5 sẽ giới thiệu về phương pháp tìm kiếm Viterbi, và tìm kiếm theo cây. 1.4. Mô hình Markov ẩn. 1.4.1 Giới thiệu chuỗi Markov Như đã đề cập trong phần trên, mô hình cú âm tính xác suất P(A|W) dựa vào mô hình HMM. Mô hình này không chỉ hữu dụng trong nhận dạng tiếng nói mà còn trong nhiều lĩnh vực khác. Trước khi áp dụng nó vào trong mô hình cú âm , chúng ta sẽ xem xét khái niệm tổng quát về mô hình HMM. Trước hết là về chuỗi Markov ẩn. Gọi Q1, Q2, …, Qn, … là một chuỗi các biến ngẫu nhiên có giá trị được lấy từ tập hữu hạn Q = {1, 2, …, c}. Theo Bayes ta có: Nhận dạng tiếng nói Việt Nam từ vựng lớn P(Q1,Q2,….Qn,)=  n i 1 Trang - 7 P (Qi | Q1, Q 2, ......, Qi  1) (1.11) Các biến ngẫu nhiên Q1, Q2, …, Qn, … gọi là chuỗi Markov, công thức 2.1 gọi là công thức của chuỗi Markov. Mỗi biến trong chuỗi gọi là một trạng thái. Tuy nhiên, nếu trong chuỗi Markov giá trị tại thời điểm t chỉ phụ thuộc vào giá trị của điểm liền trước nó tức là: P(Qi|Q1, Q2, …, Qi-1) = P(Qi|Qi-1) với mọi i (1.12) Thì cơng thức của chuỗi Markov 2.1 trở thành: P(Q1, Q2, …, Qn) =  n i-1 P(Q | Q ) i (1.13) i -1 Trong phạm vi nhận dạng tiếng nói thì chuỗi Markov luôn có tính chất trên và được gọi là giả thuyết First-order. Chuỗi Markov là đồng nhất, tức là: P(Qi = q’|Qi-1 = q) = P(q’| q) với mọi q, q’  Q (1.14) Ví dụ: cho chuỗi Markov: Q=ABCDECD Tương ứng vị trí i = 1 2 3 4 5 6 7 Thì P(Q4 = D|Q3 = C) = P(Q7 = D|Q6 = C) = p(D|C). p(q’|q) được gọi là hàm chuyển trạng thái và được biểu diễn bằng một ma trận c x c. Với mọi q  Q ta có: ; p(q’|q) ≥ 0, q’  Q Mỗi trạng thái đều có một xác suất đứng đầu chuỗi πi và: =1 Dựa vào các tài liệu tham khảo và những thông tin về các hệ thống nhận dạng đã xây dựng thành công chúng tôi thấy rằng: đối với nhận dạng tín hiệu tiếng nói Nhận dạng tiếng nói Việt Nam từ vựng lớn Trang - 8 thì mô hình HMM thường được chọn là mô hình trái phải (left-right) có từ 5 đến 6 trạng thái. Qua quá trình thử nghiệm, mô hình có 6 trạng thái cho kết quả tốt hơn nên trong chương trình của mình, các tác giả đã xây dựng một HMM với số trạng thái là 6, xem hình Hình 1.4: Mô hình HMM trái phải với 6 trạng thái Hình 1.4 là mô hình một chuỗi Markov sáu trạng thái (c = 6). Trên hình mỗi mũi tên cùng với xác suất gắn kèm biểu thị sự chuyển đổi giữa các trạng thái. Một số trạng thái không có xác suất chuyển qua trạng thái khác, ngầm hiểu là a(1|1) = a(2|2) = a(3|3) = a(4|4) =a(5|5) =a(6|6) = 0. 1.4.2 Cơ bản về mô hình Markov ẩn Để mở đầu phần này chúng ta xét một ví dụ sau đây: Giả sử chúng ta có một chuỗi Markov gồm ba trạng thái: nắng, mưa và nhiều mây, là ba trạng thái thời tiết. Thời tiết của mỗi ngày chỉ có thể là một trong ba trạng thái trên. Cho ma trận xác suất chuyển trạng thái như sau: q1 q2 q3 q1 1/3 1/3 1/3 A= q2 1/4 1/2 1/4 Nhận dạng tiếng nói Việt Nam từ vựng lớn q3 1/4 1/4 Trang - 9 1/2 q1 = nắng, q 2 = nhiều mây, q3 = mưa. Với aij = p(qj|qi) là xác suất chuyển trạng thái từ i sang j. Giả sử ngày đầu tiên là nắng (π1=1), ta có xác suất xuất hiện của chuỗi “q1q 2q3” (nắng-nhiều mây-mưa) là: p(q2| q1)* p(q 3| q2)= 1/3*1/4 = 1/12. Nhiệm vụ của chuỗi Markov đến đây là hết, nó cho phép tính xác suất của một chuỗi sự kiện nào đó. Tuy nhiên chúng ta cần nhiều hơn thế. Bây giờ, giả sử mỗi ngày một người chỉ làm một trong ba việc: mua sắm, đi dạo và dọn dẹp. Tùy vào thời tiết trong ngày mà người này sẽ làm công việc phù hợp. Cho ma trận xác suất người này làm một công việc nào đó tương ứng với thời tiết trong ngày: x1 x2 x3 q1 1/3 1/3 1/3 B= q2 1/4 1/2 1/4 q3 1/4 1/4 1/2 x1 = mua sắm, x2 = đi dạo, x3 = dọn dẹp. Với bij = p(xj|qi) là xác suất quan sát được xi khi ở trạng thái qi. Vấn đề đặt ra là: cho một chuỗi các công việc người này sẽ làm trong một số ngày liên tiếp, phải tìm ra chuỗi thời tiết phù hợp nhất cho những ngày đó. Một mô hình bao gồm chuỗi các trạng thái Q = q1, q2, …, qn tương ứng với các xác suất chuyển trạng thái, và chuỗi các kết quả X = x1, x2, …, xn tương ứng với các xác suất đầu ra như trên gọi là mô hình Markov ẩn (HMM). Kết quả đầu ra còn gọi là các quan sát. Mỗi mô hình HMM có một trạng thái ban đầu duy nhất. Sở dĩ gọi là “ẩn” bởi vì với một chuỗi quan sát cho trước, ta chưa biết được chuỗi trạng thái tương ứng là gì. Trong mô hình HMM thì: Công thức tính xác suất của một chuỗi quan sát X trong mô hình HMM M như sau: Nhận dạng tiếng nói Việt Nam từ vựng lớn Trang - 10 L(M ) P(q N , X n | M ) P(X|M)=  l 1 l 1 (1.15) Trong đó: L(M): tổng số trạng thái. N: chiều dài chuỗi quan sát. chuỗi quan sát từ a đến b. trạng thái q l tại vị trí n (ql sinh ra quan sát xn). Như vậy để tính P(X|M) cần phải xác định được các P( , |M). Hiện nay có hai cách tính là tính tổng và dùng xấp xỉ Viterbi. Phương pháp tính tổng: P(q N ,X n | M)=  L(M) P(q N ,X n-1 | M)P(qn ,xn | qn-1,X n-1,M) k=1 l l l 1 l k k Đặt = P( , (1.16) |M), ta có: αn(l | M)=  L(M)α (k | M)P(qn ,xn | q n-1,X n-1,M) k=1 n-1 l k 1 (1.17) Theo công thức 1.7 ta có: L(M) P(q n | qn-1,X n-1,M)P(x | q n ,qn-1,X n-1,M) P(q n ,xn | q n-1 ,M)= k=1 n k k l l l k 1 1 Trạng thái tại vị trí n chỉ phụ thuộc trạng thái tại vị trí n-1 nên: → Các quan sát cũng độc lập với các trạng thái trước nên: → Công thức 2.8 được viết lại: P(q n ,xn | q n-1 ,X n-1 ,M)= P(q n | q n-1 ,M)P(xn ,q n ,M) l k 1 l k l L(M) → αn(l | M)= k=1 α (k | M)P(q n | q n-1 ,M)P(xn ,qn ,M) n-1 l k l (1.19) (1.20) (1.18) Nhận dạng tiếng nói Việt Nam từ vựng lớn Trang - 11 Quay trở lại ví dụ thời tiết ở trên, chúng ta sẽ dùng phương pháp tính tổng để tính xác suất của chuỗi công việc X = {x1=“mua sắm”, x2=”đi dạo”, x3=”dọn dẹp”}. Ta có n=3, l=3, bảng sau tính các giá trị l=1 (“nắng”) : l=2 (“nhiều l=3 (“mưa”) mây”) n=1 (“mua a1(1) a1(2) a1(3) (“đi a2(1) a2(2) a2(3) (“dọn a3(1) a3(2) a3(3) sắm”) n=2 dạo”) n=3 dẹp”) Bảng 1.1 Bảng tính các giá trị α trong phương pháp tính tổng Vì chúng ta giả sử ngày đầu tiên luôn luôn là nắng nên a1(1) =1, a1(2) =0, a1(3) =0. a2(1) = [a2(1) *p(q1|q1) + a1(2) *p(q1|q2) + a1(3) *p(q 1|q3)]*p(x2|q1) = (1*1/3 + 0*1/4 + 0*1/4)*0.3 = 0.1 a2(2) = [a1(1) *p(q2|q1) + a1(2) *p(q2|q2) + a1(3) *p(q 2|q3)]*p(x2|q2) = (1*1/3 + 0*1/2 + 0*1/4)*0.7 = 7/30 a2(3) = [a1(1)*p(q3|q1) + a1(2)*p(q3|q2) + a1(3)*p(q 3|q3)]*p(x2|q3) = (1*1/3 + 0*1/4 + 0*1/2)*0.1 = 1/30 a2(1) = [a2(1)*p(q1|q1) + a2(2)*p(q1|q2) + a2(3)*p(q 1|q3)]*p(x3|q1) = (0.1*1/3 + 7/30*1/4 + 1/30*1/4)*0.1 = 1/100 a2(2) = [a2(1)*p(q2|q1) + a2(2)*p(q2|q2) + a2(3)*p(q 2|q3)]*p(x3|q2) = (0.1*1/3 + 7/30*1/2 + 1/30*1/4)*0.2 = 19/600 Nhận dạng tiếng nói Việt Nam từ vựng lớn Trang - 12 a2(3) = [a2(1)*p(q3|q1) + a2(2)*p(q3|q2) + a2(3)*p(q 3|q3)]*p(x3|q3) = (0.1*1/3 + 7/30*1/4 + 1/30*1/2)*0.8 = 13/150 Vậy P(X|M) =  L(M)  n ( L | M ) l=1 =  3  (l ) l 1 3 = 1/100 + 19/600 + 13/150 = 77/600 = 0.12833 Phương pháp xấp xỉ Viterbi: Với một mô hình HMM có số trạng thái lớn thì phương pháp tính tổng ở trên sẽ phải sử dụng rất nhiều phép nhân. Để khắc phục điều này người ta dùng phương pháp xấp xỉ Viterbi để biến các phép nhân thành tổng các log. Từ công thức 2.10 thay tổng bằng lấy max: (k | M)P(q n | q n-1 ,M)]P(xn | q n ,M) l k l (1.21) logα n (l | M)= max [logα (k | M)+ logP(q n | q n-1 ,M)] k n-1 l k (1.22) α n (l | M)= max[ α n-1 Lấy log hai vế ta được: Hay: -logαn (l | M)= min [-logα (k | M) - logP(q n | q n-1 ,M)] - logP(xn | q n ,M) k n-1 l k l (1.23) Áp dụng công thức này cho ví dụ ở trên ta có: log = max[log + logp(q1|q1) , log + logp(q1|q2) , log logp(q1|q3)] + log p(x2|q1) = max[log(1/3),-∞, -∞] + log0.3 = -1 Tương tự: log log = -0.63202, log = -1.33333, log = -1.47712. = -0.83099, log = -0.43024. Vậy: P(X|M) = E-1.33333 + E-0.83099 + E-0.43024= 0.56532. + Nhận dạng tiếng nói Việt Nam từ vựng lớn Trang - 13 1.4.3 Tìm chuỗi chuyển trạng thái tốt nhất - Thuật toán Viterbi Trong mô hình HMM nêu ở trên, nếu cho trước chuỗi quan sát X = x1, x2, …, xk, thì chuỗi trạng thái Q = q1, q 2, …, qk, nào là phù hợp nhất với nó (tương tự như ví dụ ở phần trước: cho một chuỗi các công việc người này sẽ làm trong một số ngày liên tiếp, phải tìm ra chuỗi thời tiết phù hợp nhất cho những ngày đó). Tức là phải tính: maxq1,q2,…,qkP(q1,q 2,…,qk,|x1,x2,…,xk,q0) Từ công thức 1.7 ta có: P(q1, q2, …, qk| x1, x2, …, xk, q0) = P(q ,q ,...,q ,| x ,x ,...,x | q ) 1 2 k 1 2 k 0 P(x ,x ,...,x | q ) 1 2 k 0 (1.24) Vì vậy phải tính: maxq ,q ,...,q 1 2 k P(q ,q ,...,q ,| x ,x ,...,x | q ) 1 2 k 1 2 k 0 P(x ,x ,...,x | q ) 1 2 k 0 đã biết nên ta cần tính: Vì maxq ,q ,...,q P(q ,q ,...,q ,| x ,x ,...,x | q ) k 1 2 k 0 1 2 k 1 2 Đặt: γi(q i) = maxq ,q ,...,q P(q ,q ,...,q ,qi | x ,x ,...,xi | q ) i-1 1 2 0 1 2 i-1 1 2 (1.25) thì max q  k (q ) chính là giá trị cần tính. Theo giả thuyết First-Order của mô hình HMM ta có: P(q1, q 2, …, qi, qi+1, …, qk, x1, x2, …, xi, xi+1, …, xk|q 0) = P(q1, q2, …, qi, x1, x2, …, xi|q0) P(q i+1, …, qk, xi+1, …, xk|qi) Nên: γi+1(q i+1) = maxq ,q ,...,q P(q ,q ,...,q ,qi ,q ,x ,x ,...,x | q ) i-1 i+1 1 2 i+1 0 1 2 i 1 2 Nhận dạng tiếng nói Việt Nam từ vựng lớn Trang - 14 = maxq ,q ,...,q [P(q ,q ,...,q ,qi ,x ,x ,...,xi | q )P(q ,x | qi )] 1 2 i-1 1 2 0 i+1 i+1 1 2 i |q ) =γi(q i) maxq ,q ,...,q P(q ,x i i+1 x+1 i 1 2 (1.26) Đây chính là công thức cho thuật toán Viterbi. Thuật toán Viterbi: Thuật toán Viterbi định nghĩa công thức đệ quy cho công thức 2.16, gồm các bước: 1 Khởi tạo: Xét γ0(q 0) = 1, γ0(q i) = 0 Với mọi i ≠ 0. 2. Lặp: Dùng công thức 2.16 tính γ1(q) cho tất cả các trạng thái q. γ1(q) = γ0(q’)maxq’P(x1,q|q’) = P(q, x1|q 0) Sau đó tính γ2(q) cho tất cả các trạng thái q. γ2(q) = γ1(q’) maxq’P(x2,q|q’) Chọn γ2(q’) = maxq γ2(q) để dùng cho bước lặp tiếp theo. Tiếp tục tính γi(q) cho tất cả các trạng thái q. Đánh dấu các trạng thái q’ thỏa mãn ở mỗi lần lặp. Nếu trong một lần lặp có nhiều trạng thái q thỏa mãn maxq’P(x2,q|q’) thì chỉ chọn một và loại bỏ hết các giá trị khác. 3. Kết thúc: Kết thúc khi lặp qua k bước, với k là chiều dài chuỗi quan sát. Chuỗi trạng thái đã được đánh dấu qua mỗi lần lặp chính là chuỗi trạng thái cần tìm. Nhận dạng tiếng nói Việt Nam từ vựng lớn Trang - 15 Ví dụ: Quay trở lại ví dụ thời tiết ở trên, bây giờ chúng ta sẽ áp dụng thuật toán Viterbi để xác định chuỗi thời tiết phù hợp nhất cho chuỗi công việc {“mua sắm”, “đi dạo”, “dọn dẹp”}. Chúng ta cùng xem lại hai ma trận hệ số của ví dụ: q1 q2 q3 q1 1/3 1/3 1/3 A= q2 1/4 1/2 1/4 q3 1/4 1/4 1/2 q1 = nắng, q 2 = nhiều mây, q3 = mưa. Với aij = p(qj|qi) là xác suất chuyển trạng thái từ i sang j. x1 x2 x3 q1 0.6 0.3 0.1 B = q2 0.1 0.7 0.2 q3 0.1 0.1 0.8 x1 = mua sắm, x2 = đi dạo, x3 = dọn dẹp. Với bij = p(xj|qi) là xác suất quan sát được xi khi ở trạng thái qi. Lưu ý rằng theo công thức 1.7: = P(qi+1|qi)P(xi+1|q i+1, qi) = ai(i+1)b(i+1)(i+1) Do giả sử ngày đầu luôn nắng nên: a01=1, a02 = 0, a03 = 0 γ1(1)=0.6 γ1(2)=0 γ1(3)=0 γ2(1)=0.6*1/3*0.3=0. γ2(2)=0.6*1/3*0.7=0. γ2(3)=0.6*1/3*0.1=0.