WIXLIB

GRAMÁTICAS FORMALESAnálisis,Parsing

EL LENGUAJE NATURAL Y LASGRAMÁTICAS FORMALESU:Universo de todaslas posiblescadenas de textoL:Subconjuntoespecífico queconformapalabras consignificado Gramáticaformal quedescribe unlenguajeformalG(L):

EL LENGUAJE NATURAL Y LASGRAMÁTICAS FORMALESU:Universo de todaslas posiblescadenas de textoL:Subconjuntoespecífico queconformapalabras consignificadoLN:Evoluciona, seadapta, tieneexcepciones ensu definiciónformalG(L):Gramáticaformal quedescribe unlenguajeformal

EL LENGUAJE NATURAL Y LASGRAMÁTICAS FORMALESU:Universo de todaslas posiblescadenas de textoL:Subconjuntoespecífico queconformapalabras consignificadoG’(L):Gramáticasformales queaproximen unlenguaje naturalLN:Evoluciona, seadapta, tieneexcepciones ensu definiciónformal

SIMPLIFICACIÓNLos algoritmos de análisis de lenguaje natural no se puedenbasar en gramáticas que tengan características fijas definiblescomo las de los lenguajes de programación. PERO Algunos formalismos gramaticales son muy difíciles de analizarcomputacionalmente, por lo que, se usa una aproximación librede contexto incluso si la estructura no es libre de contexto paraobtener una primera simplificación.Un rio de sangre, Violeta Parra.

JERARQUÍA LENGUAJESDE CHOMSKY Tipo 3: (regulares, RG) Tienen la estructura más sencilla. No describen lenguajes sino mor fologías de los componentes dellenguaje (tokens). Tipo 2: (libres del contexto, CFG) Se restringe la liber tad de la formación de reglas gramaticales. El significado de una palabra es totalmente independiente de su posiciónen la frase. Describen completamente lenguajes formales (ar tificiales). Tipo 1: (sensibles al contexto) Introducen algunas limitaciones en la formación de frases. El significado de las palabras depende de su posición en la frase(contexto). Muchos lenguajes ar tificiales y naturales per tenecen realmente a estegrupo, aunque gran par te de las reglas de su gramática pueden reducirseal tipo 2 más práctico. Tipo 0: (recur sivos) A estas gramáticas no se les impone restricción alguna. El conjunto de los lenguajes de tipo 0 coincide con todos los posibles. Computacionalmente más complejos de expresar y Da de Chomsky

GRAMÁTICAS, LENGUAJES YMÁQUINAS

MAPA CONCEPTUALJERARQUÍA DE CHOMSKY

PROPIEDADES DE LAS GRAMÁTICAS

FASES DEL ANÁLISIS Análisis léxico: Identificación de tokens (unidades léxicas). Gramáticas de tipo 3. Indicado mediantes Expresiones Regulares. Análisis sintáctico: Identificación de sentencias.Creación de estructura de árbol.Gramáticas de tipo 2 (o 1 simplificadas).Indicado mediante reglas Backus-Naur Form (BNF).

ANALIZADORES LÉXICOS Los interpretas autómatas finitos. Se describen con expresiones regulares.Práctica: Instalar Ultrapico Expresso (solo Windows) http://www.ultrapico.com/Expresso.htm Alternativa en la web: http://gskinner.com/RegExr/

ANALIZADORES SINTÁCTICOSUn analizador sintáctico determina si una entrada puede serderivada desde el símbolo inicial, usando las reglas de unagramática formal. Existen dos aproximaciones: Descendente LL(k) (Top-Down-Parser): Empiezan con el símbolo inicial para alcanzar la entrada, Ej: ANTLR,JavaCC. Ascendente LR, SLR, LALR (Bottom-Up-Parser): Empezar con la entrada para alcanzar el símbolo inicial, Ej: GoldParser, Yacc. Mixto (Earley, CYK, Chart): (demo CYK) Es un Top-Down con momentos de Bottom-Up, Ej: NLTK.

TOP-DOWN EN PROFUNDIDAD

TOP-DOWN EN ANCHURA

BOTTOM-UP

COMPARACIÓN DE APROXIMACIONES Top-Down (LL) Ventajas: No explora árboles que pueden llegar a ser S. Los subárboles encajan entre si bajo S. Desventajas: Se pueden explorar demasiados árboles de manera infructuosa. Puede “divagar” en el proceso. Bottom-Up (LR) Ventajas: Todos los árboles explorados son consecuentes con la entrada. Suele ser más directo. Desventajas: Se realiza la exploración aun cuando es imposible alcanzar S. Se pueden desarrollar subárboles que puede que no acaben por combinar.

