Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

See discussions, stats, and author profiles for this publication at: https://ww

See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/220760997 Apprentissage des schémas de propagation dans les multi-graphes. Conference Paper · January 2011 Source: DBLP CITATIONS 0 READS 81 3 authors, including: Some of the authors of this publication are also working on these related projects: Budget learning View project Ludovic Denoyer Sorbonne Université 156 PUBLICATIONS 2,167 CITATIONS SEE PROFILE All content following this page was uploaded by Ludovic Denoyer on 04 June 2014. The user has requested enhancement of the downloaded file. Apprentissage des schémas de propagation dans les multi-graphes Yann Jacob — Ludovic Denoyer — Patrick Gallinari Université Pierre et Marie Curie - LIP6 Boîte courrier 169 4 place Jussieu 75252 PARIS cedex 05 RÉSUMÉ. Nous considérons le problème de l’étiquetage de noeuds dans un multi-graphe - ou graphe multi-relationnel - dans lequel les noeuds peuvent être connectés simultanément par dif- férents types de relations. De nombreux problèmes se modélisent ainsi, comme par exemple les réseaux sociaux ou bien les bases de données bibliographiques. Les relations peuvent être expli- cites (par exemple amitié dans un réseau social) ou bien implicite (par exemple des similarités de contenu calculées sur les données). Nous proposons ici un algorithme d’apprentissage per- mettant d’exploiter l’information multi-relationnelle pour la tâche d’étiquetage automatique. Cette méthode est capable d’apprendre à combiner de manière optimale l’inﬂuence des dif- férents types de relations sur la propagation des étiquettes entre les noeuds du graphe. Nous décrivons des expériences sur quatre corpus qui montrent la capacité du modèle à tirer parti de l’information multi-relationnelle pour des tâches d’étiquetage complexes. ABSTRACT. We consider the problem of labeling nodes in a multi-graph where the nodes may be connected with different types of relations. This type of problem occurs in many situations like for example the analysis of social networks or bibliographic data. Relations may be provided (e.g. friends) or computed (e.g. similarity). We propose a new learning algorithm for exploiting the rich multi-relational information in the labeling task. This method is able to optimally learn combining the inﬂuence of different relation types. It is one of the very ﬁrst algorithms able to handle multi-graph information for this classiﬁcation task. We describe experiments on four datasets which show the model ability to deal with complex relationships and to take beneﬁt of multi-relational information for complex labeling problems. MOTS-CLÉS : apprentissage, classiﬁcation automatique, graphe multi-relationnel, réseaux so- ciaux KEYWORDS: machine learning, automatic classﬁcation, multi-relational graph,social net- work,web Jacob, Denoyer, Gallinari 1. Introduction Nous considérons l’analyse de données relationnelles où différents objets sont liés par des relations comme c’est le cas pour des pages Web ou des réseaux sociaux. Ce type de donnée est souvent décrit en utilisant un formalisme de graphe dans lequel les noeuds correspondent aux données et les arcs représentent les relations. L’accès à des masses de données relationnelles de plus en plus complexes et importantes dans beau- coup d’applications a motivé le développement de nouveaux paradigmes et modèles dans différentes communautés de recherche comme la communauté de l’apprentissage automatique ou bien celle de la fouille de données. Parmi les nombreux problèmes émergents, le calcul des scores des noeuds dans un graphe est un problème générique qui survient dans différents applications. Ce score peut correspondre à un indicateur de classe, un rang ou une valeur réelle indiquant l’importance ou la pertinence d’un noeud donné. Certains modèles de calcul de scores sont récemment apparus dans la lit- térature de l’apprentissage automatique avec deux objectifs principaux : la classiﬁca- tion et l’ordonnancement d’objets relationnels. Une idée populaire a été l’exploitation des relations en utilisant le laplacien du graphe pour favoriser localement la régularité des scores de noeuds. Cette intuition, valide dans beaucoup de situations, stipule que les noeuds qui partagent une relation forte doivent avoir un comportement similaire. Ce modèle a été dans un premier temps introduit dans le contexte de l’apprentissage semi-supervisé (Zhou et al., 2005, Zhou et al., 2004, Belkin et al., 2006) où les rela- tions représentent des similarités entre données et l’hypothèse de régularité est utilisée pour propager les étiquettes des noeuds étiquetés vers les noeuds non étiquetés. Il a été étendu pour l’ordonnancement (Agarwal, 2006) et utilisé dans différents contextes comme la détection de spam (Abernethy et al., 2008) ou la recherche d’informations sur internet (Qin et al., 2008) par exemple. Nous considérons ici le problème de scoring des noeuds dans un graphe et nous proposons deux extensions à des méthodes existantes : – Tout d’abord, nous considérons des données multi-relationnelles où les objets partagent différents types de relations. Les travaux précédents se concentrent princi- palement sur les données mono-relationnelles où tous les arcs représentent le même type de relation tandis que beaucoup d’applications concernent des données multi- relationnelles comme les données sociales - avec des relations comme ami, ennemi, suiveur - ou dans des domaines plus classiques comme les citations, co-auteurs ou similarité du contenu dans des données bibliographiques. – La seconde extension est d’apprendre le poids des relations pour adapter la force ou l’importance de ces poids aux données et à la tâche considérée. Ici encore, toutes les méthodes existantes se sont en deux étapes : premièrement, la force des relations entre deux noeuds est calculée manuellement - une pratique courante consistant à utiliser une fonction de similarité classique entre le contenu des noeuds - puis les scores sont propagés en utilisant ces poids prédéﬁnis. Ces poids représentent une connaissance a priori et ne sont pas directement corrélés à la tâche à résoudre. Dans notre contexte, apprendre les poids permet de donner plus d’importance à certains types de relations ou aux relations les plus signiﬁcatives et donc de découvrir automatiquement comment Propagation dans les multi-graphes Figure 1. Etiquetage transductif d’un graphe multi-relationnel l’information se propage dans les réseaux. Le modèle proposé est de plus capable de gérer aussi bien le contenu des noeuds que les nombreux types de relations, là où les nombreux modèles existants se limitent à faire de la propagation d’étiquette sur la structure du graphe, sans prise en compte de contenu. Dans la section 2 nous introduisons le modèle de régularisation classique pour ap- prendre les scores de noeuds dans un graphe, dans la section 3, nous présentons notre modèle ainsi que différentes extensions possibles, dans la section 4 nous donnons les résultats d’expériences effectuées sur quatre 4 jeux de données issus de différents do- maines applicatifs. 2. Régularisation dans les graphes mono-relationnels 2.1. Description informelle Un des premiers modèles d’apprentissage dans les graphes qui soit capable de gé- rer aussi bien le contenu que les relations est celui proposé dans (Abernethy et al., 2008) pour l’étiquetage transductif . Il est présenté ici car, même si c’est un modèle mono-relationnel uniquement, il constitue une brique de base du modèle proposé dans cet article et servira de point de départ à nos extensions. Dans le cadre de l’appren- tissage transductif, nous considérons un graphe partiellement étiquetés, c’est-à-dire pour lequel nous connaissons les étiquettes de certains noeuds mais pas de tous. Le but du modèle est alors d’être capable de généraliser l’étiquetage partiel à l’ensemble Jacob, Denoyer, Gallinari des noeuds du réseau en utilisant à la fois l’information disponible depuis les noeuds étiquetés et non étiquetés. Basiquement, ce type d’algorithme opère en deux étapes : – La première étape consiste à entraîner une machine d’apprentissage classique sur le contenu des noeuds étiquetés. Cette machine d’apprentissage sur le contenu seul peut être n’importe quel type de classiﬁeur, comme un perceptron, un SVM ou un modèle génératif. Une fois entrainé sur les noeuds étiquetés, elle sera utilisée pour calculer un score initial, dénoté ¯ yi, pour tous les noeuds non étiquetés du graphe basé sur le contenu des noeuds uniquement. – La seconde étape consiste à propager ces scores le long des arcs du graphe. La propagation est faite à travers un terme de régularisation qui pénalise le fait que deux noeuds connectés n’aient pas des scores proches. A la ﬁn du processus, le score ﬁnal obtenu pour chaque noeud est alors le résultat d’un compromis entre son score de contenu seul et le score de ses voisins. Dans un premier temps, nous déﬁnissons formellement ces deux étapes puis nous montrons pourquoi cet algorithme ne convient pas aux multi-graphes. Nous présentons ensuite dans la section 3 un modèle capable d’apprendre comment propager les étiquettes sur différents types de relations. 2.2. Notations Soit un multi-graphe G = (V, E) déﬁni par : – Un ensemble de N noeuds V = (v1, ...vN). Nous considérons que les noeuds ont une information de contenu (texte, image, ...) décrite par un vecteur. Par la suite, vk dénotera à la fois le noeud et son vecteur associé i.e. vk ∈Rd où d est la dimension du vecteur. Un tel vecteur peut être par exemple l’histogramme d’une image ou la description fréquentielle des mots d’un document. – Un ensemble de R arcs E = R ! k=1 E(k) où E(k) est l’ensemble des arcs de type k entre les éléments de V . E peut être vu comme un tenseur tri-dimensionnel E = uploads/Ingenierie_Lourd/ apprentissage-des-schemas-de-propagation-dans-les.pdf