Archivo del Autor: cubiwan

Flexiones y derivaciones de las palabras.

Uno de los mayores problemas que tenemos para conseguir que nuestro agente pueda tanto interpretar como generar con más naturalidad las frases ha de ser capaz de manejar las flexiones y derivaciones de nuestro lenguaje, al menos de una forma básica.

Eso le permite usar e interpretar correctamente el género, número, conjugaciones y tiempos verbales. Incluso aumentativos y diminutivos.

Reconozcamos que conversaciones como:

– Chispas Hola, soy Lorena

– Hola señor Lorena

– Chispas enciende las luces

– La luces está encendido

Quedan muy absurdas.

Desgraciadamente el lenguaje no se construye pensando en que sea fácil procesarlo por un algoritmo y al final el código acaba siendo un montón de reglas y excepciones. Hay que asumir que no son 100% correctos y que van a fallar en casos concretos que se salten las reglas. Hay mecanismos para incluir estás excepciones. Aún así hay que tratar de controlar el léxico usado. Como siempre es más fácil controlarlo si reducimos el lenguaje a un contexto concreto.

Pero es que hay que tener en cuenta que  todo puede funcionar bien y una palabra puede estar correctamente cambiada de género y número y aún así ser incorrecto su uso. Por ejemplo: «El manzano está en flor» si lo pasamos a femenino «La manzana está en flor» aunque manzana es correcto cambia el sentido de la frase. Ejemplos hay a montones «caso, casa», «paso, pasa»… Desgraciadamente es difícil de controlar ya que no solo depende de la palabra en sí, si no también del contexto y de su significado.

Además a veces el paso de una forma otra otro no es sencillo ya que se pierde información de la palabra original. Por ejemplo del plural al singular. En el caso de la palabras acabadas en es no queda claro cuáles tienes que quitar la terminación -es y cuales solo la -s.

Meses -> Mes

Ceses -> Cese

A todos estos problemas hay que contarle varios tipos de excepciones:

  • Verbos: llevan sus propias reglas (conjugaciones verbales) y varían según el género, número y tiempo.
  • Nombres propios: estos son un drama, los hay indistinguibles de nombres comunes (Rosa, Mar, Pilar). Los hay invariantes, que no varían con el número o el género: Sócrates y otros que si (María,Mario) y los que varían a veces no siguen las reglas habituales (Carlos, Carla).
  • Invariantes: palabras que no cambian su forma para los distintos géneros y/o números (Gafas).
  • Excepciones: palabras que no cumplen la reglas para cambiar el género o el número (Hombre/Mujer)

Los algoritmos has sido recogidos en el proyecto jsESinflection que está divido en cinco ficheros JS.

Plurales y singulares jsESnumber.js

Masculinos y femeninos jsESgender.js

Aumentativos jsESaugmentative.js

Diminutivos jsESdiminutive.js

Despreciativos jsESdespective.js

Para cargarlas se puede usar el siguite codigo:







var number = new jsESnumber();
var gender = new jsESgender();
var despective = new jsESdespective();
var augmentative = new jsESaugmentative();
var diminutive = new jsESdiminutive();

Las llamadas para transformar las palabras son sencillas:

number.pluralOf(word);
number.singularOf(word);
number.singularOrPlural(word);
gender.feminineOf(word);
gender.masculineOf(word);
gender.masculineOrFeminine(word);
despective.despectiveOf(word);
augmentative.augmentativeOf(word);
diminutive.diminutiveOf(word);

También permite añadir excepciones si las reglas que aplican las funciones no dan el resultado correcto:

number.addException(singular, plural);
gender.addException(masculine, feminine);
augmentative.addException(normal, augmentative);
diminutive.addException(normal, diminutive)
diminutive.addException(normal, despective);

La librería ya incluye las excepciones más comunes pero para declarar las propias es tan sencillo como pasarle el par de palabras. Por ejemplo:

//realmente es innecesario ya esta incluido en la librería
gender.addException("hombre", "mujer");

Me gustaría decir que funciona a la perfección en el 100% de los casos, pero el leguaje tiene demasiadas excepciones y peculiaridades apra que así sea, sin embargo da un buen resultado la mayoría de las veces.

Extraer lemas de un texto

Una vez visto como lematizar palabras vamos a ver una utilidad de ello. Sacar de que va un texto. En realidad sacar los lemas principales de un texto y así poder compararlos. ¿Por qué convertir las palabras de un texto en lemas? Simplemente porque en un texto el mismo términos puede aparecer varias veces en distintas formas (masculino, femenino, plural, singular,…) y la única forma de saber que es el mismo termino es lematizarlos o en nuestro caso usar un stemmer, en concreto jsEStemmer

