3
$\begingroup$

Suppose we have a neural network with an input layer, $n$ hidden layers, and an output layer. The input layer has $d_o$ units ($d_o-1$ inputs and a bias). Each hidden layer has $d_i$ units (bias is included in $d_i$). Finally, the output layer has only one unit. The restriction on the hidden layers is that the total number of units is a constant such that $\sum_{i=1}^nd_i=Q_o$.

By denoting the number of output layers $d_{n+1}$ (it is equal to $1$ here, but is denoted $d_{n+1}$ for generality), the total number of weights $N_w$ in the network is

$N_w=d_o(d_1-1)+d_1(d_2-1)+...+d_{n-1}(d_n-1)+d_nd_{n+1}$

or simply

$N_w=\sum_{i=0}^{n}d_i(d_{i+1}-1)+d_n$

The question is: Is there a way to maximize the number of weights $N_w$ by varying $n$ and the distribution $d_i$ for $i=1,2,..,n$ while holding the condition $\sum_{i=1}^nd_i=Q_o$?

$\endgroup$
0
$\begingroup$

Hint.

We can solve this optimization problem easily using the Lagrangian formulation. Calling

$$ f_n = \sum_{k=1}^{n-1} d_k(d_{k+1}-1)+d_n $$

with the restrictions

$$ \cases{ d_k \ge 1,\ \ k=1,\cdots, n-1\\ d_n = 1\\ \sum_{k=1}^n d_k=Q } $$

we have

$$ L_n = f_n+\lambda\left(\sum_{k=1}^n d_k-Q\right)+\sum_{k=1}^{n-1}\mu_k(d_k-1-\epsilon_k^2)+\mu_n(d_n-1) $$

so the stationary conditions are the solutions for $n=5$

$$ \nabla L = 0 = \left( \begin{array}{l} d_2+\lambda +\mu_1-1 \\ d_1+d_3+\lambda +\mu_2-1 \\ d_2+d_4+\lambda +\mu_3-1 \\ d_3+d_5+\lambda +\mu_4-1 \\ d_4+\lambda +\mu_5+1 \\ \epsilon_1 \mu_1 \\ \epsilon_2 \mu_2 \\ \epsilon_3 \mu_3 \\ \epsilon_4 \mu_4 \\ d_1-\epsilon_1^2-1 \\ d_2-\epsilon_2^2-1 \\ d_3-\epsilon_3^2-1 \\ d_4-\epsilon_4^2-1 \\ d_5-1 \\ d_1+d_2+d_3+d_4+d_5-Q \\ \end{array} \right. $$

Here $\lambda,\mu_k$ are multipliers and $\epsilon_k$ are slack variables to transform the inequalities into equations. The nonlinear restrictions $e_k\mu_k = 0$ can be handled by a binary expansion associated to the possible $\epsilon_k=0$ or $\mu_k = 0$ who verify $\epsilon_k\mu_k=0$.

The solution for $n=5$ gives

$$ \left[ \begin{array}{cccccccccccccccc} f_5&d_1&d_2&d_3&d_4&d_5&\lambda &\mu _1&\mu _2&\mu _3&\mu_4&\mu _5&\epsilon _1^2&\epsilon _2^2&\epsilon _3^2&\epsilon _4^2\\ 1 & Q-4 & 1 & 1 & 1 & 1 & 0 & 0 & 4-Q & -1 & -1 & -2 & Q-5 & 0 & 0 & 0 \\ \frac{1}{2} \left(\frac{Q-2}{2}-1\right) (Q-4)+1 & \frac{Q-4}{2} & \frac{Q-2}{2} & 1 & 1 & 1 & \frac{4-Q}{2} & 0 & 0 & -1 & \frac{Q-6}{2} & \frac{Q-8}{2} & \frac{Q-6}{2} & \frac{Q-4}{2} & 0 & 0 \\ \frac{1}{2} \left(\frac{Q-3}{2}-1\right) (Q-3)+\frac{Q-3}{2} & 1 & 1 & \frac{Q-3}{2} & \frac{Q-3}{2} & 1 & \frac{3-Q}{2} & \frac{Q-3}{2} & 0 & 0 & 0 & -1 & 0 & 0 & \frac{Q-5}{2} & \frac{Q-5}{2} \\ \frac{1}{2} \left(\frac{Q-3}{2}-1\right) (Q-3)+\frac{Q-3}{2} & 1 & \frac{Q-3}{2} & \frac{Q-3}{2} & 1 & 1 & \frac{3-Q}{2} & 1 & 0 & 0 & 0 & \frac{Q-7}{2} & 0 & \frac{Q-5}{2} & \frac{Q-5}{2} & 0 \\ Q-4 & 1 & 1 & 1 & Q-4 & 1 & -1 & 1 & 0 & 5-Q & 0 & 4-Q & 0 & 0 & 0 & Q-5 \\ Q-4 & 1 & 1 & Q-4 & 1 & 1 & -1 & 1 & 5-Q & 0 & 5-Q & -1 & 0 & 0 & Q-5 & 0 \\ Q-4 & 1 & 2 & 1 & Q-5 & 1 & -1 & 0 & 0 & 5-Q & 0 & 5-Q & 0 & 1 & 0 & Q-6 \\ Q-4 & 1 & Q-4 & 1 & 1 & 1 & -1 & 6-Q & 0 & 5-Q & 0 & -1 & 0 & Q-5 & 0 & 0 \end{array} \right] $$

Note that the feasible solutions should have all $\epsilon_k^2\ge 0$. So among those stationary points we can obtain the maximum: thus for $Q = \{20, 21\}$ we have the optimal values.

$$ \left[ \begin{array}{ccccccc} f_5&d_1&d_2&d_3&d_4&d_5&Q\\ 65 & 8 & 9 & 1 & 1 & 1 & 20 \\ 81 & 1 & 1 & 9 & 9 & 1 & 21\\ 81 & 1 & 9 & 9 & 1 & 1 & 21 \\ \end{array} \right] $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.