# Information Capacity of a Hierarchical Neural Network

## I Introduction

In the context of learning rules by perceptrons, generalization by a neural network is the capability of correctly classify new patterns after some examples being taught to the network (see, e.g.,). For attractor neural networks, another type of generalization was suggested, the categorization, that emerges from an encoding stage where a hierarchical tree of patterns is stored. The ability of the network classifying the patterns on a lower level of the tree (i.e., the $`examples`$), into categories defined by their ancestors (i.e., the $`concepts`$), arises from the Hopfield model if the examples are correlated with their concepts.

A minimal number $`S`$ of examples for each concept is necessary to start the categorization. An extensive number of concepts is then learned by memorizing finite sets of examples. This was shown for networks of binary neurons with fully-connected,, diluted or layered architectures, and for analog, ternary, and non-monotonic neurons, using Hebbian synapses. Similar behavior was found for pseudo-inverse synapses. Categorization is achieved through the appearance of symmetric spurious states. This ability to categorize start just when the capacity of the network recovering the original examples is lost, because of the interference generated by their correlations.

As in most models for pattern recognition, the adequate analysis of the memory capacity of this networks require the tools of the information theory. In the case of non-biased independent patterns, one can avoid it and measure the performance through the Hamming distance $`D`$ between the neuron and the retrieved pattern, and the load capacity $`\alpha `$. One scenario where $`D`$ and $`\alpha `$ are not enough to characterize the system is that of sparse coded patterns. Another one is that of dependent patterns. This is case for categorization models, since the information conveyed by the examples is not extensive in them.

Our goal in this work is to establish a reliable measure for the capacity of retrieving examples and the categorization, based in the information theory. In the next section, we define the model and its parameters. After obtaining the expressions for the information capacity in the section III, in the section IV we study some special cases which present the transition from a retrieval to a categorization phase. Finally we conclude with some remarks in the section V.

## II The Model

Consider a network of $`N`$ binary neurons, with states $`\{\sigma _{i,t}\pm 1\}_{i=1}^N`$ at time $`t`$. The neurons states are updated in parallel according to the deterministic rule

$$\sigma _{i,t+1}=\text{sign}(h_{i,t});h_{i,t}=\underset{i(j)}{\overset{N}{}}J_{ij}\sigma _{jt},$$
(1)   
where $`h_{i,t}`$ is the local field of neuron $`i`$ at time $`t`$. The elements of the Hebbian-like synaptic matrix between neurons $`i`$ and $`j`$ are given by

$`J_{ij}={\displaystyle \frac{1}{N}}{\displaystyle \underset{\mu }{\overset{p}{}}}{\displaystyle \underset{\rho }{\overset{S}{}}}\eta _i^{\mu \rho }\eta _j^{\mu \rho },`$ (2)   
where $`\{\eta _i^{\mu \rho }\}_{\rho =1}^S`$ are the $`examples`$ of the $`concept`$ $`\xi _i^\mu `$. The concepts are independent identically distributed random variables ($`IIDRV`$), $`\{\xi _i^\mu =\pm 1\}_{i=1}^p`$, with equal probability.

In the encoding stage, the examples are built from the concepts, according to the stochastic process:

$$p(\eta _i^{\mu \rho }|\xi _i^\mu )=b\delta (\eta _i^{\mu \rho }\xi _i^\mu )+(1b)\delta (|\eta _i^{\mu \rho }|^21),$$
(3)   
where $`b=\eta _i^{\mu \rho }\xi _i^\mu `$ gives the correlation between the ancestors (the concepts) and the descendants (the examples) of this tree of patterns. The second delta of this conditional distribution gives the component of the examples which is independent on the concepts. This process can equivalently be formulated as $`\eta _i^{\mu \rho }=\xi _i^\mu \lambda _i^{\mu \rho }`$, where the $`biased`$ IIDRV $`\lambda _i^{\mu \rho }`$ are distributed according to

$$p_B(\lambda _i^{\mu \rho })=B_+\delta (\lambda _i^{\mu \rho }1)+B_{}\delta (\lambda _i^{\mu \rho }+1),$$
(4)   
with $`B_\pm =(1\pm b)/2`$.

