Search

Subject of Research. The paper studies minimum-sized deterministic finite automata inferring problem. A hybrid method is developed and implemented reducing the given problem to Boolean satisfiability (SAT) technique and at the same time applying a counterexample guided abstraction refinement approach. Method. It is proposed to use not all given behavior examples as training data but start with some subset of them and build a consistent automaton, using SATbased automata inferring method. Then the built automaton is checked against the complete set of behavior examples. The examples not consistent with the automaton are counterexamples. Some subset of counterexamples is added to the current training data and the process is being repeated. Main Results. The proposed method is implemented as a part of deterministic finite automata inferring tool in Python language. Experimental comparison of the developed method and the SAT-based method without abstraction refinement is carried out. Practical Relevance. Experimental research has shown that the developed method is reasonable for application if the number of behavior examples is large enough, at least, two hundred times exceeds the number of the automaton states, and, therefore, the Boolean formula being created contains tens and hundreds of millions of clauses.

International audience; This paper is an attempt to bridge the gap between deep learning and grammatical inference. Indeed, it provides an algorithm to extract a (stochastic) formal language from any recurrent neural network trained for language modelling. In detail, the algorithm uses the already trained network as an oracle-and thus does not require the access to the inner representation of the black-box-and applies a spectral approach to infer a weighted automaton. As weighted automata compute linear functions, they are computationally more efficient than neural networks and thus the nature of the approach is the one of knowledge distillation. We detail experiments on 62 data sets (both synthetic and from real-world applications) that allow an in-depth study of the abilities of the proposed algorithm. The results show the WA we extract are good approximations of the RNN, validating the approach. Moreover, we show how the process provides interesting insights toward the behavior of RNN learned on data, enlarging the scope of this work to the one of explainability of deep learning models.

The paper is devoted to one of the key open problems of development of SPRELP system (the Syntactic Pattern Recognition-based Electrical Load Prediction System). The main module of SPRELP System is based on a GDPLL(\(k\)) grammar that is built according to the unsupervised learning paradigm. The GDPLL(\(k\)) grammar is generated by a grammatical inference algorithm. The algorithm doesn’t take into account an additional knowledge (the knowledge is partial and corresponds only to some examples) provided by a human expert. The accuracy of the forecast could be better if we took advantage of this knowledge. The problem of how to construct the model of a semi-supervised learning for SPRLP system that includes the additional expert knowledge is discussed in the paper. We also present several possible solutions.

This paper shows how methods from statistical relational learning can be used to address problems in grammatical inference using model-theoretic representations of strings. These model-theoretic representations are the basis of representing formal languages logically. Conventional representations include a binary relation for order and unary relations describing mutually exclusive properties of each position in the string. This paper presents experiments on the learning of formal languages, and their stochastic counterparts, with unconventional models, which relax the mutual exclusivity condition. Unconventional models are motivated by domain-specific knowledge. Comparison of conventional and unconventional word models shows that in the domains of phonology and robotic planning and control, Markov Logic Networks With unconventional models achieve better performance and less runtime with smaller networks than Markov Logic Networks With conventional models.

The paper contributes to the design of secure and resilient supervisory Cyber-Physical Systems (CPS) through learning. The reported approach involves the inclusion of learning modules in each of the supervised agents, and considers a scenario where the system’s coordinator privately transmits to individual agents their action plans in the form of symbolic strings. Each agent’s plans belong in some particular class of (sub-regular) languages, which is identifiable in the limit from positive data. With knowledge of the class of languages their plans belong to, agents can observe their coordinator’s instructions and utilize appropriate Grammatical Inference modules to identify the behavior specified for them. From that, they can then work collectively to infer the executive function of their supervisor. The paper proves that in cases where the coordinator fails, or communication to subordinates is disrupted, agents are able not only to maintain functional capacity but also to recover normalcy of operation by reconstructing their coordinator. Guaranteeing normalcy recovery in supervisory CPSs is critical in cases of a catastrophic failure or malicious attack, and is important for the design of next-generation Cyber-Physical Systems.

