Skip to content

cheap.md

Latest commit

 

History

History
662 lines (500 loc) · 27.4 KB

cheap.md

File metadata and controls

662 lines (500 loc) · 27.4 KB
Raw

Paper Analysis: “Why does deep and cheap learning work so well?”

Authors: Henry W. Lin, Max Tegmark, David Rolnick

Affiliation: Dept. of Physics, Harvard University; Dept. of Physics & Mathematics, MIT

Published in: Journal of Statistical Physics (2017)

arXiv: 1608.08225

Core Thesis: The success of deep learning depends not only on mathematics but also on physics. Properties frequently encountered in physics — symmetry, locality, compositionality, and polynomial log-probability — translate into exceptionally simple neural networks that can be approximated with exponentially fewer parameters than generic functions.

1. Core Ideas and Key Formulas

1.1 The “Swindle”: Why Cheap Learning Works

There are $2^{2^n}$ different Boolean functions of $n$ variables, so a generic function requires at least $2^n$ bits to describe. The fact that neural networks of feasible size are nonetheless so useful implies that the class of functions we care about approximating is dramatically smaller.

1.2 Bayes’ Theorem in Hamiltonian Form

Define the Hamiltonian (negative log-probability):

$$ H_y(\mathbf{x}) \equiv -\ln p(\mathbf{x}|y), \qquad \mu_y \equiv -\ln p(y) \tag{2} $$

Bayes’ theorem becomes the Boltzmann form:

$$ p(y|\mathbf{x}) = \frac{1}{N(\mathbf{x})} e^{-[H_y(\mathbf{x}) + \mu_y]} \tag{3} $$

where

$$ N(\mathbf{x}) \equiv \sum_y e^{-[H_y(\mathbf{x}) + \mu_y]} \tag{4} $$

In vector notation:

$$ \mathbf{p}(\mathbf{x}) = \frac{1}{N(\mathbf{x})} e^{-[\mathbf{H}(\mathbf{x}) + \boldsymbol{\mu}]} \tag{5} $$

This is equivalent to a softmax layer:

$$ \mathbf{p}(\mathbf{x}) = \tilde{\boldsymbol{\sigma}}[-\mathbf{H}(\mathbf{x}) - \boldsymbol{\mu}] \tag{8} $$

1.3 Feedforward Neural Network

A standard $n$-layer feedforward neural network:

$$ \mathbf{f}(\mathbf{x}) = \boldsymbol{\sigma}_n \mathbf{A}_n \cdots \boldsymbol{\sigma}_2 \mathbf{A}_2 \boldsymbol{\sigma}_1 \mathbf{A}_1 \mathbf{x} \tag{6} $$

where $\mathbf{A}_i \mathbf{x} = \mathbf{W}_i \mathbf{x} + \mathbf{b}_i$ are affine transformations.

1.4 Polynomial Expansion of Hamiltonians

Any Hamiltonian can be expanded as a power series:

$$ H_y(\mathbf{x}) = h + \sum_i h_i x_i + \sum_{i \le j} h_{ij} x_i x_j + \sum_{i \le j \le k} h_{ijk} x_i x_j x_k + \cdots \tag{9} $$

For $n$ variables, there are $(n+d)!/(n!d!)$ terms of degree up to $d$.

For binary inputs ($x_i \in {0, 1}$), since $x_i^2 = x_i$:

$$ H_y(\mathbf{x}) = h + \sum_i h_i x_i + \sum_{i < j} h_{ij} x_i x_j + \sum_{i < j < k} h_{ijk} x_i x_j x_k + \cdots \tag{12} $$

1.5 Multiplication with 4 Neurons (Key Theorem)

Theorem: Any smooth non-linear activation function $\sigma$ can approximate a multiplication gate arbitrarily well using only 4 neurons in a single hidden layer.

Let $\sigma(u) = \sigma_0 + \sigma_1 u + \sigma_2 \frac{u^2}{2} + \mathcal{O}(u^3)$.

Define the multiplication approximator:

$$ m(u,v) \equiv \frac{\sigma(u+v) + \sigma(-u-v) - \sigma(u-v) - \sigma(-u+v)}{4\sigma_2} \tag{11} $$

