SHOGUN  3.2.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
overlapping.h
Go to the documentation of this file.
1 /* This program is free software: you can redistribute it and/or modify
2  * it under the terms of the GNU General Public License as published by
3  * the Free Software Foundation, either version 3 of the License, or
4  * (at your option) any later version.
5  *
6  * This program is distributed in the hope that it will be useful,
7  * but WITHOUT ANY WARRANTY; without even the implied warranty of
8  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
9  * GNU General Public License for more details.
10  *
11  * You should have received a copy of the GNU General Public License
12  * along with this program. If not, see <http://www.gnu.org/licenses/>.
13  *
14  * Copyright (C) 2009 - 2012 Jun Liu and Jieping Ye
15  */
16 
17 #ifndef OVERLAPPING_SLEP
18 #define OVERLAPPING_SLEP
19 
20 #include <shogun/lib/config.h>
21 
22 #include <stdio.h>
23 #include <stdlib.h>
24 #include <math.h>
25 #include <string.h>
26 
27 
28 /*
29  * -------------------------------------------------------------------
30  * Function and parameter
31  * -------------------------------------------------------------------
32  *
33  * In this file, we focus solving the following problem
34  *
35  * 1/2 \|x-v\|^2 + \lambda_1 \|x\|_1 + \lambda_2 \sum w_i \|x_{G_i}\|,
36  *
37  * where x and v are of dimension p,
38  * w >0, and G_i contains the indices for the i-th group
39  *
40  * The file is implemented in the following in Matlab:
41  *
42  * x=overlapping(v, p, g, lambda1, lambda2, w, G, Y, maxIter, flag, tol);
43  *
44  * x and v are vectors of dimension p
45  *
46  * g denotes the number of groups
47  *
48  * lambda1 and labmda2 are non-negative regularization paramter
49  *
50  * G is a vector containing the indices for the groups
51  * G_1, G_2, ..., G_g
52  *
53  * w is a 3xg matrix
54  * w(1,i) contains the starting index of the i-th group in G
55  * w(2,i) contains the ending index of the i-th group in G
56  * w(3,i) contains the weight for the i-th group
57  *
58  * Y is the dual of \|x_{G_i}\|, it is of the same size as G
59  *
60  * maxIter is the maximal number of iteration
61  *
62  * flag=0, we apply the pure projected gradient descent
63  * (forward and backward line search is used)
64  *
65  * flag=1, we apply the projected gradient descent with restart
66  *
67  * in the future, we may apply the accelerated gradient descent
68  * with adaptive line search (see our KDD'09 paper) with other "flag"
69  *
70  *
71  * Note:
72  *
73  * 1. One should ensure w(2,i)-w(1,i)+1=|G_i|.
74  * !! The program does not check w(2,i)-w(1,i)+1=|G_i|.!!
75  *
76  * 2. The index in G and w starts from 0
77  *
78  * -------------------------------------------------------------------
79  * History:
80  * -------------------------------------------------------------------
81  *
82  * Composed by Jun Liu on May 17, 2010
83  *
84  * For any question or suggestion, please email j.liu@asu.edu or
85  * jun.liu.80@gmail.com
86  *
87  */
88 
89 
90 /*
91  * --------------------------------------------------------------------
92  * Identifying some zero Entries
93  * --------------------------------------------------------------------
94  *
95  * lambda1, lambda2 should be non-negative
96  *
97  * v is the vector of size p to be projected
98  *
99  *
100  * zeroGroupFlag is a vector of size g
101  *
102  * zeroGroupFlag[i]=0 denotes that the corresponding group is definitely zero
103  * zeroGroupFlag[i]=1 denotes that the corresponding group is (possibly) nonzero
104  *
105  *
106  * u is a vector of size p
107  *
108  *
109  * entrySignFlag is a vector of size p
110  *
111  * entrySignFlag[i]=0 denotes that the corresponding entry is definitely zero
112  * entrySignFlag[i]=1 denotes that the corresponding entry is (possibly) positive
113  * entrySignFlag[i]=-1 denotes that the corresponding entry is (possibly) negative
114  *
115  */
116 void identifySomeZeroEntries(double * u, int * zeroGroupFlag, int *entrySignFlag,
117  int *pp, int *gg,
118  double *v, double lambda1, double lambda2,
119  int p, int g, double * w, double *G);
120 
121 /*
122  *
123  * function: xFromY
124  *
125  * compute x=max(u-Y * e, 0);
126  *
127  * xFromY(x, y, u, Y, p, g, zeroGroupFlag, G, w);
128  *
129  * y=u-Y * e - max( u - Y * e, 0)
130  *
131  */
132 void xFromY(double *x, double *y,
133  double *u, double *Y,
134  int p, int g, int *zeroGroupFlag,
135  double *G, double *w);
136 
137 /*
138  *
139  * function: YFromx
140  *
141  * compute Y=subgradient(x)
142  *
143  * YFromx(Y, xnew, Ynew, lambda2, g, zeroGroupFlag, G, w);
144  *
145  * The idea is that, if x_{G_i} is nonzero,
146  * we compute Y^i as x_{G_i}/ \|x_{G_i}\| * lambda2 * w[3*i+2]
147  * otherwise
148  * Y^i=Ynew^i
149  *
150  */
151 void YFromx(double *Y,
152  double *xnew, double *Ynew,
153  double lambda2, int g, int *zeroGroupFlag,
154  double *G, double *w);
155 
156 /*
157  * function: dualityGap
158  *
159  * compute the duality gap for the approximate solution (x, Y)
160  *
161  * Meanwhile, we compute
162  *
163  * penalty2=\sum_{i=1}^g w_i \|x_{G_i}\|
164  *
165  */
166 void dualityGap(double *gap, double *penalty2,
167  double *x, double *Y, int g, int *zeroGroupFlag,
168  double *G, double *w, double lambda2);
169 
170 /*
171  * we solve the proximal opeartor:
172  *
173  * 1/2 \|x-v\|^2 + \lambda_1 \|x\|_1 + \lambda_2 \sum w_i \|x_{G_i}\|
174  *
175  * See the description of the variables in the beginning of this file
176  *
177  * x is the primal variable, each of its entry is non-negative
178  *
179  * Y is the dual variable, each of its entry should be non-negative
180  *
181  * flag =0: no restart
182  * flag =1; restart
183  *
184  * tol: the precision parameter
185  *
186  * The following code apply the projected gradient descent method
187  *
188  */
189 void overlapping_gd(double *x, double *gap, double *penalty2,
190  double *v, int p, int g, double lambda1, double lambda2,
191  double *w, double *G, double *Y, int maxIter, int flag, double tol);
192 
193 /*
194  *
195  * do a gradient descent step based (x, Y) to get (xnew, Ynew)
196  *
197  * (x, Y) is known. Here we do a line search for determining the value of L
198  *
199  * gradientDescentStep(double *xnew, double *Ynew,
200  double *LL, double *u,
201  double *x, double *Y, int p, int g, int * zeroGroupFlag,
202  double *G, double *w)
203  *
204  */
205 void gradientDescentStep(double *xnew, double *Ynew,
206  double *LL, double *u, double *y, int *entrySignFlag, double lambda2,
207  double *x, double *Y, int p, int g, int * zeroGroupFlag,
208  double *G, double *w);
209 
210 /*
211  *
212  * we use the accelerated gradient descent
213  *
214  */
215 void overlapping_agd(double *x, double *gap, double *penalty2,
216  double *v, int p, int g, double lambda1, double lambda2,
217  double *w, double *G, double *Y, int maxIter, int flag, double tol);
218 
219 /*
220  * This is main function for the projection
221  *
222  * It calls overlapping_gd and overlapping_agd based on flag
223  *
224  *
225  */
226 void overlapping(double *x, double *gap, double *penalty2,
227  double *v, int p, int g, double lambda1, double lambda2,
228  double *w, double *G, double *Y, int maxIter, int flag, double tol);
229 
230 #endif /* ----- #ifndef OVERLAPPING_SLEP ----- */

SHOGUN Machine Learning Toolbox - Documentation