/* 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; ialpha and 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 and size 
	dimensions */
	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 z approaches 0. If z is 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; i 0) {
			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 example observationLengths[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 example observationLengths[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 example observationLengths[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; i 0) {
					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.