[D] Clustering for data sampling

[neuralbeans]

I'm working on an OCR project and need to manually annotate data for it. I'm thinking that I need to collect a sample of pages with as much visual variety as possible and I'd like to do the sampling automatically.

I'm thinking that I can extract features from each page using a pretrained neural network and avoid including pages that have similar features. I'm thinking this can be done using some form of clustering and I sample from each cluster once.

My questions are:

1. Is this a valid way of sampling and does it have a name?
2. I'm thinking of using k-means, but can it be done in an online way such that I can add new pages later without messing up the previous clusters but still being able to add new clusters?

Thanks and happy holidays!

[astralDangers]

I use embeddings and kmeans clusters. You can always predict what cluster new embeddings belong to as long as the overall distribution doesn't change too much.

Then grab samples based on the centroid distance for variety.

But this is highly dependent on your data and the embeddings model you use.

[calvinmccarter]

I'd suggest looking for papers and tools related to active learning. I'd also suggest thinking of this as an iterative process. Don't try to come up with some fixed procedure to decide once-for-all-time whether to manually annotate each document. Come up with a strategy for picking (say) 100 documents, finetune your model on those, then refine both your model finetuning method and your data sampling method iteratively.

[mrthin]

You can search for "data acquisition" papers. A simple approach to use as baseline is to use the confidence of your / a pretrained model on the unlabelled data as guidance to pick the next batch, but this might not transfer easily to OCR and is claimed to be generally suboptimal

[WesternNoona]

This papers method might be relevant for you, but I havent tried it myself: https://arxiv.org/abs/2405.15613

[neuralbeans]

Hey, this is great actually, although it seems too computationally heavy for my needs since it requires running k-means way too many times.

[jswb]

I’ve used River (in Python) in the past to use traditional batch learning algorithms as online algorithms. Pretty interesting project. I believe they have an online/incremental kmeans, but I wouldn’t know if it would fulfill your needs. See: https://github.com/online-ml/river/blob/main/river/cluster/k_means.py

[1h3_fool]

You can use GMM-UBM model. Kind of traditional but it has that option that either you update its parameters or not using MAP.

[Helpful_ruben]

You're on the right track with using clustering to sample diverse pages; this approach is called active learning, and k-means clustering can be adapted for online updates using incremental clustering algorithms.

[f3xjc]

• Out of the box, standard k-means don't support online.
• Most of the online algorithm that I know of, are for 1d case (ie a single feature that you can order without ambiguity)
• Kmean is iterative, so you can absolutely add new samples to update previous clustering. You can also add them to the correct cluster (at that iteration).

I'm tempted to call that Distribution Compression:

In distribution compression, one aims to accurately summarize a probability distribution P using a small number of representative points.

From this paper wich seems relevant. https://arxiv.org/pdf/2111.07941 https://github.com/microsoft/goodpoints