El razonamiento automático es el proceso de extraer conclusiones (“teoremas”) a partir de información (“axiomas”) donde se trata de reconocer patrones comunes entre los axiomas. A medida que las computadoras se vuelven más poderosas y los programadores más entendidos en avances de la lógica, se pueden automatizar con buen éxito una colección mayor de tareas de razonamiento.
Los sistemas de razonamiento automático se los clasifica en cuatro grupos:
Demostradores de teoremas y lenguajes de programación lógicos: se utiliza la resolución para demostrar oraciones expresadas en lógica de primer orden total, también se les emplea para responder preguntas. También utilizan el encadenamiento hacia atrás, y a veces pueden incluir algunas características no lógicas de los lenguajes de programación. (Ej. de demostradores de teoremas: SAM, AURA, OTTER; ej de lenguajes de programación: Prolog, Mrs, LIFE).
Sistemas de producción: utilizan la implicación como elemento primario de representación. Entre las acciones figuran inserciones y eliminaciones de la base de conocimientos así como entrada y salida. Estos sistemas funcionan con una estructura de control encadenada hacia adelante (Ej: Soar, Clips, OPS-5).
Si A1& A2 & A3.... Entonces B
Ai
condiciones.
comparar con BC o con memoria de trabajo.
obtener del usuario o derivar de otras reglas.
B
una conclusión más general: una acción, p.ej., remoción de algo existente en memoria de trabajo.
Sistemas de cuadro y redes semánticas: aquí los objetos son nodos en una gráfica, los cuales se organizan de acuerdo con una estructura taxonómica y los vínculos que existen entre los nodos representen relaciones binarias. En los sistemas de cuadro estas relaciones se consideran como ranuras de un cuadro, mientras que en las redes semánticas, se consideran como flechas entre un nodo y otro (Ej: Sistemas de frames: Owl, Frail, Kodiak; Redes Semánticas: Sneps, Netl, GraCon).
Sistemas lógicos por descripción: Son redes semánticas “presionadas” para formalizar el significado de las gráficas. La lógica de la descripción se conoce a veces como lógica terminológica, debido a la atención puesta en la definición de términos (Ej: Classic, Loom).
Almacenar y Recoger son dos funciones sencillas que se concentran en la implantación física de la base de conocimientos.
Para construir un sistema de razonamiento hay que definir los tipos de datos de las oraciones y los términos, es decir definir la sintaxis de las oraciones y la representación interna en donde el sistema guardará y manejará las oraciones a nivel de implantación.
Recoger se utiliza para la localización de oraciones en la Base de conocimientos que unifican con la consulta, o que por lo menos tienen la misma estructura sintáctica. Guardar(BC, S) lo que hace es añadir todos los conjuntos de la oración S a la base de conocimientos BC. Recoger(BC, Q) tiene que recorrer todos los elementos de la base de conocimientos, uno a la vez, hasta dar con un conjunto que coincida con Q, o hasta llegar al final.
Indización basada en tablas: La base de conocimientos se debe implantar como una tabla de dispersión. Esto tiene dos desventajas: no maneja oraciones complejas que no sean las de negación ni tampoco maneja variables que puedan contener oraciones.
Indización basada en árboles: es una forma de la indización combinada, donde elabora una llave combinada a partir de los signos de predicado y de argumento de la consulta. Aunque no es de mucha ayuda cuando uno de los signos de la secuencia es una variable, puesto que necesario recorrer cada una de las ramas.
Indización cruzada: se indizan entradas en diversos sitios, cuando se hace uan consulta, la recuperación se realiza en la parte que ofrece más posibilidades.
Unificación: Es un algoritmo en tiempo lineal que retorna el unificador más general, la lista de sustitución más corta que consigue que haya acuerdo entre dos literales. Aunque en general no hay un único unificador, por lo menos retorna uno que es de longitud mínima. Una variable no puede ser reemplazada por un término que ya contiene dicha variable, por ejemplo es ilegal x/f(x). Se debe realizar esa verificación en el seudo-código antes de las llamadas recursivas.
La programación lógica considera al programa y a sus entradas como aseveraciones lógicas acerca del mundo, y al procedimiento de hacer explícitas las consecuencias como un proceso de inferencia.
Algoritmo = Lógica + Control
Los lenguajes de programación permiten escribir algoritmos al completar las oraciones lógicas con información para control del procedimiento de inferencia. Prolog es el lenguaje de programación lógica que más se ha utilizado.
Sistemas Prolog (PROgramación LOGica)
Base: encadenamiento hacia atrás con cláusulas de Horn + campanas & bocinazos.
Muy usado en Europa y Japón (donde fue la base de la Quinta Generación - Minsky atribuye su fracaso al uso de Prolog).
Programa = conjunto de cláusulas.
La cabeza o consecuente está a la izquierda.
El cuerpo o antecedentes están a la derecha.
Para demostrar la cabeza, demuestre el cuerpo.
“Unifica” con eficiencia por codificación abierta.
Recolección eficiente de cláusulas que están de acuerdo usando enlaces directos.
Primero en profundidad, encadenamiento de izq a der.
Suposición de mundo cerrado (“negación como fracaso”). Ejemplo: NoDoctor(x) se acepta si Doctor(x) falla.
Estos se diferencian de los lenguajes de programación lógica por dos aspectos:
Los lenguajes de programación lógica sólo manejan cláusulas Horn y los demostradores de teoremas aceptan la lógica de primer orden.
Los programas Prolog combinan lógica y control.
Al preparar un problema para someterlo a Otter, se debe divir el conocimiento como sigue:
Un conjunto de cláusulas conocido como conjunto de apoyo (Hechos importantes relacionados con el problema).
Un conjunto de axiomas utilizables que no pertenezcan al conjunto de apoyo.
Un conjunto de ecuaciones conocido como reelaboraciones o demoduladores.
Un conjunto de parámetros y cláusulas que definen la estrategia de control.
El demostrador de problemas OTTER opera mediante la resolución continua de un elemento del conjunto de apoyo comparándolo con uno de los axiomas utilizables. A diferencia del Prolog, utiliza una modalidad de búsqueda preferente por el mejor. Su función heurística determina el "peso" de cada una de las cláusulas y da preferencia a las más ligeras.
En cada paso, Otter desplaza la cláusula má ligera del conjunto de apoyo a la lista de lo utilizable, y añade a ésta algunas consecuencias inmediatas de la resolución de la cláusula más ligera. Otter se interrumpe cuando se topa con una refutación o cuando ya no quedan cláusulas en el conjunto de apoyo.
Los verificadores de teoremas ayudan hasta cierto punto en el caso de problemas de semidecibilidad, porque permite cancelar una consulta (por que consume mucho tiempo) y probar otro método. También puede operar como verificador de demostraciones.
Un razonador socrático es un demostrador de teoremas cuya función PREGUNTAR esta incompleta, pero llega a la solución planteando las preguntas adecuadas.
Los demostradores de teoremas se utilizan en problemas relacionados con la verificación y síntesis tanto de hardware (los axiomas describen las interacciones entre las señales y elementos del circuito) como de software (los axiomas definen las propiedades de los elementos sintácticos del lenguaje de programación).
En el encadenamiento hacia adelante no existen consultas, por lo que se aplica a la base de conocimientos reglas de inferencia, lo que produce nuevas aseveraciones. Este procedimiento se repite indefinidamente, o hasta que se logra satisfacer cierto criterio de paro.
Un sistema de producción típico se caracteriza por:
Mantiene una BC conocida como memoria de trabajo.
Mantiene también una memoria de reglas independiente.
En cada ciclo, el sistema calcula el subconjunto de reglas cuyo lado izquierdo se satisface con el contenido actual de la memoria de trabajo.
El sistema decide cuál de las reglas va a ejecutar, a esto se lo conoce como fase de resolución de conflictos.
Por último se ejecuta la(s) acción(es) de la(s) regla(s) elegida(s), esto es la fase de actuación.
Fase de cotejo: la unificación enfrenta el problema del cotejo de un par de literales, cada una de las cuales puede contener variables.
Cotejo Significa comparación...
Hacia delante ... desde condiciones hacia hechos (derivados)
Hacia atrás...desde conclusiones y hechos hacia metas.
El hecho y la condición (simple) cotejan si:
la condición es idéntica al hecho.
la condición y el hecho se unifican por substitución de variables.
El algoritmo Rete
El algoritmo rete lo que hace primero es compilar la memoria de reglas en la red.
Los nodos circulares representan ocasiones en que se han recogido literales (no unificaciones) en la memoria de trabajo.
En el nodo a, se recogen los elementos de la memoria de trabajo A(l) y A(2).
Los nodos cuadrados indican unificaciones.
De las seis posibles combinaciones A X B en el nodo A = B, sólo A(2) y B(2) satisfacen la unificación.
Por último, las cajas rectangulares indican acciones.
En la memoria inicial de trabajo, la regla "sumar D" es la única que satisface, lo que da por resultado la incorporación de la literal D(2) a la memoria de trabajo.
Memoria de Trabajo WM = {A(1), A(2), B(2), B(3), B(4), C(5)}
A(x) B(y) D(x) => sumar E(x)
A(x) B(x) C(y) => sumar D(x)
A(x) B(x) E(z) => borrar A(x)
Una red “Rete"
Los círculos representan las pruebas de predicado.
Los rectángulos representan acciones.
añadir E, añadir D, borrar A.
Los cuadrados representan restricciones: A=B significa que las soluciones de las pruebas de A y de B deben ser las mismas; A=D lo mismo, respectivamente para A y D .
Una de las ventajas de la red Rete es que elimina la duplicación en la reglas. Esta red se modifica luego de uan incorporación o una eliminación.
La fase de solución de conflictos sirve para decidir cuál de las sugerencias se va a aceptar, a esta fase se la puede considerar como la estrategia de control. Algunas de las estrategias son:
No duplicación. Na aplica dos veces la misma regla a los mismos argumentos.
Novedad. Prefiere aquellas reglas que se refieren a elementos de la memoria de trabajo de reciente creación.
Especificidad. Da preferencia a aquellas reglas que sean más específicas.
Prioridad de operación. Prefiere aquellas reglas que tienen mayor prioridad, según lo especificado por cierto sistema de calificación.
Toda red semántica o sistema de marco también puede definirse como oraciones de una lógica, lo importante en todo lenguaje de representación reside en la comprensión de la semántica y en la teoría de la demostración.
Sintaxis y semántica de las redes semánticas: en las redes semánticas lo
importante esta basado en las categorías de los objetos y las relaciones. Para
definir la semántica de estas redes es necesario proponer los equivalentes en
lógica de primer orden de las aseveraciones que se hagan en el lenguaje
de la red. Para esto se debe definir la versión en donde no hay excepciones y
vínculos (para expresar que hay una relación R entre dos objetos A y B; otro
para afirmar que R se cumple en todos los elementos de la claase A y el objeto
B; y que se afirme que R se cumple en todos los elementos de A y algún elemento
de B). Estos vínculos son recorridos a través de algoritmos de propósito
especial dentro de éstas redes.
Herencia con excepciones: una forma de manejar este tipo de herencia sería recorriendo los vínculos de un diagrama, pero también es posible definir la semántica correspondiente mediante lógica de primer orden. El primer paso en una traducción lógica consiste en reificar las relaciones: una relación R se convierte en un objeto, no en un predicado.
Herencia múltiple: es cuando un objeto pertence a más de una categoría, y por tanto hereda propiedades de varias rutas. En algunos casos esto opera sin mayor problema, pero puede suceder que dos rutas de herencia produzcan respuestan conflictivas por lo que sin información adicional que indica cierta preferencia por una ruta, no hay manera de resolver el conflicto.
Herencia y cambio: los sistemas basados en la lógica de primer orden se valen de DECIR para incorporar una nueva oración a la BC y además cuenta con la propiedad de monotonicidad: si P se deduce de BC, entonces también se aumenta por DECIR(BC, S). En cambio la herencia que no tiene excepciones se considera no monotónica, para resolver esto hay dos métodos:
Cambiar la lógica de primer orden a lógica no monotónica, la cual maneja valores por omisión.
Manejar la incorporación de una nueva aseveración como REDACTAR seguida de DECIR.
Implantación de redes semánticas: se pueden implantar redes a través de un demostrador de teoremas o con un lenguaje de programación lógica. El nodo de una red se representa mediante una estructura de datos, en la que hay campos para las conexiones taxonómicas básicas y también cuenta con campos para otras relaciones en las que participa.
Expresividad de las redes semánticas: en algunas de éstas de amplia la notación de manera que puedan trabajar con lógica de primer orden. Esto conlleva a tres ventajas: son capaces de capturar información de herencia de manera modular; su sencillez facilita mucho su comprensión y su eficiencia puesto que la inferencia se efectúa al seguir vínculos, en vez de recuperar oraciones de una BC y realizar unificaciones, necesitan de sólo unos cuantos ciclos de máquina por paso de inferencia.
Están diseñadas para concentrarse en categorías y sus definiciones cuyas principales tareas de inferencia son la subsuposición (verificar que una categoría sea subconjunto de otra con base en sus definiciones) y la clasificación (verificar que un objeto pertenezca a una categoría).
Esta lógica permite efectuar operaciones lógicas directas en los predicados, en vez de tener que crear primero oraciones que se unen mediante conectores.
Quizás el aspecto más importante de la lógica de descripciones sea el énfasis que se pone en la tratabilidad de la inferencia. Los problemas se resuelven mediante su descripción y cuestionando si se le puede subsimir mediante una de varias categorías posibles de solución.
Al procedimiento que lleva un control de qué proposiciones adicionales hay que retractar se lo conoce como mantenimiento de la verdad (en este método se lleva el control del orden en el que se incorporan las oraciones a la BC y garantiza la consistencia de esta última).
Un sistema de mantenimiento de la verdad o SMV es un programa que lleva el control de las dependencias presentes entre las oraciones con el fin de hacer más eficiente la retractación. Este sistema realiza cuatro funciones importantes:
Permite la revisión controlada por dependencias, lo que evita la ineficiencia de la reversión cronológica.
Ofrece explicaciones de las proposiciones.
La capacidad para amnejar suposiciones y explicaciones es crucial para la tercer función de un SMV: el razonamiento por omisión.
Ayudan a manejar las inconsistencias.
Existen diversos tipos de SMV. El más sencillo es el sistema de mantenimiento de la verdad basado en la justificación o SMVJ, en este caso en cada una de las oraciones de la BC se indica cuál justificación identifica las oraciones a partir de la primera que se infirió, si es que existen.
El tipo más popular es el SMVS, o sistema de mantenimiento de la verdad basado en suposiciones, este representa todos los estados que se han considerado y lleva el control, por cada oración, de qué suposiciones harán que la oración sea verdadera.
