Patent Description:
With the increasing use of neural network technology to compute predictions which are used for automated decision making, there is a growing need for interpretability of the technology. Often humans would like an explanation of how a particular decision was reached by an automated system.

Another consideration is the memory and processing requirements of neural network technology which are often significant. Where neural networks are to be stored on resource constrained devices such as smart phones and wearable computers, there is a need to try to reduce the memory and processing requirements involved. If a deep neural network is stored on a wearable computer and used to compute a prediction the computational work involved at the wearable computer can be significant and can impede the operation of other functions at the wearable computer as well as depleting power. As a result it can be difficult to deploy neural networks on resource constrained devices such as smart phones or embedded devices.

Large numbers of training examples are typically used to train neural networks in order to carry out classification tasks or regressions tasks. The training process is typically time consuming and resource intensive. There is a desire to reduce the amount of time, memory and processing resources needed for training neural network systems. For example, neural networks grow significantly with depth and so cannot be trained too deeply on computers with limited memory.

There is an ongoing need to improve the accuracy of neural network predictors and to improve generalization ability. Generalization ability is being able to accurately perform the task in question even for examples which are dissimilar to those used during training.

The embodiments described below are not limited to implementations which solve any or all of the disadvantages of known neural network technology. <NPL>), describes a neural decision tree \ which takes simplified neural networks as decision function in each branch and employs complex neural networks to generate the output in each leaf.

<NPL>), describes Neural Decision Forests, a novel approach to jointly tackle data representation and discriminative learning within randomized decision trees. Randomized Multi- Layer Perceptrons (rMLP) are used as split nodes which are capable of learning non-linear, data-specific representations and taking advantage of them by finding optimal predictions for the emerging child nodes.

The following presents a simplified summary of the disclosure in order to provide a basic understanding to the reader. This summary is not intended to identify key features or essential features of the claimed subject matter nor is it intended to be used to limit the scope of the claimed subject matter. Its sole purpose is to present a selection of concepts disclosed herein in a simplified form as a prelude to the more detailed description that is presented later.

In various examples there is a predictor for predicting an outcome given an example. The predictor has a memory which stores at least one example for which an associated outcome is not known. The memory stores at least one decision tree comprising a plurality of nodes connected by edges, the nodes comprising a root node, internal nodes and leaf nodes. Individual ones of the nodes and individual ones of the edges each have an assigned module, comprising parameterized, differentiable operations, such that for each of the internal nodes the module computes a binary outcome for selecting a child node of the internal node. The predictor has a processor configured to compute the prediction by processing the example using a plurality of the differentiable operations selected according to a path through the tree from the root node to a leaf node.

The detailed description provided below in connection with the appended drawings is intended as a description of the present examples and is not intended to represent the only forms in which the present example are constructed or utilized. The description sets forth the functions of the example and the sequence of operations for constructing and operating the example. However, the same or equivalent functions and sequences may be accomplished by different examples.

Although the present examples are described and illustrated herein as being implemented in an image processing system, the system described is provided as an example and not a limitation. As those skilled in the art will appreciate, the present examples are suitable for application in a variety of different types of image processing or machine learning systems. A machine learning system is one or more computing devices which has a stored representation describing knowledge about one or more examples, and which updates the stored representation in the light of observed examples.

<FIG> is a schematic diagram of a plurality of systems in which a machine learning system with one or more neural trees. For example, a body part classification or joint position detection system <NUM> operating on depth images <NUM>. The depth images may be from a natural user interface of a game device as illustrated at <NUM> or may be from other sources. The body part classification or joint position information may be used to calculate gesture recognition <NUM>.

In another example, a person <NUM> with a smart phone <NUM> sends an audio recording of his or her captured speech <NUM> over a communications network to a machine learning system <NUM> that carries out phoneme analysis. The phonemes are input to a speech recognition system <NUM> which uses one or more neural trees. The speech recognition results are used for information retrieval <NUM>. The information retrieval results may be returned to the smart phone <NUM>.

In another example medical images <NUM> from a CT scanner <NUM>, MRI apparatus or other device are used for automatic organ detection <NUM>.

In the examples of <FIG> a machine learning system using one or more neural trees is used for classification or regression. This gives better accuracy and/or generalization performance as compared with previous systems using equivalent amounts of computing resources and training time. The systems are also workable where memory resources are limited such as on smart phones or embedded devices.

