[mlpack-svn] r16764 - in mlpack/trunk/src/mlpack: methods/amf/termination_policies methods/amf/update_rules tests
fastlab-svn at coffeetalk-1.cc.gatech.edu
fastlab-svn at coffeetalk-1.cc.gatech.edu
Sun Jul 6 09:40:31 EDT 2014
Author: sumedhghaisas
Date: Sun Jul 6 09:40:30 2014
New Revision: 16764
Log:
* modified termination policies
* fast SVDBatch implementation
Added:
mlpack/trunk/src/mlpack/tests/svd_test.cpp
Modified:
mlpack/trunk/src/mlpack/methods/amf/termination_policies/simple_tolerance_termination.hpp
mlpack/trunk/src/mlpack/methods/amf/termination_policies/validation_RMSE_termination.hpp
mlpack/trunk/src/mlpack/methods/amf/update_rules/svd_batchlearning.hpp
mlpack/trunk/src/mlpack/tests/CMakeLists.txt
Modified: mlpack/trunk/src/mlpack/methods/amf/termination_policies/simple_tolerance_termination.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/methods/amf/termination_policies/simple_tolerance_termination.hpp (original)
+++ mlpack/trunk/src/mlpack/methods/amf/termination_policies/simple_tolerance_termination.hpp Sun Jul 6 09:40:30 2014
@@ -15,8 +15,11 @@
{
public:
SimpleToleranceTermination(const double tolerance = 1e-5,
- const size_t maxIterations = 10000)
- : tolerance(tolerance), maxIterations(maxIterations) {}
+ const size_t maxIterations = 10000,
+ const size_t reverseStepTolerance = 3)
+ : tolerance(tolerance),
+ maxIterations(maxIterations),
+ reverseStepTolerance(reverseStepTolerance) {}
void Initialize(const MatType& V)
{
@@ -29,8 +32,12 @@
bool IsConverged()
{
- if(((residueOld - residue) / residueOld < tolerance && iteration > 4)
- || iteration > maxIterations) return true;
+ if((residueOld - residue) / residueOld < tolerance && iteration > 4)
+ reverseStepCount++;
+ else reverseStepCount = 0;
+
+ if(reverseStepCount == reverseStepTolerance || iteration > maxIterations)
+ return true;
else return false;
}
@@ -48,17 +55,17 @@
size_t count = 0;
for(size_t i = 0;i < n;i++)
{
- for(size_t j = 0;j < m;j++)
- {
- double temp = 0;
- if((temp = (*V)(i,j)) != 0)
+ for(size_t j = 0;j < m;j++)
{
- temp = (temp - WH(i, j));
- temp = temp * temp;
- sum += temp;
- count++;
+ double temp = 0;
+ if((temp = (*V)(i,j)) != 0)
+ {
+ temp = (temp - WH(i, j));
+ temp = temp * temp;
+ sum += temp;
+ count++;
+ }
}
- }
}
residue = sum / count;
residue = sqrt(residue);
@@ -79,6 +86,9 @@
double residueOld;
double residue;
double normOld;
+
+ size_t reverseStepTolerance;
+ size_t reverseStepCount;
}; // class SimpleToleranceTermination
}; // namespace amf
Modified: mlpack/trunk/src/mlpack/methods/amf/termination_policies/validation_RMSE_termination.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/methods/amf/termination_policies/validation_RMSE_termination.hpp (original)
+++ mlpack/trunk/src/mlpack/methods/amf/termination_policies/validation_RMSE_termination.hpp Sun Jul 6 09:40:30 2014
@@ -14,10 +14,12 @@
ValidationRMSETermination(MatType& V,
size_t num_test_points,
double tolerance = 1e-5,
- size_t maxIterations = 10000)
+ size_t maxIterations = 10000,
+ size_t reverseStepTolerance = 3)
: tolerance(tolerance),
maxIterations(maxIterations),
- num_test_points(num_test_points)
+ num_test_points(num_test_points),
+ reverseStepTolerance(reverseStepTolerance)
{
size_t n = V.n_rows;
size_t m = V.n_cols;
@@ -44,19 +46,22 @@
void Initialize(const MatType& V)
{
+ (void)V;
iteration = 1;
rmse = DBL_MAX;
rmseOld = DBL_MAX;
- t_count = 0;
+ reverseStepCount = 0;
}
bool IsConverged()
{
- if((rmseOld - rmse) / rmseOld < tolerance && iteration > 4) t_count++;
- else t_count = 0;
+ if((rmseOld - rmse) / rmseOld < tolerance && iteration > 4)
+ reverseStepCount++;
+ else reverseStepCount = 0;
- if(t_count == 3 || iteration > maxIterations) return true;
+ if(reverseStepCount == reverseStepTolerance || iteration > maxIterations)
+ return true;
else return false;
}
@@ -108,7 +113,8 @@
double rmseOld;
double rmse;
- size_t t_count;
+ size_t reverseStepTolerance;
+ size_t reverseStepCount;
};
} // namespace amf
Modified: mlpack/trunk/src/mlpack/methods/amf/update_rules/svd_batchlearning.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/methods/amf/update_rules/svd_batchlearning.hpp (original)
+++ mlpack/trunk/src/mlpack/methods/amf/update_rules/svd_batchlearning.hpp Sun Jul 6 09:40:30 2014
@@ -17,7 +17,7 @@
SVDBatchLearning(double u = 0.0002,
double kw = 0,
double kh = 0,
- double momentum = 0.5,
+ double momentum = 0.9,
double min = -DBL_MIN,
double max = DBL_MAX)
: u(u), kw(kw), kh(kh), min(min), max(max), momentum(momentum)
@@ -48,6 +48,7 @@
const arma::mat& H)
{
size_t n = V.n_rows;
+ size_t m = V.n_cols;
size_t r = W.n_cols;
@@ -56,17 +57,16 @@
arma::mat deltaW(n, r);
deltaW.zeros();
- for(typename MatType::const_iterator it = V.begin();it != V.end();it++)
+ for(size_t i = 0;i < n;i++)
{
- size_t row = it.row();
- size_t col = it.col();
- deltaW.row(it.row()) += (*it - arma::dot(W.row(row), H.col(col))) *
- arma::trans(H.col(col));
- }
-
- if(kw != 0) for(size_t i = 0; i < n; i++)
- {
- deltaW.row(i) -= kw * W.row(i);
+ for(size_t j = 0;j < m;j++)
+ {
+ double val;
+ if((val = V(i, j)) != 0)
+ deltaW.row(i) += (val - arma::dot(W.row(i), H.col(j))) *
+ arma::trans(H.col(j));
+ }
+ if(kw != 0) deltaW.row(i) -= kw * W.row(i);
}
mW += u * deltaW;
@@ -87,6 +87,7 @@
const arma::mat& W,
arma::mat& H)
{
+ size_t n = V.n_rows;
size_t m = V.n_cols;
size_t r = W.n_cols;
@@ -96,17 +97,16 @@
arma::mat deltaH(r, m);
deltaH.zeros();
- for(typename MatType::const_iterator it = V.begin();it != V.end();it++)
+ for(size_t j = 0;j < m;j++)
{
- size_t row = it.row();
- size_t col = it.col();
- deltaH.col(col) += (*it - arma::dot(W.row(row), H.col(col))) *
- arma::trans(W.row(row));
- }
-
- if(kh != 0) for(size_t j = 0; j < m; j++)
- {
- deltaH.col(j) -= kh * H.col(j);
+ for(size_t i = 0;i < n;i++)
+ {
+ double val;
+ if((val = V(i, j)) != 0)
+ deltaH.col(j) += (val - arma::dot(W.row(i), H.col(j))) *
+ arma::trans(W.row(i));
+ }
+ if(kh != 0) deltaH.col(j) -= kh * H.col(j);
}
mH += u*deltaH;
@@ -114,13 +114,6 @@
}
private:
- double Predict(const arma::mat& wi, const arma::mat& hj) const
- {
- arma::mat temp = (wi * hj);
- double out = temp(0,0);
- return out;
- }
-
double u;
double kw;
double kh;
@@ -131,6 +124,67 @@
arma::mat mW;
arma::mat mH;
};
+
+template<>
+inline void SVDBatchLearning::WUpdate<arma::sp_mat>(const arma::sp_mat& V,
+ arma::mat& W,
+ const arma::mat& H)
+{
+ size_t n = V.n_rows;
+
+ size_t r = W.n_cols;
+
+ mW = momentum * mW;
+
+ arma::mat deltaW(n, r);
+ deltaW.zeros();
+
+ for(arma::sp_mat::const_iterator it = V.begin();it != V.end();it++)
+ {
+ size_t row = it.row();
+ size_t col = it.col();
+ deltaW.row(it.row()) += (*it - arma::dot(W.row(row), H.col(col))) * arma::trans(H.col(col));
+ }
+
+ if(kw != 0) for(size_t i = 0; i < n; i++)
+ {
+ deltaW.row(i) -= kw * W.row(i);
+ }
+
+ mW += u * deltaW;
+ W += mW;
+}
+
+template<>
+inline void SVDBatchLearning::HUpdate<arma::sp_mat>(const arma::sp_mat& V,
+ const arma::mat& W,
+ arma::mat& H)
+{
+ size_t m = V.n_cols;
+
+ size_t r = W.n_cols;
+
+ mH = momentum * mH;
+
+ arma::mat deltaH(r, m);
+ deltaH.zeros();
+
+ for(arma::sp_mat::const_iterator it = V.begin();it != V.end();it++)
+ {
+ size_t row = it.row();
+ size_t col = it.col();
+ deltaH.col(col) += (*it - arma::dot(W.row(row), H.col(col))) * arma::trans(W.row(row));
+ }
+
+ if(kh != 0) for(size_t j = 0; j < m; j++)
+ {
+ deltaH.col(j) -= kh * H.col(j);
+ }
+
+ mH += u*deltaH;
+ H += mH;
+}
+
} // namespace amf
} // namespace mlpack
Modified: mlpack/trunk/src/mlpack/tests/CMakeLists.txt
==============================================================================
--- mlpack/trunk/src/mlpack/tests/CMakeLists.txt (original)
+++ mlpack/trunk/src/mlpack/tests/CMakeLists.txt Sun Jul 6 09:40:30 2014
@@ -50,6 +50,7 @@
tree_test.cpp
tree_traits_test.cpp
union_find_test.cpp
+ svd_test.cpp
)
# Link dependencies of test executable.
target_link_libraries(mlpack_test
Added: mlpack/trunk/src/mlpack/tests/svd_test.cpp
==============================================================================
--- (empty file)
+++ mlpack/trunk/src/mlpack/tests/svd_test.cpp Sun Jul 6 09:40:30 2014
@@ -0,0 +1,156 @@
+#include <mlpack/core.hpp>
+#include <mlpack/methods/amf/amf.hpp>
+#include <mlpack/methods/amf/update_rules/svd_batchlearning.hpp>
+#include <mlpack/methods/amf/init_rules/random_init.hpp>
+#include <mlpack/methods/amf/termination_policies/validation_RMSE_termination.hpp>
+#include <mlpack/methods/amf/termination_policies/simple_tolerance_termination.hpp>
+
+#include <boost/test/unit_test.hpp>
+#include "old_boost_test_definitions.hpp"
+
+BOOST_AUTO_TEST_SUITE(SVDBatchTest);
+
+using namespace std;
+using namespace mlpack;
+using namespace mlpack::amf;
+using namespace arma;
+
+/**
+ * Make sure the momentum is working okay.
+ */
+BOOST_AUTO_TEST_CASE(SVDMomentumTest)
+{
+ mat dataset;
+ data::Load("GroupLens100k.csv", dataset);
+
+ // Generate list of locations for batch insert constructor for sparse
+ // matrices.
+ arma::umat locations(2, dataset.n_cols);
+ arma::vec values(dataset.n_cols);
+ for (size_t i = 0; i < dataset.n_cols; ++i)
+ {
+ // We have to transpose it because items are rows, and users are columns.
+ locations(0, i) = ((arma::uword) dataset(0, i));
+ locations(1, i) = ((arma::uword) dataset(1, i));
+ values(i) = dataset(2, i);
+ }
+
+ // Find maximum user and item IDs.
+ const size_t maxUserID = (size_t) max(locations.row(0)) + 1;
+ const size_t maxItemID = (size_t) max(locations.row(1)) + 1;
+
+ // Fill sparse matrix.
+ sp_mat cleanedData = arma::sp_mat(locations, values, maxUserID, maxItemID);
+
+ math::RandomSeed(10);
+ ValidationRMSETermination<sp_mat> vrt(cleanedData, 2000);
+ AMF<ValidationRMSETermination<sp_mat>,
+ RandomInitialization,
+ SVDBatchLearning> amf_1(vrt,
+ RandomInitialization(),
+ SVDBatchLearning(0.0009, 0, 0, 0));
+
+ mat m1,m2;
+ size_t RMSE_1 = amf_1.Apply(cleanedData, 2, m1, m2);
+ size_t iter_1 = amf_1.TPolicy().Iteration();
+
+ math::RandomSeed(10);
+ AMF<ValidationRMSETermination<sp_mat>,
+ RandomInitialization,
+ SVDBatchLearning> amf_2(vrt,
+ RandomInitialization(),
+ SVDBatchLearning(0.0009, 0, 0, 0.8));
+
+ size_t RMSE_2 = amf_2.Apply(cleanedData, 2, m1, m2);
+ size_t iter_2 = amf_2.TPolicy().Iteration();
+
+ BOOST_REQUIRE_LE(RMSE_2, RMSE_1);
+ BOOST_REQUIRE_LE(iter_2, iter_1);
+}
+
+/**
+ * Make sure the regularization is working okay.
+ */
+BOOST_AUTO_TEST_CASE(SVDRegularizationTest)
+{
+ mat dataset;
+ data::Load("GroupLens100k.csv", dataset);
+
+ // Generate list of locations for batch insert constructor for sparse
+ // matrices.
+ arma::umat locations(2, dataset.n_cols);
+ arma::vec values(dataset.n_cols);
+ for (size_t i = 0; i < dataset.n_cols; ++i)
+ {
+ // We have to transpose it because items are rows, and users are columns.
+ locations(0, i) = ((arma::uword) dataset(0, i));
+ locations(1, i) = ((arma::uword) dataset(1, i));
+ values(i) = dataset(2, i);
+ }
+
+ // Find maximum user and item IDs.
+ const size_t maxUserID = (size_t) max(locations.row(0)) + 1;
+ const size_t maxItemID = (size_t) max(locations.row(1)) + 1;
+
+ // Fill sparse matrix.
+ sp_mat cleanedData = arma::sp_mat(locations, values, maxUserID, maxItemID);
+
+ math::RandomSeed(10);
+ ValidationRMSETermination<sp_mat> vrt(cleanedData, 2000);
+ AMF<ValidationRMSETermination<sp_mat>,
+ RandomInitialization,
+ SVDBatchLearning> amf_1(vrt,
+ RandomInitialization(),
+ SVDBatchLearning(0.0009, 0, 0, 0));
+
+ mat m1,m2;
+ size_t RMSE_1 = amf_1.Apply(cleanedData, 2, m1, m2);
+
+ math::RandomSeed(10);
+ AMF<ValidationRMSETermination<sp_mat>,
+ RandomInitialization,
+ SVDBatchLearning> amf_2(vrt,
+ RandomInitialization(),
+ SVDBatchLearning(0.0009, 0.5, 0.5, 0.8));
+
+ size_t RMSE_2 = amf_2.Apply(cleanedData, 2, m1, m2);
+
+ BOOST_REQUIRE_LE(RMSE_2, RMSE_1);
+}
+
+/**
+ * Make sure the SVD can factorize matrices with negative entries.
+ */
+BOOST_AUTO_TEST_CASE(SVDNegativeElementTest)
+{
+ mat test;
+ test.zeros(3,3);
+ test(0, 0) = 1;
+ test(0, 1) = -2;
+ test(0, 2) = 3;
+ test(1, 0) = 2;
+ test(1, 1) = -1;
+ test(1, 2) = 1;
+ test(2, 0) = 2;
+ test(2, 1) = 2;
+ test(2, 2) = 2;
+
+ AMF<SimpleToleranceTermination<mat>,
+ RandomInitialization,
+ SVDBatchLearning> amf(SimpleToleranceTermination<mat>(),
+ RandomInitialization(),
+ SVDBatchLearning(0.3, 0.001, 0.001, 0));
+ mat m1, m2;
+ amf.Apply(test, 2, m1, m2);
+
+ arma::mat result = m1 * m2;
+ for(size_t i = 0;i < 3;i++)
+ {
+ for(size_t j = 0;j < 3;j++)
+ {
+ BOOST_REQUIRE_LE(abs(test(i,j) - result(i,j)), 0.5);
+ }
+ }
+}
+
+BOOST_AUTO_TEST_SUITE_END();
More information about the mlpack-svn
mailing list