Inteligencia Inteligencia Artificial Artificial

Fco. Javier Alcalá Casado

Normas Normas de de la la asignatura asignatura ð La asignatura consta de una parte teórica y otra práctica. ð La parte teórica se evaluará con el correspondiente examen de teoría: 80% de la nota ð La parte práctica se realizará con el lenguaje de programación LISP: 20% de la nota. 0.8 * Teoría + 0.2 * Práctica ≥ 5.0 ð La no presentación de la práctica significa la renuncia a la parte correspondiente de la nota final.

Programa Programa ð Introducción histórica ð Lenguaje de programación LISP ð Paradigmas de representación del conocimiento ð Frames ð Sistemas de producción ð Paradigma lógico ð Exploración de espacios de estados. Búsqueda ð Exploración de árboles de juego ð Planificación ð Aprendizaje simbólico. ID3 ð Algoritmos genéticos

Bibliografía Bibliografía ð Serradilla, F.; Barros, B. Representación e Inferencia en Inteligencia Artificial. Un Enfoque Práctico. Escuela Universitaria de Informática, UPM. 1996. ð Russell, S, Norvig, P. Artificial Intelligence, a modern approach. Prentice-Hall. 1995. ð Barros, B; Foulquié, T; Serradilla, F. Programación Funcional en Lisp. Escuela Universitaria de Informática, UPM. 1992. ð Feigenbaum y otros. The Handbook of AI (4 volúmenes). Addison-Wesley. ð Luger, G. F. & Stubblefield, W. A. Artificial Intelligence: structures and strategies for complex problem solving. The Benjamin-Cummings Redwood City. 1993. ð Nilsson, Nilss J. Principios de Inteligencia Artificial. Díaz de Santos. 1987. ð Rich, E. Inteligencia Artificial. Mac Graw-Hill. 1991. ð Winston, P. H. Inteligencia Artificial. 3ª ed. Addison-Wesley. 1992. ð Winston, P. H. Lisp. Addison-Wesley. 1993.

Introducción Introducción histórica histórica

Fco. Javier Alcalá Casado

Introducción Introducción histórica histórica ð El problema de la inteligencia ð Objetivos de la inteligencia artificial (IA) ð Historia û û û û û û

Rama lógico-matemática Rama de la psicología Rama de la informática Conferencia de Darmouth Rama de la simulación Panorama actual

ð Los primeros sistemas ð Áreas de estudio

El El problema problema de de la la inteligencia inteligencia ð El principal problema de la inteligencia natural es que no tiene una fácil definición ð Hofstadter (1987): Inteligencia es la habilidad para û responder flexiblemente a diferentes situaciones, û saber aprovechar circunstancias fortuitas, û dar sentido a mensajes ambiguos o contradictorios, û encontrar similitudes entre situaciones diferentes, y û generar nuevos conceptos e ideas innovadoras

El El problema problema de de la la inteligencia inteligencia (II) (II) ð La inteligencia artificial trata de “imitar” a la inteligencia natural. ¿Cómo definirla?

Eficiencia humana

Racionalidad

Procesos mentales y razonamiento

Sistemas que piensan como humanos (Bellman)

Sistemas que piensan racionalmente (Winston)

Conducta

Sistemas que actúan como humanos (Minsky)

Sistemas que actúan racionalmente (Luger)

El El problema problema de de la la inteligencia inteligencia (III) (III) ð Bellman (1978): IA es la automatización de actividades que vinculamos con procesos del pensamiento humano, actividades tales como toma de decisiones, resolución de problemas, aprendizaje... ð Winston (1992): La IA se ocupa del estudio de las computaciones que permiten percibir, razonar y actuar ð Minsky (1986): IA es el arte de construir máquinas capaces de hacer cosas que requerirían inteligencia en caso de que fuesen hechas por los seres humanos ð Luger (1989): IA es la rama de la informática que trata de la automatización del comportamiento inteligente

Test Test de de Turing Turing ð Turing (1950) dio una definición empírica: el juego de la imitación. ð Test de Turing:

¿Puede saber el hombre de fuera en qué habitación está la máquina?

Test Test de de Turing Turing (II) (II) ð Para superar el test de Turing, una máquina debería ser capaz de: û procesar lenguaje natural: para poder establecer una comunicación satisfactoria û representar el conocimiento: para guardar toda la información recibida antes o durante el interrogatorio û razonar automáticamente: para utilizar esa información al responder a las preguntas y obtener conclusiones û autoaprendizaje de la máquina: para adaptarse a nuevas situaciones y detectar y extrapolar esquemas determinados

ð Test total de Turing: También imita físicamente. Necesita: û Percepción: Visión artificial, reconocimiento del habla… û Robótica: Habilidades para andar, saltar, subir escaleras…

Objetivos Objetivos de de la la inteligencia inteligencia artificial artificial ð La IA es una ciencia multidisciplinar: matemáticas, filosofía, psicología e ingeniería ð Objetivos de ingeniería: desarrollo de sistemas inteligentes mejorando otros anteriores para los que no existe un método algorítmico ð Objetivos científicos: comprender mejor el funcionamiento de la inteligencia, tanto en el hombre como en las máquinas (filosofía, psicología) û ¿Es la inteligencia independiente del hardware? û ¿Cómo se interrelacionan las estructuras mentales? û ¿Qué reglas las gobiernan?

Historia Historia ð La IA es el punto de encuentro de varias líneas de investigación û Rama lógico-matemática û Rama de la psicología û Rama de la informática û Conferencia de Darmouth û Rama de la simulación û Panorama actual

Rama Rama lógico-matemática lógico-matemática ð Mecanización de los procesos de razonamiento desde el punto de vista de la manipulación de símbolos lógicos ð Hitos importantes: û El primer esfuerzo de mecanización del pensamiento fueron los silogismos de Aristóteles. û Leibniz construye el primer sistema axiomático de lógica formal (cálculo de predicados) û Euler formaliza la Teoría de Grafos û Hilbert intentó encontrar un conjunto de axiomas y un sistema formal que sintetizasen toda la matemática Gödel, con el teorema de incompletitud, demostró que no era posible

Rama Rama de de la la psicología psicología ð Estudia los fundamentos de la inteligencia en el hombre ð Hitos importantes û Dualismo mente/cuerpo de Descartes. La mente constituye una entidad independiente del cuerpo y puede estudiarse por separado û Los primeros psicólogos (James, Wundt) estudiaron el pensamiento con una metodología basada en la introspección (subjetiva, poco científica) û Los conductistas (Skinner) consideran a la mente como una caja negra capaz de asociar estímulos con respuestas û La psicología cognitiva (Chomsky, Fodor) es el paradigma más aceptado

Rama Rama de de la la psicología psicología (II) (II) ð Características de la psicología cognitiva: û Estructuralista: los modelos de la conducta se explican por estructuras abstractas û Los estímulos son procesados por el organismo para producir respuestas (no conductista) û Mentalismo: la mente utiliza representaciones simbólicas de los conceptos y los procesos mentales manipulan los símbolos û Paradigma del procesamiento de la información: la mente funciona como un ordenador; los programas son teorías psicológicas û Memoria semántica, modelo de memoria asociativa: los conceptos se representan por símbolos interrelacionados (redes semánticas) û Modularidad: los procesos mentales son afrontados por módulos débilmente acoplados

Rama Rama de de la la psicología psicología (III) (III) û Isomorfismo. Hofstadter: “Dos sistemas son isomórficos cuando se puede encontrar un conjunto de reglas que traduzca o identifique estados de cualquiera de ellos en estados del otro.”

Objeto

∈

Mundo

Representación

∈

Mente

Conexiones

∈

Cerebro

Rama Rama de de la la informática informática ð Inteligencia artificial ⇒ inteligencia + artefacto El ordenador se reconoce como el artefacto con mayor posibilidad de manifestar inteligencia ð Hitos importantes û Charles Babbage (principio siglo XIX) diseñó la primera máquina capaz de desarrollar cálculos automáticos û Junto con Ada Lovelace diseñó la máquina analítica de propósito general introduciendo conceptos como la memoria, procesador, programas almacenados, saltos condicionales, etc. û Alan Turing (1937) propone la máquina de Turing. Cualquier procedimiento matemático puede desarrollarse con dicha máquina con una tabla de instrucciones adecuada

Rama Rama de de la la informática informática (II) (II) û La Cibernética o Teoría de Sistemas (Wiener) puede aplicarse a sistemas biológicos, sociales y artificiales. Se basa en la retroalimentación negativa

Objetivo + -

Error

CONTROL

Medida

Actuación

SENSOR

SISTEMA

Comportamiento

Objeciones Objeciones de de Turing Turing ð En 1950, Turing publica Maquinaria de computación e inteligencia. Propone el test de Turing, defiende la posibilidad de construir máquinas que piensen y enumera las posibles objeciones contra estas máquinas: û Teológicas: la mente no reside en el cuerpo sino en el alma. Si se admite el dualismo, se niega la psicología No es científica û Del avestruz: si las máquinas pensaran, las consecuencias serían desastrosas; luego esto no puede ocurrir Sin comentarios û Matemáticas: el teorema de incompletitud de Gödel demuestra que en un sistema formal suficientemente complejo existen proposiciones indecidibles La mente humana no supera esta limitación

Objeciones Objeciones de de Turing Turing ð Más objeciones: û De conciencia: las máquinas no saben lo que están haciendo cuando trabajan. Minsky ⇒ los tres estados de conciencia de un termostato û De las diversas incapacidades: una máquina nunca podrá ser afectuosa, ingeniosa, amistosa, tener iniciativa... Ahora no, pero sí podría en el futuro û Objeción de Lady Lovelace: una máquina sólo realiza lo que sabemos cómo ordenarle que haga Se le puede ordenar que sea inteligente

Objeciones Objeciones de de Turing Turing (II) (II) ð Más objeciones: û Continuidad del sistema nervioso: una máquina de estados discretos no puede emular al hombre La discretización no supone limitaciones û Basadas en la informalidad de la conducta: el hombre no tiene un conjunto de reglas para regir su vida y las máquinas funcionan con reglas Las neuronas presentan un comportamiento rígido y de ellas surge comportamiento flexible inteligente û Basado en la percepción extrasensorial: Test de Turing extrasensorial No científica

Conferencia Conferencia de de Darmouth Darmouth ð Tuvo lugar en 1956 ð Todas las ramas anteriores confluyen en una nueva disciplina, agrupando a psicólogos, matemáticos, informáticos, neurólogos e ingenieros eléctricos ð John McCarthy acuña el término de Inteligencia Artificial ð Esta rama unificada de psicólogos cognitivos, lógico-matemáticos y computación simbólica se denomina IA clásica o IA simbólica

Rama Rama de de la la simulación simulación ð También llamada IA conexionista Desarrolla sistemas inteligentes imitando sistemas biológicos con comportamiento inteligente (animales o seres humanos) ð Su objetivo es construir cerebros artificiales formalmente similares a los cerebros biológicos para dotarles de aprendizaje ð Hitos importantes: û Células de McCulloch y Pitts (1943). Emulación de neuronas con circuitos eléctricos û Perceptrón (Rosenblatt, 1958). Mecanismo de aprendizaje mediante ajuste automático de las conexiones de una red de neuronas û Perceptrón multicapa (Rumelhart, Hinton y Williams, 1986). Generalización del perceptrón û Algoritmos Genéticos (Friedberg, 1958). Basados en la teoría evolucionista de Darwin

Panorama Panorama actual actual ð IA clásica + Rama de la Simulación = Ciencia Cognitiva ð Su objetivo es el estudio de los “objetos con mente” y los procesos implicados en el pensamiento ð Cuestiones abiertas: û Objeciones al Test de Turing, orientado a resolución de problemas, olvidando la percepción, el aprendizaje y la destreza û Objeciones de la Habitación china

Reglas Símbolos

¿Sabe chino el hombre de la habitación?

Panorama Panorama actual actual (II) (II) ð Más cuestiones abiertas: û Mezcla de técnicas de IA clásica con técnicas de la rama de simulación û Importancia creciente del aprendizaje û Problema de los problemas de juguete û Evolución desde los objetivos científicos a los ingenieriles û Con ordenadores más potentes se consideran métodos que antes se desechaban û Herbert Simon: la complejidad demostrada por seres vivos se debe a la complejidad del medio con el que interactúan más que a la complejidad interna de sus “programas” ⇒ ⇒ Vida artificial

Los Los primeros primeros sistemas sistemas ð Logic Theorist. Demostración automática de teoremas. Primer programa que utilizó símbolos en lugar de cantidades numéricas ð DENDRAL. Primer sistema experto para análisis de datos de espectografía de masas (isótopos) ð SHRDLU. Comprensión del lenguaje natural y planificación de tareas ð Turochamp. Primer programa de ajedrez ð Programa de damas de Samuel. Primer programa que incorpora aprendizaje ð MYCIN. Sistema experto sobre infecciones bacterianas en sangre. Introduce el grado de certeza ð PROSPECTOR. Sistema experto sobre búsqueda de yacimientos minerales

Áreas Áreas de de estudio estudio ð La IA está en continua evolución. Áreas más relevantes: û Representación del conocimiento: Modeliza el conocimiento en estructuras de datos adecuadas û Exploración del espacio de estados: Busca soluciones en problemas modelizados con grafos û Heurística: Conocimiento intuitivo. Atajos entre el estado actual y la solución û Resolución de problemas: Planificación de tareas û Demostración de teoremas: Programación lógica û Teoría de juegos: Estrategias de búsqueda (ajedrez) û Ingeniería del conocimiento (Sistemas Expertos): Requieren de la ayuda de un experto humano

Áreas Áreas de de estudio estudio ð Más áreas de estudio: û Diagnóstico: Establece hipótesis sobre el mal funcionamiento de un sistema û Aprendizaje: Refina el conocimiento inicial para hacerlo más operativo û Comprensión del lenguaje natural (y traducción automática): û Percepción computacional (reconocimiento de patrones): interpreta la información sensorial û Simulación de procesos psicológicos humanos: Estudia la inteligencia humana mediante procesos de simulación û Sistemas multiagente: Coordinación de la conducta inteligente entre un conjunto de agentes autónomos y heterogéneos

Lenguaje Lenguaje de de Programación Programación LISP LISP

Fco. Javier Alcalá Casado

Marco Marco histórico histórico ð McCarthy lo creó en 1958 ð Se creó para procesar de listas en un proyecto de IA ð La primera versión consumía mucha memoria (recurso caro) ð Se crearon varias versiones: FRANZLISP, ZETALISP, MULISP, XLISP, LELISP, SCHEME... ð Con el avance del hardware se solucionó el problema de la memoria y surgió el estándar actual: COMMON LISP

