Simular ideologías con autómatas celulares

Antes que nada y para evitar problemas aquí vamos tratar con dos ideologías ficticias y opuestas. Los profilobostios y los antifilobostios. Efectivamente no existe algo así como un filobostio es una palabra inventada. Así me evito problemas de gente que pone la ideología por delante del sentido común. Cualquier parecido con la realidad es pura coincidencia….o no.

Antes de continuar, todos los ejemplos vistos en este texto se pueden probar en esta demo en github, con el código fuente disponible.

Usaremos autómatas celulares bidimensionale para modelar la población. Cada celda será un individuo y su estado será la ideología que defiende. En cada iteración un individuo evalúa a sus vecinos y sus propia ideología y adapta su creencia. Vamos a tener en cuenta las siguientes normas:

  • Cada individuo solo tiene información de su entorno. No tiene un conocimiento extenso y completo. No por ello deja de posicionarse  dentro de la ideología y de defender su posición respecto a sus entorno.
  • Un individuo solo puede adoptar una ideología que esté en su entorno. Es decir, solo puede adoptar ideologías con las que tenga contacto y por lo tanto conozca.
  • Un individuo tiene preferencia por elegir la ideología mayoritaria en su entorno. Un individuo tiene más probabilidades de elegir la ideología de la que más información a favor posea.
  • El individuo tiene en cuenta su propia ideología

Con estas reglas se intenta simular el hecho de que un individuo generalmente no tiene información completa si no que su posición ideológica se conforma por su entorno que comprende tanto las personas con las que se relaciona como los medios con los que se informa. .

Ideología

Vamos a ver dos formas de representar la ideología.

Simple: hay dos posibles estados, rojo y azul, sin grados y sin termino medio. Define ideologías en la que estas en un bando o estas en el otro.

Extendida: la ideología cada individuo puede tener 17 estados de -8 a 8. Siendo cualquier valor mayor que 0 azul, profilobostios, cualquier valor menor de 0 rojo, antifilobostio, y si es exactamente 0 de color negro, neutro. El valor absoluto representa “lo extrema” que es la creencia de un individuo en esa ideología. Está representación permite que individuos con ideologías opuestas y cercanas al neutro sean más cercanos entre ellos que con los extremistas de su propia ideología. Un detalle importante es que los individuos neutros también influyen en los demás. En ese aspecto la neutralidad sería una posición ideológica activa y que actuaría como una tercera postura del individuo más que como una ausencia de ideología.

Mecanismos de decisión

Existen dos mecanismos de decisión.

Aleatoria: el individuo elige al azar una ideología entre sus vecinos y la suya propia. Este mecanismo respeta la idea de que es más probable que elijas la ideología que es mayoritaria en tu entorno. Solo que no siempre es así. Esta forma de elección permite simular la “el carisma”. Una persona se deja convencer por aquella ideología que más le atrae sin ponderarla de forma meditada.

Media: el individuo analiza el valor de sus vecinos y el propio y elige la creencia más cercana a la media de todas las creencias. En el caso de la ideología simple, en lugar de calcular la media elige aquella ideología con más representantes.

Obstinados

Un elemento extra en estos modelos son individuos que no cambian de opinión, son defensores acérrimos de su ideología e ignora todo lo demás.

Ideología simple con selección aleatoria

Este es el caso más sencillo de entender. Representaría una población completamente polarizada y que se deja llevar por lo “atractivo” que sea el mensaje de una ideología. Cuando se ejecuta se puede observar que hay mucho movimiento, la gente cambia de ideología rápidamente y hay veces que alguna parece dominar de forma aplastante sobre otra para que luego todo cambie rápidamente. Un hecho importante es que tras un periodo de tiempo largo siempre hay una que se impone y la otra desaparece. En este caso ambas ideologías son “igual de atractivas” así que termina ganando una de las dos al azar. Lo que si que es cierto es que el proceso se refuerza, contra más extendida este una ideología más fácil es que crezca.

Puede parecer que esto es malo, pero realmente hay ideologías que son tan atractivas y útiles que es difícil que no se extiendan como por ejemplo “todos somos iguales”, “robar está mal”. Permite tener una base ideológica estable.

Una única ideología se impone

Ideología simple con selección aleatoria y obstinados

En el caso que estamos simulando conde ambas ideologías son igual de atractivas los obstinados impiden que la ninguna ideología se imponga actuando como fuente de nuevos partidarios de su ideología.

En esta situación el poder de los obstinados depende de lo atractiva que sea la ideología que defienden. Si defienden una ideología poco atractiva se quedan atrapados llegando a un caso similar al de “Ideología simple con selección media y obstinados” que veremos más adelante. Sin embargo si defienden una ideología muy atractiva esta puede llegar a extenderse y dominar.

Los obstinados impiden que una única ideología se imponga

Ideología simple con selección media

En este caso la población se divide en grupos que comparten ideología. En estos grupos un individuo se ve rodeado de un entorno estable que reafirma su ideología.

La población se divide en grupos ideológicos cerrados

Ideología simple con selección media y obstinados

Los obstinados no producen ningún efecto, al ser una decisión que tiene en cuenta a toda al vecindad su influencia es muy reducida y muchos de ellos acaban “atrapados” con vecindades que no comparten su ideología y a la que no tienen ninguna probabilidad de convencer.

