本章首先介绍了分类在计算机视觉图像处理的作用,包括部分或对象检测、场景分类、行为识别、情感识别、地区分类、边界分类等方面。其次本章介绍机器学习的概述:无监督学习包括降维、聚类;监督式学习包括分类、回归。聚类方法介绍了包括K-means、Agglomerative聚类、Mean-shift聚类、Spectral聚类等。以及多种分类器的介绍。

注脚

展开查看详情

1.Machine Learning Crash Course Computer Vision Jia-Bin Huang, Virginia Tech Many slides from D. Hoiem, J. Hays

2.Administrative stuffs HW 4 Due 11:59pm on Wed, November 2 nd

3.What is a category? Why would we want to put an image in one? Many different ways to categorize To predict, describe, interact. To organize.

4.Examples of Categorization in Vision Part or object detection E.g., for each window: face or non-face? Scene categorization Indoor vs. outdoor, urban, forest, kitchen, etc. Action recognition Picking up vs. sitting down vs. standing … Emotion recognition Region classification Label pixels into different object/surface categories Boundary classification Boundary vs. non-boundary Etc , etc.

5.Image Categorization Training Labels Training Images Classifier Training Training Image Features Trained Classifier

6.Image Categorization Training Labels Training Images Classifier Training Training Image Features Image Features Testing Test Image Trained Classifier Trained Classifier Outdoor Prediction

7.Feature design is paramount Most features can be thought of as templates, histograms (counts), or combinations Think about the right features for the problem Coverage Concision Directness

8.Today’s class: Machine Learning Machine learning overview U nsupervised Learning Dimensionality reduction Clustering Supervised Learning Classification Regression

9.

10.“ If you were a current computer science student what area would you start studying heavily ?” Answer: Machine Learning. “ The ultimate is computers that learn” Bill Gates, Reddit AMA “Machine learning is the next Internet” Tony Tether, Director, DARPA “Machine learning is today’s discontinuity” Jerry Yang, CEO, Yahoo (C) Dhruv Batra 10 Slide Credit: Pedro Domingos , Tom Mitchel, Tom Dietterich

11.(C) Dhruv Batra 11

12.Machine Learning: Making predictions or decisions from Data

13.Resources Disclaimer: This overview will not cover statistical underpinnings of learning methods. We’ve looking at ML as a tool. ML related courses at Virginia Tech ECE 5424 / 4424 - CS 5824 / 4824 Introduction to Machine Learning CS 4804 Introduction to Artificial Intelligence ECE 6504 Neural Networks and Deep Learning External courses Machine Learning by Andrew Ng https:// www.coursera.org/learn/machine-learning Learning from Data by Yaser S. Abu-Mostafa https:// www.edx.org/course/learning-data-introductory-machine-caltechx-cs1156x

14.Impact of Machine Learning Machine Learning is arguably the greatest export from computing to other scientific fields.

15.Machine Learning Applications Slide: Isabelle Guyon

16.Machine Learning Applications Slide: Isabelle Guyon

17.Machine Learning Applications Slide: Isabelle Guyon

18.Eigenfaces example Top eigenvectors: u 1 ,…u k Mean: μ

19.Eigenfaces example Top eigenvectors: u 1 ,…u k Mean: μ

20.Clustering Clustering: group together similar points and represent them with a single token Key Challenges: What makes two points/images/patches similar? How do we compute an overall grouping from pairwise similarities? Slide: Derek Hoiem

21.Why do we cluster? Summarizing data Look at large amounts of data Patch-based compression or denoising Represent a large continuous vector with the cluster number Counting Histograms of texture, color, SIFT vectors Segmentation Separate the image into different regions Prediction Images in the same cluster may have the same labels Slide: Derek Hoiem

22.How do we cluster? K-means Iteratively re-assign points to the nearest cluster center Agglomerative clustering Start with each point as its own cluster and iteratively merge the closest clusters Mean-shift clustering Estimate modes of pdf Spectral clustering Split the nodes in a graph based on assigned links with similarity weights Slide: Derek Hoiem

23.How do we cluster? K-means Iteratively re-assign points to the nearest cluster center Agglomerative clustering Start with each point as its own cluster and iteratively merge the closest clusters Mean-shift clustering Estimate modes of pdf Spectral clustering Split the nodes in a graph based on assigned links with similarity weights Slide: Derek Hoiem

24.The machine learning framework Apply a prediction function to a feature representation of the image to get the desired output: f( ) = “apple” f( ) = “tomato” f( ) = “cow” Slide credit: L. Lazebnik

