add draft version of POS induction with HMM and L1 Linf constraints

git-svn-id: https://ws10smt.googlecode.com/svn/trunk@47 ec762483-ff6d-05da-a07a-a48fb63a330f

1 files changed, 348 insertions, 0 deletions

diff --git a/gi/posterior-regularisation/prjava/src/hmm/HMMObjective.java b/gi/posterior-regularisation/prjava/src/hmm/HMMObjective.java
new file mode 100644
index 00000000..551210c0
--- /dev/null
+++ b/gi/posterior-regularisation/prjava/src/hmm/HMMObjective.java
@@ -0,0 +1,348 @@
+package hmm;

+

+import gnu.trove.TIntArrayList;

+import optimization.gradientBasedMethods.ProjectedGradientDescent;

+import optimization.gradientBasedMethods.ProjectedObjective;

+import optimization.gradientBasedMethods.stats.OptimizerStats;

+import optimization.linesearch.ArmijoLineSearchMinimizationAlongProjectionArc;

+import optimization.linesearch.InterpolationPickFirstStep;

+import optimization.linesearch.LineSearchMethod;

+import optimization.projections.SimplexProjection;

+import optimization.stopCriteria.CompositeStopingCriteria;

+import optimization.stopCriteria.ProjectedGradientL2Norm;

+import optimization.stopCriteria.StopingCriteria;

+import optimization.stopCriteria.ValueDifference;

+

