Abstract:
We propose a modular architecture for lifelong learning of hierarchically structured tasks. Specifically, we prove that our architecture is theoretically able to learn tasks that can be solved by functions that are learnable given access to functions for other, previously learned tasks as subroutines. We empirically show that some tasks that we can learn in this way are not learned by standard training methods in practice; indeed, prior work suggests that some such tasks cannot be learned by any efficient method without the aid of the simpler tasks. We also consider methods for identifying the tasks automatically, without relying on explicitly given indicators.

heading: 1 INTRODUCTION
text: How can complex concepts be learned? Human experience suggests that hierarchical structure is key: the complex concepts we use are no more than simple combinations of slightly less complex concepts that we have already learned, and so on. This intuition suggests that the learning of complex concepts is most tractably approached in a setting where multiple tasks are present, where it is possible to leverage what was learned from one task in another. Lifelong learning (Silver et al., 2013; Chen & Liu, 2018) captures such a setting: we are presented with a sequence of learning tasks and wish to understand how to (selectively) transfer what was learned on previous tasks to novel tasks. We seek a method that we can analyze and prove leverages what it learns on simple tasks to efficiently learn complex tasks; in particular, tasks that could not be learned without the help provided by learning the simple tasks first.
In this work, we propose an architecture for addressing such problems based on creating new modules to represent the various tasks. Indeed, other modular approaches to lifelong learning (Yoon et al., 2018; Rusu et al., 2016) have been proposed previously. But, these works did not consider what we view as the main advantage of such architectures: their suitability for theoretical analysis. We prove that our architecture is capable of efficiently learning complex tasks by utilizing the functions learned to solve previous tasks as components in an algorithm for the more complex task. In addition to our analysis proving that the complex tasks may be learned, we also demonstrate that such an approach can learn functions that standard training methods fail to learn in practice, including some that are believed not to be learnable, even in principle (Klivans & Sherstov, 2009). We also consider methods for automatically identifying whether a learning task posed to the agent matches a previously learned task or is a novel task.
We note briefly that a few other works considered lifelong learning from a theoretical perspective. An early approach by Solomonoff (1989) did not seriously consider computational complexity aspects. Ruvolo & Eaton (2013) gave the first provable lifelong learning algorithm with such an analysis. But, the transfer of knowledge across tasks in their framework was limited to feature learning. In particular, they did not consider the kind of deep hierarchies of tasks that we seek to learn.

