Indexed text attachment
operads-modules-machine-learning.tex
Source for Operads, Modules, and Differentiation in Machine Learning
View paper · Download original file
Lines 661–760 of 1174. Source text is displayed literally.
661\(G\) acts on \(S\). Examples include relabeling interchangeable662branches and applying automorphisms of a fixed graph to its node slots.663Write \(G_s\) for the stabilizer of \(s\) and \(S/G\) for the set664of orbits. This symmetry gives two constructions on the same665representation. Tying restricts parameters to an invariant subspace.666Orbit pooling identifies slots by taking coinvariants. Their667relationship depends on the coefficient field and, for gradients,668on the metric chosen on the tied parameters.669 670\subsection{Balancing and averaging}671 672Let \(k\) be a field, \(A=k[G]\), and let \(M\) be a left673\(A\)-module. Regard \(A\) as a differential graded algebra674concentrated in degree zero, with augmentation675\(\epsilon(\sum_g a_g g)=\sum_g a_g\).676Use this augmentation for the right \(A\)-action on \(k\). Then677\[678 k\otimes_A M \cong M_G679 := M/\langle gm-m:g\in G,\ m\in M\rangle_k .680\]681Indeed the balancing relation identifies \(1\otimes gm\) with682\(1\otimes m\), and the inverse sends \(1\otimes m\) to the class of683\(m\). The fixed subspace \(M^G\) consists of those \(m\) satisfying684\(gm=m\) for every \(g\). For \(M=k[S]\otimes_k V\) with \(V\) a685trivial \(G\)-module, the fixed subspace consists of \(V\)-valued686vectors constant on each orbit. The quotient map to687\(k[S/G]\otimes_k V\) sums coordinates over each orbit. On a688constant vector \(v\) on an orbit \(O\) this quotient takes value689\(|O|v\).690 691\begin{proposition}[Averaging]692\label{prop:derived-averaging}693If \(|G|\) is invertible in \(k\), the composite694\(M^G\hookrightarrow M\twoheadrightarrow M_G\) is a natural695isomorphism. Its inverse sends \([m]\) to \(em\), where696\(e=|G|^{-1}\sum_{g\in G}g\).697For every \(M\), \(\operatorname{Tor}^{A}_q(k,M)=0\) for \(q>0\).698\end{proposition}699 700\begin{proof}701Both \(ge=e\) and \(eg=e\) hold by reindexing the sum. Also702\(e^2=e\) and \(e\) acts as the identity on fixed vectors.703Hence \(m\mapsto em\) factors over \(M_G\) and takes values in704\(M^G\). In \(M_G\), each \([gm]\) is \([m]\), so705\([em]=[m]\). This proves the isomorphism. The right ideal \(eA\)706is a summand of the free right module \(A\), via left multiplication707by \(e\). The map \(k\to eA\) sending \(1\) to \(e\) is an708isomorphism of right modules since \(ea=\epsilon(a)e\) and709\(\epsilon(e)=1\). The right module \(k\) is therefore projective.710\end{proof}711 712\subsection{The metric on shared parameters}713 714Over \(k=\mathbb R\), let \(V\) be a finite-dimensional Euclidean715space and \(P=V^S\) with the product inner product. The permutation716representation acts by isometries. Put \(U=V^{S/G}\). The tying717map \(i:U\to P\) sends \(\theta\) to the vector with718\(i(\theta)_s=\theta_{[s]}\), where \([s]\) denotes the orbit of719\(s\). Its image is \(P^G\). For a differentiable loss \(L:P\to720\mathbb R\), write \(g_s\) for the \(s\)-component of721\(\nabla L(i\theta)\). The tied derivative is the pullback722\(i^* DL(i\theta)\). On \(v\in U\) it is723\[724 D(L\circ i)(\theta)[v]725 =\sum_{O\in S/G}726 \left\langle\sum_{s\in O}g_s,v_O\right\rangle .727\]728With the ordinary product metric on \(U\), the \(O\)-component729of the gradient is \(\sum_{s\in O}g_s\). The metric induced by730\(i\) has inner product731\[732 \langle u,v\rangle_i733 =\sum_O |O|\langle u_O,v_O\rangle.734\]735In the induced metric, the component for \(O\) becomes736the average of the \(g_s\) over \(O\). Let \(R_G\) be the737Reynolds operator \(m\mapsto em\) on \(P\). Then738\[739 i\nabla_i(L\circ i)(\theta)=R_G\nabla L(i\theta).740\]741Indeed for \(s\in O\) every index \(t\in O\) occurs as \(g^{-1}s\)742for exactly \(|G_s|\) group elements, so \(R_G\) averages743uniformly over \(O\). This is also the orthogonal projection744onto \(P^G\): the operator is idempotent, and reindexing by745\(g^{-1}\) gives self-adjointness.746 747For example, let \(C_2\) swap \(a,b\) and fix \(c\), and take748\(V=\mathbb R\). The map \(i\) sends \((\theta,\eta)\) to749\((\theta,\theta,\eta)\). For \(y=(1,3,2)\) and750\(L(p)=\tfrac12\sum_{s\in S}(p_s-y_s)^2\), the product-metric751gradient in \(U\) is \((2\theta-4,\eta-2)\), while the induced752metric gives \((\theta-2,\eta-2)\). At the origin the first753shared coordinate receives two contributions to the derivative,754and the induced metric divides that sum by the orbit size.755This difference matters when a single learning rate is used756across orbits of unequal sizes.757 758When the ambient loss is invariant, its ambient gradient at a759tied point is itself fixed. Differentiating \(L\circ g=L\)760at \(p\in P^G\) gives \(DL(p)[g v]=DL(p)[v]\). Since \(g\)