LennyEugene/pbo-cscv-engine
Watch
1
0
Fork
You've already forked pbo-cscv-engine
 0
forked from Lerooy/pbo-cscv-engine
Code Pull requests Activity
pbo-cscv-engine/Include/PBO/CSCVEngine.mqh
John Bergerat 389634fb38 Add Include/PBO/CSCVEngine.mqh 
Add CSCV engine
2026-08-17 18:38:04 +00:00

493 lines
17 KiB
MQL5
Raw Permalink Blame History

//+------------------------------------------------------------------+
//| CSCVEngine.mqh |
//| Probability of Backtest Overfitting - Astralys LLC |
//| |
//| Combinatorially Symmetric Cross-Validation, after |
//| Bailey, Borwein, Lopez de Prado & Zhu (2015), "The Probability of |
//| Backtest Overfitting", Journal of Computational Finance. |
//| |
//| ---------------------------------------------------------------- |
//| WHY THIS IS FAST |
//| |
//| The naive procedure re-computes the performance of all N trials |
//| over T/2 rows, for each of the C(S, S/2) combinations. With |
//| S = 16, N = 1300 and T = 8000 that is 12,870 * 1300 * 4000 |
//| operations. Not viable. |
//| |
//| Two observations collapse it: |
//| |
//| 1. The metric is a cumulative LOG return, so it is additive over |
//| rows. Pre-aggregate once into an S x N matrix of per-partition|
//| sums. A combination's in-sample value is then a sum of S/2 |
//| terms instead of T/2. |
//| |
//| 2. The test set is the exact complement of the training set, so |
//| OOS = Total - IS |
//| and only the in-sample side is ever computed. |
//| |
//| Cost drops to C * N * S/2 additions, ~134M for the numbers above. |
//| |
//| The same trick extends to the Sharpe ratio: store sum, sum of |
//| squares and count per partition. All three are additive. |
//| ---------------------------------------------------------------- |
//| |
//| NOTE ON CORRECT USE. Bailey et al. warn that using the PBO as a |
//| criterion to select a strategy is "a gross misuse of our method": |
//| any counter-overfitting technique used to select an optimal |
//| strategy will itself overfit. Measure, then accept or reject. |
//| Never optimise against this number. |
//+------------------------------------------------------------------+
#property copyright "Astralys LLC"
#property link "https://pulsar-terminal.com"
#property version "1.00"
//+------------------------------------------------------------------+
//| Number of set bits in a 32-bit mask. |
//+------------------------------------------------------------------+
int PopCount(uint v)
{
int c = 0;
while(v)
{
v &= (v - 1); // clears the lowest set bit
c++;
}
return(c);
}
//+------------------------------------------------------------------+
//| CCSCVEngine |
//+------------------------------------------------------------------+
class CCSCVEngine
{
private:
//--- input
int m_rows; // T, number of bars
int m_cols; // N, number of parameter combinations
int m_partitions; // S, must be even
double m_returns[]; // T x N log returns, row-major: [t * N + n]
//--- pre-aggregation
double m_part[]; // S x N partition sums, row-major: [s * N + n]
double m_total[]; // N total sums
//--- results, one entry per combination
double m_logits[];
double m_selIS[]; // IS cumulative log return of the selected trial
double m_selOOS[]; // OOS cumulative log return of the selected trial
int m_selIndex[]; // which trial was selected
int m_combinations;
double m_pbo;
double m_probLoss;
bool m_ready;
bool Aggregate(void);
bool Enumerate(void);
public:
CCSCVEngine(void);
//--- setup
bool SetReturns(const double &data[], const int rows, const int cols);
bool SetPartitions(const int s);
//--- run
bool Run(void);
//--- results
bool IsReady(void) const { return(m_ready); }
double PBO(void) const { return(m_pbo); }
double ProbabilityOfLoss(void) const { return(m_probLoss); }
int CombinationCount(void) const { return(m_combinations); }
int Rows(void) const { return(m_rows); }
int Cols(void) const { return(m_cols); }
bool GetLogits(double &out[]) const;
bool GetDegradation(double &is[], double &oos[]) const;
bool GetSelected(int &out[]) const;
//--- control experiment
bool RunControl(const int &pool[], const int seed,
double &outIS[], double &outOOS[]);
};
//+------------------------------------------------------------------+
//| Constructor |
//+------------------------------------------------------------------+
CCSCVEngine::CCSCVEngine(void) : m_rows(0),
m_cols(0),
m_partitions(16),
m_combinations(0),
m_pbo(0.0),
m_probLoss(0.0),
m_ready(false)
{
}
//+------------------------------------------------------------------+
//| Load the returns matrix. |
//| |
//| data must be row-major, T x N, holding LOG returns. Row t is the |
//| bar, column n is the parameter combination. Additivity of the |
//| metric is what the whole engine rests on, so simple returns will |
//| silently give wrong answers here. |
//+------------------------------------------------------------------+
bool CCSCVEngine::SetReturns(const double &data[], const int rows, const int cols)
{
if(rows <= 0 || cols <= 0)
{
Print("CSCV: invalid dimensions ", rows, " x ", cols);
return(false);
}
if(ArraySize(data) != rows * cols)
{
Print("CSCV: array size ", ArraySize(data),
" does not match ", rows, " x ", cols);
return(false);
}
if(ArrayResize(m_returns, rows * cols) != rows * cols)
{
Print("CSCV: cannot allocate ", rows * cols, " doubles");
return(false);
}
ArrayCopy(m_returns, data);
m_rows = rows;
m_cols = cols;
m_ready = false;
return(true);
}
//+------------------------------------------------------------------+
//| Number of partitions. Must be even; Bailey et al. recommend 16 |
//| as a reasonable default, which preserves daily, weekly, monthly |
//| and quarterly effects while yielding C(16,8) = 12,870 splits. |
//+------------------------------------------------------------------+
bool CCSCVEngine::SetPartitions(const int s)
{
if(s < 4 || s > 30 || (s % 2) != 0)
{
Print("CSCV: partitions must be even and within [4, 30], got ", s);
return(false);
}
m_partitions = s;
m_ready = false;
return(true);
}
//+------------------------------------------------------------------+
//| Pre-aggregation: S x N partition sums, plus the column totals. |
//| |
//| Rows are NOT shuffled. CSCV is a time-series cross-validation: |
//| partitions keep their original order so that serial dependence |
//| and seasonal effects survive the procedure. |
//| |
//| If T is not divisible by S the remainder is dropped from the |
//| OLDEST end, keeping the most recent history intact. |
//+------------------------------------------------------------------+
bool CCSCVEngine::Aggregate(void)
{
const int S = m_partitions;
const int N = m_cols;
const int perPart = m_rows / S;
if(perPart < 1)
{
Print("CSCV: ", m_rows, " rows cannot be split into ", S, " partitions");
return(false);
}
const int offset = m_rows - perPart * S; // dropped oldest rows
if(offset > 0)
PrintFormat("CSCV: dropping %d oldest row(s) so %d rows split evenly into %d partitions",
offset, perPart * S, S);
if(ArrayResize(m_part, S * N) != S * N)
return(false);
if(ArrayResize(m_total, N) != N)
return(false);
ArrayInitialize(m_part, 0.0);
ArrayInitialize(m_total, 0.0);
for(int s = 0; s < S; s++)
{
const int base = s * N;
const int rowFrom = offset + s * perPart;
const int rowTo = rowFrom + perPart;
for(int t = rowFrom; t < rowTo; t++)
{
const int rBase = t * N;
for(int n = 0; n < N; n++)
m_part[base + n] += m_returns[rBase + n];
}
}
for(int s = 0; s < S; s++)
{
const int base = s * N;
for(int n = 0; n < N; n++)
m_total[n] += m_part[base + n];
}
return(true);
}
//+------------------------------------------------------------------+
//| Walk every combination of S/2 partitions out of S. |
//| |
//| For each: build the training set, take the best trial in sample, |
//| find where that same trial ranks out of sample, and turn the |
//| relative rank into a logit. Logits at or below zero are the |
//| failures the PBO counts. |
//+------------------------------------------------------------------+
bool CCSCVEngine::Enumerate(void)
{
const int S = m_partitions;
const int N = m_cols;
const int half = S / 2;
const uint end = (uint)1 << S;
double is[];
if(ArrayResize(is, N) != N)
return(false);
//--- C(S, S/2); allocate generously, we trim at the end
int cap = 1;
for(int i = 0; i < half; i++)
cap = (int)((double)cap * (S - i) / (i + 1));
if(ArrayResize(m_logits, cap) != cap) return(false);
if(ArrayResize(m_selIS, cap) != cap) return(false);
if(ArrayResize(m_selOOS, cap) != cap) return(false);
if(ArrayResize(m_selIndex, cap) != cap) return(false);
int c = 0;
int failures = 0;
int losses = 0;
const double denom = (double)(N + 1);
for(uint mask = 0; mask < end; mask++)
{
if(PopCount(mask) != half)
continue;
//--- training set: sum the chosen partitions
ArrayInitialize(is, 0.0);
for(int s = 0; s < S; s++)
{
if((mask & ((uint)1 << s)) == 0)
continue;
const int base = s * N;
for(int n = 0; n < N; n++)
is[n] += m_part[base + n];
}
//--- best trial in sample
int bestN = 0;
double bestIS = is[0];
for(int n = 1; n < N; n++)
{
if(is[n] > bestIS)
{
bestIS = is[n];
bestN = n;
}
}
//--- its out-of-sample value, by complement
const double bestOOS = m_total[bestN] - bestIS;
//--- rank of that value among all trials out of sample
int below = 0;
for(int n = 0; n < N; n++)
{
if((m_total[n] - is[n]) < bestOOS)
below++;
}
const double rank = (double)(below + 1);
const double omega = rank / denom; // strictly inside (0,1)
const double logit = MathLog(omega / (1.0 - omega));
m_logits[c] = logit;
m_selIS[c] = bestIS;
m_selOOS[c] = bestOOS;
m_selIndex[c] = bestN;
if(logit <= 0.0)
failures++;
if(bestOOS < 0.0)
losses++;
c++;
}
m_combinations = c;
ArrayResize(m_logits, c);
ArrayResize(m_selIS, c);
ArrayResize(m_selOOS, c);
ArrayResize(m_selIndex, c);
if(c == 0)
return(false);
m_pbo = 100.0 * (double)failures / (double)c;
m_probLoss = 100.0 * (double)losses / (double)c;
return(true);
}
//+------------------------------------------------------------------+
//| Run the full procedure. |
//+------------------------------------------------------------------+
bool CCSCVEngine::Run(void)
{
m_ready = false;
if(m_rows == 0 || m_cols == 0)
{
Print("CSCV: no returns matrix loaded");
return(false);
}
const uint t0 = GetTickCount();
if(!Aggregate())
return(false);
if(!Enumerate())
return(false);
m_ready = true;
PrintFormat("CSCV: %d combinations over %d trials, %d bars, %d partitions in %.1f s",
m_combinations, m_cols, m_rows, m_partitions,
(GetTickCount() - t0) / 1000.0);
PrintFormat("CSCV: PBO = %.2f%% Probability of loss = %.2f%%",
m_pbo, m_probLoss);
return(true);
}
//+------------------------------------------------------------------+
//| Control experiment: walk exactly the same splits, but instead of |
//| taking the best trial in sample, take one at random from a pool. |
//| |
//| This exists because of an identity that is easy to miss. The two |
//| halves partition the same period, and a cumulative log return is |
//| additive, so for any given trial |
//| |
//| IS + OOS = total over the whole sample, a constant |
//| |
//| Within one trial the correlation between the two halves is |
//| therefore exactly -1, by arithmetic and not by degradation. Any |
//| scatter of OOS against IS inherits that, whatever the selection |
//| rule. Comparing the real selection against a random one on the |
//| same splits is what separates the arithmetic from the effect. |
//| |
//| pool[] column indices the control is allowed to draw from |
//| seed fixed so the control is reproducible |
//+------------------------------------------------------------------+
bool CCSCVEngine::RunControl(const int &pool[], const int seed,
double &outIS[], double &outOOS[])
{
if(!m_ready)
return(false);
const int poolSize = ArraySize(pool);
if(poolSize < 1)
return(false);
const int S = m_partitions;
const int N = m_cols;
const int half = S / 2;
const uint end = (uint)1 << S;
double is[];
if(ArrayResize(is, N) != N)
return(false);
if(ArrayResize(outIS, m_combinations) != m_combinations) return(false);
if(ArrayResize(outOOS, m_combinations) != m_combinations) return(false);
MathSrand(seed);
int c = 0;
for(uint mask = 0; mask < end && c < m_combinations; mask++)
{
if(PopCount(mask) != half)
continue;
ArrayInitialize(is, 0.0);
for(int s = 0; s < S; s++)
{
if((mask & ((uint)1 << s)) == 0)
continue;
const int base = s * N;
for(int n = 0; n < N; n++)
is[n] += m_part[base + n];
}
const int pick = pool[MathRand() % poolSize];
outIS[c] = is[pick];
outOOS[c] = m_total[pick] - is[pick];
c++;
}
return(c == m_combinations);
}
//+------------------------------------------------------------------+
//| Logit distribution, one value per combination. |
//+------------------------------------------------------------------+
bool CCSCVEngine::GetLogits(double &out[]) const
{
if(!m_ready)
return(false);
if(ArrayResize(out, m_combinations) != m_combinations)
return(false);
ArrayCopy(out, m_logits);
return(true);
}
//+------------------------------------------------------------------+
//| Performance degradation: paired IS and OOS cumulative log returns |
//| of the selected trial, one point per combination. |
//+------------------------------------------------------------------+
bool CCSCVEngine::GetDegradation(double &is[], double &oos[]) const
{
if(!m_ready)
return(false);
if(ArrayResize(is, m_combinations) != m_combinations)
return(false);
if(ArrayResize(oos, m_combinations) != m_combinations)
return(false);
ArrayCopy(is, m_selIS);
ArrayCopy(oos, m_selOOS);
return(true);
}
//+------------------------------------------------------------------+
//| Which trial was picked in each combination. Useful to see whether |
//| the procedure keeps landing on the same corner of the grid. |
//+------------------------------------------------------------------+
bool CCSCVEngine::GetSelected(int &out[]) const
{
if(!m_ready)
return(false);
if(ArrayResize(out, m_combinations) != m_combinations)
return(false);
ArrayCopy(out, m_selIndex);
return(true);
}
//+------------------------------------------------------------------+
View git blame Copy permalink