Hello, well I'm very excited to start the tutorial.
Our first speaker is Vitaly Kuznetsov.
He's a research scientist at Google.
He did his PhD at Courant Institute for Mathematics and
his research interests are mostly in non stationary
time series analysis in both theory and applications.
No further ado.
>> Thank you so much for introduction.
And I'm also very excited to talk to you today about
non-stationary time series.
Actually let me start by saying a few words.
Why do we actually care about
time series analysis in the first place, right?
Why are we all here today?
In fact, time series data appears in many,
many real world applications these days.
Stock values, different other economic variables,
local temperatures or global climate trends.
All of these often come in the form of time series data.
In fact, I personally like to argue that
all of the data that we're collecting is time series data.
Precisely because we are collecting this data over time, right?
If you look at this list, you will see that
actually in a lot of these applications it is
critical to be able to do time shares analysis and
time shares forecasting accurately.
If we're talking about stock values then there could be millions or
billions at stake.
If we're talking about climate, even future of our planet.
But I also want to argue that time share analysis not only
very important problem, but it is also often a very challenging task.
So, let's look at maybe some examples of time series here.
So you probably have heard about Google trends, right?
So here's a plot of two time series from Google trends,
this is an interest over time in two different search terms,
machine learning and deep learning.
And you look at this time series, maybe you see some patterns there
right, maybe some common trend component, or any other patterns.
But these initial intuition that we may have from these simple
plots often can actually quite misleading.
For instance, if I were to zoom in on earlier
segments of these time series, say for 2012,
2013, then what I would see is a plot like that,
which looks very different from my original plot.
And we can see that this time series for
instance, also most of them look quite different, right?
The machine learning time series is sort of more volatile,
maybe has some seasonal component on the other.
Hence deeper and it gets more assertive, stable and
doesn't vary that much over time.
On the other hand if I were to progress further in time and
look at the more recent data 2016, 2015 period.
Then picture changes once again.
All right, now we see some sort of trends, both time series
are moving in a much more volatile fashion and maybe surprisingly.
Even we can see that, in some cases, they are moving in opposite
directions, which is also something that is counterintuitive for
these two search terms.
So these kind of phenomena of non-stationarity
make time series analysis very challenging and
it make time series analysis also very different from
the usual machine learning that we are used to, all right?
Typically, what we expect
to heal machine learning is some sort of idea assumption.
We expect that our training distribution is
going to be the same as our test distribution.
We expect that these distributions are fixed and
do not change over time, which means they're stationary.
But this is not the case for time series analysis
In general these assumptions violate within these kind of scenarios.
So how can we analyze this kind of data?
How can we learn from these kind of known stationary kinds of data?
These are the kind of questions that will
try to investigate in this tutorial and try to answer them.
And the plan for today is going to be as follows.
The first thing I'm going to do is give a very quick
30 minute introduction to classical, traditional time series analysis.
Then we're gonna have a very short two minute break just to
catch some breath.
And then we're gonna discuss some more recent learning theory that
has been developed for this kind of non-stationary time series.
After that,
after theory we're gonna take a longer break, a whole four minutes,.
And then after that we're going to switch gears and
talk a little bit about algorithmic solutions that are based
on this theory that we'll present.
And finally, we'll discuss some connections between time series
prediction and this very hot topic these days, that of online learning.
All right, so let us then jump right in and
let us talk about a classical time series analysis.
The way classical time series analysis works the way
this classical framework operates is as follows.
The first thing that you typically do you postulate some
parametric model that you assume that is
generating the data that you're observing.
Then once you have done this critical step,
you take the data that you observe and you use this data to
estimate the unknown parameters of this parametric model.
Then finally once you have this estimated model you'll use it for
whatever purposes you want to it be used enable for
instance prediction, all right.
So what kind of models are out there?
Well if you start thinking about what you're trying to do right,
somehow what you're trying to do is to
use your past observations to make the forecasts about the future.
So a very natural thing to do would be to take lots of p
observations, combine them in a certain way and
that would be your forecast of the future.
And that's precisely what, so-called autoregressive models are.
They are linear combinations of your
past p observations with weights a1, a2, up to ap.
Which we call autoregressive coefficients.
And once you form these linear combination of
the previous observations Yt,
Y t-1, Y t-2 up to Y t-p, you add some noise term epsilon t.
And you assume that that this is going to be
the next iteration in this sequence.
So these noise terms that you typically add,
they're uncorrelated zero mean random variables.
And they are supposed to capture that certainty
that is not captured by the linear combination of the past observation.
In this point, you may say, well,
why only restrict yourself to the uncertainty of time T, right.
Maybe uncertainty of previous times also may play a role in this.
And if you kind of start thinking along these lines,
then the model that you're going to arrive at
is going to be this so-called moving average model,
which assumes that the observation
Yt is a combination of the uncertainty at time t, epsilon t.
And the uncertainties at previous times, Epsilon t-1,
epsilon t- 2 up to epsilon minus, epsilon t- q.
And they combine with certain ways which we call moving
average coefficients, right.
And then combining these two models.
The ultra regressive model of the past observation The moving
average model, we arrive to a very classical and celebrated model,
which is called ARMA model, AutoRegressive Moving Average model.
It was proposed, I think, back in the 50s by Whittle,
maybe even earlier, and
it was actually popularized by Box & Jenkins in the 70s.
So, let us actually look at an example of a process
distributed according to ARMA model, and here's one.
Looks like a bunch of random noise, ups and downs, some keeps,
but one interesting thing that you may observe is the following.
If you take two chunks of these time series,
like say an earlier chunk and a later chunk.
If you look at these two chunks, then in certain statistical sense
you won't be able to distinguish these two chunks, and
this phenomena is what's known as stationarity.
More formally is defined exactly in this way.
If I take any chunk of my time series and
I shift it by k units, and if I look at the distribution of
the regional chunk and if I look at the distribution of the new chunk,
and if these two distributions happen to be exactly the same,
that's what we call for stationarity.
In fact, this is often referred to as strong stationarity and
weak stationarity, or second moment stationarity,
a property that only requires basically the first and
second moment of these distributions to match.
Now, we're more precisely you want the mean of your
statistic process to be independent of time, and
you won't the function of statistic process to be independent of time.
Which means that the covariance or correlation of any ZT,
ZT-J only depends on the lack J, but
does not depend on the exact time point, T.
So, is our original intuition about the ARMA process correct?
Is it actually stationary, right?
Cuz it seemed from the plot I have shown to you that two chance would
be kind of exactly the same, so we need some tools.
So basically for this analysis and sort of the standard tool
that you should be familiar with if you want to do anything with these
kind of ultra regressive models is So-called Lag Operator.
So it's a very simple thing.
Basically what this Lag Operator is that if you're given an observation
Yt, and you apply this Lag Operator L to this observation Yt,
then what you're gonna get back is the previous observation Yt- 1.
Very simple.
But then what you can do, you can actually rewrite the ARMA model
that we had a few slides before in terms of these lag operators.
In particular, the way it's gonna look,
you're gonna form this polynomial in terms of the lag operator, right?
So on the left hand side, I have this 1 minus ai, the sum of ai,
lag operator, to the power of i, summed from i equals 1 to p.
And they apply it to yt.
And on the right hand side they form a similar
polynomial in terms of the lag operator.
And applied to the term.
And actually if you just work out the algebra and
applied the definition of the lag operator you'll arrive at exactly
the same formulation that we had for the ARMA model a few slides before.
But the reason this is.
Nice to write out the ARMA model in this way,
is because it exposes interesting properties of this ARMA model,
in terms of the Lag Operator, and
the special polynomial that we have on the left-hand side.
In fact, we're gonna call this
Polynomial on the left hand side characteristic polynomial. Right.
This polynomial that I denote by P
here, P of Z is one minus the sum of AI Z to the power of I.
Sum from I Equals 1 to p, right?
And it precisely characterizes the stationary properties of ARMA
processes.
In particular, a very standard result says the following.
If all the roots of the characteristic polynomial P And
that we had on the previous slide like outside of the unit circle.
Then they ARMA process P cure is going to be weakly stationary.
Right.
This is actually a very simple result.
In fact, the proof of this result is also rather simple.
It's just basically a blank
What you know about the roots of the polynomial.
But in there interest of time, I'm gonna skip the proof and
in fact, we're gonna post the slides online.
So, you're gonna be able to check out the proof for
yourself if you want a reference.
But let us actually go back to what we started talking about originally.
We were interested in modeling time series that are non-stationary.
Because they're much more realistic for
any application that we want to tackle.
But we have just said that these classical ARMA
models are stationary.
Are we doomed?
Can we actually change things?
Can we actually use this Generative framework for
modelling a non stationary time series.
Well, it turns out that this lag operator and
this characteristic polynomial
allow you to also build models of non stationary time series as well.
In particular one way to do that is to use ARMA processes.
Whose characteristic polynomials do have few unit roots, all right.
They have roots that lie on the unit circle.
So if that's the case then you can factorize such
polynomial into a polynomial R(z), all right,
which has all its roots outside of the unit circle.
And then polynomial (1- z) D.
Which has a unit root of multiplicity one.
And if you have an Arima process with such
characteristic polynomial, then this Arima process.
Is going to be non-stationary and thatâs how
this celebrated ARIMA models of other D are defined.
So in a way you can think of this ARIMA models and
I here by the way stands for integrated as.
ARMA models of a process which applies
polynomial one minus lag operator to the power of D to the process Y, T.
Take for instance the simple case of D equals one.
Right.
So what ARIMA model of all the d equals 1 says is that basically,
Yt minus Yt minus 1 is a stationary ARIMA process.
So how do ARIMA processes now look like?
Well, You know, if you plot one, you will get a picture like that,
that's sort of much better in terms of non-stationarity.
Right, we get some at least stochastic trend here perhaps.
And you can keep playing this game,
if you want to sort of model all other kinds of.
Sort of non-stationarity phenomenas explicitly.
You can come up with all sort of extensions of models,
there is a whole zoo of those.
You can incorporate a seasonal component,
you can incorporate long memory You can incorporate
so-called fractional effects, time varying coefficients.
There is really no limit to that.
No linear models, etc, etc.
One probably extension that any talk like that should
mention is The one that tries to incorporate
non-stationarity in the second moment of the time series.
In other words, try to model a non-stationary variance.
And that's what's known as a Garch model.
And this model simply says well, I want a non stationary variance.
So I'm gonna assume that my variance also is a stochastic process.
Which is just an ARMA process and that's how I define a GARCH model.
So it was introduced by Engle in the 80s and
that's what he got the Nobel Prize for.
Now, here is an example of an ARMA process.
You can see that the volatility kind of changes over time for
this time series.
And then you can continue coming up,
as I said, with all sort of other more fancy models.
So another example is a state-space.
Class of state-space models which you can basically think of
as just a continuous space analog of Hidden Markov Models.
The way they work, you assume that there is some unobserved state Xt.
That follows other regressive models, right?
And each next state, Xt + 1 is simply B where B is some
parameter of the model times the previous state,
Xt, plus a noise term, right?
And then, the observations that you actually get are assumed to be
a linear combination of the state, right?
So Yt = A times Xt + a noise term.
So again, example of a particular
state-space process, right?
And, really, you can continue as I said, playing these games and
keep coming up with different generative models for this.
So, we've talked a lot about
actually this first step in the classical framework for
time series analysis, postulating a model, right?
So then, how can we perform this second step, right?
Estimation, how do you find parameters of these kind
of autoregressive or state-space models.
Well, I guess the first thing that you probably
would think about is maximum likelihood estimation, right?
Let's make a further assumption about the noise terms
that we have introduced, for instance, the Ber Gaussian.
Then, we can, maybe, write down the log likelihood
of the data that we're observing and try to optimize the parameters
of the model to minimize the negative log likelihood.
For certain other models, there are also less general techniques
such as method of moments or conditional or unconditional
least square estimation that you can imply for instance to some
of the autoregressive models that I mentioned.
But the question is, we're not in ideal scenario anymore, right?
Do these methods actually work, right?
Can we give any guarantees for these kind of methods?
And yeah, people actually have worked on this and
they have worked out some learning guarantees for
these kind of methods under some, say, additional assumptions.
Like for instance, if I wanted to give a guarantee for
ARMA model that I have described to you earlier then I would
impose an assumption of invertibility.
Which basically means that this other characteristic polynomial
that we had on the noise term in the formulation of the ARMA model
has to also have its roots outside of the unit circle.
And in that case the model, the ARMA model is invertible.
And if I have both say, invertibility and
stationarity for ARMA model, then I can, for instance, give
a guarantee that the least square estimator of the autoregressive
parameters of that model will converge in probability
to the true parameters of the model, right?
So, this is an asymptotic learning guarantee for these kind of models.
It also requires the model to be correctly specified.
But at least, it gives some hope that these models can work.
And I should also mention that, of course,
I'm talking here about just least square estimator for ARMA models but
you can come up with similar asymptotic guarantees for
other models and other estimators that they have mentioned.
So, actually, I'm gonna, this more or less wraps up the sort
of lightning fast introduction to the classical time series analysis.
I just wanna sort of emphasize a few things that we talked about.
First of all, there are many, many generative models and
you can come up with a lot of those generative models yourself and
model all this phenomenon in whatever way you like.
The learning guarantees for these kind of models that we have
discussed are only typically asymptotic.
And, they also require the model to be correctly specified.
So, they're not robust to meet many specifications of the model.
And finally, one of the major difficulties actually
applying these kind of models is that, you actually
need to come up with the model of the non-stationarity yourself.
So you need to go ahead and look at the data and then say, this is
I think what kind of non-stationary phenomenon is happening in the data.
And, this is the kind of model that I'm going to impose.
And then in the remaining of this tutorial,
we are gonna try to discuss some new theory and some new learning
algorithms that would try to lift these sort of assumptions.
So, we'll break now for two minutes to just for
you to catch your breath.
And then, we'll continue with the theory part of the tutorial.
>> Okay, so we're gonna continue with the tutorial.
>> Our next speaker is Mario Mori.
He's a professor of computer science and
mathematics at the Quran Institute and
he's also a research consultant at Google Research.
>> All right, thank you very much.
First of all, I wanted to say that I'm really, really impressed to
have that many people here for a time series tutorial.
We knew that it was popular, now that's just a proof.
I promised to say this, this section is about theory, learning theory.
And some people asked me, why do we need learning theory?
And well, the answer is otherwise you are left to do parameter
search in a blind fashion and there is no principal for
designing an algorithm.
Vitali gave a description
of some classical techniques in time series prediction.
He also mentioned that there are some insufficiencies for
these techniques.
In particular, they do not have
the standard guarantees that we expect for finite training samples.
Their guarantees are asymptotic.
They also need to, they also come with a whole bunch of assumptions.
So the concepts and tools that I'm going to
discuss in the next few slides are hopefully gonna be helpful for
designing algorithms for time series in a more general way.
So let me start with a, So let me
start with a full mode description of time series forecasting.
In that scenario, the learner receives a finite training sample
which means a finite realization of a stochastic process X1,
Y1, X2, Y2, XT, YT.
Where the X is the X sub Ts are in some input space capital X.
And the Y sub Ts in the output space, the label space, capital Y.
And I will be denoting by capital Z, the cross product of X and Y.
And then, we assumed that we have a loss function that is bounded
by 1 and that takes as arguments a hypothesis, little h.
In some hypothesis, that capital H of function is mapping from x to y.
And well, an element of Z that means the pair X and Y.
So the learners problem is to use the hypothesis,
capital H, to come up with a function, little h,
that has a small Generalization, if you wish.
Or path dependence expected loss.
And that is defined in the bottom of the slide and
it will also give me the opportunity to describe the notation.
So the calligraphic L(h,Z1T).
So for first bold Z1T denotes the sequence
of the Zs training sample, if you switch from 1 to T.
And it is defined as the expectation at time capital T + 1.
Under the time at which you wish to make a forecast of the loss of
the hypothesis For that ZT + 1 drawn from
that distribution, conditioned on what you have observed so far.
That means Z1T.
Now the standard assumptions that are made in the analysis of
time series forecasting, or as stationarity and mixing.
Stationarity was already described and mentioned by Vitali.
In short,
it means that the distribution is invariant to shifting.
Mixing is a different type of assumption, which essentially
says that events capital A that occur after time N + K,
have a dependency with the specter events capital B that
occur before little n, that decays with this gap little k.
And this decaying dependency can be measured in many different ways.
One way to do so, is to use the so-called beta mixing parameter.
There are many other ways of measuring that.
Alpha mixing, phi mixing.
There's almost any Greek letter that you could append mixing to.
So happens that beta mixing is actually,
one could argue the right view.
And I'm not going to detail exactly what technically beta mixing
consists of,
because you'll see in a minute I'm gonna criticize all of these.
And make a lot of enemies, I'm sure.
So, but before doing so, let me just say that most people who have been
studying from the learning theory point of view time series, and
that includes me and many of my colleagues.
They have been adopting these assumptions stationarity and mixing.
And that includes the work by Vidyasagar of PAC-learning,
where he's actually arguing that beta mixing is the right view.
The generalization bounds given by Yu in terms of the VC-dimension for
binary classification, covering number balance for
regression given by Ron Meir.
We have been giving with action with complexity data dependent bounds for
general loss functions,
which about gives more general view of all of this.
And then more recently there have been PAC-Bayesian bounds given by
Alquier, all of these are making this assumptions of stationarity and
beta mixing.
That includes even algorithm dependent studies
such as this study of AdaBoost by Lozano et al.
Again, our study of stability stable algorithms in a very general way,
and many other studies of this kind.
All these raise some fundamental questions.
Because stationarity and mixing, these assumptions often do not hold.
They in fact typically do not hold.
Just think trend or periodic signals.
Furthermore, these assumptions are not testable.
So how do we know if they even hold?
It's even worse than this,
because even if you assume that mixing does hold.
Make it even simpler.
Assume that you even know what form that beta mixing for
example would have.
Assume for example, that it has an exponential form.
Even if you do assume that,
estimating these parameters turns out to be a very difficult problem.
But perhaps even worse than this is that these assumptions,
these notions,
do not capture some fundamental parameters of the problem.
Those that have structure, that means the hypothesis set which we
know in machine learning cannot be the family of all
measurable functions otherwise we cannot learn, and the last function.
So this raises some questions.
Is learning with general,non-stationary, non-mixing,
stochastic processes even possible?
And can we design algorithms that come with theoretical guarantees,
for such broad and general scenarios?
Again, just think that those assumptions really typically
do not hold.
We need a new tool for this analysis.
So, to do so let's just start from first principles.
Suppose you have a single hypothesis h, so
fixed h, what are we really interested in?
What we care about is the expected loss or,
remember again that conditional expectation of the loss given
the sample at time t + 1 of forecasting.
And what we receive is just training points.
So the difference between the expectation that expected loss at
time t + 1, and the expected loss of the same
hypothesis h at time t, is really the key quantity here.
That is what we really care about.
So of course, we're getting a full sample from time 1 to capital T,
so it's the average of this quantity, that becomes the really
important difference that is related to time series prediction.
This is for a single hypothesis.
If you take the supremum over all hypothesis
this gives a definition, a quantity, that we call discrepancy.
And so you can see at the top of the slide, it's the supremum over
all hypotheses of that average difference that I mentioned before.
Notice that this quantity, unlike notions that are purely related to
the stochastic process, captures the loss function.
And it's directly depending on the hypothesis's.
Perhaps even more importantly, this quantity can be actually estimated
from data, as we will see under some relatively mild assumptions.
Notice that the discrepancy delta is 0 in the IID case.
That's really straight forward to see.
And one can show also that in some broader cases for example,
for weakly stationary processes with linear hypotheses and squared loss.
The discrepancy's also just 0.
This definition of discrepancy is based on an average of those
differences.
The average here is uniform.
But, we might actually wish to use an even richer definition,
still really geared towards the analysis of this problem,
which we call the weighted discrepancy.
And we're now,
we are not just using a uniform average of these differences.
But instead we use some weights, q1, q2, q sub capital T,
for defining that averaging.
These weights, the q sub t's, are going to be crucial.
Particularly when it's gonna come to an algorithmic design.
Why?
Because you would wish to emphasize points T,
XTs or ZTs in your sample who's difference, who's expected
losses is close to the time at which you're gonna be forecasting.
And on the contrary, deemphasize those sample points for which
the expected loss is much further away from the time of prediction.
These weights q sub t's are going to help us, do this emphasizing and
deemphasizing.
Two words about this.
That this definition of discrepancy or weighted discrepancy,
is strictly generalizing previous definition that
we have been giving still in the context of drifting,
with Andres Munoz Medina or for Domain adaptation,
with and with Karina Cortez.
And that also is related to the notion of discrepancy or
a distance that David and others, and
also and others have been giving the pass.
We can also give upper bounds for this discrepancy,
in terms of some familiar quantities such as the relative entropy.
But again if we were to do so,
we would be losing this interesting aspect of the discrepancy that is
taking into account the loss function on the hypothesis.
We can also give upper bounds in terms of other quantities such as
the five mixing coefficients of asymptotically stationary process
four of course asymptotically stationary processes.
I mentioned that the discrepancy can be estimated, so
let me discuss this here little bit on this slide.
The discrepancy can be decomposed into two parts.
Suppose that you wish to make a prediction at time T plus one.
There's gonna be some interval, say small interval of like
s just before the time of prediction at which you don't expect
the distribution to have changed radically.
So you sort of expect that the blue part, the blue arrow here,
that indicates the difference between the discrepancy if you wish,
between the last time, T+1,
and the average loss within that interval of length, s.
You expect that not to be too large.
You expect that actually to be relatively small.
In fact, I'm going to be a bit further,
you can prove that is this is not the case, learning is not possible.
Okay, so we have to make that assumption that there is going to be
some s, for which this difference is not too large.
Assuming that now, which seems to be a natural assumption,
then we can break the discrepancy into by the sum of two terms.
One is the term that I just described,
which at the top of this slide is denoted by delta s,
s referring to the size of the interval.
And the other one is the first term.
Which is the discrepancy between that interval of length s,
and whatever else you have had in your training sample.
And that is the first term that you see, that delta of q up there, okay.
And turns out that that's a delta zero of q.
That delta zero of q, which is the first term upper bounding delta q.
Notice that it's all in terms of the expected loss again, or
conditional expectation that calligraphic L.
And it turns out that that term,
delta zero of Q can be in fact accurately estimated from data.
Not so surprisingly,
right, because what would you do if you were to estimate it?
Well you would consider the same term,
with the catagraphic l's replaced by the true loss.
The losses you've observed on the sample.
Turns out that is actually a very good estimate of this
quantity, okay.
So now if you use this notion of weighted
discrepancy that I introduced.
Which again, essentially comes from the first principles.
And you apply some general tools that I will briefly describe,
you obtain the following learning guarantee which is very general.
This theorem says that, with high probability for
all hypothesis h and capital H.
And for all alpha, alpha I think of it as a small number, let's say 1/T
or 1/ square root of T, where T is the size of your sample.
So, for all hypothesis, the left hand side that is
the path dependent expected loss of the hypothesis h.
The quantity that you wish to minimize is upper bounded
by the first term, which is the weighted
training loss where the weights are these Q sub Ts that
you might wish to play with algorithmically.
Plus a term that is exactly the weighted discrepancy.
Alpha or two alpha, I already said,
you can essentially disregard it as being a small number, plus
the norm of the weight vector, q1 qt, that you consider.
Think that if you use uniform weights,
that norm two of q is just one over t.
Okay one of us score of it and then the square root of 2 times
the log of a quantity that is the expectation of a covering number.
Okay I think I've scared you enough now
actually raise your hand if you're not scared yet.
Okay, I managed to scare a few, then.
So this is the expected covering number.
For now, just think of it as a measure of the complexity
of the family of hypothesis capital G.
Which is the family of the losses of the hypothesis little h.
That's what's indicated in the bottom.
This is the family of functions that are mapping Z
to the loss of h comma Z.
The exact definition of this sequential covering number, or
expected sequential covering number, I will try to just say a few words
about a bit later, but for now think that this type of learning guarantee
Is actually not very different from what we have seen up to now.
What does it say,
in short it's simply saying that the generalization error is bounded by
the empirical error plus the last term is just a complexity term.
All of these familiar, the only term really is that weighted discrepancy.
Okay, the delta of q.
It turns out that that delta of q is really crucial.
In fact for some scenarios, say drifting for example,
you can show that you cannot do away with that discrepancy.
It's essentially the best measure here that you can
come up with, okay?
So the discrepancy is really there.
Furthermore, and Vitaly will get into the details of this,
is sort of learning guarantees can really directly guide
the design of our algorithms.
How?
Well the choice of the hypothesis little h and the choice of these
weights q one qt that I mentioned are really, really crucial here.
Can be precisely following this bound,
if you wish to minimize this bound.
Again, Vitaly will say a lot more about this.
Now there is still a problem here because delta
of q is that true discrepancy.
We don't have that true discrepancy, but
the good news is we can estimate it.
So we just have to work with the estimate of that.
To result I mentioned that before the discrepancy can be estimated and
there is an other learning bound
that is in terms of the estimate of that discrepancy.
So that's the delta hat of q.
Which previously was denoted
which was the estimate of that delta zero of q.
If you look at that delta hat,
it's just precisely the same expression as delta zero of q where
I have replaced the calligraphic l by capital L.
Okay?
So it's just precisely the empirical version of that.
So this learning bound,
which only defers from the previous one by the presence of
the empirical discrepancies versus the true discrepancies
is going to be a quantity that now you can directly work with
when it comes to algorithms and when it comes to guarantees.
This learning bond is probably the first
learning guarantee that is given for general stochastic processes.
There is no assumption about stationary or mixing.
The quantity, really, that is critical here is the discrepancy or
the weighted discrepancy.
And, again,
I have already said what I thought about deporting of those weights.
Okay.
So, if you have survived so far, you've already
had the main take aways from this theory section.
But now, I'm gonna say a few more words, and
that's only for those who can still survive, but
the definition of the weighted sequential covering number.
To tell you that in the case of stochastic processes,
we cannot just use the standard covering number.
Instead, we have to have a sequential version of that.
So a sequential,
with a sequential cover of a tree is defined as follows.
Suppose you have a full tree,
such as the one that is displayed on this slide.
And a full tree of depth capital t.
And let's call that tree, bold z.
That means that every node of that full tree
is labeled with some element of capital z.
Z1 for the root.
Z2, Z3, etc., etc.
And what a cover of that tree is, is a set of tree capital V.
Such that no matter what path you choose in this tree, for example,
if you were choosing the red path there would be a tree in capital V.
A tree v capital V such that along this path, the vector v and
the vector of g of z's would be very close to each other.
In fact they're know more of the differences with these
vectors will be bound by alpha divided by norm of q.
Okay, that's for example, what's indicated in the corner
bottom corner of the slide for the particular red path.
So when that falls in general, that means for any tree Z, where you
label the tree with the Zis and their existing v such that you can
be closed to that g of zs along that path when this is true every time.
Then they cap, the family of trees, capital V, provide
a alpha cover of a sequential alpha cover of the tree Z, okay?
So, what we would want is not just any family capital V of trees.
We want the family capital V of trees that has the smallest
cardinality, okay?
The family capital V that has the smallest cardinality and
that can cover Z is the sequential covering number of the tree Z.
That's for a particular tree Z.
Really what we care about is not just any particular tree Z,
is the expected covering number.
We take the the expectation over z, over all the trees.
And so to describe the expectation,
I'm just going to describe it briefly on this slide.
Look at the tree now that is shown here.
You can play the following game at time one which is at the root,
you can draw two samples if you want Z1 and
Z prime 1 according to the distribution.
And then if you go to the right, you can draw
a Z3 and Z prime 3 again independently, but
conditioned on the prime variable, Z prime 1.
If you go to the left, you can draw Z2 and Z prime 2 independently,
but conditioned on the Z1 and so forth.
So the expectation of the covering numbers that I talked about,
that's an expectation over Z where the Zs are drawn according
to the stochastic process that I just described, okay, all right.
All of that looks a little bit complicated.
It's not a surprise, right?
We're dealing with a much,
much more complex situation in the time series prediction.
We are far away from the easy ID case where we can just apply
blindly a whole bunch of learning theory tools.
Now we have to do a little bit more work, okay?
So if I have still some time, and I'm not sure how much I do,
I don't see anybody jumping on me, so I'm just gonna say a few words.
I have two minutes.
Then in those two minutes.
>> You have 15 minutes.
>> I have 15 minutes for the theory section?
>> [INAUDIBLE] >> I have what?
>> [INAUDIBLE] >> Okay, so it went from 15 to 2.
>> [LAUGH] >> See,
this is the way negotiations go.
So, you can see, I should not negotiate anything.
So, I went back to two minutes and
that's perhaps also what you would prefer, right?
We should just- >> [LAUGH]
>> You've
been suffering quite a bit.
Let me just say, we've decided that you would have a longer break here.
So, you really deserve it after this, but
hopefully you got the big picture.
So, I'm just gonna give you some really just the high level ideas for
the proof of that learning bound that I just threw at you.
So the way the proof starts is in the standard way of applying
a Chernoff bounding technique which consists of introducing a variable,
a positive scalar t that you would wish to optimize,
near the end of your proof to get the best bound.
And simply of applying Markov's inequality.
So this part is really not so difficult.
Next, you have to come up with a symmetrization.
And here again, I'm just gonna give you the high level ideas.
The high level ideas and the deep techniques behind this
relate to the notion of decoupled tangent sequences.
For any sequence Z1 Zt, there exists a tangent in associate sequence
Z prime t, Z prime 1 t, that is a tangent sequence associated to that.
What does that mean?
It simply means the following,
the sequence Z prime T is such that Z prime little t and
Zt are independent, given the pass Z1, Zt minus 1.
So imagine that you in fact draw Z prime in this fashion.
Whenever we have reached time t,
you draw Zt of course conditioned on what you have seen so far,
but Z prime t also in an independent fashion.
Okay, so it's clearer that you can always construct that decoupled
tangent sequence.
This way of decoupling, coming up with a Z prime that decouples and
has this independent aspect to it is crucial to the proof and
the analysis, okay?
So that's what is going on on this slide.
In the next slide, it's another property of tangent sequences
that we're using for the introduction of variables.
And then in the last slide, we are making use of that
somewhat complicated expected sequential covering number
that I mentioned by applying a standard union bound, okay?
So I just gave you a very, very high level idea of the proof, but
it's essentially what you would really need.
And as Vitali mentioned,
of course you will be able to look at these slides and
look at the details to be convinced that indeed the proof is correct.
Okay, so I'm gonna stop here and I wish you a long break and
when you come back, though, you will hear about how this theory
can be use effectively to come up with algorithms.
Okay, that have strong guarantees now, and
Vitali when I describe that.
Okay, thank you.
>> [APPLAUSE] >> Okay,
so, let's get settled in and let's continue and
talk a little bit about algorithms that one can develop
based on this theory that we have discussed before the break.
And I hope you're all not too scared by it.
But the bad news is that actually I'll have to
show a bit of theory for you again but don't be discouraged.
This is just a review actually so
you should all know what it is already.
It's actually exactly the same bound that you have seen before the break.
And, just to remind you what it says, right?
It says that with high probability, uniformly over hypothesis
set capital H, generalization error of any hypothesis.
Little h and that set of hypothesis capital H is going to be bounded by
q weighted empirical error of that hypothesis on the sample.
Empirical discrepancy, this discrepancy delta s,
that we hope to be small, and a term that captures
the complexity of this set of the hypothesis that we are using.
I would like to make two important points about this bound.
First of all, we can extend this bound to hold
uniformly over the weights q, in some bounded set.
And second thing that we kinda tried to
emphasize also before the break in the theory section is that
these guarantees are data dependent, right?
And the reason these two points are important is because they directly
motivate and help you derive some algorithmic solution to the problem
of forecasting non-stationary time series.
And the key idea here is to take this bound that you can actually for
each hypothesis compute on the data, right?
And try to seek a hypothesis h in the set of hypotheses capital H,
and the weights q over the sample that would
directly minimize the learning bound on the previous slide.
So this is a very general idea of the algorithm, but
in the rest of this presentation, I'll try to argue that actually for
certain very broad families of hypothesis sets and loss functions,
you can solve this kind of optimization problems efficiently.
And the first set of hypothesis that you may think about and
the first set of hypothesis that
you may be interested in is the set of linear hypothesis.
So we'll consider a set of linear hypothesis with squared loss.
Just to remind you, the squared loss is L of y.
y prime is defined to be y- y prime squared, right?
Something that is very natural for the problems of forecasting.
And linear hypothesis or more general kernel-based hypothesis
associated with PDS kernel K are defined as follows, right?
We take a feature map that is induced by this PDS kernel, right?
Or simply you can think maybe of linear kernel, right,
in that case, this is just an identity map.
We map our observations X by this map,
phi K to some Hilbert space, right?
And our hypothesis is going to be simply a linear function,
associated to some weight vector w.
And it just takes the dot product of that weight vector w
with the representation of our observation in the Hilbert space.
And we'll control the complexity of this
linear hypothesis by restricting the norm of the weight vector
using some parameter, capital lambda.
So this is a very standard set of hypothesis that is used everywhere
in machine learning.
So, for this setting of time series
sequential models, you can actually upper-bound that very scary
sequential covering number term that appears in the learning guarantee,
in terms of the parameters of this hypothesis set and the data.
In particular, I give a bound here on this slide,
that this complexity term is bounded in terms of this
parameter lambda, that controls the norm of the linear hypothesis.
And the radius of the PDS kernel on the data,
the supremum of the kernel (x,
x) over all the x in the sample.
We are also gonna make another simplification.
And instead of considering the empirical discrepancy directly,
we will look at what's known as instantaneous discrepancy.
And you can, in fact, upper-bound the empirical discrepancies
that appeared in our learning guarantees by the sum of qtdt,
where the sum goes from t = 1 to capital T,
plus a term that captures the division of
the weights q from uniform weights in L1 norm.
And these dts,
in this bound, are what we call instantaneous discrepancies.
And they're exactly the discrepancy between the most
recent s observations that we have in our sample,
and an observation at time t,
that's the definition of dt for each time t.
Again, I'm not gonna go through the proof of this result here,
but you're welcome to look at it at your free time.
And this is actually a very simple result that just uses
sub-additivity of supremum.
But what is important to actually discuss here is the computational
aspects that are involved in estimating discrepancy.
Can we actually compute these quantities?
We said that statistically,
we can estimate them but it doesn't mean that they're computable.
Well, if we look, actually, at the definition of this, for
instance, instantaneous discrepancy dt, at least in the case of
this kernel-based hypothesis with squared loss then we'll
arrive at the following, perhaps also scary-looking expression.
But let's take it apart, right?
What this expression tells us is that, to find instantaneous
discrepancy we need to solve a certain optimization problem, right?
And the objective of this optimization problem that we need to
solve consists of the two terms.
In fact, it's a different of two convex functions,
which means the optimization problem that we're going to
be solving is a DC programming problem.
And we can use existing machinery for
solving these kind of DC programming
problems to find what discrepancy dt is.
But what is even more important, that in this special case of squared
loss, one can actually use special DC algorithms,
difference of convex function algorithms,
that would allow you to recover a globally optimal
solution to this non-convex optimization problem.
And this is important because it allows us to efficiently and
accurately compute discrepancies that are gonna be critical for
our algorithms, as you will see.
So, okay, let us put all of this together.
So first of all, if we put all of this together for
the special case of the kernel hypothesis with squared loss
function, we have this learning guarantee.
Which is almost the same as what we've seen before, except we
replace the complexity term with this
other upper bound that I have discussed earlier.
And we also have an additional term in the bound
that comes from the fact that now
this bound holds uniformly over all the weights q.
But this bound, now, can be computed efficiently on the data, because its
data dependent learning guarantee, and all the terms are computable.
So there is a corresponding optimization problem that
needs to be solved in order to
find the hypothesis that is going to be used for forecasting.
And the objective in this optimization problem
is going to consist of
the following four terms that directly come from the upper bound.
So the first term in the objective is your empirical
q weighted L2 loss, right?
Very natural.
The second term is the q weighted sum
of the instantaneous discrepancies, that we know how to compute.
The third term in the objective is the regularization term for
the linear hypothesis that we're going to use.
And it directly comes, actually,
from the complexity term in the bound, right?
And the last term controls the deviations of the vector q
from a uniform distribution.
And it serves as a regularization for
this parameter that we're optimizing, right?
Here also, lambda 1, lambda 2, and lambda 3 are just
hyper-parameters that you set via cross-validation.
Note that this optimization problem is joint over both q and w.
And, at this moment you may be thinking, wait a second, is it okay,
is the optimization problem easy to solve, is it convex?
And in fact, that's a very right concern, in fact,
this formulation of the optimization problem is not convex.
But you can alter this
optimization a little bit to arrive to a convex formulation.
In particular, what you can do is you can change the variables and
set rt to be 1/qt.
And then if you further upper bound the regularization term for
the q's that appeared in the previous objective,
then you arrive to this new formulation.
And it's almost exactly as the previous formulation,
we still have the first term, which is a weighted
empirical error, but now the weights are 1/rt.
And this is, I remind you, a convex function in w and r,
because this is a square over a linear function.
Then, the second term is this weighted instantaneous
discrepancy term, but now the weights are 1/rt.
Again, this is going to be a convex function for the same reason.
And the last two terms, these are regularization terms,
L2 norm and L1 norm.
And they are still going to be convex.
So, overall we get a convex formulation for our problem.
So that's nice.
Let me also mention that there is another way to obtain sort
of simpler algorithm that does not learn q's and w's together, right.
But rather, does it in a two stage procedure, and
it's also going to be convex.
And the way this algorithm operates is that you first just minimize
your discrepancy empirical discrepancy on the data of this way
you would obtain after Q right and
this also can be shown to be a convex problem.
And once you have done that, you take this vector q and you solve
a weighted version of a kernel-ridge regression problem.
Which is again, a standard convex problem.
These are the algorithmic ideas that you can use for
forecasting non-stationary time series.
And we actually implemented some of these and played around with them
both on some synthetic data and some real data sets,
and I will now describe some of the experiments that we've done.
And let's start with just some very simple synthetic examples.
Just to get some intuition about how these things work in practice.
So on this slide, I plot for you a very simple stochastic process,
which is basically autoregression of order one, with a slight twist.
So for the first thousand observations, I set the parameter,
the autoregressive parameter, in this model to be 0.9.
All right, the autoregressive coefficient.
And then, for the next thousand of observations,
I switch the parameter to be negative 0.9.
And then I switch this parameter back for
the last thousand observations to be 0.9 again.
And so this way I introduce this nontrivial,
nonstationary in the stochastic process.
And it's interesting to see how the estimation of discrepancy
behaves in this kind of scenarios and how our algorithms work.
And what we can do, we can look, actually, at the plots of
the discrepancies that would be estimated for this kind of process.
And you can see they're plotted on the left of this slide.
In red, you see the estimated discrepancies, and
in green, this is the true discrepancy.
And you can see the estimation is actually rather noisy, right.
But at least it gets the shape right.
You can see that in the region
between T equal a 1,000 and T equals 2,000, right.
Where I had this switch.
At least the average discrepancy is much higher than in
the other regions.
But what's even more interesting is that these
algorithms can actually be quite robust
to these errors in the estimation of the discrepancies themselves.
So if we actually look at the weights queues that are learned
by this algorithms and they are plotted on the right of this slide.
And you'll see that in red we have the weights that were learned for
estimated discrepancies and in green we have
the weights that have been learned for the true discrepancies.
You can see that in both cases,
the algorithm completely avoids the region
where t equals 1000 and t equals 2000.
Which is exactly what we would desire, because in that region,
the distribution of the process is completely irrelevant to the most
recent observations which would be useful for casting the next point.
And just to wrap this section up.
Here are some further examples of the error plots
for this artificial synthetic data.
What we see here is running mean squared errors, so
what we do we train our three algorithms which
is ARIMA, the discrepancy-based forecasting with true discrepancies.
And discrepancy-based forecasting with estimated discrepancies.
And once we trained them on the first 500 points,
we forecast the next 25 points I believe.
Then we record their error,
we put this new 25 points in the training set.
We're gonna train with this new training set.
We forecast the next 25 points and we proceed in this online session
and then we have this running flow to means squared errors.
And as you can see, before we encounter any non stationary
in the data, these algorithmic are sort of behaving about the same.
But then once you kind of heed this non-stationary.
As you would expect,
the error in a Arima model that is not designed to handle
this kind of no stationary can blows up but these algorithms is kind of
remain robust to this non stationary change in the distribution.
So, to mention this, we did some also experiments with
some real world data sets and there are some promising results there but
they see that I am running out of time actually and
instead what I'm gonna do rather than talking about these I'm gonna
invite and he's gonna talk.
>> [INAUDIBLE] >> Yes, yes, sure.
Thank you.
Well, since I have some more time, we did some experiments.
Some data sites that we found on the internet.
These are commodity prices for different commodities,
exchange rates, climate and temperature forecasting.
And as you can see from these results, we compared ourselves
against very standard baseline that people would first compare
themselves, Arima models and at least against those models.
We never perform worse than ARIMA models.
And in I think five out of eight datasets here we do better.
So this is the algorithmic section.
And next what we're going to talk about is the connection between
sort of time series prediction and this new hot area that people
very interested in these days that of online learning.
>> Okay.
So we switch gears and try now to, after this
theoretical section and then the algorithms and the experiments,
to talk a connection with online learning which, as said,
is probably one of the most Important and
fast growing areas of research and machine learning.
Starting by saying that there are really two learning scenarios for
tackling time series.
The first one is probably the one that we favored in our presentation
up to now.
And that is that of the stochastic scenario,
which assumes that there is a distribution underlying the data.
And there the performance measure is in terms of the expected loss,
or for us this path dependent expected loss.
And the learning guarantees are generalization bounds such as those
that I presented previously.
The on-line learning scenario, in a way, is a much broader scenario.
It is one where no distributional assumption is made.
The setup is adversarial.
The performance measure is based on a notion of regret.
And the guarantees are, therefore, bounds on that regret.
This is a very, very active research area.
We've just listed here some papers and names.
Clearly, this is not covering even a small part of online
learning definitely would wish to consult the survey book
of if you're interested in this area.
There is a very rich number of papers related to this.
We are favoring here some papers by or
One reason for that there is a rich online learning algorithms,
family of algorithms for tracking.
For example, that could be relevant for time series, etc, etc.
So, since I'm not sure how much the audience here is familiar with
online learning, I'm going to give you probably the shortest
tutorial That is possible for online learning.
I have a four slide tutorial and then we'll see how we could maybe
use that to connect it with time series.
And solve problems in time series that we don't really know how to
tackle otherwise, okay?
So let me start with the setup of on-line learning.
In the on-line learning setup, it's an adversarial
setting with a hypothesis set or action set capital H.
This goes over capital T rounds, at each round little t the player or
the learner receives a point x sub t drawn from capital X.
He selects in response, the hypothesis H sub T out of capital H.
The adversary selects some label Y sub t.
And the player suffers or incurs the loss of ht of Xt, the prediction
over its divergence with respect to the true label Y sub t.
So the goal of the learner or
the player is to minimize his cumulative loss.
The first term here in the definition of the regret
indicated here at the bottom of the slide.
Now the cumulative loss is sum of the losses suffered over capital T
rounds, minus the best cumulative loss in hindsight.
Now looking back at the data, suffered by the best
hypothesis little h taken out of the family h star.
And the family h star might not always be capital H,
might not coincide with that necessarily, okay?
So that's the notion of regret, which is how much
will be the different in respect to that reference.
Here's an example of an on-line learning algorithm
that's a very standard one, based on exponential weights or exponentiated
weighted average algorithms, people would refer that as well.
Which is a case where you would seek to learn with expert advice.
So let capital H star be a family of capital N experts.
E1, E2, EN.
And denote by capital H, the convex hull of H star.
That means the convex combinations of such expert functions.
The algorithm is quite simple.
It's maintaining some weights.
W1, W sub capital N for the experts.
And so these are index by the time, at the beginning,
this is w1 sub i for expert o and time one.
At the beginning, they're all equal to one.
And then at each round, the learner receives xt,
he predicts according to this average of the functions
of the experts and the averaging is done using these weights.
He receives true label yt, incurs the loss that is base on this
function, this averaging function h of t.
And he updates the weights in this exponential fashion which
consist of multiplying the weight at time T by the exponential
of minus eta, the loss suffered by that expert i, okay?
So the weight of the expert i is updating that pressure.
So if the loss is large,
the weight is significantly decreased for example, okay?
It's a very simple algorithm, but even though it's a very simple
algorithm, it leads to a strong guarantee which is the following.
If the loss function L is convex in its first argument,
which would be the case for a variety of cases in practice.
Let's say for example squared error or
other loss functions of that kind.
And if it's a bounded loss, I'm taking values in 0, 1.
Then for any sequence y1, yt.
This is very strong because it's
not making any stochastic assumption about that sequence.
The regret of this algorithm at time capital T
is upper bounded in the way that is indicated here.
Log N over eta plus eta T.
And if you choose eta in the best way,
eta is this learning rate that appeared in the exponential.
It says that the regret is upper bounded by roughly,
the square root of T times log N.
So to understand what this means, it simply means that
if you choose a relatively large set of experts.
So if your capital N is relatively large,
then this would give you an opportunity for probably having
a best expert in hindsight that has a small loss.
On the other hand, you pay for this in terms of this upper bound log N.
But the price to pay is only logarithmic, so it's very favorable.
The regret is perhaps not even the term that you would really
be interested in.
It's even more precisely the regret per round, so that means when you're
dividing the regret by capital T, the average regret.
And here you see then at the bottom of the slide that the average regret
is decreasing as essentially 1 over square root of T.
Okay, so these are the types of guarantees that you would see for
a variety of algorithms in online learning.
Again, very general set up, very general guarantees.
The proofs for these sort of guarantees go as follows.
You define a potential, here,
the natural potential function is the log of the sum of the weights.
Then essentially, you've proven upper bound for
this potential function and the lower bound.
You compare those two and that gives you the regret bound,
here to derive that upper bound, you start by analyzing
the difference of the potential at time T and time T minus 1.
It gives you the log of ratio of two ways the denominator is the previous
ways, the numerator is the new ways, which are exponentially updated.
And that you can relate to in fact, in expectation in terms of some
weights, you have applied Hoeffding's inequality and
that gives you the type of upper bound at the bottom.
You sum up these difference and using coscopic sums,
that gives you immediately upper bounds on 5T minus 50.
You can trivially come up with a lower bound by saying that the sum
can be lower bounded by a max.
And that is the two lines that are mentioned in the middle of
this slide.
Comparing these quantities immediately gives you the bound.
Okay, so this is just a very quick tour through online learning,
probably the shortest tutorial you have
ever heard of online learning and you would ever hear probably.
This raises though a whole set of questions.
Can we explore it, both the batch scenario,
the stochastic scenario and the online learning scenario to come up
with flexible algorithms for tackling time series prediction.
One reason for that is that online learning setup, as I indicated,
is in fact very rich.
I mentioned this way of measuring the regret with respect to the best
expert in hindsight, just to tell you a few words about this.
You can extend this to the case where in fact you would not
just be comparing yourself to the best expert in hindsight.
But to the best expert that is varying over time to
the case shifting best expert.
The top of algorithms for
these sort of scenarios have already been analyzed.
These are rich family of algorithms that you can pick from.
They're all simple to implement.
They're based on simple updates such as
the exponential update that I indicated before.
So they're really easy toolbox that you wish to use.
So can we use these algorithms to come up with good solutions in
this stochastic case for time series.
Another crucial, it turns out, the usefulness or
question that comes up in this scenario is that of, can we tackle
some really, really difficult time series problems that up to now,
part of these we have been sweeping under the carpet in a way.
Which are for example, model selection in time series or
learning ensembles in time series prediction which
is a crucial problem again in this series.
So let me say a few words about model selection and
learning ensembles and
then see how we could gradually tackle these sort of things.
Model selection is this general problem of course that
we have in machine learning which consist of say,
if you have capital N models, your time series models.
The question is, how can we use a sample Z1,
ZT to come up to find a best model to choose among these models?
In the i.i.d case, this is a familiar problem,
how we have theory such as the structure of risk
minimization theory about model selection.
And we know that those guarantees can be approximated
by using cross-validation techniques.
Uh-huh, reserving some part of the data violation and using
that to pick the best parameter, for example, but how do we do that?
How do we do validation sets?
Come up with the validation set for
general statistic processes in time series.
How should the validation set be chosen?
The last few points, if we do so, we are discarding everything else that
we have seen before that could have been really, really relevant.
If we choose the first few points,
then we may be losing more critical information because
that's really information that would be close to the predicted time.
What else should we do, split the data in various different ways and
choose those as validation set?
It's just really not clear what we should be doing.
By the way, if you hear people talking about time series and
saying, we're doing model selection in some way, cross-validation or
something, ask them, what is it that you do?
Because I bet you there is no real principle behind it, okay?
I noticed that the problem can be complicated in the sense that,
of course, these models had been probably pre-trained
on that same training sample, okay?
It's another interesting problem that comes up if you wish to do
accurate prediction.
To answer this prediction in any kind of context, whether that is for
earthquakes as I heard a little bit from some people here,
whether it's for predicting the level of battery for your system,
or, I don't know, making predictions in Wall Street.
That is the one where imagine that you have already a family of
good predictors, a family of good forecasters.
Can you use them to come up with a good,
perhaps a better and more accurate solution by combining them?
By taking a convex combination of them,
sum of QTHT if the HTs are your forecasters.
Again here it's not a trivial problem because this
forecast with the HTs may have been even pre-trained or
they could be the result of training on that sample.
It turns out that both this model selection problem that I mentioned
and the problem of learning ensembles They can both be
tackled and addressed by coming up with a solution to
the so-called problem of online-to-batch conversion.
Online to To batch is a familiar term and problem for
those of you who are familiar with online learning.
But here it's a much more difficult problem,
because we're dealing with a non-stationary, non-mixing processes
that are quite different from the sort of IID cases.
So let me just first define what an online to batch
Problem consist of and how it can be tackled.
But before even doing so, and just to make sure that I'm not gonna
run out of time for saying that, there is going to be a time series
workshop here at NIBS, and I invite you to attend.
This is also co-organized by Vitali and several other people And
I will be describing in much more detail some of
the solutions here and connections between online learning and
the stochastic case int that workshop.
So, let me go back to online to batch problem.
The On-Line-to-Batch problem is a very natural problem.
Let's denote by bold h.
The sequence of hypothesis that an online learning algorithm has been
returning or outputting over the course of capital T rounds.
So the problem is to come up with a hypothesis.
Okay, so I'm a little bit confused here, okay, so
this is what the input is to the problem.
That's why, that's the input to the problem.
And the problem is to come up with a hypothesis.
Little h and capital H, that has small path-dependent
expected loss, using these hypotheses h1,
h2, hT, that the online learning algorithm has been producing.
How do we use those
hypothesis that the on-line learning algorithm has produced?
Use them to come up with the hypothesis that now has a good
path dependent expected loss.
This is not any more a matter of regret, okay.
In the setup,
this problem is well known and has good solutions.
But again, how do we design solutions here for
this general time series scenario?
One question is even to batch with general non-stationary,
non-mixing stochastic processes even possible?
Can be design algorithms with guarantees.
And here agin we need a new tool,
that tool is not surprisingly similar to what we discussed before.
It should be, it's similar it's a discrepancy tool.
But there is a new twist to it, because here.
We're not dealing with arbitrary hypothesis.
We're dealing with hypothesis that
are output by the online learning algorithm.
So if you look at the same key difference that key difference now
is for
a particular h sub t that is output by the online learning algorithm.
Okay, and so when now we are taking the averaging.
We're not gonna be taking the averaging over
that's a fixed h sub t.
But the h sub t that the online learning algorithm has been
producing at each timestamp little t.
And that's what the quantity that is in the bottom of the slide
indicates.
Now that's the average difference here.
That's the difference.
You see the H of T varies with the time here.
That leads to a notion of discrepancies against starting from
first principles, right?
That is similar to what we saw before
It's a supremum now over the choice of some hypothesis.
But it's a supremum over the bold age.
That means the supremum over that sequence, h1, h2,
h sub capital T, of this weighted difference.
The gain here, the weights q sub t are crucial.
They're going to serve as in the same as I indicated before,
to do In short make use of the fact that some hypothesis,
h sub t at time t, are much more useful to my prediction
time at time t plus one than others and
the weights are gonna help me emphasize or deemphasize them.
So this is a very natural measure of non-stationarity or
dependency as in the stochastic case.
As in this stochastic case,
it captures the hypothesis set and loss function.
And as in the stochastic case,
it can be estimated with some mild assumptions.
In fact, pretty much doing exactly the same as what I indicated before.
But you'll see that there's even another way of
estimating the online discrepancy.
That is quite interesting.
So, I will briefly touch on that.
And this discrepancy definition is a generalization of the type of
discrepancy that I need to do before.
So quickly speaking, we could use the same methods for
estimating the discrepancy as indicated before.
For the stochastic case.
But here there is an alternative method
that is very close to the online learning view.
Suppose that the last function is mu-Lipschitz.
And suppose that there exists actually an hypothesis h star
that has a small expected loss.
At time t plus 1.
That's the conditional expectation.
Let's denote by eta that expression.
Disregard the little q here.
It should not be here, by the way.
It's not eta of q, it's just eta.
So we can assume that there is a very good solution at time t plus 1.
That means that that eta, the best expectation Loss is actually small.
If that is the case then you can actually show that the discrepancy,
the left hand side in this bound, can be upper bounded by a term,
the hat term, the discrepancy hat term, the empirical one, plus
Mu times that eta plus a term that is
small as I indicated before to alpha and a complexity term.
So definitely the discrepancy can be estimated here
essentially by making use of the fact that there would exist.
A good hypothesis there exists, but I don't need to know it,
that good hypothesis that has a small error here.
Okay, so showing this turns out to be actually simple.
You start with the definition of discrepancy.
You break it into two parts to make the discrepancy Expression appear,
you use the additivity,
subadditivity of the supremum to break it into two.
You use the of the loss, and
then just the fact that the q t's sum to 1, okay?
Now, it turns out That the online tool patch
problem here admits a very nice solution here as well.
If the loss function L is a convex loss and
is upper bounded by capital M, then simply choosing
the hypothesis that is the average of the hypothesis returned
by the online learning algorithm Sum of qt ht.
That sum admits a very good guarantee in the stochastic way.
That means, with high probability, its path-dependent expected loss is
upper bounded by an average of the training sample losses,
the sum of qt L(ht, Zt) plus the online discrepancy,
plus a term that depends on the upper bound of the loss and
the norm of the weight vector, which again, you can think of as being
essentially close to 1 over square root of T.
So this is a strong learning guarantee for
the online to batch because it tells you that it is possible even in
this scenario to combine hypotheses to come up with a good accurate one.
I'm not gonna go through the proof, but it's just really two,
three lines.
What is even stronger is the following guarantee,
again in the case of the convex loss function,
which says that for the same hypothesis h,
the path-dependent expected loss can be upper bounded by
the loss of the best expert, or the best sequence, H*,
plus the discrepancy plus a term that is the regret per round,
which we showed can be upper bounded in many cases in online
learning by a term of the form 1 over square root of T.
And other terms that you saw appearing already in
the analysis that Vitaly showed,
in terms of the weights that are used in the stochastic case.
Okay.
So the high level idea here is that online learning
can be used to produce a whole sequence of experts, h1, h2 to T.
Those experts can be combined using some weights, Q1,
QT, to come up with a very strong hypothesis in the stochastic case.
The guarantee for that hypothesis is given here,
same story as before, we can choose those weights Q1,
QT in the best way to minimize that upper bound.
These are things I will be able to describe in more details if you
attend the talk I will be giving in the workshop.
I'm going to stop here and
conclude with the following remarks about time series.
Time series forecasting is a key learning problem
in a variety of important tasks,
which I've mentioned many of them in the beginning.
Most of the data that we're facing today
are in fact sequential in nature.
So time series would be the natural way of formulating the problems.
At the same, time series prediction in the most general case
is a challenging problem, both from the theoretical point of view and
the algorithmic point of view,
if you want to come up with good solutions, accurate solutions and
solutions from which you can give guarantees.
Okay.
This is, of course,
a very challenging problem also in applications.
And you know that in a variety of cases,
people would want to have very accurate solutions for
a variety of tasks of this kind for sequential data.
What Vitaly and I presented is a series of learning guarantees,
data dependent learning guarantees for
the very general case of time series prediction,
non-stationary, non-mixing, no assumption.
The notions of discrepancy that you heard multiple times in this talk
are really really crucial for tackling this problem, both from
the theoretical point of view and the algorithmic point of view.
We discussed algorithms, guarantees, and
showed also that these algorithms in practice can be effective.
The combination of online learning and batch, or stochastic prediction,
leads to a whole other set of very, very interesting solutions.
I tried to say a few words about them to sort of tell you how
this could be done.
In particular,
this can be used to solve problems that are really difficult.
We don't really know how to tackle them otherwise for
model selection or learning ensembles.
Again, these are things that I could talk about a lot more.
And let me finish by further advertising this workshop.
It's Friday, and it's in Room 117. Okay.
Thank you.
[APPLAUSE]