No todos los lemas van a ser importantes. En un texto largo puedes tener montón de palabras que no estén relacionadas con el tema principal del texto. La idea es que cuantas más veces salga repetido el mismo lema más probable es que el texto trate sobre el. Así una vez extraídos todos los lemas habría que contarlos y agruparlos para quedarnos solo con los más repetidos.
Pero antes de poder extraer los lemas hay que eliminar las stopwords que son palabras que no aportan nada y son tan comunes que casi siempre saldrían como lemas principales. Al final tendrías que casi todos los textos hablan de los lemas «un», «el», «de»,.. palabras que son muy comunes y no nos aportan nada sobre el texto.

Así que el proceso sería:

  1. Eliminar los caracteres no alfabéticos y convertir las mayúsculas a minúsculas. Asi como eliminar tildes, diéresis, etc.
  2. Eliminar stopwords
  3. Lematización la palabras restantes.
  4. Agrupar lemas similares por distancia
  5. Filtrar los lemas y dejar solo los más importantes.

En el caso de nuestra librería primero obtendríamos todos los lemmas y luego los filtraríamos.

var lemmas = stemmer.stemText(text, distance);
var lemmas = stemmer.filterLemmas(lemmas, max, number, percentage);

Se pueden filtrar por:

  • max – Número máximo de lemas que debe contener la lista
  • number – Número mínimo de veces que aparece el lemma en el texto
  • percentage – Porcentaje mínimo de veces que aparece el lemma en el texto

El resultado obtenido​ estará en forma de una estructura con tres datos:

  • Un listado de los lemas «similares»
  • El número de veces que aparecen estos lemas en el texto.
  • El porcentaje que representa respecto al total de palabras del texto sin stopwords.
function Lemma(){
  this.lemmas = []; //lista de lemmas similares
  this.number = 0; //numero de repeticiones en el texto
  this.percentage = 0; //porcentaje de repeticiones en el texto

  this.merge = function(lemma){...} //permite unir dos lemmas
}

¿Como sabemos si un lema es «similar» a otro?. Calculando la distancia entre lo dos. Si son menor que un valor umbral se consideran «idénticos». Esto es necesario porque el proceso de lematización no es tan perfecto como nos gustaría y dos palabras que deberían tener  y el mismo lema pueden generar lemas muy parecidos pero no identificos. Para ello se fija un valor de corte por debajo del cual dos lemas se consideran el mismo y se agrupan bajo la misma estructura. Se suman el número de veces que aparecen y el porcentaje.

Ahora teniendo los lemas principales de un texto podemos compararlo con los lemas de cualquier otro texto, palabra o frase para ver si están relacionados.

//Calcula lo similares que son dos listados de lemas
//El resultado se calcula entre 0 y 1.
var result = stemmer.compareArrayOfLemmas((a, b, threshold));

Medir distancia entre lemas

Ya hemos visto como medir la distancia entre palabras, pero el medir distancia entre lemas plantea un problema diferente a medir el de palabras ya que solo tienen en común el texto que vaya desde el principio del lema hasta la primera letra diferente. Por ejemplo, aunque cos y cas tienen la mayor parte de las letras en común su distancia debería ser alta ya que son lemas de palabras muy diferentes. La distancia que vamos a usar es el número de caracteres en común del principio al primer carácter diferente por dos (son caracteres en común en ambos lemas) dividido entre la suma del número de caracteres de cada palabra.


function distanceLemmas(a,b){
  var shorterLength;
  var totalLength = a.length + b.length;
  if(a.length > b.length){
    shorterLength = b.length;
  } else {
    shorterLength = a.length;
  }

  var i = 0
  for(; i < shorterLength; ++i){
    if(a[i] != b[i])
      break;
  }

  if(i == 0) {
    return 1;
  } else {
    return 1-((i*2)/totalLength);
  }
};

La distancia será un resultado entre 0 y 1. 0 si todos los caracteres coinciden 1 si no coincide ninguno.

Uno de los principales motivos para calcular esta distancia es agrupar lemas similares, ya que tras al lematización los lemas obtenidos para palabras de la misma familia no siempre son el exactamente el mismo, Tras realizar varias pruebas recomendaría que se consideren similares los lemas con una distancia de hasta 0.20-0.25.

Usando la librería jsEStemmer:


var stemmer = new jsEStemmer.stemmer();
var lemma1 = stemmer.stemWord(word1);
var lemma2 = stemmer.stemWord(word2);
var distance = stemmer.distance(lemma1, lemma2);

Medir distancias entre palabras