Características Características de de LISP LISP ð Lenguaje funcional. Utiliza las propiedades matemáticas de las funciones ð Simbólico. Utiliza el símbolo como unidad fundamental ð Procesamiento de listas (LISt Procesing) ð Flexibilidad û û û û

Utiliza la misma estructura para datos y código Paso de funciones como parámetro (reusabilidad) Autodefinición del lenguaje (entorno a la medida) Estructura de datos muy flexible (Garbage collector)

ð Recursividad. Definiciones muy claras y concisas ð Interpretado. Desarrollo rápido de prototipos ð Compacto: funcional + recursivo + listas

Lenguajes Lenguajes funcionales funcionales ð La primitiva básica es la función ð Una función es una regla de correspondencia entre miembros de un dominio y miembros de un rango ð Un programa es un conjunto de funciones que se llaman unas a otras y se pasan los datos en las llamadas ð Una ventaja importante es la recursividad ð La asignación está definida y se utiliza; a pesar de ser considerado un lenguaje sin asignación

Componentes Componentes de de LISP LISP ð Conjunto de objetos o datos. Estructura fundamental: lista ð Funciones primitivas. Aquéllas aportadas inicialmente por el lenguaje ð Operación de aplicación (read-eval-print loop). Primitiva encargada de gestionar y realizar el proceso de interpretación: lectura-escritura-devolución de resultados ð Formas funcionales (DEFUN). Funciones definidas por el programador que pasan a formar parte del lenguaje como una primitiva más ð Operadores aplicativos. Funciones cuyos parámetros son otra función y los argumentos de esta otra función

Campos Campos de de aplicación. aplicación. Funcionalidad Funcionalidad ð Campos de aplicación: û Inteligencia Artificial û Entornos gráficos

ð Funcionalidad: û No se deben utilizar variables globales dentro de funciones. Atenta contra la reusabilidad y la claridad del programa. En su lugar, se utilizan variables locales o paso de parámetros û No se deben utilizar estructuras iterativas, sino recursividad

Paradigmas Paradigmas de de Representación Representación del del Conocimiento Conocimiento

Fco. Javier Alcalá Casado

Paradigmas Paradigmas de de representación representación del del conocimiento conocimiento ð Computación sobre representaciones ð Tipos de conocimiento ð Uso del conocimiento ð Tipos de razonamiento ð Tipos clásicos de representación: û Frames (marcos) û Sistemas de producción û Paradigma lógico û Exploración de espacios de estados

Computación Computación sobre sobre representaciones representaciones ð Una estructura de datos no representa conocimiento. Es necesario establecer mecanismos para acceder y relacionar distintas partes del conocimiento ð Un sistema inteligente se divide en: û representaciones del conocimiento y û computaciones sobre estas representaciones

⇒ Paradigma C-R ð Se independiza el proceso de resolución del problema, inferencia, de la naturaleza del mismo

Computación Computación sobre sobre representaciones representaciones (II) (II)

Problema

Modelización

Representación

Inferencia

Solución

Explicación

Tipos Tipos de de conocimiento conocimiento ð Objetos. Conceptos con entidad propia ð Eventos. Especifican sucesos en el tiempo ð Reglas de inferencia. Indican cómo obtener nuevo conocimiento a partir del que ya tiene el sistema ð Conocimiento procedural. Indica la manera de realizar determinadas cosas. Son las computaciones sobre las representaciones. El cómo ð Metaconocimiento. Conocimiento a nivel más abstracto. Da una idea de cuál es la mejor manera de resolver un problema ð Conocimiento declarativo. Representa los conceptos que intervienen en el problema. Hechos, reglas y metaconocimiento. El qué

Ejemplo Ejemplo del del Metro Metro ð Definir un sistema que permita calcular el camino más corto entre dos estaciones: û Objetos: las estaciones û Eventos: las horas a las que pasan los trenes û Reglas de inferencia: determinan a qué estaciones puedo pasar a partir de una dada û Conocimiento procedural: cómo encontrar un camino entre dos estaciones û Metaconocimiento: para encontrar un camino debo buscar explorando hacia la estación destino

Uso Uso del del conocimiento conocimiento ð Problemas que se plantean con el uso del conocimiento: û Adquisición. Los modelos de representación deben ser capaces de recoger nueva información para que se integre con la adquirida anteriormente, completándola o actualizándola û Recuperación. El acceso a parte del conocimiento debe ser sencilla y eficiente. La memoria asociativa humana relaciona información con un contexto û Razonamiento. Permite obtener nuevo conocimiento a partir del que ya se tiene. Este conocimiento está implícito, pero es de difícil obtención

Tipos Tipos de de razonamiento razonamiento ð Formal. Deduce, con reglas de inferencia, estructuras de datos manipulando sintácticamente otras estructuras (gramáticas generativas) ð Procedural. Razonamiento mediante la ejecución de determinados algoritmos ð Por analogía. Razonamiento por semejanza. Frecuente en los humanos ð Generalización y abstracción. Proceso de obtención de conocimiento más refinado a partir de otro más simple

Tipos Tipos clásicos clásicos de de representación representación ð La representación se divide en dos partes: conocimiento declarativo e inferencia o conocimiento procedural ð Conocimiento declarativo (K). Representa objetos y conceptos que intervienen en el problema. Es dependiente del problema û Hechos (H): cosas ciertas en un momento dado. Constituyen la memoria de trabajo (a corto plazo) û Reglas (R): conocimiento a largo plazo. Permiten obtener nuevo conocimiento a partir del que ya se tiene û Metaconocimiento (M): ayuda a la inferencia a manipular las reglas para obtener un hecho concreto

Tipos Tipos clásicos clásicos de de representación representación (II) (II) ð Inferencia o conocimiento procedural (I): Representa el modo de obtener nuevo conocimiento a partir del que ya se tiene en un instante dado. Es independiente del problema ð Paradigmas clásicos de representación û Frames (marcos) Ÿ H: Valores de atributos Ÿ R: Herencia y demonios Ÿ I: Funciones de manipulación, equiparación

û Sistemas de producción Ÿ Ÿ Ÿ Ÿ

H: Ternas objeto-atributo-valor R: Reglas de producción M: Parámetros, metarreglas I: Encadenamiento de reglas

Tipos Tipos clásicos clásicos de de representación representación (III) (III) û Paradigma lógico Ÿ K (H y R): Cálculo de predicados, reglas lógicas, cláusulas de Horn Ÿ I: Unificación, resolución

û Exploración de espacios de estados Ÿ Ÿ Ÿ Ÿ

H: Estados R: Transiciones de estado M: Funciones heurísticas I: Algoritmos de búsqueda

Sistemas Sistemas de de Producción Producción

Fco. Javier Alcalá Casado

Sistemas Sistemas de de Producción Producción ð Introducción ð Hechos ð Reglas ð Metaconocimiento ð Motor de Inferencia ð Módulo de explicación

Introducción Introducción ð En los sistemas de producción se representa el conocimiento mediante hechos, reglas de producción y metaconocimiento.

Hechos Motor de Inferencia Reglas

Metaconocimiento

Módulo de Explicación

