La función distancia se usa muy a menudo en muchos algoritmos para calcular la distancia entre puntos en el espacio. Hay algoritmos que hacen un uso intensivo de esta función como k-nn, k-means, o casi cualquier método que incluya buscar puntos cercanos. Por lo que reducir el coste de calcularla reporta una mayoría considerable de rendimiento.

Distintas distancias

Por suerte podemos usar funciones distancia diferentes. Una función distancia tiene que cumplir las siguientes condiciones cuando
x != y:

dist(x,x) = 0
dist(x,y) != 0
dist(x,y) = dist(y,x)
dist(x,y) <= dist(x,z) + dist(z,y)

Para calcular la distancia entre dos puntos es habitual usar la distancia euclídea:

dist(A,B) = √∑(Ai-Bi)²

Podemos hacer una primera mejora, si solo necesitamos comparar distancias podemos ahorrarnos la raíz cuadrada. Obtenemos una función distancia perfectamente válida y que puede reemplazar la euclídea

Pero hay una mejora más eliminar los cuadrados de las restas. Sin embargo hay un detalle a tener en cuenta, el cuadro de un número negativo es positivo, por lo que no basta con eliminarlos hay que reemplazarlos por el valor absoluto.

Esta parece un mejora menor pero en caso de espacios de muchas dimensiones puede llegar a notarse.

Pero no somos los primeros en llegar a esta conclusión, es conocida como distancia Manhattan:

dist(A,B) = ∑|Ai-Bi|

Realmente podemos reemplazar la distancia euclídea por cualquier distancia (tiene que cumplir los cuatro puntos anteriores) siempre que la nueva distancia cumpla que si en la distancia euclídea la distancia entre dos puntos cualesquiera A y B es mayor (o menor) que entre dos puntos cualesquiera C y D, en la nueva distancia también ha de ser mayor (o menor) en la nueva distancia.

Desigualdad triangular

Viendo la cuarta propiedad de las funciones distancia, conocida como desigualdad triangular, podemos usarla para acelerar la comparación entre distancias.

Teniendo tres puntos A,B,C sabemos que:

dist(A,B) + dist(B,C) >= dist(A,C)

|dist(A,B) – dist(B,C) | <= dist(A,C)

Es decir la suma de dos lados de un triángulo es mayor o igual que el tercer lado y el valor absoluto de la resta de dos lados es menor o igual que el tercer lado.

En la imagen de debajo de este texto se puede ver ejemplos visuales:

Esto nos sirve para acotar distancias sin calcularlas. Calculando solo dos distancias podemos acotar el valor mínimo y máximo de la tercera lo cual nos puede permitir descartarla sin calcularla.

Por ejemplo, nos dan un punto C y tenemos que averiguar qué otro punto está más cerca A o B. A y B ya los conocíamos así que tenemos precalculada dist(A,B). Calculamos dist(B,C), si dist(B,C) < |dist(A,B) – dist(B,C)| entonces podemos decir que dist(A,C) > dist(B,C) ¡Sin calcularla!

En muchas situaciones tenemos puntos que son previamente conocidos/aprendidos. Por lo que podemos tener una tabla de distancias entre puntos precalculadas y usarlas para acotar distancias sin necesidad de calcular la distancia entre todos los puntos.

El problema es que una tabla de distancias entre puntos puede ocupar demasiado espacio en memoria. Veamos una alternativa, calcular la distancia de todos los puntos al mismo punto. Si no hay muy buenas razones para usar otro punto usaremos el origen de coordenadas (el punto cuyas coordenadas son todas ceros). Es muy poco costoso calcular la distancia de origen a un punto P

dist(O, P) =  √∑Pi² (euclídea)

dist(O, P) =  ∑Pi (Manhattan)

Ahora si tenemos precalculadas las distancias de los puntos a comparar con el origen y nos dan un nuevo punto P. Calculamos dist(O, P) y tenemos precalculado dist(O,A) y queremos saber dist(A, P).

Sabemos que:

dist(O, A) + dist(O, P) >= dist(A, P) >= |dist(O, A) – dist(O, P)|

Max dist(A, P) = dist(O, A) + dist(O, P) 

Min dist(A, P) = |dist(O, A) – dist(O, P)|

Ya tenemos una cota mínima y máxima de cual es la distancia de de A a P. Realmente por si misma no nos sirve de nada pero si hay que comparar con muchos puntos es suficiente pare descartar muchos de ellos.

Comparar distancias

Vamos a ver con una imagen la diferencia entre las tres distancias comentada en este texto. Euclídea, Euclídea² (sin hacer la raíz cuadrada) y distancia Manhattan. En la imagen inferior se puede ver la forma y el área que cubre una «circunferencia» de radio 2. (Tomando como circunferencia como aquel objeto geométrico cuyo todos sus puntos estan a la misma distancia del centro, en este caso 0,0)

Vivimos en la época en que los datos son tan valiosos como el dinero. Es imposible desarrollar modelos de Big data o de aprendizaje maquina sin una gran cantidad de datos (el término «big data» puede ser una pista de lo importantes que son). Obtener estos datos es uno de los problemas más costosos de resolver a la hora de implementar estos modelos.

La necesidad de datos no termina ahí, para sacar rendimiento a estos modelos necesitan datos sobre los que aplicarlos. Imagínate que voy al banco a pedir un crédito y solo tienen mi nombre y apellidos, con eso su departamento de riesgos no va a poder evaluar cuanto «riesgo» supone darme un crédito. Necesitarán que rellene un formulario y les lleve varios documentos que les permitan valorar ese riesgo. En ese caso soy consciente de ello, pero en muchos otros no.

No sirve alimentar al sistema con datos a lo loco, estos datos necesitan tener algunas características:

Cantidad: se necesitan montones de datos para obtener un modelo. Obtenerlos es un proceso complicado y en algunos casos caro. Puede ser que no sea necesario recopilar los datos, que ya estén en bruto, pero que sea necesario «extraerlos». Incluso es posible que digitalizarlos.

Procesar estos datos tiene un coste, no basta con «acumularlo y lanzarlos a los algoritmos», necesitas saber que hacer con ellos y adaptarlos. Eso necesita un equipo de expertos detrás.

Calidad: los datos han de ser ciertos y útiles. O lo que es lo mismo han de tener la mínima cantidad de errores.

Esto hay que tenerlo en cuenta al procesar los datos. Según el método de recopilación puede haber errores al introducir los datos, al transcribirlos, malentendidos o directamente datos falsos. ¿Quién no ha mentido al rellenar un formulario?.

Relevancia: si tenemos muchos datos pero no podemos obtener conclusiones de ellos no nos sirven. Por desgracia es posible que durante la fase de recopilación de datos no se sepa muy bien cuáles son útiles o que surja una especie de «síndromes de Diógenes» de los datos y se recopilen todos los que se pueda. Como consecuencia asume que cuando usas una web o una aplicación todo lo que haces es recopilado.

Por ejemplo, saber el número de pie de todos los que entran a una tienda probablemente no nos resulte útil (quizás, si es una zapatería). Sin embargo lo que han comprado si.

Hay un tipo de datos especialmente valioso que sirve para cruzar entre varias fuentes. Un ejemplo es el número de teléfono móvil. Es un dato que no solemos revelar mucho de darlo al realizar compras por internet, encargos, rellenar formularios para tarjetas descuento, …. Sin embargo puede ser tremendamente valioso ya permite identificar al mismo individuo en distintas fuentes de datos y cruzarlas.

Variedad: de nada sirve tener muchos datos de gran calidad si pertenecen a una muestra pequeña de individuos. Es necesario tener muestras del mayor número de sujetos posibles.

Si los datos están sesgados el modelo también lo estará. Por ejemplo si obtienes los datos a partir de una aplicación de descuentos en el móvil estás dejando de lado a toda la gente que no use smartphones o no tengan suficiente soltura para usarlos o no quiera «instalar cosas raras» en ellos. Los datos de esas personas se vuelven más valiosos para completar el modelo. Quizás podría hacer un concurso donde se participe rellenando una papeleta con los datos personales.

