Archivo del Autor: cubiwan

Reducir ruido usando umbrales

Los umbrales son la forma más intuitiva de filtrado de errores. Consiste en establecer valores a partir de los cuales no confiamos en las medidas de nuestros sensores. Estos umbrales pueden establecerse por varios motivos.

  • Limite de funcionamiento de nuestro sensor. Son los limites más alla de los cuales sabemos que nuestro sensor no trabaja correctamente. Por ejemplo muchos sensores de distancia comienzan a dar lecturas muy poco confiables a partir de ciertas distancias tanto de muy cerca como de muy lejos.

  • Limites del entorno. Limites esperados del entorno donde nuestro sensor esta situado. Por ejemplo un sensor de teperatura colocado en una habitación normal de una vivienda se pueden fijar como limites como límite inferior 0° y como limite superior 60° aunque el sensor trabaje en un rango mayor de temperaturas.

Umbrales para el valor

Se aplican directamente al valor medido por el sensor. Las lecturas que excedan los limites son eliminadas. Estos filtros con los primeros que se comprueban y facilitan el trabajo de los filtros que apliquemos después al eliminar valores erroneos extremos. Su implementación es muy sencilla.

Siendo S el valor medido por el sensor , y Tmin y Tmax los umbrales mínimo y máximo S será válido si:

S > Tmin & S < Tmax

Umbrales para el cambio

Se aplican a la cantidad que cambia el valor medido por el sensor en un tiempo determinado. Para poder usar este filtro es necesario conocer el tiempo que a transcurrido entre medidas del sensor. Se fija un valor máximo de cambio por unidad de tiempo. El valor del sensor se considerará valido si el cambio de valor respecto de la lectura anterior es menor que el tiempo transcurrido por el valor máximo de la unidad de cambio

Siendo S el valor medido por el sensor, t el momento actual, dt el periodo de tiempo transcurrido desde la anterior medida de valores del sensor,  T el umbral de cambio máximo permitido S será válido si:

S(t) < S(t-dt) + (T * dt) & S(t) > S(t-dt) – (T * dt)

Hay que tener en cuenta que S puede ser un valor correcto dentro de los umbrales Tmin y Tmax, pero que ha cambiado demasiado rápido para considerar la lectura correcta. por ejemplo tenemos un sensor de temperatura dentro de una habitación y en un segundo la temperatura pasa de 12º a 35º, obviamente hay algo mal.

Generador justo de números aleatorios en Arduino

Partimos de que tenemos una fuente aleatoria de bits (como el generador del mi otro post) pero desconocemos si es justa. ¿Que significa justa?. Significa que ambos valores (0,1) tiene la misma probabilidad (50%). Un bit puede ser aleatorio, pero no por ello sus posible valores han de tener la misma probabilidad. Vamos a usar como ejemplo un generador de bits cuyas probabilidades son:

P(0) = 0,1 = 10%
P(1) = 0,9 = 90%

si usamos esta fuente para generar bytes, números con muchos bit a 1 (11111101, 11110011,….) son más probables que el resto. Para evitar esto podemos convertir el generador de números en uno justo.

Para transformar la salida de ese generador en un salida justa necesitamos obtener dos bits. Si son iguales los desechamos, si son distintos devolvemos el valor del primero (también se podría usar el del segundo). ¿donde esta el truco? Que las probabilidad de que la pareja de bits sea [0,1] o [1,0] son siempre las mismas.

[0,1] = P(0) * P(1)
[1, 0] = P(1) * P(0)

Podemos ver una tabla con todas las opciones

Bit1Bit2ResultadoProbabilidadEjemplo
00 P(0) * P(0)0,1 * 0,1 = 0,01
010P(0) * P(1)0,1 * 0,9 = 0,09
101P(1) * P(0)0,9 * 0,1 = 0,09
11 P(1) * P(1)0,9 * 0.9 = 0,81

La desventaja de este sistema es que si las probabilidades están muy desparejadas puede costar tiempo encontrar una pareja distinta, en este caso el 82% de la veces habrá que descartar la pareja de bits.

Sin embargo cuenta con la ventaja de que no hace falta que conozcamos las probabilidades si tenemos dudas y necesitamos que nuestra cadena aleatoria, simplemente podemos aplicar este método y listo.

El código de ejemplo:

