Nube de Etiquetas
(Ah?)

miércoles, mayo 21, 2008

Psicología aplicada en Máquinas de Aprendizaje: los seres humanos no son números

Creo que ya que les hablé del Premio Netflix, es bueno que les comente este excelente post en el que hacen reseña de un hecho curioso: una persona que originalmente viene del área de Psicología, llamada Gavin Potter, logró un marcado avance en este concurso. Hasta el momento en que esa persona entró, ninguno de los grupos concursantes no habían logrado hacer avances significativos desde hacía algún tiempo.... ¡y estoy hablando de personas que han probado ya múltiples ideas para resolver el problema!

Esta persona oriunda del área de Psicología, ya desde su primer intento, logró un avance mucho mayor que todos los avances recientes de los demás equipos. No pienso hacer una paráfrasis del post acá, pero si resumir en pocas palabras lo importante, y que debemos tener en cuenta al enfrentarnos a problemas reales:


Los especialistas en cómputo, estadística e inteligencia artificial pueden desarrollar algoritmos muy elaborados, y entonarlos para que trabajen muy bien ante los datos disponibles para el problema de Netflix. En ellos los números representan a los cinéfilos, y a sus gustos, y las fórmulas tratan de "predecir" el gusto que tendrán por la próxima película.

Esto está bien... salvo por el hecho de que....

¡Las personas no son números... ...ni miran las películas como si éstas lo fuesen!

Potter consideró a las personas como personas, e interpretó las calificaciones de las personas, tomando en cuenta cosas ya conocidas del comportamiento humano al momento de asignar calificaciones. El hecho de que esos números fueran asignados por un ser humano, es una información que, de alguna forma, había que incluír en el modelo.

Tomar en cuenta el factor humano, es algo que se díce más fácil de lo que se hace. ¿Cómo valernos de la psicología para estudiar personas sobre las cuáles no sabemos nada, excepto cuánto "dicen" que les gustó una película.

En corto, la forma en que Potter lo hizo, fue la siguiente:
  • Consideró que los gustos de las personas pueden cambiar a medida que pasa el tiempo. Uno puede darle más "peso" a las calificaciones más recientes que a las muy viejas.
  • Consideró el efecto "anclaje", que se refiere a la inercia que nos invade cuando asignamos calificaciones numéricas a algo (me ha pasado en mi experiencia como profesor universitario!). Si una persona ve tres películas seguidas que merecen 4 estrellas, y luego ve una que es un poco mejor, muy probablemente le asignará un 5. Sin embargo, si empezó viendo un par de películas a las que les dió sólo una estrella, esa misma película, que en otra circunstancia hubiese calificado con un 5, recibiría posiblemente sólo un 4 o incluso un 3. Potter se ocupó de medir este efecto en la data proporcionada por Netflix, y tomó en cuenta este efecto en las fórmulas, para determinar más precisamente los gustos de los cinéfilos.
La moraleja detrás de esto es muy importante:

sin importar que tan buenos modeladores seamos, al enfrentar un problema real, tener en el equipo una persona que sepa de la parte de la realidad que está tratando de modelarse. Es posible que a un especialista en computación, optimización o estadística se le ocurra algo de este estilo, pero, como sugiere el post en cuestión: incluír al especialista de la parte de la realidad que estamos estudiando puede ahorrar trabajo en modelos infructuosos.

Para cerrar, les paso el link al post es éste:
http://www.wired.com/techbiz/media/magazine/16-03/mf_netflix?currentPage=all

jueves, mayo 01, 2008

Usando la IMDb para ganar el Premio Netflix

Hay ahora varias cosas que tengo pendiente publicar acá, con la esperanza de seguir generando oportunidades para que personas que no tienen formación inicial en las áreas afines a la Investigación de Operaciones y a las Máquinas de Aprendizaje puedan iniciarse en estas lides.

Mientras consigo el tiempo para escribir con la calma suficiente sobre un nuevo tema, quiero compartir con ustedes un post del blog "Geeking with Greg", en el cuál Greg comparte con nosotros las inquietudes que se han ido despertando entre los concursantes del Premio Netflix.

En resúmen, las inquietudes rondan alrededor de las dudas que hay sobre si realmente es necesario tener mayor cantidad de información sobre las películas (trayéndola de la IMdb, por ejemplo), o simplmente es necesario tener mejores algoritmos ( o ambas cosas, evidentemente ).

El post pueden verlo en esta dirección:
http://glinden.blogspot.com/2008/03/using-imdb-data-for-netflix-prize.html

Saludos!

PD: para los que no saben de qué trata el premio Netflix, éste se trata de un concurso propuesto por la empresa de ese mismo nombre, en el que invitan a cualquiera que quiera participar (la inscripción es gratuita) a usar una base de datos en la se tiene información sobre las preferencias fílmicas de los usuarios, para elaborar un algoritmo que prediga, para cada usuario, qué puntuación le pondría a una película que aún no ha visto. En la base de datos las calificaciones que tiene cada usuario del sistema, sobre cada película que ha visto son del 1 al 5. El objetivo es superar al algoritmo que ya tienen, al menos en un 10% en la efectividad.

lunes, marzo 31, 2008

Suscripción por email y Nube de Etiquetas

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

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):

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:
  1. Se elige un subconjunto de los datos, de forma aleatoria, para conformar el "conjunto de prueba" o "conjunto de validación".
  2. El resto de los datos conforman el "conjunto de entrenamiento".
  3. Se dan valores iniciales a los parámetros de todas las neuronas de la red.
  4. 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).
  5. 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.
