We study several complexity parameters for first order formulas and their suitability for first order learning models. We show that the standard notion of size is not captured by sets of parameters that are used in th...
详细信息
ISBN:
(纸本)9783540399179
We study several complexity parameters for first order formulas and their suitability for first order learning models. We show that the standard notion of size is not captured by sets of parameters that are used in the literature and thus they cannot give a complete characterization in terms of learnability with polynomial resources. We then identify an alternative notion of size and a simple set of parameters that are useful for first order Horn Expressions. These parameters are the number of clauses in the expression, the maximum number of distinct terms in a clause, and the maximum number of literals in a clause. Matching lower bounds derived using the Vapnik Chervonenkis dimension complete the picture showing that these parameters are indeed crucial.
inductive logic programming (ILP) is a well-known machine learning technique for learning concepts from relational data. Nevertheless, ILP systems are not robust enough to noisy or unseen data in real world domains. F...
详细信息
inductive logic programming (ILP) is a well-known machine learning technique for learning concepts from relational data. Nevertheless, ILP systems are not robust enough to noisy or unseen data in real world domains. Furthermore, in multi-class problems, if the example is not matched with any learned rules, it cannot be classified. This paper presents a novel hybrid learning method to alleviate this restriction by enabling Neural Networks to handle first-order logic programs directly. The proposed method, called First-Order logical Neural Network (FOLNN), employs the standard feedforward neural network and integrates inductive learning from examples and background knowledge. We also propose a method for determining the appropriate variable substitution in FOLNN learning by using Multiple-Instance Learning (MIL). In the experiments, the proposed method has been evaluated on two first-order learning problems, i.e., the Finite Element Mesh Design and Mutagenesis and compared with the state-of-the-art, the PROGOL system. The experimental results show that the proposed method performs better than PROGOL.
Background: We investigate whether annotation of gene function can be improved using a classification scheme that is aware that functional classes are organized in a hierarchy. The classifiers look at phylogenic descr...
详细信息
Background: We investigate whether annotation of gene function can be improved using a classification scheme that is aware that functional classes are organized in a hierarchy. The classifiers look at phylogenic descriptors, sequence based attributes, and predicted secondary structure. We discuss three Bayesian models and compare their performance in terms of predictive accuracy. These models are the ordinary multinomial logit (MNL) model, a hierarchical model based on a set of nested MNL models, and an MNL model with a prior that introduces correlations between the parameters for classes that are nearby in the hierarchy. We also provide a new scheme for combining different sources of information. We use these models to predict the functional class of Open Reading Frames (ORFs) from the E. coli genome. Results: The results from all three models show substantial improvement over previous methods, which were based on the C5 decision tree algorithm. The MNL model using a prior based on the hierarchy outperforms both the non-hierarchical MNL model and the nested MNL model. In contrast to previous attempts at combining the three sources of information in this dataset, our new approach to combining data sources produces a higher accuracy rate than applying our models to each data source alone. Conclusion: Together, these results show that gene function can be predicted with higher accuracy than previously achieved, using Bayesian models that incorporate suitable prior information.
This paper presents a methodology to design a discrete-event system (DES) for the on-line supervision of a biotechnological process. The DES is synthesized applying wavelet transform and inductive logic programming on...
详细信息
This paper presents a methodology to design a discrete-event system (DES) for the on-line supervision of a biotechnological process. The DES is synthesized applying wavelet transform and inductive logic programming on the measured signals constrained to the biotechnologist expert validation. (C) 2002 Elsevier Science B.V. All rights reserved.
An important ingredient in agent-mediated electronic commerce is the presence of intelligent mediating agents that assist electronic commerce participants (e.g. individual users, other agents, organisations). These me...
详细信息
An important ingredient in agent-mediated electronic commerce is the presence of intelligent mediating agents that assist electronic commerce participants (e.g. individual users, other agents, organisations). These mediating agents are in principle autonomous agents that interact with their environments (e.g. other agents and web-servers) oil behalf of participants who have delegated tasks to them. For mediating agents a (preference) model of participants is indispensable. In this paper, a generic mediating agent architecture is introduced. Furthermore, we discuss our view of user preference modelling and its need in agent-mediated electronic commerce. We survey the state of the art in the field of preference modelling and suggest that the preferences of electronic commerce participants can be modelled by learning from their behaviour. In particular, we employ an existing machine learning method called inductive logic programming (ILP). We argue that this method can be used by mediating agents to detect regularities in the behaviour of the involved participants and induce hypotheses about their preferences automatically. Finally, we discuss some advantages and disadvantages of using inductive logic programming as a method for learning user preferences and compare this method with other approaches. (c) 2005 Elsevier B.V. All rights reserved.
A continuing problem with inductive logic programming (ILP) has been the poor handling of numbers. Constraint inductive logic programming (CILP) aims to solve this problem with ILP. We propose a new approach to genera...
详细信息
A continuing problem with inductive logic programming (ILP) has been the poor handling of numbers. Constraint inductive logic programming (CILP) aims to solve this problem with ILP. We propose a new approach to generating numerical constraints in CILP, and describe an implementation of the CILP system (namely, BPU-CILP). In our approach, methods from pattern recognition and multivariate data analysis, such as Fisher's linear discriminant, dynamic clustering and principal component analysis, are introduced into CILP. The BPU-CILP can generate various forms of polynomial constraints of multiple dimensions, without additional background knowledge. As a result, the constraint logic program covering all positive examples and consistent with all negative examples can be derived automatically.
inductive learning in First-Order logic (FOL) is a hard task due to both the prohibitive size of the search space and the computational cost of evaluating hypotheses. This paper describes an evolutionary algorithm for...
详细信息
inductive learning in First-Order logic (FOL) is a hard task due to both the prohibitive size of the search space and the computational cost of evaluating hypotheses. This paper describes an evolutionary algorithm for concept learning in (a fragment of) FOL. The algorithm, called ECL (for Evolutionary Concept Learner), evolves a population of Horn clauses by repeated selection, mutation and optimization of more fit clauses. ECL relies on four greedy mutation operators for searching the hypothesis space, and employs an optimization phase that follows each mutation. Experimental results show that ECL works well in practice.
This paper presents a cognitive vision system capable of autonomously learning protocols from perceptual observations of dynamic scenes. The work is motivated by the aim of creating a synthetic agent that can observe ...
详细信息
This paper presents a cognitive vision system capable of autonomously learning protocols from perceptual observations of dynamic scenes. The work is motivated by the aim of creating a synthetic agent that can observe a scene containing interactions between unknown objects and agents, and learn models of these sufficient to act in accordance with the implicit protocols present in the scene. Discrete concepts (utterances and object properties), and temporal protocols involving these concepts, are learned in an unsupervised manner from continuous sensor input alone. Crucial to this learning process are methods for spatio-temporal attention applied to the audio and visual sensor data. These identify subsets of the sensor data relating to discrete concepts. Clustering within continuous feature spaces is used to learn object property and utterance models from processed sensor data, forming a symbolic description. The PROGOL inductive logic programming system is subsequently used to learn symbolic models of the temporal protocols presented in the presence of noise and over-representation in the symbolic data input to it. The models learned are used to drive a synthetic agent that can interact with the world in a semi-natural way. The system has been evaluated in the domain of table-top game playing and has been shown to be successful at learning protocol behaviours in such real-world audio-visual environments. (c) 2005 Elsevier B.V. All rights reserved.
We extend the notion of anti-unification to cover equational theories and present a method based on regular tree grammars to compute a finite representation of E-generalization sets. We present a framework to combine ...
详细信息
We extend the notion of anti-unification to cover equational theories and present a method based on regular tree grammars to compute a finite representation of E-generalization sets. We present a framework to combine inductive logic programming and E-generalization that includes an extension of Plotkin's lgg theorem to the equational case. We demonstrate the potential power of E-generalization by three example applications: computation of suggestions for auxiliary lemmas in equational inductive proofs, computation of construction laws for given term sequences, and learning of screen editor command sequences. (c) 2005 Elsevier B.V. All rights reserved.
A conjunctive query problem is a problem to determine whether or not a tuple belongs to the answer of a conjunctive query over a database. In this paper, a tuple, a conjunctive query and a database in relational datab...
详细信息
A conjunctive query problem is a problem to determine whether or not a tuple belongs to the answer of a conjunctive query over a database. In this paper, a tuple, a conjunctive query and a database in relational database theory are regarded as a ground atom, a nonrecursive function-free definite clause and a finite set of ground atoms, respectively, in inductive logic programming terminology. An acyclic conjunctive query problem is a conjunctive query problem with acyclicity. Concerned with the acyclic conjunctive query problem, in this paper, we present the hardness results of predicting acyclic conjunctive queries from an instance with a j-database of which predicate symbol is at most j-ary. Also we deal with two kinds of instances, a simple instance as a set of ground atoms and an extended instance as a set of pairs of a ground atom and a description. We mainly show that, from both a simple and an extended instances, acyclic conjunctive queries are not polynomial-time predictable withj-databases (j >= 3) under the cryptographic assumptions, and predicting acyclic conjunctive queries with 2-databases is as hard as predicting DNF formulas. Hence, the acyclic conjunctive queries become a natural example that the equivalence between subsumption-efficiency and efficient pac-learnability from both a simple and an extended instances collapses. (c) 2005 Elsevier B.V. All rights reserved.
暂无评论