Usage

Installation

$ git clone https://github.com/facebookresearch/LA-MCTS.git
$ cd LA-MCTS
$ pip install -e .

API References

Function Interfaces

class lamcts.Func

Bases: abc.ABC

Function interface to be implemented by the client

cleanup()
compare(fx1: float, fx2: float, margin: float = 0.0) → int

To compare two outputs, based on if one is “better” than the other. :param fx1: output 1 :param fx2: output 2 :param margin: if two outputs are within margin, they are considered equal :return: < 0, if fx1 is worse than fx2; == 0 if equal; > 0 if better

abstract property dims: int

Dimension of the input :return:

empty_bag()

Create an empty bag based on the function properties :return:

gen_random_inputs(num_inputs: int, lb: Optional[numpy.ndarray] = None, ub: Optional[numpy.ndarray] = None) → numpy.ndarray

To generate random inputs using latin hypercube

Parameters

  • num_inputs – number of inputs to be generated

  • lb – if given, generated inputs are floored by lb

  • ub – if given, generated inputs are ceilinged by up

Returns

gen_sample_bag(xs: Optional[numpy.ndarray] = None) → lamcts.type.Bag
input_equal(i1: numpy.ndarray, i2: numpy.ndarray) → bool

To test if two inputs are equal

Parameters

  • i1 – input 1

  • i2 – input 2

Returns

property is_discrete: numpy.ndarray

Whether the input is discrete :return: bool or an array of bool

property is_minimizing: bool

Whether the goal is to minimize or maximize the result :return:

abstract property lb: numpy.ndarray

Lower bounds of each dimension :return: numpy array of shape (dims,)

mcts_params(sampler: lamcts.config.config.SamplerEnum = SamplerEnum.RANDOM_SAMPLER, classifier: lamcts.config.config.ClassifierEnum = ClassifierEnum.KMEAN_SVM_CLASSIFIER) → Dict
transform_input(xs: numpy.ndarray) → numpy.ndarray
abstract property ub: numpy.ndarray

Upper bounds of each dimension :return: numpy array of shape (dims,)

class lamcts.CheckPoint(call_mark, time_mark, x, fx)
call_mark: int

Alias for field number 0

fx: float

Alias for field number 3

time_mark: float

Alias for field number 1

x: Union[numpy.ndarray, List]

Alias for field number 2

lamcts.CallHistory

alias of List[lamcts.func.CheckPoint]

class lamcts.FuncStats

Bases: abc.ABC

Interface to track call statistics

class Stats(is_minimizing: bool = True)

Bases: object

add_stat(xs: numpy.ndarray, fxs: numpy.ndarray, call_time: float)
property call_history: List[lamcts.func.CheckPoint]
property total_call_time: float
property total_calls: int
abstract property stats: lamcts.func.FuncStats.Stats
class lamcts.StatsFuncWrapper(func: lamcts.func.Func)

Bases: lamcts.func.FuncDecorator, lamcts.func.FuncStats

A convenient wrapper of Func, to provide stats tracking

cleanup()
property stats: lamcts.func.FuncStats.Stats

MCTS

class lamcts.MCTS(func: lamcts.func.Func, func_stats: lamcts.func.FuncStats, num_init_samples: int = 100, cp: float = 1.0, cb_base: lamcts.config.config.ConfidencyBase = ConfidencyBase.Mean, leaf_size: int = 20, num_samples_per_sampler: int = 200, classifier_factory: Optional[lamcts.type.ObjectFactory[lamcts.classifier.classifier.Classifier]] = None, num_split_worker: int = 1, sampler: Optional[lamcts.sampler.sampler.Sampler] = None, search_type: lamcts.config.config.SearchType = SearchType.Vertical, device: str = 'cpu')

Bases: object

LaMCTS implementation, refer to the paper for more details

Parameters

  • func – function to be optimized

  • func_stats – stats to track function calling history

  • num_init_samples – initial number of samples to draw

  • cp – parameter controlling exploration

  • cb_base – confident bound base - 0: mean, 1: best

  • leaf_size – number of samples hold by a leaf

  • num_samples_per_sampler – how many samples to draw at each iteration

  • classifier_factory – object factory to create classifiers

  • num_split_worker – number of workers to build search tree

  • sampler – sampler

  • search_type – Vertical - from root to leaf, horizontal - all leaves

  • device –

