SHOGUN  4.1.0
general_altra.h
Go to the documentation of this file.
1 /* This program is free software: you can redistribute it and/or modify
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 GENERAL_ALTRA_SLEP
18 #define GENERAL_ALTRA_SLEP
19
20 #include <shogun/lib/config.h>
21
22
23 /*
24  * Important Notice: September 20, 2010
25  *
26  * In this head file, we deal with the case that the features might not be well ordered.
27  *
28  * If the features in the tree strucutre are well ordered, i.e., the indices of the left nodes is always less
29  * than the right nodes, please refer to "altra.h".
30  *
31  * The advantage of "altra.h" is that, we donot need to use an explicit
32  * variable for recording the indices.
33  *
34  *
35  */
36
37 /*
38  * -------------------------------------------------------------------
39  * Functions and parameter
40  * -------------------------------------------------------------------
41  *
42  * general_altra solves the following problem
43  *
44  * 1/2 \|x-v\|^2 + \sum \lambda_i \|x_{G_i}\|,
45  *
46  * where x and v are of dimension n,
47  * \lambda_i >=0, and G_i's follow the tree structure
48  *
49  * It is implemented in Matlab as follows:
50  *
51  * x=general_altra(v, n, G, ind, nodes);
52  *
53  * G contains the indices of the groups.
54  * It is a row vector. Its length equals to \sum_i \|G_i\|.
55  * If all the entries are penalized with L1 norm,
56  * its length is \sum_i \|G_i\| - n.
57  *
58  * ind is a 3 x nodes matrix.
59  * Each column corresponds to a node.
60  *
61  * The first element of each column is the starting index,
62  * the second element of each column is the ending index
63  * the third element of each column corrreponds to \lambbda_i.
64  *
65  *
66  *
67  * The following example shows how G and ind works:
68  *
69  * G={ {1, 2}, {4, 5}, {3, 6}, {7, 8},
70  * {1, 2, 3, 6}, {4, 5, 7, 8},
71  * {1, 2, 3, 4, 5, 6, 7, 8} }.
72  *
73  * ind={ [1, 2, 100]', [3, 4, 100]', [5, 6, 100]', [7, 8, 100]',
74  * [9, 12, 100]', [13, 16, 100]', [17, 24, 100]' }
75  *
76  * where "100" denotes the weight for the nodes.
77  *
78  *
79  *
80  * -------------------------------------------------------------------
81  * Notices:
82  * -------------------------------------------------------------------
83  *
84  * 1. The features in the tree might not be well ordered. Otherwise, you are
85  * suggested to use "altra.h".
86  *
87  * 2. When each elements of x are penalized via the same L1
88  * (equivalent to the L2 norm) parameter, one can simplify the input
89  * by specifying
90  * the "first" column of ind as (-1, -1, lambda)
91  *
92  * In this case, we treat it as a single "super" node. Thus in the value
93  * nodes, we only count it once.
94  *
95  * 3. The values in "ind" are in [1,length(G)].
96  *
97  * 4. The third element of each column should be positive. The program does
98  * not check the validity of the parameter.
99  *
100  * 5. The values in G should be within [1, n].
101  *
102  * It is still valid to use the zero regularization parameter.
103  * In this case, the program does not change the values of
104  * correponding indices.
105  *
106  *
107  * -------------------------------------------------------------------
108 * History:
109 * -------------------------------------------------------------------
110 *
111 * Composed by Jun Liu on April 20, 2010
112 *
113 * For any question or suggestion, please email j.liu@asu.edu.
114 *
115 */
116 void general_altra(double *x, double *v, int n, double *G, double *ind, int nodes, double mult=1.0);
117
118 /*
119  * altra_mt is a generalization of altra to the
120  *
121  * multi-task learning scenario (or equivalently the multi-class case)
122  *
123  * altra_mt(X, V, n, k, G, ind, nodes);
124  *
125  * It applies altra for each row (1xk) of X and V
126  *
127  */
128 void general_altra_mt(double *X, double *V, int n, int k, double *G, double *ind, int nodes, double mult=1.0);
129
130 /*
131  * compute
132  * lambda2_max=general_computeLambda2Max(x,n,G, ind,nodes);
133  *
134  * compute the 2 norm of each group, which is divided by the ind(3,:),
135  * then the maximum value is returned
136  */
137 /*
138  *This function does not consider the case ind={[-1, -1, 100]',...}
139  *
140  *This functions is not used currently.
141  */
142 void general_computeLambda2Max(double *lambda2_max, double *x, int n, double *G, double *ind, int nodes);
143
144 /*
145  * -------------------------------------------------------------------
146  * Function and parameter
147  * -------------------------------------------------------------------
148  *
149  * treeNorm compute
150  *
151  * \sum \lambda_i \|x_{G_i}\|,
152  *
153  * where x is of dimension n,
154  * \lambda_i >=0, and G_i's follow the tree structure
155  *
156  * The file is implemented in the following in Matlab:
157  *
158  * tree_norm=general_treeNorm(x, n, G, ind,nodes);
159  */
160 double general_treeNorm(double *x, int ldx, int n, double *G, double *ind, int nodes);
161
162 /*
163  * -------------------------------------------------------------------
164  * Function and parameter
165  * -------------------------------------------------------------------
166  *
167  * findLambdaMax compute
168  *
169  * the lambda_{max} that achieves a zero solution for
170  *
171  * min 1/2 \|x-v\|^2 + \lambda_{\max} * \sum w_i \|x_{G_i}\|,
172  *
173  * where x is of dimension n,
174  * w_i >=0, and G_i's follow the tree structure
175  *
176  * The file is implemented in the following in Matlab:
177  *
178  * lambdaMax=general_findLambdaMax(v, n, G, ind,nodes);
179  */
180 double general_findLambdaMax(double *v, int n, double *G, double *ind, int nodes);
181
182 /*
183  * findLambdaMax_mt is a generalization of findLambdaMax to the
184  *
185  * multi-task learning scenario (or equivalently the multi-class case)
186  *
187  * lambdaMax=general_findLambdaMax_mt(X, V, n, k, G, ind, nodes);
188  *
189  * It applies findLambdaMax for each row (1xk) of X and V
190  *
191  */
192 double general_findLambdaMax_mt(double *V, int n, int k, double *G, double *ind, int nodes);
193 #endif /* ----- #ifndef GENERAL_ALTRA_SLEP ----- */
194
double general_treeNorm(double *x, int ldx, int n, double *G, double *ind, int nodes)
double general_findLambdaMax(double *v, int n, double *G, double *ind, int nodes)
double general_findLambdaMax_mt(double *V, int n, int k, double *G, double *ind, int nodes)
void general_altra(double *x, double *v, int n, double *G, double *ind, int nodes, double mult=1.0)
void general_altra_mt(double *X, double *V, int n, int k, double *G, double *ind, int nodes, double mult=1.0)
void general_computeLambda2Max(double *lambda2_max, double *x, int n, double *G, double *ind, int nodes)

SHOGUN Machine Learning Toolbox - Documentation