Resumen

Presentamos en este artículo la paralelización de la prueba leave-one-out, la cual es una prueba repetible pero que, en general, resulta costosa computacionalmente. La paralelización se implementó sobre arquitecturas multi-núcleo con múltiples hilos, usando la taxonomía Flynn Single Instruction Multiple Data. Esta técnica se empleó para las etapas de preproceso y proceso de dos algoritmos de clasificación que están orientados a enriquecerla representación en casos de muestra pequeña: el algoritmo de la línea de características más cercana (NFL) y el algoritmo del segmento de línea rectificado más cercano (RNFLS). Los resultados obtenidos muestran una aceleración de hasta 18.17 veces con el conjunto de datos mas pequeño y de 29.91 veces con el conjunto de datos más grande, empleando el algoritmo más costoso —RNFLS— cuya complejidad es O(n⁴). El artículo muestra también los pseudocódigos de los algoritmos seriales y paralelos empleando, en este último caso, una notación que describe la manera como se realizó la paralelización en función de los hilos.

1 INTRODUCCIÓN

Los algoritmos de clasificación pueden clasificarse a grandes rasgos en clasificadores basados en la disimilitud, clasificadores probabilísticos y clasificadores geométricos [1]. Los primeros asignan un objeto no etiquetado -representado como un vector de características x- a la clase de los ejemplos más similares dentro de un conjunto de vectores de características etiquetados (también conocidos como objetos de entrenamiento) o dentro de modelos previamente construidos a partir de ellos; los segundos estiman las densidades de probabilidad condicional de clase utilizando los objetos de entrenamiento y, posteriormente, asignan etiquetas de clase a los no etiquetados de acuerdo con las probabilidades máximas posteriores; la tercera categoría de clasificadores construye directamente los límites entre las regiones de clase en el espacio de características optimizando criterios como el error de clasificación y el margen máximo de separación entre clases. La regla del vecino más cercano (1- NN) es el ejemplo paradigmático de los clasificadores basados en la disimilitud; es muy natural, intuitiva para los no expertos [2] y exhibe un rendimiento de clasificación competitivo siempre que se disponga de un conjunto de entrenamiento suficientemente grande. Se han propuesto varias variantes para mejorar el 1-NN, entre ellas el llamado clasificador de la línea de características más cercana (NFL) [3] que amplía el poder de representación de un conjunto de entrenamiento de cardinalidad limitada construyendo un modelo lineal (una línea de características) entre cada par de vectores de características de entrenamiento de la misma clase.

• Materias:Arquitectura de computadores Algoritmos (Computadores) Redes neuronales (Computadores)
• Subjects:Computer architecture Computer algorithms Neural networks (Computer science)
• Palabras claves:Computación con múltiples núcleos; Algoritmos de clasificación; Prueba leave-one-out
• Keywords:Multi-core computing; Classification algorithms; Leave-one-out test