Accuracy over different sample sizes from dataset

Question

What I'm trying to do is predict how much more data would help in a classification task.

So, what I'm doing is bootstrapping entries in my dataset to get a sample, with a specified size. Then, I fine-tune a KNN model on the sample, and compute it's accuracy. I do this multiple times for one specified size, storing the accuracies in a list, from which I can compute the mean accuracy as well as the standard deviation of accuracies. And then rinse-and-repeat, for a different specified number of samples.

After doing this for enough different sample sizes, I practically get a new dataset, which I can fit a line to and predict how much more data would help.

However, this new "Accuracy vs. Sample Size" dataset surprises me.
What I expected was that at small sample sizes, more data would help out a lot, but with bigger sample sizes, more data would help out less. I'm also interested in the random noise between points, I understand that there will generally be more noise with smaller sample sizes, but the change is just so sudden (at around the sample_size=100 point). These results stayed consistent throughout multiple simulations. Can anyone explain this behaviour to me? I have a feeling it might be to do with how ridiculously small my dataset is, and perhaps because of how KNNs work. But I can't say for certain, or why it would be the case.

Here's a minimal working example (in python):

# Imports
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
%matplotlib inline

from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import GridSearchCV

import warnings
warnings.filterwarnings("ignore")

def auto_knn(X, y):
    """
    Returns accuracy of KNN with fine-tuned 'n_neighbours', fitted on 'X' and 'y'.
    """
    knn = KNeighborsClassifier()
    min_range, max_range = 6, 9
    found_best = False
    while not found_best:
        knn_search = GridSearchCV(knn, [{
            "n_neighbors": list(range(min_range, max_range))
        }], cv=5, scoring="accuracy", return_train_score=True)
        knn_search.fit(X, y)
        if knn_search.best_params_["n_neighbors"] == min_range and min_range != 1:
            min_range, max_range = min_range-1, max_range-1
        elif knn_search.best_params_["n_neighbors"] == max_range-1:
            min_range, max_range = min_range+1, max_range+1
        else:
            found_best = True
    return knn_search.best_score_

def knn_scores_from_subsample(X, y, subsample_size, num_iters):
    """
    Samples 'X' and 'y' with replacement to get new dataset of specific size, then fine-tunes KNN and retrieves accuracy. Resamples and retrieves accuracy 'num_iters' times. Returns list of accuracies.
    """
    accuracys = []
    for i in range(num_iters):
        print("\r["+"".join(["=" for _ in range(round(i/num_iters*100))])+"".join([" " for _ in range(round(100-i/num_iters*100))])+"] - "+str(round((i/num_iters)*100, 1))+"%", end="")
        selected_indexes = np.random.randint(0, len(X)-1, (subsample_size,))
        accuracys.append(auto_knn(X.iloc[selected_indexes], y.iloc[selected_indexes]))
    return accuracys

import requests
from io import StringIO

# Here, I'm using the Heart Failure Dataset (https://www.kaggle.com/andrewmvd/heart-failure-clinical-data),
# I've already done feature engineering, selection and preparation, so I've uploaded the prepared dataset, 
# to easily retrieve here.
orig_url = 'https://drive.google.com/file/d/1qvIkRx07Il-Mat86MSo_i8iu2YEn9rnO/view?usp=sharing'
file_id = orig_url.split('/')[-2]
dwn_url='https://drive.google.com/uc?export=download&id=' + file_id
url = requests.get(dwn_url).text
csv_raw = StringIO(url)
data = pd.read_csv(csv_raw)
data = data.drop("Unnamed: 0", axis=1)
X = data.drop("DEATH_EVENT", axis=1)
y = data[["DEATH_EVENT"]]

# Generate 'accuracy' vs. 'specific sample size'
# NOTE: This can take a very long time, to generate the image (above), it took many hours.
scores_for_n = {}
for num_points in range(20, 300, 10):
    scores_for_n[num_points] = knn_scores_from_subsample(X, y, num_points, 3500) # This will resample (with replacement) the dataset 3500 different times (and compute the accuracy).
    print("\nFinished "+str(num_points)+" points. Got a mean accuracy of "+str(round(np.array(scores_for_n[num_points]).mean()*100, 3))+"% With a standard deviation of: "+str(round( np.array(scores_for_n[num_points]).std()*100 ,3))+"%")

# Plot 'accuracy' vs. 'specific sample size'
plt.scatter(data_points, accuracies)
plt.xlabel("Dataset Size")
plt.ylabel("Mean Accuracy")

Also, I've uploaded my "Accuracy vs. Sample Size" dataset to Google Drive, so you can retrieve it for your own inspection, here's the code to do it:

import pandas as pd

import requests
from io import StringIO

orig_url = 'https://drive.google.com/file/d/1DX4tE3l7qLnTxbfxpICNuNDiloGTmL_k/view?usp=sharing'
file_id = orig_url.split('/')[-2]
dwn_url='https://drive.google.com/uc?export=download&id=' + file_id
url = requests.get(dwn_url).text
csv_raw = StringIO(url)
data = pd.read_csv(csv_raw)
data = data.drop("Unnamed: 0", axis=1)

Answer 1

I've seen this kind of more-data-is-better curve before; it is likely the first part of an S-curve.

Intuitively, and abstractly, I think of it as there are N concepts and you need to see enough of each concept to understand the overall data. And, typically, your data for the N concepts will not be uniformly distributed, but some will be rarer than others. But once you have started to see enough of each concept, then the diminishing returns of more data that you expected will kick in.

I understand that there will generally be more noise with smaller sample sizes, but the change is just so sudden (at around the sample_size=100 point).

It could be that the model has not really learned anything in this region of the graph, and this is what you can score from random guessing, or choosing the biggest class?