In this paper, we present a new open-source software library, Gl-learning, for grammatical inference. The rise of new application scenarios in recent years has required optimized methods to address knowledge extraction from huge amounts of data and to model highly complex systems. Our library implements the main state-of-the-art algorithms in the grammatical inference field (RPNI, EDSM, L*), redesigned through the OpenMP library for a parallel execution that drastically decreases execution times. To our best knowledge, it is also the first comprehensive library including a noise tolerance learning algorithm, such as Blue*, that significantly broadens the range of the potential application scenarios for grammar models. The modular design of our C++ library makes it an efficient and extensible framework for the design of further novel algorithms.

[EN] In this thesis, the problem of multilingual spoken language understanding is addressed using graphs to model and combine the different knowledge sources that take part in the understanding process. As a result of this work, a full multilingual spoken language understanding system has been developed, in which statistical models and graphs of linguistic units are used. One key feature of this system is its ability to combine and process multiple inputs provided by one or more sources such as speech recognizers or machine translators. A graph-based monolingual spoken language understanding system was developed as a starting point. The input to this system is a set of sentences that is provided by one or more speech recognition systems. First, these sentences are combined by means of a grammatical inference algorithm in order to build a graph of words. Next, the graph of words is processed to construct a graph of concepts by using a dynamic programming algorithm that identifies the lexical structures that represent the different concepts of the task. Finally, the graph of concepts is used to build the best sequence of concepts.The multilingual case happens when the user speaks a language different to the one natively supported by the system. In this thesis, a test-on-source approach was followed. This means that the input sentences are translated into the system's language, and then they are processed by the monolingual system. For this purpose, two speech translation systems were developed. The output of these speech translation systems are graphs of words that are then processed by the monolingual graph-based spoken language understanding system. Both in the monolingual case and in the multilingual case, the experimental results show that a combination of several inputs allows to improve the results obtained with a single input. In fact, this approach outperforms the current state of the art in many cases when several inputs are combined., [ES] En esta tesis se aborda el problema de la comprensión multilingüe del habla utilizando grafos para modelizar y combinar las diversas fuentes de conocimiento que intervienen en el proceso. Como resultado se ha desarrollado un sistema completo de comprensión multilingüe que utiliza modelos estadísticos y grafos de unidades lingüísticas. El punto fuerte de este sistema es su capacidad para combinar y procesar múltiples entradas proporcionadas por una o varias fuentes, como reconocedores de habla o traductores automáticos.Como punto de partida se desarrolló un sistema de comprensión multilingüe basado en grafos. La entrada a este sistema es un conjunto de frases obtenido a partir de uno o varios reconocedores de habla. En primer lugar, se aplica un algoritmo de inferencia gramatical que combina estas frases y obtiene un grafo de palabras. A continuación, se analiza el grafo de palabras mediante un algoritmo de programación dinámica que identifica las estructuras léxicas correspondientes a los distintos conceptos de la tarea, de forma que se construye un grafo de conceptos. Finalmente, se procesa el grafo de conceptos para encontrar la mejo secuencia de conceptos.El caso multilingüe ocurre cuando el usuario habla una lengua distinta a la original del sistema. En este trabajo se ha utilizado una estrategia test-on-source, en la cual las frases de entrada se traducen al lenguaje del sistema y éste las trata de forma monolingüe. Para ello se han propuesto dos sistemas de traducción del habla cuya salida son grafos de palabras, los cuales son procesados por el algoritmo de comprensión basado en grafos. Tanto en la configuración monolingüe como en la multilingüe los resultados muestran que la combinación de varias entradas permite mejorar los resultados obtenidos con una sola entrada. De hecho, esta aproximación consigue en muchos casos mejores resultados que el actual estado del arte cuando se utiliza una combinación de varias entradas., [CAT] Aquesta tesi tracta el problema de la comprensió multilingüe de la parla utilitzant grafs per a modelitzar i combinar les diverses fonts de coneixement que intervenen en el procés. Com a resultat s'ha desenvolupat un sistema complet de comprensió multilingüe de la parla que utilitza models estadístics i grafs d'unitats lingüístiques. El punt fort d'aquest sistema és la seua capacitat per combinar i processar múltiples entrades proporcionades per una o diverses fonts, com reconeixedors de la parla o traductors automàtics.Com a punt de partida, es va desenvolupar un sistema de comprensió monolingüe basat en grafs. L'entrada d'aquest sistema és un conjunt de frases obtingut a partir d'un o més reconeixedors de la parla. En primer lloc, s'aplica un algorisme d'inferència gramatical que combina aquestes frases i obté un graf de paraules. A continuació, s'analitza el graf de paraules mitjançant un algorisme de programació dinàmica que identifica les estructures lèxiques corresponents als distints conceptes de la tasca, de forma que es construeix un graf de conceptes. Finalment, es processa aquest graf de conceptes per trobar la millor seqüència de conceptes.El cas multilingüe ocorre quan l'usuari parla una llengua diferent a l'original del sistema. En aquest treball s'ha utilitzat una estratègia test-on-source, en la qual les frases d'entrada es tradueixen a la llengua del sistema, i aquest les tracta de forma monolingüe. Per a fer-ho es proposen dos sistemes de traducció de la parla l'eixida dels quals són grafs de paraules. Aquests grafs són posteriorment processats per l'algorisme de comprensió basat en grafs. Tant per la configuració monolingüe com per la multilingüe els resultats mostren que la combinació de diverses entrades és capaç de millorar el resultats obtinguts utilitzant una sola entrada. De fet, aquesta aproximació aconsegueix en molts casos millors resultats que l'actual estat de l'art quan s'utilitza una combinació de diverses entrades., Calvo Lance, M. (2016). A Strategy for Multilingual Spoken Language Understanding Based on Graphs of Linguistic Units [Tesis doctoral no publicada]. Universitat Politècnica de València. doi:10.4995/Thesis/10251/62407., TESIS

