Lecture

PAC Learning: Empirical Risk Minimization

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

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)

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.

Predictive analytics

Predictive analytics is a form of business analytics applying machine learning to generate a predictive model for certain business applications. As such, it encompasses a variety of statistical techniques from predictive modeling and machine learning that analyze current and historical facts to make predictions about future or otherwise unknown events. It represents a major subset of machine learning applications; in some contexts, it is synonymous with machine learning.

Computational complexity theory

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used.

Related lectures (64)

Machine Learning: Supervised and Unsupervised Learning Techniques

Covers supervised and unsupervised learning techniques in machine learning, highlighting their applications in finance and environmental analysis.

Gaussian Naive Bayes & K-NN

Covers Gaussian Naive Bayes, K-nearest neighbors, and hyperparameter tuning in machine learning.

Landscape and Generalisation in Deep Learning

Explores the challenges and insights of deep learning, focusing on loss landscape, generalization, and feature learning.

Machine Learning Fundamentals

Introduces fundamental machine learning concepts, covering regression, classification, dimensionality reduction, and deep generative models.

Mathematics of Data: Models and Learning