[mlpack-svn] r11668 - mlpack/trunk/src/mlpack/methods/mvu
fastlab-svn at coffeetalk-1.cc.gatech.edu
fastlab-svn at coffeetalk-1.cc.gatech.edu
Wed Feb 29 17:41:10 EST 2012
Author: rcurtin
Date: 2012-02-29 17:41:10 -0500 (Wed, 29 Feb 2012)
New Revision: 11668
Removed:
mlpack/trunk/src/mlpack/methods/mvu/mvu_objective_function.cpp
mlpack/trunk/src/mlpack/methods/mvu/mvu_objective_function.hpp
Log:
These aren't necessary any more.
Deleted: mlpack/trunk/src/mlpack/methods/mvu/mvu_objective_function.cpp
===================================================================
--- mlpack/trunk/src/mlpack/methods/mvu/mvu_objective_function.cpp 2012-02-29 22:33:45 UTC (rev 11667)
+++ mlpack/trunk/src/mlpack/methods/mvu/mvu_objective_function.cpp 2012-02-29 22:41:10 UTC (rev 11668)
@@ -1,134 +0,0 @@
-/**
- * @file mvu_objective_function.cpp
- * @author Ryan Curtin
- *
- * Implementation of the MVUObjectiveFunction class.
- */
-#include "mvu_objective_function.hpp"
-
-#include <mlpack/methods/neighbor_search/neighbor_search.hpp>
-
-using namespace mlpack;
-using namespace mlpack::mvu;
-
-using mlpack::neighbor::AllkNN;
-
-MVUObjectiveFunction::MVUObjectiveFunction()
-{
- // Need to set initial point? I guess this will be the initial matrix...
- Log::Warn << "Don't use empty constructor for MVUObjectiveFunction()!"
- << "MVU will fail." << std::endl;
-}
-
-MVUObjectiveFunction::MVUObjectiveFunction(const arma::mat& initial_point,
- const size_t newDim,
- const size_t numNeighbors) :
- numNeighbors(numNeighbors)
-{
- // We will calculate the nearest neighbors of this dataset.
- AllkNN allknn(initial_point);
-
- allknn.Search(numNeighbors, neighborIndices, neighborDistances);
-
- // Now shrink the point matrix to the correct target size.
- initialPoint = initial_point;
- initialPoint.shed_rows(newDim, initial_point.n_rows - 1);
-}
-
-double MVUObjectiveFunction::Evaluate(const arma::mat& coordinates)
-{
- // We replaced the SDP constraint (K > 0) with (K = R^T R) so now our
- // objective function is simply that (and R is our coordinate matrix). Since
- // the problem is a maximization problem, we simply negate the objective
- // function and it becomes a minimization problem (which is what L-BFGS and
- // AugLagrangian use).
- double objective = 0;
-
- for (size_t i = 0; i < coordinates.n_cols; i++)
- objective -= dot(coordinates.unsafe_col(i), coordinates.unsafe_col(i));
-
- return objective;
-}
-
-void MVUObjectiveFunction::Gradient(const arma::mat& coordinates,
- arma::mat& gradient)
-{
- // Our objective, f(R) = sum_{ij} (R^T R)_ij, is differentiable into
- // f'(R) = 2 * R.
- gradient = 2 * coordinates;
-}
-
-double MVUObjectiveFunction::EvaluateConstraint(const size_t index,
- const arma::mat& coordinates)
-{
- if (index == 0)
- {
- // We are considering the first constraint:
- // sum (R^T * R) = 0
-
- // This is a naive implementation; we may be able to improve upon it
- // significantly by avoiding the actual calculation of the Gram matrix
- // (R^T * R).
- return accu(trans(coordinates) * coordinates);
- }
-
- // Return 0 for any constraints which are out of bounds.
- if (index >= NumConstraints())
- return 0;
-
- // Any other constraints are the individual nearest neighbor constraints:
- // (R^T R)_ii - 2 (R^T R)_ij + (R^T R)_jj - || x_i - x_j ||^2 = 0
- //
- // We will get the i and j values from the given index.
- int i = floor(((double) (index - 1)) / (double) numNeighbors);
- int j = neighborIndices[index - 1]; // Retrieve index of this neighbor.
-
- // (R^T R)_ij = R.col(i) * R.col(j) (dot product)
- double rrt_ii = dot(coordinates.col(i), coordinates.col(i));
- double rrt_ij = dot(coordinates.col(i), coordinates.col(j));
- double rrt_jj = dot(coordinates.col(j), coordinates.col(j));
-
- return ((rrt_ii - 2 * rrt_ij + rrt_jj) - neighborDistances[index - 1]);
-}
-
-void MVUObjectiveFunction::GradientConstraint(const size_t index,
- const arma::mat& coordinates,
- arma::mat& gradient)
-{
- // Set gradient to 0 (we will add to it).
- gradient.zeros(coordinates.n_rows, coordinates.n_cols);
-
- // Return 0 for any constraints which are out of bounds.
- if (index >= NumConstraints())
- return;
-
- if (index == 0)
- {
- // We consider the gradient of the first constraint:
- // sum (R^T * R) = 0
- // It is eventually worked out that
- // d / dR_xy (sum (R^T R)) = sum_i (R_xi)
- //
- // We can see that we can separate this out into two distinct sums, for each
- // row and column, so we can loop first over the columns and then over the
- // rows to assemble the entire gradient matrix.
- arma::mat ones(gradient.n_cols, gradient.n_cols);
- gradient = coordinates * ones;
-
- return;
- }
-
- // Any other constraints are the individual nearest neighbor constraints:
- // (R^T R)_ii - 2 (R^T R)_ij + (R^T R)_jj = || x_i - x_j ||^2
- //
- // We will get the i and j values from the given index.
- int i = floor(((double) (index - 1)) / (double) numNeighbors);
- int j = neighborIndices[index - 1];
-
- // The gradient matrix for the nearest neighbor constraint (i, j) is zero
- // except for column i, which is equal to 2 (R.col(i) - R.col(j)) and also
- // except for column j, which is equal to 2 (R.col(j) - R.col(i)).
- arma::vec diff_row = coordinates.col(i) - coordinates.col(j);
- gradient.col(i) += 2 * diff_row;
- gradient.col(j) -= 2 * diff_row;
-}
Deleted: mlpack/trunk/src/mlpack/methods/mvu/mvu_objective_function.hpp
===================================================================
--- mlpack/trunk/src/mlpack/methods/mvu/mvu_objective_function.hpp 2012-02-29 22:33:45 UTC (rev 11667)
+++ mlpack/trunk/src/mlpack/methods/mvu/mvu_objective_function.hpp 2012-02-29 22:41:10 UTC (rev 11668)
@@ -1,82 +0,0 @@
-/**
- * @file mvu_objective_function.hpp
- * @author Ryan Curtin
- *
- * This file defines the standard MVU objective function, implemented to fulfill
- * the "LagrangianFunction" policy defined in
- * fastlib/optimization/aug_lagrangian/aug_lagrangian.h.
- *
- * We use the change of variables suggested by Burer and Monteiro [1] to
- * reformulate the MVU SDP originally provided by Weinberger and Saul [2].
- *
- * [1] S. Burer and R.D.C. Monteiro. "A nonlinear programming algorithm for
- * solving semidefinite programs via low-rank factorization," Mathematical
- * Programming, vol. 95, no. 2, pp. 329-357, 2002.
- *
- * [2] K.Q. Weinberger and L.K. Saul, "An introduction to Nonlinear
- * Dimensionality Reduction by Maximum Variance Unfolding," Proceedings of
- * the Twenty-First National Conference on Artificial Intelligence
- * (AAAI-06), 2006.
- */
-#ifndef __MLPACK_METHODS_MVU_MVU_OBJECTIVE_FUNCTION_HPP
-#define __MLPACK_METHODS_MVU_MVU_OBJECTIVE_FUNCTION_HPP
-
-#include <mlpack/core.hpp>
-
-namespace mlpack {
-namespace mvu {
-
-/**
- * The MVU objective function. This is a reformulation of the SDP proposed
- * originally by Weinberger and Saul. Their original formulation was:
- *
- * max (trace(K)) subject to:
- * (1) sum K_ij = 0
- * (2) K_ii - 2 K_ij + K_jj = || x_i - x_j ||^2 ; for all (i, j) nearest
- * neighbors
- * (3) K >= 0 (K is positive semidefinite)
- *
- * We reformulate, taking K = R R^T. This gives:
- *
- * max (R * R^T) subject to
- * (1) sum (R * R^T) = 0
- * (2) (R R^T)_ii - 2 (R R^T)_ij + (R R^T)_jj = || x_i - x_j ||^2 ;
- * for all (i, j) nearest neighbors
- *
- * Now, our optimization problem is easier. The total number of constraints is
- * equal to the number of points multiplied by the number of nearest neighbors.
- */
-class MVUObjectiveFunction
-{
- public:
- MVUObjectiveFunction();
- MVUObjectiveFunction(const arma::mat& initial_point,
- const size_t newDim,
- const size_t numNeighbors);
-
- double Evaluate(const arma::mat& coordinates);
- void Gradient(const arma::mat& coordinates, arma::mat& gradient);
-
- size_t NumConstraints() const { return numNeighbors * initialPoint.n_cols; }
-
- double EvaluateConstraint(const size_t index, const arma::mat& coordinates);
- void GradientConstraint(const size_t index,
- const arma::mat& coordinates,
- arma::mat& gradient);
-
- const arma::mat& GetInitialPoint() const { return initialPoint; }
-
- private:
- arma::mat initialPoint;
- size_t numNeighbors;
-
- // These hold the output of the nearest neighbors computation (done in the
- // constructor).
- arma::Mat<size_t> neighborIndices;
- arma::mat neighborDistances;
-};
-
-}; // namespace mvu
-}; // namespace mlpack
-
-#endif
More information about the mlpack-svn
mailing list