SHOGUN
4.2.0
Main Page
Related Pages
Modules
Classes
Files
File List
File Members
All
Classes
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Friends
Macros
Modules
Pages
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
config.h
SHOGUN
Machine Learning Toolbox - Documentation