Citation

C. Zhou, M. Prabhushankar, and G. AlRegib, ”Perceptual Quality-based Model
Training under Annotator Label Uncertainty,” in International Meeting for
Applied Geoscience & Energy (IMAGE) 2023, Houston, TX, Aug. 28-Sept. 1, 2023.

DOI

https://doi.org/10.1190/image2023-3916384.1

Review

Date of acceptance: May 16, 2023
Date of presentation: August 29, 2023

Codes

https://github.com/olivesgatech/Ramifications-HLU

Bib

@inproceedings{zhou2023perceptual,
title={Perceptual quality-based model training under annotator label
uncertainty},
author={Zhou, Chen and Prabhushankar, Mohit and AlRegib, Ghassan},
booktitle={Third International Meeting for Applied Geoscience & Energy
Expanded Abstracts},
pages={965–969},
year={2023},
doi = {10.1190/image2023-3916384.1},
URL = {https://library.seg.org/doi/abs/10.1190/image2023-3916384.1},
eprint = {https://library.seg.org/doi/pdf/10.1190/image2023-3916384.1},
organization={Society of Exploration Geophysicists and the American
Association of Petroleum Geologists}
}

Keywords

Annotator Label Disagreement, Perceptual Quality Assessments, Prediction
Uncertainty, Seismic Interpretation

Contact

<EMAIL_ADDRESS>OR<EMAIL_ADDRESS>OR<EMAIL_ADDRESS>
https://alregib.ece.gatech.edu/

Example Dellinger & Fomel Perceptual quality-based model training under
annotator label uncertainty

# Perceptual quality-based model training under annotator label uncertainty

Chen Zhou11footnotemark: 1 Mohit Prabhushankar  and Ghassan AlRegib  Center
for Energy and Geo Processing (CeGP)  School of Electrical and Computer
Engineering  Georgia Institute of Technology  {chen.zhou  mohit.p
<EMAIL_ADDRESS>
###### Abstract

Annotators exhibit disagreement during data labeling, which can be termed as
annotator label uncertainty. Annotator label uncertainty manifests in
variations of labeling quality. Training with a single low-quality annotation
per sample induces model reliability degradations. In this work, we first
examine the effects of annotator label uncertainty in terms of the model’s
generalizability and prediction uncertainty. We observe that the model’s
generalizability and prediction uncertainty degrade with the presence of low-
quality noisy labels. Meanwhile, our evaluation of existing uncertainty
estimation algorithms indicates their incapability in response to annotator
label uncertainty. To mitigate performance degradation, prior methods show
that training models with labels collected from multiple independent
annotators can enhance generalizability. However, they require massive
annotations. Hence, we introduce a novel perceptual quality-based model
training framework to objectively generate multiple labels for model training
to enhance reliability, while avoiding massive annotations. Specifically, we
first select a subset of samples with low perceptual quality scores ranked by
statistical regularities of visual signals. We then assign de-aggregated
labels to each sample in this subset to obtain a training set with multiple
labels. Our experiments and analysis demonstrate that training with the
proposed framework alleviates the degradation of generalizability and
prediction uncertainty caused by annotator label uncertainty.

##  1 Introduction

Raw data usually comes with separate annotations collected from multiple
imperfect human annotators. These separate labels lead to a lack of consensus
when they disagree with each other. For instance, the authors in Bond et al.,
(2007) demonstrate different interpretations by multiple geophysicists on the
same data, motivating the necessity to study such disagreement and its impact
on hydrocarbon predictability. The lack of consensus between human annotations
exists in all data labeling processes and can be critical in various
applications, e.g., image classification Wei et al., (2021), medical diagnosis
Ju et al., (2022); Prabhushankar et al., (2022), and seismic interpretation
Wang and Chen, (2019); Benkert et al., (2022), as shown in Figure 1. We term
this disagreement between human annotators as _annotator label uncertainty_.

Annotator label uncertainty induces degradation of label quality within
machine learning model development. Training with a single low-quality label
per sample leads to model reliability degradation in terms of generalizability
and prediction uncertainty. In image classification, models can overfit to
noisy training labels, leading to incorrect class prediction and confidence
degradation. In seismic fault prediction, low-quality labels manifest in more
diverse modes. There can be false positive labels due to unclear structures.
Additionally, substantial faults might be unlabeled due to the difficulty in
precisely marking the endpoints of fault picks. These low-quality labels can
lead to inaccurate and unconfident predictions by the model.

In order to address the model reliability degradation caused by annotator
label uncertainty, the authors in Wei et al., (2022) demonstrate that training
with multiple de-aggregated human labels can be beneficial. However,
collecting multiple annotations per sample from various independent annotators
can be challenging and expensive. To avoid collecting massive subjective
manual annotations with disagreement, we aim to generate multiple de-
aggregated labels in an objective manner for model training. The cause of
certain data samples that exhibit annotator label uncertainty relates to the
difficulty in perception by annotators. In image classification, perceptual
quality assessment Moorthy and Bovik, (2011); Temel et al., (2016); Seijdel et
al., (2020); Prabhushankar et al., (2017) measures such difficulty. In the
geophysics domain, seismic attributes, e.g., gradients of texture (GoT), and
seismic saliency, can be utilized to create objective seismic data quality
assessments. In this study, we study and tackle annotator label uncertainty in
image classification. We propose a perceptual quality-based multi-label
training scheme to tackle the model reliability degradation caused by
annotator label uncertainty. Specifically, we utilize statistical regularities
of visual signals to target the samples that show a high degree of label
uncertainty. For each of these targeted samples, we then assign different
labels to perform multi-label training.

Figure 1: The lack of consensus between annotators exists in all data labeling
processes across various fields. Left: annotators assign different labels to
classify the ambiguous image. Middle: disagreement between doctors in medical
diagnosis. Right: interpreters provide different annotations during seismic
interpretation.

We examine the effects of annotator label uncertainty and demonstrate that the
model’s reliability degradation can be tackled by our proposed perceptual
quality-based multi-label training. Specifically, we assess the models trained
on four label conditions per sample, including a) a single clean label, b) a
single noisy label, c) multiple labels collected from different annotators,
and d) multiple labels generated objectively by our framework. Compared to the
model trained with ideal clean labels, the model trained with noisy labels
exhibits higher prediction uncertainty and lower classification accuracy. Our
proposed framework avoids model fitting to incorrect sample-label pairs
thereby enhancing generalizability and uncertainty. Furthermore, our approach
does not require massive manual annotations.

The main contributions of our work include: ($i$) examining the effects of
annotator label uncertainty in terms of the model’s generalizability and
prediction uncertainty. ($ii$) identifying the limitations of certain existing
uncertainty estimation algorithms in response to annotator label uncertainty.
($iii$) introducing a novel perceptual quality-based multi-label training
framework to tackle the degradation of generalizability and prediction
uncertainty caused by annotator label uncertainty, while not requiring massive
human annotations.

## Method

Figure 2: Diagram of perceptual quality-based multi-label training framework.
We sample a subset $D_{pool}$ consisting of low-quality samples to perform
multi-label training in an objective manner. Our framework does not require
massive human annotations. $D$ denotes the initial training dataset.
$D_{pool}$ denotes the subset targeted by perceptual quality assessments.
$x_{i}$ denotes a sample in $D_{pool}$. $y_{i}^{1},y_{i}^{2},...,y_{i}^{K}$
denote multiple labels associated with $x_{i}$.

In this section, we present a novel perceptual quality-based model training
scheme that tackles model reliability degradation caused by annotator label
uncertainty. At a high level, our framework objectively injects multiple
labels into a training subset targeted by perceptual quality assessments.

