# Constructing an ROC curve without true negatives?

I’m not really a statistician by training so please excuse any incorrect terminology or if this is a painfully obvious question. I am trying to assess the performance of two algorithms. I don’t wish to divulge too much about the nature of these algorithms for reasons of confidentiality, so perhaps a useful analogy is character recognition. Each algorithm references a database of 300 letters in different languages. Given some letter-like input, these algorithms try to answer the question, which letter is this most likely to represent?

I have a test data set of 29 letter-like inputs that have been experimentally confirmed to match one of the 300 letters. Algorithm performance can be measured in a straightforward manner by determining how many of the 29 letter-like inputs are correctly matched to the correct letter in the database. However, each algorithm assigns a score to the match corresponding to the algorithm’s confidence that this represents a true match. There is also the possibility that any given letter-like input actually corresponds to a letter in a different language, which is not contained in the common letter database. I therefore wanted to assess the performance of each algorithm at different cutoffs, and somehow graphically represent the ratio of true positives to false positives at each cutoff point.

This seemed like a ROC curve problem so I went about constructing an ROC plot for each algorithm. The problem is that I have no true negatives. That is, my training data set is 29 letter-like inputs that should each be matched to a letter which is contained in the database. This means the point 1,1 will never occur on the graph. It also means that, at least using DeLong et al’s 1988 approach, I cannot statistically compare the difference in the area under the two curves.

Am I understanding this correctly as an ROC curve problem? Would another technique be more appropriate to compare the accuracy of each algorithm at a series of discrete cutoffs? Do I simply need to somehow generate a negative training set?