SHOGUN  v1.1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros 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 
16 #include <shogun/kernel/Kernel.h>
17 #include <algorithm>
18 #include <map>
19 #include <set>
20 #include <deque>
21 
22 namespace shogun
23 {
24 
29 class CNode: public CSGObject
30 {
31 public:
35  {
36  parent = NULL;
37  beta = 1.0;
38  node_id = 0;
39  }
40 
44  std::set<CNode*> get_path_root()
45  {
46  std::set<CNode*> nodes_on_path = std::set<CNode*>();
47  CNode *node = this;
48  while (node != NULL) {
49  nodes_on_path.insert(node);
50  node = node->parent;
51  }
52  return nodes_on_path;
53  }
54 
58  std::vector<int32_t> get_task_ids_below()
59  {
60 
61  std::vector<int32_t> task_ids;
62  std::deque<CNode*> grey_nodes;
63  grey_nodes.push_back(this);
64 
65  while(grey_nodes.size() > 0)
66  {
67 
68  CNode *current_node = grey_nodes.front();
69  grey_nodes.pop_front();
70 
71  for(int32_t i = 0; i!=int32_t(current_node->children.size()); i++){
72  grey_nodes.push_back(current_node->children[i]);
73  }
74 
75  if(current_node->is_leaf()){
76  task_ids.push_back(current_node->getNode_id());
77  }
78  }
79 
80  return task_ids;
81  }
82 
86  void add_child(CNode *node)
87  {
88  node->parent = this;
89  this->children.push_back(node);
90  }
91 
93  inline virtual const char *get_name() const
94  {
95  return "CNode";
96  }
97 
99  bool is_leaf()
100  {
101  return children.empty();
102 
103  }
104 
106  int32_t getNode_id() const
107  {
108  return node_id;
109  }
110 
112  void setNode_id(int32_t node_idx)
113  {
114  this->node_id = node_idx;
115  }
116 
119 
120 protected:
121 
124 
126  std::vector<CNode*> children;
127 
129  int32_t node_id;
130 
131 };
132 
133 
138 class CTaxonomy : public CSGObject
139 {
140 
141 public:
142 
146  {
147  root = new CNode();
148  nodes.push_back(root);
149 
150  name2id = std::map<std::string, int32_t>();
151  name2id["root"] = 0;
152  }
153 
158  CNode* get_node(int32_t task_id) {
159  return nodes[task_id];
160  }
161 
166  {
167  nodes[0]->beta = beta;
168  }
169 
175  CNode* add_node(std::string parent_name, std::string child_name, float64_t beta)
176  {
177  if (child_name=="") SG_ERROR("child_name empty");
178  if (parent_name=="") SG_ERROR("parent_name empty");
179 
180 
181  CNode* child_node = new CNode();
182 
183  child_node->beta = beta;
184 
185  nodes.push_back(child_node);
186  int32_t id = nodes.size()-1;
187 
188  name2id[child_name] = id;
189 
190  child_node->setNode_id(id);
191 
192 
193  //create edge
194  CNode* parent = nodes[name2id[parent_name]];
195 
196  parent->add_child(child_node);
197 
198  return child_node;
199  }
200 
205  int32_t get_id(std::string name) {
206  return name2id[name];
207  }
208 
214  std::set<CNode*> intersect_root_path(CNode* node_lhs, CNode* node_rhs)
215  {
216 
217  std::set<CNode*> root_path_lhs = node_lhs->get_path_root();
218  std::set<CNode*> root_path_rhs = node_rhs->get_path_root();
219 
220  std::set<CNode*> intersection;
221 
222  std::set_intersection(root_path_lhs.begin(), root_path_lhs.end(),
223  root_path_rhs.begin(), root_path_rhs.end(),
224  std::inserter(intersection, intersection.end()));
225 
226  return intersection;
227 
228  }
229 
235  float64_t compute_node_similarity(int32_t task_lhs, int32_t task_rhs)
236  {
237 
238  CNode* node_lhs = get_node(task_lhs);
239  CNode* node_rhs = get_node(task_rhs);
240 
241  // compute intersection of paths to root
242  std::set<CNode*> intersection = intersect_root_path(node_lhs, node_rhs);
243 
244  // sum up weights
245  float64_t gamma = 0;
246  for (std::set<CNode*>::const_iterator p = intersection.begin(); p != intersection.end(); ++p) {
247 
248  gamma += (*p)->beta;
249  }
250 
251  return gamma;
252 
253  }
254 
258  void update_task_histogram(std::vector<int32_t> task_vector_lhs) {
259 
260  //empty map
261  task_histogram.clear();
262 
263 
264  //fill map with zeros
265  for (std::vector<int32_t>::const_iterator it=task_vector_lhs.begin(); it!=task_vector_lhs.end(); it++)
266  {
267  task_histogram[*it] = 0.0;
268  }
269 
270  //fill map
271  for (std::vector<int32_t>::const_iterator it=task_vector_lhs.begin(); it!=task_vector_lhs.end(); it++)
272  {
273  task_histogram[*it] += 1.0;
274  }
275 
276  //compute fractions
277  for (std::map<int32_t, float64_t>::const_iterator it=task_histogram.begin(); it!=task_histogram.end(); it++)
278  {
279  task_histogram[it->first] = task_histogram[it->first] / float64_t(task_vector_lhs.size());
280  }
281 
282  }
283 
285  int32_t get_num_nodes()
286  {
287  return (int32_t)(nodes.size());
288  }
289 
291  int32_t get_num_leaves()
292  {
293  int32_t num_leaves = 0;
294 
295  for (int32_t i=0; i!=get_num_nodes(); i++)
296  {
297  if (get_node(i)->is_leaf()==true)
298  {
299  num_leaves++;
300  }
301  }
302 
303  return num_leaves;
304  }
305 
308  {
309  CNode* node = get_node(idx);
310  return node->beta;
311  }
312 
317  void set_node_weight(int32_t idx, float64_t weight)
318  {
319  CNode* node = get_node(idx);
320  node->beta = weight;
321  }
322 
324  inline virtual const char* get_name() const
325  {
326  return "CTaxonomy";
327  }
328 
330  std::map<std::string, int32_t> get_name2id() {
331  return name2id;
332  }
333 
339  int32_t get_id_by_name(std::string name)
340  {
341  return name2id[name];
342  }
343 
344 
345 protected:
346 
350  std::map<std::string, int32_t> name2id;
352  std::vector<CNode*> nodes;
354  std::map<int32_t, float64_t> task_histogram;
355 
356 };
357 
358 
359 
360 
362 
367 {
368 
369 
370 
371 public:
372 
376  {
377  }
378 
385  CMultitaskKernelTreeNormalizer(std::vector<std::string> task_lhs,
386  std::vector<std::string> task_rhs,
388  {
389 
390  taxonomy = tax;
391  set_task_vector_lhs(task_lhs);
392  set_task_vector_rhs(task_rhs);
393 
395 
396  dependency_matrix = std::vector<float64_t>(num_nodes * num_nodes);
397 
398  update_cache();
399  }
400 
401 
404  {
405  }
406 
407 
410  {
411 
412 
413  for (int32_t i=0; i!=num_nodes; i++)
414  {
415  for (int32_t j=0; j!=num_nodes; j++)
416  {
417 
418  float64_t similarity = taxonomy.compute_node_similarity(i, j);
419  set_node_similarity(i,j,similarity);
420 
421  }
422 
423  }
424  }
425 
426 
427 
433  inline virtual float64_t normalize(float64_t value, int32_t idx_lhs, int32_t idx_rhs)
434  {
435  //lookup tasks
436  int32_t task_idx_lhs = task_vector_lhs[idx_lhs];
437  int32_t task_idx_rhs = task_vector_rhs[idx_rhs];
438 
439  //lookup similarity
440  float64_t task_similarity = get_node_similarity(task_idx_lhs, task_idx_rhs);
441  //float64_t task_similarity = taxonomy.compute_node_similarity(task_idx_lhs, task_idx_rhs);
442 
443  //take task similarity into account
444  float64_t similarity = (value/scale) * task_similarity;
445 
446 
447  return similarity;
448  }
449 
454  inline virtual float64_t normalize_lhs(float64_t value, int32_t idx_lhs)
455  {
456  SG_ERROR("normalize_lhs not implemented");
457  return 0;
458  }
459 
464  inline virtual float64_t normalize_rhs(float64_t value, int32_t idx_rhs)
465  {
466  SG_ERROR("normalize_rhs not implemented");
467  return 0;
468  }
469 
470 
472  void set_task_vector_lhs(std::vector<std::string> vec)
473  {
474 
475  task_vector_lhs.clear();
476 
477  for (int32_t i = 0; i != (int32_t)(vec.size()); ++i)
478  {
479  task_vector_lhs.push_back(taxonomy.get_id(vec[i]));
480  }
481 
482  //update task histogram
484 
485  }
486 
488  void set_task_vector_rhs(std::vector<std::string> vec)
489  {
490 
491  task_vector_rhs.clear();
492 
493  for (int32_t i = 0; i != (int32_t)(vec.size()); ++i)
494  {
495  task_vector_rhs.push_back(taxonomy.get_id(vec[i]));
496  }
497 
498  }
499 
501  void set_task_vector(std::vector<std::string> vec)
502  {
503  set_task_vector_lhs(vec);
504  set_task_vector_rhs(vec);
505  }
506 
508  int32_t get_num_betas()
509  {
510 
511  return taxonomy.get_num_nodes();
512 
513  }
514 
518  float64_t get_beta(int32_t idx)
519  {
520 
521  return taxonomy.get_node_weight(idx);
522 
523  }
524 
528  void set_beta(int32_t idx, float64_t weight)
529  {
530 
531  taxonomy.set_node_weight(idx, weight);
532 
533  update_cache();
534 
535  }
536 
537 
543  float64_t get_node_similarity(int32_t node_lhs, int32_t node_rhs)
544  {
545 
546  ASSERT(node_lhs < num_nodes && node_lhs >= 0);
547  ASSERT(node_rhs < num_nodes && node_rhs >= 0);
548 
549  return dependency_matrix[node_lhs * num_nodes + node_rhs];
550 
551  }
552 
558  void set_node_similarity(int32_t node_lhs, int32_t node_rhs,
559  float64_t similarity)
560  {
561 
562  ASSERT(node_lhs < num_nodes && node_lhs >= 0);
563  ASSERT(node_rhs < num_nodes && node_rhs >= 0);
564 
565  dependency_matrix[node_lhs * num_nodes + node_rhs] = similarity;
566 
567  }
568 
570  inline virtual const char* get_name() const
571  {
572  return "MultitaskKernelTreeNormalizer";
573  }
574 
579  {
580  return dynamic_cast<CMultitaskKernelTreeNormalizer*>(n);
581  }
582 
583 protected:
586 
588  int32_t num_nodes;
589 
591  std::vector<int32_t> task_vector_lhs;
592 
594  std::vector<int32_t> task_vector_rhs;
595 
597  std::vector<float64_t> dependency_matrix;
598 };
599 }
600 #endif

SHOGUN Machine Learning Toolbox - Documentation