Backprop 100 Years

Rethink Differentiation from Combinators and Path Integrals

Kangbo Li

06/28/24

Department of Computer Science, Cornell University

Joint work with Prof. Anil Damle

A Complete Basis for Computable Functions

A portraint of Moses Schronfinkel in 1922

Moses Schönfinkel

A portraint of Haskell Curry

Haskell Curry

Schönfinkel, Moses (1924)

Über die Bausteine der mathematischen Logik

$\mathbf{C} \triangleq f \mapsto (x \mapsto (y \mapsto (f(y))(x)))$

$\mathbf{B} \triangleq f \mapsto (g \mapsto (x \mapsto f(g(x))))$

The Hamilton Principle

Feynman's Path Integral

$\int_{C(\mathbb{R})} \mathcal{F}(x) \mathrm{d} x$

Path Dirac Delta

$\delta(x, y, 1)$

$$ \int_{C(\mathbb{R})} \delta(x, y, \mathcal{F}(x)) \mathrm{d} x = (x \mapsto \mathcal{F}(x))(y) = \mathcal{F}(y). $$

Rethink Differentiation

$\mathbf{B}$ rule

$$ \begin{aligned} \mathcal{P}&\left( x \mapsto \mathbf{B}(f)(g)(x) \right) = (x, k) \mapsto \\ & \mathcal{P}\left( x \mapsto g(x)\right) (x, \mathcal{P}\left( f \right)(g(x), k)) +\\ & {\color{cyan} \mathcal{P}\left( x \mapsto f\right) (x, i \mapsto \delta(g(x), i, k))} \end{aligned} $$

$\mathbf{C}$ rule

$$ \begin{aligned} \mathcal{P}& \left(\mathbf{C}(g)\right) =\\ &(x, k) \mapsto {\color{cyan} \int \mathcal{P}\left( g(b) \right)(x, k(b))) \mathrm{d} b } \end{aligned} $$

$\mathbf{B}$ & $\mathbf{C}$

Pullback

$\longrightarrow$

$\longleftarrow$

Contract

Path Integral

Dirac Delta

Implications on Scientific Computing and AI

Demote backpropagtion $\Rightarrow$ Separate differentiation from numerics

Better Diff Systems for Science

  • "Doesn't work for my function"
  • "It eats all my memory"
  • "No UPCXX integration"
  • "I need to know what my code does"
  • "My gradient has structures"

More general, efficient, modular, and transparent.

Symbolic AI

  • Analytic Backprop
  • Tensor Calculus
  • Infinite Dim
  • Manifold Argmin
  • ODE Solve

Demo: CombDiff.jl

Conclusion

1.

A Model of Differentiation

Combinatory logic $\leftrightarrow$ path integrals

2.

Implications on AI and Scientific Computing

Backprop is no longer special, and differentiation is simple

3.

Prototype Demo: CombDiff.jl

Differential tensor calculus & backprop an MLP analytically

Preprint: Automating Variational Differentiation

https://arxiv.org/abs/2406.16154

Acknowledgement