Answers.Body: <p>The equation <span class="math-container">$$\hat{y} = \sigma(xW_\color{green}{1})W_\color{blue}{2} \tag{1}\label{1}$$</span> is the equation of the forward pass of a single-hidden layer fully connected and feedforward neural network, i.e. a neural network with 3 layers, 1 input layer, 1 hidden layer, and 1 output layer, where</p>
  <ul>
  <li>the input layer is connected to the hidden layer (all scalar inputs are connected to every neuron in the hidden layer)</li>
  <li>the hidden layer is connected to the output layer (all neurons in the hidden layer are connected to all neurons in the output layer</li>
  </ul>
  <p>As an example, suppose that we have <span class="math-container">$N$</span> real-valued features, there are <span class="math-container">$L$</span> hidden units (or neurons) and <span class="math-container">$M$</span> output units, then the elements (feature vector and parameters) of equation \ref{1} would have the following shape</p>
  <ul>
  <li><span class="math-container">$x \in \mathbb{R}^{1 \times N}$</span></li>
  <li><span class="math-container">$W_\color{green}{1} \in \mathbb{R}^{N \times L}$</span></li>
  <li><span class="math-container">$W_\color{blue}{2} \in \mathbb{R}^{L \times M}$</span></li>
  </ul>
  <p><span class="math-container">$\sigma$</span> is an activation function that is applicable to all elements of the matrix separately (i.e. component-wise). So, <span class="math-container">$\hat{y} \in \mathbb{R}^{1 \times M}$</span>.</p>
  <p>The equation</p>
  <p><span class="math-container">$$
  \hat{y} = \sum_{\color{red}{i} = 1}^{L} W_{\color{blue}{2}, \color{red}{i} \cdot} \sigma(\langle x, W_{\color{green}{1}, \cdot \color{red}{i}} \rangle )\label{2}\tag{2}
  $$</span></p>
  <p>is another way of writing equation \ref{1}.</p>
  <p>Before going to the explanation, let's try to understand equation \ref{2} and its components.</p>
  <ul>
  <li><p><span class="math-container">$W_{\color{green}{1}, \cdot \color{red}{i}} \in \mathbb{R}^N$</span> is the <span class="math-container">$\color{red}{i}$</span>th column of the matrix that connects the inputs to the hidden neurons, so it is a vector of <span class="math-container">$N$</span> elements (note that we sum over the number of hidden neurons, <span class="math-container">$L$</span>).</p>
  </li>
  <li><p>Similarly, <span class="math-container">$ W_{\color{blue}{2}, \color{red}{i} \cdot} \in \mathbb{R}^M$</span> is also a vector, but, in this case, it is a row of the matrix <span class="math-container">$ W_{\color{blue}{2}}$</span> (rather than a column: why? because we use <span class="math-container">$\color{red}{i} \cdot$</span> instead of <span class="math-container">$\cdot \color{red}{i}$</span>, which refers to the column).</p>
  </li>
  <li><p>So, <span class="math-container">$\langle x, W_{\color{green}{1}, \cdot \color{red}{i}} \rangle$</span> is the dot (or scalar) product between the feature vector <span class="math-container">$x$</span> and the <span class="math-container">$\color{red}{i}$</span>th column of the matrix that connects the inputs to the hidden neurons, so it's a number (or scalar). <a href="https://en.wikipedia.org/wiki/Dot_product" rel="nofollow noreferrer">Note that both <span class="math-container">$x$</span> and <span class="math-container">$W_{\color{green}{1}, \cdot \color{red}{i}}$</span> have <span class="math-container">$N$</span> elements, so the dot product is well-defined in this case</a>.</p>
  </li>
  <li><p><span class="math-container">$ W_{\color{blue}{2}, \color{red}{i}} \sigma(\langle x, W_{\color{green}{1}, \color{red}{i}} \rangle))$</span> is the product between a vector of shape <span class="math-container">$M$</span> and a number <span class="math-container">$\sigma(\langle x, W_{\color{green}{1}, \cdot \color{red}{i}} \rangle )$</span>. <a href="https://en.wikipedia.org/wiki/Scalar_multiplication" rel="nofollow noreferrer">This is also well-defined. You can multiply a real-number with a vector, it's like multiplying the real-number with each element of the vector</a>.</p>
  </li>
  <li><p><span class="math-container">$\sum_{\color{red}{i} = 1}^{L} W_{\color{blue}{2}, \color{red}{i} \cdot} \sigma(\langle x, W_{\color{green}{1}, \cdot \color{red}{i}} \rangle )$</span> is thus the sum of <span class="math-container">$L$</span> vectors of size <span class="math-container">$M$</span>, which makes <span class="math-container">$\hat{y}$</span> also have size <span class="math-container">$M$</span>, as in equation \ref{1}.</p>
  </li>
  </ul>
  <p>Now, the question is: is equation \ref{2} really equivalent to equation \ref{1}? This is still not easy to see because <span class="math-container">$xW_\color{green}{1}$</span> is a vector of shape <span class="math-container">$L$</span>, but, in equation \ref{2}, we do not have any vector of shape <span class="math-container">$L$</span>, but we have vectors of shape <span class="math-container">$N$</span> and <span class="math-container">$M$</span> (and the vectors of shape <span class="math-container">$M$</span> are summed <span class="math-container">$L$</span> times). First, note that <span class="math-container">$\sigma(xW_\color{green}{1}) = h\in \mathbb{R}^L$</span>, so <span class="math-container">$hW_\color{blue}{2}$</span> are <span class="math-container">$M$</span> dot products collected in a vector (i.e. <span class="math-container">$\hat{y} \in \mathbb{R}^M$</span>), where the <span class="math-container">$j$</span>th element of <span class="math-container">$\hat{y}$</span> was computed as a summation of <span class="math-container">$L$</span> elements (a dot product of two vectors is the element-wise multiplication of the elements of the vectors followed by the summation of these multiplications). Ha, still not clear!</p>
  <p>The easiest way (for me) to see that they are equivalent is to think that <span class="math-container">$\sigma(xW_\color{green}{1})$</span> is a vector of <span class="math-container">$L$</span> elements <span class="math-container">$\sigma(xW_\color{green}{1}) = \ell = [l_1, l_2, \dots, l_L]$</span>. Then you know that to multiply this vector with <span class="math-container">$\ell$</span> (<a href="https://math.stackexchange.com/a/1615805/168764">from the left</a>), you actually perform a dot product between <span class="math-container">$\ell$</span> and each column <span class="math-container">$W_\color{blue}{2}$</span>. A dot product is essentially a sum, and that's why we sum in equation \ref{2}. So, essentially, in equation \ref{2}, we first multiple <span class="math-container">$l_1$</span> with the first row of <span class="math-container">$W_\color{blue}{2}$</span> (i.e. by all elements of the first row). Then we multiply <span class="math-container">$l_2$</span> by the second row of <span class="math-container">$W_\color{blue}{2}$</span>. We do this for all <span class="math-container">$L$</span> rows, then we sum the rows (to conclude the dot product). So, you can think of equation 2 as first perform all multiplications, then summing, rather than dot product-by-dot product.</p>
  <p>So, in my head, I have the following picture. To simplify the notation, let <span class="math-container">$A$</span> denote <span class="math-container">$W_\color{blue}{2}$</span>, so <span class="math-container">$A_{ij}$</span> is the element at the <span class="math-container">$i$</span>th row and <span class="math-container">$j$</span>th column of matrix <span class="math-container">$W_\color{blue}{2}$</span>. So, we have the following initial matrix</p>
  <p><span class="math-container">$$
  A = 
  \begin{bmatrix}
  A_{11} &amp; A_{12} &amp; A_{13} &amp; \dots &amp; A_{1M} \\
  A_{21} &amp; A_{22} &amp; A_{23} &amp; \dots &amp; A_{2M} \\
  \vdots &amp; \vdots &amp; \vdots &amp; \dots &amp; \vdots \\
  A_{L1} &amp; A_{L2} &amp; A_{L3} &amp; \dots &amp; A_{LM} \\
  \end{bmatrix}
  = 
  \begin{bmatrix}
  W_{\color{blue}{2}, \color{red}{1} \cdot}  \\
  W_{\color{blue}{2}, \color{red}{2}  \cdot} \\
  \vdots  \\
  W_\color{blue}{2, \color{red}{L}  \cdot} \\
  \end{bmatrix}
  $$</span></p>
  <p>Then, in the first iteration of equation \ref{2}, we do the following</p>
  <p><span class="math-container">$$
  \begin{bmatrix}
  l_1 A_{11} &amp; l_1 A_{12} &amp; l_1 A_{13} &amp; \dots &amp; l_1 A_{1M} \\
  A_{21} &amp; A_{22} &amp; A_{23} &amp; \dots &amp; A_{2M} \\
  \vdots &amp; \vdots &amp; \vdots &amp; \dots &amp; \vdots \\
  A_{L1} &amp; A_{L2} &amp; A_{L3} &amp; \dots &amp; A_{LM} \\
  \end{bmatrix}
  $$</span></p>
  <p>In the second, we do the following</p>
  <p><span class="math-container">$$
  \begin{bmatrix}
  l_1 A_{11} &amp; l_1 A_{12} &amp; l_1 A_{13} &amp; \dots &amp; l_1 A_{1M} \\
  l_2 A_{21} &amp; l_2 A_{22} &amp; l_2 A_{23} &amp; \dots &amp; l_2 A_{2M} \\
  \vdots &amp; \vdots &amp; \vdots &amp; \dots &amp; \vdots \\
  A_{L1} &amp; A_{L2} &amp; A_{L3} &amp; \dots &amp; A_{LM} \\
  \end{bmatrix}
  $$</span>
  Until we have</p>
  <p><span class="math-container">$$
  \begin{bmatrix}
  l_1 A_{11} &amp; l_1 A_{12} &amp; l_1 A_{13} &amp; \dots &amp; l_1 A_{1M} \\
  l_2 A_{21} &amp; l_2 A_{22} &amp; l_2 A_{23} &amp; \dots &amp; l_2 A_{2M} \\
  \vdots &amp; \vdots &amp; \vdots &amp; \dots &amp; \vdots \\
  l_L A_{L1} &amp; l_L A_{L2} &amp; l_L A_{L3} &amp; \dots &amp; l_L A_{LM} \\
  \end{bmatrix}
  $$</span>
  Then we do a <a href="https://www.tensorflow.org/api_docs/python/tf/math/reduce_sum" rel="nofollow noreferrer">reduce sum</a> across the rows to end the dot product (i.e. for each column we sum the elements in the rows). This is exactly equivalent to first performing the dot product between <span class="math-container">$\ell$</span> and the first column of <span class="math-container">$W_\color{blue}{2}$</span>, then the second column, and so on.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-05T18:47:00.680Z
