Mostrando entradas con la etiqueta Motores de búsqueda. Mostrar todas las entradas
Mostrando entradas con la etiqueta Motores de búsqueda. Mostrar todas las entradas

miércoles, 7 de enero de 2015

Web Semántica (II): Google Knowledge


El número de páginas web supera los mil millones, la cifra se alcanzó hace unos meses según los datos difundidos en tiempo real por la web Internet Live Stats A esa hora, el número de páginas web había ascendido a más de 1.060 millones, una cifra que no para de crecer y a un ritmo considerable, según revelan los datos.
Figura 1. Captura en tiempo real de la web Internet Live Stats. 

Internet, esa red mundial interconectada, ideada por el británico Tim Berners-Lee(artículo) que presentó su idea por escrito el 12 de marzo de 1989 (fecha oficial establecida como el nacimiento de la web) y que estableció la primera comunicación entre un cliente y un servidor usando el protocolo HTTP un poco más tarde, allá por noviembre de 1989, celebró sus 25 años este 2014.

Este hito en comunicación transformaría por completo la vida de miles de millones de personas en todo el mundo con el paso del tiempo. Ahora, en la actualidad, es imposible concebir el mundo tal y como lo vivimos sin la presencia de internet.

A pesar de que los inicios de la web fueron tímidos, los gurús de la red afirman que el punto de inflexión en la creación de páginas web tuvo lugar en 1993 con la introducción del navegador Mosaic, que propició un auténtico “boom” de nuevas páginas, crecimiento que, no ha ido sino aumentando a un ritmo acelerado desde entonces y con el único punto negativo destacable del estallido o desplome de la burbuja de las punto-com en 2001.
Figura 2. Captura Country Codes of ther World.
    
Los algoritmos de los buscadores evolucionan a la vez que lo hacen las necesidades de las personas. Al principio la única manera que había de organizar la información era mediante directorios, ¿quién no se acuerda cómo era buscar en Ask y Yahoo?
La revolución de los buscadores vino cuando Sergey Brin y Larry Page fueron capaces de crear un algoritmo de IR que ordenaba las páginas por el número enlaces que recibían y te las ofrecía en una lista de 10 resultados. Gracias a este desarrollo del PageRank nació Google.
Poco a poco los buscadores fueron incorporando este sistema y añadiendo otros algoritmos de IR en paralelo (o reescribiendo directamente el core). Por ejemplo algoritmos centrados en las páginas y sus relaciones (como el HITS, TrustRank, Okapi 25, Tf-idf…), evolucionando hacia el contenido y calidad (los de NLP; LSI, LDA, Spamdexing…) para llegar a las entidades (con el AuthorRank, el SocialGraph…).
Hasta ahora vivimos en un mundo de 10 links azules donde, para encontrar la información que buscas,  tienes que leer los snippets de texto y con un poco de suerte encuentras la respuesta a tus preguntas. Durante mucho tiempo esto ha sido (y sigue siendo) una buena solución, pero no es suficiente para el usuario cuyas necesidades evolucionan (búsquedas más cortas en móvil, más búsquedas locales, búsquedas por voz…). 
El problema sobretodo reside en que es muy difícil para un buscador capturar la intención real del usuario en una búsqueda y ofrecer un resultado óptimo. Y este problema es todavía más complejo de resolver por los algoritmos cuando hablamos de búsquedas de nombre de entidades y la intención que hay detrás ellas.
 Figura 3. Captura Google BETA (1998).
¿QUÉ ES UNA ENTIDAD ?

Muy sencillo, una entidad puede ser una persona, un lugar o una cosa. Y estas entidades se pueden asociar a fechas, acciones u otras entidades.