Para medir la distancia entre dos palabras considerando solo sus caracteres e ignorando su significado. Vamos contar el número mínimo de operaciones que deberíamos realizar sobre una palabra para convertirla en la otra.

¿Que operaciones existen?:

  • Sustitución de un carácter por otro.
  • Inserción de un carácter
  • Eliminación de un carácter
  • Transposición entre dos caracteres adyacentes.

Existen varios algoritmos, según que operaciones se quieran tener en cuenta:

Distancia Sus. Ins. Eli. Tra.
Hamming X
Jaro–Winkler X
LCS X X
Levenshtein X X X
Damerau-Levenshtein X X X X

El uso de estas distancias es muy variado, por ejemplo sugerir correcciones ortográficas o agrupar palabra similares.

Hay que tener en cuanta que esto solo es una medición de la distancia comparando caracteres de dos palabras, no se tiene en cuenta su significado. Por ello aunque «remando» por significado esta más próxima a «remar» que «retar» con estas distancias «remar» y «retar» son casi iguales.

 

Lematización de palabras

Si nos pusieran la típica prueba de «¿Que palabra no está relacionada? Descubridor, descubrimiento, recubrimiento». Creo que todos acertariamos diciendo que es «recubrimiento​». Pero para un ordenador recubrimiento y descubrimiento son casi, casi la misma palabra. Al no entender el significado de las palabras no le queda más remedio que comparar sus caracteres y esa es una mala medida de similitud. Al menos de forma directa ya que en Español hay muchas terminaciones similares que hacen que dos palabras distintas tengan formas parecidas. Por ejemplo pasas con casas tienen más letra en común que con casero cuando esta claro que casero esta más relacionado con casa.

Vamos a empezar por lo más sencillo, comparar palabras. Para ello deberíamos comparar las palabras por su lema. Este proceso se llama lematización. La idea es extraer una raíz común. Hay dos principales formas de hacerlo. Usando un diccionario que asocia cada palabra con su lema. Esto requiere diccionarios enormes que es difícil que contengan todas las posibles palabras. La otra forma de hacerlo es aplicar algún algoritmo que calcule el lema. La pega es que es difícil hacer un algoritmo que calcule correctamente todos los lemas. Como casi siempre que hay dos opciones hay una tercera que es combinar ambas. Usar un diccionario y si no se encuentra ahí el lema calcularlo.

Vamos a usar esta última técnica. Para ello usaremos el algoritmo de Porter

Antes de lematización y para reducir la complejidad hay que eliminar todos los caracteres no alfabéticos. Y reemplazar la mayúscula, letras con tilde, diéresis, etc por la misma letra en minúscula.

Por ejemplo, convertiríamos «pingüino3» en «pinguino».

Sobre este resultado aplicaríamos el algoritmo de lematización.

Para los casos en que sea necesario vamos a incluir un pequeño diccionario de tal forma que podamos incluir una palabra y su lema correspondiente.

Con todo esto se ha creado la librería jsEStemmer para lemmatizar una palabra:

      var stemmer = new jsEStemmer.stemmer();
      var lemma = stemmer.stemWord(word);

 

Reconocimiento del habla en el navegador

Para el reconocimiento del habla desde el navegador usaremos la web speech API que es estandar, aunque en mis pruebas solo me ha funcionado correctamente, con algunos «peros», en Chrome. He de advertir que esta API puede enviar los audios a un servidor externo para su transcripción, lo cual debe tenerse en cuenta a nivel de seguridad y privacidad.

El primer problema que puedes tener es que para acceder a la cámara y el micro el nevegador pide autorización al usuario y solo recuerda su respuesta cuando la página se sirve desde https. No se por qué pero el reconocimiento de voz hay que reiniciarlo cada poco así que si no lo sirves desde https se hace cansado estar recargando todo el rato. Yo acabé usando caddy que permite configurar un servidor web https rápidamente.

Una vez resuelto ese problema vamos a ver el código  para inicializar el reconocimiento del habla en el navegador:

var SpeechRecognition = SpeechRecognition || webkitSpeechRecognition;

var speechRecognition = new SpeechRecognition();
speechRecognition.continuous = true;
speechRecognition.interimResults = false;
speechRecognition.lang = navigator.language || navigator.userLanguage;

speechRecognition.onresult = resultRecognition;
speechRecognition.onend = function(){
  speechRecognition.start();
};

speechRecognition.start();

 

Puedes ver todos los parámetros disponibles aquí. Como ya he comentado antes, uno de los problemas que surgen es que speechRecognition.continuous = true que se supone activa el reconocimiento continuo no va muy bien y de vez en cuando deja de funcionar, para solucionar eso en el evento onend asignamos una función que lo que hace es reiniciar el reconocimiento del habla cuando este se caiga.

En el evento onresult ponemos la función que va a tratar el resultado del reconocimiento del habla. Obtendremos un listado de cadenas de texto con un porcentaje de fiabilidad de que lo el usuario ha dicho es eso. Los resultados van ordenados de mayor a menor porcentaje. Nosotros solo vamos a usar la más probable. Pero si por ejemplo esperas un color y los resultados son: «armadillo» (90%) y «amarillo» (80%) yo apostaría por la segunda.

Con la propiedad speechRecognition.interimResults indicas cuando se lanza el evento onresult. Si es false se lanzará solo cuando el sistema de reconocimiento del habla detecte que has terminado de hablar y tenga una versión final del texto. Eso hace que a veces haya una demora entre que terminas de hablar y que se ejecute la acción. Con el valor a true lo llamará según vaya construyendo el texto. El problema es que el texto puede sufrir cambios según vaya entendiendo nuevas palabras, esos cambios pueden afectar a palabras ya detectadas. Para saber si el texto es final o no se puede consultar la propiedad isFinal de cada resultado.

En nuestro caso la función como tiene marcado que solo se le llame cuando haya terminado el reconocimiento solo tiene que pillar la solución más fiable y analizarla. Una cosa que no entiendo muy bien el motivo es que en eventos.results tienes todas las frases detectadas hasta el momento. En nuestro caso nos interesa la última. Dentro de cada uno de los elementos del array hay otro array con todas las posibles transcripciones y su fiabilidad. ¿Confuso?. Mejor vamos a ver el código:

this.resultRecognition = function(event) {
var resultIndex = event.results.length -1;
var result = event.results[resultIndex];

console.log(result[0].transcript+': '+result[0].confidence);
analyze(result[0].transcript)
};

Una vez obtenida el texto se pasa a una función nuestra para tratar de analizarlo y asociarlo al comando correspondiente. Lo primero es limpiarlo de espacios y ponerlo en minúsculas ya que a veces el texto que devuelve tiene un «original» uso de las mayúsculas

text = text.trim();
text = text.toLowerCase();

Es posible que la transcripción tenga errores. Por ejemplo en mi caso muchas veces en lugar de «chispas» reconoce «chispa» y «chispas di» es imposible que lo entienda siempre transcribe «chispas de». Lo mejor es hacer pruebas y ver cómo se comporta. Pero hay que contemplar que nuestro agente pueda interpretar diferentes versiones del comando. Mi consejo es usar expresiones regulares.

Síntesis de Voz en el navegador

En esta parte del proyecto vamos a tratar que nuestro agente pueda hablar. Para ello vamos a usar software de síntesis de voz ya sea el integrado en el propio navegador o alguna librería externa.

El don de la palabra

La comunicación oral es algo fundamental para dotar a un agente inteligente de una comunicación natural con los simples humanos. Si bien el hablar dota automáticamente a nuestro agente de un aspecto inteligente hay que tratar de no abusar de este canal de comunicación. Es cómodo y esta bien para dar información breve y concisa, pero no para leer interminables párrafos y más con el nivel actual de esta tecnología que resulta en una voz muy plana con poca o ninguna entonación.

Generalmente hay que tratar de no repetirse. Si una información que está «hablando» nuestro agente es lo mismo exactamente que se puede leer en pantalla va a resultar más molesto que otra cosa. No hay que pensar en la síntesis de voz como una alternativa a las visuales si no como un complemento que puede permitir una interacción más natural y aportar información extra. Un ejemplo perfecto en un campo donde se usan bastante aunque no nos demos cuenta (generalmente cuando algo se usa sin que nos demos cuenta es que se ha logrado integrar de forma adecuada) es en los videojuegos. El recibir asistencia e información mientras jugamos es algo habitual.

Algunos estaréis pensando en que añadiendo síntesis de voz hacéis vuestras páginas accesibles, en realidad son dos cosas diferentes. La personas con diversidad funcional ya tienen software que les ayuda y si quieres hacer la página accesible lo mejor que puedes hacer es diseñar la página correctamente siguiendo las recomendaciones de accesibilidad. Eso no quita par que un asistente virtual sea una gran ayuda.

Programando

Usar el sintetizador de voz del navegador es muy sencillo.

var utterance = new SpeechSynthesisUtterance();
utterance.text = "hola mundo";

speechSynthesis.speak(utterance);

¡Ya esta!

Nada, hemos terminado. Lo bueno si es breve dos veces bueno….Venga vale, vamos a ver un poco más.

SpeechSynthesisUtterance permite ajustar varios parámetros de la voz:

SpeechSynthesisUtterance.pitch
SpeechSynthesisUtterance.rate
SpeechSynthesisUtterance.text
SpeechSynthesisUtterance.voice
SpeechSynthesisUtterance.volume

No os asustéis si ajustáis algún parámetro y no notáis diferencia. No os estáis quedando sordos es que la implementación del estándar no es muy completa. Por ejemplo para ajustar el pitch de nuestro ejemplo:

var utterance = new SpeechSynthesisUtterance();
utterance.text = "hola mundo";
utterance.pitch = 1;
speechSynthesis.speak(utterance);

Supongo que todos los parámetros se entienden menos el de voice. ¿Como ajustamos la voz?. Para ello tenemos que usar alguna de la que nos provee el navegador. Para obtener el listado basta con llamar a:

speechSynthesis.getVoices()

Que devuelve un array con la descripción de todas las voces disponibles. Debajo pongo un ejemplo de una de las entradas del array:

default: false
lang: "es-ES"
localService: false
name: "Google español"
voiceURI: "Google español"

Los parámetros más importantes son el idioma (lang) y si es local o no. Esto último es importante porque indica que es posible que el texto se envié a un tercero, lo cual puede afectar a la privacidad y quizás habría que evitar leer datos de carácter privado.

En muchos casos en el nombre se indica si es una voz de hombre o de mujer.

Por ejemplo para cambiar la voz de nuestro ejemplo por la segunda voz seria:

var utterance = new SpeechSynthesisUtterance(); 
utterance.text = "hola mundo"; 
utterance.voice = speechSynthesis.getVoices()[1]; 
speechSynthesis.speak(utterance);

Por defecto SpeechSynthesisUtterance se inicia con la voz del idioma en que este configurado el navegador. Si no existe una voz en ese idioma se inicia en inglés.

Interacción del usuario

Una de la limitaciones de este sistema es que necesitas la interacción del usuario. Es decir no puede hablar automáticamente nada mas cargar la web, necesita hablar como respuesta a una interacción del usuario. Por ejemplo pulsar un boton:

<html>
<body>
    <button onclick="speak()">HABLA!</button>
</body>

<script>
    function speak(){
        console.log("Speaking...");

        var utterance = new SpeechSynthesisUtterance();
        utterance.text = "hola mundo";    
        speechSynthesis.speak(utterance);
    }
</script>
</html>

Podéis estar tentados a escuchar un evento mousemove para lanzar la función speak(), no va funcionar, es necesario que el usuario haga click en la web, pulse una tecla o la pantalla (si es táctil) para poder usar el síntesis de voz.

Con eso está todo. Ya sabéis usar lo básico de la síntesis de voz en el navegador.

No todo es perfecto

Ahora siento aguar la fiesta pero no todo es tan bonito. Este sistema aún tiene varios problemas.

  • Falta de entonación. La voz es muy monótona. Carece de las inflexiones del lenguaje  hablado. Por otro lado aunque pudiera entonar habría que indicarle la entonación de alguna forma ya que el lenguaje escrito, quitando las exclamaciones e interrogaciones, no aporta información sobre la entonación y muchas veces es necesario entender el significado del texto. Una solución sería implementar SSML, en teoría están en ello.
  • En textos largos se sufren pausas impredecibles.
  • Pausas cuanto reproduces dos frases en dos llamadas a speak() seguidas. Lo ideal es que se reprodujeran unas detrás de otras sin que se note.

Aun así es un avance enorme para las interfaces habladas.

En mi canal de youtube tienes un vídeo describiendo esto mismo:

Haz click para ver el vídeo en youtube

Elegir un buen vecino

Gran parte de las metaheurísticas y heurísticas tienen el paso «Elegir un nuevo vecino/solución» pero no entran mucho en detalle de cómo elegirlo. La papeleta generalmente se resuelve eligiendo el vecino con el mejor fitness o uno aleatorio. Pero no son las únicas estrategias y dependiendo el tipo de espacio de búsqueda tampoco son las mejores. Vamos a ver algunas alternativas.

¿Qué es un vecino? La respuesta depende del espacio de búsqueda y el tipo de problema y la función usada para «generar» a los vecinos. La forma más generica de definirlo que se me ocurre seria: «Son vecinos de una solución S todas aquellas soluciones que se pueden alcanzar desde S». En algunos casos queda claro quienes son los vecinos, por ejemplo en un grafo. En otros la definición de que es un vecino se va a tener que ajustar como un parámetro más del algoritmo. Por ejemplo cuando definimos el vecino de una solución como todas aquellas soluciones que estén a una distancia igual o menor que d. En este caso d se convierte en un parámetro más a tener en cuenta.

