Author: dlyubimov Date: Mon Oct 7 20:17:47 2013 New Revision: 1530047 URL: http://svn.apache.org/r1530047 Log: MAHOUT-1300:Support for functional matrix views and some of their concrete implementations.
Squashed commit of the following: commit 6328f2ef2a79a607c4acfb0ef3f6f2f14720610d Merge: 7504544 39b207b Author: Dmitriy Lyubimov <[email protected]> Date: Mon Oct 7 12:59:30 2013 -0700 Merge branch 'trunk' into MAHOUT-1300 commit 7504544f105217c92fe479fe6630e8133e9212dc Merge: 82b3412 70777c4 Author: Dmitriy Lyubimov <[email protected]> Date: Wed Aug 7 23:06:28 2013 -0700 Merge remote-tracking branch 'apache/trunk' into MAHOUT-1300 commit 82b3412acda7300367261e8610dd49295336ddfd Author: Dmitriy Lyubimov <[email protected]> Date: Tue Jul 30 19:25:25 2013 -0700 adding default implementation of viewPart to abstract Matrix (probably missing from there.). Fixing other things in FunctionalMatrixView. commit 284adde56d145f22e7e06fa0ed3d684c67dc2783 Author: Dmitriy Lyubimov <[email protected]> Date: Tue Jul 30 13:33:58 2013 -0700 Added Gaussian matrix gen test commit d0467b80c7cf2770b1ab96c9712cf2956e14cf5f Author: Dmitriy Lyubimov <[email protected]> Date: Tue Jul 30 13:30:15 2013 -0700 Test and fixes commit 2a985437a3b02866bc7493b63aa352a872a2b0f2 Author: Dmitriy Lyubimov <[email protected]> Date: Tue Jul 30 12:46:03 2013 -0700 adding Apache 2 license commit 69c8a532912a411e8abf8af759e25fc3a533925c Author: Dmitriy Lyubimov <[email protected]> Date: Tue Jul 30 12:41:49 2013 -0700 Initial write-up for MAHOUT-1300 Added: mahout/trunk/math/src/main/java/org/apache/mahout/math/FunctionalMatrixView.java mahout/trunk/math/src/main/java/org/apache/mahout/math/Matrices.java mahout/trunk/math/src/main/java/org/apache/mahout/math/function/IntIntFunction.java mahout/trunk/math/src/test/java/org/apache/mahout/math/MatricesTest.java Modified: mahout/trunk/math/src/main/java/org/apache/mahout/math/AbstractMatrix.java mahout/trunk/math/src/main/java/org/apache/mahout/math/function/Functions.java Modified: mahout/trunk/math/src/main/java/org/apache/mahout/math/AbstractMatrix.java URL: http://svn.apache.org/viewvc/mahout/trunk/math/src/main/java/org/apache/mahout/math/AbstractMatrix.java?rev=1530047&r1=1530046&r2=1530047&view=diff ============================================================================== --- mahout/trunk/math/src/main/java/org/apache/mahout/math/AbstractMatrix.java (original) +++ mahout/trunk/math/src/main/java/org/apache/mahout/math/AbstractMatrix.java Mon Oct 7 20:17:47 2013 @@ -17,19 +17,16 @@ package org.apache.mahout.math; -import java.util.Iterator; -import java.util.Map; - -import org.apache.mahout.math.function.DoubleDoubleFunction; -import org.apache.mahout.math.function.DoubleFunction; -import org.apache.mahout.math.function.Functions; -import org.apache.mahout.math.function.PlusMult; -import org.apache.mahout.math.function.VectorFunction; - import com.google.common.collect.AbstractIterator; import com.google.common.collect.Maps; +import org.apache.mahout.math.function.*; + +import java.util.Iterator; +import java.util.Map; -/** A few universal implementations of convenience functions */ +/** + * A few universal implementations of convenience functions + */ public abstract class AbstractMatrix implements Matrix { protected Map<String, Integer> columnLabelBindings; @@ -61,6 +58,7 @@ public abstract class AbstractMatrix imp public Iterator<MatrixSlice> iterateAll() { return new AbstractIterator<MatrixSlice>() { private int slice; + @Override protected MatrixSlice computeNext() { if (slice >= numSlices()) { @@ -74,6 +72,7 @@ public abstract class AbstractMatrix imp /** * Abstracted out for the iterator + * * @return numRows() for row-based iterator, numColumns() for column-based. */ @Override @@ -228,7 +227,7 @@ public abstract class AbstractMatrix imp for (int row = 0; row < rows; row++) { for (int col = 0; col < columns; col++) { setQuick(row, col, function.apply(getQuick(row, col), other.getQuick( - row, col))); + row, col))); } } return this; @@ -282,7 +281,8 @@ public abstract class AbstractMatrix imp /** * Returns a view of a row. Changes to the view will affect the original. - * @param row Which row to return. + * + * @param row Which row to return. * @return A vector that references the desired row. */ @Override @@ -293,6 +293,7 @@ public abstract class AbstractMatrix imp /** * Returns a view of a row. Changes to the view will affect the original. + * * @param column Which column to return. * @return A vector that references the desired column. */ @@ -433,7 +434,7 @@ public abstract class AbstractMatrix imp for (int row = 0; row < rows; row++) { for (int col = 0; col < columns; col++) { result.setQuick(row, col, getQuick(row, col) - - other.getQuick(row, col)); + - other.getQuick(row, col)); } } return result; @@ -466,7 +467,7 @@ public abstract class AbstractMatrix imp for (int row = 0; row < rows; row++) { for (int col = 0; col < columns; col++) { result.setQuick(row, col, getQuick(row, col) - + other.getQuick(row, col)); + + other.getQuick(row, col)); } } return result; @@ -584,6 +585,26 @@ public abstract class AbstractMatrix imp } @Override + public Matrix viewPart(int[] offset, int[] size) { + + if (offset[ROW] < 0) { + throw new IndexException(offset[ROW], 0); + } + if (offset[ROW] + size[ROW] > rowSize()) { + throw new IndexException(offset[ROW] + size[ROW], rowSize()); + } + if (offset[COL] < 0) { + throw new IndexException(offset[COL], 0); + } + if (offset[COL] + size[COL] > columnSize()) { + throw new IndexException(offset[COL] + size[COL], columnSize()); + } + + return new MatrixView(this, offset, size); + } + + + @Override public double zSum() { double result = 0; for (int row = 0; row < rowSize(); row++) { @@ -645,6 +666,7 @@ public abstract class AbstractMatrix imp public Iterator<Element> iterator() { return new AbstractIterator<Element>() { private int i; + @Override protected Element computeNext() { if (i >= size()) { @@ -658,6 +680,7 @@ public abstract class AbstractMatrix imp /** * Currently delegates to {@link #iterator()}. * TODO: This could be optimized to at least skip empty rows if there are many of them. + * * @return an iterator (currently dense). */ @Override Added: mahout/trunk/math/src/main/java/org/apache/mahout/math/FunctionalMatrixView.java URL: http://svn.apache.org/viewvc/mahout/trunk/math/src/main/java/org/apache/mahout/math/FunctionalMatrixView.java?rev=1530047&view=auto ============================================================================== --- mahout/trunk/math/src/main/java/org/apache/mahout/math/FunctionalMatrixView.java (added) +++ mahout/trunk/math/src/main/java/org/apache/mahout/math/FunctionalMatrixView.java Mon Oct 7 20:17:47 2013 @@ -0,0 +1,81 @@ +/** + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.mahout.math; + +import org.apache.mahout.math.function.IntIntFunction; + +/** + * Matrix View backed by an {@link IntIntFunction} + */ +class FunctionalMatrixView extends AbstractMatrix { + + /** + * view generator function + */ + private IntIntFunction gf; + private boolean denseLike; + + public FunctionalMatrixView(int rows, int columns, IntIntFunction gf) { + this(rows, columns, gf, false); + } + + /** + * @param gf generator function + * @param denseLike whether like() should create Dense or Sparse matrix. + */ + public FunctionalMatrixView(int rows, int columns, IntIntFunction gf, boolean denseLike) { + super(rows, columns); + this.gf = gf; + this.denseLike = denseLike; + } + + @Override + public Matrix assignColumn(int column, Vector other) { + throw new UnsupportedOperationException("Assignment to a matrix not supported"); + } + + @Override + public Matrix assignRow(int row, Vector other) { + throw new UnsupportedOperationException("Assignment to a matrix view not supported"); + } + + @Override + public double getQuick(int row, int column) { + return gf.apply(row, column); + } + + @Override + public Matrix like() { + return like(rows, columns); + } + + @Override + public Matrix like(int rows, int columns) { + if (denseLike) + return new DenseMatrix(rows, columns); + else + return new SparseMatrix(rows, columns); + } + + @Override + public void setQuick(int row, int column, double value) { + throw new UnsupportedOperationException("Assignment to a matrix view not supported"); + } + + +} Added: mahout/trunk/math/src/main/java/org/apache/mahout/math/Matrices.java URL: http://svn.apache.org/viewvc/mahout/trunk/math/src/main/java/org/apache/mahout/math/Matrices.java?rev=1530047&view=auto ============================================================================== --- mahout/trunk/math/src/main/java/org/apache/mahout/math/Matrices.java (added) +++ mahout/trunk/math/src/main/java/org/apache/mahout/math/Matrices.java Mon Oct 7 20:17:47 2013 @@ -0,0 +1,172 @@ +/** + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.mahout.math; + +import org.apache.mahout.common.RandomUtils; +import org.apache.mahout.math.function.DoubleFunction; +import org.apache.mahout.math.function.Functions; +import org.apache.mahout.math.function.IntIntFunction; + +import java.util.Random; + +/** + * @author dmitriy + */ +public final class Matrices { + + /** + * Create a matrix view based on a function generator. + * <p/> + * The generator needs to be idempotent, i.e. returning same value + * for each combination of (row, column) argument sent to generator's + * {@link IntIntFunction#apply(int, int)} call. + * + * @param rows Number of rows in a view + * @param columns Number of columns in a view. + * @param gf view generator + * @param denseLike type of matrix returne dby {@link org.apache.mahout.math.Matrix#like()}. + * @return new matrix view. + */ + public static final Matrix functionalMatrixView(final int rows, + final int columns, + final IntIntFunction gf, + final boolean denseLike) { + return new FunctionalMatrixView(rows, columns, gf, denseLike); + } + + /** + * Shorter form of {@link Matrices#functionalMatrixView(int, int, + * org.apache.mahout.math.function.IntIntFunction, boolean)}. + */ + public static final Matrix functionalMatrixView(final int rows, + final int columns, + final IntIntFunction gf) { + return new FunctionalMatrixView(rows, columns, gf); + } + + /** + * A read-only transposed view of a matrix argument. + * + * @param m original matrix + * @return transposed view of original matrix + */ + public static final Matrix transposedView(final Matrix m) { + IntIntFunction tf = new IntIntFunction() { + @Override + public double apply(int row, int col) { + return m.getQuick(col, row); + } + }; + + // TODO: Matrix api does not support denseLike() interrogation. + // so our guess has to be rough here. + return functionalMatrixView(m.numCols(), m.numRows(), tf, m instanceof DenseMatrix); + } + + /** + * Random Gaussian matrix view. + * + * @param seed generator seed + */ + public static final Matrix gaussianView(final int rows, + final int columns, + long seed) { + return functionalMatrixView(rows, columns, gaussianGenerator(seed), true); + } + + + /** + * Matrix view based on uniform [-1,1) distribution. + * + * @param seed generator seed + */ + public static final Matrix symmetricUniformView(final int rows, + final int columns, + int seed) { + return functionalMatrixView(rows, columns, uniformSymmetricGenerator(seed), true); + } + + /** + * Matrix view based on uniform [0,1) distribution. + * + * @param seed generator seed + */ + public static final Matrix uniformView(final int rows, + final int columns, + int seed) { + return functionalMatrixView(rows, columns, uniformGenerator(seed), true); + } + + /** + * Generator for a matrix populated by random Gauissian values (Gaussian matrix view) + * + * @param seed The seed for the matrix. + * @return Gaussian {@link IntIntFunction} generating matrix view with normal values + */ + public static final IntIntFunction gaussianGenerator(final long seed) { + final Random rnd = RandomUtils.getRandom(seed); + IntIntFunction gaussianGF = new IntIntFunction() { + @Override + public double apply(int first, int second) { + rnd.setSeed(seed ^ (((long) first << 32) | (second & 0xffffffffl))); + return rnd.nextGaussian(); + } + }; + return gaussianGF; + } + + private static final double UNIFORM_DIVISOR = Math.pow(2.0, 64); + + /** + * Uniform [-1,1) matrix generator function. + * <p/> + * WARNING: to keep things performant, it is stateful and so not thread-safe. + * You'd need to create a copy per thread (with same seed) if shared between threads. + * + * @param seed + * @return Uniform {@link IntIntFunction} generator + */ + public static final IntIntFunction uniformSymmetricGenerator(final int seed) { + return new IntIntFunction() { + private byte[] data = new byte[8]; + + @Override + public double apply(int row, int column) { + long d = ((long) row << Integer.SIZE) | (column & 0xffffffffl); + for (int i = 0; i < 8; i++, d >>>= 8) data[i] = (byte) d; + long hash = MurmurHash.hash64A(data, seed); + return hash / UNIFORM_DIVISOR; + } + }; + } + + /** + * Uniform [0,1) matrix generator function + * + * @param seed generator seed + */ + public static final IntIntFunction uniformGenerator(final int seed) { + return Functions.chain(new DoubleFunction() { + @Override + public double apply(double x) { + return (x + 1.0) / 2.0; + } + }, uniformSymmetricGenerator(seed)); + } + +} Modified: mahout/trunk/math/src/main/java/org/apache/mahout/math/function/Functions.java URL: http://svn.apache.org/viewvc/mahout/trunk/math/src/main/java/org/apache/mahout/math/function/Functions.java?rev=1530047&r1=1530046&r2=1530047&view=diff ============================================================================== --- mahout/trunk/math/src/main/java/org/apache/mahout/math/function/Functions.java (original) +++ mahout/trunk/math/src/main/java/org/apache/mahout/math/function/Functions.java Mon Oct 7 20:17:47 2013 @@ -1334,6 +1334,24 @@ public final class Functions { } /** + * Constructs the function <tt>g( h(a) )</tt>. + * + * @param g a unary function. + * @param h an {@link IntIntFunction} function. + * @return the unary function <tt>g( h(a) )</tt>. + */ + public static IntIntFunction chain(final DoubleFunction g, final IntIntFunction h) { + return new IntIntFunction() { + + @Override + public double apply(int first, int second) { + return g.apply(h.apply(first, second)); + } + }; + } + + + /** * Constructs a function that returns <tt>a < b ? -1 : a > b ? 1 : 0</tt>. <tt>a</tt> is a variable, <tt>b</tt> is * fixed. */ Added: mahout/trunk/math/src/main/java/org/apache/mahout/math/function/IntIntFunction.java URL: http://svn.apache.org/viewvc/mahout/trunk/math/src/main/java/org/apache/mahout/math/function/IntIntFunction.java?rev=1530047&view=auto ============================================================================== --- mahout/trunk/math/src/main/java/org/apache/mahout/math/function/IntIntFunction.java (added) +++ mahout/trunk/math/src/main/java/org/apache/mahout/math/function/IntIntFunction.java Mon Oct 7 20:17:47 2013 @@ -0,0 +1,25 @@ +/** + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.mahout.math.function; + +/** + * A function that takes to integer arguments and returns Double. + */ +public interface IntIntFunction { + double apply(int first, int second); +} Added: mahout/trunk/math/src/test/java/org/apache/mahout/math/MatricesTest.java URL: http://svn.apache.org/viewvc/mahout/trunk/math/src/test/java/org/apache/mahout/math/MatricesTest.java?rev=1530047&view=auto ============================================================================== --- mahout/trunk/math/src/test/java/org/apache/mahout/math/MatricesTest.java (added) +++ mahout/trunk/math/src/test/java/org/apache/mahout/math/MatricesTest.java Mon Oct 7 20:17:47 2013 @@ -0,0 +1,106 @@ +/** + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.mahout.math; + +import org.apache.mahout.math.function.Functions; +import org.apache.mahout.math.function.IntIntFunction; +import org.junit.Test; + +public class MatricesTest extends MahoutTestCase { + + @Test + public void testFunctionalView() { + Matrix m = Matrices.functionalMatrixView(5, 6, new IntIntFunction() { + @Override + public double apply(int row, int col) { + assertTrue(row < 5); + assertTrue(col < 6); + return row + col; + } + }); + + // row-wise sums are 15, 15+ 6, 15 +12, 15+18, 15+24 + // so total sum is 1/2*(15+15+24)*5 =27*5 = 135 + assertEquals(135, m.aggregate(Functions.PLUS, Functions.IDENTITY), 1e-10); + } + + @Test + public void testTransposeView() { + + Matrix m = Matrices.gaussianView(5, 6, 1234L); + Matrix controlM = new DenseMatrix(5, 6).assign(m); + + System.out.printf("M=\n%s\n", m); + System.out.printf("controlM=\n%s\n", controlM); + + Matrix mtm = Matrices.transposedView(m).times(m); + Matrix controlMtm = controlM.transpose().times(controlM); + + System.out.printf("M'M=\n%s\n", mtm); + + Matrix diff = mtm.minus(controlMtm); + + assertEquals(0, diff.aggregate(Functions.PLUS, Functions.ABS), 1e-10); + + } + + @Test + public void testUniformView() { + Matrix m1 = Matrices.uniformView(5, 6, 1234); + Matrix m2 = Matrices.uniformView(5, 6, 1234); + + for (int row = 0; row < m1.numRows(); row++) { + for (int col = 0; col < m1.numCols(); col++) { + assertTrue(m1.getQuick(row, col) >= 0.0); + assertTrue(m1.getQuick(row, col) < 1.0); + } + } + + Matrix diff = m1.minus(m2); + + assertEquals(0, diff.aggregate(Functions.PLUS, Functions.ABS), 1e-10); + } + + @Test + public void testSymmetricUniformView() { + Matrix m1 = Matrices.symmetricUniformView(5, 6, 1234); + Matrix m2 = Matrices.symmetricUniformView(5, 6, 1234); + + for (int row = 0; row < m1.numRows(); row++) { + for (int col = 0; col < m1.numCols(); col++) { + assertTrue(m1.getQuick(row, col) >= -1.0); + assertTrue(m1.getQuick(row, col) < 1.0); + } + } + + Matrix diff = m1.minus(m2); + + assertEquals(0, diff.aggregate(Functions.PLUS, Functions.ABS), 1e-10); + } + + @Test + public void testGaussianView() { + Matrix m1 = Matrices.gaussianView(5, 6, 1234); + Matrix m2 = Matrices.gaussianView(5, 6, 1234); + + Matrix diff = m1.minus(m2); + + assertEquals(0, diff.aggregate(Functions.PLUS, Functions.ABS), 1e-10); + } + +}
