cs330.md

$$ \def\inf{\vdash} $$

CS330

GNU General Public License v3.0 licensed. Source available on github.com/zifeo/EPFL.

Spring 2016: Intelligence Articielle

[TOC]

Déduction

Introduction

• intelligence
  • possible définition (non unanime)
    • aptitude au calcul rapide
    • reconnaissance de formes ou de situations
    • aptitude à l'apprentissage
    • aptitude à réagir à l'environnement
    • capacité d'abstraction, de raisonnement et d'explication
  • ne se définit pas par un processus mais par les connaissances qu'il implique
    • opérations admissibles
    • lois physiques
    • lois, régles et normes sociales
  • système basé sur les connaissances
• intelligence artificielle
  • données (structurées) : nombres, noms, adresses, tableau, DB
  • connaissances = données non structurées : textuel, règles, heuristiques, expressions logiques, contraintes, probabiliste
  • thèse de Chuch : tout algo est équivalent à une machine de Turing
  • intelligence != algo : plusieurs réponses, aucune réponse, réponse variable
  • paradigme classique : spécification -> programmation
  • paradigme nouveau
    • raisonnement -> comportement emergent
    • incertitude -> calcul probabiliste
    • exemples de bon comportement -> apprentissage
    • implique : difficultés de prévoir le comportement, de garantir des résultats corrects, de savoir si le concept a été appris
  • structure
    1. représentation de connaissances, moteurs d'inférences, raisonnement incertain
    2. recherche, satisfaction de contraintes, diagnostic, planification
    3. induction (non)-paramétrique, clustering, réseaux de neurons artificiels
• modélisation : définir quels sont les conclusions qui peuvent être tirées des connaissances, définir les méthodes pour arriver à ces conclusions
• logique des prédicats
  • symboles : objets et paramètres
  • prédicats : propriétés et relations
  • propositions simples : expressions logiques
  • propositions composées : expressions formées par des prédicats et des connecteurs
• inférences : à partir d'un ensemble de proposition ${P}$ on trouve une nouvelle proposition $x$ t.q. si toutes les propositions de ${P}$, $x$ le sera aussi ${P}\inf x$
  • règles d'inférence
    • modus ponens : $p\rightarrow$ inférence $q$
    • introduction : $p,q\rightarrow$ inférence $p\wedge q$
    • élimination : $p\wedge q\rightarrow$ inférence $p$, inférence $q$
  • autres possiblités
    • chercher selon des critères logiques
    • apprendre de nouvelles connaissances
    • implique : explosion combinatoire, approximation
  • modes d'inférence
    • déduction (= calcul) : raisonnement automatique, bien fondé, monotone (non falsiabiable dans le futur)
      • A, A => B alors B
    • abduction (= diagnostic): recherche d'une solution qui correspond à des critères logiques, valable que dans un monde clos
      • B, A => B alors A
    • induction : apprentissage de nouvelles connaissances à partir d'exemples
      • A, B alors A => B

Moteur d'inférence

• moteur d'inférence : algo qui trouve expressions $q$ qui sont conséquences logiques d'un ensemble de prémisse ${P}\inf q$
  • fondé : si $q$ toujours une conséquence de ${P}$
  • complet : trouve tous les $q$
  • complet pour réfutation : trouve toutes contradictions de ${P}$
  • aucun algo est fondé et complet
  • couteux : en pratique, on se limite
    • ensemble de faits $F$ : propositions simples
    • ensemble de règles $R$ : de forme $c_1\wedge c_2\wedge\cdots\Rightarrow$ conséquence
    • inférence en temps linéaire en nombre de règles
• logique des prédicats
  • conjonctive : $a_1\wedge a_2$
  • disjonctive : $a_1\vee a_2$
• inférence par résolution
  • algo
    1. $BD\leftarrow{P}$
    2. sélection deux clauses $p_1,p_2\in BD$
    3. appliquer règle de résolution pour obtenir $q:p_1\vee p_2$
    4. si $q\not\in BP$ ajouter $q$
    5. si $q$ correspond à une solution, stop sinon répéter 2
  • fondée et complète pour la réfutation
  • procédure complète pour preuves par contradiction : $({P}\cup\neg q)\inf\bot$
  • peut ne pas s'arrêter si $q$ n'est pas une conséquence de ${P}$
