Label uniqueness, overlap weights and the sequential bootstrap.

Many rows, fewer observations

Classical statistics assumes independent observations: a thousand rows are a thousand data points. With triple-barrier labels that does not hold. A label that starts at 11:52 and ends at 12:16 uses the prices of those 24 minutes; if another starts at 12:02 and ends at 12:10, the two share 8 minutes of price and their outcomes are correlated. A model that trains on both has not seen two examples: it has seen one and a half.

The figure in the header shows the problem in one FNX session (level 5 synthetic data). Each bar is a label, from the event to the touch of its first barrier; below, how many are alive each minute. Chapter 4 of López de Prado (2018) proposes three answers, which this lesson applies one by one:

• Measure the overlap: the concurrency of each minute and the average uniqueness of each label.
• Weight each label by its own information: by uniqueness, by the return that corresponds to it and by its age.
• Sample taking it into account: the sequential bootstrap for bagging methods.

Concurrency and uniqueness

The events are those of the level's CUSUM filter (lesson 5.3.5) and the labels, those of the triple barrier with $\pm\sigma\sqrt{30}$ and a vertical at 30 minutes (5.3.2). The only new thing is that the start and end of each one now matter. The 17 labels of events in the last minute of the session have no life (their vertical is their own entry) and are left out.

import numpy as np
import pandas as pd

barras = pd.read_parquet("hf5_barras_1min.parquet")
n_ses = len(barras) // 390
C = barras["cierre"].to_numpy().reshape(n_ses, 390)
V = barras["volumen"].to_numpy().reshape(n_ses, 390)
VC = barras["volumen_comprador"].to_numpy().reshape(n_ses, 390)
lr = np.diff(np.log(C), axis=1)
sig = (pd.Series(lr.ravel()).ewm(span=100).std()
       .to_numpy().reshape(n_ses, 389))


def eventos_cusum(lr, sig, k=4.0):
    """Symmetric CUSUM filter per session (lesson 5.3.5)."""
    filas = []
    for d in range(lr.shape[0]):
        s_pos = s_neg = 0.0
        for m in range(lr.shape[1]):
            h = k * sig[d, m]
            if not np.isfinite(h):
                continue
            s_pos = max(0.0, s_pos + lr[d, m])
            s_neg = min(0.0, s_neg + lr[d, m])
            if s_pos > h or s_neg < -h:
                filas.append((d, m + 1, 1 if s_pos > h else -1,
                              sig[d, m]))
                s_pos = s_neg = 0.0
    return pd.DataFrame(
        filas, columns=["sesion", "minuto", "lado", "sigma"])


def triple_barrera(C, ev, k=1.0, h=30):
    """Barriers ±k·σ·√h and vertical at h minutes (lesson 5.3.2)."""
    fin, ret, toque = [], [], []
    for d, m, s in ev[["sesion", "minuto", "sigma"]].itertuples(
            index=False):
        ult = min(m + h, C.shape[1] - 1)
        tramo = np.log(C[d, m + 1:ult + 1] / C[d, m])
        b = k * s * np.sqrt(h)
        golpes = np.flatnonzero(np.abs(tramo) >= b)
        j = golpes[0] if len(golpes) else len(tramo) - 1
        fin.append(m + 1 + j)
        ret.append(float(tramo[j]) if len(tramo) else 0.0)
        toque.append(int(np.sign(tramo[j])) if len(golpes) else 0)
    return ev.assign(fin=fin, ret=ret, toque=toque)


ev = triple_barrera(C, eventos_cusum(lr, sig))
ev = ev[ev.fin > ev.minuto].reset_index(drop=True)  # 17 with no life
ev["y"] = (ev.lado * ev.ret > 0).astype(int)
print(len(ev), "labels; mean life:",
      round((ev.fin - ev.minuto).mean(), 1), "minutes")

6533 labels; mean life: 22.6 minutes

The life of label $i$ is the minutes $(t_{i,0}, t_{i,1}]$: from the one after the event to the one of the touch. With $1_{t,i} = 1$ if label $i$ is alive at minute $t$, the concurrency of the minute is $c_t = \sum_i 1_{t,i}$. Computing it does not require building the matrix $1_{t,i}$ (96,330 minutes by 6,533 labels): it is enough to add $+1$ at the minute each label is born and $-1$ at the one after it dies, and accumulate.

G = n_ses * 390                          # minutes of the whole year
ini = ev.sesion.to_numpy() * 390 + ev.minuto.to_numpy() + 1
fin = ev.sesion.to_numpy() * 390 + ev.fin.to_numpy() + 1  # exclusive
dif = np.zeros(G + 1)
np.add.at(dif, ini, 1)
np.add.at(dif, fin, -1)
conc = np.cumsum(dif)[:G]                # labels alive per minute
print(f"minutes with some label alive: {(conc > 0).mean():.1%}")
print(f"mean concurrency in them: {conc[conc > 0].mean():.2f}")
pd.Series(conc).value_counts(normalize=True).sort_index().round(3)

minutes with some label alive: 94.9%
mean concurrency in them: 1.61
0.0    0.051
1.0    0.443
2.0    0.436
3.0    0.067
4.0    0.003
5.0    0.000
Name: proportion, dtype: float64

np.add.at also adds when an index is repeated (two labels born in the same minute), which dif[ini] += 1 does not do. 94.9% of the minutes of the year have at least one label alive, and in them there are 1.61 on average: 43.6% of the minutes have two and 6.7%, three.

The uniqueness of label $i$ at minute $t$ is $1_{t,i}/c_t$: the fraction of the minute that corresponds to it. Its average uniqueness is the mean over its life:

Again, with a cumulative sum of $1/c_t$ you get that of all labels with two subtractions:

inv = np.where(conc > 0, 1 / np.maximum(conc, 1), 0.0)
acum = np.r_[0.0, np.cumsum(inv)]
ev["unicidad"] = (acum[fin] - acum[ini]) / (fin - ini)
u = ev["unicidad"].to_numpy()
print(f"average uniqueness {u.mean():.3f}, median {np.median(u):.3f}")
print(f"“effective” labels: {u.sum():.0f} of {len(u)}")
tramos = pd.cut(ev.unicidad, [0, 0.25, 0.5, 0.75, 0.999, 1.0])
ev.groupby(tramos, observed=True).size().rename("etiquetas")

average uniqueness 0.617, median 0.583
“effective” labels: 4029 of 6533
unicidad
(0.0, 0.25]         6
(0.25, 0.5]      2288
(0.5, 0.75]      2767
(0.75, 0.999]    1314
(0.999, 1.0]      158
Name: etiquetas, dtype: int64

The average uniqueness is 0.617 and the median 0.583, the README figures. Added up, the 6,533 labels provide the information of about 4,029 independent ones. Only 158 are alone their whole life; most (5,055) have a uniqueness between 0.25 and 0.75.

The session in the header figure, as a table:

s133 = ev[(ev.sesion == 133) & (ev.minuto.between(130, 200))]
s133[["minuto", "fin", "lado", "toque", "unicidad"]].round(2)

      minuto  fin  lado  toque  unicidad
3524     130  142     1      1      0.75
3525     142  166     1      1      0.69
3526     152  160    -1      1      0.46
3527     158  168     1      1      0.47
3528     166  196     1      0      0.92
3529     193  223     1      0      0.65

The label of the 11:52 event (minute 142 of the session, the one in the figure of lesson 5.3.2) has a uniqueness of 0.69: it shares part of its life with those of minutes 152 and 158. The one at minute 166 lives 30 minutes almost alone (0.92). The figure highlights the least unique one in the window, the one at minute 223 (0.42), which is never alone: half of its life it shares with one label and the other half with two.

Weights by return attribution

Uniqueness says how much information of its own a label has, but not how informative that information is. A vertical label that ends at +0.2 bp has an almost random sign; one that touches the barrier with +25 bp describes a clear move. Return-attribution weights share each minute's return among the labels alive and weight each one by the absolute value of its share:

