multinomialpotential.java

常用机器学习算法,java编写源代码,内含常用分类算法,包括说明文档

/* Copyright (C) 2003 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 edu.umass.cs.mallet.grmm;

import edu.umass.cs.mallet.base.types.Alphabet;
import edu.umass.cs.mallet.base.types.Matrix;
import edu.umass.cs.mallet.base.types.Matrixn;
import edu.umass.cs.mallet.base.util.Maths;
import gnu.trove.TIntObjectHashMap;

import java.util.*;


/**
 * Class for a multivariate multinomial distribution.
 * <p/>
 * Created: Mon Sep 15 17:19:24 2003
 *
 * @author <a href="mailto:[e-mail]">Charles Sutton</a>
 * @version $Id: MultinomialPotential.java,v 1.2 2004/08/17 20:53:09 casutton Exp $
 */
public class MultinomialPotential implements DiscretePotential {

  /**
   * Maps all of the Variable objects of this distribution
   * to an integer that says which dimension in the probs
   * matrix correspands to that var.
   */
  private Alphabet varMap = new Alphabet ();

  /**
   * Number of variables in this potential.
   */
  private int numVars;

  private Matrix probs;

  private void initVars (Alphabet allVars)
  {
    initVars (Arrays.asList (allVars.toArray ()));
  }

  private void initVars (Variable allVars[])
  {
    int sizes[] = new int[allVars.length];

//    Arrays.sort (allVars);
    for (int i = 0; i < allVars.length; i++) {
      varMap.lookupIndex (allVars[i]);
      sizes[i] = allVars[i].getNumOutcomes ();
    }

    probs = new Matrixn (sizes);
    if (probs.singleSize () == 0) {
      System.err.println ("Warning: empty potential created");
    }

    numVars = allVars.length;
  }

  private void initVars (Collection allVars)
  {
    initVars ((Variable[]) allVars.toArray (new Variable[allVars.size ()]));
  }

  private void setProbs (double[] probArray)
  {
    if (probArray.length != probs.singleSize ()) {
      /* This shouldn't be a runtime exception. So sue me. */
      throw new RuntimeException
              ("Attempt to initialize potential with bad number of prababilities.\n"
              + "Needed " + probs.singleSize () + " got " + probArray.length);
    }

    for (int i = 0; i < probArray.length; i++) {
      probs.setSingleValue (i, probArray[i]);
    }
  }

  /**
   * Creates an identity potential over the given variable.
   */
  public MultinomialPotential (Variable var)
  {
    initVars (new Variable[]{var});
    setAsIdentity ();
  }

  public MultinomialPotential (Variable var, double[] values)
  {
    initVars (new Variable[]{var});
    setProbs (values);
  }

  /**
   * Creates an identity potential over NO variables.
   */
  public MultinomialPotential ()
  {
    initVars (new Variable[]{});
    setAsIdentity ();
  }

  /**
   * Creates an identity potential with the given variables.
   */
  public MultinomialPotential (Variable allVars [])
  {
    initVars (allVars);
    setAsIdentity ();
  }

  /**
   * Creates an identity potential with the given variables.
   *
   * @param allVars A collection containing the Variables
   *                of this distribution.
   */
  public MultinomialPotential (Collection allVars)
  {
    initVars (allVars);
    setAsIdentity ();
  }

  /**
   * Creates a potential with the given variables and
   * the given probabilities.
   *
   * @param allVars Variables of the potential
   * @param probs   All phi values of the potential, in row-major order.
   */
  public MultinomialPotential (Variable[] allVars, double[] probs)
  {
    initVars (allVars);
    setProbs (probs);
  }

  /**
   * Creates a potential with the given variables and
   * the given probabilities.
   *
   * @param allVars Variables of the potential
   * @param probs   All phi values of the potential, in row-major order.
   */
  public MultinomialPotential (Alphabet allVars, double[] probs)
  {
    initVars (allVars);
    setProbs (probs);
  }


  /**
   * Creates a potential with the given variables and
   * the given probabilities.
   *
   * @param allVars Variables of the potential
   * @param probs   All phi values of the potential, in row-major order.
   */
  public MultinomialPotential (Clique allVars, double[] probs)
  {
    initVars (allVars.toVariableArray ());
    setProbs (probs);
  }


  /**
   * Creates a potential with the given variables and
   * the given probabilities.
   *
   * @param allVars Variables of the potential
   * @param probsIn All the phi values of the potential.
   */
  public MultinomialPotential (Variable[] allVars, Matrix probsIn)
  {
    initVars (allVars);
    probs = (Matrix) probsIn.cloneMatrix ();
  }

  /**
   * Creates a potential with the given variables and
   * the given probabilities.
   *
   * @param allVars Variables of the potential
   * @param probsIn All the phi values of the potential.
   */
  public MultinomialPotential (Alphabet allVars, Matrix probsIn)
  {
    initVars (allVars);
    probs = (Matrix) probsIn.cloneMatrix ();
  }


  /**
   * Creates a potential with the given variables and
   * the given probabilities.
   *
   * @param allVars Variables of the potential
   * @param probsIn All the phi values of the potential.
   */
  public MultinomialPotential (Clique allVars, Matrix probsIn)
  {
    initVars (allVars.toVariableArray ());
    probs = (Matrix) probsIn.cloneMatrix ();
  }

  /**
   * Forces this potential to be the identity (all 1s).
   */
  void setAsIdentity ()
  {
    if (inLogSpace) {
      setAll (0.0);
    } else {
      setAll (1.0);
    }
  }

  private void setAll (double val)
  {
    for (int i = 0; i < probs.singleSize (); i++) {
      probs.setSingleValue (i, val);
    }
  }

  // This method is inherently dangerous b/c variable ordering issues.
  // Consider using setPhi(Assignment,double) instead.
  public void setPhi (Matrixn probs)
  {
    if (this.probs.singleSize () != probs.singleSize ())
      throw new UnsupportedOperationException
              ("Trying to reset prob matrix with wrong number of probabilities.");
    if (this.probs.getNumDimensions () != probs.getNumDimensions ())
      throw new UnsupportedOperationException
              ("Trying to reset prob matrix with wrong number of dimensions.");
    this.probs = probs;
  }

  /**
   * Returns true iff this potential is over the given variable
   */
  public boolean containsVar (Variable var)
  {
    return varMap.contains (var);
  }

  /**
   * Returns set of variables in this potential.
   */
  public Set varSet ()
  {
    HashSet set = new HashSet ();
    set.addAll (Arrays.asList (varMap.toArray ()));
    return set;
  }

  public AssignmentIterator assignmentIterator ()
  {
    return new AssignmentIterator (Arrays.asList (varMap.toArray ()));
  }

  public void setPhi (Assignment assn, double value)
  {
    int[] indices = new int[numVars];
    for (int i = 0; i < numVars; i++) {
      Variable var = (Variable) varMap.lookupObject (i);
      indices[i] = assn.get (var);
    }

    probs.setValue (indices, value);
  }


  public double phi (Assignment assn)
  {
    if (numVars == 0) return 1.0;

    int[] indices = new int[numVars];
    for (int i = 0; i < numVars; i++) {
      Variable var = (Variable) varMap.lookupObject (i);
      indices[i] = assn.get (var);
    }

    return probs.value (indices);
  }


  public double phi (AssignmentIterator assn)
  {
    return probs.singleValue (assn.indexOfCurrentAssn ());
  }


  /**
   * Multiplies every entry in the potential by a constant
   * such that all the entries sum to 1.
   */
  public void normalize ()
  {
    if (inLogSpace) {
      logNormalize ();
    } else {
      probs.oneNormalize ();
    }
  }

  // Special function to do normalization in log space
  private void logNormalize ()
  {
    double sum = Double.NEGATIVE_INFINITY; // That's 0 in log space
    for (int i = 0; i < probs.singleSize (); i++) {
      sum = Maths.sumLogProb (sum, probs.singleValue (i));
    }

    for (int i = 0; i < probs.singleSize (); i++) {
      probs.incrementSingleValue (i, -sum);
    }
  }

  public double sum ()
  {
    return probs.oneNorm ();
  }

  public double entropy ()
  {
    double h = 0;
    double p;
    for (int i = 0; i < probs.singleSize (); i++) {
      p = probs.singleValue (i);

      if (p != 0)
        h -= p * Math.log (p);
    }
    return h;
  }