COMPARACIÓN DE APROXIMACIONES Left-Corner Ventajas: Ambas aproximaciones puras tienen deficiencias. Soluciona muchos de sus problemas. Desventajas: Recursividad por la izquierda (S- S and S, NP- NP PP) Parsing sobre el mismo subarbol varias pasadas. Ambigüedad. Dinámicos (Chart, EARLEY, ) Ventajas: Son Top-Down con lef t-corner o Bottom-up parciales. Evita repetir la misma pasada (par sing sobre el mismo subárbol). Reduce tiempo de proceso. Desventajas: Es un reconoced or no un par ser porque los pasos que realiza noapuntan a las reglas aplicadas.

PARSING SOBRE MISMO SUBÁRBOL

AMBIGÜEDAD [Old men] and women vs. Old [men and women] Se desambigüiza con métodos estadísticos, semánticos oconocimiento pragmático del contexto.

GRAMÁTICAS LIBRES DE CONTEXTOPROBABILÍSTICAS (PCFG) Argumenta cada regla con una probabilidad condicionada A α (p)P(A α) p representa la probabilidad de que dado un no terminal Apueda ser expandido con la secuencia α. La probabilidad del árbol de derivación es el producto de lasprobabilidades de las reglas usadas en su tic context-free grammarhttp://web.media.mit.edu/ havasi/MAS.S60/pcfg.pdf

GRAMÁTICAS LIBRES DE CONTEXTOPROBABILÍSTICAS (PCFG)

EJEMPLO P(T l ) 0.50 3.78*10 -7 P(T r ) 0.50 4.32*10 -7

GRAMÁTICAS LIBRES DE CONTEXTOPROBABILÍSTICAS (PCFG)¿Cuál es la probabilidaddel árbol de derivaciónalternativo?

GRAMÁTICAS LIBRES DE CONTEXTOPROBABILÍSTICAS (PCFG)

GRAMÁTICAS LIBRES DE CONTEXTOPROBABILÍSTICAS (PCFG)

S NP VPS Aux NP VP0.80.1S VP0.1NP Pronoun0.2NP Proper-Noun0.2NP Det NominalNominal Noun0.60.3Nominal Nominal Noun 0.2Nominal Nominal PP0.5VP Verb0.2VP Verb NPVP VP PPPP Prep NP0.50.31.0Chomsky Normal FormOriginal GrammarEJEMPLO DE GRAMÁTICAPROBABILÍSTICAS NP VPS X1 VPX1 Aux NPS book include prefer0.01 0.004 0.006S Verb NPS VP PPNP I he she me0.1 0.02 0.02 0.06NP Houston NWA0.16.04NP Det NominalNominal book flight meal money0.03 0.15 0.06 0.06Nominal Nominal NounNominal Nominal PPVP book include prefer0.1 0.040.06VP Verb NPVP VP PPPP Prep NP0.80.11.00.050.030.60.20.50.50.31.0

PROBABILISTIC CKY PARSERBookS :.01, VP:.1,Verb:.5Nominal:.03Noun:.1theflight through HoustonNoneDet:.6NP:.6*.6*.15 .054Nominal:.15Noun:.527

PROBABILISTIC CKY PARSERBookS :.01, VP:.1,Verb:.5Nominal:.03Noun:.1theflight through HoustonNoneVP:.5*.5*.054 .0135Det:.6NP:.6*.6*.15 .054Nominal:.15Noun:.528

PROBABILISTIC CKY PARSERBookS :.01, VP:.1,Verb:.5Nominal:.03Noun:.1theflight through HoustonS:.05*.5*.054 .00135NoneDet:.6VP:.5*.5*.054 .0135NP:.6*.6*.15 .054Nominal:.15Noun:.529

PROBABILISTIC CKY PARSERBookS :.01, VP:.1,Verb:.5Nominal:.03Noun:.1theflight through HoustonS:.05*.5*.054 .00135NoneDet:.6VP:.5*.5*.054 None .0135NP:.6*.6*.15 .054NoneNominal:.15Noun:.5NonePrep:.230

PROBABILISTIC CKY PARSERBookS :.01, VP:.1,Verb:.5Nominal:.03Noun:.1theflight through HoustonS:.05*.5*.054 .00135NoneDet:.6VP:.5*.5*.054 None .0135NP:.6*.6*.15 .054NoneNominal:.15Noun:.5NonePrep:.2PP:1.0*.2*.16 .032NP:.16PropNoun:.831

PROBABILISTIC CKY PARSERBookS :.01, VP:.1,Verb:.5Nominal:.03Noun:.1theflight through HoustonS:.05*.5*.054 .00135NoneDet:.6VP:.5*.5*.054 None .0135NP:.6*.6*.15 5*.032 .0024PP:1.0*.2*.16 .032NP:.16PropNoun:.832

PROBABILISTIC CKY PARSERBookS :.01, VP:.1,Verb:.5Nominal:.03Noun:.1theflight through HoustonS:.05*.5*.054 .00135NoneDet:.6VP:.5*.5*.054 None .0135NP:.6*.6*.15 4 .000864Nominal:.5*.15*.032 .0024PP:1.0*.2*.16 .032NP:.16PropNoun:.833

