Download Como_maquina_comprende

¿Cómo hacer para que una máquina
comprenda el LN?
Curso de Lingüística Computacional. Heiner Mercado Percia
PROBLEMA

¿Qué hacer para que una máquina reconozca y
genere LN?
 Debemos
encontrar los medios técnicos y
conceptuales para resolver este problema de manera
automática.
 La Ingeniería de software busca un procedimiento
ejecutable de manera automática que resuelva este
problema -> busca un algoritmo.
ALGORITMOS
Algoritmo es el conjunto finito de instrucciones
que configuran el procedimiento paso a paso
para resolver un determinado problema en un
tiempo finito.
 Un programa de computadora es un algoritmo
que le dice a la computadora los pasos
específicos para llevar acabo una tarea. Los
algoritmos son rigurosamente definidos para que
la computadora pueda interpretarlos.

ALGORITMOS



Los algoritmos pueden escribirse en pseudocódigo, lo que
también los hace fáciles de entender.
También pueden representarse de forma sencilla por
medio de diagramas de flujo. De esta manera, los
algoritmos son más "universales", pues no dependen de
un lenguaje de programación específico.
En programación, los algoritmos se implementan en forma
de sentencias en algún lenguaje de programación. La
forma de escribir los algoritmos dependen del lenguaje de
programación. Estos son los algoritmos que pueden ser
interpretados por una computadora y así ser ejecutados.
EJEMPLO

Problema: Quiero saber cuantas veces aparece la
palabra “automático” en un corpus.
 Leer
caracteres de un archivo
 Reconocer una palabra
 Comparar una palabra con “automático”
 Contar el número de ocurrencias
ALGORITMO (DIAGRAMA DE FLUJO)
Inicio

Un DF es una
representación
gráfica de la
secuencia de pasos
que se realizan
para obtener un
resultado.
Paso1 : Leer caracteres
Paso 2: Reconocer palabras
Paso 3: Comparar cada
palabra con “automático”
Paso 4: Contar el número
de ocurrencias
Fin
ALGORITMO (PSEUDOCÓDIGO)
Nb Ocurrencias = 0
PARA todos los caracteres del texto HACER
palabra detectada =“”
leer un carácter
adjuntar carácter
EN TANTO QUE no fin de palabra HACER
leer un carácter
adjuntar carácter a palabra detectada
FIN TANTO QUE
SI palabra detectada =“automático”
ENTONCES Nb ocurrencias + 1
FIN PARA
Esto debe traducirse
en un lenguaje de
máquina o un
lenguaje de alto nivel
(PHP, PERL, C++, etc.)
Los lenguajes de alto
nivel son programas
que traducen órdenes
escritas en lenguaje
humano.
ALGORITMOS Y EL LN

La IA y la Traducción Automática buscan
algoritmos que permitan tratar automáticamente
el LN.
 Comienza
el problema de la calculabilidad o
computabilidad (Teoría de la complejidad
computacional)
 Un problema es computable si tiene una solución
algorítmica.
 Un computador no puede resolver un problema si no
hay una solución algorítmica
COMPUTABILIDAD
El estudio de los procesos
computacionales conduce
a una clasificación de los
problemas en
solucionables y no
solucionables.
Pensemos por un
momento en problemas
que queremos resolver.
¿Se puede resolver cualquier problema de
manera automática?
 ¿Podrá existir una máquina que logre resolver
todo tipo de problemas automáticamente?

 Limitaciones
de orden teórico (problema con solución
–calculable-)
 Limitaciones técnicas
 Evaluación de la complejidad (cantidad de recursos
necesarios: tiempo de ejecución, uso de memoria,
eficiencia, etc.)
COMPLEJIDAD
Problema 1: contar en un corpus las ocurrencias de
la palabra “lenguaje”
 Problema 2: contar las veces en que aparecen las
palabras “lenguaje” y “natural”

Solución 1: lectura secuencial de un archivo con un
contador y una comparación.
 Solución 2a: lectura secuencial de un archivo con 1
bucle, 2 contadores y 2 comparaciones (El # de
operaciones depende del número de palabras)
 Solución 2b: 2 lectores secuenciales con 1 contador
(El doble de operaciones pero utiliza sólo un
contador - memoria)

ALGORITMOS Y EL LN
Se buscan algoritmos capaces
de manipular series de
símbolos y cadenas de
símbolos (caracteres)
 Algoritmos que permitan a
una máquina reconocer,
interpretar y generar LN.

