Holds a search space, consisting of operations and terminals and functions, and methods to sample that space to create programs. More...

#include <search_space.h>

Collaboration diagram for Brush::SearchSpace:

[legend]

Public Types
using	ArgsHash = std::size_t

template<typename T >
using	Map

Public Member Functions
template<typename PT >
PT	make_program (const Parameters &params, int max_d=0, int max_size=0)
	Makes a random program.

RegressorProgram	make_regressor (int max_d=0, int max_size=0, const Parameters &params=Parameters())
	Makes a random regressor program. Convenience wrapper for make_program.

ClassifierProgram	make_classifier (int max_d=0, int max_size=0, const Parameters &params=Parameters())
	Makes a random classifier program. Convenience wrapper for make_program.

MulticlassClassifierProgram	make_multiclass_classifier (int max_d=0, int max_size=0, const Parameters &params=Parameters())
	Makes a random multiclass classifier program. Convenience wrapper for make_program.

RepresenterProgram	make_representer (int max_d=0, int max_size=0, const Parameters &params=Parameters())
	Makes a random representer program. Convenience wrapper for make_program.

	SearchSpace ()=default

	SearchSpace (const Dataset &d, const unordered_map< string, float > &user_ops={}, bool weights_init=true)
	Construct a search space.

void	init (const Dataset &d, const unordered_map< string, float > &user_ops={}, bool weights_init=true)
	Called by the constructor to initialize the search space.

bool	check (DataType R) const
	check if a return type is in the node map

bool	check (DataType R, size_t sig_hash) const
	check if a function signature is in the search space

bool	check (DataType R, size_t sig_hash, NodeType type) const
	check if a typed Node is in the search space

template<typename Iter >
bool	has_solution_space (Iter start, Iter end) const
	Takes iterators to weight vectors and checks if they have a non-empty solution space. An empty solution space is defined as having no non-zero, positive values.

template<typename F >
Node	get (const string &name)

Node	get (NodeType type, DataType R, size_t sig_hash)
	get a typed node

template<typename S >
Node	get (NodeType type, DataType R, S sig)
	get a typed node.

vector< float >	get_weights () const
	get weights of the return types

vector< float >	get_weights (DataType ret) const
	get weights of the argument types matching return type `ret`.

vector< float >	get_weights (DataType ret, ArgsHash sig_hash) const
	get the weights of nodes matching a signature.

std::optional< Node >	sample_terminal (bool force_return=false) const
	Get a random terminal.

std::optional< Node >	sample_terminal (DataType R, bool force_return=false) const
	Get a random terminal with return type `R`

std::optional< Node >	sample_op (DataType ret) const
	get an operator matching return type `ret`.

std::optional< Node >	sample_op (NodeType type, DataType R)
	Get a specific node type that matches a return value.

std::optional< Node >	sample_op_with_arg (DataType ret, DataType arg, bool terminal_compatible=true, int max_args=0) const
	get operator with at least one argument matching arg

std::optional< Node >	get_node_like (Node node) const
	get a node with a signature matching `node`

std::optional< tree< Node > >	sample_subtree (Node root, int max_d, int max_size) const
	create a subtree with maximum size and depth restrictions and root of type `root_type`

void	print () const
	prints the search space map.

template<typename P >
P	make_program (const Parameters &params, int max_d, int max_size)

Public Attributes
Map< Node >	node_map
	Maps return types to argument types to node types.

Map< float >	node_map_weights
	A map of weights corresponding to elements in node_map, used to weight probabilities of each node being sampled from the map.

unordered_map< DataType, vector< Node > >	terminal_map
	Maps return types to terminals.

unordered_map< DataType, vector< float > >	terminal_weights
	A map of weights corresponding to elements in terminal_map, used to weight probabilities of each terminal being sampled from the map.

vector< DataType >	terminal_types
	A vector storing the available return types of terminals.

Private Member Functions
tree< Node > &	PTC2 (tree< Node > &Tree, tree< Node >::iterator root, int max_d, int max_size) const