A neural tree is a plurality of nodes connected by edges to form a tree structure and where at least some of the nodes and edges each have an assigned module comprising parameterized, differentiable operations. As an example passes along a path through the neural tree from a root node of the tree to a leaf node, it is transformed according to the operations at the edges and nodes along the path. The modules are configured so that a sequence of modules along a path through the neural tree from the root node to a leaf node forms a neural network. That is, a module comprises operations which are operations carried out by one or more layers of a neural network.

The modules comprise routers, transformers and solvers. A router is a type of module assigned to an internal node of the neural tree and it computes a binary decision for routing samples from the incoming edge of the internal node to one of the child nodes of the internal node. A transformer is a type of module assigned to an edge in a neural tree and which computes a nonlinear function. An edge of a neural tree may have more than one transformer assigned to it. A solver is a type of module assigned to a leaf node of a neural tree. A solver receives input data from its incoming edge and it computes an estimate of a conditional distribution expressing the probability of an outcome y given an input x.

In various examples described herein, neural trees are described for supervised learning tasks, where the aim is to learn a conditional distribution p(y|x), which can be thought of as the probability of outcome y given input example x, from a set of N labelled samples <MAT> as training data.

A neural tree is defined formally as a tree-structured model, characterized by a set of hierarchical partitions of an input space X, a series of nonlinear transformations, and separate predictive models in the respective component regions. In particular, a neural tree is an ordered pair ( <MAT>) where <MAT> defines the topology of the neural tree, and <MAT> denotes the set of operations on it (i.e. the modules assigned to the nodes and edges of the neural tree).

In various examples described herein, the topology <MAT> comprises binary trees, defined as a set of finite graphs whose every node is either a leaf or an internal node, and every node is the child of exactly one parent node, except for a distinguished root node, which has no parent. The topology of a tree is an ordered set <MAT> where <IMG> is the set of nodes, and ε is the set of edges between them. Nodes with no children (at the bottom of the tree) are called leaf nodes (denoted by leaves(<IMG>)), and others are called internal nodes. For every internal node j ∈ internals(<IMG>): = <IMG> \ leaves(<IMG>), there are exactly two children nodes, represented by left(j) and right(j). Unlike standard trees, ε contains an edge which connects input data x with the root node, as shown in <FIG>.

Individual ones of the nodes and edges are assigned with a module comprising an operation which acts on the allocated samples of data. Starting at the root, every sample gets transformed and traverses the tree according to the set of defined operations <MAT>. Each tree is constructed based on three primitive modules of differentiable operations described below:.

Routers, <IMG> : an internal node j ∈ internals(<IMG>) holds a router module, <MAT>, parametrised by θ, which decides to send samples from the incoming edge to the left or right child. Note that Xj denotes representation at node j. Embodiments use stochastic routing here where its binary decision (<NUM> for the left and <NUM> for the right branch) is sampled from Bernouli random variable with mean <MAT> for input xj ∈ Xj. For example, <MAT> can be defined as a small convolutional neural network (CNN).

Transformers, <IMG> : an edge e ∈ ε of the tree has one or a composition of multiple transformer module(s). Each transformer <MAT> is a non-linear function, parametrized by ψ, that transforms samples from the previous module and passes them to the next one. For example, <MAT> can be a single convolutional layer followed by a rectified linear unit (ReLU). Unlike standard decision trees (DTs), edges are allowed to "grow" by adding more transformer operations as described later in this document.

Solvers, <IMG> : a leaf node l ∈ leaves(<IMG>) is assigned to a solver module, <MAT>, parametrized by φ, which operates on the transformed input data and outputs an estimate for the conditional distribution p(y|x). For example, in the case of classification, embodiments define the solver sφ as a linear classifier on the feature space Xl, which outputs a probability distribution over target classes.

Defining operations on a neural tree expressed as a graph <MAT> amounts to a specification of the triplet <MAT>. For example, given inputs from an image domain, the operations of each module (<IMG>) are selected from a set of operations commonly used in convolutional neural networks CNNs. As a result, every computational path on the resultant neural tree is a CNN, and the set of routers that guide input to one of these paths are also given by convolutional neural networks (CNNs).

