1. No category

Sistemas inteligentes, o
«inteligencia artificial»
http://www.gsi.dit.upm.es/~gfer/ssii/
https://moodle.lab.dit.upm.es/moodle/
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 1
¿Inteligencia artificial?
Entrevista a Claude Shannon:
–Could machines «think»?
–You bet. I’m a machine and you’re a machine,
and we both think, don’t we?
(J. Horgan: «Claude E. Shannon», IEEE Spectrum, 29, 4, Apr.1992, pp.72-75)
Depende de lo que entendamos por «inteligencia»
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 2
IA/Ciencia
IA
modelos de
razonamiento,
aprendizaje...
modelos de
representación,
comunicación...
Psicología
Epistemología
«Estudio de las facultades mentales mediante el uso de modelos
computacionales»
(Charniak y McDermott, 1985)
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 3
IA/Ingeniería
IA
modelos de
procesamiento de
la información y del
conocimiento
Informática
modelos de
resolución de
problemas y
automatización
Ingeniería
«Cómo hacer que los ordenadores ejecuten tareas cognoscitivas
que, por ahora, las personas realizan mejor»
(Rich y Knight, 1991)
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 4
Clasificación de definiciones según AIMA
Charniak y McDermot: énfasis en pensamiento;
criterio: inteligencia ideal, o racionalidad
Rich y Knight: énfasis en comportamiento;
criterio: inteligencia humana
inteligencia humana
pensamiento
Sistemas que piensan
como humanos:
Enfoque cognoscitivo
comportamiento Sistemas que actúan como
humanos:
Enfoque «prueba de
Turing»
racionalidad
Sistemas que piensan
racionalmente:
Enfoque lógico
Sistemas que actúan
racionalmente:
Enfoque de agentes
racionales
Russell, S. y Norvig, P.: Artificial Intelligence: A Modern Approach, 2nd. ed.
(«AIMA»). Prentice Hall, 2003
Traducido en Pearson Educación, 2004
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 5
IA/Negocio
IA
nuevas funciones
y prestaciones
Productos
etiqueta de
innovación
Mercado
Evolución de las «etiquetas»: sistemas expertos, ingeniería del
conocimiento, agentes inteligentes, gestión del conocimiento,
inteligencia de negocio...
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 6
IA interdisciplinaria
PSICOLOGÍA/
EPISTEMOLOGÍA
problemas de
comunicación
redes
semánticas
procesador
cognoscitivo
INFORMÁTICA/
INGENIERÍA
UPM
c 2009 DIT-ETSIT-UPM
interfaces
amigables
metodologías
de desarrollo
herramientas
de desarrollo
PRODUCTOS/
MERCADO
Sistemas Inteligentes: Introducción
transp. 7
Paradigmas de la IA
Procesamiento simbólico:
problemas de naturaleza no numérica (lógica)
Búsqueda heurística:
hacer tratable la complejidad del proceso
Sistemas expertos:
visión conductista, funcional
Sistemas basados en conocimiento:
visión cognoscitiva, estructural
Aprendizaje automático:
Sistemas con autonomía, inducción de conocimiento
Agentes inteligentes:
«sociedades» de componentes con «personalidad»
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 8
Formulación del problema de resolver problemas
Idea básica: Espacio de búsqueda ≡ espacio de estados
(años 50: influencia de la teoría de autómatas)
< Q, R,C >
Q: Estructura de datos que describe al estado
R: Reglas u operaciones que describen las
transiciones en el espacio de estados
R×Q → Q
C: Estrategia de control
Resolución: Búsqueda de una secuencia r1, r2, . . . rn
que conduzca de q0 a q f
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 9
Ejemplo de busqueda: «pesetas y duros»
r1
P
P D D
P P D
P P
r2
D
D D
D D
r3
q
0
P P D D
r4
P P D D
P P qf
Estado: lista con dos «P», dos «D» y un « »
Reglas: r1 : desplazar P a hueco a la derecha
r2 : desplazar D a hueco a la izquierda
r3 : saltar P a la derecha
r4 : saltar D a la izquierda
card(Q) = 27 ⇒ algoritmo de búsqueda exhaustiva
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 10
Ejemplo de busqueda: «puzzle kn − 1»
7
1
6
1
8
4
5
4 3
q
0
7
6 5
q
f
2
8
2
3
Estado: matriz
Reglas: r1 = ↑, r2 = ↓, r3 = →, r4 = ←
card(Q) = 9! = 362.880
⇒ búsqueda exhaustiva aún posible, pero
para «puzzle 15», card(Q) = 16! ≈ 2×1013 . . .
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 11
Complejidad algorítmica: Notación O
Complejidad temporal y espacial: crecimiento asintótico
k + log(x) + x + x2 + . . . + xn = O(xn) (polinómico)
O(xn) + . . . + mx = O(mx) (exponencial)
2x
x2
100
80
60
40
x log x
x
log x
20
0
0
2
x
4
log(x)
6
x*log(x)
8
x**2
10
2**x
clase P: O(xn) (problemas «fáciles»)
clase NP (No determinista Polinómico)
problemas NP-completos
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 12
Heurísticos
D.R.A.E.: «heurística» = «arte de inventar»
En I.A.:
• Como adjetivo, para distinguir de
«algorítmico» ≈ «seguro»
• Como sustantivo, truco o regla empírica que ayuda
a encontrar la solución de un problema (pero que no
garantiza que se encuentre)
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 13
Búsqueda heurística
En el desarrollo del árbol de búsqueda no fijarse en todos los
estados posibles («nodos»), sólo en los más «prometedores»
Algoritmo A*: en cada nodo se estima la distancia, o coste, del
camino que pasando por ese nodo lleva desde el estado inicial al
final (la solución).
Función de evaluación: f (n) = g(n) + h(n)
g(n): coste de n0 a n (conocido)
h(n): estimación del coste de n a n f
(menor que el coste real, para que el algoritmo
encuentre solución óptima, si la encuentra)
De los sucesores de cada nodo se elije el de menor f (n)
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 14
Ejemplos de heurísticos para el 8-puzzle
h1(n): Número de piezas mal colocadas
h2(n): Suma de «distancias Manhattan»
h1(n) = 7
h2(n) = 2 + 3 + 3 + 2 + 4 + 2 + 0 + 2 = 18
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 15
Paradigmas de la IA
Procesamiento simbólico:
problemas de naturaleza no numérica (lógica)
Búsqueda heurística:
hacer tratable la complejidad del proceso
Sistemas expertos:
visión conductista, funcional
Sistemas basados en conocimiento:
visión cognoscitiva, estructural
Aprendizaje automático:
Sistemas con autonomía, inducción de conocimiento
Agentes inteligentes:
«sociedades» de componentes con «personalidad»
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 16
Sistema experto
British Computer Society, 1983:
«Incorporación en un ordenador [. . . ] de la pericia de un
experto de modo que el sistema pueda dar consejos
inteligentes o tomar decisiones inteligentes y justificar su
razonamiento»
Aplicable el «test de Turing».
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 17
Sistema basado en conocimiento (SBC, o KBS)
Evolución de modelos estructurales de sistemas software:
sistema primitivo:
independencia
de datos:
independencia
del
conocimiento:
usuario
usuario
usuario
E/S (S.O.)
interfaz
programa
ficheros
programa
SGBD
motor de
inferencias
SGBD
BD
BD
expertos
interfaz
ingenieros
conocimiento
UPM
c 2009 DIT-ETSIT-UPM
base de
conocimientos
Sistemas Inteligentes: Introducción
transp. 18
SS.EE. vs. SS.BB.C.
SE: punto de vista funcional (conductista)
problemas,
preguntas
USUARIO
(ENTORNO)
respuestas,
justificaciones,
preguntas
SISTEMA
EXPERTO
SBC: punto de vista estructural (cognoscitivo)
SISTEMA
motor de
inferencias
base de
conocimientos
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 19
I.A., SS.BB.C. y SS.EE.
SISTEMAS DE I.A.
SS.BB.C.
SS.EE.
heurísticos,
procesamiento
simbólico
UPM
c 2009 DIT-ETSIT-UPM
conocimiento,
arquitectura
aplicaciones a dominios en los
que la resolución de problemas
requiere experiencia especial
Sistemas Inteligentes: Introducción
transp. 20
Ingeniería del conocimiento
Heterodoxia
(con respecto a la ingeniería del software):
Conocimiento humano incompleto, inconsistente, impreciso,
incierto, tolerante. . .
Razonamiento y respuestas del sistema inseguros
Conocimiento evolutivo, posibilidad de aprendizaje
Responsabilidad del diseño, desarrollo y mantenimiento:
ingenieros, expertos y usuarios finales
No aplicable el ciclo de vida en cascada
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 21
Representación del conocimiento
Modelos y lenguajes basados en la psicología
Sistemas de reglas de producción:
Si <antecedente>entonces <consecuente> (implicación)
Si <condiciones>entonces <acción> (activación)
Redes semánticas y marcos, basados en teorías de la
formación de conceptos en la mente humana
Formalización en lenguajes lógicos
Lógicas de base: proposiciones, predicados
Lógicas de descripciones
Lógicas modales
Prolog
web semántica
creencias, deseos, intenciones...
Lógica borrosa
...
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 22
Ejemplo de red semántica
vida
sentir
tiene
moverse
puede
puede
ANIMAL
bien
tipo_de
vuela
plumas tiene
huevos
pone
AVE
largas
UPM
da
leche
tiene
pelo
MAMIFERO
tipo_de
AVESTRUZ
patas
tipo_de
tipo_de
tipo_de
ALBATROS
BALLENA
vuela
vuela
tiene
muy_bien
no_puede
c 2009 DIT-ETSIT-UPM
tipo_de
LEON
vive_en
piel
mar
Sistemas Inteligentes: Introducción
come
carne
transp. 23
Traducción de la red semántica a un lenguaje lógico (1)
«Lógica OAV», o «lógica 0+»: triplas
<Objeto>
<Atributo>
<Valor>.
Conocimiento factual:
"Moby Dik"
"Moby Dik"
"Leo Verdura"
ex("Leo Verdura"
...
es_un
olor
es_un
ome
Ballena .
blano
León .
hortalizas) .
Conocimiento normativo sobre el dominio:
Animal
Animal
Animal
Ave
...
ex(Ballena
Avestruz
...
UPM
c 2009 DIT-ETSIT-UPM
tiene
puede
puede
vuela
vida .
sentir .
moverse .
bien .
tiene
piel) .
tipo_de
Ave .
Sistemas Inteligentes: Introducción
transp. 24
Traducción de la red semántica a lenguaje lógico
Conocimiento normativo general (reglas sobre herencia):
if ( ?X
tipo_de
?Y ) or ( ?X
then ( ?X
hereda_de
?Y ) .
es_un
?Y )
if ( ?X
tipo_de
?Y ) or ( ?X
and ( ?Y
hereda_de
?Z )
then ( ?X
hereda_de
?Z ) .
es_un
?Y )
if ( ?X
hereda_de
?Y )
and ( ?Y
?W
?Z )
and not(ex( ?X
?W
?Z ))
then ( ?X
?W
?Z ) .
if (ex( ?X
?W
?Z ))
then ( ?X
?W
?Z ) .
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 25
Paradigmas de la IA
Procesamiento simbólico:
problemas de naturaleza no numérica (lógica)
Búsqueda heurística:
hacer tratable la complejidad del proceso
Sistemas expertos:
visión conductista, funcional
Sistemas basados en conocimiento:
visión cognoscitiva, estructural
Aprendizaje automático:
Sistemas con autonomía, inducción de conocimiento
Agentes inteligentes:
«sociedades» de componentes con «personalidad»
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 26
Paradigma de la «agencia»
sensores
perceptos
?
entorno
acciones
agente
efectores
(Figura de AIMA)
Agente: Sistema que actúa (eventualmente, por encargo) para
producir ciertos efectos en su entorno
Agencia: Cualidades (funcionales, estructurales y/o procesales)
propias de los agentes
(en inglés: agency, o agenthood)
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 27
Agentes software
El «entorno» puede ser accesible mediante sensores y
efectores, pero más frecuentemente está formado por otros
agentes y/o personas (que también se consideran «agentes»)
accesibles localmente (en la misma máquina en la que se
ejecuta el agente) o (más interesante) remotamente.
“?” es un sistema basado en conocimiento.
Los «perceptos» y las «acciones» son actos de comunicación
expresados en un lenguaje.
Agente y entorno deben compartir el lenguaje y una
«visión del mundo», u «ontología»:
vocabulario y significado de los términos.
Más el próximo día
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 28
SINT vs. MIT-6.034
«6.034 Artificial Intelligence» (M.I.T.)
T. Lozano–Pérez y L. Kaelbling
http://ow.mit.edu/
OwWeb/Eletrial-Engineering-and-Computer-Siene/
6-034Spring-2005/CourseHome/index.htm
Tema
horas Tema
horas
Búsqueda
— Search
6
Lenguajes de represent.
Knowledge Representation
para ontologías
12
and Inference
15
Aprendizaje
10 Machine Learning
15
Agentes
16 —
—
Aplicaciones
16 —
—
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 29
Sistemas Inteligentes: Temas
Tema/horas
Introducción/2
Ontologías/12
Aprendizaje/10
Agentes/16
Aplicaciones/16
Profesor
gferdit.upm.es
gferdit.upm.es
gferdit.upm.es
mgadit.upm.es
jgdit.upm.es
gfer: Gregorio Fernández
jg: José Carlos González
mga: Mercedes Garijo
UPM
c 2009 DIT-ETSIT-UPM
Sistemas Inteligentes: Introducción
transp. 30