Inteligencia-Artificial-Avanzada UOC de Barcelona PDF

Preview

Summary

Inteligencia artificial avanzada de la UOC de Barcelona, todo lo que necesitas saber de inteligencia artificial...

Description

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

Inteligencia artificial avanzada

Índice

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

2.

Introducción a la inteligencia artificial (IA) . . . . . . . . . . . . . . . . .

9

1.1.

Neuronas y transistores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.2.

Breve historia de la IA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

1.3.

Ámbitos de aplicación de la inteligencia artificial . . . . . . . . . . . . .

15

Recomendadores y agrupamientos . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

2.1.

Métricas y medidas de similitud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

2.1.1.

Ejemplo de aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

2.1.2.

Distancia euclídea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

2.1.3.

Correlación de Pearson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

2.1.4.

Procesamiento de datos reales . . . . . . . . . . . . . . . . . . . . . . . .

25

2.1.5.

Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

2.2.

2.3.

3.

Recomendadores basados en memoria . . . . . . . . . . . . . . . . . . . . . . . .

26

2.2.1.

Conceptos generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

2.2.2.

Aproximaciones simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

2.2.3.

Recomendación ponderada . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

2.2.4.

Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

Algoritmos de agrupamiento (clustering) . . . . . . . . . . . . . . . . . . . . . .

29

2.3.1.

Ejemplo de aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

2.3.2.

Conceptos generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

2.3.3.

Agrupamiento jerárquico. Dendrogramas . . . . . . . . . . . .

32

2.3.4.

k-medios (k-means) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

2.3.5.

c-medios difuso (Fuzzy c-means) . . . . . . . . . . . . . . . . . . . . . .

37

2.3.6.

Agrupamiento espectral (spectral clustering) . . . . . . . . . . .

37

2.3.7.

Recomendadores basados en modelos . . . . . . . . . . . . . . . .

39

Extracción y selección de atributos . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

3.1.

Técnicas de factorización matricial . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

3.1.1.

43

Descomposición en valores singulares (SVD) . . . . . . . . .

3.1.2.

Análisis de componentes principales (PCA) . . . . . . . . . . .

47

3.1.3.

Análisis de componentes independientes (ICA) . . . . . .

61

3.1.4.

Factorización de matrices no-negativas (NMF) . . . . . . . .

72

Discriminación de datos en clases . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

79

3.2.1.

Análisis de discriminantes lineales (LDA) . . . . . . . . . . . . .

79

Visualización de datos mutidimensionales . . . . . . . . . . . . . . . . . . . .

86

3.3.1.

Escalamiento multidimensional (MDS) . . . . . . . . . . . . . . .

86

Clasificación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

93

4.1.

93

3.2. 3.3.

4.

7

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

CC-BY-NC-ND • PID_00174137

4.2.

4.3.

4.4.

4.5.

4.6.

5.

Inteligencia artificial avanzada

4.1.1.

Categorización de textos . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

94

4.1.2.

Aprendizaje automático para clasificación . . . . . . . . . . . .

96

4.1.3.

Tipología de algoritmos para clasificación . . . . . . . . . . . .

97

Métodos basados en modelos probabilísticos . . . . . . . . . . . . . . . . .

98

4.2.1.

Naïve Bayes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

98

4.2.2.

Máxima entropía . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

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

Métodos basados en reglas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 4.4.1.

Árboles de decisión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

4.4.2.

AdaBoost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

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

Optimización . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 5.1.

5.2.

5.3.

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

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.

5.4.

5.5.

Descripción del método . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

5.3.2.

Ejemplo de aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173

5.3.3.

Análisis del método . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

5.3.4.

Código fuente en Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176

Algoritmos genéticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 5.4.1.

Descripción del método . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

5.4.2.

Ampliaciones y mejoras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

5.4.3.

Ejemplo de aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

5.4.4.

Análisis del método . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

5.4.5.

Código fuente en Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183

Colonias de hormigas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 5.5.1.

Descripción del método . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186

5.5.2.

Ejemplo de aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187

5.5.3.

Análisis del método . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190

CC-BY-NC-ND • PID_00174137

5.5.4. 5.6.

5.7.

6.

Código fuente en Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191

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

5.7.2.

Ejemplo de aplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202

5.7.3.

Análisis del método . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204

5.7.4.

Código fuente en Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205

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

Actividades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 Bibliografía . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213

Inteligencia artificial avanzada

CC-BY-NC-ND • PID_00174137

7

Introducción

Este módulo está organizado de la forma siguiente: los métodos de búsqueda y optimización se describen en el apartado 2, donde se detallarán las técnicas de extracción de información de bases de datos que contengan información semántica, como por ejemplo web de noticias o las conversaciones entre diversos miembros de una red social. Las técnicas de caracterización de datos se estudiarán en el apartado 3, describiendo las técnicas principales basadas en descomposición de los datos en modos principales. En el apartado 3 también se estudiarán las técnicas de extracción de características y un método de visualización de datos multidimensionales. Los algoritmos de clasificación de datos se presentan en el apartado 4, en el que se estudiarán los principales métodos de clasificación y reconocimiento de patrones. En el apartado 5 se explican algunas técnicas avanzadas de inteligencia evolutiva, algoritmos que utilizan reglas heurísticas inspiradas en el funcionamiento evolutivo de los sistemas biológicos.

Inteligencia artificial avanzada

CC-BY-NC-ND • PID_00174137

9

Inteligencia artificial avanzada

1. Introducción a la inteligencia artificial (IA) .

1.1. Neuronas y transistores Empezaremos planteando la pregunta filosófica fundamental, y así podremos dedicar nuestros esfuerzos a aspectos de carácter cientifico-técnico. . ¿Es físicamente posible que una máquina presente capacidad de abstracción similar a la inteligencia humana?

Para responder esta pregunta, hay que tener en cuenta que el cerebro humano es el sistema de reconocimiento de patrones más complejo y eficiente que conocemos. Los humanos realizamos acciones tan sorprendentes como identificar a un conocido entre la multitud o reconocer de oído el solista de un concierto para violín. En el cerebro humano, las funciones cognitivas se realizan mediante la activación coordinada de unas 90.000.000.000 células nerviosas interconectadas mediante enlaces sinápticos. La activación neuronal sigue complejos procesos biofísicos que garantizan un funcionamiento robusto y adaptativo, y nos permite realizar funciones como el procesado de información sensorial, la regulación fisiológica de los órganos, el lenguaje o la abstracción matemática. La neurociencia actual todavía no aporta una descripción detallada sobre cómo la activación individual de las neuronas da lugar a la formación de representaciones simbólicas abstractas. Lo que sí parece claro es que en la mayoría de procesos cognitivos existe una separación de escalas entre la dinámica a nivel neuronal y la aparición de actividad mental abstracta. Esta separación de escalas supone la ruptura del vínculo existente entre el hardware (neuronas) y el software de nuestro cerebro (operaciones abstractas, estados mentales), y constituye la hipótesis de partida para que los símbolos abstractos puedan ser manipulados por sistemas artificiales que no requieran un substrato fisiológico natural. La posibilidad de manipular expresiones lógicas y esquemas abstractos mediante sistemas artificiales es la que permite la existencia de lo que conocemos como inteligencia artificial. Por supuesto, el cerebro no es el único sistema físico en el que se produce una separación de la dinámica a diferentes escalas. Esta característica también se observa en otros muchos sistemas complejos que presentan fenómenos de autoorganización no lineal. De la misma forma que es posible describir las co-

Lecturas complementarias C. Koch (1999). Biophysics of Computation: Information Processing in Single Neurons. USA: Oxford University Press.

CC-BY-NC-ND • PID_00174137

10

rrientes oceánicas sin necesidad de referirse al movimiento microscópico de las moléculas de agua, el pensamiento abstracto puede analizarse sin necesidad de referirse la activación eléctrica cerebral a nivel neuronal. . En cualquier caso, una de las cuestiones de mayor relevancia y aún no resueltas de la neurociencia actual es saber si existen procesos mentales -como la conciencia, la empatía o la creatividad-, que estén intrínsecamente ligados a la realidad biofísica del sistema nervioso humano y sean por tanto inaccesibles a un sistema artificial.

Otro aspecto importante en el funcionamiento del cerebro humano es el papel que tiene la experiencia y el aprendizaje. El cerebro humano actual no es solo resultado de una evolución biológica basada en alteraciones genéticas, sino también del conjunto de técnicas y conocimientos que la humanidad ha ido acumulando con el tiempo. Aspectos como la cultura o el lenguaje, transmitidas de generación en generación, también determinan la forma en la que se establecen patrones de activación neuronal en nuestro cerebro, y por lo tanto, contribuyen a la emergencia de procesos de abstracción en los que se basan áreas como las matemáticas o la literatura. A nivel biológico, existen diversos mecanismos que permiten la existencia de procesos de activación neuronal dependientes de la experiencia previa y del entrenamiento. El mecanismo principal es conocido como plasticidad sináptica, un fenómeno por el que las conexiones sinápticas entre neuronas modulan su intensidad en función de la actividad que hayan experimentado previamente. De esta forma, cuanto más veces se active un cierto canal de activación neuronal, más fácil resultará activarlo en el futuro e integrarlo a nuevos procesos cognitivos de mayor complejidad. La plasticidad neuronal es la base de la mayoría de procesos de aprendizaje y memoria. A este paradigma se le conoce como aprendizaje reforzado, ya que la actividad sináptica se refuerza en función del número de veces que se establece una conexión entre neuronas. Esta regla –que relaciona la actividad neuronal con la función cognitiva–, se le conoce como regla de Hebb por los trabajos del neuropsicólogo canadiense Donald O. Hebb publicados en su libro de 1949 The organization of behavior. Algunas técnicas de inteligencia artificial como los métodos de aprendizaje supervisado también se basan en reglas similares que permiten modificar de forma adaptativa la forma en que el sistema artificial procesa la información. La inteligencia artificial (IA) es una disciplina académica relacionada con la teoría de la computación cuyo objetivo es emular algunas de las facultades intelectuales humanas en sistemas artificiales. Con inteligencia humana nos referimos típicamente a procesos de percepción sensorial (visión, audición, etc.) y a sus consiguientes procesos de reconocimiento de patrones, por lo que las

Inteligencia artificial avanzada

CC-BY-NC-ND • PID_00174137

11

aplicaciones más habituales de la IA son el tratamiento de datos y la identificación de sistemas. Eso no excluye que la IA, desde sus inicios en la década del 1960, haya resuelto problemas de carácter más abstracto como la demostración de teoremas matemáticos, la adquisición del lenguaje, el jugar a ajedrez o la traducción automática de textos. El diseño de un sistema de inteligencia artificial normalmente requiere la utilización de herramientas de disciplinas muy diferentes como el cálculo numérico, la estadística, la informática, el procesado de señales, el control automático, la robótica...