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 281–380 of 1174. Source text is displayed literally.

281\[282 A_c=\mathbb R[X_c],\qquad283 M_c=\bigoplus_{x\in X_c}T_xX_c .284\]285Here \([x]\) denotes a basis vector of \(A_c\) and \(\iota_x\) denotes the inclusion of a tangent fiber into \(M_c\). Both use finite support. These objects capture point and first-order data algebraically. In particular, the free vector space has no prescribed completion or topology.286 287\subsection{The one-marked-input action}288 289For an input tuple \(\boldsymbol x\), let \(D_i f_p(\boldsymbol x)\) be the derivative with only the \(i\)-th input varying. It maps \(T_{x_i} X_{c_i}\) to \(T_{f_p(\boldsymbol x)}X_d\).290 291\begin{theorem}[Tangent module over the linearization]292\label{thm:tangent-module}293The formulas294\begin{align}295 A(p)([x_1],\ldots,[x_n])&=[f_p(\boldsymbol x)],\label{eq:a-act}\\296 M_i(p)([x_1],\ldots,\iota_{x_i}v,\ldots,[x_n])297   &=\iota_{f_p(\boldsymbol x)}D_i f_p(\boldsymbol x)v\label{eq:m-act}298\end{align}299extend to an \(\mathcal O\)-algebra \(A\) and an operadic \(A\)-module \(M\). For one color the action is of the form in K\v{r}\'{\i}\v{z} and May, Part~I, Definition~4.1. The colored action satisfies the same one-marked-input axioms with matching input and output colors.300\end{theorem}301 302\begin{proof}303The first formula defines a multilinear map on the tensor of all input spaces since it specifies the values on pure basis tensors. In the second formula, fix all unmarked basis points. The map into \(M_d\) is linear on each \(T_{x_i}X_{c_i}\). The direct sum property extends it to \(M_{c_i}\), and multilinearity in the other basis inputs completes the definition. Finally extend linearly in \([p]\).304 305Operad substitution holds in \(A\) because the interpretation respects substitution. For the module equation take a marked input \(j\) of \(q_i\), and put \(y_a=f_{q_a}(\boldsymbol x_a)\). The partial chain rule gives306\begin{equation}307 \begin{split}308 D_{(i,j)} f_{p(q_1,\ldots,q_n)}(\boldsymbol x)309  &=D_i f_p(\boldsymbol y)\,D_j f_{q_i}(\boldsymbol x_i).310 \end{split}311 \label{eq:partial-chain}312\end{equation}313All unmarked blocks use \(A\), so they supply the basis elements \([y_a]\). The inner marked action produces a vector in \(T_{y_i}X_{c_i}\), and the outer marked action applies the first factor in \eqref{eq:partial-chain}. This agrees with evaluating the marked slot of the substituted operation. Units and permutations respect the same formulas, since the derivative of the identity is the identity and permutation reindexes the summands. The equations extend from the generating tensors to all inputs by multilinearity.314\end{proof}315 316Equation~\eqref{eq:partial-chain} means that the derivative in a single input of a tree of operations composes along its path to the output. The unmarked branches compute the base points for the derivative along that path. In the one-color case these compositions act through the enveloping algebra \(U_{\mathcal O}(A)\) of K\v{r}\'{\i}\v{z} and May. In the colored case each one-marked map has a specified source and target color, and the relations equate two composites only when their colors match.317 318\begin{proposition}[The affine relations in a tangent fiber]319\label{prop:affine-quotient}320The smooth tangent operations on the spaces \(TX_c\) give an \(\mathcal O\)-algebra on \(\mathbb R[TX]\). There is a canonical surjective algebra map321\[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 write