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

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

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

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

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

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

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

$\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)}}}$.

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

Приложения

• Ранжирование и рейтинг . Модели стохастической транзитивности использовались в качестве основы для нескольких методов ранжирования и рейтинга. Примеры включают систему Elo-Rating, используемую в шахматах, го и других классических видах спорта, а также систему TrueSkill от Microsoft , используемую для игровой платформы Xbox.
• Модели психологии и рациональности - модели Терстона (см. случай 5 в праве сравнительного суждения ), модели Фехнера а также аксиома выбора Люси — это теории, основанные на математике стохастической транзитивности. Также модели теории рационального выбора основаны на предположении о транзитивности предпочтений (см. Полезность фон Неймана и Теоремы Дебре ), однако эти предпочтения часто выявляются с помощью шума стохастическим образом.
• Машинное обучение и искусственный интеллект (см. « Научитесь ранжировать ») . Хотя Elo и TrueSkill полагаются на конкретные модели LST, модели машинного обучения были разработаны для ранжирования без предварительного знания базовой модели стохастической транзитивности или при более слабых, чем обычно, предположениях о стохастической транзитивности. Обучение на основе парных сравнений также представляет интерес, поскольку позволяет агентам ИИ изучать основные предпочтения других агентов.
• Теория игр . Справедливость турниров со случайным выбыванием сильно зависит от базовой модели стохастической транзитивности. Теория социального выбора также имеет основы, основанные на моделях стохастической транзитивности.

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

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

1. Каждая модель, удовлетворяющая линейной стохастической транзитивности, должна также удовлетворять сильной стохастической транзитивности, которая, в свою очередь, должна удовлетворять слабой стохастической транзитивности. Это представлено как: LST $\implies$ ССТ $\implies$ВСТ ;
2. Поскольку модели Брэдли-Терри и модель Case V Терстоуна являются LST моделями , они также удовлетворяют требованиям SST и WST ;
3. За счет удобства более структурированных моделей , несколько авторов определили аксиоматические обоснования линейной стохастической транзитивности (и других моделей), в первую очередь Жерар Дебре показал, что: Четверное состояние + Непрерывность $\implies$ LST (см. также Теоремы Дебре );
4. Две модели LST, заданные обратимыми функциями сравнения $F(x)$ и $G(x)$ эквивалентны ​ тогда и только тогда, когда $F(x)=G(\kappa x)$для некоторых $\kappa \geq 0.$

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

1. Модели стохастической транзитивности эмпирически не поддаются проверке. , однако они могут быть фальсифицируемы;
2. Отличительный между LST функциями сравнения $F(x)$ и $G(x)$ может быть невозможным, даже если бесконечное количество данных предоставляется по конечному числу точек ;
3. Проблема оценки для моделей WST , SST и LST обычно применяется NP-Hard , известны почти оптимальные полиномиально вычислимые процедуры оценки однако для моделей SST и LST .

См. также

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