Análisis del lenguaje natural

En lenguaje informático o NLP , el parsing ( parsing sintáctico ) se refiere al proceso de análisis automatizado de una cadena de palabras, que representa una frase, para obtener la relación entre la coexistencia de estas palabras a través de un árbol de sintaxis . Al comenzar desde texto plano, este último debe haber sido segmentado en unidades léxicas de antemano ( tokenización ). Habitualmente se realiza un análisis léxico ( lematización , análisis morfosintáctico ...) antes del análisis sintáctico propiamente dicho, con el fin de identificar las unidades léxicas y sus propiedades. El resultado del análisis se usa típicamente como base en el análisis semántico , construyendo una representación del significado del texto, o directamente en aplicaciones como la corrección gramatical .

Para un sistema de respuesta a preguntas o búsqueda de información , sería difícil, por ejemplo, responder correctamente a la pregunta "¿qué obras fueron escritas por autores francófonos antes de 1900?" "Sin reconocer el tema" obras ", porque en particular debe entenderse que el usuario quiere una lista de obras y no una lista de autores.

El proceso de análisis puede basarse en una gramática formal y / o utilizar métodos estadísticos .

Histórico

El análisis se remonta a los inicios de la investigación de la PNL, ya que uno de los primeros algoritmos de análisis fue introducido por Victor Yngve en 1955, incluso antes del desarrollo de la teoría del lenguaje formal por Noam Chomsky en 1956. Por lo tanto, los analizadores sintácticos creados se basarán en gramáticas formales, particularmente aquellas llamadas fuera de contexto o tipo 2 . Entre otros, John Cocke inventó un algoritmo de programación dinámica en 1960, que luego fue formalizado por T. Kasami (1965) y DH Younger (1967): el famoso algoritmo CKY , que analiza una secuencia en tiempo cúbico utilizando gramáticas de forma normal de Chomsky . Esta última es de tipo mixto, es decir combinando las estrategias bottom-up y top-down, individualmente menos efectivas.

Al mismo tiempo, en los años sesenta, surgieron otros formalismos dedicados al análisis sintáctico, entre ellos gramáticas de dependencia inspiradas en Lucien Tesnière (1959) y formalizadas sobre todo por David Hays (1960). Poco después de N. Chomsky, John Backus (1959) y Peter Naur (1960) reinventaron de forma independiente gramáticas libres de contexto en su descripción del lenguaje ALGOL , dando lugar a la famosa forma Backus-Naur . En 1968, Jay Earley inventó el primer algoritmo de análisis de tiempo cúbico para todas las gramáticas libres de contexto (no necesariamente en forma normal). Al mismo tiempo, R. Kaplan y M. Kay generalizaron el algoritmo CKY a todas las gramáticas libres de contexto para convertirlo en el analizador de gráficos , utilizando un gráfico. Entre los algoritmos similares a los dos anteriores, también podemos citar el analizador de la esquina izquierda , en referencia al primer símbolo de la parte derecha de una regla de producción.

Muchos otros formalismos se desarrollaron durante los años 1970-1980, incluidas las redes de transición aumentadas (ATN) y las gramáticas de unificación (gramáticas basadas en restricciones ). Una representación en las dependencias de este último fue propuesta originalmente por H. Maruyama. Durante la década de 1990, los desarrollos se centraron principalmente en los métodos estadísticos, incluido un trabajo significativo sobre gramáticas probabilísticas libres de contexto (PCFG), uno de los modelos más influyentes de análisis estadístico, que se basa en una gramática formal, incluidos los principales problemas son la ignorancia de la información semántica y la hipótesis de independencia del apego estructural de las frases. Algunos enfoques más recientes han permitido mejorar las debilidades de los PCFG mediante la lexicalización de la gramática o el uso de un conjunto más preciso de símbolos no terminales, entre otros. Del lado de la representación en dependencias, Jason Eisner propuso el primer algoritmo estocástico de influencia.

Para los métodos que no requieren la intervención de una gramática, los modelos se inducen directamente a partir de datos anotados ( corpus ), lo que facilita la portabilidad de los sistemas a nuevos lenguajes o dominios. Aunque esta última posibilidad se utiliza principalmente en la actualidad, los métodos basados en gramáticas todavía se utilizan cuando no hay suficientes datos anotados necesarios para el funcionamiento de los métodos supervisados. Cabe señalar de paso que una gramática puede extraerse muy bien de datos lingüísticos; los métodos basados en la gramática ( análisis basado en gramática ) y los guiados por datos ( análisis basado en datos ) no son mutuamente excluyentes. La categorización sugerida de métodos estadísticos de análisis se usa ampliamente en el campo de la PNL.

Dificultades

Analizar es una tarea no trivial, principalmente debido a la ambigüedad inherente del lenguaje y su diversidad. Se dice que un enunciado es ambiguo si se le pueden asociar varias estructuras lingüísticas.

A continuación, se muestran algunos ejemplos de ambigüedades estructurales :

"John vio al hombre en la colina con un telescopio"

En esta oración, el adjunto de la frase preposicional es ambiguo, y no se sabe si John usó un telescopio para ver al hombre, o si John vio a un hombre él mismo usando un telescopio.

"¿A quién le prometiste escribir?" "

La pregunta anterior podría parafrasearse de dos maneras: "¿A quién prometiste escribir?" O "¿A quién prometiste escribir?" "; no se sabe si la persona en cuestión le escribirá a alguien, o si le ha prometido a alguien escribir (algo).

Vínculo con el análisis de un lenguaje formal

Incluso si el objetivo de analizar un lenguaje determinista formal (por ejemplo, lenguaje de programación ) es idéntico al de analizar el lenguaje natural, la tarea es mucho más difícil en el segundo caso.

Primero, la capacidad generativa de una gramática - su poder - es mucho menor en el caso de los lenguajes de computadora, porque estos deben ser estrictamente inequívocos y rápidamente analizables (por lo tanto, la gramática está restringida). En comparación, una gramática destinada al lenguaje natural debe, por ejemplo, permitir expresar dependencias entre palabras que están muy separadas unas de otras; por tanto, es más complejo.

En segundo lugar, debido a que el lenguaje natural adolece de ambigüedad estructural, en cada paso del análisis es probable que se apliquen varias reglas gramaticales. Por lo tanto, una oración como "Juan vio al hombre [en la colina] [con un telescopio] [acompañado de su hija] [...]" hará que el número de sus posibles análisis aumente exponencialmente con el número de componentes agregados. . Por cierto, esta es una de las razones que ha impulsado el desarrollo de métodos estadísticos.

La última diferencia notable está en la validez de la secuencia de entrada: un lenguaje de programación tiene un número finito de construcciones válidas, mientras que es ilimitado para un lenguaje natural. Por tanto, en el caso de la PNL existe la imposibilidad de realizar un análisis, error que no se debe necesariamente a una gramática inadecuada, sino posiblemente a un error gramatical, un error tipográfico, una palabra desconocida, etc.

Además de estas disimilitudes caricaturescas, existen muchas otras, como la delimitación estricta de "oraciones" (enunciados, bloques) y palabras en el caso de lenguajes formales con caracteres bien definidos.

Métodos clásicos

Métodos puramente gramaticales

La mayoría de los primeros sistemas de análisis se basan exclusivamente en una gramática libre de contexto ( gramática libre de contexto ) para generar estructuras sintácticas correctas, aunque este tipo de gramática no es suficiente para generar el lenguaje natural como un todo. Juntos, es necesario tener un algoritmo que dicte cómo se producirán estas estructuras de manera eficiente. En este contexto, se usa ampliamente el algoritmo de programación dinámica CKY , en el que los subproblemas, mantenidos en una matriz, están representados por árboles de sintaxis parcial enraizados en las frases de la oración de entrada. Gracias a la naturaleza independiente del contexto de las gramáticas, es posible reutilizar una subestructura en derivaciones posteriores que lo requieran, haciendo posible la programación dinámica. Los algoritmos que compiten con CKY son los de Earley y el análisis de gráficos .

Métodos con la ayuda de estadísticas

El problema de los algoritmos asimilados a CKY es su incapacidad para resolver ambigüedades estructurales (ver apartado de “ dificultades ”), aunque es posible detectarlas. Para superar esta carencia, es necesario agregar un componente estadístico al modelo; si cada regla va acompañada de una probabilidad , basta con seleccionar la que tenga mayor probabilidad en caso de ambigüedad. Como tal, el formalismo más comúnmente utilizado es la gramática libre de contexto probabilística (PCFG). Existe una versión probabilística del algoritmo CKY, descrito sobre todo por H. Ney. La inferencia exacta requiere un tiempo en , donde está el número de reglas gramaticales. ${\ Displaystyle {\ mathcal {O}} (n ^ {3} \ cdot | R |)}$ ${\ Displaystyle | R |}$

Sin embargo, el modelo PCFG es relativamente limitado en su capacidad para sobresalir, porque impone fuertes supuestos de independencia. El principal problema es que la probabilidad de una regla en particular es independiente del contexto en el que se produce; por ejemplo, la probabilidad de que un sintagma nominal se extienda a un pronombre (regla ) permanece constante, que este sintagma se encuentre en la posición de sujeto u objeto, mientras que la primera posibilidad es mucho más frecuente para ciertos lenguajes. Por otro lado, si dos estructuras diferentes usan exactamente las mismas reglas, obtendrán la misma probabilidad; sin embargo, para la misma oración (por lo tanto, las mismas reglas), a menudo hay una estructura que se prefiere a otra (cuando existen varias posibilidades), algo que no se transmite por el formalismo del PCFG. ${\ Displaystyle {\ text {NP}} \ longrightarrow {\ text {Pron}}}$

Se propusieron varios modelos para resolver los problemas mencionados anteriormente. Uno de los más influyentes es el de Michael Collins , llamado LPCFG o, en ocasiones , dirigido por la cabeza , que consiste en lexicalizar la gramática mediante la elección de un elemento preponderante ( regla principal ) para cada regla de la gramática. De esta manera, cada nodo padre del árbol de sintaxis es "parametrizado" por una palabra de la oración; por ejemplo, podría convertirse en una regla para un PCFG si "el perro" es parte de la oración a analizar. Como es la consideración primordial para esta regla, el padre hereda la palabra "perro". ${\ Displaystyle [{\ text {NP}} \ longrightarrow {\ text {DT}} \ quad {\ text {NN}}]}$ ${\ displaystyle [{\ text {NP (perro)}} \ longrightarrow {\ text {DT (el)}} \ quad \ mathbf {NN} {\ text {(perro)}}]}$ ${\ Displaystyle {\ text {NN}}}$ ${\ Displaystyle {\ text {NP}}}$

La anotación de los nodos no terminales de un PCFG, conocida como anotación padre , también ha sido muy exitosa para el análisis de componentes, porque la precisión de los sistemas que implementan esta técnica es similar a los basados en LPCFG, con menor complejidad. Tal anotación podría ser, por ejemplo, si compone una frase preposicional. ${\ Displaystyle [{\ text {NP}} ^ {\ text {PP}} \ longrightarrow {\ text {DT}} \ quad {\ text {NN}}]}$ ${\ Displaystyle {\ text {NP}}}$

Otra solución a la falta de sensibilidad estructural de los PCFG es el análisis sintáctico orientado a datos (DOP) establecido por Remko Scha y Rens Bod. El principio es analizar oraciones combinando fragmentos de análisis de oraciones cuya estructura se conoce, como los que provienen de un corpus.

Existen dos clases de modelos probabilísticos: los conocidos como generativos , como los LPCFG, y los conocidos como discriminantes (consulte la sección “ modelos de análisis estadístico ” para obtener más detalles).

métodos de estadística

Beneficios de las estadísticas

Avec l'approche classique, l'analyse d'une phrase peut donner lieu à des millions d'arbres syntaxiques possibles en raison de la grande taille de la grammaire, avec l'impossibilité de choisir lequel reflète au mieux la structure de la phrase en pregunta. Si se agregan restricciones a esta gramática para restringir el número de análisis posibles, algunas de las oraciones analizadas corren el riesgo de no tener una estructura correspondiente. El enfoque estadístico tiene la ventaja de tolerar millones de análisis, al tiempo que tiene la posibilidad de seleccionar el mejor en un tiempo razonable; como tal, a menudo es necesario reducir el espacio de búsqueda a lo largo del proceso de análisis, eliminando análisis parciales poco probables lo antes posible.

Hoy en día, las gramáticas (por sí solas) ya casi no se utilizan, y los enfoques en el campo de la PNL se basan principalmente en técnicas de aprendizaje automático .

Además, como la formalización de los fenómenos lingüísticos es laboriosa, las técnicas estadísticas han aportado la enorme ventaja de extraer el conocimiento lingüístico directamente de muestras (reales) de datos. Y si la construcción de un corpus ( banco de árboles ) es más tediosa que la construcción de una gramática, la primera tiene la ventaja de ser reutilizable en otros sistemas (incluidos los analizadores morfosintácticos), lo que explica en parte el desinterés en lo que respecta a las gramáticas. Además, los datos contienen estadísticas implícitamente y la evaluación de un sistema es fácil. Tenga en cuenta que una gramática puede extraerse muy bien de datos lingüísticos; Los métodos basados en gramáticas ( análisis basado en gramática ) y los guiados por datos ( análisis basado en datos ), hoy en día en la mayoría, no son, por lo tanto, mutuamente excluyentes.

Si bien se utilizan técnicas estadísticas para eliminar la ambigüedad, si es necesario, el proceso de análisis, el espacio de búsqueda solo puede explorarse en su totalidad en muy raras ocasiones, y es necesario limitarlo por razones de eficiencia.

Modelos de análisis estadístico

Podemos representar un analizador sintáctico mediante una función , donde es el conjunto de posibles entradas, sabiendo que representa una secuencia de entrada , y es el conjunto de representaciones sintácticas admisibles. Tenga en cuenta que la naturaleza de la representación de un análisis es específica de la teoría utilizada, al igual que su criterio de admisibilidad. ${\ Displaystyle f: {\ mathcal {X}} \ to {\ mathcal {Y}}}$ ${\ mathcal {X}}$ ${\ Displaystyle {\ boldsymbol {x}} \ in {\ mathcal {X}}}$ ${\ displaystyle {\ boldsymbol {x}} = (t_ {0}, t_ {1}, \ dots, t_ {n})}$ ${\ mathcal {Y}}$ ${\ displaystyle {\ boldsymbol {y}} \ in {\ mathcal {Y}}}$

Conceptualmente, un modelo de análisis se puede dividir en dos partes:

un componente generativo , que hace coincidir una entrada con un conjunto de análisis de candidatos , por lo tanto ; ${\ Displaystyle \ mathrm {GEN}}$ ${\ boldsymbol {x}}$ ${\ displaystyle \ {{\ boldsymbol {y}} _ {1}, {\ boldsymbol {y}} _ {2}, \ dots, {\ boldsymbol {y}} _ {| {\ mathcal {Y}} | } \}}$ ${\ displaystyle \ mathrm {GEN} ({\ boldsymbol {x}}) \ subseteq {\ mathcal {Y}}, {\ boldsymbol {x}} \ in {\ mathcal {X}}}$
un componente evaluativo , clasificando los análisis de los candidatos de acuerdo con una puntuación numérica asignada, por lo tanto . ${\ Displaystyle \ mathrm {EVAL}}$ ${\ displaystyle \ mathrm {EVAL} ({\ boldsymbol {y}}) \ in \ mathbb {R}, {\ boldsymbol {y}} \ in \ mathrm {GEN} ({\ boldsymbol {x}})}$

Los dos componentes generalmente tienen parámetros cuyos valores serán estimados estadísticamente, comenzando por el análisis de datos representativos, llamado conjunto de entrenamiento , con el fin de hacer un buen estimador del corresponsal. Esta es la etapa de aprendizaje modelo, que puede ser supervisada o no supervisada (a veces semi-supervisada ); El aprendizaje supervisado requiere que el análisis correcto esté presente en los datos. Por lo tanto, toda la dificultad de este paso es utilizar correctamente la evidencia parcial, contenida en los datos, para crear una distribución de probabilidad que refleje la realidad lo más fielmente posible. A partir de la función , inferida cuando se aprende el modelo, el segundo paso consiste en ordenar eficientemente los análisis candidatos para una oración de entrada dada (no publicada): este es el problema de inferencia . Este último puede ser exacto o aproximado, dependiendo de las garantías que brinde el algoritmo utilizado. ${\ Displaystyle f ({\ boldsymbol {x}} _ {i})}$ ${\ displaystyle {\ boldsymbol {y}} _ {i}}$ $F$

A menudo es necesario encontrar un compromiso justo entre la complejidad del modelo y la falta de precisión de las soluciones generadas. De paso, tenga en cuenta el hecho de que el conjunto es probablemente muy grande y que cada uno es un objeto con una rica estructura interna; este hallazgo contrasta con un simple problema de clasificación, para el cual sería mucho menor. Los sistemas que utilizan un algoritmo de aprendizaje supervisado son mucho más comunes porque son mucho más eficientes. ${\ Displaystyle \ mathrm {GEN} ({\ boldsymbol {x}})}$ ${\ Displaystyle {\ boldsymbol {y}} _ {i} \ in \ mathrm {GEN} ({\ boldsymbol {x}})}$ ${\ Displaystyle \ mathrm {GEN} ({\ boldsymbol {x}})}$

Además, dos grandes clases de modelos se oponen en el aprendizaje automático, no necesariamente vinculados a los componentes generativos y evaluativos mencionados anteriormente: la primera posibilidad, denominada generativa , es ver el proceso de análisis como un sistema de reescritura probabilística, donde el objetivo es producir una (o más) estructura (s) de acuerdo con una entrada determinada; en cada paso, se deben elegir las mejores alternativas para obtener la estructura más probable al final del análisis. Aquí, el objetivo es maximizar la probabilidad conjunta , cualquiera que sea y , modelando y , luego recombinándolos con la regla de Bayes (caso de PCFG). La segunda posibilidad, llamada discriminante , es ver la gramática como un conjunto de restricciones sobre las estructuras correctas y la secuencia de entrada como una restricción sobre la posición de las palabras; El análisis debe entonces resolver estas restricciones, luego seleccionar la estructura sintáctica más probable entre las que mejor se ajustan a las restricciones. En este caso, intentamos modelar la probabilidad condicional directamente a partir de los datos. Nuevamente, los dos enfoques pueden combinarse secuencialmente ( reordenando ). ${\ displaystyle P ({\ boldsymbol {x}}, {\ boldsymbol {y}})}$ ${\ Displaystyle {\ boldsymbol {x}} \ in {\ mathcal {X}}}$ ${\ displaystyle {\ boldsymbol {y}} \ in {\ mathcal {Y}}}$ ${\ displaystyle P ({\ boldsymbol {x}} | {\ boldsymbol {y}})}$ ${\ displaystyle P ({\ boldsymbol {y}})}$ ${\ displaystyle P ({\ boldsymbol {y}} | {\ boldsymbol {x}})}$

