Abstract
From LRDE
P
Quickref est une application common lisp permettant de générer automatiquement et par introspection une documentation technique des bibliothéques disponibles dans Quicklisp. +
La bibliothèque Vaucanson permet de manipuler des automates et des transducteurs. Le parser d'expression rationnelles doit donc lui aussi traiter ces différentes structures. Malheureusement l'ancien parser ne permettait pas de lire des expressions rationnelles décrivant des transducteurs ou même des automates à poids autres que des nombres. Le nouveau parser permet de lire des expressions rationnelles contenant des poids de toutes sortes et des alphabets définis sur des produits de monoïdes. Ces différentes améliorations permettent d'interpréter des expressions rationnelles complexes représentant entre autres des transducteurs. +
FIXME +
FIXME +
Nowadays, model-checking tools suffer from a scalling problem, due to their memory consuption. Partial order reduction is one way allowing to notably reduce it, by computing only needed data on-the-fly. There are many state-of-the-art algorithms, and this method is used in many softwares (such as SPIN or LTSmin). We are going to talk about the implementation of it in the Spot libraryand then the optimisation. The results show a great decrease of the memory consuption, which implies some gain in all subsequent steps. +
Spot is a model checking library implementing an automaton based approach. For the moment to verify a property Spot's algorithm may explore the whole state space of the system without any reduction. They thus suffer from the combinatorial explosion in the model's size. One way to tackle this problem is by using Partial order reduction methods. The idea is to ignore equivalent behaviour of the system with respect to a given property. Hence, reducing the size of the generated state space while preserving the whole behaviour. The goal of this work is to assess how these methods can be implemented in Spot. +
The present report is the C++ implementation of the algorithm ID described by Dana Angluin and al in Polynomial Identification of omega-Automata. It allows identification, or passive learning, of regular omega-languages and omega-automata, in polynomial time and data. It is a preliminary work to the study of active learning of omega-languages. The code is available at https://gitlab.lrde.epita.fr/cpape/ID +
Prise de décision à l'aide de SVM dans le contexte des systèmes de vérification du loctueur à base d'I-Vector +
La prise de décision dans l'état de l'art des systèmes de vérification du locuteur est basée sur la distance en cosinus. Une approche différente est de considérer une prise de décision basée sur les Séparateur à Vaste Marge (SVM). La technique des SVMs a été largement exploitée dans la reconnaissance de formes et la prise de décision mais également en association avec les GMM super-vecteurs (GSV) en reconnaissance du locuteur. Cependant, l'idée d'utiliser les SVMs dans l'espace des i-vectors pour la reconnaissance du locuteur n'a pas été le sujet d'une étude approfondie. Nous étudierons les différentes fonctions kernels et comment c cela peut être utilisé dans la vérification du locuteur. Nous explorerons comment prendre en compte les variabilités de canal et de locuteur et dans l'espace des caractéristiques. Nous expérimenterons avec les données de la base NIST-SRE 2010. +
Spot, a library for transition based Spot, a library for transition-based '"`UNIQ--math-00000005-QINU`"'-automata manipulation, provides a method to determinize Büchi automata which can produce quasi-parity automata. We introduce three tools to manipulate these automata which are reducing the number of sets in the acceptance condition, changing the style of the parity acceptance expression and colorizing an automaton. Olivier Carton introduced a method to construct the product of state-based parity automata which keeps the parity acceptance. We adapt this method to make it work with transition-based automata and we present optimizations of this product. Our work gives a better support of automata with parity acceptance and may also lead to further optimizations of the determinization of Büchi automata. +
Spot, une bibliothèque manipulant les ω-automates basés sur les transitions, offre une méthode qui construit des automates à parité déterministes à partir d'automates de Büchi non-déterministes. Nous présentons trois outils qui manipulent les automates avec une condition d'acceptation à parité. Ces outils sont la réduction du nombre d'ensembles dans la condition d'acceptation, la modification du style de la condition d'acceptation et la coloration d'un automate. Olivier Carton a présenté une méthode pour constuire le produit d'automates à parité basés sur les étatsqui conserve la parité. Nous adaptons cette méthode afin qu'elle fonctionne également avec des automates basés sur les transitions, puis nous présentons des optimisations de ce produit. Notre travail offre un meilleur support des automates avec une conditions d'acceptation à parité. Il pourrait également permettre d'optimiser la déterminisation d'automates de Büchi. +
VAUCANSON is a finite state machine manipulation platform for automata and transducers. Usage highlighted the overly complex interface for the automaton manipulation. Therefore, work was done during the past years to improve it, leading to the introduction of the concept of automaton "kinds". Two different versions of the platform are currently under development. VAUCANSON 1.4, which will be a more complete and stable version of the work done before the interface modification. Idea is to work toward releasing a final version of VAUCANSON 1.X, allowing us to focus on VAUCANSON 2.0, which is currently incomplete, due to the deep changes that "kinds" brought to the library. This report will explain a new feature of VAUCANSON 1.4the Z/nZ semirings, and presents what has been and will be done to get VAUCANSON 2.0 to work. +
Projection non-linéaire pour l'attribution de score selon la distance en cosinus dans le contexte des systèmes de vérification du locuteur à base d'i-vectors. +
À l'heure actuelle, l'espace des i-vectors est considéré comme le modèle standard pour la représentation d'information vocale dans le contexte des systèmes de vérification du locuteur. De récents progrès ont pu être accomplis grâce à ce modèle qui permet de représenter les données dans un nombre réduit de dimensions et également grâce à l'utilisation de nouvelles méthodes de classification comme l'Analyse Discriminante Linéaire Probabiliste (PLDA) ou encore le classifieur à base de distance cosinus (CD). L'idée du scoring avec le CD est de projetter les caractéristiques évoluant dans un nombre de dimensions élevé sur une hypersphère de dimension plus faible. Aujourd'hui, tous les sytèmes utilisent d'abord une Analyse Discriminante Linéaire (LDA) classique afin de trouver la meilleure projection dans l'espace de dimension inférieure avant de projetter sur l'hypersphère. Le but de ce travail est de proposer une projection non linéaire directement de l'espace des i-vectors vers une hypersphère en minimisant la corrélation inter-classe tout en maximisant la corrélation intra-classe. Il sera question de comparer les résultats obtenus avec d'autres solutions comme : le CD classique, le PLDA et l'approximation de mesure de distance avec le perceptron multicouche et les machines de Bolzmann. +
Getting both high performance and genericity at the same time is one of the major research field at the LRDE. Milena, the Olena platform library, faces that issue in the context of image processing. Furthermore Milena has for extra objective to remain simple to use for a practitioner. A solution, experimented since several years, is based on properties. Properties are a set of features statically bound to a type. For instance, image types in Milena have a property named speed that gives information at compile time about the value access time. In this seminar, we focus on the image properties. We detail the definition of those properties and justify them. We show how those properties help in improving efficiency while maintaining genericity. For that, we take as illustration the implementation of low level routines in the library. +
In Vaucanson, Finite State Machines are mathematically defined by an algebraic structure module called Algebra. Considering the algebraic mathematical definitionshowever, the current design is inaccurate: some hierarchical relations are false (for example, the inheritance between semirings and monoids). Moreover, we are unable to add new algebraic structures easily.newline Therefore, in order to give Algebra more granularity in its algebraic concept definitions, it is necessary to rework its current structure by introducing a property based class hierarchy similar to the one presented in SCOOP. Using the mathematical operator and set properties to define algebraic structures, as opposed to a usual class hierarchy, we would be able to specialize algorithms more precisely thanks to structure property verifications, thus increasing Vaucanson's performance and expressiveness. +
Climb is a generic image processing library. A generic algorithm interface often requires several different specialized implementations. Olena, a C++ library, solved this using properties. We present a way to dispatch a function call to the best specialized implementation using properties in a dynamic programming language: Common Lisp. Then, we introduce examples of algorithms and properties used in image processing. +
Property-based genericity is an object-oriented programming paradigm. It allows to model in a generic way some systems which are hard to represent using classical object-oriented programming. It was introduced by the C++-oriented SCOOP paradigm used in Olena, an image processing library. The key principle of this paradigm is the description of classes in terms of a list of the properties its instances must have, instead of their inheritance trees.par We will present this paradigm and show that it can be extended to other languages than C++ and other fields than image processing. We will then introduce an example implementation of property-based genericity in Common Lisp, which will take advantage of its dynamic capabilities and its extensibility. +
Q
In this report, we show how the quotient operator has been implemented in Vcsn, a generic and perfomant automata manipulation library. After defining the left and right quotient over rational series, we explain the algorithm implemented in Vcsn to compute the quotient of two automata. We then explore the consequences of introducing the operator on the expression-side of the library, and particularly on expansions. +
Dans ce rapport, nous montrons comment le quotient a été implémenté dans Vcsn, une bibliothèque générique et performante de manipulation d'automates. Après avoir défini le quotient à gauche et à droite de séries rationnelles, nous expliquons l'algorithme implémenté dans Vcsn pour calculer le quotient de deux automates. Nous explorons ensuite les conséquences de l'introduction du quotient du côté des expressions dans la bibliothèque, et plus particulièrement sur les expansions. +