Слияние убеждений

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

Подходы

Комбинация

В комбинированном подходе мы берем объединение баз знаний (конечный набор логических формул). Если объединение согласовано, то все готово. В противном случае мы выбираем некоторое максимально согласованное его подмножество. Барал, Краус , Минкер и Субрахманян [5] [2] представляют алгоритмы для объединения баз знаний, состоящих из теорий первого порядка , и для разрешения несоответствий между ними. Субрахманян [3] представляет единую теоретическую структуру, основанную на аннотированных логиках , для объединения нескольких баз знаний, которые могут иметь несоответствия, неопределенности и немонотонные режимы отрицания.

Арбитраж

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

Слияние

Подход слияния был представлен Конечны и Пересом. [8] Существует несколько различий между операторами комбинирования и операторами слияния: [9]

  • Объединение зависит от синтаксиса, тогда как слияние основано на принципе нерелевантности синтаксиса: операция над двумя эквивалентными базами данных должна возвращать две эквивалентные базы данных.
  • Операторы комбинирования игнорируют информацию об источнике баз знаний, поэтому они не могут учитывать количество экспертов, поддерживающих каждое предложение. В частности, они не могут принимать решения на основе большинства голосов экспертов.

Конечны и Перес [10] [11] [12] расширили свою структуру до слияния в рамках набора экзогенно наложенных ограничений, которые должны быть удовлетворены объединенной базой данных. Их структура теперь является стандартной структурой для слияния убеждений. [13] В их структуре оператор слияния является функцией f , которая принимает в качестве входных данных вектор из n непротиворечивых (выполнимых) пропозициональных формул , P=( p 1 ,..., p n ), представляющих, например, утверждения, сделанные n различными экспертами, и другую формулу c , представляющую ограничения. Она должна удовлетворять следующим постулатам:

  • IC0: f(P,c) моделирует c. [это означает, что объединенный выход удовлетворяет ограничению]
  • IC1: Если c непротиворечиво , то f(P,c) непротиворечиво.
  • IC2: Если логическая конъюнкция p 1 , ..., p n, c является последовательной, то f(P,c) равна этой логической конъюнкции.
  • IC3: если P 1 эквивалентно P 2 и c 1 эквивалентно c 2 , то f(P 1 ,c 1 ) эквивалентно f(P 2 ,c 2 ). [это означает, что слияние не зависит от синтаксиса ]
  • IC4: если p 1 моделирует c и p 2 моделирует c, то логическая конъюнкция f(p 1 ,p 2 ,c) и p 1 непротиворечива тогда и только тогда, когда логическая конъюнкция f(p 1 ,p 2 ,c) и p 2 непротиворечива.
  • IC5: Сочетание f(P 1 ,c) и f(P 2 ,c) моделирует f(P 1 +P 2 ,c).
  • IC6: Если конъюнкция f(P 1 ,c) и f(P 2 ,c) согласована, то f(P 1 +P 2 ,c) моделирует ее.
  • IC7: Конъюнкция f(P,c 1 ) и c 2 моделирует f(P, конъюнкция c 1 и c 2 ).
  • IC8: Если конъюнкция f(P,c 1 ) и c 2 является согласованной, то f(P, конъюнкция c 1 и c 2 ) моделирует ее.

Они представляют несколько операторов, которые удовлетворяют всем этим свойствам, например:

Конечны, Ланг и Маркиз [14] представляют структуру DA 2 , которая обобщает структуру слияния. Они доказывают, что в этой структуре вывод запросов из слитых баз происходит только на первом уровне полиномиальной иерархии .

Слияние убеждений и социальный выбор

Слияние убеждений в некоторой степени связано с социальным выбором , в котором мнения разных граждан должны быть объединены в единое «социальное» мнение. Мейер, Гош и Чопра [15] связывают слияние убеждений с социальным выбором, выборами и агрегацией предпочтений.

Чпора, Гош и Мейер [16] связывают слияние убеждений с стратегической устойчивостью . Они показывают, что теорема Эрроу о невозможности и теорема Гиббарда-Саттертуэйта не выполняются в их структуре слияния убеждений.

Эверер, Конечны и Маркиз [17] изучают операторов слияния убеждений в условиях, когда различные источники информации являются стратегическими и могут попытаться изменить свои заявленные убеждения, чтобы повлиять на результат. Они изучают операторы слияния, не поддающиеся стратегии.

Харет и Валлнер [18] показывают, что большинство процедур агрегации поддаются манипулированию, и изучают вычислительную сложность поиска манипуляции.

Харет, Пфандлер и Вольтран [19] рассматривают некоторые классические аксиомы социального выбора в контексте слияния убеждений.

