Modelizado autom´atico mediante programaci´on gen´etica Cruz Enrique Borges Hern´andez1 [email protected]

DeustoTech Universidad de Deusto

10 de noviembre de 2010

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.

1

http://paginaspersonales.deusto.es/cruz.borges/

Contenidos

1

¿Qu´e es un modelo?

2

¿C´omo construimos un modelo?

3

Straight-line Programs

4

Dimension de Vapnik–Chervonenkis

5

Algoritmos evolutivos

6

Ejemplo: Modelado autom´atico de curvas de carga

C.E. Borges

DeustoTech

2/17

¿Qu´e es un modelo? Modelo Matem´atico (Wikipedia 2010) A mathematical model is a description of a system using mathematical language.2 ¡Nunca podemos decir que un modelo es correcto!

Estado Inicial

Estado Final 2

Un modelo matem´ atico es una descripci´ on de un sistema usando lenguaje matem´ atico.

C.E. Borges

DeustoTech

3/17

¿Qu´e es un modelo? Modelo Matem´atico (Wikipedia 2010) A mathematical model is a description of a system using mathematical language.2 ¡Nunca podemos decir que un modelo es correcto!

Estado Inicial

Estado Final 2

Un modelo matem´ atico es una descripci´ on de un sistema usando lenguaje matem´ atico.

C.E. Borges

DeustoTech

3/17

¿Qu´e es un modelo? Modelo Matem´atico (Wikipedia 2010) A mathematical model is a description of a system using mathematical language.2 ¡Nunca podemos decir que un modelo es correcto!

Estado Inicial

Estado Final 2

Un modelo matem´ atico es una descripci´ on de un sistema usando lenguaje matem´ atico.

C.E. Borges

DeustoTech

3/17

¿Qu´e es un modelo? Modelo Matem´atico (Wikipedia 2010) A mathematical model is a description of a system using mathematical language.2 ¡Nunca podemos decir que un modelo es correcto!

Estado Inicial

Estado Final 2

Un modelo matem´ atico es una descripci´ on de un sistema usando lenguaje matem´ atico.

C.E. Borges

DeustoTech

3/17

¿Qu´e es un modelo? Modelo Matem´atico (Wikipedia 2010) A mathematical model is a description of a system using mathematical language.2 ¡Nunca podemos decir que un modelo es correcto!

Estado Inicial Modelo

Estado Final 2

Un modelo matem´ atico es una descripci´ on de un sistema usando lenguaje matem´ atico.

C.E. Borges

DeustoTech

3/17

¿C´omo construimos un modelo? i Formalismo vs Empirismo

Formalismo

Empirismo

1

Axiomatizaci´on.

1

Observaci´on.

2

Desarrollo.

2

Ajuste.

3

Validaci´on.

3

Validaci´ on.

C.E. Borges

DeustoTech

4/17

¿C´omo construimos un modelo? i Formalismo vs Empirismo

Formalismo

Empirismo

1

Axiomatizaci´on.

1

Observaci´on.

2

Desarrollo.

2

Ajuste.

3

Validaci´on.

3

Validaci´ on.

C.E. Borges

DeustoTech

4/17

¿C´omo construimos un modelo? i Formalismo vs Empirismo

Formalismo

Empirismo

1

Axiomatizaci´on.

1

Observaci´on.

2

Desarrollo.

2

Ajuste.

3

Validaci´on.

3

Validaci´ on.

C.E. Borges

DeustoTech

4/17

¿C´omo construimos un modelo? i Formalismo vs Empirismo

Formalismo

Empirismo

1

Axiomatizaci´on.

1

Observaci´on.

2

Desarrollo.

2

Ajuste.

3

Validaci´on.

3

Validaci´ on.

C.E. Borges

DeustoTech

4/17

¿C´omo construimos un modelo? i Formalismo vs Empirismo

Formalismo

Empirismo

1

Axiomatizaci´on.

1

Observaci´on.

2

Desarrollo.

2

Ajuste.

3

Validaci´on.

3

Validaci´ on.

C.E. Borges

DeustoTech

4/17

¿C´omo construimos un modelo? i Formalismo vs Empirismo

Formalismo

Empirismo

1

Axiomatizaci´on.

1

Observaci´on.

2

Desarrollo.