• inférence par Modus Ponens : $A\\ A\Rightarrow B\\ \inf B$
  • clauses de Horn : au plus 1 proposition positive
    • $\neg c_1\vee \neg c_2\vee\cdots\vee c_n$
    • 1 seule contradiction possible : $\neg X$ et $X$
  • traduction en clauses de Horn
    • disjonction des conditions : $A\vee B\Rightarrow C\sim A\Rightarrow C,B\Rightarrow C$
    • conjonction des conclusions : $A\Rightarrow B\wedge C\sim A\Rightarrow B, A\Rightarrow C$
    • disjonction des conclusions : $A\Rightarrow B\vee C$ pas de traduction possible
  • chainage : plusieurs inférences en chaine
    • avant : à partir des faits connus, produire toutes les conséquences jusqu'à la solution (nombre de faits $n$ fini, linéaire)
    • arrière : à partir d'une description de la solution recherchée, produire les étapes intermédiaires hypothétiques qui permetteront de déduire la solution
• quantification
  • universelle : $\forall$
  • existentielle : $\exists$
  • types
    • 0ème ordre : aucun quantification
    • 1er ordre : quantification sur symboles
    • 2ème ordre : quantification sur symboles et prédicats (non utilisé en IA)
  • fonctions de Skolem : remplacer variables avec quantification existentielles par fonction qui remplit toujours la condition $(\exists y) p(x,y)$ en $p(x,f(x))$
  • quantification universels : remplacer par variable
  • unification : $U(X,Y)$ substituer variables pour rendre $U(X)=U(Y)$
  • filtrage : trouver toutes combinaisons de substitutions de variables d'un certain pattern pour rendre datum (expression sans variable) = pattern (expression avec variables)
• chainage avant avec variables

Systèmes experts

• expert : profonde connaissances d'un domain particulier
• domaine d'expert
  • grand nombre d'opérations possibles : recherche inefficace
  • analyse des moyens-buts : heuristique pour limiter la recherche
• système expert : programme qui reproduit le raisonnement d'un expert
  • inférence par modus ponens en chainage arrière : $F_1\Rightarrow^{R_1}\cdots\Rightarrow^{R_n}solution$ avec les règles $R_i$
  • début d'inférence : but
  • maintient d'un agenda des buts et évolue grâce aux sous-buts
  • chaque sous-but possède son environnement
  • arrêt d'inférence : plus de buts à satisfaire
• chainage arrière $\iff$ génération de sous-buts : similaire à general problem solver (GPS)
• chainage avant vs arrière : beaucoup de données différentes vs beaucoup de résultats produits
• explication du raisonnement : conclusions et questions posées
• logique non-monotone : inférence ne reste pas toujours valable, problème théorique
• traitement de l'incertitude : non modélisable par des clauses de Horn, imprécision de modélisation, information insuffisante
• raisonnement incertain : associer à chaque proposition une représentation numérique de l'incertitude
  • réseaux Bayesien : chiffres sont estimation sur la base de l'ensemble des observations, facile mais causal
  • logique floue : validité des prédicats suit une distribution de possiblité (pourcentage de gens qui diraient que la proposition tient), facile mais sans base théorique, bonne pour l'imprécision
  • raisonnement probabilistique : difficile à appliquer
• facteur de certitude ($CF$) : associé à chaque assertion et règle entre $-1$ et $1$
  • certainement faux : $-1$
  • inconnu : $0$
  • probablement vrai : $0.75$
  • certainement vrai : $1$
  • propagation : $A\wedge B\wedge \cdots\Rightarrow X$ donne $CF(X)=CF(règle)*\max(\min(CF(A),CF(B),\ldots),0)$
  • règle combinaison parallèle
• nombres flous

Raisonnement incertain

