The Geometry of the Set of Equivalent Linear Neural Networks

Jonathan Richard Shewchuk; Sagnik Bhattacharya

Figure 1: The fiber

\mu^{-1}([1])

for the network

W_{3}W_{2}W_{1}=[\theta_{3}][\theta_{2}][\theta_{1}]=[1]=W

.

Figure 2: At left is the fiber

\mu^{-1}([0~~~0])

for the network

W_{2}W_{1}=[\theta_{2}][\theta_{1}~~~\theta^{\prime}_{1}]=[0~~~0]=W

, partitioned into three strata:

S_{00}

is the origin;

S_{10}

(blue) is the

\theta_{2}

-axis with the origin removed; and

S_{01}

(pink) is the plane spanned by the

\theta_{1}

- and

\theta^{\prime}_{1}

-axes with the origin removed. At right, the strata are arranged in a stratum dag , organized as a table indexed by the ranks of

W_{1}

and

W_{2}

. Each dag vertex specifies the dimension of the stratum (dim), the number of degrees of freedom of motion on the fiber (dof), and the number of rank-increasing degrees of freedom (rdof), which stay on the fiber but move off the stratum and onto a higher-dimensional stratum. Always, dof

=

dim

+

rdof. A directed path from one stratum to another implies that the former is a subset of the closure of the latter.

Figure 3: Schematic of a linear neural network with four edge layers (

L=4

).

A_{kji}=\mathrm{null}\,W_{k+1\blacktriangleleft j}\cap\mathrm{col}\,W_{j\blacktriangleleft i}

flow subspace of

\mathbb{R}^{d_{j}}

for unit layer

j

(note:

A_{j-1,j,i}=\{{\bf 0}\}=A_{k,j,-1}

)

a_{kji}\in A_{kji}\downarrow(A_{k,j,i-1}+A_{k-1,j,i})

prebasis subspace of

\mathbb{R}^{d_{j}}

for unit layer

j

\mathcal{A}_{kji}=\{a_{k^{\prime}ji^{\prime}}\neq\{{\bf 0}\}:k^{\prime}\in[j,k],i^{\prime}\in[0,i]\}

prebasis for

A_{kji}

(set of prebasis subspaces spanning

A_{kji}

)

\mathcal{A}_{j}=\mathcal{A}_{Ljj}

prebasis for

\mathbb{R}^{d_{j}}

for unit layer

j

(set of prebasis subspaces spanning

\mathbb{R}^{d_{j}}

)

B_{kji}=\mathrm{row}\,W_{k\blacktriangleleft j}\cap\mathrm{null}\,W_{j\blacktriangleleft i-1}^{\top}

flow subspace of

\mathbb{R}^{d_{j}}

for transpose network (

B_{L+1,j,i}=\{{\bf 0}\}=B_{k,j,j+1}

)

b_{kji}\in B_{kji}\downarrow(B_{k,j,i+1}+B_{k+1,j,i})

prebasis subspace of

\mathbb{R}^{d_{j}}

for unit layer

j

of the transpose network

\mathcal{B}_{kji}=\{b_{k^{\prime}ji^{\prime}}\neq\{{\bf 0}\}:k^{\prime}\in[k,L],i^{\prime}\in[i,j]\}

prebasis for

B_{kji}

(set of prebasis subspaces spanning

B_{kji}

)

Table 1: Notation used in this paper. Continued in Tables 2 and 3 . See also Table 6 .

\alpha_{kji}=\dim A_{kji}=\mathrm{rk}\,W_{j\blacktriangleleft i}-\mathrm{rk}\,W_{k+1\blacktriangleleft i}=\sum_{t=j}^{k}\sum_{s=0}^{i}\omega_{ts}

dimension of flow subspace

A_{kji}

\beta_{kji}=\dim B_{kji}=\mathrm{rk}\,W_{k\blacktriangleleft j}-\mathrm{rk}\,W_{k\blacktriangleleft i-1}=\sum_{t=k}^{L}\sum_{s=i}^{j}\omega_{ts}

dimension of flow subspace

B_{kji}

\eta(M_{L},M_{L-1},\ldots,M_{1})=(J_{L}M_{L}J_{L-1}^{-1},J_{L-1}M_{L-1}J_{L-2}^{-1},\ldots,J_{1}M_{1}J_{0}^{-1})

a linear transformation of

\mathbb{R}^{d_{\theta}}

\theta=(W_{L},W_{L-1},\ldots,W_{1})\in\mathbb{R}^{d_{\theta}}

weight vector representing a neural network

\Delta\theta=(\Delta W_{L},\Delta W_{L-1},\ldots,\Delta W_{1})\in\mathbb{R}^{d_{\theta}}

displacement applied to a weight vector

\theta

\theta^{\prime}=\theta+\Delta\theta=(W^{\prime}_{L},W^{\prime}_{L-1},\ldots,W^{\prime}_{1})

weight vector after a move from

\theta

to

\theta^{\prime}

\tilde{\theta}=(\tilde{I}_{L},\tilde{I}_{L-1},\ldots,\tilde{I}_{1})

the canonical weight vector (for some specified rank list

\underline{r}

)

