Informatique et recherche
opérationnelle
IFT6010

Intelligence Artificielle
Traitement statistique des langues naturelles

Hiver 2003


Accueil

Cours après cours

Devoirs

Horaires et locaux

Au sujet du
livre de cours

Consultez vos notes

Liens utiles

Contact

Les séminaires
RALI/LLI

Cours après cours

Voeux pieux: Cette page devrait contenir le plan du cours à venir (la partie en bleu indique une partie du cours hypothétique), ainsi que les informations pertinentes reliées (notes de cours, compléments éventuels tels que sources de programmes, données diverses, articles scientifiques, etc.).

Voici les notes de cours de la session automne 2001. Ces notes seront mises à jour au fur et à mesure de notre avancée dans le cours. Je tenterai de rendre la version modifiée de ces notes disponibles avant le cours correspondant. Désolé d'avance si je n'y parviens pas. La date peut vous servir de repère pour savoir si j'ai modifié ou pas le jeu de transparents en cours.

ps (1 acétate par page) [intro] [ngram] [dynamic] [em] [hmm] [tagger] [parsers]
[pcfg] [traduc] [trans-appli] [collocs] [cluster] [search]
pdf (1 acétate par page) [intro] [ngram] [dynamic] [em] [hmm] [tagger] [parsers]
[pcfg] [traduc] [trans-appli] [collocs] [cluster] [search]
ps (2 acétates par page) [intro] [ngram] [dynamic] [em] [hmm] [tagger] [parsers]
[pcfg] [traduc] [trans-appli] [collocs] [cluster] [search]
pdf (2 acétates par page) [intro] [ngram] [dynamic] [em] [hmm] [tagger] [parsers]
[pcfg] [traduc] [trans-appli] [collocs] [cluster] [search]
ps (4 acétates par page) [intro] [ngram] [dynamic] [em] [hmm] [tagger] [parsers]
[pcfg] [traduc] [trans-appli] [collocs] [cluster] [search]
pdf (4 acétates par page) [intro] [ngram] [dynamic] [em] [hmm] [tagger] [parsers]
[pcfg] [traduc] [trans-appli] [collocs] [cluster] [search]


  • [jeudi 3 mars 2003]
    • Vous avez la parole. Suivre l'agenda des présentations pour l'ordre du jour et les transparents
    • Vengez-vous à l'avance en m'évaluant (prévoyez que votre pause sera consacrée à remplir les formulaires d'évaluation du cours, mais je sais depuis lundi que vous n'avez pas nécessairement besoin de pause :-)

  • [lundi 31 mars 2003]
    • Vous avez la parole. Suivre l'agenda des présentations pour l'ordre du jour et les transparents

  • [jeudi 27 mars 2003] [cluster.ps]
    • Clustering vs plus proches voisins
    • Clustering bilingue

  • [lundi 24 mars 2003] [collocs.ps] [cluster.ps]
    • Rechercher des séquences de mots pertinentes dans un texte (suite et fin)
      • Applications au cas bilingue
      • Découvrir des équivalents traductionnels dans des corpus bilingues non parallèles à l'aide de collocations.
    • Clustering par maximisation de vraisemblance

  • [jeudi 20 mars 2003] [collocs.ps]
    • Rechercher des séquences de mots pertinentes dans un texte (suite)
      • Les tables de suffixes
        • Rechercher les occurrences d'une séquence dans une table de suffixes
        • Identifier l'ensemble des séquences d'un texte
      • Métriques pour identifier les séquences pertinentes
        • Information mutuelle, entropie, test de vraisemblance, etc.
      • Applications au cas bilingue

  • [lundi 17 mars 2003] [trans-appli.ps] [collocs.ps]
    • Quelques applications de la traduction automatique (suite et fin)
      • Les mémoires de traduction
    • Rechercher des séquences de mots pertinentes dans un texte
      • Qu'est-ce qu'une séquence pertinente de mots
      • Quelques propriétés des collocations
      • Table de suffixes (take one)

  • [jeudi 13 mars 2003] [search.ps]
    • Techniques de décodage (suite et fin)
      • greedy search
      • A* (stack decodeur)
    • Quelques applications de la traduction automatique
      • Outil d'aide à la traduction transtype

  • [lundi 10 mars 2003] [search.ps]
    • Décodage (suite)
      • Résumé sur le décodage DP
      • Décodage vorace (greedy) et hill-climbing
      • Décodage A* (stack decoder)
    • Quelques mots sur les métriques
    • Présentation d'applications de la traduction probabiliste

    une comparaison d'un greedy sur IBM4 et d'un décodage DP sur IBM2 (dans les deux cas un trigramme): IBM2vsIBM4


  • [lundi 10 mars 2003] [search.ps]

    • Décodage (3ème problème de la traduction automatique)
      • Décodage par programmation dynamique
      • Décodage vorace (greedy) et hill-climbing
      • Décodage A* (stack decoder)

  • [lundi 27 février 2003] [traduc.ps]

    • Tour d'horizon d' autres modèles
      • Les modèles IBM 4 & 5
      • Le modèle canal bruité syntaxique de Yamada
      • Le modèle génératif bilingue de Wu

  • [lundi 24 février 2003] [traduc.ps]

    • Le modèle IBM3
    • Alignement de viterbi (pour modèle 1 et 3)

  • [jeudi 20 février 2003] [traduc.ps] (les 80 premières acétates sont stables)

    • Évaluer l'alignement de phrases
    • Les modèles IBM
      • notion d'alignement
      • modèle 1
      • modèle 2

  • [lundi 17 février 2003] [traduc.ps] (les 60 premières acétates sont stables)

    • Étude du système le plus populaire de traduction automatique
    • N'oublions pas le succès québecois
    • Aligner des phrases dans un corpus

  • [lundi 17 février 2003] [traduc.ps] (les 60 premières acétates sont stables)

    • Étude du système le plus populaire de traduction automatique
    • N'oublions pas le succès québecois
    • Aligner des phrases dans un corpus

  • [jeudi 13 février 2003] [pcfg.ps]

  • Suite et fin du tour d'horizon des grammaires PCF
    • modèles de Collins
    • modèles de Charniak
  • Quelques approches alternatives
    • data oriented parsing (DOP)
    • link grammar
  • Démonstrations de quelques outils disponibles au RALI
    • réaccentuer = correction orthographique particulière
    • identifier la langue ou comment réussir à les faire rire avec le coup du danois
    • mémoire de traduction

  • [lundi 10 février 2003] [pcfg.ps] (les 95 premières acétates)

  • Survol de quelques travaux sur les grammaires probabilistes
    • inférence grammaticale à partir d'un corpus (partiellement) parenthésés
    • comment évalue-t-on automatiquement un modèle grammatical ?
    • le Penn Tree Bank
    • apprendre une grammaire Penn Tree Bank
    • retour sur les limites des PCFG
    • lexicalisation des grammaires
      • modèles de Collins
      • modèles de Charniak
      • data oriented parsing (DOP)
      • link grammar

  • [jeudi 06 février 2003] [pcfg.ps] (les 45 premières acétates sont "définitives")

  • Grammaires probabilistes hors-contexte (PCFG)
    • calculer la probabilité d'une chaîne (probabilités inside et outside)
    • calculer l'arbre le plus probable (CYK revisité)
    • CYK dans le cas des grammaires non CNF
    • estimer les probabilités des règles

  • [lundi 03 février 2003] [parsers.ps] [pcfg.ps] (les 35 premières acétates)

  • Algorithme Earley
  • Grammaires probabilistes hors-contexte (PCFG)
    • définition
    • propriétés
    • calculer la probabilité d'une chaîne (probabilités inside)
    • calculer la probabilité d'une chaîne (probabilités outside): cafouillage

  • [jeudi 30 janvier 2003] [parsers.ps] [pcfg.ps]

  • notion de langage formel (suite et fin)
    • quelques mots sur les grammaires ambigües
  • algorithmes d'analyse
    • Analyse descendante récursive
    • Analyse descendante prédicitive
    • Notion de grammaire LLk
    • Algorithme CYK

  • [lundi 27 janvier 2003] [tagger.ps] [parsers.ps]

  • Les taggeurs (suite et fin)
    • taggeur = HMM
    • problème avec EM dans la tâche de tagging
    • le taggeur de Brill - règle de transformation
    • le chunking
  • Notions de base des langages formels
    • survol de la classification chomskienne
    • exemple de langage régulier (adresse email)
    • exemple de langage de type 2 (expressions correctement parenthésées)
    • exemple de langage de type 1 (a^nb^nc^n)

  • [jeudi 23 janvier 2003] [em.ps] [hmm.ps]

  • Introduction aux modèles de Markov
    • calcul de la probabilité d'une observation
    • recherche d'une séquence cachée (approche locale et globale (viterbi))
    • estimation des paramètres d'un modèle markovien
    • Généralités
      • problèmes de sur-entraînement
      • points critiques
      • d'autres critères d'apprentissage (MMI)
    • application à la reconnaissance de la parole (RAP)
  • Introduction aux taggeurs
    • qu'est-ce que c'est ?
    • une autre application des modèles de markov

  • [lundi 20 janvier 2003] [em.ps] [hmm.ps] (p 518-525 dans MS)

  • Introduction à l'algorithme EM (Expectation, Maximization)
  • Introduction aux modèles de Markov

    Matériel supplémentaire:

    • Mes transparents reprennent ceux de Ted Pedersen, à un pannel de EMLP (juin 2001) [emnlp01-em-slides.pdf].
    • Du même auteur, un article donnant des pointeurs sur des articles concernant l'algorithme EM: [emnlp01-em-paper.ps]


  • [jeudi 16 janvier 2003] [ngram.ps] (acétates 65 et plus) [dynamic.ps]

  • Autres approches (suite et fin)
    • modélisation par maximisation d'entropie
    • une approche prometteuse
  • Quelques applications des modèles de langue
  • Représentation des lexiques
  • Illustration de la programmation dynamique avec la distance d'édition


  • [lundi 13 janvier 2003] [ngram.ps] (acétates 20 à 65)

  • Mesure de l'évaluation d'un modèle (entropie, perplexité)
  • Techniques de lissage
    • good-turing
    • katz (modèle backof)
    • jelinek-mercer (modèle interpolé)
    • absolut discounting
    • kneser-Ney
  • Autres approches
    • augmenter l'ordre du modèle n-gram entraîné
    • le skipping (retirer des mots du contexte conditionnant)
    • clustering (regroupement de mots en classes)
    • modèles adaptatifs (inter-domaine: caching, intra-domaine: modèles dépendants du topic)

    Matériel supplémentaire:

    La lecture de ces papiers est recommandée: [chen98.ps] et [goodman2001.ps], [survey-slm-IEEE-PROC-0004.pdf].
    Ce sont des alternatives au livre de Maning en ce qui concerne le chapitre 6


  • [jeudi 9 janvier 2003] (début du chapitre I dans MS) [intro.ps] et [ngram.ps] (les 20 premières acétates environ)

  • Les mains sales
    • Compter des mots, loi de Zipf
    • Quels langages de programmation utiliser ?
    • Ressources formatées
  • Modèles de langue
    • Image du canal bruité
    • Définition d'un modèle de langue
    • Les modèles ngrammes
    • Notion de lissage (add-one)
    • Mesure de la qualité d'un modèle (entropie, perplexité)

    Matériel supplémentaire:

  • Le tutoriel de Rosenfeld sur la théorie de l'information
  • Un mauvais segmenteur en mots écrit en shell script: tokenizer (usage: cat < mon-texte > | tokenizer)

  • Un programme C++ pour compter les fréquences des mots en utilisant une hash_map: frequence.cc.

    Essayez le par exemple sur une nouvelle de Jules Verne verne.fr en tapant:
    % cat verne.fr | frequence

  • Un programme C++ qui analyse un fichier de structures de phrases dont le format est fixé et qui produit un fichier LaTeX permettant de visualiser ces structures: Essayez le par exemple sur exemple-sent2tex en tapant:
    % sent2tex exemple-sent2tex > exemple.tex
    % latex exemple
    % xdvi exemple


  • [lundi 6 janvier 2003] (début du chapitre I dans MS) [intro.ps]

    Attention: Le premier cours débutera à 14h30 (après la réunion des maîtrises)

    • Discussion du plan de cours et autres détails usuels.
    • Introduction rapide au domaine
      • Quelques applications du traitement des langues
      • Un peu d'histoire
        • Départ approximatif: l'après-guerre.
        • Plusieurs dualités: rationalisme/empirisme, symbolisme/probabilisme.
        • Retour en force de l'approche probabiliste dans les années 80.


  • Dernière mise à jour : Mon Mar 31 15:49:26 EST 2003
    felipe@iro.umontreal.ca