<FIG> is a schematic diagram of a processing pipeline for growing and training a neural tree. Training data <NUM> is available from a store or other source. The training data comprises labelled examples, such as labelled images, labelled phonemes, labelled text, labelled skeletal features, or other labelled examples according to the task that the neural tree is to be used for.

During a growth phase a growth module <NUM> begins with an initial tree structure, and grows nodes and edges onto the initial tree structure as described in more detail with reference to <FIG> and <FIG>. Growth involves assigning modules <NUM> comprising parameterized, differentiable operations, to individual ones of the nodes and edges as they are grown onto the initial tree structure. The modules <NUM> are pre-defined and comprise primitive operations of a neural network. Growth continues until the tree structure reaches a threshold size and/or until convergence is reached.

The growth module <NUM> outputs a neural tree <NUM>. Optionally the neural tree is refined <NUM> in order to prune branches which are redundant and so produce a final neural tree <NUM>. The final neural tree is then deployed at a smart phone, wearable computer or other computing device by storing the parameters of the final neural tree at the computing device. In some cases the final neural tree is deployed in the cloud. The final neural tree is deployed together with a plurality of other neural trees in a neural forest in some cases.

By using the growth module it is possible to grow the topology of the neural tree so that it is bespoke to the particular training data. In contrast a neural network has an architecture which is pre-configured before training and is independent of the particular training data used. In this way the neural tree architecture is better suited to the particular task than a neural network and is typically smaller (fewer nodes) than a neural network used for the same task. The reduction in size brings efficiencies in terms of space needed to store the neural tree at a resource constrained device. The reduction in size also brings efficiencies in the amount of computing resources needed at test time inference.

<FIG> is a schematic diagram of a neural tree comprising a root node <MAT>, one internal node <MAT>, and three leaf nodes <MAT>. The root node <MAT> has one incoming edge with a transformer module <MAT> represented by a black circle on the incoming edge. An example x is transformed by transformer module <MAT> before reaching the root node <MAT>. The root node <MAT> has two outgoing edges, one with two transformers on it <MAT> which terminates at leaf node <MAT>, and one with a single transformer on it which terminates at the internal node <MAT>. The internal node <MAT> has two outgoing edges each of which terminates in a leaf node <MAT>.

<FIG> is a schematic diagram of three branches of a neural tree which illustrate three outcomes occurring during the growing process. According to outcome a "keep" in <FIG> the leaf node is unchanged so that the solver is as it was before the growing operation, and the transformer on the incoming edge is as it was before the growing operation. According to outcome b "split" in <FIG> an existing leaf node is split to create two new leaf nodes <MAT>. A new internal node is created denoted <MAT> in <FIG>. The transformer on the edge incoming to the new internal node is the same as for the transformer on the edge incoming to the original leaf node. The outgoing edges from the new internal node each have a transformer which is an identity transformer (i.e. a transformer which makes no change to the data it processes). According to outcome c "extend" in <FIG> an existing incoming edge to a leaf node is extended by adding another transformer <MAT>. Thus the incoming edge to the leaf node now has two transformers connected in series, which are the pre-existing transformer <MAT> and the new transformer.

More detail about the process carried out by the growth component <NUM> of <FIG> is now given with reference to <FIG>. To grow a neural tree from scratch, the growth component starts <NUM> at a root node which it creates. It selects the current node, which is the root node in the case that there are no other nodes yet. If other nodes of the neural tree are present, the growth process proceeds to select a current node using a breadth-first strategy.

The growth component constructs two models, model one and model two, and it does this in parallel. Model one is constructed by simulating splitting <NUM> of the current node by adding a router module. The added router module is assigned to a new internal node as for the "split" situation of <FIG> described above. Model two is constructed by simulating increasing the depth of the incoming edge of the current node by adding <NUM> a transformer to that incoming edge.

Once the two models are constructed they are assessed by carrying out local optimization. Local optimization <NUM> of model one (or model two) comprises fixing the parameters of any previous part of the neural tree, computing a loss function describing the difference between the predicted labels given at the outputs of the leaf nodes of the models and the labels of the training examples, and adjusting the local parameters of the new modules according to gradient descent computed on the loss function.

