En ocasiones ocurre que paso mucho tiempo sin publicar,... tanto, que algunos de ustedes dejarán de visitar, por haber perdido la esperanza de que publique nuevamente.
Otras veces puede que llegue a publicar 2 o 3 cosas seguidas, con lo que los últimos posts de alguna forma "entierran" a los previos, y quizá les haga difícil notar que en algún momento estuvieron allí.
Debido a esto, y dado que hay algunas personas interesadas en el tema, que podrían querer no perderse ninguno de los posts, y no necesariamente son usuarios de lectores de RSS, decidí activar un servicio de suscripción por email, que les permitirá leer las primeras líneas de cada post que yo publique, y con ello quizá puedan saber si es de su interés o no, y así decidir si visitan el blog.
También, atendiendo a un par de sugerencias, coloqué una nube con las etiquetas (tags) que uso en el blog. Si ven que alguna de ellas está en un tamaño de letra mayor, significa que hay más posts sobre ese tema. Al hacer clic sobre un tema o etiqueta, cargarán en su navegador todos los posts que tienen esa etiqueta asignada, permitiéndoles de esa forma filtrar la información, y leer sólo aquellos posts que son del tema de su interés en ese momento.
Saludos!
Orestes
lunes, marzo 31, 2008
domingo, marzo 30, 2008
Overfitting o Sobre-ajuste
Agenda:
- Este post empieza con una sacada de navaja.
- Luego explicaré por qué este post es una respuesta a uno de mis lectores, y recomendaré no usar este blog para citas en trabajos académicos.
- Por último explicaré, de la forma más amena de la que sea capaz esta vez, qué es el Overfitting o Sobre-ajuste, o el Sobre-entrenamiento.
Permítanme empezar sacando la susodicha navaja:
Plurality should not be assumed without necessity
- William de Ockham, siglo XIV
O dicho de otra forma: KISS (keep it simple, stupid!). Pero antes de explicar qué tiene que ver esto (la Navaja de Ockham) con el overfitting, permítanme escribir algo sobre el contexto de este post.
Recibí en estos días un correo de Marc (no coloco el nombre completo porque lo correcto es proteger la privacidad), en donde me decía lo siguiente:
He visto tu articulo sobre las svm , pero la verdad es que me falta una
cosa de él, el problema de el sobre-aprendizaje, me puedes comentar algo sobre
el tema? lo necesito para un trabajo
Yo ya tenía en mis planes escribir sobre el overfitting, debido a que es un tema obligado al hablar de aprendizaje. Sin embargo, antes de empezar a hablar sobre ello, quiero dejar algo en claro:
no recomiendo citar lo que se escribe en este blog, en trabajos académicos.
¿Por qué? la razón es muy sencilla. Esto no es una fuente arbitrada. Y adicionalmente, la informalidad con la que están explicadas las cosas no lo hace una buena fuente para elaborar trabajos académicos. Sin embargo es una buena fuente (o al menos pretendo que lo sea lo más posible!) para adquirir entendimiento.Si alguno de ustedes necesita referencias que puedan ser citadas sobre algún aspecto de los conversados acá, déjenme el comentario y gustoso compartiré las fuentes que yo conozca al respecto. ¿Vale?
En fin, ahora si,...
hablemos sobre overfitting: ejemplo "humano"
Hablar de overfitting es hablar de situaciones como la siguiente:
Estamos en un salón de clases, recibiendo datos de un profesor que escribe sobre la pizarra.
Nosotros podemos aprender los principios generales que él trata de transmitir usando su voz, sus gestos, y los rastros que deja la tiza sobre la pizarra durante algunos de los erráticos gestos.
Sin embargo, vemos con cierta frecuencia que hay personas que copian cada frase de lo que indica el profesor. Según mi experiencia docente me ha hecho reflexionar, hay muchas cosas que uno como profesor dice, que no es realmente necesario copiar (algunas hasta el profesor se arrepentiría de decirlas!).
Un estudiante podría copiar incluso esquemas de la gesticulación, cuantas veces la persona ha respirado en una pausa, o la intensidad de un ataque de tos. Obviamente estoy exagerando, pero ese es el punto: la exageración.
Es esa es la parte que sobra, cuando hay "sobre-entrenamiento", "sobre-aprendizaje", o "sobre-ajuste". Es decir, la parte "over" del overfitting.
Uno no necesita aprender los gestos y ruidos (palabras innecesarias) del profesor. Ellos incluso podrían distorcionar el concepto general que se trata de explicar.
En nuestro cuaderno, deberíamos ser lo más simples posibles. ¡Apéguense a la navaja de Ockham, muchachos!.
ejemplo inhumano...
De igual forma, uno puede tener una serie de datos, y usar un modelo matemático para "aprender" su patrón. Digamos que queremos hacer una regresión. El mínimo error siempre es deseable, pero no a cualquier precio. Uno podría tener puntos que son bastante cercanos a un modelo lineal, aunque los puntos no están exactamente sobre la recta que hemos trazado, lo cuál daría una cierta cantidad de error.
El caso del sobre-ajuste, sería uno en el que decidiéramos usar una función más compleja que una simple recta, para que pase por todos los puntos, tal y como se ve en la figura de abajo (cortesía de wikipedia):
Hablar de overfitting es hablar de situaciones como la siguiente:
Estamos en un salón de clases, recibiendo datos de un profesor que escribe sobre la pizarra.
Nosotros podemos aprender los principios generales que él trata de transmitir usando su voz, sus gestos, y los rastros que deja la tiza sobre la pizarra durante algunos de los erráticos gestos.
Sin embargo, vemos con cierta frecuencia que hay personas que copian cada frase de lo que indica el profesor. Según mi experiencia docente me ha hecho reflexionar, hay muchas cosas que uno como profesor dice, que no es realmente necesario copiar (algunas hasta el profesor se arrepentiría de decirlas!).
Un estudiante podría copiar incluso esquemas de la gesticulación, cuantas veces la persona ha respirado en una pausa, o la intensidad de un ataque de tos. Obviamente estoy exagerando, pero ese es el punto: la exageración.
Es esa es la parte que sobra, cuando hay "sobre-entrenamiento", "sobre-aprendizaje", o "sobre-ajuste". Es decir, la parte "over" del overfitting.
Uno no necesita aprender los gestos y ruidos (palabras innecesarias) del profesor. Ellos incluso podrían distorcionar el concepto general que se trata de explicar.
En nuestro cuaderno, deberíamos ser lo más simples posibles. ¡Apéguense a la navaja de Ockham, muchachos!.
ejemplo inhumano...
De igual forma, uno puede tener una serie de datos, y usar un modelo matemático para "aprender" su patrón. Digamos que queremos hacer una regresión. El mínimo error siempre es deseable, pero no a cualquier precio. Uno podría tener puntos que son bastante cercanos a un modelo lineal, aunque los puntos no están exactamente sobre la recta que hemos trazado, lo cuál daría una cierta cantidad de error.
El caso del sobre-ajuste, sería uno en el que decidiéramos usar una función más compleja que una simple recta, para que pase por todos los puntos, tal y como se ve en la figura de abajo (cortesía de wikipedia):
En esta curva de 8vo grado (polinomio de grado 8), estamos estimando 9 parámetros para obtener la función,... para ajustarla sobre 10 puntos. Es decir, estamos consiguiendo un modelo matemático casi tan complejo como los datos que representa. Si tenemos en cuenta que un modelo se supone que debe representar de forma simple el comportamiento de los datos (una especie de "resumen" del comportamiento de los mismos), pareciera que acá terminamos teniendo un modelo "poco eficiente".Sin embargo, no es sólo un problema de poca eficiencia. Si tenemos en cuenta que estos modelos frecuentemente se utilizan para predecir la "aparición" de otros puntos que por los momentos desconocemos, nos daremos cuenta de algo muy interesante:
A medida que aumentamos la complejidad de la función, la capacidad de pronosticar (o generalizar) al principio aumenta, pero llegado cierto punto, empieza a decaer. El principio de la navaja de Ockham, mostrado gráficamente.
¿Por qué?
La respuesta no es difícil. En la gráfica siguiente, si proyectamos como se mueve la función elaborada, entre el 0 y el 1 (en el eje "x"), vemos que se aleja bastante de la recta que pasa cerca de los puntos. Pero ¿realmente las distancias que tienen los puntos de la recta dan pie a que pensemos que el punto que va entre el 0 y el 1 esté tan lejos del valor que nos predice el modelo lineal?
La respuesta es no, inclusive de forma intuitiva, aunque, como veremos, no es necesario acudir al no tan común "sentido común" para confiar en lo que dije arriba.
típico overfitting en redes neurales
Las redes neurales artificiales han sido utilizadas con frecuencia para ajustarse a funciones. Uno consigue medir en un proceso ciertos datos, y trata de estimar la función que hay "detrás" de los datos, para tratar de predecir los datos en otros lugares en donde no hemos medido por alguna razón (imposibilidad temporal, técnica, financiera, riesgo, etc.).
Bien, típicamente esto se hace de la siguiente forma:
- Se elige un subconjunto de los datos, de forma aleatoria, para conformar el "conjunto de prueba" o "conjunto de validación".
- El resto de los datos conforman el "conjunto de entrenamiento".
- Se dan valores iniciales a los parámetros de todas las neuronas de la red.
- Se "muestra" un dato a la red, y se compara la salida de la red con la salida que debería haber dado. La diferencia entre lo deseado y lo que se ha obtenido de la red, se utiliza como información para regañar a las neuronas que se portan mal (ajustando los parámetros).
- Se repite el paso anterior, hasta que el error de la salida de la red se estabiliza en un margen aceptable.
Este proceso puede ser muy vario-pinto en las estrategias a seguir para:
- elegir el número y disposición de neuronas,
- elegir el kernel a utilizar,
- definir la sensibilidad que tienen los ajustes respecto a los errores cometidos por la red,
- y decidirse entre la acumulación de ajustes luego de "ver" todos los datos de entrenamiento versus la realización de ajusted luego de "ver" cada dato individual.
La experiencia tiende a mostrar el siguiente patrón:
- Con los primeros ajustes, poco a poco crece la eficiencia con que se logran predecir los resultados del conjunto de validación.
- Llegado cierto punto, no se logra mayor mejora en la eficiencia de la red ante el conjunto de validación. Sin embargo, sigue mejorando la eficiencia ante el conjunto de entrenamiento.
- Más allá de ese punto, aunque la eficiencia con que la función se aproxima a los datos de entrenamiento se puede acercar a la perfección, el resultado ante el conjunto de validación ha empezado a empeorar.
El comportamiento del paso 3, es una muestra numérica del concepto que vimos anteriormente de forma intuitiva, como sobre-ajuste. Empieza a ocurrir, si lo vemos en la figura de abajo (también cortesía de wikipedia), en el momento en el que la curva de color rojo deja de bajar. Esta mide el error de la red en el conjunto de validación.
He acá al principio de la navaja de Ockham, demostrado estadísticamente.
Procesos "constructivos"
Este comportamiento también puede verse en los procesos de entrenamiento constructivos, que van generando neuronas en la red (o ramificaciones en un árbol), haciéndola cada vez más compleja, para ir aprendiendo el patrón. Al inicio, con pocas neuronas (o en árboles de clasificación, con pocas hojas) ambas eficiencias crecen, y la de entrenamiento logra la perfección absoluta, mientras que en algún momento el bulto del conjunto de validación se nos ha caído en el camino.
En la imágen de arriba (nuevamente cortesía de wikipedia) se observa claramente como el clasificador representado por la línea verde se ajusta a la perfección a la data de entrenamiento. Sin embargo, el clasificador de la línea negra (mucho más sencillo), probablemente tendrá mejor capacidad de geralización. Éste es un buen ejemplo del tipo de superficies clasificadoras que resultan cuando una red tiene demasiadas neuronas, y demasiado entrenadas. [adición del autor el 31-03-08]
Esto que acabo de comentar es el tipo de procesos como el que hablamos sobre el polinomio de grado 8. Ir hacia la derecha en el gráfico de arriba, es ir aumentando el nivel del polinomio a usar para hacer la regresión sobre los datos.
¿Y cómo hacemos?
La manera de apegarse a la navaja de Ockham más evidente, es ir revisando el comportamiento de nuestro modelo sobre data de validación.
Se recomiendan técnicas como:
- cross-validation,
- early stopping,
- Bayesian priors en los parámetros
- model comparison
En un trabajo que estoy realizando actualmente en conjunto con el Prof. Ubaldo García Palomares, hemos incluído dentro de un algoritmo de generación y entrenamiento de una red neural de una capa oculta, para clasificación binaria, unas instrucciones que permiten que el algoritmo se detenga cuando ya no es posible mejorar la capacidad de generalización. Pero eso es parte de otra historia...
¡Espero que esto pueda ayudarte, Marc!
martes, marzo 25, 2008
Usando creyones para entrenar máquinas
Tuve la fortuna de toparme con un post del blog de Greg Linden, en el que se nos muestra un excelente ejemplo de lo que es el Aprendizaje Interactivo aplicado al procesamiento/reconocimiento de imágenes, mostrado por Dan Olsen de la Brigham Young University.
Se trata del uso de una interfaz para el usuario, en la que éste usa herramientas tipo creyón. En uno de los videos, se muestran imágenes donde una mano está sobre un escritorio. Un creyón es utilizado para marcar áreas de la imágen que el usuario quiere indicar que corresponden a piel. Otro es utilizado para marcar áreas de la imágen que el usuario quiere indicar que corresponden al "fondo" (cualquier cosa menos piel).
Una vez la máquina recibe esa información, la analiza, y en base a las características que tenían las áreas marcadas con ambos creyones clasifica el resto de la imágen como "piel" o "fondo". El usuario tiene entonces la oportunidad de usar los creyones para "corregir" los errores que cometió el software, marcando con el creyón "piel" aquellos puntos que la máquina clasificó como "fondo" pero eran "piel". Obviamente también se marca con el creyón ""fondo" aquellos puntos que la máquina clasificó como "piel" pero eran "fondo".
Luego de 4 minutos, el clasificador obtuvo excelentes resultados en otras imágenes donde aparece la mano, en diferentes posiciones, y una última en la que no aparece mano alguna. Siempre con alguno que otro pixel mal clasificado, pero realmente asombroso, a mi modo de ver.
Otro de los videos muestra un uso genial de este tipo de herramientas, para enseñar a un robot a manejar. Se muestran dos imágenes tomadas de la cámara que tiene el robot. En una se usan dos creyones: uno para marcar terreno "seguro", y uno para marcar terreno "inseguro". En esa misma imágen, luego de usar los creyones, se colorea la imágen según la máquina clasifica cada pixel como "seguro" o "inseguro". La otra imágen se usa para manejar al robot, indicándole hacia dónde debe ir.
El usuario, luego de marcar como "inseguro" aquellos lugares que se desea que el robot esquive, y como "seguro" aquellos lugares por los cuales el robot puede andar, le da la instrucción de caminar. En "tiempo real", las imágenes van actualizándose por la entrada de video, y el clasificador las va coloreando, y en base a ello, ajusta la trayectoria del robot. Si en algún lugar del camino, el usuario detecta que el clasificador ha cometido errores, detiene el robot y usa los creyones para corregir, y luego puede continuar.
¿Será que pronto usaremos esto para un rover en la Luna o Marte?
Si es así, ¡ojalá que algún día uno de los modelos matemáticos de clasificación que manden de viaje sea uno mío! Soñar no cuesta nada... ¿eh?
Visíten el post. Está en este URL:
http://glinden.blogspot.com/2007/12/interactive-machine-learning-talk.html
Se trata del uso de una interfaz para el usuario, en la que éste usa herramientas tipo creyón. En uno de los videos, se muestran imágenes donde una mano está sobre un escritorio. Un creyón es utilizado para marcar áreas de la imágen que el usuario quiere indicar que corresponden a piel. Otro es utilizado para marcar áreas de la imágen que el usuario quiere indicar que corresponden al "fondo" (cualquier cosa menos piel).
Una vez la máquina recibe esa información, la analiza, y en base a las características que tenían las áreas marcadas con ambos creyones clasifica el resto de la imágen como "piel" o "fondo". El usuario tiene entonces la oportunidad de usar los creyones para "corregir" los errores que cometió el software, marcando con el creyón "piel" aquellos puntos que la máquina clasificó como "fondo" pero eran "piel". Obviamente también se marca con el creyón ""fondo" aquellos puntos que la máquina clasificó como "piel" pero eran "fondo".
Luego de 4 minutos, el clasificador obtuvo excelentes resultados en otras imágenes donde aparece la mano, en diferentes posiciones, y una última en la que no aparece mano alguna. Siempre con alguno que otro pixel mal clasificado, pero realmente asombroso, a mi modo de ver.
Otro de los videos muestra un uso genial de este tipo de herramientas, para enseñar a un robot a manejar. Se muestran dos imágenes tomadas de la cámara que tiene el robot. En una se usan dos creyones: uno para marcar terreno "seguro", y uno para marcar terreno "inseguro". En esa misma imágen, luego de usar los creyones, se colorea la imágen según la máquina clasifica cada pixel como "seguro" o "inseguro". La otra imágen se usa para manejar al robot, indicándole hacia dónde debe ir.
El usuario, luego de marcar como "inseguro" aquellos lugares que se desea que el robot esquive, y como "seguro" aquellos lugares por los cuales el robot puede andar, le da la instrucción de caminar. En "tiempo real", las imágenes van actualizándose por la entrada de video, y el clasificador las va coloreando, y en base a ello, ajusta la trayectoria del robot. Si en algún lugar del camino, el usuario detecta que el clasificador ha cometido errores, detiene el robot y usa los creyones para corregir, y luego puede continuar.
¿Será que pronto usaremos esto para un rover en la Luna o Marte?
Si es así, ¡ojalá que algún día uno de los modelos matemáticos de clasificación que manden de viaje sea uno mío! Soñar no cuesta nada... ¿eh?
Visíten el post. Está en este URL:
http://glinden.blogspot.com/2007/12/interactive-machine-learning-talk.html
lunes, marzo 24, 2008
Nuevos enlaces
Hay ahora en el costado derecho del blog, nuevos links...
Más links de Investigación de Operaciones:
The OR Society
http://www.orsoc.org.uk/orshop/(txcjre45jcxf1q55fpzu32zc)/orhomepage2.aspx
Operations Research/Management Science Today
http://www.lionhrtpub.com/ORMS.shtml
International Federation of Operational Research Society
http://www.ifors.org/
Asociación Latino-Iberoamericana de Investigación Operativa
http://www-2.dc.uba.ar/alio/
International Society on Multiple Criteria Decision Making
http://www.terry.uga.edu/mcdm/
Military Operations Research Society
http://www.mors.org/
Mathematical Programming Society
http://www.mathprog.org/
Omega Rho International Honor Society
http://omegarho.informs.org/
TutORial IFORS
http://www.ifors.ms.unimelb.edu.au/tutorial/
WWW for Operations Research and Management Science
http://www.worms.ms.unimelb.edu.au/
Operations Research/Management Science Today
http://www.lionhrtpub.com/ORMS.shtml
Nueva sección de Links de ciencias relacionadas a I.O.
Clinical Operational Research Unit
http://www.ucl.ac.uk/operational-research/
Society for Industrial and Applied Mathematics
http://www.siam.org/
Center for Operations Research and Econometrics
http://www.uclouvain.be/en-core.html
Decision Sciences Institute
http://www.decisionsciences.org/
Institute of Industrial Engineers
http://www.iienet2.org/Default.aspx
Phramaceutical Management Science Association
http://www.pmsa.net/
Production and Operations Management Society
http://www.poms.org/
Game Theory Society
http://www.gametheorysociety.org/
Nuevo link personal
Mi Tlog (TumblrLog)
http://ozono27.tumblr.com
Más links de Investigación de Operaciones:
The OR Society
http://www.orsoc.org.uk/orshop/(txcjre45jcxf1q55fpzu32zc)/orhomepage2.aspx
Operations Research/Management Science Today
http://www.lionhrtpub.com/ORMS.shtml
International Federation of Operational Research Society
http://www.ifors.org/
Asociación Latino-Iberoamericana de Investigación Operativa
http://www-2.dc.uba.ar/alio/
International Society on Multiple Criteria Decision Making
http://www.terry.uga.edu/mcdm/
Military Operations Research Society
http://www.mors.org/
Mathematical Programming Society
http://www.mathprog.org/
Omega Rho International Honor Society
http://omegarho.informs.org/
TutORial IFORS
http://www.ifors.ms.unimelb.edu.au/tutorial/
WWW for Operations Research and Management Science
http://www.worms.ms.unimelb.edu.au/
Operations Research/Management Science Today
http://www.lionhrtpub.com/ORMS.shtml
Nueva sección de Links de ciencias relacionadas a I.O.
Clinical Operational Research Unit
http://www.ucl.ac.uk/operational-research/
Society for Industrial and Applied Mathematics
http://www.siam.org/
Center for Operations Research and Econometrics
http://www.uclouvain.be/en-core.html
Decision Sciences Institute
http://www.decisionsciences.org/
Institute of Industrial Engineers
http://www.iienet2.org/Default.aspx
Phramaceutical Management Science Association
http://www.pmsa.net/
Production and Operations Management Society
http://www.poms.org/
Game Theory Society
http://www.gametheorysociety.org/
Nuevo link personal
Mi Tlog (TumblrLog)
http://ozono27.tumblr.com
Notas sobre Investigación de Operaciones
Hay un excelente material (resumido y fácil de entender), que ha sido publicado por el profesor J. E. Beasley en su sitio web. Se trata del material de un curso que el dicta a nivel universitario, y recoge información bastante útil.
No sólo abarca la mayoría de los temas "clásicos" de I.O., sino que también proporciona información sobre la historia de la I.O., así como de las instituciones y asociaciones que se han formado en el mundo por gente de esta área.
Si están empezando en esto de Investigación de Operaciones, y no les molesta leer un poco de inglés, les recomiendo altamente esta página (aunque sea poco vistosa).
No sólo abarca la mayoría de los temas "clásicos" de I.O., sino que también proporciona información sobre la historia de la I.O., así como de las instituciones y asociaciones que se han formado en el mundo por gente de esta área.
Si están empezando en esto de Investigación de Operaciones, y no les molesta leer un poco de inglés, les recomiendo altamente esta página (aunque sea poco vistosa).
domingo, marzo 23, 2008
¿Qué son las SVM?
Por ahí Alfredo me preguntó qué eran las SVM o Support Vector Machines... y realmente ese debería ser tema obligado para este blog! así que ya es hora de acometer esa tarea.
Una especie de definición
Las SVM (o Máquinas de Vectores de Soporte) son un tipo de Máquinas de Aprendizaje. En particular son de esas que necesitan primero entrenarse con situaciones en las que se les dice la respuesta correcta sobre muchos ejemplos, y una vez ella se ha entrenado, entra en fase de "uso", y simplemente se convierte en una caja que devuelve la respuesta ante un nuevo caso (en pocas palabras, es un método de aprendizaje supervisado).
Quienes inventaron las SV fueron Vladimir Vapnik (una persona orientada hacia la estadística) y sus compañeros de AT&T. El método se basa en el uso de programación matemática, formulada de forma que la interpretación estadística del modelo resulta particularmente apropiada. El modelo está rigurosamente sustentado por las teorías estadísticas de aprendizaje propuestas por Vapnik.
Importancia
¿Qué tienen de particular que las hace famosas? Bueno... desde que fueron inventadas, superaron con creces la eficiencia de los algoritmos antecesores, tanto en tareas de clasificación, como de regresión. Hasta el momento, las SVMs no han sido superadas sino por ellas mismas, con los diferentes ajustes y variaciones que se han venido haciendo.
¿y para qué sirven?
Bueno, los modelos SVM nos servirán para predecir datos, siempre y cuando hayamos entrenado a la máquina. Esta predicción puede ser de varios tipos:
¿y cómo funcionan?
La forma en que trabaja es muy interesante. Supongamos que tenemos la tarea de realizar predicciones de clasificación binaria (p.e.: tenemos valores de un exámen médico rutinario de una persona, y queremos saber si tiene diabetes o no). Vamos a imaginarnos que los valores recogidos en el exámen son sólo 2, en lugar de sopotocientos. Cada paciente que efectivamente tiene diabetes lo podemos poner en un plano cartesiando (donde cada eje es uno de los dos valores que recoge el exámen médico). Colocamos a los pacientes que efectivamente tenían diabetes como círculos negros en el plano en las coordenadas que corresponden a cada uno de ellos (según sus resultados de exámen), y a los que no tenían diabetes, como rombos de centro blanco. Vamos a tener algo así:
las SVM encuentran una "superficie" que intenta separar los ejemplos negativos y positivos con el margen más grande posible a ambos lados del hiperplano. En este caso, bi-dimencional, la "superficie" sería una línea. En un caso 3D (tres atributos para cada paciente) sería un plano. En un caso de más de 3 dimensiones, sería un hiper-plano o hiper-superficie con el número apropiado de variables.
Hay muchas formas de hacer esto, propuestas por métodos estadísticos, por la gente de redes neurales, por la gente de optimización, etcétera. Lo que distingue a las SVMs es que el hiper-plano resultante se consigue logrando, como dije antes, que el margen que separa los datos es el mayor posible.
...entendiendo lo del margen, o ¿por qué lejos es mejor?
¿Y qué es eso de "margen"? Bueno, primero acudamos a la intuición, y luego definiré la palabra "margen" en este contexto. Para los datos que tenemos en el ejemplo, podríamos tener varias posibles superficies (infinitas), pero tomemos como ejemplo estas dos:
Preguntémonos ¿cuál es mejor? Vapnik demuestra estadísticamente, que mientras más lejos esté el hiper-plano de los puntos a los que clasifica, mejor. En este caso, pareciera que la Superficie A es mejor que la Superficie B.
Pero dije que iba a irme primero por la intuición: preguntémonos.... ¿Por qué lejos es mejor?
Para verlo intuitivamente, podemos imaginarnos el caso extremo, es decir, que la superficie estuviese "adherida" a algunos de los puntos de uno de los conjuntos, como en la siguiente figura:
Tengamos en cuenta que esos datos son de los pacientes para los cuales, hasta ahora, sabemos si tienen diabetes o no. Si dejamos que la superficie clasificadora esté allí, "adherida" a los pacientes sanos, intuitivamente podemos imaginar que es bastante probable que aparezca algún paciente con características similares a las de alguno de los pacientes a los cuales está "adherido" el hiper-plano. Pero cuando digo "similar", intuitivamente estamos aceptando que no hay dos pacientes exactamente iguales. Debe haber alguna pequeña diferencia. ¿Cierto?
¿Y si esa pequeña diferencia hiciera que el paciente estuviese justo un ligeramente más allá de la superficie separadora? Si eso ocurriera, la máquina diría que ese paciente pertenece al grupo de los que tienen diabetes, es decir, diría que es un "círculo negro", cuando en realidad el afortunado paciente podría no tener diabetes. Estaríamos dando un falso positivo con cierta frecuencia.
Si el hiper-plano estuviese "adherido" a los pacientes del grupo de entrenamiento que eran diabéticos, estaríamos haciendo una máquina que produciría concierta frecuencia falsos negativos (porque pacientes muy parecidos a los que ya tienen diabetes, podrían estar ya el otro lado de la superficie separadora). Uno no desearía darles falsas expectativas a un paciente, así que esto tampoco es conveniente.
Para lograr alejar la superficie de los puntos de ambos conjuntos, Vapnick define el "margen" a maximizar como la distancia entre los dos hiper-planos, paralelos al hiper-plano separador, que están, cada uno, adherido a los puntos de uno de los conjuntos. En las Superficies A y B, el "margen" vendría a ser la distancia entre las líneas punteadas que se muestran abajo:
Como podemos ver, en el caso de la Superficie A, está mucho mejor que en la B. El método, adicionalmente, coloca la superficie, en general, en la mitad de esa distancia.
¿y dónde dejamos a las Redes Neurales Artificiales?
Obviamente, las SVM están relacionadas con las redes neurales. De hecho, un modelo de SVM que use una sigmoide (aproximación a la función escalón que mencioné en mi post sobre redes neurales) como función para el cálculo de la salida, es equivalente a un perceptron (una neurona de salida binaria). En otras palabras, los parámetros para una neurona de clasificación (perceptrón), podríamos hallarlos mediante el uso del método SVM.
Cuando no es posible separar completamente los puntos de los dos conjuntos, la forma matemática en que se plantean los SVM obtiene excelentes resultados, minimizando los errores.
Kernels, o ¿qué hago cuando necesito un hiper-plano torcido?
Si nos encontráramos en un caso en el que los datos no pudieran ser separados por un hiper-plano, podría ser que una superficie no-lineal pudiera separar los conjuntos, como en el ejemplo de abajo:
.. lo que se hace en SVM (y en muchas otras técnicas) es transformar el espacio de los atributos (lo que llaman el kernel). Esto suena complicado, pero si nos fijamos en el ejemplo, podemos ver que una elipse podría resolver el problema, de la siguiente forma:
Esa sería la superficie no-lineal que necesitamos. Todo lo que hemos venido hablando, ha sido referido a hiper-planos, y claramente la elipse no es un hiper-plano. Sin embargo, sabemos que la elipse es una figura "Cónica", expresada más o menos así (en nuestro eje cartesiano del ejemplo):
donde {a, b, c, d, e} es un conjunto de constantes, y {x1, x2} nuestras variables (discúlpenme por renegar del par {x,y} jejeje).
En general, cualquier superifice cónica, termina siendo algo como esto:
Ahora, esto ni de casualidad es lineal en un espacio definido por las variables {x1, x2}. Pero si nos imaginamos un espacio donde las variables son esas dos, mas 3 variables nuevas (tres dimensiones) extra: {x3, x4, x5}, donde cada una de ellas representa a los términos cuadráticos de la expresión de arriba, tenemos:
x3 = x1^2
Y volviendo a escribir la ecuación cónica genérica (o cuadrática, como sería mejor llamarle), tenemos que nos queda así:
¡Y acá estaremos todos de acuerdo con que se trata de una ecuación bastante lineal! Dense cuenta de que lo que se desprende de todo esto, es que un hiper-plano en este espacio de atributos ampliado, equivale a una elipse en nuestro espacio bi-dimensional (definido tan sólo por {x1, x2}).
Si pudiésemos representar gráficamente lo que ocurre en este espacio 5-dimensional, sería algo así:
Repito: acá aplican ahora todos los conceptos de margen y linealidad que se habían manejado anteriormente. Como puede verse, acá el SVM, aunque modelaría un simple hiper-plano separando grupos de puntos, estaría comportándose como una superficie no-lineal.
Algunas consideraciones de modelaje del SVM y el problema a optimizar
Sin embargo, quiero hacer notar una cosa importante: este kernel cuadrático resultó bastante apropiado para el problema del ejemplo. Pero podría no ser suficiente para otro problema. En general, la estrategia de complicar el kernel depende de nuestra suposición de la estructura y complejidad de los datos, y siempre aumenta la dificultad de obtener un resultado.
Si tenemos 9 atributos principales, resolver el problema cuadrático implica añadir una cantidad mucho más grande de variables "extra", representando los cuadrados de los principales y los productos entre ellas.
Un ejemplo de un problema que no podría resolverse con un kernel cuadrático, sería este, en el que se necesitaría de un kernel basado en funciones de base radial (gaussianas):
Separar conjuntos con superficies no-lineales, es algo que se ha logrado con perceptrones clásicos multi-capa (redes neurales). Sin embargo, dado que cada perceptrón posee una función de transferencia sigmoidal (buscando comportarse como una función escalón), la optimización a la que debe acudirse en las redes neurales tipo perceptrón, equivale a una optimización de este tipo:
donde o(x) es la salida de la red (su propuesta de clasificación), y c(x) es la verdadera clasificación del individuo "x". Los w, theta, nu y tau son simplemente parámetros de las neuronas del perceptrón multicapa.
¿por qué la superficie a optimizar es así? Fácil: Porque es el error cuadrático de clasificación. El algoritmo de optimización (Backpropagation y sus primos, típicamente) va ajustando el parámetro de alguna neurona o peso de dendrita, hasta que ¡Zas! una de las neuronas cambia su salida de 0 a 1, o de 1 a 0, y con ello la respuesta de la red, posiblemente. Se sigue moviendo levemente (según un parámetro de paso) los parámetros, y posiblemente no pasa nada, hasta que se cruza otro límite de alguna de las sigmoides, y ¡Zas! ocurre otro cambio de 0 a 1, o de 1 a 0.
Mientras cambias los parámetros pero no pasa nada, se comporta de forma "estacionaria" la función del error (derivada = 0). Luego encuentras otro lugar, donde hay el cambio de respuesta, y la función de error cambia de forma brusca (derivada = mucho), ya que es la subida del "escalón" aproximado de la sigmoide. Nótese que idealmente el sigmoide sería lo más parecido a una función escalón, pero para que la derivada sea manejable numéricamente por los algoritmos de backpropagation, en el lugar donde está el umbral, se disminuye bastante, por lo que la red termina teniendo respuestas "difusas" cuando los elementos caen en el borde del umbral de alguna de las neuronas. Esto, a mi modo de ver, es indieseable.
Así pues, entrenar un perceptrón multi-capa implica un problema de optimización:
Es mucho más atractivo resolver un problema como el de las SVM, porque es optimización cuadrática con restricciones lineales,... es decir: de los problemas más fáciles de solucionar. Más adelante les hablaré de un método que utiliza Programación Lineal para generar perceptrones multi-capa, sin usar Backpropagation. Si el problema de resolver una red neural, hubiese sido atacado inicialmente, por gente de investigación de operaciones, dudo que hubiésen optado por algo como el Backpropagation, realmente.
¿Y cómo es eso de "Vectores de Soporte"?
Ahora, para cerrar, quiero aclarar la duda que siempre surge cuando uno conoce a las SVMs:
¿por qué el nombre?
La respuesta es sencilla: si asumimos que cada uno de los ejemplos de los que disponemos (círculos oscuroes y rombos blancos) es un vector en el espacio, resolver SVMs es: encontrar los vectores en los que podamos apoyar los hiper-planos que definan el mayor margen de separación. Es decir, buscamos los vectores en los cuales "soportar" los hiper-planos paralelos, uno hacia un conjunto, y uno hacia el otro, para trazar justo en el medio de ambos, nuestro hiper-plano de separación. Veámoslos señalados por círculos rojos en la siguiente figura:
¡Ahí los tienen!
Ahora lo de "Máquinas de Vectores de Soporte" suena menos oscuro ¿verdad?
En verdad espero que esta explicación les haya sido de utilidad ¡y disculpen lo extenso!
Para los que deseen profundizar, les recomiendo esta página: http://www.dtreg.com/svm.htm
Es mucho menos "básica" la explicación, pero mucho más completa.
NOTA: Si alguien detecta en mi post algún error, no duden en contactarme para decírmelo, ¿vale? ¡Gracias de antemano!.
Una especie de definición
Las SVM (o Máquinas de Vectores de Soporte) son un tipo de Máquinas de Aprendizaje. En particular son de esas que necesitan primero entrenarse con situaciones en las que se les dice la respuesta correcta sobre muchos ejemplos, y una vez ella se ha entrenado, entra en fase de "uso", y simplemente se convierte en una caja que devuelve la respuesta ante un nuevo caso (en pocas palabras, es un método de aprendizaje supervisado).
Quienes inventaron las SV fueron Vladimir Vapnik (una persona orientada hacia la estadística) y sus compañeros de AT&T. El método se basa en el uso de programación matemática, formulada de forma que la interpretación estadística del modelo resulta particularmente apropiada. El modelo está rigurosamente sustentado por las teorías estadísticas de aprendizaje propuestas por Vapnik.
Importancia
¿Qué tienen de particular que las hace famosas? Bueno... desde que fueron inventadas, superaron con creces la eficiencia de los algoritmos antecesores, tanto en tareas de clasificación, como de regresión. Hasta el momento, las SVMs no han sido superadas sino por ellas mismas, con los diferentes ajustes y variaciones que se han venido haciendo.
¿y para qué sirven?
Bueno, los modelos SVM nos servirán para predecir datos, siempre y cuando hayamos entrenado a la máquina. Esta predicción puede ser de varios tipos:
- predicción de clasificación binaria
- predicción de clasificación multi-categoría
- predicción de regresión general.
¿y cómo funcionan?
La forma en que trabaja es muy interesante. Supongamos que tenemos la tarea de realizar predicciones de clasificación binaria (p.e.: tenemos valores de un exámen médico rutinario de una persona, y queremos saber si tiene diabetes o no). Vamos a imaginarnos que los valores recogidos en el exámen son sólo 2, en lugar de sopotocientos. Cada paciente que efectivamente tiene diabetes lo podemos poner en un plano cartesiando (donde cada eje es uno de los dos valores que recoge el exámen médico). Colocamos a los pacientes que efectivamente tenían diabetes como círculos negros en el plano en las coordenadas que corresponden a cada uno de ellos (según sus resultados de exámen), y a los que no tenían diabetes, como rombos de centro blanco. Vamos a tener algo así:
las SVM encuentran una "superficie" que intenta separar los ejemplos negativos y positivos con el margen más grande posible a ambos lados del hiperplano. En este caso, bi-dimencional, la "superficie" sería una línea. En un caso 3D (tres atributos para cada paciente) sería un plano. En un caso de más de 3 dimensiones, sería un hiper-plano o hiper-superficie con el número apropiado de variables.Hay muchas formas de hacer esto, propuestas por métodos estadísticos, por la gente de redes neurales, por la gente de optimización, etcétera. Lo que distingue a las SVMs es que el hiper-plano resultante se consigue logrando, como dije antes, que el margen que separa los datos es el mayor posible.
...entendiendo lo del margen, o ¿por qué lejos es mejor?
¿Y qué es eso de "margen"? Bueno, primero acudamos a la intuición, y luego definiré la palabra "margen" en este contexto. Para los datos que tenemos en el ejemplo, podríamos tener varias posibles superficies (infinitas), pero tomemos como ejemplo estas dos:
Preguntémonos ¿cuál es mejor? Vapnik demuestra estadísticamente, que mientras más lejos esté el hiper-plano de los puntos a los que clasifica, mejor. En este caso, pareciera que la Superficie A es mejor que la Superficie B.
Pero dije que iba a irme primero por la intuición: preguntémonos.... ¿Por qué lejos es mejor?
Para verlo intuitivamente, podemos imaginarnos el caso extremo, es decir, que la superficie estuviese "adherida" a algunos de los puntos de uno de los conjuntos, como en la siguiente figura:
Tengamos en cuenta que esos datos son de los pacientes para los cuales, hasta ahora, sabemos si tienen diabetes o no. Si dejamos que la superficie clasificadora esté allí, "adherida" a los pacientes sanos, intuitivamente podemos imaginar que es bastante probable que aparezca algún paciente con características similares a las de alguno de los pacientes a los cuales está "adherido" el hiper-plano. Pero cuando digo "similar", intuitivamente estamos aceptando que no hay dos pacientes exactamente iguales. Debe haber alguna pequeña diferencia. ¿Cierto?¿Y si esa pequeña diferencia hiciera que el paciente estuviese justo un ligeramente más allá de la superficie separadora? Si eso ocurriera, la máquina diría que ese paciente pertenece al grupo de los que tienen diabetes, es decir, diría que es un "círculo negro", cuando en realidad el afortunado paciente podría no tener diabetes. Estaríamos dando un falso positivo con cierta frecuencia.
Si el hiper-plano estuviese "adherido" a los pacientes del grupo de entrenamiento que eran diabéticos, estaríamos haciendo una máquina que produciría concierta frecuencia falsos negativos (porque pacientes muy parecidos a los que ya tienen diabetes, podrían estar ya el otro lado de la superficie separadora). Uno no desearía darles falsas expectativas a un paciente, así que esto tampoco es conveniente.
Para lograr alejar la superficie de los puntos de ambos conjuntos, Vapnick define el "margen" a maximizar como la distancia entre los dos hiper-planos, paralelos al hiper-plano separador, que están, cada uno, adherido a los puntos de uno de los conjuntos. En las Superficies A y B, el "margen" vendría a ser la distancia entre las líneas punteadas que se muestran abajo:
Como podemos ver, en el caso de la Superficie A, está mucho mejor que en la B. El método, adicionalmente, coloca la superficie, en general, en la mitad de esa distancia.¿y dónde dejamos a las Redes Neurales Artificiales?
Obviamente, las SVM están relacionadas con las redes neurales. De hecho, un modelo de SVM que use una sigmoide (aproximación a la función escalón que mencioné en mi post sobre redes neurales) como función para el cálculo de la salida, es equivalente a un perceptron (una neurona de salida binaria). En otras palabras, los parámetros para una neurona de clasificación (perceptrón), podríamos hallarlos mediante el uso del método SVM.
Cuando no es posible separar completamente los puntos de los dos conjuntos, la forma matemática en que se plantean los SVM obtiene excelentes resultados, minimizando los errores.
Kernels, o ¿qué hago cuando necesito un hiper-plano torcido?
Si nos encontráramos en un caso en el que los datos no pudieran ser separados por un hiper-plano, podría ser que una superficie no-lineal pudiera separar los conjuntos, como en el ejemplo de abajo:
.. lo que se hace en SVM (y en muchas otras técnicas) es transformar el espacio de los atributos (lo que llaman el kernel). Esto suena complicado, pero si nos fijamos en el ejemplo, podemos ver que una elipse podría resolver el problema, de la siguiente forma:
Esa sería la superficie no-lineal que necesitamos. Todo lo que hemos venido hablando, ha sido referido a hiper-planos, y claramente la elipse no es un hiper-plano. Sin embargo, sabemos que la elipse es una figura "Cónica", expresada más o menos así (en nuestro eje cartesiano del ejemplo):a*(x1 + b)^2 + c*(x2 + d)^2 = e
donde {a, b, c, d, e} es un conjunto de constantes, y {x1, x2} nuestras variables (discúlpenme por renegar del par {x,y} jejeje).
En general, cualquier superifice cónica, termina siendo algo como esto:
a1*(x1)^2 + a2*(x1) + a3*(x1)*(x2) + a4*(x2) + a5*(x2)^2 = a6
Ahora, esto ni de casualidad es lineal en un espacio definido por las variables {x1, x2}. Pero si nos imaginamos un espacio donde las variables son esas dos, mas 3 variables nuevas (tres dimensiones) extra: {x3, x4, x5}, donde cada una de ellas representa a los términos cuadráticos de la expresión de arriba, tenemos:
x3 = x1^2
x4 = x2^2
x5 = x1*x2
x5 = x1*x2
Y volviendo a escribir la ecuación cónica genérica (o cuadrática, como sería mejor llamarle), tenemos que nos queda así:
a1*(x3) + a2*(x1) + a3*(x5) + a4*(x2) + a5*(x4) = a6
¡Y acá estaremos todos de acuerdo con que se trata de una ecuación bastante lineal! Dense cuenta de que lo que se desprende de todo esto, es que un hiper-plano en este espacio de atributos ampliado, equivale a una elipse en nuestro espacio bi-dimensional (definido tan sólo por {x1, x2}).
Si pudiésemos representar gráficamente lo que ocurre en este espacio 5-dimensional, sería algo así:
Repito: acá aplican ahora todos los conceptos de margen y linealidad que se habían manejado anteriormente. Como puede verse, acá el SVM, aunque modelaría un simple hiper-plano separando grupos de puntos, estaría comportándose como una superficie no-lineal.
Algunas consideraciones de modelaje del SVM y el problema a optimizar
Sin embargo, quiero hacer notar una cosa importante: este kernel cuadrático resultó bastante apropiado para el problema del ejemplo. Pero podría no ser suficiente para otro problema. En general, la estrategia de complicar el kernel depende de nuestra suposición de la estructura y complejidad de los datos, y siempre aumenta la dificultad de obtener un resultado.
Si tenemos 9 atributos principales, resolver el problema cuadrático implica añadir una cantidad mucho más grande de variables "extra", representando los cuadrados de los principales y los productos entre ellas.
Un ejemplo de un problema que no podría resolverse con un kernel cuadrático, sería este, en el que se necesitaría de un kernel basado en funciones de base radial (gaussianas):
Separar conjuntos con superficies no-lineales, es algo que se ha logrado con perceptrones clásicos multi-capa (redes neurales). Sin embargo, dado que cada perceptrón posee una función de transferencia sigmoidal (buscando comportarse como una función escalón), la optimización a la que debe acudirse en las redes neurales tipo perceptrón, equivale a una optimización de este tipo:
donde o(x) es la salida de la red (su propuesta de clasificación), y c(x) es la verdadera clasificación del individuo "x". Los w, theta, nu y tau son simplemente parámetros de las neuronas del perceptrón multicapa.¿por qué la superficie a optimizar es así? Fácil: Porque es el error cuadrático de clasificación. El algoritmo de optimización (Backpropagation y sus primos, típicamente) va ajustando el parámetro de alguna neurona o peso de dendrita, hasta que ¡Zas! una de las neuronas cambia su salida de 0 a 1, o de 1 a 0, y con ello la respuesta de la red, posiblemente. Se sigue moviendo levemente (según un parámetro de paso) los parámetros, y posiblemente no pasa nada, hasta que se cruza otro límite de alguna de las sigmoides, y ¡Zas! ocurre otro cambio de 0 a 1, o de 1 a 0.
Mientras cambias los parámetros pero no pasa nada, se comporta de forma "estacionaria" la función del error (derivada = 0). Luego encuentras otro lugar, donde hay el cambio de respuesta, y la función de error cambia de forma brusca (derivada = mucho), ya que es la subida del "escalón" aproximado de la sigmoide. Nótese que idealmente el sigmoide sería lo más parecido a una función escalón, pero para que la derivada sea manejable numéricamente por los algoritmos de backpropagation, en el lugar donde está el umbral, se disminuye bastante, por lo que la red termina teniendo respuestas "difusas" cuando los elementos caen en el borde del umbral de alguna de las neuronas. Esto, a mi modo de ver, es indieseable.
Así pues, entrenar un perceptrón multi-capa implica un problema de optimización:
- no convexo
- con múltiples puntos estacionarios (donde suelen estancarse los algoritmos de optimización)
- con elevada cantidad óptimos locales
- no acotado
- asume sigmoides suavizadas (por lo que la red da respuestas difusas posteriormente)
Es mucho más atractivo resolver un problema como el de las SVM, porque es optimización cuadrática con restricciones lineales,... es decir: de los problemas más fáciles de solucionar. Más adelante les hablaré de un método que utiliza Programación Lineal para generar perceptrones multi-capa, sin usar Backpropagation. Si el problema de resolver una red neural, hubiese sido atacado inicialmente, por gente de investigación de operaciones, dudo que hubiésen optado por algo como el Backpropagation, realmente.
¿Y cómo es eso de "Vectores de Soporte"?
Ahora, para cerrar, quiero aclarar la duda que siempre surge cuando uno conoce a las SVMs:
¿por qué el nombre?
La respuesta es sencilla: si asumimos que cada uno de los ejemplos de los que disponemos (círculos oscuroes y rombos blancos) es un vector en el espacio, resolver SVMs es: encontrar los vectores en los que podamos apoyar los hiper-planos que definan el mayor margen de separación. Es decir, buscamos los vectores en los cuales "soportar" los hiper-planos paralelos, uno hacia un conjunto, y uno hacia el otro, para trazar justo en el medio de ambos, nuestro hiper-plano de separación. Veámoslos señalados por círculos rojos en la siguiente figura:
¡Ahí los tienen!Ahora lo de "Máquinas de Vectores de Soporte" suena menos oscuro ¿verdad?
En verdad espero que esta explicación les haya sido de utilidad ¡y disculpen lo extenso!
Para los que deseen profundizar, les recomiendo esta página: http://www.dtreg.com/svm.htm
Es mucho menos "básica" la explicación, pero mucho más completa.
NOTA: Si alguien detecta en mi post algún error, no duden en contactarme para decírmelo, ¿vale? ¡Gracias de antemano!.
jueves, marzo 13, 2008
Material de Cursos "Abiertos" del M.I.T
Cómo están?
Hoy escribo brevemente para comentarles que descubrí ésta página del M.I.T. Tiene material de diferentes tipos:
- notas de clase
- lecturas recomendadas
- videos
- láminas
- ejercicios
- casos de estudio
- problemarios
- soluciones a problemas
- trabajos hechos por los alumnos
- ... etc
Obviamente no es conducente a título, y no necesariamente incluyen toda la información que se proporciona a los alumnos inscritos, pero realmente me parece algo que puede ayudarnos, ya sea que queramos:
- mantenernos actualizados,
- planificar que cursos vamos a tomar (en cualquier universidad),
- profundizar conocimientos,
- preparar un curso,
- o por simple curiosidad intelectual.
Espero esto les sea de utilidad!
Suscribirse a:
Entradas (Atom)