template<NodeType NT, typename S >
constexpr void	AddNode (const unordered_map< string, float > &user_ops, const vector< DataType > &unique_data_types)

template<NodeType NT, typename Sigs , std::size_t... Is>
constexpr void	AddNodes (const unordered_map< string, float > &user_ops, const vector< DataType > &unique_data_types, std::index_sequence< Is... >)

template<NodeType NT>
void	MakeNodes (const unordered_map< string, float > &user_ops, const vector< DataType > &unique_data_types)

template<std::size_t... Is>
void	GenerateNodeMap (const unordered_map< string, float > &user_ops, const vector< DataType > &unique_data_types, std::index_sequence< Is... >)

Static Private Member Functions
template<NodeType NT, typename S > requires (!is_in_v<NT, NodeType::Terminal, NodeType::Constant, NodeType::MeanLabel>)
static constexpr std::optional< Node >	CreateNode (const auto &unique_data_types, bool use_all, bool weighted)

Detailed Description

Holds a search space, consisting of operations and terminals and functions, and methods to sample that space to create programs.

The set of operators is a user controlled parameter; however, we can automate, to some extent, the set of possible operators based on the data types in the problem. Constraints on operators based on data types:

only user specified operators are included.
operators whose arguments are covered by terminal types are included first. Then, a second pass includes any operators whose arguments are covered by terminal_types + return types of the current set of operators. One could imagine this continuing ad infinitum, but we just do two passes for simplicity.
assertion check to make sure there is at least one operator that returns the output type of the model.

When sampling in the search space (using any of the sampling functions sample_op or sample_terminal), some methods can fail to return a value — given a specific set of parameters to a function, the candidate solutions set may be empty — and, for these methods, the return type is either a valid value, or a std::nullopt. This is controlled wrapping the return type with std::optional.

Parameters

Definition at line 83 of file search_space.h.

Member Typedef Documentation

◆ ArgsHash

using Brush::SearchSpace::ArgsHash = std::size_t

Definition at line 85 of file search_space.h.

◆ Map

template<typename T >

using Brush::SearchSpace::Map

Initial value:

 unordered_map<DataType,           
                    unordered_map<ArgsHash,         
                        unordered_map<NodeType,   
                            T>>>

Definition at line 88 of file search_space.h.

Constructor & Destructor Documentation

◆ SearchSpace() [1/2]

Brush::SearchSpace::SearchSpace ( )

default

◆ SearchSpace() [2/2]

Brush::SearchSpace::SearchSpace	(	const Dataset &	d,
		const unordered_map< string, float > &	user_ops = {},
		bool	weights_init = true )

inline

Construct a search space.

Parameters

d	A dataset containing terminal definitions
user_ops	Optional user-provided dictionary of operators with their probability of being chosen
weights_init	whether the terminal prob_change should be estimated from correlations with the target value

Definition at line 181 of file search_space.h.

Member Function Documentation

◆ AddNode()

template<NodeType NT, typename S >

constexpr void Brush::SearchSpace::AddNode	(	const unordered_map< string, float > &	user_ops,
		const vector< DataType > &	unique_data_types )

inlineconstexprprivate

Definition at line 604 of file search_space.h.

Here is the call graph for this function:

◆ AddNodes()

template<NodeType NT, typename Sigs , std::size_t... Is>

constexpr void Brush::SearchSpace::AddNodes	(	const unordered_map< string, float > &	user_ops,
		const vector< DataType > &	unique_data_types,
		std::index_sequence< Is... >	)

inlineconstexprprivate

Definition at line 628 of file search_space.h.

Here is the call graph for this function:

◆ check() [1/3]

bool Brush::SearchSpace::check ( DataType R ) const

inline

check if a return type is in the node map

Parameters

R data type

Returns: true if it exists

Definition at line 194 of file search_space.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ check() [2/3]

bool Brush::SearchSpace::check	(	DataType	R,
		size_t	sig_hash ) const

inline

check if a function signature is in the search space

Parameters

R	return type
sig_hash	signature hash

