learnabletokenedaffine.java

来自「wekaUT是 university texas austin 开发的基于wek」· Java 代码 · 共 1,105 行 · 第 1/3 页

/*
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with this program; if not, write to the Free Software
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/*
 *    LearnableTokenEDAffine.java
 *    Copyright (C) 2002-3 Mikhail Bilenko
 *
 */

package weka.deduping.metrics;

import java.text.*;
import java.io.*;
import java.util.*;
import weka.core.*;
import weka.deduping.*;
  

/** LearnableTokenEDAffine class implements a probabilistic model string edit distance with affine-cost gaps
 *
 *   @author Mikhail Bilenko<[e-mail]>
 *   @version 1.1
 **/
public class LearnableTokenEDAffine extends StringMetric implements LearnableStringMetric, Serializable, OptionHandler {

  /** The tokenizer */
  protected Tokenizer m_tokenizer = new WordTokenizer();

  /** A hashmap where observed strings are mapped to their TokenString representations */
  protected HashMap m_stringTokenStringMap = new HashMap();

  /** Parameters for the generative model */
  protected double m_subProb, m_subLogProb, m_subOccs;                           // continuing to match/substitute in state M
  protected double m_endAtSubProb, m_endAtSubLogProb, m_endAtSubOccs;            // ending the alignment at M state
  protected double m_endAtGapProb, m_endAtGapLogProb, m_endAtGapOccs;            // ending the alignment at D/I states
  protected double m_gapStartProb, m_gapStartLogProb, m_gapStartOccs;            // starting a gap in the alignment
  protected double m_gapExtendProb, m_gapExtendLogProb, m_gapExtendOccs;         // extending a gap in the alignment
  protected double m_gapEndProb, m_gapEndLogProb, m_gapEndOccs;                  // ending a gap in the alignment

  /** Emission probs */
  protected double m_matchProb, m_matchLogProb, m_matchOccs;
  protected double m_nonMatchProb, m_nonMatchLogProb, m_nonMatchOccs;
  protected double m_gapTokenProb, m_gapTokenLogProb, m_gapTokenOccs;

  /** parameters for the additive model, obtained from log-probs to speed up
      computations in the "testing" phase after weights have been learned */
  protected double m_matchCost, m_nonMatchCost;
  protected double m_endAtSubCost; 
  protected double m_endAtGapCost; 
  protected double m_gapStartCost;
  protected double m_gapExtendCost;
  protected double m_gapEndCost;
  protected double m_subCost;

  /** true if we are using a generative model for distance in the "testing" phase after learning the parameters
      By default we want to use the additive model that uses probabilities converted to costs*/
  protected boolean m_useGenerativeModel = false;

  /** Maximum number of iterations for training the model; usually converge in <10 iterations */
  protected int m_numIterations = 20;

  /** Normalization of edit distance by string length; equivalent to
    using the posterior probability in the generative model*/
  protected boolean m_normalized = true;

  /** Minimal value of a probability parameter.  Particularly important when
   training sets are small to prevent zero probabilities. */
  protected double m_clampProb = 1e-5;

  /** We can have different ways of converting from distance to similarity  */
  public static final int CONVERSION_LAPLACIAN = 1;
  public static final int CONVERSION_UNIT = 2;
  public static final int CONVERSION_EXPONENTIAL = 4;
  public static final Tag[] TAGS_CONVERSION = {
    new Tag(CONVERSION_UNIT, "similarity = 1-distance"),
    new Tag(CONVERSION_LAPLACIAN, "similarity=1/(1+distance)"),
    new Tag(CONVERSION_EXPONENTIAL, "similarity=exp(-distance)")
      };
  /** The method of converting, by default laplacian */
  protected int m_conversionType = CONVERSION_EXPONENTIAL;

  protected boolean m_verbose = false; 

  /**
   * set up an instance of LearnableTokenEDAffine
   */
  public LearnableTokenEDAffine () {
    initProbs();
    normalizeEmissionProbs();
    normalizeTransitionProbs();
    updateLogProbs();
    initCosts();
  }

  /**
   * Calculate the forward matrices
   * @param _s1 first string
   * @param _s2 second string
   * @return m_endAtSubProb*matrix[l1][l2][0] + m_endAtGapProb(matrix[l1][l2][1] +
   * matrix[l1][l2][2]) extendains the distance value
   */
  protected double[][][] forward (TokenString ts1, TokenString ts2) {
    int [] s1 = ts1.tokenIDs;
    int [] s2 = ts2.tokenIDs;
    int l1 = s1.length, l2 = s2.length;
    double matrix[][][] = new double[l1 + 1][l2 + 1][3];
    double tmpLog, subProb, tmpLog1;

    // initialization - first the substitution/matching matrix
    for (int i = 0; i <=l1; i++) { 
      matrix[i][0][0] = matrix[i][0][1] = matrix[i][0][2] = Double.NEGATIVE_INFINITY;
    }
    for (int j = 1; j <=l2; j++) { 
      matrix[0][j][0] = matrix[0][j][1] = matrix[0][j][2] = Double.NEGATIVE_INFINITY;
    }
    matrix[0][0][0] = 0;
	
    // border rows in insertion/deletion matrices
    for (int i = 1; i <= l1; i++) {
      matrix[i][0][1] = m_gapTokenLogProb + logSum(m_gapExtendLogProb + matrix[i-1][0][1], m_gapStartLogProb + matrix[i-1][0][0]);
    }
    for (int j = 1; j <=l2; j++) {
      matrix[0][j][2] = m_gapTokenLogProb + logSum(m_gapExtendLogProb + matrix[0][j-1][2], m_gapStartLogProb + matrix[0][j-1][0]); 
    }
    
    // fill the matrices
    for (int i = 1; i <= l1; i++) {
      for (int j = 1; j <= l2; j++) {
	matrix[i][j][1] = m_gapTokenLogProb + logSum(m_gapStartLogProb + matrix[i-1][j][0], m_gapExtendLogProb + matrix[i-1][j][1]);
	matrix[i][j][2] = m_gapTokenLogProb + logSum(m_gapStartLogProb + matrix[i][j-1][0], m_gapExtendLogProb + matrix[i][j-1][2]);
	
	subProb = (s1[i-1] == s2[j-1]) ? m_matchLogProb : m_nonMatchLogProb;
	tmpLog1 = logSum(m_subLogProb + matrix[i-1][j-1][0], m_gapEndLogProb + matrix[i-1][j-1][2]);
	tmpLog = logSum(m_gapEndLogProb + matrix[i-1][j-1][1], tmpLog1);
	matrix[i][j][0] =  subProb + tmpLog;
      }
    }
    return matrix;
  }

  /**
   * Calculate the backward matrices
   * @param _s1 first string
   * @param _s2 second string
   * @return matrix[0][0][0] extendains the distance value
   */
  protected double[][][] backward (TokenString ts1, TokenString ts2) {
    int [] s1 = ts1.tokenIDs;
    int [] s2 = ts2.tokenIDs;
    int l1 = s1.length, l2 = s2.length;
    double matrix[][][] = new double[l1 + 1][l2 + 1][3];
    double sub_pairProb, del_charProb, ins_charProb, tmpLog;

    // initialize
    for (int i = 0; i <=l1; i++)
      matrix[i][l2][0] = matrix[i][l2][1] = matrix[i][l2][2] = Double.NEGATIVE_INFINITY;
    for (int j = 0; j <=l2; j++)
      matrix[l1][j][0] = matrix[l1][j][1] = matrix[l1][j][2] = Double.NEGATIVE_INFINITY;
    matrix[l1][l2][0] = m_endAtSubLogProb;
    matrix[l1][l2][1] = matrix[l1][l2][2] = m_endAtGapLogProb;

    // border rows
    for (int i = l1-1; i >= 0; i--) {
      matrix[i][l2][0] = m_gapTokenLogProb + m_gapStartLogProb + matrix[i+1][l2][1];
      matrix[i][l2][1] = m_gapTokenLogProb + m_gapExtendLogProb + matrix[i+1][l2][1];
    }
    for (int j = l2-1; j >= 0; j--) {
      matrix[l1][j][0] = m_gapTokenLogProb + m_gapStartLogProb + matrix[l1][j+1][2];
      matrix[l1][j][2] = m_gapTokenLogProb + m_gapExtendLogProb + matrix[l1][j+1][2];
    }
    
    // fill the rest of the matrix
    for (int i = l1-1; i >= 0; i--) {
      for (int j = l2-1; j >= 0; j--) {
	sub_pairProb = (s1[i] == s2[j]) ? m_matchLogProb : m_nonMatchLogProb;
	matrix[i][j][1] = logSum(m_gapTokenLogProb + m_gapExtendLogProb + matrix[i+1][j][1],
				 sub_pairProb + m_gapEndLogProb + matrix[i+1][j+1][0]);
	matrix[i][j][2] = logSum(m_gapTokenLogProb + m_gapExtendLogProb + matrix[i][j+1][2],
				 sub_pairProb + m_gapEndLogProb + matrix[i+1][j+1][0]);
	tmpLog = logSum(m_gapTokenLogProb + matrix[i+1][j][1], m_gapTokenLogProb + matrix[i][j+1][2]);
	matrix[i][j][0] = logSum(sub_pairProb + m_subLogProb + matrix[i+1][j+1][0],
				 m_gapStartLogProb + tmpLog);
      }
    }
    return matrix;
  }

