Puncte:1

Ce înseamnă sintaxa Pr[D = 1]?

drapel fr

Mă uit la acest PDF pentru a înțelege argumentul hibrid: http://www.cs.columbia.edu/~tal/4261/F14/hybrid.pdf

Primele rânduri sunt după cum urmează:

Să presupunem că aveți două oracole sau distribuții de intrare, $O_0,O_1$și vrei să dovedești că nu se pot distinge, adică pentru fiecare diferență probabilistică în timp polinomial (PPT), D, trebuie să fie valabile următoarele: $$ |Pr[D^{O_1} = 1] - Pr[D^{O_0} = 1]| = neglij. $$

Încerc să înțeleg ce $Pr[D^{O_1} = 1]$ mijloace. Este probabilitatea ca deosebitorul să fie corect?

Puncte:2
drapel sa

$Pr[D^{O_i} = 1]$ este probabilitatea ca elementul de distincție să iasă 1 dat oracolul propriu-zis este $O_i.$

drapel us
Nu cred că este corect să spunem că „ieșirile distinctive 1” înseamnă „distingherul este corect”. Cred că ieșirea distinctivă „corectă” se schimbă atunci când oracolul se schimbă, dar comparăm probabilitatea „ieșirii 1” în prezența a două oracole diferite.
Foobar avatar
drapel fr
@Mikero, deci dacă înțeleg corect dacă distinctorul dă 1, cred că oracolul este O1, iar dacă iese 0, crede că oracolul este O0. Și afirmația este: distincția ar trebui să aibă la fel de probabil să iasă 1, indiferent dacă oracolul real este O1 sau O1
Puncte:1
drapel es

$\newcommand{\pr}{\mathbf{Pr}}$ O altă posibilă interpretare intuitivă ar fi: aceasta înseamnă că comportament de $D$ nu se schimbă perceptiv. Presupune $D$ iese 0 sau 1. Apoi, comportamentul de ieșire al $D$ poate fi rezumat prin distribuția de probabilitate a $D$ieșirea lui, iar aceasta poate fi scrisă ca vector $(\pr[D=0], \pr[D=1])$.

Luați în considerare distanța L1 dintre vectorii de distribuție față de oracole $O_0, O_1$: $$|\pr[D^{O_1}=0]-\pr[D^{O_0}=0]|+|\pr[D^{O_1}=1]-\pr[D^{O_0}= 1]|.$$

De cand $\pr[D^{O_1}=0]=1-\pr[D^{O_1}=1]$ și $\pr[D^{O_0}=0]=1-\pr[D^{O_0}=1]$, conectându-le la distanța L1, obținem $$2|\pr[D^{O_1}=1]-\pr[D^{O_0}=1]|.$$

Deci, condiția dată este ca distribuția probabilității de ieșire să nu se schimbe prea mult atunci când se schimbă $O_0$ și $O_1$.

Acest lucru are sens: a putea distinge două situații înseamnă a putea acționa diferit în funcție de situația dată. Dacă comportamentul cuiva nu se schimbă niciodată (și nu se poate schimba), chiar dacă schimbi unul de celălalt, înseamnă că el/ea nu recunoaște comutatorul.

Ce-ar fi dacă $D$ ieșiri nu doar un pic, ci ceva mai mult? Spune, $D$ ar putea scoate un număr. Chiar și în acest caz, dacă $D$ se comportă diferit când oracolul este comutat, un aspect al rezultatului trebuie să se schimbe. De exemplu, să zicem, MSB-ul de ieșire al $D$ s-ar putea schimba. În acest caz, putem defini un alt deosebitor $D'$ care aleargă $D$, și apoi scoate numai MSB-ul de $D$ieșirea lui. Deci, dacă nu există așa ceva $D'$, atunci nu există așa ceva $D$. Deci, mai mult sau mai puțin, fără pierderea generalității, putem lua în considerare doar distincții cu ieșire binară atunci când definim indistingubilitatea.

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.