Machine Learning Foundations A Case Study Approach Week 6

Deep Learning: Searching For Images

Going to talk about on of the most exciting thing to be happening with machine learning over the last few years. It’s a new area called deep learning. In particular, going to talk about a particular use case of this area related to shopping for products just based on image similarity.

Visual Product Recommender

There are many ways to shop for products today. Typically use what’s called keyword search. Type a query on a search engine and try to find products of interest.

I Want To Buy New Shoes, But…

• Too many options online…

So for example…want to buy a pair of shoes.

• Cool black pair of shoes
• Another black pair of shoes (might look the same, but totally different style)
• Crazy dress shoe (might look transparent, but actually a really cool shade of blue)
• Crazy two colored sneaker
• Another really interesting pair of sneakers
• Purple boots

There are a lot of shoes online. It’s really hard to find the ones that are interesting, stylish, and different.

Using keyword search doesn’t really help. By typing in dress shoes, it just find a bunch of boring usual shoes. But still want to find something different, and don’t know what keywords to type or how to search for it.

Visual Production Search

There are something even more complicated than buying shoes. Want to buy a really interesting dress.

• Just use textual keyword search for dress, going to find a bunch of dresses
• But really don’t know how to choose a dress
• Don’t know how to describe it
• Even if specifying floral dress, still presented with number of options

Maybe there’s something that will catch the eye.

• Instead of finding dresses based on keyword search
• Want to use image similarity to find similar dresses
• Find dresses that look similar based on image quality
• This is much easier to find something

Features are Key to Machine Learning

Talked about an application of finding cool shoes or dresses just based on image features. The technique used is called deep learning, and in particular, it’s based on something called neural networks.

But before that, need to talk about data representation. Discussed things like tf-idf, and bag of word models. But how to really represent data when it comes to images? These are called features, and is a key part of machine learning.

Goal: Revisit Classifiers, But Using More Complex, Non-Linear Features

So typically when talking about machine learning, it is given some input. For classification, talked about sentimental analysis.

• Given a sentence
• It goes through a classifier model
• Decided if that sentence has positive or negative sentiment

Image Classification

In image classification, the goal is to go from an image, this is the input, the pixel of the images, to a classification.

Neural Networks → Learning *Very* Non-Linear Features

So as discussed, features are the representation of the data that’s used to feed into the classifier. There are many representations…

• Text
  • Bag of words
  • tf-idf
• Image
  • There’s a lot of other representations
  • Discuss a few more of those

Focus on neural networks, which provide the non-linear representation for the data.

Linear Classifier

Going back to classification for a little review.

Discussed linear classifier

• Which create this line or linear decision boundary between say the positive class and the negative class
• The boundary is stated by the Score, $w$₀ + w₁x₁ (first feature), $w$₂x₂ (second feature) so on…
  • On the positive side, the Score is greater than zero
  • On the negative side, the Score is less than zero
• Having a nice Score function, can separate the positives from the negatives

Graph Representation of Classifier: Useful For Defining Neural Networks

In neural network, classifiers are represented using graphs.

• Have a node for each feature $x$₁, $x$₂, all the way to the $dth$ feature $x$_d
• A node for output $y$, what is trying to predict
• The first feature $x$₁ is multiplied by the weight $w$₁, putting that weight on the edge
• The second feature $x$₂ is multiplied by the second weight $w$₂, going to put it on that edge
• All the way to $x$_d, which is multiplied by weight $w$_d, to put in the last edge
• The last weight, $w$₀ doesn’t get multiplied by any feature, but it gets multiplied by $1$

Imagine multiplying the weights $w$₀ through $w$_d with the features $x$₁ through $x$_d and the coefficient $1$, to get the Score.

• When the Score is greater than $0$, it is declared the output to be $1$
• When the Score is less than $0$, it is declared the output to be $0$

This is an example of a small, one layer, neural network.

Note: If the perceptron takes an input of exactly $0$, what should it output? An input of $0$ (zero) is an edge case: there is not hard and fast rule as to whether the perceptron should output $0$ or $1$. Each implementation should pick one way and output the same value for all inputs of $0$ (zero).