Hay que distinguir entre dos tipos de vecindarios:

  • Poco poblados: cuando el número de vecinos es limitado y podemos calcular el fitness de todos. Suelen ser los vecindarios asociados a problemas combinacionales o a valores discretos. Eso no quiere decir que este tipo de problemas no puedan crecer tanto que se conviertan en el siguiente tipo de vecindario. Ojo al detalle de poder calcular el fitness, si la función que lo calcula es muy costosa puede resultar más rentable tratarlos como si fueran vecindarios muy poblados.
  • Muy poblados: cuando el número de vecinos es infinito o tan grande que es imposible (o su coste en tiempo es demasiado alto) recorrerlos todos. Generalmente corresponde a espacios de soluciones continuos.

Antes de empezar con estrategias  complicadas empecemos por la  y más simple y menos costosa que además funciona en ambos tipos de vecindarios. Elegir un vecino cualquiera al azar. El problema es que puede retrasar mucho la convergencia a un óptimo.

Las estrategias son distintas dependiendo del tipo de vecindario. Vamos a empezar por los vecindarios poco poblados. En este caso las estrategias más simple que se nos puede ocurrir es la de escoger el mejor: de todas las opciones buscamos la que tiene mejor fitness y la elegimos. El problema de asta estrategia es que dificulta la exploración. Pero  por otro lado reduce el tiempo que cuesta llegar al óptimo, aunque aumenta el riesgo que sea un óptimo local. Un pequeño cambio puede solucionarlo. Elegimos una al azar pero no todas tienen la misma probabilidad sino que la probabilidad de seleccionar una solución es proporcional a su fitness.

Para los vecindarios muy poblados podemos hacer un truco para seleccionar los vecinos como si fueran vecindarios poco poblados, elegimos n vecinos al azar y luego aplicamos la selección sobre esos n vecinos como si fueran los únicos del vecindario.

En el caso de espacios de soluciones continuas se suelen elegir como vecinos cualquier solución que esté a una distancia D o menor. Pero esta es la versión más simple, en lugar de elegir todos los vecinos a una distancia D con igual probabilidad podemos hacer que sea más probable seleccionar los que más cerca están o los más lejanos o los que estén a una distancia intermedia. Incluso fijar una distancia mínima. Jugando con estos valores podemos alterar el comportamiento del algoritmo (exploración/convergencia) sin modificar sus valores.

Otra forma de mejorar la selección de vecinos puede ser priorizar la dirección en la que antes ya has encontrado una buena solución esperando que sigamos mejorando en esa dirección. Por ejemplo supongamos que hemos ido del punto (5, 5) al (6, 8). Eso significa que hemos sumado el vector (1, 3). Lo primero que podríamos hacer es mirar el punto (7, 11) = (6, 8)+(1, 3). Es decir repetir el mismo paso y a partir de ahí mirar cerca de ese punto. El problema de hacerlo así es que acabamos repitiendo pasos iguales cuando realmente lo que nos interesa es solo la dirección. ¿Cómo extraerla?. Dividimos cada componente del vector por la distancia recorrida. El vector que hemos sumado ha sido (1,3). La distancia es la raíz cuadrada de la suma del cuadrado de cada elemento. SQRT(1^2+3^2) = 3.1622… Así que la dirección sería (1/3.1622, 3/1622) = (0.31, 0.93). Ya lo tenemos. Ahora podemos avanzar la distancia que queramos en esa dirección. Solo hemos de multiplicar la distancia por cada uno de los valores del vector dirección. Podemos avanzar en esta dirección hasta que deje de mejorar.

Pero estos cálculos pueden ser usados de otra manera. Si elegimos varios vecinos al azar y dividimos lo que mejora la solución entre la distancia del paso tendremos una manera de estimar en qué dirección las soluciones mejoran más rápido. Estamos calculando una aproximación del gradiante. En este caso podemos priorizar los que más rápido varíen.

Hay una versión de esta selección que se usaba originalmente para la metaheurística hill climbing que no requiere cálculos. Si tenemos una solución con múltiples coordenadas modificamos una a una hasta que deje de mejorar en esa coordenada. En el ejemplo anterior sería el caso de usar el vector dirección (1,0) hasta que deje de mejorar y luego usar (0,1). Tiene la desventaja de que puede quedarse atrapado cuando los mejores vecinos están en las diagonales.

