102 citations · 136 across the 12 of their papers we have counts for
12 papers
A Labelled Sample Compression Scheme of Size at Most Quadratic in the VC Dimension
Farnam Mansouri, Sandra Zilles
This paper presents a construction of a proper and stable labelled sample compression scheme of size $O(\VCD^2)$ for any finite concept class, where $\VCD$ denotes the Vapnik-Cherv…
Inferring Symbolic Automata
Dana Fisman, Hadar Frenkel, Sandra Zilles
We study the learnability of symbolic finite state automata (SFA), a model shown useful in many applications in software verification. The state-of-the-art literature on this topic…
On the Complexity of Symbolic Finite-State Automata
Dana Fisman, Hadar Frenkel, Sandra Zilles
We revisit the complexity of procedures on SFAs (such as intersection, emptiness, etc.) and analyze them according to the measures we find suitable for symbolic automata: the numbe…
Optimal Collusion-Free Teaching
David Kirkpatrick, Hans U. Simon, Sandra Zilles
Formal models of learning from teachers need to respect certain criteria to avoid collusion. The most commonly accepted notion of collusion-freeness was proposed by Goldman and Mat…
An Overview of Machine Teaching
Xiaojin Zhu, Adish Singla, Sandra Zilles +1
In this paper we try to organize machine teaching as a coherent set of ideas. Each idea is presented as varying along a dimension. The collection of dimensions then form the proble…
The Complexity of Learning Acyclic Conditional Preference Networks
Eisa Alanazi, Malek Mouhoub, Sandra Zilles
Learning of user preferences, as represented by, for example, Conditional Preference Networks (CP-nets), has become a core issue in AI research. Recent studies investigate learning…
An Empirical Study of the Effects of Spurious Transitions on Abstraction-based Heuristics
Mehdi Sadeqi, Robert C. Holte, Sandra Zilles
The efficient solution of state space search problems is often attempted by guiding search algorithms with heuristics (estimates of the distance from any state to the goal). A popu…
Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions
Jingwei Chen, Robert C. Holte, Sandra Zilles +1
It is well-known that any admissible unidirectional heuristic search algorithm must expand all states whose -value is smaller than the optimal solution cost when using a consist…
Preference-based Teaching
Ziyuan Gao, Christoph Ries, Hans Ulrich Simon +1
We introduce a new model of teaching named "preference-based teaching" and a corresponding complexity parameter---the preference-based teaching dimension (PBTD)---representing the…
Classifying the Arithmetical Complexity of Teaching Models
Achilles A. Beros, Ziyuan Gao, Sandra Zilles
This paper classifies the complexity of various teaching models by their position in the arithmetical hierarchy. In particular, we determine the arithmetical complexity of the inde…
Interactive Learning from Multiple Noisy Labels
Shankar Vembu, Sandra Zilles
Interactive learning is a process in which a machine learning algorithm is provided with meaningful, well-chosen examples as opposed to randomly chosen examples typical in standard…
Combining Models of Approximation with Partial Learning
Ziyuan Gao, Frank Stephan, Sandra Zilles
In Gold's framework of inductive inference, the model of partial learning requires the learner to output exactly one correct index for the target object and only the target object…