Kto ukuł termin „empiryczna entropia”?

Wiem o pracy Shannona z entropią, ale ostatnio pracowałem nad zwięzłymi strukturami danych, w których entropia empiryczna jest często używana jako część analizy pamięci.

Shannon zdefiniował entropię informacji wytwarzanej przez dyskretne źródło informacji jako , gdzie jest prawdopodobieństwem wystąpienia zdarzenia , np. Wygenerowany określony znak, i istnieją możliwe zdarzenia. $-\sum_{i=1}^k p_i \log{p_i}$ $p_i$ $i$ $k$

Jak wskazał MCH w komentarzach, entropia empiryczna jest entropią rozkładu empirycznego tych zdarzeń i dlatego jest podana przez gdzie to liczba zaobserwowanych wystąpień zdarzenia a to całkowita liczba zaobserwowanych zdarzeń. Nazywa się to entropią empiryczną rzędu zerowego . Pojęcie entropii warunkowej Shannona ma podobną wersję empiryczną wyższego rzędu . $-\sum_{i=1}^k \frac{n_{i}}{n} \log{\frac{n_{i}}{n}}$ $n_{i}$ $i$ $n$

Shannon nie użył terminu entropia empiryczna, choć z pewnością zasługuje na uznanie za tę koncepcję. Kto pierwszy użył tego pomysłu, a kto pierwszy użył (bardzo logicznej) nazwy empirycznej entropii, aby go opisać?

reference-request shannon-entropy succinct usunięty użytkownik 42
źródło

„punktowo zdefiniowany dla każdego ciągu” brzmi jak złożoność Kołmogorowa: czy o to ci chodzi? Jeśli nie, czy możesz wskazać link, który go definiuje, czy lepiej podać defn w samym pytaniu?

Suresh Venkat

Nazywa się to tak, ponieważ empiryczna entropia jest entropią empirycznego rozkładu sekwencji.

Mahdi Cheraghchi,

@SureshVenkat Próbowałem rozwinąć pytanie.

usunięty użytkownik 42

Spójrz także na Kosaraju S. Rao, Manziniego G., „Kompresja ciągów niskiej entropii za pomocą algorytmów Lempel-Ziv” (1998). Analizują wydajność algorytmów Lempel-Ziv przy użyciu „ tak zwanej entropii empirycznej ”.

Marzio De Biasi

Zauważ, że „rozkład empiryczny” jest tak naprawdę rozkładem ML dla danego zestawu zliczeń częstotliwości. Zastanawiam się więc, czy pochodzi to z Bayes. Nawet Laplace zastanawiał się nad problemem zdefiniowania rozkładu na podstawie obliczeń empirycznych.

Suresh Venkat

Interesuje mnie „empiryczna entropia”, podobnie jak ty, a najwcześniejszy artykuł, jaki znalazłem, to ten z Kosaraju, jak użytkownik „Marzio De Biasi” powiedział w swoim komentarzu.

Ale moim zdaniem prawdziwe definicje „empirycznej entropii” zostały sformułowane później poprzez uogólnienie wcześniejszych pojęć:

„Duże alfabety i nieściśliwość” Travisa Gagiego (2008)
„Emprical entropy” Paula MB Vitányi (2011)

Gagie przeformułowuje definicję $k$ empiryczna entropia rzędu do:

$H_{k}(w)=\frac{1}{|w|}\min\limits_{Q}\left\{\log\large\frac{1}{P(Q=w)}\right\}$

gdzie jest procesem Markowa rzędu . Pokazał również, że ta definicja jest równoważna poprzedniej. Kolejnym krokiem od Vitányi było uogólnienie na arbitralne klasy procesów (nie tylko procesy Markowa): $Q$ $k$

$H(w|\mathcal{X})=\min\limits_{X}\left\{K(X)+H(X):\;\left|H(X)-\log\large\frac{1}{P(X=w)}\right|\normalsize\;is\;minimal!\right\}$

gdzie to klasa dozwolonych procesów, a to złożoność Kołmogorowa. Jeśli wybierzemy jako klasę procesów Markowa tego rzędu, wytwarzających sekwencjęlosowe zmienne i ignorowanie złożoności Kołmogorowa, prowadzi to również do definicji Gagiego (pomnożonej przez ). $\mathcal{X}$ $K(X)$
$\mathcal{X}$ $k$ $|w|$ $|w|$

Danny
źródło

Kto ukuł termin „empiryczna entropia”?

Odpowiedzi: