Стохастическая транзитивность - Stochastic transitivity

Стохастическая транзитивность модели^[1][2][3][4] находятся стохастический версии транзитивность свойство бинарных отношений, изученное в математика. Существует несколько моделей стохастической транзитивности, которые использовались для описания вероятностей, участвующих в экспериментах парные сравнения, особенно в сценариях, где ожидается транзитивность, однако эмпирические наблюдения бинарного отношения являются вероятностными. Например, можно ожидать, что навыки игроков в спорте будут переходными, т.е. «если игрок A лучше, чем B, а B лучше, чем C, то игрок A должен быть лучше, чем C»; однако в любом конкретном матче более слабый игрок все равно может выиграть с положительной вероятностью. Точно подобранные игроки могут иметь больше шансов наблюдать эту инверсию, в то время как игроки с большими различиями в своих навыках могут видеть, что эти инверсии случаются редко. Модели стохастической транзитивности формализуют такие отношения между вероятностями (например, исхода матча) и лежащими в основе транзитивными отношениями (например, навыками игроков).

Бинарное отношение ${\textstyle \succsim }$ на съемочной площадке ${\displaystyle {\mathcal {A}}}$ называется переходный, в стандарте нестохастический смысл, если${\displaystyle a\succsim b}$ и ${\displaystyle b\succsim c}$ подразумевает ${\displaystyle a\succsim c}$для всех членов ${\displaystyle a,b,c}$ из ${\displaystyle {\mathcal {A}}}$.

Стохастик версии включают транзитивность включают:

1. Слабая стохастическая транзитивность (WST): ${\displaystyle \mathbb {P} (a\succsim b)\geq {\tfrac {1}{2}}}$ и ${\displaystyle \mathbb {P} (b\succsim c)\geq {\tfrac {1}{2}}}$ подразумевает ${\displaystyle \mathbb {P} (a\succsim c)\geq {\tfrac {1}{2}}}$, для всех ${\displaystyle a,b,c\in {\mathcal {A}}}$;^{[5]:12[6]:43rg}
2. Сильная стохастическая транзитивность (SST): ${\displaystyle \mathbb {P} (a\succsim b)\geq {\tfrac {1}{2}}}$ и ${\displaystyle \mathbb {P} (b\succsim c)\geq {\tfrac {1}{2}}}$ подразумевает ${\displaystyle \mathbb {P} (a\succsim c)\geq \max\{\mathbb {P} (a\succsim b),\mathbb {P} (b\succsim c)\}}$, для всех ${\displaystyle a,b,c\in {\mathcal {A}}}$;^[5]:12
3. Линейная стохастическая транзитивность (LST): ${\displaystyle \mathbb {P} (a\succsim b)=F(\mu (a)-\mu (b))}$, для всех ${\displaystyle a,b\in {\mathcal {A}}}$, куда ${\displaystyle F:\mathbb {R} \to [0,1]}$ есть некоторые увеличение и симметричный^{[уточнить ]} функция (называемая функция сравнения), и ${\displaystyle \mu :{\mathcal {A}}\to \mathbb {R} }$ какое-то отображение из множества ${\displaystyle {\mathcal {A}}}$ альтернатив реальной линии (называемой функция заслуг).

Пример игрушки

Мраморная игра - Предположим, двое детей, Билли и Габриэла, собирают шарики. Билли коллекционирует синие шарики и зеленые шарики Габриэлы. Когда они собираются вместе, они играют в игру, в которой смешивают все свои шарики в сумке и выбирают один случайным образом. Если выбранный шарик зеленого цвета, то выигрывает Габриэла, а если он синий, то выигрывает Билли. Если ${\displaystyle B}$ это количество синих шариков и ${\displaystyle G}$ количество зеленых шариков в сумке, тогда вероятность ${\displaystyle \mathbb {P} ({\text{Billy}}\succsim {\text{Gabriela}})}$ победы Билли над Габриэлой - это

${\displaystyle \mathbb {P} ({\text{Billy}}\succsim {\text{Gabriela}})={\frac {B}{B+G}}={\frac {e^{\ln(B)}}{e^{\ln(B)}+e^{\ln(G)}}}={\frac {1}{1+e^{\ln(G)-\ln(B)}}}}$.

В этом примере мраморная игра удовлетворяет линейной стохастической транзитивности, где функция сравнения ${\displaystyle F:\mathbb {R} \to [0,1]}$ дан кем-то ${\displaystyle F(x)={\frac {1}{1+e^{-x}}}}$ и функция заслуг ${\displaystyle \mu :{\mathcal {A}}\to \mathbb {R} }$ дан кем-то ${\displaystyle \mu (M)=\ln(M)}$, куда ${\displaystyle M}$ - количество шариков игрока. Эта игра является примером Модель Брэдли – Терри.^[7]

Приложения

• Рейтинг и рейтинг - Модели стохастической транзитивности использовались в качестве основы для нескольких методов ранжирования и рейтинга. Примеры включают Система Эло-Рейтинг используется в шахматах, го и других классических видах спорта, а также в Microsoft TrueSkill используется для игровой платформы Xbox.

• Модели психологии и рациональности - Терстонские модели^[8] (см. случай 5 в закон сравнительного суждения ), Фехнеровские модели^[3] а также Аксиома выбора Люси^[9] являются теориями, основанными на математике стохастической транзитивности. Также модели теория рационального выбора основаны на предположении о транзитивности предпочтения (видеть Полезность фон Неймана и Теоремы Дебре ), эти предпочтения, однако, часто случайным образом выявляются шумом.^[10][11][12]

• Машинное обучение и искусственный интеллект (см. Учитесь ранжировать ) - В то время как Elo и TrueSkill полагаются на конкретные модели LST, модели машинного обучения были разработаны для ранжирования без предварительного знания базовой модели стохастической транзитивности или с более слабыми, чем обычно, предположениями о стохастической транзитивности.^[13][14][15] Обучение на основе парных сравнений также представляет интерес, поскольку позволяет агентам ИИ узнать основные предпочтения других агентов.

• Теория игры - Справедливость турниров со случайным нокаутом сильно зависит от лежащей в основе модели стохастической транзитивности.^[16][17][18] Теория социального выбора также имеет основы, которые зависят от моделей стохастической транзитивности.^[19]

Связи между моделями

Положительные результаты:

1. Каждая модель, удовлетворяющая линейной стохастической транзитивности, должна также удовлетворять сильной стохастической транзитивности, которая, в свою очередь, должна удовлетворять слабой стохастической транзитивности. Это представлено как: LST ${\displaystyle \implies }$ SST${\displaystyle \implies }$WST ;
2. Поскольку модели Брэдли-Терри и Турстанская модель 5^{[уточнить ]} находятся LST модели, они также удовлетворяют SST и WST;
3. Благодаря удобству более структурированные модели^{[уточнить ]}, несколько авторов^{[1][2][3][4][20][21]} определили аксиоматику оправдания^{[уточнить ]} линейной стохастической транзитивности (и других моделей), в первую очередь Жерар Дебре показало, что^[22] : Четверное условие^{[уточнить ]} + Непрерывность^{[уточнить ]} ${\displaystyle \implies }$ LST (смотрите также Теоремы Дебре );
4. Две модели LST предоставлены обратимый функции сравнения ${\displaystyle F(x)}$ и ${\displaystyle G(x)}$ находятся эквивалент^{[уточнить ]} если и только если ${\displaystyle F(x)=G(\kappa x)}$для некоторых ${\displaystyle \kappa \geq 0.}$^[23]

Отрицательные результаты:

1. Модели стохастической транзитивности эмпирически непроверяемый^{[уточнить ]},^[4] однако они могут быть фальсифицированы;
2. Различать^{[уточнить ]} между LST функции сравнения ${\displaystyle F(x)}$ и ${\displaystyle G(x)}$ может быть невозможно, даже если бесконечное количество данных предоставляется по конечному числу точки^{[уточнить ]};^[24]
3. В проблема оценки^{[уточнить ]} за WST, SST и LST модели в целом NP-Hard, ^[25] однако известны процедуры оценивания, близкие к оптимальным, полиномиально вычислимые для SST и LST модели.^[13][14][15]

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

• Нетранзитивная игра
• Теория принятия решений
• Утилитаризм

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

