Estimating Entropy of Distributions in Constant Space
Authors: Jayadev Acharya, Sourbh Bhadane, Piotr Indyk, Ziteng Sun
NeurIPS 2019 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main contribution is an algorithm that requires O k log(1/")2 samples and a constant O(1) memory words of space and outputs a " estimate of H(p). Our algorithm partitions [0, 1] into intervals and estimates the entropy contribution of probability values in each interval. |
| Researcher Affiliation | Academia | Jayadev Acharya Cornell University EMAIL Sourbh Bhadane Cornell University EMAIL Piotr Indyk Massachusetts Institute of Technology EMAIL Ziteng Sun Cornell University EMAIL |
| Pseudocode | Yes | Algorithm 1 Entropy estimation with constant space: Simple Algorithm; Algorithm 2 A : ESTINT (N, x); Algorithm 3 ESTPROBINT (N, R); Algorithm 4 Estimating H1 and H2 : CONDEXP (N1, N2, R1, R2); Algorithm 5 Entropy Estimation with constant space: Two Intervals Algorithm; Algorithm 6 Entropy Estimation with constant space: General Intervals Algorithm. |
| Open Source Code | No | The paper does not provide any statement or link regarding the availability of open-source code for the described methodology. |
| Open Datasets | No | This is a theoretical paper focused on algorithm design and complexity analysis. It does not use or refer to any specific datasets for training. |
| Dataset Splits | No | This is a theoretical paper focused on algorithm design and complexity analysis. It does not use or refer to any specific datasets or their splits for validation. |
| Hardware Specification | No | This is a theoretical paper presenting algorithms and their complexity analysis. It does not describe any experimental setup or hardware used for running experiments. |
| Software Dependencies | No | This is a theoretical paper presenting algorithms and their complexity analysis. It does not mention any specific software or libraries with version numbers. |
| Experiment Setup | No | This is a theoretical paper focused on algorithm design and complexity analysis. It does not describe any experimental setup, hyperparameters, or training configurations. |