Introducción Introducción (II) (II) ð Base de hechos: conjunto de todos los hechos ð Base de reglas: conjunto de todas las reglas ð El metaconocimiento establece criterios para aplicar las reglas ð El motor de inferencia permite obtener nueva información a partir de la inicial ð El módulo de explicación justifica las conclusiones que se han obtenido.

Hechos Hechos ð Los hechos se representan por ternas Objeto-Atributo-Valor (, , ) ð Ejemplos: û (rayo, es-un, caballo) û (veloz, es-un, caballo) û (cometa, es-un, caballo) û (rayo, valioso, sí) û (veloz, hijo-de, cometa) û (cometa, rápido, sí)

Reglas Reglas ð Tienen el siguiente formato: IF THEN



Antecedente Consecuente

ð Una terna en el antecedente es cierta sólo si existe en la base de hechos ð Si se aplica la regla, se ejecutan todas las acciones del consecuente, que pueden ser nuevas ternas o llamadas a función ð R1: IF (X, es-un, caballo) AND (X, hijo-de, Y) AND (Y, es-un, caballo) AND (Y, rápido, sí) THEN (X, valioso, sí)

Metaconocimiento Metaconocimiento ð El metaconocimiento ayuda a determinar qué regla se aplica cuando hay varias aplicables ð Criterios de aplicación de reglas: û La primera regla de la base de reglas û Azar û La más específica (con más elementos en el antecedente) û La más genérica (con menos elementos en el antecedente) û La más recientemente utilizada û La menos recientemente utilizada û La que añada más información (con más elementos en el consecuente) û Todas

Metaconocimiento Metaconocimiento (II) (II) ð Si tras aplicar todos los criterios, sigue habiendo varias posibilidades, se elige la primera regla en orden de aparición ð Las metarreglas son reglas que expresan cuándo debemos dar preferencia a una regla concreta Ejemplo: Si la consulta es sobre gripe, entonces dar preferencia a las reglas R3 y R4

Motor Motor de de Inferencia Inferencia ð Repetir û Establecer el conjunto conflicto (CC). Se obtienen todas las reglas cuyo antecedente se equipara con los elementos de la base de hechos y se especifica una lista de pares (regla, sustitución) û Seleccionar un único par (regla, sustitución) con los criterios establecidos por el metaconocimiento û Disparar la regla seleccionada. Se aplica la sustitución y se añaden a la base de hechos las ternas del consecuente. Si ya existe el atributo del objeto en alguna terna del CC, se actualiza su valor para evitar inconsistencias

Hasta que el hecho buscado esté en la base de hechos o la base de hechos no haya cambiado

Módulo Módulo de de explicación explicación ð Se encarga de dar una justificación a posteriori de las conclusiones a las que ha llegado el sistema ð Se guarda una traza para saber qué reglas y en qué orden se han utilizado, así como los hechos que permitían utilizarlas y las conclusiones intermedias

Frames Frames

Fco. Javier Alcalá Casado

Frames Frames ð Introducción ð Estructura de un frame ð Herencia ð Demonios ð Tipos de facets ð Representación en LISP ð Funciones de manipulación de frames ð Inferencia en frames

Introducción Introducción ð Un frame es una estructura activa de almacenamiento de información ð Utiliza mecanismos para buscar automáticamente un dato si éste no se encuentra en el propio frame Estos mecanismos son: û Herencia: mediante una relación de jerarquía, busca el dato solicitado en otros frames û Demonios (o valores activos): son funciones que son llamadas automáticamente cuando se hace referencia a ciertos datos

ð Un frame se puede relacionar con otro con relaciones de pertenencia, inclusión o de usuario

Estructura Estructura de de un un frame frame ð Un frame es una estructura con compartimentos en los que se guarda la información. Representa un objeto ð Se compone de: û Atributos (slots): cada uno de los compartimentos û Valores: el contenido del compartimento û Facetas (facets): indica cómo se puede utilizar el conocimiento del slot

Pedro ES-UN Profesión Altura

Value

Hombre

Default

Pintor

Value

180

Herencia Herencia ð Si A tiene una relación de instancia o de subclase con B, los atributos de A que no tengan ningún valor lo toman de los que tengan esos mismos atributos en B ð Una relación de instancia se define a través del atributo IS-A (ES-UN). Su valor será el nombre del frame del que hereda ð Una relación de subclase se define a través del atributo AKO (a kind of) ð En una cadena de herencia puede haber varios atributos AKO, pero sólo uno IS-A

Demonios Demonios ð Los demonios o valores activos son funciones que se disparan automáticamente cuando se almacenan o se recuperan datos en un frame ð Un demonio tiene dos parámetros: frame y slot ð IF-NEEDED se dispara al intentar recuperar el valor de un atributo que no tiene ningún valor asociado. Proporciona la información requerida ejecutando un algoritmo û El demonio ASK pregunta al usuario el valor de un atributo

ð IF-ADDED se dispara después de asignar un valor a un atributo

Tipos Tipos de de facets facets ð Un sistema básico dispone de los siguientes facets: û Value: el contenido del slot es un valor literal û Default: el contenido del slot es un valor por defecto (sólo se devuelve si no está definido el facet Value) û Range: indica el rango de valores válidos para el slot û IF-ADDED: el contenido del slot es un demonio IF-ADDED û IF-NEEDED: el contenido del slot es un demonio IF-NEEDED

Representación Representación en en LISP LISP ð Hay dos maneras: û Representación muy eficiente pero incómoda de manipular: ( Frame1 Frame2 ... FrameN ) donde cada Frame-i es ( Slot1 ... SlotN ) donde cada Slot-i es ( Facet1 ... FacetN ) donde cada Facet-i es ( ) û Representación muy sencilla de manipular pero menos eficiente: ( E1 E2 ... EN) donde cada Ei es un par ( ( ) )

Funciones Funciones de de manipulación manipulación de de frames frames ð FPUT permite añadir información al sistema ( FPUT Frame Slot Valor &OPTIONAL (Facet ‘value) )

ð FGET permite recuperarla ( FGET Frame Slot &OPTIONAL (Origen Frame) (Is-a T) )

ð FFIND encuentra los frames que mejor se equiparan con ciertas restricciones ( FFIND ( Slot1 Valor1 ) ( Slot2 Valor2 ) ... ( SlotN ValorN ) )

Inferencia Inferencia en en frames frames ð La inferencia en frames se realiza de distintas maneras: û Con los valores por defecto û A través de la herencia, cuando se solicita un valor que no está en el frame, pero sí en sus antecesores û A través de los demonios, cuando se disparan procedimientos para calcular el valor solicitado û A través de la equiparación, cuando se busca en la base de frames con FFIND

Paradigma Paradigma lógico lógico

Fco. Javier Alcalá Casado

Paradigma Paradigma lógico lógico

ð Introducción

ð Unificación de predicados

ð Encadenamiento de reglas dirigido por el objetivo

Introducción Introducción ð Procesamiento realizado por el lenguaje de programación PROLOG ð Representación basada en: û Términos: variables (A, B, X), constantes (juan, 2, caballo) y funciones cuyos argumentos son términos (f(x), padre(juan)) û Predicados: símbolos de n argumentos (que son términos) que toman valor verdadero o falso caballo(X), valioso(veloz), es-padre(veloz, padre(cometa)) û Cláusulas de Horn: hechos o reglas formadas por varios antecedentes (conjunción) y un consecuente consecuente :- antecedente1, antecedente2 ... La disyunción se representa añadiendo reglas

