Background and Motivation

• Why do we need a theory paper?
• Classical machine learning is: You are given data, the goal is to train a system for the task at hand.
• The task could be things like image classification (cat or dog) or clustering, and you train a neural network to do the classification for you.
• A lot of theory has been done on this sort of learning (see VC and Valiant).

Background and Motivation

• There are many other machine learning paradigms that haven't been theoretically formalized well yet.
• In the past it didn't matter because we couldn't even do classical machine learning that well.
• GPUs changed all that and now we want to do things like transfer learning, multitask learning, lifelong learning, etc...

Learning

• This can get pretty philosophical and complicated, so let's not go there. We use a practical definition instead.
• A learner learns with respect to a task from data if the learner's performance on the task improves because of the data.
• In English, if we are doing image classification (the task), and our network classifies better (performance) after training it on the data, then the network has learned.

Performance

• Performance is just the risk. In a familiar scenario like linear regression, it is simply expected squared loss,

$\mathbb{E}_{P_{X, Y}}[\left(h(X) - Y\right)^2]$

• $X$ is the query, the pattern/feature, the image to be classified, the thing to which assign a label.
• $Y$ is the action, the label, cat or dog, the actual cluster assigned to the pattern.
• $h$ is the hypothesis, a function which when given a query, outputs its guess for the corresponding correct action.
• $P_{X, Y}$ is a distribution over queries and actions.

Performance

• Performance then, in its general form is,

$R_{P_{X, Y}}(h)$

Data

• This can be query-action pairs (i.e. $(X, Y)$ pairs), or if we have a Gaussian $\mathcal{N}(\mu, 1)$ whose mean we want to estimate, the data can just be $n$ observations from the distribution.

Performance with Data

• Some function of the expected risk, or generalization error

$\mathbb{E}_{P_{X, Y, \mathbf{S}}}[R(\hat{h})]$

• $\mathbf{S}$ is the data set.
• $\hat{h}$ is the hypothesis estimated using the data.
• From where do we $\hat{h}$?

Learner

• The learner $f$ is what produces $\hat{h}$.

• The learner takes in the data set $\mathbf{S}$ to output an estimated hypothesis. $f(\mathbf{S}) = \hat{h}$

• The performance then is really some function of $\mathbb{E}_{P_{X, Y, \mathbf{S}}}[R\left(f(\mathbf{S})\right)]$

Task

• After we have specified all the previous stuff (queries, actions, data, etc.), then the task is to minimize the generalization error

$\text{min } \qquad \mathbb{E}_{P_{X, Y, \mathbf{S}}}[R\left(f(\mathbf{S})\right)]$

$\text{such that } \qquad f \in \mathcal{F}$

• $\mathcal{F}$ is the space of learners (we could have computational complexity constraints on the learners used for example)

Improving Performance

• Recall our definition of learning, "A learner learns with respect to a task from data if the learner's performance on the task improves because of the data."
• The final piece is improving performance because of the data. We introduce learning efficiency to measure this,

$\text{LE}_f^t(\mathbf{S}_0, \mathbf{S}) = \frac{\mathcal{E}_f^t(\mathbf{S}_0)}{\mathcal{E}_f^t(\mathbf{S})}$

• $\mathbf{S}_0 = \varnothing$ is the empty data set, meaning no data.
• If $\text{LE} > 1$, then performance has improved because of the data $\mathbf{S}$.

Generalized Task

• A task is the object of study in classical machine learning.
• There we are given a data set $\mathbf{S}$ and a task $t$.
• The break we make with this framework is that we now allow for multiple data sets, and multiple tasks.
• A super task then is when we have multiple data sets $\lbrace \mathbf{S}^1, ... , \mathbf{S}^m \rbrace$ and multiple tasks $\lbrace t_1, ..., t_n \rbrace$, $m \geq n$.
• Note we can have empty data sets.
• Multitask learning, transfer learning, etc. can now be framed as generalized tasks.