Knowledge extraction has traditionally represented one of the most interesting challenges in AI; in recent years, however, the availability of large collections of data has increased the awareness that “measuring” does not seamlessly translate into “understanding”, and that more data does not entail more knowledge. We propose here a formulation of knowledge extraction in terms of Grammatical Inference (GI), an inductive process able to select the best grammar consistent with the samples. The aim is to let models emerge from data themselves, while inference is turned into a search problem in the space of consistent grammars, induced by samples, given proper generalization operators. We will finally present an application to the extraction of structural models representing user mobility behaviors, based on public datasets.

International audience; Learning the language of biological sequences is an appealing challenge for the grammatical inference research field.While some first successes have already been recorded, such as the inference of profile hidden Markov models or stochastic context-free grammars which are now part of the classical bioinformatics toolbox, it is still a source of open and nice inspirational problems for grammatical inference, enabling us to confront our ideas to real fundamental applications. As an introduction to this field, we survey here the main ideas and concepts behind the approaches developed in pattern/motif discovery and grammatical inference to characterize successfully the biological sequences with their specificities.

Some dependency treebanks use special sequences of dependencies where main arguments are mixed with separators. Classical Categorial Dependency Grammars (CDG) do not allow this construction because iterative dependency types only introduce the iterations of the same dependency. An extension of CDG is defined here that introduces a new construction for repeatable sequences of one or several dependency names. The learnability properties of the extended CDG when grammars are infered from a dependency treebank is also studied. It leads to the definition of new classes of grammars that are learnable in the limit from dependency structures.

[EN] In this article, the first public release of GREAT as an open-source, statistical machine translation (SMT) software toolkit is described. GREAT is based on a bilingual language modelling approach for SMT, which is so far implemented for n-gram models based on the framework of stochastic finite-state transducers. The use of finite-state models is motivated by their simplicity, their versatility, and the fact that they present a lower computational cost, if compared with other more expressive models. Moreover, if translation is assumed to be a subsequential process, finite-state models are enough for modelling the existing relations between a source and a target language. GREAT includes some characteristics usually present in state-of-the-art SMT, such as phrase-based translation models or a log-linear framework for local features. Experimental results on a well-known corpus such as Europarl are reported in order to validate this software. A competitive translation quality is achieved, yet using both a lower number of model parameters and a lower response time than the widely-used, state-of-the-art SMT system Moses. © 2011 Springer Science+Business Media B.V., Study was supported by the EC (FEDER, FSE), the Spanish government (MICINN, MITyC, “Plan E”, under Grants MIPRCV “Consolider Ingenio 2010”, iTrans2 TIN2009-14511, and erudito.com TSI-020110-2009-439), and the Generalitat Valenciana (Grant Prometeo/2009/014).

