Formal language identification: query learning vs. Gold-style learning

A natural approach towards powerful machine learning systems is to enable options for additional machine/user interactions, for instance by allowing the system to ask queries about the concept to be learned. This motivates the development and analysis of adequate formal learning models.In the present paper, we investigate two different types of query learning models in the context of learning indexable classes of recursive languages: Angluin's original model and a relaxation thereof, called learning with extra queries. In the original model the learner is restricted to query languages belonging to the target class, while in the new model it is allowed to query other languages, too. As usual, the following standard types of queries are considered: superset, subset, equivalence, and membership queries.The learning capabilities of the resulting query learning models are compared to one another and to different versions of Gold-style language learning from only positive data and from positive and negative data (including finite learning, conservative inference, and learning in the limit). A complete picture of the relation of all these models has been elaborated. A couple of interesting differences and similarities between query learning and Gold-style learning have been observed. In particular, query learning with extra superset queries coincides with conservative inference from only positive data. This result documents the naturalness of the new query model.     

Learning Fallible Deterministic Finite Automata

We consider the problem of learning from a fallible expert that answers all queries about a concept, but often gives incorrect answers. The expert can also be thought of as a truth table describing the concept which has been partially corrupted. In order to learn the underlying concept with arbitrarily high precision, we would like to use its structure in order to correct most of the incorrect answers. We assume that the expert's errors are uniformly and independently distributed, occur with any fixed probability strictly smaller than 1/2, and are persistent. In particular, we present a polynomial time algorithm using membership queries for correcting and learning fallible Deterministic Finite Automata under the uniform distribution.     

Polynomial Time Learnability of Simple Deterministic Languages

This paper is concerned with the problem of learning simple deterministic languages. The algorithm described in this paper is based on the theory of model inference given by Shapiro. In our setting, however, nonterminal membership queries, except for the start symbol, are not permitted. Extended equivalence queries are used instead. Nonterminals that are necessary for a correct grammar and their intended models are introduced automatically. We give an algorithm that, for any simple deterministic language L, outputs a grammar G in 2-standard form, such that L = L(G), using membership queries and extended equivalence queries. We also show that the algorithm runs in time polynomial in the length of the longest counterexample and the number of nonterminals in a minimal grammar for L.     

Learning two-tape automata from queries and counterexamples

We investigate the learning problem of two-tape deterministic finite automata (2-tape DFAs) from queries and counterexamples. Instead of accepting a subset of ∑*, a 2-tape DFA over an alphabet ∑ accepts a subset of ∑* × ∑*, and therefore, it can specify a binary relation on ∑*. In [3] Angluin showed that the class of deterministic finite automata (DFAs) is learnable in polynomial time from membership queries and equivalence queries, namely, from a minimally adequate teacher (MAT). In this article we show that the class of 2-tape DFAs is learnable in polynomial time from MAT. More specifically, we show an algorithm that, given any languageL accepted by an unknown 2-tape DFAM, learns from MAT a two-tape nonde-terministic finite automaton (2-tape NFA)M′ acceptingL in time polynomial inn andl, wheren is the size ofM andl is the maximum length of any counterexample provided during the learning process. This work was supported in part by Grants-in-Aid for Scientific Research No. 04229105 from the Ministry of Education, Science, and Culture, Japan.     

THE QSM ALGORITHM AND ITS APPLICATION TO SOFTWARE BEHAVIOR MODEL INDUCTION

This article presents a novel application of grammatical inference techniques to the synthesis of behavior models of software systems. This synthesis is used for the elicitation of software requirements. This problem is formulated as a deterministic finite-state automaton induction problem from positive and negative scenarios provided by an end user of the software-to-be. A query-driven state merging (QSM) algorithm is proposed. It extends the Regular Positive and Negative Inference (RPNI) and blue-fringe algorithms by allowing membership queries to be submitted to the end user. State merging operations can be further constrained by some prior domain knowledge formulated as fluents, goals, domain properties, and models of external software components. The incorporation of domain knowledge both reduces the number of queries and guarantees that the induced model is consistent with such knowledge. The proposed techniques are implemented in the ISIS tool and practical evaluations on standard requirements engineering test cases and synthetic data illustrate the interest of this approach.     

Design of flexible static program analyzers with PQL

