00001 /* This program is free software: you can redistribute it and/or modify 00002 * it under the terms of the GNU General Public License as published by 00003 * the Free Software Foundation, either version 3 of the License, or 00004 * (at your option) any later version. 00005 * 00006 * This program is distributed in the hope that it will be useful, 00007 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00008 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00009 * GNU General Public License for more details. 00010 * 00011 * You should have received a copy of the GNU General Public License 00012 * along with this program. If not, see <http://www.gnu.org/licenses/>. 00013 * 00014 * Copyright (C) 2009 - 2012 Jun Liu and Jieping Ye 00015 */ 00016 00017 #ifndef ALTRA_SLEP 00018 #define ALTRA_SLEP 00019 00020 #include <stdio.h> 00021 #include <stdlib.h> 00022 #include <math.h> 00023 #include <string.h> 00024 00025 00026 /* 00027 * Important Notice: September 20, 2010 00028 * 00029 * In this head file, we assume that the features in the tree strucutre 00030 * are well ordered. That is to say, the indices of the left nodes is always less 00031 * than the right nodes. Ideally, this can be achieved by reordering the features. 00032 * 00033 * The advantage of this ordered features is that, we donot need to use an explicit 00034 * variable for recording the indices. 00035 * 00036 * To deal with the more general case when the features might not be well ordered, 00037 * we provide the functions in the head file "general_altra.h". Compared with the files in this head file, 00038 * we need an additional parameter G, which contains the indices of the nodes. 00039 * 00040 * 00041 */ 00042 00043 /* 00044 * ------------------------------------------------------------------- 00045 * Functions and parameter 00046 * ------------------------------------------------------------------- 00047 * 00048 * altra solves the following problem 00049 * 00050 * 1/2 \|x-v\|^2 + \sum \lambda_i \|x_{G_i}\|, 00051 * 00052 * where x and v are of dimension n, 00053 * \lambda_i >=0, and G_i's follow the tree structure 00054 * 00055 * It is implemented in Matlab as follows: 00056 * 00057 * x=altra(v, n, ind, nodes); 00058 * 00059 * ind is a 3 x nodes matrix. 00060 * Each column corresponds to a node. 00061 * 00062 * The first element of each column is the starting index, 00063 * the second element of each column is the ending index 00064 * the third element of each column corrreponds to \lambbda_i. 00065 * 00066 * ------------------------------------------------------------------- 00067 * Notices: 00068 * ------------------------------------------------------------------- 00069 * 00070 * 1. The nodes in the parameter "ind" should be given in the 00071 * either 00072 * the postordering of depth-first traversal 00073 * or 00074 * the reverse breadth-first traversal. 00075 * 00076 * 2. When each elements of x are penalized via the same L1 00077 * (equivalent to the L2 norm) parameter, one can simplify the input 00078 * by specifying 00079 * the "first" column of ind as (-1, -1, lambda) 00080 * 00081 * In this case, we treat it as a single "super" node. Thus in the value 00082 * nodes, we only count it once. 00083 * 00084 * 3. The values in "ind" are in [1,n]. 00085 * 00086 * 4. The third element of each column should be positive. The program does 00087 * not check the validity of the parameter. 00088 * 00089 * It is still valid to use the zero regularization parameter. 00090 * In this case, the program does not change the values of 00091 * correponding indices. 00092 * 00093 * 00094 * ------------------------------------------------------------------- 00095 * History: 00096 * ------------------------------------------------------------------- 00097 * 00098 * Composed by Jun Liu on April 20, 2010 00099 * 00100 * For any question or suggestion, please email j.liu@asu.edu. 00101 * 00102 */ 00103 void altra(double *x, double *v, int n, double *ind, int nodes, double mult=1.0); 00104 00105 /* 00106 * altra_mt is a generalization of altra to the 00107 * 00108 * multi-task learning scenario (or equivalently the multi-class case) 00109 * 00110 * altra_mt(X, V, n, k, ind, nodes); 00111 * 00112 * It applies altra for each row (1xk) of X and V 00113 * 00114 */ 00115 void altra_mt(double *X, double *V, int n, int k, double *ind, int nodes, double mult=1.0); 00116 00117 /* 00118 * compute 00119 * lambda2_max=computeLambda2Max(x,n,ind,nodes); 00120 * 00121 * compute the 2 norm of each group, which is divided by the ind(3,:), 00122 * then the maximum value is returned 00123 */ 00124 /* 00125 *This function does not consider the case ind={[-1, -1, 100]',...} 00126 * 00127 *This functions is not used currently. 00128 */ 00129 void computeLambda2Max(double *lambda2_max, double *x, int n, double *ind, int nodes); 00130 00131 /* 00132 * ------------------------------------------------------------------- 00133 * Function and parameter 00134 * ------------------------------------------------------------------- 00135 * 00136 * treeNorm compute 00137 * 00138 * \sum \lambda_i \|x_{G_i}\|, 00139 * 00140 * where x is of dimension n, 00141 * \lambda_i >=0, and G_i's follow the tree structure 00142 * 00143 * The file is implemented in the following in Matlab: 00144 * 00145 * tree_norm=treeNorm(x, n, ind,nodes); 00146 */ 00147 double treeNorm(double *x, int ldx, int n, double *ind, int nodes); 00148 00149 /* 00150 * ------------------------------------------------------------------- 00151 * Function and parameter 00152 * ------------------------------------------------------------------- 00153 * 00154 * findLambdaMax compute 00155 * 00156 * the lambda_{max} that achieves a zero solution for 00157 * 00158 * min 1/2 \|x-v\|^2 + \lambda_{\max} * \sum w_i \|x_{G_i}\|, 00159 * 00160 * where x is of dimension n, 00161 * w_i >=0, and G_i's follow the tree structure 00162 * 00163 * The file is implemented in the following in Matlab: 00164 * 00165 * lambdaMax=findLambdaMax(v, n, ind,nodes); 00166 */ 00167 double findLambdaMax(double *v, int n, double *ind, int nodes); 00168 00169 /* 00170 * findLambdaMax_mt is a generalization of findLambdaMax to the 00171 * 00172 * multi-task learning scenario (or equivalently the multi-class case) 00173 * 00174 * lambdaMax=findLambdaMax_mt(X, V, n, k, ind, nodes); 00175 * 00176 * It applies findLambdaMax for each row (1xk) of X and V 00177 * 00178 */ 00179 double findLambdaMax_mt(double *V, int n, int k, double *ind, int nodes); 00180 #endif /* ----- #ifndef ALTRA_SLEP ----- */ 00181