# Prove a network is a feedforward network if and only if the numbering of its cells satisfy these conditions

Undergraduate math student here attempting to understand neural networks. Picked up a text on sale, "Neural Network Learning and Expert Systems" (Gallant), and I'm just starting on the exercises for chapter 1.

The full question is:

Prove that a network is a feedforward network if and only if its cells are numbered in a way such that:

• all $p$ input cells are numbered from $1$ to $p$.
• whenever cell $u_j$ is connected to cell $u_i$, then $j < i$.

The definition of a feedforward network, according to Gallant, is a directed network such that there are no cycles between any nodes.

I'm confused for a few reasons.

1. This sounds like I'll need at least a basic understanding of graph theory, which I don't have. Any quick and dirty resources that should cover what I need for this kind of material? I don't even know how to represent a network like this mathematically.

2. I'm used to the numbering of things being pretty arbitrary, for example, numbering basis vectors in a set just to differentiate between them. I don't really have an intuitive idea for why the numbering of input cells is a factor in deciding if a network has directed cycles or not.

Let $G = (V, E)$ with $E \subseteq V \times V$ be a directed graph. A cycle is a path of edges $e_1 = (v_1, v_2), e_2=(v_2, v_3), ..., v_n = (e_n, e_1)$ with $e_i \in E$.

Hence, by definition, the second condition means that the graph has no cycles.

The first condition is necessary because otherwise there could be hidden nodes receiving input from the input nodes (and not vice versa). One could, of course, simply define input nodes as the nodes of a network which don't have incoming edges. But this might cause problems in the definition of recurrent networks.

One direction (given such a numbering, there are no cycles) is elementary, and I encourage you to work it out on your own. The other direction is topological sorting.

I think the question is not very clear; it should mention that when the network is activated, first number 1 is activated, then 2, etc. (chronological).

Say we have the following network:

• Inputs 1 and 2
• Hidden cells 3
• Output cells 4
• connections 1>3, 2>3, 3>4

This is a feed forward network, because all input cells are activated before the other cells and because every connection is pointing to a higher number than its origin number.

If the the network would look like this:

• Inputs 2 and 3
• Hidden cells 1
• output cells 4
• connections 1>3, 2>3, 3>4

You would see that the hidden cell gets activated BEFORE the input cells get activated, so the hidden cell is actually getting activated with the values of an input that is not given yet (so the previous input, because connections remain).