Table 2: More notation used in this paper. Continued in Table 3 . See also Table 6 .

\underline{r}\leq\underline{z}

r_{k\blacktriangleleft i}\leq z_{k\blacktriangleleft i}

for all

L\geq k\geq i\geq 0

\underline{r}<\underline{z}

\underline{r}\leq\underline{z}

and

\underline{r}\neq\underline{z}

(at least one of the inequalities holds strictly)

\bar{S}

closure of set

S\subseteq\mathbb{R}^{d_{\theta}}

with respect to weight space

\mathbb{R}^{d_{\theta}}

Q^{\perp}

orthogonal complement of subspace

Q

(subspace of all vectors orthogonal to all vectors in

Q

)

MP=\{Mv:v\in P\}

product of a matrix

M

and a subspace

P

Z=P\oplus Q

direct sum decomposition:

Z=P+Q

(vector sum of subspaces) and

P\cap Q=\{{\bf 0}\}

Z=\bigoplus_{i=1}^{m}P_{i}

direct sum decomposition:

Z=\sum_{i=1}^{m}P_{i}

and for every

i\in[1,m]

,

P_{i}\cap\sum_{j\neq i}P_{j}=\{{\bf 0}\}

Table 3: Still more notation used in this paper. See also Table 6 .

Figure 4: At left is the variety of solutions to

W_{3}W_{2}W_{1}=[\theta_{3}][\theta_{2}][\theta_{1}]=[0]=W

, partitioned into seven strata:

S_{000}

is the origin;

S_{001}

,

S_{010}

, and

S_{100}

are the three coordinate axes with the origin removed; and

S_{011}

,

S_{101}

, and

S_{110}

are the three coordinate planes with the coordinate axes removed. At right is the stratum dag, organized as a three-dimensional table indexed by the ranks of

W_{3}

,

W_{2}

, and

W_{1}

.

\displaystyle\dim S

\displaystyle=

\displaystyle d_{\theta}-\mathrm{rk}\,W\cdot(d_{L}+d_{0}-\mathrm{rk}\,W)-

\displaystyle\sum_{L\geq k+1\geq i>0}\hskip-7.22743pt(\mathrm{rk}\,W_{k+1\blacktriangleleft i}-\mathrm{rk}\,W_{k+1\blacktriangleleft i-1})\,(\mathrm{rk}\,W_{k\blacktriangleleft i-1}-\mathrm{rk}\,W_{k+1\blacktriangleleft i-1}).

\displaystyle T_{\theta}S

\displaystyle=

\displaystyle\left\{(\Delta W_{L}+W_{L}H_{L-1},\Delta W_{L-1}+W_{L-1}H_{L-2}-H_{L-1}W_{L-1},\ldots,\rule{0.0pt}{10.0pt}\right.

\displaystyle\Delta W_{j}+W_{j}H_{j-1}-H_{j}W_{j},\ldots,\Delta W_{2}+W_{2}H_{1}-H_{2}W_{2},\Delta W_{1}-H_{1}W_{1}):

\displaystyle H_{j}\in\mathbb{R}^{d_{j}\times d_{j}},

\displaystyle\Delta W_{j}\in\sum_{h=1}^{j-1}\mathrm{col}\,W_{j\blacktriangleleft h}\otimes\mathrm{null}\,W_{j-1\blacktriangleleft h-1}^{\top}+(\mathrm{null}\,W_{L\blacktriangleleft j}\cap\mathrm{col}\,W_{j\blacktriangleleft 0})\otimes\mathbb{R}^{d_{j-1}}+

\displaystyle\left.\sum_{l=j}^{L-1}\mathrm{null}\,W_{l+1\blacktriangleleft j}\otimes\mathrm{row}\,W_{l\blacktriangleleft j-1}+\mathbb{R}^{d_{j}}\otimes(\mathrm{row}\,W_{L\blacktriangleleft j-1}\cap\mathrm{null}\,W_{j-1\blacktriangleleft 0}^{\top})\right\}.

\displaystyle\dim T_{\theta}S

\displaystyle=

\displaystyle\dim S.

\displaystyle N_{\theta}S

\displaystyle=

\displaystyle\left\{(X^{(L0)}_{L},X^{(L0)}_{L-1},\ldots,X^{(L0)}_{1}):M^{(L0)}\in\mathbb{R}^{d_{L}\times d_{0}}\right\}+

\displaystyle\sum_{L\geq t>s\geq 0}\left\{(X^{(ts)}_{L},X^{(ts)}_{L-1},\ldots,X^{(ts)}_{1}):M^{(ts)}\in\mathrm{null}\,W_{t\blacktriangleleft s}^{\top}\otimes\mathrm{null}\,W_{t\blacktriangleleft s}\right\}\hskip 14.45377pt\mbox{where}

\displaystyle X^{(ts)}_{j}

\displaystyle=

