Katkat
Back

Maintain Entropy for a Streaming Distribution

OpenAIMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteStatistics & Math

Last updated

Maintain empirical Shannon entropy after every categorical observation without rescanning all categories. The discussion should cover arbitrary identifiers, first-item behavior, exact counts, floating-point drift, concurrency, deletions, sliding windows, and merging summaries from separate stream partitions.

A stream emits categorical observations one at a time. After each observation, report the empirical Shannon entropy of all observations seen so far:

H = -sum(p_i * log(p_i)), where p_i is the observed frequency of category i divided by the total count. Use natural logarithms.

Design an update algorithm that does not rescan every category after each arrival. Explain the state you maintain, derive the update formula, and discuss numerical behavior. Categories may be arbitrary hashable identifiers.

Constraints & Assumptions

  • The stream is initially empty; entropy after the first item is zero.
  • Exact integer category counts fit in the chosen integer type.
  • Small floating-point rounding differences are acceptable.
  • The output is required after every insertion.

Clarifying Questions to Ask

  • Is the logarithm base prescribed? Natural log for this problem.
  • Are deletions or a sliding window required? Not initially.
  • Is an approximate sketch acceptable? No for the base problem.

Follow-up questions

  • Support deletion of an observation.
  • Maintain entropy over a fixed-size sliding window.
  • Merge summaries computed independently on several stream partitions.