SHOGUN  v3.0.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 
15 #if defined(HAVE_CXX0X) || defined(HAVE_CXX11)
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 
317  // y_truth
318  CFactorGraphObservation* y_truth =
320 
321  SGVector<int32_t> states_gt = y_truth->get_data();
322 
323  // E(x_i, y_i; w)
324  ret->psi_truth = get_joint_feature_vector(feat_idx, y_truth);
325  float64_t energy_gt = fg->evaluate_energy(states_gt);
326  ret->score = energy_gt;
327 
328  // - min_y [ E(x_i, y; w) - delta(y_i, y) ]
329  CMAPInference infer_met(fg, m_inf_type);
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  infer_met.inference();
342 
343  // y_star
344  CFactorGraphObservation* y_star = infer_met.get_structured_outputs();
345  SGVector<int32_t> states_star = y_star->get_data();
346 
347  ret->argmax = y_star;
348  ret->psi_pred = get_joint_feature_vector(feat_idx, y_star);
349  float64_t l_energy_pred = fg->evaluate_energy(states_star);
350  ret->score -= l_energy_pred;
351  ret->delta = delta_loss(y_truth, y_star);
352 
353  if (m_verbose)
354  {
357  float64_t slack = dot_pred + ret->delta - dot_truth;
358 
359  SG_SPRINT("\n");
360  w.display_vector("w");
361 
362  ret->psi_pred.display_vector("psi_pred");
363  states_star.display_vector("state_pred");
364 
365  SG_SPRINT("dot_pred = %f, energy_pred = %f, delta = %f\n\n", dot_pred, l_energy_pred, ret->delta);
366 
367  ret->psi_truth.display_vector("psi_truth");
368  states_gt.display_vector("state_gt");
369 
370  SG_SPRINT("dot_truth = %f, energy_gt = %f\n\n", dot_truth, energy_gt);
371 
372  SG_SPRINT("slack = %f, score = %f\n\n", slack, ret->score);
373  }
374 
375  SG_UNREF(y_truth);
376  SG_UNREF(fg);
377 
378  return ret;
379 }
380 
382 {
385  SGVector<int32_t> s_truth = y_truth->get_data();
386  SGVector<int32_t> s_pred = y_pred->get_data();
387 
388  ASSERT(s_pred.size() == s_truth.size());
389 
390  float64_t loss = 0.0;
391  for (int32_t si = 0; si < s_pred.size(); si++)
392  {
393  if (s_pred[si] != s_truth[si])
394  loss += y_truth->get_loss_weights()[si];
395  }
396 
397  return loss;
398 }
399 
401 {
402 }
403 
405  float64_t regularization,
413 {
415 }

SHOGUN Machine Learning Toolbox - Documentation