Machine Learning Decision Trees Quiz

Introduction to Machine Learning

• Advanced Topics in Computer Systems and Networks
• Introduction to Machine Learning covered in course

Contents

• Definition of machine learning
• Basic concepts and terms
• Types of machine learning algorithms
  • Supervised learning
    • Classification
    • Regression
  • Unsupervised learning
    • Clustering
  • Reinforcement learning

Definition of Machine Learning

• Machine learning is the study that gives computers the ability to learn without explicit programming
• It aims to make computers more similar to humans in their ability to learn

Machine Learning Algorithms (1)

• Machine learning is the study of learning algorithms
• A computer program learns from experience E with respect to a class of tasks T and performance measure P if its performance at tasks in T improves with experience E
• This involves data, learning algorithm(task) and understanding performance

Machine Learning Algorithms (2)

• Learning involves experience, induction of a law, prediction of future, and finally using a model for predictions on new data to find unknown attributes
• This includes historical data, training and prediction

Basic Concepts and Terms (1)

• Dataset: collection of data
• Training set: data used for training a machine learning model
• Test set: data used to evaluate a machine learning model

Basic Concepts and Terms (2)

• Terms
  • P: positive examples
  • N: negative examples
  • TP: true positive
  • TN: true negative
  • FP: false positive
  • FN: false negative
  • Confusion matrix: table to evaluate model accuracy

Basic Concepts and Terms (3)

• Measure and Formula
  • Accuracy: (TP + TN) / (P + N)
  • Error rate: (FP + FN) / (P + N)
  • Sensitivity/Recall: TP / P
  • Specificity: TN / N
  • Precision: TP / (TP + FP)
  • F-score: harmonic mean of precision and recall
  • Fβ (β is non-negative real number)

Basic Concepts and Terms: Example

• Trained model to identify cats in images
• Precision: TP / (TP + FP) = 87.5%
• Recall: TP / P = 93.3%
• Accuracy: (TP + TN) / (P + N) = 85%

Types of Machine Learning Algorithms (1)

• Supervised learning
• Unsupervised learning
• Semi-supervised learning
• Reinforcement learning

Types of Machine Learning Algorithms (2)

• Machine learning algorithms can be classified as supervised, unsupervised, and reinforcement learning methods
• Supervised learning: classification, regression
• Unsupervised learning: clustering, association analysis, dimensionality reduction
• Reinforcement learning: model-free, model-based

Types of Machine Learning Algorithms (2)

• Shows subcategories of machine learning algorithms: supervised, unsupervised and reinforcement
• Show details about the algorithms like K-means, PCA, SVD, LDA, DBSCAN etc

Supervised Learning Algorithms

• Classification: (Logistic Regression, Naive Bayes, K-Nearest Neighbor, Support Vector Machine)
• Regression: (Linear Regression, Ridge Regression, Ordinary Least Squares, Stepwise Regression)

Classification: Decision Trees (1)

• Decision trees use Gini Index and Entropy to decide criteria
• Gini Index
  • Measures the probability of misclassifying a randomly chosen element from the set
• Entropy measures the impurity of the data

Classification: Decision Trees (2)

• Decision trees find the best feature with descriptive features that split data, improving purity of groups
• Leaf nodes store predictions for new data

Classification: Building a Decision Tree Model (1)

• Shows visual representation of a Decision Tree model

Classification: Building a Decision Tree Model (2)

• Shows flow diagram of data processing in a decision tree

Classification: Building a Decision Tree Model (3)

• Decision tree model process is given with example

Classification: Decision Trees Example (1)

• Example dataset related to weather data and play to illustrate decision tree usage

Classification: Decision Trees Example (2)

• Details the calculation of Gini impurity and Entropy

Classification: Exploiting a Decision Tree Learning Model

• Estimating Class Probabilities
• A decision tree finds the leaf node for an instance and returns the ratio of training instances in the node

Classification: Exploiting a Decision Tree Learning Model (continued)

• Best algorithms are ID3, C4.5, CART for training and evaluation

Classification: Naïve Bayes Classifier

• Bayesian classifiers use Bayes' theorem to classify objects, assuming attributes are independent
• This creates predictive probabilities

Classification: Naïve Bayes (Bayes' Theorem)

• Relationship between P(B|A) and P(A|B) expressed through Bayes' theorem

Classification: Naïve Bayes (Bayes' Theorem for classification)

• Given input features, use Bayes' theorem for classification by finding a class that maximizes probability

Classification: Naïve Bayes (Bayes' Theorem for classification) (cont)

• Training Naïve Bayes involves estimating probabilities

Classification: Naïve Bayes Classifier (cont)

• Fast and reliable for text and attribute-independent problems, also good when attributes >> number of instances

Unsupervised Algorithms: Clustering

• Identifying groups of similar items within a dataset
• Key concepts include intra-cluster similarity, and inter-cluster dissimilarity

Unsupervised Algorithms: Clustering (cont)

• Types include K-Means, K-Median, Hierarchical clustering, DBScan, Expectation Maximization

Unsupervised Algorithms: Clustering Evaluation

• Cluster quality measures include manual review, benchmarks for existing labels, and distance measures (high within, low across clusters)

Unsupervised Algorithms: Clustering (Distance functions)

• Simplest case: one numeric attribute (A) - Distance (X,Y) = A(X) – A(Y)
• Multiple numeric attributes: - Distance(X,Y) - Euclidean
• Attributes may have differing importance, and weighting may be necessary

Unsupervised Algorithms: Clustering (Algorithm K-Means)

• Partitions observations into 'k' clusters, with each observation belonging to the cluster with the nearest mean
• Shows diagrammatic visualization

Unsupervised Algorithms: Clustering (K-Means: Cluster Center)

• Objective is to minimize the average squared Euclidean distance of values from their cluster centers.
• Cluster centers (means) represent the mean value for a cluster

Unsupervised Algorithms: Clustering (K-Means Clustering)

• Explains the stepwise algorithm of K-Means Clustering

Unsupervised Algorithms: Clustering (K-means Clustering) (steps)

• Initializing K cluster seeds
• Measuring distances to clusters
• Assigning objects to clusters
• Calculating new centroid for each cluster
• Iteration

Unsupervised Algorithms: Clustering (K-means Issues)

• Distance measure is squared Euclidean, scale should be similar across dimensions
• Not suitable for nominal data
• Approach tries to minimize within-cluster sum of squares error (WCSS)

WCSS (Within-Cluster Sum of Squares)

• Overall WCSS is given by Σ(xi−μi)²
• Finding the smallest WCSS is a goal in K-means

Reinforcement Learning

• Deals with sequential decision-making.
• The goal is to maximize the cumulative reward over time

Reinforcement Learning Algorithms

• Types include model-free (Q-learning, hybrid, policy optimization) and model-based

Reinforcement Algorithms: Q-Learning

• Input: states, actions, output: final state
• Algorithm pseudocode is presented
• Concepts of agents, states, actions, rewards, and episodes

Reinforcement Algorithms: Q-Learning (cont)

• Methods for determining Q-values explained (temporal difference and Bellman's equation)

Reinforcement Algorithms: Q-Learning (Bellman's Equation)

• The Bellman Equation is given
• States the equation in terms of Q-values, reward function, discount factor, and maximum Q-value