Answers.Body: <p>I think, that the answer depends on the actual setting and parameters of the problem.</p>
  <h4>Lookup table</h4>
  <hr />
  <p>One needs to store the whole lookup table in the memory - say <code>N</code> points.</p>
  <p>The number of operations to extract elements depends on the way values are stored in the memory.</p>
  <p>In order to get a single value given the input <span class="math-container">$x$</span>, you need to perform <span class="math-container">$O(\log N)$</span> operations using a <em>binary search</em> in the sorted array.</p>
  <p>If the data is represented as <em>hast-table</em> - you need only <span class="math-container">$O(1)$</span> operations - complexity of computing the hash-function.</p>
  <h4>Neural network</h4>
  <hr />
  <p>Given some dependence, you fit a neural network <span class="math-container">$\hat{f}(x)$</span>, that approximates the function of interest (let us call it <span class="math-container">$f(x)$</span>).
  The approximation may not be exact, let us further assume, that some <span class="math-container">$\varepsilon$</span> is the allowed error, i.e:
  <span class="math-container">$$
  \Vert f(x) - \hat{f}(x)\Vert \leq \varepsilon \quad \forall x \in X
  $$</span>
  For every value of <span class="math-container">$x$</span> inside the range of values of interest, approximation deviates at most by <span class="math-container">$\varepsilon$</span>  from the true function.</p>
  <p>Depending on the complexity of the problem, this quality of approximation can be achieved by the simple architecture with few hidden units, or large network with large width or depth is required to perform an accurate approximation.</p>
  <p>In the setting, described by you, input and output are <span class="math-container">$1$</span>-dimensional. Let MLP with the dimensions of hidden units <span class="math-container">$(h_0, h_1, h_2, \ldots h_{L})$</span>, where <span class="math-container">$h_0 = h_{L+1} = 1$</span> and <span class="math-container">$L$</span> is the number of hidden layers, and the activation function <span class="math-container">$\sigma$</span> approximate the target dependence sufficiently well in the sense described above. NN is actually
  <span class="math-container">$$
  \hat{f}(x) = \sigma(\ldots \sigma (W_2 \sigma(W_1 x + b_1) + b_2))
  $$</span>
  Here <span class="math-container">$W_i$</span> are the weights and <span class="math-container">$b_i$</span> are the biases.
  Weigh matrices consist of <span class="math-container">$h_{i} h_{i+1}$</span>  elements and biases of <span class="math-container">$h_{i+1}$</span> elements.</p>
  <p>Then the network would require the following amount of memory to store parameters:
  <span class="math-container">$$
  \sum_{i=0}^{L} (h_{i} h_{i+1} + h_{i+1})
  $$</span>
  And the number of operations to compute output <span class="math-container">$y$</span> per single <span class="math-container">$x$</span> is:</p>
  <ul>
  <li><span class="math-container">$\sum_{i=0}^{L} h_{i} h_{i+1}$</span> multiplications</li>
  <li><span class="math-container">$\sum_{i=0}^{L} h_{i} h_{i+1}$</span> additions</li>
  <li><span class="math-container">$\sum_{i=0}^{L-1} h_{i} h_{i+1}$</span> evalutations of activation function <span class="math-container">$\sigma$</span></li>
  </ul>
  <h3>Conclusion</h3>
  <hr />
  <p>So, in order to decide, whether you need DNN model or not, you need to compare the computational complexity for the Lookup table and DNN. For some architecture, DNN may be more expensive, for others cheaper. It can be the case, that there is no DNN architecture, suitable for this task.</p>
  <p>For simple dependence and long timespan DNN can be helpful, whereas for small number of points and complicated dependence of <span class="math-container">$y$</span> on <span class="math-container">$x$</span> there is no point in trying to replace the Lookup table.</p>
  <p>For the case, presented in the picture seems, that there is no reason to use DNN since the hash-table will extract value very fast.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-04T09:19:03.917Z
