Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

In the Stanford ML course, we were taught to find good values for the lambda parameters of ridge/lasso by iterating for various lambda values on several cross-validation sets and picking the values which correspond to the hypothesis with the minimum CV error.

The problem is, I am playing with a big data set (which might not even be well suited for logistic regression (??): Internet Ads set) and I can't use the method described above because, during optimization, the cost stays stable (changes only around the 8th decimal place between iterations) and doesn't seem to converge.

I need good values for the regularization in order to converge, but I can't converge without the aforementioned good values.

Any suggestions? Should I move on to using SVM, or is this data set solvable with logistic regression?

NB: I am doing this for learning purposes, so I'm much more interested in explanations why my approach is bad than I am in black-box libraries which will give me a solution.

EDIT: Some relevant code snippets (occasionally pseudocode-ish, for clarity). The usual notations apply.

The function used to compute the cost:

def computeCost(theta, X, y):
    global iter
    iter += 1
    if iter > 10:
        raise TooManyIterationsException(iter) # Because the cost doesn't converge, I force interruption in order to jump to another combination of lambda values
    m = y.size
    h = sigmoid(X.dot(theta.T))
    J = y.T.dot(log(h)) + (1.0 - y.T).dot(numpy.log(1.0 - h))
    J_reg2 = theta[1:]**2
    J_reg1 = theta[1:]
    cost = (-1.0 / m) * (J.sum()) + LAMBDA2 * J_reg2.sum() + LAMBDA1 * J_reg1.sum()
    print "Cost: ", cost
    return cost

Invoking scipy.optimize.fmin_bfgs:

initial_thetas = numpy.zeros((len(train_X[0]), 1))
myargs = (train_X, train_y)

for LAMBDA1 in [0.01, 0.02, 0.04, ..., 10]:
    for LAMBDA2 in my_range[0.01, 0.02, 0.04, ..., 10]:
        try:
            iter = 0
            theta = scipy.optimize.fmin_bfgs(computeCost, x0=initial_thetas, args=myargs)            
        except TooManyIterationsException as e:
            print '\n'

A typical output looks like this: enter image description here

EDITED AGAIN: Evolution of thetas! enter image description here

share|improve this question
1  
How is it possible that your cost is not changing? The only thing I can think of is that your lambda values aren't actually different. Maybe posting code for what you have done will help to see if your situation can be re-created. –  idris Apr 25 '12 at 5:45
    
@idris I have tried manually various combinations of lambdas, but the cost is always the same. In the meantime, I have found a couple other secondary issues with my implementation; if after fixing them I'm still having problems, I'll post the relevant parts of my code here. –  Cristina Apr 25 '12 at 11:44
    
@idris Added source code, as well as an output example. Thanks! –  Cristina Apr 25 '12 at 12:39
    
@Denis I'm not sure what you meant by +/- 1-5%... shall I increase/reduce each of my thetas by those percents and use cost with them modified? By the way, updated my post -- there's an interesting trend in the thetas. The value in theta[0] is shifted in the next cost computation to theta[1], then to theta[2], and so on. I'm not sure whether this is relevant, since I don't know the details of fmin_bfgs implementation. –  Cristina Apr 26 '12 at 11:23
    
@Denis Aha, now I understand! Thank you, this kind of debugging suggestion is invaluable -- I'll check it out! –  Cristina Apr 26 '12 at 12:54
show 1 more comment

2 Answers

up vote 1 down vote accepted

Is the question "why is cost() so flat near [0 0 0 0] ?",
or "why does fmin_xx not find a minimum on a flat surface ?"
A couple of suggestions anyway:

1) look at cost() near x0, with look( f, x0, h ) -> f() at all corners of a cube of side 2h around x0, or if that's too many at a random subset.
2) is [0 0 0 0] a reasonable start point for weights ?
3) what happened to the first 3, continuous, columns of X ?
4) start with fmin() a.k.a. Nelder-Mead (at the best dim + 1 points from look()) before running fmin_xx -- more powerful but harder to drive.
5) scikit-learn SGDClassifier got to

97.3 % correct  SGDClassifier  uciml/ad*
    X (1572, 1558) Xtest (787, 1558)  -- 2/3, 1/3 split
    centre 3  -- scale all feature columns to [-1, 1]
    sgditer 100  loss log  penalty l2
11 sec
Confusion matrix: 97.3 % correct = 766 / 787
True classes down, estimated across  / true class sizes
0:  652    8  /  660  99 %
1:   13  114  /  127  90 %
share|improve this answer
    
Thank you for the extra suggestions and for all the effort you've put into my question! I feel smarter than I was a week ago :-) –  Cristina Apr 27 '12 at 13:51
add comment

I don't understand why you have two $\lambda$ values. In all the logistic regression I've encountered, there is only one $\lambda$ value, and you try different values of $\lambda$ to minimize the cost $J$. I also took the machine learning class you reference, and my Octave code looked like this.

J = 1/m * sum(-y' * log(sigmoid(X*theta)) - (1-y)'*log(1-sigmoid(X*theta)));
J += lambda/(2*m) * sum(theta(2:theta_len,:).^2);

Note that lambda should be a scalar value in this implementation.

This is the math equivalent of the above Octave statement.

$J(\theta) = \frac{1}{m}\sum\limits_{i=1}^m[y^{(i)}log(h_{\theta}(x^{(i)})) - (1-y^{(i)})log(1-h_{\theta}(x^{(i)}))] + \frac{\lambda}{2m}\sum\limits_{j=1}^n\theta^{2}_{j}$

share|improve this answer
    
What we did there was ridge regression. Based on previous suggestions in another post, I was trying to implement here elastic net regularization, which is a combination of ridge and lasso methods. Hence, I need lambda2 for ridge, and lambda1 for lasso. –  Cristina Apr 26 '12 at 7:24
    
Ok, this is out of my wheel house as I am not yet familiar with elastic net. I do notice your (\theta) look to be pretty much all zero. Might be something work looking at. –  idris Apr 26 '12 at 15:02
    
Yeah, I have a couple of directions I want to follow now, the thetas are only one of them. Thanks a lot for the idea-bouncing! :-) –  Cristina Apr 26 '12 at 15:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.