<commit_before>/*
 * opencog/learning/moses/eda/local_structure.h
 *
 * Copyright (C) 2002-2008 Novamente LLC
 * All Rights Reserved
 *
 * Written by <NAME>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License v3 as
 * published by the Free Software Foundation and including the exceptions
 * at http://opencog.org/wiki/Licenses
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program; if not, write to:
 * Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */
#ifndef _EDA_LOCAL_STRUCTURE_H
#define _EDA_LOCAL_STRUCTURE_H

#include <opencog/util/digraph.h>
#include <opencog/util/oc_assert.h>
#include <opencog/util/tree.h>

#include "../representation/field_set.h"

namespace opencog { 
namespace moses {

using std::vector;

// a dtree_node can represent 2 things:
// 
// 1) if the node is internal then the vector has only one element,
// the idx of the known field involved in the definition of
// conditional probability
//
// 2) if the node is a leaf then the vector size is a + 1 where a is
// the arity of the corresponding field. Each element i in [0, a) is
// number of "good" instances the (i+1)th disc of the corresponding
// field is encountered. The last element is the sum of all elements
// in [0, a) (useful for computing the probability distribution over
// the elements of the disc)
typedef vector<int> dtree_node;

// decision tree to compute the conditional (or marginal if the tree
// is a single node) probability of each raw disc knowing the value of
// other discs in the field set
typedef tree<dtree_node> dtree;

struct local_structure_model : public nullary_function<instance>,
                               public vector<dtree> {
    typedef vector<dtree> super; // each entry of dtree corresponds to
                                 // a raw field

    // creates a model based on a set of fields and a range of instances
    template<typename It>
    local_structure_model(const field_set& fields,
                          It from, It to, RandGen& _rng);

    instance operator()() const; // sample from the model

    void split(int, int, dtree::iterator);

protected:
    typedef vector<const instance*> iptr_seq;
    typedef iptr_seq::iterator iptr_iter;

    size_t _instance_length;

    vector<unsigned int> _ordering; // order of field indexes, used
                                    // for model sampling. Each idx in
                                    // the ordering is such that only
                                    // the indexes preceding it are
                                    // possibly used for computing its
                                    // conditional probability

    digraph _initial_deps;      // directed graph representing the
                                // dependencies between fields. This
                                // is solely used to compute _ordering
    field_set _fields;
    RandGen& rng;

    // true if the variable at index idx is identical over the range
    // of instances [l, u)
    bool is_uniform_on(iptr_iter l, iptr_iter u, int idx) const;

    void rec_split_onto(iptr_iter l, iptr_iter u, int src_idx, int idx,
                        dtree::iterator node, onto_tree::iterator osrc);
    void rec_split_contin(iptr_iter l, iptr_iter u,
                          int src_idx, int idx, dtree::iterator node);

    void make_dtree(super::iterator, int);

    void sample(dtree::iterator, disc_t&, const vector<disc_t>&) const;
};

struct univariate { // i.e., no structure learning
    typedef local_structure_model model_type;

    template<typename It>
    void operator()(const field_set&, It, It,
                    const local_structure_model&) const {}
};

/*struct bde_local_structure_learning {
  typedef local_structure_model model_type;

  //scratch_model should go here
  template<typename It>
  void operator()(const field_set&,It,It,local_structure_model&) const { }
  };*/

struct local_structure_probs_learning {
    typedef local_structure_model model_type;

