Download Inteligencia Artificial - Página en Construcción
Document related concepts
Transcript
Resumen de Inteligencia Artificial Inteligencia Artificial Definiciones Varias – Dominio: Se define como el contexto del problema que se busca resolver. – Experto: Es una persona que puede resolver problemas de una forma correcta y rápida empleando técnicas de razonamiento. Posee la capacidad de aprender adquiriendo conocimientos y experiencia. La Inteligencia Artificial La Inteligencia es la capacidad de resolver problemas no comunes o complejos en un dominio determinado de forma sistemática. Tener Inteligencia es poseer la capacidad de aprendizaje o capacidad adaptativa. La Inteligencia Artificial estudia el comportamiento inteligente del ser humano; y puede observarse desde dos puntos de vista: Científico: Trata el estudio del comportamiento inteligente, siendo su fin el conseguir una teoría de la inteligencia que explique la conducta que se produce en seres naturales inteligentes que guíe la creación de entes artificiales capaces de alcanzar dicho proceder inteligente. En síntesis, busca comprender y analizar la inteligencia humana para emularla. Ingeniería: Se ocupa de los conceptos, la teoría, y la práctica de cómo construir máquinas inteligentes; es decir, máquinas que resuelvan problemas coextensivos con los que, al resolverlos los seres humanos, estos son tenidos por inteligentes. Clasificación de los Sistemas Los Sistemas se Clasifican según se muestra a continuación: Sistemas: Conjunto de partes interrelacionadas que interactúan entre si con el fin de satisfacer un objetivo común. o Sistemas de Información: Sistema que permite recolectar, almacenar, procesar y distribuir datos. Sistemas Inteligentes: Son todos aquellos Sistemas que emplean determinadas heurísticas para poder resolver problemas. Sistemas Basados en Conocimientos: Programa de Inteligencia Artificial, cuyas prestaciones dependen más de la presencia explícita de un cuerpo de conocimientos que de la posesión de ingeniosos procedimientos computacionales. Pertenecen a los Sistemas Inteligentes. Son sistemas que incluyen los Datos, las Noticias y los Conocimientos. Sus reglas se encuentran separadas de los procedimientos. Su Base de Conocimientos es pública y accesible. Es multidominio y reutilizable. Tiene una base de conocimientos explícita que puedo identificar, y posee un comportamiento inteligente. Es como una BD pero en vez de datos hay hechos y reglas. o Sistemas Expertos: Pertenecen al grupo de los Sistemas Basados en Conocimientos. Sus reglas provienen de distintas fuentes y de las decisiones que toma un experto. Su Base de Conocimientos no es pública y está conformada por reglas específicas de un dominio que no pueden ser modificadas por el usuario final. Sistemas Expertos: Puede no tener una base de conocimiento explícita. Son más particulares que los sistemas basados en conocimiento porque se basan en una persona llamada “Experto”. El Sistema experto no reemplaza al experto sino que lo asiste. Página 1 de 42 Resumen de Inteligencia Artificial Construcción de Sistemas Basados en Conocimientos Problemas en la Construcción de Sistemas Basados en Conocimientos Los Problemas que se dan en la construcción de Sistemas Basados en Conocimientos son: La adquisición de los conocimientos. La representación de los conocimientos. La generación de inferencias. Principios Para Construir Sistemas Basados en Conocimientos Los principios arquitectónicos que se deben seguir para construir Sistemas Basados en Conocimientos son los siguientes: Separación del mecanismo de inferencia de la Base de Conocimientos. Uniformidad en la representación. Conservar simple el motor de inferencias. Página 2 de 42 Resumen de Inteligencia Artificial Sistemas Basados en Conocimientos (SBC) Componentes de un Sistema Basado en Conocimiento Los componentes de un Sistema Basado en Conocimientos son los siguientes: 1. Base de Conocimientos (BC): Posee las reglas que guían la resolución de problemas. Es pública y accesible. Sus reglas son de la forma: SI [CONDICIÓN] [ACCIÓN]. 2. Motor de Inferencia (MI): Es quien consulta la BC para obtener las reglas con el fin de satisfacer una consulta del usuario. Se encarga de la realimentación. 3. Interfaz de Entrada/Salida (IES): Transforma las peticiones del usuario para que las entienda el MI; y viceversa, transforma los resultados que le provee el MI para que los pueda interpretar el usuario. BC MI IES SBC USUARIO Mundo Real Sistemas Expertos (SE) Componentes de un Sistema Experto Los componentes de un Sistema Experto son los siguientes: 1. Base de Conocimientos (BC): Es la unión del conjunto de acciones y el conjunto de reglas. Contiene el conocimiento público y privado que el sistema requiere para dar solución a los problemas planteados por el usuario sobre un dominio específico. Sus reglas son de un dominio específico y no pueden ser modificadas por el usuario final. 2. Base de Datos (BD): Está formada por los distintos datos sobre el problema particular que el Sistema Experto está tratando de resolver. Su función es suministrar información al MI. Posee los datos iniciales. Mientras la BC posee reglas, la BD posee datos. 3. Memoria de Trabajo (MT): Es una base de datos temporal en la cual el MI deposita la información deducida a partir de la BC, la BD y la propia MT. 4. Motor de Inferencia (MI): Activa las reglas en función de la información contenida en la BD y en la MT. La nueva información es puesta en la MT. También se encarga de proporcionar al TE las reglas que se aplicaron ante una determinada consulta del usuario. El MI trabaja bajo uno de los dos principios siguientes: a. Principio de Universo Cerrado: Establece que toda la información se encuentra contenida en el sistema, y en consecuencia lo que no se puede demostrar como verdadero se demuestra como falso. b. Principio de Universo Abierto: Establece que la información necesaria no está contenida en el sistema, está fuera de él, y en consecuencia se comunica con el usuario. Un sistema con un Universo Abierto puede comenzar a funcionar con a una BD vacía. 5. Trazador de Consultas (TC): Organiza y presenta en una forma sintáctica y semánticamente aceptable para el usuario los requerimientos de información del sistema. Las respuestas suministradas por el usuario serán asentadas en la MT. Formula las preguntas al usuario sobre los datos necesarios para resolver el problema. 6. Trazador de Explicaciones (TE): Interpreta requerimientos del usuario sobre el porqué de determinadas preguntas por parte del sistema trazando la ejecución de las mismas. Esa traza se realiza utilizando información que le suministra el MI. 7. Manejador de Comunicaciones (MC): Posee dos funciones bien definidas: Página 3 de 42 Resumen de Inteligencia Artificial a. Derivar la información inicial que suministra el usuario hacia la BD. b. Interpretar los mensajes del usuario que pueden ser respuestas del usuario a una pregunta del sistema; o una solicitud de una explicación a partir de una consulta del sistema. Los sistemas expertos, deben expresar sus conclusiones al usuario. M A N E J A D O R U S U A R I O D E Mundo Real C O M U N I C A C I O N E S TE BD MI BC MT TC SE Tipos de Sistemas Expertos Los tipos de Sistemas Expertos que hay son: Consejo al Usuario. Instrucción. Control. Ayudante Inteligente. Asimilación de Información y Descubrimiento. Ingeniería en Software vs INCO La diferencia entre la Ingeniería en Software y la INCO es que la Ing. en Software se aplica a tipos de problemas sistemáticos y procedimentales, y la INCO se caracteriza por ser heurísticos y declarativos. Página 4 de 42 Resumen de Inteligencia Artificial Los Conocimientos Pirámide de la Información A continuación se presenta la clasificación de la Información y su ubicación jerárquica Sabiduría Nivel Pragmático Nivel Semántico Nivel Sintáctico Juicios Éticos, Experiencia Conocimiento Síntesis Noticias (Información) Análisis Datos Nota: El nivel Pragmático es el mayor nivel que puede manipular un SE. En donde podemos encontrar los siguientes conceptos: Datos: Son los valores o métricas que pueden llegar a brindar información a algún individuo en un contexto determinado. Noticias: Suele conocerse con el nombre de Información. Son aquellos Datos que poseen un significado específico en un determinado contexto para un determinado individuo. Conocimiento: Es el conjunto de Noticias que posibilitan resolver problemas. Sabiduría: Permite aplicar los Conocimientos según un juicio de valor (moral, ético, correcto). Relación entre la Pirámide de la Información y las Ingenierías Sabiduría Conocimiento Noticias (Información) Ingeniería de Software Ingeniería en Conocimiento Ingeniería en Sistemas de Información Datos Los Conocimientos El Conocimiento es poder percibir conclusiones a partir de determinada información. Es relativo a la persona que lo percibe. Tipos de Conocimiento Los conocimientos se clasifican según la Operatividad, la Privacidad y según la Definición del Problema: Según la Operatividad: o Descriptivos o Declarativos: Se refieren básicamente a qué son las cosas, y describen el dominio de aplicación, habitualmente en términos de conceptos, objetos, atributos, valores y relaciones entre las entidades anteriores, sin que importe cómo se usen esos conocimientos. Derivados: Son los que se aprenden y aprehenden bien a través de la experiencia, o bien se compilan a partir de conocimientos más fundamentales. Los principios básicos suelen estar implícitos. Página 5 de 42 Resumen de Inteligencia Artificial Compilados: Son los transformados a partir de otros tipos de conocimientos. Heurísticos: Son los que establecen asociaciones entre descripciones de estado y una solución. Abstracciones: Son los que contienen, para una situación, todos los detalles relevantes y suprime los irrelevantes. Generalizaciones: Son aquellos que yendo de lo particular a lo general, son el paso de la consideración de un concepto a la consideración de un conjunto conteniendo ese concepto. Modelizados: Son una descripción de los conocimientos fundamentales ya refinados. Aparecen en los soportes de los conocimientos públicos y constituyen los conocimientos de primeros principios. Fórmulas Lógico-Matemáticas. Leyes Naturales. Modelos Causales y Temporales. Modelos Físicos. o Prescriptitos o Procedimentales: Conciernen fundamentalmente al cómo son las cosas. Sirven para controlar el proceso de solución de un problema, centrándose en el uso de los conocimientos y esquema de razonamiento usado para alcanzar una solución. Secuencial e Iterativo: Representan las acciones que se ejecutan un número de veces (Iteración), o acciones que se ejecutan en un cierto orden (Secuencia). Metaconocimientos o Condiciones de Metanivel: Describen los conocimientos usados para tomar decisiones acerca de cómo otros conocimientos pueden emplearse en el proceso de razonamiento. Verosimilitud: Cubren el uso de medidas de certidumbre en el proceso de razonamiento. Según la Privacidad: o Públicos: Son aquellos que, por haber sido publicados, están ya en forma explícita, por consiguiente, representables y utilizables inmediata o mediatamente en y por la computadora. o Privados: Son los conocimientos que los expertos tienen interiorizados y adquieren con el ejercicio de su profesión, y lo usan implícitamente. Según la Definición del Problema: o Estructurantes: Generalmente vienen expresados de manera declarativa y tradicionalmente se han identificado con los conocimientos públicos. Detectan los conceptos relevantes estableciendo relaciones entre los conceptos y las estructuras conceptuales. Definen los mecanismos que dan origen a la certeza. o Heurísticos: Pueden expresarse en formas de reglas que típicamente son atajos que conducen a la solución en grandes espacios de búsqueda en un tiempo limitado. o Epistemológicos: Son los conocimientos naturales. Poseen la característica de que son inciertos, por: incompletos, inconsistentes y/o imprecisos. o Cognoscitivos o de Modelización Conceptual: Modelizan el dominio en el cual se manejan los expertos. Fuentes de Conocimientos Las principales fuentes de conocimientos que podemos encontrar son: Libros y Manuales. Documentación Formal. Documentación Informal. Registros Internos. Presentaciones. Publicaciones Especializadas. Investigaciones. Visitas a los Centros de Trabajo del Experto. Los Humanos. La Experiencia La experiencia es pasar por un mismo hecho varias veces. Permite generar conocimiento. Cada persona interpreta los hechos de forma distinta, por lo cual cada uno aplicará y creará sus propias reglas. Página 6 de 42 Resumen de Inteligencia Artificial Dificultades de la Experiencia La transferencia de conocimiento de un experto a un sistema está condicionada y dificultada porque: Los conocimientos del experto son caros. Habitualmente, los conocimientos de los expertos no se encuentran explícitos. Los conocimientos de los expertos se adquieren gradualmente. Los conocimientos de los expertos suelen estar distribuidos. Los conocimientos de los expertos son declarativos. Un experto aplica efectiva y eficientemente lo que sabe. Experiencia Artificial Frente a Experiencia Natural Ventajas y desventajas de usar tanto la Experiencia Artificial como la Experiencia Natural. Razones para preferir la Experiencia Artificial: o La Experiencia Artificial permanece. o La Experiencia Artificial es fácil de transferir o reproducir. o La Experiencia Artificial genera resultados reproducibles más consistentes y completos que aquellos de los expertos humanos. o La Experiencia Artificial es fácil de documentar. o La Experiencia Artificial tiene un coste relativamente reducido. o La Experiencia Artificial se encuentra difundida. Razones para preferir la Experiencia Natural: o Los expertos humanos son creativos. o Los expertos humanos son capaces de aprender y adaptarse a condiciones cambiantes ajustando sus estrategias de acuerdo a las nuevas situaciones. o Los expertos humanos pueden beneficiarse y usar directamente los órganos de los sentidos. o Los expertos humanos examinan todos los aspectos de un problema y ven de qué manera están relacionados con la cuestión principal. o Los expertos humanos, y en general los seres humanos, posee lo que se denomina sentido común. Por Qué Introducir Experiencia Artificial Existen diversas razones para las cuales una entidad puede decidirse a construir un Sistema Basado en Conocimientos o un Sistema Experto, entre ellas: Satisfacción del cliente. Utilización adecuada de los empleados. Uniformidad de la producción. Incremento de ingresos y reducción de gastos. El Experto Tareas del Experto Las tareas que cumple un Experto son: Clasificación. o Clasificación Jerarquizada. o Interpretación. o Diagnosis. El diagnóstico es el procedo de encontrar fallas en un sistema e interpretarlos. Puede necesitar la combinación de varios modelos. o Depuración, Tratamiento o Reparación. Predicción, Pronóstico y Prospección. Diseño y Síntesis. Planificación y Catalogación. Monitorización. Características de un Experto Las características de un Experto son: Pericia. Página 7 de 42 Resumen de Inteligencia Artificial o Robustez: Es muy difícil de cuantificar, ya que los sistemas de este tipo se degradan rápidamente cuando tienen que tratar con problemas distintos para los cuales fueron creados. Manipulación de Símbolos. Capacidad general de resolver problemas en un dominio. Complejidad y Dificultad. Reformulación o Reutilización. Capacidad para razonar sobre sí mismos. Tareas. Metodología de Construcción de Sistemas Basados en Conocimientos Definiciones Varias – Metodología: Conjunto de etapas que se dan en un orden determinado, y que si se producen de manera exitosa permite cumplir con determinados objetivos. – Ingeniería: Conjunto de Métodos, que emplean técnicas y herramientas, para generar un artefacto o producto, que usado en buena forma, o de manera correcta, permite resolver un problema. Metodología de Sistemas La Metodología de Sistemas surge a partir de los pasos básicos para resolver un problema en el ámbito de los Sistemas de Información. El Ingeniero de Sistemas resuelve problemas empleando una metodología y construyendo artefactos. INCO (Ingeniería en Conocimiento) La INCO es una forma de aplicar IA Es el conjunto de principios, métodos y herramientas que permiten aplicar el saber científico y de experiencia a la utilización de los conocimientos y de sus fuentes, mediante invenciones o construcciones útiles para el hombre. La INCO abarca tanto la creación de Sistemas Basados en Conocimientos como la creación de Sistemas Expertos. Permite automatizar cómo se resuelve un problema. Se basa en las decisiones tomadas por un Experto; a partir de las cuales se genera un Sistema Inteligente. Busca construir algo que resuelva un problema. Desde el punto de vista de la Ingeniería el problema se resuelve creando un objeto, empleando una metodología y usando el ingenio. El Ingeniero en Conocimiento emplea métodos, técnicas, herramientas y principios básicos para construir un modelo de los procesos lógicos producto del análisis de la información. Pasos Previos Estudio de Viabilidad o Estudio de Factibilidad El Estudio de Factibilidad permite determinar si se va a desarrollar el Sistema mediante la INCO o mediante el sistema tradicional. Tiene en cuenta aquellas condiciones bajo las cuales conviene construir un Sistema Experto o no. Las características que se analizan para realizar el Estudio de Factibilidad son: 1. (Plausibilidad): ¿Es posible?. Se deberá analizar si existen Expertos, si son cooperativos, si la tarea necesita viabilidad cognoscitiva, si la tarea es estructurada, si no se aplica el sentido común y si es comprensible. 2. ¿Es adecuada?: Se deberá analizar la naturaleza, la complejidad y el tipo de tarea. 3. ¿Se Justifica?: Se deberá analizar si la tarea se desarrolla en un entorno hostil, si hay escasos expertos, si no existen alternativas y si es útil y necesario. 4. ¿Cuál es la probabilidad de llegar al éxito?: Se deberá analizar si el Experto se va a resistir al cambio, si hay fechas límites para que el Sistema se encuentre funcionando y si se tiene forma de comprobar la solución. Página 8 de 42 Resumen de Inteligencia Artificial Identificación del Problema Una vez que se aprueba esta etapa previa se pasa a la primera etapa de la metodología de la INCO. A esta etapa se la subdivide en las siguientes subetapas: 1. Plan de Requisitos: Se define el objetivo y las características de la aplicación. 2. Elección del Problema: Se definen los límites del problema. 3. Definición de Características del Problemas y Concepción de la Solución. Metodología de la INCO 1. 2. 3. 4. Adquisición de Conocimientos: Recolección de Información y conocimientos. Conceptualización: Entender el dominio y la terminología Formalización: Expresa mediante técnicas el conocimiento al problema Implementación 1. Ad qui s ic ión d e Co noc im ie nt o s Es un proceso de recolección de información (independientemente de la fuente) necesaria para construir el sistema experto. No es una etapa, sino un proceso que se va a dar a lo largo del ciclo de vida. Uno de los objetivos fundamentales es adquirir toda la información posible para construir en las etapas posteriores los modelos estáticos y dinámicos, de cuya unión surge la conducta del Experto en la solución encontrada. Luego de ejecutar el ciclo de educción es necesario analizar los conocimientos obtenidos y generar la documentación necesaria para pasar luego a la fase de Conceptualización. Adquisición de Conocimientos La Adquisición de Conocimientos comprende los siguientes tipos: Extracción de Conocimientos: Es la adquisición de los conocimientos públicos de sus fuentes escritas (libros, documentos, manuales, etc.). Educción de Conocimientos: Es la adquisición de los conocimientos privados de los Expertos. Proceso de Adquisición de Conocimientos El proceso de adquisición de conocimientos es el siguiente: Primeras Reuniones y Evaluación de Vialidad: (De Expertos, Directivos y Usuarios). Se buscan conocimientos generales, terminologías del dominio. Se emplea una baja profundidad. Se pueden usar las Entrevistas Abiertas Extracción de Conocimientos: Es el estudio de la documentación existente. Se emplean las técnicas de Estudio de Documentación y Análisis Estructural de Textos. Educción de Conocimientos: Se obtienen los conocimientos privados de los expertos. Comprende las siguientes etapas: o Interrogatorio Inicial: Se tratará una visión de alto nivel del dominio, la comprensión de las tareas del Experto, la comprensión del entorno de las tareas. Puede emplearse la técnica de Observación de Tareas Habituales. o Investigación Profunda: Se baja a mayor profundidad para obtener los conocimientos. Cuando se trata de conocimientos estáticos del dominio, se emplean las técnicas de Entrevista Estructurada, Incidentes Críticos, Clasificación de Conceptos, Emparrillado y Cuestionarios. Cuando se tratan de buscar las estrategias de resolución del Experto se emplea la técnica de Análisis de Protocolos. Cuando el objetivo sea validar los conocimientos adquiridos se emplean las técnicas de Cuestionarios y Entrevistas Estructuradas. Ciclo de Educción El ciclo de Educción es el siguiente, el cual deberá repetirse por cada sesión: Preparación de la Sesión: Información a tratar; amplitud, profundidad; técnica adecuada; preparación de las preguntas. Sesión: Repaso del análisis de la última sesión; explicación al experto de los objetivos de la nueva sesión; Educción; resumen y comentarios del Experto. Transcripción. Página 9 de 42 Resumen de Inteligencia Artificial Análisis de la Sesión: Lectura para obtención de una visión general; extracción de conocimientos concretos; lectura para recuperar detalles olvidados; crítica parar mejoras por parte del Ingeniero en Conocimientos. Evaluación: ¿Se han conseguido los objetivos?; ¿es necesario volver sobre el mismo objetivo?; Número y tipo de sesiones necesarias para cubrir el área. Técnicas de Adquisición de Conocimientos Las Técnicas de Adquisición de Conocimientos se pueden clasificar según se muestra a continuación: Técnicas de Extracción de Conocimientos: Permiten obtener conocimientos públicos de fuentes escritas. o Estudio de Documentación: Se deberá analizar la documentación escrita existente que permita al Ingeniero en Conocimiento comprender el dominio, conocer las tareas que realiza el Experto, etc. o Análisis Estructural de Textos: Consiste en la búsqueda, a través de la documentación, de determinados términos que le permitan al Ingeniero en Conocimiento introducirse en el dominio del problema. Posee la ventaja de permite adquirir gran cantidad de conocimientos. Posee las desventajas de que se limita a los conocimientos publicados; posee problemas con los gráficos; y no siempre aborda bien la semántica de los textos. Técnicas de Educción de Conocimientos: Permiten obtener los conocimientos privados de los Expertos. o Directos: El Experto reporta aquellos conocimientos que puede articular directamente. Comprende las siguientes técnicas: Entrevistas: Es el método más común de educir conocimientos. Abiertas: Es una entrevista no estructurada, que no quiere decir que sea improvisada. Se trata de conseguir que el Experto entienda bien la tarea lo más rápidamente posible y al Sistema Experto en construcción. Sus ventajas son que permite generar gran cantidad de conocimientos sobre la terminología y sobre el dominio; y permite educir información imprevista. Estructuradas: Combina una Observación de Tareas Habituales con una Entrevista Abierta. Una vez definido el tema y su profundidad, el Ingeniero en Conocimientos planifica las preguntas de la sesión. Son excelentes para coleccionar conocimientos básicos acerca de: enlaces, valores, acciones, atributos e información conceptual; hechos, reglas, etc. Posee las desventajas de que consume mucho tiempo; se basa en la memoria del experto. Cuestionarios: Consiste en realizar una Entrevista Estructurada al Experto de forma indirecta, a través de cuestionarios. Posee las ventajas de acumular información más eficientemente; el Experto lo completa cuando puede. o Indirectos: El Ingeniero en Conocimientos debe inferir los conocimientos que el Experto trata de transmitir debido a que el Experto no sabe cómo hace para resolver los problemas. Comprende las siguientes técnicas: Observaciones de Tareas Habituales: El Ingeniero en Conocimientos no debe interferir con las tareas del Experto, sino sólo observarlo y registrarlo. Permite proporcionar una primera idea de los tipos de conocimientos y habilidades implicadas en el dominio, así como también para captar conocimientos procedimentales. Sus inconvenientes son que el Ingeniero en Conocimientos actúa como un observador pasivo; en algunos dominios no se puede implementar por razones de privacidad; hay tareas que no son muy informativas solo observándolas; es consumidora de tiempo. Observación de Tareas a Través de un Novato: La variación consiste en hacer que una persona novata realice las tareas del Experto, el cual lo guiará en la resolución de los problemas sin estar presente físicamente. Incidentes Críticos: Se le pide al Experto que describa casos especialmente interesantes o difíciles que se le hayan presentado y cómo los resolvió. Suele emplearse cuando la educción llega a un punto muerto Presenta las ventajas de que permite recolectar rápidamente información útil. Presenta las desventajas de que el Experto puede olvidar detalles de la solución. Imposición de Restricciones: Se le pide a un Experto que resuelva un problema normal, pero con ciertas restricciones. Permite determinar las prioridades del Experto. Presenta como desventaja que los Expertos se encuentran a disgusto con éste método. Página 10 de 42 Resumen de Inteligencia Artificial Clasificación de Conceptos: Se emplea para estructurar conceptos en dominios muy amplios. Consiste en presentarle fichas a los Expertos con conceptos para que éste los clasifique. Análisis de Protocolos: Es similar a la Observación de Tareas Habituales, salvo que el Experto deberá decir constantemente lo que piensa. Se busca capturar y después estudiar todo lo que dice el Experto en el momento en que trata un problema. Es útil cuando los casos han sido seleccionados previamente. Posee las ventajas de que provee gran cantidad de información; puede usarse de manera complementaria a otras técnicas; permite extraer heurísticas del Experto; va más allá de lo que el Experto puede contar explícitamente. Posee las desventajas de que no puede ser usado para todo tipo de tareas; el coste en tiempo de su utilización; la incompletitud del método; puede interferir en la forma de llegar a la solución. Análisis Retrospectivo: Consiste en que el Experto resuelva un problema y luego que indique los pasos que siguió para resolverlo. Emparrillado: Incluye un diálogo inicial con el Experto, una sesión de valoración y un análisis de los resultados, es decir, de los grupos, de los conceptos y de las dimensiones sobre las cuales fueron valorados los elementos. También puede usarse como medio de clasificación. Posee las ventajas de que permite obtener información acerca de cómo piensa el Experto y cuáles son sus prioridades y factores importantes; permite que una misma cuestión sea vista más de una vez; permite detectar patrones o asociaciones; es excelente en las primeras etapas de adquisición de conocimientos. Posee las desventajas de que es intrusivo; si los elementos, las características y/o las valoraciones no se eligen bien pueden provocar resultados erróneos. Inducción: Dado un conjunto de ejemplos específicos se inducen reglas que describen los ejemplos. Si las reglas son correctas serán lo suficientemente generales como para cumplirse no sólo en los ejemplos particulares, sino en lo general. Para usar la inducción se necesita de un Conjunto de Entrenamiento, Atributos, Clases y el Algoritmo de Inducción. Se suelen emplear las técnicas AQ y TDIDT. Posee la ventaja de que es que es muy buena para capturar conocimientos tácitos y heurísticos una vez identificado los atributos. Las desventajas que posee son que puede producir reglas incorrectas debido a malos ejemplos; si el dominio es complejo serán necesarios muchos ejemplos para producir las reglas; los ejemplos y atributos pueden ser difíciles de educir. Técnicas de Educción de Conocimientos a Partir de Grupos de Expertos: Permiten obtener los conocimientos privados de un grupo de Expertos. Los conocimientos obtenidos son más completos, más verosímiles, de mayor calidad y con una mayor diversidad. o Tormenta de Ideas: Técnica en donde las ideas que llegan a la mente se analizan y estudian en grupo. Permite desarrollar ideas y explorar su significado. Estimula el pensamiento. Posee la desventaja de que sólo es válida en tanto que se circunscriba a problemas de imaginación. o Técnica Nominal de Grupo: Es una forma de estructurar reuniones de pequeños grupos que permiten combinar efectivamente juicios individuales. Es útil en identificar problemas, explorar soluciones y establecer prioridades. o Entrevistas de Grupo: Son entrevistas realizadas a un grupo de personas. Favorece la participación, la seguridad, la libertad y la estimulación de los Expertos. Puede usarse en conjunción con la Entrevista Estructurada. Puede usarse para definir el alcance del problema, identificar soluciones alternativas, etc. o Emparrillado de Grupo. o Método Delphi: Es una técnica de predicción cualitativa. El procedimiento consiste en un proceso de retroalimentación de respuestas con el objetivo de obtener un resultado representativo de la opinión del grupo. 2 . Con c ept u a liz ac ión Se describe desde una necesidad del usuario para luego transformarse en un producto Software que opere en un dominio. El objetivo de esta fase es el entendimiento del dominio del problema y de la terminología utilizada. Le permite al Ingeniero en Conocimiento formar un marco inicial o mapa mental del Dominio de Aplicación. Se busca hacer explícitos los Conceptos claves y las Relaciones más importantes, ya que en la Adquisición de Conocimientos los obtenemos de manera desestructurada, para luego estructurarlos de forma apropiada. Página 11 de 42 Resumen de Inteligencia Artificial El Modelo Conceptual y el Modelo Formal Dominio de Aplicación Modelo Conceptual Modelo Formal El Modelo Conceptual modeliza cómo el Software debería responder ante una necesidad. Define los requerimientos del sistema (conocimientos descriptivos y no operativos) y además determina la validez del sistema. Es independiente de la tecnología de implementación. El Modelo Formal surge a partir del Modelo Conceptual y determina cómo el producto responde ante una necesidad. Subfases de la Conceptualización a. Análisis: Permite identificar los Conocimientos Estratégicos, Tácticos, Operativos, y los Metaconocimientos. Es un razonamiento Regresivo. b. Síntesis: En esta subfase se construyen tanto el Modelo Estático como el Modelo Dinámico. Es un razonamiento hacia adelante. i. El Modelo Dinámico contiene las tareas (acciones) y el control (estrategias de control). ii. El Modelo Estático contiene el Diccionario de Conceptos y las tablas de ConceptoAtributo-Valor. iii. El Mapa de Conocimientos toma información de los Modelos Estático y Dinámico. 3. Fo rm a liz ac ión La formalización se corresponde con el entorno de desarrollo y expresa mediante técnicas de representación de conocimiento al problema, a la resolución y a su estructura. Hay distintos tipos de formalismos: Formalismos Basados en Conceptos: Se encuentran divididos en las técnicas: o Tabla Concepto-Atributo-Valor. o Marcos. Formalismos Basados en Relaciones: Entre los cuales podemos encontrar: o Cálculo de Predicados en Primer Orden. o Las Redes Semánticas: Grafos. o La teoría de la Dependencia Conceptual: Patrones de estructuras sintácticas para armar relaciones de conceptos. Acciones: Los modelos tienden a representar las cosas que se van ejecutando: o Sistemas de Producción. o Guiones. 4. I mpl em ent a ci ón Consiste en la implementación del sistema. Especificación de Requisitos Los requisitos se pueden clasificar según se muestra a continuación: Respecto a las propiedades del sistema que especifican: o Funcionales: Definen el comportamiento esperado del sistema. En el Software hace referencia las capacidades funcionales que proveerá el producto. o Estructurales o No Funcionales: Son los que definen las restricciones que deberá satisfacer el producto. En el Software hace referencia a las características o propiedades que pueden evaluarse. Página 12 de 42 Resumen de Inteligencia Artificial Respecto a su importancia relativa: o Esenciales: Especifican todas las propiedades del sistema objetivo, que deben ser realizados por él mismo, para que sea aceptable. Nunca estarán completos. o Deseables y/o Derivados: Son los que especifican las características del sistema que se desprenden de las especificaciones esenciales. o Implícitos: Son los que suponen un subproducto de la práctica perspicaz de la Ingeniería de Software. Respecto al carácter de cada Requisito: o Cerrados: Son aquellos Requisitos que están bien definidos y son estables. o Abiertos: Son aquellos Requisitos que se entienden malamente y son dinámicos. Variables de un Proyecto Las variables que intervienen en un proyecto son: Costo: . Tiempo: . Calidad: . Tipos de Mantenimiento Los Tipos de Mantenimiento que pueden realizarse sobre un determinado producto son: Perfectivo: En el cual se corrige lo que anda bien con el fin de mejorarlo. Correctivo: En el cual se corrigen los errores que posee el producto. A diferencia de los Sistemas de Información, los Sistemas Basados en Conocimientos comienzan siendo productos malos con errores para ir mejorando a través del tiempo. Página 13 de 42 Resumen de Inteligencia Artificial Metodología IDEAL En la INCO se emplea la Metodología IDEAL como estándar. Posee tres dimensiones; en donde en la etapa del espiral, en el tercer eje, existe un cono que representa los conocimientos adquiridos. Al principio se adquieren una gran cantidad de conocimientos, pero poco precisos y fiables; al final se adquieren una menor cantidad de conocimientos, pero estos son más específicos y fiables. Las etapas se repiten sucesivamente evaluando los riesgos y una vez que se termina el espiral, se sigue linealmente con las etapas básicas. Cono Espiral Etapas Posteriores Mantenimiento Se debe tener en cuenta la etapa de Adquisición de Conocimientos, representada por el cono ya que es muy importante y necesaria. Fases y Etapas de la Metodología IDEAL La Metodología IDEAL posee las siguientes fases y etapas: 1- Identificación de la Tarea 2- Desarrollo de Prototipos 3- Ejecución de la Construcción del Sistema Integrado 4- Actuación para conseguir el Mantenimiento Perfectivo 5- Lograr una adecuada Transferencia Tecnológica 1. Identificación de la Tarea: Incluye la definición de los objetivos de la aplicación y, en base a ellos, determinar si la a realizar es susceptible de ser tratada con la tecnología de la INCO. Al completar la fase se logran definir las funcionalidades, el rendimiento y las interfaces que se espera que tenga el sistema. Se define el objetivo y el alcance para el SBC. Esta fase se divide en las siguientes etapas: c. Plan de Requisitos y Adquisición de Conocimientos: Comprende la identificación de las necesidades del cliente describiendo los objetivos del sistema. Es necesario que el Ingeniero en Conocimientos comience con una breve Adquisición de Conocimientos. d. Evaluación y Selección de la Tarea: Conforma el llamado Estudio de Viabilidad. Se lleva a cabo realizando una evaluación de la tarea y su posterior cuantificación con el fin de determinar el grado de complejidad de la tarea. e. Definición de las Características de la Tarea: Se configura la especificación del sistema, completando la especificación de conocimientos iniciales que se tienen del sistema. 2. Desarrollo de los Prototipos: Concierne al desarrollo de los distintos prototipos que permiten ir definiendo y refinando, más rigurosamente, las especificaciones del sistema, de una forma gradual hasta conseguir las especificaciones exactas de lo que se puede hacer y cómo realizarlos. Los Página 14 de 42 Resumen de Inteligencia Artificial prototipos que se suelen desarrollar son los de: Demostración, Investigación, Campo y Operación. Las etapas b a f se repiten para cada prototipo. Esta fase se divide en las siguientes etapas: f. Concepción de la Solución (Descomposición en Subproblemas y Determinación de Analogías): Esta etapa tiene como objetivo producir un diseño general del sistema prototipo. Engloba las actividades del desarrollo del DFD y el diseño arquitectónico. g. Adquisición y Conceptualización de los Conocimientos: Si bien la adquisición de conocimientos se realiza de forma constante, en ésta etapa es donde adquiere mayor importancia. Aparte de adquirir conocimientos, es también necesario conceptualizarlos para modelizar el comportamiento del experto. h. Formalización de los Conocimientos y Definición de la Arquitectura: Las actividades que posee son: seleccionar los formalismos para representar en la máquina los conocimientos conceptualizados, y realizar el diseño detallado del Sistema Experto. i. Selección de la Herramienta e implementación: Seleccionar la herramienta de desarrollo adecuada al problema para luego realizar implementación. j. Validación y Evaluación del Prototipo: En esta etapa se valida el funcionamiento del prototipo. Se suelen realizar Casos de Prueba y Ensayos en Paralelo con el Experto. k. Definición de Nuevos Requisitos: Se corresponde con la definición de los requisitos, especificaciones y diseño del siguiente prototipo. 3. Ejecución de la Construcción del Sistema Integrado: Permite integrar el Sistema Experto a otros sistemas computacionales. Esta fase se divide en las siguientes etapas: l. Requisitos y Diseño de la Integración: Consiste en el estudio y diseño de interfaces y puentes con otros Sistemas Hardware y Software. m. Implementación y Evaluación del Sistema Integrado: Su fin es desarrollar, usando técnicas de Ingeniería en Software, los requisitos de la etapa anterior. Implementa la integración del Sistema Experto con los otros Sistemas Hardware y Software. n. Aceptación del Sistema por el Cliente: Es la prueba última de aceptación por los expertos y usuarios finales, que debe satisfacer la expectativas de fiabilidad y eficiencia. 4. Actuación Para Conseguir el Mantenimiento Perfectivo: Trata del mantenimiento perfectivo del sistema. Este mantenimiento viene reflejado en el ciclo de vida en la tercera dimensión de la espiral cónica. Esta fase se divide en las siguientes etapas: o. Definir el Mantenimiento del Sistema Global: Esta etapa emplea las técnicas de Ingeniería en Software, definiendo el mantenimiento de la base de conocimientos del Sistema Experto. p. Definir el Mantenimiento de las Bases de Conocimientos: Se encarga del mantenimiento de la Base de Conocimientos. q. Adquisición de Nuevos Conocimientos y Actualización del Sistema: Se encarga de diseñar nuevos protocolos para adquirir nuevos conocimientos, y de incorporar al Sistema los nuevos conocimientos adquiridos. 5. Lograr Una Adecuada transferencia Tecnológica: Para la correcta implantación del sistema, es necesario una correcta transferencia tecnológica de manejo desde la parte que lo desarrolló hacia los usuarios finales. Esta fase se divide en las siguientes etapas: r. Organizar la Transferencia Tecnológica: Se suelen usar entrenamientos en sesiones de tutoría entre los diseñadores y los usuarios para explicar el manejo del sistema y el entendimiento de la documentación. s. Completar la Documentación del Sistema Basados en Conocimientos Construido: Se debe crear el manual de usuario, el cual deberá estar orientado al usuario final. Página 15 de 42 Resumen de Inteligencia Artificial Lógica La lógica se puede emplear para: Representar el Conocimiento: Permite pasar del Lenguaje Natural al Lenguaje Lógico. Las traducciones deben realizarse sin aplicar conclusiones, o sea, de forma textual y literal. Razonar o Generar Nuevo Conocimiento: Para ello se pueden emplear: o La Inducción: Permite pasar de un caso particular a la regla general. o El Método Deductivo: Del caso general se obtiene un caso particular y se deduce una conclusión particular; y del caso general se obtiene un caso general y se deduce una conclusión particular. El Método Deductivo se clasifica en: Deducción Natural. Deducción Automática. Deducción Axiomática. o La Analogía. Tipos de Lógica Deductiva Lógica Proposicional Es el modo más básico y elemental para poder representar conocimientos. Elementos Son los que permiten construir las proposiciones que representan los hechos de la realidad y sus relaciones. Los elementos de la Lógica Proposicional son: Proposiciones: Representan hechos de la realidad. Se representan en minúscula (p, q, r, …). Operadores Lógicos: Relacionan hechos o Proposiciones. Son: o Y: . o O: . o NO: . o Entonces: . o Sí y Sólo Sí: . Tablas de Verdad Representan el resultado de relacionar dos proposiciones a través de un Operador Lógico. V F V F V F V F V V V F V V V V V F V V F F F F V V F F V F F V F F F V Tautologías Las Tautologías son expresiones que siempre son verdaderas. Las Tautologías son las siguientes: p q p q Leyes de Morgan p q p q p p p p p q p q p q q p Leyes Conmutativ as p q q p p q r p q r Leyes Asociativa s p q r p q r p p p p p p Página 16 de 42 Resumen de Inteligencia Artificial Formas Normales Son aquellas expresiones en las cuales las relaciones entre sus proposiciones sólo se encuentran representadas por los operadores , y . Existen dos Formas Normales, las cuales se enumeran a continuación: Forma Normal Conjuntiva (FNC): Posee la forma Forma Normal Disyuntiva (FND): Posee la forma El método de simplificación para llevar una expresión a alguna de las Formas Normales es el siguiente: 1) Sustituir: 2) Sustituir: 3) Sustituir: p q p q p q p q por: por: por: p q q p p q p q p q 4) Sustituir: por: 5) Sustituir: p por: p 6) Aplicar las Leyes Distributivas. 7) Sustituir: por: V p p p p por: F Lógica de Primer Orden A diferencia de la Lógica Proposicional, la Lógica de Primer Orden agrega varios elementos para descomponer la expresión. Elementos Son los que permiten construir las proposiciones que representan los hechos de la realidad y sus relaciones. Los elementos de la Lógica de Primer Orden son: Variables: Representan hechos de la realidad. Se representan en minúscula (x, y, z, w, …). Constantes: Se representan en minúscula (a, b, c, d, …). Operadores Lógicos: Relacionan hechos o Variables. Son: o Y: . o O: . o NO: . o Entonces: . o Sí y Sólo Sí: . Cuantificadores: Permiten englobar y definir un alcance para los hechos individuales. Son: o Para Todo: . o Existe: . Funciones de Verdad: Indican funciones sobre las Variables H x : x es ... . En las expresiones, generalmente los la existencia de . implican la existencia de o ; mientras que los implican El Método Deductivo Deducción Natural Se parte de un conjunto de hipótesis que se consideran verdaderas y se llega a demostrar la tesis. Se deben usar todas las hipótesis, a las cuales se les aplican reglas. Aplicando las reglas obtengo nuevas hipótesis que también deberán ser verdaderas. Las Hipótesis y la Tesis poseen la siguiente estructura: Página 17 de 42 Resumen de Inteligencia Artificial Hipótesis 1 Hipótesis 2 Hipótesis n Tesis Y a medida que se van resolviendo las Hipótesis para llegar a la Tesis se tendrá la siguiente estructura: 1) Hipótesis 1 2) Hipótesis 2 n) Hipótesis n n 1) Hipótesis n 1 HIP 1 HIP 2 HIP n Regla , i , j Reglas de Deducción Natural Para Proposiciones A continuación se enumeran las Reglas Básicas de Deducción Natural Para Proposiciones: 1. Introducción de la Implicación (II): Si al llegar a una determinada etapa de la deducción, nos interesa demostrar A → B, entonces se debe suponer “A” (ésta es un tipo de hipótesis que se introduce por conveniencia en la demostración). Si al hacer esa suposición, y aplicando reglas de deducción se llega a deducir “B”, se cierra la suposición escribiendo A B. A B AB 2. Eliminación de la Implicación (EI) o Modus Ponens (MP): Si en dos líneas determinadas aparecen fórmulas de la forma A y A → B, se puede escribir en la línea que sea más conveniente para la demostración, posterior a esas dos, una fórmula de la forma B. A AB B 3. Introducción de la Conjunción (IC): Si en dos líneas determinadas aparecen A y B, en una línea posterior se puede escribir su conjunción. A B AB 4. Eliminación de la Conjunción (EC): Si en una línea se tiene la conjunción de dos fórmulas, se puede, en cualquier línea posterior, escribir cualquiera de las dos fórmulas. AB AB A B 5. Introducción de la Disyunción (ID): Si en una línea se tiene A o se tiene B, en otra línea posterior se puede escribir A B. Página 18 de 42 Resumen de Inteligencia Artificial A B AB AB 6. Eliminación de la Disyunción (ED): Una vez dada o deducida una disyunción A B, se trata de comprobar si suponiendo cada uno de los términos, A y luego B, se obtiene un mismo resultado C. Si es así, se cierran las suposiciones y se escribe C. A B A B C C C 7. Introducción de la Negación (IN): Si suponiendo una fórmula A, se llega a una contradicción, en una línea posterior se puede escribir la negación de A. A B B A 8. Eliminación de la negación (EN): De la doble negación de una fórmula, se obtiene esa misma fórmula. A A Reglas de Deducción Natural Para Predicados A continuación se enumeran las Reglas Básicas de Deducción Natural Para Predicados: 1. Introducción de (I ): Esta regla dice que si un elemento de un colectivo tiene una propiedad y ese elemento “a” es genérico, entonces se puede afirmar que el resultado vale para cualquier elemento del colectivo. Por lo tanto, esta regla se puede aplicar si “a” es genérico, es decir, si no está en ningún otro supuesto previo que lo restrinja. Pa xPx 2. Eliminación de (E ): Esta regla dice que si de un colectivo se afirma algo universalmente, lo mismo se puede afirmar de cualquier miembro del colectivo. xPx Pa 3. Introducción de (I ): Esta regla dice que si un elemento de un colectivo tiene una propiedad, entonces existe algún elemento que la cumple. Pa xPx 4. Eliminación de (E ): Esta regla dice que si existe algún elemento de un colectivo que cumple una propiedad, entonces puedo particularizar el predicado P para ese determinado individuo. En este caso, “a” queda restringido. Página 19 de 42 Resumen de Inteligencia Artificial xPx Pa Deducción Automática Es un método que permite automatizar la deducción. Posee las siguientes etapas: 1. Preparar las Fórmulas: Consiste en preparar las expresiones para su posterior demostración. Primero se deben llevar las expresiones a Lógica Proposicional, a través de la Forma Prenex y la Forma Skolem. a. Forma Prenex: Una fórmula se encuentra en Forma Prenex cuando todos sus cuantificadores se encuentran al comienzo de la misma. Para pasar una fórmula a Forma Prenex se deberán seguir las siguientes reglas: x Ax Bx x Ax Bx Ax x Bx x Ax Bx x Ax Bx x Ax Bx Ax x Bx x Ax Bx x Ax x Ax x Ax x Ax x Ax Bx x Ax Bx x Ax Bx x Ax Bx Ax x Bx x Ax Bx Ax x Bx x Ax Bx b. Forma Skolem: Una fórmula se encuentra en Forma Skolem una vez que se han eliminado todos sus cuantificadores. Para ello se siguen las siguientes reglas: i. : Si es el primer cuantificador de izquierda a derecha en una fórmula se deberá reemplazar la variable por una constante y se eliminará el cuantificador. Si no es el primer cuantificador de izquierda a derecha en una fórmula se deberá reemplazar la variable por una función de las variables de todos los precedentes. ii. : Directamente se elimina el cuantificador. Si una expresión se encuentra en Forma Skolem, también se encuentra implícitamente en Forma Prenex. c. Forma Normal: Una vez que las expresiones se encuentran en Lógica Proposicional será necesario llevarlas a Forma Normal, ya sea conjuntiva o disyuntiva a través de los pasos vistos anteriormente. Si una expresión se encuentra en Forma Normal, también se encuentra implícitamente en Forma Skolem y en Forma Prenex. 2. Demostración: Para poder realizar la demostración, el método se basa en las siguientes dos teorías:0 a. Teoría de la Completitud: F1 F2 Fn V Modelo F1 F2 Fn . Una teoría es consistente si y solo si existe un modelo que lo sustente. b. Teoría de la Consistencia: H ├─ T H T F y H H 1 H 2 Hn . Este teorema establece que un conjunto de hipótesis demuestran una tesis si y solo si al agregar al conjunto de hipótesis la negación de la tesis, se llega a una inconsistencia. A partir de éstas dos teorías, se trata de buscar un modelo para H T . Para poder realizar la demostración se emplea el Método Herbrand, para ello se deberán obtener: a. Universo de Herbrand: U H Constantes . AH A cada función de verdad aplicarle U H . c. Sistema de Herbrand: S H Aplicar fórmula a todas las combinacio nes del U H . b. Átomos de Herbrand: Finalmente a partir de SH, cada combinación es un valor de verdad, con lo que pueden pasar dos cosas: Página 20 de 42 Resumen de Inteligencia Artificial a. Si al menos una de las combinaciones de SH es verdadera, entonces existe un modelo y se cumple que H T V . Por lo tanto no se puede demostrar la Tesis. b. Si todas las combinaciones de SH son falsas, entonces no existe un modelo y se cumple que H T F . Por lo tanto sí se puede demostrar la Tesis. Resumen de Reglas Deducción natural en lógica proposicional II Regla H Introducción de la implicación A .. B EI Eliminación de la implicación o MP Modus Ponens T A -> B A A -> B A B IC Introducción de la Conjunción EC Eliminación de la Conjunción A^B ID Introducción de la Disyunción A ED Eliminación de la Disyunción AvB IN Introducción de la Negación EN Eliminación de la Negación A [Sup] .. B A ->B B A^B Elijo A ó Elijo B AvB Sup A Sup B .. .. C C C A .. B ^ ¬B ¬¬A ¬A A Tip: Si tengo NO implicaciones en la tesis -> NO puedo suponer en la hipótesis. Deducción natural de Lógica de Primer Orden Regla I∀ Introducción de ∀ Pa con ‘a’ genérico sin restricciones (sale de un ∀) E∀ Eliminación de ∀ ∀ x Px Pa generico I∃ Introducción de ∃ Pa con ‘a’ restringido (sale de un ∃) ∃ x Px E∃ Eliminación de ∃ ∃ x Px Pa restringido ∀ x Px Tip: Si al hacer un ejercicio, una hipótesis tiene el cuantificador ∃, entonces la tesis deberá tener el mismo cuantificador ya que la variable se encuentra restringida. Página 21 de 42 Resumen de Inteligencia Artificial Métodos de Búsqueda Definiciones Varias – Heurística: Se la puede definir como “sentido común”. Es una función aplicada a cada nodo que indica una directriz sobre qué tan bueno es estar en cada nodo. Es un mecanismo de evaluación que guía la búsqueda en un sentido determinado. Los Métodos de Búsqueda Los Métodos de Búsqueda son métodos de resolución de problemas. Al presentarse un problema éste debe descomponerse. El primer paso para resolverlo consiste en crear una forma descriptiva formal y manipulable a partir de la descripción informal del problema. El Espacio de Estados o Espacio del Problema Es el dominio que contiene todos los posibles estados del sistema. Surge para representar la forma descriptiva formal necesaria para resolver el problema. El Espacio de Estados puede ser: Finito: Si la cantidad de Estados que lo componen es finita y determinable. Infinito: Si la cantidad de Estados que lo componen no es finita o determinable. Los Estados Los Estados son representaciones que contienen el conjunto de toda la información que describe la situación del sistema en un momento dado. Se pueden clasificar en: Estado Inicial: Es el estado del cual se parte en la búsqueda de la solución al problema. Estados Intermedios: Estados que no son el Estado Inicial ni un Estado Solución. Estado/s Final/es: Son los estados solución o estados objetivo. Las Reglas u Operadores Es un mecanismo que se emplea para modificar o transformar un Estado del sistema. Se utilizan para enlazar un Estado Actual con otro Estado Objetivo. Una Regla se compone por: Estado Actual: Es el Estado sobre el cual se aplican la Regla. Operando: Es el operador. Estado Resultado: Es el Estado resultante. El proceso de solución de un problema es el proceso mediante el cual partiendo de un Estado Inicial y mediante una Estructura de Control que selecciona y aplica Reglas que producen Transiciones entre Estados pertenecientes al Espacio de Estados del problema, se llega a un Estado Solución. Clasificación de los Problemas Los problemas se pueden clasificar en: Ignorables: Son aquellos en los cuales un error en la búsqueda no altera el proceso. Recuperables: Son aquellos en los cuales existen movimientos que pueden compensar los errores en la búsqueda. No Recuperables: Son aquellos en los que los errores no tienen vuelta atrás. Sistema de Producción Un Sistema de Producción es un Sistema Informático con una estructura especial que permite realizar los procesos de búsqueda. El Sistema de Producción posee: Las Reglas: Son las que producen las transiciones entre los distintos Estados. La Base de Conocimientos: Contiene la información apropiada para la tarea en particular. La Estrategia de Control: Especifica el orden en el que las reglas son procesadas y la forma de resolver los conflictos que surjan cuando varias reglas puedan ser aplicadas a la vez. La inteligencia se ve en la decisión tomada. La Estrategia de Control debe: o Causar algún cambio: Debe poder producir cambios a corto plazo. o Ser sistémica: Debe poder producir cambios a largo plazo. El Aplicador de Reglas: Nunca contradice la Estrategia de Control, ya que es la parte crítica. Página 22 de 42 Resumen de Inteligencia Artificial Clasificación de los Sistemas de Producción Los Sistemas de Producción se pueden clasificar en los siguientes tipos: Monótono: Es aquel en el cual la aplicación de una regla no prevé la posterior aplicación de otras reglas, que podrían haberse aplicado cuando se seleccionó la primera. No Monótono: Es aquel en que se aplican todas y cada una de las reglas que pueden ser tomadas en un momento determinado. Parcialmente Conmutativo: Es aquel en el cual si se aplican una secuencia de reglas transforma el estado X al estado Y, entonces por alguna permutación permitida de estas reglas también transforma el estado X en estado Y. No Parcialmente Conmutativo: Aquel donde si se permutan cualquiera de las reglas no se llega del estado X al estado Y. Son aptos para resolver Problemas No Recuperables. Conmutativo: Sistema que es a su vez monótono y Parcialmente Conmutativo. No contemplan volver a estados pasados. Tienden a alcanzar muchos estados individuales duplicados. Métodos de Búsqueda Sin Información del Dominio Son los Métodos que operan sin un conocimiento que pueda guiar la búsqueda acerca del dominio del problema, por lo que se deberá realizar una búsqueda exhaustiva en todo el Espacio de Estados. Primero en Amplitud A diferencia del Método Primero en Profundidad, recorre el árbol modificando (modifica) el Estado Actual por Niveles, en vez por ramas. Parte del Estado Inicial y aplica todas las reglas posibles, luego por cada nodo generado vuelve a aplicar todas las reglas posibles, generando así los nodos por niveles. En la práctica se implementa con una estructura de cola FIFO. Ventajas No queda “atrapado” en una rama cíclica o periódica. Si existe una solución, la encuentra. Si hay varias soluciones, encuentra la mejor de ellas. D e s ve n t a j a s Consume una mayor cantidad de recursos computacionales (memoria, tiempo de CPU, etc.). Primero en Profundidad El algoritmo barre el árbol (o grafo) una rama a la vez, buscando el Estado Final en cada subrama de cada Estado del Espacio de Estados. A Medida que el Algoritmo va cambiando el Estado Actual, analiza las reglas para el nuevo Estado y va actualizando el Estado Actual “Moviéndose” en el árbol a través de las ramas. En la práctica se implementa con una estructura de cola LIFO. Ventajas Consume una menor cantidad de recursos computacionales (memoria, tiempo de CPU, etc.). Si existe una solución, la encuentra. Se puede encontrar una solución sin haber buscado en gran parte del árbol. D e s ve n t a j a s Puede llegar a quedar “atrapado” en una rama cíclica o periódica, por lo que será necesario establecer un valor de corte como umbral. Devuelve la primera solución que encuentra. Si hay varias soluciones devuelve la primera de ellas, que puede no ser la mejor de ellas. Bidireccional Combina los Métodos de Búsqueda Primero en Amplitud y Primero en Profundidad. Se deberán conocer tanto el Estado Inicial como un Estado Final a fin de realizar dos búsquedas: 1. Búsqueda Top–Bottom: Partiendo desde el Estado Inicial se pretende hallar el Estado Final. 2. Búsqueda Bottom–Top: Partiendo desde el Estado Final se pretende hallar el Estado Inicial. Si bien cada búsqueda puede usar cualquiera de los dos métodos, una de ellas deberá usar el Método Primero en Amplitud. Cuando las búsquedas se crucen se podrá reconstruir el camino. Página 23 de 42 Resumen de Inteligencia Artificial Generación y Prueba En éste Método se genera una posible solución y se la compara contra todas las demás. Emplea el Método Primero en Profundidad, en donde se va explorando una rama a la vez. Generalmente se implementa con una vuelta hacia atrás. Ventajas Es adecuado para problemas sencillos. Si existe una solución, la encuentra. D e s ve n t a j a s Si el problema es complejo puede consumir mucho tiempo en encontrar la solución, ya que recorre todo el Espacio de Estados. Métodos de Búsqueda Con Información del Dominio Son aquellos Métodos que operan con un conocimiento que guía la búsqueda en un determinado sentido. Generalmente el conocimiento se basa en una función heurística que permite probar primero los caminos más prometedores, evitando una explosión combinatoria. Permiten facilitar la búsqueda de el/los Estado/s Final/es. Se suelen usar para encontrar una solución aceptablemente buena, no necesariamente la mejor dentro de todo el Espacio de Soluciones. Escalada Es una variante del Método Generación y Prueba. Utiliza una Función Heurística a los propósitos de obtener retroalimentación. Permite escalar por los nodos si el valor heurístico del nodo destino es mejor al valor heurístico del nodo origen o actual. Es un Método Local, o sea que tiene en cuenta únicamente las consecuencias inmediatas y no contempla retrocesos en la búsqueda. El Método funciona correctamente siempre y cuando la Función Heurística sea monótonamente decreciente (o creciente). Posee dos variantes: Escalada Simple y Escalada de Máxima Pendiente. – Escalada Simple Dado un Estado Actual, se aplican uno a uno los Operadores sobre éste y se “escala” por el primer sucesor cuya Función Heurística sea mejor que la del Estado Actual. Ventajas El Método es más rápido que el Método de Escalada de Máxima Pendiente. D e s ve n t a j a s Necesita más pasos para poder llegar a la solución. Se ensaña con una rama y abandona el resto. Posee mayor probabilidad de estancarse ante un mínimo (o máximo) local. No garantiza encontrar la solución, pese a que esté a un nodo de distancia. Si existe un sucesor mejor que por el que escala, pero que aún no se ha generado, éste se pierde. No se puede aplicar en problemas donde la solución es relativa. – Escalada de Máxima Pendiente Es una variante del Método de Escalada Simple. Pretende resolver el problema que se da al generar y evaluar los sucesores de un nodo de a uno. Dado un Estado Actual, generar todos los sucesores del Estado y luego los evalúa uno por uno, “escalando” por el mejor de ellos incluyendo al Estado Actual. Ventajas Posee menor probabilidad de estancarse ante un mínimo (o máximo) local. Si encuentra una solución, ésta es mejor que la posible solución encontrada por el Método de Escalada Simple, en el caso de que difieran. Necesita menor cantidad de pasos para hallar la solución. D e s ve n t a j a s Se ensaña con una rama y abandona el resto. El Método es más lento que el Método de Escalada Simple. Página 24 de 42 Resumen de Inteligencia Artificial No garantiza encontrar la solución, pese a que esté a un nodo de distancia. De todas formas puede no hallar la solución si se cae en un mínimo (o máximo) local. No se puede aplicar en problemas donde la solución es relativa. El Primero Mejor Combina las ventajas de los Métodos de Primero en Amplitud y Primero en Profundidad. Sigue un único camino a la vez y lo cambia cuando otro camino parece más prometedor. Resuelve el problema de los Métodos de Escalada. Es parecido al Método de Escalada de Máxima Pendiente ya que por cada nodo se evalúan todas las reglas para determinar los nodos hijos. Igualmente posee dos diferencias: 1. En Escalada, al elegir un nodo, todos los demás se abandonan. 2. En este Método se elige el mejor estado disponible, aún si el valor de su función es menor al actual. El Método emplea dos listas: Lista de Abiertos: Nodos generados pero que no se han explorado los sucesores. Se encuentra ordenada y priorizada por el valor heurístico de cada nodo. Lista de Cerrados: Nodos generados, de los cuales ya se han generado los nodos sucesores correspondientes. Se encuentra ordenada históricamente. En cada iteración se reordena la Lista de Abiertos, lo que posibilita la vuelta atrás. Al generar un nodo se debe controlar que ya no se encuentre en la Lista de Cerrados. Si esto sucede no se evaluará pero si se indicará ésta situación en el modelo, para no simplificar la realidad. Como el algoritmo avanza siempre por el mejor camino, al hallar una solución asume que ésta es la mejor y termina el proceso de búsqueda. El proceso también termina en el caso de que la Lista de Abiertos quede vacía. Es una simplificación del Método A*, dado que su Función Heurística sólo pondera la estimación del costo desde un nodo al nodo solución, lo que queda por recorrer, y no el costo desde la raíz hasta ese nodo, o sea el camino recorrido. En la resolución de problemas se deberá emplear la siguiente tabla: Iteración 1 … N Ítem Nodo Actual ¿Es Solución? Lista de Abiertos Lista de Cerrados … Nodo Actual ¿Es Solución? Lista de Abiertos Lista de Cerrados Valor (Estado Inicial) SI / NO (Sucesores del Estado Inicial) (Estado Inicial) … (Primer Nodo de la Lista de Abiertos) SI / NO Reordenar(Lista de Abiertos – Nodo Actual + Sucesores del Nodo Actual) (Lista de Cerrados + Nodo Actual) A* Es similar al anterior, salvo que la Función Heurística se reemplaza por la siguiente aproximación: F ' g estado h ' estado En donde: g estado representa la suma de los costos de los nodos predecesores (el costo de llegar hasta ese nodo). h estado representa la estimación de lo que cuesta llegar a un nodo objetivo desde ese nodo. El Costo es relativo a la Transición y no al Estado. Puede ser: Lineal: Es el mismo en cada nivel. Exponencial: Crece al ir pasando a un nivel inferior. ' Permite encontrar el camino de mínimo costo. En caso de existir una solución, el algoritmo la encuentra. Por esto se dice que el Método A* es un Método Completo. En la resolución de problemas se deberá emplear la tabla vista en el Método el Primero Mejor. Salvo que en la Lista de Abiertos los nodos tendrán la forma Nodo g h ' , y se deberá reordenar por éste valor. Página 25 de 42 Resumen de Inteligencia Artificial Método de Reducción de Problemas Se emplea en los casos en que los problemas pueden descomponerse en subproblemas. Dado un problema se lo divide de manera recursiva en problemas menores hasta llegar a Problemas Primitivos (problemas atómicos de resolución inmediata). Problema Meta Problema Primitivo Solución Problema Meta Solución Problema Primitivo La resolución de todos los problemas primitivos implica que el problema principal ha sido resuelto. Para graficar se emplean los denominados Grafos Y-O. En donde se dibujan arcos en las transiciones entre estados para representar el Y. Se comienza por el Estado Inicial generando todos los posibles sucesores y se evalúan los valores a fin de determinar el mejor camino. Al ir visitando los nodos descendientes se van reevaluando los valores heurísticos, con lo cual se deben propagar los cambios hacia arriba. Constantemente hay que comparar los nuevos valores obtenidos con los valores anteriores para determinar si se debe seguir por un camino o cambiarlo por otro con mejor valor. El proceso termina cuando se encuentra una solución o cuando todos los caminos llevan a callejones sin salida. Las principales diferencias con el Método el Primero Mejor son: En el Primero Mejor la vuelta atrás no es necesaria, en cambio en el Método de Reducción de Problemas si porque hay que reevaluar los nodos expandidos para determinar el mejor camino. En el Primero Mejor se buscaba el camino con menor costo, en cambio en el Método de Reducción de Problemas los caminos individuales que van de un nodo a otro no deben ser tomados independientemente de los caminos a través de otros nodos conectados a los nodos originales mediante arcos Y. Página 26 de 42 Resumen de Inteligencia Artificial Análisis de Protocolos Es una técnica que permite observar y grabar a un Experto en la resolución de un problema para lograr educir conocimientos del él, que luego sirvan en la construcción de un Sistema Basado en Conocimientos. Etapas del Análisis de Protocolos Esta técnica de Educción de Conocimientos posee las siguientes etapas. 1. Grabación del Protocolo La cual se divide en las subetapas siguientes: Introducción: El Ingeniero en Conocimiento le explica al Experto lo que espera de él. Se le pide que hable en voz alta diciendo que diga lo que piensa, lo que hace, pero no que explique sus razonamientos. Si el Experto se quedase callado por un lapso mayor a los tres segundos, deberá indicarse tal situación y pedirle que continúe. Puesta en Situación: Se busca brindarle confianza al Experto, por ejemplo mediante la resolución de algún ejercicio introductorio. Registro del Protocolo: Es la grabación y la registración de lo que dice y hace el Experto. 2. Transcripción Se transcribe lo grabado segmentándolo en frases con el fin de poder analizarlo de una mejor forma. La división en frase se realiza tratando de que cada una aporte algo por sí sola. En la resolución de la transcripción, se deberá emplear la siguiente tabla: Línea 1 2 … n Transcripción Se deberán indicar las pausas que tuvo el Experto empleando corchetes, y dentro de ellos indicando la … duración de las mismas. 3. Codificación A esta etapa se la divide en las siguientes subetapas: Identificación de Conceptos, Características, Valores, Relaciones y Operadores: Se los suele denominar también como Elementos del Protocolo. Se debe analizar frase por frase de la tabla anterior para poder determinar cada uno de estos Elementos. o Conceptos: Representan una entidad, un conocimiento. o Características: Las Características se relacionan con los Conceptos, ya que establecen las cualidades que pueden tener éstos. Serían como los atributos. o Valores: Se relacionan con las Características. Son los valores que puede adoptar una determinada Característica. O sea que definen las particularidades de un Concepto determinado que lo hacen distinguible de otros Conceptos de su misma especie. o Relaciones: Son explícitas y pueden relacionar un Concepto con otro Concepto o un Concepto con una Característica. o Operadores: Son los medios que el Experto utiliza para pasar de un estado del problema a otro estado más próximo a la solución. Se deberá emplear la siguiente tabla: Significado Concepto Característica Valor Relación Operador … Texto … Identificación de las Relaciones de Protocolo: Consiste en determinar las relaciones que existen dentro del protocolo. Se deberá construir la siguiente tabla, denominada Tabla Concepto-Característica-Valor, para ordenar y relacionar los Elementos del Protocolo detectados en la tabla anterior: Concepto Característica Valor Página 27 de 42 Resumen de Inteligencia Artificial Concepto Concepto … Característica (Característica) … Valor Valor … Entre paréntesis se deberán indicar aquellas relaciones implícitas entre un Concepto y un Valor. El siguiente paso consiste en establecer las Relaciones de Protocolos, que son relaciones explícitas entre Conceptos. Para ello se emplea un grafo como se muestra a continuación: Concepto k RELACIÓN A Concepto i RELACIÓN B Concepto j RELACIÓN C Concepto m Identificación de la búsqueda: Consiste en determinar los estados por los cuales pasa el Experto desde el estado inicial hasta llegar al estado solución. En la resolución de los ejercicios se deberá seguir el siguiente esquema: Estado Inicial Características distintivas 1 Operador 1 Estados Intermedios Características distintivas n Operador n Estado Final Identificación de Metacomentarios, Sinónimos e Incertidumbres: En base a la primera tabla se deberán detectar los Metacomentarios, los Sinónimos y las Incertidumbres. o Metacomentarios: Frases o palabras que no aportan nada en el Protocolo, sin embargo pueden representar razonamientos ocultos y pueden servir más adelante en otro Análisis de Protocolo. Sus Elementos no deben ser tenidos en cuenta en el Análisis. o Sinónimos: Palabras que representan la misma idea o concepto. o Incertidumbres: Palabras o frases que implican dudas o deducciones inciertas. Influyen en los operadores pero no forman parte de él. Representa un grado de certidumbre para un operador que brinda el Experto. En la resolución de los ejercicios se deberá seguir el siguiente esquema: Sinónimos: … … Metacomentarios: Línea n … Metacomentario … … Significado … … Incertidumbres: … … 4. Interpretación En ésta etapa se definen las reglas de razonamiento del experto. La cantidad de reglas debe ser la misma que la cantidad de operadores, que no pertenezcan a un metacomentario. Las Reglas son de la forma: SI ( CONDICIONES ) ENTONCES ( ACCIONES ) Y en donde, CONDICIONES: CONCEPTO.CARACTERÍSTICA = VALOR Página 28 de 42 Resumen de Inteligencia Artificial Anexo: Ejercicios (by JuanMA) “podríamos sostener que estamos identificando” Podríamos sostener: incertidumbre. Relación Estamos identificando: Operador (cambia el estado) Cuando hay un Vx, tiene que haber una implicación de la variable principal, pero no necesariamente de la/s secuandaria/s Página 29 de 42 Resumen de Inteligencia Artificial Emparrillado Esta es otra técnica para poder educir conocimientos de un Experto. Permite tomar en cuenta cómo piensa el experto y qué juicios emplea. Metodología 1. Identificación de los Elementos En ésta primera etapa se deben obtener los Elementos que conformarán la Parrilla. Éstos deben ser homogéneos y representativos del dominio. Que sean homogéneos se refiere a que estén en el mismo nivel. Que sean representativos indica que deberán abarcar todo el dominio. Para obtener los Elementos se pueden usar entrevistas. 2. Identificación de las Características Las Características son las cualidades que pueden ser atribuidas a los Elementos o conceptos del pensamiento. Deben ser bipolares, o sea, un Elemento es una cosa o la otra. La cantidad de Características no depende de la cantidad de elementos. Dichas Características pueden ser obtenidas mediante entrevistas. También se deberán determinar los polos de las Características, o sea cuál es el extremo que toma en cuenta en primera instancia el Experto. 3. Diseño de la Parrilla Se deberá construir una matriz, denominada Parrilla, tal como se muestra a continuación: C1 C2 C3 … Cm E1 E2 E3 … En V11 V21 V31 … Vm1 V12 V22 V32 … Vm2 V13 V23 V33 … Vm3 … … … … … V1n V2n V3n … Vmn Los tipos de Parrilla que se pueden construir son: Dicotómica: Es una matriz binaria. Las celdas adoptan los valores 0 (el elemento no posee esa característica) o 1 (el elemento sí posee esa característica). Clasificatoria: Las celdas adoptan valores entre 1 y n, donde n es el número total de elementos. No puede haber valores repetidos. Evaluativa: Las celdas adoptan valores entre 1 y x, como una escala numérica. El margen se aplica a todas las características. Al ser una escala sí puede haber valores repetidos. 4. Formalización Consta de las siguientes subetapas. 4.1. Clasificación de los Elementos Se comparar elementos contra elementos. Para ello se deberá calcular una matriz de distancia; que al ser simétrica, sólo se usará la diagonal superior. La distancia entre dos elementos E i y E j se calcula usando la siguiente fórmula: Dist Ei , E j Vki Vkj V1i V1 j V2i V2 j Vmi Vmj m k 1 Luego de calcular las distancias, la matriz quedaría: E1 E2 E3 … En E1 E2 E3 … En 0 Dist(E1, E2) 0 … … Dist(E1, E3) Dist(E2, E3) 0 … … … … … … Dist(E1, En) Dist(E2, En) Dist(E3, En) … 0 Página 30 de 42 Resumen de Inteligencia Artificial Luego se deberán agrupar los elementos tomando la menor distancia que figure en la nueva Parrilla (si se está tratando de minimizar las distancias), o tomando la mayor de las distancias (si se están maximizando las distancias entre elementos). Con los elementos agrupados se construye una nueva Parrilla, como se muestra a continuación: E1 0 E1 E2 … [Ei, Ej] … En … E2 Dist(E1, E2) 0 … … … … … … … … … … … … … … … … … [Ei, Ej] Dist(E1, [Ei, Ej]) Dist(E2, [Ei, Ej]) … 0 … En Dist(E1, En) Dist(E2, En) … Dist([Ei, Ej], En) … 0 Y, para completar los valores de cada celda se deberá tener en cuenta una nueva fórmula para calcular las distancias entre los elementos, que se muestra a continuación: Dist Ei , E j , E h Min Dist Ei , E h , Dist E j , E h O sea que se aplica la ley distributiva entre los elementos de la parte izquierda de la fórmula, se calculan las distancias correspondientes entre los elementos de la parte derecha de la fórmula según la fórmula original y luego se elige la mejor distancia para armar una nueva Parrilla con los nuevos elementos que puedan ser agrupados. El método vuelve a ciclar hasta que todos los elementos se hayan agrupado. Una vez que se han agrupado los elementos se deberá construir el Árbol Jerárquico de Distancias de Elementos, tal como se muestra a continuación: k … 3 2 1 Ei Ej Eh … En 4.2. Clasificación de las Características Es similar al proceso de Clasificación de los Elementos, salvo que se calculan dos valores de distancia: En la Diagonal Superior de la Parrilla se calcula la Distancia 1 (d1) de forma similar al cálculo de las distancias entre elementos. En la Diagonal Inferior de la Parrilla se calcula la Distancia 2 (d2), tal cual se muestra a continuación. Para calcular ambas distancias se emplean las siguientes fórmulas: d1 : Dist 1 Ci , C j Vik V jk Vi1 V j1 Vi 2 V j 2 Vin V jn n k 1 d 2 : Dist 2 Ci , C j Dist 1 Ci , C 'j Dist 1 Ci' , C j ' h En donde el valor de C es el opuesto de C h . Esto se logra armando una nueva Parrilla basada en la Parrilla original y en donde sus valores son opuestos de acuerdo a la escala empleada: En el caso de las Parrillas Dicotómicas, se debe negar el valor de cada celda. En el caso de las Parrillas Clasificatorias o Evaluativos se deberá emplear la siguiente fórmula: Vij' w 1 Vij En donde w adopta el mayor valor de los valores de la escala (n o x, según el tipo de Parrilla). Finalmente la matriz de distancias entre características quedaría así: C1 C2 C3 C1 0 Dist1(C1, C2) Dist1(C1, C3) C2 Dist2(C1, C2) 0 Dist1(C2, C3) C3 Dist2(C1, C3) Dist2(c2, C3) 0 … … … … Cm Dist2(C1, Cm) Dist2(C2, Cm) Dist2(C3, Cm) … Cm … … … … … Dist1(C1, Cm) Dist1(C2, Cm) Dist1(C3, Cm) … 0 Página 31 de 42 Resumen de Inteligencia Artificial Como sólo hay que trabajar con la diagonal superior, se deberá construir una nueva Parrilla de distancias de características tomando de la matriz anterior la distancia mínima entre los opuestos por la diagonal: Dist Ci , C j Min Dist 1 Ci , C j , Dist 2 Ci , C j C1 C2 C3 … Cn C1 C2 C3 … Cn 0 Dist(C1, C2) 0 … … Dist(C1, C3) Dist(C2, C3) 0 … … … … … … Dist(C1, Cn) Dist(C2, Cn) Dist(C3, Cn) … 0 Al construir la nueva matriz se deberán agrupar las características siguiendo el mismo proceso que se ha indicado en la Clasificación de los Elementos. Salvo que para calcular las distancias en base a la Parilla diagonal superior se deberá emplear la siguiente fórmula: Dist Ci , C j , C h Min Dist Ci , C h , Dist C j , C h El método vuelve a ciclar hasta que todas las características se hayan agrupado. Una vez que se han agrupado todas las características se deberá construir el Árbol Jerárquico de Características. k … 3 2 1 Ci Cj Ch … Cn 5. Interpretación o Análisis de los Resultados En esta última etapa se deberán analizar los siguientes ítems con el fin de obtener una conclusión: En base a los Elementos: o Cantidad de grupos que se han formado. o Grupos que se han formado. o Similitud entre los Elementos. En base a las Características: o Cantidad de grupos que se han formado. o Grupos que se han formado. o Similitud entre las Características. 6. Red de relaciones entre Características Se arma a partir del Texto Página 32 de 42 Resumen de Inteligencia Artificial Paralela Recíproca A B A B A B X Y X Y X Y Ortogonal Ambiguas A B A B A B A B X Y X Y X Y X Y Página 33 de 42 Resumen de Inteligencia Artificial Algoritmos Genéticos Introducción a los Algoritmos Genéticos Bases de los Algoritmos Genéticos Los Algoritmos Genéticos se encuentran basados en la: Genética. Teoría de la Evolución: Fue propuesta por Darwin, y propone: o Adaptación. o Supervivencia del más fuerte (del más adaptado). Los factores fundamentales que posee la Teoría de la Evolución son: o Selección Natural: Sólo los más aptos sobreviven en el ecosistema. o Cruzamiento: Es la concepción de nuevos individuos a partir de los ya existentes. o Mutación: Cambios aleatorios en los cromosomas. Comparación entre la Biología y los Algoritmos Genéticos Podemos comparar la Biología con los Algoritmos Genéticos a través de la siguiente tabla: Biología Ecosistema Organismos/Individuos Población Genes Algoritmos Genéticos Problema Posibles Soluciones (Individuos o Cromosomas) Población (De cada Ciclo) Genes (Valores binarios) Genotipo (Conjunto de Genes) Propiedad Pasos Para Configurar un Algoritmo Genético Ante un problema deberemos seguir los siguientes pasos a fin de configurar el Algoritmo Genético: 1. Definir el Cromosoma: Primero se deberán identificar las propiedades o características del problema en cuestión. Y luego se deberán asignar las posiciones dentro del cromosoma a cada una de las propiedades identificadas. El Cromosoma es el patrón de las características o propiedades que deberá tener la solución. La definición del Cromosoma quedaría como se muestra a continuación: … PROPIEDAD 1 PROPIEDAD n 2. Definir la Función de Aptitud: Es el segundo paso en la configuración de un Algoritmo Genético. La Función de Aptitud ( f ) permite comparar y descartar alternativas en base al análisis de los cromosomas. Esta función puede ser tanto una función matemática, una serie de condiciones como una combinación de ambas. Esta función depende del problema dado y del cromosoma La Función de Aptitud emplea la heurística para determinar qué tan bueno es estar en determinado estado. La Función de Aptitud queda representada por la expresión f Cromosoma Valor Real . Esquema de los Algoritmos Genéticos A continuación se presenta el esquema que posee un Algoritmo Genético. Página 34 de 42 Resumen de Inteligencia Artificial GENERAR POBLACIÓN INICIAL Pi+1 P0 SELECCIÓN PS CRUZAMIENTO PD MUTACIÓN Pi+1 NO PARO ? SI POBLACIÓN FINAL Operadores o Funciones Básicos Los operadores o funciones básicas que posee el Algoritmo Genético son: 1. Selección: Comparación y selección de los mejores individuos. Permite seleccionar los candidatos a cruzar. Se realiza en todas las Iteraciones 2. Cruzamiento: Generación de nuevos individuos a partir de los individuos seleccionados. 3. Mutación: Alteración esporádica y al azar de un gen del cromosoma de un individuo. Este operador evita la pérdida de posibles soluciones. Por tal motivo la mutación permite acercarnos más a la solución. En cuanto a la convergencia, no converge más rápido si ningún individuo de la población E t a p a s d e l Al g o r i t m o G e n é t i c o Las etapas que sigue el Algoritmo Genético para resolver un problema son: 1. Generar Población Inicial: Se genera un conjunto de cromosomas, no todo el espacio de soluciones, denominado Población Inicial (P0). La convergencia del Algoritmo Genético no depende de P0. Sin embargo sí deben configurarse dos parámetros: o Cantidad de Individuos: Puede ser tanto fija como variable, aunque generalmente se emplea una cantidad fija. o Generación de Cromosomas: Puede ser tanto aleatoria como mediante un método genético, generalmente se generan de manera aleatoria. 2. Selección: En esta segunda etapa se emplea la Función de Aptitud para comparar y seleccionar los mejores cromosomas. No se generan nuevos individuos, sino que se busca obtener la Población Seleccionada (PS) a partir de P0. A veces suele hacerse una depuración de individuos no válidos en Página 35 de 42 Resumen de Inteligencia Artificial ésta etapa si no se realiza en una etapa anterior o un paso intermedio. Los métodos de selección más comunes son: a. Torneo: Hace competir a los individuos entre sí y los ganadores son elegidos para cruzarse. Presenta el problema de que tiende a elegir los cromosomas con mejor Función de Aptitud, con lo cual se puede perder algún cromosoma con alguna propiedad interesante y también se pierde diversidad. b. Ruleta: Emplea el azar para solucionar el problema del Método de Torneo. El primer paso consiste en construir la siguiente tabla para determinar la probabilidad de cada individuo: Individuo f x I1 k1 px f x f x Px m1 s1 … … … … In kn mn 1 1 – f x Luego se deberá construir el “paño” de probabilidades en base a la columna P x con las probabilidades acumuladas de cada individuo. Finalmente se deberán elegir números al azar entre 0 y 1, y comparándolos contra el “paño” se determinará PS. c. Control Sobre Número Esperado: Es similar al Método de la Ruleta, salvo la tabla que permite calcular las probabilidades de cada individuo. Se deberá emplear la siguiente tabla para determinar las probabilidades de cada individuo: Individuo f x I1 k1 f x Promedio d1 … … … In kn dn Promedio: f x f x n Mant d1 … Mant d n p x f x Promedio f x Promedio Px m1 s1 … … mn 1 f x Promedio m – – – – i Aquellos individuos que superen con su parte entera al promedio serán seleccionados inmediatamente. Luego se sigue con el procedimiento normal del método de la Ruleta calculando la probabilidad de cada individuo, armando el “paño” y generando los números al azar para terminar de seleccionar la población. 3. Cruzamiento: En esta etapa se busca cruzar los individuos seleccionados en la Etapa de Selección. Se generan nuevos individuos y se obtiene la Población Descendente (P D). En general no se tiene en cuenta la Función de Aptitud. Las técnicas de cruzamiento pueden tener en cuenta las propiedades del cromosoma o no (genotipo). Dichas técnicas son: a. Simple: Se truncan los cromosomas en una determinada posición para armar subcadenas que luego se van a combinar. No tiene en cuenta las propiedades del cromosoma. Generalmente de dos padres se obtienen dos hijos. Ie: A1 A2 … Ai Ai+1 … An-1 An A1 A2 … Ai Bi+1 … Bn-1 Bn Id: B1 B2 … Bi Bi+1 … Bn-1 Bn B1 B2 … Bi Ai+1 … An-1 An b. Multipunto: Es similar a la Técnica de Cruzamiento Simple, salvo que se establecen múltiples puntos de corte. Puede tener en cuenta las propiedades del cromosoma o no. c. Ie: A1 A2 … Ai Ai+1 … Aj Aj+1 … AnA1 A2 … Ai Bi+1 … Bj Aj+1 … An1 An 1 An Id: B1 B2 … Bi Bi+1 … Bj Bj+1 … BnB1 B2 … Bi Ai+1 … Aj Bj+1 … Bn1 Bn 1 An Binomial: Considera cada gen como posible punto de corte. Para generar los hijos sigue la siguiente regla: por cada posición genera un número al azar, luego establece un umbral y finalmente compara cada número obtenido al azar con el umbral para determinar a qué hijo pertenece. Página 36 de 42 Resumen de Inteligencia Artificial Ie: A1 A2 … Ai Ai+1 … An-1 An ≥ Umbral A1 B2 … Ai Bi+1 … An-1 Bn Id: B1 B2 … Bi Bi+1 … Bn-1 Bn < Umbral B1 A2 … Bi Ai+1 … Bn-1 An 4. Mutación: Es la etapa en la cual se altera algún gen del cromosoma para producir la mutación de los individuos. No siempre se produce mutación, debido a que se trata de mantener controlada. Los métodos de mutación que se pueden emplear son: a. Simple: Primero se obtiene un valor al azar, el cual es comparado contra un umbral denominado Probabilidad de Mutación, que puede ser generalmente de 0,1; 0,05 o 0,01. Si el valor al azar supera el umbral, no se muta; si no los supera, se muta y para ello se genera un nuevo número al azar (RPOS.MUT) que va a definir qué gen del conjunto de todos los cromosomas de los individuos se va a alterar. b. Optativa por Convergencia: A medida que la media de la función de aptitud crece, la probabilidad de mutación baja. c. Adaptativa por Temperatura: Puede ser: i. Ascendente: Al aumentar la cantidad de ciclos, aumenta la probabilidad de mutación. ii. Descendente: Al ir aumentando la cantidad de ciclos, disminuye la probabilidad de mutación. 5. Criterio de Paro: Como criterio de paro se pueden tomar la cantidad de ciclos, el tiempo transcurrido, que la Función de Aptitud supere un mínimo preestablecido ( f x Min ), que el promedio de todas las Funciones de Aptitud de una generación sea mayor a un mínimo ( Prom f x Min ), etc. Lo más común es tomar la cantidad de ciclos o f x Min . 6. Población Final: Es el conjunto de individuos que podrían ser solución. Para obtener la solución se deberá determinar el individuo que posea la mejor Función de Aptitud. Página 37 de 42 Resumen de Inteligencia Artificial Redes Neuronales Redes Neuronales Naturales Estructura de las Redes Neuronales Naturales A continuación se muestra la estructura de las Redes Neuronales Naturales. Dendritas Núcleo Axión Funcionamiento de las Redes Neuronales Naturales Una célula neuronal, o neurona, recibe impulsos de entrada a través de las Dendritas, lo cual produce una excitación en el núcleo de la neurona que se traslada hacia el Axión para ser transmitido a otra neurona. El poder de éste modelo se encuentra en la red neuronal y no en algún conocimiento almacenado. Sinapsis La Sinapsis es el contacto que existe entre las terminales axónicas de una neurona y las dendritas de la neurona siguiente. Cabe aclarar que las Dendritas y los Axiones no se tocan físicamente entre sí. La Sinapsis puede ser: Exitadora: Cuando los neurotransmisores disminuyen el potencial de la membrana de la célula posináptica y favorecen la generación de impulsos a mayor velocidad. Inhibidora: Es cuando los neurotransmisores tienden a estabilizar el potencial de la membrana y dificulta la emisión de impulsos. Redes Neuronales Artificiales Estructura de las Redes Neuronales Artificiales A continuación se muestra la estructura de las Redes Neuronales Artificiales. Yi wij Yj f(NET) W nj n Entradas Unidad Salida Funcionamiento de las Redes Neuronales Artificiales Xi Yi i Xj j Wij Peso de la conexión entre i y j Yj Página 38 de 42 Resumen de Inteligencia Artificial En la Redes Neuronales Artificiales se sigue el mismo modelo que en las Redes Neuronales Naturales, se construye una red de unidades (o neuronas) que no posee conocimiento almacenado. Los pesos ponderan la conexión (sinapsis) entre la neurona i y la j. Cada entrada posee un peso asociado wij . A su vez, a cada entrada se conectan las salidas de otras neuronas, las cuales en un momento determinado tendrán un valor Yi . La sumatoria de cada uno de esos pesos multiplicados por la entrada correspondiente es lo que se considera como Peso Neto: NET wij Yi n i 1 El Peso Neto será la entrada para la Función de Activación, la cual dará como resultado el valor de salida de dicha neurona. Cada Neurona de una Red Neuronal Artificial entonces queda definida por: Las entradas y sus pesos wij correspondientes. f NET . La Función de Activación Cómo se conectan las neuronas, los tipos de capas y los tipos de conexión que se presentan. Las Redes Neuronales Artificiales poseen memoria implícita, es decir que no se haya centralizada, sino distribuida en el conjunto de las Neuronas y sus pesos e interconexiones. Los tipos de conexión que pueden darse en una Red Neuronal Artificial son: Sólo hacia delante. Consigo misma. Con neuronas del mismo nivel. Tipos de Neuronas En las Redes Neuronales Artificiales podemos encontrar los siguientes tipos de Neuronas: Neuronas de Entradas: Son aquellas neuronas que reciben los estímulos del exterior. Neuronas de Procesamiento: Son aquellas neuronas que se encargan de transformar la información. Neuronas de Salida: Son las neuronas que se encargan de dar la respuesta al entorno. Tipos de Redes Neuronales Artificiales Las Redes Neuronales Artificiales se clasifican en: Redes Monocapa: Son aquellas Redes Neuronales en las que existe una única capa de neuronas que se encargan de las entradas, el procesamiento y la salida. Redes Multicapa: Son aquellas Redes Neuronales en las que existen varias capas que se encargan de la funcionalidad del sistema. Las capas que se pueden encontrar son: o Capa de Entrada (1 capa): Posee Neuronas de Entrada y se encarga de Interpretar las entradas recibidas desde el exterior. o Capas de Procesamiento (n capas): Se compone de Neuronas de Procesamiento. Pueden haber varias capas de éste tipo de neuronas. Son capas ocultas. o Capa de Salida (1 capa): Se compone de Neuronas de Salida. Esta capa se encarga de dar salida a la información procesada. Estado de Activación El Estado de Activación es un valor numérico que posee una neurona en un instante de tiempo dado. La actualización de los Valores de Estado de una Neurona puede ser: Asincrónica: Las Neuronas evalúan su estado continuamente según les llega la información y actualizan su Valor de Estado de forma independiente al resto de las Neuronas. Sincrónica: Si bien la información también llega de forma continua a las Neuronas, los cambios en los Valores de Estado se realizan simultáneamente en toda la Red Neuronal. Función de Activación o Transferencia La Función de Activación es la función que transforma el Estado de Activación en una señal de salida. Es decir que transforma la entrada neta de la neurona en una señal de salida. Página 39 de 42 Resumen de Inteligencia Artificial Los distintos tipos de Función de Activación que hay son: Escalón: Se usa para salidas binarias, es limitada pero fácil de implementar. Pueden adoptar valores 0 o 1; -1 o 1. Lineal Mixta: Combina una función lineal con una función escalón a partir de un determinado rango de valores que excede los límites preestablecidos de entrada. Monotónicas Asintóticas o Sismódicas: Son funciones continuas asintóticas. Campana de Gauss: La función sigue la curva de la campana de Gauss, y por ende es continua. La función de activación puede ser desfasada respecto del Eje Y, generando así un umbral de activación o desvío. Para ello, se introduce en la entrada neta NET como un peso negativo y se le asigna una entrada unitaria, tal como se muestra a continuación: NET w n i 1 ij Y w n i ij i 1 Yi Y w1 j w2 j wnj Y En donde : w j e Y 1 El tipo de Función de Activación a usar en una Red Neuronal Artificial depende de: El dominio del problema en cuestión. La salida a mostrar. El tipo de aprendizaje a implementar. Entrenamiento de las Redes Neuronales Artificiales El entrenamiento es someter a la red a los casos de prueba. Para cada caso de prueba se deben conocer las respuestas esperadas a fin de determinar si la red funciona de manera correcta o no. Mecanismos de Aprendizaje El aprendizaje es incorporar conocimiento nuevo. Esto permite modificar el comportamiento de la Red Neuronal para adaptarse a una situación que antes no podía. Mediante el aprendizaje se establecen y se ajustan los distintos valores wij (pesos) que llevará cada una de las entradas de de las neuronas. Los mecanismos de aprendizaje que podemos encontrar son los que se enumeran a continuación: Mecanismos de Aprendizaje Supervisado: Constantemente un ente externo controla que la Red Neuronal aprenda de forma correcta. Este a su vez puede ser: o On-Line: El Sistema se implementa en producción. Dentro de ésta categoría podemos encontrar los siguientes mecanismos: Adaptive Heuristic Critic: Emplea la heurística para aprender, aunque siempre de forma supervisada. o Off-Line: El Sistema toma muestras en tiempo de desarrollo (paro para poder entrenarlas). En este tipo de aprendizaje, los pesos de las conexiones permanecen fijos después de que termina la etapa de entrenamiento, por lo cual no presentan problemas de estabilidad en su funcionamiento. Dentro de ésta categoría podemos encontrar los siguientes mecanismos: Perceptrón: El aprendizaje se realiza por corrección de errores. La Red Neuronal puede ser multicapa o no. El umbral de desvío permanece constante, y lo que se varía son los pesos de las entradas reales. El algoritmo de aprendizaje es el siguiente: 1. Se calcula la salida real S R y se compara con la salida deseada S D . n n i 1 i 1 S R wi ei w0 e0 wi ei w0 1 En donde wi es el peso de la entrada e i y w0 es el peso del umbral de desvío. 2. Si coinciden, o sea que S R S D , el algoritmo finaliza. Si no coincide se calcula la variación del peso de cada entrada como se muestra a continuación. S i ei S D S R Página 40 de 42 Resumen de Inteligencia Artificial En donde es el Coeficiente de Aprendizaje. 3. Se actualizan los pesos de las entradas sumando algebraicamente la variación calculada en el paso anterior y se vuelve al paso 1. wi wi S i Back Propagation: Este algoritmo corrige el peso en base a lo que contribuyó Mecanismos de Aprendizaje No Supervisado: No existe un ente externo que controle el aprendizaje de la red. Este a su vez puede ser: o On-Line: El Sistema se implementa en producción. o Off-Line: El Sistema toma muestras en tiempo de desarrollo. En este tipo de aprendizaje, los pesos de las conexiones permanecen fijos después de que termina la etapa de entrenamiento, por lo cual no presentan problemas de estabilidad en su funcionamiento. Dentro de ésta categoría podemos encontrar los siguientes mecanismos: Hebbiano: Al algoritmo se le brindan todos los posibles elementos que se quieran reconocer, así ante una entrada se comparan los elementos conocidos para determinar qué elemento se ingresó, aún si éste no es idéntico. Para ello emplea un concepto de simbiosis entre celdas o elementos que le permite identificar elementos que no presenten la misma forma que cuando fueron aprendidos por la red. El algoritmo de aprendizaje, y su función reconocedora, es el siguiente: 1. Transformar cada uno de los elementos de entrada en matrices aplicándole la función signo. Son las denominadas Matrices de Hoppfield. v11 v1n Mi v n1 v nn 2. Transformar cada Matriz de Hoppfield en vectores. Vi v11 v1n vn1 vnn v11 v12 vnn 3. Calcular la Pseudomatriz de Aprendizaje Pi por cada vector según se muestra a continuación: Pi Vi ViT I Esto posibilita que cada elemento tenga simbiosis consigo mismo. 4. Obtener la Matriz de Pesos Finales o Matriz de Aprendizaje A sumando todas las Pseudomatrices de Aprendizaje Pi . k A Pi i 1 Cabe aclarar que el modelo sólo puede aprender la mitad o la mitad menos uno de elementos (el valor k ) respecto del total de posibilidades que brinda la matriz. 5. Operar con la red. Dado un elemento a reconocer, se transforma en vector aplicando la función signo. Ri r11 r12 rnn 6. Multiplicar el vector a reconocer por la Matriz de Aprendizaje A . T Ri A 7. Aplicarle la función signo al vector T . T sg T 8. Continuar iterando con los puntos 5, 6 y 7 hasta que el nuevo vector T coincida con el vector T de la iteración anterior. Página 41 de 42 Resumen de Inteligencia Artificial Cuadro Comparativo de las RNA RNA Tipo Conexión Cant. Capas Perceptron FeedForward (hacia adelante) 2 Back Propagation FeedForward (hacia adelante) N HoppField Laterales (se encuentra conectada a todas, pero no consigo misma) 1 Tipo Aprendizaje Supervisado Off-Line Corrección Error Supervisado Off-Line Corrección Error No Supervisado Off-Line Hebbiano Representación Info E/S Red Hibrida Entrada = continuo Salida = discreto Red Continua Entrada = analógica Salida = analógica Continuos HoppField Red Continua Discrete HoppField Red Discreta Cuadro Comparativo de Métodos de Aprendizaje On Line Supervisado Off Line Por Refuerzo: El supervisor es un crítico. Te dice si está bien o mal la Rta pero no dice cual sería la deseada No supervisado On Line y Off line Corrección de Error: El supervisor dice la salida deseada y se ajustan los pesos entre la salida deseada y la obtenida Hebbiano: ajuste de pesos segun la multiplicacion de las salidas de las neuronas conectadas Estocástico: Cambia los pesos en forma aleatoria Competitivo (se mide familiaridad) y Cooperativo (se clasifican los datos) Supervisado Por Refuerzo Corrección de Error Estocástico No Supervisado Hebbiano Competitivo Cooperativo Página 42 de 42