De l'importance de la fonction de poids dans le noyau des sous-arbres

International audienceKernel methods are one of the main techniques used for learning on tree structured data. Among them, we interest ourselves to the subtree kernel, which has the combinatorial advantage of being able to enumerate all objects used in the estimation of the similarity between trees. We introduce concepts of DAG reduction and DAG recompression, which lead us to a performant algorithm for computing the kernel. The ability of dealing with a highly compressed database allows us to introduce a new weight function, which manages to capture information in data where weights in the literature do not.Les méthodes à noyaux sont une des approches permettant l’apprentissage à partir de données arborescentes. Parmi elles, nous nous intéressons au noyau des sous- arbres, qui présente l’avantage combinatoire de pouvoir énumérer l’ensemble des objets utilisés pour estimer la similitude entre deux arbres. Nous introduisons le concept de réduction DAG, puis de recompression DAG, qui mènent à un algorithme efficace pour calculer le noyau. La possibilité d’aborder une base de données sous un format fortement compressé nous permet d’introduire une nouvelle fonction de poids, qui parvient à capturer de l’information dans des données où les poids proposés dans la littérature n’y arrivent pas