Returns: true if it exists

Definition at line 206 of file search_space.h.

Here is the call graph for this function:

◆ check() [3/3]

bool Brush::SearchSpace::check	(	DataType	R,
		size_t	sig_hash,
		NodeType	type ) const

inline

check if a typed Node is in the search space

Parameters

R	return type
sig_hash	signature hash
type	the node type

Returns: true if it exists

Definition at line 222 of file search_space.h.

Here is the call graph for this function:

◆ CreateNode()

template<NodeType NT, typename S >
requires (!is_in_v<NT, NodeType::Terminal, NodeType::Constant, NodeType::MeanLabel>)

static constexpr std::optional< Node > Brush::SearchSpace::CreateNode	(	const auto &	unique_data_types,
		bool	use_all,
		bool	weighted )

inlinestaticconstexprprivate

Definition at line 586 of file search_space.h.

Here is the call graph for this function:

◆ GenerateNodeMap()

template<std::size_t... Is>

void Brush::SearchSpace::GenerateNodeMap	(	const unordered_map< string, float > &	user_ops,
		const vector< DataType > &	unique_data_types,
		std::index_sequence< Is... >	)

inlineprivate

Definition at line 659 of file search_space.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get() [1/3]

template<typename F >

Node Brush::SearchSpace::get ( const string & name )

Here is the caller graph for this function:

◆ get() [2/3]

template<typename S >

Node Brush::SearchSpace::get	(	NodeType	type,
		DataType	R,
		S	sig )

inline

get a typed node.

Template Parameters

S	the signature of the node, inferred.

Parameters

type	the node type
R	the return type of the node
sig	the signature of the node

Returns: the matching Node

Definition at line 265 of file search_space.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get() [3/3]

Node Brush::SearchSpace::get	(	NodeType	type,
		DataType	R,
		size_t	sig_hash )

inline

get a typed node

Parameters

type	the node type
R	the return type of the node
sig_hash	the signature hash of the node

Returns: the matching Node

Definition at line 252 of file search_space.h.

Here is the call graph for this function:

◆ get_node_like()

std::optional< Node > Brush::SearchSpace::get_node_like ( Node node ) const

inline

get a node with a signature matching node

Parameters

node	the node to match

Returns: std::optional that may contain a Node

Definition at line 550 of file search_space.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_weights() [1/3]

vector< float > Brush::SearchSpace::get_weights ( ) const

inline

get weights of the return types

Returns: a weight vector, each element corresponding to a return type.

Definition at line 269 of file search_space.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_weights() [2/3]

vector< float > Brush::SearchSpace::get_weights ( DataType ret ) const

inline

get weights of the argument types matching return type ret.

Parameters

ret	return type

Returns: a weight vector, each element corresponding to an args type.

Definition at line 289 of file search_space.h.

Here is the call graph for this function:

◆ get_weights() [3/3]

vector< float > Brush::SearchSpace::get_weights	(	DataType	ret,
		ArgsHash	sig_hash ) const

inline

get the weights of nodes matching a signature.

Parameters

ret	return type
sig_hash	signature hash

Returns: a weight vector, each element corresponding to a node.

Definition at line 308 of file search_space.h.

Here is the call graph for this function:

◆ has_solution_space()

template<typename Iter >

bool Brush::SearchSpace::has_solution_space	(	Iter	start,
		Iter	end ) const

inline

Takes iterators to weight vectors and checks if they have a non-empty solution space. An empty solution space is defined as having no non-zero, positive values.

Template Parameters

T	type of iterator.

Parameters

start	Start iterator
end	End iterator

Returns: true if at least one weight is positive

Definition at line 241 of file search_space.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ init()

void Brush::SearchSpace::init	(	const Dataset &	d,
		const unordered_map< string, float > &	user_ops = {},
		bool	weights_init = true )

Called by the constructor to initialize the search space.

Parameters

d	A dataset containing terminal definitions
user_ops	Optional user-provided dictionary of operators with their probability of being chosen
weights_init	whether the terminal prob_change should be estimated from correlations with the target value

