package cc.mallet.topics;

import java.util.Arrays;
import java.io.*;

import cc.mallet.types.*;
import cc.mallet.util.*;

public class NonNegativeMatrixFactorization {

	static CommandOption.String inputFile = new CommandOption.String(NonNegativeMatrixFactorization.class, "input", "FILENAME", true, null,
																	 "The filename from which to read the list of training instances.  Use - for stdin.  " +
																	 "The instances must be FeatureVectors, not FeatureSequences", null);
	
	static CommandOption.String outputWordsFile = new CommandOption.String(NonNegativeMatrixFactorization.class, "output-words", "FILENAME", true, "word-weights.txt",
																	  "The filename to write weights for each word.", null);
	
	static CommandOption.String outputDocsFile = new CommandOption.String(NonNegativeMatrixFactorization.class, "output-docs", "FILENAME", true, "doc-weights.txt",
																	  "The filename to write weights for each document.", null);
	
	static CommandOption.Integer numDimensions = new CommandOption.Integer(NonNegativeMatrixFactorization.class, "num-dimensions", "INTEGER", true, 50,
																	   "The number of dimensions to fit.", null);
	
	static CommandOption.Integer clusterSize = new CommandOption.Integer(NonNegativeMatrixFactorization.class, "init-cluster-size", "INTEGER", true, 0,
																	   "Select this number of random instances to initialize each dimension. 0 = off.", null);
	
	static CommandOption.Boolean useIDFOption = new CommandOption.Boolean(NonNegativeMatrixFactorization.class, "use-idf", "TRUE/FALSE", true, true,
																	   "Whether to use IDF weighting.", null);

	// It should be trivial to parallelize, I haven't done it yet.
	//static CommandOption.Integer numThreads = new CommandOption.Integer(NonNegativeMatrixFactorization.class, "num-threads", "INTEGER", true, 1,
	//																	"The number of threads for parallel training.", null);

	static CommandOption.Integer numIterationsOption = new CommandOption.Integer(NonNegativeMatrixFactorization.class, "num-iters", "INTEGER", true, 1000,
																		"The number of passes through the training data.", null);


	InstanceList instances;
	int numFactors;

	int numFeatures;
	int numInstances;
	
	int numIterations;
	boolean idfWeighting;

	double[] featureWeights = null;

	double[][] featureFactorWeights;
	double[][] instanceFactorWeights;

	double[] featureSums;
	double[] instanceSums;
	
	Randoms random;

	public NonNegativeMatrixFactorization(InstanceList instances,
                                          int numFactors, boolean idfWeighting) {
		this(instances, numFactors, idfWeighting, new Randoms());
	}

	public NonNegativeMatrixFactorization(InstanceList instances,
										  int numFactors, boolean idfWeighting,
										  Randoms random) {

		this.instances = instances;
		this.numFactors = numFactors;
		this.idfWeighting = idfWeighting;
		this.random = random;

		numFeatures = instances.getDataAlphabet().size();
		numInstances = instances.size();

		featureFactorWeights = new double[ numFeatures ][ numFactors ];
		instanceFactorWeights = new double[ numInstances ][ numFactors ];

		featureSums = new double[ numFactors ];
		instanceSums = new double[ numFactors ];

		if (idfWeighting) { calculateIDFWeights(); }
		
		// Initialize randomly to break symmetry, plus a selection of random documents to give a good initialization.
		
		for (int feature = 0; feature < numFeatures; feature++) {
			for (int factor = 0; factor < numFactors; factor++) {
				featureFactorWeights[feature][factor] = 0.001 * random.nextUniform() / numFeatures;
				featureSums[factor] += featureFactorWeights[feature][factor];
			}
		}
		
		for (int instance = 0; instance < numInstances; instance++) {
			for (int factor = 0; factor < numFactors; factor++) {
				instanceFactorWeights[instance][factor] = 1.0 / numFactors; //random.nextUniform() / numFactors;
				instanceSums[factor] += instanceFactorWeights[instance][factor];
			}
		}
	}
	
	public void calculateIDFWeights() {
		this.idfWeighting = true;
		
		System.out.println("Counting word features");
		FeatureCountTool counter = new FeatureCountTool(instances);
		counter.count();
		int[] instanceCounts = counter.getDocumentFrequencies();

		featureWeights = new double[ numFeatures ];

		for (int feature = 0; feature < numFeatures; feature++) {
			if (instanceCounts[feature] > 0) {
				featureWeights[feature] = Math.log((double) numInstances / instanceCounts[feature]);
			}
		}
	}
	
	public void initialize(int clusterSize) {
		for (int factor = 0; factor < numFactors; factor++) {
			for (int sample = 0; sample < clusterSize; sample++) {
				FeatureVector data = (FeatureVector) instances.get(random.nextInt(numInstances)).getData();
				for (int location = 0; location < data.numLocations(); location++) {
					int feature = data.indexAtLocation(location);
					double value = data.valueAtLocation(location);
					if (idfWeighting) {
						value *= featureWeights[feature];
					}
					featureFactorWeights[feature][factor] += value / clusterSize;
					featureSums[factor] += value / clusterSize;
				}
			}
		}
	}
	
