#
Publication search

with membership queries as keyword

Bistrigova, Anastasiya V.
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.

Clark, Alexander Eyraud, Rémi Habrard, Amaury

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...

Besombes, Jérôme Marion, Jean-Yves

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...

Dasgupta, Sanjoy Lee, Wee Sun Long, Philip M.
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 ...

Damaschke, Peter
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...

Domingo, Carlos Mishra, Nina Pitt, Leonard
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...