Introducción a los Sistemas Inteligentes: Conceptos y Técnicas Fundamentales

Introducción a Sistemas Inteligentes

Herramientas Básicas de la IA

• Algoritmo: procedimiento general de resolución de algún problema, tal que su validez no puede ser cuestionada, por basarse en principios formalizados.
• Procedimiento heurístico: procedimiento de resolución de problemas que se basa en la intuición o en la experiencia, y sin embargo en la práctica resuelve problemas en forma correcta.
• Computación simbólica: una aproximación metodológica correcta a un problema debe considerar el problema como un sistema de símbolos que poseen un álgebra específica.
• Procedimentalismo: la programación procedimental utiliza una descripción del problema basada en la especificación de un conjunto de órdenes o instrucciones que ejecutadas en orden conducen a la solución.
• Declarativismo: la programación declarativa realiza una descripción de los problemas en forma de relaciones lógico-funcionales de los componentes a datos del mismo. Especifica la relación entre la solución y los datos.

Problemas y Procesos de Búsqueda

Elementos Principales de los Sistemas de Resolución de Problemas

• Representación: describe el dominio, objetivo y situación inicial.
• Operadores: transforman la situación actual del problema (o lo dividen en problemas más simples).
• Estrategia de control: selecciona el operador a aplicar en cada situación del problema, de entre todos los posibles. Es responsable de la selección de la secuencia de operadores que conduce a la resolución.

Tipos de Representación de Problemas

• Mediante estados: problemas como colección de estados.
  • Dos clases de entidades, los estados y los operadores.
  • Se especifica como (S, O, G): {S} y {G} estados iniciales/finales y {O} operadores.
  • Un procedimiento define un camino en el espacio desde S a G y da una secuencia de O.
• Mediante reducción: problemas como una jerarquía de subproblemas de complejidad dispar.
  • Situación inicial definida por:
    • Formulación del problema y conjunto de operadores.
  • La descripción inicial se resuelve por aplicación de una secuencia de transformaciones que en último extremo la convierte en un conjunto de subproblemas de resolución inmediata.
  • Un operador puede transformar un problema en varios subproblemas secundarios (nodo Y) o en varios alternativos (nodo O).

Características de los Problemas

Para escoger el método más apropiado para un problema hay que analizarlo:

• ¿Se puede descomponer el problema en un conjunto de subproblemas independientes? Entonces es un problema descomponible.
• ¿Se pueden ignorar o deshacer aquellos pasos a la solución que sean poco lógicos? Entonces es un problema recuperable e ignorable.
• ¿Es obvia una buena solución del problema sin necesidad de compararla con todas las otras posibles soluciones? Entonces es un problema de cualquier camino y mejor camino.
• El conocimiento base para resolver el problema, ¿es consistente?
• ¿Es necesaria gran cantidad de conocimiento para resolver el problema o sólo para restringir la búsqueda? Aquí entra en juego el papel del conocimiento.

Reglas con las que se forma un grafo Y/O

• Nodo: representa un conjunto (uno o más) de problemas a resolver.
• Nodo terminal: nodo que no se descompone o simplifica.
• Nodo terminal con solución se corresponde con un problema primitivo (primitiva).
• Si por cada posible operador se genera un conjunto de subproblemas de solución:
  • alternativa, entonces se produce un nodo O.
  • de necesaria resolución de todos ellos, entonces se produce un nodo Y.

Estrategias Básicas de Búsqueda

Medir el Rendimiento en un Procedimiento

La salida de un procedimiento es fallo o una solución y evaluamos su rendimiento de cuatro formas:

• Completitud: garantizar que si existe solución, se encuentra.
• Optimalidad: si tiene solución, encuentra la óptima.
• Complejidad en tiempo: cuánto tarda en encontrar una solución.
• Complejidad en espacio: cuánta memoria se necesita para la búsqueda.

Y la complejidad se expresa en términos de tres cantidades:

• b, factor de ramificación o el máximo número de sucesores de cualquier nodo.
• d, la profundidad del nodo objetivo más superficial.
• m, la longitud máxima de cualquier camino en el espacio de búsqueda.

Heurística Monótona en Estados y Reducción

Una función heurística h se dice monótona si cumple que h(n) <= h(n’) + c(n,n’), ∀n y debe cumplirse tanto en estados como en reducción (en reducción es la suma de todos sus hijos).

• Heurística es admisible si nunca sobrestima el costo real (h*(n)) de alcanzar el objetivo desde un nodo n, h(n) <= h*(n). Las heurísticas admisibles son optimistas, suponen que el coste de resolver un problema es menor de lo que realmente es. Las no admisibles son pesimistas, pueden descartar un sucesor que piensan es peor de lo que realmente es.
• Una heurística es consistente sii h(n) <= k(n, as, n’) + h(n’), donde k es el costo de n a n’ a través de una secuencia de acciones as.
  Una heurística es monótona sii h(n) <= c(n, a, n’) + h(n’), con n’ sucesor inmediato de n y donde c es el costo del arco que une n y n’.
• Si h es una heurística consistente (monótona) entonces h es admisible.

Búsqueda No Informada o a Ciegas (Estados)

Búsqueda Heurística (Estados)

• Búsqueda primero el mejor avara o voraz (greedy): expande el nodo que estima más cercano al objetivo.
  • f(n) = h(n).
  • Complejidad en tiempo y espacio O(b^m).
• Búsqueda A*: minimizando el costo estimado total de la solución
  • f(n) = g(n) + h(n)
  • En arboles si h(n) es admisible —> A* es óptima
  • En grafos la admisibilidad no es suficiente para garantizar optimalidad. Para ello es se puede o extender la búsqueda que deseche el camino mas caro o exigir una propiedad mas estricta de admisibilidad (condición de consistencia).
  • Aunque es completa, óptima y eficiente, el no de nodos dentro de la curva de nivel del objetivo es exponencial en la longitud de la solución. Se queda sin espacio antes que sin tiempo.
• Búsqueda primero el mejor recursiva o con memoria acotada: Imita a primero el mejor, pero genera menos nodos y el consumo de memoria es lineal. Evita profundizar en un camino que podría empeorar.
  • Variable flímite para recordar el f-valor del mejor camino alternativo desde cualquier ancestro. Si el nodo actual excede el límite, retrocede y descarga el subárbol actual.
  • Si h(n) es admisible —> BPMR es optimo.
  • Complejidad de espacio es O(bd).
  • Su consumo de tiempo depende de h(n) porque debe reexpandir nodos varias veces.
• A*MS: Avanza como A* expandiendo la mejor hoja hasta quedarse sin memoria, en este punto, retira siempre el peor nodo hoja (f-valor más alto). Devuelve hacia atrás el valor del nodo olvidado, el antepasado de un subárbol olvidado sabe la calidad del mejor camino en el subárbol. Con esta información, solo se vuelve a generar si todos los caminos parecen peores que el olvidado.
  • Completo si hay alguna solución alcanzable (d es menor que el tamaño de memoria).
  • Óptimo si cualquier solución óptima es alcanzable.

Búsqueda No Informada o a Ciegas (Reducción)

• Búsqueda primero en anchura.
• Búsqueda primero en profundidad.
• Búsqueda de profundidad limitada.

Búsqueda Heurística (Reducción)

Estamos interesados en encontrar el grafo solución que tenga costo mínimo, el óptimo. Para ello, disponemos de una función heurística. Para buscar en un grafo Y/O son necesarias 3 acciones:

1. Atravesar el grafo desde el nodo inicial, siguiendo el mejor camino y acumulando los nodos de ese camino no expandidos.
2. Elegir uno de estos nodos y expandirlo, añadir sus sucesores y calcular h. Cambiar la h estimada recientemente, propagando hacia atrás.
3. Para cada nodo que se visita, hay que decidir el conector más prometedor y marcarlo como parte del mejor grafo solución parcial actual.

Funciones Heurísticas

• Efecto de la precisión heurística en el rendimiento
  • b*, factor de ramificación eficaz: N, no de nodos generados; d, profundidad de la solución; entonces N+1 = 1+b*+ … + (b*)^d.
• Funciones heurísticas para problemas relajados
  • Un problema con menos restricciones en las acciones se le llama problema relajado.
  • El costo de una solución óptima en un problema relajado es una heurística admisible para el problema original.
  • Es admisible porque la solución óptima del relajado también lo es para el original y por tanto debe ser al menos tan cara.

Estrategias Avanzadas de Búsqueda

Procedimientos de Búsqueda Local y Problemas de Optimización

• Búsqueda por ascensión de colinas: bucle que continuamente se mueve en dirección del valor creciente y termina cuando alcanza un pico donde ningún vecino tiene un valor más alto. A menudo se atasca en máximos locales, crestas o mesetas.
• Búsqueda por temple simulado: la ascensión de colinas es incompleto y eficaz, un camino puramente aleatorio es completo pero ineficaz por lo que en vez de escoger el mejor movimiento se escoge un movimiento aleatorio y si:
  • el movimiento mejora la situación, se acepta.
  • el movimiento no mejora la situación, el procedimiento lo acepta con una prob e^ΔE/T.
  La probabilidad disminuye exponencialmente con la falta de calidad de ΔE y la temperatura, siendo los malos movimientos son más probables al comienzo cuando la temperatura es alta y se hacen más improbables cuando disminuye.
