alma.c

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

/* Copyright (C) 2001-2002  Mikael Ylikoski
 * See the accompanying file "README" for the full copyright notice */
/**
 * @file
 * Alma learning algorithm.
 *
 * See:
 * Gentile, C., <em>A New Approximate Maximal Margin Classification
 * Algorithm</em>, 2001.
 *
 * @author  Mikael Ylikoski
 * @date    2001-2002
 */

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include "alma.h"
#include "multi.h"
#include "utility.h"
#include "vector.h"


/**
 * Alma database.
 */
typedef struct {
    float a;		/**< a in (0,1] */
    float B;		/**< B > 0 */
    float C;		/**< C > 0 */
    float p;
    float q;
} alma_db;


/**
 * Alma class.
 */
typedef struct {
    vector *w;		/**< Weight vector */
    int k;
} alma_class;


/**
 * Create a new alma database.
 *
 * @return The database.
 */
void *
alma_new_db (const char *opts) {
    alma_db *db;

    db = my_malloc (sizeof(alma_db));
    db->a = 0.6;
    db->B = 1.66666;
    db->C = 1.41421;
    db->p = 6;
    db->q = 1 / (1 - 1 / db->p);

    return db;
}


/**
 * Create a new class.
 *
 * @return The class.
 */
void *
alma_new (void) {
    alma_class *ac;

    ac = my_malloc (sizeof(alma_class));
    ac->w = vector_new (10);
    if (!ac->w) {
	free (ac);
	return NULL;
    }
    ac->k = 1;

    return ac;
}


/**
 * Copy a alma class.
 *
 * @param data  class to copy
 * @return  The copy.
 */
void *
alma_copy (void *data) {
    alma_class *nc;
    alma_class *ac;

    nc = my_malloc (sizeof(alma_class));
    ac = (alma_class *)data;
    nc->w = vector_copy (ac->w);
    if (!nc->w) {
	free (nc);
	return NULL;
    }
    nc->k = ac->k;

    return nc;
}


/**
 * Free memory used by alma class.
 *
 * @param class  class to free
 */
void
alma_free (void *class) {
    alma_class *ac;

    ac = (alma_class *)class;
    vector_free (ac->w);
    free (ac);
}


/**
 * Learn from an example.
 *
 * @param db     classifier database
 * @param data   class
 * @param v      example vector
 * @param class  example class
 */
int
alma_learn (void *db, void *data, vector *v, int class) {
    double d, lx, sk;
    alma_class *ac;
    alma_db *adb;

    ac = (alma_class *)data;
    adb = (alma_db *)db;

    lx = vector_length (v);
    sk = sqrt (ac->k);

    d = vector_dot_product (ac->w, v);
    if (d * class / lx > (1 - adb->a) * adb->B / sk)
	return 0;

    d = adb->C / (lx * sk);
    vector_add_w (ac->w, v, d * class);

    d = vector_length (ac->w);
    if (d > 1)
	vector_scale (ac->w, 1 / d);

    ac->k++;

    return 0;
}


/**
 * Learn from an example.
 * For alma-p.
 *
 * @param db     classifier database
 * @param data   class
 * @param v      example vector
 * @param class  example class
 */
int
alma_learn_p (void *db, void *data, vector *v, int class) {
    double d, lx, sk, sp;
    alma_class *ac;
    alma_db *adb;

    ac = (alma_class *)data;
    adb = (alma_db *)db;

    lx = vector_p_norm (v, adb->p);
    sk = sqrt (ac->k);
    sp = sqrt (adb->p - 1);

    d = vector_dot_product (ac->w, v);
    //printf (": %f", d);
    if (d * class / lx > (1 - adb->a) * adb->B * sp / sk)
	return 0;

    d = adb->C / (sp * lx * sk);
    //printf (": %f", d);
    vector_f (ac->w, adb->q);
    vector_add_w (ac->w, v, d * class);
    vector_f (ac->w, adb->p);

    d = vector_p_norm (ac->w, adb->q);
    //printf (": %f", d);
    if (d > 1)
	vector_scale (ac->w, 1 / d);
    ac->k++;

    return 0;
}


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

    ac = (alma_class *)data;
    return vector_dot_product (ac->w, v);
}


void *
alma_load_db (FILE *file) {
    int i;
    alma_db *adb;

    adb = my_malloc (sizeof(alma_db));
    i = fscanf (file, "a %f\n", &adb->a);
    i = fscanf (file, "B %f\n", &adb->B);
    i = fscanf (file, "C %f\n", &adb->C);
    i = fscanf (file, "p %f\n", &adb->p);
    adb->q = 1 / (1 - 1 / adb->p);

    return adb;
}


void *
alma_load_class (FILE *file) {
    int i;
    alma_class *ncl;

    ncl = my_malloc (sizeof(alma_class));
    i = fscanf (file, "k %d\n", &ncl->k);
    fscanf (file, "weights ");
    ncl->w = vector_load (file);
    if (!ncl->w) {
	free (ncl);
	return NULL;
    }
    fscanf (file, "\n");

    return ncl;
}


int
alma_save_db (FILE *file, void *db) {
    alma_db *adb;

    adb = (alma_db *)db;
    fprintf (file, "a %f\n", adb->a);
    fprintf (file, "B %f\n", adb->B);
    fprintf (file, "C %f\n", adb->C);
    fprintf (file, "p %f\n", adb->p);

    return 0;
}


int
alma_save_class (FILE *file, void *data) {
    alma_class *ncl;

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

    return 0;
}


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


/**
 * Alma classifier name.
 */
const char *my_classifier_name = "Alma";


/**
 * Alma classifier functions.
 */
const multi_functions my_functions = {
    .new_db = alma_new_db,
    .new = alma_new,
    .copy = alma_copy,
    .free = alma_free,
    .learn = alma_learn,
    .classify = alma_classify,
    .load_db = alma_load_db,
    .load_class = alma_load_class,
    .save_db = alma_save_db,
    .save_class = alma_save_class,
    .option = OPTION_BINARY
};