Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

PAC Learning: Empirical Risk Minimization

In course

MATH-412: Statistical machine learning

A course on statistical machine learning for supervised and unsupervised learning ...

Description

This lecture delves into quantifying how much an algorithm learns using the PAC learning framework, introducing the Empirical Risk Minimization principle, discussing the ill-posed nature of learning, the need for inductive bias, and different predictor/hypothesis spaces.

Instructor

Yoav Zemel

Official source

Related concepts (32)

Machine learning

Machine learning (ML) is an umbrella term for solving problems for which development of algorithms by human programmers would be cost-prohibitive, and instead the problems are solved by helping machines 'discover' their 'own' algorithms, without needing to be explicitly told what to do by any human-developed algorithms. Recently, generative artificial neural networks have been able to surpass results of many previous approaches.

Supervised learning

Supervised learning (SL) is a paradigm in machine learning where input objects (for example, a vector of predictor variables) and a desired output value (also known as human-labeled supervisory signal) train a model. The training data is processed, building a function that maps new data on expected output values. An optimal scenario will allow for the algorithm to correctly determine output values for unseen instances. This requires the learning algorithm to generalize from the training data to unseen situations in a "reasonable" way (see inductive bias).

Computation

A computation is any type of arithmetic or non-arithmetic calculation that is well-defined. Common examples of computations are mathematical equations and computer algorithms. Mechanical or electronic devices (or, historically, people) that perform computations are known as computers. The study of computation is the field of computability, itself a sub-field of computer science. The notion that mathematical statements should be ‘well-defined’ had been argued by mathematicians since at least the 1600s, but agreement on a suitable definition proved elusive.

Pareto distribution

The Pareto distribution, named after the Italian civil engineer, economist, and sociologist Vilfredo Pareto, is a power-law probability distribution that is used in description of social, quality control, scientific, geophysical, actuarial, and many other types of observable phenomena; the principle originally applied to describing the distribution of wealth in a society, fitting the trend that a large portion of wealth is held by a small fraction of the population.

Predictive modelling

Predictive modelling uses statistics to predict outcomes. Most often the event one wants to predict is in the future, but predictive modelling can be applied to any type of unknown event, regardless of when it occurred. For example, predictive models are often used to detect crimes and identify suspects, after the crime has taken place. In many cases, the model is chosen on the basis of detection theory to try to guess the probability of an outcome given a set amount of input data, for example given an email determining how likely that it is spam.

Related lectures (49)

Machine Learning Fundamentals

Covers the fundamental principles and methods of machine learning, including supervised and unsupervised learning techniques.

Unsupervised Learning: Dimensionality Reduction

Explores unsupervised learning techniques for reducing dimensions in data, emphasizing PCA, LDA, and Kernel PCA.

Supervised Learning: Linear Regression

Covers supervised learning with a focus on linear regression, including topics like digit classification, spam detection, and wind speed prediction.

Active Learning for Molecular Design

Covers machine learning approaches for material design, practical examples, and software tools for research.

World of Data: Machine Learning and Value Chain