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

SHOGUN Machine Learning Toolbox - Documentation