What Can a Linear Classifier Represent?

It was described the small linear classifiers is a neural network, a one layer neural network. What can this one layer neural network represent?

Take the function $x$₁ OR x₂

• Can it be represented using a small neural network
• Define the function a little bit more formally
• Have variable $x$₁, $x$₂, and the output $y$
• There are some possibilities…
  • When $x$₁ is $0$, and $x$₂ is $0$, the output $y$ would be $0$
  • When $x$₁ is $1$, and $x$₂ is $0$, the output $y$ would be $1$
  • When $x$₁ is $0$, and $x$₂ is $1$, the output $y$ would be $1$
  • Similarly, when they are both $1$, the output is $1$

$x$1	$x$2	y	Score
0	0	0	-0.5
1	0	1	0.5
0	1	1	0.5
1	1	1	1.5

• Define a Score function such that the value is greater than $0$ for the last three (3) rows, but it is less than $0$ for the first row
• How to do that (there are many ways of doing it actually)
  • Put a weight of $1$, one each of the edges $x$₁ and $x$₂
  • Think about the Score
  • The Score of the first row is $0$, and the Score of the other rows are greater than $0$
• Might want to add a little bit of separation, might put a negative value on the first edge ($-0.5$)
  • When $x$₁ is $0$, and $x$₂ is $0$, then the Score becomes $-0.5$
  • When $x$₁ is $1$, and $x$₂ is $0$, then the Score becomes $0.5$
  • When $x$₁ is $0$, and $x$₂ is $1$, then the Score becomes $0.5$
  • When they are both $1$, the Score is $1.5$

With this simple weights on the edges, it represents the function of $x$₁ OR x₂

Now can represent the function $x$₁ AND x₂

• Similarly can put weights $1$ and $1$ on the edges $x$₁ and $x$₂
• But in this case, only want to turn it on when both $x$₁ and $x$₂ have value $1$
• So instead of putting $-0.5$ on the top edge, put $-1.5$
• If fill out the table just like with the first example, notice that it is represent the function $x$₁ and $x$₂ using a simple neural network

What Can’t a Simple Linear Classifier Represent?

A one layer neural network is basically the same as the standard linear classifiers. So what can linear classifier not represent? It can represent $x$₁ OR x₂. It can represent $x$₁ AND x₂. But what’s a function, a very simple function it cannot represent?

Well, here is an example…

• There is no line that separate the pluses and minuses
• This function is called the XOR
• It is a counter example to (almost) everything
• Whenever a counter example is needed, first thing to try is XOR
• For this case, the linear features described are not enough and need some kind of non-linear features
• This is when the neural networks come to play for real

Solving The XOR Problem: Adding a Layer

So XOR has value $1$ either…

• Value of $x$₁ is true AND $x$₂ is false, so NOT $x$₂
• Value of $x$₁ is false AND $x$₂ is true, so NOT $x$₁

How can this be represented with a neural network?

• Call the first term $z$₁
• Call the second term $z$₂

Going to build a neural network to represent not directly the inputs of $x$₁ and $x$₂ to predict $y$. But they predict intermediate values $z$₁ and $z$₂, and then those are going to predict $y$.

Take $z$₁

• How to represent only a neural network that can predict $z$₁
• Since it have to negate, it is NOT $x$₂
  • Put a $-1$ on that edge $x$₂
  • Put a $+1$ on $x$₁
  • Put a $-0.5$ on $1$ edge
• Now have the representation for $z$₁

Similarly for $z$₂

• Put a $-1$ on edge $x$₁
• Put a $+1$ on edge $x$₂
• Put a $-0.5$ on $1$, the constant edge
• Now it represents $z$₂

The last step…

• If $z$₁ and $z$₂ exist, just have to OR them
• Already know how to OR the boolean variables
• It is just $1$ and $1$ on the $z$₁ and $z$₂ edge, and $-0.5$ on the constant edge

Now it has built out the first deep neural network, not super deep, but it has two (2) layers.

A Neural Network

