Skip to content

Logarithmic functions

Level FundamentalDifficulty ★★★★★Concept⌖ Open in the map

What is it?

The inverse of the exponential: $\log_a x$ is the power you raise $a$ to in order to get $x$ . Logarithms turn products into sums, which is why they appear in algorithm costs, information theory and every loss function based on likelihood.

Intuition

$\log_2 n$ counts how many times you can halve $n$ before reaching 1 — the number of steps of binary search, the depth of a balanced tree, the number of bits needed to write $n$ .

Formulas

$\log(xy) = \log x + \log y, \qquad \frac{\dd}{\dd x}\ln x = \frac1x$; $\log \prod_i p(x_i) = \sum_i \log p(x_i)$
products of probabilities become sums

Where it shows up in computing

Algorithm analysis and complexity★★★★★fundamentalScientific computing and algorithms
Binary search is $O(\log n)$ and comparison sorting $\Theta(n \log n)$ .
Floating point (IEEE 754)★★★★★frequentScientific computing and algorithms
Multiplying many small probabilities underflows to 0; summing their logs (log-sum-exp) does not.

Where it shows up in AI

Loss function★★★★★fundamentalAI and machine learning
Cross-entropy is a negative log-likelihood; the log turns a product over samples into a sum.

Where is it used?

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

λ Scientific computing and algorithms

Algorithm analysis and complexity★★★★★
Derivatives of elementary functions→Antiderivatives and indefinite integrals→Symbolic computation (CAS)★★★★★
Orders of growth→Asymptotic notation (O, o, Ω, Θ)→Order of convergence→Scientific computing★★★★★
Derivatives of elementary functions→Antiderivatives and indefinite integrals→Fundamental theorem of calculus→Cumulative distribution function→Monte Carlo methods★★★★★
Floating point (IEEE 754)★★★★★

ℒ AI and machine learning

Loss function★★★★★
Loss function→Gradient descent★★★★★
Maximum likelihood estimation→Logistic regression★★★★★
Derivatives of elementary functions→Activation functions★★★★★
Loss function→Regularization★★★★★
Loss function→Support vector machines★★★★★
+14

⚙ Robotics and control

Derivatives of elementary functions→Antiderivatives and indefinite integrals→Ordinary differential equations→Control theory★★★★★
Derivatives of elementary functions→Antiderivatives and indefinite integrals→Ordinary differential equations→Control theory→Trajectory optimization and MPC★★★★★
Derivatives of elementary functions→Antiderivatives and indefinite integrals→Ordinary differential equations→Laplace transform→PID control★★★★★

⚛ Physics and simulation

Derivatives of elementary functions→Antiderivatives and indefinite integrals→Ordinary differential equations→Classical mechanics★★★★★
Derivatives of elementary functions→Antiderivatives and indefinite integrals→Ordinary differential equations→Physics engines★★★★★
Derivatives of elementary functions→Antiderivatives and indefinite integrals→Ordinary differential equations→Population and epidemic models★★★★★
Derivatives of elementary functions→Antiderivatives and indefinite integrals→Integration by parts→Finite element method★★★★★
Derivatives of elementary functions→Antiderivatives and indefinite integrals→Ordinary differential equations→Physics engines→N-body gravitational simulation★★★★★
Derivatives of elementary functions→Antiderivatives and indefinite integrals→Ordinary differential equations→Partial differential equations→Heat equation and diffusion★★★★★
+2

⇄ Optimization and systems

Loss function→Gradient descent→Recommender systems★★★★★
Derivatives of elementary functions→Antiderivatives and indefinite integrals→Fundamental theorem of calculus→Cumulative distribution function→Queueing theory and performance★★★★★

∿ Signals, media and vision

Derivatives of elementary functions→Antiderivatives and indefinite integrals→Partial fractions→Digital filters★★★★★
Derivatives of elementary functions→Antiderivatives and indefinite integrals→Integration by substitution→Trigonometric integrals→Signal processing★★★★★
Derivatives of elementary functions→Antiderivatives and indefinite integrals→Ordinary differential equations→Partial differential equations→Image processing and computer vision★★★★★

What depends on it

Exercises

1Computing

Why do ML libraries compute $\log \sum_i e^{z_i}$ as $m + \log\sum_i e^{z_i - m}$ with $m = \max_i z_i$ ?

Solution

Both are equal since $e^{z_i} = e^m e^{z_i - m}$ . But $e^{1000}$ overflows a double, while every $e^{z_i - m} \le 1$ and at least one equals 1, so the sum is in $[1, n]$ and safe.