0:00

We've previously talked about maximum likelihood destination from Markov random

fields. Though when we first defined Markov

random fields, we also defined a, an extension on MRFs called conditional

random fields or CRFs. So, now let's think about how the ideas

that we developed in the context of MRFs can be utilized for the maximum

likelihood destination of a conditional random field.

So as a reminder the point of the CRF was to compute the probability of a

particular set of target variables Y given an, a set observe variables X. And,

the idea behind this was that, although, the unnormalized density p tilde of X, Y

was defined in exactly the same kind of parameterization,

whether there's a product of factors or as a log-linear model.

As in the MRF case, the difference here is that we have a a,

an X specific partition function that guarantees that what we have is a

normalized distribution over the Y variables given a particular X.

So this partition function is the sum over all Ys of the unnormalized measure p

tilde theta of X, Y and so it normalizes only all the Ys and not just, and not the

Xs. When learning CRFs, our data is now a set

of pairs. It's a set of input variables or observed

features X and a set of target variables Y.

And in the training data, both of these are observed and we'd like to use this to

learn conditional distribution of Y given X.

So the right objective function that we're going to apply in this context is

the what's often called the conditional log likelihood but really should be

called the log conditional likelihood, because the conditioning is inside the

log. And what we have in terms of this of this

objective is the sum over all data instances m of the log of the conditional

probability of Y given X. So, if we look at the conditional log

likelihood and we basically open it up, we end up with a, an expression that

looks very similar to what we saw in the case of MRFs.

We have a sum over i of, and this is for the case of a log linear

model, we have a sum over i of the parameter

theta i multiplied by the value of the feature, fi.

This is for a particular instance XY. So it's theta i fi of Xm, Ym.

And, over here, we have a in, a negative minus log of the

partition function for X of m and this uses the exact same derivation that we

had for the case of an MRF. And so now we can sum up over multiple

data instances m and compute the derivative relative to a particular

parameter theta i of the one over m of the log conditional likelihood.

and then, what we end up with is a, again, again an average of, in this case,

the sum over two expectations. So, what we have in the, we have a

summation over m and the first term is the value of the feature function fi of

Xm, Ym and the second term is the expected,

expectation of that feature fi relative to Xm and Y.

Now, it's important to look carefully at the second expression over here,

E theta of fi Xm, Y. And note, that here, the expect, the Xm

is fixed and the expectation is taken only over the variables Y.

And this is in contrast to the case of MRFs where we were taking the expectation

relative to the entire set of variables. Let's see how this pans out in the

context of a particular example, so we're going to look a really brain dead notion,

model for image segmentation, where we just have two features, f1 and f2.

The first feature, f1, is a singleton feature and it takes the value of the

average green value for pixels in a superpixel s.

So if this is my superpixel s, we average out all of the green superpixels, but we

only put them into that feature in cases where that pixel is labelled with g for

grass. So and notice that this feature is

repeated across all superpixels s in the image, so this is a model with shared

parameters. The second feature, f2, is a pairwise

feature, and here we get a one for cases where two adjacent superpixels s and t

are labeled the same value, say both grass or both cow.

And this allows the model to learn how likely it is for superpixels that are

adjacent to each other to have the same class label.

Notice that this model too had this feature too is shared both across pairs

of superpixels, but also across different classes.

That is we have the same parameter for cow, cow as we do for grass, grass, or

sky, sky. So let's plug in these two features into

the the model for the radiant that we had on the previous slide, so this is the

general equation and let's see what happens for theta one.

So the partial derivative relative to the parameter theta one has the difference of

two expectations, again, and empirical expectation, and a

and a model expectation. So, this is for particular instance m, so we're not

currently averaging across multiple training images. We have a single image m

that we're working over. So here, because the model has shared

parameters, we're summing over all possible superpixels s in the image and

the empirical expectation sums up the product of this indicator function for

the superpixel s multiplied the, this average greeness of the superpixel and

that's the empirical expectation. The model-based expectation has exactly

the same form, we're also summing up over all superpixels s and we similarly have a

product of two terms only here, because we don't know whether, because in this

model-based expectation, we don't have the Y labels, we're computing the

