Learning with attribute costs

ABSTRACT

We study an extension of the "standard" learning models to settings where observing the value of an attribute has an associated cost (which might be different for different attributes). Our model assumes that the correct classification is given by some target function f from a class of functions cal F; most of our results discuss the ability to learn a clause (an OR function of a subset of the variables) in various settings:Offline: We are given both the function f and the distribution D that is used to generate an input x. The goal is to design a strategy to decide what attribute of x to observe next so as to minimize the expected evaluation cost of f(x). (In this setting there is no "learning" to be done but only an optimization problem to be solved; this problem to be NP-hard and hence approximation algorithms are presented.)Distributional online: We study two types of "learning" problems; one where the target function f is known to the learner but the distribution D is unknown (and the goal is to minimize the expected cost including the cost that stems from "learning" D), and the other where f is unknown (except that f∈cal F) but D is known (and the goal is to minimize the expected cost while limiting the prediction error involved in "learning" f).Adversarial online: We are given f, however the inputs are selected adversarially. The goal is to compare the learner's cost to that of the best fixed evaluation order (i.e., we analyze the learner's performance by a competitive analysis).

REFERENCES

• 1: D. Angluin and L. G. Valiant. Fast probabilistic algorithms for Hamiltonian circuits and matchings. JCSS, 18(2):155--193, April 1979.
• 2: Shivnath Babu , Rajeev Motwani , Kamesh Munagala , Itaru Nishizawa , Jennifer Widom, Adaptive ordering of pipelined stream filters, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007615]
• 3: Amotz Bar-Noy , Mihir Bellare , Magnús M. Halldórsson , Hadas Shachnai , Tami Tamir, On chromatic sums and distributed resource allocation, Information and Computation, v.140 n.2, p.183-202, Feb. 1, 1998 [doi>10.1006/inco.1997.2677 ]
• 4: A. Bar-Noy, M. M. Halldórsson, and G. Kortsarz. A matched approximation bound for the sum of a greedy coloring. IPL, 71(3-4):135--140, 1999.
• 5: Moses Charikar , Ronald Fagin , Venkatesan Guruswami , Jon Kleinberg , Prabhakar Raghavan , Amit Sahai, Query strategies for priced information (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.582-591, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335382]
• 6: E. Cohen, A. Fiat, and H. Kaplan. Associative search in peer to peer networks: Harnessing latent semantics. In Proceedings IEEE INFOCOM , 2003.
• 7: O. Madani, Efficient information gathering on the Internet, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.234, October 14-16, 1996
• 8: Oren Etzioni , Steve Hanks , Tao Jiang , Omid Madani, Optimal Information Gathering on the Internet with Time and Cost Constraints, SIAM Journal on Computing, v.29 n.5, p.1596-1620, March 2000 [doi>10.1137/S0097539797314465]
• 9: Uriel Feige , László Lovász , Prasad Tetali, Approximating Min-sum Set Cover, Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, p.94-107, September 17-21, 2002
• 10: Joseph M. Hellerstein , Michael Stonebraker, Predicate migration: optimizing queries with expensive predicates, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.267-276, May 25-28, 1993, Washington, D.C., United States
• 11: A. T. Kalai and S. Vempala. Efficient algorithms for online decision problems. In COLT, 26--40, 2003.
• 12: Michael Kharitonov, Cryptographic hardness of distribution-specific learning, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.372-381, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167197]
• 13: Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
• 14: D. J. Lizotte, O. Madani, and R. Greiner. Budgeted learning of naive-bayes classifiers. In UAI, 378--385, 2003.
• 15: O. Madani, D. J. Lizotte, and R. Greiner. Active model selection. ICML, 2004.
• 16: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 17: K. Munagala, S. Babu, R. Motwani, and J. Widom. The pipelined set cover problem. ICDT, 2005.
• 18: R. Smorodinsky and M. Tennenholtz. Overcoming free riding in multi-party computations - the anonymous case. Unpublished, 2004.
• 19: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• 20: L. G. Valiant. Learning disjunctions of conjunctions. IJCAI, 560--566, 1985

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, learning, online