• Búsqueda por haz local: guarda la pista de k estados. Comienza con estados generados aleatoriamente, en cada paso, se generan sucesores de los k estados. Si alguno de los sucesores es objetivo, paramos el procedimiento, si no, se seleccionan los k mejores sucesores y repetimos.

Búsqueda entre Adversarios

• Juegos. Decisiones óptimas: Consideramos juegos con dos jugadores (MAX y MIN), MAX mueve primero y luego por turnos hasta terminar. Al final, se conceden puntos al ganador y penalizaciones al perdedor.
  • Estrategia óptima. Minimax: MAX debe encontrar una estrategia contingente, que especifique un movimiento inicial y luego los movimientos en los estados que resultan de cada respuesta de MIN. Se realiza una exploración primero en profundidad.
  • Decisiones óptimas en juegos multijugador: Sustituir el valor para cada nodo con un vector de valores. Para los estados terminales, dará utilidad del estado desde el punto de vista de cada jugador.
  • Minimax-alfa-beta (poda alfa-beta): Devuelve el mismo movimiento que devuelve minimax, pero podando nodos o subárboles. Su eficiencia es muy dependiente del orden en que se examinan los sucesores.
• Decisiones en tiempo real imperfectas. Heurísticas: Se propone implementar un corte de la búsqueda y evaluación heurística a las estrategias anteriores. Para el corte, se lleva la contabilidad de la profundidad y se corta cuando se supere una profundidad d.
• Juegos que incluyen un elemento de posibilidad: Se trata de generalizar el valor minimax para juegos deterministas a un valor minimax esperado para juegos con nodos de posibilidad.

Representación del Conocimiento y Razonamiento

Tipos de Conocimiento

• de Entidades: referido a las propiedades y estructura física de los objetos o entes reales.
• de Conducta: referido al comportamiento o modo de proceder de los entes del mundo real.
• de Eventos: referido a la secuencia y distribución en el tiempo de sucesos, y de las relaciones causales de los mismos.
• Procedimental: referido al conocimiento de cómo deben realizarse determinados procesos o transformaciones.
• sobre Incertidumbre: referido a la certeza sobre los hechos.
• Meta-Conocimientos: conocimiento cuyo objeto de referencia es el propio conocimiento, es decir, un conocimiento acerca de las propiedades de los conocimientos o de cómo usar distintos módulos de conocimiento.

Fases de Utilización del Conocimiento

• Adquisición: se extrae el conocimiento de un experto o de algún proceso de prueba-error, generalmente mediante técnicas de aprendizaje.
• Conceptualización: definición y organización de los distintos componentes de conocimiento.
• Representación: diseño de las estructuras de datos que se usarán como soporte computacional del conocimiento.
• Implementación: desarrollo del software que implementa el conocimiento y las técnicas de inferencia.
• Acceso: esta relacionado con la forma de extraer el conocimiento desde una representación estructurada.
• Selección o recuperación: fase en la que hay que seleccionar un elemento de conocimiento concreto, adecuado al problema y al estado del proceso de resolución del mismo.

Propiedades del Conocimiento

• Ámbito: extensión del dominio en el que se va a aplicar el conocimiento. Se considera imposible definir conocimiento que abarque cualquier contexto, es más adecuado contextos restringidos.
• Granularidad: tamaño de la unidad mínima de representación.
  • Grano grande: ventaja para representar contenidos de alto nivel, pero de difícil tratamiento y proceso.
  • Grano pequeño: ventaja para representar contenidos de bajo nivel y de fácil tratamiento, el inconveniente es representar conceptos de alto nivel.
• Redundancia: posible representar un mismo conocimiento en múltiples formas.
• Modularidad: posibilidad de agrupar unidades (gránulos) de conocimiento en módulos.
• Comprensibilidad: capacidad de interpretar las estructuras de representación.

Cosas Malas de la Lógica No Clásica

• Lógicas no monótonas: La incorporación de un teorema a una teoría puede invalidar conclusiones que podrían haberse dado previamente. Son buenas en conocimientos incompletos, discursos cambiantes y en resolución de problemas donde se hagan suposiciones temporales.
  NOTA: En las lógicas monótonas, si se añade un teorema propio a una teoría T para obtener una teoría T’, entonces todos los teoremas de T son también teoremas de T’.
• Lógica difusa: Inconsistencia en los predicados vagos, aunque podemos razonar a partir de afirmaciones vagas mediante el razonamiento aproximado.
• Lógica de situaciones: Una afirmación que hoy es cierta, mañana puede que no lo sea, una afirmación que es cierta en un contexto, en otro puede que no.

Combinación de Factores de Certeza (Incertidumbre)

• Combinación de antecedentes
• Adquisición incremental de evidencia
• Encadenamiento de evidencia

Representación del Conocimiento y Razonamiento

Componentes de un Sistema de Planificación

• Estado inicial y estado intermedio. Se describen mediante conjunciones de literales básicos.
• Estado objetivo. Se expresan como conjunciones de literales y todas las variables son cuantificadas.
• Descripción de operadores. Las acciones ejecutadas generan nuevos estados. Constan de antecedente (precondición) y consecuente (lista de supresión y fórmula de adición).

Planificación de Orden Total

• Planificación como búsqueda en un espacio de estados: compuesto por objetivo (estado final), acciones disponibles (operadores de búsqueda) y árbol de búsqueda. La búsqueda tanto hacia delante como hacia atrás. Una búsqueda exhaustiva es inviable, por lo que se usan heurísticas.
• Planificación secuencial usando una pila de objetivos (STRIPS): sistema de planificación lineal (con una pila de subobjetivos)y que funciona bien cuando no hay interdependencias. El control del sistema debe tomar diversas decisiones: ordenación de las componentes de un objetivo compuesto, elección entre distintas particularizaciones o la selección de operadores.

Planificación Ordenada Parcialmente

Un planificador no lineal construye un plan cuyo orden no es total. Sus ideas básicas son:

• Planificación de compromiso mínimo.
• Escoger solamente las acciones estrictamente necesarias.

Planificación Jerárquica

La idea es jerarquizar el programa en diferentes niveles de complejidad y resolver gradualmente aumentando progresivamente la misma. Las jerarquías se crean dependiendo de valores críticos de las precondiciones de los operadores. > dificultad en satisfacer precondición > valor crítico.

Introducción al Lenguaje Computacional

Tipos de Aprendizaje, Fases del Aprendizaje y Proceso de Inferencia

Tipos de aprendizaje:

• Aprendizaje supervisado: la experiencia viene en forma de ejemplos etiquetados.
• Aprendizaje no supervisado: la experiencia viene en forma de observaciones del entorno.

Fases del aprendizaje:

la base del aprendizaje es la optimización de una función de costo.

• Entrenamiento: se distingue entre supervisión o no supervisión.
• Prueba: no se hace esa distinción, pero se habla de clasificación o predicción.

El Proceso de Inferencia es la predicción final.

Características Deseables de un Sis. Aprendizaje

• Precisión: fiabilidad del modelo aprendido.
• Velocidad: rapidez al producir la predicción.
• Compresión: si es un operador humano el que usa el modelo aprendido, debe ser fácil de entender para evitar errores.
• Tiempo en aprender: de especial importancia en aprendizaje on-line aplicado a sistemas que cambian rápidamente.

Estimadores de Error de un Método en un Problema

• Estimador del error de los ejemplos: Sea N no de ejemplos y E no de errores del modelo: E/N.
• Estimador del error de resustitución: Usamos el conjunto de datos del entrenamiento.
• Estimador del error por validación cruzada (CV): realiza varias estimaciones y las agrega, a partir de diferentes combinaciones de conjuntos de entrenamiento y prueba. Se aplica en casos en los que los datos son escasos, pues es costoso computacionalmente.
  Para ello se divide el conjunto original S en V partes disjuntas (S₁,…,S_v) de tamaño semejante, y para cada una se:
  • construye el modelo usando el método sobre el conjunto de ejemplos S-S_i.
  • determina el estimador del error de los ejemplos R_i usando el conjunto de prueba S_i.
  Se calcula el estimador del error por validación cruzada como:
  (con | x | tamaño del conjunto de ejemplos de x)

Algunos Sistemas Básicos de Aprendizaje e Inferencia

• Aprendizaje memorístico: almacenar todo el nuevo conocimiento para utilizarlo cuando sea preciso. Algunos elementos: organización de memoria, estabilidad y almacenamiento frente a recálculo.
• Aprendizaje en la resolución de problemas: tras resolver un problema, se recuerda su estructura, métodos para resolverlo y solución. En la siguiente ocasión podemos usar esta experiencia directamente o generalizarla.
• Aprendizaje por inducción en modo estructural: durante el aprendizaje se construyen modelos de clasificación, El modelo aprendido puede tener dos formas: modelo estadístico o estructural.
• Aprendizaje de reglas de asociación: las reglas se obtienen a partir de observaciones. Aquellas cuyo antecedente y consecuente son ciertos tendrán una cobertura (soporte) alta y cuando se cumple el antecedente tendrán una confianza (precisión) alta. El objetivo es encontrar reglas con buenos valores de cobertura y confianza. Hay que seguir dos fases para obtener las reglas:
  1. Generar todas las combinaciones de ítems, con un soporte superior al mínimo.
  2. Dado un itemset frecuente, generar todas las reglas que contengan todos los ítems del mismo. Tienen que cumplir Confianza = Soporte(Y)/Soporte(x).