Abstract
We consider the minimum entropy principle for learning data generated by a random source and observed with random noise.
In our setting we have a sequence of observations of objects drawn uniformly at random from a population. Each object in the population belongs to one class. We perform an observation for each object which determines that it belongs to one of a given set of classes. Given these observations, we are interested in assigning the most likely class to each of the objects.
This scenario is a very natural one that appears in many real life situations. We show that under reasonable assumptions finding the most likely assignment is equivalent to the following variant of the set cover problem. Given a universe U and a collection \({\cal S} = (S_1,\ldots,S_m)\) of subsets of U, we wish to find an assignment \(f:U \to \cal S\) such that u ∈ f(u) and the entropy of the distribution defined by the values |f − − 1(S i )| is minimized.
We show that this problem is NP-hard and that the greedy algorithm for set cover finds a cover with an additive constant error with respect to the optimal cover. This sheds a new light on the behavior of the greedy set cover algorithm. We further enhance the greedy algorithm and show that the problem admits a polynomial time approximation scheme (PTAS).
Finally, we demonstrate how this model and the greedy algorithm can be useful in real life scenarios, and in particular, in problems arising naturally in computational biology.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Chvátal, V.: A greedy heuristic for the set-covering problem. Mathematics of Operations Research 4, 233–235 (1979)
Feige, U.: A threshold of ln n for approximating set cover. Journal of the ACM 45 (1998)
Hardy, G.H., Littlewood, J.E., Polya, G.: Inequalities. Cambridge University Press, Cambridge (1934)
Herskovits, E.H., Cooper, G.F.: Kutato: an entropy-driven system for construction of probabilistic expert systems from database. In: Proceedings of the Sixth Conference on Uncertainty in Artificial Intelligence, pp. 54–62 (1990)
Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. In: Proceedings of the 25rd Annual ACM Symposium on Theory of Computing, San Diego, California, pp. 286–293 (1993)
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, El Paso, Texas, pp. 475–484 (1997)
Roberts, S., Everson, R., Rezek, I.: Minimum entropy data partitioning. In: Proc. of 9th International Conference on Articial Neural Networks, pp. 844–849 (1999)
Roberts, S.J., Holmes, C., Denison, D.: Minimum-entropy data partitioning using reversible jump markov chain monte carlo. IEEE Transactions on Pattern Analysis and Machine Intelligence 23(8), 909–914 (2001)
Sharan, R.: Personal communication (2003)
Xiang, Y., Michael Wong, S.K., Cercone, N.: A “microscopic” study of minimum entropy search in learning decomposable markov networks. Machine Learning 26(1), 65–92 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Halperin, E., Karp, R.M. (2004). The Minimum-Entropy Set Cover Problem. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds) Automata, Languages and Programming. ICALP 2004. Lecture Notes in Computer Science, vol 3142. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27836-8_62
Download citation
DOI: https://doi.org/10.1007/978-3-540-27836-8_62
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22849-3
Online ISBN: 978-3-540-27836-8
eBook Packages: Springer Book Archive