---

gnn_bfgs : Broyden-Fletcher-Goldfarb-Shanno Algorithm.
[gnn_trainer : Trainers for Models.]

---

Detailed Description

This trainer implements the Broyden-Fletcher-Goldfarb-Shanno (BFGS) optimization algorithm. It is a so-called Quasi-Newton algorithm. The parameters are updated using the formula:

where is an approximation to the inverse Hessian matrix, which is built step by step using the formula:

• 

where the following vectors have been defined:

and is the -th gradient . The step size is found using a line-minimization, which can be one of those available in gnn_line_search.

Although theoretically well founded and very robust, the BFGS algorithm is very expensive, both in time and space. The approximation of the Hessian matrix is kept in memory, which is of size where are the number of parameters, leading to a prohibitive amount of storage requirement for greater Gradient Machines.

Defines
#define	GNN_BFGS_TOL   0.0001
	Default precision for line search procedures.
#define	GNN_BFGS_STEP   0.1
	Default bracketing step taken by the line search procedures.
#define	GNN_BFGS_RESTART   100
	Default restart.
#define	GNN_BFGS_ALPHA   gnn_line_search_brent
	Default line search procedure.
Typedefs
typedef double(*	gnn_bfgs_beta )(gnn_trainer *trainer)
	Type for evaluation procedures.
typedef _gnn_bfgs	gnn_bfgs
	Conjugate gradients trainer structure.
Functions
int	gnn_bfgs_reset (gnn_trainer *trainer)
	The trainer's "reset" implementation.
int	gnn_bfgs_iteration (gnn_bfgs *bf)
	Computes the step-wise approximation of the Hessian matrix.
void	gnn_bfgs_destroy (gnn_trainer *trainer)
	The trainers "destroy" implementation.
gnn_trainer *	gnn_bfgs_new (gnn_node *node, gnn_criterion *crit, gnn_dataset *data)
	Creates a new BFGS trainer.
int	gnn_bfgs_set_tol (gnn_trainer *trainer, double tol)
	Sets the precision tolerance for the line search procedure.
double	gnn_bfgs_get_tol (gnn_trainer *trainer)
	Gets the tolerance for the line search procedure.
int	gnn_bfgs_set_step (gnn_trainer *trainer, double step)
	Sets the initial step for the interval bracketing procedure.
double	gnn_bfgs_get_step (gnn_trainer *trainer)
	Gets the initial step for the interval bracketing procedure.
int	gnn_bfgs_set_restart (gnn_trainer *trainer, size_t restart)
	Sets the number of iterations before restarting.
size_t	gnn_bfgs_get_restart (gnn_trainer *trainer)
	Gets the number of iterations before reinitializing the direction.
int	gnn_bfgs_set_line_search (gnn_trainer *trainer, gnn_line_search_type lsearch)
	Sets the line search procedure.
gnn_line_search_type	gnn_bfgs_get_alpha (gnn_trainer *trainer)
	Gets the installed line search procedure.

---

Define Documentation

#define GNN_BFGS_ALPHA   gnn_line_search_brent

This is the default line search procedure used by the conjugate gradients algorithm. Definition at line 77 of file gnn_bfgs.h.

#define GNN_BFGS_RESTART   100

This constant defines the default number of iterations that the conjugate gradients algorithm takes before restarting the algorithm. Definition at line 68 of file gnn_bfgs.h.

#define GNN_BFGS_STEP   0.1

This constant defines the initial step taken by the bracketing algorithm to search the minimum along the line. Definition at line 59 of file gnn_bfgs.h.

#define GNN_BFGS_TOL   0.0001

This constant defines the tolerance for the line search procedure used by the conjugate gradients algorithm. Definition at line 50 of file gnn_bfgs.h.

---

Typedef Documentation

typedef struct _gnn_bfgs gnn_bfgs

This type extends the basic gnn_trainer : Trainers for Models. structure for the conjugate gradients trainer. Definition at line 95 of file gnn_bfgs.h.

typedef double(* gnn_bfgs_beta)(gnn_trainer *trainer)

This type defines the form of the procedures for computing the coefficient used by the conjugate gradients method. Definition at line 86 of file gnn_bfgs.h.

---

Function Documentation

void gnn_bfgs_destroy (  gnn_trainer *    trainer )  [static]

Parameters: trainer  A pointer to a gnn_bfgs : Broyden-Fletcher-Goldfarb-Shanno Algorithm.. Definition at line 261 of file gnn_bfgs.c.

gnn_line_search_type gnn_bfgs_get_alpha (  gnn_trainer *    trainer )

Parameters: trainer  A pointer to a gnn_bfgs : Broyden-Fletcher-Goldfarb-Shanno Algorithm.. Returns: Returns a pointer to the installed line-search procedure. Definition at line 587 of file gnn_bfgs.c.

size_t gnn_bfgs_get_restart (  gnn_trainer *    trainer )

This function returns the number of iterations executed by the BFGS trainer before reinitializing the search direction. Parameters: trainer  A pointer to a gnn_bfgs : Broyden-Fletcher-Goldfarb-Shanno Algorithm.. Returns: Returns the number of iterations. Definition at line 532 of file gnn_bfgs.c.

double gnn_bfgs_get_step (  gnn_trainer *    trainer )

Parameters: trainer  A pointer to a gnn_bfgs : Broyden-Fletcher-Goldfarb-Shanno Algorithm.. Returns: The trainer's internal step. Definition at line 481 of file gnn_bfgs.c.

double gnn_bfgs_get_tol (  gnn_trainer *    trainer )

Parameters: trainer  A pointer to a gnn_bfgs : Broyden-Fletcher-Goldfarb-Shanno Algorithm.. Returns: Returns the tolerance's value. Definition at line 433 of file gnn_bfgs.c.

int gnn_bfgs_iteration (  gnn_bfgs *    bf )  [static]

Parameters: trainer  A pointer to a gnn_bfgs : Broyden-Fletcher-Goldfarb-Shanno Algorithm.. Returns: Returns 0 if suceeded. Definition at line 140 of file gnn_bfgs.c.

gnn_trainer* gnn_bfgs_new (  gnn_node *    node, gnn_criterion *    crit, gnn_dataset *    data )

This function creates a new BFGS trainer (gnn_bfgs : Broyden-Fletcher-Goldfarb-Shanno Algorithm.). Parameters: node  A pointer to a gnn_node. crit  A pointer to a gnn_criterion : Basic Criterion Function.. data  A pointer to a gnn_dataset : Datasets for Training.. Returns: Returns a pointer to a new gnn_bfgs : Broyden-Fletcher-Goldfarb-Shanno Algorithm. trainer. Definition at line 311 of file gnn_bfgs.c.

int gnn_bfgs_reset (  gnn_trainer *    trainer )  [static]

Parameters: trainer  A pointer to a gnn_bfgs : Broyden-Fletcher-Goldfarb-Shanno Algorithm.. Returns: Returns 0 if suceeded. Definition at line 105 of file gnn_bfgs.c.

int gnn_bfgs_set_line_search (  gnn_trainer *    trainer, gnn_line_search_type    lsearch )

This function sets a new line search procedure used by the BFGS trainer. gnn_trainer *trainer; trainer = gnn_bfgs_new (node, crit, data); // use the Golden-Section line search gnn_bfgs_set_line_search (trainer, gnn_line_search_golden); Please refer to (Line Search Procedures for Nodes.) for the available line search procedures. Parameters: trainer  A pointer to a gnn_bfgs : Broyden-Fletcher-Goldfarb-Shanno Algorithm.. lsearch  A pointer to a line search procedure. Returns: Returns 0 if succeeded. Definition at line 565 of file gnn_bfgs.c.

int gnn_bfgs_set_restart (  gnn_trainer *    trainer, size_t    restart )

Parameters: trainer  A pointer to a gnn_bfgs : Broyden-Fletcher-Goldfarb-Shanno Algorithm.. restart  A stricly positive integer. Returns: Returns 0 if succeeded. Definition at line 501 of file gnn_bfgs.c.

int gnn_bfgs_set_step (  gnn_trainer *    trainer, double    step )

Parameters: trainer  A pointer to a gnn_bfgs : Broyden-Fletcher-Goldfarb-Shanno Algorithm.. step  A stricly positive real value. Returns: Returns 0 if succeeded. Definition at line 453 of file gnn_bfgs.c.

int gnn_bfgs_set_tol (  gnn_trainer *    trainer, double    tol )

Parameters: trainer  A pointer to a gnn_bfgs : Broyden-Fletcher-Goldfarb-Shanno Algorithm.. tol  A stricly positive real value. Returns: Returns 0 if succeeded. Definition at line 405 of file gnn_bfgs.c.

---