The macroscopic parameters which describe the state of the network are the $`retrieval`$ and the $`categorization`$ $`overlaps`$, respectively:

$`m_{Nt}^{\mu \rho }{\displaystyle \frac{1}{N}}{\displaystyle \underset{j}{}}\eta _j^{\mu \rho }\sigma _{jt},M_{Nt}^\mu {\displaystyle \frac{1}{N}}{\displaystyle \underset{j}{}}\xi _j^\mu \sigma _{jt}.`$ (5)   
In the thermodynamic limit, the qualities of the retrieval and of the categorization can be measured by taking the $`limN\mathrm{}`$ of the overlaps for a single concept, say $`\mu =1`$, which give

$`m_t^{1\rho }\eta ^{1\rho }\text{sign}[h_{t1}],M_t^1\xi ^1\text{sign}[h_{t1}],`$ (6)   
where the brackets mean averages over the set of examples $`\eta ^{1\rho }`$ and the local field $`h_{t1}`$ for a single neuron.

The $`generalization`$ $`error`$, can be defined as $`E_t^1|\sigma _t\xi ^1|^2=1M_t^1`$, as a function of the categorization overlap. The stationary states are given by macroscopic overlaps with examples of a given concept, say $`m_{\mathrm{}}^{1\rho }m^{1\rho }`$, and microscopic remaining overlaps $`\nu >1`$, $`m^{\nu \rho }1/\sqrt{N}`$. The general solution is represented by a retrieval overlap with a single example, say $`m^{11}m`$, and the $`quasisymmetric`$ overlaps with the other examples, $`m^{1\rho }m^S,\rho >1`$. In the retrieval phase one have $`m1`$, $`m^Sb^2`$, while in the categorization phase the stable state is $`m=m^Sb`$, which may leads to a large categorization overlap, $`M_{\mathrm{}}^1M1`$. In the following we will consider a situation where the network have relaxed to the equilibrium states, so we can drop the time $`t`$ on the parameters.

## III Information Capacities

In this section we describe a way to measure the storage of information by the network in the retrieving and categorizing regimes. There are two types of information to be extracted from the patterns in these network: the retrieval information and the categorization information. The former is that which can be conveyed from the examples to the neurons, while the latter is that which can be conveyed from the concepts. In each case one must calculate the information entropy of the pattern distributions, $`H[\{\xi _i^\mu \}_{i,\mu }^{N,p}]=_{\{\xi _i^\mu \}}p(\{\xi _i^\mu \})\mathrm{log}[p(\{\xi _i^\mu \})]`$, and $`H[\{\eta _i^{\mu \rho }\}_{i,\mu ,\rho }^{N,p,S}]=_{\{\eta _i^{\mu \rho }\}}p(\{\eta _i^{\mu \rho }\})\mathrm{log}[p(\{\eta _i^{\mu \rho }\})]`$, where $`p(\{\xi _i^\mu \})`$ and $`p(\{\eta _i^{\mu \rho }\})`$ are the concepts and examples joint probability distributions, respectively.

The categorization information can be easily measured by computing the categorization overlap of a single concept, $`M`$, and its entropy. Since the concepts $`\{\xi _i^\mu \}_{i,\mu }^{N,p}`$ are IIDRV, their probability distribution is factorial, $`p(\{\xi _i^\mu \}_{i,\mu }^{N,p})=_{i,\mu }^{N,p}p(\xi _i^\mu )`$. Thus, the entropy of the concepts is extensive, $`H[\{\xi _i^\mu \}_{i,\mu }^{N,p}]=_{\mu ,i}^{p,N}H[\xi _i^\mu ]=pNH[\xi ]`$, where the entropy of a single concept on a single neuron is $`H[\xi ]=\mathrm{log}(2)`$. As we study binary patterns, we shall use base-2 logarithm in order to count information in bits, then we have $`H[\xi ]=1`$. The equivocation in the categorization can be evaluated by the square of the overlap, in such a way that no information is transmitted by the concepts if $`M=0`$ and the information is maximal if $`M=\pm 1`$, reminding that the information is symmetric in this overlap, because an inverted concept $`\sigma _i=\xi _i`$ carries the same information than $`\sigma _i=\xi _i`$. Therefore, the total categorization information is $`I_C=pNM^2H[\xi ]`$, and the categorization information (per synapse) is

