Download Generación

Formalismos lógicos
• Introducción
• Gramáticas lógicas
• Gramáticas de rasgos
PLN formalismos lógicos
1
Las Gramáticas Lógicas
•
•
•
•
•
•
•
•
•
Soporte a teorías lingüísticas concretas vs formalismo general
aproximaciones lógicas o algebraicas
descripciones lingüísticas con base diversa
nivel de abstracción alto vs lenguaje próximo al de implementación
descripción lingüística ligada a una forma o estrategia de
funcionamiento vs utilización más flexible.
comprensión del LN vs generación o transferencia
descripción separada de la información sintáctica y semántica vs
descripción uniforme.
paradigma lógico de programación (o de resolución de problemas)
gramática generativa
PLN formalismos lógicos
2
Idea básica
• En las gramáticas de estructura sintagmática los
vocabularios terminal y no terminal eran conjuntos
finitos (simples colecciones de etiquetas)
• A     (V)*
• En las gramáticas lógicas los elementos de V y 
pueden ser categorías complejas, con estructura
interna y posiblemente infinitos
• functores, términos Prolog, vectores y matrices de rasgos,
etc.
PLN formalismos lógicos
3
Referencia Histórica 1
•
•
•
•
•
•
•
•
•
•
Q-Systems Colmerauer 72 => Prolog.
Gramáticas de Metamorfosis Colmerauer
ATNs Woods 1970.
WFSTs M. Kay.
Charts M. Kay.
Gramáticas de Cláusulas Definidas Pereira, Warren, 80
Gramáticas Léxico-Funcionales Kaplan Bresnan 82
Gramáticas Funcionales Dik
Gramáticas de Unificación Kay
Gramáticas Funcionales de Unificación Kay,
PLN formalismos lógicos
4
Referencia Histórica 2
•
•
•
•
•
•
•
•
•
•
GPSG Gazdar... 85
HG Pollard
HPSG Pollard Sag 87
Gramáticas Categoriales Steedman
Gramáticas Categoriales de Unificación Zeevat
Gramáticas de Extraposición Pereira
Slot Grammars Mc Cord
Gap Grammars Dahl
Discontinuous Grammars Dahl
Static Discontinuous Grammars Dahl Popowich 90
PLN formalismos lógicos
5
Referencia Histórica 3
•
•
•
•
•
DISLOG P. St.Dizier
Modular Logic Grammars McCord
Definite Clause Translation Grammars Abramson
Restriction Grammar Hirshman
Gramáticas de Rasgos.
• PATR-II Shieber,86
• ALE Carpenter,92
• ALEP Alshawi,92
• TFS Zajac,92
• CUF Dörre, Dorna,93
PLN formalismos lógicos
6
Gramáticas de cláusulas definidas (DCG)
• Repasar el tema de la asignatura de TMIA
• Notación, Ejemplos
PLN formalismos lógicos
7
Sistemas basados en rasgos 1
• Rasgos y categorías complejas
• FS (Feature Structures)
• Formalismos de unificación (Shieber)
• Declarativos
• Basados en categorías complejas (FS)
• Ligados a la superficie (normalmente basados en CFG
nucleares).
• Basados en la unificación como mecanismo básico de
combinación de FS.
• Basados en restricciones sobre las FS como medio de
representar las reglas de buena formación del Lenguaje.
PLN formalismos lógicos
8
Sistemas basados en rasgos 2
• Dos familias:
• Sistemas de rasgos abiertos
• Sistemas de rasgos con tipos (Typed Feature Structures)
• Cada FS pertenece a un tipo
• Los valores permitidos para asociar a un rasgo pertenecen a un
tipo
• Se deben definir restricciones que garanticen la utilización
correcta de los tipos
PLN formalismos lógicos
9
Estructuras de rasgos 1

cat : det




gen : masc  
sin : 

concord : num : sing  




el : 
persona : 3 

sem :



 mor :



...

PLN formalismos lógicos
10
Estructuras de rasgos 2
Las FS como DAG (Directed Acyclic Graphs)
el
mor
•
sin
...
sem
•
cat
•
concordancia
det
•
num
singular
PLN formalismos lógicos
gen
persona
masculino
3
11
Estructuras de rasgos 3
• Camino (Path): secuencia de atributos (una rama
del árbol).
• Las restricciones se pueden expresar como
ecuaciones del tipo:
• <camino_1> = <camino_2> (reentrancia)
• <camino_1> = <valor>
• <sin concordancia gen> = fem
PLN formalismos lógicos
12
Reentrancia
f : h : a 
g : h : a 


f : 1  h : a 
g : 1 



PLN formalismos lógicos
f
g
h
h
a
a
f
g
h
a
13
La relación básica entre FS es la Subsunción.
• Decimos que FS1 subsume a FS2 (o que es más
general, o que contiene menos información) si se
cumple que:
• Cualquier rasgo de FS1 existe en FS2.
• Cualquier valor de un rasgo de FS1 subsume al valor
correspondiente de FS2.
• Si dos valores son reentrantes en FS1 también lo son en
FS2.
FS1
PLN formalismos lógicos
FS2
14
Subsunción
FS1
sint: cat: n
sint: cat: n
concord: gen: fem
PLN formalismos lógicos
FS2
sint: cat: n
concord: num: sing
sint: cat: n
concord: num: sing
gen: fem
15
La operación básica es la unificación.
• La operación básica es la unificación. Esta operación
permite combinar la información de dos FSs bajo el
supuesto de que sean compatibles (unificables).
Podemos decir que la unificación de FS1 y FS2 es la
FS más general subsumida por ambas
FS = FS1 FS2
PLN formalismos lógicos
16
Unificación
sint: cat: n
concord: gen: fem
sint: cat: n
concord: num: sing
sint: cat: n
concord: num: sing
gen: fem
PLN formalismos lógicos
17
Análisis con gramáticas de rasgos abiertas 1
• Términos Prolog vs (untyped) Feature Structures (DAGs)
• Los términos Prolog pueden considerarse Dags que permiten la
reentrancia (subgraph sharing) únicamente para las hojas
etiquetadas con variables.
• Los dos formalismos pueden representar información parcial.
• Los dos formalismos permiten que la información se incremente a
medida que el contexto se extienda.
• Los DAGs permiten la omisión de la información no esencial
• Los DAGs permiten, al mismo nivel de anidado, que los rasgos se
incluyan en cualquier orden
• El sistema más conocido es PATR II (Shieber)
PLN formalismos lógicos
18
Análisis con gramáticas de rasgos abiertas 2
• Representación de términos vs representación de FS.
• representación naive FS
• Gazdar,Mellish, 1989
• Boyer, 1988
• P-Patr, Hirsh, 1988
• Schöter, 1993
• Unificación de términos vs unificación de FS.
• La unificación de términos es lineal
• La unificación de Dags es O(n2)
PLN formalismos lógicos
19
Análisis con gramáticas de rasgos abiertas 3


n :   
cat
:


 v : -  
head
:

 

X

agr : per : 3


bar : 2



n :   

cat : 
 
v
:

 




 per : 3  
 head : agr : 


X

 num : pl 

case : nom









 bar : 2

PLN formalismos lógicos
the fish
cat(+,-,3,_,_,2)
the fish are colourful
cat(+,-,3,pl,nom,2)
20
Análisis con gramáticas de rasgos abiertas 4


n :   
cat
:


 v : -  
head
:

 

X

agr : per : 3


bar : 2

X
X
X
X
:
:
:
:
the fish
cat(+,-,3,_,_,2)
head : cat : n <== '+'
head : cat : v <== '-'
head : agr : per <== 3
bar <== 2
PLN formalismos lógicos
21
Análisis con gramáticas de rasgos abiertas 5
La representación de las estructuras de rasgos
listas Prolog abiertas (Gazdar, Mellish)
[cat:
arg0:
cat : v



cat
:
sn






arg0 : caso : nom 



 num : sing  

v
[cat: sn
caso: nom
num: sing|_]|_]
[cat:v, arg0:[cat:sn, caso:nom, num:sing|_]|_]
PLN formalismos lógicos
22
Notación Patr II 1