The overall diagram of our proposed framework is illustrated in Figure 2.
Consider a model, an initial training dataset $D$. We aim to inject multiple
training labels into a subset $D_{pool}$ that initially contains an underlying
single noisy annotation per sample. One can determine $D_{pool}$ by examining
the disagreement of annotations collected from multiple independent
annotators. However, it is challenging and expensive to collect massive manual
annotations. The cause of certain samples exhibiting annotator label
uncertainty relates to the difficulty of human perception. Objective
perceptual quality assessment Moorthy and Bovik, (2011); Temel et al., (2016);
Seijdel et al., (2020); Prabhushankar et al., (2017) measures such difficulty.
Hence, we propose to exploit perceptual data quality assessments to
objectively determine this subset. We compute the perceptual quality scores of
all samples from $D$, which reflect the perception difficulty during labeling.
Particularly, we employ BRISQUE Mittal et al., (2012) algorithm to obtain
perceptual quality scores of all training data. Given an image sample, BRISQUE
Mittal et al., (2012) exploits its spatial statistics of locally normalized
luminance coefficients to quantify the perceptual quality. The samples with
low-quality scores exhibit relatively high annotator label uncertainty and are
targeted as $D_{pool}$. Given that $D_{pool}$ is determined, we assign
multiple de-aggregated labels to mimic annotator disagreement. Moderately
uncertain samples are likely to be associated with semantically relevant noisy
labels, instead of random labels that are completely semantically irrelevant.
Hence, we fit a $K$-means model on the training data and assign multiple
labels, i.e., $y_{i}^{1},...,y_{i}^{k},k\in\\{1,2,...,K\\}$ to each sample
$x_{i}\in D_{pool}$ based on its feature distance to the clustering centroids.
$K$ denotes the cardinality of the set of multiple labels. The remaining
samples are associated with clean labels. We combine $D_{pool}$ with the
remaining clean data to train the model. Note that for a sample $x_{i}\in
D_{pool}$, the model is given its $k$ replications, each associated with one
of the labels drawn from $y_{i}^{1},...,y_{i}^{k}$.

##  2 Experiments

We first examine the effects of noisy annotations on the model’s reliability
in terms of generalizability and prediction uncertainty. We then show the
efficacy of the proposed framework in enhancing the model reliability under
annotator label uncertainty.

In order to examine the effects of noisy annotations, we compare the model’s
generalizability and prediction uncertainty between two training label
conditions, a) training with a single clean label per sample, and b) training
with a single noisy human label per sample. Specifically, we use the original
CIFAR-10 Krizhevsky et al., (2009) training images for both training label
conditions, and use the noisy human annotations in CIFAR-10-N Wei et al.,
(2021) for noisy label condition b). Following the uncertainty evaluation
protocols in prior works Gal and Ghahramani, (2016); Hendrycks et al., (2019);
Zhou and Levine, (2021); Prabhushankar and AlRegib, (2022), we assess
predictive uncertainty and generalizability of a vanilla ResNet18 (Vanilla),
Monte Carlo (MC) Dropout Gal and Ghahramani, (2016), and deterministic
uncertainty quantification (DUQ) Van Amersfoort et al., (2020) under two types
of distribution shifts, including rotation and corruption. For all models, we
use the same base ResNet-18 He et al., (2016). We measure generalizability and
prediction uncertainty via accuracy and entropy Shannon, (1948), respectively.
We summarize the prediction uncertainty and generalizability of these models
on the test sets of CIFAR-10-Rotations and CIFAR-10-C Hendrycks and
Dietterich, (2019) in the first two rows (Clean and Human Noise) of both the
top and bottom parts in Table 1. We observe significant degradation in both
prediction uncertainty and accuracy by comparing the performance of the models
trained with clean labels, and noisy human annotations. Besides, we find that
MC Dropout and DUQ models are not able to tackle annotator label uncertainty
since they do not enhance the performance of uncertainty measures compared to
the vanilla network.

We then verify the efficacy of the proposed framework in tackling the
uncertainty and generalizability degradation. The core of the framework is to
construct the uncertain training subset $D_{pool}$ with multiple labels. We
ensure that the number of samples in $D_{pool}$ is the same as the number of
samples with noisy labels in CIFAR-10-N. Specifically, we rank all training
samples in $D$ via perceptual quality statistics and select the top $40\%$ of
uncertain samples to construct $D_{pool}$. Furthermore, we ensure that the
level of label uncertainty in the constructed $D_{pool}$ is the same as that
of human labeling. All samples in $D_{pool}$ are associated with maximum $K=3$
labels. For each sample in $D_{pool}$ with the top $10\%$ uncertainty measured
by perceptual quality scores, we assign at least two noisy labels. The
remaining $30\%$ of samples are assigned with one noisy label. In this way, we
construct $D_{pool}$ to have the same overall label disagreement as that of
single noisy training label condition with the real-world noisy annotations in
CIFAR-10-N.

Overall, the degradation in prediction uncertainty under the noisy label
condition can be mitigated by our perceptual quality-based multi-label
training framework as shown in the last row of both the top and bottom parts
in Table 1. In addition to mitigating the increase in predictive uncertainty,
training with our framework also enhances generalizability as measured in
classification accuracy. These observations validate that our proposed
framework mitigates the negative effects caused by annotator label
uncertainty. We also include the results of an annotator-based multi-label
training scheme using real-world manual annotations collected from multiple
independent annotators Wei et al., (2021) as shown in the third row in Table
1. While training with multiple manual labels collected from different
annotators achieves the highest accuracy, it requires massive human
annotations and does not show better enhancement in prediction uncertainty.
This observation confirms the efficacy of utilizing perceptual quality-based
multi-label training to enhance the model’s prediction uncertainty.

Table 1: Evaluation results on CIFAR-10-Rotations (top part) and CIFAR-10-C (bottom part). The three uncertainty quantification models are assessed against different training label conditions. Overall, our proposed perceptual quality-based multi-label training framework mitigates the degradation of generalizability and prediction uncertainty caused by annotator label uncertainty, while avoiding massive manual annotations. All models are trained with the original CIFAR-10 training images but with different labels. Training Label Conditions | CIFAR-10-Rotations
---|---
Vanilla | MC Dropout | DUQ
| Entropy
---
$(\downarrow)$
| Accuracy
---
$(\uparrow)$
| Entropy
---
$(\downarrow)$
| Accuracy
---
$(\uparrow)$
| Entropy
---
$(\downarrow)$
| Accuracy
---
$(\uparrow)$
Effects of Annotator Label Uncertainty
Clean | 0.675 | 0.446 | 0.696 | 0.446 | 1.071 | 0.427
Human Noise | 2.398 | 0.355 | 2.413 | 0.350 | 1.697 | 0.282
| Multi-label Training Frameworks
Human-based | 2.069 | 0.392 | 2.058 | 0.394 | 2.068 | 0.379
Perceptual quality-based (ours) | 1.264 | 0.362 | 1.284 | 0.357 | 1.569 | 0.350
Training Label Conditions | CIFAR-10-C
Vanilla | MC Dropout | DUQ
| Entropy
---
$(\downarrow)$
| Accuracy
---
$(\uparrow)$
| Entropy
---
$(\downarrow)$
| Accuracy
---
$(\uparrow)$
| Entropy
---
$(\downarrow)$
| Accuracy
---
$(\uparrow)$
Effects of Annotator Label Uncertainty
Clean | 0.384 | 0.750 | 0.396 | 0.746 | 0.829 | 0.686
Human Noise | 2.172 | 0.640 | 2.184 | 0.634 | 1.563 | 0.470
| Multi-label Training Frameworks
Human-based | 1.855 | 0.702 | 1.848 | 0.706 | 1.863 | 0.664
Perceptual quality-based (ours) | 1.222 | 0.580 | 1.243 | 0.580 | 1.496 | 0.540

##  3 Conclusions

In this work, we first examine the effects of annotator label uncertainty on
the model’s generalizability and prediction uncertainty. Meanwhile, we observe
that certain existing uncertainty quantification algorithms are incapable of
responding to annotator label uncertainty. We introduce the concept of
exploiting perceptual quality assessments, which objectively quantify
annotation quality, within a multi-label training framework to enhance
generalizability and prediction uncertainty under annotator label uncertainty.
The experiments on an image classification dataset validate that our proposed
training framework can improve classification accuracy and prediction entropy
of all three uncertainty quantification models with the presence of noisy
labels while avoiding the collection of massive manual annotations. For
seismic-related applications, we suggest that the concept of perceptual
quality-based multi-label training can be applied to the geophysics domain by
exploiting seismic attributes. Specifically, one can utilize seismic
attributes, e.g., grey-level co-occurrence matrix (GLCM) texture, gradients of
texture (GoT), and seismic saliency, to create objective seismic data quality
assessments. The seismic quality assessments can be utilized to enhance the
model’s reliability under annotator label uncertainty without requiring
massive annotations.