Legales y éticos: es importante no recopilar datos que la ley prohíba recopilar o qué no sea ético hacerlo. Aunque es posible hacer trampas y usar proxys. Los proxys son datos que de forma directa o indirecta permiten «deducir» otros datos. A veces no son 100% exactos pero no importa los algoritmos pueden tolerar cierta cantidad de errores. Un ejemplo tan obvio que solo sirve como ejemplo sería no poder pedir el sexo pero si el nombre. Con el nombre se puede extraer el sexo en la mayoría de los casos. Hay veces que un proxy no es un solo dato sino varios.

Baratos: debido a la cantidad de datos necesarios es importante que obtener cada muestra sea barato. Eso puede condicionar el método elegido para recopilarlos e introducir sesgos.

Muchos datos que necesitan tratamiento manual son procesados por personas con sueldos bastante bajos.

Hasta este punto todo han sido costes. El modelo no dará beneficios hasta que empiece a usarse. Esto no es una justificación para no pagar por los datos, de hecho es probable que te hayan pagado en forma de descuentos, promociones, concursos. El problema es que no sabes que van a hacer con esos datos. ¿Y si se usan en un modelo que acaba siendo usado en perjuicio tuyo?

Una vez creado el modelo para obtener beneficio hay que usarlo. Para ello se necesita obtener tus datos para introducirlos al modelo y obtener un resultado. Lo que este resultado aporte al negocio (más conversiones a clientes, más compras, mejor servicio, ahorro de recursos y costes) es el beneficio que produce.

Cuando alguna empresa anuncie que ha desarrollado un sistema que le va a permitir ahorrar o ganar cantidades ingentes de dinero piensa que tus datos han sido necesario para ello.

Supongo que la entropía os sonara de la termodinámica y así es. Cuando Shannon desarrollo la teoría de la información llego a una formula similar a la que describe la entropía en los sistema físicos. He aquí la formula:

H(x) = – Σ p(xi) * log2(p(xi))

Es decir, si tenemos una variable x con distintos valores posibles, para cada valor (xi) cuya probabilidad es p(xi) la entropía de ese valor es:

 p(xi) * log2(p(xi))

Y la entropía total es la suma de la entropía de cada valor. A veces a cada posible valor se le llama signo.

Por ejemplo supongamos un semáforo que se pasa el 45% del tiempo en rojo, el 45% en verde y el 10% restante en ambar. La entro pía de cada señal seria:

Entropia =  -0,412

¿Como se usa esto y qué mide?

Mide la cantidad de bits que «aporta» un dato o lo que es lo mismo, la cantidad de información que transmite. Para entenderlo mejor tomando el ejemplo más simple, un bit con dos valores (0,1) pero cambiando la probabilidad de cada uno, respetando que la suma de ambas siempre es 1 (P(1) = 1 – P(0)):

Para el primer caso que es que el bit siempre sea 1 el valor aportado es 0. ya que no aporta ninguna información. en resumen si sabemos que un signo es más probable que otro aporta menos información que si ambos son equiprobables. 

¿Para qué nos sirve todo esto?. De forma muy simple, cuando haya que elegir entre varias propiedades, la entropía puede ayudarnos a elegir que parámetro escoger

Decenas de algoritmos de aprendizaje que van desde la sencilla regresión lineal a cosas tan complejas como las redes neuronales y casi todos (seguro que hay alguno que no solo por fastidiar) se basan en una misma y sencilla idea. Reducir al mínimo el error total de la función de aprendizaje.

Vamos poco a poco. tenemos una función f(x) que recibe una entrada de valores x = [x0,…,xn] y que tiene unos parámetros p = [p0,….,pi] que configuran la respuesta de la función. Esta función es la que aprende, el proceso de aprendizaje consiste en adaptar los parámetros p para aproximar la salida a una deseada.

Voy a ir al caso del aprendizaje supervisado que es el más sencillo de entender. Hay un conjunto de ejemplos de entrada x cada uno con una «respuesta» Y = [Y0,…,Um] asociada (la respuesta correcta). Lo ideal es que cuando a f se le pasa x devuelva una «respuesta» y = [y0,…,ym] esa respuesta sea lo más parecida posible a Y.

f(x) = y ≈ Y

Esto se ha de cumplir con todos los ejemplos que hay. Ajustamos p para que minimice la suma de los errores de cada muestra de aprendizaje.

min Σ error(y, Y)

• f es la función que pretende usarse para aprender el modelo.
• p son los parámetros de f cuyo valor se módica para adaptarse al modelo. Este cambio de valor es la parte que se aprende.
• x son los valores que recibimos como entrada de los cuales nuestro algoritmo tiene que calcular y
• Y es el valor real asociado a esos parámetros
• y es la aproximación calculada por nuestra función f

Para calcular el error se pueden usar diversas funciones. Igual que métodos para aproximar los valores de p. Sin embargo el algoritmo será algo parecido a este:

Inicializamos p
Para cada x
y = f(p, x)
e = error(Y,y)
aproximar(p, e)

El error total no siempre se calcula sumando los errores de cada muestra, pero es algo habitual.

A veces no es tan sencillo y para cada muestra x no hay un valor Y con el que comparar los resultados. El valor puede ser una propiedad de todos los resultados obtenidos. Por ejemplo muchos algoritmos de «clustering» se basan en minimizar la distancia interna entre elementos del cluster y maximizar la distancia externa entre los clusters elegidos.

Todo esto se puede complicar bastante y cambiar algunos detalles, pero en el fondo de todo algoritmo de aprendizaje hay una función de optimización que trata de reducir el error.

Ya hemos visto otras formas de generar frases. Esta forma de generar frases consiste en tener unas plantillas de las que sólo algunas partes son variables.

Por ejemplo:

Al abrir el cofre encuentras un ${adjetivo} ${objeto} para ${acción}

Al usar una plantilla las frases generadas tienen sentido y es fácil integrarlas con otras generadas de la misma forma. Los textos generados no tienen tanta variedad como con otros métodos pero te aseguras el sentido de los mismos.

Hay un curioso proyecto en inglés que partiendo de una base de datos de palabras en inglés te permite generar un frase a partir de un aplantilla en la cual solo indicas {{an_ adjetive}}, {{noum}} y el lo rellena con palabras al azar de la base de datos (de términos terroríficos al parecer)

Por ejemplo:

This is {{ an_adjective }} {{ noun }}. => This is a wicked cadaver.

En castellano el principal problema que tiene este método son  distintas flexiones que tiene las palabras y la necesidad de que las distintas palabras de la frase tengan concordancia entre ellas. «Caperucita rojo» es claramente incorrecta. Así que nosotros tenemos que aportar género y número para nombres, complementos, adjetivos. Y en el caso de los verbos persona, tiempo y modo. Para solucionar este problema hay tres opciones:

• Limitar las opciones, generamos frases solo con un género, número, tiempo y modo.
• Crear diccionarios diferentes para cada opción. Por ejemplo para los nombres se crearían cuatro diccionarios: femenino-singular, femenino-plural, masculino-singular, masculino-plural.
• Usar un algoritmo que modifique las flexiones de cada palabra Algo de eso ya hemos visto en este blog. Es un algoritmo al que le pasas una palabra y la forma de la misma que quieres obtener y te la transforma. Ya hemos visto algo así.

En JS generar este tipo de frases es muy sencillo, preparamos una plantilla.

‘Al abrir el cofre encuentras un ${objeto} ${adjetivo} para ${acción}`

Crearemos una lista de opciones:

var adjetivos = ["épico","dorado","brillante"];
var objetos = ["mazo", "mandoble", "arco"];
var acciones = ["matar dragones", "rescatar princesas", "luchar batallas"];

Ahora usaremos una función para elegir uno de ellos al azar:

function selectOne(items){
return items[Math.floor(Math.random() * items.length)];
}

Y finamente otra que rellena la plantilla:

function template(objeto, adjetivo, accion){
return `Al abrir el cofre encuentras un ${objeto} ${adjetivo} para ${accion}`
}

Vamos con el ejemplo de funcionamiento:

template(selectOne(adjetivos), selectOne(objetos), selectOne(acciones));

Ejemplo de resultados:

• «Al abrir el cofre encuentras un brillante arco para luchar batallas»
• «Al abrir el cofre encuentras un épico arco para matar dragones»
• «Al abrir el cofre encuentras un dorado mazo para matar dragones»

Este sistema para generar frases tiene la ventaja de que estas tienen sentido pero tiene la desventaja de que resultan repetitivas y si se usa varias veces en seguida se percibe el patrón.

Un mejora necesaria seria usar un algoritmo de flexiones para encontrar el género y número del objeto y adecuar el del adjetivo. Imaginaros que uno de los objetos es «espada», el adjetivos debería ser femenino.

Ya hemos visto, sin entrar en detalles, un sistema para generar frases en la entrada sobre los bots y las respuestas en lenguaje natural.

La solución más común para generar texto de forma automática es usar cadenas de Markov. Explicándolo pronto y mal consiste en tener un grafo para cada palabra, esa palabra está conectada con el resto de las posibles palabras que pueden seguirla. Cada enlace tiene asociada la probabilidad de que esa sea la siguiente palabra. Además de palabras hay que tener en cuenta dos nodos especiales: «inicio de frase» y «fin de frase». El primer nodo es por el que se empieza para formar una frase y al llegar al segundo se termina la frase.

La forma de usar este grafo es sencilla. Se parte del nodo «inicio de frase». El siguiente nodo se elige al azar, cada nodo tiene una probabilidad distinta de ser elegido. Una vez un nodo es elegido se repite la operación en ese nodo hasta llegar al nodo de «final de la frase».

Generar estos grafos a mano seria demasiado trabajo, por eso estos grafos se crean fácilmente a partir de textos. Tan sencillo como recorrer los textos e ir contando para cada palabra cual es la siguiente. Por ejemplo para la palabra «perro» tomando como base del aprendizaje las siguientes frases:

• El perro ladró a la bicicleta.
• El perro lamió la mano de su dueño
• El perro olisqueó la comida antes de comerla
• El perro olisqueó la prenda antes de seguir el rastro
• Como el perro y el gato

El resultado serían:

Olisqueó tiene el doble de probabilidades de ser elegida como siguiente palabra que las demás.

El problema que vemos aquí es con las palabras muy habituales como «y». Detrás de «y» puede ir cualquier cosa que no tenga ninguna relación con las palabras anteriores de la frase. ¿Como evitamos eso?. En lugar de generar el grafo de una sola palabra lo generamos de dos o tres. En nuestro caso si lo generamos de dos palabras quedaría así:

El problema de usar más de una palabra es que el tamaño de los textos de aprendizaje ha de ser grande o se repetirán siempre las mismas frases. Vamos a añadir una frase más para que no todas empiecen por «el perro»

• Al perro le gusta jugar con la pelota

El resultado

Con más palabras de profundidad las frases tienen más sentido, pero su variedad se resiente. Al final hay que buscar un equilibrio.

Este sistema sirve para generar frases que a veces tienen sentido o que por lo menos dan la sensación de que quieren decir algo. Es importante buscar textos similares para generar grafos que mantengan el sentido. Si por ejemplo mezclamos textos de gatos, animales, con gatos, herramienta, puede ser divertido el resultado pero difícilmente tendrá sentido. Al final el resultado de estas herramientas es más artístico que practico y el texto generado difícilmente tendrá sentido más allá de una frase, aunque si los textos están bien elegidos tendrás la sensación de que quiere decir «algo».

Un ejemplo muy sencillo de usar es esta aplicación cuyo uso es muy sencillo, basta con preparar los textos de ejemplo y pasarlos al generador:

python markov.py gen <name> <count>

• Name es el nombre del fichero que contiene esos textos
• Count es el nivel de profundidad de los nodos (el numero de palabras que tiene en cuenta)

Una de la ventajas de este sistema es que solo depende del idioma de los textos usado como fuente, el algoritmo funciona igual en todos los idiomas.