Trích chọn sự kiện y sinh phức hợp dựa vào mô hình phân tích cây phụ thuộc trong văn bản về bệnh ung thư di truyền

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Phí Văn Thủy TRÍCH CHỌN SỰ KIỆN Y SINH PHỨC HỢP DỰA VÀO MÔ HÌNH PHÂN TÍCH CÂY PHỤ THUỘC TRONG VĂN BẢN VỀ BỆNH UNG THƯ DI TRUYỀN KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI - 2013 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Phí Văn Thủy TRÍCH CHỌN SỰ KIỆN Y SINH PHỨC HỢP DỰA VÀO MÔ HÌNH PHÂN TÍCH CÂY PHỤ THUỘC TRONG VĂN BẢN VỀ BỆNH UNG THƯ DI TRUYỀN KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: TS. Phan Xuân Hiếu Cán bộ đồng hướng dẫn: ThS. Trần Mai Vũ VIETNAM NATIONAL UNIVERSITY, HANOI UNIVERSITY OF ENGINEERING AND TECHNOLOGY Phi Van Thuy A COMPLEX EVENT EXTRACTION METHOD BASED ON DEPENDENCY PARSING FOR CANCER GENETICS DATASET Major: Information Technology Supervisor: Dr. Xuan-Hieu Phan Co-Supervisor: MSc. Mai-Vu Tran HA NOI - 2013 Lời cảm ơn Trước tiên, tôi xin gửi lời cảm ơn và lòng biết ơn sâu sắc nhất tới Phó Giáo sư Tiến sĩ Hà Quang Thụy, Tiến sĩ Phan Xuân Hiếu, và Thạc sĩ Trần Mai Vũ – những người đã tận tình chỉ bảo và hướng dẫn tôi trong quá trình thực hiện khoá luận tốt nghiệp. Tôi xin gửi lời cảm ơn chân thành tới Phó Giáo sư Tiến sĩ Nigel H. Collier, thuộc Viện Thông tin quốc gia Nhật Bản (NII), người đã tận tình hỗ trợ về kiến thức chuyên môn, giúp đỡ tôi hoàn thành khóa luận. Tôi chân thành cảm ơn các thầy, cô và cán bộ của trường Đại Học Công Nghệ đã tạo những điều kiện thuận lợi cho tôi học tập và nghiên cứu. Tôi cũng xin gửi lời cảm ơn tới các anh chị và các bạn sinh viên trong phòng thí nghiệm KT-Lab đã giúp tôi rất nhiều trong việc thu thập và xử lý dữ liệu. Cuối cùng, tôi muốn gửi lời cảm ơn tới gia đình và bạn bè, những người thân yêu luôn bên cạnh, động viên tôi trong suốt quá trình thực hiện khóa luận tốt nghiệp. Tôi xin chân thành cảm ơn ! Hà Nội, ngày 15 tháng 5 năm 2013 Sinh viên Phí Văn Thủy i TRÍCH CHỌN SỰ KIỆN Y SINH PHỨC HỢP DỰA VÀO MÔ HÌNH PHÂN TÍCH CÂY PHỤ THUỘC TRONG VĂN BẢN VỀ BỆNH UNG THƯ DI TRUYỀN Phí Văn Thủy Khóa QH-2009-I/CQ , ngành Công nghệ thông tin Tóm tắt Khóa luận tốt nghiệp: Thuật ngữ trích chọn sự kiện y sinh học được sử dụng để đề cập đến bài toán trích chọn sự mô tả về các hoạt động và quan hệ giữa một hoặc nhiều thực thể từ tài liệu y sinh học. Việc tự động nhận dạng bất kì đối tượng của một lớp sự kiện riêng, trích chọn các tham số liên quan của chúng và biểu diễn thông tin được trích chọn vào một dạng có cấu trúc từ các công trình khoa học giúp cộng đồng nghiên cứu y sinh học nhanh chóng thu nhận được các kết quả nghiên cứu mới nhất trong lĩnh vực liên quan mật thiết tới việc đảm bảo sức khỏe con người. Các kết quả mới nhất cho thấy hiệu năng khi trích chọn các sự kiện phức hợp (sự kiện có thể nhận tham số là thực thể hoặc sự kiện khác) chỉ đạt khoảng 40-50% F1 tại BioNLP Shared Task 2011. Khóa luận này đề xuất một mô hình học máy cho bài toán trích chọn sự kiện y sinh phức hợp và áp dụng vào Cancer Genetics (CG) task – một bài toán trích chọn thông tin trong BioNLP Shared Task (ST) 2013. Mục đích của CG task là trích chọn thông tin tự động từ các văn bản về quá trình sinh học, liên quan đến sự phát triển và tiến triển của bệnh ung thư. Mô hình của chúng tôi gồm ba thành phần chính: (1) nhận diện trigger; (2) trích chọn ứng viên sự kiện; (3) xếp hạng và đưa ra kết quả. Khi đánh giá trên tập dữ liệu phát triển được cung cấp bởi BioNLP-ST 2013, với khoảng 1000 câu lấy từ PubMed, chúng tôi thu được kết quả bước đầu khá khả quan: độ đo F1 khi trích chọn các sự kiện phức hợp đạt từ 50% đến 70%. Mô hình mới phù hợp với miền dữ liệu về bệnh ung thư di truyền và cho hiệu năng tốt hơn mô hình cơ sở chúng tôi đưa ra. Từ khóa: Event extraction, Dependency tree, Cancer Genetics Task. ii A COMPLEX EVENT EXTRACTION METHOD BASED ON DEPENDENCY PARSING FOR CANCER GENETICS DATASET Phi Van Thuy Course: QH-2009-I/CQ , major: Information technology Abstract: The term biomedical event extraction is used to refer to the task of extracting descriptions of actions and relations among one or more entities from the biomedical literature. Generally, event extraction is to identify any instance of a particular class of events in a biomedical text, to extract the relevant arguments of the event, and to represent the extracted information into a structured form. This helps the community of biomedical researchers to quickly get the latest research results in the fields closely related to ensuring human health. The final results enabled to observe the state-of-the-art performance of the community on the bio-event extraction task, which showed that the automatic extraction of complex events was a lot more challenging, having achieved 40-50% in F1-score, in BioNLP Shared Task 2011. In this thesis, we propose a machine learning model for complex event extraction task and apply to Cancer Genetics (CG) task – the information extraction task in BioNLP-ST 2013. The CG task aims to advance the automatic extraction of information from statements on the biological processes relating to the development and progression of cancer. Our model consists of three modules: (1) trigger detection; (2) candidate event extraction; (3) ranking and returning output. Our approach obtains competitive results in the extraction of complex events from the BioNLP-ST Shared Task 2013 with a F1-score of 50-70% in development. The new model fits the data domain of cancer genetics and perform better than the base model we proposed. Keywords: Event extraction, Dependency tree, Cancer Genetics Task. iii Lời cam đoan Em xin cam đoan rằng đây là công trình nghiên cứu của mình, có sự giúp đỡ từ giáo viên hướng dẫn là Tiến sĩ Phan Xuân Hiếu và Thạc sĩ Trần Mai Vũ. Các nội dung nghiên cứu và kết quả trong đề tài này là trung thực, không sao chép từ bất cứ nguồn nào có sẵn. Tất cả những tham khảo từ các nghiên cứu liên quan đều được nêu nguồn gốc một cách rõ ràng từ danh mục tài liệu tham khảo trong khóa luận. Trong khóa luận, không có việc sao chép tài liệu, công trình nghiên cứu của người khác mà không chỉ rõ về tài liệu tham khảo. Nếu phát hiện có bất kỳ sự gian lận nào, em xin hoàn toàn chịu trách nhiệm trước hội đồng, cũng như kết quả khóa luận tốt nghiệp của mình. Sinh viên Phí Văn Thủy iv Mục lục Tóm tắt nội dung ........................................................................................................ i Lời cam đoan ............................................................................................................. ii Mục lục ...................................................................................................................... iv Danh sách bảng ........................................................................................................ vi Danh sách hình vẽ ................................................................................................... vii Bảng các ký hiệu .................................................................................................... viii Mở đầu ....................................................................................................................... 1 Chương 1. Bài toán trích chọn sự kiện liên quan đến bệnh ung thư di truyền trong văn bản y sinh học ........................................................................................... 3 1.1. Giới thiệu chung ...................................................................................... 3 1.2. Các khái niệm liên quan đến bài toán ...................................................... 5 1.3. Phát biểu bài toán ..................................................................................... 7 1.4. Khó khăn và thách thức ........................................................................... 8 1.5. Phương pháp đánh giá ............................................................................. 9 1.5.1. Khớp nhau hoàn toàn ...................................................................... 10 1.5.2. Khớp biên xấp xỉ ............................................................................ 10 Chương 2. Các hướng tiếp cận giải quyết bài toán trích chọn sự kiện trong văn bản y sinh học ................................................................................................... 11 2.1. Trích chọn sự kiện dựa vào phân tích phụ thuộc cú pháp ..................... 11 2.2. Trích chọn sự kiện dựa vào hệ thống đường ống .................................. 12 2.3. Mô hình học máy đã đề xuất cho bài toán trích chọn sự kiện liên quan đến bệnh ung thư di truyền .............................................................................. 14 2.3.1. Thành phần nhận diện trigger ........................................................ 15 2.3.2. Thành phần trích chọn sự kiện đơn ............................................... 16 2.3.3. Thành phần trích chọn sự kiện phức ............................................. 17 Chương 3. Mô hình giải quyết bài toán trích chọn sự kiện y sinh phức hợp dựa vào mô hình phân tích cây phụ thuộc ............................................................ 19 v 3.1. Cơ sở lý thuyết ....................................................................................... 19 3.1.1. Chuyển đổi cấu trúc sự kiện sang dạng biểu diễn cây phụ thuộc .. 19 3.1.2. Giải thuật Earley paresr ................................................................. 21 3.2. Mô hình đề xuất giải quyết bài toán ...................................................... 23 3.2.1. Thành phần nhận diện trigger ........................................................ 24 3.2.2. Thành phần trích chọn ứng viên sự kiện ....................................... 25 3.2.3. Thành phần xếp hạng và đưa ra kết quả ........................................ 26 Chương 4. Thực nghiệm và đánh giá .................................................................... 28 4.1. Môi trường và dữ liệu thực nghiệm ....................................................... 28 4.1.1. Môi trường thực nghiệm ................................................................ 28 4.1.2. Dữ liệu thực nghiệm ...................................................................... 28 4.2. Giới thiệu phần mềm thực nghiệm ........................................................ 31 4.3. Thực nghiệm .......................................................................................... 32 4.3.1. Hướng tiếp cận thực nghiệm .......................................................... 32 4.3.2. Thực nghiệm nhận diện trigger ...................................................... 32 4.3.3. Thực nghiệm trích chọn sự kiện phức hợp .................................... 34 4.4. Nhận xét và thảo luận ............................................................................ 36 Kết luận và định hướng .......................................................................................... 39 Tài liệu tham khảo .................................................................................................. 40 Tiếng Anh ........................................................................................................ 40 vi Danh sách bảng Bảng 1: Các kiểu thực thể trong CG task ........................................................................ 5 Bảng 2: Các kiểu sự kiện trong CG task ......................................................................... 6 Bảng 3: Kết quả với tập kiểm thử theo các lớp sự kiện ................................................. 12 Bảng 4: Phân loại các kiểu sự kiện trong CG task ....................................................... 17 Bảng 5: Kết quả với trích chọn các sự kiện phức hợp liên quan đến bệnh ung thư di truyền ............................................................................................................................. 18 Bảng 6: Các loại đặc trưng trong thành phần nhận diện trigger ................................. 26 Bảng 7: Môi trường thực nghiệm .................................................................................. 30 Bảng 8: Thống kê chung về dữ liệu thực nghiệm .......................................................... 33 Bảng 9: Thống kê các sự kiện trong tập dữ liệu ............................................................ 33 Bảng 10: Các loại đặc trưng trong nhận diện trigger .................................................. 35 Bảng 11: Kết quả với trích chọn các sự kiện phức hợp liên quan đến bệnh ung thư di truyền dựa vào mô hình phân tích cây phụ thuộc ......................................................... 36 Bảng 12: Một số kiểu lỗi nhận diện thiếu sự kiện ......................................................... 36 Bảng 13: Thống kê các kiểu thực thể/sự kiện là tham số cho sự kiện Regulation ........ 37 Bảng 14: Mẫu các sự kiện phức hợp trong CG task ..................................................... 38 Bảng 15: So sánh kết quả giữa mô hình cơ sở và mô hình mới đề xuất (dạng bảng) ... 38 vii Danh sách hình vẽ Hình 1: Trang chủ BioNLP-ST 2013 .................................................................................. 4 Hình 2: Ví dụ về trích chọn sự kiện liên quan đến bệnh ung thư di truyền ..................... 5 Hình 3: Minh họa đầu vào và đầu ra của bài toán trích chọn sự kiện liên quan đến bệnh ung thư di truyền ..................................................................................................... 8 Hình 4: Cấu trúc sự kiện y sinh học ................................................................................ 8 Hình 5: Mô hình của hướng tiếp cận dựa vào phân tích phụ thuộc cú pháp ................ 11 Hình 6: Hệ thống EventMine ......................................................................................... 13 Hình 7: Mô hình giải quyết bài toán Trích chọn sự kiện liên quan đến bệnh ung thư di truyền ............................................................................................................................. 14 Hình 8a: Câu gốc với các sự kiện ................................................................................. 20 Hình 8b: Sau khi chuyển đổi sang sự phụ thuộc sự kiện ............................................... 20 Hình 9: Mô hình giải quyết bài toán Trích chọn sự kiện y sinh phức hợp trong văn bản về bệnh ung thư di truyền .............................................................................................. 25 Hình 10: Minh họa dạng biểu diễn hai cây sự kiện cho hai sự kiện phức hợp ............. 27 Hình 11: Các mô-đun chính trong phần mềm thực nghiệm .......................................... 34 Hình 12: Ví dụ về một câu trong tập dữ liệu huấn luyện cho nhận diện trigger ................... 35 Hình 13: So sánh kết quả giữa mô hình cơ sở và mô hình mới đề xuất (dạng biều đồ)38 viii Bảng các ký hiệu Từ viết tắt Thuật ngữ BioNLP-ST BioNLP Shared Task CG Task Cancer Genetics Task SVM Support Vector Machine 1 Mở đầu Trích chọn sự kiện y sinh học là bài toán trích chọn sự mô tả về các hoạt động và quan hệ giữa một hoặc nhiều thực thể từ tài liệu y sinh học. Đây là một vấn đề khó trong lĩnh vực xử lý ngôn ngữ tự nhiên [10] [11], nhận được nhiều sự quan tâm của các nhà nghiên cứu, các hội nghị lớn trên thế giới như: ACL (Association for Computational Linguistics), BioNLP-ST (BioNLP Shared Task), CoNLL (Conference on Computational Natural Language Learning) ... Tại BioNLP-ST 2013, trích chọn sự kiện liên quan đến bệnh ung thư di truyền (Cancer Genetics (CG) Task) là một trong sáu bài toán mới nhất cần được giải quyết. Nếu một phương pháp được đề xuất cho kết quả tốt thì nhiều bài toán khác như: xác định đồng tham chiếu1 (Co-reference), xác định ngữ cảnh phủ định và suy luận của sự kiện (Negative and speculation recognition), trích chọn quan hệ giữa các thực thể2 (Entity Relations) … sẽ được cải thiện về chất lượng một cách đáng kể. Các kết quả mới nhất cho bài toán trích chọn sự kiện, cho thấy hiệu năng với trích chọn sự kiện đơn (simple event) – chỉ nhận các thực thể là tham số (chẳng hạn gene expression, localization...), có thể đạt khoảng 70% F1, nhưng với trích chọn các sự kiện phức hợp (complex event) – có thể nhận cả thực thể và sự kiện khác là tham số (chẳng hạn regulation, positive regulation...), bài toán gặp rất nhiều thách thức, hiệu năng chỉ đạt khoảng 40-50% F1 [12]. Xuất phát từ lý do đó và mong muốn nâng cao chất lượng đề tài nghiên cứu khoa học sinh viên 2012 – 2013 (“Một mô hình học máy trích chọn sự kiện y sinh trong văn bản về bệnh ung thư di truyền”), khóa luận chọn bài toán trích chọn sự kiện y sinh phức hợp trong văn bản về bệnh ung thư di truyền, là nội dung tập trung nghiên cứu và xây dựng mô hình giải quyết. Trích chọn sự kiện phức hợp liên quan đến bốn kiểu sự kiện trong CG Task: Regulation, Positive regulation, Negative regulation và Planned process. Các phương pháp tiếp cận ban đầu chủ yếu dựa trên các phương pháp tiếp cận kinh nghiệm. Cho tới nay có rất nhiều phương pháp tiếp cận khác nhau đã được đề xuất để giải quyết bài toán chung trích chọn sự kiện y sinh học. Khóa luận này giới thiệu hai hướng tiếp cận giải quyết điển hình: dựa vào phân tích phụ thuộc cú pháp và dựa vào hệ thống đường ống. Những công trình này mang tính ứng dụng cao, đang ngày càng được cải tiến cho hiệu quả tốt hơn. 1 https://sites.google.com/site/bionlpst/home/protein-gene-coreference-task 2 https://sites.google.com/site/bionlpst/home/entity-relations 2 Dựa trên những hướng tiếp cận này cùng với một mô hình học máy đã đề xuất trong đề tài nghiên cứu khoa học sinh viên, chúng tôi đề xuất một mô hình phân tích cây phụ thuộc cho việc giải quyết bài toán trích chọn sự kiện y sinh phức hợp trong văn bản về bệnh ung thư di truyền. Kết quả thực nghiệm bước đầu cho thấy mô hình mới phù hợp với miền dữ liệu y sinh và cho hiệu năng tốt hơn mô hình cơ sở đã đề xuất: độ đo F1 khi trích chọn các sự kiện phức hợp đạt từ 50% đến 70%. Các kết quả này khá khả quan, thể hiện được ưu điểm của mô hình đề xuất. Nội dung của khóa luận bao gồm có 4 chương: Chương 1: Giới thiệu khái quát về bài toán trích chọn sự kiện liên quan đến bệnh ung thư di truyền cũng như các khái niệm liên quan. Chương 2: Giới thiệu một số hướng tiếp cận giải quyết bài toán trích chọn sự kiện y sinh học, bao gồm hướng tiếp cận dựa vào phân tích phụ thuộc cú pháp và hướng tiếp cận dựa vào hệ thống đường ống. Đây là cơ sở lý thuyết, phương pháp luận quan trọng để khóa luận đưa ra mô hình trích chọn các sự kiện y sinh phức hợp ở chương 3. Chương 3: Trên cơ sở những hướng tiếp cận trình bày ở chương 2 và thông qua khảo sát miền dữ liệu văn bản y sinh học về bệnh ung thư di truyền, khóa luận đã lựa chọn phương pháp dựa vào mô hình phân tích cây phụ thuộc là cơ sở của việc giải quyết bài toán trích chọn sự kiện y sinh phức hợp. Nội dung chính của chương này trình bày một số đặc trưng của văn bản y sinh học về bệnh ung thư di truyền, bài toán trích chọn sự kiện y sinh phức hợp và mô hình đề xuất. Chương 4: Thực nghiệm, kết quả và đánh giá. Tiến hành thực nghiệm nhận diện trigger và trích chọn các sự kiện phức hợp dựa trên dập dữ liệu phát triển được cung cấp bởi BioNLP-ST 2013. Trong chương này đánh giá, so sánh kết quả giữa mô hình đề xuất và mô hình cơ sở mà khóa luận dựa trên. Phần kết luận và định hướng phát triển: Tóm lược những kết quả đạt được của khóa luận. Đồng thời đưa ra những hạn chế, những điểm cần khắc phục và đưa ra định hướng nghiên cứu trong thời gi