Upload
andre-roger
View
110
Download
0
Embed Size (px)
Citation preview
Vers un nouvel empirisme:l’apprentissage
automatiqueJohn Goldsmith
Université de ChicagoProjet MoDyCo / CNRS
1. Remarques générales sur une perspective empiriste, et sur ses implications vis-à-vis la linguistique. – Remarques un peu trop formelles et
mathématiques sur les structures probabilistes.
2. L’apprentissage automatique de la structure morphologique, implémenté dans un logiciel: Linguistica, qui illustre cette perspective.
Le message central de Chomsky
• L’apprentissage est difficile à expliquer.• La présentation des données n’amène
pas automatiquement à une généralisation.
• Le problème de l’induction en philosophie et sa pertinence en linguistique : Comment établir une généralisation dans la portée est non-bornée, étant donné un échantillon fini d’observations.
Une conclusion possible?
• Rechercher ce qui n’est pas appris dans le langage.
• Ce qui n’est pas appris sera universel.
• Valoriser la recherche du non-appris.
Non-appris
Appris
Non-appris
Appris
Appris
Non-appris
Comment déterminer devant quel scénario nous nous trouvons?
• Considérons une question dont la réponse doit être apprise:– Le vocabulaire d’une langue, ou– La structure morphologique de ce
vocabulaire.
Quels méthodes faut-il pour apprendre l’appris?
Deux facteurs de l’apprentissage dans un
domaine1. La simplicité du système g appris2. La mesure dans laquelle g explique
les données D.
• Ces deux facteurs jouaient un role important dans la grammaire générative de LSLT (Chomsky 1975 [1955])
La métrique de simplicité
I think the right approach to the fundamental theoretical issues is the one attempted [in LSLT]: to make precise a certain format and schematism for grammars, and to provide an evaluation procedure (or simplicity measure) that leads to the choice of a particular system, a particular grammar that is of the required form, namely, the optimal, most highly valued system of the required form that is compatible with the presented data. Then what the “language learner” comes to know is that most highly valued system; it is that system that underlies the actual use of language by the person who has gained his knowledge.
Chomsky Language and Mind
• A third task is that of determining just what it means for a hypothesis about the generative grammar of a language to be “consistent” with the data of sense. Notice that it is a great oversimplification to suppose that a child must discover a generative grammar that accounts for all the linguistic data that has been presented to him and that “projects” such data to an infinite range of potential sound-meaning relations….
Chomsky Language and Mind
• The task, then, is to study what we might think of as the problem of “confirmation”—in this context, the problem of what relation must hold between a potential grammar and a set of data for this grammar to be confirmed as the actual theory of the language in question.
Equivalence
Trouver la grammaire g dont sa complexité et sa confirmation par les données D sont maximales.
Sous 2 conditions:1. g assigne à chaque
représentation engendrée une valeur p(g) et
2. nous assignons une valeur a chaque grammaire g
alors:g est la grammaire la plus
probable, étant donné D.
r
rp 1)(
||2
1g
Une citation de Syntactic Structures,Noam Chomsky 1957
The strongest requirement that could be placed on the relation between a theory of linguistic structure and particular grammars is that the theory must provide a practical and mechanical method for actually constructing the grammar, given a corpus of utterances. Let us say that such a theory provides us with a discovery procedure.
corpus grammar
• A weaker requirement would be that the theory must provide a practical and mechanical method for determining whether or not a grammar proposed for a given corpus is, in fact, the best grammar of the language from which the corpus is drawn (a decision procedure).
corpus yes/no
grammar
• An even weaker requirement would be that given a corpus and given two proposed grammars G1 and G2, the theory must tell us which is the better grammar....an evaluation procedure.
"G1" or "G2"
G1
G2
corpus
The point of view adopted here is that it is unreasonable to demand of linguistic theory that it provide anything more than a practical evaluation procedure for grammars. That is, we adopt the weakest of the three positions described above...
I think that it is very questionable that this goal is attainable in any interesting way, and I suspect that any attempt to meet it will lead into a maze of more and more elaborate and complex analytic procedures that will fail to provide answers for many important questions about the nature of linguistic structure. I believe that by lowering our sights….
lowering oursights to the more modest goal of developing an evaluation procedure for grammars we can focus attention more clearly on truly crucial problems...The correctness of this judgment can only be determined by the actual development and comparison of theories of these various sorts.
Notice, however, that the weakest of these three requirements is still strong enough to guarantee significance for a theory that meets it. There are few areas of science in which one would seriously consider the possibility of developing a general, practical, mechanical method for choosing among several theories, each compatible with the available data.
Noam Chomsky, Syntactic Structures 1957
2. L’apprentissage automatique de la grammaire
• Plan général– Un corpus C– Une famille de grammaires possibles G– Une façon de mesurer la relation entre un
corpus C et une grammaire particulière g:• Complexité de g (indépendamment du corpus)• La complexité du corpus selon grammaire g.• Notre but est de minimiser la somme de ces
deux éléments. (MDL = “Longueur de déscription minimale”). Nous y revenons!
Plus contrètement:
• Une heuristique initiale (amorce) qui prend un corpus comme input et en crée une grammaire préliminaire (sans doute trop simple).
• Une série de heuristiques de modifie la grammaire.
• Une facon d’appeler la mesure du slide précédent: est-ce que la modification est pour le meilleur? (MDL)
Corpus
Nous choississons un corpus natureld’une langue naturelle (5,000-1,000,000 mots)
Corpus
Heuristique “amorce”Nous introduisons le corpus à la heuristique “bootstrap”
Corpus
Cela nous donne unemorphologie, qui n’estpas forcément très bonne.morphologie
Heuristique “amorce”
Corpus
Heuristiquesincrémentieles
Nous l’envoyons auxheuristiques incrémentielles.
Heuristique “amorce”
morphologie
Corpus
Sortie: une morphologiemodifiéeHeuristique “amorce”
morphologie
Heuristiquesincrémentieles
morphologiemodifiée
Corpus
morphologiemodifiée
Est-ce que la modificationest un amélioration? Notre expression MDLdonne la réponse.
Heuristique “amorce”
morphologie
Heuristiquesincrémentieles
Corpus
morphologie
S’il s’agit d’une amélioration,elle remplace la vieille morphologie.
Poubelle
Heuristique “amorce”
morphologie modifiée
Corpus
Send it back to theincremental heuristics again...
Heuristique “amorce”
Heuristiquesincrémentieles
morphologiemodifiée
morphologie
Continuez jusqu’aumoment où il n’existe plusd’améliorations à tester.
Heuristiquesincrémentieles
morphologiemodifiée
Reprise
• Nous avons vu la méthode algorithmique.
• Pour chaque domaine linguistique, il nous faut préciser:
1. La heuristique “amorce”;2. Les heuristiques incrémentielles;3. Le modéle MDL (Longueur de
déscription minimale).
1. L’heuristique amorce
Elle se fait en deux temps:A. Elle trouve des coupures potentielles
en utilisant une suggestion de Zellig Harris.
B. Elle acceptent une coupure potentielle si et seulement si elle fait partie d’une signature propre.
Zellig Harris:successor frequency
Successor frequency of jum: 2jum p (jump, jumping, jumps, jumped, jumpy) b (jumble)Successor frequency of jump:5
e (jumped)i (jumping)
jump s (jumps)y (jumpy)
# (jump)
Zellig Harris:Successor Frequency
a c c e p t i n g
19 9 6 3 1 3 1 1
ableing
lerate (“accelerate”)nted (“accented”)
ident (“accident”)laim (“acclaim”)omodate (“accomodate”)reditated (“accredited”)used (“accused”)
coupure prévue
5
Zellig Harris: Successor frequency
d
a
e
i
o
9
a b debate, debuting c decade, december, decide d dedicate, deduce, deduct e deep f e defeat, defend, defer
i deficit, deficiency r defraud
d deadf deafl dealn deant death
18
3
prédictionsfausses
bonnes prédictions
Zellig Harris:Successor frequencies
c o n s e r v a t i v e s
9 18 11 6 4 1 2 1 1 2 1 1
incorrecte correcte incorrecte
Problèmes
• Si 2+ suffixes commencent par le même phoneme/lettre:
donnais
ait
a
donna
is
it
NULL
Analyse basée sur successor frequency
Amorce B: Signatures
• Nous acceptons la dernière coupure dans chaque mot: – Racine (potentiel) + suffixe (potentiel)
• Avec chaque racine (potentiel) nous associons l’ensemble de ses suffixes (potentiels):
aient
ons
es
e
mang
Signatures
Toutes les racines qui possèdent le même ensemble de suffixes forment l’ensemble de racines dans une signature:
s
ing
ed
NULL
jump
walk
laugh
aient
ons
es
e
parl
mange
chant
Finite state automaton (FSA)
ing
ed
NULL
walk
jump
PF1 SF1
PF3 SF3
SF2
jump
walk
NULL
eding
Signature propre
Une signature propre contient au moins deux racines et au moins deux suffixes.
Nous gardons (maintenant) seulement les signatures propres, et jetent les autres. (Certaines d’entres elles vont revenir plus tard.)
Reprise
Pour chaque domaine linguistique, il nous faut préciser:
1. La heuristique “amorce”;2. Les heuristiques incrémentielles;3. Le modéle MDL (Longueur de
déscription minimale).
Exemples
• Bientôt --
Reprise
Pour chaque domaine linguistique, il nous faut préciser:
1. La heuristique “amorce”;2. Les heuristiques incrémentielles;3. Le modéle MDL (Longueur de
déscription minimale).
Modèle MDL
La longueur de déscription se compose de deux termes:
[La longueur de la grammaire, en bits] +
[La quantité d’information dans le corpus qui n’est pas expliquée totalement par la grammaire, en bits]
Ici, grammaire = morphologie
[La longueur de la grammaire, en bits] +[La quantité d’information dans le corpus
qui n’est pas expliquée totalement par la grammaire, en bits]
L’idée centrale: une analyse extrait toujours des redondances. Par exemple…
Longueur de description (version naïve!)
Corpus:jump, jumps,
jumpinglaugh, laughed,
laughingsing, sang, singingthe, dog, dogs totale: 62 lettres
Analyse:Racines: jump laugh
sing sang dog (20 lettres)
Suffixes: s ing ed (6 lettres)
Non analysés: the (3 lettres)
totale: 29 lettres.
Pour decrire le corpus, il vaut mieux extraire un lexicon structuré, et décrire le corpus à travers la structure du lexicon.
s
ing
NULL
jump
walk
laugh
Pourquoi minimiser?
Si la longueur de la grammaire est trop longue, on risque “overfitting”: la grammaire décrit le message, non pas le système qui a crée le message.
Si la description des données est trop longue, on risque de ne pas avoir capté des généralisations inhérentes dans les données.
Essence of MDL…
0
100000
200000
300000
400000
500000
600000
700000
Best analysis Elegant theorythat works
badly
Baroque theorymodeled on
data
Length of morphology
Log prob of corpus
Mesurer la longueur de la morphologie
• La morphologie est composée de trois composantes:
1. Une liste de racines2. Une liste d’affixes3. Une list de signatures.
• Nous calculons d’abord (1) et (2).
La longueur d’une liste de morphèmes
• La longueur d’une list (de longueur N) de morphèmes =
– log N + longueur de chaque morphème ]
• La longueur d’un morphème m:1. log|m| + [-1 * log2 freq de chaque lettre]
2. log |m| + [-1 * log2 freq de chaque lettre, donné la lettre précédente]
autrement dit:
])[(log.1||
12 imfreq
Lexiconm
m
i
])1[|][(log.2||
22
imimfreqLexiconm
m
i
Mesurer la longueur de la morphologie
• La morphologie est composée de trois composantes:
1. Une liste de racines2. Une liste d’affixes3. Une list de signatures.
• Nous calculons (3).
s
ing
NULL
jump
walk
laugh
Nous remplaçons chaque morphème par un pointeur au morphème,qui coûte moins cher (en bits). La longueur optimale d’un pointeur est basésa fréquence: -log2 fréquence(m).
Une signature consiste de deux listes de pointers, et nous sommes en mesure de tout mesurer:
L’Information contenuedans toutes les signatures
)][
][log
][
][log(
)()(
SuffixesfSigs Stemst dansft
W
Source plus profonde de MDL
Le but de tout sysème rationel est de trouver le meilleur explication des observations.
On interprète ceci dans un contexte probabiliste: Trouver l’analyse la plus probable, étant données les faits.
)|(maxarg donnéeshprh
La règle de Bayes
)(
)()|()|(
Dpr
hprhDprDhpr
h = hypothèse; D = données.Trouver l’hypothèse la plus probable =trouver celle dans le produit de sa probabilitéet de la probabilité qu’elle donne aux donnéesest maximale.
)](log)|(log[minarg hprhDprHh
)]()|([maxarg hprhDprHh
)(
)()|()|(
Dpr
hprhDprDhpr
]
[
minarg
hdelongueur
Ddanshselonbitsdenombre
Hh
Probabilité d’un mot m
=pr(sig(m)) x pr(racine(m)|sig(m)) xpr(suffixe(m)|sig(m))
• Nous pouvons maintenant regarder le fonctionnement de cet algorithme.
http://Linguistica.uchicago.edu
Conclusion
• Comment définir ce type d’analyse linguistique?
• Aucun linguiste générative à l’heure actuelle ne l’identifierait comme une analyse générative.
• Et pourtant…• C’est une interprétation empiriste du
programme original générativiste.