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

Lecture

Building a Decision Tree

In course

MGT-448: Statistical inference and machine learning

This course aims to provide graduate students a thorough grounding in the methods, theory, mathematics and algorithms needed to do research and applications in machine learning. The course covers topics from machine learning, classical statistics, and data ...

Description

This lecture covers the process of building a decision tree to classify mushrooms as poisonous or not based on given data. It includes determining entropy, selecting the root attribute, calculating information gain, and classifying new mushrooms. The lecture also discusses the greedy character of maximizing information gain and decision tree pruning techniques.

Instructor

Negar Kiyavash

Official source

Related concepts (32)

Information gain (decision tree)

In information theory and machine learning, information gain is a synonym for Kullback–Leibler divergence; the amount of information gained about a random variable or signal from observing another random variable. However, in the context of decision trees, the term is sometimes used synonymously with mutual information, which is the conditional expected value of the Kullback–Leibler divergence of the univariate probability distribution of one variable from the conditional distribution of this variable given the other one.

Mutual information

In probability theory and information theory, the mutual information (MI) of two random variables is a measure of the mutual dependence between the two variables. More specifically, it quantifies the "amount of information" (in units such as shannons (bits), nats or hartleys) obtained about one random variable by observing the other random variable. The concept of mutual information is intimately linked to that of entropy of a random variable, a fundamental notion in information theory that quantifies the expected "amount of information" held in a random variable.

Kullback–Leibler divergence

In mathematical statistics, the Kullback–Leibler divergence (also called relative entropy and I-divergence), denoted , is a type of statistical distance: a measure of how one probability distribution P is different from a second, reference probability distribution Q. A simple interpretation of the KL divergence of P from Q is the expected excess surprise from using Q as a model when the actual distribution is P.

Information theory

Information theory is the mathematical study of the quantification, storage, and communication of information. The field was originally established by the works of Harry Nyquist and Ralph Hartley, in the 1920s, and Claude Shannon in the 1940s. The field, in applied mathematics, is at the intersection of probability theory, statistics, computer science, statistical mechanics, information engineering, and electrical engineering. A key measure in information theory is entropy.

Decision tree learning

Decision tree learning is a supervised learning approach used in statistics, data mining and machine learning. In this formalism, a classification or regression decision tree is used as a predictive model to draw conclusions about a set of observations. Tree models where the target variable can take a discrete set of values are called classification trees; in these tree structures, leaves represent class labels and branches represent conjunctions of features that lead to those class labels.

Related lectures (57)

Supervised Learning: Decision Trees

Covers supervised learning with decision trees and feature selection for classification.

Interpretation of Entropy

Explores the concept of entropy expressed in bits and its relation to probability distributions, focusing on information gain and loss in various scenarios.

Decision Trees: Overfitting and Randomization

Explores decision trees, overfitting, and randomization in supervised learning, emphasizing the importance of managing variance and feature selection.

Variational Formulation: Information Measures

Explores variational formulation for measuring information content and divergence between probability distributions.

Information Measures