We reduce ranking, as measured by the Area Under the Receiver Operating Characteristic Curve (AUC), to binary classification. The core theorem shows that a binary classification regret of r on the induced binary problem implies an AUC regret of at most 4r. (The binary problem is to predict, given a random pair of elements in the test set, whether the first element should be ordered before the second.) This is a large improvement over naive approaches such as ordering according to regressed scores, which have a regret transform of r --> nr where n is the number of elements.
By: Nina Balcan; Alina Beygelzimer; John Langford; Gregory B. Sorkin
Published in: RC24129 in 2006
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .