Name
Abstract | ||
|---|---|---|
A substantial connection exists between supervised learning from data represented in logic form and the solution of the Minimum Cost Satisfiability Problem (MinCostSAT). Methods based on such connection have been developed and successfully applied in many contexts. The deployment of such methods to large-scale learning problem is often hindered by the computational challenge of solving MinCostSAT, a problem well known to be NP-complete. In this paper, we propose a GRASP-based metaheuristic designed for such problem, that proves successful in leveraging the very distinctive structure of the MinCostSAT problems arising in supervised learning. The algorithm is equipped with an original stopping criterion based on probabilistic assumptions which results very effective for deciding when the search space has been explored enough. Although the proposed solver may approach MinCostSAT of general form, in this paper we limit our analysis to some instances that have been created from artificial supervised learning problems, and show that our method outperforms more general purpose well established solvers. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/978-3-319-69404-7_5 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
Hard combinatorial optimization,SAT problems,GRASP,Local search,Probabilistic stopping criterion,Approximate solutions | Mathematical optimization,GRASP,Computer science,Boolean satisfiability problem,Theoretical computer science,Supervised learning,Probabilistic logic,Solver,Local search (optimization),Logic form,Metaheuristic | Conference |
Volume | ISSN | Citations |
10556 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 16 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Giovanni Felici | 1 | 201 | 21.98 |
| daniele ferone | 2 | 19 | 5.78 |
| Paola Festa | 3 | 287 | 25.32 |
| Antonio Napoletano | 4 | 0 | 1.01 |
| Tommaso Pastore | 5 | 0 | 1.01 |