Khóa luận Phân lớp câu hỏi hướng tới tìm kiếm ngữ nghĩa tiếng việt trong lĩnh vực y tế

) – X là diện tích. Với 5 qui tắc biến đổi trên, một câu hỏi bất kỳ đều được chuyển sang dạng QLL, với lợi thế về suy luận và tối ưu xử lý, câu hỏi dưới dạng QLL sẽ mang lại tốc độ tốt hơn và mang đặc thù ngữ nghĩa nhiều hơn. c. Tìm kiếm câu trả lời. Sau khi câu hỏi/truy vấn của người dùng được chuyển sang dạng QLL, hệ thống tiến hành tìm kiếm câu trả lời sẽ được thực hiện qua các phép toán logic với dữ liệu là các Ontology (mạng ngữ nghĩa) được xây dựng từ trước. Giả sử S2 là một câu truy vấn dạng QLL, hệ thống cần tìm ra câu trả lời cho S2. Chiến lược giải quyết như sau: 13 (1) Với mỗi một vị từ trong S2, xác định Ontology để tìm kiếm (sử dụng kết quả từ bước phân lớp câu hỏi ở trên), tìm ra đối tượng chứa câu trả lời từ tập các đối tượng thuộc miền Ontology đã chỉ ra, trong đó: o Đối tượng chứa câu trả lời phải có một thuộc tính có độ tương đồng với một trong các tham số của vị từ. Ví dụ: với vị từ diện_tích(Hà_Nôi), trong Ontology về địa lý đối tượng chứa câu trả lời sẽ là thành_phố.Hà_Nội - ở đây có sự tương đồng về tên của đối tượng với tham số của vị từ. o Thông tin trả lời cho vị từ hoặc thông tin về vị từ được mô tả bằng tên gọi của lớp hay bằng thuộc tính của một lớp có trong Ontology. Ví dụ : với vị từ diện_tích (Hà_Nội) thì câu trả lời được chứa trong một thuộc tính của đối tượng thành_phố.Hà_Nội. (2) Lặp lại bước (1) cho đến khi tìm được đối tượng chứa thông tin trả lời, hoặc đã tìm qua tất cả các đối tượng mà không có câu trả lời. Vị từ nào không đưa lại kết quả (không xác định được giá trị) sẽ được loại bỏ ra khỏi S2. Câu trả lời của truy vấn sẽ là phép tính tổ hợp giá trị của các vị từ. Thay vì đưa ra câu trả lời chính xác hoặc khi không tìm được câu trả lời chính xác cho câu hỏi đưa vào, hệ thống có thể trả về thông tin của đối tượng được xác định là có thể trả lời cho câu hỏi. d. Mạng ngữ nghĩa. Mạng ngữ nghĩa là cơ sở dữ liệu cho hệ thống tìm kiếm ngữ nghĩa. Về cơ bản, một mạng ngữ được hình thành từ một tập các thông tin mang ngữ nghĩa có quan hệ với nhau có thể là tập các Ontology hay tập các trang Web ngữ nghĩa. Với các máy tìm kiếm thông thường, cơ sở dữ liệu cho tìm kiếm được thu thập tự động từ các trang Web hiện có trên internet. Và quá trình xử lý các thông tin của các trang Web lấy về không gặp nhiều khó khăn. Trái lại, đối với máy tìm kiếm ngữ nghĩa thì công việc xây cơ sở cho tìm kiếm không đơn giản bởi hai nguyên nhân sau: • Số lượng các trang Web ngữ nghĩa còn hạn chế. • Việc xây dựng Ontology cho từng miền đòi hỏi sự hợp tác của nhiều chuyên gia miền trong thời gian lớn. Hiện nay có một số công cụ hỗ trợ việc xây dựng Ontology như: Protégé hay GATE… 1 2 3 14 Chương 2. Tìm kiếm ngữ nghĩa trong tiếng Việt 2.1. Tổng quan về cơ sở cho tìm kiếm ngữ nghĩa tiếng Việt Từ cấu trúc cơ bản của một hệ thống tìm kiếm ngữ nghĩa đã được trình bày ở trên cho thấy để xây dựng được một hệ thống tìm kiếm ngữ nghĩa trong tiếng Việt trước tiên phải giải quyết hai bai toán: (1) Xây dựng bộ phân lớp câu hỏi tiếng Việt (2) Xây dựng một mạng ngữ nghĩa tiếng Việt Hai bài toán trên đều chịu sự chi phối của yếu tố ngôn ngữ. Tiếng Việt có những đặc trưng riêng biệt về: chữ viết – chính tả, âm tiết và từ … do vậy đối với bài toán (1) và (2) phải tích hợp được những đặc trưng này. Hiện nay chưa có hệ thống tìm kiếm ngữ nghĩa tiếng Việt nào được công bố. Nguyên nhân chính là do tập cơ sở dữ liệu về ngữ nghĩa tiếng Việt còn ít không như tiếng Anh, Pháp… Trên thế giới có rất nhiều tổ chức, viện nghiên cứu, trường đại học đã đưa ra các Ontology trong những miền lĩnh vực khác nhau, có thể kể đến như: • Miền Y tế có các Ontology như : Semantic Mining1 một Ontology về khai phá dữ liệu trong Y tế, hay Disease Ontology là Ontology về các từ khóa chuyên ngành y khoa được phát triển bởi khoa Tin sinh tại Center for Genetic Medicine2 ... • Miền thương mại, kinh doanh: điển hình là Ontology-Based Business Process Management được nghiên cứu và phát triển bởi Jenz & Partner GmbH [16]. • Miền khoa học phổ thông: có Ontology về vật lý (Physical-Concepts được phát triển bởi Laboratory for Applied Ontology3) … • Và nhiều miền lĩnh vực khác. Có một số ít Ontolgy được công bố, điển hình là Ontology VN–KIM [4]. Ontology này bao gồm 347 lớp thực thể và 114 quan hệ và thuộc tính. Cơ sở tri thức của VN-KIM là một tập hợp các thực thể có tên phổ biến ở Việt Nam và Quốc tế, các thực thể chủ yếu thuộc các miền như: - Con người (Các nhà lãnh đạo quốc gia, giám đốc công ty, bác sỹ, nhà giáo, văn nghệ sỹ…) - Tổ chức, công ty (Các tổ chức xã hội, giáo dục, công ty…) 15 - Đơn vị hành chính (các tỉnh, thành phố, quận, huyện, phường, xã ở Việt Nam và các thành phố lớn trên thế giới) - Sông, núi (các sông, núi lớn ở Việt Nam và trên thế giới) - Đường (các đường ở TPHCM, Hà Nội, các tỉnh lộ, quốc lộ) Điều này cho thấy, tập các Ontology miền trong Tiếng Việt còn ít, đây là một trong những khó khăn cần giải quyết để sớm, tạo tiền đề phát triển những hệ thống mang ngữ nghĩa. 2.2. Một số đặc trưng của tiếng Việt Tiếng Việt thuộc ngôn ngữ đơn lập, tức là mỗi một tiếng (âm tiết) được phát âm tách rời nhau và được thể hiện bằng một chữ viết. Đặc điểm này thể hiện rõ rệt ở tất cả các mặt ngữ âm, từ vựng, ngữ pháp. Dưới đây trình bày một số đặc điểm của tiếng Việt theo các tác giả ở Trung tâm ngôn ngữ học Việt Nam đã trình bày [3]. 2.2.1 Đặc điểm ngữ âm Tiếng Việt có một loại đơn vị đặc biệt gọi là "tiếng", về mặt ngữ âm, mỗi tiếng là một âm tiết. Hệ thống âm vị tiếng Việt phong phú và có tính cân đối, tạo ra tiềm năng của ngữ âm tiếng Việt trong việc thể hiện các đơn vị có nghĩa. Nhiều từ tượng hình, tượng thanh có giá trị gợi tả đặc sắc. Khi tạo câu, tạo lời, người Việt rất chú ý đến sự hài hoà về ngữ âm, đến nhạc điệu của câu văn. 2.2.2 Đặc điểm từ vựng: Mỗi tiếng nói chung là một yếu tố có nghĩa. Tiếng là đơn vị cơ sở của hệ thống các đơn vị có nghĩa của tiếng Việt. Từ tiếng, người ta tạo ra các đơn vị từ vựng khác để định danh sự vật, hiện tượng..., chủ yếu nhờ phương thức ghép và phương thức láy. Việc tạo ra các đơn vị từ vựng ở phương thức ghép luôn chịu sự chi phối của quy luật kết hợp ngữ nghĩa, ví dụ: đất nước, máy bay, nhà lầu xe hơi, nhà tan cửa nát... Hiện nay, đây là phương thức chủ yếu để sản sinh ra các đơn vị từ vựng. Theo phương thức này, tiếng Việt triệt để sử dụng các yếu tố cấu tạo từ thuần Việt hay vay mượn từ các ngôn ngữ khác để tạo ra các từ, ngữ mới, ví dụ như tiếp thị, karaoke, thư điện tử (e-mail), thư thoại (voice mail), phiên bản (version), xa lộ thông tin, siêu liên kết văn bản, truy cập ngẫu nhiên, v.v. Việc tạo ra các đơn vị từ vựng ở phương thức láy thì quy luật phối hợp ngữ âm chi phối chủ yếu việc tạo ra các đơn vị từ vựng, chẳng hạn như chôm chỉa, chỏng chơ, đỏng đa đỏng đảnh, thơ thẩn, lúng lá lúng liếng, v.v. Vốn từ vựng tối thiểu của tiếng Việt phần lớn là các từ đơn tiết (một âm tiết, một tiếng). Sự linh hoạt trong sử dụng, việc tạo ra các từ ngữ mới một cách dễ dàng đã tạo điều kiện thuận lợi cho sự phát triển vốn từ, vừa phong phú về số lượng, vừa đa dạng trong hoạt động. Cùng một sự vật, hiện tượng, một hoạt động hay một đặc trưng, có thể có nhiều từ ngữ khác nhau biểu thị. Tiềm năng của vốn từ ngữ tiếng Việt được phát huy cao độ trong các phong cách chức năng ngôn ngữ, đặc biệt là trong phong cách ngôn ngữ 16 nghệ thuật. Hiện nay, do sự phát triển vượt bậc của khoa học-kĩ thuật, đặc biệt là công nghệ thông tin, thì tiềm năng đó còn được phát huy mạnh mẽ hơn. 2.2.3 Đặc điểm ngữ pháp: Từ của tiếng Việt không biến đổi hình thái. Đặc điểm này sẽ chi phối các đặc điểm ngữ pháp khác. Khi từ kết hợp từ thành các kết cấu như ngữ, câu, tiếng Việt rất coi trọng phương thức trật tự từ và hư từ. Việc sắp xếp các từ theo một trật tự nhất định là cách chủ yếu để biểu thị các quan hệ cú pháp. Trong tiếng Việt khi nói “Anh ta lại đến” là khác với “Lại đến anh ta”. Khi các từ cùng loại kết hợp với nhau theo quan hệ chính phụ thì từ đứng trước giữ vai trò chính, từ đứng sau giữ vai trò phụ. Nhờ trật tự kết hợp của từ mà "củ cải" khác với "cải củ", "tình cảm" khác với "cảm tình". Trật tự chủ ngữ đứng trước, vị ngữ đứng sau là trật tự phổ biến của kết cấu câu tiếng Việt. Phương thức hư từ cũng là phương thức ngữ pháp chủ yếu của tiếng Việt. Nhờ hư từ mà tổ hợp “anh của em” khác với tổ hợp “anh và em”, “anh vì em”. Hư từ cùng với trật tự từ cho phép tiếng Việt tạo ra nhiều câu cùng có nội dung thông báo cơ bản như nhau nhưng khác nhau về sắc thái biểu cảm. Ví dụ, so sánh các câu sau đây: - Ông ấy không hút thuốc. - Thuốc, ông ấy không hút. - Thuốc, ông ấy cũng không hút. Ngoài trật tự từ và hư từ, tiếng Việt còn sử dụng phương thức ngữ điệu. Ngữ điệu giữ vai trò trong việc biểu hiện quan hệ cú pháp của các yếu tố trong câu, nhờ đó nhằm đưa ra nội dung muốn thông báo. Trên văn bản, ngữ điệu thường được biểu hiện bằng dấu câu. Sự khác nhau trong nội dung thông báo được nhận biệt khi so sánh hai câu sau: - Đêm hôm qua, cầu gãy. - Đêm hôm, qua cầu gãy. Qua một số đặc điểm nổi bật vừa nêu trên đây, chúng ta có thể hình dung được phần nào bản sắc và tiềm năng của tiếng Việt 2.3. Tìm kiếm ngữ nghĩa trong lĩnh vực y tế Trong phần này, khóa luận sẽ trình bày những bước đầu của việc xây dựng một máy tìm kiếm ngữ nghĩa trên lĩnh vực Y tế cho tiếng Việt. 2.3.1. Ontology Y tế trong tiếng Việt Với các dữ liệu về y tế thu thập được từ các trang Web và Ontology BioCaster [1], tiến hành liệt kê các thuật ngữ (term) quan trọng nhằm có thể nêu định nghĩa cho người dùng với hướng nghiên cứu tiếp theo là tự động liên kết đến các định nghĩa có sẵn trên 17 trang wikipedia. Từ các thuật ngữ trên, sẽ định nghĩa các thuộc tính của chúng. Việc xây dựng Ontology là một quá trình lặp lại được bắt đầu bằng việc định nghĩa các khái niệm trong hệ thống lớp và mô tả thuộc tính của các khái niệm đó. Qua khảo sát Ontology BioCaster với các thuật ngữ trong tiếng Việt, cùng với một số luợng lớn các trang Web về y tế hiện nay ở Việt Nam, chúng tôi đã xây dựng nên một tập các thuật ngữ, các mối quan hệ cơ bản nhất để từ đó để xuất ra Ontology thử nghiệm ban đầu, với những khái niệm cơ bản sau: - Thuốc: bao gồm hai loại Đông y và Tây y. Ví dụ, thuốc 5-Fluorouracil Ebewe chống ung thư (ung thư đại trực tràng, vú, thực quản, dạ dày), hay là thuốc Ciloxan sát trùng, chống nhiễm khuẩn ở mắt. Thuốc đông y ngũ gia bì chữa bệnh phong thấp, tráng gân cốt … - Bệnh, hội chứng: Các loại bệnh như cúm gà, viêm loét dạ dày, các hội chứng mất ngủ, suy tim … - Triệu chứng : Ví dụ như triệu chứng của cúm H5N1 là sốt cao, nhức đầu, đau mỏi toàn thân,... - Nguyên nhân: Tác nhân (virut, vi khuẩn..muỗi, gà, chim..), và các nguyên khác như là thiếu ngủ, lười tập thể dục, hút thuốc lá thụ động … - Thực phẩm: Bao gồm các món ăn có lợi hoặc gây hại cho sức khỏe con nguời cũng như phù hợp với một số loại bệnh nào đó. - Người: Bao gồm bác sỹ, giáo sư mà người bệnh có thể tìm kiếm để khám bênh, xin giúp đỡ khi mắc bệnh. - Tổ chức: Bệnh viện, phòng khám, hiệu thuốc … là các địa điểm để bệnh nhân có thể tìm đến khi mắc bệnh. - Địa điểm: Địa chỉ của một tổ chức nào đó mà bệnh nhân có thể tìm đến, các nơi dịch đang phát sinh và lan rộng. - Cơ thể người: Là tất cả các bộ phận cơ thể người có thể thể bị nhiễm bệnh: mắt, mũi, gan, tim … - Hoạt động: Chẩn trị, xét nghiệm, hồi cứu, hô hấp nhân tạo, phòng tránh, tiêm phòng ... - Hóa chất: Vitamin, khoáng chất …gây tác động xấu, tốt đến cơ thể con người, ví dụ vitamin A có lợi cho mắt, Vitamin C, E làm giảm các nguy cơ bệnh tim… Giữa các khái niệm cơ bản trên có các mỗi quan hệ như sau: - Sự tương tác thuốc – thuốc : Thuốc này có thể gây tác dụng phụ cho thuốc kia, hay có thể kết hợp các loại thuốc với nhau để chữa bệnh. Ví dụ thuốc chống ung 18 thư Alexan không nên dùng chung với methotrexate hay 5-fluorouracil - Thực phẩm tác động xấu, tốt đến bệnh, cơ thể người: Ví dụ như uống xôđa nhiêu có rủi ro mắc các bệnh rối loạn trao đổi chất, tăng vòng bụng, tăng huyết áp… - Quan hệ bệnh – thuốc: () - Quan hệ nguyên nhân gây ra bệnh, hay bệnh có nguyên nhân: () - Quan hệ bệnh – triệu chứng: () - Quan hệ bệnh biến chứng thành bệnh khác: - Các hoạt động tác động lên bệnh: - Bệnh được phát hiện, chữa trị ở tổ chức: - Người làm việc trong một tổ chức tại địa điểm nào đó: Ví dụ minh họa thể hiện Mô hình của Ontology Y tế này ở hình 2. 2.3.2. Bộ phân lớp câu hỏi Y tế trong tiếng Việt Với Ontology Y tế giới thiệu ở phần trên, để giải quyết được hai bài toán mang đặc trưng của tiếng Việt cần xây dựng một bộ phân lớp câu hỏi Y tế trong tiếng Việt. Bộ phân lớp câu hỏi này là bộ phân lớp nội miền (trong miền Ontology Y tế), tức là với các câu hỏi/truy vấn của người dùng đưa vào, bộ phân lớp phải xác định chúng thuộc về các khái niệm nào. Chương 3 sẽ cụ thể hóa các phương pháp phân lớp câu hỏi. 19 Chương 3. Các phương pháp phân lớp câu hỏi 3.1. Giới thiệu về phân lớp câu hỏi. Trong hầu hết các hệ thống tìm kiếm ngữ nghĩa, bước đầu tiên là xử lý câu hỏi nhằm xác định câu hỏi đó hỏi về cái gì? Phân chia truy vấn của người dùng ra thành một số lớp định nghĩa trước như hỏi địa điểm (ở đâu ?), thời gian (khi nào ?)… Thông thường ở phần lớn các trường hợp để xác định được điều này, hệ thống thường sử dụng một số thông tin hay đặc trưng của câu hỏi để xác định kiểu của câu trả lời. Ví dụ với câu hỏi “ai là người phát hiện ra vacxin phòng bệnh dại?” thì mục đích của câu hỏi là muốn tìm hiểu thông tin về một người. Hệ thống cần xác định được kiểu của câu trả lời (trong ví dụ này là thông tin về một người) để có thể trả về thong tin mong muốn cho người dùng. Trong các hệ thống tìm kiếm ngữ nghĩa, đối tượng được tìm kiếm là các thông tin mang ngữ nghĩa, do vậy việc phân lớp câu hỏi còn được gọi là phân lớp ngữ nghĩa cho câu hỏi (semantic question classification) có hai vai trò quan trọng sau đây: (1) Giảm không gian tìm kiếm, chẳng hạn với câu hỏi “thuốc nào chữa bệnh viêm họng?” hệ thống chỉ cần tìm kiếm trên các lớp thuốc của miền Y tế để có câu trả lời, thay vì tìm kiếm trên toàn bộ cơ sở dữ liệu. (2) Nâng cao độ chính xác của câu trả lời. Đối với các hệ thống tìm kiếm ngữ nghĩa lớn tìm kiếm trên nhiều miền Ontology, thường có bộ phân lớp câu hỏi kép gồm : (1) phân lớp để xác định miền Ontology của câu hỏi (phân lớp nội miền) (2) phân lớp để xác định câu hỏi thuộc lĩnh vực nào (lớp nào) trong miền Ontology đã xác định ở phân lớp nội miền. Ngược lại đối với các máy tìm kiếm ngữ nghĩa trên một miền Ontology, chỉ cần xây dựng bộ phân lớp đơn (2). 3.2. Các phương pháp phân lớp câu hỏi Hiện nay, có một số nghiên cứu tập trung vào hướng tiếp cận biểu thức chính qui dựa vào những luật ngữ pháp viết tay (hand-written grammar rulers) để xác định lớp của câu hỏi đầu vào như các tác giả B., Huang, Y., Kupsc, A. và Nyberg, E năm 2003 [35] giới thiệu. Mặc dù hướng tiếp cận này cũng đạt được những thành công đáng kể, nhưng vẫn có những hạn chế mà đã được Li, Roth 2002[19] và Hacioglu, Ward 2003[16] chỉ ra. 20 Cụ thể, các tác giả [14] đã chỉ ra bốn hạn chế của hướng tiếp cận này: (1) Xây dựng mô hình cho phương pháp này rất tốn thời gian và công sức, cần có sự cộng tác của những chuyên gia trong lĩnh vực ngôn ngữ học khi xây dựng các mẫu câu hỏi và văn phạm cho từng loại câu hỏi đó. (2) Các luật ngữ pháp viết tay và văn phạm của từng loại câu hỏi rất cứng nhắc, không linh động. Khi một dạng câu hỏi mới xuất hiện, mô hình theo hướng này không thể xử lý. Muốn xử lý được mô hình cần phải được cung cấp những luật mới. (3) Vấn đề nhập nhằng của các văn phạm ngữ pháp rất khó xử lý, kiểm soát và phụ thuộc vào đặc điểm của từng ngôn ngữ. (4) Khi tập câu trả lời được mở rộng hoặc thay đổi kéo theo việc phải viết lại hoàn toàn các luật trước đó nên hệ thống rất khó mở rộng. Với các hạn chế như trên dẫn đến số lớp của bộ phân lớp theo hướng này là nhỏ (khoảng 8-10 lớp) không thích hợp khi tích hợp vào một hệ thống tìm kiếm ngữ nghĩa có qui mô lớn. Một hướng tiếp cận khác để giải quyết bài toán phân lớp câu hỏi là theo hướng tiếp cận xác suất được Jonathan Brown năm 2004 tổng hợp lại [15], bao gồm hai cách tiếp cận chính đó là: (1) Tiếp cận theo hướng học máy (machine learning) (2) Tiếp cận theo mô hình ngôn ngữ (language modeling) Không giống như hướng tiếp cận biểu thức chính quy (thực hiện việc so sánh mẫu), các phương pháp theo hướng tiếp cận dựa trên xác suất sẽ xây dựng một mô hình phân lớp tự động từ tập dữ liệu học cho trước. Các thuật toán của hướng tiếp cận này sẽ tính toán xác suất phân lớp cho câu hỏi vào dựa trên những đặc trưng hay những mối quan hệ của các từ trong câu hỏi/truy vấn đưa vào. Nhờ đó phương pháp này khắc phục những nhược điểm của hướng tiếp cận biểu thức chính quy [15]. Do vậy, hướng tiếp cận này không những phù hợp với các hệ thống tìm kiếm ngữ nghĩa lớn mà còn phù hợp với các hệ thống nhỏ hơn (do khả năng linh hoạt cao dễ dàng mở rộng tập dữ liệu và số phân lớp). Khóa luận sẽ tập trung trình bày các phương pháp phân lớp câu hỏi dựa trên hướng tiếp cận xác suất để xây dựng bộ phân lớp câu hỏi trong Tiếng Việt. 3.3. Hướng tiếp cận dựa trên xác suất Bên cạnh hướng tiếp cận dựa trên biểu thức chính quy thì hướng tiếp cận dựa trên xác suất cũng là một hướng tiếp cận được nhiều nhà khoa học lựa chọn khi nghiên cứu về phân lớp câu hỏi. Như đã được giới thiệu, hướng tiếp cận dựa trên xác suất bao gồm hai hướng con là hướng học máy và hướng dựa trên mô hình ngôn ngữ [15]. Hướng tiếp cận học máy sử dụng những thuật toán và kỹ thuật cho phép máy tính có thể “học” 1 được. Cụ thể, trong bài toán phân lớp câu hỏi hướng tiếp cận học máy sử dụng các thuật toán như : Support Vector Machines (SVM), láng giềng gần nhất (Nearest 21 Neighbors – kNN), Naïve Bayes (NB)…v.v để học trên tập câu hỏi mẫu đã được gán nhãn từ đó xây dựng mô hình phân lớp câu hỏi. Trong khi đó, tiếp cận dựa trên mô hình ngôn ngữ xây dựng một mô hình ngôn ngữ thống kê có thể ước lượng được phân phối của ngôn ngữ tự nhiên chính xác nhất có thể. Ví dụ, với một xâu S = “Bệnh đau dạ dày chữa ở đâu?” thì mô hình ngôn ngữ cho xâu S chính là xác suất P(S), sao cho xác suất này ánh xạ với tần suất mà xâu S trở được xuất hiện như một câu nói trong ngôn ngữ tự nhiên (ví dụ tiếng Việt). Khi áp dụng phương pháp này cho bài toán phân lớp câu hỏi, tức là xây dựng một mô hình ngôn ngữ cho từng câu hỏi. Mô hình này sẽ cho biết xác suất câu hỏi được phân vào lớp nào là hợp lý nhất (lớn nhất). Cả hai phương pháp trên đều có độ chính xác khác nhau phụ thuộc vào ngôn ngữ áp dụng. Để lựa chọn hướng tiếp cận tốt nhất khi xây dựng bộ phân lớp câu hỏi cho tiếng Việt, phần tiếp theo của khóa luận sẽ trình bày những khảo sát về cả hai hướng tiếp cận trên 3.3.2 Các hướng tiếp cận theo phương pháp học máy Trong hướng tiếp học máy thuật toán được sử dụng chủ yếu để giải quyết bài toán phân lớp câu hỏi là Support Vector Machines (được sử dụng trong các tài liệu [19, 20, 22], ngoài ra các thuật toán khác cũng được sử dụng như Nearest Neighbors (NN), Naïve Bayes (NB), Decision Tree (DT) và Sparse Network of Winnows (SNoW) [42]. Đưới đây trình bày sơ lược về nội dung một số thuật toán học máy. 3.3.1.1 Support Vector Machines (SVM) a. Thuật toán [2] Thuật toán Support Vector Machines (máy vector hỗ trợ) được Corters và Vapnik giới thiệu vào năm 1995. SVM rất hiệu quả để giải quyết các bài toán với dữ liệu có số chiều lớn như các vector biểu diễn văn bản. Thuật toán SVM ban đầu chỉ được thiết kế để giải quyết bài toán phân lớp nhị phân tức là số lớp hạn chế là hai lớp. Hiện nay, SVM được đánh giá là bộ phân lớp chính xác nhất cho bài toán phân lớp văn bản [31] bởi vì đó là bộ phân lớp tốc độ rất nhanh và hiệu quả đối với bài toán phân lớp văn bản. Cho tập dữ liệu học D ={(xi, yi), i = 1,…, n} với xi ∈ Rm và yi∈{0,1} là một số là một số nguyên xác định xi là dữ liệu dương hay âm. Một tài liệu xi được gọi là dữ liệu dương nếu nó thuộc lớp ci ; xi được gọi là dữ liệu âm nếu nó không thuộc lớp ci . Bộ phân lớp tuyến tính được xác định bằng siêu phẳng: {x : f(x) = WT + w0 =0} Trong đó W∈ Rm và w0∈R đóng vai trò là tham số của mô hình. Hàm phân lớp nhị phân h: Rm → {0,1}, có thể thu được bằng cách xác định dấu của f(x): { 0 (x) 1 0 (x) 0 >≤= f f h 22 Học bộ phân lớp của mô hình bao gồm việc xác định w và w0 từ dữ liệu. Với thuật toán này, mỗi dữ liệu được xem là một điểm trong mặt phẳng. Dữ liệu học là tách rời tuyến tính (linearly separable) nếu tồn tại một siêu phẳng sao cho hàm phân lớp phù hợp với tất cả các nhãn; tức là yif(xi)>0 với mọi i = 1,...,n. Với giả thuyết này, Rosenblatt đã đưa ra một thuật toán đơn giản để xác định siêu phẳng : 1. w ←0 2. w0←0 3. repeat 4. e←0 5. for i←1,…,n 6. do s←sign(yi(wTxi +w0) 7. if s<0 8. then w ←w + yixi 9. w0←w0 + yixi 10. e←e+1 11. util e=0 12. return (w,w0) Điều kiện cần để D tách rời tuyến tính là số dữ liệu học n = |D| nhỏ hơn hoặc bằng m+1. Điều này là thường đúng với bài toán phân lớp văn bản, bởi vì số lượng từ mục có thể lên tới hàng nghìn và lớn hơn nhiều lần so với số lượng dữ liệu học. 23 Hình 4. Mối quan hệ giữa các siêu phẳng phân cách Trong Hình 4, giả sử rằng các dữ liệu mẫu thuộc lớp âm và lớp dương đều tuân theo luật phân bố chuẩn Gaussian, và được tạo ra với cùng một xác suất. Khi đó một siêu phẳng phân cách được gọi là lý tưởng nếu nó làm cực tiểu xác suất phân lớp sai cho một điểm dữ liệu mới. Với giả thuyết ở trên thì siêu phẳng phân cách lý tưởng sẽ trực giao với đoạn thẳng nối tâm của hai vùng có mật độ xác suất lớn nhất. Rõ ràng các siêu phẳng được xây dựng nhằm phân cách các điểm dữ liệu mẫu có thể lệch đi rất nhiều so với siêu phẳng lý tưởng, do đó sẽ dẫn tới việc phân lớp không tốt trên dữ liệu mới sau này. Độ phức tạp của quá trình xác định siêu phẳng lý tưởng sẽ tăng theo số chiều của không gian đầu vào m, vì với một số lượng các dữ liệu mẫu cố định, tập hợp các siêu phẳng thực tế sẽ tăng theo hàm mũ với lũy thừa m. Với bài toán phân lớp trang văn bản, m thường rất lớn, khoảng vài ngàn hay thậm chí là hàng triệu từ. 24 Hình 5. Siêu phẳng tối ưu và biên. Theo lý thuyết thống kê được phát triển bởi Vapnik năm 1998 chỉ ra rằng có thể xác định một siêu phẳng tối ưu thoả mãn hai tính chất quan trong (1) nó là duy nhất với mỗi tập dữ liệu học tách rời tuyến tính; (2) khả năng overfitting là nhỏ hơn so với các siêu phẳng khác [26]. Định nghĩa biên M của bộ phân lớp là khoảng cách giữa các siêu phẳng và các dữ liệu học gần nhất. Siêu phẳng tối ưu nhất là siêu phẳng có biên lớn nhất, điều đó có nghĩa là chúng ta cần tìm siêu phẳng sao cho khoảng cách từ siêu phẳng đến những điểm gần nhất là lớn nhất (Hình 5). Vapnik cũng chứng minh rằng khả năng overfitting với siêu phẳng tối ưu nhỏ hơn so với các siêu phẳng khác. Khoảng cách từ một điểm x đến siêu phẳng là : Vì vậy siêu phẳng tối ưu có thể thu được bằng ràng buộc tối ưu sau: 0w,w max M sao cho Ti i 0 1 y (w x w ) M,i 1,...n || w || + ≥ = 0 T ww ||w|| 1 + 25 Trong đó ràng buộc yêu cầu mỗi tài liệu học (tương đương với các điểm) phải nằm trên nửa mặt phẳng của nó và khoảng cách từ điểm tới siêu phẳng lớn hơn hoặc bằng M. Đặt 1w M= biểu thức trên được viết lại như sau 0w,w min W sao cho Ti i 0y (w x w ) M,i 1,...,n+ ≥ = Đưa về phương trình Lagrangian: ( )n2 Ti i 0 i 1 1L(D) || w || y w w 1 2 = ⎡ ⎤= − + α + −⎣ ⎦∑ Sau đó tính đạo hàm của phương trình trên theo w,w0 ta được n T i i 1 1max 2α = − α Λα + α∑ thoả mãn i 0,i 1,...,nα ≥ = Với Λ là ma trận n×n trong đó iα = yiyj jTi xx . Đây là bài toán bậc hai, theo lý thuyết có thể giải được bằng phương pháp chuẩn tối ưu. Với mỗi dữ liệu học i, cách giải phải thoả mãn điều kiện: iα ( )[ ]1wwy 0Ti −+ =0 Và do đó hoặc iα = 0 hoặc )wxw(y 0iTi + =1. Nói cách khác, nếu iα >0 thì khoảng cách từ điểm xi đến mặt phẳng phân cách là M . Các điểm thoả mãn iα >0 được gọi là các vector hỗ trợ. Hàm quyết định h(x) có thể được tính qua công thức dấu của f(x) hoặc tương đương với dạng sau: i T i n 1i i xxxy(x) ∑ = =f Nếu dữ liệu học không tách rời tuyến tính, thêm biến ξi và thay phương trình trên bằng phương trình: ∑ = + n 1i C||w||min iww, ξ0 thỏa mãn ( )+ ≥ − = ≥ = ⎧⎪⎨⎪⎩ T i i 0 i i y w x w 1 ξ ,i 1,...,n ξ 0, i 1,...,n Vấn đề này có thể đưa về dạng: 1 1max 2 n T i iα α α α = − Λ +∑ thỏa mãn Cα0 i ≤≤ i=1,…,n Bộ phân lớp theo cách này được gọi là bộ phân lớp máy vector hỗ trợ – Support Vector Machine. 26 b. Phân lớp đa lớp với SVM Bài toán phân lớp câu hỏi yêu cầu một bộ phân lớp đa lớp do đó cần cải tiến SVM cơ bản