Neutralizing DNS attack on Wikileaks.

Why Lucene doesn't work properly with structured documents?

Most ranking functions, use a non-linear method to saturate the computation of the frequencies. This is due to the fact that the information gained on observing a term the first time is greater than the information gained on subsequently seeing the same term.

The non-linear method can be as simple as a logarithmic or a square-root function or more complex parameter-based approaches like BM25 k1 parameter. S. Robertson* has described the dangers to combine scores from different document fields and what are the most tipical errors when ranking functions are modified to consider the structure of the documents.

A good example of these errors is Lucene library**. Apache Lucene is a high-performance and full-featured text search engine library written entirely in Java. It is a scalable technology suitable for nearly any application that requires fulltext search. Lucene offers high-performance indexing and has become one of the most used search engine libraries in both academia and industry.

The ranking function is the core of any search engine applied to determine how relevant a document is to a given query. Lucene ranking function is built on a combination of the Vector Space Model (VSM) and the Boolean model of Information
Retrieval. The main idea behind Lucene approach is the more times a query term appears in a document relative to the number of times the term appears in the whole
collection, the more relevant that document will be to the query. Lucene uses also the Boolean model to first narrow down the documents that need to be scored based on the use of boolean logic in the query specification. Lucene is able to deal with document structure and actually implements the necessary functionalities to index structured documents based on fields. To rank these structured documents, Lucene
combines the scores from document fields. The method used by Lucene to compute the score of an structured document is based on the linear combination of the scores for each field of the document:



where



and



As we can see, Lucene’s ranking function uses the square-root of the frequency to implement the non-linear method to saturate the computation of the frequencies, but the linear combination of the tfc(tl, d) values that Lucene implements breaks the saturation effect, since field’s boost factors wc are applied after of non-linear methods are used. The consequence is that a document matching a single query term over several fields could score much higher than a document matching several query terms in one field only, which is not a good way to compute relevance and use to hurt dramatically ranking function performance.

This problem hurt search engine performance where two or more fields are used to represent a document.

Fortunately, Rober Muir, from Lucene Commiters Team, is working on this problem, and hopefully it will be fixed soon. In the meantime, if you need index and retrieve structured documents using Lucene, you can use the BM25F implementation for Lucene that is available at http://nlp.uned.es/~jperezi/Lucene-BM25/

* Robertson, S., Zaragoza, H., and Taylor, M. 2004. Simple BM25 extension to multiple weighted fields. In Proceedings of the Thirteenth ACM international Conference on information and Knowledge Management (Washington, D.C., USA, November 08 - 13, 2004). CIKM '04. ACM, New York, NY, 42-49. DOI= http://doi.acm.org/10.1145/1031171.1031181
** http://lucene.apache.org/java/docs/index.html

La clave es el ranking

En recuperacion de informacion, el modelo mas basico es el modelo basado en logica booleana. En este modelo la relevancia de los documentos se evalua en torno a dos unicos valores: relevante y no-relevante, o lo que es lo mismo verdadero o falso. La logica booleana es lo que se denomina una logica bivaluada, es decir con solo dos valores de verdad, en contraposicion a otras logicas polivaluadas, como por ejemplo la logica borrosa, donde podemos utilizar infinitos valores de verdad.

Los operadores booleanos AND, OR y NOT han sido usados durante mucho tiempo como base para crear lenguajes de consulta sencillos pero a la vez bastante potentes. Un buen ejemplo de lenguaje de consulta basado en logica booleana es SQL, utilizado en bases de datos relacionales.

Las limitaciones del modelo booleano en recuperacion de informacion son evidentes, ya que no nos permite decidir entre dos documentos relevantes cual es mas relevante de los dos a partir de una consulta dada. Por este motivo los buscadores como Google o Yahoo no implemenetan realmente una capa booleana, dejando todo el trabajo a modelos de recuperacion mas complejos basados en tecnicas probabilisticas.

Sin embargo, cuando hablamos sobre buscadores con profesionales que no estan familiarizados con las tecnicas de recuperacion de informacion, suele ser complicado hacerles ver que se tienen que olvidar del modelo booleano. Mucha gente viene del mundo de las bases de datos relacionales que almacenan informacion muy estructurada (nombres de personas, numeros de registro, direcciones, telefonos, cuentas bancarias, etc) y no son capaces de ver que un buscador NO es una base de datos relacional, ya que sigue un modelo basado en informacion escasamente estructurada que se almacena en estructuras de datos no relacionales como son los indices invertidos.

