11 papers
Query Feedback and Teaching for Stable and Certifiable Language Generation
Farnam Mansouri, Alireza F. Pour, Grigoris Velegkas +1
Language generation in the limit studies whether a learner observing an enumeration of an unknown target language can eventually generate only valid, previously unseen elements. We…
Burning Signed Graphs
Shaun Fallat, Himanshu Gupta, Kamyar Khodamoradi +1
We introduce and analyze a new model of graph burning, in which two competing fires (coloured yellow and green) ignite vertices of a given signed graph and propagate along its edge…
Learning Shuffle Ideals with Membership Queries and Contrastive Examples
S. Mahmoud Mousawi, Pierluigi San Pietro, Sandra Zilles
This paper studies learning of shuffle ideals with membership queries as well as with contrastive queries---a form of membership query that reveals not only whether a selected word…
On the Semantics of Primary Cause in Hybrid Dynamic Domains
Shakil M. Khan, Asim Mehmood, Sandra Zilles
Reasoning about actual causes of observed effects is fundamental to the study of rationality. This important problem has been studied since the time of Aristotle, with formal mathe…
Active learning from positive and unlabeled examples
Farnam Mansouri, Sandra Zilles, Shai Ben-David
Learning from positive and unlabeled data (PU learning) is a weakly supervised variant of binary classification in which the learner receives labels only for (some) positively labe…
Learning Half-Spaces from Perturbed Contrastive Examples
Aryan Alavi Razavi Ravari, Farnam Mansouri, Yuxin Chen +3
We study learning under a two-step contrastive example oracle, as introduced by Mansouri et. al. (2025), where each queried (or sampled) labeled example is paired with an additiona…
Distance-based Learning of Hypertrees
Shaun Fallat, Kamyar Khodamoradi, David Kirkpatrick +3
We study the problem of learning hypergraphs with shortest-path queries (SP-queries), and present the first provably optimal online algorithm for a broad and natural class of hyper…
Positive Characteristic Sets for Relational Pattern Languages
S. Mahmoud Mousawi, Sandra Zilles
In the context of learning formal languages, data about an unknown target language L is given in terms of a set of (word,label) pairs, where a binary label indicates whether or not…
The Computational Complexity of Almost Stable Clustering with Penalties
Kamyar Khodamoradi, Farnam Mansouri, Sandra Zilles
We investigate the complexity of stable (or perturbation-resilient) instances of and clustering problems in metrics with smal…
Formal Models of Active Learning from Contrastive Examples
Farnam Mansouri, Hans U. Simon, Adish Singla +2
Machine learning can greatly benefit from providing learning algorithms with pairs of contrastive training examples -- typically pairs of instances that differ only slightly, yet h…
Common Benchmarks Undervalue the Generalization Power of Programmatic Policies
Amirhossein Rajabpour, Kiarash Aghakasiri, Sandra Zilles +1
Algorithms for learning programmatic representations for sequential decision-making problems are often evaluated on out-of-distribution (OOD) problems, with the common conclusion t…