N.Bel - FPLN

FONAMENTS DE PROCESSAMENT DEL LLENGUATGE NATURAL

13305 – Lingüística - UPF

FONAMENTS DE PROCESSAMENT DEL LLENGUATGE NATURAL

13305 – Lingüística - UPF

nuria.bel@upf.edu

Classe 6

N.Bel - FPLN

El programaEl programa

4.   Les oracions         Sintaxi: L’estructura de l’oració    Categories, constituents i funcions.     Gramàtiques, regles lliures de context i arbres.     Analitzadors: algoritmes i tècniques de cerca.          Processament d’informació sintàctica.     Concordança. Coordinació. Subcategorització.     Trets i unificació. Formalismes d’Unificació.     Gramàtiques lliures de context augmentades amb

unificació.  

N.Bel - FPLN

continúa ...continúa ...

      Anàlisi sintàctica probabilística amb gramàtiques lliures de context. Anàlisi probabilística lexicalitzada.

 

        Semàntica: El significat de les oracions

    Principi de composicionalitat i lògica de primer ordre.

    Predicats i arguments. Papers temàtics. Restriccions de selecció

    Representació de la informació semàntica.

    Informació semàntica a les gramàtiques d’unificació.

 

N.Bel - FPLN

En aquesta sessióEn aquesta sessió

4.   Les oracions         Sintaxi: L’estructura de l’oració    Categories, constituents i funcions.     Gramàtiques, regles lliures de context i arbres.     Analitzadors: algoritmes i tècniques d’exploració.          Processament d’informació sintàctica.     Concordança. Coordinació. Subcategorització.     Trets i unificació. Formalismes d’Unificació.     Gramàtiques lliures de context augmentades amb

unificació.  

N.Bel - FPLN

SintaxiSintaxi

Hocket (1954): “És un error pensar que les emissions més extenses que les paraules no són més que combinacions mecàniques d’unitats més petites” doncs hi ha seqüències (morfemàtiques) que no tenen sentit:

“ese parque están secas”

“las flores de ese parque están secas”

El que és més important per al PLN:

el césped de *[ese parque está seco]

[[el césped [de ese parque]] [está seco]]

N.Bel - FPLN

Sintaxi (2)Un parèntesi

Sintaxi (2)Un parèntesi

I seqüències que no són frases d’una llengua, però on la raó no és que no tenen significat

*Què qui vol?

*el arroz y pescado come gato

L’argument chomskyà és que hi ha frases gramaticals que no tenen sentit: “Colourless green ideas sleep furiously”

i que ha de ser possible descriure les combinacions de paraules que resulten gramaticals amb mitjans finits

N.Bel - FPLN

Parsing: anàlisi en constituentsWells (1947) Hockett (1954)

Parsing: anàlisi en constituentsWells (1947) Hockett (1954)