Unificación Unificación de de predicados predicados ð La unificación es un proceso por el cual se transforman dos expresiones lógicas para hacerlas idénticas No siempre es posible realizarla ð Algoritmo para unificar dos predicados: û Los símbolos de los predicados han de ser iguales y con el mismo número de argumentos. Si no se termina con FALLO û Por cada término de ambos predicados puede suceder: Ÿ Si un término es una variable y el otro es cualquier término que no contenga a esa variable, se sustituye la variable por el término Ÿ Si los dos términos son constantes con el mismo valor, ya están unificados. Si el valor es distinto se termina con FALLO Ÿ Si los términos son funciones, deberán llamarse igual y tener el mismo número de argumentos. Se aplica recursivamente el algoritmo a los argumentos de la función Ÿ Si no se cumple ningún caso, se termina con FALLO

Ejemplos Ejemplos de de unificación unificación de de predicados predicados ð Unificar: û {tos(X), tos(juan)} ⇒ û {amigo(X,Y), amigo(andres,julio)} ⇒ û {colocado(X,Y,atras), colocado(X,grande,X)} ⇒ û {B(a,g(X,b),Y), B(Z,g(c,b),d)} ⇒ û {A(X,g(Y)), A(c,Y)} ⇒ FALLO û {A(X,g(Y)), A(c,Z)} ⇒

Encadenamiento Encadenamiento de de reglas reglas dirigido dirigido por por el el objetivo objetivo 1. Se parte de una lista L de objetivos O1 O2 ... On 2. Selección 2.1 Seleccionar un objetivo Oi por orden de aparición 2.2 Seleccionar una cláusula Rj por orden de aparición. Renombrar sus variables. Si el consecuente de Rj puede unificarse con Oi, se crea una nueva rama realizando las sustituciones necesarias; si no se puede unificar ⇒ la rama termina en FRACASO 3. Resolución: Oi se sustituye en L por el antecedente de Rj . A todas las cláusulas de L se les aplica las sustituciones de la unificación 4. Si L vacía ⇒ la rama termina en ÉXITO si no, volver al paso 2 El algoritmo termina cuando se han recorrido todas las ramas

Métodos Métodos de de Exploración Exploración en en Espacios Espacios de de Estados Estados

Fco. Javier Alcalá Casado

Métodos Métodos de de exploración exploración en en espacios espacios de de estados estados ð Introducción ð Algoritmos de búsqueda û Expansión de un camino û Esquema básico de un algoritmo de búsqueda û Método de escalada û Primero el mejor û Algoritmo A*

ð Representación en árbol

Introducción Introducción ð La exploración de espacios de estados es una de las técnicas más importantes en IA ð Se manejan estados (hechos del problema), transiciones (reglas) y funciones heurísticas (metaconocimiento). La inferencia se realiza a través de algoritmos de búsqueda ð Un estado es cada configuración posible de un problema. Se representan con estructuras de datos. Ej: Problema del Metro ⇒ estado: “estar en la estación X” û Los sucesores son los estados que se pueden alcanzar en un único paso desde un estado. Son el resultado de una transición de estado Ej: Metro ⇒ sucesores: “estaciones consecutivas”

Introducción Introducción (II) (II) ð Una transición permite obtener una lista de estados a los que se llega desde un estado previo tras la aplicación de operaciones definidas en el dominio del problema. Se describe con un algoritmo y puede tener un coste asociado. Ej: Metro ⇒ coste: “tiempo medio entre estaciones” ð Una función heurística o heurístico es una función matemática que devuelve un valor numérico menor cuanto más cerca está un estado cualquiera del estado objetivo. El valor no tiene por qué ser exacto. Ej: Metro ⇒ función: “distancia euclídea entre estaciones”

Introducción Introducción (III) (III) ð Elementos a definir para la exploración de espacios de estados: û Una estructura de datos para los estados û Operaciones aplicables a un estado para obtener nuevos estados (y un coste asociado, si es preciso) û Una función heurística que devuelva la proximidad entre un estado cualquiera y el estado objetivo û Una función que determine si un estado X es o no un estado solución

Algoritmos Algoritmos de de búsqueda búsqueda ð Un algoritmo de búsqueda permite encontrar, desde un estado inicial, una secuencia de estados hasta alcanzar el estado objetivo. ð Cada estado intermedio es consecuencia de aplicar una regla de transición al estado precedente ð Se llama camino a una secuencia de estados que lleva de un estado a otro û Camino solución es el que va desde el estado inicial hasta el estado objetivo û Camino parcial es el que va desde el estado inicial hasta un estado que no es solución (estado actual)

Expansión Expansión de de un un camino camino ð La expansión de un camino C resulta de añadir a C cada uno de los nuevos estados alcanzables desde el último estado de C. Se excluyen los caminos cíclicos, es decir, los que llegan a un nodo que ya está incluido en C ð EXPANDIR ( C ) û Calcular los sucesores del último estado de C utilizando reglas de transición û Inicializar R = { } û Para cada sucesor Ei que no esté en C Añadir a la lista R un nuevo camino, obtenido de añadir a C el estado Ei

û Devolver R

Expansión Expansión de de un un camino camino (II) (II) C A

E

B

ð Camino = (A B D)

D

ð EXPANDIR ( Camino ) Sucesores: B, C, E, F R={} R = { (A B D C) } R = { (A B D C), (A B D E) } R = { (A B D C), (A B D E), (A B D F) }

ð En LISP, las listas se crean a la inversa

F

Esquema Esquema básico básico de de un un algoritmo algoritmo de de búsqueda búsqueda BUSCAR ( INICIO OBJETIVO HEURISTICO COSTE ) 1. Formar la lista CP de caminos pendientes (lista de posibles caminos solución). Inicialmente CP contiene el estado INICIO 2. Mientras CP ≠ { } y estado actual del primer camino ≠ OBJETIVO Ÿ Expandir primer camino obteniendo una nueva lista E Ÿ Quitar de CP el primer camino Ÿ Formar una nueva lista CP combinando CP y E y la información de HEURISTICO y COSTE 3. Si CP = { }, devolver FALLO en caso contrario, devolver como solución el primer camino

Método Método de de escalada escalada ESCALADA ( INICIO OBJETIVO HEURISTICO ) 1. Formar la lista CP de caminos pendientes (lista de posibles caminos solución). Inicialmente CP contiene el estado INICIO 2. Mientras CP ≠ { } y estado actual del primer camino ≠ OBJETIVO Ÿ Expandir primer camino obteniendo una nueva lista E Ÿ Quitar de CP el primer camino Ÿ Ordenar E de menor a mayor según el valor devuelto por HEURISTICO Ÿ Añadir E por delante a la lista CP 3. Si CP = { }, devolver FALLO en caso contrario, devolver como solución el primer camino ð Se da prioridad a los nuevos caminos más prometedores

Representación Representación en en árbol árbol ð Se coloca en la raíz el estado inicial ð Por cada estado seleccionado se indica en el árbol el número de iteración con un recuadro y se añaden sus descendientes (expansión) ð Se selecciona el siguiente nodo a expandir según el algoritmo de exploración que se esté utilizando ð Junto a cada nodo se anota el valor de la función heurística (para escalada y “primero el mejor”) o de la función de estimación (para A*). En el A* se señalan también las “podas” realizadas por la programación dinámica (PD)

