Introduction à l'IA

Pour pouvoir répondre, l'ordinateur a besoin de :

• TALN (NLP) : Traitement automatique du Langage Naturel
• Représentation des connaissances pour stocker ce qu'il sait
• Raisonnement automatisé : Répondre aux questions
• Apprentissage automatique : pour s'adapteur aux nouvelles circonstances, détecter et extrapoler des tendances
• Vision par ordinateur
• Robotique

Limitation : L'humain n'est qu'un modèle d'intelligence. Pour construire des avions, pas besoin de système qui trompent même les oiseaux

Aux débuts de l'IA, il y a deux objectifs :

• Efficacité computationnelle
• Plausibilité cognitive

=> Hybridation très fertile : Réseaux de neurones artificiels

Les philosophes et les mathématiciens s'intéressent depuis longtemps aux "lois du raisonnement" : la logique. Une notation précise a été développée pour décrire toutes sortes d'énoncé et de relations entre des entités du monde.

Intelligence Artificielle Symbolique : solveurs logiques

Limitations : Toutes les connaissances ne sont pas évidentes à décrire de façon suffisament précise pour un système logique

Tous les programmes font des choses, un agent rationnel peut potentioellement

• Agir de manière autonome
• En percevant son environnement
• De facon à persister sur une longue période
• Obtenir le meilleur résultat possible

Dans l'approche "lois du raisonnement", on cherche à avoir un inférence correcte qui permet une action performante. Parfois, on doit qunad-même prendre une décision sans inférence correcte. Certains comportements rationnels court-circuitent la délibération logique

Un agent perçoit son environnement, réalise des actions, mesure son succès par une mesure de performance et peut posséder une connaissance de son environnement.

• Le degré d'un graphe non dirigé d'un noeud est le nombre d'arêtes qui s'attachent à ce noeud.

Soit \( G = \left(V, E\right) , V = \{ x_1, \dots , x_{n} \} , |E| = m \) , on a :

\[ \sum_{i = 1}^{n}{\operatorname{degré}(x_{i})} = 2m \]

Soit \( G \) un graphe complet de \( n \) sommets. Alors :

\[ \sum_{i = 1}^{n}{\operatorname{degré} \left(x_{i}\right) = n \left(n-1\right) } \]

• La densité d'un graphe \( G = \left(V, E\right) |V| = n, |E| =m \) est le rapport :

\[ \operatorname{densité} \left(G\right) = \frac{2m}{n \left(n-1\right) } \]

• La distance entre deux sommets est la longueur du plus court chemin les reliant. S'il n'existe pas de chemin entre les deux sommets, la distance est considérée comme infinie
• L'exentricité d'un sommet est la plus grande distance qui le sépare des autres sommets. Le diamètre d'un graphe correspond à la plus grande valeur d'exentricité des sommets du graphe. Le rayon d'un graphe est la plus petite valeur d'exentricité des sommets du graphe
• La périphérie est l'ensemble des sommets dont l'exentricité est égale au diamètre
• Le centre est l'ensembled des sommets dont l'exentricité est égale au rayon
• La centralité de proximité. Soit \( G = \left(V, E\right) , x \in V, n = |V| \) , on a :

\[ \operatorname{C}(x) = \frac{n-1}{\sum_{y \in V}{d(x, y)}} \]

Si la distance moyenne est basse, la centralité est forte

• La centralité d'intermédiarité. Soit \( G = \left(V, E\right) , x \in V \), on a :

\[ g(x) = \sum_{y \neq x; z \neq x}{\frac{\sigma_{yz}\left(x\right) }{\sigma_{yz}}} \]

où \( \sigma _{yz} \) est le nombre de plus court chemin entre \( y \) et \( z \) et \( \sigma _{yz}(x) \) est le nombre de plus court chemin entre \( y \) et \( z \) passsant par \( x \)

Soit \( G = \left(V, E\right) \) un graphe non orienté avec { γ : E \longmapsto { 1 } }. Soit \( S \in V \) le sommet initial. BFS (Breath-First Search). Chaque sommet \( x \) possède trois attributs :

• color \( \in \{ \text{ blanc, gris, noir } \} \), avec blanc : inconnu, gris : atteint mais non développé, noir : développé
• distance : c'est la distance à \( s \)
• \( \pi \) : c'est le prédécesseur dans le chemin depuis \( s \)

BFS(G, s):
  Pour chaque i dans V \ {S}
    u.color = blanc
    u.d = +oo
    u.pi = NiL
  s.color = gris
  s.d = 0
  s.pi = NiL
  Q = Nouvelle File Vide
  Enfiler(Q, s)
  Tant que Q n'est pas vide
    u = Defile(Q)
    Pour chaque v adjacent à u
      Si v.color == blanc
        v.color = gris
        v.d = u.d + 1
        v.pi = u
        Enfiler(Q, v)
    u.color = noir

Le parcours en largeur est :

• Complet
• Optimal pour la longueur
• Soit \( G \) un graphe uniforme de degré \( b \) et soit \( d \) la distance à laquelle se trouve le sommet cible \( b + b ^2 + b ^3 + \dots + b^{d} = O(b^{d} ) \). Même complexité en espace et en temps.

Voir une visualisation de BFS pour un exemple

On cherche un chemin minimim en \( x \) et \( y \). Soit \( f \) une fonction d'évaluation du sommet \( x \) : \( f(x) = g(x) + h(x) \), où \( g(x) = \) le coût du chemin jusqu'à \( x \) et \( h(x) \) est une heuristique sur le chemin jusqu'à \( y \). La frontière est modélisée par une file prioritaire.

Astar(G, s1, s2, h):
  for each u in G.V \ {s1}
    u.gscore = infty
    u.fscore = infty
    u.pi = nil
  s1.gscore = 0
  s1.fscore = h(s1)
  s1.pi = nil
  q = new file priorité
  enfile(q, s1)
  while q != vide:
    u = defile(q)
    if u == s2:
      break
    for each v in  G.adj[u]:
      gscore = u.gscore + G.gamma(u,v)
      if u.score < v.gscore:
        v.gscore = gscore
        v.fscore = gscore + h(v)
        v.pi = u
        if v not in q:
          enfiler(q,v)

La fonction h est l'heuristique utilisée. h devrait fournir une "estimation" du coût minimum pour atteidre ls sommet \( s_2 \) depuis \( v \). v.fscore = v.gscore + h(v)