You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mahout.apache.org by td...@apache.org on 2012/01/16 01:01:39 UTC

svn commit: r1231800 - in /mahout/trunk/core/src: main/java/org/apache/mahout/math/ssvd/SequentialOutOfCoreSvd.java test/java/org/apache/mahout/math/ssvd/SequentialOutOfCoreSvdTest.java

Author: tdunning
Date: Mon Jan 16 00:01:38 2012
New Revision: 1231800

URL: http://svn.apache.org/viewvc?rev=1231800&view=rev
Log:
MAHOUT-792 - Forced correct block ordering in out-of-core SVD.  Hopefully addresses ubuntu test failures.  Also forced file closing.

Modified:
    mahout/trunk/core/src/main/java/org/apache/mahout/math/ssvd/SequentialOutOfCoreSvd.java
    mahout/trunk/core/src/test/java/org/apache/mahout/math/ssvd/SequentialOutOfCoreSvdTest.java

Modified: mahout/trunk/core/src/main/java/org/apache/mahout/math/ssvd/SequentialOutOfCoreSvd.java
URL: http://svn.apache.org/viewvc/mahout/trunk/core/src/main/java/org/apache/mahout/math/ssvd/SequentialOutOfCoreSvd.java?rev=1231800&r1=1231799&r2=1231800&view=diff
==============================================================================
--- mahout/trunk/core/src/main/java/org/apache/mahout/math/ssvd/SequentialOutOfCoreSvd.java (original)
+++ mahout/trunk/core/src/main/java/org/apache/mahout/math/ssvd/SequentialOutOfCoreSvd.java Mon Jan 16 00:01:38 2012
@@ -54,7 +54,8 @@ import java.io.IOException;
  * <p/>
  * R' R = \sum_i Y_i' Y_i
  * <p/>
- * For reference, R is all we need to compute explicitly.  Q will be computed on the fly when needed.
+ * For reference, R is all we need to compute explicitly.  Q will be computed on the fly when
+ * needed.
  * <p/>
  * Q = Y R^-1
  * <p/>