    public static final String[] BARS = { " ", "\u2581", "\u2582", "\u2583", "\u2584", "\u2585", "\u2586", "\u2587", "\u2588" };

     public static String getBar(double x, double min, double max) {
             if (x > max) { x = max; }
             if (x < min) { x = min; }
             return BARS[ (int) Math.round(8.0 * (x - min) / (max - min)) ];
     }
     
     public static String getBars(double[] sequence, double min, double max) {

              StringBuilder out = new StringBuilder();
              for (double x :sequence) {
                      out.append(getBar(x, min, max));
              }
              return out.toString();
      }

     public static String getBars(double[] sequence) {
             double max = Double.NEGATIVE_INFINITY;
             double min = Double.POSITIVE_INFINITY;
             
             for (double x : sequence) {
                     if (x > max) { max = x; }
                     if (x < min) { min = x; }
             }

             return getBars(sequence, 0.0, max);
     }

	public double getDivergence() {
		double divergence = 0.0;
		for (int instance = 0; instance < numInstances; instance++) {
			FeatureVector data = (FeatureVector) instances.get(instance).getData();

			double[] currentInstanceFactorWeights =
				instanceFactorWeights[instance];
		
			for (int location = 0; location < data.numLocations(); location++) {
				int feature = data.indexAtLocation(location);
				double value = data.valueAtLocation(location);
				if (idfWeighting) {
					value *= featureWeights[feature];
				}
				
				double[] currentFeatureFactorWeights = 
					featureFactorWeights[feature];
				
				double innerProduct = 0.0;

				for (int factor = 0; factor < numFactors; factor++) {
					innerProduct += 
						currentInstanceFactorWeights[factor] *
						currentFeatureFactorWeights[factor];
				}
				if (innerProduct == 0.0) { continue; }
				
				divergence += value * Math.log(value / innerProduct) - value + innerProduct;
			}
		
		}
		return divergence;
	}

	public void updateWeights() {

		// First do the instance-factor updates
		
		for (int instance = 0; instance < numInstances; instance++) {
			FeatureVector data = (FeatureVector) instances.get(instance).getData();

			double[] currentInstanceFactorWeights =
				instanceFactorWeights[instance];

			// Gather the expected counts (W * H)

			double[] updateRatios = new double[ numFactors ];
			
			double valueSum = 0.0;

			for (int location = 0; location < data.numLocations(); location++) {
				int feature = data.indexAtLocation(location);
				double value = data.valueAtLocation(location);
				if (idfWeighting) {
					value *= featureWeights[feature];
				}
				valueSum += value;
				
				double[] currentFeatureFactorWeights = 
					featureFactorWeights[feature];
				
				double innerProduct = 0.0;

				for (int factor = 0; factor < numFactors; factor++) {
					innerProduct += 
						currentInstanceFactorWeights[factor] *
						currentFeatureFactorWeights[factor];
				}
				if (innerProduct == 0.0) { continue; }
				
				double ratio = value / innerProduct;

				for (int factor = 0; factor < numFactors; factor++) {
					updateRatios[factor] +=
						currentFeatureFactorWeights[factor] * 
						ratio;
				}
			}

			// Finally, scale by the inverse of the sum over features for 
			//  this factor and do the update.

			if (valueSum > 0.0) {
				for (int factor = 0; factor < numFactors; factor++) {
					currentInstanceFactorWeights[ factor ] *=
						updateRatios[factor] / 
						featureSums[factor];
					assert(! Double.isNaN(currentInstanceFactorWeights[ factor ]));
				}
			}
			else {
				for (int factor = 0; factor < numFactors; factor++) {
					currentInstanceFactorWeights[ factor ] = 0.0;
				}
			}
		}

		Arrays.fill(instanceSums, 0);
		
		for (int instance = 0; instance < numInstances; instance++) {
			for (int factor = 0; factor < numFactors; factor++) {
				instanceSums[factor] += instanceFactorWeights[instance][factor];
			}
		}

		// Now collect data for the updates for featureFactor weights

		
		// It's more convenient to loop over documents
		//  and then features than the other way around,
		//  so we need to save some the full matrix of
		//  update ratios.
		double[][] featureFactorUpdateRatios = new double[ numFeatures ][ numFactors ];

		for (int instance = 0; instance < numInstances; instance++) {
            FeatureVector data = (FeatureVector) instances.get(instance).getData();

            double[] currentInstanceFactorWeights =
                instanceFactorWeights[instance];

			for (int location = 0; location < data.numLocations(); location++) {
                int feature = data.indexAtLocation(location);
                double value = data.valueAtLocation(location);
				if (idfWeighting) {
					value *= featureWeights[feature];
				}
				
				if (value == 0.0) {
					continue;
				}

                double[] currentFeatureFactorWeights =
                    featureFactorWeights[feature];

                double innerProduct = 0.0;

                for (int factor = 0; factor < numFactors; factor++) {

					assert( currentInstanceFactorWeights[factor] >= 0.0 );
					assert( currentFeatureFactorWeights[factor] >= 0.0 );

                    innerProduct +=
                        currentInstanceFactorWeights[factor] *
                        currentFeatureFactorWeights[factor];
                }

                double ratio = value / innerProduct;
				
                for (int factor = 0; factor < numFactors; factor++) {
					assert( ! Double.isNaN( currentInstanceFactorWeights[factor] ) );
					assert( ! Double.isNaN(ratio) ) : value + " / " + innerProduct;
					

                    featureFactorUpdateRatios[feature][factor] +=
                        currentInstanceFactorWeights[factor] *
                        ratio;
                }
			}
		}
		
		// ... and do the updates

		for (int feature = 0; feature < numFeatures; feature++) {

			double[] currentFeatureFactorWeights =
				 featureFactorWeights[feature];

			for (int factor = 0; factor < numFactors; factor++) {
				
				assert( ! Double.isNaN(featureFactorUpdateRatios[feature][factor]) );
				assert( ! Double.isNaN(instanceSums[factor]) ) : instanceSums[factor];

				currentFeatureFactorWeights[factor] *= 
					featureFactorUpdateRatios[feature][factor] /
					instanceSums[factor];

				assert( ! Double.isNaN(currentFeatureFactorWeights[factor]));
			}
			
		}
				
		Arrays.fill(featureSums, 0);

		for (int feature = 0; feature < numFeatures; feature++) {
			for (int factor = 0; factor < numFactors; factor++) {
				featureSums[factor] += featureFactorWeights[feature][factor];
			}
		}
		//System.out.println(getBars(featureSums));

		
	}

