SHOGUN  3.2.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
MultitaskKernelTreeNormalizer.h
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 2 of the License, or
5  * (at your option) any later version.
6  *
7  * Written (W) 2010 Christian Widmer
8  * Copyright (C) 2010 Max-Planck-Society
9  */
10 
11 #ifndef _MULTITASKKERNELTREENORMALIZER_H___
12 #define _MULTITASKKERNELTREENORMALIZER_H___
13 
14 #include <shogun/lib/config.h>
15 
17 #include <shogun/kernel/Kernel.h>
18 #include <algorithm>
19 #include <map>
20 #include <set>
21 #include <deque>
22 #include <vector>
23 
24 namespace shogun
25 {
26 
31 class CNode: public CSGObject
32 {
33 public:
37  {
38  parent = NULL;
39  beta = 1.0;
40  node_id = 0;
41  }
42 
43  virtual ~CNode()
44  {
45  for (size_t i = 0; i < children.size(); i++)
46  delete children[i];
47  }
48 
52  std::set<CNode*> get_path_root()
53  {
54  std::set<CNode*> nodes_on_path = std::set<CNode*>();
55  CNode *node = this;
56  while (node != NULL) {
57  nodes_on_path.insert(node);
58  node = node->parent;
59  }
60  return nodes_on_path;
61  }
62 
66  std::vector<int32_t> get_task_ids_below()
67  {
68 
69  std::vector<int32_t> task_ids;
70  std::deque<CNode*> grey_nodes;
71  grey_nodes.push_back(this);
72 
73  while(grey_nodes.size() > 0)
74  {
75 
76  CNode *current_node = grey_nodes.front();
77  grey_nodes.pop_front();
78 
79  for(int32_t i = 0; i!=int32_t(current_node->children.size()); i++){
80  grey_nodes.push_back(current_node->children[i]);
81  }
82 
83  if(current_node->is_leaf()){
84  task_ids.push_back(current_node->getNode_id());
85  }
86  }
87 
88  return task_ids;
89  }
90 
95  {
96  node->parent = this;
97  this->children.push_back(node);
98  }
99 
101  virtual const char *get_name() const
102  {
103  return "Node";
104  }
105 
107  bool is_leaf()
108  {
109  return children.empty();
110 
111  }
112 
114  int32_t getNode_id() const
115  {
116  return node_id;
117  }
118 
120  void setNode_id(int32_t node_idx)
121  {
122  this->node_id = node_idx;
123  }
124 
127 
128 protected:
129 
132 
134  std::vector<CNode*> children;
135 
137  int32_t node_id;
138 
139 };
140 
141 
146 class CTaxonomy : public CSGObject
147 {
148 
149 public:
150 
154  {
155  root = new CNode();
156  nodes.push_back(root);
157 
158  name2id = std::map<std::string, int32_t>();
159  name2id["root"] = 0;
160  }
161 
162  virtual ~CTaxonomy()
163  {
164  for (size_t i = 0; i < nodes.size(); i++)
165  delete nodes[i];
166  nodes.clear();
167  name2id.clear();
168  task_histogram.clear();
169  }
170 
175  CNode* get_node(int32_t task_id) {
176  return nodes[task_id];
177  }
178 
183  {
184  nodes[0]->beta = beta;
185  }
186 
192  CNode* add_node(std::string parent_name, std::string child_name, float64_t beta)
193  {
194  if (child_name=="") SG_ERROR("child_name empty")
195  if (parent_name=="") SG_ERROR("parent_name empty")
196 
197 
198  CNode* child_node = new CNode();
199 
200  child_node->beta = beta;
201 
202  nodes.push_back(child_node);
203  int32_t id = nodes.size()-1;
204 
205  name2id[child_name] = id;
206 
207  child_node->setNode_id(id);
208 
209 
210  //create edge
211  CNode* parent = nodes[name2id[parent_name]];
212 
213  parent->add_child(child_node);
214 
215  return child_node;
216  }
217 
222  int32_t get_id(std::string name) {
223  return name2id[name];
224  }
225 
231  std::set<CNode*> intersect_root_path(CNode* node_lhs, CNode* node_rhs)
232  {
233 
234  std::set<CNode*> root_path_lhs = node_lhs->get_path_root();
235  std::set<CNode*> root_path_rhs = node_rhs->get_path_root();
236 
237  std::set<CNode*> intersection;
238 
239  std::set_intersection(root_path_lhs.begin(), root_path_lhs.end(),
240  root_path_rhs.begin(), root_path_rhs.end(),
241  std::inserter(intersection, intersection.end()));
242 
243  return intersection;
244 
245  }
246 
252  float64_t compute_node_similarity(int32_t task_lhs, int32_t task_rhs)
253  {
254 
255  CNode* node_lhs = get_node(task_lhs);
256  CNode* node_rhs = get_node(task_rhs);
257 
258  // compute intersection of paths to root
259  std::set<CNode*> intersection = intersect_root_path(node_lhs, node_rhs);
260 
261  // sum up weights
262  float64_t gamma = 0;
263  for (std::set<CNode*>::const_iterator p = intersection.begin(); p != intersection.end(); ++p) {
264 
265  gamma += (*p)->beta;
266  }
267 
268  return gamma;
269 
270  }
271 
275  void update_task_histogram(std::vector<int32_t> task_vector_lhs) {
276 
277  //empty map
278  task_histogram.clear();
279 
280 
281  //fill map with zeros
282  for (std::vector<int32_t>::const_iterator it=task_vector_lhs.begin(); it!=task_vector_lhs.end(); it++)
283  {
284  task_histogram[*it] = 0.0;
285  }
286 
287  //fill map
288  for (std::vector<int32_t>::const_iterator it=task_vector_lhs.begin(); it!=task_vector_lhs.end(); it++)
289  {
290  task_histogram[*it] += 1.0;
291  }
292 
293  //compute fractions
294  for (std::map<int32_t, float64_t>::const_iterator it=task_histogram.begin(); it!=task_histogram.end(); it++)
295  {
296  task_histogram[it->first] = task_histogram[it->first] / float64_t(task_vector_lhs.size());
297  }
298 
299  }
300 
302  int32_t get_num_nodes()
303  {
304  return (int32_t)(nodes.size());
305  }
306 
308  int32_t get_num_leaves()
309  {
310  int32_t num_leaves = 0;
311 
312  for (int32_t i=0; i!=get_num_nodes(); i++)
313  {
314  if (get_node(i)->is_leaf()==true)
315  {
316  num_leaves++;
317  }
318  }
319 
320  return num_leaves;
321  }
322 
325  {
326  CNode* node = get_node(idx);
327  return node->beta;
328  }
329 
334  void set_node_weight(int32_t idx, float64_t weight)
335  {
336  CNode* node = get_node(idx);
337  node->beta = weight;
338  }
339 
341  virtual const char* get_name() const
342  {
343  return "Taxonomy";
344  }
345 
347  std::map<std::string, int32_t> get_name2id() {
348  return name2id;
349  }
350 
356  int32_t get_id_by_name(std::string name)
357  {
358  return name2id[name];
359  }
360 
361 
362 protected:
363 
367  std::map<std::string, int32_t> name2id;
369  std::vector<CNode*> nodes;
371  std::map<int32_t, float64_t> task_histogram;
372 
373 };
374 
379 {
380 
381 public:
382 
386  {
387  }
388 
395  CMultitaskKernelTreeNormalizer(std::vector<std::string> task_lhs,
396  std::vector<std::string> task_rhs,
398  {
399 
400  taxonomy = tax;
401  set_task_vector_lhs(task_lhs);
402  set_task_vector_rhs(task_rhs);
403 
405 
406  dependency_matrix = std::vector<float64_t>(num_nodes * num_nodes);
407 
408  update_cache();
409  }
410 
411 
414  {
415  }
416 
417 
420  {
421 
422 
423  for (int32_t i=0; i!=num_nodes; i++)
424  {
425  for (int32_t j=0; j!=num_nodes; j++)
426  {
427 
428  float64_t similarity = taxonomy.compute_node_similarity(i, j);
429  set_node_similarity(i,j,similarity);
430 
431  }
432 
433  }
434  }
435 
436 
437 
443  virtual float64_t normalize(float64_t value, int32_t idx_lhs, int32_t idx_rhs)
444  {
445  //lookup tasks
446  int32_t task_idx_lhs = task_vector_lhs[idx_lhs];
447  int32_t task_idx_rhs = task_vector_rhs[idx_rhs];
448 
449  //lookup similarity
450  float64_t task_similarity = get_node_similarity(task_idx_lhs, task_idx_rhs);
451  //float64_t task_similarity = taxonomy.compute_node_similarity(task_idx_lhs, task_idx_rhs);
452 
453  //take task similarity into account
454  float64_t similarity = (value/scale) * task_similarity;
455 
456 
457  return similarity;
458  }
459 
464  virtual float64_t normalize_lhs(float64_t value, int32_t idx_lhs)
465  {
466  SG_ERROR("normalize_lhs not implemented")
467  return 0;
468  }
469 
474  virtual float64_t normalize_rhs(float64_t value, int32_t idx_rhs)
475  {
476  SG_ERROR("normalize_rhs not implemented")
477  return 0;
478  }
479 
480 
482  void set_task_vector_lhs(std::vector<std::string> vec)
483  {
484 
485  task_vector_lhs.clear();
486 
487  for (int32_t i = 0; i != (int32_t)(vec.size()); ++i)
488  {
489  task_vector_lhs.push_back(taxonomy.get_id(vec[i]));
490  }
491 
492  //update task histogram
494 
495  }
496 
498  void set_task_vector_rhs(std::vector<std::string> vec)
499  {
500 
501  task_vector_rhs.clear();
502 
503  for (int32_t i = 0; i != (int32_t)(vec.size()); ++i)
504  {
505  task_vector_rhs.push_back(taxonomy.get_id(vec[i]));
506  }
507 
508  }
509 
511  void set_task_vector(std::vector<std::string> vec)
512  {
513  set_task_vector_lhs(vec);
514  set_task_vector_rhs(vec);
515  }
516 
518  int32_t get_num_betas()
519  {
520 
521  return taxonomy.get_num_nodes();
522 
523  }
524 
528  float64_t get_beta(int32_t idx)
529  {
530 
531  return taxonomy.get_node_weight(idx);
532 
533  }
534 
538  void set_beta(int32_t idx, float64_t weight)
539  {
540 
541  taxonomy.set_node_weight(idx, weight);
542 
543  update_cache();
544 
545  }
546 
547 
553  float64_t get_node_similarity(int32_t node_lhs, int32_t node_rhs)
554  {
555 
556  ASSERT(node_lhs < num_nodes && node_lhs >= 0)
557  ASSERT(node_rhs < num_nodes && node_rhs >= 0)
558 
559  return dependency_matrix[node_lhs * num_nodes + node_rhs];
560 
561  }
562 
568  void set_node_similarity(int32_t node_lhs, int32_t node_rhs,
569  float64_t similarity)
570  {
571 
572  ASSERT(node_lhs < num_nodes && node_lhs >= 0)
573  ASSERT(node_rhs < num_nodes && node_rhs >= 0)
574 
575  dependency_matrix[node_lhs * num_nodes + node_rhs] = similarity;
576 
577  }
578 
580  virtual const char* get_name() const
581  {
582  return "MultitaskKernelTreeNormalizer";
583  }
584 
589  {
590  return dynamic_cast<CMultitaskKernelTreeNormalizer*>(n);
591  }
592 
593 protected:
596 
598  int32_t num_nodes;
599 
601  std::vector<int32_t> task_vector_lhs;
602 
604  std::vector<int32_t> task_vector_rhs;
605 
607  std::vector<float64_t> dependency_matrix;
608 };
609 }
610 #endif

SHOGUN Machine Learning Toolbox - Documentation