La población se divide en grupos ideológicos cerrados con unos pocos obstinados aislados

Ideología extendida con selección aleatoria

El comportamiento aquí es muy parecido al de “Ideología simple con selección aleatoria” pero con múltiples ideologías. Lo curioso de esta situación es que cada “grado” en la ideología actúa como si fuera un bando contrario a todos los demás, se convierte en un todos contra todos de 17 bandos hasta que al final uno se impone a los demás.

Cada grado de creencia se comporta como un bando diferente, al final uno se impone

Ideología extendida con selección aleatoria y obstinados

Los obstinados impiden que la población colapse en un único valor manteniendo la competición entre ideologías. Al igual que en el caso con ideología simple el poder de los obstinados depende de lo “atractiva” que sea su ideología.

Los obstinados impiden que una única ideología se imponga

Ideología extendida con selección media

En este caso la ejecución rápidamente converge a una población donde se crean grupos ideológicos estables separados por una frontera de neutrales. Si nos fijamos en el color la mayoría de los individuos son cercanos a la neutralidad. La única excepción son pequeños que se crean dentro de los grupos más grandes cuyo color es más intenso.

La neutralidad y los grupos ideológicos muy cercanos a la misma predominan. Se pueden formar pequeños grupos más alejados de la neutralidad (arriba a la derecha el circulo rojo)

Ideología extendida con selección media y obstinados

Si al caso anterior añadimos unos pocos obstinados ocurre un cambio sorprendente. La población se radicaliza. Desaparecen los neutrales y los colores se vuelven más intenso.

Con un 10% de obstinados la neutralidad se reduce y la población de polariza
Con un 20% de obstinados la neutralidad casi desaparece y los individuos se alejan de ella

Conclusiones

Obstinación contra neutralidad

En el caso de las decisiones ponderadas con ideología extendida vemos que los obstinados actúan aumentando la polarización de la población. De hecho en el caso de la ideología simple donde la polarización es máxima los obstinados no tienen efecto. Promover la aparición de estimados puede servir ambas ideologías y así reducir “el peligro de los neutrales”

Para entender este peligro vamos a incluir un nuevo elemento, una especie de tendencia global en toda la población, está tendencia se puede deber a muchas causas: modas, noticias, decisiones políticas o errores.

Para simular esta tendencia basta con sumar o restar (según la tendencia beneficie a profilobostios o antifilobostios) a cada individuo. Tras está operación los ciudadanos neutros o cercanos a la neutralidad adoptan una posición ideológica.

Es decir en un mundo moderado un suceso externo puede fácilmente inclinar la balanza hacia uno de los lados.

Si fuéramos responsables de cualquiera de las dos ideologías nos interesaría eliminar este riesgo y la mejor forma para ambos bandos es promover la aparición de obstinados. Esto les protege de los neutrales y sus cambios de opinión, cuanto más cerca este un individuo de un extremo ideológico más difícil es que cambie de opinión. Como ambos bandos se benefician de este hecho su mejor movimiento es que ambos colaboren para lograr esta situación.

Selección arbitraria e ideología única

En los casos en que la ideología no se elige de forma ponderada si no de forma arbitraria una única ideología termina imponiéndose a las demás, el tiempo que esto tarde en ocurrir dependerá del tamaño de la población y de lo “persuasiva” (probabilidad de ser elegida) que sea cada ideología y del azar. Es importante saber que una ideología no tiene porque ser superior a otra, el simple azar la convierte en ganadora.

En este modelo cada pequeña diferencia ideológica se convierte en un bando aislado que lucha contra los demás hasta que se impone. No basta con que el tablero este azul o rojo, tiene que estar en un solo tono de este color.

Sin embargo es muy sensible a los obtusos que impiden que el sistema converja en una solo ideología manteniendo el enfrentamiento activo.

La dificultad de usar algoritmos para controlar a las personas

Siempre que se habla de medidas de control de la población usando herramientas tecnológicas se centra el tema en el derecho a la privacidad y la libertad individual. Pero aquí vamos a ver porque es difícil que ese tipo de control funcione tan bien como prometen. Nos vamos a centrar en el mundo laboral que me parece el más neutral.

Trabajo como programador y una de los grandes retos de la industria es medir nuestro desempeño. No es que no existan técnicas para medirlo es que no funcionan. Los jefes piensan que sí y están felices con sus datos. Si hay algo que he aprendido es que mucha gente se siente más segura con un dato de fiabilidad cuestionable que sin datos. Sin embargo como si de un fenómeno cuántico se tratara el hecho de medir el rendimiento de la gente afecta a lo medido. Que muchas veces es lo que se desea, se instala un sistema para vigilar a los trabajadores, no tanto por los datos como para que el trabajador se sienta vigilado y trabaje más. Sin embargo el resultado puede ser el contrario, menos trabajo y de peor calidad. Los trabajadores se centran en puntuar bien aunque eso suponga empeorar su trabajo. Y no se debe a que el trabajador solo busca trabajar lo menos posible, si no que, como a todos, le gusta que le reconozcan su trabajo, cobrar más sueldo y ser ascendido. Y va a invertir su tiempo y esfuerzo en aquellas tareas que le den más posibilidades de conseguir alguno de esos tres objetivos.

Cuando hablamos de engañar a estos sistemas suena como algo complicado, necesitarias grandes conocimientos del algoritmos, matematicas y miles de pruebas para ver como se comporta. Los propios creadores de estos sitemas te podrán decir que ellos no sabrian como engañarlos. ¿Qué posibilidades tiene una persona normal?. Muy pocas, pero cuando el sistema trata con cientos o miles de personas la cosa cambia. Una persona puede encontrar de forma accidental un comportamiento que le da una ventaja frente a la evaluación. Los seres humanos somos muy buenos adaptandonos y percibiendo patrones, es algo que hacemos sin darnos cuenta. Tambien somos buenos adoptando comportamientos de grupo, muchas veces sin ser conscientes de ello. Si algo parece funcionar lo adoptamos. Así que cualquier comportamiento beneficioso va a extenderse entre la población.

Estos sistemas se enfrentan a un reto que es difícil de resolver hasta para los humanos: Evaluar de forma objetiva a una persona en un entorno real. Para ello tienen que trabajar con métrica y simplificaciones que no siempre son fieles a la realidad. Por lo que es casi seguro que habrá errores de clasificación, buenos trabajadores que son clasificados como malos y viceversa. Incluso puede que el error sea más sutil, un trabajador puede descubrir que es mejor valorado si hace las cosas de una determinada manera que si las hace de otra. La primera manera puede ser más correcta desde el punto de vista profesional pero el trabajador va a optar por la que mayor recompensa/reconocimiento le de. Además este proceso se realimenta puesto que los trabajadores que no hagan las cosas así tendrán menos éxito en esa empresa y será más probable que sean despedidos, se vayan o adopten la otra forma.

No hace falta que haya una búsqueda consciente de los puntos débiles de algoritmo, el sistema funciona por prueba y error. Se parece mucho a las metaheurísticas basadas en población. Muchos agentes probando (aun sin querer) estrategias diferentes y los que encuentran una estrategia que mejora su valoración son beneficiados, estas estrategias se extienden por el resto de los agentes mientras que los que no las imitan reciben peor puntuación, esto crea un ciclo de mejora y propagación constante.

Una solución que puede parecer muy sencilla es que cada persona sea evaluar por los demás algo del estilo “poner estrellitas”, el problema de esto es que entonces el trabajador intentara “optimizar” la valoración del cliente. Puede dejar al cliente muy contento pero no realizar un trabajo satisfactorio. Por ejemplo puede dedicar demasiado tiempo atenderle a costa de realizar menos ventas o evitar atender a clientes “complicados”. Incluso puede derivar en una guerra entre compañeros para “quitarse de encima esos clientes”.

Otro problema que se da en este tipo de evaluaciones es “la inversión del control”. Se da cuando en una jerarquía con este tipo de control alguien de un puesto superior puede perder mas que alguien de un puesto inferior si este no realiza su trabajo. De tal forma que el puesto inferior puede llegar a forzar al superior. También puede darse el caso de que el “castigo” por no realizar su trabajo se reparta entre los puesto inferiores suponiendo menor castigo a nivel personal que en los puestos superiores. Esa es la base de las huelgas, cada uno de los trabajadores pierde el sueldo de un día, pero la empresa pierde la producción de un día. Esto puede ser un gran problema para la empresa si le supone incumplir contratos, perder clientes o tener que pagar luego horas extra para recuperar la producción perdida.

Otro elemento difícil de eliminar de estos sistemas son los prejuicios. El sistema cree ciegamente sus resultados, ni se plantea que pueda equivocarse, ni tiene ne cuenta excepciones, ni el contexto. Tampoco hay que olvidar que toda aproximación estadística comete un error de sesgo al juzgar a una sola persona. Los datos te pueden decir que el 20% de los trabajadores que visten con pantalones azules tienen bajo rendimiento pero cuando aplicas eso a una sola persona vestida con pantalones azules estas siendo injusto y quizás descartando a un buen trabajador por otro peor.

No son necesarios sistemas muy complicados para que surjan estos comportamientos. Haces años trabajé programando una herramienta interna de gestión de proyectos. Una de sus principales funciones era ayudar a automatizar los cálculos de los costes de cada proyecto y el punto del mismo. De eso dependía la parte variable del sueldo de los jefes de proyecto. El sistema era especialmente propenso a las trampas ya que todos los jefes tenían acceso a los datos y podían ver claramente los motivos de su evaluación. Además la evaluación se realizaba en un momento concreto de la semana, lo que te daba tiempo a “arreglar los datos” por último era muy fácil retocar datos sin que se notase y si te pillaban achacarlo a un error,el riesgo si te pillaban era bajo pero el beneficio en comparación era alto. Esto dio lugar a todo tipo de manipulaciones y puñaladas entre los jefes de proyectos. El ambiente no era el mejor, pero los objetivos artificiales del sistema se cumplían. El sistema en si no era nada especialmente complicado básicamente calculaba los costes y los asignaba a cada proyecto según el uso de los recursos que hacia. Sin embargo pronto me toco ir modificando el código para tener en cuenta “casos especiales”.

En resumen, a veces parece que ante el control automático solo hay dos caminos: la sumisión o la rebelión. Pero lo cierto es que el tercer camino la manipulación se nos da bastante mejor. Es más difícil controlarnos de lo que parece.Aun así existe el peligro de que estos sistemas inciten comportamientos no deseados como consecuencia de su uso.

Regresión lineal segmentada en Arduino

