SHOGUN  3.2.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
FactorGraphModel.cpp
Go to the documentation of this file.
1 /*
2  * This program is free software; you can redistribute it and/or modify
3  * it under the terms of the GNU General Public License as published by
4  * the Free Software Foundation; either version 3 of the License, or
5  * (at your option) any later version.
6  *
7  * Written (W) 2013 Shell Hu
8  * Copyright (C) 2013 Shell Hu
9  */
10 
14 
15 #ifdef HAVE_STD_UNORDERED_MAP
16  #include <unordered_map>
17  typedef std::unordered_map<int32_t, int32_t> factor_counts_type;
18 #else
19  #include <tr1/unordered_map>
20  typedef std::tr1::unordered_map<int32_t, int32_t> factor_counts_type;
21 #endif
22 
23 using namespace shogun;
24 
27 {
28  init();
29 }
30 
32  EMAPInferType inf_type, bool verbose) : CStructuredModel(features, labels)
33 {
34  init();
35  m_inf_type = inf_type;
36  m_verbose = verbose;
37 }
38 
40 {
42 }
43 
44 void CFactorGraphModel::init()
45 {
46  SG_ADD((CSGObject**)&m_factor_types, "factor_types", "Array of factor types", MS_NOT_AVAILABLE);
47  SG_ADD(&m_w_cache, "w_cache", "Cache of global parameters", MS_NOT_AVAILABLE);
48  SG_ADD(&m_w_map, "w_map", "Parameter mapping", MS_NOT_AVAILABLE);
49 
52  m_verbose = false;
53 
55 }
56 
58 {
59  REQUIRE(ftype->get_w_dim() > 0, "%s::add_factor_type(): number of parameters can't be 0!\n",
60  get_name());
61 
62  // check whether this ftype has been added
63  int32_t id = ftype->get_type_id();
64  for (int32_t fi = 0; fi < m_factor_types->get_num_elements(); ++fi)
65  {
66  CFactorType* ft= dynamic_cast<CFactorType*>(m_factor_types->get_element(fi));
67  if (id == ft->get_type_id())
68  {
69  SG_UNREF(ft);
70  SG_PRINT("%s::add_factor_type(): factor_type (id = %d) has been added!\n",
71  get_name(), id);
72 
73  return;
74  }
75 
76  SG_UNREF(ft);
77  }
78 
79  SGVector<int32_t> w_map_cp = m_w_map.clone();
80  m_w_map.resize_vector(w_map_cp.size() + ftype->get_w_dim());
81 
82  for (int32_t mi = 0; mi < w_map_cp.size(); mi++)
83  {
84  m_w_map[mi] = w_map_cp[mi];
85  }
86  // add new mapping in the end
87  for (int32_t mi = w_map_cp.size(); mi < m_w_map.size(); mi++)
88  {
89  m_w_map[mi] = id;
90  }
91 
92  // push factor type
93  m_factor_types->push_back(ftype);
94 
95  // initialize w cache
96  fparams_to_w();
97 
98  if (m_verbose)
99  {
100  m_w_map.display_vector("add_factor_type(): m_w_map");
101  }
102 }
103 
104 void CFactorGraphModel::del_factor_type(const int32_t ftype_id)
105 {
106  int w_dim = 0;
107  // delete from m_factor_types
108  for (int32_t fi = 0; fi < m_factor_types->get_num_elements(); ++fi)
109  {
110  CFactorType* ftype = dynamic_cast<CFactorType*>(m_factor_types->get_element(fi));
111  if (ftype_id == ftype->get_type_id())
112  {
113  w_dim = ftype->get_w_dim();
114  SG_UNREF(ftype);
116  break;
117  }
118 
119  SG_UNREF(ftype);
120  }
121 
122  ASSERT(w_dim != 0);
123 
124  SGVector<int32_t> w_map_cp = m_w_map.clone();
125  m_w_map.resize_vector(w_map_cp.size() - w_dim);
126 
127  int ind = 0;
128  for (int32_t mi = 0; mi < w_map_cp.size(); mi++)
129  {
130  if (w_map_cp[mi] == ftype_id)
131  continue;
132 
133  m_w_map[ind++] = w_map_cp[mi];
134  }
135 
136  ASSERT(ind == m_w_map.size());
137 }
138 
140 {
142  return m_factor_types;
143 }
144 
145 CFactorType* CFactorGraphModel::get_factor_type(const int32_t ftype_id) const
146 {
147  for (int32_t fi = 0; fi < m_factor_types->get_num_elements(); ++fi)
148  {
149  CFactorType* ftype = dynamic_cast<CFactorType*>(m_factor_types->get_element(fi));
150  if (ftype_id == ftype->get_type_id())
151  return ftype;
152 
153  SG_UNREF(ftype);
154  }
155 
156  return NULL;
157 }
158 
160 {
161  return m_w_map.clone();
162 }
163 
165 {
166  return m_w_map.find(ftype_id);
167 }
168 
170 {
171  return m_w_map.size();
172 }
173 
175 {
176  REQUIRE(m_factor_types != NULL, "%s::fparams_to_w(): no factor types!\n", get_name());
177 
178  if (m_w_cache.size() != get_dim())
180 
181  int32_t offset = 0;
182  for (int32_t fi = 0; fi < m_factor_types->get_num_elements(); ++fi)
183  {
184  CFactorType* ftype = dynamic_cast<CFactorType*>(m_factor_types->get_element(fi));
185  int32_t w_dim = ftype->get_w_dim();
186  offset += w_dim;
187  SGVector<float64_t> fw = ftype->get_w();
189 
190  ASSERT(fw_map.size() == fw.size());
191 
192  for (int32_t wi = 0; wi < w_dim; wi++)
193  m_w_cache[fw_map[wi]] = fw[wi];
194 
195  SG_UNREF(ftype);
196  }
197 
198  ASSERT(offset == m_w_cache.size());
199 
200  return m_w_cache;
201 }
202 
204 {
205  // if nothing changed
206  if (m_w_cache.equals(w))
207  return;
208 
209  if (m_verbose)
210  SG_SPRINT("****** update m_w_cache!\n");
211 
212  ASSERT(w.size() == m_w_cache.size());
213  m_w_cache = w.clone();
214 
215  int32_t offset = 0;
216  for (int32_t fi = 0; fi < m_factor_types->get_num_elements(); ++fi)
217  {
218  CFactorType* ftype = dynamic_cast<CFactorType*>(m_factor_types->get_element(fi));
219  int32_t w_dim = ftype->get_w_dim();
220  offset += w_dim;
221  SGVector<float64_t> fw(w_dim);
223 
224  for (int32_t wi = 0; wi < w_dim; wi++)
225  fw[wi] = m_w_cache[fw_map[wi]];
226 
227  ftype->set_w(fw);
228  SG_UNREF(ftype);
229  }
230 
231  ASSERT(offset == m_w_cache.size());
232 }
233 
235 {
236  // factor graph instance
238  CFactorGraph* fg = mf->get_sample(feat_idx);
239 
240  // ground truth states
242  SGVector<int32_t> states = fg_states->get_data();
243 
244  // initialize psi
246  psi.zero();
247 
248  // construct unnormalized psi
249  CDynamicObjectArray* facs = fg->get_factors();
250  for (int32_t fi = 0; fi < facs->get_num_elements(); ++fi)
251  {
252  CFactor* fac = dynamic_cast<CFactor*>(facs->get_element(fi));
253  CTableFactorType* ftype = fac->get_factor_type();
254  int32_t id = ftype->get_type_id();
256 
257  ASSERT(w_map.size() == ftype->get_w_dim());
258 
259  SGVector<float64_t> dat = fac->get_data();
260  int32_t dat_size = dat.size();
261 
262  ASSERT(w_map.size() == dat_size * ftype->get_num_assignments());
263 
264  int32_t ei = ftype->index_from_universe_assignment(states, fac->get_variables());
265  for (int32_t di = 0; di < dat_size; di++)
266  psi[w_map[ei*dat_size + di]] += dat[di];
267 
268  SG_UNREF(ftype);
269  SG_UNREF(fac);
270  }
271 
272  // negation (-E(x,y) = <w,phi(x,y)>)
273  psi.scale(-1.0);
274 
275  SG_UNREF(facs);
276  SG_UNREF(fg);
277 
278  return psi;
279 }
280 
281 // E(x_i, y; w) - E(x_i, y_i; w) >= L(y_i, y) - xi_i
282 // xi_i >= max oracle
283 // max oracle := argmax_y { L(y_i, y) - E(x_i, y; w) + E(x_i, y_i; w) }
284 // := argmin_y { -L(y_i, y) + E(x_i, y; w) } - E(x_i, y_i; w)
285 // we do energy minimization in inference, so get back to max oracle value is:
286 // [ L(y_i, y_star) - E(x_i, y_star; w) ] + E(x_i, y_i; w)
287 CResultSet* CFactorGraphModel::argmax(SGVector<float64_t> w, int32_t feat_idx, bool const training)
288 {
289  // factor graph instance
291  CFactorGraph* fg = mf->get_sample(feat_idx);
292 
293  // prepare factor graph
294  fg->connect_components();
295  if (m_inf_type == TREE_MAX_PROD)
296  {
297  ASSERT(fg->is_tree_graph());
298  }
299 
300  if (m_verbose)
301  SG_SPRINT("\n------ example %d\n", feat_idx);
302 
303  // update factor parameters
304  w_to_fparams(w);
305  fg->compute_energies();
306 
307  if (m_verbose)
308  {
309  SG_SPRINT("energy table before loss-aug:\n");
310  fg->evaluate_energies();
311  }
312 
313  // prepare CResultSet
314  CResultSet* ret = new CResultSet();
315  SG_REF(ret);
316  ret->psi_computed = true;
317 
318  // y_truth
319  CFactorGraphObservation* y_truth =
321 
322  SGVector<int32_t> states_gt = y_truth->get_data();
323 
324  // E(x_i, y_i; w)
325  ret->psi_truth = get_joint_feature_vector(feat_idx, y_truth);
326  float64_t energy_gt = fg->evaluate_energy(states_gt);
327  ret->score = energy_gt;
328 
329  // - min_y [ E(x_i, y; w) - delta(y_i, y) ]
330  if (training)
331  {
332  fg->loss_augmentation(y_truth); // wrong assignments -delta()
333 
334  if (m_verbose)
335  {
336  SG_SPRINT("energy table after loss-aug:\n");
337  fg->evaluate_energies();
338  }
339  }
340 
341  CMAPInference infer_met(fg, m_inf_type);
342  infer_met.inference();
343 
344  // y_star
345  CFactorGraphObservation* y_star = infer_met.get_structured_outputs();
346  SGVector<int32_t> states_star = y_star->get_data();
347 
348  ret->argmax = y_star;
349  ret->psi_pred = get_joint_feature_vector(feat_idx, y_star);
350  float64_t l_energy_pred = fg->evaluate_energy(states_star);
351  ret->score -= l_energy_pred;
352  ret->delta = delta_loss(y_truth, y_star);
353 
354  if (m_verbose)
355  {
358  float64_t slack = dot_pred + ret->delta - dot_truth;
359 
360  SG_SPRINT("\n");
361  w.display_vector("w");
362 
363  ret->psi_pred.display_vector("psi_pred");
364  states_star.display_vector("state_pred");
365 
366  SG_SPRINT("dot_pred = %f, energy_pred = %f, delta = %f\n\n", dot_pred, l_energy_pred, ret->delta);
367 
368  ret->psi_truth.display_vector("psi_truth");
369  states_gt.display_vector("state_gt");
370 
371  SG_SPRINT("dot_truth = %f, energy_gt = %f\n\n", dot_truth, energy_gt);
372 
373  SG_SPRINT("slack = %f, score = %f\n\n", slack, ret->score);
374  }
375 
376  SG_UNREF(y_truth);
377  SG_UNREF(fg);
378 
379  return ret;
380 }
381 
383 {
386  SGVector<int32_t> s_truth = y_truth->get_data();
387  SGVector<int32_t> s_pred = y_pred->get_data();
388 
389  ASSERT(s_pred.size() == s_truth.size());
390 
391  float64_t loss = 0.0;
392  for (int32_t si = 0; si < s_pred.size(); si++)
393  {
394  if (s_pred[si] != s_truth[si])
395  loss += y_truth->get_loss_weights()[si];
396  }
397 
398  return loss;
399 }
400 
402 {
403 }
404 
406  float64_t regularization,
414 {
416  REQUIRE(m_factor_types != NULL, "%s::init_primal_opt(): no factor types!\n", get_name());
417 
418  int32_t dim_w = get_dim();
419 
420  switch (m_inf_type)
421  {
422  case GRAPH_CUT:
423  lb.resize_vector(dim_w);
424  ub.resize_vector(dim_w);
427 
428  for (int32_t fi = 0; fi < m_factor_types->get_num_elements(); ++fi)
429  {
430  CFactorType* ftype = dynamic_cast<CFactorType*>(m_factor_types->get_element(fi));
431  int32_t w_dim = ftype->get_w_dim();
432  SGVector<int32_t> card = ftype->get_cardinalities();
433 
434  // TODO: Features of pairwise factor are assume to be 1. Consider more general case, e.g., edge features are availabel.
435  // for pairwise factors with binary labels
436  if (card.size() == 2 && card[0] == 2 && card[1] == 2)
437  {
438  REQUIRE(w_dim == 4, "GraphCut doesn't support edge features currently.");
439  SGVector<float64_t> fw = ftype->get_w();
441  ASSERT(fw_map.size() == fw.size());
442 
443  // submodularity constrain
444  // E(0,1) + E(1,0) - E(0,0) + E(1,1) > 0
445  // For pairwise factors, data term = 1,
446  // energy table indeces are defined as follows:
447  // w[0]*1 = E(0, 0)
448  // w[1]*1 = E(1, 0)
449  // w[2]*1 = E(0, 1)
450  // w[3]*1 = E(1, 1)
451  // thus, w[2] + w[1] - w[0] - w[3] > 0
452  // since factor graph model is over-parametering,
453  // the constrain can be written as w[2] > 0, w[1] > 0, w[0] = 0, w[3] = 0
454  lb[fw_map[0]] = 0;
455  ub[fw_map[0]] = 0;
456  lb[fw_map[3]] = 0;
457  ub[fw_map[3]] = 0;
458  lb[fw_map[1]] = 0;
459  lb[fw_map[2]] = 0;
460  }
461  SG_UNREF(ftype);
462  }
463  break;
464  case TREE_MAX_PROD:
465  case LOOPY_MAX_PROD:
466  case LP_RELAXATION:
467  case TRWS_MAX_PROD:
468  break;
469  }
470 }

SHOGUN Machine Learning Toolbox - Documentation