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 GENERAL_ALTRA_SLEP 00018 #define GENERAL_ALTRA_SLEP 00019 00020 #include <stdio.h> 00021 #include <stdlib.h> 00022 #include <math.h> 00023 #include <string.h> 00024 00025 /* 00026 * Important Notice: September 20, 2010 00027 * 00028 * In this head file, we deal with the case that the features might not be well ordered. 00029 * 00030 * If the features in the tree strucutre are well ordered, i.e., the indices of the left nodes is always less 00031 * than the right nodes, please refer to "altra.h". 00032 * 00033 * The advantage of "altra.h" is that, we donot need to use an explicit 00034 * variable for recording the indices. 00035 * 00036 * 00037 */ 00038 00039 /* 00040 * ------------------------------------------------------------------- 00041 * Functions and parameter 00042 * ------------------------------------------------------------------- 00043 * 00044 * general_altra solves the following problem 00045 * 00046 * 1/2 \|x-v\|^2 + \sum \lambda_i \|x_{G_i}\|, 00047 * 00048 * where x and v are of dimension n, 00049 * \lambda_i >=0, and G_i's follow the tree structure 00050 * 00051 * It is implemented in Matlab as follows: 00052 * 00053 * x=general_altra(v, n, G, ind, nodes); 00054 * 00055 * G contains the indices of the groups. 00056 * It is a row vector. Its length equals to \sum_i \|G_i\|. 00057 * If all the entries are penalized with L1 norm, 00058 * its length is \sum_i \|G_i\| - n. 00059 * 00060 * ind is a 3 x nodes matrix. 00061 * Each column corresponds to a node. 00062 * 00063 * The first element of each column is the starting index, 00064 * the second element of each column is the ending index 00065 * the third element of each column corrreponds to \lambbda_i. 00066 * 00067 * 00068 * 00069 * The following example shows how G and ind works: 00070 * 00071 * G={ {1, 2}, {4, 5}, {3, 6}, {7, 8}, 00072 * {1, 2, 3, 6}, {4, 5, 7, 8}, 00073 * {1, 2, 3, 4, 5, 6, 7, 8} }. 00074 * 00075 * ind={ [1, 2, 100]', [3, 4, 100]', [5, 6, 100]', [7, 8, 100]', 00076 * [9, 12, 100]', [13, 16, 100]', [17, 24, 100]' } 00077 * 00078 * where "100" denotes the weight for the nodes. 00079 * 00080 * 00081 * 00082 * ------------------------------------------------------------------- 00083 * Notices: 00084 * ------------------------------------------------------------------- 00085 * 00086 * 1. The features in the tree might not be well ordered. Otherwise, you are 00087 * suggested to use "altra.h". 00088 * 00089 * 2. When each elements of x are penalized via the same L1 00090 * (equivalent to the L2 norm) parameter, one can simplify the input 00091 * by specifying 00092 * the "first" column of ind as (-1, -1, lambda) 00093 * 00094 * In this case, we treat it as a single "super" node. Thus in the value 00095 * nodes, we only count it once. 00096 * 00097 * 3. The values in "ind" are in [1,length(G)]. 00098 * 00099 * 4. The third element of each column should be positive. The program does 00100 * not check the validity of the parameter. 00101 * 00102 * 5. The values in G should be within [1, n]. 00103 * 00104 * It is still valid to use the zero regularization parameter. 00105 * In this case, the program does not change the values of 00106 * correponding indices. 00107 * 00108 * 00109 * ------------------------------------------------------------------- 00110 * History: 00111 * ------------------------------------------------------------------- 00112 * 00113 * Composed by Jun Liu on April 20, 2010 00114 * 00115 * For any question or suggestion, please email j.liu@asu.edu. 00116 * 00117 */ 00118 void general_altra(double *x, double *v, int n, double *G, double *ind, int nodes, double mult=1.0); 00119 00120 /* 00121 * altra_mt is a generalization of altra to the 00122 * 00123 * multi-task learning scenario (or equivalently the multi-class case) 00124 * 00125 * altra_mt(X, V, n, k, G, ind, nodes); 00126 * 00127 * It applies altra for each row (1xk) of X and V 00128 * 00129 */ 00130 void general_altra_mt(double *X, double *V, int n, int k, double *G, double *ind, int nodes, double mult=1.0); 00131 00132 /* 00133 * compute 00134 * lambda2_max=general_computeLambda2Max(x,n,G, ind,nodes); 00135 * 00136 * compute the 2 norm of each group, which is divided by the ind(3,:), 00137 * then the maximum value is returned 00138 */ 00139 /* 00140 *This function does not consider the case ind={[-1, -1, 100]',...} 00141 * 00142 *This functions is not used currently. 00143 */ 00144 void general_computeLambda2Max(double *lambda2_max, double *x, int n, double *G, double *ind, int nodes); 00145 00146 /* 00147 * ------------------------------------------------------------------- 00148 * Function and parameter 00149 * ------------------------------------------------------------------- 00150 * 00151 * treeNorm compute 00152 * 00153 * \sum \lambda_i \|x_{G_i}\|, 00154 * 00155 * where x is of dimension n, 00156 * \lambda_i >=0, and G_i's follow the tree structure 00157 * 00158 * The file is implemented in the following in Matlab: 00159 * 00160 * tree_norm=general_treeNorm(x, n, G, ind,nodes); 00161 */ 00162 double general_treeNorm(double *x, int ldx, int n, double *G, double *ind, int nodes); 00163 00164 /* 00165 * ------------------------------------------------------------------- 00166 * Function and parameter 00167 * ------------------------------------------------------------------- 00168 * 00169 * findLambdaMax compute 00170 * 00171 * the lambda_{max} that achieves a zero solution for 00172 * 00173 * min 1/2 \|x-v\|^2 + \lambda_{\max} * \sum w_i \|x_{G_i}\|, 00174 * 00175 * where x is of dimension n, 00176 * w_i >=0, and G_i's follow the tree structure 00177 * 00178 * The file is implemented in the following in Matlab: 00179 * 00180 * lambdaMax=general_findLambdaMax(v, n, G, ind,nodes); 00181 */ 00182 double general_findLambdaMax(double *v, int n, double *G, double *ind, int nodes); 00183 00184 /* 00185 * findLambdaMax_mt is a generalization of findLambdaMax to the 00186 * 00187 * multi-task learning scenario (or equivalently the multi-class case) 00188 * 00189 * lambdaMax=general_findLambdaMax_mt(X, V, n, k, G, ind, nodes); 00190 * 00191 * It applies findLambdaMax for each row (1xk) of X and V 00192 * 00193 */ 00194 double general_findLambdaMax_mt(double *V, int n, int k, double *G, double *ind, int nodes); 00195 #endif /* ----- #ifndef GENERAL_ALTRA_SLEP ----- */ 00196