0:00:14so my name is the current crush them more the and i'm presenting the top michael orders uh
0:00:19my graduate student was stuff a and also line white to in the audience you lying is from the you
0:00:24is your badly
0:00:26uh so just to kind of give you a pictorial
0:00:29description of what the problem is it's kind of nice to start with something artistic so uh
0:00:34this is a main idea
0:00:36we are looking at
0:00:38eight basic scenario where you're trying to track a moving target so
0:00:54signal processing that B
0:00:56the silly in papers where what you do is you do some sort of bayesian estimate of the state of
0:01:01the top given noisy measurements
0:01:03uh and of kind of written that abstractly
0:01:16once you have those track estimates
0:01:18typically you have some he wouldn't being looking at a
0:01:21television screen and saying okay this it
0:01:24is doing something interesting
0:01:26well this start it is not doing something interest
0:01:29what we wanna do is all to mate that high level
0:01:32that's why we call this metalevel tracking so
0:01:34in other words
0:01:46no i i had to have a project a a a a a thing
0:01:49the red button you
0:01:50so the idea is given these dot
0:01:54how do you joint the essential
0:01:57can you tell from these dots what sort trajectory the talk it's gonna do
0:02:01and
0:02:02do this in a page and sense to some sort of non than you filter
0:02:05estimate the trajectory
0:02:07so this is to automate
0:02:09several possible toss which are of interest
0:02:11for example you might have a target
0:02:14which you interested in which goes to a check point of fills up fuel goes to another point and then
0:02:19a final this
0:02:21um are only interested in targets which go to this trajectory go to those but specific point
0:02:27how can i we construct
0:02:28an estimate of such a project
0:02:30you know patience and
0:02:32so this kind of bills on a a legacy tracker
0:02:36and a goal is to see how could be construct good models to this
0:02:40and once you do construct a good model how can you actually can L
0:02:45so uh just to give you a further example of this this is a typical example which kind of motivated
0:02:50by we did some of this research
0:02:52so this could be maybe somewhere in a city where a
0:02:57typically traffic
0:02:59road traffic goes like this
0:03:00donna role
0:03:02and then some day
0:03:04do you to maybe the local people knowing that i have something was deployed in the role maybe and i
0:03:08i D use something
0:03:10you see a lot of traffic
0:03:12by pass a particle part of the road
0:03:15so probably a track see all the dots done with people by past the that
0:03:19so previous so you're going the straight line
0:03:21now you kind of died reading and then going back
0:03:25how could you actually construct some like to classify for that
0:03:29given given the do
0:03:32so all an obvious way of more like this would be that
0:03:35in some sense i'm deviating
0:03:37some amount
0:03:38X
0:03:38from the road
0:03:40and then a coming back but a same amount
0:03:42now that a more X could be variable a baby got all the way here are then going back
0:03:46so we need a model which is scale invariant
0:03:48which allows you to go in a particular dimension probably a random number of step
0:03:53and then you need to remember that that a number of steps to come back and we model construct a
0:03:57model which does that
0:03:59it's kind of obvious that a standard finite state markov chain cannot do that
0:04:03is a markov chain cannot embed them E which is
0:04:06variable in it
0:04:07i mean of course you can construct a state space which is a maximal possible size
0:04:11that's ridiculous because a of possible that's very here
0:04:13so it sort of possible use
0:04:15station
0:04:15so we need something smarter than a markov chain
0:04:18so uh the that's that's basically the idea of what we gonna talk about
0:04:21so you can think from an abstract point of view this is a special case of a trajectory which we
0:04:26call it a
0:04:27where you deviation away from it is equal to the deviation to words that
0:04:31and this D V A should could be around random
0:04:33what to do
0:04:34so could be anything
0:04:35another example could be top which just circling the building so for example a to be something suspicious build themselves
0:04:41up or whatever
0:04:42so
0:04:43can you tell from a bunch of don't
0:04:45isolate only those trajectories
0:04:48where talk it's something a building
0:04:49for example going a rectangle
0:04:52uh a or for example maybe be power just going straight fine to be known
0:04:55so how do you isolate different trajectories you using some sort of nonlinear filtering operation um
0:05:04okay so i just just a kind of again reinforce the idea that
0:05:08in conventional talk tracking which i guess to lots of papers and signal processing it's so one
0:05:12the main idea you construct a steak space model for the trajectory of the top
0:05:17that's fantastic if you're doing very short ranges over time because you can approximate things by random walks
0:05:24but over long periods of time the drivers not a random block
0:05:27he has a well defined destination
0:05:29and they typically going through for example
0:05:32a street man
0:05:33a digital that for example which you could we construct google
0:05:36or whatever
0:05:37so how do you construct
0:05:39an efficient model which can do that and then the questions how can you estimate that
0:05:43so the main idea the talk is we we dealing with a particular class of models which are called stochastic
0:05:48context free grammars
0:05:49and maybe is useful to start with this picture the border
0:05:52so if you if you did a elementary course and radical computer science
0:05:55you would see that a markov chain
0:05:58or for like to go to state space models
0:06:00are
0:06:00regular grammars
0:06:02they assume that what happens now depends probabilistic lee
0:06:06on what happened at the previous time point
0:06:09it's not true would most complicated trajectories because if you're gonna go in a square
0:06:14you have a long range dependency because you're starting and ending point of the simple
0:06:18that's not my
0:06:19so
0:06:20in in computer science there is this more general model call eight context free grammar
0:06:25which is a level of abstraction we gonna talk about today
0:06:28where
0:06:29you can actually construct
0:06:31several very interesting
0:06:33trajectories
0:06:34which are non that of you
0:06:35such as rectangles all since a
0:06:38a but size which but you can prove
0:06:40a markov chain cannot
0:06:42we can write and talk about the
0:06:45now of course there are even more general language
0:06:47such as context-sensitive grammars
0:06:49but there are no use to was because they do not have all real time out
0:06:53some things not all of the you know it's not
0:06:56from an engineering point of view
0:06:57useful and that there are restricted was just like one i'm talking about
0:07:01it's kind of a while english so speak
0:07:03so typically regular is
0:07:06mark or V a know the sort of stuff everybody does
0:07:08what we're trying to do here something a slight generalisation of the context free
0:07:12me
0:07:14so this is called a chomsky hierarchy a formal language that and our goal is to see can one constructs
0:07:19the equivalent filters such as a kalman filter or the hidden markov model filter so one
0:07:24in this domain where you have long range dependence
0:07:27okay not a can be a little bit more insight
0:07:30now you might say why is this of any use and i want give you some more insight as to
0:07:34why this is of use
0:07:36for starts this is a very convenient model for human operators
0:07:40you can imagine that
0:07:42in ideally only what happens is off to the tracker operates and as a should in the first slide we
0:07:47trying to build something on top of that
0:07:49which helps to human
0:07:51automate to the process of detecting if something doing
0:07:54something interest
0:07:55now it's pretty hard to teach the average soldier probability theory and detection it's so on and make them understand
0:08:01how to construct a bayesian estimate
0:08:03if you can automate that process by allowing the average soldier just to estimate
0:08:08to put in
0:08:09uh_huh
0:08:10metalevel is that if a target is doing something it's a species
0:08:13if is not doing something not speech
0:08:15so essentially actually you can quantify these rules
0:08:19in two
0:08:19fairly interesting types
0:08:21of of production rules what you call be size
0:08:24and you can check the consistency of those by a compiler which which are long describe here but it's pretty
0:08:28easy to do
0:08:29second point is once you do that
0:08:32just like a regular grammars in the context free grammar domain main you have
0:08:36polynomial out
0:08:38a estimation
0:08:39a lot of this work is really been motivated by recent research should by all informatics
0:08:44where you also have long range dependencies
0:08:46and i want to give you some insight as to what i mean
0:08:48so this is a typical buyer informatics type example this is
0:08:51a protein which coils
0:08:54or a given thing D N A which is a you can declare nuclear tag sequence which also close like
0:08:58this now the dependencies you're a spatial so this guy here depends a lot of disk Q even though it's
0:09:03pretty far we you will always call
0:09:06rather than have a linear depends
0:09:08okay so mark of in type processes can not more the sort of dependency with this guy
0:09:12is spatially very close to you
0:09:14long
0:09:16another example
0:09:17think of a computer language
0:09:18this is a a complete or experiment it's not it's not a actual useful thing but it's it's a nice
0:09:22thought experiment
0:09:23suppose to take
0:09:24something like a computer language like C your back to that
0:09:28have a big in if
0:09:30and then i have a lot of stuff and then at the end
0:09:32if a computer language was marked for the and then at have a a and if
0:09:35with a high probability you be B up for beginners
0:09:38although an actual computer language you have a lot of stuff
0:09:41so now you can think of the core experiment
0:09:42suppose i think this computer language
0:09:45this code and a corrupted by noise
0:09:47how that we can
0:09:48now i can't use a markov chain because this is not
0:09:52representation
0:09:53so that's another example
0:09:55i
0:09:56so the ball is how can you construct a useful things here
0:09:59and the point is
0:10:00they should be scale invariant you C
0:10:02all of these are the structure it scale in it's i have a big in if i can have a
0:10:06lot of junk could between and nine is but me and
0:10:08so the size of how much stuff is in between
0:10:11should not matter for the context of the a
0:10:14so that's that's something which we want as well
0:10:16now it turns out that
0:10:17for such that the models people are shown i'm not to give you any right studies here
0:10:22that
0:10:22in terms of entropy
0:10:24these context free grammars
0:10:26do fantastic stick that is
0:10:28for a equal size parameterization of a model
0:10:32if we look at the
0:10:33predicted entropy
0:10:35these are extremely efficient models when you have to sort of scale and
0:10:39okay so let's not jump in
0:10:41the actual types of trajectories we want talk about
0:10:44so this is the first trajectory a random walk which is simply
0:10:48a good role of chain which you do was state space
0:10:51this is a widely used
0:10:53it target tracking but as i said it's pretty useless because no drivers a drunk or simply flips a point
0:10:57it is that's but gonna drive
0:10:59they got go in a directed we from a to B
0:11:01a much more sophisticated model which michael a line white is that's a pretty cool work alone
0:11:05is very you know the beginning and you don't the and
0:11:09and you want an so it's called the reciprocal process are a lot of you bridge which is a generalisation
0:11:13of a brownian bridge so you clap the two and but you start this
0:11:18definition as random pass
0:11:19and then you construct
0:11:21a dependency but each point now depends so the next point at the previous one
0:11:24to this is a one dimensional model round fee
0:11:27and that's called them up with you
0:11:29now you can think of a much more generalisation of that we is a stochastic context free grammar
0:11:33so rather than have
0:11:35i start from a a
0:11:36and i'm restrict to reach time be at a fixed future time
0:11:41i now want to go through particular weight points these could be for example a ones
0:11:45so i one like topic to go from a to C to be
0:11:49and in between to you i'll i'll a we project
0:11:53how can a now if uh
0:11:55given this sort of model
0:11:56construct from noisy estimates
0:11:58the actual trajectory that would be a question once
0:12:01so here are examples of cases where you can not fit simple markov change
0:12:06so i the said one of them is an out
0:12:08so if i goal in this direction a four and point
0:12:12and then and and the tree number of points to this direction B
0:12:15and then come back
0:12:16see for and points
0:12:18you can prove
0:12:19by something colour pumping level like computer signs that
0:12:21such a string
0:12:23when you have and As
0:12:25a bunch of bees and then and sees were and is a battery
0:12:28can not exclusive we generated by a markov process it's a possible you can do that you can actually she
0:12:33for like four
0:12:34so a rectangle
0:12:36so suppose i when equal number of points year then here than equal number of points and the backward
0:12:41such a close trajectory can not be generate by
0:12:44the intuition is that a markov chain cannot store memory in
0:12:47it's got a markov chain is simply a regular automata
0:12:50to store memory you need something called push down stack you have to store stuff and you put that out
0:12:55of the stack
0:12:56and that's a lot of
0:12:58so anyway so these are kind of
0:13:00but a things i don't just one a very quickly give you a a uh some inside
0:13:05as to how this differs from a standard construction of a
0:13:08hidden markov model which is
0:13:10what you typically do
0:13:12when you deal that are tracked
0:13:13a little
0:13:15so most if you would know what a hidden markov model or a probabilistic model of them are uh functional
0:13:19markov chain
0:13:21we start with the transition matrix so this is an underlying markov chain
0:13:25which of evolves over time
0:13:27and we observe the markov chain
0:13:29it also to alphabet you a and B
0:13:31well these are the probabilities of the observation a given state one
0:13:35these are the probabilities of the observation a given state doing so so this is you parameterize it to do
0:13:41um now
0:13:42you can as right this in in the type of rules we wanted to do to express a context free
0:13:46grammar and the next page
0:13:47by simply saying that we have a bunch of terminals which uh what you'll to
0:13:52and a bunch of non terminals which are state
0:13:55okay
0:13:55and essentially actually you can qualify all these in to rules that if i scott
0:13:59from some starting state S one
0:14:01then i generate
0:14:02a a and remain S one it probably point five for and that's pretty clear is the i-th eight point
0:14:06nine mike transition matrix of boy from S one to S one
0:14:09and not blah but the probably a generate eight point nine ten point six point five and i can do
0:14:13this for all possibilities and this is be the production rules
0:14:16the drama which can generate any string which is mark of view
0:14:20this is how a re
0:14:22and then i simply start for example a S one
0:14:25i use a real i S one piece me a S two with some probably point to just my simulation
0:14:29i keep generating and what you see here is the markov chain grows
0:14:33on a bayesian network from left to right
0:14:36dependencies is just
0:14:37one
0:14:38this is trivial this is well known
0:14:40now we let me give you some insight to the stochastic to three gram
0:14:43so here are the same rules as what we and the previous page
0:14:46the only difference
0:14:48is this last rule
0:14:49what you see here is that we have
0:14:52a not want term at
0:14:53a state if you like
0:14:55which maps
0:14:56not just to another stadium but
0:14:58a bunch of state
0:15:00and this is the key difference you see when you have a context free grammar the chomsky
0:15:05sort of hierarchy of languages tells you that
0:15:07any time you map from a nonterminal on one side
0:15:10to a terminal and
0:15:12multiple non terminals
0:15:14such as a language the string can not be model by a markov G
0:15:19now this is
0:15:20oh wait so this ground or would generate and we compute a language you know such as C
0:15:25for of whatever the all examples
0:15:27of things we set for the strong
0:15:29of course this is a probabilistic version because we log probabilities but things
0:15:33the big a generalisation of course which we want consider here is context sensitive
0:15:37in context sensitive you have a
0:15:39eight
0:15:40terminal followed by a non little which maps of the right and say that would be the context
0:15:44this don't to
0:15:46anyway so this is how you would generate
0:15:48using these rules uh a stochastic context free grammars string
0:15:51and what you know here is
0:15:53the recursive embedding it doesn't just left to right but it grows inside out
0:15:57so it other words
0:15:58you see this a and this at
0:16:01get further and further away and yet they depend on each other
0:16:04C is long range dependence
0:16:06which which can a picture
0:16:09this is
0:16:09in very simple terms
0:16:11how you generate a stochastic context free grammar
0:16:13now to some mathematics
0:16:14so everything here so far been pictorial next one X three
0:16:17so
0:16:18how would you that he model this in terms of and
0:16:20or stochastic process well these are actually special types of branching process
0:16:25that multi type gal and what's and branching process
0:16:28where the order of the caff the bottom process better
0:16:32so you can view this is saying roughly speaking that each realise a should is a
0:16:36three
0:16:37or a patient at
0:16:38so each realise asian is a patient
0:16:40so every time we realise it
0:16:42you have different patient
0:16:44just like for
0:16:45state space models you have a realisation T this case the call chomsky don't forms and so one
0:16:50and to prove that i have a string and it does not belong to a particular language
0:16:55there are well defined rooms which are called pumping that
0:16:58which can like to show that
0:17:00okay now i i guess wanna give you some more insight as a how you can process these sort of
0:17:04strings
0:17:04so i have a spring i have a bunch of observations which are noisy i want it's a is this
0:17:09target gotta go has gone in a straight line has to go on and then all has gone in a
0:17:13circle
0:17:15these a context free grammar type things which cannot be recognized by a markov chain
0:17:18what sort of out sums of it'll
0:17:20well you know the are or in case
0:17:22there are standard filters like a hidden markov model filter which is analogous to a kalman filter
0:17:27if we want to do so a poster sequence estimate the the viterbi out
0:17:31it's so
0:17:32i you want to estimate the parameters that things like the so like to estimation by the expectation maximization
0:17:38it turns out
0:17:38all these things generalized to the stochastic context free grammar to me
0:17:42so just like you have a forward-backward filter
0:17:44in a stochastic context free grammar because you of on a parse tree
0:17:48you have something called the inside outside help with
0:17:52just like you have the viterbi algorithm in the stochastic context free grammar case you have you do the cook
0:17:57younger "'cause" sound out the model only two parts
0:18:00which which do
0:18:02so
0:18:02essentially what you have done is you of generalized the role or the evolution of a random process
0:18:08on a straight line
0:18:10to something which of balls on a tree now and that's that's basically that the i Q where eventually the
0:18:15tree has long which dependencies because it start from a common
0:18:18okay so that's uh
0:18:20get get so this is a then your hmm the the
0:18:23pitch a network
0:18:24and
0:18:25this is
0:18:26for example stochastic comes to grab but this is called the parse tree
0:18:30okay K and has that all these algorithms have polynomial only complexity what you lose is
0:18:34typically for a
0:18:36hmm or any type of mark of via process when you do
0:18:40filtering
0:18:41the complexity
0:18:43of going through T points of data is then you're T
0:18:47a common filter of your processing a million points requires a million
0:18:50time to state space
0:18:51in this case for a stochastic on is free grammars actually cubic peak the like the day but it still
0:18:55or no
0:18:56it's Q
0:18:58okay
0:18:58so uh here is a example of of some rules which are just distorted you bit more be killed the
0:19:03paper give the out with them simulations and so on
0:19:05so here is a sort of
0:19:07flow of traffic in normal life
0:19:10at this is actually a fight of the google that what of the things you can do very nice use
0:19:13you can actually qualify
0:19:15different maps digital maps in constraints in used to go
0:19:21so you you have talk at just go in a straight line or a bunch of targets maybe be today
0:19:25and then to you notice that
0:19:26some that like this people are deviating from
0:19:29how would you all to make that how you come up the bayesian inference that
0:19:32something funny was going on you the people of changes
0:19:35so you would qualify
0:19:36the rule that people have on
0:19:38equal amounts away and come back to the rule by equal
0:19:42which is at a
0:19:43and this sum the go by is a random amount
0:19:46so you a fixed but you have a memory which is variable
0:19:49and that cannot be and coded is
0:19:51markov of G
0:19:52and of course you measuring these a noise was of a noisy sensor
0:19:55you can construct a grammatical and so this fairly easily terms of production rules
0:19:59once you do that
0:20:00you can construct an optimal filter
0:20:02which gives it the optimal estimate of what's what's going on
0:20:06so
0:20:07i in the time available of course that can the find to how you derive still does but they given
0:20:11in the paper and also the reference here
0:20:13so i just one a kind of conclude with some some of the main points
0:20:16what i want say here
0:20:18so the first point is that these syntactic models which are constructed
0:20:22context free grammar model
0:20:23a a to really look at a complex
0:20:26trajectories of targets
0:20:28which can not be dealt with it the markovian work
0:20:31there are several classes of trajectories which you can prove
0:20:35can not be generated by a markov process
0:20:37and
0:20:38so i in some sense this allows us to go into a slightly more general class
0:20:43these are meant to replace the human operator who sits and looks at track lit
0:20:48coming out of a track or you wanna automate that for
0:20:51the second point is that these algorithms of polynomial complexity so the practical
0:20:56just like in
0:20:57for a state space model you call that filtering she you would call that a parsing out
0:21:01because you really constructing a parse S
0:21:05uh in many cases you can view this is a human sensor interface because there's been a lot of work
0:21:09done in the actual sense signal processing
0:21:13how can i or to made the process of using that
0:21:15estimate from the sensor level
0:21:17to something which helps if you mean
0:21:20determine a something's happen
0:21:21that's really what we're talking about you
0:21:23is the human sensor interface also known as middle where
0:21:27there's a very interesting system you ready issues which i haven't even mentioned you
0:21:30okay so the first thing is if we have a parse tree which keeps generating these non terminal to eventually
0:21:35stops
0:21:36of course you need the eventual length of you string to be fine i
0:21:40so how do you and sure that's the case
0:21:42those that stability issues he's a course some pretty cool than what's of processes
0:21:46and essentially you need to spectral norm a particular matrix vol be the probabilities to be less and one
0:21:51there are also constraint
0:21:54if you know that a the target gonna and up at some particular location
0:21:57how do you constrain the probabilities in your mobile so that
0:22:02so that you model actually ends up there
0:22:04piece so those are also pretty interesting problem
0:22:07fine are several unresolved issues and this problem as i said much of the detail as been developed in the
0:22:12by informatics that are only the last ten fifteen years
0:22:15and
0:22:17things like how sensitive is your beige an estimator to prior
0:22:22does it for get you initialization geometrically fast which just to for example the kalman filter so
0:22:26these are unresolved issues
0:22:29so in time sort of that picture there's been a lot of work done research in this area are just
0:22:33given you a couple of
0:22:34references here
0:22:35uh and we also use this quite a bit not only to model trajectories but also to model
0:22:41for example radars
0:22:42complex sensors are not markovian because they
0:22:46they have feedback structure with the them and and really you can you
0:22:50the
0:22:51oh put of a complex sequence of sensors as a grammatical more
0:22:55and so essentially the idea is
0:22:58by doing that you can apply
0:23:00patient signal processing to come up with
0:23:03so that's really all the one C thank you
0:23:09five questions to me
0:23:11that
0:23:12you're all we should really be asking questions
0:23:17um can you go back to your original picture at the beginning where you had the
0:23:22the uh
0:23:22legacy tracker and
0:23:31oh
0:23:32yeah uh yeah right so
0:23:34you have here
0:23:35um the
0:23:37try what's coming into the middle level of and you have a portable and saying feedback
0:23:42uh
0:23:43can you call in a or
0:23:45so one additional point did mention is now suppose you can infer that talk it is actually gonna in a
0:23:50rectangle
0:23:51you can use that information to help you track at the lower that
0:23:54which you low level tracker does on know that you low level tracker simply assuming a top it's sit down
0:23:58target
0:23:59flipping a point deciding where it's still
0:24:01a if you had this high level infers that you know what's gonna make a right to
0:24:04or if you look at the global maps and you figure out the constraint that the role only you can
0:24:08go left or right any can't go right out of the role
0:24:11you can of course utilise information to
0:24:13to improve you estimates and and that's that's really good
0:24:16that
0:24:16i did mention that you're so of course as a feedback structure where you can use that to
0:24:20proof proof you
0:24:25yeah
0:24:31uh could you please one tell the differences between a stochastic context free grammar and the mark of tree as
0:24:37a small doing and in is can a good point
0:24:40okay so the idea here is
0:24:43we're looking at a actually a a a probably go to that little picture which are
0:24:49okay so
0:24:51this would be a standard finite state markov chain which is kind of a
0:24:55this is our parse tree which is really and count and what's and branching process so i start with
0:25:01a bunch of parents they have children they actually not children and so on and it keeps scrolling
0:25:05but the point is the order of the chill the name of the children matters in a standard multi think
0:25:09type gas the what's process you only K they have three kids of for kids
0:25:13here the name of the matter because they can wait different trajectories
0:25:16eventually
0:25:18all these children stop and that's your all of that the the thing you read and you meet a from
0:25:22that to right and that's for example that all or some sort of straw
0:25:26so that's the multi type gas and what's some process we considering here
0:25:29so it's really a a realisation of for tree whose size
0:25:34is not a you know
0:25:36you could only
0:25:37more the expectation of that
0:25:38you to come up with the as of that and and so
0:25:49okay well are out of time thank very much we go to the next speaker or no