Smart data split (train/eval) for Object Detection

Question

I am looking for a smart way of splitting object detection data (images with labelled objects inside them) while taking into account the distribution of the objects themselves and not just the images.

I have a dataset composed of many images. Each of these images has one or more objects inside, which are labelled. In order to train an object detection model, I need to perform the traditional train/eval split (in this case I don't need a test set). However, I have very specific requirements as for which labels should end up in each set.

Concretely, I want to ensure that a minimum amount of samples per label ends up in the train and eval sets. For example, if I know that I only have 5 samples of cars, I want to ensure that at least 3 of these cars will be in the train set. Therefore, a simple random split of the images (E.g. 80/20) is not ideal, because it doesn't take into account the objects within each image and thus cannot enforce my constraints. For example, if only two images have cars, one with three and one with two, nothing will stop these two images to be in the train set, and thus I might not have any cars for evaluation!

Naturally, these constraints could be impossible to achieve (if there is a single image were all cars are, it will not be possible to have cars in both train and eval), which is something the algorithm should manage. (i.e. giving the most optimal solution that complies with the requirements as best as it can).

A few other complications:

• Each image can have any number of objects belonging to any number of labels, so adding an image to either set will affect the distribution of all labels it contains.
• As a result of the previous point, enforcing one constraint in one set can invalidate another in the other set (for the same label or even for a different one).

Have you encountered this problem before? Any suggestions?

Please let me know if more details are required and I will updated the post accordingly. Thanks in advance.

EDIT 1: Adding integer programming approach status

This is a working example of the current integer solution in Python, using cvxpy:

Needed libraries:

import numpy as np
import cvxpy

Example data:

# rows -> classes, columns -> images
L = np.array([[2, 0, 0, 0, 3, 0, 8, 0, 0],
              [0, 3, 0, 2, 0, 0, 0, 8, 0],
              [0, 0, 2, 0, 0, 3, 0, 0, 8]])
big_L = np.vstack((np.hstack((L, np.zeros_like(L))),
                   np.hstack((np.zeros_like(L), L))))

# minimum examples per class for each set
left_min = [2, 2, 2]
right_min = [2, 2, 2]

# maximum examples per class for each set
left_max = [9, 9, 9]
right_max = [2, 2, 2]

# number of frames and classes
nc, n = L.shape

Some variables needed to define constraints:

w = np.hstack((np.array(left_min), np.array(right_min))).T
max_w = np.hstack((np.array(left_max), np.array(right_max))).T

s = cvxpy.Variable(2*n, boolean=True)

big_s = np.vstack((np.hstack((np.zeros((n, n)), np.eye(n))),
                   np.hstack((np.eye(n), np.zeros((n, n))))))

Constraints:

# constraints
# only one frame can be selected for each set
output_constraint_0 = (big_s @ s) + s <= np.ones((2*n))

# only one frame can be selected for each set
output_constraint_01 = (big_s @ s) + s >= np.zeros((2*n))

# all frames must be selected for either set
output_constraint_1 = cvxpy.sum(s) == cvxpy.Variable(n, integer=True)

# result vector must be binary, only zeros or ones (and in between?) 
output_constraint_2 = np.eye(2*n) @ s <= np.ones(2*n)
output_constraint_3 = - np.eye(2*n) @ s <= np.zeros(2*n)

# sets have at least required quantities of examples per class
output_constraint_4 = big_L @ s - w >= np.zeros((2*nc))

# check that train has required (for now, we ignore eval numbers)
output_constraint_5 = big_L @ s - max_w >= np.zeros((2*nc))

constraints = [output_constraint_0, output_constraint_01,
               output_constraint_1, output_constraint_2,
               output_constraint_3, output_constraint_4,
               output_constraint_5]

# Objective function
objective = cvxpy.norm((big_s @ s) + s - np.ones((2*n)))

Define problem and solve:

split_problem = cvxpy.Problem(cvxpy.Minimize(objective), constraints)
split_problem.solve()

Get images indices for each set and assert results are as intended:

result = s.value.reshape((2, n))
l = np.array([int(x) for x in np.round(s.value[:n])], dtype=np.int)
r = np.array([int(x) for x in np.round(s.value[n:])], dtype=np.int)

assert all(L @ l >= left_min) and all(L @ l >= left_max)
assert all(L @ r >= right_min) and all(L @ r >= right_max)

While this solution works for simple cases such as the presented example dataset above, it does not work for real-life datasets, with much more complicated classes distribution. The problem is mainly with infeasible "max number of examples" constraints, which can be remedied by iterating through different train/eval fractions (e.g. 0.2, 0.3, 0.4, ...) and solving the problem for each of them, which can eventually reach a solution (in the worst case, eval fraction would be 1). Here we assume that if the problem is infeasible with an eval_fraction of x, there is an eval_fraction, y, bigger than x, that can make the problem solvable.

Another complication is that the current solver we are using, namely "ECOS_BB" (more information here and here), is way too slow for big datasets, making it completely impractical for real usage. Additionally, cvxpy only uses a single CPU core, with the lack of processing speed that implies.

So, the next step is to find a suitable solution that can process large, very heterogeneous datasets taking advantage of all hardware available and in a reasonable time.

Answer 1

I guess I might as well put forward the integer program formulation alluded to in the comments.

Let $A=(a_{ij})$, where $a_{ij}$ is the number of object $i$ in image $j$. We have a binary variable $x_j$ for each image $j$, a 1 indicating that we will include the image in the training set. Then $Ax$ is the vector whose $i$th entry is the number of object $i$ included in the training set. Putting a lower bound on $Ax$ gives the lower bound desired in the training set, and putting an upper bound on it gives the complementary lower bound desired in the validation set.

This doesn't use an objective function yet, so you could just ask for feasibility, or add something to optimize.

If the integer program is infeasible, you could add and subtract new variables (I think I was wrong to call them "slack variables" in the comments?) from the bounds on $Ax$, and minimize the sum of those variables. You'd be guaranteed a solution that way, could see how far off you are, and could see which objects are the problematic ones [for that solution anyway].

EDIT: Unless I've misunderstood something, or you had a next step in mind, your MILP can be simplified quite a bit. And here's what I had in mind for minimizing violations. I've changed L and the bounds a bit to get an infeasible original problem. (That's something I don't understand from your example: what are the four bounds?) Setting x as binary, and L being nonnegative integers, we get for free that the outputs are nonnegative integers and the new lr, ur ("lower/upper relaxation") are integral, but we need to enforce nonegativity. Finally, since you're already using a convex optimization software, I thought making the objective the square of the violations should yield "nicer" results.

import numpy as np
import cvxpy

L = np.array([[2,3,0,3,0,8,4],
              [3,0,2,0,0,0,4],
              [0,2,5,1,3,0,2]])
nc, n = L.shape

train_mins = np.array([12,6,8])
valid_mins = np.array([7,3,4])

x = cvxpy.Variable(n, boolean=True)
lr = cvxpy.Variable(nc, nonneg=True)
ur = cvxpy.Variable(nc, nonneg=True)

lb = (L @ x >= train_mins.T - lr)
ub = (L @ x <= (sum(L.T)-valid_mins).T + ur)
constraints = [lb, ub]

objective = (sum(lr)+sum(ur))**2

problem = cvxpy.Problem(cvxpy.Minimize(objective), constraints)
problem.solve()

(https://github.com/bmreiniger/datascience.stackexchange/blob/master/54450.ipynb)

Assuming that's all right, it at least removes the need to iterate through different train/eval proportions. (You could modify the upper and lower bounds and the relaxations/objective to put it more in terms of the train/eval proportions.)

I'm not so familiar with different solvers. A superficial glance suggests that ECOS_BB isn't actually built for MICP, so maybe backing the objective off to a linear one is a better idea.