Definition at line 166 of file search_space.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ make_classifier()

ClassifierProgram Brush::SearchSpace::make_classifier	(	int	max_d = 0,
		int	max_size = 0,
		const Parameters &	params = Parameters() )

Makes a random classifier program. Convenience wrapper for make_program.

Parameters

max_d	max depth of the program
max_size	max size of the program

Returns: a classifier program

Definition at line 407 of file search_space.cpp.

Here is the call graph for this function:

◆ make_multiclass_classifier()

MulticlassClassifierProgram Brush::SearchSpace::make_multiclass_classifier	(	int	max_d = 0,
		int	max_size = 0,
		const Parameters &	params = Parameters() )

Makes a random multiclass classifier program. Convenience wrapper for make_program.

Parameters

max_d	max depth of the program
max_size	max size of the program

Returns: a multiclass classifier program

Definition at line 412 of file search_space.cpp.

Here is the call graph for this function:

◆ make_program() [1/2]

template<typename P >

P Brush::SearchSpace::make_program	(	const Parameters &	params,
		int	max_d,
		int	max_size )

Definition at line 681 of file search_space.h.

Here is the call graph for this function:

◆ make_program() [2/2]

template<typename PT >

PT Brush::SearchSpace::make_program	(	const Parameters &	params,
		int	max_d = 0,
		int	max_size = 0 )

Makes a random program.

We use an implementation of PTC2 for strongly typed GP from