Vamos a seguir viendo “trucos” para aprovechar la regresión lineal. La principal limitación de la regresión lineal es precisamente que es “lineal”. Ya hemos visto que se puede utilizar la regresión lineal para calcular otro tipo de regresiones. Ahora vamos a ver como aproximar formas mas complicadas.

Cualquier curva se puede aproximar usando segmentos de linea recta. A mayor número de segmentos mejor aproximación. Por ejemplo debajo podemos ver la aproximación a una curva con forma de campana.

Se puede consguir mejor resultado si cada segmento empieza en el mismo punto que termina el anterior, pero la imagen es más realista respecto al caso que vamos a ver: Usar la regresión lineal para calcular cada uno de esos segmentos de forma independiente.

La forma de trabajar es muy sencilla, dividimos el espacio en varias partes para cada una de las cuales calculamos una regresión lineal. Luego cuando queremos estimar un valor lo primero es ver a que segmento corresponde y usar esa regresión para calcular su valor.

Para elegir como dividir la regresión hay varias opciones:

  • Dividir en segmentos iguales, es la forma más sencilla y entendible. Tiene el problema de que te puedes encontrar huecos sin datos.
  • Dividir cuando haya datos suficientes para asegurarse la calidad del aprendizaje. Se toman segmentos de longitud variable, el unico requisito es que haya suficiente punto de aprendizaje en ese segmento para asegurarse de que hay datos, si no los hay se alarga el segmento hasta que los haya.
  • Se empieza con una solo regresión, luego se divide en dos y se compara el error cuadrático medio entre ambos, si es menor en la version de mas segmentos se repite la operación

Este último punto no muestra algo interesante. Si necesitas comparar que combinación de segmentos es la mejor opción se puede usar el error cuadrático medio. Aquí puedes ver como calcularlo.

Ejemplo

Vamos a usar la librería Regressino en concreto nos vamos a basar en uno de sus ejemplos.

Lo primero es incluir la librería correspondiente y declarar una regresión lineal para cada segmento que queremos crear (en este caso 3)

#include <LinearRegression.h>

LinearRegression lr1 = LinearRegression();
LinearRegression lr2 = LinearRegression();
LinearRegression lr3 = LinearRegression();

El primer segmento va de X = 1 a X = 10, el segundo de X = 11 a X = 20 y el tercero de X = 21 a X = 30.

    Serial.println("Start learn");
    //1-10
    lr1.learn(1,2);  
    lr1.learn(2,3);
    lr1.learn(3,4);
    lr1.learn(6,7);
    lr1.learn(8,9);

    //11-20
    lr2.learn(11,24);  
    lr2.learn(12,26);
    lr2.learn(13,28);
    lr2.learn(16,34);
    lr2.learn(18,38);

    //21-30
    lr3.learn(21,66);  
    lr3.learn(22,69);
    lr3.learn(23,72);
    lr3.learn(26,81);
    lr3.learn(28,87);
    Serial.println("End learn");

Para calcular la estimaciones hay que tener en cuenta esos límites para saber que regresión lineal usar:


    for(int i = 0; i < 31; i++){
      Serial.print("Result (");
      Serial.print(i);
      Serial.print("): ");
      if(i < 11){
        Serial.println(lr1.calculate(i));    
      } else if(i < 21){
        Serial.println(lr2.calculate(i));
      } else {
        Serial.println(lr3.calculate(i));
      }
    }

Como podemos ver es un proceso muy sencillo pero no todo son ventajas.

Problemas

  • Puede dar lugar discontinuidades y saltos bruscos en los puntos donde se produce un cambio de segmento
  • Una de las limitaciones es que para cada valor de X solo puede existir un valor Y. Las rectas calculadas en cada segmento no pueden solaparse en ningun punto.
  • Lo contrario si que puede producirse, que varios valores de X tengan el mismo valor de Y
  • Necesitas tener valores de muestra en todos los segmentos. Si divides los datos en cinco segmentos, te tienes que asegurar de que tienes muestras suficientes para que el algoritmo de regresión calcule una buena aproximación en cada uno de ellos.

Ideas para explorar

  • Hemos usado el algoritmo de regresión lineal para cada segmento, pero podria usarse algún otro de los que hemos visto, incluso distintos en cada segmento.
  • Si hay un hueco sin datos podemos estimar la ecuación del segmento Y = m*X + c usando el punto final de segmento anterior (X1, Y1) y el punto inicial del segmento siguiente (X2, Y2). Para ello m = (Y2-Y1)/(X2-X1) una vez calculada la m podemos calcular la c = Y1 – m*X1. No es una solución ideal y seguramente resulte en una mala aproximación
  • Otra opción pra calcularlo es realizar el aprendizaje con algunos de los puntos del final del segmento anterior y de algunos del inicio del segmento siguiente.
  • Esa misma idea se puede usar para tratar de mejorar el aprendizaje permitiendo que el inicio y final de cada segmento se solapen con los segmento anterior y siguiente.

Calcular la media aritmética, media geométrica, media armónica y media cuadrática en Arduino

Vamos a ver como implementar más funcione estadísticas en un entorno tan limitado como Arduino. Para ello necesitamos usar formas acumulativas de cálculo. En este caso acumulativas se refiere a que no tengan que calcularse de nuevo todos los valores cada vez que se añade uno nuevo, esto nos ahorra gran cantidad de cálculos y de espacio en memoria.