Харет, Лакнер, Пфандлер и Валлнер [20] изучают операторы слияния убеждений, которые удовлетворяют свойствам справедливости, аналогичным обоснованному представлению . Для иллюстрации предположим, что три эксперта поддерживают предложения x1,x2,x3,x4 и выступают против предложений y1,y2,y3,y4, тогда как четвертый эксперт выступает против предложений x1,x2,x3,x4 и поддерживает предложения y1,y2,y3,y4. Тогда:

  • Правило утилитаризма (минимизация суммы расстояний) выберет x1,x2,x3,x4; это несправедливо по отношению к эксперту меньшинства, который вообще не представлен.
  • Правило эгалитаризма (минимизация максимальных расстояний) выберет x1,x2,y1,y2; это несправедливо по отношению к большинству экспертов, которые представлены только 2 из 4 предложений, хотя они составляют 3/4 населения.
  • Новое предлагаемое правило, основанное на пропорциональном голосовании по принципу одобрения , выберет x1,x2,x3,y1, что удовлетворяет «справедливому представительству» как для меньшинства, так и для большинства.

Голосование с несколькими победителями можно рассматривать как особый случай слияния убеждений с ограничениями, где ограничения кодируют размер комитета. [21] : Подпункт 6.7 

Формальные методы, разработанные для слияния убеждений, были применены в других областях социальной эпистемологии , таких как:

  • Групповой консенсус; [22]
  • Агрегация суждений — тесно связанный процесс, в котором несколько экспертов выражают свои собственные суждения (в виде логической формулы), а общество должно агрегировать их последовательным образом. [23]

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

  • Пересмотр убеждений — тесно связанный процесс, в ходе которого человек изменяет существующую базу знаний после получения новой и противоречивой информации.
  • Агрегация убеждений — похожий термин, но относящийся к другому процессу, в котором убеждения выражаются в виде распределений вероятностей по событиям, а цель состоит в том, чтобы объединить их в единое распределение.
  • Объединение данных датчиков — объединение данных с разных датчиков.

Ссылки

  1. ^ Элмагармид, Ахмед К.; Русинкевич, Марек; Шет, Амит (1999). Управление гетерогенными и автономными системами баз данных. Морган Кауфманн. ISBN 978-1-55860-216-8.
  2. ^ ab Барал, Читта; Краус, Сарит; Минкер, Джек; Субрахманиан, В.С. (1992-02-01). «Объединение баз знаний, состоящих из теорий первого порядка». Computational Intelligence . 8 (1): 45–71 . doi :10.1111/j.1467-8640.1992.tb00337.x. ISSN  0824-7935. S2CID  964506.
  3. ^ ab Subrahmanian, VS (1994-06-01). «Объединение баз знаний». ACM Transactions on Database Systems . 19 (2): 291– 331. doi : 10.1145/176567.176571 . ISSN  0362-5915. S2CID  15968948.
  4. ^ "Современные системы баз данных". Путеводители . Получено 2023-11-13 .
  5. ^ Барал, К.; Краус, С.; Минкер, Дж. (1991-06-01). «Объединение нескольких баз знаний». Труды IEEE по инжинирингу знаний и данных . 3 (2): 208– 220. doi :10.1109/69.88001. ISSN  1041-4347.
  6. ^ Ревес, Питер З. (1993-08-01). "О семантике изменения теории: арбитраж между старой и новой информацией". Труды двенадцатого симпозиума ACM SIGACT-SIGMOD-SIGART по принципам систем баз данных - PODS '93 . Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники. стр.  71–82 . doi :10.1145/153850.153857. ISBN 978-0-89791-593-9. S2CID  2627403.
  7. ^ Либераторе, П.; Шаерф, М. (1998). «Арбитраж (или как объединить базы знаний)». Труды IEEE по инжинирингу знаний и данных . 10 (1): 76– 90. doi :10.1109/69.667090. ISSN  1041-4347. S2CID  5672503.
  8. ^ Конечный, Себастьян; Пино Перес, Рамон (1 апреля 2011 г.). «Логическое слияние». Журнал философской логики . 40 (2): 239–270 . doi : 10.1007/s10992-011-9175-5. ISSN  1573-0433. S2CID  1458423.
  9. ^ Конечны, Себастьен (2000-04-11). «О различии между слиянием баз знаний и их объединением». Труды Седьмой международной конференции по принципам представления и обоснования знаний . KR'00. Сан-Франциско, Калифорния, США: Morgan Kaufmann Publishers Inc.: 135–144 .
  10. ^ Konieczny, Sébastien; Pérez, Ramón Pino (1999). «Слияние с ограничениями целостности». В Hunter, Anthony; Parsons, Simon (ред.). Symbolic and Quantitative Approaches to Reasoning and Uncertainty . Lecture Notes in Computer Science. Vol. 1638. Berlin, Heidelberg: Springer. pp.  233– 244. doi :10.1007/3-540-48747-6_22. ISBN 978-3-540-48747-0.
  11. ^ Конечны, С. (2002-10-01). «Объединение информации при ограничениях: логическая структура». Журнал логики и вычислений . 12 (5): 773– 808. doi :10.1093/logcom/12.5.773.
  12. ^ Конечны, Себастьен; Пино Перес, Рамон (2005-02-01). «Слияние баз пропозициональных убеждений или как объединить убеждения/цели, исходящие из нескольких источников, и некоторые связи с теорией социального выбора». Европейский журнал операционных исследований . Анализ решений и искусственный интеллект. 160 (3): 785– 802. doi :10.1016/j.ejor.2003.06.039. ISSN  0377-2217.
  13. ^ Пигоцци, Габриэлла (2015-07-08). «Слияние убеждений и агрегация суждений». {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  14. ^ Konieczny, S; Lang, J; Marquis, P (2004-08-01). "Операторы слияния DA2". Искусственный интеллект . Немонотонные рассуждения. 157 (1): 49–79 . doi : 10.1016/j.artint.2004.04.008 . ISSN  0004-3702.
  15. ^ Мейер, Томас; Гош, Адитья; Чопра, Самир (2001). «Социальный выбор, слияние и выборы». В Бенферхат, Салем; Беснард, Филипп (ред.). Символические и количественные подходы к рассуждению с неопределенностью . Конспект лекций по информатике. Том 2143. Берлин, Гейдельберг: Springer. стр.  466– 477. doi :10.1007/3-540-44652-4_41. ISBN 978-3-540-44652-1.
  16. ^ Чопра, Самир; Гош, Адитья; Мейер, Томас (2006-03-01). «Теория социального выбора, слияние убеждений и устойчивость к стратегиям». Слияние информации . Логические подходы к слиянию информации. 7 (1): 61– 79. doi :10.1016/j.inffus.2005.05.003. ISSN  1566-2535.
  17. ^ Эверэр, П.; Конечный, С.; Маркиз, П. (6 февраля 2007 г.). «Стратегическая устойчивость слияний». Журнал исследований искусственного интеллекта . 28 : 49–105 . arXiv : 1110.2766 . дои : 10.1613/jair.2034 . ISSN  1076-9757. S2CID  2559616.
  18. ^ Харет, Адриан; Валлнер, Йоханнес П. (2019). «Манипулирование скептическими и доверчивыми последствиями при слиянии убеждений». В Calimeri, Francesco; Leone, Nicola; Manna, Marco (ред.). Логика в искусственном интеллекте . Конспект лекций по информатике. Том 11468. Cham: Springer International Publishing. стр.  133– 150. doi : 10.1007/978-3-030-19570-0_9. ISBN 978-3-030-19570-0. S2CID  146807947.
  19. ^ Харет, Адриан; Пфандлер, Андреас; Вольтран, Стефан (2016-08-29). «За пределами постулатов IC: критерии классификации для слияния операторов». Труды Двадцать второй Европейской конференции по искусственному интеллекту . ECAI'16. NLD: IOS Press: 372– 380. doi :10.3233/978-1-61499-672-9-372. ISBN 978-1-61499-671-2.
  20. ^ Харет, Адриан; Лакнер, Мартин; Пфандлер, Андреас; Валлнер, Йоханнес П. (2020-04-03). «Пропорциональное слияние убеждений». Труды конференции AAAI по искусственному интеллекту . 34 (3): 2822– 2829. doi : 10.1609/aaai.v34i03.5671 . ISSN  2374-3468.
  21. ^ Лакнер, Мартин; Сковрон, Петр (2023). Голосование за нескольких победителей с предпочтениями одобрения. Springer Nature. hdl :20.500.12657/60149. ISBN 978-3-031-09016-5.
  22. ^ Gauwin, Olivier; Konieczny, Sébastien; Marquis, Pierre (2005). «Conciliation and Consensus in Iterated Belief Merging». В Godo, Lluís (ред.). Symbolic and Quantitative Approaches to Reasoning with Uncertainty (PDF) . Lecture Notes in Computer Science. Vol. 3571. Berlin, Heidelberg: Springer. pp.  514– 526. doi :10.1007/11518655_44. ISBN 978-3-540-31888-0.
  23. ^ Пигоцци, Габриэлла (2006-09-01). «Слияние убеждений и дискурсивная дилемма: аргументированный отчет о парадоксах агрегации суждений». Synthese . 152 (2): 285– 298. doi :10.1007/s11229-006-9063-7. ISSN  1573-0964. S2CID  18001376.
Взято с "https://en.wikipedia.org/w/index.php?title=Слияние_верований&oldid=1247314598"