Una última mejora es guardar un histórico de soluciones ya seleccionadas para evitar elegir una ya elegida o muy cercana (lo que sería el equivalente a andar en círculos). Según el coste en memoria de almacenarlas y en tiempo de compararlas puede ser mejor almacenar solo las últimas. Esta opción solo es válida cuando la selección del siguiente vecino es determinista, por ejemplo eligiendo el de mayor gradiante o cuando se inspeccionan todas las opciones y lo más probable es que se elija el mismo vecino la última vez que se «visitó» esa solución. Guardar información de los vecinos ya visitados no puede ahorrar «dar vueltas» y reducir el coste computacional.

Templado Simulado

El templado o cocido o temple o recocido simulado es una metaheurística inspirada en el templado (o cocido o temple…) de metales (en algunos sitios hablan de espadas samuráis para hacerlo parecer más interesante. Como si una metaheurística necesitara algo más para parecer interesante…mejor no respondáis). La idea es que durante el templado los átomos van colocándose en las posiciones de menor energía aunque a veces pueden moverse a una de mayor energía. Este caso depende de la temperatura a la que esté en el material y a mayor temperatura más probable es que ocurra. Tampoco todos los saltos son igual de probables, a mayor diferencia de energía también es menos probable que ocurra.

Sonará ridículo, pero uno de los problemas que he encontrado con este algoritmo es que se suelen usar términos químicos para describirlo lo cual resulta confuso para los pobres programadores que no estamos acostumbrados a ellos. Así que dejando de lado el modelo real en que se inspira, el algoritmo es similar a la búsqueda aleatoria con el añadido de que tiene cierta probabilidad de aceptar una solución cuyo valor sea peor que la actual. Es decir, que las soluciones peores que la actual no se descartan siempre, se deja al azar si se conserva la actual (la mayoría de las veces) o se remplaza por la nueva solución. Esto le permite escapar de óptimos locales explorando zonas que de otra forma no visitaría. Eso sí, para evitar ir saltando de un lado a otro a lo loco y lograr converger en un máximo la diferencia entre los valores de la función fitness no puede superar un límite que se reduce con cada iteración con lo que es menos probable que se elija una solución peor que la actual. La formula que se aplica es que una solución de fitness f’ peor que f se acepta siempre y cuando:

e ^ (f-f’/ Ti ) > rnd(0,1)

Podemos ver que se usa e ^ x para calcular la posibilidad de que se elija esa solución. Para ello calculamos la diferencia entre ambas soluciones y la dividimos entre la temperatura actual. Hay que tener en cuente que este caso solo sirve cuando busquemos el mínimo (f’ es peor si f’ > f) pero si buscamos el máximo debería de ser f’-f  ( f’ es peor si f’ < f). con esto debería de darnos siempre un resultado negativo ya que si f’ es mejor que f se elegiría directamente y no llegaríamos a este punto.

if(newFitness  Math.random()){
    this.cords = newCords;
    this.fitness = newFitness;
}

Si nos fijamos en la gráfica de la función e ^ x entre -5 y 0 vemos que su valor decrece según aumenta la diferencia entre ambos valores. También podemos ver, que al estar dividida por la temperatura, cuanto mayor sea la misma más «tolerante» es con la diferencia. Como según se itera el algoritmo la temperatura se reduce cada vez es menos probable elegir una solución peor que la actual. Según disminuye la temperatura y el comportamiento del algoritmo se asemeja más a una búsqueda aleatoria.

ex

Gráfica de e^x para x < 0

Función de enfriamiento

La función de enfriamiento es la operación que se ocupa de reducir el valor de la temperatura cada iteración. Es más importante de lo que parece ya que es la temperatura la que permite saltar a soluciones peores y explorar el espacio de soluciones. Las dos más habituales son:

Restar un valor que sea muy pequeño «casi cero»

Ti = To – k * i     =     Ti = Ti-1 – k

Tiene la ventaja de que se puede calcular muy rápidamente. El problema es que es demasiado lineal y no suele dar tan buen resultado.

Multiplicar por un valor menor que uno pero cercano a él. O sea que sea «casi 1».

Ti = T0 * k ^ i    =   Ti = Ti-1 * k

Es rápida de calcular y da buen resultado. Variando el valor de k variamos «el comportamiento» alargando o acortando el rápido descenso inicial o lo «exploradora» que sea la metaheurística.

Algunas más complejas:

Ti = T0*k*i

Ti = (To/imax) * i

Ti = To/(1+k*ln(1+i))

La temperatura controla el umbral de aceptación de una variable. Si es alta es más fácil que una solución peor «pase el filtro». Así que lo ideal sería poder adaptarla según lo necesite el algoritmo. Acelerar su descenso, retrasarlo e incluso invertirlo. Para que el algoritmo converja en una solución es necesario que la tendencia general de la temperatura sea descender pero puede sufrir momentos puntuales de aumento. En concreto lo ideal sería que la temperatura aumente cuando esté intentando «escapar» de un óptimo local. ¿Como sabemos cuándo es eso? Sencillo, ocurre cada vez que se elige una solución peor que la actual. Nos podemos imaginar que la solución