2

Ajuste.

3

Validaci´on.

3

Validaci´ on.

C.E. Borges

DeustoTech

4/17

¿C´omo construimos un modelo? i Formalismo vs Empirismo

Formalismo

Empirismo

1

Axiomatizaci´on.

1

Observaci´on.

2

Desarrollo.

2

Ajuste.

3

Validaci´on.

3

Validaci´ on.

C.E. Borges

DeustoTech

4/17

¿C´omo construimos un modelo? i Formalismo vs Empirismo

Formalismo

Empirismo

1

Axiomatizaci´on.

1

Observaci´on.

2

Desarrollo.

2

Ajuste.

3

Validaci´on.

3

Validaci´ on.

C.E. Borges

DeustoTech

4/17

¿C´omo construimos un modelo? i Formalismo vs Empirismo

Formalismo

Empirismo

1

Axiomatizaci´on.

1

Observaci´on.

2

Desarrollo.

2

Ajuste.

3

Validaci´on.

3

Validaci´ on.

X: No depende de las muestras.

X: F´aciles de construir.

7: Complicados de construir.

7: Depende de las muestras.

C.E. Borges

DeustoTech

4/17

¿C´omo construimos un modelo? i Formalismo vs Empirismo

Formalismo

Empirismo

1

Axiomatizaci´on.

1

Observaci´on.

2

Desarrollo.

2

Ajuste.

3

Validaci´on.

3

Validaci´ on.

X: No depende de las muestras.

X: F´aciles de construir.

7: Complicados de construir.

7: Depende de las muestras.

C.E. Borges

DeustoTech

4/17

¿C´omo construimos un modelo? i Formalismo vs Empirismo

Formalismo

Empirismo

1

Axiomatizaci´on.

1

Observaci´on.

2

Desarrollo.

2

Ajuste.

3

Validaci´on.

3

Validaci´ on.

X: No depende de las muestras.

X: F´aciles de construir.

7: Complicados de construir.

7: Depende de las muestras.

C.E. Borges

DeustoTech

4/17

¿C´omo construimos un modelo? i Formalismo vs Empirismo

Formalismo

Empirismo

1

Axiomatizaci´on.

1

Observaci´on.

2

Desarrollo.

2

Ajuste.

3

Validaci´on.

3

Validaci´ on.

X: No depende de las muestras.

X: F´aciles de construir.

7: Complicados de construir.

7: Depende de las muestras.

C.E. Borges

DeustoTech

4/17

¿C´omo construimos un modelo? i Formalismo vs Empirismo

Formalismo

Empirismo

1

Axiomatizaci´on.

1

Observaci´on.

2

Desarrollo.

2

Ajuste.

3

Validaci´on.

3

Validaci´ on.

Curiosidades Existen varios modelos formalistas sobre el aprendizaje emp´ırico (Cucker y Smale 2002). Existe un modelo formalista correcto: las M´aquinas de Turing

C.E. Borges

DeustoTech

4/17

¿C´omo construimos un modelo? i Formalismo vs Empirismo

Formalismo

Empirismo

1

Axiomatizaci´on.

1

Observaci´on.

2

Desarrollo.

2

Ajuste.

3

Validaci´on.

3

Validaci´ on.

Curiosidades Existen varios modelos formalistas sobre el aprendizaje emp´ırico (Cucker y Smale 2002). Existe un modelo formalista correcto: las M´aquinas de Turing

C.E. Borges

DeustoTech

4/17

¿C´omo construimos un modelo? ii Problemas de regresi´ on

Concepto a aprender y

f (x)

x

C.E. Borges

DeustoTech

5/17

¿C´omo construimos un modelo? ii Problemas de regresi´ on

Muestra

y

x10

f (x)

x9 x2 x x 3 x4 5 x1 x6

x7

x8

x0 x

C.E. Borges

DeustoTech

5/17

¿C´omo construimos un modelo? ii Problemas de regresi´ on

Modelo regresor y

g (x)

x

C.E. Borges

DeustoTech

5/17

¿C´omo construimos un modelo? iii Si conocemos el espacio de b´ usqueda. . .

. . . y es un espacio vectorial3 Muestra sin errores =⇒ Interpolaci´ on. Muestra con errores =⇒ M´ınimos Cuadrados.

