CrossValidation.h

Go to the documentation of this file.

// Copyright (c) 2002-present, OpenMS Inc. -- EKU Tuebingen, ETH Zurich, and FU Berlin
// SPDX-License-Identifier: BSD-3-Clause
//
// --------------------------------------------------------------------------
// $Maintainer: Justin Sing $
// $Authors: Justin Sing $
// --------------------------------------------------------------------------
//
 
#pragma once
 
#include <OpenMS/config.h>
#include <OpenMS/CONCEPT/Types.h>
#include <OpenMS/CONCEPT/Exception.h>
#include <OpenMS/DATASTRUCTURES/String.h>
 
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <utility>
#include <vector>
 
namespace OpenMS
{
 
class CrossValidation
{
public:
  enum class CandidateTieBreak
  {
    PreferLarger,
    PreferSmaller,
    PreferAny
  };
 
  static std::vector<std::vector<Size>> makeKFolds(Size n, Size K)
  {
    if (n == 0)
    {
      throw Exception::InvalidValue(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION,
                                    "n", String(n));
    }
    if (K == 0)
    {
      throw Exception::InvalidValue(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION,
                                    "K", String(K));
    }
    if (K > n) K = n;
 
    std::vector<std::vector<Size>> folds(K);
    for (Size i = 0; i < n; ++i) folds[i % K].push_back(i);
    return folds;
  }
 
  template <typename CandIter, typename TrainEval, typename ScoreFn>
  static std::pair<typename std::iterator_traits<CandIter>::value_type, double>
  gridSearch1D(CandIter cbegin, CandIter cend,
               const std::vector<std::vector<Size>>& folds,
               TrainEval train_eval,
               ScoreFn score,
               double tie_tol = 1e-12,
               CandidateTieBreak tie_break = CandidateTieBreak::PreferLarger)
  {
    using CandT = typename std::iterator_traits<CandIter>::value_type;
 
    if (cbegin == cend)
    {
      throw Exception::InvalidRange(__FILE__, __LINE__, OPENMS_PRETTY_FUNCTION);
    }
 
    CandT best_cand = *cbegin;
    double best_score = std::numeric_limits<double>::infinity();
    bool first = true;
 
    for (auto it = cbegin; it != cend; ++it)
    {
      const CandT cand = *it;
 
      std::vector<double> abs_errs;
      abs_errs.reserve(256); // grows as needed
      train_eval(cand, folds, abs_errs);
 
      const double s = score(abs_errs);
 
      // Prefer larger candidate on numerical ties (more stable smoothing, etc.)
      const bool better = (s < best_score - tie_tol);
      const bool tie    = (std::fabs(s - best_score) <= tie_tol);
 
      bool wins_on_tie = false;
      if (tie)
      {
        switch (tie_break)
        {
          case CandidateTieBreak::PreferLarger:  wins_on_tie = cand > best_cand; break;
          case CandidateTieBreak::PreferSmaller: wins_on_tie = cand < best_cand; break;
          case CandidateTieBreak::PreferAny:     wins_on_tie = false;            break;
        }
      }
 
      if (first || better || wins_on_tie)
      {
        best_cand  = cand;
        best_score = s;
        first = false;
      }
    }
 
    return {best_cand, best_score};
  }
};
 
} // namespace OpenMS