• Layers and layers and layers of linear models and non-linear transformation
• Around for about 50 years
  • Fell in “disfavor” in 90s
• In last few years, big resurgence
  • Impressive accuracy on several benchmark problems
  • Powered by huge datasets, GPUs, and modeling / learning algorithm improvements

In general…

• Neural networks is about this layers and layers of transformations of the data
  • Use these transformations to create these non-linear features (more example in computer vision)
• Neural network has been around for about 50 years (about as long as machine learning’s been around)
  • However, they fell in disfavor around the 90’s
  • Because folks are having a hard time getting good accuracy in neural networks
• But everything changed about 10 years ago (because of two things that came about)
  • First, it was a lot more data
    • Because neural networks have so many, many more layers
    • So many layers that it need a lot of data to be able to train all those layers
    • They have a lot of parameters
    • Recently have came about lots and lots and lots of data from a variety of sources, especially the web
  • Second, it was computing resources
    • Because have to deal with bigger neural networks, and more data
    • Need faster computers and GPUs which were originally design for accelerating graphics for computer games
    • Turns out to be exactly the right tool to build and use neural network with lots of data
    • So because of GPUs and because of these deep neural networks, everything changed

Application of Deep Learning To Computer Vision

The first place where neural networks made a tremendous difference, is in an area called computer vision. (Analyzing images and videos) In order to understand how deep learning, or these big neural networks, can be applied to computer vision, is good to understand what image features are.

Image Features

• Features = local detectors
  • Combined to make prediction
  • (in reality, features are more low-level)

In computer vision, image features are kind of like local detectors that get combined to make a prediction. Take a particular image, want to predict whether this is a face image or not a face image.

Run the neural detector, if all these fire, using a little neural network, then can say this is a face.

• Nose detector
• Eye detector
• Another eye detector
• Mouth detector

This is a simple example of how it can build a classifier for images, but in reality they don’t explicitly have a nose detector or eye detector.

Typical Local Detectors Look For Locally “Interest Points” in Image

• Image features: collections of locally interesting points
  • Combined to build classifiers

What happens is these called image features, or interest points (there are various names for it), they really tried to final local image segments, patches, that are really distinctive. So maybe they’ll find the corner around the eye, maybe the corner around the nose. So if there are lots of these corner detectors (a face is comprised of corners), corner detector firings at places around the eyes, the mouth, and nose. If enough of these fire in a particular pattern, a face is discovered. This is how computer vision typically works, how classification works. Of course, there’re more general models and more complex ones, but this is the basic idea.

Many Hand Created Features Exist For Finding Interest Points…

• Spin Images [Johnson and Herbert ‘99]
• Textons [Malik et al. ‘99]
• RIFT [Lazebnik ‘04]
• GLOH [Mikolajczyk and Schmid ‘05]
• HoG [Dalal and Triggs ‘05]
• SIFT [Lowe ‘99]

For years, these types of detectors of local features are built by hand. A very popular one was called SIFT features, and this retransformed their computer vision because they were really quite applicable and quite cool. There are many other that can improve accuracy. Other kinds of features that can be used.

Standard Image Classification Approach

Talked about this hand created image features like SIFT feature. Now talk about how they can be typically used for classification.

• Run the sifted textures over the image and they fire in various places
• (For example the corners of the eyes and the mouth)
• Create a vector that describe the image based on the firings, the locations where those SIFT features fired
  • Might have some firings in some locations, no firings in other locations
  • Can be viewed similarly to the words in a document
  • Does the word messy appear
  • Does the word football appear
  • Similarly, does a corner appear in a particular place in the image
• Once have the description of the image, can feed it to a classifier (for example, a simple linear classifier)
  • Logistic regression
  • Support Vector Machine
  • …and more
• From there, get a detection as to whether this image is a face or not

Now that sounds pretty exciting and it had a real significant impact in their computer vision.

Many Hand Created Feature Exist For Finding Interest Points…

…but very painful to design

The challenge though, is that creating these hand built image features was a really complicated process and require several PhD thesis to be done well.

Deep Learning: Implicitly Learns Features

