DependenceMaximization.cpp

/*
 * Copyright (c) The Shogun Machine Learning Toolbox
 * Written (w) 2014 Soumyajit De
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice, this
 *    list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * The views and conclusions contained in the software and documentation are those
 * of the authors and should not be interpreted as representing official policies,
 * either expressed or implied, of the Shogun Development Team.
 */

#include <shogun/lib/SGMatrix.h>
#include <shogun/labels/Labels.h>
#include <shogun/features/DenseFeatures.h>
#include <shogun/statistical_testing/IndependenceTest.h>
#include <shogun/preprocessor/DependenceMaximization.h>
#include <shogun/mathematics/Math.h>

using namespace shogun;

CDependenceMaximization::CDependenceMaximization()
	: CFeatureSelection<float64_t>()
{
	init();
}

void CDependenceMaximization::init()
{
	SG_ADD((CSGObject**)&m_estimator, "estimator",
			"the estimator for computing measures", MS_NOT_AVAILABLE);
	SG_ADD((CSGObject**)&m_labels_feats, "labels_feats",
			"the features based on labels", MS_NOT_AVAILABLE);

	m_estimator=NULL;
	m_labels_feats=NULL;
}

CDependenceMaximization::~CDependenceMaximization()
{
	SG_UNREF(m_estimator);
	SG_UNREF(m_labels_feats);
}

CFeatures* CDependenceMaximization::create_transformed_copy(CFeatures* features,
		index_t idx)
{
	SG_DEBUG("Entering!\n");

	// remove the dimension specified by the index, i.e. get X\X_i
	// NULL check is handled in CFeatureSelection::get_num_features call
	index_t num_features=get_num_features(features);
	REQUIRE(num_features>idx, "Specified dimension to remove (%d) is greater "
			"than the total number of current features (%d)!\n",
			idx, num_features);

	SGVector<index_t> dims(num_features-1);
	index_t n_dims=0;
	for (index_t i=0; i<num_features; ++i)
	{
		if (i!=idx)
			dims[n_dims++]=i;
	}

	if (io->get_loglevel()==MSG_DEBUG || io->get_loglevel()==MSG_GCDEBUG)
		dims.display_vector("dims");

	// the following already does a SG_REF on the newly created feature
	SG_DEBUG("Leaving!\n");
	return features->copy_dimension_subset(dims);
}

float64_t CDependenceMaximization::compute_measures(CFeatures* features,
		index_t idx)
{
	SG_DEBUG("Entering!\n");

	// remove the dimension (feat) specified by the index idx
	CFeatures* reduced_feats=create_transformed_copy(features, idx);
	ASSERT(reduced_feats);

	// perform an independence test for X\X_i ~ p and Y ~ q with
	// H_0: P(X\X_i, Y) = P(X\X_i) * P(Y)
	// the test statistic can then be used as a measure of dependence
	// See CIndependenceTest class documentation for details
	m_estimator->set_p(reduced_feats);
	float64_t statistic=m_estimator->compute_statistic();

	SG_DEBUG("statistic = %f!\n", statistic);

	SG_UNREF(reduced_feats);

	SG_DEBUG("Leaving!\n");
	return statistic;
}

CFeatures* CDependenceMaximization::remove_feats(CFeatures* features,
		SGVector<index_t> argsorted)
{
	SG_DEBUG("Entering!\n");

	REQUIRE(m_num_remove>0, "Number or percentage of features to be removed is "
			"not set! Please use set_num_remove() to set this!\n");
	REQUIRE(m_policy==N_LARGEST || m_policy==PERCENTILE_LARGEST,
			"Only N_LARGEST and PERCENTILE_LARGEST removal policy can work "
			"with %s!\n", get_name());
	REQUIRE(features, "Features is not intialized!\n");
	REQUIRE(argsorted.vector, "The argsorted vector is not initialized!\n");
	REQUIRE(get_num_features(features)==argsorted.vlen,
			"argsorted vector should be equal to the number of features (%d)! "
			"But it was %d!\n", argsorted.vlen);

	// compute a threshold to remove for both the policies
	index_t threshold=m_num_remove;
	if (m_policy==PERCENTILE_LARGEST)
		threshold*=argsorted.vlen*0.01;

	// make sure that the threshold is valid given the current number of feats
	REQUIRE(threshold<argsorted.vlen, "The threshold of removal is too high "
			"(asked to remove %d features out of %d)! Please use a smaller "
			"number for removal using set_num_remove() call",
			threshold, argsorted.vlen);

	// remove the highest rank holders by storing indices
	SGVector<index_t> inds(argsorted.vlen-threshold);
	sg_memcpy(inds.vector, argsorted.vector, sizeof(index_t)*inds.vlen);

	// sorting the indices to get the original order
	CMath::qsort(inds);
	if (io->get_loglevel()==MSG_DEBUG || io->get_loglevel()==MSG_GCDEBUG)
		inds.display_vector("selected feats");

	// copy rest of the features and SG_UNREF the original feat obj
	CFeatures* reduced_feats=features->copy_dimension_subset(inds);

	// add the selected features to the subset
	ASSERT(m_subset)
	m_subset->add_subset(inds);

	SG_UNREF(features);

	SG_DEBUG("Leaving!\n");
	return reduced_feats;
}

void CDependenceMaximization::set_policy(EFeatureRemovalPolicy policy)
{
	REQUIRE(policy==N_LARGEST || policy==PERCENTILE_LARGEST,
			"Only N_LARGEST and PERCENTILE_LARGEST removal policy can work "
			"with %s!\n", get_name());
	m_policy=policy;
}

void CDependenceMaximization::set_labels(CLabels* labels)
{
	// NULL check is handled in base class CFeatureSelection
	CFeatureSelection<float64_t>::set_labels(labels);

	// convert the CLabels object to CDenseFeatures
	SG_UNREF(m_labels_feats);

	SGMatrix<float64_t> labels_matrix(1, m_labels->get_num_labels());
	for (index_t i=0; i<labels_matrix.num_cols; ++i)
		labels_matrix.matrix[i]=m_labels->get_value(i);

	m_labels_feats=new CDenseFeatures<float64_t>(labels_matrix);
	SG_REF(m_labels_feats);

	// we need to set this to the estimator which is set internally
	ASSERT(m_estimator);
	m_estimator->set_q(m_labels_feats);
}