summaryrefslogtreecommitdiff
path: root/gi/posterior-regularisation/prjava/src/optimization/projections
diff options
context:
space:
mode:
Diffstat (limited to 'gi/posterior-regularisation/prjava/src/optimization/projections')
-rw-r--r--gi/posterior-regularisation/prjava/src/optimization/projections/BoundsProjection.java104
-rw-r--r--gi/posterior-regularisation/prjava/src/optimization/projections/Projection.java72
-rw-r--r--gi/posterior-regularisation/prjava/src/optimization/projections/SimplexProjection.java127
3 files changed, 303 insertions, 0 deletions
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;
+ }
+
+}