+public class HMMObjective extends ProjectedObjective{

+

+	

+	private static final double GRAD_DIFF = 3;

+	public static double INIT_STEP_SIZE=10;

+	public static double VAL_DIFF=2000;

+	

+	private HMM hmm;

+	double[] newPoint  ;

+	

+	//posterior[sent num][tok num][tag]=index into lambda

+	private int posteriorMap[][][];

+	//projection[word][tag].get(occurence)=index into lambda

+	private TIntArrayList projectionMap[][];

+

+	//Size of the simplex

+	public double scale=10;

+	private SimplexProjection projection;

+	

+	private int wordFreq[];

+	private static int MIN_FREQ=3;

+	private int numWordsToProject=0;

+	

+	private int n_param;

+	

+	public  double loglikelihood;

+	

+	public HMMObjective(HMM h){

+		hmm=h;

+		

+		countWords();

+		buildMap();

+

+		gradient=new double [n_param];

+		projection = new SimplexProjection(scale);

+		newPoint  = new double[n_param];

+		setInitialParameters(new double[n_param]);

+		

+	}

+	

+	/**@brief counts word frequency in the corpus

+	 * 

+	 */

+	private void countWords(){

+		wordFreq=new int [hmm.emit[0].length];

+		for(int i=0;i<hmm.data.length;i++){

+			for(int j=0;j<hmm.data[i].length;j++){

+				wordFreq[hmm.data[i][j]]++;

+			}

+		}

+	}

+	

+	/**@brief build posterior and projection indices

+	 * 

+	 */

+	private void buildMap(){

+		//number of sentences hidden states and words

+		int n_states=hmm.trans.length;

+		int n_words=hmm.emit[0].length;

+		int n_sents=hmm.data.length;

+		

+		n_param=0;

+		posteriorMap=new int[n_sents][][];

+		projectionMap=new TIntArrayList[n_words][];

+		for(int sentNum=0;sentNum<n_sents;sentNum++){

+			int [] data=hmm.data[sentNum];

+			posteriorMap[sentNum]=new int[data.length][n_states];

+			numWordsToProject=0;

+			for(int i=0;i<data.length;i++){

+				int word=data[i];

+				for(int state=0;state<n_states;state++){

+					if(wordFreq[word]>MIN_FREQ){

+						if(projectionMap[word]==null){

+							projectionMap[word]=new TIntArrayList[n_states];

+						}

+						

+						posteriorMap[sentNum][i][state]=n_param;

+						if(projectionMap[word][state]==null){

+							projectionMap[word][state]=new TIntArrayList();

+							numWordsToProject++;

+						}

+						projectionMap[word][state].add(n_param);

+						n_param++;

+					}else{

+						

+						posteriorMap[sentNum][i][state]=-1;

+					}

+				}

+			}

+		}

+	}

+	

+	@Override

+	public double[] projectPoint(double[] point) {

+		// TODO Auto-generated method stub

+		for(int i=0;i<projectionMap.length;i++){

+			

+			if(projectionMap[i]==null){

+				//this word is not constrained

+				continue;

+			}

+			

+			for(int j=0;j<projectionMap[i].length;j++){

+				TIntArrayList instances=projectionMap[i][j];

+				double[] toProject = new double[instances.size()];

+				

+				for (int k = 0; k < toProject.length; k++) {

+					//	System.out.print(instances.get(k) + " ");

+						toProject[k] = point[instances.get(k)];

+				}

+				

+				projection.project(toProject);

+				for (int k = 0; k < toProject.length; k++) {

+					newPoint[instances.get(k)]=toProject[k];

+				}

+			}

+		}

+		return newPoint;

+	}

+

+	@Override

+	public double[] getGradient() {

+		// TODO Auto-generated method stub

+		gradientCalls++;

+		return gradient;

+	}

+

+	@Override

+	public double getValue() {

+		// TODO Auto-generated method stub

+		functionCalls++;

+		return loglikelihood;

+	}

+	

+

+	@Override

+	public String toString() {

+		// TODO Auto-generated method stub

+		StringBuffer sb = new StringBuffer();

+		for (int i = 0; i < parameters.length; i++) {

+			sb.append(parameters[i]+" ");

+			if(i%100==0){

+				sb.append("\n");

+			}

+		}

+		sb.append("\n");

+		/*

+		for (int i = 0; i < gradient.length; i++) {

+			sb.append(gradient[i]+" ");

+			if(i%100==0){

+				sb.append("\n");

+			}

+		}

+		sb.append("\n");

+		*/

+		return sb.toString();

+	}

+

+	

+	/**

+	 * @param seq

+	 * @return posterior probability of each transition

+	 */

+	public double [][][]forwardBackward(int sentNum){

+		int [] seq=hmm.data[sentNum];

+		int n_states=hmm.trans.length;

+		double a[][]=new double [seq.length][n_states];

+		double b[][]=new double [seq.length][n_states];

+		

+		int len=seq.length;

+		

+		boolean  constrained=

+			(projectionMap[seq[0]]!=null);

+

+		//initialize the first step

+		for(int i=0;i<n_states;i++){

+			a[0][i]=hmm.emit[i][seq[0]]*hmm.pi[i];

+			if(constrained){

+				a[0][i]*=

+					Math.exp(- parameters[ posteriorMap[sentNum][0][i] ] );

+			}

+			b[len-1][i]=1;

+		}

+		

+		loglikelihood+=Math.log(hmm.l1norm(a[0]));		

+		hmm.l1normalize(a[0]);

+		hmm.l1normalize(b[len-1]);

+		

+		//forward

+		for(int n=1;n<len;n++){

+			

+			constrained=

+				(projectionMap[seq[n]]!=null);

+			

+			for(int i=0;i<n_states;i++){

+				for(int j=0;j<n_states;j++){

+					a[n][i]+=hmm.trans[j][i]*a[n-1][j];

+				}

+				a[n][i]*=hmm.emit[i][seq[n]];

+				

+				if(constrained){

+					a[n][i]*=

+						Math.exp(- parameters[ posteriorMap[sentNum][n][i] ] );

+				}

+				

+			}

+			loglikelihood+=Math.log(hmm.l1norm(a[n]));

+			hmm.l1normalize(a[n]);

+		}

+		

+		//temp variable for e^{-\lambda}

+		double factor=1;

+		//backward

+		for(int n=len-2;n>=0;n--){

+			

+			constrained=

+				(projectionMap[seq[n+1]]!=null);

+			

+			for(int i=0;i<n_states;i++){

+				for(int j=0;j<n_states;j++){

+					

+					if(constrained){

+						factor=

+							Math.exp(- parameters[ posteriorMap[sentNum][n+1][j] ] );

+					}else{

+						factor=1;

+					}

+					

+					b[n][i]+=hmm.trans[i][j]*b[n+1][j]*hmm.emit[j][seq[n+1]]*factor;

+					

+				}

+			}

+			hmm.l1normalize(b[n]);

+		}

+		

+		//expected transition 

+		double p[][][]=new double [seq.length][n_states][n_states];

+		for(int n=0;n<len-1;n++){

+			

+			constrained=

+				(projectionMap[seq[n+1]]!=null);

+			

+			for(int i=0;i<n_states;i++){

+				for(int j=0;j<n_states;j++){

+					

+					if(constrained){

+						factor=

+							Math.exp(- parameters[ posteriorMap[sentNum][n+1][j] ] );

+					}else{

+						factor=1;

+					}

+					

+					p[n][i][j]=a[n][i]*hmm.trans[i][j]*

+						hmm.emit[j][seq[n+1]]*b[n+1][j]*factor;

+					

+				}

+			}

+

+			hmm.l1normalize(p[n]);

+		}

+		return p;

+	}

+

+	public void optimizeWithProjectedGradientDescent(){

+		LineSearchMethod ls =

+			new ArmijoLineSearchMinimizationAlongProjectionArc

+				(new InterpolationPickFirstStep(INIT_STEP_SIZE));

+		

+		OptimizerStats stats = new OptimizerStats();

+		

+		

+		ProjectedGradientDescent optimizer = new ProjectedGradientDescent(ls);

+		StopingCriteria stopGrad = new ProjectedGradientL2Norm(GRAD_DIFF);

+		StopingCriteria stopValue = new ValueDifference(VAL_DIFF);

+		CompositeStopingCriteria compositeStop = new CompositeStopingCriteria();

+		compositeStop.add(stopGrad);

+		compositeStop.add(stopValue);

+		

+		optimizer.setMaxIterations(10);

+		updateFunction();

+		boolean succed = optimizer.optimize(this,stats,compositeStop);

+		System.out.println("Ended optimzation Projected Gradient Descent\n" + stats.prettyPrint(1));

+		if(succed){

+			System.out.println("Ended optimization in " + optimizer.getCurrentIteration());

+		}else{

+			System.out.println("Failed to optimize");

+		}

+	}

+	

+	@Override

+	public void setParameters(double[] params) {

+		super.setParameters(params);

+		updateFunction();

+	}

+	

+	private void updateFunction(){

+		

+		updateCalls++;

+		loglikelihood=0;

+	

+		for(int sentNum=0;sentNum<hmm.data.length;sentNum++){

+			double [][][]p=forwardBackward(sentNum);

+			

+			for(int n=0;n<p.length-1;n++){

+				for(int i=0;i<p[n].length;i++){

+					if(projectionMap[hmm.data[sentNum][n]]!=null){

+						double posterior=0;

+						for(int j=0;j<p[n][i].length;j++){

+							posterior+=p[n][i][j];

+						}

+						gradient[posteriorMap[sentNum][n][i]]=-posterior;

+					}

+				}

+			}

+			

+			//the last state

+			int n=p.length-2;

+			for(int i=0;i<p[n].length;i++){

+				if(projectionMap[hmm.data[sentNum][n+1]]!=null){

+					

+					double posterior=0;

+					for(int j=0;j<p[n].length;j++){

+						posterior+=p[n][j][i];

+					}

+					gradient[posteriorMap[sentNum][n+1][i]]=-posterior;

+				

+				}

+			}	

+		}

+		

+	}

+	

+}