DEFAULT_CB_BASE = 0
DEFAULT_CP = 1.0
DEFAULT_GAMMA_TYPE = 'auto'
DEFAULT_KERNAL_TYPE = 'rbf'
DEFAULT_KMEAN_SVM_CLASSIFIER_PARAM = {'gamma': 'auto', 'kernel': 'rbf', 'scaler': 'standard', 'use_features': False}
DEFAULT_LEAF_SIZE = 20
DEFAULT_NUM_INIT_SAMPLES = 100
DEFAULT_NUM_SAMPLES_PER_SAMPLER = 200
DEFAULT_SAMPLER_CONFIG = {'params': {'batch_size': 10, 'num_init_samples': 20}, 'type': 'turbo'}
DEFAULT_SOLVER_TYPE = 'turbo'
static create_mcts(func: lamcts.func.Func, func_stats: lamcts.func.FuncStats, params: Dict) → lamcts.mcts.MCTS
init_tree()
search(greedy: lamcts.config.config.GreedyType = GreedyType.ConfidencyBound, call_budget: float = inf) → Tuple

Search for optimal solution

Parameters

  • greedy – < 0 random; == 0 using confidence bound; == 1 using mean; == 2 using best sample

  • call_budget –

Returns

best sample found

property stats: Tuple

Classifiers

class lamcts.classifier.Classifier

A classifier to separate input bag into clusters

abstract classify(bag: lamcts.type.Bag) → Optional[numpy.ndarray]

Classify input bag into clusters :param bag: input (rows, features) :return: label of each row of input (rows,)

abstract predict(xs: numpy.ndarray) → numpy.ndarray

Predict which cluster input belongs to :param xs: (rows, features) :return: labels of each row of input (rows,)

class lamcts.classifier.SvmClassifier(lb: numpy.ndarray, ub: numpy.ndarray, svm='svc', kernel='rbf', gamma='auto', scaler='', use_features=False)

Bases: lamcts.classifier.classifier.Classifier

A classifier using SVM for boundary, refer: https://scikit-learn.org/0.24/modules/generated/sklearn.svm.SVC.html for parameter details

Parameters

  • lb – lower bounds of the inputs

  • ub – upper bounds of the inputs

  • svm – “svr” or “svc”

  • kernel – “linear”, “poly”, “rbf”, “sigmoid” or “precomputed”

  • gamma – “scale” or “auto”

  • scaler – input preprocessing scaler, “standard” or “minmx” or empty for no scalers

classify(bag: lamcts.type.Bag) → numpy.ndarray

Classify input bag into clusters :param bag: input (rows, features) :return: label of each row of input (rows,)

predict(xs: numpy.ndarray) → numpy.ndarray

Predict which cluster input belongs to :param xs: (rows, features) :return: labels of each row of input (rows,)

class lamcts.classifier.KmeanSvmClassifier(lb: numpy.ndarray, ub: numpy.ndarray, svm='svc', kernel='rbf', gamma='auto', scaler='', use_features=False)

Bases: lamcts.classifier.svm_classifier.SvmClassifier

A classifier using KMean for cluster and SVM for boundary

class lamcts.classifier.ThresholdSvmClassifier(lb: numpy.ndarray, ub: numpy.ndarray, threshold_type: lamcts.config.config.ThresholdType = ThresholdType.Median, svm='svc', kernel='rbf', gamma='auto', scaler='', use_features=False)

Bases: lamcts.classifier.svm_classifier.SvmClassifier

A classifier using threshold (median or mean) to divide samples and SVM for boundary

class lamcts.classifier.RegressionSvmClassifier(lb: numpy.ndarray, ub: numpy.ndarray, threshold_type: lamcts.config.config.ThresholdType = ThresholdType.Median, regressor: str = 'ridge', svm='svc', kernel='rbf', gamma='auto', scaler='', use_features=False)

Bases: lamcts.classifier.svm_classifier.SvmClassifier

A classifier using a regressor to fit samples, then threshold (median or mean) to divide samples, and SVM for boundary

Samplers

class lamcts.sampler.Sampler(func: lamcts.func.Func, func_stats: lamcts.func.FuncStats)

Bases: abc.ABC

Interface for samplers, a.k.a, optimizers or solvers

abstract sample(num_samples: int, path: Optional[lamcts.node.Path] = None, **kwargs) → lamcts.type.Bag

Generate num_samples samples, on the leaf node of the path (if not none) :param num_samples: :param path: path from root to leaf :param kwargs: :return: sample bag

class lamcts.sampler.RandomSampler(func: lamcts.func.Func, func_stats: lamcts.func.FuncStats)

Bases: lamcts.sampler.sampler.Sampler

TOTAL_RETRIES: ClassVar[int] = 50
sample(num_samples: int, path: Optional[lamcts.node.Path] = None, **kwargs) → lamcts.type.Bag

Randomly sample num_samples. If path is given, samples are filtered by all SVM regions along the path

Parameters

  • num_samples –

  • path –

  • kwargs –

Returns

class lamcts.sampler.BOSampler(func: lamcts.func.Func, func_stats: lamcts.func.FuncStats, acquisition: str = 'ei', nu: float = 1.5, gp_num_cands: int = 0, gp_max_samples: int = 0, batch_size: int = 0)

Bases: lamcts.sampler.random_sampler.RandomSampler

sample(num_samples: int, path: Optional[lamcts.node.Path] = None, **kwargs) → lamcts.type.Bag

Randomly sample num_samples. If path is given, samples are filtered by all SVM regions along the path

Parameters

  • num_samples –

  • path –

  • kwargs –

Returns

class lamcts.sampler.TuRBOSampler(func: lamcts.func.Func, func_stats: lamcts.func.FuncStats, acquisition: str = 'ei', nu: float = 1.5, gp_max_samples: int = 0, gp_num_cands: int = 0, gp_training_steps: int = 50, gp_max_cholesky_size: int = 2000, batch_size: int = 5, init_tr_length: float = 0.8, min_tr_length: float = 0.0078125, max_tr_length: float = 1.6, tr_length_multiplier: float = 2.0, fail_threshold: int = 3, succ_threshold: int = 3, device: str = 'cuda')

Bases: lamcts.sampler.random_sampler.RandomSampler

sample(num_samples: int, path: Optional[lamcts.node.Path] = None, **kwargs) → lamcts.type.Bag

Randomly sample num_samples. If path is given, samples are filtered by all SVM regions along the path

Parameters

  • num_samples –

  • path –

  • kwargs –

Returns

class lamcts.sampler.CmaesSampler(func: lamcts.func.Func, func_stats: lamcts.func.FuncStats, **kwargs)

Bases: lamcts.sampler.sampler.Sampler

sample(num_samples: int, path: Optional[lamcts.node.Path] = None, **kwargs) → lamcts.type.Bag

Generate num_samples samples, on the leaf node of the path (if not none) :param num_samples: :param path: path from root to leaf :param kwargs: :return: sample bag

class lamcts.sampler.NevergradSampler(func: lamcts.func.Func, func_stats: lamcts.func.FuncStats, sample_center: lamcts.config.config.SampleCenter = SampleCenter.Median)

Bases: lamcts.sampler.random_sampler.RandomSampler

sample(num_samples: int, path: Optional[lamcts.node.Path] = None, **kwargs) → lamcts.type.Bag

Randomly sample num_samples. If path is given, samples are filtered by all SVM regions along the path

Parameters

  • num_samples –

  • path –

  • kwargs –

Returns

Utilies

class lamcts.Sample(x, fx, feature)
feature: numpy.ndarray

Associated features (optional)

fx: float

Function value

x: numpy.ndarray

Input

class lamcts.Bag(xs: Union[numpy.ndarray, int], fxs: numpy.ndarray = array([], dtype=float64), features: Optional[numpy.ndarray] = None, is_minimizing: bool = False, is_discrete: Optional[numpy.ndarray] = None)

Bases: object

append(sample: lamcts.type.Sample) → bool
property best: lamcts.type.Sample
clear() → Any
clone() → lamcts.type.Bag
property dims: int
extend(other) → bool
property features: Optional[numpy.ndarray]
property fxs: numpy.ndarray
property is_discrete: numpy.ndarray
property is_minimizing: bool
property mean: float
remove_duplicate(xs: numpy.ndarray) → Tuple[numpy.ndarray, numpy.ndarray]
trim(size: int) → Any
property x_bounds: Tuple[numpy.ndarray, numpy.ndarray]
x_confidence_bounds(z: float = 1.0) → Tuple[numpy.ndarray, numpy.ndarray]
property xs: numpy.ndarray

Configuration

class lamcts.config.SearchType(value)

Bases: enum.Enum

Search type, depth first (Vertical) or breadth first (Horizontal)

Horizontal = 1
Vertical = 0
class lamcts.config.SamplerEnum(value)

Bases: enum.Enum

Enums for builtin samplers

BO_SAMPLER = 'bo'
CMAES_SAMPLER = 'cmaes'
NEVERGRAD_SAMPLER = 'nevergrad'
RANDOM_SAMPLER = 'random'
TURBO_SAMPLER = 'turbo'
class lamcts.config.ClassifierEnum(value)

Bases: enum.Enum

Enums for builtin classifiers

KMEAN_SVM_CLASSIFIER = 'kmean_svm'
REGRESSION_SVM_CLASSIFIER = 'regression_svm'
THRESHOLD_SVM_CLASSIFIER = 'threshold_svm'
lamcts.config.get_mcts_params(sampler: lamcts.config.config.SamplerEnum = SamplerEnum.RANDOM_SAMPLER, classifier: lamcts.config.config.ClassifierEnum = ClassifierEnum.KMEAN_SVM_CLASSIFIER)

Generate a template for MCTS configuration

Parameters

  • sampler – Sampler to use

  • classifier – Classifier to use

Returns

MCTS configuration