heading: 1.1 OVERVIEW OF THE ARCHITECTURE
text: The main technical novelty in our architecture over previous modular lifelong learners is that ours uses a particular type of internal data structure called sketches (Ghazi et al., 2019; Panigrahy, 2019). All such data, including inputs from the environment, outputs from a module for another task, decisions such as choosing an action to take, or even descriptions of the modules themselves, are
encoded as such sketches. Although sketches have a dense (vector) representation, they can also be interpreted as a kind of structured representation (Ghazi et al., 2019, Theorem 9) and are recursive; that is, they point to the previous modules/events that they arose from (Figure 1, right). However, in order to construct these sketches in Ghazi et al. (2019), the structure of the network is assumed to be given. No algorithms for constructing such a hierarchical network of modules from training data were known. In this work we show a method to construct such a hierarchical network from training data. We provide an architecture and algorithms for learning from a stream of training inputs that produces such a network of modules over time. This includes challenges of identifying each module, and discovering which other modules it depends on.
Our architecture can be viewed as a variant of the Transformer architecture (Radford et al., 2021; Shazeer et al., 2017), particularly the Switch Transformer (Fedus et al., 2021) in conjunction with the idea of Neural Memory (Wang et al., 2021). Instead of having a single feedforward layer, the Switch Transformer has an array of feedforward layers that an input can be routed to at each layer. Neural Memory on the other hand is a large table of values, and one or a few locations of the memory can be accessed at each layer of a deep network. In a sense the Switch Transfomer can be viewed as having a memory of possible feedforward layers (although they use very few) to read from. It is viewing the memory as holding “parts of a deep network” as opposed to data, although this difference between program and data is artificial: for example, embedding table entries can be viewed as “data” but are also used to alter the computation of the rest of the network, and in this sense act as a “program modifier”.
The key component of our architecture is a locality sensitive hash (LSH) table based memory (see Wang et al. (2021)) that holds sketches of data (such as inputs) and modules or programs (think of an encoding of a small deep network) that handles such sketches (Figure 1, left). The “operating system” of our architecture executes the basic loop of taking sketches (either from the environment or from internal modules) and routing/hashing them to the LSH table to execute the next module that processes these sketches. These modules produce new sketches that are fed back into the loop.
New modules (or concepts) are formed simply by instantiating a new hash bucket whenever a new frequently-occurring context arises, i.e. whenever several sketches hash to the same place; the context can be viewed as a function-pointer and the sketch can be viewed as arguments for a call to that function. Frequent subsets of sketches may be combined to produce compound sketches. Finally we include pointers among sketches based on co-occurrence and co-reference in the sketches themselves. These pointers form a knowledge graph: for example if the inputs are images of pairs of people where the pairs are drawn from some latent social network, then assuming sufficient sampling of the network, this network will arise as a subgraph of the graph given by these pointers. The main loop allows these pointers to be dereferenced by passing them through the memory table, so they indeed serve the intended purpose.
The main idea of the architecture is that all events produce sketches, which can intuitively be thought of as the “mind-state” of the system when that event occurs. The sketch-to-sketch similarity property (see below) combined with a similarity-preserving hash function ensures that similar sketches go
to the same hash bucket (Appendix B); thus the hash table can be viewed as a content addressed memory. See Figure 1 for an illustration of this. We remark that the distances between embeddings of scene representations were used to automatically segment video into discrete events by Franklin et al. (2020), and obtained strong agreement with human annotators. The thresholded distance used to obtain the segmentation is analogous to our locality-sensitive hashes, which we use as context sketches.
A sketch can be viewed at different levels of granularity before using it to access the hash table; this becomes the context of the sketch. Each bucket contains a program that is executed when a sketch arises that indexes into that bucket. The program in turn produces outputs and new sketches that are routed back to the hash table. The system works in a continuous loop where sketches are coming in from the environment and also from previous iterations; the main structure of the loop is:
Phenomena sketch context bucket program Phenomena input f h
produces
output
Thus external and internal inputs arrive as sketches that are converted into a coarser representation using a function f (see Section 2.1 below) and then hashed to a bucket using a locality-sensitive hash function h. The program at that bucket is executed to produce an output-sketch that is fed back into the system and may also produce external outputs. This basic loop (described in Algorithm 1) is executed by the routing module, which can be thought of as the operating system of the architecture.