Esto ocurre incluso a nivel de investigacion donde investigadores de otras areas tratan de aplicar tecnicas propias a la recuperacion de informacion sin tener en cuenta adecuadamente las bases sobre las que se disena e implementa un buscador.

En el mundo SEO es tambien facil encontrar este tipo de errores, ya que muchos SEOs son webmasters que llevan mucho tiempo trabajando con PHP y MySQL e incluso implementando buscadores para sus webs con estas herramientas, por lo que les cuesta olvidarse del modelo booleano cuando piensan en optimizar una web.

Por supuesto como en todo en la vida, no se puede generalizar, y hay investigadores, SEOs e ingenieros que son capaces de ir mas alla y aplicar correctamente las tecnicas basicas de recuperacion de informacion.

Una buena manera de evitar caer en este error es asumir que el gran problema de la recuperacion de informacion no es recuperar documentos relevantes, si no ordenarlos en funcion de esa relevancia, y por lo tanto todas las tecnicas que utilicemos para intentar mejorar nuestro buscador deben estar centradas en mejorar nuestro ranking de documentos y no tanto en recuperar mas o menos documentos.

Por muy obvio que parezca lo que explico aqui, es muy facil caer en este error. De hecho, muchas tecnicas que tratan de aplicar Procesamiento de Lenguaje Natural y/o tecnicas basadas en tecnologias de la Web Semantica caen precisamente en este error de principiante. Una buena manera de evitar este problema es preguntarse:

"Como afecta esta tecnica al ranking de documentos que se genera?" lo altera de alguna forma? lo deja igual? lo mejora? lo empeora?

si no tenemos respuesta para estas preguntas, deberiamos pensarnos dos veces el aplicar cambios a nuestro algoritmo de busqueda o a nuestra web, al fin y al cabo ya sabemos que lo que aparezca mas alla de los 10 primeros resultados de un buscador realmente no existe :-)

Calculo de relevancia y usuarios

El calculo de relevancia que realizan buscadores como Google o Bing a la hora de ordenar los resultados correspondientes a una consulta de un usuario es una aproximacion a la relevancia real que cada documento tiene para el usuario que realiza la consulta.

De esta forma los buscadores realmente calculan la probabilidad de que un documento sea relevante o no para una consulta dada, cuanto mas probable sea su relevancia, mas arriba estara en el ranking de documentos que se devuelve al usuario.

Obviamente esta relevancia basada en probabilidad esta muy lejos de lo que seria la relevancia ideal que solo existe en la cabeza del usuario que realiza la consulta y que, para mas complicacion, puede ser distinta para dos usuarios diferentes, con lo cual lo que un usuario considera relevante para una consulta dada, otro puede considerar que no lo es incluso para la misma consulta.

Hoy en dia, el problema de detectar cuando la misma consulta debe devolver distintos resultados en funcion de cada usuario se intenta solventar adivinando cual es el contexto en el que se encuentra el usuario, por ejemplo su situacion geografica.

El ejemplo tipico es la busqueda local. Para la consulta "restaurantes en Santiago" un buscador deberia devolver distintos resultados si el usuario esta en Galicia (Santiago de Compostela) o si esta en Chile (Santiago de Chile).

La idea central es que cuanto mas sepamos sobre el contexto en el que se encuentra el usuario cuando hace la consulta, mas nos aproximaremos a la idea de relevancia que tiene el usuario en su cabeza en ese momento. Si seguimos esta idea la mejor manera de calcular una relevancia adaptada a cada usuario sera que se matengan cuentas de usuario, donde en funcion de las busquedas anteriores podemos saber lo que un usario concreto considera relevante y lo que no. Esto es precisamente lo que hace Google cuando realizamos busquedas personalizadas.

Por otro lado, todos los buscadores, ya sean especializados o no, intentan aproximarse a la idea que tienen sus usuarios de lo que es relevante y de lo que no lo es a traves del analisis de los registros de consultas que se producen durante la interaccion de los usuarios con el buscador, lo que se denominan "query logs".

La informacion estadistica que se extrae de estos registros sirve para "entrenar" las funciones de ranking que usan los buscadores, de manera que se ofrecen los resultados mas relevantes y a la vez mas populares (es decir donde mas gente ha hecho click) en las posiciones mas altas del ranking.

Un ejemplo sencillo de esto seria el siguiente: Imaginemos que nuestro buscador devuelve una lista de 10 documentos para una consulta dada, sin embargo, nos damos cuenta de que un porcentaje alto de usuarios suele hacer click en el tercer resultado, ignorando el primero y el segundo. Asi pues, lo que haremos sera asignar un factor (que puede estar basado en el numero de personas que hacen click en ese resultado) de manera que el resultado mas popular (es decir el que mas gente pincha) pasa de aparecer tercero a aparecer en la primera posicion del ranking para esa consulta.

Un buen articulo para profundizar en este tema es el siguiente (en ingles):

Improving Web Search Ranking by Incorporating User Behavior Information [paper], Eugene Agichtein, Eric Brill, and Susan T. Dumais, ACM SIGIR Conference on Research and Development on Information Retrieval (SIGIR), 2006

De un tiempo a esta parte, la informacion generada por los usuarios de los buscadores se ha convertido en uno de los aspectos mas importantes en la definicion del calculo de relevancia en los buscadores. Actualmente, el buscador que devuelve los mejores resultados no es aquel que tiene los mejores algoritmos, sino aquel que tiene la mejor muestra posible para hacerse una idea de que es considerado relevante por los usuarios y que no.

En mi opinion, la gran ventaja que hace que Google, a dia de hoy, devuelva resultados mas relevantes no es que tenga mejores algoritmos, sino que, dado que es el buscador mas utilizado, tiene mucha mas informacion sobre lo que los usuarios consideran relevante, y por lo tanto es capaz de aproximarse mas a esa funcion ideal de relevancia que los usuarios tienen en la cabeza.

La disciplina surgida a partir de esta idea, se denomina Web Mining, y es sin duda una de las areas mas interesantes hoy en dia en Busqueda Web, no solo por sus implicaciones en el campo de la relevancia, sino tambien por su importancia en temas como marketing en internet y posicionamiento. Una buena forma de introducirse en este mundo es el libro escrito por Fabrizio Silvestri:

Fabrizio Silvestri: Mining Query Logs: Turning Search Usage Data into Knowledge. Foundations and Trends in Information Retrieval 4(1-2): 1-174 (2010)
http://www.nowpublishers.com/product.aspx?doi=1500000013&product=INR

Tambien es muy interesante el tutorial que dieron el mismo autor y Ricardo Baeza-Yates en Madrid en 2009, el cual fue grabado integramente y puedes seguir desde aqui:

http://videolectures.net/qlm09_madrid/

Los problemas de la Busqueda Semantica

Desde hace un tiempo se oye hablar mucho de la busqueda semantica, incluso muchas empresas se ganan la vida vendiendo buscadores semanticos. Sin embargo, no es oro todo lo que reluce y la busqueda semantica no solo no es util en muchos casos, sino que ademas, en ocasiones puede llegar a ser perjudicial.

El problema con la busqueda semantica, ya sea desde la perspectiva del PLN o desde el punto de vista de la Web Semantica de Tim Berners-Lee reside en que la integracion de conocimiento semantico en los buscadores tradicionales es muy complicada. Desde mi punto de vista, la tarea mas importante que realiza un buscador no es recuperar documentos (o paginas web), sino ordenarlos.

El ranking es la pieza clave de un buscador, ya que un buscador ha de ser capaz de situar aquellos documentos que satisfacen la necesidad de informacion del usuario, es decir los mas relevantes, en las primeras posiciones de la lista de resultados.

Un error muy tipico es pensar que los buscadores se basan solamente en un sistema booleano, es decir en calcular si un documento o pagina web es relevante o no lo es para el usuario que realiza la consulta, y esto no es asi, ya que la tarea es calcular en que medida es relevante para el usuario, de manera que podamos situar los documentos mas relevantes en la parte alta del ranking de resultados.

Aunque las tecnologias semanticas son utiles para recuperar documentos, sin embargo, suelen ser bastante perjudiciales a la hora de ordenar esos documentos en funcion de su relevancia.

Te pondre un ejemplo muy sencillo, es una simplificacion, pero sirve para ilustrar lo que intento explicar aqui. Imagina que el usuario introduce la siguiente consulta en un buscador:

Consulta : restaurante barcelona

La necesidad de informacion del usuario parece bastante clara, quiere recuperar documentos que hablen de restaurantes que estan en la ciudad de barcelona.

Si vemos esta consulta desde la perspectiva de una algoritmo tipico de IR como los que usan los buscadores veremos que cada documento se ordenara en funcion del peso (el peso es un valor numerico que define la importancia de una palabra en un documento, por ejemplo, el numero de veces que aparece) de las palabras de la consulta que aparecen en el. De esta forma se suma el peso de "restaurante" mas el peso de "barcelona" y eso nos ayuda a generar nuestra lista ordenada de documentos relevantes.

Asi pues podemos decir que la palabar "barcelona" aporta un 50% de la informacion necesaria para resolver la necesidad de informacion del usuario y la palabra "restaurante" aporta el otro 50%.

Ahora imaginemos que metemos algo de semantica, una ontologia, o algun tipo de diccionario por detras que nos permite expandir de alguna forma la consulta inicial del usuario, por ejemplo:

Consulta original: restaurante barcelona

Consulta expandida: restaurante bistro buffet barcelona

Aparentemente estamos completando la informacion que nos ha dado el usuario, utilizando sinonimos de la palabra "restaurante" de manera que ahora recuperaremos tambien documentos sobre buffets en barcelona que tambien podrian ser del interes del usuario. El problema reside es que si bien estamos mejorando la capacidad de recuperar nuevos documentos, nos estamos cargando el ranking.

Recordemos que el ranking se calcula en base a una suma (combinacion lineal) de los pesos en los documentos de cada una de las palabras que aparecen en la consulta, de manera que con la version expandida de la consulta la palabra "Barcelona" ha pasado de tener un 50% de impacto en el calculo de nuestro ranking (que es lo que tenia en la consulta inicial) a tener solo un 25%, ya que en la consulta expandida tenemos restaurante 25% + bistro 25% + buffet 25% + barcelona 25%

Esto quiere decir que un documento donde aparezcan las palabras "buffet" "restaurante" y "bistro" pero no la palabra "barcelona" estara mas arriba en nuestro ranking que un documento que contenga solo las palabras "restaurante" y "barcelona". Asi pues, hay una probabilidad muy alta de devolverle al usuario paginas web con informacion de restaurantes, buffets y bistros en Madrid.

Este ejemplo es una simplificacion, y existen tecnicas para suavizar el efecto de la expansion, pero aun asi no estan muy depuradas y sigue siendo un problema por resolver en lo que a busqueda semantica se refiere.

Son bueno estos resultados?

Una de las cosas mas dificiles de saber cuando tenemos un buscador es si estamos devolviendo resultados relevantes en nuestro buscador, especialmente cuando no tenemos los query logs con la informacion de interaccion de los usuarios.

En los ultimos anos se han desarrollados varios metodos para intentar saber si estamos cubriendo la necesidad de informacion del usuario. Todos estos metodos se han recogido recientemente en un libro de manera que nos podemos evitar la lectura de un buen monton de papers:

Estimating the Query Difficulty for Information Retrieval
Synthesis Lectures on Information Concepts, Retrieval, and Services
2010, 89 pages, (doi:10.2200/S00235ED1V01Y201004ICR015)
David Carmel‌ IBM Research, Israel
Elad Yom-Tov‌ IBM Research, Israel
http://www.morganclaypool.com/doi/abs/10.2200/S00235ED1V01Y201004ICR015

Yo la verdad es que no le veo mucho futuro a estas tecnicas, pero sin duda se trata un trabajo interesante que analiza muchos aspectos interesantes del proceso de recuperacion, y de como funcionan las funciones de ranking y las listados de documentos que se devuelven.

Software libre de IR para SEOs. Parte 2

Segunda parte de la charla que di en 2007 en el congreso Ojobuscador sobre Recuperacion de Infromacion, SEO y software libre para buscadores. Esta charla fue publicada originalmente en .
http://www.ojobuscador.com