MultitaskKernelTreeNormalizer.h

Go to the documentation of this file.

/*
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * Written (W) 2010 Christian Widmer
 * Copyright (C) 2010 Max-Planck-Society
 */

#ifndef _MULTITASKKERNELTREENORMALIZER_H___
#define _MULTITASKKERNELTREENORMALIZER_H___

#include <shogun/transfer/multitask/MultitaskKernelMklNormalizer.h>
#include <shogun/kernel/Kernel.h>
#include <algorithm>
#include <map>
#include <set>
#include <deque>
#include <vector>

namespace shogun
{

class CNode: public CSGObject
{
public:
    CNode()
    {
        parent = NULL;
        beta = 1.0;
        node_id = 0;
    }

    virtual ~CNode()
    {
        for (size_t i = 0; i < children.size(); i++)
            delete children[i];
    }

    std::set<CNode*> get_path_root()
    {
        std::set<CNode*> nodes_on_path = std::set<CNode*>();
        CNode *node = this;
        while (node != NULL) {
            nodes_on_path.insert(node);
            node = node->parent;
        }
        return nodes_on_path;
    }

    std::vector<int32_t> get_task_ids_below()
    {

        std::vector<int32_t> task_ids;
        std::deque<CNode*> grey_nodes;
        grey_nodes.push_back(this);

        while(grey_nodes.size() > 0)
        {

            CNode *current_node = grey_nodes.front();
            grey_nodes.pop_front();

            for(int32_t i = 0; i!=int32_t(current_node->children.size()); i++){
                grey_nodes.push_back(current_node->children[i]);
            }

            if(current_node->is_leaf()){
                task_ids.push_back(current_node->getNode_id());
            }
        }

        return task_ids;
    }

    void add_child(CNode *node)
    {
        node->parent = this;
        this->children.push_back(node);
    }

    virtual const char *get_name() const
    {
        return "Node";
    }

    bool is_leaf()
    {
        return children.empty();

    }

    int32_t getNode_id() const
    {
        return node_id;
    }

    void setNode_id(int32_t node_idx)
    {
        this->node_id = node_idx;
    }

    float64_t beta;

protected:

    CNode* parent;

    std::vector<CNode*> children;

    int32_t node_id;

};


class CTaxonomy : public CSGObject
{

public:

    CTaxonomy() : CSGObject()
    {
        root = new CNode();
        nodes.push_back(root);

        name2id = std::map<std::string, int32_t>();
        name2id["root"] = 0;
    }

    virtual ~CTaxonomy()
    {
        for (size_t i = 0; i < nodes.size(); i++)
            delete nodes[i];
        nodes.clear();
        name2id.clear();
        task_histogram.clear();
    }

    CNode* get_node(int32_t task_id) {
        return nodes[task_id];
    }

    void set_root_beta(float64_t beta)
    {
        nodes[0]->beta = beta;
    }

    CNode* add_node(std::string parent_name, std::string child_name, float64_t beta)
    {
        if (child_name=="") SG_ERROR("child_name empty")
        if (parent_name=="") SG_ERROR("parent_name empty")


        CNode* child_node = new CNode();

        child_node->beta = beta;

        nodes.push_back(child_node);
        int32_t id = nodes.size()-1;

        name2id[child_name] = id;

        child_node->setNode_id(id);


        //create edge
        CNode* parent = nodes[name2id[parent_name]];

        parent->add_child(child_node);

        return child_node;
    }

    int32_t get_id(std::string name) {
        return name2id[name];
    }

    std::set<CNode*> intersect_root_path(CNode* node_lhs, CNode* node_rhs)
    {

        std::set<CNode*> root_path_lhs = node_lhs->get_path_root();
        std::set<CNode*> root_path_rhs = node_rhs->get_path_root();

        std::set<CNode*> intersection;

        std::set_intersection(root_path_lhs.begin(), root_path_lhs.end(),
                              root_path_rhs.begin(), root_path_rhs.end(),
                              std::inserter(intersection, intersection.end()));

        return intersection;

    }

    float64_t compute_node_similarity(int32_t task_lhs, int32_t task_rhs)
    {

        CNode* node_lhs = get_node(task_lhs);
        CNode* node_rhs = get_node(task_rhs);

        // compute intersection of paths to root
        std::set<CNode*> intersection = intersect_root_path(node_lhs, node_rhs);

        // sum up weights
        float64_t gamma = 0;
        for (std::set<CNode*>::const_iterator p = intersection.begin(); p != intersection.end(); ++p) {

            gamma += (*p)->beta;
        }

        return gamma;

    }

    void update_task_histogram(std::vector<int32_t> task_vector_lhs) {

        //empty map
        task_histogram.clear();


        //fill map with zeros
        for (std::vector<int32_t>::const_iterator it=task_vector_lhs.begin(); it!=task_vector_lhs.end(); it++)
        {
            task_histogram[*it] = 0.0;
        }

        //fill map
        for (std::vector<int32_t>::const_iterator it=task_vector_lhs.begin(); it!=task_vector_lhs.end(); it++)
        {
            task_histogram[*it] += 1.0;
        }

        //compute fractions
        for (std::map<int32_t, float64_t>::const_iterator it=task_histogram.begin(); it!=task_histogram.end(); it++)
        {
            task_histogram[it->first] = task_histogram[it->first] / float64_t(task_vector_lhs.size());
        }

    }

    int32_t get_num_nodes()
    {
        return (int32_t)(nodes.size());
    }

