Kegunaan entropi Renyi?

14

Sebagian besar dari kita akrab dengan - atau setidaknya pernah mendengar tentang - entropi Shannon dari variabel acak, $H(X) = -\mathbb{E} \bigl[ \log p(X)\bigr]$ , dan semua informasi terkait - ukuran teoretis seperti entropi relatif, informasi timbal balik, dan sebagainya. Ada beberapa ukuran entropi lain yang biasa digunakan dalam ilmu komputer teoretis dan teori informasi, seperti min-entropi variabel acak.

Saya sudah mulai lebih sering melihat apa yang disebut entri Renyi ketika saya membaca literatur. Mereka menggeneralisasi entropi Shannon dan min-entropi, dan pada kenyataannya menyediakan seluruh spektrum ukuran entropik dari variabel acak. Saya bekerja sebagian besar di bidang informasi kuantum, di mana versi kuantum dari renyi entropi juga dianggap cukup sering.

Apa yang saya tidak benar-benar mengerti adalah mengapa mereka berguna. Saya pernah mendengar bahwa seringkali mereka lebih mudah untuk dikerjakan secara analitis daripada kata Shannon / von Neumann entropi atau min-entropi. Tetapi mereka juga dapat dihubungkan kembali ke Shannon entropy / min-entropy, juga.

Adakah yang bisa memberikan contoh (klasik atau kuantum) ketika menggunakan entropi Renyi adalah "hal yang benar untuk dilakukan"? Yang saya cari adalah "kait mental" atau "templat" untuk mengetahui kapan saya ingin menggunakan entropi Renyi.

Terima kasih!

it.information-theory quantum-information Henry Yuen
sumber

Tambahan untuk jawaban saya: Tampaknya ada definisi probabilistik entropi q-Renyi ( ) i, e . Kemudian dan RHS ini disebut `` Shannon Entropy ". Satu juga mendefinisikan batas lainnya yaitu . Gagasan ini tampaknya telah menemukan kegunaan dalam konstruksi expander seperti yang terlihat di sini, math.rutgers.edu/~sk1233/courses/topics-S13, math.ias. edu / ~ avi / PUBLIKASI / MYPAPER / CRVW01 / crvw01.pdf, arxiv.org/pdf/math/0406038.pdf

q \in Z^{+}

$q \in \mathbb{Z}^+$

H_{q} ({p_{i}}_{i = 1}^{n}) = \frac{1}{1 - q} l n [\sum_{k = 1}^{n} p_{k}^{q}]

$H_q (\{ p_i \}_{i=1}^n )= \frac{1}{1-q} ln [ \sum_{k=1}^n p_k^q ]$

l i m_{q \to 1} H_{q} = - \sum p_{k} l n (p_{k})

$lim_{q \rightarrow 1} H_q = - \sum p_k ln (p_k)$

H_{\infty} (X) = l n [\frac{1}{m a x_{a} P r [X = a]}]

$H_{\infty} (X) = ln [\frac{1}{ max_{a} Pr[X=a]} ]$

Anirbit

15

Mempertimbangkan untuk mencoba untuk membuat tebakan atom untuk diketahui variabel acak didistribusikan melalui beberapa himpunan berhingga Dalam entropi Shannon, diasumsikan bahwa Anda dapat meminta sedikit demi sedikit, yaitu, jika Anda dapat bertanya: $X$ $A.$ $A=\{1,\ldots,N\}$

Apakah ? $X\in \{1,\ldots,N/2\}$ (asumsikan even atau gunakan fungsi lantai / langit-langit) $N$

Dalam skenario crypto dan beberapa decoding ini tidak realistis. Mencoba menebak kata sandi yang tidak dikenal, Anda perlu membuat kueri atom, yaitu kueri jika adalah nilai tertentu. $X$

Ternyata jumlah pertanyaan yang diharapkan untuk menebak variabel acak kemudian sangat bergantung pada entropi Renyi pesananJadi, lakukan beberapa momen yang lebih tinggi. Sebagai contoh $X$ $1/2.$

E [G] \leq \frac{(\sum_{x \in A} P_{X} (x)^{1 / 2})^{2}}{2}

$E[G]\leq \frac{(\sum_{x \in A} P_X(x)^{1/2})^2}{2}$

dan pembilang pada dasarnya adalah logaritma dari Renyi entropi pesananSeseorang juga dapat membuat entropi Shannon menjadi sangat besar sementara entropi Renyi dan ekspektasi jumlah tebakan sangat kecil. Jika Anda mengandalkan entropi Shannon untuk keamanan, Anda akan berada dalam masalah dalam kasus itu. $1/2.$

Silakan juga lihat pertanyaan terkait Menebak nilai entropi rendah dalam beberapa upaya

Beberapa referensi:

JO Pliam, Tentang Ketidakterbandingan Entropi dan Tebak Marjinal dalam Serangan Brute-Force. INDOCRYPT 2000: 67-79
E. Arikan, Ketidaksetaraan dalam menebak dan penerapannya untuk penguraian kode sekuensial. Transaksi IEEE tentang Teori Informasi 42 (1): 99-105.1996.
S. Boztas, On Renyi entropi dan aplikasinya untuk menebak serangan dalam kriptografi, Transaksi IEICE tentang Dasar-Dasar Elektronik, Komunikasi dan Ilmu Komputer 97 (12): 2542-2548, 2014.