Then:

$$ m(u,v) = uv \left[ 1 + \mathcal{O}(u^2 + v^2) \right] $$

By scaling inputs small and outputs large, this approximation becomes exact in the limit.

Corollary: Any multivariate polynomial can be approximated by a neural network of fixed finite size (independent of accuracy $\epsilon$).

1.6 Hierarchical Processes and Markov Chains

Physical and machine-learning data often have hierarchical structure:

$$ \mathbf{p}_i = \mathbf{M}_i \mathbf{p}_{i-1} \tag{15} $$

where $\mathbf{p}_i$ is the probability distribution at hierarchy level $i$, and $\mathbf{M}_i$ is a Markov transition matrix.

1.7 No-Flattening Theorems

The paper proves various “no-flattening theorems” showing that efficient deep networks cannot be accurately approximated by shallow ones without efficiency loss.

Key example: $n$ variables cannot be multiplied using fewer than $2^n$ neurons in a single hidden layer.

2. Detailed Explanation of Mathematical Symbols

Table 1: Symbol Dictionary

Symbol Meaning Concrete Example
$p(\mathbf{x}|y)$ Conditional probability of data $\mathbf{x}$ given class/parameter $y$ Probability of a specific image of a cat given the label "cat"
$p(y|\mathbf{x})$ Conditional probability of class/parameter $y$ given data $\mathbf{x}$ Probability that an image is a cat given its pixel values (classification)
$H_y(\mathbf{x})$ Hamiltonian: $-\ln p(\mathbf{x}|y)$, the “surprisal” or negative log-likelihood If $p(\text{cat image}|\text{cat}) = 0.1$, then $H = -\ln(0.1) \approx 2.30$
$\mu_y$ Prior self-information: $-\ln p(y)$ If 10% of images are cats, $p(\text{cat}) = 0.1$, then $\mu = -\ln(0.1) \approx 2.30$
$N(\mathbf{x})$ Partition function (normalization constant) Sum over all possible classes $y$ of $e^{-[H_y(\mathbf{x}) + \mu_y]}$
$\mathbf{p}(\mathbf{x})$ Vector of probabilities $p(y|\mathbf{x})$ for all $y$ $\mathbf{p} = [p(\text{cat}|\mathbf{x}), p(\text{dog}|\mathbf{x}), \ldots]^T$
$\mathbf{H}(\mathbf{x})$ Vector of Hamiltonians $H_y(\mathbf{x})$ for all $y$ $\mathbf{H} = [H_{\text{cat}}(\mathbf{x}), H_{\text{dog}}(\mathbf{x}), \ldots]^T$
$\boldsymbol{\mu}$ Vector of prior self-informations $\mu_y$ $\boldsymbol{\mu} = [\mu_{\text{cat}}, \mu_{\text{dog}}, \ldots]^T$
$\tilde{\boldsymbol{\sigma}}$ Softmax function: $\tilde{\sigma}_i(\mathbf{z}) = e^{z_i} / \sum_j e^{z_j}$ Normalizes logits to a probability distribution
$\boldsymbol{\sigma}_i$ Element-wise non-linear activation function (e.g., ReLU, sigmoid) $\sigma(x) = \max(0, x)$ for ReLU
$\mathbf{W}_i$ Weight matrix of layer $i$ For a fully-connected layer with 256 inputs and 128 outputs: $\mathbf{W}_i \in \mathbb{R}^{128 \times 256}$
$\mathbf{b}_i$ Bias vector of layer $i$ $\mathbf{b}_i \in \mathbb{R}^{128}$
$\mathbf{A}_i$ Affine transformation: $\mathbf{A}_i \mathbf{x} = \mathbf{W}_i \mathbf{x} + \mathbf{b}_i$ A linear layer followed by bias addition
$\sigma_2$ Second derivative (curvature) of activation function at origin For $\sigma(x) = \tanh(x)$, $\sigma_2 = 0$ at origin; need to shift bias
$m(u,v)$ Multiplication approximator using 4 neurons Approximates $u \times v$ using a combination of $\sigma$ evaluations
$\mathbf{p}_i$ Probability vector at hierarchy level $i$ Distribution of states at the $i$-th level of a hierarchical generative process
$\mathbf{M}_i$ Markov transition matrix between hierarchy levels $\mathbf{M}i$ maps $\mathbf{p}{i-1} \to \mathbf{p}_i$ in a Markov chain

Table 2: Physics–Machine Learning Dictionary

Physics Machine Learning
Hamiltonian Surprisal $-\ln p$
Simple $H$ Cheap learning
Quadratic $H$ Gaussian $p$
Locality Sparsity
Translationally symmetric $H$ Convnet
Computing $p$ from $H$ Softmaxing
Spin Bit
Free energy difference KL-divergence
Effective theory Nearly lossless data distillation
Irrelevant operator Noise
Relevant operator Feature

3. Visualization Code

"""
Visualization for "Why does deep and cheap learning work so well?"
Lin, Tegmark & Rolnick (Journal of Statistical Physics, 2017)
arXiv: 1608.08225
"""

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import FancyBboxPatch, Circle, FancyArrowPatch
import matplotlib.patches as mpatches
from scipy.special import softmax


# ============================================================
# 1. Multiplication with 4 Neurons (Figure 2 from paper)
# ============================================================
def visualize_multiplication_gate():
    """Visualize the multiplication approximator with 4 neurons"""
    fig, axes = plt.subplots(1, 2, figsize=(14, 5))

    # ---- Left: Multiplication gate architecture ----
    ax1 = axes[0]
    ax1.set_xlim(0, 10)
    ax1.set_ylim(0, 6)
    ax1.axis('off')

    # Inputs
    ax1.text(0.5, 4.5, r'$u$', fontsize=16, fontweight='bold', ha='center', va='center')
    ax1.text(0.5, 1.5, r'$v$', fontsize=16, fontweight='bold', ha='center', va='center')

    # Multiplication by constants
    constants = [
        (1, 1, 4.5, 1), (1, -1, 4.5, 2), (-1, 1, 4.5, 3), (-1, -1, 4.5, 4)
    ]

    # Draw connections with constant multipliers
    y_positions = [4.5, 3.5, 2.5, 1.5]
    for i, (cu, cv, x, y_idx) in enumerate(constants):
        y = y_positions[i]

        # From u
        ax1.plot([1.0, 2.0], [4.5, y], 'k-', linewidth=1)
        ax1.text(1.5, (4.5 + y) / 2, f'{cu}', fontsize=10, ha='center', va='center', color='blue')

        # From v
        ax1.plot([1.0, 2.0], [1.5, y], 'k-', linewidth=1)
        ax1.text(1.5, (1.5 + y) / 2, f'{cv}', fontsize=10, ha='center', va='center', color='blue')

    # Sigma boxes (non-linear activation)
    for i, y in enumerate(y_positions):
        box = FancyBboxPatch((2.5, y - 0.4), 0.8, 0.8,
                              boxstyle="round,pad=0.05", edgecolor='#e74c3c',
                              facecolor='#fadbd8', linewidth=2)
        ax1.add_patch(box)
        ax1.text(2.9, y, r'$\sigma$', fontsize=12, fontweight='bold', ha='center', va='center')

    # Summation nodes (circles)
    for i, y in enumerate(y_positions):
        # From sigma to summation
        ax1.plot([3.3, 4.0], [y, y], 'k-', linewidth=1)

    # Connections to summation nodes
    # Row 1: sigma outputs to summation with coefficients
    sum_positions = [4.5, 3.5, 2.5, 1.5]
    for i, (y_from, y_to) in enumerate(zip(y_positions, sum_positions)):
        ax1.plot([4.0, 4.5], [y_from, y_to], 'k-', linewidth=1)

    # Summation nodes (circles)
    for i, y in enumerate(sum_positions):
        circle = Circle((4.8, y), 0.3, edgecolor='black', facecolor='lightyellow', linewidth=2)
        ax1.add_patch(circle)
        ax1.text(4.8, y, r'$\Sigma$', fontsize=10, fontweight='bold', ha='center', va='center')

    # Connect summation nodes to output
    # The four summation outputs feed into final output with coefficients
    # In the paper: m(u,v) = [σ(u+v)+σ(-u-v)-σ(u-v)-σ(-u+v)] / (4σ₂)
    # The coefficients are: +1, +1, -1, -1 then divide by 4σ₂

    # Draw connections from summation nodes to output
    for i, y in enumerate(sum_positions):
        coeff = 1 if i < 2 else -1
        ax1.plot([5.1, 6.0], [y, 3.0], 'k-', linewidth=1)
        if i == 0:
            ax1.text(5.5, (y + 3.0) / 2 + 0.2, f'{coeff}', fontsize=10, color='blue', ha='center')

    # Final division by 4σ₂
    div_box = FancyBboxPatch((6.2, 2.5), 1.2, 1.0,
                              boxstyle="round,pad=0.05", edgecolor='#2980b9',
                              facecolor='#d6eaf8', linewidth=2)
    ax1.add_patch(div_box)
    ax1.text(6.8, 3.0, r'$\div 4\sigma_2$', fontsize=11, fontweight='bold', ha='center', va='center')

    # Output
    ax1.plot([7.4, 8.5], [3.0, 3.0], 'k-', linewidth=2)
    ax1.text(9.0, 3.0, r'$m(u,v) \approx uv$', fontsize=16, fontweight='bold', ha='center', va='center')

    # Title
    ax1.text(5.0, 5.7, 'Multiplication Approximator (4 Neurons)',
             fontsize=14, fontweight='bold', ha='center')
    ax1.text(5.0, 5.2, r'$m(u,v) = \frac{\sigma(u+v) + \sigma(-u-v) - \sigma(u-v) - \sigma(-u+v)}{4\sigma_2}$',
             fontsize=12, ha='center', style='italic')

    # ---- Right: Accuracy vs lambda ----
    ax2 = axes[1]

    # Simulate accuracy as a function of λ (input scaling)
    lambda_vals = np.logspace(-2, 2, 100)
    # Error roughly ~ 1/λ² (from Taylor expansion)
    error = 1 / (lambda_vals ** 2 + 1e-6)
    error = np.clip(error, 0, 1)

    ax2.semilogx(lambda_vals, error, 'b-', linewidth=3, label=r'Approximation error $\propto 1/\lambda^2$')
    ax2.axhline(y=0.01, color='red', linestyle='--', alpha=0.7, label='1% error threshold')
    ax2.axvline(x=10, color='green', linestyle='-.', alpha=0.7, label=r'$\lambda \approx 10$ (practical)')

    ax2.set_xlabel(r'$\lambda$ (input scaling factor)', fontsize=13)
    ax2.set_ylabel('Approximation Error', fontsize=13)
    ax2.set_title('Accuracy vs. Input Scaling', fontsize=14, fontweight='bold')
    ax2.legend(loc='upper right', fontsize=11)
    ax2.grid(alpha=0.3)
    ax2.set_ylim(0, 0.5)

    # Annotation
    ax2.annotate('Arbitrarily accurate\nas $\lambda \to \infty$',
                 xy=(100, 0.0001), xytext=(30, 0.2),
                 arrowprops=dict(arrowstyle='->', color='blue', lw=2),
                 fontsize=11, ha='center')

    ax2.annotate('Practical regime\n$\lambda \sim 10$',
                 xy=(10, 0.01), xytext=(3, 0.08),
                 arrowprops=dict(arrowstyle='->', color='green', lw=2),
                 fontsize=11, ha='center')

    plt.tight_layout()
    plt.show()


