Sistemas inteligentes

Resúmenes y apuntes

José Francisco Díez Pastor - César García-Osorio

José Luis Garrido Labrador


Introducción

La inteligencia artificial es el estudio de las computaciones que permiten percibir, razonar y actuar.

Enfoque Objetivo Método
Ingenieril Resolver problemas reales Estudio de los procesos
Científico Representar el conocimiento Modelar la inteligencia

Tipos de IAs

Agentes Inteligentes

Sistema informático, situado en un entorno dentro del que realiza acciones de forma autónoma e inteligente con un objetivo. Es sensible al entorno y ejecuta acciones que pueden cambiarlo

El carácter de racionalidad depende de:

Propiedades de los ambientes

Ejemplos

Ambiente Accesible Determinista Episódico Estático Discreto Benigno
Age of Empires No No No No No No
Solitario No Si Si Si Si Si
Parchís Si No Si Si Si No
Reversi Si Si No Si Si No
Sokoban Si Si Si Si Si Si

Tipos de agentes

Neurona Artificial

Con un vector de entrada de valores que entran a la neurona, un umbral que posee la misma y un vector de pesos asociados a cada entrada.

Para obtener la salida se hace el sumatorio del producto de los pesos y las entradas y se resta al umbral.

#Ejemplo de neurona OR import numpy as np weight = np.array([0.3,0.4]) umbral = 0.2 entrada = [np.array([0,0]),np.array([0,1]),np.array([1,0]),np.array([1,1])] salida = [] for e in entrada: salida.append(np.floor(np.sum(entrada*weight-umbral))+1)

Modelización de problemas de espacio de estados

Resolución de problemas

Se requiere

Dentro de la resolución existen varias técnicas generales para llegar más facilmente a las mismas. Se divide además el problema en dos tipos, aquellos cuyo método de solución es específico y por otro lado están los que no se pueden formalizar del todo.

Problema bien definido: Siendo S solución posible, P problema definido y Pr Procedimiento se define como

P ⇔ ∀ S ∃ Pr

Esto permite verificar automáticamente si se ha encontrado una solución y además se verifica en un número finito de pasos (algorítmico)

Entonces para resolver un problema se necesitan los siguientes pasos

  1. Definir el problema con precisión aislando y representando el conocimiento necesario para resolver el problema
  2. Analizar el problema definiendo que técnicas de solución son convenientes, esto implica seleccionar la mejor técnica y aplicarla

Los aspectos de la representación son

Representación del problema

La representación de los problemas tienen varias partes fundamentales, tiene un léxico que determina los símbolos del vocabulario. También la estructura donde se describen las restricciones sobre la sintaxis. La parte operativa donde se especifican los procedimientos de acceso, permitiendo crear descripciones, modificarlas y responder a preguntas utilizándolas. Por último existe una parte semántica en la cual se establece una forma de asociar el significado con las descripciones.

Las buenas representaciones hacen explícitos los objetos y las restricciones que importan, son completas, los objetos y las relaciones están agrupadas, están abstraídas correctamente, son concisas al dar información eficientemente, son calculables y rápidas además de ser transparentes.

Las representaciones tienen también una complejidad según sean representados los estados.

Búsqueda en espacio de estados

Es una técnica general para la resolución de problemas además de un método de generación y prueba porque genera las posibles soluciones y las verifica.

Se caracteriza la BEE por definir formalmente el problema mediante la necesidad de convertir una situación inicial dada (estado inicial) a una situación final deseada (estado final) mediante un conjunto de operaciones (operadores)

Las entidades entonces son:

Los estados han de ser expresivos para representar cualquier configuración del problema, concisos para incluir solamente los aspectos relevantes, naturales sobre la representación del problema y eficientes en su código. Además los operadores han de ser todos los necesarios e interesa sobre todo que sean naturales, reducidos y que su especificación sea lo más general posible.

A la hora de definir el problema se deben llevar a cabo los siguientes pasos:

  1. Definir el espacio de estados con todas las configuraciones
  2. Identificar los estados que comienzan el procesos estados iniciales
  3. Especificar soluciones o metas
  4. Especificar las reglas

Tras formalizar el problema, podemos pensar en el proceso de búsqueda como un árbol cuyos nodos son estados y los arcos los operadores, la raíz es el estado inicial y las hojas un estado cuyos sucesores no han sido calculados o que no tienen sucesores.

Sistema de producción

La búsqueda tiene muchos procesos, por lo que se debe estructurar el diseño del agente para describir el proceso de búsqueda. El sistema de producción no es más que una arquitectura que nos dará las estructuras necesarias.

Consta de la memoria del trabajo o lo que es lo mismo del histórico de los estados, un conjunto de reglas de producción que son los operadores además de un intérprete de reglas

La memoria del trabajo según su contenido podemos saber la complejidad del problema. Las reglas de producción tiene la estructura condición → acción. El intérprete de reglas se encargará por su parte de elegir las reglas aplicables, aplicarlas modificando la memoria y suspender el proceso si se ha llegado a una meta.

Estrategias de control de búsqueda

Dirección de búsqueda

La dirección se puede invertir intercambiando el estado inicial y el final e interpretando las reglas directa o inversamente.

La interpretación directa es aquella en la que teniendo un estado X al realizar la acción Y tenemos un nuevo estado. La interpretación inversa es teniendo un estado al que se ha llegado por Y, que X verifica el estado actual.

A la hora de seleccionar una dirección de búsqueda se deben tener en cuenta

Búsqueda hacia delante

Partimos del estado inicial y las reglas se aplican para alcanzar el estado final.

Búsqueda haca atrás

Partimos de la meta y las reglas se aplican inversamente

Búsqueda bidireccional

Se exploran los dos sentidos, se utiliza solamente si hay garantías de que las fronteras se pueden encontrar.

Información utilizada

Sin información

O también búsqueda ciega, aquella en la que no se utiliza un criterio para aplicar las reglas, su inconveniente es que la explosión combinatoria hace que el número de estados sea exponencial.

Heurística

O búsqueda informada aquella en la que, según un conocimiento del problema, se decide un método que reduzca el esfuerzo de la exploración del espacio de estados, aunque no garantiza la solución, una heurística, es una buena heurística si además garantiza la solución.

Según sea el método de búsqueda informada se dice si es ordenada porque la heurística decide el camino a recorrer o de poda si algunos estados se descartan.

También hay que tener en cuenta el coste, el de aplicación y el de control, el de aplicación es el número de reglas aplicadas y los estados generados y el de control la implementación de la búsqueda y la selección de reglas. La información afecta al coste, a mayor información mayor coste de control y menor coste de aplicación. También ocurre al revés.

Es recomendable utilizar heurísticas, ya que si son adecuadas se puede reducir la explosión combinatoria, además de que no siempre se necesita la mejor solución, si no una adecuada. Los peores casos apenas ocurren en la realizad y las además ayudan a entender los problemas de una manera más acertada.

Reconcideración efecto reglas

El control irrevocable es una regla aplicable que no se puede deshacer. Es más sencilla de implementar pero si la regla no es adecuada no se podrá encontrar la solución.

Si el sistema es de producción conmutativo entonces si que es interesante aplicar este tipo de reglas. Estos sistemas son los que la aplicación de una regla R no evita que se pueda aplicar otra regla S que podía ser aplicada antes de R. Además de que el estado resultante de aplicar S y R sería el mismo de aplicar R y luego S.

Cualquier proceso que se puede resolver con un proceso de búsqueda se puede resolver por uno conmutativo, además de que algunos problemas de manera natural ya son conmutativos.

Por último el control tentativo selecciona una regla aplicable y la aplica pero toma las medidas precisas para poder retornar, la ventaja es que ninguna regla puede impedir llegar a la solución, sin embargo es más costoso y necesita de más carga computacional. Se utiliza en búsqueda retroactiva y búsqueda en grafos


Técnicas de búsqueda

Búsqueda ciega

Primero en profundidad

  1. Nodos ← Lista de nodos iniciales
  2. Si nodos vacío, fallo
  3. Si Nodos[0] es final, entonces éxito
  4. Si no entonces Nodos ← Hijos de Nodos[0] + Nodos[1:]
  5. Ir a paso 2
def dfs(nodes, goalp, getnext): if nodes==[]: return None current=nodes[0] if goalp(current): return current return dfs(getnext(current)+nodes[1:],goalp,getnext)

Profundidiad con profundización iterativa

  1. Nodos ← lista de nodos iniciales
  2. Si nodos vacio, fallo
  3. Si Nodos[0] es final, entonces éxito
  4. Si la profunidad de Nodos[0] es mayor que max ir a 2
  5. En otro caso Nodos ← hijos de Nodos[0] + Nodos[1:]
  6. Ir a 2
def some(func, iterable): for element in iterable: res = fuct(element) if res != None : return res return None def dfsFd(node, goalp, getnext,depth, maxdepth): if goalp(node): return node if depth==maxdepth: return None return some (lambda n: dfsFd(n,goalp,getnext,depth+1,maxdepth), getnext(node))

La tabla de comparación de complejidad es la siguiente

Algoritmo Complejidad temporal Complejidad espacial ¿Completo?
Búsqueda en anchura O(b^d) O(b^d) Si
Búsqueda en profundidad O(b^m) O(mb) No
Profundidad limitada O(b^l) O(lb) Si l>=d
Profundización iterativa O(b^d) O(db) Si
Búsqueda bidireccional O(b^(d/2)) O(b^(d/2)) Si

Búsqueda informada

A*

Algoritmo admisible porque la función h es minorante, la función h no es admisible para un nodo si su valor es mayor que el coste del camino más corto


Representación del conocimiento

Existen dos tipos de métodos para solucionar problemas, débiles y fuertes, los débiles se caracterizan por usan un medio uniforme de representación, tiene reglas de inferencia que se basan en las características sintácticas de la representación y tienen estrategias de control para guiar la búsqueda y combatir la explosión combinatoria.

La búsqueda en espacio de estados tiene

Los métodos débiles tienen el inconveniente de que las estructuras de representación son demasiado simples para tener en cuenta todos los aspectos relevantes para encontrar una solución al problema, además de que una única heurística útil no existe.

Los métodos fuertes por otro lado utilizan un conocimiento profundo sobre el dominio del problema ya que incorporan conocimiento específico sobre los tipos de objetos y relaciones permitidos.

Surge entonces la pregunta de ¿qué es el conocimiento? es un tipo refinado de información (que es un tipo refinado de datos procesados) que puede ser incompleto o difuso, colecciona os hechos relacionados, procedimientos, modelos, heurísticas que se utilizan para resolver el problema.

Para representar entonces el conocimiento necesitamos de un modelo, existen tres:

Nginx Indexer