Máquina de Turing
ALGORITMOS Y EL LN
Reconocimiento: (teoría de los autómatas) se
buscan algoritmos que permitan, dado un lenguaje L
y una cadena x determinar si x є L o x є L
 Interpretación: tiene que ver con la semántica de los
lenguajes. Se intenta formalizar el significado de las
sentencias de un lenguaje
 Generación: consiste en encontrar mecanismos que
permitan enumerar las cadenas que pertenecen a
un lenguaje. Estos mecanismos son las gramáticas.

ESTUDIO DE LOS LENGUAJES
Tradicionalmente el estudio de los leguajes se divide
en dos partes: el análisis de la estructura de las
frases (gramática) y el estudio de su significado
(semántica).
 A su vez, el estudio de la gramática se subdivide en
morfología, sintaxis, y fonética.
 En los años 50 Chomsky introdujo la teoría de las
gramáticas transformacionales o teoría de lenguajes
formales que convirtió la lingüística en una ciencia.
 Esta teoría facilitó el estudio tanto de la LN como la
formalización de los lenguajes de programación para
computadores

ESTUDIO DE LOS LENGUAJES

Un Lenguaje L es:
 Conjunto
infinito de oraciones
 Número finito de símbolos
(palabras)
 Número finito de
combinaciones bien formadas
 Reglas que organizan las
combinaciones posibles de
formación
ESTUDIO DE LOS LENGUAJES
Una gramática formal es un objeto o modelo
matemático que permite especificar un lenguaje o
lengua, es decir, es el conjunto de reglas capaces de
generar todas las posibilidades combinatorias de ese
lenguaje.
 La expresión «gramática formal» tiene dos sentidos:

gramática de un lenguaje formal
 descripción formal de parte de la gramática de un
lenguaje natural o sintaxis.


Hay distintos tipos de gramáticas formales que
generan lenguajes formales, veamos:
GRAMÁTICA FORMAL

Un lenguaje L está formado por el cuádruplo VN,
VT, P, O en el que:
 VN
conjunto finito de símbolos no-terminales o
variables (categorías sintácticas)
 VT conjunto finito de símbolos terminales (palabras)
 P conjunto finito de reglas de producción que suelen
adoptar la forma  ->  donde  y  pueden ser
VT y VN
 O símbolo inicial o axioma (Oración)
JERARQUÍA DE LAS GRAMÁTICAS DE CHOMSKY
Chomsky clasificó los lenguajes en una jerarquía
inclusiva de cuatro grados:
Máquinas que pueden
analizar cada lenguaje
JERARQUÍA DE LAS GRAMÁTICAS DE CHOMSKY

Gramática tipo 0: pertenece a la semántica de
los lenguajes naturales y artificiales. No tienen
restricción alguna. Está relacionado con todos los
problemas computables o recursivamente
enumerables (solucionables por la máquina de
Turing)
JERARQUÍA DE LAS GRAMÁTICAS DE CHOMSKY

Gramática tipo 1: Lenguajes sensibles al
contexto. Introducen algunas limitaciones en la
estructura gramatical, aunque permite que el
valor sintáctico de las palabras dependa de la
posición en la frase, es decir, de su contexto.
Ejemplo: Lengua africana bambara y el alemánsuizo.
xz -> xz
JERARQUÍA DE LAS GRAMÁTICAS DE CHOMSKY
Gramática tipo 2: Lenguajes independientes del
contexto. El valor sintáctico de una palabra es
totalmente independiente de su posición en la frase.
Ejemplo: todos los lenguajes de computadores.
 El término libre de contexto se refiere al hecho de
que el símbolo no terminal V puede siempre ser
sustituido por w sin tener en cuenta el contexto en
el que ocurra.

V -> w
JERARQUÍA DE LAS GRAMÁTICAS DE CHOMSKY

Gramática tipo 3: Lenguajes regulares. Se suelen
describir mediante expresiones regulares. Sus
palabras contienen regularidades. Una ER
describe un conjunto de cadenas sin enumerar
sus elementos. Por ejemplo, el grupo formado
por las cadenas Handel, Händel y Haendel se
describe mediante el patrón "H(a|ä|ae)ndel".
VT ->
VN (A->t)
VT -> VN VT (A->tN)
EMPLEO DE GRAMÁTICAS

Aplicaciones:
 Traducción
Automática
 Comprensión y reconocimiento del lenguaje oral
 Interfaces de LN para comunicación hombre – máquina
 Búsqueda de datos en bd.
 Enseñanza asistida por ordenador
 Comprensión y tratamiento de textos (lo más utilizado)