\displaystyle\left\{\begin{array}[]{rl}W_{t\blacktriangleleft j}^{\top}M^{(ts)}W_{j-1\blacktriangleleft s}^{\top},&j\in[s+1,t],\\ 0,&j\not\in[s+1,t].\end{array}\right.

\displaystyle\dim N_{\theta}S

\displaystyle=

\displaystyle d_{\theta}-\dim S.

\displaystyle\mathrm{rk}\,\mathrm{d}\mu(\theta)

\displaystyle=

\displaystyle\sum_{j=1}^{L}\mathrm{rk}\,W_{L\blacktriangleleft j}\cdot\mathrm{rk}\,W_{j-1\blacktriangleleft 0}-\sum_{j=1}^{L-1}\mathrm{rk}\,W_{L\blacktriangleleft j}\cdot\mathrm{rk}\,W_{j\blacktriangleleft 0}.\hskip 14.45377pt\mbox{(Trager et al.~\cite[cite]{[\@@bibref{}{trager20}{}{}]}, Lemma~3.)}

\displaystyle\mathrm{null}\,\mathrm{d}\mu(\theta)

\displaystyle=

\displaystyle\left\{(\Delta W_{L}+W_{L}H_{L-1},\Delta W_{L-1}+W_{L-1}H_{L-2}-H_{L-1}W_{L-1},\ldots,\rule{0.0pt}{10.0pt}\right.

\displaystyle\Delta W_{j}+W_{j}H_{j-1}-H_{j}W_{j},\ldots,\Delta W_{2}+W_{2}H_{1}-H_{2}W_{2},\Delta W_{1}-H_{1}W_{1}):

\displaystyle\left.H_{j}\in\mathbb{R}^{d_{j}\times d_{j}},\Delta W_{j}\in\mathrm{null}\,W_{L\blacktriangleleft j}\otimes\mathbb{R}^{d_{j-1}}+\mathbb{R}^{d_{j}}\otimes\mathrm{null}\,W_{j-1\blacktriangleleft 0}^{\top}\right\}.

\displaystyle\dim\mathrm{null}\,\mathrm{d}\mu(\theta)

\displaystyle=

\displaystyle d_{\theta}-\mathrm{rk}\,\mathrm{d}\mu(\theta).

\displaystyle\mathrm{row}\,\mathrm{d}\mu(\theta)

\displaystyle=

\displaystyle\{(X_{L},X_{L-1},\ldots,X_{1}):M\in\mathbb{R}^{d_{L}\times d_{0}}\}\hskip 14.45377pt\mbox{where~}

\displaystyle X_{j}

\displaystyle=

\displaystyle W_{L\blacktriangleleft j}^{\top}MW_{j-1\blacktriangleleft 0}^{\top}.

\displaystyle\dim\mathrm{row}\,\mathrm{d}\mu(\theta)

\displaystyle=

\displaystyle\mathrm{rk}\,\mathrm{d}\mu(\theta).

Notes:

\displaystyle N_{\theta}S=(T_{\theta}S)^{\perp};\mathrm{row}\,\mathrm{d}\mu(\theta)=(\mathrm{null}\,\mathrm{d}\mu(\theta))^{\perp};

\displaystyle T_{\theta}S\subseteq\mathrm{null}\,\mathrm{d}\mu(\theta);N_{\theta}S\supseteq\mathrm{row}\,\mathrm{d}\mu(\theta).

Table 4: Some of this paper’s main results about subspaces of the weight space

\mathbb{R}^{d_{\theta}}

and their dimensions.

S

is the stratum of the fiber

\mu^{-1}(W)

containing the point

\theta=(W_{L},W_{L-1},\ldots,W_{1})

,

T_{\theta}S

is the tangent space of

S

at

\theta

(

T_{\theta}S

passes through the origin, not through

\theta

),

N_{\theta}S

is the normal space of

S

at

\theta

(the orthogonal complement of

T_{\theta}S

), and

\mathrm{d}\mu(\theta)

is the (linear) differential map of the matrix multiplication map

\mu

at

\theta

, defined in Section 8 . In our illustrations of stratum dags, “dim” refers to

\dim S

and “dof” refers to

\dim\mathrm{null}\,\mathrm{d}\mu(\theta)

.

$\mathrm{rk}\,W_{2}=5$	dim: 31	dof: 34	$\rightarrow$	dim: 34	dof: 34
$\mathrm{rk}\,W_{2}=5$	$S_{51}$	rdof: 3	$\rightarrow$	$S_{52}$	rdof: 0
	$\uparrow$			$\uparrow$
$\mathrm{rk}\,W_{2}=4$	dim: 29	dof: 37	$\rightarrow$	dim: 33	dof: 36	$\rightarrow$	dim: 35	dof: 35
$\mathrm{rk}\,W_{2}=4$	$S_{41}$	rdof: 8	$\rightarrow$	$S_{42}$	rdof: 3	$\rightarrow$	$S_{43}$	rdof: 0
	$\uparrow$			$\uparrow$			$\uparrow$
$\mathrm{rk}\,W_{2}=3$	dim: 25	dof: 40	$\rightarrow$	dim: 30	dof: 38	$\rightarrow$	dim: 33	dof: 36	$\rightarrow$	dim: 34	dof: 34

Figure 5: Stratum dag representing the stratification of

\mu^{-1}(W)

for

W=W_{2}W_{1}

,

W_{2}\in\mathbb{R}^{5\times 6}

,

W_{1}\in\mathbb{R}^{6\times 4}

, and

\mathrm{rk}\,W=1

. For every pair of strata

S_{ts}

and

S_{t^{\prime}s^{\prime}}

with

t\leq t^{\prime}

and

s\leq s^{\prime}

,

S_{ts}\subseteq\bar{S}_{t^{\prime}s^{\prime}}

.

Figure 6: The top half is an annotated barcode that illustrates the flow of the “fundamental” subspaces

a_{kji}

through the network. Double boxes represent subspaces of dimension 2 and triple boxes represent subspaces of dimension 3. The bottom half relates the interval counts, the layer sizes, and the subsequence matrix ranks. The number of units

d_{j}

in unit layer

j

is the sum of the counts

\omega_{ts}

of the intervals that touch layer

j

(i.e., the dimensions of the subspaces

a_{tjs}

). Each matrix rank

\mathrm{rk}\,W_{k\blacktriangleleft i}

is the sum of the counts of the intervals that touch both layers

k

and

i

.

$\mathbb{R}^{d_{2}}$	$k=4$	$A_{4,2,-1}=\{{\bf 0}\}$	$\subseteq$	$A_{420}$	$\subseteq$	$A_{421}$	$\subseteq$	$A_{422}=\mathbb{R}^{d_{2}}$
$\subseteq$				$\subseteq$		$\subseteq$		$\subseteq$
$\mathrm{null}\,W_{4}W_{3}$	$k=3$	$A_{3,2,-1}=\{{\bf 0}\}$	$\subseteq$	$A_{320}$	$\subseteq$	$A_{321}$	$\subseteq$	$A_{322}$
$\subseteq$				$\subseteq$		$\subseteq$		$\subseteq$
$\mathrm{null}\,W_{3}$	$k=2$	$A_{2,2,-1}=\{{\bf 0}\}$	$\subseteq$	$A_{220}$	$\subseteq$	$A_{221}$	$\subseteq$	$A_{222}$
$\subseteq$				$\subseteq$		$\subseteq$		$\subseteq$
$\{{\bf 0}\}$	$k=1$	$A_{1,2,-1}=\{{\bf 0}\}$		$A_{120}=\{{\bf 0}\}$		$A_{121}=\{{\bf 0}\}$		$A_{122}=\{{\bf 0}\}$

Table 5: The hierarchical nesting of the flow subspaces at unit layer

j=2

of a network with

L=4

matrices. Top:

A_{k2i}=\mathrm{null}\,W_{k+1\blacktriangleleft 2}\cap\mathrm{col}\,W_{2\blacktriangleleft i}

for each

k,i

. Bottom:

B_{k2i}=\mathrm{row}\,W_{k\blacktriangleleft 2}\cap\mathrm{null}\,W_{2\blacktriangleleft i-1}

for each

k,i

.

Figure 7: Top: an example of flow subspaces

A_{kji}

. Observe that

A_{000}

is annihilated in the nullspace of

W_{1}

, whereas

A_{300}

is not entirely annihilated until it reaches the nullspace of

W_{4}

. Observe that

A_{311}

and

A_{410}

meet at an oblique angle; flow subspaces do not always meet orthogonally. Note that the subspace

A_{322}

is five-dimensional, so we cannot draw it complete. Instead, we draw a three-dimensional subspace of

A_{322}

labeled

A_{322}\downarrow A_{321}

such that

A_{322}

is the vector sum of the plane

A_{321}

and the space labeled

A_{322}\downarrow A_{321}

. Similarly,

A_{222}

is a three-dimensional subspace, but we draw a two-dimensional subspace of

A_{222}

labeled

A_{222}\downarrow A_{221}

such that

A_{222}

is the vector sum of the line

A_{221}

and the plane labeled

A_{222}\downarrow A_{221}

. Bottom: an example of corresponding prebasis subspaces

a_{kji}

, forming flow prebases. The prebasis subspaces for layer

j

span

\mathbb{R}^{d_{j}}

. The subspaces

a_{211}

,

a_{410}

, and

a_{310}

cannot all be pairwise orthogonal because

A_{311}

and

A_{410}

are not orthogonal.

Figure 8: At left, we reprise the annotated barcode from Figure 6 . At right, we tabulate the values of the interval counts

\omega_{ts}

with boxes that illustrate how the four summations compute

d_{1}

,

\alpha_{322}

,

\beta_{321}

, and

\mathrm{rk}\,W_{3\blacktriangleleft 1}=\mathrm{rk}\,W_{3}W_{2}

. At the bottom of the figure, we reprise the four summations for reference.

Figure 9: The canonical weight vector

\tilde{\theta}=(\tilde{I}_{4},\tilde{I}_{3},\tilde{I}_{2},\tilde{I}_{1})

and its subsequence matrices when every interval count is

\omega_{ki}=1

except

\omega_{20}=2

. Each row of

\tilde{I}_{j}

is associated with some interval

[i,l]

that contains

j

, marked in shorthand with indices

li

, and each column of

\tilde{I}_{j}

is associated with some interval

[h,k]

that contains

j-1

, marked in shorthand with indices

kh

. Blocks where the row indices match the column indices are identity matrices; all other component are zeros. Every rank-

1

matrix

W\in\mathbb{R}^{5\times 6}

can be factored as

W=J_{4}\tilde{I}_{4}\tilde{I}_{3}\tilde{I}_{2}\tilde{I}_{1}J_{0}^{-1}

where the matrices

\tilde{I}_{j}

have the values depicted (determined solely by the barcode) but

J_{4}

and

J_{0}

depend on

W

and are invertible. This gives us a weight vector

(J_{4}\tilde{I}_{4},\tilde{I}_{3},\tilde{I}_{2},\tilde{I}_{1}J_{0}^{-1})

that lies on the fiber

\mu^{-1}(W)

and has the same rank list as

\tilde{\theta}

.

Figure 10: The influence of a basic move in which a factor matrix

W_{j}

undergoes a nonzero displacement

\Delta W_{j}\in o_{lkjih}

. The effects on the subsequence matrix

W_{t\blacktriangleleft s}

are listed for every

t

and

s

with

L\geq t\geq s\geq 0

. These tables are triangular, though it’s not obvious at first: the hatched regions represent unused zones where

t<s

. A yellow rectangle indicates which subsequence matrices increase in rank, constituting a barcode move if no rank decreases. The black font indicates where

W^{\prime}_{t\blacktriangleleft s}\neq W_{t\blacktriangleleft s}

. The red font indicates where

W^{\prime}_{t\blacktriangleleft s}=W_{t\blacktriangleleft s}

because the matrix

W_{j}

is not a factor in

W_{t\blacktriangleleft s}

. The blue font indicates where

W^{\prime}_{t\blacktriangleleft s}=W_{t\blacktriangleleft s}

by properties of the flow relationships. (a) Table for the case where

L>l>k\geq j>i>h>0

. An example of a swapping move (if no rank decreases). (b) The third row disappears if

k+1=j

, and the third column disappears if

i=j

. When

k+1=j=i

, the move is a connecting move. (c) The second row disappears if

k\geq l

, and the second column disappears if

i\leq h

. If either inequality holds, no subsequence matrix rank increases; the move is not a barcode move. The first column disappears if

h=0

. (The first row disappears if

l=L

, though we don’t depict that case here. If

h=0

and

l=L

, then

W^{\prime}\neq W

and we move off the fiber.)

Figure 11: Two examples of connecting moves. The top example is the simplest example possible:

W_{1}

has been perturbed to increase its rank from zero to one. In the bottom example,

W_{2}

has been perturbed. In both examples, the perturbation of

W_{j}

replaces two intervals

[h,j-1]

and

[j,l]

with a single interval

[h,l]

. Three interval counts change, at three of the four corners of the red rectangle:

\omega_{lj}

and

\omega_{j-1,h}

decrease by one, and

\omega_{lh}

increases by one. The ranks of the subsequence matrices

W_{t\blacktriangleleft s}

increase by one for all

t\in[j,l]

and

s\in[h,j-1]

(the ranks inside the red rectangle, including

\mathrm{rk}\,W_{j}

). Outside the red rectangle, all interval counts and matrix ranks are unchanged.

Figure 12: Two examples of swapping moves. In the top example—the simplest example possible—either

W_{1}

or

W_{2}

may be perturbed to cause the move. In the bottom example, any of

W_{2}

,

W_{3}

, or

W_{4}

may be perturbed. The intervals

[h,k]

and

[i,l]

are replaced by an interval

[h,l]

, longer than both original intervals, and an interval

[i,k]

, shorter than both. Four interval counts change, at the four corners of the red rectangle:

\omega_{kh}

and

\omega_{li}

decrease, and

\omega_{lh}

and

\omega_{ki}

increase. The ranks of the subsequence matrices

W_{t\blacktriangleleft s}

increase for all

t\in[k+1,l]

and

s\in[h,i-1]

(the ranks inside the red rectangle). Outside the red rectangle, all interval counts and matrix ranks are unchanged.

Figure 13: Annotated barcodes for four strata in a stratum dag. (Assume that

W_{4}=0

, although

W_{4}

is not illustrated, so all four strata are on the fiber of

W=0

.) Green arrows are edges of the dag; in this example they all representing swapping moves. This dag includes the directed edge

(S_{\underline{r}},S_{\underline{z}})

, even though there are directed paths from

S_{\underline{r}}

to

S_{\underline{z}}

passing through

S_{\underline{u}}

or

S_{\underline{v}}

. Hence the dag is not a Hasse diagram. The edge

(S_{\underline{r}},S_{\underline{z}})

represents swapping moves whose displacements come from the subspaces

\phi_{31210}

or

\phi_{31110}

.

Figure 14: One-matrix subspaces for the canonical weight vector

\tilde{\theta}=(\tilde{I}_{4},\tilde{I}_{3},\tilde{I}_{2},\tilde{I}_{1})

when every

\omega_{ki}=1

except

\omega_{20}=2

. Yellow and green backgrounds indicate basic moves that stay on the fiber (moves with displacements from subspaces in

\Theta_{\mathrm{O}}^{\mathrm{fiber}}

such as

\phi_{22100}

and

\phi_{32330}

), whereas pink and blue backgrounds indicate basic moves off the fiber (moves from subspaces in

\Theta_{\mathrm{O}}^{\mathrm{off}}

such as

\phi_{44420}

and

\phi_{43220}

, satisfying

l=4

and

h=0

). Green and blue backgrounds indicate discrete moves that increase the rank of some subsequence matrix (moves from subspaces in

\Theta_{\mathrm{O}}^{\mathrm{barc}}

such as

\phi_{32330}

and

\phi_{43220}

, satisfying

l>k

and

i>h

), whereas yellow and pink backgrounds indicate moves that do not increase any rank. Hence, yellow indicates moves that stay on the closure of the stratum (moves from subspaces in

\Theta_{\mathrm{O}}^{\mathrm{strat}}

such as

\phi_{22100}

). Green indicates discrete moves to a different stratum that stay on the fiber (moves from subspaces in

\Theta_{\mathrm{O}}^{\mathrm{fiber}}\cap\Theta_{\mathrm{O}}^{\mathrm{barc}}

such as

\phi_{32330}

); these induce edges in the stratum dag. Pink indicates moves off the fiber in which no subsequence matrix’s rank increases. Blue indicates discrete moves off the fiber.

Figure 16: Four examples of reverse barcode moves found by the algorithm FindLastMove (shown prior to performing the reverse move). In each example, the algorithm finds a red rectangle such that its bottom corner lies at a bottommost positive

\Delta\omega_{lh}

, its top corner lies at a positive

\Delta\omega_{ki}

or between two

\Delta d

’s, and every

\Delta r

inside the rectangle is positive. In (b) and (c) the algorithm finds a reverse connecting move (

k=i-1

), whereas in (a) and (d) it finds a reverse swapping move (

k\geq i

), with (d) being a move that changes

W

’s rank. In (a) and (b), Line 10 of FindLastMove determines the top corner of the rectangle (hence

k=l-1

), whereas in (c) and (d), Lines 12 and 13 do (hence

k\leq l-2

).

Figure 17: Fiber prebases at five points on the fibers from Figures 4 and 2 . Note that we have drawn each prebasis translated to the point where it is defined (to clarify how the subspaces are related to the strata), but all the subspaces actually pass through the origin, and not necessarily through the points

\theta

,

\theta^{\prime}

, etc.

Figure 18: Two-matrix subspaces in

\Theta_{\mathrm{T}}^{\mathrm{off}}\cup\Theta_{\mathrm{T}}^{\mathrm{barc}}

at the canonical weight vector

\tilde{\theta}=(\tilde{I}_{4},\tilde{I}_{3},\tilde{I}_{2},\tilde{I}_{1})

when every

\omega_{ki}=1

except

\omega_{20}=2

. Each two-matrix subspace

\tau_{lkjih}\in\Theta_{\mathrm{T}}

has nonzero components in two blocks within two consecutive factor matrices. Pink backgrounds indicate subspaces in

\Theta_{\mathrm{T}}^{\mathrm{off}}

; green backgrounds indicate subspaces in

\Theta_{\mathrm{T}}^{\mathrm{barc}}

; and blue backgrounds indicate subspaces in both

\Theta_{\mathrm{T}}^{\mathrm{off}}

and

\Theta_{\mathrm{T}}^{\mathrm{barc}}

. Subspaces in

\Theta_{\mathrm{T}}^{\mathrm{off}}\cup\Theta_{\mathrm{T}}^{\mathrm{barc}}

(all three colors) represent directions along which the stratum is curved. Compare with Figure 14 , which illustrates the one-matrix subspaces at

\tilde{\theta}

.

Figure 19: Visualizing prebases at the canonical weight vector

\tilde{\theta}=(\tilde{I}_{4},\tilde{I}_{3},\tilde{I}_{2},\tilde{I}_{1})

when every

\omega_{ki}=1

except

\omega_{20}=2

. Top: visualizing the prebasis

\Theta^{\mathrm{strat}}

, the tangent space

T_{\theta}S=\mathrm{span}\,\Theta^{\mathrm{strat}}

, and its dimension

D^{\mathrm{strat}}

. Each component with a yellow background indicates a dimension in a one-matrix subspace in

\Theta^{\mathrm{strat}}

(such as

\phi_{44441}

); this component varies freely in

T_{\theta}S

. Other background colors indicate dimensions in two-matrix subspaces in

\Theta^{\mathrm{strat}}

(such as

\tau_{44320}

), dimensions that linearly link two components in weight space: pink for a direction that changes one component of

\tilde{I}_{4}

and one component of

\tilde{I}_{3}

; blue for

\tilde{I}_{3}

and

\tilde{I}_{2}

; and orange for

\tilde{I}_{2}

and

\tilde{I}_{1}

. You can see the dimension

D^{\mathrm{strat}}

of

T_{\theta}S

by counting dimensions of all four colors. Center: visualizing the prebasis

\Theta^{\mathrm{free}}

, the nullspace

\mathrm{null}\,\mathrm{d}\mu(\theta)=\mathrm{span}\,\Theta^{\mathrm{free}}

, and its dimension

D^{\mathrm{free}}

at

\tilde{\theta}

. Bottom: visualizing the prebasis

\Theta^{\mathrm{fiber}}

. Observe that for

\Theta^{\mathrm{fiber}}

only, some components participate in both a one-matrix subspace and a two-matrix subspace, such as

\phi_{43431}

and

\tau_{43331}

.

\Theta_{\mathrm{O}}=\{\phi_{lkjih}\neq\{{\bf 0}\}:L\geq l\geq j\geq i\geq 0

and

L\geq k\geq j-1\geq h\geq 0\}

\mbox{\hskip-26.73953pt}D_{\mathrm{O}}=d_{\theta}=\sum_{j=1}^{L}d_{j}d_{j-1}

(8.19)

\Theta_{\mathrm{O}}^{\mathrm{off}}=\{\phi_{Lkji0}\in\Theta_{\mathrm{O}}\}=\{\phi_{Lkji0}\neq\{{\bf 0}\}:L\geq j>0,L\geq k\geq j-1,

and

j\geq i\geq 0\}

\mbox{\hskip-26.73953pt}D_{\mathrm{O}}^{\mathrm{off}}=\sum_{j=1}^{L}\left(\sum_{i=0}^{j}\omega_{Li}\right)\left(\sum_{k=j-1}^{L}\omega_{k0}\right)=\sum_{j=1}^{L}\mathrm{rk}\,W_{L\blacktriangleleft j}\cdot\mathrm{rk}\,W_{j-1\blacktriangleleft 0}

(8.20)

\Theta_{\mathrm{O}}^{\mathrm{fiber}}=\Theta_{\mathrm{O}}\setminus\Theta_{\mathrm{O}}^{\mathrm{off}}=\{\phi_{lkjih}\in\Theta_{\mathrm{O}}:L>l

or

h>0\}

\mbox{\hskip-26.73953pt}D_{\mathrm{O}}^{\mathrm{fiber}}=D_{\mathrm{O}}-D_{\mathrm{O}}^{\mathrm{off}}=d_{\theta}-\sum_{j=1}^{L}\mathrm{rk}\,W_{L\blacktriangleleft j}\cdot\mathrm{rk}\,W_{j-1\blacktriangleleft 0}

(8.21)

\Theta_{\mathrm{O}}^{\mathrm{barc}}=\{\phi_{lkjih}\in\Theta_{\mathrm{O}}:l>k

and

i>h\}=\{\phi_{lkjih}\neq\{{\bf 0}\}:L\geq l\geq k+1\geq j\geq i>h\geq 0\}

Table 6: Sets of subspaces of

\mathbb{R}^{d_{\theta}}

and their total dimensions. See also Table 7 in Appendix E .

Figure 20: Top: visualizing the prebasis

\Psi^{\mathrm{strat}}

, the normal space

N_{\theta}S=\mathrm{span}\,\Psi^{\mathrm{strat}}

, and its dimension

d_{\theta}-D^{\mathrm{strat}}

at the canonical weight vector

\tilde{\theta}=(\tilde{I}_{4},\tilde{I}_{3},\tilde{I}_{2},\tilde{I}_{1})

when every

\omega_{ki}=1

except

\omega_{20}=2

. Each component with a pink background is a dimension that varies freely in

N_{\theta}S

; it also varies freely in some subspace in

\Psi^{\mathrm{strat}}

(such as

\psi_{4342}

). Blue backgrounds represent a dimension in which four components vary together, one in each of the four matrices (such as the single degree of freedom in

\psi_{4410}

). Gold and purple backgrounds represent dimensions that linearly link components in three of the four matrices. Turquoise, green, and tan backgrounds represent dimensions that linearly link components in two of the four matrices. You can see the dimension of

N_{\theta}S

by counting dimensions of all colors. Bottom: visualizing the prebasis

\Psi^{\mathrm{free}}

, the rowspace

\mathrm{row}\,\mathrm{d}\mu(\theta)=\mathrm{span}\,\Psi^{\mathrm{free}}

, and its dimension

\mathrm{rk}\,\mathrm{d}\mu(\theta)=d_{\theta}-D^{\mathrm{free}}

at

\tilde{\theta}

. Gradient descent algorithms for training neural networks choose a descent direction in

\mathrm{row}\,\mathrm{d}\mu(\theta)

.

Figure 21: Green arrows indicate the order in which our algorithm for enumerating valid rank lists assigns ranks to the subsequence matrices. The

d_{j}

’s and

\mathrm{rk}\,W

are fixed (black text); only the ranks in red can vary from stratum to stratum. The

\geq

and

\leq

symbols indicate some of the constraints that the ranks must satisfy. There are additional constraints: each interval count

\omega_{ki}=\mathrm{rk}\,W_{k\blacktriangleleft i}-\mathrm{rk}\,W_{k\blacktriangleleft i-1}-\mathrm{rk}\,W_{k+1\blacktriangleleft i}+\mathrm{rk}\,W_{k+1\blacktriangleleft i-1}

must be nonnegative (by the Frobenius rank inequality). For example,

\mathrm{rk}\,W_{2}\leq d_{1}-\mathrm{rk}\,W_{1}+\mathrm{rk}\,W_{2}W_{1}

.

Figure 24: A map showing the structure of

\mathrm{col}\,\mathrm{d}\mu(\theta)

,

\mathrm{null}\,\mathrm{d}\mu^{\top}(\theta)

,

T_{W}\mathrm{DV}_{\rho}

, and

N_{W}\mathrm{DV}_{\rho}

for a weight vector

\theta

, where

W=\mu(\theta)

and

\rho=\mathrm{rk}\,W

. Here we use the standard prebases

\mathcal{B}_{4}

and

\mathcal{A}_{0}

(see Appendix B ) so that the subspaces

a_{k00}

are mutually orthogonal and span

\mathbb{R}^{d_{0}}

, the subspaces

b_{44i}

are mutually orthogonal and span

\mathbb{R}^{d_{4}}

, and the subspaces

e_{ki}=b_{44i}\otimes a_{k00}

are mutually orthogonal and span

\mathbb{R}^{d_{4}\times d_{0}}

.

Figure 25: To the left of the barcode, we draw the matrix

G^{\top}

and draw green links in it to indicate which components

G_{ki}

are nonzero. In the top example, dashed purple edges show some of the ways by which gradient descent can “complete a loop” and make progress by modifying

W_{3}

,

W_{2}

, or

W_{1}

. Hence this example indicates that

\theta

is not a critical point. In the bottom example,

G

is nonzero but it is not possible to complete a loop by modifying just one factor matrix. Hence this example indicates that

\theta

is a spurious critical point. (Not depicted is the case of a pure critical point, which simply has

G=0

.)

The Geometry of the Set of Equivalent Linear Neural Networks

Abstract

Figures & tables

Appendix

Deep Linear Networks

Flag Varieties: A Geometric Framework for Deep Network Alignment

A Computational Tropical Geometry Framework for Neural Networks

On the Topology of Neural Network Superlevel Sets

$\Theta_{\mathrm{O}}^{\mathrm{conn}}=\{\phi_{l,j-1,j,j,h}\neq\{{\bf 0}\}:L\geq l\geq j>h\geq 0\}$
$\mbox{\hskip-26.73953pt}D_{\mathrm{O}}^{\mathrm{conn}}=\sum_{L\geq l\geq j>h\geq 0}\omega_{lj}\,\omega_{j-1,h}=\sum_{j=1}^{L}\underbrace{(d_{j}-\mathrm{rk}\,W_{j})}_{\beta_{jjj}}\,\underbrace{(d_{j-1}-\mathrm{rk}\,W_{j})}_{\alpha_{j-1,j-1,j-1}}.$ (E.1)
$\Theta_{\mathrm{O}}^{\mathrm{swap}}=\{\phi_{lkjih}\in\Theta_{\mathrm{O}}:l>k\geq i>h\}=\{\phi_{lkjih}\neq\{{\bf 0}\}:L\geq l>k\geq i>h\geq 0$ and $k+1\geq j\geq i\}$
$\mbox{\hskip-26.73953pt}D_{\mathrm{O}}^{\mathrm{swap}}=\sum_{L>k\geq i>0}(k-i+2)\,\underbrace{(\mathrm{rk}\,W_{k+1\blacktriangleleft i}-\mathrm{rk}\,W_{k+1\blacktriangleleft i-1})}_{\beta_{k+1,i,i}}\,\underbrace{(\mathrm{rk}\,W_{k\blacktriangleleft i-1}-\mathrm{rk}\,W_{k+1\blacktriangleleft i-1})}_{\alpha_{k,k,i-1}}$ (E.2)
$\Theta_{\mathrm{O}}^{{\mathrm{off}},{\mathrm{barc}}}=\Theta_{\mathrm{O}}^{\mathrm{off}}\cap\Theta_{\mathrm{O}}^{\mathrm{barc}}=\{\phi_{Lkji0}\neq\{{\bf 0}\}:L\geq k+1\geq j\geq i>0\}$
$\mbox{\hskip-26.73953pt}D_{\mathrm{O}}^{{\mathrm{off}},{\mathrm{barc}}}=\sum_{L\geq k+1\geq i>0}(k-i+2)\,\omega_{Li}\,\omega_{k0}\rule[-18.0pt]{0.0pt}{11.0pt}$ (E.3)
$\Theta_{\mathrm{O}}^{{\mathrm{fiber}},{\mathrm{barc}}}=\Theta_{\mathrm{O}}^{\mathrm{fiber}}\cap\Theta_{\mathrm{O}}^{\mathrm{barc}}=\Theta_{\mathrm{O}}^{\mathrm{barc}}\setminus\Theta_{\mathrm{O}}^{\mathrm{off}}=\{\phi_{lkjih}\in\Theta_{\mathrm{O}}^{\mathrm{barc}}:L>l$ or $h>0\}$

Abstract

Deep Linear Networks

Explore similar work

Flag Varieties: A Geometric Framework for Deep Network Alignment

A Computational Tropical Geometry Framework for Neural Networks

On the Topology of Neural Network Superlevel Sets