程序代写 - PowCoder代写

Classification
DTU Electrical Engineering

• What is Classification?
• Dimensionality Reduction – PCA
– Face detection
• Classifiers
– k-Nearest Neighbors
– Support Vector Machines
• Class/Category Recognition • Summary
DTU Electrical Engineering

What is Classification?
DTU Electrical Engineering

A taxonomy of ML algorithms
Machine Learning
Unsupervised Learning
Clustering
Supervised Learning
Reinforcement Learning
Regression
• Supervised Learning – The target values are known – Regression – The target value is numeric
– Classification – The target value is nominal
• Unsupervised Learning – The target values are unknown – Clustering – Group together similar instances
Classification
• Reinforcement Learning – Interacting with a dynamic environment the system must perform a certain goal.
DTU Electrical Engineering

Classification
Machine Learning
Supervised Learning
Classification
• Supervised Learning – The target values are known – Classification – The target value is nominal
DTU Electrical Engineering

Classification
• Some terminology:
– Concept: The description of the dataset. What can be learned by the examined dataset (e.g. the labels)
– Instances: Individual and independent examples of the concept (e.g. an image) – Attributes: The features/dimensions that describe each instance.
DTU Electrical Engineering

What is Classification?
• The final output of a classification algorithm is usually decision boundaries that separate the classes.
• So, the examined concept is classified according to which boundary side it is found on.
DTU Electrical Engineering

Image classification pipeline
• Our input is a training dataset that consists of N images, each labeled with one of K different classes.
• Then, we use this training set to train a classifier to learn what every one of the classes looks like.
• In the end, we evaluate the quality of the classifier by asking it to predict labels for a new set of images that it’s never seen before. We’ll then compare the true labels of these images to the ones predicted by the classifier.
DTU Electrical Engineering

Dimensionality Reduction
• When each concept is described by a large number of attributes, we say that the concept is described by a vector with large dimensionality.
• Generally, large dimensional vectors are well suited for machine learning.
• However,
– some of the attributes may be redundant, i.e, attributes with small variance.
– having many dimensions, might lead to the curse of dimensionality (data sparsity).
• Solution :
– Reduce the dimensionality of the problem to boost speed and performance.
DTU Electrical Engineering

Dimensionality Reduction • Principal Component Analysis (PCA)
DTU Electrical Engineering

Dimensionality Reduction • Principal Component Analysis (PCA)
• A solution for dealing with/reducing high dimensionality.
• Characteristics
– Creates new features that are linear combinations of the original features
– New features are orthogonal to each other
– Keep the new features that account for a large amount of the variance in the original dataset
– Re-base the dataset’s coordinate system in a new space defined by its lines of greatest variance
DTU Electrical Engineering

Dimensionality Reduction • Principal Component Analysis (PCA)
1. Center the input data
2. Calculate Covariance Matrix
3. Compute eigenvectors & eigenvalues of the Covariance Matrix
• The first principal component is the eigenvector of the covariance matrix that has the largest eigenvalue
» This vector points towards the direction of the largest variance of the data
» The corresponding eigenvalue defines the magnitude of this vector
• The second largest eigenvector is orthogonal to the largest eigenvector, and points into the direction of the second largest spread of the data.
4. Sort the eigenvectors according to their eigenvalues
5. Calculate the variance score (significance).
6. Keep eigenvectors that explain most (e.g. 95%) variance / remove the rest! (ß dimensionality reduction)
7. Project instances to eigenvectors y.
DTU Electrical Engineering

Dimensionality Reduction
• Principal Component Analysis (PCA)
• A solution for dealing with/reducing high dimensionality.
• Eigenvector: points to the direction of variance.
• Eigenvalues: shows how much of the total variance is explained by the corresponding eigenvector. • Keep the eigenvectors that explain most (e.g. 95%) of the variance.
1st Principal Component
2nd Principal Component
DTU Electrical Engineering
figure from:

Dimensionality Reduction
• Principal Component Analysis (PCA)
• A solution for dealing with/reducing high dimensionality.
• Eigenvector: points to the direction of variance.
• Eigenvalues: shows how much of the total variance is explained by the corresponding eigenvector. • Keep the eigenvectors that explain most (e.g. 95%) of the variance.
ßWhat are the Principal Components here?
DTU Electrical Engineering
figure from:

Eigenfaces
• Face Recognition
• Consider many images of faces (each image with the same dimensions).
• Consider each image, not as a 2D table, but just as a very long vector!
• How many dimensions does such a vector have?
• We want to construct a low-dimensional linear subspace that best explains the variation in our set of face images.
• Most face images lie on a low-dimensional subspace determined by the first some(!) directions of maximum variance.
• Use PCA to find the vectors(eigenfaces) that determine this subspace
• Then, all face images can be expressed as linear combinations of the eigenfaces
M. Turk and A. Pentland, 1991. Eigenfaces for Recognition, Journal of Cognitive Neuroscience, 3(1), 71-86.
DTU Electrical Engineering

Eigenfaces
Large dataset of face images Mean Image The first 64 eigenvectors (eigenfaces)
DTU Electrical Engineering

Eigenfaces
• Then an image of our dataset becomes:
Image = Mean Image + c1*(1st Eigenface) + c2*(2nd Eigenface) + …
• So, these coefficients c1, c2, … c64 represent the face image!!
• We can perform Face Recognition – For a new face image
– We can calculate its 64 coefficients
– Find the closest training face (most similar coefficients) in the 64-dimensional space (the most similar face of my training dataset)
– Classify the new face as this most similar training face.
DTU Electrical Engineering

k-Nearest Neighbors (k-NN)
k-NN is a geometric method for classification.
• Itisbasedontheassumptionthatneighborinstancesbelongtothesameclass.
For classifying a new instance x* :
• wecalculateitsdistancefromalltheotherinstances. • Thenweselectthek-nearestinstances.
• Theprobabilityoftheclassisgivenby:
where kj is the number of nearest neighbors that belong to class j, and K is the total number of nearest neighbors.
DTU Electrical Engineering

k-Nearest Neighbors (k-NN)
What is the class of the black dot?
The black dot belongs to the “red” class with probability 4/5
DTU Electrical Engineering

k-Nearest Neighbors (k-NN)
The parameters of k-NN are:
• the number of nearest neighbors k
• the distance metric that would be used.
• Most common distance metric is Euclidean — other possibilities are: Mahalanobis, Manhattan etc.
DTU Electrical Engineering

k-Nearest Neighbors (k-NN)
Characteristics of k-NN:
• Very small numbers of k do not perform well on noisy data. • k-NN is a non-linear classifier.
• Despite its simplicity is powerful.
• Can be very slow for large datasets.
DTU Electrical Engineering

Support Vector Machines (SVMs)
• SVMs are geometric methods for classification
• Find a line/surface in feature space that separates the classes
• Linear Classifier: (here, a 2D example)
Which line is best?
DTU Electrical Engineering

Support Vector Machines (SVMs)
• Lines in 2D
DTU Electrical Engineering

Support Vector Machines (SVMs)
• SVMs are geometric methods for classification
• They derive a linear decision boundary which satisfies two criteria:
1. The distance between the instances and the boundary is as large as possible (max margin).
2. The instances are classified as good as possible.
• Thus, the decision boundary is a hyperplane h(x) defined as: …the goal is to find the w that satisfy the above criteria.
DTU Electrical Engineering

Support Vector Machines (SVMs)
• SVMs are geometric methods for classification
• They derive a linear decision boundary which satisfies two criteria:
1. The distance between the instances and the boundary is as large as possible (max margin).
2. The instances are classified as good as possible.
It is only these 3 points that define our separation boundary!
These 3 points are called: Support Vectors
DTU Electrical Engineering

Support Vector Machines (SVMs)
• Maximize the margin while correctly classifying all training data points
• The goal is to find the w that satisfies the criteria of: • The classification rule is expressed as:
• The sign function is defined as:
• Thus, a new instance is labeled with 1 if it is located above the boundary and with -1 otherwise.
DTU Electrical Engineering

Support Vector Machines (SVMs)
• Extending SVMs!
– Moving beyond 2D
– There might be more
than 2 classes
– Data might not be linearly separable
DTU Electrical Engineering

Support Vector Machines (SVMs)
• Extending SVMs!
– Moving beyond 2D – There might be more
than 2 classes
– Data might not be linearly separable
• Our math work just fine for more than 2 dimensions! – Instead of lines, we get planes/hyperplanes…
DTU Electrical Engineering

Support Vector Machines (SVMs)
• Extending SVMs!
– Moving beyond 2D
– There might be more
than 2 classes
– Data might not be linearly separable
• Multi-class SVMs
– Possible solutions:
• 1-vs-all
» Combine multiple binary classifiers.
» Choose the one with the largest decision value
» Train one classifier for each pair of classes
» Choose the class that most classifiers vote for
DTU Electrical Engineering

Support Vector Machines (SVMs)
• Extending SVMs!
– Moving beyond 2D
– There might be more
than 2 classes
– Data might not be linearly separable
• The kernel trick
– We can use kernels (functions)
• We are moving our problem in a higher- (or even infinite-) dimensional space.
• In this new space our problem is linearly separable!
– Typical kernels:
• Polynomial
• Gaussian (Radial Basis Function – RBF)
DTU Electrical Engineering

Class/Category Recognition • Bag of Words
DTU Electrical Engineering
Image from: Fei-Fei Li

Class/Category Recognition
• Bag of Words
– Feature Detection
– Feature Extraction/Description (e.g. SIFT, …)
– Codebook/Vocabulary Generation
– Image description:
• Histogram Computation
• a bag of visual words is a vector of occurrence counts of a vocabulary of local image features.
– Classification of new image in the descriptor’s space
DTU Electrical Engineering

Class/Category Recognition
• Bag of Words
– Feature Detection
– Feature Extraction/Description (e.g. SIFT, …) – Codebook/Vocabulary Generation
– Image description:
• Histogram Computation
• a bag of visual words is a vector of occurrence counts of a vocabulary of local image features.
DTU Electrical Engineering
Image from:

Class/Category Recognition
• Bag of Words
– Feature Detection
– Feature Extraction/Description (e.g. SIFT, …)
– Codebook/Vocabulary Generation
– Image description:
• Histogram Computation
• a bag of visual words is a vector of occurrence
counts of a vocabulary of local image features.
– Classification of new image in the descriptor’s space
DTU Electrical Engineering
Image from: Fei-Fei Li

• Machine Learning techniques can find the best label for a new instance, based on known labeled training instances.
• We might
– know what we are looking foràobject detection
– have a specific rigid object we are trying to recognize à instance recognition
– want to recognize instances of extremely varied classes (e.g. animals or furniture) à category/class recognition
“Woven into all of these techniques is the topic of learning, since hand-crafting specific object recognizers seems like a futile approach given the complexity of the problem.”
R. Szelinski, “Computer Vision: Algorithms and Applications”, 2010.
DTU Electrical Engineering Source: https://en.wikipedia.org/wiki/Otsu%27s_method

• Latest methods rely on deep neural networks. – Object Detection in images:
» J. Redmon, S. Divvala, R. Girshick and A. Farhadi, “You Only Look Once: Unified, Real-Time Object Detection,” 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Las Vegas, NV, 2016, pp. 779-788.
» https://arxiv.org/abs/1506.02640 • Faster R-CNN
» S. Ren, K. He, R. Girshick and J. Sun, “Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 39, no. 6, pp. 1137-1149, 1 June 2017.
» https://arxiv.org/abs/1506.01497 – Classification in 3D point clouds
• PointNet
» R. Q. Charles, H. Su, M. Kaichun and L. J. Guibas, “PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation,” 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Honolulu, HI, 2017, pp. 77-85.
» https://arxiv.org/abs/1612.00593
DTU Electrical Engineering Source: https://en.wikipedia.org/wiki/Otsu%27s_method

Classification
DTU Electrical Engineering

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts