---

gnn_weight_elimination.c

Go to the documentation of this file.

/***************************************************************************
 *  @file gnn_weight_elimination.c
 *  @brief gnn_weight_elimination Implementation.
 *
 *  @date   : 05-10-03 19:23
 *  @author : Pedro Ortega C. <peortega@dcc.uchile.cl>
 *  Copyright  2003  Pedro Ortega C.
 ****************************************************************************/
/*
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Library General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

/**
 * @brief Weight Elimination Regularization.
 * @defgroup gnn_weight_elimination_doc gnn_weight_elimination : Weight Elimination Regularization.
 * @ingroup gnn_criterion_doc
 *
 * This datatype implements the \em Weight \em Elimination Regularization,
 * given by the error penalty term:
 *
 * \f[ \Omega = \sum_i \frac{ w_i^2 }{ \hat{w}^2 + w_i^2 } \f]
 *
 * Where the \f$w_i, i=0,\ldots,L\f$ are parameters that have been chosen
 * from a \ref gnn_node by hand. They are usually those of a \ref gnn_weight
 * linear transform node. The term \f$\hat{w}\f$ is a scale parameter that
 * usually is taken of order unity. The \em weight \em elimination regularizer
 * will favour few large terms rather than many small ones, like in
 * \em weight \em decay (\ref gnn_weight_decay).
 *
 * Although the weights never fall to zero in practice, after training the
 * associated \ref gnn_node a while, you can call the
 * \ref gnn_weight_elimination_prun function, which deletes the weights
 * below a given threshold.
 *
 * As in general with all regularizers, the \ref gnn_weight_elimination doesn't
 * work by itself, and needs a \ref gnn_criterion to build upon.
 *
 * The resulting error function is:
 *
 * \f[ \widetilde{E} = E + \nu \Omega \f]
 *
 * where \f$\nu\f$ is the regularization coeffcient. The corresponding
 * gradient is:
 * \f[ \frac{\partial \widetilde{E}}{\partial w_l} =
 *         2 w_i \frac{ \hat{w}^2 }{ (\hat{w}^2 + w_i ^2)^2 }
 * \f]
 */



/******************************************/
/* Include Files                          */
/******************************************/

#include <math.h>
#include "gnn_utilities.h"
#include "gnn_weight_elimination.h"



/******************************************/
/* Static Declaration                     */
/******************************************/

typedef struct _gnn_weight_elimination gnn_weight_elimination;

struct _gnn_weight_elimination
{
    gnn_criterion  crit;
    gnn_criterion *subcrit;
    gnn_pbundle   *pb;
    gsl_vector    *w;
    gsl_vector    *dw;
    double         nu;
    double         wp;
};


double
gnn_weight_elimination_e (gnn_criterion *crit,
                          const gsl_vector *y,
                          const gsl_vector *t);

int
gnn_weight_elimination_dy (gnn_criterion *crit,
                           const gsl_vector *y,
                           const gsl_vector *t,
                           gsl_vector * dy);

static void
gnn_weight_elimination_destroy (gnn_criterion *crit);



/******************************************/
/* Static Implementation                  */
/******************************************/

/**
 * @brief The evaluation function.
 * @ingroup gnn_weight_elimination_doc
 *
 * This function corresponds to the evaluation function.
 *
 * @param  crit A pointer to a \ref gnn_weight_elimination criterion.
 * @param  y    A pointer to an estimation vector \f$y\f$.
 * @param  t    A pointer to the desired target vector \f$t\f$.
 * @return A real number corresponding to the value of the criterion.
 */
double
gnn_weight_elimination_e (gnn_criterion *crit,
                          const gsl_vector *y,
                          const gsl_vector *t)
{
    size_t i;
    double E;
    double Ep;
    double wsum;
    gnn_weight_elimination *we;

    assert (crit != NULL);
    assert (y != NULL);
    assert (t != NULL);

    /* get view as a gnn_weight_elimination */
    we = (gnn_weight_elimination *) crit;

    /* check sizes */
    if (y->size != t->size)
        GSL_ERROR_VAL ("vector sizes should be the same", GSL_EINVAL, 0.0);

    /* compute subnode error */
    E = gnn_criterion_evaluate_e (we->subcrit, y, t);

    /* get parameter vector */
    gnn_pbundle_get_w (we->pb, we->w);

    /* compute penalization term */
    Ep = 0.0;
    for (i=0; i<we->w->size; ++i)
    {
        double wi;
        double wpwi;

        wi   = gsl_vector_get (we->w, i);
        wpwi = we->wp * we->wp + wi * wi;
        wpwi = GNN_MAX (GNN_TINY, wpwi);
        Ep += wi * wi / wpwi;
    }

    return E + 0.5 * we->nu * Ep;
}

