Truth discovery
Nell'integrazione dei dati, la truth discovery (letteralmente "definizione della verità") è il processo di selezione del valore di verità di un determinato oggetto quando sorgenti di dati diverse forniscono informazioni contrastanti su di esso.
Diversi algoritmi sono stati proposti per risolvere questo problema. Il metodo più semplice è basato sulla selezione del valore più popolare come valore di verità, altri metodi più sofisticati danno una stima dell'attendibilità delle varie sorgenti di dati allo scopo di ottenere un risultato più accurato.[1]
I problemi di truth discovery possono essere suddivisi in due sottoclassi: single-truth discovery e multi-truth discovery. Nel primo caso ad ogni oggetto è associato un solo valore di verità (ad esempio il compleanno di una persona, o la capitale di un paese). Mentre nel secondo caso ad ogni oggetto sono associati più valori di verità (ad esempio il cast di un film o gli autori di un libro).[2][3]
In genere, la fase di truth discovery è l'ultimo passo da svolgere durante l'integrazione dei dati, quando gli schemi di diverse sorgenti di dati sono stati unificati e i record che si riferiscono allo stesso oggetto sono stati identificati.[4]
Principi generali[modifica | modifica wikitesto]
L'abbondanza di dati disponibili sul web rende sempre più probabile l'eventualità di incorrere in fonti diverse che forniscono valori discordanti (parzialmente o completamente) per lo stesso oggetto. Il fatto che oggigiorno ci affidiamo sempre più ai dati trovati in rete per prendere decisioni importanti rende indispensabile lo sviluppo affidabili algoritmi di truth discovery.[5]
Molti metodi attualmente disponibili utilizzano una strategia basata sul voto per definire il valore di verità di un oggetto. Tuttavia, studi recenti su dataset appartenenti a domini diversi hanno dimostrato che, se assumiamo come verità il valore più popolare, si potrebbe ottenere un valore non corretto nel 30% dei casi.[5]
La soluzione a questo problema è valutare l'attendibilità delle fonti e dare più importanza ai voti provenienti da fonti attendibili.[4][5]
Single-truth e multi-truth discovery[modifica | modifica wikitesto]
Le tecniche utilizzate per risolvere i problemi single-truth sono molto diverse da quelle utilizzate per risolvere i problemi multi-truth.[2]
I problemi single-truth sono caratterizzati dalle seguenti proprietà:
- consentono un solo valore di verità per ogni oggetto;
- valori diversi forniti per un oggetto si oppongono l'un l'altro;
- i valori e le sorgenti possono essere corretti o errati.
Mentre, nel caso multi-truth, valgono le seguenti proprietà:
- la verità è composta da un insieme di valori;
- valori diversi potrebbero fornire una verità parziale;
- fornire un valore per un dato oggetto non implica l'opposizione a tutti gli altri valori;
- il numero di valori di verità per ogni oggetto non è noto a priori.
Il caso multi-truth ha caratteristiche uniche che rendono il problema più complesso e dovrebbero essere prese in considerazione quando si sviluppano soluzioni di truth discovery.[2]
Gli esempi qui di seguito evidenziano le principali differenze tra i due metodi. Sapendo che in entrambi gli esempi la verità è fornita dalla fonte 1, nel caso single-truth (prima tabella) possiamo dedurre che le fonti 2 e 3 si oppongono alla verità e quindi forniscono valori errati; d'altra parte, nel secondo caso (seconda tabella), le fonti 2 e 3 non sono né corrette né errate, bensì forniscono un sottoinsieme dei valori di verità (verità parziale).
| Sorgente | Nome | Data di nascita | |
|---|---|---|---|
| S1 | George Washington | 22-02-1732 | Corretto |
| S2 | George Washington | 17-09-1738 | Errato |
| S3 | George Washington | 23-10-1734 | Errato |
| Sorgente | Titolo | Autori | |
|---|---|---|---|
| S1 | La natura dello spazio e del tempo | Stephen Hawking, Roger Penrose | Corretto |
| S2 | La natura dello spazio e del tempo | Stephen Hawking | Verità parziale |
| S3 | La natura dello spazio e del tempo | Roger Penrose | Verità parziale |
| S4 | La natura dello spazio e del tempo | J. K. Rowling | Errato |
Attendibilità delle sorgenti[modifica | modifica wikitesto]
La maggioranza dei metodi di truth-discovery utilizzano una strategia basata sul voto: le fonti votano per i valori di un oggetto e, alla fine, il valore che ottiene più voti viene selezionato come valore di verità. Nei metodi più sofisticati, i voti non hanno lo stesso peso per tutte le sorgenti, maggiore importanza è data ai voti provenienti da fonti attendibili.[5]
L'attendibilità delle fonti di solito non è nota a priori ma è valutata attraverso un approccio iterativo. Ad ogni passo dell'algoritmo di truth discovery il punteggio di attendibilità di ciascuna sorgente viene aggiornato, migliorando la valutazione dei valori di verità che a sua volta porta ad una stima migliore dell'attendibilità delle fonti. Questo processo di solito termina quando tutti i valori raggiungono uno stato di convergenza.[5]
L'attendibilità delle sorgenti può essere basata su metriche diverse, come l'accuratezza dei valori forniti, il fatto che una sorgente copi dei valori da altre sorgenti e la copertura del dominio.[1]
Identificare i valori copiati è molto importante, infatti la copia consente di diffondere i valori falsi molto facilmente e questo può rendere molto difficile la scoperta della verità poiché molte fonti potrebbero votare per i valori sbagliati. In molti sistemi l'importanza dei voti associati ai valori copiati viene ridotta o non vengono presi in considerazione.[6]
Metodi single-truth[modifica | modifica wikitesto]
La maggior parte dei metodi di truth-discovery attualmente disponibili sono stati progettati per funzionare solo nel caso single-truth.[1][3]
Di seguito sono riportate alcune delle caratteristiche più rilevanti di alcune tipologie dei metodi single-truth e, in particolare, viene presentato in che modo i diversi sistemi stimano l'attendibilità delle sorgenti di dati.[5]
Majority voting[modifica | modifica wikitesto]
Selezionare il valore più popolare come valore di verità è il metodo truth-discovery più semplice. Questo metodo viene spesso usato come base per valutare le prestazioni di metodi più complessi.
Web-link[modifica | modifica wikitesto]
Questi metodi stimano l'attendibilità della fonte sfruttando una tecnica simile a quella utilizzata per misurare l'autorità delle pagine Web in base ai collegamenti tra le pagine. Il voto assegnato ad un valore è calcolato come la somma dell'attendibilità delle fonti che forniscono quel particolare valore, mentre l'attendibilità di una fonte è calcolata come la somma dei voti assegnati ai valori che fornisce.[5][7]
Information-retrieval[modifica | modifica wikitesto]
Questi metodi stimano l'attendibilità della fonte utilizzando misure di similarità tipicamente utilizzate in information-retrieval. L'attendibilità della fonte è stimata calcolando la cosine similarity (o altre misure di similarità) tra l'insieme di valori forniti dalla sorgente e l'insieme di valori considerati veri (selezionati in modo probabilistico oppure ottenuti da un dataset manualmente annotato).[5][8]
Bayesian[modifica | modifica wikitesto]
Questi metodi utilizzano l'inferenza bayesiana per definire la probabilità che un valore sia vero sulla base dei valori forniti da tutte le sorgenti.
dove è un valore fornito per un oggetto e è l'insieme dei valori forniti delle sorgenti per quello specifico oggetto.
L'attendibilità di una fonte viene quindi calcolata sulla base dell'accuratezza dei valori che fornisce.[6][9] Altri metodi più complessi sfruttano l'inferenza bayesiana per rilevare comportamenti di copia e utilizzano queste informazioni per valutare meglio l'attendibilità delle fonti.[6]
Metodi multi-truth[modifica | modifica wikitesto]
A causa della complessità dei problemi multi-truth, meno attenzione è stata dedicata al loro studio.[2][3]
Di seguito sono riportate alcune delle caratteristiche di due tipologie di metodi multi-truth.
Bayesiani[modifica | modifica wikitesto]
Questi metodi utilizzano l'inferenza bayesiana per definire la probabilità che un gruppo di valori sia vero sulla base dei valori forniti da tutte le sorgenti di dati. In questo caso, poiché potrebbero esistere più valori di verità per ogni oggetto, e le sorgenti possono fornire più valori per un singolo oggetto, non è possibile considerare i valori singolarmente; è necessario applicare procedure di mapping e valutare le relazioni tra i valori forniti e le fonti che li forniscono. L'attendibilità di una fonte viene poi calcolata in base all'accuratezza dei valori forniti.[2]
Metodi più sofisticati considerano anche la copertura di dominio e i comportamenti di copia per meglio stimare l'attendibilità delle fonti.[2][3]
Modelli probabilistici geografici[modifica | modifica wikitesto]
Questi metodi utilizzano modelli grafici probabilistici per definire automaticamente l'insieme dei valori corretti di un determinato oggetto e valutare la qualità della sorgente.[10]
Applicazioni[modifica | modifica wikitesto]
Molte applicazioni possono trarre vantaggio dall'uso di algoritmi di truth discovery. Ambiti di applicazione tipici comprendono: healthcare, crowd/social sensing, crowdsourcing, estrazione di informazioni e costruzione di knowledge base.[1]
Gli algoritmi di truth discovery potrebbero anche essere usati per rivoluzionare il modo in cui le pagine web sono classificate dai motori di ricerca, sostituendo i metodi attuali basati sull'analisi dei link come PageRank, con procedure che classificano le pagine web sulla base all'accuratezza delle informazioni che forniscono.[11]
Note[modifica | modifica wikitesto]
- ^ a b c d (EN) Yaliang Li, Jing Gao, Chuishi Meng, Qi Li, Lu Su, Bo Zhao, Wei Fan e Jiawei Han, A Survey on Truth Discovery, in ACM SIGKDD Explorations Newsletter, vol. 17, n. 2, 25 febbraio 2016, pp. 1-16, DOI:10.1145/2897350.2897352.
- ^ a b c d e f (EN) Xianzhi Wang, Quan Z. Sheng, Xiu Susie Fang, Lina Yao, Xiaofei Xu e Xue Li, An Integrated Bayesian Approach for Effective Multi-Truth Discovery, in Proceedings of the 24th ACM International on Conference on Information and Knowledge Management - CIKM '15, Melbourne, Australia, ACM Press, 2015, pp. 493-502, DOI:10.1145/2806416.2806443, ISBN 978-1-4503-3794-6.
- ^ a b c d Xueling Lin e Lei Chen, Domain-aware Multi-truth Discovery from Conflicting Sources, in VLDB Endowment, vol. 11, 2018, pp. 635--647, DOI:10.1145/3187009.3177739.
- ^ a b (EN) Xin Luna Dong e Divesh Srivastava, Big Data Integration, in Synthesis Lectures on Data Management, vol. 7, n. 1, 15 febbraio 2015, pp. 1-198, DOI:10.2200/S00578ED1V01Y201404DTM040, ISSN 2153-5418.
- ^ a b c d e f g h (EN) Xian Li, Xin Luna Dong, Kenneth Lyons, Weiyi Meng e Divesh Srivastava, Truth finding on the deep web: is the problem solved?, in Proceedings of the VLDB Endowment, vol. 6, n. 2, 1º dicembre 2012, pp. 97-108, DOI:10.14778/2535568.2448943.
- ^ a b c (EN) Xin Luna Dong, Laure Berti-Equille e Divesh Srivastava, Integrating conflicting data: the role of source dependence, in Proceedings of the VLDB Endowment, vol. 2, n. 1, 1º agosto 2009, pp. 550-561, DOI:10.14778/1687627.1687690.
- ^ Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, in Journal of the ACM, vol. 46, n. 5, 1º settembre 1999, pp. 604-632, DOI:10.1145/324133.324140.
- ^ (EN) Alban Galland, Serge Abiteboul, Amélie Marian e Pierre Senellart, Corroborating information from disagreeing views, in Proceedings of the third ACM international conference on Web search and data mining - WSDM '10, New York, New York, USA, ACM Press, 2010, p. 131, DOI:10.1145/1718487.1718504, ISBN 978-1-60558-889-6.
- ^ Xiaoxin Yin, Jiawei Han e P.S. Yu, Truth Discovery with Multiple Conflicting Information Providers on the Web, in IEEE Transactions on Knowledge and Data Engineering, vol. 20, n. 6, 2008, pp. 796-808, DOI:10.1109/TKDE.2007.190745, ISSN 1041-4347.
- ^ (EN) Bo Zhao, Benjamin I. P. Rubinstein, Jim Gemmell e Jiawei Han, A Bayesian approach to discovering truth from conflicting sources for data integration, in Proceedings of the VLDB Endowment, vol. 5, n. 6, 1º febbraio 2012, pp. 550-561, DOI:10.14778/2168651.2168656.
- ^ The huge implications of Google's idea to rank sites based on their accuracy, su washingtonpost.com, 2015.