Une modelisation en CSP des grammaires de proprietes

De
Publié par

Actes JFPC 2010 Une modelisation en CSP des grammaires de proprietes Denys Duchier, Thi-Bich-Hanh Dao, Yannick Parmentier, Willy Lesaint Laboratoire d'Informatique Fondamentale d'Orleans – Universite d'Orleans Batiment 3IA, Rue Leonard de Vinci – 45067 Orleans Cedex 2 Resume Les Grammaires de Proprietes (GP) constituent un formalisme a base de contraintes capable de decrire a la fois des enonces bien-formes et des enonces agram- maticaux, ce qui en fait un formalisme particulierement interessant pour traiter de la gradience de grammatica- lite, comme l'a demontre Prost [12]. Duchier et al [7] ont defini une semantique des grammaires de proprietes en theorie des modeles. Cet article poursuit ce travail en montrant comment, a partir de cette semantique, definir l'analyse syntaxique en GP sous la forme d'un Probleme de Satisfaction de Contraintes (CSP), traitable au moyen de la programmation par contraintes. Abstract Property grammars offer a constraint-based forma- lism capable of handling both well-formed and deviant utterances. It is thus well-suited for addressing issues of gradience of grammaticality, as demonstrated by Prost [12]. Duchier et al [7] contributed precise model- theoretic semantics for property grammars. The present article follows up on that work and explains how to turn such a formalization into a concrete constraint satisfac- tion problem (CSP), solvable using constraint program- ming.

  • nœuds

  • proprietes

  • nœud

  • ratio entre instances de proprietes pertinentes

  • nœud fils etiquete

  • arbre

  • grammaire

  • instance de propriete

  • arbres syntaxiques