byte randomFairAnalog(int analogInput){
  byte rnd = 0;

  for(int i = 0; i < 8; ){
    delay(5);
    int aux1 = analogRead(analogInput)%2;
    delay(5);
    int aux2 = analogRead(analogInput)%2;

    if(aux1 == aux2)
      continue;
 
    rnd += (aux1 << i);
    i++;
  }

  return rnd;
}

Cuidado con este código en caso de que por algún motivo las lecturas del puerto dejen de ser aleatorias y sean todo el rato la misma la función caerá en un  bucle infinito.

Todo el código puede verse aqui.

Puedes ver el vídeo de como generar números aleatorios con Arduino, donde se aplica este método:

Haz click para ver el vídeo en mi canal de Youtube

Programación Lógica

La programación lógica está inspirada en la lógica de primer orden. El lenguaje más conocido es Prolog y si no lo conocéis os recomiendo que le echéis un ojo. Es una forma de programar bastante diferente a la habitual y aunque para cosas genéricas pueden ser más «cómodos» otros paradigmas de programación para ciertas ramas de la I.A. facilita el desarrollo de forma espectacular.

En programación lógica por lo general hay tres tipos de sentencias:

  • Hechos (facts): Serían los conocimientos de los que se parte. Son sentencias del estilo «Juan es padre de Pepe» que se escribiría como algo así: padre(juan, pepe).
  • Reglas (rules): Calculan nuevos hechos estableciendo relaciones entre ellos.Para ello se utilizan variables. Por ejemplo «Si X es padre de Y e Y es padre de Z entonces X es abuelo de Z» que en Prolog sería: abuelo(X,Z) :- padre(X,Y), padre(Y,Z).
  • Consultas (queries): Se usan para extraer información. Hay de dos tipos, la primera dice si un hecho es verdadero o falso. Por ejemplo «¿Es padre Juan de Pepe?» Que se escribiría (depende el intérprete de Prolog) padre(juan, pepe). El otro tipo son las que tiene que completar un hecho. Por ejemplo «¿Quien es el padre de Pepe?» padre(X, pepe).

Si queréis jugar con él sin tener que instalar nada podéis probar aquí.

Guardando el conocimiento

Supongo que ya os imaginareis como va a aprender este sistema. Convertiremos los datos a un conjunto de hechos y reglas. Para obtener la respuesta de la base de datos usaremos consultas.

¿Qué ventajas tiene este sistema?. Que no solo «aprende» datos, si no que también las relaciones entre ellos y la forma de calcularlas.

En el siguiente ejemplo vemos qué se define el concepto de abuelo y en lugar de añadir abuelo(juan, javi) añadimos la regla genérica para calcularlo.

padre(juan, jose). # juan padre de jose
padre(jose, javi). # jose pare de javi
abuelo(X,Y):-padre(X,Z), padre(Z,Y).

Probamos la query:

abuelo(juan, X)

Se comporta igual que si hubiéramos introducido el dato directamente abuelo(juan, javi).

Otra ventaja de la programación lógica es que es comprensible por los seres humanos, bueno al menos por algunos de ellos.

Usando Prolog desde Javascript

La cosa se complicó en este punto. Si quería que Chispas pudiera usar prolog necesitaba que se pudiera interpretar desde JS. El problema es que no encontré ningún intérprete de programación lógica que encajara con mi idea. O no tenían una sintaxis que me convenciera o no funcionaban bien cuando las reglas se complicaban o lo hacían pero eran muy lentos. Al final el que más me gustaba era el de la página que os he enlazado antes. El único problema es que la web era monolítica y tendría que separar la parte del interprete, encapsularlo y dotarle de una forma de introducir las reglas y leer los resultados que fuera amigable para el desarrollador. Pero eso era fácil de resolverlo programado. Al final el resultado podéis verlo aquí.

Histéresis

El ruido puede causar comportamiento errático. En este caso vamos a ver que problemas puede causar cuando hay un umbral de activación en un sistema. Por ejemplo una célula fotoeléctrica que determina cuando encender o apagar unas luces. Para ello hemos programado un microcontrolador «lea» el valor de la célula y cuando sea menor de 100 encienda la luz. Cuando el valor se aproxime a este punto puede devolver lecturas como estas:

100, 99, 98, 101, 102, 99, 100, 97

Que traducido a la luz que controla sería:

Off, On, On, Off, Off, On, Off, On

La bombilla parpadea sin parar, va parecer que los espíritus tratan de comunicarse con nosotros a través de ella. Para evitar eso se puede separar el umbral en dos. Uno para encender la luz y otro para apagarla. A este hueco se le llama histéresis. Por ejemplo se podría decidir que por debajo de 100 se enciende pero no se apaga hasta que el valor sea 105. Esta distancia sirve para evitar que la luz actúe erraticamente encendiéndose y apagándose sin parar cuando el valor es próximo al del umbral de activación.

El resultado seria:

100, 99, 98, 101, 102, 99, 100, 97

Off, On, On, On, On, On, On, On

Evitando que la luz parpadee todo el rato.

Reducir ruido usando la media y la desviación típica

Este metido es para detectar y reducir los ruidos intensos y poco frecuentes. La idea principal es que el valor leído más el ruido de baja intensidad se comportan como una función de normal. Se podría ver como que a mayor intensidad del ruido menos probable es que aparezca. Visto en forma de gráfica:

Standard deviation diagram micro.svg
De Ainali – Trabajo propio, CC BY-SA 3.0, Enlace

En la imagen se puede ver que según un valor se aleja de la media (μ) menos probable es que pertenezca a la muestra. Así que según su distancia a la muestra podemos saber lo probable que es que pertenezca. Sabiendo esto se ponen una distancia máxima a la media de tal forma que habrá dos umbrales (μ+distancia y μ-distancia) los valores que queden fuera de esos umbrales de eliminan. Valores habituales de filtrado corresponde a μ±σ, μ±2σ y μ±3σ. O aproximadamente dejan fuera el 16%, 2% y 0.1% de los valores (a cada lado del umbral). Para filtrar valores fijamos la probabilidad de pertenencia a la muestra que les «exigimos». Por ejemplo si un valor solo puede pertenecer a la muestra con una seguridad del 5% lo descartamos.

Este proceso lo podemos aplica una vez o varias, repitiéndolo hasta que no se elimine ninguno de los valores.

Una vez eliminados los valores que quedan fuera del umbral podemos aplicar alguno de los filtros ya vista como la moda, mediana o media para calcular el valor.

Ejemplo:

Usamos como limite 2σ. repetiremos el filtrado hasta que no haya descartes en las muestras

Iteración 1

muestras iniciales: [23, 4, 5, 5, 6, 4, 5, 4, 5, 6, 4, 12]

media: 6.9167

desviación estándar: 5.5179

tolerancias: 6.9167+(2 * 5.5179) = 17.953         6.9167-(2 * 5.5179) = -4.1191

muestras admitidas: [4, 5, 5, 6, 4, 5, 4, 5, 6, 4, 12]

Iteración 2

muestras iniciales: [4, 5, 5, 6, 4, 5, 4, 5, 6, 4, 12]

media: 5.4545

desviación estándar: 2.2962

tolerancias: 5.4545 + (2 * 2.2962) = 10.047       5.4545 – (2 * 2.2962) = 0.8621

muestras admitidas: [4, 5, 5, 6, 4, 5, 4, 5, 6, 4]

Iteración 3

muestras iniciales: [4, 5, 5, 6, 4, 5, 4, 5, 6, 4]

media: 4.8

desviación estándar: 0.7888

tolerancia: 4.8 + (2 * 0.7888) = 6.3776        4.8 – (2 * 0.7888) = 3.2224

muestras admitidas: [4, 5, 5, 6, 4, 5, 4, 5, 6, 4]

Ahora calculamos los distintos valores usando al media, moda y mediana

media: 4.8 

moda: 4

mediana: 5

Comparamos entre los resultados entre los datos filtrados y sin filtrar:

Filtrado Sin filtrar
Media 4.8 6.9167
Mediana 5 5
Moda 4 4

Es normal que solo se haya visto afectada la media, ya que tanto la moda como la mediana están libres de la influencia de los valores en los extremos.

Reducir ruido usando la mediana

Otra idea para reducir el ruido es ordenar todos los valores y coger el central. La idea es muy parecida a la de la media. Se considera el ruido como la suma de una pequeña cantidad aleatoria cuyo valor oscila entre -e y e. Si el valor real es V las muestras se dividirán entre la que sumen el ruido (V+e) y la que lo resten (V-e) . Quedando el valor real V mas o menos en el centro de todos los valores. La mediana es precisamente eso, el valor en el centro de todos los valores. Para calcularlo es necesario ordenar la lista de muestras. Este es su punto débil ya que aumenta el coste computacional de calcular la mediana.

Tiene varias ventajas:

  • Es sencillo
  • Es insensible al ruido intenso pero poco frecuente.

También tiene sus inconvenientes:

  • Ordenar las muestras puede ser una tarea costosa a nivel computacional
  • Solo se puede usar cuando se puedan tomar varias muestras de la misma medida

Ejemplo:

Partimos de las siguientes muestras [23, 4, 5, 5, 6, 4, 5, 4, 5, 6, 4, 12]

Mediana: 5

El resultado no se ha visto influido por los valores extremos (12 y 23)

Reducir ruido usando la moda

El uso de la moda para evitar el ruido es parecida al caso de la media, pero en lugar de sumar todos los valores se selecciona el que más veces se repite. La idea en que se basa en que la mayoría del ruido es pequeño así que el valor que más veces aparezca es el más cercano al real.

Al igual que la media, esta técnica solo sirve si se pueden capturar suficiente numero de muestras sin que el valor cambie de forma apreciable. En este caso necesitamos mas valores que en caso de la media.

Tiene varias ventajas:

  • Es sencillo
  • Requiere poco «coste computacional»
  • Es insensible al ruido intenso pero poco frecuente.

También tiene sus inconvenientes:

  • Solo se puede usar cuando se puedan tomar varias muestras de la misma medida
  • Requiere muchas medidas para ser exacto
  • Por lo general supone perder «resolución» en la medida para poder «agrupar» las medidas y calcular la moda. Por ejemplo si tenemos los valores 4,13 y 4,18 hay que eliminar el último decimal para poder contar ambos como el mismo valor 4,1

Ejemplo:

Partimos de las siguientes muestras [23, 4, 5, 5, 6, 4, 5, 4, 5, 6, 4, 12]

Moda: 4

El resultado no se ha visto influido por los valores extremos (12 y 23)

Reducir ruido usando la media

Vamos a ver una técnica para ocuparnos del ruido habitual pero de baja intensidad. En el caso de que podamos tomar varias medidas sin que haya a penas variación del valor a medir. Es decir, estamos midiendo un valor que no cambia o lo hace tan lentamente que podemos capturar varias muestras sin que cambie.

Podemos ver el ruido como la suma de una pequeña cantidad aleatoria cuyo valor oscila entre -e y e. Eso significa que si tomamos suficiente muestras y las sumamos entre ellas lo mas probable es que los diferentes incrementos y decrementos que el ruido produce al valor medido se «neutralice» entre si. Ese calculo, sumar varios valores y dividir la suma entre el número de valores es precisamente la media.

Tiene varias ventajas:

  • Es sencillo
  • Requiere poco «coste computacional»
  • Se puede aplicar a cualquier número de muestras, aunque a mayor número de muestras mejores resultados.

También tiene sus inconvenientes:

  • Solo se puede usar cuando se puedan tomar varias muestras de la misma medida.
  • Hay que filtrar primero los valores de ruido más intenso ya que «desplazan» el valor de la media y son tan poco habituales que no se «neutralizan» al sumar las medidas
  • No todos los ruidos siguen el modelo propuesto de valor aleatorio entre e y -e

Ejemplo:

Partimos de las siguientes muestras [23, 4, 5, 5, 6, 4, 5, 4, 5, 6, 4, 12]

Media: 6.9167

Se puede ver como el 12 y el 23 han influido «desplazando» la media hacia su lado.

Combinar varias metaheurísticas

Si ajustar una metaheurísticas ya cuesta. ¿Por qué querríamos sufrir el doble para hacerlo con dos?. Hay varios motivos, el principal es que una metaheurística no se comportan bien en todo el espacio de soluciones del problema y por ello se usan varias.

Un caso es que una metaheurística se puede comportar muy bien para calcular parte de la solución pero no toda. Entonces algunos de sus valores los calcularemos usando una metaheurística dejando intactos aquellas partes de la solución para los que no funciona a los que posteriormente aplicaremos la segunda metaheurística que al igual que la anterior no alterará la parte para la que no funciona. Este proceso tiene que repetirse varias veces permitiendo que ambas partes evolucionen de forma conjunta.

Otro caso en que resulta útil aplicar una segunda metaheurística es cuando tenemos una que funciona muy bien explorando el espacio de soluciones y encontrando la zona donde se encuentra el máximo pero muy mal para precisar el valor de este. En ese caso se usa una metaheurística para acercarnos al máximo y cuando ha terminado aplicamos otra para precisar el resultado.

