Sandra Zilles

AAMAS Conference 2026 Conference Paper

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 mathematical accounts emerging recently. We live in a world where change due to actions can be both discrete and continuous, that is, hybrid. Yet, despite extensive research on actual causation, only few studies looked into causation with continuous change. Building on recent progress, in this paper we outline a definition of primary cause in a hybrid action-theoretic framework, namely the hybrid temporal situation calculus. Our definition formalizes causation through contributions, which can then be verified from a counterfactual perspective using a modified “but-for” test. We show that our definition of causation have some intuitively justifiable properties.

AAMAS Conference 2025 Conference Paper

Approximation Ratio for Preference Aggregation Using Tree CP-Nets

• Abu Mohammad Hammad Ali
• Daniel Ogundare
• Boting Yang
• Sandra Zilles

Aggregating preferences of multiple entities is a problem that has been studied in various models of preference representation, including Conditional Preference Networks (CP-nets). Since optimal aggregation of CP-nets (for a specific natural choice of objective function) is known to require exponential time, efficient approximation algorithms have been proposed in the literature, yet with very limited results on the corresponding approximation ratio. In this paper, we show that a very simple and efficient method yields a 4 3 -approximation for aggregating CP-nets from a proper superset of the set of all tree CP-nets—a well-studied class of CP-nets of relevance to many applications.

NeurIPS Conference 2025 Conference Paper

Formal Models of Active Learning from Contrastive Examples

• Farnam Mansouri
• Hans Simon
• Adish Singla
• Yuxin Chen
• Sandra Zilles

Machine learning can greatly benefit from providing learning algorithms with pairs of contrastive training examples---typically pairs of instances that differ only slightly, yet have different class labels. Intuitively, the difference in the instances helps explain the difference in the class labels. This paper proposes a theoretical framework in which the effect of various types of contrastive examples on active learners is studied formally. The focus is on the sample complexity of learning concept classes and how it is influenced by the choice of contrastive examples. We illustrate our results with geometric concept classes and classes of Boolean functions. Interestingly, we reveal a connection between learning from contrastive examples and the classical model of self-directed learning.

AAAI Conference 2024 Conference Paper

Approximation Algorithms for Preference Aggregation Using CP-Nets

• Abu Mohammad Hammad Ali
• Boting Yang
• Sandra Zilles

This paper studies the design and analysis of approximation algorithms for aggregating preferences over combinatorial domains, represented using Conditional Preference Networks (CP-nets). Its focus is on aggregating preferences over so-called swaps, for which optimal solutions in general are already known to be of exponential size. We first analyze a trivial 2-approximation algorithm that simply outputs the best of the given input preferences, and establish a structural condition under which the approximation ratio of this algorithm is improved to 4/3. We then propose a polynomial-time approximation algorithm whose outputs are provably no worse than those of the trivial algorithm, but often substantially better. A family of problem instances is presented for which our improved algorithm produces optimal solutions, while, for any ε, the trivial algorithm cannot attain a (2- ε)-approximation. These results may lead to the first polynomial-time approximation algorithm that solves the CP-net aggregation problem for swaps with an approximation ratio substantially better than 2.

TCS Journal 2024 Journal Article

The zero-visibility cops and robber game on graph products

• Yuan Xue
• Boting Yang
• Sandra Zilles

The zero-visibility cops and robber game is a variant of Cops and Robbers subject to the constraint that the cops have no information at any time about the location of the robber. We first study a partition problem in which for a given graph and an integer k, we want to find a partition of the vertex set such that the size of the boundary of the smaller subset in the partition is at most k while the size of this subset is as large as possible under some conditions. Then we apply such partitions to prove lower bounds on the zero-visibility cop numbers of graph products. We also investigate the monotonic zero-visibility cop numbers of graph products.

TMLR Journal 2024 Journal Article

Using Sum-Product Networks to Assess Uncertainty in Deep Active Learning

• Mohamadsadegh Khosravani
• Sandra Zilles

The success of deep active learning hinges on the choice of an effective acquisition function, which ranks not yet labeled data points according to their expected informativeness. Many acquisition functions are (partly) based on the uncertainty that the current model has about the class label of a point, yet there is no generally agreed upon strategy for computing such uncertainty. This paper proposes a new and very simple approach to computing uncertainty in deep active learning with a Convolutional Neural Network (CNN). The main idea is to use the feature representation extracted by the CNN as data for training a Sum-Product Network (SPN). Since SPNs are typically used for estimating the distribution of a dataset, they are well suited to the task of estimating class probabilities that can be used directly by standard acquisition functions such as max entropy and variational ratio. The effectiveness of our method is demonstrated in an experimental study on several standard benchmark datasets for image classification, where we compare it to various state-of-the-art methods for assessing uncertainty in deep active learning.

JMLR Journal 2023 Journal Article

On Batch Teaching Without Collusion

• Shaun Fallat
• David Kirkpatrick
• Hans U. Simon
• Abolghasem Soltani
• Sandra Zilles

Formal models of learning from teachers need to respect certain criteria to avoid collusion. The most commonly accepted notion of collusion-avoidance was proposed by Goldman and Mathias (1996), and various teaching models obeying their criterion have been studied. For each model $M$ and each concept class $\mathcal{C}$, a parameter $M$-TD$(\mathcal{C})$ refers to the teaching dimension of concept class $\mathcal{C}$ in model $M$---defined to be the number of examples required for teaching a concept, in the worst case over all concepts in $\mathcal{C}$. This paper introduces a new model of teaching, called no-clash teaching, together with the corresponding parameter NCTD$(\mathcal{C})$. No-clash teaching is provably optimal in the strong sense that, given any concept class $\mathcal{C}$ and any model $M$ obeying Goldman and Mathias's collusion-avoidance criterion, one obtains NCTD$(\mathcal{C})\le M$-TD$(\mathcal{C})$. We also study a corresponding notion NCTD$^+$ for the case of learning from positive data only, establish useful bounds on NCTD and NCTD$^+$, and discuss relations of these parameters to other complexity parameters of interest in computational learning theory. We further argue that Goldman and Mathias's collusion-avoidance criterion may in some settings be too weak in that it admits certain forms of interaction between teacher and learner that could be considered collusion in practice. Therefore, we introduce a strictly stronger notion of collusion-avoidance and demonstrate that the well-studied notion of Preference-based Teaching is optimal among all teaching schemes that are strongly collusion-avoiding on all finite subsets of a given concept class. [abs] [ pdf ][ bib ] &copy JMLR 2023. ( edit, beta )

CSL Conference 2022 Conference Paper

Inferring Symbolic Automata

• Dana Fisman
• Hadar Frenkel
• Sandra Zilles

We study the learnability of symbolic finite state automata, a model shown useful in many applications in software verification. The state-of-the-art literature on this topic follows the query learning paradigm, and so far all obtained results are positive. We provide a necessary condition for efficient learnability of SFAs in this paradigm, from which we obtain the first negative result. The main focus of our work lies in the learnability of SFAs under the paradigm of identification in the limit using polynomial time and data. We provide a necessary condition and a sufficient condition for efficient learnability of SFAs in this paradigm, from which we derive a positive and a negative result.

NeurIPS Conference 2022 Conference Paper

On Batch Teaching with Sample Complexity Bounded by VCD

• Farnam Mansouri
• Hans Simon
• Adish Singla
• Sandra Zilles

In machine teaching, a concept is represented by (and inferred from) a small number of labeled examples. Various teaching models in the literature cast the interaction between teacher and learner in a way to obtain a small complexity (in terms of the number of examples required for teaching a concept) while obeying certain constraints that are meant to prevent unfair collusion between teacher and learner. In recent years, one major research goal has been to show interesting relationships between teaching complexity and the VC-dimension (VCD). So far, the only interesting relationship known from batch teaching settings is an upper bound quadratic in the VCD, on a parameter called recursive teaching dimension. The only known upper bound on teaching complexity that is linear in VCD was obtained in a model of teaching with sequences rather than batches. This paper is the first to provide an upper bound of VCD on a batch teaching complexity parameter. This parameter, called STDmin, is introduced here as a model of teaching that intuitively incorporates a notion of ``importance'' of an example for a concept. In designing the STDmin teaching model, we argue that the standard notion of collusion-freeness from the literature may be inadequate for certain applications; we hence propose three desirable properties of teaching complexity and demonstrate that they are satisfied by STDmin.

AAAI Conference 2021 Conference Paper

Precision-based Boosting

• Mohammad Hossein Nikravan
• Marjan Movahedan
• Sandra Zilles

AdaBoost is a highly popular ensemble classification method for which many variants have been published. This paper proposes a generic refinement of all of these AdaBoost variants. Instead of assigning weights based on the total error of the base classifiers (as in AdaBoost), our method uses classspecific error rates. On instance x it assigns a higher weight to a classifier predicting label y on x, if that classifier is less likely to make a mistake when it predicts class y. Like Ada- Boost, our method is guaranteed to boost weak learners into strong learners. An empirical study on AdaBoost and one of its multi-class versions, SAMME, demonstrates the superiority of our method on datasets with more than 1, 000 instances as well as on datasets with more than three classes.

IJCAI Conference 2020 Conference Paper

Combining Direct Trust and Indirect Trust in Multi-Agent Systems

• Elham Parhizkar
• Mohammad Hossein Nikravan
• Robert C. Holte
• Sandra Zilles

To assess the trustworthiness of an agent in a multi-agent system, one often combines two types of trust information: direct trust information derived from one's own interactions with that agent, and indirect trust information based on advice from other agents. This paper provides the first systematic study on when it is beneficial to combine these two types of trust as opposed to relying on only one of them. Our large-scale experimental study shows that strong methods for computing indirect trust make direct trust redundant in a surprisingly wide variety of scenarios. Further, a new method for the combination of the two trust types is proposed that, in the remaining scenarios, outperforms the ones known from the literature.

TCS Journal 2020 Journal Article

Finitely distinguishable erasing pattern languages

• Fahimeh Bayeh
• Ziyuan Gao
• Sandra Zilles

Pattern languages have been an object of study in various subfields of computer science for decades. This paper introduces and studies a decision problem on patterns called the finite distinguishability problem: given a pattern π, are there finite sets T + and T − of strings such that the only pattern language containing all strings in T + and none of the strings in T − is the language generated by π? This problem is related to the complexity of teacher-directed learning, as studied in computational learning theory, as well as to the long-standing open question whether the equivalence of two patterns is decidable. We show that finite distinguishability is decidable if the underlying alphabet is of size other than 2 or 3, and provide a number of related results, such as (i) partial solutions for alphabet sizes 2 and 3, and (ii) decidability proofs for variants of the problem for special subclasses of patterns, namely, regular, 1-variable, and non-cross patterns. For the same subclasses, we further determine the values of two complexity parameters in teacher-directed learning, namely the teaching dimension and the recursive teaching dimension.

AIJ Journal 2020 Journal Article

The complexity of exact learning of acyclic conditional preference networks from swap examples

• 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 of CP-nets from randomly chosen examples or from membership and equivalence queries. To assess the optimality of learning algorithms as well as to better understand the combinatorial structure of classes of CP-nets, it is helpful to calculate certain learning-theoretic information complexity parameters. This article focuses on the frequently studied case of exact learning from so-called swap examples, which express preferences among objects that differ in only one attribute. It presents bounds on or exact values of some well-studied information complexity parameters, namely the VC dimension, the teaching dimension, and the recursive teaching dimension, for classes of acyclic CP-nets. We further provide algorithms that exactly learn tree-structured and general acyclic CP-nets from membership queries. Using our results on complexity parameters, we prove that our algorithms, as well as another query learning algorithm for acyclic CP-nets presented in the literature, are near-optimal.

IJCAI Conference 2019 Conference Paper

Indirect Trust is Simple to Establish

• Elham Parhizkar
• Mohammad Hossein Nikravan
• Sandra Zilles

In systems with multiple potentially deceptive agents, any single agent may have to assess the trustworthiness of other agents in order to decide with which agents to interact. In this context, indirect trust refers to trust established through third-party advice. Since the advisers themselves may be deceptive or unreliable, agents need a mechanism to assess and properly incorporate advice. We evaluate existing state-of-the-art methods for computing indirect trust in numerous simulations, demonstrating that the best ones tend to be of prohibitively large complexity. We propose a new and easy to implement method for computing indirect trust, based on a simple prediction with expert advice strategy as is often used in online learning. This method either competes with or outperforms all tested systems in the vast majority of the settings we simulated, while scaling substantially better. Our results demonstrate that existing systems for computing indirect trust are overly complex; the problem can be solved much more efficiently than the literature suggests.

AAAI Conference 2019 Conference Paper

On the Optimal Efficiency of Cost-Algebraic A*

• Robert C. Holte
• Sandra Zilles

Edelkamp et al. (2005) proved that A*, given an admissible heuristic, is guaranteed to return an optimal solution in any cost algebra, not just in the traditional shortest path setting. In this paper, we investigate cost-algebraic A*’s optimal efficiency: in the cost-algebraic setting, under what conditions is A* guaranteed to expand the fewest possible states? In the traditional setting, this question was examined in detail by Dechter & Pearl (1985). They identified five different situations in which A* was optimally efficient. We show that three of them continue to hold in the cost-algebraic setting, but that one does not. We also show that one of them is false, it does not hold even in the traditional setting. We introduce an alternative that does hold in the cost-algebraic setting. Finally, we show that a well-known result due to Nilsson does not hold in the general cost-algebraic setting but does hold in a slightly less general setting.

TCS Journal 2018 Journal Article

On the teaching complexity of linear sets

• Ziyuan Gao
• Hans Ulrich Simon
• Sandra Zilles

Linear sets are the building blocks of semilinear sets, which are in turn closely connected to automata theory and formal languages. Prior work has investigated the learnability of linear sets and semilinear sets in three models – Valiant's PAC-learning model, Gold's learning in the limit model, and Angluin's query learning model. This paper considers teacher–learner models of learning families of linear sets, in which a benevolent teacher presents a set of labelled examples to the learner. First, we study the classical teaching model, in which a teacher must successfully teach any consistent learner. Second, we will apply a generalisation of the recently introduced recursive teaching model to several infinite classes of linear sets, and show that thus the maximum sample complexity of teaching these classes can be drastically reduced compared to classical teaching. To this end, a major focus of the paper will be on determining two relevant teaching parameters, the teaching dimension and recursive teaching dimension, for various families of linear sets.

I&C Journal 2017 Journal Article

Distinguishing pattern languages with membership examples

• Ziyuan Gao
• Zeinab Mazadi
• Regan Meloche
• Hans Ulrich Simon
• Sandra Zilles

This article determines two learning-theoretic combinatorial parameters, the teaching dimension and the recursive teaching dimension, for various families of pattern languages over alphabets of varying size. Our results and formal proofs are of relevance to recent studies in computational learning theory as well as in formal language theory. This is an expanded and corrected version of an earlier paper by Mazadi et al. (2014).

IJCAI Conference 2017 Conference Paper

Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions

• Jingwei Chen
• Robert C. Holte
• Sandra Zilles
• Nathan R. Sturtevant

It is well-known that any admissible unidirectional heuristic search algorithm must expand all states whose f-value is smaller than the optimal solution cost when using a consistent heuristic. Such states are called “surely expanded” (s. e. ). A recent study characterized s. e. pairs of states for bidirectional search with consistent heuristics: if a pair of states is s. e. then at least one of the two states must be expanded. This paper derives a lower bound, VC, on the minimum number of expansions required to cover all s. e. pairs, and present a new admissible front-to-end bidirectional heuristic search algorithm, Near-Optimal Bidirectional Search (NBS), that is guaranteed to do no more than 2VC expansions. We further prove that no admissible front-to-end algorithm has a worst case better than 2VC. Experimental results show that NBS competes with or outperforms existing bidirectional search algorithms, and often outperforms A* as well.

JMLR Journal 2017 Journal Article

Preference-based Teaching

• Ziyuan Gao
• Christoph Ries
• Hans U. Simon
• Sandra Zilles

We introduce a new model of teaching named preference-based teaching and a corresponding complexity parameter---the preference-based teaching dimension (PBTD)---representing the worst-case number of examples needed to teach any concept in a given concept class. Although the PBTD coincides with the well- known recursive teaching dimension (RTD) on finite classes, it is radically different on infinite ones: the RTD becomes infinite already for trivial infinite classes (such as half- intervals) whereas the PBTD evaluates to reasonably small values for a wide collection of infinite classes including classes consisting of so-called closed sets w.r.t. a given closure operator, including various classes related to linear sets over $\mathbb{N}_0$ (whose RTD had been studied quite recently) and including the class of Euclidean half-spaces. On top of presenting these concrete results, we provide the reader with a theoretical framework (of a combinatorial flavor) which helps to derive bounds on the PBTD. [abs] [ pdf ][ bib ] &copy JMLR 2017. ( edit, beta )

ICAPS Conference 2017 Conference Paper

Sufficient Conditions for Node Expansion in Bidirectional Heuristic Search

• Jürgen Eckerle
• Jingwei Chen
• Nathan R. Sturtevant
• Sandra Zilles
• Robert C. Holte

In this paper we study bidirectional state space search with consistent heuristics, with a focus on obtaining sufficient conditions for node expansion, that is, conditions characterizing nodes that must be expanded by any admissible bidirectional search algorithm. We provide such conditions for front-to-front and front-to-end bidirectional search. The sufficient conditions are used to prove that the front-to-front bidirectional search algorithm BDS1 is optimally efficient, in terms of node expansion, among a broad class of bidirectional search algorithms, for a specific class of problem instances. Dechter and Pearl's well-known result on sufficient conditions for node expansion by unidirectional algorithms such as A* is shown to be a special case of our results.

IJCAI Conference 2016 Conference Paper

Heuristic Subset Selection in Classical Planning

• Levi H. S. Lelis
• Santiago Franco
• Marvin Abisrror
• Mike Barley
• Sandra Zilles
• Robert C. Holte

In this paper we present greedy methods for selecting a subset of heuristic functions for guiding A* search. Our methods are able to optimize various objective functions while selecting a subset from a pool of up to thousands of heuristics. Specifically, our methods minimize approximations of A*'s search tree size, and approximations of A*'s running time. We show empirically that our methods can outperform state-of-the-art planners for deterministic optimal planning.

TCS Journal 2016 Journal Article

Order compression schemes

• Malte Darnstädt
• Thorsten Kiss
• Hans Ulrich Simon
• Sandra Zilles

Sample compression schemes are schemes for “encoding” a set of examples in a small subset of examples. The long-standing open sample compression conjecture states that, for any concept class C of VC-dimension d, there is a sample compression scheme in which samples for concepts in C are compressed to samples of size at most d. We show that every order over C induces a special type of sample compression scheme for C, which we call order compression scheme. It turns out that order compression schemes can compress to samples of size at most d if C is maximum, intersection-closed, a Dudley class, or of VC-dimension 1 – and thus in most cases for which the sample compression conjecture is known to be true. Since order compression schemes are much simpler than sample compression schemes in general, their study seems to be a promising step towards resolving the sample compression conjecture. We reveal a number of fundamental properties of order compression schemes, which are helpful in such a study. In particular, order compression schemes exhibit interesting graph-theoretic properties as well as connections to the theory of learning from teachers. To obtain small compressed sets, order compression schemes for a concept class C must often use a proper superset H ⊃ C as a hypothesis space. We thus further compare order compression schemes for C to order compression schemes for such hypothesis spaces, leading to a study of a number of mutually related combinatorial parameters specifying compressibility.

TCS Journal 2016 Journal Article

Partial learning of recursively enumerable languages

• Ziyuan Gao
• Frank Stephan
• Sandra Zilles

This paper studies several typical learning criteria in the model of partial learning of r. e. sets in the recursion-theoretic framework of inductive inference. Its main contribution is a complete picture of how the criteria of confidence, consistency and conservativeness in partial learning of r. e. sets separate, also in relation to basic criteria of learning in the limit. Thus this paper constitutes a substantial extension to prior work on partial learning. Further highlights of this work are very insightful characterisations of some of the inference criteria studied, leading to interesting consequences about the structural properties of the collection of classes learnable under these criteria. In particular a class is consistently partially learnable iff it is a subclass of a uniformly recursive family.

AIJ Journal 2016 Journal Article

Predicting optimal solution costs with bidirectional stratified sampling in regular search spaces

• Levi H.S. Lelis
• Roni Stern
• Shahab Jabbari Arfaee
• Sandra Zilles
• Ariel Felner
• Robert C. Holte

Optimal planning and heuristic search systems solve state-space search problems by finding a least-cost path from start to goal. As a byproduct of having an optimal path they also determine the optimal solution cost. In this paper we focus on the problem of determining the optimal solution cost for a state-space search problem directly, i. e. , without actually finding a solution path of that cost. We present an algorithm, BiSS, which is a hybrid of bidirectional search and stratified sampling that produces accurate estimates of the optimal solution cost. BiSS is guaranteed to return the optimal solution cost in the limit as the sample size goes to infinity. We show empirically that BiSS produces accurate predictions in several domains. In addition, we show that BiSS scales to state spaces much larger than can be solved optimally. In particular, we estimate the average solution cost for the 6 × 6, 7 × 7, and 8 × 8 Sliding-Tile puzzle and provide indirect evidence that these estimates are accurate. As a practical application of BiSS, we show how to use its predictions to reduce the time required by another system to learn strong heuristic functions from days to minutes in the domains tested.

IJCAI Conference 2016 Conference Paper

The Complexity of Learning Acyclic CP-Nets

• Eisa Alanazi
• Malek Mouhoub
• Sandra Zilles

Learning of user preferences has become a core issue in AI research. For example, recent studies investigate learning of Conditional Preference Networks (CP-nets) from partial information. To assess the optimality of learning algorithms as well as to better understand the combinatorial structure of CP-net classes, it is helpful to calculate certain learning-theoretic information complexity parameters. This paper provides theoretical justification for exact values (or in some cases bounds) of some of the most central information complexity parameters, namely the VC dimension, the (recursive) teaching dimension, the self-directed learning complexity, and the optimal mistake bound, for classes of acyclic CP-nets. We further provide an algorithm that learns tree-structured CP-nets from membership queries. Using our results on complexity parameters, we can assess the optimality of our algorithm as well as that of another query learning algorithm for acyclic CP-nets presented in the literature.

TCS Journal 2014 Journal Article

Algebraic methods proving Sauer's bound for teaching complexity

• Rahim Samei
• Pavel Semukhin
• Boting Yang
• Sandra Zilles

This paper establishes an upper bound on the size of a concept class with given recursive teaching dimension (RTD, a teaching complexity parameter). The upper bound coincides with Sauer's well-known bound on classes with a fixed VC-dimension. Our result thus supports the recently emerging conjecture that the combinatorics of VC-dimension and those of teaching complexity are intrinsically interlinked. We further introduce and study RTD-maximum classes (whose size meets the upper bound) and RTD-maximal classes (whose RTD increases if a concept is added to them), showing similarities but also differences to the corresponding notions for VC-dimension. Another contribution is a set of new results on maximal classes of a given VC-dimension. Methodologically, our contribution is the successful application of algebraic techniques, which we use to obtain a purely algebraic characterization of teaching sets (sample sets that uniquely identify a concept in a given concept class) and to prove our analog of Sauer's bound for RTD. Such techniques have been used before to prove results relevant to computational learning theory, e. g. , by Smolensky [13], but are not standard in the field.

JMLR Journal 2014 Journal Article

Recursive Teaching Dimension, VC-Dimension and Sample Compression

• Thorsten Doliwa
• Gaojian Fan
• Hans Ulrich Simon
• Sandra Zilles

This paper is concerned with various combinatorial parameters of classes that can be learned from a small set of examples. We show that the recursive teaching dimension, recently introduced by Zilles et al. (2008), is strongly connected to known complexity notions in machine learning, e.g., the self- directed learning complexity and the VC-dimension. To the best of our knowledge these are the first results unveiling such relations between teaching and query learning as well as between teaching and the VC-dimension. It will turn out that for many natural classes the RTD is upper-bounded by the VCD, e.g., classes of VC-dimension 1, intersection-closed classes and finite maximum classes. However, we will also show that there are certain (but rare) classes for which the recursive teaching dimension exceeds the VC-dimension. Moreover, for maximum classes, the combinatorial structure induced by the RTD, called teaching plan, is highly similar to the structure of sample compression schemes. Indeed one can transform any repetition-free teaching plan for a maximum class $\mathcal{C}$ into an unlabeled sample compression scheme for $\mathcal{C}$ and vice versa, while the latter is produced by (i) the corner- peeling algorithm of Rubinstein and Rubinstein (2012) and (ii) the tail matching algorithm of Kuzmin and Warmuth (2007). [abs] [ pdf ][ bib ] &copy JMLR 2014. ( edit, beta )

TCS Journal 2013 Journal Article

Learning without coding

• Sanjay Jain
• Samuel E. Moelius
• Sandra Zilles

Iterative learning is a model of language learning from positive data, due to Wiehagen. When compared to a learner in Gold’s original model of language learning from positive data, an iterative learner can be thought of as memory-limited. However, an iterative learner can memorize some input elements by coding them into the syntax of its hypotheses. A main concern of this paper is: to what extent are such coding tricks necessary? One means of preventing some such coding tricks is to require that the hypothesis space used be free of redundancy, i. e. , that it be 1–1. In this context, we make the following contributions. By extending a result of Lange and Zeugmann, we show that many interesting and non-trivial classes of languages can be iteratively identified using a Friedberg numbering as the hypothesis space. (Recall that a Friedberg numbering is a 1–1 effective numbering of all computably enumerable sets.) An example of such a class is the class of pattern languages over an arbitrary alphabet. On the other hand, we show that there exists an iteratively identifiable class of languages that cannot be iteratively identified using any 1–1 effective numbering as the hypothesis space. We also consider an iterative-like learning model in which the computational component of the learner is modeled as an enumeration operator, as opposed to a partial computable function. In this new model, there are no hypotheses, and, thus, no syntax in which the learner can encode what elements it has or has not yet seen. We show that there exists a class of languages that can be identified under this new model, but that cannot be iteratively identified. On the other hand, we show that there exists a class of languages that cannot be identified under this new model, but that can be iteratively identified using a Friedberg numbering as the hypothesis space.

AIJ Journal 2013 Journal Article

Predicting the size of IDA*ʼs search tree

• Levi H.S. Lelis
• Sandra Zilles
• Robert C. Holte

Korf, Reid and Edelkamp initiated a line of research for developing methods (KRE and later CDP) that predict the number of nodes expanded by IDA* for a given start state and cost bound. Independently, Chen developed a method (SS) that can also be used to predict the number of nodes expanded by IDA*. In this paper we improve both of these prediction methods. First, we present ϵ-truncation, a method that acts as a preprocessing step and improves CDPʼs prediction accuracy. Second and orthogonally to ϵ-truncation, we present a variant of CDP that can be orders of magnitude faster than CDP while producing exactly the same predictions. Third, we show how ideas developed in the KRE line of research can be used to improve the predictions produced by SS. Finally, we make an empirical comparison between our new enhanced versions of CDP and SS. Our experimental results suggest that CDP is suitable for applications that require less accurate but fast predictions, while SS is suitable for applications that require more accurate predictions but can afford more computation time.

AAAI Conference 2012 Conference Paper

Fast and Accurate Predictions of IDA*’s Performance

• Levi Lelis
• Sandra Zilles
• Robert Holte

Korf, Reid and Edelkamp initiated a line of research for developing methods (KRE and later CDP) that predict the number of nodes expanded by IDA* for a given start state and cost bound. Independent of that, Chen developed a method (SS) that can also be used to predict the number of nodes expanded by IDA*. In this paper we advance these prediction methods. First, we develop a variant of CDP that can be orders of magnitude faster than CDP while producing exactly the same predictions. Second, we show how ideas developed in the KRE line of research can be used to substantially improve the predictions produced by SS. Third, we make an empirical comparison between our new enhanced versions of CDP and SS. Our experimental results point out that CDP is suitable for applications that require less accurate but very fast predictions, while SS is suitable for applications that require more accurate predictions but allow more computation time.

SoCS Conference 2012 Conference Paper

Learning Heuristic Functions Faster by Using Predicted Solution Costs

• Levi H. S. Lelis
• Shahab Jabbari Arfaee
• Sandra Zilles
• Robert C. Holte

Jabbari Arfaee, Zilles, and Holte presented the bootstrap learning system, a system that learns strong heuristic functions for state-space problems. They showed that IDA* with a bootstrap heuristic is able to quickly find near-optimal solutions in several problem domains. However, the process the bootstrap method uses to learn heuristic functions is time-consuming: it is on the order of days. In this paper we present a learning system that uses an approximation method instead of an exact one to generate the training set required to learn heuristics. We showed recently that solution costs can often be quickly and accurately predicted without having to actually find a solution. In this paper we apply this idea to speedup the process of learning heuristics. In contrast with other learning approaches that use search algorithms to solve problem instances to generate the training set, our system uses a solution cost predictor. We reduce the time required to learn strong heuristics from days to minutes on the domains tested.

ICAPS Conference 2012 Conference Paper

Predicting Optimal Solution Cost with Bidirectional Stratified Sampling

• Levi H. S. Lelis
• Roni Stern
• Ariel Felner
• Sandra Zilles
• Robert C. Holte

Optimal planning and heuristic search systems solve state-space searchproblems by finding a least-cost path from start to goal. As a byproduct of having an optimal path they also determine the optimal solution cost. In this paper we focus on the problem of determining the optimal solution cost for a state-space search problem directly, i. e. without actually finding a solution path of that cost. We present an efficient algorithm, BiSS, based on ideas of bidirectional search and stratified sampling that produces accurate estimates of the optimal solution cost. Our method is guaranteed to return the optimal solution cost in the limit as the sample size goes to infinity. We show empirically that our method makes accurate predictions in several domains. In addition, we show that our method scales to state spaces much larger than can be solved optimally. In particular, we estimate the average solution cost for the 6x6, 7x7, and 8x8 Sliding-Tile Puzzle and provide indirect evidence that these estimates are accurate.

SoCS Conference 2012 Conference Paper

Predicting Optimal Solution Cost with Bidirectional Stratified Sampling (Abstract)

• Levi H. S. Lelis
• Roni Stern
• Ariel Felner
• Sandra Zilles
• Robert C. Holte

Optimal planning and heuristic search systems solve state-space searchproblems by finding a least-cost path from start to goal. As a byproduct of having an optimal path they also determine the optimal solution cost. In this paper we focus on the problem of determining the optimal solution cost for a state-space search problem directly, i. e. , without actually finding a solution path of that cost. We present an efficient algorithm, BiSS, based on ideas of bidirectional search and stratified sampling that produces accurate estimates of the optimal solution cost. Our method is guaranteed to return the optimal solution cost in the limit as the sample size goes to infinity.

SoCS Conference 2011 Conference Paper

Improved Prediction of IDA*'s Performance via Epsilon-Truncation

• Levi H. S. Lelis
• Sandra Zilles
• Robert C. Holte

Korf, Reid, and Edelkamp launched a line of research aimed at predicting how many nodes IDA* will expand with a given cost bound. This paper advances this line of research in three ways. First, we identify a source of prediction error that has hitherto been overlooked. We call it the ``discretization effect

AIJ Journal 2011 Journal Article

Learning heuristic functions for large state spaces

• Shahab Jabbari Arfaee
• Sandra Zilles
• Robert C. Holte

We investigate the use of machine learning to create effective heuristics for search algorithms such as IDA ⁎ or heuristic-search planners such as FF. Our method aims to generate a sequence of heuristics from a given weak heuristic h 0 and a set of unsolved training instances using a bootstrapping procedure. The training instances that can be solved using h 0 provide training examples for a learning algorithm that produces a heuristic h 1 that is expected to be stronger than h 0. If h 0 is so weak that it cannot solve any of the given instances we use random walks backward from the goal state to create a sequence of successively more difficult training instances starting with ones that are guaranteed to be solvable by h 0. The bootstrap process is then repeated using h i in lieu of h i − 1 until a sufficiently strong heuristic is produced. We test this method on the 24-sliding-tile puzzle, the 35-pancake puzzle, Rubikʼs Cube, and the 20-blocks world. In every case our method produces a heuristic that allows IDA ⁎ to solve randomly generated problem instances quickly with solutions close to optimal. The total time for the bootstrap process to create strong heuristics for these large state spaces is on the order of days. To make the process effective when only a single problem instance needs to be solved, we present a variation in which the bootstrap learning of new heuristics is interleaved with problem-solving using the initial heuristic and whatever heuristics have been learned so far. This substantially reduces the total time needed to solve a single instance, while the solutions obtained are still close to optimal.

JMLR Journal 2011 Journal Article

Models of Cooperative Teaching and Learning

• Sandra Zilles
• Steffen Lange
• Robert Holte
• Martin Zinkevich

While most supervised machine learning models assume that training examples are sampled at random or adversarially, this article is concerned with models of learning from a cooperative teacher that selects "helpful" training examples. The number of training examples a learner needs for identifying a concept in a given class C of possible target concepts (sample complexity of C ) is lower in models assuming such teachers, that is, "helpful" examples can speed up the learning process. The problem of how a teacher and a learner can cooperate in order to reduce the sample complexity, yet without using "coding tricks", has been widely addressed. Nevertheless, the resulting teaching and learning protocols do not seem to make the teacher select intuitively "helpful" examples. The two models introduced in this paper are built on what we call subset teaching sets and recursive teaching sets. They extend previous models of teaching by letting both the teacher and the learner exploit knowing that the partner is cooperative. For this purpose, we introduce a new notion of "coding trick"/"collusion". We show how both resulting sample complexity measures (the subset teaching dimension and the recursive teaching dimension ) can be arbitrarily lower than the classic teaching dimension and known variants thereof, without using coding tricks. For instance, monomials can be taught with only two examples independent of the number of variables. The subset teaching dimension turns out to be nonmonotonic with respect to subclasses of concept classes. We discuss why this nonmonotonicity might be inherent in many interesting cooperative teaching and learning scenarios. [abs] [ pdf ][ bib ] &copy JMLR 2011. ( edit, beta )

TCS Journal 2011 Journal Article

Preface

• Gábor Lugosi
• Sandra Zilles

AAAI Conference 2011 Conference Paper

Time Complexity of Iterative-Deepening A*: The Informativeness Pathology (Abstract)

• Levi Lelis
• Sandra Zilles
• Robert Holte

SoCS Conference 2010 Conference Paper

Bootstrap Learning of Heuristic Functions

• Shahab Jabbari Arfaee
• Sandra Zilles
• Robert C. Holte

search algorithms such as IDA* or heuristic-search planners. Our method aims to generate a strong heuristic from a given weak heuristic h0 through bootstrapping. The "easy" problem instances that can be solved using h0 provide training examples for a learning algorithm that produces a heuristic h1 that is expected to be stronger than h0. If h0 is too weak to solve any of the given instances we use a random walk technique to create a sequence of successively more difficult instances starting with ones that are solvable by h0. The bootstrap process is then repeated using hi in lieu of hi-1 until a sufficiently strong heuristic is produced. We test our method on the 15- and 24-sliding tile puzzles, the 17- and 24-pancake puzzles, and the 15- and 20-blocks world. In every case our method produces a heuristic that allows IDA* to solve randomly generated problem instances extremely quickly with solutions very close to optimal.

TCS Journal 2010 Journal Article

Incremental learning with temporary memory

• Sanjay Jain
• Steffen Lange
• Samuel E. Moelius
• Sandra Zilles

In the inductive inference framework of learning in the limit, a variation of the bounded example memory ( Bem ) language learning model is considered. Intuitively, the new model constrains the learner’s memory not only in how much data may be stored, but also in how long those data may be stored without being refreshed. More specifically, the model requires that, if the learner commits an example x to memory, and x is not presented to the learner again thereafter, then eventually the learner forgets x, i. e. , eventually x no longer appears in the learner’s memory. This model is called temporary example memory ( Tem ) learning. Many interesting results concerning the Tem -learning model are presented. For example, there exists a class of languages that can be identified by memorizing k + 1 examples in the Tem sense, but that cannot be identified by memorizing k examples in the Bem sense. On the other hand, there exists a class of languages that can be identified by memorizing just one example in the Bem sense, but that cannot be identified by memorizing any number of examples in the Tem sense. Results are also presented concerning the special case of learning classes of infinite languages.

I&C Journal 2010 Journal Article

Models of active learning in group-structured state spaces

• Gábor Bartók
• Csaba Szepesvári
• Sandra Zilles

We investigate the problem of learning the transition dynamics of deterministic, discrete-state environments. We assume that an agent exploring such an environment is able to perform actions (from a finite set of actions) in the environment and to sense the state changes. The question investigated is whether the agent can learn the dynamics without visiting all states. Such a goal is unrealistic in general, hence we assume that the environment has structural properties an agent might exploit. In particular, we assume that the set of all action sequences forms an algebraic group. We introduce a learning model in different variants and study under which circumstances the corresponding “group-structured environments” can be learned efficiently by experimenting with group generators (actions). It turns out that for some classes of such environments the choice of actions given to the agent determines if efficient learning is possible. Negative results are presented, even without efficiency constraints, for rather general classes of groups, showing that even with group structure, learning an environment from partial information is far from trivial. However, positive results for special subclasses of Abelian groups turn out to be a good starting point for the design of efficient learning algorithms based on structured representations.

AIJ Journal 2010 Journal Article

The computational complexity of avoiding spurious states in state space abstraction

• Sandra Zilles
• Robert C. Holte

Abstraction is a powerful technique for speeding up planning and search. A problem that can arise in using abstraction is the generation of abstract states, called spurious states, from which the goal state is reachable in the abstract space but for which there is no corresponding state in the original space from which the goal state can be reached. Spurious states can be harmful, in practice, because they can create artificial shortcuts in the abstract space that slow down planning and search, and they can greatly increase the memory needed to store heuristic information derived from the abstract space (e. g. , pattern databases). This paper analyzes the computational complexity of creating abstractions that do not contain spurious states. We define a property—the downward path preserving property (DPP)—that formally captures the notion that an abstraction does not result in spurious states. We then analyze the computational complexity of (i) testing the downward path preserving property for a given state space and abstraction and of (ii) determining whether this property is achievable at all for a given state space. The strong hardness results shown carry over to typical description languages for planning problems, including sas + and propositional strips. On the positive side, we identify and illustrate formal conditions under which finding downward path preserving abstractions is provably tractable.

TCS Journal 2008 Journal Article

Foreword

• John Case
• Takeshi Shinohara
• Thomas Zeugmann
• Sandra Zilles

TCS Journal 2008 Journal Article

Learning indexed families of recursive languages from positive data: A survey

• Steffen Lange
• Thomas Zeugmann
• Sandra Zilles

In the past 40 years, research on inductive inference has developed along different lines, e. g. , in the formalizations used, and in the classes of target concepts considered. One common root of many of these formalizations is Gold’s model of identification in the limit. This model has been studied for learning recursive functions, recursively enumerable languages, and recursive languages, reflecting different aspects of machine learning, artificial intelligence, complexity theory, and recursion theory. One line of research focuses on indexed families of recursive languages — classes of recursive languages described in a representation scheme for which the question of membership for any string in any of the given languages is effectively decidable with a uniform procedure. Such language classes are of interest because of their naturalness. The survey at hand picks out important studies on learning indexed families (including basic as well as recent research), summarizes and illustrates the corresponding results, and points out links to related fields such as grammatical inference, machine learning, and artificial intelligence in general.

TCS Journal 2008 Journal Article

Learning recursive functions: A survey

• Thomas Zeugmann
• Sandra Zilles

Studying the learnability of classes of recursive functions has attracted considerable interest for at least four decades. Starting with Gold’s (1967) model of learning in the limit, many variations, modifications and extensions have been proposed. These models differ in some of the following: the mode of convergence, the requirements intermediate hypotheses have to fulfill, the set of allowed learning strategies, the source of information available to the learner during the learning process, the set of admissible hypothesis spaces, and the learning goals. A considerable amount of work done in this field has been devoted to the characterization of function classes that can be learned in a given model, the influence of natural, intuitive postulates on the resulting learning power, the incorporation of randomness into the learning process, the complexity of learning, among others. On the occasion of Rolf Wiehagen’s 60th birthday, the last four decades of research in that area are surveyed, with a special focus on Rolf Wiehagen’s work, which has made him one of the most influential scientists in the theory of learning recursive functions.

TCS Journal 2007 Journal Article

A general comparison of language learning from examples and from queries

• Sanjay Jain
• Steffen Lange
• Sandra Zilles

In language learning, strong relationships between Gold-style models and query models have recently been observed: in some quite general setting Gold-style learners can be replaced by query learners and vice versa, without loss of learning capabilities. These ‘equalities’ hold in the context of learning indexable classes of recursive languages. Former studies on Gold-style learning of such indexable classes have shown that, in many settings, the enumerability of the target class and the recursiveness of its languages are crucial for learnability. Moreover, studying query learning, non-indexable classes have been mainly neglected up to now. So it is conceivable that the recently observed relations between Gold-style and query learning are not due to common structures in the learning processes in both models, but rather to the enumerability of the target classes or the recursiveness of their languages. In this paper, the analysis is lifted onto the context of learning arbitrary classes of recursively enumerable languages. Still, strong relationships between the approaches of Gold-style and query learning are proven, but there are significant changes to the former results. Though in many cases learners of one type can still be replaced by learners of the other type, in general this does not remain valid vice versa. All results hold even for learning classes of recursive languages, which indicates that the recursiveness of the languages is not crucial for the former ‘equality’ results. Thus we analyze how constraints on the algorithmic structure of the target class affect the relations between two approaches to language learning.

I&C Journal 2007 Journal Article

Some natural conditions on incremental learning

• Sanjay Jain
• Steffen Lange
• Sandra Zilles

The present study aims at insights into the nature of incremental learning in the context of Gold’s model of identification in the limit. With a focus on natural requirements such as consistency and conservativeness, incremental learning is analysed both for learning from positive examples and for learning from positive and negative examples. The results obtained illustrate in which way different consistency and conservativeness demands can affect the capabilities of incremental learners. These results may serve as a first step towards characterising the structure of typical classes learnable incrementally and thus towards elaborating uniform incremental learning methods.

TCS Journal 2006 Journal Article

An approach to intrinsic complexity of uniform learning

• Sandra Zilles

Inductive inference is concerned with algorithmic learning of recursive functions. In the model of learning in the limit a learner successful for a class of recursive functions must eventually find a program for any function in the class from a gradually growing sequence of its values. This approach is generalised in uniform learning, where the problem of synthesising a successful learner for a class of functions from a description of this class is considered. A common reduction-based approach for comparing the complexity of learning problems in inductive inference is intrinsic complexity. Informally, if a learning problem (a class of recursive functions) A is reducible to a learning problem (a class of recursive functions) B, then a solution for B can be transformed into a solution for A. In the context of intrinsic complexity, reducibility between two classes is expressed via recursive operators transforming target functions in one direction and sequences of corresponding hypotheses in the other direction. The present paper is concerned with intrinsic complexity of uniform learning. The relevant notions are adapted and illustrated by several examples. Characterisations of complete classes finally allow for various insightful conclusions. The connection to intrinsic complexity of non-uniform learning is revealed within several analogies concerning first the structure of complete classes and second the general interpretation of the notion of intrinsic complexity.

I&C Journal 2005 Journal Article

Relations between Gold-style learning and query learning

• Steffen Lange
• Sandra Zilles

Different formal learning models address different aspects of human learning. Below we compare Gold-style learning—modelling learning as a limiting process in which the learner may change its mind arbitrarily often before converging to a correct hypothesis—to learning via queries—modelling learning as a one-shot process in which the learner is required to identify the target concept with just one hypothesis. In the Gold-style model considered below, the information presented to the learner consists of positive examples for the target concept, whereas in query learning, the learner may pose a certain kind of queries about the target concept, which will be answered correctly by an oracle (called teacher). Although these two approaches seem rather unrelated at first glance, we provide characterisations of different models of Gold-style learning (learning in the limit, conservative inference, and behaviourally correct learning) in terms of query learning. Thus we describe the circumstances which are necessary to replace limit learners by equally powerful one-shot learners. Our results are valid in the general context of learning indexable classes of recursive languages. This analysis leads to an important observation, namely that there is a natural query learning type hierarchically in-between Gold-style learning in the limit and behaviourally correct learning. Astonishingly, this query learning type can then again be characterised in terms of Gold-style inference.

TCS Journal 2004 Journal Article

Separation of uniform learning classes

• Sandra Zilles

Within the scope of inductive inference a recursion theoretic approach is used to model learning behaviour. The fundamental model considered is Gold's identification of recursive functions in the limit. Modifying the corresponding definition has proposed several inference classes, which have been compared regarding the capacities of the relevant learners. The present paper is concerned with a meta-version of this learning model. Given a description of a class of target functions, a uniform learner is supposed to develop a specific successful method for learning the represented class. The same modifications as in the elementary model are considered in the context of uniform learning, especially respecting identification capacities. It turns out that the former separations of inference classes are reflected on the meta-level, in particular finite classes of recursive functions—which constitute the most simple learning problems in the elementary model—are evidence of these separations.