The growth module then selects <NUM> between model one, or model two, or making no change. The selection is made using validation data, which is a sub-set of the training examples reserved for use in validation and which is not used for other parts of the training procedure. The validation data is processed using model one, model two and the existing neural tree with no change. The best performing option is selected which is the option giving predictions most similar to the labels of the validation data.

The neural tree is then updated <NUM> according to the selected option. For example, if model two is selected the neural tree is updated by increasing the depth of the incoming edge by adding a transformer with parameter values as computed from the local optimization process. If model one is selected the neural tree is updated by splitting the current node by adding a router module with parameters as computed from the local optimization process.

The growth module decides at check point <NUM> whether to end the growth process or not. The growth process ends if a threshold number of nodes is reached, or if convergence is reached or according to a combination of these and/or other factors. When the growth process ends the neural tree is stored <NUM> in the form of the topology (including the number of nodes, the modules and the arrangement of the nodes and modules) and parameter values of the modules. The stored neural tree <NUM> is then suitable for deployment and can be sent to other devices and/or the cloud. If the growth process is to continue the process returns to operation <NUM> of <FIG>.

The rationale for evaluating the two models in the process of <FIG> is to give the process freedom to choose the most effective option between "going deeper" or partitioning the data space. Splitting a node is equivalent to a soft partitioning of the feature space of incoming data, and gives birth to two new leaf nodes (left and right children solvers). In this case, the added transformer modules on the two branches are identity function. Adding depth on the other hand does not change the number of leaf nodes, but instead seeks to learn richer representation via an extra nonlinear transformation, and replaces the old solver with a new one.

Using local optimization in the process of <FIG> saves time, memory and compute. Gradients only need to be computed for the parameters of the newly added peripheral parts of the architecture, reducing the amount of time and computation needed. Forward activations prior to the new parts do not need to be stored in memory, saving space.

More detail about the refinement process is now given with reference to <FIG>. Component <NUM> of <FIG> carries out the refinement process. A stored neural tree is accessed <NUM> such as a neural tree grown by the process of <FIG>. A global optimization process <NUM> of parameters of all modules of the neural tree is then carried out and this results in a pruned neural tree <NUM> since redundant branches of the neural tree are effectively removed as a result of the global optimization as indicated in <FIG>. Global optimization fine-tunes the parameters of all modules in the graph, jointly optimizing the hierarchical grouping of data to paths on the tree and the associated expert neural networks. The fine-tuning phase corrects suboptimal decision made during the local optimization of the growth phase, and empirically improves the generalization error.

<FIG> shows a neural tree <NUM> output from the growth process. It processes images of objects, such as an image of a car in the <FIG> example, in order to compute a prediction such as whether the object is liked by people in a particular age bracket. During the growth process the internal nodes and modules of the neural tree are grown and their parameters locally optimized. After global optimization the neural tree <NUM> becomes the neural tree <NUM> and it is seen that a branch of the neural tree <NUM> has been remove. The global optimization process calculated values of the parameters of the modules such that the branch <NUM> became redundant as is effectively pruned.

It is found in some cases that the neural tree is interpretable to some extent by humans which is not the case if only a neural network were used for the same task. In the example of <FIG>, neural tree <NUM>, it is found by inspection that the first level internal nodes act to divide the images into those depicting man-made objects along branch <NUM> and those depicting natural objects along branch <NUM>. It is found that the branch <NUM> for man-made objects divides into images depicting (cars and trucks) along branch <NUM>, and images depicting (planes and ships) along branch <NUM>. Thus it is possible to interpret the path through the neural tree from the root node to a given leaf node and this enables humans to have some understanding of how a prediction computed by the neural tree is arrived at. In contrast, neural networks do not have this ability.

Once a neural tree is deployed it is used for test time processing as now described with reference to <FIG>.

An input example is received <NUM> at the root node. The nature of the input example depends on the application domain. A non-exhaustive list of input examples is: image, image feature map derived from an image, video, audio signal, text segment, phonemes from a speech recognition pre-processing system, skeletal data produced by a system which estimates skeletal positions of humans or animals from images, sensor data, or data derived from sensor data. The input example has been processed by any transformer on the incoming edge to the root node. In an example, the transformer is a filter which acts to remove noise from the input example.

