Sweden SAIO · Correction IOAI Training

Liszten Closely

Cette page donne toute la méthode. Lisez-la une fois que vous avez cherché.

Métrique: 200 - MSE (capped to [0,100])
Évaluée sur: held-out validation (official test labels are private)
Notre score: MSE 108.7, score 91.3
Niveau attendu: full score at MSE 100; best Kattis score 89.4

Notre solution n'atteint pas le niveau attendu : il reste de la marge pour faire mieux

Nous avons résolu l'épreuve nous-mêmes : téléchargé les données, mené les expériences et mesuré le score ci-dessous. L'énoncé et les données appartiennent à leurs organisateurs. Cette correction est rédigée en anglais.

The problem in brief

You hear 19 consecutive notes of a piano piece (for each note: its onset time, duration, MIDI pitch and velocity) and you are told the composer. You must predict the pitch of the 20th note as a real number. There are 119 640 labelled training windows and 51 275 test windows, cut from recorded classical piano performances of the same kind as in the sister problem Haydn Seek. It is from the Swedish AI Olympiad final 2025 (problem by Arvid Kristoffersson). You print one number per test window.

The test answers are hidden, so all scores below come from 20 000 training windows held out from fitting.

How you are scored

The statement calls $S$ the sum of squared differences, but a sum over 51 275 windows would always exceed 200 and give 0, and the published scores (around 89) only make sense if $S$ is the mean squared error in semitones squared, so we read it that way:

\text{Score} = \max\big(0,\ \min(100,\ 200 - \text{MSE})\big).

Every unit of MSE is a point. Full marks need MSE $\le 100$ , an RMSE of 10 semitones. That sounds lax, until you see how unpredictable the next note is.

What to aim for. The Kattis statistics show no full solve. The best score is 89.4 (MSE about 110.6), and the next ones are 80.8 and 79.7.

First look at the data

The pitch of the next note has a variance of 195.7. Predicting a constant would therefore score about 4.
The last note is a bad guess: MSE 255. Notes are listed by onset time, and piano music is two-handed and full of chords, so the next note often jumps to the other hand. The histogram below shows the jump from the last note: it is broad, with sharp peaks at $\pm 12$ and $\pm 24$ (octaves) and none at 0 (repeated notes are rare).
The mean of the 19 pitches is much better: MSE 147.6, a score of 52. Under squared error, the best constant guess is the centre of the register the passage lives in.
Inside chords, the order of notes with near-equal onsets is not sorted by pitch (going up 43 %, down 57 %), so there is no bookkeeping shortcut.
In 61 % of windows, the answer is one of the 19 pitches already played.

Distribution of the pitch jump, and error by matched context length

A first baseline

MSE rewards predicting the conditional mean $\mathbb{E}[\text{pitch}_{20} \mid \text{window}]$ . For a bimodal situation ("the next note is either the bass or the melody"), the best answer under squared error is in between, even though no real note is ever played there.

Gradient boosting (HistGradientBoostingRegressor) on about 150 hand-made features: the 19 pitches relative to their mean, the same sorted, spread and range, durations, velocities, gaps between onsets, intervals, the pitch-class histogram, and the composer as a categorical variable. To help the trees, the target is the offset from the window's mean pitch. This model reaches MSE 124.6, score 75.4.

The key idea

Every window teaches 18 transitions for free, without any label. Inside a 19-note window, notes 1 to $k$ are followed by note $k+1$ , notes 2 to $k+1$ by note $k+2$ , and so on. Pooling all windows, training and test, gives a corpus of about 3 million "context of $k$ pitches, then the next pitch" examples. This uses no answer at all, so it is not leakage: it is unsupervised use of the test inputs, exactly as a language model is pre-trained on raw text.

Since many pieces appear in several performances, the last $k$ notes of a window have often been heard elsewhere, followed by a known note. For each window and each $k \in \{2,3,4,5,6,8,10\}$ , we look up its last $k$ pitches and record three features: how often that context occurred, the average next pitch (relative to the last note) and its spread. We do the same with intervals instead of absolute pitches, which makes a melody match even in another key. This is a classical $n$ -gram language model, and we let the boosted trees learn the back-off: trust long contexts when they have been seen often, fall back to shorter ones otherwise.

The right panel of the figure shows why it works. When only a 2- or 3-note context has been seen elsewhere (27 % of windows), the error stays large. When a 6- to 10-note context has been seen (27 % of windows), the boosted model's error falls to 50 to 70, three times better than the register mean.

Adding these 39 features takes boosting from MSE 124.6 to 110.2.

The full solution

Parse the JSON lists into an array of shape (windows, 19, 4).
Corpus $n$ -gram statistics from all 170 915 windows, using pandas groupby on 64-bit hashes of the contexts (7 bits per pitch). It takes 12 s.
Gradient boosting on the $n$ -gram features plus the hand-made features, predicting the offset from the mean pitch (learning rate 0.05, 63 leaves, early stopping at about 400 trees).
A second, different model: a 2-layer GRU (192 units) reads the 19 notes (a pitch embedding plus duration, velocity, gap and composer) and outputs a probability distribution over the 128 MIDI pitches. We train it with cross-entropy and predict the mean of the distribution, which is the MSE-optimal answer if the distribution is well calibrated. It overfits after about 5 epochs (validation MSE rises from 126.6 to 137.8 over 12 epochs), so we train it for 6 epochs with a one-cycle learning rate. Alone, it reaches 126.
Blend: $0.8 \times$ boosting $+\ 0.2 \times$ GRU. We chose the weight on one half of the validation windows and report on the other half.
For Kattis, the predictions are rounded to half a semitone (which adds less than 0.03 to the MSE), packed as bytes, compressed and embedded in a 49 KiB program that prints them.

Results

MSE on held-out training windows (official test answers are private). The final row is measured on the 10 000 windows that were not used to pick the blend weight.

approach	MSE	score
last pitch	255.1	0
constant (mean pitch of the training set)	195.7	4.3
mean of the 19 pitches	147.6	52.4
corpus $n$ -gram back-off alone (longest context seen at least 3 times)	144.5	55.5
GRU, distribution over pitches, 12 epochs (overfits)	137.8	62.2
GRU, 6 epochs	126.0	74.0
boosting, hand-made features	124.6	75.4
boosting + corpus $n$ -gram features	110.3	89.7
blend 0.8 boosting + 0.2 GRU (final)	108.7	91.3

That is slightly above the best Kattis score (89.4), but still 8.7 MSE short of full marks.

What to remember

Under squared error, predict the conditional mean. A bimodal outcome is answered "in between", and the mean of a predicted distribution is a good way to get there.
Unlabelled data, including the test inputs, can be mined for self-supervised statistics: here every window holds 18 free next-note examples.
$n$ -gram counts with several context lengths, fed to boosted trees, give a learned back-off model in a few lines of pandas.
Two models with different biases (trees on counts, a sequence network) blend for a free gain. Tune the weight on data you do not report on.
Check the score's units: here "sum" has to mean "mean", or no published score is possible.

Code complet (solution.py)

"""SAIO Liszten Closely: predict the pitch of note 20 from notes 1-19 (score = 200 - MSE).

Model = 0.8 * gradient boosting on hand-made + corpus n-gram features
      + 0.2 * GRU that outputs a distribution over the 128 MIDI pitches (we use its mean).
Corpus n-grams: inside every 19-note window of train AND test, each run of k notes is followed
by a known note; we index "k previous pitches -> next pitch" (no labels needed, no leakage)
and look up the last k notes of the window to predict (k = 2..10, absolute and interval form).

  python3 solution.py --validate   # hold-out estimate (weight tuned on half A, reported on half B)
  python3 solution.py              # fit on all data, write predictions.txt + Kattis submission.py
Run from the folder that contains data/train.csv and data/test.csv.
"""
import sys, json, zlib, base64
import numpy as np, pandas as pd, torch, torch.nn as nn
from sklearn.ensemble import HistGradientBoostingRegressor
torch.set_num_threads(2)
W_GRU = 0.2


def load(name):
    d = pd.read_csv(f'data/{name}.csv')
    X = np.stack([np.array([json.loads(s) for s in d[c]], dtype=float)
                  for c in ['start', 'duration', 'pitch', 'velocity']], -1)     # (n, 19, 4)
    y = d['answer'].values.astype(float) if 'answer' in d else None
    return X, d['composer'].values.astype(str), y


def hand_features(X, comp, classes):
    s, d, p, v = [X[..., k] for k in range(4)]
    m = p.mean(1, keepdims=True)
    F = [p - m, np.sort(p - m, 1), m, p.std(1, keepdims=True), p.min(1, keepdims=True) - m,
         p.max(1, keepdims=True) - m, d, v, np.diff(s, axis=1),
         (s + d).max(1, keepdims=True) - s[:, -1:], s[:, -1:], np.diff(p, axis=1),
         np.stack([(p % 12 == k).mean(1) for k in range(12)], 1), p[:, -1:] % 12,
         np.searchsorted(classes, comp)[:, None]]                     # composer id (categorical, last)
    return np.hstack(F).astype(np.float32)


def kgram_hash(A, k, j):
    h = np.zeros(len(A), dtype=np.int64)
    for t in range(j - k, j): h = h * 128 + A[:, t].astype(np.int64)
    return h


def ngram_features(P_corpus, P_query, ks, rel):
    """Count, mean and spread of the note that followed the query's last k notes in the corpus."""
    A = np.diff(P_corpus, axis=1) + 64 if rel else P_corpus
    Q = np.diff(P_query, axis=1) + 64 if rel else P_query
    out = []
    for k in ks:
        df = pd.DataFrame({'h': np.concatenate([kgram_hash(A, k, j) for j in range(k, A.shape[1])]),
                           'n': np.concatenate([A[:, j] for j in range(k, A.shape[1])]).astype(float)})
        df['n2'] = df.n ** 2
        g = df.groupby('h').agg(s=('n', 'sum'), c=('n', 'count'), q=('n2', 'sum'))
        r = g.reindex(kgram_hash(Q, k, Q.shape[1]))
        cnt = r['c'].fillna(0).values
        mean = (r['s'] / r['c']).values
        sd = np.sqrt(np.maximum((r['q'] / r['c']).values - mean ** 2, 0))
        out += [np.log1p(cnt), mean - Q[:, -1], sd]                   # NaN when unseen (HGB handles it)
    return np.column_stack(out).astype(np.float32)


class GRUNet(nn.Module):
    def __init__(s, n_comp, h=192):
        super().__init__()
        s.pe, s.ce = nn.Embedding(128, 64), nn.Embedding(n_comp, 16)
        s.inp = nn.Linear(64 + 4 + 16, h)
        s.gru = nn.GRU(h, h, num_layers=2, batch_first=True, dropout=0.1)
        s.out = nn.Sequential(nn.Linear(h, h), nn.GELU(), nn.Linear(h, 128))
    def forward(s, p, x, c):
        z = torch.cat([s.pe(p), x, s.ce(c)[:, None].expand(-1, p.shape[1], -1)], -1)
        o, _ = s.gru(torch.relu(s.inp(z)))
        return s.out(o[:, -1])                                        # logits over 128 pitches


def gru_tensors(X, comp, classes):
    s, d, p, v = [X[..., k] for k in range(4)]
    ioi = np.diff(s, axis=1, prepend=s[:, :1])
    cont = np.stack([(p - p.mean(1, keepdims=True)) / 12, np.log(d + 1e-3), v / 64 - 1,
                     np.log(ioi + 1e-3)], -1).astype(np.float32)
    return (torch.tensor(p.astype(np.int64)), torch.tensor(cont),
            torch.tensor(np.searchsorted(classes, comp)))