probability over the Y label taking the value grass. That is for each superpixel

s, we compute the probability that Ys takes the value green given but we know

about the image, that is the, the values x of m and that gets multiplied with the

average greenness again. So that's the gradient for the first

parameter. The gradient for the second parameter is

very similar in spirit. So here, we're looking at the sum over

all pairs of adjacent superpixel s and t and the empirical expectation just sums

that over all those pairs with an indicator function of Ys is equal to Yt.

So we a one if Ys is the same as Yt Say, they're both labeled grass or they're

both labeled cow, and zero otherwise. And in the, in the model based

expectation term, we have the probability of that event.

That is, the probability that ys is = to yt.

given the image. And once again, that's summed up over all

pairs of, adjacent superpixels, s and t. So, again, a difference of two

expectations in both cases. An empirical expectation, and a model

based expectation. Taking that and thinking about this let's

compare the computational cost of two of two models, of two training regimes.

One is the MRF training and the second is the CRF training.

So in the MRF training remember that our gradient relative to parameter theta I

was the difference of two expectations. And we've already pointed out that the

computation of the second expectation, the model based expectation requires that

we run inference at each gradient and we thought that was pretty expensive or it

could be, but now lets see what happens for serifs, lets look at that gradient

for more time, for the case of serifs and here notice that we don't really have.

That, that we have a summation over M. That is a summation over all of the data

instances of a difference of two terms. The second is the feature value in that

particular instance. And the second, is the expected feature

value in that particular instance, X of M.

So. The important observation to come out of

this is that this expectation, the second expectation, relative to theta, is an

expectation that is different for each of our input instances.

So that means that we need to rerun this inference for each and every one of our x

m's at each gradient step. So whereas mrf's requires one inference.

At each gradient step. This requires M inferences at each

gradient step. Where M is the number of training

instances. And so here, the inference required to do

learning is considerably more expensive. However, one needs to weigh the balance

of all of the factors that contribute to computational cost.

So, when we're doing inference of the conditional probability, P of Y, given X.

We only need to worry about the y variables.

So the Xs are all fixed, their values are instantiated.

And so our factors in the resulting model are factors only over the variables one.

If we were to want to use mrf training because say we decided that crf trainings

too expensive because of the additional cost of inference we would need to

compute the joint probability p of yx which.

Might be much more complicated. And that might be much more complicated

not only because of the fact that we have more variables now in the model both the

y's and the x's. But also because in many cases where we

would like to apply crf, the distribution that we might have over the x's becomes

quite un-, unmanageable if we want to compute a distribution over that.

So to understand that, let's go back to the previous example and consider this

very simple image segmentation model. And here notice that the x.

The, the variable x sub s implies this This average greenness of the superpixel.

Now, in the context of CRFs, we don't need to compute a distribution over

average greenness, because we're conditioning on the X of s.

And so g of s is now fixed, it's instantiated.

And we're only computing the probability distribution over the ys.

But if we wanted to train this model as an MRF, we would need to somehow maintain

a distribution over this average greenness.

And since that's a continuous quantity. It actually requires that we think about

parametric forms. And is it a Gaussian, or, or a mixture of

Gaussian. Gaussians, and it becomes quite hairy to

manage. And so.

Although there, the CRF based training in this case, might have additional cost, it

can also reduce the cost, in terms of any particular inference step as well as

avoided a bunch of thorny issues regarding, parameterization of the

distribution over various features. [SOUND] So to summarize, CRF learning, in

terms of the mathematical formulation is very similar to MRF learning.

The likelihood function has the same form, it's concave.

It's similarly optimized using gradient ascent, usually the same L-BFGS

algorithm. However the gradient computation is now

much more expensive, because it requires inference not only once per gradient

step, but also once per gradient step and data instance,

and as a comparison, once per gradient step in the context of MRF's.

But as we already said, as we just said, the conditional model is often much

simpler, so the inference calls for a CRF and the MRF is not the same, so we're not

really comparing apples and oranges. And, so in the context of any given

model, one really needs to think about which of these models is more

appropriate. And not only based on the computational

costs of training, but also in terms of the overall performance and

generalization.