The Modern Mathematics of Deep Learning

A finite symmetrization example

Penguin learning project

The project uses 342 complete Palmer penguin records: 240 training-pool and 102 held-out rows. The selected training rows determine feature scaling and model parameters. Source CSV

This project trains weights with softmax, unlike the homepage lab, which uses nearest species averages. Same penguin measurements; different classification methods. Predictions can differ.

Generalization and risk bounds · Relate sample behavior to population risk under stated assumptions.

The project supplies finite observations and fitted parameters. A held-out sample does not establish population bounds or prove a theorem.

Consider this concept alongside the project; its source assumptions may differ. These observations do not prove a theorem.

Input: 12 × 2; Held-out evaluation: 102 · #58 · 40.6 mm, 193 mm. Known answer: Adélie; Prediction: Adélie · [≈0.7383, ≈0.2444, ≈0.01737].

Used in these source sections: 1.2.3 Does it work on new examples? · 1.2 Learning from examples

The source compares a sample with an independent ghost sample, then bounds the expected gap using random signs.

This toy enumerates every sample, ghost sample, and sign pair for a two-example Bernoulli distribution and the class {0,z}.

The calculation makes the expectation and finite supremum explicit.

Source formula example

\begin{split}{\mathbbm{E}}\big[{\varepsilon}^{\mathrm{gen}}\big]={\mathbbm{E}}\Big[\sup_{f\in{\mathcal{F}}}|{\mathcal{R}}(f)-\widehat{\mathcal{R}}_{S}(f)|\Big]&={\mathbbm{E}}\Big[\sup_{g\in{\mathcal{G}}}\frac{1}{m}\big|\sum_{i=1}^{m}{\mathbbm{E}}\big[g(\widetilde{Z}^{(i)})-g(Z^{(i)})|{S}\big]\big|\Big]\\ &\leq{\mathbbm{E}}\Big[\sup_{g\in{\mathcal{G}}}\frac{1}{m}\big|\sum_{i=1}^{m}g(\widetilde{Z}^{(i)})-g(Z^{(i)})\big|\Big]\\ &={\mathbbm{E}}\Big[\sup_{g\in{\mathcal{G}}}\frac{1}{m}\big|\sum_{i=1}^{m}\tau_{i}\big(g(\widetilde{Z}^{(i)})-g(Z^{(i)})\big)\big|\Big]\\ &\leq 2{\mathbbm{E}}\Big[\sup_{g\in{\mathcal{G}}}\frac{1}{m}\big|\sum_{i=1}^{m}\tau_{i}g(Z^{(i)})\big|\Big],\end{split}

illustration · This exhaustively computes a finite toy distribution and class. It does not prove the source inequalities for general classes. The source uses hidden constants in its two-sided comparison.

Symbols

$\mathcal{G}$: A class of loss functions.
$\widehat{Z}$: Independent ghost examples with the same distribution as the training examples.
$τ_i$: Independent uniform random signs.
$ℜ_m$: Rademacher complexity.

Source formula example

This source example uses its own inputs and assumptions. Editing it does not change the project.

Edit a value or the code, then run the example. This is a finite demonstration, not a proof of the paper’s theorem.

This example’s data flow

Initial values in code

pairs = [ [0, 0], [0, 1], [1, 0], [1, 1], ]
signs = [ [-1, -1], [-1, 1], [1, -1], [1, 1], ]

Calculated here

Result expression: { expectedGap, ghostGap, ghostMeanRisk, signedGhostGap, complexity, twiceComplexity: 2 * complexity, lowerExpression: complexity - 1 / Math.sqrt(2), }

expectedGap = average(pairs.map((sample) => Math.abs(0.5 - mean(sample)))) Uses: average, pairs, mean
ghostGap = average( pairs.flatMap((sample) => pairs.map((ghost) => Math.abs(mean(ghost) - mean(sample)))), ) Uses: average, pairs, mean
ghostMeanRisk = average(pairs.map(mean)) Uses: average, pairs, mean
signedGhostGap = average( pairs.flatMap((sample) => pairs.flatMap((ghost) => signs.map((sign) => Math.abs( (sign[0] * (ghost[0] - sample[0]) + sign[1] * (ghost[1] - sample[1])) / 2, ), ), ), ), ) Uses: average, pairs, signs
complexity = average( pairs.flatMap((sample) => signs.map((sign) => Math.abs((sample[0] * sign[0] + sample[1] * sign[1]) / 2)), ), ) Uses: average, pairs, signs

Returns

Example result

expectedGap: 0.25
ghostGap: 0.375
ghostMeanRisk: 0.5
signedGhostGap: 0.375
complexity: 0.375
twiceComplexity: 0.75
lowerExpression: ≈-0.3321

JavaScript

const pairs = [
  [0, 0],
  [0, 1],
  [1, 0],
  [1, 1],
];
const signs = [
  [-1, -1],
  [-1, 1],
  [1, -1],
  [1, 1],
];
const mean = (values) => (values[0] + values[1]) / 2;
const average = (values) => values.reduce((a, b) => a + b, 0) / values.length;
const expectedGap = average(pairs.map((sample) => Math.abs(0.5 - mean(sample))));
const ghostGap = average(
  pairs.flatMap((sample) => pairs.map((ghost) => Math.abs(mean(ghost) - mean(sample)))),
);
const ghostMeanRisk = average(pairs.map(mean));
const signedGhostGap = average(
  pairs.flatMap((sample) =>
    pairs.flatMap((ghost) =>
      signs.map((sign) =>
        Math.abs(
          (sign[0] * (ghost[0] - sample[0]) + sign[1] * (ghost[1] - sample[1])) / 2,
        ),
      ),
    ),
  ),
);
const complexity = average(
  pairs.flatMap((sample) =>
    signs.map((sign) => Math.abs((sample[0] * sign[0] + sample[1] * sign[1]) / 2)),
  ),
);
return {
  expectedGap,
  ghostGap,
  ghostMeanRisk,
  signedGhostGap,
  complexity,
  twiceComplexity: 2 * complexity,
  lowerExpression: complexity - 1 / Math.sqrt(2),
};

Read numbers from input and return the result. JavaScript basics.

Result

Enable JavaScript to run this example.

Technical statement

Here m=2, each Z is an independent fair Bernoulli random variable, and G consists of the zero function and g(z)=z. The source symmetrization compares expected uniform risk gap, ghost-sample gap, and twice Rademacher complexity. The two-sided displayed relation to expected generalization error uses ≲ and therefore does not specify exact constants.

Source: Symmetrization