Haim Kaplan
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).
- D. Angluin and L. G. Valiant. Fast probabilistic algorithms for Hamiltonian circuits and matchings. JCSS, 18(2):155--193, April 1979.Google Scholar
Cross Ref
- S. Babu, R. Motwani, K. Munagala, I. Nishizawa, and J. Widom. Adaptive ordering of pipelined stream filters. In SIGMOD, 2004. Google ScholarDigital Library
- A. Bar-Noy, M. Bellare, M. M. Halldórsson, H. Shachnai, and T. Tamir. On chromatic sums and distributed resource allocation. Inf. Comput., 140(2):183--202, 1998. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- M. Charikar, R. Fagin, V. Guruswami, J. Kleinberg, P. Raghavan, and A. Sahai. Query strategies for priced information. In 32nd STOC, pages 582--591, 2000. Google ScholarDigital Library
- E. Cohen, A. Fiat, and H. Kaplan. Associative search in peer to peer networks: Harnessing latent semantics. In Proceedings IEEE INFOCOM, 2003.Google ScholarCross Ref
- O. Etzioni, S. Hanks, T. Jiang, R. M. Karp, O. Madani, and O. Waarts. Efficient information gathering on the internet. In FOCS, 234--243, 1996. Google ScholarDigital Library
- O. Etzioni, S. Hanks, T. Jiang, and O. Madani. Optimal information gathering on the internet with time and cost constraints. SIAM J. Comput., 29(5):1596--1620, 2000. Google ScholarDigital Library
- U. Feige, L. Lovász, and P. Tetali. Approximating min-sum set cover. In APPROX, 94--107, 2002. Google ScholarDigital Library
- J. M. Hellerstein and M. Stonebraker. Predicate migration: optimizing queries with expensive predicates. In SIGMOD, 267--276. ACM Press, 1993. Google ScholarDigital Library
- A. T. Kalai and S. Vempala. Efficient algorithms for online decision problems. In COLT, 26--40, 2003.Google Scholar
- M. Kharitonov. Cryptographic hardness of distribution-specific learning. CLOT, 372--381, 1993. Google ScholarDigital Library
- N. Littlestone. Learning when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2:285--318, 1988. Google ScholarDigital Library
- D. J. Lizotte, O. Madani, and R. Greiner. Budgeted learning of naive-bayes classifiers. In UAI, 378--385, 2003. Google ScholarDigital Library
- O. Madani, D. J. Lizotte, and R. Greiner. Active model selection. ICML, 2004.Google Scholar
- R. Motwani and P. Raghavan. Randomized algorithms. Cambridge University Press, 1995. Google ScholarDigital Library
- K. Munagala, S. Babu, R. Motwani, and J. Widom. The pipelined set cover problem. ICDT, 2005. Google ScholarDigital Library
- R. Smorodinsky and M. Tennenholtz. Overcoming free riding in multi-party computations - the anonymous case. Unpublished, 2004.Google Scholar
- L. G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134--1142, 1984. Google ScholarDigital Library
- L. G. Valiant. Learning disjunctions of conjunctions. IJCAI, 560--566, 1985Google Scholar
Index Terms
- Learning with attribute costs
Recommendations
Approximation algorithms for inventory problems with submodular or routing costs
We consider the following two deterministic inventory optimization problems with non-stationary demands. Submodular joint replenishment problem. This involves multiple item types and a single retailer who faces demands over a finite planning horizon of ...
Learning attribute-efficiently with corrupt oracles
We study learning in a modified EXACT model, where the oracles are corrupt and only few of the presented attributes are relevant. Both modifications were already studied in the literature [Dana Angluin, Martins Krikis, Learning with malicious membership ...
Primal-Dual Algorithms for Deterministic Inventory Problems
We consider several classical models in deterministic inventory theory: the single-item lot-sizing problem, the joint replenishment problem, and the multistage assembly problem. These inventory models have been studied extensively, and play a ...
Comments