Learning first-order definable concepts over structures of small degree
作者： Martin Grohe , Martin Ritzert
DOI:
关键词:
摘要: We consider a declarative framework for machine learning where concepts and hypotheses are defined by formulas of logic over some background structure. show that within this framework, first-order structure at most polylogarithmic degree can be learned in time the "probably approximately correct" sense.
arxiv.org参考文章(24)
Detlef Seese, Linear time computable problems and first-order descriptions Mathematical Structures in Computer Science. ,vol. 6, pp. 505- 526 ,(1996) , 10.1017/S0960129500070079
Shai Shalev-Shwartz, Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms ,(2015)
S. Feferman, R. Vaught, The first order properties of products of algebraic systems Fundamenta Mathematicae. ,vol. 47, pp. 57- 103 ,(1959) , 10.4064/FM-47-1-57-103
Umesh V. Vazirani, Michael J. Kearns, An Introduction to Computational Learning Theory ,(1994)
Robert H. Sloan, Learning Logic Programs with Unary Partial Function Graph Background Knowledge (extended abstract) ,(2003)
Tamás Horváth, György Turán, Learning logic programs with structured background knowledge Artificial Intelligence. ,vol. 128, pp. 31- 97 ,(2001) , 10.1016/S0004-3702(01)00062-5
Angela Bonifati, Radu Ciucanu, Sławek Staworko, Learning Join Queries from User Examples ACM Transactions on Database Systems. ,vol. 40, pp. 24- ,(2016) , 10.1145/2818637
Goldreich, Ron, Property Testing in Bounded Degree Graphs Algorithmica. ,vol. 32, pp. 302- 343 ,(2002) , 10.1007/S00453-001-0078-7
William W. Cohen, C. David Page, Polynomial learnability and Inductive Logic Programming: Methods and results New Generation Computing. ,vol. 13, pp. 369- 409 ,(1995) , 10.1007/BF03037231
Ashok Chandra, David Harel, Structure and complexity of relational queries Journal of Computer and System Sciences. ,vol. 25, pp. 99- 128 ,(1982) , 10.1016/0022-0000(82)90012-5