  /**
   * print out some data in case things go wrong
   */
  protected void printOpProbs() {
    System.out.println("extend_gap_op.prob=" + m_gapExtendProb +
		       "  end_gap_op.prob=" + m_gapEndProb +
		       "  subst_op.prob=" + m_subProb);
  }

  /**
   * print out the three matrices
   */
  public void printMatrices(TokenString ts1, TokenString ts2) {
    double[][][] forward = forward(ts1, ts2);
    double[][][] backward = backward(ts1, ts2);
    int l1 = ts1.tokenIDs.length, l2 = ts2.tokenIDs.length;

    double totalForward = logSum(m_endAtSubLogProb + forward[l1][l2][0], m_endAtGapLogProb + forward[l1][l2][1]);
    totalForward = logSum(totalForward, m_endAtGapLogProb + forward[l1][l2][2]);
    System.out.println("\nB:" + backward[0][0][0] + "\tF:" + totalForward);
    
    System.out.println("\n***FORWARD***\nSUBSTITUTION:");
    printAlignmentMatrix(ts1, ts2, 0, forward);

    System.out.println("\n\nDELETION:");
    printAlignmentMatrix(ts1, ts2, 1, forward);

    System.out.println("\n\nINSERTION:");
    printAlignmentMatrix(ts1, ts2, 2, forward);


    System.out.println("\n***BACKWARD***\nSUBSTITUTION:");
    printAlignmentMatrix(ts1, ts2, 0, backward);

    System.out.println("\n\nDELETION:");
    printAlignmentMatrix(ts1, ts2, 1, backward);

    System.out.println("\n\nINSERTION:");
    printAlignmentMatrix(ts1, ts2, 2, backward);
  }