Publié le : mardi 19 juin 2012
Lecture(s) : 39
Tags :
Source : univ-orleans.fr
Nombre de pages : 10
Voir plus Voir moins
Actes JFPC 2010
1
Une
mode´lisationenCSPdes proprie´t´es
grammaires
de
Denys Duchier, Thi-Bich-Hanh Dao, Yannick Parmentier, Willy Lesaint LaboratoiredInformatiqueFondamentaledOrle´ansUniversit´edOrl´eans Baˆtiment3IA,RueL´eonarddeVinci45067Orle´ansCedex2 prenom.nom@univ-orleans.fr
Re´sume´ LesGrammairesdePropri´et´es(GP)constituentun formalisme`abasedecontraintescapableded´ecrire`a lafoisdes´enonce´sbien-form´esetdes´enonce´sagram-maticaux,cequienfaitunformalismeparticulie`rement int´eressantpourtraiterdelagradiencedegrammatica-lit´e,commelade´montre´Prost[12].Duchieret al[7] ontde´niunes´emantiquedesgrammairesdepropri´et´es enth´eoriedesmode`les.Cetarticlepoursuitcetravailen montrantcomment,a`partirdecettese´mantique,d´enir lanalysesyntaxiqueenGPsouslaformedunProbl`eme de Satisfaction de Contraintes (CSP), traitable au moyen de la programmation par contraintes. Abstract Property grammars offer a constraint-based forma-lism capable of handling both well-formed and deviant utterances. It is thus well-suited for addressing issues of gradience of grammaticality, as demonstrated by Prost [12]. Duchieret al[7] contributed precise model-theoretic semantics for property grammars. The present article follows up on that work and explains how to turn such a formalization into a concrete constraint satisfac-tion problem (CSP), solvable using constraint program-ming.
Introduction
Danscetravail,nousnousint´eressons`aunetˆache spe´ciquedudomaineduTraitementAutomatiquedes Langues,`asavoirlanalysesyntaxique.Cettetaˆche apourbutdeconstruire,`apartirdunedescription formelle de la syntaxe de la langue naturelle (i.e., une grammaire), une structure exprimant les relations entrelesdiversconstituantsdune´nonc´e.Cettestruc-tureprendge´n´eralementuneformearborescente,on parle alors d’arbre syntaxique.
Denombreuxformalismesgrammaticauxont´et´e propos´espourd´ecrirelasyntaxedelalanguenaturelle, g´en´eralementensebasantsurunsyste`medere´e´cri-ture (e.g.ˆanıedhcuterceirr´e´serrasgaimmpoesleur hors-contexte[4],ouencorer´ee´crituredarbrespour lesgrammairesdarbresadjoints[10]).Unproble`me majeur de ces formalismes, dans un contexte de Trai-tement Automatique de la Langue, est leur manque de robustesse. En effet, ils ne permettent pas d’analyser dese´nonc´esquisontmal-forme´s,mˆemelorsquilsagit d’erreurs mineures. Commelontde´montre´PullumetScholz[13],les grammaires formelles de typesve-aritnee´ex´gnyat e´num´erativentrentceonecssleelu`oerusemalsnad, surlag´en´erationdemode`lesbienform´es,sontintrin-s`equementinadapte´esautraitementd´enonce´sagram-maticaux. Par contre, des grammaires formelles de typexetandfoynshte´roeie´seruallesdesmod`e, qui se concentrentsurunevalidationdemod`elesentermes decontraintessatisfaites,sontnaturellementadapt´ees au traitement dequasi-expressions. Blache[2,3]apropos´eleformalismedesGram-mairesdePropri´ete´s(GP),commeunformalismea` basedecontraintes,permettantdanalysera`lafoisdes e´nonce´sgrammaticauxetagrammaticaux.Prost[12] ad´evelopp´eunetechniquedanalysesyntaxiqueutili-sant GP, et permettant de produire une structure syn-taxiquepourtouttyped´enonc´e,toutenyassociant unjugementpre´cissurlagrammaticalite´del´enonc´e en question. Duchieret alno]7uoft[anem-iurns´ne tiqueenthe´oriedesmod`elespourGP,ainsiquune d´enitionlogiqueformelledestravauxdanalysesyn-taxiquemene´sparProst.Danscetarticle,nousmon-tronscommentunetelleformalisationdelase´man-tiquedeGP,peuteˆtreconvertieenunCSP,ouvrant lavoiea`limplantationdunanalyseursyntaxiquea`
base de contraintes, qui calcule des arbres syntaxiques optimaux(entermesdegrammaticalit´ed´enonc´e),au moyen d’une recherche de typebranch-and-bound. Larticleeststructure´commesuit.Ensection2, nous introduisons le formalisme des grammaires de proprie´t´es.Ensection3,nousde´nissonsunese´man-tiquedesgrammairesdeproprie´t´esbas´eesurlath´eorie desmod`eles.Cettes´emantiquevaservirdecadre`ala d´enitiondelatˆachedanalysesyntaxiqueentermes deproble`medesatisfactiondecontraintes.Cetted´e-nition va reposer sur deux types de contraintes permet-tantdeconstruirelarbresyntaxiquedun´enonc´e.Le premier type de contraintes, les contraintes de struc-turedarbre,serapre´sente´ensection4,lesecondtype decontraintes,lescontraintesdepropri´et´es,ensec-tion5.Cetted´enitiona`basedecontraintesdelana-lysesyntaxiquepourlesgrammairesdepropri´ete´sm`e-neranaturellementa`uneimplantationenprogram-mation par contraintes, qui sera introduite en sec-tion 6. Enfin, en section 7, nous comparons notre tra-vail avec les approches existantes, et en section 8, nous concluonsenpre´sentantlestravauxfuturs.
2
Grammairesdeproprie´te´s
Lesgrammairesdepropri´ete´s[2,3]constituentun formalismepermettantded´ecrirelalanguenaturelle entermesdecontrainteslocales,appel´eese´s´iteprrop. Cespropri´et´espeuventˆetreviol´eesinde´pendemment les unes des autres, ce qui rend possible la description de´nonce´sagrammaticaux(i.e.ptsaianeirev´eruine,q lensembledesproprie´te´sdelalangue),et´egalement dede´nirunenotiondegrammaticalite´(ratioentre proprie´te´sviol´eesetproprie´t´esv´erie´es). Lespropri´et´esutilis´eespourde´crirelalanguese basent sur des observations linguistiques : ordre (par-tiel) entre les mots, exclusion mutuelle entre certains motsdansuncontexteproche,cooccurrencesyste´ma-tique de certains mots dans un contexte proche, non-r´ep´etitiondecertainsmotsdansuncontexteproche, pre´sencefacultativedecertainsmots,etc. Chaqueproprie´t´ealaformeA:ψ,o`uAneetrepr´es lacat´egorie(i.e.renarbnnud)etusnadduœl,etquti´e syntaxique, etψla contrainte qui s’applique sur les nœudslsdecelui-ci.Lensembledesproprie´t´esaux-quellesnousnousint´eressonsestlesuivant: obligationA:4Buddutnœquet´etietpo,tourA, pre´sencedaumoinsunnœudls´etiquet´eB, unicit´eA:B!,pourtoutœndude´ituqteetApr,-´e sencedauplusunnœudlse´tiquete´B, line´arit´eA:BCtourpo,teuqtee´itdudtuœnA, encasdepr´esencedenœudslse´tiquet´esBetC, Bp´rcee`edC,
1 exigenceA:BCe´ddœutnttueiqet,pourtou A´rpal,decnese´teudlunnœiques´etBimplique lapr´esencedunnœudlse´tiquete´C, exclusionA:B6⇔Cruottuœndude´ituqteet,poA, desnœudslsd´etiquettesBetCsont mutuelle-ment exclusifs, constituenceA:Soutnourt´etœuddetteuqip,A, lese´tiquettesdesnœudslsappartiennenta`len-sembleS. Apartirdecetensembledeproprie´te´s,ilestpos-sibled´enonceruncertainnombredere`glesgramma-ticalesde´crivantlasyntaxedelalanguenaturelle. Parexemple,uner`eglegrammaticalestipulantquun groupe nominal contient exactement un nom et que ce nompeutˆetrepre´ce´d´edunde´terminant,pourraitˆetre repre´sent´eeparlensembledeproprie´te´sci-dessous: SN:{D,N},SN:4N,SN:N!,SN:D!, (1) (2) (3) (4) SN:DN,D:{},N:{} (5) (6) (7) o`uSN´ale`erttueiqete`fe´rSyntagme Nominal(groupe nominal),Da`Dete´nimrtna, etN`aNomap.Lprro´ei´et (1) (SN:{D,N}) indique que, dans un arbre syntaxique, lesnœudslsdunœudrepr´esentantlegroupenomi-naldoiventeˆtre´etiquete´sDouN. (2) (SN:4N) in-dique qu’un nœudSNdomine directement au moins un nœudN. (3) (SN:N!) indique qu’un nœudSNdo-mine directement au plus un nœudN. (4) (SN:D!) indique qu’un nœudSNdomine directement au plus un nœudD. (5) (SN:DN) indique que, pour tout nœudde´tiquetteSN, si ce nœud comporte deux nœuds lsd´etiquettesrespectivesDetN,alorte´-inelsdduœ quetteD`eecceder´ptteqieu´teuldiN. Enfin, (6) et (7) permettentdesassurerquelesnœudsd´etiquettesD etNsont des nœuds feuilles (seuls les mots du lexique peuventˆetresitu´esendessousdecesnœuds).Len-sembledecespropri´ete´saexactementdeuxmod`eles d’arbre syntaxique ayant la racineSN: SN SN
D
N
N
Les´etiquettesintroduitesdanscetexemplesontap-pel´eesiqaxsuesyntries´egocatet renseignent sur le type d’un constituant de la phrase. Une grammaire de pro-pri´et´esde´nitdoncdescontraintessurlesrelations entrelesdi´erentstypesdeconstituantsapparaissant dans une phrase. Pour faire le lien avec le lexique, on d´enituneassociationentremotsetcat´egoriessyn-taxiques.Parexemple,onpeutspe´cierquelemot pommee(monnutscat´egorieN) via :
cat(pomme) =N ´ 1.Egalementappele´ecooccurrence.erutare´ttislnaald
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.