summaryrefslogtreecommitdiff
path: root/gi/posterior-regularisation/prjava/src/optimization/projections/SimplexProjection.java
blob: f22afcaf98070722bb460893ff13c75de193089c (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
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 < -1e-10){
				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;
	}
	
}