Static program analyzers (SPA) are interactive tools that enhance program understanding during maintenance by answering queries about programs. Depending on the maintenance task in hand, SPAs must process different source programs and answer different types of program queries. Flexibility is, therefore, a desirable property of SPAs. The author describes a program query language, called PQL, that facilitates the design of flexible SPAs. PQL is a conceptual level, source language-independent notation to specify program queries and program views. In PQL, one can query global program design as well as search for detail code patterns. PQL queries are answered automatically by a query evaluation mechanism built into an SPA. Program design models and POL form the core of an SPA conceptual model. He based the SPA's architecture on this conceptual model. By separating the conceptual model from the implementation decisions, one can design SPAs that are customizable to the needs of the maintenance project at hand. Depending on criteria such as efficiency of query evaluation or simplicity of the SPA design, one can implement the same functional specifications of an SPA on a variety of program representations to meet the required criteria. Apart from its role in the design of SPAs, the conceptual model also allows one to rigorously study SPA functionality in the context of the underlying maintenance process and programmer behavior models, in isolation from tool implementation details     

A comparison of statistical relational learning and graph neural networks for aggregate graph queries

Statistical relational learning (SRL) and graph neural networks (GNNs) are two powerful approaches for learning and inference over graphs. Typically, they are evaluated in terms of simple metrics such as accuracy over individual node labels. Complex aggregate graph queries (AGQ) involving multiple nodes, edges, and labels are common in the graph mining community and are used to estimate important network properties such as social cohesion and influence. While graph mining algorithms support AGQs, they typically do not take into account uncertainty, or when they do, make simplifying assumptions and do not build full probabilistic models. In this paper, we examine the performance of SRL and GNNs on AGQs over graphs with partially observed node labels. We show that, not surprisingly, inferring the unobserved node labels as a first step and then evaluating the queries on the fully observed graph can lead to sub-optimal estimates, and that a better approach is to compute these queries as an expectation under the joint distribution. We propose a sampling framework to tractably compute the expected values of AGQs. Motivated by the analysis of subgroup cohesion in social networks, we propose a suite of AGQs that estimate the community structure in graphs. In our empirical evaluation, we show that by estimating these queries as an expectation, SRL-based approaches yield up to a 50-fold reduction in average error when compared to existing GNN-based approaches.

     

A general dimension for query learning

We introduce a combinatorial dimension that characterizes the number of queries needed to exactly (or approximately) learn concept classes in various models. Our general dimension provides tight upper and lower bounds on the query complexity for all sorts of queries, not only for example-based queries as in previous works.As an application we show that for learning DNF formulas, unspecified attribute value membership and equivalence queries are not more powerful than standard membership and equivalence queries. Further, in the approximate learning setting, we use the general dimension to characterize the query complexity in the statistical query as well as the learning by distances model. Moreover, we derive close bounds on the number of statistical queries needed to approximately learn DNF formulas.     

Fuzzy classifications using fuzzy inference networks

In this paper, fuzzy inference models for pattern classifications have been developed and fuzzy inference networks based on these models are proposed. Most of the existing fuzzy rule-based systems have difficulties in deriving inference rules and membership functions directly from training data. Rules and membership functions are obtained from experts. Some approaches use backpropagation (BP) type learning algorithms to learn the parameters of membership functions from training data. However, BP algorithms take a long time to converge and they require an advanced setting of the number of inference rules. The work to determine the number of inference rules demands lots of experiences from the designer. In this paper, self-organizing learning algorithms are proposed for the fuzzy inference networks. In the proposed learning algorithms, the number of inference rules and the membership functions in the inference rules will be automatically determined during the training procedure. The learning speed is fast. The proposed fuzzy inference network (FIN) classifiers possess both the structure and the learning ability of neural networks, and the fuzzy classification ability of fuzzy algorithms. Simulation results on fuzzy classification of two-dimensional data are presented and compared with those of the fuzzy ARTMAP. The proposed fuzzy inference networks perform better than the fuzzy ARTMAP and need less training samples.     

Learning with errors in answers to membership queries

We study the learning models defined in [D. Angluin, M. Krikis, R.H. Sloan, G. Turán, Malicious omissions and errors in answering to membership queries, Machine Learning 28 (2–3) (1997) 211–255]: Learning with equivalence and limited membership queries and learning with equivalence and malicious membership queries.We show that if a class of concepts that is closed under projection is learnable in polynomial time using equivalence and (standard) membership queries then it is learnable in polynomial time in the above models. This closes the open problems in [D. Angluin, M. Krikis, R.H. Sloan, G. Turán, Malicious omissions and errors in answering to membership queries, Machine Learning 28 (2–3) (1997) 211–255].Our algorithm can also handle errors in the equivalence queries.     