PROBABILISTIC CKY PARSERBookS :.01, VP:.1,Verb:.5Nominal:.03Noun:.1theflight through HoustonS:.05*.5*.054 .00135NoneDet:.6VP:.5*.5*.054 None .0135S:.05*.5*.000864 .0000216NP:.6*.6*.15 .054NP:.6*.6*.0024 *.15*.032 .0024PP:1.0*.2*.16 .032NP:.16PropNoun:.834

PROBABILISTIC CKY PARSERBookS :.01, VP:.1,Verb:.5Nominal:.03Noun:.1theflight through HoustonS:.05*.5*.054 .00135NoneDet:.6VP:.5*.5*.054 None .0135NP:.6*.6*.15 032 .00001296S:.0000216NP:.6*.6*.0024 .000864Nominal:.5*.15*.032 .0024PP:1.0*.2*.16 .032NP:.16PropNoun:.835

PROBABILISTIC CKY PARSERBookS :.01, VP:.1,Verb:.5Nominal:.03Noun:.1theflight through HoustonS:.05*.5*.054 .00135NoneDet:.6S:.0000216VP:.5*.5*.054 None .0135NP:.6*.6*.15 4 .000864Pick most probableparse, i.e. take max tocombine probabilitiesof multiple derivationsof each constituent ineach cell.Nominal:.5*.15*.032 .0024PP:1.0*.2*.16 .032NP:.16PropNoun:.836

PCFG: CUANDO LO EVIDENTE NO LOES TANTO

LEXICAL PGFG (LPCFG): PROB. COND.A PAPELES TEMÁTICOS (FILLMORE)

PCFG: TREE BANKSMediante aprendizaje supervisado, pasamos lasreglas de la gramática por un conjunto desentencias de aprendizaje y estimamos losparámetros de probabilidad, con cierto suavizado.Tree BankSNPVPJohnVNPPPput the dog in the penSNPJohnVPVNPPPput the dog in the pen.SupervisedPCFGTrainingS NP VPS VPNP Det A NNP NP PPNP PropNA εA Adj APP Prep NPVP V NPVP VP PPEnglish0.90.10.50.30.20.60.41.00.70.3

ESTIMACIÓN DE PROBABILIDADESCONDICIONADAS Dado un conjunto de sentencias, buscamos la gramática quemaximice la probabilidad de que haya sido generada por ellamisma.count( )count( )P( ) count( ) count( )

TRADUCCIÓN (MT)Se realiza a nivel de:1. Palabra: Yo lo haré mañana - I will do it tomorrow2. Frase: Yo lo haré mañana - I will do it tomorrow3. Árbol: Busca que la unidad léxica mantenga el mismo papelsintáctico. Lo visto en el capítulo,4. Significado: Doing - do verb (does; doing; past did; pastpar t. done). Perform or carry out (an action), work on(something) to bring it to completion or to a required state .Busca la semántica de la unidad léxica para comprender sufunción así identificar las papeles que intervienen.

SUMARIO EN LABIBLIOGRAFÍAJ u r a f s ky,D . &M a r t i n , J . ( 2 0 07 ) :Speech andL a n g u a ge P r o c e s si n gA n I n t r o d u c t i o n toSpeech Recognition,ComputationalLinguistics andNatural LanguageP r o c e s si n g ,S e c o n d E d i t i o n , N ewYo r k , Pe a r s o n .

SUMARIO CAPÍTULO 12 In many languages, groups of consecutive words act as a group or a constituent, which can bemodeled by c o ntext-free g rammars (also known as phrase-structure grammars). A context-free grammar consists of a set of rules or productions, expressed over a set of nont e r m i n a l s y m b o l s a n d a s e t o f t e r m i n a l s y m b o l s . F o r m a l l y, a p a r t i c u l a r c o n t e x t - f r e e l a n g u a g e i s t h es e t o f s t r i n g s w h i c h c a n b e d e r i v e d f r o m a p a r t i c u l a r c o n t e x t - f r e e g r a m m a r. A g enerative g rammar is a traditional name in linguistics for a formal language which is used tomodel the grammar of a natural language . There are many sentence-level g rammatical c o nstructions in English; declarative, imperative, yes no-question, and wh-question are four ver y common types, which c an b e mo deled w ith c o ntext -freerules. An English noun phrase can have determiners , numbers, quantifiers, and adjective phrasespreceding the head noun, which can be followed by a number of postmodifiers; gerundive,infinitives, and past participial are common possibilities. Tr e e b a n k s o f p a r s e d s e n t e n c e s e x i s t f o r m a n y g e n r e s o f E n g l i s h a n d f o r m a n y l a n g u a g e s . Tr e ebanks can be searched using tree -search tools. Any context-free grammar can be conver ted to C ho msky no rmal form , in which the right-hand-sideof each rule has either two non -terminals or a single terminal .