Modelos Humanos vs AI

Usualmente el conocimiento se ha considerado como encontrar el orden en el caos. Las personas hemos buscado reducir el comportamiento físico de las cosas a modelos matemáticos que nos permitan interactuar de manera precisa con nuestro entorno.

Mientras mas simple y exacto sea el modelo matemático, le consideramos más elegante.

Consideramos que existe conocimiento cuando se tiene un tren de ideas lógico, que nos conducen a un resultado coherente. De esta forma puede explicarse el origen de las consecuencias, como el porque de un movimiento en un juego de ajedrez.

Sin embargo con el avance en el aprendizaje computacional, el hombre se ha visto superado en sus capacidades de comprensión, debido a que las computadoras no están limitadas a trabajar con modelos simples como nosotros.

Dada una fuente de información amplia, estas técnicas de aprendizaje permiten a los ordenadores generar sus propios modelos numéricos internos. Estos modelos, después de entrenados, han probado producir resultados eficientes y exactos, sin embargo, incomprensibles para los hombres, ya que son resultado de infinidad de variables y enlaces en múltiples capas de abstracción.

Por ejemplo, puede entrenarse a una computadora a reconocer un dígito escrito manualmente, mediante la exposición de un conjunto de ejemplos. Supongamos el numero 8. A diferencia de nosotros, que reconocemos este dígito por reglas estructurales donde dos circunferencias se unen parcialmente en un orden vertical, la computadora analiza posiciones en los pixeles de la imagen, y genera su propio conjunto de reglas, incomprensibles a nuestros ojos, para determinar si la imagen representa un 8 o no.

Anteriormente este tipo de conocimiento numérico se consideraba incompleto, ya que carece de una representación matemática elegante. Sin embargo, ante la evidencia de la funcionalidad de estos métodos, no queda mas que reconocer la limitante en la capacidad de la mente humana, para representar fenómenos complejos.

Ante la insaciable sed de conocimiento, podemos solo aceptar esta nuestra frontera intelectual, y dar paso a nuevo conocimiento generado no por hombres.

Pensamiento corto despues de leer este buen articulo:

Our Machines Now Have Knowledge We’ll Never Understand

David Weinberger

Modelos Humanos vs AI

Espectro Radioeléctrico, una perspectiva de la escasez actual

El Espectro Electromagnético es como se conoce al conjunto de todas las frecuencias conocidas por las cuales se propagan ondas electromagnéticas. Desde algunos cuantos hertz hasta las encontradas en procesos nucleares.

Aunque existe un conjunto enorme de estas frecuencias, solo algunas porciones de este espectro tienen comportamientos de propagación benéficas para el uso de comunicaciones inalámbricas, este subconjunto se conoce como Espectro Radioeléctrico.

Una propiedad conocida de la propagación a lo largo del espectro es que mientras menor sea la frecuencia central utiliza la onda transmitida se tiene una mayor capacidad de atravesar objetos, pero menor ancho de banda esta disponible. En el caso contrario, frecuencias altas son más absorbidas por los objetos pero existe la posibilidad de usar mas ancho de banda. Esto determina que servicios son asignados a las porciones de espectro que sean útiles para los mismos.

Las transmisiones de radio se encuentran en la porción del espectro radioeléctrico con menores frecuencias, cubren una área amplia. Y conexiones que requieren mayor transferencia como Wi-Fi o la red celular 4G se encuentran en las porciones mas altas, cubriendo áreas de cobertura de algunos metros.

El espectro radioeléctrico es administrado por los gobiernos de cada país. Estos junto con la Unión Internacional de Telecomunicaciones asignan bandas especificas para ciertos servicios de manera global o regional.

Esta administración del espectro es fija, y regulada mediante licencias de largo plazo. Aunque existen porciones del espectro que son utilizadas sin licencia (Wi-Fi), la gran mayoría se encuentra licenciado y es utilizado por un gran rango de tecnologías que operan con suficiente potencia para permitir que los servicios tengan coberturas de áreas relativamente amplias.

Los sistemas de comunicaciones celulares tienen una porción del espectro determinada, la cual es distribuida mediante un proceso subasta entre los operadores de estos servicios. Sin embargo, esta porción del espectro ha sido ampliamente explotada, y por lo cual es muy difícil para los operadores conseguir más.

Estos sistemas comenzaron con comunicaciones analógicas hace 40 años, y ofrecían servicios de voz unicamente. Con la evolución y digitalización de estos servicios, cada vez los sistemas obtuvieron mayores capacidades de transmisión. Hasta el punto en la actualidad donde existe una densidad de subscriptores del 96% con respecto a la población mundial.

Hoy en día las comunicaciones celulares son oblicuas y una parte fundamental nuestro día a día. Esta gran absorción del servicio ha incrementado la demanda a los sistemas, y con ello a los operadores. Además la tendencia de uso de internet de banda ancha con los sistemas celulares ha incrementado a un paso acelerado, de forma que se estima que para el 2020 existirá una congestión en los sistemas actuales.

La solución directa para el problema de la gran demanda del servicio es hacer uso de una porción mas grande de espectro, ya que con ello los operadores tienen más canales, y/o mayor ancho de banda. De esta forma los sistemas podrían atender a más usuarios y/o mayores velocidades de transmisión.

Sin embargo, dadá la asignación de espectro fija actual, esta solución no puede ser alcanzada, ya que no hay mas espectro designado para estas comunicaciones disponible para los operadores, ademas toma un tiempo bastante considerable el que parte del mismo se vuelva disponible. Por este motivo los operadores deben adoptar también nuevas tecnologías que ayudan al problema en un termino corto.

Existen múltiples enfoques que buscan atacar el problema de la escasez de espectro desde otro angulo distinto a conseguir mas del mismo. Los principales son listados a continuación:

  • Hacer un uso mas eficiente del espectro.
    • Asignación dinámica de recursos.
    • Densificación de las redes (HetNets)
  • Hacer un uso compartido del espectro, mediante radio cognitiva.

Durante las generaciones de tecnologías de transmisión celular 2G, 3G y 4G los sistemas utilizan métodos cada vez más eficientes de codificar la señal en ondas de radio para crear conexiones de datos más rápidas. Estas tecnologías que incrementan la eficiencia del uso del espectro, por lo que permiten transmitir más datos utilizando una cantidad fija de espectro.

De esta misma han surgido nuevas estrategias del uso del espectro que han empezado a ser utilizadas en los sistemas de 4ta Generación y que serán parte clave para los sistemas de la siguiente generación 5G.

La asignación dinámica de recursos, se conoce al proceso de asignar inteligentemente, los recursos disponibles de las estaciones base a los usuarios considerando las condiciones físicas en cada instante. Los recursos que son distribuidos son los canales, la potencia de los mismos, y el tiempo que son asignados a cada usuario.

Por otro lado la densificación de las redes, hace un uso conjunto de redes de menor tamaño en las celdas macro desplegadas tradicionalmente. Estas redes tienen áreas de cobertura mucho menores, por lo que atienden a usuarios a distancias mas cortas, con menor potencia y usualmente mayor velocidad de transmisión. Lo mejor de estos sistemas es que estas celdas reutilizan el mismo conjunto de frecuencias, por lo que se consigue un uso eficiente del espectro a costa de una no despreciable complexidad de las redes para evitar interferencia.

Espectro compartido es una alternativa al problema de las escasez de espectro. En esta propuesta dispositivos con capacidades cognitivas detectan oportunidades espectrales para transmitir sobre las mismas en bandas pertenecientes a otros sistemas licenciados, siempre y cuando no afecten la comunicación de estos sistemas. Esto es posible dado que mediciones recientes han demostrado que una gran parte del espectro licenciado es sub-utilizado la mayor parte del tiempo.

Si bien estas alternativas proponen una solución al problema de escasez agregan complejidad a las redes. Por lo que hay un gran esfuerzo en desarrollar algoritmos eficientes que puedan lidear con la complejidad agregada.

Espectro Radioeléctrico, una perspectiva de la escasez actual

Apuntando a una función en Matlab (Punteros)

Matlab Tips and Tricks.

Esta es una sección donde se explicaran algunos conceptos sobre programación que me han sido útiles para aplicar algoritmos en Matlab. Muchos de estos pequeños tutoriales pueden ser aplicados a diversos lenguajes de programación, donde cada uno maneja un concepto es similar, sin embargo otros serán exclusivos de la forma en la que trabaja Matlab, sobre todo aquellos orientados a la indexación y manejo de matrices.

La intensión de esta información no es proporcionar un estudio o definición formal de estos conceptos, y puede que los nombres aquí asignados varíen con los oficiales en la documentación. En todo tiempo trataré de proporcionar un link directo a documentación oficial que los respalde.

Apuntando a una función (Punteros).

Para quienes tienen conocimiento de lenguaje C, o similares, la palabra puntero no es nueva en su vocabulario. Los punteros son referencias a espacios en memoria, que pueden ser variables o funciones, o cualquier espacio de memoria donde la interpretación de contenido tiene que hacerse explícitamente. Para este tipo de lenguajes el uso de punteros es algo común, usualmente se utiliza para pasar variables a las funciones en forma de referencia, veremos un poco más a detalle sobre qué significa esto en un momento.

In computer science, a pointer is a programming language object, whose value refers to (or “points to”) another value stored elsewhere in the computer memory using its memory address.
Wikipedia: Pointer (computer programming)

En Matlab no existe tal concepto de punteros para pasar variables por referencia, al menos no de la forma clásica. Existe una forma de realizar esto mediante una transformación de tipo de variable C-like que puede encontrarse en este link, o también en la definición de objetos que heredan el comportamiento de Handle, un tema que trataremos en otra ocasión.

Sin embargo existe una forma útil de hacer referencia a un espacio de memoria, que permite pasar funciones como referencia a otras funciones. Para tener en claro el concepto haremos uso de un ejemplo práctico. Suponemos que tenemos que realizar una función grafique cualquier función trigonométrica en un rango de 0 a 2Pi. Llamaremos a esta función graficaTrig y tomara un solo argumento func el cual indica la función trigonométrica que quiere ser graficada.

Podríamos resolver este requerimiento de múltiples formas, en este caso vamos a analizar dos de ellas. Si definimos que el argumento será una cadena (String) con el nombre de la función (Coseno, Seno, etc), entonces la función tendrá que comparar entre un conjunto de fórmulas conocidas.

function graficaTrig(func)
 x = [0:0.01:2*pi]
 if func == 'Coseno'
  plot(x,cos(x))
 end
 if func == 'Seno'
  plot(x,sin(x))
 end
 … %others
end 

Para este caso tenemos que tener conocimiento de todas las posibles Funciones Trigonométricas de antemano, y comparar la cadena con el nombre de cada una, y aplicar la función de Matlab que corresponde a tal función.

La segunda opción que analizaremos, y el propósito de este escrito, es hacer uso de un manejador (handle) de la función trigonométrica, para pasarlo como argumento de la función y evaluarlo directamente. Para esto haremos uso del operador @, que además de otorgarnos un puntero una función puede ser utilizado para definir funciones anónimas (tema que quizá veremos en el futuro). El siguiente código ejemplifica el su forma de uso:

cos(0)
newCos = @cos
newCos(0)

Como se puede observar la función cos devuelve el valor del coseno del número que pasamos como argumento, podemos apuntar a esta función utilizando @ y almacenando dicho puntero a una nueva variable, la cual funcionara como si fuera la misma función. Haciendo uso de este método podemos resolver nuestro problema ejemplo de forma sencilla.

function graficaTrig(func)
 x = [0:0.01:2*pi]
 plot(x,func(x))
end

Donde para obtener la gráfica de la función coseno utilizamos: graficaTrig(@cos). En este caso la función cos es pasada como argumento, tomando un nuevo nombre de variable (func). Por lo que para hacer uso de dicha función solo se manda a llamar de la forma func(x).

En Matlab para ejecutar una función no es necesario hacer uso de los paréntesis (a diferencia de la mayoría de lenguajes) por lo que rand y rand() producen el mismo resultado. Sin embargo en lenguajes como Javascript o Python, hacer uso del nombre de la función sin paréntesis devuelve el handle (dirección de memoria) de dicha función.

En el área de algoritmos metaheurísticos es común que estos algoritmos sean probados en un conjunto de funciones llamadas funciones de prueba (benchmark). Estas funciones contienen ecuaciones matemáticas multidimensionales sobre las cuales se pretende buscar los valores máximos o mínimos. A diferencia de nuestro ejemplo práctico sencillo, no se conocen de antemano todas las posibles funciones que podríamos requerir o utilizar, ya que nuevas funciones pueden irse agregando a nuestro conjunto.

Para el autodenominado toolbox expuesto en Una Clase Para Gobernarlos A Todos, se explica que hacer uso de una clase general sobre la cual desarrollar los múltiples algoritmos metaheurísticos tiene sus ventajas. Y para ello en la clase tenemos una propiedad que contiene la función de costo (función de prueba (fitnessFunction)) que pretende optimizarse. Para ello hacemos uso de un puntero a alguna de estas funciones, y en la parte de la evaluación de la población simplemente utilizamos dicha propiedad de la siguiente forma:

fit(i) = obj.fitnessFunction(population(i,:));

De esta manera podemos hacer pruebas de distintas funciones de manera sencilla. Del repositorio en GitHub se puede observar el script de prueba que hace uso del toolbox.

clear, clc
AISearch = DE(@Rastrigin,30);
AISearch.sizePopulation = 500;
AISearch.maxNoIterations = 1000;
AISearch.start()

La explicación formal de este concepto puede encontrarse en: https://www.mathworks.com/help/matlab/matlab_prog/creating-a-function-handle.html
Si tienes algún problema haciendo uso de punteros a funciones o requieres alguna explicación adicional no dudes en comentar en la sección de abajo. Te responderemos a la brevedad.

Apuntando a una función en Matlab (Punteros)

Canales Inalámbricos: Teoría y Simulación (Parte 1)

Las comunicaciones inalámbricas se llevan a cabo mediante la transformación de señales (información) que requieren ser transmitidas de forma que puedan ser llevadas a travéz de un medio físico hasta el receptor, quien puede transformarlas de nuevo y conseguir el contenido de dicha comunicación.

Actualmente existe un gran interés por desarrollar formas novedosas de comunicación inalámbrica que permitan mejorar las prestaciones actuales que han sido logradas por estos medios, ademas de dar abasto a un constante incremento en la demanda de dispositivos con múltiples capacidades de comunicación inalámbricas.

Toda comunicación es llevada por un medio físico, y esté tipo de comunicación sin cables no es la excepción. El medio por el cual se propaga la señal es el espacio, a diferencia del sonido que se propaga con el aire, por lo que la señal viaja a la velocidad de la luz (3e8). Este tipo de señales se llaman señales electromagnéticas, y son una composición compleja que se trasmiten en forma de ondas a una cierta frecuencia de transmisión. Todas estas frecuencias están contenidas en el espectro de frecuencias radio eléctrico, el cual es un recurso finito aunque inagotable.

Conocer las propiedades físicas del medio y los efectos que esté causa a la señal propagada, es de vital importancia para hacer un mejor uso del mismo. De esta forma se puede mejorar las características de las transmisión, obteniendo mayores velocidades de datos, una menor probabilidad de error y dar servicio a mas dispositivos simultáneamente.

Los modelos matemáticos son representaciones en forma de ecuaciones que permiten abstraer el comportamiento de un proceso físico, o de cualquier naturaleza. Estos modelos, si bien limitados a ambientes controlados, permiten construir simulaciones computacionales que permiten a su vez un sistema de experimentación rápida y accesible para el desarrollo de nuevas tecnologías.

Con esto en mente presentamos esta serie de entradas pretende ser una introducción al tema, de forma que se den a conocer las características físicas que intervienen en el proceso de comunicación por un medio inalaámbrico, y simular dichos comportamientos y sistemas, para experimentación.

Modelo Físico de los Canales Inalámbricos

Un aspecto característico de los canales inalámbricos móviles es la variación de la fuerza de la señal sobre el tiempo y sobre la frecuencia. Esta variación puede es categorizada en dos tipos:

  • Desvanecimiento a gran escala. (lento)
    Debido a perdidas por el recorrido de la señal, estas pérdidas están en función de la distancia y el sombreo por objetos grandes. Este desvanecimiento cambia con forme el movimiento del receptor y es usualmente independiente de la frecuencia.
  • Desvanecimiento a pequeña escala. (rápido)
    Debido a las interferencias constructivas o destructivas de los múltiples recorridos que ocurren de la señal entre el transmisor y el receptor. Este desvanecimiento permanece en constante cambio, aun cuando el receptor se encuentre estacionario, y es usualmente dependiente de la frecuencia.

Los canales inalámbricos operan mediante la radiación de ondas electromagnéticas desde el transmisor hasta el receptor. La porción de espectro utilizado en la comunicación celular es legislada por entidades establecidas en cada estado, usualmente se utiliza las bandas cerca de 0.9Ghz, 1.9GHz, y 5.8GHz.

La longitud de onda de estas frecuencias está dentro del rango de fracción de un metro, lo que complica resolver las ecuaciones de campo electromagnético (Maxwell), por lo que modelos más sencillos que capturen características esenciales de su comportamiento son importantes. Por ejemplo algunos aspectos importantes para planeación de celdas y de los sistemas de trasmisión y modulación de la señal, es conocer los efectos físicos que afectan la señal y como la afectan.

Comencemos con algunos ejemplos sobre-simplificados. Si consideramos que el transmisor y el receptor se encuentran en un espacio abierto, entonces en respuesta de una señal sinusoidal el campo eléctrico a una cierta distancia para un tiempo \( t \) es:

$$ E(f,t,u)= \frac{\alpha_s(u) cos(2 \pi f (t-r / c))}{r} $$

En donde u es el vector de posición relativa al trasmisor en donde se mide la energía del campo electromagnético, \( \alpha_s(u) \) es la ganancia de la antena que depende de la dirección, si consideramos una antena ideal omnidireccional, podemos omitir esta ganancia. La variable \( r \) representa la distancia entre el transmisor y el punto \(u\), y finalmente \(cos(2 \pi f (t-r / c)) \) representa la señal que está siendo transmitida. Es importante notar que la fase de la señal varía en proporción \( f r / c \) donde \(c\) es la velocidad de la luz, que es la velocidad a la que viaja la señal, esta propiedad será importante cuando consideremos el desvanecimiento a pequeña escala.

Para este modelo sencillo puede observarse que la energía de la señal transmitida decrece con forme la distancia, por lo que la potencia por metro cuadrado en el espacio libre decrece de forma cuadrática \(r^{-2}\).

Si consideramos este modelo de transmisión entonces podemos calcular de manera sencilla la relación señal-ruido (SNR) de un canal de comunicación inalámbrico.

$$SNR=P_{señal}/P_{ruido}$$

Esta relación entre la potencia percibida de la señal dividida entre la potencia del ruido de fondo (ruido piso), que usualmente es conocida o medible, permite que podamos calcular la capacidad máxima teórica de transmisión de datos. Para esto hacemos uso de la función de capacidad propuesta por Shannon en su trabajo de la Teoría de la Comunicación.

$$Capacidad=AnchoDeBanda \cdot log_2⁡(1+SNR)$$

Si sustituimos el modelo de canal en espacio libre en la formula entonces obtenemos la siguiente expresión matemática.

$$Capacidad=AnchoDeBanda \cdot log_2⁡(1+(P_{transmitida} r^{-2})/P_{ruido} )$$

Este modelo es muy limitado, ya que toma demasiadas consideraciones que no son posibles en de implementar en la realidad, aunque puede ser considerado para transmisiones cortas en espacios interiores. Sin embargo de esté podemos expresar de forma matemática algo que puede ser fácilmente observable mediante experimentación, que la potencia de la señal decrece con forme te alejas de la fuente. Por esta razón se le llama desvanecimiento a gran escala, ya que afecta significativamente la fuerza de la señal, y varia con forme la distancia, por lo que usualmente representa variaciones relativamente lentas en la potencia, si consideramos las altas frecuencias de trasmisión.

Simulación en Matlab

Dado este sencillo modelo de un canal inalámbrico podemos hacer uso de estas ecuaciones para generar gráficas de comportamiento. Para ello damos valores numéricos a las variables que intervienen, y dando un rango de valores a aquellas variables sobre las cuales queremos observar el comportamiento del sistema.

Una implementación de este modelo en Matlab puede ejecutarse con el siguiente codigo:

f = 0.9e6;
c = 3e8;
waveL = c/f;
T = 1/f;
r = 50:waveL;
recordAt50 = [];
for t = 0:T/100:T*3
    E = cos(2*pi*f*(t-r/c))./r.^2;
    recordAt50(end+1) = cos(2*pi*f*(t-50/c))./50.^2;
    figure(1)
    plot(r,E)
    ylim([-0.0004 0.0004])
    figure(2)
    plot(recordAt50)
    pause(0.01)
