Empleo de modelos de optimización matemática en la solución de problemas computacionales
RESUMEN
Introducción.

La presente investigación se enmarca en la introducción de nuevos métodos computacionales de optimización matemática para el estudio de problemas de estimación de múltiples indicadores.

Métodos.

Se incluyen un grupo de propuestas de algoritmos de aprendizaje, modelados eficientemente por medio de métodos de optimización ajustados a cada problema y sus aplicaciones en la predicción de múltiples indicadores. Se resuelve eficientemente la introducción de regularizadores apropiados para el entrenamiento simultáneo de varias estructuras de aprendizajes de bajo rango y el aprendizaje de funciones de distancias.

Resultados y Discusión.

Se comprobó experimentalmente, sobre 18 conjuntos de datos disponibles. Los resultados muestran superioridad de la propuesta respecto a los algoritmos del estado del arte MSLR y MMR en tanto los tiempos de ejecución son significativamente menores. Los algoritmos meta-heurísticos basados en métodos de continuación propuestos en el presente trabajo obtienen un menor valor del error de generalización y error de entrenamiento, con diferencia estadísticamente significativa, respecto al algoritmo gradiente descendente estocástico en el entrenamiento de redes neuronales artificiales. Los resultados de introducir el algoritmo DMLMTP demuestran una mejora significativa respecto al algoritmo base KNN-SP propuesto previamente como parte del aprendizaje basado en instancias. Conclusiones, se proponen modernos métodos de optimización matemáticas para la solución de problemas de predicción de múltiples indicadores, posiblemente correlacionados los cuales mejoran los resultados de exactitud del estado del arte en tanto su diseño denota una elevada eficiencia. Se logran aplicaciones concretas en la estimación de la aparición a corto y largo plazo de COVID-19 que validan la investigación.

ABSTRACT
Introduction.

The current research is framed in the introduction of new computational methods of mathematical optimization for multitarget regression problems.

Methods.

A group of proposals of learning algorithms are included, efficiently modeled by means of optimization methods adjusted to each problem and their applications in the multitarget regression. The introduction of appropriate regularizers is efficiently solved for the simultaneous training of several low range learning structures and distance metric learning.

Results and Discussion.

It was tested experimentally, on 18 sets of available data. The results show the superiority of the proposal with respect to the state-of-the-art algorithms MSLR and MMR in that the execution times are significantly lower. The meta-heuristic algorithms based on continuation methods proposed in the present work obtain a lower value of the generalization error and training error, with statistically significant difference, with respect to the Stochastic Gradient Descent algorithm in the training of Artificial Neural Networks. The results of introducing the DMLMTP algorithm demonstrate a significant improvement over the KNN-SP algorithm previously proposed as part of the instance-based learning. As some conclusions, modern mathematical optimization methods are proposed for the solution of prediction problems of multiple indicators possibly correlated which improve the accuracy results of the state of the art as their design denotes high efficiency. Concrete applications are achieved in the estimation of the short- and long-term forecasting of COVID-19 that validate the research.

Palabras clave:
    • optimización matemática;
    • predicción de múltiples indicadores;
    • aprendizaje de funciones de distancia;
    • regresión lineal multivariada.
Keywords:
    • mathematical optimization;
    • multitarget regression;
    • distance metric kearning;
    • multivariate response.

INTRODUCCIÓN

Los métodos tradicionales de clasificación en aprendizaje automático supervisado asumen que se desea estudiar una variable expresada en un dominio que pueden ser valores reales, binarios, categóricos u ordinales. En los últimos años, en la rama de aprendizaje automático han aparecido problemas de la vida práctica donde los esquemas tradicionales de aprendizaje se deben ajustar a escenarios donde existen variable posiblemente correlacionadas entre sí. En este sentido existen campos muy diversos de aplicaciones como son la clasificación multietiqueta, predicción multitarea, predicción con salidas múltiples entre muchas otras aplicaciones.1

La solución al problema de aprendizaje en el manejo de múltiples indicadores tiene su esencia en el tratamiento de la dependencia condicional en las variables del espacio de salida como parte del proceso de aprendizaje. En este sentido se han identificado diversas maneras de abordar el problema de aprendizaje que van desde la estadística multivariada,2,3 el aprendizaje de funciones de distancias4,5 y el empleo de redes neuronales artificiales6 para combinar, de alguna manera, las variables de entrada y salida. Para abordar cada uno de los enfoques descritos, se modelan métodos de optimización específicos y diversos en el proceso de aprendizaje.

La mayoría de los trabajos reportados adoptan un método de optimización específico como solución al problema de optimización, descuidando la eficiencia computacional del proceso de aprendizaje como es el caso de los métodos cuadráticos,7,8 los dependientes del Hessiano9 o basados en el problema de Sylvester.10,11 De igual manera varios de los enfoques se basan en la estimación de varias estructuras de aprendizajes los cuales transitan por procesos de optimización independientes sin tomar en cuenta la convergencia global del problema de optimización y por ende lograr soluciones precisas en el aprendizaje. La presente investigación introduce métodos de optimización apropiados, basados en gradiente proximal acelerado, algoritmos metaheurísticos y aprendizaje por continuación.

Como resultado, el presente trabajo incluye un grupo de propuestas de algoritmos de aprendizaje, modelados eficientemente por medio de métodos de optimización ajustados a cada problema y sus aplicaciones en problemas de predicción de múltiples indicadores. Los resultados computacionales han sido abordados desde la mejora en eficiencia del entrenamiento de una red neuronal artificial (RNA) por medio de algoritmos metaheurísticos basados en continuación, el uso eficiente de regularizadores para el entrenamiento simultáneo de varias estructuras de aprendizajes de bajo rango y el aprendizaje de funciones de distancias de Mahalanobis con algoritmos de optimización eficientemente diseñados.

MÉTODOS

Algoritmo de estimación de dependencia Generalized multitarget linear regression with output dependence estimation

Para un problema de predicción con salidas múltiples se intenta predecir simultáneamente y con un único modelo, el conjunto de valores reales expresados en forma vectorial y con cierta relación entre ellos. Nuestra propuesta se basa en un esquema general, flexible y adaptable a diferentes escenarios y regularizadores que hemos denominado Generalized multitarget linear regression with output dependence estimation (GMLR).12 EL algoritmo está basado en la regresión lineal múltiple con introducción de un espacio de variables latentes, a través de las cuales se estiman las relaciones de dependencia en el espacio de salida. El algoritmo GMLR, se ha formulado de modo que pueda adecuarse a la posible no linealidad a la que puede responder la distribución de los datos. Para ello se ha diseñado la variante con Kernel KGMLR. La principal ventaja de la propuesta diseñada es la escalabilidad para considerar disímiles situaciones aprovechando las bondades del método de optimización gradiente proximal acelerado. Nuestra propuesta es capaz de reproducir, como casos particulares, algoritmos recientes que se encuentran en el estado del arte en la predicción con salidas múltiples como es el caso del MSLR y MMR.2,3 Otra de las ventajas, en el uso del método de optimización gradiente proximal acelerado, es la mejora que introduce en la eficiencia computacional respecto al estado del arte, donde la solución del método de optimización, por derivación directa del problema de Sylvestre, es ineficiente.10-14

Aprendizaje de funciones de distancia

Cuando no hay ningún conocimiento disponible sobre el dominio de aplicación o incluso en presencia de tal conocimiento, por lo general, las implementaciones de k-NN15 utilizan la función de distancia euclidiana.a Sin embargo, la utilización de una función de distancia adecuada es fundamental para el uso de cualquiera de los algoritmos de clasificación basados en vecindad. Para problemas de predicción con salidas múltiples, se introduce el algoritmo denominado DMLMTP siendo la primera vez que se adapta el aprendizaje de funciones de distancia en el ámbito de la predicción con salidas múltiples.16

El algoritmo DMLMTP no toma en cuenta, directamente, la dependencia condicional entre las variables de salida en el proceso de aprendizaje, lo cual es relevante en problemas de predicción con salidas múltiples. Por otra parte, el DMLMTP emplea una matriz diagonal en la estructura de la función de distancia, que representa los pesos de cada atributo de entrada lo cual impone limitaciones. Estas 2 limitaciones motivaron estudiar el problema de la dependencia entre las variables de salidas y el aprendizaje de funciones de distancia, con estructuras de aprendizaje más robustas y funciones no lineales, como las que se proponen en los trabajos de Weinberger KQ, et al. y González H, et al.17,18

Para definir el algoritmo DMLMTP se generaliza la heurística planteada en Schultz M et al19 la cual queda expresada de la siguiente manera: Objetos cercanos respecto a otros en el espacio de salida deberán estar más cercanos en el espacio de entrada, mientras que objetos alejados en el espacio de salida deberán alejarse en el espacio de entrada. Recordemos que los objetos, en el espacio de salida, están expresados como vectores de valores reales por lo que se hace necesario medir la proximidad entre objetos de dicho espacio.

Algoritmos metaheurísticos y métodos de continuación

El campo de investigaciones referido a las RNA es uno de los más activos en la comunidad científica con múltiples aplicaciones recientes en actividades como el reconocimiento de imágenes, el procesamiento de señales y el reconocimiento de voz. De forma general, las RNA se emplean para la resolución de una serie de problemas bien establecidos como agrupamiento, clasificación y regresión. Por lo general, el entrenamiento de una RNA se concibe como un problema de optimización sin restricciones sobre un conjunto de parámetros reales y una función objetivo, donde es necesario encontrar los valores de los parámetros que minimicen o maximicen el valor de la función objetivo. El entrenamiento de una RNA se considera un problema de optimización de complejidad NP-difícil.

Las dificultades del entrenamiento neuronal han motivado la aparición de estudios relacionados con el empleo de metaheurísticas alternativas a los métodos de primer y segundo orden. Esto se sustenta en la elevada complejidad temporal del cálculo de la función objetivo durante el entrenamiento limitando el tratamiento de problemas donde la cantidad de parámetros sobrepase el orden de las decenas y la cantidad de casos de entrenamiento sobrepase el orden de los cientos. De ahí que, la segunda propuesta desarrollada en nuestra investigación se centre en desarrollar algoritmos basados en metaheurı́sticas de optimización y métodos de continuación para el entrenamiento de RNA, aumentando la precisión respecto a gradiente descendente estocástico y la eficiencia de los algoritmos metaheurı́sticos.14

Predicción de popularidad de video con métodos de continuación

En el presente trabajo se desarrolla un algoritmo para la predicción de reproducciones de video basado en redes neuronales multicapa con entrenamiento metaheurístico y métodos de continuación. Los resultados muestran que los algoritmos metaheurísticos acoplados con métodos de continuación obtienen mayor precisión que gradiente descendente estocástico con diferencia estadísticamente significativa y el tiempo de ejecución del entrenamiento es significativamente inferior respecto a los algoritmos meta-heurísticos estándar.

Se considera un modelo de RNA conformado por una capa de entrada, una capa oculta y una capa de salida. La capa intermedia posee 45 neuronas con función de activación de tipo ReLU. La capa de salida posee una neurona de tipo ReLU. Todas las capas son de tipo totalmente conexas.

En la tabla 1 se detallan los resultados obtenidos en cuanto error de generalización y error de entrenamiento luego de 50 mediciones para el modelo de ANN descrito. Para cada algoritmo se especifica la media y la desviación estándar de la precisión entre paréntesis.

Media y desviación del error de entrenamiento
Método Generalización Entrenamiento
SGD 3,95 E-03 (3,20 E-05) 1,15 E-03 (9,45 E-6)
PSO 1,79 E-03 (1,56 E-05) 1,05 E-03 (8,84 E-6)
CPSO 1,76 E-03 (7,92 E-06) 1,07 E-03 (7,05 E-6)
FA 2,54 E-03 (2,85 E-05) 1,14 E-03 (1,02 E-5)
CFA 2,21 E-03 (8,41 E-06) 1,21 E-03 (7,43 E-6)
CS 2,82 E-03 (7,51 E-06) 1,19 E-03 (5,25 E-6)
CCS 2,75 E-03 (5,12 E-06) 1,31 E-03 (4,94 E-6)

Al aplicar la prueba no paramétrica de Friedman para un nivel de significancia de 0,05 se obtienen valores de F = 30,622; p-valor < 0,01 por lo que se rechaza la hipótesis nula, existiendo diferencias estadísticamente significativas entre los algoritmos de entrenamiento. Al existir diferencias estadísticamente significativas entre los algoritmos, se procede con el posthoc de Nemenyi como se muestra en la figura.

Diagrama de diferencias críticas entre los algoritmos de entrenamiento.

A partir de los resultados presentados en la comparación de los algoritmos de entrenamiento estudiados, se refieren las siguientes conclusiones: Se conforman 2 grupos de algoritmos, denominados grupo a y grupo b, conformados por SGD y CPSO respectivamente. Entre los algoritmos del grupo a y el grupo b existen diferencias estadísticamente significativas para un nivel de confianza de 0,05.

Para el caso de los algoritmos, SPSO, SFA y CFA los datos experimentales obtenidos no son suficientes para determinar si pertenecen al grupo b o a un grupo diferente. Una situación similar se observa en el caso de los algoritmos SCS y CCS para los cuales los datos experimentales obtenidos no son suficientes para determinar si e pertenecen al grupo a o a un grupo diferente.

RESULTADOS Y DISCUSIÓN

A partir del estudio conducido en la presente investigación, las evidencias obtenidas y los experimentos desarrollados muestran los siguientes resultados: Con la propuesta del modelo GMLR para el tratamiento de la dependencia condicional entre variables de salida se obtiene un modelo general que puede ser empleado en diversos esquemas de aprendizaje y que toma como casos particulares los algoritmos del estado del arte disponibles.

Al introducir el algoritmo GMLR, para abordar la dependencia condicional entre las variables de entrada y salida se comprobó experimentalmente, sobre 18 conjuntos de datos disponibles, la escalabilidad de la propuesta realizada. Para medir la eficiencia de la propuesta GMLR, basada en el método del gradiente proximal acelerado, se implementaron los algoritmos originales MMR y MSLR y se compararon computacionalmente, obteniendo una superioridad en los tiempos de ejecución de la propuesta, así como una mejora considerable en la complejidad computacional teórica y las tasas de convergencias.

Se desarrolló un método de continuación para el entrenamiento de RNA basado en algoritmos metaheurísticos, con el fin de aumentar la precisión obtenida mediante el algoritmo gradiente descendente estocástico y aumentar la eficiencia de los algoritmos metaheurísticos. Los algoritmos meta-heurísticos basados en métodos de continuación desarrollados en el presente trabajo obtienen un menor valor del error de generalización y error de entrenamiento, con diferencia estadísticamente significativa, respecto al algoritmo gradiente descendente estocástico en el entrenamiento de RNA. Los algoritmos metaheurísticos basados en continuación obtienen resultados similares al considerar la precisión respecto a sus versiones estándares, sin embargo, el tiempo de ejecución es significativamente menor.

En los trabajos asociados a la presente investigación se introduce una familia de algoritmos de aprendizaje de funciones de distancia para problemas de predicción con salidas múltiples (DMLMTP y APG_MLKR con sus variantes). En el caso del algoritmo DMLMTP, se desarrolló un método de optimización propio, basado en SMO, para resolver el problema de optimización en el dual. Los resultados de introducir el algoritmo DMLMTP demuestran una mejora significativa respecto al algoritmo base KNN-SP 20,21 propuesto previamente como parte del aprendizaje basado en instancias. De igual manera, estos resultados fueron comprobados haciendo uso de diferentes funciones de predicción, siendo en todos los casos el DMLMTP el que alcanza los mejores resultados. Los resultados experimentales de los modelos APG_MLKR y BR_MLKR denotan, resultados equivalentes a los modelos lineales para determinados dominios de aplicaciones y en menor medida, resultados superiores para aquellas bases de datos que pudieran responder a un comportamiento no lineal entre sus variables.

Desde el punto de vista aplicado, los hallazgos de esta investigación han logrado importantes resultados que impactan en productos de software ampliamente utilizados a nivel mundial y en el contexto cubano. Estos productos están relacionados con los métodos de inteligencias artificial, el aprendizaje automático supervisado y las técnicas de minería de datos que pueden ser empleados como valor agregado en diferentes sistemas informáticos. A continuación, se detallan las aportaciones prácticas que sustentan el resultado alcanzado.

En tal sentido se han integrado algoritmos clásicos de aprendizaje de funciones de distancia en la herramienta WEKA como parte del desarrollo de la tesis de pregrado titulada: Implementación de algoritmos basados en aprendizaje de funciones de distancia para problemas de clasificación en la herramienta WEKA, desarrollada por coautores de la presente investigación.

Por otra parte, se han desarrollado diversos algoritmos del estado del arte y los propuestos por el autor en la herramienta de código abierto MULAN. Esta herramienta está disponible para investigadores y desarrolladores de MULAN.b Como parte de esta herramienta se han incorporado los algoritmos del estado del arte KNN-SP y los métodos de estadística multivariada RRR, C&W, MRCE y FES como parte de la tesis: Extensión de algoritmos de estadística multivariada para problemas de predicción con salidas compuestas como parte de la herramienta MULAN.

En la presente investigación, se han implementado un grupo de algoritmos meta-heurísticos para el entrenamiento de RNA, que incluye la implementación de métodos de continuación, en una biblioteca de clases disponible libremente en Internet.c Esta biblioteca posee implementaciones secuenciales y paralelas para procesadores multinúcleos y Graphic processing units que permite el tratamiento de problemas de elevada complejidad computacional. Este resultado es fruto de la tesis de maestría: Algoritmos meta-heurísticos de optimización aplicados al entrenamiento de redes neuronales profundas y las tesis de grado: Implementación de funciones de optimización estándar en paralelo para la biblioteca dnn_opt, Implementación del algoritmo meta-heurístico Gray wolf optimization para la optimización de funciones objetivos estándar y finalmente Implementación de rutinas para la lectura de conjuntos de datos en diferentes formatos de fichero para la biblioteca dnn opt.

Adicionalmente, el entrenamiento de RNA mediante algoritmos meta-heurísticos y métodos de continuación, específicamente aplicados al problema de predicción de la popularidad de videos para la plataforma de contenidos audiovisuales, permitió corroborar a escala de laboratorio un decremento importante del número de fallas de caché con un beneficio económico importante por concepto de sustitución de importaciones. Este resultado fue parcialmente derivado de la tesis de grado: Módulo para la recomendación de contenidos audiovisuales en la plataforma Internos 2.0.

De las aplicaciones más recientes donde se han aplicado los resultados teóricos de los modelos de predicción con salidas múltiples podemos mencionar la introducción de un nuevo algoritmo para el pronóstico a corto plazo de nuevos casos de COVID-19 modelados como un problema estacionario de aprendizaje.22 El pronóstico de aparición de nuevos casos acumulados de infectados de COVID-19 cada día en el país es un elemento clave en la toma de decisiones de las autoridades gubernamentales y sanitarias. Este número depende de varios factores, la mayoría de los cuales son muy difíciles de cuantificar de forma precisa. En tal sentido, estudios revelan que la aparición de nuevos casos está relacionada con la tasa de transmisión del virus, la duración de la enfermedad, la movilidad de las personas y las medidas higiénicas y de aislamiento social que ellas tomen.23 Excepto la duración de la enfermedad, el resto de los factores resulta imposible cuantificarlos con precisión. Es por ello que en este trabajo se intenta construir un modelo predictivo a partir de los datos disponibles de nuevos casos aparecidos cada día, desde el inicio de la epidemia. Este tipo de datos, coleccionado de forma periódica de una variable de interés, se conoce como serie temporal univariada. Tradicionalmente el pronóstico en series de tiempo se realiza utilizando herramientas estadísticas bien establecidas como por ejemplo los modelos auto-regresivos de Box-Jenkins o el enfoque de Holt-Winters al suavizado exponencial.24 Sin embargo, existe un marcado interés en la comunidad científica por abordar esta problemática utilizando técnicas de aprendizaje automático. En tal sentido nuestro trabajo fue dirigido a la utilización de técnicas convencionales del aprendizaje automático para el pronóstico de nuevos casos acumulados de infectados en un día del COVID-19, a partir del comportamiento de los días anteriores.

Desde otra perspectiva, el empleo de algoritmos metaheurísticos aplicados al ajuste de modelos epidemiológicos susceptible-expuestos-infectados-recuperados, permitió predecir el comportamiento a largo plazo de la epidemia causada por el SARS CoV-2 diseminada durante el 2020.

Conclusiones

Se proponen modernos métodos de optimización matemáticas para la solución de problemas de predicción de múltiples indicadores, posiblemente correlacionados los cuales mejoran los resultados de exactitud del estado del arte. Al mismo tiempo los resultados de eficiencia computacional de los algoritmos propuestos son muy superiores a los ya existentes. Se logran aplicaciones concretas en la estimación de la aparición a corto y largo plazo de COVID-19 lo cual da una validación práctica a los resultados teóricos alcanzados.

Notas al pie:
  • Este trabajo ha recibido financiamiento por FEDER and Spanish MEC mediante el proyecto TIN2014-59641-C2-1-P y UVEG grant INV17-01-15-03. De igual forma las participaciones en los congresos CIARP 2016 y 2018 fue parcialmente financiado por el proyecto Project ELINF “ICT Supporting the educational processes and the knowledge management in higher education”.

REFERENCIAS BIBLIOGRÁFICAS
Historial:
  • » Recibido: 10/02/2022
  • » Aceptado: 23/03/2022
  • » Publicado : 01/11/2022


Copyright (c) 2022 Jairo Rojas Delgado et al.

Licencia de Creative Commons
Esta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial 4.0 Internacional.