Открытие истины

Открытие истины (также известное как поиск истины ) — это процесс выбора фактического истинного значения для элемента данных , когда разные источники данных предоставляют о нем противоречивую информацию.

несколько алгоритмов Для решения этой проблемы было предложено : от простых методов, таких как голосование большинством , до более сложных, позволяющих оценить достоверность источников данных . ^[1]

Проблемы обнаружения истины можно разделить на два подкласса: с одной истиной и с множественной истиной. допускается только одно истинное значение В первом случае для элемента данных (например, день рождения человека, столица страны). Во втором случае допускается несколько истинных значений (например, актерский состав фильма, авторы книги). ^[2]^[3]

Обычно обнаружение истины является последним шагом конвейера интеграции данных , когда схемы различных источников данных унифицированы элементу записи, относящиеся к одному и тому же данных . и обнаружены ^[4]

Общие принципы

Обилие данных, доступных в сети, делает все более вероятным обнаружение того, что разные источники предоставляют (частично или полностью) разные значения для одного и того же элемента данных . Это, а также тот факт, что мы все больше полагаемся на данные для принятия важных решений, мотивирует необходимость разработки хороших алгоритмов обнаружения истины . ^[5]

Многие доступные в настоящее время методы основаны на стратегии голосования для определения истинного значения элемента данных . Тем не менее, недавние исследования показали, что, если мы будем полагаться только на голосование большинства , мы можем получить неправильные результаты даже по 30% элементов данных . ^[5]

Решение этой проблемы состоит в том, чтобы оценить достоверность источников и придать большее значение голосам, поступающим из доверенных источников. ^[4]^[5]

В идеале, методы контролируемого обучения можно было бы использовать для присвоения оценки надежности источникам после ручной маркировки предоставленных значений; к сожалению, это неосуществимо, поскольку количество необходимых размеченных примеров должно быть пропорционально количеству источников , а во многих приложениях количество источников может быть непомерно высоким. ^[2]^[6]

Открытие единой истины и множественной истины

Открытие единой истины и множественной истины — две совершенно разные проблемы. ^[2]

Открытие единой истины характеризуется следующими свойствами:

допускается только одно истинное значение для каждого элемента данных ;
разные значения, предусмотренные для данного элемента данных, противостоят друг другу;
значения и источники могут быть как правильными, так и ошибочными.

В то время как в случае множественной истины сохраняются следующие свойства:

истина состоит из набора ценностей;
разные ценности могут обеспечить частичную истину;
утверждение одного значения для данного элемента данных не означает противопоставления всем остальным значениям;
количество истинных значений для каждого элемента данных неизвестно . заранее

Обнаружение множественной истины имеет уникальные особенности, которые усложняют проблему и должны учитываться при разработке решений по обнаружению истины. ^[2]

В приведенных ниже примерах показаны основные различия двух методов. Зная, что в обоих примерах истина предоставляется источником 1, в случае единственной истины (первая таблица) мы можем сказать, что источники 2 и 3 противоречат истине и в результате предоставляют неверные значения. С другой стороны, во втором случае (вторая таблица) источники 2 и 3 не являются ни правильными, ни ошибочными, а дают подмножество истинных значений и в то же время не противоречат истине.

Когда родился Джордж Вашингтон?
Источник	Имя	Дата рождения
С1	Джордж Вашингтон	1732-02-22	Правильный
С2	Джордж Вашингтон	1738-09-17	Ошибочный
S3	Джордж Вашингтон	1734-10-23	Ошибочный

Кто написал «Природу пространства и времени»?
Источник	Заголовок	Авторы
С1	Природа пространства и времени	Стивен Хокинг , Роджер Пенроуз	Правильный
С2	Природа пространства и времени	Стивен Хокинг	Частичная правда
S3	Природа пространства и времени	Роджер Пенроуз	Частичная правда
С4	Природа пространства и времени	Дж. К. Роулинг	Ошибочный

Надежность источника

Подавляющее большинство методов установления истины основано на подходе голосования: каждый источник голосует за значение определенного элемента данных , и в конце значение, набравшее наибольшее количество голосов, выбирается как истинное. В более сложных методах голоса не имеют одинакового веса для всех источников данных , большее значение действительно придается голосам, поступающим из надежных источников. ^[5]

Надежность источника обычно неизвестна априори , но оценивается с помощью итеративного подхода. На каждом этапе алгоритма обнаружения истины оценка достоверности каждого источника данных уточняется, улучшая оценку истинных значений, что, в свою очередь, приводит к лучшей оценке достоверности источников. Этот процесс обычно заканчивается, когда все значения достигают состояния сходимости. ^[5]

Надежность источника может основываться на различных показателях, таких как точность предоставленных значений, копирование значений из других источников и покрытие домена. ^[1]

Обнаружение копирующего поведения очень важно, на самом деле копирование позволяет легко распространять ложные ценности, что очень затрудняет обнаружение истины, поскольку многие источники будут голосовать за неправильные ценности. Обычно системы уменьшают вес голосов, связанных с скопированными значениями, или даже не учитывают их вообще. ^[7]

Методы единой истины

Большинство доступных в настоящее время методов обнаружения истины были разработаны так, чтобы хорошо работать только в случае единственной истины. ^[1]^[3]

Ниже приводятся некоторые характеристики наиболее актуальных типологий методов единой истины и то, как различные системы моделируют надежность источника. ^[5]

Большинство голосов

Голосование большинством – самый простой метод, в качестве истинного выбирается наиболее популярное значение. Голосование большинством обычно используется в качестве отправной точки при оценке эффективности более сложных методов.

на основе веб-ссылок

Эти методы оценивают надежность источника, используя метод, аналогичный тому, который используется для измерения авторитетности веб -страниц на основе веб-ссылок . Голосование, присвоенное значению, рассчитывается как сумма достоверности источников, предоставляющих это конкретное значение, а достоверность источника рассчитывается как сумма голосов, присвоенных значениям, которые предоставляет источник. ^[5]^[8]

Информационно-поисковый

Эти методы оценивают надежность источника, используя меры сходства, обычно используемые при поиске информации . Достоверность источника рассчитывается как косинусное сходство (или другие меры сходства ) между набором значений, предоставленных источником, и набором значений, считающихся истинными (либо выбранных вероятностным способом, либо полученных на основе достоверных данных). ^[5]^[9]

Байесовский подход

Эти методы используют байесовский вывод для определения вероятности истинности значения при условии, что значения предоставлены всеми источниками.

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

где $\textstyle v$ значение, предоставленное для элемента данных $\textstyle o$ и $\textstyle \psi (o)$ представляет собой набор наблюдаемых значений, предоставленных всеми источниками для этого конкретного элемента данных .

Затем надежность источника рассчитывается на основе точности предоставляемых значений. ^[7]^[10] Другие, более сложные методы используют байесовский вывод для обнаружения поведения копирования и используют эту информацию для лучшей оценки достоверности источника. ^[7]

Методы множественной истины

Из-за своей сложности изучению открытия множественной истины уделялось меньше внимания. ^[2]^[3]

Ниже представлены две типологии методов множественной истины и их характеристики.

Байесовский подход

Эти методы используют байесовский вывод для определения вероятности истинности группы значений при условии, что значения предоставлены всеми источниками данных . может существовать несколько истинных значений В этом случае, поскольку для каждого элемента данных , а источники могут предоставлять несколько значений для одного элемента данных, рассматривать значения по отдельности невозможно. Альтернативой является рассмотрение отображений и отношений между набором предоставленных значений и источниками, предоставляющими их. Затем надежность источника рассчитывается на основе точности предоставляемых значений. ^[2]

Более сложные методы также учитывают покрытие домена и поведение копирования, чтобы лучше оценить надежность источника. ^[2]^[3]

Вероятностные графические модели на основе

Эти методы используют вероятностные графические модели для автоматического определения набора истинных значений данного элемента данных, а также для оценки качества источника без необходимости какого-либо контроля. ^[11]

Приложения

Многие реальные приложения могут извлечь выгоду из использования алгоритмов обнаружения истины. Типичные области применения включают: здравоохранение , массовое/социальное зондирование , агрегирование краудсорсинга , извлечение информации и построение баз знаний . ^[1]

Алгоритмы обнаружения истины также могут быть использованы для революционного изменения способа -страниц ранжирования веб в поисковых системах : от нынешних методов, основанных на анализе ссылок, таких как PageRank , до процедур, которые ранжируют веб-страницы на основе точности предоставляемой ими информации. ^[12]

См. также

Ссылки

^ Jump up to: ^а ^б ^с ^д Ци; Чжао, Бо; Хан, Цзявэй (25 февраля 2016 г.). Ли, Ялян, Цзин; Ли , Информационный бюллетень . 17 (2): 1–16. документа 10.1145 2897350.2897352 . : / Номер
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г Ван, Сяньчжи; Шэн, Цюань Цз.; Фанг, Сю Сьюзи; Яо, Лина; Сюй, Сяофэй; Ли, Сюэ (2015). «Интегрированный байесовский подход для эффективного обнаружения нескольких истин» . Материалы 24-й Международной конференции ACM по управлению информацией и знаниями . Мельбурн, Австралия: ACM Press. стр. 493–502. дои : 10.1145/2806416.2806443 . hdl : 2440/110033 . ISBN 9781450337946 . S2CID 16207808 .
^ Jump up to: ^а ^б ^с ^д Линь, Сюэлин; Чен, Лэй (2018). «Обнаружение множественной правды с учетом предметной области из конфликтующих источников». Фонд ВЛДБ . 11 (5): 635–647. дои : 10.1145/3187009.3177739 .
^ Jump up to: ^а ^б Донг, Синь Луна ; Шривастава, Дивеш (15 февраля 2015 г.). «Интеграция больших данных» . Обобщающие лекции по управлению данными . 7 (1): 1–198. дои : 10.2200/S00578ED1V01Y201404DTM040 . ISSN 2153-5418 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час Ли, Сиань; Донг, Синь Луна ; Лайонс, Кеннет; Мэн, Вэйи; Шривастава, Дивеш (1 декабря 2012 г.). «Выяснение истины в глубокой сети: решена ли проблема?». Труды Фонда VLDB . 6 (2): 97–108. arXiv : 1503.00303 . дои : 10.14778/2535568.2448943 . S2CID 3133027 .
^ Нг, Эндрю Ю; Джордан, Майкл И. (2001). «Дискриминационные и генеративные классификаторы: сравнение логистической регрессии и наивного Байеса» . Материалы 14-й Международной конференции по нейронным системам обработки информации: натуральные и синтетические : 841–848.
^ Jump up to: ^а ^б ^с Донг, Синь Луна ; Берти-Экиль, Лора; Шривастава, Дивеш (1 августа 2009 г.). «Интеграция противоречивых данных: роль зависимости от источника». Труды Фонда VLDB . 2 (1): 550–561. дои : 10.14778/1687627.1687690 . S2CID 9664056 .
^ Кляйнберг, Джон М. (1 сентября 1999 г.). «Авторитетные источники в гиперссылочной среде» . Журнал АКМ . 46 (5): 604–632. дои : 10.1145/324133.324140 . S2CID 221584113 .
^ Галланд, Альбан; Абитбул, Серж; Мариан, Амели; Сенеллар, Пьер (2010). «Подтверждающая информация из несогласных точек зрения» . Материалы третьей международной конференции ACM по веб-поиску и интеллектуальному анализу данных (PDF) . Нью-Йорк, Нью-Йорк, США: ACM Press. стр. 131–140. дои : 10.1145/1718487.1718504 . ISBN 9781605588896 . S2CID 1761360 .
^ Сяосинь Инь; Цзявэй Хан; Ю, П.С. (2008). «Обнаружение истины с помощью нескольких конфликтующих поставщиков информации в Интернете». Транзакции IEEE по знаниям и инженерии данных . 20 (6): 796–808. дои : 10.1109/TKDE.2007.190745 . ISSN 1041-4347 .
^ Чжао, Бо; Рубинштейн, Беньямин И.П.; Геммелл, Джим; Хан, Цзявэй (01 февраля 2012 г.). «Байесовский подход к раскрытию истины из противоречивых источников для интеграции данных». Труды Фонда VLDB . 5 (6): 550–561. arXiv : 1203.0058 . дои : 10.14778/2168651.2168656 . S2CID 8837716 .
^ «Огромные последствия идеи Google ранжировать сайты на основе их точности» . www.washingtonpost.com . 2015.

[:3-1] Jump up to: ^а ^б ^с ^д Ци; Чжао, Бо; Хан, Цзявэй (25 февраля 2016 г.). Ли, Ялян, Цзин; Ли , Информационный бюллетень . 17 (2): 1–16. документа 10.1145 2897350.2897352 . : / Номер

[:0-2] Jump up to: ^а ^б ^с ^д ^и ^ж ^г Ван, Сяньчжи; Шэн, Цюань Цз.; Фанг, Сю Сьюзи; Яо, Лина; Сюй, Сяофэй; Ли, Сюэ (2015). «Интегрированный байесовский подход для эффективного обнаружения нескольких истин» . Материалы 24-й Международной конференции ACM по управлению информацией и знаниями . Мельбурн, Австралия: ACM Press. стр. 493–502. дои : 10.1145/2806416.2806443 . hdl : 2440/110033 . ISBN 9781450337946 . S2CID 16207808 .

[:4-3] Jump up to: ^а ^б ^с ^д Линь, Сюэлин; Чен, Лэй (2018). «Обнаружение множественной правды с учетом предметной области из конфликтующих источников». Фонд ВЛДБ . 11 (5): 635–647. дои : 10.1145/3187009.3177739 .

[:1-4] Jump up to: ^а ^б Донг, Синь Луна ; Шривастава, Дивеш (15 февраля 2015 г.). «Интеграция больших данных» . Обобщающие лекции по управлению данными . 7 (1): 1–198. дои : 10.2200/S00578ED1V01Y201404DTM040 . ISSN 2153-5418 .

[:2-5] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час Ли, Сиань; Донг, Синь Луна ; Лайонс, Кеннет; Мэн, Вэйи; Шривастава, Дивеш (1 декабря 2012 г.). «Выяснение истины в глубокой сети: решена ли проблема?». Труды Фонда VLDB . 6 (2): 97–108. arXiv : 1503.00303 . дои : 10.14778/2535568.2448943 . S2CID 3133027 .

[6] Нг, Эндрю Ю; Джордан, Майкл И. (2001). «Дискриминационные и генеративные классификаторы: сравнение логистической регрессии и наивного Байеса» . Материалы 14-й Международной конференции по нейронным системам обработки информации: натуральные и синтетические : 841–848.

[:5-7] Jump up to: ^а ^б ^с Донг, Синь Луна ; Берти-Экиль, Лора; Шривастава, Дивеш (1 августа 2009 г.). «Интеграция противоречивых данных: роль зависимости от источника». Труды Фонда VLDB . 2 (1): 550–561. дои : 10.14778/1687627.1687690 . S2CID 9664056 .

[8] Кляйнберг, Джон М. (1 сентября 1999 г.). «Авторитетные источники в гиперссылочной среде» . Журнал АКМ . 46 (5): 604–632. дои : 10.1145/324133.324140 . S2CID 221584113 .

[9] Галланд, Альбан; Абитбул, Серж; Мариан, Амели; Сенеллар, Пьер (2010). «Подтверждающая информация из несогласных точек зрения» . Материалы третьей международной конференции ACM по веб-поиску и интеллектуальному анализу данных (PDF) . Нью-Йорк, Нью-Йорк, США: ACM Press. стр. 131–140. дои : 10.1145/1718487.1718504 . ISBN 9781605588896 . S2CID 1761360 .

[10] Сяосинь Инь; Цзявэй Хан; Ю, П.С. (2008). «Обнаружение истины с помощью нескольких конфликтующих поставщиков информации в Интернете». Транзакции IEEE по знаниям и инженерии данных . 20 (6): 796–808. дои : 10.1109/TKDE.2007.190745 . ISSN 1041-4347 .

[11] Чжао, Бо; Рубинштейн, Беньямин И.П.; Геммелл, Джим; Хан, Цзявэй (01 февраля 2012 г.). «Байесовский подход к раскрытию истины из противоречивых источников для интеграции данных». Труды Фонда VLDB . 5 (6): 550–561. arXiv : 1203.0058 . дои : 10.14778/2168651.2168656 . S2CID 8837716 .

[12] «Огромные последствия идеи Google ранжировать сайты на основе их точности» . www.washingtonpost.com . 2015.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]