/**
 * @brief The gradient evaluation function.
 * @ingroup gnn_weight_elimination_doc
 *
 * This function implements criterion's gradient evaluation function.
 *
 * @param  crit A pointer to a \ref gnn_weight_elimination criterion.
 * @param  y    A pointer to an estimation vector \f$y\f$.
 * @param  t    A pointer to the desired target vector \f$t\f$.
 * @param  dy   A pointer to a buffer vector where the result should be placed.
 * @return Returns 0 if succeeded.
 */
int
gnn_weight_elimination_dy (gnn_criterion *crit,
                           const gsl_vector *y,
                           const gsl_vector *t,
                           gsl_vector * dy)
{
    int i;
    gnn_weight_elimination *we;

    assert (crit != NULL);
    assert (y    != NULL);
    assert (t    != NULL);
    assert (dy   != NULL);

    /* get view as a gnn_weight_elimination */
    we = (gnn_weight_elimination *) crit;

    /* compute subnode dy */
    gnn_criterion_evaluate_dy (we->subcrit, dy);

    /* get parameter gradient vector */
    gnn_pbundle_get_dw (we->pb, we->dw);

    /* compute gradient penalization terms */
    for (i=0; i<we->w->size; ++i)
    {
        double wi;
        double dwi;
        double wpwi2;

        wi  = gsl_vector_get (we->w, i);
        dwi = gsl_vector_get (we->dw, i);

        wpwi2 = we->wp * we->wp + wi * wi;
        wpwi2 = GNN_MAX (GNN_TINY, wpwi2 * wpwi2);

        dwi += we->nu * 2 * wi * (we->wp * we->wp / wpwi2);

        gsl_vector_set (we->dw, i, dwi);
    }

    /* set parameter gradient vector penalization */
    gnn_pbundle_set_dw (we->pb, we->dw);

    return 0;
}

/**
 * @brief The destroy function.
 * @ingroup gnn_weight_elimination_doc
 *
 * This function implements destroy function.
 *
 * @param  crit A pointer to a \ref gnn_weight_elimination criterion.
 */
static void
gnn_weight_elimination_destroy (gnn_criterion *crit)
{
    gnn_weight_elimination *we;

    assert (crit != NULL);

    /* get view as a gnn_weight_elimination */
    we = (gnn_weight_elimination *) crit;

    /* free allocate memory */
    if (we->subcrit != NULL)
        gnn_criterion_destroy (we->subcrit);
    if (we->pb != NULL)
        gnn_pbundle_destroy (we->pb);
    if (we->w != NULL)
        gsl_vector_free (we->w);
    if (we->dw != NULL)
        gsl_vector_free (we->dw);
}



/******************************************/
/* Public Interface                       */
/******************************************/

/**
 * @brief Creates a Weight Elimination regularization for \ref gnn_weight.
 * @ingroup gnn_weight_elimination_doc
 *
 * This function builds a new \ref gnn_weight_elimination regularizer for
 * all \ref gnn_weight nodes contained in the given node \a node.
 *
 * @param  crit A pointer to a \ref gnn_weight_elimination criterion.
 * @param  nu   The regularization coefficient \f$\nu\f$.
 * @param  wp   The scale factor \f$\hat{w}\f$.
 * @param  node A pointer to a \ref gnn_node.
 * @return Returns a pointer to a \ref gnn_weight_elimination
 *         if succeeded or NULL.
 */
gnn_criterion *
gnn_weight_elimination_new (gnn_criterion *crit,
                            double         nu,
                            double         wp,
                            gnn_node *node)
{
    gnn_pbundle *pb;
    gnn_weight_elimination *we;

    assert (crit != NULL);
    assert (node != NULL);

    /* get parameter bundle consisting of gnn_weight nodes' params */
    pb = gnn_node_sub_search_params (node, "gnn_weight");

    /* create weight elimination penalizer */
    we = (gnn_weight_elimination *)
          gnn_weight_elimination_new_with_pbundle (crit, nu, wp, pb);
    if (we == NULL)
    {
        gnn_pbundle_destroy (pb);
        GSL_ERROR_VAL ("couldn't create gnn_weight_elimination regularizer",
                       GSL_EFAILED, NULL);
    }

    return (gnn_criterion *) we;
}