heading: 2 SKETCHES REVIEW
text: Our architecture relies on the properties of the sketches introduced in Ghazi et al. (2019). In this section we briefly describe the key properties of these sketches; the interested reader is referred to Ghazi et al. (2019); Wang et al. (2021) for details.
A sketch is a compact representation of a possibly exponentially-wide (d×N ) matrix in which only a small number k of the columns are nonzero, that supports efficient computation of inner products, and for which encoding and decoding are performed by linear transformations. For concreteness, we note that sketches may be computed by random projections to Rd′ for d′ ≥ kd logN ; the JohnsonLindenstrauss Lemma then guarantees that inner-products are preserved.
For our purposes, we suppose modules M1, . . . ,MN produce vectors x1, . . . , xN ∈ Rd as output, where only k of the modules produce (nonzero) outputs. We view the sparse collection of module outputs as a small set of pairs of the form {[Mi1 , xi1 ],. . . ,[Mik , xik ] }: For example an input image has a sketch that can be thought of as a tuple [IMAGE, 〈bit-map-sketch〉]. An output by an image recognition module that finds a person in the image can be represented as [PERSON, [〈personsketch〉, 〈position-in-image-sketch〉]); here IMAGE and PERSON can be thought of as “labels”. If the outputs of these modules are vector embeddings in the usual sense, then indeed the inner products measure the similarity of the objects represented by the output embeddings.
Observe that the constituent individual vectors xj in a sketch may themselves be sketches. For example, 〈person-sketch〉 could in turn be set of such pairs {[NAME,〈name-sketch〉], [FACIALFEATURES,〈facial-sketch〉], [POSTURE,〈posture-sketch〉]}, and an image consisting of multiple people could be mapped by our recognition module to a set {〈person-1-sketch〉, 〈person-2sketch〉,. . . ,〈person-k-sketch〉}. Note if the if the tuple is very large, we will not be able to recover the sketch of each of its members but only get a “average” or summary of all the sketches – however if a member has high enough relative weight (see (Ghazi et al., 2019, Section 3.3)) it can be recovered. Appendix C.1 discusses how large objects can be stored as sketches hierarchically.
Indeed, following Ghazi et al. (2019), the outputs of modules in our architecture will be tuples that, in addition to an “output” component, represent the input sketches which, in turn, represent the modules that produced those inputs, e.g., {[MODULE-ID,〈module-id〉], [OUTPUT-SKETCH,〈outputsketch〉], [RECURSIVE-INPUT-SKETCH, 〈recursive-input-sketch〉]}. By recursively unpacking the input sketch, it is possible to reconstruct the history of computation that produced the sketch.
Algorithm 1 Informal presentation of the main execution loop Input: input sketch T (this sketch may contain a desired output for training)
1 current-sketches← {T} 2 while current-sketches is not empty: 3 current-programs← ∅ 4 foreach sketch S in current-sketches do 5 extract context C = f(S) 6 update access-frequency-count of bucket h(C) 7 if bucket h(C) has a program P : 8 append (S, P ) to current-programs 9 else: 10 if bucket h(C) is frequently accessed: 11 initialize program at h(C) with some random program and mark it for training. 12 Fetch programs Pi (possibly by some similarity criterion), append those (S, Pi) to current-programs 13 Routing module chooses some subset of current-programs, runs each program on its associated sketch, appends outputs to current-sketches 14 Append sketches on outgoing edges of accessed buckets to current-sketches 15 if any of the programs are marked for training: 16 routing module picks one or some of them and trains them, and may choose to stop execution loop 17 if any of the sketches is of (a special) type OUTPUT sketch: 18 routing module picks one such, outputs that sketch or performs that action, and may choose to stop execution loop 19 if any of the sketches is of type REWARD sketch (say for correct prediction or action): 20 updates the reward for this bucket and propagates those rewards to prior buckets 21 Routing module picks k combinations of sketches in current-sketches, and combine them into compound sketches: S1, . . . , Sk (may produce 0 sketches) 22 current-sketches← {S1, . . . , Sk}

heading: 2.1 PRINCIPLES OF THE ARCHITECTURE
text: The following are the guiding principles behind the architecture.
1. Sketches. All phenomena (inputs, outputs, commonly co-occurring events, etc) are represented as sketches. There is a function from sketch to context f : S → C that gives a coarse grained version of the sketch. This is obtained by looking at the fields in the sketch S that are high level labels and dropping fine details with high variance such as attribute values; it essentially extracts the “high-level bits” in the sketch S.
2. Hash table indexed by context that is robust to noise. (more details in Appendix C.2) The hash function h : C → [hash-bucket] is “locality sensitive” in the sense that similar contexts are hashed to the same bucket with high probability. Each hash bucket may contain a trainable program P , and summary statistics as described in Figure 3. We don’t start to train P until the hash bucket has been visited a sufficient number of times. (Note: A program may not have to be an explicit interpretable program but could just be an “embedding” that represents (or modifies) a neural network.)
3. Routing-module. (can be implemented by Alg.2 ) Given a set of sketches from the previous iteration, the routing module identifies the top ones, applies the context function f followed by the hash function h to route them to their corresponding buckets. Before feeding these to f , the routing module picks a subset of sketches and combines them into compound sketches. The routing module makes all subset-choosing decisions
In addition, we can also keep associations of frequently co-occuring sketch contexts as edges across buckets forming knowledge graph. Please see Appendix C and G for details.
Thus new modules (or concepts) are formed simply by a new frequently occurring context (see earlier papers on how sketches are stored in LSH based sketch memory). Since sketches are fed to the programs indexed by their context, the context can be viewed as a function-pointer and the
sketch can be viewed as arguments for a call to that function; multiple arguments can be passed by using a compound sketch. Programs that call other modules can be represented as a computation DAG over modules at the nodes .

heading: 3 INDEPENDENT TASKS AND ARCHITECTURE V0
text: Our learning problem follows a formulation similar to Ruvolo & Eaton (2013). In a lifelong learning system, we are facing a sequence of supervised learning tasks: Z(1), . . . ,Z(Tmax). In contrast to Ruvolo & Eaton, at each step we will generally obtain a single input (in the form of sketch (st,x
(t),y(t))) that contains DATA x(t) ∈ X (t), TARGET y(t) ∈ Y(t) and task descriptor sketch (vector) st, where the tth task is given by a hidden function φ̂(t) : X (t) → Y(t) that we want to learn, and φ̂(t)(x(t)) = y(t). We assume that that the tasks are uniformly distributed, and the distributions over task data are stationary: i.e., at each step, the task is sampled uniformly at random, and for the sampled task t, the data is sampled independently from a fixed distribution on X (t) for t. In this setting, we assume the task functions are all members of a common, known class of functionsM for which there exists an efficient learning algorithm AM, i.e., AM satisfies a standard PAC-learning guarantee: when provided with a sufficiently large number of training examplesM , with probability 1 − δ AM returns a function that agrees with the task function with probability at least 1 − on the task distribution. For example, SGD learns a certain class of neural networksM with a small constant depth. Indeed, we stress that this setting does not require transfer across tasks.
Our architectures are instantiated by a choice of hash function h and a context function f . Architecture v0 uses a very simple context function f : it projects the sketch down to the task descriptor t, dropping the DATA x(t) and TARGET y(t) components. (Other combinatorial decisions in the routing module are NO-OPs.) Each time we receive an input learning sample, we will call Alg. 1 (input is a single sketch). Claim 3.1. Given an error rate > 0 and confidence parameter δ > 0 and N independent tasks, each of which require at most M = M( , δ) examples to learn to accuracy 1 − with probability 1−δ, and training data as described in above, with probability 1− (N+1)δ, Architecture v0 learns to perform all N tasks to accuracy at least 1− in O(MN log Nδ ) steps.

