[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