Skip to content

Commit

Permalink
Proper automatic k neighborhood matrix handling for LLE,HLLE,LTSA
Browse files Browse the repository at this point in the history
  • Loading branch information
@lisitsyn
lisitsyn committed Jan 30, 2012
1 parent 03e8d6b commit 03786e6
Show file tree
Hide file tree
Showing 3 changed files with 47 additions and 70 deletions.
39 changes: 14 additions & 25 deletions src/shogun/converter/HessianLocallyLinearEmbedding.cpp
View file
Expand Up @@ -34,18 +34,12 @@ struct HESSIANESTIMATION_THREAD_PARAM
int32_t idx_stop;
/// number of neighbors
int32_t m_k;
/// current dimensionality
int32_t dim;
///
int32_t N;
/// dp
int32_t dp;
/// target dimensionality
int32_t target_dim;
/// matrix containing indexes of neighbors of ith vector in ith column
const int32_t* neighborhood_matrix;
SGMatrix<int32_t> neighborhood_matrix;
/// feature matrix
const float64_t* feature_matrix;
SGMatrix<float64_t> feature_matrix;
/// local feature matrix contating features of neighbors
float64_t* local_feature_matrix;
/// Yi matrix
Expand Down Expand Up @@ -130,12 +124,9 @@ SGMatrix<float64_t> CHessianLocallyLinearEmbedding::construct_weight_matrix(CSim
parameters[t].idx_step = num_threads;
parameters[t].idx_stop = N;
parameters[t].m_k = m_k;
parameters[t].dim = dim;
parameters[t].target_dim = m_target_dim;
parameters[t].N = N;
parameters[t].dp = dp;
parameters[t].neighborhood_matrix = neighborhood_matrix.matrix;
parameters[t].feature_matrix = feature_matrix.matrix;
parameters[t].neighborhood_matrix = neighborhood_matrix;
parameters[t].feature_matrix = feature_matrix;
parameters[t].local_feature_matrix = local_feature_matrix + (m_k*dim)*t;
parameters[t].Yi_matrix = Yi_matrix + (m_k*(1+m_target_dim+dp))*t;
parameters[t].mean_vector = mean_vector + dim*t;
Expand All @@ -160,11 +151,8 @@ SGMatrix<float64_t> CHessianLocallyLinearEmbedding::construct_weight_matrix(CSim
single_thread_param.idx_stop = N;
single_thread_param.m_k = m_k;
single_thread_param.dim = dim;
single_thread_param.target_dim = m_target_dim;
single_thread_param.N = N;
single_thread_param.dp = dp;
single_thread_param.neighborhood_matrix = neighborhood_matrix.matrix;
single_thread_param.feature_matrix = feature_matrix.matrix;
single_thread_param.neighborhood_matrix = neighborhood_matrix;
single_thread_param.feature_matrix = feature_matrix;
single_thread_param.local_feature_matrix = local_feature_matrix;
single_thread_param.Yi_matrix = Yi_matrix;
single_thread_param.mean_vector = mean_vector;
Expand Down Expand Up @@ -196,12 +184,9 @@ void* CHessianLocallyLinearEmbedding::run_hessianestimation_thread(void* p)
int32_t idx_step = parameters->idx_step;
int32_t idx_stop = parameters->idx_stop;
int32_t m_k = parameters->m_k;
int32_t dim = parameters->dim;
int32_t N = parameters->N;
int32_t dp = parameters->dp;
int32_t target_dim = parameters->target_dim;
const int32_t* neighborhood_matrix = parameters->neighborhood_matrix;
const float64_t* feature_matrix = parameters->feature_matrix;
SGMatrix<int32_t> neighborhood_matrix = parameters->neighborhood_matrix;
SGMatrix<float64_t> feature_matrix = parameters->feature_matrix;
float64_t* local_feature_matrix = parameters->local_feature_matrix;
float64_t* Yi_matrix = parameters->Yi_matrix;
float64_t* mean_vector = parameters->mean_vector;
Expand All @@ -216,6 +201,10 @@ void* CHessianLocallyLinearEmbedding::run_hessianestimation_thread(void* p)
#endif

int i,j,k,l;
int32_t dp = target_dim*(target_dim+1)/2;
int32_t actual_k = neighborhood_matrix.num_rows;
int32_t N = feature_matrix.num_cols;
int32_t dim = feature_matrix.num_rows;

for (i=idx_start; i<idx_stop; i+=idx_step)
{
Expand All @@ -230,7 +219,7 @@ void* CHessianLocallyLinearEmbedding::run_hessianestimation_thread(void* p)
for (j=0; j<m_k; j++)
{
for (k=0; k<dim; k++)
local_feature_matrix[j*dim+k] = feature_matrix[neighborhood_matrix[i*m_k+j]*dim+k];
local_feature_matrix[j*dim+k] = feature_matrix[neighborhood_matrix[i*actual_k+j]*dim+k];

cblas_daxpy(dim,1.0,local_feature_matrix+j*dim,1,mean_vector,1);
}
Expand Down Expand Up @@ -303,7 +292,7 @@ void* CHessianLocallyLinearEmbedding::run_hessianestimation_thread(void* p)
for (j=0; j<m_k; j++)
{
for (k=0; k<m_k; k++)
W_matrix[N*neighborhood_matrix[i*m_k+k]+neighborhood_matrix[i*m_k+j]] += q_matrix[j*m_k+k];
W_matrix[N*neighborhood_matrix[i*actual_k+k]+neighborhood_matrix[i*actual_k+j]] += q_matrix[j*m_k+k];
}
#ifdef HAVE_PTHREAD
PTHREAD_UNLOCK(W_matrix_lock);
Expand Down
36 changes: 15 additions & 21 deletions src/shogun/converter/LocalTangentSpaceAlignment.cpp
View file
Expand Up @@ -37,20 +37,16 @@ struct LTSA_THREAD_PARAM
int32_t m_k;
/// target dimension
int32_t target_dim;
/// current dimension
int32_t dim;
/// number of objects
int32_t N;
/// matrix containing indexes of ith vector's neighbors in ith column
const int32_t* neighborhood_matrix;
SGMatrix<int32_t> neighborhood_matrix;
/// G matrix
float64_t* G_matrix;
/// mean vector
float64_t* mean_vector;
/// local feature matrix containing neighbors of vector
float64_t* local_feature_matrix;
/// feature matrix of given features instance
const float64_t* feature_matrix;
SGMatrix<float64_t> feature_matrix;
/// used to store singular values
float64_t* s_values_vector;
/// q matrix
Expand Down Expand Up @@ -118,13 +114,11 @@ SGMatrix<float64_t> CLocalTangentSpaceAlignment::construct_weight_matrix(CSimple
parameters[t].idx_stop = N;
parameters[t].m_k = m_k;
parameters[t].target_dim = m_target_dim;
parameters[t].dim = dim;
parameters[t].N = N;
parameters[t].neighborhood_matrix = neighborhood_matrix.matrix;
parameters[t].neighborhood_matrix = neighborhood_matrix;
parameters[t].G_matrix = G_matrix + (m_k*(1+m_target_dim))*t;
parameters[t].mean_vector = mean_vector + dim*t;
parameters[t].local_feature_matrix = local_feature_matrix + (m_k*dim)*t;
parameters[t].feature_matrix = feature_matrix.matrix;
parameters[t].feature_matrix = feature_matrix;
parameters[t].s_values_vector = s_values_vector + dim*t;
parameters[t].q_matrix = q_matrix + (m_k*m_k)*t;
parameters[t].W_matrix = W_matrix;
Expand All @@ -143,13 +137,11 @@ SGMatrix<float64_t> CLocalTangentSpaceAlignment::construct_weight_matrix(CSimple
single_thread_param.idx_stop = N;
single_thread_param.m_k = m_k;
single_thread_param.target_dim = m_target_dim;
single_thread_param.dim = dim;
single_thread_param.N = N;
single_thread_param.neighborhood_matrix = neighborhood_matrix.matrix;
single_thread_param.neighborhood_matrix = neighborhood_matrix;
single_thread_param.G_matrix = G_matrix;
single_thread_param.mean_vector = mean_vector;
single_thread_param.local_feature_matrix = local_feature_matrix;
single_thread_param.feature_matrix = feature_matrix.matrix;
single_thread_param.feature_matrix = feature_matrix;
single_thread_param.s_values_vector = s_values_vector;
single_thread_param.q_matrix = q_matrix;
single_thread_param.W_matrix = W_matrix;
Expand All @@ -163,10 +155,11 @@ SGMatrix<float64_t> CLocalTangentSpaceAlignment::construct_weight_matrix(CSimple
SG_FREE(local_feature_matrix);
SG_FREE(q_matrix);

int32_t actual_k = neighborhood_matrix.num_rows;
for (int32_t i=0; i<N; i++)
{
for (int32_t j=0; j<m_k; j++)
W_matrix[N*neighborhood_matrix[i*m_k+j]+neighborhood_matrix[i*m_k+j]] += 1.0;
W_matrix[N*neighborhood_matrix[i*actual_k+j]+neighborhood_matrix[i*actual_k+j]] += 1.0;
}

return SGMatrix<float64_t>(W_matrix,N,N);
Expand All @@ -180,13 +173,11 @@ void* CLocalTangentSpaceAlignment::run_ltsa_thread(void* p)
int32_t idx_stop = parameters->idx_stop;
int32_t m_k = parameters->m_k;
int32_t target_dim = parameters->target_dim;
int32_t dim = parameters->dim;
int32_t N = parameters->N;
const int32_t* neighborhood_matrix = parameters->neighborhood_matrix;
SGMatrix<int32_t> neighborhood_matrix = parameters->neighborhood_matrix;
float64_t* G_matrix = parameters->G_matrix;
float64_t* mean_vector = parameters->mean_vector;
float64_t* local_feature_matrix = parameters->local_feature_matrix;
const float64_t* feature_matrix = parameters->feature_matrix;
SGMatrix<float64_t> feature_matrix = parameters->feature_matrix;
float64_t* s_values_vector = parameters->s_values_vector;
float64_t* q_matrix = parameters->q_matrix;
float64_t* W_matrix = parameters->W_matrix;
Expand All @@ -195,6 +186,9 @@ void* CLocalTangentSpaceAlignment::run_ltsa_thread(void* p)
#endif

int32_t i,j,k;
int32_t N = feature_matrix.num_cols;
int32_t dim = feature_matrix.num_rows;
int32_t actual_k = neighborhood_matrix.num_rows;

for (j=0; j<m_k; j++)
G_matrix[j] = 1.0/CMath::sqrt((float64_t)m_k);
Expand All @@ -208,7 +202,7 @@ void* CLocalTangentSpaceAlignment::run_ltsa_thread(void* p)
for (j=0; j<m_k; j++)
{
for (k=0; k<dim; k++)
local_feature_matrix[j*dim+k] = feature_matrix[neighborhood_matrix[i*m_k+j]*dim+k];
local_feature_matrix[j*dim+k] = feature_matrix[neighborhood_matrix[i*actual_k+j]*dim+k];

cblas_daxpy(dim,1.0,local_feature_matrix+j*dim,1,mean_vector,1);
}
Expand Down Expand Up @@ -246,7 +240,7 @@ void* CLocalTangentSpaceAlignment::run_ltsa_thread(void* p)
for (j=0; j<m_k; j++)
{
for (k=0; k<m_k; k++)
W_matrix[N*neighborhood_matrix[i*m_k+k]+neighborhood_matrix[i*m_k+j]] -= q_matrix[j*m_k+k];
W_matrix[N*neighborhood_matrix[i*actual_k+k]+neighborhood_matrix[i*actual_k+j]] -= q_matrix[j*m_k+k];
}
#ifdef HAVE_PTHREAD
PTHREAD_UNLOCK(W_matrix_lock);
Expand Down
42 changes: 18 additions & 24 deletions src/shogun/converter/LocallyLinearEmbedding.cpp
View file
Expand Up @@ -40,14 +40,10 @@ struct LINRECONSTRUCTION_THREAD_PARAM
int32_t idx_step;
/// number of neighbors
int32_t m_k;
/// current dimension
int32_t dim;
/// number of vectors
int32_t N;
/// matrix containing indexes of neighbors of ith object in ith column
const int32_t* neighborhood_matrix;
SGMatrix<int32_t> neighborhood_matrix;
/// old feature matrix
const float64_t* feature_matrix;
SGMatrix<float64_t> feature_matrix;
/// Z matrix containing features of neighbors
float64_t* z_matrix;
/// covariance matrix, ZZ'
Expand Down Expand Up @@ -369,11 +365,9 @@ SGMatrix<float64_t> CLocallyLinearEmbedding::construct_weight_matrix(CSimpleFeat
parameters[t].idx_step = num_threads;
parameters[t].idx_stop = N;
parameters[t].m_k = m_k;
parameters[t].dim = dim;
parameters[t].N = N;
parameters[t].neighborhood_matrix = neighborhood_matrix.matrix;
parameters[t].neighborhood_matrix = neighborhood_matrix;
parameters[t].z_matrix = z_matrix+(m_k*dim)*t;
parameters[t].feature_matrix = feature_matrix.matrix;
parameters[t].feature_matrix = feature_matrix;
parameters[t].covariance_matrix = covariance_matrix+(m_k*m_k)*t;
parameters[t].id_vector = id_vector+m_k*t;
parameters[t].W_matrix = W_matrix;
Expand All @@ -391,11 +385,9 @@ SGMatrix<float64_t> CLocallyLinearEmbedding::construct_weight_matrix(CSimpleFeat
single_thread_param.idx_step = 1;
single_thread_param.idx_stop = N;
single_thread_param.m_k = m_k;
single_thread_param.dim = dim;
single_thread_param.N = N;
single_thread_param.neighborhood_matrix = neighborhood_matrix.matrix;
single_thread_param.neighborhood_matrix = neighborhood_matrix;
single_thread_param.z_matrix = z_matrix;
single_thread_param.feature_matrix = feature_matrix.matrix;
single_thread_param.feature_matrix = feature_matrix;
single_thread_param.covariance_matrix = covariance_matrix;
single_thread_param.id_vector = id_vector;
single_thread_param.W_matrix = W_matrix;
Expand Down Expand Up @@ -472,17 +464,18 @@ void* CLocallyLinearEmbedding::run_linearreconstruction_thread(void* p)
int32_t idx_step = parameters->idx_step;
int32_t idx_stop = parameters->idx_stop;
int32_t m_k = parameters->m_k;
int32_t dim = parameters->dim;
int32_t N = parameters->N;
const int32_t* neighborhood_matrix = parameters->neighborhood_matrix;
SGMatrix<int32_t> neighborhood_matrix = parameters->neighborhood_matrix;
float64_t* z_matrix = parameters->z_matrix;
const float64_t* feature_matrix = parameters->feature_matrix;
SGMatrix<float64_t> feature_matrix = parameters->feature_matrix;
float64_t* covariance_matrix = parameters->covariance_matrix;
float64_t* id_vector = parameters->id_vector;
float64_t* W_matrix = parameters->W_matrix;
float64_t m_reconstruction_shift = parameters->m_reconstruction_shift;

int32_t i,j,k;
int32_t dim = feature_matrix.num_rows;
int32_t N = feature_matrix.num_cols;
int32_t actual_k = neighborhood_matrix.num_rows;
float64_t norming,trace;

for (i=idx_start; i<idx_stop; i+=idx_step)
Expand All @@ -491,8 +484,8 @@ void* CLocallyLinearEmbedding::run_linearreconstruction_thread(void* p)
// center features by subtracting i-th feature column
for (j=0; j<m_k; j++)
{
cblas_dcopy(dim,feature_matrix+neighborhood_matrix[i*m_k+j]*dim,1,z_matrix+j*dim,1);
cblas_daxpy(dim,-1.0,feature_matrix+i*dim,1,z_matrix+j*dim,1);
cblas_dcopy(dim,feature_matrix.matrix+neighborhood_matrix[i*actual_k+j]*dim,1,z_matrix+j*dim,1);
cblas_daxpy(dim,-1.0,feature_matrix.matrix+i*dim,1,z_matrix+j*dim,1);
}

// compute local covariance matrix
Expand Down Expand Up @@ -535,13 +528,14 @@ void* CLocallyLinearEmbedding::run_linearreconstruction_thread(void* p)
W_matrix[N*i+i] += 1.0;
for (j=0; j<m_k; j++)
{
W_matrix[N*i+neighborhood_matrix[i*m_k+j]] -= id_vector[j];
W_matrix[N*neighborhood_matrix[i*m_k+j]+i] -= id_vector[j];
W_matrix[N*i+neighborhood_matrix[i*actual_k+j]] -= id_vector[j];
W_matrix[N*neighborhood_matrix[i*actual_k+j]+i] -= id_vector[j];
}
for (j=0; j<m_k; j++)
{
for (k=0; k<m_k; k++)
W_matrix[N*neighborhood_matrix[i*m_k+j]+neighborhood_matrix[i*m_k+k]]+=covariance_matrix[j*m_k+k];
W_matrix[N*neighborhood_matrix[i*actual_k+j]+neighborhood_matrix[i*actual_k+k]]+=
covariance_matrix[j*m_k+k];
}
}
return NULL;
Expand All @@ -565,7 +559,7 @@ SGMatrix<int32_t> CLocallyLinearEmbedding::get_neighborhood_matrix(SGMatrix<floa
{
std::vector<LLE_COVERTREE_POINT> neighbors =
coverTree->kNearestNeighbors(LLE_COVERTREE_POINT(i,distance_matrix),k+1);
for (std::size_t m=1; m<neighbors.size(); m++)
for (std::size_t m=1; m<unsigned(k+1); m++)
neighborhood_matrix[i*k+m-1] = neighbors[m].point_index;
}

Expand Down

0 comments on commit 03786e6

Please sign in to comment.