Ahora el problema es como combinar varias metaheurísticas ya que algunas funcionan con mutiles soluciones y otras con una sola.

Empezamos por el caso más intuitivo, el de que ambas metaheurísticas recurran a una población de varios individuos. Aquí las opciones son varias:

  • Cada metaheurística se ejecuta de forma separa con sus propia población de soluciones y cada cierto tiempo se intercambian soluciones entre ellas.
  • Ambas metaheurística actúan sobre las mismas soluciones y compiten entre ellas. Solo las mejores soluciones pasan a formar parte de la población
  • Intercalar metaheurísticas. Aplicamos una durante varias iteracciones  una y luego iteramos varias veces con la otra.

Para el caso de combinar dos metaheurísticas que trabajan con un solo resultado todas las opciones se limitan a usar primero una y luego la otra. Este proceso puede repetirse varias veces o realizarse solo una vez.

Para el caso de combinar metaheurísticas con población y las que trabajan mejorando una única solución:  

  • Tras cada ciclo de la metaheurística orientada a población se aplica la otra metaheurística a los individuos nuevos tratando de mejorarlos
  • Otra opción es usar la metaheristica individual como función de modificación/creación de nuevo individuos.

Un ejemplo muy habitual de combinar metahurísticas es en el caso de los algoritmos genéticos, tras haber generado los nuevos individuos usando los operadores de mutación y/o cruce  y antes de que compitan con el resto de la población se trata de mejorar los nuevos individuos usando alguna metaheurísticas que explore el espacio cercano a cada individuo tratando de encontrar el máximo local.

Trilateralización

Tras que medir la distancia al emisor no diera el resultado deseado pensé en no escribir esta entrada, pero como puede ser útil y ya la tenia medio escrita he decidido terminarla.

Ya hemos visto cómo calcular (más o menos) la distancia a un emisor. Si conocemos la situación del emisor podemos situarnos en algún punto de una circunferencia de radio r1 (r1 es igual a la distancia al emisor). Si añadiéramos un segundo emisor de coordenadas conocidas y al que calculamos la distancia r2. Esto nos sitúa en una segunda circunferencia que corta a la primera en dos puntos. Ahora ya sabemos que estamos situados en uno de esos dos puntos. Para saber en cual exactamente necesitamos un tercer emisor cuya posición conozcamos y del que podamos calcular la distancia r3. Esta tercera circunferencia coincidirá con las otras dos en un solo punto. En la imagen se ve mejor

Trilateration.svg
De Braindrain0000 de la Wikipedia en inglés, CC BY-SA 3.0, Enlace

Ahora toca ponerlo todo en lenguaje matemático. En lugar de usar circunferencias vamos a usar esferas, los cálculos son los mismo y nos permite no tener los tres emisores y el receptor en el mismo plano. La ecuación de una esfera cuyo centro está en las coordenadas (a,b,c) es:

(x ─ a) 2 + (y ─ b) 2 + (z ─ c) 2= r2

Esta ecuación representa a todos los puntos de la súperficie de una esfera. Cómo tenemos tres esferas que coinciden en un punto de sus superficies hay que buscar un punto (x,y,z) que cumpla las ecuaciones de las tres esferas.

Esfera1, vamos a ser amables con nosotros mismo y vamos a colocar esta esfera en el origen de coordenadas (0,0,0) por lo que su ecuación es:

x 2 + y 2 + z 2 = r12

Esfera2, también por simplificar nos la vida, colocamos el centro de esta esfera en línea con la anterior en las coordenadas (d,0,0). Su ecuación es:

(x – d)2 + y 2 + z 2 = r22

La tercer esfera la colocamos con el centro en el mismo plano pero con ambas coordenadas distintas.

(x – i)2 + (y – j) 2 + z 2 = r32 

En el articulo de la wikipedia esta la resolución completa de las ecuaciones paso a paso, yo salto a la conclusión:

x = (r1 2 – r2 2 + d 2 ) / 2d

y = (r1 2 – r3 2 + i 2 + j 2) / 2j + (x * i / j)

z = √(r12 – x 2 – y 2 )

Con estos cálculos ya tienes localizado el punto exacto. Desgraciadamente en la vida real las mediciones no suelen ser tan exactas por eso la mejor solución es detectar donde cortan dos circunferencias (por ejemplo la 1 con la 2 y la 1 con la 3) Buscar los puntos mas cercano y tomar el punto medo entre ambos, teniendo en cuenta que es una aproximación y que no será el punto exacto.