Sistemas Basados en el Conocimiento
De Computacion
No hace mucho tiempo, se creían que algunos problemas como la demostración de teoremas, el reconocimiento de la voz y el de patrones, ciertos juegos (como el ajedrez o las damas), y sistemas altamente complejos de tipo determinista o estocástico, debían ser resueltos por personas, dado que su formulación y resolución requieren ciertas habilidades que solo se encuentran en los seres humanos (por ejemplo, la habilidad de pensar, observar, memorizar, aprender, ver, oler, etc.). Sin embargo, el trabajo realizado en las tres ultimas décadas por investigadores procedentes de varios campos, muestra que muchos de estos problemas pueden ser formulados y resueltos por maquinas. El amplio campo que se conoce como inteligencia artificial (IA) trata de estos problemas, que en un principio parecían imposibles, intratables y difíciles de formular utilizando ordenadores. A. Barr y E. A. Feigenbaum, dos de los pioneros de la investigación en IA, definen esta como sigue: “La Inteligencia Artificial es la parte de la Ciencia que se ocupa del diseño de sistemas de computación inteligentes, es decir, sistemas que exhiben las características que asociamos a la inteligencia en el comportamiento humano que se refiere a la comprensión del lenguaje, el aprendizaje, el razonamiento, la resolución de problemas, etc. En la primera parte veremos temas relacionados a la Inteligencia artificial, cuáles fueron sus inicios, sus áreas de aplicación, los algoritmos de búsqueda existentes y finalizaremos analizando las ventajas y desventajas de los métodos de búsqueda más conocidos como son en anchura y profundidad. Para la segunda parte revisaremos los temas de algoritmos de búsqueda en grafos explícitos, y abordaremos el tema de la lógica de predicados, se propondrá el desarrollo de algunos ejercicios y de lecturas para que se comprenda mucho mejor los métodos de búsqueda planteados en el presente capitulo. Esta guía didáctica trata de dar una visión real y práctica de la temática abordada a través de la inclusión de explicaciones, ejemplos y otros temas relacionados al tema, para que el profesional en formación pueda asimilar de mejor forma los conceptos y teorías que encontrará en los libros y bibliografía de Internet.
Objetivos Generales
- Dotar al profesional en formación de las bases formales para el estudio y práctica de la IA en la vida diaria.
- Dar a conocer al profesional en formación algunas áreas de aplicación de la IA.
-
Desarrollar en el profesional en formación las destrezas necesarias para que pueda iniciar o continuar su investigación en el ámbito de la Inteligencia Artificial.
Objetivos Especificos
- Identificar cuales son las áreas de aplicación de la inteligencia artificial y cuál es el futuro de la IA.
- Adquirir las destrezas necesarias para resolver problemas relacionados con la Inteligencia Artificial.
- Conocer los pasos y términos utilizados para la resolución de problemas.
- Conocer y aplicar los métodos de búsqueda en anchura y profundidad.
- Conocer cuales son las ventajas y desventajas de utilizar los diferentes algoritmos de búsqueda.
- Conocer el campo de la lógica de predicados en la resolución de problemas de IA.
- Identificar los elementos principales y cuales son los avances de la tecnología en el campo de los Sistemas Expertos.
-
Proponer situaciones reales en las cuales se pueda ver inmerso el ámbito de los sistemas expertos conjuntamente con los algoritmos de búsqueda y decisión.
Bibliografía
Texto Básico: [NILS2001] NILS J. NILSON, Inteligencia Artificial “Una nueva síntesis“, McGraw-Hill, Madrid, 2001, 458 pág.
Se ha elegido éste libro para la asignatura debido a que posee los contenidos requeridos para el estudio de la Inteligencia
Artificial. Además mantiene una concordancia con los contenidos de asignatura de Sistemas Inteligentes I ya que se emplean algunos capítulos del libro para dicha asignatura.
Bibliografía complementaria:
[ELA1998] ELAINE RICH, KEVIN KNIGHT., Inteligencia Artificial, McGraw-Hill, Madrid, 1994, 2da. Edición en español, 703 p.
Este texto constituye el principal complemento para el estudio de la asignatura. Provee algunas definiciones un poco mas claras con ejemplos gráficos y con procedimientos explicados.
Otras fuentes de información:
Otra fuente de información muy importante es el Internet. Aquí mostramos algunas direcciones de páginas web que resultan de interés para ésta asignatura:
Página principal dedicada a términos básicos de IA, ¿Qué es la IA? y cuáles son sus principales aplicaciones. (Idioma Inglés)
Página dedicada al uso de grafos en búsquedas en anchura y profundidad.
Página con ejemplos a desarrollar con la máquina de Turing, sus elementos, su recorrido, la declaración de reglas y un applet para ser utilizado en el desarrollo de sus ejercicios.
Página en la cual se menciona el funcionamiento de una máquina de Turing
Página en la cual se define a cada uno de los algoritmos de busqueda utilizados en IA, tales como A*, en anchura, en profundidad.
Desarrollo del Aprendizaje
Capitulo 1 : ¿QUÉ ES LA INTELIGENCIA ARTIFICIAL?
Datos Generales:
| Texto Base | Nils J. Nilsson. Inteligencia Artificial: Una nueva Síntesis. McGRAW-HILL. Madrid, España. 2001 |
| Capítulo | 1. ¿Qué es la IA? |
| Páginas | 1 – 15 |
| Horas de estudio empleadas para el desarrollo del contenido | 2 horas |
Propositos:
El propósito de este capítulo es conocer en forma general los aspectos relacionados con la IA, sus aplicaciones, el futuro de la IA, la dualidad que existe con otras ciencias, las técnicas y campos de la IA. Así también trabajaremos en el aspecto de investigar o conocer acerca de algunos proyectos que se llevan a cabo con IA en la vida cotidiana.
Conceptos Claves:
- ¿Por qué el estudio de la IA?
Una de las grandes razones por la cuales se realiza el estudio de la IA es el poder aprender más acerca de nosotros mismos a diferencia de la psicología y de la filosofía que también centran su estudio de la inteligencia. La IA y sus esfuerzos por comprender este fenómeno están encaminados tanto a la construcción de entidades inteligentes como su comprensión. La IA es una de las disciplinas más nuevas que junto con la genética moderna es el campo en que la mayoría de los científicos “ más les gustaría trabajar”.<7p>
- Enfoques de la IA
En la IA se puede observar dos enfoques diferentes:
- <p align='justify'> • La IA concebida como el intento por desarrollar una tecnología capáz de proveer al ordenador capacidades de razonamiento similares a los de la inteligencia humana.
• La IA en su concepción como investigación relativa a los mecanismos de la inteligencia humana que se emplean en la simulación de validación de teorías.
- ¿Qué es una técnica de IA?
Una técnica de IA es un método que utiliza conocimiento representado de tal forma que no sea necesario representar de forma separada cada situación individual.
En lugar de esto, se agrupan las situaciones que comparten propiedades importantes. Si el conocimiento no posee esta propiedad, puede necesitarse demasiada memoria. Si no se cumple esta propiedad es mejor hablar de “datos” que de conocimiento.
Una técnica de IA es aquella que puede modificarse fácilmente para corregir errores y reflejar los cambios en el mundo y nuestra visión del mundo.
Esquema de Estudio:
A continuación se detallan los temas que se deben llevar a cabo, una descripción general del mismo, y un conjunto de actividades que se recomienda sean desarrolladas para una mejor asimilación y comprensión de los conceptos. Se han dispuesto las tres columnas de la derecha para llevar un control personal del tiempo de dedicación a cada tema, marcar las actividades que estima que necesita tutoría y realizar anotaciones.
| Tema a revisar | Descripción del Contenido a revisar | Actividades Recomendadas | Planificación Personal del estudio (fecha) | ¿Requiero Tutorial? | Anotaciones |
|---|---|---|---|---|---|
| 1.1 ¿Qué es la IA? | En este apartado se hace una breve descripción de cómo surge la IA y cuales fueron algunos de los términos utilizados. | Revise el tema referente a entidad inteligente, los puntos de vista sobre el tipo de máquinas, el procesamiento subsimbólico y el Test de Turing (¿Qué es? y ¿para qué sirve?) | |||
| 1.2. Aproximaciones a la Inteligencia Artificial | Se describe algunos símbolos y las aproximaciones basadas en el conocimiento. | Revise lo referente a los niveles de conocimiento, el comportamiento emergente. | |||
| 1.3. Breve Historia de la IA | En este apartado se detallan algunas aplicaciones que dieron inicio al estudio de la IA y quienes fueron algunos de sus precursores. | Revise el tema referente al primer programa en el que se utilizo IA (Dendral). |
Capitulo 2 : PROBLEMAS QUE SE RESUELVEN CON IA
Datos Generales:
| Texto Base | Nils J. Nilsson. Inteligencia Artificial: Una nueva Síntesis. McGRAW-HILL. Madrid, España. 2001 |
| Capítulo | 7. Agentes que planifican |
| Páginas | 105 – 113 |
| Horas de estudio empleadas para el desarrollo del contenido | 4 horas |
Propositos:
El propósito de este capítulo es conocer en forma general cuales son las acciones para resolver un problema de IA. Determinar algunos elementos como son: los estados, operadores, solución, entre otros.
Conceptos Claves:
- ¿Cuáles son las acciones para resolver un problema?
- Son cuatro las acciones principales para resolver un problema:
- 1. Definir el problema con precisión.
- 2. Analizar el problema.
- 3. Aislar y representar el conocimiento necesario para resolver el problema
- 4. Elegir la mejor técnica(s) que resuelva el problema y aplicarla(s) al problema particular.
- Conceptos utilizados en la resolución de problemas de IA
- Estado: Se define a cada una de las situaciones en las que nos podemos encontrar durante la resolución de un problema.
- - Estado inicial: situación de partida.
- - Estado final: situación a la que se desea llegar, que cumple unas condiciones determinadas.
- - Operador: acción que podemos realizar en un estado para pasar a otro estado diferente.
- - Espacio de estados: Se define como un grafo etiquetado dirigido
- - Nodos: estados posibles.
- - Aristas: aplicación de un operador a un estado para pasar a otro estado diferente.
- - Etiqueta de una arista: identificador del operador aplicado.
- Solución: Una solución se puede definir como una secuencia de estados e1, e2, ..., en, donde e1 es el estado inicial y en es un estado final.
- Requisitos fundamentales a cumplir por una estrategias de Control
El primer requisito que debe cumplir una buena estrategia de control es que cause algún cambio
El segundo requisito que debe cumplir una buena estrategia de control es que sea sistemática.
Esquema de Estudio:
A continuación se detallan los temas que se deben llevar a cabo, una descripción general del mismo, y un conjunto de actividades que se recomienda sean desarrolladas para una mejor asimilación y comprensión de los conceptos. Se han dispuesto las tres columnas de la derecha para llevar un control personal del tiempo de dedicación a cada tema, marcar las actividades que estima que necesita tutoría y realizar anotaciones.
| Tema a revisar | Descripción del Contenido a revisar | Actividades Recomendadas | Planificación Personal del estudio (fecha) | ¿Requiero Tutorial? | Anotaciones |
|---|---|---|---|---|---|
| 7.2 Grafos de Estado | En este apartado se hace una breve descripción acerca de la utilización de grafos para representar los diferentes problemas a tratar en IA. | Revise algunos temas relacionados con definiciones de grafos y su representación. | |||
| 7.3 Búsqueda en estados explícitos | Se menciona una de las formas de cómo resolver un problema utilizando el estado inicial y como llegar al estado objetivo. | Resuelva ejercicios como las jarras de agua, misioneros y caníbales y trate de representar su estado(s) inicial(es) y final(es) | |||
| 7.5 Notación de Grafos | Composición y denominación de un grafo, coste de un camino entre nodos. | Revisar el algoritmo y algunas aplicaciones de dijkstra. |
Capitulo 3 :¿QUÉ ES LA INTELIGENCIA ARTIFICIAL?
Datos Generales:
| Texto Base | Nils J. Nilsson. Inteligencia Artificial: Una nueva Síntesis. McGRAW-HILL. Madrid, España. 2001 |
| Capítulo | 8. Búsquedas a ciegas |
| Páginas | 115 – 125 |
| Horas de estudio empleadas para el desarrollo del contenido | 8 horas |
Propositos:
El propósito de este capítulo es conocer las definiciones y características de los métodos de búsqueda utilizados en IA, específicamente la búsqueda en anchura, profundidad y heurística.
Conceptos Claves:
- Ventajas Búsqueda en Profundidad
- La búsqueda primero en profundidad necesita menos memoria ya que solo se almacenan los nodos del camino que se sigue en ese instante. Esto contrasta con la búsqueda primero en anchura en la que debe almacenarse todo el árbol que hay sido generado hasta ese momento.
- Si se tiene suerte (o si se tiene cuidado en ordenar los estados alternativos sucesores), la búsqueda primero en profundidad puede encontrar una solución si tener que examinar gran parte del espacio de estados.
- - Puede encontrar una solución sin examinar mucho el árbol, sobretodo si hay varios caminos a la solución.
- Ventajas Búsqueda en Anchura
- La búsqueda primero en anchura no queda atrapada explorando callejones sin salida. Esto se contrapone con la búsqueda primero en profundidad en la que se puede seguir una ruta infructuosa durante mucho tiempo, y quizás para siempre, antes de acabar en un estado sin sucesores.
- Si existe una solución, la búsqueda primero en anchura garantiza que se encontrarla. Además, si existen, múltiples soluciones, se encuentra la solución mínima (es decir la que requiere el mínimo numero de pasos). Esto esta garantizado por el hecho de que no se explora una ruta larga hasta que se hayan examinado todas las rutas mas cortas que ella. En cambio en la búsqueda primero en profundidad es posible encontrar una solución larga en alguna parte del árbol, cuando puede existir otra mucho mas corta en alguna parte inexplorada del mismo.
- - Si hay una solución la encuentra. Es mas si hay varias encuentra la óptima.
- Ventajas de las Heurísticas
- - Normalmente, en problemas complejos no necesitamos soluciones óptimas, solo suficientemente buenas.
- Aunque las aproximaciones conseguidas con heuristicos no sean buenas en el peor de los casos, el caso peor no se da normalmente.
- Tratar de entender por qué o (por qué no) funciona un heuristico muchas veces nos da un conocimiento mayor del problema que estamos intentando resolver.
Esquema de Estudio:
A continuación se detallan los temas que se deben llevar a cabo, una descripción general del mismo, y un conjunto de actividades que se recomienda sean desarrolladas para una mejor asimilación y comprensión de los conceptos. Se han dispuesto las tres columnas de la derecha para llevar un control personal del tiempo de dedicación a cada tema, marcar las actividades que estima que necesita tutoría y realizar anotaciones.
| Tema a revisar | Descripción del Contenido a revisar | Actividades Recomendadas | Planificación Personal del estudio (fecha) | ¿Requiero Tutorial? | Anotaciones |
|---|---|---|---|---|---|
| 8.1. Especificación del espacio de búsqueda | En este apartado se hace una breve descripción acerca de la utilización de grafos para representar los diferentes problemas a tratar en IA. | Revise algunos temas relacionados con definiciones de grafos y su representación. | |||
| 8.3 Búsqueda primero en anchura | Cual es la principal propiedad de este tipo de búsqueda | Revisar material adicional de eva, dirección del recorrido en un árbol. | |||
| 8.4 Búsqueda primero en profundidad | Características, consideraciones en relación al coste de memoria. | Revisar material adicional de eva, dirección del recorrido en un arbol. Revisar ejercicios desarrollados en material adicional | |||
| 9.1 Búsqueda Heurística | Función de evaluación heurística y sus componentes |
Capitulo 4: BÚSQUEDA HEURÍSTICA Y EN GRAFOS
Datos Generales:
| Texto Base | Nils J. Nilsson. Inteligencia Artificial: Una nueva Síntesis. McGRAW-HILL. Madrid, España. 2001 |
| Capítulo | 9. Búsqueda heurística |
| Páginas | 125-144 |
| Horas de estudio empleadas para el desarrollo del contenido | 10 horas |
Propositos:
El propósito de este capítulo es conocer la definición y característica de una función heurística, y vamos a revisar el algoritmo A* y todas sus capacidades.
Conceptos Claves:
- Función Heurística
Una función heurística es una correspondencia entre las descripciones de estados del problema hacia alguna medida de deseabilidad, normalmente representada por números. Los aspectos de los problemas que se consideran, como se evalúan estos aspectos, y los pesos que se dan a los aspectos individuales, se eligen de forma que el valor que la función heurística da a un nodo en el proceso de búsqueda, sea una estimación tan buena como sea posible para ver si ese nodo pertenece a la ruta que conduce a la solución.
- Propósito del uso de una función heurística
El propósito de una función heurística es el de guiar el proceso de búsqueda en la dirección mas provechosa sugiriendo que camino se debe guiar primero cuando hay mas de uno disponible. Cuando más exactamente estime la función heurística los meritos de cada nodo del árbol (o grafo), as directo será el proceso de solución.
- Ventajas de las Heurísticas
- - Normalmente, en problemas complejos no necesitamos soluciones óptimas, solo suficientemente buenas.
- Aunque las aproximaciones conseguidas con heuristicos no sean buenas en el peor de los casos, el caso peor no se da
- Tratar de entender por qué o (por qué no) funciona un heuristico muchas veces nos da un conocimiento mayor del problema que estamos intentando resolver
- Descripción del Algoritmo A*
El algoritmo A* utiliza una función de evaluación f(n) = g(n) + h(n), donde h(n) representa el valor heurístico del nodo a evaluar, y g(n), el coste real del camino recorrido para llegar a dicho nodo. A* mantiene dos estructuras de datos auxiliares, que podemos denominar abiertos, implementado como una cola de prioridad (ordenada por el valor f(n) de cada nodo), y cerrados, donde se guarda la información de los nodos que ya han sido visitados.
En cada paso del algoritmo, se expande el nodo que esté primero en abiertos, y en caso de que no sea un nodo objetivo, calcula la f(n) de todos sus hijos, los inserta en abiertos, y pasa el nodo evaluado a cerrados.
El algoritmo es una combinación entre búsquedas del tipo primero en anchura con primero en profundidad: mientras que h(n) tiende a primero en profundidad, g(n) tiende a primero en anchura. De este modo, se cambia de camino de búsqueda cada vez que existen nodos más prometedores.
Esquema de Estudio:
A continuación se detallan los temas que se deben llevar a cabo, una descripción general del mismo, y un conjunto de actividades que se recomienda sean desarrolladas para una mejor asimilación y comprensión de los conceptos. Se han dispuesto las tres columnas de la derecha para llevar un control personal del tiempo de dedicación a cada tema, marcar las actividades que estima que necesita tutoría y realizar anotaciones.
| Tema a revisar | Descripción del Contenido a revisar | Actividades Recomendadas | Planificación Personal del estudio (fecha) | ¿Requiero Tutorial? | Anotaciones |
|---|---|---|---|---|---|
| 9.1 Funciones de Evaluación | Se define a la función heurística y la descripción de sus componentes. | Revisar los anexos del tema
Complementar tema con lectura de capitulo 9.3 | |||
| 9.2 Algoritmo genérico de búsqueda en grafos | Vamos a revisar el algoritmo, admisibilidad y otras características del Algoritmo A*. | Revisar los anexos del tema.
Revisar los factores que influyen en el algoritmo A*. (Pág. 142) |
Capitulo 5: BÚSQUEDAS Y MÉTODOS
Datos Generales:
| Texto Base | Nils J. Nilsson. Inteligencia Artificial: Una nueva Síntesis. McGRAW-HILL. Madrid, España. 2001 |
| Capítulo | 12. Búsqueda en problemas de Juego |
| Páginas | 175 -186 |
| Horas de estudio empleadas para el desarrollo del contenido | 10 horas |
Propositos:
El propósito de este capítulo es combinar los conceptos utilizados en los capítulos anteriores para resolver problemas de IA, en la mayoría de los casos en aplicaciones de juegos de IA.
Conceptos Claves:
- Procedimiento de Búsqueda Mínimax
- Es un procedimiento de búsqueda en profundidad, de profundidad limitada.
Esquema de Estudio:
A continuación se detallan los temas que se deben llevar a cabo, una descripción general del mismo, y un conjunto de actividades que se recomienda sean desarrolladas para una mejor asimilación y comprensión de los conceptos. Se han dispuesto las tres columnas de la derecha para llevar un control personal del tiempo de dedicación a cada tema, marcar las actividades que estima que necesita tutoría y realizar anotaciones.
| Tema a revisar | Descripción del Contenido a revisar | Actividades Recomendadas | Planificación Personal del estudio (fecha) | ¿Requiero Tutorial? | Anotaciones |
|---|---|---|---|---|---|
| 12.2 Procedimiento Mínimax | Se define a la función heurística y la descripción de sus componentes. | Revisar los anexos del tema
Complementar tema con lectura de capitulo 9.3 | |||
| 12.3 | Algoritmo de Dijkstra | Revisar material del EVA, Documento Dijkstra.pdf | |||
| 12.4 Procedimiento alfa-beta | Definición del procedimiento Alfa Beta | Revisar los anexos de Tema (Anexo I).
Revisar eficiencia del procedimiento alfa-beta. Revisar los valores alfa y beta de un nodo MAX y MIN respectivamente, Pág. 183. |
Capitulo 6: LÓGICA DE PREDICADOS
Datos Generales:
| Texto Base | Nils J. Nilsson. Inteligencia Artificial: Una nueva Síntesis. McGRAW-HILL. Madrid, España. 2001 |
| Capítulo | 15. El cálculo de predicados |
| Páginas | 215 |
| Horas de estudio empleadas para el desarrollo del contenido | 8 horas |
Propositos:
El propósito de este capítulo estudiar uno de los mecanismos concretos de representación del conocimiento, el aspecto mas atractivo del formalismo lógico es que proporciona de manera inmediata un método muy potente para la obtención de nuevo conocimiento. Para el presente capitulo es necesario que recordemos algunos aspectos relacionados con la lógica proposicional y de predicados.
Conceptos Claves:
- Idea de la lógica de predicados
-
La lógica de predicados, llamada también lógica cuantificacional, comienza distinguiendo dos clases de términos, los que representan individuos (gramaticalmente “sujetos”) y los que representan propiedades (gramaticalmente “predicados”), lógicamente llamados argumentos y predicados respectivamente. Ejemplo:
- Raúl canta donde: Raúl = Argumento; canta = predicado.
- Clasificación de la lógica de predicados de acuerdo a la cantidad del sujeto
- - Singulares: el sujeto es un individuo: Ejemplo: Manuel Kant es filosofo.
- - Universales: el sujeto es una totalidad de individuos. Ejemplo: Todos los geriatras son médicos.
- - Particulares: el sujeto es una parcialidad de individuos. Ejemplo: Algunos musulmanes son talibanes.
- Sintaxis de la lógica de predicados
Los símbolos que introduce la lógica de predicados son:
- Variables individuales: que representan individuos indeterminados. Se emplean las últimas letras minúsculas del alfabeto: x, y, z.
- - Constantes individuales: representan individuos determinados. Se utilizan las primeras letras del alfabeto.
- - Variables predicativas: representan predicados indeterminados. Se usan las letras mayúsculas, F, G, H…..
- Cuantificadores: hacen referencia a la totalidad o a una parte de los miembros de un conjunto. Pudiendo ser la generalización universal o particular, los cuantificadores son de dos tipos: Cuantificador Universal y Cuantificador Existencial.
Esquema de Estudio:
A continuación se detallan los temas que se deben llevar a cabo, una descripción general del mismo, y un conjunto de actividades que se recomienda sean desarrolladas para una mejor asimilación y comprensión de los conceptos. Se han dispuesto las tres columnas de la derecha para llevar un control personal del tiempo de dedicación a cada tema, marcar las actividades que estima que necesita tutoría y realizar anotaciones.
| Tema a revisar | Descripción del Contenido a revisar | Actividades Recomendadas | Planificación Personal del estudio (fecha) | ¿Requiero Tutorial? | Anotaciones |
|---|---|---|---|---|---|
| 15.2 El lenguaje y su sintaxis | Enfocarse en los aspectos de Componentes, Términos, y las formulas bien formadas. | Revisar el material que se mostrara en el EVA y resolver las actividades del mismo. | |||
| 15.5 Semántica de los cuantificadores | Uso de los cuantificadores en la IA | Revisar el material que se mostrara en el EVA y resolver las actividades del mismo. |
Capitulo 7: SISTEMAS BASADOS EN CONOCIMIENTO Y SISTEMAS EXPERTOS
Datos Generales:
| Texto Base | Nils J. Nilsson. Inteligencia Artificial: Una nueva Síntesis. McGRAW-HILL. Madrid, España. 2001 |
| Capítulo | 17. Sistemas Basados en Conocimiento |
| Páginas | 241- 255 |
| Horas de estudio empleadas para el desarrollo del contenido | 10 horas |
Propositos:
Los sistemas expertos resuelven problemas que normalmente son solucionados por “expertos” humanos. Para resolver problemas a nivel experto, los sistemas expertos necesitan acceder a una importante base de conocimiento sobre el dominio, la cual debe construirse los mas eficiente posible.
Conceptos Claves:
- Características básicas en los sistemas expertos
- Estos sistemas derivan su potencia del fuerte compromiso en conocimiento específico del dominio en lugar de una sola técnica poderosa.
- En los sistemas que han tenido éxito, el conocimiento requerido se refiere a un área particular y está bien definido. Esto contrasta con el tipo de conocimiento que llamamos sentido común.
- Un sistema experto se construye normalmente con la ayuda de uno o más expertos, que deben estar dispuestos a invertir un gran esfuerzo en la transferencia de sus habilidades al sistema.
- - La cantidad de conocimiento que se requiere depende de la tarea. Puede oscilar desde cuarenta reglas hasta miles de ellas.
- Problemas a los que se enfrentan los sistemas expertosç
- Fragilidad: Dado que los SE solamente tienen acceso a un conocimiento altamente especifico del dominio, no pueden retroceder a un conocimiento más general cuando lo necesiten.
- Ausencia de meta-conocimiento: Los SE no tienen un conocimiento profundo acerca de su propia gestión. Normalmente no pueden razonar sobre su campo de acción y limitaciones, haciéndolo más difícil frente a su fragilidad.
- Adquisición de conocimiento: La adquisición aún ignora el cuello de botella que supone aplicar la tecnología de los sistemas expertos a nuevos dominios.
- Validación: La medición de los resultados de un sistema experto es difícil porque no se sabe cómo cuantificar el uso del conocimiento.
Esquema de Estudio:
A continuación se detallan los temas que se deben llevar a cabo, una descripción general del mismo, y un conjunto de actividades que se recomienda sean desarrolladas para una mejor asimilación y comprensión de los conceptos. Se han dispuesto las tres columnas de la derecha para llevar un control personal del tiempo de dedicación a cada tema, marcar las actividades que estima que necesita tutoría y realizar anotaciones.
| Tema a revisar | Descripción del Contenido a revisar | Actividades Recomendadas | Planificación Personal del estudio (fecha) | ¿Requiero Tutorial? | Anotaciones |
|---|---|---|---|---|---|
| 17.1 El enfrentamiento con el mundo | Proporciona una visión general a los Sistemas Basados en el conocimiento | Revisar material en el EVA | |||
| 17.4 Sistemas Expertos basados en reglas | Se trata definiciones de Sistemas Expertos, algunas aplicaciones, la estructura para construir un Sistema Experto. | Revisar material en el EVA |
ANEXOS
ANEXO 1: BUSQUEDA MINIMAX Y ALGORITMO A*
Introducción
Los juegos provocan una inexplicable fascinación y, la idea de que los computadores puedan jugar existe desde que existen las computadoras:
- Siglo XIX, Babbage, arquitecto de computadoras, pensó en programar su máquina analítica para que jugara al ajedrez.
- ‘50, Shannon describió los mecanismos que podían usarse en un programa jugara al ajedrez
- ‘50, Turing describió un programa para jugar al ajedrez pero no lo construyó
-
‘60, Samuel construyó el primer programa de juegos importante y operativo, el cual jugaba a las damas y podía aprender de sus errores para mejorar su comportamiento
Los juegos proporcionan una tarea estructurada en la que es muy fácil medir el éxito o el fracaso. En comparación con otras aplicaciones de inteligencia artificial, por ejemplo comprensión del lenguaje, los juegos no necesitan grandes cantidades de conocimiento.
En un primer momento se pensó que se podrían resolver por búsqueda exhaustiva en el árbol del juego, es decir, un árbol que contenga todos los movimientos posibles de ambos jugadores. Considerando por ejemplo el juego de ajedrez, en una partida cada jugador realiza una media de 50 movimientos, con un factor de ramificación medio de 35 posibilidades, por lo tanto para examinar el árbol de juego completamente se tendrían que examinar 35100 posibilidades. Resulta evidente que una simple búsqueda directa no es posible de realizar en la práctica, y por lo tanto es necesario algún tipo de procedimiento de búsqueda heurística. Todos los procedimientos de búsqueda pueden verse como procedimientos de generación y prueba, en donde la comprobación se realiza después de distintas cantidades de trabajo del generador. En un extremo el generador proporciona una solución completa a evaluar por el comprobador; en el otro extremo, el generador genera movimientos individuales cada uno de los cuales se evalúa por el comprobador
Para mejorar la efectividad de un programa resolutor de problemas, en particular de juegos, es importante:
- Mejorar el procedimiento de generación de manera de que se generen sólo movimientos buenos.
- Mejorar el procedimiento de prueba para que sólo se reconozcan los mejores movimientos.
-
Dado que estos dos procedimientos no son perfectos, se incorpora la búsqueda o exploración de distintos niveles del juego para ver que puede ocurrir una serie de movimientos más adelante. Resulta evidente que la elección del camino a seguir será más acertada cuántas más capas se exploren antes de tomar la decisión. Se utiliza una función de evaluación estática (heurística) para elegir el movimiento más prometedor.
Por ejemplo,
- Turing usó la sencilla función B/N (piezas blancas / piezas negras) para evaluar una posición dada de un tablero de ajedrez.
-
Shanon utilizó una función lineal de funciones de evaluación simples para evaluar un tablero de damas:
c1 * ventaja piezas + c2 * avance + c3 * amenazas dobles + ...
En la función anterior, con un mecanismo de aprendizaje, los pesos o ponderaciones ci se incrementan o disminuyen siempre que sus componentes sugieran movimientos que conducen a la victoria o al fracaso respectivamente. Este es un problema denominado de asignación de crédito, es decir, decidir de entre una serie de acciones cuál es la responsable del resultado. En juegos y otros dominios la solución se encuentra mediante un proceso de búsqueda que debe combinarse de ser posible con una técnica directa. Por ej. en el ajedrez, las aperturas y los finales están ya estudiados y se almacenan en una base de datos.
Juegos sin adversario: algoritmo A*
Para juegos simples unipersonales (por ej. 8-puzzle) puede usarse el algoritmo A* (Hart, 1968) que se describe en esta sección. Este algoritmo implementa una búsqueda primero el mejor.
Se utiliza una función de evaluación estática f formada por:
La función g es una función de coste de llegar del estado inicial al estado evaluado.
La función h es una estimación del coste de llegar desde el estado evaluado al estado final u objetivo del juego.
En cada paso del algoritmo se selecciona el mejor nodo que no se ha expandido hasta el momento, es decir, aquel que tiene menor valor de función f. Este nodo se agrega a una lista de nodos explorados (NodosExplorados) y sus nodos sucesores se agregan a la lista de nodos pendientes de ser explorados (NodosNoExplorados).
Juegos con adversario: algoritmo Minimax
Búsqueda Minimax
En juegos bipersonales el algoritmo más usado es el denominado Minimax. El procedimiento de búsqueda Minimax es una búsqueda en profundidad (DFS) de profundidad limitada.
La idea consiste en comenzar en la posición actual y usar el generador de movimientos plausibles para generar las posibles posiciones sucesivas hasta un cierto límite de niveles. A continuación se aplica la función de evaluación estática a las posiciones obtenidas y se elige la mejor posición para el jugador correspondiente, llevando los valores un nivel hacia atrás para continuar la evaluación en todos los niveles anteriores. Se supone una función de evaluación estática que devuelve valores elevados para indicar buenas situaciones y valores negativos para indicar buenas situaciones para el oponente. Visto de esta manera, la meta es maximizar el valor de la función estática de la siguiente posición de tablero. El nombre del algoritmo deriva de considerar que, dada una función estática que devuelve valores en relación al jugador maximizante, éste procura maximizar su valor mientras que su oponente procura minimizarlo. En un árbol de juego donde los valores de la función estática están en relación al jugador maximizante, se maximiza y minimiza alternadamente de un nivel a otro. La figura 1 muestra un ejemplo donde la elección del siguiente movimiento según la búsqueda Minimax de tres niveles sería el nodo D.
El algoritmo Minimax es un procedimiento recursivo, y el corte de la recursión está dado por alguna de las siguientes condiciones:
- • Gana algún jugador
- • Se han explorado N capas, siendo N el límite establecido
- • Se ha agotado el tiempo de exploración
- • Se ha llegado a una situación estática donde no hay grandes cambios de un nivel a otro
En el algoritmo MINIMAX detallado en breve la función de corte de recursión SUFICIENTE (posición, profundidad) sólo considera las dos primeras condiciones de corte.
El algoritmo MINIMAX( posición, profundidad, jugador) usa dos funciones:
- GENMOV (posición, jugador): devuelve la lista de movimientos posibles para el jugador a partir de la posición
- ESTÁTICA (posición, jugador): devuelve un número que representa la bondad de la posición desde el punto de vista de jugador.
A diferencia de los valores mostrados en el ejemplo de la figura 1, la función ESTÁTICA devuelve valores en relación al jugador actual en vez del jugador maximizante. Por esta razón, en lugar de realizar maximización y minimización alternativas, siempre se maximiza el valor que devuelve esta función. El algoritmo MINIMAX no necesita tratar diferente a los niveles maximizante y minimizante dado que invierte los valores de un nivel a otro.
La función Minimax devuelve una estructura con
- VALOR: valor propagado de la función estática
- CAMINO: camino para llegar a la solución desde la posición
La primera llamada a la función recursiva será:
MINIMAX (posición actual, 0, JUGADOR-UNO)
El algoritmo MINIMAX es el siguiente:
MINIMAX( posición, profundidad, jugador)
comienzo
Si SUFICIENTE (posición, profundidad) entonces
- resultado.VALOR := ESTATICA (posición, jugador);
- resultado.CAMINO := NULO;
- return resultado;
sino
- Sucesores := GENMOV (posición, jugador);
Si EstaVacia (Sucesores) entonces
- resultado.VALOR := ESTATICA (posición, jugador);
- resultado.CAMINO := NULO;
- return resultado;
sino
- resultadoMejor.VALOR := MININT;
- por cada sucesor de Sucesores
- resultadoSucesor := MINIMAX (sucesor, profundidad+1,CONTRARIO (jugador));
- Si resultadoMejor.VALOR < - resultadoSucesor.VALOR entonces
- resultadoMejor.VALOR := - resultadoSucesor.VALOR;
- resultadoMejor.CAMINO := sucesor + resultadoSucesor.CAMINO;
- fin si;
- fin por;
- return resultadoMejor;
- fin sino;
fin sino;
fin MINIMAX;
Poda alfa-beta de la búsqueda Minimax
Los procedimientos de búsqueda en profundidad (DFS) pueden mejorar su eficiencia usando una técnica de branch and bound (ramificación y acotación), con la cual una solución parcial se abandona cuando se comprueba que es peor que otra solución conocida o umbral.
La estrategia de poda del algoritmo Minimax es llamada poda alfa-beta, puesto que dado que existen dos jugadores maximizador y minimizador, existen dos valores umbral alfa y beta para acotar la búsqueda de cada uno respectivamente.
- El valor alfa representa la cota inferior del valor que puede asignarse en último término a un nodo maximizante.
- El valor beta representa la cota superior del valor que puede asignarse en último término a un nodo minimizante.
La figura 2 muestra la aplicación de la poda alfa-beta al ejemplo de la figura 1. La evaluación del nodo E asegura al oponente (jugador minimizante) una cota superior con valor 7, es decir, el oponente obtendrá 7 o un valor menor en la evaluación de B (dado que los valores están en relación al jugador maximizante, los valores menores a 7 son mejores para el oponente). En este caso, 7 representa el valor beta. A continuación, cuando se examina el nodo N cuyo valor es 8, dado que es mayor que beta (7), los nodos hermanos de N (en este caso el nodo O) pueden podarse (dado que nos hallamos en un nivel maximizante, el nodo F tendrá un valor igual o superior a 8, y por lo tanto no podrá competir con la cota asegurada beta en el nivel minimizante anterior). Luego de evaluar los sucesores de B, se concluye que este nodo asegura al jugador maximizante una cota inferior con valor 3, es decir, obtendrá 3 o un valor mayor en la evaluación de A. En este caso, 3 representa el valor de alfa. A continuación, cuando se examina el nodo H cuyo valor es 0, dado que es menor que alfa (3), los nodos hermanos de H (en este caso el nodo I) pueden podarse (dado que nos hallamos en un nivel minimizante, el nodo C tendrá un valor menor o igual a 0, y por lo tanto no podrá competir con la cota asegurada alfa en el nivel maximizante anterior).
En un nivel dado, el valor de umbral alfa o beta según corresponda, debe actualizarse cuando se encuentra un umbral mejor. En el ejemplo anterior, al obtenerse el valor 8 del nodo D se puede actualizar el valor de alfa (3) a alfa (8). Esto tendría sentido en el caso de que existieran otros nodos hermanos de D que pudieran ser podados utilizando este valor de alfa. Análogamente, al obtenerse un valor de 3 en el nodo G se puede actualizar el valor de beta (7) a beta (3). Esto tendría sentido en el caso de que existieran otros nodos hermanos G que pudieran ser podados utilizando este valor de beta. El algoritmo MINIMAX_ALFABETA evita esta diferenciación utilizando dos valores de umbral, uno que usa efectivamente como umbral (umbralUSO) y otro que debe pasar al nivel siguiente para ser usado (umbralPASO). En un nivel dado, uno de los valores es usado para realizar posibles podas de nodos hijos (umbralUSO), y mientras tanto se va actualizando el valor de umbral del nivel anterior (umbralPASO).