Problemas Problemas del del método método de de escalada escalada ð Sensible a mínimos locales: un mínimo local se produce cuando estando en un estado la función heurística se hace mínima localmente. Esto lleva a caminos que no conducen a la solución o a caminos más largos ð Mesetas: se produce cuando la función heurística toma valores similares en todos los caminos pendientes. El progreso hacia la solución es lento ð Importancia del heurístico: un buen heurístico debe dar valores bajos cuando el estado actual esté cerca de la solución. Un heurístico ideal nos guiaría hacia la solución con un coste computacional mínimo y con el menor número de nodos

Primero Primero el el mejor mejor PRIMERO_EL_MEJOR ( INICIO OBJETIVO HEURISTICO ) 1. Formar la lista CP de caminos pendientes (lista de posibles caminos solución). Inicialmente CP contiene el estado INICIO 2. Mientras CP ≠ { } y estado actual del primer camino ≠ OBJETIVO Ÿ Expandir primer camino obteniendo una nueva lista E Ÿ Quitar de CP el primer camino Ÿ Añadir E por detrás a la lista CP Ÿ Ordenar la nueva lista CP de menor a mayor según el valor devuelto por HEURISTICO 3. Si CP = { }, devolver FALLO en caso contrario, devolver como solución el primer camino ð La ordenación se realiza en todos los caminos pendientes ð Da mejores resultados que el método de “escalada” con mayor carga computacional

Algoritmo Algoritmo A* A* ð A* encuentra la solución óptima siempre que la función heurística cumpla la condición de minorancia: h(e) ≤ h*(e)

∀e

h(e) valor del heurístico en el estado e h*(e) coste real del menor camino desde e hasta el estado solución La distancia euclídea cumple la condición de minorancia

ð Utiliza dos nuevos elementos: û Programación dinámica: si hay dos caminos que llegan al mismo nodo, se eliminan los de mayor coste û Función de estimación:

f(c) = g(c) + h(c)

g(c) coste acumulado desde el inicio hasta el estado actual h(c) valor del heurístico desde el estado actual hasta el objetivo f(c) estimación del coste total que tendrá el camino solución

Algoritmo Algoritmo A* A* (II) (II) A* ( INICIO OBJETIVO HEURISTICO COSTE ) 1. Formar la lista CP de caminos pendientes (lista de posibles caminos solución). Inicialmente CP contiene el estado INICIO 2. Mientras CP ≠ { } y estado actual del primer camino ≠ OBJETIVO Ÿ Expandir primer camino obteniendo una nueva lista E Ÿ Quitar de CP el primer camino Ÿ Añadir E por detrás a la lista CP Ÿ Ordenar la nueva lista CP de menor a mayor según la función de estimación (HEURISTICO + COSTE acumulado) Ÿ Aplicar programación dinámica: si hay dos caminos que llegan al mismo nodo, se elimina el de mayor coste 3. Si CP = { }, devolver FALLO en caso contrario, devolver como solución el primer camino

Exploración Exploración de de Árboles Árboles de de Juegos Juegos

Fco. Javier Alcalá Casado

Exploración Exploración de de árboles árboles de de juego juego ð Introducción ð Juegos de suma cero ð Implementación de juegos ð Los jugadores y la heurística ð Algoritmo Minimax ð Algoritmo Alfa-beta

Introducción Introducción ð Shannon (1950) publicó “Programando un ordenador para jugar al ajedrez” ð El ajedrez plantea problemas similares a los de la deducción lógica: hay que elegir entre varias situaciones posibles y el objetivo no está totalmente definido ð El modelo discreto que define Shannon se conoce como árbol de juego y el modelo matemático como teoría de juegos de suma cero de dos jugadores con información completa

û Juego de suma cero: aquél en el que los intereses de los jugadores son contrarios. Si uno gana el otro pierde û Juego de información completa: aquél en el que cada jugador conoce las posibles jugadas que puede realizar el adversario

Juegos Juegos de de suma suma cero cero ð Características: û Suelen ser juegos de dos contrarios con turno alternativo û Terminan en dos o tres resultados posibles: ganar, perder o tablas (no se da en todos) û Cada movimiento implica una elección sobre todas las jugadas posibles. La elección sigue criterios determinados por el juego y no depende del azar (como en los dados, cartas...) û En todo momento los jugadores conocen las jugadas ya realizadas y las que se pueden realizar û Cada jugador tiene un nº determinado de movimientos en un momento dado. El árbol resultante es finito

Implementación Implementación de de juegos juegos ð Son necesarios 4 elementos: û abstracción de datos: para almacenar y representar el tablero (estado del juego) û generador de movimientos: genera todas las posibles jugadas inmediatas a partir de una situación del juego û función heurística: devuelve un valor, llamado valor estático, que evalúa cómo de favorable es cada jugada para orientar al algoritmo de búsqueda û estrategia de búsqueda: permite decidir qué estrategia es la más apropiada en cada momento

Los Los jugadores jugadores yy la la heurística heurística ð Se consideran dos jugadores, MAX y MIN, que intentan maximizar y minimizar la función heurística ð MAX (ordenador) elige la posición que tenga más valor en la evaluación de la función heurística ð MIN (adversario) elige la posición con menos valor ð La función heurística debe asignar valores tanto mayores cuanto mejor sea el estado del juego. Los valores deberán ser positivos para MAX y negativos para MIN ð Si MAX gana, la función devolverá +∞; si gana MIN, -∞

Algoritmo Algoritmo Minimax Minimax ð El objetivo es encontrar una buena jugada rápidamente ð La generación y la exploración del árbol están separadas ð Algoritmo: û Generar el árbol con profundidad n etiquetando cada nivel con MAX y MIN, alternativamente. El primer nivel es MAX û Calcular los valores estáticos para los nodos hoja û Explorar desde el nivel n hasta la raíz: Ÿ Si el nivel es MIN, elegir el menor valor de sus nodos hijos. Si el nivel es MAX, elegir el mayor valor de sus nodos hijos Ÿ Etiquetar el nodo con ese valor

û Elegir como mejor jugada la correspondiente al valor elegido por el nodo raíz

Algoritmo Algoritmo Alfa-beta Alfa-beta ð Alfa-beta mejora el minimax utilizando dos valores: û alfa (α): asociado a MAX; no puede decrecer; inicio, α = -∞ û beta (β): asociado a MIN; no puede crecer; inicio, β = +∞ ð ALFA-BETA (nodo, profundidad, F, α, β, jugador) Iniciar α, β localmente Si profundidad = 0 ó es final de juego, devolver F Si jugador = MIN Repetir hasta terminar todos los hijos ó α ≥ β V = ALFA-BETA ( HIJOi, profundidad-1, F, α, β , MAX) Si V < β entonces β = V Si α ≥ β, devolver -∞ (corte β); si no, devolver β Si jugador = MAX Repetir hasta terminar todos los hijos ó α ≥ β V = ALFA-BETA ( HIJOi, profundidad-1, F, α, β , MIN) Si V > α entonces α = V Si α ≥ β, devolver +∞ (corte α); si no, devolver α

Planificación Planificación de de Tareas Tareas

Fco. Javier Alcalá Casado

Planificación Planificación de de Tareas Tareas ð Visión general ð Método STRIPS ð Operador STRIPS ð Algoritmo STRIPS

