/* Copyright (C) 2002 Univ. of Massachusetts Amherst, Computer Science Dept. This file is part of "MALLET" (MAchine Learning for LanguagE Toolkit). http://www.cs.umass.edu/~mccallum/mallet This software is provided under the terms of the Common Public License, version 1.0, as published by http://www.opensource.org. For further information, see the file `LICENSE' included with this distribution. */ package cc.mallet.types; import com.carrotsearch.hppc.IntHashSet; import com.carrotsearch.hppc.IntIntHashMap; import com.carrotsearch.hppc.cursors.IntCursor; import java.io.BufferedWriter; import java.io.FileWriter; import java.io.IOException; import java.io.PrintWriter; import java.text.NumberFormat; import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; import cc.mallet.types.Multinomial; import cc.mallet.util.Maths; import cc.mallet.util.Randoms; /** * Various useful functions related to Dirichlet distributions. * * @author Andrew McCallum and David Mimno */ public class Dirichlet { Alphabet dict; double magnitude = 1; double[] partition; Randoms random = null; /** Actually the negative Euler-Mascheroni constant */ public static final double EULER_MASCHERONI = -0.5772156649015328606065121; public static final double PI_SQUARED_OVER_SIX = Math.PI * Math.PI / 6; public static final double HALF_LOG_TWO_PI = Math.log(2 * Math.PI) / 2; public static final double DIGAMMA_COEF_1 = 1/12; public static final double DIGAMMA_COEF_2 = 1/120; public static final double DIGAMMA_COEF_3 = 1/252; public static final double DIGAMMA_COEF_4 = 1/240; public static final double DIGAMMA_COEF_5 = 1/132; public static final double DIGAMMA_COEF_6 = 691/32760; public static final double DIGAMMA_COEF_7 = 1/12; public static final double DIGAMMA_COEF_8 = 3617/8160; public static final double DIGAMMA_COEF_9 = 43867/14364; public static final double DIGAMMA_COEF_10 = 174611/6600; public static final double DIGAMMA_LARGE = 9.5; public static final double DIGAMMA_SMALL = .000001; /** A dirichlet parameterized by a distribution and a magnitude * * @param m The magnitude of the Dirichlet: sum_i alpha_i * @param p A probability distribution: p_i = alpha_i / m */ public Dirichlet (double m, double[] p) { magnitude = m; partition = p; } /** A symmetric dirichlet: E(X_i) = E(X_j) for all i, j * * @param m The magnitude of the Dirichlet: sum_i alpha_i * @param n The number of dimensions */ /* public Dirichlet (double m, int n) { magnitude = m; partition = new double[n]; partition[0] = 1.0 / n; for (int i=1; iand the * number of dimensions of the given alphabet. */ public Dirichlet (Alphabet dict, double alpha) { this(dict.size(), alpha); this.dict = dict; dict.stopGrowth(); } /** A symmetric Dirichlet with alpha_i = 1.0 andalpha sizedimensions */ public Dirichlet (int size) { this (size, 1.0); } /** A symmetric dirichlet: E(X_i) = E(X_j) for all i, j * * @param n The number of dimensions * @param alpha The parameter for each dimension */ public Dirichlet (int size, double alpha) { magnitude = size * alpha; partition = new double[size]; partition[0] = 1.0 / size; for (int i=1; iexpected total number of counts in the returned vector. The actual number is ~ Poisson( n) */ public int[] drawObservation(int n, double[] distribution) { initRandom(); int[] histogram = new int[partition.length]; Arrays.fill(histogram, 0); int count; // I was using a poisson, but the poisson variate generator // goes berzerk for lambda above ~500. if (n < 100) { count = random.nextPoisson(); } else { // p(N(100, 10) <= 0) = 7.619853e-24 count = (int) Math.round(random.nextGaussian(n, n)); } for (int i=0; ilogGammaStirling */ public static double logGamma(double z) { return logGammaStirling(z); } /** Use a fifth order Stirling's approximation. * * @param z Note that Stirling's approximation is increasingly unstable as zapproaches 0. Ifzis less than 2, we shift it up, calculate the approximation, and then shift the answer back down. */ public static double logGammaStirling(double z) { int shift = 0; while (z < 2) { z++; shift++; } double result = HALF_LOG_TWO_PI + (z - 0.5) * Math.log(z) - z + 1/(12 * z) - 1 / (360 * z * z * z) + 1 / (1260 * z * z * z * z * z); while (shift > 0) { shift--; z--; result -= Math.log(z); } return result; } /** Gergo Nemes' approximation */ public static double logGammaNemes(double z) { double result = HALF_LOG_TWO_PI - (Math.log(z) / 2) + z * (Math.log(z + (1/(12 * z - (1/(10*z))))) - 1); return result; } /** Calculate digamma using an asymptotic expansion involving Bernoulli numbers. */ public static double digamma(double z) { // This is based on matlab code by Tom Minka // if (z < 0) { System.out.println(" less than zero"); } double psi = 0; if (z < DIGAMMA_SMALL) { psi = EULER_MASCHERONI - (1 / z); // + (PI_SQUARED_OVER_SIX * z); /*for (int n=1; n<100000; n++) { psi += z / (n * (n + z)); }*/ return psi; } while (z < DIGAMMA_LARGE) { psi -= 1 / z; z++; } double invZ = 1/z; double invZSquared = invZ * invZ; psi += Math.log(z) - .5 * invZ - invZSquared * (DIGAMMA_COEF_1 - invZSquared * (DIGAMMA_COEF_2 - invZSquared * (DIGAMMA_COEF_3 - invZSquared * (DIGAMMA_COEF_4 - invZSquared * (DIGAMMA_COEF_5 - invZSquared * (DIGAMMA_COEF_6 - invZSquared * DIGAMMA_COEF_7)))))); return psi; } public static double digammaDifference(double x, int n) { double sum = 0; for (int i=0; i0) { shift--; z--; result += 1.0 / (z * z); } return result; } /** * Learn the concentration parameter of a symmetric Dirichlet using frequency histograms. * Since all parameters are the same, we only need to keep track of * the number of observation/dimension pairs with count N * * @param countHistogram An array of frequencies. If the matrix X represents observations such that xdt is how many times word t occurs in document d, countHistogram[3]is the total number of cells in any column that equal 3. * @param observationLengths A histogram of sample lengths, for exampleobservationLengths[20]could be the number of documents that are exactly 20 tokens long. * @param numDimensions The total number of dimensions. * @param currentValue An initial starting value. */ public static double learnSymmetricConcentration(int[] countHistogram, int[] observationLengths, int numDimensions, double currentValue) { double currentDigamma; // The histogram arrays are presumably allocated before // we knew what went in them. It is therefore likely that // the largest non-zero value may be much closer to the // beginning than the end. We don't want to iterate over // a whole bunch of zeros, so keep track of the last value. int largestNonZeroCount = 0; int[] nonZeroLengthIndex = new int[ observationLengths.length ]; for (int index = 0; index < countHistogram.length; index++) { if (countHistogram[index] > 0) { largestNonZeroCount = index; } } int denseIndex = 0; for (int index = 0; index < observationLengths.length; index++) { if (observationLengths[index] > 0) { nonZeroLengthIndex[denseIndex] = index; denseIndex++; } } int denseIndexSize = denseIndex; for (int iteration = 1; iteration <= 200; iteration++) { double currentParameter = currentValue / numDimensions; // Calculate the numerator currentDigamma = 0; double numerator = 0; // Counts of 0 don't matter, so start with 1 for (int index = 1; index <= largestNonZeroCount; index++) { currentDigamma += 1.0 / (currentParameter + index - 1); numerator += countHistogram[index] * currentDigamma; } // Now calculate the denominator, a sum over all observation lengths currentDigamma = 0; double denominator = 0; int previousLength = 0; double cachedDigamma = digamma(currentValue); for (denseIndex = 0; denseIndex < denseIndexSize; denseIndex++) { int length = nonZeroLengthIndex[denseIndex]; if (length - previousLength > 20) { // If the next length is sufficiently far from the previous, // it's faster to recalculate from scratch. currentDigamma = digamma(currentValue + length) - cachedDigamma; } else { // Otherwise iterate up. This looks slightly different // from the previous version (no -1) because we're indexing differently. for (int index = previousLength; index < length; index++) { currentDigamma += 1.0 / (currentValue + index); } } denominator += currentDigamma * observationLengths[length]; } currentValue = currentParameter * numerator / denominator; ///System.out.println(currentValue + " = " + currentParameter + " * " + numerator + " / " + denominator); } return currentValue; } public static void testSymmetricConcentration(int numDimensions, int numObservations, int observationMeanLength) { double logD = Math.log(numDimensions); for (int exponent = -5; exponent < 4; exponent++) { double alpha = numDimensions * 1.0; Dirichlet prior = new Dirichlet(numDimensions, alpha / numDimensions); int[] countHistogram = new int[ 1000000 ]; int[] observationLengths = new int[ 1000000 ]; Object[] observations = prior.drawObservations(numObservations, observationMeanLength); Dirichlet optimizedDirichlet = new Dirichlet(numDimensions, 1.0); optimizedDirichlet.learnParametersWithHistogram(observations); System.out.println(optimizedDirichlet.magnitude); for (int i=0; i < numObservations; i++) { int[] observation = (int[]) observations[i]; int total = 0; for (int k=0; k < numDimensions; k++) { if (observation[k] > 0) { total += observation[k]; countHistogram[ observation[k] ]++; } } observationLengths[ total ]++; } double estimatedAlpha = learnSymmetricConcentration(countHistogram, observationLengths, numDimensions, 1.0); System.out.println(alpha + "\t" + estimatedAlpha + "\t" + Math.abs(alpha - estimatedAlpha)); } } /** * Learn Dirichlet parameters using frequency histograms * * @param parameters A reference to the current values of the parameters, which will be updated in place * @param observations An array of count histograms.observations[10][3]could be the number of documents that contain exactly 3 tokens of word type 10. * @param observationLengths A histogram of sample lengths, for exampleobservationLengths[20]could be the number of documents that are exactly 20 tokens long. * @returns The sum of the learned parameters. */ public static double learnParameters(double[] parameters, int[][] observations, int[] observationLengths) { return learnParameters(parameters, observations, observationLengths, 1.00001, 1.0, 200); } /** * Learn Dirichlet parameters using frequency histograms * * @param parameters A reference to the current values of the parameters, which will be updated in place * @param observations An array of count histograms.observations[10][3]could be the number of documents that contain exactly 3 tokens of word type 10. * @param observationLengths A histogram of sample lengths, for exampleobservationLengths[20]could be the number of documents that are exactly 20 tokens long. * @param shape Gamma prior E(X) = shape * scale, var(X) = shape * scale2 * @param scale * @param numIterations 200 to 1000 generally insures convergence, but 1-5 is often enough to step in the right direction * @returns The sum of the learned parameters. */ public static double learnParameters(double[] parameters, int[][] observations, int[] observationLengths, double shape, double scale, int numIterations) { int i, k; double parametersSum = 0; // Initialize the parameter sum for (k=0; k < parameters.length; k++) { parametersSum += parameters[k]; } double oldParametersK; double currentDigamma; double denominator; int nonZeroLimit; int[] nonZeroLimits = new int[observations.length]; Arrays.fill(nonZeroLimits, -1); // The histogram arrays go up to the size of the largest document, // but the non-zero values will almost always cluster in the low end. // We avoid looping over empty arrays by saving the index of the largest // non-zero value. int[] histogram; for (i=0; i0) { nonZeroLimits[i] = k; //out.append(k + ":" + histogram[k] + " "); } } //System.out.println(out); } for (int iteration=0; iteration maxBinCounts[bin]) { maxBinCounts[bin] = observation[bin]; } length += observation[bin]; } if (length > maxLength) { maxLength = length; } } // Arrays start at zero, so I'm sacrificing one int for greater clarity // later on... int[][] binCountHistograms = new int[partition.length][]; for (int bin=0; bin < partition.length; bin++) { binCountHistograms[bin] = new int[ maxBinCounts[bin] + 1 ]; Arrays.fill(binCountHistograms[bin], 0); } // System.out.println("got mem: " + (System.currentTimeMillis() - start)); int[] lengthHistogram = new int[maxLength + 1]; Arrays.fill(lengthHistogram, 0); // System.out.println("got lengths: " + (System.currentTimeMillis() - start)); for (int i=0; i < observations.length; i++) { int length = 0; int[] observation = (int[]) observations[i]; for (int bin=0; bin < observation.length; bin++) { binCountHistograms[bin][ observation[bin] ]++; length += observation[bin]; } lengthHistogram[length]++; } return learnParametersWithHistogram(binCountHistograms, lengthHistogram); } public long learnParametersWithHistogram(int[][] binCountHistograms, int[] lengthHistogram) { long start = System.currentTimeMillis(); double[] newParameters = new double[partition.length]; double alphaK; double currentDigamma; double denominator; double parametersSum = 0.0; int i, k; for (k = 0; k < partition.length; k++) { newParameters[k] = magnitude * partition[k]; parametersSum += newParameters[k]; } for (int iteration=0; iteration<1000; iteration++) { // Calculate the denominator denominator = 0; currentDigamma = 0; for (i=1; i < lengthHistogram.length; i++) { currentDigamma += 1 / (parametersSum + i - 1); denominator += lengthHistogram[i] * currentDigamma; } assert(denominator > 0.0); assert(! Double.isNaN(denominator)); parametersSum = 0.0; // Calculate the individual parameters for (k=0; k 0.0)) { System.out.println("length of empty array: " + (new int[0]).length); for (i=0; i 0.0); assert(! Double.isNaN(newParameters[k])); newParameters[k] *= alphaK / denominator; parametersSum += newParameters[k]; } /* try { if (iteration % 25 == 0) { //System.out.println(distributionToString(parametersSum, newParameters)); //toFile("../newsgroups/direct/iteration" + iteration); //System.out.println(iteration + ": " + (System.currentTimeMillis() - start)); } } catch (Exception e) { System.out.println(e); } */ } for (k = 0; k < partition.length; k++) { partition[k] = newParameters[k] / parametersSum; magnitude = parametersSum; } // System.out.println(distributionToString(magnitude, partition)); return System.currentTimeMillis() - start; } /** Use the fixed point iteration described by Tom Minka. */ public long learnParametersWithDigamma(Object[] observations) { int[][] binCounts = new int[partition.length][observations.length]; // System.out.println("got mem: " + (System.currentTimeMillis() - start)); int[] observationLengths = new int[observations.length]; // System.out.println("got lengths: " + (System.currentTimeMillis() - start)); for (int i=0; i < observations.length; i++) { int[] observation = (int[]) observations[i]; for (int bin=0; bin < partition.length; bin++) { binCounts[bin][i] = observation[bin]; observationLengths[i] += observation[bin]; } } // System.out.println("init: " + (System.currentTimeMillis() - start)); return learnParametersWithDigamma(binCounts, observationLengths); } public long learnParametersWithDigamma(int[][] binCounts, int[] observationLengths) { long start = System.currentTimeMillis(); double[] newParameters = new double[partition.length]; double alphaK; double denominator; double newMagnitude; int i, k; for (int iteration=0; iteration<1000; iteration++) { newMagnitude = 0; // Calculate the denominator denominator = 0; for (i=0; i 0); assert(! Double.isNaN(newParameters[k])); newMagnitude += newParameters[k]; // System.out.println("finished dimension " + k); } magnitude = newMagnitude; for (k=0; k = 2) { binSums[bin] += (counts[i] / (counts[i] - 1 + (magnitude * partition[bin]))); } } } parameterSum = 0.0; for (bin=0; bin < partition.length; bin++) { if (binSums[bin] == 0.0) { newParameters[bin] = 0.000001; } else { newParameters[bin] = (partition[bin] * magnitude * binSums[bin] / observationSum); } parameterSum += newParameters[bin]; } for (bin=0; bin < partition.length; bin++) { partition[bin] = newParameters[bin] / parameterSum; } magnitude = parameterSum; /* if (iteration % 50 == 0) { System.out.println(iteration + ": " + magnitude); } */ } // System.out.println(distributionToString(magnitude, partition)); return System.currentTimeMillis() - start; } /** Compute the L1 residual between two dirichlets */ public double absoluteDifference(Dirichlet other) { if (partition.length != other.partition.length) { throw new IllegalArgumentException("dirichlets must have the same dimension to be compared"); } double residual = 0.0; for (int k=0; k
Ads help maintain this website.