jmlr jmlr2006 jmlr2006-68 jmlr2006-68-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Michael Schmitt, Laura Martignon
Abstract: Fast and frugal heuristics are well studied models of bounded rationality. Psychological research has proposed the take-the-best heuristic as a successful strategy in decision making with limited resources. Take-the-best searches for a sufficiently good ordering of cues (or features) in a task where objects are to be compared lexicographically. We investigate the computational complexity of finding optimal cue permutations for lexicographic strategies and prove that the problem is NP-complete. It follows that no efficient (that is, polynomial-time) algorithm computes optimal solutions, unless P = NP. We further analyze the complexity of approximating optimal cue permutations for lexicographic strategies. We show that there is no efficient algorithm that approximates the optimum to within any constant factor, unless P = NP. The results have implications for the complexity of learning lexicographic strategies from examples. They show that learning them in polynomial time within the model of agnostic probably approximately correct (PAC) learning is impossible, unless RP = NP. We further consider greedy approaches for building lexicographic strategies and determine upper and lower bounds for the performance ratio of simple algorithms. Moreover, we present a greedy algorithm that performs provably better than take-the-best. Tight bounds on the sample complexity for learning lexicographic strategies are also given in this article. Keywords: bounded rationality, fast and frugal heuristic, PAC learning, NP-completeness, hardness of approximation, greedy method
E. Amaldi and V. Kann. The complexity and approximability of finding maximum feasible subsystems of linear relations. Theoretical Computer Science, 147:181–210, 1995. E. Amaldi and V. Kann. On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems. Theoretical Computer Science, 209:237–260, 1998. Martin Anthony and Peter L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, Cambridge, 1999. G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and Approximation: Combinatorial Problems and Their Approximability Properties. Springer-Verlag, Berlin, 1999. G. Ausiello, A. D’Atri, and M. Protasi. Structure preserving reductions among convex optimization problems. Journal of Computer and System Sciences, 21:136–153, 1980. R. Bar-Yehuda and S. Even. A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 2:198–203, 1981. M. Bellare, S. Goldwasser, C. Lund, and A. Russell. Efficient probabilistically checkable proofs and applications to approximation. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, pages 294–304. ACM Press, New York, NY, 1993. Arndt Br¨ der. Assessing the empirical validity of the “take-the-best” heuristic as a model of human o probabilistic inference. Journal of Experimental Psychology: Learning, Memory, and Cognition, 26:1332–1346, 2000. 80 L EARNING L EXICOGRAPHIC S TRATEGIES Arndt Br¨ der. Take the best, Dawes’ rule, and compensatory decision strategies: A regression-based o classification method. Quality & Quantity, 36:219–238, 2002. Arndt Br¨ der and Stefanie Schiffer. Take the best versus simultaneous feature matching: Probao bilistic inferences from memory and effects of representation format. Journal of Experimental Psychology: General, 132:277–293, 2003. Seth Bullock and Peter M. Todd. Made to measure: Ecological rationality in structured environments. Minds and Machines, 9:497–541, 1999. William W. Cohen, Robert E. Schapire, and Yoram Singer. Learning to order things. Journal of Artificial Intelligence Research, 10:243–270, 1999. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, CA, 1979. Gerd Gigerenzer and Daniel G. Goldstein. Reasoning the fast and frugal way: Models of bounded rationality. Psychological Review, 103:650–669, 1996. Gerd Gigerenzer, Ulrich Hoffrage, and Heinz Kleinb¨ lting. Probabilistic mental models: A o Brunswikian theory of confidence. Psychological Review, 98:506–528, 1991. Gerd Gigerenzer, Peter M. Todd, and the ABC Research Group. Simple Heuristics That Make Us Smart. Oxford University Press, New York, NY, 1999. Russell Greiner. The complexity of revising logic programs. The Journal of Logic Programming, 40:273–298, 1999. Russell Greiner and Pekka Orponen. Probably approximately optimal satisficing strategies. Artificial Intelligence, 82:21–44, 1996. Dorit S. Hochbaum. Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing, 11:555–556, 1982. Klaus-U. H¨ ffgen, Hans-U. Simon, and Kevin S. Van Horn. Robust trainability of single neurons. o Journal of Computer and System Sciences, 50:114–125, 1995. Robin M. Hogarth and Natalia Karelaia. “Take-the-best” and other simple strategies: Why and when they work “well” in binary choice. DEE Working Paper 709, Universitat Pompeu Fabra, Barcelona, October 2003. Michael J. Kearns, Robert E. Schapire, and Linda M. Sellie. Toward efficient agnostic learning. Machine Learning, 17:115–141, 1994. Michael D. Lee and Tarrant D. R. Cummins. Evidence accumulation in decision making: Unifying the “take the best” and the “rational” models. Psychonomic Bulletin & Review, 11:343–352, 2004. Laura Martignon and Ulrich Hoffrage. Why does one-reason decision making work? A case study in ecological rationality. In Gigerenzer, G., Todd, P. M., and the ABC Research Group, Simple Heuristics That Make Us Smart, pages 119–140. Oxford University Press, New York, NY, 1999. 81 S CHMITT AND M ARTIGNON Laura Martignon and Ulrich Hoffrage. Fast, frugal, and fit: Simple heuristics for paired comparison. Theory and Decision, 52:29–71, 2002. Laura Martignon and Michael Schmitt. Simplicity and robustness of fast and frugal heuristics. Minds and Machines, 9:565–593, 1999. Stefani Nellen. The use of the “take the best” heuristic under different conditions, modeled with ACT-R. In F. Detje, D. D¨ rner, and H. Schaub, editors, Proceedings of the Fifth Internao tional Conference on Cognitive Modeling, pages 171–176, Universit¨ tsverlag Bamberg, Bama berg, 2003. Ben R. Newell and David R. Shanks. Take the best or look at the rest? Factors influencing “OneReason” decision making. Journal of Experimental Psychology: Learning, Memory, and Cognition, 29:53–65, 2003. Ben R. Newell, Nicola J. Weston, and David R. Shanks. Empirical tests of a fast-and-frugal heuristic: Not everyone “takes-the-best”. Organizational Behavior and Human Decision Processes, 91: 82–96, 2003. Ran Raz and Shmuel Safra. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 475–484. ACM Press, New York, NY, 1997. Ronald L. Rivest. Learning decision lists. Machine Learning, 2:229–246, 1987. Stuart Russell and Eric Wefald. Do The Right Thing: Studies in Limited Rationality. MIT Press, Cambridge, MA, 1991. Michael Schmitt and Laura Martignon. Complexity of lexicographic strategies on binary cues. Preprint, 1999. Michael Schmitt and Laura Martignon. On the accuracy of bounded rationality: How far from optimal is fast and frugal? In Yair Weiss, Bernhard Sch¨ lkopf, and John C. Platt, editors, Advances o in Neural Information Processing Systems 18. MIT Press, Cambridge, MA, 2006. To appear. Herbert A. Simon. Models of Bounded Rationality, Volume 2. MIT Press, Cambridge, MA, 1982. Herbert A. Simon and Joseph B. Kadane. Optimal problem-solving search: All-or-none solutions. Artificial Intelligence, 6:235–247, 1975. Herbert A. Simon and Joseph B. Kadane. Problems of computational complexity in artificial intelligence. In J. F. Traub, editor, Algorithms and Complexity: New Directions and Recent Results, pages 281–299. Academic Press, New York, NY, 1976. Steven S. Skiena. The Algorithm Design Manual. Springer-Verlag, New York, NY, 1997. D. W. Slegers, G. L. Brake, and M. E. Doherty. Probabilistic mental models with continuous predictors. Organizational Behavior and Human Decision Processes, 81:98–114, 2000. 82 L EARNING L EXICOGRAPHIC S TRATEGIES Peter M. Todd and Anja Dieckmann. Heuristics for ordering cue search in decision making. In Lawrence K. Saul, Yair Weiss, and L´ on Bottou, editors, Advances in Neural Information Proe cessing Systems 17, pages 1393–1400. MIT Press, Cambridge, MA, 2005. Peter M. Todd and Gerd Gigerenzer. Pr´ cis of “Simple Heuristics That Make Us Smart”. Behavioral e and Brain Sciences, 23:727–741, 2000. V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16:264–280, 1971. 83