The transformed input example is processed <NUM> using the router module of the root node and as a result the left or right child node of the root node is selected. That is, a child of the current node is selected <NUM> using the router decision. The root node output is passed <NUM> to the selected child node via an outgoing edge of the root node. The output is transformed <NUM> using any transformer module(s) on the outgoing edge and a check is made <NUM> to see if a solver has been reached at a leaf node. If so, a prediction <NUM> is computed <NUM> by the solver <NUM> using the data input to the solver from the incoming edge. If no solver is reached at check <NUM> the results of the transformation are processed <NUM> by the router module at the current node, which is an internal node. The router module at the current node makes a decision <NUM> which is used to select a child of the router and the process repeats from operation <NUM>.

The test time inference process of <FIG> is efficient to compute as compared with a neural network and yet still gives highly accurate results. The reason for the efficiency is that the inference is computed along a path through the tree rather than for all nodes of the neural tree. In comparison, inference with a neural network involves making computations for all nodes of the neural network. The reason for the accuracy is that the modules associated with the edges and nodes have parameters with values that are learnt in training in a similar way to parameters of a neural network which are learnt during training. Because the modules along a path from the root node to a leaf node together form a neural network, the processing at test time inference gives highly accurate results. Because the test time inference process is efficient to compute it is practical to deploy and use neural trees on resource constrained devices such as smart phones, wearable computers and embedded devices.

Because a neural tree is used as opposed to a neural network the predictions computed by the neural tree are interpretable. This is beneficial where the technology is used to make automated decisions and it is desired to provide human users with a reasonable explanation of the logic involved in making the automated decision.

A probabilistic interpretation of the neural trees described in this document is now given and the neural trees are referred to as adaptive neural trees. An adaptive neural tree, ANT ( <MAT>) models the conditional distribution p(y|x) as a hierarchical mixture of experts (HMEs) each of which corresponds to a particular root-to-leaf path in the tree. For input x, an ANT stochastically selects a path down to one of the leaf nodes l ∈ leaves(<IMG>), and generates a value for y from the corresponding neural network. Supposing we have L leaf nodes, the full predictive distribution is given by <MAT>
where z ∈ {<NUM>,<NUM>} L is a L dimensional binary latent variable such that <MAT>, which describes the choice of leaf node (e.g. zl = <NUM> means that leaf <NUM> is used). Here θ, ψ, φ summarise the parameters of router, transformer and solver modules in the tree. The mixing coefficient <MAT> quantifies the probability that x is assigned to leaf <NUM> and is given by a product of decision probabilities over all router modules on the unique path <IMG> from the root to leaf node l: <MAT> where l ↙ j is a binary relation and is only true if leaf l is in the left-subtree of internal node j, and <MAT> is the feature representation of x at node j. Suppose <MAT> denotes the ordered set of transformer modules on the path from root to node j, the feature vector <MAT> is given by <MAT>.

On the other hand, the leaf-specific conditional distribution <MAT> in eq. (<NUM>) yields an estimate for the distribution over target y for the chosen expert leaf node l and is given by <MAT>.

Two schemes of inference are considered, based on a trade-off between accuracy and computation. Firstly, the full predictive distribution given in eq. (<NUM>) is used as the estimate for the target conditional distribution p(y|x). However, averaging the distributions over all the leaves, weighted by their respective path probabilities, involves computing all operations at all of the nodes and edges of the tree, which makes inference expensive for a large ANT. We therefore consider a second scheme which uses the predictive distribution at the leaf node chosen by greedily traversing the tree in the directions of highest confidence of the routers. This approximation constrains computations to a single path, allowing for more memory- and time-efficient inference.

Training of an ANT proceeds in two stages: <NUM>) growth phase during which the model progressively increases its complexity based on local optimization, and <NUM>) fine-tuning phase which refines the parameters of the model discovered in the first phase based on global optimization.

In various examples, for both phases, the negative log-likelihood (NLL) is used as the common objective function, which is given by <MAT>.

Where X = {x<NUM>,. , x(N)}, Y = {y<NUM>,. , y(N)} denote the training inputs and targets. As all component modules (routers, transformers and solvers) are differentiable with respect to their parameters Θ = (θ, ψ, φ), it is possible to use gradient-based optimization. Given an ANT with fixed topology, backpropagation is used for gradient computation and gradient descent is used to minimize the NLL for learning the parameters of the modules.

