Lalgoritmo di Rocchio è una tecnica classica di relevance feedback (riscontro di rilevanza) utilizzata nei sistemi di Information Retrieval (IR). Formulato da J.J. Rocchio nel 1971 nell'ambito del progetto SMART guidato da Gerard Salton, l'algoritmo ha lo scopo di incorporare il giudizio dell'utente riguardante la pertinenza dei documenti recuperati per raffinare e riformulare la query originaria, migliorando precisione e richiamo dei risultati successivi.
In un modello basato su spazio vettoriale, la query e i documenti sono rappresentati come vettori in uno spazio ad alta dimensionalità, in cui le componenti corrispondono al peso dei termini (spesso calcolato tramite tf-idf). L'algoritmo modifica la posizione del vettore query originale facendolo spostare verso la regione dello spazio vettoriale popolata dai documenti ritenuti rilevanti e allontanandolo da quella dei documenti non rilevanti.
Formulazione
Sia il vettore query originario acquisito dall'utente. Siano l'insieme dei documenti identificati dagli utenti come rilevanti e l'insieme dei documenti identificati come non rilevanti. L'algoritmo calcola la nuova query ottimizzata tramite la seguente formula:
dove: è il vettore della query originale; e sono i vettori rappresentanti rispettivamente i documenti rilevanti e non rilevanti; e indicano la cardinalità (numero di elementi) dei due insiemi di documenti; , e sono parametri di peso positivi regolabili.
Significato dei parametri : pesa l'importanza del vettore query originario. Mantenere un valore elevato per garantisce che la query modificata rimanga ancorata all'intenzione iniziale dell'utente. : regola l'influenza dei documenti rilevanti. Poiché l'obiettivo è muovere il vettore verso il centroide dei documenti pertinenti, viene solitamente impostato su un valore relativamente alto. : regola l'impatto dei documenti non rilevanti. Nella pratica applicativa, l'influenza negativa viene spesso limitata impostando su un valore inferiore rispetto a (o applicando la variante del Positive Feedback, dove ).
Se la formula produce componenti con valori negativi nel vettore , tali pesi vengono solitamente azzerati, poiché nell'IR tradizionale i termini di una query non possono avere frequenza o peso negativo.
Applicazioni e varianti
Oltre al normale feedback esplicito fornito dell'utente, l'algoritmo trova applicazione anche nel cosiddetto Pseudo-Relevance Feedback (o Blind Relevance Feedback). In questo contesto, il sistema presuppone automaticamente che i primi documenti restituiti al primo passaggio di ricerca siano rilevanti, applicando la formula di Rocchio senza richiedere l'intervento manuale dell'utente.
Denominazione L'algoritmo prende il nome dal suo autore, Joseph J. Rocchio Jr., che lo propose in un rapporto tecnico del 1965 al Computation Laboratory dell'Università di Harvard (dove aveva conseguito il PhD in matematica applicata, 1959–1965). La pubblicazione di riferimento è il capitolo "Relevance Feedback in Information Retrieval" nel volume Experiments in Automatic Document Processing (1971), curato da Gerard Salton.
È la stessa convenzione con cui si chiamano molti altri algoritmi in informatica: il cognome dello sviluppatore diventa il nome del metodo. Non c'è un significato lessicale dietro il nome "Rocchio" si tratta semplicemente del cognome della persona.
Note
Voci correlate
Information retrieval TF-IDF
Categoria:Recupero dell'informazione Categoria:Algoritmi di classificazione Categoria:Elaborazione del linguaggio naturale Categoria:Motori di ricerca