Entradas etiquetadas como ‘Algoritmo’

El algoritmo de los cupidos 2.0

Tiempo ha que Cupido disparaba sus flechas más o menos ciegamente. Como todos en estos tiempos, hasta el dios del amor se ha modernizado y actualmente los portales de citas o encuentros por internet se han convertido en una herramienta de auxilio al niño alado cada día más utilizados y cada vez más lucrativos para sus creadores. Pero, ¿como asignan las parejas dichos portales? ¿actúan ciegamente como el dios Cupido? Lo cierto es que no y que, dada la gran cantidad de gente que se apuntan a ello, es necesario utilizar algoritmos que propongan parejas de forma eficaz, con lo cual se pretende que la mayor parte de los usuarios queden satisfechos.

Naturalmente cuanto más gente se apunte a un portal concreto, más posibilidades existirá de encontrar la persona adecuada para alguien nuevo que se apunte, pero, a la vez, más difícil será manejar la cantidad de datos necesarios para realizar los emparejamientos. Por lo tanto, es necesario diseñar un procedimiento que permita determinar el tipo de datos que hay que saber de cada persona y, después, en función de dichos datos, tratar de realizar tantos emparejamientos satisfactorios como sea posible.

Afortunadamente hay un charla TED que nos explica cómo se hace esta asignación. Para quien no lo sepa TED  (copiando de la wikipedia) «es una organización sin ánimo de lucro dedicada a las «Ideas dignas de difundir» (del inglés: Ideas worth spreading). TED es ampliamente conocida por su congreso anual (TED Conference) y sus charlas (TED Talks) que cubren un amplio espectro de temas que incluyen ciencias, arte y diseño, política, educación, cultura, negocios, asuntos globales, tecnología y desarrollo, y entretenimiento». Numerosos y muy destacados conferenciantes han participado en las charlas TED. En una de las lecciones TED,  Como decía, en una charla TED Christian Rudder, fundador de uno de dichos portales de citas y encuentros, relata las matemáticas involucradas en el funcionamiento de dicho portal. Ya que métodos de asignación más o menos ciegos (como Cupido) o basados en algoritmos de emparejamiento de grafos como los que hemos contado en alguna ocasión, incluso aquellos métodos que tienen en cuenta preferencias de los participantes, no son válidos dadas las características dinámicas del problema que estamos considerando.

Christian Rudder. Fuente.

Christian Rudder. Fuente.

Veamos qué es lo que nos cuenta Christian Rudder:

En primer lugar, se han de acumular tantos datos como sea posible: hemos de conocer las preferencias de aquellos que se apuntan al portal, se les ha de formular preguntas, pero las preguntas han de tener varias características para que su información sea eficaz: las respuestas a dichas preguntas han de ser o bien un simple o no o un número: han de ser fácilmente cuantificables. Tanto en las preferencias de cada uno como en las características o preferencias que deseamos de nuestro posible pareja. Algunas de dichas preguntas serían: ¿Te gustaría tener hijos algún día? ¿cuántas veces te cepillas los dientes? ¿te gustan las películas de miedo? ¿crees en dios? 

Pero, naturalmente, no todas las preguntas (o las respuestas a ellas) han de valorarse igualmente, algunas son más significativas que otras, así se le pide a los usuarios que clasifiquen la importancia de cada una de las preguntas; por ejemplo, para mi puede ser poco significativo si a alguien le gustan las películas de miedo, pero fundamental que se cepille los dientes al menos tres veces al día (y, a ser posible, que esas veces sean después de las comidas, pero esto no sé si se llega a preguntar).

Así, estos tres elementos para cada una de las preguntas formuladas (la respuesta del usuario, la deseada por su posible pareja y la importancia que le demos a dicha pregunta) son los que alimentan el algoritmo de asignación de parejas. Y lo único que hay que hacer es convertir todas las respuestas en un número por cada pareja potencial, de tal forma que la información más o menos abstracta obtenida de las respuestas se conviertan en algo manejable por el ordenado como es un número. Naturalmente confiamos en que, cuanto mayor sea dicho número, más posibilidades tenemos de construir una pareja adecuada. La pregunta es. ¿cómo construimos dicho número? Y la respuesta es relativamente simple, veámosla con un ejemplo: supongamos que se formulan solo dos preguntas y tratemos de asignar un número a las respuestas de dos parejas para ver cómo de afines son. Las dos preguntas son:

1) ¿Te gustan mucho las historias de Mati?  Y las posibles respuestas son: mucho, bastante, poco, nada.

2)  ¿Eres vegetariano/a? Y las posibles respuestas son o no.

Como hemos dicho antes, también se pregunta sobre la importancia de ese tema a los distintos candidatos. Supongamos que obtenemos estas respuestas:

De la persona a la que queremos asignar una pareja (llamemos 1 a esta persona):

tarjeta1

 

De un posible candidato (llamado A) a emparejarse con 1:

tarjeta2

De otro posible candidato (llamado B) a emparejarse con 1:

tarjeta3

Tratamos de darle un número a las parejas 1-A y 1-B para determinar cuál de las dos es más compatible.

En primer lugar lo que haremos será asignar un valor a las importancias que le damos a las respuestas de los demás. Así si decimos que la pregunta X no es importante, a dicha pregunta le asignamos un valor 0, si es poco importante le asignamos un valor 1, bastante importante, un valor 10, a muy importante (mucho), le asignamos un valor 50 y si decimos que es obligatoria, le asignamos un valor 250.

Así como 1 ha dicho que la pregunta 1 es poco importante, le asignaremos a las respuestas de A y B como máximo ese valor si coincide con los deseos de 1 (que era que le gustaran mucho las historias de Mati). Puesto que 1 ha dicho que la primera pregunta es poco importante (1 punto) y que la segunda es bastante importante (10 puntos) el total al que se puede aspirar por parte de y de B en el grado de satisfacción de  1 es de 11 puntos. De esos posibles 11 puntos consigue 1 en la pregunta 1 puesto que su respuesta cumple los deseos de 1 y 0 en la pregunta 2 puesto que no es vegetariano contrariamente a lo que deseaba 1. Por tanto A  tiene un total de 1 punto sobre 11 (valor_de_A_para_1=1/11). Sin embargo, saca 0 puntos en la primera pregunta ya que no cumple los deseo de (podríamos matizar esto ya que su respuesta no difiere en mucho) y 10 puntos en la segunda pregunta puesto que sí es vegetariano, tal y como deseaba 1, así que obtiene 10 puntos de 11  (valor_de_B_para_1=10/11).

El siguiente paso es hacer lo mismo con respecto a los deseos de y de B. A había dado poca importancia a las dos preguntas, luego lo máximo que se puede alcanzar es 2 puntos. saca 0 puntos en la primera pregunta, pero saca 1 punto en la segunda, así que obtiene un total de 1 punto sobre 2 posibles (valor_de_1_para_A=1/2). Con respecto a los deseos de B, este había otorgado poca importancia a la primera pregunta (1 punto en disputa) y mucha importancia a la segunda pregunta (50 puntos en disputa), de esos 51 puntos posibles, A obtiene solo 1 correspondiente a la primera pregunta, así que tiene 1 punto sobre 51 (valor_de_1_para_B=1/51).

Entonces ya sabemos que para el mejor candidato es B que obtiene 10/11 puntos, mientra que obtiene 1/11, pero desde el punto de vista de Bes un mal candidato puesto que solo obtiene 1/51 puntos ¿Cómo determinamos qué pareja es la mejor? Pues mediante la media geométrica de los dos valores que involucran a cada pareja (la media geométrica de dos valores es la raíz cuadrada del producto de los dos valores). Así a la pareja 1-A le asignamos como valor la raíz cuadrada de (1/11)(1/2) y ese valor es 0,213 y a la pareja 1-B le asignamos la raíz cuadrada de (10/11)(1/51) cuyo valor es 0,133. Luego concluimos que la pareja más factible (con valores muy bajos en este ejemplo) es la pareja 1-A.

Alguien se podría preguntar el porqué de usar la media geométrica en vez de la media aritmética. La razón es que en este tipo de cuestiones, la media geométrica es más fiable; imaginad que tenemos dos parejas, en la primera pareja ambos obtienen una puntuación de 1/3 con respecto al otro y en la segunda pareja se obtienen valores muy desiguales, así uno obtiene una puntuación de 2/2 y el otro un 0/2. Si realizamos la media aritmética de ambas parejas, para la primera queda 1/3 y la segunda 1/2, luego esta última obtiene mejor puntuación, sin embargo, en esa segunda pareja, uno de los individuos ha obtenido un 0 con respecto al otro, lo cual quiere decir que es totalmente incompatible y esa pareja está condenada al fracaso. Si calculamos la media geométrica, eso queda mejor reflejado ya que la media geométrica de la primera pareja es 1/3, mientras que de la segunda es 0, mostrando así la inviabilidad de esta segunda  pareja.

Evidentemente, una vez que se ponga en contacto la pareja asignada por el algoritmo, los miembros de esta deberían poner un poco de su parte y tratar de enamorar al otro por los medios que han existido siempre porque ningún algoritmo sustituirá a una caricia, a una mirada, a un beso…

¿Cuánto os estáis llevando… restando?

–Y te llevas 1, Ven.

–No, no me llevo ninguna, le presto 10 al 1 ¿ves, Sal? –dio el pequeño –El 9 se queda en 8 y ya se puede hacer.

–Que no, Ven –insistió Sal –Que la decena que le prestas al 1, te la llevas y se la regalas al 7…

–Pero, a ver… ¿cuántos os estáis llevando? –era Mati quien acababa de entrar –¿Otra vez jugando a los banqueros?

 

–¡Hola Mati! –saludaron los dos hermanos.

–Hola chicos, ¿en qué estáis?

–Estamos haciendo una resta con llevada –dijo el gafotas –y no nos ponemos de acuerdo… Ven las hace de una forma muy rara…

–Rara, no –protestó el pequeño –Me la ha enseñado mi seño y he sacado muy buena nota en Mates.

–Bueno –intervino la pelirroja –Puede haber varias formas diferentes de hacer una resta con llevadas, distintos algoritmos…

–¿Distintos qué? –preguntó Ven con la cara arrugada como una pasa.

–Distintos algoritmos –repitió ella.

–¿Qué es un algoritmo, Mati? –preguntó Sal mientras se ajustaba las gafotas.

–Un algoritmo es como una receta de cocina –empezó diciendo Mati —Una lista de instrucciones que si se siguen ordenadamente, nos permiten realizar algo, por ejemplo, una resta con llevada.

–Me encanta cocinar –dijo Ven — y restar –concluyó con una enorme sonrisa.

–¿Me explicas tu algoritmo para la resta con llevada, Ven? –le pidió Mati –¿Qué resta estabais haciendo?

–91 menos 78 –dio Ven –Como encima del 8 hay un número más pequeño, el 1, éste le pide prestada una decena al número que está a la izquierda de él, que es el 9, que se convierte en 8, y ya se puede hacer la resta.

–Ese algoritmo es perfecto, Ven –dijo Mati –¿Cuál es el problema, Sal?

–Pues que yo no lo hago así –dijo éste –Yo le daría la decena al 1 y una unidad al 7, que es el que está a la izquierda del 8…

–También es correcto tu algoritmo, Sal –dijo la pelirroja.

–¿Cuál es mejor, Mati? –preguntó el pequeño.

–El que  a cada uno le resulte más fácil –respondió ella sonriendo –¿Os cuento otro?

–¿¿Otro?? –preguntó Ven con los ojos como platos –¡Vale!

–Vamos a hacer un pequeño truco –propuso la gafotas con voz misteriosa –¿Cuál es el número mayor de la resta, el minuendo?

–91 –dijo Sal casi en un susurro.

–Bien, como tiene dos cifras –continuó ella –Para nuestro siguiente truco usaremos un número auxiliar, el 100, un 1 y 2 ceros (por las 2 cifras de 91), o como decimos los matemáticos, 10 elevado a 2, que es 100.

–¿Para que quieres el 100 Mati? –preguntó misterioso y en voz baja Ven.

–Para hacer esto, ya verás…

 

 

–Pues, vaya, rollo Mati –protestó Ven –ahora tenemos una cuenta más difícil…

–Espera, cielo –dijo ésta –Vamos a hacerlas por trocitos y despacio. Primero Vamos a calcular 100 menos el sustraendo. 78. Pero eso es muy fácil: empezamos por el número de la derecha, el 8, y miramos cuánto le falta hasta 10, y al resto de los números a la izquierda, en este caso sólo está el 7, cuánto le falta hasta 9.

 

–Ahora –dijo Mati –sólo nos queda sumar 91 más 22 y restarle 100, pero restarle 100 es sólo borrar el uno que aparecerá en la posición de las centenas… y ¡tachán!

–¡Toma, toma, toma! ¡Cómo mola! –Ven saltaba de emoción.

–¡Me encanta tu algoritmo para la resta con llevada Mati! –gritó Sal –¿Puedo hacer yo una resta con él?

–Claro, cielo –respondió ésta.

–4321 menos 1456 –propuso el pequeño.

–¡Ahí estamos! –dijo Sal.

Paso 1: Buscar el número auxiliar que vamos a usar –dijo Mati.

–10000 –respondió el gafotas –porque el minuendo, 4321, tiene 4 cifras, necesitamos un 1 y 4 ceros.

–Eso es… –añadió Mati.

Paso 2: Completar el sustraendo hasta el número auxiliar, o sea, 10000 –continuó el gafotas –Esto lo hacemos completando la cifra de las unidades, 6, hasta 10 y las otras hasta 9…

 

Paso 3: sumar el resultado al minuendo que era… 4321 –Sal seguía bajo la mirada atenta y de admiración de su hermano.

 

–¡Paso 4: Borrar el primer 1! –gritó Ven –¡Qué chulada!

 

–¡Muy bien, chicos! –Mati sonreía orgullosa.

–¡Me encantan los algoritmos! ¡Me encantan los algoritmos! –Ven saltaba abrazado a Gauss.

–Ya veis –concluyó ésta –Hay varias formas de hacer una misma cosa, lo importante es hacerla y hacerla ordenadamente y bien.

–Hablando de ordenar, Ven –dijo Sal –tenemos que ordenar los juguetes de nuestro cuarto.

–Vamos, chicos, –dijo la pelirroja —os echo una mano y os invito a un helado después.