Independent scholarship · Open accessThe monthly digest

Indexed text attachment

operads-modules-machine-learning.tex

Source for Operads, Modules, and Differentiation in Machine Learning

View paper · Download original file

Lines 321–420 of 1174. Source text is displayed literally.

321\[322 Q_c:\mathbb R[TX_c]\longrightarrow A_c\oplus M_c,\qquad323 [(x,v)]\longmapsto ([x],\iota_xv),324\]325where \(A\oplus M\) is the square-zero extension associated to the module. The kernel is the span, for each fiber, of the relations326\begin{align*}327 [(x,v+w)]-[(x,v)]-[(x,w)]+[(x,0)],\\328 [(x,av)]-a[(x,v)]+(a-1)[(x,0)]329 \quad(a\in\mathbb R).330\end{align*}331\end{proposition}332 333\begin{proof}334The tangent map respects substitution by the ordinary chain rule. On a tuple of basis vectors \([(x_i,v_i)]\), the composite of the tangent operation and \(Q_d\) gives335\[336 \Big([f_p(\boldsymbol x)],337       \iota_{f_p(\boldsymbol x)}\sum_iD_i f_p(\boldsymbol x)v_i\Big).338\]339In the square-zero extension, only the term with no marked input and the terms with exactly one marked input survive. Their values give the same pair. This proves that \(Q\) is a morphism on basis vectors and hence on all inputs.340 341Surjectivity follows from \([(x,0)]\) and \([(x,v)]-[(x,0)]\). Each displayed relation maps to zero. In the quotient by their span, for a fixed \(x\) the assignment342\(v\mapsto[(x,v)]-[(x,0)]\) is linear. Combining this assignment with sending \(1\) to \([(x,0)]\) constructs the inverse from \(\mathbb R\oplus T_xX_c\) for that fiber. The sum over fibers supplies the claimed kernel. The relations form an operadic ideal because they are the kernel of the algebra morphism \(Q\).343\end{proof}344 345For composable unary operations \(f:X\to Y\) and \(g:Y\to Z\), write \(h=g\circ f\). The two routes in the following square have the same effect on every generator.346\[347\begin{tikzcd}[column sep=2.7em,row sep=2.6em]348 \mathbb R[TX]\arrow[r,"{\mathbb R[Th]}"]349   \arrow[d,two heads,"Q_X"']&350 \mathbb R[TZ]\arrow[d,two heads,"Q_Z"]\\351 A_X\oplus M_X\arrow[r,"h^{(1)}"']&352 A_Z\oplus M_Z .353\end{tikzcd}354\]355An implementation therefore needs the fibers visited by the program on the given data. Constructing the full free vector space would add no information to derivative evaluation at those points.356 357\section{Reverse accumulation and parameter sharing}358\label{sec:reverse}359 360A parameterized layer has the form \(F:P\times X\to Y\). An independent composition with \(G:Q\times Y\to Z\) has parameter space \(Q\times P\) and evaluates to \(G(q,F(p,x))\). Associativity follows from associativity of function composition and the canonical reassociation of products. This is the usual parameterized-map construction appearing in categorical learning~\cite{fong2019,cruttwell2022,gavranovic2024}. The tangent module supplies the one-input linear pieces of the derivative of the interpretation.361 362\subsection{Finite computation graphs}363 364Fix a finite acyclic graph. Each noninput node \(w\) has an ordered list of predecessor slots \((v(w,1),\dots,v(w,r_w))\) and a local smooth operation \(F_w\). A predecessor can occur in several slots. Write \(z_w\) for the evaluated state and365\[366 L_{w,i}=D_iF_w(z_{v(w,1)},\dots,z_{v(w,r_w)}).367\]368The output is one node \(o\), with a scalar loss \(\ell\) of \(z_o\). Tuple-valued outputs can be made into one node by a product. If \(h_v\) denotes a tangent perturbation at node \(v\), then369\[370 h_w=\sum_{i=1}^{r_w}L_{w,i}h_{v(w,i)} ,371\]372by splitting the tangent input of \(F_w\) into its slots. Each \(L_{w,i}\) appears in the action of Theorem~\ref{thm:tangent-module}. For a linear map \(L:U\to V\), write \(L^\vee:V^*\to U^*\) for precomposition with \(L\).373 374\begin{theorem}[Reverse accumulation for a graph]375\label{thm:reverse}376Initialize the output covector with \(D\ell(z_o)\) and all other covectors with zero. Process each noninput node \(w\) in reverse topological order. For every slot \(i\), add \(L_{w,i}^\vee\lambda_w\) to its predecessor's covector. At the input nodes the final covectors are exactly the input partial differentials of the composite loss.377\end{theorem}378 379\begin{proof}380Start with the linear pairing \(\langle D\ell(z_o),h_o\rangle\). Whenever a noninput variable \(h_w\) is eliminated, use its forward tangent equation to write381\[382 \langle\lambda_w,h_w\rangle383   =\sum_i \langle L_{w,i}^{\vee}\lambda_w,h_{v(w,i)}\rangle .384\]385Processing in reverse order puts all downstream contributions at \(w\) before it is eliminated. If an input occurs repeatedly, the identical \(h_v\) appears with a sum of covectors. At the end the original differential has been written as a pairing with all input variations independently. Its coefficients are the desired partial differentials.386\end{proof}387 388No inner product is required for the reverse sweep. Choosing an inner product identifies each covector with a gradient. Under Euclidean coordinates \(L^\vee\) is represented by the transpose. This is reverse-mode automatic differentiation~\cite{baydin2018}, which also underlies the categorical formulations in~\cite{fong2019,cruttwell2022}. Here its linear pieces are obtained as operators in a module over an explicit linearized operad.389 390The cotangents of this calculation are local to the evaluated fibers.391The algebraic dual of \(M_c\) is \(\prod_{x\in X_c}T_x^*X_c\).392A transpose on the whole dual need not preserve finite support.393For example, under the unary map \(x\mapsto\sin x\), a covector394supported at the output \(0\) acquires an entry at every \(n\pi\)395when pulled back. Each such entry is multiplied by396\(\cos(n\pi)=(-1)^n\). A reverse pass on a fixed graph uses only397the fibers specified by its forward evaluation.398 399\subsection{Tying parameters along a diagonal}400 401Let \(\Phi:P_1\times\cdots\times P_r\times X\to Y\) be a model with independent parameter slots. A parameterization \(\tau:Q\to\prod_i P_i\) gives the tied model \(\Phi(\tau(q),x)\). At fixed \(x\) put \(L(p)=\ell(\Phi(p,x))\). The tied differential is402\[403 D(L\circ\tau)(q)=(D\tau(q))^\vee\, DL(\tau(q)).404\]405If all \(P_i=P\) and \(\tau(q)=(q,\ldots,q)\), it follows that406\[407 D(L\circ\tau)(q)=\sum_{i=1}^r D_i L(q,\ldots,q).408\]409The summands are covectors on \(P\). The sum arises from evaluating the module on the smooth diagonal \(P\to P^r\), viewed as a unary operation whose output color is a product. Its tangent is \(v\mapsto(v,\ldots,v)\), so dualizing produces addition. It would give a different result to treat repeated mentions as newly independent parameters.410 411For equipped parameter spaces, the Euclidean gradient used by an optimizer depends on the metric chosen on \(Q\). In particular, taking the pullback of the product metric to the diagonal rescales the repeated block by \(r\) and changes the gradient from a sum to an average. The parameter differential already determines the chain rule and is independent of this decision. Section~\ref{sec:derived} computes the same distinction for permutation orbits.412 413\subsection{Differentiating a symmetry}414 415Let \(\sigma:X\to X\) and \(\rho:Y\to Y\) be invertible smooth maps with \(F\circ\sigma=\rho\circ F\). The chain rule gives416\[417 DF(\sigma x)\,D\sigma(x)=D\rho(F(x))\,DF(x).418\]419For a linear action and an invariant \(F\), take \(\rho=\id\). Then \(DF(\sigma x)\sigma=DF(x)\). If the action on \(X\) is orthogonal and \(F\) is scalar, the corresponding gradient satisfies \(\nabla F(\sigma x)=\sigma\nabla F(x)\). This gives a concrete check of a permutation-invariant architecture and of its backward operation. The pooling example below exhibits the check without assuming a universality theorem for invariant networks.420