En la práctica, durante el proceso se evalúa el trabajo predictivo de la red ante los datos del conjunto de validación (que la red nunca ha usado para entrenarse). Esa evaluación permite observar qué tanta capacidad de generalización tiene el modelo.

La experiencia tiende a mostrar el siguiente patrón:
  1. Con los primeros ajustes, poco a poco crece la eficiencia con que se logran predecir los resultados del conjunto de validación.
  2. 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.
  3. 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:

En general, estas herramientas permiten algún nivel de análisis para determinar si un trabajo más complejo o largo, está ayudando o no a la capacidad de generalización (predecir valores no vistos durante el entrenamiento o determinación de parámetros).

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

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

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).

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:
  • 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

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:
  1. no convexo
  2. con múltiples puntos estacionarios (donde suelen estancarse los algoritmos de optimización)
  3. con elevada cantidad óptimos locales
  4. no acotado
  5. asume sigmoides suavizadas (por lo que la red da respuestas difusas posteriormente)
Es decir: ¡todo lo que un optimizador no desea encontrar!

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
...de muchos de los cursos dictados en ese instituto. Este material lo hay de cursos tanto de nivel de pregrado como postgrado (Master y PhD).

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.
A nosotros los que nos interesan los temas afines a este blog, pueden interesarnos las secciones de cursos de:
Espero esto les sea de utilidad!

lunes, febrero 11, 2008

¿Regresión usando Programación Lineal?

Alfredo me comentaba que había leído varios tópicos de Investigación de Operaciones, pero que ninguno de los tópicos era Data-Mining, por ejemplo, o métodos Multi-Superficie. En mi respuesta le insinué que ciertamente no son tópicos de la IO, pero no por ello es imposible que si se idea una formulación adecuada del modelo, la IO pueda aportar en campos que en principio se asumen como "diferentes".

En un post anterior escribí sobre la diferencia entre Regresión y Clasificación. Para la mayoría de los que han tenido contacto con cursos introductorios de IO, estará claro que no son parte del temario de IO.

Todo esto me inclinó a escribir hoy acerca de una aplicación de IO para Regresión. Ya a muchos les quedó claro que me he ocupado bastante del uso de la IO para clasificar, y bueno, la Regresión quedó huerfanita, al parecer... ;o)

Antes que todo, quiero dejar claro que el modelo más famoso en la actualidad, para realizar clasificación binaria (los SVM) también es utilizado para regresión. Con esto quiero decir, que lo que voy a desarrollar acá no es la invención de la rueda.
Es un simple ejemplo ilustrativo, que me permitirá (espero yo!) mostrar una regresión mediate IO, sin entrar en detalles sobre los SVMs (vale la pena acotar que fue parte de los ejercicios de un curso de Análisis de Sistemas Lineales del Prof. Ubaldo García Palomares de la USB).

El ejemplo es el siguiente:

Se tienen 4 puntos en el plano cartesiano...
e1 = (0.1 , 1.0)
e2 = (0.8 , 2.2)
e3 = (2.2 , 2.8)
e4 = (3.3 , 3.9)

Que lucen más o menos así, al graficarlos en Excel (disculpen la cuña!):


Bueno. Se nos pide que, sin usar mínimos cuadrados, aproximemos una recta

y = a*x + b

que pase lo más cerca posible a todos esos puntos.

Yo voy a resolver el problema formulando un modelo de programación lineal... primero, tengo como información que la función a aproximar es una línea recta. Si me disculpan una notación extremadamente simple, diré que cuando tenga un i-ésimo punto ei, con componentes (xi , yi), tendré un error dado por la resta

[ yi - yi~ ]

donde yi~ es el estimado que me arroja la función de la recta, es decir:

yi~ = a*xi + b.

En mínimos cuadrados, se quiere hacer pequeña la suma de los errores cuadráticos:

[ yi - yi~ ]^2

Bueno, como me pidieron que no fuese una minimización de los errores cuadráticos, me quedaré con la expresión [ yi - yi~ ].

Ahora, ese error me va a dar positivo cuando el estimado sea menor que el valor real, y negativo cuando pase lo contrario... y si sumo los errores así, podrían cancelarse positivos con negativos, dando una suma que realmente no significará nada para mi.

Así que voy a hacer pequeña, en cambio, a la suma de los errores absolutos:

| yi - yi~ |

Ahora, recordemos de bachillerato que la función "valor absoluto" ( y=|x| ) no es lineal, así que... evidentemente no puedo resolverlo con Programación Lineal....

... O SI!!!

Yo puedo respirar profundo, abrir y cerrar los ojos, y escribir lo mismo, de forma un poquito diferente. Puedo tranquilamente decir que yi~ es igual a yi, más una variable "di" que mide el i-ésimo error de forma no-absoluta, así:

di = yi - yi~

yi~ + di = yi

Ahora, todavía la suma de los errores "di" me deja en las mismas, porque podría tener positivos y negativos (con toda seguridad!). No he hecho nada interesante aún. Sin embargo, ahora si respiro profundo y me aseguro de que mi lapiz tiene punta, porque voy a jugar con ese error "di". Quiero jugar de forma que tenga sólo variables no-negativas, que crezcan cuando hay error. Por ello, voy hacer lo primero que se me ocurre: expresarlo como una resta de dos valores positivos.

