[mlpack-git] master: add a comment on why the MVU test fails (e14826d)
gitdub at big.cc.gt.atl.ga.us
gitdub at big.cc.gt.atl.ga.us
Mon Feb 2 15:16:10 EST 2015
Repository : https://github.com/mlpack/mlpack
On branch : master
Link : https://github.com/mlpack/mlpack/compare/bb6e5c56aab07e6449d86021246b52a9e323f3a0...bd6cb33f8d8270b02a84e81e38727679bb6c319a
>---------------------------------------------------------------
commit e14826d96c28528dac8c5b9cbb1d6902dc40579c
Author: Stephen Tu <tu.stephenl at gmail.com>
Date: Fri Jan 16 12:47:07 2015 -0800
add a comment on why the MVU test fails
>---------------------------------------------------------------
e14826d96c28528dac8c5b9cbb1d6902dc40579c
src/mlpack/core/optimizers/sdp/primal_dual.cpp | 4 +-
src/mlpack/core/optimizers/sdp/sdp.cpp | 26 ++++++++
src/mlpack/core/optimizers/sdp/sdp.hpp | 7 ++
src/mlpack/tests/sdp_primal_dual_test.cpp | 91 ++++++++++++++++++++++++++
4 files changed, 127 insertions(+), 1 deletion(-)
diff --git a/src/mlpack/core/optimizers/sdp/primal_dual.cpp b/src/mlpack/core/optimizers/sdp/primal_dual.cpp
index f3b391c..32ba4f4 100644
--- a/src/mlpack/core/optimizers/sdp/primal_dual.cpp
+++ b/src/mlpack/core/optimizers/sdp/primal_dual.cpp
@@ -268,7 +268,9 @@ PrimalDualSolver::Optimize(arma::mat& X,
//std::cout << "rhs" << std::endl;
//std::cout << rhs << std::endl;
- arma::solve(dy, M, rhs);
+ if (!arma::solve(dy, M, rhs))
+ Log::Fatal << "PrimalDualSolver::Optimize(): Could not solve KKT system" << std::endl;
+
if (sdp.NumSparseConstraints())
dysparse = dy(arma::span(0, sdp.NumSparseConstraints() - 1));
if (sdp.NumDenseConstraints())
diff --git a/src/mlpack/core/optimizers/sdp/sdp.cpp b/src/mlpack/core/optimizers/sdp/sdp.cpp
index e4a2dbd..984ea7e 100644
--- a/src/mlpack/core/optimizers/sdp/sdp.cpp
+++ b/src/mlpack/core/optimizers/sdp/sdp.cpp
@@ -25,5 +25,31 @@ SDP::SDP(const size_t n,
denseC.zeros();
}
+bool SDP::HasLinearlyIndependentConstraints() const
+{
+ // Very inefficient, should only be used for testing/debugging
+
+ const size_t n2bar = N2bar();
+ arma::mat A(NumConstraints(), n2bar);
+ if (A.n_rows > n2bar)
+ return false;
+
+ for (size_t i = 0; i < NumSparseConstraints(); i++)
+ {
+ arma::vec sa;
+ math::Svec(arma::mat(SparseA()[i]), sa);
+ A.row(i) = sa.t();
+ }
+ for (size_t i = 0; i < NumDenseConstraints(); i++)
+ {
+ arma::vec sa;
+ math::Svec(DenseA()[i], sa);
+ A.row(NumSparseConstraints() + i) = sa.t();
+ }
+
+ const arma::vec s = arma::svd(A);
+ return s(s.n_elem - 1) > 1e-5;
+}
+
} // namespace optimization
} // namespace mlpack
diff --git a/src/mlpack/core/optimizers/sdp/sdp.hpp b/src/mlpack/core/optimizers/sdp/sdp.hpp
index 83c2002..4d57dab 100644
--- a/src/mlpack/core/optimizers/sdp/sdp.hpp
+++ b/src/mlpack/core/optimizers/sdp/sdp.hpp
@@ -80,6 +80,13 @@ class SDP
bool HasDenseObjective() const { return hasModifiedDenseObjective; }
+ /**
+ * Check whether or not the constraint matrices are linearly independent.
+ *
+ * Warning: possibly very expensive check
+ */
+ bool HasLinearlyIndependentConstraints() const;
+
private:
//! Dimension of the objective variable.
diff --git a/src/mlpack/tests/sdp_primal_dual_test.cpp b/src/mlpack/tests/sdp_primal_dual_test.cpp
index c4d7d3e..dda0166 100644
--- a/src/mlpack/tests/sdp_primal_dual_test.cpp
+++ b/src/mlpack/tests/sdp_primal_dual_test.cpp
@@ -6,12 +6,15 @@
#include <mlpack/core.hpp>
#include <mlpack/core/optimizers/sdp/sdp.hpp>
#include <mlpack/core/optimizers/sdp/primal_dual.hpp>
+#include <mlpack/methods/neighbor_search/neighbor_search.hpp>
#include <boost/test/unit_test.hpp>
#include "old_boost_test_definitions.hpp"
using namespace mlpack;
using namespace mlpack::optimization;
+using namespace mlpack::distribution;
+using namespace mlpack::neighbor;
class UndirectedGraph
{
@@ -388,4 +391,92 @@ BOOST_AUTO_TEST_CASE(LogChebychevApproxSdp)
BOOST_REQUIRE(stat1.first);
}
+/**
+ * Maximum variance unfolding (MVU) SDP to learn the unrolled gram matrix. For
+ * the SDP formulation, see:
+ *
+ * Unsupervised learning of image manifolds by semidefinite programming.
+ * Kilian Weinberger and Lawrence Saul. CVPR 04.
+ * http://repository.upenn.edu/cgi/viewcontent.cgi?article=1000&context=cis_papers
+ *
+ * @param origData origDim x numPoints
+ * @param numNeighbors
+ */
+static inline SDP ConstructMvuSDP(const arma::mat& origData,
+ size_t numNeighbors)
+{
+ const size_t numPoints = origData.n_cols;
+
+ assert(numNeighbors <= numPoints);
+
+ arma::Mat<size_t> neighbors;
+ arma::mat distances;
+ AllkNN allknn(origData);
+ allknn.Search(numNeighbors, neighbors, distances);
+
+ SDP sdp(numPoints, numNeighbors * numPoints, 1);
+ sdp.SparseC().eye(numPoints, numPoints);
+ sdp.SparseC() *= -1;
+ sdp.DenseA()[0].ones(numPoints, numPoints);
+ sdp.DenseB()[0] = 0;
+
+ for (size_t i = 0; i < neighbors.n_cols; ++i)
+ {
+ for (size_t j = 0; j < numNeighbors; ++j)
+ {
+ // This is the index of the constraint.
+ const size_t index = (i * numNeighbors) + j;
+
+ arma::sp_mat& aRef = sdp.SparseA()[index];
+ aRef.zeros(numPoints, numPoints);
+
+ // A_ij(i, i) = 1.
+ aRef(i, i) = 1;
+
+ // A_ij(i, j) = -1.
+ aRef(i, neighbors(j, i)) = -1;
+
+ // A_ij(j, i) = -1.
+ aRef(neighbors(j, i), i) = -1;
+
+ // A_ij(j, j) = 1.
+ aRef(neighbors(j, i), neighbors(j, i)) = 1;
+
+ // The constraint b_ij is the distance between these two points.
+ sdp.SparseB()[index] = distances(j, i);
+ }
+ }
+
+ return sdp;
+}
+
+/**
+ * Maximum variance unfolding
+ *
+ * Test doesn't work, because the constraint matrices are not linearly
+ * independent.
+ */
+BOOST_AUTO_TEST_CASE(SmallMvuSdp)
+{
+ const size_t n = 20;
+
+ arma::mat origData(3, n);
+
+ // sample n random points on 3-dim unit sphere
+ GaussianDistribution gauss(3);
+ for (size_t i = 0; i < n; i++)
+ {
+ // how european of them
+ origData.col(i) = arma::normalise(gauss.Random());
+ }
+
+ SDP sdp = ConstructMvuSDP(origData, 5);
+
+ PrimalDualSolver solver(sdp);
+ arma::mat X, Z;
+ arma::vec ysparse, ydense;
+ const auto p = solver.Optimize(X, ysparse, ydense, Z);
+ BOOST_REQUIRE(p.first);
+}
+
BOOST_AUTO_TEST_SUITE_END();
More information about the mlpack-git
mailing list