Media aritmética

Es o que normalmente llamamos “media”. Corresponde con la suma de cada uno de los valores de muestra dividido entre el numero de valores:

\frac{1}{n} \sum_{} x

Ya la vimos como calcularla de forma acumulativa, vamos a recordarlo rápidamente:

mean = mean + (x-mean)/n);

Media geométrica

Es la raiz enesima del producto de cada uno de los valores:

\sqrt[n]{\prod_{} x}

Vamos a desarrollar nuestro cálculo acumulativo a partir del modelo acumulativo para calcularla que desarrollan en este articulo.

Resumiendo, calculamos la media de ln(x) usando la formula de la media acumulada vista antes:

meanLn = meanLn + ((log(x)-meanLn)/n);

Para calcula la media geométrica a partir de este valor vasta con elevar el numero e al valor calculado:

Necesitaras declarar el número e:

const double e=2.71828;

Media armónica

Se calcula dividiendo el numero de muestras entre el sumatorio de uno partido por el valor de cada muestra. (Si no te has enterado, tranquilo, no me he enterado ni yo y soy el que lo ha escrito). Se ve mejor con la fórmula:

\frac{n}{\sum_{} 1/x}

En lugar de usar la versión acumulativa vamos a optar por aprovecharnos de la relación entre las distintas medias:

harmonica = \frac{geometrica^2}{aritmetica}

En código:

harmonicMean =  pow(geometricMean(), 2)/mean();

Media Cuadrática

Es la raíz cuadra del sumatorio del cuadrado de los valores:

\sqrt{\frac{1}{n} \sum_{} x^2}

Para calcularlo usamos la misma formula que para la media aritmética pero aplicada al cuadrado del valor:

mean2 = mean2 + (((x*x)-mean2)/n);

Luego para obtener el valor final solo hemos de calcular la raíz cuadrada de la misma:

sqrt(mean2):

Puede encontrar el código de la implementación de todo esto en este proyecto de github.

Error medio absoluto y error cuadrático medio en Arduino

El error cuadrático y el R cuadrado se usan como medidas para evaluar el desempeño de un estimador. Es decir cual es el error que comete al estimar un valor. Un ejemplo de estimador seria, por ejemplo, una regresión, ahora si no interesa saber lo bien que estima esa función podemos hacerlo a partir de direrente estimadores.

Para calcularlos se usan dos valores, el valor real y el valor devuelto por nuestro estimador (representado por la Y con “sombrerito”). El error para cada caso es el valor absoluto de la resta de ambos valores:

Error = |\hat{Y_{i}}-Y_{i}|

Se puede entender intuitivamente de forma muy simple, es la diferencia entre el valor que obtenido del estimador y el valor real. Se usa el valor absoluto para que cuando se sumen varios errores no se “cancelen”. Si al estimar un valor se equivoca en 3 y al estimar otro en -3 el error total es 6 no 0.

Su calculo en Arduino seria:

double error = abs(y - ey);

Error medio absoluto

No podemos valorar un estimador solo por el error en una estimación, habrá que usar varias y calcular la media del error a lo que se le llama “error medio absoluto“, la suma del error de cada medida partido por el número de muestras:

MAE = \frac{1}{n} * \sum _{i=1}^{n}|\hat{Y_{i}}-Y_{i}|

Para implementarlo en Arduino vamos a usar el mismo “truco” que usamos para calcular diferentes estadisticos en Arduino. Usando la versión acumulada del calculo de la media para no tener que guardar todos los valores:

meanError = meanError + ((error - meanError)/n);

Error cuadrático medio

Otro valor usado es la media del error al cuadrado:

MSE = \frac{1}{n} * \sum _{i=1}^{n}(\hat{Y_{i}}-Y_{i})^{2}

Para implmentarla en Arduino vamos a usar el mismo “truco” que antes para el error medio:

 meanError2 = meanError2 + (((error*error) - meanError2)/n);

El problema de elevar los valores al cuadrado es que cuantificar su diferencia resulta poco intuitivo. Para hacer el valor más entendible se puede usar la raiz cuadrada del error cuadrático medio:

RMSE = \sqrt{MSE}

En código para Arduino:

sqrt(meanError2);

Todo esto lo puedes ver implementado en los ficheros error.h y error.cpp de SimpleStatisticsArduino

De regresión lineal a regresión logística en Arduino

Ya hemos visto como calcular la regresión lineal en Arduino y como a partir de esta calcular diversos tipos de regresiones. Lo que vamos a ver aquí es usar un truco para convertir la regresión lineal en regresión logística basandonos en la función sigmoide.

La regresión lineal se usa como clasificador binario entre dos conjuntos. En el caso ideal de regresion logística para cualqueir valor de x devuelve un valor de y que es 0 o 1 dependiendo de a que clase pertenezca. Pero en la vida real rara vez suele ser un “caso ideal” y hay valores para los que devolverá un valor comprendido entre 0 y 1. Este resultado puede interpretarse como la probabilidad de que sea del grupo representado por el valor 1 o cuadno esto carezca de sentido simplemente tomar cualqueir valor mayor de 0,5 como del grupo del 1 y cualquie valor por debajo como del grupo del 0.

La función sigmoide se define como:

1 / 1 + e^{-y}

El valor de y lo podemos sacar de la regresión lineal:

y = mx +b

Juntandolo todo:

1 / 1 + e^{-(mx+b)}

Veamos las diferencias entre ambas fórmulas:

Regresión lineal (verde) comparada con regresión logística (naranja)

Regresión Lineal:

  • Su fórmula define una linea
  • No está acotada, no tiene un valor máximo ni mínimo
  • Se usa para estimar valores.
  • Devuelve un valor numérico

Regresión logística:

  • Su fórmula define una "S"
  • Esta acotada entre 1 y 0
  • Se usa para clasificar un valor en uno de dos grupos. Clasificador binario.
  • El resultado que devuelve se puede interpretar de dos maneras: como probabilidad de pertenecer a un grupo si se toma el valor directamente o como pertenencia absoluta a un grupo u otro si se considera que cuando el valor obtenido este por encima de 0,5 se pertenece a uno y por debajo al otro.

Forma de implementarlo

La forma de implementar esto en un Arduino es aprovechar la librería que ya tenemos de regresión lineal y que nos soluciona los problemas de memoria y tiempo de cálculo que tienen los cálculos estadísticos en Arduino. Simplemente una vez que nuestro sistema aprenda el modelo lineal basta con transformar el resultado que devuelve este modelo para convertir su respuesta a la de una regresión logística.

    double exp = linealRegression.calculate(x)*-1; 
    return 1/1+pow(e, exp);

La implementación del código se puede encontrar en la librería Regressino

Utilidad

¿Tiene sentido transformar una regresión lineal en un modelo de regresión logística?. Aunque esta conversión se puede realizar para cualquier regresión lineal no tiene sentido hacerlo. Solo tiene sentido usarlos cuando se quiera entrenar un clasificador binario y haya dos grupos de elementos claramente diferenciables. Entonces se puede calcular la recta de regresión y convertirla en una regresión logística que funcione como clasificador.

Tampoco va servir para calsificar cualquier grupo de elementos, han de ser linealmente separables. dicho de forma más intuitiva, tienen que poder separarse trazando una linea recta entre ellos.

En definitiva, sin ser una opción ideal, es suficiente buena y útil como para plantearse su uso.

Estadísticas básicas en Arduino

Como ya vimos en el post sobre regresión lineal en Arduino, el principal problema que plantea Arduino para realizar cálculos estadísticos es la escasa capacidad de memoria y cálculo que tiene. Para ello en lugar de guardar todos los datos vamos a usar formulas que permiten aproximar los valores estadísticos que vamos a utilizar sin gastar casi recursos, la idea es guardar solo una aproximación.

En el siguiente enlace puedes encontrar la librería SimpleStatisticsArduino de Arduino que implenta lo explicado en este texto.

Para la varianza y la media usaremos las siguientes formulas que tratan de aproximar

numeroDeMuestras++;
media += (nuevoValor – media)/numeroDeMuestras;
media2 += (value^2 – media2)/numeroDeMuestras;
varianza = media2 – media^2;

Con estos valores podemos aproximar la suma de todas los datos:

suma = media*numeroDeMuestras;

La desviación estándar :

desviacionEstandar = sqrt(varianza);

Otros dos valores que podemos almacenar de forma muy sencilla y casi sin costes es el valor mínimo y máximo. Cada nuevo valor se comprueba:

if(minimo > nuevoValor){
minimo = nuevoValor;
}
if(maximo < nuevoValor){
maximo = nuevoValor;
}

Ahora con estos dos valores podemos calcular el valor central, que no es lo mismo que la media:

centro = (maximo – minimo) / 2;

Con esta estrategia solo necesitamos 6 variables para almacenar los datos sobre los que se calcula la estadística.

Estadística con dos variables en Arduino

Tenemos dos variables X e Y, partiendo de los cálculos del apartado anterior para cada una ahora podemos calcular los valores conjuntos, para ello debemos de almacenar dos variables más necesarias para calcular la covarianza:

mediaXY += ((XY)-mediaXY)/numeroDeMuestras;
covarianza = mediaXY – (mediaXmediaY);

Ahora con la covarianza podemos calcular la correlación:

correlacion = covarianza / (desviacionEstandarX * desviacionEstandarY);

Con estos datos podemos calcular los parámetros de la regresión lineal:

m = covarianza / varianzaX;
b = mediaY – m*mediaX;

Y la propia regresión:

y = m*x + b;

Si buscas una implementación de la idea de este post pero optimizada exclusivamente para la regresión lineal puede mirar la librería Regressino.

Por último podemos calcular el centroide que no es nada mas que el centro de cada una de las variables X e Y.

centroide = [centroX, centroY]

De esta forma se pueden calcular bastantes valores sin consumir casi memoria o recursos

Regresiones logarítmica, exponencial y potencial a partir de la regresión lineal en Arduino

Lo que vamos a ver en este texto tiene bastante de truco matemático, pero funciona lo suficientemente bien para que merezca la pena hacerlos.

Ya en otro post vimos como implementar la regresión lineal en Arduino, aprovechando ese mismo código se puede calcular la regresión para otras funciones que se pueden adaptar mejor a los datos que la lineal.

Cómo de aquí en adelante nos hará falta vamos a recordar que la fórmula de la regresión lineal es:

y = a + b*x

