Besting the Quiz Master: Crowdsourcing Incremental Classification Games

Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 1290–1301, Jeju Island, Korea, 12–14 July 2012. c⃝2012 Association for Computational Linguistics Besting the Quiz Master: Crowdsourcing Incremental Classification Games Jordan Boyd-Graber iSchool and UMIACS University of Maryland jbg@umiacs.umd.edu Brianna Satinoff, He He, and Hal Daum´e III Department of Computer Science University of Maryland {bsonrisa, hhe, hal}@cs.umd.edu Abstract Cost-sensitive classification, where the features used in machine learning tasks have a cost, has been explored as a means of balancing knowl- edge against the expense of incrementally ob- taining new features. We introduce a setting where humans engage in classification with incrementally revealed features: the collegiate trivia circuit. By providing the community with a web-based system to practice, we collected tens of thousands of implicit word-by-word ratings of how useful features are for eliciting correct answers. Observing humans’ classifi- cation process, we improve the performance of a state-of-the art classifier. We also use the dataset to evaluate a system to compete in the incremental classification task through a reduc- tion of reinforcement learning to classification. Our system learns when to answer a question, performing better than baselines and most hu- man players. 1 Introduction A typical machine learning task takes as input a set of features and learns a mapping from features to a label. In such a setting, the objective is to minimize the error of the mapping from features to labels. We call this traditional setting, where all of the features are consumed, rapacious machine learning.1 This not how humans approach the same task. They do not exhaustively consider every feature. Af- ter a certain point, a human has made a decision and no longer needs additional features. Even in- defatigable computers cannot always exhaustively consider every feature. This is because the result 1Earlier drafts called this “batch” machine learning, which confused the distinction between batch and online learning. We gladly adopt “rapacious” to make this distinction clearer and to cast traditional machine learning—that always examines all features—as a resource hungry approach. is time sensitive, such as in interactive systems, or because processing time is limited by the sheer quan- tity of data, as in sifting e-mail for spam (Pujara et al., 2011). In such settings, often the best solution is incremental: allow a decision to be made without seeing all of an instance’s features. We discuss the incremental classification framework in Section 2. Our understanding of how humans conduct incre- mental classification is limited. This is because com- plicating an already difficult annotation task is often an unwise tradeoff. Instead, we adapt a real world setting where humans are already engaging (eagerly) in incremental classification—trivia games—and de- velop a cheap, easy method for capturing human incremental classification judgments. After qualitatively examining how humans con- duct incremental classification (Section 3), we show that knowledge of a human’s incremental classifi- cation process improves state-of-the-art rapacious classification (Section 4). Having established that these data contain an interesting signal, we build Bayesian models …

Content truncated to 500 words