matchbin_metrics.hpp

Metric structs that can be plugged into MatchBin.

Typedefs

template<size_t Width>
using StreakMetric = ApproxDualStreakMetric<Width>

Matches based on longest streaks of equal and unequal bits in two bitsets. Adapted from Downing, Keith L. Intelligence emerging: adaptivity and search in evolving neural systems. MIT Press, 2015.

Functions

template<size_t N>
const ExactStreakDistribution<N> &ExactStreakDistribution_ConstructOnFirstUse()
template<typename Query, typename Tag>
struct BaseMetric
#include <matchbin_metrics.hpp>

Abstract base class for metrics.

Public Functions

inline virtual ~BaseMetric()
virtual double operator()(const Query &a, const Tag &b) const = 0
virtual size_t dim() const = 0
virtual size_t width() const = 0
virtual std::string name() const = 0
virtual std::string base() const = 0
template<size_t Width>
struct HammingMetric : public BaseMetric<BitSet<Width>, BitSet<Width>>
#include <matchbin_metrics.hpp>

Metric for MatchBin stored in the struct so we can template on it Returns the number of bits not in common between two BitSets

Public Types

using query_t = BitSet<Width>
using tag_t = BitSet<Width>

Public Functions

inline virtual size_t dim() const override
inline virtual size_t width() const override
inline virtual std::string name() const override
inline virtual std::string base() const override
inline double operator()(const query_t &a, const tag_t &b) const override

Public Static Functions

static inline double calculate(const query_t &a, const tag_t &b)
template<size_t Width>
struct HashMetric : public BaseMetric<BitSet<Width>, BitSet<Width>>
#include <matchbin_metrics.hpp>

Generate an arbitrary, but consistent, match score between 0 and 1.

Public Types

using query_t = BitSet<Width>
using tag_t = BitSet<Width>

Public Functions

inline virtual size_t dim() const override
inline virtual size_t width() const override
inline virtual std::string name() const override
inline virtual std::string base() const override
inline double operator()(const query_t &a, const tag_t &b) const override

Public Static Functions

static inline double calculate(const query_t &a, const tag_t &b)
struct AbsDiffMetric : public BaseMetric<int, int>
#include <matchbin_metrics.hpp>

Metric gives the absolute difference between two integers.

Public Types

using query_t = int
using tag_t = int

Public Functions

inline virtual size_t dim() const override
inline virtual size_t width() const override
inline virtual std::string name() const override
inline virtual std::string base() const override
inline virtual double operator()(const query_t &a, const tag_t &b) const override

Public Static Functions

static inline double calculate(const query_t &a, const tag_t &b)
template<size_t Max = 1000>
struct NextUpMetric : public BaseMetric<size_t, size_t>
#include <matchbin_metrics.hpp>

Metric gives the matchings by the closest tag on or above itself. Wraps on Max. Adapted from Spector, Lee, et al. “Tag-based modules in genetic programming.” Proceedings of the 13th annual conference on Genetic and evolutionary computation. ACM, 2011.

Public Types

using query_t = size_t
using tag_t = size_t

Public Functions

inline virtual size_t dim() const override
inline virtual size_t width() const override
inline virtual std::string name() const override
inline virtual std::string base() const override
inline virtual double operator()(const query_t &a, const tag_t &b) const override

Public Static Functions

static inline double calculate(const query_t &a, const tag_t &b)
template<size_t Width>
struct AsymmetricWrapMetric : public BaseMetric<BitSet<Width>, BitSet<Width>>
#include <matchbin_metrics.hpp>

BitSet-based implementation of NextUpMetric. Adapted from Spector, Lee, et al. “Tag-based modules in genetic programming.” Proceedings of the 13th annual conference on Genetic and evolutionary computation. ACM, 2011.

Public Types

using query_t = BitSet<Width>
using tag_t = BitSet<Width>

Public Functions

inline virtual size_t dim() const override
inline virtual size_t width() const override
inline virtual std::string name() const override
inline virtual std::string base() const override
inline double operator()(const query_t &a, const tag_t &b) const override

Public Static Functions

static inline double calculate(const query_t &a, const tag_t &b)
template<size_t Width>
struct AsymmetricNoWrapMetric : public BaseMetric<BitSet<Width>, BitSet<Width>>
#include <matchbin_metrics.hpp>

BitSet-based implementation of NextUpMetric without wrapping.

Public Types

using query_t = BitSet<Width>
using tag_t = BitSet<Width>

Public Functions

inline virtual size_t dim() const override
inline virtual size_t width() const override
inline virtual std::string name() const override
inline virtual std::string base() const override
inline double operator()(const query_t &a, const tag_t &b) const override

Public Static Functions