##  4 ACKNOWLEDGMENTS

This work is supported by the ML4Seismic Industry Partners at Georgia Tech.

## References

  * Benkert et al., (2022) Benkert, R., O. J. Aribido, and G. AlRegib, 2022, Example forgetting: A novel approach to explain and interpret deep neural networks in seismic interpretation: IEEE Transactions on Geoscience and Remote Sensing.
  * Bond et al., (2007) Bond, C. E., A. D. Gibbs, Z. K. Shipton, S. Jones, et al., 2007, What do you think this is¿‘conceptual uncertainty”in geoscience interpretation: GSA today, 17, 4.
  * Gal and Ghahramani, (2016) Gal, Y., and Z. Ghahramani, 2016, Dropout as a bayesian approximation: Representing model uncertainty in deep learning: international conference on machine learning, PMLR, 1050–1059.
  * He et al., (2016) He, K., X. Zhang, S. Ren, and J. Sun, 2016, Deep residual learning for image recognition: Proceedings of the IEEE conference on computer vision and pattern recognition, 770–778.
  * Hendrycks and Dietterich, (2019) Hendrycks, D., and T. Dietterich, 2019, Benchmarking neural network robustness to common corruptions and perturbations: arXiv preprint arXiv:1903.12261.
  * Hendrycks et al., (2019) Hendrycks, D., N. Mu, E. D. Cubuk, B. Zoph, J. Gilmer, and B. Lakshminarayanan, 2019, Augmix: A simple data processing method to improve robustness and uncertainty: arXiv preprint arXiv:1912.02781.
  * Ju et al., (2022) Ju, L., X. Wang, L. Wang, D. Mahapatra, X. Zhao, Q. Zhou, T. Liu, and Z. Ge, 2022, Improving medical images classification with label noise using dual-uncertainty estimation: IEEE transactions on medical imaging.
  * Krizhevsky et al., (2009) Krizhevsky, A., G. Hinton, et al., 2009, Learning multiple layers of features from tiny images.
  * Mittal et al., (2012) Mittal, A., A. K. Moorthy, and A. C. Bovik, 2012, No-reference image quality assessment in the spatial domain: IEEE Transactions on image processing, 21, 4695–4708.
  * Moorthy and Bovik, (2011) Moorthy, A. K., and A. C. Bovik, 2011, Blind image quality assessment: From natural scene statistics to perceptual quality: IEEE transactions on Image Processing, 20, 3350–3364.
  * Prabhushankar and AlRegib, (2022) Prabhushankar, M., and G. AlRegib, 2022, Introspective learning: A two-stage approach for inference in neural networks: arXiv preprint arXiv:2209.08425.
  * Prabhushankar et al., (2022) Prabhushankar, M., K. Kokilepersaud, Y.-y. Logan, S. T. Corona, G. AlRegib, and C. Wykoff, 2022, Olives dataset: Ophthalmic labels for investigating visual eye semantics: arXiv preprint arXiv:2209.11195.
  * Prabhushankar et al., (2017) Prabhushankar, M., D. Temel, and G. AlRegib, 2017, Ms-unique: Multi-model and sharpness-weighted unsupervised image quality estimation: Electronic Imaging, 2017, 30–35.
  * Seijdel et al., (2020) Seijdel, N., S. Jahfari, I. I. Groen, and H. S. Scholte, 2020, Low-level image statistics in natural scenes influence perceptual decision-making: Scientific reports, 10, 1–9.
  * Shannon, (1948) Shannon, C. E., 1948, A mathematical theory of communication: The Bell system technical journal, 27, 379–423.
  * Temel et al., (2016) Temel, D., M. Prabhushankar, and G. AlRegib, 2016, Unique: Unsupervised image quality estimation: IEEE signal processing letters, 23, 1414–1418.
  * Van Amersfoort et al., (2020) Van Amersfoort, J., L. Smith, Y. W. Teh, and Y. Gal, 2020, Uncertainty estimation using a single deep deterministic neural network: International conference on machine learning, PMLR, 9690–9700.
  * Wang and Chen, (2019) Wang, F., and S. Chen, 2019, Residual learning of deep convolutional neural network for seismic random noise attenuation: IEEE Geoscience and Remote Sensing Letters, 16, 1314–1318.
  * Wei et al., (2021) Wei, J., Z. Zhu, H. Cheng, T. Liu, G. Niu, and Y. Liu, 2021, Learning with noisy labels revisited: A study using real-world human annotations: arXiv preprint arXiv:2110.12088.
  * Wei et al., (2022) Wei, J., Z. Zhu, T. Luo, E. Amid, A. Kumar, and Y. Liu, 2022, To aggregate or not? learning with separate noisy labels: arXiv preprint arXiv:2206.07181.
  * Zhou and Levine, (2021) Zhou, A., and S. Levine, 2021, Amortized conditional normalized maximum likelihood: Reliable out of distribution uncertainty estimation: International Conference on Machine Learning, PMLR, 12803–12812.


∎

11institutetext: M. Agenis-Nevers 22institutetext: Independent Researcher,
Epicentre Factory, Clermont-Ferrand, France
22email<EMAIL_ADDRESS>33institutetext: N. D. Bokde 44institutetext:
Department of Engineering - Renewable Energy and Thermodynamics, Aarhus
University, Denmark
44email<EMAIL_ADDRESS>55institutetext: z. M. Yaseen
66institutetext: Sustainable Developments in Civil Engineering Research Group,
Faculty of Civil Engineering, Ton Duc Thang University, Ho Chi Minh City,
Vietnam
66email<EMAIL_ADDRESS>77institutetext: M. Shende 88institutetext:
Government College of Engineering, Nagpur, India

# An empirical estimation for time and memory algorithm complexities: Newly
developed R package

Marc Agenis-Nevers  Neeraj Dhanraj Bokde  Zaher Mundher Yaseen  Mayur Shende

(Received: date / Accepted: date)

###### Abstract

When an algorithm or a program runs on a computer, it requires some resources.
The complexity of an algorithm is the measure of the resources, for some
input. These complexities are usually space and time. The subject of the
empirical computational complexity has been studied in the research. This
article introduces GuessCompx which is an R package that performs an empirical
estimation on the time and memory complexities of an algorithm or a function,
and provides a reliable, convenient and simple procedure for estimation
process. It tests multiple increasing-sizes samples of the user’s data and
attempts to fit one of seven complexity functions: _O(N), O(N^2), O(log(N))_ ,
etc. In addition, based on the best fit procedure using leave one out-mean
squared error (LOO-MSE), it predicts the full computation time and memory
usage on the whole dataset. Together with this results, a plot and a
significance test are returned. Complexity is assessed with regard to the
user’s actual dataset through its size (and no other parameter). This article
provides several examples demonstrating several cases (e.g., distance
function, time series and custom function) and optimal parameters tuning.

###### Keywords:

time complexitymemory complexityempirical approach R package algorithm
complexity

##  1 Introduction

Complexity of an algorithm is a measure of resources amount the algorithm
needs to run the completion, for a given input [1][2]. Usually, the resources
of an algorithm require either space or time, which represent two types of
complexities [3] [4]. The time complexity is the total amount of time required
by an algorithm to complete its execution [5]. The running time of an
algorithm may differ for the same input sizes, depending on the type of data
[6; 7; 8]. For instance, in bubble sort algorithm, if the input array is
already sorted then the running time of the algorithm will be lower [9]. This
is what is so called the best case complexity. Similarly; if the input list is
in reverse order, the algorithm will take the maximum time capacity, which is
called worst case complexity. If the input list is neither sorted nor
reversed, then the running time is less than worst case but more than best
case: this is the average case complexity. Since an algorithm cannot require
more time than the worst case scenario, this scenario is set to be the
reference complexity [10][11]. Since this function is generally difficult to
compute exactly, and the running time for small inputs is usually not
consequential, one commonly focuses on the behavior of the complexity when the
input size increases. This is the asymptotic behavior of the complexity.
Hence, the time complexity is commonly expressed using big O notation,
typically _O(N), O(NlogN), O(N^2), O(2^N)_ , etc., where N is the input size
in units of bits needed to represent the input [12].

Most mathematical problem can be solved with different algorithms [13]. These
algorithms may include complex optimization [14; 15; 16], forecasting [17;
18], data decomposition [19] or searching methodologies [20]. These algorithms
do not need the same amount of resources and can have different complexities.
The algorithm that uses less memory and completes in less time is, by
definition, more efficient. By studying the complexities of different
algorithms, it can be determined the most efficient algorithm for a given
input.

In the specific field of data science, it has been witnessed an exponential
growth of datasets size and required computational power [21; 22]. Some review
researches such as [23] gave an overview of the statistical methods for big
data, mentions the words “computational complexity” or “computational
efficiency” no less than 10 times. However, while designing new algorithms,
their combinations, or even simply data treatments or data streams, the
engineers have a constant need to check the computational complexity of their
code [24]. A great amount of time can be lost in this process, while waiting
for a new computation to complete without knowing the exact time required: one
minute, one hour, several weeks? Is it even worth waiting? Having a way to
estimate the execution time of a new piece of code, before running it in full
scale, could be a critical time-saving tool.

In recent years, the possibility of new and efficient computational models
including empirical views of complexity theory is recommended as a part of
computer science [25]. The importance of this view and its consequences are
discussed in detail in [26]. Further, the need of the empirical methods for
complexity computation is convinced by the comment: “ _In particular, the
existence of a function computable by a machine but not by an algorithm would
imply that some mathematical problem are solvable by empirical processes
without any mathematical method_ ” [26; 25; 27]. With this motivations, there
are a couple of tools to estimate computational complexity empirically as
discussed in the next paragraph along with their limitations and drawbacks.
This paper has proposed GuessCompx, a new R package to estimate the
computational complexity accurately with minimum efforts. The subsequent
sections are dedicated to description and demonstration of the package.

According to [28], “ _it takes significant amount of effort to judge the
complexity of an algorithm. Various manual methods are used till now to get
calculate the time complexities such as Master Method, using control flow
graph, but all of them remain tedious to work with and owing to their manual
nature, have limitations and are prone to error_ ”. Recently, manual and exact
methods have started to be challenged by so-called empirical methods, that try
to give an estimate of the complexity by observing the code being run several
times. Goldsmith et al. [29] proposed a tool in C/C++ language named Trend
Profiler (trend-prof) to construct models of empirical computational
complexity that estimate how many times each basic block in a program runs;
statistical modeling is applied, in the form of linear, polynomial or power
terms, the models for the different blocks of code are eventually combined to
predict the final execution time or to report performance problems to the
developer. The authors don’t directly measure CPU-time and justify this choice
by the desire to avoid the replicability problem. Modeling code-blocks is more
robust but has a major drawback: it needs to access the source code of the
target function and to ask some manual-input features like the number of
nodes, characters, lines, etc. More recently, [28] introduced a concept of
predicting time complexity using gradient boosted trees in a supervised manner
in C++ language and Python. The authors reached exceptional prediction
capability by treating the problem not as a regression anymore but as a
classification into 7 complexity families. The algorithm has to be executed in
a controlled environment with a high number of replications, to retrieve 6
features linked with execution time and hardware information (clock time,
number of processors, etc.), but the technique also gave good results using
only two of them: the execution time and processor speed. Unfortunately, the
code and the models are not directly applicable (e.g., package or library) for
a data scientist to use in his daily work. Eventually, apart from those two
works, the state of the art concerning memory complexity estimation seems to
be particularly sparse.

This research is devoted on the proposition of GuessCompx package [30], which
enables the R users to empirically estimate the computation time and memory
usage of any algorithm prior to the final implementation. As per author’s
knowledge, this is the first package proposal in CRAN which discusses
empirical estimation of algorithm complexity.

In the GuessCompx package, the complexity estimation is only defined with
regard to N (being the number of rows of the data). Many other factors could
be thought of that influence complexity, such as: data dimension, number of
features, time horizon for recursive forecasting, sparsity of the data,
possibility of parallel computing, and eventually interactions between two or
more of those factors. Such influences are out of scope of the GuessCompx
package, but could be investigated in future versions. Details on the subject
of algorithmic complexity can be found at [31].

The popular complexity functions have implemented over the literature are
_O(1), O(N), O(N^2), O(N^3), O(N^0.5), O(log(N)), O(N*log(N))_. Those
functions are representative of the most commonly found complexity functions
and were chosen to be similar as those tested in [28], excepted for
_O(N*N^0.5)_ which was replaced by the constant function.

It is worth to highlight that the salient features of the proposed GuessCompx
package in comparison with the existed techniques are:

  * •

The GuessCompx is a user-friendly tool to estimate the empirical complexity of
functions. The complexities of algorithm or functions are achievable with a
single step of code and minimum efforts.

  * •

The complexity accuracy with GuessCompex can be very high and it is examined
for some popular algorithms with known complexities in the subsequent section.
The accuracy can further be improved with fine-tuning the several input
parameters used in the package, such as max.time, start.size, replicates, etc.

  * •

Apart from accuracy, another major advantage of  GuessCompx than other
tools/packages/techniques, it does not require having the code of the target
function.

  * •

The GuessCompx provides a reliable, convenient, and simple procedure for the
estimation process.

  * •

The GuessCompx is the only tool of its kind in the R and can be easily
integrated with other programming languages such as Java, Matlab with several
relevant R packages.

The rest of the manuscript is organized as follows: Section 2 describes the
GuessCompx package and its functions in further detail. Section 3 demonstrates
the usefulness of the GuessCompx package with several examples and discusses
how the best tuning parameters attained. Section 4 shows the performance of
the GuessCompx package in predicting the time and space complexities. Finally,
the summary of the proposed GuessCompx package is presented in Section 5.

##  2 GuessCompx package description

An asymptotic complexity behavior can be defined for most common algorithms:
some are independent of the length of the data (think of the length function),
some linear, some quadratic (typically a distance computation), etc. We track
the computation time and memory of the algorithm runs on increasing subsets of
the data, using sampling or stratified sampling if needed. We fit the various
complexity functions with a simple glm() procedure with a formula of the kind
glm(time ~ log(nb_rows)), then find which is the best fit to the data. This
comparison between the models is achieved through a LOO (leave-one-out)
routine using Mean Squared Error as the indicator.

The GuessCompx package has a single entry point: the CompEst() function that
accept diverse input formats (data.frame, matrix, time series) and is fully
configurable to fit most use cases: which size of data to start at, how much
time the user has to do the audit (usually 1 minute gives a good result), how
many replicates you needed for each tested size (in case of high variability),
is a stratified sampling required (in case each run must include all possible
categories of one variable), by how much we increase the size at each run,
etc.

The plot output helps to compare the fit of each complexity function to the
data. The generalized block diagram of the GuessCompx package is as shown in
Figure 1.

Figure 1: generalized block diagram of GuessCompx package.

The GuessCompx package is adopted to estimate the worst case complexity of an
algorithm or function based on increasing length of the targeted dataset.
Hence, the dataframe and the R script (or function or code line/s) of the
targeted algorithm are the mandatory inputs for the GuessCompx package. Then
after, the GuessCompx package can be fine tuned with several input parameters
as shown in Figure 1. These parameters are discussed in detail in next
subsections. Based on the inputs and tuning of the package, it provides the
time and memory complexity for the given algorithm with the targeted
dataframes. There are several other modes of output results and visualization
(which are not mentioned in the block diagram) discussed in next section while
demonstrating the GuessCompx package.

Note on the memory complexity: memory analysis relies on the memory.size()
function to estimate the trend and this function only works on Windows
machines. If another OS is detected, the algorithm will skip the memory part.

###  2.1 Imports

GuessCompx requires the following CRAN packages to be installed: dplyr,
reshape2, lubridate, ggplot2, boot

###  2.2 Installation

The package can be downloaded from the CRAN repositories:

    Ψ\begin{Sinput}
    Ψ# install.packages("GuessCompx")
    Ψlibrary(GuessCompx)
    Ψ# ?CompEst
    Ψ\end{Sinput}
    Ψ

Also, it can be download it from Github:

    Ψ# install.packages("devtools")
    Ψlibrary(devtools)
    Ψinstall_github("agenis/GuessCompx")
    Ψ

###  2.3 Introduction to functions in GuessCompx package

Following sub-sections provide the insight on the main and internal functions
developed in the GuessCompx package.

####  2.3.1 The CompEst() function:

CompEst() is the main function used for estimation of complexity of an
algorithm. The function first creates a vector of data sizes, with possible
replicates, and loops through it. The max.time argument is then used as a
stopping condition to the loop (it stops as soon as the previous iteration has
exceeded the time limit). Indeed, the max.time argument does not limit the
total time spent by the function, but the maximum time of one single iteration
including possible replicates: the total number of iterations will be high if
the power factor is low, if the starting size is also low, and if the running
time increases slowly. The user might have to think about how to set his
parameters to prevent the computation time to be too long.

The core of the CompEst function works by simultaneously evaluating the time
and the memory used by one iteration of the target function over a sample of
the data. Time evaluation is achieved via a call to system.time(), memory
evaluation is done through memory.size() function, called before and after a
double garbage collection gc(). By passing the limitations of the
memory.size() function to only Windows users have been unsuccessfully tried
(pryr::mem_change, Rprof). Note that the sampling phase is conducted outside
the time/memory evaluation, so it has no footprint on the results.

A dataframe containing the data sizes, the memory and time results, is created
and serves as input to fit 2*7 complexity models and add their predictions to
the data. The cv.glm() function eventually computes the Leave-One-Out RMSE
error of each model, in an efficient way. Eventually, once the best model is
selected (the one with the smallest LOO-error), a significance test is
performed to check if the model is better than an intercept-only model.

It must be noted that, when a CONSTANT relationship is predicted, it might
simply mean that the max.time value is too low to show any tendency. Several
such cases rise an alert to the user to suggest modifications in the value of
the function’s arguments.

The function returns a list with the best complexity model and the computation
time on the whole dataset, for both time and memory complexity (Windows) and
time complexity only (all other OS). Also, it returns two plots, with the best
model curve highlighted in bold. The function has following arguments:

    ΨCompEst(d, f, random.sampling = FALSE, max.time = 30,
    Ψstart.size = NULL, replicates = 4, strata = NULL,
    Ψpower.factor = 2, alpha.value = 0.005, plot.result = TRUE)
    Ψ

d: A dataframe on which the algorithm is to be tested. This can also be a
vector or a matrix.

f: A user-defined function that runs the algorithm. The algorithm takes d as
the first argument. There is no need for the function to return any value.

random.sampling: This argument can have only two possible values, either TRUE
or FALSE (boolean). The default value is set to FALSE. If the value is TRUE, a
random sample is taken at each step. If FALSE, the first N observations are
taken at each step. Choosing a random sampling is relevant with the use of
replicates to help the discrimination power for complexity functions.

max.time: The maximum time allowed for each step of the analysis in seconds,
that is the time for all replicates of a single sample size. Once the
specified time limit is reached, the execution of the function is stopped. If
no value is specified, the default value of 30 seconds is used. There is no
such limitation regarding memory.

start.size: The size of the first sample to run the algorithm. The size is
given in the form of rows number. The default value of the argument is
floor(log2(nrow(d))). If strata is not NULL, it is recommended to pass a value
which is multiple of number of categories.

replicates: The number of replicated runs of the algorithm for a specific
sample size. This argument allows better discrimination of the complexity
function. The default value of the argument is set to 2.

strata: This argument is a string containing the name of categorical column of
d that must be used for stratified sampling. A fixed proportion of the
categories is sampled, always keeping at least one observation per category.

power.factor: The common ratio of the geometric progression of the sample
sizes. The default value is 2. It means that sample sizes double every step.
The argument can also be passed as a decimal value.

alpha.value: The alpha risk of the test whether the model is significantly
different from a constant relation. The default value is set to 0.005.

plot.result: A boolean value to indicate if the summary plot of all the
complexity functions is to be displayed. The best model is shown by the curve
in bold. If FALSE, then the plot is not displayed. The default value is set to
TRUE.

####  2.3.2 The CompEstBenchmark() function:

CompEstBenchmark() function presents a benchmark procedure to fit complexity
functions to a dataframe of time or memory values. The function takes input a
dataframe produced by the CompEst() function. User needs to specify whether
function deals with time or memory data. The function returns a list of all
the fitted complexity model.

The function has following arguments:

    ΨCompEstBenchmark(to.model, use = "time")
    Ψ

to.model: A dataframe produced by the CompEst() function. The dataframe is
comprised of size, time, memory and _NlogN_X_ columns.

use: A string indicating if the function deals with time or memory data. The
default value of the argument is ”time”.

####  2.3.3 The CompEstPlot() function:

The CompEstPlot() function plots the results of algorithms complexities. It
returns a ”ggplot” object.

The arguments of the function are:

    ΨCompEstPlot(to.plot, element_title = list("", ""), use = "time")
    Ψ

to.plot: A dataframe produced by CompEst() function.

element_title: A string that will be added to the subtitle of the plot.

use: A string to indicate if the function deals with ”time” or ”memory” data.
The default value is ”time”.

####  2.3.4 The CompEstPred() function:

The CompEstPred() function predicts the computation time of the whole dataset.
The function returns the predicted time for the whole dataset.

The arguments are:

    ΨCompEstPred(model.list, benchmark, N, use = "time")
    Ψ

model.list: A list containing the fitted complexity functions, produced by
CompEst() function.

benchmark: A vector of LOO errors of complexity functions, produced by
CompEst().

N: Number of rows of the whole dataset, produced by CompEst().

use: A string indicating if the function deals ”time” or ”memory” data.

####  2.3.5 GroupedSampleFracAtLeastOneSample() and rhead()

The GroupedSampleFracAtLeastOneSample() function samples a random proportion
of data, keeping at least one observation. This function is designed to allow
its use with group splitting or do.by methods. The function takes as input a
dataframe from which a small sample is to be returned. It is also possible to
specify the desired sampling fraction (second argument). The value of sampling
fraction is between 0 and 1. The third argument, is.random, is a boolean
value. If TRUE, a random sample is drawn, else it takes the head() of the
data.

The rhead() generates small random samples from a vector or a dataframe. The
function takes input a vector or a dataframe from which the small random
samples are generated. The second argument is a positive integer, representing
the number of lines or elements to print. The default value is 7. The third
argument, is.random is same as the one of the above functions. All functions
other than CompEst and rhead() are internal and not directly accessible to
users, but corresponding codes are available at Github page [32].

##  3 Demonstration of Guesscompx package

This section demonstrates the usefulness of the Guesscompx package. It
provides several examples showing some use cases (distance function, time
series, custom function) and how to attain the best tuned parameters. It is
important to keep in mind, since this package is measuring actual CPU times,
absolute reproducibility is out of reach. Running the examples on the computer
will return slightly different results each time.

###  3.1 Example 1

This example sets up a dummy function that mimics an algorithm with a _O(1)_
time complexity and a _O(N.log(N))_ memory complexity, both with some random
noise. See the warning issued for the time complexity : when a constant model
is found, it always suggests that the cause might be insufficient running time
or insufficient replicates. Also note that a _O(N.log(N))_ trend can sometimes
be mistaken for a linear trend.

    Ψ# Dummy function that mimics a constant time complexity and
    Ψ# N.log(N) memory complexity:
    Ψf1 = function(df){
    ΨSys.sleep(rnorm(1, 0.1, 0.02))
    Ψv = rnorm(n = nrow(df)*log(nrow(df))*(runif(1, 1e3, 1.1e3)))
    Ψ}
    Ψout = CompEst(d = mtcars, f = f1, replicates=2, start.size=2, max.time = 1)
    Ψ

(a)

(b)

Figure 2: Complexity fit against (a) run time and (b) memory usage for
function ‘f()‘ on ‘mtcars‘ dataset, suggests _O(1)_ and _O(Nlog(N))_ as best
model, respectively (Example 1)

    Ψ# Raises an alert for TIME complexity.
    Ψ# Sometimes confuses MEMORY complexity with linear:
    Ψprint(out)
    Ψ

    Ψ#> $sample.sizes
    Ψ#>  [1]  2  2  4  4  8  8 16 16 32 32
    Ψ#>
    Ψ#> $‘TIME COMPLEXITY RESULTS‘
    Ψ#> $‘TIME COMPLEXITY RESULTS‘$best.model
    Ψ#> [1] "CONSTANT"
    Ψ#>
    Ψ#> $‘TIME COMPLEXITY RESULTS‘$computation.time.on.full.dataset
    Ψ#> [1] "0.11S"
    Ψ#>
    Ψ#> $‘TIME COMPLEXITY RESULTS‘$p.value.model.significance
    Ψ#> [1] NA
    Ψ#>
    Ψ#>
    Ψ#> $‘MEMORY COMPLEXITY RESULTS‘
    Ψ#> $‘MEMORY COMPLEXITY RESULTS‘$best.model
    Ψ#> [1] "NLOGN"
    Ψ#>
    Ψ#> $‘MEMORY COMPLEXITY RESULTS‘$memory.usage.on.full.dataset
    Ψ#> [1] "1 Mb"
    Ψ#>
    Ψ#> $‘MEMORY COMPLEXITY RESULTS‘$system.memory.limit
    Ψ#> [1] "8064 Mb"
    Ψ#>
    Ψ#> $‘MEMORY COMPLEXITY RESULTS‘$p.value.model.significance
    Ψ#> [1] 3.166196e-09
    Ψ

###  3.2 Example 2

This example tests the behaviour against a real-life distance algorithm whose
complexity should be a clear _O(N^2)_ , for both memory and time.

    Ψ# ’dist’ function analysis:
    Ψf2 = dist
    Ψd  = ggplot2::diamonds[, 5:8]
    ΨCompEst(d = d, f = f2, replicates = 1, max.time = 1)
    Ψ

(a)

(b)

Figure 3: Complexity fit against (a) run time and (b) memory usage for
distance function on ‘diamonds‘ dataset, suggests _O(Nlog(N))_ and _O(N^2)_ as
best model, respectively (Example 2)

    Ψ#> $sample.sizes
    Ψ#>  [1]    15    30    60   120   240   480   960  1920  3840  7680 15360
    Ψ#> [12] 30720 53940
    Ψ#>
    Ψ#> $‘TIME COMPLEXITY RESULTS‘
    Ψ#> $‘TIME COMPLEXITY RESULTS‘$best.model
    Ψ#> [1] "NLOGN"
    Ψ#>
    Ψ#> $‘TIME COMPLEXITY RESULTS‘$computation.time.on.full.dataset
    Ψ#> [1] "5.78S"
    Ψ#>
    Ψ#> $‘TIME COMPLEXITY RESULTS‘$p.value.model.significance
    Ψ#> [1] 1.57405e-07
    Ψ#>
    Ψ#>
    Ψ#> $‘MEMORY COMPLEXITY RESULTS‘
    Ψ#> $‘MEMORY COMPLEXITY RESULTS‘$best.model
    Ψ#> [1] "QUADRATIC"
    Ψ#>
    Ψ#> $‘MEMORY COMPLEXITY RESULTS‘$memory.usage.on.full.dataset
    Ψ#> [1] "11110 Mb"
    Ψ#>
    Ψ#> $‘MEMORY COMPLEXITY RESULTS‘$system.memory.limit
    Ψ#> [1] "8064 Mb"
    Ψ#>
    Ψ#> $‘MEMORY COMPLEXITY RESULTS‘$p.value.model.significance
    Ψ#> [1] 1.28452e-28
    Ψ

###  3.3 Example 3

This example tests the time and memory complexity of a time series prediction
method. For this purpose, an ARIMA model is used. For time series functions,
the f argument may include ts() and to avoid loosing this ts attribute at
sampling, it is recommended to set start.size argument to 3 periods at least.
The ARIMA function should return a linear trend for time complexity.

    Ψ# time series prediction function analysis:
    Ψf = function(d) arima(ts(d, freq = 12), order=c(1,0,1), seasonal = c(0,1,1))
    Ψd = ggplot2::txhousing$sales
    ΨCompEst(d, f, start.size = 4*12, random.sampling = FALSE)
    Ψ

(a)

(b)

Figure 4: Complexity fit against (a) run time and (b) memory usage for
distance function on ‘sales‘ dataset, suggests _O(N)_ and _O(N^(1/2))_ as best
model, respectively (Example 3)

    Ψ#> $sample.sizes
    Ψ#>  [1]   48   48   48   48   96   96   96   96  192  192  192  192  384  384
    Ψ#> [15]  384  384  768  768  768  768 1536 1536 1536 1536 3072 3072 3072 3072
    Ψ#> [29] 6144 6144 6144 6144 8602 8602 8602 8602
    Ψ#>
    Ψ#> $‘TIME COMPLEXITY RESULTS‘
    Ψ#> $‘TIME COMPLEXITY RESULTS‘$best.model
    Ψ#> [1] "LINEAR"
    Ψ#>
    Ψ#> $‘TIME COMPLEXITY RESULTS‘$computation.time.on.full.dataset
    Ψ#> [1] "6.88S"
    Ψ#>
    Ψ#> $‘TIME COMPLEXITY RESULTS‘$p.value.model.significance
    Ψ#> [1] 3.492077e-16
    Ψ#>
    Ψ#>
    Ψ#> $‘MEMORY COMPLEXITY RESULTS‘
    Ψ#> $‘MEMORY COMPLEXITY RESULTS‘$best.model
    Ψ#> [1] "SQUAREROOT"
    Ψ#>
    Ψ#> $‘MEMORY COMPLEXITY RESULTS‘$memory.usage.on.full.dataset
    Ψ#> [1] "84 Mb"
    Ψ#>
    Ψ#> $‘MEMORY COMPLEXITY RESULTS‘$system.memory.limit
    Ψ#> [1] "8064 Mb"
    Ψ#>
    Ψ#> $‘MEMORY COMPLEXITY RESULTS‘$p.value.model.significance
    Ψ#> [1] 0.004649934
    Ψ

###  3.4 Example 4

This example tests the behavior of eigen decomposition process of a matrix.
Since the algorithm only works on square matrices, here the target function
subsets columns to force the matrix into a square one, otherwise the sampling
would result in a rectangular matrix. This analysis yields an _O(N^3)_ fit for
time complexity, which is scientifically correct, and a quadratic for memory
one.

    Ψ# Eigendecomposition of a matrix
    Ψm = matrix(rnorm(1e6), ncol=1000, nrow=1000)
    Ψ
    Ψ# force the matrix into a square one:
    Ψeigen. = function(m) eigen(as.matrix(m[, 1:nrow(m)]))
    Ψ
    Ψ# This yields an O(n^3) fit, which is scientifically correct,
    Ψ# and a quadratic for memory.
    Ψout = CompEst(m, eigen., replicates = 5, max.time = 60)
    Ψ

(a)

(b)

Figure 5: Complexity fit against (a) run time and (b) memory usage for eigen
decomposition function on a matrix dataset, suggests _O(N^3)_ and _O(N^2)_ as
best model, respectively (Example 4)

###  3.5 Example 5

This example is an special case of stratified input, which is useful to force
the sampling to have at least one observation of each class of a specific
column. Consider a function to predict a diabetes outcome in the dataset
‘PimaIndiansDiabetes‘ with the Support Vector Machine (SVM) method. Depending
on algorithm, the true complexity (time) of SVM is between _O(N^2)_ and
_O(N^3)_.

    Ψlibrary(mlbench)
    Ψlibrary(e1071)
    Ψdata("PimaIndiansDiabetes")
    Ψf6 = function(df){
    Ψfit = svm(diabetes ~ ., data=df)
    Ψreturn(table(df$diabetes, fitted(fit)))
    Ψ}
    Ψ

With this configuration, sampling will often result in only negative or
positive observations to train the model, which results in an error message as
shown below.

    ΨCompEst(PimaIndiansDiabetes, f6, start.size = 3, power.factor = 3)
    Ψ
    Ψ# ERROR: model is empty!
    Ψ

After fixing the strata argument to be the Y vector of classes, to ensure that
both classes will be represented in the model as follows. Currently, the
strata argument enables to specify only one column, but future versions of
this package will accept list of columns.

    ΨCompEst(PimaIndiansDiabetes, f6, start.size = 3, power.factor = 3, strata = "diabetes")
    Ψ

(a)

(b)

Figure 6: Complexity fit against (a) run time and (b) memory usage for SVM
function on ‘PimaIndiansDiabetes‘ dataset, suggests _O(N^2)_ and _O(N)_ as
best model, respectively (Example 5)

    Ψ#> $sample.sizes
    Ψ#>  [1]   3   3   3   3   9   9   9   9  27  27  27  27  81  81  81  81 243
    Ψ#> [18] 243 243 243 729 729 729 729 768 768 768 768
    Ψ#>
    Ψ#> $‘TIME COMPLEXITY RESULTS‘
    Ψ#> $‘TIME COMPLEXITY RESULTS‘$best.model
    Ψ#> [1] "QUADRATIC"
    Ψ#>
    Ψ#> $‘TIME COMPLEXITY RESULTS‘$computation.time.on.full.dataset
    Ψ#> [1] "0.07S"
    Ψ#>
    Ψ#> $‘TIME COMPLEXITY RESULTS‘$p.value.model.significance
    Ψ#> [1] 8.624223e-15
    Ψ#>
    Ψ#>
    Ψ#> $‘MEMORY COMPLEXITY RESULTS‘
    Ψ#> $‘MEMORY COMPLEXITY RESULTS‘$best.model
    Ψ#> [1] "LINEAR"
    Ψ#>
    Ψ#> $‘MEMORY COMPLEXITY RESULTS‘$memory.usage.on.full.dataset
    Ψ#> [1] "2 Mb"
    Ψ#>
    Ψ#> $‘MEMORY COMPLEXITY RESULTS‘$system.memory.limit
    Ψ#> [1] "8064 Mb"
    Ψ#>
    Ψ#> $‘MEMORY COMPLEXITY RESULTS‘$p.value.model.significance
    Ψ#> [1] 7.60052e-29
    Ψ

###  3.6 Example 6

This example tests the complexity of a dummy function that mimics a linear
time complexity with high CPU variability and heteroscedasticity. This
function results in a variety of non-significant “best models”, often “LINEAR”
one. Thereafter, we increase the number of replicates, start at a smaller
size, and get an almost always “Linear” response. This example takes much more
time because we replicate 10 times the result.

    Ψ# A dummy function:
    Ψf3 = function(df){  Sys.sleep(max(0, rnorm(1, 0.1+nrow(df)/500, nrow(df)/2000)))  }
    Ψset.seed(1);
    Ψreplicate(10, CompEst(d = mtcars, f = f3, plot.result = F)$‘TIME COMPLEXITY RESULTS‘$best.model)
    Ψ

    Ψ#>  [1] "LOG"        "SQUAREROOT" "LINEAR"     "LOG"        "SQUAREROOT"
    Ψ#>  [6] "QUADRATIC"  "SQUAREROOT" "QUADRATIC"  "SQUAREROOT" "SQUAREROOT"
    Ψ

    Ψset.seed(2);
    Ψreplicate(10, CompEst(d = mtcars, f = f3, plot.result = F, start.size = 1,
    Ψreplicates = 10, max.time=5)$‘TIME COMPLEXITY RESULTS‘$best.model)
    Ψ

    Ψ#>  [1] "SQUAREROOT" "LINEAR"     "NLOGN"      "SQUAREROOT" "LINEAR"
    Ψ#>  [6] "LINEAR"     "LINEAR"     "LINEAR"     "NLOGN"      "NLOGN"
    Ψ

##  4 Performance

As in [28], it was assessed the prediction power of the described method. It
is important to understand the prediction performance of the proposed tool has
no absolute meaning, since it can always be improved by allocating more time
to run the test.

Table 1: Some famous algorithms with their predicted complexities

|  | True time
---
complexity
| Time
---
Accuracy
| True space
---
complexity
| Predicted space
---
complexity
Bubble sort | O(N^2) | 97% | O(N) | 97% O(Nlog(N))11footnotemark: 1
Find max | O(N) | 95% | O(1) | 65%
Permutations | O(N^3) | 99% | O(N) | 95%
Tree split22footnotemark: 2 | O(log(N)) | 38% | O(NlogN) | 98%
Shell search | O(N^(4/3))33footnotemark: 3 |  | NA
---
(73% O(NlogN),
27% O(N))
O(N) | 100%

11footnotemark: 1

it is known that _O(logN)_ and _O(NlogN)_ are easy to confuse

22footnotemark: 2

rpart regression from rpart package, which is sensitive to the data itself

33footnotemark: 3

not part of the 7 base complexity functions

These considerations taken aside, a test bench was set up in order to test one
paragon algorithm for each complexity family as shown in Table 1. The selected
algorithms are the popular ones with known time and space complexities. In
this section, we have checked the performance of the GuessCompx in predicting
the respective time and space complexities. Whenever possible, we worked with
the default setting of the CompEst() function, sometimes reducing the time
limit down to 1 second. One hundred replicates of the function were set.
Accuracy is defined as:

$\text{Accuracy}=\frac{\text{Number of correct predictions for complexity
function}}{\text{total number of cases}}\times 100$ (1)

Table 1 shows the accuracy in predicting complexities of the targeted
algorithms. In most of the cases (especially, Bubble sort, Find max,
Permutation), both predicted time and space complexities are significantly
accurate. Further, the space complexity of the Tree split algorithm is
predicted accurately, but time complexity accuracy is average, since the
algorithm is highly sensitive to the input dataset. Besides, the true time
complexity of the Shell search algorithm is O(N^(4/3)), but it is not within
the seven base complexities considered in the GuessCompx package. Therefore,
the predicted time complexities are the ones which are near to the real one.
However, the predicted space complexity for the Shell search is 100% accurate.

Eventually, some of the precision results may seem disappointing. There is
indeed a strong sensibility to the choice of the settings and fine-tuning the
arguments can make a sensible difference in the result. It is illustrated by a
detailed simulation where the maximum vector length varies between 1E4 and
1E9, this last value being considered as the ”asymptotic” value. The Figure 7
shows asymptotic linear trend for ‘max()‘ function as target algorithm. It
represents the result in proportion of the best model outputted: when the data
is too small no model can be determined because the ‘max()‘ function is too
fast; for vectors around size 1E07, CPU time starts to rise with some
variability, but the fit will not return a stable solution; eventually, with
sizes going over 1E08, the asymptotic linear trend appears strongly.

Figure 7: The asymptotic linear trend for ‘max()‘ function as target algorithm

###  4.1 Number of Replicates:

As a second performance example, the number of replicates is tested in the
benchmark. The max.time limit argument is not used here because it is counted
for all replicates of the same size. In order to hold everything constant but
the number of replicates, we set an infinite time limit for a run, only
limiting it with a small input dataset, so it will not take more than a
fraction of seconds to complete a run. This testbench, using a distance
computation on a data.frame as the target algorithm, shows that when the we
are in the “grey zone” (uncertain outcome of the analysis), the number of
replicates can make the difference to find the correct model as shown in
Figure 8.

Figure 8: Effect of number of replicates on finding the correct model for
distance algorithm on ‘diamonds‘ dataset

The codes to test all analysis and comparison done in this section are
available in GitHub page [33].

##  5 Summary

This article was proposed a thorough description of the GuessCompx R package.
The package is introduced to perform an empirical estimate on the time and
memory complexities of an algorithm or a function. It tests multiple,
increasing-sizes samples of the user’s data and try to fit one of seven
complexity functions: _O(N), O(N^2), O(log(N))_ , etc. Based on the best fit
procedure using LOO-MSE (leave one out-mean square error), it also predicts
the full computation time and memory usage on the whole dataset. The hereby
suggested method and package are believed to be new to the R users community;
however there is a lot of room for improvement, both in terms of automation
and variety of complexity functions. Further, it is worthy in noting that the
complexity is understood only with regard to the size of the data (number of
rows), not other possible parameters such as number of features, tuning
parameters, etc. Interactions with those parameters could be investigated in
future versions of the package. There is always a scope of addition of extra
and more complex complexity families in the present version of the GuessCompx
package.

## References

  * [1] J. He and X. Yao, “Drift analysis and average time complexity of evolutionary algorithms,” Artificial intelligence, vol. 127, no. 1, pp. 57–85, 2001\.
  * [2] M. T. Jensen, “Reducing the run-time complexity of multiobjective eas: The nsga-ii and other algorithms,” IEEE Transactions on Evolutionary Computation, vol. 7, no. 5, pp. 503–515, 2003.
  * [3] J. Anderson and S. Mohan, “Sequential coding algorithms: A survey and cost analysis,” IEEE Transactions on Communications, vol. 32, no. 2, pp. 169–176, 1984.
  * [4] G. J. Woeginger, “Space and time complexity of exact algorithms: Some open problems,” in International Workshop on Parameterized and Exact Computation, pp. 281–290, Springer, 2004.
  * [5] I. C. Wong, Z. Shen, B. L. Evans, and J. G. Andrews, “A low complexity algorithm for proportional resource allocation in ofdma systems,” in IEEE Workshop on Signal Processing Systems, pp. 1–6, IEEE, 2004.
  * [6] L. G. Valiant, “The complexity of computing the permanent,” Theoretical computer science, vol. 8, no. 2, pp. 189–201, 1979.
  * [7] L. Abualigah, “Multi-verse optimizer algorithm: a comprehensive survey of its results, variants, and applications,” Neural Computing and Applications, pp. 1–21, 2020.
  * [8] L. M. Q. Abualigah, Feature selection and enhanced krill herd algorithm for text document clustering.  Springer, 2019.
  * [9] W. Min, “Analysis on bubble sort algorithm optimization,” in International Forum on Information Technology and Applications, vol. 1, pp. 208–211, IEEE, 2010.
  * [10] W. Min, “Analysis on bubble sort algorithm optimization,” in 2010 International Forum on Information Technology and Applications, vol. 1, pp. 208–211, IEEE, 2010.
  * [11] Y. Yang, P. Yu, and Y. Gan, “Experimental study on the five sort algorithms,” in 2011 Second International Conference on Mechanic Automation and Control Engineering, pp. 1314–1317, IEEE, 2011.
  * [12] I. Chivers and J. Sleightholme, “An introduction to algorithms and the big o notation,” in Introduction to Programming with Fortran, pp. 359–364, Springer, 2015.
  * [13] J. F. Shapiro, “Mathematical programming: structures and algorithms,” tech. rep., 1979.
  * [14] Z. Zhang, W.-C. Hong, and J. Li, “Electric load forecasting by hybrid self-recurrent support vector regression model with variational mode decomposition and improved cuckoo search algorithm,” IEEE Access, vol. 8, pp. 14642–14658, 2020.
  * [15] V. Paliwal, A. D. Ghare, A. B. Mirajkar, N. D. Bokde, and A. E. Feijoo Lorenzo, “Computer modeling for the operation optimization of mula reservoir, upper godavari basin, india, using the jaya algorithm,” Sustainability, vol. 12, no. 1, p. 84, 2020.
  * [16] W.-C. Hong, M.-W. Li, J. Geng, and Y. Zhang, “Novel chaotic bat algorithm for forecasting complex motion of floating platforms,” Applied Mathematical Modelling, vol. 72, pp. 425–443, 2019.
  * [17] W.-C. Hong, Y. Dong, C.-Y. Lai, L.-Y. Chen, and S.-Y. Wei, “Svr with hybrid chaotic immune algorithm for seasonal load demand forecasting,” Energies, vol. 4, no. 6, pp. 960–977, 2011.
  * [18] Y. Dong, Z. Zhang, and W.-C. Hong, “A hybrid seasonal mechanism with a chaotic cuckoo search algorithm with a support vector regression model for electric load forecasting,” Energies, vol. 11, no. 4, p. 1009, 2018.
  * [19] Z. Zhang and W.-C. Hong, “Electric load forecasting by complete ensemble empirical mode decomposition adaptive noise and support vector regression with quantum-based dragonfly algorithm,” Nonlinear Dynamics, vol. 98, no. 2, pp. 1107–1136, 2019.
  * [20] H. Kundra and H. Sadawarti, “Hybrid algorithm of cuckoo search and particle swarm optimization for natural terrain feature extraction,” Research Journal of Information Technology, vol. 7, no. 1, pp. 58–69, 2015.
  * [21] L. M. Abualigah, A. T. Khader, and E. S. Hanandeh, “A new feature selection method to improve the document clustering using particle swarm optimization algorithm,” Journal of Computational Science, vol. 25, pp. 456–466, 2018\.
  * [22] L. M. Abualigah and A. T. Khader, “Unsupervised text feature selection technique based on hybrid particle swarm optimization algorithm with genetic operators for the text clustering,” The Journal of Supercomputing, vol. 73, no. 11, pp. 4773–4795, 2017.
  * [23] J. Qiu, Q. Wu, G. Ding, Y. Xu, and S. Feng, “A survey of machine learning for big data processing,” EURASIP Journal on Advances in Signal Processing, vol. 2016, no. 1, p. 67, 2016.
  * [24] S. Q. Salih and A. A. Alsewari, “A new algorithm for normal and large-scale optimization problems: Nomadic people optimizer,” Neural Computing and Applications, pp. 1–28, 2019.
  * [25] O. Bournez and A. Pouly, “A survey on analog models of computation,” arXiv preprint arXiv:1805.05729, 2018.
  * [26] M. Pégny, “Computational complexity: An empirical view,” 39th Annual Convention of the Society for the Study of Artificial Intelligence and the Simulation of Behaviour (AISB 2013), pp. 1–6, 2013.
  * [27] M. Pégny, “How to make a meaningful comparison of models: The church–turing thesis over the reals,” Minds and Machines, vol. 26, no. 4, pp. 359–388, 2016.
  * [28] D. K. Sharma, S. Vohra, T. Gupta, and V. Goyal, “Predicting the algorithmic time complexity of single parametric algorithms using multiclass classification with gradient boosted trees,” in 2018 Eleventh International Conference on Contemporary Computing (IC3), pp. 1–6, IEEE, 2018\.
  * [29] S. F. Goldsmith, A. S. Aiken, and D. S. Wilkerson, “Measuring empirical computational complexity,” in Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, pp. 395–404, ACM, 2007.
  * [30] M. Agenis and N. Bokde, GuessCompx: Empirically Estimates Algorithm Complexity, 2019.  R package version 1.0.3.
  * [31] W. contributors, “Time complexity — Wikipedia, the free encyclopedia,” 2019\.  Online; accessed 01-May-2019.
  * [32] M. Agenis, “Guesscompx.” https://github.com/agenis/GuessCompx, 2019.
  * [33] M. Agenis, “Guesscompxperformancetests.” https://github.com/agenis/GuessCompxPerformanceTests, 2019.