Nota del T: Sigo traduciendo el libro de Peter Norvig. Son complicadas algunas funciones, le aconsejo que las vaya construyendo a medida que lee. Si hay problemas con alguna traducción les ruego me avisen.
Este capítulo y el resto de la
parte 1 examina tres programas más de IA bien conocidos de la década de 1960.
Eliza mantiene una conversación con el usuario en la que es simulada una
psicóloga. STUDENT resuelve problemas de los que son encontrados en los libros
de álgebra, y MACSYMA resuelve una variedad de problemas matemáticos,
incluyendo cálculo diferencial e integral. Desarrollaremos versiones de los
primeros dos programas que duplican la mayoría de las características
esenciales, pero para el tercero implementaremos solo una pequeña parte de las capacidades
del programa original.
Los tres programas usan una
técnica llamada “coincidencia de patrones”. La parte 1 sirve para mostrar la
versatilidad –y también las limitaciones- de esta técnica.
De los tres programas, los
primeros dos procesos introducen un Español plano, y los últimos dos resuelven
problemas no triviales de matemática, de esta manera hay algunas bases para
describirlos como “inteligentes”. Por otro lado, veremos que esta inteligencia
es por lejos una ilusión, y que Eliza en particular fue diseñada para demostrar
esta ilusión, no para ser un programa “serio” de IA.
ELIZA fue uno de los primeros
programas que tenía al idioma Inglés como salida tanto así como en la entrada.
El programa fue llamado después la heroína de Pygmalion, que fue enseñada para
hablar Inglés correctamente a través de un dedicado profesor. El principal
desarrollador de ELIZA fue el profesor Joseph Weizenbaum del MIT, publicada en
el documento sobre ELIZA en Enero del 1966 para el problema de la comunicación entre
máquinas de cómputo. La introducción a ese documento es reproducida enteramente
aquí:
Se dice que explicar algo es explicarlo en profundidad. Esta máxima está aquí para mostrar como es el área de programación de
ordenadores, especialmente en lo que se concierne a programación heurística e
inteligencia artificial. En estos dominios las maquinas son hechas para
comportarse de maneras maravillosas, obteniendo suficiente para deslumbrar
incluso a la mayoría de los observadores experimentados. Pero una vez que un
programa particular es desenmascarado, una vez que el trabajo interno es
explicado en un lenguaje suficientemente plano para inducir a la comprensión,
su magia se desmorona, su puesto es revelado como una mera colección de
procedimientos, cada uno de los cuales es comprensible. El observador se dice a
si mismo, “Yo podría haber escrito eso”. Con ese pensamiento el mueve el
programa en cuestión del estante marcado como “inteligente”, al de las curiosidades, encajando en la discusión solo con personas menos ilustradas que
él.
El objeto de este documento es
causar solo una re-evaluación del programa a ser “explicado”. Pocos programas
necesitan eso.
Déjeme explicar el punto sobre
que el objeto principal de este libro es causar que el lector se diga a sí
mismo, “yo podría haber escrito eso”. Esta será la esperanza en algunos casos
debido a que el lector haya ganado algo, y no solamente porque el programa en
cuestión haya perdido su habilidad para deslumbrar.
Empecemos nuestra investigación
sobre ELIZA mirando un ejemplo de diálogo desde el artículo de Weizenbaum.
ELIZA fue diseñada para ser instruida por una variedad de guiones, o patrones
de interacción. En efecto tiene varios guiones, incluyendo algunos en
alemán y galés. Pero el único guión que fue usado para cualquier extensión fue
en inglés, y esto hace ELIZA emular un psicoanalista Rogeriano. Los Rogerianos no tienen “directivas” – ellos intentan dejar al paciente que se revele a sí
mismo. Este es un guion sencillo de seguir para ELIZA, porque este encierra el hecho
de estar pasivo y reaccionar, antes que voluntariamente generar nueva
información. En el listado siguiente, la entrada del usuario está en oraciones,
tanto en mayúsculas como minúsculas, y ELIZA responde solo en mayúsculas:
Los hombres son todos iguales.
EN QUE SENTIDO
Ellos están siempre
fastidiándonos sobre una cosa u otra.
PUEDES SER MAS ESPECIFICA
Bueno, mi novio me hizo venir
aquí.
TU NOVIO TE HIZO VENIR AQUÍ
El me dice que estoy deprimida a
menudo.
ME APENA ESCUCHAR QUE ESTES
DEPRIMIDA
Es verdad. No soy feliz.
PIENSAS VENIR AQUÍ PARA QUE TE
AYUDE A SER FELIZ.
Necesito alguna ayuda, eso me parece.
QUE PASARIA SI TE OFREZCO ALGUNA AYUDA
Tal vez aprendería a llevarme bien con mi madre.
HABLAME MAS ACERCA DE TU FAMILIA
Esto parece impresionante; el
programa está respondiendo razonablemente a una variedad de entradas y muestra
una verdadera “comprensión”. Pero, como explica Weizenbaum, esta apariencia es
una ilusión, y el programa ha reducido la difícil tarea de comprender a través
de un cuidadoso reconocimiento, transformando, y haciendo eco de las piezas de
entrada. El procedimiento es observar patrones específicos, basados en una
palabra clave o palabras en la entrada. Por ejemplo, siempre que el programa
aparece la palabra “iguales” o “mismo”, esta escribe un mensaje en pantalla
respondiendo sobre cosas que son semejantes, en este caso “EN QUE SENTIDO”.
Otros patrones son más complicados. Cerca del último intercambio, ELIZA arroja
lejos todo lo que esta después de la coma, y luego usa un patrón que mira las
entradas de la forma “necesito X” y lo transforma en la salida “Que pasaría si
te ofrezco X”, donde X es la frase “alguna ayuda” en este caso. La gran ventaja
de este enfoque es que la respuesta se hará en base a una variedad de entradas:
“necesito vacaciones” y se obtendrá “Que pasaría si te ofrezco vacaciones”. Esto
ocurrirá automáticamente, sin tener que decirle al programa la diferencia entre
“alguna ayuda” y “vacaciones”. La desventaja es que el programa algunas veces
hará respuestas tontas: “necesito esto como un agujero en la cabeza” será
respondido con “Que pasaría si te ofrezco esto como un agujero en la cabeza”.
En efecto, el programa solo construye cualquier sentido en todo caso si recibe
entradas desde alguien que construye sentido –y alguien que interpreta sus respuestas caritativamente. Cuando se le da “necesito gibble pliz zzq”, ELIZA
replicaría “Que pasaría si te ofrezto gibble plix zzq”, sin ningún indicio de
que algo está mal. Otro ejemplo del programa original ELIZA cuando mantiene una
comunicación con otro programa PARRY, que fue escrito por el Dr. Kenneth Colby
para simular un comportamiento paranoico. Parte de esa conversación sigue a
continuación, con ELIZA nuevamente solo en mayúsculas y PARRY en oraciones,
tanto en mayúsculas como minúsculas:
No entiendo tus motivaciones.
¿QUE NO ENTIENDES DE MIS MOTIVACIONES?
¿No debería ser yo?
¿POR QUE DICES ESO AHORA?
Así es la manera.
SUPONGA QUE LA MANERA NO FUERA ASI.
¿Así?
NO ESTOY SEGURA DE ENTENDERTE COMPLETAMENTE.
Insistes demasiado en las mismas preguntas.
¿QUE TE SUGIERE ESA SEMEJANZA?
No te entiendo.
¿QUE ES LO QUE DESEAS ENTENDER?
Esto sugiere que PARRY el vecino
de ELIZA, tiene una comprensión profunda del diálogo. Cuando hay un humano que
tiene la mayoría de la carga para llevar adelante la conversación, estos
programas pueden ser convincentes, pero cuando el humano está fuera de la
conversación, las debilidades del programa son reveladas.
Describiendo y especificando ELIZA
Ahora que tenemos una idea de lo
que es ELIZA, podemos comenzar la descripción y especificación del programa, y
eventualmente movernos hacia la implementación y el debugging. El algoritmo de
ELIZA puede ser descrito simplemente como: (1) leer una entrada, (2) buscar un
patrón que coincida con la entrada, (3) transformar la entrada en una
respuesta, y (4) mostrar en pantalla la respuesta. Estos cuatro pasos son
repetidos para cada entrada.
La especificación e
implementación de los pasos (1) y (4) son triviales: para (1), usa la función
interna read para leer una lista de palabras, y para (4) usa print para mostrar
en pantalla la lista de palabras en la respuesta.
Por supuesto, hay algunos
inconvenientes para esta especificación. El usuario tendrá que escribir una
lista real –usando paréntesis- y el usuario no puede usar caracteres especiales
para leer, tales como comillas, comas y períodos. Así nuestra entrada no puede
estar sin restricciones tal como el dialogo del ejemplo, pero ese es un pequeño
precio a pagar para la conveniencia de tener la mitad del problema resuelto.
Coincidencia de patrones
La parte difícil está en los
pasos (2) y (3) –esta noción de coincidencia de patrones y transformación. Hay
cuatro cosas relacionadas: un patrón general y la respuesta, y una entrada
específica y la transformación de esa entrada. Desde que accedimos a
representar las entradas como una lista, esto permite tratar a otros
componentes como listas también. Por ejemplo, podemos tener:
Patrón: (necesito X)
Respuesta: (¿Qué pasaría si te ofrezco X?)
Entrada: (necesito vacaciones)
Transformación: (¿Qué pasaría si te ofrezco vacaciones?)
El programa de coincidencia de
patrones debe hacer coincidir los literales i con i, necesito con necesito, y a
con a, como así también hacer coincidir la variable X con vacaciones. Esto
presupone que hay algunas maneras de decidir que X sea una variable y que
necesito no lo es. Debemos arreglar el sustituto vacaciones para X con la
respuesta, para obtener la transformación final.
Ignorando por un momento el
problema de transformar el patrón en la respuesta, podemos ver que esta noción de coincidencia
de patrones es solo una generalización de la función Lisp equal. Primero
mostramos la función simple-equal, que es como la función interna equal, y la
función patron-coincide que es definida para manejar variables de coincidencia
de patrones:
(defun simple-equal (x y)
"¿Son x e y
iguales? (No hace revision dentro de cadenas.)"
(if (or (atom x)
(atom y))
(eql x y)
(and (simple-equal
(first x) (first y))
(simple-equal (rest x) (rest y)))))
(defun patron-coincide (patron entrada)
"¿Hay
coincidencia entre patron y entrada? Cualquier variable puede coincidir con
cualquier cosa."
(if (variable-p
patron)
t
(if (or (atom
patron) (atom entrada))
(eql
patron entrada)
(and
(patron-coincide (first patron) (first entrada))
(patron-coincide (rest patron) (rest
entrada))))))
Antes de que podamos avanzar,
necesitamos decidir sobre una implementación para las variables de
patron-coincide. Podríamos, por instancia, decir que solo un cierto conjunto de
símbolos, tales como {X,Y,Z} son variables. Alternativamente, podríamos definir
una estructura de tipo de variable, pero entonces no tendríamos que escribir
algo como (make-variable :name ‘X) cada vez que buscamos una. Otra opción
podría ser el uso de símbolos, pero para distinguir variables de constantes por
el nombre del símbolo. Por ejemplo, en
Prolog, las variables comienzan con letras mayúsculas y las constantes con
minúsculas. Pero Common Lisp no es sensible al contexto, así que esto no
funcionará. En lugar de ello, hay una tradición en los programas de IA basados
en Lisp donde las variables son símbolos que comienzan el carácter de pregunta.
Hasta aquí hemos repartido símbolos como átomos –objetos sin estructura
interna. Pero las cosas son siempre más complicadas de lo que aparentan al
principio y, tanto en Lisp así como en física, lo que provoca que incluso los
átomos tengan componentes. En partículas, los símbolos tienen nombres, que son
cadenas de caracteres y son accesibles a través de la función symbol-name. Las
cadenas en cambio tienen elementos que son caracteres, accesibles a través de
la función char. El carácter ‘7’ es denotado por la secuencia de
auto-evaluación #\? De esta manera el predicado variable-p puede ser definido
como sigue a continuación, y ahora tenemos un programa completo de patrón de
coincidencias:
(defun variable-p (x)
"¿x es una
variable? (un simbolo que comienza con '?')"
(and (symbolp x)
(equal (char (symbol-name x) 0) #\?)))
> (patron-coincide '(necesito ?X) '(necesito vacaciones))
T
> (patron-coincide '(necesito ?X) '(realmente necesito
vacaciones))
NIL
En cada caso obtenemos la
respuesta correcta, pero no obtenemos ninguna indicación de lo que es ?X, de esta manera no podríamos sustituirla
dentro de la respuesta. Necesitamos modificar patron-coincide para que devuelva
algún tipo de tabla de variables y sus correspondientes valores. En la
construcción de esta opción, el programador experimentado en Common Lisp puede
ganar algo de tiempo siendo oportunista: reconocer cuando hay una función
existente que hará una gran parte de la tarea. Lo que buscamos es sustituir
valores para variables a través de la respuesta. El programador atento haría
referencia al índice de este libro o de un manual de referencia de Common Lisp
y buscará las funciones substitute, subst y sublis. Todas estas sustituyen algunas expresiones nuevas por unas
anteriores con una expresión. Sublis en cambio es la más apropiada porque es la
única que nos permite hacer varias sustituciones al mismo tiempo. Sublis toma
dos argumentos, el primero es una lista de pares anterior-nuevo, y el segundo
es una expresión en la que hace las sustituciones. Para cada uno de los pares,
el car es reemplazado por el cdr. En otras palabras, formaríamos cada par con
algo como (cons anterior nuevo). (Así como una lista de pares es conocida como
una lista de asociación, o a-list, debido a que esta asocia claves con valores.
En términos del ejemplo abajo, usaríamos:
> (sublis '((?X . vacaciones))
'(Que
pasaría si te ofrezco ?X ?))
(QUE PASARIA SI TE OFREZCO VACACIONES ?)
Nota: Quisiera poner el signo de pregunta ¿ de apertura,
pero algunos interpretes no los tienen.
Ahora necesitamos arreglar nuestro patron-coincide para que
devuelva una a-lisp, mejor que solo T para un resultado exitoso. Aquí tenemos
un primer intento:
(defun patron-coincide (patron entrada)
"¿Coincide el
patron con la entrada? CUIDADO: versión con errores."
(if (variable-p
patron)
(list (cons
patron entrada))
(if (or (atom
patron) (atom entrada))
(eql
patron entrada)
(append
(patron-coincide (first patron) (first entrada))
(patron-coincide (rest patron) (rest
entrada))))))
Esta implementación luce
razonable: devuelve una a-list de un elemento si el patrón es una variable, y
une las a-list si el patrón y la entrada son listas. Sin embargo, hay varios
problemas. Primero, la verificación (eql patron entrada) puede devolver T, que
no es una lista, de esta manera append se quejará. Segundo, el mismo test debe
devolver nil, lo que indicaría una falla, pero este será tratado como una
lista, y será unido al resto de la respuesta. Tercero, no podemos distinguir
entre el caso donde el patron falla –y devuelve nil- contra el caso donde todo
coincide, pero no hay variables, devolviendo una a-lista nula. (Este es el
problema del semipredicado). Cuarto, queremos las uniones de variables para
acceder –si ?X es usado dos veces en el patrón, no queremos hacer coincidir dos
valores distintos en la entrada. Finalmente, patron-coincide es ineficiente
para verificar tanto el primero como el resto de las listas, incluso cuando la
primera parte correspondiente no coincide. (¿No es increíble que haya cinco
errores en una función de siete líneas?)
Podemos resolver estos problemas
aceptando dos convenciones. Primero, es más conveniente hacer que
patron-coincide sea un verdadero predicado, de esta manera aceptamos que
devuelve nil solo para indicar falla. Lo que ocurre es que necesitaremos un
valor nil-anonimo para representar la lista vacía. Segundo, si estamos yendo
hacia una consistencia de los valores de las variables, entonces el first
tendrá que saber cuál es el rest. Podemos lograr esto pasando la lista de
uniones como un tercer argumento para patron-coincide. Lo haremos como un
argumento opcional, porque queremos poder decir simplemente (patron-coincide a
b).
Para abstraer más allá de estas
decisiones de implementación, definiremos las constantes falla y sin-uniones
para representar los dos valores devueltos con problemas. La forma especial
defconstant es usada para indicar que estos valores no cambiarán. (Es opcional
tener nombres de variables que comienzan y terminan con asteriscos, pero esta
convención usualmente no se usa para las constantes). El motivo es que los
asteriscos gritan, “Cuidado! Puedo ser cambiado por algo fuera de este alcance
léxico”. Las constantes, por supuesto, no pueden ser cambiadas.
(defconstant falla nil "Indica que patron-coincide
falla")
(defconstant sin-uniones '((t . t))
"Indica el
éxito de patron-coincide, sin variables.")
Luego, abstraemos más alla con el uso de assoc, introduciendo
las siguientes cuatro funciones:
(defun obtener-union(var uniones)
"Busca un par
(variable . valor) en una lista de uniones."
(assoc var uniones))
(defun union-val(union)
"Obtiene el
valor de una union."
(cdr union))
(defun buscar(var uniones)
"Obtiene el
valor (para var) de una lista de uniones."
(union-val
(obtener-union var uniones)))
(defun extender-uniones (var valor uniones)
"Agrega un par
(var . valor) a una lista de uniones."
(cons (cons var
valor) uniones))
Ahora que las variables y las
uniones están definidas, patron-coincide es fácil. Este consiste de cinco
casos. Primero, si la lista de uniones es falla, entonces la coincidencia falla
(debido a que algunas coincidencias previas deben haber fallado). Si el patrón
es una sola variable, entonces la coincidencia devuelve lo que sea que coincida
con la variable; ya sea la lista de uniones existente, una extendida, o falla.
Luego, tanto el patron como la entrada son listas, primero llamaremos a
patron-coincide recursivamente sobre el primer elemento de cada lista. Este
devuelve una lista de uniones (o falla), la que usaremos para hacer coincidir
con el resto de las listas. Este es el único caso que invoca a una función no
trivial, asi que es una buena idea probar informalmente que la función
terminará: cada una de las dos llamadas recursivas redice el tamaño tanto del
patron como de la entrada, y patron-coincide verifica el caso de patrones
atómicos y entradas, de esta manera la función como un todo debe devolver
eventualmente una respuesta (a menos que patrón y entrada tengan un tamaño
infinito). Si ninguno de estos cuatro casos ocurre, entonces la coincidencia
falla.
(defun patron-coincide (patron entrada &optional
(uniones sin-uniones))
"Coincidencia
de patrones preparando la entrada en el contexto de las uniones"
(cond ((eq uniones
falla) falla)
((variable-p
patron)
(coincidir-variable patron entrada uniones))
((eql
patron entrada) uniones)
((and
(consp patron) (consp entrada))
(patron-coincide (rest patron) (rest entrada)
(patron-coincide (first patron) (first
entrada)
uniones)))
(t
falla)))
(defun coincidir-variable (var entrada uniones)
"Coincide VAR
con entrada? Usa (o actualiza) y devuelve las uniones."
(let ((union (obtener-union
var uniones)))
(cond ((not union)
(extender-uniones var entrada uniones))
((equal entrada (union-val union)) uniones)
(t falla))))
Ahora podemos probar patron-coincide y ver cómo trabaja:
> (patron-coincide '(necesito ?X) '(necesito vacaciones))
((?X . VACACIONES) (T . T))
La respuesta es una lista de
uniones de variable que esta dotadas de notación de pares; cada elemento de la
lista es una par (variable . valor). (T . T) es un residuo de sin-uniones. Esto
no hace daño realmente, pero podemos eliminarlo haciendo extender-uniones un
poco más complicada:
(defun extender-uniones(var valor uniones)
"Agrega un par
(var . value) a la lista de uniones."
(cons (cons var
valor)
;; Una
ver que agregamos una union "real",
;;
podemos eliminar el tonto sin-uniones
(if (eq
uniones sin-uniones)
nil
uniones)))
> (sublis (patron-coincide '(necesito ?X) '(necesito
vacaciones))
'(que pasaria si te ofrezco ?X ?))
(QUE PASARIA SI TE OFREZCO VACACIONES ?)
> (patron-coincide '(necesito ?X) '(realmente necesito
vacaciones))
NIL
> (patron-coincide '(esto es facil) '(esto es facil) )
((T. T))
> (patron-coincide '(?X es ?X) '((2 + 2) es 4))
NIL
> (patron-coincide '(?X es ?X) '((2 + 2) es (2 + 2)))
((?X 2 + 2))
> (patron-coincide '(?P necesito . ?X) '(yo necesito unas largas vacaciones))
((?X UNAS LARGAS VACACIONES) (?P . YO))
Nota del T: El problema con el
español es que las conjugaciones del verbo dependen de persona y numero.
Note la distinción entre NIL y (
(T . T) ). El último tratamiento es exitoso, pero no hubieron uniones para
devolver. Recuerde también que (?X 2 + 2) es lo mismo que (?X . (2 + 2)).
Una implementación más poderosa
de patron-coincide se da en el capítulo 6. Otra implementación es dada más
adelante. Es más eficiente pero más incómoda de usar.
Coincidencia de Segmentos Patrones
En el patrón (?P necesito . ?X),
la variable ?X coincide con el rest de la lista de entrada, sin importar cuál
es su longitud. Esto está en contraste con ?P, que puede solo coincidir con un
solo elemento, llamado, el primer elemento de la entrada. Para muchas
aplicaciones de coincidencia de patrones, esto está bien; buscamos solamente
hacer coincidir los elementos correspondientes. Sin embargo, ELIZA es algo
diferente en que necesita llevar una cuenta para variables en cualquier
posición que coincida una secuencia de ítems en la entrada. Llamaremos a tales
variables de segmento. Necesitaremos una notación para diferenciar variables de
segmento de las variables normales. Las posibilidades caen en dos clases: ya
sea que usemos átomos para representar variables de segmento y distinguirlas
por alguna convención ortográfica (como hicimos para distinguir variables de
constantes) o que usemos construcciones no atómicas. Elegiremos la última,
usando una lista de la forma (?* variable) para denotar variables de segmento.
El símbolo ?* es elegido porque
combina la noción de variable con la notación de estrella de Kleene. De esta
manera, el comportamiento que buscamos para patron-coincide es ahora:
> (patron-coincide '((?* ?p) necesitamos (?* ?X))
'(El Sr Perez
y yo necesitamos vacaciones))
((?P EL SR PEREZ Y YO) (?X VACACIONES))
En otras palabras, cuando el
patrón y la entrada son listas y el primer elemento del patrón es una variable
de segmento, la variable hará coincidir la parte inicial de la entrada, y el
resto del patrón se intentará coincidir
con el resto. Podemos actualizar patron-coincide para llevar una cuenta para esto
agregando una simple cláusula cond. Definir el predicado para verificar las
variables de segmento es fácil también:
(defun patron-coincide (patron entrada &optional
(uniones sin-uniones))
"Coincidencia
de patrones preparando la entrada en el contexto de las uniones"
(cond ((eq uniones
falla) falla)
((variable-p
patron)
(coincidir-variable patron entrada uniones))
((eql
patron entrada) uniones)
((segmento-patron-p
patron) ;***
(segmento-coincide patron entrada
uniones)) ;***
((and
(consp patron) (consp entrada))
(patron-coincide (rest patron) (rest entrada)
(patron-coincide (first patron) (first
entrada)
uniones)))
(t
falla)))
(defun segmento-patron-p (patron)
"Es este un segmento patron: (?* var) . pat)"
(and (consp patron)
(comienza-con (first patron) '?*)))
(defun comienza-con (list x)
"Es esta una lista cuyo primer elemento es x?"
(and (consp list) (eql (first list) x)))
Para escribir segmento-coincide,
la pregunta importante es cuánto de la entrada va a coincidir con el segmento.
Una respuesta es mirar el próximo elemento del patrón (el que está después de
la variable de segmento) y ver que en esa posición eso ocurre en la entrada. Si
no ocurre, el patrón total nunca puede coincidir, y debería fallar. Si eso
ocurre, pasa a su posición. Si queremos hacer coincidir la variable preparando
la parte inicial de la entrada, pasa por arriba. Pero primero tenemos que ver
si el resto del patrón coincide con el resto de la entrada. Si esto es así se
hace una llamada recursiva a patron-coincide. El resultado de esta llamada
recursiva es llamado b2. Si b2 es exitoso, entonces vamos hacia
adelante y hacemos coincidir la variable de segmento preparando la subsecuencia
inicial.
El truco es que b2 falla. No
queremos darlo completamente, porque puede ser que si la variable de segmento
coincide con una subsecuencia más larga de la entrada, entonces el resto del
patrón coincidiría con el resto de la entrada. De esta manera queremos intentar
nuevamente la función segmento-coincide, pero forzándola a considerar una
coincidencia más larga para la variable. Esto se hace introduciendo un
parámetro opcional, inicio, que es inicialmente 0 y se incrementa con cada
falla. Observe que esta política deja afuera la posibilidad de cualquier tipo
de variable siguiendo una variable de
segmento. (Luego de remover esta restricción).
(defun segmento-coincide(patron entrada uniones
&optional (inicio 0))
"Coincide el
segmento patron ((?* var) . pat) preparando la entrada."
(let ((var (second
(first patron)))
(pat
(rest patron)))
(if (null pat)
(coincidir-variable
var entrada uniones)
;; Asumimos que
pat comienza con una constante
;; En otras
palabras, un patron no puede tener 2 vars consecutivas
(let ((pos
(position (first pat) entrada
:start inicio :test #'equal )))
(if
(null pos)
falla
(let ((b2 (patron-coincide pat (subseq
entrada pos) uniones)))
;;Si esta coincidencia falla, intenta otra
mas larga
;;Si esto funciona, verifica que las
variables coincidan
(if (eq b2 falla)
(segmento-coincide
patron entrada uniones (+ pos 1))
(coincidir-variable var (subseq entrada 0
pos) b2))))))))
Vemos algunos ejemplos de coincidencia de patrones:
> (patron-coincide '((?* ?p) necesitamos (?* ?x))
'(El Sr Gomez
y yo necesitamos vacaciones))
((?P EL SR GOMEZ Y YO) (?X VACACIONES))
> (patron-coincide '((?* ?x) es un (?* ?y)) '(que el es
es un tonto))
((?X QUE EL ES) (?Y TONTO))
El primero de estos ejemplos
muestra un caso bastante simple: ?P coincide con todo lo necesario, y ?X
coincide con el resto. El siguiente ejemplo encierra el caso más complicado.
Primero ?X coincide con todo lo que esta primero (esta es la posición 2, con la
cuenta comenzando en 0 en Common Lisp). Pero luego el patrón falla al coincidir
la entrada, de esta manera segmento-coincide intenta nuevamente iniciar con la
posición 3. Esta vez todo funciona; es coincide con es, un coincide con un, y
(?* ?Y) coincide con tonto.
Desafortunadamente, esta versión de segmento-coincide no
hace coincidir todo como debería.
Considere el siguiente ejemplo:
> (patron-coincide '((?* ?x) a b (?* ?x)) '(1 2 a b a b 1
2 a b)) => NIL
Esto falla porque ?x coincide con
la subsecuencia (1 2), y luego el resto del patrón coincide exitosamente con el
resto de la entrada, pero al final la llamada coincidir-variable falla, porque
?X tiene dos valores diferentes. La solución es llamar a coincidir-variable
antes de verificar que b2 falle, así nos aseguraremos intentar
segmento-coincide nuevamente con una coincidencia larga sin importar cuál sea
la causa de la falla.
(defun segmento-coincide (patron entrada uniones
&optional (inicio 0))
"Coincide el
segmento patron (?* var) . pat) preparando la entrada."
(let ((var (second
(first patron)))
(pat
(rest patron)))
(if (null pat)
(coincidir-variable
var entrada uniones)
;;Asumimos que
pat comienza con una constante
;;En otras
palabras, un patron no puede tener 2 vars consecutivas
(let ((pos
(position (first pat) entrada
:start inicio :test #'equal)))
(if
(null pos)
falaa
(let ((b2 (patron-coincide
pat (subseq entrada pos)
(coincidir-variable var (subseq entrada 0
pos)
uniones))))
;; Si esta coincidencia falla, intenta otra
mas larga
(if (eq b2 falla)
(segmento-coincide
patron entrada uniones (+ pos 1))
b2)))))))
Ahora vemos que la coincidencia ocurre:
> (patron-coincide '((?* ?x) a b (?* ?x)) '(1 2 a b a b 1
2 a b))
((?X 1 2 A B))
Observe que esta versión de segmento-coincide intenta hacer
coincidir primero lo más corto posible. Podría también ser posible intentar
hacer coincidir primero lo mas largo.
El programa ELIZA: Un traductor basado en reglas
Ahora que tenemos una
coincidencia de patrones funcionando, necesitamos algunos patrones para hacer
coincidir. Algo más, queremos que el patrón esté asociado con respuestas.
Podemos hacer esto inventando una estructura de datos llamada regla, que
consisten de un patrón y una o más respuestas asociadas. Hay reglas en el
sentido en que ellas afirman, “Si tú ves A, entonces responde B o C, seleccionadas
al azar.” Elegiremos la implementación más simple posible para las reglas: como
listas, donde el primer elemento es el patrón y el resto es una lista de
respuestas:
(defun regla-patron (regla) (first regla))
(defun regla-respuesta (regla) (rest regla))
Aquí un ejemplo de una regla:
(((?* ?x) quiero (?* ?y))
(que pasaria si te ofrezco ?y)
(por que quieres ?y)
(suponga que obtiene ?y pronto)
Nota del T: En español tenemos
que usar verbos distintos para decir cosas distintas, en cambio en ingles un
verbo tiene distintos significados. Por ejemplo
want en ingles puede decir varias cosas (querer, necesitar, desear).
Pero en español debemos usar verbos distintos para decir “quiero” “necesito”
“deseo”. También está el tema, no menor, del uso de las distintas conjugaciones
de los verbos según la persona y el número.
Cuando es aplicada en la entrada
(yo quiero verificar este programa), esta regla (cuando es interpretada por el
programa ELIZA) debería replicar una respuesta aleatoria, sustituyendo en el
valor de ?y, y respondiendo con (por que quieres verificar este programa). Ahora
que sabemos lo que hará una regla individual, necesitamos decidir cómo manejar
un conjunto de reglas. Si ELIZA está hecha para cualquier contexto, tendrá que
tener una variedad de respuestas. Así varias reglas pueden ser aplicables a la
misma entrada. Una posibilidad podría ser elegir una regla al azar desde un
montón de reglas teniendo patrones que coinciden con la entrada.
Otra posibilidad es solo aceptar
la primera regla que coincida. Esto implica que las reglas están en una lista
ordenada, antes que un conjunto desordenado. La regla inteligente de ELIZA
puede tomar ventaja de este ordenamiento y arreglo para la mayoría de las
reglas específicas come first, mientras más
reglas vagas están cerca del fin de la lista.
El ELIZA original tiene un
sistema donde cada regla tiene un número de prioridad asociado con ella. La
regla de coincidencia con la más alta prioridad fue elegida. Observe que
poniendo las reglas en orden logra el mismo efecto que tener un número de
prioridad en cada regla: la primer regla implícita tiene la más alta prioridad,
la segunda regla es la próxima más alta, y así sucesivamente. Hay una lista
corta de reglas, seleccionadas del artículo original de Weizenbaum, pero con la
forma de las reglas actualizadas a la forma que nosotros estamos usando. La
respuesta al ejercicio 5.19 contiene una larga lista de reglas.
(defparameter *reglas-eliza*
'((((?* ?x) hola (?* ?y))
(Como estas. Por favor cuentame tu problema.))
(((?* ?x) quiero (?* ?y))
(que pasaria si te ofrezco ?y)
(por que quieres ?y) (suponga que obtienes ?y pronto))
(((?* ?x) si (?* ?y))
(realmente piensas que es probable que ?y) (deseas que ?y)
(que piensas sobre ?y) (realmente si ?y))
(((?* ?x) no (?* ?y))
(por que no?) (estas siendo un poco negativo)
(estas diciendo "NO" solo para ser negativo?))
(((?* ?x) era (?* ?y))
(eras tu realmente?) (tal vez ya sabia que tu eras ?y)
(por que me dices que tu eras ?y ahora?))
(((?* ?x) siento (?* ?y))
(te sientes a menudo ?y ?))
(((?* ?x) senti (?* ?y))
(que otros sentimientos tienes?))))
Finalmente estamos listos para
definir a ELIZA apropiadamente. Como dijimos antes, el programa principal
debería ser un bucle que lee entradas, las transforma, e imprime en pantalla el
resultado. La transformación es hecha primariamente buscando alguna regla tal
que su patrón coincida con la entrada, y luego sustituir las variables dentro
de la respuesta de la regla. El programa es resumido a continuación en una
tabla.
Hay unas complicaciones menores.
Imprimiremos en pantalla un prompt para decirle al usuario que escriba algo.
Usaremos la función aplanar para asegurarnos que la salida no tiene embebidas
listas después de la sustitución de la variable. Un truco importante es alterar
la entrada intercambiando “tu” por “mi” y así sucesivamente, ya que estos
términos son relativos al que habla.
Funciones
de alto nivel
|
|
eliza
|
Responde a la entrada del usuario usando reglas de coincidencia de
patrones.
|
Variables
Globales
|
|
*reglas-eliza*
|
Una lista de reglas de transformación.
|
Tipos
de dato
|
|
regla
|
Una asociación de un patrón con una lista de respuestas.
|
Funciones
|
|
eliza
|
Responde a la entrada del usuario usando reglas
de coincidencia de patrones.
|
usar-reglas-eliza
|
Busca alguna regla con la cual transformar la
entrada.
|
cambiar-puntodevista
|
Cambia yo por tu y viceversa, y asi
sucesivamente.
|
aplanar
|
Une juntos elementos (o listas) en la lista.
|
Funciones
de Common-Lisp
|
|
sublis
|
Sustituye elementos dentro de un árbol.
|
Funciones
definidas previamente
|
|
random-elt
|
Recoge un elemento aleatorio de una lista.
|
patron-coincide
|
Coincide un patrón con una entrada.
|
mappend
|
Aplica una función a cada elemento de la lista y
une los resultados.
|
Aquí está el programa completo:
(defun eliza ()
"Responde a la
entrada del usuario usando reglas de coincidencia de patrones."
(loop
(print 'eliza>)
(write (aplanar
(usar-reglas-eliza (read))) :pretty t)))
(defun usar-reglas-eliza (entrada)
"Busca alguna
regla con la cual transformar la entrada."
(some #'(lambda
(regla)
(let ((resultado (patron-coincide
(regla-patron regla) entrada)))
(if (not (eq resultado falla))
(sublis (cambiar-puntodevista resultado)
(random-elt (regla-respuesta regla))))))
*reglas-eliza*))
(defun cambiar-puntodevista (palabras)
"Cambia yo por
tu y viceversa, y asi sucesivamente."
(sublis '((yo . tu)
(tu . yo) (mi . ti) (soy . eres))
palabras))
(defun aplanar (la-lista)
"Une juntos
elementos (o listas) en la lista."
(mappend #'mklist
la-lista))
(defun mklist (x)
"Devuelve x si
este es una lista, en otro caso devuelve (x)."
(if (listp x)
x
(list x)))
(defun mappend (funcion la-lista)
"Aplica funcion
a cada elemento de la lista y une los resultados."
(apply #'append
(mapcar funcion la-lista)))
(defun random-elt (opciones)
"Recoge un
elemento de una lista al azar."
(elt opciones
(random (length opciones))))
Observe el uso de write con la
palabra clave :pretty. Este dará una mejor salida formateada en algunos casos.
El programa hace uso de la función previamente definida random-elt, y aplanar,
que son definidas aquí usando mappend y mklist, una función que es definida en
el dialecto InterLisp pero no en Common Lisp.
El programa ELIZA actual tiene
algunas complicaciones que no se muestran en esta versión. Primero, había un método
alias para asociar varias palabras con el mismo patrón; tanto “madre” como “padre”
podría ser asociado con el patrón “familia”. Había también un mecanismo de sinónimo que
podría tratar las palabras que signifiquen lo mismo. En el caso de entradas con
varias frases separadas con coma, cada frase fue procesada en forma separada, y
la respuesta con la prioridad más alta fue seleccionada. Adicionalmente, el ELIZA
original tiene un mecanismo de “memoria”.
Cuando no coincide un patrón de entrada, esta dice algo como “Háblame más sobre
X”, donde X es alguna entrada anteriormente dada. Finalmente, nuestra versión
tiene pocas reglas. A pesar delos defectos de nuestra versión, esta puede
ocasionalmente mantener una conversación como se muestra aquí:
> (eliza)
ELIZA> (hola)
(COMO ESTAS. POR FAVOR CUENTAME TU PROBLEMA.)
ELIZA> (quiero verificar este programa)
(QUE PASARIA SI TE OFREZCO VERIFICAR ESTE PROGRAMA)
ELIZA> (podria ver si funciona)
(REALMENTE PIENSAS QUE ES PROBABLE QUE FUNCIONA)
ELIZA> (no realmente)
(ESTAS DICIENDO "NO" SOLO PARA SER NEGATIVO?)
ELIZA> (no)
(ESTAS SIENDO UN POCO NEGATIVO)
ELIZA> (olvida eso estoy asombrado por el funcionamiento
del programa)
(POR QUE ME DICES QUE TU ESTAS ASOMBRADO POR EL FUNCIONAMIENTO
DEL PROGRAMA
AHORA?)
ELIZA> (senti eso)
(QUE OTROS SENTIMIENTOS TIENES?)
ELIZA> (siento que ya es suficiente)
(TE SIENTES A MENUDO QUE YA ES SUFICIENTE ?)
ELIZA> :q
>
Al final, lo que importa es la técnica,
no el programa. ELIZA ha sido “explicada en profundidad” y podría legítimamente
ser movida a la repisa de curiosidades. La coincidencia de patrones en general
permanece como una técnica importante, y la veremos nuevamente en capítulos
siguientes. La noción de un traductor basado en reglas es importante también. El problema de
entender español (y otros lenguajes) si siendo una parte importante en la IA.
Claramente, el problema de entender español no fue resuelto por ELIZA. En la
parte V, veremos el problema nuevamente, usando técnicas más sofisticadas.
Dejo un link con el eliza modificado; con mas reglas, agregue mas reglas si lo desea: Eliza2.lisp
Historia y Referencias
Como se mencionó antes, el
artículo original describiendo ELIZA está en Weizenbaum 1966. Y otros sistemas
de dialogo que usan técnicas similares a la coincidencia de patrones está en el
PARRY de Kennth Colby (1975). Este programa simula la conversación de una
persona paranoica de manera demasiado elemental para varios psicólogos
profesionales. Aunque la técnica de coincidencia de patrones fue simple, el modelo
es mantenido por sistemas mucho más sofisticados que ELIZA. Colby ha sugerido
que los programas de dialogo como ELIZA, es aumentado con algunos modelos como
PARRY, podrían ser herramientas útiles en el tratamiento de enfermedades
mentales de personas. De acuerdo a Colby, podría ser barato y efectivo tener
conversaciones con pacientes con un programa especialmente diseñado, que podría
manejar casos simples y alertar a los doctores sobre los pacientes que
necesitan más ayuda. El libro Poded de Ordenadores y Razones Humanas de Weizenbaum
(1976) habla sobre ELIZA y PARRY y toma una visión muy crítica sobre la
sugerencia de Colby. Otro trabajo interesante sobre modelos de sistemas de
diálogo esta reportado por Allan Collins (1978) y Jamie Carbonell (1981).