static inline double calculate(const query_t &a, const tag_t &b)
template<size_t Width>
struct SymmetricWrapMetric : public BaseMetric<BitSet<Width>, BitSet<Width>>
#include <matchbin_metrics.hpp>

Metric gives the absolute value of the difference between the integer representations of the BitSets with wrap from zero to the maximum value the BitSet can represent. Adapted from Downing, Keith L. Intelligence emerging: adaptivity and search in evolving neural systems. MIT Press, 2015.

Public Types

using query_t = BitSet<Width>
using tag_t = BitSet<Width>

Public Functions

inline virtual size_t dim() const override
inline virtual size_t width() const override
inline virtual std::string name() const override
inline virtual std::string base() const override
inline double operator()(const query_t &a, const tag_t &b) const override

Public Static Functions

static inline double calculate(const query_t &a, const tag_t &b)
template<size_t Width>
struct SymmetricNoWrapMetric : public BaseMetric<BitSet<Width>, BitSet<Width>>
#include <matchbin_metrics.hpp>

Metric gives the absolute value of the difference between the integer representations of the BitSets. Adapted from Downing, Keith L. Intelligence emerging: adaptivity and search in evolving neural systems. MIT Press, 2015.

Public Types

using query_t = BitSet<Width>
using tag_t = BitSet<Width>

Public Functions

inline virtual size_t dim() const override
inline virtual size_t width() const override
inline virtual std::string name() const override
inline virtual std::string base() const override
inline double operator()(const query_t &a, const tag_t &b) const override

Public Static Functions

static inline double calculate(const query_t &a, const tag_t &b)
template<size_t Width>
struct HammingCumuMetric : public BaseMetric<BitSet<Width>, BitSet<Width>>
#include <matchbin_metrics.hpp>

Matches based on the number of bits in common between the two bitsets. Normalized so that each match score represents the cumulative probability of an as-good or better match.

Public Types

using query_t = BitSet<Width>
using tag_t = BitSet<Width>

Public Functions

inline virtual size_t dim() const override
inline virtual size_t width() const override
inline virtual std::string name() const override
inline virtual std::string base() const override
inline double operator()(const query_t &a, const tag_t &b) const override

Public Static Functions

static inline double calculate(const query_t &a, const tag_t &b)

Public Static Attributes

static static_constructed cumulative = {}
struct static_constructed : public vector<double>
#include <matchbin_metrics.hpp>

Public Functions

inline static_constructed()
template<size_t Width>
struct ApproxSingleStreakMetric : public BaseMetric<BitSet<Width>, BitSet<Width>>
#include <matchbin_metrics.hpp>

Matches based on longest streaks of equal bits in two bitsets. This implementation uses Incorrect Math from Downing’s Intelligence Emerging. Adapted from Downing, Keith L. Intelligence emerging: adaptivity and search in evolving neural systems. MIT Press, 2015.

Public Types

using query_t = BitSet<Width>
using tag_t = BitSet<Width>

Public Functions

inline virtual size_t dim() const override
inline virtual size_t width() const override
inline virtual std::string name() const override
inline virtual std::string base() const override
inline double operator()(const query_t &a, const tag_t &b) const override

Public Static Functions

static inline double calculate(const query_t &a, const tag_t &b)
static inline double ProbabilityKBitSequence(const size_t k)
template<size_t Width>
struct ApproxDualStreakMetric : public BaseMetric<BitSet<Width>, BitSet<Width>>
#include <matchbin_metrics.hpp>

Matches based on longest streaks of equal and unequal bits in two bitsets. This implementation uses Incorrect Math from Downing’s Intelligence Emerging. Adapted from Downing, Keith L. Intelligence emerging: adaptivity and search in evolving neural systems. MIT Press, 2015.

Public Types

using query_t = BitSet<Width>
using tag_t = BitSet<Width>

Public Functions

inline virtual size_t dim() const override
inline virtual size_t width() const override
inline virtual std::string name() const override
inline virtual std::string base() const override
inline double operator()(const query_t &a, const tag_t &b) const override

Public Static Functions

static inline double calculate(const query_t &a, const tag_t &b)
static inline double ProbabilityKBitSequence(size_t k)
template<size_t N>
struct ExactStreakDistribution
#include <matchbin_metrics.hpp>

Compute the probability of K or more heads in a row out of N flips. Adapted from https://www.askamathematician.com/2010/07/q-whats-the-chance-of-getting-a-run-of-k-successes-in-n-bernoulli-trials-why-use-approximations-when-the-exact-answer-is-known/ Helper class for exact streak metrics

Public Functions

inline ExactStreakDistribution()
inline double GetStreakProbability(const size_t min_heads, const size_t num_coins = N) const
inline double CalcStreakProbability(const size_t min_heads, const size_t num_coins = N)

