Safety Test

Before we implement the safety test, let's write a shell for our quasi-Seldonian algorithm, which we will call QSA. This shell will show how the safety test will be called. At a high level, we are simply partitioning the data, getting a candidate solution, and running the safet test. If you are relatively new to C++, the third argument may appear to be confusing: this argument is an std::vector of pointers to functions, each of which has inputs and outputs matching the functions hatG1 and hatG2 that we wrote earlier. Also, we are using the more descriptive names candData (candidate data) for \(D_1\) and safetyData for \(D_2\). Lastly, notice that we are placing 40% of the data in candData and 60% in safetyData—this is an arbitrary choice and it remains an open question how best to optimize this partitioning of the data.

// Our quasi-Seldonian linear regression algorithm. The result is a pair of items, the second
// is a Boolean denoting whether a solution is being returned. If it is false, it indicates
// No Solution Found (NSF), and the first element is irrelevant. If the second element is
// true, then the first element is the solution that was found.
pair<VectorXd,bool> QSA(
  const vector<Point>& Data,              // The training data to use
  const vector<VectorXd(*)(const VectorXd&, const vector<Point>&)>& gHats,       // Unbiased estimators of g(theta) for each of the behavioral constraints
  const vector<double>& deltas,           // Confidence levels for the behavioral constraints
  mt19937_64& generator)                  // The random number generator to use
{
  vector<Point> candData(Data.begin(), Data.begin() + (int)(Data.size() * 0.4)); // Put 40% of the data in candidateData
  vector<Point> safetyData(Data.begin() + candData.size(), Data.end());          // Put the rest of the data in safetyData
  pair<VectorXd, bool> result;            // Create the object that we will return
  result.first = getCandidateSolution(candData, gHats, deltas, (unsigned int)safetyData.size(), generator); // Get the candidate solution
  result.second = safetyTest(result.first, safetyData, gHats, deltas);           // Run the safety test
  return result;                          // Return the result object
}

Recall the pseudocode for the safety test:

3. Safety Test: Return \(\theta_c\) if $$ \forall i \in \{1,2,\dotsc,n\}, \quad \hat \mu(\hat g_i(\theta_c,D_2)) + \frac{\hat \sigma(\hat g(\theta_c,D_2))}{\sqrt{|D_2|}}t_{1-\delta_i,|D_2|-1} \leq 0, $$ and No Solution Found (NSF) otherwise.

Given the helper functions we already have, this function is straightforward to write:

// Run the safety test on the solution theta. Returns true if the test is passed
bool safetyTest(
  const VectorXd& theta,                              // The solution to test
  const vector<Point>& Data,                          // The data to use in the safety test
  const vector<VectorXd(*)(const VectorXd&, const vector<Point>&)>& gHats,  // Unbiased estimators of g(theta) for each of the behavioral constraints
  const vector<double>& deltas)                       // Confidence levels for the behavioral constraints 
{
  for (unsigned int i = 0; i < gHats.size(); i++) {   // Loop over behavioral constraints, checking each
    if (ttestUpperBound(gHats[i](theta, Data), deltas[i]) > 0)              // Check if the i'th behavioral constraint is satisfied
      return false;                                   // It wasn't - the safety test failed.
  }
  return true;                                        // If we get here, all of the behavioral constraints were satisfied
}

We're almost there. All that's left is the the function getCandidateSolution!

Previous: Coding environment setup Next: Candidate selection