Abstract
In most concept learning problems considered so far by the learning theory community, the instances are labeled by a single unknown target. However, in some situations, although the target concept may be quite complex when expressed as a function of the attribute values of the instance, it may have a simple relationship with some intermediate (yet to be learned) concepts. In such cases, it may be advantageous to learn both these intermediate concepts and the target concept in parallel, and use the intermediate concepts to enhance our approximation of the target concept.
In this paper, we consider the problem of learning multiple interrelated concepts simultaneously. To avoid stability problem, we assume that the dependency relations among the concepts are not cyclical and hence can be expressed using a directed acyclic graph (not known to the learner). We investigate this learning problem in various popular theoretical models: mistake bound model, exact learningmo del and probably approximately correct (PAC) model.
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
D. Angluin, M. Frazier, and L. Pitt. Learning conjunctions of Horn clauses. Machine Learning, 9:147–164, 1992.
D. Angluin, L. Hellerstein, and M. Karpinski. Learning read-once formulas with queries. J. ACM, 40:185–210, 1993.
D. Angluin and M. Krikis. Learningwith malicious membership queries and exceptions. In Proc. 7th Annu. ACM Workshop on Comput. Learning Theory, pages 57–66. ACM Press, New York, NY, 1994.
Dana Angluin, Mārtinš Krikis, Robert H. Sloan, and György Turán. Malicious omissions and errors in answers to membership queries. Machine Learning, 28:211–255, 1997.
D. Angluin. Queries and concept learning. Machine Learning, 2(4):319–342, April 1988.
D. Angluin and D. K. Slonim. Learning monotone DNF with an incomplete membership oracle. In Proc. 4th Annu. Workshop on Comput. Learning Theory, pages 139–146, San Mateo, CA, 1991. Morgan Kaufmann.
David Barrington. Bounded-width polynomial-size branching programs recognize exactly those language in nc. JCSS, 38:150–164, 1989.
Jonathan Baxter. Learningin ternal representations. In Proc. 8th Annu. Conf. on Comput. Learning Theory, pages 311–320. ACM Press, New York, NY, 1995.
Jonathan Baxter. A Bayesian/information theoretic model of learningto learn via multiple task sampling. Machine Learning, 28:7–39, 1997.
Avrim Blum, Prasad Chalasani, Sally A. Goldman, and Donna K. Slonim. Learningwith unreliable boundary queries. In Proc. 8th Annu. Conf. on Comput. Learning Theory, pages 98–107. ACM Press, New York, NY, 1995.
A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. J. ACM, 36(4):929–965, 1989.
Nader H. Bshouty, Christino Tamon, and David K. Wilson. On learning width two branchingprog rams. In Proc. 9th Annu. Conf. on Comput. Learning Theory, pages 224–227. ACM Press, New York, NY, 1996.
Rich Caruana. Algorithms and applications for multitask learning. In Proc. 13th International Conference on Machine Learning, pages 87–95. Morgan Kaufmann, 1996.
R. Caruana. A dozen tricks with multitask learning. Lecture Notes in Computer Science, 1524:165–187, 1998.
N. Cesa-Bianchi, P. Long, and M. K. Warmuth. Worst-case quadratic loss bounds for on-line prediction of linear functions by gradient descent. IEEE Transactions on Neural Networks, 1995. To appear. An extended abstract appeared in COLT’ 93.
Rich Caruana, Lorien Pratt, and Sebastian Thrun. Multitask learning. Machine Learning, 28:41, 1997.
Thomas G. Dietterich, Hermann Hild, and Ghulum Bakiri. A comparison of ID3 and backpropagation for english text-to-speech mapping. Machine Learning, 18:51–80, 1995.
Ricard Gavaldà and David Guijarro. Learningordered binary decision diagrams. In Proc. 6th Int. Workshop on Algorithmic Learning Theory, pages 228–238. Springer-Verlag, 1995.
D. P. Helmbold, J. Kivinen, and M. K. Warmuth. Worst-case loss bounds for sigmoided linear neurons. In Proc. 1996 Neural Information Processing Conference, 1996. To appear.
M. Kearns. Efficient noise-tolerant learningfrom statistical queries. In Proc. 25th Annu. ACM Sympos. Theory Comput., pages 392–401. ACM Press, New York, NY, 1993.
Michael J. Kearns, Robert E. Schapire, and Linda M. Sellie. Toward efficient agnostic learning. Machine Learning, 17(2/3):115–142, 1994.
J. Kivinen and M. K. Warmuth. Exponentiated gradient versus gradient descent for linear predictors. Technical Report UCSC-CRL-94-16, University of California, Santa Cruz, Computer Research Laboratory, June 1994. Revised December 7, 1995. An extended abstract to appeared in the STOC 95, pp. 209–218.
N. Littlestone. Learningwhen irrelevant attributes abound: A new linearthreshold algorithm. Machine Learning, 2:285–318, 1988.
Ronald L. Rivest. Learningdecision lists. Machine Learning, 2:229–246, 1987.
Steven C. Suddarth and Alistair D. C. Holden. Symbolic-neural systems and the use of hints for developingcomplex systems. International Journal of Man-Machine Studies, 35(3):291–311, 1991.
S. C. Suddarth and Y. L. Kergosien. Rule-injection hints as a means of improvingnet work performance and learningtime. In Proceedings of the EURASIP Workshop on Neural Networks, pages 120–129, Sesimbra, Portugal, February 1990. EURASIP.
L. G. Valiant. A theory of the learnable. Commun. ACM, 27(11):1134–1142, November 1984.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kwek, S.S. (2001). Learning Intermediate Concepts. In: Abe, N., Khardon, R., Zeugmann, T. (eds) Algorithmic Learning Theory. ALT 2001. Lecture Notes in Computer Science(), vol 2225. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45583-3_13
Download citation
DOI: https://doi.org/10.1007/3-540-45583-3_13
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42875-6
Online ISBN: 978-3-540-45583-7
eBook Packages: Springer Book Archive