Answers.LastActivityDate: 2021-01-08T17:56:18.943Z
Answers.LastEditDate: 2021-01-08T17:56:18.943Z
Answers.UserDisplayName: nbro
Body: <p>I'm currently reading the paper <a href="https://arxiv.org/pdf/2002.06440.pdf" rel="nofollow noreferrer">Federated Learning with Matched Averaging</a> (2020), where the authors claim:</p>
  <blockquote>
  <p>A basic fully connected (FC) NN can be formulated as: <span class="math-container">$\hat{y} = \sigma(xW_1)W_2$</span> [...]</p>
  <p>Expanding the preceding expression
  <span class="math-container">$\hat{y} = \sum_{i=1}^{L} W_{2, i \cdot } \sigma(\langle x, W_{1,\cdot i} \rangle))$</span>, where <span class="math-container">$ i\cdot$</span> and <span class="math-container">$\cdot i$</span> denote the ith row and column correspondingly and <span class="math-container">$L$</span> is the number of hidden units.</p>
  </blockquote>
  <p>I'm having a hard time wrapping my head around how it can be boiled down to this. Is this rigorous? Specifically, what is meant by the ith row and column? Is this formula for only one layer or does it work with multiple layers?</p>
  <p>Any clarification would be helpful.</p>
  
Tags: <neural-networks><papers><feedforward-neural-networks><linear-algebra><federated-learning>
Title: How to express a fully connected neural network succintly using linear algebra?
UserDisplayName: user1360448
ThreadText: # How to express a fully connected neural network succintly using linear algebra?
  
  (Asked by: username_0 on 2021-01-05)
  
  I'm currently reading the paper [Federated Learning with Matched Averaging](https://arxiv.org/pdf/2002.06440.pdf) (2020), where the authors claim:
  
  > A basic fully connected (FC) NN can be formulated as: $\hat{y} = \sigma(xW\_1)W\_2$ [...]
  >
  > Expanding the preceding expression
  > $\hat{y} = \sum\_{i=1}^{L} W\_{2, i \cdot } \sigma(\langle x, W\_{1,\cdot i} \rangle))$, where $ i\cdot$ and $\cdot i$ denote the ith row and column correspondingly and $L$ is the number of hidden units.
  
  I'm having a hard time wrapping my head around how it can be boiled down to this. Is this rigorous? Specifically, what is meant by the ith row and column? Is this formula for only one layer or does it work with multiple layers?
  
  Any clarification would be helpful.
  
  **Tags:** neural-networks, papers, feedforward-neural-networks, linear-algebra, federated-learning
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-01-05. Score: 8 | Accepted answer
  
  The equation $$\hat{y} = \sigma(xW\_\color{green}{1})W\_\color{blue}{2} \tag{1}\label{1}$$ is the equation of the forward pass of a single-hidden layer fully connected and feedforward neural network, i.e. a neural network with 3 layers, 1 input layer, 1 hidden layer, and 1 output layer, where
  
  * the input layer is connected to the hidden layer (all scalar inputs are connected to every neuron in the hidden layer)
  * the hidden layer is connected to the output layer (all neurons in the hidden layer are connected to all neurons in the output layer
  
  As an example, suppose that we have $N$ real-valued features, there are $L$ hidden units (or neurons) and $M$ output units, then the elements (feature vector and parameters) of equation \ref{1} would have the following shape
  
  * $x \in \mathbb{R}^{1 \times N}$
  * $W\_\color{green}{1} \in \mathbb{R}^{N \times L}$
  * $W\_\color{blue}{2} \in \mathbb{R}^{L \times M}$
  
  $\sigma$ is an activation function that is applicable to all elements of the matrix separately (i.e. component-wise). So, $\hat{y} \in \mathbb{R}^{1 \times M}$.
  
  The equation
  
  $$
  \hat{y} = \sum\_{\color{red}{i} = 1}^{L} W\_{\color{blue}{2}, \color{red}{i} \cdot} \sigma(\langle x, W\_{\color{green}{1}, \cdot \color{red}{i}} \rangle )\label{2}\tag{2}
  $$
  
  is another way of writing equation \ref{1}.
  
  Before going to the explanation, let's try to understand equation \ref{2} and its components.
  
  * $W\_{\color{green}{1}, \cdot \color{red}{i}} \in \mathbb{R}^N$ is the $\color{red}{i}$th column of the matrix that connects the inputs to the hidden neurons, so it is a vector of $N$ elements (note that we sum over the number of hidden neurons, $L$).
  * Similarly, $ W\_{\color{blue}{2}, \color{red}{i} \cdot} \in \mathbb{R}^M$ is also a vector, but, in this case, it is a row of the matrix $ W\_{\color{blue}{2}}$ (rather than a column: why? because we use $\color{red}{i} \cdot$ instead of $\cdot \color{red}{i}$, which refers to the column).
  * So, $\langle x, W\_{\color{green}{1}, \cdot \color{red}{i}} \rangle$ is the dot (or scalar) product between the feature vector $x$ and the $\color{red}{i}$th column of the matrix that connects the inputs to the hidden neurons, so it's a number (or scalar). [Note that both $x$ and $W\_{\color{green}{1}, \cdot \color{red}{i}}$ have $N$ elements, so the dot product is well-defined in this case](https://en.wikipedia.org/wiki/Dot_product).
  * $ W\_{\color{blue}{2}, \color{red}{i}} \sigma(\langle x, W\_{\color{green}{1}, \color{red}{i}} \rangle))$ is the product between a vector of shape $M$ and a number $\sigma(\langle x, W\_{\color{green}{1}, \cdot \color{red}{i}} \rangle )$. [This is also well-defined. You can multiply a real-number with a vector, it's like multiplying the real-number with each element of the vector](https://en.wikipedia.org/wiki/Scalar_multiplication).
  * $\sum\_{\color{red}{i} = 1}^{L} W\_{\color{blue}{2}, \color{red}{i} \cdot} \sigma(\langle x, W\_{\color{green}{1}, \cdot \color{red}{i}} \rangle )$ is thus the sum of $L$ vectors of size $M$, which makes $\hat{y}$ also have size $M$, as in equation \ref{1}.
  
  Now, the question is: is equation \ref{2} really equivalent to equation \ref{1}? This is still not easy to see because $xW\_\color{green}{1}$ is a vector of shape $L$, but, in equation \ref{2}, we do not have any vector of shape $L$, but we have vectors of shape $N$ and $M$ (and the vectors of shape $M$ are summed $L$ times). First, note that $\sigma(xW\_\color{green}{1}) = h\in \mathbb{R}^L$, so $hW\_\color{blue}{2}$ are $M$ dot products collected in a vector (i.e. $\hat{y} \in \mathbb{R}^M$), where the $j$th element of $\hat{y}$ was computed as a summation of $L$ elements (a dot product of two vectors is the element-wise multiplication of the elements of the vectors followed by the summation of these multiplications). Ha, still not clear!
  
  The easiest way (for me) to see that they are equivalent is to think that $\sigma(xW\_\color{green}{1})$ is a vector of $L$ elements $\sigma(xW\_\color{green}{1}) = \ell = [l\_1, l\_2, \dots, l\_L]$. Then you know that to multiply this vector with $\ell$ ([from the left](https://math.stackexchange.com/a/1615805/168764)), you actually perform a dot product between $\ell$ and each column $W\_\color{blue}{2}$. A dot product is essentially a sum, and that's why we sum in equation \ref{2}. So, essentially, in equation \ref{2}, we first multiple $l\_1$ with the first row of $W\_\color{blue}{2}$ (i.e. by all elements of the first row). Then we multiply $l\_2$ by the second row of $W\_\color{blue}{2}$. We do this for all $L$ rows, then we sum the rows (to conclude the dot product). So, you can think of equation 2 as first perform all multiplications, then summing, rather than dot product-by-dot product.
  
  So, in my head, I have the following picture. To simplify the notation, let $A$ denote $W\_\color{blue}{2}$, so $A\_{ij}$ is the element at the $i$th row and $j$th column of matrix $W\_\color{blue}{2}$. So, we have the following initial matrix
  
  $$
  A =
  \begin{bmatrix}
  A\_{11} & A\_{12} & A\_{13} & \dots & A\_{1M} \\
  A\_{21} & A\_{22} & A\_{23} & \dots & A\_{2M} \\
  \vdots & \vdots & \vdots & \dots & \vdots \\
  A\_{L1} & A\_{L2} & A\_{L3} & \dots & A\_{LM} \\
  \end{bmatrix}
  =
  \begin{bmatrix}
  W\_{\color{blue}{2}, \color{red}{1} \cdot} \\
  W\_{\color{blue}{2}, \color{red}{2} \cdot} \\
  \vdots \\
  W\_\color{blue}{2, \color{red}{L} \cdot} \\
  \end{bmatrix}
  $$
  
  Then, in the first iteration of equation \ref{2}, we do the following
  
  $$
  \begin{bmatrix}
  l\_1 A\_{11} & l\_1 A\_{12} & l\_1 A\_{13} & \dots & l\_1 A\_{1M} \\
  A\_{21} & A\_{22} & A\_{23} & \dots & A\_{2M} \\
  \vdots & \vdots & \vdots & \dots & \vdots \\
  A\_{L1} & A\_{L2} & A\_{L3} & \dots & A\_{LM} \\
  \end{bmatrix}
  $$
  
  In the second, we do the following
  
  $$
  \begin{bmatrix}
  l\_1 A\_{11} & l\_1 A\_{12} & l\_1 A\_{13} & \dots & l\_1 A\_{1M} \\
  l\_2 A\_{21} & l\_2 A\_{22} & l\_2 A\_{23} & \dots & l\_2 A\_{2M} \\
  \vdots & \vdots & \vdots & \dots & \vdots \\
  A\_{L1} & A\_{L2} & A\_{L3} & \dots & A\_{LM} \\
  \end{bmatrix}
  $$
  Until we have
  
  $$
  \begin{bmatrix}
  l\_1 A\_{11} & l\_1 A\_{12} & l\_1 A\_{13} & \dots & l\_1 A\_{1M} \\
  l\_2 A\_{21} & l\_2 A\_{22} & l\_2 A\_{23} & \dots & l\_2 A\_{2M} \\
  \vdots & \vdots & \vdots & \dots & \vdots \\
  l\_L A\_{L1} & l\_L A\_{L2} & l\_L A\_{L3} & \dots & l\_L A\_{LM} \\
  \end{bmatrix}
  $$
  Then we do a [reduce sum](https://www.tensorflow.org/api_docs/python/tf/math/reduce_sum) across the rows to end the dot product (i.e. for each column we sum the elements in the rows). This is exactly equivalent to first performing the dot product between $\ell$ and the first column of $W\_\color{blue}{2}$, then the second column, and so on.
  
  
  ---
  
  