Scoperta del giorno: Contextual Network Graphs.
Premesso che devo ancora approfondire, si tratta di una tecnica di analisi della semantica latente basata su un grafo dei termini e dei documenti:
uses a term-document matrix to generate a bipartite graph of term and document nodes representing the document collection. This graph can be searched by a simple recursive procedure that distributes energy from an initial query node. Nodes that acquire energy above a specified threshold comprise the result set. Initial results on live collections suggest that this technique may offer performance comparable to latent semantic indexing (LSI), while avoiding some of that technique’s computational pitfalls.
Molto interessante.
Ettore Conte ha realizzato un’implementazione opensource di CNG in Python:
Axil, ossia AXiom Indexing Library, e’ una implementazione open-source in Python di un algoritmo di ricerca, o meglio di contextual search, noto sotto il nome di CNG (Contextual Network Graphs) o CNS (Contextual Network Search).
Anche altri due italiani, Mauro Cherubini e Lorenzo Viscanti, hanno lavorato ad un’implementazione di CNG.
19/08/2006 alle 05:10 |
a dire la verita’ gli italiani che hanno realizzato un’implementazione di CNG in phyton sono tre e non due :-)
infatti l’implementazione alla quale ti riferisci, ovvero Axil, e’ la mia (come si’ puo’ facilmente verificare andando a guardare nella prima riga di un qualsiasi file del codice sorgente), non quella di Mauro Cherubini e Lorenzo Viscanti.
19/08/2006 alle 15:20 |
Ops! Mi scuso. Su blorigo.net e blorigo.com non avevo trovato riferimenti agli autori e non ho pensato di controllare nel codice. Avevo dedotto del coinvolgimento di Mauro Cherubini e Lorenzo Viscanti nel progetto attraverso i loro blog. A dire il vero nella prima stesura del post avevo scritto “Mi par di capire che due italiani …”; modificandolo successivamente ho dato per certa la mia deduzione incappando così nell’errore.
Ora ho modificato nuovamente il post aggiungendo anche il tuo nome.
19/08/2006 alle 20:49 |
grazie :-)
….ma , a scanso di equivoci, lasciami fare un solo chiarimento: la mia implementazione e’ distinta da quella di Mauro Cherubini e Lorenzo Viscanti, che non sono mai stati coinvolti nel progetto di cui Axil fa parte.
20/08/2006 alle 11:09 |
L’implementazione mia e di Mauro è in Java, ma a breve verrà convertita in Python per ragioni legate all’utilizzo applicativo che intendiamo farne.
In particolare il nostro sistema implementa in maniera trasparente sia LSI sia CNG (o SA se si vuole utilizzare il nome che usano gli specialisti di AI).
Potete provare la nostra inplementazione in una applet disponibile a questo indirizzo: http://www.noosfactory.com/visual%5Fir/
L’obbiettivo di questo software è quello di testare contemporaneamente LSI e SA per vedere se producono performances confrontabili.
CNG era in auge alcuni anni fa nel mondo della ricerca, noi abbiamo cominciato ad interessarcene durante lo scorso autunno ed in primavera abbiamo realizzato l’implementazione.
Ho dato un’occhiata al codice di Ettore, è estremamente interessante!
Non so quanto lui lo abbia già provato ma nel nostro caso prima di un tuning approfondito i risultati non sono stati incoraggianti. Il problema più grande è legato all’algoritmo di analisi del testo e di selezione delle features.
20/08/2006 alle 17:08 |
Dalle prove che ho avuto modo di fare sono rimasto sono rimasto soddisfatto;
comunque attualmente sto lavorando alla realizzazione di una versione di Axil per “beta tester”:
sostanzialmente un applicazione per windows (possibilmente con installer) con una semplice interfaccia a linea di comando (o con una semplice GUI se riesco a trovare il tempo di farlo) per consentire agli eventuali interessati di provare Axil senza doversi installare le varie librerie che utilizza; e senza dovere scendere nei dettagli delle dipendenze delle varie versioni delle librerie ….per esempio la versione attuale di Axil funziona solo con la vecchia versione di Axiom visto che la nuova ha cambiato le API.
Tra qualche giono dovrebbe essere pronta (molto dipende dal fatto che io decida o meno di aggiornare il tutto per aggiungere il supporto alle nuove librerie) cosi’ potrete verificare di persona le reali performance dell’implementazione.
20/08/2006 alle 17:54 |
Siete a conoscenza di test che confrontino LSI e CNG, e i cui risultati siano reperibili su Internet? Oppure, avete fatto voi dei test?
Mi interesserebbe conoscere, ad esempio, le prestazioni dei due algoritmi a tempo di query. E poi naturalmente precision, recall, etc.
20/08/2006 alle 19:07 |
Noi abbiamo confrontato LSI con CNG giungendo a risultati che stiamo cercando di pubblicare (lavorando a distanza con Mauro siamo purtroppo molto lenti).
Per il momento l’unico confronto è (molto parziale) in questo paper: http://scholar.google.com/scholar?hl=en&lr=&safe=off&cluster=16125775306147573871
A tempo di query naturalmente CNG soffre di qualche problema legato alla lentezza, mentre come precision e recall non si distanzia troppo da LSI.
Se vuoi posso fornirti anche dati più precisi.
20/08/2006 alle 20:37 |
Non avendo una implementazione di LSI da usare come termine di paragone, non dispongo di dati di prima mano che confrontino le prestazioni dei due algoritmi; appena ho un po’ di tempo vado a riguardarmi alcuni papers che mi sono letto in cui, se non ricordo male, c’erano dei dati al riguardo…
Per quel che riguarda l’eccessiva durata delle query in un CNG; in effetti e’ uno dei principali problemi che mi si sono presentati dopo avere realizzato le prime implementazioni dell’algoritmo:
infatti ho subito cominciato a modificare l’algoritmo iniziale con dei metodi euristici che mi permettessero di limitare la durata della query mantenendo i documenti nello stesso ordine di rilevanza;
se dai un’occhiata al codice puoi vedere che esistono differenti versioni del metodo “query” che consentono di impostare dei limiti in termini di tempo e/o di nodi visitati.
20/08/2006 alle 22:51 |
Lorenzo Viscanti ha scritto:
| Se vuoi posso fornirti anche dati più precisi.
Se non ti è di troppo disturbo; altrimenti attendo la vostra pubblicazione.
Ettore Conte ha scritto:
| se dai un’occhiata al codice puoi vedere che esistono differenti versioni del metodo
| “query” che consentono di impostare dei limiti in termini di tempo e/o di nodi
| visitati.
Ieri ho dato un’occhiata veloce e ho notato la presenza di timeout; comunque approfondirò anche per ciò che riguarda i metodi euristici che hai adottato.
Grazie ad entrambi.
23/07/2007 alle 09:29 |
Salve a tutti.
Mi chiedevo se un approccio con CNG per catalogare documenti solo in base ai titoli(con un training fatto comunque tramite il corpo dei documenti) poteva rivelarsi valido.
Inoltre in giro per la rete non ho trovato tantissimo materiale in merito all uso del CNG. Se poteste darmi qualche riferimento ve ne sarei veramente grato.
13/02/2008 alle 20:34 |
Ciao a tutti.
Una domanda al volo:
devo clusterizzare dei documenti restituiti da un motore di retrieval. Ottengo una matrice W Termini per Documenti, che SVDPackC mi decompone in W=U*S*Vt.
Se riduco il rango di S e moltiplico W’=U’*S’*V’t, posso essere sicuro che W’ contiene gli stessi termini e documenti di W nello stesso ordine?
Vi prego è importante, non mi sembra vero aver trovato qualcuno che ci capisce qualcosa
15/02/2008 alle 18:22 |
Certo. Guarda questo documento http://www-db.deis.unibo.it/courses/SI2/slides/LSI.pdf che contiene un semplicissimo esempio numerico; può aiutarti a chiarire il funzionamento di LSI.
16/02/2008 alle 16:17 |
Grazie per il link, mi ha chiarito alcuni dubbi.
Ma Vk rappresenta la matrice concetti per documenti? Va prima moltiplicata per Sk?
Mi hanno detto che la matrice termini per documenti non va mai ricostruita dopo la SVD.
Quello che non so fare è associare un nome (un insieme di termini) a un cluster, e quindi a un concetto. Pensavo a una cosa del genere:
- creare una matrice concetti per documenti moltiplicando Vk*Sk
- fare document clustering su tale matrice
- per ogni cluster, trovare il centroide (è un documento)
- per tale documento, trovare il termine più rappresentativo/rilevante (nome del cluster)
Sbaglio qualcosa? Ogni suggerimento è ben accetto
mranieri81@hotmail.com
18/02/2008 alle 19:46 |
Secondo me, potrei anche sbagliare:
Ricostruire la matrice termini-documenti in effetti non ti serve.
Vk rappresenta la matrice documenti x concetti e va moltiplicarla per Sk.
Documenti e termini vengono proiettati tutti in un medesimo spazio a dimensionalità ridotta (diciamo lo spazio dei concetti). Ora se tu fai un clustering dei documenti in questo spazio, puoi determinare il centroide di ciascun cluster di documenti e quindi cercare i termini più vicini al centroide, oppure clusterizzare contemporaneamente termini e documenti.