{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Dimension adaptive sampling tutorial\n", "\n", "Here, briefly describe the concept behind dimension-adaptive sparse grids, starting from a standard Stochastic Collocation (SC) campaign. Following this, a dimension adaptive EasyVVUQ script using a simple analytic test function is presented. We will assume you are familiar with the basics of EasyVVUQ.\n", "\n", "## Standard SC\n", "\n", "In a standard EasyVVUQ Campaign, a Stochastic Collocation sampler object might be created via::\n", "\n", "```python\n", "sampler = uq.sampling.SCSampler(vary=vary, polynomial_order=2)\n", "```\n", "Here the specified `polynomial_order`, and the number of inputs in `vary`, determine the\n", "number of samples, which increases exponentially fast with an increasing amount of inputs. This\n", "is the so-called *curse of dimensionality*. \n", "\n", "Basically, by setting `polynomial_order=2` we create a sampling plan through a single tensor product of one-dimensional quadrature nodes with order 3 for every input. It is this tensor product construction that leads to the exponential rise in cost. So if we have 2 inputs `x1` and `x2`, and our one-dimensional quadrature rule of order 2 produces 5 points, we obtain a total of 25 points in the `(x1, x2)` domain. Likewise, if `vary` contains 3 inputs, we would need to evaluate the computational model 125 times, and 10 inputs would require `5**10 = 9765625` model evaluations. For this reason, a standard SC campaign is rarely used beyond 6 or 7 inputs.\n", "\n", "## Sparse SC\n", "\n", "Sparse grids on the other hand, do not create a single tensor product, but build the sampling plan from the ground up by using a *linear combination of tensor products involving 1D quadrature rules of* ***different*** *orders*. \n", "\n", "For two inputs, we might for instance consider using 1D quadrature rules of order [0, 0], [0, 1] and [1, 0], where:\n", "\n", " * [0, 0]: a single point in the 2D domain (x1, x2)\n", " * [0, 1]: a line of 3 points with constant x1\n", " * [1, 0]: a line of 3 points with constant x2\n", "\n", "In the case of sparse grids it is common to select a *nested* quadrature rule. This means that the quadrature\n", "rule of order p contains all points of the same rule of order p-1. When taking the linear combinations, a nested rule ensures that many points will conincide, which yields efficient sampling \n", "plans, especially in higher dimensions. If our nested 1D rule of order 1 and 2 generates the points [0.5] and [0, 0.5, 1] we obtain a sampling plan consisting of\n", "\n", " * [0, 0]: [0.5, 0.5]\n", " * [0, 1]: [0.5, 0.0], [0.5, 0.5], [0.5, 1.0]\n", " * [1, 0]: [0.0, 0.5], [0.5, 0.5], [1.0, 0.5],\n", "\n", "which gives a total of 5 unique points, compared to a corresponding standard SC campaign with [1, 1], which would generate 9 unique points (`[0, 0.5, 1] x [0, 0.5, 1.0]`). Note that sparse grids do **not** circumvent the curse of dimensionality, although they can postpone its effect to higher dimensions.\n", "\n", "## Dimension-adaptive SC\n", "\n", "What we described above is an *isotropic* sparse grid, since the multi indices `[0, 0], [1, 0], [0,1]` result in a sampling plan where both inputs end up with the same number of samples. However, in practice model parameters are rarely equally important. The idea behind dimension-adaptive sampling is to build the sampling plan in an iterative fashion, find out which (combination of) parameters are important as we go, and then place more samples along those directions. This results in a anisotropic sampling plan, where the important inputs get relatively high number of samples. To find out which directions are important we need an appropriate error measure, and we need to split the quadrature order multi indices in an *accepted* and an *admissible* set. The accepted set is initialized to `[0, 0]` in 2D, i.e. we start with just a single code evaluation. Without going into detail, we can think of the admissible set as the candidate refinement directions, from which we must add a single entry to the accepted set at every iteration.\n", "\n", "In our 2D example, at the 1st iteration the candidate set consists of `[1, 0]` and `[0, 1]`. That is, we can either refine only `x1` or only `x2`. We must select the multi index which generates the highest error when added to the accepted set. There are a variety of error measures, the two main ones in EasyVVUQ are:\n", "\n", "1. the hierarchical surplus error, and\n", "2. a variance-based error.\n", "\n", "Roughly speaking, the surplus is an interpolation based error, which measures the difference between the code output and the corresponding SC polynomial surrogate, when evaluated at new sample locations. The variance-based error selects the direction in which the variance in the output changes the most. For more information we refer to the references below.\n", "\n", "Assume that `[1, 0]` generated the highest error, and so it is added to the accepted set, now consisting of `[0, 0]` and `[1, 0]`. This means that `x1` has more points than `x2`. Also, adding a multi index to the accepted set means that the admissible set changes. In this case, since `[1, 0]` has been accepted, `[2, 0]` has become admissible. Note that the new entry `[2, 0]` also requires new evaluations of the code, and so a new ensemble must be submitted. Again, if we use a nested rule, the grid of `[2, 0]` will have a partial overlap with the accepted points, so we only have to evaluate the code at the new points, *not* all points of `[2, 0]`.\n", "\n", "Thus, the admissible set now consists of `[0, 1]` and `[2, 0]`. Hence, we now have to option of refining `x1` again (to second order), or refining `x2` to first order. Assume the latter happens. As both `x1` and `x2` have been refined to 1st order, `[1, 1]` has become admissible. If accepted, this multi index results in a *simultaneous* refinement of both `x1` and `x2`. Note that `[1, 1]` represents a tensor product, and that therefore it is not the same as `[1, 0]` and `[0, 1]` taken together. We added this example to show that the algoritmn is not limited to one-at-a-time refinement.\n", "\n", "To conclude, every time a multi index is accepted, new indices become admissible, and the cycle repeats.\n", "\n", "## References\n", "\n", "Our description of the method here was rather limited, so for more information and applications of this (and similar) methods, see the following references:\n", "\n", "* T. Gerstner and M. Griebel. \"Dimension–adaptive tensor–product quadrature.\" Computing 71.1 (2003): 65-87.\n", "* W. Edeling , H. Arabnejad , R. Sinclair, D. Suleimenova, K. Gopalakrishnan, B. Bosak, D. Groen, I. Mahmood, D. Crommelin, and Peter V Coveney, \"The Impact of Uncertainty on Predictions of the CovidSim Epidemiological Code\", Nature Computational Science, 1 (2), 2021.\n", "* D. Loukrezis, U. Römer, and H. De Gersem. \"Assessing the performance of Leja and Clenshaw-Curtis collocation for computational electromagnetics with random input data\". International Journal for Uncertainty Quantification , 9(1), 2019.\n", "* J.D. Jakeman, M.S. Eldred, G. Geraci, and A. Gorodetsky. \"Adaptive multi-index collocation for uncertainty quantification and sensitivity analysis\". Numerical Methods in Engineering , 121(6):1314-1343, 2020." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Example\n", "\n", "Below we give an EasyVVUQ script for a dimension-adaptive campaign on a simple polynomial function with 20 uncertain inputs. The function is given by:\n", "\n", "```python\n", " sol = 1.0\n", " for i in range(d):\n", " sol *= 3 * a[i] * theta[i]**2 + 1.0\n", " return sol/2**d\n", "```\n", "\n", "Thus, it is just a product of quadratic polynomials. The coefficients `a[i]` are given by\n", "\n", "```python\n", "a = [1/(2*(i+1)) for i in range(d)]\n", "```\n", "Such that `a=[0.5, 0.25, 0.125, ..., 1/2**20]`. That is, we have imposed that `x1` is the most important, then `x2` etc. The variables near `x20` virtually do not contribute at all. We would like to pick up on this, and only refine the first couple of inputs." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "ExecuteTime": { "end_time": "2021-06-09T07:35:54.662443Z", "start_time": "2021-06-09T07:35:54.660674Z" } }, "outputs": [], "source": [ "#!pip install EasyVVUQ\n", "#!pip install future\n", "#!pip install fipy" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "ExecuteTime": { "end_time": "2021-06-09T07:35:57.781098Z", "start_time": "2021-06-09T07:35:54.663891Z" } }, "outputs": [], "source": [ "import easyvvuq as uq\n", "import numpy as np\n", "import chaospy as cp\n", "import os\n", "import matplotlib.pyplot as plt\n", "from easyvvuq.actions import CreateRunDirectory, Encode, Decode, CleanUp, ExecuteLocal, Actions" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Running an adaptive campaign starts exactly the same as creating a 'normal' SC campaign, with the exception of a few extra flags that are passed to the SC sampler object. We therefore start as usual with creating a Campaign, encoder and decoder, and setting up the parameters space:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "ExecuteTime": { "end_time": "2021-06-09T07:35:57.809880Z", "start_time": "2021-06-09T07:35:57.782354Z" } }, "outputs": [], "source": [ "# The number of uncertain inputs\n", "d = 20\n", "\n", "#All parameters are between 0 and 1\n", "params = {}\n", "for i in range(d):\n", " params[\"x%d\" % (i + 1)] = {\"type\": \"float\",\n", " \"min\": 0.0,\n", " \"max\": 1.0,\n", " \"default\": 0.5}\n", " \n", "#also store the name of the output file and the stochastic dimension\n", "params[\"out_file\"] = {\"type\": \"string\", \"default\": \"output.csv\"}\n", "params[\"d\"] = {\"type\": \"integer\", \"default\": d}\n", "output_filename = params[\"out_file\"][\"default\"]\n", "output_columns = [\"f\"]\n", "\n", "# Create an encoder, decoder and collation element\n", "encoder = uq.encoders.GenericEncoder(\n", " template_fname='poly_model.template',\n", " delimiter='$',\n", " target_filename='poly_in.json')\n", "\n", "\n", "decoder = uq.decoders.SimpleCSV(target_filename=output_filename,\n", " output_columns=output_columns)\n", "\n", "\n", "execute = ExecuteLocal('{}/poly_model.py poly_in.json'.format(os.getcwd()))\n", "\n", "\n", "actions = Actions(CreateRunDirectory('/tmp'), \n", " Encode(encoder), execute, Decode(decoder))\n", "\n", "\n", "# Create an EasyVVUQ campaign\n", "campaign = uq.Campaign(name='sc_adaptive', work_dir='/tmp', params=params, actions=actions)\n", "\n", "\n", "# All inputs are uniformly distributed\n", "vary = {}\n", "for i in range(d):\n", " vary[\"x%d\" % (i + 1)] = cp.Uniform(0, 1)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "As mentioned, the sampler is a bit different:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "ExecuteTime": { "end_time": "2021-06-09T07:35:57.820269Z", "start_time": "2021-06-09T07:35:57.811263Z" } }, "outputs": [], "source": [ "sampler = uq.sampling.SCSampler(vary=vary, polynomial_order=1,\n", " quadrature_rule=\"C\",\n", " sparse=True, growth=True,\n", " midpoint_level1=True,\n", " dimension_adaptive=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Here:\n", "\n", "* `polynomial_order=1`: do not change, will be adaptively increased for influential parameters. Technically, it'll change the quadrature order for different (combinations of) parameters).\n", "* `quadrature_rule=\"C\":`selects the Clenshaw Curtis quadrature rule. This is a common choice, although others are available.\n", "* `sparse = True`: selects a sparse grid. This is required.\n", "* `growth = True`: selects a nested quadrature rule (a quadrature rule such that a 1D rule of order p contains all points of the same rule of order p-1). Also not required, but is efficient in high dimensions. Note that this can only be selected with a subset of all quadrature rules in Chaospy, including Clenshaw Curtis.\n", "* `midpoint_level1=True`: this means that the first iteration of the dimension-adaptive sampler consists of a single sample. \n", "* `dimension_adaptive=True`: selects the dimension-adaptive sparse grid sampler (opposed to the isotropic sparse grid sampler, which treats each input the same)." ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "ExecuteTime": { "end_time": "2021-06-09T07:35:58.030632Z", "start_time": "2021-06-09T07:35:57.820969Z" } }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "100%|██████████| 1/1 [00:00<00:00, 5.59it/s]\n" ] } ], "source": [ "# set the sampler, and draw the first sample\n", "campaign.set_sampler(sampler)\n", "campaign.execute().collate(progress_bar=True)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "ExecuteTime": { "end_time": "2021-06-09T07:35:58.050314Z", "start_time": "2021-06-09T07:35:58.031567Z" } }, "outputs": [ { "data": { "text/html": [ "
\n", " | run_id | \n", "iteration | \n", "x1 | \n", "x2 | \n", "x3 | \n", "x4 | \n", "x5 | \n", "x6 | \n", "x7 | \n", "x8 | \n", "... | \n", "x14 | \n", "x15 | \n", "x16 | \n", "x17 | \n", "x18 | \n", "x19 | \n", "x20 | \n", "out_file | \n", "d | \n", "f | \n", "
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
\n", " | 0 | \n", "0 | \n", "0 | \n", "0 | \n", "0 | \n", "0 | \n", "0 | \n", "0 | \n", "0 | \n", "0 | \n", "... | \n", "0 | \n", "0 | \n", "0 | \n", "0 | \n", "0 | \n", "0 | \n", "0 | \n", "0 | \n", "0 | \n", "0 | \n", "
0 | \n", "1 | \n", "0 | \n", "0.5 | \n", "0.5 | \n", "0.5 | \n", "0.5 | \n", "0.5 | \n", "0.5 | \n", "0.5 | \n", "0.5 | \n", "... | \n", "0.5 | \n", "0.5 | \n", "0.5 | \n", "0.5 | \n", "0.5 | \n", "0.5 | \n", "0.5 | \n", "output.csv | \n", "20 | \n", "0.000003 | \n", "
1 rows × 25 columns
\n", "