Inteligencia Artificial
- Fundamentos
- Tecnicas de solucion
- Sistemas de produccion
- Representacion del conocimiento
- Inferencia y razonamiento
- Representación mediante reglas de producción
- El proceso de razonamiento
- Sistemas basados en conocimiento
- Sistemas expertos
FUNDAMENTOS DE LA INTELIGENCIA ARTIFICIAL
En primer lugar, revisemos algunas definiciones generales de inteligencia, antes de intentar definir inteligencia artificial. Inteligencia es la aptitud de crear relaciones. Esta creación puede darse de manera puramente sensorial, como en la inteligencia animal; también puede darse de manera intelectual, como en el ser humano, que pone en juego el lenguaje y los conceptos. También se la puede conceptuar como la habilidad para adquirir, comprender y aplicar conocimiento; o como la aptitud para recordar, pensar y razonar.
La IA es una nueva generación de tecnología informática, caracterizada no sólo por su arquitectura (hardware), sino también por sus capacidades. El énfasis de generaciones previas fue en las computaciones numéricas para aplicaciones científicas o de negocios. La nueva generación de tecnología informática incluye además la manipulación simbólica, con el objetivo de emular el comportamiento inteligente; y, la computación en paralelo, para tratar de conseguir resultados prácticamente en tiempo real. La capacidad predominante de la nueva generación, también conocida como la Quinta Generación, es la habilidad de emular (y tal vez en algunos casos superar) ciertas funciones inteligentes del ser humano.
Por ejemplo:
Aprendizaje:
- Captación automática de conocimientos.
Razonamiento:
Percepción:
- Comprensión de lenguaje natural.
- Interpretación de escenas visuales (Visión por computadora).
Locomoción y Manipulación:
Creación:
- Generación, verificación, depuración y optimización automática de programas.
Algunas de las tareas que estos sistemas realizan en el campo de la IA son:
Tareas generales
- Percepción: Visión, Fonemas.
- Lenguaje Natural: Comprensión, generación y traducción.
- Razonamiento de sentido común.
- Control de robots.
Tareas formales
- Juegos: Ajedrez, Backgammon, Damas.
- Matemáticas: Geometría, Lógica, Cálculo Integral.
Tareas expertas
- Ingeniería: Diseño, Localización de fallas, Planeamiento.
- Análisis Científico.
- Diagnóstico Médico.
- Análisis Financiero.
Las técnicas de solución de problemas en IA, en general, incorporan un proceso de búsqueda. Todo proceso de búsqueda puede ser visualizado como el recorrido por un árbol en el que cada nodo representa un estado y cada rama representa las relaciones entre los estados cuyos nodos conecta.
En general, las reglas contienen en forma implícita el árbol, y se genera en forma explícita sólo aquellas partes que se decide explorar. Las principales diferencias que pueden aparecer en las diferentes técnicas de búsqueda, son:
- La dirección en la cual se conduce la búsqueda (hacia adelante o hacia atrás).
- La estrategia de control, o forma de seleccionar las reglas que pueden ser aplicables. Los principales requerimientos de una buena estrategia de control son: que cause desplazamiento en el espacio de estado; y, que sea sistemático.
- La forma de representar cada nodo del proceso de búsqueda (representación del conocimiento).
Muchas veces, tratar el proceso como búsqueda en un grafo en lugar de una búsqueda en un árbol, puede reducir el esfuerzo que se gasta en explorar senderos, esencialmente iguales, varias veces. Sin embargo, los requisitos asociados, son:
- Cada vez que se genere un nodo se debe chequear para ver si ha sido generado antes.
- Se deben introducir procedimientos especiales para que la búsqueda no quede atrapada en algún lazo.
A continuación se describen los algoritmos de tres procesos básicos de búsqueda de soluciones en el espacio de estado.
Algoritmo Generación Y Prueba (GENERATE-AND-TEST)
1. Generar una posible solución. (estado o camino)
2. Comprobar para ver si es una solución, mediante comparación con los elementos del conjunto de objetivos aceptables.
3. Si la solución ha sido encontrada salir, de otra manera, retornar al paso 1.
Algoritmo Primero a lo Ancho (BREATH-FIRST)
- Crear una variable NODE_LIST y ponerla al estado inicial.
- Remover el primer elemento de NODE_LIST, y llamarlo E. Si NODE_LIST estuvo vacía, salir.
- Aplicar la regla para generar un nuevo estado.
- Si el nuevo estado es un estado objetivo, salir y retornar este estado.
- Sino, añada el nuevo estado al final de NODE_LIST.
- Para cada forma en que cada regla puede ajustarse al estado descrito en E, haga lo siguiente:
- Hasta que se encuentre el objetivo o hasta que NODE_LIST esté vacía haga lo siguiente:
Algoritmo Primero en Profundidad (DEPTH-FIRST)
- Si el estado inicial es el objetivo, salir y retornar éxito.
- Genere un sucesor E del estado inicial. Si no hay más sucesores, retorne con señal de fracaso.
- Llame recursivamente al algoritmo, esta vez con E como el estado inicial.
- Si la señal es éxito, retorne, de otra manera, continúe en este lazo.
- Sino, haga lo siguiente hasta que se obtenga señal de éxito o fracaso:
Búsqueda Heurística
Para resolver muchos problemas difíciles (explosión combinatoria), es necesario muchas veces llegar a un compromiso de los requerimientos de movilidad y sistematicidad y construir una estructura de control que no necesariamente garantiza el encontrar la mejor respuesta, sino que casi siempre encuentra una buena respuesta. Una técnica heurística mejora la eficiencia del proceso de búsqueda sacrificando, usualmente, exhaustividad.
Las consideraciones que sirven de soporte a un proceso de búsqueda heurística, son:
- Rara vez se requiere, en realidad, una solución óptima. Una buena aproximación, normalmente, sirve muy bien.
- A pesar que una aproximación heurística no puede resultar muy buena en el peor de los casos, raras veces aparecen los peores casos en la práctica.
- El tratar de comprender por qué un heurístico funciona o por qué no funciona, a menudo conduce a una mejor comprensión del problema.
Un sistema de producción proporciona una estructura que facilita la descripción y la ejecución de un proceso de búsqueda. Un sistema de producción consiste de:
- Un conjunto de facilidades para la definición de reglas.
- Mecanismos para acceder a una o más bases de conocimientos y datos.
- Una estrategia de control que especifica el orden en el que las reglas son procesadas, y la forma de resolver los conflictos que pueden aparecer cuando varias reglas coinciden simultáneamente.
- Un mecanismo que se encarga de ir aplicando las reglas.
Dentro de esta definición general de sistema de producción, se incluyen:
- Lenguajes básicos para sistemas de producción (LISP, CLIPS, PROLOG). También se los conoce como lenguajes de Inteligencia Artificial.
- Sistemas híbridos y sistemas vacíos (shells) para producción de sistemas basados en conocimientos (VP-Expert, Expert Teach, Personal Consultant, Intelligence Compiler, EXSYS).
- Arquitecturas generales para resolución de problemas (máquinas LISP, máquinas PROLOG).
Características de los Sistemas de Producción
Un sistema de producción, al igual que los problemas, puede ser descrito por un conjunto de características que permiten visualizar la mejor forma en que puede ser implementado.
Un sistema de producción se dice que es monotónico si la aplicación de un regla nunca evita que más tarde se pueda aplicar otra regla que también pudo ser aplicada al momento en que la primera fue seleccionada.
Un sistema de producción es parcialmente conmutativo si existe un conjunto de reglas que al aplicarse en una secuencia particular transforma un estado A en otro B, y si con la aplicación de cualquier permutación posible de dichas reglas se puede lograr el mismo resultado.
Un sistema de producción es conmutativo, si es monotónico y parcialmente conmutativo.
SISTEMA DE PRODUCCIÓN | MONOTÓNICO | NO-MONOTÓNICO |
PARCIALMENTE CONMUTATIVO |
Demostración de Teoremas | Navegación Robótica |
PARCIALMENTE NO CONMUTATIVO |
Síntesis Química | Juego de Ajedrez |
Procesos Heurísticos de Búsqueda
Las técnicas heurísticas de búsqueda son como guías de turismo. Buenas, en el sentido que señalan aspectos de gran interés general, pero malas ya que pueden no satisfacer aspectos de interés particular.
Existen varias técnicas heurísticas buenas, de propósito general, que son útiles para una diversidad de problemas. Adicionalmente, es posible construir heurísticos especiales que exploten conocimiento específico en cada dominio, para resolver problemas particulares.
Ascenso a Colina (Hill Climbing)
Es una variante del algoritmo de búsqueda de generación y prueba. Del procedimiento de prueba existe una realimentación que ayuda al generador a decidirse por cual dirección debe moverse en el espacio de búsqueda. En estos procesos se abandona la búsqueda si no existe un estado alternativo razonable al que se pueda mover.
Los algoritmos de ascenso a colina son típicamente locales, ya que deciden qué hacer, mirando únicamente a las consecuencias inmediatas de sus opciones. Puede que nunca lleguen a encontrar una solución, si son atrapados en estados que no son el objetivo, desde donde no se puede hallar mejores estados, por ejemplo:
1. Un máximo local, que es un estado mejor que sus vecinos pero no es mejor que otros que están algo más alejados.
2. Una meseta, es un espacio de búsqueda en el que todo un conjunto de estados vecinos tienen igual valor.
3. Un risco, que es un tipo especial de máximo local, imposible de atravesar con movimientos simples.
Hay algunas formas que pueden ayudar a solventar estos problemas, aunque no existe garantía:
1. Para evitar máximos locales, regresar a un estado anterior y explorar en una dirección diferente.
2. Para casos de mesetas, dar un salto grande en alguna dirección y tratar de encontrar una nueva sección del espacio de estado.
3. Para los riscos, aplicar dos o más reglas, antes de realizar una prueba del nuevo estado, esto equivale a moverse en varias direcciones a la vez.
Los algoritmos de ascenso a colina, a pesar de explorar sólo un paso adelante, al examinar el nuevo estado pueden incluir una cierta cantidad de información global codificada en la función objetivo o función heurística.
Recocido Simulado (Simulated Annealing)
Es una variación del ascenso a colina. Al inicio, este algoritmo, permite explorar una buena parte del espacio de estado, de tal forma que la solución final puede resultar insensible al estado inicial. En consecuencia, la probabilidad de quedar atrapado en un máximo local, en una meseta o en un risco, se hace mínima.
El recocido simulado es un proceso computacional que refleja los pasos establecidos en el proceso físico de tratamiento térmico de materiales. En el recocido, por ejemplo, un metal es llevado a elevados niveles energéticos, hasta que alcanza su punto de fusión. Luego, gradualmente es enfriado hasta alcanzar un estado sólido, de mínima energía, previamente definido. Por su naturaleza, este algoritmo debe ser formulado como un descenso a valle en el que la función objetivo es el nivel energético.
Las sustancias físicas usualmente se mueven desde configuraciones de alta energía a las de menor energía, así que el descenso al valle, ocurre en forma natural.
Pero, eventualmente pueden haber transiciones a niveles energéticos más altos, con una probabilidad dada por
T es la Temperatura absoluta y k es la constante de Boltzmann.
El procedimiento que se va a seguir para enfriar el sistema, se llama programa de recocido. Su forma óptima depende de cada tipo de problema y usualmente se lo descubre empíricamente. El programa de recocido, debe incluir los siguientes ingredientes:
- El valor inicial de la temperatura.
- El criterio que será utilizado para decidir cuando reducir la temperatura.
- La cantidad en que será reducida la temperatura.
- Cuando finalizar el proceso.
El algoritmo para el recocido simulado, es ligeramente diferente del procedimiento simple de ascenso a colina. Las diferencias son:
- Se debe respetar el programa de recocido.
- Movimientos a estados peores que el actual, pueden ser aceptados.
- Se debe mantener, a más del estado actual, el mejor estado encontrado hasta el momento. Así, si por alguna razón el estado final resulta peor que el mejor encontrado anteriormente, siempre será posible regresar a él.
Primero el Mejor (Best-First)
Este algoritmo, combina las ventajas de los algoritmos primero en profundidad y primero en amplitud. Sigue un sendero a la vez, pero puede cambiarse a otro sendero que parece más prometedor que el que está siguiendo.
En este sentido, puede considerarse que es un algoritmo que realiza su proceso de búsqueda en un grafo de tipo O, ya que todos sus ramales representan una alternativa de solución. Para su operación, el algoritmo necesita dos listas de nodos y una función heurística que estime los méritos de cada nodo que se genere:
1. ABIERTOS – Es una variable que contiene los nodos que han sido generados. La función heurística ha sido aplicada a ellos, pero todavía no han sido examinados, es decir no se han generado sus sucesores. ABIERTOS puede considerarse como una COLA DE PRIORIDADES en la que los elementos con mayor prioridad son los que tienen los valores más prometedores, dados por la función heurística.
2. CERRADOS – Es una variable que contiene los nodos que han sido examinados. Es necesario tener esta información, para que la búsqueda sea en un grafo y no en un árbol.
3. FUNCIÓN HEURÍSTICA – Permite que el algoritmo busque primero por senderos que son o parecen más prometedores.
Para muchas aplicaciones, es conveniente definir esta función f', como la suma de dos, que se las llamará g y h'. La función g es una medida del costo de llegar desde el nodo inicial al nodo actual. La función h' es una estimación del costo adicional para llegar desde el nodo actual al estado objetivo. Aquí es donde se explota el conocimiento que se dispone sobre el dominio del problema.
Es decir, la función combinada f' representa una estimación del costo de llegar desde el estado inicial hasta el estado objetivo, siguiendo el sendero que ha generado el nodo actual. Si el nodo actual ha generado más de un sendero, el algoritmo deberá dejar registrado sólo el mejor.
El algoritmo, en la forma que fue formulado, se aplica a grafos. Puede ser simplificado para aplicarse a árboles, si no se preocupa de comprobar si un nuevo nodo esta en ABIERTOS o en CERRADOS. Esto aceleraría la generación de nodos y la búsqueda, para casos en que es poco probable que se repitan nodos.
Usualmente, el costo de ir de un nodo a su sucesor, g, se fija en una constante igual 1, cuando se desea encontrar un sendero a la solución, que involucre el menor número de pasos. Si por el contrario nos interesa encontrar el camino menos costoso y algunos operadores cuestan más que otros, se asume un valor de g, que refleje esos costos. Un valor de g igual a cero significaría que simplemente nos interesa llegar a alguna solución, de cualquier manera.
Si h' es un estimador perfecto de h, hará que A* converja inmediatamente al objetivo, sin búsqueda. Mientras mejor sea h', más cerca se estará de alcanzar esta aproximación directa. Si h' vale cero, la búsqueda será controlada por g. Si el valor de g es también cero, hará que la búsqueda sea aleatoria. Si el valor de g es siempre 1, hará que la búsqueda sea primero en anchura. Para los casos en que h' no sea perfecto ni cero, y nunca llega a sobrestimar el valor de h, el algoritmo A* está garantizado que encontrará un sendero óptimo a un objetivo, en caso de que exista solución. Cuando un algoritmo garantiza el encontrar una solución óptima, si esta existe, se dice que es admisible.
Teorema de Admisibilidad
Si h' nunca sobrestima a h entonces A* es admisible. La única manera de garantizar que h' nunca sobrestime a h es haciéndolo cero, pero con ello estamos en la búsqueda primero en anchura, es decir el algoritmo es admisible, pero no eficiente.
Pero existe un corolario que puede ser de utilidad en casos prácticos:
COROLARIO: Si h' muy rara vez sobrestima h por más de entonces el algoritmo A* rara vez encontrará una solución cuyo costo sea mayor más que en que el costo de la solución óptima.
Bajo ciertas condiciones, el algoritmo A* puede ser óptimo, en el sentido de generar el menor número de nodos posibles, en el proceso de encontrar una solución, pero bajo otras condiciones puede no serlo.
Algoritmo Guiado por Agenda
Una agenda es una lista de tareas que un sistema podría realizar. Asociado con cada tarea están, usualmente, dos cosas: una lista de razones de por qué se propone la tarea (justificaciones); y, un valor representando el peso de la evidencia que sugiere que la tarea podría ser útil.
Reducción de Problema
La estructura de grafo tipo Y-O es útil para representar la solución de problemas que pueden ser descompuestos en un conjunto de problemas más pequeños. Esta descomposición o reducción genera enlaces de tipo Y. Enlaces de tipo Y apuntan a cualquier número de nodos sucesores que deben ser resueltos para ver si es que el enlace apunta hacia una solución. Los enlaces Y se indican con un arco que conecta los enlaces componentes.
Para la descripción del algoritmo de búsqueda en un grafo Y-O se definirá un valor llamado INUTILIDAD. Si el valor estimado para una solución se hace mayor que el valor de INUTILIDAD, se abandona la búsqueda. El valor de INUTILIDAD debe escogerse para que cualquier solución con un costo superior resulte demasiado cara como para ser de utilidad práctica, aún en el caso de que sea posible encontrarla.
Algoritmo AO*
El algoritmo anterior, es una simplificación del algoritmo denominado como AO*. En este algoritmo se emplea una estructura GRAFO, representando parte del grafo de búsqueda que ha sido explícitamente generado hasta el momento. Cada nodo en el grafo apuntará tanto a sus inmediatos sucesores, como hacia sus inmediatos predecesores, tendrá su correspondiente valor h' pero no habrá un valor de g ya que puede darse el caso que exista varios senderos al mismo nodo, dificultando su cálculo.
Satisfacción de Requisitos
Muchos problemas en Inteligencia Artificial pueden ser vistos como problemas que requieren de la satisfacción de ciertos requisitos, para poder llegar a una solución. Ejemplos de este tipo de problemas son: los llamados rompecabezas criptaritméticos y tareas de diseño que tienen limitaciones en tiempo, costo y materiales.
Análisis de Medios Y Metas (Means-Ends)
Esta técnica permite en primer lugar resolver las mayores partes de un problema y luego regresar para resolver los problemas más pequeños que pueden aparecer al ensamblar las soluciones a las partes mayores. El proceso se centra en la detección de diferencias entre el estado actual y el estado objetivo. Una vez que se aísla dicha diferencia, se necesita encontrar un operador que reduzca la diferencia.
Pero es posible que el operador encontrado no pueda ser aplicado al estado actual. En este caso, se define como subproblema el alcanzar el estado en el que el operador pueda ser aplicado. Puede también suceder que la aplicación del operador no nos conduce exactamente al estado objetivo deseado. Si tal es el caso, se define un como subproblema el llegar desde el estado producido, al objetivo.
Cuando la diferencia ha sido escogida correctamente y el operador es realmente efectivo, normalmente resulta más fácil resolver los dos subproblemas, que el problema original. Luego, el algoritmo puede ser aplicado en forma recursiva.
Para enfocar la atención del sistema primero en los problemas grandes, se pueden asignar niveles de prioridad a las diferencias. Así, diferencias de mayor prioridad, serán atendidas antes que las de menor prioridad.
Al igual que otras técnicas de solución de problemas, el análisis de medios y metas se basa en un conjunto de reglas que pueden transformar un estado del problema en otro. Las reglas están escritas de tal forma que el lado izquierdo describe las condiciones que deben cumplirse para que la regla sea aplicable (precondiciones de la regla) y el lado derecho describe aquellos aspectos del estado del problema que será cambiados por la aplicación de la regla (resultados). Una estructura de datos separada, llamada tabla de diferencias, indexa las reglas de acuerdo con las diferencias que pueden reducir, al ser usadas.
REPRESENTACIÓN DEL CONOCIMIENTO
En organismos biológicos se estima que el conocimiento es almacenado como estructuras complejas de neuronas interconectadas.
En las computadoras, el conocimiento también se almacena como estructuras simbólicas, pero en forma de estados eléctricos y magnéticos.
En forma natural, el ser humano representa el conocimiento simbólicamente: imágenes, lenguaje hablado y lenguaje escrito. Adicionalmente, ha desarrollado otros sistemas de representación del conocimiento: literal, numérico, estadístico, estocástico, lógico.
La ingeniería cognoscitiva ha adaptado diversos sistemas de representación del conocimiento que, implantados en un computador, se aproximan mucho a los modelos elaborados por la psicología cognoscitiva para el cerebro humano. Entre los principales se tienen:
Lógica Simbólica Formal:
– Lógica proposicional
– Lógica de predicados.
– Reglas de producción.
Formas Estructuradas:
– Redes asociativas.
– Estructuras marco.
– Representación orientada a objetos.
Lógica Proposicional
La lógica proposicional es la más antigua y simple de las formas de lógica. Utilizando una representación primitiva del lenguaje, permite representar y manipular aserciones sobre el mundo que nos rodea. La lógica proposicional permite el razonamiento, a través de un mecanismo que primero evalúa sentencias simples y luego sentencias complejas, formadas mediante el uso de conectivos proposicionales, por ejemplo Y (AND), O (OR). Este mecanismo determina la veracidad de una sentencia compleja, analizando los valores de veracidad asignados a las sentencias simples que la conforman.
Una proposición es una sentencia simple que tiene un valor asociado ya sea de verdadero (V), o falso (F). Por ejemplo:
Hoy es Viernes
Ayer llovió
Hace frío
La lógica proposicional, permite la asignación de un valor verdadero o falso para la sentencia completa, no tiene facilidad par analizar las palabras individuales que componen la sentencia. Por este motivo, la representación de las sentencias del ejemplo, como proposiciones, sería:
hoy_es_Viernes
ayer_llovió
hace_frío
La proposiciones pueden combinarse para expresar conceptos más complejos. Por ejemplo:
hoy_es_Viernes y hace_frío.
A la proposición anterior dada como ejemplo, se la denomina fórmula bien formada (well-formed formula, wff). Una fórmula bien formada puede ser una proposición simple o compuesta que tiene sentido completo y cuyo valor de veracidad, puede ser determinado. La lógica proposicional proporciona un mecanismo para asignar valores de veracidad a la proposición compuesta, basado en los valores de veracidad de las proposiciones simples y en la naturaleza de los conectores lógicos involucrados.
Representación mediante Lógica de Predicados
La principal debilidad de la lógica proposicional es su limitada habilidad para expresar conocimiento. Existen varias sentencias complejas que pierden mucho de su significado cuando se las representa en lógica proposicional. Por esto se desarrolló una forma lógica más general, capaz de representar todos los detalles expresados en las sentencias, esta es la lógica de predicados.
La lógica de predicados está basada en la idea de las sentencias realmente expresan relaciones entre objetos, así como también cualidades y atributos de tales objetos. Los objetos pueden ser personas, objetos físicos, o conceptos. Tales cualidades, relaciones o atributos, se denominan predicados. Los objetos se conocen como argumentos o términos del predicado.
Al igual que las proposiciones, los predicados tienen un valor de veracidad, pero a diferencia de las preposiciones, su valor de veracidad, depende de sus términos. Es decir, un predicado puede ser verdadero para un conjunto de términos, pero falso para otro.
Por ejemplo, el siguiente predicado es verdadero:
color (yerba, verde)
el mismo predicado, pero con diferentes argumentos, puede no ser verdadero:
color (yerba, azul) o color (cielo, verde)
Los predicados también pueden ser utilizados para asignar una cualidad abstracta a sus términos, o para representar acciones o relaciones de acción entre dos objetos. Por ejemplo:
mortal(juan_carlos) | clima(martes, lluvioso) | ave(gaviota) | ama(roberto, vanessa) | lee(alex, novela) | mordio(boby, cartero) |
Al construir los predicados se asume que su veracidad está basada en su relación con el mundo real. Naturalmente, siendo prácticos, trataremos que los predicados que definimos estén de acuerdo con el mundo que conocemos, pero no es absolutamente necesario que así lo hagamos. En lógica de predicados el establecer como verdadero un predicado es suficiente para que así sea considerado.
Demos el siguiente ejemplo, que indica que Ecuador está en Europa:
parte_de(ecuador, europa)
Obviamente, esto no es verdadero en el mundo real, pero la lógica de predicados no tiene razón de saber geografía y si el predicado es dado como verdadero, entonces es considerado como lógicamente verdadero. Tales predicados, establecidos y asumidos como lógicamente verdaderos se denominan axiomas, y no requieren de justificación para establecer su verdad.
La lógica de predicados, se ocupa únicamente de métodos de argumentación sólidos. Tales argumentaciones se denominan Reglas de Inferencia. Si se da un conjunto de axiomas que son aceptados como verdaderos, las reglas de inferencia garantizan que sólo serán derivadas consecuencias verdaderas.
Tanto los conectivos lógicos, como los operadores dados anteriormente para la lógica proposicional, son igualmente válidos en lógica de predicados. De hecho, la lógica proposicional es un subconjunto de la lógica de predicados.
Cada uno de los argumentos en los ejemplos de predicados dados anteriormente, representan a un objeto específico. Tales argumentos se denominan constantes. Sin embargo, en la lógica de predicados se pueden tener argumentos que en determinado momento pueden ser desconocidos. Estos son los argumentos tipo variable.
En el ejemplo: color (yerba, X), la variable X, puede tomar el valor de verde, haciendo que el predicado sea verdadero; o puede tomar el valor de azul, dando lugar a que el predicado sea falso.
Las variables, también pueden ser cuantificadas. Los cuantificadores que típicamente se utilizan en lógica de predicados son:
- El cuantificador universal; indica que la fórmula bien formada, dentro de su alcance, es verdadera para todos los valores posibles de la variable que es cuantificada. Por ejemplo:
X . . . .
Establece que "para todo X, es verdad que . . . "
- El cuantificador existencial; , indica que la fórmula bien formada, dentro de su alcance, es verdadera para algún valor o valores dentro del dominio. Por ejemplo:
X . . . .
Establece que "existe un X, tal que . . . "
A continuación se dan algunos ejemplos de predicados cuantificados:
X, [niño (X) => le_gusta (X, helados)].
Y, [mamífero (Y) => nace (Y, vivo)].
Z, [cartero(Z) ^ mordió (boby, Z)].
Desde el punto vista de representación, los cuantificadores son difíciles de usar. Por lo que es deseable reemplazarlos con alguna representación equivalente, más fácil de manipular. El caso del cuantificador universal es más simple ya que se asume a todas las variables como universalmente cuantificadas.
El cuantificador existencial es más difícil de reemplazar. El cuantificador existencial garantiza la existencia de uno o más valores particulares (instancias) de la variable cuantificada, que hace a la cláusula verdadera. Si se asume que existe una función capaz de determinar los valores de la variable que hace la cláusula verdadera, entonces simplemente se remueve el cuantificador existencial y se reemplaza las variables por la función que retorna dichos valores. Para la resolución de problemas reales, esta función, llamada función de Skolem, debe ser conocida y definida.
Unificación
Cuando se tienen sentencias compuestas por predicados y conectivos lógicos, se debe evaluar la veracidad de cada uno de sus componentes para determinar si toda la sentencia es verdadera o falsa. Para ello, se busca en el conjunto de axiomas la forma de establecer la veracidad de los predicados componentes. Un predicado componente se dice que es verdadero si se identifica con un axioma de la base de información. En la lógica de predicados, este proceso es algo complicado ya que las sentencias pueden tener términos variables. A los predicados que tienen variables por argumentos, se los denomina patrones.
La unificación es el proceso de computar las sustituciones apropiadas que permitan determinar si dos expresiones lógicas, ya sean predicados o patrones, coinciden.
El proceso de unificación involucra los siguientes pasos:
- Todo predicado que no contenga variables en sus argumentos, deben tener un axioma que se identifique totalmente, para considerarlo como verdadero.
- Si un predicado contiene una variable, esta debe ser asociada a un valor determinado. Esta asociación se realiza buscando en la base de axiomas y seleccionando todos aquellos que se identifican con el patrón en todo, excepto por la variable. La variable es asociada con el valor en la posición correspondiente del axioma. Si más de un axioma se identifica con el predicado dado, todos los valores asociados son considerados y son tratados separadamente.
- El proceso de identificación continua asumiendo que el valor de la variable es el valor asociado, en cualquier lugar que esta aparezca.
- Los conectivos lógicos son aplicados a todos los predicados, para determinar la veracidad de la sentencia dada.
Inferir es concluir o decidir a partir de algo conocido o asumido; llegar a una conclusión. A su vez, razonar es pensar coherente y lógicamente; establecer inferencias o conclusiones a partir de hechos conocidos o asumidos.
El proceso de razonamiento, por lo tanto, involucra la realización de inferencias, a partir de hechos conocidos. Realizar inferencias significa derivar nuevos hechos a partir de un conjunto de hechos conocidos como verdaderos. La lógica de predicados proporciona un grupo de reglas sólidas, con las cuales se pueden realizar inferencias. Las principales Reglas de Inferencia son:
Modus ponens.- Es la más importante, en los sistemas basados en conocimiento. Establece que:
Si las sentencias p y (p q) se conocen que son verdaderas,
entonces se puede inferir que q también es verdadera.
Modus tolens.- Esta regla establece que:
Si la sentencia (p q) es verdadera y q es falsa,
entonces se puede inferir que p también es falsa.
Resolución.- Utiliza refutación para comprobar una determinada sentencia. La refutación intenta crear una contradicción con la negación de la sentencia original, demostrando, por lo tanto, que la sentencia original es verdadera. La resolución es una técnica poderosa para probar teoremas en lógica y constituye la técnica básica de inferencia en PROLOG, un lenguaje que manipula en forma computacional la lógica de predicados. La regla de resolución, establece que:
Si (A B) es verdadero y (~B C) es verdadero,
entonces (A C) también es verdadero
En lógica de predicados, existen tres métodos básicos de razonamiento: deductivo, abductivo e inductivo.
Deducción.- Es el razonamiento a partir de un principio conocido hacia un desconocido; de lo general, a lo específico, o de la premisa a la conclusión lógica. La deducción realiza inferencias lógicamente correctas. Esto significa que la deducción a partir de premisas verdaderas, garantiza el resultado de conclusiones también verdaderas.
La deducción es el método más ampliamente comprendido, aceptado y reconocido de los tres indicados. Es la base tanto de la lógica proposicional, como de la lógica de predicados. A manera de ejemplo, el método deductivo, se puede expresar, utilizando lógica de predicados, como sigue:
A, B, C, [mayor (A, B) mayor (B, C) mayor (A, C)]
Abducción.- Es un método de razonamiento comúnmente utilizado para generar explicaciones. A diferencia de la inducción, la abducción no garantiza que se puedan lograr conclusiones verdaderas, por lo tanto no es un método sólido de inferencia. La forma que tiene la abducción es la siguiente:
Si la sentencia (A B) es verdadera y B es verdadera,
entonces A es posiblemente verdadera.
En abducción, se empieza por una conclusión y se procede a derivar las condiciones que podrían hacer a esta conclusión válida. En otras palabras, se trata de encontrar una explicación para la conclusión.
Inducción.- Se define como el razonamiento a partir de hechos particulares o casos individuales, para llegar a una conclusión general. El método inductivo es la base de la investigación científica. La forma más común del método inductivo es la siguiente:
Si se conoce que P(a), P(b), ……, P(n) son verdaderos,
entonces se puede concluir que X, P(X) es también verdadero.
La inducción es una forma de inferencia muy importante ya que el aprendizaje, la adquisición de conocimiento y el descubrimiento están basados en ella. Al igual que la abducción, la inducción no es un método sólido de inferencia.
El razonamiento deductivo es una forma monotónica de razonar que produce argumentos que preservan la verdad. En un sistema monotónico todos los axiomas utilizados se conocen como verdaderos por sus propios méritos, o pueden ser derivados de otros hechos conocidos como verdaderos. Los axiomas no pueden cambiar, ya que una vez que se los conoce como verdaderos, siempre permanecen así y no pueden ser modificados o retractados. Esto significa que en el razonamiento monotónico el conjunto de axiomas continuamente crece en tamaño.
Otro aspecto del razonamiento monotónico es que si más de una inferencia lógica puede ser hecha a un tiempo específico y una de ellas se realiza, las inferencias que quedan serán todavía aplicables después que dicha inferencia haya sido hecha.
REPRESENTACIÓN MEDIANTE REGLAS DE PRODUCCIÓN
Los sistemas basados en reglas son los más comúnmente utilizados. Su simplicidad y similitud con el razonamiento humano, han contribuido para su popularidad en diferentes dominios. Las reglas son un importante paradigma de representación del conocimiento.
Las reglas representan el conocimiento utilizando un formato SI-ENTONCES (IF-THEN), es decir tienen 2 partes:
- La parte SI (IF), es el antecedente, premisa, condición o situación; y
- La parte ENTONCES (THEN), es el consecuente, conclusión, acción o respuesta.
Las reglas pueden ser utilizadas para expresar un amplio rango de asociaciones, por ejemplo:
SI está manejando un vehículo Y se aproxima una ambulancia, ENTONCES baje la velocidad Y hágase a un lado para permitir el paso de la ambulancia.
SI su temperatura corporal es de 39 ºC, ENTONCES tiene fiebre.
SI el drenaje del lavabo está tapado Y la llave de agua está abierta, ENTONCES se puede inundar el piso.
Inferencia Basada en Reglas
Una declaración de que algo es verdadero o es un hecho conocido, es una afirmación (fact). El conjunto de afirmaciones se conoce a menudo con el nombre de memoria de trabajo o base de afirmaciones. De igual forma, al conjunto de reglas se lo denomina base de reglas.
Un sistema basado en reglas utiliza el modus ponens para manipular las afirmaciones y las reglas durante el proceso de inferencia. Mediante técnicas de búsqueda y procesos de unificación, los sistemas basados en reglas automatizan sus métodos de razonamiento y proporcionan una progresión lógica desde los datos iniciales, hasta las conclusiones deseadas. Esta progresión hace que se vayan conociendo nuevos hechos o descubriendo nuevas afirmaciones, a medida que va guiando hacia la solución del problema.
En consecuencia, el proceso de solución de un problema en los sistemas basados en reglas va realizando una serie de inferencias que crean un sendero entre la definición del problema y su solución. Las inferencias están concatenadas y se las realiza en forma progresiva, por lo que se lo que se dice que el proceso de solución origina una cadena de inferencias.
Los sistemas basados en reglas difieren de la representación basada en lógica en las siguientes características principales:
- Son en general no-monotónicos, es decir hechos o afirmaciones derivadas, pueden ser retractados, en el momento en que dejen de ser verdaderos.
- Pueden aceptar incertidumbre en el proceso de razonamiento.
El proceso de razonamiento en un sistema basado en reglas es una progresión desde un conjunto inicial de afirmaciones y reglas hacia una solución, respuesta o conclusión.
Como se llega a obtener el resultado, sin embargo, puede variar significativamente:
- Se puede partir considerando todos los datos conocidos y luego ir progresivamente avanzando hacia la solución. Este proceso se lo denomina guiado por los datos o de encadenamiento progresivo (forward chainning).
- Se puede seleccionar una posible solución y tratar de probar su validez buscando evidencia que la apoye. Este proceso se denomina guiado por el objetivo o de encadenamiento regresivo (backward chainning).
Razonamiento Progresivo
En el caso del razonamiento progresivo, se empieza a partir de un conjunto de datos colectados a través de observación y se evoluciona hacia una conclusión. Se chequea cada una de las reglas para ver si los datos observados satisfacen las premisas de alguna de las reglas. Si una regla es satisfecha, es ejecutada derivando nuevos hechos que pueden ser utilizados por otras reglas para derivar hechos adicionales. Este proceso de chequear reglas para ver si pueden ser satisfechas se denomina interpretación de reglas.
La interpretación de reglas es realizada por una máquina de inferencia en un sistema basado en conocimiento. La interpretación de reglas, o inferencia, en el razonamiento progresivo involucra la repetición de los pasos que se indican en la siguiente figura.
Razonamiento Progresivo…
- Unificación (Matching).- En este paso, en las reglas en la base de conocimientos se prueban los hechos conocidos al momento para ver cuáles son las que resulten satisfechas. Para decir que una regla ha sido satisfecha, se requiere que todas las premisas o antecedentes de la regla resuelvan a verdadero.
- Resolución de Conflictos.- Es posible que en la fase de unificación resulten satisfechas varias reglas. La resolución de conflictos involucra la selección de la regla que tenga la más alta prioridad de entre el conjunto de reglas que han sido satisfechas.
- Ejecución.- El último paso en la interpretación de reglas es la ejecución de la regla. La ejecución puede dar lugar a uno o dos resultados posibles: nuevo hecho (o hechos) pueden ser derivados y añadidos a la base de hechos, o una nueva regla (o reglas) pueden ser añadidas al conjunto de reglas (base de conocimiento) que el sistema considera para ejecución.
En esta forma, la ejecución de las reglas procede de una manera progresiva (hacia adelante) hacia los objetivos finales.
Un conjunto de aplicaciones adecuadas al razonamiento progresivo incluye supervisión y diagnóstico en sistemas de control de procesos en tiempo real, donde los datos están continuamente siendo adquiridos, modificados y actualizados. Estas aplicaciones tienen 2 importantes características:
- Necesidad de respuesta rápida a los cambios en los datos de entrada.
- Existencia de pocas relaciones predeterminadas entre los datos de entrada y las conclusiones derivadas.
Otro conjunto de aplicaciones adecuadas para el razonamiento progresivo está formado por: diseño, planeamiento y calendarización, donde ocurre la síntesis de nuevos hechos basados en las conclusiones de las reglas. En estas aplicaciones hay potencialmente muchas soluciones que pueden ser derivadas de los datos de entrada.
Debido a que estas soluciones no pueden ser enumeradas, las reglas expresan conocimiento como patrones generales y las conexiones precisas entre estas reglas no pueden ser predeterminadas.
Razonamiento Regresivo
El mecanismo de inferencia, o interprete de reglas para el razonamiento regresivo, difiere significativamente del mecanismo de razonamiento progresivo. Si bien es cierto ambos procesos involucran el examen y aplicación de reglas, el razonamiento regresivo empieza con la conclusión deseada y decide si los hechos que existen pueden dar lugar a la obtención de un valor para esta conclusión. El razonamiento regresivo sigue un proceso muy similar a la búsqueda primero en profundidad.
El sistema empieza con un conjunto de hechos conocidos que típicamente está vacío. Se proporciona una lista ordenada de objetivos (o conclusiones), para las cuales el sistema trata de derivar valores. El proceso de razonamiento regresivo utiliza esta lista de objetivos para coordinar su búsqueda a través de las reglas de la base de conocimientos. Esta búsqueda consiste de los siguientes pasos:
- Conformar una pila inicialmente compuesta por todos los objetivos prioritarios definidos en el sistema.
- Considerar el primer objetivo de la pila. Determinar todas las reglas capaces de satisfacer este objetivo, es decir aquellas que mencionen al objetivo en su conclusión.
- Si todos los antecedentes de la regla son satisfechos (esto es, cada parámetro de la premisa tiene su valor especificado dentro de la base de datos), entonces ejecutar esta regla para derivar sus conclusiones. Debido a que se ha asignado un valor al objetivo actual, removerlo de la pila y retornar al paso (2).
- Si alguna premisa de la regla no puede ser satisfecha, buscar reglas que permitan derivar el valor especificado para el parámetro utilizado en esta premisa.
- Si en el paso (b) no se puede encontrar una regla para derivar el valor especificado para el parámetro actual, entonces preguntar al usuario por dicho valor y añadirlo a la base de datos. Si este valor satisface la premisa actual entonces continuar con la siguiente premisa de la regla. Si la premisa no es satisfecha, considerar la siguiente regla.
Si todas las reglas que pueden satisfacer el objetivo actual se han probado y todas no han podido derivar un valor, entonces este objetivo quedará indeterminado. Removerlo de la pila y retornar al paso (2). Si la pila está vacía parar y anunciar que se ha terminado el proceso.
El razonamiento regresivo es mucho más adecuado para aplicaciones que tienen mucho mayor número de entradas, que de soluciones posibles. La habilidad de la lógica regresiva para trazar desde las pocas conclusiones hacia las múltiples entradas la hace más eficiente que el encadenamiento progresivo.
Una excelente aplicación para el razonamiento regresivo es el diagnóstico, donde el usuario dialoga directamente con el sistema basado en conocimiento y proporciona los datos a través del teclado. Problemas de clasificación también son adecuados para ser resuelto mediante el razonamiento regresivo.
SISTEMAS BASADOS EN CONOCIMIENTO
Los métodos generales desarrollados para la resolución de problemas y técnicas de búsqueda al inicio de la era de la IA demostraron no ser suficientes para resolver los problemas orientados a las aplicaciones, ni fueron capaces de satisfacer los difíciles requerimientos de la investigación. A este conjunto de métodos, procedimientos y técnicas, se lo conoce como Inteligencia Artificial Débil. La principal conclusión que se derivó de este trabajo inicial fue que los problemas difíciles sólo podrían ser resueltos con la ayuda del conocimiento específico acerca del dominio del problema.
La aplicación de estas ideas dio lugar al desarrollo de los denominados Sistemas Basados en Conocimiento (Knowledge Based Systems) y al aparecimiento de la Ingeniería Cognoscitiva, como una rama de la IA, que estudia los sistemas basados en el conocimiento. La definición de un sistema basado en conocimiento puede ser simplemente la siguiente:
Es un sistema computarizado capaz de resolver problemas en el dominio en el cual posee conocimiento específico.
La solución es esencialmente la misma que hubiera dado un ser humano confrontado con idéntico problema, aunque no necesariamente el proceso seguido por ambos puede ser igual.
El simple concepto dado, puede causar confusión ya que muchos sistemas basados en programas convencionales podrían ser incorrectamente categorizados como sistemas basados en conocimiento. Esta inconsistencia puede ser aclarada, sobre la base de tres conceptos fundamentales que distinguen a los sistemas basados en conocimiento de los programas algorítmicos convencionales y de los programas generales basados en búsqueda (IA débil):
- Para cada una de estas reglas examinar en turno sus antecedendentes:
- La separación que existe entre el conocimiento, y la forma cómo éste es utilizado.
- El uso de conocimiento específico de un determinado dominio.
- La naturaleza heurística, antes que algorítmica del conocimiento utilizado.
Dicho de una manera simple, los programas convencionales utilizan algoritmos para resolver problemas, mientras que los sistemas basados en conocimiento resuelven problemas donde las soluciones algorítmicas no existen o son muy costosas para ser implementadas.
Experiencia, Habilidades y Conocimiento
Los tipos de experiencia que son interés en los sistemas basados en conocimiento, pueden ser clasificados en tres categorías: asociativa, motora y teórica.
Los sistemas basados en conocimiento son excelentes para representar conocimiento asociativo. Este tipo de experiencia refleja la habilidad heurística o el conocimiento que es adquirido mayoritariamente, a través de la observación. Puede ser que no se comprenda exactamente lo que ocurre al interior de un sistema (caja negra), pero se puede asociar entradas o estímulos con salidas o respuestas, para resolver problemas que han sido previamente conocidos.
La experiencia motora es más física que cognitiva. La habilidad se adquiere fundamentalmente a través del ejercicio y la práctica física constante. Los sistemas basados en conocimiento no pueden emular fácilmente este tipo de experiencia, principalmente por la limitada capacidad de la tecnología robótica.
La experiencia teórica y el conocimiento profundo permite que los humanos podamos resolver problemas que no los hemos visto antes, es decir que no existe una posibilidad asociativa. El conocimiento teórico y profundo se lo adquiere a través de estudio y entrenamiento formal, así como por medio de la resolución directa de problemas. Debido a la naturaleza teórica, este conocimiento se lo puede olvidar fácilmente, a no ser que se lo use en forma continua. Al momento, los sistemas convencionales basados en conocimiento tienen muchas dificultades para duplicar este tipo de experiencia. Sin embargo, los Sistemas de Razonamiento Basado en Modelos representan un notable intento de encapsular este conocimiento profundo y razonar con él.
En las siguientes secciones se concentrará el estudio en los sistemas basados en conocimiento que representan experiencias de tipo asociativo.
Estructura de los SBC
La arquitectura de un sistema basado en conocimiento de alguna manera refleja la estructura cognitiva y los procesos humanos. La primera parte es la memoria de largo plazo, en la que guarda los hechos (Base de Hechos) y los conocimientos (Base de Conocimientos) acerca del dominio en el que tiene experiencia.
Figura 6.1. Estructura de un sistema basado en conocimiento
La segunda parte es el sistema que realiza la función de razonamiento para resolver problemas (Motor de Inferencia). Finalmente, la tercera parte la conforman las unidades de entrada y salida que permiten la comunicación entre el sistema y su entorno.
A continuación se describen las principales características de estas unidades.
El Motor de inferencia (MI)
Selecciona, decide, interpreta y aplica el conocimiento de la base de conocimientos sobre la base de hechos con el fin de obtener la solución buscada. Un mecanismo de inferencia debe ser independiente del conocimiento y de los hechos. Está caracterizado por:
- El lenguaje en que ha sido escrito.
- La velocidad de trabajo: Inferencias/segundo.
- Las estrategias de búsqueda de soluciones:
No Ordenada: aleatoria, heurística.
Ordenada: Encadenamiento hacia adelante (guiado por los datos, deductivo), encadenamiento hacia atrás (guiado por los objetivos, inductivo).
- La forma en que elige el conocimiento.
- La posibilidad de incorporar metaconocimiento.
- El tipo de lógica que emplea en el razonamiento:
Booleana, trivalente, multivalente, difusa.
Monotónica o no monotónica.
Atemporal o temporal.
Lógica de orden 0, orden 0+, orden 1.
- El método que utiliza para la evaluación del conocimiento incompleto o incierto:
Determinístico.
Probabilístico.
Aproximado.
Difuso.
La Base de Conocimientos
Contiene el conocimiento del dominio en el cual el programa es competente. El conocimiento tiene que estar representado en la forma que resulte más adecuada para el dominio de su competencia. Adicionalmente hay que tratar que esa representación sea:
- Sencilla.
- Independiente.
- Fácil de modificar.
- Transparente: justificación de soluciones y explicación de los procesos.
- Relacional.
- Potente: poder expresivo y eficiencia de cálculo.
Un aspecto importante de una base de conocimientos es su capacidad, expresada sobre la base del número de reglas que posee:
- Demostración interesante: 50 reglas.
- Prototipo funcional: 250 reglas.
- SE operacional medio: 500 – 1000 reglas.
- SE operacional especial: 4000 reglas.
Una base de conocimientos debe ser coherente, rápida, modular, fácil de desarrollar y mantener.
La Base de Hechos
La base de hechos es el conjunto de información invariable de una a otra resolución. Los hechos se diferencian de los datos en el sentido que los hechos forman parte del SBC, mientras que los datos, al poder variar de una solución a otra, conviene agruparlos en archivos externos al SBC.
Algunos autores no consideran a la base de hechos en forma independiente. Los conocimientos y los hechos pueden aparecer conjuntamente en una sola base, la de conocimientos.
Los Módulos de Comunicación
Un SE necesita medios y canales adecuados, sencillos y potentes, para comunicarse:
- Con el usuario:Para permitir el diálogo en forma sencilla.
- Con el experto:Para la configuración del sistema; para la adquisición, mantenimiento, depuración y validación del conocimiento.
- Con archivos externos: Bases de datos, hojas electrónicas de cálculo, archivos de texto, programas.
Desde el punto de vista de la especificidad del conocimiento, los sistemas basados en conocimiento ocupan un lugar intermedio entre los sistemas originales de IA débil, en los que el conocimiento utilizado es de carácter general, y los Sistemas Expertos (SE) que operan en un dominio muy restringido, utilizando conocimiento altamente especializado.
A la luz de esta cadena de desarrollo, un sistema experto puede ser definido como un sistema basado en conocimiento que emula la competencia de un experto, dentro de un campo de aplicación bien delimitado. También puede ser definido como un conjunto de programas de computadora cuyo comportamiento es similar al que tendría un experto humano
Características de los Sistemas Expertos
Para que un sistema computacional actúe como un verdadero experto, es deseable que reúna, en lo posible, lo más importante de las características de un experto humano, esto es:
- Habilidad para adquirir conocimiento.
- Fiabilidad, para poder confiar en sus resultados o apreciaciones.
- Solidez en el dominio de su conocimiento.
- Capacidad para resolver problemas.
Dada la complejidad de los problemas que usualmente tiene que resolver un SE, puede existir cierta duda en el usuario sobre la validez de respuesta obtenida. Por este motivo, es una condición indispensable que un SE sea capaz de explicar su proceso de razonamiento o dar razón del por qué solicita tal o cual información o dato.
Faustino Peraza Rodriguez
E-Mail :