Date post: | 23-Jan-2016 |
Category: |
Documents |
Upload: | manuelita-rafael |
View: | 224 times |
Download: | 0 times |
PLN parsing unificación 1
Análisis de gramáticas lógicas
• Introducción
• El Prolog como analizador
• Análisis con gramáticas de rasgos abiertas
• Schöter
• Análisis con gramáticas de rasgos con tipos• ALE (Carpenter)
• Amalia (Wintner)
PLN parsing unificación 2
Introducción 1
• Gramáticas Sintagmáticas (Phrase Structure Grammars) vs Gramáticas Lógicas (Logic Grammars)• Elementos de los vocabularios (terminal y no terminal)
• símbolos (etiquetas) pertenecientes a un conjunto finito
• expresiones abiertas• términos de una lógica de predicados de 1er orden (ej. términos
Prolog)
• estructuras de rasgos (Feature Structures, FS)
• ...
PLN parsing unificación 3
Introducción 2
• Gramáticas Lógicas vs Gramáticas de Unificación• El peso de la unificación
• Adaptación de los algoritmos clásicos de tratamiento de gramáticas incontextuales
PLN parsing unificación 4
Introducción 3
El peso de la unificación Tomabechi,1991
85% - 90% del tiempo de análisis 75% - 95% de este tiempo: copia de estructuras > 60% de las unificaciones de los análisis correctos fallan
Otras operaciones subsunción, generalización, herencia, disyunción,
negación, reescritura, asignación
PLN parsing unificación 5
Introducción 4
Unificación de dags y unificación de términos Representación de las estructuras de rasgos Compilación:
• FS términos Prolog, vectores de bits, predicados lógicos
• P-Patr (Hirst,1988), CLE (Hinrich,1992), Schöter
• HPSG Tag (Kasper, Kiefer)
• FS con tipos: ALE (Carpenter,1993), ALEP, TFS, CUF
WAM (Warren Abstract Machine) Carpenter, Penn (ALE), Wintner (Amalia)
PLN parsing unificación 6
Esquemas de análisis con unificación
• Enriquecer el esquema de análisis con información que puede añadirse al núcleo incontextual de la gramática
• Introducción de rasgos 0 (A ) para las producciones
(X) para los constituyentes ([A , i, j]) para los items
• Aplicable a CKI, Earley, LR, ...
() () subsunción
unificación () ()
PLN parsing unificación 7
Extensión del esquema de Earley 1
Iearley = {[A , i, j] | A PG 0 i j 0 (A ) () consistent ( ())}
Dinit = { [S , 0, 0] | () = 0 (S )}
PLN parsing unificación 8
Extensión del esquema de Earley 2
Dscan = {[A a, i, j], [a, j, j+1] [A a, i, j+1] | () = () ()}
Dcompl = {[A B, i, j], [B , j, k] [AB, i, k] | () = () ()}}
Dpred = {[A B, i, j] [B, j, j] | () = (B) (B)}}}
PLN parsing unificación 9
Prolog como analizador 1
• Ventajas• Análisis sintáctico como demostración de un
teorema
• No es necesario construir un analizador
• Incorporado al lenguaje: DCG
• Relativamente fácil de escribir la gramática
• Relativamente fácil de integrar
PLN parsing unificación 10
Prolog como analizador 2
• Limitaciones• Estrategia fija descendente
• Orden de tratamiento fijo de izquierda a derecha
• Orden de aplicación de las cláusulas (reglas de la gramática) fijo
• Problemas al gestionar la recursividad izquierda
• Repetición de cálculos
• Generación de árboles de análisis parciales inútiles
• Rigidez
PLN parsing unificación 11
Mejoras (Stabler,1990) 1
• Separación de las cláusulas de la gramática de las del lexicón.
• Reordenación de los objetivos a satisfacer. Estática y Dinámica (en el momento de intentar la demostración de la parte derecha de la cláusula),
• Técnicas de desplegado. Substituyendo parte de los objetivos de la derecha de una cláusula por el desplegado de la o las posibles cláusulas a expandir.
• Evaluación parcial. Ejecución por adelantado de etapas de resolución y reordenación de los literales.
PLN parsing unificación 12
Mejoras (Stabler,1990) 2
• Generación y test. Ejecutar los tests cuanto antes dentro de una conjunción.
• Uso de funciones de selección específicas del dominio• Ordenación de literales de la gramática usando técnicas
estadísticas que tengan en cuenta factores como el número de argumentos, su complejidad, su nivel de instanciación, etc...
• Podado dinámico (ej. limitaciones sobre el número de pasos recursivos).
• Almacenamiento de resultados intermedios (positivos o negativos)
PLN parsing unificación 13
Mejoras (Kiefer et al, 1999) 3
• Precompilación del lexicón• expansión y aplicación de reglas léxicas
• eliminación de partes de la FS no útiles para el análisis
• Mejoras en la unificación• algoritmo casi-destructivo de unificación de Tomabechi
• reusar partes de la estructura de entrada en la de salida (Pereira)
• Precompilación de la unificación de tipos• Precompilación de las reglas de filtrado
• evitar el fallo de las unificaciones aplicando filtros baratos
PLN parsing unificación 14
Mejoras (Kiefer et al, 1999) 4
• Filtros dinámicos de unificación (“quick check”)• Reducción del tamaño de las FS con restrictores• Limititación del número inicial de items del chart• Cálculo de los mejores análisis parciales
PLN parsing unificación 15
Unificación
• Técnicas• Compartición de información en FS y MFS
• [Pereira, 1985], [Karttunen,Kay, 1985]
• Incremental Copying
• Lazy copying
PLN parsing unificación 16
BUP 1
• Bottom Up Parser• Traducción, en tiempo de compilación, de les reglas de
la gramàtica, escritas en DCG, a un tipo de cláusulas de Horn, denominadas cláusulas BUP, que posteriormente serán procesadas por Prolog.
• Dotar a la gramática DCG original de una interpretación procedimental diferente.
• El analizador resultante incorpora en las cláusulas BUP el mecanismo de control: de tipo ascendente y en profundidad ("left corner")
PLN parsing unificación 17
BUP 2
• [Matsumoto et al, 1983], [Matsumoto et al, 1985]• Búsqueda indexada para Links• Consulta en diccionario• almacenamiento de éxitos y fracasos parciales
• LangLab (Tanaka)• XG• Lexías. Tries
• SAX (Matsumoto, Sagimura)• PAX (paralelo), Prologs paralelos (Parlog -Clark-, Guarded Horn
Clauses -Ueda-)• Técnicas de compilación Prolog
• indexación de predicados• eliminación de recursividad terminal
PLN parsing unificación 18
BUP 3
gramática DCG original
gramática BUP
proceso de la gramática BUP como sise tratara de una DCG
PLN parsing unificación 19
Paso de DCG a BUP 1
reglas del tipo c0 c1 c2.
producen reglas BUP del tipo:
c1 (Obj, Pal_ini, Pal_fin):-objetivo (c2, Pal_ini,Pal_1),c0 (Obj, Pal_1,Pal_fin).
reglas del tipo: c0 c1.
producen reglas BUP del tipo:
c1 (Obj, Pal_ini, Pal_fin):-c0 (Obj, Pal_ini,Pal_fin).
PLN parsing unificación 20
donde:
objetivo (Obj,X,Z) :- dicc (C,X,Y), P =.. [C,Obj,Y,Z], P.
La cláusula objetivo da lugar a la expansión horizontal
Paso de DCG a BUP 2
PLN parsing unificación 21
BUP (ejemplo) 1
oracion sintagma_nominal, sintagma_verbal.sintagma_nominal pronombre.sintagma_verbal verbo_intransitivo.Pronombre [ella].verbo_intransitivo [pasea].
Esta gramática y lexicón DCG (G1) sólo es capaz de analizar
la oración "ella pasea"
PLN parsing unificación 22
BUP (ejemplo) 2
sintagma_nominal (Obj) objetivo (sintagma_verbal), oracion (Obj).pronombre (Obj) sintagma_nominal (Obj).verbo_intransitivo (Obj) sintagma_verbal (Obj).
dicc (pronombre) [ella].dicc (verbo_intransitivo) [pasea].
Aplicando las transformaciones anteriores obtenemosuna gramática BUP (G2) equivalente
PLN parsing unificación 23
BUP (ejemplo) 3
sintagma_nominal (Obj,X,Z):-objetivo(sintagma_verbal,X,Y),
oracion (Obj,Y,Z).pronombre (Obj,X,Y):-
sintagma_nominal (Obj,X,Y).verbo_intransitivo (Obj,X,Y):-
sintagma_verbal (Obj,X,Y).dicc (pronombre,[ella|X],X).dicc (verbo_intransitivo,[pasea|X],X).oracion (oracion,X,X).sintagma_nominal (sintagma_nominal,X,X).sintagma_verbal (sintagma_verbal,X,X).pronombre (pronombre,X,X).verbo_intransitivo (verbo_intransitivo,X,X).
Explicitando los argumentos ocultos de la DCG tenemosuna gramática Prolog (G3) equivalente
PLN parsing unificación 24
BUP (ejemplo) 4
el objetivo inicial
objetivo(oracion, [ella,pasea], []).
da lugar al subobjetivo dicc y a la construcción del objetivo ascendente
dicc(pronombre, [ella,pasea], [pasea])pronombre(oracion, [pasea], [])
la aplicación de la cláusula correspondiente permite la ascensión left-corner
sintagma_nominal (oracion, [pasea], [])
PLN parsing unificación 25
BUP (ejemplo) 5
la aplicación de la cláusula que expande el sintagma_nominal produce
objetivo (sintagma_verbal, [pasea], Y)oracion (oracion, Y, [])
la cláusula objetivo da lugar a la expansión horizontal
dicc (verbo_intransitivo, [pasea], [])verbo_intransitivo (sintagma_verbal, [], Y)
PLN parsing unificación 26
BUP (ejemplo) 6
la aplicación de la cláusula correspondiente permite la ascensión left-corner
sintagma_verbal (sintagma_verbal, [], Y)
que permite, a continuación, la unificación de Y con []
sintagma_verbal (sintagma_verbal, [], [])oracion (oracion, [], [])
PLN parsing unificación 27
Análisis con gramáticas de rasgos abiertas 1
• Boyer,1988• Convierte las listas originales de rasgos en listas
incompletas.
• Efectúa la reordenación de las listas y renombrado de las variables.
• Expande las desreferenciaciones de las ecuaciones.
• Expande las apariciones de determinados predicados.
PLN parsing unificación 28
Análisis con gramáticas de rasgos abiertas 2
P-Patr (Hirsh, 1988)1) Cálculo de la aridad y composición de todas las FS complejas2) Pares atributo/valor en posición correcta. Listas cerradas.Eliminación de los atributos. Análisis siguiendo una estrategia left corner
[n,[masc,sing,_]] [n,[_,plu,3]]
sing : num
masc : gen :agr
n :cat
3 :per
plu : num :agr
n :cat
PLN parsing unificación 29
oracion sintagma_nominal, sintagma_verbal <oracion head> === <sintagma_verbal head> <sintagma_verbal head agr> === <sintagma_nominal head agr>
se representaría como:
oracion([head:[agr:Y]]) -->sintagma_nominal([head:
[agr:Y]]),sintagma_verbal([head:[agr:Y]]).
es decir, los componentes de la backbone CFG actúan como functores y las ecuaciones se reflejan en argumentos
ojo! parte de la información que en la forma original se compartía, ahora se copia!
Análisis con gramáticas de rasgos abiertas 3
PLN parsing unificación 30
Schöter 1993 1
• Compilación Patr términos Prolog• se extrae un conjunto de dags de referencia a partir de la gramática.• se genera una especificación tipificada de la gramática
• Se usa esta especificación para construir un conjunto de esquemas de traducción de dags a términos• funciones de acceso
• Se aplican los esquemas y funciones de acceso sobre la gramática inicial para construir la gramática de términos
PLN parsing unificación 31
Schöter 1993 2
PATRequations
PrologDAGs
flatterms
Hirsh-stylelists
partial evaluation compilation
PLN parsing unificación 32
Schöter 1993 3
rule(1,tran,VB,V,NP):-V:subcat === 1,
cat_macro([v,bar(0)],V),
cat_macro([norm,bar(2)],NP),cat_macro(bar(1),VB),
VB:head === V:head, V:subj === ‘-’, VB:subj ===
V:subj, NP:tree === A, V:tree === B, VB:tree ===
vb(A,B).
V1 H[1], N2
subcategorization numberrule identificationmother categorydaughters
PATR's macro facility
PLN parsing unificación 33
Schöter 1993 4
rule(1,tran,A,B,C):-C===[head:[cat:[maj:[n:+,v:-|D],min:nil|
E]...],B===[subcat:1,head:[cat:[maj:[n:-,v:+|
I]...],C===[bar:1,head[cat:[maj:[n:-,v:+|I]...].
macro expansionindividual unification performance
Evaluación parcial
PLN parsing unificación 34
Schöter 1993 5
rule(nil,bare_np,A,B):-B===[head:[cat:[maj:[n:+,v:-|C],min:nil|D]...],A===[bar:2,head:[cat:[maj:[n:+,v:-|C],min:nil|
D]...],(
A:head:agr:num === pl;
A:head:ntype === mass).
Evaluación parcial
DAG:Path <== Value(A===B;C===D)
no pueden ser precompilados, han de ser evaluados en el momento del parsing
PLN parsing unificación 35
Schöter 1993 6
Compilación
Los términos deben poseer instancias instanciadas al máximoConseguir un inventario estable de features
conjunto de features enumeración
Usar sólo la información implícita en la gramática (no hay estructura de tipos preexistente)
3 etapas 1) Obtención de la estructura de tipos de la gramática (implícita en ella) 2) Obtención de un conjunto de templates para traducir dags a términos 3) Aplicar las templates sobre todos los dags de la gramática
PLN parsing unificación 36
Schöter 1993 7
path(0, head:cat:n, [+]).path(0, head:cat:v, [-]).path(0, head:agr:per, [1,2,3]).path(0, head:agr:num, [sg,pl]).path(0, head:case, [nom,acc]).path(0, head:nform, [it,norm]).path(0, bar, [0]).
1ª etapa
Fuente de conocimiento: conjunto representativo de dags(por defecto la propia gramática, incluyendo el lexicón)Posibilidad de modificación manualPosibilidad de usar una especificación de la estructura de tipos
hierarchy type number (0 for simple terms)feature pathset of values
PLN parsing unificación 37
Schöter 1993 8
2ª etapa
1) Compiler template Skeletal maximal DAG whose values are replaced by variables Equivalent terms all of whose arguments are terms A set of type constraints on atomic values2) Access functions
path(0, head:cat:n, [+]).path(0, head:cat:v, [-]).path(0, head:agr:per, [1,2,3]).path(0, head:agr:num, [sg,pl]).path(0, head:case, [nom,acc]).path(0, head:nform, [it,norm]).path(0, bar, [0]).
[head:[cat:[n:A,v:B|_],agr:[per:C,num:D|_],case:E,nform:F|_],bar:G|_]dag0(A,B,C,D,E,F,G)
PLN parsing unificación 38
Schöter 1993 9
Access functionsReplacing the functionality lost in moving from named grouped arguments to positional independent ones
a_func/3a_func(Path, Term, Value)
path(0, head:cat:n, [+]).path(0, head:cat:v, [-]).path(0, head:agr:per, [1,2,3]).path(0, head:agr:num, [sg,pl]).path(0, head:case, [nom,acc]).path(0, head:nform, [it,norm]).path(0, bar, [0]).
a_func(head_cat, dag0(...,A,B,...), dag3(A,B))....
Functions (dagterm/1) are also generated to recognize terms as compiled DAGs
PLN parsing unificación 39
Schöter 1993 10
rule(nil,bare_np,A,B):-B===[head:[cat:[maj:[n:+,v:-|C],min:nil|D]...],A===[bar:2,head:[cat:[maj:[n:+,v:-|C],min:nil|
D]...],(
A:head:agr:num === pl;
A:head:ntype === mass).
rule(nil,bare_np,dag0(2,np(A),_,_,_,_,_,_,nil,-,+,norm,H,I,J,K,L,M,N,O,P,Q),dag0(1,A,_,_,_,_,_,_,nil,-,+,norm,H,I,J,K,L,M,N,O,P,Q)):-(a_func(head:agr:num, dag0(1,A,_,_,_,_,_,_,nil,-,
+,norm,H,I,J,K,L,M,N,O,P,Q),pl);
a_func(head:ntype, dag0(1,A,_,_,_,_,_,_,nil,-,
+,norm,H,I,J,K,L,M,N,O,P,Q),mass)).
Uso de Access functions
PLN parsing unificación 40
Schöter 1993 11
rule(1,tran,dag0(1,vb(A,B),_,C,_,_,_,_,nil,-,
+,D,E,F,G,H,I,J,K,L,M,N),dag0(0,A,1,C,_,_,_,_,nil,-,+,D,E,F,G,H,I,J,K,L,M,N),dag0(2,B,_,_,_,_,_,_,nil,+,-,norm,_,_,_,_,_,_,_,_,_,_),
3ª etapa
Translating DAGs of the grammar into termsUnifying the DAG to be compiled with the template's skeletal maximal DAG
rule(1,tran,A,B,C):-C===[head:[cat:[maj:[n:+,v:-|D],min:nil|
E]...],B===[subcat:1,head:[cat:[maj:[n:-,v:+|
I]...],C===[bar:1,head[cat:[maj:[n:-,v:+|I]...].
PLN parsing unificación 41
Schöter 1993 12
Transformaciones en el analizador
DAG1: Path1 === DAG2: Path2
DAG: Path <== Value
path_to_pathname(Path1,PathName1),path_to_pathname(Path2,PathName2),a_func(PathName1,Term1,V),a_func(PathName2,Term2,V)path_to_pathname(Path,PathName),a_func(PathName,Term,V0),nonvar(V0),V0 = Value
PLN parsing unificación 42
Schöter 1993 13
Test Grammar: GPSGdiccionario 268 lexemas39 reglas10 definiciones auxiliares22 rasgos
Extensiones:Implicit Types
Gross (G) Type: atomic vs complexFine (F) Type: valid extensions of a labelTerminal (T) Type: constraints sobre los
valoresConstraints
FCR (Feature Co-occurrence Restriction)Hierarchical Compilation
PLN parsing unificación 43
Restrictores
• Forma de limitar el espacio de busqueda• [Shieber,1985], [Seiffert,1987], [Gerdemann,1993], [La Serna,1998]• Dominios potencialmente infinitos• Algoritmos que implican predicción (e.g. Earley)• R = Restrictor = conjunto finito de caminos (subconjunto del conjunto de
caminos, potencialmente infinito)• RD Restricted Dag (relativo a R)
• RD subsume a D
• Para cada camino p en RD, q en R tal que p es prefijo de q
• RD es el dag más específico que satisface estas conditiones
• Uso de RD para predicción y D para scanning y completion• Forma de seleccionar los restrictores:
• cat: CFG backbone
• Modelo estadístico sobre el grado de instanciación de los rasgos
PLN parsing unificación 44
Análisis con gramáticas de rasgos con tipos 1
• Typed FS• Cualquier FS f posee un tipo t
• t T, conjunto finito no vacío de tipos normalmente organizado como una jerarquía
• Una FS f, de tipo t permite tener un conjunto finito de rasgos, apropiados al tipo
• Un valor específico, perteneciente a un tipo apropiado puede asociarse a cada rasgo de una FS
• Ejemplos• ALE, Carpenter
• Alep, Alshawi
• AMALIA, Wintner
• CUF, Dörre
• TFS, Zajac
PLN parsing unificación 45
Análisis con gramáticas de rasgos con tipos 2
bot
list
e-list
atom
ne-list hd: bot tl: list
a b
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 []
Ejemplo de jerarquía de tipos en ALE
PLN parsing unificación 46
Análisis con gramáticas de rasgos con tipos 3
• Compiling Type structure T• transitive closure of subsumption in T
• Wharshall´s algorithm
• least upper bounds for each pair of consistent types
• Appropriateness• appropriate features for each type
• appropriate value for each feature
• Compiling basic operations• Compiling descriptions• Compiling grammar and programs
Parsing con gramáticas ALE
PLN parsing unificación 47
Análisis con gramáticas de rasgos con tipos 4
Tag
foo
V1
V2
Vn
...
Siguiendo a Carpenter,1993una FS se representa como
Tag - foo (V1,...Vn)donde
Tag reference pointer- prolog operatorfoo type of the structure
Implementing FS in ALE
PLN parsing unificación 48
Análisis con gramáticas de rasgos con tipos 5
El siguiente tipo de código se producirá:
Comunicación de que una FS pertenece a determinado tipo(e.g. una list es una ne_list):
(e.g. un sign es un word):
Compilación de las operaciones básicas
unify(T-ne_list(H, R), T-ne_list(H2, R2):-
unify(H, H2), unify(R, R2).
add_to(ne_list, Tag-TVs):- add_to_ne_list(TVs, Tag).
add_to_ne_list(list, _-ne_list(T1-bot, T2-bot):-
add_to_atom(bot,T1), add_to_atom(bot,T2).
add_to_word(sign(T1-Phon, Synsem, QSt), _-word(T1-Phon, Synsem, QSt)):-
add_to_singleton_phon_list(Phon,T).
PLN parsing unificación 49
Amalia 1
Abstract MAchine for LInguistic Applications
Wintner, 1997Wintner,Francez, 1996, 1999
Abstract Feature Structures
unifying two TFS: a program and a query => new TFS
Grammar rules and lexicon entries follow ALE format
The main difference between AMALIA and abstract machines devised forvariants of Prolog (e.g. ALE) is that AMALIA is not based on resolution buton parsing with respect to an input grammar.
PLN parsing unificación 50
Amalia 2
Ejemplo de jerarquía de tipos
bool
yes no
signsyn: catsem: anim
birdwings: yes
beast adj n v
animprd: bool
cat
mythf: bool
anim sub[bird,beast] intro[prd:bool]
PLN parsing unificación 51
Amalia 3
Ejemplo de reglas
:sem
: syn
:sem
: syn
:sem
: syn n
sign
adj
sign
anim
n
sign
:sem
: syn
:sem
: syn
:sem
: syn v
sign
n
sign
anim
v
sign
Ejemplo lexicon
beast
n
sign
:sem
: syn : horses
beast
v
sign
:sem
: syn : ran
yes
bird
v
sign
:wings:sem
: syn :flew
yes
bird
adj
sign
:wings:sem
: syn : winged
PLN parsing unificación 52
Amalia 4
Address 1 2 3 4 5 6 7 8 Tag STR REF REF STR REF REF STR STR contents sign 4 5 n myth 8 8 yes
Representación en memoria de una FS
e.g. TFS sign(myth(yes,),n)
Flattening FS:
Linear representation Set of equations sign(myth(jyes, ),n) X1 = sign(X2, X3)
X2 = n X3 = myth(X4, X4) X4 = yes
:wings
:f:sem
: syn
yes
myth
n
sign
PLN parsing unificación 53
Amalia 5
compiled code for the query sign(myth(yes,),n)
Set of equations Compiled code X1 = sign( X2, X3) X2 = n X3 = myth( X4, X4) X4 = yes
put_node sign/2, X1
put_arc X1, 1, X2
put_arc X1, 2, X3 put_node n/0, X2
put_node myth/2, X3
put_arc X3, 1, X4
put_arc X3, 2, X4 put_node yes/0, X4
PLN parsing unificación 54
Amalia 6
c[f4:bot] e
a [f1:bot] b [f2:bot] d1 d2
g [f3:d] d
g d a b c e d1 d2 arity appropriateness g d a a a a c c 2 f3:d, f1: b c f3:d, f1: , f2: , f4: e d1 d2
compiling the type hierarchy
least upper bounds (partial)
PLN parsing unificación 55
Amalia 7
A series of abstract machine language functions are generated:e.g. unify_type[t1,t2] with one parameter addr, where addr is the address of some TFSof type t2
unify_type[bird, beast](beast_addr) build_str(myth); % since the LUB is myth build_self_ref; % the value of wings is yet unknown build_var(bool); % the value of f is a new structure return;unify_type[beast, bird](bird_addr) build_str(myth); % since the LUB is myth build_ref 1; % wings is the first feature of bird build_var(bool); % the value of f is a new structure return;
PLN parsing unificación 56
Amalia 8
Compiling a programe.g. sign(myth(yes,),n)
=>X1 = sign(
X2, X3)
X2 = nX3 = myth(
X4, X4)
X4 = yes
get_structure sign/2, X1unify_variable X2 unify_variable X3 get_structure n/0, X2get_structure myth/2, X3unify_variable X4 unify_value X4 get_structure yes/0, X4