Fonction dite Sigmoid
L'application d'algorithmes à base de "fourmis" dans le cadre du TALN permet d'appréhender un certain nombre de difficultés lors des différentes phases d'analyse d'un texte. En particulier, l'utilisation conjointe des vecteurs conceptuels offre de perspectives interessantes en ce qui concerne les tâches suivantes :
Une analyse morpho-syntaxique fourni un arbre pour le segment textuel considéré. Il s'agit d'un arbre de constituants, c'est-à-dire un arbre où il est possible de reconstituer le texte en parcourant les mots des feuilles. Les feuilles de l'arbres sont donc, les termes du textes. A chaque sens d'un terme, on associe une fourmillière dont l'objectif (implicite) est d'imposer son vecteur conceptuel sur l'ensemble de l'arbre d'analyse (et en particulier à sa racine). Une fourmillière va d'une part, entrer en conflit avec des fourmillières conccurentes (les autres sens du même terme) et d'autre part, trouver un soutien (involontaire) dans les fourmillières associées aux autres termes. Ce soutien est proportionnel à la similarité entre les deux fourmillères (deux fourmillière que se ressemblent se soutiennent mutuellement plus fortement que deux fourmillières différentes). Par l'intermédiaire de leurs fourmis, les fourmillières essaye (1) de maintenir leur activation à un niveau aussi élevé que possible, (2) de construire et de conserver des "ponts" activateurs et/ou inhibiteurs avec d'autres fourmillères. L'ensemble du processus se fait sur la base de transfert d'énergie dont la quantité globale est constante (et finie).
Quelques notions et notations de base :
Pour une introduction générale aux vecteurs conceptuels, on peut se référer aux articles récents disponible à http://www.lirmm.fr/~lafourca/ML-biblio/lafourcade-publications.html.
On note sim(A,B) la similarité entre deux vecteurs A et B. Deux vecteurs sont identiques si leur similarité est égale à 1, et orthogonaux pour 0. La similarité est le produit scalire des deux vecteurs divisé par le produit de leur norme. La distance agulaire de deux vecteurs est arccos(sim(A,B)).
La fonctions Sigmo est definie comme :
Sigmo(x) = (+ (/-2 (atan val) *pi*) 0.5)
Cela correspond à artangente resserrée sur un intervale 0,1 . Par exemple :
Sigmo(0) = 1/2
Sigmo (1) = 0.75
Sigmo (2) = 0.852
Sigmo (-1) = 0.25
Sigmo (-2) = 0.147.La fonction est croissante, continue.
Fonction dite Sigmoid
Voici un exemple d'arbre d'analyse syntaxique. A l'url http://www.lirmm.fr/~chauche/ExempleAnlMem.html , il est possible d'obtenir de tels arbres à partir de textes rentrés en paramètres.
Arbre d'analyse morpho-syntaxique pour le phrase L'avocat est véreux.
Les noeuds de l'arbre d'analyse contiennent des informations morpholigique et syntaxiques.
En plus d'information lingusitique, un noeud de l'arbre d'analyse a les propriétés suivantes :
On distingue donc les nœuds internes de l'arbre et les fourmillières. Tout noeud dispose d'un niveau d'énergie, cependant pour les noeuds internes ce niveau d'énergie sera maintenu >= 0 (il peut être <= 0 pour les fourmillières).
- Eliminer les fourmis trop vieilles ;
- Pour chaque fourmillière, soliciter la production d'une fourmi (une fourmi peut ou non voir le jour, de façon probaliste) ;
- Pour chaque arc, diminuer le taux de phéromone (évaporation des traces) ;
- Pour chaque fourmi : déterminer son type et la déplacer ;
- Calculer les conséquences du déplacement des fourmis (sur l'activation des arcs et l'énergie des nœuds) ;
D'une façon informelle, on peut résumer le déplacement d'un fourmi comme suit. Une fourmi qui vient de naître (cad produite par sa fourmillière) par à la recherche de nourriture. Elle est attirée par les nœud qui porte beaucoup d'énergie. Elle ramasse autant d'énergie qu'elle peut en porter (et de ce qui est disponible) et se promène ainsi sur le graphe. Au fur et et à mesure, elle transporte de plus en plus de nourriture et la probabilité de souhaiter rentrer à la fourmillière augmente. Lorsqu'elle vent rentrer, elle se deplace en suivant (statistiquement) les chemins qui contiennent sa phéromone, et reoturne ainsi à sa froummillière où elle dépose son chargement. Si elle rencontre une autre fourmillière (non concurrent) elle dépose également une petite partie de son chargement.
Les fourmis se déplacent de façon pseudo-aléatoire sur l'arbre d'analyse. Dans certaines conditions, elle peuvent construire des ponts (ou court-circuits) entre certains nœuds de l'arbre (qui devient alors un graphe).
Une fourmi dispose de plusieurs attributs:
A chaque instant, une fourmi se trouve sur un noeud k. Si cette fourmi vient d'être crée par sa forumillière elle se trouve sur cette fourmillière. Il peut y avoir un nombre quelconque de fourmis sur un nœud. Les fourmis n'intéragissent pas directement entre elles. A chaque tour, chaque fourmi doit se déplacer, et les destinations possibles sont les nœuds accessibles selon la géométrie de l'arbre.
Si une fourmi se trouve sur un nœud tel que linkable(node) = vrai elle peut toujours rallier sa propre fourmillière en créant un pont, s'il n'existe pas déjà.
Lorsqu'une fourmi se retrouve sur un nœud, plusieurs situations se produisent selon le type de ce nœud. En particulier, on distingue quatre types de nœuds :
On notera les quatre cas comme les quatre valeurs possible de la fonction Status(ant, node).
Les comportements sont les suivants :
(1) Status(ant, node)= Home. Lorsqu'une fourmi arrive à Home (1), elle restitue l'ensemble de son énergie à Home. Elle repartira avec une énergie 0. (On veillera ici à ne pas confondre l'energie et la durée de vie).
(2) Status(ant, node)= Ennemy. Si elle arrive sur une fourmillière concurrente (cas 2), elle lui vole une quantité d'énergie egale à (1-sim(Ant, Enemy)). On a donc les variations suivantes :
E(node) = E(node) - min (MaxE(ant)-E(ant) , (1-sim(V(Ant), V(node))))
E(ant) = E(ant) + min (MaxE(ant)-E(ant) , (1-sim(V(Ant), V(node))))Plus une fourmillière ennemie est différente, plus la quantité d'énergie dérobée tend vers 1. Cependant, la fourmis ne peut jamais dépasser sa charge maximale.
(3) Status(ant, node)= Nest. La fourmi qui arrive sur une autre fourmillière (cas 3) donne une partie de son énergie dans la proportion sim(V(node),V(ant)).
E(node) = E(node) + sim(V(node), V(ant))* E(ant)
E(ant) = E(ant) - sim(V(node), V(ant))* E(ant).(4) Status(ant, node)= Intern. La fourmi qui arrive sur un nœud interne de l'arbre (cas 4) prend le plus d'énergie possible de façon à maximiser l'énergie qu'elle porte :
E(ant) = E(ant) + min(MaxE(ant) - E(ant), E(node))
E(node) = E(node) - min(MaxE(ant) - E(ant), E(node))
On remarquera que si un nœud interne node n'a plus d'énergie (E(node)=0), on ne peut lui en soustraire d'avantage. Par contre, on peut toujours soustraire de l'énergie à une fourmillière, même si celle-ci a déjà une énergie nulle (elle deviendra alors négative).
Avant de se déplacer, une fourmi va évaluer les nœuds qui sont des destinations possibles du nœud où elle se trouve. On note Val(node) cette valeur. En toute généralité, la probabilité qu'une fourmi a de prendre une destination k (un arc k menant au nœud k) est :
pa(k)= Val(k)/somme[i=1;n]Val(i))
On considère deux types de fourmis:
Une fourmi E évalue les destinations possibles selon la fonction suivante. Pour un nœud destination node, la valuation de ce noeud est :
Val(node) = Sigmo(E(node))
Une fourmi R évalue les destinations possibles selon la fonction suivante. Pour un nœud destination node, la valuation de ce noeud est :
Val(node) = sim(V(ant), V(node))
De plus, et de façon tout à fait générale, on considérera quelques heuristiques de déplacement. Par exemple, on donnera un très fort malus à une destination qui est la précédente (Val(node) = Val(node)/10) (sauf si la fourmi vient de changer de type). Il s'agit d'encourager une fourmi à ne pas toujours préférer sa propre fourmillière à une autre nœud, et à parcourir l'arbre selon des cycles.
La fourmi peut porter une charge MaxE. Avant chaque déplacement, la fourmi décide ou non de chnager son type en fonction de ce qu'elle porte. La probabilité d'être du type R (de retourner à la maison) est définie comme :
p(ant,R)= E/MaxE
Par exemple, si la fourmi porte une charge relative de 1/2 alors elle à 50% de décider de rentrer à la maison. Si une fourmi porte déjà sa charge maximale, elle à alors 100% de chance de décider de rentrer.
Lors de chaque déplacement, la fourmi dépose sur l'arc traversé une petite quantité de phéromone (delta = 0.1). Elle laisse une sorte de trace. Cependant, si une fourmi emprunte un arc dont une des extrémités est un nœud concurrent alors, elle baisse l'activation de cet arc. dans ce cas, on note l'arc k entre node1 et node 2 : k(node1, node2). Les arcs ne sont pas orientés.
k(node, ennemy(ant)) : Act(k) = Act(k) - delta
k(node1, node2) : Act(k) = Act(k) + delta
Le niveau d'activation d'une arc ayant une influence sur le déplacement (voir Stygmergie), l'idée est qu'une fourmi ne souhaite pas qu'un arc lié à une fourmillière concurrente soit fréquenté.
A chaque cycle de la simulation, la quantité de phéromones sur chaque arc diminue (évaporation) selon un coefficient ro. Pour un arc k, la nouvelle quantité de phéromone diminue :
Act(k) = (1 - ro) * Act(k)
L'activation d'un arc peut être positive ou négative selon l'activité des fourmis. Cependant, avec le temps et si aucune fourmi ne repasse sur l'arc, l'activation a naturellement tendance à converger vers 0.
Dans ce qui précède sur la description du processus de deplacement d'une fourmi, les activations des arcs ne joue pas de rôle. L'ensemble du processus est donc analogue à un algorithme glouton. La terme de stygmergy correspond au phénomène de communication indirecte et de renforcement induit par les phéromones déposées par les fourmis. Les phéromones sont ici simulées par le niveau d'activation des arcs.
On rappelle qu'à chaque passage sur un arc, une fourmi augmente l'activation de ce dernier d'une petite constante (delta = 0.1). La probabilité de choisir l'arc k à partir de node (ayant les arcs 1 … k … n) est égale :
pb(k)=sigmo(Act(k))/somme[i=1;n](sigmo(Act(i)))
Toutses choses étant égales par ailleurs, les fourmis ont tendance à préférer les zones de fort passage.
De façon globale, une fourmi évalue donc une destination (cad un arc k et le nœud destination k) :
p(ant,k)= pa(k)* pb(k)/somme[i=1;n](pa(i)* pb(i))
En toute generalité (cf Dorigo), on peut affecter des pondérations A et B aux termes pa et pb:
p(ant,k)= pa(k)A* pb(k)B/somme[i=1;n](pa(i)A* pb(i)B)
en pratique, on obtient de bons résultats en fixant A = B = 1.
Lors de son déplacement sur les nœuds interne de l'arbre, une fourmi propage son vecteur conceptuel. Le vecteur porté par un nœued est modifié lors du passage d'une fourmi :
V(n) = V(n) + fs * alpha * V(ant)
alpha est une petite constante non nulle (alpha = 0.05, soit 5 %) et fs = 1 par défaut. Au debut de la simulation les nœuds internes n'ont pas de vecteur. La facteur alph peut être diminué ou agmenté selon la fonction syntaxique du nœud d'ou provient la fourmi. En particulier, si la nœud précedent est un gouverneur (GOV) alors fs = 2 . Les fourmillières sont les seuls nœuds dont le vecteur ne peut pas être modifié par le passage d'autres fourmis (ce sont des points fixes).
Le déplacement des fourmis implique une propagation des vecteurs et participe à l'effet stygmergétique (traces). Cependant, l'effet est ici rationnel pour les fourmis car elle ont tendance, selon leur type, à choisir selon leur destination selon les vecteurs porté par les nœuds.
Ce phénomène permet aux fourmis de revenir à leur fourmillière, ou éventuellement à se tromper et à se diriger vers des fourmillière amies.
Une fourmillière dispose :
La production d'une fourmi est pseudo-aléatoire et est gourvernée par une fonction (dite Sigmo) de l'activation. La propabilité de produire une fourmi pour un nœud k est :
pf(k) = Sigmo(E(k))
Par exemple, une fourmillière à activation 0, a une chance sur deux de produire une fourmi. Une fourmillière sera dite inhibé sur E << 0, et activé si E >> 0 .
Le coût d'une fourmi est constant (AntCost) et baisse l'énergie du nœud node de AntCost :
E(node) = E(node) - AntCost
Le coût est empiriquement fixé (AntCost = 0.1) .
La discussion qui suit présente la dynamique globale du système, qui est induite par les régles de comportement présentées ci-dessus.
L'énergie est la facteur de contrôle des population de fourmis. En effet, contrairement aux applications classques des algorithmes fourmis à certains problèmes de combinatoire (TSP, etc) nous somme dans une situation ou plusieurs populations de fourmis se font concurrence ou coopèrent. D'une façon générale, plus une fourimmilère obtient de l'énergie plus sa population de fourmis va s'accroître. Et en retour, son niveau d'énergie pourra être maintenu relativement élevé. Cependant, le système ne peut diverger, la quantité globale d'énergie disponible étant finie et constante.
D'ou provient l'énergie que reccupère une fourmillière ? Elle provient (1) de ces propres fourmis, mais aussi (2) des fourmis altruistes des autres fourmillière non-concurrentes. Ne considérons que se qui se passe avec ses propres fourmis.
à faire
L'approche précedente (dites dure) aboutit à un système dont le dynamique est violente pour les fourmis minoritaires. Certaines modifications relachent les contraintes pesant sur les fourmis et les fourmillières. Cette approche est qualifiée de douce.
Pour la phrase il est avocat à la cour
Les sens avocat.1 correspond au sens défenseur de justice et avocat .2 correspond au sens de fruit. L'acception cour.1 correspond à cour de bâtiment, et cour.2 correspond à cour de justice.
Pour la phrase L'avocat est véreux
Les sens avocat.1 correspond au sens défenseur de justice et avocat .2 correspond au sens de fruit. L'acception véreux.1 correspond à corrumpu, et véreux.2 correspond à plein de vers.
Même phrase (l'avocat est véreux), avec une approche douce.
L'avocat est véreux, le prénue a été condamné. Approche douce.
Drogoul
Ferber