Transfer Learning

• In transfer learning, we have a single task and multiple data sets.
• With transfer learning, we want to measure if the out-of-task data has helped our performance more than just using the task data.
• We use learning efficiency to measure this, $\text{LE}_f^t(\mathbf{S}^1, \mathbf{S}) = \frac{\mathcal{E}_f^t(\mathbf{S}^1)}{\mathcal{E}_f^t(\mathbf{S})}$
• $\mathbf{S}^1$ is the task data.
• $\mathbf{S}$ is all of the data (i.e. we put together all of the data sets).
• We have transfer learned if $\text{LE}_f^t > 1$.

Multitask Learning

• In multitask learning, we have multiple tasks and multiple data sets.
• With multitask learning, we want want to measure how much we have transfer learned for each task, $\text{LE}_f^t(\mathbf{S}^t, \mathbf{S}) = \frac{\mathcal{E}_f^t(\mathbf{S}^t)}{\mathcal{E}_f^t(\mathbf{S})}$
• $\mathbf{S}^t$ is the task $t$ data.
• $\mathbf{S}$ is all of the data.
• We have transfer learned for that task if $\text{LE}_f^t > 1$.
• We have multitask learned if some weighted average of the learning efficiencies $\text{LE}_f^{t_1}, ..., \text{LE}^{t_n}$ is greater than $1$.

Continual Learning

• Continual learning is very akin to multitask learning
• The primary difference with multitask learning is that it is done sequentially in time.
• This leads us to explicitly require computational complexity constraints on the hypothesis and learner spaces. Namely, we require $o(n)$ space and/or $o(n^2)$ time as upperbounds for the complexity.
• The other aspect to continual learning is that everything is streaming: data, queries, actions, error, and tasks. Hence anything about the task the learner is faced with can change over time (without the learner necessarily knowing that a change has occurred).

Quantifying Continual Learning

With continual learning, we want to incorporate the time-dependent, streaming nature of the problem in our performance metrics. Given a task $t$, let $\mathbf{S}^{< t}$ be the set of data points up to and including the last data point from task $t$.

We define forward transfer to be $\text{LE}_f^t(\mathbf{S}^t, \mathbf{S}^{< t}) = \frac{\mathcal{E}_f^t(\mathbf{S}^t)}{\mathcal{E}_f^t(\mathbf{S}^{< t})}$

And we define backward transfer to be $\text{LE}_f^t(\mathbf{S}^{< t}, \mathbf{S}) = \frac{\mathcal{E}_f^t(\mathbf{S}^{< t})}{\mathcal{E}_f^t(\mathbf{S})}$

Where $\mathbf{S}$ is all of the data and $\mathbf{S}^t$ is the task $t$ data.

Other definitions of learning for OOD scenarios

• We used learning efficiency as the basis metric with which to measure performance and trasnfer in the various OOD scenarios.
• There are many other ways as well to measure transfer and performance.
• Analogous to traditional learning, we will introduce and examine here the two notions of weak OOD learning and strong OOD learning.

Weak OOD

Assume we have some model of distributions $\mathcal{P}$ and source distribution $P$. Loosely, we say $\mathcal{P}$ is weakly OOD learnable with target data of size $n$ if given enough source data, we can perform better than base performance (i.e. with just target data) with arbitrarily high probability.

Strong OOD

Assume we have some model of distributions $\mathcal{P}$ and source distribution $P$. We say $\mathcal{P}$ is strongly OOD learnable with target data of size $n$ if given enough source data, we can perform arbitrarily well (i.e. arbitrarily close to the Bayes risk) with arbitrarily high probability.

Theoretical Results

• Strong OOD learning implies weak OOD learning
• Weak OOD meta-learning does not imply strong OOD meta-learning (meaning we cannot boost)
• Weak OOD learning implies positive transfer (meaning learning efficiency is greater than $1$ ), but not vice versa