Modelos generativos

La derivación de la estructura sintáctica está modelada por un proceso estocástico para el cual cada paso depende de eventos que han surgido en el pasado (histórico). La forma general de tales modelos, inicialmente mencionada por G. Leech, es la siguiente:

y=⟨D1,D2,...,Dmetro⟩{\ displaystyle {\ boldsymbol {y}} = {\ big \ langle} d_ {1}, d_ {2}, \ dots, d_ {m} {\ big \ rangle}} ${\ displaystyle {\ boldsymbol {y}} = {\ big \ langle} d_ {1}, d_ {2}, \ dots, d_ {m} {\ big \ rangle}}$ PAG(y)=∏I=1metroPAG(DI|Φ(D1,...,DI-1)){\ Displaystyle P {\ big (} {\ boldsymbol {y}} {\ big)} = \ prod _ {i = 1} ^ {m} P {\ big (} d_ {i} | \ Phi (d_ { 1}, \ dots, d_ {i-1}) {\ big)}} ${\ Displaystyle P {\ big (} {\ boldsymbol {y}} {\ big)} = \ prod _ {i = 1} ^ {m} P {\ big (} d_ {i} | \ Phi (d_ { 1}, \ dots, d_ {i-1}) {\ big)}}$ donde la función define qué eventos históricos se tienen en cuenta. Aunque este suele ser el caso, el componente generativo es un sistema de derivaciones que no está necesariamente limitado por una gramática formal (el modelo de analizador de IDP es un ejemplo). La evaluación se realiza de acuerdo con la probabilidad conjunta, factorizada en probabilidades condicionales. Tenga en cuenta que se reduce a porque, para una estructura dada, la probabilidad es igual a si es la única oración correspondiente a esta estructura; por lo tanto, si genera , o en todos los demás casos. $\ Phi$ ${\ Displaystyle \ mathrm {GEN} ({\ boldsymbol {x}})}$ ${\ Displaystyle \ mathrm {EVAL} ({\ boldsymbol {y}})}$ ${\ displaystyle P ({\ boldsymbol {x}}, {\ boldsymbol {y}})}$ ${\ displaystyle P ({\ boldsymbol {y}})}$ ${\ displaystyle P ({\ boldsymbol {x}} | {\ boldsymbol {y}})}$ $1$ ${\ boldsymbol {x}}$ ${\ displaystyle P ({\ boldsymbol {x}}, {\ boldsymbol {y}}) = P ({\ boldsymbol {y}})}$ ${\ displaystyle {\ boldsymbol {y}}}$ ${\ boldsymbol {x}}$ ${\ displaystyle P ({\ boldsymbol {x}}, {\ boldsymbol {y}}) = 0}$

Los modelos generativos imponen supuestos rígidos de independencia, lo que impacta en la desambiguación (típicamente PCFG). Sin embargo, la adaptación de estos supuestos da modelos más complejos y la inferencia exacta ya no es posible (ver también la sección “ métodos asistidos por estadísticas ”). Básicamente, este tipo de modelo tiene que predecir la siguiente palabra a medida que avanza el análisis, lo que requiere una normalización global en todo el vocabulario y, a menudo, un grupo más grande (si lo hay), de modo que pueda "probar" una gran cantidad de estructuras en el parte de una oración que incluye la palabra predicha. Además, el entrenamiento de modelos generativos busca la mayor parte del tiempo maximizar la probabilidad conjunta de las entradas-salidas del conjunto de entrenamiento; sin embargo, el objetivo del análisis es maximizar la precisión del modelo para oraciones no publicadas. Por estas razones, los modelos discriminatorios se utilizan cada vez más.

Modelos de discriminación local

El objetivo de estos modelos es maximizar la probabilidad de decisiones locales , esperando llegar a la mejor solución global gracias a la sucesión de decisiones óptimas (locales), como modelos generativos basados en una historia:

Aquí, la función representa propiedades / rasgos arbitrarios según el historial de decisiones tomadas

y la entrada ; en otras palabras, definimos una clase de equivalencia para cualquier combinación de historia y entrada. Al emplear métodos de pronóstico en la entrada, algunos analizadores abordan el análisis determinista (predictivo). Para este tipo de modelo, el componente generativo consiste en un proceso incremental (por ejemplo, un autómata), mientras que el componente evaluativo debe ser capaz de asignar un puntaje a una decisión local dada, y combinar estos puntajes en puntajes globales, evaluando una secuencia completa de transiciones.

\ Phi

{\ Displaystyle \ langle d_ {1}, \ dots, d_ {i-1} \ rangle}

{\ boldsymbol {x}}

{\ Displaystyle \ mathrm {GEN} ({\ boldsymbol {x}})}

{\ Displaystyle \ mathrm {EVAL} ({\ boldsymbol {y}})}

A veces, este tipo de modelo se llama "generativo" porque implica supuestos de independencia como modelos verdaderamente generativos - modelando la probabilidad conjunta - pero sobre decisiones locales , no decisiones globales. El enfoque local tiene la ventaja de favorecer la consideración de rasgos característicos útiles para la desambiguación, el principal problema de los verdaderos modelos generativos. Esta categoría de modelos permite obtener analizadores mucho más rápido que los basados en modelos generativos (por ejemplo, del orden de 35x).

Modelos discriminantes

Esta clase de modelos típicamente define la función de evaluación como el producto de un vector de rasgos (características) y un vector de pesos : ${\ displaystyle \ mathbf {f} ({\ boldsymbol {x}}, {\ boldsymbol {y}}) = \ langle f_ {1} ({\ boldsymbol {x}}, {\ boldsymbol {y}}), \ dots, f_ {m} ({\ boldsymbol {x}}, {\ boldsymbol {y}}) \ rangle \ in \ mathbb {R} ^ {m}}$ ${\ Displaystyle {\ boldsymbol {w}} = \ langle w_ {1}, \ dots, w_ {m} \ rangle \ in \ mathbb {R} ^ {m}}$

S(X,y)=F(X,y)⋅w=∑k=1metroFk(X,y)⋅wk{\ displaystyle S ({\ boldsymbol {x}}, {\ boldsymbol {y}}) \; = \; \ mathbf {f} ({\ boldsymbol {x}}, {\ boldsymbol {y}}) \ cdot {\ boldsymbol {w}} \; = \; \ sum _ {k = 1} ^ {m} f_ {k} ({\ boldsymbol {x}}, {\ boldsymbol {y}}) \ cdot w_ {k }} ${\ displaystyle S ({\ boldsymbol {x}}, {\ boldsymbol {y}}) \; = \; \ mathbf {f} ({\ boldsymbol {x}}, {\ boldsymbol {y}}) \ cdot {\ boldsymbol {w}} \; = \; \ sum _ {k = 1} ^ {m} f_ {k} ({\ boldsymbol {x}}, {\ boldsymbol {y}}) \ cdot w_ {k }}$

donde cada uno representa una característica de y , y cada uno cuantifica la importancia de la característica para un análisis óptimo. Si este peso es negativo, la característica sirve para el análisis, mientras que en caso contrario, la característica influye positivamente en el análisis óptimo. La naturaleza de las características

no está limitada; la única restricción es poder codificarlos en formato digital. Por ejemplo, se puede utilizar la puntuación proporcionada por otro analizador como característica, o tener en cuenta la presencia / ausencia de una subestructura.

{\ displaystyle f_ {k} ({\ boldsymbol {x}}, {\ boldsymbol {y}}): {\ mathcal {X}} \ times {\ mathcal {Y}} \ to \ mathbb {R}}

{\ boldsymbol {x}}

{\ displaystyle {\ boldsymbol {y}}}

{\ Displaystyle w_ {k} \ in \ mathbb {R}}

f_ {k}

Por lo tanto, un modelo verdaderamente discriminatorio define una puntuación única en la estructura general de un análisis. La ventaja es poder observar las propiedades

globales de las estructuras sintácticas y poder tener en cuenta (agregar) nuevas restricciones sin alterar la derivación del modelo. Para esta clase, el componente generativo es bastante variable de un sistema a otro, mientras que el componente de evaluación se establece mediante una combinación lineal de características ponderadas, no restringidas por ningún proceso, y cuyos pesos son fijados por un modelo de aprendizaje discriminatorio.

{\ Displaystyle \ mathrm {GEN} ({\ boldsymbol {x}})}

{\ Displaystyle \ mathrm {EVAL} ({\ boldsymbol {y}})}

