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

SHOGUN Machine Learning Toolbox - Documentation