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.