Ensemble Methods in Machine Learning

Tree-Based Methods

• Tree-based methods are useful for their interpretability.
• However, they are not always the most accurate compared to other supervised learning approaches.

Decision Tree Algorithm

• Used for solving both regression and classification problems.
• Aims to create a training model to predict the value of the target variable by learning simple decision rules.
• Data (training data) is used to infer these decision rules.
• Prediction begins at the root of the tree.
• The record's attribute is compared to the root attribute.
• Based on the comparison, the corresponding branch is followed.
• The process moves to the next node.

Terminology Related to Decision Trees

• Root Node: Represents the entire population that branches into two or more homogeneous sets.
• Splitting: Process of dividing a node into two or more sub-nodes.
• Decision Node: A sub-node that further splits into sub-nodes.
• Leaf/Terminal Node: A node that does not split.
• Pruning: Removing sub-nodes from a decision node (opposite of splitting).
• Branch/Sub-Tree: A subsection of the entire tree.
• Parent and Child Node: A node that branches is the parent node of its sub-nodes and its sub-nodes are the child nodes.

How do Decision Trees Work?

• The decision criteria for splitting nodes affect accuracy.
• Decision trees use various algorithms for splitting a node into multiple sub-nodes, improving the homogeneity of the resultant sub-nodes (more purity of the split).
• The algorithm selection depends on the target variable type.

Steps in ID3 Algorithm

• Starts with the original dataset (S) as the root node.
• Iterates through unused attributes of dataset (S).
• Calculates the Entropy(H) and Information gain (IG) of each attribute.
• Selects the attribute with the lowest Entropy or highest Information gain.
• Splits data(S) based on the selected attribute to create subsets.
• Recursively repeats the process on each subset using only never-selected attributes.

Attribute Selection Measures

• Deciding which attribute to place at the root or at various levels is crucial to accuracy.
• Common criteria for attribute selection: Entropy, Information Gain, Gini index, Gain Ratio, Reduction in Variance, and Chi-Square.
• Attribute values are sorted and attributes are placed in the tree based on the criteria (highest value at root).
• Categorical or continuous attributes are assumed depending on the criteria.

Entropy

• Measures randomness of information.
• Higher entropy, harder to draw conclusions from the information.
• Coin flip provides random information.

Information Gain

• A statistical property to assess how well an attribute separates training samples into categories.
• Decision tree algorithms aim to find attributes that yield the highest information gain to minimize entropy.
• Mathematically expressed as: 'Information Gain = Entropy (before) - Entropy (after split)'

Gini Index

• A cost function for evaluating splits in the dataset.
• Favors larger partitions and is readily implemented.
• Calculated by subtracting the sum of the squared probabilities of each class from one.

Gain Ratio

• An improvement over Information Gain.
• Corrects Information Gain by considering the intrinsic information of a split.
• Favors attributes with a smaller number of distinct values.

Reduction in Variance

• Algorithm for continuous target variables.
• Splits population based on a split with lower variance.
• Standard variance formula is used to determine the best split.

Chi-Square

• An older method for classification trees.
• Used to find the statistical significance of differences through comparing sub-nodes with parent nodes.
• Uses the sum of squared standardized differences to determine statistical significance.
• Works well with categorical variables like "Success" or "Failure".

Pros & Cons of Tree-based Methods

• Simple and useful for interpretation.
• Less competitive with other supervised learning algorithms regarding prediction accuracy.

How to Avoid Overfitting in Decision Trees

• Pruning: Trim branches to prevent overfitting by segregating actual training data and validation data, then preparing decision trees using only training data.
• Random Forest: Growing multiple uncorrelated trees to reduce overfitting.

Ensemble Classifiers

• Bagging: Creating multiple datasets of the training data through sampling with replacement to reduce variance in the training dataset. Then these individual models make predictions, and the majority vote or average is taken as the final prediction.
• Boosting: Iteratively improving models with each iteration to compensate for errors of the previous models. Data samples are given a specific weight. Models are learned in a sequential manner.
• Stacking: Combines multiple Models in parallel, then uses a Meta model to combine the predictions into a final prediction.

Random Forest

• An extension of bagging to create diverse decision trees.
• Feature randomness is used to ensure low correlation between decision trees.
• Considers a subset of features at each split.

Classification in Random Forest

• An ensemble method achieving prediction via decision trees.
• Each decision tree provides a prediction.
• The final prediction is determined by the output from the majority of the decision trees.

Disadvantages of Random Forest

• Training time and space increase as more trees are used.
• Higher number of trees results in very little improvement in accuracy, thereby making it difficult to decide on the ideal number of trees.
• Sensitive to parameters, noise, and environmental changes.

Boosting

• Ensemble learning method combining weak learners to minimize training errors.
• Models are trained sequentially, with each trying to compensate for the weaknesses of its predecessor.
• Models are combined to form an overall, stronger prediction rule.

Types of Boosting

• Adaptive Boosting (AdaBoost): Weights are assigned to data points to focus on misclassified data.
• Gradient Boosting: Uses gradient descent and corrects for errors by subsequent models.
• Extreme Gradient Boosting (XGBoost): Designed for speed and scale, leveraging multiple cores for parallel training.
• LightGBM: High efficiency and scalability.
• CatBoost: Particularly good for categorical data, avoids extensive data preprocessing.
• Stochastic Gradient Boosting: Introduces randomness by subsampling the data in each iteration.

Benefits of Boosting

• Easier to implement.
• Reduces bias in models.
• Computationally more efficient by selecting features that increase predictive power.

Challenges of Boosting

• Overfitting can potentially occur.
• Computationally intensive, especially for very complex models.
• Intense computation for sequential training.

Applications of Boosting

• Healthcare: Predictions on survival or risk factors.
• Information technology: Improve accuracy of network intrusion detection systems.
• Environment: Models to identify types of wetlands.
• Finance: Fraud detection, pricing analysis, etc.

Bagging vs. Boosting

• Bagging: Parallel training of multiple similar models, with averaging outputs.
• Boosting: Sequential training of increasingly complex models, by adjusting weights based on prior predictions to compensate for errors and improve results over time.

Stacking

• Combines predictions outputs from multiple models.
• Leverages a Meta model to combine outputs for overall prediction.

The No Free Lunch Theorem

• The best algorithm depends on the dataset and the task.
• Different algorithms may provide superior performance in different scenarios.

Uncertainties in Supervised Learning

• Models do not always accurately reflect the actual distribution.
• Data characteristics and distributions may drift or change over time.

Difference Between Error and Uncertainty

• Error: Difference between predictions and actual observations.
• Uncertainty: Sources that create potential variety of possible data models (data, model selection, parameterization, inference, decisions).

This quiz focuses on the fundamental concepts of ensemble classifiers, including techniques such as bagging and boosting. It covers the mechanisms behind decision tree pruning, the role of validation datasets, and the advantages of popular algorithms like AdaBoost and XGBoost. Test your understanding of how these methods enhance classifier accuracy and effectiveness in various contexts.