cat : n




gen
:
masc


sin : 

concord :  num : sing  




pepe : 
 persona : 3 

sem : pepe



 mor :

word


...


pepe:
<sin cat> = n
<sin concordancia gen> = masc
<sin concordancia num> = sing
<sin concordancia persona> = 3
<sem> = pepe
...
PLN formalismos lógicos
23
Notación Patr II 2
let nombre-masc-sing be:
<sin cat> = n
<sin concordancia gen> = masc
<sin concordancia num> = sing
<sin concordancia persona> = 3.
word pepe:
PLN formalismos lógicos
nombre-masc-sing
<sem> = pepe.
24
Herencia en Patr II
let verbo be:
<sin cat> = v
<sin suj cat> = gn
<sin suj caso> = nominativo.
let vt be:
verbo
<sin obj1 cat> = gn
<sin obj1 caso> = acusativo.
let vdat be:
vt
<sin obj2 cat> = gprep
<sin obj2 prep> = a.
word reir:
verbo
<sem pred> = reir
<sem arg1> = humano.
(alguien ríe)
word dar:
vdat
<sem pred> = dar
<sem arg1> = humano
<sem arg2> = cosa
<sem arg3> = humano.
(alguien da algo a alguien).
PLN formalismos lógicos
25
REGLAS EN Patr II
X0 --> X1 X2
<X0 cat> = GN
<X1 cat> = det
<X2 cat> = n
<X1 concord> = <X2 concord>
<X0 concord> = <X1 concord>.
GN --> det n
<det concord> = <n concord>
<GN concord> = <n concord>.
PLN formalismos lógicos
26
Gramáticas de rasgos con tipos
Ejemplos: ALE, CUF, TFS, ALEP
cada FS tiene asociado un tipo
cada rasgo tiene asociado un tipo
para sus valores
la estructura de tipos suele ser
prescrita
PLN formalismos lógicos
bot sub [list, atom]
list sub [e-list ne-list]
e-list sub []
ne-list sub []
intro [hd:bot,
tl:list]
atom sub [a, b]
a sub []
b sub []
27
Ejemplo gramática GPSG (Alvey) 1
FEATURE N{+, -}
FEATURE V{+, -}
FEATURE BAR{0, 1, 2}
...
ALIAS N = [N +, V -, BAR 0]
...
SET VHEAD = {N, V, PER, PLU, PAST, VFORM, AUX, INV}
SET NHEAD = {N, V, PER, PLU, NTYPE, CASE, PRD}
...
PLN formalismos lógicos
28
Ejemplo gramática GPSG (Alvey) 2
WORD laughs :
V[SUBCAT INTRANS, PLU -, PER 3, PAST -, VFORM FIN, AUX -, INV -] : laugh1.
WORD laugh :
V[SUBCAT INTRANS, PLU -, PER 1, PAST -, VFORM FIN, AUX -, INV -] : laugh1,
V[SUBCAT INTRANS, PLU -, PER 2, PAST -, VFORM FIN, AUX -, INV -] : laugh1,
V[SUBCAT INTRANS, PLU +, PAST -, VFORM FIN, AUX -, INV -] : laugh1,
V[SUBCAT INTRANS, VFORM BSE, AUX -, INV -] : laugh1.
...
PSRULE VP1 : VP --> H0[SUBCAT INTRANS] : 1.
PSRULE VP2 : VP --> H0[SUBCAT TRANS] NP[CASE ACC, PRD -] :
(lambda (x) (2 (lambda (y) (1 x y)))).
PSRULE VP8 : VP --> H0[SUBCAT DITRANS] NP[CASE ACC, PRD -]
NP[CASE ACC, PRD -] :
(lambda (x) (3 (lambda (y) (2 (lambda (z) (1 x y z)))))).
...
PLN formalismos lógicos
29
HPSG usando ALE
bot
sign
phrase
...
cat
sub [sign,synsem,loc,cat,head,list,nonloc,pform,bool,cont,context,para,index,
psoa,con_struc,pers,num,gen,case,vform,ontologia,morfo,wh_str,marking,xbar].
sub [word,phrase]
intro [phon:list,synsem:synsem].
sub []
intro [dtrs:con_struc].
sub [cat_subst,cat_funct]
intro [head:head,subj:list,comps:list,mark:list,fill:list,adj:list,
marking:bool,xbar:xbar].
...
synsem sub [synsemsubst,synsemfunct]
intro [loc:loc,nonloc:nonloc].
synsemsubst sub [synsemnoun,synsemverb,synsemadj,synsemprep]
intro [loc:locsubst].
synsemfunct
sub [synsemdet,synsemmark].
synsemnoun
sub [synsempropi,synsemcomu]
intro [loc:locnoun].
PLN formalismos lógicos
30
Extensiones de los formalismos lógicos
•
•
•
•
Gramáticas de Extraposición
Definite Clause Translation Grammars
Gramáticas lógicas modulares
...
PLN formalismos lógicos
31
Gramáticas de Extraposición
Pereira, 1981: Fenómeno de la Extraposición izquierda
"el peix que el gat menja es mou”
[frase el peix quei [frase el gat menja ti] es_mou]
marca
PLN formalismos lógicos
traza
32
Posibles soluciones 1
frase
sintagma_nominal
sintagma_nominal
sintagma_nominal
sintagma_nominal
traça
sintagma_verbal
sintagma_verbal
relatiu
relatiu
sintagma_prep
--> sintagma_nominal, sintagma_verbal.
--> nom_propi.
--> det, nom, relatiu.
--> det, nom, sintagma_prep.
--> traça.
--> [].
--> verb, sintagma_nominal.
--> verb.
--> [].
--> pron_rel, frase.
--> prep, sintagma_nominal.
PROBLEMA: NO ES UNA SOLUCION, PERMITE EL
SINTAGMA NOMINAL ELIDIDO FUERA DE LA ORACION
DE RELATIVO
PLN formalismos lógicos
33
Posibles soluciones 2
frase_completa
frase(F0)
sintagma_verbal(F1).
sintagma_nominal(F0,F0)
sintagma_nominal(F0,F0)
sintagma_nominal(F0,F1)
sintagma_nominal(traza, nil)
traza
sintagma_verbal(F0)
sintagma_verbal(nil)
relatiu
relatiu
sintagma_prep(F0,F1)
--> frase(nil).
--> sintagma_nominal(F0,F1),
--> nom_propi.
--> det, nom, relatiu.
--> det, nom, sintagma_prep(F0,F1).
--> traza.
--> [].
--> verb, sintagma_nominal(F0,nil).
--> verb.
--> [].
--> pron_rel, frase(traza).
--> prep, sintagma_nominal(F0,F1).
PROBLEMA: MULTIPLICACION DE ARGUMENTOS
PLN formalismos lógicos
34
Posibles soluciones 3
frase
sintagma_nominal
sintagma_nominal
sintagma_nominal
sintagma_nominal
traça
sintagma_verbal
sintagma_verbal
relatiu
relatiu
sintagma_prep
marca_rel ... traça
--> sintagma_nominal, sintagma_verbal.
--> nom_propi.
--> det, nom, relatiu.
--> det, nom, sintagma_prep.
--> traça.
--> [].
--> verb, sintagma_nominal.
--> verb.
--> [].
--> marca_rel, frase.
--> prep, sintagma_nominal.
--> pron_rel.
Regla de extraposición
PLN formalismos lógicos
35
Posibles soluciones 4
frase
frase_nominal
det
nom
relatiu
marca_rel
[el]
[peix]
[que]
frase
frase_nominal
det
nom
relatiu
[el]
[gat]
[]
frase_verbal
verb
[menja]
frase_nominal
traça
frase_verbal
verb
PLN formalismos lógicos
[es_mou]
36