Published in Discrete Mathematics and Applications
We consider exact attribute-efficient learning of functions from Post closed classes using membership queries and obtain bounds on learning complexity.
We present a polynomial update time algorithm for the inductive inference of a large class of context-free languages using the paradigm of positive data and a membership oracle. We achieve this result by moving to a novel representation, called Contextual Binary Feature Grammars (CBFGs), which are capable of representing richly structured context-f...
Dans le but de modéliser l'apprentissage des langues naturelles, nous nous intéressons à l'apprentissage des langages réguliers d'arbres à partir d'exemples positifs et en interaction avec un expert. L'expert est un oracle qui connaît le langage appris et qui répond à des questions d'appartenance. Nous donnons un algorithme efficace d'apprentissage...
Published in Machine Learning
We consider the problem of determining which of a set of experts has tastes most similar to a given user by asking the user questions about his likes and dislikes. We describe a simple algorithm for generating queries for a theoretical model of this problem. We show that the algorithm requires at most opt(F)(ln(|F|/opt(F)) + 1) + 1 queries to find ...
Published in Machine Learning
We study the complexity of learning arbitrary Boolean functions of n variables by membership queries, if at most r variables are relevant. Problems of this type have important applications in fault searching, e.g. logical circuit testing and generalized group testing. Previous literature concentrates on special classes of such Boolean functions and...
Published in Machine Learning
We consider exact learning monotone CNF formulas in which each variable appears at most some constant k times ("read-k" monotone CNF). Let f : {0,1}n → {0,1} be expressible as a read-k monotone CNF formula for some natural number k. We give an incremental output polynomial time algorithm for exact learning both the read-k CNF and (not necessarily r...
