Открытие истины - Truth discovery

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Когда родился Джордж Вашингтон?

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

Кто написал «Природу пространства и времени»?

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

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

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

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

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

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

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

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

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

Голосование большинством

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

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

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

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

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

Байесовский

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

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

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

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

Методы мульти-истины

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

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

На основе байесовского

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

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

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

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

Приложения

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

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

Смотрите также

• Интеграция данных
• Информационная интеграция
• Слияние данных (интеграция данных)
• Качество данных

Рекомендации

1. Ли, Ялянь; Гао, Цзин; Мэн, Чуйши; Ли, Ци; Су, Лу; Чжао, Бо; Фан, Вэй; Хан, Цзявэй (2016-02-25). «Обзор истины». Информационный бюллетень ACM SIGKDD Explorations. 17 (2): 1–16. Дои:10.1145/2897350.2897352.
2. Ван, Сяньчжи; Sheng, Quan Z .; Фанг, Сю Сьюзи; Яо, Лина; Сюй, Сяофэй; Ли, Сюэ (2015). «Интегрированный байесовский подход для эффективного обнаружения множественной истины». Материалы 24-й конференции ACM International по управлению информацией и знаниями - CIKM '15. Мельбурн, Австралия: ACM Press: 493–502. Дои:10.1145/2806416.2806443. HDL:2440/110033. ISBN  9781450337946.
3. Lin, Xueling; Чен, Лэй (2018). «Обнаружение множественной правды с учетом предметной области из конфликтующих источников». Фонд VLDB. 11 (5): 635–647. Дои:10.1145/3187009.3177739.
4. Дун, Синь Луна; Шривастава, Дивеш (15.02.2015). «Интеграция больших данных». Обобщающие лекции по управлению данными. 7 (1): 1–198. Дои:10.2200 / S00578ED1V01Y201404DTM040. ISSN  2153-5418.
5. Ли, Сиань; Дун, Синь Луна; Лайонс, Кеннет; Мэн, Вэйи; Шривастава, Дивеш (2012-12-01). «Поиск истины в глубокой сети: проблема решена?». Труды эндаумента VLDB. 6 (2): 97–108. arXiv:1503.00303. Дои:10.14778/2535568.2448943.
6. Нг, Эндрю Y; Джордан, Майкл И. (2001). «О дискриминирующих и генеративных классификаторах: сравнение логистической регрессии и наивного Байеса». Материалы 14-й Международной конференции по системам обработки нейронной информации: естественные и синтетические.: 841–848.
7. Дун, Синь Луна; Берти-Эквилль, Лора; Шривастава, Дивеш (01.08.2009). «Интеграция противоречивых данных: роль зависимости от источника». Труды эндаумента VLDB. 2 (1): 550–561. Дои:10.14778/1687627.1687690.
8. Клейнберг, Джон М. (1999-09-01). «Авторитетные источники в среде с гиперссылками». Журнал ACM. 46 (5): 604–632. Дои:10.1145/324133.324140.
9. Галланд, Албан; Абитебул, Серж; Мариан, Амели; Сенелларт, Пьер (2010). «Подтверждающая информация из несогласных взглядов». Материалы третьей международной конференции ACM по веб-поиску и интеллектуальному анализу данных - WSDM '10. Нью-Йорк, Нью-Йорк, США: ACM Press: 131. Дои:10.1145/1718487.1718504. ISBN  9781605588896.
10. Сяосинь Инь; Цзявэй Хан; Ю. П.С. (2008). «Открытие истины с множеством конфликтующих поставщиков информации в Интернете». IEEE Transactions по разработке знаний и данных. 20 (6): 796–808. Дои:10.1109 / TKDE.2007.190745. ISSN  1041-4347.
11. Чжао, Бо; Рубинштейн, Бенджамин И. П .; Геммелл, Джим; Хан, Цзявэй (01.02.2012). «Байесовский подход к обнаружению истины из конфликтующих источников для интеграции данных». Труды эндаумента VLDB. 5 (6): 550–561. arXiv:1203.0058. Дои:10.14778/2168651.2168656.
12. «Огромные последствия идеи Google ранжировать сайты на основе их точности». www.washingtonpost.com. 2015.