How (and when) can you fit examples to logic-based hypothesis classes over infinite structures?
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916070950961152 |
|---|---|
| author | Benedikt, Michael Mansutti, Alessio |
| author_facet | Benedikt, Michael Mansutti, Alessio |
| contents | We study fitting problems, sometimes called ``training problems'', where we have a finite sample consisting of inputs and outputs, and we want to know whether there is a function in a certain class that could produce these outputs, exactly or approximately, on the given inputs. We focus on the computational and descriptive complexity of fitting for logically-defined classes in common decidable structures, like the real ordered field and Presburger arithmetic, and also for broader classes defined via combinatorial or model-theoretic properties. We isolate the complexity of these fitting problems, with particular attention to cases where we can use queries in a natural query language over the sample to determine whether a sample is fittable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2606_01107 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | How (and when) can you fit examples to logic-based hypothesis classes over infinite structures? Benedikt, Michael Mansutti, Alessio Logic in Computer Science Machine Learning Logic We study fitting problems, sometimes called ``training problems'', where we have a finite sample consisting of inputs and outputs, and we want to know whether there is a function in a certain class that could produce these outputs, exactly or approximately, on the given inputs. We focus on the computational and descriptive complexity of fitting for logically-defined classes in common decidable structures, like the real ordered field and Presburger arithmetic, and also for broader classes defined via combinatorial or model-theoretic properties. We isolate the complexity of these fitting problems, with particular attention to cases where we can use queries in a natural query language over the sample to determine whether a sample is fittable. |
| title | How (and when) can you fit examples to logic-based hypothesis classes over infinite structures? |
| topic | Logic in Computer Science Machine Learning Logic |
| url | https://arxiv.org/abs/2606.01107 |