  //  PROJECTION OF INDICES


  // Maps potentials --> int[]
/* Be careful about this thing, however.  It gets shallow copied whenever
   *  a potential is duplicated, so if a potential were modified (e.g.,
   *  by expandToContain) while this was being shared, things could
   *  get ugly.  I think everything is all right at the moment, but keep
   *  it in mind if inexplicable bugs show up in the future. -cas
   */
  transient private TIntObjectHashMap projectionCache = new TIntObjectHashMap ();

  private void clearProjectionCache ()
  {
    projectionCache = new TIntObjectHashMap (varMap.size ());
  }

  /*  Returns a hash value for subsets of this potential's variable set.
   *   Note that the hash value depends only on the set's membership
   *   (not its order), so that this hashing scheme would be unsafe
   *   for the projection cache unless potential variables were always
   *   in a canonical order, which they are.
   */
  private int computeSubsetHashValue (MultinomialPotential subset)
  {
    // If potentials have more than 32 variables, we need to use an
    // expandable bitset, but then again, you probably wouldn't have
    // enough memory to represent the potential anyway
    assert varMap.size () <= 32;
    int result = 0;
    for (int i = 0; i < subset.varMap.size (); i++) {
      Object var = subset.varMap.lookupObject (i);
      int myidx = this.varMap.lookupIndex (var);
      result |= (1 << myidx);
    }
    return result;
  }

  private int[] computeLargeIdxToSmall (MultinomialPotential smallPotential)
//	private int largeIdxToSmall (int largeIdx, MultinomialPotential smallPotential)
  {
    int projection[] = new int[probs.singleSize ()];
    int largeDims[] = new int[numVars];
    int smallDims[] = new int[smallPotential.numVars];

    for (int largeIdx = 0; largeIdx < probs.singleSize (); largeIdx++) {
      probs.singleToIndices (largeIdx, largeDims);
      for (int smallDim = 0; smallDim < smallPotential.numVars; smallDim++) {
        Variable smallVar = (Variable) smallPotential.varMap.lookupObject (smallDim);
        int largeDim = this.varMap.lookupIndex (smallVar, false);
        assert largeDim != -1 : smallVar;
        smallDims[smallDim] = largeDims[largeDim];
      }
      projection[largeIdx] = smallPotential.probs.singleIndex (smallDims);
    }

    return projection;
  }

  private int[] largeIdxToSmall (MultinomialPotential smallPotential)
          //	private int cachedlargeIdxToSmall (int largeIdx, MultinomialPotential smallPotential)
  {
// Special case where smallPtl has only one variable.  Here
//  since ordering is not a problem, we can use a set-based
//  hash key.
    if (smallPotential.varSet ().size () == 1) {
      return cachedLargeIdxToSmall (smallPotential);
    } else {
      return computeLargeIdxToSmall (smallPotential);
    }
  }


  // Cached version of computeLargeIdxToSmall for ptls with a single variable.
  //  This code is designed to work if smallPotential has multiple variables,
  //  but it breaks if it's called with two potentials with the same
  //  variables in different orders.
  // TODO: Make work for multiple variables (canonical ordering?)
  private int[] cachedLargeIdxToSmall (MultinomialPotential smallPotential)
  {
    int hashval = computeSubsetHashValue (smallPotential);
    Object ints = projectionCache.get (hashval);
    if (ints != null) {
      return (int[]) ints;
    } else {
      int[] projection = computeLargeIdxToSmall (smallPotential);
      projectionCache.put (hashval, projection);
      return projection;
    }
  }

  /**
   * Returns the marginal of this distribution over the given variables.
   */
  public DiscretePotential marginalize (Variable vars[])
  {
    assert varSet ().containsAll (Arrays.asList (vars)); // Perhaps throw exception instead
    return marginalizeInternal (new MultinomialPotential (vars));
  }

  public DiscretePotential marginalize (Collection vars)
  {
    assert varSet ().containsAll (vars);  // Perhaps throw exception instead
    return marginalizeInternal (new MultinomialPotential (vars));
  }

  public DiscretePotential marginalize (Variable var)
  {
    assert varSet ().contains (var);  // Perhaps throw exception instead
    return marginalizeInternal (new MultinomialPotential
            (new Variable[]{var}));
  }