Kodlu
sumber

Saya tidak dapat mengakses makalah S.Boztas ini. Anda memiliki tautan yang dapat diakses publik?

Anirbit

@Anirbit lihat repositori riset RMIT, researchbank.rmit.edu.au

kodlu

Saya telah mencari melalui tautan itu. Saya hanya perlu berputar-putar. Saya tidak pernah menemukan file pdf yang dapat diakses publik!

Anirbit

@Anirbit, maaf, saya pikir itu benar-benar disimpan di sana!

Kodlu

18

Entropi Renyi adalah analog, dalam arti tertentu, dengan -norm, jadi mari kita ingat mengapa norma-norma itu berguna. $\ell_p$

Misalkan kita memiliki vektor angka . Kami ingin memiliki satu nomor yang mewakili, dalam arti, bagaimana elemen khas terlihat seperti. $a \in \mathbb{R}^n$ $a$

Salah satu cara untuk melakukannya adalah dengan mengambil rata-rata angka dalam , yang kira-kira sesuai dengan norma : . Ini sering berguna, tetapi untuk beberapa aplikasi memiliki masalah berikut: Pertama, norma tidak memberi kita batas atas yang baik pada elemen terbesar dari , karena jika ada elemen besar tunggal dan banyak nol, maka norma akan secara signifikan lebih kecil dari elemen terbesar. Di sisi lain, $a$ $\ell_1$ $\mathbb{E}_{1 \le i \le n}[|a_i|]$ $\ell_1$ $a$ $\ell_1$ $\ell_1$ norma juga tidak memberi kita batasan yang baik tentang seberapa kecil elemen-elemen , misalnya, berapa banyak nol dimiliki - masalah ini terjadi dalam skenario yang persis sama seperti sebelumnya. $a$ $a$

Tentu saja, ketika unsur-unsur dari memiliki banyak varian, seperti dalam skenario ekstrim seperti di atas, ada nomor tunggal dapat memberikan memecahkan kedua masalah di atas. Kami memiliki tradeoff. Misalnya, jika kita hanya ingin tahu elemen terbesar, kita dapat menggunakan norma , tetapi kemudian kita akan kehilangan semua informasi tentang elemen yang lebih kecil. Jika kita menginginkan jumlah nol, kita dapat melihat norma , yang hanya merupakan ukuran dari dukungan . $a$ $\ell_\infty$ $\ell_0$ $a$

Sekarang, alasan untuk mempertimbangkan norma adalah bahwa mereka memberi kita tradeoff seluruh terus menerus antara dua ekstrem. Jika kita ingin lebih banyak informasi tentang elemen besar kita mengambil menjadi lebih besar, dan sebaliknya. $\ell_p$ $p$

Hal yang sama berlaku untuk entropi Renyi: Entropi Shanon seperti norma - ia memberi tahu kita sesuatu tentang probabilitas "tipikal" suatu elemen, tetapi tidak ada tentang varians atau ekstrem. Min-entropi memberi kita informasi tentang elemen dengan probabilitas terbesar, tetapi kehilangan semua informasi tentang sisanya. Ukuran dukungan memberikan yang lain ekstrim. Entropi Renyi memberi kita tradeoff terus menerus antara dua ekstrem. $\ell_1$

Sebagai contoh, berkali-kali entropi Renyi-2 berguna karena di satu sisi dekat dengan entropi Shanon, dan dengan demikian berisi informasi tentang semua elemen pada distribusi, dan di sisi lain memberikan informasi lebih lanjut tentang elemen dengan yang terbesar kemungkinan. Secara khusus, diketahui bahwa batasan pada entropi Renyi-2 memberikan batasan pada entropi min, lihat, misalnya, Lampiran A di sini: http://people.seas.harvard.edu/~salil/research/conductors-prelim .ps

Atau Meir
sumber

11

Entropi Renyi (urutan 2) berguna dalam kriptografi untuk menganalisis kemungkinan tabrakan.

Ingat bahwa entropi Renyi orde 2 dari variabel acak diberikan oleh $X$

H_{2} (X) = - \log_{2} \sum_{x} Pr [X = x]^{2} .

$H_2(X) = - \log_2 \sum_x \Pr[X=x]^2.$

Ternyata memungkinkan kita mengukur probabilitas bahwa dua nilai yang ditarik iid menurut distribusi adalah sama ("bertabrakan"): probabilitas ini tepat . Setelah menggambar kali dari distribusi ini, jumlah tumbukan yang diharapkan di antara draw ini adalah . $H_2(X)$ $X$ $2^{-H_2(X)}$ $n$ $n$ $C(n,2) 2^{-H_2(X)}$

Fakta-fakta ini berguna dalam kriptografi, di mana tabrakan kadang-kadang bisa menjadi masalah dan memungkinkan serangan.

Untuk beberapa analisis penggunaan lain dalam kriptografi, saya merekomendasikan disertasi PhD berikut:

Christian Cachin. Tindakan Entropi dan Keamanan Tanpa Syarat dalam Kriptografi . Disertasi PhD, ETH Zurich, Mei 1997.

DW
sumber

Apakah ada definisi probabilitas langsung dari setiap entropi q-Renyi? (seperti yang dapat Anda lihat dari jawaban saya, satu-satunya cara saya mengetahui mendefinisikan ini pada q sewenang-wenang adalah melalui mendefinisikan fungsi partisi yang sesuai dengan sistem fisik yang telah ditentukan melalui Lagrangian atau Hamiltonian atau aksinya)

Anirbit

@Anirbit, saya tidak tahu. Tidak ada yang saya ingat melihat (meskipun itu mungkin entropi q-Renyi dapat menyebabkan batas pada batas lain yang kita pedulikan ...)

DW

Juga tampaknya "entropi informasi" tampaknya pada dasarnya adalah "entropi termodinamika". Jadi, bahkan pada (q = 1) -Renyi entropi yaitu entropi entanglement ada kesenjangan konseptual tentang kompleksitas interpretasi itu?

Anirbit

@ DW: Jawaban yang bagus, saya lalai untuk memasukkan kasus ini: memang tampaknya bahwa renyi entropi dari berbagai pesanan terhubung dengan skenario kriptografi yang berbeda, termasuk misalnya min-entropi (yang sesuai dengan parameter Renyi yang mendekati

) yang memainkan bagian dalam ekstraksi keacakan.

- \infty

$-\infty$

kodlu

@ DW Tampaknya ada interpretasi probabilistik. Lihat komentar saya pada pertanyaan awal.

Anirbit

3

Jawaban stackexchange lain ini dan posting blog ini mungkin sangat membantu untuk merasakan contoh dasar,

Secara kasar entropi Renyi tahu tentang keadaan tereksitasi dari sistem kuantum tetapi entropi keterjeratan tahu tentang keadaan dasar. PERINGATAN: Intuisi ini bisa sangat kasar tetapi mungkin hanya "kait mental" yang bagus: DI SANGAT senang mengetahui cara yang lebih baik dan tepat untuk mengatakan ini!

Seseorang dapat berpikir untuk menghitung entropi entropi (yang merupakan jumlah yang lebih fisik) sebagai batas tunggal untuk menghitung entropi Renyi ( untuk setiap ). Tapi batas ini sangat buruk didefinisikan. Jadi sering idenya adalah bahwa seseorang dapat menghitung pada nilai integer sewenang-wenang dan kemudian melakukan analisis lanjutan itu untuk dan kemudian mencoba untuk mendefinisikan mengambil dari $S_1$ $S_q$ $q \in \mathbb{Z}^+$ $S_1 = limit_{q \rightarrow 1} S_q$ $S_q$ $q \in \mathbb{R}$ batas. (meskipun selalu , ini saya sebut kelanjutan "analitik" karena seringkali cukup seseorang perlu melakukan interpolasi melalui kontur pada bidang kompleks - dan kelanjutan dapat bergantung pada kontur apa yang dipilih seseorang melalui kutub dan pemotongan cabang yang dimulai dengan) $q \rightarrow 1$ $q \in \mathbb{R}$ $S_q$

Pada nilai integral biasanya selalu ada konstruksi yang didefinisikan dengan sangat baik dalam hal integrasi beberapa fungsi pada beberapa manifold bercabang. Setelah seseorang melakukan integrasi seperti itu, ia dengan senang hati lupa tentang manifold yang digunakan dan hanya mencoba melakukan kelanjutan analitik secara parametrik dalam variabel . $q>1$ $q-$ $q$

Selalu ada banyak masalah tentang keberadaan dan kedudukan baik ketika seseorang mencoba melakukan kelanjutan anayltic ini - tetapi bagi seseorang seperti saya yang dibesarkan dengan diet harian Feynman path-integral, ini adalah masalah yang sangat umum untuk dihadapi dan kami punya banyak alat untuk mengatasinya. Tiga makalah yang bagus untuk membahas masalah ini adalah, http://arxiv.org/pdf/1306.5242.pdf , http://arxiv.org/pdf/1402.5396.pdf , http://arxiv.org/pdf/1303.7221 .pdf (makalah terakhir ini mungkin merupakan titik awal yang lebih mudah) Presentasi ini juga dapat membantu, https://www.icts.res.in/media/uploads/Talk/Document/Tadashi_Takayanagi.pdf

Apa yang dikatakan Renyi entropi dalam kaitannya dengan teori kompleksitas kuantum mungkin merupakan pertanyaan yang menarik! Bisakah seseorang menganggap indeks Renyi sebagai parameter parameter hierarki kelas kompleksitas? Itu harus menyenangkan jika benar! Biarkan saya tahu :)

Anirbit
sumber

0

Entropi Renyi telah menemukan jalannya ke definisi aliran informasi kuantitatif , suatu bidang atau penelitian keamanan. Lihat makalah survei G. Smith .

Kai
sumber

Kegunaan entropi Renyi?

Jawaban: