Fundamentals of Learning¶

Table of Contents

Entropy, Cross-Entropy, NLL, KL¶

Categorical distribution with number of classes C.
Labels: \(y_i=\{0,1\}^{C}\in\mathbb{R}^C\), one-hot.
Empirical distribution: \(\hat{p}=\frac{1}{N}\sum_{i=1}^N y_i\in\mathbb{R}^C\)

\[\hat{p}(k)=\frac{1}{N}\sum_{i=1}^N\mathbb{1}(y_i(k)=1)\in\mathbb{R}\]
Predicted probability:
- Density function learned: \(\pi\), \(\pi(k)\) for each category.
- For sample \(i\): Sample from \(\pi\), \(\pi_i\in\mathbb{R}^C\)
- For class \(k\): \(\pi_i(k)\in\mathbb{R},k=1\dots C\)
- For true class: \(\pi(y_i)\in\mathbb{R}=\pi_i^Ty_i\)
Aggregate predictive probability:

\[\bar{\pi}(k)=\frac{1}{N}\sum_{i=1}^N\pi_i(k)\]
Entropy: \(H(p)=-p\log(p)=-\sum_{k=1}^C p_k\log(p_k)\)
Empirical entropy:

\[H(\hat{p})=-\sum_{k=1}^C \hat{p}\log(\hat{p})\]
Entropy of predicted probability:

\[H(\pi)\approx-\frac{1}{N}\sum_{i=1}^N H(\pi_i)=-\frac{1}{N}\sum_{i=1}^N \sum_{k=1}^C \pi_i(k)\log(\pi_i(k))\]
Cross-entropy:

\[H(\hat{p},\pi)=-\sum_{k=1}^C \hat{p}(k)\log(\pi(k))\approx-\frac{1}{N}\sum_{k=1}^C\sum_{i=1}^N\mathbb{1}(y_i(k)=1)\log(\pi_i(k))=-\frac{1}{N}\sum_{i=1}^N y_i^T\log(\pi_i)=-\frac{1}{N}\sum_{i=1}^N \log(\pi(y_i))=NLL\]
KL

\[KL(\hat{p}||\pi)=\hat{p}\log(\frac{\hat{p}}{\pi})=\sum_{k=1}^C \hat{p}(k)\log(\frac{\hat{p}(k)}{\pi(k)})=H(\hat{p},\pi)-H(\hat{p})\]

Note

Note

Prerequisies:
- Matrix Algebra and Calculus - Geometric View, Identities
- Taylor Approximation
Unconstrained: First and Second Order Methods
- First Order Methods
  - Exact: Gradient Descent Variants
  - Approximate: Stochastic Gradient Descent Variants
- Second Order Methods
  - Exact: Newton’s Method
  - Approximate: Gauss-Newton’s Hessian Approximation
Constrained
- Lagrange Multipliers
- KKT