Sean Luke. "Two fast tree-creation algorithms for genetic programming" (https://doi.org/10.1109/4235.873237)

Template Parameters

PT	program type

Parameters

max_d	max depth of the program
max_size	max size of the programd

Returns: a program of type PTsize

Here is the caller graph for this function:

◆ make_regressor()

RegressorProgram Brush::SearchSpace::make_regressor	(	int	max_d = 0,
		int	max_size = 0,
		const Parameters &	params = Parameters() )

Makes a random regressor program. Convenience wrapper for make_program.

Parameters

max_d	max depth of the program
max_size	max size of the program

Returns: a regressor program

Definition at line 402 of file search_space.cpp.

Here is the call graph for this function:

◆ make_representer()

RepresenterProgram Brush::SearchSpace::make_representer	(	int	max_d = 0,
		int	max_size = 0,
		const Parameters &	params = Parameters() )

Makes a random representer program. Convenience wrapper for make_program.

Parameters

max_d	max depth of the program
max_size	max size of the program

Returns: a representer program

Definition at line 418 of file search_space.cpp.

Here is the call graph for this function:

◆ MakeNodes()

template<NodeType NT>

void Brush::SearchSpace::MakeNodes	(	const unordered_map< string, float > &	user_ops,
		const vector< DataType > &	unique_data_types )

inlineprivate

Definition at line 636 of file search_space.h.

Here is the call graph for this function:

◆ print()

void Brush::SearchSpace::print ( ) const

prints the search space map.

Definition at line 162 of file search_space.cpp.

◆ PTC2()

tree< Node > & Brush::SearchSpace::PTC2	(	tree< Node > &	Tree,
		tree< Node >::iterator	root,
		int	max_d,
		int	max_size ) const

private

Definition at line 268 of file search_space.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sample_op() [1/2]

std::optional< Node > Brush::SearchSpace::sample_op ( DataType ret ) const

inline

get an operator matching return type ret.

Parameters

ret	return type

Returns: std::optional that may contain a randomly chosen operator matching return type ret

Definition at line 420 of file search_space.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sample_op() [2/2]

std::optional< Node > Brush::SearchSpace::sample_op	(	NodeType	type,
		DataType	R )

inline

Get a specific node type that matches a return value.

Parameters

type	the node type
R	the return type

Returns: std::optional that may contain a Node of type type with return type R.

Definition at line 454 of file search_space.h.

Here is the call graph for this function:

◆ sample_op_with_arg()

std::optional< Node > Brush::SearchSpace::sample_op_with_arg	(	DataType	ret,
		DataType	arg,
		bool	terminal_compatible = true,
		int	max_args = 0 ) const

inline

get operator with at least one argument matching arg

Parameters

ret	return type
arg	argument type to match
terminal_compatible	if true, the other args the returned operator takes must exist in the terminal types.
max_args	if zero, there is no limit on number of arguments of the operator. If not, the operator can have at most `max_args` arguments.

Returns: std::optional that may contain a matching operator respecting all restrictions.

Definition at line 492 of file search_space.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sample_subtree()

std::optional< tree< Node > > Brush::SearchSpace::sample_subtree	(	Node	root,
		int	max_d,
		int	max_size ) const

create a subtree with maximum size and depth restrictions and root of type root_type

Parameters

root_type	return type
max_d	the maximum depth
max_size	the maximum size of the tree (will be sampled between [1, max_size])

Returns: std::optional that may contain a tree

Definition at line 235 of file search_space.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sample_terminal() [1/2]

std::optional< Node > Brush::SearchSpace::sample_terminal ( bool force_return = false ) const

inline

Get a random terminal.

Returns: std::optional that may contain a terminal Node.

Definition at line 319 of file search_space.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sample_terminal() [2/2]

std::optional< Node > Brush::SearchSpace::sample_terminal	(	DataType	R,
		bool	force_return = false ) const

inline

Get a random terminal with return type R

Returns: std::optional that may contain a terminal Node of type R.

Definition at line 380 of file search_space.h.

Here is the call graph for this function:

Member Data Documentation

◆ node_map

Map<Node> Brush::SearchSpace::node_map

Maps return types to argument types to node types.

schema:

{ return_type : { arguments_type : {node_type : node } }}

Definition at line 100 of file search_space.h.

◆ node_map_weights

Map<float> Brush::SearchSpace::node_map_weights

A map of weights corresponding to elements in node_map, used to weight probabilities of each node being sampled from the map.

Definition at line 103 of file search_space.h.

◆ terminal_map

unordered_map<DataType, vector<Node> > Brush::SearchSpace::terminal_map

Maps return types to terminals.

schema:

 { return_type : vector of Nodes }

Definition at line 113 of file search_space.h.

◆ terminal_types

vector<DataType> Brush::SearchSpace::terminal_types

A vector storing the available return types of terminals.

Definition at line 119 of file search_space.h.

◆ terminal_weights

unordered_map<DataType, vector<float> > Brush::SearchSpace::terminal_weights

A map of weights corresponding to elements in terminal_map, used to weight probabilities of each terminal being sampled from the map.

Definition at line 116 of file search_space.h.

The documentation for this struct was generated from the following files:

Public Types

Public Member Functions

Public Attributes

Private Member Functions

Static Private Member Functions

Detailed Description

Parameters

Member Typedef Documentation

◆ ArgsHash

◆ Map

Constructor & Destructor Documentation

◆ SearchSpace() [1/2]

◆ SearchSpace() [2/2]

Member Function Documentation

◆ AddNode()

◆ AddNodes()

◆ check() [1/3]

◆ check() [2/3]

◆ check() [3/3]

◆ CreateNode()

◆ GenerateNodeMap()

◆ get() [1/3]

◆ get() [2/3]

◆ get() [3/3]

◆ get_node_like()

◆ get_weights() [1/3]

◆ get_weights() [2/3]

◆ get_weights() [3/3]

◆ has_solution_space()

◆ init()

◆ make_classifier()

◆ make_multiclass_classifier()

◆ make_program() [1/2]

◆ make_program() [2/2]

◆ make_regressor()

◆ make_representer()

◆ MakeNodes()

◆ print()

◆ PTC2()

◆ sample_op() [1/2]

◆ sample_op() [2/2]

◆ sample_op_with_arg()

◆ sample_subtree()

◆ sample_terminal() [1/2]

◆ sample_terminal() [2/2]

Member Data Documentation

◆ node_map

◆ node_map_weights

◆ terminal_map

◆ terminal_types

◆ terminal_weights