Come fanno i motori di ricerca a capire un nome a partire da un soprannome? Faccio un esempio per chiarirmi: cerco con Google.com informazioni riguardanti il principe William del Galles. Come keyphrase uso “Bill Philip Louis” e ottengo al secondo posto la pagina Wikipedia della persona che stavo cercando; eppure all’interno della pagina non c’è mai il nome “Bill”. Se invece faccio la ricerca solo con “Philip Louis” non ottengo più quello che cercavo. Come fa Google ha capire che io cerca esattamente William e non altri corrispondenti alle altre keys?

Un brevetto di Yahoo, pubblicato recentemente, ci fornisce una possibile risposta. Riporto solo l’estratto, il link del sito USA è nel titolo.

PREDICTIVE PERSON NAME VARIANTS FOR WEB SEARCH

Inventors: LU, Yumao (San Jose, CA, US) Peng, Fuchun (Sunnyvale, CA, US) Dumoulin, Benoit (Palo Alto, CA, US)

Application Number: 12/480628

Publication Date: 12/09/2010

Filing Date: 06/08/2009

Abstract

Techniques for determining when and which name variant candidates to use to re-write a search query that includes a person’s name in order to provide the most relevant search results are provided. A determination is made whether a person name is present in a search query request entered by a user. Name variant candidates are generated for each person name. Then, the name variant candidates are ranked for each person name based upon one or more models that calculate a probability value for each name variant candidate. Based upon these rankings, the query may be re-written to include the original person name and a specified number of top ranked name variant candidates to present the user with the most relevant search results.

[…]

Identificazione del nome

Questo brevetto ci spiega che il motore di ricerca non si limita a scegliere tra una lista di parole corrispondenti al soprannome utilizzato. Il metodo è più complesso.

In primo luogo Yahoo quando riceve una query dall’utente analizza se in essa è presente almeno un nome e lo identifica. Questi modelli che intervengono per l’identificazione, come si può immaginare, vengono aggiornati continuamente.

Interviene il Condictional Random Field (“CRF”), vediamo cosa dice il brevetto:

“In an embodiment, a Conditional Random Field (“CRF”) model is used to recognize person names in user queries. CRF is a discriminative probabilistic model that may be used to label sequential data. In an embodiment, the CRF model is trained using a pre-tagged corpus of search queries. For example, a CRF engine might be given 250,000 different previously submitted search queries. The CRF engine tags each term of the search query with a label of whether the term is a person name.”

Il CRF viene usato per riconoscere il nome della persona nella query. In base alle queries precedentemente inviate dagli utenti. Il CRF può analizzare 250’000 precedenti queries e contrassegnare nome di persona e attraverso queste etichette analizzare la query in questione.

Altri modelli degni di interesse sono l’Hidden Markov Model (HMM) e il Support Vector Machine (SVM), vediamo di nuovo il brevetto:

“Hidden Markov Model (HMM) is employed to determine the presence of person names within a search query. HMM is a statistical model that has been used to find the part-of-speech of a given word. For example, an article such as “the” might indicate that the next word is a noun 40% of the time, an adjective 40% of the time, and a number 20% of the time. Based on these probabilities, the part of speech of the next word is determined. This model may be easily adapted for use to also find the presence of person names. A Support Vector Machine (SVM) model or a hybrid of HMM and SVM may also be used to determine the presence of person names in search queries. SVMs are related supervised learning methods used for classification and regression. In SVM, given data (a corpus) that belong to one of two classes (`name` or `not a name`) is analyzed. When a new data point (word) is received, a determination is made as to which class the new data point belongs. In addition, any other model that labels and classifies data that may be adapted to find person names may also be used.”

Anch’essi sono utilizzati per determinare la presenza di un nome proprio nella query. Si tratta di un modello statistico che è utilizzato per capire quale valore grammaticale è data ad ogni singola parola. L’esempio che riporta il brevetto è molto chiaro; esso dice che la parola che segue “the” è al 40% un nome, al 40% un aggettivo, etc..

Ad ogni parola viene assegnata la classe “nome” o “non-nome” e permette una classificazione.

Riconoscimento del nickname

A questo punto ogni nome viene confrontato con due differenti dizionari:

1.    dal soprannome al nome vero e proprio.

2.    dal nome al soprannome.

Questi dizionari sono costruiti offline da dizionari preesistenti (come quello dei nomi mantenuti nella Social Security Administration), o dalle query di ricerche precedenti o dai nomi trovati nel Web.

A questo punto il motore di ricerca assegna un volere al nome più probabile da associare.

Nel brevetto sono riportati alcuni metodi utilizzati da Yahoo per assegnare tale valore.

Come il White Page Frequency, ecco cosa ci dice il brevetto:

“In white page frequency, the frequency or occurrence of name variant candidates are counted in a known list of names. For example, a list of names from the Social Security Administration may be used to find the popularity of names of people in the United States for a given year. Using the lists of names from the Social Security Administration, counts or popularity of name variant candidates are calculated. The name variant candidates are ranked based upon the popularity of use and the highest ranked name variant candidates are those names that are the most popular.”

Questa opzione è piuttosto semplice da capire. Infatti, analizza i dizionari noti al motore per capire la popolarità del nome degli USA e assegna un valore conseguentemente.

Lo Statistical Traslation Model è un altro sistema utilizzato, il brevetti ci dice:

“A statistical translation model may be used to calculate the probabilities of finding a name variant candidate where the person name is found in a resource. This model calculates and stores the probabilities, given a corpus or web files, of the number of times any word sequence occurs within the corpus. The corpus may be the entire Internet, a set of previous search queries, or a small collection of files on a single web server. In an example, a notation of the probability of the occurrence of a four word phrase “w.sub.1w.sub.2w.sub.3w.sub.4” is “P(w.sub.1w.sub.2w.sub.3w.sub.4)” and might be shown as follows:

P ( w 1 w 2 w 3 w 4 ) = # ( w 1 w 2 w 3 w 4 ) ( * ) = P ( w 1 ) P ( w 2 w 1 ) P ( w 3 w 2 w 1 ) P ( w 4 w 3 w 2 w 1 ) ##EQU00001##  […]”

Esso prende un corpo di informazioni, come la lista di parole presenti sul Web, o le queries delle precedenti ricerche, o nei libri noti al motore e ripartisce le parole in sequenze di frasi.

A seconda della frequenza di ripetizioni nel corpo viene associato un valore probabilistico.

Il Session Based Query Analysis è il terzo sistema illustrato dal brevetto. Ecco il testo:

“Another model that may be used is session based query analysis. Session based query analysis considers search behavior of a particular user within a session, or certain time constraint. This model is illustrated in FIG. 1. First, a server retrieves all of the different name variant candidates for a particular person name, as shown in 101. Then, as shown in 103, previous queries submitted by users are compiled and gathered by the server. The previous queries may be extracted from cookies that are stored on a user’s computer. Alternatively, the previous queries may be stored on a central database when the search queries are received. Any identification data of a user may be removed from the cookies in order to preserve the privacy of the user. The queries are grouped based upon a session from a user, as shown in 105. Sessions may be defined as being within a specified time boundary. The specified time boundary may be, for example, thirty minutes, but may vary from implementation to implementation. In another embodiment, a session may be based on express login/logout actions performed by the user.”

Questo metodo si basa sulle precedenti queries memorizzate dal motore. Infatti, in molte queries è possibile trovare nomi che hanno una relazione tra loro, questa situazione è molto frequente e questi rende il modello più affidabile. Sfruttando un gran numero di queries si possono stabilire, quindi, alcune possibili relazioni tra diversi nomi.

Guardiamo oltre

Questo brevetto è ovviamente interessante per tutte le attuali applicazioni ma probabilmente dovremmo osservarlo in con un sguardo più avanti. Difatti esso è interessante per quel che riguarda LDA. Se ora i motori di ricerca riescono a stabilire con chiarezza il valore di un soprannome e associargli il nome completo (o viceversa) analizzando, quindi, tutti i sinonimi, presto i motori saranno in grado di implementare le proprie conoscenze a livello semantico. Con gli strumenti mostrati nel brevetto possiamo anche immaginare che presto i motori di ricerca riusciranno a riconoscere la struttura grammaticale di una pagina, in base ai modelli probabilistici, e riconoscere, in maniera automatica, i contenuti autogenerati sfruttando i software che sfruttando la semantica, che stanno avendo una discreta diffusione.

Questo brevetto è un esempio di come i motori di ricerca stiano facendo grandi passi avanti nello sviluppo di LDA e HTMM. Attraverso i sistemi descritti, opportunamente sviluppati, i motori riusciranno a capire moltissime informazioni sul contenuto e sulla attinenza del testo.

One Response

  1. Quadrrato

    Salve,
    la cosa è davvero ragguardevole. Sono dei veri e propri calcoli mostruosi i quali permetteno di fare cose come quelle descritte molto bene in questo articolo.
    Allo stesso tempo in me viene rafforzato un dubbio (quasi certezza), ovvero: "Ormai i più imporatanti siti ci conoscono e ci distinguono senza problemi".
    Secondo me arriveremo al punto che gli "evercokie" saranno le cose meno preoccupanti (giusto per dire un pericolo per la privacy).
    Saluti, Quadrrato

    Rispondi

Leave a Reply

Your email address will not be published.