end

De este script se obtienen dos gráficas, la primera muestra la señal percibida de acuerdo a la distancia, en cada instante de tiempo. De esta gráfica se puede observar el como la señal transmitida, para cada instante de tiempo, se encuentra desfasada dependiendo de la distancia por la que viaja de forma \( f r / c \) y disminuye rápidamente. Cuando la distancia es igual a la longitud de onda \( c / f \) la señal se encuentra en fase con la señal emitida en el transmisor. El conocimiento de la fase con referencia a la emitida permite luego considerar la interferencia generada por múltiples caminos, un tema que desarrollaremos mas adelante. La segunda gráfica representa la señal recibida por un receptor a una distancia fija de 50m. Esta señal es una versión disminuida y desfasada de la original emitida en el transmisor.

Señal percibida por el receptor, donde el eje X representa la distancia recorrida de la señal, y Y la energía percibida.

wave50m

Señal recibida por el receptor a una distancia de 50m, se puede observar el desface al principio de la señal.

Teniendo conocimiento del desvanecimiento de la energia con forme a la distancia recorrida por la señal, podemos hacer el calculo del SNR y la capacidad del canal. Consideremos una potencia de 1 watt, y la capacidad en bits por símbolo transmitido, y una densidad de ruido espectral de 1e-8. Para ello podemos utilizar el siguiente codigo:

%1 watt * path loss / noise
SNR = 1 * r.^-2 / 1e-8; 
capacity = log2(1+SNR);
figure(3)
plot(r, capacity)

capacitywave

Capacidad del canal para transmitir en bits por símbolo. Sin considerar el Ancho de Banda. Eje X representa la distancia y Y la capacidad.

El ancho de banda de un canal digital determina la velocidad de symbolos por segundo que pueden ser transmitidos, ya que determina la frecuencia de la modulación de la señal. Más adelante estudiaremos que según la modulación utilizada podemos transmitir múltiples bits en cada símbolo, y cada una conlleva a una probabilidad de error por bit propia. Aunque aumentar el ancho de banda de una comunicación incrementa la velocidad, también incrementa el ruido del canal, entre otros factores, por lo que en cierto punto, incluso grandes aumentos de ancho de banda logran muy poco incremento la capacidad del canal. El siguiente código gráfica las lineas de este comportamiento a distintas distancias, considerando el modelo de canal inalámbrico expuesto antes.

bandwitdh = 1e3:5e3:1e6;
for i = 50:50:200
    SNR = 1 * (i)^-2 ./ (1e-8 * bandwitdh); %1 watt * path loss / noise
    capacity = bandwitdh .* log2(1+SNR);
    figure(4)
    plot(bandwitdh, capacity)
    hold on
end

bandwidth

Lineas de comportamiento en capacidad del canal (Mbps) con forme aumenta el ancho de banda (Hz)

Resumen:

Los canales inalámbricos propagan una señal electromagnética a través del espacio. Esta señal sufre un desface y un desvanecimiento con forme a la distancia del recorrido de la señal, desde el transmisor hasta el receptor. Conociendo el desvanecimiento de la energía, podemos hacer el calculo de la relación señal-ruido del canal, y obtener la capacidad de transmisión máxima teórica del canal, que se ve afectada por el cuadrado de la distancia. Ademas conocemos que el ancho de banda incrementa el numero de símbolos transmitidos en un segundo, pero también el ruido involucrado en el canal, por lo que aumentarlo solo es conveniente hasta cierto punto.

El modelo de canal de espacio abierto es muy simple y no considera muchos otros efectos físicos que ocurren a la señal transmitida. Otros modelos con mayores consideraciones serán presentados a la brevedad posible, en las siguientes partes de estas entradas.

Canales Inalámbricos: Teoría y Simulación (Parte 1)

Detección y descripción de características – Lo que vemos V.S. lo que entendemos

Para una amplia variedad de aplicaciones computacionales encontrar las correspondencias visuales entre un par de imágenes dado es una de las temas de investigación actuales más importantes dentro del área de visión computacional. Tareas como la representación de imágenes, el reconocimiento de patrones y objetos, la reconstrucción de escenas 3D, o la navegación visual  no serían posibles de llevar a cabo sin la presencia de características estables y representativas en la imagen.

La descomposición de una imagen digital en regiones de interés o “características locales” es una técnica ampliamente utilizada en visión artificial que permite, tanto explotar las propiedades de apariencia local, como reducir la complejidad de los problemas de visión computacional.

La tarea de encontrar correspondencias visuales entre imágenes de una misma escena se divide en dos partes importantes: En primer lugar está la detección de los puntos clave (características locales) más sobresalientes en la imagen y, en segundo lugar, la descripción de dichos puntos de interés.


1

Figura 1. Características Locales detectadas en una imagen digital


Los detectores de características ideales encuentran regiones salientes en la imagen tales que sean posibles de detectar aun cuando estos estén sujetos a cambios de punto de vista; en forma más general, estos deben ser robustos a todas las transformaciones posibles de la imagen. Una vez que se encuentra un conjunto distintivo de puntos de interés con características contrastantes, es posible construir un descriptor de características para cada uno de dichos elementos. Un descriptor de características ideal debe ser capaz de capturar la información más importante y distintiva de una región saliente, de manera que si la misma estructura es detectada posteriormente, esta pueda ser reconocida. En este contexto, ciertas características de imagen como la intensidad de color, las formas, las texturas, o bien la respuesta de ciertos tipos de filtros espaciales pueden ser utilizados para construir descriptores.

Además de cumplir con estas características, la velocidad con que se detecta y describe a cada uno de estos puntos significativos de la imagen debe también ser optimizada para ajustarse a las restricciones de tiempo demandadas por ciertas aplicaciones particulares. Por esta razón la dificultad inherente de extraer características útiles de una imagen yace en balancear dos metas comunes de competitividad: La  calidad en la descripción de las características locales y los requerimientos de costo computacional.


2

Figura 2. Correspondencias entre los puntos característicos de un par de imágenes de una misma escena.


La década pasada fue testigo de avances clave en lo que se refiere a la extracción de puntos característicos en imágenes digitales. En el 2004 David Lowe propuso el algoritmo SIFT (Scale Invariant Feature Transform), un detector y descriptor de características locales que es invariante tanto a la rotación como al escalamiento.  Dicho algoritmo emplea una versión adaptado a la escala del método de Diferencias Gaussianas (DoG) en conjunto con el descriptor de características conocido como Histograma de Gradientes Orientados (HOG).  A pesar de que el enfoque empleado por el algoritmo SIFT implica un considerable costo computacional, este es ampliamente aceptado como uno de las opciones de más alta calidad actualmente disponibles, prometiendo distintividad y robustez a una variedad de transformaciones de imagen comunes.

Recientemente, la meta en la investigación de algoritmos de detección y descripción de características locales ha consistido en buscar un desempeño similar a SIFT, mientras que a su vez se adquiera una complejidad computacional mucho menor. El algoritmo SURF (Speeded-Up Robust Features) desarrollado y publicado por Herbert Bay en el 2006 es quizá el ejemplo más importante de ello. Dicho algoritmo de detección y descripción de características locales está basado en principios similares al algoritmo SIFT, diferenciándose principalmente en la explotación de las propiedades de la imagen integral para llevar a cabo aproximaciones eficientes de las operaciones de filtrado implicadas en la detección de los puntos clave, lo cual se traduce en una velocidad de computo notoriamente superior en comparación al algoritmo SIFT.

 

CARACTERÍSTICAS LOCALES

Una característica local puede ser definida como un patrón en una imagen digital que difiere de su vecindad inmediata.  Dichas características están usualmente asociadas con algún cambio en alguna o varias de las propiedades de la imagen, como pueden ser los cambios en el nivel de intensidad, el color o la textura.

Las características locales pueden ser puntos específicos en la imagen, aunque otras características de la imagen como los bordes o pequeñas masas (blobs) pueden ser también consideradas como tal.

Típicamente, algún tipo de información es extraída de una región centrada sobre la posición de la característica local y de esta forma dicha información puede convertirse en un descriptor de dicha característica.

El principal objetivo de la detección y descripción de características locales en una imagen es proveer una abstracción general y compacta de la información contenida en dicha imagen, de manera que esta pueda ser utilizada con mayor facilidad y eficiencia en diversas aplicaciones de visión computacional.


3

Figura 3. La detección y descripción de características locales en una imagen digital permiten obtener una representación general y compacta de la información contenida en dicha imagen.


En términos generales, una característica local ideal debe de tener las siguientes propiedades:

  • Repetibilidad: Dadas dos imágenes de un mismo objeto o escena en particular, tomadas en condiciones diferentes de punto de vista, un alto porcentaje de las características detectadas en dicho objeto o escena deben poder ser encontrados en ambas imágenes.
  • Distintividad: Los patrones de intensidad asociados con la característica detectada deben de mostrar suficiente variación, de manera que dicha característica local pueda ser distinguida apropiadamente.
  • Localidad: La característica debe ser local, con el fin de eliminar la probabilidad de oclusión y para permitir la aproximación a través de modelos simples de las deformaciones geométricas y fotométricas entre dos imágenes tomadas desde puntos de vista diferentes.
  • Cantidad: El número de características locales detectadas debe ser lo suficientemente grande, tal que un número razonable de estas sean detectadas aun en objetos muy pequeños. Además, la densidad de características detectadas debe reflejar el contenido de información de una imagen y proveer una representación compacta de la misma.
  • Precisión: Las características detectadas deben estar localizadas en forma precisa, tanto en ubicación en la imagen, así como con respecto de la escala y deformación geométrica del objeto.
  • Eficiencia: Preferentemente, el tiempo de detección de características en una nueva imagen debe ser lo suficientemente razonable para aplicaciones donde el tiempo es crítico.

 

DESCRIPTORES DE CARACTERÍSTICAS

Los detectores de características locales permiten localizar y visualizar propiedades importantes en las imágenes digitales, sin embargo la simple detección de estos puntos o regiones características usualmente no provee información suficiente que pueda ser utilizada en aplicaciones de visión artificial.

Los descriptores de características  juegan un papel importante dentro de una amplia variedad de aplicaciones de visión computacional ya que estos permiten extraer información significativa correspondiente a una amplia variedad de propiedades en la imagen.

En forma general, un descriptor de características (o simplemente descriptor) se puede definir como una abstracción de las características visuales contenidas en una imagen digital. Dichos descriptores usualmente describen características elementales como son la forma, el color, la textura, el movimiento, entre otras.

Como resultado de la descripción de características, típicamente se obtiene lo que se conoce como vector de características, el cual contiene una descripción codificada de cada uno de los puntos característicos encontrados en la imagen.

Dependiendo del contenido y la cantidad de información característica que engloban, los descriptores de características  se pueden clasificar como:

  1. Descriptores Globales: Este tipo de descriptores proporcionan una descripción general de la información de color o textura, contenida en una imagen. Un ejemplo típico de este tipo de descriptores son los histogramas de intensidad, los cuales ofrecen una descripción clara de la distribución estadística en los niveles de intensidad de los píxeles de la imagen.
  2. Descriptores Locales: Como su nombre lo sugiere, los descriptores locales proporcionan una descripción informativa de ciertos elementos u objetos específicos en la imagen digital.  Este tipo de descriptores se utilizan para sustraer información descriptiva de los puntos o regiones de interés encontradas por un detector de características locales.

 

Los descriptores de características pueden ademas clasificarse de acuerdo al tipo de información empleada pasa su construcción, como por ejemplo:

  1. Descriptores de forma: Este tipo de descriptores proporcionan información referente a la geometría de los elementos u objetos en una imagen.
  2. Descriptores de color: Los descriptores de color proveen información sobre la distribución de color en los elementos y objetos que conforman la imagen.
  3. Descriptores de textura: Estos descriptores ofrecen una descripción distintiva de propiedades estructurales de la imagen, como son el contraste, la direccionalidad, o la rugosidad, entre otras.
  4. Descriptores de movimiento: Los descriptores de movimiento tienen la función de extraer la información acerca de la relación espacio-temporal de los objetos en una imagen. El movimiento se puede relacionar con el cambio de posición de los objetos en una escena, o bien con el desplazamiento del dispositivo utilizado para la captura de imágenes.

 

Un algoritmo de descripción de características abstrae la información contenida alrededor de un punto de interés dado y la representa a través de un vector de características.

Encontrar las correspondencias entre las características locales en un par de imágenes diferentes de una misma escena u objeto es la tarea más importante derivada de la descripción de dichas características locales, y es lo que hace posible la implementación de una amplia variedad de aplicaciones de visión computacional.


4

Figura 4. Aplicación de la detección y descripción de características para la detección de objetos en una imagen.


En entradas posteriores veremos con mas detalle algunas de las técnicas mas populares para detectar y describir características en una imagen. ¡Manténganse sintonizados!

Detección y descripción de características – Lo que vemos V.S. lo que entendemos

Una clase para gobernarlos a todos.

AISearch

AISearch es una implementación propia de los algoritmos de búsqueda populares en textos de investigación, con objeto de tener un toolbox fácil de implementar, así como poder cambiar la resolución del problema con distintos algoritmos de forma sencilla. Buscando tener un punto de partida para analizarlos, compararlos o diseñar nuevas estrategias, enfocándose únicamente en los operadores del algoritmo.

Los algoritmos de búsqueda metaheurísticos que utilizan una población de soluciones, buscan mejorar esta población de soluciones mediante un proceso iterativo que hace uso de la información acumulada durante todo el proceso, o bien la disponible en cada iteración. El proceso de estos puede ser abstraído en conjunto con el siguiente diagrama de flujo.

Untitled Diagram (2)

Estos algoritmos comparten múltiples procesos en común, y aunque estos algoritmos pueden ser implementados de múltiples formas, también pueden ser organizados a manera de clases, para trabajar con ellos en un paradigma de programación orientada a objetos. De esta forma pueden compartir una gran parte de las funciones que los componen, y ser mejor comprendidos y analizados únicamente en el núcleo de los operadores que los definen.

Uno no simplemente implementa todos los algoritmos

Hacer uso de la orientación a objetos, trae consigo múltiples beneficios, entre ellos un mayor reúso del código, encapsulación, y un mejor mantenimiento y optimización del código. Aunque esta entrada no busca desarrollar el tema de programación orientada a objetos, una introducción sencilla puede encontrarse en wikipedia.

Con este objetivo en mente, el primer paso entonces es describir la clase principal, que contiene todas las propiedades y métodos que pueden ser compartidos por cada uno de los diferentes algoritmos. Por ejemplo, todos ellos tienen un arreglo donde almacenan la información de la soluciones que se encuentran actualmente en la población. Así mismo un vector con la información de asociada de desempeño por cada solución. Todos ellos comienzan con una población inicial aleatoria, por lo que tener una sola función para realizar este proceso permite que puedan ser comparados equitativamente, o bien que si esta función es mejorada, o se arregla algún error dentro de ella, haciendo cambio de esta, todos los algoritmos se beneficiaran de dicho cambio.

Las propiedades consideradas para esta clase principal son:

 properties
        sizePopulation = 30;
        noDimensions = 1;
        population = [];            %size = (sizePop, NoDim)
        fitness = [];               %size = (sizePop, 1)
        bestSolution = [];
        bestFitness = inf;
        fitnessFunction;
        numberOfFunctionCalls = 0;
        maxNoIterations = 100;
        actualIteration = 0;
 end

Los métodos que estos algoritmos comparten tienen que ver con la población, su fitness, ordenamiento, entre otras utilidades que pueden ser parte o no de los algoritmos, como la visualización gráfica de la información. A continuación citaremos cada uno de ellos.

  • Población Inicial: Usualmente estos algoritmos comienzan con un conocimiento nulo del problema que están buscando resolver de forma optima. Por lo que sus primeros intentos comienzan con soluciones totalmente aleatorias.
function initialPopulation(obj, sizePopulation, noDimensions)
   obj.population = rand(sizePopulation, noDimensions);
end
  • Evaluación de la Población: Cada solución en la población debe ser evaluada para conocer su valor de desempeño, este valor indica la superioridad de las soluciones sobre las demás. Usualmente este valor busca ser maximizado o bien minimizado.
function fit = evalPopulation(obj, population)
   fit = zeros(size(population,1),1);
   for i=1:size(population,1)
     fit(i) = obj.fitnessFunction(population(i,:));
   end
end
  • Ordenamiento de la población: Algunas veces es conveniente tener la población ordenada de acuerdo a su valor de desempeño, de forma que las mejores soluciones se encuentren primero. Aunque este proceso es conocido por ser costoso computacionalmente, por lo que su uso debe ser limitado.
function sortPopulation(obj)
   temp = sortrows([obj.fitness, obj.population], 1);
   obj.fitness = temp(:,1);
   obj.population = temp(:,2:end);
end
  • Revisar los limites de búsqueda: En ocasiones los algoritmos utilizan operadores que pueden sacar de los limites permisibles a las variables que estás siendo controladas en las soluciones. Debido a que la solución que se busca esta restringida en un área bien delimitada, soluciones fuera de esta área no deben ser aceptadas. Por lo que esta función busca entre la población soluciones que tengan variables fuera del rango permisible y las reúbica en el limite permitido.
function solutions = checkBounds(obj, solutions)
   solutions(solutions>1)=1;
   solutions(solutions<0)=0;
end

Para esta implementación consideramos que todos los problemas trabajan variables en el rango de 0 a 1, y estas son escaladas para cada problema en el rango de interés de los mismos.

  • Actualiza la mejor solución: Es común que los algoritmos utilicen la mejor solución encontrada en todo el proceso evolutivo para guiar el movimiento o evolución de la población, para ello este valor debe ser actualizado en cada iteración.
function updateBest(obj)
   [bestFitTemp, bestIndex] = min(obj.fitness);
   if bestFitTemp < obj.bestFitness
      obj.bestSolution = obj.population(bestIndex,:);
      obj.bestFitness = bestFitTemp;
   end
end
  • Ejecución del algoritmo: Este método se encarga de iniciar el proceso de búsqueda, y mantener la evolución del proceso por el número de iteraciones definidas en la clase. Es importante el orden en el que los otros métodos son llamados, así como el método llamado operadores (operators) que es la implementación del algoritmo en sí.
function start(obj)
   obj.initialPopulation();
   obj.evalPopulation();
   for i=1:obj.maxNoIterations
      obj.actualIteration = i;
      obj.operators();
      obj.updateBest();
   end
end

El metodo operators se define como abstracto, por lo que cada subclase (cada algoritmo) debe definirlo. Este método se encarga de modificar las soluciones actuales con la información recibida, y se espera que devuelva la población con las nuevas soluciones junto con el valor de desempeño de las mismas. Esto lo puede hacer internamente o bien utilizando la función definida en la clase base.

  • Otras: Existen otras funciones que son compartidas entre los algoritmos relacionadas en la forma en la que se presenta la información del proceso de evolución, o bien los resultados obtenidos. Estas funciones pueden encontrarse en el repositorio de GitHub.

Cómo un ejemplo de la implementación del algoritmo, dejó el código del método operators del algoritmo basado en enjambre de particulas (PSO), que será mejor explicado en otra ocación:

function operators(obj)
   % atraction to the best personal solution
   pbAtraction = rand(obj.sizePopulation,obj.noDimensions) .* ...
        (obj.bestPersonal(:,2:end)-obj.population);

   % atraction to the best global solution
   bestAtraction = rand(obj.sizePopulation,obj.noDimensions) .* ...
        (repmat(obj.bestSolution, obj.sizePopulation, 1) - obj.population);

   % update velocity trayectories.
   obj.velocity = obj.velocityParam * obj.velocity + ...
        obj.bestPersonalParam * pbAtraction + ...
        obj.bestParam * bestAtraction;

   % update solutions
   obj.population = obj.population + obj.velocity;
   obj.checkBounds();

   % eval fitness
   obj.evalPopulation();
end

Cada función contiene código extra que revisa las condiciones de las variables, y permite un uso mas dinámico de estos métodos. Pero el concepto clave fue expuesto en este documento. Si tienes alguna duda o comentario sobre algún código en esta implementación déjanos saber en la sección de abajo.

Una clase para gobernarlos a todos.

La genética de la optimización

Algoritmo Genético.

El algoritmo genético imita el comportamiento evolutivo descrito por Darwin, donde el individuo mejor adaptado prevalece. En ambiente limitado de recursos, lo individuos compiten entre si, y aquellos mas fuertes obtienen ventaja sobre los demás, en posibilidades de permanecer con vida, así como de aparearse y generar descendencia. Con forme pasa el tiempo y las generaciones los individuos son cada vez mas adaptados al ambiente y mantienen los “buenos” genes. Fue desarrollado en los años 1970, de la mano de John Henry Holland.

El algoritmo genético considera que cada solución del problema representa un individuo, el cual tiene un cierto nivel de adaptación a su entorno, la adaptación es un valor numérico dado por la función de desempeño (fitness). Estos individuos que forman parte de una población compiten entre si, se reproducen, e inclusive mutan, pero dado las condiciones limitadas de recursos solo un numero fijo de los mismos sobreviven en cada generación.

De la misma forma en la que las especies evolucionan en cada generación, el algoritmo evolutivo busca que el conjunto de soluciones inicial evolucione en cada iteración, hasta que los individuos sobrevivientes sean representaciones de soluciones con altos desempeños.

Este comportamiento evolutivo es imitado mediante un conjunto de operadores que trabajan sobre la población actual. Suponiendo una población inicial poco adaptada al ambiente, usualmente soluciones completamente aleatorias, y el conocimiento de su adaptación (fitness). En cada iteración del algoritmo primeramente se ejecuta un mecanismo de Selección de Padres. La descendencia es generada mediante un Operador de Cruzamiento, en el cual la información de los genes de los padres es mezclada, cada uno de los nuevos descendientes tiene una pequeña probabilidad de experimentar un proceso de Mutación, donde su información genética puede ser alterada de forma aleatoria. Finalmente la nueva población y la anterior compiten para mantenerse con vida para la siguiente generación, un operador de Remplazo.

Primero lo primero, Codificación.

Antes de poder implementar los operadores genéticos es importante definir la codificación de los individuos. Las soluciones en este algoritmo deben estar representadas por una cadena de caracteres, usualmente binaria para números, o soluciones que buscan seleccionar entre un numero de objetos la mejor combinación.

Por ejemplo:
Si una de las variables del problema tiene que seleccionar entre 127 objetos, entonces la codificación de dicho gen seria la cadena binaria del valor propuesto por la solución.

127 = 1111111
83 = 1010011
1 = 0000001

En el caso que alguna variable del problema tiene que elegir un grupo de objetos que serán incluidos y el resto no, entonces el gen adquiere un valor de 1 en los indices de los objetos que considera para dicha solución y 0 en los demás.

Obj1 Obj2 Obj3 ... ObjN
   1    0    1 ...    1
   0    0    1 ...    0
   1    1    0 ...    1

Aunque la representación binaria es muy utilizada en este algoritmo no es estrictamente necesaria ya que si una solución busca escoger para cada gen entre un numero N de opciones, la cadena podría ser de la forma:

Suponiendo N como 5.
Gen1 Gen2 Gen3 Gen4
   2    5    3    1
   4    2    1    1
   5    5    2    1

O alguna mezcla de estas.

El siguiente ejemplo muestra la codificación utilizada en para resolver el problema de optimización discreta conocido como problema de la mochila. En este problema se busca escoger entre todos los objetos el conjunto de ellos que represente el mayor valor económico, teniendo como limitante un peso máximo posible de escoger. Prueba entre las diferentes combinaciones, y observa la codificación de la solución para cada una.

Este problema es desarrollado mas extensamente en esta entrada

Operaciones Evolutivas.

Estos cuatro operadores manipulan la información obtenida de una población aleatoria de forma que iterativa, simulando un comportamiento evolutivo, mejorando las soluciones, mediante la explotación de la información conocida por los individuos que constituyen a la población actual.

Selección de Padres.

En la selección se considera un balance entre aleatoriedad y elitismo, para dar preferencia a individuos con mejor adaptación, pero también permitir la diversificación evitando convergencia prematura.
La selección de padres se lleva a cabo mediante un proceso de torneo, donde dos individuos distintos de la población son seleccionados aleatoriamente, y el que tenga mejor desempeño es seleccionado. Este proceso se realiza tantas veces como numero de individuos hay en la población.

Desde 1 hasta el numero de individuos en la población:
  P1 = selecciona un individuo aleatoriamente
  P2 = selecciona un individuo aleatoriamente
  seleccionados = selecciona entre P1 y P2 al que tiene mejor fitness.

Cruzamiento.

Con los pares de padres seleccionados, entonces un torneo probabilistico evalúa si estos producirán descendencia entre ellos. La descendencia es generada mediante un Operador de Cruzamiento, en el cual la información de los genes de los padres es mezclada al rededor de un punto de cruce, aunque existen otras formas de realizar esta operación.

Este operador es el que mezcla la información de los individuos seleccionados. Cada par de individuos generan dos descendientes, por lo que al final una nueva población de mismo tamaño que la anterior es generada.

Para cada par de individuos seleccionados: %(NoIndividuos / 2)
  Si (numero aleatorio > Probabilidad de cruce):
    indiceCruce = NumeroAleatorio entre 1 y el numero de bits de la solución.
    Hijo1 = [Padre1[desde 1 hasta indice de cruce] , Padre2[desde indice de cruce al final]
    Hijo2 = [Padre2[desde 1 hasta indice de cruce] , Padre1[desde indice de cruce al final]
  sino
    Hijo1 = Padre1
    Hijo2 = Padre2
  Descendencia.agregar([Hijo1, Hijo2])

La información de la descendencia es resultado de una mezcla de la información de los padres en un punto de cruce, el cual es seleccionado de manera aleatoria. Por ejemplo si tenemos los siguientes padres: $P1 = 01010101$ y $P2 = 11111111$, y el punto de cruce resulto ser 4 entonces:

Punto de cruce aleatorio PC, suponemos que sea 4
P1_1 = P1(1:4) %que sería 0101
P1_2 = P1(5:8) %que sería 0101
P2_1 = P2(1:4) %que sería 1111
P2_2 = P2(5:8) %que sería 1111

Ch1 = [P1_1 P2_2] %01011111
Ch2 = [P2_1 P1_2] %11110101

Mutación.

Cada uno de los nuevos descendientes tiene una pequeña probabilidad de experimentar un proceso de Mutación, donde su información genética puede ser alterada de forma aleatoria. Esta posibilidad es evaluada en cada bit de la solución de la siguiente forma:

Para cada nuevo individuo generado:
  Para cada bit i:
    Si (numero aleatorio > Probabilidad de mutación):
      individuo[i] = inverso(individuo[i]) %si era 1 -> 0 o el inverso.

Remplazo.

Finalmente la nueva población y la anterior compiten para mantenerse con vida para la siguiente generación, un operador de Remplazo selecciona los individuos tomando en cuenta su adaptación al medio.

Añadir la nueva población con la anterior
Ordenar la población de acuerdo al desempeño
Población = Seleccionar los NumeroIndividuos mejores de la población.

De esta forma la siguiente iteración tendrá de inicio los mejores individuos encontrados hasta el momento. Esta estrategia es elitista y suele tener problemas de convergencia prematura. Existen múltiples variantes para estos operadores. En otra entrada hablaremos sobre algunas de estas variantes y sus características.

Clasificación.

Este algoritmo pertenece a la clasificación de:

  • algoritmos evolutivos,
  • metaheurísticos,
  • optimización global,
  • algoritmo poblaciónal,
  • para un solo objetivo, aunque tiene sus variantes multiobjetivo
  • optimización de parámetros reales, o en problemas de combinatoria, incluso mixtos.

Este algoritmo es uno de los pioneros en el área, y abrió el paso a muchas versiones que utilizan está misma inspiración de la evolución.

Pseudocodigo

P = PoblaciónInicial(NoPoblación)
F = FunciónDesempeño(P)
mientras (i < NoIteraciones):
  Padres = SeleccionaPadres(P)
  Hijos = Cruzamiento(Padres, ProbCruz)
  Hijos = Mutación(Hijos)
  FH = FunciónDesempeño(Hijos)
  P = Remplazo(P, Hijos)

Implementaciones.

Este algoritmo esta implementado en javascript con el modulo AISearch, desarrollado por nosotros, y disponible en el área de pruebas.

La genética de la optimización

Algoritmos que van mas allá.

Algoritmos metaheurísticos.

En muchas ocasiones en la investigación científica se busca encontrar formas eficientes de realizar procesos. Usualmente estos problemas terminan siendo representados mediante un proceso de optimización, donde el objetivo es encontrar una configuración de parámetros (variables) que mejor resuelvan el problema dada una métrica que los clasifica.

Cuando estos problemas son muy complejos (NP Hard) no pueden encontrarse soluciones de forma determinista, o bien es imposible enumerar todas las configuraciones posibles en un tiempo aceptable. Este tipo de problemas se conocen también como intratables o altamente intratables. Usualmente en este tipo de problemas suelen utilizarse métodos heurísticos, que son diseñados especificamente para el problema a tratar.

Las heuristicas son métodos desarrollados para ofrecer soluciones de forma mas rápida o para encontrar una solución aproximada donde los métodos clásicos son lentos o fallan en encontrar una solución.
https://en.wikipedia.org/wiki/Heuristic_(computer_science)

Algunos problemas comunes en estos métodos es que suelen atorarse en óptimos locales o bien si la naturaleza del problema cambia un poco puede que estos no funcionen de forma correcta ya que están diseñados especificamente para el problema en cuestión.

Con estas restricciones en mente surgen un nuevo conjunto de métodos denominados metaheurísticos. Estos algoritmos están diseñados para dar una respuesta rápida, esquivando óptimos locales, y para trabajar independientemente del problema, lo que cual les brinda robustes al enfrentar cambios en la naturaleza del mismo.

La palabra “meta” quiere decir que va mas allá.

La forma en la que están diseñados estos algoritmos es muy variada, pueden ser resultado de imitar un fenómeno natural (bioinspirados) o basarse en una trayectoria, tener una única solución o un conjunto de ellas (poblacionales), buscar el optimo global o también un conjunto de óptimos locales (unimodal – multimodal), tener un único objetivo o múltiples, entre otras clasificaciones.

Blum y Roli remarcan algunas características de los algoritmos metaheurísticos:
+ Son estrategias que “guían” el proceso de búsqueda.
+ Buscan eficientizar la exploración por el espacio de búsqueda.
+ Se componen de técnicas que van desde búsqueda local hasta complejos procesos de aprendizaje.
+ Son métodos aproximados y usualmente no determinísticos.
+ Incorporan mecanismos que evitan quedar atrapados en óptimos locales prematuramente.
+ No son diseñados para un problema en especifico.
+ Los mas avanzados utilizan la experiencia obtenida en la búsqueda (mediante algún tipo de memoria) que los dirige.

Clever Algoritms

Dada su naturaleza de diseño independiente del problema, son aplicados en a los problemas de la forma “black box”, es decir, pueden ser implementados sin tener que tener ningún (o muy poco) conocimiento del problema que buscan resolver. Esto permite que sean muy flexibles en su uso sin tener que realizar muchas modificaciones. Generalmente las técnicas que requieren menos información sobre el problema que resuelven son mas flexibles, aunque menos eficientes. El mejor ejemplo de este comportamiento sería la búsqueda aleatoria, que simplemente genera soluciones aleatorias.

Este tipo de algoritmos también son denominados como Algoritmos de Optimización Estocasticos. Esto debido a que utilizan aleatoriedad en sus operaciones, lo cual los convierte en no deterministas. Esto no significa que sean algoritmos aleatorios, si no que explotan la aleatoriedad al explorar de manera probabilística, enfocandose en áreas de interés.

J. Brownlee utiliza la siguiente clasificación:

  • Algoritmos Estocásticos.
  • Algoritmos Evolutivos.
  • Algoritmos Físicos.
  • Algoritmos Probabilisticos.
  • Algoritmos Basados en Partículas.
  • Algoritmos Inmunes.
  • Algoritmos Neuronales.

La mayoría de estos algoritmos presentan un comportamiento de aprendizaje inductivo, es decir que van aprendiendo de la experiencia, comienzan de manera aleatoria y mediante generación, selección y prueba van mejorando las soluciones a través de la iteraciones.

En este espacio publicaremos un análisis de algunos de estos algoritmos, con su explicación, clasificación, bondades y posibles problemas, y el pseudocodigo y código en Matlab. La lista de algoritmos que tenemos contemplados por el momento son:

  • Algoritmo Genético.
  • Evolución Diferencial.
  • PSO (Optimización por enjambre de partículas).
  • Algoritmo inspirado en los estados de la materia.
  • Optimización por colonia de hormigas.
  • Búsqueda del Cuckoo
  • (coloca aquí el algoritmo en el que estés interesado)

Algunos problemas que estarán contemplados mas adelante y que utilizan un proceso de optimización son:

  • Segmentación inteligente de imágenes:
    Este proceso busca separar el fondo de uno o varios objetos en una imagen, para ello utiliza el histograma de la imagen, y busca representar esta información estadística mediante una sumatoria de gaussianas parametrizadas.
  • Asignación dinámica de canal en comunicaciones inalámbricas:
    Busca vincular a cada usuario con un conjunto de entre los canales disponibles del sistema, de forma que el sistema incremente su eficiencia en el uso espectral.
  • Entre otros.

Dejanos saber en los comentarios si tienes un problema en especifico que utiliza estos algoritmos o bien que consideres implementarlos para su solución. Dinos también si te interesa que incluyamos una revisión de alguno en especifico.

Si estas interesado en escribir sobre alguna implementación propia o compartir tu experiencia escribiendo para el blog, estamos buscando gente como tu. Dejanos saber que estas ahí.

Algoritmos que van mas allá.

Percepción artificial de un mundo real

La visión es el más avanzado de nuestros sentidos. El mundo a nuestro alrededor es comprensible gracias a todos aquellos elementos que somos capaces de percibir con la mirada.

El ser humano es capaz de interpretar la información percibida a través de los ojos en una infinidad de formas diferentes. El significado que damos la información adquirida a través de nuestra visión es el resultado de un largo proceso de aprendizaje, vivencias y experiencias. Así pues, cada uno de los elementos presentes en una imagen armonizan entre sí para dar un significado a todo lo que vemos. Dicho esto, la magia de la visión humana no yace en el hecho de poder percibir imágenes de nuestro entorno, sino en nuestra habilidad para comprender la información que percibimos, así como en nuestra capacidad de hacer inferencias y tomar decisiones a partir de dicha información.

Continue reading “Percepción artificial de un mundo real”

Percepción artificial de un mundo real