CalculusΓ—Computing
ES

Expectation

Level UniversityDifficulty β˜…β˜…β˜…β˜…β˜…ConceptβŒ– Open in the map

What is it?

𝔼[X]=∫x p(x) dx\E[X] = \int x\,p(x)\,\dd x: the probability-weighted average, the centre of mass of the distribution. More generally 𝔼[g(X)]=∫g(x) p(x) dx\E[g(X)] = \int g(x)\,p(x)\,\dd x β€” and the expected loss over the data distribution is what learning really minimizes.

Why does it exist?

To summarize a random quantity by one number that behaves well: it is linear, it is what averages of many samples converge to (law of large numbers), and decisions that maximize expected value are optimal in the long run.

Intuition

Balance the graph of the density on a knife edge: it balances at 𝔼[X]\E[X]. And the average of NN independent samples estimates it with error about Οƒ/N\sigma/\sqrt N β€” the principle behind Monte Carlo, mini-batch gradients and A/B tests.

Formal definition

𝔼[g(X)]=βˆ«βˆ’βˆžβˆžg(x) p(x) dx\E[g(X)] = \int_{-\infty}^{\infty} g(x)\,p(x)\,\dd x when the integral converges absolutely. Linearity: 𝔼[aX+bY]=a𝔼[X]+b𝔼[Y]\E[aX + bY] = a\E[X] + b\E[Y] (always, even for dependent variables). Law of large numbers: 1Nβˆ‘i=1Ng(Xi)→𝔼[g(X)]\frac1N\sum_{i=1}^N g(X_i) \to \E[g(X)] for i.i.d. samples.

Formulas

𝔼[g(X)]=∫g(x) p(x) dxβ‰ˆ1Nβˆ‘i=1Ng(xi)\E[g(X)] = \int g(x)\,p(x)\,\dd x \approx \frac1N\sum_{i=1}^{N} g(x_i)
R(ΞΈ)=𝔼(x,y)∼P[β„“(fΞΈ(x),y)]β‰ˆ1∣Bβˆ£βˆ‘(x,y)∈Bβ„“(fΞΈ(x),y)R(\theta) = \E_{(x,y)\sim P}\big[\ell(f_\theta(x), y)\big] \approx \frac{1}{|B|}\sum_{(x,y)\in B}\ell(f_\theta(x), y)
expected risk and its mini-batch estimate
βˆ‡ΞΈβ€‰π”Ό[β„“]=𝔼[βˆ‡ΞΈβ€‰β„“]\nabla_\theta\,\E[\ell] = \E[\nabla_\theta\,\ell]
why stochastic gradients are unbiased

Why does it matter?

Training minimizes an expectation it cannot compute, by following unbiased noisy estimates of its gradient (SGD). Reinforcement learning maximizes expected return. Monte Carlo rendering computes pixel colours as expectations over random light paths.

Where it shows up in computing

  • Monte Carlo methodsβ˜…β˜…β˜…β˜…β˜…fundamentalScientific computing and algorithms

    Monte Carlo estimates expectations by sample averages.

  • Queueing theory and performanceβ˜…β˜…β˜…β˜…β˜…frequentOptimization and systems

    Little's law L=Ξ»WL = \lambda W relates expected queue length and expected waiting time.

Where it shows up in AI

  • Loss functionβ˜…β˜…β˜…β˜…β˜…fundamentalAI and machine learning

    The objective of learning is the expected loss (risk) over the data distribution.

  • Stochastic gradient descent (SGD)β˜…β˜…β˜…β˜…β˜…fundamentalAI and machine learning

    A mini-batch gradient is an unbiased estimate of the expected gradient.

  • Reinforcement learningβ˜…β˜…β˜…β˜…β˜…fundamentalAI and machine learning

    Agents maximize expected discounted return; policy gradients differentiate an expectation.

Where is it used?

Computing topics reachable from here, through the chain of ideas that leads to them:

Ξ» Scientific computing and algorithms

β„’ AI and machine learning

3D Computer graphics

βš™ Robotics and control

⇄ Optimization and systems

What depends on it

Exercises

1Computation

Compute 𝔼[X]\E[X] for the exponential density p(x)=Ξ»eβˆ’Ξ»xp(x) = \lambda e^{-\lambda x}, xβ‰₯0x \ge 0.

Solution

By parts: ∫0∞xΞ»eβˆ’Ξ»x dx=[βˆ’xeβˆ’Ξ»x]0∞+∫0∞eβˆ’Ξ»x dx=1Ξ»\int_0^\infty x\lambda e^{-\lambda x}\,\dd x = \big[-xe^{-\lambda x}\big]_0^\infty + \int_0^\infty e^{-\lambda x}\,\dd x = \frac1\lambda.

2AI

Why is the gradient of a random mini-batch loss an unbiased estimate of the full gradient? What assumption is needed?

Solution

If the batch is drawn uniformly at random, 𝔼[1∣Bβˆ£βˆ‘i∈Bβˆ‡β„“i]=1Nβˆ‘iβˆ‡β„“i\E[\frac1{|B|}\sum_{i\in B}\nabla\ell_i] = \frac1N\sum_i\nabla\ell_i by linearity of expectation (and exchanging gradient and expectation, which needs mild smoothness). Non-random batches (e.g. sorted data) break it.

↑ ↓ to navigate Β· ↡ Β· Esc