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

SHOGUN Machine Learning Toolbox - Documentation