Visión Visión General General ð La planificación pertenece al campo de resolución de problemas ð La planificación se basa en la división de un problema en subproblemas más pequeños que se resuelven por separado. La combinación de todas las subsoluciones forma la solución del problema original

Barra de pan entera Tenedor en la mano

Dejar tenedor

Mano libre

Coger cuchillo

Cuchillo en la mano

Cortar pan

Pan cortado

Visión Visión General General (II) (II) ð La planificación debe encontrar un conjunto de acciones, operaciones o tareas que transformen un estado inicial en un estado objetivo ð La solución del problema estará formada por una sucesión de operaciones denominado plan

PLAN = { Dejar Tenedor, Coger Cuchillo, Cortar Pan }

Visión Visión General General (II) (II) ð El primer planificador, desarrollado por Newell y Simon (1957), fue el sistema GPS (General Problem Solver). Su objetivo era resolver cualquier tipo de problema ð La principal aportación de GPS a los planificadores de tareas se centra en la organización de los datos: û Selector: atributo que define una característica relevante del entorno del problema (subobjetivos) û Estado: conjunto de selectores que definen una situación del mundo en un instante concreto û Operador: acción que transforma un estado en otro

Método Método STRIPS STRIPS ð STRIPS (STanford Research Institute Problem Solver) utiliza la lógica para mejorar la resolución del problema ð Utiliza gran parte de los elementos del sistema GPS ð Realiza una exploración en profundidad sobre el espacio de estados del problema (despliega un árbol) ð Opcionalmente, proporciona un mecanismo de aprendizaje utilizando la información de tareas resueltas previamente (tablas triangulares)

Operador Operador STRIPS STRIPS ð Un operador STRIPS consta de los siguientes elementos: û Nombre del operador û Parámetros del operador. Son opcionales û Precondiciones (P): lista de selectores que se tienen que cumplir para poder aplicar el operador û Lista de Adición (A): lista de selectores que se añaden al estado actual al aplicar el operador û Lista de Supresión (S): lista de selectores que se suprimen del estado actual al aplicar el operador

Algoritmo Algoritmo STRIPS STRIPS ð STRIPS consiste en seleccionar un operador que permita alcanzar el objetivo al aplicarlo. Las precondiciones pasan a ser subobjetivos que deben alcanzarse ð Se seguirá descomponiendo hasta que todas las precondiciones se cumplan y se pueda aplicar el operador ð Un nodo de exploración contiene dos variables: û ESTADO, que almacena el estado en ese nodo û PILA, que almacena selectores, operadores y conjunciones de selectores

ð Un nodo de FALLO es aquél en el cual, para alcanzar un determinado objetivo A, es necesario que A se cumpla

Algoritmo Algoritmo STRIPS STRIPS (II) (II) ESTADO = ESTADO_INICIAL; PILA = OBJETIVO REPETIR HASTA que PILA = ø ó todos los nodos sean de FALLO SI la cima de la PILA es un operador ENTONCES aplicarlo y obtener el nuevo ESTADO (suprimiendo y añadiendo selectores), suprimirlo de la cima (PLAN++) SI la cima de la PILA es una conjunción de selectores ENTONCES SI se verifica la conjunción ENTONCES suprimirla de la cima EN CASO CONTRARIO añadir la precondición que falla SI la cima de la PILA es un selector ∈ ESTADO ENTONCES suprimirlo de la cima EN CASO CONTRARIO SI el selector aparece más abajo en la PILA ENTONCES es un nodo de FALLO, la rama se aborta y recorre otra rama en profundidad Determinar operadores que contenga en su lista de adición el selector de la cima de la pila POR CADA operador Añadir la instancia del operador Añadir la conjunción de sus precondiciones Añadir cada una de sus precondiciones SI PILA ≠ ø ENTONCES devolver FALLO, no hay solución EN CASO CONTRARIO hemos ejecutado el PLAN

Aprendizaje Aprendizaje Simbólico Simbólico aa partir partir de de Ejemplos Ejemplos

Fco. Javier Alcalá Casado

Aprendizaje Aprendizaje Simbólico Simbólico aa partir partir de de Ejemplos Ejemplos ð Introducción ð Parámetros del algoritmo ID3 ð Algoritmo ID3 ð Generación de las reglas derivadas del árbol ID3

Introducción Introducción ð El aprendizaje automático se puede clasificar en: û Métodos simbólicos: basados en símbolos Ÿ Sintéticos o inductivos: ID3 Ÿ Analíticos o deductivos

û Métodos subsimbólicos: basados en cantidades numéricas

ð El objetivo del algoritmo ID3 consiste en clasificar varios elementos, utilizando ejemplos y valores de condición, representándolos en forma de árbol de decisión û Cada ejemplo es un individuo û Los valores de condición son propiedades û Los elementos se clasifican según el valor de una propiedad concreta binaria llamada resultado (con 2 valores posibles)

Introducción Introducción (II) (II) ð El árbol de decisión resultante determina el conjunto al que pertenece un individuo según los valores que toman alguna de sus propiedades (no todas) û Cada nodo interno representa una propiedad û Cada rama es un valor posible de esa propiedad û Cada hoja es un valor de la propiedad resultado

ð Un individuo nuevo se clasifica atravesando las ramas del árbol hasta llegar a una propiedad resultado ⇒ REGLAS ð Para clasificar los individuos se utiliza la idea de entropía. La entropía mide la cantidad de información necesaria para representar los datos de un conjunto (nº bits). A menor valor de entropía, mayor orden en los datos

Parámetros Parámetros del del algoritmo algoritmo ID3 ID3 ð Del conjunto inicial de ejemplos se definen: û û û û û û û

nt: c: nc: P: d: b: nb:

número total de ejemplos valores posibles para el resultado nº individuos que tienen el valor c como resultado nombre de las propiedades propiedad decisora de la propiedad resultado valores posibles para una propiedad d nº individuos con valor b para una propiedad

û nbc:

nº individuos con valor b para una propiedad y un valor c para un resultado

û Pc:

probabilidad de que un individuo tenga como resultado valor c (Pc = nc / nt) probabilidad de que suceda b (Pb = nb / nt)

û Pb: û Pbc:

probabilidad de que suceda c suponiendo que sucede b (Pbc= n bc / n b )

Parámetros Parámetros del del algoritmo algoritmo ID3 ID3 (II) (II)

ð Estos parámetros se utilizan para calcular la entropía:

û Entropía de un conjunto nc nc Entropía = ∑ − Pc log 2 Pc = ∑ − log 2 nt nt c c

û Entropía del valor de una propiedad ndecisora n Entropía(b) = ∑ − Pbc log 2 Pbc = ∑ − c

c

bc

nb

log 2

bc

nb

û Entropía media de una propiedad decisora nb nbc

nbc EntropíaMedia (d ) = ∑ Pb ∗ Entropía(b) = ∑ ∗∑ − log 2 nb nb b∈d b∈d nt c log 2 x =

(Recordatorio:

ln x ln 2

; si x=0,

x log 2 x = 0

)

ð Un conjunto es homogéneo si todos los ejemplos dan como resultado el mismo valor c Un conjunto es equilibrado si los valores de su propiedad resultado son equiprobables (máxima entropía)