with $r_t$ the log return of the minute. The normalization makes the weights add up to $N$, as if there were no weights.

r = np.c_[np.zeros(n_ses), lr].ravel()   # r of the minute, 0 at the open
ra = np.r_[0.0, np.cumsum(r * inv)]
w_ret = np.abs(ra[fin] - ra[ini])
w_ret = w_ret * len(w_ret) / w_ret.sum()   # they add up to N
ev["w_ret"] = w_ret
print("correlation with uniqueness:",
      round(np.corrcoef(w_ret, u)[0, 1], 3))
ev.groupby("toque")[["unicidad", "w_ret"]].mean().round(3)

correlation with uniqueness: 0.336
       unicidad  w_ret
toque
-1        0.607  1.406
 0        0.623  0.648
 1        0.611  1.403

The labels that touch a horizontal barrier weigh 1.40 on average and the verticals 0.65: the return of the former is, by construction, at least $\sigma\sqrt{30}$. The average uniqueness of the two groups is almost the same. The 0.336 correlation between weight and uniqueness comes from the division by $c_t$: for the same move, the overlapping label gets a smaller fraction.

These weights are passed to the model as sample_weight (almost all scikit-learn, LightGBM and XGBoost estimators accept it). They are a correction of what is learned, not of the validation.

Time decay

Markets change (lesson 5.10.2) and an observation from a year ago may teach a relationship that no longer exists. López de Prado's time decay lowers the weight of the old linearly, but over cumulative uniqueness and not over the number of rows, so that a period with many overlapping labels does not count as a lot of time:

One parameter $c$ decides the shape: with $c = 1$ there is no decay; with $c \in [0, 1)$ the oldest label weighs $c$; with $c < 0$ the oldest fraction $|c|$ weighs zero.

def decaimiento(u, c=1.0):
    """Weight by age, linear in cumulative uniqueness; the most
    recent label weighs 1. c = 1: no decay; c in [0, 1): the
    oldest weighs c; c < 0: the oldest fraction |c| weighs 0."""
    x = np.cumsum(u)
    b = (1 - c) / x[-1] if c >= 0 else 1 / ((c + 1) * x[-1])
    return np.clip(1 - b * (x[-1] - x), 0, None)


