BACKGROUND

This specification relates to neural network systems, particularly ones which are capable of rapid online learning.

Neural networks are machine learning models that employ one or more layers of units or nodes to predict an output for a received input. Some neural networks include one or more hidden layers in addition to an output layer. The output of each hidden layer is used as input to the next layer in the network, i.e., the next hidden layer or the output layer. Each layer of the network generates an output from a received input in accordance with current values of a respective set of parameters.

SUMMARY

This specification describes a neural network system implemented as computer programs on one or more computers in one or more locations that, in some implementations, is capable of rapid online learning, although the system can also be used where online learning is not needed. Unlike conventional neural networks in some implementations the nodes (also referred to as“neurons”) or units may define a linear network and the

representational power when approximating a complex function may come from additional “side” information used to gate the nodes. Further, in some implementations rather than the network as a whole predicting a target each neuron may probabilistically predict the target. That is, each neuron in the network generates a prediction of the target output for the network, i.e., rather than only the output layer of the network generating the prediction. Thus learning, e.g., the updating of weights, may be local to a neuron based on the prediction generated by that neuron, and can be potentially in parallel and/or distributed, rather than relying upon backpropagation.

Thus in one aspect a neural network system implemented on one or more computers may comprise one or more neural networks, each comprising a plurality of layers arranged in a hierarchy of layers, each layer having a plurality of nodes. An input to the neural network system is referred to as a“system input”, which is transmitted to each of the neural networks as an input. Each node in a layer may have an output, a plurality of inputs coupled to the outputs of some or all the nodes in a preceding (“lower”) layer in the hierarchy of layers, and a side gate coupled to the system input. Each node in the layer may be configured to combine the plurality of inputs according to a set of weights defined by the side information and to output a probability value representing the probability of a target data value for the neural network conditioned upon the side information. There may be a system output from one, or potentially more than one, of the nodes of an upper layer in the hierarchy of layers. That is, the prediction generated by one or more nodes in the highest layer of the hierarchy is the output of the neural network.

In particular, in some cases, the system generates a respective probability distribution over possible values for each of multiple data values in an output of the system (an“output data sample”) and each neural network in the system generates the probability distribution for a respective one of the data values. For example, if the output of the system is an image, each neural network can generate a probability distribution over possible color values for a respective pixel of the image or for a respective color channel of a respective pixel of the image.

In some implementations each of the plurality of inputs represents a probability value and each node is configured to combine the plurality of inputs according to a geometric mixture model. In this way the nodes may work together so that nodes in one layer can improve the predictions of nodes in a previous layer rather than acting as a non-linear feature extractor.

Such a geometric mixture model may involve each node applying a non-linear function to each of the plurality of inputs before they are combined, and then applying an inverse of the non-linear function to the weighted combination before providing the node output. Thus unlike conventional neurons the nodes may implement an overall linear network, with richness of representations coming from the side gating. The non-linear function may comprise a logit function and the inverse non-linear function may comprise a sigmoid function.

The side gate of each node may be configured to apply a respective context function to the side information to determine a context value. The node may then select a set of weights dependent upon the context value. For example, the node may select a row of weights from a weight matrix for the node based upon the context value. The context function may partition the side information (that is, the space of side information) into two or more regions either linearly or according to some complex boundary which may be defined by a kernel or map, which may be learned. In general the different nodes may have different context functions; these different functions may have the same form and different parameterization. The context functions may define regions or ranges, which accumulate across nodes, over which the system learns to define the output value.

The neural network may have a base layer of nodes defining base probability values for input to the nodes of the first layer in the hierarchy. The base probability values may, for example, be fixed or only dependent on the side information. This base layer may effectively be used to initialize the network. Alternatively, the base layer may be conditioned on different information than the gated linear layers in the network. For example, in an image generation task, the base layer for a network assigned to a particular pixel may be

conditioned on features of color values already generated for earlier pixels in the image.

In some implementations the side information, and system output, may each comprise a sequence of data values, for example a time sequence.

The system may include a controller to implement an online training procedure in which weights of the set of weights are adjusted during output of the sequence of data values in response to a loss dependent upon an observed data value for each step in the sequence of data values. The update may depend on the gradient of a loss, which may depend upon the observed data value, a predicted probability of the observed value, and the side value, each for a step in the sequence. For example, the loss may be proportional to the logarithm of the probability of the observed data value according to the probability distribution defined by the node probability output. The loss and the training may be local, in that the loss used to update the weights of a given node may depend only on the probability generated by a given node, the weights for the given node, and observed value for the target. Any of a range of online convex programming techniques may be employed, for example algorithms of the“no- regret” type. One technique which may be employed for updating the weights is Online Gradient Ascent/Descent (Zinkevich, 2003).

During training, whether or not online, the system may treat the nodes as an ensemble of models, more particularly a sequence of an ensemble of models. These may be weighted using switching weights so that as the model leams the better models or nodes are given relatively higher weights. This can help to ensure that at each step of a learning sequence the more accurate predictions are relied upon most, which can thus increase learning speed and output accuracy.

