SAT-Based PAC Learning of Description Logic Concepts

被引:0
作者
ten Cate, Balder [1 ]
Funk, Maurice [2 ,3 ]
Jung, Jean Christoph [4 ]
Lutz, Carsten [2 ,3 ]
机构
[1] Univ Amsterdam, ILLC, Amsterdam, Netherlands
[2] Univ Leipzig, Leipzig, Germany
[3] Ctr Scalable Data Analyt & Artificial Intelligenc, Leipzig, Germany
[4] TU Dortmund Univ, Dortmund, Germany
来源
PROCEEDINGS OF THE THIRTY-SECOND INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, IJCAI 2023 | 2023年
关键词
FRAMEWORK;
D O I
暂无
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
We propose bounded fitting as a scheme for learning description logic concepts in the presence of ontologies. A main advantage is that the resulting learning algorithms come with theoretical guarantees regarding their generalization to unseen examples in the sense of PAC learning. We prove that, in contrast, several other natural learning algorithms fail to provide such guarantees. As a further contribution, we present the system SPELL which efficiently implements bounded fitting for the description logic ELHr based on a SAT solver, and compare its performance to a state-of- the-art learner.
引用
收藏
页码:3347 / 3355
页数:9
相关论文
共 37 条
[1]  
Angluin D., 1988, Machine Learning, V2, P319, DOI 10.1007/BF00116828
[2]  
[Anonymous], 1989, J ASS COMPUTING MACH
[3]  
Baader Franz., 2017, INTRO DESCRIPTION LO
[4]  
Baader Franz, 2008, P OWLED
[5]  
Biere A, 1999, LECT NOTES COMPUT SC, V1579, P193
[6]   ON THE NECESSITY OF OCCAM ALGORITHMS [J].
BOARD, R ;
PITT, L .
THEORETICAL COMPUTER SCIENCE, 1992, 100 (01) :157-184
[7]   DL-Learner-A framework for inductive learning on the Semantic Web [J].
Buehmann, Lorenz ;
Lehmann, Jens ;
Westphal, Patrick .
JOURNAL OF WEB SEMANTICS, 2016, 39 :15-24
[8]   THE LEARNABILITY OF DESCRIPTION LOGICS WITH EQUALITY CONSTRAINTS [J].
COHEN, WW ;
HIRSH, H .
MACHINE LEARNING, 1994, 17 (2-3) :169-199
[9]  
Fanizzi Nicola, 2018, Knowledge Engineering and Knowledge Management. 21st International Conference, EKAW 2018. Proceedings: Lecture Notes in Artificial Intelligence (LNAI 11313), P98, DOI 10.1007/978-3-030-03667-6_7
[10]  
Frazier M, 1996, MACH LEARN, V25, P151, DOI 10.1007/BF00114009