Tài liệu Luận văn Thạc sĩ Khoa học máy tính Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ

Đại Học Quốc Gia Thành Phố Hồ Chí Minh Trường Đại Học Bách Khoa BÙI VĂN ĐỒNG PHƯƠNG PHÁP ĐẠI SỐ CHO BÀI TOÁN ƯỚC LƯỢNG HỢP LÝ CỰC ĐẠI – ÁP DỤNG TRÊN CÂY SINH LOÀI NHỎ Chuyên ngành: Khoa học Máy tính LUẬN VĂN THẠC SĨ TP. HỒ CHÍ MINH, tháng 11 năm 2007 ĐẠI HỌC QUỐC GIA TP. HCM CỘNG HOÀ Xà HỘI CHỦ NGHIà VIỆT NAM TRƯỜNG ĐẠI HỌC BÁCH KHOA ---------------- Độc Lập - Tự Do - Hạnh Phúc ---oOo--- Tp. HCM, ngày . .05. . tháng . .11. . năm .2007. NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ và tên học viên : Bùi Văn Đồng Giới tính : Nam ;/ Nữ … Ngày, tháng, năm sinh : 10/10/1969 Nơi sinh : Quảng Ngãi Chuyên ngành : Khoa học Máy tính Khoá : 2005 1- TÊN ĐỀ TÀI : PHƯƠNG PHÁP ĐẠI SỐ CHO BÀI TOÁN ƯỚC LƯỢNG HỢP LÝ CỰC ĐẠI – ÁP DỤNG TRÊN CÂY SINH LOÀI NHỎ 2- NHIỆM VỤ LUẬN VĂN : 3- NGÀY GIAO NHIỆM VỤ: 4- NGÀY HOÀN THÀNH NHIỆM VỤ: 5- HỌ VÀ TÊN CÁN BỘ HƯỚNG DẪN : TS. Nguyễn Văn Minh Mẫn Nội dung và đề cương Luận văn thạc sĩ đã được Hội Đồng Chuyên Ngành thông qua. CÁN BỘ HƯỚNG DẪN CHỦ NHIỆM BỘ MÔN (Họ tên và chữ ký) QUẢN LÝ CHUYÊN NGÀNH Họ tên và chữ ký) TS. Nguyễn Văn Minh Mẫn TS. Đinh Đức Anh Vũ CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH Cán bộ hướng dẫn khoa học : TS. Nguyễn Văn Minh Mẫn Cán bộ chấm nhận xét 1 : Cán bộ chấm nhận xét 2 : Luận văn thạc sĩ được bảo vệ tại HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN THẠC SĨ TRƯỜNG ĐẠI HỌC BÁCH KHOA, ngày . . . . tháng . . . . năm . 2007 . Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ LỜI CAM ĐOAN Tôi cam đoan rằng, ngoại trừ các kết quả tham khảo từ các công trình khác như đã ghi rõ trong luận văn, các công việc trình bày trong luận văn này là do chính tôi thực hiện và chưa có phần nội dung nào của luận văn này được nộp để lấy một bằng cấp ở trường này hoặc trường khác. Ngày 05 tháng 11 năm 2007 Bùi Văn Đồng Bùi Văn Đồng Trang 1 Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ LỜI CẢM ƠN Xin gởi lời cảm ơn chân thành và sâu sắc đến TS. Nguyễn Văn Minh Mẫn, người Thầy đã tận tình hướng dẫn và tạo mọi điều kiện để tôi có thể hoàn thành luận văn này. Xin gởi lời cảm ơn đến các Thầy Cô đã dạy cho tôi trong thời gian qua. Tôi xin cảm ơn các bạn đồng môn và đồng nghiệp đã quan tâm, chia sẻ trong suốt quá trình học và làm luận văn. Luận văn này như một món quà nhỏ đáp lại tình cảm của gia đình và bạn bè thân thích. Bùi Văn Đồng Trang 2 Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ TÓM TẮT LUẬN VĂN Cây sinh loài mô tả lịch sử tiến hóa của một nhóm các loài với những đặc tính khác nhau nhưng cùng có mối quan hệ họ hàng với nhau và cùng hình thành từ một tổ tiên chung trong quá khứ. Đặc tính của mỗi loài được chúng ta quan tâm ở đây tương ứng với các bộ gen. Gen là các chuỗi DNA được bao gồm từ các kí tự A, G, C và T hợp thành. Cây sinh loài là một cây mà các nút lá (taxa) của nó có thể là các vật sống hiện tại ngày nay, các nút trong của cây đó là các tổ tiên của các nút lá. Tái cấu trúc cây sinh loài chính là tìm những gen phù hợp nhất để đưa vào các nút tổ tiên hoặc là đưa ra một cây sinh loài phù hợp nhất để giải thích quá trình tiến hoá. Tuy nhiên, việc nghiên cứu cây sinh loài cho nhiều hướng tiếp cận. Mỗi phương pháp có những ưu điểm và khuyết điểm của nó. Phương pháp ước lượng hợp lý cực đại được chọn ở đây là phương pháp phức tạp nhất nhưng lại là phương pháp cho kết quả tin cậy nhất. Công cụ chính sử dụng trong phương pháp này là Đại số thống kê và Đại số máy tính. Đó là những lãnh vực phát triển mạnh mẽ trong những năm gần đây. Thống kê là ngành khoa học phân tích dữ liệu. Đối với các chuỗi DNA thì thống kê sẽ xây dựng những mô hình quá trình phát sinh dữ liệu. Đưa ra những kết luận chung về quá trình phát sinh đó. Mô hình thống kê là nguyên tắc cơ bản đối với các gen. Đại số thống kê làm sáng tỏ cho những ý tưởng trọng tâm về phân tích dữ liệu rời rạc nói riêng và phân tích chuỗi sinh học nói riêng. Ước lượng hợp lý cực đại (Maximum Likelihood Estimation – MLE) được công thức hoá trong Xác suất cổ điển, nó có tính chất của một ước lượng tốt. Phương pháp MLE đánh giá những tham số của một mô hình thối lui. MLE dẫn đến việc giải quyết là làm cực đại tích của những đa thức. Đại số máy tính là một lãnh vực mới, nó cung cấp những nền tảng để giải bài toán MLE trên máy tính. Đề tài này tập trung vào việc nghiên cứu mô hình xác suất thống kê trên cây sinh loài từ những dữ liệu là các gen của sinh vật sống. Sau đó sử dụng những nền tảng toán học, đại số máy tính để giải quyết bài toán hợp lý cực đại của mô hình xác suất trên. Mục tiêu cuối cùng là tìm một cây sinh loài thích hợp nhất để giải thích sự tiến hoá. Những kết quả của luận văn đã làm như sau: - Về phương pháp: Chọn phương pháp đáng tin cậy nhất là phương pháp ước lượng hợp lý cực đại cho mô hình hóa bài toán. Giải phương trình hợp lý bằng phương pháp tính toán đại số để tìm kết quả chính xác. - Về tính toán: Viết một chương trình để mô hình hóa ước lượng hợp lý cực đại trên cây sinh loài và chạy tìm nghiệm phương trình hợp lý trên một số cây sinh loài nhỏ 3 và 4 taxa ở một số mô hình. Bùi Văn Đồng Trang 3 Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ DANH MỤC BẢNG Bảng 1: Bảng biến thiên của hàm hợp lý.......................................................................27 Bảng 2: Các mẫu và số lượng từng mẫu trên 3 chuỗi gen HIVenvSweden với cây hình móng (U68496, U68497, U68498).........................................................................55 Bảng 3: Các mẫu và số lượng từng mẫu trên 3 chuỗi gen HIVenvSweden với cây hình lược với trường hợp ((U68496,(U68497, U68498))...............................................55 Bảng 4: Các mẫu và số lượng từng mẫu trên 3 chuỗi gen HIVenvSweden với cây hình lược với trường hợp ((U68498,(U68496, U68497))...............................................56 Bùi Văn Đồng Trang 4 Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ DANH MỤC HÌNH Hình 1: Hai trường hợp xảy ra khi tung đinh bấm ........................................................26 Hình 2: Đồ thị của hàm hợp lý ......................................................................................27 Hình 3: Cây sinh loài của sự sống .................................................................................30 Hình 4: Mô tả xác suất chuyển đổi trạng thái của chuỗi “DNA”..................................32 Hình 5: Cây sinh loài với các nút trong và xác suất chuyển đổi ...................................32 Hình 6: Một trong những cây sinh loài 4 taxa...............................................................35 Hình 7: Cây sinh loài với dữ liệu trên nút lá và các khả năng xảy ra ở các nút tổ tiên.36 Hình 8: Cây sinh loài có gốc với 3 nút lá ......................................................................42 Hình 9: Sơ đồ khối chương trình tìm cấu trúc cây sinh loài .........................................53 Hình 10: Hai hình dạng cây 3 taxa có gốc.....................................................................55 Hình 11: Cây sinh loài 4 taxa hình móng ......................................................................68 Hình 12: Cây sinh loài 4 taxa hình cần trục ..................................................................68 Hình 13: Một số cây sinh loài 4 taxa.............................................................................68 Bùi Văn Đồng Trang 5 Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ MỤC LỤC LỜI CAM ĐOAN ..........................................................................................................1 LỜI CẢM ƠN ................................................................................................................2 TÓM TẮT LUẬN VĂN ................................................................................................3 DANH MỤC BẢNG ......................................................................................................4 DANH MỤC HÌNH .......................................................................................................5 MỤC LỤC ......................................................................................................................6 Chương 1. GIỚI THIỆU ĐỀ TÀI ................................................................................9 1.1. 1.2. Giới thiệu .............................................................................................................. 9 Cấu trúc luận văn .............................................................................................. 10 Chương 2. CƠ SỞ LÝ THUYẾT VỀ CÁC CẤU TRÚC ĐẠI SỐ VÀ XÁC SUẤT THỐNG KÊ ..............................................................................................12 2.1. 2.1.1. 2.1.2. 2.1.3. 2.1.4. 2.1.5. 2.1.6. 2.1.7. 2.1.8. 2.2. 2.2.1. 2.2.2. 2.2.3. 2.2.4. 2.2.5. 2.2.6. 2.2.7. Một số cấu trúc đại số cơ bàn ........................................................................... 12 Lý thuyết nhóm.........................................................................................................12 Lý thuyết vành ..........................................................................................................13 Trường ......................................................................................................................14 Vành đa thức .............................................................................................................14 Ma trận......................................................................................................................15 Định thức ..................................................................................................................15 Không gian vector.....................................................................................................16 Đa tạp đại số .............................................................................................................18 Các khái niệm về xác suất thống kê .................................................................18 Định nghĩa về xác suất..............................................................................................18 Xác suất có điều kiện ................................................................................................19 Đại lượng ngẫu nhiên và hàm phân phối ..................................................................20 Các đặc trưng của đại lượng ngẫu nhiên...................................................................20 Lý thuyết mẫu ...........................................................................................................21 Ước lượng tham số....................................................................................................22 Sơ lược về ước lượng hợp lý cực đại ........................................................................22 Chương 3. ƯỚC LƯỢNG HỢP LÝ CỰC ĐẠI TRÊN MẪU QUAN SÁT............25 3.1. 3.1.1. 3.1.2. 3.1.3. 3.2. 3.2.1. 3.2.2. 3.3. 3.3.1. Bùi Văn Đồng Ước lượng hợp lý cực đại là gì? ........................................................................ 25 Đặt vấn đề .................................................................................................................25 Khái quát về ước lượng hợp lý cực đại.....................................................................25 Ví dụ về ước lượng hợp lý cực đại ...........................................................................26 Giải bài toán ước lượng hợp lý cực đại............................................................ 26 Nguyên lý ước lượng hợp lý cực đại ........................................................................26 Logarit hàm hợp lý....................................................................................................26 Tổng quát hóa bài toán ước lượng hợp lý cực đại .......................................... 27 Ước lượng hợp lý cực đại trên mẫu quan sát ............................................................27 Trang 6 Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ 3.3.2. Một số phương pháp giải phương trình hợp lý .........................................................28 Chương 4. CÂY SINH LOÀI - MÔ HÌNH XÁC SUẤT THỐNG KÊ TRÊN CÂY SINH LOÀI ...............................................................................................30 4.1. 4.2. 4.3. 4.4. Giới thiệu sơ lược về cây sinh loài ....................................................................30 Các nghiên cứu phát sinh sinh loài................................................................... 31 Mô hình ước lượng hợp lý cực đại trên cây sinh loài ..................................... 32 Mô hình tiến hóa ................................................................................................ 33 Chương 5. BẤT BIẾN TRÊN CÂY SINH LOÀI .....................................................37 5.1. 5.2. 5.2.1. 5.2.2. 5.3. 5.4. 5.5. 5.5.1. 5.5.2. 5.5.3. 5.5.4. 5.5.5. 5.6. Dẫn nhập............................................................................................................. 37 Mô hình xác suất trên cây sinh loài..................................................................38 Mô hình bài toán cây sinh loài..................................................................................38 Nhóm Abel và sự liên hệ với các ma trận chuyển đổi ..............................................39 Biến đổi Fourier ................................................................................................. 40 Toạ độ Fourier ................................................................................................... 42 Áp dụng tìm bất biến trên một cây sinh loài ................................................... 42 Mô hình bài toán .......................................................................................................42 Các khả năng xảy ra trên các nút lá ..........................................................................43 Các lớp xác suất tương đương ..................................................................................43 Chuyển đổi Fourier ...................................................................................................44 Kết quả tìm được ......................................................................................................45 Những tính chất của thành phần bất biến....................................................... 46 Chương 6. GIẢI PHƯƠNG TRÌNH HỢP LÝ..........................................................47 6.1. 6.2. 6.2.1. 6.2.2. 6.2.3. 6.3. 6.4. 6.5. 6.6. Quỹ tích hợp lý trên một đa tạp ....................................................................... 47 Ma trận Jacobi của các đa thức bất biến......................................................... 47 Gradient- Vector vận tốc...........................................................................................47 Ma trận Jacobi của các đa thức bất biến ...................................................................48 Không gian tiếp xúc..................................................................................................49 Bài toán cực trị điều kiện .................................................................................. 49 Bậc của hợp lý cực đại....................................................................................... 50 Các thuật toán .................................................................................................... 50 Áp dụng giải phương trình hợp lý.................................................................... 51 Chương 7. CHƯƠNG TRÌNH THỰC HIỆN ...........................................................53 7.1. 7.2. 7.3. Sơ đồ khối chương trình.................................................................................... 53 Sơ lược về chương trình .................................................................................... 54 Kết quả chương trình ........................................................................................ 54 Chương 8. TỔNG KẾT – ĐÁNH GIÁ ......................................................................57 8.1. 8.2. 8.3. Tổng kết .............................................................................................................. 57 Những đóng góp của luận văn .......................................................................... 57 Hướng phát triển ............................................................................................... 58 TÀI LIỆU THAM KHẢO...........................................................................................59 Bùi Văn Đồng Trang 7 Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ Phụ lục 1. Tập các xác suất trình bày ở chương 5....................................................60 Phụ lục 2. Tập các dữ liệu kết quả thực hiện trình bày ở chương 6.......................62 Phụ lục 3. Trích một số SourceCodes chương trình viết trên Singular .................64 Phụ lục 4. Một số kết quả chương trình trên cây sinh loài 4 taxa ..........................68 Phụ lục 5. Bảng đối chiếu Thuật ngữ Anh - Việt.....................................................69 Danh mục các tên.........................................................................................................70 Bùi Văn Đồng Trang 8 Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ Chương 1. GIỚI THIỆU ĐỀ TÀI Chương này giới thiệu chung về bối cảnh, mục tiêu và kết quả thu được của đề tài. Cấu trúc nội dung của quyển thuyết minh được trình bày ở cuối chương. 1.1. Giới thiệu Phát sinh sinh loài đó là tái tạo lịch sử tiến hóa dựa trên các phương pháp toán học nhằm suy luận lịch sử tiến hóa sự sống trên hành tinh chúng ta. Việc tái cấu trúc này liên quan đến việc nhận diện chỉ định những đặc tính đồng dạng (homologous characters) được chia sẻ giữa các loài sinh vật khác nhau và suy luận cây phát sinh sinh loài từ việc so sánh các đặc tính thông qua việc sử dụng các phương pháp tái cấu trúc có độ tin cậy cao. Độ chính xác của quá trình suy luận vì thế phụ thuộc rất lớn vào độ tin cậy của các mô hình dùng để đánh giá sự tiến hóa của các đặc tính này. Trước đây việc tái tạo cây tiến hóa chủ yếu dựa trên phân tích hình thái và các đặc tính siêu cấu trúc. Trong nửa cuối thập niên 1980 nguồn dữ liệu trình tự DNA gia tăng cộng với sự phát triển ngành công nghệ thông tin, từ đó giúp nhà nghiên cứu có được những công cụ mạnh mẽ và nhằm giải quyết vài bài toán phát sinh sinh loài đang chưa có lời giải. Trong việc suy luận phát sinh sinh loài có 2 bước cơ bản đó là: - Chỉ định những đặc tính đồng dạng là những đặc tính chung truyền từ một tổ tiên chung cho đến các thế hệ hiện tại. - Tái cấu trúc cây tiến hóa bằng việc sử dụng các phương pháp thích hợp. Các dạng đặc tính có thể sử dụng là cấu trúc hình thái, siêu cấu trúc của tế bào, gene, trình tự DNA và protein miễn rằng chúng thỏa điều kiện là Đồng dạng. Có 3 nhóm phương pháp thường được dùng để tái cấu trúc cây phát sinh sinh loài từ một ma trận đặc tính: - Nhóm các phương pháp khoảng cách (Distance methods): Khoảng cách chính là khoảng cách tiến hóa giữa các cặp đối tượng đang được so sánh. - Nhóm phương pháp hà tiện đến mức tối đa (Maximum parsimony - MP): phương pháp này sẽ chọn lựa cây tiến hóa thỏa điều kiện là số lượng đặc tính bị biến đổi phải thấp nhất để giải thích những dữ liệu đã quan sát được. - Nhóm phương pháp hợp lý cực đại (Maximum Likelihood methods): nhóm phương pháp này dựa trên một hàm toán học tính toán xác suất khả năng một cây tiến hóa được tạo thành từ dữ liệu đã quan sát. Hàm này cho phép việc tích hợp các quá trình tiến hóa của đặc tính thành mô hình xác suất. Phương pháp hợp lý cực đại chọn lựa cây tiến hóa tối đa mà khi quan sát các dữ liệu dưới một mô hình nào đó có xác xuất tối đa. Trong các phương pháp giới thiệu ở trên thì phương pháp hợp lý cực đại là phương pháp là phức tạp nhất và cho kết quả đáng tin cậy nhất. Vì những lý do trên, Bùi Văn Đồng Trang 9 Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ trong dự án nghiên cứu này chúng tôi hướng vào kỹ thuật đại số tính toán cho vấn đề ước lượng khả năng cực đại và áp dụng để tái cấu trúc cây sinh loài. Xuất phát từ những thực tế trên, đề tài này đặt ra một số mục tiêu sau: ¾ Tìm hiểu mô hình xác suất thống kê trên cây sinh loài. Tìm hiểu phương pháp hợp lý cực đại và áp dụng trên cây sinh loài. ¾ Tìm những phương pháp toán học thích hợp để giải bài toán ước lượng hợp lý cực đại. ¾ Giải quyết cho trường hợp cây sinh loài 3 và 4 taxa. ¾ Tìm kiếm kết quả tương tự cho trường hợp 5 taxa. ¾ Hoàn thành một chương trình để kiểm nghiệm. Sau đây là một số kết quả thu được của đề tài: ¾ Xây dựng được mô hình xác suất thống kê tổng quát trên cây sinh loài. ¾ Chỉ ra sự tương đồng của mô hình bài toán với một số cấu trúc đại số cơ bản, từ đó tìm được thành phần bất biến trên cây sinh loài và giải bài toán. ¾ Xây dựng được một chương trình kiểm nghiệm. ¾ Chương trình đã giải quyết được bài toán MLE để tái cấu trúc cây sinh loài trên một số cây sinh loài nhỏ 3 taxa và trường hợp đặc biệt với cây 4 và 5 taxa. 1.2. Cấu trúc luận văn Nội dung luận văn được trình bày trong các chương sau: CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI Chương này giới thiệu chung về bối cảnh, mục tiêu và kết quả thu được của đề tài. Cấu trúc nội dung của quyển thuyết minh được trình bày ở cuối chương. CHƯƠNG 2: CÁC CẤU TRÚC ĐẠI SỐ CƠ BẢN - CƠ SỞ LÝ THUYẾT VỀ XÁC SUẤT THỐNG KÊ Chương này giới thiệu các khái niệm cơ bản của toán học đại số và xác suất thống kê được sử dụng vào các chương sau của đề tài. Các khái niệm về các cấu trúc đại số như: nhóm, vành, trường, vành đa thức, ma trận, vectơ, …. Các khái niệm về xác suất thống kê như: xác suất, đại lượng ngẫu nhiên và hàm phân phối, các đặc trưng của các đại lượng ngẫu nhiên, lý thuyết mẫu,…và ước lượng hợp lý cực đại. CHƯƠNG 3: ƯỚC LƯỢNG HỢP LÝ CỰC ĐẠI Chương này chúng ta tìm hiểu kỹ hơn về MLE trên mô hình thống kê. Dẫn ra một vài ví dụ về ước lượng hợp lý cực đại trên một số mẫu dữ liệu quan sát và giải bài toán. CHƯƠNG 4: CÂY SINH LOÀI – MÔ HÌNH XÁC SUẤT THỐNG KÊ TRÊN CÂY SINH LOÀI Chương này giới thiệu cây sinh loài, mô hình xác suất thống kê trên cây sinh loài. Ngoài ra cũng giới thiệu một số mô hình thường sử dụng hiện nay trên cây sinh loài như mô hình Neyman 2 trạng thái, Jukes – Cantor, Kimura với 2 và 3 tham số. Bùi Văn Đồng Trang 10 Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ CHƯƠNG 5: BẤT BIẾN TRÊN CÂY SINH LOÀI Trong chương này, giới thiệu tổng quát hóa mô hình xác suất thống kê trên sinh loài. Chỉ ra cấu trúc nhóm Aben đối với các mô hình sử dụng để từ đó tìm thành phần bất biến trên cây sinh loài. CHƯƠNG 6: GIẢI PHƯƠNG TRÌNH HỢP LÝ Chương này đưa ra phương pháp giải phương trình hợp lý dựa vào tính bất biến của cây sinh loài và mẫu dữ liệu quan sát. CHƯƠNG 7: CHƯƠNG TRÌNH THỰC HIỆN Chương này trình bày chi tiết hiện thực của chương trình. CHƯƠNG 8: TỔNG KẾT – ĐÁNH GIÁ Chương này tổng kết lại những công việc đã làm được, sau đó nêu ra những đóng góp và hướng phát triển của luận văn. Bùi Văn Đồng Trang 11 Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ Chương 2. CƠ SỞ LÝ THUYẾT VỀ CÁC CẤU TRÚC ĐẠI SỐ VÀ XÁC SUẤT THỐNG KÊ Các khái niệm cơ bản của đại số được trình bày ở phần đầu của chương này. Tiếp theo đó là phần giới thiệu về những khái niệm về xác suất thống kê trong đó có phần khái quát về ước lượng hợp lý cực đại. 2.1. Một số cấu trúc đại số cơ bàn 2.1.1. Lý thuyết nhóm Định nghĩa 1: Một nhóm là một cặp (G , ) trong đó G là một tập hợp không rỗng và là một luật hợp thành trên G thỏa mãn 3 điều kiện sau: (i) Luật hợp thành là kết hợp, tức là: ( x y) z = x ( y z ) với mọi x, y, z ∈ G . (ii) Có một phần tử e ∈ G , được gọi là phần tử trung lập, có tính chất x e=e x= x với mọi x ∈ G . Phần tử e còn được gọi là phần tử đơn vị của G . (iii) Với mọi x ∈ G , có một phần tử x , ∈ G , được gọi là nghịch đảo của x sao cho x x, = x, x = e Nếu luật hợp thành đã rõ và không nhầm lẫn gì, người ta cũng nói G là một nhóm. Định nghĩa 2: Nhóm (G , ) được gọi là giao hoán (hay Abel) nếu: x y=y x với mọi x, y ∈ G . Định nghĩa 3: Giả sử G và G ' là các nhóm (với luật hợp thành viết theo lối nhân). Một ánh xạ ϕ : G → G ' được gọi là một đồng cấu nhóm nếu: ϕ ( xy ) = ϕ ( x)ϕ ( y ) với mọi x, y ∈ G . Định nghĩa 4: Một đồng cấu nhóm đồng thời là một song ánh được gọi là một đẳng cấu nhóm. Định nghĩa 5: Hạt nhân và ảnh của đồng cấu nhóm ϕ : G → G ' được định nghĩa như sau: Bùi Văn Đồng Trang 12 Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ Kerϕ := {x ∈ G : ϕ ( x ) = e, } = ϕ −1 (e, ) Im ϕ := {ϕ ( x) : x ∈ G } = ϕ (G ) trong đó e, là đơn vị trong G ' . Định nghĩa 6: Giả sử G là một nhóm. Một tập con không rỗng S ⊂ G được gọi là một nhóm con của G nếu S khép kín đối với luật hợp thành trong G (tức là xy ∈ S với mọi x, y ∈ S ) và khép kín đối với phép lấy nghịch đảo trong G (tức là x −1 ∈ S với mọi x ∈ S ). 2.1.2. Lý thuyết vành Định nghĩa 7: Ta gọi là vành mỗi tập hợp R ≠ ∅ cùng với hai phép toán hai ngôi, gồm phép cộng +:R× R → R ( x, y ) x+ y và phép nhân •: R× R → R ( x, y ) xy thỏa mãn ba điều kiện sau đây: (i) R là một nhóm Abel đối với phép cộng. (ii) Phép nhân có tính kết hợp. (iii) Phép nhân phân phối về hai phía đối với phép cộng: (x + y)z = xz + yz, z(x + y) = zx + zy với mọi x, y, z ∈ R . Khi hai phép toán đều đã rõ, ta sẽ nói đơn giản: R là một vành. Định nghĩa 8: Vành R được gọi là vành giao hoán nếu phép nhân của nó giao hoán. Định nghĩa 9: Giả sử R là một vành. Tập con S ⊂ R được gọi là một vành con của R nếu S là một nhóm con của nhóm cộng R và khép kín đối với phép nhân, tức là x, y ∈ R kéo theo xy ∈ S . Định nghĩa 10: (i) Một iđêan trái của vành R là một vành con A ⊂ R có tính hấp thụ đối với phép nhân từ bên trái, tức là ra ∈ A, ∀r ∈ R, ∀a ∈ A (ii) (iii) Một iđêan phải của vành R là một vành con A ⊂ R có tính hấp thụ đối với phép nhân từ bên phải, tức là ar ∈ A, ∀r ∈ R, ∀a ∈ A Nếu vành con A ⊂ R vừa là một iđêan trái, vừa là một iđêan phải thì nó được gọi là một iđêan (hai phía) của R. Bùi Văn Đồng Trang 13 Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ Định lí : Giả sử A là một iđêan của vành R, thì: (i) Lớp xy + A chỉ phụ thuộc vào các lớp x + A và y + A mà không phụ thuộc vào sự lựa chọn của các phần tử x, y từ các lớp đó. (ii) X/A cùng với 2 phép toán ( x + A, y + A) x+ y+ A ( x + A, y + A) xy + A là một vành gọi là vành thương của R trên A. Định nghĩa 11: Giả sử R là một vành (giao hoán và có đơn vị). Iđêan A của R được gọi là nguyên tố nếu A ≠ R và với mọi x, y ∈ R , từ chỗ xy ∈ A suy ra hoặc x ∈ A hoặc y ∈ A . 2.1.3. Trường Định nghĩa 12: (i) Vành có đơn vị R được gọi là một thể nếu 1 ≠ 0 và mọi phần tử khác 0 trong R đều khả nghịch, nói cách khác, nếu R \ {0} là một nhóm đối với phép nhân. (ii) Mỗi thể giao hoán được gọi là một trường. Chúng ta đã biết một số trường số quen thuộc như: Q, R, C . 2.1.4. Vành đa thức Định nghĩa 13: Vành P được gọi là vành đa thức của ẩn x lấy hệ tử trong A, hay vắn tắt vành đa thức của ẩn x trên A, và kí hiệu là A[x]. Các phần tử của vành đó gọi là đa thức của ẩn x lấy hệ tử trong A. Trong một đa thức f ( x ) = a0 x 0 + a1 x1 + ... + an x n các ai , i = 0, 1,..., n gọi là các hệ tử của đa thức. Các ai x i được gọi là các hạng tử của đa thức. Đa thức có tất cả hệ tử bằng 0 gọi là đa thức 0. Định nghĩa 14: Giả sử A là một vành giao hoán có đơn vị. Ta đặt A1 = A[ x1 ] An = An−1[ xn ] vành An = An −1[ xn ] kí hiệu là A[ x1 , x2 ,..., xn ] và gọi là vành đa thức của n ẩn x1 , x2 ,..., xn lấy hệ tử trong vành A. Một phần tử của An gọi là một đa thức của n ẩn x1 , x2 ,..., xn lấy hệ tử trong vành A, người ta kí hiệu bằng f ( x1 , x2 ,..., xn ) hay g ( x1 , x2 ,..., xn ) … Định nghĩa 15: Giả sử f ( x1 , x2 ,..., xn ) ∈ A[ x1 , x2 ,..., xn ] là một đa thức khác 0 f ( x1 , x2 ,..., xn ) = c1 x1a11 ...xna1n + ... + cm x1am1 ...xnamn Bùi Văn Đồng Trang 14 Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ với các ci ≠ 0, i = 1,...., m và (ai1 ,..., ain ) ≠ (a j1 ,..., a jn ) khi i ≠ j . Ta gọi bậc của hạng tử ci x1ai1 ...xnain là tổng các số mũ đối với ẩn xi số mũ ai1 + ... + ain của các ẩn. Bậc của đa thức (đối với toàn thể các ẩn) là số lớn nhất trong các bậc của các hạng tử của nó. Đa thức 0 là đa thức không có bậc. Nếu các hạng tử của f ( x1 , x2 ,..., xn ) có cùng bậc k thì f ( x1 , x2 ,..., xn ) gọi là một đa thức thuần nhất cấp bậc k hay một dạng bậc k. Đặc biệt một dạng bậc nhất gọi là dạng tuyến tính, một dạng bậc 2 gọi là dạng toàn phương, một dạng bậc 3 gọi là dạng lập phương. 2.1.5. Ma trận Một ma trận A là một bảng có m × n phần tử lấy ở vành R, viết như sau: ⎡ a11 a12 ⎢a a22 A = ⎢ 21 ⎢ ⎢ ⎣ am1 am 2 a1n ⎤ a2 n ⎥ ⎥ ⎥ ⎥ amn ⎦ Các số aij được viết thành m dòng và n cột, chúng mang hai chỉ số: chỉ số i nói lên dòng và j nói lên cột mà aij được đặt trong bảng. Mỗi aij được gọi là một thành phần của ma trận. Một ma trận kiểu (m, n) là một ma trận có m dòng và n cột. Khi m = n thì ta bảo ta có một ma trận vuông cấp n. Ma trận chuyển vị của ma trận A được kí hiệu là AT được định nghĩa như sau: ⎡ a11 a21 ⎢a a22 T A = ⎢ 12 ⎢ ⎢ ⎣ an1 am 2 am1 ⎤ am 2 ⎥ ⎥ ⎥ ⎥ anm ⎦ hay ma trận AT là ma trận A nhưng chuyển dòng thành cột và cột thành dòng. 2.1.6. Định thức Giả sử A là một ma trận vuông cấp n (n ≥ 1) ⎡ a11 a12 ⎢a a22 A = ⎢ 21 ⎢ ⎢ ⎣ an1 an 2 a1n ⎤ a2 n ⎥ ⎥ ⎥ ⎥ ann ⎦ Định thức của ma trận A là gọi là det(A) hay | A | được định nghĩa như sau theo cách triển khai theo dòng i: Bùi Văn Đồng Trang 15 Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ det( A) = ai1 Ai1 + ai2 Ai2 + ... + ain Ain trong đó Aij = (−1)i + j M ij với M ij là định thức cấp n -1 suy ra từ A bằng cách bỏ dòng thứ i và cột thứ j. Aij được gọi là phần bù đại số của aij ta đi đến tính n định thức cấp n-1. Ma trận có một phần tử thì định thức bằng chính phần tử đó. 2.1.7. Không gian vector K là một trường, chủ yếu là Q, R, C , mà các phần tử kí hiệu là: λ , μ , ν ,... , E là một tập hợp mà các phần tử là x, y, z ,... Giả sử cho 2 phép toán: - Phép cộng: E×E → E ( x, y ) x+ y và - Phép nhân: Một phần tử của K với một phần tử E: K×E→E (λ , x ) λx thỏa mãn các tính chất sau với mọi x, y ∈ E và mọi λ , μ ∈ K : (i) E cùng với phép cộng là một nhóm Abel. (ii) Phép nhân phân phối đối với phép cộng của trường K: (λ + μ )x = λ x + μ x (iii) Phép nhân phân phối đối với phép cộng của E: λ ( x + y) = λ x + λ y (iv) Phép nhân có tính kết hợp: λ ( μ x) = (λμ ) x (v) 1x = x , 1 là đơn vị của trường K. Lúc đó ta bảo E cùng với hai phép toán: Cộng trong E và nhân đối với một phần tử trong trường K, thỏa tính chất (i), (ii), (iii), (iv) và (v) là một không gian vector trên trường K hay K – không gian vector (cũng gọi tắt là không gian vector khi không cần chỉ rõ K). Các phần tử của E gọi là các vector; các phần tử của K gọi là vô hướng. Phép toán + gọi là phép cộng vector, phép toán nhân với một phần tử của trường K được gọi là phép nhân vector với vô hướng. Độc lập tuyến tính và phụ thuộc tuyến tính Giả sử x1 , x2 , ..., xn ( n ≥ 1) là n vectơ của K – không gian vector E và λ1 , λ2 , ..., λn là n phần tử của trường K. Vectơ x = λ1 x1 + λ2 x2 + ... + λn xn Bùi Văn Đồng Trang 16 Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ n còn được viết là: x = ∑ λi xi ∈ E và gọi là tổ hợp tuyến tính của các vectơ i =1 x1 , x2 , ..., xn với các hệ tử λ1 , λ2 , ..., λn . Trong trường hợp K là một trường số, các λi sẽ gọi là hệ số thay cho hệ tử. Hệ n vectơ x1 , x2 , ..., xn ( n ≥ 1) trong K không gian vectơ E gọi là độc lập tuyến tính khi vectơ 0 chỉ có một biểu thị tuyến tính, đó là biểu thị tuyến tính tầm thường, qua hệ vectơ đó. Vậy hệ x1 , x2 , ..., xn ( n ≥ 1) độc lập tuyến tính khi và chỉ khi n ∑ λi xi = 0 kéo theo λ1 = λ2 = i =1 ... = λn = 0 Hệ vectơ x1 , x2 , ..., xn ( n ≥ 1) không độc lập tuyến tính thì gọi là phụ thuộc tuyến tính. Hạng của một hệ hữu hạn vectơ Giả sử I là một tập hữu hạn và ∅ ≠ J ⊂ I . Giả sử cho hệ vectơ ( xi )i∈I trong Kkhông gian vector E. Hệ con ( x j ) j∈J gọi là một hệ con độc lập tuyến tính tối đại của hệ đã cho nếu nó là một hệ độc lập tuyến tính và nếu thêm bất cứ vector xi (i ∈ I − J ) nào vào hệ con đó thì ta đều được một hệ phụ thuộc tuyến tính. Cho hệ hữu hạn vector ( xi )i∈I trong K- không gian vector E. Người ta chứng minh được rằng số phần tử của mọi hệ con độc lập tuyến tính tối đại của nó bằng nhau và gọi là hạng của hệ vector đã cho. Hạng của vectơ (0) được coi bằng 0. Hạng của ma trận Ma trận A có m dòng và n cột với aij ∈ K . Hạng của A là hạng của hệ vector cột và người ta chứng minh nó cũng bằng hạng của vectơ dòng và bằng cấp cao nhất của các định thức con khác 0 của nó. Nếu A chứa một ma trận vuông cấp p có định thức khác 0, sao cho mọi ma trận vuông cấp p+1 chứa nó có định thức bằng 0, thì ma trận có hạng là p. Cơ sở và số chiều của một K – không gian vector Ở đây chúng ta chỉ đề cập tới các không gian vector có hữu hạn chiều. Giả sử E là một K – không gian vector. Giả sử tồn tại trong E một hệ vector độc lập tuyến tính (e1 , e2 ,..., en ) sao cho mọi vector của E đều biểu thị tuyến tính qua hệ đó. Lúc đó ta có thể nói hệ (e1 , e2 ,..., en ) là độc lập tuyến tính tối đại trong E. Và ta nói (e1 , e2 ,..., en ) là một cơ sở của K – không gian vector E và số chiều (hay vắn tắt là chiều) của E, kí hiệu là dim E, là số vectơ của cơ sở. Ta viết dim E = n; và gọi E là K - không gian vector n chiều. Bùi Văn Đồng Trang 17