[O [SN la niña] [SVcantó [SNlas canciones]]

[O [SN ella] [SVcantó [SNlas canciones]]

[O [SN la niña] [Svcantó [SNcanciones]]

[O [SN la niña] [SVcantó]

[O [SVcantó]]

Representem amb [Sintagma C [Nucli C]] les

relacions de dominància i precedència

N.Bel - FPLN

Categories(Parts de l’oració)

Categories(Parts de l’oració)

Hem discriminat per criteris entre “Categories Lèxiques” i “Categories Funcionals” les parts de l’oració.Però també elevarem a “categoria” altra informació que tenen les paraules i que ens ha de ser molt útil per definir els constituents– gènere– nombre– temps/aspecte

N.Bel - FPLN

Jerarquia: dominància(abast – ‘scope’)

Jerarquia: dominància(abast – ‘scope’)

Estructuració del sintagma en termes d’especificador/modificador i nucli

[algunos y no todos los] niños

algunos

SD

y

coord

no

todos los

SD

SD

SD

N.Bel - FPLN

Funcions i precedènciaFuncions i precedència

Informació sobre l’ordre de les paraules i dels sintagmes:– * niña la cantó– un perro cazó un gato– un gato cazó un perro

L’ordre determina la funció

N.Bel - FPLN

Representació en àrbres: reflexa l’anàlisi en constituents

Representació en àrbres: reflexa l’anàlisi en constituents

Subjecte

N.Bel - FPLN

gramàtiques lliures de context (Context Free Grammars - CFG)

gramàtiques lliures de context (Context Free Grammars - CFG)

El formalisme matemàtic usat per tal de modelar les estructures de constituents són les gramàtiques lliures de context (CFG), també anomenades Phrase Structure Grammars, i el formalisme de les quals és equivalent a les Backus Naur Form o BNF.A aBUna CFG consisteix en un conjunt de regles (o produccions) i un lèxic de símbols. Símbols: terminals (lèxic de paraules d’una llengua) i no terminals (N, Art, SN, que expressen les generalitzacions)És declaratiu: diem què, no diem com

N.Bel - FPLN

Gramàtiques lliures de contextGramàtiques lliures de context

La forma de les regles està restringida:

A aB

1 símbol no terminal

llista ordenada de 1 o més terminals o no terminals

llegim: solament tindrem A si tenim aB

N.Bel - FPLN

La nostra primera “CFG”La nostra primera “CFG”

O SN SV

SN Art N

SV V SN

Art la

N niña

V cantó

N.Bel - FPLN

Propietats de les CFG’sPropietats de les CFG’s

l’única operació és la concatenació de símbols

l’única representació que assigna és la de constituents

els símbols no terminals no tenen propietats associades

els símbols terminals són atòmics, no tenen estructura interna

el coneixement gramatical està codificat a les regles de producció

N.Bel - FPLN

Objectiu: donar a cada interpretació una estructura

Objectiu: donar a cada interpretació una estructura

(S

(SN

(N pasajero))

(SV

(VT1 exhiba)

(SN

(SN

(N abono))

(CC o)

(SN

(N pase)))))

(S

(SN

(N pasajero))

(SV

(SV

(VT1 exhiba)

(SN

(N abono)))

(CC o)

(SV

(VI pase))))

N.Bel - FPLN

Parsing – Anàlisi amb CFG’sParsing – Anàlisi amb CFG’s

Per nosaltres fer una anàlisi és una combinació de reconèixer una seqüència d’elements i assignar-li una representació.Una representació útil (conté informació) és assignar cada oració una estructura en constituents.

Però:Hem separat el coneixement lingüístic del procediment:– la gramàtica és declarativa– Analitzador: No sap fer res més que anar a la

gramàtica i mirar les regles per executar les instruccions

N.Bel - FPLN

L’analitzador Algorisme d’exploració (search)

L’analitzador Algorisme d’exploració (search)

Hi ha dos restriccions que han de guiar l’exploració:

 -  Pel que fa a l’input: Sigui quina sigui l’anàlisi

final, ha de tenir tants terminals com paraules tingui l’input.

-  Pel que fa a la gramàtica. Sigui com sigui l’arbre resultant, ha de tenir una única arrel: el símbol O, el nostre símbol inicial.

N.Bel - FPLN

Estratègies d’exploració de l’analitzadorEstratègies d’exploració de l’analitzador

bottom-up o data-directed (“de baix a dalt” o “dirigit per les dades”): comencem pels terminals, aplicant totes les regles la banda dreta de les quals correspongui a la seqüència observada re-escribint el símbol de la banda esquerra fins que tinguem ‘O’.top-down o goal-oriented (“de dalt a baix” o “orientat a l’objectiu”): a partir del símbol ‘O’, intentarem construir totes les possibles re-escriptures: buscarà a la banda esquerra per produir deduccions segons la banda dreta de la regla.

N.Bel - FPLN

Altres instruccions per a l’analitzadorAltres instruccions per a l’analitzador

Però necessitem donar-li més:

Profunditat primer (“Depth first”): comprova totes les possibles expansions d’un símbol abans de passar al següent símbol de la llistaAmplitud primer (Breath first): comprova totes les possibles expansions de tots els elements de la llista abans de passar al següent nivell.D’esquerra a dreta i De dreta a esquerra

N.Bel - FPLN

Analitzem, explorant l’arbre de decisions possibles

Analitzem, explorant l’arbre de decisions possibles

O SN SV

SN Art N

SN N

SV V SN

Art la

N niña

N canciones

V cantó

“La niña cantó canciones”

b o tto m -up

?? --> Art

?? --> N

?? -> V

?? -> N

N --> canciones

?? --> canciones

V --> cantó

?? --> cantó

N --> niña

?? --> niña

Art --> la

?? --> la

La niña cantó canciones

N.Bel - FPLN

b o ttom -up (d ep th -f irs t)

FALLA!!

?? --> Art

FALL A

?? --> SN

SN --> N

?? --> N

?? --> SN

SN --> Art N

FALL A

?? --> V

V --> cantó

?? --> cantó

?? --> Art N

N --> niña

?? --> niña

Art --> la

?? --> la

La niña cantó canciones

N.Bel - FPLN

Comparació d’algoritmesComparació d’algoritmes

Cada una d’aquestes dues estratègies d’exploració té avantatges i desavantatges:

 

top-down no perd temps explorant arbres que no poden acabar essent una ‘O’

però perd el temps explorant arbres que no correspondran a la cadena d’entrada, de fet construirà tots els possibles per veure quin pot casar amb la cadena d’entrada.

N.Bel - FPLN

L’algorisme d’EarlyL’algorisme d’Early

Tècnica de programació dinàmica (emmagatzema sistemàticament les solucions a sub-problemes) per a un top-down, breath-first, esquerra-dretaemplena una llista (vector) que anomena chart y que conté N+1 entrades. Para cada posició de paraules en l’oració, el chart conté una llista de estats que representen els arbres parcials d’anàlisis que han estat generats fins al moment.

N.Bel - FPLN

Chart parsingChart parsing

1 la2 niña 3 cantó 4

Creem objectes on es representen el progrés i les regles de producció:

<1,2, D la >

<2,3, N niña >

Està complet si el està al final ,

Incomplet en cas contrari

N.Bel - FPLN

N.Bel - FPLN

N.Bel - FPLN

N.Bel - FPLN

N.Bel - FPLN