Various examples of neural trees according to the present technology are now described together with empirical data obtained from testing the neural trees.

Compact neural trees with high performance are discovered on the MNIST (LeCun et al. , <NUM>) and CIFAR-<NUM> (Krizhevsky & Hinton, <NUM>) datasets. The number of parameters in the router and transformer modules are balanced to be of the same order of magnitude to avoid favouring either partitioning the data or learning more expressive features.

Unless otherwise stated, the following training protocol is used in the empirical testing: (<NUM>) optimize parameters using Adam (Kingma & Ba, <NUM>) with initial learning rate of <NUM>-<NUM> and " = [<NUM>, <NUM>], with minibatches of size <NUM>; (<NUM>) during the growth phase, employ early stopping with a patience of <NUM>, that is, training is stopped after <NUM> epochs of no progress on the validation set; (<NUM>) during the fine-tuning phase, train for <NUM> epochs, decreasing the learning rate by a factor of <NUM> after <NUM> and <NUM> epochs. For both MNIST and CIFAR-<NUM>, hold out <NUM>% of training images as a validation set. The best model is selected based on the validation accuracy over the course of ANT training, spanning both the growth phase and the fine tuning step, and its accuracy on the testing set is reported. The hyperparameters are also selected on the validation performance, but not the test set.

For each ANT, classification is performed in two ways: using the full predictive distribution (eq. (<NUM>)) and a single greedily-selected leaf node.

Regarding the MNIST digit classification task, the dataset consists of <NUM>, <NUM> train and <NUM>, <NUM> test examples, all of which are <NUM> × <NUM> images of digits from <NUM> to <NUM> (<NUM> classes). The data set is pre-processed by subtracting the mean, but no data augmentation is used.

ANTs are trained with a range of primitive modules and compared against relevant neural network and random forest (RF) models. For simplicity, consider primitive modules based on three types of neural network layers: convolutional, global-average-pooling (GAP) and fully-connected (FC). Solver modules are fixed as linear classifiers (LC) with a softmax output. Router modules are binary classifiers with a sigmoid output. All convolutional and FC layer are followed by ReLU, except in the last layers of solvers and routers. Also apply <NUM> × <NUM> max-pooling to feature maps after every two transformer modules.

The primitive modules used for the MNIST digit classification task and for the CIFAR10 task are set out in the table below. Row one of the table indicates that for the model called ANT-MNIST-A the routers comprise a single convolutional neural network layer using a 2D convolution with <NUM> kernels of spatial size <NUM> by <NUM>, with global-average pooling (GAP) and with two fully connected layers (FC). The model called ANT-MNIST-A has transformers with a single convolutional neural network layer having a 2D convolution with <NUM> kernels of spatial size <NUM> by <NUM>. The model called ANT-MNIST-A has solvers with a linear classifier (LC) and the frequency at which two by two max-pooling is applied is set to two.

Row two of the table indicates similar information regarding the primitive modules used for the ANT-MNIST-B model and so on for the other rows of the table.

It is found that ANT-MNIST-A outperforms the state-of-the-art RF methods in accuracy. This performance is attained despite the use of a single tree, while RF methods operate with ensembles of classifiers. Previous work uses a pre-specified architecture. ANT-MNIST-A on the other hand is automatically constructed from primitive modules, and displays an improvement over previous work in terms of accuracy and number of parameters. In addition, reducing the size of convolution kernels (ANT-MNIST-B) reduces the total number of parameters by <NUM>% and the path-wise average by almost <NUM>% while retaining performance.

Comparison is made against the LeNet-<NUM> CNN, comprised of the same types of operations as is used in the present technology's primitive module specifications (i.e. convolutional, max-pooling and FC layers). The network is trained with the same protocol as the fine-tuning phase of an ANT, and the error rate of <NUM>% (lower than the reported value of <NUM>%) was obtained on the test set. Both ANT-MNIST-A and ANT-MNIST-B attain better accuracy with a smaller number of parameters than LeNet-<NUM>, demonstrating again the potential of the proposed growth protocol for discovering compact models with high performance. Lastly, ANT-MNIST-C, with the simplest primitive modules, achieves an error rate of <NUM>% with single-path inference, which is significantly better than that of the linear classifier (<NUM>%), while engaging almost the same number of parameters (<NUM>, <NUM> vs. <NUM>, <NUM>) on average.

