SHOGUN  v3.2.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
FactorGraphModel.cpp
Go to the documentation of this file.
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 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

SHOGUN Machine Learning Toolbox - Documentation