Online Closure-Based Learning of Relational Theories Export

@incollection{citeulike:1306316, abstract = {Online learning algorithms such as Winnow have received much attention in Machine Learning. Their performance degrades only logarithmically with the input dimension, making them useful in large spaces such as relational theories. However, online first-order learners are intrinsically limited by a computational barrier: even in the finite, function-free case, the number of possible features grows exponentially with the number of first-order atoms generated from the vocabulary. To circumvent this issue, we exploit the paradigm of closure-based learning which allows the learner to focus on the features that lie in the closure space generated from the examples which have lead to a mistake. Based on this idea, we develop an online algorithm for learning theories formed by disjunctions of existentially quantified conjunctions of atoms. In this setting, we show that the number of mistakes depends only logarithmically on the number of features. Furthermore, the computational cost is essentially bounded by the size of the closure lattice.}, author = {Koriche, Fr\'{e}d\'{e}ric}, citeulike-article-id = {1306316}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/11536314_11}, doi = {10.1007/11536314_11}, journal = {Inductive Logic Programming}, keywords = {closure-lattice, closure-structures, lattice-of-features, lattice-of-properties}, pages = {172--189}, posted-at = {2007-05-18 20:48:53}, priority = {2}, title = {Online Closure-Based Learning of Relational Theories}, url = {http://dx.doi.org/10.1007/11536314_11}, year = {2005} }

TY - CHAP ID - citeulike:1306316 L3 - citeulike-article-id:1306316 N2 - Online learning algorithms such as Winnow have received much attention in Machine Learning. Their performance degrades only logarithmically with the input dimension, making them useful in large spaces such as relational theories. However, online first-order learners are intrinsically limited by a computational barrier: even in the finite, function-free case, the number of possible features grows exponentially with the number of first-order atoms generated from the vocabulary. To circumvent this issue, we exploit the paradigm of closure-based learning which allows the learner to focus on the features that lie in the closure space generated from the examples which have lead to a mistake. Based on this idea, we develop an online algorithm for learning theories formed by disjunctions of existentially quantified conjunctions of atoms. In this setting, we show that the number of mistakes depends only logarithmically on the number of features. Furthermore, the computational cost is essentially bounded by the size of the closure lattice. JF - Inductive Logic Programming EP - 189 TI - Online Closure-Based Learning of Relational Theories SP - 172 KW - closure-lattice KW - closure-structures KW - lattice-of-features KW - lattice-of-properties AU - Koriche, Frédéric PY - 2005/// UR - http://dx.doi.org/10.1007/11536314_11 ER -