svm_struct_api.c

svm(支持向量机)分类算法本质上是二类分类器

/***********************************************************************/
/*                                                                     */
/*   svm_struct_api.c                                                  */
/*                                                                     */
/*   Definition of API for attaching implementing SVM learning of      */
/*   structures (e.g. parsing, multi-label classification, HMM)        */ 
/*                                                                     */
/*   Author: Thorsten Joachims                                         */
/*   Date: 03.07.04                                                    */
/*                                                                     */
/*   Copyright (c) 2004  Thorsten Joachims - All rights reserved       */
/*                                                                     */
/*   This software is available for non-commercial use only. It must   */
/*   not be modified and distributed without prior permission of the   */
/*   author. The author is not responsible for implications from the   */
/*   use of this software.                                             */
/*                                                                     */
/***********************************************************************/

#include <stdio.h>
#include <string.h>
#include "svm_struct/svm_struct_common.h"
#include "svm_struct_api.h"

SAMPLE      read_struct_examples(char *file, STRUCT_LEARN_PARM *sparm)
{
  /* Reads training examples and returns them in sample. The number of
     examples must be written into sample.n */
  SAMPLE   sample;  /* sample */
  EXAMPLE  *examples;
  long     n;       /* number of examples */
  DOC **docs;       /* examples in original SVM-light format */ 
  double *target;
  long totwords,i;

  /* Using the read_documents function from SVM-light */
  read_documents(file,&docs,&target,&totwords,&n);
  examples=(EXAMPLE *)my_malloc(sizeof(EXAMPLE)*n);
  for(i=0;i<n;i++) {   /* copy docs over into new datastructure */
    examples[i].x.doc=docs[i];
    examples[i].y.class=target[i]+0.1;
  }
  free(target);
  free(docs);
  sample.n=n;
  sample.examples=examples;

  if(struct_verbosity>=0)
    printf(" (%d examples) ",sample.n);
  return(sample);
}

void        init_struct_model(SAMPLE sample, STRUCTMODEL *sm, 
			      STRUCT_LEARN_PARM *sparm)
{
  /* Initialize structmodel sm. The weight vector w does not need to be
     initialized, but you need to provide the maximum size of the
     feature space in sizePsi. This is the maximum number of different
     weights that can be learned. Later, the weight vector w will
     contain the learned weights for the model. */
  long i,totwords=0;
  WORD *w;

  sparm->num_classes=1;
  for(i=0;i<sample.n;i++)     /* find highest class label */
    if(sparm->num_classes < (sample.examples[i].y.class+0.1)) 
      sparm->num_classes=sample.examples[i].y.class+0.1;
  for(i=0;i<sample.n;i++)     /* find highest feature number */
    for(w=sample.examples[i].x.doc->fvec->words;w->wnum;w++) 
      if(totwords < w->wnum) 
	totwords=w->wnum;
  sparm->num_features=totwords;
  if(struct_verbosity>=0)
    printf("Training set properties: %d features, %d classes\n",
	   sparm->num_features,sparm->num_classes);
  sm->sizePsi=sparm->num_features*sparm->num_classes;
  if(struct_verbosity>=2)
    printf("Size of Phi: %ld\n",sm->sizePsi);
}

