Mostrando entradas con la etiqueta Algoritmia. Mostrar todas las entradas
Mostrando entradas con la etiqueta Algoritmia. Mostrar todas las entradas

domingo, 10 de septiembre de 2023

Machine Learning y cambio climático



Poco se habla de la contribución del Machine Learning a las emisiones de gases de efecto invernadero. En contraste encontramos miles de artículos sobre las ventajas del Deep Learning y las maravillas de las inteligencias artificiales generativas. Como punto negativo se menciona la posible pérdida de puestos de trabajo,  algunos inconvenientes relacionados con los derechos de autor, los sesgos o si estamos marcando el camino hacia la imbecilidad colectiva confiando ciegamente en la tecnocracia de las grandes corporaciones.  Evidentemente estos temas son muy interesantes y deben ser tratados desde el punto de vista de la ética y la política, pero también me parece fundamental hablar de las consecuencias climáticas que tiene el empleo de los servidores de gran potencia que normalmente se encuentra detrás de la magia de la inteligencia artificial. Considero además que somo quienes nos dedicamos a estos asuntos los primeros que deberíamos meditar sobre las consecuencias de nuestro trabajo, por su puesto cada uno desde la modestia de su posición.

Las ideas subyacentes

Para entender el impacto sobre el medio ambiente pueden tener el uso de la inteligencia artificial repasemos antes algunos conceptos básicos:

El paradigma de algoritmo de inteligencia artificial se encuentra en las llamadas redes neuronales artificiales, existen muchos otros métodos pero para ejemplificar la explosión actual de las AI nos referiremos principalmente a ellas.  Las redes neuronales artificiales son un tipo de algoritmo del tipo denominado aprendizaje supervisado que emula en cierta medida el funcionamiento de la neurona natural. El perceptrón, que es la unidad básica de estas redes, fue desarrollada teóricamente en el año 1943 por Walter Pitts y Warren McCulloch. La primera red neuronal artificial fue implementada algo después, en 1957 Frank Rosenblatt empezó a trabajar en una máquina capaz de emular físicamente la idea teórica subyacente en la ideal del perceptrón. Estamos hablando de una implementación por hardware {Figura 1} no por software, para una codificación de los algoritmos en una máquina de propósito general hubo que esperar a la década de los 60  usando para su ejecución un IBM 704. Estas redes se podrían usar para aprender ciertas tareas, entre las más simples clasificar entradas, como por ejemplo, dada una foto donde aparecía una persona,  decidir si esta era una mujer o un hombre. 


Mark 1
Figura 1: Mark 1


Tras la construcción y ejecución del perceptrón se comprobó por un lado la considerable potencia de estos métodos y por otro, el enorme costo en hardware y tiempo de cómputo para ejecutar estas redes.  Desde la invención del perceptrón hasta la actualidad, se han sucedido diversos "inviernos de la AI" consistentes en periodos  de escasos avances prácticos en esta disciplina. Las redes neuronales artificiales usan básicamente calculo matricial lo que implica un coste computacional considerable y las máquinas de la época no estaban preparadas para realizar de forma eficiente estos cálculos. Por tanto, aunque ya en los años 80 del siglo pasado se hablara de deep learning - redes neuronales multicapa - su construcción  experimental no estaba al alcance del hardware de la época. El invierno se ceñía sobre el campo de la AI, las ejecuciones prácticas eran inviables lo que generó  un desincentivo que afecto a los desarrollos teóricos.   


Figura 2. Los inviernos de la AI {1}.


Los avances en hardware de principios de los años 2000 abrieron la puerta al uso en aplicaciones reales, pero aún faltaba un pequeño pero importante empujón. Este empujón vino del mundo de los videojuegos, generar movimiento en los gráficos conlleva un buen número de operaciones de algebra matricial, por lo que se pensó en desarrollar hardware altamente especializado que realizará de forma eficiente estos cálculos. A partir de ese momento y gracias al uso de las tarjetas gráficas usadas en consolas y PCs para jugar, se logró superar las dificultades que presentaban los tiempos de entrenamiento y uso de este tipo de algoritmos.  En cierta medida los jugadores pusimos nuestro grano de arena en el deshielo del invierno de la AI. 

