Inference of regular languages using state merging algorithms with search

State merging algorithms have emerged as the solution of choice for the problem of inferring regular grammars from labeled samples, a known NP-complete problem of great importance in the grammatical inference area. These methods derive a small deterministic finite automaton from a set of labeled strings (the training set), by merging parts of the acceptor that corresponds to this training set. Experimental and theoretical evidence have shown that the generalization ability exhibited by the resulting automata is highly correlated with the number of states in the final solution.As originally proposed, state merging algorithms do not perform search. This means that they are fast, but also means that they are limited by the quality of the heuristics they use to select the states to be merged. Sub-optimal choices lead to automata that have many more states than needed and exhibit poor generalization ability.In this work, we survey the existing approaches that generalize state merging algorithms by using search to explore the tree that represents the space of possible sequences of state mergings. By using heuristic guided search in this space, many possible state merging sequences can be considered, leading to smaller automata and improved generalization ability, at the expense of increased computation time.We present comparisons of existing algorithms that show that, in widely accepted benchmarks, the quality of the derived solutions is improved by applying this type of search. However, we also point out that existing algorithms are not powerful enough to solve the more complex instances of the problem, leaving open the possibility that better and more powerful approaches need to be designed.     

Learning efficiency of very simple grammars from positive data

The class of very simple grammars is known to be polynomial-time identifiable in the limit from positive data. This paper gives an even more general discussion on the efficiency of identification of very simple grammars from positive data, which includes both positive and negative results. In particular, we present an alternative efficient inconsistent learning algorithm for very simple grammars.     

Learning tree languages from positive examples and membership queries

We investigate regular tree languages’ exact learning from positive examples and membership queries. Input data are trees of the language to infer. The learner computes new trees from the inputs and asks the oracle whether or not they belong to the language. From the answers, the learner may ask further membership queries until he finds the correct grammar that generates the target language. This paradigm was introduced by Angluin in the seminal work [D. Angluin, A note on the number of queries needed to identify regular languages, Information and Control 51 (1981) 76–87] for the case of regular word languages. Neither negative examples, equivalence queries nor counter-examples are allowed in this paradigm.     

A solution of the syntactical induction-inference problem for regular languages

A Teacher knows a regular language L(G), in the form of a finite state acceptor. A method is described for selecting a set of examples, strings X, each in L(G) as inputs to the Pupil. The Set X is mapped into a lattice W (in Pupil) of finite state machines. A mapping is defined from pairs of machines in the lattice W into strings y, each of which serves as a ”crucial experiment”. The Teacher is asked to decide if the string y belongs to L(G). The process then repeats or terminates.This procedure is shown to converge (if Teacher answers truthfully) to a finite state acceptor accepting only strings of L(G)(which obviously may be brought into canonical, minimal state form). However, this process does not depend on state minimization as an inference method.The only necessary condition for the inference process is that every move (edge) of that finite state acceptor U(X) chosen to correspond to L(G) must be applied at least once in generating some string x in X. A proof is given that if the Teacher answers correctly, the Pupil will infer a machine behaviorally equivalent to the original acceptor U.Elements of the lattice W are constructed by successive refinement of the partitions of the state set of the initial finite state machine U(X). Pairs are chosen in an ordered process and converted to deterministic and completely specified machines, if necessary. The two machines are tested for behavioral equivalence. If they are equivalent, one is eliminated. If not, a testing string y belonging to one machine, but not the other, is constructed and output to the teacher. If y belongs to L(G), one machine is eliminated. If not, y is tested by the Pupil against a sequence of machines generated internally. If only one machine is left, the process terminates, otherwise two new candidate machines are chosen. The algorithm described is relatively simple and easy to understand, but does not necessarily produce a minimal time solution.     

Optimal language learning from positive data

Gold?s original paper on inductive inference introduced a notion of an optimal learner. Intuitively, a learner identifies a class of objects optimally iff there is no other learner that: requires as little of each presentation of each object in the class in order to identify that object, and, for some presentation of some object in the class, requires less of that presentation in order to identify that object. Beick considered this notion in the context of function learning, and gave an intuitive characterization of an optimal function learner. Jantke and Beick subsequently characterized the classes of functions that are algorithmically, optimally identifiable.Herein, Gold?s notion is considered in the context of language learning. It is shown that a characterization of optimal language learners analogous to Beick?s does not hold. It is also shown that the classes of languages that are algorithmically, optimally identifiable cannot be characterized in a manner analogous to that of Jantke and Beick.Other interesting results concerning optimal language learning include the following. It is shown that strong non-U-shapedness, a property involved in Beick?s characterization of optimal function learners, does not restrict algorithmic language learning power. It is also shown that, for an arbitrary optimal learner F of a class of languages L, F optimally identifies a subclass K of L iff F is class-preserving with respect to K.     

