Classifier that optimizes performance on only a subset of the data?

Question

I'm working on machine learning problem where I'm only interested in getting high accuracy within a narrow band of my predicted likelihoods. Specifically, I want an algorithm that will score very accurately when it predicts a likelihood above a specific threshold.

A motivating example:

I'm presented with 1 million closed boxes, 10 percent of which contain a gold coin. The likelihood of a box containing a gold coin is associated with physical characteristics of the boxes. I'm allowed to open 500K boxes, chosen at random, to see which contain the coins. After this, I'm allowed to choose 100 of the remaining 500K boxes and keep any gold that I find.

I'm looking to build a classifier to solve this problem. Specifically, I'm looking for the correct way to incorporate the constraint that I am only able to open 100 boxes in the test sample. Put another way, my measure of performance is limited to a subsample of my test data, so I need a classifier that is highly accurate when it predicts the highest likelihoods. Prediction errors outside of these 100 boxes are of zero concern.

I'm aware of cost-weighted loss functions that penalize false positives/negatives differently, but I'm not familiar with any that solve this specific problem of optimizing for a localized accuracy.

Specifically, I'm trying to answer two questions:
1) Are there specific classification algorithms well suited for this type of problem? 2) Can I modify the loss function used on my training set to produce a high localized accuracy within these specific 100 boxes?

Answer 1

I want to clarify that the fact that you can pick only 100 boxes from the test dataset is NOT a limitation (like you describe it). You just need to see it from this perspective:

How to pick the 100 boxes (out of 500K) that MOST LIKELY contain gold?

A very suitable algorithm would be a Decision Tree classifier. By using the Information Gain (based on Entropy Reduction), it can learn which features can split the dataset more accurately into two classes, i.e. the one that contains gold and the one that doesn't, and neglect (prune) the weakest attributes. After that, you will not only have a trained classifier but also gain insight on which features are the most important to make the decision (very important information).

Answer 2

There are at least two approaches:

1. Train on a subsample of data. 100 positive examples and only 100 negative examples (randomly sampled from all negative samples).
2. Create a 2 pass system. 1st pass uses a high recall algorithm, selects reasonable options (eliminate options that are not reasonable). The 2nd pass is a high precision algorithm. It only looks possible options and selects the most likely options.

Answer 3

Great question, and yes it is possible (as you alluded in point #2) to re-weight your loss function to accomplish your objective. In fact, training on a subsample is a special case of this. However, we’ll first have to assume that your loss function is additively-separable (which is the case for 95% of popular machine learning models).

Let’s say your loss function is $f$ and your model parameter is $x$. Then, to get your optimal model parameter $x_*$, you would solve the problem

$$x_* = \text{argmin}_x f(x)$$

Now let’s say $f$ is additively-separable

$$f(x) = \sum_i^n f_i (x)$$

where $i$ indexes observations from your data set—this is the case for linear regression, logistic regression, SVM, and many more. Well, it naturally follows that

$$x_* = \text{argmin}_x f(x) = \text{argmin}_x \sum_i^n f_i(x) = \text{argmin}_x \sum_i^n \alpha_i f_i(x)$$

where $\alpha_i = 1$ for all $i$. You can think of $\alpha_i$ being the importance of the $i^{th}$ observation: as $\alpha_i$ gets larger, you are essentially biasing the parameter $x_*$ towards that observation. In fact, if you set $\alpha_i$ negative, then observation $i$ is now treated as a counterexample for the model. And when $\alpha_i$ is set to 0, it’s as if you trained your model without observation $i$ included—a special case of withholding data from the model as mentioned in other answers.

You can manipulate the set of weights $\{\alpha_i\}_1^n$ if you have reason to believe that not all observations in your dataset are equally important. A real world example would be setting $\alpha_i$ proportional to the monetary losses caused by some fraudulent event. Then the model isn’t just trying to accurately predict fraud, but moreso to accurately predict costly fraud events.