Pese a las considerables ventajas de su uso, estos dispositivos tienen sus inconvenientes,  por un lado un consumo nada desdeñable, por otro su nivel de complejidad y por último la necesidad de emplear materiales escasos para su construcción. 

Figura 3. Consumos de algunas GPUs, para el caso que nos ocupa, el entrenamiento de una red,  podemos considerar  el valor de TGP , total graphics power 

 

Usar una red neuronal artificial  para distinguir, por ejemplo, entre perros y gatos,  conlleva dos tareas:

- Entrenamiento: Básicamente consiste en ofrecerle al algoritmo un conjunto de imágenes etiquetadas  - perros vs gatos - para que mediante métodos de control del error configure unos pesos, esto es, una gran matriz que sirva precisamente para clasificar las entradas - imágenes - en dos conjuntos. 

- Predicción: Una vez entrenada la red se le pasa la imagen y la matriz de pesos da como salida una predicción sobre la clase a la pertenece - perro o gato - dicha imagen. 

El entrenamiento conlleva un considerable esfuerzo de cómputo y para poder hacerlo en un tiempo razonable, lo más conveniente es llevar este proceso a las GPUs. El proceso de predicción es más liviano, pero las necesidades de acelerar la predicción en entornos reales - la detección de objetos en la conducción autónoma, por ejemplo - obligan a usar el hardware de forma intensiva, por lo que el uso de la GPU también esta generalizado. Sea como fuere, el uso de deep learning  conlleva unos consumos energéticos y de materias primas considerables ya que se debe usar de forma intensiva las GPUs durante los dos procesos antes citados  -  {2, 3} - . Por ejemplo:

  • El entrenamiento de GPT-3 expulso a la atmósfera unas 552 toneladas de CO2.
  • Alpha Zero de Google libero unas 100 toneladas de CO2 a la atmósfera durante su fase de aprendizaje. 
  • Entrenar una red neuronal de gran tamaño, 200 millones de parámetros, produce aproximadamente unas 240 toneladas de CO2.
La ejecución de la predicción tiene un coste mucho menor, pero su uso generalizado es una parte fundamental del problema. Por otro lado los requisitos de hardware no van a reducirse y el empleo de estas técnicas no para de extenderse. Es evidente que el uso del deep learning participa  de forma considerable en el  cambio climático  de origen atropogénico. Sin embargo, de poco sirve ser un ludita en estos asuntos, las ventajas que ofrece esta tecnología son enormes, incluidas una inestimable ayuda precisamente en la búsqueda de soluciones a nuestros problemas climáticos. Lo más sensato es, sin renunciar al uso de la tecnología, meditar sobre su empleo y reflexionar en que medida podemos reducir o mitigar el impacto negativo. Precisamente aquí planteo algunas de estas reflexiones:

¿Deep learning para todo? 

Disponer de un martillo puede ser imprescindible en algunos ámbitos pero si pretendemos resolver todos lo problemas a martillazos nos vamos a encontrar en serias dificultades.  ¿De verdad es necesario extender  tanto el uso del deep learning?, ¿no existen otras técnicas alternativas?. Por ejemplo, desde Aerín hemos investigado algoritmos alternativos, menos costosos computacionalmente, para detectar la presencia de mascarillas. Mientras que durante la pandemia se multiplicaban las publicaciones científicas que resolvían este problema  usando redes convolucionales  {4} , desde el departamento de I+D de Aerin buscábamos soluciones por vías alternativas, usando entre otras cosas análisis del histograma con resultados mejores que los modelos CNN. 

Pero podemos llegar más lejos, que una inteligencia artificial pueda hacer un trabajo no significa que automáticamente tenga que emplearse para tal fin. No hay nada malo en analizar si hay una alternativa más  sencilla o si un operador humano  asistido por una AI puede ser más eficiente que emplear pesados modelos de deep learning. La tecnología es una gran herramienta pero no es ni la única ni la mejor en todos los ámbitos

Una clave, la investigación básica

Muchos son los matemáticos y los físicos que deciden seguir la senda de la empresa privada, dedicando su vida laboral al desarrollo y la aplicación práctica de técnicas de inteligencia artificial. Esta decisión conlleva en muchos casos  el sacrificio de la otra vía, la de la investigación básica. Es conocido que la vocación eminentemente teórica en matemáticas esta descendiendo en favor de un carrera profesional más elocuente desde el punto de vista de lo material. Sin embargo,  el trabajo teórico es absolutamente fundamental, no solo para la AI, sino para todas las ciencias en general. Por tanto dignificar el trabajo de la investigación en  ciencia básica, aumentar las cuantías de las becas  y asegurar un futuro estable y bien remunerado es fundamental en todos los sentidos. Un ejemplo, recientemente se ha logrado por parte del Instituto de Telecomunicaciones y Aplicaciones Multimedia en la Universitat Politècnica de València  {5}, al encontrar una mejora en el método de calculo de funciones de matrices basado en la técnica de Paterson-Stockmeyer. Este hallazgo teórico puede tener un impacto importante en cualquier algoritmo que trabaje con matrices, incluida la gran mayoría de las técnicas de deep learning reduciendo las necesidades de cómputo

En otro caso, optimizar


En caso de que tengamos que usar algoritmos complejo, con la necesidad de entrenar mediante largos conjuntos de datos etiquetados, debería ser obligado realizar una correcta planificación con la finalidad de reducir en la medida de lo posible el impacto. Esto se puede realizar de varias formas, usando métodos de "transferencia de conocimiento", eligiendo con cuidado la arquitectura o construyendo un buen dataset. También es posible ajustar la potencia requerida de las GPUs sin que esto suponga un gran impacto en los tiempos de entrenamiento, ni en los resultados. Mi próxima entrada realiza un análisis de estas técnicas de reducción de potencia. 

Finalmente podemos trabajar en mejorar el impacto de nuestros algoritmos y considerar en que medida podemos reducir el impacto en las emisiones de gases contaminantes.


{1}. Schuchmann, Sebastian. (2019). Analyzing the Prospect of an Approaching AI Winter. 10.13140/RG.2.2.10932.91524. 
{2}.  Lacoste, A., Luccioni, A., Schmidt, V., & Dandres, T. (2019). Quantifying the carbon emissions of machine learning. arXiv preprint arXiv:1910.09700. 
{3}.  Schwartz, R., Dodge, J., Smith, N. A., & Etzioni, O. (2020). Green ai. Communications of the ACM, 63(12), 54-63. 
{4}.  JIGNESH CHOWDARY, G., et al. Face mask detection using transfer learning of inceptionv3. En Big Data Analytics: 8th International Conference, BDA 2020, Sonepat, India, December 15–18, 2020, Proceedings 8. Springer International Publishing, 2020. p. 81-90. 
{5}.  Sastre, J., & Ibáñez, J. (2021). Efficient evaluation of matrix polynomials beyond the Paterson–Stockmeyer method. Mathematics, 9(14), 1600. 


miércoles, 9 de mayo de 2018

TensorFlow, machine learning I: Perceptrón multicapa

Esta entrada presupone, por parte del lector, ciertos conocimientos de redes neuronales artificiales. No obstante ofrezco una descripción teórica muy rápida.

Las redes neuronales artificiales se basan en el funcionamiento de las redes formadas por células de los sistemas nerviosos cuya principal capacidad es la de excitarse eléctricamente según una serie de estímulos.



Los estímulos son recibidos a través de las dentritas  y en función de estas entradas la neurona puede activarse y mandar estímulos a través de los axones terminales a otras neuronas o no activarse. Poniendo un ejemplo muy sencillo; supongamos que tenemos una red neuronal encargada de mandar la señal a los músculos para encestar una bola de papel en una papelera; las entradas a las neuronas podría ser al ángulo de lanzamiento y la fuerza, las redes se activan o no según una función de activación determinada que tiene como entrada el valor de las entradas multiplicadas por unos pesos -inicialmente aleatorios-. Este proceso de activación pasará por diferentes capas neuronales, cada una con su función de activación y sus pesos. Finalmente la capa de salida da un valor que se interpreta para colocar el brazo y lanzar. A continuación se observa el resultado y se corrige los pesos usando como criterio la minimización del error -por ejemplo según mínimos cuadrados-. El proceso de lanzamiento-evaluación del error-modificación de pesos-lanzamiento continua hasta que se alcanza el error deseado, a continuación se fijan esos pesos "ganadores". A partir de ese momento lanzar y encestar -en esas mismas condiciones- no debería requerir más entrenamiento, usando siempre los mismos pesos. Evidentemente esto es una simplificación muy grande pero es justo la idea que subyace en las redes neuronales artificiales.

Una vez establecidas estas pequeñas ideas teóricas vamos a implementar una red neuronal  en TensorFlow. Básicamente esto consiste en realizar el siguiente esquema:
Por sencillez vamos a usar solo una capa oculta, un solo atributo de entrada y una sola salida. Ampliar a más capas, a más entradas o más salidas es inmediato. 

Básicamente lo que tenemos que hacer es:
  1. Establecer el número de entradas.
  2. Definir cuantas capas ocultas -hidden layers- que deseamos y cuantas neuronas por capa.
  3. Cuales será los pesos iniciales -W-.
  4. Añadir el bias.
  5. Cual será la función de activación de cada capa.
  6. Definir la capa de salida. 
  7. Cual será el criterio de error.
  8. Entrenar la red.
  9.  
A continuación el código que realiza todo este trabajo:

def neural_net(input_x, output_y, total_epoch):
    x = ts.placeholder("float", [None, 1])
    y = ts.placeholder("float", [None])
    batch_size = 10
    n_input = 1
    n_output = 1
    n_hidden_layer = 10
    w_layer1 = ts.Variable(ts.random_normal([n_input, n_hidden_layer]))
    bias = ts.Variable(ts.random_normal([n_hidden_layer]))
    hidden_layer = ts.nn.sigmoid(ts.add(ts.matmul(x, w_layer1), bias))
    w_layer2 = ts.Variable(ts.random_normal([n_hidden_layer, n_output]))
    bias_out = ts.Variable(ts.random_normal([n_output]))
    output_layer = ts.matmul(hidden_layer, w_layer2) + bias_out

    cost = ts.reduce_mean(ts.square(output_layer-y))
    optimizer = ts.train.AdamOptimizer(learning_rate=0.001).minimize(cost)

    with ts.Session() as sess:
        sess.run(ts.global_variables_initializer())
        for epoch in range(total_epoch):
            error = 0
            total_batch = int(len(input_x) / batch_size)
            for i in range(total_batch - 1):
                batch_x = input_x[i * batch_size:(i + 1) * batch_size]
                batch_y = output_y[i * batch_size:(i + 1) * batch_size]
                feed_dict = {x: batch_x, y: batch_y}
                _, c, p = sess.run([optimizer, cost, output_layer], feed_dict=feed_dict)
                error += c/total_batch
        print("Training finalizado")


x = [[x/100] for x in range(-20, 20)]
y = [y[0]*y[0] for y in x]
neural_net(x, y, 200)
Y ahora una explicación más detallada.

1. Establecer el número de entradas

Esto es establecer cuantos atributos tendremos. En un ejemplo muy sencillo, para hacer regresión de una función desconocida $f(x)$, solo tendremos una entrada.
Otro aspecto importante es crear un placeholter para las entradas y las salidas.  Los placeholter son variables vacías que serán alimentadas más adelante. Si no se alimentan, cuando ejecutemos el algoritmo nos dará un error. Hay que tener en cuenta que si empleáramos Variables en lugar de placeholder los valores podrían ser sobrescritos, de esta forma aseguramos que los valores de entrada y salida para entrenamiento permanecen constantes a lo largo del entrenamiento. Es cierto que también podrían usarse constantes en vez de estas estructuras, sin embargo TensorFlow penaliza este uso limitando el tamaño de las constantes -2 Gb- .Por otro lado los placeholder pueden aumentar dinámicamente el tamaño de la memoria, lo que permite más flexibilidad a la hora de nutrir un modelo con diferentes conjuntos de entrenamiento.

x = ts.placeholder("float", [None, 1])
y = ts.placeholder("float", [None])
En este caso  las entradas se han representado como una matriz de una columna, mientras que la salida está representada por un array.
 

2. Definir cuantas capas ocultas que deseamos y las neuronas por capa

Por lo general no es necesario emplear más de dos capas ocultas, evidentemente hay una razón para ello. Por una lado hay que tener en cuenta que al añadir capas ocultas incrementamos el número de pesos, si la capa anterior tiene m neuronas -o si es la capa de entrada, m entradas- y la nueva capa oculta aporta n neuronas, tendremos en total mxn nuevos pesos. El exceso de pesos puede generar un problema de sobre aprendizaje siendo capaz de aprender "de memoria"  acomodando los pesos para cumplir con unas salidas dentro del error solicitado. El problema es que ante cualquier modificación de las condiciones no es capaz de ofrecer respuestas satisfactorias. Por otro lado el aumento de neuronas implica tiempos de cálculo crecientes. Lo más adecuado es empezar con una sola capa, ir aumentando las neuronas de esa capa esperando que el error se ajuste a lo solicitado. Si los resultados no mejoran entonces habría que pensar en el aumento de capas ocultas. Esto lo definiremos como una contante:

n_hidden_layer = 10

3. Cuales será los pesos iniciales, W. 

Como puede verse cada entrada, o cada neurona, aporta a la activación de todas las que tiene por delante según un peso. Inicialmente estos pesos son aleatorios. 

w_layer = ts.Variable(ts.random_normal([n_input,n_hidden_layer])) 

Esto nos da una matriz de pesos que une cada entrada -una en este caso- con cada una de las neuronas de la primera capa -10-.

4. Establecer el bias.

Cada entrada se multiplica con el peso que le corresponde para cada neurona -tal y como se muestra en el esquema-. Es decir, si tuviésemos 3 entradas $x_{0}, x_{1}, x_{2}$ la entrada a la primera neurona seria $x_{0}*w_{0,0}+x_{1}*w_{1,0}+x_{2}*w_{2,0}$, de igual manera para el resto de las neuronas. Sin embargo resulta conveniente añadir un grado de libertad más al conjunto (un bias), de tal forma que la entrada a la primera neurona de la capa oculta quede como:

$x_{0}*w_{0,0}+x_{1}*w_{1,0}+x_{2}*w_{2,0}+bias_{0}$

En nuestro caso como solo hay una entrada tendremos:

$x_{0}*w_{0,0}+bias_{0}$

El bias fue introducido en el modelo de red Adalina -ADAptative LInear Neuron- por Widrow y Ho (1960).

En nuestro caso el bias para la primera capa oculta lo calculamos como:

bias = ts.Variable(ts.random_normal([n_hidden_layer]))

5. Cual será la función de activación de cada capa.

Lo recibido por cada neurona es procesado por esta y activa la salida en función de la llamada función de activación $f(x_{0}*w_{0,0}+bias_{0})$. Existen diferentes funciones de activación:
  • Neurona todo/nada. Representada por una función escalón con un umbral -salida digital-.
  • Neurona continua tipo sigmoide.
Hay algunas otras funciones de activación pero estas son las más empleadas. En cualquier caso es necesario que sean derivables como exige el algoritmo de retropropagación del error. El módulo nn de TensorFlow nos proporciona un buen número de funciones de activación. En nuestro caso emplearemos la función sigmoide para calcular la salida de las neuronas de la capa oculta, que no es más que la suma de las entradas pasadas por la función de activación:

hidden_layer = ts.nn.sigmoid(ts.add(ts.matmul(input_x, w_layer), bias))
Esto último requiere una pequeña explicación, aunque realmente no es más que cálculo matricial simple. En cualquier caso tenemos:
  
ts.matmul(input_x, w_layer) -> Producto matricial de la matriz de 
entradas por la matriz de los pesos, si recordamos el producto 
matricial reconoceremos que el resultado es la suma de los productos
de las entradas por los pesos correspondientes, cada fila es justo 
la entrada a cada neurona de la capa oculta.  
 
ts.addts.matmul(input_x, w_layer), bias)) ->  Le sumamos a la matriz anterior los bias. 
6. Definir la capa de salida 
De igual manera debemos establecer lo que llega a la salida desde las neuronas de la última capa oculta -en este caso coincide también con la primera oculta-. Esto se hace con el mismo razonamiento que empleamos en el paso 5. 

w_layer2 =  ts.Variable(ts.random_normal([n_hidden_layer, n_output]))
bias_out = ts.Variable(ts.random_normal([n_output]))
output_layer = ts.matmul(hidden_layer, w_layer2) + bias_out

6. Cual será el criterio de error y el algoritmo de optimización

El aprendizaje de una red neuronal es de tipo supervisado, esto significa que deberemos disponer de un conjunto de datos con sus entradas y con sus salidas correctas, de tal manera que la propia red sepa en que medida su predicción es la adecuada, corrigiendo los pesos para mejorar su predicción. Para ello debemos dar a la red un criterio para establecer lo bien que esta realizando su tarea. La función de error cumple precisamente este cometido, también llamada función coste.

cost = ts.reduce_mean(ts.square(output_layer-y)

Como puede observarse esto no es más que el error cuadrático medio. 

Una vez establecido el error a estimar hay que decidir como buscar el mínimo. Cambiar los pesos sin criterio, al zar, no es un método efectivo para minimizar una función de coste. Entre los muchos métodos que se pueden elegir, uno muy efectivo es el de descenso de gradiente. De forma muy resumida, dada una función F que queremos minimizar, probablemente $F(x_{n+1})<F(x_{n})$ para:

$x_{n+1}=x_{n}-\gamma \bigtriangledown F(x_{n})$

El método de descenso de gradiente Adaptive Moment Estimation o Adam es una implementación más efectiva del descenso de gradiente: 

optimizer = ts.train.AdamOptimizer(learning_rate=0.001).minimize(cost)

7. Entrenar la red

Una vez configurada la red debemos empezar el entrenamiento. Básicamente esa tarea se realiza en el siguiente código:

with ts.Session() as sess:
        sess.run(ts.global_variables_initializer())
        for epoch in range(total_epoch):
            error = 0
            total_batch = int(len(input_x) / batch_size)
            for i in range(total_batch - 1):
                batch_x = input_x[i * batch_size:(i + 1) * batch_size]
                batch_y = output_y[i * batch_size:(i + 1) * batch_size]
                feed_dict = {x: batch_x, y: batch_y}
                _, c, p = sess.run([optimizer, cost, output_layer], feed_dict=feed_dict)
                error += c/total_batch
        print("Training finalizado")

Como puede verse es imprescindible crear una sesión y e inicializar las variables. A continuación corremos el entrenamiento un numero suficiente de veces epoch, que buscando un símil cotidiano equivaldría al número de clases de conducir que necesitamos para entrenar a nuestras neuronas para que sepan conducir un vehículo. En la línea 5 separamos el conjunto de entrenamiento en lotes, en la línea 9 creamos un diccionario para alimentar los placeholder y en la siguiente entremos la red, los valores _, c, p corresponde al optimizador, al coste y a la salida que proporciona la red, es decir a la predicción.

Logicamente habría que controlar el error y salir del bucle si se alcanza  antes de finalizar todos los ciclos de entrenamiento. Tampoco es suficiente con entrenar la red, a continuación habría que validar con un conjunto diferente de datos y en última instancia pasarle un último test con un tercer conjunto. Estos detalles los dejo para las siguientes entradas. En cualquier caso los resultados son los siguientes para los siguientes datos:
x = [[x/100] for x in range(-300, 300)]
y = [1+math.sin(3*y[0]) for y in x]
En azul la predicción de la red. Evidentemente la función no es extraordinariamente complicada, no obstante es útil para verificar que esta bien configurada. Una recomendación es siempre pasar a nuestra red configurada un patrón bien conocido -una función matemática- con pocos ejemplos pero suficiente para comprobar que la red esta bien configurada; por ejemplo, un valor excesivo en el factor $\gamma=0.01$ genera resultados menos satisfactorios.

Incluso con idénticos valores de entrenamiento una mala configuración de la red -en este caso simplemente hemos elegido mal el tamaño de los lotes de entrenamiento-.

Una vez comprobada la bondad de la red para un problema de regresión genérico, sabiendo que no hay fallos de construcción, podemos atacar el  problema de regresión real -evidentemente será necesario ajustar ciertos parámetros, aumentar las neuronas,..- pero sabremos que nuestra red esta bien construida.
  

miércoles, 9 de abril de 2014

La funcion Gaussiana en visión artificial II


Como decíamos en la anterior entrada dedicada a la gaussiana, su empleo  puede servir de ayuda para encontrar características en una imagen sin tener que preocuparnos por la escala. Para ver como funciona vamos a recordar un nuevo operador ampliamente conocido en el mundo de la física, se trata del operador laplanciano:


$\Delta f =\nabla^2f$

O en dos dimensiones y en coordenadas cartesianas:

$\Delta f =\nabla^2f = \frac{\partial^2f}{\partial x^2}+\frac{\partial^2f}{\partial y^2}$ 

Cuando es aplicado sobre imágenes, la función f es $I(x,y)$ y designa la intensidad del pixel de coordenadas x, y. En OpenCV podemos fácilmente calcular el resultado del operador laplanciano si tenemos en cuenta que este puede calcularse como una convolución con un kernel determinado. El siguiente ejemplo muestra lo que hace el operador laplanciano, en este caso con un kernel de 5x5:


Como puede verse la segunda derivada ofrece una gran sensibilidad al ruido. Si lo que se desea es calcular los bordes de los objetos el uso del operador laplanciano  pude ser de utilidad, pero la excesiva sensibilidad al ruido lo hace de difícil uso. No obstante podemos emplear, antes del operador laplanciano, un filtrado gaussiano. Esta nueva convolución es conocida como LoG. A grandes rasgos el filtrado LoG tendrá el siguiente comportamiento al aplicarlo a una imagen:

- Cero a lo largo de los contornos.
- Positivo justo a un lado del contorno.
- Negativo al otro lado del contorno.
- Cero en el interior del contorno.

Cuando se eligen valores de sigma pequeños el filtro LoG es capaz de captar los bordes que se encuentran a menos escala, mientras que con valores grandes se capturan los de mayor tamaño. El siguiente ejemplo muestra un LoG con un sigma de 3.


La parte correspondiente a la cabeza y al borde de las alas se distinguen con facilidad, sin embargo otras zonas mas sutiles son menos nítidas - las antenas, por ejemplo -. Si reducimos el valor de sigma, digamos a 1, tenemos el siguiente resultado:



Ahora logramos que otras características se hagan visibles. Aplicando este método, usando con cuidados los valores del tamaño del kernel y el de sigma, podemos descubrir muchas de las características notables de una imagen. Ahora bien, el LoG es costoso en tiempo de computación, aunque existe una solución si empleamos un camino opcional calculando las diferencias de convoluciones gaussianas con dos diferentes sigmas, por ejemplo $\sigma$ y $k\sigma$. Esto es una aproximación al cálculo de LoG más rápida. Esto se hace para varios valores de sigma, en forma piramidal y disminuyendo la escala - o aumentándola si partimos de un valor de sigma pequeño -. Una vez realizadas las diferencias se buscan los máximos comparándolos con 8 los píxeles vecinos, así como los 9 píxeles de los niveles de escala posteriores y anteriores. De esta forma se consiguen los extremos locales, que potencialmente pueden ser keypoints. Una vez obtenidos estos máximos locales se puede refinar aún más nuestro conjunto de keypoints desechando los que estén por debajo de un cierto umbral. Esta descripción corresponde al método SIFT, descrito en 2004, D.Lowe, University of British Columbia, Came up with a new algorithm, Scale Invariant Feature Transform. El algoritmo esta disponible en OpenCV por lo que no necesitamos implementarlo nosotros mismos. Ahora describimos en pocas líneas como usar SIFT en openCV desde Python:
 
sift = cv2.SIFT()
keypoints, descriptor = self.sift.detectAndCompute(image,None) 

Para representar los keypoints sobre la imagen podemos recurrir a  drawKeypoints, que si le añadimos DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS como flag, nos dibujará los keypoints  con su orientación y un radio proporcional a la "fuerza" del mismo. El resultado es el siguiente:





En la siguiente entrada veremos como podemos recurrir a un algoritmo aún más eficiente que el SIFT.

viernes, 14 de marzo de 2014

Evaluación de algoritmos en Python



En algunas ocasiones preocuparse por la eficiencia de un algoritmo es la diferencia entre encontrar una solución y no encontrarla. Disponer de un algoritmo que nos ofrece una solución en un tiempo imposible de asumir, es no haber encontrado la solución en absoluto. En algunos casos, cuando el tiempo no es determinante, podemos ser menos sutiles y usar la "fuerza bruta", siempre y cuando el tiempo que necesita nuestro programa para ejecutarse sea razonable. Son soluciones que, aunque poco elegantes, nos permiten seguir avanzando. No obstante evaluar nuestros algoritmos es una buena practica que permite mejorar los mismos, encontrando soluciones mas óptimas y mejorando el rendimiento. En Python tenemos algunas herramientas muy útiles, describiremos algunas y como se pueden usar:


  • Para evaluar tiempos tenemos timing, su uso resulta muy sencillo:



Una forma de uso muy útil de timing es desde la línea de comandos, un ejemplo para evaluar una función que se encuentra en un módulo (mymodule) podría realizarse como $python -m timeit -s "import mymodule as m" "m.function()"

  • Para comparar funciones o encontrar cuellos de botella, cProfile. 
Vamos a intentar comparar tres formas de calcular un factorial, para ello partimos del siguiente código:

import cProfile
def main ():
    
    def factorial1(n):
        if n == 0:
            return 1
        return factorial1(n-1)*n
    def factorial2(n):
        fac = 1
        for x in xrange(1,n+1):
            fac = fac * x
        return fac
    def factorial3(n):
        fac = 1
        for x in range(1,n+1):
            fac = fac * x
        return fac
    
    factorial1(990)
    factorial2(990)
    factorial3(990)
    
if __name__=="__main__":        
        main()

cProfile.run('main()')

El resultado que ofrece mi máquina es el siguiente:



Como puede verse el cuello de botella se encuentra en la función recursiva (factorial1). Para poder evaluar con más precisión cual de las funciones es más efectiva, debemos aumentar el límite de profundidad de recursividad, ya que factorial1 estará limitado a 950. Para aumentar tal restricción añadimos lo siguiente:

import sys
sys.setrecursionlimit(10000)

Ahora podemos calcular el factorial de un número mucho más grande, digamos 5000. El resultado es:
  


Se confirma el cuello de botella en la función recursiva resultando ganadora aquella que emplea range en lugar de xrange. Ya que estamos, aprovechemos para comprobar que es más rápido en una lista; append vs insert. 

def main2():
    def append():
        list1 = []
        for x in range(1,1000):
            list1.append(x)
            
    def insert():
        list1 = []
        for x in range(1,1000):
            list1.insert(0,x)    
    
    append()
    insert()

    
if __name__=="__main2__":        
        main2()

cProfile.run('main2()')

Los resultados del combate:



Como puede verse el método append resulta ser más efectivo que insert. 

Estas herramientas, y algunas otras, son muy efectivas a la hora de valorar los distintos algoritmos. Si se quiere ser preciso estos experimentos deberían realizarse muchas veces y con distintos tamaños o repeticiones. Por ejemplo, en el experimento anterior, insert es igual de rápido que append para pocas inserciones, sin embargo cuando estas ganan en tamaño es cuando las diferencias se hacen más notables. Visualizar los resultados mediante gráficas para poder valorar mejor los resultados también es muy importante. Python ofrece herramientas eficientes para automatizar y ofrecer estos resultados o elaborar informes, no obstante este propósito excede de la finalidad de esta entrada, pero basta decir que los módulos csv y matplotlib aportan las herramientas necesarias para tal labor .