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

SHOGUN Machine Learning Toolbox - Documentation