FastPrep
Problem · Array

Streaming Entropy, Part 1: Batch Entropy

Learn this problem
● EasyOpenAIFULLTIMEONSITE INTERVIEW

Problem statement

Streaming Entropy interview sequence

This is Part 1 of one four-part ML coding exercise.

  1. Part 1: Batch Entropy
  2. Part 2: Numerically Stable Entropy
  3. Part 3: Block-wise Entropy
  4. Part 4: Stable Streaming Entropy

A model produces a one-dimensional array of logits x[0], x[1], ..., x[n - 1]. The logits define a probability distribution through softmax:

p[i] = exp(x[i]) / sum(exp(x[j]))

The entropy of that distribution is:

H = -sum(p[i] * ln(p[i]))

Here, ln is the natural logarithm. Given all logits at once, return the non-negative entropy of their softmax distribution. An answer is accepted when its absolute or relative error is at most 1e-6.

This opening part uses moderate logits, so numerical overflow and underflow are not the focus yet. Your implementation should run in O(n) time.

After solving this part, continue to Part 2: Numerically Stable Entropy.

Function

entropy(logits: double[]) → double

Examples

Example 1

logits = [0.0, 0.0]return = 0.6931471805599453

The two logits are equal, so softmax produces [0.5, 0.5]. The entropy is -2 * 0.5 * ln(0.5) = ln(2).

Example 2

logits = [0.0, 1.0986122886681098]return = 0.5623351446188083

The second logit is ln(3), so the probabilities are [0.25, 0.75].

Example 3

logits = [2.0, 1.0, 0.0]return = 0.8323955818399389

Softmax is unchanged if the same constant is added to every logit. This distribution is equivalent to the logits [0, -1, -2].

Constraints

  • 1 <= logits.length <= 2 * 10^5
  • Every logit is finite and lies in [-20, 20].
  • Use the natural logarithm.
  • Use O(n) time.

More OpenAI problems

drafts saved locally
public double entropy(double[] logits) {
  // write your code here
}
logits[0.0, 0.0]
expected0.6931471805599453
checking account