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.

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.

We consider the problem of learning a labeled hypergraph from a given family of hypergraphs, using shortest path (SP) queries. An SP query specifies two vertices and asks for their distance in the target hypergraph. For various classes $\mathcal{H}$ of hypertrees, we present bounds on the number of queries required to learn an unknown hypertree from $\mathcal{H}$. Matching upper and lower asymptotic bounds are presented for learning hyperpaths and hyperstars, both in the adaptive and in the non-adaptive setting. Moreover, two non-trivial classes of hypertrees are shown to be efficiently learnable from adaptive SP queries, under certain conditions on structural parameters.

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.

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 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, and its strengthening efficient identifiability, which are concerned with the existence of a systematic set of characteristic samples from which a learner can correctly infer the target language. We provide a necessary condition for identification of SFAs in the limit using polynomial time and data, and a sufficient condition for efficient learnability of SFAs. From these conditions we derive a positive and a negative result. The performance of a learning algorithm is typically bounded as a function of the size of the representation of the target language. Since SFAs, in general, do not have a canonical form, and there are trade-offs between the complexity of the predicates on the transitions and the number of transitions, we start by defining size measures for SFAs. We revisit the complexity of procedures on SFAs and analyze them according to these measures, paying attention to the special forms of SFAs: normalized SFAs and neat SFAs, as well as to SFAs over a monotonic effective Boolean algebra. This is an extended version of the paper with the same title published in CSL'22.

This paper studies the equivalence problem for relational pattern languages, where a relation imposes dependencies between the two strings with which two variables in a pattern can be replaced simultaneously. Our focus is on the question whether the non-equivalence of two relational patterns is witnessed by short strings, namely those generated by replacing variables in the patterns by strings of length bounded by some (small) number $z$. After establishing a close connection between this problem and the study of the notions of \emph{teaching dimension}\/{and} \emph{no-clash teaching dimension}, we investigate specific classes of relational pattern languages. We show that the smallest number $z$ that serves as a bound for testing equivalence is $2$ when the relation between variable substitutions is that of equal string length, and the alphabet size it at least 3. This has interesting implications on the size and form of non-clashing teaching sets for the corresponding languages. By contrast, not even $z=3$ is sufficient when the constraints require two substituted strings to be the reversal of one another, for alphabets of size 2. We conclude with a negative result on erasing pattern languages.

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.

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.

Avoiding collision between two robot arms in a common workspace is non-trivial, since each arm acts as a dynamic obstacle for the other one. In this context, Motion Path Planning (MPP) is the process of finding an optimal and collision-free track that a robot/robot arm can follow to get to the target position starting from any point in its workspace. We propose a reinforcement learning approach to MPP for two manipulators, the first one of which tries to avoid collision with the second one. Initially, the first manipulator has no knowledge about the environment, but it successfully learns optimal collision-free paths through a Team Q-learning algorithm. We present experiments using two different methods for state discretization, namely General State (GS) Discretization and Tile Coding (TC) Discretization, as well as two different Q-learning methods, namely single-agent (SA) and multi-agent (MA) approaches.

MOTIVATION: A digenic genetic interaction (GI) is observed when mutations in two genes within the same organism yield a phenotype that is different from the expected, given each mutation's individual effects. While multiplicative scoring is widely applied to define GIs, revealing underlying gene functions, it remains unclear if it is the most suitable choice for scoring GIs in Escherichia coli. Here, we assess many different definitions, including the multiplicative model, for mapping functional links between genes and pathways in E.coli. RESULTS: Using our published E.coli GI datasets, we show computationally that a machine learning Gaussian process (GP)-based definition better identifies functional associations among genes than a multiplicative model, which we have experimentally confirmed on a set of gene pairs. Overall, the GP definition improves the detection of GIs, biological reasoning of epistatic connectivity, as well as the quality of GI maps in E.coli, and, potentially, other microbes. AVAILABILITY AND IMPLEMENTATION: The source code and parameters used to generate the machine learning models in WEKA software were provided in the Supplementary information. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

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.

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 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$-$\mathrm{TD}(\mathcal{C})$ refers to the \emph{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 $\mathrm{NCTD}(\mathcal{C})$. No-clash teaching is provably optimal in the strong sense that, given \emph{any}\/{concept} class $\mathcal{C}$ and \emph{any}\/{model} $M$ obeying Goldman and Mathias’s collusion-freeness criterion, one obtains $\mathrm{NCTD}(\mathcal{C})\le M$-$\mathrm{TD}(\mathcal{C})$. We also study a corresponding notion $\mathrm{NCTD}^+$ for the case of learning from positive data only, establish useful bounds on $\mathrm{NCTD}$ and $\mathrm{NCTD}^+$, and discuss relations of these parameters to the VC-dimension and to sample compression. In addition to formulating an optimal model of collusion-free teaching, our main results are on the computational complexity of deciding whether $\mathrm{NCTD}^+(\mathcal{C})=k$ (or $\mathrm{NCTD}(\mathcal{C})=k$) for given $\mathcal{C}$ and $k$. We show some such decision problems to be equivalent to the existence question for certain constrained matchings in bipartite graphs. Our NP-hardness results for the latter are of independent interest in the study of constrained graph matchings.

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.

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 $\pi$, 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 $\pi$? 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.

This paper studies exact learning of unions of non-discretized geometric concepts in the model of preference-based teaching. In particular, it focuses on upper and lower bounds of the corresponding sample complexity parameter, the preference-based teaching dimension (PBTD), when learning disjoint unions of a bounded number of geometric concepts of various types -- for instance balls, axis-aligned cubes, or axis-aligned boxes -- in arbitrary dimensions. It is shown that the PBTD of disjoint unions of some such types of concepts grows linearly with the number of concepts in the union, independent of the dimensionality. Teaching the union of potentially overlapping objects turns out to be more involved and is hence considered here only for unions of up to two objects.

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.

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.

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 \mathbbN_0 (whose RTD had been studied quite recently) and including the class of Euclidean half-spaces (and some other geometric classes). 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.

The Recursive Teaching Dimension (RTD) of a concept class \mathcalC is a complexity parameter referring to the worst-case number of labelled examples needed to learn any target concept in \mathcalC from a teacher following the recursive teaching model. It is the first teaching complexity notion for which interesting relationships to the VC dimension (VCD) have been established. In particular, for finite maximum classes of a given VCD d, the RTD equals d. To date, there is no concept class known for which the ratio of RTD over VCD exceeds 3/2. However, the only known upper bound on RTD in terms of VCD is exponential in the VCD and depends on the size of the concept class. We pose the following question: is the RTD upper-bounded by a function that grows only linearly in the VCD? Answering this question would further our understanding of the relationships between the complexity of teaching and the complexity of learning from randomly chosen examples. In addition, the answer to this question, whether positive or negative, is known to have implications on the study of the long-standing open sample compression conjecture, which claims that every concept class of VCD d has a sample compression scheme in which samples for concepts in the class are compressed to subsets of size no larger than d.

This paper studies labeled sample compression for multi-label concept classes. For a specific extension of the notion of VC-dimension to multi-label classes, we prove that every maximum multi-label class of dimension d has a sample compression scheme in which every sample is compressed to a subset of size at most d. We further show that every multi-label class of dimension 1 has a sample compression scheme using only sets of size at most 1. As opposed to the binary case, the latter result is not immediately implied by the former, since there are multi-label concept classes of dimension 1 that are not contained in maximum classes of dimension 1.

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 both of 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.

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.

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.

Korf, Reid, and Edelkamp launched a line of research aimed at predicting how many nodes IDA* will expand with a given depth 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." Second, we disprove the intuitively appealing idea that a "more informed" prediction system cannot make worse predictions than a ``less informed'' one. More informed systems are more susceptible to the discretization effect, and in our experiments the more informed system makes poorer predictions. Our third contribution is a method, called "Epsilon-truncation," which makes a prediction system less informed, in a carefully chosen way, so as to improve its predictions by reducing the discretization effect. In our experiments Epsilon-truncation improved predictions substantially.

Many tracking problems involve several distinct objects interacting with each other. We develop a framework that takes into account interactions between objects allowing the recognition of complex activities. In contrast to classic approaches that consider distinct phases of tracking and activity recognition, our framework performs these two tasks simultaneously. In particular, we adopt a Bayesian standpoint where the system maintains a joint distribution of the positions, the interactions and the possible activities. This turns out to be advantegeous, as information about the ongoing activities can be used to improve the prediction step of the tracking, while, at the same time, tracking information can be used for online activity recognition. Experimental results in two different settings show that our approach 1) decreases the error rate and improves the identity maintenance of the positional tracking and 2) identifies the correct activity with higher accuracy than standard approaches.

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''. Second, we disprove the intuitively appealing idea that a ``more informed'' prediction system cannot make worse predictions than a ``less informed'' one. More informed systems are more susceptible to the discretization effect, and in several of our experiments the more informed system makes poorer predictions. Our third contribution is a method, called ``$\epsilon$-truncation'', which makes a prediction system less informed, in a carefully chosen way, so as to improve its predictions by reducing the discretization effect. In our experiments $\epsilon$-truncation rarely degraded predictions; in the vast majority of cases it improved predictions, often substantially.

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.