Inference of finite-state transducers from regular languages

Finite-state transducers are models that are being used in different areas of pattern recognition and computational linguistics. One of these areas is machine translation, where the approaches that are based on building models automatically from training examples are becoming more and more attractive. Finite-state transducers are very adequate to be used in constrained tasks where training samples of pairs of sentences are available. A technique to infer finite-state transducers is proposed in this work. This technique is based on formal relations between finite-state transducers and finite-state grammars. Given a training corpus of input-output pairs of sentences, the proposed approach uses statistical alignment methods to produce a set of conventional strings from which a stochastic finite-state grammar is inferred. This grammar is finally transformed into a resulting finite-state transducer. The proposed methods are assessed through series of machine translation experiments within the framework of the EUTRANS project.     

A note on phase transitions and computational pitfalls of learning from sequences

An ever greater range of applications call for learning from sequences. Grammar induction is one prominent tool for sequence learning, it is therefore important to know its properties and limits. This paper presents a new type of analysis for inductive learning. A few years ago, the discovery of a phase transition phenomenon in inductive logic programming proved that fundamental characteristics of the learning problems may affect the very possibility of learning under very general conditions. We show that, in the case of grammatical inference, while there is no phase transition when considering the whole hypothesis space, there is a much more severe “gap” phenomenon affecting the effective search space of standard grammatical induction algorithms for deterministic finite automata (DFA). Focusing on standard search heuristics, we show that they overcome this difficulty to some extent, but that they are subject to overgeneralization. The paper last suggests some directions to alleviate this problem.

Boosting for transfer learning from multiple data sources

Transfer learning aims at adapting a classifier trained on one domain with adequate labeled samples to a new domain where samples are from a different distribution and have no class labels. In this paper, we explore the transfer learning problems with multiple data sources and present a novel boosting algorithm, SharedBoost. This novel algorithm is capable of applying for very high dimensional data such as in text mining where the feature dimension is beyond several ten thousands. The experimental results illustrate that the SharedBoost algorithm significantly outperforms the traditional methods which transfer knowledge with supervised learning techniques. Besides, SharedBoost also provides much better classification accuracy and more stable performance than some other typical transfer learning methods such as the structural correspondence learning (SCL) and the structural learning in the multiple sources transfer learning problems.     

Ranking discovered rules from data mining with multiple criteria by data envelopment analysis

In data mining applications, it is important to develop evaluation methods for selecting quality and profitable rules. This paper utilizes a non-parametric approach, Data Envelopment Analysis (DEA), to estimate and rank the efficiency of association rules with multiple criteria. The interestingness of association rules is conventionally measured based on support and confidence. For specific applications, domain knowledge can be further designed as measures to evaluate the discovered rules. For example, in market basket analysis, the product value and cross-selling profit associated with the association rule can serve as essential measures to rule interestingness. In this paper, these domain measures are also included in the rule ranking procedure for selecting valuable rules for implementation. An example of market basket analysis is applied to illustrate the DEA based methodology for measuring the efficiency of association rules with multiple criteria.     

Method of probabilistic inference from learning data in Bayesian networks

Bayesian networks (BN) are a powerful tool for various data-mining systems. The available methods of probabilistic inference from learning data have shortcomings such as high computation complexity and cumulative error. This is due to a partial loss of information in transition from empiric information to conditional probability tables. The paper presents a new simple and exact algorithm for probabilistic inference in BN from learning data. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 93–99, May–June 2007.     

Dealing with conflicting information from multiple nonlinear texts: Effects of prior attitudes

This study investigated the effects of prior attitudes on how students deal with conflicting information in multiple nonlinear texts. Sixty-one Dutch 11th grade students read multiple texts on a controversial topic and wrote a short essay on it. These essays were scored on perspective taken and the origin of information included in them. Ordinal regression analysis showed that students with strong prior attitudes were significantly more likely to write essays that were biased towards their prior attitudes. Furthermore, multiple regression analyses revealed that students with strong attitudes took explicit stances and added large proportions of information not presented in the reading materials in their essays, whereas students with neutral attitudes wrote syntheses and borrowed more information from the materials. Overall, results show that prior attitudes can bias how students deal with conflicting information in an open-ended reading and writing task.