Descoperirea adevărului

În integrarea datelor , descoperirea adevărului este procesul de selectare a valorii adevărului unui anumit obiect atunci când diferite surse de date furnizează informații contradictorii despre acesta.

Au fost propuși mai mulți algoritmi pentru a rezolva această problemă. Metoda mai simplă se bazează pe selectarea celei mai populare valori ca valoare de adevăr, alte metode mai sofisticate oferă o estimare a fiabilității diferitelor surse de date pentru a obține un rezultat mai precis. ^[1]

Problemele de descoperire a adevărului pot fi împărțite în două subclase: descoperirea unui singur adevăr și descoperirea cu mai multe adevăruri. În primul caz, fiecare obiect este asociat cu o singură valoare de adevăr (de exemplu ziua de naștere a unei persoane sau capitala unei țări). În timp ce în al doilea caz, mai multe valori de adevăr sunt asociate fiecărui obiect (de exemplu, distribuția unui film sau autorii unei cărți). ^[2] ^[3]

De obicei, faza de descoperire a adevărului este ultimul pas în integrarea datelor , când schemele diferitelor surse de date au fost unificate și au fost identificate înregistrări referitoare la același obiect . ^[4]

Principii generale

Abundența datelor disponibile pe web face din ce în ce mai probabilă posibilitatea de a rula în diferite surse care oferă valori discordante (parțial sau complet) pentru același obiect . Faptul că astăzi ne bazăm tot mai mult pe datele găsite pe net pentru a lua decizii importante face imperativ dezvoltarea unor algoritmi fiabili de descoperire a adevărului. ^[5]

Multe metode disponibile în prezent utilizează o strategie bazată pe vot pentru a defini valoarea adevărată a unui obiect . Cu toate acestea, studii recente asupra seturilor de date aparținând diferitelor domenii au arătat că, dacă luăm drept adevăr cea mai populară valoare, s-ar putea obține o valoare incorectă în 30% din cazuri. ^[5]

Soluția la această problemă este evaluarea fiabilității surselor și acordarea unei importanțe mai mari voturilor din surse fiabile. ^[4] ^[5]

Descoperirea adevărului unic și a adevărului multiplu

Tehnicile folosite pentru rezolvarea problemelor cu adevăr unic sunt foarte diferite de cele utilizate pentru rezolvarea problemelor cu adevăr adevărat. ^[2]

Problemele cu adevăr unic se caracterizează prin următoarele proprietăți:

ele permit o singură valoare de adevăr pentru fiecare obiect ;
diferite valori date pentru un obiect se opun reciproc;
valorile și sursele pot fi corecte sau incorecte.

În timp ce, în cazul multi-adevărului, se mențin următoarele proprietăți:

adevărul este compus dintr-un set de valori;
valori diferite ar putea oferi adevăr parțial;
furnizarea unei valori pentru un anumit obiect nu implică opoziție față de toate celelalte valori;
numărul valorilor de adevăr pentru fiecare obiect nu este cunoscut a priori.

Cazul multi-adevăr are caracteristici unice care fac problema mai complexă și ar trebui luat în considerare atunci când se dezvoltă soluții de descoperire a adevărului. ^[2]

Exemplele de mai jos evidențiază principalele diferențe dintre cele două metode. Știind că în ambele exemple adevărul este furnizat de sursa 1, în cazul adevărului unic (primul tabel) putem deduce că sursele 2 și 3 sunt opuse adevărului și, prin urmare, oferă valori incorecte; pe de altă parte, în al doilea caz (al doilea tabel), sursele 2 și 3 nu sunt nici corecte, nici incorecte, ci furnizează un subset al valorilor adevărului (adevăr parțial).

Când s-a născut George Washington?
Sursă	Nume	Data de nastere
S1	George Washington	22-02-1732	Corect
S2	George Washington	17-09-1738	Gresit
S3	George Washington	23-10-1734	Gresit

Cine a scris „Natura spațiului și a timpului”?
Sursă	Titlu	Autori
S1	Natura spațiului și a timpului	Stephen Hawking , Roger Penrose	Corect
S2	Natura spațiului și a timpului	Stephen Hawking	Adevăr parțial
S3	Natura spațiului și a timpului	Roger Penrose	Adevăr parțial
S4	Natura spațiului și a timpului	JK Rowling	Gresit

Fiabilitatea surselor

