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. The information gain of a random variable X obtained from an observation of a random variable A taking value A=a is defined the Kullback–Leibler divergence of the prior distribution for x from the posterior distribution for x given a. The expected value of the information gain is the mutual information I(X; A) of X and A – i.e. the reduction in the entropy of X achieved by learning the state of the random variable A. In machine learning, this concept can be used to define a preferred sequence of attributes to investigate to most rapidly narrow down the state of X. Such a sequence (which depends on the outcome of the investigation of previous attributes at each stage) is called a decision tree and applied in the area of machine learning known as decision tree learning. Usually an attribute with high mutual information should be preferred to other attributes. In general terms, the expected information gain is the reduction in information entropy Η from a prior state to a state that takes some information as given: where is the conditional entropy of given the value of attribute . This is intuitively plausible when interpreting entropy Η as a measure of uncertainty of a random variable : by learning (or assuming) about , our uncertainty about is reduced (i.e. is positive), unless of course is independent of , in which case , meaning . Let T denote a set of training examples, each of the form where is the value of the attribute or feature of example and y is the corresponding class label.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (3)

Related courses (11)

Related lectures (51)

Information gain (decision tree)

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.

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.

ENG-209: Data science for engineers with Python

Ce cours est divisé en deux partie. La première partie présente le langage Python et les différences notables entre Python et C++ (utilisé dans le cours précédent ICC). La seconde partie est une intro

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 topi

EE-311: Fundamentals of machine learning

Ce cours présente une vue générale des techniques d'apprentissage automatique, passant en revue les algorithmes, le formalisme théorique et les protocoles expérimentaux.

Decision Trees and Boosting EE-311: Fundamentals of machine learning

Introduces decision trees as a method for machine learning and explains boosting techniques for combining predictors.

Building a Decision Tree MGT-448: Statistical inference and machine learning

Covers building decision trees to classify mushrooms as poisonous or not.

Decision Trees: Classification ENG-209: Data science for engineers with Python

Explores decision trees for classification, entropy, information gain, one-hot encoding, hyperparameter optimization, and random forests.