Tests also evaluate the ANTs performance on CIFAR-<NUM>, which consists of <NUM> × <NUM> coloured natural images drawn from <NUM> classes. The train and test sets contains <NUM>, <NUM> and <NUM>, <NUM> images. An augmentation scheme is used whereby images are zero-padded with <NUM> pixels on each side, randomly cropped and horizontally mirrored.

Variants of ANTs with different types of module are compared against modern NN models. Comparisons are limited to NNs of up to <NUM> layers with the same set of operations and linear structures. All-CNN is selected as the baseline which reports the lowest error among the comparison targets and is the closest in terms of constituent operations (convolutional, GAP and FC layers). For a fair comparison, training is done in the same experimental set-up as the fine-tuning phase of ANT training, and the new performance is reported. Batch normalization is applied after every convolutional layer both in ANT modules, and All- CNN, as it improved convergence and accuracy. It was found that the growth protocol discovers an architecture (ANTCIFAR10- A) which attains lower error than All-CNN while retaining a similar number of parameters in total, and <NUM>% less for path-wise inference. Simpler modules lead to more compact models (ANT-CIFAR10-B and C) with competitive performance with a marginal compromise in accuracy.

One strength of the methods described herein is the ability to adapt the model structure to the given availability of data and the complexity of the task. On the other hand, oversized models, trained in the standard way without regularization, are vulnerable to overfitting on small datasets. To confirm the benefits of the growth protocol, classification experiments are run on CIFAR-<NUM> and three variants of ANTs are trained, the baseline All-CNN and linear classifier on subsets of the dataset of varying size. Models are given data sets of size <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> and <NUM> (the full training set). The best model is picked based on the performance on the same validation set of <NUM> examples as before. As the dataset gets smaller, the margin between the test accuracy of the ANT models and All-CNN/linear classifier increases (up to <NUM>%). It can be observed that for different settings of primitive modules, the number of parameters generally increases as a function of the dataset size. All- CNN has a fixed number of parameters, consistently larger than the discovered ANTs, and suffers from overfitting, particularly on small datasets. The linear classifier, on the otherhand, underfits to the data. The methods of the present technology construct networks of adequate complexity, leading to better generalisation.

The proposed training procedure in the growth phase of ANTs is capable of discovering hierarchical structures in the data that are useful to the end task. Learned hierarchies often display strong specialisation of paths to certain classes or categories of data on both the MNIST and CIFAR-<NUM> datasets.

The global fine-tuning step improves the generalisation error. While the models initially undergo a steep drop in performance, they all consistently converge to higher test accuracy than the best value attained during the growth phase. This provides evidence that global optimisation remedies suboptimal decisions made during the locally optimised growth phase. For example, fine-tuning tends to polarize the decisions of routers, which occasionally leads to the pruning of some branches, and improves generalisation, displaying resolvement of suboptimal partitioning of data.

Various examples described herein comprise ANTs, a form of decision trees (DTs) which use neural networks in both its edges and nodes, combining the abilities of representation learning with hierarchical data partitioning. A training algorithm optimises both the parameters and architectures of ANTs through progressive growth, tuning them to the size and complexity of the training dataset.

<FIG> illustrates various components of an exemplary computing-based device <NUM> which are implemented as any form of a computing and/or electronic device, and in which embodiments of a predictor using at least one neural tree is implemented in some examples.

Computing-based device <NUM> comprises one or more processors <NUM> which are microprocessors, controllers or any other suitable type of processors for processing computer executable instructions to control the operation of the device in order to train neural trees and/or use neural trees for classification or regression tasks applied to input examples such as images or other types of input examples. In some examples, for example where a system on a chip architecture is used, the processors <NUM> include one or more fixed function blocks (also referred to as accelerators) which implement a part of the method of training a neural tree and/or computing predictions in hardware (rather than software or firmware). Platform software comprising an operating system <NUM> or any other suitable platform software is provided at the computing-based device to enable application software <NUM> to be executed on the device. A training logic <NUM> is arranged to train one or more neural trees. A data store <NUM> holds training examples, training objectives, parameter values, neural trees, or other data. A classification or regression logic <NUM> is arranged to use trained neural trees to carry out regression or classification tasks with respect to images or other examples.

