CSE 254 LECTURE NOTES

April 10, 2007


ANNOUNCEMENTS

Handout today:  A warm-up assignment and also a sign-up sheet for paper presentations by students.


FEATURES AND WEIGHTS

Remember:  A feature is a real-valued function of both the data space X and the label space Y: a function f: X x Y -> R.   Features can overlap in arbitrary ways.  

Log-linear models have one real-valued weight for each feature, no more no less.  Let the features be subscripted i and let the weights be w_i.

Almost all features are presence/absence indicator functions so the real value is either 0 or 1.  We often sum over a training set and talk about the value of a feature on the whole training set.

Given a test example x we classify it with the label y that has highest total weight   SUM_i w_i f_i(x,y)

Remember that each feature f_i is real-valued.  Typically it is zero for all values of y except one particular one.  Given some attribute value of x, we can have a different weight for this attribute value and each different label.  These weights can capture the affinity of this attribute-value for each label.

The learning problem is to choose values for the weights.  Since this is just a linear model we could train it in a non-probabilistic way, e.g. with a perceptron.  But we'll go probabilistic.


MAXIMUM CONDITIONAL LIKELIHOOD

Define  p(y | x; w)  =  exp SUM_i w_i f_i(x,y)  /   SUM_y' exp SUM_i w_i f_i(x,y)  
Our goal is to choose parameter values w_i to maximize the conditional probability of the training examples.

Let (C,D) be the training set.  C is all the labels of the training examples (labels are called y above) and D is all the feature values (called x above).  We have

log p(C | D, w)  =  log PROD_(C,D)  p(c | d; w)  =  SUM_(C,D)  log p(c | d; w)

Using the softmax function and separating its numerator from its denominator we get

log p(C | D, w)  =  SUM_CD log exp [ SUM_i w_i f_i(d,c) ]   -   SUM_CD log SUM_c' exp SUM_i w_i f_i(d,c')

The lefthand part of the big sum is N(w) = SUM_CD SUM_i w_i f_i(d,c)   which is going to be tractable because it is purely linear.  Call the righthand part  M(w).  This will be tougher because there is a sum inside a log.


TAKING DERIVATIVES

Our approach to maximizing the conditional likelihood will be to compute derivatives explicitly and then use a black-box numerical optimization algorithm based on these derivatives.  So for each weight w_i we need to evaluate  d/dw_i N(w)  and also  d/dw_i  M(w).

d/dw_i N(w)  =    SUM_CD f_i(d,c)

In words, the derivative of the log-numerator is the empirical count: the sum over all training examples (c,d) of the observed value of feature i.

Write  M(w) = SUM_CD log SUM_c' exp g'.  We will use the chain rule to get the derivative of  log SUM_c' exp g'  step by step.

d/dw_i [ log SUM_c' exp g' ] =  [ 1/ SUM_c exp g ] [ d/dw_i SUM_c' exp g']   =   [ 1/ SUM_c' exp g' ] [ SUM_c' exp g' [ d/dw_i g' ] ]

Now put the outer sum inside the inner sum, changing the variable name from c' to c".  Notice that  d/dw_i g' = f_i(d,c').   This gives

                       =  SUM_c' [ exp g' / [ SUM_c" exp g" ] ] f_i(d,c')

                       =  SUM_c'  p(c' | d, w)  f_i(d,c')

In words, the derivative of the log-denominator is the expected value according to the model of feature i.  This expectation is a sum over all training examples d.  The sum ignores the actual labels c and instead averages over the potential labels c'.


SETTING THE DERIVATIVE TO ZERO

We have a function to maximize, namely the log of the conditional likelihood of the training data.  At the maximum, the derivatives will be zero.  This means that d/dw_i [N(w) - M(w]  = 0  i.e.

SUM_CD f_i(d,c)  =  SUM_CD  SUM_c'  p(c' | d, w)  f_i(d,c')

The lefthand side above is the total value of feature i on the whole training set.  The righthand side is the total value of feature i predicted by the model.  In other words, for each feature, the trained model will spread out over all examples as much mass as the training data has just on those examples for which the feature is nonzero.  


CHECKING CORRECTNESS

For any particular application of log-linear modeling, you have to write code to evaluate numerically the symbolic derivatives.  Then you call a blackbox optimization function to find the optimal parameter values.  How can you check you have not made a mistake?

Answer 1:  Verify for each feature that  SUM_CD f_i(d,c)  =  SUM_CD  SUM_c'  p(c' | d, w)  f_i(d,c').

Answer 2:  Verify that your derivatives are correct compared to finite differencing.


NONLINEAR OPTIMIZATION

We have a function from R^n to R that we want to maximize.  First, what sort of optimization problem do we have?  Nonlinear and unconstrained.

The gradient is the n by 1 vector of partial derivatives.  The Hessian is the n by n matrix of second derivatives.  We assume that we can compute the gradient exactly, and that we have memory to store it.  Neither fact is true for the Hessian.

We'll use a global method: the entire x vector will be updated at once.  (An alternative is called stochastic descent.)  The method will be iterative: we will find x_1, x_2, etc. such that f(x_i+1) >= f(x_i) for each iteration i.

The method will use a "line search:"  x_i+1 = argmax_t f(x_i + t*s_i)  for fixed x_i and s_i.   The direction vector s_i  will be a function of the gradient at x_i.  Let's assume we know how do line search: this is a one-dimensional problem so it is not too difficult.