Randomly Fallible Teachers: Learning Monotone DNF with an Incomplete Membership Oracle

We introduce a new fault-tolerant model of algorithmic learning using an equivalence oracle and anincomplete membership oracle, in which the answers to a random subset of the learner's membership queries may be missing. We demonstrate that, with high probability, it is still possible to learn monotone DNF formulas in polynomial time, provided that the fraction of missing answers is bounded by some constant less than one. Even when half the membership queries are expected to yield no information, our algorithm will exactly identifym-term,n-variable monotone DNF formulas with an expectedO(mn ²) queries. The same task has been shown to require exponential time using equivalence queries alone. We extend the algorithm to handle some one-sided errors, and discuss several other possible error models. It is hoped that this work may lead to a better understanding of the power of membership queries and the effects of faulty teachers on query models of concept learning.     

A New Abstract Combinatorial Dimension for Exact Learning via Queries

We introduce an abstract model of exact learning via queries that can be instantiated to all the query learning models currently in use, while being closer to them than previous unifying attempts. We present a characterization of those Boolean function classes learnable in this abstract model, in terms of a new combinatorial notion that we introduce, the abstract identification dimension. Then we prove that the particularization of our notion to specific known protocols such as equivalence, membership, and membership and equivalence queries results in exactly the same combinatorial notions currently known to characterize learning in these models, such as strong consistency dimension, extended teaching dimension, and certificate size. Our theory thus fully unifies all these characterizations. For models enjoying a specific property that we identify, the notion can be simplified while keeping the same characterizations. From our results we can derive combinatorial characterizations of all those other models for query learning proposed in the literature. We can also obtain the first polynomial-query learning algorithms for specific interesting problems such as learning DNF with proper subset and superset queries.     

Separating models of learning with faulty teachers

We study the power of two models of faulty teachers in Valiant’s PAC learning model and Angluin’s exact learning model. The first model we consider is learning from an incomplete membership oracle introduced by Angluin and Slonim [D. Angluin, D.K. Slonim, Randomly fallible teachers: Learning monotone DNF with an incomplete membership oracle, Machine Learning 14 (1) (1994) 7–26]. In this model, the answers to a random subset of the learner’s membership queries may be missing. The second model we consider is random persistent classification noise in membership queries introduced by Goldman, Kearns and Schapire [S. Goldman, M. Kearns, R. Schapire, Exact identification of read-once formulas using fixed points of amplification functions, SIAM Journal on Computing 22 (4) (1993) 705–726]. In this model, the answers to a random subset of the learner’s membership queries are flipped.     

Malicious Omissions and Errors in Answers to Membership Queries

We consider two issues in polynomial-time exact learning of concepts using membership and equivalence queries: (1) errors or omissions in answers to membership queries, and (2) learning finite variants of concepts drawn from a learnable class.To study (1), we introduce two new kinds of membership queries: limited membership queries and malicious membership queries. Each is allowed to give incorrect responses on a maliciously chosen set of strings in the domain. Instead of answering correctly about a string, a limited membership query may give a special I don't know answer, while a malicious membership query may give the wrong answer. A new parameter Lis used to bound the length of an encoding of the set of strings that receive such incorrect answers. Equivalence queries are answered correctly, and learning algorithms are allowed time polynomial in the usual parameters and L. Any class of concepts learnable in polynomial time using equivalence and malicious membership queries is learnable in polynomial time using equivalence and limited membership queries; the converse is an open problem. For the classes of monotone monomials and monotone k-term DNF formulas, we present polynomial-time learning algorithms using limited membership queries alone. We present polynomial-time learning algorithms for the class of monotone DNF formulas using equivalence and limited membership queries, and using equivalence and malicious membership queries.To study (2), we consider classes of concepts that are polynomially closed under finite exceptions and a natural operation to add exception tables to a class of concepts. Applying this operation, we obtain the class of monotone DNF formulas with finite exceptions. We give a polynomial-time algorithm to learn the class of monotone DNF formulas with finite exceptions using equivalence and membership queries. We also give a general transformation showing that any class of concepts that is polynomially closed under finite exceptions and is learnable in polynomial time using standard membership and equivalence queries is also polynomial-time learnable using malicious membership and equivalence queries. Corollaries include the polynomial-time learnability of the following classes using malicious membership and equivalence queries: deterministic finite acceptors, boolean decision trees, and monotone DNF formulas with finite exceptions.     

