0
$\begingroup$

I executed a linear search on an array containing all unique elements in range [1, 10000], sorted in increasing order with all search values i.e., from 1 to 10000 and plotted the runtime vs search value graph as follows:

enter image description here

Upon closely analysing the zoomed in version of the plot as follows:

enter image description here

I mainly have 2 questions:

1. Will piecewise regression will be a better idea to fit the data instead of linear regression, as the plot represents a step function (runtime is step function of search value) ?

2. In this case we are sure that when the step function breaks (or starts taking news values), we have NOISE, that may lower the accuracy of the model. So, should we consider this noisy data in our training dataset or exclude it and why ?

Clarification for what is NOISE : In the second screenshot, the runtime for some of the higher search values in lower than the runtime for lower search values and vice versa

Any suggestion is greatly appreciated!

$\endgroup$
6
  • 1
    $\begingroup$ Do you know in advance that the functional dependence should be linear or piecewise linear? If not, how do you know what's noise and what isn't? $\endgroup$ Commented Apr 2, 2020 at 2:03
  • $\begingroup$ Hi Dave! Here the Noise I am talking about is runtime for the search values when the step function is about to encounter breakpoints. In the second screenshot, the runtime for some of the higher search values in lower than the runtime for lower search values and vice versa. $\endgroup$ Commented Apr 2, 2020 at 2:16
  • $\begingroup$ You're missing the point of my question. Choosing the appropriate model depends on your assumptions about the underlying behavior that generates the data. $\endgroup$ Commented Apr 2, 2020 at 2:18
  • $\begingroup$ The fact that the higher search values should require higher runtime is palatable. But from the plot is evident that this is not true. Therefore I considered it as a noise in the dataset $\endgroup$ Commented Apr 2, 2020 at 2:23
  • 1
    $\begingroup$ Also, I don't know about the functional dependence. But what I understand from this usecase is that I can perform both linear and piecewise regression and check which one of them performs better on validation dataset. Correct me if I am thinking in wrong way. $\endgroup$ Commented Apr 2, 2020 at 2:25

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.