CONSTSET    init_struct_constraints(SAMPLE sample, STRUCTMODEL *sm, 
				    STRUCT_LEARN_PARM *sparm)
{
  /* Initializes the optimization problem. Typically, you do not need
     to change this function, since you want to start with an empty
     set of constraints. However, if for example you have constraints
     that certain weights need to be positive, you might put that in
     here. The constraints are represented as lhs[i]*w >= rhs[i]. lhs
     is an array of feature vectors, rhs is an array of doubles. m is
     the number of constraints. The function returns the initial
     set of constraints. */
  CONSTSET c;
  long     sizePsi=sm->sizePsi;
  long     i;
  WORD     words[2];

  if(1) { /* normal case: start with empty set of constraints */
    c.lhs=NULL;
    c.rhs=NULL;
    c.m=0;
  }
  else { /* 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;
    }
  }
  return(c);
}

LABEL       classify_struct_example(PATTERN x, STRUCTMODEL *sm, 
				    STRUCT_LEARN_PARM *sparm)
{
  /* Finds the label yhat for pattern x that scores the highest
     according to the linear evaluation function in sm, especially the
     weights sm.w. The returned label is taken as the prediction of sm
     for the pattern x. The weights correspond to the features defined
     by psi() and range from index 1 to index sm->sizePsi. If the
     function cannot find a label, it shall return an empty label as
     recognized by the function empty_label(y). */
  LABEL y;
  DOC doc;
  long class,bestclass=-1,first=1,j;
  double score,bestscore=-1;
  WORD *words;

  doc=*(x.doc);
  words=doc.fvec->words;
  for(j=0;(words[j]).wnum != 0;j++) {       /* Check if feature numbers   */
    if((words[j]).wnum>sparm->num_features) /* are not larger than in     */
      (words[j]).wnum=0;                    /* model. Remove feature if   */
  }                                         /* necessary.                 */
  for(class=1;class<=sparm->num_classes;class++) {
    y.class=class;
    doc.fvec=psi(x,y,sm,sparm);
    score=classify_example(sm->svm_model,&doc);
    free_svector(doc.fvec);
    if((bestscore<score)  || (first)) {
      bestscore=score;
      bestclass=class;
      first=0;
    }
  }
  y.class=bestclass;
  return(y);
}

LABEL       find_most_violated_constraint_slackrescaling(PATTERN x, LABEL y, 
						     STRUCTMODEL *sm, 
						     STRUCT_LEARN_PARM *sparm)
{
  /* Finds the label ybar for pattern x that that is responsible for
     the most violated constraint for the slack rescaling
     formulation. It has to take into account the scoring function in
     sm, especially the weights sm.w, as well as the loss
     function. The weights in sm.w correspond to the features defined
     by psi() and range from index 1 to index sm->sizePsi. Most simple
     is the case of the zero/one loss function. For the zero/one loss,
     this function should return the highest scoring label ybar, if
     ybar is unequal y; if it is equal to the correct label y, then
     the function shall return the second highest scoring label. If
     the function cannot find a label, it shall return an empty label
     as recognized by the function empty_label(y). */
  LABEL ybar;
  DOC doc;
  long class,bestclass=-1,first=1;
  double score,bestscore=-1;

  doc=*(x.doc);
  for(class=1;class<=sparm->num_classes;class++) {
    ybar.class=class;
    doc.fvec=psi(x,ybar,sm,sparm);
    score=classify_example(sm->svm_model,&doc);
    free_svector(doc.fvec);
    if(((bestscore<score)  || (first)) && (y.class!=class)) {
      bestscore=score;
      bestclass=class;
      first=0;
    }
  }
  if(bestclass == -1) 
    printf("ERROR: Only one class\n");
  ybar.class=bestclass;
  if(struct_verbosity>=3)
    printf("[%ld:%.2f] ",bestclass,bestscore);
  return(ybar);
}

LABEL       find_most_violated_constraint_marginrescaling(PATTERN x, LABEL y, 
						     STRUCTMODEL *sm, 
						     STRUCT_LEARN_PARM *sparm)
{
  /* Finds the label ybar for pattern x that that is responsible for
     the most violated constraint for the margin rescaling
     formulation. It has to take into account the scoring function in
     sm, especially the weights sm.w, as well as the loss
     function. The weights in sm.w correspond to the features defined
     by psi() and range from index 1 to index sm->sizePsi. Most simple
     is the case of the zero/one loss function. For the zero/one loss,
     this function should return the highest scoring label ybar, if
     ybar is unequal y; if it is equal to the correct label y, then
     the function shall return the second highest scoring label. If
     the function cannot find a label, it shall return an empty label
     as recognized by the function empty_label(y). */

  /* margin and slack rescaling are equivalent for zero/one loss */
  return(find_most_violated_constraint_slackrescaling(x,y,sm,sparm));
}

int         empty_label(LABEL y)
{
  /* Returns true, if y is an empty label. An empty label might be
     returned by find_most_violated_constraint_???(x, y, sm) if there
     is no incorrect label that can be found for x, or if it is unable
     to label x at all */
  return(y.class<0.9);
}

SVECTOR     *psi(PATTERN x, LABEL y, STRUCTMODEL *sm,
		 STRUCT_LEARN_PARM *sparm)
{
  /* Returns a feature vector describing the match between pattern x and
     label y. The feature vector is returned as an SVECTOR
     (i.e. pairs <featurenumber:featurevalue>), where the last pair has
     featurenumber 0 as a terminator. Featurenumbers start with 1 and end with
     sizePsi. This feature vector determines the linear evaluation
     function that is used to score labels. There will be one weight in
     sm.w for each feature. Note that psi has to match
     find_most_violated_constraint_???(x, y, sm) and vice versa. In
     particular, find_most_violated_constraint_???(x, y, sm) finds that
     ybar!=y that maximizes psi(x,ybar,sm)*sm.w (where * is the inner
     vector product) and the appropriate function of the loss.  */
  SVECTOR *fvec;
  long i;

  fvec=create_svector(x.doc->fvec->words,x.doc->fvec->userdefined,1.0);
  for(i=0;fvec->words[i].wnum;i++) { /* move to weight vector of class y */
    fvec->words[i].wnum+=(y.class-1)*sparm->num_features;