classifiers/Perceptron.c File Reference

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <assert.h>
#include <stdint.h>
#include "Perceptron.h"
#include "../msg.c"
#include "../bio/mkSfx.c"
#include "../bio/new.c"
#include "../bio/ch2Id.c"
#include "../bio/save.c"
#include "../bio/find.c"
#include "../bio/mapP.c"
#include "../bio/del.c"
#include "../hash/nps_vocab.c"
#include "../imat/InstMatLoL.c"
#include "../hash/Intern.c"
#include "../num/blas/level1/cblas_daxpy.c"
#include "../num/blas/level1/cblas_dscal.c"
#include "../num/permute.c"

Classes

struct  nps_avgperc_t
struct  Nps_PercModel

Functions

struct Nps_PercModelnps_newPercModel (nps_error_t *err, struct Nps_Intern *featDict, struct Nps_Intern *labDict, char ignoreBias)
struct Nps_PercModelnps_PercModel_FromModelDir (nps_error_t *err, const char *const model_dir)
struct Nps_PercModelnps_PercModel_ctor (struct Nps_PercModel *o, nps_error_t *error, va_list *app)
int nps_PercModel_dtor (struct Nps_PercModel *o, nps_error_t *err)
int nps_initPercModel (nps_error_t *err)
struct nps_avgperc_tperc_model_avg_alloc (int64_t numFeats, int64_t numCats)
void perc_model_avg_free (struct nps_avgperc_t *o)
double perc_model_binary_error (struct Nps_PercModel *o, double *test_weights, int64_t biasIndex, struct nps_InstMatLoL *mat)
double perc_model_multi_error (struct Nps_PercModel *o, double *test_weights, int64_t biasIndex, struct nps_InstMatLoL *mat)
int perc_model_binary_train (struct Nps_PercModel *o, nps_error_t *e, struct nps_InstMatLoL *mat, int64_t maxIterations, FILE *out)
int perc_model_multi_train (struct Nps_PercModel *o, nps_error_t *e, struct nps_InstMatLoL *mat, int64_t maxIterations, FILE *out)
double nps_PercModel_binary_predict (struct Nps_PercModel *o, s8f8_svec_t *svec, double *out_pred)
int64_t nps_PercModel_multi_predict (struct Nps_PercModel *o, s8f8_svec_t *svec, double *out_preds)
void perc_model_del (perc_model_t *o)
int perc_model_save (struct Nps_PercModel *o, const char *root, nps_error_t *err)

Variables

struct Nps_PercModelNps_PercModel

Function Documentation

int nps_initPercModel ( nps_error_t err  ) 
struct Nps_PercModel* nps_newPercModel ( nps_error_t err,
struct Nps_Intern featDict,
struct Nps_Intern labDict,
char  ignoreBias 
) [read]
double nps_PercModel_binary_predict ( struct Nps_PercModel o,
s8f8_svec_t svec,
double *  out_pred 
)
struct Nps_PercModel* nps_PercModel_ctor ( struct Nps_PercModel o,
nps_error_t error,
va_list *  app 
) [read]
int nps_PercModel_dtor ( struct Nps_PercModel o,
nps_error_t err 
)
struct Nps_PercModel* nps_PercModel_FromModelDir ( nps_error_t err,
const char *const   model_dir 
) [read]
int64_t nps_PercModel_multi_predict ( struct Nps_PercModel o,
s8f8_svec_t svec,
double *  out_preds 
)
struct nps_avgperc_t* perc_model_avg_alloc ( int64_t  numFeats,
int64_t  numCats 
) [read]
void perc_model_avg_free ( struct nps_avgperc_t o  ) 
double perc_model_binary_error ( struct Nps_PercModel o,
double *  test_weights,
int64_t  biasIndex,
struct nps_InstMatLoL mat 
)
int perc_model_binary_train ( struct Nps_PercModel o,
nps_error_t e,
struct nps_InstMatLoL mat,
int64_t  maxIterations,
FILE *  out 
)

perc_model_binary_train implements the training procedure for the averaged perceptron. The averaged perceptron is a variant of the voted perceptron that was introduced in: Freund, Y. and Schapire, R. E. 1999. Large margin classification using the perceptron algorithm. In Machine Learning 37(3):277-296, 1999.

It is a good idea to normalize mat before calling this procedure.

The implementation uses a trick involving sparse vectors that greatly speeds up computation.

In interpretting the details below, the reader should also have Figure 1 of Freund and Schapire ... in front of them as we pick up using their notation and definitions (e.g. $m$).

In the standard representation, the weighted/averaged perceptron may be written:

{eqnarray} {y} &=& {sign}(s), {where} \ s &=& ^k c_i {v_i} {x}. \ {eqnarray} By introducing a new "average vector" ${a}$, we can simplify the decision rule as: {eqnarray} s & = & {a} {x}. {eqnarray} Now we can define the components of ${a}$ in a way that does not require a dense dot product of training set sparse vectors ${x_t}$. {eqnarray} a_i & = & - {t}^T (T-t) x_{ti} 1_{t {correct}} y_t & = & {t}^T t x_{ti} 1_{t {correct}}y_t - T {t}^T x_{ti} 1_{t {correct}}y_t {eqnarray}

So a_i is decomposed into two "left" and "right" expressions with very interesting properties Both quantities can be computed in streaming fashion using sparse vector operations, requiring only a single dense vector operation at the end of the computation. Also, the second expression is non other than w_{i}, where w_{i} is a perceptron computed in standard (i.e. non-weighted fashion). It is difficult to give the second quantity an intuitive term, and so in the implementation below we will reuse the variable W[] (with caps) to hold this data until combining it with w[] at the end of the routine.

void perc_model_del ( perc_model_t o  ) 
double perc_model_multi_error ( struct Nps_PercModel o,
double *  test_weights,
int64_t  biasIndex,
struct nps_InstMatLoL mat 
)
int perc_model_multi_train ( struct Nps_PercModel o,
nps_error_t e,
struct nps_InstMatLoL mat,
int64_t  maxIterations,
FILE *  out 
)
int perc_model_save ( struct Nps_PercModel o,
const char *  root,
nps_error_t err 
)

Variable Documentation

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines
Generated on Sun Sep 11 09:40:46 2011 for NPSML by  doxygen 1.6.3