Pattern Recognition Lecture 5: Classification III
9 Questions
5 Views
3.4 Stars

Pattern Recognition Lecture 5: Classification III

This quiz covers the concepts of multi-class classification, decision trees, and Support Vector Machines (SVM) in pattern recognition. It includes topics such as learning a decision tree, feature selection criteria, and achieving multi-class classification by combining binary classifiers.

Created by
@CoherentTechnetium

Questions and Answers

What is the complexity of the decision tree learning problem?

NP-hard

What is the primary goal of decision tree learning?

Find the tree with the lowest classification error

What is the range of the classification error metric?

0.0 to 1.0

What is the first step in the simple greedy algorithm for decision tree learning?

<p>Start with an empty tree</p> Signup and view all the answers

What is the purpose of the recursion step in the greedy decision tree learning algorithm?

<p>To continue splitting the data until a stopping condition is reached</p> Signup and view all the answers

What are the two main problems in greedy decision tree learning?

<p>Feature selection and stopping condition</p> Signup and view all the answers

What is the name of the machine learning specialization course credited in the text?

<p>Credit for Machine Learning Specialization</p> Signup and view all the answers

What is the number of observations (xi,yi) in the training data?

<p>40</p> Signup and view all the answers

What is the name of the university associated with Andrew Ng's machine learning course?

<p>University of Stanford</p> Signup and view all the answers

Study Notes

Classification III

  • Multi-class classification can be achieved by combining a number of binary classifiers
  • Two common approaches to multi-class SVMs: One vs. all and One vs. one

One vs. All

  • Train an SVM for each class vs. the rest
  • Testing: apply each SVM to test example and assign to it the class of the SVM that returns the highest decision value
  • Advantages: number of binary classifiers equals the number of classes
  • Disadvantages: during training, training sample sizes are unbalanced

One vs. One

  • Train an SVM for each pair of classes
  • Testing: each learned SVM “votes” for a class to assign to the test example
  • Advantages: training data required for each class is balanced
  • Disadvantages: number of classifiers are n(n-1)/2, so they increase as the number of classes increase (higher computational cost)

SVMs: Pros and Cons

  • Pros: many publicly available SVM packages, kernel-based framework is very powerful and flexible, work well in practice, even with very small training sample sizes
  • Cons: no “direct” multi-class SVM, must combine two-class SVMs, can be tricky to select best kernel function for a problem, computational and memory issues during training time

Logistic Regression vs. SVMs

  • If number of features is large (relative to number of training examples), use logistic regression, or SVM without a kernel (“linear kernel”)
  • If number of features is small, and number of training examples is intermediate, use SVM with Gaussian kernel
  • If number of features is small, and number of training examples is large, create/add more features, then use logistic regression or SVM without a kernel

Decision Trees

  • Intuition: what makes a loan risky? (credit history, income, loan terms, personal information)
  • Decision tree learning task: learn decision tree from data, find the best tree that represents the data
  • Problem: exponentially large number of possible trees makes decision tree learning hard (NP-hard problem)

Decision Tree Learning

  • Training data: N observations (xi, yi)
  • Quality metric: classification error, error measures fraction of mistakes, best possible value: 0.0, worst possible value: 1.0
  • Find the tree with lowest classification error

Simple Greedy Algorithm Decision Tree Learning

  • Step 1: Start with an empty tree, start with the data
  • Step 2: Select a feature to split data, split on a feature
  • Step 3: Making predictions, if nothing more to do, make predictions
  • Step 4: Recursion, otherwise, go to Step 2 & continue (recurse) on this split

Problems in Decision Tree Learning

  • Problem 1: Feature split selection
  • Problem 2: Stopping condition

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Quiz Team
Use Quizgecko on...
Browser
Browser