A highly interpretable form of Sugeno inference systems

We present a form of fuzzy inference systems (FISs) that is highly interpretable and easy to manipulate. The form is based on a judicious choice of membership functions that have strong locality and differentiability properties and on a modification of the Sugeno and generalized Sugeno forms of the consequent polynomials so as to make them rule centered. Under these conditions, the coefficients in the consequent polynomials can be exactly interpreted as Taylor series coefficients. Besides the intuitive interpretation thus bestowed on the coefficients, we show that the new form allows easy design, manipulation, testing, training, and combination of the resulting fuzzy inference systems. The rudiments of a calculus of fuzzy inference systems are then introduced     

Complexity theoretic hardness results for query learning

We investigate the complexity of learning for the well-studied model in which the learning algorithm may ask membership and equivalence queries. While complexity theoretic techniques have previously been used to prove hardness results in various learning models, these techniques typically are not strong enough to use when a learning algorithm may make membership queries. We develop a general technique for proving hardness results for learning with membership and equivalence queries (and for more general query models). We apply the technique to show that, assuming , no polynomial-time membership and (proper) equivalence query algorithms exist for exactly learning read-thrice DNF formulas, unions of halfspaces over the Boolean domain, or some other related classes. Our hardness results are representation dependent, and do not preclude the existence of representation independent algorithms.?The general technique introduces the representation problem for a class F of representations (e.g., formulas), which is naturally associated with the learning problem for F. This problem is related to the structural question of how to characterize functions representable by formulas in F, and is a generalization of standard complexity problems such as Satisfiability. While in general the representation problem is in , we present a theorem demonstrating that for "reasonable" classes F, the existence of a polynomial-time membership and equivalence query algorithm for exactly learning F implies that the representation problem for F is in fact in co-NP. The theorem is applied to prove hardness results such as the ones mentioned above, by showing that the representation problem for specific classes of formulas is NP-hard. Received: December 6, 1994     

The query complexity of learning DFA

It is known that the class of deterministic finite automata is polynomial time learnable by using membership and equivalence queries. We investigate the query complexity of learning deterministic finite automata, i.e., the number of membership and equivalence queries made during the process of learning. We extend a known lower bound on membership queries to the case of randomized learning algorithms, and prove lower bounds on the number of alternations between membership and equivalence queries. We also show that a trade-off exists, allowing us to reduce the number of equivalence queries at the price of increasing the number of membership queries.     

How Many Queries Are Needed to Learn One Bit of Information?

In this paper we study the question how many queries are needed to halve a given version space. In other words: how many queries are needed to extract from the learning environment the one bit of information that rules out fifty percent of the concepts which are still candidates for the unknown target concept. We relate this problem to the classical exact learning problem. For instance, we show that lower bounds on the number of queries needed to halve a version space also apply to randomized learners (whereas the classical adversary arguments do not readily apply). Furthermore, we introduce two new combinatorial parameters, the halving dimension and the strong halving dimension, which determine the halving complexity (modulo a small constant factor) for two popular models of query learning: learning by a minimum adequate teacher (equivalence queries combined with membership queries) and learning by counterexamples (equivalence queries alone). These parameters are finally used to characterize the additional power provided by membership queries (compared to the power of equivalence queries alone). All investigations are purely information-theoretic and ignore computational issues.     

Relations between Gold-style learning and query learning

Different formal learning models address different aspects of human learning. Below we compare Gold-style learning—modelling learning as a limiting process in which the learner may change its mind arbitrarily often before converging to a correct hypothesis—to learning via queries—modelling learning as a one-shot process in which the learner is required to identify the target concept with just one hypothesis. In the Gold-style model considered below, the information presented to the learner consists of positive examples for the target concept, whereas in query learning, the learner may pose a certain kind of queries about the target concept, which will be answered correctly by an oracle (called teacher). Although these two approaches seem rather unrelated at first glance, we provide characterisations of different models of Gold-style learning (learning in the limit, conservative inference, and behaviourally correct learning) in terms of query learning. Thus we describe the circumstances which are necessary to replace limit learners by equally powerful one-shot learners. Our results are valid in the general context of learning indexable classes of recursive languages. This analysis leads to an important observation, namely that there is a natural query learning type hierarchically in-between Gold-style learning in the limit and behaviourally correct learning. Astonishingly, this query learning type can then again be characterised in terms of Gold-style inference.