Stochastická tranzitivita - Stochastic transitivity

Stochastická tranzitivita modely^[1][2][3][4] jsou stochastický verze tranzitivita vlastnost binárních vztahů studovaných v matematika. Existuje několik modelů stochastické tranzitivity, které byly použity k popisu pravděpodobností experimentů párová srovnání, konkrétně ve scénářích, kde se očekává tranzitivita, jsou však empirická pozorování binární relace pravděpodobnostní. Například lze očekávat, že dovednosti hráče ve sportu budou přechodné, tj. „Pokud je hráč A lepší než B a B je lepší než C, pak hráč A musí být lepší než C“; v každém daném zápase by však slabší hráč mohl nakonec skončit s pozitivní pravděpodobností. Vysoce shodní hráči mohou mít větší šanci pozorovat tuto inverzi, zatímco hráči s velkými rozdíly ve svých dovednostech mohou tyto inverze vidět jen zřídka. Stochastické modely přechodnosti formalizují takové vztahy mezi pravděpodobnostmi (např. Výsledku zápasu) a základním přechodným vztahem (např. Dovednostmi hráčů).

Binární relace ${ textstyle succsim}$ na setu ${ displaystyle { mathcal {A}}}$ je nazýván tranzitivní ve standardu nestochastický smysl, pokud${ displaystyle a succsim b}$ a ${ displaystyle b succsim c}$ naznačuje ${ displaystyle a succsim c}$pro všechny členy ${ displaystyle a, b, c}$ z ${ displaystyle { mathcal {A}}}$.

Stochastický verze zahrnují tranzitivitu zahrnují:

1. Slabá stochastická tranzitivita (WST): ${ displaystyle mathbb {P} (a succsim b) geq { tfrac {1} {2}}}$ a ${ displaystyle mathbb {P} (b succsim c) geq { tfrac {1} {2}}}$ naznačuje ${ displaystyle mathbb {P} (a succsim c) geq { tfrac {1} {2}}}$, pro všechny ${ displaystyle a, b, c v { mathcal {A}}}$;^{[5]:12[6]:43rg}
2. Silná stochastická tranzitivita (SST): ${ displaystyle mathbb {P} (a succsim b) geq { tfrac {1} {2}}}$ a ${ displaystyle mathbb {P} (b succsim c) geq { tfrac {1} {2}}}$ naznačuje ${ displaystyle mathbb {P} (a succsim c) geq max { mathbb {P} (a succsim b), mathbb {P} (b succsim c) }}$, pro všechny ${ displaystyle a, b, c v { mathcal {A}}}$;^[5]:12
3. Lineární stochastická tranzitivita (LST): ${ displaystyle mathbb {P} (a succsim b) = F ( mu (a) - mu (b))}$, pro všechny ${ displaystyle a, b in { mathcal {A}}}$, kde ${ displaystyle F: mathbb {R} na [0,1]}$ je nějaký vzrůstající a symetrický^{[vyjasnit ]} funkce (tzv srovnávací funkce), a ${ displaystyle mu: { mathcal {A}} do mathbb {R}}$ je nějaké mapování ze sady ${ displaystyle { mathcal {A}}}$ alternativ ke skutečné linii (tzv. a funkce zásluh).

Příklad hračky

Mramorová hra - Předpokládejme, že dvě děti, Billy a Gabriela, sbírají kuličky. Billy sbírá modré kuličky a Gabriela zelené kuličky. Když se dají dohromady, hrají hru, kde smíchají všechny své kuličky v tašce a náhodně ochutnají. Pokud je vzorkovaný mramor zelený, pak vyhrává Gabriela a pokud je modrý, pak vyhrává Billy. Li ${ displaystyle B}$ je počet modrých kuliček a ${ displaystyle G}$ je počet zelených kuliček v sáčku, pak pravděpodobnost ${ displaystyle mathbb {P} ({ text {Billy}} succsim { text {Gabriela}})}$ Billyho vítězství proti Gabriele je

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

V tomto příkladu hra s mramorem vyhovuje lineární stochastické tranzitivitě, kde funkce porovnání ${ displaystyle F: mathbb {R} na [0,1]}$ darováno ${ displaystyle F (x) = { frac {1} {1 + e ^ {- x}}}}$ a funkce zásluh ${ displaystyle mu: { mathcal {A}} do mathbb {R}}$ darováno ${ displaystyle mu (M) = ln (M)}$, kde ${ displaystyle M}$ je počet kuliček hráče. Tato hra je příkladem hry a Bradley – Terryho model.^[7]

Aplikace

• Hodnocení a hodnocení - Stochastické tranzitivní modely byly použity jako základ několika metod hodnocení a hodnocení. Mezi příklady patří Systém Elo-Rating používá se v šachu, go a jiných klasických sportech i v Microsoftu TrueSkill používané pro herní platformu Xbox.

• Modely psychologie a racionality - Thurstonian modely^[8] (viz případ 5 v zákon srovnávacího úsudku ), Fechnerovské modely^[3] a také Luciin axiom^[9] jsou teorie, které mají základy v matematice stochastické přechodnosti. Také modely teorie racionální volby jsou založeny na předpokladu tranzitivity předvolby (vidět Von Neumannova užitečnost a Debreuovy věty ), tyto preference jsou však často odhaleny hlukem stochastickým způsobem.^[10][11][12]

• Strojové učení a umělá inteligence (viz Naučte se hodnotit ) - Zatímco se Elo a TrueSkill spoléhají na konkrétní modely LST, modely strojového učení byly vyvinuty tak, aby byly hodnoceny bez předchozích znalostí základního stochastického modelu přechodnosti nebo podle slabších předpokladů o stochastické přechodnosti.^[13][14][15] Učení se z párových srovnání je také zajímavé, protože umožňuje agentům AI naučit se základní preference ostatních agentů.

• Herní teorie - Spravedlivost náhodných vyřazovacích turnajů je silně závislá na základním stochastickém modelu přechodnosti.^[16][17][18] Teorie sociální volby má také základy, které závisí na stochastických tranzitivních modelech.^[19]

Propojení mezi modely

Pozitivní výsledky:

1. Každý model, který vyhovuje lineární stochastické přechodnosti, musí také uspokojit silnou stochastickou přechodnost, která naopak musí vyhovovat slabé stochastické přechodnosti. Toto je reprezentováno jako: LST ${ displaystyle naznačuje}$ SST${ displaystyle naznačuje}$WST ;
2. Vzhledem k tomu, modely Bradeley-Terry a Thurstanian model 5^{[vyjasnit ]} jsou LST modely také uspokojí SST a WST;
3. Kvůli pohodlí strukturovanější modely^{[vyjasnit ]}, několik autorů^{[1][2][3][4][20][21]} identifikovali axiomatické odůvodnění^{[vyjasnit ]} lineární stochastické tranzitivity (a dalších modelů), zejména Gérard Debreu to ukázal^[22] : Čtyřlůžkový stav^{[vyjasnit ]} + Kontinuita^{[vyjasnit ]} ${ displaystyle naznačuje}$ LST (viz také Debreuovy věty );
4. Dva modely LST dané invertibilní srovnávací funkce ${ displaystyle F (x)}$ a ${ displaystyle G (x)}$ jsou ekvivalent^{[vyjasnit ]} kdyby a jen kdyby ${ displaystyle F (x) = G ( kappa x)}$pro některé ${ displaystyle kappa geq 0.}$^[23]

Negativní výsledky:

1. Stochastické tranzitivní modely jsou empiricky neověřitelné^{[vyjasnit ]},^[4] mohou však být padělatelné;
2. Rozlišovací^{[vyjasnit ]} mezi LST srovnávací funkce ${ displaystyle F (x)}$ a ${ displaystyle G (x)}$ může být nemožné, i když je poskytnuto nekonečné množství dat přes konečný počet bodů^{[vyjasnit ]};^[24]
3. The problém s odhadem^{[vyjasnit ]} pro WST, SST a LST modely jsou obecně NP-tvrdý, ^[25] jsou však známy téměř optimální polynomiálně vypočítatelné postupy odhadu SST a LST modely.^[13][14][15]

Viz také

• Nepřenosná hra
• Teorie rozhodování
• Prospěchářství

Reference