A día de hoy, una porción muy significativa de las búsquedas son nombres de entidades (20-30% según un estudio de Microsoft (documento) y una porción aún más grande de las búsquedas son las que contienen nombres de entidades (71% según el mismo estudio). Como he mencionado antes, es complejo para un buscador detectar la intención que hay detrás de la búsqueda de una entidad. A continuación podemos un ejemplo de cuáles son las intenciones más comunes detrás de diferentes tipos entidades:





Internet, esa red mundial interconectada, ideada por el británico Tim Berners-Lee, que presentó su idea por escrito el 12 de marzo de 1989 (fecha oficial establecida como el nacimiento de la web) y que estableció la primera comunicación entre un cliente y un servidor usando el protocolo HTTP un poco más tarde, allá por noviembre de 1989, celebró sus 25 años este 2014.



Este hito en comunicación transformaría por completo la vida de miles de millones de personas en todo el mundo con el paso del tiempo. Ahora, en la actualidad, es imposible concebir el mundo tal y como lo vivimos sin la presencia de internet.

Figura 4.  Intenciones más comunes para ciertos tipos de entidades.
 
Incluso para búsquedas que contienen nombres de entidades cuya intención debería ser más clara, los usuarios escogen diferentes tipos de resultados. En la imagen siguiente podemos ver un ejemplo real de las intenciones que hay detrás de 4 tipos distintos de búsquedas que contienen la entidad “Seattle”:



Figura 5.Porcentaje de usuarios escogiendo diferentes resultados para cuatro búsquedas distintas que contienen la palabra “Seattle”.
Otro problema que nos encontramos con las entidades pueden ser citadas por más de un nombre, o un mismo nombre puede ser referido a entidades distintas. Por ejemplo la entidad “Barcelona” puede ser referida a la ciudad española, al equipo de fútbol y en menor medida a la ciudad de Venezuela. También la Barcelona española es comúnmente conocida por “ciudad condal".
 
 Figura 6. Grado de conectividad social. 


LAS ENTIDADES Y LOS BUSCADORES
Los principales buscadores están continuamente desarrollando y testeando diferentes soluciones para satisfacer las necesidades del usuario cuando hace una búsqueda con el nombre de una entidad. Por ejemplo, nada más entrar en Yahoo, nos encontramos con un apartado que nos muestra “lo más buscado”, donde vemos curiosamente que la mayoría de search queries son nombres de entidades.

Figura 7. Lo más buscado en Yahoo.
 
En Google para resolver estas necesidades se usa el Knowledge Graph (KG o copia de Wikipedia para los amigos). Podemos ver para la query “Barcelona” que la principal tarea que viene a realizar el usuario es más la futbolística que cultural/turística, pero no por ello no se incluye la segunda por su peso:
Figura 8.Google Knowledge Graph para la búsqueda “Barcelona”.
 
Bing también tiene su propio KG, pero si no está seguro no te lo muestra y te ofrece en el lateral queries relacionadas antes de mostrártelo.

Uno de los mejores buscadores semánticos Wolfram Alpha, para la entidad Barcelona te ofrece una desambiguación como podemos ver:
 Figura 9. Búsqueda semántica en 'WolframAppha'.

Entonces para que los buscadores puedan ofrecer las respuestas específicas más populares o una ayuda para que el usuario pueda completar su tarea inicial, no sólo tienen que capturar la intención, sino también las relaciones que hay entre las entidades. Para ello hace falta que esa información se extraiga, se relacione y se almacene en algún lugar. Y la mejor manera de lograrlo eficientemente es mediante grafos.

----------------- TO BE CONTINUED ---------------------



lunes, 5 de enero de 2015

Googlebot: Cómo funciona un buscador

 Figura 1. Definición de GoogleBot.
     Para cualquier profesional, un esfuerzo extra supone posponer un montón de cosas personales. No es el caso, puesto que antes de salir 'pintando' para la Cabalgata de Reyes, me propongo haceros llegar un post resumido sobre el funcionamiento de los motores de búsqueda. Nos introducimos ayer en algunos conceptos complejos y extensos, como es la web semántica... continuaremos haciéndolo, no obstante se hace conveniente para los que aún no controlaís la terminología y los aspectos fundamentales de Internet, dedicar unas cuantas líneas a la herramienta que ha posibilitado la evolución de la red y la organización de la información: los motores de búsqueda. Disculpad la calidad de las imágenes, y el idioma. La falta de tiempo (hoy como excepción), no me permiten disponer de algunas más adecuadas.


Cómo realiza Google las búsquedas



     Si estás leyendo este post, estás interesado en aprender cómo Google crea el índice y la base de datos de los documentos a los que se accede cuando se procesa una consulta.  Tomaremos como punto de partida, la descripción que ofrece Gary Precio en el Capítulo II de La Web Invisible (CyberAge Books, 2001), sobre cómo los Motores de Búsqueda organizan la información.
     <<Google se ejecuta en una red distribuida de miles de computadoras de bajo costo y por lo tanto puede llevar a cabo el procesamiento en paralelo rápido. El procesamiento en paralelo es un método de cálculo en la que muchos cálculos pueden realizarse de forma simultánea, lo que acelera significativamente el procesamiento de datos.>>
Google tiene tres partes bien diferenciadas:
 Figura 2. 'The Invisible Web',(CyberAge Books, 2001). 
Autores: Chris Sherman y Gary Price. 
Googlebot, un rastreador web que busca y recupera las páginas web.



El indexador que ordena cada palabra en cada página y almacena el índice resultante de las palabras en una enorme base de datos.



El procesador de consultas, que se compara su consulta de búsqueda en el índice y recomienda los documentos que considere más relevantes.
 
Echemos un vistazo a cada parte.

Googlebot, Web Crawler de Google

     Googlebot es un robot de rastreo web de Google, que encuentra y recupera las páginas en la web y las superpone encima del indexador Google. Es fácil imaginar Googlebot como una pequeña araña corriendo por los hilos del ciberespacio, pero en realidad Googlebot no atraviesa la web en absoluto. Funciona muy parecido a su navegador de Internet, mediante el envío de una petición a un servidor web para cargar una página web; posteriormente procede a la descarga de toda la página, y luego la entrega al ndexador de Google.

     Googlebot se compone de muchos equipos que solicitan y ir a buscar páginas mucho más rápido de lo que puede con su navegador web. De hecho, Googlebot puede solicitar miles de diferentes páginas simultáneamente. Para evitar sobrecargar los servidores web, o desplazar las peticiones de los usuarios humanos, Googlebot hace deliberadamente peticiones de cada servidor web de forma individual.
      Googlebot encuentra páginas de dos maneras: a través de un formulario de URL add, www.google.com/addurl.html , y a través de la búsqueda de enlaces de rastreo de la web. 

 Figura 3. Googlebot: Formulario de búsqueda.
     Desafortunadamente, los spammers descubrieron cómo crear robots automatizados que bombardearon el formulario add URL con millones de direcciones URL que apunta a la propaganda comercial. Google rechaza esas URLs enviadas a través de su formuario URL Add, por el  sospecha están tratando de engañar a los usuarios mediante el empleo de tácticas como la inclusión de texto oculto, o enlaces a una página. Otras técnicas como el relleno de una página con palabras irrelevantes, el encubrimiento (también conocido como señuelo), utilizando redireccionamientos elusivos, la creación de portales, dominios o subdominios con contenido sustancialmente similar, el envío de consultas automatizadas a Google, y la vinculación a los malos vecinos. Así que ahora el formulario Add URL también tiene una prueba: muestra algunas opciones para engañar a los spammers de forma automatizada; se le pedirá que introduzca las letras que ve - algo así como un examen de la vista, similar a los caracterís captcha para tratar de frenar los spambots.
     Cuando Googlebot obtiene una página, entresaca todos los enlaces que aparecen en la página y los añade a una cola para su posterior rastreo. Googlebot tiende a encontrarse con baja de spam porque la mayoría de los autores web vinculan sólo a los que ellos creen que son las páginas de alta calidad. Por vínculos de cosecha de cada página que encuentra, Googlebot puede crear rápidamente una lista de enlaces que pueden cubrir amplios alcances de la web. Esta técnica, conocida como el rastreo profundo, también permite que el robot de Google para sondear las profundidades de los sitios individuales. Debido a su escala masiva, los rastreos profundos pueden llegar a casi todas las páginas de la web. La web es enorme, esto puede tomar algún tiempo, por lo que algunas páginas pueden ser rastreaas sólo una vez al mes.

     Aunque su función es simple, Googlebot se debe programar para manejar varios desafíos. En primer lugar, ya que el robot de Google envía solicitudes simultáneas de miles de páginas, la cola de la "visita breve" URLs, debe ser constantemente examinada y comparada con las URL que ya están en el índice de Google.Los duplicadios en la cola deben ser eliminados para evitar que Googlebot vaya a buscar la misma página de nuevo.  Determinará con qué frecuencia volverá a visitar una página. De otro lado, es una pérdida de recursos para volver a indexar una página sin cambios. 

     Para mantener actualizado el índice, Google rastrea constantemente las páginas web que cambian con más frecuencia. Estos rastreos mantienen un índice corriente, y se conocen como rastreos frescos. Las páginas de los periódicos se descargan a diario, y las páginas con las cotizaciones de bolsa se descargan con frecuencia horaria. Por supuesto, los rastreos frescos devuelven menos páginas que el arrastre de profundidad. La combinación de los dos tipos de rastreos permite que Google hacer un uso eficiente de sus recursos, y mantener su índice razonablemente actualizado.

Indexador de Google

     Googlebot ofrece el indexador al texto completo de las páginas que encuentra. Estas páginas se almacenan en la base de datos del índice de Google. Este índice está ordenada alfabéticamente por el término de búsqueda, con cada entrada de índice que almacena una lista de los documentos en los que aparece el término y la ubicación dentro del texto donde se produce. La estructura de datos permite un rápido acceso a los documentos que contienen los términos de búsqueda del usuario.

     Para mejorar el rendimiento de búsqueda, Google ignora (no indexa) palabras comunes llamados palabras vacías (como el, es, en, o, de, cómo, por qué, así como algunos dígitos y letras independientes). Las palabras vacías son tan comunes que hacen poco para restringir una búsqueda, y por lo tanto de manera segura pueden ser descartadas. El indexador ignora igualmente algunos signos de puntuación y espacios múltiples, así como la conversión de todas las letras en minúsculas para mejorar el rendimiento de Google.
Procesador de consultas de Google

     El procesador de consultas tiene varias partes, incluyendo la interfaz de usuario (cuadro de búsqueda), es el "motor" que evalúa las consultas y lass compara con los documentos pertinentes, y los resultados del formateador.

     PageRank es el sistema de Google para clasificar las páginas web. Una página con un PageRank más alto se considera más importante y es más probable que se enumere más arriba que una página con un PageRank más bajo.

     Google tiene en cuenta más de un centenar de factores en el cálculo de un PageRank y determinar qué documentos son más relevantes para una consulta, incluyendo la popularidad de la página, la posición y el tamaño de los términos de búsqueda dentro de la página, igualmente, también la proximidad de los términos de búsqueda entre sí en la página. Una solicitud de patente, analiza otros factores que Google tiene en cuenta al clasificar una página. Visita el informe del SEOmoz.org para una interpretación de los conceptos y las aplicaciones prácticas que figuran en la solicitud de patente de Google.
     Google también aplica técnicas de aprendizaje para mejorar su rendimiento de forma automática: basada en relaciones y asociaciones entre los datos almacenados. Por ejemplo, el sistema de corrección ortográfica utiliza esas técnicas parra averiguar otras ortografías alternativas. Google guarda celosamente las fórmulas que utiliza para el cálculo de relevancia; que están ajustados para mejorar la calidad y el rendimiento, y para burlar las últimas técnicas (ataques) utilizadass por los spammers.

     Indexar el texto completo de la web, permite a Google ir más allá de los resultados de términos de búsqueda individuales. Google da más prioridad a las páginas que tienen los términos de búsqueda más aproximados, y en el mismo orden que en la consulta. Google también puede hacer coincidir frases de varias palabras y oraciones.

     Desde Google se indexa código HTML, además del texto en la página, los usuarios pueden restringir las búsquedas sobre la base de donde aparecen palabras de la consulta, por ejemplo; en el título, en la URL, en el cuerpo, en enlaces de la página, en las opciones que ofrece por Búsqueda Avanzada el Formulario de Google y el Uso de Operadores de búsqueda (Operadores Avanzados).

A continuación un ejemplo sobre cómo Google procesa una consulta:

Esquema. Procesamiento de consulta.


Recursos y complementos: