Metadatos y usabilidad

Seguimos intentando convencernos de las ventajas del uso de los metadatos. El otro día, buscando en Google por «metadatos» y «usabilidad» me encontré un trabajo con la siguiente frase al comienzo: «Encuéntrame, descárgame y úsame. Déjate luego seducir y vuelve a mí una y otra vez. Yo por mi parte usaré mucho, mucho sentido común y trataré de sorprenderte cada día«.

Supongo que algunos ya saben que el autor de esta frase es el casi omnipresente Ricardo Baeza-Yates, así que poco más que hablar, a leer el artículo que da título a este post.

El idioma español y las conferencias TREC

logo de la primera conferencia TREC

logo de la primera conferencia TRECCuenta Donna K. Harman en el capítulo séptimo de ‘TREC: Experiment and Evaluation in Information Retrieval‘ que a partir de la conferencia TREC-3 comenzaron a probarse distintos sistemas de recuperación de información implementados en colecciones de documentos multilingües. Hasta ese momento, como es fácil suponer solo se había empleado el Inglés.

En esa conferencia, cuatro grupos trabajaron con una colección de 58.000 documentos procedentes de un periódico de Monterrey llamado El  Norte (aproximadamente 200 megabtytes de tamaño). Los grupos usaron búsquedas simples y analizaron el comportamiento del sistema con un total de 25 preguntas. Algunos de estos grupos (de las universidades de Cornell y Amherst -Massachusetts), trasladaron sus sistemas directamente, con la única salvedad de los ficheros de palabras vacías que ahora iban a ser términos en español. Los otros dos grupos (Dublin -«la del Core»- y Michigan) usaron desarrollos adaptados al nuevo idioma, modificando la primera de ellas el original algoritmo de lematización (‘stemming‘) propuesto por Porter.

El principal resultado de este experimento fue la facilidad de portabilidad de las aplicaciones y técnicas de recuperación de información a textos escritos en otro idioma, el nuestro en este caso. En el informe de la Universidad de Cornell se decía que bastaban unas pocas horas de trabajo para garantizar la misma efectividad de los sistemas. Estas conclusiones iniciales fueron refrendadas posteriormente en las conferencias TREC-4 y TREC-5. La inmortal lengua de Miguel de Cervantes está al mismo nivel que la de Shakespeare, por tanto.

Utilidad lineal.

medidas de la recuperación de información la utilidad lineal

La usabilidad lineal es una medida de la recuperación de información que, esencialmente asume que la presencia de documentos relevantes en la respuesta de un sistema de recuperación de información a una determinada pregunta debe tomarse como un rédito a favor del sistema, al mismo tiempo que los documentos no relevantes deben considerarse como un débito. Por lo tanto, esta medida establece su valor favoreciendo el acierto y penalizando al mismo tiempo el desacierto
Seguir leyendo…

El secreto de Google y el Álgebra Lineal

google y el álgebra lineal

google y el álgebra lineal

La base matemática subyace en el algoritmo de alineamiento de Google (Pagerank en un principio, ahora podríamos hablar de ese algoritmo y múltiples extensiones). El algoritmo lleva a cabo una serie de cálculos recursivos que dificultan su entendimiento y que precisa de simplificaciones matemáticas. Una de ellas es el trabajo «El secreto de Google y el Álgebra Lineal» de Pablo Fernández Gallardo, profesor de la Universidad Autónoma de Madrid que le sirvió al autor para obtener el quinto Premio SEMA a la Divulgación en Matemática Aplicada, otorgado por la Sociedad Española de Matemática Aplicada en septiembre de 2004. Ha sido publicado en el Boletín de la Sociedad Española de Matemática Aplicada 30 (2004), 115-141. En enlace anterior podemos ver la versión en formato de diapositivas y haciendo clic sobre la imagen de la diapositiva accedemos al texto del artículo.. .

Un grupo de amigas y Berners-Lee.

Esta mañana recibía el agradable comentario que os acompaño:

«Hola, javima: Un grupo de amigas estamos buscando información sobre diseño paginas web cuando encontramos tu blog. Tu título, Textffiles: memoria de Internet., nos ha gustado y lo hemos comentado. Estamos tratando de escribir algo relacionado con diseño paginas web para un proyecto de internet. Muchas gracias por permitirnos aprender de ti con tu excelente blog.»

Aprovecho para darle las gracias a «este grupo de amigas» y de paso presentaros una breve referencia al trabajo ‘The World Wide Web: A very short personal history‘ escrito por Tim Berners-Lee, y ya de paso -no todo va ser historia – vaya a terminar este blog en una especie de serie Cuéntame que te pasó – podemos leer también la transcripción del discurso del mismo Tim en la celebración en el MIT del 35 aniversario del Computer Science and Artificial Intelligence Laboratory.

El Modelo del Espacio Vectorial: similitud entre vectores.

representación de la función del coseno para calcular la similitud de dos vectores de documentos en recuperación de información

En algunas partes de esta web hablamos de Gerad Salton y de «su Modelo del Espacio Vectorial que implementan la mayoría de los motores de búsqueda lo implementan como estructura de datos y que el alineamiento suele realizarse en función del parecido (o similitud) de la pregunta con los documentos almacenados. Viniendo hacia el trabajo me he parado a pensar que igual muchos no saben cómo funciona realmente este modelo y que no sería nada malo dedicarle una pequeña serie de posts para explicarlo. Vamos a ello.

La idea básica de este modelo reside en la construcción de una matriz (podría llamarse tabla) de términos y documentos, donde las filas fueran estos últimos y las columnas correspondieran a los términos incluidos en ellos. Así, las filas de esta matriz (que en términos algebraicos se denominan vectores) serían equivalentes a los documentos que se expresarían en función de las apariciones (frecuencia) de cada término. De esta manera, un documento podría expresarse de la manera d1=(1, 2, 0, 0, 0, … … …, 1, 3) siendo cada uno de estos valores el número de veces que aparece cada término en el documento. La longitud del vector de documentos sería igual al total de términos de la matriz (el número de columnas).

De esta manera, un conjunto de m documentos se almacenaría en una matriz de m filas por n columnas, siendo n el total de términos almacenamos en ese conjunto de documentos. La segunda idea asociada a este modelo es calcular la similitud entre la pregunta (que se convertiría en el vector pregunta, expresado en función de la aparición de los n términos en la expresión de búsqueda) y los m vectores de documentos almacenados. Los más similares serían aquellos que deberían colocarse en los primeros lugares de la respuesta.

¿Cómo se calcula esta similitud? Disponemos de varias fórmulas que nos permiten realizar este cálculo, la más conocida es la Función del Coseno, que equivale a calcular el producto escalar de dos vectores de documentos (A y B) y dividirlo por la raíz cuadrada del sumatorio de los componentes del vector A multiplicada por la raíz cuadrada del sumatorio de los componentes del vector B.

representación de la función del coseno para calcular la similitud de dos vectores de documentos en recuperación de información

No hay que asustarse a la hora de oir hablar de «producto escalar de dos vectores», ya que se calcula multiplicando componente a componente y sumando los productos. Así, si disponemos de los vectores de documentos A (1, 0, 1, 0, 1, 0) y B (1, 0, 1, 1, 0, 0) su valor de similitud según la función del Coseno se calculará tal como podemos ver en la siguiente tabla:

tabla de ejemplo de cálculo de la función de similitud del coseno

De esta manera tan sencilla se calcula este valor de similitud. Como es obvio, si no hay coincidencia alguna entre los componentes, la similitud de los vectores será cero ya que el producto escalar será cero (circunstancia muy frecuente en la realidad ya que los vectores llegan a tener miles de componentes y se da el caso de la no coincidencia con mayor frecuencia de lo que cabría pensar). También es lógico imaginar que la similitud máxima sólo se da cuando todos los componentes de los vectores son iguales, en este caso la función del coseno obtiene su máximo valor, la unidad. Lo normal es que los términos de las columnas de la matriz hayan sido filtrados (supresión de palabras vacías) y que en lugar de corresponder a palabras, equivalgan a su raíz ‘stemmed’ (agrupamiento de términos en función de su base léxica común, por ejemplo: economista, económico, economía, económicamente, etc.). Generalmente las tildes y las mayúsculas/minúsculas son ignorados. Esto se hace para que las dimensiones de la matriz, de por sí considerablemente grandes no alcancen valores imposibles de gestionar. No obstante podemos encontrar excepciones a la regla general, tal como parece ser el caso de Yahoo!, que no ignora las palabras vacías.

Para finalizar, la del coseno no es la única función de similitud. Existen otras, entre las que destacan las de Dice y Jaccar, pero que pueden resultar algo más engorrosas no sólo de calcular sino más bien de interpretar y que por tanto son menos aplicadas en Recuperación de Información

Precisión y exhaustividad normalizadas

Entre las medidas alternativas a la relevancia encontramos la Exhaustividad Normalizada como propuesta de diversos autores. Casi todo el mundo reconoce que el mayor problema de las medidas basadas en la relevancia es la alta dosis de subjetividad inherente a su determinación. Otro de los problemas que conlleva su uso reside en la secuencialidad de la lectura de los resultados. Korfhage avisa: “los sistemas de recuperación de información típicos presentan los resultados formando una secuencia de documentos. Incluso en aquellos sistemas que no presentan así la información, el usuario suele examinar los documentos secuencialmente» (Korfhage, 1997). Inevitablemente, este modo de consulta afectará al juicio que el usuario ha de llevar a cabo sobre la relevancia o no de los documentos siguientes.

En la práctica, todos los usuarios de estos sistemas sufren este problema cuando, al consultar dos documentos más o menos igual de interesantes y relacionados con una materia, centran su atención de forma preferente en el primero de ellos, aunque el segundo no desmerezca en nada al anterior. Algo parecido acaece cuando un usuario realiza una búsqueda y los primeros documentos recuperados resultan relevantes con el tema de su interés. En esta circunstancia, el usuario tendrá una sensación positiva y se considerará satisfecho, no preocupándose por el número de documentos no relevantes que también recupera (que puede llegar a ser muy grande). La situación contraria también ocurre cuando la presencia de los documentos no relevantes al principio de la respuesta es masiva. En este caso la sensación de frustración va a ser de gran consideración, independientemente de que en el global de la búsqueda se entreguen muchos más documentos relevantes que no relevantes.

Estas reflexiones han propiciado el desarrollo de medidas que tomen en consideración la secuencia en la que los documentos son presentados a los usuarios. El primer trabajo conocido corresponde a Rocchio (citado en [Rijsbergen, 1999] y en [Moschitii, 2003]), quien define una exhaustividad normalizada y una precisión normalizada para sistemas que presentan los documentos alineados según un determinado criterio de clasificación y donde no afecte el tamaño de la muestra analizada. El autor define un “sistema ideal donde los documentos relevantes se recuperan antes que los documentos no relevantes y se puede representar en un gráfico la evolución de la exhaustividad de esta operación de recuperación de información”. 

e-p normalizadas
Ejemplo de cómo la Exhaustividad normalizada queda comprendida entre el peor y el mejor resultado posible. Fuente: Rijsbergen, C.J. Information Retrieval. [En línea]. Glasgow, University, 1999.[Consulta: 29 noviembre 2004]

Si en una base de datos de 25 documentos se sabe que cinco de ellos son relevantes, y que han sido devueltos por el sistema al realizar una búsqueda en las posiciones {3, 5 , 10, 11, 15}, se puede representar un gráfico etapa a etapa (tal como muestra la imagen anterior). La exhaustividad de esta búsqueda alcanza el valor de 0.2 (1 documento relevante recuperado dividido entre 5 documentos relevantes de la colección) al analizar el tercer documento (hasta entonces vale cero). Cada vez que se analice un documento relevante, el valor de la exhaustividad aumentará, hasta llegar a la unidad (en este caso, en el documento 15), permaneciendo constante hasta el último documento recuperado, ya que todos los relevantes ya han aparecido. Tal como se desprende de la comparación con la gráfica de la mejor búsqueda posible (cuando se presentan los cinco documentos relevantes en las cinco primeras posiciones de la secuencia) o con la peor búsqueda posible (cuando se presentan los cinco documentos relevantes en las cinco últimas posiciones de la secuencia), resulta muy intuitiva, tal como se refleja en la anterior imagen.

Para Korfhage, “el área comprendida entre la búsqueda actual y la gráfica ideal representa una medida de la ejecución del SRI” (Korfhage, 1997). Esta medida se calcula restando al valor de la unidad el resultado de dividir el valor de esta área por (n1 * (N – n1)). En el ejemplo anterior, el valor del área es 29, por lo que el valor de la exhaustividad normalizada, aplicando la anterior fórmula, será el resultado de la siguiente operación: (1 – 21/(5 * (25 – 5)) = (1 – 0.21) = 0.79

La precisión normalizada se define de manera análoga: “mientras la precisión ordinaria es una medida exactamente definida, esta medida depende del conocimiento del número total de documentos relevantes” (Korfhage, 1997). Rijsbergen propone como método para su cálculo “restar a la unidad el resultado de dividir el valor de esta área por el valor del área existente entre la búsqueda ideal y la peor búsqueda” (Rijsbergen, 1999). En el ejemplo propuesto, el resultado de esta precisión normalizada sería (1 – 21/(95 – 15)) = (1 – 21/80) = 0.7375. Rijsbergen destaca algunos aspectos de estas medidas: “ambas presentan un comportamiento consistente, es decir, cuando una se aproxima a cero la otra se aproxima a la unidad. Ambas medidas asignan valores distintos de peso a los documentos recuperados en la secuencia, la precisión los asigna a los iniciales y la exhaustividad asigna un valor uniforme a todos los documentos relevantes. En tercer lugar, estas medidas pueden entenderse como una aproximación de la precisión y exhaustividad promedio y, por último, los problemas que surgían en la determinación de la longitud esperada de búsqueda (por la posición de los documentos relevantes), son inexistentes en este caso”.

Bibliografía.

(Korfhage, 1997) Korfhage, R.R. Information Retrieval and Storage. New York: Wiley Computer Publisher, 1997.

(Moschitti, 2003) Moschitti, A. ‘A study on optimal parameter tuning for Rocchio Text Classifier’. ECIR 2003 [En línea][Consulta: 29 noviembre 2004]

(Risjbergen, 1999) Risjbergen, C. J. Information Retrieval. [En línea]Glasgow, University, 1999.[Consulta: 29 noviembre 2004]

‘Google bombing’

bombardeo a google - google bombing

bombardeo a google - google bombingEn los últimos meses hemos asistido al nacimiento de un nuevo término conocido como ‘Google bombing‘ (expresión que se puede traducir como «bombardeo a Google»). Este «bombardeo» consiste en introducir enlaces (ojo, de forma coordinada) a un mismo sitio web dentro de varias páginas que gozan de cierta popularidad en el buscador (páginas con Page Rank alto o relativamente alto), con el objeto de que ese sitio web aparezca en los primeros lugares de la respuesta del motor, ya que Google clasifica los documentos devueltos según su «popularidad», y si páginas que gozan de cierta popularidad recomiendan en bloque una misma página, pues esta última se convierte (por propiedad «multi-transitiva» podríamos decir) en una nueva página popular.

Espero que hayas seguido leyendo hasta aquí y que no te duela la cabeza mucho, básicamente porque ahora llega lo mejor. Si bien puede parecer normal que varios administradores de sitios web recomienden una misma página, lo que caracteriza a este fenómeno (al «bombardeo») es que ese enlace al unísono se lleva a cabo por medio de la inserción de una frase escrita en tono de broma en la página que recomienda, empleándose ese texto para enlazar hacia la otra página. ¿Qué hay de raro en ello?, pues, por ejemplo, puedes poner en tu página personal, al final y escrito de forma más o menos disimulada para no mezclar este enlace con el resto del contenido de la página, un texto que diga «Obviously, I think too that George Bush is a miserable failure» (parafraseando lo que dijo hace tiempo el candidato demócrata John Kerry sobre el POTUS). Este texto «casi oculto» te traslada a la biografía de George W. Bush, 43º Presidente de los Estados Unidos de América, uno de los peores de la historia.

La gracia del «bombardeo» reside precisamente en que si vamos a Google e insertamos la búsqueda «miserable failure«, la primera página devuelta es esa biografía. Y lo más chocante a primera vista es que en esa página no aparece ni por asomo esa expresión (que podría traducirse como «miserable fracasado», más concretamente en política exterior, tal como decía Kerry). ¿Qué está pasando? ¿Falla Google? ¿Se ha descubierto la manera de enturbiar la gloriosa vida de este buscador?. En realidad no pasa nada más que lo que tenía que pasar, Google es capaz de recomendar la visita a sitios que ni siquiera ha visitado o que no poseen los términos de la ecuación planteada (a la vista está). ¿Por qué se atreve a hacerlo?, básicamente porque el buscador confía en la credibilidad de los administradores de sitios que llevan a cabo estos enlaces y si los mismos deciden «engañarle», pues el motor cae en la trampa sin ningún pudor y de forma irremediable.

Pero la gracia del «bombardeo» no se queda ahí. En este caso, la contribución de mi página es escasa y tardía a este «bombing». Ha habido otros antes, uno famoso dedicado a un «hacker sin futuro ni imaginación» que terminó recibiendo una vista del FBI y, como no podía ser de otro modo, a Bill Gates a quien enlazaban desde el texto de una archiconocida canción de los Rolling Stones), porque ya se encargaron los administradores de sitios webs mucho más populares (el cineasta Michael Moore a la cabeza), de provocarlo. Posteriormente, alguno de estos famosos personajes deja «caer» esta noticia a un periodista y rápidamente todas las televisiones del mundo lo están emitiendo, ante el gran impacto mediático que tiene este buscador y las personas involucradas.

¿Qué hacer al respecto? Mi opinión personal es que nada debe hacerse y que Google no debe corregir su algoritmo para evitar este problema, entre otras muchas razones porque ¿alguien en su sano juicio piensa que George W. Bush no es un pobre FRACASADO miserable? No obstante, se trata de una moda, y como tal desaparecerá y dejará sitio a otra nueva, ya sabemos que el tiempo en la red es cuestión de eso, de poco tiempo. Otro día hablaremos de Page Rank y de toda la serie de trucos que se vienen llevando a cabo para ganar «popularidad» ante este algoritmo, eso ya es otro cantar.