• inférence probabiliste : $p(B)=p(B|A)p(A)+p(B|\neg A)(1-p(A))$
• complexité : tenir compte des dépendances partout, $2^p$ avec $p$ propositons, besoin de se limiter aux causes directes, exponentiel en temps et en mémoire, donné par la largeur de l'ordre causal
• causalité : cause > effet $\iff$ parent > descendant
• independance : $p(C|A)=p(C|\neg A)=p(C)$
• marginalisation : $p(C|A)=p(C|B)p(B|A)+p(C|\neg B)(1-p(B|A))$
• descendants multiples : pas besoin de connaitre la distribution jointe
• causes multiples : distribution jointe nécessaire, dépendance conditionelle, si parent indépendant ils deviennent dépendant si l'enfant est connu
• inférence abductive : multiple cause $p(B|Y_1,\ldots,Y_k)=\alpha p(B)\Pi_{i=1}^kp(Y_i|B)$
• résolution stochastique
  • échantillonage : beaucoup de répétition, pas d'arrêt clair
  • échantillonage selon Gibbs

Abduction

Algorithmes de recherche

• algo de recherche : trouver une solution dont l'évaluation remplit des critères de succès
  • noeuds de recherche : état courant
  • fonction de successeur : liste des noeuds atteingables de $n$, espace de recherche
  • critère de succès : condition de terminaison, peut être noeud final ou chemin au noeud final (moindre coût)
• recherche en profondeur d'abord (DFS) : peu descendre très loin dans un chemin inutile, peu de mémoire
  • limiter à une profondeur (DLS) : complexité pas plus que doublée, approfondissement itératif (complexité pas plus que doublé)
  • détection de cycle
• recherche en largeur d'abord (BFS) : mémoire exponentiel, trouve toujours chemin le plus court
• optimisation de coûts : minimiser le coût augmenté à chaque génération $g(n)=c(n',n)+g(n')$ où $n$ est sucesseur de $n'$
  • DFS
  • branch-and-bound
• recherche heuristique : guider la recherche pour explorer d'abord les solutions les plus prometteuses
  • fonction heuristique : $h(n)=$ estimation du coût minimal, trouver l'heuristique en simplifiant le problème
  • estimation du coût du chemin : $f(n)=g(n)+h(n)$
• A*
  • optimalité : $h(n)=0$ noeud exploré dans l'ordre de leur coût, trouve toujours la solution optimal tant que $h(n)$ ne surestime pas le vrai coût
  • complexité : exponentiel dans la longueur de la solution, polynomial en nombre de noeurds exploré si $|h^(n)-h(n)|\le O(\log(h^(n))$ avec $h^*(n)$ coût réel
• limitations de mémoire : queue A* très longue
  • beam search : garder les $n$ meilleurs noeuds seulement, jamais explorer les autres
  • iterative deepening : effectuer un depth-first search jusqu'à un certain seuil de la fonction d'évaluation, incrémenter par petites quantités uniquement
  • memory-bounded : oublier et regénérer des noeuds
  • traitement des cycles : si chemin déjà étendu, mettre à jour les succésseurs si meilleur
  • critère de monotonicité : éviter le réarrangement causé par les cycles, garanti par $h(n_1)-h(n_2)\le c(n1,n2)$
  • simuler DFS : $g(n)=0$ et $h(n)=$ ordre dans $succ(n)$
  • simuler BFS : $g(n)=$ longueur du chemin et $h(n)=0$
• temps de calcul : imprévisible, dépend de l'ordre d'exploration
  • minimal : longueur du chemin à la solution
  • maximal : exploration de tout le graphe

Satisfaction de contraintes

• satisfaction de contraintes (CSP) : ordonnancement, planification
  • variables : $X={x_1,\ldots, x_n}$
  • domaines discrets : $D_1,\ldots,D_n$ des variables
  • contraintes : $C={c_1(x_k,x_l,\ldots),\ldots,c_m}$
  • solutions : trouver ${x_1=v_k,\ldots,x_n=v_o}$ satisfaisant toutes les contraintes
• réseau de contraintes : satisfaction de contraines binaires
  • noeuds : variable
  • arcs : contraintes
• contraintes non binaire : projection, variable supplémentaire, graphe dual pour ramener à un problème binaire
• generate-and-test : brute forcer tous les combinaisons, exponentiel en nombre de variables
• CSP par recherche
  • noeud recherche : $x_1=v_1,\ldots,x_k=v_k$
  • fonction de successeur : instantiation $x_{k+1}=v_{k+1}$ respectant toutes les constraintes
• recherche systematique
  • backjumping
  • forward checking : éviter des valeurs qui ne laissent plus aucune possibilité d'instantiation consistante pour d'autres variables
    • ajouter un label $l[i]$ à chaque variable
    • initialement : label = domaine
    • à chaque itération : éliminer du label des variables non-instanciées les valeurs inconsistantes
    • label vide : backtrack
  • lookahead : forward checking et vérifer aussi entre toute paire de variables non-instanciés
• ordre des variables : heuristique d'ordre
  • dynamic variable ordering (DVO) : prendre la variable dont le label est le plus petit
  • min-width ordering : prendre la variable qui a des contraintes avec le moins de variables ouvertes
  • max-degree ordering : prendre la variable la plus connecté dans le PSC original
  • DVO + tiebreaking avec min-width : optimal
• consistance : important de connaitre le temps requis, possible dans certaines topologies
  • consistance partielle : solution en 2 temps, éliminer combinaisons/valeurs/contraintes inconsistantes, effectuer la recherche dans l'espace reduit
  • propagation locale : algo de Waltz, appliquer un opérateur de raffinement à chaque contrainte jusqu'à qu'il n'y ait plus de changement, binaires discrets et label requis
  • complexité Waltz : $O(e\cdot n\cdot d)$ ou optimisé $O(n^2d)$
    • contraintes : $e$
    • variables : $n$
    • taille maximale de domaines : $d$
  • CSP arbre : pas de cycle, consitance des arcs garantis sans retour arrière, assigner une valeur à la racine, forcément des valeurs consistances, récursif
  • cycle : peut satisfaire consistance des arbes, mais pas de solution, car consistance des arcs est binaire
• recherche local : assigination initial, modifier jusqu'à ce que toutes les contraintes soit satisfaites, toujours exponentiel
  • min-conflicts/GSAT : changer l'assignation de la variable qui réduit le nombre total de conflits, hill-climbing (minima locaux nuisent à la performance), heuristique (valeurs avec moins de conflits pour futures instanciations)
  • recuit simulé : probabiliste, parfois faire changement non-optimal

Diagnostic

• diagnostic : trouver composantes défaillantes
  • modèle du système : MS
  • ensemble d'observations : OBS
  • ensemble compostantes défectueuses : CAND à calculer
• comportement défaillant : $MS\cup OBS\inf \bot$ (contradiction)
  • candidat explique observations : $MS\cup CAND\inf OBS$
  • candidat rend observations consistentes : $(MS-CAND)\cup OBS\inf\not\bot$
  • pas de clauses de Horn : meilleur approche avec adbuction d'une simulation
• abduction explicite : par recherche, complexité élevée, BFS ou A* si heuristique claire
  • noeud de recherche : ensemble de défauts
  • noeud initial : ensemble vide
  • fonction de successeur : ajouter un défaut
  • termination : quand les défauts permettent de déduire les observations
• transformation en deduction
  • monde clos : circuit ne change pas, pas de nouvelle défaillance, impossible de traiter les changements
  • pas tous les cas donnent lieu à des clauses de Horn
  • simuler le comportement pour tous défauts possibles
  • construire des règles pour la déduction du diagnostics à partir des observations
• raisonnement incertain : évite monde clos et système spécialisé, choix de certitude peu clair
• diagnostic par consistance : prédire les observations
  • symptôme : différence entre prévision et mesure ou 2 prévisions
  • conflict des justifications des symptômes : au moins une des composantes doit être défectueuse
  • candidats : si minimaux aucun sous-ensemble est déjà candidat
  • évaluer les candidats : $P(C)=\Pi_{c\in D}P(c)\Pi_{c\in N}(1-P(c)$ avec $D$ composantes défectueuses et $N$ non-défectueuses
  • entropie des mesres : incertitude quant à la valeur mesurée $E(var_i)=-\sum_k p(var_i=val_{ik})\log(p(var_i=val_{ik}))$, choix de l'entropie la plus elevée
  • probabilité des valeurs : $p(var_i=val_{ik})=\sum_{c\in P_{ik}}p(c)+\sum_{c\in U_i}p(c)/m$ avec $P_{ik}$ ensemble des candidats qui prédisent valeur $k$ pour mesure $i$ et $U_i$ prédisent aucune valeur pour $i$
  • probabilité des candidats : normaliser pour $\sum_{CAND} p(CAND)=1$

Planification automatique

• planification automatique
  • ensemble d'opérateurs
  • état initial
  • conditions qui doivent être satifaites
  • état : conjonction d'expressions en calcul de prédicats qui doivent être vrais
  • plan : séquence d'action/transformation
  • Chapman : si l'ensemble de situations est illimité, la planification n'est pas décidable
• opérateurs STRIPS : transformation $S_i\Rightarrow S_{i+1}$
  • préconditions $P$ : propositions qui doivent être vraies dans $S_i$
  • postconditions $A$(add) : propositions qui sont réalisées $S_{i+1}$
  • suppressions $D$(delete) : propositions qui ne sont plus vraies $S_{i+1}$
  • axiome de cadre : propositions non-mentionnées dans les suppressiosn restent valables
• planification linéaire : chainage arrière à partir du but avec arbre de recherche
  • problème de variable : on ne connait pas toujours toutes les varibles pour instancier un opérateur en chaine arrière
  • inconsistance : éliminer au plus vite
• planification A*
  • noeuds de recherche : situations
  • fonction de succésseur : chainage des sous-buts
  • coût d'un chemin : somme des coûts d'application des opérateurs
  • heuristique : $2*d(ON)-d(HOLDING)$ moins d'efforts
• anomalie de Sussman : si l'un des buts empêche un autre suivant l'ordre
  • planification non-linéaire : plusieurs buts indépendant, action en parallèle jusqu'à combination- plans : ordres partiels
  • least committment : ne pas faire de choix avant que ce soit vraiment nécessaire
  • pour chaque action on associe une variable booléenne : action à cette étape ou non
  • dernière étape : aucune action possible
  • variable d'état : pour chaque proposition possible de STRIPS et chaque étape, il existe une variable booléenne
  • si valeur change, il y a une action qui en est responsable
  • contrainte d'exclusion : mutex entre actions tels que l'une affecte la précondition de l'autre
• planification et raisonnement temporel
  • précédence : opérateur qui satisfait précondition d'un autre doit venir avant
  • ressource : deux opérations qui utilisent la même ressource ne peuvent se chevaucher
• planification hiéarchique : réduire complexité par plusieurs niveaux d'abstractions

Induction

Apprentissage supervisé

• validité de l'induction
  • monde clos
  • plus d'exemples considérées plus fiable
  • théorie de l'apprentissage : quantitifie le nombre d'exemples nécessaires pour garantir la qualité
  • données : troisième type de ressource (avec temps et mémoire)
• apprentissage
  • supervisé : modèle à partir d'exemples classifiés
  • non-supervisé : modèle en regroupant exemples similaires
• traits : feature, l'utilité des traîts peut parfois se reveler uniquement dans leur combinaison
• classification : appartenance à une classe
  • ensemble $P$ d'instance d'un concept
  • ensemble $N$ de non-instance
  • trouver description du concept qui couvre uniquement $P$
• classification simple : paramétrisé $f(x)>0$, approximation par regression $=f(x)$, frontière de décision
• classification structurée : non-paramétrisé, décomposition et classification paramétrique pour les sous-ensembles, arbres de décision, boosting (combinaison pondérée de classification)
• frontières de décisions linéaires
• perceptron
• descente de gradient stochastique : classification erronée, correction du vecteur
  • gradient : $\frac{\delta(W·X)}{\delta W}\prop X$
  • largeur de pas : $\sigma$
  • stochastique : sélection alléatoire de l'exemple
  • bonne convergance
• support vector machines : SVM
  • solution optimale
  • instance non séparable : admettre certains exemples mal-classifié, minimiser l'erreur, ou introduire une transformation non-linéaire qui les rend séparables (kernel function)
    • radial basis function : $K(X,Y)=e^{-(X-Y)^2/2\sigma^2}$
• regression : valeur d'un attribut
• moindres carrées : optimal, minimise $\sum L_i^2$ où $L_i$ distance endroit la droite et le point $i$
• overfitting : biais du modèle, variance de l'apprentissage (erreur d'observation)
• régularisation
  • optimisation $\ln(p(X\mid W))$ produit coefficients extrêmes : reégularisateur les rendent peu probables
  • autre régularisateur courant : $\sum_k w_k$ (distribution exponentielle)
• classification par régression
  • transformation logistique : sigmoïde entre 0 et 1 $p(y=c_1\mid X)=\frac{e^{w_0+w_1x_1+\cdots+w_kx_k}}{1+e^{w_0+w_1x_1+\cdots+w_kx_k}}$
    • choisir $w$ pour maximiser $\sum_i -\ln(1+e^{-y(i)W\cdot X(i)}$

Apprentissage non-paramétrique

• classification disjonctives : admettre des hypothèses $h$ non satisfaites par tous exemples positifs
• listes de décisions : admettre des hypothèses $h$ satisfaites par certains exemples négatifs
• description disjonctives : difficle de trouver description qui admet aucun exemple négatif
  • meilleur algo : recherche d'une description par spécialisation
  • noeud initial : description vide $D_0$
  • successeur : rajout d'un attribut
  • noeud final : ne couvre aucun exemple négatif
• représentation par exceptions
• arbre de classification : chaque noeud spécifie un prédicat qui détermine gauche (vrai) ou droite (faux)
  • ID3 : construction de l'arbre pour $k$ classe
    • optimal : profondeur moyenne minimale
    • incrémental : tous les exemples en même temps
    • très efficace, mais pas toujours bonne pour de nouveaux exemples (performance)
  • formaliser l'incertitude par l'entropie
  • valeurs multiples : choisir $A$ pour maximiser $\frac{H(C)-H(C\mid A)}{|valeurs(A)|}$, diviser réduction d'incertitude par le nombre de branches générées
  • alternatives à l'entropie
    • variance des sous-classes : $1/n\sum^n_{i=1}(c_i-\bar c)^2$
    • fraction d'exemples n'appartenant pas à la classe la plus fréquente $c_i$ : $|c_j|/n$
  • estimer la qualité (ou overfitting)
    • gardant une partie des exemples pour évaluer le taux d'erreur
• PAC : chiffer la qualité = relation entre $N$ exemples, $|H|$ possibilités, $\delta$ et $\epsilon$
  • probablement : classfication n'est pas approximativement correcte abec probabilité $\delta$
  • approximativement : probabilité d'erreur de classification est inféreure $\epsilon$
  • correct
• élaguer l'arbre : décision proche de feuille sont basées sur très peu d'exemples, tailler
  • selon taux d'erreur : en utilisant un nouveau jeu d'exemples
  • hypothèses d'indépendance des erreurs : statistique permet d'estimer la fréquence d'erreurs de l'arbre
  • élaguer quand nombre erreurs introduti par l'élagage est inférieur au nombre d'erreurs sans
• transformation arbre en règle : séquence de parcours
  • simplifier une règle à la fois
  • parfois toléré des exemples couverts incorrectement : élimine le bruit
• boosting : combiner plus techniques pour améliorer la précision
  • induction faible
  • adaboost
  • martingale boosting : faire dépendre prochain classifcateur des résultats des précédents

Apprentissage non-supervisé

• clustering : apprentissage de sous-classe, criète d'homogeneité
  • regrouper en aggrégats homogène
  • base : mesure de distance $d(x_1,x_2)$ entre deux exemples
  • étape
    • représentation des exemples
    • mesure de similarité : définition de proximité
    • regroupement d'exemples
• clustering hiérachique : différents niveaux
  • complexité : $n$ objets, $m$ attributs, au moins $O(n^2m)$
  • dendrogramme : représente regroupements d'exemples et niveaux de similarité
  • par agglomération :
    • placer 1 exemple par cluster
    • pour chaque exemple trouver le cluster le plus proche et fusionner
    • réadjuster l'agglomérat
  • par division : graphe de similarité
    • noeuds : instance
    • arcs : paires de noeuds dont similarité dépasse un seuil
    • poids d'un arc : similarité entre instance
    • division : couper les arcs les plus faibles et considerer les compostantes connexes
    • arbre couvrant minimal MST : single link, transitif, sensible aux erreurs d'instance, pas d'équilibre
    • coupes à poids minimal
    • coupe spectrale : pour $k>2$ instance, trier les valeurs propres dans l'ordre croissant $e_1\le e_2\le\cdot$
• clustering de partitionnement : partition unique
  • k-means
    • aucune garantie de convergence, difficle de choisr le bon $k$
    • complexité : $n$ objets, $m$ attributs, $O(lknm)$ avec $l$ nombre d'itérations
• cluster flou : probabilité d'appartenir à un cluster
  • appartenance aux clusters est distribuée gaussiennement
  • algorithme EM : expecteation maximization
• apprentissage semi-supervisé : utiliser données supplémentatires pour améliorer un apprentissage supervisé

Apprentissage bio-inspiré

• réseau de neuron artificiel
  • entrée : $e_1,\ldots, e_k$ à la couche cachée $H_1,\ldots, H_l$
  • couche cachée : à la couche de sortie $O_1,\ldots, O_m$
  • représente n'importe quelle fonction : si nombre de neuron suffisant
• neuron
• fonction d'activation
• entrainement
  • adaptation de l'algo du perceptron : itérativement passer des exemples alléatoires et corriger les poids
  • rétropropagation : à chaque prévision rétropropager l'erreur aux couches cachées
  • optimization par descente de gradient : ajuster les poids selon le gradient pour réduire l'erreur de classification
  • forme du gradient
• deep learning
  • nombreuses couches cachées : par ex. 30
  • backpropagation
  • nécessicite beaucoup de données : convergance difficile
  • imprévisibilité : qualité non garantie
• perceptron : discrimination de fomres simplements séparables
• multicouche : frontières plus complexes
• gradient disparaissant
  • perceptron : gradient de l'erreur = vecteur de l'exemple
  • multicouche : gradient doit être propagé à travers la fonction d'activation
• minima locaux
  • introduire une variation alléatoire
  • dropout : enlever quelques neurones du calcul du gradient aléatoirement
• algorithm génétiques : apprentissage par découverte
  • population initiale de $n$ solutions potentielles : chromosomes
  • fonction d'évaluation d'une solution
  • génèrer de nouvelles solutions
    • mutation aléatoire
    • combinaison de deux solutions : empêche minima locaux
  • prochain génération
    • $k$ solution ayant la fonction d'évaluation la plus élevée
    • $n-k$ solutions choisies au hasard parmi les autres
• diversité : combinaison uniquement utilise si bonne diversité
  • degrée d'individualisme : $g(s)=\frac{1}{\sum_i\frac{1}{d^2(s,s_i)}}$ avec $f(s)+g(s)$ comme nouvelle fonction d'évaluation ($f(s)$ était la fonction originel)
• généralisation
  • génération de nouvelles instances
  • évaluation de l'intérêt : heuristique
• apprentissage automatique
  • promesse : remplacer la modélisation et programmation par l'apprentissage
  • limitation : surapprentissage, données insuffisantes, imprévisible
  • théorie : PAC, pas de garantie
  • ingenierie
    • beaucoup de données : deep learning
    • utiliser connaissances pour réduire la complexité :
      • modélisation, selection des traits : apprentissage supervisé
      • imposer des contraintes : apprentissage non-supervisé