Algoritmos para la generación de datos subrogados: análisis, implementación y paralelización

Abstract

[EN] Abstract Surrogate methods are very useful in nonlinearities detection application and supervised detection or classification where there aren’t available sufficient data. In both cases it’s needed optimize runtime methods so, in the case of detecting nonli- nearities can be performed virtually in real time and in the case of generating data they can be large. The present work analyzes the major algorithms and design an implementation op- timized of the different versions of them.

[ES] El diseño supervisado de detectores/clasificadores requiere de la disponibilidad de un número suficiente de datos etiquetados en todas las posibles hipótesis/ categorías a las que debemos asignar cada nueva medida. Sin embargo, en numerosas aplicaciones, esta disponibilidad no está garantizada. Así por ejemplo, en detección de defectos en materiales mediante técnicas no destructivas, el número de registros correspondientes a defectos suele ser órdenes de magnitud inferior al número de registros de ausencia de defecto (¿ruido¿). Esto es generalizable a otras áreas donde un comportamiento ¿anómalo¿ infrecuente debe ser detectado frente a un comportamiento ¿normal¿. La detección de fraudes en operaciones financieras es otro ejemplo ilustrativo. Todo ello lleva a la necesidad de generar a partir de un conjunto limitado de mediciones reales, réplicas de los datos que reproduzcan adecuadamente el comportamiento deseado. Estas réplicas pueden generarse tanto en el dominio de las propias mediciones (señales adquiridas), como en el dominio de los vectores de características u observaciones que constituyen la entrada al detector/clasificador. Una opción para la generación de réplicas es utilizar la subrogación. Originariamente, la subrogación se propuso para testear la presencia de no linealidades en señales, pero posteriormente se ha propuesto también como un método que permite generar réplicas a partir de registros de datos o señales reales manteniendo las propiedades de correlación (o equivalentemente espectro) y de distribución marginal de las amplitudes [1], [2], [3]. La generación de dichas réplicas tiene un alto coste computacional, especialmente en el caso multivariante. Por ello resulta necesario el uso de técnicas de paralelización para que la generación de las réplicas pueda realizarse en un tiempo razonable. El objetivo de esta tesina es analizar los diferentes algoritmos existentes, proponer nuevas extensiones de los mismos, verificarlos en datos reales y analizar la problemática computacional involucrada, proponiendo soluciones que aceleren su ejecución. Para ello se consideran las siguientes tareas que se desarrollarán de manera secuencial: -estudio/implementación de los algoritmos de subrogación propuestos hasta ahora -propuesta e implementación de extensiones de los anteriores algoritmos. En particular se considerará la extensión a señales complejas, ya que hasta ahora los algoritmos sólo trabajan con señales reales. También se considerará la posibilidad de generar réplicas de las denominadas señales sobre grafos [4]. -aplicación y verificación en señales reales -paralelización de los algoritmos, especialmente en el caso de señales multivariantes.

[1] T. Schreiber and A. Schmitz, ¿Surrogate time series,¿ Physica D, vol. 142, no. 3-4, pp. 346¿382, 2000. [2] P. Borgnat, P. Abry, P. Flandrin, "Using surrogates and optimal transport for synthesis of stationary multivariate series with prescribed covariance function and non-Gaussian joint distribution," Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2012, pp. 3729-3732, 2012 [3] A. Salazar, G. Safont, L. Vergara: Surrogate Techniques for Testing Fraud Detection Algorithms in Credit Card Operations, 2014 IEEE International Carnahan Conference on Security Technology (ICCSR 2014), Roma (Italia), 2014. [4] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, P. Vandergheynst: ¿The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains,¿ IEEE Signal Process. Mag., vol. 30, pp. 83¿98, 2013.