NOTA: cualquier número puede expresarse como
la diferencia
de dos valores no-negativos. Ejemplo:
1 = 34-33
-8 = 10 - 18

Por lo tanto, "nadie me quita lo bailao" si yo decido escribir ahora la diferencia así:

yi~ + (dip - din) = yi

donde dip, vale di, si el error es positivo... (y din = 0)
y din, vale -di, si éste es negativo... (y dip = 0)

Digamos, para mostrarlo fácilmente, que si yi = 2, y el estimado yi~ = 3, entonces tendremos:
3 + 0 - 1 = 2

en otras palabras, dip = 0, y din = 1.

Por lo que din estaría sumando 1 a mi total de errores, en lugar de un -1 (aunque el error que he definido es negativo, porque el verdadero valor es más pequeño que el estimado).

Ahora tengo lo siguiente, si lo aplicamos a los 4 puntos:

y1~ + d1p - d1n = y1
y2~ + d2p - d2n = y2
y3~ + d3p - d3n = y3
y4~ + d4p - d4n = y4

con d1p, d2p, d3p, d4p, d1n, d2n, d3n, d4n todos >= 0.

Esas serían las restricciones de mi modelo, que si sustituímos los estimados por la expresión que proporciona el estimado en base a el xi (componente x del i-ésimo punto) en cada caso, sería lo mismo que:

(a*x1 + b) + d1p - d1n = y1
(a*x2 + b) + d2p - d2n = y2
(a*x3 + b) + d3p - d3n = y3
(a*x4 + b) + d4p - d4n = y4
d1p, d2p, d3p, d4p, d1n, d2n, d3n, d4n >= 0

Nótese que he colocado las variables en color azul. Lo que esté en negro es "dato".

Ahora, me podría asustar y gritar: ¡ahora tengo 2 veces más incógnitas que antes! ... pero en este tipo de cosas lo que se nos pide es que tengamos la valentía de seguir adelante a ver a donde se llega, hasta que se llegue,... a la solución...

...o a una calle ciega... lo cual es siempre una posibilidad que no tiene por qué desanimarnos si no estamos en un exámen.. jeje.

Así que tomamos un poco de chocolate caliente para el alma, y nos preguntamos: ¿qué es lo que quiero hacer pequeño? Respuesta: la suma de los errores dip y din.

Es decir, que mi función objetivo es la suma de los errores positivos y negativos:

Minimizar Z = (d1p + d2p + d3p + d4p) + (d1n + d2n + d3n + d4n)

Esto hará, que en la resolución el algoritmo utilizado quiera hacer que todas las variables dip y din tengan el menor valor posible: cero (0), colocando la recta justo para que pase por los puntos.... en tus sueños!! jaja...

Como lo más probable es que no lo logre, tendrá que sacrificar alguna de las variables dejándola que sea mayor que cero. Pero en ningún momento hará que una que no sea necesaria, sea mayor que cero. El modelo entonces queda formulado completo así:

Minimizar Z = (d1p + d2p + d3p + d4p) + (d1n + d2n + d3n + d4n)
din, dip, a, b

Sujeto a:
(a*x1 + b) + d1p - d1n = y1
(a*x2 + b) + d2p - d2n = y2

(a*x3 + b) + d3p - d3n = y3

(a*x4 + b) + d4p - d4n = y4
d1p, d2p, d3p, d4p, d1n, d2n, d3n, d4n >= 0

Abajo tengo una imágen donde muestro en excel como saqué las cuentas en la hoja de cálculo, para la función objetivo y los valores que necesito para las restricciones. Lo amarillo es celda que representa a una variable, y lo azul son celdas que cambian en función de las variables (diferente a como coloreé las cosas en el texto). Guardé ese pantallazo mostrando en particular la fórmula con que estoy calculando el y~.


Ya es el momento de llamar a la máquina que me dirá cuáles son los valores óptimos de "a" y "b" de la recta, es decir, aquellos que podrán existir haciendo la suma de los errores lo más pequeña posible. La forma en que llené los datos en el Solver, la muestro abajo. Dense cuenta de que hice que los dip y din fuesen no-negativos, pero no restringí en absoluto a las variables "a" y "b":

(Las dudas sobre lo que significa lo que se ve arriba las podemos aclarar luego en la medida en que me pregunten, si lo desean)

Finalmente, y para no seguir alargando el post, veamos el resultado que arroja el Solver, así como una graficación de la recta que resulta:


¿No está mal, eh? Bueno. Aquí termina el ejemplo de hoy.

Traté de hacer esto de forma que todos pudiesen replicar el resultado fácilmente. Espero haberlo logrado. ¡Cualquier cosa, como siempre: pregunten!

Así pues, tenemos una regresión, no basada en minimización de errores cuadrados, sino obtenida mediante la resolución de la clase de modelo más emblemático de la IO: la Programación Lineal.

¿Es la Regresión Lineal un problema de IO? Probablemente no... pero no significa que pueda usarla para resolver el problema. ¡Ese es el espíritu!

Nota: para los recién iniciados en esto, que estén curiosos y quieran ver más allá de lo evidente, les adelanto que este tipo de regresión tiene cierto tipo de ventajas respecto a la regresión cuadrática bajo ciertas circunstancias. Se llama minimización en "norma - 1", mientras que en la de mínimos cuadrados se minimiza la "norma - 2"....

...pero eso es parte de otra historia

XoD

sábado, febrero 09, 2008

Respuestas para Alfredo

Primero que todo, Alfredo, gracias por tomar la confianza de escribirme, me gusta ayudar (es una de las principales razones por las cuales escribo el blog... porque yo quisiera haber podido leer algo como esto cuando me iniciaba en el área). Como tus preguntas no son de las que uno quisiera responder con monosílabos, te respondo en un post.

Sabes? No se necesita ser una lumbrera para meterse en esto. Sólo se necesita hacer lo que estás haciendo: dedicarle... y algo que te ayudará a hacerlo, es tener gusto por esto. Al poco tiempo tendrás que explicarle a los demás que tu no eres una lumbrera (si ellos hubiesen pasado el mismo tiempo que tu, dedicándole a esto, no les parecería tan genial lo que tu puedes hacer con estas herramientas). Yo tampoco soy una lumbrera, by the way... jeje.

En cuanto a tus preguntas a mi "como analista de operaciones", tengo que decirte varias cosas:
No he tenido trabajo en la empresa privada como "analista de operaciones". Y con esto me refiero a que no he tenido un trabajo en el que haya podido utilizar la investigación de operaciones (hasta ahora).
  1. El trabajo de una persona que tiene experticia en investigación de operaciones puede ser (en el mundo empresarial/industrial) uno de planificación, por ejemplo, o el de consultor. El resto de los trabajos que he podido ver, puede que requieran puntualmente el uso de investigación de operaciones, pero una vez encontrado el modelo, e implementado, correrlo periódicamente no es un trabajo interesante para una persona con el perfil de IO.
  2. En el mundo académico, es obvio que el trabajo para una persona del área de IO es dar clases, y buscar ampliar los horizontes de la IO mediante la investigación, que además te pone en contacto con lo que otros locos están haciendo respecto a eso en otras partes del mundo.
  3. Recientemente un Gran Amigo de la infancia me propuso trabajar juntos como consultores. Mi actividad cotidiana en ese aspecto estaría formada por actividades de este tipo:
    • reunirme con el cliente para entender su problema
    • definir un modelo (esto es un proceso que es arte y ciencia)
    • definir cómo voy a recoger los datos que necesito y negociar con el cliente cómo vamos a recogerlos.
    • definir qué infraestructura informática necesito para resolver el modelo y negociarlo con el cliente.
    • intentar explicar al cliente en forma sencilla qué es lo que estoy haciendo.
    • fumarme una lumpia para resolver el modelo que planteé.
    • ver los resultados, y traducir eso en algo que pueda digerir el cliente.
    • antes que todo, demostrar al cliente qué beneficios le puede traer contratarte para que apliques IO
    • Eh... creo que esa es una lista que podría darte una idea de la no-cotidianidad del asunto.
  4. En cuanto a que si la IO es tan tomada en serio en Venezuela como lo podría ser en EEUU, te puedo decir, sin que me quede nada por dentro, que la respuesta es: NO. Lo más frecuente es que las respuestas en Venezuela las de alguien con experiencia (al menos aparente) o el viento que pegue en el dedo luego de ser correctamente ensalibado (yuck!). Esto no siempre es criticable, puesto que los "sistemas" que uno analiza en países como el nuestro no siempre son del todo estables, predecibles y bonitos, sino que la alta sensibilidad a miles de variables ... todas en comportamiento caótico... hacen que estas técnicas ameriten una gran inversión, o tengan poca probabilidad de ser efectivas. Eso no significa que haya puestos en las empresas del área de petróleo, comunicaciones, construcción, e industrias manufactureras y de producción "contínua" que denigren de estas técnicas. Simplemente que son pocos los sitios donde lo hacen. Tengo entendido que en "la anterior PDVSA" (dejémoslo así para no entrar en el tema político) había un departamento de gente de IO dedicada específicamente a mejorar los procesos e la empresa mediante estas técnicas. Hay empresas consultoras que valoran MUCHO que una persona tenga formación en IO, aunque no lo usen nunca en el puesto que le van a dar, tan sólo por "el tipo de pensamiento" que tenemos. Con esto termino en lo referente a las posibilidades de trabajo.
La pregunta sobre la "buena paga", no puedo respondértela con propiedad, porque tengo noticias de personas a las que les pagan bien poco, y otras que ganan una millonada. Los sueldos en PDVSA no estaban para nada mal, en "épocas anteriores", por ejemplo. Ahora, consultoras hay de muchas clases, unas que pagan mucho y luego, al finalizar un contrato te botan. Otras te pagan mucho menos, pero no te echan a la calle. Creo que lo importante es saber venderte.

No hay una "moda" como la que hay por la gente que tiene academia SAP, por ejemplo, que siempre son bien pagados, si es lo que querías saber. Espero esto te responda un poco tus inquietudes.

Me preguntas ¿Hacia donde se dirige la IO?... y me pones en problemas. La IO es un campo MUY amplio. No sólo en cuanto al tipo de técnicas que hay, sino a las aplicaciones, y al enfoque que tienen las personas. Por ejemplo, hay gente que se ocupa de la Programación Lineal, desde un punto de vista estrictamente matemático, generando nuevas aproximaciones a la resolución del problema. Otros se paran desde el punto de vista computacional, viendo como resuelven los obstáculos que pueden presentarse al sacar las cuentas con una computadora. Y hay otros, como yo, que nos ocupamos de usar el ingenio en resolver problemas nuevos con técnicas viejas, mediante innovación en la formulación. Aunque pensaba que esa era la última de mi enumeración, creo que también hay gente que se ocupa de mezclar las técnicas de IO con otras técnicas: estadística, lógica difusa, redes neurales, etc.

Cada uno de estos miembros de esta fauna de la IO, a su vez, tienen campos muy específicos en los que investigan, y todos los meses puedes ver en las revistas arbitradas que hay en el mundo, publicaciones de cosas nuevas. La pregunta, Alfredo, para respondértela más certeramente, tendrías que hacérmela restringida a un tipo de fauna de IO, y además restringida a un tipo de problema... vale? y disculpa esa!

Creo que es obvio que mi opinión es que hay MUCHO campo para investigar. No en vano hay revistas arbitradas dedicadas exclusivamente al área de IO.

Sin embargo quiero dejar en claro algo: los temas en los que se inicia el estudio de la IO son la Programación Lineal, la Teoría de Colas, el Pert-CPM, los modelos de Optmización en Redes, la Simulación de Eventos Discretos y la Programación Lineal Entera... eso es cierto...
Pero esos temas son las herramientas básicas.

Ahora, el Data-Mining, por ejemplo, no es en si mismo un tema típico de IO. Los modelos de IO que se han aplicado para hacer Data-Mining son eso mismo: algoritmos de un área, utilizados para resolver un problema de otra área (lo cual nos lleva a ver que las áreas están entrelazadas).

Por ejemplo, un problema de SVM (Support Vector Machine) ciertamente es un modelo de Programación Matemática (y por ende IO), pero no todo modelo de IO puede ser aplicado para el reconocimiento de patrones. Normalmente los modelos de Programación Matemática usualmente dan un resultado válido estrictamente para los parámetros que se utilizan al momento de resovlerlo,... y puedes mantener "la solución" sólo si cambian esos parámetros dentro de los rangos que de da el análisis de sensibilidad. Una vez cambian demasiado los parámetros, la solución es otra. Por lo tanto, en principio, no son buenos para "generalizar". En particular los modelos como el SVM y los utilizados en Métodos Multi-Superficie están construídos con la intención de obtener una buena capacidad de generalización, y los parámetros que reciben al formularlos, SON los elementos sobre los cuales se va a generalizar. Sólo por ello sirven para "simular" aprendizaje. ¡Así que OJO con eso Alfredo! Lo que si puedo permitirme decirte es que esto demuestra que la IO no tiene por qué restringirse a los temas y problemas clásicos.

La imaginación es el límite... dice el cliché por ahí... jeje... aunque yo también diría que ese límite a veces se hace más pequeño debido a las restricciones en capacidad de cómputo que tendremos siempre, obligándonos a simplificar nuestros modelos para poder tener una respuesta en un tiempo razonable.

¡Espero te sientas respondido!

Regresando a la Web

8 días sin internet... no fue algo que me enloqueciera, pero definitivamente la piquiña en los dedos (por escribir) y en los ojos (por leer) era innegable.
Eso si: nunca imaginé que este blog (con pocos posts, y de temática no muy "comercial") iba a tener la cantidad de visitas que tuvo, ni los comentarios que hoy veo que han dejado en este tiempo.
A quienes esperaban el próximo post, o una respuesta a los comentarios, les pido disculpas por hacerles esperar. Sin embargo, créanme: fue por una buena razón.
Mi papá, desde el 1º de Febrero lo ingresamos por emergencia a una clínica, y estuvo hospitalizado hasta ayer, y en esta ocasión el único que podía quedarse allí con él a cuidar de él, era yo. Pero ya todo volvió a la normalidad.
Bueno, dicho esto, no me queda otra cosa que darles las gracias por la recepitividad con que han acogido este blog... y por supuesto ponerme a responder los comentarios ASAP. :o)
Como le digo a mis compañeros de juegos de rol cuando falto a una sesión (virtual o no), "la realidad se me atravesó". Pero ya tengo licencia para seguir soñando despierto nuevamente, y compartirlo con Uds.
See you in the mirror!

viernes, febrero 01, 2008

Regresión vs. Clasificación

Regresión, en el contexto de la estadística y el modelaje matemático, es algo claramente distinto a autoespiarse en una etapa infantil o una vida pasada. Y ciertamente cuando uno hace una regresión típica (digamos, por ejemplo, mínimos cuadrados), uno ciertamente no siente que está regresando en ningún sentido.
El orígen del término data del siglo XIX, cuando fue utilizado en el contexto del análisis de un proceso biológico. Éste proceso tenía que ver con el hecho de que los descendientes de individuos excepcionales, tienden a ser más normalitos que sus excepcionales ancestros. Charles Darwin tenía un primo de apellido Galton (si no me equivoco) que llamó a este proceso "regresión". Este caso fue estudiado luego desde el punto de vista estadístico, y al final se terminó llamando "Regresión" a las técnicas en las que uno examina como se reacciona una variable de respuesta (variable dependiente) en función de una variable explicativa (variable independiente).
Este tipo de procesos de análisis no requieren entender los procesos detrás de la generación de los datos estudiados. Las premisas que se toman, en todo caso, son sólo de tipo estadístico (como por ejemplo que los errores respecto a la curva que "modela" el sistema están distribuídos según la campana de Gauss).
La regresión se usa para realizar pronósticos, probar hipótesis, estimar parámetros, entre otras cosas. He escuchado varias opiniones acerca de estos métodos, y no les quito razón, cuando dicen que debido a que "cualquiera hace una regresión, pero sólo expertos pueden criticarlas", uno encuentra que muchísima gente hace una regresión simplemente por hacerla.
Los que no conocen de estadística o modelos matemáticos ven unas "cuentas" y una curva, y realmente no tienen el tiempo de comprobar que todo lo que se hizo está bien, pero ya la exposición del analista de la regresión queda enmarcada en una supuesta formalidad.
A esto se refiere el dicho de que "la mayoría de las personas usan la estadística de la misma forma que los borrachos usan los postes de luz, para apoyarse, pero no para buscar iluminación".
Al final, simplemente una regresión es una forma de aproximar una expresión matemática para que se comporte de forma similar a un conjunto de datos que uno ha recogido. Por ejemplo: quiero saber cómo varía la presión atmosférica según se sube por una montaña, y hago mi escalada para la montaña, parándome 4 veces en mi camino para sacar mi barómetro y ver cuánto marca, y en el mapa me dicen a que altura está el parador turístico en el que me detuve a hacer la medición, por lo que en mis notas pongo los dos datos juntos.
Al final tengo 4 pares de datos (altitud, presión), y en la próxima tarde lluviosa me pongo a sacar cuentas, para ver qué función matemática pasa por esos puntos de la mejor forma. Cuando la tenga lista, asumiré que cada vez que me digan la altura, podré estimar la presión, y viceversa. Perfecto. Si no tuviese esa técnica (ni conocimientos teóricos sobre termodinámica y fluídos), sólo podría responder a esas preguntas específicamente para los puntos que ya medí. Ahora puedo responderlo para cualquier punto intermedio aunque no me haya parado a medir.
¿Y para donde voy con todo esto? Bien. Ahora que está claro para todos lo que es una regresión, puedo pasar a relacionar el concepto con el de clasificación, que lo hablé en un post anterior.
Resulta que construír un modelo de clasificación es conceptualmente muy similar a construír un modelo de regresión, sólo que la respuesta que se me pide que de, no es un número cualquiera, sino una categoría.
Es algo así como que me pidan que elabore un modelo para saber cuando un lugar es de presión alta y cuando es de presión baja. Me voy de paseo, y en el camino voy preguntando a las personas: "¡Señor! ¿acá la presión es alta o baja?". Voy anotando los valores de altitud, junto a la respuesta del paisano de ese lugar en mi cuadernito. Luego tengo que sentarme en mi casa y ver para cada altura qué me respondieron. El modelo podría ser algo así como "Si la altura es mayor que X, la gente en general piensa que la presión es alta". Ese es mi modelo de clasificación.
En el fondo es un modelo de Regresión, pero que la variable de respuesta (dependiente) no es contínua, sino categórica.
Bueno, a mi me pareció interesante cuando supe esto, y quería compartirlo con los que aún no han pasado a considerarlo trivial, jeje. Son los pequeños asombros que lo animan a uno a seguir investigando estas cosas. ¿No es verdad?

jueves, enero 31, 2008

Clasificar vs. Reconocer un Patrón

Estaba en estos días reunido con un amigo explicándole que estaba trabajando en un algoritmo para el reconocimiento de patrones binarios. Entré en detalles, y posteriormente usé la palabra "Clasificación binaria", lo que le motivó a preguntarme:
Por fin, Orestes ¿esto no era para reconocimiento de patrones? ¡Ahora me acabas de decir que es para clasificacion binaria!.

Claro... para algunos de ustedes, que también están empapados en estos temas, la pregunta es trivial. Sin embargo para los que ocupan su mente con otro tipo de problemas y herramientas, no es evidente que ambas cosas son lo mismo.
Para ellos estoy escribiendo este post, y lo haré parafraseando una explicación muy buena que hicieron K.P. Bennet y E.J. Bredensteiner en su artículo "Geometry in Learning".
Imagínese que su trabajo es determinar si un tumor de seno es benigno o maligno. Un cirujano inserta una aguja en el tumor y aspira una pequeña cantidad de tejido. Se prepara una placa de vidrio (porta-objeto) en la que se coloca la muestra, y usted procede a colocarla en el microscopio para estudiarla. Su trabajo es examinar las células que están en la láminilla de vidrio, reconocer los atributos importantes de las células, tales como la uniformidad de la fórma de las células, y la variabilidad en el tamaño. Eventualmente usted llega a la conclusión de que es benigno, o de que es maligno. Esto es algo que usted debería haber aprendido a hacer luego de examinar montones de tumores de los que ya previamente le habían chismeado si el tumor era maligno o benigno, de parte de un experto patólogo que usó biopsias quirúrjicas tradicionales (a punta de cuchillo, para ser completamente claros). Probablemente alguien podría ayudarle señalando en la imágen los atributos que deben ser estudiados con más incapié. Y entonces usted debería "generalizar" el conocimiento que aprendió, aplicándolo luego para estudiar nuevos tumores, para (por ejemplo) tener una idea previa de la malginidad del caso, sin tener que echar cuchillo al delicado seno (y aquí termina mi paráfrasis de la introducción del paper de Bennet y Bredensteiner).
Hablando normalmente, como quien se encuentra en una cafetería hablando con los familiares de la pacienet, usted diría sobre un caso, que "Reconoció el Patrón" que tienen los tumores malignos.
Ahora, hablando matemáticamente, podemos decir que usted "clasificó" a ese elemento como "Maligno", tal y como si usted tuviese una caja donde recibe los casos a estudiar, a su lado derecho, y dos cajas a su lado izquierdo, cada una con una etiqueta: una dice "Maligno" y otra dice "Benigno". El equivalente de su trabajo es tomar cada tumor de la caja de la derecha, estudiarlo, y en base al estudio de sus atributos, lo lanza a una de las cajas de la izquierda. Por eso es que los matemáticos consideran el proceso de "reconocer patrones", como un caso más de "clasificación".

Obviamente, esta puede ser de múltiples clases, no necesariamente binaria. Por ejemplo, reconocer caracteres visualmente, además de entenderse como "reconocer el patrón" de la letra A, la letra B, y así sucesivamente, puede entenderse como que usted tiene tantas cajitas a su izquierda, como letras hay en el abecedario (más una por cada número), y recibe un caracter, lo estudia y lo lanza en alguna de las cajitas luego de dar cuenta de los atibutos de ese caracter. Reconocer patrones de caracteres, es clasificar caracteres en tantos tipos como caracteres posibles pueda haber. También puede verse así el problema típico de "reconocer" una huella digital (alguno ha visto CSI?). Las "clases" son cada uno de los criminales en la base de datos contra la cuál se contrasta la huella en cuestión.

En fin... Yo ya estoy empezando a clasificar este punto de mi escritura del post como del tipo "ya ponte a trabajar", así que... nos vemos luego!

miércoles, enero 30, 2008

¿Para qué me sirve este blog?

Está bien, me digo a mi mismo, pues me he quedado con una pregunta hipotética en mi mente. La pregunta es: Si yo fuese un lector de este blog, para qué me serviría leer lo que se ha publicado acá (hasta el momento)? ¿y el blog en general?

Así que me animé a escribir nuevamente hoy (lo cuál debe ser una especie de record para mi en este blog!), para responder esta pregunta a mis amigos imaginarios (invisibles, diría Uslar Pietri).

Empecemos, aprovechando que son pocos posts, enumerándo las preguntas que podrían ser respondidas en cada uno de los posts:

  1. Máquinas de Aprendizaje ¿con Investigación de Operaciones?
    • ¿Cómo hago si no encuentro como entrenar una red de clasificación binaria?
    • ¿La Investigación de Operaciones me sirve para Inteligencia Artificial?
    • ¿Es Backpropagation (Retropropagación) la mejor forma de entrenar un perceptrón multicapa?
    • ¿Cómo se relaciona la Minería de Datos con la Investigación de Operaciones?
    • ¿Cómo se relacionan la Inteligencia Artificial, las Máquinas de Aprendizaje, la Minería de Datos, las Redes Neurales, la Invesgiación de Operaciones y la Optimización?
    • ¿Qué ideas critica Orestes? (esta es la que menos probablemente se hagan ustedes, pero la que me gustaría que más se hicieran!)
  2. ¿Dónde está el área de Investigación de Operaciones?
    1. ¿En qué departamentos de una universidad puedo encontrar a los profesores e investigadores del área de Investigación de Operaciones?
    2. Mi área es Investigación de Operaciones ¿en qué tipo de lugares debo meter el curriculum vitae en una universidad?
  3. ¿Qué es la Investigación de Operaciones?
    Ya el título es la pregunta, obviamente. Sin embargo, por no dejar, diré acá que esa pregunta puede surgir tanto a una persona de otra área, a la que le salieron con "la palabrota", como a una persona que sencillamente está buscando hacer un postgrado y quiere saber un poco más sobre esto de la IO.
    Yo se los digo, créanme: resulta particularmente confuso y "generaloide" leer la mayoría de las definiciones que hay por ahí. Para quitarse la triste sensación de que los únicos que saben qué es la investigación de operaciones, son los que trabajan en eso, puede ser que este post les de un respiro.
  4. Comienzo de divulgación de mis aportes durante la Maestría
    • ¿Cuáles son las grandes áreas de la Ingeniería de Sistemas?
    • ¿Qué motivó a Orestes a abrir este blog? (el que aún luego de leer lo de arriba, sienta que el blog no se justifica, podría hacerse esta pregunta)
      Claro está, que aún no he cumplido con la "impetuosa necesidad de comunicar mis aportes... etc etc", porque no quiero soltarlos sin contexto. Quiero comunicar mis aportes, luego de poner en el tapete todas las ideas que se necesitan para que al leer mis aportes no se queden con la pregunta mental "¿where are you coming from, Orestes?". Quiero asegurarme de que pongo las ideas de la manera más sencilla y clara posible, en parte para que el mensaje llegue a quienes no son expertos en el área, y en parte porque me gusta contar esto como un cuento que todos puedan más o menos entender (con un poco de investigación en wikipedia, si hace falta!).
  5. My own introduction to Neural Networks (spanish)
    • ¿Qué son las redes neurales artificiales?
    • ¿Para qué sirven?
    • ¿Qué las hace diferentes al cómputo clásico?
    • ¿Cómo me bajo el pdf de la tesis de maestría de Orestes? (LOL!)
Bueno. Ahora si me siento satisfecho. Procuraré, de ahora en adelante, hacer más énfasis en la utilidad de lo que escriba, porque en estos tiempos el ocio no es el que nos lleva a leer cosas como éstas!

Máquinas de Aprendizaje ¿con Investigación de Operaciones?

El tema del "Machine Learning" o de las Máquinas de Aprendizaje es un tema que en principio está en el terreno de la inteligencia artificial, pues cuando queremos que una "máquina" (en general un "ente" artificial) aprenda, básicamente estámos tratando de emular la forma en que el ser humano, a partir de su experiencia, logra tomar deciciones apropiadas, y esto, evidentemente, es parte de lo que llamamos "inteligencia".

Claro que este blog no es un blog de inteligencia artificial, sino de Optimización y Máquinas de Aprendizaje. Así que de ahí se puede desprender una razonable sospecha de que no voy a tratar a las máquinas de aprendizaje de modo general, sino sólo en los aspectos que tiene en común con el área de la Opimización (métodos prescriptivos de Investigación de operaciones, que comenté en un post anterior).

¿Y cuáles son esos tópicos de Máquinas de Aprendizaje que tienen que ver con Optimización? No pretendo en esto mostrar una lista completa de los tópicos, ya que mis conocimientos no abarcan con suficiente profundidad todos los tópicos de las Máquinas de Aprendizaje. Simplemente diré en respuesta a ello, me referiré en particular a los Algoritmos de Aprendizaje Supervisado.

El Aprendizaje Supervisado, como casi todos los tópicos de Máquinas de Aprendizaje, ha sido atacado desde enfoques estadísticos, de redes neurales, y ciencias teóricas de la computación. Son raros los casos en los que se enfrentan estos problemas desde el enfoque de la optimización. En particular, el área del "Data Mining" o Minería de Datos tiene importantes exponentes del área de optimización como lo son las diferentes técnicas de las famosas SVM o Máquinas de Vectores de Soporte.

Estas tienen como particularidad que minimizan el error de clasificación empírico (de allí que sean de Aprendizaje Supervisado) al mismo tiempo que maximizan la distancia que tiene la superficie separadora de las dos clases respecto a los elementos de esas clases que separa. Los problemas de minimización o maximización siempre buscan el comportamiento óptimo de un sistema. En este caso, la función a optimizar es al mismo tiempo los errores y el mencionado margen. Esta optimización simultánea fue deducida por Vapnik como parte de los aportes colaterales de sus nuevas propuestas en el área de la estadística, con apoyo de Chervonenkis.

Hay otros métodos de optimización que atacan problemas de Minería de Datos, por supuesto. Uno de ellos que me parece extremadamente interesante, aunque luego de su surgimiento no ha habido grandes avances en ese respecto, son los métodos "multi-superficie". En ellos se generan, siguiendo una estrategia "golosa", múltiples superficies, que seccionan el espacio en el que se encuentran los elementos a ser clasificados. La máquina de aprendizaje resultante no hace otra cosa que evaluar en cuál de las áreas delimitadas por esas superficies está el individuo que se desea clasificar. La respuesta es: la misma clase que tienen mayoritariamente los individuos de esa área.

Este tipo de estrategias generan, como sub-producto de su uso, el diseño de una red neural (perceptrón multicapa), o un árbol de clasificación.

En mi opinión es muy interesante el hecho de que algoritmos como estos puedan generar redes neurales de clasificación binaria "sin intervención humana". Es bien sabido en la comunidad de las redes neurales, que resolver un problema con redes neurales, la mayor parte de los casos puede considerarse no sólo una ciencia sino un arte, debido a que hay muchas decisiones "arbitrarias" que tomar, y que por ende provocan largas sesiones de ensayo y error, tanteo, o entonamiento. Hay que decidir, cuantas neuronas usar, de qué tipo, conectadas en qué forma, y por si fuera poco, luego decidirse por una estrategia para el entrenamiento.

El uso de algoritmos que propongan ya de por si la estructura y parámetros de la red, hace que el proceso de construír una red neural de clasificación deje de ser un arte, para empezar a convertirse en un proceso ya automático.

Por último, en este post de reflexiones sobre el uso de la optimización para resolver problemas de máquinas de aprendizaje, quiero asomar una idea. Invariablemente, la construcción de máquinas que aprendan a hacer clasificación binaria, basándose en los errores, implica el uso de técnicas para conseguir parámetros óptimos para esas máquinas. En el caso de las redes neurales como los Perceptrones Multicapa, es común el uso de algoritmos asociados al Backpropagation. Mi comentario es el siguiente: desde el punto de vista de optimización, la forma en que se plantea el problema que resuelve la retropropagación, es el tipo de problemas que todo optimizador quiere evitar, ya que:
* la función a optimizar no es convexa
* hay abundancia de óptimos locales
* hay abundancia de puntos estacionarios en los que un algoritmo de optimización fácilmente "cree haber llegado".

Para evitar algunos de esos problemas, se "distorciona" la función de transferencia de las neuronas del perceptrón multicapa, para que la función sea una sigmoidal "suave", en lugar de una función tipo "escalón", lo que da orígen a clasificaciones difusas (sin que en ello esté involucrada la batería de herramientas de las que se aprovisiona la lógica difusa para resolver estas situaciones).

Bueno, es probable que el 99.99% de las personas que lean esto se pregunten ¿y cómo piensa Orestes entrenar un perceptrón sin usar los principios de la retropropagación? Bueno. La respuesta es: buscándole la vuelta al problema, para sólo resolver problemas convexos. Más adelante les seguiré contando.