Abstract
In this paper we demonstrate how weighted majority voting with multiplicative weight updating can be applied to obtain robust algorithms for learning binary relations. We first present an algorithm that obtains a nearly optimal mistake bound but at the expense of using exponential computation to make each prediction. However, the time complexity of our algorithm is significantly reduced from that of previously known algorithms that have comparable mistake bounds. The second algorithm we present is a polynomial time algorithm with a non-optimal mistake bound. Again the mistake bound of our second algorithm is significantly better than previous bounds proven for polynomial time algorithms.
A key contribution of our work is that we define a “non-pure” or noisy binary relation and then by exploiting the robustness of weighted majority voting with respect to noise, we show that both of our algorithms can learn non-pure relations. These provide the first algorithms that can learn non-pure binary relations.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Angluin, D. (1988). Queries and concept learning.Machine Learning, 2(4): pp. 319–342.
Barzdin, J. & Freivald, R. (1972). On the prediction of general recursive functions.Soviet Mathematics Doklady, 13: pp. 1224–1228.
Cesa-Bianchi, N., Freund, Y., Helmbold, D., Haussler, D., Schapire, R. & Warmuth, M. (1993). How to use expert advice.Proceedings of the Twenty Fifth Annual ACM Symposium on Theory of Computing, pp. 382–391.
Chen, W. (1992). Personal communication.
Goldman, S., Rivest, R. & Schapire, R. (1993). Learning binary relations and total orders.SIAM Journal of Computing, 22(5): pp. 1006–1034.
Kivinen, J. & and Warmuth, M. (1994) Using Experts for Predicting Continuous Outcomes.Computational Learning Theory: Eurocolt '93 pp. 109–120. Oxford University Press, Oxford, ISBN 0-19-853492-2.
Littlestone, N. (1988) Learning when irrelevant attributes abound: A new linear-threshold algorithm.Machine Learning, 2(4): pp. 285–318.
Littlestone, N. (1989)Mistake Bounds and Logarithmic Linear-threshold Learning algorithms. PhD thesis, U. C. Santa Cruz.
Littlestone, N., Long, P. & Warmuth, M. (1991) On-line learning of linear functions.Proceedings of the Twenty Third Annual ACM Symposium on Theory of Computing, pp. 465–475. To appear inJournal of Computational Complexity.
Littlestone, N. & Warmuth, M. (1994) The weighted majority algorithm.Information and Computation, 108(2): pp. 212–261.
Vovk, V. (1990) Aggregating strategies.Proceedings of the Third Annual Workshop on Computational Learning Theory, pp. 371–383. Morgan Kaufmann.
Author information
Authors and Affiliations
Additional information
The first author was supported in part by NSF grant CCR-91110108 and NSF National Young Investigator Grant CCR-9357707 with matching funds provided by Xerox Corporation, Palo Alto Research Center and WUTA. The second author was supported by ONR grant NO0014-91-J-1162 and NSF grant IRI-9123692.
Rights and permissions
About this article
Cite this article
Goldman, S.A., Warmuth, M.K. Learning binary relations using weighted majority voting. Mach Learn 20, 245–271 (1995). https://doi.org/10.1007/BF00994017
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF00994017