emnlp emnlp2012 emnlp2012-23 emnlp2012-23-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Jordan Boyd-Graber ; Brianna Satinoff ; He He ; Hal Daume III
Abstract: Cost-sensitive classification, where thefeatures used in machine learning tasks have a cost, has been explored as a means of balancing knowledge against the expense of incrementally obtaining 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’ classification 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 reduction of reinforcement learning to classification. Our system learns when to answer a question, performing better than baselines and most human players.
Pieter Abbeel and Andrew Y. Ng. 2004. Apprenticeship learning via inverse reinforcement learning. In Proceedings of International Conference of Machine Learning. J. Blatz, E. Fitzgerald, G. Foster, S. Gandrabur, C. Goutte, A. Kulesza, A. Sanchis, and N. Ueffing. 2004. Confidence estimation for machine translation. In Proceedings of the Association for Computational Linguistics. Mark Boddy and Thomas L. Dean. 1989. Solving timedependent planning problems. In International Joint Conference on Artificial Intelligence, pages 979–984. Morgan Kaufmann Publishers, August. Nicolo` Cesa-Bianchi, Shai Shalev-Shwartz, and Ohad Shamir. 2011. Efficient learning with partially observed attributes. Journal of Machine Learning Research, 12:2857–2878. Xiaoyong Chai, Lin Deng, Qiang Yang, and Charles X. Ling. 2004. Test-cost sensitive naive bayes classification. In IEEE International Conference on Data Mining. Dipanjan Das and Andre Martins. 2007. A survey on automatic text summarization. Engineering and Technology, 4: 192–195. Hal Daume´ III. 2004. Notes on CG and LMBFGS optimization of logistic regression. Paper available at http : / /pub .hal 3 .name / ˜ daume 0 4 cg-bfgs, implementation available at http : / /hal 3 .name /megam/ . Rong-En Fan, Kai-Wei Chang, Cho-Jui Hsieh, XiangRui Wang, and Chih-Jen Lin. 2008. LIBLINEAR: A library for large linear classification. Journal of Machine Learning Research, 9: 1871–1874. David Ferrucci, Eric Brown, Jennifer Chu-Carroll, James Fan, David Gondek, Aditya A. Kalyanpur, Adam Lally, J. William Murdock, Eric Nyberg, John Prager, Nico Schlaefer, and Chris Welty. 2010. Building Watson: 1300 An Overview of the DeepQA Project. AI Magazine, 31(3). Aria Haghighi and Dan Klein. 2007. Unsupervised coreference resolution in a nonparametric bayesian model. In Proceedings of the Association for Computational Linguistics. Eric Hardisty, Jordan Boyd-Graber, and Philip Resnik. 2010. Modeling perspective using adaptor grammars. In Proceedings of Emperical Methods in Natural Language Processing. Michael C. Horsch and David Poole. 1998. An anytime algorithm for decision making under uncertainty. In Proceedings of Uncertainty in Artificial Intelligence. Ken Jennings. 2006. Brainiac: adventures in the curious, competitive, compulsive world of trivia buffs. Villard. Shihao Ji and Lawrence Carin. 2007. Cost-sensitive feature acquisition and classification. Pattern Recognition, 40: 1474–1485, May. Shyong K. Lam, David M. Pennock, Dan Cosley, and Steve Lawrence. 2003. 1 billion pages = 1 million dollars? mining the web to play ”who wants to be a millionaire?”. In Proceedings of Uncertainty in Artificial Intelligence. John Langford and Bianca Zadrozny. 2005. Relating reinforcement learning performance to classification performance. In Proceedings of International Conference of Machine Learning. Roger P. Levy, Florencia Reali, and Thomas L. Griffiths. 2008. Modeling the effects of memory on human online sentence processing with particle filters. In Proceedings of Advances in Neural Information Processing Systems. Roger Levy. 2011. Integrating surprisal and uncertaininput models in online sentence comprehension: formal techniques and empirical results. In Proceedings of the Association for Computational Linguistics. David D. Lewis. 1998. Naive (Bayes) at forty: The independence assumption in information retrieval. In Claire Ne´dellec and Ce´line Rouveirol, editors, Proceedings of European Conference of Machine Learning, number 1398. Michael L. Littman, Greg A. Keim, and Noam Shazeer. 2002. A probabilistic approach to solving crossword puzzles. Artif. Intell., 134(1-2):23–55, January. Edward Loper and Steven Bird. 2002. NLTK: the natural language toolkit. In Tools and methodologies for teaching. Prem Melville, Maytal Saar-Tsechansky, Foster Provost, and Raymond J. Mooney. 2005. An expected utility approach to active feature-value acquisition. In International Conference on Data Mining, November. Dan Moldovan, Sanda Harabagiu, Marius Pasca, Rada Mihalcea, Roxana Girju, Richard Goodrum, and Vasile Rus. 2000. The structure and performance of an opendomain question answering system. In Proceedings of the Association for Computational Linguistics. Joakim Nivre. 2008. Algorithms for deterministic incremental dependency parsing. Comput. Linguist., 34(4):513–553, December. Jay Pujara, Hal Daume III, and Lise Getoor. 2011. Using classifier cascades for scalable e-mail classification. In Collaboration, Electronic Messaging, Anti-Abuse and Spam Conference, ACM International Conference Proceedings Series. Sebastian Riedel, David McClosky, Mihai Surdeanu, Andrew McCallum, and Christopher D. Manning. 2011. Model combination for event extraction in bionlp 2011. In Proceedings of the BioNLP Workshop. Afshin Rostamizadeh, Alekh Agarwal, and Peter L. Bartlett. 2011. Learning with missing features. In Proceedings of Uncertainty in Artificial Intelligence. Maytal Saar-Tsechansky and Foster Provost. 2007. Handling missing values when applying classification models. Journal of Machine Learning Research, 8: 1623– 1657, December. Gerard. Salton. 1968. Automatic Information Organization and Retrieval. McGraw Hill Text. Burr Settles. 2011. Closing the loop: Fast, interactive semi-supervised annotation with queries on features and instances. In Proceedings of Emperical Methods in Natural Language Processing. David Silver, Richard S. Sutton, and Martin Mu¨ller. 2008. Sample-based learning and search with permanent and transient memories. In International Conference on Machine Learning. Noah A. Smith, Michael Heilman, and Rebecca Hwa. 2008. Question generation as a competitive undergraduate course project. In Proceedings of the NSF Workshop on the Question Generation Shared Task and Evaluation Challenge. Umar Syed, Michael Bowling, and Robert E. Schapire. 2008. Apprenticeship learning using linear programming. In Proceedings of International Conference of Machine Learning. Gerald Tesauro and Gregory R. Galperin. 1996. On-line policy improvement using monte-carlo search. In Pro- ceedings of Advances in Neural Information Processing Systems. Robert Thibadeau, Marcel A. Just, and Patricia A. Carpenter. 1982. A model of the time course and content of reading. Cognitive Science, 6. Hanna M Wallach. 2008. Structured Topic Models for Language. Ph.D. thesis, University of Cambridge. Lidan Wang, Donald Metzler, and Jimmy Lin. 2010. Ranking Under Temporal Constraints. In Proceedings of the ACM International Conference on Information and Knowledge Management. 1301 Kevin Waugh, Brian D. Ziebart, and J. Andrew Bagnell. 2011. Computational rationalization: The inverse equilibrium problem. In Proceedings of International Conference of Machine Learning. F. Wood and Y. W. Teh. 2009. A hierarchical nonparametric Bayesian approach to statistical language model domain adaptation. In Proceedings of Artificial Intelligence and Statistics. Omar F. Zaidan, Jason Eisner, and Christine Piatko. 2008. Machine learning with annotator rationales to reduce annotation cost. In Proceedings of the NIPS*2008 Workshop on Cost Sensitive Learning. Valentina Bayer Zubek and Thomas G. Dietterich. 2002. Pruning improves heuristic search for cost-sensitive learning. Learning. In International Conference on Machine