Implementations of the system have many applications. In broad terms the system can be used to determine a probability density function, for example for a sequence of data items. The sequence of data items may represent, for example, a still or moving image, in which case values of the data may represent pixel values; or sound data, for example amplitude values of an audio waveform; or text data, for example a text string or other word representation; or object position/state/action data, for example for a reinforcement learning system; or other data, for example atomic position data for a molecule.

The system may be used directly as a generative model, for example to generate examples conditioned upon the side information. Alternatively, it may be used to score the quality of already generated examples, i.e., in terms of how well the examples match the training data.

Alternatively it may be employed as a classifier, to produce a probability conditional upon a side information input, for example an image. For example, the neural network system may be used to classify images (e.g. of a real-world of simulated environment) into one of a pre-determined plurality of classes.

Alternatively, the neural network system may be used for reinforcement learning, for example to generate control data for controlling an agent (e.g. a robot) moving in a real- world or simulated environment, or data predicting a future image or video sequence seen by a real or virtual camera associated with a physical object or agent in a simulated or real-world environment. In reinforcement learning the side information may include one or more previous image or video frames seen by the camera. The learned probability density may be used directly for probabilistic planning and/or state space exploration in a simulated or real- world environment at least part of which is imaged by the camera (a“visual environment”).

Some example implementations are described using binary data. That is, the claimed “probability outputs” are single probability values that represent the likelihood that the value of the corresponding data sample is a particular one of the two possible values. However examples of the system may be used with continuous valued data, for example by

thresholding. More generally the examples described using a binary distribution may be extended to a binomial distribution for multi-bit binary values, or even to continuous data, for example based upon Gaussian distributions.

The subject matter described in this specification can be implemented in particular embodiments so as to realize one or more of the following advantages. The described systems and methods can leam online, that is the training process can be performed while generating a sequence of output data values, with the output data values being successively better attempts to perform the desired computational task. The learning can be very fast, that is requiring fewer processing power and less training data than other approaches.

Accordingly, the local learning can be performed on a mobile device or other resource- constrained computing environment rather than needing to train the system using a large amount of computing resources, e.g., in a data center. The learning of weights converges under a wide range of conditions and the system can thus leam from sub-optimal training data such as data which includes correlated examples. Furthermore, in contrast to many neural network training techniques, given a sufficiently large network size the convergence is guaranteed to be to state of the neural network system which performs any computational task defined by a continuous density function, to an arbitrary level of accuracy. Learning, that is updating the weights, can be local and thus there is no need to communicate between neurons when updating. This facilitates a parallel, distributed implementation of the system. The weight updating is also computationally efficient and easily implemented on a GPU (Graphics Processing Unit) or other special-purpose hardware. Additionally, the gated linear network itself may be particularly suited to being implemented in special-purpose hardware, e.g., hardware that performs matrix multiplications in hardware, e.g., a Tensor Processing Unit (TPU) or another hardware machine learning accelerator.

BRIEF DESCRIPTION OF THE DRAWINGS

Examples of the present disclosure will now be described for the sake of example only with reference to the following figures, in which:

Fig. 1 illustrates a function used by a neuron in a neural network system according to the present disclosure; Fig. 2 illustrates the operation of a certain neuron of a gated linear network included in a neural network system according to the present disclosure, specifically the k- th neuron in layer i of the gated linear network, where i is greater than zero;

Fig. 3 is a flow diagram of the method carried out by the neuron of Fig. 2; and Fig. 4 illustrates the bottom 3 layers of a gated linear network according to the present disclosure, comprising multiple layers of neurons as shown in Fig. 2.

DETAILED DESCRIPTION OF THE EXAMPLES

Firstly we will define some notation. We then review the concept of geometric mixing, an adaptive online ensemble technique from the output of multiple models. We then describe the properties of a logarithmic loss function. We then describe the example of the disclosure.

1. Notation

Let A _d = {x e [0,l] ^d : ||x|li = 1} be the d dimensional probability simplex embedded in M ^{d + 1} and Έ = {0,1} be the set of binary elements. The indicator function for set A is I4 and satisfies I^( ) = 1 if x E A and (x) = 0 otherwise. For predicate P we also write P[R], which evaluates to 1 if P is true and 0 otherwise. The scalar element located at position (i,j) of a matrix A is Ai _j , with the z-th row and j- th column denoted by Ai _* and A _*j respectively. For functions /: M ® M and vectors x we adopt the convention of writing /(x) £ K ^d for the coordinate-wise image of x under / so that f(x) = (f(xi ),. . . ,f(xd)).

If p, q E [0, 1], then D(p, q) = p log p/q + (1 ^~ p) log(l ^~ p)/(l ^~ q) is the Kullback- Leibler (KL) divergence between Bernoulli distributions with parameters p and q

respectively. Let X be a finite, non-empty set of symbols, which we call the alphabet. A string of length n over X is a finite sequence x _/.« = X1X2 ... x _n E X ⁿ with x _t EX for all t. For t < n we introduce the shorthands x< _t = xi.-t i and x _£t = x _1:t · The string of length zero is e and the set of all finite strings is X ^* = { e } U U^X ¹ . The concatenation of two strings s, r EX * is denoted by sr.

A sequential, probabilistic model p is a probability mass function p: X ^* ® [0,1], satisfying the constraint that p(x _1:n ) = R( ^c i _·.h U) f° ^{r a} ll ⁿ EN ^x i- _.n G X”, with p(e) =

1. Under this definition, the conditional probability of a symbol x _n given previous data x< _n is defined as p(x, _< \ x< _n ) = p(xi.-n)/p(x<n) provided p(x< _n ) > 0, with the familiar chain rules p(xi. _n ) applying as usual.

2. Geometric mixing

Given m sequential, probabilistic, binary models pi, , pm, geometric mixing provides a principled way of combining the m associated conditional probability distributions into a single conditional probability distribution, giving rise to a probability measure on binary sequences that has a number of desirable properties. Let x _t E {0, 1} denote a Boolean target at time t. Furthermore, let pt = ( pi(xt = l\x<t), . . . , pm(x _t = l\x< _t ) ). Given a convex set W c and a parameter vector w E W, the Geometric Mixture is defined by: with GEO _w (x _t = 0; p _t )=l - GEO _w (x _t = 1 ; p _t ).

Setting Wi = 1/m for i E [1, m] is equivalent to taking the geometric mean of the m input probabilities. As illustrated in Fig. 1, higher absolute values of vvv translate into an increased belief in the z-th model prediction; for negative values of wi, the prediction needs to be reversed. If w = 0 then GEO _w (x _t = 1; p _t )= 1/2; and in the case where wi = 0 for i E S where S is a proper subset of [1, m], the contributions of the models in S are essentially ignored (taking 0° to be 1). Due to the product formulation, every model also has“the right of veto”, in the sense that a single pu close to 0 coupled with a uv > 0 drives GEO _w (x _t =

1; p _t ) close to zero. These properties are graphically depicted in Fig. 1.

Via simple algebraic manipulation, one can also express Eqn. (1) as:

GEO _w (x _t = 1; p _t ) = a(w. logit(p _t )), (2)

where s(c) = - -— denotes the sigmoid function, and logit(x) = log(x/(l - xj) is its

inverse. This form is well suited for numerical implementation. Furthermore, the property of having an input non-linearity that is the inverse of the output non-linearity means that a linear network is obtained when layers of geometric mixers are stacked on top of each other. 3. Logarithmic loss

We assume a standard online learning setting, whereby at each round t £ N a predictor outputs a binary distribution q _t : B [0, 1], with the environment responding with an observation x _t £ B . The predictor then suffers the logarithmic loss

before moving onto round t + 1. The loss will be close to 0 when the predictor assigns high probability to xt, and large when low probability is assigned to xt. In the extreme cases, a zero loss is obtained when qt(xt) = 1, and an infinite loss is suffered when q _t (x _t ) = 0. In the case of geometric mixing, which depends on both the m dimensional input predictions p _t and the parameter vector w £ W, we abbreviate the loss by defining

The properties of i ^E0 (w)make it straightforward to minimize it by adapting w at the end of each round, such as by Online Gradient Descent. Alternatively, second order techniques may be used, such as Online Newton Step (Hazan et ah, 2007) and its sketched variants

4. A neuron of the example

Fig. 2 illustrates the operation of a single neuron (or“node”) 200 of the example of a neural network system according to the present disclosure. Fig. 3 illustrates the steps of a method 300 performed by the neuron 200. The neuron 200 is part of a gated linear network 400, part of which is shown in Fig. 4. The gated linear network 400 is one of one or more gated linear networks in a neural network system according to the present disclosure. Each gated linear network is used for generating at least one data value, such that the set of one or more gated linear networks generate respective data values.

As described in more detail below, the gated linear network 400 contains layers L + 1 layers indexed by an integer index i E {0, . . . , L}, with W models in each layer labelled by the integer variable k. As described below, one of these models may be a bias model, and, except for i=0, the other K,- 1 of these models are neurons having the same general form as neuron 200. Layers are“gated linear layers”, which form a hierarchy of layers, in which layer i is“higher” than layer i-l. Fig. 2 illustrates a neuron 200 which is the k- th neuron in a gated linear layer i of the gated linear network 400, where i is greater than zero.

The neuron 200 operates as a gated geometric mixer which combines a contextual gating procedure with geometric mixing. Here, contextual gating has the intuitive meaning of mapping particular examples to particular sets of weights.

The neuron 200 comprises an input unit 201 which (in step 301) receives / ,_i inputs which are respective outputs of the K _t _ models in the row below (i.e. the row i-l). These are denoted P _(i-i) o, . There may be denoted as the vector p.

The neuron 200 further comprises a side gate 202 which (in step 302) receives side information z.

In step 303, the side gate 202 of neuron 200 applies a respective context function (described below) to the side information to derive a context value c _ik (z). A weighting unit 203 is configured to select a set of weights W _ikc ^ dependent upon the context value c _ik (z). This is illustrated schematically in Fig. 2 as the weighting unit 203 selecting the set of weights W i _{ke lk(z)} from a plurality of sets of weights which are illustrated as the respective rows 204 of a table. The input unit 201 is configured to generate from the vector p, the vector logit(p) , where logit (x) denotes log(x/l-x). The weighting unit 203 is configured to generate an initial output as W _ikClkiz) x logit{p).

In step 304, an output unit 205 of the neuron 200 generates a node probability output Pi _k — a{Wi _kcik(z) ^x l°git(p)) which is a probability distribution over possible values for the data value corresponding to the gated linear network of which the neuron 200 is a component.

In step 305, the output unit 205 outputs the node probability output ^p i _k for the corresponding data value.

To express this in more detail, associated with each neuron 200 is a respective context function c\ Z ® C where Z is the set of possible side information and C = (0, ... , k— 1} for some k EN is the context space. Given a convex set W c I ^d , each neuron 200 is parametrized by a respective matrix

with each row vector £ W for 0 < i < k. The context function c is responsible for mapping a given piece of side information z _t £ Z to a particular row w _{C(Z )} of W, which we then use with standard geometric mixing. More formally, we define the gated geometric mixture prediction as

with GEOw(x _t = 0; p _t , z _t ) = 1— GEO^(x _t = 1; p _t , z _t ). Once again we have the following equivalent form

The key idea is that the neuron 200 can specialize its weighting of the input predictions based on some property of the side information z _t . The side information can be arbitrary, for example it may comprise one or more additional input features. Alternatively or additionally, it may be a function of p _t . The choice of context function is informative in the sense that it simplifies the probability combination task.

5. Context functions

Here we introduce several classes of general purpose context functions. All of these context functions take the form of an indicator function I _s (z): Z ® Έ on a particular choice of set S <X z, with 1 _s (z) : = 1 if z ES and 0 otherwise. In variants of the example, other context functions can be used, such as one which is selected in view of the task the trained network is to perform.

A. Half-space contexts This choice of context function is useful for real-valued side information. Given a normal v £ and an offset b £ M, consider the associated affine hyperplane {x x v = b}. This divides M ^d in two, giving rise to two half-spaces, one of which we denote H _{v b} = (x £ x v > b}. The associated half-space context is then given by l _Hv,b (z).

B. Skip-gram contexts The following type of context function is useful when we have multi-dimensional binary side information and can expect single components of Z to be informative. If Z = Έ ^ά , given an index i E[l, d] , a skip-gram context is given by the function I _s. (z) where 5); = {z E Z: z _i= l}. One can also naturally extend this notion to categorical multi-dimensional side information or real valued side information by using thresholding.

6. Context function composition

Richer notions of context can be created from composition. In particular, any finite set of d context functions {c . Z ® C f ₌₁ with associated context spaces C _d can be composed into a single higher order context function c\ Z ® C , where C = {0,1, ... ,— 1 + = ₁ \Ci \}

by defining

For example, we can combine four different skip-gram contexts into a single context function with a context space containing 16 elements. The combined context function partitions the side information based on the values of the four different binary components of the side information.

7. Gated Linear Network

We now describe a neural network which is an example of the present disclosure. The neural network is termed a gated linear network (GLN), and is one network out of one or more networks which compose a neural network system according to the present disclosure.

It is a feed-forward network composed of a plurality (hierarchy) of gated linear layers of gated geometric mixing neurons 200. The GLN also includes a base layer (layer 0, that is i=0). Each neuron 200 in a given gated linear layer outputs a gated geometric mixture over the predictions from the previous layer, with the final layer typically consisting of just a single neuron that determines the output of the entire network.

Fig. 4 illustrates the bottom three layers (that is layer 0, layer 1 and layer 2) in the gated linear network 400. Each of the layers 1 and 2 is a gated linear layer. The input to the gated linear network (the“system input”) is denoted z.

The zero-th layer (also called here the“base layer”, or“layer 0”) includes a bias unit 401 which generates an output Poo (typically dependent upon z), and Ko-l base models 402, which each perform different functions of the input z to generate respective outputs Roi, P02, · · The respective functions performed by the base models 402 are not varied during the training procedure.

Layer 1 of the gated linear network 400 comprises a bias unit 403, which generates an output P10 (typically dependent upon z). It further comprises Ki-l neurons each of which has the structure of the neuron 200 of Fig. 2. The side gates 202 of these neurons are denoted 404 in Fig. 4, and the units 201, 203, 205 of the neuron 200 are denoted as a unit 405 in Fig. 4. The Ki-l side gates 404 receive the side information z and produce the respective context values cn, C12, ...c _{1 (/<} ^, _{l -i )} · The respective units 405 use this, and the outputs of the bias unit 401 and all the base models 402, to generate respective outputs P11, P12,...., .

Layer 2 of the gated linear network 400 comprises a bias unit 406, which generates an output P20. It further comprises K2-I neurons each of which has the structure of the neuron 200 of Fig. 2. The side gates 202 of these neurons are denoted 407 in Fig. 4, and the units 201, 203, 205 of the neuron 200 are denoted as a unit 408 in Fig. 4. The K2-I side gates 407 receive the side information z and produce the respective context values C21, C22, .. . C ₂ (K ₂ - 1 ₎ · The respective units 408 use this, and the outputs of the bias unit 403 and all the units 405, to generate respective outputs P21, P22,...., R2 ₍ k _2-ΐ)

Note that the gated linear network contains higher layers (i.e. gated linear layers above 2) which are omitted from Fig. 4 for simplicity. Each of these layers (except the top one) comprises a bias unit, and one or more neurons having the structure of the neuron 200, each of those neurons receiving the input signal z to their respective side gates, and the outputs of the bias unit and neurons of the layer immediately below to their respective input unit.

In the top layer (not shown in Fig. 4), there is only a single neuron, having the structure of the neuron 200 of Fig. 2. This neuron receives the input signal z to its side gate, and the outputs of the bias unit and all the neurons of the layer immediately below to its input unit. The neuron outputs the final output of the gated linear network.

We now express this concept mathematically. Once again let Z denote the set of possible side information and C c N be a finite set called the context space. A GLN is a network of sequential, probabilistic models organized in L + 1 layers indexed by i G {0, ,

L}, with Ki models (neurons) in each layer. Models are indexed by their position in the network when laid out on a grid; for example, pik will refer to the k- th model in the z-th layer. The zeroth layer of the network is called the base layer and is constructed from Ko probabilistic base models {po _k } _k =o °f the form given in the above“notation” section. Any base models may be used in the example network, since each of their predictions may be assumed to be a function of the given side information and all previously seen examples.

The non-zero layers are composed of a bias unit 403, 406 and gated geometric mixing neurons 200 as shown in Fig. 2. Associated to each of these will be a fixed context function c _{ik \} Z ® C that determines the behavior of the gating. In addition to the context function, for each context c £ C and each neuron (i, k) there is an associated weight vector w _ikc £

M^- ¹ which is used to geometrically mix the inputs. Each bias unit 403, 406 a non-adaptive bias model on every layer, which will be denoted by Pi ₀ for each layer z. Each of these bias models corresponds to a Bernoulli Process with parameter b. These bias models play a similar role to the bias inputs in MLPs.

Given a z £ Z, a weight vector for each neuron is determined by evaluating its associated context function. The output of each neuron is described inductively in terms of the outputs of the previous layer. To simplify the notation, we assume an implicit dependence on x _<t and let pi _j (z) = p _Lj (x _t = 1 |x _<t ; z) denote the output of the j- th neuron in the z-th layer, and R _ί ki_ ₁ O)) the output of the z-th layer. The bias output for each layer is defined to be p _i0 (z) = b for all z £ Z, for all 0 < i < L + 1, where b £ (0,l)\{l/2). The constraint that b is not equal to one half is made to ensure that the partial derivative of the loss with respect to the bias weight is not zero under geometric mixing.

From here onwards we adopt the convention of setting b = e/(e + 1) so that logit( ) = 1.

For layers i > 1, the k- th node in the z-th layer receives as input the vector of dimension K i of predictions of the preceding layer, as shown in Fig. 4. The output of a single neuron 200 is the geometric mixture of the inputs with respect to a set of weights that depend on its context, namely

as illustrated by Figure 2. The output of layer i can be re-written in matrix form as

PiO) = (tT _i (z)/o^it(p _i-1 (z))) , (6) where 1 / _; (z) £ M ^KiCKi - ¹ is the matrix with A-th row equal to w _ik (z ) = w _ifcc.fe(-z) .

Iterating Eqn. (6) once gives

Since logit is the inverse of s, the z-th iteration of Eqn. (6) simplifies to

Pi (z) = s(I4/;(z)I4/;_ ₁ (z) ... W ₁ (z^logit (p _Q (z))) . (7)

Eqn. (7) shows the network behaves like a linear network, but with weight matrices that are data-dependent. Without the data dependent gating, the product of matrices would collapse to single linear mapping, giving the network no additional modeling power over a single neuron.

We now describe how the weights are leamt in the GLN, that is the neural network 400 of Fig. 4. While architecturally a GLN appears superficially similar to the well-known multilayer perception (MLP), what and how it leams is very different. The key difference is that every neuron in a GLN probabilistically predicts the target. This makes it possible to associate a loss function to each neuron. This loss function will be defined in terms of just the parameters of the neuron itself; thus, unlike backpropagation, learning will be local.

Furthermore, this loss function will be convex, which will allow us to avoid many of the difficulties associated with training typical deep architectures. For example, simple deterministic weight initializations may be performed, which aids the reproducibility of empirical results. In many situations, convergence to an optimal solution is guaranteed. The convexity also makes it possible to leam from correlated inputs in an online fashion without suffering significant degradations in performance. Furthermore, GLNs are extremely data efficient, and can produce state of the art results in a single pass through the data.

Each layer may be thought of as being responsible for trying to directly improve the predictions of the previous layer, rather than a form of implicit non-linear feature/filter construction as is the case with MLPs trained offline with back-propagation.

Optionally, the weights may be chosen satisfy the following mild technical constraints:

1 · ^w _kc o ^e [ ^a h] <= M for some real a < 0 and b > 0;

2. w _ikc £ S c where S is a compact, convex set such that D _k c S.

One natural way to simultaneously meet these constraints is to restrict each neuron’s con textual weight vectors to lie within some (scaled) hypercube: w _ikc £ [—b, b] ^K ^ , where b >

1.

To discuss the training during a period of time indexed by a time value t=l .... wc will use to denote the weight vector w _i;c at time t. Each neuron will be solving an online convex programming problem, so initialization of the weights is straightforward and is non- essential to the theoretical analysis. Choices found to work well in practice are zero initialization (i.e. i¾ iAl =0 for all i k and c), and geometric average initialization (i.e.

P

wi _k c = \ /Ki-i f° ^r all k, and c).

The zero initialization can be seen as a kind of sparsity prior, where each input model is considered a-priori to be unimportant, which has the effect of making the geometric mixture rapidly adapt to incorporate the predictions of the best performing models. The geometric average initialization forces the geometric mixer to (unsurprisingly) initially behave like a geometric average of its inputs, which makes sense if one believes that the predictions of each input model are reasonable.

As an alternative to the two above initializations, one could also use small random weights, as is typically done in MLPs. However, this choice makes little practical difference and has a negative impact on reproducibility. Learning in GLNs is straightforward in principle. As each neuron probabilistically predicts the target, the current input to any neuron is treated as a set of expert predictions and a single step of local online learning is performed using one of the no-regret methods discussed above in the section describing“logarithmic loss”. For example, online gradient descent (Martin Zinkevich. Online convex programming and generalized infinitesimal gradient as ccnt. In Machine Learning, Proceedings of the Twentieth International

Conference (ICML 2003), August 21-24, 2003, Washington, DC, USA, pages 928-936, 2003) with W _ik a hypercube. This allows the weight update for any neuron at layer i to be done in time complexity O(Ki-i), which permits the construction of large networks.

More precisely, let l _t ^lJ (w _i;c ) denote the loss of the j- th neuron in layer i. Using Eqn.

(3) we have

Now, for all i £[1, L]J £Ki , and for all c = d _j (zt), we set where P _ί is the projection operation onto hypercube [—b, b] ^{Ki 1} :

arg

P<M ⁼ y e [- The projection is efficiently implemented by clipping every component of w® to the interval

[ b, b] . The learning rate h _{ £ M ₊ can depend on time.

Some computational properties of Gated Linear Networks are now discussed.

Firstly, generating a prediction requires computing the contexts from the given side information for each neuron, and then performing L matrix-vector products. Under the assumption that multiplying a m ^x « by n x i pair of matrices takes O(mn) work, the total time complexity to generate a single prediction is 0 for the matrix-vector products, which in typical cases will dominate the overall runtime. Using online gradient descent just requires updating the rows of the weight matrices using Eqn. (9); this again takes time Secondly, when generating a prediction, parallelism can occur within a layer, similar to an MLP. The local training rule however enables all the neurons to be updated simultaneously (or more generally by a process in which multiple neurons, in the same or different levels, are updated at the same time), as they have no need to communicate information to each other. This compares favorably to back-propagation and significantly simplifies any possible distributed implementation. Furthermore, as the bulk of the computation is primarily matrix multiplication, large speedups can be obtained straightforwardly using GPUs (graphics processing units).

In the case where no online updating is desired (that is, the trained neural network is just used for prediction), prediction can be implemented efficiently depending on the exact shape of the network architecture. This can be done directly using Eqn. (7). Efficiency can be improved by solving a Matrix Chain Ordering problem to determine the optimal way to group the matrix multiplications.

Neural networks have long been known to be capable of approximating arbitrary continuous functions with almost any reasonable activation function. It can be shown that provided the contexts are chosen sufficiently richly, then GLNs also have the capacity to approximate large classes of functions. In fact, GLNs have almost arbitrary capacity. More than this, the capacity is effective in the sense that gradient descent will eventually find the approximation. In contrast, similar results for neural networks show the existence of a choice of weights for which the neural network will approximate some function, but do not show that gradient descent (or any other single algorithm) will converge to these weights. Although gated linear networks are not the only model with an effective capacity result, gated linear networks have some advantages over other architectures in the sense that they are

constructed from small pieces that are well-understood in isolation and the nature of the training rule eases the analysis relative to neural networks.

While GLNs can have almost arbitrary capacity in principle, large networks are susceptible to a form of the catch-up phenomenon. That is, during the initial stages of learning, neurons in the lower layers typically have better predictive performance than neurons in the higher layers. This problem can be addressed based on switching, which is a fixed share variant tailored to the logarithmic loss. The main idea is that as each neuron predicts the target, one can construct a switching ensemble across all neurons predictions. This guarantees that the predictions made by the ensemble are not much worse than the predictions made by the best sparsely changing sequence of neurons. We now describe this process in detail.

Let M = { pi _j : i E [i, L},j E [0, K _L — 1]) denote the model class consisting of all neurons that make up a particular GLN with L layers and K, neurons in each layer. Now for all n e hi, for all x _1:n e X ⁿ , consider a Bayesian (non-parametric) mixture that puts a prior W (-) over all sequences of neurons inside the index set J _n (M) = M ⁿ , namely

where is a prior, it is chosen to be non-negative and satisfy w _T (v _1:n ) = 1 for all n e hi. From the dominance property of Bayesian mixtures it immediately follows that for any v . _n e3 _n (M) we have

— logr(x _1:n ) < - log(w _T (vi _:n )vi _:n (x _1:n )) < - log(w _T (vi _:n )- log( i?i _:n (x _1:n )) (11)

Thus the regret Jl _n with respect to a sequence of models iq _:n is upper

bounded by -log(w _T (i7i _:n ). Putting a uniform prior over all neuron sequences would lead to a vacuous regret of n log( Jtf), so it is preferably to concentrate our prior mass on a smaller set of neuron sequences which are a-priori likely to predict well.

Empirically we found that when the number of training examples is small, neurons in the lower layers usually predict better than those in higher layers, but this reverses as more data becomes available. Viewing the sequence of best-predicting neurons over time as a string, we see that a run-length encoding gives rise to a highly compressed representation with a length linear in the number of times the best-predicting neuron changes. Run-length encoding can be implemented probabilistically by using an arithmetic encoder with the following recursively defined prior:

This assigns a high prior weight to model sequences which have short run length encodings.

When there exists a sequence of neurons with a small s(vf _n ) « n of switches that performs well, only logarithmic regret is suffered, and one can expect the switching ensemble to predict almost as well as if we knew what the best performing sparsely changing sequence of neurons was in advance.

A direct computation of Eqn. (10) would require a very large number of additions. An equivalent numerically robust formulation is described here, which incrementally maintains a weight vector that is used to compute a convex combination of model predictions at each time step.

Let e (0,1] denote the switching weight associated with the neuron (i, k) at time t. The weights will satisfy the invariant = 1, for all t. At each time step t the switching mixture outputs the conditional probability

with the weights defined, for all 1 £ i £ L and 0 < k < K _t by u = 1/\M\ and

This weight update can be straightforwardly implemented in 0\M\) time per step. To avoid numerical issues, the weights may be enforced to sum to 1 by explicitly dividing by after each weight update.

For a system of one or more computers to be configured to perform particular operations or actions means that the system has installed on it software, firmware, hardware, or a combination of them that in operation cause the system to perform the operations or actions. For one or more computer programs to be configured to perform particular operations or actions means that the one or more programs include instructions that, when executed by data processing apparatus, cause the apparatus to perform the operations or actions.

Embodiments of the subject matter and the functional operations described in this specification can be implemented in digital electronic circuitry, in tangibly-embodied computer software or firmware, in computer hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. Embodiments of the subject matter described in this specification can be implemented as one or more computer programs, i.e., one or more modules of computer program instructions encoded on a tangible non transitory program carrier for execution by, or to control the operation of, data processing apparatus. Alternatively or in addition, the program

instructions can be encoded on an artificially generated propagated signal, e.g., a machine- generated electrical, optical, or electromagnetic signal, that is generated to encode information for transmission to suitable receiver apparatus for execution by a data processing apparatus. The computer storage medium can be a machine -readable storage device, a machine-readable storage substrate, a random or serial access memory device, or a combination of one or more of them. The computer storage medium is not, however, a propagated signal.

The term“data processing apparatus” encompasses all kinds of apparatus, devices, and machines for processing data, including by way of example a programmable processor, a computer, or multiple processors or computers. The apparatus can include special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application specific integrated circuit). The apparatus can also include, in addition to hardware, code that creates an execution environment for the computer program in question, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, or a combination of one or more of them.

A computer program (which may also be referred to or described as a program, software, a software application, a module, a software module, a script, or code) can be written in any form of programming language, including compiled or interpreted languages, or declarative or procedural languages, and it can be deployed in any form, including as a stand alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. A computer program may, but need not, correspond to a file in a file system. A program can be stored in a portion of a file that holds other programs or data, e.g., one or more scripts stored in a markup language document, in a single file dedicated to the program in question, or in multiple coordinated files, e.g., files that store one or more modules, sub programs, or portions of code. A computer program can be deployed to be executed on one computer or on multiple computers that are located at one site or distributed across multiple sites and interconnected by a communication network.

As used in this specification, an“engine,” or“software engine,” refers to a software implemented input/output system that provides an output that is different from the input. An engine can be an encoded block of functionality, such as a library, a platform, a software development kit (“SDK”), or an object. Each engine can be implemented on any appropriate type of computing device, e.g., servers, mobile phones, tablet computers, notebook computers, music players, e-book readers, laptop or desktop computers, PDAs, smart phones, or other stationary or portable devices, that includes one or more processors and computer readable media. Additionally, two or more of the engines may be implemented on the same computing device, or on different computing devices.

The processes and logic flows described in this specification can be performed by one or more programmable computers executing one or more computer programs to perform functions by operating on input data and generating output. The processes and logic flows can also be performed by, and apparatus can also be implemented as, special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application specific integrated circuit). For example, the processes and logic flows can be performed by and apparatus can also be implemented as a graphics processing unit (GPU).

Computers suitable for the execution of a computer program include, by way of example, can be based on general or special purpose microprocessors or both, or any other kind of central processing unit. Generally, a central processing unit will receive instructions and data from a read only memory or a random access memory or both. The essential elements of a computer are a central processing unit for performing or executing instructions and one or more memory devices for storing instructions and data. Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto optical disks, or optical disks. However, a computer need not have such devices. Moreover, a computer can be embedded in another device, e.g., a mobile telephone, a personal digital assistant (PDA), a mobile audio or video player, a game console, a Global Positioning System (GPS) receiver, or a portable storage device, e.g., a universal serial bus (USB) flash drive, to name just a few.

Computer readable media suitable for storing computer program instructions and data include all forms of non-volatile memory, media and memory devices, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto optical disks; and CD ROM and DVD-ROM disks. The processor and the memory can be supplemented by, or incorporated in, special purpose logic circuitry.

To provide for interaction with a user, embodiments of the subject matter described in this specification can be implemented on a computer having a display device, e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor, for displaying information to the user and a keyboard and a pointing device, e.g., a mouse or a trackball, by which the user can provide input to the computer. Other kinds of devices can be used to provide for interaction with a user as well; for example, feedback provided to the user can be any form of sensory feedback, e.g., visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including acoustic, speech, or tactile input. In addition, a computer can interact with a user by sending documents to and receiving documents from a device that is used by the user; for example, by sending web pages to a web browser on a user’s client device in response to requests received from the web browser.

Embodiments of the subject mater described in this specification can be implemented in a computing system that includes a back end component, e.g., as a data server, or that includes a middleware component, e.g., an application server, or that includes a front end component, e.g., a client computer having a graphical user interface or a Web browser through which a user can interact with an implementation of the subject matter described in this specification, or any combination of one or more such back end, middleware, or front end components. The components of the system can be interconnected by any form or medium of digital data communication, e.g., a communication network. Examples of communication networks include a local area network (“LAN”) and a wide area network (“WAN”), e.g., the Internet.

The computing system can include clients and servers. A client and server are generally remote from each other and typically interact through a communication network. The relationship of client and server arises by virtue of computer programs running on the respective computers and having a client-server relationship to each other.

While this specification contains many specific implementation details, these should not be construed as limitations on the scope of any invention or of what may be claimed, but rather as descriptions of features that may be specific to particular embodiments of particular inventions. Certain features that are described in this specification in the context of separate embodiments can also be implemented in combination in a single embodiment. Conversely, various features that are described in the context of a single embodiment can also be implemented in multiple embodiments separately or in any suitable subcombination.

Moreover, although features may be described above as acting in certain combinations and even initially claimed as such, one or more features from a claimed combination can in some cases be excised from the combination, and the claimed combination may be directed to a subcombination or variation of a subcombination.

Similarly, while operations are depicted in the drawings in a particular order, this should not be understood as requiring that such operations be performed in the particular order shown or in sequential order, or that all illustrated operations be performed, to achieve desirable results. In certain circumstances, multitasking and parallel processing may be advantageous. Moreover, the separation of various system modules and components in the embodiments described above should not be understood as requiring such separation in all embodiments, and it should be understood that the described program components and systems can generally be integrated together in a single software product or packaged into multiple software products.

Particular embodiments of the subject matter have been described. Other

embodiments are within the scope of the following claims. For example, the actions recited in the claims can be performed in a different order and still achieve desirable results. As one example, the processes depicted in the accompanying figures do not necessarily require the particular order shown, or sequential order, to achieve desirable results. In certain implementations, multitasking and parallel processing may be advantageous.