A model to suggest salient examples to annotate I have a very large dataset of items that are all initially unlabeled. A user picks at random 5-20 items, labels them and creates an initial training set for a model. The model is trained and is ready to do the predictions.
The problem with the model that it has been trained on too few training examples and performs poorly on unseen data. The user goes back to the dataset and picks 5-20 items at random and runs the trained model to obtain the predictions. The user discards all those items that are either correctly labeled by the model or otherwise uninteresting (e.g. unsure if it is correct, junk data). The items that are picked, get annotation corrected and added to the training set. The model is re-trained and a new model is obtained.
The user iteratively builds the model and soon realizes that the process is very manual. She also notices that random sampling strategy is perhaps not the best because eventually, some of the sampled items are very similar to those seen before. It gets harder and harder to find novel, informative items to add to the training set. She wonders if she can do better than assigning equal sampling probability to the remaining items in the dataset.
The items that have been previously examined (both rejected and accepted ones for annotation) are never picked again.
The model returns confidence predictions (from 0 to 1) but it is very noisy. The model is very fast to train (subsecond) and is not a problem here.
My question is: Is there a way to build an iterative procedure that will still sample from the dataset but will suggest relevant examples to annotate that are better than plain random sampling? Or is this problem misspecified?
I am not looking for a sampling method that will magically propose new examples to annotate. It should be just better than random sampling.
I currently have one expert user and would like to postpone the option to use crowd to do the work.
 A: If I have understood your question correctly, it sounds like your are in a situation where the machine learning field of active learning might help.  
The method you are proposing sounds is called uncertainty sampling in active learning. There are certainly other algorithms besides this available: for instance you might like to look at this survey on the subject or John Langford's tutorial from ICML.  
Is the problem misspecified? I don't think so, but I'm not quite sure how to answer that so I'll quote what I think is relevant from Burr's survey:

An important question is: “does active learning work?” Most of the
  empirical results in the published literature suggest that it does
  (e.g., the majority of papers in the bibliography of this survey).
  Furthermore, consider that software companies and large-scale research
  projects such as CiteSeer, Google, IBM, Microsoft, and Siemens are
  increasingly using active learning technologies in a variety of
  realworld applications

I'm not sure what the current theoretical state of affairs is, but I believe there is a proof that under reasonable conditions in the binary classification setting active learning outperforms a model trained using a dataset built by random sampling. This is discussed further here. 
I think there's at least one reasonable implementation of an active learning algorithm in Langford's software Vowpal Wabbit.
