อะไรคือความแตกต่างที่สำคัญระหว่างเอนโทรปีของแชนนอนและเอนโทรปีของเดา

ทุกคนสามารถอธิบายได้ว่าอะไรคือความแตกต่างที่สำคัญระหว่างเอนโทรปีของแชนนอนและเอนโทรปีของเดา ในการวิจัยบางอย่าง ฉันได้รับเอนโทรปีโดยใช้การค้นหาแบบไบนารีหรือต้นไม้ Huffman ที่สมดุล Guesswork ใช้ต้นไม้ Huffman เชิงเส้นและไม่สมดุล?

การคาดเดายังสามารถคำนวณการคาดเดาได้ไม่จำกัด?

แก้ไข: จากความคิดเห็นของ OP วิธีคิดข้อแตกต่างระหว่าง Guesswork และ Shannon Entropy มีดังต่อไปนี้:

แชนนอน: สมมติว่าเรามีตัวแปรสุ่มที่จะเข้ารหัส เมื่อมีการแจกจ่าย รหัส Huffman หรือขั้นตอนการเข้ารหัสแหล่งที่มาอื่นๆ สามารถใช้ได้ และ ความยาวที่คาดไว้ ของคำรหัสในรหัสนั้นผูกพันอย่างแน่นหนากับเอนโทรปีของแชนนอนของตัวแปรสุ่ม แผนผังรหัส Huffman อธิบายกระบวนการเรียกซ้ำโดยที่ แข็งแกร่งโดยพลการ แบบสอบถามสามารถทำจากตัวแปรสุ่ม ตัวอย่างเช่น คุณสามารถถามสำหรับ $X\in {1,\ldots,N\}$ คำถาม

เป็น $X \leq N/3$?

และเลือกกิ่งด้านซ้ายของต้นไม้จากราก ถ้าคำตอบคือใช่ ในกรณีของ Huffman เราต้องการลดขนาดต้นไม้ให้เล็กที่สุด และแม้ว่าเราจะใช้ขั้นตอนจากล่างขึ้นบนที่ดีในการ "ผสาน" ใบไม้ ในท้ายที่สุด หากคำถามคือคำถามข้างต้น $Pr[X\leq N/3]\ประมาณ 1/2.$ เราแยกซ้าย/ขวา ณ จุดที่ทำให้ความน่าจะเป็นของต้นไม้ย่อยทั้งสองสมดุลกัน

การคาดเดา: ในบริบทนี้ แบบสอบถาม ไม่สามารถมีอำนาจตามอำเภอใจได้ โดยทั่วไปจะเป็นปรมาณู ฉันหมายความว่าในขณะที่สร้างต้นไม้ เราได้รับอนุญาตให้ถามคำถามเกี่ยวกับแบบฟอร์ม

เป็น $X=1$?

ตัวอย่างเช่น. ทะลึ่ง $Pr[X=1]$ คือความน่าจะเป็นของอะตอมที่ใหญ่ที่สุดของรูปแบบ $Pr[X=x]$ ที่ไหน $x\in \{1,2,\ldots,N\}$ นี่เป็นคำถามที่ดีที่สุดที่จะถามเพื่อลดจำนวนการเดาให้น้อยที่สุด ในกรณีนี้ คุณจะยังคงมีแผนผังอยู่แต่โครงสร้างต้นทุนเปลี่ยนไป คุณไม่สามารถตัดต้นไม้ย่อยออกได้หากคำตอบคือ ไม่ คุณสามารถตัดค่าออกได้เท่านั้น $X=1.$ นี่คือสิ่งที่นำไปสู่การคาดเดาเอนโทรปีหรือ $H_{1/2}(X).$

แอปพลิเคชันที่ใช้รวมถึงการโจมตีแบบคาดเดากำลังดุร้าย คุณไม่สามารถถามได้ ตัวอักษรตัวแรกของรหัสผ่านคือ A หรือไม่ คุณต้องป้อนรหัสผ่านแบบเต็มและเข้าหรือถูกปฏิเสธ นี่คือสาเหตุที่คุณไม่สามารถใช้คำถามปรมาณูและถามเกี่ยวกับส่วนของสตริงที่ไม่รู้จักได้

พื้นหลัง:

มีการอภิปรายที่นี่เกี่ยวกับการคาดเดาเอนโทรปี (ซึ่งจริงๆแล้วคือเอนโทรปีของ Renyi ของลำดับที่ 1/2) ในคำถามด้านล่าง:

ความแตกต่างระหว่างเอนโทรปีของแชนนอนและเดา

ความปลอดภัยของการตรวจสอบรหัสผ่านที่กำหนดเอนโทรปี

โดยสรุป หากคุณกังวลเกี่ยวกับจำนวนการเดาโดยเฉลี่ยเพื่อระบุตัวแปรสุ่มที่ไม่รู้จัก คุณควรใช้การเดาเอนโทรปี ไม่ใช่เอนโทรปีของแชนนอน เนื่องจากอันแรกนั้นผูกพันอย่างแน่นหนากับจำนวนการเดาที่คาดไว้

เอนโทรปีของคำสั่ง Renyi $\alpha$ ถูกกำหนดโดย $$ H_{\alpha}(X)=\frac{1}{1-\alpha} \log \left(\sum_{x} Pr(X=x)^{\alpha} \right) $$ ที่ไหน $\alpha \in [0,1) \cup (1,\infty).$ มันเชื่อฟัง $$ \lim_{\alpha\ลูกศรขวา 1} H_{\alpha}(X)=H(X). $$ แสดงโดย John Pliam (ดู ที่นี่ ) ว่าถ้า $X$ เป็นตัวแปรสุ่มที่ไม่ต่อเนื่องกับ $M$ คะแนนในการสนับสนุน $H(X)$ สามารถเข้าใกล้ค่าสูงสุดได้ $\log M$ ในขณะที่ความน่าจะเป็นของนักเดาที่ดีที่สุดที่จะค้นพบค่าที่แท้จริงของ $X$ ใน $k$ คำถามต่อเนื่องน้อยกว่ามาก $2^{H(X)}=M.$

ยิ่งไปกว่านั้น ไม่เพียงแต่จำนวนการคาดเดาที่คาดไว้เท่านั้น แต่ยังรวมถึงช่วงเวลาโดยพลการด้วย จำนวนการเดาอาจเกี่ยวข้องกับเอนโทรปีของ Renyi ของลำดับต่างๆ

ผลลัพธ์หนึ่งตามความคาดหวังคือจำนวนการเดาที่คาดหวัง กำหนด ตัวแปรสุ่ม $X$ (สำหรับลำดับการเดาที่ดีที่สุด) คือ ขอบบนโดย

$$2^{H_{1/2}(X)-1}$$

ที่ไหน $H_{1/2}(X)$ หมายถึงค่าเอนโทรปีของระเบียบ Renyi $\alpha=1/2$ และเรียกอีกอย่างว่าเอนโทรปีแบบคาดเดา ยิ่งกว่านั้น มันจำกัดด้วย (สำหรับลำดับการคาดเดาทั้งหมด)

$$\frac{2^{H_{1/2}(X)}}{1 + \log M } \ประมาณ 2^{H_{1/2}(X)} / H_{max}(X)$ $

ที่ไหน $H_{สูงสุด}(X)$ คือเอนโทรปีสูงสุด $\log M$ ใน Renyi อย่างใดอย่างหนึ่ง หรือกรณีแชนนอน