It is investigated for which choice of a parameter q, denoting the number of contexts, the class of simple external contextual languages is iteratively learnable. On one hand, the class admits, for all values of q, polynomial time learnability provided an adequate choice of the hypothesis space is given. On the other hand, additional constraints like consistency and conservativeness or the use of a one-one hypothesis space changes the picture -- iterative learning limits the long term memory of the learner to the current hypothesis and these constraints further hinder storage of information via padding of this hypothesis. It is shown that if q> 3, then simple external contextual languages are not iteratively learnable using a class preserving one-one hypothesis space, while for q= 1 it is iteratively learnable, even in polynomial time. For the intermediate levels, there is some indication that iterative learnability using a class preserving one-one hypothesis space might depend on the size of the alphabet. It is also investigated for which choice of the parameters, the simple external contextual languages can be learnt by a consistent and conservative iterative learner.

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.

The aim of this paper is to develop a new algorithm that, with a complete sample as input, identifies the family of regular languages by means of nondeterministic finite automata. It is a state-merging algorithm. One of its main features is that the convergence (which is proved) is achieved independently from the order in which the states are merged, that is, the merging of states may be done “randomly”.

National audience; In this theoretical paper, we compare the "classical" learning techniques used to infer regular grammars from positive examples with the ones used to infer categorial grammars. To this aim, we first study how to translate finite state automata into categorial grammars and back. We then show that the generalization operators employed in both domains can be compared, and that their result can always be represented by generalized automata, called "recursive automata". The relation between these generalized automata and categorial grammars is studied in detail. Finally, new learnable subclasses of categorial grammars are defined, for which learning from strings is nearly not more expensive than from structures.

We show that simple deterministic languages are polynomial time learnable via membership queries if the learner knows a special finite set of positive examples. This finite set is called a representative sample and has been introduced by Angluin Inform. Control 51 (1981) to show that regular languages are polynomial time learnable via membership queries. If simple deterministic languages are learnable in polynomial time via membership and equivalence queries, we can obtain a representative sample of a target language in polynomial time from a correct hypothesis. Thus, our result implies that the polynomial time learning problem of simple deterministic languages via membership and equivalence queries is solvable if and only if we can find a representative sample in polynomial time via these queries. We show the learnability of simple deterministic languages by giving a learning algorithm. The algorithm, at the first stage, makes all possible candidate rules to generate the target language and a set of simple deterministic grammars which are little different each other. Then, comparing them, the algorithm eliminates inappropriate rules.

Residual languages are important and natural components of regular languages and several grammatical inference algorithms naturally rely on this notion. In order to identify a given target language L, classical inference algorithms try to identify words which define identical residual languages of L. Here, we study whether it could be interesting to perform a tighter analysis by identifying inclusion relations between the residual languages of L. We consider the class of Residual Finite State Automata (RFSAs). An RFSA A is a NonDeterministic Automaton whose states corresponds to residual languages of the language LA it recognizes. The inclusion relations between residual languages of LA can be naturally materialized on A. We prove that the class of RFSAs is not polynomially characterizable. We lead some experiments which show that when a regular language is randomly drawn by using a nondeterministic representation, the number of inclusion relations between its residual languages is very important. Moreover, its minimal RFSA representation is much smaller than its minimal DFA representation. Finally, we design a new learning algorithm, DeLeTe2, based on the search for the inclusion relations between the residual languages of the target language. We give sufficient conditions for the identifiability of the target language. We experimentally compare the performance of DeLeTe2 to those of classical inference algorithms.

