Điểm:1

Cú pháp Pr[D = 1] nghĩa là gì?

lá cờ fr

Tôi đang xem bản PDF này để hiểu đối số kết hợp: http://www.cs.columbia.edu/~tal/4261/F14/hybrid.pdf

Vài dòng đầu tiên như sau:

Giả sử bạn có hai lời tiên tri, hoặc phân phối đầu vào, $O_0,O_1$và bạn muốn chứng minh rằng chúng không thể phân biệt được, I E. cho mọi bộ phân biệt xác suất, thời gian đa thức (PPT), Đ., những điều sau đây phải giữ: $$ |Pr[D^{O_1} = 1] - Pr[D^{O_0} = 1]| = bỏ bê. $$

Tôi đang cố gắng để hiểu những gì $Pr[D^{O_1} = 1]$ có nghĩa. Đó có phải là xác suất phân biệt là chính xác?

Điểm:2
lá cờ sa

$Pr[D^{O_i} = 1]$ là xác suất mà bộ phân biệt xuất ra 1 được cho nhà tiên tri thực tế là $O_i.$

lá cờ us
Tôi không nghĩ là đúng khi nói rằng "đầu ra của bộ phân biệt 1" có nghĩa là "bộ phân biệt là đúng". Tôi nghĩ rằng đầu ra của bộ phân biệt "chính xác" thay đổi khi tiên tri thay đổi, nhưng chúng tôi đang so sánh xác suất của "đầu ra 1" với sự có mặt của hai tiên tri khác nhau.
Foobar avatar
lá cờ fr
@Mikero, vì vậy nếu tôi hiểu chính xác nếu bộ phân biệt xuất ra 1 thì nó nghĩ tiên tri là O1 và nếu nó xuất ra 0 thì nó nghĩ tiên tri là O0. Và yêu cầu là: bộ phân biệt phải có khả năng xuất ra 1 như nhau bất kể lời tiên tri thực tế là O1 hay O1
Điểm:1
lá cờ es

$\newcommand{\pr}{\mathbf{Pr}}$ Một cách giải thích trực quan khác có thể là: điều này có nghĩa là cư xử của $D$ không thay đổi về mặt nhận thức. Giả sử $D$ đầu ra 0 hoặc 1. Sau đó, hành vi đầu ra của $D$ có thể được tóm tắt bằng phân phối xác suất của $D$đầu ra của nó, và cái này có thể được viết dưới dạng véc-tơ $(\pr[D=0], \pr[D=1])$.

Xem xét khoảng cách L1 giữa các vectơ phân phối đối với các nhà tiên tri $O_0, O_1$: $$|\pr[D^{O_1}=0]-\pr[D^{O_0}=0]|+|\pr[D^{O_1}=1]-\pr[D^{O_0}= 1]|.$$

Từ $\pr[D^{O_1}=0]=1-\pr[D^{O_1}=1]$$\pr[D^{O_0}=0]=1-\pr[D^{O_0}=1]$, cắm chúng vào khoảng cách L1, chúng tôi nhận được $$2|\pr[D^{O_1}=1]-\pr[D^{O_0}=1]|.$$

Vì vậy, điều kiện đã cho là phân phối xác suất đầu ra không thay đổi nhiều, khi một người hoán đổi $O_0$$O_1$.

Điều này có ý nghĩa: có thể phân biệt hai tình huống có nghĩa là có thể hành động khác nhau tùy theo tình huống nhất định. Nếu hành vi của ai đó không bao giờ thay đổi (và không thể thay đổi) ngay cả khi bạn chuyển cái này sang cái kia, điều đó có nghĩa là người đó không nhận ra sự chuyển đổi.

Chuyện gì xảy ra nếu $D$ đầu ra không chỉ một chút mà còn nhiều hơn nữa? Nói, $D$ có thể xuất ra một số. Ngay cả trong trường hợp đó, nếu $D$ hành xử khác đi khi oracle được chuyển đổi, một số khía cạnh của đầu ra phải thay đổi. Ví dụ: giả sử, MSB của đầu ra của $D$ có thể thay đổi. Trong trường hợp đó, chúng ta có thể định nghĩa một dấu hiệu phân biệt khác $D'$ mà chạy $D$, và sau đó chỉ xuất ra MSB của $D$đầu ra của. Vì vậy, nếu không có như vậy $D'$, sau đó không có như vậy $D$. Vì vậy, ít nhiều không làm mất tính tổng quát, chúng ta có thể chỉ xem xét các bộ phân biệt với đầu ra nhị phân khi xác định tính không thể phân biệt.

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.