* Command-line usage: java Options [properties.txt] -param [val] ... * properties.txt - optional file in Properties format * param - property name * val - value for that property (set to null if not present) ** @author Alex * @version VERSIONDATA */ public class Options extends java.util.Properties { public static Options parse(String[] args) { Options o = new Options(args); return o; } ////////// /** @serial **/ protected String[] args; public boolean appendValues = false; public Options(Properties defaults, String[] args) { super(defaults); this.args = args; parse(); } public Options(String[][] defaults, String[] args) { Properties def = new Properties(); for (int i=0; i
This implementation of CRF is as described in the following two papers.
The code relies on a sparse matrix operations available from the COLT distribution and an implementation of the Quasi-Newton optimization algorithm (LBFGS) available under the package name riso.numerical
The basic package is intentionally kept barebones without any code for
data input/output and feature design. Before you can start using the
package you need to provide implementations of the FeatureGenerator
and DataIter classes. The best way to learn how to use this code is
to examples in the package @see iitb.usingCRFs.Segment for Sequence
annotations and @see iitb.usingCRFs.MaxentClassifier for a basic
maximum entropy based classifier.
@author Sunita Sarawagi, IIT Bombay (sunita@iitb.ac.in)
CRF/src/iitb/CRF/SegmentViterbi.java 0000644 0001760 0001760 00000031755 10421544045 020046 0 ustar abhisheka abhisheka package iitb.CRF;
import gnu.trove.TIntFloatHashMap;
import gnu.trove.TIntHashSet;
import gnu.trove.TIntProcedure;
import java.util.Iterator;
import java.util.TreeSet;
/**
*
* @author Sunita Sarawagi
*
*/
public class SegmentViterbi extends SparseViterbi {
protected SegmentCRF segmentModel;
static class LabelConstraints {
private static final long serialVersionUID = 1L;
ConstraintDisallowedPairs disallowedPairs;
class Intersects implements TIntProcedure {
int label;
int prevLabel;
public boolean execute(int arg0) {
return !disallowedPairs.conflictingPair(label,arg0,(arg0==prevLabel));
}
}
Intersects intersectTest = new Intersects();
/**
* @param pairs
*/
public LabelConstraints(ConstraintDisallowedPairs pairs) {
disallowedPairs = pairs;
}
/**
* @param set
* @param prevLabel
* @param i
* @return
*/
private boolean valid(TIntHashSet set, int label, int prevLabel) {
if (!conflicting(label))
return true;
if (disallowedPairs.conflictingPair(label,prevLabel,true))
return false;
intersectTest.label = label;
intersectTest.prevLabel = prevLabel;
return set.forEach(intersectTest);
}
/**
* @param dataSeq
* @return
*/
public static LabelConstraints checkConstraints(CandSegDataSequence dataSeq, LabelConstraints labelCons) {
Iterator constraints = dataSeq.constraints(-1,dataSeq.length());
if (constraints != null) {
for (; constraints.hasNext();) {
Constraint constraint = (Constraint)constraints.next();
if (constraint.type() == Constraint.PAIR_DISALLOW) {
if (labelCons != null) {
labelCons.disallowedPairs = (ConstraintDisallowedPairs)constraint;
return labelCons;
} else
return new LabelConstraints((ConstraintDisallowedPairs)constraint);
}
}
}
return null;
}
/**
* @param label
* @return
*/
public boolean conflicting(int label) {
return disallowedPairs.conflicting(label);
}
}
LabelConstraints labelConstraints=null;
class SolnWithLabelsOnPath extends Soln {
void clear() {
super.clear();
labelsOnPath.clear();
}
protected void copy(Soln soln) {
super.copy(soln);
labelsOnPath.clear();
labelsOnPath.addAll(((SolnWithLabelsOnPath)soln).labelsOnPath.toArray());
}
private static final long serialVersionUID = 1L;
TIntHashSet labelsOnPath;
/**
* @param id
* @param p
*/
SolnWithLabelsOnPath(int id, int p) {
super(id, p);
labelsOnPath = new TIntHashSet();
}
protected void setPrevSoln(Soln prevSoln, float score) {
super.setPrevSoln(prevSoln,score);
if ((prevSoln != null) && (labelConstraints != null)) {
labelsOnPath.clear();
labelsOnPath.addAll(((SolnWithLabelsOnPath)prevSoln).labelsOnPath.toArray());
assert(labelConstraints.valid(labelsOnPath,label,prevSoln.label));
if (labelConstraints.conflicting(prevSoln.label))
labelsOnPath.add(prevSoln.label);
}
}
}
class EntryForLabelConstraints extends Entry {
/**
* @param beamsize
* @param id
* @param pos
*/
EntryForLabelConstraints(int beamsize, int id, int pos) {
super();
solns = new Soln[beamsize];
for (int i = 0; i < solns.length; i++)
solns[i] = new SolnWithLabelsOnPath(id, pos);
}
protected int findInsert(int insertPos, float score, Soln prev) {
for (; insertPos < size(); insertPos++) {
if (score >= get(insertPos).score) {
if ((prev == null) || labelConstraints.valid(((SolnWithLabelsOnPath)prev).labelsOnPath,get(insertPos).label, prev.label)) {
insert(insertPos, score, prev);
insertPos++;
} else if (prev != null) {
// System.out.println("Constraint violation");
}
break;
}
}
return insertPos;
}
}
class ContextForLabelConstraints extends Context {
ContextForLabelConstraints(int numY, int beamsize, int pos) {
super(numY, beamsize, pos);
}
private static final long serialVersionUID = 1L;
public void add(int y, Entry prevSoln, float thisScore) {
if (labelConstraints==null) {
super.add(y,prevSoln,thisScore);
} else {
if (getQuick(y) == null) {
setQuick(y, new EntryForLabelConstraints((pos==0)?1:beamsize, y, pos));
}
super.add(y,prevSoln,thisScore);
}
}
}
protected SegmentViterbi(SegmentCRF nestedModel, int bs) {
super(nestedModel, bs);
this.segmentModel = nestedModel;
}
protected void computeLogMi(DataSequence dataSeq, int i, int ell, double lambda[]) {
SegmentTrainer.computeLogMi((CandSegDataSequence)dataSeq,i-ell,i,segmentModel.featureGenNested,lambda,Mi,Ri);
}
class SegmentIter extends Iter {
int nc;
CandidateSegments candidateSegs;
protected void start(int i, DataSequence dataSeq) {
candidateSegs = (CandidateSegments)dataSeq;
nc = candidateSegs.numCandSegmentsEndingAt(i);
}
protected int nextEll(int i) {
nc--;
if (nc >= 0)
return i - candidateSegs.candSegmentStart(i,nc) + 1;
return -1;
}
}
protected Iter getIter(){return new SegmentIter();}
/**
* @return
*/
int prevSegEnd = -1;
protected double getCorrectScore(DataSequence dataSeq, int i, int ell) {
SegmentDataSequence data = (SegmentDataSequence)dataSeq;
if (data.getSegmentEnd(i-ell+1) != i)
return 0;
if ((i - ell >= 0) && (prevSegEnd != i-ell))
return RobustMath.LOG0;
prevSegEnd = i;
if ((labelConstraints != null) && labelConstraints.conflicting(data.y(i))) {
for (int segStart = 0; segStart < i-ell+1; segStart = data.getSegmentEnd(segStart)+1) {
int segEnd = data.getSegmentEnd(segStart);
if (labelConstraints.disallowedPairs.conflictingPair(data.y(i),data.y(segStart),segEnd==i-ell))
return RobustMath.LOG0;
}
}
if (model.params.debugLvl > 0) {
// output features that hold
segmentModel.featureGenNested.startScanFeaturesAt(dataSeq,i-ell,i);
while (segmentModel.featureGenNested.hasNext()) {
Feature f = segmentModel.featureGenNested.next();
if (((CandSegDataSequence)data).holdsInTrainingData(f,i-ell,i)) {
System.out.println("Feature " + (i-ell) + " " + i + " " + segmentModel.featureGenerator.featureName(f.index()) + " " + segmentModel.lambda[f.index()] + " " + f.value());
}
}
}
double val = (Ri.getQuick(dataSeq.y(i)) + ((i-ell >= 0)?Mi.get(dataSeq.y(i-ell),dataSeq.y(i)):0));
if (Double.isInfinite(val)) {
System.out.println("Infinite score");
}
return val;
}
protected void setSegment(DataSequence dataSeq, int prevPos, int pos, int label) {
((CandSegDataSequence)dataSeq).setSegment(prevPos+1,pos, label);
}
public void singleSegmentClassScores(CandSegDataSequence dataSeq, double lambda[], TIntFloatHashMap scores) {
viterbiSearch(dataSeq, lambda,false);
scores.clear();
int i = dataSeq.length()-1;
if (i >= 0) {
double norm = RobustMath.LOG0;
for (int y = 0; y < context[i].size(); y++) {
if (context[i].entryNotNull(y)) {
Soln soln = ((Entry)context[i].getQuick(y)).get(0);
assert (soln.prevSoln == null); // only applicable for single segment.
norm = RobustMath.logSumExp(norm,soln.score);
}
}
for (int y = 0; y < context[i].size(); y++) {
if (context[i].entryNotNull(y)) {
Soln soln = ((Entry)context[i].getQuick(y)).get(0);
scores.put(soln.label,(float)Math.exp(soln.score-norm));
}
}
/*context[i].getNonZeros(validPrevYs, prevContext);
for (int prevPx = 0; prevPx < validPrevYs.size(); prevPx++) {
Soln soln = ((Entry)prevContext.getQuick(prevPx)).get(0);
assert (soln.prevSoln == null); // only applicable for single segment.
norm = RobustMath.logSumExp(norm,soln.score);
}
for (int prevPx = 0; prevPx < validPrevYs.size(); prevPx++) {
Soln soln = ((Entry)prevContext.getQuick(prevPx)).get(0);
scores.put(soln.label,(float)Math.exp(soln.score-norm));
}
*/
}
}
protected Context newContext(int numY, int beamsize, int pos){
if (labelConstraints == null)
return new Context(numY,beamsize,pos);
return new ContextForLabelConstraints(numY,(beamsize==1)?20:beamsize,pos);
}
public double viterbiSearch(DataSequence dataSeq, double[] lambda,
boolean calcCorrectScore) {
labelConstraints = LabelConstraints.checkConstraints((CandSegDataSequence)dataSeq, labelConstraints);
return super.viterbiSearch(dataSeq, lambda, calcCorrectScore);
}
class SegmentationImpl implements Segmentation {
class Segment implements Comparable {
int start;
int end;
int label;
int id;
Segment(int start, int end, int label) {
this.start = start;
this.end = end;
this.label = label;
}
/* (non-Javadoc)
* @see java.lang.Comparable#compareTo(java.lang.Object)
*/
public int compareTo(Object arg0) {
return end - ((Segment)arg0).end;
}
}
TreeSet segments = new TreeSet();
Segment segmentArr[]=null;
Segment dummySegment = new Segment(0,0,0);
/* (non-Javadoc)
* @see iitb.CRF.Segmentation#numSegments()
*/
public int numSegments() {
return segments.size();
}
/* (non-Javadoc)
* @see iitb.CRF.Segmentation#segmentLabel(int)
*/
public int segmentLabel(int segmentNum) {
return segmentArr[segmentNum].label;
}
/* (non-Javadoc)
* @see iitb.CRF.Segmentation#segmentStart(int)
*/
public int segmentStart(int segmentNum) {
return segmentArr[segmentNum].start;
}
/* (non-Javadoc)
* @see iitb.CRF.Segmentation#segmentEnd(int)
*/
public int segmentEnd(int segmentNum) {
return segmentArr[segmentNum].end;
}
/* (non-Javadoc)
* @see iitb.CRF.Segmentation#getSegmentId(int)
*/
public int getSegmentId(int offset) {
dummySegment.end = offset;
// if (segments.headSet(dummySegment) == null)
// return 0;
return ((Segment)segments.tailSet(dummySegment).first()).id;
}
/* (non-Javadoc)
* @see iitb.CRF.Segmentation#setSegment(int, int, int)
*/
public void setSegment(int segmentStart, int segmentEnd, int label) {
Segment segment = new Segment(segmentStart, segmentEnd, label);
boolean b = segments.add(segment);
}
public void doneAdd() {
segmentArr = new Segment[segments.size()];
int p = 0;
for (Iterator iter = segments.iterator(); iter.hasNext();) {
segmentArr[p++] = (Segment) iter.next();
}
for (int i = segmentArr.length-1; i >= 0; segmentArr[i].id = i, i--);
}
};
public Segmentation[] segmentSequences(CandSegDataSequence dataSeq, double lambda[], int numLabelSeqs) {
viterbiSearch(dataSeq, lambda,false);
int numSols = Math.min(finalSoln.numSolns(), numLabelSeqs);
Segmentation segments[] = new Segmentation[numSols];
for (int k = numSols-1; k >= 0; k--) {
Soln ybest = finalSoln.get(k);
ybest = ybest.prevSoln;
segments[k] = new SegmentationImpl();
while (ybest != null) {
segments[k].setSegment(ybest.prevPos()+1,ybest.pos,ybest.label);
ybest = ybest.prevSoln;
}
((SegmentationImpl)segments[k]).doneAdd();
}
return segments;
}
};
CRF/src/iitb/CRF/CrfParams.java 0000644 0001760 0001760 00000006371 10421544046 016772 0 ustar abhisheka abhisheka package iitb.CRF;
import java.io.Serializable;
import java.util.StringTokenizer;
/**
* This class holds all parameters to control various aspects of the CRF model
*
* @author Sunita Sarawagi
*
*/
public class CrfParams implements Serializable {
/** initial value for all the lambda arrays */
public double initValue = 0;
/** penalty term for likelihood function is ||lambda||^2*invSigmaSquare/2
set this to zero, if no penalty needed
*/
public double invSigmaSquare = 0.01;
/** Maximum number of iterations over the training data during training */
public int maxIters = 100;
/** Convergence criteria for finding optimum lambda using BFGS */
public double epsForConvergence = 0.001;
/** The number of corrections used in the BFGS update. */
public int mForHessian = 7;
public String trainerType = "";
public int debugLvl = 1; // controls amount of status information output
public boolean doScaling = true;
public boolean doRobustScale = false;
public boolean reuseM = false;
public java.util.Properties miscOptions;
/**
* constructor with default values as follows.
* initValue = 0;
* invSigmaSquare = 1.0;
* maxIters = 50;
* epsForConvergence = 0.0001;
* mForHessian = 7;
* trainerType = "";
* debugLvl = 1;
*/
public CrfParams() {}
/** Initialize any parameter using space separated list of name value pairs
* Example: "initValue 0.1 maxIters 20"
* will set the initValue param to 0.1 and maxIters param to 20.
*/
public CrfParams(String args) {
this(stringToOptions(args));
}
static java.util.Properties stringToOptions(String args) {
java.util.Properties opts = new java.util.Properties();
StringTokenizer tok = new StringTokenizer(args, " ");
while (tok.hasMoreTokens()) {
String name = tok.nextToken();
String value = tok.nextToken();
opts.put(name,value);
}
return opts;
}
public CrfParams(java.util.Properties opts) {
parseParameters(opts);
}
public void parseParameters(java.util.Properties opts) {
miscOptions = opts;
if (opts.getProperty("initValue") != null) {
initValue = Double.parseDouble(opts.getProperty("initValue"));
}
if (opts.getProperty("maxIters") != null) {
maxIters = Integer.parseInt(opts.getProperty("maxIters"));
}
if (opts.getProperty("invSigmaSquare") != null) {
invSigmaSquare = Double.parseDouble(opts.getProperty("invSigmaSquare"));
}
if (opts.getProperty("debugLvl") != null) {
debugLvl = Integer.parseInt(opts.getProperty("debugLvl"));
}
if (opts.getProperty("scale") != null) {
doScaling = opts.getProperty("scale").equalsIgnoreCase("true");
}
if (opts.getProperty("robustScale") != null) {
doRobustScale = opts.getProperty("robustScale").equalsIgnoreCase("true");
}
if (opts.getProperty("epsForConvergence") != null) {
epsForConvergence = Double.parseDouble(opts.getProperty("epsForConvergence"));
}
if (opts.getProperty("mForHessian") != null) {
mForHessian = Integer.parseInt(opts.getProperty("mForHessian"));
}
if (opts.getProperty("trainer") != null) {
trainerType = opts.getProperty("trainer");
}
reuseM = Boolean.valueOf(opts.getProperty("reuseM","false")).booleanValue();
}
};
CRF/src/iitb/CRF/CandidateSegments.java 0000644 0001760 0001760 00000000553 10421454646 020500 0 ustar abhisheka abhisheka /*
* Created on Nov 18, 2004
*
*/
package iitb.CRF;
/**
* @author sunita
*
*/
public interface CandidateSegments {
/**
* The number of candidate segments ending at given position
*/
int numCandSegmentsEndingAt(int endPos);
/**
* The start position of the segNum-th segment ending at "endPos"
*/
int candSegmentStart(int endPos, int segNum);
}
CRF/src/iitb/CRF/LogDenseDoubleMatrix1D.java 0000644 0001760 0001760 00000006330 10421544053 021312 0 ustar abhisheka abhisheka package iitb.CRF;
import java.util.TreeSet;
import cern.colt.function.DoubleDoubleFunction;
import cern.colt.function.IntDoubleFunction;
import cern.colt.matrix.DoubleMatrix1D;
import cern.colt.matrix.DoubleMatrix2D;
import cern.colt.matrix.impl.DenseDoubleMatrix1D;
import cern.colt.matrix.impl.DenseDoubleMatrix2D;
//this needs to be done to support an efficient sparse implementation
//of matrices in the log-space
public class LogDenseDoubleMatrix1D extends DenseDoubleMatrix1D {
static double map(double val) {
if (val == RobustMath.LOG0)
return 0;
if (val == 0)
return Double.MIN_VALUE;
return val;
}
static double reverseMap(double val) {
if (val == 0) {
return RobustMath.LOG0;
}
if (val == Double.MIN_VALUE)
return 0;
return val;
}
public LogDenseDoubleMatrix1D(int numY) {super(numY);}
public DoubleMatrix1D assign(double val) {
return super.assign(map(val));
}
public void set(int row, double val) {
super.set(row,map(val));
}
public double get(int row) {
return reverseMap(super.get(row));
}
public double zSum() {
TreeSet logProbVector = new TreeSet();
// TODO
for (int row = 0; row < size(); row++) {
if (getQuick(row) != 0)
RobustMath.addNoDups(logProbVector,get(row));
}
return RobustMath.logSumExp(logProbVector);
}
// WARNING: this is only correct for functions that leave the infinity unchanged.
public DoubleMatrix1D forEachNonZero(IntDoubleFunction func) {
for (int y = 0; y < size(); y++) {
if (getQuick(y) != 0)
setQuick(y,func.apply(y,get(y)));
}
return this;
}
// WARNING: this is only correct for functions that leave the infinity unchanged.
public DoubleMatrix1D assign(DoubleMatrix1D v2, DoubleDoubleFunction func) {
// TODO..
for (int row = 0; row < size(); row++) {
if ((v2.getQuick(row) != 0) || (getQuick(row) != 0))
set(row,func.apply(get(row), v2.get(row)));
}
return this;
}
public boolean equals(Object arg) {
DoubleMatrix1D mat = (DoubleMatrix1D)arg;
for (int row = size()-1; row >= 0; row--)
if (Math.abs(mat.get(row)-get(row))/Math.abs(mat.get(row)) > 0.0001)
return false;
return true;
}
};
class LogDenseDoubleMatrix2D extends DenseDoubleMatrix2D {
static double map(double val) { return LogSparseDoubleMatrix1D.map(val);}
static double reverseMap(double val) { return LogSparseDoubleMatrix1D.reverseMap(val);}
LogDenseDoubleMatrix2D(int numR, int numC) {super(numR,numC);
}
public DoubleMatrix2D assign(double val) {
return super.assign(map(val));
}
public void set(int row, int column, double val) {
super.set(row,column,map(val));
}
public double get(int row, int column) {
return reverseMap(super.get(row,column));
}
public DoubleMatrix1D zMult(DoubleMatrix1D y, DoubleMatrix1D z, double alpha, double beta, boolean transposeA) {
return RobustMath.logMult(this,y,z,alpha,beta,transposeA);
}
};
CRF/src/iitb/CRF/SegmentTrainer.java 0000644 0001760 0001760 00000035423 10421544045 020042 0 ustar abhisheka abhisheka package iitb.CRF;
import java.util.Iterator;
import cern.colt.matrix.DoubleMatrix1D;
import cern.colt.matrix.DoubleMatrix2D;
/**
*
* @author Sunita Sarawagi
*
*/
public class SegmentTrainer extends SparseTrainer {
protected DoubleMatrix1D alpha_Y_Array[];
protected DoubleMatrix1D alpha_Y_ArrayM[];
protected boolean initAlphaMDone[];
protected DoubleMatrix1D allZeroVector;
public SegmentTrainer(CrfParams p) {
super(p);
logTrainer = true;
}
protected void init(CRF model, DataIter data, double[] l) {
super.init(model,data,l);
allZeroVector = newLogDoubleMatrix1D(numY);
allZeroVector.assign(0);
}
protected double computeFunctionGradient(double lambda[], double grad[]) {
try {
FeatureGeneratorNested featureGenNested = (FeatureGeneratorNested)featureGenerator;
double logli = 0;
for (int f = 0; f < lambda.length; f++) {
grad[f] = -1*lambda[f]*params.invSigmaSquare;
logli -= ((lambda[f]*lambda[f])*params.invSigmaSquare)/2;
}
diter.startScan();
initMDone=false;
if (featureGenCache != null) featureGenCache.startDataScan();
int numRecord;
for (numRecord = 0; diter.hasNext(); numRecord++) {
CandSegDataSequence dataSeq = (CandSegDataSequence)diter.next();
if (featureGenCache != null) featureGenCache.nextDataIndex();
if (params.debugLvl > 1)
Util.printDbg("Read next seq: " + numRecord + " logli " + logli);
for (int f = 0; f < lambda.length; f++)
ExpF[f] = RobustMath.LOG0;
int base = -1;
if ((alpha_Y_Array == null) || (alpha_Y_Array.length < dataSeq.length()-base)) {
allocateAlphaBeta(2*dataSeq.length()+1);
}
if (reuseM)
for (int i = dataSeq.length(); i >= 0; i--)
initAlphaMDone[i] = false;
int dataSize = dataSeq.length();
DoubleMatrix1D oldBeta = beta_Y[dataSeq.length()-1];
beta_Y[dataSeq.length()-1] = allZeroVector;
for (int i = dataSeq.length()-2; i >= 0; i--) {
beta_Y[i].assign(RobustMath.LOG0);
}
CandidateSegments candidateSegs = (CandidateSegments)dataSeq;
for (int segEnd = dataSeq.length()-1; segEnd >= 0; segEnd--) {
for (int nc = candidateSegs.numCandSegmentsEndingAt(segEnd)-1; nc >= 0; nc--) {
int segStart = candidateSegs.candSegmentStart(segEnd,nc);
int ell = segEnd-segStart+1;
int i = segStart-1;
if (i < 0)
continue;
// compute the Mi matrix
initMDone = computeLogMi(dataSeq,i,i+ell,featureGenNested,lambda,Mi_YY,Ri_Y,reuseM,initMDone);
tmp_Y.assign(Ri_Y);
if (i+ell < dataSize-1) tmp_Y.assign(beta_Y[i+ell], sumFunc);
if (!reuseM) Mi_YY.zMult(tmp_Y, beta_Y[i],1,1,false);
else beta_Y[i].assign(tmp_Y, RobustMath.logSumExpFunc);
}
if (reuseM && (segEnd-1 >= 0)) {
tmp_Y.assign(beta_Y[segEnd-1]);
Mi_YY.zMult(tmp_Y, beta_Y[segEnd-1],1,0,false);
}
}
double thisSeqLogli = 0;
alpha_Y_Array[0] = allZeroVector; //.assign(0);
int trainingSegmentEnd=-1;
int trainingSegmentStart = 0;
boolean trainingSegmentFound = true;
boolean noneFired=true;
for (int segEnd = 0; segEnd < dataSize; segEnd++) {
alpha_Y_Array[segEnd-base].assign(RobustMath.LOG0);
if (trainingSegmentEnd < segEnd) {
if ((!trainingSegmentFound)&& noneFired) {
System.out.println("Error: Training segment ("+trainingSegmentStart + " "+ trainingSegmentEnd + ") not found amongst candidate segments");
}
trainingSegmentFound = false;
trainingSegmentStart = segEnd;
trainingSegmentEnd =((SegmentDataSequence)dataSeq).getSegmentEnd(segEnd);
}
for (int nc = candidateSegs.numCandSegmentsEndingAt(segEnd)-1; nc >= 0; nc--) {
int ell = segEnd - candidateSegs.candSegmentStart(segEnd,nc)+1;
// compute the Mi matrix
initMDone=computeLogMi(dataSeq,segEnd-ell,segEnd,featureGenNested,lambda,Mi_YY,Ri_Y,reuseM,initMDone);
boolean mAdded = false, rAdded = false;
if (segEnd-ell >= 0) {
if (!reuseM) Mi_YY.zMult(alpha_Y_Array[segEnd-ell-base],newAlpha_Y,1,0,true);
else {
if (!initAlphaMDone[segEnd-ell-base]) {
alpha_Y_ArrayM[segEnd-ell-base].assign(RobustMath.LOG0);
Mi_YY.zMult(alpha_Y_Array[segEnd-ell-base],alpha_Y_ArrayM[segEnd-ell-base],1,0,true);
initAlphaMDone[segEnd-ell-base] = true;
}
newAlpha_Y.assign(alpha_Y_ArrayM[segEnd-ell-base]);
}
newAlpha_Y.assign(Ri_Y,sumFunc);
} else
newAlpha_Y.assign(Ri_Y);
alpha_Y_Array[segEnd-base].assign(newAlpha_Y, RobustMath.logSumExpFunc);
// find features that fire at this position..
featureGenNested.startScanFeaturesAt(dataSeq, segEnd-ell,segEnd);
while (featureGenNested.hasNext()) {
Feature feature = featureGenNested.next();
int f = feature.index();
int yp = feature.y();
int yprev = feature.yprev();
float val = feature.value();
if (dataSeq.holdsInTrainingData(feature,segEnd-ell,segEnd)) {
grad[f] += val;
thisSeqLogli += val*lambda[f];
noneFired=false;
/*
double lZx = alpha_Y_Array[i-base].zSum();
if ((thisSeqLogli > lZx) || (numRecord == 3)) {
System.out.println("This is shady: something is wrong Pr(y|x) > 1!");
System.out.println("Sequence likelihood " + thisSeqLogli + " " + lZx + " " + Math.exp(lZx));
System.out.println("This Alpha-i " + alpha_Y_Array[i-base].toString());
}
*/
if (params.debugLvl > 2) {
System.out.println("Feature fired " + f + " " + feature);
}
}
if (yprev < 0) {
ExpF[f] = RobustMath.logSumExp(ExpF[f], (newAlpha_Y.get(yp)+RobustMath.log(val)+beta_Y[segEnd].get(yp)));
} else {
ExpF[f] = RobustMath.logSumExp(ExpF[f], (alpha_Y_Array[segEnd-ell-base].get(yprev)+Ri_Y.get(yp)+Mi_YY.get(yprev,yp)+RobustMath.log(val)+beta_Y[segEnd].get(yp)));
}
}
if ((segEnd == trainingSegmentEnd) && (segEnd-ell+1==trainingSegmentStart)) {
trainingSegmentFound = true;
double val1 = Ri_Y.get(dataSeq.y(trainingSegmentEnd));
double val2 = 0;
if (trainingSegmentStart > 0) {
val2 = Mi_YY.get(dataSeq.y(trainingSegmentStart-1), dataSeq.y(trainingSegmentEnd));
}
if ((val1 == RobustMath.LOG0) || (val2 == RobustMath.LOG0)) {
System.out.println("Error: training labels not covered in generated features " + val1 + " "+val2
+ " yprev " + dataSeq.y(trainingSegmentStart-1) + " y " + dataSeq.y(trainingSegmentEnd));
System.out.println(dataSeq);
featureGenNested.startScanFeaturesAt(dataSeq, segEnd-ell,segEnd);
while (featureGenNested.hasNext()) {
Feature feature = featureGenNested.next();
System.out.println(feature + " " + feature.yprev() + " "+feature.y());
}
}
}
}
if (params.debugLvl > 2) {
System.out.println("Alpha-i " + alpha_Y_Array[segEnd-base].toString());
System.out.println("Ri " + Ri_Y.toString());
System.out.println("Mi " + Mi_YY.toString());
System.out.println("Beta-i " + beta_Y[segEnd].toString());
}
}
double lZx = alpha_Y_Array[dataSeq.length()-1-base].zSum();
thisSeqLogli -= lZx;
logli += thisSeqLogli;
// update grad.
for (int f = 0; f < grad.length; f++)
grad[f] -= expLE(ExpF[f]-lZx);
if (noneFired) {
System.out.println("WARNING: no features fired in the training set");
}
if (thisSeqLogli > 0) {
System.out.println("ERROR: something is wrong Pr(y|x) > 1! for sequence " + numRecord);
System.out.println(dataSeq);
}
if (params.debugLvl > 1 || (thisSeqLogli > 0)) {
System.out.println("Sequence likelihood " + thisSeqLogli + " lZx " + lZx + " Zx " + Math.exp(lZx));
System.out.println("Last Alpha-i " + alpha_Y_Array[dataSeq.length()-1-base].toString());
}
beta_Y[dataSeq.length()-1] = oldBeta;
}
if (params.debugLvl > 2) {
for (int f = 0; f < lambda.length; f++)
System.out.print(lambda[f] + " ");
System.out.println(" :x");
for (int f = 0; f < lambda.length; f++)
System.out.println(f + " " + featureGenNested.featureName(f) + " " + grad[f] + " ");
System.out.println(" :g");
}
if (params.debugLvl > 0) {
if (icall == 0) {
Util.printDbg("Number of training records " + numRecord);
}
Util.printDbg("Iter " + icall + " loglikelihood "+logli + " gnorm " + norm(grad) + " xnorm "+ norm(lambda));
}
return logli;
} catch (Exception e) {
e.printStackTrace();
System.exit(0);
}
return 0;
}
/**
* @param i
*/
protected void allocateAlphaBeta(int newSize) {
alpha_Y_Array = new DoubleMatrix1D[newSize];
for (int i = 0; i < alpha_Y_Array.length; i++)
alpha_Y_Array[i] = newLogDoubleMatrix1D(numY);
beta_Y = new DoubleMatrix1D[newSize];
for (int i = 0; i < beta_Y.length; i++)
beta_Y[i] = newLogDoubleMatrix1D(numY);
alpha_Y_ArrayM = new DoubleMatrix1D[newSize];
for (int i = 0; i < alpha_Y_ArrayM.length; i++)
alpha_Y_ArrayM[i] = newLogDoubleMatrix1D(numY);
initAlphaMDone = new boolean[newSize];
}
// TODO..
public static double initLogMi(CandSegDataSequence dataSeq, int prevPos, int pos,
FeatureGeneratorNested featureGenNested, double[] lambda, DoubleMatrix2D Mi, DoubleMatrix1D Ri) {
featureGenNested.startScanFeaturesAt(dataSeq,prevPos,pos);
Iterator constraints = dataSeq.constraints(prevPos,pos);
double defaultValue = RobustMath.LOG0;
if (Mi != null) Mi.assign(defaultValue);
Ri.assign(defaultValue);
if (constraints != null) {
for (; constraints.hasNext();) {
Constraint constraint = (Constraint)constraints.next();
if (constraint.type() == Constraint.ALLOW_ONLY) {
RestrictConstraint cons = (RestrictConstraint)constraint;
/*
for (int c = cons.numAllowed()-1; c >= 0; c--) {
Ri.set(cons.allowed(c),0);
}
*/
for (cons.startScan(); cons.hasNext();) {
cons.advance();
int y = cons.y();
int yprev = cons.yprev();
if (yprev < 0) {
Ri.set(y,0);
} else {
if (Mi != null) Mi.set(yprev,y,0);
}
}
}
}
} else {
defaultValue = 0;
if (Mi != null) Mi.assign(defaultValue);
Ri.assign(defaultValue);
}
return defaultValue;
}
static boolean computeLogMi(CandSegDataSequence dataSeq, int prevPos, int pos,
FeatureGeneratorNested featureGenNested,
double[] lambda, DoubleMatrix2D Mi, DoubleMatrix1D Ri,
boolean reuseM, boolean initMDone) {
if (reuseM && initMDone)
Mi = null;
computeLogMi(dataSeq, prevPos, pos, featureGenNested,lambda,Mi,Ri);
if ((prevPos >= 0) && reuseM) {
initMDone = true;
//((FeatureGeneratorNestedSameTransitions)featureGenNested).transitionsCached();
}
return initMDone;
}
static void computeLogMi(CandSegDataSequence dataSeq, int prevPos, int pos,
FeatureGeneratorNested featureGenNested, double[] lambda, DoubleMatrix2D Mi, DoubleMatrix1D Ri) {
double defaultValue = initLogMi(dataSeq, prevPos,pos,featureGenNested,lambda,Mi,Ri);
SparseTrainer.computeLogMiInitDone(featureGenNested,lambda,Mi,Ri,defaultValue);
}
};
CRF/src/iitb/CRF/NestedCollinsTrainer.java 0000644 0001760 0001760 00000001070 10421454646 021204 0 ustar abhisheka abhisheka package iitb.CRF;
/**
* Implements the CollinsVotedPerceptron training algorithm
*
* @author Sunita Sarawagi
*
*/
class NestedCollinsTrainer extends CollinsTrainer {
public NestedCollinsTrainer(CrfParams p) {
super(p);
}
int getSegmentEnd(DataSequence dataSeq, int ss) {
return ((SegmentDataSequence)dataSeq).getSegmentEnd(ss);
}
void startFeatureGenerator(FeatureGenerator _featureGenerator, DataSequence dataSeq, Soln soln) {
((FeatureGeneratorNested)_featureGenerator).startScanFeaturesAt(dataSeq, soln.prevPos(), soln.pos);
}
};
CRF/src/iitb/CRF/Feature.java 0000644 0001760 0001760 00000001156 10421454646 016511 0 ustar abhisheka abhisheka package iitb.CRF;
/**
* A single feature returned by the FeatureGenerator needs to support this interface.
* @author Sunita Sarawagi
*
*/
public interface Feature {
int index(); /** the index of this feature from 0..numFeatures-1. */
int y(); /** has to be a label index from 0..numLabels-1 */
int yprev(); /** can be -1 if the feature is a state, rather than an edge feature */
float value(); /** any real value, don't return anything if 0 for efficiency */
int[] yprevArray(); /** for history of length greater than 1, return array of prev values, will be ignore of history of length 1*/
};
CRF/src/iitb/CRF/RestrictConstraint.java 0000644 0001760 0001760 00000001167 10421454646 020764 0 ustar abhisheka abhisheka /*
* Created on Dec 3, 2004
*
* TODO To change the template for this generated file go to
* Window - Preferences - Java - Code Style - Code Templates
*/
package iitb.CRF;
/**
* @author Administrator
*
* TODO To change the template for this generated type comment go to
* Window - Preferences - Java - Code Style - Code Templates
*/
public abstract class RestrictConstraint implements Constraint {
public final int type() {return ALLOW_ONLY;}
public abstract void startScan();
public abstract boolean hasNext();
public abstract void advance();
public abstract int y();
public abstract int yprev();
}
CRF/src/iitb/CRF/FeatureGenCache.java 0000644 0001760 0001760 00000012742 10421533442 020062 0 ustar abhisheka abhisheka /*
* Created on Feb 15, 2005
*
*/
package iitb.CRF;
/**
* @author sunita
*
*/
public class FeatureGenCache implements FeatureGeneratorNested {
/**
* @author sunita
*
*/
class FeatureImpl implements Feature {
int _index;
int _y;
int _yprev;
float _value;
void init(int _index, int _y, int _yprev, float _value) {
this._index = _index;
this._y = _y;
this._yprev = _yprev;
this._value = _value;
}
/**
*
*/
public FeatureImpl() {
super();
// TODO Auto-generated constructor stub
}
/* (non-Javadoc)
* @see iitb.CRF.Feature#index()
*/
public int index() {
return _index;
}
/* (non-Javadoc)
* @see iitb.CRF.Feature#y()
*/
public int y() {
return _y;
}
/* (non-Javadoc)
* @see iitb.CRF.Feature#yprev()
*/
public int yprev() {
return _yprev;
}
/* (non-Javadoc)
* @see iitb.CRF.Feature#value()
*/
public float value() {
return _value;
}
/* (non-Javadoc)
* @see iitb.CRF.Feature#yprevArray()
*/
public int[] yprevArray() {
// TODO Auto-generated method stub
return null;
}
}
private static final long serialVersionUID = 1L;
FeatureGeneratorNested fgen;
FeatureGenerator sfgen;
FeatureImpl feature = new FeatureImpl();
int numFeatures = 0;
int scanNum = 0;
int dataIndex = 0;
int y[];
int yprev[];
int index[];
float val[];
int offset[], endOffset[];
int indexPtr;
int thisKey;
int maxKey=0;
int numData = 0;
int maxDataLen=0;
int maxSegLen=0;
/**
*
*/
public FeatureGenCache(FeatureGeneratorNested fgen) {
this.fgen = fgen;
sfgen = fgen;
numFeatures = 0;
}
public FeatureGenCache(FeatureGenerator fgen) {
this.sfgen = fgen;
numFeatures = 0;
this.fgen = null;
if (sfgen instanceof FeatureGeneratorNested)
this.fgen = ((FeatureGeneratorNested)sfgen);
}
/* (non-Javadoc)
* @see iitb.CRF.FeatureGeneratorNested#maxMemory()
*/
public int maxMemory() {
return (sfgen instanceof FeatureGeneratorNested)?((FeatureGeneratorNested)sfgen).maxMemory():1;
}
public void startDataScan() {
scanNum++;
if (scanNum==2) {
// System.out.println("Numfeatures overall "+numFeatures);
y = new int[numFeatures];
yprev = new int[numFeatures];
index = new int[numFeatures];
val = new float[numFeatures];
maxKey = maxSegLen*numData*maxDataLen;
offset = new int[maxKey+1];
endOffset = new int[maxKey+1];
numFeatures = 0;
}
dataIndex = -1;
}
public void nextDataIndex() {
dataIndex++;
if (scanNum==1) numData++;
}
public void startScanFeaturesAt(DataSequence data, int prevPos, int pos) {
startScanFeaturesAt(data,prevPos,pos,true);
}
/* (non-Javadoc)
* @see iitb.CRF.FeatureGeneratorNested#startScanFeaturesAt(iitb.CRF.DataSequence, int, int)
*/
public void startScanFeaturesAt(DataSequence data, int prevPos, int pos, boolean nested) {
assert(scanNum > 0);
thisKey = dataIndex*maxDataLen + pos + (pos-prevPos-1)*maxDataLen*numData;
if (scanNum == 1) {
maxSegLen = Math.max(maxSegLen,pos-prevPos);
maxDataLen = Math.max(maxDataLen,data.length());
} else
assert(thisKey < maxKey+1);
if (scanNum <= 2) {
if (nested)
fgen.startScanFeaturesAt(data,prevPos,pos);
else
sfgen.startScanFeaturesAt(data,pos);
} else {
indexPtr = offset[thisKey];
}
if (scanNum==2) {
offset[thisKey]=numFeatures;
endOffset[thisKey]=numFeatures;
}
}
/* (non-Javadoc)
* @see iitb.CRF.FeatureGenerator#numFeatures()
*/
public int numFeatures() {
return fgen.numFeatures();
}
/* (non-Javadoc)
* @see iitb.CRF.FeatureGenerator#startScanFeaturesAt(iitb.CRF.DataSequence, int)
*/
public void startScanFeaturesAt(DataSequence data, int pos) {
startScanFeaturesAt(data,pos-1,pos,false);
}
/* (non-Javadoc)
* @see iitb.CRF.FeatureGenerator#hasNext()
*/
public boolean hasNext() {
return (scanNum<=2)?sfgen.hasNext():endOffset[thisKey]>indexPtr;
}
/* (non-Javadoc)
* @see iitb.CRF.FeatureGenerator#next()
*/
public Feature next() {
if (scanNum <= 2) {
Feature f = sfgen.next();
if (scanNum==2) {
y[numFeatures]=f.y();
yprev[numFeatures]=f.yprev();
val[numFeatures]=f.value();
index[numFeatures] = f.index();
endOffset[thisKey]++;
}
numFeatures++;
return f;
} else {
feature.init(index[indexPtr],y[indexPtr],yprev[indexPtr],val[indexPtr]);
indexPtr++;
return feature;
}
}
/* (non-Javadoc)
* @see iitb.CRF.FeatureGenerator#featureName(int)
*/
public String featureName(int featureIndex) {
return sfgen.featureName(featureIndex);
}
}
CRF/src/iitb/CRF/SegmentCRF.java 0000644 0001760 0001760 00000005600 10421454646 017051 0 ustar abhisheka abhisheka /*
* Created on Nov 21, 2004
*
* This is a version of the CRF model that applies the semi-markov
* model on data where the candidate segments are provided by the dataset.
*/
package iitb.CRF;
import gnu.trove.TIntArrayList;
import gnu.trove.TIntFloatHashMap;
/**
* @author sunita
*
*/
public class SegmentCRF extends CRF {
FeatureGeneratorNested featureGenNested;
transient SegmentViterbi segmentViterbi;
public SegmentCRF(int numLabels, FeatureGeneratorNested fgen, String arg) {
super(numLabels,fgen,arg);
featureGenNested = fgen;
segmentViterbi = new SegmentViterbi(this,1);
}
public SegmentCRF(int numLabels, FeatureGeneratorNested fgen, java.util.Properties configOptions) {
super(numLabels,fgen,configOptions);
featureGenNested = fgen;
segmentViterbi = new SegmentViterbi(this,1);
}
public interface ModelGraph {
public int numStates();
public void stateMappingGivenLength(int label, int len, TIntArrayList stateIds)
throws Exception;
};
/*
public SegmentCRF(int numLabels, FeatureGeneratorNested fgen, FeatureGenerator markovGen,
ModelGraph modelGraph, java.util.Properties configOptions) {
super(numLabels,fgen,configOptions);
combinedFeatureCache = new CombinedFeatureCache(numLabels,fgen,markovGen, modelGraph);
featureGenNested = combinedFeatureCache;
segmentViterbi = new SegmentViterbi(this,1);
}*/
protected Trainer getTrainer() {
if (params.trainerType.startsWith("SegmentCollins"))
return new NestedCollinsTrainer(params);
return new SegmentTrainer(params);
}
protected Viterbi getViterbi(int beamsize) {
return new SegmentViterbi(this,beamsize);
}
public void apply(CandSegDataSequence dataSeq, int rank) {
if (segmentViterbi==null)
segmentViterbi = (SegmentViterbi)getViterbi(1);
segmentViterbi.bestLabelSequence(dataSeq,lambda);
}
public void singleSegmentClassScores(CandSegDataSequence dataSeq, TIntFloatHashMap scores) {
if (segmentViterbi==null)
segmentViterbi = (SegmentViterbi)getViterbi(1);
segmentViterbi.singleSegmentClassScores(dataSeq,lambda,scores);
}
public Segmentation[] segmentSequences(CandSegDataSequence dataSeq, int numLabelSeqs) {
if (segmentViterbi==null)
segmentViterbi = (SegmentViterbi)getViterbi(numLabelSeqs);
return segmentViterbi.segmentSequences(dataSeq,lambda,numLabelSeqs);
}
/*
public void apply(DataSequence dataSeq) {
apply((CandSegDataSequence)dataSeq);
}
public void apply(CandSegDataSequence dataSeq) {
if (segmentViterbi==null)
segmentViterbi = new SegmentViterbi(this,1);
if (params.debugLvl > 2)
Util.printDbg("SegmentCRF: Applying on " + dataSeq);
segmentViterbi.bestLabelSequence(dataSeq,lambda);
}
*/
/*
public double score(DataSequence dataSeq) {
if (segmentViterbi==null)
segmentViterbi = new SegmentViterbi(this,1);
return segmentViterbi.viterbiSearch(dataSeq,lambda,true);
}
*/
}
CRF/src/iitb/CRF/Trainer.java 0000644 0001760 0001760 00000053665 10421712566 016534 0 ustar abhisheka abhisheka package iitb.CRF;
import riso.numerical.LBFGS;
import cern.colt.function.DoubleDoubleFunction;
import cern.colt.function.DoubleFunction;
import cern.colt.matrix.DoubleMatrix1D;
import cern.colt.matrix.DoubleMatrix2D;
import cern.colt.matrix.impl.DenseDoubleMatrix1D;
import cern.colt.matrix.impl.DenseDoubleMatrix2D;
/**
*
* @author Sunita Sarawagi
*
*/
public class Trainer {
protected int numF,numY;
double gradLogli[];
double diag[];
double lambda[];
protected boolean reuseM, initMDone=false;
protected double ExpF[];
double scale[], rLogScale[];
protected DoubleMatrix2D Mi_YY;
protected DoubleMatrix1D Ri_Y;
protected DoubleMatrix1D alpha_Y, newAlpha_Y;
protected DoubleMatrix1D beta_Y[];
protected DoubleMatrix1D tmp_Y;
static class MultFunc implements DoubleDoubleFunction {
public double apply(double a, double b) {return a*b;}
};
static class SumFunc implements DoubleDoubleFunction {
public double apply(double a, double b) {return a+b;}
};
static MultFunc multFunc = new MultFunc();
protected static SumFunc sumFunc = new SumFunc();
class MultSingle implements DoubleFunction {
public double multiplicator = 1.0;
public double apply(double a) {return a*multiplicator;}
};
MultSingle constMultiplier = new MultSingle();
protected DataIter diter;
FeatureGenerator featureGenerator;
protected CrfParams params;
EdgeGenerator edgeGen;
protected int icall;
Evaluator evaluator = null;
FeatureGenCache featureGenCache;
protected double norm(double ar[]) {
double v = 0;
for (int f = 0; f < ar.length; f++)
v += ar[f]*ar[f];
return Math.sqrt(v);
}
public Trainer(CrfParams p) {
params = p;
}
public void train(CRF model, DataIter data, double[] l, Evaluator eval) {
init(model,data,l);
evaluator = eval;
if (params.debugLvl > 0) {
Util.printDbg("Number of features :" + lambda.length);
}
doTrain();
}
double getInitValue() {
// returns a negative value to avoid overflow in the initial stages.
// if (params.initValue == 0)
// return -1*Math.log(numY);
return params.initValue;
}
protected void init(CRF model, DataIter data, double[] l) {
edgeGen = model.edgeGen;
lambda = l;
numY = model.numY;
diter = data;
featureGenerator = model.featureGenerator;
numF = featureGenerator.numFeatures();
gradLogli = new double[numF];
diag = new double [ numF ]; // needed by the optimizer
ExpF = new double[lambda.length];
initMatrices();
reuseM = params.reuseM;
if (params.miscOptions.getProperty("cache", "false").equals("true")) {
featureGenCache = new FeatureGenCache(featureGenerator);
featureGenerator = featureGenCache;
} else
featureGenCache = null;
}
void initMatrices() {
Mi_YY = new DenseDoubleMatrix2D(numY,numY);
Ri_Y = new DenseDoubleMatrix1D(numY);
alpha_Y = new DenseDoubleMatrix1D(numY);
newAlpha_Y = new DenseDoubleMatrix1D(numY);
tmp_Y = new DenseDoubleMatrix1D(numY);
}
void doTrain() {
double f, xtol = 1.0e-16; // machine precision
int iprint[] = new int [2], iflag[] = new int[1];
icall=0;
iprint [0] = params.debugLvl-2;
iprint [1] = params.debugLvl-1;
iflag[0]=0;
for (int j = 0 ; j < lambda.length ; j ++) {
// lambda[j] = 1.0/lambda.length;
lambda[j] = getInitValue();
}
do {
f = computeFunctionGradient(lambda,gradLogli);
f = -1*f; // since the routine below minimizes and we want to maximize logli
for (int j = 0 ; j < lambda.length ; j ++) {
gradLogli[j] *= -1;
}
if ((evaluator != null) && (evaluator.evaluate() == false))
break;
try {
LBFGS.lbfgs (numF, params.mForHessian, lambda, f, gradLogli, false, diag, iprint, params.epsForConvergence, xtol, iflag);
} catch (LBFGS.ExceptionWithIflag e) {
System.err.println( "CRF: lbfgs failed.\n"+e );
if (e.iflag == -1) {
System.err.println("Possible reasons could be: \n \t 1. Bug in the feature generation or data handling code\n\t 2. Not enough features to make observed feature value==expected value\n");
}
return;
}
icall += 1;
} while (( iflag[0] != 0) && (icall <= params.maxIters));
}
protected double computeFunctionGradient(double lambda[], double grad[]) {
initMDone=false;
//System.out.println("---"+params.trainerType);
if (params.trainerType.equals("ll"))
return computeFunctionGradientLL(lambda, grad);
double logli = 0;
try {
for (int f = 0; f < lambda.length; f++) {
grad[f] = -1*lambda[f]*params.invSigmaSquare;
logli -= ((lambda[f]*lambda[f])*params.invSigmaSquare)/2;
}
boolean doScaling = params.doScaling;
diter.startScan();
if (featureGenCache != null) featureGenCache.startDataScan();
int numRecord = 0;
for (numRecord = 0; diter.hasNext(); numRecord++) {
DataSequence dataSeq = (DataSequence)diter.next();
if (featureGenCache != null) featureGenCache.nextDataIndex();
if (params.debugLvl > 1) {
Util.printDbg("Read next seq: " + numRecord + " logli " + logli);
}
alpha_Y.assign(1);
for (int f = 0; f < lambda.length; f++)
ExpF[f] = 0;
if ((beta_Y == null) || (beta_Y.length < dataSeq.length())) {
beta_Y = new DenseDoubleMatrix1D[2*dataSeq.length()];
for (int i = 0; i < beta_Y.length; i++)
beta_Y[i] = new DenseDoubleMatrix1D(numY);
scale = new double[2*dataSeq.length()];
}
// compute beta values in a backward scan.
// also scale beta-values to 1 to avoid numerical problems.
scale[dataSeq.length()-1] = (doScaling)?numY:1;
beta_Y[dataSeq.length()-1].assign(1.0/scale[dataSeq.length()-1]);
for (int i = dataSeq.length()-1; i > 0; i--) {
if (params.debugLvl > 2) {
Util.printDbg("Features fired");
//featureGenerator.startScanFeaturesAt(dataSeq, i);
//while (featureGenerator.hasNext()) {
//Feature feature = featureGenerator.next();
//Util.printDbg(feature.toString());
//}
}
// compute the Mi matrix
initMDone = computeLogMi(featureGenerator,lambda,dataSeq,i,Mi_YY,Ri_Y,true,reuseM,initMDone);
tmp_Y.assign(beta_Y[i]);
tmp_Y.assign(Ri_Y,multFunc);
RobustMath.Mult(Mi_YY, tmp_Y, beta_Y[i-1],1,0,false,edgeGen);
// Mi_YY.zMult(tmp_Y, beta_Y[i-1]);
// need to scale the beta-s to avoid overflow
scale[i-1] = doScaling?beta_Y[i-1].zSum():1;
if ((scale[i-1] < 1) && (scale[i-1] > -1))
scale[i-1] = 1;
constMultiplier.multiplicator = 1.0/scale[i-1];
beta_Y[i-1].assign(constMultiplier);
}
double thisSeqLogli = 0;
for (int i = 0; i < dataSeq.length(); i++) {
// compute the Mi matrix
initMDone = computeLogMi(featureGenerator,lambda,dataSeq,i,Mi_YY,Ri_Y,true,reuseM,initMDone);
// find features that fire at this position..
featureGenerator.startScanFeaturesAt(dataSeq, i);
if (i > 0) {
tmp_Y.assign(alpha_Y);
RobustMath.Mult(Mi_YY, tmp_Y, newAlpha_Y,1,0,true,edgeGen);
// Mi_YY.zMult(tmp_Y, newAlpha_Y,1,0,true);
newAlpha_Y.assign(Ri_Y,multFunc);
} else {
newAlpha_Y.assign(Ri_Y);
}
while (featureGenerator.hasNext()) {
Feature feature = featureGenerator.next();
int f = feature.index();
int yp = feature.y();
int yprev = feature.yprev();
float val = feature.value();
if ((dataSeq.y(i) == yp) && (((i-1 >= 0) && (yprev == dataSeq.y(i-1))) || (yprev < 0))) {
grad[f] += val;
thisSeqLogli += val*lambda[f];
}
if (yprev < 0) {
ExpF[f] += newAlpha_Y.get(yp)*val*beta_Y[i].get(yp);
} else {
ExpF[f] += alpha_Y.get(yprev)*Ri_Y.get(yp)*Mi_YY.get(yprev,yp)*val*beta_Y[i].get(yp);
}
}
alpha_Y.assign(newAlpha_Y);
// now scale the alpha-s to avoid overflow problems.
constMultiplier.multiplicator = 1.0/scale[i];
alpha_Y.assign(constMultiplier);
if (params.debugLvl > 2) {
System.out.println("Alpha-i " + alpha_Y.toString());
System.out.println("Ri " + Ri_Y.toString());
System.out.println("Mi " + Mi_YY.toString());
System.out.println("Beta-i " + beta_Y[i].toString());
}
}
double Zx = alpha_Y.zSum();
thisSeqLogli -= log(Zx);
// correct for the fact that alpha-s were scaled.
for (int i = 0; i < dataSeq.length(); i++) {
thisSeqLogli -= log(scale[i]);
}
logli += thisSeqLogli;
// update grad.
for (int f = 0; f < grad.length; f++)
grad[f] -= ExpF[f]/Zx;
if (params.debugLvl > 1) {
System.out.println("Sequence " + thisSeqLogli + " logli " + logli + " log(Zx) " + Math.log(Zx) + " Zx " + Zx);
}
}
if (params.debugLvl > 2) {
for (int f = 0; f < lambda.length; f++)
System.out.print(lambda[f] + " ");
System.out.println(" :x");
for (int f = 0; f < lambda.length; f++)
System.out.println(featureGenerator.featureName(f) + " " + grad[f] + " ");
System.out.println(" :g");
}
if (params.debugLvl > 0)
Util.printDbg("Iter " + icall + " log likelihood "+logli + " norm(grad logli) " + norm(grad) + " norm(x) "+ norm(lambda));
if (icall == 0) {
System.out.println("Number of training records " + numRecord);
}
} catch (Exception e) {
System.out.println("Alpha-i " + alpha_Y.toString());
System.out.println("Ri " + Ri_Y.toString());
System.out.println("Mi " + Mi_YY.toString());
e.printStackTrace();
System.exit(0);
}
return logli;
}
static void computeLogMi(FeatureGenerator featureGen, double lambda[],
DoubleMatrix2D Mi_YY,
DoubleMatrix1D Ri_Y, boolean takeExp) {
computeLogMi(featureGen,lambda,Mi_YY,Ri_Y,takeExp,false,false);
}
static boolean computeLogMi(FeatureGenerator featureGen, double lambda[],
DoubleMatrix2D Mi_YY,
DoubleMatrix1D Ri_Y, boolean takeExp,boolean reuseM, boolean initMDone) {
if (reuseM && initMDone) {
Mi_YY = null;
} else
initMDone = false;
if (Mi_YY != null) Mi_YY.assign(0);
Ri_Y.assign(0);
while (featureGen.hasNext()) {
Feature feature = featureGen.next();
int f = feature.index();
int yp = feature.y();
int yprev = feature.yprev();
float val = feature.value();
// System.out.println(feature.toString());
if (yprev < 0) {
// this is a single state feature.
double oldVal = Ri_Y.getQuick(yp);
Ri_Y.setQuick(yp,oldVal+lambda[f]*val);
} else if (Mi_YY != null) {
Mi_YY.setQuick(yprev,yp,Mi_YY.getQuick(yprev,yp)+lambda[f]*val);
initMDone = true;
}
}
if (takeExp) {
for(int r = Ri_Y.size()-1; r >= 0; r--) {
Ri_Y.setQuick(r,expE(Ri_Y.getQuick(r)));
if (Mi_YY != null)
for(int c = Mi_YY.columns()-1; c >= 0; c--) {
Mi_YY.setQuick(r,c,expE(Mi_YY.getQuick(r,c)));
}
}
}
return initMDone;
}
static void computeLogMi(FeatureGenerator featureGen, double lambda[],
DataSequence dataSeq, int i,
DoubleMatrix2D Mi_YY,
DoubleMatrix1D Ri_Y, boolean takeExp) {
computeLogMi(featureGen, lambda, dataSeq, i, Mi_YY, Ri_Y, takeExp,false,false);
}
static boolean computeLogMi(FeatureGenerator featureGen, double lambda[],
DataSequence dataSeq, int i,
DoubleMatrix2D Mi_YY,
DoubleMatrix1D Ri_Y, boolean takeExp, boolean reuseM, boolean initMDone) {
featureGen.startScanFeaturesAt(dataSeq, i);
return computeLogMi(featureGen, lambda, Mi_YY, Ri_Y, takeExp,reuseM, initMDone);
}
protected double computeFunctionGradientLL(double lambda[], double grad[]) {
double logli = 0;
try {
for (int f = 0; f < lambda.length; f++) {
grad[f] = -1*lambda[f]*params.invSigmaSquare;
logli -= ((lambda[f]*lambda[f])*params.invSigmaSquare)/2;
}
diter.startScan();
if (featureGenCache != null) featureGenCache.startDataScan();
for (int numRecord = 0; diter.hasNext(); numRecord++) {
DataSequence dataSeq = (DataSequence)diter.next();
if (featureGenCache != null) featureGenCache.nextDataIndex();
if (params.debugLvl > 1) {
Util.printDbg("Read next seq: " + numRecord + " logli " + logli);
}
alpha_Y.assign(0);
for (int f = 0; f < lambda.length; f++)
ExpF[f] = RobustMath.LOG0;
if ((beta_Y == null) || (beta_Y.length < dataSeq.length())) {
beta_Y = new DenseDoubleMatrix1D[2*dataSeq.length()];
for (int i = 0; i < beta_Y.length; i++)
beta_Y[i] = new DenseDoubleMatrix1D(numY);
}
// compute beta values in a backward scan.
// also scale beta-values to 1 to avoid numerical problems.
beta_Y[dataSeq.length()-1].assign(0);
for (int i = dataSeq.length()-1; i > 0; i--) {
if (params.debugLvl > 2) {
/* Util.printDbg("Features fired");
featureGenerator.startScanFeaturesAt(dataSeq, i);
while (featureGenerator.hasNext()) {
Feature feature = featureGenerator.next();
Util.printDbg(feature.toString());
}
*/
}
// compute the Mi matrix
initMDone = computeLogMi(featureGenerator,lambda,dataSeq,i,Mi_YY,Ri_Y,false,reuseM,initMDone);
tmp_Y.assign(beta_Y[i]);
tmp_Y.assign(Ri_Y,sumFunc);
RobustMath.logMult(Mi_YY, tmp_Y, beta_Y[i-1],1,0,false,edgeGen);
}
double thisSeqLogli = 0;
for (int i = 0; i < dataSeq.length(); i++) {
// compute the Mi matrix
initMDone = computeLogMi(featureGenerator,lambda,dataSeq,i,Mi_YY,Ri_Y,false,reuseM,initMDone);
// find features that fire at this position..
featureGenerator.startScanFeaturesAt(dataSeq, i);
if (i > 0) {
tmp_Y.assign(alpha_Y);
RobustMath.logMult(Mi_YY, tmp_Y, newAlpha_Y,1,0,true,edgeGen);
newAlpha_Y.assign(Ri_Y,sumFunc);
} else {
newAlpha_Y.assign(Ri_Y);
}
while (featureGenerator.hasNext()) {
Feature feature = featureGenerator.next();
int f = feature.index();
int yp = feature.y();
int yprev = feature.yprev();
float val = feature.value();
if ((dataSeq.y(i) == yp) && (((i-1 >= 0) && (yprev == dataSeq.y(i-1))) || (yprev < 0))) {
grad[f] += val;
thisSeqLogli += val*lambda[f];
if (params.debugLvl > 2) {
System.out.println("Feature fired " + f + " " + feature);
}
}
if (yprev < 0) {
ExpF[f] = RobustMath.logSumExp(ExpF[f], newAlpha_Y.get(yp) + RobustMath.log(val) + beta_Y[i].get(yp));
} else {
ExpF[f] = RobustMath.logSumExp(ExpF[f], alpha_Y.get(yprev)+Ri_Y.get(yp)+Mi_YY.get(yprev,yp)+RobustMath.log(val)+beta_Y[i].get(yp));
}
}
alpha_Y.assign(newAlpha_Y);
if (params.debugLvl > 2) {
System.out.println("Alpha-i " + alpha_Y.toString());
System.out.println("Ri " + Ri_Y.toString());
System.out.println("Mi " + Mi_YY.toString());
System.out.println("Beta-i " + beta_Y[i].toString());
}
}
double lZx = RobustMath.logSumExp(alpha_Y);
thisSeqLogli -= lZx;
logli += thisSeqLogli;
// update grad.
for (int f = 0; f < grad.length; f++) {
grad[f] -= RobustMath.exp(ExpF[f]-lZx);
}
if (params.debugLvl > 1) {
System.out.println("Sequence " + thisSeqLogli + " logli " + logli + " log(Zx) " + lZx + " Zx " + Math.exp(lZx));
}
}
if (params.debugLvl > 2) {
for (int f = 0; f < lambda.length; f++)
System.out.print(lambda[f] + " ");
System.out.println(" :x");
for (int f = 0; f < lambda.length; f++)
System.out.print(grad[f] + " ");
System.out.println(" :g");
}
if (params.debugLvl > 0)
Util.printDbg("Iteration " + icall + " log-likelihood "+logli + " norm(grad logli) " + norm(grad) + " norm(x) "+ norm(lambda));
} catch (Exception e) {
System.out.println("Alpha-i " + alpha_Y.toString());
System.out.println("Ri " + Ri_Y.toString());
System.out.println("Mi " + Mi_YY.toString());
e.printStackTrace();
System.exit(0);
}
return logli;
}
static double log(double val) {
try {
return logE(val);
} catch (Exception e) {
System.out.println(e.getMessage());
e.printStackTrace();
}
return -1*Double.MAX_VALUE;
}
static double logE(double val) throws Exception {
double pr = Math.log(val);
if (Double.isNaN(pr) || Double.isInfinite(pr)) {
throw new Exception("Overflow error when taking log of " + val);
}
return pr;
}
static double expE(double val) {
double pr = RobustMath.exp(val);
if (Double.isNaN(pr) || Double.isInfinite(pr)) {
try {
throw new Exception("Overflow error when taking exp of " + val + "\n Try running the CRF with the following option \"trainer ll\" to perform computations in the log-space.");
} catch (Exception e) {
System.out.println(e.getMessage());
e.printStackTrace();
return Double.MAX_VALUE;
}
}
return pr;
}
static double expLE(double val) {
double pr = RobustMath.exp(val);
if (Double.isNaN(pr) || Double.isInfinite(pr)) {
try {
throw new Exception("Overflow error when taking exp of " + val
+ " you might need to redesign feature values so as to not reach such high values");
} catch (Exception e) {
System.out.println(e.getMessage());
e.printStackTrace();
return Double.MAX_VALUE;
}
}
return pr;
}
}
CRF/src/iitb/CRF/CandSegDataSequence.java 0000644 0001760 0001760 00000000511 10421454646 020677 0 ustar abhisheka abhisheka /*
* Created on Nov 25, 2004
*
*/
package iitb.CRF;
import java.util.Iterator;
/**
* @author sunita
*
*/
public interface CandSegDataSequence extends SegmentDataSequence, CandidateSegments {
boolean holdsInTrainingData(Feature feature, int prevPos, int pos);
public Iterator constraints(int prevPos, int pos);
}
CRF/src/iitb/CRF/Soln.java 0000644 0001760 0001760 00000002554 10421544045 016025 0 ustar abhisheka abhisheka /*
* Created on Apr 25, 2005
*
*/
package iitb.CRF;
import java.io.Serializable;
/**
* @author sunita
*
*/
public class Soln implements Serializable, Comparable {
private static final long serialVersionUID = 812L;
public float score=-1*Float.MAX_VALUE;
public Soln prevSoln=null;
public int label = -1;
public int pos;
public Soln(int id, int p) {label = id;pos = p;}
void clear() {
score=-1*Float.MAX_VALUE;
prevSoln=null;
}
boolean isClear() {
return (score == -1*Double.MAX_VALUE);
}
protected void copy(Soln soln) {
score = soln.score;
prevSoln = soln.prevSoln;
}
public int prevPos() {
return (prevSoln == null)?-1:prevSoln.pos;
}
protected int prevLabel() {
return (prevSoln == null)?-1:prevSoln.label;
}
public boolean equals(Soln s) {
return (label == s.label) && (pos == s.pos) && (prevPos() == s.prevPos()) && (prevLabel() == s.prevLabel());
}
/**
* @param prevSoln2
* @param score2
*/
protected void setPrevSoln(Soln prevSoln, float score) {
this.prevSoln = (prevSoln==null)?null:prevSoln.getSoln();
this.score = score;
}
protected Soln getSoln() {
return this;
}
public int compareTo(Object s) {
return ((((Soln)this).score-((Soln)s).score)>0)?1:-1;
}
};
CRF/src/iitb/CRF/Util.java 0000644 0001760 0001760 00000000245 10421454646 016031 0 ustar abhisheka abhisheka package iitb.CRF;
/**
*
* @author Sunita Sarawagi
*
*/
public class Util {
static public void printDbg(String msg) {
System.out.println(msg);
}
};
CRF/src/iitb/CRF/ConstraintDisallowedPairs.java 0000644 0001760 0001760 00000000562 10421454646 022251 0 ustar abhisheka abhisheka /*
* Created on Dec 31, 2004
*
*/
package iitb.CRF;
/**
* @author sunita
*
*/
public interface ConstraintDisallowedPairs extends Constraint {
boolean conflictingPair(int label1, int label2, boolean adjacent);
/**
*
* @param label
* @return true if the label is disallowed with any other label
*/
boolean conflicting(int label);
}
CRF/src/iitb/CRF/FeatureGenerator.java 0000644 0001760 0001760 00000001027 10421454646 020355 0 ustar abhisheka abhisheka package iitb.CRF;
import java.io.Serializable;
/**
* The basic interface to be implemented by the user of this package
* for providing features of an individual data sequence.
*
* @author Sunita Sarawagi
* */
public interface FeatureGenerator extends Serializable {
/** The number of features has to be correctly set before train is called. */
int numFeatures();
void startScanFeaturesAt(DataSequence data, int pos);
boolean hasNext();
Feature next();
public String featureName(int featureIndex);
};
CRF/src/iitb/CRF/SparseViterbi.java 0000644 0001760 0001760 00000015035 10421544054 017672 0 ustar abhisheka abhisheka package iitb.CRF;
import cern.colt.function.IntDoubleFunction;
import cern.colt.function.IntIntDoubleFunction;
import cern.colt.list.DoubleArrayList;
import cern.colt.list.IntArrayList;
import cern.colt.list.ObjectArrayList;
import cern.colt.matrix.impl.DenseObjectMatrix1D;
/**
*
* Viterbi search
*
* @author Sunita Sarawagi
*
*/
public class SparseViterbi extends Viterbi {
protected SparseViterbi(CRF model, int bs) {
super(model,bs);
}
protected class Context extends DenseObjectMatrix1D {
protected int pos;
protected int beamsize;
protected Context(int numY, int beamsize, int pos){
super(numY);
this.pos = pos;
this.beamsize = beamsize;
}
protected Entry newEntry(int beamsize, int label, int pos) {
return new Entry(beamsize,label,pos);
}
public void add(int y, Entry prevEntry, float thisScore) {
if (getQuick(y) == null) {
setQuick(y, newEntry((pos==0)?1:beamsize, y, pos));
}
getEntry(y).valid = true;
getEntry(y).add(prevEntry,thisScore);
}
public void clear() {
// assign((Object)null);
for (int i = 0; i < size(); i++)
if (getQuick(i) != null)
getEntry(i).clear();
}
public Entry getEntry(int y) {return (Entry)getQuick(y);}
/**
* @param y
* @return
*/
public boolean entryNotNull(int y) {
return ((getQuick(y) != null) && getEntry(y).valid);
}
void assign(LogSparseDoubleMatrix1D Ri) {
for (int y = 0; y < Ri.size(); y++) {
if (Ri.getQuick(y) != 0)
add(y,null,(float)Ri.get(y));
}
}
};
protected Context context[];
// SparseDoubleMatrix2D Mi;
protected LogSparseDoubleMatrix1D Ri;
ObjectArrayList prevContext = new ObjectArrayList();
IntArrayList validYs = new IntArrayList();
IntArrayList validPrevYs = new IntArrayList();
DoubleArrayList values = new DoubleArrayList();
protected void computeLogMi(DataSequence dataSeq, int i, int ell, double lambda[]) {
model.featureGenerator.startScanFeaturesAt(dataSeq, i);
SparseTrainer.computeLogMi(model.featureGenerator,lambda,Mi,Ri);
}
protected class Iter {
protected int ell;
protected void start(int i, DataSequence dataSeq) {ell = 1;}
protected int nextEll(int i) {return ell--;}
}
protected Iter getIter(){return new Iter();}
protected void finishContext(int i2) {;}
/**
* @return
*/
protected double getCorrectScore(DataSequence dataSeq, int i, int ell) {
return (Ri.getQuick(dataSeq.y(i)) + ((i > 0)?Mi.get(dataSeq.y(i-1),dataSeq.y(i)):0));
}
protected class ContextUpdate implements IntIntDoubleFunction, IntDoubleFunction {
protected int i, ell;
protected Iter iter;
public double apply(int yp, int yi, double val) {
if (context[i-ell].entryNotNull(yp))
context[i].add(yi, context[i-ell].getEntry(yp),(float)(Mi.get(yp,yi)+Ri.get(yi)));
return val;
}
public double apply(int yi, double val) {
context[i].add(yi,null,(float)Ri.get(yi));
return val;
}
double fillArray(DataSequence dataSeq, double lambda[], boolean calcScore) {
double corrScore = 0;
for (i = 0; i < dataSeq.length(); i++) {
context[i].clear();
for (iter.start(i,dataSeq); (ell = iter.nextEll(i)) > 0;) {
// compute Mi.
// i - ell = i'
computeLogMi(dataSeq, i, ell, lambda);
if (i - ell < 0) {
Ri.forEachNonZero(this);
} else {
Mi.forEachNonZero(this);
}
if (model.params.debugLvl > 1) {
System.out.println("Ri "+Ri);
System.out.println("Mi "+ Mi);
}
if (calcScore) {
corrScore += getCorrectScore(dataSeq, i, ell);
}
}
finishContext(i);
}
/*
i = dataSeq.length();
context[i].clear();
if (i >= 1) {
for (int yp = 0; yp < context[i-1].size(); yp++) {
if (context[i-1].entryNotNull(yp))
context[i].add(0, context[i-1].getEntry(yp),0);
}
}
*/
return corrScore;
}
};
protected ContextUpdate contextUpdate;
protected ContextUpdate newContextUpdate() {
return new ContextUpdate();
}
protected void allocateScratch(int numY) {
Mi = new LogSparseDoubleMatrix2D(numY,numY);
Ri = new LogSparseDoubleMatrix1D(numY);
context = new Context[0];
finalSoln = new Entry(beamsize,0,0);
contextUpdate = newContextUpdate();
contextUpdate.iter = getIter();
}
protected Context newContext(int numY, int beamsize, int pos){
return new Context(numY,beamsize,pos);
}
public double viterbiSearch(DataSequence dataSeq, double lambda[], boolean calcCorrectScore) {
if (Mi == null) {
allocateScratch(model.numY);
}
if (context.length < dataSeq.length()+1) {
Context oldContext[] = context;
context = new Context[dataSeq.length()+1];
for (int l = 0; l < oldContext.length; l++) {
context[l] = oldContext[l];
}
for (int l = oldContext.length; l < context.length; l++) {
context[l] = newContext(model.numY,beamsize,l);
}
}
double corrScore = contextUpdate.fillArray(dataSeq, lambda,calcCorrectScore);
finalSoln.clear();
finalSoln.valid = true;
int i = dataSeq.length()-1;
if (i >= 0) {
for (int y = 0; y < context[i].size(); y++) {
if (context[i].entryNotNull(y))
finalSoln.add((Entry)context[i].getQuick(y),0);
}
}
// finalSoln = (Entry)context[dataSeq.length()].getQuick(0);
if (model.params.debugLvl > 1) {
System.out.println("Score of best sequence "+finalSoln.get(0).score + " corrScore " + corrScore);
}
return corrScore;
}
};
CRF/src/iitb/CRF/NestedTrainer.java 0000644 0001760 0001760 00000030702 10421544046 017656 0 ustar abhisheka abhisheka package iitb.CRF;
import cern.colt.matrix.impl.DenseDoubleMatrix1D;
/**
*
* @author Sunita Sarawagi
*
*/
class NestedTrainer extends Trainer {
public NestedTrainer(CrfParams p) {
super(p);
}
DenseDoubleMatrix1D alpha_Y_Array[];
protected double computeFunctionGradient(double lambda[], double grad[]) {
if (params.doScaling)
return computeFunctionGradientLL(lambda, grad);
try {
FeatureGeneratorNested featureGenNested = (FeatureGeneratorNested)featureGenerator;
double logli = 0;
for (int f = 0; f < lambda.length; f++) {
grad[f] = -1*lambda[f]*params.invSigmaSquare;
logli -= ((lambda[f]*lambda[f])*params.invSigmaSquare)/2;
}
boolean doScaling = false; // scaling as implemented below does not work.
diter.startScan();
if (featureGenCache != null) featureGenCache.startDataScan();
for (int numRecord = 0; diter.hasNext(); numRecord++) {
SegmentDataSequence dataSeq = (SegmentDataSequence)diter.next();
if (featureGenCache != null) featureGenCache.nextDataIndex();
if (params.debugLvl > 1)
Util.printDbg("Read next seq: " + numRecord + " logli " + logli);
for (int f = 0; f < lambda.length; f++)
ExpF[f] = 0;
int base = -1;
if ((alpha_Y_Array == null) || (alpha_Y_Array.length < dataSeq.length()-base)) {
alpha_Y_Array = new DenseDoubleMatrix1D[2*dataSeq.length()];
for (int i = 0; i < alpha_Y_Array.length; i++)
alpha_Y_Array[i] = new DenseDoubleMatrix1D(numY);
}
if ((beta_Y == null) || (beta_Y.length < dataSeq.length())) {
beta_Y = new DenseDoubleMatrix1D[2*dataSeq.length()];
for (int i = 0; i < beta_Y.length; i++)
beta_Y[i] = new DenseDoubleMatrix1D(numY);
scale = new double[2*dataSeq.length()];
}
// compute beta values in a backward scan.
// also scale beta-values as much as possible to avoid numerical overflows
beta_Y[dataSeq.length()-1].assign(1.0);
scale[dataSeq.length()-1]=1;
for (int i = dataSeq.length()-2; i >= 0; i--) {
// we need to do delayed scaling, so scale everything by the first element of the current window.
if (doScaling && (i + featureGenNested.maxMemory() < dataSeq.length())) {
int iL = i + featureGenNested.maxMemory();
scale[iL] = beta_Y[iL].zSum();
constMultiplier.multiplicator = 1.0/scale[iL];
for (int j = i+1; j <= iL; j++) {
beta_Y[j].assign(constMultiplier);
}
}
beta_Y[i].assign(0);
scale[i] = 1;
for (int ell = 1; (ell <= featureGenNested.maxMemory()) && (i+ell < dataSeq.length()); ell++) {
// compute the Mi matrix
featureGenNested.startScanFeaturesAt(dataSeq, i, i+ell);
//if (! featureGenNested.hasNext())
// break;
initMDone = computeLogMi(featureGenNested,lambda,Mi_YY,Ri_Y,true,reuseM,initMDone);
tmp_Y.assign(beta_Y[i+ell]);
tmp_Y.assign(Ri_Y,multFunc);
Mi_YY.zMult(tmp_Y, beta_Y[i],1,1,false);
}
}
double thisSeqLogli = 0;
alpha_Y_Array[0].assign(1);
int segmentStart = 0;
int segmentEnd = -1;
boolean invalid = false;
for (int i = 0; i < dataSeq.length(); i++) {
if (segmentEnd < i) {
segmentStart = i;
segmentEnd = dataSeq.getSegmentEnd(i);
}
if (segmentEnd-segmentStart+1 > featureGenNested.maxMemory()) {
if (icall <= 1) {
System.out.println("Ignoring record with segment length greater than maxMemory " + numRecord);
}
invalid = true;
break;
}
alpha_Y_Array[i-base].assign(0);
// compute the scale adjustment.
float scaleProduct = 1;
for (int j = i-featureGenNested.maxMemory()-base; j <= i-1; j++)
if (j >= 0) scaleProduct *= scale[j];
for (int ell = 1; (ell <= featureGenNested.maxMemory()) && (i-ell >= base); ell++) {
// compute the Mi matrix
featureGenNested.startScanFeaturesAt(dataSeq, i-ell,i);
// if (!featureGenNested.hasNext())
// break;
initMDone = computeLogMi(featureGenNested,lambda,Mi_YY,Ri_Y,true,reuseM,initMDone);
// find features that fire at this position..
featureGenNested.startScanFeaturesAt(dataSeq, i-ell,i);
boolean isSegment = ((i-ell+1==segmentStart) && (i == segmentEnd));
while (featureGenNested.hasNext()) {
Feature feature = featureGenNested.next();
int f = feature.index();
int yp = feature.y();
int yprev = feature.yprev();
float val = feature.value();
boolean allEllMatch = isSegment && (dataSeq.y(i) == yp);
if (allEllMatch && (((i-ell >= 0) && (yprev == dataSeq.y(i-ell))) || (yprev < 0))) {
grad[f] += val;
thisSeqLogli += val*lambda[f];
}
if (yprev < 0) {
for (yprev = 0; yprev < Mi_YY.rows(); yprev++)
ExpF[f] += (alpha_Y_Array[i-ell-base].get(yprev)*Ri_Y.get(yp)*Mi_YY.get(yprev,yp)*val*beta_Y[i].get(yp))/scaleProduct;
} else {
ExpF[f] += (alpha_Y_Array[i-ell-base].get(yprev)*Ri_Y.get(yp)*Mi_YY.get(yprev,yp)*val*beta_Y[i].get(yp))/scaleProduct;
}
}
Mi_YY.zMult(alpha_Y_Array[i-ell-base],tmp_Y,1,0,true);
tmp_Y.assign(Ri_Y,multFunc);
alpha_Y_Array[i-base].assign(tmp_Y, sumFunc);
}
// now do the delayed scaling of the alpha-s to avoid overflow problems.
if (i-base-featureGenNested.maxMemory() >= 0) {
int iL = i-base-featureGenNested.maxMemory();
constMultiplier.multiplicator = 1.0/scale[iL];
for (int j = iL; j <= i-base; j++) {
alpha_Y_Array[j].assign(constMultiplier);
}
}
if (params.debugLvl > 2) {
System.out.println("Alpha-i " + alpha_Y_Array[i-base].toString());
System.out.println("Ri " + Ri_Y.toString());
System.out.println("Mi " + Mi_YY.toString());
System.out.println("Beta-i " + beta_Y[i].toString());
}
if (params.debugLvl > 1) {
System.out.println(" pos " + i + " " + thisSeqLogli);
}
}
if (invalid)
continue;
double Zx = alpha_Y_Array[dataSeq.length()-1-base].zSum();
thisSeqLogli -= log(Zx);
// correct for the fact that alpha-s were scaled.
for (int i = 0; i < dataSeq.length()-base-featureGenNested.maxMemory(); i++) {
thisSeqLogli -= log(scale[i]);
}
logli += thisSeqLogli;
// update grad.
for (int f = 0; f < grad.length; f++)
grad[f] -= ExpF[f]/Zx;
if (params.debugLvl > 1) {
System.out.println("Sequence " + thisSeqLogli + " " + logli + " " + Zx);
System.out.println("Last Alpha-i " + alpha_Y_Array[dataSeq.length()-1-base].toString());
}
}
if (params.debugLvl > 2) {
for (int f = 0; f < lambda.length; f++)
System.out.print(lambda[f] + " ");
System.out.println(" :x");
for (int f = 0; f < lambda.length; f++)
System.out.print(grad[f] + " ");
System.out.println(" :g");
}
if (params.debugLvl > 0)
Util.printDbg("Iter " + icall + " loglikelihood "+logli + " gnorm " + norm(grad) + " xnorm "+ norm(lambda));
return logli;
} catch (Exception e) {
e.printStackTrace();
System.exit(0);
}
return 0;
}
protected double computeFunctionGradientLL(double lambda[], double grad[]) {
try {
FeatureGeneratorNested featureGenNested = (FeatureGeneratorNested)featureGenerator;
double logli = 0;
for (int f = 0; f < lambda.length; f++) {
grad[f] = -1*lambda[f]*params.invSigmaSquare;
logli -= ((lambda[f]*lambda[f])*params.invSigmaSquare)/2;
}
diter.startScan();
if (featureGenCache != null) featureGenCache.startDataScan();
for (int numRecord = 0; diter.hasNext(); numRecord++) {
SegmentDataSequence dataSeq = (SegmentDataSequence)diter.next();
if (featureGenCache != null) featureGenCache.nextDataIndex();
if (params.debugLvl > 1)
Util.printDbg("Read next seq: " + numRecord + " logli " + logli);
for (int f = 0; f < lambda.length; f++)
ExpF[f] = RobustMath.LOG0;
int base = -1;
if ((alpha_Y_Array == null) || (alpha_Y_Array.length < dataSeq.length()-base)) {
alpha_Y_Array = new DenseDoubleMatrix1D[2*dataSeq.length()];
for (int i = 0; i < alpha_Y_Array.length; i++)
alpha_Y_Array[i] = new DenseDoubleMatrix1D(numY);
}
if ((beta_Y == null) || (beta_Y.length < dataSeq.length())) {
beta_Y = new DenseDoubleMatrix1D[2*dataSeq.length()];
for (int i = 0; i < beta_Y.length; i++)
beta_Y[i] = new DenseDoubleMatrix1D(numY);
}
// compute beta values in a backward scan.
// also scale beta-values as much as possible to avoid numerical overflows
beta_Y[dataSeq.length()-1].assign(0);
for (int i = dataSeq.length()-2; i >= 0; i--) {
beta_Y[i].assign(RobustMath.LOG0);
for (int ell = 1; (ell <= featureGenNested.maxMemory()) && (i+ell < dataSeq.length()); ell++) {
// compute the Mi matrix
featureGenNested.startScanFeaturesAt(dataSeq, i, i+ell);
//if (! featureGenNested.hasNext())
// break;
initMDone = computeLogMi(featureGenNested,lambda,Mi_YY,Ri_Y,false,reuseM,initMDone);
tmp_Y.assign(beta_Y[i+ell]);
tmp_Y.assign(Ri_Y,sumFunc);
RobustMath.logMult(Mi_YY, tmp_Y, beta_Y[i],1,1,false,edgeGen);
}
}
double thisSeqLogli = 0;
alpha_Y_Array[0].assign(0);
int segmentStart = 0;
int segmentEnd = -1;
boolean invalid = false;
for (int i = 0; i < dataSeq.length(); i++) {
if (segmentEnd < i) {
segmentStart = i;
segmentEnd = dataSeq.getSegmentEnd(i);
}
if (segmentEnd-segmentStart+1 > featureGenNested.maxMemory()) {
if (icall == 0) {
System.out.println("Ignoring record with segment length greater than maxMemory " + numRecord);
}
invalid = true;
break;
}
alpha_Y_Array[i-base].assign(RobustMath.LOG0);
for (int ell = 1; (ell <= featureGenNested.maxMemory()) && (i-ell >= base); ell++) {
// compute the Mi matrix
featureGenNested.startScanFeaturesAt(dataSeq, i-ell,i);
// if (!featureGenNested.hasNext())
// break;
initMDone = computeLogMi(featureGenNested,lambda,Mi_YY,Ri_Y,false,reuseM,initMDone);
// find features that fire at this position..
featureGenNested.startScanFeaturesAt(dataSeq, i-ell,i);
boolean isSegment = ((i-ell+1==segmentStart) && (i == segmentEnd));
while (featureGenNested.hasNext()) {
Feature feature = featureGenNested.next();
int f = feature.index();
int yp = feature.y();
int yprev = feature.yprev();
float val = feature.value();
boolean allEllMatch = isSegment && (dataSeq.y(i) == yp);
if (allEllMatch && (((i-ell >= 0) && (yprev == dataSeq.y(i-ell))) || (yprev < 0))) {
grad[f] += val;
thisSeqLogli += val*lambda[f];
}
if ((yprev < 0) && (i-ell >= 0)) {
for (yprev = 0; yprev < Mi_YY.rows(); yprev++)
ExpF[f] = RobustMath.logSumExp(ExpF[f], (alpha_Y_Array[i-ell-base].get(yprev)+Ri_Y.get(yp)+Mi_YY.get(yprev,yp) + RobustMath.log(val)+beta_Y[i].get(yp)));
} else if (i-ell < 0) {
ExpF[f] = RobustMath.logSumExp(ExpF[f], (Ri_Y.get(yp)+RobustMath.log(val)+beta_Y[i].get(yp)));
} else {
ExpF[f] = RobustMath.logSumExp(ExpF[f], (alpha_Y_Array[i-ell-base].get(yprev)+Ri_Y.get(yp)+Mi_YY.get(yprev,yp)+RobustMath.log(val)+beta_Y[i].get(yp)));
}
}
if (i-ell >= 0) {
RobustMath.logMult(Mi_YY, alpha_Y_Array[i-ell-base],tmp_Y,1,0,true,edgeGen);
tmp_Y.assign(Ri_Y,sumFunc);
RobustMath.logSumExp(alpha_Y_Array[i-base],tmp_Y);
} else {
RobustMath.logSumExp(alpha_Y_Array[i-base],Ri_Y);
}
}
if (params.debugLvl > 2) {
System.out.println("Alpha-i " + alpha_Y_Array[i-base].toString());
System.out.println("Ri " + Ri_Y.toString());
System.out.println("Mi " + Mi_YY.toString());
System.out.println("Beta-i " + beta_Y[i].toString());
}
if (params.debugLvl > 1) {
System.out.println(" pos " + i + " " + thisSeqLogli);
}
}
if (invalid)
continue;
double lZx = RobustMath.logSumExp(alpha_Y_Array[dataSeq.length()-1-base]);
thisSeqLogli -= lZx;
logli += thisSeqLogli;
// update grad.
for (int f = 0; f < grad.length; f++)
grad[f] -= RobustMath.exp(ExpF[f]-lZx);
if (params.debugLvl > 1) {
System.out.println("Sequence " + thisSeqLogli + " " + logli + " " + Math.exp(lZx));
System.out.println("Last Alpha-i " + alpha_Y_Array[dataSeq.length()-1-base].toString());
}
}
if (params.debugLvl > 2) {
for (int f = 0; f < lambda.length; f++)
System.out.print(lambda[f] + " ");
System.out.println(" :x");
for (int f = 0; f < lambda.length; f++)
System.out.print(grad[f] + " ");
System.out.println(" :g");
}
if (params.debugLvl > 0)
Util.printDbg("Iter " + icall + " loglikelihood "+logli + " gnorm " + norm(grad) + " xnorm "+ norm(lambda));
return logli;
} catch (Exception e) {
e.printStackTrace();
System.exit(0);
}
return 0;
}
};
CRF/src/iitb/CRF/NestedViterbi.java 0000644 0001760 0001760 00000003256 10421454647 017671 0 ustar abhisheka abhisheka package iitb.CRF;
/**
*
* NestedViterbi search
*
* @author Sunita Sarawagi
*
*/
public class NestedViterbi extends Viterbi {
NestedCRF nestedModel;
NestedViterbi(NestedCRF nestedModel, int bs) {
super(nestedModel, bs);
this.nestedModel = nestedModel;
}
double fillArray(DataSequence dataSeq, double lambda[], boolean calcScore) {
int numY = model.numY;
int maxLen = nestedModel.featureGenNested.maxMemory();
for (int i = 0; i < dataSeq.length(); i++) {
for (int yi = 0; yi < numY; winningLabel[yi++][i].clear());
for (int ell = 1; (ell <= maxLen) && (i-ell >= -1); ell++) {
nestedModel.featureGenNested.startScanFeaturesAt(dataSeq, i-ell,i);
Trainer.computeLogMi(model.featureGenerator,lambda,Mi,Ri,false);
for (int yi = 0; yi < numY; yi++) {
if (i-ell < 0) {
winningLabel[yi][i].add((float)Ri.get(yi));
} else {
for (int yp = 0; yp < numY; yp++) {
double val = Mi.get(yp,yi)+Ri.get(yi);
winningLabel[yi][i].add(winningLabel[yp][i-ell], (float)val);
}
}
}
}
}
return 0;
}
public void bestLabelSequence(SegmentDataSequence dataSeq, double lambda[]) {
viterbiSearch(dataSeq, lambda,false);
Soln ybest = finalSoln.get(0);
ybest = ybest.prevSoln;
while (ybest != null) {
dataSeq.setSegment(ybest.prevPos()+1,ybest.pos,ybest.label);
ybest = ybest.prevSoln;
}
}
};
CRF/src/iitb/CRF/Segmentation.java 0000644 0001760 0001760 00000000675 10421454647 017561 0 ustar abhisheka abhisheka /*
* Created on Nov 17, 2004
*
*/
package iitb.CRF;
/**
*
*/
public interface Segmentation {
int numSegments(); //number of segments in the record
int segmentLabel(int segmentNum); //label of each segment
int segmentStart(int segmentNum);
int segmentEnd(int segmentNum);
// get the segment-id that contains the given offset position
int getSegmentId(int offset);
void setSegment(int segmentStart, int segmentEnd, int label);
};
CRF/src/iitb/CRF/Constraint.java 0000644 0001760 0001760 00000000764 10421454647 017247 0 ustar abhisheka abhisheka /*
* Created on Dec 3, 2004
*
* TODO To change the template for this generated file go to
* Window - Preferences - Java - Code Style - Code Templates
*/
package iitb.CRF;
/**
* @author Administrator
*
* TODO To change the template for this generated type comment go to
* Window - Preferences - Java - Code Style - Code Templates
*/
public interface Constraint {
public static int UNION=1;
public static int PAIR_DISALLOW=2;
public static final int ALLOW_ONLY = 3;
public int type();
}
CRF/src/iitb/CRF/CRF.java 0000644 0001760 0001760 00000010611 10421712571 015516 0 ustar abhisheka abhisheka package iitb.CRF;
import java.io.BufferedReader;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.io.Serializable;
/**
*
* CRF (conditional random fields) This class provides support for
* training and applying a conditional random field for sequence
* labeling problems.
*
* @author Sunita Sarawagi
*
*/
public class CRF implements Serializable {
/**
* Comment for serialVersionUID
*/
private static final long serialVersionUID = 14L;
double lambda[];
protected int numY;
transient Trainer trainer;
FeatureGenerator featureGenerator;
EdgeGenerator edgeGen;
HistoryManager histMgr;
public CrfParams params;
transient Viterbi viterbi;
/**
* @param numLabels is the number of distinct class labels or y-labels
* @param fgen is the class that is responsible for providing
* the features for a particular position on the sequence.
* @param arg is a string that can be used to control various
* parameters of the CRF, these are space separated name-value pairs
* described in
* @see iitb.CRF.CrfParams
*/
public CRF(int numLabels, FeatureGenerator fgen, String arg) {
this(numLabels, fgen, CrfParams.stringToOptions(arg));
}
public CRF(int numLabels, FeatureGenerator fgen, java.util.Properties configOptions) {
this(numLabels,1,fgen,configOptions);
}
public CRF(int numLabels, int histsize, FeatureGenerator fgen, java.util.Properties configOptions) {
histMgr = new HistoryManager(histsize,numLabels);
featureGenerator = histMgr.getFeatureGen(fgen);
numY = histMgr.numY;
if(configOptions != null)
params = new CrfParams(configOptions);
edgeGen = histMgr.getEdgeGenerator();
viterbi = getViterbi(1);
}
/*
* useful for resetting Viterbi options after loading a saved model.
*/
public void reinitOptions(java.util.Properties configOptions) {
params = new CrfParams(configOptions);
viterbi = null;
}
/**
* write the trained parameters of the CRF to the file
*/
public void write(String fileName) throws IOException {
PrintWriter out=new PrintWriter(new FileOutputStream(fileName));
out.println(lambda.length);
for (int i = 0; i < lambda.length; i++)
out.println(lambda[i]);
out.close();
}
/**
* read the parameters of the CRF from a file
*/
public void read(String fileName) throws IOException {
BufferedReader in=new BufferedReader(new FileReader(fileName));
int numF = Integer.parseInt(in.readLine());
lambda = new double[numF];
int pos = 0;
String line;
while((line=in.readLine())!=null) {
lambda[pos++] = Double.parseDouble(line);
}
}
protected Trainer getTrainer() {
if (params.trainerType.startsWith("Collins"))
return new CollinsTrainer(params);
return new Trainer(params);
}
protected Viterbi getViterbi(int beamsize) {
return new Viterbi(this,beamsize);
}
/**
* Trains the model given the data
* @return the learnt parameter value as an array
*/
public double[] train(DataIter trainData) {
return train(trainData,null);
}
/**
* Trains the model given the data
* @return the learnt parameter value as an array
*/
public double[] train(DataIter trainData, Evaluator evaluator) {
lambda = new double[featureGenerator.numFeatures()];
trainer = getTrainer();
//System.out.println("got trainer");
trainer.train(this, histMgr.mapTrainData(trainData), lambda, evaluator);
return lambda;
}
public double[] learntWeights() {
return lambda;
}
public void apply(DataSequence dataSeq) {
if (viterbi==null)
viterbi = getViterbi(1);
if (params.debugLvl > 1)
Util.printDbg("CRF: Applying on " + dataSeq);
viterbi.bestLabelSequence(dataSeq,lambda);
if (histMgr != null) {
for(int i = dataSeq.length()-1; i >= 0; i--) {
histMgr.set_y(dataSeq, i, dataSeq.y(i));
}
}
}
public double score(DataSequence dataSeq) {
if (viterbi==null)
viterbi = getViterbi(1);
return viterbi.viterbiSearch(dataSeq,lambda,true);
}
};
CRF/src/iitb/CRF/RobustMath.java 0000644 0001760 0001760 00000016741 10421544046 017206 0 ustar abhisheka abhisheka package iitb.CRF;
import java.util.TreeSet;
import cern.colt.function.DoubleDoubleFunction;
import cern.colt.function.IntIntDoubleFunction;
import cern.colt.matrix.DoubleMatrix1D;
import cern.colt.matrix.DoubleMatrix2D;
public class RobustMath {
public static double LOG0 = -1*Double.MAX_VALUE;
public static double LOG2 = 0.69314718055;
static final double MINUS_LOG_EPSILON = 30; //-1*Math.log(Double.MIN_VALUE);
static class LogExpCache {
static int CUT_OFF = 6;
static int NUM_FINE = 10000;
static int NUM_COARSE = 1000;
static boolean useCache = true;
static double vals[] = new double[CUT_OFF*NUM_FINE+((int)MINUS_LOG_EPSILON-CUT_OFF)*NUM_COARSE+1];
static {
for(int i = vals.length-1; i >= 0; vals[i--]=-1);
}
static double lookupAdd(double val) {
if (!useCache)
return Math.log(Math.exp(-1*val) + 1.0);
int index = 0;
//assert ((val < MINUS_LOG_EPSILON) && (val > 0));
if (val < CUT_OFF) {
index = (int)Math.rint(val*NUM_FINE);
} else {
index = NUM_FINE*CUT_OFF + (int)Math.rint((val-CUT_OFF)*NUM_COARSE);
}
if (vals[index] < 0)
vals[index] = Math.log(Math.exp(-1*val) + 1.0);
return vals[index];
}
};
public static double logSumExp(double v1, double v2) {
if (Math.abs(v1-v2) < Double.MIN_VALUE)
return v1 + LOG2;
double vmin = Math.min(v1,v2);
double vmax = Math.max(v1,v2);
if ( vmax > vmin + MINUS_LOG_EPSILON ) {
return vmax;
} else {
return vmax + LogExpCache.lookupAdd(vmax-vmin);
/*
double retval = vmax + Math.log(Math.exp(vmin-vmax) + 1.0);
//System.out.println((vmax-vmin) + " " + (retval-vmax));
return retval;
*/
}
}
static class LogSumExp implements DoubleDoubleFunction {
public double apply(double v1, double v2) {
return logSumExp(v1,v2);
}
};
public static LogSumExp logSumExpFunc = new LogSumExp();
static void addNoDups(TreeSet vec, double v) {
Double val = new Double(v);
if (!vec.add(val)) {
vec.remove(val);
addNoDups(vec, val.doubleValue()+LOG2);
}
}
public static double logSumExp(TreeSet logProbVector) {
while ( logProbVector.size() > 1 ) {
double lp0 = ((Double)logProbVector.first()).doubleValue();
logProbVector.remove(logProbVector.first());
double lp1 = ((Double)logProbVector.first()).doubleValue();
logProbVector.remove(logProbVector.first());
addNoDups(logProbVector,logSumExp(lp0,lp1));
}
if (logProbVector.size() > 0)
return ((Double)logProbVector.first()).doubleValue();
return RobustMath.LOG0;
}
// matrix stuff for the older version..
static double logSumExp(DoubleMatrix1D logProb) {
TreeSet logProbVector = new TreeSet();
for ( int lpx = 0; lpx < logProb.size(); lpx++ )
if (logProb.getQuick(lpx) != RobustMath.LOG0)
addNoDups(logProbVector,logProb.getQuick(lpx));
return logSumExp(logProbVector);
}
static void logSumExp(DoubleMatrix1D v1, DoubleMatrix1D v2) {
for (int i = 0; i < v1.size(); i++) {
v1.set(i,logSumExp(v1.get(i), v2.get(i)));
}
}
static class LogMult implements IntIntDoubleFunction {
DoubleMatrix2D M;
DoubleMatrix1D z;
double lalpha;
boolean transposeA;
DoubleMatrix1D y;
public double apply(int i, int j, double val) {
int r = i;
int c = j;
if (transposeA) {
r = j;
c = i;
}
z.set(r, RobustMath.logSumExp(z.get(r), M.get(i,j)+y.get(c)+lalpha));
return val;
}
};
static LogMult logMult = new LogMult();
public static DoubleMatrix1D logMult(DoubleMatrix2D M, DoubleMatrix1D y, DoubleMatrix1D z, double alpha, double beta, boolean transposeA) {
// z = alpha * A * y + beta*z
double lalpha = 0;
if (alpha != 1)
lalpha = Math.log(alpha);
if (beta != 0) {
if (beta != 1) {
double lbeta = Math.log(beta);
for (int i = 0; i < z.size(); z.set(i,z.get(i)+lbeta),i++);
}
} else {
z.assign(RobustMath.LOG0);
}
// in log domain this becomes:
logMult.M = M;
logMult.z = z;
logMult.lalpha = lalpha;
logMult.transposeA = transposeA;
logMult.y = y;
M.forEachNonZero(logMult);
return z;
}
static DoubleMatrix1D logMult(DoubleMatrix2D M, DoubleMatrix1D y, DoubleMatrix1D z, double alpha, double beta, boolean transposeA, EdgeGenerator edgeGen) {
// z = alpha * A * y + beta*z
// in log domain this becomes:
double lalpha = 0;
if (alpha != 1)
lalpha = Math.log(alpha);
if (beta != 0) {
if (beta != 1) {
for (int i = 0; i < z.size(); z.set(i,z.get(i)+Math.log(beta)),i++);
}
} else {
z.assign(LOG0);
}
for (int j = 0; j < M.columns(); j++) {
for (int i = edgeGen.first(j); i < M.rows(); i = edgeGen.next(j,i)) {
int r = i;
int c = j;
if (transposeA) {
r = j;
c = i;
}
z.setQuick(r, logSumExp(z.getQuick(r), M.getQuick(i,j)+y.get(c)+lalpha));
}
}
return z;
}
static DoubleMatrix1D Mult(DoubleMatrix2D M, DoubleMatrix1D y, DoubleMatrix1D z, double alpha, double beta, boolean transposeA, EdgeGenerator edgeGen) {
// z = alpha * A * y + beta*z
for (int i = 0; i < z.size(); z.set(i,z.get(i)*beta),i++);
for (int j = 0; j < M.columns(); j++) {
for (int i = edgeGen.first(j); i < M.rows(); i = edgeGen.next(j,i)) {
int r = i;
int c = j;
if (transposeA) {
r = j;
c = i;
}
z.set(r, z.getQuick(r) + M.getQuick(i,j)*y.getQuick(c)*alpha);
}
}
return z;
}
public static void main(String args[]) {
// double vals[] = new double[]{10.172079, 7.452882, 2.429751, 7.452882, 10.818797, 8.573773, 19.215824};
/*double vals[] = new double[]{2.883626, 1.670196, 0.553112, 1.670196, -0.935964, 1.864568, 2.064754};
TreeSet vec = new TreeSet();
double trueSum = 0;
for (int i = 0; i < vals.length; i++) {
addNoDups(vec,vals[i]);
trueSum += Math.exp(vals[i]);
}
double sum = logSumExp(vec);
*/
System.out.println(logSumExp(Double.parseDouble(args[0]), Double.parseDouble(args[1])));
}
/**
* @param d
* @return
*/
public static double exp(double d) {
if (Double.isInfinite(d) || ((d < 0) && (Math.abs(d) > MINUS_LOG_EPSILON)))
return 0;
//if ((d > 0) && (d < Double.MIN_VALUE))
// return 1;
//System.out.println(d + " " + Math.exp(d));
return Math.exp(d);
}
/**
* @param val
* @return
*/
public static double log(float val) {
return (Math.abs(val-1) < Double.MIN_VALUE)?0:Math.log(val);
}
};
CRF/src/iitb/CRF/CollinsTrainer.java 0000644 0001760 0001760 00000013465 10421544045 020045 0 ustar abhisheka abhisheka package iitb.CRF;
import java.util.Vector;
/**
* Implements the CollinsVotedPerceptron training algorithm
*
* @author Sunita Sarawagi
*
*/
class CollinsTrainer extends Trainer {
int beamsize = 3;
double beta = 0.05;
boolean useUpdated = false;
boolean voted = true;
Soln solnPool[]; // for efficiency
public CollinsTrainer(CrfParams p) {
super(p);
if (params.miscOptions.getProperty("beamSize") != null)
beamsize = Integer.parseInt(params.miscOptions.getProperty("beamSize"));
if (params.miscOptions.getProperty("beta") != null)
beta = Double.parseDouble(params.miscOptions.getProperty("beta"));
if (params.miscOptions.getProperty("UpdatedViterbi") != null)
useUpdated = params.miscOptions.getProperty("UpdatedViterbi").equalsIgnoreCase("true");
if (params.miscOptions.getProperty("voted") != null)
voted = params.miscOptions.getProperty("voted").equalsIgnoreCase("true");
}
public void train(CRF model, DataIter data, double[] l, Evaluator eval) {
init(model,data,l);
double grad[] = gradLogli; // reusing parent's structures.
Viterbi viterbiSearcher = model.getViterbi(beamsize);
for (int i = 0; i < lambda.length; i++)
lambda[i] = grad[i] = 0;
Vector viterbiS = new Vector();
for (int t = 0; t < params.maxIters; t++) {
int numErrs = 0;
diter.startScan();
for (int numRecord = 0; diter.hasNext(); numRecord++) {
DataSequence dataSeq = (DataSequence)diter.next();
viterbiSearcher.viterbiSearch(dataSeq,(useUpdated)?lambda:grad, false);
Soln corrSoln = getCorrectSoln(dataSeq,(useUpdated)?lambda:grad);
double corrScore = corrSoln.score;
int maxNum = viterbiSearcher.numSolutions();
viterbiS.clear();
for (int k = 0; k < maxNum; k++) {
Soln viterbi = viterbiSearcher.getBestSoln(k);
if (viterbi.score < corrScore*(1-beta))
break;
if ( !isCorrect(viterbi,corrSoln)) {
viterbiS.add(viterbi);
//System.out.println("adding " + viterbiS.size() + " " + viterbi.score + " " + corrScore + " grad " + norm(grad));
}
}
if (viterbiS.size() > 0) {
for (; corrSoln != null; corrSoln = corrSoln.prevSoln) {
boolean differenceAtI = false;
for (int s = 0; s < viterbiS.size(); s++) {
Soln viterbi = (Soln) viterbiS.elementAt(s);
if ((viterbi == null) || !corrSoln.equals(viterbi)) {
differenceAtI = true;
break;
}
}
if (differenceAtI) {
numErrs++;
updateWeights(corrSoln, 1.0, grad, dataSeq);
for (int s = 0; s < viterbiS.size(); s++) {
Soln viterbi = (Soln) viterbiS.elementAt(s);
// if (within current frontier, i.e. endpoint overlaps with current segment
for (;(viterbi != null) && (viterbi.pos > corrSoln.prevPos()); viterbi = viterbi.prevSoln) {
updateWeights(viterbi, -1.0/viterbiS.size(), grad, dataSeq);
}
}
/*System.out.println("gnorm at " + corrSoln.pos + " " + norm(grad));
for (int s = 0; s < viterbiS.size(); s++) {
Soln viterbi = (Soln) viterbiS.elementAt(s);
System.out.println(s + " viterbi " + viterbi.pos + " " + viterbi.label);
}*/
}
// advance all viterbi solutions..
for (int s = 0; s < viterbiS.size(); s++) {
Soln viterbi = (Soln) viterbiS.elementAt(s);
// if (within current frontier, i.e. endpoint overlaps with current segment
for (;(viterbi != null) && (viterbi.pos > corrSoln.prevPos()); viterbi = viterbi.prevSoln);
viterbiS.set(s,viterbi);
}
}
}
// voted perceptron, so add.
for (int f = 0; f < lambda.length; f++)
lambda[f] += grad[f];
} // all records.
if (params.debugLvl > 0)
Util.printDbg("Iteration " + t + " numErrs "+ numErrs);
if (numErrs == 0)
break;
}
}
boolean isCorrect(Soln viterbi, Soln corr) {
for (; (viterbi != null) && (corr != null); corr = corr.prevSoln, viterbi = viterbi.prevSoln) {
if (!viterbi.equals(corr))
return false;
}
return ((viterbi == null) && (corr == null));
}
int getSegmentEnd(DataSequence dataSeq, int ss) {
return ss;
}
void startFeatureGenerator(FeatureGenerator _featureGenerator, DataSequence dataSeq, Soln soln) {
_featureGenerator.startScanFeaturesAt(dataSeq, soln.pos);
}
void updateWeights(Soln soln, double wt, double grad[], DataSequence dataSeq) {
startFeatureGenerator(featureGenerator,dataSeq,soln);
while (featureGenerator.hasNext()) {
Feature feature = featureGenerator.next();
int f = feature.index();
int yp = feature.y();
int yprev = feature.yprev();
float val = feature.value();
if ((soln.label == yp) && (((soln.prevPos() >= 0) && (yprev == soln.prevSoln.label)) || (yprev < 0))) {
grad[f] += wt*val;
/* if (soln.prevPos() < 0)
System.out.println("Updating " + soln.label + " ");
else
System.out.println("Updating " + soln.label + " " + yprev + " " + soln.prevSoln.label);
*/
}
}
}
Soln getCorrectSoln(DataSequence dataSeq, double grad[]) {
int se = 0;
Soln prevSoln = null;
if ((solnPool == null) || solnPool.length < dataSeq.length()) {
solnPool = new Soln[dataSeq.length()];
for (int i = 0; i < dataSeq.length(); solnPool[i++] = new Soln(0,0));
}
for (int ss = 0; ss < dataSeq.length(); ss = se+1) {
se = getSegmentEnd(dataSeq, ss);
Soln soln = solnPool[ss];
soln.pos = se;
soln.label = dataSeq.y(ss);
soln.prevSoln = prevSoln;
soln.score = (prevSoln == null)?0:prevSoln.score;
startFeatureGenerator(featureGenerator,dataSeq,soln);
while (featureGenerator.hasNext()) {
Feature feature = featureGenerator.next();
int f = feature.index();
int yp = feature.y();
int yprev = feature.yprev();
float val = feature.value();
if ((soln.label == yp) && (((soln.prevPos() >= 0) && (yprev == soln.prevSoln.label)) || (yprev < 0))) {
soln.score += grad[f]*val;
}
}
prevSoln = soln;
}
return prevSoln;
}
};
CRF/src/iitb/CRF/Viterbi.java 0000644 0001760 0001760 00000013152 10421546755 016524 0 ustar abhisheka abhisheka package iitb.CRF;
import java.io.Serializable;
import cern.colt.matrix.DoubleMatrix1D;
import cern.colt.matrix.DoubleMatrix2D;
import cern.colt.matrix.impl.DenseDoubleMatrix1D;
import cern.colt.matrix.impl.DenseDoubleMatrix2D;
/**
*
* Viterbi search
*
* @author Sunita Sarawagi
*
*/
public class Viterbi implements Serializable {
private static final long serialVersionUID = 8122L;
protected CRF model;
protected int beamsize;
Viterbi(CRF model, int bs) {
this.model = model;
beamsize = bs;
// if (model.params.miscOptions.getProperty("beamSize") != null)
// beamsize = Integer.parseInt(model.params.miscOptions.getProperty("beamSize"));
}
protected class Entry {
public Soln solns[]; // TODO.
boolean valid=true;
protected Entry() {}
protected Entry(int beamsize, int id, int pos) {
solns = new Soln[beamsize];
for (int i = 0; i < solns.length; i++)
solns[i] = newSoln(id, pos);
}
protected Soln newSoln(int label, int pos) {
return new Soln(label,pos);
}
protected void clear() {
valid = false;
for (int i = 0; i < solns.length; i++)
solns[i].clear();
}
protected int size() {return solns.length;}
protected Soln get(int i) {return solns[i];}
protected void insert(int i, float score, Soln prev) {
for (int k = size()-1; k > i; k--) {
solns[k].copy(solns[k-1]);
}
solns[i].setPrevSoln(prev,score);
}
protected void add(Entry e, float thisScore) {
assert(valid);
if (e == null) {
add(thisScore);
return;
}
int insertPos = 0;
for (int i = 0; (i < e.size()) && (insertPos < size()); i++) {
float score = e.get(i).score + thisScore;
insertPos = findInsert(insertPos, score, e.get(i));
}
// print();
}
protected int findInsert(int insertPos, float score, Soln prev) {
for (; insertPos < size(); insertPos++) {
if (score >= get(insertPos).score) {
insert(insertPos, score, prev);
insertPos++;
break;
}
}
return insertPos;
}
protected void add(float thisScore) {
findInsert(0, thisScore, null);
}
protected int numSolns() {
for (int i = 0; i < solns.length; i++)
if (solns[i].isClear())
return i;
return size();
}
public void setValid() {valid=true;}
void print() {
String str = "";
for (int i = 0; i < size(); i++)
str += ("["+i + " " + solns[i].score + " i:" + solns[i].pos + " y:" + solns[i].label+"]");
System.out.println(str);
}
};
Entry winningLabel[][];
protected Entry finalSoln;
protected DoubleMatrix2D Mi;
protected DoubleMatrix1D Ri;
void allocateScratch(int numY) {
Mi = new DenseDoubleMatrix2D(numY,numY);
Ri = new DenseDoubleMatrix1D(numY);
winningLabel = new Entry[numY][];
finalSoln = new Entry(beamsize,0,0);
}
double fillArray(DataSequence dataSeq, double lambda[], boolean calcScore) {
double corrScore = 0;
int numY = model.numY;
for (int i = 0; i < dataSeq.length(); i++) {
// compute Mi.
Trainer.computeLogMi(model.featureGenerator,lambda,dataSeq,i,Mi,Ri,false);
for (int yi = 0; yi < numY; yi++) {
winningLabel[yi][i].clear();
winningLabel[yi][i].valid = true;
}
for (int yi = model.edgeGen.firstY(i); yi < numY; yi = model.edgeGen.nextY(yi,i)) {
if (i > 0) {
for (int yp = model.edgeGen.first(yi); yp < numY; yp = model.edgeGen.next(yi,yp)) {
double val = Mi.get(yp,yi)+Ri.get(yi);
winningLabel[yi][i].add(winningLabel[yp][i-1], (float)val);
}
} else {
winningLabel[yi][i].add((float)Ri.get(yi));
}
}
if (calcScore)
corrScore += (Ri.get(dataSeq.y(i)) + ((i > 0)?Mi.get(dataSeq.y(i-1),dataSeq.y(i)):0));
}
return corrScore;
}
protected void setSegment(DataSequence dataSeq, int prevPos, int pos, int label) {
dataSeq.set_y(pos, label);
}
public void bestLabelSequence(DataSequence dataSeq, double lambda[]) {
double corrScore = viterbiSearch(dataSeq, lambda,false);
assignLabels(dataSeq);
}
void assignLabels(DataSequence dataSeq) {
Soln ybest = finalSoln.get(0);
ybest = ybest.prevSoln;
int pos=-1;
while (ybest != null) {
pos = ybest.pos;
setSegment(dataSeq,ybest.prevPos(),ybest.pos, ybest.label);
ybest = ybest.prevSoln;
}
assert(pos>=0);
}
public double viterbiSearch(DataSequence dataSeq, double lambda[], boolean calcCorrectScore) {
if (Mi == null) {
allocateScratch(model.numY);
}
if ((winningLabel[0] == null) || (winningLabel[0].length < dataSeq.length())) {
for (int yi = 0; yi < winningLabel.length; yi++) {
winningLabel[yi] = new Entry[dataSeq.length()];
for (int l = 0; l < dataSeq.length(); l++)
winningLabel[yi][l] = new Entry((l==0)?1:beamsize, yi, l);
}
}
double corrScore = fillArray(dataSeq, lambda,calcCorrectScore);
finalSoln.clear();
finalSoln.valid = true;
for (int yi = 0; yi < model.numY; yi++) {
finalSoln.add(winningLabel[yi][dataSeq.length()-1], 0);
}
return corrScore;
}
int numSolutions() {return finalSoln.numSolns();}
Soln getBestSoln(int k) {
return finalSoln.get(k).prevSoln;
}
};
CRF/src/iitb/CRF/HistoryManager.java 0000644 0001760 0001760 00000011417 10421544045 020044 0 ustar abhisheka abhisheka package iitb.CRF;
import iitb.Utils.Counters;
import java.io.Serializable;
class EdgeGenerator implements Serializable {
int offset;
int numOrigY;
int histsize;
EdgeGenerator(int histsize, int numOrigY) {
offset = 1;
for (int i = 0; i < histsize-1; i++)
offset *= numOrigY;
this.numOrigY = numOrigY;
this.histsize = histsize;
}
int first(int destY) {
return destY/numOrigY;
}
int next(int destY, int currentSrcY) {
return currentSrcY + offset;
}
int firstY(int pos) {
return 0;
}
int nextY(int currentY, int pos) {
if ((pos >= histsize-1) || (currentY < numOrigY-1))
return currentY+1;
if (currentY >= Math.pow(numOrigY,(pos+1)))
return numOrigY*offset;
return currentY+1;
}
};
class HistoryManager implements Serializable {
int histsize;
int numOrigY;
int numY;
HistoryManager(int histsize, int num) {
this.histsize = histsize;
numOrigY = num;
this.numY = num;
for (int i = 0; i < histsize-1; numY *= num, i++);
};
FeatureGenerator getFeatureGen(FeatureGenerator fgen) {
if (histsize == 1)
return fgen;
return new FeatureGeneratorWithHistory(fgen);
};
DataIter mapTrainData(DataIter trainData) {
if (histsize == 1)
return trainData;
return new DataIterHistory(trainData);
};
void set_y(DataSequence data, int i, int label) {
if (histsize > 1) data.set_y(i,label%numOrigY);
}
EdgeGenerator getEdgeGenerator() {
return new EdgeGenerator(histsize,numOrigY);
}
class FeatureHist implements Feature {
Feature orig;
Counters ctr;
FeatureHist() {}
FeatureHist(int histsize, int numOrigY) {
ctr = new Counters(histsize+1, numOrigY);
}
void init(Feature f) {
orig = f;
ctr.clear();
ctr.fix(0,orig.y());
ctr.fix(histsize,0);
if (orig.yprev() != -1) {
ctr.fix(1,orig.yprev());
}
/*
if (pos == 0) {
for (int i = 1; i < histsize; i++)
ctr.fix(i,0);
}
*/
if (orig.yprevArray() != null) {
for (int i = 0; i < orig.yprevArray().length; i++) {
if (orig.yprevArray()[i] != -1)
ctr.fix(i+1, orig.yprevArray()[i]);
}
}
}
boolean advance() {
return ctr.advance();
}
public int index() {return orig.index();}
public int y() {return ctr.value(histsize-1,0);}
public int yprev() {
if ((orig.yprevArray() == null) || (orig.yprevArray()[histsize-1] == -1))
return -1;
return ctr.value(histsize,1);
}
public int[] yprevArray() {return null;}
public float value() {return orig.value();}
String type() {return "H ";}
void print() {System.out.println(type() + index() + " " + y() + " " + yprev() + " " + value());}
};
class FeatureGeneratorWithHistory implements FeatureGenerator {
FeatureGenerator fgen;
FeatureHist currentFeature, histFeature;
boolean allDone;
iitb.Model.FeatureImpl feature = new iitb.Model.FeatureImpl();
FeatureGeneratorWithHistory(FeatureGenerator fgen) {
this.fgen = fgen;
histFeature = new FeatureHist(histsize,numOrigY);
}
public int numFeatures() {return fgen.numFeatures();} // + numY*numOrigY;}
public void startScanFeaturesAt(DataSequence data, int pos) {
fgen.startScanFeaturesAt(data,pos);
allDone = false;
if (fgen.hasNext()) {
currentFeature = histFeature;
currentFeature.init(fgen.next());
} else
allDone = true;
}
public boolean hasNext() {return !allDone;}
public Feature next() {
feature.copy(currentFeature);
//currentFeature.print();
boolean nextY = currentFeature.advance();
if (!nextY) {
if (fgen.hasNext())
currentFeature.init(fgen.next());
//else if (currentFeature != edgeFeatures)
// currentFeature = edgeFeatures;
else
allDone = true;
}
return feature;
}
/* (non-Javadoc)
* @see iitb.CRF.FeatureGenerator#featureName(int)
*/
public String featureName(int featureIndex) {
return fgen.featureName(featureIndex);
}
};
class DataSequenceHist implements DataSequence {
Counters cntr;
transient DataSequence orig;
DataSequenceHist() {cntr = new Counters(histsize,numOrigY);}
void init(DataSequence orig) {
this.orig = orig;
}
public int length() {return orig.length();}
public int y(int i) {
cntr.clear();
for(int k = histsize-1; k >= 0; k--)
if (i-k >= 0)
cntr.fix(k,orig.y(i-k));
else
cntr.fix(k,0);
return cntr.value();
}
public Object x(int i) {return orig.x(i);}
public void set_y(int i, int label) {}
};
class DataIterHistory implements DataIter {
DataIter orig;
DataSequenceHist dataSeq;
DataIterHistory(DataIter orig) {
this.orig = orig;
dataSeq = new DataSequenceHist();
}
public void startScan() {orig.startScan();}
public boolean hasNext() {return orig.hasNext();}
public DataSequence next() {dataSeq.init(orig.next()); return dataSeq;}
};
};
CRF/src/iitb/CRF/Evaluator.java 0000644 0001760 0001760 00000000464 10421454647 017062 0 ustar abhisheka abhisheka package iitb.CRF;
/*
* If this is given as an argument to train() then during the training
* loop this function will be called at each iteration. If evaluate
* returns false, the training loop will exit.
*
* @author Sunita Sarawagi
*
*/
public interface Evaluator {
public boolean evaluate();
};
CRF/src/iitb/CRF/NestedCRF.java 0000644 0001760 0001760 00000002333 10421454647 016672 0 ustar abhisheka abhisheka package iitb.CRF;
/**
*
* @author Sunita Sarawagi
*
*/
public class NestedCRF extends CRF {
FeatureGeneratorNested featureGenNested;
transient NestedViterbi nestedViterbi;
public NestedCRF(int numLabels, FeatureGeneratorNested fgen, String arg) {
super(numLabels,fgen,arg);
featureGenNested = fgen;
nestedViterbi = new NestedViterbi(this,1);
}
public NestedCRF(int numLabels, FeatureGeneratorNested fgen, java.util.Properties configOptions) {
super(numLabels,fgen,configOptions);
featureGenNested = fgen;
nestedViterbi = new NestedViterbi(this,1);
}
protected Trainer getTrainer() {
if (params.trainerType.startsWith("SegmentCollins"))
return new NestedCollinsTrainer(params);
return new NestedTrainer(params);
}
protected Viterbi getViterbi(int beamsize) {
return new NestedViterbi(this,beamsize);
}
public void apply(DataSequence dataSeq) {
apply((SegmentDataSequence)dataSeq);
}
public void apply(SegmentDataSequence dataSeq) {
if (nestedViterbi==null)
nestedViterbi = new NestedViterbi(this,1);
if (params.debugLvl > 2)
Util.printDbg("NestedCRF: Applying on " + dataSeq);
nestedViterbi.bestLabelSequence(dataSeq,lambda);
}
};
CRF/src/iitb/CRF/LogSparseDoubleMatrix1D.java 0000644 0001760 0001760 00000015223 10421544045 021513 0 ustar abhisheka abhisheka package iitb.CRF;
import gnu.trove.TIntDoubleHashMap;
import gnu.trove.TIntDoubleIterator;
import java.util.TreeSet;
import cern.colt.function.DoubleDoubleFunction;
import cern.colt.function.IntDoubleFunction;
import cern.colt.matrix.DoubleMatrix1D;
import cern.colt.matrix.DoubleMatrix2D;
import cern.colt.matrix.impl.SparseDoubleMatrix1D;
//this needs to be done to support an efficient sparse implementation
//of matrices in the log-space
public class LogSparseDoubleMatrix1D extends SparseDoubleMatrix1D {
static double map(double val) {
if (val == RobustMath.LOG0)
return 0;
if (val == 0)
return Double.MIN_VALUE;
return val;
}
static double reverseMap(double val) {
if (val == 0) {
return RobustMath.LOG0;
}
if (val == Double.MIN_VALUE)
return 0;
return val;
}
public LogSparseDoubleMatrix1D(int numY) {super(numY);}
public DoubleMatrix1D assign(double val) {
return super.assign(map(val));
}
public void set(int row, double val) {
super.set(row,map(val));
}
public double get(int row) {
return reverseMap(super.get(row));
}
public double zSum() {
TreeSet logProbVector = new TreeSet();
// TODO
for (int row = 0; row < size(); row++) {
if (getQuick(row) != 0)
RobustMath.addNoDups(logProbVector,get(row));
}
return RobustMath.logSumExp(logProbVector);
}
// WARNING: this is only correct for functions that leave the infinity unchanged.
public SparseDoubleMatrix1D forEachNonZero(IntDoubleFunction func) {
for (int y = 0; y < size(); y++) {
if (getQuick(y) != 0)
setQuick(y,func.apply(y,get(y)));
}
return this;
}
// WARNING: this is only correct for functions that leave the infinity unchanged.
public DoubleMatrix1D assign(DoubleMatrix1D v2, DoubleDoubleFunction func) {
// TODO..
for (int row = 0; row < size(); row++) {
if ((v2.getQuick(row) != 0) || (getQuick(row) != 0))
set(row,func.apply(get(row), v2.get(row)));
}
return this;
}
public boolean equals(Object arg) {
DoubleMatrix1D mat = (DoubleMatrix1D)arg;
for (int row = size()-1; row >= 0; row--)
if (Math.abs(mat.get(row)-get(row))/Math.abs(mat.get(row)) > 0.0001)
return false;
return true;
}
};
class LogSparseDoubleMatrix1DOld extends SparseDoubleMatrix1D {
private static final long serialVersionUID = 1L;
TIntDoubleHashMap elementsZ;
static double map(double val) {
if (val == RobustMath.LOG0)
return 0;
if (val == 0)
return Double.MIN_VALUE;
return val;
}
static double reverseMap(double val) {
if (val == 0) {
return RobustMath.LOG0;
}
if (val == Double.MIN_VALUE)
return 0;
return val;
}
LogSparseDoubleMatrix1DOld(int numY) {
super(numY);
elementsZ = new TIntDoubleHashMap();
}
public DoubleMatrix1D assign(double val) {
//super.assign(map(val));
double newVal = map(val);
if (newVal != 0) {
for (int i = size()-1; i >= 0; i--)
setQuick(i,newVal);
}
return this;
}
public void set(int row, double val) {
setQuick(row,map(val));
}
public double get(int row) {
return reverseMap(getQuick(row));
}
public double zSum() {
TreeSet logProbVector = new TreeSet();
// TODO
for (int row = 0; row < size(); row++) {
if (getQuick(row) != 0)
RobustMath.addNoDups(logProbVector,get(row));
}
return RobustMath.logSumExp(logProbVector);
}
/* static class IntDoubleFunctionWrapper implements IntDoubleFunction {
IntDoubleFunction func;
public double apply(int row, double val) {
return func.apply(row, reverseMap(val));
}
}
IntDoubleFunctionWrapper funcWrapper = new IntDoubleFunctionWrapper();
public SparseDoubleMatrix1D forEachNonZero(IntDoubleFunction func) {
funcWrapper.func = func;
return this;
//return super.forEachNonZero(funcWrapper);
}
*/
// WARNING: this is only correct for functions that leave the infinity unchanged.
public DoubleMatrix1D forEachNonZero(IntDoubleFunction func) {
for (int y = 0; y < size(); y++) {
if (getQuick(y) != 0)
setQuick(y,func.apply(y,get(y)));
}
return this;
}
static class DoubleDoubleFunctionWrapper implements DoubleDoubleFunction {
DoubleDoubleFunction func;
public double apply(double val1, double val2) {
return map(func.apply(reverseMap(val1), reverseMap(val2)));
}
}
DoubleDoubleFunctionWrapper funcWrapper = new DoubleDoubleFunctionWrapper();
// WARNING: this is only correct for functions that leave the infinity unchanged.
public DoubleMatrix1D assign(DoubleMatrix1D v2, DoubleDoubleFunction func) {
for (TIntDoubleIterator iter = ((LogSparseDoubleMatrix1DOld)v2).elementsZ.iterator(); iter.hasNext();) {
iter.advance();
int row = iter.key()-1;
set(row,func.apply(get(row), v2.get(row)));
}
for (TIntDoubleIterator iter = elementsZ.iterator(); iter.hasNext();) {
iter.advance();
int row = iter.key()-1;
if (v2.getQuick(row)==0)
set(row,func.apply(get(row), v2.get(row)));
}
return this;
}
/* (non-Javadoc)
* @see cern.colt.matrix.DoubleMatrix1D#getQuick(int)
*/
public double getQuick(int arg0) {
return elementsZ.get(arg0+1);
}
/* (non-Javadoc)
* @see cern.colt.matrix.DoubleMatrix1D#like(int)
*/
public DoubleMatrix1D like(int arg0) {
// TODO Auto-generated method stub
return null;
}
/* (non-Javadoc)
* @see cern.colt.matrix.DoubleMatrix1D#like2D(int, int)
*/
public DoubleMatrix2D like2D(int arg0, int arg1) {
// TODO Auto-generated method stub
return null;
}
/* (non-Javadoc)
* @see cern.colt.matrix.DoubleMatrix1D#setQuick(int, double)
*/
public void setQuick(int arg0, double arg1) {
if (arg1 != 0)
elementsZ.put(arg0+1,arg1);
}
/* (non-Javadoc)
* @see cern.colt.matrix.DoubleMatrix1D#viewSelectionLike(int[])
*/
protected DoubleMatrix1D viewSelectionLike(int[] arg0) {
// TODO Auto-generated method stub
return null;
}
};
CRF/src/iitb/CRF/SegmentDataSequence.java 0000644 0001760 0001760 00000000644 10421454647 021005 0 ustar abhisheka abhisheka package iitb.CRF;
/**
* The training/test instance for segment sequence data as needed by NestedCRF.
* @author Sunita Sarawagi
*
*/
public interface SegmentDataSequence extends DataSequence {
/** get the end position of the segment starting at segmentStart */
int getSegmentEnd(int segmentStart);
/** set segment boundary and label */
void setSegment(int segmentStart, int segmentEnd, int y);
};
CRF/src/iitb/CRF/LogSparseDoubleMatrix2D.java 0000644 0001760 0001760 00000001750 10421454647 021524 0 ustar abhisheka abhisheka /*
* Created on May 18, 2005
*
*/
package iitb.CRF;
import cern.colt.matrix.DoubleMatrix1D;
import cern.colt.matrix.DoubleMatrix2D;
import cern.colt.matrix.impl.SparseDoubleMatrix2D;
public class LogSparseDoubleMatrix2D extends SparseDoubleMatrix2D {
static double map(double val) { return LogSparseDoubleMatrix1D.map(val);}
static double reverseMap(double val) { return LogSparseDoubleMatrix1D.reverseMap(val);}
public LogSparseDoubleMatrix2D(int numR, int numC) {super(numR,numC);
}
public DoubleMatrix2D assign(double val) {
return super.assign(map(val));
}
public void set(int row, int column, double val) {
super.set(row,column,map(val));
}
public double get(int row, int column) {
return reverseMap(super.get(row,column));
}
public DoubleMatrix1D zMult(DoubleMatrix1D y, DoubleMatrix1D z, double alpha, double beta, boolean transposeA) {
return RobustMath.logMult(this,y,z,alpha,beta,transposeA);
}
};
CRF/src/iitb/CRF/FeatureGeneratorNested.java 0000644 0001760 0001760 00000000617 10421454647 021525 0 ustar abhisheka abhisheka package iitb.CRF;
/**
*
* @author Sunita Sarawagi
*
*/
public interface FeatureGeneratorNested extends FeatureGenerator {
/** for nestedCRF this controls the maximum number of x-s grouped together.
the maximum number of symbols generated by a state in a single nested step.
**/
int maxMemory();
void startScanFeaturesAt(DataSequence data, int prevPos, int pos);
};
CRF/src/iitb/CRF/SparseTrainer.java 0000644 0001760 0001760 00000043264 10421544046 017700 0 ustar abhisheka abhisheka package iitb.CRF;
import cern.colt.function.DoubleFunction;
import cern.colt.function.IntDoubleFunction;
import cern.colt.function.IntIntDoubleFunction;
import cern.colt.matrix.DoubleMatrix1D;
import cern.colt.matrix.DoubleMatrix2D;
import cern.colt.matrix.impl.SparseDoubleMatrix1D;
import cern.colt.matrix.impl.SparseDoubleMatrix2D;
/**
*
* @author Sunita Sarawagi
*
*/
public class SparseTrainer extends Trainer {
boolean logTrainer;
static class ExpFunc implements DoubleFunction {
public double apply(double a) {return Math.exp(a);}
};
static class ExpFunc2D implements IntIntDoubleFunction {
public double apply(int first, int second, double third) {
return Math.exp(third);
}
};
static class ExpFunc1D implements IntDoubleFunction {
public double apply(int first, double third) {
return Math.exp(third);
}
};
static ExpFunc expFunc = new ExpFunc();
static IntDoubleFunction expFunc1D = new ExpFunc1D();
static IntIntDoubleFunction expFunc2D = new ExpFunc2D();
/**
* @param numY
* @return
*/
protected DoubleMatrix1D newLogDoubleMatrix1D(int numY) {
if ((Boolean.valueOf(params.miscOptions.getProperty("sparse", "false"))).booleanValue())
return new LogSparseDoubleMatrix1D(numY);
return new LogDenseDoubleMatrix1D(numY);
}
protected DoubleMatrix2D newLogDoubleMatrix2D(int numR, int numC) {
if ((Boolean.valueOf(params.miscOptions.getProperty("sparse", "false"))).booleanValue())
return new LogSparseDoubleMatrix2D(numR, numC);
return new LogDenseDoubleMatrix2D(numR, numC);
}
public SparseTrainer(CrfParams p) {
super(p);
params = p;
logTrainer = params.trainerType.equals("ll");
}
public void train(CRF model, DataIter data, double[] l, Evaluator eval) {
init(model,data,l);
evaluator = eval;
if (params.debugLvl > 0) {
Util.printDbg("Number of features :" + lambda.length);
}
doTrain();
}
void initMatrices() {
if (!logTrainer) {
Mi_YY = new SparseDoubleMatrix2D(numY,numY);
Ri_Y = new SparseDoubleMatrix1D(numY);
alpha_Y = new SparseDoubleMatrix1D(numY);
newAlpha_Y = new SparseDoubleMatrix1D(numY);
tmp_Y = new SparseDoubleMatrix1D(numY);
} else {
Mi_YY = newLogDoubleMatrix2D(numY,numY);
Ri_Y = newLogDoubleMatrix1D(numY);
alpha_Y = newLogDoubleMatrix1D(numY);
newAlpha_Y = newLogDoubleMatrix1D(numY);
tmp_Y = newLogDoubleMatrix1D(numY);
}
}
protected double computeFunctionGradient(double lambda[], double grad[]) {
if (params.trainerType.equals("ll"))
return computeFunctionGradientLL(lambda, grad);
double logli = 0;
try {
for (int f = 0; f < lambda.length; f++) {
grad[f] = -1*lambda[f]*params.invSigmaSquare;
logli -= ((lambda[f]*lambda[f])*params.invSigmaSquare)/2;
}
boolean doScaling = params.doScaling;
diter.startScan();
if (featureGenCache != null) featureGenCache.startDataScan();
for (int numRecord = 0; diter.hasNext(); numRecord++) {
DataSequence dataSeq = (DataSequence)diter.next();
if (featureGenCache != null) featureGenCache.nextDataIndex();
if (params.debugLvl > 1) {
Util.printDbg("Read next seq: " + numRecord + " logli " + logli);
}
alpha_Y.assign(1);
for (int f = 0; f < lambda.length; f++)
ExpF[f] = 0;
if ((beta_Y == null) || (beta_Y.length < dataSeq.length())) {
beta_Y = new DoubleMatrix1D[2*dataSeq.length()];
for (int i = 0; i < beta_Y.length; i++)
beta_Y[i] = new SparseDoubleMatrix1D(numY);
scale = new double[2*dataSeq.length()];
}
// compute beta values in a backward scan.
// also scale beta-values to 1 to avoid numerical problems.
scale[dataSeq.length()-1] = (doScaling)?numY:1;
beta_Y[dataSeq.length()-1].assign(1.0/scale[dataSeq.length()-1]);
for (int i = dataSeq.length()-1; i > 0; i--) {
if (params.debugLvl > 2) {
Util.printDbg("Features fired");
//featureGenerator.startScanFeaturesAt(dataSeq, i);
//while (featureGenerator.hasNext()) {
//Feature feature = featureGenerator.next();
//Util.printDbg(feature.toString());
//}
}
// compute the Mi matrix
computeMi(featureGenerator,lambda,dataSeq,i,Mi_YY,Ri_Y);
tmp_Y.assign(beta_Y[i]);
tmp_Y.assign(Ri_Y,multFunc);
// RobustMath.Mult(Mi_YY, tmp_Y, beta_Y[i-1],1,0,false,edgeGen);
Mi_YY.zMult(tmp_Y, beta_Y[i-1]);
// need to scale the beta-s to avoid overflow
scale[i-1] = doScaling?beta_Y[i-1].zSum():1;
if ((scale[i-1] < 1) && (scale[i-1] > -1))
scale[i-1] = 1;
constMultiplier.multiplicator = 1.0/scale[i-1];
beta_Y[i-1].assign(constMultiplier);
}
double thisSeqLogli = 0;
for (int i = 0; i < dataSeq.length(); i++) {
// compute the Mi matrix
computeMi(featureGenerator,lambda,dataSeq,i,Mi_YY,Ri_Y);
// find features that fire at this position..
featureGenerator.startScanFeaturesAt(dataSeq, i);
if (i > 0) {
// tmp_Y.assign(alpha_Y);
// RobustMath.Mult(Mi_YY, tmp_Y, newAlpha_Y,1,0,true,edgeGen);
Mi_YY.zMult(alpha_Y, newAlpha_Y,1,0,true);
newAlpha_Y.assign(Ri_Y,multFunc);
} else {
newAlpha_Y.assign(Ri_Y);
}
while (featureGenerator.hasNext()) {
Feature feature = featureGenerator.next();
int f = feature.index();
int yp = feature.y();
int yprev = feature.yprev();
float val = feature.value();
if ((dataSeq.y(i) == yp) && (((i-1 >= 0) && (yprev == dataSeq.y(i-1))) || (yprev < 0))) {
grad[f] += val;
thisSeqLogli += val*lambda[f];
}
if (yprev < 0) {
ExpF[f] += newAlpha_Y.get(yp)*val*beta_Y[i].get(yp);
} else {
ExpF[f] += alpha_Y.get(yprev)*Ri_Y.get(yp)*Mi_YY.get(yprev,yp)*val*beta_Y[i].get(yp);
}
}
alpha_Y.assign(newAlpha_Y);
// now scale the alpha-s to avoid overflow problems.
constMultiplier.multiplicator = 1.0/scale[i];
alpha_Y.assign(constMultiplier);
if (params.debugLvl > 2) {
System.out.println("Alpha-i " + alpha_Y.toString());
System.out.println("Ri " + Ri_Y.toString());
System.out.println("Mi " + Mi_YY.toString());
System.out.println("Beta-i " + beta_Y[i].toString());
}
//badVector(alpha_Y);
}
double Zx = alpha_Y.zSum();
//if (Zx == 0) {
//Zx = (Double.MIN_VALUE*100000000);
//}
thisSeqLogli -= log(Zx);
// correct for the fact that alpha-s were scaled.
for (int i = 0; i < dataSeq.length(); i++) {
thisSeqLogli -= log(scale[i]);
}
if (thisSeqLogli > 0) {
System.out.println("This is shady: something is wrong Pr(y|x) > 1!");
}
logli += thisSeqLogli;
// update grad.
for (int f = 0; f < grad.length; f++)
grad[f] -= ExpF[f]/Zx;
if (params.debugLvl > 1) {
System.out.println("Sequence " + thisSeqLogli + " " + logli);
}
}
if (params.debugLvl > 2) {
for (int f = 0; f < lambda.length; f++)
System.out.print(lambda[f] + " ");
System.out.println(" :x");
for (int f = 0; f < lambda.length; f++)
System.out.print(grad[f] + " ");
System.out.println(" :g");
}
if (params.debugLvl > 0)
Util.printDbg("Iter " + icall + " log likelihood "+logli + " norm(grad logli) " + norm(grad) + " norm(x) "+ norm(lambda));
} catch (Exception e) {
System.out.println("Alpha-i " + alpha_Y.toString());
System.out.println("Ri " + Ri_Y.toString());
System.out.println("Mi " + Mi_YY.toString());
e.printStackTrace();
System.exit(0);
}
return logli;
}
static void computeLogMi(FeatureGenerator featureGen, double lambda[],
DoubleMatrix2D Mi_YY,
DoubleMatrix1D Ri_Y) {
double DEFAULT_VALUE = 0;
Mi_YY.assign(DEFAULT_VALUE);
Ri_Y.assign(DEFAULT_VALUE);
computeLogMiInitDone(featureGen,lambda,Mi_YY,Ri_Y, DEFAULT_VALUE);
}
static void computeLogMiInitDone(FeatureGenerator featureGen, double lambda[],
DoubleMatrix2D Mi_YY,
DoubleMatrix1D Ri_Y, double DEFAULT_VALUE) {
while (featureGen.hasNext()) {
Feature feature = featureGen.next();
int f = feature.index();
int yp = feature.y();
int yprev = feature.yprev();
float val = feature.value();
if (yprev == -1) {
// this is a single state feature.
// if default value was a negative_infinity, need to
// reset to.
double oldVal = Ri_Y.get(yp);
if (oldVal == DEFAULT_VALUE)
oldVal = 0;
Ri_Y.set(yp,oldVal+lambda[f]*val);
} else if (Mi_YY != null) {
double oldVal = Mi_YY.get(yprev,yp);
if (oldVal == DEFAULT_VALUE) {
oldVal = 0;
if (Ri_Y.get(yp) == DEFAULT_VALUE)
Ri_Y.set(yp,0);
}
Mi_YY.set(yprev,yp,oldVal+lambda[f]*val);
}
}
}
static void computeMi(FeatureGenerator featureGen, double lambda[],
DataSequence dataSeq, int i,
DoubleMatrix2D Mi_YY,
DoubleMatrix1D Ri_Y) {
featureGen.startScanFeaturesAt(dataSeq, i);
computeLogMi(featureGen, lambda, Mi_YY, Ri_Y);
Ri_Y.assign(expFunc);
Mi_YY.assign(expFunc);
// Mi_YY.forEachNonZero(expFunc2D);
}
static void computeLogMi(FeatureGenerator featureGen, double lambda[],
DataSequence dataSeq, int i,
DoubleMatrix2D Mi_YY,
DoubleMatrix1D Ri_Y) {
featureGen.startScanFeaturesAt(dataSeq, i);
computeLogMi(featureGen, lambda, Mi_YY, Ri_Y);
}
protected double computeFunctionGradientLL(double lambda[], double grad[]) {
double logli = 0;
try {
for (int f = 0; f < lambda.length; f++) {
grad[f] = -1*lambda[f]*params.invSigmaSquare;
logli -= ((lambda[f]*lambda[f])*params.invSigmaSquare)/2;
}
diter.startScan();
if (featureGenCache != null) featureGenCache.startDataScan();
for (int numRecord = 0; diter.hasNext(); numRecord++) {
DataSequence dataSeq = (DataSequence)diter.next();
if (featureGenCache != null) featureGenCache.nextDataIndex();
if (params.debugLvl > 1) {
Util.printDbg("Read next seq: " + numRecord + " logli " + logli);
}
alpha_Y.assign(0);
for (int f = 0; f < lambda.length; f++)
ExpF[f] = RobustMath.LOG0;
if ((beta_Y == null) || (beta_Y.length < dataSeq.length())) {
beta_Y = new DoubleMatrix1D[2*dataSeq.length()];
for (int i = 0; i < beta_Y.length; i++)
beta_Y[i] = newLogDoubleMatrix1D(numY);
}
// compute beta values in a backward scan.
// also scale beta-values to 1 to avoid numerical problems.
beta_Y[dataSeq.length()-1].assign(0);
for (int i = dataSeq.length()-1; i > 0; i--) {
if (params.debugLvl > 3) {
Util.printDbg("Features fired");
featureGenerator.startScanFeaturesAt(dataSeq, i);
while (featureGenerator.hasNext()) {
Feature feature = featureGenerator.next();
Util.printDbg(feature.toString());
}
}
// compute the Mi matrix
computeLogMi(featureGenerator,lambda,dataSeq,i,Mi_YY,Ri_Y);
tmp_Y.assign(beta_Y[i]);
tmp_Y.assign(Ri_Y,sumFunc);
Mi_YY.zMult(tmp_Y, beta_Y[i-1],1,0,false);
}
double thisSeqLogli = 0;
for (int i = 0; i < dataSeq.length(); i++) {
// compute the Mi matrix
computeLogMi(featureGenerator,lambda,dataSeq,i,Mi_YY,Ri_Y);
// find features that fire at this position..
featureGenerator.startScanFeaturesAt(dataSeq, i);
if (i > 0) {
//tmp_Y.assign(alpha_Y);
Mi_YY.zMult(alpha_Y, newAlpha_Y,1,0,true);
newAlpha_Y.assign(Ri_Y,sumFunc);
} else {
newAlpha_Y.assign(Ri_Y);
}
while (featureGenerator.hasNext()) {
Feature feature = featureGenerator.next();
int f = feature.index();
int yp = feature.y();
int yprev = feature.yprev();
float val = feature.value();
if ((dataSeq.y(i) == yp) && (((i-1 >= 0) && (yprev == dataSeq.y(i-1))) || (yprev < 0))) {
grad[f] += val;
thisSeqLogli += val*lambda[f];
}
if (yprev < 0) {
ExpF[f] = RobustMath.logSumExp(ExpF[f], newAlpha_Y.get(yp) + RobustMath.log(val) + beta_Y[i].get(yp));
} else {
ExpF[f] = RobustMath.logSumExp(ExpF[f], alpha_Y.get(yprev)+Ri_Y.get(yp)+Mi_YY.get(yprev,yp)+RobustMath.log(val)+beta_Y[i].get(yp));
}
}
alpha_Y.assign(newAlpha_Y);
if (params.debugLvl > 2) {
System.out.println("Alpha-i " + alpha_Y.toString());
System.out.println("Ri " + Ri_Y.toString());
System.out.println("Mi " + Mi_YY.toString());
System.out.println("Beta-i " + beta_Y[i].toString());
}
}
double lZx = alpha_Y.zSum();
thisSeqLogli -= lZx;
logli += thisSeqLogli;
// update grad.
for (int f = 0; f < grad.length; f++)
grad[f] -= RobustMath.exp(ExpF[f]-lZx);
if (params.debugLvl > 1) {
System.out.println("Sequence " + thisSeqLogli + " " + logli );
}
if (thisSeqLogli > 0) {
System.out.println("This is shady: something is wrong Pr(y|x) > 1!");
}
}
if (params.debugLvl > 2) {
for (int f = 0; f < lambda.length; f++)
System.out.print(lambda[f] + " ");
System.out.println(" :x");
for (int f = 0; f < lambda.length; f++)
System.out.print(grad[f] + " ");
System.out.println(" :g");
}
if (params.debugLvl > 0)
Util.printDbg("Iteration " + icall + " log-likelihood "+logli + " norm(grad logli) " + norm(grad) + " norm(x) "+ norm(lambda));
} catch (Exception e) {
System.out.println("Alpha-i " + alpha_Y.toString());
System.out.println("Ri " + Ri_Y.toString());
System.out.println("Mi " + Mi_YY.toString());
e.printStackTrace();
System.exit(0);
}
return logli;
}
}
CRF/src/iitb/CRF/DataSequence.java 0000644 0001760 0001760 00000000634 10421454647 017461 0 ustar abhisheka abhisheka package iitb.CRF;
/**
* A basic training/test instance needs to support the DataSequence interface.
* @author Sunita Sarawagi
*
*/
public interface DataSequence {
public int length();
public int y(int i);
/** The type of x is never interpreted by the CRF package. This could be useful for your FeatureGenerator class */
public Object x(int i);
public void set_y(int i, int label);
};
CRF/src/iitb/CRF/DataIter.java 0000644 0001760 0001760 00000000437 10421454647 016615 0 ustar abhisheka abhisheka package iitb.CRF;
/**
* The basic interface to be implemented by the user of this package for
* providing training and test data to the learner.
*
* @author Sunita Sarawagi
*
*/
public interface DataIter {
void startScan();
boolean hasNext();
DataSequence next();
};
CRF/src/iitb/MaxentClassifier/ 0000775 0001760 0001760 00000000000 10421454647 017102 5 ustar abhisheka abhisheka CRF/src/iitb/MaxentClassifier/package.html 0000644 0001760 0001760 00000000152 10421454647 021357 0 ustar abhisheka abhisheka
There is a class called FeatureTypes which you inherit from for creating any kind of feature. You will see various derived classes from them, EdgeFeatures, StartFeatures, etc, etc. In FeatureTypes the num() and setOffset() methods are irrelevant after the FeatureMaps class. Also the ".id" field of FeatureImpl does not need to be set by the FEatureTypes.next() methods.
The FeatureGenerator is an aggregator over all these different feature types. It is responsible for converting the string-ids that the FeatureTypes assign to their features into distinct numbers. It has a inner class called FeatureMap that will make one pass over the training data and create the map of featurenames->integer id and as a side effect count the number of features. You can then just inherit from the FeatureGenImpl class and after calling one of the constructors that does not make a call to (addFeatures()) you can then implement your own addFeatures class. There you will typically add the EdgeFeatures feature first and then the rest. So, for example if you wanted to add some parameter for each label (like a prior), you can create a new FeatureTypes class that will create as many featureids as the number of labels. You will have to create a new class that is derived from FeatureGenImpl and just have a different implementation of the addFeatures subroutine. The rest will be handled by the parent class.
Another important class is the dictionary class that is WordsInTrain
class. This is created by FeatureGenTypes and is available for any
featureTypes class to use. What it does is provide you counts of the
number of times a word occurs in a state. A third class is the
various graph class. This allows you to create CRFs where you can have
more than one state per label.
CRF/src/iitb/Model/WindowFeatures.java 0000644 0001760 0001760 00000010436 10421544054 020504 0 ustar abhisheka abhisheka /*
* Created on Dec 6, 2004
*
*/
package iitb.Model;
import iitb.CRF.DataSequence;
import java.io.Serializable;
/**
* @author Administrator
*
* Define features for windows of ranges
*/
public class WindowFeatures extends FeatureTypes {
private static final long serialVersionUID = 6123;
protected FeatureTypes single;
protected int currentWindow;
int prevPos;
protected int pos;
protected transient DataSequence dataSeq;
public static class Window implements Serializable {
public int start;
public boolean startRelativeToLeft;
public int end;
public boolean endRelativeToLeft;
String winName=null;
public int maxLength=Integer.MAX_VALUE;
public int minLength=1;
public Window(int start, boolean startRelativeToLeft, int end,
boolean endRelativeToLeft) {
this(start,startRelativeToLeft,end,endRelativeToLeft,null);
String startB = startRelativeToLeft?"L":"R";
String endB = endRelativeToLeft?"L":"R";
winName = startB + start + endB + end;
}
public Window(int start, boolean startRelativeToLeft, int end,
boolean endRelativeToLeft, String winName) {
this.start = start;
this.startRelativeToLeft = startRelativeToLeft;
this.end = end;
this.endRelativeToLeft = endRelativeToLeft;
this.winName = winName;
}
public Window(int start, boolean startRelativeToLeft, int end,
boolean endRelativeToLeft, String winName, int minWinLength, int maxWinLength) {
this(start,startRelativeToLeft,end,endRelativeToLeft,winName);
this.maxLength = maxWinLength;
this.minLength = minWinLength;
}
int leftBoundary(int segStart, int segEnd) {
if (startRelativeToLeft)
return boundary(segStart,start);
return boundary(segEnd,start);
}
int rightBoundary(int segStart, int segEnd) {
if (endRelativeToLeft)
return boundary(segStart,end);
return boundary(segEnd,end);
}
/**
* @param segStart
* @param start2
* @return
*/
private int boundary(int boundary, int offset) {
return boundary+offset;
}
public String toString() {
return winName;
}
}
protected Window windows[];
private int dataLen;
/**
*
*/
public WindowFeatures(Window windows[], FeatureTypes single) {
super(single);
this.single = single;
this.windows = windows;
}
protected boolean advance(boolean firstCall) {
while (firstCall || !single.hasNext()) {
currentWindow--;
if (currentWindow < 0)
return false;
if ((windows[currentWindow].maxLength < pos-prevPos) || (windows[currentWindow].minLength > pos-prevPos))
continue;
int rightB = windows[currentWindow].rightBoundary(prevPos+1,pos);
int leftB = windows[currentWindow].leftBoundary(prevPos+1,pos);
if ((leftB < dataLen) && (rightB >= 0) && (leftB <= rightB)) {
single.startScanFeaturesAt(dataSeq,Math.max(leftB,0)-1, Math.min(rightB,dataLen-1));
firstCall = false;
}
}
return true;
}
/* (non-Javadoc)
* @see iitb.Model.FeatureTypes#startScanFeaturesAt(iitb.CRF.DataSequence, int, int)
*/
public boolean startScanFeaturesAt(DataSequence data, int prevPos, int pos) {
currentWindow = windows.length;
dataSeq = data;
dataLen = dataSeq.length();
this.prevPos = prevPos;
this.pos = pos;
return advance(true);
}
/* (non-Javadoc)
* @see iitb.Model.FeatureTypes#hasNext()
*/
public boolean hasNext() {
return single.hasNext() && (currentWindow >= 0);
}
/* (non-Javadoc)
* @see iitb.Model.FeatureTypes#next(iitb.Model.FeatureImpl)
*/
public void next(FeatureImpl f) {
single.next(f);
String name = "";
if (featureCollectMode()) {
name += f.strId.name + ".W." + windows[currentWindow];
}
setFeatureIdentifier(f.strId.id*windows.length+currentWindow, f.strId.stateId, name, f);
advance(false);
}
public boolean requiresTraining() {
return single.requiresTraining();
}
public void train(DataSequence data, int pos) {
single.train(data, pos);
}
}
CRF/src/iitb/Model/KnownInOtherState.java 0000644 0001760 0001760 00000002123 10421544045 021116 0 ustar abhisheka abhisheka package iitb.Model;
import iitb.CRF.DataSequence;
/**
*
* @author Sunita Sarawagi
*
*/
public class KnownInOtherState extends FeatureTypes {
int stateId;
WordsInTrain dict;
float wordFreq;
int wordPos;
public KnownInOtherState(FeatureGenImpl m, WordsInTrain d) {
super(m);
dict = d;
}
void nextStateId() {
for (stateId++; (stateId < model.numStates()); stateId++)
if (dict.count(wordPos,stateId) == 0)
return;
}
public boolean startScanFeaturesAt(DataSequence data, int prevPos, int pos) {
if (dict.count(data.x(pos)) <= WordFeatures.RARE_THRESHOLD+1) {
stateId = model.numStates();
return false;
} else {
wordPos = dict.getIndex(data.x(pos));
stateId = -1;
nextStateId();
wordFreq = (float)Math.log((double)dict.count(data.x(pos))/dict.totalCount());
return true;
}
}
public boolean hasNext() {
return (stateId < model.numStates());
}
public void next(FeatureImpl f) {
setFeatureIdentifier(stateId,stateId,"K",f);
f.yend = stateId;
f.ystart = -1;
f.val = wordFreq;
nextStateId();
}
};
CRF/src/iitb/Model/FeatureTypesEachLabel.java 0000644 0001760 0001760 00000003622 10421454647 021706 0 ustar abhisheka abhisheka package iitb.Model;
import iitb.CRF.DataSequence;
/**
* This can be used as a wrapper around a FeatureTypes class that wants to
* generate a feature for each label.
*/
public class FeatureTypesEachLabel extends FeatureTypes {
protected FeatureTypes single;
int numStates;
int stateId;
FeatureImpl featureImpl;
boolean optimize = false;
public FeatureTypesEachLabel(FeatureGenImpl fgen, FeatureTypes single) {
super(fgen);
numStates = model.numStates();
this.single = single;
featureImpl = new FeatureImpl();
thisTypeId = single.thisTypeId;
}
protected void nextFeature() {
single.next(featureImpl);
}
boolean advance() {
stateId++;
if (stateId < numStates)
return true;
if (single.hasNext()) {
nextFeature();
stateId = 0;
}
return stateId < numStates;
}
public boolean startScanFeaturesAt(iitb.CRF.DataSequence data, int prevPos,
int pos) {
stateId = numStates;
single.startScanFeaturesAt(data, prevPos, pos);
return advance();
}
public boolean startScanFeaturesAt(iitb.CRF.DataSequence data,
int pos) {
stateId = numStates;
single.startScanFeaturesAt(data, pos);
return advance();
}
public boolean hasNext() {
return (stateId < numStates);
}
protected FeatureImpl getFeature() {return featureImpl;}
public void next(iitb.Model.FeatureImpl f) {
f.copy(getFeature());
f.yend = stateId;
single.setFeatureIdentifier(featureImpl.strId.id * numStates + stateId,
stateId, featureImpl.strId.name, f);
advance();
}
/* (non-Javadoc)
* @see iitb.Model.FeatureTypes#requiresTraining()
*/
public boolean requiresTraining() {
return single.requiresTraining();
}
/* (non-Javadoc)
* @see iitb.Model.FeatureTypes#train(iitb.CRF.DataSequence, int)
*/
public void train(DataSequence data, int pos) {
single.train(data, pos);
}
public boolean fixedTransitionFeatures() {
return single.fixedTransitionFeatures();
}
};
CRF/src/iitb/Model/FeatureImpl.java 0000644 0001760 0001760 00000002350 10421544054 017747 0 ustar abhisheka abhisheka package iitb.Model;
import iitb.CRF.Feature;
import java.io.Serializable;
/**
*
* @author Sunita Sarawagi
*
*/
public class FeatureImpl implements Feature, Serializable {
public String type;
public FeatureIdentifier strId = new FeatureIdentifier();
public int id;
public int ystart, yend;
public float val = 1;
public int historyArray[] = null;
public void init() {
val = 1;
historyArray = null;
ystart = -1;
id = 0;
}
public FeatureImpl() {init();}
public FeatureImpl(FeatureImpl f) {copy(f);}
public void copy(Feature featureToReturn) {
id = featureToReturn.index();
ystart = featureToReturn.yprev();
yend = featureToReturn.y();
val = featureToReturn.value();
historyArray = featureToReturn.yprevArray();
}
public void copy(FeatureImpl featureToReturn) {
copy((Feature)featureToReturn);
strId.copy(featureToReturn.strId);
type = featureToReturn.type;
}
public int index() {return id;}
public int y() {return yend;}
public int yprev() {return ystart;}
public float value() {return val;}
public String toString() {return strId + " " + val;}
public FeatureIdentifier identifier() {return strId;}
public int[] yprevArray() {return historyArray;}
};
CRF/src/iitb/Model/WordScoreFeatures.java 0000644 0001760 0001760 00000002320 10421544044 021134 0 ustar abhisheka abhisheka package iitb.Model;
import iitb.CRF.DataSequence;
/**
* These return one feature per state. The value of the feature is the
* fraction of training instances passing through this state that contain
* the word
*
* @author Sunita Sarawagi
*/
public class WordScoreFeatures extends FeatureTypes {
int stateId;
int wordPos;
WordsInTrain dict;
public WordScoreFeatures(FeatureGenImpl m, WordsInTrain d) {
super(m);
dict = d;
}
private void nextStateId() {
stateId = dict.nextStateWithWord(wordPos, stateId);
}
public boolean startScanFeaturesAt(DataSequence data, int prevPos, int pos) {
stateId = -1;
if (dict.count(data.x(pos)) > WordFeatures.RARE_THRESHOLD) {
Object token = (data.x(pos));
wordPos = dict.getIndex(token);
stateId = -1;
nextStateId();
return true;
}
return false;
}
public boolean hasNext() {
return (stateId < model.numStates()) && (stateId >= 0);
}
public void next(FeatureImpl f) {
setFeatureIdentifier(stateId,stateId,"S",f);
f.yend = stateId;
f.ystart = -1;
f.val = (float)Math.log(((double)dict.count(wordPos,stateId))/dict.count(stateId));
// System.out.println(f.toString());
nextStateId();
}
};
CRF/src/iitb/Model/CompleteModel.java 0000644 0001760 0001760 00000003404 10421544046 020265 0 ustar abhisheka abhisheka package iitb.Model;
import iitb.CRF.DataSequence;
/**
*
* @author Sunita Sarawagi
*
*/
public class CompleteModel extends Model {
public CompleteModel(int nlabels) {
super(nlabels);
name = "Complete";
}
public int numStates() {return numLabels;}
public int label(int stateNum) {return stateNum;}
public int numEdges() {return numLabels*numLabels;}
public int numStartStates() {return numLabels;}
public int numEndStates() {return numLabels;}
public int startState(int i) {
if (i < numStartStates())
return i;
return -1;
}
public int endState(int i) {
if (i < numEndStates())
return i;
return -1;
}
public void stateMappings(DataSequence data) throws Exception {;}
public void stateMappings(DataSequence data, int len, int start) throws Exception{;}
public boolean isEndState(int i) {return true;}
public boolean isStartState(int i) {return true;}
public class SingleEdgeIterator implements EdgeIterator {
CompleteModel model;
Edge edge;
Edge edgeToReturn;
SingleEdgeIterator(CompleteModel m) {
model = m;
edge = new Edge();
edgeToReturn = new Edge();
start();
};
public void start() {
edge.start = 0;
edge.end = 0;
}
public boolean hasNext() {
return (edge.start < model.numStates());
}
public Edge next() {
edgeToReturn.start = edge.start;
edgeToReturn.end = edge.end;
edge.end++;
if (edge.end == model.numStates()) {
edge.end= 0;
edge.start++;
}
return edgeToReturn;
}
public boolean nextIsOuter() {
return true;
}
};
public EdgeIterator edgeIterator() {
return new SingleEdgeIterator(this);
}
/* (non-Javadoc)
* @see iitb.Model.Model#innerEdgeIterator()
*/
public EdgeIterator innerEdgeIterator() {
return null;
}
};
CRF/src/iitb/Model/TokenGenerator.java 0000644 0001760 0001760 00000000405 10421454647 020470 0 ustar abhisheka abhisheka package iitb.Model;
public class TokenGenerator {
boolean firstCall;
Object x;
public void startScan(Object xArg) {x=xArg; firstCall=true;}
public boolean hasNext() {return firstCall;}
public Object next() {firstCall = false; return x;}
};
CRF/src/iitb/Model/EdgeFeatures.java 0000644 0001760 0001760 00000003245 10421544045 020101 0 ustar abhisheka abhisheka package iitb.Model;
import iitb.CRF.DataSequence;
/**
*
* @author Sunita Sarawagi
*
*/
public class EdgeFeatures extends FeatureTypes {
transient protected EdgeIterator edgeIter = null;
protected int edgeNum;
transient boolean edgeIsOuter;
Object labelNames[];
public EdgeFeatures(FeatureGenImpl m, Object labels[]) {
super(m);
labelNames=labels;
}
public EdgeFeatures(FeatureGenImpl m) {
this(m,null);
}
protected void setEdgeIter() {
edgeIter = model.edgeIterator();
}
public boolean startScanFeaturesAt(DataSequence data, int prevPos, int pos) {
if (prevPos < 0) {
edgeNum = model.numEdges();
return false;
} else {
edgeNum = 0;
if (edgeIter == null) {
setEdgeIter();
}
if (edgeIter != null)
edgeIter.start();
return hasNext();
}
}
public boolean hasNext() {
return (edgeIter != null) && (edgeNum < model.numEdges());
}
public boolean lastEdgeWasOuter() {return edgeIsOuter;}
public void next(FeatureImpl f) {
edgeIsOuter = edgeIter.nextIsOuter();
Edge e = edgeIter.next();
Object name="";
if (featureCollectMode()) {
if (labelNames == null) {
name = "E."+model.label(e.start);
} else {
name = labelNames[model.label(e.start)];
}
}
if (edgeIsOuter) {
setFeatureIdentifier(model.label(e.start)*model.numberOfLabels()+model.label(e.end) + model.numEdges(), model.label(e.end),name,f);
} else {
setFeatureIdentifier(edgeNum,e.end,name,f);
}
f.ystart = e.start;
f.yend = e.end;
f.val = 1;
edgeNum++;
}
public boolean fixedTransitionFeatures() {
return ((model.numStartStates()==model.numStates())&&
(model.numEndStates()==model.numEndStates()));
}
};
CRF/src/iitb/Model/todo 0000644 0001760 0001760 00000000131 10421454647 015562 0 ustar abhisheka abhisheka WordScoreFeatures: do not need to return the 0 value for non-occuring
state-token pairs.
CRF/src/iitb/Model/EdgeLinearHistFeatures.java 0000644 0001760 0001760 00000003173 10421544053 022063 0 ustar abhisheka abhisheka package iitb.Model;
import iitb.CRF.DataSequence;
/**
*
* @author Sunita Sarawagi
*
* Suppose if history size is H and number of edges in the model graph
* is E, this will generate HE features (for each history position
* generate features for each possible edge)
*/
public class EdgeLinearHistFeatures extends FeatureTypes {
Object fnames[][];
int histsize;
boolean allDone;
int histArr[];
int histPos;
EdgeIterator edgeIter;
Edge edge;
int edgeNum;
public EdgeLinearHistFeatures(FeatureGenImpl m, Object labels[][], int histsize) {
super(m);
fnames=labels;
edgeIter = model.edgeIterator();
this.histsize = histsize;
histArr = new int[histsize];
}
public boolean startScanFeaturesAt(DataSequence data, int prevPos, int pos) {
allDone = false;
edgeIter.start();
if ((pos < 2) || !edgeIter.hasNext())
allDone = true;
histPos = 1;
edge = edgeIter.next();
edgeNum=0;
return allDone;
}
public boolean hasNext() {
return (histsize > 1) && !allDone;
}
public void next(FeatureImpl f) {
// zero all other pos..
for (int i = 0; i < histArr.length; histArr[i++] = -1);
histArr[histPos] = edge.start;
f.yend = edge.end;
f.historyArray = histArr;
f.val = 1;
Object fname;
if (fnames == null) {
fname = "H."+histPos;
} else {
fname = fnames[histPos][f.yend];
}
histPos++;
if (histPos+1 > histsize) {
histPos = 1; // the first set is handled by edge features.
if (edgeIter.hasNext()) {
edge = edgeIter.next();
edgeNum++;
} else {
allDone = true;
}
}
setFeatureIdentifier(edgeNum*histPos, model.label(f.yend),fname,f);
}
};
CRF/src/iitb/Model/EdgeHistFeatures.java 0000644 0001760 0001760 00000002675 10421544046 020740 0 ustar abhisheka abhisheka package iitb.Model;
import iitb.CRF.DataSequence;
import iitb.Utils.Counters;
/**
*
* @author Sunita Sarawagi
*
* Suppose if history size is H and number of labels in the model
* graph is m, this will generate m^(H+1) features
*/
public class EdgeHistFeatures extends FeatureTypes {
String fname;
String labelNames[];
int histsize;
Counters ctr;
boolean allDone;
int histArr[];
public EdgeHistFeatures(FeatureGenImpl m,String name, String labels[], int histsize) {
super(m);
fname=name;
labelNames=labels;
ctr = new Counters(histsize+1, m.numStates());
this.histsize = histsize;
histArr = new int[histsize];
}
public boolean startScanFeaturesAt(DataSequence data, int prevPos, int pos) {
ctr.clear();
allDone = false;
if (pos < histsize)
allDone = true;
return allDone;
}
public boolean hasNext() {
return (histsize > 1) && !allDone;
}
public void next(FeatureImpl f) {
f.ystart = ctr.value(1,1);
f.yend = ctr.value(0,0);
ctr.arrayCopy(histsize-1,1,histArr);
f.historyArray = histArr;
f.val = 1;
allDone = !ctr.advance();
String name="";
for (int i = 0; i < histArr.length; i++) {
if (histArr[i] != -1) {
if (labelNames == null) {
name += ctr.value(histsize-1,1);
} else {
int index = i + 1;
name += fname+"."+index+"."+labelNames[model.label(f.ystart)];
}
}
}
setFeatureIdentifier(ctr.value(histsize-1,0), model.label(f.yend),name,f);
}
};
CRF/src/iitb/Model/UnknownFeature.java 0000644 0001760 0001760 00000001664 10421544046 020515 0 ustar abhisheka abhisheka package iitb.Model;
import iitb.CRF.DataSequence;
/**
*
* @author Sunita Sarawagi
*
*/
public class UnknownFeature extends FeatureTypes {
private static final long serialVersionUID = 6122L;
int stateId;
WordsInTrain dict;
public UnknownFeature(FeatureGenImpl m, WordsInTrain d) {
super(m);
dict = d;
}
public boolean startScanFeaturesAt(DataSequence data, int prevPos, int pos) {
if (dict.count(data.x(pos)) > WordFeatures.RARE_THRESHOLD+1) {
stateId = model.numStates();
return false;
} else {
stateId = 0;
return true;
}
}
public boolean hasNext() {
return (stateId < model.numStates());
}
public void next(FeatureImpl f) {
setFeatureIdentifier(stateId,stateId,"U",f);
f.yend = stateId;
f.ystart = -1;
f.val = 1;
stateId++;
}
/* (non-Javadoc)
* @see iitb.Model.FeatureTypes#maxFeatureId()
*/
public int maxFeatureId() {
return model.numStates();
}
};
CRF/src/iitb/Model/WordsInTrain.java 0000644 0001760 0001760 00000011337 10421544054 020122 0 ustar abhisheka abhisheka package iitb.Model;
import iitb.CRF.DataIter;
import iitb.CRF.DataSequence;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.io.Serializable;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.StringTokenizer;
/**
*
* This is created by FeatureGenTypes and is available for any
* featureTypes class to use. What it does is provide you counts of
* the number of times a word occurs in a state.
*
* @author Sunita Sarawagi
* */
public class WordsInTrain implements Serializable {
class HEntry implements Serializable {
int index;
int cnt;
int stateArray[];
HEntry(int v) {
index = v;
cnt = 0;
}
HEntry(int v, int numStates) {
index = v;
cnt = 0;
stateArray = new int[numStates];
}
};
private Hashtable dictionary;
private int cntsArray[][];
private int cntsOverAllWords[];
private int allTotal;
transient TokenGenerator tokenGenerator;
public WordsInTrain() {
this(new TokenGenerator());
}
public WordsInTrain(TokenGenerator tokenGen) {
tokenGenerator = tokenGen;
dictionary = new Hashtable();
}
int[] getStateArray(int pos) {
return cntsArray[pos];
}
public int getIndex(Object w) {
return ((HEntry)(dictionary.get(w))).index;
}
boolean inDictionary(Object w) {
return (dictionary.get(w) != null);
}
public int count(Object w) {
HEntry entry = (HEntry)dictionary.get(w);
return ((entry != null)?entry.cnt:0);
}
public int count(int wordPos, int state) {
return getStateArray(wordPos)[state];
}
public int count(int state) {
return cntsOverAllWords[state];
}
public int totalCount() {return allTotal;}
public int dictionaryLength() {return dictionary.size();}
public int nextStateWithWord(Object w, int prev) {
if (!inDictionary(w))
return -1;
int pos = getIndex(w);
return nextStateWithWord(pos,prev);
}
public int nextStateWithWord(int pos, int prev) {
int k = 0;
if (prev >= 0)
k = prev + 1;
for (; k < getStateArray(pos).length; k++) {
if (getStateArray(pos)[k] > 0)
return k;
}
return -1;
}
public Enumeration allWords() {return dictionary.keys();}
private void addDictElem(Object x, int y) {
HEntry index = (HEntry)dictionary.get(x);
if (index == null) {
index = new HEntry(dictionary.size());
dictionary.put(x, index);
}
index.cnt++;
}
private void addDictElem(Object x, int y, int nelems) {
HEntry index = (HEntry)dictionary.get(x);
if (index == null) {
index = new HEntry(dictionary.size(),nelems);
dictionary.put(x, index);
}
index.cnt++;
index.stateArray[y]++;
}
void setAggregateCnts(int numStates) {
cntsOverAllWords = new int[numStates];
for (int i = 0; i < numStates; i++) {
cntsOverAllWords[i] = 0;
for (int m = 0; m < cntsArray.length; m++)
cntsOverAllWords[i] += getStateArray(m)[i];
allTotal += cntsOverAllWords[i];
}
}
public void train(DataIter trainData, int numStates) {
for (trainData.startScan(); trainData.hasNext();) {
DataSequence seq = trainData.next();
for (int l = 0; l < seq.length(); l++) {
for (tokenGenerator.startScan(seq.x(l)); tokenGenerator.hasNext();) {
addDictElem(tokenGenerator.next(),seq.y(l),numStates);
}
}
}
cntsArray = new int[dictionary.size()][0];
for (Enumeration e = dictionary.keys() ; e.hasMoreElements() ;) {
Object key = e.nextElement();
HEntry entry = (HEntry)dictionary.get(key);
cntsArray[entry.index] = entry.stateArray;
}
setAggregateCnts(numStates);
}
public void read(BufferedReader in, int numStates) throws IOException {
int dictLen = Integer.parseInt(in.readLine());
cntsArray = new int[dictLen][numStates];
String line;
for(int l = 0; (l < dictLen) && ((line=in.readLine())!=null); l++) {
StringTokenizer entry = new StringTokenizer(line," ");
String key = entry.nextToken();
int pos = Integer.parseInt(entry.nextToken());
HEntry hEntry = new HEntry(pos);
dictionary.put(key,hEntry);
while (entry.hasMoreTokens()) {
StringTokenizer scp = new StringTokenizer(entry.nextToken(),":");
int state = Integer.parseInt(scp.nextToken());
int cnt = Integer.parseInt(scp.nextToken());
getStateArray(pos)[state] = cnt;
hEntry.cnt += cnt;
}
}
setAggregateCnts(numStates);
}
public void write(PrintWriter out) throws IOException {
out.println(dictionary.size());
for (Enumeration e = dictionary.keys() ; e.hasMoreElements() ;) {
Object key = e.nextElement();
int pos = getIndex(key);
out.print(key + " " + pos);
for (int s = nextStateWithWord(pos,-1); s != -1;
s = nextStateWithWord(pos,s)) {
out.print(" " + s + ":" + getStateArray(pos)[s]);
}
out.println("");
}
}
};
CRF/src/iitb/Model/EndFeatures.java 0000644 0001760 0001760 00000001563 10421544054 017744 0 ustar abhisheka abhisheka package iitb.Model;
import iitb.CRF.DataSequence;
/**
*
* @author Sunita Sarawagi
*
*/
public class EndFeatures extends FeatureTypes {
int stateId;
int endStateNum;
Object fname;
public EndFeatures(FeatureGenImpl m) {
super(m);
fname="End.";
}
public EndFeatures(FeatureGenImpl m, Object fname) {
super(m);
this.fname = fname;
}
public boolean startScanFeaturesAt(DataSequence data, int prevPos, int pos) {
if (pos < data.length()-1) {
stateId = -1;
return false;
} else {
endStateNum = 0;
stateId = model.endState(endStateNum);
return true;
}
}
public boolean hasNext() {
return (stateId >= 0);
}
public void next(FeatureImpl f) {
setFeatureIdentifier(stateId,stateId,fname,f);
f.yend = stateId;
f.ystart = -1;
f.val = 1;
endStateNum++;
stateId = model.endState(endStateNum);
}
};
CRF/src/iitb/Model/FeatureTypesConcat.java 0000644 0001760 0001760 00000004374 10421544046 021313 0 ustar abhisheka abhisheka /*
* Created on Dec 6, 2004
*
*/
package iitb.Model;
import iitb.CRF.DataSequence;
import iitb.Utils.Utils;
/**
* @author Administrator
*
*/
public class FeatureTypesConcat extends FeatureTypes {
FeatureTypes single;
int numBits = 0;
FeatureImpl feature = new FeatureImpl();
private static final long serialVersionUID = 612L;
private int maxConcatLength;
/**
* @param m
*/
public FeatureTypesConcat(FeatureGenImpl fgen, FeatureTypes single, int maxMemory) {
super(fgen);
this.single = single;
// TODO: set this properly for different classes.
int maxId = single.maxFeatureId()+1; // for the feature not firing.
numBits = Utils.log2Ceil(maxId);
thisTypeId = single.thisTypeId;
maxConcatLength = maxMemory;
}
/* (non-Javadoc)
* @see iitb.Model.FeatureTypes#startScanFeaturesAt(iitb.CRF.DataSequence, int, int)
*/
public boolean startScanFeaturesAt(DataSequence data, int prevPos, int pos) {
int bitMap = 0;
String name = "";
feature.strId.id=0;
if (pos-prevPos > maxConcatLength)
return false;
for (int i = 0; (i < pos-prevPos) && (i < maxConcatLength); i++) {
if (single.startScanFeaturesAt(data,pos-i-1,pos-i) && single.hasNext()) {
single.next(feature);
// this could be wrong since label information is not present in single.
int thisId = offsetLabelIndependentId(feature)+1;
bitMap = bitMap | (thisId << i*numBits);
if (featureCollectMode()) {
name = feature.strId.name + "." + name;
if (thisId > (1 << numBits)) {
System.out.println("Error in max-feature-id value " + feature);
}
if (single.hasNext()) {
// System.out.println("FeatureTypesConcat: Taking only the first feature: others to be ignored");
}
}
}
}
setFeatureIdentifier(bitMap,feature.strId.stateId,name,feature);
return (bitMap != 0);
}
/* (non-Javadoc)
* @see iitb.Model.FeatureTypes#hasNext()
*/
public boolean hasNext() {
return feature.strId.id > 0;
}
/* (non-Javadoc)
* @see iitb.Model.FeatureTypes#next(iitb.Model.FeatureImpl)
*/
public void next(FeatureImpl f) {
f.copy(feature);
feature.strId.id = -1;
}
public boolean requiresTraining() {
return single.requiresTraining();
}
public void train(DataSequence data, int pos) {
single.train(data, pos);
}
}
CRF/src/iitb/Model/NestedModel.java 0000644 0001760 0001760 00000020223 10421544046 017735 0 ustar abhisheka abhisheka package iitb.Model;
import gnu.trove.TIntArrayList;
import iitb.CRF.DataSequence;
import iitb.CRF.SegmentDataSequence;
import java.util.StringTokenizer;
public class NestedModel extends Model {
int _numStates;
int _numEdges;
int nodeOffsets[]; // the number of states in the labels before this.
Model inner[];
Model outer;
int startStates[];
int endStates[];
public NestedModel(int num, String specs) throws Exception {
super(num);
name = "Nested";
nodeOffsets = new int[numLabels];
inner = new Model[numLabels];
StringTokenizer start = new StringTokenizer(specs, ",");
assert start.hasMoreTokens();
outer = Model.getNewBaseModel(numLabels, (String)start.nextToken());
String commonStruct = null;
for(int i=0 ; i
* The feature generated here is whether a sequence of tokens has a particular sequence of given pattern or not.
* For example, if a pattern is to mathc a capital word, then for two token context window, various features
* generated are weither two token (bigram) sequence is having any of the following pattern or not:
* (1) Capital, Capital
* (2) Capital, Non-Capital
* (3) Non-capital, Capital.
*
* You can use any window around the current token (segment) for creating regular expression based features.
* Also, you can define your own patterns, by writing down the regular expression in a file,
* whose format is specified below.
*
* The object of this class should be wrap around {@link FeatureTypesEachLabel} as follows:
*
* new FeatureTypesEachLabel(model, new ConcreteConcatRegexFeatures(model,relSegmentStart, relSegmentEnd, maxMemory, patternFile));
*
*
x0 x1 x2 x3 x4 x5 x6 x7 .... xn -4 -3 -2 -1 0 0 0 1 2 ... **
* In above example, the current segment is from postion 4 to 6 with value of pos = 6 and prevPos = 3 in * startScanFeaturesAt() call of FeatureGenerator. * You can refer to any of the token relative to current position by using the index below the token sequence. * Thus, you can create a pattern concat features for any token sequence in the neighbourhood of the current token, * using relSegmentStart and relSegmentEnd. * For, example to create pattern for two tokens to the left of the current token, following is the parameters * to be passed to the constructor of the class: *
** new FeatureTypesEachLabel(model, new ConcreteConcatRegexFeatures(model,-2, -1, maxMemory, patternFile)); ** * @author Imran Mansuri */ public class ConcatRegexFeatures extends FeatureTypes { /** * Various patterns are defined here. * First dimension of this two dimensional array is feature name and second value is the * regular expression pattern to be matched against a token. You can add your own patterns * in this array. */ String patternString[][] = { {"isWord", "[a-zA-Z][a-zA-Z]+" }, {"singleCapLetterWithDot", "[A-Z]\\." }, {"singleCapLetter", "[A-Z]" }, {"isDigits", "\\d+" }, {"singleDot", "[.]" }, {"singleComma", "[,]" }, {"isSpecialCharacter", "[#;:\\-/<>'\"()&]"}, {"containsSpecialCharacters",".*[#;:\\-/<>'\"()&].*"}, {"isInitCapital", "[A-Z][a-z]+" }, {"isAllCapital", "[A-Z]+" }, {"isAllSmallCase", "[a-z]+" }, {"isAlpha", "[a-zA-Z]+" }, {"isAlphaNumeric", "[a-zA-Z0-9]+" }, {"endsWithDot", "\\p{Alnum}+\\." }, {"endsWithComma", "\\w+[,]" }, {"endsWithPunctuation", "\\w+[;:,.?!]" }, {"singlePunctuation", "\\p{Punct}" }, {"singleAmp", "[&]" }, {"containsDigit", ".*\\d+.*" }, {"singleDigit", "\\s*\\d\\s*" }, {"twoDigits", "\\s*\\d{2}\\s*" }, {"threeDigits", "\\s*\\d{3}\\s*" }, {"fourDigits", "\\s*\\(*\\d{4}\\)*\\s*" }, {"isNumberRange", "\\d+\\s*([-]{1,2}\\s*\\d+)?"}, {"isDashSeparatedWords", "(\\w[-])+\\w"}, {"isDashSeparatedSeq", "((\\p{Alpha}+|\\p{Digit}+)[-])+(\\p{Alpha}+|\\p{Digit}+)"}, {"isURL", "\\p{Alpha}+://(\\w+\\.)\\w+(:(\\d{2}|\\d{4}))?(/\\w+)*(/|(/\\w+\\.\\w+))?" }, {"isEmailId", "\\w+@(\\w+\\.)+\\w+" }, {"containsDashes", ".*--.*"} }; Pattern p[]; transient protected DataSequence data; protected int index, idbase, curId, window; protected int relSegmentStart, relSegmentEnd; protected int maxMemory; protected int left, right; /** * Constructs an object of ConcatRegexFeatures to be used to generate features for the token * sequence as specified. * You can specify the sequence of tokens on which the pattern has to be applied using relSegmentStart * and relSegmentEnd, which denotes segment boundries. * The maxMemory denotes the maximum segment size, for normal CRF the value of maxMemory is 1. * There are certain default patterns defined in the class. You can specify your own pattern in a file, and pass * the name of the file in this constructor. The file should begin with integer value for number of pattern in the * file. This should be follwoed by one pattern definition on each line. The first word is the name of the pattern * and second word is regular expression for the pattern. * * @param fgen a {@link Model} object * @param relSegmentStart index of the reltive position for left boundary * @param relSegmentEnd index of the reltive position for right boundary * @param maxMemory maximum size of a segment * @param patternFile file which contains the pattern definition */ public ConcatRegexFeatures(FeatureGenImpl fgen, int relSegmentStart, int relSegmentEnd, int maxMemory, String patternFile){ super(fgen); assert(relSegmentEnd >= relSegmentStart); this.relSegmentStart = relSegmentStart; this.relSegmentEnd = relSegmentEnd; this.maxMemory = maxMemory; window = getWindowSize(relSegmentStart, relSegmentEnd); idbase = (int) Math.pow(2, window); getPatterns(patternFile); assert(patternString != null); p = new Pattern[patternString.length]; for(int i = 0; i < patternString.length; i++){ //System.out.println("i"+ i +" " + patternString[i][1]); p[i] = Pattern.compile(patternString[i][1]); } } /** * @param relSegmentStart2 * @param relSegmentEnd2 * @return */ private int getWindowSize(int relSegmentStart, int relSegmentEnd) { if((sign(relSegmentEnd) == sign(relSegmentStart)) && relSegmentStart != 0) return relSegmentEnd - relSegmentStart + 1; else return relSegmentEnd - relSegmentStart + maxMemory; } /** * Constructs an object of ConcatRegexFeatures to be used to generate features for current token. * @param m a {@link Model} object * @param relSegmentStart index of the reltive position for left boundary * @param relSegmentEnd index of the reltive position for right boundary * @param maxMemory maximum size of a segment */ public ConcatRegexFeatures(FeatureGenImpl m, int relSegmentStart, int relSegmentEnd, int maxMemory){ super(m); assert(relSegmentEnd >= relSegmentStart); this.relSegmentStart = relSegmentStart; this.relSegmentEnd = relSegmentEnd; this.maxMemory = maxMemory; window = getWindowSize(relSegmentStart, relSegmentEnd); idbase = (int) Math.pow(2, window); assert(patternString != null); p = new Pattern[patternString.length]; for(int i = 0; i < patternString.length; i++){ //System.out.println("i"+ i +" " + patternString[i][1]); p[i] = Pattern.compile(patternString[i][1]); } } /** * Constructs an object of ConcatRegexFeatures to be used to generate features for current token. * @param m a {@link Model} object * @param relSegmentStart index of the reltive position for left boundary * @param relSegmentEnd index of the reltive position for right boundary */ public ConcatRegexFeatures(FeatureGenImpl m, int relSegmentStart, int relSegmentEnd){ this(m, relSegmentStart, relSegmentEnd, 1); } /** * Constructs an object of ConcatRegexFeatures to be used to generate features for current token. * @param m a {@link Model} object * @param relSegmentStart index of the reltive position for left boundary * @param relSegmentEnd index of the reltive position for right boundary * @param patternFile file which contains the pattern definition */ public ConcatRegexFeatures(FeatureGenImpl m, int relSegmentStart, int relSegmentEnd, String patternFile){ this(m, relSegmentStart, relSegmentEnd, 1, patternFile); } private int sign(int boundary){ if(boundary == 0) return 0; else if(boundary < 0) return -1; else return 1; } /** * Reads patterns to be matched from the file. * The format of the file is as follows: * The first line of the file is number of patterns, followed by a list of patterns one per line. * Each line describes a pattern's name and pattern string itself. * * @param patternFile name of the pattern file */ void getPatterns(String patternFile){ String line; String patterns[][]; try { BufferedReader in = new BufferedReader(new FileReader(patternFile)); int len = Integer.parseInt(in.readLine()); patterns = new String[len][2]; for(int k = 0; k < len; k++){ StringTokenizer strTokenizer = new StringTokenizer(in.readLine()); patterns[k][0] = strTokenizer.nextToken(); patterns[k][1] = strTokenizer.nextToken(); //System.out.println(patterns[k][0] + " " + patterns[k][1]); } }catch(IOException ioe){ System.err.println("Could not read pattern file : " + patternFile); ioe.printStackTrace(); return; } patternString = patterns; return; } /** * Initaites scanning of features in a sequence at specified position. * * @param data a training sequence * @param prevPos the previous label postion * @param pos Current token postion */ public boolean startScanFeaturesAt(DataSequence data, int prevPos, int pos){ assert(patternString != null); this.data = data; index = 0; if (relSegmentStart <= 0) { left = prevPos + 1 + relSegmentStart; } else { left = pos + relSegmentStart; } if (relSegmentEnd < 0) { right = prevPos + 1 + relSegmentEnd; } else { right = pos + relSegmentEnd; } if(!(left >= 0 && left < data.length() && right >= 0 && right < data.length())) index = patternString.length; //System.out.println("DataLength:" + data.length() + " segment(" + (prevPos+1) + "," + pos + ") rs(" +relSegmentStart + "," + relSegmentEnd + ") window(" + left + "," + right + ") idbase:" + idbase); advance(); return true; } /** * Returns true if there are any more feature(s) for the current scan. * */ public boolean hasNext() { return index < patternString.length; } /** * Generates the next feature for the current scan. * * @param f Copies the feature generated to the argument */ public void next(FeatureImpl f) { if(featureCollectMode()){ //This is a feature collection mode, so return id and name f.strId.name = patternString[index][0] + "_" + window + "_" + Integer.toBinaryString(curId); } /*//Return feature on token window int base = 1; f.strId.id = 0; for(int k = left; k <= right; k++){ boolean match = p[index].matcher((String)data.x(k)).matches(); f.strId.id += base * (match? 1:0); base = base * 2; } f.val = (f.strId.id > 0) ? 1:0; //In case of no match return 0 as feature value f.ystart = -1; f.strId.id += idbase * index++;*/ f.val = 1; f.strId.id = curId + idbase * index++; f.ystart = -1; advance(); } private void advance(){ curId = 0; while(curId <= 0 && index < patternString.length){ int base = 1; for(int k = left; k <= right; k++){ boolean match = p[index].matcher((String)data.x(k)).matches(); curId += base * (match? 1:0); base = base * 2; } if(curId > 0) break; index++; } } public int maxFeatureId(){ return idbase * (patternString.length - 1) + (idbase -1); //(maximum base i.e. most significat bits + maximum offset) } int offsetLabelIndependentId(FeatureImpl f) { return f.strId.id; } }; CRF/src/iitb/Model/FeatureTypes.java 0000644 0001760 0001760 00000005200 10421544054 020147 0 ustar abhisheka abhisheka package iitb.Model; import iitb.CRF.DataSequence; import java.io.Serializable; /** * * Inherit from the FeatureTypes class for creating any kind of * feature. You will see various derived classes from them, * EdgeFeatures, StartFeatures, etc, etc. The ".id" field of * FeatureImpl does not need to be set by the FEatureTypes.next() * methods. * * @author Sunita Sarawagi */ public abstract class FeatureTypes implements Serializable { int thisTypeId; private FeatureGenImpl fgen; public Model model; public FeatureTypes(FeatureGenImpl fgen) { model = fgen.model; this.fgen = fgen; thisTypeId = fgen.numFeatureTypes++; } /** * @param s */ public FeatureTypes(FeatureTypes s) { this(s.fgen); thisTypeId = s.thisTypeId; fgen.numFeatureTypes--; } public boolean requiresTraining(){return false;} public void train(DataSequence data, int pos) {;} public boolean startScanFeaturesAt(DataSequence data, int pos) { return startScanFeaturesAt(data,pos-1,pos); } public abstract boolean startScanFeaturesAt(DataSequence data, int prevPos, int pos); public abstract boolean hasNext(); public abstract void next(FeatureImpl f); public void setFeatureIdentifier(int fId, int stateId, String name, FeatureImpl f) { setFeatureIdentifier( fId, stateId, (Object)name, f); } public void setFeatureIdentifier(int fId, int stateId, Object name, FeatureImpl f) { f.strId.init(fId*fgen.numFeatureTypes + thisTypeId,stateId,name); } public void setFeatureIdentifier(int fId, FeatureImpl f) { f.strId.init(fId*fgen.numFeatureTypes + thisTypeId); } int labelIndependentId(FeatureImpl f) { return ((f.strId.id-thisTypeId)-f.strId.stateId*fgen.numFeatureTypes)/model.numStates()+thisTypeId; } int offsetLabelIndependentId(FeatureImpl f) { return (labelIndependentId(f)-thisTypeId)/fgen.numFeatureTypes; } public static int featureTypeId(FeatureImpl f, FeatureGenImpl fgen) { return f.strId.id % fgen.numFeatureTypes; } public void print(FeatureGenImpl.FeatureMap strToInt, double crfWs[]) {;} public int maxFeatureId() {return Integer.MAX_VALUE;} /* private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException { s.defaultReadObject(); offset = Math.max(fgen.numFeatureTypes,thisTypeId+1); } */ public int getTypeId() {return thisTypeId;} public boolean featureCollectMode() {return fgen.featureCollectMode;} // returns false if transition features change with x or position public boolean fixedTransitionFeatures() { return true; } }; CRF/src/iitb/acrfinder/ 0000755 0001760 0001760 00000000000 10421742716 015571 5 ustar abhisheka abhisheka CRF/src/iitb/acrfinder/acrFinder.java 0000644 0001760 0001760 00000021226 10422241611 020321 0 ustar abhisheka abhisheka package iitb.acrfinder; import iitb.CRF.CRF; import iitb.CRF.DataIter; import iitb.CRF.DataSequence; import iitb.CRF.FeatureGenerator; import iitb.CRF.Util; import iitb.Model.FeatureGenImpl; import iitb.Utils.Options; import java.io.File; import java.io.FileInputStream; import java.util.StringTokenizer; import java.util.Vector; public class acrFinder { String inName; String outDir; String baseDir="/home/abhisheka/irmProject"; int nlabels; String delimit=" "; // used to define token boundaries String tagDelimit="|"; // seperator between tokens and tag number String impDelimit=""; // delimiters to be retained for tagging String groupDelimit=null; boolean confuseSet[]=null; boolean validate = false; String mapTagString = null; String smoothType = ""; String modelArgs = ""; String featureArgs = ""; String modelGraphType = "naive"; private static int ACR_LABEL = 1; private static int OTHER_LABEL = 0; private int numLabels; // LabelMap labelMap; private Options options; CRF crfModel; FeatureGenImpl featureGen; public FeatureGenerator featureGenerator() {return featureGen;} public static void main(String argv[]) throws Exception { acrFinder objAcrFinder = new acrFinder(); objAcrFinder.parseConf(argv); if (argv[0].toLowerCase().equals("all")) { objAcrFinder.train(); objAcrFinder.test(); //segment.calc(); } if (argv[0].toLowerCase().equals("train")) { objAcrFinder.train(); } if (argv[0].toLowerCase().equals("test")) { objAcrFinder.doTest(); } // if (argv[0].toLowerCase().equals("calc")) { // segment.calc(); // } // objAcrFinder.train(); // objAcrFinder.test(); } private void doTest() throws Exception { // TODO Auto-generated method stub allocModel(); featureGen.read(baseDir+"/learntModels/"+"features"); crfModel.read(baseDir+"/learntModels/"+"crf"); test(); } private void test() { // TODO Auto-generated method stub DCTestData testData=null; baseDir="/home/abhisheka/irmProject"; testData = readTestData(baseDir+"/testDocs"); doTest(testData); testData.startScan(); int cntOtherOrg=0, cntAcrOrg=0, cntOthPrd=0, cntAcrPrd=0; int cntOthOth=0, cntOthAcr=0, cntAcrAcr=0, cntAcrOth=0; //System.out.println("test data has "+testData.size()); while(testData.hasNext()) { DCTestRecord tmpTestRcd= testData.nextRecord(); //System.out.println("seq has "+tmpTestRcd.length()); for(int cnt=0; cnt
There is a class called FeatureTypes which you inherit from for creating any kind of feature. You will see various derived classes from them, EdgeFeatures, StartFeatures, etc, etc. In FeatureTypes the num() and setOffset() methods are irrelevant after the FeatureMaps class. Also the ".id" field of FeatureImpl does not need to be set by the FEatureTypes.next() methods.
The FeatureGenerator is an aggregator over all these different feature types. It is responsible for converting the string-ids that the FeatureTypes assign to their features into distinct numbers. It has a inner class called FeatureMap that will make one pass over the training data and create the map of featurenames->integer id and as a side effect count the number of features. You can then just inherit from the FeatureGenImpl class and after calling one of the constructors that does not make a call to (addFeatures()) you can then implement your own addFeatures class. There you will typically add the EdgeFeatures feature first and then the rest. So, for example if you wanted to add some parameter for each label (like a prior), you can create a new FeatureTypes class that will create as many featureids as the number of labels. You will have to create a new class that is derived from FeatureGenImpl and just have a different implementation of the addFeatures subroutine. The rest will be handled by the parent class.
Another important class is the dictionary class that is WordsInTrain
class. This is created by FeatureGenTypes and is available for any
featureTypes class to use. What it does is provide you counts of the
number of times a word occurs in a state. A third class is the
various graph class. This allows you to create CRFs where you can have
more than one state per label.
CRF/bin/iitb/Model/README 0000644 0001760 0001760 00000003622 10421454647 015543 0 ustar abhisheka abhisheka In this package you will find a whole bunch of files designed to make
it easy to add features without bothering about counting them and
setting the id right. There is a class called FeatureTypes which you
inherit from for creating any kind of feature. You will see various
derived classes from them, EdgeFeatures, StartFeatures, etc, etc.
In FeatureTypes the num() and setOffset() methods are irrelevant after
the FeatureMaps class. Also the ".id" field of FeatureImpl does not
need to be set by the FEatureTypes.next() methods.
The FeatureGenerator is an aggregator over all these different feature
types. It is responsible for converting the string-ids that the
FeatureTypes assign to their features into distinct numbers. It has a
inner class called FeatureMap that will make one pass over the
training data and create the map of featurenames->integer id and as a
side effect count the number of features. You can then just inherit
from the FeatureGenImpl class and after calling one of the
constructors that does not make a call to (addFeatures()) you can then
implement your own addFeatures class. There you will typically add the
EdgeFeatures feature first and then the rest. So, for example if you
wanted to add some parameter for each label (like a prior), you can
create a new FeatureTypes class that will create as many featureids as
the number of labels. You will have to create a new class that is
derived from FeatureGenImpl and just have a different implementation
of the addFeatures subroutine. The rest will be handled by the parent
class.
Another important class is the dictionary class that is WordsInTrain
class. This is created by FeatureGenTypes and is available for any
featureTypes class to use. What it does is provide you counts of the
number of times a word occurs in a state. A third class is the
various graph class. This allows you to create CRFs where you can have
more than one state per label.
CRF/bin/iitb/Model/WordsInTrain$HEntry.class 0000644 0001760 0001760 00000001410 10422165435 021457 0 ustar abhisheka abhisheka 1 ) iitb/Model/WordsInTrain$HEntry java/lang/Object java/io/Serializable index I cnt
stateArray [I this$0 Liitb/Model/WordsInTrain;
This implementation of CRF is as described in the following two papers.
The code relies on a sparse matrix operations available from the COLT
distribution and an implementation of the Quasi-Newton
optimization algorithm (LBFGS) available under the package name riso.numerical
The basic package is intentionally kept barebones without any code for
data input/output and feature design. Before you can start using the
package you need to provide implementations of the FeatureGenerator
and DataIter classes. The best way to learn how to use this code is
to examples in the package @see iitb.usingCRFs.Segment for Sequence
annotations and @see iitb.usingCRFs.MaxentClassifier for a basic
maximum entropy based classifier.
@author Sunita Sarawagi, IIT Bombay (sunita@iitb.ac.in)
CRF/bin/iitb/CRF/Viterbi.class 0000644 0001760 0001760 00000010055 10422165435 016661 0 ustar abhisheka abhisheka 1 iitb/CRF/Viterbi java/lang/Object java/io/Serializable serialVersionUID J
ConstantValue model Liitb/CRF/CRF; beamsize I winningLabel [[Liitb/CRF/Viterbi$Entry; finalSoln Liitb/CRF/Viterbi$Entry; Mi !Lcern/colt/matrix/DoubleMatrix2D; Ri !Lcern/colt/matrix/DoubleMatrix1D; $assertionsDisabled Z