1. Фишберн, Питер С. (ноябрь 1973 г.). «Вероятности двоичного выбора: о разновидностях стохастической транзитивности». Журнал математической психологии. 10 (4): 327–352. Дои:10.1016/0022-2496(73)90021-7. ISSN  0022-2496.
2. Кларк, Стивен А. (март 1990 г.). «Концепция стохастической транзитивности для случайной полезной модели». Журнал математической психологии. 34 (1): 95–108. Дои:10.1016/0022-2496(90)90015-2.
3. Райан, Мэтью (21 января 2017). «Неопределенность и бинарный стохастический выбор». Экономическая теория. 65 (3): 629–662. Дои:10.1007 / s00199-017-1033-4. ISSN  0938-2259. S2CID  125420775.
4. Oliveira, I.F.D .; Zehavi, S .; Давыдов, О. (август 2018). «Стохастическая транзитивность: аксиомы и модели». Журнал математической психологии. 85: 25–35. Дои:10.1016 / j.jmp.2018.06.002. ISSN  0022-2496.
5. Дональд Дэвидсон и Джейкоб Маршак (июль 1958 г.). Экспериментальные проверки теории стохастических решений (PDF) (Технический отчет). Стэндфордский Университет.
6. Мишель Регенветтер, Джейсон Дана и Клинтин П. Дэвис-Стобер (2011). «Транзитивность предпочтений» (PDF). Психологический обзор. 118 (1): 42–56. Дои:10.1037 / a0021150. PMID  21244185.
7. Брэдли, Ральф Аллан; Терри, Милтон Э. (декабрь 1952 г.). «Ранговый анализ неполных блочных конструкций: I. Метод парных сравнений». Биометрика. 39 (3/4): 324. Дои:10.2307/2334029. JSTOR  2334029.
8. Терстон, Л. Л. (1994). «Закон сравнительного суждения». Психологический обзор. 101 (2): 266–270. Дои:10.1037 / 0033-295X.101.2.266. ISSN  0033-295X.
9. Люс, Р. Дункан (Роберт Дункан) (2005). Индивидуальный выбор поведения: теоретический анализ. Минеола, Нью-Йорк: Dover Publications. ISBN  0486441369. OCLC  874031603.
10. Дебре, Жерар (июль 1958). «Стохастический выбор и кардинальная полезность» (PDF). Econometrica. 26 (3): 440–444. Дои:10.2307/1907622. ISSN  0012-9682. JSTOR  1907622.
11. Регенветтер, Мишель; Дана, Джейсон; Дэвис-Стобер, Клинтин П. (2011). «Транзитивность предпочтений». Психологический обзор. 118 (1): 42–56. Дои:10.1037 / a0021150. ISSN  1939-1471. PMID  21244185.
12. Cavagnaro, Daniel R .; Дэвис-Стобер, Клинтин П. (2014). «Переходный в наших предпочтениях, но переходный по-разному: анализ изменчивости выбора». Решение. 1 (2): 102–122. Дои:10.1037 / dec0000011. ISSN  2325-9973.
13. Shah, Nihar B .; Балакришнан, Шивараман; Гунтубойина, Адитьянанд; Уэйнрайт, Мартин Дж. (Февраль 2017 г.). «Стохастически транзитивные модели для парных сравнений: статистические и вычислительные вопросы». IEEE Transactions по теории информации. 63 (2): 934–959. Дои:10.1109 / tit.2016.2634418. ISSN  0018-9448.
14. Чаттерджи, Сабьясачи; Мукерджи, Сумит (июнь 2019 г.). «Оценка турниров и графиков при ограничениях монотонности». IEEE Transactions по теории информации. 65 (6): 3525–3539. arXiv:1603.04556. Дои:10.1109 / tit.2019.2893911. ISSN  0018-9448. S2CID  54740089.
15. Oliveira, Ivo F.D .; Айлон, Нир; Давыдов, Ори (2018). «Новый и гибкий подход к анализу парных сравнительных данных». Журнал исследований в области машинного обучения. 19: 1–29.
16. Израиль, Роберт Б. (декабрь 1981 г.). «Более сильным игрокам не нужно выигрывать больше турниров на выбывание». Журнал Американской статистической ассоциации. 76 (376): 950–951. Дои:10.2307/2287594. ISSN  0162-1459. JSTOR  2287594.
17. Чен, Роберт; Хван, Ф. К. (декабрь 1988 г.). «Более сильные игроки выигрывают более сбалансированные турниры на выбывание». Графы и комбинаторика. 4 (1): 95–99. Дои:10.1007 / bf01864157. ISSN  0911-0119. S2CID  44602228.
18. Адлер, Илан; Цао, Ян; Карп, Ричард; Peköz, Erol A .; Росс, Шелдон М. (декабрь 2017 г.). «Случайные турниры на выбывание». Исследование операций. 65 (6): 1589–1596. arXiv:1612.04448. Дои:10.1287 / opre.2017.1657. ISSN  0030-364X. S2CID  1041539.
19. Сен, Амартия (январь 1977 г.). «Теория социального выбора: переосмысление». Econometrica. 45 (1): 53–89. Дои:10.2307/1913287. ISSN  0012-9682. JSTOR  1913287.
20. Блаватский, Павел Р. (2007). Теорема стохастической полезности. Inst. для эмпирических исследований в области экономики. OCLC  255736997.
21. Дагсвик, Джон К. (октябрь 2015 г.). «Стохастические модели для рискованного выбора: сравнение различных аксиоматизаций». Журнал математической экономики. 60: 81–88. Дои:10.1016 / j.jmateco.2015.06.013. ISSN  0304-4068.
22. Дебре, Жерар (июль 1958). «Стохастический выбор и кардинальная полезность» (PDF). Econometrica. 26 (3): 440–444. Дои:10.2307/1907622. ISSN  0012-9682. JSTOR  1907622.
23. Йеллотт, Джон И. (апрель 1977 г.). «Связь между аксиомой выбора Люси, теорией сравнительного суждения Терстона и двойным экспоненциальным распределением». Журнал математической психологии. 15 (2): 109–144. Дои:10.1016/0022-2496(77)90026-8. ISSN  0022-2496.
24. Рокуэлл, Кристина; Йеллотт, Джон И. (февраль 1979 г.). «Примечание об эквивалентных моделях Thurstone». Журнал математической психологии. 19 (1): 65–71. Дои:10.1016/0022-2496(79)90006-3. ISSN  0022-2496.
25. деКани, Джон С. (декабрь 1969 г.). «Максимальное правдоподобие парных сравнений по линейному программированию». Биометрика. 56 (3): 537–545. Дои:10.2307/2334661. ISSN  0006-3444. JSTOR  2334661.