    int32_t get_num_leaves()
    {
        int32_t num_leaves = 0;

        for (int32_t i=0; i!=get_num_nodes(); i++)
        {
            if (get_node(i)->is_leaf()==true)
            {
                num_leaves++;
            }
        }

        return num_leaves;
    }

    float64_t get_node_weight(int32_t idx)
    {
        CNode* node = get_node(idx);
        return node->beta;
    }

    void set_node_weight(int32_t idx, float64_t weight)
    {
        CNode* node = get_node(idx);
        node->beta = weight;
    }

    virtual const char* get_name() const
    {
        return "Taxonomy";
    }

    std::map<std::string, int32_t> get_name2id() {
        return name2id;
    }

    int32_t get_id_by_name(std::string name)
    {
        return name2id[name];
    }


protected:

    CNode* root;
    std::map<std::string, int32_t> name2id;
    std::vector<CNode*> nodes;
    std::map<int32_t, float64_t> task_histogram;

};

class CMultitaskKernelTreeNormalizer: public CMultitaskKernelMklNormalizer
{

public:

    CMultitaskKernelTreeNormalizer() : CMultitaskKernelMklNormalizer()
    {
    }

    CMultitaskKernelTreeNormalizer(std::vector<std::string> task_lhs,
                                   std::vector<std::string> task_rhs,
                                   CTaxonomy tax) : CMultitaskKernelMklNormalizer()
    {

        taxonomy = tax;
        set_task_vector_lhs(task_lhs);
        set_task_vector_rhs(task_rhs);

        num_nodes = taxonomy.get_num_nodes();

        dependency_matrix = std::vector<float64_t>(num_nodes * num_nodes);

        update_cache();
    }


    virtual ~CMultitaskKernelTreeNormalizer()
    {
    }


    void update_cache()
    {


        for (int32_t i=0; i!=num_nodes; i++)
        {
            for (int32_t j=0; j!=num_nodes; j++)
            {

                float64_t similarity = taxonomy.compute_node_similarity(i, j);
                set_node_similarity(i,j,similarity);

            }

        }
    }



    virtual float64_t normalize(float64_t value, int32_t idx_lhs, int32_t idx_rhs)
    {
        //lookup tasks
        int32_t task_idx_lhs = task_vector_lhs[idx_lhs];
        int32_t task_idx_rhs = task_vector_rhs[idx_rhs];

        //lookup similarity
        float64_t task_similarity = get_node_similarity(task_idx_lhs, task_idx_rhs);
        //float64_t task_similarity = taxonomy.compute_node_similarity(task_idx_lhs, task_idx_rhs);

        //take task similarity into account
        float64_t similarity = (value/scale) * task_similarity;


        return similarity;
    }

    virtual float64_t normalize_lhs(float64_t value, int32_t idx_lhs)
    {
        SG_ERROR("normalize_lhs not implemented")
        return 0;
    }

    virtual float64_t normalize_rhs(float64_t value, int32_t idx_rhs)
    {
        SG_ERROR("normalize_rhs not implemented")
        return 0;
    }


    void set_task_vector_lhs(std::vector<std::string> vec)
    {

        task_vector_lhs.clear();

        for (int32_t i = 0; i != (int32_t)(vec.size()); ++i)
        {
            task_vector_lhs.push_back(taxonomy.get_id(vec[i]));
        }

        //update task histogram
        taxonomy.update_task_histogram(task_vector_lhs);

    }

    void set_task_vector_rhs(std::vector<std::string> vec)
    {

        task_vector_rhs.clear();

        for (int32_t i = 0; i != (int32_t)(vec.size()); ++i)
        {
            task_vector_rhs.push_back(taxonomy.get_id(vec[i]));
        }

    }

    void set_task_vector(std::vector<std::string> vec)
    {
        set_task_vector_lhs(vec);
        set_task_vector_rhs(vec);
    }

    int32_t get_num_betas()
    {

        return taxonomy.get_num_nodes();

    }

    float64_t get_beta(int32_t idx)
    {

        return taxonomy.get_node_weight(idx);

    }

    void set_beta(int32_t idx, float64_t weight)
    {

        taxonomy.set_node_weight(idx, weight);

        update_cache();

    }


    float64_t get_node_similarity(int32_t node_lhs, int32_t node_rhs)
    {

        ASSERT(node_lhs < num_nodes && node_lhs >= 0)
        ASSERT(node_rhs < num_nodes && node_rhs >= 0)

        return dependency_matrix[node_lhs * num_nodes + node_rhs];

    }

    void set_node_similarity(int32_t node_lhs, int32_t node_rhs,
            float64_t similarity)
    {

        ASSERT(node_lhs < num_nodes && node_lhs >= 0)
        ASSERT(node_rhs < num_nodes && node_rhs >= 0)

        dependency_matrix[node_lhs * num_nodes + node_rhs] = similarity;

    }

    virtual const char* get_name() const
    {
        return "MultitaskKernelTreeNormalizer";
    }

    CMultitaskKernelTreeNormalizer* KernelNormalizerToMultitaskKernelTreeNormalizer(CKernelNormalizer* n)
    {
        return dynamic_cast<CMultitaskKernelTreeNormalizer*>(n);
    }

protected:
    CTaxonomy taxonomy;

    int32_t num_nodes;

    std::vector<int32_t> task_vector_lhs;

    std::vector<int32_t> task_vector_rhs;

    std::vector<float64_t> dependency_matrix;
};
}
#endif