JAIR article: "Learing to Order Things"

[Steve Minton]

Readers of this mailing list may be interested in the following
article, which was just published by JAIR:

Cohen, W.W., Schapire, R.E., and Singer, Y. (1999)
  "Learning to Order Things", 
   Volume 10, pages 243-270.

   Available in PDF, PostScript and compressed PostScript.
   For quick access via your WWW browser, use this URL:
     http://www.jair.org/abstracts/cohen99a.html
   More detailed instructions are below.

   Abstract: There are many applications in which it is desirable to
   order rather than classify instances. Here we consider the problem of
   learning how to order instances given feedback in the form of
   preference judgments, i.e., statements to the effect that one instance
   should be ranked ahead of another.  We outline a two-stage approach in
   which one first learns by conventional means a binary preference
   function indicating whether it is advisable to rank one instance
   before another. Here we consider an on-line algorithm for learning
   preference functions that is based on Freund and Schapire's 'Hedge'
   algorithm.  In the second stage, new instances are ordered so as to
   maximize agreement with the learned preference function.  We show that
   the problem of finding the ordering that agrees best with a learned
   preference function is NP-complete.  Nevertheless, we describe simple
   greedy algorithms that are guaranteed to find a good approximation.
   Finally, we show how metasearch can be formulated as an ordering
   problem, and present experimental results on learning a combination of
   'search experts', each of which is a domain-specific query expansion
   strategy for a web search engine.

The article is available via:
   
 -- comp.ai.jair.papers (also see comp.ai.jair.announce)

 -- World Wide Web: The URL for our World Wide Web server is
       http://www.jair.org/
    For direct access to this article and related files try:
       http://www.jair.org/abstracts/cohen99a.html

 -- Anonymous FTP from either of the two sites below.

    Carnegie-Mellon University (USA):
	ftp://ftp.cs.cmu.edu/project/jair/volume10/cohen99a.ps
    The University of Genoa (Italy):
	ftp://ftp.mrg.dist.unige.it/pub/jair/pub/volume10/cohen99a.ps

    The compressed PostScript file is named cohen99a.ps.Z (229K)

 -- automated email. Send mail to jair at cs.cmu.edu or jair at ftp.mrg.dist.unige.it
    with the subject AUTORESPOND and our automailer will respond. To
    get the Postscript file, use the message body GET volume10/cohen99a.ps 
    (Note: Your mailer might find this file too large to handle.) 
    Only one can file be requested in each message.

For more information about JAIR, visit our WWW or FTP sites, or
send electronic mail to jair at cs.cmu.edu with the subject AUTORESPOND
and the message body HELP, or contact jair-ed at ptolemy.arc.nasa.gov.