/**
 * @brief Creates a Weight Elimination regularization for a given type.
 * @ingroup gnn_weight_elimination_doc
 *
 * This function builds a new \ref gnn_weight_elimination regularizer for
 * all parameters that pertain to nodes of type \a type contained in the
 * given node \a node.
 *
 * @param  crit A pointer to a \ref gnn_weight_elimination criterion.
 * @param  nu   The regularization coefficient \f$\nu\f$.
 * @param  wp   The scale parameter \f$\hat{w}\f$.
 * @param  node A pointer to a \ref gnn_node.
 * @param  type A string containing the type.
 * @return Returns a pointer to a \ref gnn_weight_elimination if succeeded or NULL.
 */
gnn_criterion *
gnn_weight_elimination_new_with_type (gnn_criterion *crit,
                                      double         nu,
                                      double         wp,
                                      gnn_node      *node,
                                      const char    *type)
{
    gnn_pbundle *pb;
    gnn_weight_elimination *we;

    assert (crit != NULL);
    assert (node != NULL);
    assert (type != NULL);

    /* get parameter bundle consisting of  */
    /* the nodes' params of the given type */
    pb = gnn_node_sub_search_params (node, type);

    /* create weight decay penalizer */
    we = (gnn_weight_elimination *)
          gnn_weight_elimination_new_with_pbundle (crit, nu, wp, pb);
    if (we == NULL)
    {
        gnn_pbundle_destroy (pb);
        GSL_ERROR_VAL ("couldn't create gnn_weight_elimination regularizer",
                       GSL_EFAILED, NULL);
    }

    return (gnn_criterion *) we;
}

/**
 * @brief Creates a Weight Elimination regularization for a given \em pbundle.
 * @ingroup gnn_weight_elimination_doc
 *
 * This function builds a new \ref gnn_weight_elimination regularizer for
 * all parameters contained in the given parameter bundle \a pb.
 *
 * @param  crit A pointer to a \ref gnn_weight_elimination criterion.
 * @param  nu   The regularization coefficient \f$\nu\f$.
 * @param  wp   The scale parameter \f$\hat{w}\f$.
 * @param  pb   A \ref gnn_pbundle.
 * @return Returns a pointer to a \ref gnn_weight_elimination
 *         if succeeded or NULL.
 */
gnn_criterion *
gnn_weight_elimination_new_with_pbundle (gnn_criterion *crit,
                                         double         nu,
                                         double         wp,
                                         gnn_pbundle   *pb)
{
    int status;
    size_t l;
    size_t size;
    gnn_criterion *c;
    gnn_weight_elimination *we;

    assert (crit != NULL);
    assert (pb != NULL);

    /* check for positive penalty term coefficient */
    if (nu < 0.0)
    {
        GSL_ERROR_VAL ("penalty term coefficient should be positive",
                       GSL_EINVAL, NULL);
    }

    /* check for positive weight scale factor */
    if (wp <= 0.0)
    {
        GSL_ERROR_VAL ("weight scale factor should be strictly positive",
                       GSL_EINVAL, NULL);
    }

    /* alloc memory */
    we = (gnn_weight_elimination *) malloc (sizeof (gnn_weight_elimination));
    if (we == NULL)
    {
        GSL_ERROR_VAL ("couldn't alloc memory for gnn_weight_elimination",
                       GSL_ENOMEM, NULL);
    }

    /* get view as gnn_criterion */
    c = (gnn_criterion *) we;

    /* get size */
    size = gnn_criterion_get_size (crit);

    /* initialize */
    status = gnn_criterion_init  (c,
                                  "gnn_weight_elimination",
                                  size,
                                  gnn_weight_elimination_e,
                                  gnn_weight_elimination_dy,
                                  gnn_weight_elimination_destroy);
    if (status)
    {
        gnn_criterion_destroy (c);
        GSL_ERROR_VAL ("couldn't initialize gnn_weight_elimination",
                       GSL_EFAILED, NULL);
    }

    /* get number of penalized parameters */
    l = gnn_pbundle_get_size (pb);

    /* set fields */
    we->subcrit = crit;
    we->pb      = pb;
    we->w       = gsl_vector_alloc (l);
    we->dw      = gsl_vector_alloc (l);
    we->nu      = nu;
    we->wp      = wp;

    if (we->dw == NULL || we->w == NULL)
    {
        gnn_criterion_destroy (c);
        GSL_ERROR_VAL ("couldn't allocate memory for internal "
                       "gnn_weight_elimination buffer", GSL_EFAILED, NULL);
    }

    return c;
}