Neural networks are going to discover and learn those features automatically.

Example, supposed given an input image, and they run it through a three layer neural network before making a prediction

• Typically what happens, is that it learn local feature detectors (they’re like SIFT)
• But at different levels and different layers
• These detectors that is learned, they detect different things, different properties of the the image at different levels
• The first layer
  • Might learn detectors that look kind of like little patches
  • Which really react to things like diagonal edges
  • All about capturing diagonal edges
    • The first one is about capturing diagonal edges
    • The center one is about capturing diagonal edges in the other direction
    • The last one is about capturing transitions and color from dark to green
• The next (second) layer
  • Combining the diagonal edge detection into some kind of more complex detector
  • For example, discovered this wiggly line and pattern detectors in the layer
  • Also discovered this kind of detectors that react to and detect corners in the image
• The final (third) layer
  • Come up with detectors that are even more complicated
  • For a variety of images, might end up with things that react to torsos and faces
  • Maybe with a bigger data set, it can even fire up with images of corals

So neural networks capture different types of image features at different layers, and then they get learned automatically.

Deep Learning Performance

Deep learning is exciting because it learns these complex features of images. They also had tremendous impact over the recent years in a variety of computer vision applications.

Sample Results Using Deep Neural Network

• German traffic sign recognition benchmark
  • 99.5% accuracy (IDSIA team)
• House number recognition
  • 97.8% accuracy per character (Goodfellow et al. ‘13)

One is an example of identifying traffic signs based on neural networks.

• So these are a dataset of German traffic signs
• The idea is for every image, identify what sign it is
• They were able to get 99.5% accuracy using a deep neural network

Another is an example that came out of some work from Google on identifying the house number based on what’s called street view data.

• This is the data that Google uses driving around cars and photographing all sorts of streets around the world
• The images are pretty complex
• Still, they’re able to get 97.8% accuracy on the per character level

These were exciting results. But the one that changed everything, the really excited field happened in 2012.

ImageNet 2012 Competition: 1.2M Training Images, 1000 Categories

For many years, there was an image competition called ImageNet.

• In 2012, the ImageNet competition included 1.2 million training images from about 1,000 categories
• The idea was to classify an image (not just a dog, but is it a golden retriever or labrador?)
• Very, very fine level detail

There were many teams competing. There were top 3 teams.

• A team called OXFORD_VGG
  • Which got pretty decent accuracy
  • Looking at their top 5 guesses, they were getting about 25% error
  • Using traditional techniques like SIFT
• A team called ISI
  • Did a little bit better
  • Using traditional techniques like SIFT, a little bit more elaborate, kind of like that
• A team called SuperVision
  • Used a deep neural network and had huge gain over the competitors
  • That performance really sparked a lot of excitement of using deep neural networks in computer vision
  • They didn’t have to just use hand coded features, they can be learned automatically

Winning entry: SuperVision

• 8 layers, 60M parameters (Krizhevsky et al. ‘12)

Achieving these amazing result required:

• New learning algorithms
• GPU implementation

Now that neural network that won the competition with the SuperVision team was called the AlexNet neural network. That neural network

• Involved 8 layers, 60 million parameters
• Was only possible because
  • New training algorithms that could deal with lots of images and lots of parameters
  • The GPU implementation that would really scale to large data sets

Deep Learning on ImageNet

Deep learning had a tremendous part in the ImageNet competition. Which allowed them to take 1.2 million images to the deep neural network and get amazing performance to predict on of a thousand different categories.

Deep Learning in Computer Vision

There are some examples of neural networks in computer vision and doing classification. Such as “Is there a labrador retriever in this image?”. But they can do quite a bit more.

Scene Parsing With Deep Learning

For example, it can do image parsing. For every picture in an image, try to classify it and discover regions. This kind of image description, or is called scene understanding. It is pretty cool, and neural network provided significant gains.

Retrieving Similar Images

Going back a bit, to the discussion of a new way to shop for shoes or dresses. The thing tried there is to retrieve similar images.

• For example, given input of boring black shoe, what neural network will output is similar black shoes.
• If a little bit more stylish boot is input, it gives a variety of interesting boots.
• Similarly for heels, for brown shoes, for sneakers, and so on.

Challenges of Deep Learning

Neural networks provide some exciting results. However, they do come with some challenges.

Deep Learning Score Card

Pros

• Enables learning of features rather than hand tuning
• Impressive performance gains
  • Computer vision
  • Speech recognition
  • Some text analysis
• Potential for more impact

Cons

• Requires a lot of data for high accuracy
• Computationally really expensive
• Extremely hard to tune
  • Choice of architecture
  • Parameter types
  • Hyperparameters
  • Learning algorithm
  • …

On the pro side.

• They enable it to represent this non-linear complex features
• They have impressive results, not just in computer vision, but in some other areas like speech recognition
• So systems like Siri on the phone and others use neural networks behind the scene
• As well as some text analysis tasks
• Potential for much more impact in the wide range of areas

Although there’s some great pros, neural network also comes with some cons too.

• They require lots of data to get great performance
• They are computationally expensive, even with GPUs they can be computationally expensive
• They are extremely hard to tune
• There are a lot of choices
  • Layers to use
  • Parameters to use
  • Can be really hard

Computational Cost + So Many Choices = Incredibly Hard To Tune

They do come with some challenges.

Deep Learning Workflow

To understand the challenges, need to talk about the workflow of training a neural network.

• Start with lots and lots and lots of data
  • That data has to be labeled
  • That requires a lot of human annotation and that can be hard
• Feed it, split them into training tasks or validation sets
  • Learned with deep neural network, and that can take quite a while
• But once validate
  • Realized that complex eight layer structure of 60 million parameters wasn’t exact what is needed
  • Need to revise it, or adjust parameters, or change how it is learned
• Have to iterate again and again

Many Tricks Needed To Work Well…

• Different types of layers, connections, …
• Needed for high accuracy

To get the winning neural network

• Really needed to connect various layers with different representations
• Lots of complexity in the learning algorithm
• It was hard

So if combining the computational choices and costs with so many things too soon, it will end up with an incredibly hard process to figure out what neural network to use.

Deep Features: Deep Learning + Transfer Learning

Learned that deep neural networks are really cool, high accuracy tool. But they can be really hard to build and learn, and requires lots and lots of data. Next going to talk about something really exciting. Which is called deep features, which allow it to build neural networks, even when it doesn’t have a lot of data.

Standard Image Classification Approach

Going back to the image data classification pipeline

• Start with an image
• Detected some features, or other representations
• Fed that to a simple classifier, like a linear classifier

The question here is can it use the features that is learned through the neural network? Those cool ones at the corners, edges, and even faces to feed that classifier. Can do something a different different?

Transfer Learning: Use Data From One Task to Help Learn on Another

Old idea, explored for deep learning by Donahue et al. ‘14 & others

The idea here, having deep features, is something called transfer learning. Transfer learning is a pretty old idea that’s been around for quite a while, but has a lot of impact in recent years in area of deep neural networks.

• So the idea is to train the neural network in a case where there it have lots and lots of data (for example, in a task of differentiating cats versus dogs)
• Learned that eight layer, 16 million parameter complex neural network
• Able to get great accuracy in the task of cats versus dogs

Now what if there is a little bit of data, not tons of data for new tasks? Trying to detect chairs, elephants, cars, camera, in hundreds of categories. Can somehow use the features learned in cats versus dogs to combine for simple classifier and feed that and get great accuracy on this 101 new categories?

Reference

• [PDF] Deep Learning
• Object Recognition From Local Scale-Invariant Features
• Spin-Images: A Representation For 3-D Surface Matching
• Representing and Recognizing the Visual Appearance of Material Three-dimensional Textons
• A Sparse Texture Representation Using Local Affine Regions
• A Performance Evaluation of Local Descriptors
• Histograms of Oriented Gradients for Human Detection
• SURF: Speeded Up Robust Features
• ImageNet Classification with Deep Convolutional Neural Networks
• Computer Vision
• Scale-Invariant Feature Transform