6 ms·

When to assume neural networks can solve a problem

165 points by george3d6 7y ago

lidHanteyk 7y ago
I don't understand why the author thinks that the PAC learning framework is not useful. PAC gives quick back-of-napkin math for estimating how long it might take to train a network, what kind of quality level is acceptable for inputs, etc.
- mlthoughts2018 7y ago
  PAC does not provide these types of estimates in most practical situations.
- 317070 7y ago
  Correct me if I'm wrong, but doesn't PAC on real data usually just tells you that "it doesn't know the answer"? Like, it says the equivalent to: "I think this is the answer, but it might be miles off and I give it 50% it is even more than miles off." I found that it is able to give hard guarantees, by being very loose on the bounds. Do you have a real-world example where it actually gave something useful? I'm genuine curious, because I discarded it early on, but am willing to revisit it.
- eugenhotaj 7y ago
  I disagree, PAC bounds are usually way too loose to be useful in practice when it comes to NNs. I think part of the reason is that the way we measure model complexity for NNs does not correspond very well with their ability to generalize, as we've seen with recent papers like deep double descent [1]. Anecdotally, I was of the main authors of the AdaNet framework [2] where we used (approximate) Rademacher complexity (closely related to PAC) to bound the complexity of our learned ensemble models. We never got good results using the complexity measure and would basically turn it off for any practical problem we solved. [1]: https://openai.com/blog/deep-double-descent https://openai.com/blog/deep-double-descent [2]: https://github.com/tensorflow/adanet https://github.com/tensorflow/adanet
makach 7y ago
This reminds me of an oldie, but goodie: http://thedailywtf.com/articles/No%2C_We_Need_a_Neural_Network http://thedailywtf.com/articles/No%2C_We_Need_a_Neural_Netwo...
- kelvin0 7y ago
  Wow, I had never read this gem before. Made me laugh, thanks for sharing this piece! I'm surprised they did not ask him to log everything in a blockchain :)
  - tmoravec 7y ago
    I think that's only because the story is from 2006 so blockchain was not a thing, yet.
  - teraflop 7y ago
    Check the date -- the article predates the Bitcoin white paper by two years. (It also predates most of the modern "deep learning" hype.)
- narag 7y ago
  No Quack.
ramoz 7y ago
What is the current state of NN in the context of AI state of the art?
gambler 7y ago
I've been hearing about deep learning revolutionizing "everything" for the past 8 years. So, can someone name me any significant impact it made on figuring out what to do about the recent epidemic? If not, I think it's worth reflecting on what value we get out of the technology that sucked up so much of our intellectual, financial and computational resources.
- forgotmyhnacc 7y ago
  I've been hearing about modern JavaScript development revolutionizing "everything" for the past 8 years. So, can someone name me any significant impact it made on figuring out what to do about the recent epidemic? If not, I think it's worth reflecting on what value we get out of the technology that sucked up so much of our intellectual, financial and computational resources.
  - gambler 7y ago
    This is a nonsensical response on two levels. First, you're missing the obvious fact that the response to this pandemic is largely dictated by data processing. People are modeling the spread of the virus, trying to make predictions about the optimal policy, trying to figure out infection rates without full testing and evaluating promising drugs. All of those things relate to modeling and data analysis. Deep learning was touted to revolutionize exactly those two things. Second, web technologies are making an obvious impact by allowing (some, many) people to stay in touch, stay informed, keep working and buy stuff without exposing themselves to crowded places. This constitutes visible and significant positive impact.
- malux85 7y ago
  If you're listening to people who claim any one technology solves "everything" --- and believing them --- then you are the fool. There's no silver bullet. Deep Learning has made huge strides in noise reduction, image and video processing (self driving cars), lidar processing, medical imaging, etc, but it's not made any progress in knitting, tooth brushing, dog walking, or many other tasks ill suited for deep learning - so clearly not everything.
