Spn.hpp

Go to the documentation of this file.

#pragma once
 
#include <Eigen/Core>
#include <iostream>
#include <map>
#include <memory>
#include "mutable/util/ADT.hpp"
#include <set>
#include <type_traits>
#include <unordered_map>
#include <vector>
 
 
namespace m {
 
struct Spn
{
    public:
    enum LeafType {
        AUTO,
        DISCRETE,
        CONTINUOUS
    };
    enum SpnOperator {
        EQUAL,
        LESS,
        LESS_EQUAL,
        GREATER,
        GREATER_EQUAL,
        IS_NULL,
        EXPECTATION
    };
    enum EvalType {
        APPROXIMATE,
        UPPER_BOUND,
        LOWER_BOUND
    };
    enum UpdateType {
        INSERT,
        DELETE
    };
 
    using Filter = std::unordered_map<unsigned, std::pair<SpnOperator, float>>;
 
    private:
 
    struct LearningData
    {
        const Eigen::MatrixXf &data;
        const Eigen::MatrixXf &normalized;
        const Eigen::MatrixXi &null_matrix;
        SmallBitset variables;
        std::vector<LeafType> leaf_types;
 
        LearningData(
            const Eigen::MatrixXf &data,
            const Eigen::MatrixXf &normalized,
            const Eigen::MatrixXi &null_matrix,
            SmallBitset variables,
            std::vector<LeafType> leaf_types
        )
            : data(data)
            , normalized(normalized)
            , null_matrix(null_matrix)
            , variables(variables)
            , leaf_types(std::move(leaf_types))
        { }
    };
 
    struct Node
    {
        std::size_t num_rows;
 
        explicit Node(std::size_t num_rows) : num_rows(num_rows) { }
 
        virtual ~Node() = default;
        void dump() const;
        void dump(std::ostream &out) const;
 
        virtual std::pair<float, float> evaluate(const Filter &filter, unsigned leaf_id, EvalType eval_type) const = 0;
 
        virtual void update(Eigen::VectorXf &row, SmallBitset variables, UpdateType update_type) = 0;
 
        virtual std::size_t estimate_number_distinct_values(unsigned id) const = 0;
 
        virtual unsigned height() const = 0;
        virtual unsigned breadth() const = 0;
        virtual unsigned degree() const = 0;
        virtual std::size_t memory_usage() const = 0;
 
        virtual void print(std::ostream &out, std::size_t num_tabs) const = 0;
    };
 
    struct Sum : Node
    {
        struct ChildWithWeight
        {
            std::unique_ptr<Node> child;
            float weight; 
            Eigen::VectorXf centroid; 
 
            ChildWithWeight(std::unique_ptr<Node> child, float weight, Eigen::VectorXf centroid)
                : child(std::move(child))
                , weight(weight)
                , centroid(std::move(centroid))
            { }
        };
 
        std::vector<std::unique_ptr<ChildWithWeight>> children;
 
        Sum(std::vector<std::unique_ptr<ChildWithWeight>> children, std::size_t num_rows)
            : Node(num_rows)
            , children(std::move(children))
        { }
 
        std::pair<float, float> evaluate(const Filter &filter, unsigned leaf_id, EvalType eval_type) const override;
 
        void update(Eigen::VectorXf &row, SmallBitset variables, UpdateType update_type) override;
 
        std::size_t estimate_number_distinct_values(unsigned id) const override;
 
        unsigned height() const override {
            unsigned max_height = 0;
            for (auto &child : children) { max_height = std::max(max_height, child->child->height()); }
            return 1 + max_height;
        }
        unsigned breadth() const override {
            unsigned breadth = 0;
            for (auto &child : children) { breadth += child->child->breadth(); }
            return breadth;
        }
        unsigned degree() const override {
            unsigned max_degree = children.size();
            for (auto &child : children) { max_degree = std::max(max_degree, child->child->degree()); }
            return max_degree;
        }
        std::size_t memory_usage() const override {
            std::size_t memory_used = 0;
            memory_used += sizeof *this + children.size() * sizeof(decltype(children)::value_type);
            for (auto &child : children) {
                memory_used += child->child->memory_usage();
            }
            return memory_used;
        }
 
        void print(std::ostream &out, std::size_t num_tabs) const override;
    };
 
    struct Product : Node
    {
        struct ChildWithVariables
        {
            std::unique_ptr<Node> child; 
            SmallBitset variables; 
 
            ChildWithVariables(std::unique_ptr<Node> child, SmallBitset variables)
                : child(std::move(child))
                , variables(variables)
            { }
        };
 
        std::vector<std::unique_ptr<ChildWithVariables>> children;
 
        Product(std::vector<std::unique_ptr<ChildWithVariables>> children, std::size_t num_rows)
            : Node(num_rows)
            , children(std::move(children))
        { }
 
        std::pair<float, float> evaluate(const Filter &filter, unsigned leaf_id, EvalType eval_type) const override;
 
        void update(Eigen::VectorXf &row, SmallBitset variables, UpdateType update_type) override;
 
        std::size_t estimate_number_distinct_values(unsigned id) const override;
 
        unsigned height() const override {
            unsigned max_height = 0;
            for (auto &child : children) { max_height = std::max(max_height, child->child->height()); }
            return 1 + max_height;
        }
        unsigned breadth() const override {
            unsigned breadth = 0;
            for (auto &child : children) { breadth += child->child->breadth(); }
            return breadth;
        }
        unsigned degree() const override {
            unsigned max_degree = children.size();
            for (auto &child : children) { max_degree = std::max(max_degree, child->child->degree()); }
            return max_degree;
        }
        std::size_t memory_usage() const override {
            std::size_t memory_used = 0;
            memory_used += sizeof *this + children.size() * sizeof(decltype(children)::value_type);
            for (auto &child : children) {
                memory_used += child->variables.size() * sizeof child->variables;
                memory_used += child->child->memory_usage();
            }
            return memory_used;
        }
 