This paper introduces a new extension of outlier detection approaches and a new concept, class separation through variance. We show that accumulating information about the outlierness of points in multiple subspaces leads to a ranking in which classes with differing variance naturally tend to separate. Exploiting this leads to a highly effective and efficient unsupervised class separation approach, especially useful in the difficult case of heavily overlapping distributions. Unlike typical outlier detection algorithms, this method can be applied beyond the `rare classes' case with great success. Two novel algorithms that implement this approach are provided. Additionally, experiments show that the novel methods typically outperform other state-of-the-art outlier detection methods on high dimensional data such as Feature Bagging, SOE1, LOF, ORCA and Robust Mahalanobis Distance and competes even with the leading supervised classification methods.

This paper introduces and analyzes a new approach to query suggestion. After the user issues a query q_0, for every document retrieved in a certain rank range [Theta_1,Theta_2], a query search procedure constructs queries that rank the document high enough for the user to see it. From this set of queries the suggestions to be presented to the user are then selected so as to give the best possible access to the documents that were ranked in [Theta_1,Theta_2] for the user's initial query q_0. This approach turns out to be successful under certain assumptions, which are discussed in this paper.

This paper proposes an empirical approach for analyzing the rank distribution of relevant documents in Web search. From a methodological point of view a new transaction log analysis method is proposed; the relevance of documents is studied over transaction sessions rather than single transactions. From a practical point of view the paper provides insights about the actual rank distribution of relevant documents in Web search, with several consequences for the design of applications related to Web search.

We consider concept learning from examples. The learner receives - step by step - larger and larger initial segments of a sequence of examples describing an unknown target concept, processes these examples, and computes hypotheses. The learner is successful, if its hypotheses stabilize on a correct representation of the target concept. The underlying model is called identification in the limit. The present study concerns different versions of incremental learning in the limit. In contrast to the general case, now the learner has only limited access to the examples provided so far. In the special case of iterative learning, the learner builds its new hypotheses just on the basis of the current hypothesis and the next example, without having access to any of the other examples presented so far. In the case of bounded example-memory learning, the learner may in addition memorize up to an a priori fixed number of examples already presented. Formal studies have shown that restricting the accessibility of the input data results in a loss of learning power, i.e. there are concept classes learnable in the limit, but not identifiable by any incremental learner at all. The present analysis aims at illustrating this phenomenon and giving insights into the structure of concept classes incremental learners can cope with. Examples of identifiable and non-identifiable classes are given; different learning models are compared to one another with respect to the competence of the corresponding learners.