El inconveniente de este tipo de modelo es la necesidad de volver a analizar el conjunto de entrenamiento en cada iteración, lo que naturalmente consume muchos recursos. Ciertos enfoques, conocidos como reordenamiento , se han contentado con utilizar este tipo de modelo solo para un subconjunto de , obtenido a sí mismo mediante un modelo generativo. Sin embargo, el mejor análisis no se encuentra necesariamente en este último subconjunto, lo que hace que no sea una técnica ideal. Sin embargo, los problemas de eficiencia son menos marcados en el análisis de dependencias que en el de constituyentes, y se utilizan mucho en el primer caso donde la inferencia exacta es incluso posible bajo ciertas condiciones (ver apartado "

métodos basados en gráficos ").

{\ Displaystyle \ mathrm {GEN} ({\ boldsymbol {x}})}

Paradigmas de análisis

Actualmente, la representación más popular de estructuras sintácticas es la de dependencias , debido al buen compromiso entre expresividad y eficiencia de los algoritmos que ofrece, y el rendimiento obtenido para una amplia variedad de lenguajes. Con esta representación, muy a menudo se utilizan modelos probabilísticos discriminantes o discriminantes localmente, a diferencia de la representación en constituyentes , para los que los modelos generativos son más competitivos. Sin embargo, es interesante notar que ciertos sistemas recientes (por ejemplo ) , particularmente potentes, se basan en el ensamblaje de modelos de diferentes tipos (técnica de ensamblaje o combinación de sistemas ).

La gran mayoría de los modelos de análisis de dependencia estadística se pueden clasificar en dos familias:

Los métodos basados en las transiciones ( basado en la transición ) se basan en un autómata de estado finito por lo que es posible generar una estructura sintáctica de una oración dada. A lo largo del análisis, el modelo aprendido debe poder predecir la próxima transición, basándose en el historial de las transiciones, de modo que se pueda encontrar la secuencia óptima de transiciones que conduzca al mejor análisis posible de la oración.
Los métodos basados en gráficos definen un universo de análisis de candidatos para una oración determinada. El aprendizaje se reduce a inducir un modelo capaz de evaluar estos análisis de candidatos en su conjunto; el proceso de análisis debe encontrar la estructura, como su puntaje más alto, correspondiente a la oración de entrada.

En el primer caso, la estrategia es encontrar la mejor solución local (enfoque codicioso ), mientras que en el segundo caso, el razonamiento adquiere la apariencia de una búsqueda exhaustiva . Además, el primer método a veces se denomina análisis sintáctico con reducción de cambios , que recibe su nombre del algoritmo de

análisis sintáctico utilizado por muchas implementaciones. Es un método muy popular debido a su excelente eficiencia: la complejidad del algoritmo de análisis típico es lineal (en relación con el número de palabras en la oración de entrada). En cuanto al segundo método, a veces se encuentra bajo el nombre de análisis sintáctico máximo de árbol de expansión ( MST ), que corresponde al nombre del algoritmo utilizado por el sistema que introdujo esta técnica. En 2015, Jinho Choi et al. estudió el rendimiento de diez analizadores de dependencia competitivos, en detalle y utilizando diferentes métricas. Métodos basados en transiciones

Los modelos basados en transiciones son modelos de discriminación local con aprendizaje discriminante, en el sentido de que solo se extrae de la distribución probabilística la estimación del análisis final , por ejemplo, utilizando una superficie de decisión. Esto contrasta con los modelos condicionales, donde se optimizaría toda

la densidad de probabilidad condicional . Suponiendo una función de evaluación que asigna una puntuación a las posibles transiciones según un patrón, representado por un vector , así como un medio para evaluar una secuencia completa de transiciones, el análisis equivale a encontrar la secuencia que tiene la puntuación más alta. Como tal, la mayoría de los sistemas implementan una búsqueda de haz.

{\ displaystyle {\ boldsymbol {y}}}

{\ displaystyle P ({\ boldsymbol {y}} | {\ boldsymbol {x}})}

{\ Displaystyle S (\ Phi (\ mathbf {c}), d)}

D

{\ Displaystyle \ Phi (\ mathbf {c})}

Un método muy popular para el análisis de estructuras de dependencia es el uso de un clasificador (entrenado en un corpus), para predecir la siguiente acción ejecutada por un algoritmo de análisis determinista. Este enfoque a veces se denomina "pseudodeterminista", en referencia a los algoritmos de análisis deterministas aplicados a gramáticas no ambiguas ( lenguajes formales ). En el caso que nos ocupa, el espacio de búsqueda está intrínsecamente limitado por el método del algoritmo, ya que una sola acción elegida implica el abandono de todas las demás; Debido a este enfoque codicioso, la poda es muy agresiva. Esta fortaleza también es una desventaja, ya que una elección incorrecta temprana puede afectar negativamente el análisis final.

Un sistema de análisis basado en clasificadores consta de tres ingredientes esenciales:

un algoritmo de análisis sintáctico que establece un análisis por sucesión de acciones elementales (mediante un sistema de transiciones );
un modelo que permite describir cualquier estado del analizador (configuraciones del sistema de transiciones) mediante un vector de características;
un clasificador que transforma un estado, en forma de vector de características, en una acción del algoritmo de análisis.

Este enfoque fue iniciado por T. Kudo e Y. Matsumoto, quienes propusieron una implementación acoplada a un clasificador de tipo de máquina de vector de soporte , para el análisis de dependencia sin etiquetar del japonés. Utilizando la base del algoritmo de Joakim Nivre, la idea se extendió posteriormente de forma iterativa a dependencias etiquetadas para sueco, luego para inglés, luego 19 idiomas, antes de optimizarse para formar el software MaltParser . Los primeros algoritmos se limitan a estructuras proyectivas , pero G. Attardi, entre otros, propuso un algoritmo extendido a un subconjunto de estructuras no proyectivas. Como tal, J. Nivre ofrece una versión de reordenamiento en línea de su sistema de transiciones, mientras que otros enfoques implican una descomposición en (sub) árboles de dependencias planas y el análisis de cada plan por separado ( análisis sintáctico mltiplanar ). Otra solución implica el procesamiento previo / posterior de los datos (llamado pseudoproyectivización ).

Los principales problemas de este paradigma son la sensibilidad a los errores de búsqueda y la propagación de errores debido al proceso incremental uno a uno. En un intento por mejorar la precisión, mientras se mantiene un análisis altamente eficiente, han surgido varias técnicas. Algunos han relajado el proceso estrictamente determinista, manteniendo los mejores análisis de K ( búsqueda de haz ), a veces asociado con el entrenamiento como una predicción estructurada, mientras que otros han abandonado el análisis puramente secuencial de izquierda a derecha ( análisis fácil primero ), porque la búsqueda de haz ralentiza sustancialmente el análisis. Con el mismo objetivo, J. Nivre experimentó con el uso de un oráculo dinámico, tanto no determinista como completo (a diferencia de los oráculos estáticos habituales), para su sistema de transiciones ávidas de

arco . Sin embargo, estos oráculos inducen una gran complejidad cuando se usan con sistemas generales (no limitados a estructuras proyectivas), y no siempre es posible derivarlos. Por esta razón, M. Straka et al. han introducido una nueva clase de oráculos denominados oráculos basados en búsquedas , que es una aproximación de los oráculos dinámicos.

En la práctica, se definen modelos probabilísticos para cada acción del algoritmo de análisis, según su contexto actual; sin embargo, los modelos basados en un historial de acciones (o transiciones) deben hacer frente a una cantidad ilimitada de información, lo que hace imposible el modelado probabilístico. Este problema generalmente se resuelve limitando la historia a un conjunto finito de características. En este punto, la mayor dificultad radica en la elección de la representación de esta historia, es decir, su visión general, a partir de la cual se puede estimar adecuadamente la probabilidad de la próxima acción. Como esta probabilidad es independiente de cualquier información sobre el historial que no esté contenida en su descripción general, la calidad del análisis puede verse fuertemente afectada por las características seleccionadas.

La investigación en el campo del análisis estadístico comenzó a mediados de la década de 1990 y se centró principalmente en modelos lineales durante muchos años. Con tales modelos, la puntuación asignada a un análisis se calcula de acuerdo con una combinación de rasgos estructurales o características morfológicas, cuya representación es naturalmente escasa , relacionada con la estructura en cuestión. Sin embargo, esto requiere una selección manual, plausiblemente tediosa, de las combinaciones de rasgos que se incluirán en la evaluación, antes del uso de un algoritmo de aprendizaje. Por tanto, adaptar estos modelos a nuevos lenguajes o nuevos campos es difícil y caro; además, olvidar una característica importante puede tener un impacto muy negativo en la precisión (problema de incompletitud). Además, los analizadores dedican la mayor parte de su tiempo a extraer características, no al análisis en sí. Todas estas razones han motivado el desarrollo de modelos no lineales , capaces de inducir automáticamente una combinación adecuada de rasgos predictivos; en tales casos, una red neuronal artificial en segundo lugar o en su mayoría reemplaza al clasificador lineal . Con la mayoría de los modelos, sin embargo, es necesario proporcionarles un pequeño número (aprox. 10-20) de características dinámicas simples (es decir, no combinadas). Este enfoque fue iniciado por James Henderson a principios de la década de 2000, luego se profundizó en 2007 con un analizador basado en un modelo probabilístico puramente generativo y equipado con un ISBN ( red de creencias sigmoideas incrementales ) para la extracción de características, bastante cercano a 'una dinámica bayesiana red . La ventaja de esta técnica es obtener una representación densa de palabras (es decir, incrustación de palabras ), etiquetas morfosintácticas y otras características lingüísticas; esta última representación (de menor dimensión) transmite, por ejemplo, una noción de similitud entre palabras en un espacio dimensional continuo , o incluso todo el historial de análisis cuando la red es recurrente. En resumen, las representaciones densas se benefician de una fuerte capacidad de generalización. $metro$

Los modelos de características dinámicas (independientes) mencionados en el párrafo anterior seleccionan elementos lingüísticos (palabras, etiquetas de dependencia, etc.), cuyos vectores de representación ( incrustaciones ) a menudo se concatenan en la entrada de la red neuronal. Si el número de características está sujeto a variaciones, se necesita alguna forma de mantener los vectores de tamaño fijo, ya que la entrada a una red es de tamaño fijo. Se puede, por ejemplo, realizar una media de los vectores (representación mediante “bolsa continua de palabras” o CBOW).

Hoy en día, la extracción de características se realiza con redes de diversa complejidad, compuestas por unidades LSTM , por ejemplo (red LSTM apilada, LSTM bidireccional, etc.), un ISBN, o utilizando redes de no recurrencia, como la primera capa de un multi -perceptrón en capas . Algunos enfoques (llamados basados en caracteres ) incluso aprenden a representar palabras de caracteres individuales, como SyntaxNet ( segunda versión ) y LSTM-Parser.

En cuanto al clasificador en sí, suele ser un perceptrón estructurado, como el sistema SyntaxNet ( Parsey's Cousins ) propuesto por Google, del cual el sistema revisado ( ParseySaurus ) es uno de los más precisos en la actualidad. Estos últimos sistemas se basan inicialmente en el Stanford Parser desarrollado por Danqi Chen y Christopher Manning en 2014, pero integran una red neuronal profunda (y diferentes funciones de activación) con entrenamiento estructurado, sin mencionar el modelo probabilístico con normalización global . O con auto- Estandarización. Pero los sistemas de última generación, como LSTM-Parser o DINN, no utilizan necesariamente una red profunda y utilizan, por ejemplo, una capa softmax como clasificador (predicción de las acciones elementales de análisis).

Métodos basados en gráficos

Los modelos de análisis basados en gráficos son modelos discriminantes (consulte la sección “ modelos de análisis estadístico ”). La ventaja de las estructuras en dependencias, en comparación con las de los constituyentes, es hacer que este tipo de enfoque sea compatible con la inferencia exacta. De hecho, un enfoque generalizado, propuesto inicialmente por Ryan McDonald et al. , es encontrar el árbol de

expansión de peso máximo en un gráfico completo . Tenga en cuenta que, en estas condiciones, el componente no está modelado por un sistema autónomo, sino por una propiedad de la teoría de grafos . Sin embargo, la inferencia exacta presupone limitar el alcance de las características a los subgrafos; por tanto, se han desarrollado otras técnicas de aproximación. En comparación con los modelos basados en transiciones, la ventaja de este tipo de modelo es la observación, en teoría, de propiedades sobre toda la estructura global y / o la oración de entrada sin restricciones, mientras que las propiedades se limitan a un contexto estructuralmente local con la primera categoría. .

{\ Displaystyle \ mathrm {GEN} ({\ boldsymbol {x}})}

En la práctica, solo los modelos que tratan el puntaje de cada arco de forma aislada - llamados de " 1er orden" o factorizados por arco - son solubles de manera exacta en un tiempo razonable, ya que el menor incremento de estos modelos genera un problema NP-difícil . Esto presupone que cada relación de dependencia es independiente de las demás, lo que está lejos de ser cierto desde el punto de vista lingüístico. Sin embargo, algunos sistemas de 1er orden son extremadamente competitivos en términos de precisión, al igual que los de T. y C. Manning Dozat, basado en un mecanismo de cuidado biafino profundo . La gran mayoría de los sistemas de primer orden se basan en el algoritmo

de Eisner o en el codicioso algoritmo Chu-Liu-Edmonds (CLE). El primero es un algoritmo de programación dinámica derivado de CKY que, por lo tanto, solo encuentra estructuras proyectivas, mientras que el segundo encuentra el árbol de expansión de peso máximo y, por lo tanto, también es capaz de devolver un árbol de dependencias no proyectivo.

Para prever una mejora en el rendimiento manteniendo un algoritmo de tiempo polinomial, algunos enfoques han ampliado el gráfico del algoritmo de Eisner, agregando un factor cuadrático a la complejidad con cada aumento en el orden del modelo. La investigación en esta dirección está más o menos de acuerdo con modelos de 4º orden (complejidad temporal ). Más recientes estrategias - y 200x, respectivamente, y 5 veces más rápido que un modelo exacto de la 3

ª fin - explorado podar el espacio de búsqueda con el uso del algoritmo de vid parse ( ) , o el mantenimiento de un conjunto de alternativas integrado en el algoritmo de Eisner (espíritu de la poda en cubos ), entre otros. Estas aproximaciones permiten reducir drásticamente el costo del análisis, mientras se mantiene la precisión en los modelos exactos de 3º o 4º orden.

{\ Displaystyle {\ mathcal {O}} (n ^ {5})}

En cuanto a los modelos de orden superior capaces de producir todo tipo de árboles de dependencia (incluidos los no proyectivos), necesariamente pasan por una aproximación, ya sea de decodificación o del espacio de búsqueda. La primera opción incluye sistemas que incorporan postprocesamiento al final del algoritmo Eisner o CLE, que reorganiza los arcos o combina los mejores árboles de expansión, respectivamente. Otros se basan en el principio de descomposición dual, relajación continua , etc. La segunda categoría incluye los procesos que consideran solo una pequeña parte del conjunto de árboles de dependencia no proyectiva, porque algunas estructuras son lingüísticamente improbables y es completamente inútil tratar de producirlas (las últimas se denominan estructuras levemente no proyectivas ). . Sin embargo, se intentaron experimentos menos exitosos con optimización lineal entera (ILP).

Todos estos sistemas utilizan un algoritmo de aprendizaje como el perceptrón estructurado, MIRA (extensión de este último), clasificador de máxima entropía (MaxEnt), etc. La mayoría de los sistemas discutidos en esta sección seleccionan las características de cada subgrafo (por ejemplo, un arco) utilizando modelos preestablecidos (representación escasa). Sin embargo, algunas técnicas recientes emplean una red neuronal para la extracción de características: propagación directa o recurrente ; además, la puntuación ya no se calcula linealmente, sino en particular mediante un perceptrón multicapa , a veces asociado con una transformación bilineal.

Complejidad del análisis de dependencia

Aquí hay una descripción general de la complejidad temporal de analizar algoritmos para estructuras de dependencia. Diferenciamos aquellos capaces de producir solo estructuras proyectivas de algoritmos generales, pero solo consideramos versiones exactas (excluye aproximaciones).

	Proy.	No proy.
Análisis basado en la transición	${\ mathcal {O}} (n)$	${\ mathcal {O}} (n ^ {2})$ ${\ mathcal {O}} (n)$ en la práctica
Análisis basado en gráficos - 1er orden	${\ Displaystyle {\ mathcal {O}} (n ^ {3})}$	${\ mathcal {O}} (n ^ {2})$
Análisis basado en gráficos : enésimo orden (n> 1)	FP ...	FNP-completo

Evaluación de análisis

Cualquier sistema de análisis debe evaluarse para medir su rendimiento. Esto se hace realizando el procedimiento de análisis en un conjunto de datos de prueba, diferente del conjunto de entrenamiento (si lo hay) y generalmente mucho más pequeño. Las estructuras producidas por el analizador sintáctico se compararán con las estructuras de referencia ( análisis estándar de oro ), que se consideran los mejores análisis, que son anotados por los lingüistas. Las medidas que se utilizan habitualmente son precisión y recuerdo , a menudo combinadas en una única puntuación denominada puntuación F , que corresponde a la media armónica de precisión ( ) y recuerdo ( ): ${\ textstyle P}$ ${\ textstyle R}$

F1=(2PAGR)(PAG+R){\ Displaystyle F_ {1} = {\ frac {(2PR)} {(P + R)}}} ${\ Displaystyle F_ {1} = {\ frac {(2PR)} {(P + R)}}}$

El método más simple es contar el número de frases para las que la estructura producida es idéntica a la estructura de referencia ( coincidencia exacta ). Esta es una prueba extremadamente dura, en el sentido de que un solo error de etiqueta tiene el mismo impacto que un análisis completamente erróneo; por lo tanto, se prefieren las métricas basadas en una coincidencia parcial, cuya granularidad es más fina.

De las estructuras a los constituyentes

Las medidas más utilizadas son las relacionadas con las métricas PARSEVAL, contando el número de constituyentes que corresponden a los presentes en la estructura de referencia.

De estructuras a dependencias

Con respecto a las estructuras de dependencia, la medida comúnmente utilizada es la puntuación de apego , que determina la proporción de palabras correctamente vinculadas al padre correcto, en comparación con la referencia. Existen varias variaciones:

Puntuación de archivo adjunto sin etiquetar (UAS): una relación se considera correcta si el niño está relacionado con el padre esperado.
Puntaje de apego etiquetado (LAS): una relación se considera correcta si el niño está relacionado con el padre esperado y el tipo de relación se reproduce fielmente.
Puntaje de precisión de etiqueta (LS): solo examinamos la etiqueta de una relación, sin tener en cuenta al padre.

Como cada unidad léxica tiene exactamente un padre, una sola medida es suficiente para calificar la precisión. A nivel de corpus, la puntuación global se puede calcular en la escala de la palabra ( micropromedio ), es decir, sin tener en cuenta la oración a la que pertenece una palabra, o en la escala de la oración ( macropromedio ) , tomando el promedio de las puntuaciones de cada uno de ellos.

Notas y referencias

Por lo general, las dependencias cruzadas (o no proyectivas), que ocurren en algunos idiomas, no se pueden obtener con una gramática de tipo 2 . El lenguaje natural es, por tanto, de tipo 1 ( contextual ), pero muy cercano al tipo 2.
Un árbol de dependencia es formalmente un grafo dirigido simple, conectado y acíclico etiquetado, que comprende una sola raíz, provista de una relación de precedencia lineal en el conjunto de vértices (orden de palabras). $V$
Esto corresponde a combinar elementos lingüísticos (palabras ...), luego buscar en una estructura de datos que contiene varios millones de elementos.
Todos los sistemas anteriores utilizan una normalización local , mucho menos compleja de calcular. También es imposible calcular probabilidades globalmente normalizadas en un tiempo razonable; estos sistemas, por tanto, requieren una aproximación.

Referencias bibliográficas

Jacqueline Léon , Historia de la automatización de las ciencias del lenguaje , ENS Éditions, coll. "Idiomas",27 de marzo de 2015, 218 p. ( ISBN 978-2-84788-680-1 , DOI 10.4000 / books.enseditions.3733 , leer en línea )
Tadao Kasami, "Un algoritmo de reconocimiento y sintaxis eficiente para lenguajes sin contexto", Informe técnico AFCLR-65-758 , Laboratorio de investigación de Cambridge de la Fuerza Aérea, 1965
DH Younger, “Reconocimiento de lenguajes libres de contexto en el tiempo n 3 ” , Información y control , vol. 10, n o 2, 1967, p. 189-208.
Jay Earley, “An eficiente libre de contexto algoritmo de análisis sintáctico”, En: Comunicaciones de la ACM 13 (2) , p. 94-102, 1970
Ronald M. Kaplan, “Un procesador sintáctico en general”, En: Procesamiento del Lenguaje Natural , Bajo la dir. por R. Rustin, Algorithmics Press, pág. 193-241, 1973
Martin Kay, “Algoritmo Los esquemas y estructuras de datos en el procesamiento sintáctico”, Informe CSL - 80-12 , Xerox PARC, 1980
Alan Demers, “Análisis generalizado de la esquina izquierda”, en: Actas del 4º Simposio ACM SIGACT-SIGPLAN sobre principios de lenguajes de programación , ACM, p. 170-182, 1977
Hiroshi Maruyama, “Desambiguación estructural con propagación de restricciones”, En: Actas de la 28ª Reunión de la Asociación de Lingüística Computacional , Asociación de Lingüística Computacional, p. 31-38, 1990
T. L. Booth y AR Thompson, “La aplicación de medidas de probabilidad de abstraer las lenguas”, en: IEEE Transactions on Computers 22.5 , p. 442-450, 1973
Eugene Charniak, "Análisis estadístico con una gramática libre de contexto y estadísticas de palabras", En: Actas de la 14ª Conferencia Nacional sobre Inteligencia Artificial , Asociación de Lingüística Computacional, p. 598-603, 1997
Dan Klein y Christopher D. Manning, "Análisis sintáctico preciso no exicalizado", en: Actas de la 41a reunión anual sobre la Asociación de Lingüística Computacional , Asociación de Lingüística Computacional., 2003
Jason M. Eisner, "Tres nuevos modelos probabilísticos para el análisis de dependencias: una exploración", en: Actas de la 16ª Conferencia Internacional sobre Lingüística Computacional, Asociación de Lingüística Computacional, p. 340-345, 1996
Joakim Nivre, "Análisis estadístico", en: Manual de procesamiento del lenguaje natural , bajo el dir. por Nitin Indurkhya y Fred J. Damerau, 2nd, Chapman & Hall / CRC, Cap. 11, pág. 237-266, 2010
Kenneth Church y Ramesh Patil, "Hacer frente a la ambigüedad sintáctica o cómo poner el bloque en la caja sobre la mesa", Computación. Lingüista. 8, 3-4, 139-149, 1982
H. Ney, “Análisis de programación dinámica para gramáticas libres de contexto en reconocimiento de voz continuo”, I EEE Transactions on Signal Processing, 39 (2) , 336–340, 1991.
(en) Michael Collins , " Modelos estadísticos dirigidos por la cabeza para el análisis del lenguaje natural " , Lingüística computacional , vol. 29, n o 4,1 st de diciembre de de 2003, p. 589–637 ( ISSN 0891-2017 , DOI 10.1162 / 089120103322753356 , leer en línea )
(en) Slav Petrov , Leon Barrett , Romain Thibaux y Dan Klein , " Aprendizaje preciso, compacto e interpretable de la anotación de árbol " , Actas de la 21ª Conferencia Internacional sobre Lingüística Computacional y 44ª Reunión Anual de la Asociación de Lingüística Computacional ,2006( leer en línea )
R. Bod, “Enriquecimiento de la lingüística con estadísticas: modelos de desempeño del lenguaje natural”, tesis de doctorado , Universidad de Amsterdam, Amsterdam, Holanda, 1995.
R. Bod, R. Scha y K. Sima'an (Eds.), "Análisis orientado a datos", Publicaciones de CSLI , Stanford, CA, 2003. ( Leer en línea )
(en) Michael Collins y Terry Koo , " reordenación discriminativo de Lenguaje Natural de análisis " , lingüística computacional , vol. 31, n o 1,Marzo de 2005, p. 25–70 ( ISSN 0891-2017 y 1530-9312 , DOI 10.1162 / 0891201053630273 , leído en línea , consultado el 11 de junio de 2018 )
(en) Geoffrey N. Leech , Gramáticas informáticas del inglés basadas en estadísticas: el enfoque IBM / Lancaster , Rodopi,1993( ISBN 90-5183-478-0 )
(en) Ivan Titov y James Henderson , " Un modelo de variable latente para el análisis de la dependencia generativa " , Actas de la 10ª Conferencia Internacional sobre Tecnologías de Análisis , Asociación de Lingüística Computacional,23 de junio de 2007, p. 144-155 ( ISBN 9781932432909 , leído en línea , consultado el 12 de junio de 2018 )
(en) Michael Collins , “ discriminativo para la reordenación de análisis de lenguaje natural ” , Actas de la Conferencia Internacional del Decimoséptimo Machine Learning , Morgan Kaufmann Publishers Inc.,29 de junio de 2000, p. 175–182 ( ISBN 1558607072 , leer en línea )
(en) Michael Collins y Nigel Duffy , " Nuevos algoritmos de clasificación para analizar y etiquetar: núcleos sobre estructuras discretas y el perceptrón votado " , Actas de la 40a reunión anual de la Asociación de Lingüística Computacional , Asociación de Lingüística Computacional,6 de julio de 2002, p. 263–270 ( DOI 10.3115 / 1073083.1073128 , leer en línea )
Haim Gaifman, "Sistemas de dependencia y sistemas de estructura de frases", En: Información y control 8.3 , p. 304-337, 1965
(en) Michael A. Covington, “ un algoritmo Fundamental a la Dependencia de análisis ” , Actas de la 39ª Conferencia Anual del sureste ACM ,2001, p. 95-102
(in) Sabine Buchholz y Erwin Marsi , " CoNLL-X Shared Task is Multilingual Dependency Parsing " , Revista Internacional de Ingeniería y Tecnología Web - IJWET ,1 st de enero de de 2006( DOI 10.3115 / 1596276.1596305 , leído en línea , consultado el 12 de junio de 2018 )
(en) J. NIVRE, J. Hall, S. Kübler, R. McDonald, J. Nilsson, S. Riedel, D. Yuret, " The CoNLL 2007 Shared Task Dependency Analizando nosotros " , Actas de la Task CoNLL Shared Session de EMNLP-CoNLL 2007 ,2007, p. 915-932
(en) Tianze Shi , Felix G. Wu , Xilun Chen y Yao Cheng , " Combinando modelos globales para analizar dependencias universales " , Actas de la tarea compartida de CoNLL 2017: Análisis de texto multilingüe de dependencias crudas a universales , Asociación de Lingüística Computacional, Además de esto, necesita saber más al respecto.2017, p. 31–39 ( DOI 10.18653 / v1 / K17-3003 , leer en línea )
(in) Anders Björkelund Agnieszka Falenska , Xiang Yu y Jonas Kuhn , " IMS en la tarea compartida de UD de CoNLL 2017: CRF y perceptrones se encuentran con redes neuronales " , Actas de la tarea compartida de CoNLL 2017: análisis multilingüe de texto sin formato a dependencias universales , Asociación de Lingüística Computacional,2017, p. 40–51 ( DOI 10.18653 / v1 / K17-3004 , leer en línea )
(en) Joakim NIVRE y Ryan McDonald , " Integración de analizadores de dependencia basados en gráficos y en transición " , Actas de ACL-08: HLT ,2008( leer en línea )
(in) Ryan Mcdonald , " Caracterización de los errores de los modelos de análisis de dependencia basados en datos " , PROCEDIMIENTOS DE LA CONFERENCIA SOBRE MÉTODOS EMPÍRICOS EN EL PROCESAMIENTO DEL LENGUAJE NATURAL Y EL APRENDIZAJE DEL LENGUAJE NATURAL ,2007( leer en línea , consultado el 11 de junio de 2018 )
Joakim Nivre, “un algoritmo eficiente para proyectiva Dependencia de análisis”, en: Actas de la octava Taller Internacional sobre análisis sintáctico Technologies (IWPT) , 2003
(en) Ryan McDonald , Fernando Pereira , Kiril Ribarov y Jan Hajič , " Análisis de dependencia no proyectiva utilizando algoritmos de árbol de expansión " , Actas de la Conferencia sobre tecnología del lenguaje humano y métodos empíricos en el procesamiento del lenguaje natural , Asociación para Lingüística Computacional,6 de octubre de 2005, p. 523-530 ( DOI 10.3115 / 1220575.1220641 , leído en línea , consultado el 6 de junio de 2018 )
(en) Jinho D. Choi , Joel Tetreault y Amanda Stent , " Depende: Analizador de dependencias una comparación utilizando la herramienta de evaluación basada en la web " , Actas de la 53ª Reunión Anual de la Asociación de Lingüística Computacional y la 7ª Conferencia Conjunta Internacional sobre Procesamiento del lenguaje natural (Volumen 1: Artículos extensos) , Asociación de Lingüística Computacional, vol. 1,2015, p. 387–396 ( DOI 10.3115 / v1 / P15-1038 , leer en línea )
Tony Jebara, “Aprendizaje discriminativo, generativo e imitativo”, tesis de doctorado , Instituto de Tecnología de Massachusetts, 212 p., 2002.
(en) Joakim NIVRE , " Algoritmos para análisis de dependencias incrementales deterministas " , Lingüística computacional , vol. 34, n o 4,diciembre 2008, p. 513–553 ( ISSN 0891-2017 y 1530-9312 , DOI 10.1162 / coli.07-056-r1-07-027 , leído en línea , consultado el 6 de junio de 2018 )
(en) Taku Kudo y Yuji Matsumoto , " El análisis de la estructura de dependencia japonesa se basa en máquinas de vectores de soporte " , Actas de la Conferencia conjunta de 2000 sobre métodos empíricos SIGDAT en el procesamiento del lenguaje natural y cuerpos muy grandes , Asociación de Lingüística Computacional,7 de octubre de 2000, p. 18-25 ( DOI 10.3115 / 1117794.1117797 , leído en línea , consultado el 6 de junio de 2018 )
(en) Joakim NIVRE Johan Hall , Jens Nilsson y Gülşen Eryiǧit , " Análisis de dependencia pseudo-proyectiva etiquetada con máquinas de vectores de soporte " , Actas de la Décima Conferencia sobre Aprendizaje del Lenguaje Natural Computacional , Asociación de Lingüística Computacional,8 de junio de 2006, p. 221–225
J. Nivre, J. Hall, J. Nilsson, A. Chanev, G. Eryigit, S. Kübler, S. Marinov y E. Marsi, "MaltParser: Un sistema independiente del lenguaje para el análisis de dependencias basado en datos", Ingeniería del lenguaje natural , 13, 95-135, 2007.
Giuseppe Attardi, “Experimentos con un analizador sintáctico de dependencia no proyectivo multilenguaje”, en Actas de la Décima Conferencia sobre Aprendizaje Computacional del Lenguaje Natural (CoNLL-X '06). Asociación de Lingüística Computacional, Stroudsburg, PA, EE. UU., 166-170, 2006.
(en) Joakim Nivre , " Incremental no proyectiva Dependencia de análisis. » , Actas de la Conferencia del Capítulo Norteamericano de la Asociación de Lingüística Computacional ,1 st de enero de de 2007, p. 396-403
Joakim Nivre, “análisis de dependencias no proyectiva en el tiempo lineal esperada”. En Actas de la Conferencia Conjunta de la 47a Reunión Anual de la ACL y la 4a Conferencia Conjunta Internacional sobre Procesamiento del Lenguaje Natural de la AFNLP: Volumen 1 - Volumen 1 (ACL '09), Asociación de Lingüística Computacional, Stroudsburg, PA, EE. UU., 351-359, 2009.
“analizador basado en transición A para las estructuras de dependencia 2-planares” Carlos Gómez-Rodríguez y Joakim Nivre,. En Actas de la 48a Reunión Anual de la Asociación de Lingüística Computacional (ACL '10), Asociación de Lingüística Computacional, Stroudsburg, PA, EE. UU., 1492-1501, 2010.
(in) Joakim NIVRE y Jens Nilsson , " Análisis de dependencia pseudo-proyectiva " , Actas de la 43ª Reunión Anual de la Asociación de Lingüística Computacional , Asociación de Lingüística Computacional,25 de junio de 2005, p. 99–106 ( DOI 10.3115 / 1219840.1219853 , leído en línea , consultado el 12 de junio de 2018 )
Richard Johansson y Pierre Nugues, “Investigating multilingual dependency parsing”, en actas de la décima conferencia sobre aprendizaje computacional del lenguaje natural (CoNLL-X '06), Asociación de lingüística computacional, Stroudsburg, PA, EE. UU., 206-210, 2006.
(en) Yue Zhang y Stephen Clark , " Una historia de dos analizadores: investigando y combinando análisis de dependencia basado en gráficos y en transición utilizando la búsqueda de haces " , EN PROCEDIMIENTOS DE EMNLP-08 ,2008
Yoav Goldberg y Michael Elhadad, "Un algoritmo eficiente para el análisis de dependencias no direccionales y fáciles primero", en Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics (HLT '10), Association for Lingüística Computacional, Stroudsburg, PA, EE. UU., 742-750, 2010.
Yoav Goldberg, Joakim Nivre, "Un Oracle dinámico para el análisis de dependencias Arc-Eager", 2012
Milan Straka, Jan Hajič, Jana Strakova y Jan jr. Hajič, "Análisis de bancos de árboles de dependencia universal mediante redes neuronales y Oracle basado en búsquedas", 2015.
(in) Yue Zhang y Joakim NIVRE , " Análisis de dependencia basado en la transición con características enriquecidas no locales " , Actas de la 49ª Reunión Anual de la Asociación de Lingüística Computacional ,2011
(in) Bernd Bohnet , " La precisión muy alta y el análisis de dependencia rápido no es una contradicción " , Actas de la 23ª Conferencia Internacional sobre Lingüística Computacional , Asociación de Lingüística Computacional,23 de agosto de 2010, p. 89–97
(in) James Henderson , " Inducción de la amplia cobertura de representaciones históricas para el análisis estadístico " , Actas de la Conferencia de 2003 del Capítulo norteamericano de la Asociación de Lingüística Computacional sobre Tecnología del Lenguaje Humano , Asociación de Lingüística Computacional,27 de mayo de 2003, p. 24–31 ( DOI 10.3115 / 1073445.1073459 , leído en línea , consultado el 6 de junio de 2018 )
(en) James Henderson , " entrenamiento discriminativo de un analizador estadístico de redes neuronales " , Actas de la 42ª Reunión Anual de la Asociación de Lingüística Computacional , Asociación de Lingüística Computacional,21 de julio de 2004, p. 95 ( DOI 10.3115 / 1218955.1218968 , leído en línea , consultado el 6 de junio de 2018 )
(in) T Mikolov , W. T- Yih y G Zweig , " Regularidades lingüísticas en representaciones de palabras en espacios continuos " , Actas de NAACL-HLT ,1 st de enero de 2013, p. 746–751 ( leer en línea )
(in) Tomas Mikolov Kai Chen , Greg Corrado y Jeffrey Dean , " Estimación eficiente de representaciones de vectores de palabras en el espacio " , arXiv: 1301.3781 [cs] ,16 de enero de 2013( leer en línea )
(en) Chris Dyer , Miguel Ballesteros , Wang Ling y Austin Matthews , " Pila de análisis de dependencia basada en la transición con memoria a corto plazo " , arXiv: 1505.08075 [cs] ,29 de mayo de 2015( leer en línea )
(en) Eliyahu Kiperwasser y Yoav Goldberg , “ simple y preciso de Dependencia de análisis Uso de representaciones de entidades bidireccional LSTM ” , arXiv: 1603.04351 [cs] ,14 de marzo de 2016( leer en línea )
Majid Yazdani y James Henderson, incremental red neuronal recurrente Dependencia Analizador con el entrenamiento discriminativo basado en la búsqueda, En: Actas de la 19ª Conferencia Computacional aprendizaje de idiomas , Beijing, China, 2015, p. 142-152.
(en) Daniel Andor , Chris Alberti , David Weiss y Aliaksei Severyn , “ A nivel mundial normalizados de transición basados Redes Neuronales ” , Actas de la 54ª Reunión Anual de la Asociación de Lingüística Computacional (Volumen 1: Documentos de largo) , Asociación de Lingüística Computacional,2016( DOI 10.18653 / v1 / p16-1231 , leer en línea )
(es) " una actualización a SyntaxNet, nuevos modelos y una Liga de análisis " ,15 de marzo de 2017
(en) Miguel Ballesteros , Chris Dyer y Noah A. Smith , “ Mejora de análisis de transición de base mediante el modelado de caracteres en lugar de las palabras con los LSTMs ” , Actas de la Conferencia de 2015 sobre métodos empíricos en Procesamiento del Lenguaje Natural , Asociación Computacional Lingüística,2015( DOI 10.18653 / v1 / d15-1041 , leer en línea )
(en) Ryan McDonald y Fernando Pereira , " Aprendizaje en Línea de Dependencia aproximado de análisis de algoritmos " , en Proc. DE AECL ,2006, p. 81––88
(en) Ryan McDonald y Giorgio Satta , “ Por la complejidad de la no-proyectivo análisis de dependencias basadas en datos ” , Actas de la 10ª Conferencia Internacional sobre Tecnologías de análisis sintáctico , la Asociación de Lingüística Computacional,23 de junio de 2007, p. 121-132 ( ISBN 9781932432909 , leer en línea )
(en) Jason M. Eisner , " Tres nuevos modelos probabilísticos para el análisis de dependencia: una exploración " , Actas de la 16ª Conferencia sobre Lingüística Computacional , Asociación de Lingüística Computacional,5 de agosto de 1996, p. 340–345 ( DOI 10.3115 / 992628.992688 , leer en línea )
Jack Edmonds, "Optimum Branchings", en: J. Res. Nat. Rebaba. Estándares 71B.4 , p. 233-240, 1967.
(en) Xavier Carreras , “ Experimentos con un orden superior proyectiva Dependencia Analizador ” , Actas de la Conferencia Conjunta de 2007 sobre métodos empíricos en el Procesamiento del Lenguaje Natural y Aprendizaje Computacional del Lenguaje Natural (EMNLP-CoNLL) ,2007( leer en línea )
(en) Terry Koo y Michael Collins , " Analizadores de dependencia de tercer orden eficientes. » , Actas de la 48ª Reunión Anual de la Asociación de Lingüística Computacional ,22 de diciembre de 2010, p. 1-11 ( leer en línea )
(en) Xuezhe My y Hai Zhao , " Análisis de dependencia de cuarto orden " , Actas de COLING 2012 ,1 st de diciembre de 2012, p. 785–796 ( leer en línea )
(en) Markus Dreyer , David A. Smith y Noah A. Smith , " Análisis de vid y cambio de clasificación de riesgo mínimo para lograr velocidad y precisión " , Actas de la Décima Conferencia sobre Aprendizaje de Lenguaje Natural Computacional , Asociación de Lingüística Computacional,8 de junio de 2006, p. 201–205 ( leer en línea )
(in) Alexander M. Rush y Slav Petrov , " Poda de vid para una dependencia eficiente del análisis de múltiples pasadas " , Actas de la Conferencia de 2012 del Capítulo norteamericano de la Asociación de Lingüística Computacional , Asociación de Lingüística Computacional,3 de junio de 2012, p. 498–507 ( ISBN 9781937284206 , leer en línea )
(en) Mark Hopkins y Greg Langmead , "La poda de cubos como búsqueda heurística " , Actas de la Conferencia de 2009 sobre métodos empíricos en el procesamiento del lenguaje natural , Asociación de Lingüística Computacional,6 de agosto de 2009, p. 62–71 ( ISBN 9781932432596 , leer en línea )
(en) Hao Zhang y Ryan McDonald , " Análisis de dependencia generalizado de orden superior con poda de cubos " , Actas de la Conferencia conjunta de 2012 sobre métodos empíricos en el procesamiento del lenguaje natural y el aprendizaje computacional del lenguaje natural ,2012( leer en línea )
(in) Keith Hall , " K-best Spanning Tree Parsing " , Actas de la 45ª Reunión Anual de la Asociación de Lingüística Computacional ,2007( leer en línea )
(in) Terry Koo , Alexander M. Rush , Michael Collins y Tommi Jaakkola , " Descomposición dual para el análisis sintáctico con autómatas de cabeza no proyectiva " , Actas de la Conferencia de 2010 sobre métodos empíricos en el procesamiento del lenguaje natural , Asociación de Lingüística Computacional,9 de octubre de 2010, p. 1288–1298 ( leer en línea )
(in) Andre FT Martins , Noah A. Smith , Pedro MQ Aguiar y AT Mário Figueiredo , " Descomposición dual con muchos componentes superpuestos " , Actas de la Conferencia sobre métodos empíricos en el procesamiento del lenguaje natural , Asociación de Lingüística Computacional,27 de julio de 2011, p. 238–249 ( ISBN 9781937284114 , leer en línea )
(in) André Martins , Miguel Almeida y Noah A Smith , " Encendido de los analizadores turbo no proyectivos de tercer orden Turbo Fast " , Actas de la 51ª Reunión Anual de la Asociación de Lingüística Computacional , vol. 2,1 st de agosto de 2013, p. 617–622 ( leer en línea )
(en) Sebastian Riedel , David Smith y Andrew Mccallum , " Parse, price and cut: delay column and row generation for graph based parsers " , Actas de la Conferencia conjunta de 2012 sobre métodos empíricos en el procesamiento del lenguaje natural y el aprendizaje computacional del lenguaje natural , Además de esto, necesita saber más al respecto.12 de julio de 2012, p. 732–743 ( leer en línea )
(en) Carlos Gomez-Rodriguez , John Carroll y David Weir , " Esquemas de análisis de dependencia y análisis de dependencia levemente no proyectivo " , Lingüística Computacional , vol. 37, n o 3,1 st de septiembre de 2011, p. 541–586 ( ISSN 0891-2017 , DOI 10.1162 / COLI_a_00060 , leer en línea )
(en) Emily Pitler , Sampath Kannan y Mitchell Marcus , " Programación dinámica para análisis de orden superior de árboles de búsqueda de espacios " , Actas de la Conferencia conjunta de 2012 sobre métodos empíricos en el procesamiento del lenguaje natural y el aprendizaje computacional del lenguaje natural ,2012( leer en línea )
(en) Emily Pitler , Sampath Kannan y Mitchell Marcus , " Encontrar árboles óptimos de cruce de 1 punto final " , Transacciones de la Asociación de Lingüística Computacional , vol. 1,2013( leer en línea )
(en) Emily Pitler , " Una factorización de tercer orden sensible al cruce para el análisis de dependencias " , Transacciones de la Asociación de Lingüística Computacional , vol. 2, n o 1,2014( leer en línea )
(en) Andre FT Martins , Noah A. Smith y Eric P. Xing , " Formulaciones de programación lineal de enteros concisos para análisis de dependencia " , Actas de la Conferencia Conjunta de la 47ª Reunión Anual de la ACL y la 4ª Conferencia Conjunta Internacional sobre Natural Procesamiento del lenguaje de la AFNLP , Asociación de Lingüística Computacional,2 de agosto de 2009, p. 342–350 ( ISBN 9781932432459 , leer en línea )
(en) Koby preparador y Yoram cantante , " algoritmos en línea ultraconservadores para los problemas multiclase " , The Journal of Machine Learning Investigación , vol. 3,1 st de marzo de de 2003, p. 951–991 ( ISSN 1532-4435 , DOI 10.1162 / jmlr.2003.3.4-5.951 , leer en línea )
(en) Wenzhe Pei , Tao Ge y Baobao Chang , “ Un Neural eficaz modelo de red a la Dependencia de análisis basado en el gráfico ” , Actas de la 53ª Reunión Anual de la Asociación de Lingüística Computacional y la 7ª Conferencia Internacional Conjunta sobre Natural Procesamiento del lenguaje (Volumen 1: Artículos extensos) , Asociación de Lingüística Computacional, vol. 1,2015, p. 313–322 ( DOI 10.3115 / v1 / P15-1031 , leer en línea )
CJ van Rijsbergen, Recuperación de información , Butterworths, 1975.
(in) S. Abney , S. Flickenger , C. Gdaniec y C. Grishman , " Procedimiento para comparar cuantitativamente la cobertura sintáctica de las gramáticas inglesas " , Actas del taller es Speech and Natural Language Association for Computational Linguistics,19 de febrero de 1991, p. 306–311 ( DOI 10.3115 / 112405.112467 , leer en línea )
R. Grishman, C. Macleod y J. Sterling, “Evaluación de estrategias de análisis sintáctico utilizando archivos de análisis estandarizados”, en Actas de la Tercera Conferencia sobre Procesamiento del Lenguaje Natural Aplicado (ANLP) , Trento, Italia, p. 156-161, 1992.
(en) Sabine Buchholz y Erwin Marsi , " La tarea compartida de CoNLL-X es el análisis de dependencias multilingües " , Actas de la Décima Conferencia sobre Aprendizaje Computacional del Lenguaje Natural (CoNLL-X) , Asociación de Lingüística Computacional,8 de junio de 2006, p. 149-164 ( DOI 10.3115 / 1596276.1596305 , leído en línea , consultado el 11 de junio de 2018 )

Ver también

Bibliografía

Daniel Jurafsky y James H. Martin, Procesamiento del habla y el lenguaje (segunda edición), Prentice Hall,16 de mayo de 2008, 1024 p.
Nitin Indurkhya y Fred J. Damerau (ed.), Manual de procesamiento del lenguaje natural (segunda edición), Chapman & Hall,22 de febrero de 2010, 702 p.
AV Aho y JD Ullman, La teoría del análisis, traducción y compilación , vol. 1. Prentice Hall, 1972.
Christophe Moor, Análisis de dependencias multilingües de texto sin formato a dependencias universales: la entrada de CLCL , tesis de maestría, Universidad de Ginebra, 2018.

enlaces externos

Analizador de componentes históricos del

analizador de Collins basado en gramáticas libres de contexto probabilísticas lexicalizadas

Analizador de dependencia estadística

MaltParser basado en transiciones (implementado en Java)

Analizador de dependencias basado en

gráficos MSTParser (Java)

Analizador de dependencia de

IDP basado en transiciones y modelo probabilístico generativo, integrando una red neuronal recurrente (C)

Analizador de dependencia reciente de

Stanford Parser basado en transiciones e integración de una red neuronal <img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">