        void print(std::ostream &out, std::size_t num_tabs) const override;
    };
 
    struct DiscreteLeaf : Node
    {
        struct Bin
        {
            float value; 
            float cumulative_probability;
 
            Bin(float value, float cumulative_probability)
                : value(value)
                , cumulative_probability(cumulative_probability)
            { }
 
            bool operator<(Bin &other) const { return this->value < other.value; }
            bool operator<(float other) const { return this->value < other; }
        };
 
        std::vector<Bin> bins; 
        float null_probability; 
 
        DiscreteLeaf(std::vector<Bin> bins, float null_probability, std::size_t num_rows)
            : Node(num_rows)
            , bins(std::move(bins))
            , null_probability(null_probability)
        { }
 
        std::pair<float, float> evaluate(const Filter &bin_value, unsigned leaf_id, EvalType eval_type) const override;
 
        void update(Eigen::VectorXf &row, SmallBitset variables, UpdateType update_type) override;
 
        std::size_t estimate_number_distinct_values(unsigned id) const override;
 
        unsigned height() const override { return 0; }
        unsigned breadth() const override { return 1; }
        unsigned degree() const override { return 0; }
        std::size_t memory_usage() const override {
            return sizeof *this + bins.size() * sizeof(decltype(bins)::value_type);
        }
        void print(std::ostream &out, std::size_t num_tabs) const override;
    };
 
    struct ContinuousLeaf : Node
    {
        struct Bin
        {
            float upper_bound; 
            float cumulative_probability;
 
            Bin(float upper_bound, float cumulative_probability)
                : upper_bound(upper_bound)
                , cumulative_probability(cumulative_probability)
            { }
 
            bool operator<(Bin &other) const { return this->upper_bound < other.upper_bound; }
            bool operator<(float other) const { return this->upper_bound < other; }
        };
 
        std::vector<Bin> bins; 
        float lower_bound; 
        float lower_bound_probability; 
        float null_probability; 
 
        ContinuousLeaf(
            std::vector<Bin> bins,
            float lower_bound,
            float lower_bound_probability,
            float null_probability,
            std::size_t num_rows
        )
            : Node(num_rows)
            , bins(std::move(bins))
            , lower_bound(lower_bound)
            , lower_bound_probability(lower_bound_probability)
            , null_probability(null_probability)
        { }
 
        std::pair<float, float> evaluate(const Filter &filter, unsigned leaf_id, EvalType eval_type) const override;
 
        void update(Eigen::VectorXf &row, SmallBitset variables, UpdateType update_type) override;
 
        std::size_t estimate_number_distinct_values(unsigned id) const override;
 
        unsigned height() const override { return 0; }
        unsigned breadth() const override { return 1; }
        unsigned degree() const override { return 0; }
        std::size_t memory_usage() const override {
            return sizeof *this + bins.size() * sizeof(decltype(bins)::value_type);
        }
        void print(std::ostream &out, std::size_t num_tabs) const override;
    };
 
    std::size_t num_rows_;
    std::unique_ptr<Node> root_;
 
    Spn(std::size_t num_rows, std::unique_ptr<Node> root) : num_rows_(num_rows), root_(std::move(root)) { }
 
    public:
 
    std::size_t num_rows() const { return num_rows_; }
 
    /*==================================================================================================================
     * Learning
     *================================================================================================================*/
 
    private:
 
    static std::unique_ptr<Spn::Product> create_product_min_slice(LearningData &learning_data);
 
    static std::unique_ptr<Product> create_product_rdc(
        LearningData &learning_data,
        std::vector<SmallBitset> &column_candidates,
        std::vector<SmallBitset> &variable_candidates
    );
 
    static std::unique_ptr<Spn::Sum> create_sum(LearningData &learning_data);
 
    static std::unique_ptr<Node> learn_node(LearningData &learning_data);
 
    public:
 
    static Spn learn_spn(Eigen::MatrixXf &data, Eigen::MatrixXi &null_matrix, std::vector<LeafType> &leaf_types);
 
    /*==================================================================================================================
     * Inference
     *================================================================================================================*/
 
    private:
 
    void update(Eigen::VectorXf &row, UpdateType update_type);
 
    public:
 
    float likelihood(const Filter &filter) const;
 
    float upper_bound(const Filter &filter) const;
 
    float lower_bound(const Filter &filter) const;
 
    float expectation(unsigned attribute_id, const Filter &filter) const;
 
    void update_row(Eigen::VectorXf &old_row, Eigen::VectorXf &updated_row);
 
    void insert_row(Eigen::VectorXf &row);
 
    void delete_row(Eigen::VectorXf &row);
 
    std::size_t estimate_number_distinct_values(unsigned attribute_id) const;
 
    unsigned height() const { return root_->height(); }
    unsigned breadth() const { return root_->breadth(); }
    unsigned degree() const { return root_->degree(); }
    std::size_t memory_usage() const {
        std::size_t memory_used = 0;
        memory_used += sizeof root_;
        memory_used += root_->memory_usage();
        return memory_used;
    }
 
    void dump() const;
    void dump(std::ostream &out) const;
};
 
}