Design of poset forest-based algorithms for the U-curve optimization problem

• Grant number: 16/25959-7
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: May 01, 2017
• End date: December 31, 2017
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computing Methodologies and Techniques
• Principal Investigator: Marcelo da Silva Reis
• Grantee: Gustavo Estrela de Matos
• Host Institution: Instituto Butantan. Secretaria da Saúde (São Paulo - Estado). São Paulo , SP, Brazil
• Associated research grant: 13/07467-1 - CeTICS - Center of Toxins, Immune-Response and Cell Signaling, AP.CEPID

Abstract

The U-curve problem is a formulation of an optimization problem that can be used in the feature selection step of Machine Learning, with applications in the designing of computational models of biological systems. Nevertheless, the solutions so far proposed to tackle this problem have limitations from both required computational time and space points of view, which implies in the need for development of new algorithms. To this end, it was introduced in 2012 the Poset-Forest-Search (PFS) algorithm, which organizes the search space in forests of posets. This algorithm was implemented and tested, with promising results; however, new improvements are required until PFS becomes a competitive alternative to tackle the U-curve problem. In this project, we propose the design of a parallelized, scalable version of the PFS algorithm, using reduced ordered binary decision diagrams. Moreover, we propose to adapt PFS as an approximation algorithm, in which the approximation criterion to the optimal solution makes use of the Ockham's razor theorem. The developed algorithms will be implemented and tested on artificial instances and also on collection of datasets that are suitable for benchmarking of feature selection algorithms. (AU)

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

REIS, MARCELO S.; ESTRELA, GUSTAVO; FERREIRA, CARLOS EDUARDO; BARRERA, JUNIOR. featsel: A framework for benchmarking of feature selection algorithms and cost functions. SOFTWAREX, v. 6, p. 193-197, 2017. (13/03447-6, 15/01587-0, 16/25959-7, 13/07467-1)

ESTRELA, GUSTAVO; GUBITOSO, MARCO DIMAS; FERREIRA, CARLOS EDUARDO; BARRERA, JUNIOR; REIS, MARCELO S.. An Efficient, Parallelized Algorithm for Optimal Conditional Entropy-Based Feature Selection. Entropy, v. 22, n. 4, APR 2020. (16/25959-7, 13/07467-1, 15/01587-0)