Blog sobre optimización de modelos lineales (PL)

Desde que inicié labores como profesor universitario, una de las materias que con más frecuencia dicto es una llamada "[Optimización de] Modelos Lineales". En esta materia se tratan temas de Programación Lineal y PERT-CPM, a nivel de pregrado, para las carreras de Urbanismo, Ingeniería de Computación e Ingeniería de Producción. Ocasionalmente, algunos estudiantes de otras ingenierías (Mecánica, Eléctrica y Química) han cursado la materia como electiva, motivados por profesores de ciertas materias de sus respectivas carreras, quienes les han dicho que la respuesta a determinada interrogante, sólo puede hallarse mediante Programación Lineal.
Es de mi opinión, que Modelos Lineales debería ser una materia electiva para todas las ingenierías, pero hace falta aún que haya más consciencia de las coordinaciones de las diferentes carreras, sobre el alcance en cuanto aplicaciones, que tienen las técnicas de Investigación de Operaciones.
Motivado por un curso de "Conectividad para Docentes" dictado por el Prof. Luis Ordoñez (ver el blog http://www.conectividadlatinoamericana.org/ para mayor información sobre el grupo al que pertenece), decidí plantear actividades de "conectividad" para los dos cursos que dicto este trimestre, siendo uno de ellos el de "Modelos Lineales".

Decidí evaluar a los alumnos tradicionalmente (exámenes escritos), y en paralelo evaluar un 10% en una actividad que estimulara la "conectividad". Resultado de esta actividad, es la creación del blog  http://opti-lineal.blogspot.com/, en donde están publicando información mis estudiantes, sobre temas de aplicaciones de la Programación Lineal, ayudándose con mapas conceptuales.

En futuras entregas del blog, luego de revisar más a fondo el material, publicarán mapas más refinados, y finalmente harán una prueba numérica pequeña de un caso ejemplo, para mostrarla en el blog, posiblemente resuelta en excel. Los temas han sido escogidos por ellos.

Disponibles online las tesis de maestría sobre uso de I.O. para el reconocimiento de patrones

Tengo el agrado de informar que en la página de "Reportes Técnicos" del Centro de Estadística y Software Matemático se han colgado los archivos en "pdf" de mis tesistas de maestría Ana Serra y Adriana Torres:

Los resúmenes y palabras clave los coloco a continuación:

ALGORITMO DE BOOSTING EN MÉTODOS MULTI-SUPERFICIES PARA CLASIFICACIÓN BINARIA
por Ing. Ana María Serra Balza

Existen diversas técnicas de Minería de Datos para la Clasificación Binaria. Una de sus vertientes de investigación, denominada Métodos Multi-superficies, que puede ser interpretada como otro enfoque para entrenar Redes Neuronales Artificiales, evita el reajuste de parámetros al emplear Modelos de Programación Lineal para definir las superficies de separación. Asimismo, logra esquivar el problema de Programación Cuadrática y la escogencia de la transformación Kernel en Máquinas de Vectores de Soporte. Otra vertiente, denominada Boosting, que permite articular Clasificadores Individuales “débiles” en un solo Clasificador Ensamblado “robusto” y preciso, ya ha sido implementada con otras técnicas como Máquinas de Vectores de Soporte, Redes Neuronales Artificiales y Árboles de Decisión, arrojando buenos resultados.
Se propone un Algoritmo de Boosting en Métodos Multi-superficies, que facilite el entrenamiento de la máquina de clasificación binaria en extensas bases de datos, ofreciendo resultados precisos en datos reales.

Palabras claves: Clasificación Binaria, Redes Neuronales Artificiales, Árboles de Decisión, Multisuperfici

Este trabajo resulta importante por cuanto es una estrategia válida y resistente al "sobre-ajuste" que puede utilizarse cuando la cantidad de datos es tan grande que no puede ingresarse completa dentro de los modelos de optimización que requieren los métodos multi-superficie. Adicionalmente es una excelente referencia para conocer los diferentes métodos existentes en esta área.

CLASIFICACIÓN MULTICATEGORIA DE PATRONES MEDIANTE OPTIMIZACIÓN DE MULTISUPERFICIES
por Ing. Adriana Torres García

Recientemente, con la llegada de las computadoras, la demanda en aplicaciones basadas en el reconocimiento de patrones se ha incrementado considerablemente. El uso de herramientas para el reconocimiento de patrones incluye desde aplicaciones industriales hasta aplicaciones médicas, botánicas e incluso espaciales. Estas parten del procesamiento de datos en máquinas de entrenamiento con el objeto de lograr identificar, predecir y clasificar individuos de acuerdo a sus características. Existe un sinfín de técnicas para la construcción de clasificadores dentro de las cuales se presentan los sistemas de reconocimiento de patrones con aprendizaje supervisado, los cuales permiten desarrollar herramientas de clasificación, entrenadas con datos de atributos y clases conocidas a priori. Dentro de los sistemas de reconocimiento de patrones, se encuentran las redes neuronales artificiales, las cuales, según propone Mangasarian [Man92], pueden ser diseñadas y entrenadas en base a métodos de generación de multisuperficies para responder el problema de clasificación binaria. Recientemente, Manzanilla y García Palomares, [MGP10], plantearon una mejora del algoritmo de Mangasarian al que denominaron Método de Multisuperficies No Paralelo (NPMS), el cual, en pruebas numéricas, muestra una disminución de iteraciones y una mejor capacidad de generalización. Este algoritmo tal y como está planteado hasta el momento sólo puede ser usado en problemas de clasificación binaria. El objetivo del presente trabajo de investigación es resolver el problema de clasificación multicategoría mediante la optimización de multisuperficies. Para lo cual, se realiza un análisis de los diferentes métodos de multisuperficies, se plantea un algoritmo de multisuperficies no paralelas basado en el NPMS para clasificación multicategoría, se propone una red neuronal equivalente para el clasificador y finalmente, se valida la calidad del modelo propuesto mediante la presentación de resultados favorables de pruebas realizadas en bases de datos reales usadas previamente por investigadores del área.

Palabras Clave: Aprendizaje Supervisado, Métodos Multisuperficie, Perceptrones Multicapa, Clasificación Multicategoría, Programación Lineal.

El trabajo de Adriana es muy importante por cuanto permite observar como la estrategia de planos "alternantes" resulta altamente competitiva inclusive en problemas multi-categoría. Adicionalmente muestra como la implementación de kernels sobre el espacio de las características no es una estrategia que siempre otorgue ventajas. Realiza propuestas en el mejoramiento de los resultados de los modelos de optimización que toman en cuenta el margen de separación.

Aceptado artículo sobre el uso de programación lineal para la construcción de clasificadores de patrones binarios

Fue aceptado en la revista Decision Support Systems (4ta revista en el ranking de las revistas de Investigación de Operaciones) el siguiente artículo:

García Palomares, U; Manzanilla, Orestes. "Novel linear programming approach for building a piecewise nonlinear binary classifier with a priori accuracy". DECISION SUPPORT SYSTEMS. 2011. Indexada en el SCIENCE CITATION INDEX.

En este trabajo, el prof. Ubaldo García Palomares y yo hemos diseñado un algoritmo que construye una estrutura no-lineal, pero lineal por partes, que separa la data de entrenamiento de un problema de clasificación, logrando alcanzar, en ese conjunto, una precisión tan alta como se requiera.

En cada iteración, se resuelve un modelo de programación lineal, o un número arbitrariamente pequeño de modelos de programación lineal entera-mixta. Se muestran bondades que permiten el uso de procesamiento paralelo y/o distribuído.

Entre las bondades que presenta el trabajo, al igual que otros algoritmos similares como el Multi-Superficie (MSM) de Olvi Mangasarian, es que requiere de un mínimo de parámetros a utilizar por parte del usuario, haciendo que el resultado de la aplicación del modelo sea poco dependiente de las decisiones de implantación por parte del usuario.

La estructura resultante puede ser evaluada tanto como árbol de clasificación, como red neuronal artificial.

Actualización del 11 de Abril de 2011
Puede descargarse la versión preliminar enviada para la revista Decision Support Systems, en la sección de Reportes Técnicos del CESMa (Centro de Estadística y Software Matemático), correspondiente al año 2011.

¡Aprobadas tesis de maestría en I.O. aplicada a Machine Learning!

Orgullosamente felicito a mis dos amigas y tesistas de la maestría en Ingeniería de Sistemas de la USB (opción Investigación de Operaciones), Adriana Torres y Ana Serra, quienes este viernes en la mañana tuvieron sus respectivas defensas, con un jurado integrado por mi persona, como tutor, por el prof. Marcos Raydan, como miembro principal del jurado. Los presidentes del jurado evaluador fueron, respectivamente, Ana María Borges y Hugo Montesinos.

Los nombres de los trabajos de grado son:

• "Clasificación multicategoría de patrones mediante optimización de multisuperficies" - Adriana Torres
•  "Algoritmo de Boosting en Métodos Multi-superficies para clasificación binaria" - Ana Serra

Ambas defensas tuvieron lugar en la sala de reuniones del Centro de Estadística y Software Matemático.

Felicidades por un trabajo bien hecho! Es un placer contar con tesistas de ese calibre.

Búsqueda Directa no monótona para optimización con restricciones lineales

Tengo el agrado de invitarlos a la defensa de la Tesis Doctoral denominada

     "MÉTODO DE BÚSQUEDA DIRECTA NO MONÓTONA
             PARA OPTIMIZAR UNA FUNCIÓN OBJETIVO
                SUJETA A RESTRICCIONES LINEALES"

presentada por el estudiante ILDEMARO JOSÉ GARCÍA URREA
como requisito parcial para optar al título de DOCTOR EN INGENIERÍA.

Fecha: viernes 10 de diciembre del 2010
Hora: 2:00 pm
Sitio: sala 133 del edificio Ciclo Básico 1.

Trabajo realizado bajo la tutoría del Prof. Ubaldo García Palomares

Jurado examinador:
     Prof. Bernardo Feijoo (USB),
     Prof. Marcos Raydán(UCV),
     Prof. Ubaldo García Palomares(USB),
     Prof. Ebert Brea (suplente UCV),
     Prof. Débora Cores (suplente USB)

Charla: Clasificadores multi-superficie con minimización asimétrica de errores

En el contexto del Primer Ciclo de Charlas de los Postgrados en Estadística a realizarse los días jueves de las semanas impares de este trimestre, este jueves 4 de junio de 2009 dictaré esta charla, a las 11:30 am en el edificio MyS oficina 108. Específicamente, se realizará en la sala de seminarios del CESMa-USB.

Las charlas están pensadas para que estudiantes o egresados de nuestros programas compartan resultados o avances de sus trabajos de grado, estimulando el intercambio de ideas entre los participantes.

El tema de mi ponencia, en esta ocasión, versará sobre el uso de heurísticas de optimización, para la generación de un clasificador de patrones (reconocedor de patrones) multi-superficie. Se hablará sobre las Redes Neurales Artificiales de Clasificación Binaria (perceptrones de una capa oculta), Máquinas de Vectores de Soporte (SVMs), y sobre enfoques innovadores en el tratamiento asimétrico de errores de clasificación.

Ya lista (hace tiempo) mi página académica!

Mi página académica está lista desde hace algunos meses, pero ocupado en las menudencias de la vida académica REAL, no me había ocupado de anunciarla en mi vida VIRTUAL.

Está montada, para practicidad (mía) en la plataforma de google Sites, y pueden visitarla haciendo clic aquí , o yendo al URL:
http://sites.google.com/site/omanzanillausb/

En ella he colocado todo lo referente a mi actividad académica, a saber:

• Mis actividades docentes (materias de Investigación de Operacioens, Gestión de la Producción, y Toma de Decisiones).
• Mis actividades investigativas
• Mis actividades de extensión (recientemente me incorporé al equipo de trabajo de la Unidad de Gestión Ambiental de la Universidad Simón Bolívar y estamos haciendo un proyecto en una playa venezolana pra la gestión autogestionada de desechos).

Bueno, están invitados a visitarla, y cualquier comentario puede ser dejado acá en este post, como siempre.

Pronto haré mi site personal en Google Sites, debido a que mi site en Googlepages está peligrando. No se si lo sabían, pero Googlepages está por ser descontinuado, y no quisiera que el "robot" destroce mi información al hacer la migración automática a Google Sites.

Optimización por "enjambres"

Todos hemos escuchado de los algoritmos genéticos.

Básicamente, se usan para ver, dentro de un espacio matemático, qué punto es el "mejor". Para saber cuando un punto es mejor que otro, simplemente se evalúa cierta función en ese punto, y se ve cuanto vale. Por lo general, se busca que sea lo mayor posible, o lo menor posible (problemas de maximización y minimización, respectivamente). Esa función la podemos llamar "Aptitud", o como se le nombra clásicamente en Investigación de Operaciones: Función Objetivo (puede ser minimizar costos, riesgos, distancias, o maximizar ganancias, flexibilidad, robustez, etc).

(NOTA: si tienen flojera de leer, pasen al final del post, que hay un video EXCELENTE!)

Subiendo (o bajando) montañas...

Esa solución es un vector "x". Usualmente en optimización, uno se busca un "x-inicial", y evalúa la "aptitud"de los puntos que están en los alrededores de ese lugar, y se sigue alguna estrategia para suponer hacia dónde hay que moverse para encontrar un mejor valor de la función. Una vez se determina hacia dónde se busca una mejor solución, se "avanza" un poco (una distancia a escoger juiciosamente), y tenemos una nueva "x". El proceso se repite, hasta que  uno ve que en los alrededores no hay nada mejor, y supone que llegó al "mejor" lugar (el que tiene menor valor o mayor valor en la función objetivo). Puede ocurrir que se llegó a un óptimo local (había otro máximo mejor, pero éste se encontró más rápido).

La competencia para "sobrevivir"...

En Algoritmos Genéticos, no se hace esto. Los pasos son más o menos los siguientes:

1. Generar a los competidores. Aleatoriamente creamos una cantidad grande de posibles soluciones, es decir, no una "x", sino (pongamos un número) 100 diferentes soluciones, x1, x2,..., x100. Estos serán nuestra "población".
2. Selección "natural". Ahora toca jugar a la madre naturaleza, y determinar cuáles son los mejores de ellos, es decir los más aptos. Pongamos un número: seleccionamos a los 20 mejores (se evalúa la función objetivo en cada uno y tomamos los que tienen los 20 valores más pequeños o más altos de esa función). A los que no entren en este grupo, los "matamos" (eliminamos esas variables).
   
3. Sexo libre, 100% de fertilidad, y la aparición de mutantes.  Cada uno de estos 20 ganadores, es apareado con los otros 19 (aunque pueden seguirse estrategias menos promíscuas ;D ), con un 100% de posibilidad de embarazo. Es decir, siempre se genera uno o más hijos en cada apareamiento. Puede haber apareamiento entre más de dos de los competidores, cosa que en la biología no ocurre! (aquí si tendría sentido la serie de televisión "Mis dos papás"). Cada hijo es una "x" nueva, cuyas características genéticas (valores de cada posición del vector "x"), son una mezcla de las de sus padres. Adicionalmente, aleatoriamente algunos de los hijos producidos en esta etapa tienen alguna característica genética cambiada aleatoriamente, lo que corresponde a una mutación. La población crece hasta tener 100 indivíduos nuevamente, donde están los 20 padres, y los demás son los hijos.
4. Ahora se repite el proceso, porque se vuelve a ver cuáles son los 20 más aptos, y el resto se muere, y se produce nuevamente un apareamiento... Esto se repite hasta que las diferencias de aptitud entre los miembros de la población son muy pequeñas, y están todos muy cerca (tienen genes casi iguales). En ese momento se supone que el promedio de los genes de la población es la solución al problema (el mejor valor de "x" en el espacio matemático, según esa función objetivo fijada).

Importante es notar que en este método, hay dos componentes del comportamiento del algoritmo: la exploración (generando aleatoriamente "x" por todo el espacio, y aleatoriamente generando indivíduos mutantes, de forma ciega), y la explotación (siempre matando a los peores, y dejando a los mejores, hace que se aglomeren cada vez más arriba en las "montañas" de la función objetivo). Esto hace que sea menos probable que la solucion encontrada sea un óptimo local, y en eso puede resultar mejor que la optimización clásica.

Vuelen, hijos míos, exploren, ayúdense y destruyan al enemigo!

Ahora entonces tenemos a las técnicas de Optimización por "enjambres". Estas no son una población en la que se mueren los menos aptos. Por el contrario, siguen vivos, y el que no mueran agrega ese componente de "exploración" del que hablamos en los algoritmos genéticos, pero el que compartan información, hace que busquen las partes altas del espacio matemático, lo que equivale a un comportamiento de explotación. Dicen que nadie aprende de la experiencia ajena, lo cuál es verdad en el genético, pero acá se rompe esa regla!

1. Enjambre en caos. Cada "x" nace, inicialmente, en una posición aleatoria, con una velocidad aleatoria, volando hacia una dirección aleatoria. Es decir, la locura y el caos total!
   
2. Corran la voz!... la versión matemática de un chisme. Cada indivíduo (que es una posible solución "x" al problema), se entera de en qué posición está el que, dentro de toda la población, ha conseguido un mejor espacio para explorar (el que tenga mejor valor para la función objetivo). También se entera, de entre los que estén más cerca de él, cuál es el que mejor posicionado está.
3. La información es de quién la usa!. Cada uno de los indivíduos de la población ahora decide cómo usa la información que tiene, y la pondera respecto a lo que él ya venía haciendo (por algo venía en esta dirección, no?). Aleatoriamente le da más o menos importancia al chisme de dónde está el mejor de toda la población, dondé está el mejor de sus vecinos, y hacia dónde iba cuando se enteró de estos dos chismes. Según la información, elige una nueva dirección, y camina por ahí, llegando a una nueva posición. Allí vuelven a llegarle los chismes actualizados, y se repite el proceso.
4. Cuando todos más o menos están en el mismo sitio, el promedio de los lugares en los que están se asume como la respuesta al problema.

Interesante, no?

Ahora vean un video de unos robots que tienen la tarea de arrimar un objeto hacia su base. Ninguno de ellos logra ver más allá de unos centímetros de su naríz, pero se comunican perfectamente entre ellos, y trabajan bajo la optimización de enjambres. Poco a poco ubican el objeto, y logran llevarlo hacia su objetivo. Realmente alucinante!!

(gracias Gregorio por comentarme sobre este tema y pasarme el video!)

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

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.