Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011 #ifndef _MULTITASKKERNELTREENORMALIZER_H___
00012 #define _MULTITASKKERNELTREENORMALIZER_H___
00013
00014 #include <shogun/kernel/KernelNormalizer.h>
00015 #include <shogun/kernel/MultitaskKernelMklNormalizer.h>
00016 #include <shogun/kernel/Kernel.h>
00017 #include <algorithm>
00018 #include <map>
00019 #include <set>
00020 #include <deque>
00021
00022 namespace shogun
00023 {
00024
00029 class CNode: public CSGObject
00030 {
00031
00032 public:
00033
00034
00037 CNode()
00038 {
00039 parent = NULL;
00040 beta = 1.0;
00041 node_id = 0;
00042 }
00043
00047 std::set<CNode*> get_path_root()
00048 {
00049 std::set<CNode*> nodes_on_path = std::set<CNode*>();
00050 CNode *node = this;
00051 while (node != NULL) {
00052 nodes_on_path.insert(node);
00053 node = node->parent;
00054 }
00055 return nodes_on_path;
00056 }
00057
00061 std::vector<int32_t> get_task_ids_below()
00062 {
00063
00064 std::vector<int32_t> task_ids;
00065 std::deque<CNode*> grey_nodes;
00066 grey_nodes.push_back(this);
00067
00068 while(grey_nodes.size() > 0)
00069 {
00070
00071 CNode *current_node = grey_nodes.front();
00072 grey_nodes.pop_front();
00073
00074 for(int32_t i = 0; i!=int32_t(current_node->children.size()); i++){
00075 grey_nodes.push_back(current_node->children[i]);
00076 }
00077
00078 if(current_node->is_leaf()){
00079 task_ids.push_back(current_node->getNode_id());
00080 }
00081 }
00082
00083 return task_ids;
00084 }
00085
00089 void add_child(CNode *node)
00090 {
00091 node->parent = this;
00092 this->children.push_back(node);
00093 }
00094
00096 inline virtual const char *get_name() const
00097 {
00098 return "CNode";
00099 }
00100
00102 bool is_leaf()
00103 {
00104 return children.empty();
00105
00106 }
00107
00109 int32_t getNode_id() const
00110 {
00111 return node_id;
00112 }
00113
00115 void setNode_id(int32_t node_idx)
00116 {
00117 this->node_id = node_idx;
00118 }
00119
00121 float64_t beta;
00122
00123 protected:
00124
00126 CNode* parent;
00127
00129 std::vector<CNode*> children;
00130
00132 int32_t node_id;
00133
00134 };
00135
00136
00141 class CTaxonomy : public CSGObject
00142 {
00143
00144 public:
00145
00148 CTaxonomy() : CSGObject()
00149 {
00150 root = new CNode();
00151 nodes.push_back(root);
00152
00153 name2id = std::map<std::string, int32_t>();
00154 name2id["root"] = 0;
00155 }
00156
00161 CNode* get_node(int32_t task_id) {
00162 return nodes[task_id];
00163 }
00164
00168 void set_root_beta(float64_t beta)
00169 {
00170 nodes[0]->beta = beta;
00171 }
00172
00178 CNode* add_node(std::string parent_name, std::string child_name, float64_t beta) {
00179
00180
00181 if (child_name=="") SG_ERROR("child_name empty");
00182 if (parent_name=="") SG_ERROR("parent_name empty");
00183
00184
00185 CNode* child_node = new CNode();
00186
00187 child_node->beta = beta;
00188
00189 nodes.push_back(child_node);
00190 int32_t id = nodes.size()-1;
00191
00192 name2id[child_name] = id;
00193
00194 child_node->setNode_id(id);
00195
00196
00197
00198 CNode* parent = nodes[name2id[parent_name]];
00199
00200 parent->add_child(child_node);
00201
00202 return child_node;
00203
00204 }
00205
00210 int32_t get_id(std::string name) {
00211 return name2id[name];
00212 }
00213
00219 std::set<CNode*> intersect_root_path(CNode* node_lhs, CNode* node_rhs) {
00220
00221 std::set<CNode*> root_path_lhs = node_lhs->get_path_root();
00222 std::set<CNode*> root_path_rhs = node_rhs->get_path_root();
00223
00224 std::set<CNode*> intersection;
00225
00226 std::set_intersection(root_path_lhs.begin(), root_path_lhs.end(),
00227 root_path_rhs.begin(), root_path_rhs.end(),
00228 std::inserter(intersection, intersection.end()));
00229
00230 return intersection;
00231
00232 }
00233
00239 float64_t compute_node_similarity(int32_t task_lhs, int32_t task_rhs)
00240 {
00241
00242 CNode* node_lhs = get_node(task_lhs);
00243 CNode* node_rhs = get_node(task_rhs);
00244
00245
00246 std::set<CNode*> intersection = intersect_root_path(node_lhs, node_rhs);
00247
00248
00249 float64_t gamma = 0;
00250 for (std::set<CNode*>::const_iterator p = intersection.begin(); p != intersection.end(); ++p) {
00251
00252 gamma += (*p)->beta;
00253 }
00254
00255 return gamma;
00256
00257 }
00258
00262 void update_task_histogram(std::vector<int32_t> task_vector_lhs) {
00263
00264
00265 task_histogram.clear();
00266
00267
00268
00269 for (std::vector<int32_t>::const_iterator it=task_vector_lhs.begin(); it!=task_vector_lhs.end(); it++)
00270 {
00271 task_histogram[*it] = 0.0;
00272 }
00273
00274
00275 for (std::vector<int32_t>::const_iterator it=task_vector_lhs.begin(); it!=task_vector_lhs.end(); it++)
00276 {
00277 task_histogram[*it] += 1.0;
00278 }
00279
00280
00281 for (std::map<int32_t, float64_t>::const_iterator it=task_histogram.begin(); it!=task_histogram.end(); it++)
00282 {
00283 task_histogram[it->first] = task_histogram[it->first] / float64_t(task_vector_lhs.size());
00284 }
00285
00286 }
00287
00289 int32_t get_num_nodes()
00290 {
00291 return (int32_t)(nodes.size());
00292 }
00293
00295 int32_t get_num_leaves()
00296 {
00297 int32_t num_leaves = 0;
00298
00299 for (int32_t i=0; i!=get_num_nodes(); i++)
00300 {
00301 if (get_node(i)->is_leaf()==true)
00302 {
00303 num_leaves++;
00304 }
00305 }
00306
00307 return num_leaves;
00308 }
00309
00311 float64_t get_node_weight(int32_t idx)
00312 {
00313 CNode* node = get_node(idx);
00314 return node->beta;
00315 }
00316
00321 void set_node_weight(int32_t idx, float64_t weight)
00322 {
00323 CNode* node = get_node(idx);
00324 node->beta = weight;
00325 }
00326
00328 inline virtual const char* get_name() const
00329 {
00330 return "CTaxonomy";
00331 }
00332
00334 std::map<std::string, int32_t> get_name2id() {
00335 return name2id;
00336 }
00337
00343 int32_t get_id_by_name(std::string name)
00344 {
00345 return name2id[name];
00346 }
00347
00348
00349 protected:
00350
00352 CNode* root;
00354 std::map<std::string, int32_t> name2id;
00356 std::vector<CNode*> nodes;
00358 std::map<int32_t, float64_t> task_histogram;
00359
00360 };
00361
00362
00363
00364
00365 class CMultitaskKernelMklNormalizer;
00366
00370 class CMultitaskKernelTreeNormalizer: public CMultitaskKernelMklNormalizer
00371 {
00372
00373
00374
00375 public:
00376
00379 CMultitaskKernelTreeNormalizer() : CMultitaskKernelMklNormalizer()
00380 {
00381 }
00382
00389 CMultitaskKernelTreeNormalizer(std::vector<std::string> task_lhs,
00390 std::vector<std::string> task_rhs,
00391 CTaxonomy tax) : CMultitaskKernelMklNormalizer()
00392 {
00393
00394 taxonomy = tax;
00395 set_task_vector_lhs(task_lhs);
00396 set_task_vector_rhs(task_rhs);
00397
00398 num_nodes = taxonomy.get_num_nodes();
00399
00400 dependency_matrix = std::vector<float64_t>(num_nodes * num_nodes);
00401
00402 update_cache();
00403 }
00404
00405
00407 virtual ~CMultitaskKernelTreeNormalizer()
00408 {
00409 }
00410
00411
00413 void update_cache()
00414 {
00415
00416
00417 for (int32_t i=0; i!=num_nodes; i++)
00418 {
00419 for (int32_t j=0; j!=num_nodes; j++)
00420 {
00421
00422 float64_t similarity = taxonomy.compute_node_similarity(i, j);
00423 set_node_similarity(i,j,similarity);
00424
00425 }
00426
00427 }
00428 }
00429
00430
00431
00437 inline virtual float64_t normalize(float64_t value, int32_t idx_lhs, int32_t idx_rhs)
00438 {
00439
00440
00441 int32_t task_idx_lhs = task_vector_lhs[idx_lhs];
00442 int32_t task_idx_rhs = task_vector_rhs[idx_rhs];
00443
00444
00445 float64_t task_similarity = get_node_similarity(task_idx_lhs, task_idx_rhs);
00446
00447
00448
00449 float64_t similarity = (value/scale) * task_similarity;
00450
00451
00452 return similarity;
00453
00454 }
00455
00460 inline virtual float64_t normalize_lhs(float64_t value, int32_t idx_lhs)
00461 {
00462 SG_ERROR("normalize_lhs not implemented");
00463 return 0;
00464 }
00465
00470 inline virtual float64_t normalize_rhs(float64_t value, int32_t idx_rhs)
00471 {
00472 SG_ERROR("normalize_rhs not implemented");
00473 return 0;
00474 }
00475
00476
00478 void set_task_vector_lhs(std::vector<std::string> vec)
00479 {
00480
00481 task_vector_lhs.clear();
00482
00483 for (int32_t i = 0; i != (int32_t)(vec.size()); ++i)
00484 {
00485 task_vector_lhs.push_back(taxonomy.get_id(vec[i]));
00486 }
00487
00488
00489 taxonomy.update_task_histogram(task_vector_lhs);
00490
00491 }
00492
00494 void set_task_vector_rhs(std::vector<std::string> vec)
00495 {
00496
00497 task_vector_rhs.clear();
00498
00499 for (int32_t i = 0; i != (int32_t)(vec.size()); ++i)
00500 {
00501 task_vector_rhs.push_back(taxonomy.get_id(vec[i]));
00502 }
00503
00504 }
00505
00507 void set_task_vector(std::vector<std::string> vec)
00508 {
00509 set_task_vector_lhs(vec);
00510 set_task_vector_rhs(vec);
00511 }
00512
00514 int32_t get_num_betas()
00515 {
00516
00517 return taxonomy.get_num_nodes();
00518
00519 }
00520
00524 float64_t get_beta(int32_t idx)
00525 {
00526
00527 return taxonomy.get_node_weight(idx);
00528
00529 }
00530
00534 void set_beta(int32_t idx, float64_t weight)
00535 {
00536
00537 taxonomy.set_node_weight(idx, weight);
00538
00539 update_cache();
00540
00541 }
00542
00543
00549 float64_t get_node_similarity(int32_t node_lhs, int32_t node_rhs)
00550 {
00551
00552 ASSERT(node_lhs < num_nodes && node_lhs >= 0);
00553 ASSERT(node_rhs < num_nodes && node_rhs >= 0);
00554
00555 return dependency_matrix[node_lhs * num_nodes + node_rhs];
00556
00557 }
00558
00564 void set_node_similarity(int32_t node_lhs, int32_t node_rhs,
00565 float64_t similarity)
00566 {
00567
00568 ASSERT(node_lhs < num_nodes && node_lhs >= 0);
00569 ASSERT(node_rhs < num_nodes && node_rhs >= 0);
00570
00571 dependency_matrix[node_lhs * num_nodes + node_rhs] = similarity;
00572
00573 }
00574
00575
00577 inline virtual const char* get_name() const
00578 {
00579 return "MultitaskKernelTreeNormalizer";
00580 }
00581
00582
00583
00584 protected:
00585
00586
00588 CTaxonomy taxonomy;
00589
00591 int32_t num_nodes;
00592
00594 std::vector<int32_t> task_vector_lhs;
00595
00597 std::vector<int32_t> task_vector_rhs;
00598
00600 std::vector<float64_t> dependency_matrix;
00601
00602 };
00603 }
00604 #endif