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