0
$\begingroup$

Assuming one has collected the 24 pairs of the input-output datasets for a target system:

enter image description here

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?

$\endgroup$
5
  • $\begingroup$ 24 data points is too small a data set to use machine learning. Stick to a lookup table. $\endgroup$ Jan 4 at 9:20
  • $\begingroup$ 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. $\endgroup$
    – nbro
    Jan 4 at 10:42
  • $\begingroup$ 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? $\endgroup$
    – nbro
    Jan 4 at 10:45
  • $\begingroup$ 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. $\endgroup$
    – Joe
    Jan 4 at 11:38
  • $\begingroup$ @Joe Which interpolation/extrapolation methods do you have in mind? Please, edit your post to include these details directly there. $\endgroup$
    – nbro
    Jan 4 at 11:41
0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ The lookup can be done in O(1) in this case if we limit it to integer values. $\endgroup$ Jan 4 at 9:19
  • $\begingroup$ 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. $\endgroup$
    – nbro
    Jan 4 at 9:23
  • $\begingroup$ 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) you can retrieve $y$ in constant time (at least on average; in the worst case it would be $n$). $\endgroup$
    – nbro
    Jan 4 at 9:27
  • $\begingroup$ Thanks @nbro and OliverMason for your comments, I'll update the answer $\endgroup$ Jan 4 at 16:56

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.