493 lines
17 KiB
MQL5
493 lines
17 KiB
MQL5
//+------------------------------------------------------------------+
|
|
//| 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);
|
|
}
|
|
//+------------------------------------------------------------------+
|