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

SHOGUN Machine Learning Toolbox - Documentation