BIRD, BCAM's Institutional Repository DataThe BIRD digital repository system captures, stores, indexes, preserves, and distributes digital research material.https://bird.bcamath.org:4432024-02-28T09:23:26Z2024-02-28T09:23:26ZSpeeding-Up Evolutionary Algorithms to Solve Black-Box Optimization ProblemsEchevarrieta, J.Arza, E.Pérez, A.http://hdl.handle.net/20.500.11824/17852024-02-27T23:20:13Z2024-01-10T00:00:00ZSpeeding-Up Evolutionary Algorithms to Solve Black-Box Optimization Problems
Echevarrieta, J.; Arza, E.; Pérez, A.
Population-based evolutionary algorithms are often considered when approaching computationally expensive black-box optimization problems. They employ a selection mechanism to choose the best solutions from a given population after comparing their objective values, which are then used to generate the next population. This iterative process explores the solution space efficiently, leading to improved solutions over time. However, one of the challenges of these algorithms is that they require a large number of evaluations to provide a quality solution, which might be computationally expensive when the evaluation cost is high. In some cases, it is possible to replace the original objective function with a less accurate approximation of lower cost. This introduces a trade-off between the evaluation cost and its accuracy. In this paper, we propose a technique capable of choosing an appropriate approximate function cost during the execution of the optimization algorithm. The proposal finds the minimum evaluation cost at which the solutions are still properly ranked, and consequently, more evaluations can be computed in the same amount of time with minimal accuracy loss. An experimental section on four very different problems reveals that the proposed approach can reach the same objective value in less than half of the time in certain cases.
2024-01-10T00:00:00ZFast Computation of Cluster Validity Measures for Bregman Divergences and BenefitsCapó, M.Pérez, A.Lozano, J.A.http://hdl.handle.net/20.500.11824/17842024-02-27T23:20:16Z2023-01-01T00:00:00ZFast Computation of Cluster Validity Measures for Bregman Divergences and Benefits
Capó, M.; Pérez, A.; Lozano, J.A.
Partitional clustering is one of the most relevant unsupervised learning and pattern recognition techniques. Unfortunately, one of the main drawbacks of these methodologies refer to the fact that the number of clusters is generally assumed to be known beforehand and automating its selection is not straightforward. On the same token, internal validity measures, such as the Silhouette index, Davies-Bouldin and Caliski-Harabasz measures have emerged as the standard techniques to be used when comparing the goodness of clustering results obtained via different clustering methods. These measures take into consideration both the inter and intra-cluster simmilarities and can be adapted to different metrics. Unfortunately, their used has been hindered due to their large computational complexities, which are commonly quadratic with respect to the number of instances of the data set. In this work, we show that the time complexity of computing the most popular internal validity measures can be utterly reduced by making used of the within-cluster errors and different properties of the Bregman divergences. This contribution ultimately allows us to massively speed-up the selection of an adequate number of clusters for a given data set as verified with extensive empirical comparisons.
2023-01-01T00:00:00ZFast K-Medoids With the l_1-NormCapó, M.Pérez, A.Lozano, J.A.http://hdl.handle.net/20.500.11824/17832024-02-27T23:20:12Z2023-07-26T00:00:00ZFast K-Medoids With the l_1-Norm
Capó, M.; Pérez, A.; Lozano, J.A.
K-medoids clustering is one of the most popular techniques in exploratory data analysis. The most commonly used algorithms to deal with this problem are quadratic on the number of instances, n, and usually the quality of the obtained solutions strongly depends upon their initialization phase. In this work, we propose an algorithm for the K -medoids problem on the l_1-norm/Manhattan distance with a computational complexity of O(n⋅max{log n,K}⋅d) , along with theoretical guarantees in terms of the accuracy of the obtained approximation. In addition, we propose a cheap split-merge mechanism that can be used to re-start the proposed algorithm after its convergence to a fixed point. Under some mild assumptions, we prove that such a re-start procedure reduces the error of the given fixed point. The work also includes an extensive experimentation, in which we compare our method to the most popular approaches for the K -medoids problem: PAM, CLARA and Park's K -medoids. The obtained empirical results show the proposed algorithm to consistently converge to the solutions with the lowest errors, up to two orders of magnitude of relative error lower than the previously mentioned methods, while also requiring the lowest computational running times among them: up to three orders of magnitude lower.
2023-07-26T00:00:00ZMinimax Forward and Backward Learning of Evolving Tasks with Performance GuaranteesÁlvarez, V.Mazuelas, S.Lozano, J.A.http://hdl.handle.net/20.500.11824/17822024-02-27T23:20:15Z2023-12-01T00:00:00ZMinimax Forward and Backward Learning of Evolving Tasks with Performance Guarantees
Álvarez, V.; Mazuelas, S.; Lozano, J.A.
For a sequence of classification tasks that arrive over time, it is common that tasks
are evolving in the sense that consecutive tasks often have a higher similarity. The
incremental learning of a growing sequence of tasks holds promise to enable accurate
classification even with few samples per task by leveraging information from
all the tasks in the sequence (forward and backward learning). However, existing
techniques developed for continual learning and concept drift adaptation are either
designed for tasks with time-independent similarities or only aim to learn the
last task in the sequence. This paper presents incremental minimax risk classifiers
(IMRCs) that effectively exploit forward and backward learning and account for
evolving tasks. In addition, we analytically characterize the performance improvement
provided by forward and backward learning in terms of the tasks’ expected
quadratic change and the number of tasks. The experimental evaluation shows
that IMRCs can result in a significant performance improvement, especially for
reduced sample sizes.
2023-12-01T00:00:00Z