[mlpack-svn] r10372 - mlpack/trunk/src/mlpack/methods/nca
fastlab-svn at coffeetalk-1.cc.gatech.edu
fastlab-svn at coffeetalk-1.cc.gatech.edu
Wed Nov 23 21:06:42 EST 2011
Author: rcurtin
Date: 2011-11-23 21:06:41 -0500 (Wed, 23 Nov 2011)
New Revision: 10372
Added:
mlpack/trunk/src/mlpack/methods/nca/nca.hpp
mlpack/trunk/src/mlpack/methods/nca/nca_impl.hpp
mlpack/trunk/src/mlpack/methods/nca/nca_main.cpp
mlpack/trunk/src/mlpack/methods/nca/nca_softmax_error_function.hpp
mlpack/trunk/src/mlpack/methods/nca/nca_softmax_error_function_impl.hpp
Removed:
mlpack/trunk/src/mlpack/methods/nca/nca.h
mlpack/trunk/src/mlpack/methods/nca/nca_impl.h
mlpack/trunk/src/mlpack/methods/nca/nca_main.cc
mlpack/trunk/src/mlpack/methods/nca/nca_softmax_error_function.h
mlpack/trunk/src/mlpack/methods/nca/nca_softmax_error_function_impl.h
Modified:
mlpack/trunk/src/mlpack/methods/nca/CMakeLists.txt
Log:
Change NCA filenames according to #152 and change style according to #153.
Modified: mlpack/trunk/src/mlpack/methods/nca/CMakeLists.txt
===================================================================
--- mlpack/trunk/src/mlpack/methods/nca/CMakeLists.txt 2011-11-24 01:51:41 UTC (rev 10371)
+++ mlpack/trunk/src/mlpack/methods/nca/CMakeLists.txt 2011-11-24 02:06:41 UTC (rev 10372)
@@ -3,10 +3,10 @@
# Define the files we need to compile.
# Anything not in this list will not be compiled into MLPACK.
set(SOURCES
- nca.h
- nca_impl.h
- nca_softmax_error_function.h
- nca_softmax_error_function_impl.h
+ nca.hpp
+ nca_impl.hpp
+ nca_softmax_error_function.hpp
+ nca_softmax_error_function_impl.hpp
)
# Add directory name to sources.
@@ -19,7 +19,7 @@
set(MLPACK_SRCS ${MLPACK_SRCS} ${DIR_SRCS} PARENT_SCOPE)
add_executable(nca
- nca_main.cc
+ nca_main.cpp
)
target_link_libraries(nca
mlpack
Deleted: mlpack/trunk/src/mlpack/methods/nca/nca.h
===================================================================
--- mlpack/trunk/src/mlpack/methods/nca/nca.h 2011-11-24 01:51:41 UTC (rev 10371)
+++ mlpack/trunk/src/mlpack/methods/nca/nca.h 2011-11-24 02:06:41 UTC (rev 10372)
@@ -1,67 +0,0 @@
-/**
- * @file nca.h
- * @author Ryan Curtin
- *
- * Declaration of NCA class (Neighborhood Components Analysis).
- */
-#ifndef __MLPACK_METHODS_NCA_NCA_H
-#define __MLPACK_METHODS_NCA_NCA_H
-
-#include <mlpack/core.h>
-#include <mlpack/core/metrics/lmetric.hpp>
-
-namespace mlpack {
-namespace nca {
-
-/**
- * An implementation of Neighborhood Components Analysis, both a linear
- * dimensionality reduction technique and a distance learning technique. The
- * method seeks to improve k-nearest-neighbor classification on a dataset by
- * scaling the dimensions. The method is nonparametric, and does not require a
- * value of k. It works by using stochastic ("soft") neighbor assignments and
- * using optimization techniques over the gradient of the accuracy of the
- * neighbor assignments.
- *
- * For more details, see the following published paper:
- *
- * @inproceedings{Goldberger2004,
- * author = {Goldberger, Jacob and Roweis, Sam and Hinton, Geoff and
- * Salakhutdinov, Ruslan},
- * booktitle = {Advances in Neural Information Processing Systems 17},
- * pages = {513--520},
- * publisher = {MIT Press},
- * title = {{Neighbourhood Components Analysis}},
- * year = {2004}
- * }
- */
-template<typename Kernel>
-class NCA {
- public:
- /**
- * Construct the Neighborhood Components Analysis object. This simply stores
- * the reference to the dataset, before the actual optimization is performed.
- *
- * @param dataset Input dataset.
- */
- NCA(const arma::mat& dataset, const arma::uvec& labels);
-
- /**
- * Perform Neighborhood Components Analysis. The output distance learning
- * matrix is written into the passed reference.
- *
- * @param output_matrix Covariance matrix of Mahalanobis distance.
- */
- void LearnDistance(arma::mat& output_matrix);
-
- private:
- const arma::mat& dataset_;
- const arma::uvec& labels_;
-};
-
-}; // namespace nca
-}; // namespace mlpack
-
-// Include the implementation.
-#include "nca_impl.h"
-
-#endif
Copied: mlpack/trunk/src/mlpack/methods/nca/nca.hpp (from rev 10353, mlpack/trunk/src/mlpack/methods/nca/nca.h)
===================================================================
--- mlpack/trunk/src/mlpack/methods/nca/nca.hpp (rev 0)
+++ mlpack/trunk/src/mlpack/methods/nca/nca.hpp 2011-11-24 02:06:41 UTC (rev 10372)
@@ -0,0 +1,68 @@
+/**
+ * @file nca.hpp
+ * @author Ryan Curtin
+ *
+ * Declaration of NCA class (Neighborhood Components Analysis).
+ */
+#ifndef __MLPACK_METHODS_NCA_NCA_HPP
+#define __MLPACK_METHODS_NCA_NCA_HPP
+
+#include <mlpack/core.h>
+#include <mlpack/core/metrics/lmetric.hpp>
+
+namespace mlpack {
+namespace nca {
+
+/**
+ * An implementation of Neighborhood Components Analysis, both a linear
+ * dimensionality reduction technique and a distance learning technique. The
+ * method seeks to improve k-nearest-neighbor classification on a dataset by
+ * scaling the dimensions. The method is nonparametric, and does not require a
+ * value of k. It works by using stochastic ("soft") neighbor assignments and
+ * using optimization techniques over the gradient of the accuracy of the
+ * neighbor assignments.
+ *
+ * For more details, see the following published paper:
+ *
+ * @inproceedings{Goldberger2004,
+ * author = {Goldberger, Jacob and Roweis, Sam and Hinton, Geoff and
+ * Salakhutdinov, Ruslan},
+ * booktitle = {Advances in Neural Information Processing Systems 17},
+ * pages = {513--520},
+ * publisher = {MIT Press},
+ * title = {{Neighbourhood Components Analysis}},
+ * year = {2004}
+ * }
+ */
+template<typename Kernel>
+class NCA
+{
+ public:
+ /**
+ * Construct the Neighborhood Components Analysis object. This simply stores
+ * the reference to the dataset, before the actual optimization is performed.
+ *
+ * @param dataset Input dataset.
+ */
+ NCA(const arma::mat& dataset, const arma::uvec& labels);
+
+ /**
+ * Perform Neighborhood Components Analysis. The output distance learning
+ * matrix is written into the passed reference.
+ *
+ * @param output_matrix Covariance matrix of Mahalanobis distance.
+ */
+ void LearnDistance(arma::mat& output_matrix);
+
+ private:
+ const arma::mat& dataset_;
+ const arma::uvec& labels_;
+};
+
+}; // namespace nca
+}; // namespace mlpack
+
+// Include the implementation.
+#include "nca_impl.hpp"
+
+#endif
Deleted: mlpack/trunk/src/mlpack/methods/nca/nca_impl.h
===================================================================
--- mlpack/trunk/src/mlpack/methods/nca/nca_impl.h 2011-11-24 01:51:41 UTC (rev 10371)
+++ mlpack/trunk/src/mlpack/methods/nca/nca_impl.h 2011-11-24 02:06:41 UTC (rev 10372)
@@ -1,40 +0,0 @@
-/***
- * @file nca_impl.h
- * @author Ryan Curtin
- *
- * Implementation of templated NCA class.
- */
-#ifndef __MLPACK_METHODS_NCA_NCA_IMPL_H
-#define __MLPACK_METHODS_NCA_NCA_IMPL_H
-
-// In case it was not already included.
-#include "nca.h"
-
-#include <mlpack/core/optimizers/lbfgs/lbfgs.hpp>
-
-#include "nca_softmax_error_function.h"
-
-namespace mlpack {
-namespace nca {
-
-// Just set the internal matrix reference.
-template<typename Kernel>
-NCA<Kernel>::NCA(const arma::mat& dataset, const arma::uvec& labels) :
- dataset_(dataset), labels_(labels) { /* nothing to do */ }
-
-template<typename Kernel>
-void NCA<Kernel>::LearnDistance(arma::mat& output_matrix) {
- output_matrix = arma::eye<arma::mat>(dataset_.n_rows, dataset_.n_rows);
-
- SoftmaxErrorFunction<Kernel> error_func(dataset_, labels_);
-
- // We will use the L-BFGS optimizer to optimize the stretching matrix.
- optimization::L_BFGS<SoftmaxErrorFunction<Kernel> > lbfgs(error_func, 10);
-
- lbfgs.Optimize(0, output_matrix);
-}
-
-}; // namespace nca
-}; // namespace mlpack
-
-#endif
Copied: mlpack/trunk/src/mlpack/methods/nca/nca_impl.hpp (from rev 10352, mlpack/trunk/src/mlpack/methods/nca/nca_impl.h)
===================================================================
--- mlpack/trunk/src/mlpack/methods/nca/nca_impl.hpp (rev 0)
+++ mlpack/trunk/src/mlpack/methods/nca/nca_impl.hpp 2011-11-24 02:06:41 UTC (rev 10372)
@@ -0,0 +1,41 @@
+/***
+ * @file nca_impl.hpp
+ * @author Ryan Curtin
+ *
+ * Implementation of templated NCA class.
+ */
+#ifndef __MLPACK_METHODS_NCA_NCA_IMPL_HPP
+#define __MLPACK_METHODS_NCA_NCA_IMPL_HPP
+
+// In case it was not already included.
+#include "nca.hpp"
+
+#include <mlpack/core/optimizers/lbfgs/lbfgs.hpp>
+
+#include "nca_softmax_error_function.hpp"
+
+namespace mlpack {
+namespace nca {
+
+// Just set the internal matrix reference.
+template<typename Kernel>
+NCA<Kernel>::NCA(const arma::mat& dataset, const arma::uvec& labels) :
+ dataset_(dataset), labels_(labels) { /* nothing to do */ }
+
+template<typename Kernel>
+void NCA<Kernel>::LearnDistance(arma::mat& output_matrix)
+{
+ output_matrix = arma::eye<arma::mat>(dataset_.n_rows, dataset_.n_rows);
+
+ SoftmaxErrorFunction<Kernel> error_func(dataset_, labels_);
+
+ // We will use the L-BFGS optimizer to optimize the stretching matrix.
+ optimization::L_BFGS<SoftmaxErrorFunction<Kernel> > lbfgs(error_func, 10);
+
+ lbfgs.Optimize(0, output_matrix);
+}
+
+}; // namespace nca
+}; // namespace mlpack
+
+#endif
Deleted: mlpack/trunk/src/mlpack/methods/nca/nca_main.cc
===================================================================
--- mlpack/trunk/src/mlpack/methods/nca/nca_main.cc 2011-11-24 01:51:41 UTC (rev 10371)
+++ mlpack/trunk/src/mlpack/methods/nca/nca_main.cc 2011-11-24 02:06:41 UTC (rev 10372)
@@ -1,43 +0,0 @@
-/**
- * @file nca_main.cc
- * @author Ryan Curtin
- *
- * Executable for Neighborhood Components Analysis.
- */
-#include <mlpack/core.h>
-#include <mlpack/core/metrics/lmetric.hpp>
-
-#include "nca.h"
-
-// Define parameters.
-PROGRAM_INFO("Neighborhood Components Analysis",
- "documentation not done yet", "");
-
-PARAM_STRING_REQ("input_file", "Input dataset to run NCA on.", "");
-PARAM_STRING_REQ("output_file", "Output file for learned distance matrix.", "");
-
-using namespace mlpack;
-using namespace mlpack::nca;
-using namespace mlpack::metric;
-using namespace std;
-
-int main(int argc, char* argv[]) {
- CLI::ParseCommandLine(argc, argv);
-
- arma::mat data;
- data::Load(CLI::GetParam<string>("input_file").c_str(), data, true);
-
- arma::uvec labels(data.n_cols);
- for (size_t i = 0; i < data.n_cols; i++)
- labels[i] = (int) data(data.n_rows - 1, i);
-
- data.shed_row(data.n_rows - 1);
-
- NCA<LMetric<2> > nca(data, labels);
-
- arma::mat distance;
-
- nca.LearnDistance(distance);
-
- data::Save(CLI::GetParam<string>("output_file").c_str(), distance, true);
-}
Copied: mlpack/trunk/src/mlpack/methods/nca/nca_main.cpp (from rev 10353, mlpack/trunk/src/mlpack/methods/nca/nca_main.cc)
===================================================================
--- mlpack/trunk/src/mlpack/methods/nca/nca_main.cpp (rev 0)
+++ mlpack/trunk/src/mlpack/methods/nca/nca_main.cpp 2011-11-24 02:06:41 UTC (rev 10372)
@@ -0,0 +1,44 @@
+/**
+ * @file nca_main.cpp
+ * @author Ryan Curtin
+ *
+ * Executable for Neighborhood Components Analysis.
+ */
+#include <mlpack/core.h>
+#include <mlpack/core/metrics/lmetric.hpp>
+
+#include "nca.hpp"
+
+// Define parameters.
+PROGRAM_INFO("Neighborhood Components Analysis",
+ "documentation not done yet", "");
+
+PARAM_STRING_REQ("input_file", "Input dataset to run NCA on.", "");
+PARAM_STRING_REQ("output_file", "Output file for learned distance matrix.", "");
+
+using namespace mlpack;
+using namespace mlpack::nca;
+using namespace mlpack::metric;
+using namespace std;
+
+int main(int argc, char* argv[])
+{
+ CLI::ParseCommandLine(argc, argv);
+
+ arma::mat data;
+ data::Load(CLI::GetParam<string>("input_file").c_str(), data, true);
+
+ arma::uvec labels(data.n_cols);
+ for (size_t i = 0; i < data.n_cols; i++)
+ labels[i] = (int) data(data.n_rows - 1, i);
+
+ data.shed_row(data.n_rows - 1);
+
+ NCA<LMetric<2> > nca(data, labels);
+
+ arma::mat distance;
+
+ nca.LearnDistance(distance);
+
+ data::Save(CLI::GetParam<string>("output_file").c_str(), distance, true);
+}
Deleted: mlpack/trunk/src/mlpack/methods/nca/nca_softmax_error_function.h
===================================================================
--- mlpack/trunk/src/mlpack/methods/nca/nca_softmax_error_function.h 2011-11-24 01:51:41 UTC (rev 10371)
+++ mlpack/trunk/src/mlpack/methods/nca/nca_softmax_error_function.h 2011-11-24 02:06:41 UTC (rev 10372)
@@ -1,104 +0,0 @@
-/**
- * @file nca_softmax.h
- * @author Ryan Curtin
- *
- * Implementation of the stochastic neighbor assignment probability error
- * function (the "softmax error").
- */
-#ifndef __MLPACK_METHODS_NCA_NCA_SOFTMAX_ERROR_FUNCTCLIN_H
-#define __MLPACK_METHODS_NCA_NCA_SOFTMAX_ERROR_FUNCTCLIN_H
-
-#include <mlpack/core.h>
-
-namespace mlpack {
-namespace nca {
-
-/**
- * The "softmax" stochastic neighbor assignment probability function.
- *
- * The actual function is
- *
- * p_ij = (exp(-|| A x_i - A x_j || ^ 2)) /
- * (sum_{k != i} (exp(-|| A x_i - A x_k || ^ 2)))
- *
- * where x_n represents a point and A is the current scaling matrix.
- *
- * This class is more flexible than the original paper, allowing an arbitrary
- * kernel function to be used, meaning that the Mahalanobis distance is not the
- * only allowed way to run NCA. However, the Mahalanobis distance is probably
- * the best way to use this.
- */
-template<typename Kernel>
-class SoftmaxErrorFunction {
- public:
- /**
- * Initialize with the given kernel; useful when the kernel has some state to
- * store, which is set elsewhere. If no kernel is given, an empty kernel is
- * used; this way, you can call the constructor with no arguments. A
- * reference to the dataset we will be optimizing over is also required.
- *
- * @param dataset Matrix containing the dataset.
- * @param labels Vector of class labels for each point in the dataset.
- * @param kernel Instantiated kernel (optional).
- */
- SoftmaxErrorFunction(const arma::mat& dataset,
- const arma::uvec& labels,
- Kernel kernel = Kernel());
-
- /**
- * Evaluate the softmax function for the given covariance matrix.
- *
- * @param covariance Covariance matrix of Mahalanobis distance.
- */
- double Evaluate(const arma::mat& covariance);
-
- /**
- * Evaluate the gradient of the softmax function for the given covariance
- * matrix.
- *
- * @param covariance Covariance matrix of Mahalanobis distance.
- * @param gradient Matrix to store the calculated gradient in.
- */
- void Gradient(const arma::mat& covariance, arma::mat& gradient);
-
- /**
- * Get the initial point.
- */
- arma::mat GetInitialPoint();
-
- private:
- const arma::mat& dataset_;
- const arma::uvec& labels_;
-
- Kernel kernel_;
-
- arma::mat last_coordinates_;
- arma::mat stretched_dataset_;
- arma::vec p_; // Holds calculated p_i.
- arma::vec denominators_; // Holds denominators for calculation of p_ij.
-
- //! False is nothing has ever been precalculated (only at construction time).
- bool precalculated_;
-
- /**
- * Precalculate the denominators and numerators that will make up the p_ij,
- * but only if the coordinates matrix is different than the last coordinates
- * the Precalculate() method was run with.
- *
- * This will update last_coordinates_ and stretched_dataset_, and also
- * calculate the p_i and denominators_ which are used in the calculation of
- * p_i or p_ij. The calculation will be O((n * (n + 1)) / 2), which is not
- * great.
- *
- * @param coordinates Coordinates matrix to use for precalculation.
- */
- void Precalculate(const arma::mat& coordinates);
-};
-
-}; // namespace nca
-}; // namespace mlpack
-
-// Include implementation.
-#include "nca_softmax_error_function_impl.h"
-
-#endif
Copied: mlpack/trunk/src/mlpack/methods/nca/nca_softmax_error_function.hpp (from rev 10352, mlpack/trunk/src/mlpack/methods/nca/nca_softmax_error_function.h)
===================================================================
--- mlpack/trunk/src/mlpack/methods/nca/nca_softmax_error_function.hpp (rev 0)
+++ mlpack/trunk/src/mlpack/methods/nca/nca_softmax_error_function.hpp 2011-11-24 02:06:41 UTC (rev 10372)
@@ -0,0 +1,105 @@
+/**
+ * @file nca_softmax_error_function.hpp
+ * @author Ryan Curtin
+ *
+ * Implementation of the stochastic neighbor assignment probability error
+ * function (the "softmax error").
+ */
+#ifndef __MLPACK_METHODS_NCA_NCA_SOFTMAX_ERROR_FUNCTION_HPP
+#define __MLPACK_METHODS_NCA_NCA_SOFTMAX_ERROR_FUNCTION_HPP
+
+#include <mlpack/core.h>
+
+namespace mlpack {
+namespace nca {
+
+/**
+ * The "softmax" stochastic neighbor assignment probability function.
+ *
+ * The actual function is
+ *
+ * p_ij = (exp(-|| A x_i - A x_j || ^ 2)) /
+ * (sum_{k != i} (exp(-|| A x_i - A x_k || ^ 2)))
+ *
+ * where x_n represents a point and A is the current scaling matrix.
+ *
+ * This class is more flexible than the original paper, allowing an arbitrary
+ * kernel function to be used, meaning that the Mahalanobis distance is not the
+ * only allowed way to run NCA. However, the Mahalanobis distance is probably
+ * the best way to use this.
+ */
+template<typename Kernel>
+class SoftmaxErrorFunction
+{
+ public:
+ /**
+ * Initialize with the given kernel; useful when the kernel has some state to
+ * store, which is set elsewhere. If no kernel is given, an empty kernel is
+ * used; this way, you can call the constructor with no arguments. A
+ * reference to the dataset we will be optimizing over is also required.
+ *
+ * @param dataset Matrix containing the dataset.
+ * @param labels Vector of class labels for each point in the dataset.
+ * @param kernel Instantiated kernel (optional).
+ */
+ SoftmaxErrorFunction(const arma::mat& dataset,
+ const arma::uvec& labels,
+ Kernel kernel = Kernel());
+
+ /**
+ * Evaluate the softmax function for the given covariance matrix.
+ *
+ * @param covariance Covariance matrix of Mahalanobis distance.
+ */
+ double Evaluate(const arma::mat& covariance);
+
+ /**
+ * Evaluate the gradient of the softmax function for the given covariance
+ * matrix.
+ *
+ * @param covariance Covariance matrix of Mahalanobis distance.
+ * @param gradient Matrix to store the calculated gradient in.
+ */
+ void Gradient(const arma::mat& covariance, arma::mat& gradient);
+
+ /**
+ * Get the initial point.
+ */
+ arma::mat GetInitialPoint();
+
+ private:
+ const arma::mat& dataset_;
+ const arma::uvec& labels_;
+
+ Kernel kernel_;
+
+ arma::mat last_coordinates_;
+ arma::mat stretched_dataset_;
+ arma::vec p_; // Holds calculated p_i.
+ arma::vec denominators_; // Holds denominators for calculation of p_ij.
+
+ //! False is nothing has ever been precalculated (only at construction time).
+ bool precalculated_;
+
+ /**
+ * Precalculate the denominators and numerators that will make up the p_ij,
+ * but only if the coordinates matrix is different than the last coordinates
+ * the Precalculate() method was run with.
+ *
+ * This will update last_coordinates_ and stretched_dataset_, and also
+ * calculate the p_i and denominators_ which are used in the calculation of
+ * p_i or p_ij. The calculation will be O((n * (n + 1)) / 2), which is not
+ * great.
+ *
+ * @param coordinates Coordinates matrix to use for precalculation.
+ */
+ void Precalculate(const arma::mat& coordinates);
+};
+
+}; // namespace nca
+}; // namespace mlpack
+
+// Include implementation.
+#include "nca_softmax_error_function_impl.hpp"
+
+#endif
Deleted: mlpack/trunk/src/mlpack/methods/nca/nca_softmax_error_function_impl.h
===================================================================
--- mlpack/trunk/src/mlpack/methods/nca/nca_softmax_error_function_impl.h 2011-11-24 01:51:41 UTC (rev 10371)
+++ mlpack/trunk/src/mlpack/methods/nca/nca_softmax_error_function_impl.h 2011-11-24 02:06:41 UTC (rev 10372)
@@ -1,141 +0,0 @@
-/**
- * @file nca_softmax_impl.h
- * @author Ryan Curtin
- *
- * Implementation of the Softmax error function.
- */
-#ifndef __MLPACK_METHODS_NCA_NCA_SOFTMAX_ERROR_FUNCTCLIN_IMPL_H
-#define __MLPACK_METHODS_NCA_NCA_SOFTMAX_ERROR_FUNCTCLIN_IMPL_H
-
-#include "nca_softmax_error_function.h"
-
-namespace mlpack {
-namespace nca {
-
-// Initialize with the given kernel.
-template<typename Kernel>
-SoftmaxErrorFunction<Kernel>::SoftmaxErrorFunction(const arma::mat& dataset,
- const arma::uvec& labels,
- Kernel kernel) :
- dataset_(dataset), labels_(labels), kernel_(kernel),
- last_coordinates_(dataset.n_rows, dataset.n_rows),
- precalculated_(false)
-{ /* nothing to do */ }
-
-template<typename Kernel>
-double SoftmaxErrorFunction<Kernel>::Evaluate(const arma::mat& coordinates) {
- // Calculate the denominators and numerators, if necessary.
- Precalculate(coordinates);
-
- return -accu(p_); // Sum of p_i for all i. We negate because our solver
- // minimizes, not maximizes.
-};
-
-template<typename Kernel>
-void SoftmaxErrorFunction<Kernel>::Gradient(const arma::mat& coordinates,
- arma::mat& gradient) {
- // Calculate the denominators and numerators, if necessary.
- Precalculate(coordinates);
-
- // Now, we handle the summation over i:
- // sum_i (p_i sum_k (p_ik x_ik x_ik^T) -
- // sum_{j in class of i} (p_ij x_ij x_ij^T)
- // We can algebraically manipulate the whole thing to produce a more
- // memory-friendly way to calculate this. Looping over each i and k (again
- // O((n * (n + 1)) / 2) as with the last step, we can add the following to the
- // sum:
- //
- // if class of i is the same as the class of k, add
- // (((p_i - (1 / p_i)) p_ik) + ((p_k - (1 / p_k)) p_ki)) x_ik x_ik^T
- // otherwise, add
- // (p_i p_ik + p_k p_ki) x_ik x_ik^T
- arma::mat sum;
- sum.zeros(stretched_dataset_.n_rows, stretched_dataset_.n_rows);
- for (size_t i = 0; i < stretched_dataset_.n_cols; i++) {
- for (size_t k = (i + 1); k < stretched_dataset_.n_cols; k++) {
- // Calculate p_ik and p_ki first.
- double eval = exp(-kernel_.Evaluate(stretched_dataset_.unsafe_col(i),
- stretched_dataset_.unsafe_col(k)));
- double p_ik = 0, p_ki = 0;
- p_ik = eval / denominators_(i);
- p_ki = eval / denominators_(k);
-
- // Subtract x_i from x_k. We are not using stretched points here.
- arma::vec x_ik = dataset_.col(i) - dataset_.col(k);
- arma::mat second_term = (x_ik * trans(x_ik));
-
- if (labels_[i] == labels_[k])
- sum += ((p_[i] - 1) * p_ik + (p_[k] - 1) * p_ki) * second_term;
- else
- sum += (p_[i] * p_ik + p_[k] * p_ki) * second_term;
- }
- }
-
- // Assemble the final gradient.
- gradient = -2 * coordinates * sum;
-}
-
-template<typename Kernel>
-arma::mat SoftmaxErrorFunction<Kernel>::GetInitialPoint() {
- return arma::eye<arma::mat>(dataset_.n_rows, dataset_.n_rows);
-}
-
-template<typename Kernel>
-void SoftmaxErrorFunction<Kernel>::Precalculate(const arma::mat& coordinates) {
- // Make sure the calculation is necessary.
- if ((accu(coordinates == last_coordinates_) == coordinates.n_elem) &&
- precalculated_)
- return; // No need to calculate; we already have this stuff saved.
-
- // Coordinates are different; save the new ones, and stretch the dataset.
- last_coordinates_ = coordinates;
- stretched_dataset_ = coordinates * dataset_;
-
- // For each point i, we must evaluate the softmax function:
- // p_ij = exp( -K(x_i, x_j) ) / ( sum_{k != i} ( exp( -K(x_i, x_k) )))
- // p_i = sum_{j in class of i} p_ij
- // We will do this by keeping track of the denominators for each i as well as
- // the numerators (the sum for all j in class of i). This will be on the
- // order of O((n * (n + 1)) / 2), which really isn't all that great.
- p_.zeros(stretched_dataset_.n_cols);
- denominators_.zeros(stretched_dataset_.n_cols);
- for (size_t i = 0; i < stretched_dataset_.n_cols; i++) {
- for (size_t j = (i + 1); j < stretched_dataset_.n_cols; j++) {
- // Evaluate exp(-K(x_i, x_j)).
- double eval = exp(-kernel_.Evaluate(stretched_dataset_.unsafe_col(i),
- stretched_dataset_.unsafe_col(j)));
-
- // Add this to the denominators of both i and j: p_ij = p_ji.
- denominators_[i] += eval;
- denominators_[j] += eval;
-
- // If i and j are the same class, add to numerator of both.
- if (labels_[i] == labels_[j]) {
- p_[i] += eval;
- p_[j] += eval;
- }
- }
- }
-
- // Divide p_i by their denominators.
- p_ /= denominators_;
-
- // Clean up any bad values.
- for (size_t i = 0; i < stretched_dataset_.n_cols; i++) {
- if (denominators_[i] == 0.0) {
- Log::Debug << "Denominator of p_{" << i << ", j} is 0." << std::endl;
-
- // Set to usable values.
- denominators_[i] = std::numeric_limits<double>::infinity();
- p_[i] = 0;
- }
- }
-
- // We've done a precalculation. Mark it as done.
- precalculated_ = true;
-}
-
-}; // namespace nca
-}; // namespace mlpack
-
-#endif
Copied: mlpack/trunk/src/mlpack/methods/nca/nca_softmax_error_function_impl.hpp (from rev 10352, mlpack/trunk/src/mlpack/methods/nca/nca_softmax_error_function_impl.h)
===================================================================
--- mlpack/trunk/src/mlpack/methods/nca/nca_softmax_error_function_impl.hpp (rev 0)
+++ mlpack/trunk/src/mlpack/methods/nca/nca_softmax_error_function_impl.hpp 2011-11-24 02:06:41 UTC (rev 10372)
@@ -0,0 +1,153 @@
+/**
+ * @file nca_softmax_impl.h
+ * @author Ryan Curtin
+ *
+ * Implementation of the Softmax error function.
+ */
+#ifndef __MLPACK_METHODS_NCA_NCA_SOFTMAX_ERROR_FUNCTCLIN_IMPL_H
+#define __MLPACK_METHODS_NCA_NCA_SOFTMAX_ERROR_FUNCTCLIN_IMPL_H
+
+// In case it hasn't been included already.
+#include "nca_softmax_error_function.hpp"
+
+namespace mlpack {
+namespace nca {
+
+// Initialize with the given kernel.
+template<typename Kernel>
+SoftmaxErrorFunction<Kernel>::SoftmaxErrorFunction(const arma::mat& dataset,
+ const arma::uvec& labels,
+ Kernel kernel) :
+ dataset_(dataset), labels_(labels), kernel_(kernel),
+ last_coordinates_(dataset.n_rows, dataset.n_rows),
+ precalculated_(false)
+{ /* nothing to do */ }
+
+template<typename Kernel>
+double SoftmaxErrorFunction<Kernel>::Evaluate(const arma::mat& coordinates)
+{
+ // Calculate the denominators and numerators, if necessary.
+ Precalculate(coordinates);
+
+ return -accu(p_); // Sum of p_i for all i. We negate because our solver
+ // minimizes, not maximizes.
+};
+
+template<typename Kernel>
+void SoftmaxErrorFunction<Kernel>::Gradient(const arma::mat& coordinates,
+ arma::mat& gradient)
+{
+ // Calculate the denominators and numerators, if necessary.
+ Precalculate(coordinates);
+
+ // Now, we handle the summation over i:
+ // sum_i (p_i sum_k (p_ik x_ik x_ik^T) -
+ // sum_{j in class of i} (p_ij x_ij x_ij^T)
+ // We can algebraically manipulate the whole thing to produce a more
+ // memory-friendly way to calculate this. Looping over each i and k (again
+ // O((n * (n + 1)) / 2) as with the last step, we can add the following to the
+ // sum:
+ //
+ // if class of i is the same as the class of k, add
+ // (((p_i - (1 / p_i)) p_ik) + ((p_k - (1 / p_k)) p_ki)) x_ik x_ik^T
+ // otherwise, add
+ // (p_i p_ik + p_k p_ki) x_ik x_ik^T
+ arma::mat sum;
+ sum.zeros(stretched_dataset_.n_rows, stretched_dataset_.n_rows);
+ for (size_t i = 0; i < stretched_dataset_.n_cols; i++)
+ {
+ for (size_t k = (i + 1); k < stretched_dataset_.n_cols; k++)
+ {
+ // Calculate p_ik and p_ki first.
+ double eval = exp(-kernel_.Evaluate(stretched_dataset_.unsafe_col(i),
+ stretched_dataset_.unsafe_col(k)));
+ double p_ik = 0, p_ki = 0;
+ p_ik = eval / denominators_(i);
+ p_ki = eval / denominators_(k);
+
+ // Subtract x_i from x_k. We are not using stretched points here.
+ arma::vec x_ik = dataset_.col(i) - dataset_.col(k);
+ arma::mat second_term = (x_ik * trans(x_ik));
+
+ if (labels_[i] == labels_[k])
+ sum += ((p_[i] - 1) * p_ik + (p_[k] - 1) * p_ki) * second_term;
+ else
+ sum += (p_[i] * p_ik + p_[k] * p_ki) * second_term;
+ }
+ }
+
+ // Assemble the final gradient.
+ gradient = -2 * coordinates * sum;
+}
+
+template<typename Kernel>
+arma::mat SoftmaxErrorFunction<Kernel>::GetInitialPoint()
+{
+ return arma::eye<arma::mat>(dataset_.n_rows, dataset_.n_rows);
+}
+
+template<typename Kernel>
+void SoftmaxErrorFunction<Kernel>::Precalculate(const arma::mat& coordinates)
+{
+ // Make sure the calculation is necessary.
+ if ((accu(coordinates == last_coordinates_) == coordinates.n_elem) &&
+ precalculated_)
+ return; // No need to calculate; we already have this stuff saved.
+
+ // Coordinates are different; save the new ones, and stretch the dataset.
+ last_coordinates_ = coordinates;
+ stretched_dataset_ = coordinates * dataset_;
+
+ // For each point i, we must evaluate the softmax function:
+ // p_ij = exp( -K(x_i, x_j) ) / ( sum_{k != i} ( exp( -K(x_i, x_k) )))
+ // p_i = sum_{j in class of i} p_ij
+ // We will do this by keeping track of the denominators for each i as well as
+ // the numerators (the sum for all j in class of i). This will be on the
+ // order of O((n * (n + 1)) / 2), which really isn't all that great.
+ p_.zeros(stretched_dataset_.n_cols);
+ denominators_.zeros(stretched_dataset_.n_cols);
+ for (size_t i = 0; i < stretched_dataset_.n_cols; i++)
+ {
+ for (size_t j = (i + 1); j < stretched_dataset_.n_cols; j++)
+ {
+ // Evaluate exp(-K(x_i, x_j)).
+ double eval = exp(-kernel_.Evaluate(stretched_dataset_.unsafe_col(i),
+ stretched_dataset_.unsafe_col(j)));
+
+ // Add this to the denominators of both i and j: p_ij = p_ji.
+ denominators_[i] += eval;
+ denominators_[j] += eval;
+
+ // If i and j are the same class, add to numerator of both.
+ if (labels_[i] == labels_[j])
+ {
+ p_[i] += eval;
+ p_[j] += eval;
+ }
+ }
+ }
+
+ // Divide p_i by their denominators.
+ p_ /= denominators_;
+
+ // Clean up any bad values.
+ for (size_t i = 0; i < stretched_dataset_.n_cols; i++)
+ {
+ if (denominators_[i] == 0.0)
+ {
+ Log::Debug << "Denominator of p_{" << i << ", j} is 0." << std::endl;
+
+ // Set to usable values.
+ denominators_[i] = std::numeric_limits<double>::infinity();
+ p_[i] = 0;
+ }
+ }
+
+ // We've done a precalculation. Mark it as done.
+ precalculated_ = true;
+}
+
+}; // namespace nca
+}; // namespace mlpack
+
+#endif
More information about the mlpack-svn
mailing list