# ============================================================
# 2. Hamiltonian Decomposition (Polynomial Expansion)
# ============================================================
def visualize_hamiltonian_decomposition():
    """Visualize the polynomial expansion of Hamiltonians"""
    fig, axes = plt.subplots(1, 2, figsize=(14, 5))

    # ---- Left: Generic vs. Structured Hamiltonians ----
    ax1 = axes[0]

    # Simulate number of parameters
    n = np.arange(1, 21)

    # Generic polynomial (all terms): ~ 2^n
    generic_params = 2 ** n

    # Low-degree polynomial (d=2): ~ n²/2
    low_degree_params = 0.5 * n ** 2

    # Local polynomial: ~ n
    local_params = 2 * n

    # Symmetric + local + low-degree: ~ constant
    symmetric_params = np.ones_like(n) * 3

    ax1.semilogy(n, generic_params, 'r-', linewidth=2.5, label='Generic (all terms)')
    ax1.semilogy(n, low_degree_params, 'orange', linewidth=2.5, label='Low-degree (d=2)')
    ax1.semilogy(n, local_params, 'g-', linewidth=2.5, label='Local (nearest-neighbor)')
    ax1.semilogy(n, symmetric_params, 'b-', linewidth=2.5, label='Symmetric + Local + Low-degree')

    ax1.set_xlabel('Number of variables (n)', fontsize=13)
    ax1.set_ylabel('Number of Parameters', fontsize=13)
    ax1.set_title('Parameter Count: Generic vs. Structured Hamiltonians', fontsize=14, fontweight='bold')
    ax1.legend(loc='upper left', fontsize=11)
    ax1.grid(alpha=0.3)

    # Annotation
    ax1.annotate('Exponential growth\n(impossible for large n)',
                 xy=(15, 2**15), xytext=(12, 2**12),
                 arrowprops=dict(arrowstyle='->', color='red', lw=2),
                 fontsize=10, color='red')

    ax1.annotate('Linear or constant\n(cheap learning!)',
                 xy=(15, 3), xytext=(12, 10),
                 arrowprops=dict(arrowstyle='->', color='blue', lw=2),
                 fontsize=10, color='blue')

    # ---- Right: Physics examples ----
    ax2 = axes[1]
    ax2.axis('off')

    # Table of physics examples
    examples = [
        ('Harmonic Oscillator', 'Quadratic (d=2)', '3 parameters'),
        ('Ising Model', 'Quadratic (d=2), local', 'O(n) parameters'),
        ('Standard Model', 'Quartic (d=4), symmetric, local', '32 parameters'),
        ('Maxwell Eqs', 'Linear (d=1), local', 'O(n²) parameters'),
        ('Navier-Stokes', 'Quadratic (d=2), local', 'O(n²) parameters'),
    ]

    # Header
    ax2.text(0.5, 4.8, 'Physics Hamiltonians are Low-Order Polynomials',
             fontsize=14, fontweight='bold', ha='center')

    y_pos = 4.2
    for name, degree, params in examples:
        ax2.text(0.1, y_pos, name, fontsize=12, fontweight='bold', va='center')
        ax2.text(0.45, y_pos, degree, fontsize=11, va='center', style='italic')
        ax2.text(0.8, y_pos, params, fontsize=11, va='center', color='#2980b9')
        y_pos -= 0.6

    # Box around the table
    rect = FancyBboxPatch((0.05, 1.8), 0.9, 3.2,
                           boxstyle="round,pad=0.05", edgecolor='#2c3e50',
                           facecolor='none', linewidth=2)
    ax2.add_patch(rect)

    ax2.text(0.5, 1.5, 'Low polynomial order (d=2 to 4) is common in physics',
             fontsize=11, ha='center', style='italic', color='#555')

    # Citation
    ax2.text(0.5, 0.3, 'From Lin, Tegmark & Rolnick (2017)',
             fontsize=10, ha='center', style='italic', color='#888')

    plt.tight_layout()
    plt.show()