The computer executable instructions are provided using any computer-readable media that is accessible by computing based device <NUM>. Computer-readable media includes, for example, computer storage media such as memory <NUM> and communications media. Computer storage media, such as memory <NUM>, includes volatile and non-volatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or the like. Computer storage media includes, but is not limited to, random access memory (RAM), read only memory (ROM), erasable programmable read only memory (EPROM), electronic erasable programmable read only memory (EEPROM), flash memory or other memory technology, compact disc read only memory (CD-ROM), digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other non-transmission medium that is used to store information for access by a computing device. In contrast, communication media embody computer readable instructions, data structures, program modules, or the like in a modulated data signal, such as a carrier wave, or other transport mechanism. As defined herein, computer storage media does not include communication media. Therefore, a computer storage medium should not be interpreted to be a propagating signal per se. Although the computer storage media (memory <NUM>) is shown within the computing-based device <NUM> it will be appreciated that the storage is, in some examples, distributed or located remotely and accessed via a network or other communication link (e.g. using communication interface <NUM>).

The computing-based device <NUM> also comprises an input/output controller comprising input interface <NUM> and output interface <NUM>. Output interface <NUM> is arranged to output display information to a display device <NUM> which may be separate from or integral to the computing-based device <NUM>. The display information may provide a graphical user interface. The input/output controller is also arranged to receive and process input from one or more devices, such as a user input device <NUM>, <NUM>, <NUM> (e.g. a mouse, keyboard, camera, microphone or other sensor) or capture device <NUM> such as a camera, microphone or other sensor. In some examples the user input device detects voice input, user gestures or other user actions and provides a natural user interface (NUI). This user input may be used to specify training objectives, set parameter values, input training data or for other purposes. In an embodiment the display device <NUM> also acts as the user input device if it is a touch sensitive display device. The input/output controller outputs data to devices other than the display device in some examples, e.g. a locally connected printing device.

Any of the input/output controller <NUM>, <NUM>, display device <NUM> and the user input device <NUM>, <NUM>, <NUM> may comprise NUI technology which enables a user to interact with the computing-based device in a natural manner, free from artificial constraints imposed by input devices such as mice, keyboards, remote controls and the like. Examples of NUI technology that are provided in some examples include but are not limited to those relying on voice and/or speech recognition, touch and/or stylus recognition (touch sensitive displays), gesture recognition both on screen and adjacent to the screen, air gestures, head and eye tracking, voice and speech, vision, touch, gestures, and machine intelligence. Other examples of NUI technology that are used in some examples include intention and goal understanding systems, motion gesture detection systems using depth cameras (such as stereoscopic camera systems, infrared camera systems, red green blue (rgb) camera systems and combinations of these), motion gesture detection using accelerometers/gyroscopes, facial recognition, three dimensional (3D) displays, head, eye and gaze tracking, immersive augmented reality and virtual reality systems and technologies for sensing brain activity using electric field sensing electrodes (electro encephalogram (EEG) and related methods).

Alternatively or in addition to the other examples described herein, examples include any combination of the following clauses:.

The term 'subset' is used herein to refer to a proper subset such that a subset of a set does not comprise all the elements of the set (i.e. at least one of the elements of the set is missing from the subset).

Claim 1:
A predictor (<NUM>) for predicting an outcome y given an example x, comprising:
a memory (<NUM>) which stores at least one example x for which an outcome y is not known;
the memory (<NUM>) storing at least one decision tree (<NUM>) comprising a plurality of nodes connected by edges, the nodes comprising a root node, internal nodes and leaf nodes;
wherein, individual ones of the nodes each have an assigned module, comprising parameterized, differentiable operations, such that for each of the internal nodes the module computes a binary outcome for selecting a child node of the internal node;
individual ones of the edges each have a transformer configured to compute a non-linear function of an example or a processed example reaching the edge from a parent node, and where a plurality of different transformers are used;
a processor (<NUM>) configured to compute the prediction y by processing the example x using a plurality of the differentiable operations and transformers selected according to a path through the tree from the root node to a leaf node;
wherein:
the predictor is used for medical image analysis; and the outcome is a class label and the example is a voxel of a medical image.