6
$\begingroup$

After reading a joke Fizz Buzz in Tensorflow, I am curious to know if it is possible to do such simple task correctly with deep learning. Any theoretical explanation for the reason we can or we cannot?

It is modulo operation, if we can do Fizz Buzz, maybe deep learning also can be used in number theory, such as finding prime numbers?

$\endgroup$
2
  • $\begingroup$ Please add the problem description into body of your question. $\endgroup$
    – Tim
    Jul 21 '18 at 15:19
  • 3
    $\begingroup$ It's a very, very big jump from computing a modulo operation to use in modern number theory. $\endgroup$ Jul 21 '18 at 19:25
8
$\begingroup$

As the author of the linked blog post, I am happy to say that (with the correct choice of hyperparameters and a little luck) Fizz Buzz can be completely learned by a neural network with one hidden layer.

I spent some time investigating why it works, and the reason is somewhat interesting. It hinges upon the binary representation of the input and the following observation:

  • if two numbers differ by a multiple of 15, then they belong to the same fizzbuzz "class" (as-is / fizz / buzz / fizzbuzz)

It turns out that there are a number of ways in which you can reverse two bits in a 10-digit binary number and get a number that differs by a multiple of 15. For example, if you start with some number x and turn on the 128 bit and turn off the 8 bit, you get x + 120. There are many other such examples.

And if you have a linear function of the bits that puts the identical weights on those two bits, it will produce the same output for x and x + 128.

As there are many such bit pairs, it turns out that the neural network basically

  • learns a bunch of equivalence classes (for example, one would contain x, x + 120, and a few other numbers), and
  • "memorizes" the correct answer for each equivalence class

And so it turns out that when you train the model on the numbers 101 to 1023, you've got enough equivalence classes to predict correctly on 1 to 100.

(This is not formal, of course, this is just a high-level summary of what I learned when I investigated the network.)

--

As to your question about finding prime numbers, I'd be surprised if an approach like this worked. My sense is that the nice "same modulo 15" structure of this problem is what makes the neural net work, and it's hard to think of anything analogous for e.g. finding prime numbers.

$\endgroup$
0
$\begingroup$

Let me answer the question in a meme way.

Why (always) deep learning? All neural nets do is linear regression (x*w+b) with some non-linearity around the (intermediate) response.

deep or derp

Lets talk machine learning, better yet, optimization. The obvious general class of problems you are referring to is function approximation (not regression per se). So, why not to use method that was developed to do exactly this: writing programs. In theory, yes, you can use 'artificial intelligence' methods to create programs and one of them, given enough data and time, can theoretically be FizzBuzz. Or a programm that computes prime numbers (and that program could be theoretically the same when written by a human). -- No deep learning here --.

Learning from data

Well, can we learn from data? Yes, we can. But first we need to understand data and to engineer some features. Because only one numeric feature is not expressive enough... (for now).

Some code incoming:

library(tidyverse)

theData <- data_frame(a = as.double(1:100),
                      a3 = as.double(a %% 3 == 0),
                      a5 = as.double(a %% 5 == 0),
                      cl = case_when((a3 > 0) & (a5 > 0) ~ 'FizzBuzz',
                                     a3 > 0 ~ 'Fizz',
                                     a5 > 0 ~ 'Buzz',   
                                     TRUE ~ 'Number')) %>%
  mutate(cl = factor(cl))

Now we have a numerical feature a (numbers) and a3 and a5 te help with the decision ...

enter image description here

... tree. (╯°□°)╯︵ ┻━┻ again not deep learning here. But a stacked model: first level is DT and scond level is (using Viola-Jones-Cascades or simple filter on the Number response) a plain old linear regression with the solution $y=a$.

The DT first:

treeModel <- rpart::rpart(cl ~ ., theData, 
                          control = rpart::rpart.control(minsplit = 5))
rattle::fancyRpartPlot(treeModel, caption = '')

enter image description here

THAT IS CRAZY! A simple decision tree learned FizzBuzz! But did it? Apply some test data:

testData <- data_frame(a = as.double(200:300),
                      a3 = as.double(a %% 3 == 0),
                      a5 = as.double(a %% 5 == 0),
                      cl = case_when((a3 > 0) & (a5 > 0) ~ 'FizzBuzz',
                                     a3 > 0 ~ 'Fizz',
                                     a5 > 0 ~ 'Buzz',   
                                     TRUE ~ 'Number'))

predictions <- predict(treeModel, testData, type = 'class')
table(testData$cl, predictions) 


        predictions
         Buzz Fizz FizzBuzz Number
Buzz       14    0        0      0
Fizz        0   27        0      0
FizzBuzz    0    0        7      0
Number      0    0        0     53

Perfect on test set for numbers 200 to 300!

Well, the second layer is easy:

lmModel <- lm(arep ~ a - 1, mutate(theData, arep = a))

The error estimating the number is

testData %>%
  mutate(pred = predict(treeModel, ., type = 'class')) %>%
  filter(pred == 'Number') %>%
  mutate(apred = predict(lmModel, .),
         error = a - apred) %>%
  pull(error) %>%
  summary()

     Min.   1st Qu.    Median      Mean   3rd Qu.      Max. 
5.684e-14 5.684e-14 5.684e-14 5.684e-14 5.684e-14 5.684e-1

... well very close to 0. Tada!

We learned FizzBuzz from data!

Derp learning

Probably you can do the same stuff with deep learning. You can also do stacked models with LSTM layers and convolution (ya know, because of modulo 3 and 5), and with a huge amount of data you may have a chance to generalize some patterns... yeah... no.

So hope this answer helps to clarify that yes it is possible. And no, you don't need deep learning to do the job. And now, from a single feature a even deep learning will not be able to learn FizzBuzz.

As for prime numbers... if you compute/engineer as many features as there are prime numbers, you can learn them from data, too. ¯_(ツ)_/¯

$\endgroup$
5
  • 1
    $\begingroup$ Honestly, it needs just a few lines of if-else code, so any machine learning is overkill... As I understood the question, it was rather if deep learning can not fail it as the example failed (obviously yes). $\endgroup$
    – Tim
    Jul 21 '18 at 19:38
  • $\begingroup$ this doesn't answer the question $\endgroup$ Jul 22 '18 at 1:48
  • $\begingroup$ @aaaaaa because the question is specifically about deep learning? $\endgroup$
    – Drey
    Jul 22 '18 at 3:57
  • $\begingroup$ the Q is not "how to solve this problem" but how can ML help and whether it can help. Great, you showed the Whole Internet that you can write FizzBuzz program. That is not the point. Your only ref to actual question is "with a huge amount of data you may have a chance to generalize some patterns... yeah... no." $\endgroup$ Jul 22 '18 at 4:49
  • $\begingroup$ So what's again wrong with showing that and how ML can solve it? Or GP and DT is not ML? $\endgroup$
    – Drey
    Jul 22 '18 at 5:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.