From 7f69c868c41e4b36eecf9d3b1dc22f3f3aa1540c Mon Sep 17 00:00:00 2001 From: desaicwtf Date: Fri, 9 Jul 2010 16:59:55 +0000 Subject: add optimization library source code git-svn-id: https://ws10smt.googlecode.com/svn/trunk@204 ec762483-ff6d-05da-a07a-a48fb63a330f --- .../optimization/projections/BoundsProjection.java | 104 +++++++++++++++++ .../src/optimization/projections/Projection.java | 72 ++++++++++++ .../projections/SimplexProjection.java | 127 +++++++++++++++++++++ 3 files changed, 303 insertions(+) create mode 100644 gi/posterior-regularisation/prjava/src/optimization/projections/BoundsProjection.java create mode 100644 gi/posterior-regularisation/prjava/src/optimization/projections/Projection.java create mode 100644 gi/posterior-regularisation/prjava/src/optimization/projections/SimplexProjection.java (limited to 'gi/posterior-regularisation/prjava/src/optimization/projections') diff --git a/gi/posterior-regularisation/prjava/src/optimization/projections/BoundsProjection.java b/gi/posterior-regularisation/prjava/src/optimization/projections/BoundsProjection.java new file mode 100644 index 00000000..0429d531 --- /dev/null +++ b/gi/posterior-regularisation/prjava/src/optimization/projections/BoundsProjection.java @@ -0,0 +1,104 @@ +package optimization.projections; + + +import java.util.Random; + +import optimization.util.MathUtils; +import optimization.util.MatrixOutput; + +/** + * Implements a projection into a box set defined by a and b. + * If either a or b are infinity then that bound is ignored. + * @author javg + * + */ +public class BoundsProjection extends Projection{ + + double a,b; + boolean ignoreA = false; + boolean ignoreB = false; + public BoundsProjection(double lowerBound, double upperBound) { + if(Double.isInfinite(lowerBound)){ + this.ignoreA = true; + }else{ + this.a =lowerBound; + } + if(Double.isInfinite(upperBound)){ + this.ignoreB = true; + }else{ + this.b =upperBound; + } + } + + + + /** + * Projects into the bounds + * a <= x_i <=b + */ + public void project(double[] original){ + for (int i = 0; i < original.length; i++) { + if(!ignoreA && original[i] < a){ + original[i] = a; + }else if(!ignoreB && original[i]>b){ + original[i]=b; + } + } + } + + /** + * Generates a random number between a and b. + */ + + Random r = new Random(); + + public double[] samplePoint(int numParams) { + double[] point = new double[numParams]; + for (int i = 0; i < point.length; i++) { + double rand = r.nextDouble(); + if(ignoreA && ignoreB){ + //Use const to avoid number near overflow + point[i] = rand*(1.E100+1.E100)-1.E100; + }else if(ignoreA){ + point[i] = rand*(b-1.E100)-1.E100; + }else if(ignoreB){ + point[i] = rand*(1.E100-a)-a; + }else{ + point[i] = rand*(b-a)-a; + } + } + return point; + } + + public static void main(String[] args) { + BoundsProjection sp = new BoundsProjection(0,Double.POSITIVE_INFINITY); + + + MatrixOutput.printDoubleArray(sp.samplePoint(3), "random 1"); + MatrixOutput.printDoubleArray(sp.samplePoint(3), "random 2"); + MatrixOutput.printDoubleArray(sp.samplePoint(3), "random 3"); + + double[] d = {-1.1,1.2,1.4}; + double[] original = d.clone(); + MatrixOutput.printDoubleArray(d, "before"); + + sp.project(d); + MatrixOutput.printDoubleArray(d, "after"); + System.out.println("Test projection: " + sp.testProjection(original, d)); + } + + double epsilon = 1.E-10; + public double[] perturbePoint(double[] point, int parameter){ + double[] newPoint = point.clone(); + if(!ignoreA && MathUtils.almost(point[parameter], a)){ + newPoint[parameter]+=epsilon; + }else if(!ignoreB && MathUtils.almost(point[parameter], b)){ + newPoint[parameter]-=epsilon; + }else{ + newPoint[parameter]-=epsilon; + } + return newPoint; + } + + +} diff --git a/gi/posterior-regularisation/prjava/src/optimization/projections/Projection.java b/gi/posterior-regularisation/prjava/src/optimization/projections/Projection.java new file mode 100644 index 00000000..b5a9f92f --- /dev/null +++ b/gi/posterior-regularisation/prjava/src/optimization/projections/Projection.java @@ -0,0 +1,72 @@ +package optimization.projections; + +import optimization.util.MathUtils; +import optimization.util.MatrixOutput; +import util.ArrayMath; +import util.Printing; + + + +public abstract class Projection { + + + public abstract void project(double[] original); + + + /** + * From the projection theorem "Non-Linear Programming" page + * 201 fact 2. + * + * Given some z in R, and a vector x* in X; + * x* = z+ iif for all x in X + * (z-x*)'(x-x*) <= 0 where 0 is when x*=x + * See figure 2.16 in book + * + * @param original + * @param projected + * @return + */ + public boolean testProjection(double[] original, double[] projected){ + double[] original1 = original.clone(); + //System.out.println(Printing.doubleArrayToString(original1, null, "original")); + //System.out.println(Printing.doubleArrayToString(projected, null, "projected")); + MathUtils.minusEquals(original1, projected, 1); + //System.out.println(Printing.doubleArrayToString(original1, null, "minus1")); + for(int i = 0; i < 10; i++){ + double[] x = samplePoint(original.length); + // System.out.println(Printing.doubleArrayToString(x, null, "sample")); + //If the same this returns zero so we are there. + MathUtils.minusEquals(x, projected, 1); + // System.out.println(Printing.doubleArrayToString(x, null, "minus2")); + double dotProd = MathUtils.dotProduct(original1, x); + + // System.out.println("dot " + dotProd); + if(dotProd > 0) return false; + } + + //Perturbs the point a bit in all possible directions + for(int i = 0; i < original.length; i++){ + double[] x = perturbePoint(projected,i); + // System.out.println(Printing.doubleArrayToString(x, null, "perturbed")); + //If the same this returns zero so we are there. + MathUtils.minusEquals(x, projected, 1); + // System.out.println(Printing.doubleArrayToString(x, null, "minus2")); + double dotProd = MathUtils.dotProduct(original1, x); + + // System.out.println("dot " + dotProd); + if(dotProd > 0) return false; + } + + + + return true; + } + + //Samples a point from the constrained set + public abstract double[] samplePoint(int dimensions); + + //Perturbs a point a bit still leaving it at the constraints set + public abstract double[] perturbePoint(double[] point, int parameter); + + +} diff --git a/gi/posterior-regularisation/prjava/src/optimization/projections/SimplexProjection.java b/gi/posterior-regularisation/prjava/src/optimization/projections/SimplexProjection.java new file mode 100644 index 00000000..eec11bcf --- /dev/null +++ b/gi/posterior-regularisation/prjava/src/optimization/projections/SimplexProjection.java @@ -0,0 +1,127 @@ +package optimization.projections; + + + +import java.util.Random; + +import optimization.util.MathUtils; +import optimization.util.MatrixOutput; + +public class SimplexProjection extends Projection{ + + double scale; + public SimplexProjection(double scale) { + this.scale = scale; + } + + /** + * projects the numbers of the array + * into a simplex of size. + * We follow the description of the paper + * "Efficient Projetions onto the l1-Ball + * for learning in high dimensions" + */ + public void project(double[] original){ + double[] ds = new double[original.length]; + System.arraycopy(original, 0, ds, 0, ds.length); + //If sum is smaller then zero then its ok + for (int i = 0; i < ds.length; i++) ds[i] = ds[i]>0? ds[i]:0; + double sum = MathUtils.sum(ds); + if (scale - sum >= -1.E-10 ){ + System.arraycopy(ds, 0, original, 0, ds.length); + //System.out.println("Not projecting"); + return; + } + //System.out.println("projecting " + sum + " scontraints " + scale); + util.Array.sortDescending(ds); + double currentSum = 0; + double previousTheta = 0; + double theta = 0; + for (int i = 0; i < ds.length; i++) { + currentSum+=ds[i]; + theta = (currentSum-scale)/(i+1); + if(ds[i]-theta <= 0){ + break; + } + previousTheta = theta; + } + //DEBUG + if(previousTheta < 0){ + System.out.println("Simple Projection: Theta is smaller than zero: " + previousTheta); + System.exit(-1); + } + for (int i = 0; i < original.length; i++) { + original[i] = Math.max(original[i]-previousTheta, 0); + } + } + + + + + + + /** + * Samples a point from the simplex of scale. Just sample + * random number from 0-scale and then if + * their sum is bigger then sum make them normalize. + * This is probably not sampling uniformly from the simplex but it is + * enough for our goals in here. + */ + Random r = new Random(); + public double[] samplePoint(int dimensions) { + double[] newPoint = new double[dimensions]; + double sum =0; + for (int i = 0; i < newPoint.length; i++) { + double rand = r.nextDouble()*scale; + sum+=rand; + newPoint[i]=rand; + } + //Normalize + if(sum > scale){ + for (int i = 0; i < newPoint.length; i++) { + newPoint[i]=scale*newPoint[i]/sum; + } + } + return newPoint; + } + + public static void main(String[] args) { + SimplexProjection sp = new SimplexProjection(1); + + + double[] point = sp.samplePoint(3); + MatrixOutput.printDoubleArray(point , "random 1 sum:" + MathUtils.sum(point)); + point = sp.samplePoint(3); + MatrixOutput.printDoubleArray(point , "random 2 sum:" + MathUtils.sum(point)); + point = sp.samplePoint(3); + MatrixOutput.printDoubleArray(point , "random 3 sum:" + MathUtils.sum(point)); + + double[] d = {0,1.1,-10}; + double[] original = d.clone(); + MatrixOutput.printDoubleArray(d, "before"); + + sp.project(d); + MatrixOutput.printDoubleArray(d, "after"); + System.out.println("Test projection: " + sp.testProjection(original, d)); + + } + + + double epsilon = 1.E-10; + public double[] perturbePoint(double[] point, int parameter){ + double[] newPoint = point.clone(); + if(MathUtils.almost(MathUtils.sum(point), scale)){ + newPoint[parameter]-=epsilon; + } + else if(point[parameter]==0){ + newPoint[parameter]+=epsilon; + }else if(MathUtils.almost(point[parameter], scale)){ + newPoint[parameter]-=epsilon; + } + else{ + newPoint[parameter]-=epsilon; + } + return newPoint; + } + +} -- cgit v1.2.3