filas = {}
for c in (1.0, 0.5, 0.0, -0.5):
    dk = decaimiento(u, c)
    filas[c] = {"primera": dk[0], "cuartil_1": dk[len(dk) // 4],
                "mitad": dk[len(dk) // 2], "ultima": dk[-1],
                "a_cero": (dk == 0).mean()}
pd.DataFrame(filas).T.rename_axis("c").round(3)

      primera  cuartil_1  mitad  ultima  a_cero
c
 1.0      1.0      1.000  1.000     1.0   0.000
 0.5      0.5      0.626  0.750     1.0   0.000
 0.0      0.0      0.252  0.501     1.0   0.000
-0.5      0.0      0.000  0.001     1.0   0.499

With $c = 0$, the label at the first quartile weighs 0.25 and the one at the middle, 0.50. With $c = -0.5$, the oldest half of the sample does not count. In one year of FNX the decay does not make much sense, because the data model does not change; in a ten-year sample or in data with drift (5.10.2) it is one more parameter that is validated, never one chosen by looking at the test result.

The sequential bootstrap

Bagging (lesson 5.5.2) trains many models on samples drawn with replacement and averages them. It works because the models are different from one another. With overlapping labels, a standard bootstrap sample is full of almost repeated labels: two that share 20 minutes of price are almost the same row for a tree. The sequential bootstrap draws the labels one by one and, at each step, gives each candidate a probability proportional to the average uniqueness it would have together with those already drawn:

with $c^{(k)}_t$ the previous draws alive at minute $t$.

flowchart TB
  I[Empty sample] --> P[Weight by uniqueness]
  P --> E[Draw at random]
  E --> A[Add its life to c]
  A --> Q{N drawn?}
  Q -- no --> P
  Q -- yes --> F[Sample]

The literal implementation, with the full indicator matrix, is slow: at each step it recomputes the uniqueness of all candidates. Since FNX labels do not cross the session close, the matrix is split into one block per session, and a draw only changes the uniqueness of the labels in its block. The draw is done in two steps: first the session, with probability proportional to the sum of the uniqueness of its labels, and then the label within it. It is exactly the same distribution.

def bloques_por_sesion(ses, a, b):
    """For each session, its labels and its indicator matrix
    (labels x minutes of the session) with life (a, b]."""
    out = []
    for s in np.unique(ses):
        idx = np.flatnonzero(ses == s)
        ind = np.zeros((len(idx), 390))
        for k, i in enumerate(idx):
            ind[k, a[i] + 1:b[i] + 1] = 1.0
        out.append((idx, ind))
    return out


def bootstrap_secuencial(bloques, n, rng):
    """Draws n labels; each with probability proportional to the
    average uniqueness it would have together with those drawn."""
    L = [ind.sum(axis=1) for _, ind in bloques]
    S = [x.copy() for x in L]          # sum of 1/(c+1) over its life
    c = [np.zeros(390) for _ in bloques]
    u = [np.ones(len(i)) for i, _ in bloques]
    tot = np.array([x.sum() for x in u])
    out = np.empty(n, dtype=int)
    for k in range(n):
        acu = np.cumsum(tot)
        s = int(np.searchsorted(acu, rng.random() * acu[-1], "right"))
        acu = np.cumsum(u[s])
        j = int(np.searchsorted(acu, rng.random() * acu[-1], "right"))
        idx, ind = bloques[s]
        out[k] = idx[j]
        vida = np.flatnonzero(ind[j])
        antes = 1 / (c[s][vida] + 1)
        c[s][vida] += 1
        S[s] += ind[:, vida] @ (1 / (c[s][vida] + 1) - antes)
        u[s] = S[s] / L[s]
        tot[s] = u[s].sum()
    return out


def unicidad_muestra(bloques, muestra):
    """Average uniqueness of the labels of a sample (with
    repetitions), measured only among them."""
    filas = np.zeros(sum(len(i) for i, _ in bloques), dtype=int)
    for s, (idx, _) in enumerate(bloques):
        filas[idx] = s
    total = []
    for s, (idx, ind) in enumerate(bloques):
        sel = np.searchsorted(idx, muestra[filas[muestra] == s])
        if len(sel) == 0:
            continue
        m = ind[sel]
        cc = m.sum(axis=0)
        total.append((m / np.where(cc > 0, cc, 1)).sum(axis=1)
                     / m.sum(axis=1))
    return np.concatenate(total).mean()


bl = bloques_por_sesion(ev.sesion.to_numpy(), ev.minuto.to_numpy(),
                        ev.fin.to_numpy())
rng = np.random.default_rng(0)
n = len(ev)
res = {"standard": [], "sequential": []}
for _ in range(5):
    est = rng.integers(0, n, n)
    sec = bootstrap_secuencial(bl, n, rng)
    for nombre, mu in (("standard", est), ("sequential", sec)):
        res[nombre].append((unicidad_muestra(bl, mu),
                            len(np.unique(mu)) / n))
pd.DataFrame({k: np.mean(v, axis=0) for k, v in res.items()},
             index=["average uniqueness", "distinct labels"]).round(3)

                    standard  sequential
average uniqueness     0.472       0.528
distinct labels        0.631       0.708

A standard bootstrap sample of 6,533 draws has 63.1% distinct labels (the usual $1 - 1/e$) and an average uniqueness, measured among the labels of the sample itself, of 0.472: repetitions and overlaps add up. The sequential one raises the uniqueness to 0.528 and the distinct labels to 70.8%. That is the improvement the method promises; the question is whether it shows up in a model.

When the overlap is large: a bagging

With 1.6 labels alive per minute the effect is small. To see it clearly you need more overlap, the kind someone who labeled at fixed intervals instead of by events would have: one label every 3 minutes, with the side of the return of the previous 30 minutes (a continuous momentum) and the same triple barrier. The meta-label is whether that side is right; the features, those of the imbalance (5.3.3) and two standardized recent returns.

PASO = 3
lc = np.log(C)
filas = [(d, m, 1 if lc[d, m] > lc[d, m - 30] else -1, sig[d, m - 1])
         for d in range(n_ses) for m in range(30, 360, PASO)]
dn = triple_barrera(C, pd.DataFrame(
    filas, columns=["sesion", "minuto", "lado", "sigma"]))
dn["y"] = (dn.lado * dn.ret > 0).astype(int)
ds, dm = dn.sesion.to_numpy(), dn.minuto.to_numpy()
cv = np.cumsum(V, axis=1)
ci = np.cumsum(2 * VC - V, axis=1)
imb = (ci[ds, dm] - ci[ds, dm - 30]) / (cv[ds, dm] - cv[ds, dm - 30])
Xd = np.column_stack([
    dn.lado * imb, np.abs(imb),
    dn.lado * (lc[ds, dm] - lc[ds, dm - 30]) / dn.sigma,
    dn.lado * (lc[ds, dm] - lc[ds, dm - 10]) / dn.sigma, dm])
yd = dn.y.to_numpy()
a_n, b_n = ds * 390 + dm + 1, ds * 390 + dn.fin.to_numpy() + 1
dif = np.zeros(G + 1)
np.add.at(dif, a_n, 1)
np.add.at(dif, b_n, -1)
conc_n = np.cumsum(dif)[:G]
acu_n = np.r_[0.0, np.cumsum(1 / np.maximum(conc_n, 1))]
u_n = (acu_n[b_n] - acu_n[a_n]) / (b_n - a_n)
print(len(dn), "labels; mean concurrency:",
      round(conc_n[conc_n > 0].mean(), 1), "; average uniqueness:",
      round(u_n.mean(), 3))

27170 labels; mean concurrency: 7.6 ; average uniqueness: 0.136

With 27,170 labels the concurrency rises to 7.6 and the average uniqueness falls to 0.136: each label shares almost all its minutes with six or seven others.

The experiment trains 40 decision trees on the first half of the sessions with three ways of sampling and measures two AUCs: the out-of-bag one (OOB), which evaluates each label with the trees that did not see it, and that of the second half, sessions no tree has seen. The third way, “reduced”, is the cheap alternative that López de Prado himself proposes: samples with replacement of only $\overline{u} \cdot N$ labels.

from sklearn.metrics import roc_auc_score
from sklearn.tree import DecisionTreeClassifier

ent = np.flatnonzero(ds < n_ses // 2)
pru = np.flatnonzero(ds >= n_ses // 2)
bl_n = bloques_por_sesion(ds[ent], dm[ent], dn.fin.to_numpy()[ent])
u_ent = u_n[ent].mean()


def bagging(muestreo, n_arboles=40, semilla=0):
    """Trees on training samples; out-of-bag (OOB) AUC and
    AUC in the second half."""
    rng = np.random.default_rng(semilla)
    n = len(ent)
    p_pru = np.zeros(len(pru))
    s_oob, n_oob = np.zeros(n), np.zeros(n)
    for _ in range(n_arboles):
        if muestreo == "standard":
            mu = rng.integers(0, n, n)
        elif muestreo == "reduced":
            mu = rng.integers(0, n, int(round(u_ent * n)))
        else:
            mu = bootstrap_secuencial(bl_n, n, rng)
        arbol = DecisionTreeClassifier(
            min_samples_leaf=5, max_features=2,
            random_state=int(rng.integers(2**31)))
        arbol.fit(Xd[ent][mu], yd[ent][mu])
        p_pru += arbol.predict_proba(Xd[pru])[:, 1]
        fuera = np.setdiff1d(np.arange(n), mu)
        s_oob[fuera] += arbol.predict_proba(Xd[ent][fuera])[:, 1]
        n_oob[fuera] += 1
    v = n_oob > 0
    return {"AUC_OOB": roc_auc_score(yd[ent][v], s_oob[v] / n_oob[v]),
            "AUC_prueba": roc_auc_score(yd[pru], p_pru / n_arboles)}


print(f"average uniqueness in training: {u_ent:.3f}")
tabla = pd.DataFrame({m: bagging(m) for m in
                      ("standard", "reduced", "sequential")}).T
tabla["diferencia"] = tabla.AUC_OOB - tabla.AUC_prueba
tabla.round(3)

average uniqueness in training: 0.137
            AUC_OOB  AUC_prueba  diferencia
standard      0.572       0.529       0.043
reduced       0.570       0.544       0.026
sequential    0.566       0.529       0.037

Three results, in order of importance:

1. The out-of-bag AUC is optimistic with any sampling. With the standard bootstrap it promises 0.572 and on new sessions it gives 0.529. The reason is the same as in random k-fold (lesson 5.4.1): each out-of-bag label has overlapping neighbors inside, with almost the same price path and almost the same label, and the tree has memorized them. The OOB of a random forest with financial labels is not a validation.
2. Reducing the sample to $\overline{u} \cdot N$ is what helps most. Each tree sees about 1,850 labels instead of 13,500: the trees are more different from one another, memorize fewer neighbors and the average generalizes better. The test AUC rises to 0.544 and the difference with the OOB drops from 0.043 to 0.026.
3. The sequential bootstrap, here, changes nothing (0.529 on the test). It raises the uniqueness of each sample, but it still draws $N$ labels, and with a concurrency of 7.6 almost all of them remain overlapped with others. The method shines when concurrency is moderate and uneven; with a lot of uniform overlap, the lever is the sample size.

The differences between AUCs of 0.529 and 0.544 look small, but with 13,640 test labels they are stable: the seeds change the third decimal. And they are still modest AUCs, because the FNX signal is that of a market: the improvement is the kind that matters when trading many times, not the kind you see in a single trade.

What to use and when

Exercises

1. Compute the average uniqueness of the labels with a vertical at 60 minutes instead of 30. How much does it drop and how many “effective” labels are left?

e60 = triple_barrera(C, eventos_cusum(lr, sig), h=60)
e60 = e60[e60.fin > e60.minuto]
a60 = e60.sesion.to_numpy() * 390 + e60.minuto.to_numpy() + 1
b60 = e60.sesion.to_numpy() * 390 + e60.fin.to_numpy() + 1
d60 = np.zeros(G + 1)
np.add.at(d60, a60, 1)
np.add.at(d60, b60, -1)
c60 = np.cumsum(d60)[:G]
acu60 = np.r_[0.0, np.cumsum(1 / np.maximum(c60, 1))]
u60 = (acu60[b60] - acu60[a60]) / (b60 - a60)
print(f"average uniqueness {u60.mean():.3f}; effective {u60.sum():.0f}"
      f" of {len(u60)}; mean life {(e60.fin - e60.minuto).mean():.1f}")

average uniqueness 0.347; effective 2270 of 6533; mean life 42.6

2. Repeat the comparison between the standard bootstrap and the reduced sample with scikit-learn's RandomForestClassifier and 200 trees. Does the result hold?

from sklearn.ensemble import RandomForestClassifier

for ms in (None, u_ent):
    rf = RandomForestClassifier(
        n_estimators=200, min_samples_leaf=5, max_features=2,
        max_samples=ms, oob_score=True, random_state=0, n_jobs=4)
    rf.fit(Xd[ent], yd[ent])
    oob = roc_auc_score(yd[ent], rf.oob_decision_function_[:, 1])
    prueba = roc_auc_score(yd[pru], rf.predict_proba(Xd[pru])[:, 1])
    nombre = "standard" if ms is None else f"max_samples={ms:.3f}"
    print(f"{nombre:>20}: OOB {oob:.3f}  test {prueba:.3f}")

            standard: OOB 0.576  test 0.536
   max_samples=0.137: OOB 0.582  test 0.553

3. A colleague trains a model with the labels every 3 minutes, chooses the depth of the trees with the random forest's oob_score_ and gets an AUC of 0.60. What would you tell them?