/**
 * @brief Sets the regularization coefficient.
 * @ingroup gnn_weight_elimination_doc
 *
 * This function sets a new regularization coefficient for the
 * \ref gnn_weight_elimination regularizer. It should be positive.
 *
 * @param  crit A pointer to a \ref gnn_weight_elimination criterion.
 * @param  nu   The new regularization coefficient \f$nu\f$.
 * @return Returns 0 if succeeded.
 */
int
gnn_weight_elimination_set_nu (gnn_criterion *crit, double nu)
{
    gnn_weight_elimination *we;

    assert (crit != NULL);

    if (nu < 0.0)
    {
        GSL_ERROR ("penalty term coefficient should be positive", GSL_EINVAL);
    }

    we = (gnn_weight_elimination *) crit;
    we->nu = nu;

    return 0;
}

/**
 * @brief Gets the regularization coefficient.
 * @ingroup gnn_weight_elimination_doc
 *
 * This function gets the currently used regularization coefficient of the
 * \ref gnn_weight_elimination regularizer.
 *
 * @param  crit A pointer to a \ref gnn_weight_elimination criterion.
 * @return Returns the regularization coefficient \f$nu\f$.
 */
double
gnn_weight_elimination_get_nu (gnn_criterion *crit)
{
    gnn_weight_elimination *we;

    assert (crit != NULL);

    we = (gnn_weight_elimination *) crit;
    return we->nu;
}

/**
 * @brief Sets the scale parameter \f$\hat{w}\f$.
 * @ingroup gnn_weight_elimination_doc
 *
 * This function sets a new scale paramter \f$\hat{w}\f$ for the
 * \ref gnn_weight_elimination regularizer. It should be stricly positive.
 *
 * @param  crit A pointer to a \ref gnn_weight_elimination criterion.
 * @param  wp   The new scale parameter \f$\hat{w}\f$.
 * @return Returns 0 if succeeded.
 */
int
gnn_weight_elimination_set_wp (gnn_criterion *crit, double wp)
{
    gnn_weight_elimination *we;

    assert (crit != NULL);

    if (wp <= 0.0)
    {
        GSL_ERROR ("weight scale coefficient should be strictly positive",
                   GSL_EINVAL);
    }

    we = (gnn_weight_elimination *) crit;
    we->wp = wp;

    return 0;
}

/**
 * @brief Gets the current scale parameter \f$\hat{w}\f$.
 * @ingroup gnn_weight_elimination_doc
 *
 * This function gets the currently used scale parameter \f$\hat{w}\f$ by the
 * \ref gnn_weight_elimination regularizer.
 *
 * @param  crit A pointer to a \ref gnn_weight_elimination criterion.
 * @return Returns the scale parameter \f$\hat{w}\f$.
 */
double
gnn_weight_elimination_get_wp (gnn_criterion *crit)
{
    gnn_weight_elimination *we;

    assert (crit != NULL);

    we = (gnn_weight_elimination *) crit;
    return we->wp;
}

/**
 * @brief Perform parameter pruning.
 * @ingroup gnn_weight_elimination_doc
 *
 * This function pruns the penalized parameters that fall below the given
 * threshold \a th in magnitude. These are frozen to zero.
 *
 * @param  crit A pointer to a \ref gnn_weight_elimination criterion.
 * @param  th   The threshold for parameter pruning.
 * @return Returns 0 if succeeded.
 */
int
gnn_weight_elimination_prun (gnn_criterion *crit, double th)
{
    size_t i;
    size_t size;
    gnn_weight_elimination *we;

    assert (crit != NULL);

    /* get view as a weight elimination criterion */
    we = (gnn_weight_elimination *) crit;

    /* get number of parameters */
    size = gnn_pbundle_get_size (we->pb);

    /* check every parameter for its value and */
    /* prun if it falls below the threshold.   */
    for (i=0; i<size; ++i)
    {
        double wi;
        
        wi = gnn_pbundle_get_w_at (we->pb, i);
        if (fabs (wi) < th)
        {
            gnn_pbundle_set_w_at (we->pb, i, 0.0);
            gnn_pbundle_set_f_at (we->pb, i, 1);
        }
    }
    
    return 0;
}

---