Player is loading...

Embed

Embed code

Transcriptions

Note: this content has been automatically generated.
00:00:00
ah our ah ah to sort of talk exactly okay so
00:00:07
every yeah is a professor of economics veteran a a
00:00:10
recession rec arts interacts in paris uh i know finishes cage to some time ago thinking two thousand five
00:00:19
uh from our our it's a very nice uh next customer phosphor also
00:00:25
has a very in depth knowledge of machine or computer vision room
00:00:30
the graphics in a number of topics every day for them so i would like to uh the room or
00:00:37
just to uh on the line for peaceful it's a string on our mutual
00:00:43
and also that it's uh this invitation is cosponsor with their with their goals
00:00:50
thank you very much happier for coming and i'm perfectly okay thing so that's it's uh
00:00:58
a real pleasure to be here
00:01:00
so what i will do today is kind of um june on pollution
00:01:04
to this a few little commandments barton illustrate with reputation meaning uh
00:01:09
national name so wanted me to have some senior that is not clear my
00:01:13
goal is to convey a bit of the id from the algorithmic side
00:01:17
and to try to see how it interacts oh of course with a with a with optimisation and mathematics
00:01:22
so this is a joint work with a lot of callings uh most on top couple portly
00:01:26
a market actually with maya 'cause colour bought or on this idea of approximate ultimatums bought
00:01:31
uh many other than to actually those over to get a piece of order
00:01:35
especially when they were speak about uh the sample complexity in high dimensions okay
00:01:40
uh before starting a bit of advertisement for this book uh that that what we sow marco
00:01:45
oh that can find online so everything that was said say today you can find it in this book was much more the terms of course
00:01:52
well it also includes some caught than links and references so feel free to go there's also slides for courses and so on
00:01:59
i prefer to go to have more information also before starting you know why should we care about uh uh
00:02:05
probably this would be shown one could our the empirical material but i guess because in many application it's quite
00:02:11
natural to frame the problem oh using just one weight of distribution these are just a few example
00:02:17
but in those just one i know dimension for emitting sciences we should think about the colour palette
00:02:22
of image this is just the each pixel disappoints would like the empirical description of the coral
00:02:27
and if you want to modify the corporate change it is going
00:02:30
to be uh the point of comparison modification of of distribution
00:02:35
a famous line of ideas for distribution of mass constant of activity in the brain phone was science
00:02:40
for shape matching shape registration it's also very not to want to move the the shape and the
00:02:45
description of mass the description of feature could also think about the description of curvature of normalcy
00:02:50
so it's quite natural or oh two uses two distribution of feature using the language of nancy to
00:02:57
and this is no high dimensional problems that this would be a natural language processing
00:03:01
uh where you want to more than a copies of documents and it's document
00:03:06
will be more they're using the description of something and the simple no idea
00:03:09
is just a description of the said oh well the company page documents
00:03:13
so here's the sizes rejoice proportional to the number of times the well the
00:03:16
appears in the text books very simple push you can think about
00:03:20
morgan places revision but then you would compel the documents by comparing this bible features is by the word
00:03:26
this would be for uh for instance for our clustering off or should always know name
00:03:30
um and the same line of ideas uh is in uh unsupervised longing for instance for a modern images
00:03:37
so here's the most on the stone in some in some way to description of all the major points on
00:03:42
on the internet you know though to draw some new we may joke to solve some problems with it
00:03:46
and you'd like to more there's very very high dimensional distribution of point of images
00:03:51
oh it's very ah ah a lot of space so here once again
00:03:54
an actual wage for unsupervised learning is the language of distribution
00:03:59
okay so just to be a bit more precise what you would typically have oh oh to sort
00:04:04
out the problem for fountains and should always be owning is your given the distribution of
00:04:08
points of observation and you will want to more there it's using some kind of an l.
00:04:13
c. d. and uh in the politics it is it would be permit tries but
00:04:17
uh to to hear when you want to find the best that also that this red l. c. t.
00:04:21
match as closely as possible the input okay 'cause would be like a classical problem of parameter estimation
00:04:27
um typically him very simple so that you can choose abortion and then put that would be the mean in the finals
00:04:33
but of course no though to model more complicated that assets you want want to lose more by may tell more complex
00:04:38
more they're typically deep longing with those are are used for this task and now it becomes a a non korean
00:04:44
and actually very difficult to find the best data to model the distribution okay and of course what user be on this
00:04:51
is the loss function you like to use to make the feet the question is how
00:04:54
do you uh compel this so red description to this blue distribution using some discrepancy
00:05:00
okay and this is basically the the core my talk is what kind of discrepancy you would like
00:05:05
and the id sharing all the talk is to make use of some
00:05:09
unknown in german should do you like to do some discrepancy she'll
00:05:12
gee that is really dramatic or that is able to uh make these
00:05:15
guys together of as good as possible by exploiting some rage
00:05:20
about uh where you're that that it could be for instance so if you think about calling just okay then distance between the colour
00:05:26
could you could use more perceptible does not but you can start but couldn't on the shape you could use would you do the distance maybe or something like this
00:05:33
on the space oh well of course is very on the regular with the question
00:05:37
what is the distance between what so that the people working on this but
00:05:40
we could find point in some kind of okay don't bedding for the wealth would make sense to do some kind of a distance between the well
00:05:46
the and the same thing for image very very complicated what is not
00:05:50
what distance between age seventy no that couldn't spaces space of image
00:05:54
and it's really underlying id between all these cablevision of the browning is it try to find ways to me that he made
00:06:00
doing all this feel they actually a very natural for a grown distance between the point
00:06:05
and the goal of the story about americans bought these two lifted his distance
00:06:08
between pairs of point to distance between group of point or between distribution
00:06:13
okay so what i want to come they decided to go to my point about israel tool an automatic tool
00:06:19
to lift a distance between points that you typically up in your condition two or more complicated distant between uh
00:06:25
a set of points or or distribution is the main take home message okay
00:06:30
so i want i will give you a boxes is still recall um
00:06:36
or toyota made possible that was evolution i like the uh in the
00:06:40
forty by one controller which was the russian mathematicians or would explain
00:06:44
uh what uh is construction is and then i would speak to what we do work shortly which is
00:06:49
an approximate optimal points bought a which is um somehow related to the work of holding or
00:06:54
that would explain why it's important in high dimension because or the second to commit anything high dimension optimal
00:07:00
control doesn't work so you need to approximate it's in order to have something that uh works
00:07:05
uh impact is for high dimensional uh learning problems right what is the problem
00:07:10
of ultimate transport in the language of control each the goal is
00:07:12
to compare to distinguish and so will mostly probably some discrete distribution but
00:07:16
everything that i say works for arbitrary continued was that you were
00:07:20
so in this this quit long wage what is the distribution is just a set of points with weights on each point okay
00:07:27
so the excite all the position of the points selected yard mass and
00:07:30
a a i is just the weight the mass at each point
00:07:33
so the a. i. r. was it a number and the sum to one because for most of what i would say
00:07:38
we will uh focus on a probability don't it's okay and you like to compare this to a group of point
00:07:44
to get okay and the evolution of control each and you got the nobel prize in economy for this
00:07:49
is to describe this notion of consultation between these uh clouds that uh using what you call the uh coupling between
00:07:56
the point what is the coupling is kind of a non deterministic points bought okay it's an area of number
00:08:02
okay so if you have an element in a and and in the it's
00:08:06
going to be an actress aside and time at its positive elements
00:08:09
and each time yeah but no they will uh anyone in these metrics it means you want to transfer some ass from here to here
00:08:16
so for instance on the first will you see there is a single and on the wall elements it means
00:08:20
that all the mass of a of this points of the first point gets oneself to this point
00:08:25
so this would correspond to deterministic on spot between these points to
00:08:29
all these point what historically was introduced by um which
00:08:33
more than two hundred years ago but could or would say sometimes you can speed the mass so if you look at the second will
00:08:39
is is that there is to know what it meant it means that it's this simple
00:08:43
math of a get split into two parts get to the might get it
00:08:48
and you get not to this and it's just like uh no that i mean these digit once
00:08:51
they are where there are so many not of mass can be split in in two parts
00:08:56
okay so uh so what do the set of possible caught coupling between a a a and
00:09:00
b. what are they they are uh that of mattresses that up was it either
00:09:04
in that obeys the conservation of mass but is it means it means all the mass of a get transferred to all the men so the
00:09:10
it means that the some along it roll of b. must be equal to a
00:09:15
and the some along each colour on much be equal to be this is
00:09:18
simply conservation of mass during that comes out again time of night
00:09:22
things bechtel a notation it means that the metric speed time one which
00:09:26
will compute the sum room the role should be able to eight
00:09:29
and the transpose of the time one should be able to be these are the two
00:09:33
point the conservation of mass constraints okay and why is it really like a breakthrough
00:09:39
it because this set is very simple it's uh just uni our publicity the constraints and a
00:09:45
fine constraint so this guy is a bit complex at it's a big put your
00:09:49
and complexity will play a key role in order to be able just to have al gore is um and also does jesus or
00:09:55
so the fact that you can't reason that's the so called
00:09:58
a conclusion backup of each of these possibilities business
00:10:03
make one spot a complex problem as opposed to o. wanted to linking the deterministic way the other phone
00:10:10
uh so now yeah the notion of what is the point spots then what would be
00:10:13
easy all tonight on spot would be the best possible coupling that minimise some functional
00:10:18
so you have to say what is the price you pay when you point to a unit of mass home point excite too windy
00:10:25
it can be any number but usually what people would say is uh you give me some notion of distance
00:10:30
between payoff points and i we pay a price which is proportional to the distance local r. p.
00:10:36
where he is someone to go that is typically larger than one okay so historically or
00:10:41
in the work of motor used p. acquire one jack actually very artistically mathematically
00:10:47
but imagine the of the news people too because it much simpler but for no on every
00:10:52
occasion perspective you can use any do you want your do you prefer smaller p. to
00:10:57
avoid giving too much uh everyone's to outliers but it's just you choice okay so a
00:11:02
couple which will be the best possible p. n. y. is it's a very nice
00:11:06
because this is just enough function and this is a convex put it all a consensus is
00:11:11
the first one of the first up every appearance of linear programming okay
00:11:16
and actually also a controlled you got the nobel prize for this
00:11:20
but you could say that george jones it work at very similar time should also got
00:11:23
the nobel prize because don't don't only is the one that created the simplex algorithm
00:11:28
so don't only the one that explain how you can source is actually interact is in fact
00:11:32
someplace i really don't know very efficient ultimate possible so it's good is a combination of
00:11:38
the genius of control vigil proposal complex formulation for that one sport program and don't see you on your exam
00:11:45
but where able to make these bricks who first in economic this was mostly used initially to
00:11:50
model the economics of programs are and where you have a them and and uh um
00:11:56
and uh factories that creates a object so you want to match factories
00:12:00
uh to uh to the men's but of course it's much
00:12:04
more going on today we are using it more for i would explain a machine owning or that that science a problem okay
00:12:11
so just to mention that everything that i say carries over to arbitrary a density is
00:12:16
you simply it is he plays discrete sounds by antagonists and everything that i say
00:12:20
there's no uh no problem it carries over to the discrete story is just
00:12:25
actually a particular case of judging the artery aware use any probability measure
00:12:30
okay so why is is very interesting of course it's interesting because it gives you access to
00:12:34
the principal not which is useful if you want to do want operation but what is
00:12:38
much more important in my mind that gives you access to the values of this program so
00:12:43
if you look at what is the value of this program is defined some number
00:12:47
okay and you should take the ball well one of the appeal this number you define what is often
00:12:52
core the vast often distance also that's often as very little to do with its good name should
00:12:57
be most want to with huge distance and as its name subjects these uh better stand distance is a
00:13:03
distance to the value of this problem did you access to discrepancy between i'll find it out
00:13:08
in particular the value zero if and only if i if i quit without it satisfies it can get out
00:13:14
inequality okay okay with the okay i know tones of disk and so forth and see anyone normally
00:13:19
we just don't didn't worry t. why should i care about this optimal transport distance at or
00:13:25
we should just because it's really a genetic or distance and for mathematical prospective how do you describe
00:13:31
what it means to be genetic or you can you should care about the translation of object
00:13:36
okay and the wood notion of topology that cares about conservation of of object
00:13:40
is what is called the week topology every week stock apology for those
00:13:44
adopt probabilistic it's what is core to combat austen row so if your
00:13:48
your your density of the distribution of the whole non backed all
00:13:52
the topology of the we got onto the bridge of the combatants you know
00:13:55
that everybody use when you speak about fountain that some poly mitterrand
00:13:59
and many joins in quite easy are really using this german technician of components so in time of night what does it means
00:14:05
uh some measure some segments of measure are for and convention you know
00:14:09
or can that we get to another one if and only if
00:14:12
all possible you nothing also little migration of mass com badge to income of of
00:14:17
of of on them by yeah but it means what was your expectation
00:14:21
can they have to uh the limit expectation it's really like a and take it all week notion of criminals
00:14:27
so what is the typical economical example we can add ons is if you imagine the points so gerard
00:14:32
which can they also that it's it's i can just put the c. b. to its and
00:14:37
then the jack masking that in the week sense but it doesn't come down in the strong sense in the sense of function
00:14:43
because because it's not the entrance to the hard but if you think about the most
00:14:46
simple way to compare two distribution the most simple way is just to anyone on
00:14:51
okay if you compute the uh anyone know the difference between two directs so these guys be mine is is the
00:14:57
rack is a tool iraq doesn't overlap then the difference the the mass of the difference would be too
00:15:03
so uh in term of uh anyone convergence but you're not now talking there just one of them
00:15:08
okay so when notion of commandos when you look at object that moves is going to be a the we can batons and
00:15:15
guess what the best often distances away to watch all these grounds so damn of mathematics it means
00:15:20
a distribution converse to another one if and only if the conduct for the ultimate once
00:15:26
it's not the only this now that that is part of the but it's one of the few
00:15:30
that as problems with very important for many application and i will expend specially in high dimension
00:15:35
for answer but i don't think it's very important to be able to be very sensitive to uh
00:15:39
to miss a misfits or two or german click or uh or movements or what
00:15:45
it's really the main reason why we should care about are using ultimate transport
00:15:49
for many problem emerging and uh in machine and get the turn of i want to use this uh whereas a week
00:15:56
combatants right so now that i've explain a bit what is
00:16:00
up to multiple distance whiting button from mathematical perspective
00:16:05
i would question is how do you computed and the values it's quite
00:16:08
expensive except in some simple guide in general it's too big time
00:16:12
okay if you need me to distribution of points and you want to compute the the distance i have to solve or enough program
00:16:18
and for the specific yeah sorry now program optimal algorithms off complex algorithm and there should be complexity
00:16:25
so a table with all but the depend whether any is uh is there is more on that so it's more so for and to the order
00:16:31
of a of a few thousand it's really really efficient so if you're that as that is below a one thousand point or should i mean
00:16:38
still happened to michael but what i would say after is not very relevant at
00:16:42
least if you just want to conclude with zero yeah well documents for this
00:16:46
okay the awesome special case for which can use the fast algorithm to what is the best noisy optimal matching program
00:16:52
it was meant to the case where you have a two distribution of the same number of points with equal weight
00:16:58
it's going to be on critical a description of pointing out in this case you can show
00:17:03
that the optimal transport of quota which is equal to the ultimate part of motion
00:17:07
meaning that you would only a deterministic movement of massive no point will be split in half
00:17:12
it's a very remarkable result um and uh in this case it
00:17:16
corresponds to an a a combinatorial optimisation for which you have
00:17:19
return more efficient and always i'm the most well known algae and diana go
00:17:23
is a very famous and also the option algorithm job very very
00:17:26
clever and and judy full uh optimisation method that works in should be
00:17:31
complexity contract is they are the most efficient uh option here
00:17:35
pay the trigger data so if you are in one d. actually a women's what is is a bit boring uh
00:17:41
because of what what is is really like a flat geometry yeah it's not being really uh interesting uh
00:17:47
if you take points in the simple case where you have to point out with the same number of point in one day
00:17:51
once in the distribution of excels in a grey scale images then the
00:17:55
ultimate hotspot map is obtained by sorting the point from left to
00:17:58
right and mappings of that blue point to the first read point in the second one to the second one and so on
00:18:04
so the complexity of ultimate one spot in one bit and again and it's pretty if you have instead of points you have a dosages is going
00:18:10
to be a distance between the cumulative or non beating that should be
00:18:13
that you are a just distribution which really not very interesting okay
00:18:20
not okay that is our was much when it is over case of motion
00:18:23
in this case the you can have a more efficient algorithm because you can show
00:18:27
that ultimate one spot can be a recast it as a mean cut throat
00:18:32
on this on the graph instead of looking for a um for this basement look for
00:18:37
a vector or feel that would either back the mass not describe it but
00:18:40
uh the addition is it's much more much cheaper so it's basically
00:18:44
a quite a particular complexity okay it's it's nice to know
00:18:48
uh into the ultimate what's actually related to a a partial
00:18:52
differential equation and we'll just basics competition of your disease
00:18:56
if you do not produce a time and you will uh do the consultation
00:18:59
probably filling time between the initial c. d. and the final city
00:19:04
uh this was a opposed by uh to mathematician and i've been them and and when you were one of the
00:19:09
funding for their automatic import and this is uh joe does each between uh yeah and the density
00:19:14
so here grey or black sorry means not of mass okay and a room that would be no
00:19:19
here so it's got the idea uh something that you should not do that on the document what
00:19:23
should be used to want to operate between two uh faces is you get a crazy uh
00:19:28
uh just option but just for fun okay ultimate control does not something you want to
00:19:32
use for a teenage modification is really a new age is not the dosage
00:19:38
right but it's it's fun and it's okay that was did a lot by company logo is a case where you want to map
00:19:43
set of points to well the continue on city in this case is
00:19:46
very close related to what is core optimal quantisation paintings and
00:19:51
allowed algorithm so we're not on the other the does but in this case optimal possible boils down to computing of one oysters
00:19:57
they very nicely with them based on the complication of uh when they said that works well
00:20:01
in in new dimension to once again if you are in the settings are very
00:20:05
efficient with but i think the key question is what happen if you have a genetic
00:20:09
cost not looking and got what about if you are in very high dimension
00:20:13
and more importantly than these are you really interested in computing ultimate comport with arbitrary occurrence
00:20:19
and i would argue that in high dimension it actually not what you want to do because this would not work
00:20:24
in many situation what you guys to have a good approximation of ultimate can spot that would be more stable
00:20:30
and fast talking to and this is what i would explain now so we go now my talk injury to
00:20:35
insist on the i. d. that impresses you never really wants to computer ultimate comport with high precision
00:20:41
okay and the technology that that will promote is a very simple ideas that you can trace back
00:20:45
to uh holding the ah that was using this for a modelling guys on to action
00:20:50
which is ideal gathering a program that is very hard to to to
00:20:53
tonight you would make it simpler might been advising it without
00:20:57
quickly convex printer to to you we would make the problem or kill me more simple to start an error in the settings
00:21:04
in terms of the best on algebraic point of view a regular relation is your
00:21:08
copy the channel will be so i'm but i think the optimal compo cost
00:21:13
which actually is a classic optional hoping i just can't wait here by the input
00:21:17
mass i don't really explain why but it's very natural to use a all
00:21:20
pole p. with respect to the inputs a distribution of mass just a little or
00:21:26
a little too that is is really important that good a mathematical poverty
00:21:31
well uh i i want this is clean but everything can be done for auditory don't so it's not is the
00:21:36
is the temperature on the asian goes to the or compatible to the we approximate the optimal can spot
00:21:41
oh are more and more efficiently with of course algorithm would be slower ones
00:21:45
were really the one i will uh and systems on high dimension
00:21:48
is to have an epsilon that maybe is not too small to be very well versed in high dimensional level within that are very fast
00:21:54
okay i see something nice enough statistical physics if if that is your judgement
00:21:59
possible between point guard is just the optimal match and it's yeah it's
00:22:02
john goes uh increases you have more and more active action one mall stability
00:22:06
and as a large stone units and then we'll expenses paid job
00:22:09
everybody all the particles attacks with everybody and then i i would explain what this unit is but it's a way
00:22:15
to to uh other uh notion that is not that looked much of course that would explain it i mean
00:22:21
in in one the if you want to go but little cities are celebrated dilemma yeah and when you say that
00:22:27
more than components yeah once again take what and the optimal coupling is localised on a basic even that
00:22:33
increasing map here uh and you uh if you want to use a little bit of a batch of what would happen if you
00:22:39
were to be unable or these instead of having a single abide action you would have some kind of a blurry stochastic uh
00:22:46
on to action so the go over it see not just wanted users who seem more more attraction to make sense um
00:22:53
a faster to compute and most labour can of the intrusion now i would describe that go with a
00:22:58
menu which is algorithm become almost hidden much more simpler than uh i'm promoting of some blacks
00:23:04
so when you wanna that already trying once in is that complement the subject and that is really
00:23:08
like before it was very odd to party light and i'll probably with a couple everything okay
00:23:14
uh so what do you do if you look at this is a convex quickly convex optimisation problem
00:23:18
little bit inadequate facts you should i will you your claim is to uh look at your personality condition or to look at the drug
00:23:24
problem which is essentially the same and if you lose the match your your clues i don't mean to pry off all the constraints
00:23:30
uh it's exactly what it was also when you have a pool a minimal probably make thought imported you
00:23:35
what you would find a solution either very nice expression into another dips down there damn of a good distribution
00:23:41
so what is it it's done and accidental tomatoes box is simply exponential minus
00:23:46
the cost to divide it by its your to to begin metrics
00:23:50
the good thing about the classical case of uh couldn't does not this would simply
00:23:53
be a cushion conclusion john okay bodies do not just some exponential done that
00:23:59
and as a tail and it's like this it's it's very easy to to to put
00:24:02
is that your solution uh a couple which solution to this problem also optimal
00:24:08
that was part uh metrics with this little bit of like innovation if and only if you can get it done
00:24:14
in a factor way as the just on that mickey playa really
00:24:18
brains or of rose by some scott are you i
00:24:21
and the colour on my son's kind of you are going down automatics it means that your tonight one spot
00:24:27
should be the gets down and dirty play on the left by they're gonna mappings and on the high by in those are diagonal metric
00:24:33
you diagonally scale the road and the colour which is something that is not a
00:24:38
specific document comport it's a problem very important in that and actually in statistics
00:24:43
you have an area of number and you want to normalise them by normalising the rose and the current
00:24:48
and it's it's not a question is it possible to always normalising area number
00:24:52
get the question is can you normalised and are we on the and number so that's
00:24:56
so the some of the rules and the some of the couldn't stay the same
00:24:59
okay and and so is yes because it's simply a optimisation problems at all with a a solution
00:25:05
and not only it's yes but it's still just a very natural algorithm what you want is to find this you and is v.
00:25:11
such as the rules as to prescribe some and the colour on as a priest quite some
00:25:16
solution up the time one equate if you'll be hides these income of you one v. it as a very nice
00:25:21
uh expression which is this one is going to be you look for you and you look for the
00:25:26
such that this is really not knowing i question old you so this is
00:25:30
a dot multiply it's just the multiplication of each country over the top
00:25:35
so the bechtel you multiply by the back door k. v. so hates matting the committee big engine should be equal to it
00:25:41
so here is just a hygiene of the constraint income of you want and of course you have
00:25:46
the same for the conservation of mass in the other direction you change all of you when
00:25:51
so the question which equivalent sorties graham can you find you envy that satisfy at the same time these two inside and if you
00:25:57
can find them then you have store the or a shooting a program because it if and only if because everything is complex
00:26:04
and it's just the trigger algorithm you just take this one and you could get you by dividing a by this guy if you do
00:26:10
this of course then this equation would be satisfied just thing you that if you look at this content is very easy to satisfy
00:26:17
but the point is if you do this and you will uh typically violate of
00:26:20
cosy also contains what is obvious to satisfy them both at the same time
00:26:24
so what you do is very simple act you can i program you it
00:26:27
yeah it interferes point my no between updating you and updating the
00:26:31
and you really should do this it never works okay thank god you've around with an exit the ami work but you know if you test it works
00:26:38
and actually it who it has been proven by seem gone in sixty
00:26:42
four in for example is very or this much older than sequence
00:26:45
it's a event even older than a control issue to touch another we don't normally
00:26:50
the metrics by dividing those the roles and the colour which aren't you
00:26:54
here i just explained to you that is very naive algorithm is actually an algorithm that's for approximately optimal
00:27:00
anita usually has the name of sin gone because it's the first might imagine that would be talking about
00:27:05
yeah with a very very nice actually uh underneath right so it's a two it's a superstar with and you can
00:27:10
find to uh approximate document and it really works amazingly well if it's you know it is not too smart
00:27:16
'cause it can get very fast if it's menus larger this you can uh uh the map for
00:27:20
this but more important than this isn't a little isn't that is super easy to body lies
00:27:25
okay so if in a mention on setup instead of having to compare just to input
00:27:30
you have to compute uh uh ultimate comport between although no millions of input
00:27:35
here you can run everything about it because the only difficulty past is the multiplication of them
00:27:39
at least time a vector okay and of course if you have several inputs with replace
00:27:44
methods bechtel multiplication by letting semantics and begin with c. b. store all that that's that's
00:27:49
a big metrics and this is really what g. p. u. on it for socialism
00:27:54
isn't it can change or if you a map it on on t. b. s. because this
00:27:58
is what you use knows how to do very efficiently like does not expect on multiplication
00:28:03
so this is where you're reading a lot with respect to more traditional optimal control
00:28:06
that didn't like this it's really what we we we aim for this like
00:28:10
a lobster setup and i would also explain that not only it's important for now would need perspective
00:28:15
but now we spent to do but it's also important in high dimension because it can produce a lot of
00:28:20
stability it was is it yeah okay so before doing this let me just get is that there is
00:28:27
many mania expansion of the the idea and this uh ultimatums bought me that
00:28:31
much more than this that that would explain uh there it's quantity of of of optimisation problem that are somehow related
00:28:37
to uh this ultimate comport ram as i could make one the simplest one is uh probably something or
00:28:43
instead of just having two inputs that you want to go but now you have several inputs and you want to find in the meters of them all city
00:28:50
that minimises some ultimate possible distance to just three inputs you
00:28:54
are just actually looking for three ultimatums pocket p.
00:28:57
at the same times instead of just one you you want to try the verse three groupings it's a very natural extension
00:29:02
and i see not is that ultimate one spot is actually a assertion
00:29:06
requests program but it also defines a complex function of its input
00:29:10
the optimal companies don't electric works function which one occupant in our distances not complex
00:29:16
so this one is actually a convex optimisation program that what you did buy a marshall id and young to only a few years ago in
00:29:22
fact you can do everything that i've say to this idea of uh of holding the our taxation you can upgrade to the uh nice
00:29:28
and there and then you would find a single algorithm for the vice and it's very a very simple to do with additional paper and it
00:29:34
works really well i hasten example you want separate between shapes i did
00:29:39
they were like description of clay is inside the to support
00:29:42
so why the display no i don't think it's a good a method for the printing shape
00:29:47
it's really not that whole articulating the notion of smoothness so shape or like elastic deformation
00:29:52
but the good news is it's very cheap very simple to to to is like a broom and uh wait want separate between shapes
00:30:00
this is another example we that we worked on a lot with our previous uh really students
00:30:05
uh i mean actions that it was a collaboration uh with the so that it at all
00:30:09
and then the natural question is everything that i've say so for these four probability distribution technique while the mass to
00:30:16
be that unit mass any situation was your shades are not normalised okay out the shape is not normal right
00:30:22
the big is input mass is not uh it's not normalised to they have different mass
00:30:26
what is the problem with optimal transport usually quiet exact conservation of mass so uh
00:30:31
this is an example of the of the appalachian or what's my point about your disease
00:30:35
that you obtain if you want to map this mixture of two motion in blue
00:30:39
to this next job to cushion in red but i i i believe they're trick this
00:30:43
mass here is a is a is a bit larger than this not here
00:30:47
so because of the conservation of mass of tomatoes bought cannot map this one to this one
00:30:52
so we really we will break is going to uh i will be is kind of ugly sweeten
00:30:57
that is forced to be map from here to the opposite side so chemical
00:31:00
spot is it will be a viewing of tomatoes bob if you don't
00:31:04
if you're not careful it will be too very very i it would
00:31:07
not operation be because of this a lack of balance of mass
00:31:12
income has what we do here is to simply instead of asking for the first
00:31:16
marginal for the some of the remote to be exactly what what fun
00:31:19
we just been honest with black was the most most of things
00:31:23
we'd like if a soft comes twenty of masking summation
00:31:27
and i i would not want all the detail but the natural way to penalise using the true black label
00:31:31
geometric so if you do this you have to press they have all the nice about your document comport
00:31:36
like we defined the mitre goodies downs is to just do the dispense the final week we're downs and so on
00:31:42
so it's really that whole to do this and if you do this you can also nice and population and application of the ultimate on spot
00:31:49
as what you do is worse you at the back the mass but does that sometime
00:31:53
you can remove mass so you can care particular or you can create mass
00:31:58
so it's kind of uh immigration between the optimal point fortunately which is just like oh isn't adamantly that only
00:32:05
uh move the mouse and the goodbye dramatically all the fish are
00:32:09
urgently which in the cost is operating in the other direction
00:32:12
so what where you can create add a little bit of mass of the movie there'd be that much
00:32:17
so these are produced a workstation but i made the whole and thoughts bigger application nationally you would cause validate
00:32:22
the will to see what is the best directly to those are okay for short cut up tomatoes box
00:32:27
for sure it's not productive something in between so here uh the interesting ideas
00:32:32
to mix the two or an impact is it really what works uh
00:32:35
the best so i've been a nice to meet i advise you to
00:32:38
to test this it's usually a a better than your remote control
00:32:43
and guess what the us in congo is an extent also very easy
00:32:46
to this uh to these are to this uh formulation quite
00:32:51
so these are like in the example of expansion draft on that was our example will ultimately spa can be used as a
00:32:57
uh would you know would say to compare this cribbage and then you want on that adding optimisation problem to solve
00:33:02
will be more complicated than this but well you could also use in gordon's or okay so now we
00:33:08
are try to open drive a bit more into uh oh this uh on topic regular edition
00:33:13
as the just the last function you want to use that between nation on him to estimate the cities
00:33:18
and the the first thing is the bad news is if you use it like this it doesn't work and what is the reason for this the reason
00:33:24
is because you add a little bit about what it is not the distance anymore in particular the distance of our fight to itself is non zero
00:33:32
it's yeah but uh because of the of the diffusion the good of the the point
00:33:35
that sure uh you have to do something for to come back to yourself
00:33:39
so it's not as able to do that if you do not break matching like uh no time it could estimation where are you off
00:33:45
we don't use any l. file of course a solution should be i think will be done the best possible mentioned user input
00:33:51
i thought the case what jobs are is the bias because on club it was optional a fitting in red
00:33:57
as you increase it's you and we shrink strange strange words about something so it's you don't uh shrink with the two of us don't
00:34:03
resent the bad the downside you would not lose the uh shrinkage
00:34:07
which really bad and i just mean that this wouldn't work
00:34:10
okay so then we were we were sitting with although how can we do to uh some are changes to correct for the
00:34:16
bass and we came up with a very simple trigger heart which is the okay let's remove the part that is problematic
00:34:22
just remove one half of the distance all of the cost from i thought we'd
00:34:26
self and one half of it that would set it to their it done
00:34:29
but that is what it does is that this guy is you want to do it when i when i think will be does it get a bunch
00:34:34
but of course since java remove deposited number this might become negative so maybe it's actually what else uh maybe by
00:34:40
trying to fix up when you actually create create another what i know that is even with what we did
00:34:45
we tried it on the computer and we we we have to don't make many dances and it was always positive
00:34:52
i was one of the great books we'll it looks like there is a till i'm behind it but
00:34:56
when you look at this and uh with increased i mean i was surprised so are we worked for
00:35:01
at least a one year and a half and get we really on those to what was happening
00:35:04
is what i'm going to present uh the first thing we did um which is actually very simple but very
00:35:09
um insightful is to sell at what happened in the us more and a lot of sudden unit
00:35:15
in the small it's running it is not so surprising that this guy and this guy we can sell
00:35:19
out because this with uh conductors of the buttons body can i find i find it's zero
00:35:24
and this we have to do this with a young tardy and gullible i thought this
00:35:28
would converge to the ultimate possible because you don't agree right so the smaller
00:35:32
certain images just ultimate spot but what is more interesting is a lot of snow
00:35:35
need because the uh couldn't this not opinion on that is very famous
00:35:40
that that was our caller usually in the statistically charger a maximum mean discrepancies
00:35:45
uh in the image was the seeing or shape as they are often called channel method
00:35:49
and actually corresponding functionalities to sober up spaces which is something that is really really
00:35:54
we went well uh what you did this much simpler arteries and ultimate possible
00:35:58
uh what is it and i will um defined is very briefly but they like books on
00:36:03
the subject and the guy that was the most on this is uh after that
00:36:07
um yeah these are simply you take your uh your description i find it up you can get the difference because you
00:36:14
want to compute and all that could excite and then you compute the double the adoption of 'cause i was itself
00:36:20
you can get on an annual picnic twice this panel against yourself
00:36:24
to feel this good point it mute would double some way to the button thing all but if it's
00:36:28
point going to be a double some of the gallon value between all the bells of points
00:36:33
'cause that everybody would contact with everybody that's why i was saying that i think
00:36:37
i that is on placing his idea of making people speak to each
00:36:40
other in the larger needs just double thing look on it and yeah if
00:36:44
you do think on to get you would use looks very we um
00:36:47
it's minus the distance to the ball up so it looks we're there isn't i
00:36:51
notice how this could be positive in fact it's positive or in some cases
00:36:56
because there is a minus but you have to remember that show you'll computing some since that is the difference of too much
00:37:03
in particular it as as it will mean we should double articulate something of the only in
00:37:08
against minus the couldn't distance one sounds page put it it and actually yeah the name this guy
00:37:14
his name the energy distance would uh norman why they could not distance because energy not
00:37:19
uh so for me between zero and two is not so odd to see that this guy is uh is the norm
00:37:26
and it actually doesn't i mean that in in and then it is it's chorus about half an hour to so what i've norm of negative on x.
00:37:32
okay so what you recover in the large i've seen only need to uh for
00:37:36
the single an algorithm or zinc on you don't also with the extra
00:37:40
collecting tom is a simple uh will be option on on between them or
00:37:44
three network to see that's uh uh uh this uh technology of uh
00:37:49
sink onto their jobs is it can be seen as a weight what operate between two very different
00:37:54
class of the stance one that would be a very flat which is just the induction distance
00:37:59
something that's very fat which is it what operate would just do like classical or um
00:38:04
minstrel murders but of course if certain goes to the only be comparing them flat
00:38:08
i could show the space of ultimate transport and then get operation be becomes much more interesting but of course it much more complicated okay
00:38:15
so i think it's quite into it into inside for but still it was like in this uh up about your being positive
00:38:22
and in fact we prove it read very recently wizarding fiji and gullible bottles
00:38:26
of a sentence with positive but of course is not always positive
00:38:30
needs and what is on the keyboard is is actually is really natural when you look
00:38:33
at sink on either the dips down there should be a positive twenty different different
00:38:38
so if you the importance of the okay the and he's not here if he's between uh the one too
00:38:44
then it's account and that would be put it even then it would work but if you use the larger than to like people for
00:38:50
something and what you would do this but okay uh it's not down to anybody you can find example like that with it
00:38:55
with alternative possible p. which is the settings which isn't park is it's going to be opposed on it
00:39:00
and this guy the single need i don't is going to be positive and that's going to be something that you
00:39:07
can use that as the discrepancies with positive or zero if and only if i fight will be thought
00:39:12
and it's something that makes high so we can add ons meaning that we still have this nice remote capability of um
00:39:17
if i file genetically conduct two bit are then uh this uh
00:39:21
think on the gardens we conducted so it's it's the body
00:39:24
they the the idea that you can use it uh if you if you do this for for non by making fitting
00:39:31
where you you what your thing what you what you guys you should obtain is that the optimal matches or the
00:39:36
red point it was a blue points uh which is uh i five will be time the cost you
00:39:42
an additional bonus and it explain it doesn't really give you the pool but explain why there is something happening
00:39:47
is that um actually the optimal can spot a while the
00:39:52
cost if you want um here the sink on cost
00:39:55
is convex of i'm fine income is collected data get something that is not to our control but actually if you
00:40:01
look it's along the diagonal so if you put our folk would be that it become come to have
00:40:05
so it's a function that is convex on the r. faxes and collect on the bit x. but can
00:40:10
got on the deck that bit where like the functional minus it's time white it's convex and
00:40:14
it's come back to my butt gatherings today with that so and if you put a minus it's
00:40:19
complex so these guys conveys gateways get next we find these guys actually it works under
00:40:24
it's really nice with when you can see device enter everything you want to do
00:40:28
uh when you use convex optimisation you can use with the normalised of
00:40:31
course it's really a good news for us because of good news which was uh i guess to be expected is what i've been in high
00:40:39
dimension okay and uh it's not really a way to say that this would work formation on problem but i think it's a sanity check that you
00:40:46
could do that to start with is in part is nationally never really attracted
00:40:50
to are fun but that you are taught access to discrete samples
00:40:54
and the first question is when you describe title problem but it comes out and if it comes out at what speed
00:40:59
the fact that it it converges it's obvious just logged on and all that uh the distance that we can
00:41:04
better but the question is if you it instead of using of computing the tool to martin's body styles
00:41:08
you can put the ultimate one spot between discrete samples at what speed would conduct with all and the values it come down very very story
00:41:15
in fact you pay the cost of dimensionality you have exponential dependency on the dimension
00:41:20
okay and the and the little space is one of the into the pool one of on so
00:41:24
if the louder than five and bigger mention on your cousin emergent ten or one hundred
00:41:29
it's it's it's doomed to fail java genetic density like uh on the cube
00:41:33
you can add noise to make it to the document what using disk with some part is
00:41:37
just too good to get people to match what works is because of some other reason
00:41:41
but for from the discrete uh point of view it's it's it would be affect your um
00:41:46
on very shocking cost if you do the same sanity check with okay the norms
00:41:51
uh basically because of the somehow detail and you would become like them to call me that would become a deployment of the dimension
00:41:57
so maybe it would not work for some reason but at least you can estimate the distance
00:42:01
and can estimate is at the other line that one of us colder than usual right
00:42:05
which made a okay in quantities okay another question is what happened with the
00:42:10
scene gone or uh it's it's it's not operating between the two
00:42:14
the guess is that it should not operate busy between these two whites and it's it's what we prove recently
00:42:19
with or the most is black and the market you it is that the rates as soon as it stands today with it either
00:42:25
that is no couldn't spaces used to for couldn't ultimately support the line between one on becomes one of us go with
00:42:31
them the whole that is there is no freedom because you know when it's understood what she says she blows
00:42:37
so that might become one of us code of an but the gospel explode with obscure like it's shown
00:42:41
to the pool minus divide it back so there is no footage if you want to approximate the
00:42:46
puritans what do we need to pay a price that will blows with it so if you even
00:42:50
point two weeks to be clever and say let choose it soon as a function of and
00:42:54
and you matched uh you manage the volume make with the one you you make when you approximate within call
00:42:59
oh you will go though i that is is what we would to begin again
00:43:03
okay so single is not the way to approximate optimal what more efficiently
00:43:06
you just the way to define a new set of discrepancy that you
00:43:10
can estimate mortician okay so the goal is to uh be
00:43:14
able to show maybe they don't know we don't i mean each already for this that you could use a larger epsilon
00:43:19
you could beneath that beneath the shade for better sample complex design ultimatums part
00:43:24
but at the same time we need to change for the for on the german killed my transport would would had
00:43:29
to uh have better things if the density are on it shifted or if you have something station to estimate so
00:43:35
where a ultimate 'cause what is clearly much better than a candidate that get so one oh unfortunately we don't have any choice
00:43:42
so i want to conclude a briefly on the idea of using this forty and we have a few minutes or left
00:43:48
uh also unfortunately i think it would be quite deceiving because i want to convey
00:43:51
the id that's yeah is too complicated for us at this moment mention
00:43:55
but there is very nice about it you to to understand this to you know ladies to doodle c. t. v. things at all with the site
00:44:01
okay uh the classic uh one classical approach i would say that it's it's it's to say okay
00:44:06
the more that i have the alpha beta uh i want to use aspen plates the other density with respect
00:44:11
to fix description like the the big one for some but doesn't really matter which one you use
00:44:16
uh then you set up a maximum likelihood estimate or what you would minimise the
00:44:20
some of mine as a lot of the density every international for this is
00:44:24
you play oh you make them assumption that so some points on the point okay
00:44:28
so mine is a lot would make this into the plug into some
00:44:32
so this would wait for many application the simplest case is a cushion case where you have to
00:44:37
postpone expression but what people want to to do noise to do estimation very high dimension
00:44:43
what the big races input this would break people this is that you can have a fixed a reference
00:44:48
measure that will what what or whom with as is not possible in very very high dimension
00:44:53
uh and the typical scenario where are where these breaks it's it's a good analogy models that's not you
00:44:58
well you say instead of trying to prescribe a density i. dominance very on i will prescribe an arrow is
00:45:03
them to do on them some part in what is this algorithms and with them is very simple
00:45:08
you'd first draw all the points at one domino dimension like in the square for instance and then you might disappoint school
00:45:15
some function pragmatic function jitter thought and part is it would be a
00:45:19
probably a dip nets because it's something that mothers well complicated images
00:45:23
so you just push for one income apply v. d. c. description a low cost low dimensional distribution
00:45:29
into a very id much respect what would happen is this just to bother distribution would be
00:45:34
very single art would be distributed along some some of of bypass your face in very high
00:45:39
dimension so impact it's it would mean that show you with a lot of the all
00:45:43
what it means it means that the m. a. is not define because uh this uh bothers guy would change if that
00:45:49
that change so is no way you can come up with a g. d. x. that would be walking for everybody
00:45:54
so in this in i don't so singularly high dimension that you cannot estimate the
00:45:58
maximum like you would need to come up with like a good validation
00:46:01
i thought then you typically need something to scan it and so on so what you need actually to do is to use the loss function
00:46:07
that is not the true but just mention that you've been in any way that is a function that is uh
00:46:12
pagan always aspect to do we can gardens and of course you know what i want to
00:46:15
say maybe i this management can spot is uh is what you are looking for
00:46:19
so for those you would try to boss defeating with this uh uh normalising only got not
00:46:24
which of course content as particular case of buttons management balls and the and and you can add a lot to each get okay
00:46:31
so no mathematics just okay you can use it and it makes
00:46:34
sense common optimisation topic to because everything is is continues here
00:46:38
this is a typical scenario i'm not a specialist in deep longing but the typical scenario where does make sense impacted
00:46:44
is uh well you would use a deep longing did network not in
00:46:48
the traditional way that people use for discrimination forty by donning but
00:46:51
well join the oboe the white we are you would stop by a low dimensional us collect all and then you would map it's
00:46:58
it and you get when you made by basically planes early all backwards so the idea of generative uh did network
00:47:05
that the do not you net i've kind of you oppose it or the joint genetically as the disconnect unit
00:47:12
what you do is you would put the t. v. announcer dimensional that that until you get an image
00:47:16
and this incorrectly works amazingly what impact does nobody really understood why
00:47:20
but the screen is something that can models very complicated network
00:47:24
you can do this we simpler little or digits very boring these days you can even take a on them pointing
00:47:30
to do or what if you have more complicated images you need to have a lap on space of
00:47:35
the space or for that to be a more high dimensional like dimension one hundred and
00:47:41
okay so i will skip how you do this impact is it's very complicated you need to some kind of to get to get i don't
00:47:46
but there is no theory for this because nothing is really like a nothing cards with very complicated can just use it seems to works
00:47:53
uh the aspect shorten it's complicated of course and it's it's even more complicated because you typically have a
00:47:59
then to compute its multiple distance using single was typical uh i would second
00:48:05
traditional gender on that you would have but you have yielded nets
00:48:08
you input data and the function that would compel you input that i withdraw the net okay i
00:48:13
i i don't want to go into detail that's really to show that the function dash picture
00:48:18
that defines your last uh functions is complicated same thing i don't have a lot of time are but uh what do you do when
00:48:25
you have a complicated function to minimise so i guess i'm probably many of you already know this but uh it's quite interesting
00:48:32
uh what you would do is what how the computer i don't of a of a computed function
00:48:37
so if you think you have a some kind of complicated function that runs in k. operation okay our phones and the
00:48:44
one option before um it when caleb action what is the complexity of completing the guy don't all your function
00:48:51
that now isn't that fun and and two and okay so what are you know the answer but what is the complexity of computing i don't
00:48:58
it's a fundamental question for for not going and it is in some sense it's an avon so would be okay we'll try using finite differences
00:49:04
of course only good by using the category general if you do this
00:49:08
uh you all that i mean an algorithm that scales linearly
00:49:12
with the dimensions is very bad to join high dimension of course you cannot use when i mean because everybody knows is what is the
00:49:18
answer to this whatever it's it's a it's a it's definitive on so
00:49:21
it's uh you should use the back wall automatically from station
00:49:25
what is quality that model to make it in this case you would have to embrace it you're
00:49:29
converting the guide on that would be exactly the same as the beast you're computing the function
00:49:34
which typically what everybody know deep down in that you should you back propagation
00:49:38
which is specific guys of these don't of course you can use this
00:49:41
for every tori ash picture like the one uh with unforeseen go on that for you and you will part is what people would do
00:49:49
these are simple example uh we did in my teen not seem very spectacular in fact there is
00:49:54
many many other methods that can be used to train got me your sticks to different
00:49:58
assumption that on typically not ports and they don't implement transport it's not clear what is the
00:50:03
best complain when it better than the other but every week series and you pay product
00:50:07
uh that basically improve what works well is just using a lot on that work typically so we're not really
00:50:13
give you an insight of what is the best a loss function to give the best kind without
00:50:18
um of course impact is uh one even questioning my talk is
00:50:22
what is the method usually used to combat images and of
00:50:25
course for image should not use your to norm because it's bad for your everybody or from moses in image processing
00:50:31
so what you should do when you want to do high quality generation of of images it also longer metric
00:50:37
which would lead you to exactly the same class of architecture or very similar architecture that people do
00:50:42
we know also going yeah and so it wasn't produced by a young good fellow a few years ago
00:50:47
where you learn those on the porch disk miniature images to hear this committee your images would mean
00:50:53
find a good meeting to discriminate a huge impact is what you have to do is something even more
00:50:58
complicated than one of say before i also want to lay on assume that work in competition
00:51:03
to the first one gets of all those who knows guy and it's it's really like to because
00:51:06
what they also do or impact is you you need to train to networks in on them
00:51:11
okay so quite a lot of question what is or if i feel so it's
00:51:15
you and how can you even say that one and is better than than
00:51:18
in another one maybe he'll was okay maybe the best guy is the one that
00:51:22
minimise the best any well but in high dimensions not possible to compute
00:51:26
any points what people want is high quality images which has nothing to do with high quality optimal
00:51:31
control this not so it's really like it to vary a touchy problem that nobody really knows
00:51:36
or how to even framework is a bit yeah and i don't think anybody knows uh for one
00:51:41
better image is something that you could do but it's not related to having the bit down
00:51:45
ah it's an open program these are just for fun that is not my team it's a real that
00:51:49
was a pain in the job to a twenty operate between major facing people do with yeah and
00:51:54
to check what it gives is to take two point in the rat on space and was some kind of a straight line
00:51:59
which would be mapped in some sort of cool on this data base of images so this wasn't done
00:52:05
by a great and you just you can find videos online and it could be explained white so
00:52:10
complicated because it up or do some kind of contemplation that is is is very complicated would say that
00:52:16
if a three years ago people uh say that you get this kind of aunt operation quality
00:52:21
between images nobody would have believed it working so it you break too but at the same time much shopping here
00:52:27
it's probably very far from uh from the good statistical model 'cause gander usually the record poodle
00:52:32
but we fitting isn't of images but they were very good job at contemplating between you
00:52:37
which is a very different problem than a statistical so it's really something that nobody's uh
00:52:42
can i can understand now but uh it's quite a lot of changes for positive station
00:52:47
and with this i will conclude my talk so just to say that's uh the
00:52:50
the really like a stream of lot of produced work of great mathematician
00:52:55
including that of your the nobel prize and preliminaries so i've read any
00:52:58
but the few militant pop voice broken up tomatoes bought this
00:53:01
summer uh and each of you get the with a student of uh of sleep with anyone also the feud with ours
00:53:07
forty one on the regularity of multiple which people cared about in math but here i would say it is not so relevant
00:53:14
so there's a lot of strong mathematician another question is can you apply it in high dimension
00:53:18
and so is no of course you cannot because it's too complicated this that's degree not great event but can you take some ideas
00:53:24
ones great mathematician and use them to solve or open printing machine running i hope so and i think it's quite exciting

Share this talk: 


Conference Program

Optimal Transport for Machine Learning
Dr. Gabriel Peyré
12 Feb. 2019 · 4:05 p.m.
284 views
Q&A
12 Feb. 2019 · 4:58 p.m.