widrowhoff.c

使用具有增量学习的监控式学习方法。包括几个不同的分类算法。

/* Copyright (C) 2001-2002  Mikael Ylikoski
 * See the accompanying file "README" for the full copyright notice */
/**
 * @file
 * Widrow-Hoff learning algorithm.
 * Also known as Least-Mean-Square (LMS) algorithm.
 *
 * For a description of the algorithm see Lewis, D.D., Schapire, R.E.,
 * Callan, J.P. & Papka, R., <em>Training algorithms for Linear
 * Text Classifiers</em>, 1996.
 *
 * @author  Mikael Ylikoski
 * @date    2001-2002
 */

#include <stdlib.h>
#include <string.h>
#include "multi.h"
#include "parray.h"
#include "utility.h"
#include "vector.h"
#include "widrowhoff.h"


/**
 * Widrow-Hoff database
 */
struct widrowhoff_db_ {
    float ny;		/**< Learning rate */
};


/**
 * Widrow-Hoff class
 */
typedef struct {
    vector *w;		/**< Weight vector */
    vector *mean;	/**< Class mean vector */
    int n;		/**< Number of training examples */
} widrowhoff_class;


/**
 * Create a new global state.
 *
 * @return  The classifier.
 */
void *
widrowhoff_new_db (const char *opts) {
    float f;
    widrowhoff_db *db;

    db = my_malloc (sizeof(widrowhoff_db));
    db->ny = 0.8;

    if (opts) {
	f = get_opt_flt (opts, "a=");
	if (f > 0)
	    db->ny = f;
    }

    return db;
}


/**
 * Create a new classifier.
 *
 * @return  The classifier.
 */
void *
widrowhoff_new (void) {
    widrowhoff_class *whc;

    whc = my_malloc (sizeof(widrowhoff_class));
    whc->w = vector_new (10);
    if (!whc->w) {
	free (whc);
	return NULL;
    }
    whc->mean = vector_new (10);
    if (!whc->mean) {
	free (whc->w);
	free (whc);
	return NULL;
    }
    whc->n = 0;

    return whc;
}


/**
 * Copy a class.
 *
 * @param data  class to copy
 * @return  The copy
 */
void *
widrowhoff_copy (void *data) {
    widrowhoff_class *dc;
    widrowhoff_class *whc;

    whc = my_malloc (sizeof(widrowhoff_class));
    dc = (widrowhoff_class *)data;
    whc->w = vector_copy (dc->w);
    if (!whc->w) {
	free (whc);
	return NULL;
    }
    if (dc->mean) {
	whc->mean = vector_copy (dc->mean);
	if (!whc->mean) {
	    free (whc->w);
	    free (whc);
	    return NULL;
	}
    } else
	whc->mean = NULL;
    whc->n = dc->n;

    return whc;
}


/**
 * Free a class.
 *
 * @param data  class to free
 */
void
widrowhoff_free (void *data) {
    widrowhoff_class *whc;

    whc = (widrowhoff_class *)data;
    vector_free (whc->w);
    if (whc->mean)
	vector_free (whc->mean);
}


/**
 * Learn from a positive example.
 *
 * @param db     classifier database
 * @param data   class
 * @param v      example vector
 * @param class  example class
 */
int
widrowhoff_learn (void *db, void *data, vector *v, int class) {
    double d;
    widrowhoff_class *whc;
    widrowhoff_db *wdb;

    whc = (widrowhoff_class *)data;
    wdb = (widrowhoff_db *)db;

    d = vector_dot_product (whc->w, v);
    if (class > 0)
	vector_add_w (whc->w, v, -wdb->ny * (d - 1));
    else
	vector_add_w (whc->w, v, -wdb->ny * d);
    //vector_add_w(whc->w, v, -wdb->ny * (d - (class + 1) * 0.5));
    whc->n++;
    if (whc->n == 1)
	whc->mean = vector_copy (whc->w);
    else
	vector_n_mean (whc->mean, whc->w, whc->n);

    return 0;
}


/**
 * Classify a vector.
 *
 * @param db    classifier database
 * @param data  class
 * @param v     vector to classify
 * @return  The most probable class.
 */
double
widrowhoff_classify (void *db, void *data, vector *v) {
    widrowhoff_class *whc;

    whc = (widrowhoff_class *)data;
    //return vector_dot_product (whc->mean, v);
    return vector_dot_product (whc->w, v);
}


void *
widrowhoff_load_db (FILE *file) {
    int i;
    widrowhoff_db *ndb;

    ndb = my_malloc (sizeof(widrowhoff_db));
    i = fscanf (file, "ny %f\n", &ndb->ny);

    return ndb;
}


void *
widrowhoff_load_class (FILE *file) {
    int i;
    widrowhoff_class *ncl;

    ncl = my_malloc (sizeof(widrowhoff_class));

    fscanf (file, "weights ");
    ncl->w = vector_load (file);
    if (!ncl->w) {
	free (ncl);
	return NULL;
    }
    fscanf (file, "\n");

    fscanf (file, "mean ");
    ncl->mean = vector_load (file);
    fscanf (file, "\n");

    i = fscanf (file, "n %d\n", &ncl->n);
    if (i != 1) {
	free (ncl);
	return NULL;
    }

    return ncl;
}


int
widrowhoff_save_db (FILE *file, void *db) {
    widrowhoff_db *ndb;

    ndb = (widrowhoff_db *)db;
    fprintf (file, "ny %f\n", ndb->ny);

    return 0;
}


int
widrowhoff_save_class (FILE *file, void *data) {
    widrowhoff_class *ncl;

    ncl = (widrowhoff_class *)data;
    fprintf (file, "weights ");
    vector_save (ncl->w, file);
    fprintf (file, "\n");
    fprintf (file, "mean ");
    vector_save (ncl->mean, file);
    fprintf (file, "\n");
    fprintf (file, "n %d\n", ncl->n);

    return 0;
}


/**
 * Keep cygwin happy.
 */
int
main (void) {
    return 0;
}


/**
 * Widrow-Hoff classifier name.
 */
const char *my_classifier_name = "WidrowHoff";


/**
 * Widrow-Hoff classifier functions.
 */
const multi_functions my_functions = {
    .new_db = widrowhoff_new_db,
    .new = widrowhoff_new,
    .copy = widrowhoff_copy,
    .free = widrowhoff_free,
    .learn = widrowhoff_learn,
    .classify = widrowhoff_classify,
    .load_db = widrowhoff_load_db,
    .load_class = widrowhoff_load_class,
    .save_db = widrowhoff_save_db,
    .save_class = widrowhoff_save_class,
    .option = OPTION_BINARY | OPTION_BOOLEAN
};