Re:Deep Neural Decision Forests [pdf]
by Fede_V on Saturday November 14, 2015 @02:32PM
(#10566885)
Sure.
Random forests are a very powerful machine learning method that has proven to give excellent performance with very little tuning. Neural networks with many layers (aka deep learning) is the new frontier of machine learning - they are very powerful but require extensive tuning (the architecture of the network) and lots of examples before they become practical.
In this paper, the authors combine the two methods - they basically stack a random forest on top of a neural network, and obtain some cutting edge results. One of the main theoretical results in the paper is that they propose a differentiable (which means you can use gradient-based optimization techniques) technique to optimize the parameters of the trees (which are the building blocks of the random forest).
Re:Deep Neural Decision Forests [pdf]
by obastani on Saturday November 14, 2015 @04:40PM
(#10567378)
I think there are a few additional important details.
It's not so much that they stack a random forest on top of a neural network, as that they are trying to train neural networks that have tree-like properties. Deep neural networks can be expensive to evaluate because every layer is needed to compute the resulting label. On the other hand, in a decision tree you only need to evaluate one of a nodes children (i.e., evaluation is linear in the depth of the tree).
They combine these ideas by allowing some nodes in the network to branch (so for a given image, you choose one of two neural networks to evaluate). These nodes don't have to occur at the top level, but can occur in the middle of the network as well.
The difficulty is how you train these nodes; that's where the differential technique for optimizing trees come in. Because you have a unified training algorithm, you can mix and match tree-like nodes and neural network like nodes and train the whole thing.
All in all, the hope is that getting a label for a given node is much faster, so you can run these on smaller devices such as phones without sacrificing accuracy.
Re:Deep Neural Decision Forests [pdf]
by JD557 on Saturday November 14, 2015 @02:39PM
(#10566914)
Also, it might be worth adding that random forests are based on decision trees, which can be interpreted by humans.
While it's hard to interpret a random forest, it's still much more interpretable than a neural network. Maybe this model is also easier to interpret by humans.
Re:Deep Neural Decision Forests [pdf]
by eva1984 on Saturday November 14, 2015 @05:12PM
(#10567486)
Old time neural networks not even came close to current models in terms of performance.
I clearly remember in my machine learning class, one professor mentions neural networks and says it is slow and impossible to tame when the layers goes up thus loses its popularity. That is just 3-4 years ago.
Re:Deep Neural Decision Forests [pdf]
by tormeh on Saturday November 14, 2015 @11:39PM
(#10568518)
I took some machine learning classes a while 1-2 years ago at the TU Berlin, and while there was some emphasis on neural nets, it was just as much emphasis on SVMs, with the remainder of the time filled with other traditional models. The lecturer had done some research into SVMs, though, so it was probably just bias rather than old-fashionedness. He was also of the mathematical sort, and I suspect the unanalyzable nature of NNs rubbed him the wrong way. I'm not saying that all other AI/ML methods should be abandoned, but NN definitely didn't get the attention it deserved. Deep learning techniques weren't covered at all, for example.
Re:Deep Neural Decision Forests [pdf]
by yabun on Saturday November 14, 2015 @05:20PM
(#10567524)
Deep learning has really only recently become successful with new learning algorithms such as constrastive divergence and convolutional neural networks. Previous efforts were focused around backpropagation, but due to the signal loss across many layers there was never enough information in the output layer to successfully train the network.
Re:Deep Neural Decision Forests [pdf]
by seiji on Saturday November 14, 2015 @05:42PM
(#10567600)
Time for a fact update! My, my, how time flies.
Deep learning has really only recently become successful
hinton coined the term "deep learning" around 2006/2007 (more around deep belief nets/RBMs, but still, same thing), if that's considered "recently."
constrastive divergence and convolutional neural networks.
CD was also ~10 years ago. CNNs were reading your checks and postal zipcodes in the mid 90s.
successfully train the network.
In the early 90s, RNNs were driving cars on highways using only webcams under basically VFR. No giant sensors, no LIDAR, no GPS, no mesh networks, just camera input.
Re:Deep Neural Decision Forests [pdf]
by nl on Saturday November 14, 2015 @10:19PM
(#10568344)
The 2012 ImageNet results were what really launched the current interest.
Before that there was little evidence that any form of neural network was massively better than other forms of machine learning. Now it has become clear that isn't the case.
Re:Deep Neural Decision Forests [pdf]
by mtrimpe on Saturday November 14, 2015 @03:04PM
(#10567015)
Regular neural networks were popular until they stopped delivering best-in-class results for a lot of problems.
Recent hardware made it possible to train more layers and they're now getting cutting-edge results in many areas again so they're now getting more attention again.
Re:Deep Neural Decision Forests [pdf]
by simonhughes22 on Saturday November 14, 2015 @05:52PM
(#10567639)
Yes and No. Layer to layer training of deep belief nets were doing very well before alex.net came along, although alex.net was seminal for images. People often miss the big 'advances' in RNN's, although those go back to the 90's and earlier. A lot of this (but not all) is also due to more data, better and faster hardware (including GPU's). Although there have been some important algorithmic enhancements too.
Re:Deep Neural Decision Forests [pdf]
by YeGoblynQueenne on Wednesday November 18, 2015 @04:47AM
(#10586841)
What I mean is that decision trees are not seen as optimising a function so it doesn't make much sense to think of them as finding optima, or getting stuck in sub-optima (if I may).
That's the traditional view. I guess it's always possible to see decision trees as optimising a binary function, but that's probably to be filed under "original research". Or maybe not- I'm not sure.
In any case, I've never heard of anyone worried that a tree learner would get stuck anywhere. The concern is usually with overfitting.
Re:Deep Neural Decision Forests [pdf]
by gamegoblin on Saturday November 14, 2015 @03:00PM
(#10567000)
Super high level of deep nets, skip if you already know:
Deep nets are good at taking a vector of size N and transforming it to a vector of size M, where M is perhaps a more general, abstract, or "useful" representation.
e.g.
Your N-vector might be a length 786 vector of floating point values representing black-intensity in a 28x28 grayscale image. This is the case in the MNIST dataset (lots of 28x28 images of the digits 0-9), a classic dataset in machine learning.
After a layer or two of a deep net, this N-vector might be transformed into an M-vector where each component represents some particular edge, curve, or blip within the source image.
So you've gone from the representation of "pixel 0 is gray, pixel 1 is dark gray, pixel 2 is white..." to a representation of "There is a vertical edge on the central lefthand side of the image, there is an upwards facing curve in the central top part of the image....".
It's clear that the latter representation is more compact and useful for the purpose of digit recognition.
It's also worth noting this representation is specific to the problem at hand. The edges and curves you have learned would probably be unable to accurately reproduce say, letters of the alphabet, as they are specialized to reproducing digits. The net has learned a more compact representation by using statistics to figure out that most of the information is redundant. There are only 10 possible outputs, but the input space is 256 grayscale values ^ 768 pixels.
In a traditional deep net, your output layer for this particular problem (digit recognition) might be a vector of length 10, where element of the vector is the probability of that digit being the one shown. So a result of <0.1, 0.1, 0.998, 0.0 ... 0.0> would indicate that the net thought the digit was a 2.
================
Super high level of decision trees and forests, skip if you already know:
A decision tree is somewhat self-explanatory -- it's kind of like a flow chart for making judgments. Here is an example, classifying cool vs. uncool based on 3 attributes.
if bow_tie == true
return true
else
if socks == true
if sandals == true
return false
else
return true
else
if sandals == true
return true
else
return false
It's also worth noting that decisions trees can be equal with different representation. The following will always return the same value as the above for the elements of the dataset:
if socks == true
if sandals == true
if bow_tie == true
return true
else
return false
else
return true
else
if sandals == true
return true
else
if bow_tie == true
return true
else
return false
The difference is how you pick the divisions. The first one uses a more entropy-reducing strategy -- we notice that the bow_tie division is a simple, hard rule. Bowties are cool. The second is more of a random decision decision tree, so it's less "efficient" in that it must make potentially more judgments.
Why would we ever want to be less efficient? It turns out if you train several (hundreds, thousands, etc) decision trees on subsets of the data, and then average their results together, they are alarmingly good classifiers. Extremely simple to code, train, and use. This is called a decision forest. A decision tree on its own is often weak, but decision forests are a powerful tool.
================
High level of why this work is interesting:
The traditional means of training a deep neural net is with gradient descent. The most common form of this is some method of "backpropagation". You run a training example through your network, calculate the error between the result and expected result, and then propagate this error gradient back through the network to tune the transformations to produce closer to what you want. This method often requires the functions you use within the deep network to be differentiable.
As mentioned above, there are several training strategies for decision trees, but the most common is some form of "mostly random".
To extend my example from the first section, one could use the deep neural net to transform the 768 grayscale pixel values into perhaps 30 higher level edge/curve features. Then one could use this length 30 vector as the input to train a decision forest.
This might end up getting better results than either strategy by itself. You use the neural net to do the abstracting and the decision forest to make the final decision. This uses both of their advantages in tandem -- deep neural nets are great at generating more abstract and general features, and decision forests are quite good at producing accurate classifications given high-quality, lower-dimensional input data.
This idea of multi-tiered systems isn't particularly new. What this paper does, though, is introduce a differentiable decision tree. This means that they can train their decision trees with gradient descent, the same way they train the neural network. This means that, rather than training the two tiers of their system individually, they can train them together, producing even better results.
Re:Deep Neural Decision Forests [pdf]
by freedryk on Saturday November 14, 2015 @03:03PM
(#10567010)
To elaborate on Fede_V's comment, Deep Neural Networks seem to work well on classification problems because they can automatically build abstract features from a dataset and combine them in different ways. Like, in image data they will automatically identify common shapes and patterns of light and dark, and combine these simple patterns together to identify faces or whatever (like by saying a face is a circle with two dots for eyes and a line for a mouth). Random Forests, on the other hand, are really good at classifying things if you give them meaningful dataset features to learn on, but aren't as good at building these features in the first place. By combining them together, they get a system with the classification abilities of random forests and the automated feature discovery of deep neural nets, and it seems to work a bit better than either.
Re:Deep Neural Decision Forests [pdf]
by simonhughes22 on Saturday November 14, 2015 @05:56PM
(#10567655)
They currently really excel at unstructured data - images and text and speech. If you have structured data though (columns, regular features) it really depends. In Kaggle, RF's and GBT's seem to mostly dominate structured problems, while neural nets dominate unstructured datasets (as they can do feature extraction), according to talk I attended.
Re:Deep Neural Decision Forests [pdf]
by strebler on Saturday November 14, 2015 @08:17PM
(#10568088)
Why do they only compare their method against GoogLeNet? VGG was the winner in 2014, most papers seem to use VGG and my team has observed it to always gets higher accuracy than GoogLeNet.
Re:Deep Neural Decision Forests [pdf]
by nl on Saturday November 14, 2015 @10:16PM
(#10568339)
GoogLeNet "won" ImageNet 2014[1], but VGG is often found to be more flexible.
I'm not entirely sure, but I think that the multiple softmax layers in GoogLeNet might make it easier to modify for this purpose than the VGG architecture.
Random forests are a very powerful machine learning method that has proven to give excellent performance with very little tuning. Neural networks with many layers (aka deep learning) is the new frontier of machine learning - they are very powerful but require extensive tuning (the architecture of the network) and lots of examples before they become practical.
In this paper, the authors combine the two methods - they basically stack a random forest on top of a neural network, and obtain some cutting edge results. One of the main theoretical results in the paper is that they propose a differentiable (which means you can use gradient-based optimization techniques) technique to optimize the parameters of the trees (which are the building blocks of the random forest).
It's not so much that they stack a random forest on top of a neural network, as that they are trying to train neural networks that have tree-like properties. Deep neural networks can be expensive to evaluate because every layer is needed to compute the resulting label. On the other hand, in a decision tree you only need to evaluate one of a nodes children (i.e., evaluation is linear in the depth of the tree).
They combine these ideas by allowing some nodes in the network to branch (so for a given image, you choose one of two neural networks to evaluate). These nodes don't have to occur at the top level, but can occur in the middle of the network as well.
The difficulty is how you train these nodes; that's where the differential technique for optimizing trees come in. Because you have a unified training algorithm, you can mix and match tree-like nodes and neural network like nodes and train the whole thing.
All in all, the hope is that getting a label for a given node is much faster, so you can run these on smaller devices such as phones without sacrificing accuracy.
While it's hard to interpret a random forest, it's still much more interpretable than a neural network. Maybe this model is also easier to interpret by humans.
Depends on the domain. The first layer or two of a neural network can be fairly interpretable on image or spectrogram (sound) data, for example.
I clearly remember in my machine learning class, one professor mentions neural networks and says it is slow and impossible to tame when the layers goes up thus loses its popularity. That is just 3-4 years ago.
Deep learning has really only recently become successful
hinton coined the term "deep learning" around 2006/2007 (more around deep belief nets/RBMs, but still, same thing), if that's considered "recently."
constrastive divergence and convolutional neural networks.
CD was also ~10 years ago. CNNs were reading your checks and postal zipcodes in the mid 90s.
successfully train the network.
In the early 90s, RNNs were driving cars on highways using only webcams under basically VFR. No giant sensors, no LIDAR, no GPS, no mesh networks, just camera input.
Before that there was little evidence that any form of neural network was massively better than other forms of machine learning. Now it has become clear that isn't the case.
Recent hardware made it possible to train more layers and they're now getting cutting-edge results in many areas again so they're now getting more attention again.
(Yes this is hyperbole, but any old timers out there will know the feeling)
Also "Past decades was AI winter. But no worries, now we'll start seeing human intelligence in a about next year" probably heard that since late 90's.
Yay! Now Decision Trees too can get stuck in local optima! :D
(totally tongue in cheek)
That's the traditional view. I guess it's always possible to see decision trees as optimising a binary function, but that's probably to be filed under "original research". Or maybe not- I'm not sure.
In any case, I've never heard of anyone worried that a tree learner would get stuck anywhere. The concern is usually with overfitting.
Deep nets are good at taking a vector of size N and transforming it to a vector of size M, where M is perhaps a more general, abstract, or "useful" representation.
e.g.
Your N-vector might be a length 786 vector of floating point values representing black-intensity in a 28x28 grayscale image. This is the case in the MNIST dataset (lots of 28x28 images of the digits 0-9), a classic dataset in machine learning.
After a layer or two of a deep net, this N-vector might be transformed into an M-vector where each component represents some particular edge, curve, or blip within the source image.
So you've gone from the representation of "pixel 0 is gray, pixel 1 is dark gray, pixel 2 is white..." to a representation of "There is a vertical edge on the central lefthand side of the image, there is an upwards facing curve in the central top part of the image....".
It's clear that the latter representation is more compact and useful for the purpose of digit recognition.
It's also worth noting this representation is specific to the problem at hand. The edges and curves you have learned would probably be unable to accurately reproduce say, letters of the alphabet, as they are specialized to reproducing digits. The net has learned a more compact representation by using statistics to figure out that most of the information is redundant. There are only 10 possible outputs, but the input space is 256 grayscale values ^ 768 pixels.
In a traditional deep net, your output layer for this particular problem (digit recognition) might be a vector of length 10, where element of the vector is the probability of that digit being the one shown. So a result of <0.1, 0.1, 0.998, 0.0 ... 0.0> would indicate that the net thought the digit was a 2.
================
Super high level of decision trees and forests, skip if you already know:
A decision tree is somewhat self-explanatory -- it's kind of like a flow chart for making judgments. Here is an example, classifying cool vs. uncool based on 3 attributes.
My dataset:
A possible decision tree: It's also worth noting that decisions trees can be equal with different representation. The following will always return the same value as the above for the elements of the dataset: The difference is how you pick the divisions. The first one uses a more entropy-reducing strategy -- we notice that the bow_tie division is a simple, hard rule. Bowties are cool. The second is more of a random decision decision tree, so it's less "efficient" in that it must make potentially more judgments.Why would we ever want to be less efficient? It turns out if you train several (hundreds, thousands, etc) decision trees on subsets of the data, and then average their results together, they are alarmingly good classifiers. Extremely simple to code, train, and use. This is called a decision forest. A decision tree on its own is often weak, but decision forests are a powerful tool.
================
High level of why this work is interesting:
The traditional means of training a deep neural net is with gradient descent. The most common form of this is some method of "backpropagation". You run a training example through your network, calculate the error between the result and expected result, and then propagate this error gradient back through the network to tune the transformations to produce closer to what you want. This method often requires the functions you use within the deep network to be differentiable.
As mentioned above, there are several training strategies for decision trees, but the most common is some form of "mostly random".
To extend my example from the first section, one could use the deep neural net to transform the 768 grayscale pixel values into perhaps 30 higher level edge/curve features. Then one could use this length 30 vector as the input to train a decision forest.
This might end up getting better results than either strategy by itself. You use the neural net to do the abstracting and the decision forest to make the final decision. This uses both of their advantages in tandem -- deep neural nets are great at generating more abstract and general features, and decision forests are quite good at producing accurate classifications given high-quality, lower-dimensional input data.
This idea of multi-tiered systems isn't particularly new. What this paper does, though, is introduce a differentiable decision tree. This means that they can train their decision trees with gradient descent, the same way they train the neural network. This means that, rather than training the two tiers of their system individually, they can train them together, producing even better results.
I'm not entirely sure, but I think that the multiple softmax layers in GoogLeNet might make it easier to modify for this purpose than the VGG architecture.
[1] http://image-net.org/challenges/LSVRC/2014/results (look for "Classification+localization with provided training data: Ordered by classification error")