def fit_gru(T, y, n_comp, epochs=6, bs=512):
    torch.manual_seed(0)
    dev = 'mps' if torch.backends.mps.is_available() else 'cpu'
    net = GRUNet(n_comp).to(dev)
    opt = torch.optim.AdamW(net.parameters(), 2e-3, weight_decay=1e-4)
    sched = torch.optim.lr_scheduler.OneCycleLR(opt, 2e-3, total_steps=epochs * (len(y) // bs))
    grid = torch.arange(128, device=dev).float(); Y = torch.tensor(y.astype(np.int64))
    for ep in range(epochs):
        perm = np.random.default_rng(ep).permutation(len(y))
        for i in range(0, len(y) - bs + 1, bs):
            b = perm[i:i + bs]
            logit = net(*(t[b].to(dev) for t in T)); yb = Y[b].to(dev)
            ev = (torch.softmax(logit, -1) * grid).sum(-1)
            loss = nn.functional.cross_entropy(logit, yb) + 0.01 * ((ev - yb) ** 2).mean()
            opt.zero_grad(); loss.backward(); opt.step(); sched.step()
    def predict(Tq):
        net.eval(); out = []
        with torch.no_grad():
            for i in range(0, len(Tq[0]), 4096):
                pr = torch.softmax(net(*(t[i:i + 4096].to(dev) for t in Tq)), -1)
                out.append((pr * grid).sum(-1).cpu())                 # expected pitch = MSE-optimal
        return torch.cat(out).numpy()
    return predict


def fit_predict(Xa, ca, ya, Fa, Xb, cb, Fb, classes):
    ma, mb = Xa[:, :, 2].mean(1), Xb[:, :, 2].mean(1)
    hgb = HistGradientBoostingRegressor(max_iter=2000, learning_rate=0.05, max_leaf_nodes=63,
                                        min_samples_leaf=40, l2_regularization=1,
                                        categorical_features=[Fa.shape[1] - 1], early_stopping=True,
                                        validation_fraction=0.1, n_iter_no_change=50, random_state=0)
    hgb.fit(Fa, ya - ma)                                              # predict offset from mean pitch
    p_hgb = hgb.predict(Fb) + mb
    p_gru = fit_gru(gru_tensors(Xa, ca, classes), ya, len(classes))(gru_tensors(Xb, cb, classes))
    return p_hgb, p_gru


if __name__ == '__main__':
    X, c, y = load('train'); Xt, ct, _ = load('test'); classes = np.unique(np.concatenate([c, ct]))
    P, Pt = X[:, :, 2].astype(int), Xt[:, :, 2].astype(int); corpus = np.vstack([P, Pt])
    def all_features(Xq, cq, Pq):
        return np.hstack([ngram_features(corpus, Pq, (2, 3, 4, 5, 6, 8, 10), False),
                          ngram_features(corpus, Pq, (2, 3, 4, 5, 6, 8), True),
                          hand_features(Xq, cq, classes)])
    F, Ft = all_features(X, c, P), all_features(Xt, ct, Pt)
    if '--validate' in sys.argv:
        perm = np.random.default_rng(0).permutation(len(y)); va, tr = perm[:20000], perm[20000:]
        ph, pg = fit_predict(X[tr], c[tr], y[tr], F[tr], X[va], c[va], F[va], classes)
        A, B = np.arange(10000), np.arange(10000, 20000)
        mse = lambda p, idx: ((p[idx] - y[va][idx]) ** 2).mean()
        ws = np.linspace(0, 1, 11)
        w = ws[np.argmin([mse(wi * pg + (1 - wi) * ph, A) for wi in ws])]
        for name, p in [('mean of 19 pitches', X[va, :, 2].mean(1)), ('HGB', ph), ('GRU', pg),
                        (f'blend w={w:.1f}', w * pg + (1 - w) * ph)]:
            print(f'{name:22s} MSE on half B {mse(p, B):7.2f}  score {max(0, min(100, 200 - mse(p, B))):.1f}')
    else:
        ph, pg = fit_predict(X, c, y, F, Xt, ct, Ft, classes)
        pred = np.clip(W_GRU * pg + (1 - W_GRU) * ph, 0, 127)
        np.savetxt('predictions.txt', pred, fmt='%.2f')
        code = base64.b85encode(zlib.compress(np.round(pred * 2).astype(np.uint8).tobytes(), 9)).decode()
        open('submission.py', 'w').write('import zlib,base64\nfor b in zlib.decompress(base64.b85decode('
                                         f'{code!r})):print(b/2)\n')
        print('wrote', len(pred), 'predictions; submission.py',
              len(open('submission.py').read()) // 1024, 'KiB')