# ============================================================
# 3. Hierarchical Structure (Figure 3 from paper)
# ============================================================
def visualize_hierarchical_structure():
    """Visualize hierarchical / compositional structure"""
    fig, axes = plt.subplots(1, 2, figsize=(14, 5))

    # ---- Left: Hierarchical Markov chain ----
    ax1 = axes[0]
    ax1.set_xlim(0, 10)
    ax1.set_ylim(0, 5)
    ax1.axis('off')

    # Hierarchy levels
    levels = ['$y_0$', '$y_1$', '$y_2$', '$y_3$', '$y_4$', '...', '$y_n$']
    x_positions = [0.5, 2.0, 3.5, 5.0, 6.5, 8.0, 9.5]

    for i, (label, x) in enumerate(zip(levels, x_positions)):
        # Box
        box = FancyBboxPatch((x - 0.4, 2.0 - 0.4), 0.8, 0.8,
                              boxstyle="round,pad=0.05", edgecolor='#2980b9',
                              facecolor='#d6eaf8', linewidth=2)
        ax1.add_patch(box)
        ax1.text(x, 2.0, label, fontsize=14, fontweight='bold', ha='center', va='center')

        # Arrow to next
        if i < len(levels) - 1:
            ax1.annotate('', xy=(x_positions[i+1] - 0.4, 2.0), xytext=(x + 0.4, 2.0),
                         arrowprops=dict(arrowstyle='->', color='#e74c3c', lw=2.5))

    # Markov matrix label above arrows
    for i in range(len(levels) - 1):
        mid_x = (x_positions[i] + x_positions[i+1]) / 2
        ax1.text(mid_x, 2.8, r'$\mathbf{M}_{i+1}$', fontsize=12, fontweight='bold',
                 ha='center', color='#e74c3c')

    # Equation
    ax1.text(5.0, 0.6, r'$\mathbf{p}_i = \mathbf{M}_i \mathbf{p}_{i-1}$',
             fontsize=16, fontweight='bold', ha='center')

    ax1.text(5.0, 4.5, 'Hierarchical Generative Process (Markov Chain)',
             fontsize=14, fontweight='bold', ha='center')
    ax1.text(5.0, 4.0, 'Each level depends only on its immediate predecessor',
             fontsize=12, ha='center', style='italic')

    # ---- Right: Depth efficiency ----
    ax2 = axes[1]

    # Simulate number of neurons needed for shallow vs deep networks
    n_layers = np.arange(1, 21)
    # Shallow: exponential growth in neurons
    shallow_neurons = 2 ** (n_layers / 2)
    # Deep: linear growth in neurons
    deep_neurons = 2 * n_layers

    ax2.semilogy(n_layers, shallow_neurons, 'r-', linewidth=3, label='Shallow Network (1 hidden layer)')
    ax2.semilogy(n_layers, deep_neurons, 'g-', linewidth=3, label='Deep Network (hierarchical)')

    # Mark the "no-flattening" result
    ax2.axvline(x=10, color='purple', linestyle='--', alpha=0.7,
                label=r'$n$ variables need $\geq 2^n$ neurons in 1 layer')

    ax2.set_xlabel('Problem Complexity / Hierarchy Depth', fontsize=13)
    ax2.set_ylabel('Number of Neurons Required', fontsize=13)
    ax2.set_title('Depth Efficiency: Shallow vs. Deep Networks', fontsize=14, fontweight='bold')
    ax2.legend(loc='upper left', fontsize=11)
    ax2.grid(alpha=0.3)

    # Annotations
    ax2.annotate('Exponential growth\n(impractical for large n)',
                 xy=(15, 2**(15/2)), xytext=(12, 2**7),
                 arrowprops=dict(arrowstyle='->', color='red', lw=2),
                 fontsize=10, color='red')

    ax2.annotate('Linear growth\n(efficient!)',
                 xy=(15, 30), xytext=(12, 15),
                 arrowprops=dict(arrowstyle='->', color='green', lw=2),
                 fontsize=10, color='green')

    # No-flattening theorem
    ax2.text(12, 500, r'No-Flattening Theorem:', fontsize=11, fontweight='bold')
    ax2.text(12, 350, r'$n$ variables need $\geq 2^n$', fontsize=10)
    ax2.text(12, 250, r'neurons in a single layer', fontsize=10)

    plt.tight_layout()
    plt.show()