imvetri 7y ago
When a neural network solved a problem, it means it found the algebraic function it needs to solve the problem. > Once it found the algebraic function, there is no need to run the problem to the neural network. We can sideload the problem to a simple program that takes input and gives an output. This strategy can help to free up the GPU for next set of problem.
- ludwigschubert 7y ago
  How would one extract an algebraic function from the network’s weights? Why would the function the network approximates necessarily be algebraic?
  - Plough_Jogger 7y ago
    The function would simply be a chain of multiplications and (typically) non-linear transformations. For classification problems, there is often a final non-linear transformation, like a softmax. Example with ReLu activation: Output_i = max((input_i * weight_i),0)
    - jawarner 7y ago
      I don't understand. The example you gave is not an algebraic function.
      - Plough_Jogger 7y ago
        You are correct. It is possible to construct a linear neural network, where an algebraic function could be extracted, but in practice, almost all networks use non-linear activation functions. In the case of a linear network, the function would be a dot product between the input and the weights: 𝑥1𝑤1+𝑥2𝑤2+𝑥3𝑤3 ... for all inputs (xi) and weights (wi)
folbec 7y ago
"That’s why building a product recommendation algorithm was a hot topic 20 years ago, but nowadays everyone and their mom can just get a WordPress plugin for it and get close to Amazon’s level." Well, I haven't had a remotely relevant Amazon recommendation in 5 to 10 years. Unless you count read a book by the exact same author as a useful recommendation.
- scrooched_moose 7y ago
  At least on my account, it seems like Amazon has given up on recommendations and is just suggesting I buy the same things again. I wouldn't be shocked if it's actually quite a bit more accurate then real predictions, but it does lead to funny things like "You already bought this book? How about a second copy?"
  - pareshverma91 7y ago
    I wonder if the same book recommendations are happening because people might just be buying products like these for gifts. Something like I liked this book, so you should read it to.
ljlolel 7y ago
I've made a neural network where you feed it a problem and it will tell you if a neural network will solve it. I call it a Neural decider. Getting weird results when I feed it to itself though.
- keiferski 7y ago
  Neuroboros?