Public Members

robin_hood::unordered_map<std::tuple<size_t, size_t>, double, TupleHash<size_t, size_t>> computed = {}
template<size_t Width>
struct ExactDualStreakMetric : public BaseMetric<BitSet<Width>, BitSet<Width>>
#include <matchbin_metrics.hpp>

Matches based on longest streaks of equal and unequal bits in two bitsets. This implementation uses Corect Math adapted from https://www.askamathematician.com/2010/07/q-whats-the-chance-of-getting-a-run-of-k-successes-in-n-bernoulli-trials-why-use-approximations-when-the-exact-answer-is-known/ This metric is NOT uniformly distributed. Adapted from Downing, Keith L. Intelligence emerging: adaptivity and search in evolving neural systems. MIT Press, 2015.

Public Types

using query_t = BitSet<Width>
using tag_t = BitSet<Width>

Public Functions

inline virtual size_t dim() const override
inline virtual size_t width() const override
inline virtual std::string name() const override
inline virtual std::string base() const override
inline double operator()(const query_t &a, const tag_t &b) const override

Public Static Functions

static inline const ExactStreakDistribution<Width> &GetDistn()
static inline double calculate(const query_t &a, const tag_t &b)
template<size_t Width>
struct ExactSingleStreakMetric : public BaseMetric<BitSet<Width>, BitSet<Width>>
#include <matchbin_metrics.hpp>

Matches based on longest streak of equal bits in two bitsets. This implementation uses Corect Math adapted from https://www.askamathematician.com/2010/07/q-whats-the-chance-of-getting-a-run-of-k-successes-in-n-bernoulli-trials-why-use-approximations-when-the-exact-answer-is-known/ This metric is uniformly distributed. Adapted from Downing, Keith L. Intelligence emerging: adaptivity and search in evolving neural systems. MIT Press, 2015.

Public Types

using query_t = BitSet<Width>
using tag_t = BitSet<Width>

Public Functions

inline virtual size_t dim() const override
inline virtual size_t width() const override
inline virtual std::string name() const override
inline virtual std::string base() const override
inline double operator()(const query_t &a, const tag_t &b) const override

Public Static Functions

static inline const ExactStreakDistribution<Width> &GetDistn()
static inline double calculate(const query_t &a, const tag_t &b)
template<typename Metric, size_t MaxCapacity = 100000>
struct CacheMod : public Metric
#include <matchbin_metrics.hpp>

Public Types

using query_t = typename Metric::query_t
using tag_t = typename Metric::tag_t

Public Functions

inline std::string name() const override
inline double operator()(const query_t &a, const tag_t &b) const override

Public Members

Metric metric

Public Static Functions

static inline double calculate(const query_t &a, const tag_t &b)

Public Static Attributes

static robin_hood::unordered_map<std::tuple<query_t, tag_t>, double, TupleHash<query_t, tag_t>> cache
static std::queue<std::tuple<query_t, tag_t>> purge_queue
template<typename Metric>
struct SlideMod : public Metric
#include <matchbin_metrics.hpp>

Public Types

using query_t = typename Metric::query_t
using tag_t = typename Metric::tag_t

Public Functions

inline double operator()(const query_t &a, const tag_t &b) const override

Public Static Functions

static inline double calculate(const query_t &a, const tag_t &b)

Public Static Attributes

static size_t metric_width = {Metric{}.width()}
template<typename Metric>
struct HardStartMod : public Metric
#include <matchbin_metrics.hpp>

Public Types

using query_t = typename Metric::query_t
using tag_t = typename Metric::tag_t

Public Functions

inline std::string name() const override
inline double operator()(const query_t &a, const tag_t &b) const override

Public Members

Metric metric

Public Static Functions

static inline double calculate(const query_t &a, const tag_t &b)
template<typename Metric>
struct AntiMod : public Metric
#include <matchbin_metrics.hpp>

Public Types

using query_t = typename Metric::query_t
using tag_t = typename Metric::tag_t

Public Functions

inline double operator()(const query_t &a, const tag_t &b) const override

Public Members

Metric metric

Public Static Functions

static inline double calculate(const query_t &a, const tag_t &b)
template<typename Metric, typename Root>
struct PowMod : public Metric
#include <matchbin_metrics.hpp>

Public Types

using query_t = typename Metric::query_t
using tag_t = typename Metric::query_t

Public Functions

inline std::string name() const override
inline double operator()(const query_t &a, const tag_t &b) const override

Public Members

Metric metric

Public Static Functions

static inline double calculate(const query_t &a, const tag_t &b)
template<typename Metric, typename Base>
struct LogMod : public Metric
#include <matchbin_metrics.hpp>

