I am considering training a neural network to place a number of data items into a list ordered by priority, so that the most important items are dealt with first and the least important are dealt with last. My training data will consist of pairs of items (A and B) and expected outputs with categories: "item A first", "item B first", or "order of these items is not important".
I can obviously train the network to simply categorize the pairs of items, but in operation this will be inefficient: if I have a large list of items to sort, I'll need to run $O(n \log n)$ pairs of items through the network to sort the list, so for example given a 64 item list, we'd have to run the network 384 times.
I wonder if it is possible to train a network that produces a single score that I can use a proxy for the items and just sort based on those scores. Then I'd only have to run the network once for each item in the list and use a traditional sorting method to sort the list. But how can I train such a network without knowing in advance what the scores should be? The only useful information I have is that I know pairs of inputs $A$ and $B$ such that $s(A) > s(B)$, but not the actual values themselves. I could arbitrarily assign numbers myself, but this could result in data that is harder for the network to learn than is necessary.
Is there a special training architecture or loss function I could use that would allow me to train the network to produce such numbers without needing to fix their actual value in advance?