$$i_C=\alpha M^2.$$
(7)   
The retrieval information can be similarly measured, by computing the retrieval overlap and the entropy of the examples, since this entropy can also be factorized as $`p(\{\eta _i^{\mu \rho }\}_{i,\mu ,\rho }^{N,p,S})=_{i,\mu }^{N,p}p(\{\eta _i^{\mu \rho }\}_\rho ^S)`$, such that the entropy is extensive in the concepts and in the neurons, $`H[\{\eta _i^{\mu \rho }\}_{i,\mu ,\rho }^{N,p,S}]=_{\mu ,i}^{p,N}H[\{\eta _i^{\mu \rho }\}_\rho ^S]=pNH[\{\eta ^\rho \}_\rho ^S]`$. Thus it is enough to calculate the entropy of a set of examples of a single concept, $`\{\eta ^\rho \}_\rho ^S\{\eta _i^{\mu \rho }\}_\rho ^S`$, on a single neuron, to get the entropy of the whole set $`\{\eta _i^{\mu \rho }\}_{i,\mu ,\rho }^{N,p,S}`$.

On the other hand, $`\{\eta ^\rho \}_\rho ^S`$ is $`not`$ a set of IIDRV, so $`p(\{\eta ^\rho \}_\rho ^S)`$ is $`not`$ factorizable in example probabilities, and the entropy is $`not`$ extensive in the examples, $`H[\{\eta ^\rho \}_\rho ^S]_\rho ^SH[\eta ^\rho ]`$. So the retrieval information is not the naive one, $`i_R\alpha S`$.

Let $`\{\eta ^\rho \}\{\eta ^\rho \}_\rho ^S`$ be a set of examples of a given concept on a given neuron. In calculating $`p(\{\eta ^\rho \})`$ we proceed as it follows: we take the conditional probability of the examples given the concept, $`p(\{\eta ^\rho \}|\xi )`$, from Eq.(3), and average it on the distribution of $`\xi `$,

$$p(\{\eta ^\rho \})=p(\{\eta ^\rho \}|\xi )_\xi =\underset{\rho =1}{\overset{S}{}}\frac{p_B(\eta ^\rho )+p_B(\eta ^\rho )}{2},$$
(8)   
where $`p_B`$ is the probability distribution in Eq.(4). After expanding this product, we calculated the entropy of this distribution, obtaining

$`H[\{\eta ^\rho \}]={\displaystyle \underset{k=0}{\overset{S}{}}}C_k^SA_k\mathrm{log}(A_k);`$ (9)   
$`A_k=[B_+^kB_{}^{Sk}+B_{}^kB_+^{Sk}]/2,`$ (10)   
where $`C_k^S`$ are the combinatorial numbers.

In evaluating the equivocation in the retrieval, we here have to multiply this entropy by the square of the retrieval overlap of a single example. Since we have to subtract the information due to the categorization, and the overlaps between examples and their concepts are $`b=\eta ^\rho \xi `$, we estimate the total retrieval information as $`I_R=pN(mbM)^2H[\{\eta ^\rho \}]`$. Therefore the retrieval information (per synapse) is

$$i_R=\alpha (mbM)^2H[\{\eta ^\rho \}].$$
(11)   
Although other measures for the informations could be used, they must be monotonous functions of those we consider in the Eqs.(7),(11). These have, nevertheless, the advantage that both are equivalently scaled and they can be directly compared to each other.

## IV Results

We present now the equilibrium states for the networks which are used to obtain the retrieval and categorization informations. This states are studied for two systems: an asymptotic network ($`N\mathrm{}`$), for which analytical stationary equations were derived and finite-sized systems, for which simulations of the dynamics in Eq.(1) are carried on. While the information measures obtained in the previous section are functions of asymptotic parameters, $`M`$ and $`m`$, the results from simulation use the overlaps in Eqs.(5).

### A Asymptotic network