Public Types

using query_t = typename Metric::query_t
using tag_t = typename Metric::query_t

Public Functions

inline std::string name() const override
inline double operator()(const query_t &a, const tag_t &b) const override

Public Members

Metric metric

Public Static Functions

static inline double calculate(const query_t &a, const tag_t &b)
template<typename Metric, size_t Samples = 10000>
struct UnifMod : public Metric
#include <matchbin_metrics.hpp>

Reshape metric’s probability distribution to be approximately uniform. Sample from the original distribution to create a percentile map, and then, at runtime, put raw matches through the percentile map to approximate a uniform distribution.

Public Types

using query_t = typename Metric::query_t
using tag_t = typename Metric::query_t

Public Functions

inline std::string name() const override
inline double operator()(const query_t &a, const tag_t &b) const override

Public Static Functions

static inline const internal::lookup_holder<Metric, Samples> &GetLookupHolder()
static inline double calculate(const query_t &a, const tag_t &b)
template<typename Metric, size_t Dim>
struct MeanDimMod : public BaseMetric<std::array<Metric::query_t, Dim>, std::array<Metric::tag_t, Dim>>
#include <matchbin_metrics.hpp>

Public Types

using query_t = std::array<typename Metric::query_t, Dim>
using tag_t = std::array<typename Metric::tag_t, Dim>

Public Functions

inline virtual size_t width() const override
inline virtual size_t dim() const override
inline virtual std::string name() const override
inline virtual std::string base() const override
inline double operator()(const query_t &a, const tag_t &b) const override

Public Members

Metric metric

Public Static Functions

static inline double calculate(const query_t &a, const tag_t &b)
template<typename Metric, size_t Dim>
struct EuclideanDimMod : public BaseMetric<std::array<Metric::query_t, Dim>, std::array<Metric::tag_t, Dim>>
#include <matchbin_metrics.hpp>

Public Types

using query_t = std::array<typename Metric::query_t, Dim>
using tag_t = std::array<typename Metric::tag_t, Dim>

Public Functions

inline virtual size_t width() const override
inline virtual size_t dim() const override
inline virtual std::string name() const override
inline virtual std::string base() const override
inline double operator()(const query_t &a, const tag_t &b) const override

Public Members

Metric metric

Public Static Functions

static inline double calculate(const query_t &a, const tag_t &b)
template<typename Metric, size_t Dim>
struct MinDimMod : public BaseMetric<std::array<Metric::query_t, Dim>, std::array<Metric::tag_t, Dim>>
#include <matchbin_metrics.hpp>

Public Types

using query_t = std::array<typename Metric::query_t, Dim>
using tag_t = std::array<typename Metric::tag_t, Dim>

Public Functions

inline virtual size_t width() const override
inline virtual size_t dim() const override
inline virtual std::string name() const override
inline virtual std::string base() const override
inline double operator()(const query_t &a, const tag_t &b) const override

Public Members

Metric metric

Public Static Functions

static inline double calculate(const query_t &a, const tag_t &b)
template<typename Metric, size_t Dim>
struct HarmonicDimMod : public BaseMetric<std::array<Metric::query_t, Dim>, std::array<Metric::tag_t, Dim>>
#include <matchbin_metrics.hpp>

Public Types

using query_t = std::array<typename Metric::query_t, Dim>
using tag_t = std::array<typename Metric::tag_t, Dim>

Public Functions

inline virtual size_t width() const override
inline virtual size_t dim() const override
inline virtual std::string name() const override
inline virtual std::string base() const override
inline double operator()(const query_t &a, const tag_t &b) const override

Public Members

Metric metric

Public Static Functions

static inline double calculate(const query_t &a, const tag_t &b)
template<typename DimMetric>
struct FlatMod : public BaseMetric<BitSet<std::tuple_size<DimMetric::query_t>::value * DimMetric::query_t::value_type::GetCTSize()>, BitSet<std::tuple_size<DimMetric::tag_t>::value * DimMetric::tag_t::value_type::GetCTSize()>>
#include <matchbin_metrics.hpp>

Public Types

using query_t = BitSet<std::tuple_size<typename DimMetric::query_t>::value * DimMetric::query_t::value_type::GetCTSize()>
using tag_t = BitSet<std::tuple_size<typename DimMetric::query_t>::value * DimMetric::tag_t::value_type::GetCTSize()>

Public Functions

inline virtual size_t width() const override
inline virtual size_t dim() const override
inline virtual std::string name() const override
inline virtual std::string base() const override
inline double operator()(const query_t &a, const tag_t &b) const override

Public Static Functions

static inline double calculate(const query_t &a, const tag_t &b)

Public Static Attributes

static DimMetric metric = {}