Enfoques basados en optimización convexa para clasificación de patrones

Tal y como lo comenté anteriormente, el próximo martes 8 de mayo de 2012, en la Sala Carlos Aragone, Edf. FEI-256 (segundo piso), de la Universidad Simón Bolívar (USB), a las 2:30pm se dictará un seminario titulado:

ENFOQUES BASADOS EN OPTIMIZACION CONVEXA
PARA LA CLASIFICACION DE PATRONES

El expositor, el Prof. Orestes Manzanilla (del Dpto. Procesos y Sistemas de la USB)

Resumen

En este seminario se mostrará un enfoque novedoso para resolver un problema específico dentro de las áreas de minería de datos, aprendizaje artificial y reconocimiento de patrones: el de la clasificación de patrones. Este es un problema con diversas aplicaciones, entre las cuales se puede mencionar el apoyo en
prognosis médica, otorgamiento de créditos, categorización de textos, prospección petrolera, detección de patrones de fraude, detección de patrones físicos (sonoros, visuales, etc), análisis de perfiles de expresión genética, ADN y proteínas diversas. Se hará un breve repaso de las técnicas más comunes para la resolución de este problema,  nacidas de la estadística, y de distintos campos de “máquinas de aprendizaje”, algunos de ellos bio-inspirados, indicando brevemente las ventajas y desventajas de cada método.

Se expondrá un grupo de heurísticas basadas en optimización lineal, y lineal entera-mixta para la generación de clasificadores de patrones de tipo no-lineal (pero lineal por partes), que puede representarse tanto como redes neurales artificiales, como árboles de clasificación, explicando las ventajas y  desventajas que comparativamente se observan respecto a los métodos mencionados anteriormente.
Los métodos están orientados hacia la búsqueda de (1) la minimización de la dependencia del “éxito” de la implementación, de la experticia del implementador, cerrando la brecha "tecnológica" que actualmente mantiene a los no-expertos alejados de este tipo de problemas, y (2) la escalabilidad de la técnica, para garantizar su aplicabilidad en bases de datos masivas. Por último, se esboza el posible uso de las  estructuras no-lineales generadas en el espacio multi-dimensional, ya no tanto para la predicción de la categoría o patrón de un nuevo
indivíduo de clase desconocida, sino para la visualización de los patrones en el espacio multi-dimensional.

Palabras claves: Programación lineal, Redes neurales artificiales, Máquinas de Soporte Vectorial, Clasificadores de patrones, Máquinas de aprendizaje.

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.

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.

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