Systems, Man & Cybernetics - July 2015 - 20

Training
As in the standard NT training algorithms, the perceptron
tree training procedure generates a tree in a recursive
manner by partitioning the training set. The procedure
involves three steps: 1) training internal nodes, 2) determining leaf nodes, and 3) labeling them.
For a generic NT with heterogeneous in-node models
(e.g., splits, ANNs, and so on), the training procedure can
be written as shown in Algorithm 1. Starting from the root,
the following holds.
1) The TrainNode procedure is used to train the innode model.
2) The training patterns are later classified by means of
the Classify procedure; hence, the training set is
partitioned.
3) If a partition satisfies the homogeneity condition, then a
leaf node is created and labeled with the corresponding
class. Under particular conditions, the in-node model
can be replaced by a more appropriate one (e.g., in the
perceptron tree, if the training patterns of a node are
not linearly separable, the trained perceptron is substituted by a split node).
4) If a partition is not homogeneous, a new child node is
added to the tree. The child node will be trained using
the patterns of the associated partition.
5) The training stops when all nodes become leaves.
The differences between the alternative NT schemes rely
on the TrainNode procedure and the homogeneity definitions. The former decides which type of in-node model

Algorithm 1. NT Training.
Input: The training set X
Output: The trained NT model
Set Q v ! " v 0 , and Q X ! " X ,;
while Q v do
v ! Pop^Q v h and Xl ! Pop^Q X h;
TrainNode ^v, Xlh;
^Q vt , Q Xt h ! Classify^v, Xlh;
while Q Xt do
if X* ! Pop^Q Xt h is homogeneous then
v * ! Pop^Q vt h is set to leaf;
else
Push^Q v , Pop^Q vt hh;
Push^Q X , X * h;
end
end
end
v 0 represents the root node, and X ! R d # n is the training set
consisting of n d-dimensional feature vectors. Xl 1 X is the
local training set (LTS) at a given node v. Let Q v and Q X be
the queues holding the nodes to train and the corresponding LTSs. TrainNode is the procedure used to train an ANN. It
eventually substitutes the ANN node with a more appropriate classification scheme (e.g., a split node). Classify is the
procedure that, given a node v, classifies the related LTS
and produces the list of child nodes Q vt together with a list
of corresponding patterns Q Xt. The homogeneity property of
a training set is a set of rules that define the correct classification of an LTS. Finally, Pop and Push are the usual queuerelated procedures.

IEEE Systems, Man, & Cybernetics Magazine July 2015

has to be considered, while the latter defines the training
stop criteria.
Classification
The decision-making procedure in the NT is governed
by the Classify function. The class of a test pattern
is obtained by traversing the tree in a top-down fashion,
starting from the root node. At each node, the Classify
function classifies the pattern and, hence, selects the
children to which the pattern should be presented next.
The procedure stops when the pattern reaches a leaf node,
representing the class.
What Are the Limits of NTs?
While NTs solve the problem of defining the ANN architecture a priori, they still have a number of drawbacks.
◆ There is a lack of control on the depth of the tree.
◆ Convergence is not guaranteed for all of the schemes.
◆ Training in-node models on small LTSs limits the
generalization.
◆ As ANNs, NTs also work on features representing the
data.
In recent years, many studies were successfully conducted to address the aforementioned issues [33]. As for
ANNs, the success or failure of NTs for pattern classification still depends on the raw data representations. These
are usually built by means of hand-crafted feature-extraction algorithms that fit to the considered problem. This
highlights the essence of new learning architectures in
inducing the discriminative raw data representation that is
not task-dependent.
Learning Data Representations
To solve the raw data representation problem, in the last
few years, several different systems that are able to automatically learn proper data representations have been
investigated [34], [35]. However, much of the success of the
new deep architectures can be attributed to a relatively old
[36] but special kind of ANN that is able to capture signal
spatiotemporal dependences: the convolutional neural
network (CNN).
To make the introduction to CNNs more intuitive, in the
following sections, we use the example of images rather
than generic signals. Nevertheless, the discussion can be
generalized to any type of signal.
CNNs
In pattern-recognition problems, a vector is usually used
to represent a real signal. In the case of images, this vector
becomes a matrix. Within the matrix, there exists a group
of pixels that share local (spatiotemporal) properties,
which CNNs are able to capture [36]. A CNN is a particular
type of ANN, where precise rules are defined to introduce
the following layers: 1) a convolution layer, 2) a local contrast normalization (LCN) layer, 3) a pooling/subsampling
layer, and 4) a fully connected layer.

Table of Contents for the Digital Edition of Systems, Man & Cybernetics - July 2015