@@ -93,7 +94,7 @@ public class SequentialOutOfCoreSvd {
   private final int seed;
   private final int dim;
 
-  public SequentialOutOfCoreSvd(Iterable<File> partsOfA, String uBase, String vBase, File tmpDir, int internalDimension, int columnsPerSlice) throws IOException {
+  public SequentialOutOfCoreSvd(Iterable<File> partsOfA, File tmpDir, int internalDimension, int columnsPerSlice) throws IOException {
     this.columnsPerSlice = columnsPerSlice;
     this.dim = internalDimension;
 
@@ -126,7 +127,12 @@ public class SequentialOutOfCoreSvd {
     int ncols = 0;
     for (File file : partsOfA) {
       MatrixWritable m = new MatrixWritable();
-      m.readFields(new DataInputStream(new FileInputStream(file)));
+      final DataInputStream in = new DataInputStream(new FileInputStream(file));
+      try {
+        m.readFields(in);
+      } finally {
+        in.close();
+      }
       Matrix aI = m.get();
       ncols = Math.max(ncols, aI.columnSize());
 
@@ -144,7 +150,13 @@ public class SequentialOutOfCoreSvd {
     MatrixWritable bTmp = new MatrixWritable();
     for (int j = 0; j < ncols; j += columnsPerSlice) {
       if (bFile(tmpDir, j).exists()) {
-        bTmp.readFields(new DataInputStream(new FileInputStream(bFile(tmpDir, j))));
+        final DataInputStream in = new DataInputStream(new FileInputStream(bFile(tmpDir, j)));
+        try {
+          bTmp.readFields(in);
+        } finally {
+          in.close();
+        }
+
         b2.assign(bTmp.get().times(bTmp.get().transpose()), Functions.PLUS);
       }
     }
@@ -152,34 +164,44 @@ public class SequentialOutOfCoreSvd {
     svd = new SingularValueDecomposition(l2.getL());
   }
 
-  public void computeV(File tmpDir, String vBase, int ncols) throws IOException {
+  public void computeV(File tmpDir, int ncols) throws IOException {
     // step 5, compute pieces of V
-    if (vBase != null) {
-      for (int j = 0; j < ncols; j += columnsPerSlice) {
-        if (bFile(tmpDir, j).exists()) {
-          MatrixWritable m = new MatrixWritable();
-          m.readFields(new DataInputStream(new FileInputStream(bFile(tmpDir, j))));
-          m.set(l2.solveRight(m.get().transpose()).times(svd.getV()));
-          m.write(new DataOutputStream(new FileOutputStream(new File(tmpDir, vBase + j / columnsPerSlice))));
+    for (int j = 0; j < ncols; j += columnsPerSlice) {
+      final File bPath = bFile(tmpDir, j);
+      if (bPath.exists()) {
+        MatrixWritable m = new MatrixWritable();
+        final DataInputStream in = new DataInputStream(new FileInputStream(bPath));
+        try {
+          m.readFields(in);
+        } finally {
+          in.close();
+        }
+        m.set(l2.solveRight(m.get().transpose()).times(svd.getV()));
+        final DataOutputStream out = new DataOutputStream(new FileOutputStream(new File(tmpDir, String.format("V-%s", bPath.getName().replaceAll(".*-", "")))));
+        try {
+          m.write(out);
+        } finally {
+          out.close();
         }
       }
     }
   }
 
-  public void computeU(Iterable<File> partsOfA, String uBase, File tmpDir) throws IOException {
+  public void computeU(Iterable<File> partsOfA, File tmpDir) throws IOException {
     // step 4, compute pieces of U
-    if (uBase != null) {
-      int i = 0;
-      for (File file : partsOfA) {
-        MatrixWritable m = new MatrixWritable();
-        m.readFields(new DataInputStream(new FileInputStream(file)));
-        Matrix aI = m.get();
+    for (File file : partsOfA) {
+      MatrixWritable m = new MatrixWritable();
+      m.readFields(new DataInputStream(new FileInputStream(file)));
+      Matrix aI = m.get();
 
-        Matrix y = aI.times(new RandomTrinaryMatrix(seed, aI.numCols(), dim, false));
-        Matrix uI = r2.solveRight(y).times(svd.getU());
-        m.set(uI);
-        m.write(new DataOutputStream(new FileOutputStream(new File(tmpDir, uBase + i))));
-        i += aI.rowSize();
+      Matrix y = aI.times(new RandomTrinaryMatrix(seed, aI.numCols(), dim, false));
+      Matrix uI = r2.solveRight(y).times(svd.getU());
+      m.set(uI);
+      final DataOutputStream out = new DataOutputStream(new FileOutputStream(new File(tmpDir, String.format("U-%s", file.getName().replaceAll(".*-", "")))));
+      try {
+        m.write(out);
+      } finally {
+        out.close();
       }
     }
   }

Modified: mahout/trunk/core/src/test/java/org/apache/mahout/math/ssvd/SequentialOutOfCoreSvdTest.java
URL: http://svn.apache.org/viewvc/mahout/trunk/core/src/test/java/org/apache/mahout/math/ssvd/SequentialOutOfCoreSvdTest.java?rev=1231800&r1=1231799&r2=1231800&view=diff
==============================================================================
--- mahout/trunk/core/src/test/java/org/apache/mahout/math/ssvd/SequentialOutOfCoreSvdTest.java (original)
+++ mahout/trunk/core/src/test/java/org/apache/mahout/math/ssvd/SequentialOutOfCoreSvdTest.java Mon Jan 16 00:01:38 2012
@@ -17,6 +17,7 @@
 
 package org.apache.mahout.math.ssvd;
 
+import com.google.common.collect.Lists;
 import org.apache.mahout.common.MahoutTestCase;
 import org.apache.mahout.math.DenseMatrix;
 import org.apache.mahout.math.DenseVector;
@@ -24,6 +25,7 @@ import org.apache.mahout.math.DiagonalMa
 import org.apache.mahout.math.Matrix;
 import org.apache.mahout.math.MatrixWritable;
 import org.apache.mahout.math.RandomTrinaryMatrix;
+import org.apache.mahout.math.SingularValueDecomposition;
 import org.apache.mahout.math.Vector;
 import org.apache.mahout.math.function.Functions;
 import org.junit.Before;
@@ -61,14 +63,17 @@ public final class SequentialOutOfCoreSv
         return fileName.matches("A-.*");
       }
     }));
-    SequentialOutOfCoreSvd s = new SequentialOutOfCoreSvd(partsOfA, "U", "V", tmpDir, 100, 210);
+
+    // rearrange A to make sure we don't depend on lexical ordering.
+    partsOfA = Lists.reverse(partsOfA);
+    SequentialOutOfCoreSvd s = new SequentialOutOfCoreSvd(partsOfA, tmpDir, 100, 210);
     SequentialBigSvd svd = new SequentialBigSvd(A, 100);
 
     Vector reference = new DenseVector(svd.getSingularValues()).viewPart(0, 6);
     Vector actual = s.getSingularValues().viewPart(0, 6);
     assertEquals(0, reference.minus(actual).maxValue(), 1.0e-9);
 
-    s.computeU(partsOfA, "U-", tmpDir);
+    s.computeU(partsOfA, tmpDir);
     Matrix u = readBlockMatrix(Arrays.asList(tmpDir.listFiles(new FilenameFilter() {
       @Override
       public boolean accept(File file, String fileName) {
@@ -76,7 +81,7 @@ public final class SequentialOutOfCoreSv
       }
     })));
 
-    s.computeV(tmpDir, "V-", A.columnSize());
+    s.computeV(tmpDir, A.columnSize());
     Matrix v = readBlockMatrix(Arrays.asList(tmpDir.listFiles(new FilenameFilter() {
       @Override
       public boolean accept(File file, String fileName) {
@@ -88,8 +93,20 @@ public final class SequentialOutOfCoreSv
     assertEquals(0, A.minus(u.times(new DiagonalMatrix(s.getSingularValues())).times(v.transpose())).aggregate(Functions.PLUS, Functions.ABS), 1.0e-7);
   }
 
+  /**
+   * Reads a list of files that contain a column of blocks.  It is assumed that the files
+   * can be sorted lexicographically to determine the order they should be stacked.  It
+   * is also assumed here that all blocks will be the same size except the last one which
+   * may be shorter than the others.
+   * @param files  The list of files to read.
+   * @return  The row-wise concatenation of the matrices in the files.
+   * @throws IOException If we can't read the sub-matrices.
+   */
   private static Matrix readBlockMatrix(List<File> files) throws IOException {
+    // force correct ordering
     Collections.sort(files);
+
+    // initially, we don't know what size buffer to hold
     int nrows = -1;
     int ncols = -1;
     Matrix r = null;
@@ -102,6 +119,7 @@ public final class SequentialOutOfCoreSv
       m.readFields(in);
       in.close();
       if (nrows == -1) {
+        // now we can set an upper bound on how large our result will be
         nrows = m.get().rowSize() * files.size();
         ncols = m.get().columnSize();
         r = new DenseMatrix(nrows, ncols);
@@ -109,44 +127,46 @@ public final class SequentialOutOfCoreSv
       r.viewPart(row, m.get().rowSize(), 0, r.columnSize()).assign(m.get());
       row += m.get().rowSize();
     }
+    // at the end, row will have the true size of the result
     if (row != nrows && r != null) {
+      // and if that isn't the size of the buffer, we need to crop the result a bit
       r = r.viewPart(0, row, 0, ncols);
     }
     return r;
   }
 
-//  @Test
-//  public void testLeftVectors() {
-//    Matrix A = lowRankMatrix();
-//
-//    SequentialBigSvd s = new SequentialBigSvd(A, 6);
-//    SingularValueDecomposition svd = new SingularValueDecomposition(A);
-//
-//    // can only check first few singular vectors
-//    Matrix u1 = svd.getU().viewPart(0, 20, 0, 3).assign(Functions.ABS);
-//    Matrix u2 = s.getU().viewPart(0, 20, 0, 3).assign(Functions.ABS);
-//    assertEquals(u1, u2);
-//  }
-//
-//  private void assertEquals(Matrix u1, Matrix u2) {
-//    assertEquals(0.0, u1.minus(u2).aggregate(Functions.MAX, Functions.ABS), 1e-10);
-//  }
-//
-//  private void assertEquals(Vector u1, Vector u2) {
-//    assertEquals(0.0, u1.minus(u2).aggregate(Functions.MAX, Functions.ABS), 1e-10);
-//  }
-//
-//  @Test
-//  public void testRightVectors() {
-//    Matrix A = lowRankMatrix();
-//
-//    SequentialBigSvd s = new SequentialBigSvd(A, 6);
-//    SingularValueDecomposition svd = new SingularValueDecomposition(A);
-//
-//    Matrix v1 = svd.getV().viewPart(0, 20, 0, 3).assign(Functions.ABS);
-//    Matrix v2 = s.getV().viewPart(0, 20, 0, 3).assign(Functions.ABS);
-//    assertEquals(v1, v2);
-//  }
+  @Test
+  public void testLeftVectors() throws IOException {
+    Matrix A = lowRankMatrixInMemory(20, 20);
+
+    SequentialBigSvd s = new SequentialBigSvd(A, 6);
+    SingularValueDecomposition svd = new SingularValueDecomposition(A);
+
+    // can only check first few singular vectors
+    Matrix u1 = svd.getU().viewPart(0, 20, 0, 3).assign(Functions.ABS);
+    Matrix u2 = s.getU().viewPart(0, 20, 0, 3).assign(Functions.ABS);
+    assertEquals(u1, u2);
+  }
+
+  private Matrix lowRankMatrixInMemory(int rows, int columns) throws IOException {
+    return lowRankMatrix(null, null, 0, rows, columns);
+  }
+
+  private void assertEquals(Matrix u1, Matrix u2) {
+    assertEquals(0.0, u1.minus(u2).aggregate(Functions.MAX, Functions.ABS), 1e-10);
+  }
+
+  @Test
+  public void testRightVectors() throws IOException {
+    Matrix A = lowRankMatrixInMemory(20, 20);
+
+    SequentialBigSvd s = new SequentialBigSvd(A, 6);
+    SingularValueDecomposition svd = new SingularValueDecomposition(A);
+
+    Matrix v1 = svd.getV().viewPart(0, 20, 0, 3).assign(Functions.ABS);
+    Matrix v2 = s.getV().viewPart(0, 20, 0, 3).assign(Functions.ABS);
+    assertEquals(v1, v2);
+  }
 
   private static Matrix lowRankMatrix(File tmpDir, String aBase, int rowsPerSlice, int rows, int columns) throws IOException {
     int rank = 10;
@@ -159,16 +179,17 @@ public final class SequentialOutOfCoreSv
     Matrix v = new RandomTrinaryMatrix(2, columns, rank, false);
     Matrix a = u.times(d).times(v.transpose());
 
-    for (int i = 0; i < a.rowSize(); i += rowsPerSlice) {
-      MatrixWritable m = new MatrixWritable(a.viewPart(i, Math.min(a.rowSize() - i, rowsPerSlice), 0, a.columnSize()));
-      DataOutputStream out = new DataOutputStream(new FileOutputStream(new File(tmpDir, String.format("%s-%09d", aBase, i))));
-      try {
-        m.write(out);
-      } finally {
-        out.close();
+    if (tmpDir != null) {
+      for (int i = 0; i < a.rowSize(); i += rowsPerSlice) {
+        MatrixWritable m = new MatrixWritable(a.viewPart(i, Math.min(a.rowSize() - i, rowsPerSlice), 0, a.columnSize()));
+        DataOutputStream out = new DataOutputStream(new FileOutputStream(new File(tmpDir, String.format("%s-%09d", aBase, i))));
+        try {
+          m.write(out);
+        } finally {
+          out.close();
+        }
       }
     }
     return a;
   }
-
 }