Nhận dạng tiếng nói & ứng dụng tích hợp với các phần mềm máy tính

i các phần mềm máy tính” làm đồ án của mình nhằm đạt các mục tiêu chính sau: Tìm hiểu về lĩnh vực xử lý tiếng nói; Nghiên cứu và tìm hiểu về ứng dụng nhận dạng tiếng nói; Xây dựng chương trình nhận dạng tiếng nói theo thời gian thực; Xây dựng chương trình tích hợp với các phần mềm máy tính. Xử lí tiếng nói là lĩnh vực rộng đã và đang từng bước được nghiên cứu và thử nghiệm trong thực tế. Nhờ sự nỗ lực của bản thân cùng sự giúp đỡ của gia đình, thầy cô và bạn bè tôi đã thực hiện các nội dung của đồ án theo đúng yêu cầu. Sau thời gian nghiên cứu, tìm hiểu và thực hiện, tôi xin trình bày bản báo cáo tổng hợp những lý thuyết liên quan và chương trình Demo nhận dạng tiếng nói và chương trình tích hợp với Excel. Trước tiên tôi xin gửi lời cảm ơn tới cha mẹ và những người thân đã luôn động viên và tạo điều kiện tốt nhất cho tôi học tập. Tôi cũng xin gửi lời cảm ơn tới các thầy cô giáo trong khoa Công nghệ thông tin I nói riêng và Học viện Công nghệ Bưu chính Viễn thông nói chung đã giúp đỡ, dìu dắt tôi trong những năm tháng học tập tại trường. Đặc biệt, tôi xin chân thành cảm ơn thầy giáo Ts.Nguyễn Quang Hoan người đã trực tiếp hướng dẫn trong thời gian tôi thực hiện đồ án tốt nghiệp. MỤC LỤC Trang DANH MỤC HÌNH VẼ Hình 11 Mô hình bài toán xử lý tiếng nói. 8 Hình 12 Các phần tử cơ bản của một hệ thống nhận dạng tiếng nói 10 Hình 13 Sơ đồ phân loại các hệ thống nhận dạng tiếng nói 11 Hình 14 Hệ thống nhận dạng tiếng nói theo phương pháp âm học-ngữ âm học 12 Hình 15 Tích hợp tri thức trong nhận dạng tiếng nói theo hướng từ dưới lên 17 Hình 21 Mô hình dự đoán tuyến tính của tiếng nói 22 Hình 22 Sơ đồ khối bộ tiền xử lý LPC trong hệ thống nhận dạng tiếng nói 26 Hình 23 Sơ đồ khối tính toán các hệ số MFCC 31 Hình 24 Sơ đồ khối thuật toán tách nhị phân 38 Hình 31 Ba mô hình Markov ẩn cho thí nghiệm tung đồng xu 43 Hình 32 Chuỗi thao tác tính toán biến trạng thái. 47 Hình 33 Thao tác tính 48 Hình 34 Các loại mô hình Markov ẩn . 53 Hình 51 Sơ đồ khối của chương trình chính 69 Hình 52 Giải thuật thu âm trong luồng nhận dạng tiếng nói 74 Hình 53 Giải thuật phát hiện tiếng nói 77 Hình 54 Sơ đồ khối phân tích Cepstral thông qua mã hóa dự đoán tuyến tính 80 Hình 55 Giải thuật tạo Codebook 82 Hình 56 Giải thuật lượng tử hóa vector 85 Hình 57 Thuật toán huấn luyện mô hình 86 Hình 58 Sơ đồ khối giải thuật nhận dạng 89 Hình 61 Giao diện tiếng Anh 91 Hình 62 Giao diện tiếng Việt 92 Hình 63 Hộp thoại tạo codebook mới 92 Hình 64 Hộp thoại huấn luyện mô hình 93 CÁC THUẬT NGỮ VIẾT TẮT Viết tắt Viết đầy đủ Dịch nghĩa ASR Automatic Speech Recognition Nhận dạng tiếng nói tự động CWT Continuos Wavelet Transform Biến đổi Wavelet liên tục DCT Discrete Cosin Transform Biến đổi Cosin rời rạc DFT Discrete Fourier Transform Biến đổi Fourier rời rạc FFT Fast Fourier Transform Biến đổi Fourier nhanh FIR Finite Impulse Response Bộ lọc đáp ứng xung hữu hạn HMM Hide Markov Model Mô hình Markov ẩn IDFT Inverse Discrete Fourier Transform Biến đổi Fourier rời rạc ngược LCT Local Cosin Transform Biến đổi Cosin cục bộ LPC Linear Prediction Coding Mã dự đoán tuyến tính MCI Media Control Interface Giao diện điều khiển truyền thông MFCC Mel Frequency Cepstral Coefficients Hệ số phân tích phổ tần Mel PC Personal Computer Máy tính cá nhân ROT Running Object Table Bảng chương trình đang chạy TTS Text To Speech Chuyển văn bản thành tiếng nói STE Short Time Energy Năng lượng ngắn hạn STFS Short Time Fourier Transform Biến đổi Fourier ngắn hạn WFT Windowed Fourier Transform Biến đổi Fourier cửa sổ ZCR Zero Crossing Rate Tỉ lệ vượt quá điểm không MỞ ĐẦU Trong thời đại công nghệ thông tin hiện nay, khi việc giao tiếp giữa người với máy, máy với máy… luôn luôn là vấn đề được quan tâm thì việc trao đổi thông tin bằng tiếng nói có một vai trò quan trọng. Máy tính ra đời đã giúp con người giải quyết công việc nhanh gọn và hiệu quả hơn. Tuy nhiên, các máy tính ngày nay chỉ nhận thông tin từ con người qua các thiết bị như: bàn phím, chuột, bút,.. Mặc dù tốc độ xử lý của máy tính ngày càng được cải thiện đáng kể song tốc độ tạo lập thông tin của các thiết bị này vẫn còn thấp. Con người mong muốn máy tính ngày càng mạnh hơn, thông minh hơn và một trong số các yêu cầu đó là máy tính trong tương lai phải tương tác với người sử dụng bằng tiếng nói tự nhiên. Đây sẽ là một bước tiến lớn nhằm nâng cao sức mạnh của máy tính, đồng thời cũng tăng tốc độ truyền đạt thông tin giữa máy tính và con người. Xử lý tiếng nói trở thành một trong những lĩnh vực quan trọng trong xu hướng phát triển công nghệ của xã hội hiện nay. Đặc biệt, khi công nghệ thông tin ngày càng phát triển thì các ứng dụng của xử lý tiếng nói ngày càng trở lên cấp thiết. Mục đích của những nghiên cứu trong lĩnh vực xử lý tiếng nói là làm cho việc tương tác giữa người và máy ngày càng hiệu quả và tự nhiên hơn. Hiện nay trên thế giới các công nghệ xử lý tiếng nói đã phát triển, các hệ thống ứng dụng xử lý tiếng nói đã được sử dụng ở nhiều nơi, độ chính xác của các hệ thống này ngày càng được cải thiện. Các ứng dụng của lĩnh vực xử lý tiếng nói rất phổ biến: nhận dạng tiếng nói, tổng hợp tiếng nói, xác thực người nói qua giọng nói và các thành tựu của chúng được áp dụng vào nhiều lĩnh vực trong thực tế. Ở Việt Nam vì nhiều lí do khác nhau nên xử lý tiếng nói còn chưa phát triển, chưa có nhiều kết quả được công bố, đồng thời các ứng dụng của xử lý tiếng nói chưa nhiều, tài liệu về xử lý tiếng nói viết bằng tiếng Việt chưa phổ biến. Lĩnh vực xử lý tiếng nói đã và đang tiếp tục được nghiên cứu, phát triển và các ứng dụng của nó ngày càng trở nên phổ biến và quan trọng. Vì vậy xử lý tiếng nói và các ứng dụng của nó đã trở thành đề tài được nhiều nhà nghiên cứu cũng như học sinh, sinh viên nghiên cứu và phát triển. Đồ án tốt nghiệp của tôi tập trung nghiên cứu ứng dụng nhận dạng tiếng nói trong thực tế, từ đó xây dựng một ứng dụng nhận dạng cụ thể (nhận dạng các con số) và ứng dụng nhận dạng tiếng nói vào một số phần mềm máy tính (ban đầu là nhập dữ liệu vào bảng tính Excel). Nội dung đồ án của tôi gồm các chương như sau: Chương 1: Tổng quan về nhận dạng tiếng nói Chương này giới thiệu tổng quan về xử lý tiếng nói, tập trung giới thiệu tổng quan về nhận dạng tiếng nói và các phương pháp nhận dạng đã được áp dụng trong thực tế. Chương 2: Quá trình tiền xử lý tiếng nói Chương này tập trung trình bày cơ sở lý thuyết của các thuật toán trong khâu tiền xử lý tiếng nói bao gồm: giải thuật phát hiện tiếng nói, hai phương pháp trích chọn đặc trưng LPC và MFCC; những lý thuyết cơ bản về lượng tử hóa vector, những thành phần cần thiết để thực hiện lượng tử hóa vector . Chương 3: Mô hình Markov ẩn (HMM) Chương này tập trung nói về lý thuyết mô hình Markov ẩn, những vấn đề cần phải thực hiện khi cài đặt mô hình Markov ẩn trong ứng dụng nhận dạng tiếng nói. Chương 4: Tích hợp với phần mềm máy tính Nội dung của chương này tập chung giới thiệu các phương pháp kết nối với bộ Office XP. Giới thiệu về mô hình đối tượng của Excel và việc trao đổi dữ liệu với Excel. Chương 5: Thiết kế chương trình Chương này tập trung vào công việc thiết kế của đồ án bao gồm các bước thiết kế và các thuật toán được cài đặt trong chương trình. Chương 6: Xây dựng chương trình và thử nghiệm Nội dung của chương sẽ giới thiệu về chương trình đã xây dựng cùng với một số kết quả được thống kê khi chạy thử nghiệm chương trình. Nội dung cụ thể từng chương sẽ lần lượt được trình bày trong các phần tiếp theo của đồ án. TỔNG QUAN VỀ NHẬN DẠNG TIẾNG NÓI GIỚI THIỆU VỀ XỬ LÝ TIẾNG NÓI Xử lý tiếng nói ngày nay đang là vấn đề được quan tâm nghiên cứu nhiều bởi khả năng ứng dụng trong nhiều lĩnh vực như: Công nghệ thông tin, Viễn thông, tự động hóa (chế tạo người máy có khả năng tương tác với con người)... qua đó giúp quá trình tương tác giữa người với máy trở nên hiệu quả và tự nhiên hơn. Quá trình xử lý tín hiệu tiếng nói là quá trình thu nhận, lưu trữ và truyền tín hiệu. Quá trình nhận dạng, tổng hợp tiếng nói hay xác thực người nói thông qua giọng nói là các ví dụ điển hình của quá trình xử lý tín hiệu tiếng nói. Mục đích của xử lý tiếng nói: Thực hiện xử lý, mã hoá một cách có hiệu quả tín hiệu tiếng nói để truyền và lưu trữ tiếng nói. Tổng hợp và nhận dạng tiếng nói tới giao tiếp người-máy bằng tiếng nói dựa vào các thông tin của quá trình tiền xử lý… Chúng ta có thể mô hình hóa cho bài toán xử lý tiếng nói như sau: Hình 11 Mô hình bài toán xử lý tiếng nói. Thông tin đầu vào là tín hiệu tiếng nói do con người phát ra dưới dạng tương tự, sau đó tín hiệu này được số hóa (rời rạc, lượng tử và mã hóa dạng nhị phân). Quá trình tiền xử lý tiếng nói tiến hành xử lý tín hiệu tiếng nói cho kết quả là các tham số của tín hiệu tiếng nói (Các hệ số MFCC và LPC). Các tham số này trở thành đầu vào đối với tất cả các ứng dụng của xử lý tiếng nói. Như vậy tất cả các ứng dụng của xử lý tiếng nói đều cần phải dựa trên các kết quả của quá trình tiền xử lý. Kết quả của quá trình này góp phần quyết định tính chính xác và hiệu quả của các ứng dụng. NHẬN DẠNG TIẾNG NÓI Khái niệm về nhận dạng tiếng nói Nhận dạng tiếng nói tự động là một kỹ thuật nhằm làm cho máy “hiểu” được tiếng nói của con người. Thực chất đây là một quá trình biến tín hiệu tiếng nói do người phát ra thành tín hiệu số sau đó sử dụng một số giải thuật để đối chiếu giữa tín hiệu thu được với các dữ liệu tham chiếu để xác định xem tín hiệu thu được tương ứng với dữ liệu tham chiếu nào trong bộ tham chiếu (từ điển nhận dạng). Kết quả của việc nhận dạng sau đó có thể được sử dụng trong các ứng dụng khác như nhập số liệu, soạn thảo văn bản bằng lời nói, điều khiển tự động… Mục tiêu của hầu hết các chương trình nhận dạng tiếng nói là kết quả nhận dạng đạt đến độ chính xác 100% mà không phụ thuộc vào một điều kiện nào cả. Tuy nhiên tất cả các nghiên cứu gần đây chỉ cho độ chính xác đến khoảng trên 90% trong một số điều kiện cụ thể nào đó còn những chương trình nhận dạng mà không có điều kiện giới hạn gì thì độ chính xác chỉ đạt không quá 87%. Các chương trình nhận dạng tiếng nói tự động hiện nay khá nhiều và hết sức đa dạng. Tuy nhiên chúng ta cũng có thể dựa vào một số đặc điểm để phân chúng thành một số dạng chủ yếu như: Nhận dạng các từ phát âm rời rạc/liên tục: Trong các chương trình nhận dạng các từ phát âm rời rạc yêu cầu người nói phải dừng một khoảng trước khi nói từ tiếp theo. Còn hệ thống nhận dạng các từ phát âm liên tục không yêu cầu điều kiện này: Nhận dạng tiếng nói độc lập/phụ thuộc người nói Đối với hệ thống nhận dạng phụ thuộc người nói đòi hỏi tiếng người nói phải có trong cơ sở dữ liệu của hệ thống còn hệ thống nhận dạng không phụ thuộc người nói thì người nói không nhất thiết phải có mẫu trước khi nhận dạng trong cơ sở dữ liệu. Nhận dạng với tử điển cỡ nhỏ/vừa/lớn: Hiệu năng của một hệ thống nhận dạng với từ điển cỡ nhỏ thường cao hơn hiệu năng của các hệ thống nhận dạng có từ điển cỡ vừa và lớn. Nhận dạng trong môi trường nhiễu cao/thấp: Hiệu năng của các hệ thống nhận dạng không nhiễu sẽ cao hơn hiệu năng của các hệ thống nhận dạng có nhiễu. Dưới đây là hình biểu diễn các phần tử cơ bản của một hệ thống nhận dạng tiếng nói. Hình 12 Các phần tử cơ bản của một hệ thống nhận dạng tiếng nói Tín hiệu tiếng nói sau khi được số hóa sẽ phân thành các khung có độ dài khoảng từ 10 đến 45ms qua bước phân tích và xác định các đặc tính sẽ cho ta một dãy các vector đặc tính của tiếng nói. Các vector này sau đó sẽ được sử dụng để tìm kiếm các từ giống nhất trong từ điển dựa trên một số điều kiện ràng buộc nào đó về mặt âm thanh, ngữ nghĩa, từ vựng… Do tính chất của tiếng nói phụ thuộc vào nhiều yếu tố nên việc thu nhận, phân tích các đặc trưng của tiếng nói là việc không dễ dàng. Ở đây, chúng ta có thể nêu ra một số yếu tố khó khăn cho bài toán nhận dạng tiếng nói: Khi phát âm, người nói thường nói nhanh chậm khác nhau. Các từ được nói thường dài ngắn khác nhau. Một người cùng nói một từ nhưng ở hai lần phát âm khác nhau thì cho kết quả phân tích khác nhau. Mỗi người có một chất giọng riêng được thể hiện thông qua độ cao của âm, độ to của âm, cường độ âm và âm sắc Những yếu tố như nhiễu của môi trường, nhiễu của thiết bị thu… Phân loại các hệ thống nhận dạng tiếng nói Nhận dạng tiếng nói được chia thành hai nhóm dựa trên mục đích sử dụng: Nhóm được sử dụng với mục đích điều khiển thiết bị thông qua giọng nói. Nhóm sử dụng nhằm xử lý từ tiếng nói sang văn bản. Phân loại các hệ thống nhận dạng tiếng nói sẽ giúp chúng ta có một cái nhìn trực quan hơn về bài toán. Các hệ thống nhận dạng được phân loại như hình vẽ 1.4 dưới đây. Hình 13 Sơ đồ phân loại các hệ thống nhận dạng tiếng nói Hiện nay, khả năng nhận dạng tiếng nói chưa thực sự đáp ứng được các yêu cầu của thực tế, song trong những năm gần đây những hệ thống nhận dạng tiếng nói đã có bước phát triển đáng kể. Trong một giới hạn nào đó thì bên cạnh bàn phím và con chuột, những phần mềm nhận dạng tiếng nói đã đóng vai trò như một bộ phận nhập dữ liệu vào các PC và một số thao tác điều khiển PC mà người dùng đòi hỏi. Như vậy, ta thấy được nhận dạng tiếng nói là lĩnh vực nghiên cứu quan trọng để phát triển và đưa các ứng dụng tự động vào nhiều ngành. Ngoài các yếu tố về công nghệ nhận dạng tiếng nói, thì do tiếng nói của mỗi dân tộc có những đặc thù riêng, đòi hỏi việc phân tích và tìm ra công nghệ phù hợp. Ở Việt Nam việc tìm nghiên cứu và phát triển các hệ thống nhận dạng tiếng nói còn đang ở bước đầu với rất ít các kết quả được công bố. Các phương pháp nhận dạng tiếng nói Như đã đề cập trong phần trên, hiện nay có ba phương pháp chủ yếu được sử dụng trong nhận dạng tiếng nói là: Phương pháp nhận dạng mẫu Phương pháp âm học-ngữ âm học Phương pháp ứng dụng trí tuệ nhân tạo Phương pháp âm học ngữ âm học Hướng tiếp cận âm học và ngữ âm học dựa trên lý thuyết về âm học-ngữ âm học. Theo lý thuyết này thì trong bất kỳ một ngôn ngữ nào cũng luôn tồn tại một số hữu hạn các đơn vị ngữ âm phân biệt và những đơn vị ngữ âm đó được đặc trưng bởi các thuộc tính vốn có trong tín hiệu tiếng nói, hoặc trong phổ của nó thông qua thời gian. Một hệ thống nhận dạng tiếng nói theo phương pháp âm học – ngữ âm học có thể mô tả bằng sơ đồ sau [9]: Hình 14 Hệ thống nhận dạng tiếng nói theo phương pháp âm học-ngữ âm học Nguyên lý hoạt động của hệ thống này như sau: Bước đầu tiên:Tín hiệu tiếng nói sau khi số hoá được đưa qua một bộ “đo” các đặc trưng của tiếng nói, mục đích là nhằm biểu diễn xấp xỉ các đặc tính của tiếng nói thay đổi theo thời gian. Bước này là cần thiết cho hầu hết các hệ thống nhận dạng theo các hướng tiếp cận khác nhau. Bươc thứ hai: Là bước tách các đặc tính của tiếng nói nhằm biến đổi các số đo phổ tín hiệu thành một tập các đặc trưng mô tả các đặc tính âm học của các đơn vị ngữ âm khác nhau. Các đặc trưng đó có thể là: Tính chất âm mũi, âm xát, vị trí các formant… Bước thứ ba: Là bước phân đoạn và gán nhãn. Ở bước này hệ thống nhận dạng cố gắng tìm các vùng âm thanh ổn định và gán cho mỗi vùng này một nhãn phù hợp với đặc tính của đơn vị ngữ âm. Đối với một hệ thống nhận dạng theo hướng âm học ngữ âm học thì bước này là tâm điểm và khó thực hiên nhất. Do đó có rất nhiều chiến lược đã được sử dụng để giới hạn phạm vi của các điểm phân đoạn và xác xuất gán nhãn. Bước cuối cùng: Từ các khối ngữ âm thu được sau bước phân đoạn và gán nhãn, người ta dựa vào một số nguyên tắc lựa chọn để kết hợp các khối ngữ âm này thành các từ, câu nhận dạng. Có rất nhiều vấn đề đối với một hệ thống nhận dạng tiếng nói theo hướng âm học ngữ - ngữ âm học những vấn đề này bằng nhiều cách khác nhau nó ảnh hưởng tới hiệu quả của một hệ thống nhận dạng theo hướng này. Những vấn đề đó là: Cần có sự hiểu biết về các đặc tính âm học của các đơn vị ngữ âm. Sự hiểu biết này không thể đầy đủ cho tất cả nhưng đối với một số trường hợp đơn giản thì có thể cho kết quả tốt. Sự chọn lựa các đặc trưng dựa của tiếng nói hầu hết tùy thuộc vào một khía cạnh cụ thể mà ta quan tâm. Chúng được chọn theo trực giác không tối ưu và đầy đủ ý nghĩa. Việc thiết kế của các hệ thống phân lớp âm thanh cũng không tối ưu và hầu hết nó đều dựa trên cây nhị phân quyết định… Không có một thủ tục tự động lựa chọn ngưỡng chính xác để làm căn cứ cho việc gán nhãn. Trên thực tế không có một phương pháp lý tưởng để gán nhãn cho tập huấn luyện. Từ đó, hướng tiếp cận âm học - ngữ âm học muốn áp dụng được vào thực tế cần phải có thêm nhiều nghiên cứu nữa. Phương pháp nhận dạng mẫu Phương pháp nhận dạng mẫu sử dụng trực tiếp mẫu tiếng nói mà không cần phải xác định các đặc trưng hay phân đoạn một cách rõ ràng. Trong hầu hết các hệ thống, nhận dạng mẫu bao gồm hai bước. Bước đầu tiên: là bước huấn luyện.Ở bước này dựa trên nhiều phiên bản khác nhau của mẫu cần nhận dạng hệ thống tạo ra các mẫu tham chiếu dùng để so sánh với mẫu cần nhận dạng ở bước sau. Bước thứ hai: là bước nhận dạng. Ở bước này mẫu cần nhận dạng được so sánh với các mẫu tham chiếu để xác định xem nó “giống” mẫu tham chiếu nào nhất. Mẫu tham chiếu giống nó nhất chính là kết quả nhận dạng. Tư tưởng của phương pháp này là nếu như có đủ các phiên bản khác nhau của mẫu cần nhận dạng thì thông qua bước huấn luyện hệ thống có thể xác định một cách chính các đặc trưng của mẫu. Việc xác định các đặc trưng thông qua bước huân luyện được gọi là phân lớp mẫu. Hiện nay, có hai phương pháp nhận dạng mẫu được sử dụng rỗng rãi đó là mô hình Markov ẩn và mạng Neural. Sơ đồ khối của một hệ thống nhận dạng mẫu như sau [9]: Hình 1.3 Hệ thống nhận dạng tiếng nói theo phương pháp nhận dạng mẫu Những bước cần thực hiện đối với một hệ thống nhận dạng mẫu là: Trích chọn các đặc trưng: Ở bước này dựa trên một số biện pháp phân tích để xác định các đặc trưng của các mẫu. Đối với các hệ thống nhận dạng tiếng nói có hai phương pháp cơ bản là phương pháp phân tích hệ số phổ theo thang độ Mel (MFCC) và phương pháp phân tích mã hóa dự đoán tuyến tính (LPC). Huấn luyện mẫu: Ở bước này, hệ thống dựa trên các đặc trưng của các mẫu trong cùng một lớp được tạo ra ở bước trước để tạo nên các mẫu tham chiếu của hệ thống. Ví dụ trong hệ thống nhận dạng từ, để xây dựng nên một từ tham chiếu chúng ta phải thu từ đó lặp đi lặp lại nhiều lần, sau đó trích chọn các đặc trưng của những từ này nhằm tạo một từ tham chiếu cho hệ thống. Phân lớp mẫu: Trong bước này, mẫu cần nhận dạng được so sánh với các mẫu tham chiếu. Ở đây, cần một thủ tục để tính khoảng cách cục bộ, và quy chuẩn thời gian giữa các mẫu. Quyết định logic: Sau bước phân lớp mẫu ta có được điểm đánh giá sự “giống” nhau giữa mẫu cần nhận dạng và mẫu tham chiếu. Những thông số điểm này sẽ được sử dụng để đưa ra quyết định là mẫu nào “giống” với mẫu cần nhận dạng nhất. Đặc điểm của một hệ thống nhận dạng mẫu: Hiệu năng của hệ thống rất nhạy cảm với số mẫu dữ liệu có trong tập huấn luyện. Thông thường, khi mà số mẫu có trong tập huấn luyện càng nhiều thì hiệu năng nhận của hệ thống càng cao. Mẫu tham chiếu rất nhạy cảm với môi trường thu âm và đặc tính của đường truyền do đặc tính phổ của tiếng nói chịu tác động của đường truyền và nhiễu nền. Không cần có những hiểu biết đặc biệt về ngôn ngữ chính vì vậy hệ thống này ít phụ thuộc vào kích thước từ điển, cú pháp và ngữ nghĩa. Khối lượng tính toán trong thủ tục huấn luyện hoặc nhận dạng tỷ lệ tuyến tính với số mẫu dùng huấn luyện hoặc nhận dạng. Phương pháp ứng dụng trí tuệ nhân tạo Phương pháp này là sự lai tạo của của hai phương pháp trên với mục đích khai thác tối đa ưu điểm của từng phương pháp. Phương pháp này điều chỉnh thủ tục nhận dạng theo cách mà con người sử dụng trí tuệ của mình trong việc quan sát, phân tích và cuối cùng đưa ra một quyết định dựa trên các thông số đặc trưng về âm học. Những kỹ thuật thường được sử dụng cùng với các phương pháp này là: Sử dụng hệ chuyên gia để phân đoạn và gán nhãn do đó bước chủ yếu và khó nhất được thực hiện đơn giản hơn so với một hệ thống nhận dạng chỉ dựa vào hướng tiếp cận âm học - ngữ âm học thuần tuý. Sử dụng mạng neural để học mối quan hệ giữa các đơn vị ngữ âm và tất cả các đầu vào đã nhận biết (bao gồm âm học, ngôn ngữ học, cú pháp, ngữ nghĩa…), sau đó sử dụng mạng này để nhận dạng. Mục đích của việc sử dụng hệ chuyên gia là nhằm tận dụng các nguồn kiến thức của con người vào hệ thống nhận dạng. Các nguồn kiến thức đó bao gồm: Kiến thức về âm học : Nhằm để phân tích phổ và xác định đặc tính âm học của các mẫu tiếng nói đầu vào. Kiến thức về từ vựng : Sử dụng để kết hợp các khối ngữ âm thành các từ cần nhận dạng. Kiến thức về cú pháp : Nhằm kết hợp các từ thành các câu cần nhận dạng. Kiến thức về ngữ nghĩa : Nhằm xác định tính logic của các câu đã được nhận dạng. Sự kết hợp các nguồn kiến thức phụ thuộc vào hệ chuyên gia mà hệ thống nhận dạng sử dụng. Có nhiều cách khác nhau để có thể kết hợp các nguồn kiến thức. Cách thông dụng nhất là xử lý từ dưới lên, trong đó các tiến trình ở mức thấp nhất (như trích chọn đặc trưng, giải mã ngữ nghĩa) được đặt trên các tiến trình cao hơn (như giải mã từ vựng, mô hình ngôn ngữ) theo một tiến trình tuần tự nhằm giảm việc xử lý trong mỗi tầng xuống mức nhỏ nhất có thể. Sơ đồ khối của phương pháp này như sau [9]: Hình 15 Tích hợp tri thức trong nhận dạng tiếng nói theo hướng từ dưới lên Chương này đã giới thiệu một cách tổng quan về xử lý tiếng nói và nhận dạng tiếng nói cùng các phương pháp nhận dạng đã được sử dụng. Nhận dạng tiếng nói là một ứng dụng quan trọng của xử lý tiếng nói đã được đưa vào nhiều lĩnh vực của đời sống. Một hệ thống nhận dạng bao gồm nhiều khâu và chi tiết từng khâu sẽ được trình bày chi tiết trong các chương sau. QUÁ TRÌNH TIỀN XỬ LÝ TIẾNG NÓI Trong các hệ thống phát triển ứng dụng của xử lý tiếng nói (nhận dạng, tổng hợp tiếng nói, xác thực người nói) có một bộ phận không thể thiếu là quá trình tiền xử lý tiếng nói. Nhiệm vụ chính của quá trình này: Phát hiện tiếng nói từ tín hiệu âm thanh thu nhận được Tiến hành phân tích và trích chọn đặc trưng của tiếng nói để loại bỏ những thông tin dư thừa chỉ giữ lại những thông tin cần thiết nhất của tiếng nói. Các giải thuật cụ thể trong quá trình tiền xử lý sẽ được trình bày sau đây. PHÁT HIỆN TIẾNG NÓI Một khâu mà bất cứ một hệ thống nhận dạng tiếng nói nào cũng cần phải có là khâu phát hiện tiếng nói [8]. Ở khâu này ta thực hiện công việc phân tách tín hiệu tiếng nói với thành phần khác. Một trong những nhân tố quan trọng nhất trong các giải thuật phát hiện tiếng nói là chọn tham số sử dụng để tách tín hiệu tiếng nói với các tín hiệu khác. Có ba tham số thường được dùng nhất hiện nay trong các giải thuật phát hiện tiếng nói: Năng lượng ngắn hạn, tốc độ đi qua điểm không, lượng thông tin. Năng lượng ngắn hạn Giả sử ta có tín hiệu tiếng nói x(n), khung mà ta cần nghiên cứu bắt đầu từ mẫu thứ n và có N mẫu trong khung đó khi đó hàm năng lượng ngắn hạn của tín hiệu tiếng nói được tính như sau: (2.1) trong đó là một hàm cửa sổ. Dạng thường sử dụng là cửa sổ hình chữ nhật có dạng như sau : (2.2) Một của sổ có độ rộng lớn tương đương một bộ lọc thông thấp băng hẹp, muốn năng lượng ngắn hạn phản ánh được biên độ ngắn hạn của tín hiệu thì phải dùng cửa sổ nhỏ. Muốn năng lượng ngắn hạn thay đổi kịp tốc độ biến đổi của các âm trong tiếng nói chúng ta phải dùng cửa sổ nhỏ, nhưng nếu quá nhỏ thì năng lượng ngắn hạn không phản ánh được năng lượng trung bình của tín hiệu. Tốc độ đi qua điểm không Tham số thứ hai là tốc độ đi qua điểm không của tín hiệu tiếng nói. Tốc độ đi qua điểm không là thông tin về tấn số tiếng nói, đặc biệt là tín hiệu băng hẹp. Nếu tỉ lệ này lớn thì tần số của tín hiệu tiếng nói lớn. Tham số này được tính như sau: (2.3) với sgn(x(n)) được định nghĩa như sau: (2.4) Lượng thông tin Gần đây trong một số hệ thống nhận dạng tiếng nói người ta có sử dụng tham số Entropy của tín hiệu tiếng nói trong việc phát hiện điểm đầu/cuối của tiếng nói. Việc áp dụng tham số này đã đem lại một hiệu quả nhất định dưới đây là cách tính tham số này. Để tính được Entropy của một khung tín hiệu tiếng nói ta cần thực hiện ba bước sau: Tính FFT Tín hiệu tiếng nói từ miền thời gian được chuyển sang miền tần số bằng cách thực hiện phép biến đổi Fourier. Công thức tính như sau: (2.5) Mật độ xác suất của phổ năng lượng Hàm mật độ phân bố xác suất phổ năng lượng của tín hiệu được tính như sau: i=1…..M (2.6) trong đó: s(fi) là phổ năng lượng của thành phần tần số fi M là số điểm tính FFT. Trước khi tính tiếp bước ba có một số thủ thuật được sử dụng nhằm tăng tính phân tách của hàm phân bố xác suất giữa tín hiệu tiếng nói và tín hiệu khác. (2.7) (2.8) Tính Entropy Sau khi tính được hàm phân bố xác suất của phổ năng lượng ta tính Entropy của tín hiệu theo công thức. (2.9) Giải thuật phát hiện tiếng nói Trước khi tiến hành viết một giải thuật để phát hiện tiếng nói, chúng ta cần phải quyết định: Sử dụng tham số nào Ngưỡng cho tham số đó là bao nhiêu Dưới đây là một giải thuật phát hiện tiếng nói sử dụng kết hợp hai tham số là năng lượng ngắn hạn và tốc độ đi qua điểm không. Sử dụng giải thuật này ta có thể xác định ngưỡng một cách tự động. Khởi tạo: Coi 100ms đầu tiên của tín hiệu thu được là khoảng lặng. Tính giá trị trung bình và độ lêch chuẩn của tham số tốc độ đi qua điểm không. Tính ngưỡng tốc độ đi qua điểm không IZCT theo công thức sau: Tính năng lượng cho từng khung Tính ngưỡng năng lượng ITL và ITU theo trình tự sau: Tìm khung có năng lượng lớn hơn ITL đánh dấu nó như là điểm có thể bắt đầu tiếng nói, gọi nó là s. Nếu khung sau s có năng lượng lớn hơn ITL thì nó sẽ là khung bắt đầu tiếng nói. Còn nếu có năng lượng nhỏ hơn ITL thì phải tìm lại s. Tìm khung có năng lượng nhỏ hơn ITU, khung này là khung kết thúc tiếng nói. Kết quả phát hiện tiếng nói ở các bước trên có thể chưa chính xác, cần phải điều chỉnh chúng theo cách sau: Từ khung bắt đầu tiếng nói ta tìm ngược về phía trước 250ms. Đếm số khung có tốc độ đi qua điểm không vượt quá ngưỡng IZCT. Nếu có từ 3 khung trở lên thì dich chuyển vị trí bắt đầu về khung có tốc độ đi qua điểm không vượt quá IZCT gần s nhất. Ngược lại s vẫn giữ nguyên vị trí. Thực hiện tương tự đối với điểm kết thúc tiếng nói. Giải thuật này đã được cài đặt trong chương trình và nó cho kết quá khá tốt với tham số IFT chọn là 25/độ dài của frame. PHÂN TÍCH MÃ HÓA DỰ ĐOÁN TUYẾN TÍNH (LPC) Lý thuyết về mã hoá dự đoán tuyến tính đã được nghiên cứu trong nhiều năm qua và nó đã chứng tỏ được những ưu điểm của mình khi áp dụng trong lĩnh vực xử lý tiếng nói. Phần này sẽ mô tả những kiến thức cơ bản để có thể ứng dụng nó trong lĩnh vực xử lý tiếng nói [6]. Mô hình LPC Ý tưởng cơ bản của mô hình LPC là một mẫu tín hiệu tiếng nói ở thời điểm n, có thể xấp xỉ như là tổ hợp tuyến tính của p mẫu trước đó, về mặt toán học ta có công thức sau: s(n) a1s(n -1) + a2s(n - 2) + … + aps(n - p) (2.10) ở đó là tín hiệu tiếng nói ở thời điểm n, còn các hệ số ai được coi là các hằng số đối với mỗi khung tiếng nói. Chúng ta có thể chuyển công thức xấp xỉ trên thành biểu thức với việc thêm vào các trọng số kích thích Gu(n) như sau: s(n) = a1s(n -1) + a2s(n - 2) + … + aps(n - p) + Gu(n) (2.11) Trong đó u(n) là kích thích được chuẩn hóa và G là trọng số kích thích (Gain). Thực hiện phép biến đổi Z cho 2 vế của đẳng thức (2.11) ta có: (2.12) Suy ra hàm truyền đạt : (2.13) Hình 2.1 dưới đây minh họa cho biểu thức (2.13), trong đó nguồn kích thích chuẩn hóa u(n) được nhân với trọng số kích thích G, và đóng vai trò là đầu vào cho hệ thống toàn điểm cực để tạo ra tín hiệu tiếng nói s(n). Hình 21 Mô hình dự đoán tuyến tính của tiếng nói Các công thức phân tích LPC Nếu coi ước lượng của tín hiệu tiếng nói ở thời điểm n như là tổ hợp tuyến tính của p mẫu trong quá khứ thì ta có công thức sau: (2.14) trong đó được gọi là ước lượng của Khi đó sai số dự đoán e(n) được định nghĩa là : (2.15) và hàm truyền đạt sai số là : (2.16) Vấn đề cơ bản của phân tích dự đoán tuyến tính là phải xác định trực tiếp từ tín hiệu tiếng nói một tập các hệ số dự đoán {ak} sao cho các thuộc tính phổ của bộ lọc số ở hình 2.1 phù hợp với các thuộc tính phổ tương ứng của dạng sóng tiếng nói trong cửa sổ phân tích. Do đặc tính phổ của tiếng nói thay đổi theo thời gian như đã đề cập ở trên nên các hệ số dự đoán tại thời điểm n phải được đánh giá trên một đoạn tín hiệu tiếng nói ngắn xung quanh thời điểm n. Bởi vậy, cách tiếp cận cơ bản là tìm ra một tập các hệ số dự đoán mà tập hệ số này làm tối thiểu hóa sai số bình phương trung bình trên một đoạn ngắn của tín hiệu. Để thiết lập các phương trình xác định tập hệ số dự đoán, ta định nghĩa tín hiệu tiếng nói trong thời gian ngắn và sai số tại thời điểm n như sau : sn(m) = s(n+m) (2.17) en(m) = e(n+m) (2.18) Sai số bình phương trung bình của tín hiệu tại thời điểm n sẽ có công thức như sau : (2.19) Nếu tối thiểu hóa En bằng cách chọn các hệ số ak thích hợp thì đạo hàm riêng của En ứng với mỗi hệ số ak (k = 1, 2, ..., p) sẽ bằng 0, tức là : (2.20) Suy ra : (2.21) Kí hiệu hàm hiệp biến : (2.22) Đẳng thức (2.21) được viết dưới dạng rút gọn như sau: (2.23) Công thức này mô tả một hệ p phương trình p ẩn số. Còn sai số bình phương trung bình sẽ được biểu diễn dưới dạng sau : (2.24) Ta thấy sai số bình phương trung bình bao gồm một số hạng cố định () và các số hạng phụ thuộc vào các hệ số tiên đoán. Để xác định các hệ số dự đoán tối ưu () bằng cách giải phương trình (2.23) chúng ta phải tính với 1£ i£ p và 0£ k£ p, rồi sau đó giải một hệ p phương trình tuyến tính. Trên thực tế, phương pháp để giải hệ phương trình này phụ thuộc rất nhiều vào khoảng m sử dụng trong xác định đoạn tín hiệu tiếng nói phân tích và vùng trên đó sai số bình phương trung bình được tính. Có 2 phương pháp phân tích LPC dựa trên việc xác định khoảng này, đó là phương pháp tự tương quan (Autocorrelation Method) và phương pháp hiệp biến (Covariance Method). Trong các hệ thống nhận dạng tiếng nói trên thực tế người ta thường chỉ sử dụng phương pháp phân tích tự tương quan nên bản báo cáo này chỉ trình bày nội dụng của phương pháp này._.. Phân tích tự tương quan Một cách định nghĩa giới hạn của m trong các tổng đơn giản và dễ thực hiện là cho rằng các đoạn tiếng nói sn(m) là bằng 0 ở bên ngoài khoảng 0£m£N-1. Điều này tương đương với việc nhân tín hiệu tiếng nói s(m+n) với một cửa sổ có độ dài hữu hạn w(m), cửa sổ này bằng 0 ở bên ngoài khoảng 0£m£N-1. Như vậy mẫu tiếng nói có thể được biểu diễn như sau : (2.25) Vì sn(m) = 0 " mN-1+p cũng không có sai số dự đoán bởi vì sn(m) = 0 " m>N-1. Tuy nhiên, trong vùng từ m=0 tới m=p-1 tín hiệu tiếng nói đã qua cửa sổ sn(m) được dự đoán từ các mẫu trước đó, một vài trong số chúng ngẫu nhiên bằng 0. Vì vậy, có khả năng lớn là sai số dự đoán tồn tại trong vùng này. Hơn nữa, trong vùng từ m=N-1 đến m=N-1+p khả năng xảy ra sai số dự đoán cũng khá lớn bởi vì tín hiệu tiếng nói bằng 0 được dự đoán từ một vài mẫu tín hiệu tiếng nói khác 0 trước đó. Do vậy chúng ta sẽ thấy ảnh hưởng này lớn tại hai biên. Mục đích việc sử dụng cửa sổ trong phương trình (2.25) là ghi lại tín hiệu gần m=0 và gần m=N-1 để tối thiểu hóa sai số tại các biên của đoạn cần phân tích. Với việc sử dụng tín hiệu có trọng số ở phương trình (2.25), sai số bình phương trung bình trở thành : (2.26) Và có thể được biểu diễn như sau: (2.27) Hay : (2.28) Vì phương trình (2.28) chỉ là một hàm của i-k nên hàm hiệp biến trở thành hàm tự tương quan đơn giản: (2.29) Vì hàm tự tương quan là đối xứng, rn(-k) = rn(k) nên các phương trình LPC có thể biểu diễn như sau: (2.30) Biểu diễn dưới dạng ma trận: (2.31) Ma trận các giá trị tương quan là một ma trận Toeplitz (ma trận đối xứng có các phần tử trên đường chéo chính bằng nhau) nên phương trình (2.31) có thể được giải quyết hiệu quả bởi một số thuật toán nổi tiếng. Một trong số đó là giải thuật Durbin. Giải thuật Durbin là giải thuật sử dụng truy hồi được phát biểu như sau: (2.32) (2.33) (2.34) (2.35) (2.36) Trong đó tổng sigma trong (2.33) được bỏ qua khi i=1. Các phương trình (2.32 - 2.36) được thực hiện với i lần lượt bằng 1, 2, .., p. Cuối cùng ta thu được lời giải của (2.31) với là các hệ số LPC, là các hệ số PARCOR: (2.37) Bộ xử lý LPC trong hệ thống nhận dạng tiếng nói Phần này chúng ta sẽ thảo luận chi tiết về bộ tiền xử lý LPC đã được sử dụng rộng rãi trong các hệ thống nhận dạng tiếng nói. Sơ đồ khối của bộ tiền xử lý này như sau: Hình 22 Sơ đồ khối bộ tiền xử lý LPC trong hệ thống nhận dạng tiếng nói Bộ tiền xử lý LPC bao gồm 8 bước như trong hình 2.2, chức năng cụ thể từng bước được trình bày chi tiết dưới đây. Bộ lọc hiệu chỉnh Tín hiệu tiếng nói s(n) được đưa qua một bộ lọc số bậc thấp (thường là bộ lọc có đáp ứng xung hữu hạn bậc một) để làm cho phổ đồng đều hơn, như vậy sẽ làm giảm ảnh hưởng gây ra bởi độ chính xác hữu hạn của các xử lý tín hiệu sau này. Bộ lọc số ở đây có thể là bộ lọc cố định hoặc bộ lọc thích nghi chậm. Thường bộ lọc hiệu chỉnh trong trường hợp này là bộ lọc cố định bậc một, có dạng : H(z) = 1 - az -1 , với 0.9 £ a £ 1.0 (2.38) Trong trường hợp này tín hiệu ra quan hệ với tín hiệu vào theo phương trình sai phân sau : (2.39) Giá trị a thường được chọn xung quanh 0.95 hoặc nó có thể chọn thay đổi tùy theo giá trị của n. Phân khung Trong bước này tín hiệu đầu ra của bộ lọc hiệu chỉnh được phân thành các khung, mỗi khung có N mẫu. Hai khung kề nhau lệch nhau M mẫu. Khung đầu tiên chứa N mẫu, khung thứ hai bắt đầu chậm hơn khung thứ nhất M mẫu, và đè lên khung thứ nhất N- M mẫu. Tương tự khung thứ ba chậm hơn khung thứ nhất 2M mẫu (chậm hơn khung thứ hai M mẫu) và đè lên khung thứ nhất N- 2M mẫu. Quá trình này tiếp tục cho đến khi tất cả các mẫu tiếng nói cần phân tích thuộc về một hoặc nhiều khung. Dễ thấy, nếu M £ N thì các khung kề nhau sẽ chồng lên nhau, kết quả là việc đánh giá phổ sẽ liên quan từ khung này đến khung kia, nếu M<<N thì việc đánh giá phổ từ khung này đến khung kia sẽ rất trơn. Ngược lại nếu M ³ N thì các khung kề nhau sẽ không chồng lên nhau, do đó một vài tín hiệu sẽ bị mất hoàn toàn (nghĩa là không xuất hiện trong bất kì khung nào), phổ thu được khi đánh giá các khung kề nhau sẽ chứa một phần nhiễu. Biên độ thành phần nhiễu này tăng lên khi M tăng (nghĩa là càng nhiều mẫu bị bỏ qua không phân tích). Điều này là không thể chấp nhận được đối với các hệ thống nhận dạng thực tế. Nếu ta kí hiệu khung thứ k là xk(n), và có tất cả K khung thì: , n = 0, 1, .., N -1, k = 0, 1,.., K - 1 (2.40) Tức là, khung thứ nhất gồm các mẫu , ,.., , khung thứ hai gồm các mẫu ,,..,, cuối cùng khung thứ K, xK-1(n), gồm các mẫu ,,..,. Giá trị thường sử dụng của M trong các hệ thống nhận dạng dựa trên bộ tiền xử lý LPC là . Những bước tiếp sau đều xử lý trên từng frame tiếng nói. Lấy cửa sổ Để làm giảm thiểu tính gián đoạn của tín hiệu tại điểm đầu và cuối của mỗi khung. Tín hiệu tiếng nói được nhân với một cửa sổ với mục đích làm thon hai đầu của khung tín hiệu cần phân tích. Nếu ta định nghĩa cửa sổ là w(n), 0£ n £ N-1, kết quả sau khi lấy cửa sổ là: , 0£ n £ N -1 (2.41) Cửa sổ thường được sử dụng trong phương pháp phân tích tự tương quan là cửa sổ Hamming, cửa sổ này có dạng: , 0£ n £ N -1 (2.42) Phân tích tự tương quan Mỗi khung sau khi đi qua cửa sổ được lấy tự tương quan theo công thức sau: , m = 0, 1, .., p (2.43) Trong đó p là bậc của phân tích LPC giá trị thường sử dụng của nó trong khoảng 8 đến 16. Một lợi ích phụ khi phân tích tự tương quan là giá trị tương quan đầu tiên, , là năng lượng của khung thứ k. Năng lượng của khung là một tham số quan trọng trong các hệ thống phát hiện tiếng nói. Phân tích LPC Trong bước này sẽ chuyển p+1 giá trị tương quan của mỗi khung thành một “tập tham số LPC”, tập tham số này có thể là các hệ số LPC, hệ số phản xạ, hệ số phổ, hay bất cứ thông tin nào được suy ra từ các tập trên. Phương pháp tìm các hệ số LPC từ giá trị tương quan đã được trình bày trong phần phân tích tự tương quan. Chuyển hệ số LPC thành các hệ số Cepstral Trong các hệ thống nhận dạng tiếng nói người ta thường sử dụng các hệ số Cepstral thay vì dùng trực tiếp các hệ số LPC. Các công thức để chuyển các hệ số LPC thành các hệ số Cepstral như sau: (2.44) , (2.45) , (2.46) Trong đó là trọng số kích thích trong mô hình LPC giá trị của nó trong trường hợp này không quan trọng vì ta không sử dụng đến c0. Thường dùng số các hệ số cepstral Q lớn hơn số các hệ số LPC p (Qp). Cepstral có trọng số Bởi vì độ nhạy của các hệ số cepstral bậc thấp làm cho phổ toàn bộ bị đổ dốc, và độ nhạy của các hệ số cepstral bậc cao gây ra nhiễu, nên người ta thường sử dụng cửa sổ cepstral để cực tiểu hóa các độ nhạy này. Một cách thức bình thường để điều chỉnh là sử dụng một cửa sổ Cepstral được xem xét với khai triển Fourier của bộ đệm cường độ dải âm thanh và được phân biệt với bộ đệm dải âm thanh như sau: (2.47) (2.48) Sự khác biệt của bộ đệm cường độ dải âm thanh có một thuộc tính mà bất kỳ độ lệch quang phổ trong bộ đệm cường độ dải âm thanh là một hàm số; hơn nữa bất kỳ một đỉnh quang phổ nào trong bộ đệm cường độ dải âm thanh được bảo quản tốt như một đỉnh trong tín hiệu cường độ dải âm thanh. Vì vậy bằng cách xem xét nhân với (-jm) trong khai triển của bộ đệm cường độ dải âm thanh chúng ta được: (2.49) với (2.50) Để nhận được các giá trị chính xác của m và để cắt sự tính toán vô hạn trong công thức (2.50), chúng ta phải xem xét thêm các trọng có dạng (2.51) Khi một trọng xấp xỉ được lọc trong vùng Cepstral: (2.52) Hàm chỉnh trọng này cắt xén sự tính toán và làm giảm cm quanh các giá trị m=1 và m = Q. Đạo hàm Cepstral theo thời gian Biểu diễn cepstral của phổ tiếng nói là biểu diễn tốt tính chất phổ địa phương ứng với một frame đã cho. Để cải thiện hơn nữa ta có thể khảo sát thêm đạo hàm cepstral theo thời gian. Kí hiệu hệ số cepstral đã nhân trọng số thứ m tại thời điểm t là . Khi tổ chức chương trình, thời gian t sẽ là chỉ số frame. Do được biểu diễn rời rạc theo thời gian nên dùng vi phân cấp một và cấp hai để xấp xỉ đạo hàm là không thích hợp. (2.53) Các xử lý phù hợp hơn cả là xấp xỉ bằng một đa thức trực giao phù hợp trên cửa sổ có chiều dài hữu hạn, tức là : (2.54) Trong đó m là hằng số chuẩn hóa thích hợp giá trị thường chọn của nó là 0.375 [7] và (2K+1) là số lượng frame cần tính (K=2 là giá trị hay được sử dụng để tính đạo hàm cấp một). Tóm lại, sau tám bước trên mỗi khung ta thu được một Vector có 2Q thành phần. Vector này sẽ trở thành chuỗi quan sát dùng để nhận dạng về sau. PHÂN TÍCH CEPSTRAL THÔNG QUA THANG ĐỘ MEL (MFCC) Gần đây trong bộ tiền xử lý của một số hệ thống nhận dạng tiếng nói có sử dụng một phương pháp khác để phân tích các tham số của tiếng nói. Phương pháp này có tên là phân tích Cepstral thông qua thang độ mel (MFCC) [6]. Phương pháp này đã cho hiệu quả nhất định. Mô hình tính toán các hệ số MFCC Trong phần này sẽ mô tả toàn bộ chuỗi xử lý trả về các đặc trưng của tín hiệu. Lược đồ thể hiện trên hình 2-3 sẽ trả về hệ số phân tích phổ tần MFCC [6]. Hình 23 Sơ đồ khối tính toán các hệ số MFCC Mỗi khối trong chuỗi sẽ được mô tả chi tiết ở các mục sau. Mặc dù hiện nay có rất nhiều mô hình xử lý song mô hình trên là mô hình có độ chính xác cao hơn đồng thời độ phức tạp tính toán cũng nhỏ hơn so với các mô hình khác. Quá trình tiền xử lý tín hiệu Bộ lọc thích nghi Tín hiệu tiếng nói sau khi số hoá được đưa qua một bộ lọc thích nghi để làm phẳng phổ của tín hiệu. Bộ lọc thích nghi này thường là bộ lọc thông cao và có thể thực hiện ở cả trong miền thời gian và miền tần số. Trong miền thời gian ta có công thức sau: (2.55) hệ số a nằm trong khoảng [0.9,1.0]. Giá trị thường chọn của nó là 0.95. Chuẩn hóa biên độ Sau khi qua bộ lọc hiệu chỉnh tín hiệu được chuẩn hóa để có biên độ nằm trong khoảng [-1.0,1.0], theo công thức sau: i=0,…,N-1 (2.56) Phân khung Tín hiệu sau khi qua bộ lọc, chuẩn hoá được phân thành M khung, mỗi frame có W mẫu và trồng nên nhau V mẫu. Giá trị của V thường là 20 đến 50% giá trị của W. Sau khi phân khung ta được một ma trận Y có M hàng, mỗi hàng là một frame tiếng nói. Ta có công thức sau: (2.57) , (2.58) Lấy cửa sổ Mỗi khung tiếng nói được nhân với một hàm cửa sổ nhằm làm giảm tính gián đoạn trong miền thời gian của phổ do các hoạt động của con người tạo ra. Ta có: (2.59) Hàm cửa sổ thường sử dụng là cửa sổ Hamming được mô tả trong công thức (2.43) nhưng thay N là W. Phổ năng lượng Khung tiếng nói sau khi được nhân trọng số sẽ được tính FFT, sau bước tính FFT ta thu được phổ của tín hiệu và khi đó phổ năng lượng của tín hiệu được tính như sau: (2.60) kết quả của bước này ta thu được ma trận S có kích thước M x U với U là số điểm tính FFT cho một frame. Băng lọc Mel Băng lọc Mel là một dãy các băng lọc dạng tam giác trồng nên nhau với tần số cắt của mỗi bộ lọc được xác định bởi tần số trung tâm của hai bộ lọc kề với nó. Mô hình này được xây dựng dựa trên nghiên cứu cho rằng tai con người không cảm nhận theo thang tuyến tính mà nó chỉ tuyến tính với những tâng số dưới 1000Hz và theo thang logarit với các tần số khác.Nếu chúng ta coi tần số fmin = 20Hz và fmax là một phần hai tần số lấy mẫu thì khi đó băng lọc mel được định nghĩa như sau: (2.61) (2.62) (2.63) (2.64) (2.65) Một sự xấp xỉ thường được sử dụng trong tỉ lệ Mel đối với băng lọc là các băng lọc theo thang tuyến tính và có giải thông bằng nhau ứng với tần số dưới 1000Hz và biến thiên theo thang logarit ứng với tần số trên 1000Hz, ở đó tần số trung tâm của mỗi bộ lọc bằng 1.1 lần tần số trung tâm của bộ lọc trước nó. Sau bước trên ta sẽ có một ma trận F kích thước K x U với K là số bộ lọc trong băng lọc còn U là số điểm tính FFT. Logarit các hệ số năng lượng qua băng lọc Phổ năng lượng của tín hiệu được đưa qua băng lọc. Kết quả ở bước này ta thu được một ma trận P kích thước M x K với các phần tử của nó được tính như sau: (2.66) và (2.67) Biến dổi Cosine rời rạc ngược Phép biến đổi Cosine rời rạc ngược được sử dụng để làm trực giao các vector năng lượng đã qua bộ lọc. Do bước biến đổi trực giao này thông tin của các vector phổ năng lượng được nén xướng các thành phần đầu tiên và chúng ta có thể rút ngắn các vector này xuóng còn L thành phần. Kết quả của bước này ta thu được một ma trận Q có kích thước là M x L. với các phần tử được đinh nghĩa như sau: (2.68) L được chọn nhỏ hơn K và thường từ 9 đến 15. Sau 8 bước trên ta thu được các phần tử là các hệ số Cepstral của tiếng nói. Cepstral có trọng số Bởi vì độ nhạy của các hệ số cepstral bậc thấp làm cho phổ toàn bộ bị đổ dốc, và độ nhạy của các hệ số cepstral bậc cao gây ra nhiễu, nên người ta thường sử dụng cửa sổ cepstral để cực tiểu hóa các độ nhạy này. Công thức biểu diễn các hệ số cepstral có trọng số là : (2.69) Đạo hàm Cepstral theo thời gian Để nâng cao chất lượng nhận dạng, ta đưa thêm các giá trị đạo hàm theo thời gian của các hệ số MFCC vào trong vector tham số tiếng nói, các giá trị đó được tính theo công thức sau : (2.70) Trong đó là độ dài cửa sổ tính delta, thường chọn là 2 hoặc 3. Tóm lại, sau các bước trên với mỗi khung ta thu được một vector có 2L thành phần biểu diễn tham số đặc trưng của tiếng nói. Qua thực nghiệm cho thấy nếu sử dụng hệ số MFCC thì trong môi trường nhiễu hiệu quả của nó sẽ cao hơn sử dụng hệ số LPC, còn trong môi trường bình thường thì kết quả của chúng là gần như nhau. Tuy nhiên nếu dùng hệ số LPC thì tốc độ nhận dạng nhanh hơn so với việc sử dụng MFCC. Do vậy tuỳ điều kiện cụ thể và mục tiêu mà ta sử dụng phương pháp tương ứng. LƯỢNG TỬ HÓA VECTOR Sau bước phân tích và trích trọn đặc trưng của tiếng nói thì lượng thông tin cần phải xử lý của tiếng nói đã giảm đi khá nhiều, tuy nhiên đây chưa phải là biện pháp giảm tối thiểu lượng thông tin cần xử lý. Trong các hệ thống nhận dạng tiếng nói còn có thêm một bước nữa để giảm hơn nữa lượng thông tin của tiếng nói cần phải xử lý đó là phương pháp Lượng tử hóa vector. Có hai bước cần phải làm để thực hiện lượng tử hóa vector là: Bước 1: Xây dựng codebook. Các vector đặc trưng của tập huấn luyện được phân thành các nhóm, trong mỗi nhóm này chọn ra nhân của nhóm để làm một từ mã, tập các từ mã này tạo thành một sách mã (codebook). Bước 2: Lượng tử hóa. Mỗi một vector đầu vào được so sánh với các vector có trong codebook để tìm ra từ mã nào “giống” với nó nhất. Sau khi lượng tử hóa thay vì phải thao tác với một vector chúng ta chỉ cần thao tác với chỉ số của từ mã giống với vector đó nhất, do đó làm giảm đáng kể khối lượng tính toán cần thực hiện. Những phần tử sau đây sẽ giúp ta hoàn thành hai bước trên Tập vector huấn luyện Tập vector huấn luyện là tập vector đặc trưng của các mẫu tiếng nói dùng để tạo ra các mẫu tham chiếu trong nhận dạng. Để việc tạo codebook có hiệu quả thì tập các mẫu này phải được thu thập từ các nguồn sau: Nhiều người nói khác nhau về tuổi tác, giới tính, giọng điệu, tốc độ… Thu âm trong nhiều điều kiện khác nhau, trong môi trường yên tĩnh, trong phòng làm việc, qua điện thoại… Qua các thiết bị truyển đổi, các hệ thống truyền thông như mic, điện thoại cầm tay… Khoảng cách giữa hai vector Khoảng cách giữa hai vector phổ vi và vj được định nghĩa như sau (2.71) Đối với các vector LPC hoặc các vector được tính ra từ nó thì thường sử dụng là khoảng cách cepstral được tính như sau: (2.72) trong đó , là thành phần thứ n của hai vector cepstral tương ứng. L là số thành phần có trong một vector cepstral. Trong các ứng dụng nhận dạng tiếng nói, ngoài việc sử dụng tính khoảng cách như trên người ta còn sử dụng khoảng cách cepstral có trọng số như: (2.73) (2.74) với w(n) thường sử dụng có dạng như sau: (2.75) giá trị của h thường sử dụng là L/2. Việc sử dụng khoảng cách Cepstral có trọng số sẽ giúp loại bỏ ảnh hưởng của các thành phần không mong muốn trong phổ LPC (như nhiễu) mà vẫn giữ lại được toàn bộ các đặc tính trong cấu trúc của các formant. Nhân của một tập vector Giả sử ta có L vector xi khi đó nếu sử dụng khoảng cách cepstral thì nhân của L vector này có thể tính như sau: (2.76) Phân cụm các vector Giả sử trong tập huấn luyện của ta có L vector bây giờ ta cần xây dựng nên một codebook có M vector. Để làm được điều này ta cần có một thủ tục để phân L vector huấn luyện thành M cụm và sau đó từ mỗi cụm này ta chọn ra một phần tử đại diện là nhân của cả cụm. Thủ tục sau đây sẽ giúp ta thực hiện được nhiệm vụ này (Thủ tục này thường được gọi là giải thuật Lloyd hay giải thuật phân cụm K-trung bình) Khởi tạo: Chọn tuỳ ý M vector (Có thể không nằm trong tập huấn luyện) dùng làm các từ khởi tạo trong codebook. Tìm láng giếng gần nhất: Với mỗi một vector trong tập huấn luyện ta tìm ra một vector trong codebook “giống” nó nhất và gán vector này về nhóm tương ứng với từ mã đó Cập nhật nhân: Sử dụng công thức tìm nhân ở trên để cập nhật lại nhân của từng nhóm. Lặp: Lặp lại bước hai và bước ba cho đến khi trung bình khoảng cách của các vector trong cùng một nhóm đến nhân của nhóm nhỏ hơn một ngưỡng nào đó. Thủ thục lặp trên chạy tốt, song trên thực tế còn có một thủ tục khác có lợi hơn trong việc thiết kế một codebook có kích thước là M. Thủ tục này được gọi là thủ tục tách nhị phân, nó gồm các bước như sau: Bước 1: Thiết kế codebook có một vector. Vector này là nhân của tập vector huấn luyện. Bước 2: Nhân đôi kích thước của codebook bằng cách tách mỗi một vector yn trong codebook theo luật sau: (2.77) giá trị của thường chọn trong khoảng [0.01,0.05]. Bước 3: Sử dụng giải thuật phân nhóm K trung bình ở trên để tìm ra tập nhân tốt nhất cho codebook vừa được tách ra. Bước 4: Lặp lại bước hai và bước ba cho đến khi xây dựng được codebook có kích thước theo yêu cầu. Sơ đồ khối của thuật toán tách nhị phân như sau: Tìm nhân ban đầu Bắt đầu Tách nhân D’ = 0 Phân lớp vector Tìm các nhân Tính độ méo D’ D-D’<d m< M D’ = D m= 2*m Kết thúc Y N N m = 1 Y Hình 24 Sơ đồ khối thuật toán tách nhị phân Chương này đã trình bày cơ sở lý thuyết của các thuật toán trong khâu tiền xử lý tiếng nói. Tín hiệu sau khi được thu nhận từ card âm thanh được đưa vào modul phát hiện tiếng nói nhằm lọc thông tin dư thừa ra khỏi tín hiệu tiếng nói. Sau đó, tín hiệu này được trích chọn lấy tín hiệu đặc trưng bằng một trong hai phương pháp là mã hóa dự đoán tuyến tính hoặc phân tích hệ số phổ tần Mel. Cuối cùng tín hiệu được lượng tử hóa vector để tối thiểu hóa lượng thông tin trước khi đưa vào khâu nhận dạng. MÔ HÌNH MARKOV ẨN Trong chương một đã đề cập đến các phương pháp thường được sử dụng trong nhận dạng tiếng nói. Trong ba phương pháp này thì phương pháp nhận dạng mẫu là phương pháp đơn giản và khá hiệu quả. Các hệ thống nhận dạng tiếng nói theo phương pháp nhận dạng mẫu thường gặp nhất là nhận dạng mẫu có sử dụng mô hình Markov ẩn. Đây là một mô hình thống kê có rất nhiều ưu điểm trong nhận dạng tiếng nói. Chương này sẽ trình bày lý thuyết về mô hình Markov ẩn và những vấn đề cần chú ý khi cài đặt mô hình Markov ẩn. Để cho dễ hiểu trước hết chúng ta hãy nghiêm cứu một chút về chuỗi Markov rời rạc sau đó mở rộng nó sang mô hình Markov ẩn [7] [9]. CÁC QUÁ TRÌNH MARKOV RỜI RẠC Xét một hệ thống mà ở đó tại bất kì thời điểm nào ta cũng có thể mô tả nó bởi một trong N trạng thái phân biệt S1, S2,…,SN. Với những khoảng thời gian rời rạc cách đều hệ thống thực hiện chuyển trạng thái (có thể vẫn ở trạng thái đó) theo một tập xác suất nào đó gắn với từng trạng thái. Gọi thời gian ứng với việc thay đổi trạng thái đó là t =1,2,3,…., và gọi trạng thái ở thời điểm t là qt. Trong trường hợp tổng quát thì xác xuất để hệ thống ở một trạng thái nào dó phải phụ thuộc vào tất cả các trạng thái trước nó, tuy nhiên đối với chuỗi Markov bậc một thì xác suất này chỉ phụ thuộc vào trạng thái liền trước nó mà thôi. P[qt = j | qt-1 = i, qt-2 = k, ...] = P[qt = j | qt-1 = i] ( 3.1) Hơn nữa chúng ta chỉ quan tâm tới những tiến trình mà ở đó vế phải của công thức (3.1) độc lập với thời gian. Khi đó ta có một ma trận chuyển trạng thái như sau: aij = P[at = j | qt-1 = i] 1 £ i, j £ N ( 3.2) với các hệ số chuyển trạng thái có các thuộc tính sau: ( 3.3) ( 3.4) Quá trình thống kê trên gọi là một mô hình Markov có thể quan sát được bởi đầu ra của tiến trình tại bất kì thời điểm nào chỉ là môt trong số N trạng thái, và mỗi trạng thái lại gắn với một sự kiện vất lý nào đó. Hãy xem xét ví dụ mo hình Markov ba trạng thái về thời tiết như sau: Giả định thời tiết trong một ngày t được mô tả bởi một trong ba trang thái. Trạng thái 1: Trời mưa. Trạng thái 2: Trời nhiều mây. Trạng thái 3: Trời nắng. Ma trận chuyển trạng thái A như sau: ( 3.5) với mô hình trên các câu hỏi thường đặt ra là: Cho trạng trạng thái ở ngày thứ nhất (t=1) là trời nắng, tính xác suất để 7 ngày tiếp sau sẽ là: “Nắng-Nắng-Mưa-Mưa-Nắng-Mây-Nắng”. Giải: Kí hiệu chuỗi quan sát O ứng với các trạng thái của mô hình là: O = {S3, S3, S3, S1, S1,S3, S2, S3} tương ứng với t=1, 2, 3, … ,8 khi đó ta có ( 3.6) ở đây là xác xuất để trạng thái thứ i là trạng thái khởi đầu của mô hình, do đó ta có. ( 3.7 Cho mô hình và trạng thái khởi tạo hãy tính xác suất để mô hình vẫn ở trạng thái đó đúng trong d ngày tiếp sau Giải: Từ giả thiết ta có chuỗi quan sát tương ứng là: ( 3.8) xác suất của chuỗi với mô hình là. ( 3.9) ở đây pi(d) là hàm xác suất rời rạc để mô hình ở trạng thái i trong d ngày. Dựa vào pi(d) chúng ta có thể tính được số lần mong đợi để hệ thống ở nguyên trạng thái đó trong một với điều kiện nó chính là trạng thái khởi đầu của mô hình đó. ( 3.10) do đó ngày mong đợi liên tiếp nhau để mô hình có trạng thái là trời nắng là: 1/(1-0.2) = 5 ngày, trời mưa là: 1/(1-0.6) = 2.5 ngày và nhiều mây là: 1/(1-0.4) = 1.67 ngày. MÔ HÌNH MARKOV ẨN Khái niệm Mô hình Markov mà chúng ta thảo luận ở phần trên là mô hình có thể quan sát được, mô hình này có rất nhiều hạn chế khi áp dụng nó vào giải quyết các vấn đề trong thực tế. Trong phần này chúng ta sẽ mở rộng nó để bao gồm cả trường hợp trong đó chuỗi quan sát là hàm xác suất của trạng thái, kết quả ta thu được mô hình là một quá trình ngẫu nhiên được nhúng hai lần với một quá trình ngẫu nhiên chính không thể quan sát được một cách trực tiếp mà chỉ có thể quan sát được thông qua một tập quá trình ngẫu nhiên khác – các quá trình ngẫu nhiên tạo ra các chuỗi quan sát. Để hiểu rõ hơn về khái niệm mô hình Markov ẩn chúng ta hãy nghiên cứu thí nghiệm tung đồng xu. Mô hình tung đồng xu: Giả sử bạn đang ngồi trong một căn phòng có một bức tường chắn do đó bạn không thể nhìn thấy được điều gì đang xảy ra ở phía bên kia của bức tường, ở đó một người đang thực hiện một thí nghiệm tung đồng xu. Người này sẽ không nói cho ban biết là anh ta tung đồng xu nào mà chỉ nói cho bạn biết kết quả tung đồng xu là xấp hay ngửa. Do đó một chuỗi các thí nghiệm tung đồng xu “ẩn” đã được thực hiện, với chuỗi quan sát là một dãy các mặt xấp, ngửa của các đồng xu. Thông thường chuỗi quan sát này có dạng như sau: O = {o1,o2,….,oT} = {H T H T… T} ( 3.11) với mô hình thí nghiệm này thì một vấn đề đặt ra là làm sao chúng ta có thể xây dựng nên một mô hình Markov ẩn (HMM) để giải thích cho các chuỗi quan sát được. Hai vấn đề mà ta cần phải giải quyết để có thể xây dựng nên một HMM là: Các trạng thái của mô hình tương ứng với cái gì. Mô hình cần bao nhiêu trạng thái. Đối với thí nghiệm trên chúng ta có thể có ba lựa chon sau: Giả định chỉ có một đồng xu được tung khi đó chúng ta có thể mô hình hoá thí nghiệm trên bằng mô hình có hai trạng thái với mỗi trạng thái của nó ứng với kết quả của lần tung đồng xu trước đó. Đây là mô hình Markov có thể quan sát được và chỉ có một vấn đề cần phải giả quyết là xác định giá trị tốt nhất cho từng tham số của mô hình (xác suất mặt xấp, ngửa). Mô hình được thể hiện trong hình 3.1.1. Mô hình thứ hai là một mô hình có hai trạng thái, trong đó mỗi trạng thái tương ứng với một mặt của đồng xu (Hình 3.1.2). Mỗi trạng thái của mô hình được đặc trưng bởi. Phân bố xác suất mặt sấp hay mặt ngửa. Xác xuất chuyển đổi giữa các trạng thái, được mô tả bởi ma trận chuyển trạng thái. Mô hình thứ ba ứng với trường hợp có ba đồng xu được sử dụng trong thí nghiệm. Việc lựa chọn đồng xu nào do một số sự kiện mang tính xác suất quyết định.(Hình 3.1.3). Hình 31 Ba mô hình Markov ẩn cho thí nghiệm tung đồng xu Với các mô hình trên thì câu hỏi đặt ra là mô hình nào giải thích tốt nhất cho chuỗi quan sát thu được. Với mô hình thứ nhất thì chỉ có một tham số ma ta chưa biết là P(H), với mô hình thứ hai có bốn tham số mà ta chưa biết là {a11, a22, P1,P2}, còn đối với mô hình thư ba thì có chín tham số mà ta chưa biết là (a11, a12, a21, a22, a31, a32, P1, P2, P3). Có thể thấy rằng những mô hình có bậc tự do lớn hơn dường như sẽ mô hình hóa thí nghiệm trên tốt hơn, điều này chỉ đúng về mặt lý thuyết còn trên thực tế có một số giới hạn về kích thước của mô hình cần phải quan tâm đến. Thành phần của mô hình Markov ẩn Một mô hình Markov ẩn được mô tả bởi 3 thành phần cơ bản: N-Số trạng thái của mô hình: Mặc dù số trạng thái của mô hình là ẩn nhưng trong các ứng dụng ở thực tế thì thường có một ý nghĩa vật lý nào đó gắn với các trạng thái của mô hình. Ta đánh nhãn các trạng thái riêng rẽ là {1,2,3,4,..,N} và kí hiệu trạng thái ở thời điểm t là qt. M- Số biểu tượng có thể quan sát được ứng với mỗi trạng thái: Các biểu tượng có thể quan sát được thường tương ứng với sự kiện vật lý đàu ra của một hệ thống đang được mô hình hoá. Trong thí nghiệm tung đồng xu thì số biểu tượng có thể quan sát được ứng với từng trạng thái chính là mặt sấp và mặt ngửa của đồng xu. Ta kí hiệu các biểu tượng đó là V = {v1,v2,…,vM}. Ma trận xác suất chuyển trạng thái A = {aij}:Với aij là xác suất để trạng thái ở thời điểm t là i và trạng thái ở thời điểm t+1 là j. Do đó ta có. ( 3.12) ( 3.13) trong trường hợp tổng quát thì aij>0 với mọi i,j nằm trong khoản từ 1 đến N tuy nhiên trong nhiều hệ thống aij lại có thể bằng không ứng với một số giá trị nào đó của i và j. Ma trận phân bố xác suất các kí hiệu quan sát B = {bi(k)}. Trong đó bj(k) là xác suất nhận được kí hiệu quan sát vk ở trạng thái j: bj(k) = P[ot=vk | qt=j] 1£k£M ( 3.14) ( 3.15) Ma trận phân bố xác suất trạng thái ban đầu p = {pi} Trong đó pi là xác suất mô hình ở trạng thái i tại thời điểm ban đầu t=1: p = P[q1=i] ( 3.16) ( 3.17) như vậy để đặc tả đầy đủ một mô hình Markov ẩn thì chúng ta cần các tham số là số trạng thái N, số biểu tượng quan sát M và các ma trạn xác suất A,B,p. Người ta thường kí hiệu một mô hình như trên dưới dạng: ( 3.18) Ba bài toán cơ bản của mô hình Markov ẩn Với mô hình Markov ẩn được mô tả như trên thì có ba bài toán cơ bản cần phải giải quyết để có thể áp dụng nó vào thực tế là: Bài toán một Vấn đề: Cho một chuỗi quan sát O = O1 O2 … OT, và một mô hình Markov ẩn , Tính xác suất của chuỗi quan sát O với mô hình một cách hiệu quả nhất. Giải pháp: Đây là bài toán đánh giá, nghĩa là cho trước mô hình và dãy quan sát, ta phải tính xác suất mô hình với dãy quan sát đã được tạo ra. Có thể xem đây là một kiểu đánh giá xem mô hình được cho có tốt với dãy quan sát đó hay không. Trong trường hợp ta phải chọn một trong số nhiều mô hình thì giải pháp cho bài toán 1 sẽ cho ta sự lựa chọn được mô hình thích hợp nhất đối với dãy quan sát. Cách tường minh nhất để tính được xác suất trên là thông qua việc đánh số mọi dãy trạng thái chiều dài T (T là số lượng quan sát trong dãy). Có NT dãy trạng thái như vậy. Xét một trong các dãy trạng thái đó: q = (q1q2...qT) ( 3.19) Trong đó q1 là trạng thái khởi đầu. Xác suất của dãy quan sát O cho bởi dãy trạng thái q ở trên sẽ là: ( 3.20) Giả sử rằng các quan sát là độc lập thống kê, ta có: ( 3.21) Xác suất của một dãy trạng thái q như vậy là: ( 3.22) Xác suất để O và q xảy ra đồng thời là: ( 3.23) Xác suất của O cho bởi mô hình chính là lấy tổng của xác suất trên tất cả các dãy trạng thái có thể có của q, tức là: ( 3.24) Việc tính toán P(O|l) theo định nghĩa trực tiếp của nó như trên bao gồm 2T.NT phép tính, do tại mọi thời điểm t=1,2,...T có N trạng thái có thể đạt được (có NT chuỗi trạng thái có thể), và với mỗi dãy trạng thái như vậy cần khoảng 2T phép tính cho mỗi toán hạng trong tổng ở công thức trên. Khối lượng tính toán nhiều như vậy trong thực tế là không thể thực hiện được (với những giá trị khá nhỏ của N và T, chẳng hạn N=5 và T=100 thì cũng cần phải thực hiện khoảng 1072 phép tính). Vì vậy, ta cần phải có một giải thuật đơn giản hơn để giải quyết vấn đề này. Dưới đây là hai thủ tục để giải quyết vấn để này. Cần phải chú ý là nếu chỉ để tính xác suất của một chuỗi quan sát với một mô hình thì ta chỉ cần sử dụng thủ tục tiến nhưng ở đây giới thiệu cả thủ tục lùi để do nó được sử dụng để giải quyết vấn đề thứ 3. Thủ tục tiến (Forward Procedure) Xét biến tiến at(i) được định nghĩa như sau: at(i) = P(o1o2...ot, qt=i|l) ( 3.25) Đó là xác suất của dãy quan sát bộ phận o1o2...ot và trạng thái i đạt được tại thời điểm t. Ta có thể dùng quy nạp để tính at(i) như sau: Khởi tạo: ( 3.26) Quy nạp: ( 3.27) Kết thúc: ( 3.28) Bước 1 khởi tạo các biến a1(i) là xác suất đồng thời trạng thái i và quan sát ban đầu o1. Bước quy nạp là cốt lõi của thủ tục, được minh họa trong hình 3.2 (a). Hình này cho thấy ta có thể đạt tới trạng thái j ở thời điểm t+1 từ N trạng thái i, , ở thời điểm t như thế nào. Vì at(i) là xác suất của biến cố o1o2 ... ot và trạng thái ở thời điểm t là i, nên tích at(i)aij là xác suất đồng thời của biến cố o1o2...ot và trạng thái j ở thời điểm t+1 qua trạng thái i ở thời điểm t. Lấy tổng tất cả các tích này theo tất cả các trạng thái i, , ở thời điểm t ta sẽ nhận được xác suất trạng thái j ở thời điểm t+1 với tất cả những quan sát từng phần ở trước thời điểm t+1. Do đó dễ dàng nhận thấy rằng at+1(j) bằng tổng trên nhân với bj(ot+1). Cuối cùng, bước 3 cho ta kết quả P(O|l) là tổng của những biến tiến cuối cùng aT(i), đó là do định nghĩa: aT(i) = P(o1o2...ot, qT=i|l) ( 3.29) Vì vậy P(O|l) chính là tổng của các aT(i), Ta có nhận xét rằng, việc tính toán theo thủ tục tiến cần khoảng N2T phép tính, cụ thể cần N(N+1)(T-1)+N phép tính nhân và N(N-1)(T-1) phép tính cộng. Chẳng hạn với N=5 và T=100 thì ta cần khoảng 3000 phép._.