//+------------------------------------------------------------------+ //| 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); } //+------------------------------------------------------------------+