Algoritmo Algoritmo ID3 ID3 ID3 ( Conjunto, P ) SI Entropía = 0 Devolver un nodo hoja etiquetado con la clase SI NO Calcular EntropiaMedia(P) Seleccionar la PROPIEDAD con menor EntropiaMedia Hacer PROPIEDAD raíz del árbol actual Borrar PROPIEDAD de P Para cada valor b de PROPIEDAD Crear una rama del árbol etiquetada con b Crear CONJUNTOb con todos los elementos con valor b para PROPIEDAD ID3 ( CONJUNTOb, P )

Generación Generación de de las las reglas reglas derivadas derivadas del del árbol árbol ID3 ID3 ð A partir del árbol ID3 generado se puede obtener un conjunto de reglas para clasificar nuevos individuos ð Cada nodo hoja genera una regla diferente ð Para ello: û Se recorre el árbol desde la raíz hasta las hojas û El antecedente de cada regla se crea tomando la etiqueta de la raíz más la etiqueta de la rama que recorre û Se añade un AND por cada pareja raíz-rama que se recorre û El consecuente de la regla es el nodo hoja

Aprendizaje Aprendizaje con con Algoritmos Algoritmos Genéticos Genéticos

Fco. Javier Alcalá Casado

Aprendizaje Aprendizaje con con Algoritmos Algoritmos Genéticos Genéticos ð Introducción ð Componentes de un Algoritmo Genético û Representación de individuos û Procedimientos generales de elección aleatoria û Operador selección û Operador emparejamiento û Operador mutación

ð Algoritmo general

Introducción Introducción ð Los algoritmos genéticos son adecuados cuando se dispone de mecanismos para establecer el rendimiento de un sistema, modificando ciertos parámetros ð El problema de aprendizaje consiste en encontrar una configuración adecuada de los parámetros, para que el rendimiento sea óptimo ð Ejemplo: ajuste del flujo de agua de un generador hidroeléctrico para que la producción eléctrica sea máxima ð Los algoritmos genéticos se apoyan en las teorías evolutivas de Charles Darwin (1859, El Origen de las Especies)

Introducción Introducción (II) (II) ð En cada generación se crea un nuevo conjunto de individuos utilizando parte del material genético de los mejores individuos de la generación anterior ð Objetivos de los algoritmos genéticos: û abstraer y explicar los procesos adaptativos de los sistemas naturales û diseñar sistemas artificiales basados en estos procesos

ð La principal característica es la robustez del sistema ð Surge una nueva rama, la Programación Genética: generación automática de programas que evolucionan para resolver cada vez mejor la tarea encomendada

Principios Principios de de Evolución Evolución por por Selección Selección Natural Natural 1. Cada individuo tiende a transmitir sus rasgos a su progenie 2. La naturaleza produce individuos con rasgos diferentes 3. Los individuos más adaptados, cuyos rasgos son más favorables para desenvolverse en el medio, tienden a producir más progenie 4. Durante largos períodos de tiempo se puede acumular la variación produciendo nuevas especies completamente adaptadas a nichos particulares

Componentes Componentes de de un un Algoritmo Algoritmo Genético Genético ð Los componentes básicos de un algoritmo genético son los siguientes: û Una representación para los individuos û Una función de calidad, que da una medida del grado de adaptación de un individuo al medio û Un operador selección, con probabilidad de selección de cada individuo proporcional a la calidad (principio 3) û Un operador emparejamiento o reproducción, que producirá nuevos individuos en la siguiente generación (principio 1) û Un operador mutación, capaz de alterar el código de los nuevos individuos, incrementando la riqueza genética de la población (principio 2)

Representación Representación de de Individuos Individuos ð Se utiliza la idea de cromosoma, que es una secuencia que determina la estructura de un individuo ð La secuencia es de longitud L y se compone de caracteres que pertenecen a un alfabeto Ω. Cada carácter es un gen ð Dado un cromosoma C, se puede construir el individuo I al que representa aplicando una función ð Normalmente se utiliza el alfabeto binario, Ω = {0,1}

Procedimientos Procedimientos Generales Generales de de Elección Elección Aleatoria Aleatoria ð Se utiliza una función random(), devuelve un real ∈ [0,1) ð Hay tres situaciones en las que es necesario realizar elecciones aleatorias: A) Ejecutar una acción con probabilidad p: IF (random() < p) THEN B) Elegir entre N elementos equiprobables: Ÿ Generar random() y ver dónde cae Ÿ Elegir el elemento correspondiente al tramo en el que caiga el valor aleatorio

E1 0

E2 E3

1/N 2/N

3/N

...

1

Procedimientos Procedimientos Generales Generales de de Elección Elección Aleatoria Aleatoria (II) (II) C) Elegir entre N elementos no equiprobables: Ÿ Calcular las probabilidades acumuladas Ÿ Generar random() y ver dónde cae k

ak = ∑ pi i =1

E1 0

E2 a1

E3 a2 a3

...

1

Operador Operador Selección Selección ð Cada vez que se necesita, se extraen ciertos individuos de la población. Para ello, se calcula la probabilidad de selección de cada individuo proporcional a la calidad ð Existen dos métodos: estándar y del rango ð Método estándar: û Establecer la calidad de cada individuo de la población û Calcular la probabilidad de selección de cada individuo dividiendo cada calidad por la calidad total û Elegir un individuo entre N elementos no equiprobables (procedimiento C)

Operador Operador Selección Selección (II) (II) ð Método del rango: û Fijar una probabilidad a priori de elección, p û Establecer la calidad de cada individuo de la población û Ordenar los individuos según su calidad (de mayor a menor) û Para cada individuo i desde 1 hasta N-1 Ÿ Elegir, con probabilidad p, el individuo i (procedimiento A) Si se ha elegido uno, salir y devolver dicho individuo

û Si no se ha elegido ninguno, devolver el individuo N

Operador Operador Emparejamiento Emparejamiento ð Este operador intercambia información genética entre dos individuos seleccionados ð Dados 2 individuos a emparejar: û Ejecutar el emparejamiento con probabilidad Pe (procedimiento A). Si no hay que emparejar, salir. û Elegir un punto de corte de las cadenas entre 1 y L-1 (procedimiento B) û Las cadenas que representan a los individuos se parten en dos trozos y se intercambian, dando lugar a dos individuos nuevos

Operador Operador Mutación Mutación ð Altera aleatoriamente el código genético de un individuo para variar ligeramente sus características ð Permite que aparezcan rasgos en los nuevos individuos que no existían antes en la población original ð La probabilidad de aplicación de este operador debe ser pequeña ð Dado 1 individuo a mutar: û Para cada gen del cromosoma, hacer: Ÿ Con probabilidad Pm (procedimiento A), cambiar el valor del gen por un nuevo valor. El nuevo valor se elige (procedimiento B) sobre los elementos del alfabeto Ω

Algoritmo Algoritmo General General EVOLUCIONAR (NI Pe Pm N) û Generar una POBLACION aleatoria de NI individuos û Repetir hasta haber realizado N iteraciones Ÿ Hacer NUEVA_POBLACION = { } Ÿ Repetir hasta que NUEVA_POBLACION tenga NI individuos Aplicar operador SELECCIÓN para extraer 2 individuos de POBLACION Aplicar operador EMPAREJAMIENTO con probabilidad Pe a los individuos seleccionados. Esto genera 2 nuevos individuos Aplicar operador MUTACION con probabilidad Pm a cada individuo generado en el paso anterior Añadir el resultado a NUEVA_POBLACION Ÿ Copiar NUEVA_POBLACION en POBLACION û Devolver el individuo con mayor calidad de POBLACION