SHOGUN
v3.2.0
|
00001 /* 00002 * This program is free software; you can redistribute it and/or modify 00003 * it under the terms of the GNU General Public License as published by 00004 * the Free Software Foundation; either version 3 of the License, or 00005 * (at your option) any later version. 00006 * 00007 * Written (W) 2013 Shell Hu 00008 * Copyright (C) 2013 Shell Hu 00009 */ 00010 00011 #include <shogun/structure/FactorGraphModel.h> 00012 #include <shogun/structure/Factor.h> 00013 #include <shogun/features/FactorGraphFeatures.h> 00014 00015 #ifdef HAVE_STD_UNORDERED_MAP 00016 #include <unordered_map> 00017 typedef std::unordered_map<int32_t, int32_t> factor_counts_type; 00018 #else 00019 #include <tr1/unordered_map> 00020 typedef std::tr1::unordered_map<int32_t, int32_t> factor_counts_type; 00021 #endif 00022 00023 using namespace shogun; 00024 00025 CFactorGraphModel::CFactorGraphModel() 00026 : CStructuredModel() 00027 { 00028 init(); 00029 } 00030 00031 CFactorGraphModel::CFactorGraphModel(CFeatures* features, CStructuredLabels* labels, 00032 EMAPInferType inf_type, bool verbose) : CStructuredModel(features, labels) 00033 { 00034 init(); 00035 m_inf_type = inf_type; 00036 m_verbose = verbose; 00037 } 00038 00039 CFactorGraphModel::~CFactorGraphModel() 00040 { 00041 SG_UNREF(m_factor_types); 00042 } 00043 00044 void CFactorGraphModel::init() 00045 { 00046 SG_ADD((CSGObject**)&m_factor_types, "factor_types", "Array of factor types", MS_NOT_AVAILABLE); 00047 SG_ADD(&m_w_cache, "w_cache", "Cache of global parameters", MS_NOT_AVAILABLE); 00048 SG_ADD(&m_w_map, "w_map", "Parameter mapping", MS_NOT_AVAILABLE); 00049 00050 m_inf_type = TREE_MAX_PROD; 00051 m_factor_types = new CDynamicObjectArray(); 00052 m_verbose = false; 00053 00054 SG_REF(m_factor_types); 00055 } 00056 00057 void CFactorGraphModel::add_factor_type(CFactorType* ftype) 00058 { 00059 REQUIRE(ftype->get_w_dim() > 0, "%s::add_factor_type(): number of parameters can't be 0!\n", 00060 get_name()); 00061 00062 // check whether this ftype has been added 00063 int32_t id = ftype->get_type_id(); 00064 for (int32_t fi = 0; fi < m_factor_types->get_num_elements(); ++fi) 00065 { 00066 CFactorType* ft= dynamic_cast<CFactorType*>(m_factor_types->get_element(fi)); 00067 if (id == ft->get_type_id()) 00068 { 00069 SG_UNREF(ft); 00070 SG_PRINT("%s::add_factor_type(): factor_type (id = %d) has been added!\n", 00071 get_name(), id); 00072 00073 return; 00074 } 00075 00076 SG_UNREF(ft); 00077 } 00078 00079 SGVector<int32_t> w_map_cp = m_w_map.clone(); 00080 m_w_map.resize_vector(w_map_cp.size() + ftype->get_w_dim()); 00081 00082 for (int32_t mi = 0; mi < w_map_cp.size(); mi++) 00083 { 00084 m_w_map[mi] = w_map_cp[mi]; 00085 } 00086 // add new mapping in the end 00087 for (int32_t mi = w_map_cp.size(); mi < m_w_map.size(); mi++) 00088 { 00089 m_w_map[mi] = id; 00090 } 00091 00092 // push factor type 00093 m_factor_types->push_back(ftype); 00094 00095 // initialize w cache 00096 fparams_to_w(); 00097 00098 if (m_verbose) 00099 { 00100 m_w_map.display_vector("add_factor_type(): m_w_map"); 00101 } 00102 } 00103 00104 void CFactorGraphModel::del_factor_type(const int32_t ftype_id) 00105 { 00106 int w_dim = 0; 00107 // delete from m_factor_types 00108 for (int32_t fi = 0; fi < m_factor_types->get_num_elements(); ++fi) 00109 { 00110 CFactorType* ftype = dynamic_cast<CFactorType*>(m_factor_types->get_element(fi)); 00111 if (ftype_id == ftype->get_type_id()) 00112 { 00113 w_dim = ftype->get_w_dim(); 00114 SG_UNREF(ftype); 00115 m_factor_types->delete_element(fi); 00116 break; 00117 } 00118 00119 SG_UNREF(ftype); 00120 } 00121 00122 ASSERT(w_dim != 0); 00123 00124 SGVector<int32_t> w_map_cp = m_w_map.clone(); 00125 m_w_map.resize_vector(w_map_cp.size() - w_dim); 00126 00127 int ind = 0; 00128 for (int32_t mi = 0; mi < w_map_cp.size(); mi++) 00129 { 00130 if (w_map_cp[mi] == ftype_id) 00131 continue; 00132 00133 m_w_map[ind++] = w_map_cp[mi]; 00134 } 00135 00136 ASSERT(ind == m_w_map.size()); 00137 } 00138 00139 CDynamicObjectArray* CFactorGraphModel::get_factor_types() const 00140 { 00141 SG_REF(m_factor_types); 00142 return m_factor_types; 00143 } 00144 00145 CFactorType* CFactorGraphModel::get_factor_type(const int32_t ftype_id) const 00146 { 00147 for (int32_t fi = 0; fi < m_factor_types->get_num_elements(); ++fi) 00148 { 00149 CFactorType* ftype = dynamic_cast<CFactorType*>(m_factor_types->get_element(fi)); 00150 if (ftype_id == ftype->get_type_id()) 00151 return ftype; 00152 00153 SG_UNREF(ftype); 00154 } 00155 00156 return NULL; 00157 } 00158 00159 SGVector<int32_t> CFactorGraphModel::get_global_params_mapping() const 00160 { 00161 return m_w_map.clone(); 00162 } 00163 00164 SGVector<int32_t> CFactorGraphModel::get_params_mapping(const int32_t ftype_id) 00165 { 00166 return m_w_map.find(ftype_id); 00167 } 00168 00169 int32_t CFactorGraphModel::get_dim() const 00170 { 00171 return m_w_map.size(); 00172 } 00173 00174 SGVector<float64_t> CFactorGraphModel::fparams_to_w() 00175 { 00176 REQUIRE(m_factor_types != NULL, "%s::fparams_to_w(): no factor types!\n", get_name()); 00177 00178 if (m_w_cache.size() != get_dim()) 00179 m_w_cache.resize_vector(get_dim()); 00180 00181 int32_t offset = 0; 00182 for (int32_t fi = 0; fi < m_factor_types->get_num_elements(); ++fi) 00183 { 00184 CFactorType* ftype = dynamic_cast<CFactorType*>(m_factor_types->get_element(fi)); 00185 int32_t w_dim = ftype->get_w_dim(); 00186 offset += w_dim; 00187 SGVector<float64_t> fw = ftype->get_w(); 00188 SGVector<int32_t> fw_map = get_params_mapping(ftype->get_type_id()); 00189 00190 ASSERT(fw_map.size() == fw.size()); 00191 00192 for (int32_t wi = 0; wi < w_dim; wi++) 00193 m_w_cache[fw_map[wi]] = fw[wi]; 00194 00195 SG_UNREF(ftype); 00196 } 00197 00198 ASSERT(offset == m_w_cache.size()); 00199 00200 return m_w_cache; 00201 } 00202 00203 void CFactorGraphModel::w_to_fparams(SGVector<float64_t> w) 00204 { 00205 // if nothing changed 00206 if (m_w_cache.equals(w)) 00207 return; 00208 00209 if (m_verbose) 00210 SG_SPRINT("****** update m_w_cache!\n"); 00211 00212 ASSERT(w.size() == m_w_cache.size()); 00213 m_w_cache = w.clone(); 00214 00215 int32_t offset = 0; 00216 for (int32_t fi = 0; fi < m_factor_types->get_num_elements(); ++fi) 00217 { 00218 CFactorType* ftype = dynamic_cast<CFactorType*>(m_factor_types->get_element(fi)); 00219 int32_t w_dim = ftype->get_w_dim(); 00220 offset += w_dim; 00221 SGVector<float64_t> fw(w_dim); 00222 SGVector<int32_t> fw_map = get_params_mapping(ftype->get_type_id()); 00223 00224 for (int32_t wi = 0; wi < w_dim; wi++) 00225 fw[wi] = m_w_cache[fw_map[wi]]; 00226 00227 ftype->set_w(fw); 00228 SG_UNREF(ftype); 00229 } 00230 00231 ASSERT(offset == m_w_cache.size()); 00232 } 00233 00234 SGVector< float64_t > CFactorGraphModel::get_joint_feature_vector(int32_t feat_idx, CStructuredData* y) 00235 { 00236 // factor graph instance 00237 CFactorGraphFeatures* mf = CFactorGraphFeatures::obtain_from_generic(m_features); 00238 CFactorGraph* fg = mf->get_sample(feat_idx); 00239 00240 // ground truth states 00241 CFactorGraphObservation* fg_states = CFactorGraphObservation::obtain_from_generic(y); 00242 SGVector<int32_t> states = fg_states->get_data(); 00243 00244 // initialize psi 00245 SGVector<float64_t> psi(get_dim()); 00246 psi.zero(); 00247 00248 // construct unnormalized psi 00249 CDynamicObjectArray* facs = fg->get_factors(); 00250 for (int32_t fi = 0; fi < facs->get_num_elements(); ++fi) 00251 { 00252 CFactor* fac = dynamic_cast<CFactor*>(facs->get_element(fi)); 00253 CTableFactorType* ftype = fac->get_factor_type(); 00254 int32_t id = ftype->get_type_id(); 00255 SGVector<int32_t> w_map = get_params_mapping(id); 00256 00257 ASSERT(w_map.size() == ftype->get_w_dim()); 00258 00259 SGVector<float64_t> dat = fac->get_data(); 00260 int32_t dat_size = dat.size(); 00261 00262 ASSERT(w_map.size() == dat_size * ftype->get_num_assignments()); 00263 00264 int32_t ei = ftype->index_from_universe_assignment(states, fac->get_variables()); 00265 for (int32_t di = 0; di < dat_size; di++) 00266 psi[w_map[ei*dat_size + di]] += dat[di]; 00267 00268 SG_UNREF(ftype); 00269 SG_UNREF(fac); 00270 } 00271 00272 // negation (-E(x,y) = <w,phi(x,y)>) 00273 psi.scale(-1.0); 00274 00275 SG_UNREF(facs); 00276 SG_UNREF(fg); 00277 00278 return psi; 00279 } 00280 00281 // E(x_i, y; w) - E(x_i, y_i; w) >= L(y_i, y) - xi_i 00282 // xi_i >= max oracle 00283 // max oracle := argmax_y { L(y_i, y) - E(x_i, y; w) + E(x_i, y_i; w) } 00284 // := argmin_y { -L(y_i, y) + E(x_i, y; w) } - E(x_i, y_i; w) 00285 // we do energy minimization in inference, so get back to max oracle value is: 00286 // [ L(y_i, y_star) - E(x_i, y_star; w) ] + E(x_i, y_i; w) 00287 CResultSet* CFactorGraphModel::argmax(SGVector<float64_t> w, int32_t feat_idx, bool const training) 00288 { 00289 // factor graph instance 00290 CFactorGraphFeatures* mf = CFactorGraphFeatures::obtain_from_generic(m_features); 00291 CFactorGraph* fg = mf->get_sample(feat_idx); 00292 00293 // prepare factor graph 00294 fg->connect_components(); 00295 if (m_inf_type == TREE_MAX_PROD) 00296 { 00297 ASSERT(fg->is_tree_graph()); 00298 } 00299 00300 if (m_verbose) 00301 SG_SPRINT("\n------ example %d\n", feat_idx); 00302 00303 // update factor parameters 00304 w_to_fparams(w); 00305 fg->compute_energies(); 00306 00307 if (m_verbose) 00308 { 00309 SG_SPRINT("energy table before loss-aug:\n"); 00310 fg->evaluate_energies(); 00311 } 00312 00313 // prepare CResultSet 00314 CResultSet* ret = new CResultSet(); 00315 SG_REF(ret); 00316 00317 // y_truth 00318 CFactorGraphObservation* y_truth = 00319 CFactorGraphObservation::obtain_from_generic(m_labels->get_label(feat_idx)); 00320 00321 SGVector<int32_t> states_gt = y_truth->get_data(); 00322 00323 // E(x_i, y_i; w) 00324 ret->psi_truth = get_joint_feature_vector(feat_idx, y_truth); 00325 float64_t energy_gt = fg->evaluate_energy(states_gt); 00326 ret->score = energy_gt; 00327 00328 // - min_y [ E(x_i, y; w) - delta(y_i, y) ] 00329 CMAPInference infer_met(fg, m_inf_type); 00330 if (training) 00331 { 00332 fg->loss_augmentation(y_truth); // wrong assignments -delta() 00333 00334 if (m_verbose) 00335 { 00336 SG_SPRINT("energy table after loss-aug:\n"); 00337 fg->evaluate_energies(); 00338 } 00339 } 00340 00341 infer_met.inference(); 00342 00343 // y_star 00344 CFactorGraphObservation* y_star = infer_met.get_structured_outputs(); 00345 SGVector<int32_t> states_star = y_star->get_data(); 00346 00347 ret->argmax = y_star; 00348 ret->psi_pred = get_joint_feature_vector(feat_idx, y_star); 00349 float64_t l_energy_pred = fg->evaluate_energy(states_star); 00350 ret->score -= l_energy_pred; 00351 ret->delta = delta_loss(y_truth, y_star); 00352 00353 if (m_verbose) 00354 { 00355 float64_t dot_pred = SGVector< float64_t >::dot(w.vector, ret->psi_pred.vector, w.vlen); 00356 float64_t dot_truth = SGVector< float64_t >::dot(w.vector, ret->psi_truth.vector, w.vlen); 00357 float64_t slack = dot_pred + ret->delta - dot_truth; 00358 00359 SG_SPRINT("\n"); 00360 w.display_vector("w"); 00361 00362 ret->psi_pred.display_vector("psi_pred"); 00363 states_star.display_vector("state_pred"); 00364 00365 SG_SPRINT("dot_pred = %f, energy_pred = %f, delta = %f\n\n", dot_pred, l_energy_pred, ret->delta); 00366 00367 ret->psi_truth.display_vector("psi_truth"); 00368 states_gt.display_vector("state_gt"); 00369 00370 SG_SPRINT("dot_truth = %f, energy_gt = %f\n\n", dot_truth, energy_gt); 00371 00372 SG_SPRINT("slack = %f, score = %f\n\n", slack, ret->score); 00373 } 00374 00375 SG_UNREF(y_truth); 00376 SG_UNREF(fg); 00377 00378 return ret; 00379 } 00380 00381 float64_t CFactorGraphModel::delta_loss(CStructuredData* y1, CStructuredData* y2) 00382 { 00383 CFactorGraphObservation* y_truth = CFactorGraphObservation::obtain_from_generic(y1); 00384 CFactorGraphObservation* y_pred = CFactorGraphObservation::obtain_from_generic(y2); 00385 SGVector<int32_t> s_truth = y_truth->get_data(); 00386 SGVector<int32_t> s_pred = y_pred->get_data(); 00387 00388 ASSERT(s_pred.size() == s_truth.size()); 00389 00390 float64_t loss = 0.0; 00391 for (int32_t si = 0; si < s_pred.size(); si++) 00392 { 00393 if (s_pred[si] != s_truth[si]) 00394 loss += y_truth->get_loss_weights()[si]; 00395 } 00396 00397 return loss; 00398 } 00399 00400 void CFactorGraphModel::init_training() 00401 { 00402 } 00403 00404 void CFactorGraphModel::init_primal_opt( 00405 float64_t regularization, 00406 SGMatrix< float64_t > & A, 00407 SGVector< float64_t > a, 00408 SGMatrix< float64_t > B, 00409 SGVector< float64_t > & b, 00410 SGVector< float64_t > lb, 00411 SGVector< float64_t > ub, 00412 SGMatrix< float64_t > & C) 00413 { 00414 C = SGMatrix< float64_t >::create_identity_matrix(get_dim(), regularization); 00415 }