{ "cells": [ { "cell_type": "markdown", "id": "eb2cd418", "metadata": {}, "source": [ "# The Search Space\n", "\n", "The [`SearchSpace`](../cpp_api/search_space.html) holds the terminals and operators used to define programs, and includes utilities for creating programs and modifying them. \n", "It has a few basic components:\n", "\n", "- `node_map`: this object maps function signatures to specific node types. It is a nested map, made to most quickly match on return types first, then full signatures. It is structured this way to mutations and crossover lookups fast. \n", "- `terminal_map`: same as `node_map` but for terminals. \n", "\n", "Both of these maps have associated weights that are used to weight the probabilities of each operator/terminal being sampled. \n", "Users can optionally provide these weights." ] }, { "cell_type": "markdown", "id": "429d810b", "metadata": {}, "source": [ "## Initializing\n", "\n", "At a minimum, initializing the search space requires that a `Dataset` is already defined, so that `SearchSpace` knows how to define the terminals. " ] }, { "cell_type": "code", "execution_count": 1, "id": "b667948a", "metadata": {}, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
idsexracetarget
count993.00000993.000000993.000000993.000000
mean496.000000.4874122.6253788.219092
std286.798710.5000931.7252401.101319
min0.000000.0000000.0000001.337280
25%248.000000.0000001.0000007.836757
50%496.000000.0000003.0000008.404038
75%744.000001.0000004.0000008.810710
max992.000001.0000005.00000011.410597
\n", "
" ], "text/plain": [ " id sex race target\n", "count 993.00000 993.000000 993.000000 993.000000\n", "mean 496.00000 0.487412 2.625378 8.219092\n", "std 286.79871 0.500093 1.725240 1.101319\n", "min 0.00000 0.000000 0.000000 1.337280\n", "25% 248.00000 0.000000 1.000000 7.836757\n", "50% 496.00000 0.000000 3.000000 8.404038\n", "75% 744.00000 1.000000 4.000000 8.810710\n", "max 992.00000 1.000000 5.000000 11.410597" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "import pandas as pd\n", "from pybrush import Dataset, SearchSpace\n", "\n", "df = pd.read_csv('../examples/datasets/d_example_patients.csv')\n", "X = df.drop(columns='target')\n", "y = df['target']\n", "\n", "df.describe()" ] }, { "cell_type": "code", "execution_count": 2, "id": "6d563aae", "metadata": {}, "outputs": [], "source": [ "data = Dataset(X,y)\n", "\n", "search_space = SearchSpace(data)" ] }, { "cell_type": "markdown", "id": "d3e4128c", "metadata": {}, "source": [ "By default, the search space includes all available operators that have at least one argument type matching a datatype in `Data`. \n", "That can be quite large. \n", "\n", "Instead, the user may specify operators with weightings that determine the probability of being sampled, i.e. " ] }, { "cell_type": "code", "execution_count": 3, "id": "23d6f552", "metadata": {}, "outputs": [], "source": [ "user_ops = {\n", " 'Add': 0.5,\n", " 'Sub': 0.5,\n", " 'Mul': 1.0,\n", " 'Div': 0.1,\n", " 'SplitBest':0.1,\n", " 'SplitOn':0.1\n", "}\n", "\n", "search_space = SearchSpace(data, user_ops)\n" ] }, { "cell_type": "markdown", "id": "7ebde83f", "metadata": {}, "source": [ "## Inspecting" ] }, { "cell_type": "markdown", "id": "551a450b", "metadata": {}, "source": [ "We now have a much smaller search space. To view it, call `print()`:" ] }, { "cell_type": "code", "execution_count": 4, "id": "a2953719", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "=== Search space ===\n", "terminal_map: {\"ArrayI\": [\"x_2\", \"1.00\"], \"ArrayB\": [\"x_1\"], \"ArrayF\": [\"x_0\", \"1.00\"]}\n", "terminal_weights: {\"ArrayI\": [0.01214596, 0.01214596], \"ArrayB\": [0.026419641], \"ArrayF\": [0.056145623, 0.056145623]}\n", "SplitOn node_map[ArrayB][[\"ArrayB\", \"ArrayB\", \"ArrayB\"]][SplitOn] = SplitOn, weight = 0.1\n", "SplitBest node_map[ArrayB][[\"ArrayB\", \"ArrayB\"]][SplitBest] = SplitBest, weight = 0.1\n", "SplitOn node_map[ArrayI][[\"ArrayB\", \"ArrayI\", \"ArrayI\"]][SplitOn] = 1.00*SplitOn, weight = 0.1\n", "Div node_map[ArrayI][[\"ArrayI\", \"ArrayI\"]][Div] = 1.00*Div, weight = 0.1\n", "Mul node_map[ArrayI][[\"ArrayI\", \"ArrayI\"]][Mul] = 1.00*Mul, weight = 1\n", "SplitBest node_map[ArrayI][[\"ArrayI\", \"ArrayI\"]][SplitBest] = 1.00*SplitBest, weight = 0.1\n", "Sub node_map[ArrayI][[\"ArrayI\", \"ArrayI\"]][Sub] = 1.00*Sub, weight = 0.5\n", "Add node_map[ArrayI][[\"ArrayI\", \"ArrayI\"]][Add] = 1.00*Add, weight = 0.5\n", "SplitOn node_map[ArrayF][[\"ArrayB\", \"ArrayF\", \"ArrayF\"]][SplitOn] = 1.00*SplitOn, weight = 0.1\n", "Div node_map[ArrayF][[\"ArrayF\", \"ArrayF\"]][Div] = 1.00*Div, weight = 0.1\n", "Mul node_map[ArrayF][[\"ArrayF\", \"ArrayF\"]][Mul] = 1.00*Mul, weight = 1\n", "SplitBest node_map[ArrayF][[\"ArrayF\", \"ArrayF\"]][SplitBest] = 1.00*SplitBest, weight = 0.1\n", "Sub node_map[ArrayF][[\"ArrayF\", \"ArrayF\"]][Sub] = 1.00*Sub, weight = 0.5\n", "Add node_map[ArrayF][[\"ArrayF\", \"ArrayF\"]][Add] = 1.00*Add, weight = 0.5\n", "\n" ] } ], "source": [ "search_space.print()" ] }, { "cell_type": "markdown", "id": "cdcee683", "metadata": {}, "source": [ "## Initializing sampling probabilities\n", "\n", "The search space will create the terminals based on each input feature.\n", "\n", "Brush lets you start the execution with uniformly initialized weights for sampling terminals when creating or mutating programs or pre-calculating sampling probabilities based on correlations with the target variable.\n", "\n", "These weights will affect the occurrence of each terminal in the programs during the run.\n", "\n", "You can enable this feature by setting `weights_init=True`. This setting is true by default.\n", "\n", "Below we show the search space with the weights off." ] }, { "cell_type": "code", "execution_count": 5, "id": "77d94281", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "=== Search space ===\n", "terminal_map: {\"ArrayI\": [\"x_2\", \"1.00\"], \"ArrayB\": [\"x_1\"], \"ArrayF\": [\"x_0\", \"1.00\"]}\n", "terminal_weights: {\"ArrayI\": [1, 1], \"ArrayB\": [1], \"ArrayF\": [1, 1]}\n", "SplitOn node_map[ArrayB][[\"ArrayB\", \"ArrayB\", \"ArrayB\"]][SplitOn] = SplitOn, weight = 0.1\n", "SplitBest node_map[ArrayB][[\"ArrayB\", \"ArrayB\"]][SplitBest] = SplitBest, weight = 0.1\n", "SplitOn node_map[ArrayI][[\"ArrayB\", \"ArrayI\", \"ArrayI\"]][SplitOn] = 1.00*SplitOn, weight = 0.1\n", "Div node_map[ArrayI][[\"ArrayI\", \"ArrayI\"]][Div] = 1.00*Div, weight = 0.1\n", "Mul node_map[ArrayI][[\"ArrayI\", \"ArrayI\"]][Mul] = 1.00*Mul, weight = 1\n", "SplitBest node_map[ArrayI][[\"ArrayI\", \"ArrayI\"]][SplitBest] = 1.00*SplitBest, weight = 0.1\n", "Sub node_map[ArrayI][[\"ArrayI\", \"ArrayI\"]][Sub] = 1.00*Sub, weight = 0.5\n", "Add node_map[ArrayI][[\"ArrayI\", \"ArrayI\"]][Add] = 1.00*Add, weight = 0.5\n", "SplitOn node_map[ArrayF][[\"ArrayB\", \"ArrayF\", \"ArrayF\"]][SplitOn] = 1.00*SplitOn, weight = 0.1\n", "Div node_map[ArrayF][[\"ArrayF\", \"ArrayF\"]][Div] = 1.00*Div, weight = 0.1\n", "Mul node_map[ArrayF][[\"ArrayF\", \"ArrayF\"]][Mul] = 1.00*Mul, weight = 1\n", "SplitBest node_map[ArrayF][[\"ArrayF\", \"ArrayF\"]][SplitBest] = 1.00*SplitBest, weight = 0.1\n", "Sub node_map[ArrayF][[\"ArrayF\", \"ArrayF\"]][Sub] = 1.00*Sub, weight = 0.5\n", "Add node_map[ArrayF][[\"ArrayF\", \"ArrayF\"]][Add] = 1.00*Add, weight = 0.5\n", "\n" ] } ], "source": [ "search_space_off = SearchSpace(data, user_ops, weights_init=False)\n", "search_space_off.print()" ] }, { "cell_type": "markdown", "id": "b02a700b", "metadata": {}, "source": [ "Note that the `node_map` includes two `SplitBest` operators: one with the signature `ArrayI(ArrayI, ArrayI)` and one with the signature `ArrayF(ArrayF, ArrayF)`. \n", "This is because our dataset contains both interger and floating point data types. \n", "Note also that the default behavior is to give both of these nodes the same weight as specified by the user. " ] }, { "cell_type": "markdown", "id": "ca903d90", "metadata": {}, "source": [ "## Loading datatypes\n", "\n", "If you pass a numpy array, Brush will try to infer datatypes based on its values.\n", "If instead of passing the data directly you rather pass a pandas dataframe, then it will use the data types retrieved from the powerful pandas sniffer to use as its own data type." ] }, { "cell_type": "code", "execution_count": 6, "id": "1c8c72c1", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "=== Search space ===\n", "terminal_map: {\"ArrayI\": [\"x_2\", \"1.00\"], \"ArrayB\": [\"x_1\"], \"ArrayF\": [\"x_0\", \"1.00\"]}\n", "terminal_weights: {\"ArrayI\": [0.01214596, 0.01214596], \"ArrayB\": [0.026419641], \"ArrayF\": [0.056145623, 0.056145623]}\n", "SplitOn node_map[ArrayB][[\"ArrayB\", \"ArrayB\", \"ArrayB\"]][SplitOn] = SplitOn, weight = 0.1\n", "SplitBest node_map[ArrayB][[\"ArrayB\", \"ArrayB\"]][SplitBest] = SplitBest, weight = 0.1\n", "SplitOn node_map[ArrayI][[\"ArrayB\", \"ArrayI\", \"ArrayI\"]][SplitOn] = 1.00*SplitOn, weight = 0.1\n", "Div node_map[ArrayI][[\"ArrayI\", \"ArrayI\"]][Div] = 1.00*Div, weight = 0.1\n", "Mul node_map[ArrayI][[\"ArrayI\", \"ArrayI\"]][Mul] = 1.00*Mul, weight = 1\n", "SplitBest node_map[ArrayI][[\"ArrayI\", \"ArrayI\"]][SplitBest] = 1.00*SplitBest, weight = 0.1\n", "Sub node_map[ArrayI][[\"ArrayI\", \"ArrayI\"]][Sub] = 1.00*Sub, weight = 0.5\n", "Add node_map[ArrayI][[\"ArrayI\", \"ArrayI\"]][Add] = 1.00*Add, weight = 0.5\n", "SplitOn node_map[ArrayF][[\"ArrayB\", \"ArrayF\", \"ArrayF\"]][SplitOn] = 1.00*SplitOn, weight = 0.1\n", "Div node_map[ArrayF][[\"ArrayF\", \"ArrayF\"]][Div] = 1.00*Div, weight = 0.1\n", "Mul node_map[ArrayF][[\"ArrayF\", \"ArrayF\"]][Mul] = 1.00*Mul, weight = 1\n", "SplitBest node_map[ArrayF][[\"ArrayF\", \"ArrayF\"]][SplitBest] = 1.00*SplitBest, weight = 0.1\n", "Sub node_map[ArrayF][[\"ArrayF\", \"ArrayF\"]][Sub] = 1.00*Sub, weight = 0.5\n", "Add node_map[ArrayF][[\"ArrayF\", \"ArrayF\"]][Add] = 1.00*Add, weight = 0.5\n", "\n" ] } ], "source": [ "data = Dataset(X.values, y.values)\n", "\n", "search_space = SearchSpace(data, user_ops)\n", "search_space.print()" ] }, { "cell_type": "markdown", "id": "e9799b3a", "metadata": {}, "source": [ "The regressor contains an engine, responsible for running the search.\n", "\n", "The engine will have its own instance of the search space.You can access the search space from the regressor with the following:" ] }, { "cell_type": "markdown", "id": "23b173bf", "metadata": {}, "source": [ "## Automatically updating sampling probabilities with multi-armed bandits\n", "\n", "Brush has a reinforcement learning agent implemented on the C++ backend that will observe which terminals are making the programs better or worse regarding the user-defined objectives and update the sampling probabilities.\n", "\n", "To enable it, you must set `bandit=\"thompson\"` if you want to have a global static probability used during the entire search, or `bandit=\"dynamic_thompson\"` if you want to use a policy that gives more importance to recent observed results and sets a lower importance to older generations." ] }, { "cell_type": "code", "execution_count": 7, "id": "3a68b9eb", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Completed 100% [====================]\n", "Best model: If(x_0>=1.00,Sub(8.32,0.00*x_0),9.04)\n", "score: 0.003572196870614497\n" ] } ], "source": [ "from pybrush import BrushRegressor\n", "\n", "est = BrushRegressor(\n", " functions=user_ops,\n", " max_gens=20,\n", " objectives=[\"scorer\", \"linear_complexity\"],\n", " weights_init=True,\n", " bandit=\"dynamic_thompson\",\n", " verbosity=1\n", ")\n", "\n", "est.fit(X.values,y.values)\n", "\n", "print(\"Best model:\", est.best_estimator_.get_model())\n", "print('score:', est.score(X,y))" ] }, { "cell_type": "code", "execution_count": 8, "id": "bcfc0903", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "=== Search space ===\n", "terminal_map: {\"ArrayI\": [\"x_2\", \"1.00\"], \"ArrayB\": [\"x_1\"], \"ArrayF\": [\"x_0\", \"1.00\"]}\n", "terminal_weights: {\"ArrayI\": [0.27175248, 0.07708182], \"ArrayB\": [0.5928491], \"ArrayF\": [0.30130994, 0.60325474]}\n", "SplitOn node_map[ArrayB][[\"ArrayB\", \"ArrayB\", \"ArrayB\"]][SplitOn] = SplitOn, weight = 0.59618497\n", "SplitBest node_map[ArrayB][[\"ArrayB\", \"ArrayB\"]][SplitBest] = SplitBest, weight = 0.2912048\n", "SplitOn node_map[ArrayI][[\"ArrayB\", \"ArrayI\", \"ArrayI\"]][SplitOn] = 1.00*SplitOn, weight = 0.32809982\n", "Div node_map[ArrayI][[\"ArrayI\", \"ArrayI\"]][Div] = 1.00*Div, weight = 0.1448153\n", "Mul node_map[ArrayI][[\"ArrayI\", \"ArrayI\"]][Mul] = 1.00*Mul, weight = 0.5934199\n", "Add node_map[ArrayI][[\"ArrayI\", \"ArrayI\"]][Add] = 1.00*Add, weight = 0.59812796\n", "Sub node_map[ArrayI][[\"ArrayI\", \"ArrayI\"]][Sub] = 1.00*Sub, weight = 0.78607696\n", "SplitBest node_map[ArrayI][[\"ArrayI\", \"ArrayI\"]][SplitBest] = 1.00*SplitBest, weight = 0.7199181\n", "SplitOn node_map[ArrayF][[\"ArrayB\", \"ArrayF\", \"ArrayF\"]][SplitOn] = 1.00*SplitOn, weight = 0.55268025\n", "Div node_map[ArrayF][[\"ArrayF\", \"ArrayF\"]][Div] = 1.00*Div, weight = 0.82452416\n", "Mul node_map[ArrayF][[\"ArrayF\", \"ArrayF\"]][Mul] = 1.00*Mul, weight = 0.60206795\n", "Add node_map[ArrayF][[\"ArrayF\", \"ArrayF\"]][Add] = 1.00*Add, weight = 0.4405351\n", "Sub node_map[ArrayF][[\"ArrayF\", \"ArrayF\"]][Sub] = 1.00*Sub, weight = 0.6042208\n", "SplitBest node_map[ArrayF][[\"ArrayF\", \"ArrayF\"]][SplitBest] = 1.00*SplitBest, weight = 0.34729484\n", "\n" ] } ], "source": [ "est.engine_.search_space.print()" ] }, { "cell_type": "code", "execution_count": 9, "id": "e876b1c0", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "If(x_0>=1.00)\n", "|- Sub\n", "| |- 8.32\n", "| |- 0.00*x_0\n", "|- 9.04\n" ] } ], "source": [ "print(est.best_estimator_.get_model(\"tree\"))" ] }, { "cell_type": "markdown", "id": "d662c5a7", "metadata": {}, "source": [ "## Sampling\n", "\n", "TODO. For now, see the mutation and crossover functions in the [Program](../cpp_api/program.html) class." ] } ], "metadata": { "kernelspec": { "display_name": "brush", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.13.5" } }, "nbformat": 4, "nbformat_minor": 5 }