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_PercModel *	nps_newPercModel (nps_error_t *err, struct Nps_Intern *featDict, struct Nps_Intern *labDict, char ignoreBias)
struct Nps_PercModel *	nps_PercModel_FromModelDir (nps_error_t *err, const char *const model_dir)
struct Nps_PercModel *	nps_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_t *	perc_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_PercModel *	Nps_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

struct Nps_PercModel* Nps_PercModel