Majoritatea metodelor de descoperire a adevărului utilizează o strategie bazată pe vot: sursele votează pentru valorile unui obiect și , în cele din urmă, valoarea care obține cele mai multe voturi este selectată ca valoare de adevăr. În metodele mai sofisticate, notele nu au aceeași pondere pentru toate sursele , se acordă mai multă importanță notelor din surse fiabile. ^[5]

Fiabilitatea surselor nu este de obicei cunoscută a priori, dar este evaluată printr-o abordare iterativă. La fiecare etapă a algoritmului de descoperire a adevărului, scorul de încredere al fiecărei surse este actualizat, îmbunătățind evaluarea valorilor adevărului, ceea ce duce la o estimare mai bună a fiabilității surselor. Acest proces se încheie de obicei atunci când toate valorile ating o stare de convergență. ^[5]

Fiabilitatea surselor se poate baza pe diferite valori, cum ar fi acuratețea valorilor furnizate, faptul că o sursă copiază valori din alte surse și acoperirea domeniului. ^[1]

Identificarea valorilor copiate este foarte importantă, de fapt copierea face posibilă răspândirea foarte ușoară a valorilor false și acest lucru poate face foarte dificilă descoperirea adevărului, deoarece multe surse ar putea vota pentru valorile greșite. În multe sisteme, importanța notelor asociate cu valorile copiate este redusă sau nu este luată în considerare. ^[6]

Metode de adevăr unic

Majoritatea metodelor disponibile în prezent pentru descoperirea adevărului sunt proiectate să funcționeze numai în cazul adevărului unic. ^[1] ^[3]

Următoarele sunt câteva dintre cele mai relevante caracteristici ale unor tipuri de metode cu adevăr unic și, în special, se prezintă modul în care diferite sisteme estimează fiabilitatea surselor de date . ^[5]

Votarea majorității

Selectarea celei mai populare valori ca valoare de adevăr este cea mai simplă metodă de descoperire a adevărului. Această metodă este adesea utilizată ca bază pentru evaluarea performanței metodelor mai complexe.

Web-link

Aceste metode estimează încrederea sursei utilizând o tehnică similară cu cea utilizată pentru a măsura autoritatea paginilor web pe baza legăturilor dintre pagini. Nota atribuită unei valori este calculată ca suma fiabilității surselor care furnizează acea valoare particulară, în timp ce încrederea unei surse este calculată ca suma voturilor atribuite valorilor pe care le furnizează. ^[5] ^[7]

Recuperarea informațiilor

Aceste metode estimează fiabilitatea sursei utilizând măsuri de similaritate utilizate în mod obișnuit în recuperarea informațiilor . Fiabilitatea sursei este estimată prin calcularea similarității cosinusului (sau a altor măsuri de similaritate) între setul de valori furnizate de sursă și setul de valori considerate adevărate (selectate într-un mod probabilistic sau obținute dintr-o adnotare manuală set de date). ^[5] ^[8]

Bayesian

Aceste metode folosesc inferența bayesiană pentru a defini probabilitatea ca o valoare să fie adevărată pe baza valorilor furnizate de toate sursele.

$P(v\mid \psi (o))={\frac {P(\psi (o)\mid v)\cdot P(v)}{P(\psi (o))}}$ ${\ displaystyle P (v \ mid \ psi (o)) = {\ frac {P (\ psi (o) \ mid v) \ cdot P (v)} {P (\ psi (o))}}}$ ${\ displaystyle P (v \ mid \ psi (o)) = {\ frac {P (\ psi (o) \ mid v) \ cdot P (v)} {P (\ psi (o))}}}$

unde este $\textstyle v$ ${\ displaystyle \ textstyle v}$ ${\ displaystyle \ textstyle v}$ este o valoare furnizată pentru un obiect $\textstyle o$ ${\ displaystyle \ textstyle o}$ ${\ displaystyle \ textstyle o}$ Și $\textstyle \psi (o)$ ${\ displaystyle \ textstyle \ psi (o)}$ ${\ displaystyle \ textstyle \ psi (o)}$ este setul de valori furnizate de surse pentru acel obiect specific.

Fiabilitatea unei surse este apoi calculată pe baza acurateței valorilor pe care le furnizează. ^[6] ^[9] Alte metode mai complexe exploatează inferența bayesiană pentru a detecta comportamentul copierii și folosesc aceste informații pentru a evalua mai bine fiabilitatea surselor. ^[6]

Metode multi-adevăr

Datorită complexității problemelor multi-adevăr, s-a acordat mai puțină atenție studiului lor. ^[2] ^[3]

Iată câteva dintre caracteristicile a două tipuri de metode multi-adevăr.

Bayezieni

Aceste metode utilizează inferența bayesiană pentru a defini probabilitatea ca un set de valori să fie adevărat pe baza valorilor furnizate de toate sursele de date . În acest caz, deoarece pot exista mai multe valori de adevăr pentru fiecare obiect , iar sursele pot furniza mai multe valori pentru un singur obiect, nu este posibil să se ia în considerare valorile în mod individual; este necesar să se aplice proceduri de cartografiere și să se evalueze relațiile dintre valorile furnizate și sursele care le furnizează. Fiabilitatea unei surse este apoi calculată pe baza preciziei valorilor furnizate. ^[2]

Metodele mai sofisticate iau în considerare și acoperirea domeniului și comportamentele de copiere pentru a estima mai bine fiabilitatea surselor. ^[2] ^[3]

Modele geografice probabiliste

Aceste metode utilizează modele grafice probabilistice pentru a defini automat setul corect de valori pentru un anumit obiect și pentru a evalua calitatea sursei. ^[10]

Aplicații

Multe aplicații pot beneficia de utilizarea algoritmilor de descoperire a adevărului. Domeniile tipice de aplicare includ: asistență medicală, mulțumire / detectare socială, crowdsourcing , extragerea informațiilor și construirea bazei de cunoștințe . ^[1]

Algoritmii de descoperire a adevărului ar putea fi, de asemenea, utilizați pentru a revoluționa modul în care paginile web sunt clasificate de motoarele de căutare , înlocuind metodele actuale bazate pe analiza link-urilor , cum ar fi PageRank , cu proceduri care clasifică paginile web pe baza exactității informațiilor pe care le furnizează. ^[11]

Notă

^ ^A ^b ^c ^d (EN) Yaliang Li, Jing Gao, Chuishi Meng, Qi Li, Lu Su, Bo Zhao, Wei Fan și Jiawei Han, A Survey on Truth Discovery , în ACM SIGKDD Explorations Newsletter, vol. 17, n. 2, 25 februarie 2016, pp. 1-16, DOI : 10.1145 / 2897350.2897352 .
^ ^A ^b ^c ^d ^și ^f (EN) Xianzhi Wang, Z. Sheng Quan, Xiu Fang Susie, Lina Yao, Xu Xiaofei și Xue Li, O abordare Bayesiană integrată pentru descoperirea eficientă a mai multor adevăruri , în 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 și Lei Chen, descoperire multi-adevăr conștientă de domeniu din surse conflictuale , în VLDB Endowment , vol. 11, 2018, pp. 635-647, DOI : 10.1145 / 3187009.3177739 .
^ ^a ^b ( EN ) Xin Luna Dong și Divesh Srivastava, Big Data Integration , în Synthesis Lectures on Data Management , vol. 7, nr. 1, 15 februarie 2015, pp. 1-198, DOI : 10.2200 / S00578ED1V01Y201404DTM040 , ISSN 2153-5418 ( WC ACNP ) .
^ ^a ^b ^c ^d ^e ^f ^g ^h ( EN ) Xian Li, Xin Luna Dong, Kenneth Lyons, Weiyi Meng și Divesh Srivastava, Adevărul aflat pe deep web: problema este rezolvată? , în Proceedings of the VLDB Endowment , vol. 6, nr. 2, 1 decembrie 2012, pp. 97-108, DOI : 10.14778 / 2535568.2448943 .
^ ^a ^b ^c ( EN ) Xin Luna Dong, Laure Berti-Equille și Divesh Srivastava, Integrarea datelor conflictuale: rolul dependenței de sursă , în Proceedings of the VLDB Endowment , vol. 2, nr. 1, 1 august 2009, pp. 550-561, DOI : 10.14778 / 1687627.1687690 .
^ Jon M. Kleinberg, Surse autoritare într-un mediu hiperlegat , în Jurnalul ACM , vol. 46, nr. 5, 1 septembrie 1999, pp. 604-632, DOI : 10.1145 / 324133.324140 .
^ (EN) Alban Galland, Serge Abiteboul, Amélie Marian și Pierre Senellart, Coroborarea informațiilor din puncte de vedere dezacordate , în Proceedings of the ACM a treia conferință internațională privind căutarea pe web și extragerea datelor - WSDM '10, New York, New York, SUA, ACM Presă, 2010, p. 131, DOI : 10.1145 / 1718487.1718504 , ISBN 978-1-60558-889-6 .
^ Xiaoxin Yin, Jiawei Han și PS Yu, Truth Discovery with Multiple Conflicting Information Providers on the Web , în IEEE Transactions on Knowledge and Data Engineering , vol. 20, nr. 6, 2008, pp. 796-808, DOI : 10.1109 / TKDE.2007.190745 , ISSN 1041-4347 ( WC ACNP ) .
^ (EN) Bo Zhao, IP Benjamin Rubinstein, Jim Gemmell și Jiawei Han, O abordare bayesiană pentru descoperirea adevărului din surse conflictuale pentru integrarea datelor , în Proceedings of the VLDB Endowment, vol. 5, nr. 6, 1 februarie 2012, pp. 550-561, DOI : 10.14778 / 2168651.2168656 .
^ Implicațiile uriașe ale ideii Google de a clasifica site-urile pe baza exactității lor , www.washingtonpost.com , 2015.

Elemente conexe

[:3-1] A ^b ^c ^d (EN) Yaliang Li, Jing Gao, Chuishi Meng, Qi Li, Lu Su, Bo Zhao, Wei Fan și Jiawei Han, A Survey on Truth Discovery , în ACM SIGKDD Explorations Newsletter, vol. 17, n. 2, 25 februarie 2016, pp. 1-16, DOI : 10.1145 / 2897350.2897352 .

[:0-2] A ^b ^c ^d ^și ^f (EN) Xianzhi Wang, Z. Sheng Quan, Xiu Fang Susie, Lina Yao, Xu Xiaofei și Xue Li, O abordare Bayesiană integrată pentru descoperirea eficientă a mai multor adevăruri , în 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 .

[:4-3] Xueling Lin și Lei Chen, descoperire multi-adevăr conștientă de domeniu din surse conflictuale , în VLDB Endowment , vol. 11, 2018, pp. 635-647, DOI : 10.1145 / 3187009.3177739 .

[:1-4] ( EN ) Xin Luna Dong și Divesh Srivastava, Big Data Integration , în Synthesis Lectures on Data Management , vol. 7, nr. 1, 15 februarie 2015, pp. 1-198, DOI : 10.2200 / S00578ED1V01Y201404DTM040 , ISSN 2153-5418 ( WC ACNP ) .

[:2-5] ^ ^a ^b ^c ^d ^e ^f ^g ^h ( EN ) Xian Li, Xin Luna Dong, Kenneth Lyons, Weiyi Meng și Divesh Srivastava, Adevărul aflat pe deep web: problema este rezolvată? , în Proceedings of the VLDB Endowment , vol. 6, nr. 2, 1 decembrie 2012, pp. 97-108, DOI : 10.14778 / 2535568.2448943 .

[:5-6] ( EN ) Xin Luna Dong, Laure Berti-Equille și Divesh Srivastava, Integrarea datelor conflictuale: rolul dependenței de sursă , în Proceedings of the VLDB Endowment , vol. 2, nr. 1, 1 august 2009, pp. 550-561, DOI : 10.14778 / 1687627.1687690 .

[7] Jon M. Kleinberg, Surse autoritare într-un mediu hiperlegat , în Jurnalul ACM , vol. 46, nr. 5, 1 septembrie 1999, pp. 604-632, DOI : 10.1145 / 324133.324140 .

[8] (EN) Alban Galland, Serge Abiteboul, Amélie Marian și Pierre Senellart, Coroborarea informațiilor din puncte de vedere dezacordate , în Proceedings of the ACM a treia conferință internațională privind căutarea pe web și extragerea datelor - WSDM '10, New York, New York, SUA, ACM Presă, 2010, p. 131, DOI : 10.1145 / 1718487.1718504 , ISBN 978-1-60558-889-6 .

[9] Xiaoxin Yin, Jiawei Han și PS Yu, Truth Discovery with Multiple Conflicting Information Providers on the Web , în IEEE Transactions on Knowledge and Data Engineering , vol. 20, nr. 6, 2008, pp. 796-808, DOI : 10.1109 / TKDE.2007.190745 , ISSN 1041-4347 ( WC ACNP ) .

[10] (EN) Bo Zhao, IP Benjamin Rubinstein, Jim Gemmell și Jiawei Han, O abordare bayesiană pentru descoperirea adevărului din surse conflictuale pentru integrarea datelor , în Proceedings of the VLDB Endowment, vol. 5, nr. 6, 1 februarie 2012, pp. 550-561, DOI : 10.14778 / 2168651.2168656 .

[11] Implicațiile uriașe ale ideii Google de a clasifica site-urile pe baza exactității lor , www.washingtonpost.com , 2015.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]