. . . y NO es un espacio vectorial Muestra sin errores =⇒ Interpolaci´ on no lineal. Muestra con errores =⇒ Descenso de Gradiente.

3

de dimensi´ on finita

C.E. Borges

DeustoTech

6/17

¿C´omo construimos un modelo? iii Si conocemos el espacio de b´ usqueda. . .

. . . y es un espacio vectorial3 Muestra sin errores =⇒ Interpolaci´ on. Muestra con errores =⇒ M´ınimos Cuadrados.

. . . y NO es un espacio vectorial Muestra sin errores =⇒ Interpolaci´ on no lineal. Muestra con errores =⇒ Descenso de Gradiente.

3

de dimensi´ on finita

C.E. Borges

DeustoTech

6/17

¿C´omo construimos un modelo? iii Si conocemos el espacio de b´ usqueda. . .

. . . y es un espacio vectorial3 Muestra sin errores =⇒ Interpolaci´ on. Muestra con errores =⇒ M´ınimos Cuadrados.

. . . y NO es un espacio vectorial Muestra sin errores =⇒ Interpolaci´ on no lineal. Muestra con errores =⇒ Descenso de Gradiente.

3

de dimensi´ on finita

C.E. Borges

DeustoTech

6/17

¿C´omo construimos un modelo? iii Si conocemos el espacio de b´ usqueda. . .

. . . y es un espacio vectorial3 Muestra sin errores =⇒ Interpolaci´ on. Muestra con errores =⇒ M´ınimos Cuadrados.

. . . y NO es un espacio vectorial Muestra sin errores =⇒ Interpolaci´ on no lineal. Muestra con errores =⇒ Descenso de Gradiente.

3

de dimensi´ on finita

C.E. Borges

DeustoTech

6/17

¿C´omo construimos un modelo? iii Si conocemos el espacio de b´ usqueda. . .

. . . y es un espacio vectorial3 Muestra sin errores =⇒ Interpolaci´ on. Muestra con errores =⇒ M´ınimos Cuadrados.

. . . y NO es un espacio vectorial Muestra sin errores =⇒ Interpolaci´ on no lineal. Muestra con errores =⇒ Descenso de Gradiente.

3

de dimensi´ on finita

C.E. Borges

DeustoTech

6/17

¿C´omo construimos un modelo? iv Si NO conocemos el espacio de b´ usqueda. . .

¿? Regresi´on Simb´olica. La fuerza bruta no es una opci´ on. ¿Cu´al es el conjunto de todos los modelos?

C.E. Borges

DeustoTech

7/17

¿C´omo construimos un modelo? iv Si NO conocemos el espacio de b´ usqueda. . .

¿? Regresi´on Simb´olica. La fuerza bruta no es una opci´ on. ¿Cu´al es el conjunto de todos los modelos?

C.E. Borges

DeustoTech

7/17

¿C´omo construimos un modelo? iv Si NO conocemos el espacio de b´ usqueda. . .

¿? Regresi´on Simb´olica. La fuerza bruta no es una opci´ on. ¿Cu´al es el conjunto de todos los modelos?

C.E. Borges

DeustoTech

7/17

¿C´omo construimos un modelo? iv Si NO conocemos el espacio de b´ usqueda. . .

¿? Regresi´on Simb´olica. La fuerza bruta no es una opci´ on. ¿Cu´al es el conjunto de todos los modelos?

C.E. Borges

DeustoTech

7/17

¿C´omo codificamos los modelos? Straight-line Programs

Estucturas de datos propuestas para modelar Koza 1992: ´arboles. Alonso y col. 2009: straight-line programs (slp).

C.E. Borges

DeustoTech

8/17

Straight-line Programs Propiedades

Straight-line Programs (slp 0 s) Grafo Ac´ıclico Dirigido que codifica una aplicaci´ on.

Figura: Codificaci´ on de un slp.

Figura: Representaci´ on gr´afica de un slp.

 u1 := x ∗ x     u2 := u1 ∗ u1    u3 := u1 ∗ x f1 ≡ u4 := u3 + x      u := u4 + u1   5 u6 := u5 + u4

C.E. Borges

f1 ≡ ∗

+ + +

∗ ∗ x

DeustoTech

9/17

Straight-line Programs Propiedades

Straight-line Programs (slp 0 s) F´aciles de evaluar. . . y de diferenciar.

Figura: Codificaci´ on de un slp.

Figura: Representaci´ on gr´afica de un slp.

 u1 := x ∗ x     u2 := u1 ∗ u1    u3 := u1 ∗ x f1 ≡ u4 := u3 + x      u := u4 + u1   5 u6 := u5 + u4

C.E. Borges

f1 ≡ ∗

+ + +

∗ ∗ x

DeustoTech

9/17

Straight-line Programs Propiedades

Straight-line Programs (slp 0 s) Reutiliza c´alculos ya hechos.

Figura: Codificaci´ on de un slp.

Figura: Representaci´ on gr´afica de un slp.

 u1 := x ∗ x     u2 := u1 ∗ u1    u3 := u1 ∗ x f1 ≡ u4 := u3 + x      u := u4 + u1   5 u6 := u5 + u4

C.E. Borges

f1 ≡ ∗

+ + +

∗ ∗ x

DeustoTech

9/17

Straight-line Programs Propiedades

Straight-line Programs (slp 0 s) Equivalentes a m´aquina de Turing.4

Figura: Codificaci´ on de un slp.

Figura: Representaci´ on gr´afica de un slp.

 u1 := x ∗ x     u2 := u1 ∗ u1    u3 := u1 ∗ x f1 ≡ u4 := u3 + x      u := u4 + u1   5 u6 := u5 + u4 4

f1 ≡ ∗

+ + +

∗ ∗ x

permitiendo la instrucci´ on if como operador.

C.E. Borges

DeustoTech

9/17

¿C´omo comparamos dos modelos? i La Navaja de Ockham

Dada la muestra: f (x)

x

C.E. Borges

DeustoTech

10/17

¿C´omo comparamos dos modelos? i La Navaja de Ockham

¿Qu´e modelo es m´as probable? f (x)

4 Y f (x) = (x − i) i=1

x

C.E. Borges

DeustoTech

10/17

¿C´omo comparamos dos modelos? i La Navaja de Ockham

¿Qu´e modelo es m´as probable? f (x)

f (x) = 1 x

C.E. Borges

DeustoTech

10/17

¿C´omo comparamos dos modelos? i La Navaja de Ockham

Navaja de Ockham (Ockham 1495) Pluralitas non est ponenda sine necessitate.5

5

La pluralidad no se debe postular sin necesidad.

C.E. Borges

DeustoTech

10/17

¿C´omo comparamos dos modelos? ii La dimensi´ on de Vapnik–Chervonenkis

Idea Calificar los modelos de acuerdo a su error emp´ırico m´as una penalizaci´on en funci´ on de su complejidad.

Capacidad de clasificaci´on Cantidad de puntos que el modelo puede clasificar sin error.

C.E. Borges

DeustoTech

11/17

¿C´omo comparamos dos modelos? ii La dimensi´ on de Vapnik–Chervonenkis

Idea Calificar los modelos de acuerdo a su error emp´ırico m´as una penalizaci´on en funci´ on de su complejidad.

Capacidad de clasificaci´on Cantidad de puntos que el modelo puede clasificar sin error.

C.E. Borges

DeustoTech

11/17

¿C´omo comparamos dos modelos? ii La dimensi´ on de Vapnik–Chervonenkis

Idea Calificar los modelos de acuerdo a su error emp´ırico m´as una penalizaci´on en funci´ on de su complejidad.

Capacidad de clasificaci´on Cantidad de puntos que el modelo puede clasificar sin error.

C.E. Borges

DeustoTech

11/17

¿C´omo comparamos dos modelos? ii La dimensi´ on de Vapnik–Chervonenkis

Idea Calificar los modelos de acuerdo a su error emp´ırico m´as una penalizaci´on en funci´ on de su complejidad.

Capacidad de clasificaci´on Cantidad de puntos que el modelo puede clasificar sin error.

C.E. Borges

DeustoTech

11/17

¿C´omo comparamos dos modelos? ii La dimensi´ on de Vapnik–Chervonenkis

Idea Calificar los modelos de acuerdo a su error emp´ırico m´as una penalizaci´on en funci´ on de su complejidad.

Capacidad de clasificaci´on Cantidad de puntos que el modelo puede clasificar sin error.

Teorema (Monta˜na y col. 2009) La dimensi´on de Vapnik–Chervonenkis de un modelo construido mediante slp 0 s es polinomial en el n´ umero de operaciones no escalares que posea.

C.E. Borges

DeustoTech

11/17

Algoritmos Evolutivos i Idea General

Idea General Transformamos un problema de modelado en uno de optimizaci´on. Emular la selecci´on natural buscando el ´ optimo. Poblaci´on de Individuos: slp 0 s. Mecanismo de Calificaci´on: dimensi´ on VC. Mecanismos de Evoluci´on: depende de la estrategia evolutiva.

C.E. Borges

DeustoTech

12/17

Algoritmos Evolutivos i Idea General

Idea General Transformamos un problema de modelado en uno de optimizaci´on. Emular la selecci´on natural buscando el ´ optimo. Poblaci´on de Individuos: slp 0 s. Mecanismo de Calificaci´on: dimensi´ on VC. Mecanismos de Evoluci´on: depende de la estrategia evolutiva.

C.E. Borges

DeustoTech

12/17

Algoritmos Evolutivos i Idea General

Idea General Transformamos un problema de modelado en uno de optimizaci´on. Emular la selecci´on natural buscando el ´ optimo. Poblaci´on de Individuos: slp 0 s. Mecanismo de Calificaci´on: dimensi´ on VC. Mecanismos de Evoluci´on: depende de la estrategia evolutiva.

C.E. Borges

DeustoTech

12/17

Algoritmos Evolutivos i Idea General

Idea General Transformamos un problema de modelado en uno de optimizaci´on. Emular la selecci´on natural buscando el ´ optimo. Poblaci´on de Individuos: slp 0 s. Mecanismo de Calificaci´on: dimensi´ on VC. Mecanismos de Evoluci´on: depende de la estrategia evolutiva.

C.E. Borges

DeustoTech

12/17

Algoritmos Evolutivos i Idea General

Idea General Transformamos un problema de modelado en uno de optimizaci´on. Emular la selecci´on natural buscando el ´ optimo. Poblaci´on de Individuos: slp 0 s. Mecanismo de Calificaci´on: dimensi´ on VC. Mecanismos de Evoluci´on: depende de la estrategia evolutiva.

C.E. Borges

DeustoTech

12/17

Algoritmos Evolutivos ii Mecanismos evolutivos con slp 0 s Γ1 ≡

Γ2 ≡

∗

+ ∗

+

+ ∗

+

∗ ∗ + y

x

+

≡ Γs1

∗

∗ +

∗ ∗

+ x

≡

∗

∗

+

y x

C.E. Borges

y

x

Γs2

DeustoTech

y

13/17

Algoritmos Evolutivos iii Pseudoc´ odigo

No Paralelizable

Crear Poblacion Inicial

Poco inter´ es en Paralelizar Paralelizable

Calificar Poblacion Inicial generaciones Mientras no Fin

Calificar Nueva Poblaci´ on

Operadores Gen´ eticos

Validar Resultado

C.E. Borges

DeustoTech

14/17

Algoritmos Evolutivos iv Ejemplo

1º Generaci´ on y

x

C.E. Borges

DeustoTech

15/17

Algoritmos Evolutivos v Resultados te´ oricos

Teorema (Teorema de los Esquemas (Holland 1992)) Usando los operadores est´andar, un algoritmo evolutivo convergencia hacia un ´ optimo local r´apidamente.

Teorema (No free lunch (Wolpert y Macready 1997)) Para todo problema algoritmo de optimizaci´ on de tipo evolutivo existe el mismo n´ umero de problemas en los que tiene un buen comportamiento que en los que tiene uno malo.

C.E. Borges

DeustoTech

16/17

Modelado autom´atico de curvas de carga i

kwh

t

C.E. Borges

DeustoTech

17/17

Modelado autom´atico de curvas de carga ii kwh

kwh

t

t

kwh

t

C.E. Borges

DeustoTech

18/17

Modelado autom´atico de curvas de carga ii kwh

kwh

t kwh

t kwh

t

C.E. Borges

DeustoTech

t

18/17

¿Preguntas?

¿Preguntas?

¿?

¿? ¿Preguntas?

¿?