heading: 4 HIERARCHICAL LIFELONG LEARNING AND ARCHITECTURE V1
text: We follow a similar problem formulation as in Sec.3, but in this case a task can depend on other tasks. We assume that the structure of dependencies can be described by a degree-d directed acyclic graph (DAG), in which the nodes correspond to tasks. Each task t depends on at most d other tasks t′1, . . . , t ′ d, indicated by the nodes in the DAG with edges to its node, and the task is to compute the corresponding function φ̂(t) = φ(t)(φ̂(t ′ 1), . . . , φ̂(t
′ d)) where φ(t) ∈ M. If t′1, . . . , t′d are sources in
the DAG (no incoming edges) then φ̂(t ′ i) ∈ M. We assume that all tasks share a common input distribution. We will call the functions fromM atomic modules, since they are the building blocks of this hierarchy. We will call functions that call other functions in the DAG, such as φ̂(t) above, a compound module. As before, we assumeM is a learnable function class. However, φ̂(t) might not belong to a learnable function class due to its higher complexity. Here, we will assume moreover that the algorithm AM for learning M is robust to label noise. Concretely, we will assume that if an -fraction of the labels are corrupted by an adversary, then AM produces an O( )-accurate function. We note that methods are known to provide SGD with such robustness for strongly convex loss functions, even if the features are corrupted during training (Diakonikolas et al., 2019) (see also, e.g., Li et al. (2020); Shah et al. (2020)). In this setting, we assume that the tasks are again sampled uniformly at random, and that the data is sampled independently from a common, fixed distribution for all tasks.
As with the architecture v0, v1 uses any locality sensitive hash function h and a context function f that projects the input sketch down to the task descriptor, discarding other components. The primary modifications are that
1. v1 tracks whether tasks are “well-trained,” freezing their parameters when they reach a given accuracy for their level of the hierarchy, and
2. until a “well-trained” model is found, we train candidate models for the task in parallel that use the outputs of each possible subset of up to d well-trained modules as auxiliary inputs.
We will maintain a global task level L, initially 0. We define the target accuracy for level-L tasks to be L = (2dC)L , where C is the constant under the big-O for the guarantee provided by our robust training method; we letML denote the sample complexity of robustly learning members of our class M to accuracy 1−Cd L−1 with confidence 1−δ when a 1−d L−1-accurate model exists. We check if any tasks became well-trained in level L − 1, and if so, for all tasks that are not yet well-trained, we initialize models for all combinations of up to d − 1 other well-trained tasks for each such new task. Each model is of the form φ(φ̂i1(x), ..., φ̂ik(x)), where i1, . . . ik (k ≤ d) is the corresponding subset of well-trained tasks such that at least one has level L − 1. On each iteration, the arriving example is hashed to a bucket for task t. We track the number of examples that have arrived for t thus far at this level. For the first M ′ examples that arrive in a bucket, we pass the example to the training algorithms for each model for this task, which for example completes another step of SGD. Once ML examples have arrived, we count the fraction of the next O( d L log N δ ) examples that are classified correctly by each of the models. We thus check if its empirical accuracy is guaranteed to be at least 1 − L with high probability. If the empirical accuracy is sufficiently high, we mark the task as well-trained and use this model for the task, discarding the rest of the candidates. Once all of the tasks are well-trained or have obtained ML + O( d L log N δ ) examples since the global level incremented to L, we increment the global level to L+ 1. Lemma 4.1. Suppose at each step, a task t is chosen uniformly random from the set of tasks {t1, . . . , tN} in a DAG of height `, along with one random sample (x, y) where φ̂(t)(x) = y. Then after `MN ln(1/δ) steps all the tasks will be well-trained (training error rate≤ L for each module at level L) w.h.p. We will call SGD O(`MN (1+d) ln(1/δ)) times during the training. Here, M is the upper bound of all ML.
In the above discussion we argued at an algorithmic level and ignored the specific architecture details of which buckets the ( N d ) candidate modules are trained and how eventually a single compound module gets programmed in the bucket h(st). See Appendix E for those details.

heading: 5 ARCHITECTURE V2: TASKS WITHOUT PRECISE EXPLICIT DESCRIPTIONS
text: We follow a similar problem formulation as in Sec. 4. However now clear task descriptors may not be provided externally, but may implicitly depend on the output of a previous module. (detailed examples in Appendix.F ). The following definitions and assumption differ from Sec. 4. Definition 5.1 (Tasks). Let U be a space of all (potentially recursive) sketches that include the input and output of all modules. (U can be polymorphic, that is, it can contain multiple different data types). Each task ti is a mapping : U → U . The input distribution of ti, Di, is supported on U . Definition 5.2 (Latent dependency DAG). The latent dependency DAG is a DAG with nodes corresponding to tasks t1, .., tN and edges indicating dependencies. Each task at an internal node depends on at most d other tasks (d may not be known to the learner, but is a small quantity). Definition 5.3 (Latent circuit). Given a dependency DAG, for each task ti there is a latent circuit with gates (nodes) corresponding to the tasks t′i that it depends on. In this circuit for ti, there are (potentially) multiple sinks (nodes with no outgoing edges). The output of these sinks will be the inputs to some atomic module, which gives the output of ti. There are multiple atomic internal modules for each ti and the circuit routes each example to one of these modules. Each ti is “vague” in the sense that there are multiple modules that can cater to an example of this task. Definition 5.4 (Hidden task description / Context). Given the circuit of each ti, there is a fixed (unknown) subset of the outputs of the circuit that give a context value that uniquely identifies ti. There exists a bound gi on the number of context values for ti. There is one atomic module for each context. We let G be an integer such that ∑ i gi ≤ G.
Assumption 5.5 (No distribution shift). For a latent dependency DAG and circuit for task ti, suppose tj is one of the nodes in the circuit of task ti, and let x ∼ Di be the input to ti. For each xj computed as an input to tj when the circuit is evaluated on x, we assume xj belongs to Dj .
Given the problem set-up above, we present our main result for this section:
Theorem 5.6 (Learning DAG using v2). Given a latent dependency DAG of tasks overN nodes and height `, and a circuit per internal node in the DAG, there exists an architecture v2 that learns all these tasks (up to error rate L as defined in Sec.4) with at most O(`GM2O(d 2+d log(N/d))) steps.

heading: 5.1 CONTEXT FUNCTION AS A DECISION TREE
text: In architecture v2 we use a more complicated context function f to extract the stable context for each task. The context function can be implemented as a modular decision tree where each node is a separate module. We are given a compound sketch [S1, .., Sk] where we assume the sketches are ordered by importance (e.g., based on frequency: if there are m hash buckets we will only track contexts that appear at least O(1/m) fraction of the time, while others get “timed out“ – we assume m ≥ G2O(d2+d log(N/d))). We apply f recursively and then over f(S1), .., f(Sk) from left to right in a decision tree where each branch either keeps or drops each item and stops or continues based on what obtains the highest rewards, tracked at each node (subtree) of the decision tree. Thus the context function can be implemented as a recursive call to a decision tree f([S1, .., Sk]) = DecisionTree([f(S1),..,f(Sk)]) (see Alg.2 )—each node of the decision tree will be implemented in a separate module (hash bucket).
Algorithm 2 Decision Tree DecisionTree([C1, ..Ck]) = TreeWalk([], [C1, ..Ck]) TreeWalk(l, [Ci, .., Ck]) = branch-based-on-argmax (
reward(h([TREE-WALK, l.append(Ci)])]) :TreeWalk(l.append(Ci), [Ci+1, .., Ck]) /* keep Ci in l and proceed to next field */ reward(h([TREE-WALK, l])]): TreeWalk( l, [Ci+1, .., Ck]) /* drop Ci and proceed to next field */ reward(h([TREE-WALK, l.append(END-WALK-SYMBOL)]) ) : TreeWalk(l, []) /* exit the walk and output l */ ) /* l is the subset of fields from the sketch from the prefix processed so far,Ci, .., Ck is the remaining part of the sketch. l is used as the context for this current decision tree node and [C1, .., Ck] is the input sketch. Each distinct value of l is a separate decision tree node */
The branch statement is branching to a one of the three buckets: h([TREE-WALK, l.append(Ci)]), h([TREE-WALK, l])], or h([TREE-WALK, l.append(END-WALK-SYMBOL)]) based on the rewards; each bucket continues the decision tree walk with the rest of the entries in the list of contexts. Note that during training the branch will be a probabilistic softmax rather than a deterministic argmax, with a temperature parameter T that controls the exploration of the branches and decreases eventually to near 0; thus the probability of each branch is proportional to e−Rbranch/T , where Rbranch is the reward of the branch. Initially all rewards are 0 and so all branching probabilities are all equal to 1/3 (but there could be some other priors). Over time as the temperature is lowered, the probability concentrates gradually on the bucket with maximum reward. See Appendix F for full details. Claim 5.7. If p is the initial probability of taking the optimal reward path to the leaf in the DecisionTree algorithm above, there is a schedule for the temperature in Algorithm 2, so that in O(1/p log 1/δ) tree walk steps the modules at the nodes of the tree will converge so that the decision tree achieves optimal rewards with high probability 1− δ.
Proof. We will keep a very high initial temperature T (say ∞) for O((1/p) log(1/δ)) tree walk steps and then suddenly freeze it to near zero (which converts the softmax to a max) after these steps are finished. In these initial steps with high probability 1 − δ the optimal path to the leaf will have been visited at least 1/δ times. Since each node is tracking the optimal rewards in its subtree, the recorded best path from root will have tracked at least this optimal reward.

heading: 5.2 INCREMENTALLY LEARNING A NEW NODE (IMPLICIT TASK)
text: In this subsection we provide an induction proof sketch for Theorem 5.6. In the previous subsection, we saw how the context function can be implemented as a probabilistic decision tree. Other functions of the routing module that involve making subset-choosing decisions (such as Lines 13 & 21
in Alg. 1): for example, selecting a subset of d pre-existing modules as children of a new task in v1 can be done using a separate decision tree (e.g. Alg. 2) where one needs to select a subset of at most d. This again becomes very similar to the operation of the context function: we just need to input all matured modules of the previous layer to Alg. 2 and find the ≤ d child modules. In architecture v2 any subset-choosing decision in our architecture can be done by using Alg. 2.
The learning algorithm follows the framework of Alg.1. The circuit routing is also done by Alg. 2: we feed all the O( ( N d ) 3( d 2)) candidate edges of the circuit to Alg. 2, which finds the correct subset. The inductive guarantee that lower-level tasks are well-trained comes from the bottom-up online algorithm of v1. Modules are marked as mature based on performance, and new modules are only built on top of mature previous nodes. The probability of picking the right sequence of decisions for perform the new task is p = 1/2O(d
2+d log(N/d)) (including which identifying which previous possibly implicit tasks it depends on and wiring them correctly with the right contexts) and it takes M examples to train the task, then the task can be learned in O(M2O(d
2+d log(N/d))) steps per atomic module (see Appendix F for full details).

heading: 6 EXPERIMENTS
text: We empirically examine two tasks for which learning benefits from using a modular architecture in this section. We compare an “end to end” learning approach to a modular learning approach which explores a DAG of previously learned tasks probabilistically.

heading: 6.1 LEARNING INTERSECTIONS OF HALFSPACES
text: Learning intersections of halfspaces has been studied extensively, see for example (Klivans & Sherstov, 2009). We first describe the experiment setting. Let K be the number of hyperplanes, D feature space dimension, we generate the following data: hyperplane coefficients wk ∈ RD, k = 1, 2, ...,K whose components are independent and follow standard normal distribution; 2.feature xi ∈ RD, i = 1, 2, ..., N , independently chosen uniformly from [−1, 1]. And we have yi = ∏ k∈[K] sgn(wk · xi), where sgn is the sign function.
While learning a single halfspace K = 1 is easily solved by a two-layer network with ReLU activation, it becomes much more difficult for neural networks to learn when K grows. This can be observed in Figure-2, where a 3-layer neural network is used to learn the intersections.
For a modular approach, we follow Algorithm-3, which is a simplified version of Algorithm–1 and it probabilistically route to sub-modules. The input data are batches of triplets {(k, xki , yki )}i∈[B], where B is the batch size, k ∈ [K + 1] is the task id, x1i = ... = x K+1 i = xi, y k i = sgn(wk · xi) for
k ∈ [K] and yK+1i = ∏ k∈[K] y k i , and we maintain a task list T and module list Φ.
The results are plotted in Figure-2, with K = 1, 2, ..., 10, D = 100, patomic = 0.5 and pcompound = 0.75. For the modular approach, all the modules are 3 layer fully-connected network of the same size and are trained for 10 epochs. For the end-to-end approach, a single 3 layer fully-connected network with 10x hidden units of the modular models and is trained until convergence. We observe for large K (K ≥ 7 in the figure), the end-to-end approach fails at the task while the modular approach continues to have good performance. See appendix for more details.

heading: 6.2 FIVE DIGIT RECOGNITION
text: In this experiment, we compare the “end to end” approach and a modular approach for the task of recognizing 5-digit numbers, where the input is an image that contains 5 digits from left to right, and the expected output is the number that is formed from concatenating the 5 digits. This task is described in Example 2 of Appendix F. Note in this task, we have 3 sub-tasks: task-1 is single digit recognition, task-2 is image segmentation, and task-3 is 5 digit recognition.
For the “end to end” approach, we train a convolutional neural network to predict the 5 digit number (see appendix for more details). For the modular approach, the input data are batches of triplets {(k, x(k)i , y (k) i )}i∈[B], where B is the batch size, k ∈ [3], x (1) i = x (2) i = x (3) i = xi is the image.
Algorithm 3 Probabilistic routing algorithm
Input: Batches of {(k, xki , yki )}i∈[B], k the same within a batch. Constants: patomic, pcompound. Initialization: Set of modules Φ = ∅, set of task ids T = [K + 1] Repeat the following steps:
y (1) i is the single digit label, y (2) i is 5 segmentation coordinate pairs (upper-left and lower-right coordinates), and y(3)i is the 5 digit number label. We also maintain a task list T and module list Φ. For training an atomic module in Algorithm-3, we only allow the module to take inputs of the same modality (i.e. either only image or only digits, discarding the others).
We construct the training and test datasets by concatenating 5 images from the MNIST dataset. The results of the two approaches are compared in Table-1. We observe the modular approach achieves higher accuracy and has less variance with the same training steps.

heading: 7 DISCUSSION AND FUTURE WORK
text: We saw a uniform continual learning architecture that learns tasks hierarchically based on sketches, LSH, and modules. We also show how a knowledge graph is formed across hash buckets as nodes and formally show its utility (for e.g. for finding common friends in a social network) in Appendix G. Extensions of the decision tree learning to solve reinforcement learning tasks are shown in Appendix H. Although our inputs were labeled with a unique task description vector, we note our architecture works even with noisy but well-separated contexts (see Appendix D). A weakness of our work is that we have ignored how logic or language could be handled in this architecture – while perhaps there could be separate compound modules for those kinds of tasks, we leave that topic open.

Review summaries:
This work introduces a continual-learning architecture that combines elements for sketches, hash functions, modules and routing. Theoretical guarantees are provided for the performance of the architecture.  Some experiments seem to support the advantage of the proposed architecture over conventional deep learning ones.

The submission proposes an approach to lifelong learning using a sketch-based modular architecture. The primary contributions of the paper are proofs of the learnability of certain classes of tasks with three different choices of modular architectures. The algorithms are also evaluated empirically on toy supervised learning tasks.  

The authors propose a modular architecture for multitask learning in the presence of hierarchically structured tasks leveraging sketches and locally sensitive hashing. They further provide proofs and error bounds about how the proposed architecture can learn tasks while leveraging access to previously learned subroutines. The authors additionally provide extensions to the proposed architecture in the case of tasks depending on other tasks and lack of clear task boundaries. Empirical studies are conducted for this modular approach in comparison to end-to-end models on synthetic domains related to learning the intersection of half-spaces and MNIST digits.