# ============================================================
# 4. Symmetry, Locality, and Polynomial Order
# ============================================================
def visualize_cheap_learning_factors():
    """Visualize the three factors enabling cheap learning"""
    fig, ax = plt.subplots(figsize=(12, 6))

    # Data
    factors = ['Generic\nFunction', '+ Low\nPolynomial Order', '+ Locality', '+ Symmetry']
    param_counts = [2**10, 10**2/2, 2*10, 3]  # for n=10

    colors = ['#e74c3c', '#f39c12', '#3498db', '#2ecc71']

    bars = ax.bar(factors, param_counts, color=colors, edgecolor='black', linewidth=1.5, width=0.6)

    # Add value labels
    for bar, count in zip(bars, param_counts):
        height = bar.get_height()
        ax.text(bar.get_x() + bar.get_width()/2., height + 0.5,
                f'{count:.0f}', ha='center', va='bottom', fontsize=12, fontweight='bold')

    ax.set_ylabel('Number of Parameters (n=10)', fontsize=13)
    ax.set_title('How Symmetry, Locality & Low Order Enable "Cheap Learning"',
                 fontsize=14, fontweight='bold')
    ax.set_yscale('log')
    ax.grid(axis='y', alpha=0.3)

    # Add reduction annotations
    ax.annotate('×500 reduction', xy=(1, 500), xytext=(0.5, 200),
                arrowprops=dict(arrowstyle='->', color='#e74c3c', lw=2),
                fontsize=10, color='#e74c3c')

    ax.annotate('×25 reduction', xy=(2, 50), xytext=(1.5, 20),
                arrowprops=dict(arrowstyle='->', color='#f39c12', lw=2),
                fontsize=10, color='#f39c12')

    ax.annotate('×6.7 reduction', xy=(3, 20), xytext=(2.5, 8),
                arrowprops=dict(arrowstyle='->', color='#3498db', lw=2),
                fontsize=10, color='#3498db')

    # Example from paper
    ax.text(0.5, 0.5, 'Example: Microphone recording\nn=10 time steps',
            fontsize=10, style='italic', color='#555')

    plt.tight_layout()
    plt.show()


