Presenter: Bernardo Ávila Pires, Ph.D Candidate, Department of Computing Science, University of Alberta
Abstract: The theory developed by Vapnik and Chervonenkis provides a solid foundation to study the learnability of binary classification. For example, it is known that the so-called VC dimension of a hypothesis class precisely characterizes the amount of training data needed by optimal learning algorithms to compete against the best hypothesis in that class. It would be interesting to have a concept similar to the VC dimension for other discrete prediction problems. In fact, researchers have been after such notions of dimension for other discrete prediction problems, including multiclass classification, for many years by now, but so far their efforts have failed.
In order to study learnability in discrete prediction problems, we will look into the problem of "Probability Maximization". This is a discrete prediction problem that we define and which generalizes well-known problems, including binary and multiclass classification, multilabel prediction, relation learning and some flavors of clustering. I will show that in some instances of probability maximization an appropriate notion of dimension does not exist. This previously-unknown phenomenon raises the question of whether the search for appropriate notions of dimension in other discrete prediction problems could also be futile.
ai seminar series
Fridays at noon, Amii and the Department of Computing Science host AI Seminars, engaging presentations on topics in the broad field of artificial intelligence. With speakers from the University of Alberta and other world-leading groups, the talks give AI enthusiasts a friendly way of engaging with the latest trends and topics in research and development.
Seminars are open to the public, and no registration is required, though seating is limited and on a first-come-first-served basis. Topics range from foundational theoretical work to innovative applications of artificial intelligence technologies.
If you would like to present at an upcoming AI Seminar, please contact Colin Bellinger.
Join the AI Seminar mailing list to stay up-to-date on all the latest presentations.