SHOGUN  v1.1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
List of all members | Public Member Functions | Protected Member Functions | Static Protected Member Functions | Protected Attributes
CLocallyLinearEmbedding Class Reference

Detailed Description

the class LocallyLinearEmbedding used to preprocess data using Locally Linear Embedding algorithm described in

Saul, L. K., Ave, P., Park, F., & Roweis, S. T. (2001). An Introduction to Locally Linear Embedding. Available from, 290(5500), 2323-2326. Retrieved from: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.123.7319&rep=rep1&type=pdf

The process of finding nearest neighbors is parallel and involves Fibonacci Heap and Euclidian distance.

Linear reconstruction step runs in parallel for objects and involves LAPACK routine DPOSV for solving a system of linear equations.

The eigenproblem stated in the algorithm is solved with LAPACK routine DSYEVR or with ARPACK DSAUPD/DSEUPD routines if available.

Due to computation speed, ARPACK is being used with small regularization of weight matrix and Cholesky factorization is used internally for Lanzcos iterations (in case of only LAPACK is available) and SUPERLU library for fast solving sparse equations stated by ARPACK is being used if available.

This class also have capability of selecting k automatically in range between "k" and "max_k" in case if "auto_k" is true. This is being done using ternary search of minima of the mean reconstruction error. The reconstruction error is considered to have only one global minimum in this mode.

It is optimized with alignment formulation as described in

Zhao, D. (2006). Formulating LLE using alignment technique. Pattern Recognition, 39(11), 2233-2235. Retrieved from http://linkinghub.elsevier.com/retrieve/pii/S0031320306002160

Definition at line 63 of file LocallyLinearEmbedding.h.

Inheritance diagram for CLocallyLinearEmbedding:
Inheritance graph
[legend]

Public Member Functions

 CLocallyLinearEmbedding ()
virtual ~CLocallyLinearEmbedding ()
virtual CFeaturesapply (CFeatures *features)
void set_k (int32_t k)
int32_t get_k () const
void set_max_k (int32_t max_k)
int32_t get_max_k () const
void set_auto_k (bool auto_k)
bool get_auto_k () const
void set_reconstruction_shift (float64_t reconstruction_shift)
float64_t get_reconstruction_shift () const
void set_nullspace_shift (float64_t nullspace_shift)
float64_t get_nullspace_shift () const
void set_use_arpack (bool use_arpack)
bool get_use_arpack () const
virtual const char * get_name () const
- Public Member Functions inherited from CEmbeddingConverter
 CEmbeddingConverter ()
virtual ~CEmbeddingConverter ()
virtual CSimpleFeatures
< float64_t > * 
embed (CFeatures *features)
void set_target_dim (int32_t dim)
int32_t get_target_dim () const
void set_distance (CDistance *distance)
CDistanceget_distance () const
void set_kernel (CKernel *kernel)
CKernelget_kernel () const
- Public Member Functions inherited from CConverter
 CConverter ()
virtual ~CConverter ()
- Public Member Functions inherited from CSGObject
 CSGObject ()
 CSGObject (const CSGObject &orig)
virtual ~CSGObject ()
virtual bool is_generic (EPrimitiveType *generic) const
template<class T >
void set_generic ()
void unset_generic ()
virtual void print_serializable (const char *prefix="")
virtual bool save_serializable (CSerializableFile *file, const char *prefix="")
virtual bool load_serializable (CSerializableFile *file, const char *prefix="")
void set_global_io (SGIO *io)
SGIOget_global_io ()
void set_global_parallel (Parallel *parallel)
Parallelget_global_parallel ()
void set_global_version (Version *version)
Versionget_global_version ()
SGVector< char * > get_modelsel_names ()
char * get_modsel_param_descr (const char *param_name)
index_t get_modsel_param_index (const char *param_name)

Protected Member Functions

void init ()
 HELPERS.
virtual SGMatrix< float64_tconstruct_weight_matrix (CSimpleFeatures< float64_t > *simple_features, float64_t *W_matrix, SGMatrix< int32_t > neighborhood_matrix)
virtual SGMatrix< float64_tconstruct_embedding (SGMatrix< float64_t > matrix, int dimension)
virtual SGMatrix< int32_t > get_neighborhood_matrix (SGMatrix< float64_t > distance_matrix, int32_t k)
int32_t estimate_k (CSimpleFeatures< float64_t > *simple_features, SGMatrix< int32_t > neighborhood_matrix)
float64_t compute_reconstruction_error (int32_t k, int dim, int N, float64_t *feature_matrix, float64_t *z_matrix, float64_t *covariance_matrix, float64_t *resid_vector, float64_t *id_vector, SGMatrix< int32_t > neighborhood_matrix)

Static Protected Member Functions

static void * run_neighborhood_thread (void *p)
 THREADS.
static void * run_linearreconstruction_thread (void *p)

Protected Attributes

int32_t m_k
 FIELDS.
int32_t m_max_k
float64_t m_reconstruction_shift
float64_t m_nullspace_shift
bool m_use_arpack
bool m_auto_k
- Protected Attributes inherited from CEmbeddingConverter
int32_t m_target_dim
CDistancem_distance
CKernelm_kernel

Additional Inherited Members

- Public Attributes inherited from CSGObject
SGIOio
Parallelparallel
Versionversion
Parameterm_parameters
Parameterm_model_selection_parameters

Constructor & Destructor Documentation

constructor

Definition at line 83 of file LocallyLinearEmbedding.cpp.

destructor

Definition at line 115 of file LocallyLinearEmbedding.cpp.

Member Function Documentation

CFeatures * apply ( CFeatures features)
virtual

apply preprocessor to features

Parameters
features

Implements CEmbeddingConverter.

Reimplemented in CKernelLocallyLinearEmbedding.

Definition at line 186 of file LocallyLinearEmbedding.cpp.

float64_t compute_reconstruction_error ( int32_t  k,
int  dim,
int  N,
float64_t feature_matrix,
float64_t z_matrix,
float64_t covariance_matrix,
float64_t resid_vector,
float64_t id_vector,
SGMatrix< int32_t >  neighborhood_matrix 
)
protected

computes reconstruction error using subset of given features

Parameters
k
dim
N
feature_matrix
z_matrix
covariance_matrix
resid_vector
id_vector
neighborhood_matrix
Returns
residual sum

Definition at line 278 of file LocallyLinearEmbedding.cpp.

SGMatrix< float64_t > construct_embedding ( SGMatrix< float64_t matrix,
int  dimension 
)
protectedvirtual

constructs embedding

Parameters
matrixcomputed weight matrix
dimensiondimension of embedding
Returns
embedding features

Definition at line 397 of file LocallyLinearEmbedding.cpp.

SGMatrix< float64_t > construct_weight_matrix ( CSimpleFeatures< float64_t > *  simple_features,
float64_t W_matrix,
SGMatrix< int32_t >  neighborhood_matrix 
)
protectedvirtual

constructs weight matrix

Parameters
simple_featuresfeatures to be used
W_matrixweight matrix
neighborhood_matrixmatrix containing neighbor idxs

Reimplemented in CLocalTangentSpaceAlignment, and CHessianLocallyLinearEmbedding.

Definition at line 322 of file LocallyLinearEmbedding.cpp.

int32_t estimate_k ( CSimpleFeatures< float64_t > *  simple_features,
SGMatrix< int32_t >  neighborhood_matrix 
)
protected

estimates k using ternary search

Parameters
simple_featuressimple features to use
neighborhood_matrixmatrix containing indexes of neighbors for every vector
Returns
optimal k (in means of reconstruction error)

Definition at line 241 of file LocallyLinearEmbedding.cpp.

bool get_auto_k ( ) const

getter for auto_k parameter

Returns
m_auto_k value

Definition at line 146 of file LocallyLinearEmbedding.cpp.

int32_t get_k ( ) const

getter for k parameter

Returns
m_k value

Definition at line 125 of file LocallyLinearEmbedding.cpp.

int32_t get_max_k ( ) const

getter for max_k parameter

Returns
m_max_k value

Definition at line 136 of file LocallyLinearEmbedding.cpp.

const char * get_name ( ) const
virtual
SGMatrix< int32_t > get_neighborhood_matrix ( SGMatrix< float64_t distance_matrix,
int32_t  k 
)
protectedvirtual

constructs neighborhood matrix by distance

Parameters
distance_matrixdistance matrix to be used
knumber of neighbors
Returns
matrix containing indexes of neighbors of i-th vector in i-th column

Reimplemented in CKernelLocallyLinearEmbedding.

Definition at line 532 of file LocallyLinearEmbedding.cpp.

float64_t get_nullspace_shift ( ) const

getter for nullspace shift parameter

Returns
m_nullspace_shift value

Definition at line 156 of file LocallyLinearEmbedding.cpp.

float64_t get_reconstruction_shift ( ) const

getter for reconstruction shift parameter

Returns
m_reconstruction_shift value

Definition at line 166 of file LocallyLinearEmbedding.cpp.

bool get_use_arpack ( ) const

getter for use arpack parameter

Returns
use_arpack value

Definition at line 176 of file LocallyLinearEmbedding.cpp.

void init ( )
protected

HELPERS.

default init

Reimplemented from CEmbeddingConverter.

Definition at line 99 of file LocallyLinearEmbedding.cpp.

void * run_linearreconstruction_thread ( void *  p)
staticprotected

runs linear reconstruction thread

Parameters
pthread params

Reimplemented in CKernelLocallyLinearEmbedding.

Definition at line 450 of file LocallyLinearEmbedding.cpp.

void * run_neighborhood_thread ( void *  p)
staticprotected

THREADS.

runs neighborhood determination thread

Parameters
pthread params

Reimplemented in CKernelLocallyLinearEmbedding.

Definition at line 591 of file LocallyLinearEmbedding.cpp.

void set_auto_k ( bool  auto_k)

setter for auto_k parameter

Parameters
auto_kauto_k value

Definition at line 141 of file LocallyLinearEmbedding.cpp.

void set_k ( int32_t  k)

setter for k parameter

Parameters
kk value

Definition at line 119 of file LocallyLinearEmbedding.cpp.

void set_max_k ( int32_t  max_k)

setter for max_k parameter

Parameters
max_kmax_k value

Definition at line 130 of file LocallyLinearEmbedding.cpp.

void set_nullspace_shift ( float64_t  nullspace_shift)

setter for nullspace shift parameter

Parameters
nullspace_shiftnullsapce shift value

Definition at line 151 of file LocallyLinearEmbedding.cpp.

void set_reconstruction_shift ( float64_t  reconstruction_shift)

setter for reconstruction shift parameter

Parameters
reconstruction_shiftreconstruction shift value

Definition at line 161 of file LocallyLinearEmbedding.cpp.

void set_use_arpack ( bool  use_arpack)

setter for use arpack parameter

Parameters
use_arpackuse arpack value

Definition at line 171 of file LocallyLinearEmbedding.cpp.

Member Data Documentation

bool m_auto_k
protected

whether use automatic k or not

Definition at line 212 of file LocallyLinearEmbedding.h.

int32_t m_k
protected

FIELDS.

number of neighbors

Definition at line 197 of file LocallyLinearEmbedding.h.

int32_t m_max_k
protected

maximum number of neighbors

Definition at line 200 of file LocallyLinearEmbedding.h.

float64_t m_nullspace_shift
protected

regularization shift of nullspace finding step

Definition at line 206 of file LocallyLinearEmbedding.h.

float64_t m_reconstruction_shift
protected

regularization shift of reconstruction step

Definition at line 203 of file LocallyLinearEmbedding.h.

bool m_use_arpack
protected

whether use arpack or not

Definition at line 209 of file LocallyLinearEmbedding.h.


The documentation for this class was generated from the following files:

SHOGUN Machine Learning Toolbox - Documentation