Using SVM^struct with additional contraints

The newest release of the dlib library updates its structural SVM solver to support a non-negativity constraint. You don't have to define anything special yourself or set penalty factors, just tell it which terms you want to be non-negative and it will do the right thing. There is also an object specifically for doing max-margin training on a kind of MRF solvable with graph cuts.

As a disclaimer, I wrote this library. :)

You are not doing anything wrong, but the constraints are only enforced up to the current precision of the solver (denoted by epsilon). See the following code from the original svm_struct_api.c

/* add constraints so that all learned weights are
        positive. WARNING: Currently, they are positive only up to
        precision epsilon set by -e. */
c.lhs=my_malloc(sizeof(DOC *)*sizePsi);
c.rhs=my_malloc(sizeof(double)*sizePsi);
for(i=0; i<sizePsi; i++) {
  words[0].wnum=i+1;
  words[0].weight=1.0;
  words[1].wnum=0;
  /* the following slackid is a hack. we will run into problems,
     if we have move than 1000000 slack sets (ie examples) */
  c.lhs[i]=create_example(i,0,1000000+i,1,create_svector(words,"",1.0));
  c.rhs[i]=0.0;
}

The Python equivalent (without the slackid hack) is the following:

def init_constraints(sample,sm,sparm):
    slackid = len(sample)+1

    #set constraints that each weight should be positive
    constraints = []
    for i in range(sm.size_psi):
        coefficients = svmapi.Document(svmapi.Sparse([(i,1)]))
        coefficients.slackid = slackid+i
        constraints.append((coefficients,0))

    return constraints