Algoritmos en Línea

Se dice que un algoritmo es en línea (en inglés on line) cuando es capaz de ponerse a trabajar en el problema para el que fue diseñado sin necesidad de disponer de todos los datos de entrada antes de empezar, es decir, que puede trabajar a medida que va recibiendo los datos de entrada.

Por ejemplo, el algoritmo de ordenación BubbleSort no es un algoritmo en línea (podría decirse que es fuera de línea u offline), porque si tiene que trabajar sobre 10 valores, necesita que los diez valores estén disponibles al comienzo del algoritmo. Sin embargo, el algoritmo de ordenación InsertionSort sí es un algoritmo en línea, porque si tiene que trabajar sobre 10 valores, puede leer el primero y procesarlo, y luego el segundo y procesarlo, y luego el tercero y procesarlo... ý así hasta el último. Puede realizar parte de su trabajo con una entrada parcial de los datos, ya que el procesamiento de los datos sólo depende de los datos de entrada leídos hasta el momento, y no de la totalidad.

Spam

Cuando un correo electrónico no  ha sido solicitado por el destinatario, nace el término de spam, junk mail o más formalmente “correo electrónico comercial no solicitado”.

El contenido de un mensaje spam es variado, pero siempre dentro de los mismos márgenes: ofertas de cualquier tipo de producto, ofertas para hacerse ricos en poco tiempo y sobre todo, contenido pornográfico, siendo los receptores de spam los grandes perjudicados por la obligación a utilizar las líneas de comunicación para descargar los correos, aparte de la pérdida de tiempo que se invierte en eliminar los correos no deseados.

En este punto, es donde entran en juego los dos tipos de medidas anti-spam que existen actualmente: medidas legales y medidas técnicas. En este espacio hablaremos de las medidas técnicas orientada al tema que estamos tratando.

Una de las medidas técnicas que se están estudiando son  las máquinas de soporte vectorial (SVM, Support Vector Machines), que son construcciones matemáticas que buscan hiperplanos no lineales en el espacio utilizando transformaciones de Lagrange. Son muy populares en los campos de aprendizaje automático y la minería de datos debido a su capacidad de generalizar y de manejar grandes dimensiones de datos a través del uso de núcleos (kernels). La idea básica de un kernel es que proporciona una función que permite la transformación de un espacio de características, a priori no separables linealmente, en un espacio de características con varias dimensiones que sí son separables linealmente.

Las principales ventajas derivadas de la utilización de este método son su rápida velocidad en tiempo de ejecución y el hecho de que no son influenciadas por la distribución de clase en los ficheros de entrenamiento. Como desventaja más importante está el hecho de que consumen mucho tiempo de entrenamiento si el fichero contiene muchos correos.

Un requerimiento importante para cualquier algoritmo en línea es que su complejidad paso a paso este acotada por una constante independiente del tiempo t, para lo cual se asume que los datos se obtienen de manera constante. Y dado que la complejidad de SVM es dependiente del número de datos de entrenamiento, obtener una solución sparse es esencial para el aprendizaje. Mientras que se puede utilizar el algoritmo por lotes utilizando un buffer deslizante para aplicaciones en línea, es mucho mejor desarrollar un algoritmo que trabaje en línea.

En conclusión tenemos que los algoritmos en línea procesan información al momento que la reciben, una aplicación importarte e interesante es en la detención del spam, para esto se está trabajando con las máquinas de soporte vectorial, pero aún sigue en investigación.

Para mayor información pueden consultar la tesis Las máquinas de vectores de soporte para identificación en línea del Ing. Juan Angel Resendiz Trejo.