# 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 ```python """ 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 - **Original Paper**: Lin, H. W., Tegmark, M., & Rolnick, D. (2017). Why does deep and cheap learning work so well? *Journal of Statistical Physics*, 168(6), 1223-1247 - **arXiv Preprint**: https://arxiv.org/abs/1608.08225 - **Published Version**: https://link.springer.com/article/10.1007/s10955-017-1836-5 - **Journal**: Journal of Statistical Physics, Springer ### 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