PDF de programación - Inteligencia artificial avanzada

Inteligencia
artificial avanzada

Raúl Benítez
Gerard Escudero
Samir Kanaan

PID_00174137

Los textos e imágenes publicados en esta obra están sujetos –excepto que se indique lo contrario– a
una licencia de Reconocimiento-NoComercial-SinObraDerivada (BY-NC-ND) v.3.0 España de
Creative Commons. Podéis copiarlos, distribuirlos y transmitirlos públicamente siempre que citéis
el autor y la fuente (FUOC. Fundació per a la Universitat Oberta de Catalunya), no hagáis un uso
comercial y no hagáis una obra derivada. La licencia completa se puede consultar en
http://creativecommons.org/licenses/by-nc-nd/3.0/es/legalcode.es

CC-BY-NC-ND • PID_00174137

Índice

Inteligencia artificial avanzada

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.

Introducción a la inteligencia artificial (IA) . . . . . . . . . . . . . . . . .
1.1. Neuronas y transistores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.
Breve historia de la IA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3. Ámbitos de aplicación de la inteligencia artificial . . . . . . . . . . . . .

2.2.

2. Recomendadores y agrupamientos. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1. Métricas y medidas de similitud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1.
Ejemplo de aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.2. Distancia euclídea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.3. Correlación de Pearson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.4.
Procesamiento de datos reales . . . . . . . . . . . . . . . . . . . . . . . .
2.1.5. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Recomendadores basados en memoria . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1. Conceptos generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Aproximaciones simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2.
2.2.3.
Recomendación ponderada . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.4. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3. Algoritmos de agrupamiento (clustering) . . . . . . . . . . . . . . . . . . . . . .
2.3.1.
Ejemplo de aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.2. Conceptos generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Agrupamiento jerárquico. Dendrogramas . . . . . . . . . . . .
2.3.3.
k-medios (k-means) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.4.
2.3.5.
c-medios difuso (Fuzzy c-means) . . . . . . . . . . . . . . . . . . . . . .
Agrupamiento espectral (spectral clustering) . . . . . . . . . . .
2.3.6.
2.3.7.
Recomendadores basados en modelos . . . . . . . . . . . . . . . .

3. Extracción y selección de atributos . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Técnicas de factorización matricial . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1. Descomposición en valores singulares (SVD) . . . . . . . . .
Análisis de componentes principales (PCA). . . . . . . . . . .
3.1.2.
Análisis de componentes independientes (ICA) . . . . . .
3.1.3.
3.1.4.
Factorización de matrices no-negativas (NMF). . . . . . . .
3.2. Discriminación de datos en clases. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Análisis de discriminantes lineales (LDA) . . . . . . . . . . . . .
3.3. Visualización de datos mutidimensionales . . . . . . . . . . . . . . . . . . . .
Escalamiento multidimensional (MDS) . . . . . . . . . . . . . . .

3.2.1.

3.1.

3.3.1.

4. Clasificación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.1.

9
9
12
15

19
20
20
21
23
25
25
26
26
26
27
28
29
29
31
32
35
37
37
39

40
42
43
47
61
72
79
79
86
86

93
93

CC-BY-NC-ND • PID_00174137

Inteligencia artificial avanzada

4.1.1. Categorización de textos . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
94
Aprendizaje automático para clasificación . . . . . . . . . . . .
4.1.2.
96
4.1.3.
Tipología de algoritmos para clasificación . . . . . . . . . . . .
97
4.2. Métodos basados en modelos probabilísticos . . . . . . . . . . . . . . . . .
98
4.2.1. Naïve Bayes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
98
4.2.2. Máxima entropía . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4.3. Métodos basados en distancias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.3.1.
kNN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.3.2. Clasificador lineal basado en distancias. . . . . . . . . . . . . . . 108
4.3.3.
Clustering dentro de clases . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.4. Métodos basados en reglas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
Árboles de decisión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
AdaBoost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
4.5. Clasificadores lineales y métodos basados en kernels . . . . . . . . . 125
4.5.1. Clasificador lineal basado en producto escalar . . . . . . . . 125
4.5.2. Clasificador lineal con kernel . . . . . . . . . . . . . . . . . . . . . . . . . 130
4.5.3.
Kernels para tratamiento de textos . . . . . . . . . . . . . . . . . . . 135
4.5.4. Máquinas de vectores de soporte . . . . . . . . . . . . . . . . . . . . . 143
Protocolos de test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
4.6.1.
Protocolos de validación. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
4.6.2. Medidas de evaluación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
4.6.3.
Tests estadísticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
4.6.4. Comparativa de clasificadores . . . . . . . . . . . . . . . . . . . . . . . . 161

4.4.1.
4.4.2.

4.6.

5.3.

5.1.

5. Optimización . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
5.1.1.
Tipología de los métodos de optimización . . . . . . . . . . . . 167
5.1.2. Características de los metaheurísticos de optimización 167
5.2. Optimización mediante multiplicadores de Lagrange . . . . . . . . . 168
5.2.1. Descripción del método . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
5.2.2.
Ejemplo de aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
5.2.3.
Análisis del método . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
Recocción simulada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
5.3.1. Descripción del método . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
Ejemplo de aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
5.3.2.
5.3.3.
Análisis del método . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
5.3.4. Código fuente en Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
5.4. Algoritmos genéticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
5.4.1. Descripción del método . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
5.4.2.
Ampliaciones y mejoras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
Ejemplo de aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
5.4.3.
5.4.4.
Análisis del método . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
5.4.5. Código fuente en Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
5.5. Colonias de hormigas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
5.5.1. Descripción del método . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
Ejemplo de aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
5.5.2.
5.5.3.
Análisis del método . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190

CC-BY-NC-ND • PID_00174137

Inteligencia artificial avanzada

5.5.4. Código fuente en Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
5.6. Optimización con enjambres de partículas . . . . . . . . . . . . . . . . . . . . 193
5.6.1. Descripción del método . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
5.6.2.
Ejemplo de aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
5.6.3.
Análisis del método . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
5.6.4. Código fuente en Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
Búsqueda tabú . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
5.7.1. Descripción del método . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
Ejemplo de aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
5.7.2.
5.7.3.
Análisis del método . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
5.7.4. Código fuente en Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205

5.7.

6. Anexo: conceptos básicos de estadística . . . . . . . . . . . . . . . . . . . . . . . 208

Actividades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

Bibli