We show how appropriately chosen functions f which we call distinguishing can be used to make deterministic finite automata backward deterministic. This idea can be exploited to design regular language classes called f-distinguishable which are identifiable in the limit from positive samples. Special cases of this approach are the k-reversible and terminal distinguishable languages, as discussed in Angluin (J. Assoc. Comput. Mach. 29 (3) (1982) 741), Fernau (Technical Report WSI-99-23, Universität Tübingen (Germany), Wilhelm-Schickard-Institut für Informatik, 1999, Short version published in the proceedings of AMAI 2000, see \tt http://rutcor.rutgers.edu/~amai/aimath00/AcceptedCont.htm, Proc. 15th Internat. Conf. on Pattern Recognition (ICPR 2000), Vol. 2, IEEE Press, New York, 2000, pp. 125–128), Radhakrishnan (Ph.D. Thesis, Department of Computer Science and Engineering, Indian Institute of Technology, Bombay, India, 1987), Radhakrishnan and Nagaraja (IEEE Trans. Systems, Man Cybernet. 17 (6) (1987) 982). Moreover, we show that all regular languages may be approximated in the setting introduced by Kobayashi and Yokomori (in: K. P. Jantke, T. Shinohara, Th. Zeugmann (Eds.), Proc. Sixth Internat. Conf. Algorithmic Learning Theory (ALT’95), Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence, Vol. 997, Springer, Berlin, 1995, pp. 298–312), (Theoret. Comput. Sci. 174 (1997) 251–257) by any class of f-distinguishable languages. Observe that the class of all function-distinguishable languages is equal to the class of regular languages.

We show that so-called deterministic even linear simple matrix grammars can be inferred in polynomial time using the query-based learner–teacher model (minimally adequate teacher-learning model) proposed by Angluin (Inform. and Comput. 75 (1987) 87) for learning deterministic regular languages. In this way, we extend the class of efficiently learnable languages beyond both the even linear languages and the even equal matrix languages (Pattern Recognition 21 (1988) 55; Proc. 2nd Internat. Colloq. on Grammatical Inference (ICGI-94): Grammatical Inference and Applications, Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence, vol. 862, Springer, Berlin, 1994, p. 38; Inform. Process. Lett. 28 (1988) 193; Technical Report IIAS-RR-93-6E, Fujitsu Laboratories, 1992; Parallel Image Analysis, ICPIA’92, Lecture Notes in Computer Science, vol. 652, Springer, Berlin, 1992, p. 274; Inform. and Comput. 123 (1995) 138; Algorithmic Learning for Knowledge-Based Systems, Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence, Springer, Berlin, 1995, p. 317). Moreover, we investigate formal language properties of even linear simple matrix languages and related language classes. More precisely, we discuss characterizations, (proper) inclusion relations, closure properties and decidability questions. This way, we also show that, in a certain sense, the idea of iterating the control language approach for learning purposes, as undertook by Takada (1995), could be seen as a special case of using deterministic even linear simple matrix grammars as basic and uniform learning target.

We discuss in this short survey article some current mathematical models from neurophysiology for the computational units of biological neural systems: neurons and synapses. These models are contrasted with the computational units of common artificial neural network models, which reflect the state of knowledge in neurophysiology 50 years ago. We discuss the problem of carrying out computations in circuits consisting of biologically realistic computational units, focusing on the biologically particularly relevant case of computations on time series. Finite state machines are frequently used in computer science as models for computations on time series. One may argue that these models provide a reasonable common conceptual basis for analyzing computations in computers and biological neural systems, although the emphasis in biological neural systems is shifted more towards asynchronous computation on analog time series. In the second half of this article some new computer experiments and theoretical results are discussed, which address the question whether a biological neural system can, in principle, learn to behave like a given simple finite state machine.

Selecting the optimal topology of a neural network for a particular application is a difficult task. In the case of recurrent neural networks, most methods only induce topologies in which their neurons are fully connected. In this paper, we present a genetic algorithm capable of obtaining not only the optimal topology of a recurrent neural network but also the least number of connections necessary. Finally, this genetic algorithm is applied to a problem of grammatical inference using neural networks, with very good results.

In this paper, a new formalism that permits to represent a non-trivial class of context-sensitive languages, the Augmented Regular Expressions (AREs), is introduced. AREs augment the expressive power of Regular Expressions (REs) by including a set of constraints that involve the number of instances in a string of the operands of the star operations of an RE. An efficient algorithm is given to recognize language strings by AREs. Also a general learning method to infer AREs from examples is presented, that consists of a regular grammatical inference step, a DFA to RE transformation, an RE parsing of the examples, and a constraint induction process.

Part 15: Energy Systems - II; International audience; A new approach in detecting and identifying power quality disturbances is presented. The use of Formal Language Theory, already exploited in other fields, was used to develop an innovative tool to identify patterns in electrical signals. The Concordia transform is applied to the 3-phase electrical system, composing a 2-D signal. The obtained signal is computed with a “healthy” 3-phase composed signal, retrieving new data. A Formal Language based inference algorithm is used to infer a grammar from this new data. Each type of fault has its own grammar, which allows the developed algorithm to easily detect and identify the disturbances.

Recurrent neural networks processing symbolic strings can be regarded as adaptive neural parsers. Given a set of positive and negative examples, picked up from a given language, adaptive neural parsers can effectively be trained to infer the language grammar. In this paper we use adaptive neural parsers to face the problem of inferring grammars from examples that are corrupted by a kind of noise that simply changes their membership.We propose a training algorithm, referred to as hybrid finite state filter (HFF), which is based on a parsimony principle that penalizes the development of complex rules.We report very promising experimental results showing that the proposed inductive inference scheme is indeed capable of capturing rules, while removing noise.

Colloque avec actes et comité de lecture. internationale.; International audience; We define the class of reversible classical categorial grammars, similar in the spirit to the notion of reversible class of languages introduced by Angluin and Sakkakibara. We show that the class of reversible classical categorial grammars is identifiable from positive structured examples. For this, we provide an original algorithm, which runs in quadratic time in the size of the examples. This work extends the previous results of Kanazawa. Indeed, in our work, several types can be associated to a word and the class is still identifiable in polynomial time. We illustrate the relevance of the class of reversible classical categorial grammars with linguistic examples.

[EN] In this paper, a new method for modelling tRNA secondary structures is presented. This method is based on the combination of stochastic context-free grammars (SCFG) and Hidden Markov Models (HMM). HMM are used to capture the local relations in the loops of the molecule (nonstructured regions) and SCFG are used to capture the long term relations between nucleotides of the arms (structured regions). Given annotated public databases, the HMM and SCFG models are learned by means of automatic inductive learning methods. Two SCFG learning methods have been explored. Both of them take advantage of the structural information associated with the training sequences: one of them is based on a stochastic version of the Sakakibara algorithm and the other one is based on a Corpus based algorithm. A final model is then obtained by merging of the HMM of the nonstructured regions and the SCFG of the structured regions. Finally, the performed experiments on the tRNA sequence corpus and the non-tRNA sequence corpus give significant results. Comparative experiments with another published method are also presented., We would like to thank Diego Linares and Joan Andreu Sanchez for answering all our questions about SCFG, as well as Satoshi Sekine for his evaluation software. We would also like to thank the Ministerio de Sanidad y Consumo of Spain for the grants to the INBIOMED consortium.

A classical problem in inferring automata from data is to find the smallest compatible automaton, i.e. the smallest automaton accepting all examples and rejecting all counter-examples. We are interested in Non-deterministic Finite Automata (NFA) inference which is better suited to Occam's razor optimization principle than Deterministic Finite Automata (DFA). We revisit the existing results on the search space in the state-merging framework, focusing on nondeterminism. We introduce unambiguous automata (UFA) inference, an intermediate between the difficult NFA inference framework and the weaker DFA inference framework. The UFA search space, though containing nondeterministic automata, shares many properties with the DFA search space. Our conclusion is that the search spaces of UFA and DFA are lattices when using adequate operators.