manthideaal 7y ago
it seems that neural networks have problem for computing the maximum function, and a human can compute the maximum easily, so it seems that the three heuristic rules don't work in this case. (1) https://datascience.stackexchange.com/questions/56676/can-machine-learning-learn-a-function-like-finding-maximum-from-a-list https://datascience.stackexchange.com/questions/56676/can-ma...
- george3d6 7y ago
  That is untrue, Here's a code example (actually took me ~20 minutes to get it "right" so I'll admit it's not the most trivial problem)... it includes seeds so that you can replicate locally (it should hit 100% accuracy all the time on the 1200 examples testing set reliably by about epoch 700): ''' import torch import random from sklearn.metrics import accuracy_score random.seed(61) torch.manual_seed(61) X = [[random.random() for x in range(2)] for x in range(2000)] X_train = torch.FloatTensor(X[0:800]).cuda() X_test = torch.FloatTensor(X[800:]).cuda() X = torch.FloatTensor(X) Y = [] for x in X: y = [0] * len(x) y[torch.argmax(x)] = 1 Y.append(y) Y_train = torch.FloatTensor(Y[0:800]).cuda() Y_test = torch.FloatTensor(Y[800:]).cuda() shape = [2,2] layers = [] for ind in range(len(shape) - 1): layers.append(torch.nn.Linear(shape[ind],shape[ind+1],bias=False)) net = torch.nn.Sequential(layers).cuda() optim = torch.optim.SGD(net.parameters(), lr=1) criterion = torch.torch.nn.CrossEntropyLoss() dataset = torch.utils.data.TensorDataset(X_train, Y_train) dataloader = torch.utils.data.DataLoader(dataset, shuffle=True, batch_size=10) for i in range(pow(10,6)): for X,Y in dataloader: Yp = net(X) loss = criterion(Yp, Y.max(1).indices) loss.backward() optim.step() optim.zero_grad() if i > 500: optim = torch.optim.SGD(net.parameters(), lr=0.002) if i % 20 == 0: Yp = net(X_test) print('Training loss: ', loss.item()) print(f'\nAccuracy score for epoch {i}:') print(accuracy_score(Yp.max(1).indices.tolist(),Y_test.max(1).indices.tolist())) ''' This is as basic as you can get, predict the max out of 2 numbers, only uses a total of 4 node: 2 inputs (the 2 number) -> 2 outputs (the index of the maximum numbers). just 2 weight being optimize, no biases no nothing, as simple an implementation as you can get in terms of size. There's also way to do it (apparently) where instead of treating it as "find the max index" you treat it as "output the maximum number": https://www.quora.com/Can-deep-neural-networks-learn-the-minimum-function https://www.quora.com/Can-deep-neural-networks-learn-the-min... But the approach I have will generalize to e.g. "Find the max of 5 or 100 or 1000 numbers" (although I assume it might take some time) And overall you have no guarantee, that's why I qualified the statement and didn't say "Literally any imaginable problem that a human can solve without context". To some extent it also matter how you encoder your number, you can train a 10000000000 parameter FCNN with RELU activations until the end of time to learn a simple mutliplication, and it won't be able to do so if you don't log encode your numbers or use some encoding or activation that means `` can be transposed in the `+` operations being done inside the nodes to combine the outputs... because that's outside of the scope of mathematics that given netwrok can do. But, unless you are specifically trying to come up with an edge case and are instead looking at real world problems and trying to design the network in such a way as to best handle them (and this doesn't have to be all manual, you can use various NAS techniques), the rule will hold most of the time I believe.
mooshmoosh 7y ago
> 3. A neural network can solve problems that a human can solve with small-sized datapoints and little to no context I like this rule, because it is actionable. Its easy to take a sample of your data, (in the case of images) lower the quality to 20x20 pixels and get see if you, or another person can do the classification task. Audio could be handled similarly.
jonesn11 7y ago
Here is a take from Google AI on when to use ML: https://developers.google.com/machine-learning/problem-framing/good https://developers.google.com/machine-learning/problem-frami... "You should understand the problem well enough to list some potential solutions to test first to find the best model" and "it shouldn't be used for a problem that conventional programming can solve" like hard coding a symbolic rule.
- rahimnathwani 7y ago
  Unless it's fizzbuzz: https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/ https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/

165 points by george3d6 7y ago

I don't understand why the author thinks that the PAC learning framework is not useful. PAC gives quick back-of-napkin math for estimating how long it might take to train a network, what kind of quality level is acceptable for inputs, etc.

mlthoughts2018 7y ago
PAC does not provide these types of estimates in most practical situations.
317070 7y ago
Correct me if I'm wrong, but doesn't PAC on real data usually just tells you that "it doesn't know the answer"? Like, it says the equivalent to: "I think this is the answer, but it might be miles off and I give it 50% it is even more than miles off." I found that it is able to give hard guarantees, by being very loose on the bounds. Do you have a real-world example where it actually gave something useful? I'm genuine curious, because I discarded it early on, but am willing to revisit it.
eugenhotaj 7y ago
I disagree, PAC bounds are usually way too loose to be useful in practice when it comes to NNs. I think part of the reason is that the way we measure model complexity for NNs does not correspond very well with their ability to generalize, as we've seen with recent papers like deep double descent [1]. Anecdotally, I was of the main authors of the AdaNet framework [2] where we used (approximate) Rademacher complexity (closely related to PAC) to bound the complexity of our learned ensemble models. We never got good results using the complexity measure and would basically turn it off for any practical problem we solved. [1]: https://openai.com/blog/deep-double-descent https://openai.com/blog/deep-double-descent [2]: https://github.com/tensorflow/adanet https://github.com/tensorflow/adanet

makach 7y ago

This reminds me of an oldie, but goodie: http://thedailywtf.com/articles/No%2C_We_Need_a_Neural_Network http://thedailywtf.com/articles/No%2C_We_Need_a_Neural_Netwo...

kelvin0 7y ago
Wow, I had never read this gem before. Made me laugh, thanks for sharing this piece! I'm surprised they did not ask him to log everything in a blockchain :)
- tmoravec 7y ago
  I think that's only because the story is from 2006 so blockchain was not a thing, yet.
- teraflop 7y ago
  Check the date -- the article predates the Bitcoin white paper by two years. (It also predates most of the modern "deep learning" hype.)
narag 7y ago
No Quack.

ramoz 7y ago

What is the current state of NN in the context of AI state of the art?

gambler 7y ago

I've been hearing about deep learning revolutionizing "everything" for the past 8 years. So, can someone name me any significant impact it made on figuring out what to do about the recent epidemic? If not, I think it's worth reflecting on what value we get out of the technology that sucked up so much of our intellectual, financial and computational resources.

forgotmyhnacc 7y ago
I've been hearing about modern JavaScript development revolutionizing "everything" for the past 8 years. So, can someone name me any significant impact it made on figuring out what to do about the recent epidemic? If not, I think it's worth reflecting on what value we get out of the technology that sucked up so much of our intellectual, financial and computational resources.
- gambler 7y ago
  This is a nonsensical response on two levels. First, you're missing the obvious fact that the response to this pandemic is largely dictated by data processing. People are modeling the spread of the virus, trying to make predictions about the optimal policy, trying to figure out infection rates without full testing and evaluating promising drugs. All of those things relate to modeling and data analysis. Deep learning was touted to revolutionize exactly those two things. Second, web technologies are making an obvious impact by allowing (some, many) people to stay in touch, stay informed, keep working and buy stuff without exposing themselves to crowded places. This constitutes visible and significant positive impact.
malux85 7y ago
If you're listening to people who claim any one technology solves "everything" --- and believing them --- then you are the fool. There's no silver bullet. Deep Learning has made huge strides in noise reduction, image and video processing (self driving cars), lidar processing, medical imaging, etc, but it's not made any progress in knitting, tooth brushing, dog walking, or many other tasks ill suited for deep learning - so clearly not everything.

imvetri 7y ago

When a neural network solved a problem, it means it found the algebraic function it needs to solve the problem. > Once it found the algebraic function, there is no need to run the problem to the neural network. We can sideload the problem to a simple program that takes input and gives an output. This strategy can help to free up the GPU for next set of problem.

ludwigschubert 7y ago
How would one extract an algebraic function from the network’s weights? Why would the function the network approximates necessarily be algebraic?
- Plough_Jogger 7y ago
  The function would simply be a chain of multiplications and (typically) non-linear transformations. For classification problems, there is often a final non-linear transformation, like a softmax. Example with ReLu activation: Output_i = max((input_i * weight_i),0)
  - jawarner 7y ago
    I don't understand. The example you gave is not an algebraic function.
    - Plough_Jogger 7y ago
      You are correct. It is possible to construct a linear neural network, where an algebraic function could be extracted, but in practice, almost all networks use non-linear activation functions. In the case of a linear network, the function would be a dot product between the input and the weights: 𝑥1𝑤1+𝑥2𝑤2+𝑥3𝑤3 ... for all inputs (xi) and weights (wi)

folbec 7y ago

"That’s why building a product recommendation algorithm was a hot topic 20 years ago, but nowadays everyone and their mom can just get a WordPress plugin for it and get close to Amazon’s level." Well, I haven't had a remotely relevant Amazon recommendation in 5 to 10 years. Unless you count read a book by the exact same author as a useful recommendation.

scrooched_moose 7y ago
At least on my account, it seems like Amazon has given up on recommendations and is just suggesting I buy the same things again. I wouldn't be shocked if it's actually quite a bit more accurate then real predictions, but it does lead to funny things like "You already bought this book? How about a second copy?"
- pareshverma91 7y ago
  I wonder if the same book recommendations are happening because people might just be buying products like these for gifts. Something like I liked this book, so you should read it to.

ljlolel 7y ago

I've made a neural network where you feed it a problem and it will tell you if a neural network will solve it. I call it a Neural decider. Getting weird results when I feed it to itself though.

keiferski 7y ago
Neuroboros?

manthideaal 7y ago

it seems that neural networks have problem for computing the maximum function, and a human can compute the maximum easily, so it seems that the three heuristic rules don't work in this case. (1) https://datascience.stackexchange.com/questions/56676/can-machine-learning-learn-a-function-like-finding-maximum-from-a-list https://datascience.stackexchange.com/questions/56676/can-ma...

george3d6 7y ago
That is untrue, Here's a code example (actually took me ~20 minutes to get it "right" so I'll admit it's not the most trivial problem)... it includes seeds so that you can replicate locally (it should hit 100% accuracy all the time on the 1200 examples testing set reliably by about epoch 700): ''' import torch import random from sklearn.metrics import accuracy_score random.seed(61) torch.manual_seed(61) X = [[random.random() for x in range(2)] for x in range(2000)] X_train = torch.FloatTensor(X[0:800]).cuda() X_test = torch.FloatTensor(X[800:]).cuda() X = torch.FloatTensor(X) Y = [] for x in X: y = [0] * len(x) y[torch.argmax(x)] = 1 Y.append(y) Y_train = torch.FloatTensor(Y[0:800]).cuda() Y_test = torch.FloatTensor(Y[800:]).cuda() shape = [2,2] layers = [] for ind in range(len(shape) - 1): layers.append(torch.nn.Linear(shape[ind],shape[ind+1],bias=False)) net = torch.nn.Sequential(layers).cuda() optim = torch.optim.SGD(net.parameters(), lr=1) criterion = torch.torch.nn.CrossEntropyLoss() dataset = torch.utils.data.TensorDataset(X_train, Y_train) dataloader = torch.utils.data.DataLoader(dataset, shuffle=True, batch_size=10) for i in range(pow(10,6)): for X,Y in dataloader: Yp = net(X) loss = criterion(Yp, Y.max(1).indices) loss.backward() optim.step() optim.zero_grad() if i > 500: optim = torch.optim.SGD(net.parameters(), lr=0.002) if i % 20 == 0: Yp = net(X_test) print('Training loss: ', loss.item()) print(f'\nAccuracy score for epoch {i}:') print(accuracy_score(Yp.max(1).indices.tolist(),Y_test.max(1).indices.tolist())) ''' This is as basic as you can get, predict the max out of 2 numbers, only uses a total of 4 node: 2 inputs (the 2 number) -> 2 outputs (the index of the maximum numbers). just 2 weight being optimize, no biases no nothing, as simple an implementation as you can get in terms of size. There's also way to do it (apparently) where instead of treating it as "find the max index" you treat it as "output the maximum number": https://www.quora.com/Can-deep-neural-networks-learn-the-minimum-function https://www.quora.com/Can-deep-neural-networks-learn-the-min... But the approach I have will generalize to e.g. "Find the max of 5 or 100 or 1000 numbers" (although I assume it might take some time) And overall you have no guarantee, that's why I qualified the statement and didn't say "Literally any imaginable problem that a human can solve without context". To some extent it also matter how you encoder your number, you can train a 10000000000 parameter FCNN with RELU activations until the end of time to learn a simple mutliplication, and it won't be able to do so if you don't log encode your numbers or use some encoding or activation that means `` can be transposed in the `+` operations being done inside the nodes to combine the outputs... because that's outside of the scope of mathematics that given netwrok can do. But, unless you are specifically trying to come up with an edge case and are instead looking at real world problems and trying to design the network in such a way as to best handle them (and this doesn't have to be all manual, you can use various NAS techniques), the rule will hold most of the time I believe.

mooshmoosh 7y ago

> 3. A neural network can solve problems that a human can solve with small-sized datapoints and little to no context I like this rule, because it is actionable. Its easy to take a sample of your data, (in the case of images) lower the quality to 20x20 pixels and get see if you, or another person can do the classification task. Audio could be handled similarly.

jonesn11 7y ago

Here is a take from Google AI on when to use ML: https://developers.google.com/machine-learning/problem-framing/good https://developers.google.com/machine-learning/problem-frami... "You should understand the problem well enough to list some potential solutions to test first to find the best model" and "it shouldn't be used for a problem that conventional programming can solve" like hard coding a symbolic rule.

rahimnathwani 7y ago
Unless it's fizzbuzz: https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/ https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/