Answers.Text: The lookup can be done in _O(1)_ in this case if we limit it to integer values.
Answers.UserDisplayName: Oliver Mason
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-04T09:23:43.820Z
Answers.Text: You say "Then the network would require the following amount of memory to store parameters ..." and then you show a formula, which seems to be correct (because you're computing the # of elements in the matrix by using the # of units in the previous and next layer and adding the number of biases), but, given that the amount of memory that you need to save a NN is proportional to the # of weights and biases, why not simply use the weight matrices $W_i$ and biases $b_i$ to clarify what you need to store? I guess you did this because it would also be beneficial to show the number of operations.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-04T09:27:26.397Z
Answers.Text: I am not sure if Oliver meant that you need O(1) space or time, but, if you use a hash table, you can retrieve elements in O(1) time complexity, so you don't need to first sort the table, which would require $n \log n$ and, then, once it's sorted, as you point out, it would only require $\log n$ to search, but this would still be probably unnecessary, because given $x$ (the key for the [hash table](https://en.wikipedia.org/wiki/Hash_table)) you can retrieve $y$ in constant time (at least on average; in the worst case it would be $n$).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-04T16:56:24.903Z
Answers.Text: Thanks @nbro and OliverMason for your comments, I'll update the answer
Answers.UserDisplayName: spiridon_the_sun_rotator
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-03T19:26:53.687Z
Answers.LastActivityDate: 2022-01-04T17:00:44.903Z
Answers.LastEditDate: 2022-01-04T17:00:44.903Z
Answers.UserDisplayName: spiridon_the_sun_rotator
Body: <p>Assuming one has collected the 24 pairs of the input-output datasets for a target system:</p>
  <p><a href="https://i.sstatic.net/w0kPE.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/w0kPE.png" alt="enter image description here" /></a></p>
  <p>One can create a simple lookup table to describe the input-output behavior and utilize this as a controller.</p>
  <p>One can also train a DNN model to learn the relationship.</p>
  <p>What is the benefit of using DNN in this case?</p>
  <p>In my view, for a DNN, one does not have to store the whole dataset for the lookup table. If one gives a new input value that is not included in the training dataset, the trained DNN would perform better, since, in the case of the lookup table, the predicted output is just an extrapolated value from the previously known output.</p>
  <p>Any other benefits that can justify using DNN?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-04T09:20:24.983Z
Comments.Text: 24 data points is too small a data set to use machine learning. Stick to a lookup table.
Comments.UserDisplayName: Oliver Mason
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-04T10:42:04.033Z
Comments.Text: Why are people voting to close this as "opinion-based"? Rather than downvoting  (or actually _just not upvoting_: yes, people are upvoting unclear questions, not sure why) other poor questions (that we have received), people are trying to close this question, which is not (necessarily) opinion-based.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-04T10:45:16.890Z
Comments.Text: One detail is missing from this post: are you expecting inputs outside of the inputs in the training dataset? If yes, with a table you cannot directly do that, so you cannot use the table. From this sentence "If one gives a new input value that is not included in the training dataset, the trained DNN would perform better, since, in the case of the lookup table, the predicted output is just an extrapolated value from the previously known output." it seems that you're expecting values not seen during training. In that case, how would you predict for those values with a table?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-04T11:38:58.360Z
Comments.Text: The idea was to apply a fitting curve approach along with the identified input-output pairs and use the interpolation/extrapolation methods to predict those values that are in the lookup table.
Comments.UserDisplayName: Joe
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-04T11:41:37.397Z
Comments.Text: @Joe Which interpolation/extrapolation methods do you have in mind? Please, edit your post to include these details directly there.
Comments.UserDisplayName: nbro
Tags: <neural-networks><deep-learning>
Title: What is the benefit of using a neural network instead of a look-up table in this case?
UserDisplayName: Joe
ThreadText: # What is the benefit of using a neural network instead of a look-up table in this case?
  
  (Asked by: username_0 on 2022-01-03)
  
  Assuming one has collected the 24 pairs of the input-output datasets for a target system:
  
  [![enter image description here](https://i.sstatic.net/w0kPE.png)](https://i.sstatic.net/w0kPE.png)
  
  One can create a simple lookup table to describe the input-output behavior and utilize this as a controller.
  
  One can also train a DNN model to learn the relationship.
  
  What is the benefit of using DNN in this case?
  
  In my view, for a DNN, one does not have to store the whole dataset for the lookup table. If one gives a new input value that is not included in the training dataset, the trained DNN would perform better, since, in the case of the lookup table, the predicted output is just an extrapolated value from the previously known output.
  
  Any other benefits that can justify using DNN?
  
  **Tags:** neural-networks, deep-learning
  > **Comments:**
  > **username_1**: 24 data points is too small a data set to use machine learning. Stick to a lookup table.  
  > **username_2**: Why are people voting to close this as "opinion-based"? Rather than downvoting  (or actually _just not upvoting_: yes, people are upvoting unclear questions, not sure why) other poor questions (that we have received), people are trying to close this question, which is not (necessarily) opinion-based.  
  > **username_2**: One detail is missing from this post: are you expecting inputs outside of the inputs in the training dataset? If yes, with a table you cannot directly do that, so you cannot use the table. From this sentence "If one gives a new input value that is not included in the training dataset, the trained DNN would perform better, since, in the case of the lookup table, the predicted output is just an extrapolated value from the previously known output." it seems that you're expecting values not seen during training. In that case, how would you predict for those values with a table?  
  > **username_0**: The idea was to apply a fitting curve approach along with the identified input-output pairs and use the interpolation/extrapolation methods to predict those values that are in the lookup table.  
  > **username_2**: @Joe Which interpolation/extrapolation methods do you have in mind? Please, edit your post to include these details directly there.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2022-01-03. Score: 0 | Accepted answer
  
  I think, that the answer depends on the actual setting and parameters of the problem.
  
  #### Lookup table
  
  ---
  
  One needs to store the whole lookup table in the memory - say `N` points.
  
  The number of operations to extract elements depends on the way values are stored in the memory.
  
  In order to get a single value given the input $x$, you need to perform $O(\log N)$ operations using a *binary search* in the sorted array.
  
  If the data is represented as *hast-table* - you need only $O(1)$ operations - complexity of computing the hash-function.
  
  #### Neural network
  
  ---
  
  Given some dependence, you fit a neural network $\hat{f}(x)$, that approximates the function of interest (let us call it $f(x)$).
  The approximation may not be exact, let us further assume, that some $\varepsilon$ is the allowed error, i.e:
  $$
  \Vert f(x) - \hat{f}(x)\Vert \leq \varepsilon \quad \forall x \in X
  $$
  For every value of $x$ inside the range of values of interest, approximation deviates at most by $\varepsilon$ from the true function.
  
  Depending on the complexity of the problem, this quality of approximation can be achieved by the simple architecture with few hidden units, or large network with large width or depth is required to perform an accurate approximation.
  
  In the setting, described by you, input and output are $1$-dimensional. Let MLP with the dimensions of hidden units $(h\_0, h\_1, h\_2, \ldots h\_{L})$, where $h\_0 = h\_{L+1} = 1$ and $L$ is the number of hidden layers, and the activation function $\sigma$ approximate the target dependence sufficiently well in the sense described above. NN is actually
  $$
  \hat{f}(x) = \sigma(\ldots \sigma (W\_2 \sigma(W\_1 x + b\_1) + b\_2))
  $$
  Here $W\_i$ are the weights and $b\_i$ are the biases.
  Weigh matrices consist of $h\_{i} h\_{i+1}$ elements and biases of $h\_{i+1}$ elements.
  
  Then the network would require the following amount of memory to store parameters:
  $$
  \sum\_{i=0}^{L} (h\_{i} h\_{i+1} + h\_{i+1})
  $$
  And the number of operations to compute output $y$ per single $x$ is:
  
  * $\sum\_{i=0}^{L} h\_{i} h\_{i+1}$ multiplications
  * $\sum\_{i=0}^{L} h\_{i} h\_{i+1}$ additions
  * $\sum\_{i=0}^{L-1} h\_{i} h\_{i+1}$ evalutations of activation function $\sigma$
  
  ### Conclusion
  
  ---
  
  So, in order to decide, whether you need DNN model or not, you need to compare the computational complexity for the Lookup table and DNN. For some architecture, DNN may be more expensive, for others cheaper. It can be the case, that there is no DNN architecture, suitable for this task.
  
  For simple dependence and long timespan DNN can be helpful, whereas for small number of points and complicated dependence of $y$ on $x$ there is no point in trying to replace the Lookup table.
  
  For the case, presented in the picture seems, that there is no reason to use DNN since the hash-table will extract value very fast.
  
  > **Comments:**
  > **username_1**: The lookup can be done in _O(1)_ in this case if we limit it to integer values.  
  > **username_2**: You say "Then the network would require the following amount of memory to store parameters ..." and then you show a formula, which seems to be correct (because you're computing the # of elements in the matrix by using the # of units in the previous and next layer and adding the number of biases), but, given that the amount of memory that you need to save a NN is proportional to the # of weights and biases, why not simply use the weight matrices $W_i$ and biases $b_i$ to clarify what you need to store? I guess you did this because it would also be beneficial to show the number of operations.  
  > **username_2**: I am not sure if Oliver meant that you need O(1) space or time, but, if you use a hash table, you can retrieve elements in O(1) time complexity, so you don't need to first sort the table, which would require $n \log n$ and, then, once it's sorted, as you point out, it would only require $\log n$ to search, but this would still be probably unnecessary, because given $x$ (the key for the [hash table](https://en.wikipedia.org/wiki/Hash_table)) you can retrieve $y$ in constant time (at least on average; in the worst case it would be $n$).  
  > **username_3**: Thanks @nbro and OliverMason for your comments, I'll update the answer  
  
  ---
  
  