Tài liệu Học cấu trúc mạng logic Markov và ứng dụng trong bài toán phân lớp

Luận văn thạc sĩ Phạm Đình Hiệu ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN --------------------- Phạm Đình Hiệu HỌC CẤU TRÚC MẠNG LOGIC MARKOV VÀ ỨNG DỤNG TRONG BÀI TOÁN PHÂN LỚP LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội - 2012 1 Luận văn thạc sĩ Phạm Đình Hiệu ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN --------------------- Phạm Đình Hiệu HỌC CẤU TRÚC MẠNG LOGIC MARKOV VÀ ỨNG DỤNG TRONG BÀI TOÁN PHÂN LỚP Chuyên ngành: Bảo đảm toán học cho máy tính và hệ thống tính toán. Mã số: 60 46 35 LUẬN VĂN THẠC SĨ KHOA HỌC Ngƣời hƣớng dẫn khoa học: TS. Nguyễn Thị Minh Huyền Hà Nội - 2012 2 Luận văn thạc sĩ Phạm Đình Hiệu MỤC LỤC LỜI NÓI ĐẦU ............................................................................................................6 CHƢƠNG 1. CƠ SỞ TOÁN HỌC ............................................................................8 1.1 Lý thuyết đồ thị..............................................................................................8 1.2 Logic tân từ cấp một ......................................................................................9 1.2.1 Các khái niệm và ký hiệu........................................................................9 1.2.2 Công thức trong logic tân từ cấp một ...................................................10 1.2.3 Dạng chuẩn hội .....................................................................................12 1.3 Xác suất – thống kê .....................................................................................13 1.3.1 Các khái niệm .......................................................................................13 1.3.2 Công thức Bayes ...................................................................................15 1.3.3 Cực đại hóa xác suất có điều kiện.........................................................16 1.3.4 Xích Markov .........................................................................................17 1.3.5 Xích Markov Monte Carlo ....................................................................19 1.3.6 Phƣơng pháp lấy mẫu Gibbs .................................................................20 CHƢƠNG 2. MẠNG LOGIC MARKOV ...............................................................21 2.1 Giới thiệu .....................................................................................................21 2.2 Mạng Markov ..............................................................................................22 2.3 Mạng logic Markov .....................................................................................24 2.4 Suy diễn .......................................................................................................29 2.4.1 Suy diễn MAP/MPE .............................................................................29 2.4.2 Suy diễn điều kiện.................................................................................32 2.5 Học tham số và học cấu trúc........................................................................34 2.5.1 Học tham số ..........................................................................................34 2.5.2 Học cấu trúc ..........................................................................................39 CHƢƠNG 3. ỨNG DỤNG MẠNG LOGIC MARKOV TRONG BÀI TOÁN GÁN NHÃN VAI NGHĨA 3.1 Bài toán gán nhãn vai nghĩa ........................................................................46 3.2 Mô tả dữ liệu sử dụng ..................................................................................46 3 Luận văn thạc sĩ Phạm Đình Hiệu 3.3 Giới thiệu công cụ Thebeast ........................................................................47 3.4 Các bƣớc thực hiện bài toán ........................................................................48 3.4.1 Dữ liệu và cấu trúc dữ liệu trong Thebeast ...........................................48 3.4.2 Xây dựng dữ liệu huấn luyện ................................................................49 3.5 Đánh giá kết quả thực nghiệm .....................................................................52 TÀI LIỆU THAM KHẢO .........................................................................................55 4 Luận văn thạc sĩ Phạm Đình Hiệu DANH MỤC HÌNH VẼ Hình 1-1. Đồ thị G ......................................................................................................8 Hình 1-2. Phân phối biên trên biến rời rạc ................................................................14 Hình 1-3. Phân phối biên cho biến liên tục ...............................................................15 Hình 2-1. Minh họa cho mạng Markov ....................................................................22 Hình 2-2. Mạng Markov nền .....................................................................................26 Hình 3-1. Biểu diễn cây cú pháp ...............................................................................50 5 Luận văn thạc sĩ Phạm Đình Hiệu LỜI NÓI ĐẦU Trong sự phát triển về Công nghệ thông tin hiện nay vấn đề xử lý, tính toán không còn thuần túy là tính toán trên các dữ liệu kiểu số biểu diễn dƣới dạng cấu trúc, bảng biểu hay véc tơ, vv. Nó đã đƣợc phát triển mở rộng xử lý trên dữ liệu kiểu hình ảnh, âm thanh, văn bản, đồ thị và nhiều kiểu khác nữa. Trong sự phát triển đó của Công nghệ, học máy đƣợc xem là một lĩnh vực của trí tuệ nhân tạo với mục tiêu là nghiên cứu các thuật toán cho phép máy tính có thể học đƣợc các khái niệm. Thƣờng học máy đƣợc phân làm hai phƣơng pháp: phƣơng pháp quy nạp và phƣơng pháp suy diễn. Đến nay học máy có ứng dụng rộng khắp trong các ngành khoa học, sản xuất, đặc biệt những ngành cần phân tích khối lƣợng dữ liệu khổng lồ. Một số ứng dụng thƣờng thấy: Rôbốt, trò chơi, phân tích thị trƣờng chứng khoán, phát hiện gian lận tài chính, phân tích ảnh thiên văn, phân loại chuỗi gene, quá trình hình thành gene, phân tích ảnh X-quang, các hệ chuyên gia chẩn đoán tự động, tìm kiếm, nhận dạng hay nhiều ứng dụng liên quan tới xử lý ngôn ngữ tự nhiên. Học quan hệ thống kê cũng là một trong các lĩnh vực của học máy, nó hƣớng tới sự kết hợp giữa học theo quan hệ và học theo thống kê nhằm xử lý các dữ liệu không chắc chắn với cấu trúc quan hệ phức tạp. Có nhiều mô hình đƣợc phát triển gần đây cho học quan hệ thống kê nhƣ mô hình quan hệ xác suất (Probabilistic Relational Model) sử dụng logic kết hợp với các mạng Bayes hay Markov. Trong đó các mạng MLN (Markov Logic Network) mang tính tổng quát cao nhất, có thể chuyển đổi sang các mô hình khác và ngày càng có nhiều nghiên cứu về các mạng này. Mạng logic Markov có thể đƣợc xem nhƣ là một sự kết hợp hữu cơ giữa học logic và học thống kê. Mục đích của MLN là mô tả một minh họa cho trƣớc với một tập các công thức logic có trọng số. Nó cho phép sử dụng những ƣu điểm của logic tân từ cấp một là khả năng biểu diễn tri thức và các mối quan hệ phức tạp của tri thức, cùng với ƣu điểm của mạng Markov có thể xử lý một cách hiệu quả sự không chắc chắn và giải quyết tri thức một cách đối lập và thiếu thông tin. 6 Luận văn thạc sĩ Phạm Đình Hiệu Mục tiêu của luận văn là tìm hiểu các mạng MLN và phƣơng pháp học cấu trúc cho mạng MLN. Luận văn cũng triển khai một ứng dụng giải quyết bài toán phân lớp với mạng MLN sử dụng phần mềm Thebeast. Cụ thể ở đây là bài toán gán nhãn vai nghĩa trong lĩnh vực xử lý ngôn ngữ. Xử lý ngôn ngữ chính là xử lý thông tin khi đầu vào là dữ liệu ngôn ngữ, tức là dữ liệu kiểu văn bản hay tiếng nói. Các dữ liệu liên quan đến ngôn ngữ viết (văn bản) và tiếng nói đang dần trở nên kiểu dữ liệu chính con ngƣời có và lƣu trữ dƣới dạng điện tử. Việc xây dựng ngữ liệu mẫu cho bài toán gán nhãn vai nghĩa tƣơng đối phức tạp, nên bƣớc đầu thực hiện chúng tôi chỉ dùng giới hạn bài toán ở 2 vai nghĩa “tác thể” và “bị thể” trong câu. Bố cục luận văn đƣợc chia làm 3 chƣơng: Chƣơng I: Cơ sở toán học Trong chƣơng này sẽ trình bày về một số kiến thức cơ bản đƣợc sử dụng trong luận văn liên quan tới lý thuyết đồ thị, logic và xác suất thống kê. Chƣơng II: Mạng logic Markov Chƣơng này sẽ trình bày các kiến thức về mạng Markov, mạng logic Markov và một số vấn đề về học máy với mạng logic Markov nhƣ suy diễn, học tham số và đặc biệt là học cấu trúc. Chƣơng III: Ứng dụng mạng logic Markov trong bài toán gán nhãn vai nghĩa Chƣơng này sẽ trình bày về bài toán gán nhãn vai nghĩa, vấn đề xây dựng dữ liệu huấn luyện trong công cụ Thebeast cho bài toán gán nhãn vai nghĩa và đánh giá kết quả. 7 Luận văn thạc sĩ Phạm Đình Hiệu CHƢƠNG 1. CƠ SỞ TOÁN HỌC 1.1 Lý thuyết đồ thị Định nghĩa 1.1.1. Đồ thị là cặp từ , trong đó A là tập đỉnh, F là ánh xạ [3]. Ta cũng có thể định nghĩa đồ thị là cặp: , trong đó là tập đỉnh và là tập cung. Về thực chất đồ thị là một tập hợp các đối tƣợng đƣợc biểu diễn bằng các đỉnh và giữa các đối tƣợng có quan hệ (nhị nguyên) biểu diễn bằng các cung[3]. Cho đồ thị gọi là đỉnh đầu, . Nếu có thì ta nói rằng là một cung và gọi là đỉnh cuối của cung đó. Hai đỉnh kề nhau là hai đỉnh của cùng một cung. Đỉnh nút là đỉnh kề với chính nó. Định nghĩa 1.1.2. Đồ thị đồ thị nếu với đƣợc gọi là đồ thị con của [3]. Định nghĩa 1.1.3. Hai đỉnh gọi là liên thông với nhau nếu chúng trùng nhau hoặc có xích nối với nhau[3]. Đồ thị đối xứng gọi là đồ thị vô hƣớng tức là ta luôn có . Định nghĩa 1.1.4. Đồ thị vô hƣớng đƣợc gọi là đầy đủ nếu hai đỉnh bất kỳ đều có cung nối với nhau[3]. Định nghĩa 1.1.5. Clic (Clique) của đồ thị là một đồ thị con đầy đủ[3]. Hình 1-1. Đồ thị G 8 Luận văn thạc sĩ Phạm Đình Hiệu Clic cực đại là một clic với số nút là lớn nhất, không thể thêm bất kỳ nút nào nữa để cho nó vẫn còn là một clic. Ví dụ: Cho đồ thị nhƣ hình vẽ:   Ví dụ trong hình trên các clique cực đại là {(3; 4; 6); (3; 1); (1; 2); (2; 4); (2; 5); (5; 6)} 1.2 Logic tân từ cấp một 1.2.1 Các khái niệm và ký hiệu Logic tân từ cấp một là một ngôn ngữ rất mạnh để biểu diễn những thông tin có quan hệ phức tạp, cho phép ta mô tả thế giới với các đối tƣợng, các thuộc tính của đối tƣợng và các mối quan hệ giữa các đối tƣợng[9]. Một cơ sở tri thức xây dựng trên logic tân từ cấp một (KB) là một tập các câu hay các công thức trong logic tân từ cấp một. Công thức đƣợc xây dựng bằng cách sử dụng 4 loại ký hiệu: hằng, biến, hàm và vị từ[9], [12].  Ký hiệu hằng: dùng để chỉ các đối tƣợng trên một miền (Ví dụ miền chỉ ngƣời: Nga, Hùng,…).  Ký hiệu biến: dùng để biểu diễn các đối tƣợng trong miền (ví dụ x, y).  Ký hiệu vị từ: biểu diễn mối quan hệ giữa các đối tƣợng trong miền (ví dụ Bạn(x,y) biểu diễn quan hệ x là bạn của y) hay là thuộc tính của các đối tƣợng (ví dụ Hútthuốc(x) biểu diễn thuộc tính có hút thuốc của đối tƣợng x (x có hút thuốc)).  Các ký hiệu phép toán logic: (hội), (tƣơng đƣơng). 9 (tuyển), (kéo theo), (phủ định), Luận văn thạc sĩ Phạm Đình Hiệu  Các ký hiệu lƣợng từ: (với mọi), (tồn tại).  Các ký hiệu ngăn cách: Dấu phẩy, dấu mở ngoặc, dấu đóng ngoặc. 1.2.2 Công thức trong logic tân từ cấp một Các hạng thức là các biểu thức mô tả các đối tƣợng. Các hạng thức xác định đệ quy nhƣ sau:  Các hằng, biến là hạng thức.  Nếu là các hạng thức và là hàm thì là hạng thức. Một hạng thức không chứa biến đƣợc gọi là một hạng thức nền. Ví dụ: Nga là ký hiệu hằng, MotherOf là ký hiệu hàm một biến, thì MotherOf (Nga) là một hạng thức nền. Một công thức nguyên tử đƣợc định nghĩa là: Nếu P là vị từ n biến và là các hạng thức thì là công thức nguyên tử. Các công thức đƣợc xây dựng một cách đệ quy từ các công thức nguyên tử bằng cách sử dụng các phép toán logic và các lƣợng từ. Nếu thức thì những ký hiệu sau đây cũng là công thức: : F1 F2, F1 và và là các công F1, F1^F2, F1 F2, F1 F1[9]. Mức ƣu tiên: 1. Các lƣợng từ có mức ƣu tiên cao nhất. 2. Phép phủ định có mức ƣu tiên cao hơn các phép toán logic khác. 3. Phép hội có mức ƣu tiên cao hơn phép tuyển. Ta có thể sử dụng các dấu ngoặc đơn để thực thi các mức ƣu tiên. Ví dụ: 1. Nga và anh trai cô ấy không có bạn chung: 2. Tất cả con chim đều bay: 10 F2, Luận văn thạc sĩ Phạm Đình Hiệu Công thức đóng: Một biến nằm trong phạm vi của lƣợng từ gọi là biến ràng buộc. Ví dụ biến ràng buộc trong là . Một biến nằm ngoài phạm vi của bất kỳ lƣợng từ nào gọi là biến tự do. Ví dụ : là biến tự do trong . Một công thức đƣợc gọi là công thức đóng nếu nó không chứa biến tự do nào. Ở đây chúng ta chỉ quan tâm tới các công thức đóng. Một literal dƣơng (Positive literal) là một công thức nguyên tử, một literal âm (negative literal) là một công thức nguyên tử ở dạng phủ định. Các công thức trong cơ sở tri thức KB (knowledge base) kết nối với nhau bởi phép hội, vì vậy một KB có thể đƣợc coi là một công thức đơn lớn. Một hạng thức nền (hay hạng thức cụ thể) (ground term) là một hạng thức không chứa biến. Một công thức nguyên tử nền (ground atom) là một công thức nguyên tử mà tất cả các tham biến của nó đều là các hạng thức nền. Không gian Herbrand (Herbrand universe) U(C) của tập các mệnh đề C là tập các hạng thức cụ thể đƣợc xây dựng từ hàm và hằng trong C (hoặc nếu C không chứa hằng thì cũng coi nhƣ nó chứa một hằng bất kỳ, giả sử là A). Nếu C chứa các hằng thì U(C) là hữu hạn. (Ví dụ: Nếu C chỉ chứa duy nhất một hàm và không chứa hằng, U(C) = Một minh họa (interpretation) là một ánh xạ giữa các hằng, vị từ và hàm trong ngôn ngữ và các đối tƣợng, các hàm và các mối quan hệ trong miền. Một minh họa có thể là phép gán giá trị chân lý cho các vị từ. Cùng với một minh họa, nó gán một giá trị chân lý tới mọi công thức nguyên tử, và vì vậy tới mọi công thức trong cơ sở tri thức. Một công thức là thỏa được nếu và chỉ nếu tồn tại ít nhất một minh họa làm cho nó đúng. Vấn đề suy diễn cơ bản trong logic tân từ cấp một là xác định cơ sở tri thức 11 Luận văn thạc sĩ Phạm Đình Hiệu KB có suy dẫn ra một công thức F hay không? Nghĩa là nếu F đúng với mọi minh họa khi KB đúng (ký hiệu KB KB ). Ta có thể viết lại: KB dẫn ra F nếu và chỉ nếu F là không thỏa đƣợc. Mọi cơ sở tri thức trong logic tân từ cấp một đều có thể chuyển sang dạng mệnh đề (clausal form). Dạng mệnh đề cho cơ sở tri thức trong logic tân từ cấp một là hội của các mệnh đề, trong đó mỗi biến đều có các lƣợng từ toàn thể. Việc chuyển đổi này bao gồm việc xóa hết tất cả các lƣợng từ tồn tại bằng phƣơng pháp Skolem. Trong miền hữu hạn một công thức có lƣợng từ tồn tại có thể thay thế bởi một phép tuyển của các thay thế của nó. 1.2.3 Dạng chuẩn hội Mọi công thức trong logic tân từ cấp một có thể chuyển thành một công thức tƣơng đƣơng trong dạng chuẩn hội (CNF) lƣợng từ, là biến và , trong đó Q là là hội của các mệnh đề. Ví dụ: Logic tân từ cấp một Biến đổi trong logic tân từ cấp một “Bạn của bạn là bạn” “Hút thuốc dẫn đến ung thƣ” “Nếu hai ngƣời là bạn thì họ cùng hoặc không cùng hút thuốc” ) 12 Luận văn thạc sĩ Phạm Đình Hiệu 1.3 Xác suất – thống kê 1.3.1 Các khái niệm Định nghĩa 1.3.1. Xác xuất của biến cố A là một số không âm bằn trong khoảng [0;1], ký hiệu là P(A), biểu thị khả năng xảy ra biến cố A và đƣợc xác định nhƣ sau: Trong đó là số trƣờng hợp thuận lợi cho , là số trƣờng hợp có thể có khi phép thử thực hiện . Định nghĩa 1.3.2. Xác suất có điều kiện của biến cố đã xảy ra là một con số không âm, đƣợc ký hiệu là xảy ra của biến cố trong tình huống biến cố với điều kiện biến cố , nó biểu thị khả năng đã xảy ra khi đó: Định nghĩa 1.3.3. Biến ngẫu nhiên: Một biến nhận các giá trị của nó ứng với một xác suất nào đấy gọi là biến ngẫu nhiên[1]. Định nghĩa 1.3.4. Hai biến ngẫu nhiên và và là độc lập nếu . Định nghĩa 1.3.5. Phân phối đồng thời (joint distribution): Cho hai biến ngẫu nhiên và đồng thời của nhiên của đƣợc định nghĩa trên cùng một không gian xác suất, phân phối và là xác suất của các biến cố đƣợc định nghĩa trong véc tơ ngẫu và . Định nghĩa 1.3.6. Phân phối biên (marginal distribution): Cho hai biến ngẫu nhiên và , và phân phối của là phân phối đồng thời của chúng. Phân phối biên của mà đƣợc bỏ qua. 13 là Luận văn thạc sĩ Phạm Đình Hiệu Các công thức cho phân phối đồng thời:  Trƣờng hợp cho các biến rời rạc:  Trƣờng hợp cho các biến liên tục: trong đó và của và khi biết là phân phối điều kiện của . và là phân phối biên của Phân phối đồng thời cho các biến độc lập:  Trƣờng hợp cho các biến rời rạc:  Trƣờng hợp cho các biến liên tục: Các công thức cho phân phối biên:  Trƣờng hợp cho các biến rời rạc: trong đó . Minh họa bằng hình vẽ: Hình 1-2. Phân phối biên trên biến rời rạc 14 khi biết và . Luận văn thạc sĩ Phạm Đình Hiệu  Trƣờng hợp cho các biến liên tục: Minh họa bằng hình vẽ: Hình 1-3. Phân phối biên cho biến liên tục 1.3.2 Công thức Bayes Cho biến cố và các biến cố - Có tập sao cho[8]: rời nhau từng đôi một. Thì ta có công thức tổng: Công thức Bayes [1]: Trong đó:  A1, …, An là hệ đầy đủ : A1+ …+ An = Ω - không gian mẫu. 15 Luận văn thạc sĩ Phạm Đình Hiệu  là xác suất xảy ra biến cố Ak  : Xác suất để biến cố B xảy ra. P(B)>0.  P(B| Ai) là xác suất để B xảy ra biết rằng Ai đã xảy ra rồi ( tỉ lệ xảy ra B trong Ai) 1.3.3 Cực đại hóa xác suất có điều kiện Với một tập giả thiết có thể , hệ thống học sẽ tìm giả thiết có thể xảy ra nhất đối với các dữ liệu quan sát đƣợc . Giả thiết này đƣợc gọi là giả thiết cực đại hóa xác suất có điều kiện (maximum a posteriori – MAP) [6]. theo định lý Bayes và Ví dụ: Tập bao gồm giả thiết là nhƣ nhau đối với mọi giả thiết. : Anh ta chơi tennis, tennis. Tính giá trị của hai xác suất có điều kiện đó : Anh ta không chơi và , trong là tập dữ liệu về thông tin về thời tiết nhƣ: trời nắng hay mƣa, nhiệt độ, độ ẩm, sức gió,… Giả thiết có thể nhất nếu . Vì , ngƣợc lại thì là nhƣ nhau đối với cả hai giả thiết nên có thể bỏ qua đại lƣợng và . Vì vậy chỉ cần tính hai biểu thức và đƣa ra kết quả tƣơng ứng.  Nếu , thì kết luận anh ta chơi tennis.  Ngƣợc lại thì kết luận anh ta không chơi tennis. Giả sử trong phƣơng pháp ƣớc lƣợng hợp lý cực đại (hay đánh giá khả năng xảy ra cao nhất – maximum likelihood estimation – MLE) tất cả các giá trị đều có 16 Luận văn thạc sĩ Phạm Đình Hiệu giá trị xác suất tiên nghiệm nhƣ nhau : P( tìm giả thiết cực đại hóa giá trị dữ liệu thì phƣơng pháp MLE trong đó gọi là khả năng xảy ra của đối với . Vẫn với ví dụ trên, tập ta không chơi tennis. bao gồm hai giả thiết : Anh ta chơi tennis, : Anh lúc này là tập dữ liệu mà trong đó biết trời nắng, gió mạnh. Giả sử ta có , vậy hệ thống sẽ kết luận rằng anh ta sẽ không chơi tennis. 1.3.4 Xích Markov Xét một hệ nào đó đƣợc quan sát tại những thời điểm rời rạc 0, 1, 2,…Giả sử các quan sát đó là (ĐLNN) ( trong đó Khi đó ta có một dãy các đại lƣợng ngẫu nhiên là trạng thái tại thời điểm là ĐLNN rời rạc. Ký hiệu của hệ. Giả thiết rằng mỗi là tập giá trị của các . Khi đó một tập hữu hạn hay đếm đƣợc, các phần tử của nó đƣợc ký hiệu là là Ta gọi là không gian trạng thái của dãy. Định nghĩa 1.3.7. Ta nói rằng dãy các ĐLNN ( với mọi là một xích Markov nếu và với mọi . Ta coi thời điểm là tƣơng lai, là hiện tại còn Nhƣ vậy, xác suất có điều kiện của một sự kiện là quá khứ. nào đó trong tƣơng lai nếu biết hiện tại và quá khứ của hệ cũng giống nhƣ xác suất có điều kiện của nếu biết trạng thái hiện tại của hệ. Đó chính là tính Markov của hệ. Đôi khi tính Markov của hệ còn phát biểu dƣới dạng : Nếu biết trạng thái hiện tại của hệ thì quá khứ và tương lai độc lập với nhau. 17 Luận văn thạc sĩ Phạm Đình Hiệu Giả sử sau là xác suất để xích tại thời điểm bƣớc, tại thời điểm ở trạng thái chuyển sang trạng thái . Đây là một con số nói chung phụ thuộc vào . Nếu đại lƣợng này không phụ thuộc ta nói xích là thuần nhất[7]. Ma trận xác suất chuyển Giả sử là xích Markov rời rạc và thuần nhất. Nói một cách chính xác là: Giả sử ( là không gian xác suất, ngẫu nhiên nhận giá trị trong tập đếm đƣợc tính Markov và tính thuần nhất của là biến (đại lƣợng) là không gian trạng thái. Khi đó, có nghĩa là: không phụ thuộc vào . đƣợc gọi là ma trận xác suất chuyển sau một bƣớc, có điều kiện để hệ tại thời điểm tại thời điểm (hiện tại) ở trạng thái , chuyển sang trạng thái (tƣơng lai). Xác suất chuyển sau Rõ ràng rằng và đặt là xác suất bƣớc đƣợc định nghĩa theo công thức: . Ta quy ƣớc: . Đó là ma trận xác suất chuyển sau bƣớc. Phân phối dừng Phân phối của hệ tại thời điểm đƣợc cho bởi công thức sau : 18 Luận văn thạc sĩ Đặt Phạm Đình Hiệu và gọi Ta có là phân phối ban đầu của hệ. . Và đƣợc gọi là phân phối dừng nếu 1.3.5 Xích Markov Monte Carlo Tích phân Monte Carlo Tiếp cận đầu tiên của Monte Carlo là một phƣơng pháp phát triển bởi các nhà vật lý sử dụng phép sinh số ngẫu nhiên để tính toán. Giả sử rằng ta phải tính toán tích phân rất phức tạp: Nếu ta có thể phân tích hàm mật độ về dạng tích của một hàm đƣợc định nghĩa trong khoảng và một hàm . Tích phân có thể hiểu nhƣ là một kỳ vọng của hàm qua hàm mật độ . Vì vậy nếu ta sinh một số lƣợng lớn các biến ngẫu nhiên mật độ thì: Công thức này gọi là tích phân Monte Carlo. Ví dụ: 19 từ hàm Luận văn thạc sĩ Phạm Đình Hiệu Trong đó , khi suy ra Một vấn đề khi áp dụng tích phân Monte Carlo là việc thu các mẫu từ các phân bố xác suất phức tạp . Phƣơng pháp giải quyết vấn đề này là phƣơng pháp Markov chain Monte Carlo (MCMC). Ý tƣởng đơn giản của MCMC là: Cho một phân phối xác suất trên tập , ta phải sinh ngẫu nhiên các phần tử của với phân phối . MCMC thực hiện việc này bằng cách xây dựng một xích Markov với phân phối dừng và mô phỏng xích này. Thuật toán sinh đƣợc dùng là phƣơng pháp lấy mẫu Gibbs đƣợc trình bày dƣới đây. 1.3.6 Phƣơng pháp lấy mẫu Gibbs Cho tập các biến . Giả thiết trạng thái hiện tại là .  Chọn một giá trị mới cho từ ). Đặt  là giá trị mới đó. Tiếp theo chọn một giá trị mới cho từ , rồi từ .  Tiếp tục tƣơng tự với đến khi có một trạng thái mới 20 .