	public void printFactorFeatures(int limit) {
		IDSorter[] sortedIDs = new IDSorter[numFeatures];

		StringBuilder output = new StringBuilder();

		for (int factor = 0; factor < numFactors; factor++) {

			for (int feature = 0; feature < numFeatures; feature++) {
				sortedIDs[feature] = new IDSorter(feature, featureFactorWeights[feature][factor]);
			}
			Arrays.sort(sortedIDs);

			output.append(factor + "\t");
			for (int i = 0; i < limit; i++) {
				output.append(instances.getDataAlphabet().lookupObject(sortedIDs[i].getID()) + " ");
			}
			output.append("\n");
		}

		System.out.println(output);
	}
	
	public void writeFeatureFactors(PrintWriter out) throws IOException {
		for (int feature = 0; feature < numFeatures; feature++) {

			double[] currentFeatureFactorWeights =
				 featureFactorWeights[feature];
			
			out.print(instances.getDataAlphabet().lookupObject(feature));

			for (int factor = 0; factor < numFactors; factor++) {
				out.format("\t%f", currentFeatureFactorWeights[factor]);
			}
			out.println();
		}
	}
	
	public void writeInstanceFactors(PrintWriter out) throws IOException {
		for (int instance = 0; instance < numInstances; instance++) {

			double[] currentInstanceFactorWeights =
				 instanceFactorWeights[instance];
			
			out.print(instances.get(instance).getName());

			for (int factor = 0; factor < numFactors; factor++) {
				out.format("\t%f", currentInstanceFactorWeights[factor]);
			}
			out.println();
		}
	}

	public static void main (String[] args) throws Exception {
		
		// Process the command-line options
		CommandOption.setSummary (NonNegativeMatrixFactorization.class,
								  "Train non-negative matrix factorization.");
		CommandOption.process (NonNegativeMatrixFactorization.class, args);

		InstanceList instances = InstanceList.load(new File(inputFile.value));
		
		NonNegativeMatrixFactorization nmf = 
			new NonNegativeMatrixFactorization(instances, numDimensions.value, useIDFOption.value);

		if (clusterSize.value > 0) {
			nmf.initialize(clusterSize.value);
		}

		System.out.println("Finding " + numDimensions.value + " factors.");
		System.out.println("Histograms show relative factor sizes, the number measures factorization error (smaller is better).");
		double previousDivergence = Double.POSITIVE_INFINITY;
		for (int iteration = 1; iteration <= numIterationsOption.value; iteration++) {
			nmf.updateWeights();
			
			if (iteration % 100 == 0) {
				nmf.printFactorFeatures(15);
			}
			if (iteration % 10 == 0) {
				double divergence = nmf.getDivergence();
				System.out.println(getBars(nmf.featureSums) + "\t" + getBars(nmf.instanceSums) + "\t" + divergence);
				if (divergence / previousDivergence > 0.9999) {
					break;
				}
				previousDivergence = divergence;
			}
		}		
		
		if (outputWordsFile.value != null) {
			System.out.println("Writing to " + outputWordsFile.value);

			PrintWriter out = new PrintWriter(new File(outputWordsFile.value));
			nmf.writeFeatureFactors(out);
			out.close();
		}
		
		if (outputDocsFile.value != null) {
			System.out.println("Writing to " + outputDocsFile.value);

			PrintWriter out = new PrintWriter(new File(outputDocsFile.value));
			nmf.writeInstanceFactors(out);
			out.close();			
		}
	}
}
 

Ads help maintain this website.