Date/heure
Date(s) - 6 mars 2015

Catégories Pas de Catégories

$Title : Hypernode Graphs For Learning From Binary Relations Between Sets of Objects\n\nAbstract (english) : Graphs are commonly used as a powerful abstract model to represent complex relationships between individuals. For (classical) graphs, pairwise relations are modeled by edges between vertices. This is for instance the case for social networks with the friendship relation, or for computer networks with the connection relation.\n\nThe hypergraph formalism has been introduced in the 1970s for modeling complex problems where relationships are no longer binary, which is when they involve more than two individuals. Hypergraphs have been used for instance in bioinformatics, computer vision or natural language processing. But, graphs and hypergraphs are limited when it comes to consider relationships between sets of individual objects. A typical example is the case of multiplayer games where a game can be viewed as an established relationship between two (or more) teams of multiple players. Other examples include relationships between groups in social networks or between clusters in computer networks. For these problems, considering both the group level and the individual level is a requisite.\n\nWe introduce and study a new data structure called hypernode graph specifically designed to handle this type of higher-order relations.\n\nWe show that we can extend the notion of graph Laplacian and graph Kernel to this new class of objects. This extension of the spectral learning framework is fully consistent with the graph case and allows us to design efficient learning algorithms on top of our new data structure. We also show that our newly defined Laplacians are strictly more expressive than graph Laplacians. Note that this property does not hold for instance in the case of hypergraphs. We use our new formalism in order to design a new skill rating algorithm for multiplayers games. We estimate the relevance of the results using a predictive scheme (we predict new games using the skills estimated in the past). Experimental results have shown that we obtain very competitive results compared to specialized algorithms.\n\nWe also study in detail some important properties of the undirected hypergraphs and bring into focus some fundamental links with the theory of signed graphs.\n\nAbstract (français) : Les graphes sont communément utilisés en tant que modèle abstrait permettant de représenter des relations complexes qui impliquent des couples d’individus. Chaque relation s’y voit associée à une arrête qui relie deux sommets du graphe. On peut par exemple citer le cas des graphes construits à partir de réseaux sociaux et où les arrêtes représentent des relations d’amitié entre utilisateurs ou le cas des graphes issus de réseaux informatiques où chaque arrête décrit une connexion entre deux serveurs.\n\nAu cours des années 1970, la notion d’hypergraphe a été introduite afin de modéliser des relations plus complexes, impliquant potentiellement plus de deux individus. Ce nouveau formalisme a donné lieu à de nombreuses applications dans des domaines aussi divers que la bio-informatique, la vision par ordinateur ou encore le traitement du langage naturel. Cependant, et à l’instar des graphes, ce nouveau modèle se montre limité dès lors que l’on considère des relations entre ensembles d’individus. A titre d’illustration, on peut citer le cas des jeux compétitifs à plusieurs joueurs : chaque partie peut en effet être considérée comme une relation liant (au minimum) deux équipes de joueurs (victoire, défaite, égalité). Des relations similaires peuvent intervenir dans le cadre de réseaux sociaux (relations entre groupes d’individus) ou dans le cadre de réseaux informatiques (relations entre clusters). Dans le cadre des problèmes listés ci-dessus, il est impératif de prendre en considération\nà la fois les individus et les ensembles.\n\nDans le cadre de ce travail, nous introduisons un nouveau modèle appelé graphe d’hypernoeuds (hypernode graph) permettant de représenter spécifiquement des relations binaires entre ensembles d’individus.\n\nNous proposons également une extension des notions de Laplacien de graphe et de noyau de graphe pour cette nouvelle classe d’objets. Nous montrons que cette extension est cohérente avec la théorie spectrale définie dans le cadre des graphes non dirigés. De plus, nous montrons que nos Laplaciens sont strictement plus expressifs que les Laplaciens de graphe. On notera que cette propriété est spécifique à notre classe d’objets et n’est pas vérifiée par exemple dans le cas des Laplaciens d’hypergraphe.\n\nA l’aide de ces nouveaux outils, nous sommes capables de définir des algorithmes d’apprentissage efficaces pour les graphes d’hypernoeuds. Sur ces bases, nous proposons un nouvel algorithme permettant d’évaluer les niveaux de compétence individuels dans des jeux à plusieurs joueurs (skill rating). Nous évaluons la qualité de nos résultats via un schéma prédictif (nous prédisons le résultat de nouveaux matchs à l’aide des valeurs précédemment calculées). Les résultats expérimentaux montrent que nous sommes en mesure d’obtenir des résultats compétitifs vis-à-vis d’algorithmes spécialisés.\n\nNous étudions en détail les principales propriétés des graphes d’hypernoeuds et mettons en évidence des relations fondamentales avec les graphes signés.[$