Siendo

fbest la solución seleccionada hasta ese momento

f el valor de fitness para la solución elegida

Ti la temperatura calculada para la iteración i por alguno de los métodos anteriores

T’ = (1+(f-fbest/f))*Ti

Como f solo puede ser igual o mayor (es peor) a fbest. La formula actúa compensando la disminución de la temperatura cuando  la solución empeora. De tal forma que combina ciclos de descenso con otros de ascenso aunque en teoría tendencia general es que la temperatura disminuya. ¡Ojo! Que es en teoría. Puesto que al subir la temperatura aumenta la probabilidad de que seleccione soluciones peores y cada vez que selecciona una soluciones peor aumenta la temperatura puede llegar realimentarse hasta que el aumento de temperatura se dispara.

Al final yo he optado por:

T’ = (1+(f-fbest/f))*Kinc + Ti

Al ser una suma se frena el aumento de temperatura y el parámetro Kinc permite controlar esta variación.

Aunque con los parámetros iniciales adecuados puede encontrar una correcta aproximación al óptimo global su desempeño en espacios de búsqueda muy grandes o con muchas dimensiones no suele ser muy bueno. También se usa como optimizador local.

Puedes encontrar el código aquí.

Random Search

Esta metaheurística tiene la ventaja de que es sencilla de entender y de aplicar. En su forma más simple consiste en partir de un punto aleatorio del espacio de soluciones, elegir aleatoriamente una solución cercana, si es peor se elige otra, si es mejor movernos a ella y volver a elegir otra solución desde ahí.

La implementación es fácil y su ejecución es rápida o al menos hasta donde lo permita el cálculo del fitness de la solución elegida.

var newCords = this.newSolution(this.cords.slice(0));
var newFitness = this.model.calculateFitness(newCords);
if(newFitness > this.fitness){
  this.cords = newCords;
  this.fitness = newFitness;
}

Por desgracia su desempeño solo es bueno en espacios de búsqueda sencillos. Es fácil que se quede atrapada en un óptimo local. Todo depende del tamaño del área en que se busca la nueva solución. Un tamaño muy grande hace que le cueste mucho más converger, uno muy pequeño causa que se quede atrapada en máximos locales. Y no hay una buena solución para todos los problemas, los valores dependen del espacio de búsqueda. Ahora es cuando estaréis pensando: «¿Y si hacemos el tamaño del área de selección variable?». Mala suerte, llegáis unas cuantas décadas tarde. Hay varios algoritmos que usan esta táctica.

Primero un detalle, el «Tamaño del área de selección» se le llama también «tamaño del paso» ya que sería el símil a lo que puede avanzar en cada iteración por el espacio de búsqueda (generalmente hay tendencia a representar el espacio de búsqueda como montañas y a nuestro algoritmo caminando por ahí).

Volviendo a las búsquedas aleatorias con «paso de tamaño variable». Hay varias estrategias, unas intentan calcular el tamaño del paso analizando la función a optimizar, otros van ajustando el valor de forma dinámica. La forma más sencilla de hacerlo es simplemente ir aumentando el tamaño del paso cada vez que compruebas un vecino y es peor que la solución actual. Una vez encuentras una solución mejor vuelves al tamaño de paso inicial. Con cuidado de no superar un tamaño máximo de paso para evitarnos problemas como superar el espacio de búsqueda.

var newCords = this.newSolution(this.cords.slice(0));
var newFitness = this.model.calculateFitness(newCords);
if(newFitness > this.fitness){
  this.cords = newCords;
  this.fitness = newFitness;
  this.step = this.parameters.step;
} else { //variamos tamaño del paso
  this.step.map(function(step){return step*this.parameters.increaseStep}, this);
}

Aunque se puede usar como optimizador global suele tener mejor desempeño como optimizador local que parte de los resultados obtenidos por un optimizador global.

Hay algunas modificaciones interesantes que mejoran algunos aspectos.

Por ejemplo, al ser el punto de origen aleatorio solo explora una pequeña parte del espacio de búsqueda. La forma más fácil de resolverlo es ejecutarlo varias veces con puntos de inicio diferentes y quedarse con la mejor. Esto permite su uso como optimizador global. Además lo hace fácilmente paralelizable. A este algoritmo se le denomina «con reinicio».

El código completo esta en este repositorio de github.