    // update the model given a field_set and a range of "good"
    // instances
    template<typename It>
    void operator()(const field_set&, It, It, local_structure_model&) const;
protected:
    // update the dtree of the model of a field at index idx
    template<typename It>
    void rec_learn(const field_set&, It, It, int, dtree::iterator) const;
};

/////////////TEMPLATIZED FUNCTION IMPLEMENTATION///////////////

//creates a model based on a set of fields and a range of instances
template<typename It>
local_structure_model::local_structure_model(const field_set& fs,
                                             It from, It to,
                                             RandGen& _rng) :
    super(fs.raw_size()), _instance_length(fs.packed_width()),
    _ordering(make_counting_iterator(0), make_counting_iterator(int(size()))),
    _initial_deps(size()), _fields(fs), rng(_rng)
{
    super::iterator dtr = begin();

    if (!_fields.contin().empty() || !_fields.onto().empty()) {
        iptr_seq iptrs(make_transform_iterator(from, addressof<const instance>),
                       make_transform_iterator(to, addressof<const instance>));
        
        foreach(const field_set::onto_spec& o, _fields.onto()) { // onto vars
            int idx_base = distance(begin(), dtr);
            make_dtree(dtr++, o.tr->begin().number_of_children() + 1); // why + 1?

            for (field_set::width_t i = 1;i < o.depth;++i, ++dtr) {
                make_dtree(dtr, 0);
                _initial_deps.insert(idx_base + i - 1, idx_base + i);
                // need to recursively split on gggparent, ... , gparent, parent
                rec_split_onto(iptrs.begin(), iptrs.end(),
                               idx_base, idx_base + i,
                               dtr->begin(), o.tr->begin());

                //make_dtree(dtr,o.branching);
            }
        }

        foreach(const field_set::contin_spec& c, _fields.contin()) { // contin vars
            int idx_base = distance(begin(), dtr);
            make_dtree(dtr++, 3); //contin arity is 3
            for (field_set::width_t i = 1;i < c.depth;++i, ++dtr) {
                make_dtree(dtr, 3);
                _initial_deps.insert(idx_base + i - 1, idx_base + i); //add dep to parent

                //recursively split on gggparent, ... , gparent, parent<commit_msg>add docs for Bayesian optimization algorithm.<commit_after>/*
 * opencog/learning/moses/eda/local_structure.h
 *
 * Copyright (C) 2002-2008 Novamente LLC
 * All Rights Reserved
 *
 * Written by <NAME>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License v3 as
 * published by the Free Software Foundation and including the exceptions
 * at http://opencog.org/wiki/Licenses
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program; if not, write to:
 * Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */
#ifndef _EDA_LOCAL_STRUCTURE_H
#define _EDA_LOCAL_STRUCTURE_H

#include <opencog/util/digraph.h>
#include <opencog/util/oc_assert.h>
#include <opencog/util/tree.h>

#include "../representation/field_set.h"

namespace opencog {
namespace moses {

// Code in this file is used to implement the Bayesian Optimization
// Algorithm (BOA). Given a set of variables, it generates possible
// dependency trees between these variables, and then computes
// conditional probabilities between these variables.  The BOA algorithm
// then attempts to discover the dependency tree that best describes
// the inter-relationships between the variables.

using std::vector;

// dtree == dependency tree
//
// XXX from what I can tell, this code currently handles only
// dependencies between discrete variables... which makes snese,
// since conditional probabilities bewteen continuous variables
// would be quite different in the nitty gritty details. Don't
// know who easily this could be fixed using templates.
//
// a dtree_node can represent 2 things:
//
// 1) if the node is internal then the vector has only one element,
// the idx of the known field involved in the definition of
// conditional probability
//
// 2) if the node is a leaf then the vector size is a + 1 where a is
// the multiplicity of the corresponding field. Each element i in [0, a)
// is the number of "good" instances the (i+1)th disc of the corresponding
// field is encountered. The last element is the sum of all elements
// in [0, a) (useful for computing the probability distribution over
// the elements of the disc)
typedef vector<int> dtree_node;

// decision tree to compute the conditional (or marginal if the tree
// is a single node) probability of each raw disc knowing the value of
// other discs in the field set
typedef tree<dtree_node> dtree;

struct local_structure_model : public nullary_function<instance>,
                               public vector<dtree> {
    typedef vector<dtree> super; // each entry of dtree corresponds to
                                 // a raw field

    // creates a model based on a set of fields and a range of instances
    template<typename It>
    local_structure_model(const field_set& fields,
                          It from, It to, RandGen& _rng);

    instance operator()() const; // sample from the model

    void split(int, int, dtree::iterator);

protected:
    typedef vector<const instance*> iptr_seq;
    typedef iptr_seq::iterator iptr_iter;

    size_t _instance_length;

    vector<unsigned int> _ordering; // order of field indexes, used
                                    // for model sampling. Each idx in
                                    // the ordering is such that only
                                    // the indexes preceding it are
                                    // possibly used for computing its
                                    // conditional probability

    digraph _initial_deps;      // directed graph representing the
                                // dependencies between fields. This
                                // is solely used to compute _ordering
    field_set _fields;
    RandGen& rng;

    // true if the variable at index idx is identical over the range
    // of instances [l, u)
    bool is_uniform_on(iptr_iter l, iptr_iter u, int idx) const;

    void rec_split_onto(iptr_iter l, iptr_iter u, int src_idx, int idx,
                        dtree::iterator node, onto_tree::iterator osrc);
    void rec_split_contin(iptr_iter l, iptr_iter u,
                          int src_idx, int idx, dtree::iterator node);

    void make_dtree(super::iterator, int);

    void sample(dtree::iterator, disc_t&, const vector<disc_t>&) const;
};

struct univariate { // i.e., no structure learning
    typedef local_structure_model model_type;

    template<typename It>
    void operator()(const field_set&, It, It,
                    const local_structure_model&) const {}
};

/*struct bde_local_structure_learning {
  typedef local_structure_model model_type;

  //scratch_model should go here
  template<typename It>
  void operator()(const field_set&,It,It,local_structure_model&) const { }
  };*/

struct local_structure_probs_learning {
    typedef local_structure_model model_type;

    // update the model given a field_set and a range of "good"
    // instances
    template<typename It>
    void operator()(const field_set&, It, It, local_structure_model&) const;
protected:
    // update the dtree of the model of a field at index idx
    template<typename It>
    void rec_learn(const field_set&, It, It, int, dtree::iterator) const;
};

/////////////TEMPLATIZED FUNCTION IMPLEMENTATION///////////////

//creates a model based on a set of fields and a range of instances
template<typename It>
local_structure_model::local_structure_model(const field_set& fs,
                                             It from, It to,
                                             RandGen& _rng) :
    super(fs.raw_size()), _instance_length(fs.packed_width()),
    _ordering(make_counting_iterator(0), make_counting_iterator(int(size()))),
    _initial_deps(size()), _fields(fs), rng(_rng)
{
    super::iterator dtr = begin();

    if (!_fields.contin().empty() || !_fields.onto().empty()) {
        iptr_seq iptrs(make_transform_iterator(from, addressof<const instance>),
                       make_transform_iterator(to, addressof<const instance>));

        foreach(const field_set::onto_spec& o, _fields.onto()) { // onto vars
            int idx_base = distance(begin(), dtr);
            make_dtree(dtr++, o.tr->begin().number_of_children() + 1); // why + 1?

            for (field_set::width_t i = 1;i < o.depth;++i, ++dtr) {
                make_dtree(dtr, 0);
                _initial_deps.insert(idx_base + i - 1, idx_base + i);
                // need to recursively split on gggparent, ... , gparent, parent
                rec_split_onto(iptrs.begin(), iptrs.end(),
                               idx_base, idx_base + i,
                               dtr->begin(), o.tr->begin());

                //make_dtree(dtr,o.branching);
            }
        }

        foreach(const field_set::contin_spec& c, _fields.contin()) { // contin vars
            int idx_base = distance(begin(), dtr);
            make_dtree(dtr++, 3); //contin arity is 3
            for (field_set::width_t i = 1;i < c.depth;++i, ++dtr) {
                make_dtree(dtr, 3);
                _initial_deps.insert(idx_base + i - 1, idx_base + i); //add dep to parent

                //recursively split on gggparent, ... , gparent, parent
{'fraction_non_alphanumeric': 0.09412835047938974, 'fraction_numerical': 0.005318776681363287, 'mean_word_length': 2.4466956102267248, 'pattern_counts': {'":': 0, '<': 47, '<?xml version=': 0, '>': 49, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 24, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5385940', 'n_tokens_mistral': 4069, 'n_tokens_neox': 3879, 'n_words': 1425}