Cải tiến FOCL trong việc học các khái niệm đệ quy

Trong bài báo này chúng tôi đề xuất cải tiến cho FOCL bằng cách tạo thêm các ràng buộc đệ quy cho FOCL trong khi học nhằm tránh rủi ro này. Các ràng buộc được đưa ra để ngăn chặn FOCL lựa chọn và kết nạp các trực kiện gây rủi ro vào tập mệnh đề định nghĩa khái niệm đệ quy cần học. Kết quả thử nghiệm cho thấy việc cải tiến thực sự có tác dụng.
Nội dung trích xuất từ tài liệu:
Cải tiến FOCL trong việc học các khái niệm đệ quyPhạm Thị Thương và ĐtgTạp chí KHOA HỌC & CÔNG NGHỆ86(10): 49 - 54CẢI TIẾN FOCL TRONG VIỆC HỌC CÁC KHÁI NIỆM ĐỆ QUYPhạm Thị Thương*, Ngô Thị Lan, Nguyễn Lan Oanh1Trường ĐH CNTT&TT – ĐH Thái NguyênTÓM TẮTFOCL là một thuật toán học khái niệm logic vị từ cấp một đã được đề xuất bởi Pazzani, BrunkSilverstein, 1991; Pazzani và Kibler, (1992) [3]. Tuy nhiên vấn đề học khái niệm đệ quy phức tạp– chứa nhiều lời gọi đệ quy có thể dẫn đến rủi ro, thuật toán không dừng do gặp phải đệ quy khôngxác định. Trong bài báo này chúng tôi đề xuất cải tiến cho FOCL bằng cách tạo thêm các ràngbuộc đệ quy cho FOCL trong khi học nhằm tránh rủi ro này. Các ràng buộc được đưa ra để ngănchặn FOCL lựa chọn và kết nạp các trực kiện gây rủi ro vào tập mệnh đề định nghĩa khái niệm đệquy cần học. Kết quả thử nghiệm cho thấy việc cải tiến thực sự có tác dụng.Từ khóa: FOCL (First Order Combined Learner) – Hệ học Kết hợp logic vi từ Cấp 1, đệ quy vôhạn, khái niệm đệ quy, trực kiện, trực kiện âm, vị từ, vi từ mục tiêu, vị từ mở rộng, mệnh đề, mệnhđề Horn, mệnh đề bội, nhóm, tri thức miền, tập dữ liệu huấn luyện.ĐẶT VẤN ĐỀHọc để tổng quát hóa các khái niệm là mộttrong những chủ đề chính của lĩnh vực Máyhọc, thuộc ngành Trí tuệ nhân tạo. Tổng quáthóa khái niệm nghĩa là từ các tình huống haycác quy tắc, sự việc cụ thể ta diễn dịch đượcmột công thức đủ khái quát để mô tả các tìnhhuống, quy tắc và các sự việc này [8]. Có rấtnhiều các thuật toán học đã được nghiên cứucho chủ đề này như FIND_S, LTE, CEL,GOLEM, FOIL, FOCL,.... [6 ]. Tuy nhiên cácthuật toán này chưa quan tâm nhiều đến việchọc các khái niệm đệ quy phức tạp. Việc họccác khái niệm này phải đương đầu với nhiềukhó khăn, trong tập dữ liệu huấn luyện và tậptri thức miền có thể chứa các định nghĩa đệquy không xác định, dẫn đến thuật toán họcdễ rơi vào tình trạng không dừng.Trong bài báo này chúng tôi chọn FOCL đểcải tiến vì FOCL được sử dụng để học cáckhái niệm được biểu diễn bằng logic vị từcấp một. Logic vị từ cấp một là một dạngbiểu diễn khá thuận lợi cho các khái niệmđệ quy. Mục tiêu của việc cải tiến nhằmtránh rủi ro thuật học không dừng do gặpphải đệ quy vô hạn. Các nghiên cứu về việchọc các khái niệm đệ quy trên thế giới đãTel: 0912 838646, Email: tn.univer@gmail.comSố hóa bởi Trung tâm Học liệu – Đại học Thái Nguyênđược trình bày trong một số tài liệu [1, 2, 3,4, 7]. Tuy nhiên việc khắc phục rủi ro nàymới chỉ đề cập ở [3], được áp dụng choFOIL. Các kết quả nghiên cứu trong nướcvề vấn đề này còn rất hạn chế.Bài báo có cấu trúc như sau: Sau phần đặt vấnđề, phần kế tiếp sẽ trình bày phương phápphát hiện thứ tự của tập các hằng và các trựckiện trong tập mệnh đề định nghĩa khái niệmđệ quy [3]. Tiếp theo là thuật toán FOCL,thuật toán FOCL cải tiến và phần thử nghiệmđược thực hiện qua một bộ dữ liệu thử cụ thểmà chúng tôi lập trình để học hàmAckermann. Cuối cùng là thảo luận và tài liệutham khảo.KHÁM PHÁ THỨ TỰ ĐỆ QUY TRONGTẬP MỆNH ĐỀThứ tự của một tập hằngXét quan hệ R(V1, V2, ….., Vk) được địnhnghĩa mở rộng bởi tập dữ liệu huấn luyện D.D chứa một tập POS gồm một tập các k –tuple, mỗi k tupe (tạm dịch là nhóm k hằng)mô tả R đúng gọi là các nhóm hằng dươngtính, ký hiệu  và tập NEG gồm các nhóm khằng mô tả R sai, gọi là các nhóm hằng âmtính, ký hiệu . Mỗi nhóm k hằng có dạng(ax1, ax2, …., axk), với axi là hằng thứ i trongnhóm hằng thứ x; i = 1.. k. Các hằng axi có thể49http://www.lrc-tnu.edu.vnPhạm Thị Thương và ĐtgTạp chí KHOA HỌC & CÔNG NGHỆthuộc các kiểu dữ liệu khác nhau, có một thứtự nào đó. Giải thuật tìm một thứ tự hợp lýcủa các hằng thuộc cùng một kiểu được mô tảnhư sau [4]:Bước 1: Mọi cặp đối số (Vi, Vj ); i  j của Rđều được kiểm tra nhằm khẳng định xem Vi Vj vì cả hai đều hợplý, không thể phân biệt giữa chúng. Kết quảthu được của bước này là tập các bất đẳngthức giữa các cặp đối số của R.Bước 2: Tìm tập con của tập các bất đẳngthức thu được ở bước 1 mà phù hợp nhất vớitập huấn luyện D.Bước 3: Tìm một thứ tự tổng hợp trên cáchằng bằng cách tạo ra cây phân cấp có gốc làmột hằng nào đó dựa vào sự đóng kín của tậpcác bất đẳng thức giữa các cặp hằng và tậpcác bất đẳng thức tìm được ở bước 2.Ví dụ xét hai quan hệ biểu diễn bởi 2 vị từSubtree và leaf_of như sau:Subtree (A, B, C) : Có nghĩa là cây A có haicây con là B và CLeaf_of(A, B): A là lá của cây BVới tập huấn luyện D có tập POS:Subtree:Leaf_of:(0,1,2)(a,0)(b,1)(1,a,b)(a,1)(c,0)(d,2)(2,c,3)(a,2)(c,2)(d,3)(3,d,a)(a,3)(d,0)(b,0)Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên86(10): 49 - 54Các nhóm hằng không thuộc tập ví dụnày được xem là sai với giả định thế giớiđóng – tập NEG.Xét vị từ Subtree(A,B,C), xét cặp đối số (A, B).Thứ tự các cặp hằng tương ứng với các nhómhằng là 0 ...