25.The machine learning framework y = f( x ) Training: given a training set of labeled examples {( x 1 ,y 1 ), …, ( x N ,y N )} , estimate the prediction function f by minimizing the prediction error on the training set Testing: apply f to a never before seen test example x and output the predicted value y = f( x ) output prediction function Image feature Slide credit: L. Lazebnik

26.Classifier A classifier maps from the feature space to a label x x x x x x x x o o o o o x2 x1

27.Different types of classification Exemplar-based : transfer category labels from examples with most similar features What similarity function? What parameters? Linear classifier : confidence in positive label is a weighted sum of features What are the weights? Non-linear classifier : predictions based on more complex function of features What form does the classifier take? Parameters? Generative classifier : assign to the label that best explains the features (makes features most likely) What is the probability function and its parameters? Note: You can always fully design the classifier by hand, but usually this is too difficult. Typical solution: learn from training examples.

28.One way to think about it… Training labels dictate that two examples are the same or different, in some sense Features and distance measures define visual similarity Goal of training is to learn feature weights or distance measures so that visual similarity predicts label similarity We want the simplest function that is confidently correct

29.Exemplar-based Models Transfer the label(s) of the most similar training examples

30.K-nearest neighbor classifier x x x x x x x x o o o o o o o x2 x1 + +

31.1-nearest neighbor x x x x x x x x o o o o o o o x2 x1 + +

32.3-nearest neighbor x x x x x x x x o o o o o o o x2 x1 + +

33.5-nearest neighbor x x x x x x x x o o o o o o o x2 x1 + +

34.K-nearest neighbor x x x x x x x x o o o o o o o x2 x1 + +

35.Using K-NN Simple, a good one to try first Higher K gives smoother functions No training time (unless you want to learn a distance function) With infinite examples, 1-NN provably has error that is at most twice Bayes optimal error

36.Discriminative classifiers Learn a simple function of the input features that confidently predicts the true labels on the training set Training Goals Accurate classification of training data Correct classifications are confident Classification function is simple  

37.Classifiers: Logistic Regression Objective Parameterization Regularization Training Inference x x x x x x x x o o o o o x2 x1 The objective function of most discriminative classifiers includes a loss term and a regularization term .

38.Using Logistic Regression Quick, simple classifier (good one to try first) Use L2 or L1 regularization L1 does feature selection and is robust to irrelevant features but slower to train

39.Classifiers: Linear SVM x x x x x x x x o o o o o o x2 x1

40.Classifiers: Kernelized SVM x x x x o o o x x x x x o o o x x 2

41.Using SVMs Good general purpose classifier Generalization depends on margin, so works well with many weak features No feature selection Usually requires some parameter tuning Choosing kernel Linear: fast training/testing – start here RBF: related to neural networks, nearest neighbor Chi-squared, histogram intersection: good for histograms (but slower, esp. chi-squared) Can learn a kernel function

42.Classifiers: Decision Trees x x x x x x x x o o o o o o o x2 x1

43.Ensemble Methods: Boosting figure from Friedman et al. 2000

44.Boosted Decision Trees … Gray? High in Image? Many Long Lines? Yes No No No No Yes Yes Yes Very High Vanishing Point? High in Image? Smooth? Green? Blue? Yes No No No No Yes Yes Yes Ground Vertical Sky [Collins et al. 2002] P( label | good segment , data )

45.Using Boosted Decision Trees Flexible: can deal with both continuous and categorical variables How to control bias/variance trade-off Size of trees Number of trees Boosting trees often works best with a small number of well-designed features Boosting “stubs” can give a fast classifier

46.Generative classifiers Model the joint probability of the features and the labels Allows direct control of independence assumptions Can incorporate priors Often simple to train (depending on the model) Examples Naïve Bayes Mixture of Gaussians for each class

47.Naïve Bayes Objective Parameterization Regularization Training Inference x 1 x 2 x 3 y

48.Using Naïve Bayes Simple thing to try for categorical data Very fast to train/test

49.Many classifiers to choose from SVM Neural networks Naïve Bayes Bayesian network Logistic regression Randomized Forests Boosted Decision Trees K-nearest neighbor RBMs Deep networks Etc. Which is the best one?

50.No Free Lunch Theorem

51.Generalization Theory It’s not enough to do well on the training set: we want to also make good predictions for new examples

52.Bias-Variance Trade-off E(MSE) = noise 2 + bias 2 + variance See the following for explanation of bias-variance (also Bishop’s “Neural Networks” book ): http ://www.inf.ed.ac.uk/teaching/courses/mlsc/Notes/Lecture4/BiasVariance.pdf Unavoidable error Error due to incorrect assumptions Error due to variance parameter estimates from training samples

53.Bias and Variance Many training examples Few training examples Complexity Low Bias High Variance High Bias Low Variance Test Error Error = noise 2 + bias 2 + variance

54.Choosing the trade-off Need validation set Validation set is separate from the test set Training error Test error Complexity Low Bias High Variance High Bias Low Variance Error

55.Effect of Training Size Testing Training Number of Training Examples Error Generalization Error Fixed classifier

56.How to measure complexity? VC dimension Other ways: number of parameters, etc. Training error + Upper bound on generalization error N: size of training set h: VC dimension : 1-probability that bound holds What is the VC dimension of a linear classifier for N-dimensional features? For a nearest neighbor classifier? Test error <=

57.How to reduce variance? Choose a simpler classifier Regularize the parameters Use fewer features Get more training data Which of these could actually lead to greater error?

58.Reducing Risk of Error Margins x x x x x x x x o o o o o x2 x1

59.The perfect classification algorithm Objective function: encodes the right loss for the problem Parameterization: makes assumptions that fit the problem Regularization: right level of regularization for amount of training data Training algorithm: can find parameters that maximize objective on training set Inference algorithm: can solve for objective function in evaluation

60.Comparison Naïve Bayes Logistic Regression Linear SVM Nearest Neighbor Kernelized SVM Learning Objective Training Inference Gradient ascent Quadratic programming or subgradient opt. Quadratic programming complicated to write most similar features  same label Record data assuming x in {0 1}

61.Characteristics of vision learning problems Lots of continuous features E.g., HOG template may have 1000 features Spatial pyramid may have ~15,000 features Imbalanced classes often limited positive examples, practically infinite negative examples Difficult prediction tasks

62.When a massive training set is available Relatively new phenomenon MNIST (handwritten letters) in 1990s, LabelMe in 2000s, ImageNet (object images) in 2009, … Want classifiers with low bias (high variance ok) and reasonably efficient training Very complex classifiers with simple features are often effective Random forests Deep convolutional networks

63.New training setup with moderate sized datasets Training Labels Training Images Tune CNN features and Neural Network classifier Trained Classifier Dataset similar to task with millions of labeled examples Initialize CNN Features

64.Practical tips Preparing features for linear classifiers Often helps to make zero-mean, unit- dev For non-ordinal features, convert to a set of binary features Selecting classifier meta-parameters (e.g., regularization weight) Cross-validation: split data into subsets; train on all but one subset, test on remaining; repeat holding out each subset Leave-one-out, 5-fold, etc. Most popular classifiers in vision SVM : linear for when fast training/classification is needed; performs well with lots of weak features Logistic Regression : outputs a probability; easy to train and apply Nearest neighbor : hard to beat if there is tons of data (e.g., character recognition) Boosted stumps or decision trees : applies to flexible features, incorporates feature selection, powerful classifiers Random forests : outputs probability; good for simple features, tons of data Deep networks / CNNs : flexible output; learns features; adapt existing network (which is trained with tons of data) or train new with tons of data Always try at least two types of classifiers

65.Making decisions about data 3 important design decisions: 1) What data do I use? 2) How do I represent my data (what feature)? 3) What classifier / regressor / machine learning tool do I use? These are in decreasing order of importance Deep learning addresses 2 and 3 simultaneously (and blurs the boundary between them). You can take the representation from deep learning and use it with any classifier.

66.Things to remember No free lunch: machine learning algorithms are tools Try simple classifiers first Better to have smart features and simple classifiers than simple features and smart classifiers Though with enough data, smart features can be learned Use increasingly powerful classifiers with more training data (bias-variance tradeoff)

67.Some Machine Learning References General Tom Mitchell, Machine Learning , McGraw Hill, 1997 Christopher Bishop, Neural Networks for Pattern Recognition , Oxford University Press, 1995 Adaboost Friedman, Hastie, and Tibshirani , “Additive logistic regression: a statistical view of boosting”, Annals of Statistics, 2000 SVMs http://www.support-vector.net/icml-tutorial.pdf Random forests http:// research.microsoft.com/pubs/155552/decisionForests_MSR_TR_2011_114.pdf