-
An Incremental MaxSAT-based Model to Learn Interpretable and Balanced Classification Rules
Authors:
Antônio Carlos Souza Ferreira Júnior,
Thiago Alves Rocha
Abstract:
The increasing advancements in the field of machine learning have led to the development of numerous applications that effectively address a wide range of problems with accurate predictions. However, in certain cases, accuracy alone may not be sufficient. Many real-world problems also demand explanations and interpretability behind the predictions. One of the most popular interpretable models that…
▽ More
The increasing advancements in the field of machine learning have led to the development of numerous applications that effectively address a wide range of problems with accurate predictions. However, in certain cases, accuracy alone may not be sufficient. Many real-world problems also demand explanations and interpretability behind the predictions. One of the most popular interpretable models that are classification rules. This work aims to propose an incremental model for learning interpretable and balanced rules based on MaxSAT, called IMLIB. This new model was based on two other approaches, one based on SAT and the other on MaxSAT. The one based on SAT limits the size of each generated rule, making it possible to balance them. We suggest that such a set of rules seem more natural to be understood compared to a mixture of large and small rules. The approach based on MaxSAT, called IMLI, presents a technique to increase performance that involves learning a set of rules by incrementally applying the model in a dataset. Finally, IMLIB and IMLI are compared using diverse databases. IMLIB obtained results comparable to IMLI in terms of accuracy, generating more balanced rules with smaller sizes.
△ Less
Submitted 29 April, 2024; v1 submitted 25 March, 2024;
originally announced March 2024.
-
Logic-based Explanations for Linear Support Vector Classifiers with Reject Option
Authors:
Francisco Mateus Rocha Filho,
Thiago Alves Rocha,
Reginaldo Pereira Fernandes Ribeiro,
Ajalmar Rêgo da Rocha Neto
Abstract:
Support Vector Classifier (SVC) is a well-known Machine Learning (ML) model for linear classification problems. It can be used in conjunction with a reject option strategy to reject instances that are hard to correctly classify and delegate them to a specialist. This further increases the confidence of the model. Given this, obtaining an explanation of the cause of rejection is important to not bl…
▽ More
Support Vector Classifier (SVC) is a well-known Machine Learning (ML) model for linear classification problems. It can be used in conjunction with a reject option strategy to reject instances that are hard to correctly classify and delegate them to a specialist. This further increases the confidence of the model. Given this, obtaining an explanation of the cause of rejection is important to not blindly trust the obtained results. While most of the related work has developed means to give such explanations for machine learning models, to the best of our knowledge none have done so for when reject option is present. We propose a logic-based approach with formal guarantees on the correctness and minimality of explanations for linear SVCs with reject option. We evaluate our approach by comparing it to Anchors, which is a heuristic algorithm for generating explanations. Obtained results show that our proposed method gives shorter explanations with reduced time cost.
△ Less
Submitted 24 March, 2024;
originally announced March 2024.
-
On Finding a First-Order Sentence Consistent with a Sample of Strings
Authors:
Thiago Alves Rocha,
Ana Teresa Martins,
Francicleber Martins Ferreira
Abstract:
We investigate the following problem: given a sample of classified strings, find a first-order sentence of minimal quantifier rank that is consistent with the sample. We represent strings as successor string structures, that is, finite structures with unary predicates to denote symbols in an alphabet, and a successor relation. We use results of the Ehrenfeucht-Fraïssé game over successor string st…
▽ More
We investigate the following problem: given a sample of classified strings, find a first-order sentence of minimal quantifier rank that is consistent with the sample. We represent strings as successor string structures, that is, finite structures with unary predicates to denote symbols in an alphabet, and a successor relation. We use results of the Ehrenfeucht-Fraïssé game over successor string structures in order to design an algorithm to find such sentence. We use conditions characterizing the winning strategies for the Spoiler on successor strings structures in order to define formulas which distinguish two strings. Our algorithm returns a boolean combination of such formulas.
△ Less
Submitted 9 September, 2018;
originally announced September 2018.