thesis

Noyaux rationnels et automates d'arbres

Defense date:

Jan. 1, 2015

Edit

Institution:

Rouen

Disciplines:

Computer sciences

Authors:

Directors:

Abstract EN:

In the case of words, a general scheme for computing rational kernels has been proposed. It is based on a general algorithm for composition of weighted transducers and a general algorithm computing smallest distance. Our goal is to generalize this computation scheme to the case of trees using tree automata. To do this we have established the following two main objectives : On the one hand,define tree automata for computing subtree kernel, subsettree kernel and tree factor kernel. On the other hand, from a regular tree expression, build a tree automaton to compute the various rational tree kernels described by regular tree expressions using the following scheme over two tree languages L1 and L2 : KE(L1;L2) = (AL1 \ AE \ AL1). We explored and proposed efficient algorithms for the conversion of a regular tree expression into tree automata. The first algorithm computes the Follow sets for a regular tree expression E of a size jEj and alphabetic width jjEjj in O(jjEjj jEj) time complexity. The second algorithm computes the equation tree automaton via the k-C-Continuations which is based on the acyclic minimization of Revuz. The algorithm is performed in an O(jQj jEj) time and space complexity, where jQj is the number of states of the produced automaton. Then we developed algorithms for the computation of subtree kernel, subsettree kernel and tree factor kernel. Our approach is based on the representation of all trees of the set S = fs1; : : : ; sng (resp. T = ft1; : : : ; tmg) by a particular weighted tree automaton called Root Weighted Tree Automaton the RWTA AS (resp. AT ) (equivalent to the prefix automaton in the case of words) such that jASj #Pn i=1 jsij = jSj (resp. JAT #Pm j=1 jtj j = jTj) ; then we compute the kernels between the two sets S and T. This amounts to compute the weight of the intersection automaton AS \ AT. We show that the computation of the kernel K(S; T) can be done in O(jASj jAT j) time and space complexity. Keywords: Finite Tree Automata, Rationnal Tree Languages, Regular Tree Expressions, Conversion of Regular Tree Expressions, Rational Kernels, Trees, Rational Tree Kernels.

Abstract FR:

Dans le cas des mots, un schéma général de calcul des noyaux rationnels a été proposé. Il repose sur un algorithme général de composition des transducteurs pondérés et un algorithme général de calcul de plus petite distances. Notre objectif est de généraliser ce schéma de calcul aux cas des arbres en utilisant les automates d’arbres. Pour ce faire, nous avons fixé les deux objectifs principaux suivants : D’une part, définir les automates d’arbres pour le calcul des noyaux des sousarbres, des sous-séquences d’arbres et des facteurs d’arbres. D’autre part, à partir d’une expression rationnelle d’arbres, construire un automate d’arbres pour le calcul des différents noyaux rationnels décrits par des expressions rationnelles d’arbres en utilisant le schéma suivant sur deux langages d’arbres L1 et L2 : KE (L1;L2) = (AL1 \ AE \ AL2). Nous avons exploré et proposé des algorithmes efficaces pour la conversion d’une expression rationnelle d’arbres en automates d’arbres. Le premier algorithme calcule, à partir d’une expression rationnelle d’arbres E de taille jEj et de largeur alphabétique jjEjj, les ensembles Follow en temps O(jjEjj jEj). Le second algorithme calcule l’automate d’arbres des équations via les k-C-Continuations qui est basé sur la minimisation acyclique de Revuz. Cet algorithme calcule l’automate des équations avec une complexité e temps et en espace en O(jQj jEj) où jQj est le nombre d’états de l’automate produit. Ensuite, nous avons conçu des algorithmes pour le calcul des noyaux des sous-arbres, des sous-séquences d’arbres et des facteurs d’arbres. Notre Approche est basée sur la représentation de l’ensemble d’arbres S = fs1; : : : ; sng (resp. T = ft1; : : : ; tmg) par un automate d’arbres pondéré particulier baptisé Root Automate d’Arbres Pondéré, le RAAP AS (resp. AT ) (équivalent à l’automate des préfixes dans le cas des mots) tel que jASj Pn P i=1 jsij = jSj (resp. JAT j # m j=1 jtj j = jTj) ; puis de calculer les noyaux entre les deux ensembles S et T. Ceci revient au calcul du poids de l’automate intersection AS \ AT. Nous montrons que le calcul du noyau K(S; T) peut se faire en temps et en espace O(jASj jAT j).