You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@opennlp.apache.org by jo...@apache.org on 2014/04/26 15:02:14 UTC
svn commit: r1590233 - in /opennlp/trunk/opennlp-tools: lang/ml/
src/main/java/opennlp/tools/ml/maxent/quasinewton/
src/test/java/opennlp/tools/ml/maxent/quasinewton/
Author: joern
Date: Sat Apr 26 13:02:13 2014
New Revision: 1590233
URL: http://svn.apache.org/r1590233
Log:
OPENNLP-671 Add L1-regularization into L-BFGS. Thanks to Vinh Khuc for providing a patch.
Added:
opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/NegLogLikelihood.java (with props)
opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/QNMinimizer.java (with props)
opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/NegLogLikelihoodTest.java (with props)
opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/QNMinimizerTest.java (with props)
Removed:
opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/DifferentiableFunction.java
opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/LineSearchResult.java
opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/LogLikelihoodFunction.java
opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/NegLogLikelihoodFunction.java
opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/LogLikelihoodFunctionTest.java
opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/NegLogLikelihoodFunctionTest.java
opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/QuadraticFunction.java
opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/QuadraticFunction02.java
Modified:
opennlp/trunk/opennlp-tools/lang/ml/MaxentQnExperimentalTrainerParams.txt
opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/ArrayMath.java
opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/Function.java
opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/LineSearch.java
opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/QNModel.java
opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/QNTrainer.java
opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/LineSearchTest.java
opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/QNPrepAttachTest.java
Modified: opennlp/trunk/opennlp-tools/lang/ml/MaxentQnExperimentalTrainerParams.txt
URL: http://svn.apache.org/viewvc/opennlp/trunk/opennlp-tools/lang/ml/MaxentQnExperimentalTrainerParams.txt?rev=1590233&r1=1590232&r2=1590233&view=diff
==============================================================================
--- opennlp/trunk/opennlp-tools/lang/ml/MaxentQnExperimentalTrainerParams.txt (original)
+++ opennlp/trunk/opennlp-tools/lang/ml/MaxentQnExperimentalTrainerParams.txt Sat Apr 26 13:02:13 2014
@@ -18,4 +18,5 @@
Algorithm=MAXENT_QN_EXPERIMENTAL
Iterations=100
Cutoff=5
-L2Cost=1.0
\ No newline at end of file
+L1Cost=0.5
+L2Cost=0.5
\ No newline at end of file
Modified: opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/ArrayMath.java
URL: http://svn.apache.org/viewvc/opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/ArrayMath.java?rev=1590233&r1=1590232&r2=1590233&view=diff
==============================================================================
--- opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/ArrayMath.java (original)
+++ opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/ArrayMath.java Sat Apr 26 13:02:13 2014
@@ -37,13 +37,30 @@ public class ArrayMath {
}
/**
+ * L1-norm
+ */
+ public static double l1norm(double[] v) {
+ double norm = 0;
+ for (int i = 0; i < v.length; i++)
+ norm += Math.abs(v[i]);
+ return norm;
+ }
+
+ /**
* L2-norm
*/
- public static double norm(double[] v) {
+ public static double l2norm(double[] v) {
return Math.sqrt(innerProduct(v, v));
}
/**
+ * Inverse L2-norm
+ */
+ public static double invL2norm(double[] v) {
+ return 1 / l2norm(v);
+ }
+
+ /**
* Computes \log(\sum_{i=1}^n e^{x_i}) using a maximum-element trick
* to avoid arithmetic overflow.
*
Modified: opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/Function.java
URL: http://svn.apache.org/viewvc/opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/Function.java?rev=1590233&r1=1590232&r2=1590233&view=diff
==============================================================================
--- opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/Function.java (original)
+++ opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/Function.java Sat Apr 26 13:02:13 2014
@@ -19,11 +19,13 @@
package opennlp.tools.ml.maxent.quasinewton;
/**
- * Interface for a function.
+ * Interface for a function
*/
public interface Function {
- public double valueAt(double[] x);
+ int getDimension();
- public int getDomainDimension();
+ double valueAt(double[] x);
+
+ double[] gradientAt(double[] x);
}
Modified: opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/LineSearch.java
URL: http://svn.apache.org/viewvc/opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/LineSearch.java?rev=1590233&r1=1590232&r2=1590233&view=diff
==============================================================================
--- opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/LineSearch.java (original)
+++ opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/LineSearch.java Sat Apr 26 13:02:13 2014
@@ -22,21 +22,21 @@ package opennlp.tools.ml.maxent.quasinew
* Class that performs line search to find minimum
*/
public class LineSearch {
- private static final double INITIAL_STEP_SIZE = 1.0;
private static final double C = 0.0001;
private static final double RHO = 0.5; // decrease of step size (must be from 0 to 1)
/**
* Backtracking line search (see Nocedal & Wright 2006, Numerical Optimization, p. 37)
*/
- public static void doLineSearch(DifferentiableFunction function,
- double[] direction, LineSearchResult lsr)
+ public static void doLineSearch(Function function,
+ double[] direction, LineSearchResult lsr, double initialStepSize)
{
- double stepSize = INITIAL_STEP_SIZE;
+ double stepSize = initialStepSize;
int currFctEvalCount = lsr.getFctEvalCount();
double[] x = lsr.getNextPoint();
double[] gradAtX = lsr.getGradAtNext();
double valueAtX = lsr.getValueAtNext();
+ int dimension = x.length;
// Retrieve current points and gradient for array reuse purpose
double[] nextPoint = lsr.getCurrPoint();
@@ -50,11 +50,13 @@ public class LineSearch {
while (true) {
// Get next point
- for (int i = 0; i < x.length; i++) {
+ for (int i = 0; i < dimension; i++) {
nextPoint[i] = x[i] + direction[i] * stepSize;
}
+ // New value
valueAtNextPoint = function.valueAt(nextPoint);
+
currFctEvalCount++;
// Check Armijo condition
@@ -73,4 +75,280 @@ public class LineSearch {
lsr.setAll(stepSize, valueAtX, valueAtNextPoint,
gradAtX, gradAtNextPoint, x, nextPoint, currFctEvalCount);
}
+
+ /**
+ * Constrained line search (see section 3.2 in the paper "Scalable Training
+ * of L1-Regularized Log-Linear Models", Andrew et al. 2007)
+ */
+ public static void doConstrainedLineSearch(Function function,
+ double[] direction, LineSearchResult lsr, double l1Cost, double initialStepSize)
+ {
+ double stepSize = initialStepSize;
+ int currFctEvalCount = lsr.getFctEvalCount();
+ double[] x = lsr.getNextPoint();
+ double[] signX = lsr.getSignVector(); // existing sign vector
+ double[] gradAtX = lsr.getGradAtNext();
+ double[] pseudoGradAtX = lsr.getPseudoGradAtNext();
+ double valueAtX = lsr.getValueAtNext();
+ int dimension = x.length;
+
+ // Retrieve current points and gradient for array reuse purpose
+ double[] nextPoint = lsr.getCurrPoint();
+ double[] gradAtNextPoint = lsr.getGradAtCurr();
+ double valueAtNextPoint;
+
+ double dirGradientAtX;
+
+ // New sign vector
+ for (int i = 0; i < dimension; i++) {
+ signX[i] = x[i] == 0? -pseudoGradAtX[i] : x[i];
+ }
+
+ while (true) {
+ // Get next point
+ for (int i = 0; i < dimension; i++) {
+ nextPoint[i] = x[i] + direction[i] * stepSize;
+ }
+
+ // Projection
+ for (int i = 0; i < dimension; i++) {
+ if (nextPoint[i] * signX[i] <= 0)
+ nextPoint[i] = 0;
+ }
+
+ // New value
+ valueAtNextPoint = function.valueAt(nextPoint) +
+ l1Cost * ArrayMath.l1norm(nextPoint);
+
+ currFctEvalCount++;
+
+ dirGradientAtX = 0;
+ for (int i = 0; i < dimension; i++) {
+ dirGradientAtX += (nextPoint[i] - x[i]) * pseudoGradAtX[i];
+ }
+
+ // Check the sufficient decrease condition
+ if (valueAtNextPoint <= valueAtX + C * dirGradientAtX)
+ break;
+
+ // Shrink step size
+ stepSize *= RHO;
+ }
+
+ // Compute and save gradient at the new point
+ System.arraycopy(function.gradientAt(nextPoint), 0, gradAtNextPoint, 0,
+ gradAtNextPoint.length);
+
+ // Update line search result
+ lsr.setAll(stepSize, valueAtX, valueAtNextPoint, gradAtX,
+ gradAtNextPoint, pseudoGradAtX, x, nextPoint, signX, currFctEvalCount);
+ }
+
+ // ------------------------------------------------------------------------------------- //
+
+ /**
+ * Class to store lineSearch result
+ */
+ public static class LineSearchResult {
+
+ private int fctEvalCount;
+ private double stepSize;
+ private double valueAtCurr;
+ private double valueAtNext;
+ private double[] gradAtCurr;
+ private double[] gradAtNext;
+ private double[] pseudoGradAtNext;
+ private double[] currPoint;
+ private double[] nextPoint;
+ private double[] signVector;
+
+ /**
+ * Constructor
+ */
+ public LineSearchResult(
+ double stepSize,
+ double valueAtCurr,
+ double valueAtNext,
+ double[] gradAtCurr,
+ double[] gradAtNext,
+ double[] currPoint,
+ double[] nextPoint,
+ int fctEvalCount)
+ {
+ setAll(stepSize, valueAtCurr, valueAtNext, gradAtCurr, gradAtNext,
+ currPoint, nextPoint, fctEvalCount);
+ }
+
+ /**
+ * Constructor with sign vector
+ */
+ public LineSearchResult(
+ double stepSize,
+ double valueAtCurr,
+ double valueAtNext,
+ double[] gradAtCurr,
+ double[] gradAtNext,
+ double[] pseudoGradAtNext,
+ double[] currPoint,
+ double[] nextPoint,
+ double[] signVector,
+ int fctEvalCount)
+ {
+ setAll(stepSize, valueAtCurr, valueAtNext, gradAtCurr, gradAtNext,
+ pseudoGradAtNext, currPoint, nextPoint, signVector, fctEvalCount);
+ }
+
+ /**
+ * Update line search elements
+ */
+ public void setAll(
+ double stepSize,
+ double valueAtCurr,
+ double valueAtNext,
+ double[] gradAtCurr,
+ double[] gradAtNext,
+ double[] currPoint,
+ double[] nextPoint,
+ int fctEvalCount)
+ {
+ setAll(stepSize, valueAtCurr, valueAtNext, gradAtCurr, gradAtNext,
+ null, currPoint, nextPoint, null, fctEvalCount);
+ }
+
+ /**
+ * Update line search elements
+ */
+ public void setAll(
+ double stepSize,
+ double valueAtCurr,
+ double valueAtNext,
+ double[] gradAtCurr,
+ double[] gradAtNext,
+ double[] pseudoGradAtNext,
+ double[] currPoint,
+ double[] nextPoint,
+ double[] signVector,
+ int fctEvalCount)
+ {
+ this.stepSize = stepSize;
+ this.valueAtCurr = valueAtCurr;
+ this.valueAtNext = valueAtNext;
+ this.gradAtCurr = gradAtCurr;
+ this.gradAtNext = gradAtNext;
+ this.pseudoGradAtNext = pseudoGradAtNext;
+ this.currPoint = currPoint;
+ this.nextPoint = nextPoint;
+ this.signVector = signVector;
+ this.fctEvalCount = fctEvalCount;
+ }
+
+ public double getFuncChangeRate() {
+ return (valueAtCurr - valueAtNext) / valueAtCurr;
+ }
+
+ public double getStepSize() {
+ return stepSize;
+ }
+ public void setStepSize(double stepSize) {
+ this.stepSize = stepSize;
+ }
+
+ public double getValueAtCurr() {
+ return valueAtCurr;
+ }
+ public void setValueAtCurr(double valueAtCurr) {
+ this.valueAtCurr = valueAtCurr;
+ }
+
+ public double getValueAtNext() {
+ return valueAtNext;
+ }
+ public void setValueAtNext(double valueAtNext) {
+ this.valueAtNext = valueAtNext;
+ }
+
+ public double[] getGradAtCurr() {
+ return gradAtCurr;
+ }
+ public void setGradAtCurr(double[] gradAtCurr) {
+ this.gradAtCurr = gradAtCurr;
+ }
+
+ public double[] getGradAtNext() {
+ return gradAtNext;
+ }
+ public void setGradAtNext(double[] gradAtNext) {
+ this.gradAtNext = gradAtNext;
+ }
+
+ public double[] getPseudoGradAtNext() {
+ return pseudoGradAtNext;
+ }
+ public void setPseudoGradAtNext(double[] pseudoGradAtNext) {
+ this.pseudoGradAtNext = pseudoGradAtNext;
+ }
+
+ public double[] getCurrPoint() {
+ return currPoint;
+ }
+ public void setCurrPoint(double[] currPoint) {
+ this.currPoint = currPoint;
+ }
+
+ public double[] getNextPoint() {
+ return nextPoint;
+ }
+ public void setNextPoint(double[] nextPoint) {
+ this.nextPoint = nextPoint;
+ }
+
+ public double[] getSignVector() {
+ return signVector;
+ }
+ public void setSignVector(double[] signVector) {
+ this.signVector = signVector;
+ }
+
+ public int getFctEvalCount() {
+ return fctEvalCount;
+ }
+ public void setFctEvalCount(int fctEvalCount) {
+ this.fctEvalCount = fctEvalCount;
+ }
+
+ /**
+ * Initial linear search object
+ */
+ public static LineSearchResult getInitialObject(
+ double valueAtX,
+ double[] gradAtX,
+ double[] x)
+ {
+ return getInitialObject(valueAtX, gradAtX, null, x, null, 0);
+ }
+
+ /**
+ * Initial linear search object for L1-regularization
+ */
+ public static LineSearchResult getInitialObjectForL1(
+ double valueAtX,
+ double[] gradAtX,
+ double[] pseudoGradAtX,
+ double[] x)
+ {
+ return getInitialObject(valueAtX, gradAtX, pseudoGradAtX, x, new double[x.length], 0);
+ }
+
+ public static LineSearchResult getInitialObject(
+ double valueAtX,
+ double[] gradAtX,
+ double[] pseudoGradAtX,
+ double[] x,
+ double[] signX,
+ int fctEvalCount)
+ {
+ return new LineSearchResult(0.0, 0.0, valueAtX, new double[x.length], gradAtX,
+ pseudoGradAtX, new double[x.length], x, signX, fctEvalCount);
+ }
+ }
}
Added: opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/NegLogLikelihood.java
URL: http://svn.apache.org/viewvc/opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/NegLogLikelihood.java?rev=1590233&view=auto
==============================================================================
--- opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/NegLogLikelihood.java (added)
+++ opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/NegLogLikelihood.java Sat Apr 26 13:02:13 2014
@@ -0,0 +1,183 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package opennlp.tools.ml.maxent.quasinewton;
+
+import java.util.Arrays;
+
+import opennlp.tools.ml.model.DataIndexer;
+import opennlp.tools.ml.model.OnePassRealValueDataIndexer;
+
+/**
+ * Evaluate negative log-likelihood and its gradient from DataIndexer.
+ */
+public class NegLogLikelihood implements Function {
+
+ private int dimension;
+ private double[] empiricalCount;
+ private int numOutcomes;
+ private int numFeatures;
+ private int numContexts;
+
+ // Information from data index
+ private final float[][] values;
+ private final int[][] contexts;
+ private final int[] outcomeList;
+ private final int[] numTimesEventsSeen;
+
+ // For computing negative log-likelihood
+ private double[][] voteSum;
+ private double[] logSumExp;
+
+ // For gradient computation
+ private double[] gradient;
+ private double[] expectedCount;
+
+ public NegLogLikelihood(DataIndexer indexer) {
+
+ // Get data from indexer.
+ if (indexer instanceof OnePassRealValueDataIndexer) {
+ this.values = indexer.getValues();
+ } else {
+ this.values = null;
+ }
+
+ this.contexts = indexer.getContexts();
+ this.outcomeList = indexer.getOutcomeList();
+ this.numTimesEventsSeen = indexer.getNumTimesEventsSeen();
+
+ this.numOutcomes = indexer.getOutcomeLabels().length;
+ this.numFeatures = indexer.getPredLabels().length;
+ this.numContexts = this.contexts.length;
+ this.dimension = numOutcomes * numFeatures;
+ this.empiricalCount = new double[dimension];
+
+ this.voteSum = new double[numContexts][numOutcomes];
+ this.logSumExp = new double[numContexts];
+
+ this.gradient = new double[dimension];
+ this.expectedCount = new double[dimension];
+
+ computeEmpCount();
+ }
+
+ public int getDimension() {
+ return this.dimension;
+ }
+
+ public double[] getInitialPoint() {
+ return new double[dimension];
+ }
+
+ /**
+ * Negative log-likelihood
+ */
+ public double valueAt(double[] x) {
+
+ if (x.length != this.dimension)
+ throw new IllegalArgumentException(
+ "x is invalid, its dimension is not equal to domain dimension.");
+
+ computeSums(x); // Compute voteSum and logSumExp
+
+ double negLogLikelihood = 0.;
+ for (int ci = 0; ci < numContexts; ci++) {
+ int outcome = this.outcomeList[ci];
+ negLogLikelihood += (voteSum[ci][outcome] - logSumExp[ci]) * numTimesEventsSeen[ci];
+ }
+ negLogLikelihood = -negLogLikelihood;
+
+ return negLogLikelihood;
+ }
+
+ /**
+ * Compute gradient
+ */
+ public double[] gradientAt(double[] x) {
+
+ if (x.length != this.dimension)
+ throw new IllegalArgumentException(
+ "x is invalid, its dimension is not equal to the function.");
+
+ computeSums(x); // Compute voteSum and logSumExp
+
+ // Reset
+ Arrays.fill(expectedCount, 0);
+ for (int ci = 0; ci < numContexts; ci++) {
+ for (int oi = 0; oi < numOutcomes; oi++) {
+ for (int af = 0; af < contexts[ci].length; af++) {
+ int vectorIndex = indexOf(oi, this.contexts[ci][af]);
+ double predValue = 1.;
+ if (values != null) predValue = this.values[ci][af];
+ if (predValue == 0.) continue;
+
+ expectedCount[vectorIndex] +=
+ predValue * Math.exp(voteSum[ci][oi] - logSumExp[ci]) * this.numTimesEventsSeen[ci];
+ }
+ }
+ }
+
+ for (int i = 0; i < dimension; i++) {
+ gradient[i] = expectedCount[i] - this.empiricalCount[i];
+ }
+
+ return gradient;
+ }
+
+ private int indexOf(int outcomeId, int featureId) {
+ return outcomeId * numFeatures + featureId;
+ }
+
+ /**
+ * Compute temporary values
+ */
+ private void computeSums(double[] x) {
+ for (int ci = 0; ci < numContexts; ci++) {
+ for (int oi = 0; oi < numOutcomes; oi++) {
+ double vecProduct = 0.;
+ for (int af = 0; af < this.contexts[ci].length; af++) {
+ int vectorIndex = indexOf(oi, contexts[ci][af]);
+ double predValue = 1.;
+ if (values != null) predValue = this.values[ci][af];
+ if (predValue == 0.) continue;
+ vecProduct += predValue * x[vectorIndex];
+ }
+ voteSum[ci][oi] = vecProduct;
+ }
+
+ // \log(\sum_{c'=1}^{C} e^{w_c'^T x_i})
+ logSumExp[ci] = ArrayMath.logSumOfExps(voteSum[ci]);
+ }
+ }
+
+ /**
+ * Compute empirical count
+ */
+ private void computeEmpCount() {
+ for (int ci = 0; ci < numContexts; ci++) {
+ for (int af = 0; af < this.contexts[ci].length; af++) {
+ int vectorIndex = indexOf(this.outcomeList[ci], contexts[ci][af]);
+ if (values != null) {
+ empiricalCount[vectorIndex] += this.values[ci][af] * numTimesEventsSeen[ci];
+ } else {
+ empiricalCount[vectorIndex] += 1. * numTimesEventsSeen[ci];
+ }
+ }
+ }
+ }
+}
\ No newline at end of file
Propchange: opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/NegLogLikelihood.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/QNMinimizer.java
URL: http://svn.apache.org/viewvc/opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/QNMinimizer.java?rev=1590233&view=auto
==============================================================================
--- opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/QNMinimizer.java (added)
+++ opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/QNMinimizer.java Sat Apr 26 13:02:13 2014
@@ -0,0 +1,531 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package opennlp.tools.ml.maxent.quasinewton;
+
+import opennlp.tools.ml.maxent.quasinewton.LineSearch.LineSearchResult;
+
+/**
+ * Implementation of L-BFGS which supports L1-, L2-regularization
+ * and Elastic Net for solving convex optimization problems. <p>
+ * Usage example:
+ * <blockquote><pre>
+ * // Quadratic function f(x) = (x-1)^2 + 10
+ * // f obtains its minimum value 10 at x = 1
+ * Function f = new Function() {
+ *
+ * {@literal @}Override
+ * public int getDimension() {
+ * return 1;
+ * }
+ *
+ * {@literal @}Override
+ * public double valueAt(double[] x) {
+ * return Math.pow(x[0]-1, 2) + 10;
+ * }
+ *
+ * {@literal @}Override
+ * public double[] gradientAt(double[] x) {
+ * return new double[] { 2*(x[0]-1) };
+ * }
+ *
+ * };
+ *
+ * QNMinimizer minimizer = new QNMinimizer();
+ * double[] x = minimizer.minimize(f);
+ * double min = f.valueAt(x);
+ * <pre></blockquote>
+ */
+public class QNMinimizer {
+
+ // Function change rate tolerance
+ public static final double CONVERGE_TOLERANCE = 1e-4;
+
+ // Relative gradient norm tolerance
+ public static final double REL_GRAD_NORM_TOL = 1e-4;
+
+ // Initial step size
+ public static final double INITIAL_STEP_SIZE = 1.0;
+
+ // Minimum step size
+ public static final double MIN_STEP_SIZE = 1e-10;
+
+ // Default L1-cost
+ public static final double L1COST_DEFAULT = 0;
+
+ // Default L2-cost
+ public static final double L2COST_DEFAULT = 0;
+
+ // Default number of iterations
+ public static final int NUM_ITERATIONS_DEFAULT = 100;
+
+ // Default number of Hessian updates to store
+ public static final int M_DEFAULT = 15;
+
+ // Default maximum number of function evaluations
+ public static final int MAX_FCT_EVAL_DEFAULT = 30000;
+
+ // L1-regularization cost
+ private double l1Cost;
+
+ // L2-regularization cost
+ private double l2Cost;
+
+ // Maximum number of iterations
+ private int iterations;
+
+ // Number of Hessian updates to store
+ private int m;
+
+ // Maximum number of function evaluations
+ private int maxFctEval;
+
+ // Verbose output
+ private boolean verbose;
+
+ // Objective function's dimension
+ private int dimension;
+
+ // Hessian updates
+ private UpdateInfo updateInfo;
+
+ // For evaluating quality of training parameters.
+ // This is optional and can be omitted.
+ private Evaluator evaluator;
+
+ public QNMinimizer() {
+ this(L1COST_DEFAULT, L2COST_DEFAULT);
+ }
+
+ public QNMinimizer(double l1Cost, double l2Cost) {
+ this(l1Cost, l2Cost, NUM_ITERATIONS_DEFAULT);
+ }
+
+ public QNMinimizer(double l1Cost, double l2Cost, int iterations) {
+ this(l1Cost, l2Cost, iterations, M_DEFAULT, MAX_FCT_EVAL_DEFAULT);
+ }
+
+ public QNMinimizer(double l1Cost, double l2Cost,
+ int iterations, int m, int maxFctEval) {
+ this(l1Cost, l2Cost, iterations, m, maxFctEval, true);
+ }
+
+ /**
+ * Constructor
+ * @param l1Cost L1-regularization cost
+ * @param l2Cost L2-regularization cost
+ * @param iterations maximum number of iterations
+ * @param m number of Hessian updates to store
+ * @param maxFctEval maximum number of function evaluations
+ * @param verbose verbose output
+ */
+ public QNMinimizer(double l1Cost, double l2Cost, int iterations,
+ int m, int maxFctEval, boolean verbose)
+ {
+ // Check arguments
+ if (l1Cost < 0 || l2Cost < 0)
+ throw new IllegalArgumentException(
+ "L1-cost and L2-cost must not be less than zero");
+
+ if (iterations <= 0)
+ throw new IllegalArgumentException(
+ "Number of iterations must be larger than zero");
+
+ if (m <= 0)
+ throw new IllegalArgumentException(
+ "Number of Hessian updates must be larger than zero");
+
+ if (maxFctEval <= 0)
+ throw new IllegalArgumentException(
+ "Maximum number of function evaluations must be larger than zero");
+
+ this.l1Cost = l1Cost;
+ this.l2Cost = l2Cost;
+ this.iterations = iterations;
+ this.m = m;
+ this.maxFctEval = maxFctEval;
+ this.verbose = verbose;
+ }
+
+ public Evaluator getEvaluator() {
+ return evaluator;
+ }
+ public void setEvaluator(Evaluator evaluator) {
+ this.evaluator = evaluator;
+ }
+
+ /**
+ * Find the parameters that minimizes the objective function
+ * @param function objective function
+ * @return minimizing parameters
+ */
+ public double[] minimize(Function function) {
+
+ Function l2RegFunction = new L2RegFunction(function, l2Cost);
+ this.dimension = l2RegFunction.getDimension();
+ this.updateInfo = new UpdateInfo(this.m, this.dimension);
+
+ // Current point is at the origin
+ double[] currPoint = new double[dimension];
+
+ double currValue = l2RegFunction.valueAt(currPoint);
+
+ // Gradient at the current point
+ double[] currGrad = new double[dimension];
+ System.arraycopy(l2RegFunction.gradientAt(currPoint), 0,
+ currGrad, 0, dimension);
+
+ // Pseudo-gradient - only use when L1-regularization is enabled
+ double[] pseudoGrad = null;
+ if (l1Cost > 0) {
+ currValue += l1Cost * ArrayMath.l1norm(currPoint);
+ pseudoGrad = new double[dimension];
+ computePseudoGrad(currPoint, currGrad, pseudoGrad);
+ }
+
+ LineSearchResult lsr;
+ if (l1Cost > 0) {
+ lsr = LineSearchResult.getInitialObjectForL1(
+ currValue, currGrad, pseudoGrad, currPoint);
+ } else {
+ lsr = LineSearchResult.getInitialObject(
+ currValue, currGrad, currPoint);
+ }
+
+ if (verbose) {
+ display("\nSolving convex optimization problem.");
+ display("\nObjective function has " + dimension + " variable(s).");
+ display("\n\nPerforming " + iterations + " iterations with " +
+ "L1-cost = " + l1Cost + " and L2-cost = " + l2Cost + ".\n");
+ }
+
+ double[] direction = new double[dimension];
+ long startTime = System.currentTimeMillis();
+
+ // Initial step size for the 1st iteration
+ double initialStepSize = l1Cost > 0?
+ ArrayMath.invL2norm(lsr.getPseudoGradAtNext()) :
+ ArrayMath.invL2norm(lsr.getGradAtNext());
+
+ for (int iter = 1; iter <= iterations; iter++) {
+ // Find direction
+ if (l1Cost > 0) {
+ System.arraycopy(lsr.getPseudoGradAtNext(), 0, direction, 0, direction.length);
+ } else {
+ System.arraycopy(lsr.getGradAtNext(), 0, direction, 0, direction.length);
+ }
+ computeDirection(direction);
+
+ // Line search
+ if (l1Cost > 0) {
+ // Constrain the search direction
+ pseudoGrad = lsr.getPseudoGradAtNext();
+ for (int i = 0; i < dimension; i++) {
+ if (direction[i] * pseudoGrad[i] >= 0) {
+ direction[i] = 0;
+ }
+ }
+ LineSearch.doConstrainedLineSearch(l2RegFunction, direction, lsr, l1Cost, initialStepSize);
+ computePseudoGrad(lsr.getNextPoint(), lsr.getGradAtNext(), pseudoGrad);
+ lsr.setPseudoGradAtNext(pseudoGrad);
+ }
+ else {
+ LineSearch.doLineSearch(l2RegFunction, direction, lsr, initialStepSize);
+ }
+
+ // Save Hessian updates
+ updateInfo.update(lsr);
+
+ if (verbose) {
+ if (iter < 10)
+ display(" " + iter + ": ");
+ else if (iter < 100)
+ display(" " + iter + ": ");
+ else
+ display(iter + ": ");
+
+ if (evaluator != null) {
+ display("\t " + lsr.getValueAtCurr() + "\t" + lsr.getFuncChangeRate()
+ + "\t" + evaluator.evaluate(lsr.getNextPoint()) + "\n");
+ } else {
+ display("\t " + lsr.getValueAtCurr() + "\t" + lsr.getFuncChangeRate() + "\n");
+ }
+ }
+ if (isConverged(lsr))
+ break;
+
+ initialStepSize = INITIAL_STEP_SIZE;
+ }
+
+ // Undo L2-shrinkage if Elastic Net is used (since
+ // in that case, the shrinkage is done twice)
+ if (l1Cost > 0 && l2Cost > 0) {
+ double[] x = lsr.getNextPoint();
+ for (int i = 0; i < dimension; i++) {
+ x[i] = Math.sqrt(1 + l2Cost) * x[i];
+ }
+ }
+
+ long endTime = System.currentTimeMillis();
+ long duration = endTime - startTime;
+ display("Running time: " + (duration / 1000.) + "s\n");
+
+ // Release memory
+ this.updateInfo = null;
+ System.gc();
+
+ // Avoid returning the reference to LineSearchResult's member so that GC can
+ // collect memory occupied by lsr after this function completes (is it necessary?)
+ double[] parameters = new double[dimension];
+ System.arraycopy(lsr.getNextPoint(), 0, parameters, 0, dimension);
+
+ return parameters;
+ }
+
+ /**
+ * Pseudo-gradient for L1-regularization (see equation 4 in the paper
+ * "Scalable Training of L1-Regularized Log-Linear Models", Andrew et al. 2007)
+ *
+ * @param x current point
+ * @param g gradient at x
+ * @param pg pseudo-gradient at x which is to be computed
+ */
+ private void computePseudoGrad(double[] x, double[] g, double[] pg) {
+ for (int i = 0; i < dimension; i++) {
+ if (x[i] < 0) {
+ pg[i] = g[i] - l1Cost;
+ }
+ else if (x[i] > 0) {
+ pg[i] = g[i] + l1Cost;
+ }
+ else {
+ if (g[i] < -l1Cost) {
+ // right partial derivative
+ pg[i] = g[i] + l1Cost;
+ }
+ else if (g[i] > l1Cost) {
+ // left partial derivative
+ pg[i] = g[i] - l1Cost;
+ }
+ else {
+ pg[i] = 0;
+ }
+ }
+ }
+ }
+
+ /**
+ * L-BFGS two-loop recursion (see Nocedal & Wright 2006, Numerical Optimization, p. 178)
+ */
+ private void computeDirection(double[] direction) {
+
+ // Implemented two-loop Hessian update method.
+ int k = updateInfo.kCounter;
+ double[] rho = updateInfo.rho;
+ double[] alpha = updateInfo.alpha; // just to avoid recreating alpha
+ double[][] S = updateInfo.S;
+ double[][] Y = updateInfo.Y;
+
+ // First loop
+ for (int i = k - 1; i >= 0; i--) {
+ alpha[i] = rho[i] * ArrayMath.innerProduct(S[i], direction);
+ for (int j = 0; j < dimension; j++) {
+ direction[j] = direction[j] - alpha[i] * Y[i][j];
+ }
+ }
+
+ // Second loop
+ for (int i = 0; i < k; i++) {
+ double beta = rho[i] * ArrayMath.innerProduct(Y[i], direction);
+ for (int j = 0; j < dimension; j++) {
+ direction[j] = direction[j] + S[i][j] * (alpha[i] - beta);
+ }
+ }
+
+ for (int i = 0; i < dimension; i++) {
+ direction[i] = -direction[i];
+ }
+ }
+
+ private boolean isConverged(LineSearchResult lsr) {
+
+ // Check function's change rate
+ if (lsr.getFuncChangeRate() < CONVERGE_TOLERANCE) {
+ if (verbose)
+ display("Function change rate is smaller than the threshold "
+ + CONVERGE_TOLERANCE + ".\nTraining will stop.\n\n");
+ return true;
+ }
+
+ // Check gradient's norm using the criteria: ||g(x)|| / max(1, ||x||) < threshold
+ double xNorm = Math.max(1, ArrayMath.l2norm(lsr.getNextPoint()));
+ double gradNorm = l1Cost > 0?
+ ArrayMath.l2norm(lsr.getPseudoGradAtNext()) : ArrayMath.l2norm(lsr.getGradAtNext());
+ if (gradNorm / xNorm < REL_GRAD_NORM_TOL) {
+ if (verbose)
+ display("Relative L2-norm of the gradient is smaller than the threshold "
+ + REL_GRAD_NORM_TOL + ".\nTraining will stop.\n\n");
+ return true;
+ }
+
+ // Check step size
+ if (lsr.getStepSize() < MIN_STEP_SIZE) {
+ if (verbose)
+ display("Step size is smaller than the minimum step size "
+ + MIN_STEP_SIZE + ".\nTraining will stop.\n\n");
+ return true;
+ }
+
+ // Check number of function evaluations
+ if (lsr.getFctEvalCount() > this.maxFctEval) {
+ if (verbose)
+ display("Maximum number of function evaluations has exceeded the threshold "
+ + this.maxFctEval + ".\nTraining will stop.\n\n");
+ return true;
+ }
+
+ return false;
+ }
+
+ /**
+ * Shorthand for System.out.print
+ */
+ private void display(String s) {
+ System.out.print(s);
+ }
+
+ /**
+ * Class to store vectors for Hessian approximation update.
+ */
+ private class UpdateInfo {
+ private double[][] S;
+ private double[][] Y;
+ private double[] rho;
+ private double[] alpha;
+ private int m;
+
+ private int kCounter;
+
+ // Constructor
+ UpdateInfo(int numCorrection, int dimension) {
+ this.m = numCorrection;
+ this.kCounter = 0;
+ S = new double[this.m][dimension];
+ Y = new double[this.m][dimension];
+ rho = new double[this.m];
+ alpha = new double[this.m];
+ }
+
+ public void update(LineSearchResult lsr) {
+ double[] currPoint = lsr.getCurrPoint();
+ double[] gradAtCurr = lsr.getGradAtCurr();
+ double[] nextPoint = lsr.getNextPoint();
+ double[] gradAtNext = lsr.getGradAtNext();
+
+ // Inner product of S_k and Y_k
+ double SYk = 0.0;
+
+ // Add new ones.
+ if (kCounter < m) {
+ for (int j = 0; j < dimension; j++) {
+ S[kCounter][j] = nextPoint[j] - currPoint[j];
+ Y[kCounter][j] = gradAtNext[j] - gradAtCurr[j];
+ SYk += S[kCounter][j] * Y[kCounter][j];
+ }
+ rho[kCounter] = 1.0 / SYk;
+ }
+ else {
+ // Discard oldest vectors and add new ones.
+ for (int i = 0; i < m - 1; i++) {
+ S[i] = S[i + 1];
+ Y[i] = Y[i + 1];
+ rho[i] = rho[i + 1];
+ }
+ for (int j = 0; j < dimension; j++) {
+ S[m - 1][j] = nextPoint[j] - currPoint[j];
+ Y[m - 1][j] = gradAtNext[j] - gradAtCurr[j];
+ SYk += S[m - 1][j] * Y[m - 1][j];
+ }
+ rho[m - 1] = 1.0 / SYk;
+ }
+
+ if (kCounter < m)
+ kCounter++;
+ }
+ }
+
+ /**
+ * L2-regularized objective function
+ */
+ public static class L2RegFunction implements Function {
+ private Function f;
+ private double l2Cost;
+
+ public L2RegFunction(Function f, double l2Cost) {
+ this.f = f;
+ this.l2Cost = l2Cost;
+ }
+
+ @Override
+ public int getDimension() {
+ return f.getDimension();
+ }
+
+ @Override
+ public double valueAt(double[] x) {
+ checkDimension(x);
+ double value = f.valueAt(x);
+ if (l2Cost > 0) {
+ value += l2Cost * ArrayMath.innerProduct(x, x);
+ }
+ return value;
+ }
+
+ @Override
+ public double[] gradientAt(double[] x) {
+ checkDimension(x);
+ double[] gradient = f.gradientAt(x);
+ if (l2Cost > 0) {
+ for (int i = 0; i < x.length; i++) {
+ gradient[i] += 2 * l2Cost * x[i];
+ }
+ }
+ return gradient;
+ }
+
+ private void checkDimension(double[] x) {
+ if (x.length != getDimension())
+ throw new IllegalArgumentException(
+ "x's dimension is not the same as function's dimension");
+ }
+ }
+
+ /**
+ * Evaluate quality of training parameters. For example,
+ * it can be used to report model's training accuracy when
+ * we train a Maximum Entropy classifier.
+ */
+ public static interface Evaluator {
+ /**
+ * Measure quality of the training parameters
+ * @param parameters
+ * @return evaluated result
+ */
+ double evaluate(double[] parameters);
+ }
+}
Propchange: opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/QNMinimizer.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Modified: opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/QNModel.java
URL: http://svn.apache.org/viewvc/opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/QNModel.java?rev=1590233&r1=1590232&r2=1590233&view=diff
==============================================================================
--- opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/QNModel.java (original)
+++ opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/QNModel.java Sat Apr 26 13:02:13 2014
@@ -20,13 +20,11 @@ package opennlp.tools.ml.maxent.quasinew
import opennlp.tools.ml.model.AbstractModel;
import opennlp.tools.ml.model.Context;
-import opennlp.tools.ml.model.UniformPrior;
public class QNModel extends AbstractModel {
public QNModel(Context[] params, String[] predLabels, String[] outcomeNames) {
super(params, predLabels, outcomeNames);
- this.prior = new UniformPrior();
this.modelType = ModelType.MaxentQn;
}
Modified: opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/QNTrainer.java
URL: http://svn.apache.org/viewvc/opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/QNTrainer.java?rev=1590233&r1=1590232&r2=1590233&view=diff
==============================================================================
--- opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/QNTrainer.java (original)
+++ opennlp/trunk/opennlp-tools/src/main/java/opennlp/tools/ml/maxent/quasinewton/QNTrainer.java Sat Apr 26 13:02:13 2014
@@ -23,6 +23,7 @@ import java.util.ArrayList;
import java.util.List;
import opennlp.tools.ml.AbstractEventTrainer;
+import opennlp.tools.ml.maxent.quasinewton.QNMinimizer.Evaluator;
import opennlp.tools.ml.model.AbstractModel;
import opennlp.tools.ml.model.Context;
import opennlp.tools.ml.model.DataIndexer;
@@ -33,62 +34,57 @@ import opennlp.tools.ml.model.DataIndexe
public class QNTrainer extends AbstractEventTrainer {
public static final String MAXENT_QN_VALUE = "MAXENT_QN_EXPERIMENTAL";
-
- // function change rate tolerance
- private static final double CONVERGE_TOLERANCE = 1e-4;
- // relative gradient norm tolerance. Currently not being used.
- private static final boolean USE_REL_GRAD_NORM = false;
- private static final double REL_GRAD_NORM_TOL = 1e-8;
-
- // minimum step size
- public static final double MIN_STEP_SIZE = 1e-10;
+ public static final String L1COST_PARAM = "L1Cost";
+ public static final double L1COST_DEFAULT = 0.5;
public static final String L2COST_PARAM = "L2Cost";
- public static final double L2COST_DEFAULT = 1.0;
+ public static final double L2COST_DEFAULT = 0.5;
- // number of Hessian updates to store
- private static final String M_PARAM = "numOfUpdates";
- private static final int M_DEFAULT = 15;
-
- private static final String MAX_FCT_EVAL_PARAM = "maxFctEval";
- private static final int MAX_FCT_EVAL_DEFAULT = 30000;
+ // Number of Hessian updates to store
+ public static final String M_PARAM = "numOfUpdates";
+ public static final int M_DEFAULT = 15;
+
+ // Maximum number of function evaluations
+ public static final String MAX_FCT_EVAL_PARAM = "maxFctEval";
+ public static final int MAX_FCT_EVAL_DEFAULT = 30000;
+ // L1-regularization cost
+ private double l1Cost;
+
// L2-regularization cost
private double l2Cost;
- // settings for objective function and optimizer.
- private int dimension;
+ // Settings for QNMinimizer
private int m;
private int maxFctEval;
- private double initialGradNorm;
- private QNInfo updateInfo;
private boolean verbose = true;
- // constructor -- to log. For testing purpose
+ // Constructor -- to log. For testing purpose
public QNTrainer(boolean verbose) {
this(M_DEFAULT, verbose);
}
- // constructor -- m : number of hessian updates to store. For testing purpose
+ // Constructor -- m : number of hessian updates to store. For testing purpose
public QNTrainer(int m) {
this(m, true);
}
- // constructor -- to log, number of hessian updates to store. For testing purpose
+ // Constructor -- to log, number of hessian updates to store. For testing purpose
public QNTrainer(int m, boolean verbose) {
this(m, MAX_FCT_EVAL_DEFAULT, verbose);
}
- // for testing purpose
+ // For testing purpose
public QNTrainer(int m, int maxFctEval, boolean verbose) {
this.verbose = verbose;
this.m = m < 0? M_DEFAULT: m;
this.maxFctEval = maxFctEval < 0? MAX_FCT_EVAL_DEFAULT: maxFctEval;
+ this.l1Cost = L1COST_DEFAULT;
this.l2Cost = L2COST_DEFAULT;
}
- // >> members related to AbstractEventTrainer
+ // >> Members related to AbstractEventTrainer
public QNTrainer() {
}
@@ -117,7 +113,13 @@ public class QNTrainer extends AbstractE
}
this.maxFctEval = maxFctEval;
- // L2-regularization cost must be >= 0
+ // Regularization costs must be >= 0
+ double l1Cost = getDoubleParam(L1COST_PARAM, L1COST_DEFAULT);
+ if (l1Cost < 0) {
+ return false;
+ }
+ this.l1Cost = l1Cost;
+
double l2Cost = getDoubleParam(L2COST_PARAM, L2COST_DEFAULT);
if (l2Cost < 0) {
return false;
@@ -136,65 +138,20 @@ public class QNTrainer extends AbstractE
return trainModel(iterations, indexer);
}
- // << members related to AbstractEventTrainer
+ // << Members related to AbstractEventTrainer
public QNModel trainModel(int iterations, DataIndexer indexer) {
- NegLogLikelihoodFunction objectiveFunction = new NegLogLikelihoodFunction(indexer, l2Cost);
- this.dimension = objectiveFunction.getDomainDimension();
- this.updateInfo = new QNInfo(this.m, this.dimension);
-
- // current point is at the origin
- double[] currPoint = new double[dimension];
- double currValue = objectiveFunction.valueAt(currPoint);
+ // Train model's parameters
+ Function objectiveFunction = new NegLogLikelihood(indexer);
- // gradient at the current point
- double[] currGrad = new double[dimension];
- System.arraycopy(objectiveFunction.gradientAt(currPoint), 0,
- currGrad, 0, dimension);
-
- // initial L2-norm of the gradient
- this.initialGradNorm = ArrayMath.norm(currGrad);
-
- LineSearchResult lsr = LineSearchResult.getInitialObject(
- currValue, currGrad, currPoint, 0);
+ QNMinimizer minimizer = new QNMinimizer(
+ l1Cost, l2Cost, iterations, m, maxFctEval, verbose);
+ minimizer.setEvaluator(new ModelEvaluator(indexer));
- if (verbose)
- display("\nPerforming " + iterations + " iterations with " +
- "L2-cost = " + l2Cost + "\n");
-
- double[] direction = new double[this.dimension];
- long startTime = System.currentTimeMillis();
-
- for (int iter = 1; iter <= iterations; iter++) {
- computeDirection(lsr, direction);
- LineSearch.doLineSearch(objectiveFunction, direction, lsr);
- updateInfo.updateInfo(lsr);
-
- if (verbose) {
- double accurarcy = evaluateModel(indexer, lsr.getNextPoint());
- if (iter < 10)
- display(" " + iter + ": ");
- else if (iter < 100)
- display(" " + iter + ": ");
- else
- display(iter + ": ");
-
- display("\t " + lsr.getValueAtCurr());
- display("\t" + lsr.getFuncChangeRate());
- display("\t" + accurarcy);
- display("\n");
- }
- if (isConverged(lsr))
- break;
- }
-
- long endTime = System.currentTimeMillis();
- long duration = endTime - startTime;
- display("Training time: " + (duration / 1000.) + "s\n");
-
- double[] parameters = lsr.getNextPoint();
-
+ double[] parameters = minimizer.minimize(objectiveFunction);
+
+ // Construct model with trained parameters
String[] predLabels = indexer.getPredLabels();
int nPredLabels = predLabels.length;
@@ -207,11 +164,8 @@ public class QNTrainer extends AbstractE
List<Double> alpha = new ArrayList<Double>(nOutcomes);
for (int oi = 0; oi < nOutcomes; oi++) {
double val = parameters[oi * nPredLabels + ci];
- // Only save data corresponding to non-zero values
- if (val != 0) {
- outcomePattern.add(oi);
- alpha.add(val);
- }
+ outcomePattern.add(oi);
+ alpha.add(val);
}
params[ci] = new Context(ArrayMath.toIntArray(outcomePattern),
ArrayMath.toDoubleArray(alpha));
@@ -221,172 +175,46 @@ public class QNTrainer extends AbstractE
}
/**
- * L-BFGS two-loop recursion (see Nocedal & Wright 2006, Numerical Optimization, p. 178)
+ * For measuring model's training accuracy
*/
- private void computeDirection(LineSearchResult lsr, double[] direction) {
-
- // implemented two-loop Hessian update method.
- System.arraycopy(lsr.getGradAtNext(), 0, direction, 0, direction.length);
+ private class ModelEvaluator implements Evaluator {
- int k = updateInfo.kCounter;
- double[] rho = updateInfo.rho;
- double[] alpha = updateInfo.alpha; // just to avoid recreating alpha
- double[][] S = updateInfo.S;
- double[][] Y = updateInfo.Y;
-
- // first loop
- for (int i = k - 1; i >= 0; i--) {
- alpha[i] = rho[i] * ArrayMath.innerProduct(S[i], direction);
- for (int j = 0; j < dimension; j++) {
- direction[j] = direction[j] - alpha[i] * Y[i][j];
- }
- }
+ private DataIndexer indexer;
- // second loop
- for (int i = 0; i < k; i++) {
- double beta = rho[i] * ArrayMath.innerProduct(Y[i], direction);
- for (int j = 0; j < dimension; j++) {
- direction[j] = direction[j] + S[i][j] * (alpha[i] - beta);
- }
+ public ModelEvaluator(DataIndexer indexer) {
+ this.indexer = indexer;
}
- for (int i = 0; i < dimension; i++) {
- direction[i] = -direction[i];
- }
- }
-
- // TODO: Need an improvement in convergence condition
- private boolean isConverged(LineSearchResult lsr) {
-
- if (lsr.getFuncChangeRate() < CONVERGE_TOLERANCE) {
- if (verbose)
- display("Function change rate is smaller than the threshold "
- + CONVERGE_TOLERANCE + ".\nTraining will stop.\n\n");
- return true;
- }
-
- if (USE_REL_GRAD_NORM) {
- double gradNorm = ArrayMath.norm(lsr.getGradAtNext());
- if (gradNorm / initialGradNorm < REL_GRAD_NORM_TOL) {
- if (verbose)
- display("Relative L2-norm of the gradient is smaller than the threshold "
- + REL_GRAD_NORM_TOL + ".\nTraining will stop.\n\n");
- return true;
- }
- }
-
- if (lsr.getStepSize() < MIN_STEP_SIZE) {
- if (verbose)
- display("Step size is smaller than the minimum step size "
- + MIN_STEP_SIZE + ".\nTraining will stop.\n\n");
- return true;
- }
+ /**
+ * Evaluate the current model on training data set
+ * @return model's training accuracy
+ */
+ @Override
+ public double evaluate(double[] parameters) {
+ int[][] contexts = indexer.getContexts();
+ float[][] values = indexer.getValues();
+ int[] nEventsSeen = indexer.getNumTimesEventsSeen();
+ int[] outcomeList = indexer.getOutcomeList();
+ int nOutcomes = indexer.getOutcomeLabels().length;
+ int nPredLabels = indexer.getPredLabels().length;
+
+ int nCorrect = 0;
+ int nTotalEvents = 0;
+
+ for (int ei = 0; ei < contexts.length; ei++) {
+ int[] context = contexts[ei];
+ float[] value = values == null? null: values[ei];
- if (lsr.getFctEvalCount() > this.maxFctEval) {
- if (verbose)
- display("Maximum number of function evaluations has exceeded the threshold "
- + this.maxFctEval + ".\nTraining will stop.\n\n");
- return true;
- }
-
- return false;
- }
-
- /**
- * Evaluate the current model on training data set
- * @return model's training accuracy
- */
- private double evaluateModel(DataIndexer indexer, double[] parameters) {
- int[][] contexts = indexer.getContexts();
- float[][] values = indexer.getValues();
- int[] nEventsSeen = indexer.getNumTimesEventsSeen();
- int[] outcomeList = indexer.getOutcomeList();
- int nOutcomes = indexer.getOutcomeLabels().length;
- int nPredLabels = indexer.getPredLabels().length;
-
- int nCorrect = 0;
- int nTotalEvents = 0;
-
- for (int ei = 0; ei < contexts.length; ei++) {
- int[] context = contexts[ei];
- float[] value = values == null? null: values[ei];
-
- double[] probs = new double[nOutcomes];
- QNModel.eval(context, value, probs, nOutcomes, nPredLabels, parameters);
- int outcome = ArrayMath.maxIdx(probs);
- if (outcome == outcomeList[ei]) {
- nCorrect += nEventsSeen[ei];
- }
- nTotalEvents += nEventsSeen[ei];
- }
-
- return (double) nCorrect / nTotalEvents;
- }
-
- /**
- * Shorthand for System.out.print
- */
- private void display(String s) {
- System.out.print(s);
- }
-
- /**
- * Class to store vectors for Hessian approximation update.
- */
- private class QNInfo {
- private double[][] S;
- private double[][] Y;
- private double[] rho;
- private double[] alpha;
- private int m;
-
- private int kCounter;
-
- // constructor
- QNInfo(int numCorrection, int dimension) {
- this.m = numCorrection;
- this.kCounter = 0;
- S = new double[this.m][dimension];
- Y = new double[this.m][dimension];
- rho = new double[this.m];
- alpha = new double[this.m];
- }
-
- public void updateInfo(LineSearchResult lsr) {
- double[] currPoint = lsr.getCurrPoint();
- double[] gradAtCurr = lsr.getGradAtCurr();
- double[] nextPoint = lsr.getNextPoint();
- double[] gradAtNext = lsr.getGradAtNext();
-
- // inner product of S_k and Y_k
- double SYk = 0.0;
-
- // add new ones.
- if (kCounter < m) {
- for (int j = 0; j < dimension; j++) {
- S[kCounter][j] = nextPoint[j] - currPoint[j];
- Y[kCounter][j] = gradAtNext[j] - gradAtCurr[j];
- SYk += S[kCounter][j] * Y[kCounter][j];
- }
- rho[kCounter] = 1.0 / SYk;
- }
- else if (m > 0) {
- // discard oldest vectors and add new ones.
- for (int i = 0; i < m - 1; i++) {
- S[i] = S[i + 1];
- Y[i] = Y[i + 1];
- rho[i] = rho[i + 1];
- }
- for (int j = 0; j < dimension; j++) {
- S[m - 1][j] = nextPoint[j] - currPoint[j];
- Y[m - 1][j] = gradAtNext[j] - gradAtCurr[j];
- SYk += S[m - 1][j] * Y[m - 1][j];
+ double[] probs = new double[nOutcomes];
+ QNModel.eval(context, value, probs, nOutcomes, nPredLabels, parameters);
+ int outcome = ArrayMath.maxIdx(probs);
+ if (outcome == outcomeList[ei]) {
+ nCorrect += nEventsSeen[ei];
}
- rho[m - 1] = 1.0 / SYk;
+ nTotalEvents += nEventsSeen[ei];
}
- if (kCounter < m)
- kCounter++;
+ return (double) nCorrect / nTotalEvents;
}
}
}
\ No newline at end of file
Modified: opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/LineSearchTest.java
URL: http://svn.apache.org/viewvc/opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/LineSearchTest.java?rev=1590233&r1=1590232&r2=1590233&view=diff
==============================================================================
--- opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/LineSearchTest.java (original)
+++ opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/LineSearchTest.java Sat Apr 26 13:02:13 2014
@@ -21,6 +21,7 @@ package opennlp.tools.ml.maxent.quasinew
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
+import opennlp.tools.ml.maxent.quasinewton.LineSearch.LineSearchResult;
import org.junit.Test;
@@ -28,8 +29,8 @@ public class LineSearchTest {
public static final double TOLERANCE = 0.01;
@Test
- public void testLineSearchDeterminesSaneStepLength01() {
- DifferentiableFunction objectiveFunction = new QuadraticFunction();
+ public void testLineSearchDeterminesSaneStepLength1() {
+ Function objectiveFunction = new QuadraticFunction1();
// given
double[] testX = new double[] { 0 };
double testValueX = objectiveFunction.valueAt(testX);
@@ -37,7 +38,7 @@ public class LineSearchTest {
double[] testDirection = new double[] { 1 };
// when
LineSearchResult lsr = LineSearchResult.getInitialObject(testValueX, testGradX, testX);
- LineSearch.doLineSearch(objectiveFunction, testDirection, lsr);
+ LineSearch.doLineSearch(objectiveFunction, testDirection, lsr, 1.0);
double stepSize = lsr.getStepSize();
// then
boolean succCond = TOLERANCE < stepSize && stepSize <= 1;
@@ -45,8 +46,8 @@ public class LineSearchTest {
}
@Test
- public void testLineSearchDeterminesSaneStepLength02() {
- DifferentiableFunction objectiveFunction = new QuadraticFunction02();
+ public void testLineSearchDeterminesSaneStepLength2() {
+ Function objectiveFunction = new QuadraticFunction2();
// given
double[] testX = new double[] { -2 };
double testValueX = objectiveFunction.valueAt(testX);
@@ -54,7 +55,7 @@ public class LineSearchTest {
double[] testDirection = new double[] { 1 };
// when
LineSearchResult lsr = LineSearchResult.getInitialObject(testValueX, testGradX, testX);
- LineSearch.doLineSearch(objectiveFunction, testDirection, lsr);
+ LineSearch.doLineSearch(objectiveFunction, testDirection, lsr, 1.0);
double stepSize = lsr.getStepSize();
// then
boolean succCond = TOLERANCE < stepSize && stepSize <= 1;
@@ -62,8 +63,8 @@ public class LineSearchTest {
}
@Test
- public void testLineSearchFailsWithWrongDirection01() {
- DifferentiableFunction objectiveFunction = new QuadraticFunction();
+ public void testLineSearchFailsWithWrongDirection1() {
+ Function objectiveFunction = new QuadraticFunction1();
// given
double[] testX = new double[] { 0 };
double testValueX = objectiveFunction.valueAt(testX);
@@ -71,7 +72,7 @@ public class LineSearchTest {
double[] testDirection = new double[] { -1 };
// when
LineSearchResult lsr = LineSearchResult.getInitialObject(testValueX, testGradX, testX);
- LineSearch.doLineSearch(objectiveFunction, testDirection, lsr);
+ LineSearch.doLineSearch(objectiveFunction, testDirection, lsr, 1.0);
double stepSize = lsr.getStepSize();
// then
boolean succCond = TOLERANCE < stepSize && stepSize <= 1;
@@ -80,8 +81,8 @@ public class LineSearchTest {
}
@Test
- public void testLineSearchFailsWithWrongDirection02() {
- DifferentiableFunction objectiveFunction = new QuadraticFunction02();
+ public void testLineSearchFailsWithWrongDirection2() {
+ Function objectiveFunction = new QuadraticFunction2();
// given
double[] testX = new double[] { -2 };
double testValueX = objectiveFunction.valueAt(testX);
@@ -89,7 +90,7 @@ public class LineSearchTest {
double[] testDirection = new double[] { -1 };
// when
LineSearchResult lsr = LineSearchResult.getInitialObject(testValueX, testGradX, testX);
- LineSearch.doLineSearch(objectiveFunction, testDirection, lsr);
+ LineSearch.doLineSearch(objectiveFunction, testDirection, lsr, 1.0);
double stepSize = lsr.getStepSize();
// then
boolean succCond = TOLERANCE < stepSize && stepSize <= 1;
@@ -98,8 +99,8 @@ public class LineSearchTest {
}
@Test
- public void testLineSearchFailsWithWrongDirection03() {
- DifferentiableFunction objectiveFunction = new QuadraticFunction();
+ public void testLineSearchFailsWithWrongDirection3() {
+ Function objectiveFunction = new QuadraticFunction1();
// given
double[] testX = new double[] { 4 };
double testValueX = objectiveFunction.valueAt(testX);
@@ -107,7 +108,7 @@ public class LineSearchTest {
double[] testDirection = new double[] { 1 };
// when
LineSearchResult lsr = LineSearchResult.getInitialObject(testValueX, testGradX, testX);
- LineSearch.doLineSearch(objectiveFunction, testDirection, lsr);
+ LineSearch.doLineSearch(objectiveFunction, testDirection, lsr, 1.0);
double stepSize = lsr.getStepSize();
// then
boolean succCond = TOLERANCE < stepSize && stepSize <= 1;
@@ -116,8 +117,8 @@ public class LineSearchTest {
}
@Test
- public void testLineSearchFailsWithWrongDirection04() {
- DifferentiableFunction objectiveFunction = new QuadraticFunction02();
+ public void testLineSearchFailsWithWrongDirection4() {
+ Function objectiveFunction = new QuadraticFunction2();
// given
double[] testX = new double[] { 2 };
double testValueX = objectiveFunction.valueAt(testX);
@@ -125,7 +126,7 @@ public class LineSearchTest {
double[] testDirection = new double[] { 1 };
// when
LineSearchResult lsr = LineSearchResult.getInitialObject(testValueX, testGradX, testX);
- LineSearch.doLineSearch(objectiveFunction, testDirection, lsr);
+ LineSearch.doLineSearch(objectiveFunction, testDirection, lsr, 1.0);
double stepSize = lsr.getStepSize();
// then
boolean succCond = TOLERANCE < stepSize && stepSize <= 1;
@@ -134,8 +135,8 @@ public class LineSearchTest {
}
@Test
- public void testLineSearchFailsAtMinimum01() {
- DifferentiableFunction objectiveFunction = new QuadraticFunction02();
+ public void testLineSearchFailsAtMinimum1() {
+ Function objectiveFunction = new QuadraticFunction2();
// given
double[] testX = new double[] { 0 };
double testValueX = objectiveFunction.valueAt(testX);
@@ -143,7 +144,7 @@ public class LineSearchTest {
double[] testDirection = new double[] { -1 };
// when
LineSearchResult lsr = LineSearchResult.getInitialObject(testValueX, testGradX, testX);
- LineSearch.doLineSearch(objectiveFunction, testDirection, lsr);
+ LineSearch.doLineSearch(objectiveFunction, testDirection, lsr, 1.0);
double stepSize = lsr.getStepSize();
// then
boolean succCond = TOLERANCE < stepSize && stepSize <= 1;
@@ -152,8 +153,8 @@ public class LineSearchTest {
}
@Test
- public void testLineSearchFailsAtMinimum02() {
- DifferentiableFunction objectiveFunction = new QuadraticFunction02();
+ public void testLineSearchFailsAtMinimum2() {
+ Function objectiveFunction = new QuadraticFunction2();
// given
double[] testX = new double[] { 0 };
double testValueX = objectiveFunction.valueAt(testX);
@@ -161,11 +162,51 @@ public class LineSearchTest {
double[] testDirection = new double[] { 1 };
// when
LineSearchResult lsr = LineSearchResult.getInitialObject(testValueX, testGradX, testX);
- LineSearch.doLineSearch(objectiveFunction, testDirection, lsr);
+ LineSearch.doLineSearch(objectiveFunction, testDirection, lsr, 1.0);
double stepSize = lsr.getStepSize();
// then
boolean succCond = TOLERANCE < stepSize && stepSize <= 1;
assertFalse(succCond);
assertEquals(0.0, stepSize, TOLERANCE);
}
+
+ /**
+ * Quadratic function: f(x) = (x-2)^2 + 4
+ */
+ public class QuadraticFunction1 implements Function {
+
+ public double valueAt(double[] x) {
+ // (x-2)^2 + 4;
+ return Math.pow(x[0] - 2, 2) + 4;
+ }
+
+ public double[] gradientAt(double[] x) {
+ // 2(x-2)
+ return new double[] {2 * (x[0]- 2)};
+ }
+
+ public int getDimension() {
+ return 1;
+ }
+ }
+
+ /**
+ * Quadratic function: f(x) = x^2
+ */
+ public class QuadraticFunction2 implements Function {
+
+ public double valueAt(double[] x) {
+ // x^2;
+ return Math.pow(x[0], 2);
+ }
+
+ public double[] gradientAt(double[] x) {
+ // 2x
+ return new double[] {2 * x[0]};
+ }
+
+ public int getDimension() {
+ return 1;
+ }
+ }
}
\ No newline at end of file
Added: opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/NegLogLikelihoodTest.java
URL: http://svn.apache.org/viewvc/opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/NegLogLikelihoodTest.java?rev=1590233&view=auto
==============================================================================
--- opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/NegLogLikelihoodTest.java (added)
+++ opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/NegLogLikelihoodTest.java Sat Apr 26 13:02:13 2014
@@ -0,0 +1,242 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package opennlp.tools.ml.maxent.quasinewton;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertTrue;
+
+import java.io.IOException;
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.Map;
+
+import opennlp.tools.ml.model.DataIndexer;
+import opennlp.tools.ml.model.OnePassRealValueDataIndexer;
+import opennlp.tools.ml.model.RealValueFileEventStream;
+
+import org.junit.Test;
+
+public class NegLogLikelihoodTest {
+ public final double TOLERANCE01 = 1.0E-06;
+ public final double TOLERANCE02 = 1.0E-10;
+
+ @Test
+ public void testDomainDimensionSanity() throws IOException {
+ // given
+ RealValueFileEventStream rvfes1 = new RealValueFileEventStream(
+ "src/test/resources/data/opennlp/maxent/real-valued-weights-training-data.txt", "UTF-8");
+ DataIndexer testDataIndexer = new OnePassRealValueDataIndexer(rvfes1,1);
+ NegLogLikelihood objectFunction = new NegLogLikelihood(testDataIndexer);
+ // when
+ int correctDomainDimension = testDataIndexer.getPredLabels().length
+ * testDataIndexer.getOutcomeLabels().length;
+ // then
+ assertEquals(correctDomainDimension, objectFunction.getDimension());
+ }
+
+ @Test
+ public void testInitialSanity() throws IOException {
+ // given
+ RealValueFileEventStream rvfes1 = new RealValueFileEventStream(
+ "src/test/resources/data/opennlp/maxent/real-valued-weights-training-data.txt", "UTF-8");
+ DataIndexer testDataIndexer = new OnePassRealValueDataIndexer(rvfes1,1);
+ NegLogLikelihood objectFunction = new NegLogLikelihood(testDataIndexer);
+ // when
+ double[] initial = objectFunction.getInitialPoint();
+ // then
+ for (int i = 0; i < initial.length; i++) {
+ assertEquals(0.0, initial[i], TOLERANCE01);
+ }
+ }
+
+ @Test
+ public void testGradientSanity() throws IOException {
+ // given
+ RealValueFileEventStream rvfes1 = new RealValueFileEventStream(
+ "src/test/resources/data/opennlp/maxent/real-valued-weights-training-data.txt", "UTF-8");
+ DataIndexer testDataIndexer = new OnePassRealValueDataIndexer(rvfes1,1);
+ NegLogLikelihood objectFunction = new NegLogLikelihood(testDataIndexer);
+ // when
+ double[] initial = objectFunction.getInitialPoint();
+ double[] gradientAtInitial = objectFunction.gradientAt(initial);
+ // then
+ assertNotNull(gradientAtInitial);
+ }
+
+ @Test
+ public void testValueAtInitialPoint() throws IOException {
+ // given
+ RealValueFileEventStream rvfes1 = new RealValueFileEventStream(
+ "src/test/resources/data/opennlp/maxent/real-valued-weights-training-data.txt", "UTF-8");
+ DataIndexer testDataIndexer = new OnePassRealValueDataIndexer(rvfes1,1);
+ NegLogLikelihood objectFunction = new NegLogLikelihood(testDataIndexer);
+ // when
+ double value = objectFunction.valueAt(objectFunction.getInitialPoint());
+ double expectedValue = 13.86294361;
+ // then
+ assertEquals(expectedValue, value, TOLERANCE01);
+ }
+
+ @Test
+ public void testValueAtNonInitialPoint01() throws IOException {
+ // given
+ RealValueFileEventStream rvfes1 = new RealValueFileEventStream(
+ "src/test/resources/data/opennlp/maxent/real-valued-weights-training-data.txt", "UTF-8");
+ DataIndexer testDataIndexer = new OnePassRealValueDataIndexer(rvfes1,1);
+ NegLogLikelihood objectFunction = new NegLogLikelihood(testDataIndexer);
+ // when
+ double[] nonInitialPoint = new double[] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
+ double value = objectFunction.valueAt(nonInitialPoint);
+ double expectedValue = 13.862943611198894;
+ // then
+ assertEquals(expectedValue, value, TOLERANCE01);
+ }
+
+ @Test
+ public void testValueAtNonInitialPoint02() throws IOException {
+ // given
+ RealValueFileEventStream rvfes1 = new RealValueFileEventStream(
+ "src/test/resources/data/opennlp/maxent/real-valued-weights-training-data.txt", "UTF-8");
+ DataIndexer testDataIndexer = new OnePassRealValueDataIndexer(rvfes1,1);
+ NegLogLikelihood objectFunction = new NegLogLikelihood(testDataIndexer);
+ // when
+ double[] nonInitialPoint = new double[] { 3, 2, 3, 2, 3, 2, 3, 2, 3, 2 };
+ double value = objectFunction.valueAt(dealignDoubleArrayForTestData(nonInitialPoint,
+ testDataIndexer.getPredLabels(),
+ testDataIndexer.getOutcomeLabels()));
+ double expectedValue = 53.163219721099026;
+ // then
+ assertEquals(expectedValue, value, TOLERANCE02);
+ }
+
+ @Test
+ public void testGradientAtInitialPoint() throws IOException {
+ // given
+ RealValueFileEventStream rvfes1 = new RealValueFileEventStream(
+ "src/test/resources/data/opennlp/maxent/real-valued-weights-training-data.txt", "UTF-8");
+ DataIndexer testDataIndexer = new OnePassRealValueDataIndexer(rvfes1,1);
+ NegLogLikelihood objectFunction = new NegLogLikelihood(testDataIndexer);
+ // when
+ double[] gradientAtInitialPoint = objectFunction.gradientAt(objectFunction.getInitialPoint());
+ double[] expectedGradient = new double[] { -9.0, -14.0, -17.0, 20.0, 8.5, 9.0, 14.0, 17.0, -20.0, -8.5 };
+ // then
+ assertTrue(compareDoubleArray(expectedGradient, gradientAtInitialPoint,
+ testDataIndexer, TOLERANCE01));
+ }
+
+ @Test
+ public void testGradientAtNonInitialPoint() throws IOException {
+ // given
+ RealValueFileEventStream rvfes1 = new RealValueFileEventStream(
+ "src/test/resources/data/opennlp/maxent/real-valued-weights-training-data.txt", "UTF-8");
+ DataIndexer testDataIndexer = new OnePassRealValueDataIndexer(rvfes1,1);
+ NegLogLikelihood objectFunction = new NegLogLikelihood(testDataIndexer);
+ // when
+ double[] nonInitialPoint = new double[] { 0.2, 0.5, 0.2, 0.5, 0.2, 0.5, 0.2, 0.5, 0.2, 0.5 };
+ double[] gradientAtNonInitialPoint =
+ objectFunction.gradientAt(dealignDoubleArrayForTestData(nonInitialPoint,
+ testDataIndexer.getPredLabels(),
+ testDataIndexer.getOutcomeLabels()));
+ double[] expectedGradient =
+ new double[] { -12.755042847945553, -21.227127506102434,
+ -72.57790706276435, 38.03525795198456,
+ 15.348650889354925, 12.755042847945557,
+ 21.22712750610244, 72.57790706276438,
+ -38.03525795198456, -15.348650889354925 };
+ // then
+ assertTrue(compareDoubleArray(expectedGradient, gradientAtNonInitialPoint,
+ testDataIndexer, TOLERANCE01));
+ }
+
+ private double[] alignDoubleArrayForTestData(double[] expected,
+ String[] predLabels, String[] outcomeLabels) {
+ double[] aligned = new double[predLabels.length * outcomeLabels.length];
+
+ String[] sortedPredLabels = predLabels.clone();
+ String[] sortedOutcomeLabels = outcomeLabels.clone();
+ Arrays.sort(sortedPredLabels);
+ Arrays.sort(sortedOutcomeLabels);
+
+ Map<String, Integer> invertedPredIndex = new HashMap<String, Integer>();
+ Map<String, Integer> invertedOutcomeIndex = new HashMap<String, Integer>();
+ for (int i = 0; i < predLabels.length; i++) {
+ invertedPredIndex.put(predLabels[i], i);
+ }
+ for (int i = 0; i < outcomeLabels.length; i++) {
+ invertedOutcomeIndex.put(outcomeLabels[i], i);
+ }
+
+ for (int i = 0; i < sortedOutcomeLabels.length; i++) {
+ for (int j = 0; j < sortedPredLabels.length; j++) {
+ aligned[i * sortedPredLabels.length + j] = expected[invertedOutcomeIndex
+ .get(sortedOutcomeLabels[i])
+ * sortedPredLabels.length
+ + invertedPredIndex.get(sortedPredLabels[j])];
+ }
+ }
+ return aligned;
+ }
+
+ private double[] dealignDoubleArrayForTestData(double[] expected,
+ String[] predLabels, String[] outcomeLabels) {
+ double[] dealigned = new double[predLabels.length * outcomeLabels.length];
+
+ String[] sortedPredLabels = predLabels.clone();
+ String[] sortedOutcomeLabels = outcomeLabels.clone();
+ Arrays.sort(sortedPredLabels);
+ Arrays.sort(sortedOutcomeLabels);
+
+ Map<String, Integer> invertedPredIndex = new HashMap<String, Integer>();
+ Map<String, Integer> invertedOutcomeIndex = new HashMap<String, Integer>();
+ for (int i = 0; i < predLabels.length; i++) {
+ invertedPredIndex.put(predLabels[i], i);
+ }
+ for (int i = 0; i < outcomeLabels.length; i++) {
+ invertedOutcomeIndex.put(outcomeLabels[i], i);
+ }
+
+ for (int i = 0; i < sortedOutcomeLabels.length; i++) {
+ for (int j = 0; j < sortedPredLabels.length; j++) {
+ dealigned[invertedOutcomeIndex.get(sortedOutcomeLabels[i])
+ * sortedPredLabels.length
+ + invertedPredIndex.get(sortedPredLabels[j])] = expected[i
+ * sortedPredLabels.length + j];
+ }
+ }
+
+ return dealigned;
+ }
+
+ private boolean compareDoubleArray(double[] expected, double[] actual,
+ DataIndexer indexer, double tolerance)
+ {
+ double[] alignedActual = alignDoubleArrayForTestData(
+ actual, indexer.getPredLabels(), indexer.getOutcomeLabels());
+
+ if (expected.length != alignedActual.length) {
+ return false;
+ }
+
+ for (int i = 0; i < alignedActual.length; i++) {
+ if (Math.abs(alignedActual[i] - expected[i]) > tolerance) {
+ return false;
+ }
+ }
+ return true;
+ }
+}
Propchange: opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/NegLogLikelihoodTest.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/QNMinimizerTest.java
URL: http://svn.apache.org/viewvc/opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/QNMinimizerTest.java?rev=1590233&view=auto
==============================================================================
--- opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/QNMinimizerTest.java (added)
+++ opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/QNMinimizerTest.java Sat Apr 26 13:02:13 2014
@@ -0,0 +1,102 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package opennlp.tools.ml.maxent.quasinewton;
+
+import static java.lang.Math.pow;
+import static org.junit.Assert.assertEquals;
+
+import org.junit.Test;
+
+public class QNMinimizerTest {
+
+ @Test
+ public void testQuadraticFunction() {
+ QNMinimizer minimizer = new QNMinimizer();
+ Function f = new QuadraticFunction();
+ double[] x = minimizer.minimize(f);
+ double minValue = f.valueAt(x);
+
+ assertEquals(x[0], 1.0, 1e-5);
+ assertEquals(x[1], 5.0, 1e-5);
+ assertEquals(minValue, 10.0, 1e-10);
+ }
+
+ @Test
+ public void testRosenbrockFunction() {
+ QNMinimizer minimizer = new QNMinimizer();
+ Function f = new Rosenbrock();
+ double[] x = minimizer.minimize(f);
+ double minValue = f.valueAt(x);
+
+ assertEquals(x[0], 1.0, 1e-5);
+ assertEquals(x[1], 1.0, 1e-5);
+ assertEquals(minValue, 0, 1e-10);
+ }
+
+ /**
+ * Quadratic function: f(x,y) = (x-1)^2 + (y-5)^2 + 10
+ */
+ public class QuadraticFunction implements Function {
+
+ @Override
+ public int getDimension() {
+ return 2;
+ }
+
+ @Override
+ public double valueAt(double[] x) {
+ return pow(x[0] - 1, 2) + pow(x[1] - 5, 2) + 10;
+ }
+
+ @Override
+ public double[] gradientAt(double[] x) {
+ return new double[] { 2 * (x[0] - 1), 2 * (x[1] - 5) };
+ }
+ }
+
+ /**
+ * Rosenbrock function (http://en.wikipedia.org/wiki/Rosenbrock_function)
+ * f(x,y) = (1-x)^2 + 100*(y-x^2)^2
+ * f(x,y) is non-convex and has global minimum at (x,y) = (1,1) where f(x,y) = 0
+ *
+ * f_x = -2*(1-x) - 400*(y-x^2)*x
+ * f_y = 200*(y-x^2)
+ */
+ public class Rosenbrock implements Function {
+
+ @Override
+ public int getDimension() {
+ return 2;
+ }
+
+ @Override
+ public double valueAt(double[] x) {
+ return pow(1-x[0], 2) + 100 * pow(x[1] - pow(x[0], 2), 2);
+ }
+
+ @Override
+ public double[] gradientAt(double[] x) {
+ double[] g = new double[2];
+ g[0] = -2*(1-x[0]) - 400 * (x[1] - pow(x[0], 2)) * x[0];
+ g[1] = 200 * (x[1] - pow(x[0], 2));
+ return g;
+ }
+
+ }
+}
Propchange: opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/QNMinimizerTest.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Modified: opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/QNPrepAttachTest.java
URL: http://svn.apache.org/viewvc/opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/QNPrepAttachTest.java?rev=1590233&r1=1590232&r2=1590233&view=diff
==============================================================================
--- opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/QNPrepAttachTest.java (original)
+++ opennlp/trunk/opennlp-tools/src/test/java/opennlp/tools/ml/maxent/quasinewton/QNPrepAttachTest.java Sat Apr 26 13:02:13 2014
@@ -38,40 +38,73 @@ public class QNPrepAttachTest {
@Test
public void testQNOnPrepAttachData() throws IOException {
AbstractModel model =
- new QNTrainer(true).trainModel(100,
- new TwoPassDataIndexer(createTrainingStream(), 1));
+ new QNTrainer(true).trainModel(
+ 100, new TwoPassDataIndexer(createTrainingStream(), 1));
- testModel(model, 0.8165387472146571);
+ testModel(model, 0.8229759841544937);
}
@Test
- public void testQNOnPrepAttachDataWithParams() throws IOException {
+ public void testQNOnPrepAttachDataWithParamsDefault() throws IOException {
+
+ Map<String, String> trainParams = new HashMap<String, String>();
+ trainParams.put(AbstractTrainer.ALGORITHM_PARAM, QNTrainer.MAXENT_QN_VALUE);
+
+ MaxentModel model = TrainerFactory.getEventTrainer(trainParams, null)
+ .train(createTrainingStream());
+
+ testModel(model, 0.8150532309977717);
+ }
+
+ @Test
+ public void testQNOnPrepAttachDataWithElasticNetParams() throws IOException {
Map<String, String> trainParams = new HashMap<String, String>();
trainParams.put(AbstractTrainer.ALGORITHM_PARAM, QNTrainer.MAXENT_QN_VALUE);
trainParams.put(AbstractEventTrainer.DATA_INDEXER_PARAM,
AbstractEventTrainer.DATA_INDEXER_TWO_PASS_VALUE);
trainParams.put(AbstractTrainer.CUTOFF_PARAM, Integer.toString(1));
- // use L2-cost higher than the default
- trainParams.put(QNTrainer.L2COST_PARAM, Double.toString(2.0));
+ trainParams.put(QNTrainer.L1COST_PARAM, Double.toString(0.25));
+ trainParams.put(QNTrainer.L2COST_PARAM, Double.toString(1.0));
MaxentModel model = TrainerFactory.getEventTrainer(trainParams, null)
.train(createTrainingStream());
- testModel(model, 0.8202525377568705);
+ testModel(model, 0.8229759841544937);
}
@Test
- public void testQNOnPrepAttachDataWithParamsDefault() throws IOException {
+ public void testQNOnPrepAttachDataWithL1Params() throws IOException {
Map<String, String> trainParams = new HashMap<String, String>();
trainParams.put(AbstractTrainer.ALGORITHM_PARAM, QNTrainer.MAXENT_QN_VALUE);
+ trainParams.put(AbstractEventTrainer.DATA_INDEXER_PARAM,
+ AbstractEventTrainer.DATA_INDEXER_TWO_PASS_VALUE);
+ trainParams.put(AbstractTrainer.CUTOFF_PARAM, Integer.toString(1));
+ trainParams.put(QNTrainer.L1COST_PARAM, Double.toString(1.0));
+ trainParams.put(QNTrainer.L2COST_PARAM, Double.toString(0));
MaxentModel model = TrainerFactory.getEventTrainer(trainParams, null)
.train(createTrainingStream());
- testModel(model, 0.8153008170339193);
+ testModel(model, 0.8180242634315424);
}
+ @Test
+ public void testQNOnPrepAttachDataWithL2Params() throws IOException {
+
+ Map<String, String> trainParams = new HashMap<String, String>();
+ trainParams.put(AbstractTrainer.ALGORITHM_PARAM, QNTrainer.MAXENT_QN_VALUE);
+ trainParams.put(AbstractEventTrainer.DATA_INDEXER_PARAM,
+ AbstractEventTrainer.DATA_INDEXER_TWO_PASS_VALUE);
+ trainParams.put(AbstractTrainer.CUTOFF_PARAM, Integer.toString(1));
+ trainParams.put(QNTrainer.L1COST_PARAM, Double.toString(0));
+ trainParams.put(QNTrainer.L2COST_PARAM, Double.toString(1.0));
+
+ MaxentModel model = TrainerFactory.getEventTrainer(trainParams, null)
+ .train(createTrainingStream());
+
+ testModel(model, 0.8227283981183461);
+ }
}