  public void printAlignmentMatrix(TokenString ts1, TokenString ts2, int idx, double[][][] matrix) {
    DecimalFormat fmt = new DecimalFormat ("0.0000");
    
    System.out.print('\t');
    for (int i = 0; i < ts2.tokenIDs.length; i++) {
      System.out.print("\t" + ts2.tokenIDs[i]);
    }
    System.out.println();
    for (int i = 0; i < matrix.length; i++) {
      if (i > 0) System.out.print(ts1.tokenIDs[i-1] + "\t");  else System.out.print("\t");
      for (int j = 0; j < matrix[i].length; j++) {
	System.out.print(fmt.format(matrix[i][j][idx]) + "\t");
      }
      System.out.println();
    }
  } 
  
        
  /**
   *  Train the distance parameters using provided examples using EM
   * @param matched_pairs Each member is a String[] extendaining two matching fields
   * @param matched_pairs Each member is a String[] extendaining two non-matching fields
   */ 
  public void trainMetric (ArrayList pairList) throws Exception {
    initProbs();
    recordCosts(0);

    // initialize m_stringTokenStringMap
    m_stringTokenStringMap = new HashMap();
    for (int j = 0; j < pairList.size(); j++) {
      StringPair pair = (StringPair)pairList.get(j);
      if (!m_stringTokenStringMap.containsKey(pair.str1)) { 
	m_stringTokenStringMap.put(pair.str1, m_tokenizer.getTokenString(pair.str1));
      }
      if (!m_stringTokenStringMap.containsKey(pair.str2)) { 
	m_stringTokenStringMap.put(pair.str2, m_tokenizer.getTokenString(pair.str2));
      }
//        System.out.println("Pair:\t" + pair.str1 + "\n\t\"" + m_stringTokenStringMap.get(pair.str1) + "\"\n\t" +
//    			 pair.str2 + "\n\t\"" + m_stringTokenStringMap.get(pair.str2) + "\"");
    }

    // initialize the token emission probabilities
    int numTokens = m_stringTokenStringMap.size();
    m_gapTokenProb = 1.0/numTokens;
    normalizeEmissionProbs();
    updateLogProbs();

    try {
      // dump out the current probablities
      PrintWriter out = new PrintWriter(new FileWriter("/tmp/probs1"));
      double totalProb = 0;
      double prevTotalProb = Double.MIN_VALUE;
      for (int i = 1; i <= m_numIterations && Math.abs(totalProb - prevTotalProb) > 1; i++) {
	resetOccurrences();
	out.println(i + ":\t" + m_endAtSubProb + "\t" + m_subProb + "\t" + m_gapStartProb +
		    "\t" + m_endAtGapProb + "\t" + m_gapEndProb + "\t" + m_gapExtendProb + "\t" + m_matchProb);

	// go through positives
	prevTotalProb = totalProb;
	totalProb = 0;
	int shortestIdx = 0; int shortest = 100; 
	for (int j = 0; j < pairList.size(); j++) {
	  StringPair pair = (StringPair)pairList.get(j);
	  if (pair.positive) {
//  	    System.out.println("Pair:\t" + pair.str1 + "\n\t\"" + m_stringTokenStringMap.get(pair.str1) + "\"\n\t" +
//  			 pair.str2 + "\n\t\"" + m_stringTokenStringMap.get(pair.str2) + "\"");
	    totalProb += expectationStep ((TokenString) m_stringTokenStringMap.get(pair.str1),
					  (TokenString) m_stringTokenStringMap.get(pair.str2), 1, true);
	    if (((TokenString) m_stringTokenStringMap.get(pair.str2)).tokenIDs.length < shortest) {
	      shortest = ((TokenString) m_stringTokenStringMap.get(pair.str2)).tokenIDs.length;
	      shortestIdx = j;
	    } 
	  }
	}
	// go through negatives  - TODO - discriminative training
	//	    for (int j = 0; j < negExamples.length; j++)
	//		expectationStep (negExamples[j][1], negExamples[j][0], 1, false);

	if (m_verbose) {
	  DecimalFormat fmt = new DecimalFormat ("0.000");
	  System.out.println("\n" + i + ". Total likelihood=" + fmt.format(totalProb) + ";  prev=" + fmt.format(prevTotalProb));
	  System.out.println("************ Accumulated expectations ******************** ");
	  System.out.println("End_s=" + fmt.format(m_endAtSubOccs) + "\tSub=" + fmt.format(m_subOccs) +
			     "\tStGap=" + fmt.format(m_gapStartOccs) + "\nEnd_g=" + fmt.format(m_endAtGapOccs) +
			     "\tEndGap=" + fmt.format(m_gapEndOccs) + " ContGap=" + fmt.format(m_gapExtendOccs) +
			     "\nmatch=" + fmt.format(m_matchOccs) + "\tnonMatch=" + fmt.format(m_nonMatchOccs));
	  System.out.println("********************************");
	}
	maximizationStep ();
//  	StringPair pair = (StringPair)pairList.get(shortestIdx);
//  	printMatrices((TokenString) m_stringTokenStringMap.get(pair.str1),(TokenString) m_stringTokenStringMap.get(pair.str1));
      }
      out.close();
    } catch (Exception e) { e.printStackTrace();}
    initCosts();
    recordCosts(1);
  }
    
  /**
   * Expectation  part of the EM algorithm
   *  accumulates expectations of editop probabilities over example pairs
   *  Expectation is calculated based on two examples which are either duplicates (pos=true)
   *  or non-duplicates (pos=false).  Lambda is a weighting parameter, 1 by default.
   * @param _s1 first string
   * @param _s2 second string
   * @param lambda learning rate parameter, 1 by default
   * @param pos_training true if strings are matched, false if mismatched
   */
  protected double expectationStep (TokenString ts1, TokenString ts2, int lambda, boolean pos_training) {
    int [] s1 = ts1.tokenIDs;
    int [] s2 = ts2.tokenIDs;
    int l1 = s1.length, l2 = s2.length;
    if (l1 == 0 || l2 == 0) {
      return 0;
    }
    double fMatrix[][][] = forward (ts1, ts2);
    double bMatrix[][][] = backward (ts1, ts2);
    double stringProb = bMatrix[0][0][0];
//NB: b[0][0][0]must be equal to endAtSub*f[l1][l2][0] + endAtGap*(f[l1][l2][1]+f[l1][l2][2]); uncomment below for sanity check
//      double totalForward = logSum(m_endAtSubLogProb + fMatrix[l1][l2][0], m_endAtSubLogProb + fMatrix[l1][l2][1]);
//      totalForward = logSum(totalForward, m_endAtSubLogProb + fMatrix[l1][l2][2]);
//      System.out.println("b:" + bMatrix[0][0][0] + "\tf:" + totalForward);    

    double occsSubst, occsStartGap_1, occsStartGap_2, occsExtendGap_1, occsExtendGap_2;
    double occsEndGap_1, occsEndGap_2;
    double subTokenLogProb;
    int s1_i, s2_j;