First we study the stationary states of the overlaps in Eqs.(5), in the thermodynamic limit $`N\mathrm{}`$. Using the Hebbian synapses in Eq.(2) in the dynamics in Eq.(1), taking the local field at the fixed point, and averaging over the distribution of a single example, one get:

$`m=`$ $`{\displaystyle \underset{k=0}{\overset{S1}{}}}p_S(k){\displaystyle _{\mathrm{}}^{\mathrm{}}}Dz[B_+G_+B_{}G_{}],`$ (12)   
$`M=`$ $`{\displaystyle \underset{k=0}{\overset{S1}{}}}p_S(k){\displaystyle _{\mathrm{}}^{\mathrm{}}}Dz[B_+G_++B_{}G_{}],`$ (13)   
$`m^S=`$ $`{\displaystyle \underset{k=0}{\overset{S1}{}}}p_S(k){\displaystyle \frac{x_S}{S1}}{\displaystyle _{\mathrm{}}^{\mathrm{}}}Dz[B_+G_++B_{}G_{}],`$ (14)   
for the retrieval, categorization and quasi-symmetric overlap, respectively. Here

$$G_\pm =\text{sign}[x_Sm^S\pm m+z\sqrt{\alpha r}],$$
(15)   
with $`x_S_{\rho =2}^S\lambda _\rho 2k(S1)`$. and the averages are over the remaining $`S1`$ examples from the first concept, and the remaining $`p1`$ concepts. The first is the binomial variable $`x_S=2k(S1)`$, distributed according to

$$p_S(k)=C_k^{S1}B_+^kB_{}^{S1k},$$
(16)   
the last is a Gaussian noise, distributed according to

$$Dz=\frac{dz}{\sqrt{2\pi }}e^{\frac{z^2}{2}}.$$
(17)   
In the present case of a fully-connected network, there is a strong feedback in the dynamics, but an expression for the variance of the noise can be obtained using a replica symmetric approach,,

$$r=s\frac{[1C(1b^2)(1b^2+sb^2)]^2+(s1)b^4}{[1C(1b^2)]^2[1C(1b^2+sb^2)]^2},$$
(18)   
with

$$C=\frac{1}{\sqrt{\alpha r}}\underset{k=0}{\overset{S1}{}}p_S(k)_{\mathrm{}}^{\mathrm{}}Dzz[B_+G_++B_{}G_{}].$$
(19)   
We have to solve this Eqs.(14)-(19), then we introduce the overlaps in the expressions for the informations, Eqs.(7),(11). These analytical results for the information are then presented in comparison with the results from simulation.

### B Simulation

The simulations we have performed are for networks of $`N=5,000`$ and $`N=10^4`$ neurons, which are updated in parallel according to the dynamics in Eq.(1), up to $`t=10`$ time steps, or when the overlaps converge. Thus we have $`almost`$ stationary states in most cases, except when a state of non-information is obtained, for which the times of convergence are typically much larger.

The capacity is analized as a function of the two parameters of loading of the network: the rate of loading of concepts, $`\alpha =p/N`$, and the number of examples per concept, $`S`$. The sample averages are taken over an interval in $`\mathrm{ln}(S)`$ or in $`\alpha `$. When simulating the information as a function of $`S`$, we generate first the concepts and then store consecutively the examples of each concept. When simulating the information as a function of $`\alpha `$, we generate the $`S`$ examples of the concept generated at each step of the learning.

The network is trained then storing examples, while the retrieval and categorization overlaps are monotorized. For a fixed $`\alpha `$, it is expected that increasing $`S`$ the network pass from a regime where the retrieving information is large to another where the categorizing information increase up to saturation in a upper bound. This behavior is seen in Fig.1, where the overlaps, as well as the informations, are plotted as a function of $`\mathrm{ln}(S)`$, with a correlation $`b=0.3`$, for a loading of concepts $`\alpha =0.01`$. When more and more examples are learned, the retrieval information increases until a maximum at $`S_R=7`$, then it falls down. After a while when no information is transmitted, the network reach, at $`S_C33`$, the categorization phase, where the categorization information jumps to a higher value. It continues to increase untill it saturates in $`i_C=0.01`$, when the network reach $`M1`$ after $`S90`$. The retrieval information capacity of the network is $`i_R0.06`$. The asymptotic theory for $`N\mathrm{}`$ fits quite well the simulation for $`N=10^4`$, except in the region of no information. This is due to the finite number of steps used in the dynamical simulation, $`t=10`$, while the convergence to the fixed-point there is very slow.