# ============================================================
# 5. Softmax and Hamiltonian Visualization
# ============================================================
def visualize_softmax_hamiltonian():
    """Visualize the relation between Hamiltonian and softmax output"""
    fig, axes = plt.subplots(1, 2, figsize=(14, 5))

    # ---- Left: Hamiltonian landscape ----
    ax1 = axes[0]

    x = np.linspace(-4, 4, 100)
    # Simulate Hamiltonians for 3 classes
    H1 = 0.5 * (x - 1) ** 2 + 0.5
    H2 = 0.5 * (x + 1) ** 2 + 0.5
    H3 = 0.3 * (x + 2) ** 2 + 1.5

    ax1.plot(x, H1, 'r-', linewidth=2.5, label=r'$H_1(x)$ (class 1)')
    ax1.plot(x, H2, 'g-', linewidth=2.5, label=r'$H_2(x)$ (class 2)')
    ax1.plot(x, H3, 'b-', linewidth=2.5, label=r'$H_3(x)$ (class 3)')

    ax1.set_xlabel(r'$\mathbf{x}$ (data)', fontsize=13)
    ax1.set_ylabel(r'$H_y(\mathbf{x})$ (Hamiltonian / surprisal)', fontsize=13)
    ax1.set_title('Hamiltonians for Different Classes', fontsize=14, fontweight='bold')
    ax1.legend(loc='upper right', fontsize=11)
    ax1.grid(alpha=0.3)

    # Mark a sample point
    ax1.axvline(x=0.5, color='purple', linestyle='--', alpha=0.7, label=r'$\mathbf{x}=0.5$')
    ax1.plot(0.5, H1[np.argmin(np.abs(x - 0.5))], 'ro', markersize=10)
    ax1.plot(0.5, H2[np.argmin(np.abs(x - 0.5))], 'go', markersize=10)
    ax1.plot(0.5, H3[np.argmin(np.abs(x - 0.5))], 'bo', markersize=10)

    # ---- Right: Softmax output ----
    ax2 = axes[1]

    # Compute softmax from Hamiltonians (with μ=0 for simplicity)
    H_matrix = np.array([H1, H2, H3])
    logits = -H_matrix  # p(y|x) ∝ exp(-H_y(x))
    softmax_output = softmax(logits, axis=0)

    ax2.plot(x, softmax_output[0, :], 'r-', linewidth=2.5, label=r'$p(y=1|\mathbf{x})$')
    ax2.plot(x, softmax_output[1, :], 'g-', linewidth=2.5, label=r'$p(y=2|\mathbf{x})$')
    ax2.plot(x, softmax_output[2, :], 'b-', linewidth=2.5, label=r'$p(y=3|\mathbf{x})$')

    ax2.set_xlabel(r'$\mathbf{x}$ (data)', fontsize=13)
    ax2.set_ylabel(r'$p(y|\mathbf{x})$ (probability)', fontsize=13)
    ax2.set_title('Softmax Output: $p(y|\mathbf{x}) = \text{softmax}(-H_y(\mathbf{x}))$',
                  fontsize=14, fontweight='bold')
    ax2.legend(loc='upper right', fontsize=11)
    ax2.grid(alpha=0.3)
    ax2.set_ylim(0, 1.05)

    # Mark sample point
    ax2.axvline(x=0.5, color='purple', linestyle='--', alpha=0.7)

    plt.tight_layout()
    plt.show()


# ============================================================
# Execute visualizations
# ============================================================
if __name__ == "__main__":
    print("=" * 70)
    print("Why does deep and cheap learning work so well?")
    print("Lin, Tegmark & Rolnick (Journal of Statistical Physics, 2017)")
    print("arXiv: 1608.08225")
    print("=" * 70)
    print("\nVisualizing Core Concepts...\n")

    print("1. Multiplication with 4 Neurons (Theorem)...")
    visualize_multiplication_gate()

    print("2. Hamiltonian Decomposition...")
    visualize_hamiltonian_decomposition()

    print("3. Hierarchical Structure & Depth Efficiency...")
    visualize_hierarchical_structure()

    print("4. Cheap Learning Factors (Symmetry, Locality, Low Order)...")
    visualize_cheap_learning_factors()

    print("5. Softmax and Hamiltonian Relation...")
    visualize_softmax_hamiltonian()

    print("\n" + "=" * 70)
    print("Key Takeaways:")
    print("1. Neural networks can approximate any function, but generic functions")
    print("   require exponentially many parameters.")
    print("2. Physics-inspired properties (symmetry, locality, low polynomial order)")
    print("   enable 'cheap learning' with far fewer parameters.")
    print("3. Multiplication can be approximated arbitrarily well with only 4 neurons.")
    print("4. Deep networks are more efficient than shallow ones for hierarchical data.")
    print("5. No-flattening theorems: n variables cannot be multiplied using fewer")
    print("   than 2^n neurons in a single hidden layer.")
    print("=" * 70)

Code Output Interpretation

Visualization Content Key Insight
Multiplication Gate Architecture using 4 neurons + accuracy vs. λ Any smooth nonlinearity can approximate multiplication arbitrarily well
Hamiltonian Decomposition Parameter count: generic vs. structured Symmetry + locality + low order → O(1) parameters
Hierarchical Structure Markov chain + depth efficiency Deep networks are exponentially more efficient for hierarchical data
Cheap Learning Factors Reduction from generic to symmetric Each constraint reduces parameters dramatically
Softmax Hamiltonian Hamiltonian → softmax probability Classification = softmax(−Hamiltonian)

4. Academic Sources

Core Contributions Summary

  1. Cheap Learning: The functions of practical interest can be approximated with exponentially fewer parameters than generic ones due to symmetry, locality, and low polynomial order

  2. Multiplication with 4 Neurons: Any smooth nonlinear activation can approximate multiplication arbitrarily well using only 4 neurons in a single hidden layer

  3. Hamiltonian Perspective: Classification problems reduce to computing Hamiltonians $H_y(\mathbf{x}) = -\ln p(\mathbf{x}|y)$ followed by a softmax layer

  4. No-Flattening Theorems: Efficient deep networks cannot be accurately approximated by shallow ones without efficiency loss; e.g., $n$ variables cannot be multiplied using fewer than $2^n$ neurons in a single hidden layer

  5. Hierarchical Efficiency: When data has hierarchical/compositional structure (common in physics and machine learning), deep networks are exponentially more efficient than shallow ones