El algoritmo de la regresión lineal lo que hace es a partir de ejemplos de valores de x e y calcular los valores de a y b

Ahora intentemos explicar el truco que usamos. Primero tomamos la función que queremos ajustar a los datos, por ejemplo:

y = a * e^(b*x)

Buscamos una transformación lineal que deje la fórmula de la misma forma que la de la regresión lineal. En nuestro ejemplo calcular el ln de ambos lados de la igualdad:

ln(y) = ln(a) + b*x

Este truco solo funciona cuando sea posible encontrar una transformación de este tipo, que no siempre se puede.

Realizamos cambios de variables para transformar la formula:

x -> x
y -> ln(y)
a -> ln(a)
b -> b

Ahora podemos usar el mismo algoritmo que en la regresión lineal solo que con un par de cambios de variables:

  • En la fase de aprendizaje, cuando tengamos la pareja de valores (x,y) le pasaremos al algoritmo de regresión lineal (x,ln(y))
  • Una vez calculados los parámetros no tendremos (a, b) si no (ln(a), b) por lo que para obtener a tendremos que elevar e al valor obtenido a = e ^ln(a)
  • Ahora que tenemos los parámetros (a,b) para estimar un valor en lugar de usar la ecuación de la recta (regresión lineal) usaremos y = a * e^(b*x)

Regresión exponencial

La fórmula de esta regresión es:

y = a*e^(b*x)

La transformación lineal que vamos a usar es:

ln(y) = ln(a) + b*x

Como ya hemos visto los cambios de variable son:

x -> x
y -> ln(y)
a -> ln(a)
b -> b

En pseudocódigo:

regExp::learn(x,y){
    regLineal.learn(x,ln(y));
}

regExp::calculate(x){
    a = e ^ regLineal.a;
    b = regLineal.b;
    y = a*e^(b*x);
    return y;
}

Regresión logarítmica

La fórmula de esta regresión es:

y = a*ln(x)+b

La transformación lineal que vamos a usar es:

y = a*ln(x)+b

Efectivamente es la misma puesto que ya tiene la forma deseada.

Los cambios de variable son:

x -> ln(x)
y -> y
a -> a
b -> b

En pseudocódigo:

regLog::learn(x,y){
    regLineal.learn(ln(x),y);
}

regLog::calculate(x){
    a = regLineal.a;
    b = regLineal.b;
    y = a*ln(x)+b;
    return y;
}

Regresión potencial

La fórmula de esta regresión es:

y = b*x^a

La transformación lineal que vamos a usar es:

ln(y) = a*ln(x)+10^b

Los cambios de variable son:

x -> ln(x)
y -> ln(y)
a -> a
b -> 10^b

En pseudocódigo:

regPot::learn(x,y){
    regLineal.learn(ln(x),ln(y));
}

regPot::calculate(x){
    a = regLineal.a;
    b = 10^regLineal.b;
    y = b*x^a
    return y;
}

Ejemplo gráfico

Para ver bien las diferencias entre las cuatro regresiones dejo esta imagen donde se pueden ver todas para los valores a= 1 y b = 3

Comparativa entre las cuatro regresiones con a= 2 y b = 3

La librería

Todo lo aquí explicado se puede encontrar en la librería Regressino que implementa estas cuatro regresiones con ejemplos de como usarlas

Secreto compartido entre dos usuarios para Arduino

¿Sabéis esas películas en las que hay que lanzar una cabeza nuclear y dos personas han de meter su código, ya sea a mano o con una llave, para autorizarlo?. Eso es el secreto compartido. Una contraseña que está “dividida” en partes que tienen que juntarse para poder usarse. Hay esquemas de secreto compartido que permiten configuraciones mucho más flexibles, pero también son más exigentes en cuanto a recursos. Para el caso más simple de una contraseña y dos partes este sistema es suficiente.

Veamos cómo es el sistema. Tenemos una contraseña K que lanza los misiles. Está contraseña es dividida en dos contraseña K1 y K2. Al juntarlas se obtiene la contraseña K. Para que el sistema sea seguro ambas han de ser igual de difíciles de adivinar que K y cualquiera de ellas por separado no ha de aportar información que reduzca la dificultad de adivinar K.

Lo primeros que pensaréis será: “Tomamos la contraseña (K) de un tamaño de N bits y la dividimos en otras dos (K1,K2) de tamaño N/2 y listo”. Es cierto que funciona, pero tiene varios problemas, el principal es que estás desvelando información sobre K a quien posea una de estas partes.

Veamos otra aproximación. Generamos una contraseña K1 aleatoria de N bits. Está claro que K1 no aporta ninguna información sobre K, aunque por ahora tampoco nos sirve de nada. Será K2 quién los relacione. Para ello realizamos una operación xor entre K1 y K bit a bit.

Los poseedores de K1 no tienen ninguna pista que les ayude a calcular K o K2. Y lo mismo para quién posea K2.

Veamos un ejemplo:

K = 00110100
K1 = rand() = 10011011
K2 = K xor K1 = 10101111

K1 xor K2 = 00110100 = K

Una de las ventajas de este sistema es que puedes crear tantas parejas de claves como quieras.

Es poco probable que tengas armamento nuclear en casa. Pero esta idea es aplicable sobre cualquier sistema que use contraseñas.

Clasificar colores

Si estás buscando un algoritmo “mágico” que clasifique colores en esta entrada no lo vas a encontrar, más bien vas a descubrir lo complicado que es un tema que de primeras parece muy simple y posibles alternativas para clasificar colores.

La primera pregunta que tenemos que hacernos es ¿Cuántos colores hay?. Lo más probable es que los que están acostumbrados a trabajar con colores en el ordenador digan “unos dieciséis millones” y es cierto. Pero sería duro ponerle un nombre a cada uno así que seamos un poquito menos quisquillosos y pensemos como agruparlos. Cómo vamos a usar el sistema RGB podemos empezar por los colores que no sean mezcla de ningún otro: rojo, verde y azul. Luego los que son mezcla de otros dos colores: amarillo, cían, magenta. Por último los que son mezcla de los tres: blanco, gris y negro.

Los colores “puros” en RGB serían:

rojo (255,0,0)
verde (0,255,0)
azul (0,0,255)

amarillo (255,255,0)
cian (0,255,255)
magenta (255,0,255)

gris (192,192,192)
blanco (255,255,255)
negro (0,0,0)

Pero no basta con esos colores, claramente hay más: ocre, marrón, turquesa, naranja, morado, lila, malva, rosa…No hay una definición exacta de cuántos colores hay, ni siquiera de que significa cada nombre, algunos colores se solapan. Tanto que directamente a los colores entre los dos algunos les llaman cosas como verde-amarillos, rojo-naranjas,….

Pero aunque nos parezca que los colores son algo bastante universal no es así. Hay influencias culturales que hacen que algunos colores caigan a un lado u otro de la frontera, colores que son verdes o azules dependiendo de la cultura de donde sea el que los ve.

También hay factores fisiológicos que hacen que veamos los colores de forma diferente. No hay más que recordar alguna discusión en internet sobre de qué color es algo que aparece en una foto.

Y por último nuestra percepción de un color puede cambiar por influencia de los colores que lo rodean. Tomas un verde-amarillo lo pones junto a los verdes y lo ves amarillo, lo juntas con estos y lo ves verde. Tan sorprendente como frustrante.

Conociendo todas estas pegas y sabiendo que acertar al 100% es difícil por lo que no hay una solución ideal vamos a ver algunas soluciones.

Usar colores de referencia

Lo primero que se nos ocurre cuando hablamos de clasificar colores es tomar unos colores representativos como referencia. Cuando queramos clasificar un color medimos la distancia a cada uno de estos colores de referencia y elegimos el más cercano. Básicamente es un algoritmo del vecino más cercano. Ya hemos visto como calcular la diferencia entre dos colores, solo nos queda elegir los colores de referencia.

El problema es que no hay un espacio de color con una frontera clara y definida por lo que hace falta una gran cantidad de puntos de referencia. Generar ese listado de puntos es costoso, tiene que ser generado por humanos y resolver las diferencias de opinión entre ellos. Cómo creo que no tenemos recursos para hacer eso y tenemos que trabajar con tamaños de muestra muy pequeños el funcionamiento no es el ideal.

Espacio HSL

Una ventaja del espacio HSL (matiz, saturación, luminosidad) es que es relativamente fácil de saber el color. Basta con fijarse el valor del componente H o matiz, que viene expresado en grados o radianes. Con él ya puedes distinguir entre varios colores. Los más habituales son:

  • 0 rojo
  • 30 naranja
  • 60 amarillo
  • 120 verde
  • 180 cian
  • 240 azul
  • 300 magenta
  • 330 rosa
  • 360 rojo

La componente L el indica “la luminosidad” del color. Viene expresada en %. El 50% es el tono puro del color. Por encima los colores son cada vez más claros y por debajo más oscuros. Si es muy bajo esta cerca de color negro y si es muy claro lo está del blanco. Cómo referencia podemos usar estos valores:

  • 0, 2 negro
  • 3, 8 casi negro
  • 9, 39 oscuro
  • 40, 60 [nada]
  • 61, 91 claro
  • 92, 97 casi blanco98,
  • 100 blanco

El componente S indica la saturación del color, está expresado en %. Un valor muy bajo indica que está cercano al gris:

  • 0-2 gris
  • 3-10 casi gris
  • 10-25 grisáceo
  • 25-50 pálido

Aún así hay colores problemáticos como el marrón que surge de algunos rojos o narajas (o rojo-naranjas) muy oscuros. O los tono pastel que la mayoria surgen cuando la saturación y la luminosidad estan entre el 70% y el 85%.

Lista de colores

Hay otra opción, usar un listado de colores y sus nombres, buscar el más cercano y usarlo como respuesta. Aunque usar términos como “verde menta”, “amarillo eléctrico”, “rosa pastel” nos parezca menos exacto que los métodos anteriores, para los seres humanos resulta más fácil de entenderlos y muy intuitivos.

El principal problema es que no hay un estándar de que es el color “verde menta” puedes encontrar montones de listados y en cada uno puede un valor distinto o el mismo color llamarse de otra manera.

Las listas de colores se pueden conseguir de catálogos de pinturas, de la Wikipedia o de estándares como por ejemplo los colores web.

¿Por cual optar?

Si necesitar clasificar el color dentro de una lista cerrada de los mismos lo mejor es el primer método.

Si necesitas clasificar cualquier color dentro del espacio de colores sin tener colores de referencia.

La tercera resulta útil para mostrar resultado a los humanos.