A case with a larger load of concepts, $`\alpha =0.04`$, is plotted in Fig.2. Although now the network can only retrieve well the examples up to $`S=3`$, it has $`i_R0.10`$. Then there is a large waiting period where the informations stay close to zero, up to $`S_C74`$, when the categorization information jumps to $`i_C0.04`$, which is much larger than in the case $`\alpha =0.01`$.

Comparing this with a network with larger correlation, $`b=0.4`$, plotted in Fig.3, we observe that the network can store with a larger overlap only $`S_R=2`$ examples, with a maximal retrieval information $`i_R0.05`$, which is somewhat smaller than the naive $`S\alpha 0.08`$. However the categorization information approaches its saturation value $`i_C0.04`$ much faster, only $`S30`$ examples must be learned. We have checked that for larger load of concepts ($`\alpha 0.06`$) the categorization information is larger than the retrieval information. Also we verified the for higher correlations ($`b0.6`$) the categorization information can be the larger one, even for small load $`\alpha 0.01`$, while for smaller correlations ($`b0.2`$) the retrieval information is always the larger one.

For a fixed $`S`$, one expects that increasing $`\alpha `$ the categorization information (if $`b`$ or $`S`$ are large enough) increases up to a maximum value after which it decreases until it becomes zero at a critical $`\alpha `$. This behavior can be seen in Fig.4, where the case $`b=0.2`$, $`S=170`$ is plotted. We verified that the larger the values of $`b`$, the higher are the maxima of $`i_C`$, and less examples are need. We also observed that the retrieval information have a similar non-monotonic behavior if $`b`$ or $`S`$ are small.

## V Conclusion

The information conveyed by the categorization model was studied. It was shown that the transition from the retrieval phase to the categorization phase carries together a transition in the information: the retrieval information decreases when the network is oversaturated with examples, and after a period of resting, the categorization information increases.

It is interesting to note that, although neither the retrieval nor the categorization informations surpasses the usual Hopfield model, ($`S=1`$, $`b=1`$), which is $`i_R0.13`$ at $`\alpha =0.135`$, the fact that the network can return to behave as an associative memory after a long period of $`resting`$ between $`S_R<S<S_C`$ is an advantage with respect to Hopfield network. It is also of worth of note that the retrieval information can still be relatively large, as we see in Fig.2, a quotation which was not observed before in any work about the categorization model in the literature.

The simulation results fit very well with the theoretical in both retrieval and categorization regimes, showing that almost no effect of finite-size is present, but the time of convergence in the resting period must be much larger than that used in this work.

Both expressions for the information of the retrieval and of the categorization in Eqs.(11-7) are not claimed to be exact. They are approximations for a more precise measure, the $`mutual`$ $`information`$ between neuron and patterns, $`[\sigma ,\xi ]=H[\xi ]H[\sigma |\xi ]_\xi `$, where $`H[\sigma |\xi ]`$ is the conditional entropy. Since we know that the conditional probability of the neuron, given the concept state, is $`p(\sigma |\xi )=(1+M\sigma \xi )\delta (|\sigma |^21)`$, we can replace the categorization information by

$$[\sigma ,\xi ]=\frac{1+M}{2}\mathrm{ln}(1+M)+\frac{1M}{2}\mathrm{ln}(1M).$$
(20)   
This quantity gives the degree of information the neuron can catch from the concept. However we prefer to use the estimation in Eq.(7) to compare with the retrieval information with the same precision.

Finally we hope that the present approach to the information content of a neural network of correlated patterns can be used in the context of more general architectures and learning rules. A more general distribution of the $`\lambda _i^{\mu \rho }`$ may also deserves some attention.

Acknowledgments

This work was financially supported by the Research Fund of the K.U.Leuven (grant OT/94/9).