Search

In certain applications there may be only positive examples available to learn concepts of a class of interest. Furthermore, learning has to be done properly, i. e. the hypothesis space has to coincide with the concept class, and without false positives, i. e. the hypothesis always has to be a subset of the real concept (one-sided error). For the well studied class of k-term DNF formulas it has been known that learning is difficult. Unless RP = NP, it is not feasible to learn k-term DNF formulas properly in a distribution-free sense even if both positive and negative examples are available and even if false positives are allowed. This paper constructs an efficient algorithm that, for fixed but arbitrary k and q, if examples are drawn from q-bounded distributions, it properly learns the class of k-term DNFs without false positives from positive examples alone with arbitrarily small relative error.

In 2006, Valiant introduced a variation to his celebrated PAC model to Biology, by which he wished to explain how such complex life mechanisms evolved in that short time by two simple mechanisms — random variation and natural selection. Soon after, several works extended and specialized his work to more specific processes. To the best of our knowledge, there is no such extension to the prokaryotic world, in which gene sharing is the prevailing mode of evolution. In this work we do the first step in this direction by extending the evolvability framework to accommodate horizontal gene transfer (HGT). Despite its computational equivalence to the basic evolvability model, we prove that under certain cases the new model allows an asymptotic acceleration in terms of the number of generations. This is done via a general reduction from parallel CSQ algorithm. As a demonstration of its learning power, we show that the concept class of conjunctions, a common concept class in the computational learning literature, can be learned by evolvability with HGT in constant number of generations.

Markov networks and Bayesian networks are two popular models for classification. Vapnik–Chervonenkis dimension and Euclidean dimension are two measures of complexity of a class of functions, which can be used to measure classification capability of classifiers. One can use Vapnik–Chervonenkis dimension of the class of functions associated with a classifier to construct an estimate of its generalization error. In this paper, we study Vapnik–Chervonenkis dimension and Euclidean dimension of concept classes induced by discrete Markov networks and Bayesian networks. We show that these two dimensional values of the concept class induced by a discrete Markov network are identical, and the value equals dimension of the toric ideal corresponding to this Markov network as long as the toric ideal is nontrivial. Based on this result, one can compute the dimensional value in terms of a computer algebra system directly. Furthermore, for a general Bayesian network, we show that dimension of the corresponding toric ideal offers an upper bound of Euclidean dimension. In addition, we illustrate how to use Vapnik–Chervonenkis dimension to estimate generalization error in binary classification.

We compose a toolbox for the design of Minimum Disagreement algorithms. This box contains general procedures which transform (without much loss of efficiency) algorithms that are successful for some d-dimensional (geometric) concept class C into algorithms which are successful for a ( d + 1 ) -dimensional extension of C . An iterative application of these transformations has the potential of starting with a base algorithm for a trivial problem and ending up at a smart algorithm for a non-trivial problem. In order to make this working, it is essential that the algorithms are not proper, i.e., they return a hypothesis that is not necessarily a member of C . However, the “price” for using a super-class H of C is so low that the resulting time bound for achieving accuracy e in the model of agnostic learning is significantly smaller than the time bounds achieved by the up-to-date best (proper) algorithms. We evaluate the transformation technique for d = 2 on both artificial and real-life data sets and demonstrate that it provides a fast algorithm, which can successfully solve practical problems on large data sets.

Traditionally, the probably approximately correct (PAC) learning refers the single concept class. We discuss the PAC framework of the multiple tasks in the joint inference model. And we extend PAC learning to multi-concept classes.We present an ensemble learning approach to joint inference on the three NLP sub-tasks. We explain how to combine those weak learners to a strong ability and present the dynamic weighted combination method in the ensemble joint inference model.Our Ensemble Markov Logic Networks (EMLNs) address the problem of the Markov Logic Networks intractable dealing with the large scale data. Experiments show that this approach leads to a higher precision and recall than that of pipeline approaches. Joint inference is a fundamental issue in the field of artificial intelligence. The greatest advantage of the joint inference is demonstrated by its capability of avoiding errors from cascading and accumulating on a pipeline of multiple chained sub-tasks. Markov Logic Network(MLN) is the most common joint inference model that provides a flexible representation and handles uncertainty. It has been applied successfully to joint inference on many natural language processing tasks to avoid error propagation. However, due to the great expressiveness of first-order logic, the representation for it in MLN generates rather complicated graph structures, which makes the learning and inference on large scale data intractably. In this paper, we present an ensemble learning approach to deal with the challenges in MLNs. Firstly, we give a proof within the probably approximately correct (PAC) framework. The proof points out what conditions are necessary for successful applying the ensemble learning approach to MLN. Secondly, the paper explains how to combine the learners. Finally, in order to illustrate the working mechanism of the ensemble joint inference model, we present an Ensemble Markov Logic Networks (EMLNs) method and use it to extract knowledge from a large scale corpus published by Google.11code.google.com/p/relation-extraction-corpus/. Experiments suggest that significant speedup can be gained by the EMLNs. Meanwhile, it show that this approach leads to a higher precision and recall than that of those pipeline approaches.

We solve the problem of concept learning using a semi-tensor product method. All possible hypotheses are expressed under the framework of a semi-tensor product. An algorithm is raised to derive the version space. In some cases, the new approach improves the efficiency compared to the previous approach. doi:10.1017/S1446181116000316

Sample compression schemes were defined by Littlestone and Warmuth (1986) as an abstraction of the structure underlying many learning algorithms. Roughly speaking, a sample compression scheme of size $k$ means that given an arbitrary list of labeled examples, one can retain only $k$ of them in a way that allows to recover the labels of all other examples in the list. They showed that compression implies PAC learnability for binary-labeled classes, and asked whether the other direction holds. We answer their question and show that every concept class $C$ with VC dimension $d$ has a sample compression scheme of size exponential in $d$. The proof uses an approximate minimax phenomenon for binary matrices of low VC dimension, which may be of interest in the context of game theory., 14 pages. The previous version of this text contained an error; Theorem 2.1 in it is false. This error only affects the statement for multi-labeled classes, and the construction for binary-labeled classes still holds. In the new version of the text, we added a relevant discussion in Section 4

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 HC 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.

The model of three-way concept lattices, a novel model for widely used three-way decisions, is an extension of classical concept lattices in formal concept analysis. This paper systematically analyses the connections between two types of three-way concept lattices (object-induced and attribute-induced three-way concept lattices) and classical concept lattices. The relationships are discussed from the viewpoints of elements, sets and orders, respectively. Furthermore, the necessary and sufficient conditions used to construct three-way concepts on the basis of classical concepts are proved, the algorithms building three-way concept lattices on the basis of classical concept lattices are presented. The obtained results are finally demonstrated and verified by examples.

Looking for strategies to reduce the size of concept lattices is very important in formal concept analysis, when they preserve the main information of the relational database.This paper presents several properties of the useful fuzzy-attributes, in the general fuzzy case of multi-adjoint concept lattices and provides two mechanisms in order to reduce the size of concept lattices based on irreducible elements, without losing or modifying important information. Specifically, the reduced concept lattices are sublattices of the original one. Moreover, interesting properties of these mechanisms are studied and the relationship among both and other strategies is also introduced.

Survey of the main existing techniques for concept lattices reduction.Classification of techniques in three classes based on seven dimensions.Analyzing reduction techniques with formal concept analysis.Considerations are carried out about computational complexity and feasibility. Formal concept analysis (FCA) is currently considered an important formalism for knowledge representation, extraction and analysis with applications in different areas. A problem identified in several applications is the computational cost due to the large number of formal concepts generated. Even when that number is not very large, the essential aspects, those effectively needed, can be immersed in a maze of irrelevant details. In fact, the problem of obtaining a concept lattice of appropriate complexity and size is one of the most important problems of FCA. In literature, several different approaches to control the complexity and size of a concept lattice have been described, but so far they have not been properly analyzed, compared and classified. We propose the classification of techniques for concept lattice reduction in three groups: redundant information removal, simplification, and selection. The main techniques to reduce concept lattice are analyzed and classified based on seven dimensions, each one composed of a set of characteristics. Considerations are made about the applicability and computational complexity of approaches of different classes.

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.

Co-training under the Conditional Independence Assumption is among the models which demonstrate how radically the need for labeled data can be reduced if a huge amount of unlabeled data is available. In this paper, we explore how much credit for this saving must be assigned solely to the extra assumptions underlying the Co-training Model. To this end, we compute general (almost tight) upper and lower bounds on the sample size needed to achieve the success criterion of PAC-learning in the realizable case within the model of Co-training under the Conditional Independence Assumption in a purely supervised setting. The upper bounds lie significantly below the lower bounds for PAC-learning without Co-training. Thus, Co-training saves labeled data even when not combined with unlabeled data. On the other hand, the saving is much less radical than the known savings in the semi-supervised setting.

In multiple-instance learning (MIL), an object is represented as a bag consisting of a set of feature vectors called instances. In the training set, the labels of bags are given, while the uncertainty comes from the unknown labels of instances in the bags. In this paper, we study MIL with the assumption that instances are drawn from a mixture distribution of the concept and the non-concept, which leads to a convenient way to solve MIL as a classifier combining problem. It is shown that instances can be classified with any standard supervised classifier by re-weighting the classification posteriors. Given the instance labels, the label of a bag can be obtained as a classifier combining problem. An optimal decision rule is derived that determines the threshold on the fraction of instances in a bag that is assigned to the concept class. We provide estimators for the two parameters in the model. The method is tested on a toy data set and various benchmark data sets, and shown to provide results comparable to state-of-the-art MIL methods.

The application of formal concept analysis to the problem of information retrieval has been shown useful but has lacked any real analysis of the idea of relevance ranking of search results. SearchSleuth is a program developed to experiment with the automated local analysis of Web search using formal concept analysis. SearchSleuth extends a standard search interface to include a conceptual neighbourhood centred on a formal concept derived from the initial query. This neighbourhood of the concept derived from the search terms is decorated with its upper and lower neighbours representing more general and special concepts, respectively. SearchSleuth is in many ways an archetype of search engines based on formal concept analysis with some novel features. In SearchSleuth, the notion of related categories – which are themselves formal concepts – is also introduced. This allows the retrieval focus to shift to a new formal concept called a sibling. This movement across the concept lattice needs to relate one forma...

This paper develops techniques to extract conceptual graphs from a patent claim using syntactic information (POS, and dependency tree) and semantic information (background ontology). Due to plenteous technical domain terms and lengthy sentences prevailing in patent claims, it is difficult to apply a NLP Parser directly to parse the plain texts in the patent claim. This paper combines techniques such as finite state machines, Part-Of-Speech tags, conceptual graphs, domain ontology and dependency tree to convert a patent claim into a formally defined conceptual graph. The method of a finite state machine splits a lengthy patent claim sentence into a set of shortened sub-sentences so that the NLP Parser can parse them one by one effectively. The Part-Of-Speech and dependency tree of a patent claim are used to build the conceptual graph based on the pre-established domain ontology. The result shows that 99% sub-sentences split from 1700 patent claims can be efficiently parsed by the NLP Parser. There are two types of nodes in a conceptual graph, the concept and the relation nodes. Each concept or relation can be extracted directly from a patent claim and each relation can link with a fixed number of concepts in a conceptual graph. From 100 patent claims, the average precision and recall of a concept class mapping from the patent claim to domain ontology are 96% and 89%, respectively, and the average precision and recall for Real relation class mapping are 97% and 98%, respectively. For the concept linking of a relation, the average precision is 79%. Based on the extracted conceptual graphs from patents, it would facilitate automated comparison and summarization among patents for judgment of patent infringement.

We prove the following strong hardness result for learning: Given a distribution of labeled examples from the hypercube such that there exists a monomial consistent with $(1-\eps)$ of the examples, it is NP-hard to find a halfspace that is correct on $(1/2+\eps)$ of the examples, for arbitrary constants $\eps > 0$. In learning theory terms, weak agnostic learning of monomials is hard, even if one is allowed to output a hypothesis from the much bigger concept class of halfspaces. This hardness result subsumes a long line of previous results, including two recent hardness results for the proper learning of monomials and halfspaces. As an immediate corollary of our result we show that weak agnostic learning of decision lists is NP-hard. Our techniques are quite different from previous hardness proofs for learning. We define distributions on positive and negative examples for monomials whose first few moments match. We use the invariance principle to argue that regular halfspaces (all of whose coefficients have small absolute value relative to the total $\ell_2$ norm) cannot distinguish between distributions whose first few moments match. For highly non-regular subspaces, we use a structural lemma from recent work on fooling halfspaces to argue that they are ``junta-like'' and one can zero out all but the top few coefficients without affecting the performance of the halfspace. The top few coefficients form the natural list decoding of a halfspace in the context of dictatorship tests/Label Cover reductions. We note that unlike previous invariance principle based proofs which are only known to give Unique-Games hardness, we are able to reduce from a version of Label Cover problem that is known to be NP-hard. This has inspired follow-up work on bypassing the Unique Games conjecture in some optimal geometric inapproximability results., 37 pages, Preliminary version appeared in FOCS 2009

In contrast to traditional multi-objective problems the concept-based version of such problems involves sets of particular solutions, which represent predefined conceptual solutions. This paper addresses the concept-based multi-objective problem by proposing two novel multi objective evolutionary algorithms. It also compares two major search approaches.The suggested algorithms deal with resource sharing among concepts, and within each concept, while simultaneously evolving concepts towards a Pareto front by way of their representing sets. The introduced algorithms, which use a simultaneous search approach, are compared with a sequential one. For this purpose concept-based performance indicators are suggested and used. The comparison study includes both the computational time and the quality of the concept-based front representation. Finally, the effect on the computational time of both the concept fitness evaluation time and concept optimality, for both the sequential and simultaneous approaches, is highlighted.

Under consideration are some equivalent definitions of the class of Skolemelementary functions (analogous to the known definitions of the class of Kalmar elementary functions) and some results for this class obtained by various mathematicians. The definitions of this class were studied independently of each other, and their equivalence is proved in this paper. The question is studied of the existence of finite superposition bases in this class. We prove that the problem of the existence of such a basis amounts to the well-known problem from the theory of computational complexity.

We prove that the concept class of disjunctions cannot be pointwise approximated by linear combinations of any small set of arbitrary real-valued functions. That is, suppose that there exist functions $$\phi_{1}, \ldots , \phi_{r}$$: {− 1, 1}n → $${\mathbb{R}}$$with the property that every disjunction f on n variables has $$\|f - \sum\nolimits_{i=1}^{r} \alpha_{i}\phi_{i}\|_{\infty}\leq 1/3$$ for some reals $$\alpha_{1}, \ldots , \alpha_{r}$$. We prove that then $$r \geq exp \{\Omega(\sqrt{n})\}$$, which is tight. We prove an incomparable lower bound for the concept class of decision lists. For the concept class of majority functions, we obtain a lower bound of $$\Omega(2^{n}/n)$$, which almost meets the trivial upper bound of 2n for any concept class. These lower bounds substantially strengthen and generalize the polynomial approximation lower bounds of Paturi (1992) and show that the regression-based agnostic learning algorithm of Kalai et al. (2005) is optimal.

It is widely accepted in machine learning that it is easier to learn several smaller decomposed concepts than a single large one. Typically, such decomposition of concepts is achieved in highly constrained environments, or aided by human experts. In this article, we investigate concept learning by example decomposition in a general probably approximately correct setting for Boolean learning. We develop sample complexity bounds for the different steps involved in the process. We formally show that if the cost of example partitioning is kept low then it is highly advantageous to learn by example decomposition.

Concept lattices are the central notion of formal concept analysis. They are applied in many different areas such as data mining, knowledge representation or ontology engineering and are subject to ongoing research. In order to better understand the nature of concept lattices, it is useful to consider their links to other mathematical notions. For example, a concept lattice can be viewed as a special kind of poset or closure system. In this paper, we consider another view of concept lattices by establishing a link to propositional formulae and a special closure property of relations. The main result is an elementary derivation of a Horn formula that uniquely represents a concept lattice based on prime implicates. Using the derived Horn representation, we re-establish the #P-completeness of the concept counting problem and find that the Horn representation is closely related to the stem base of a concept lattice.

We present new expected risk bounds for binary and multiclass prediction, and resolve several recent conjectures on sample compressibility due to Kuzmin and Warmuth. By exploiting the combinatorial structure of concept class F, Haussler et al. achieved a VC(F)/n bound for the natural one-inclusion prediction strategy. The key step in their proof is a d=VC(F) bound on the graph density of a subgraph of the hypercube—one-inclusion graph. The first main result of this paper is a density bound of n(n−1⩽d−1)/(n⩽d)

Generalized concept lattices have been recently proposed for dealing with uncertainty or incomplete information as a non-symmetric generalization of the theory of fuzzy formal concept analysis. On the other hand, concept lattices have been defined as well in the framework of fuzzy logics with non-commutative conjunctors. The contribution of this work is to prove that any concept lattice for non-commutative fuzzy logic can be interpreted inside the framework of generalized concept lattices; specifically, it is isomorphic to a sublattice of the cartesian product of two generalized concept lattices.

Concept lattices are systems of conceptual clusters, called formal concepts, which are partially ordered by the subconcept/superconcept relationship. Concept lattices are basic structures used in formal concept analysis. In general, a concept lattice may contain overlapping clusters and need not be a tree. On the other hand, tree-like classification schemes are appealing and are produced by several clustering methods. In this paper, we present necessary and sufficient conditions on input data for the output concept lattice to form a tree after one removes its least element. We present these conditions for input data with yes/no attributes as well as for input data with fuzzy attributes. In addition, we show how Lindig's algorithm for computing concept lattices gets simplified when applied to input data for which the associated concept lattice is a tree after removing the least element. The paper also contains illustrative examples.

The problem of imbalanced data sets occurs anytime one class represents a circumscribed concept, while the other represents the counterpart of that concept. The imbalanced data set problem can thus take two distinct forms: either the counterpart class is under-sampled relative to the concept class or it is over-sampled but particularly sparse. In bankruptcy prediction, classifiers are faced with imbalanced datasets: a lot of healthy firms and a smaller number of bankrupt firms. This paper firstly provides a systematic study on the various methodologies that have tried to handle the problem of imbalanced datasets. It presents an experimental study of these methodologies with a proposed technique and it concludes that such a framework can be a more effective solution to the bankruptcy prediction. Our method seems to allow improved identification of difficult small class (bankrupt firms) in predictive analysis, while keeping the classification ability of the other class (healthy firms) in an acceptable level.

We study the average number of well-chosen labeled examples that are required for a helpful teacher to uniquely specify a target function within a concept class. This "average teaching dimension" has been studied in learning theory and combinatorics and is an attractive alternative to the "worst-case" teaching dimension of Goldman and Kearns which is exponential for many interesting concept classes. Recently Balbach showed that the classes of 1-decision lists and 2-term DNF each have linear average teaching dimension. As our main result, we extend Balbach's teaching result for 2-term DNF by showing that for any 1?s?2 ?(n), the well-studied concept classes of at-most-s-term DNF and at-most-s-term monotone DNF each have average teaching dimension O(ns). The proofs use detailed analyses of the combinatorial structure of "most" DNF formulas and monotone DNF formulas. We also establish asymptotic separations between the worst-case and average teaching dimension for various other interesting Boolean concept classes such as juntas and sparse GF 2 polynomials.

The known O(dklogk) bound on the VC dimension of k-fold unions or intersections of a given concept class with VC dimension d is shown to be asymptotically tight.

A new class of b-spaces, called e b-spaces, is defined. This class is a natural generalization of the class of ℒ∞-spaces. Some properties of e b-spaces are established.

This paper discusses theoretical limitations of classification systems that are based on feature maps and use a separating hyper-plane in the feature space. In particular, we study the embeddability of a given concept class into a class of Euclidean half spaces of low dimension, or of arbitrarily large dimension but realizing a large margin. New bounds on the smallest possible dimension or on the largest possible margin are presented. In addition, we present new results on the rigidity of matrices and briefly mention applications in complexity and learning theory.

The general dimension is a combinatorial measure that characterizes the number of queries needed to learn a concept class. We use this notion to show that any p-evaluatable concept class with polynomial query complexity can be learned in polynomial time with the help of an oracle in the polynomial hierarchy, where the complexity of the required oracle depends on the query-types used by the learning algorithm. In particular, we show that for subset and superset queries an oracle in Σ3P suffices. Since the concept class of DNF formulas has polynomial query complexity with respect to subset and superset queries with DNF formulas as hypotheses, it follows that DNF formulas are properly learnable in polynomial time with subset and superset queries and the help of an oracle in Σ3P. We also show that the required oracle in our main theorem cannot be replaced by an oracle in a lower level of the polynomial-time hierarchy, unless the hierarchy collapses.

In this article we give several new results on the complexity of algorithms that learn Boolean functions from quantum queries and quantum examples. Hunziker et al. conjectured that for any class C of Boolean functions, the number of quantum black-box queries which are required to exactly identify an unknown function from C is $O(\frac{\log |C|}{\sqrt{{\hat{\gamma}}^{C}}})$, where $\hat{\gamma}^{C}$ is a combinatorial parameter of the class C. We essentially resolve this conjecture in the affirmative by giving a quantum algorithm that, for any class C, identifies any unknown function from C using $O(\frac{\log |C| \log \log |C|}{\sqrt{{\hat{\gamma}}^{C}}})$ quantum black-box queries. We consider a range of natural problems intermediate between the exact learning problem (in which the learner must obtain all bits of information about the black-box function) and the usual problem of computing a predicate (in which the learner must obtain only one bit of information about the black-box function). We give positive and negative results on when the quantum and classical query complexities of these intermediate problems are polynomially related to each other. Finally, we improve the known lower bounds on the number of quantum examples (as opposed to quantum black-box queries) required for $(\epsilon,\delta)$-PAC learning any concept class of Vapnik-Chervonenkis dimension d over the domain $\{0,1\}^n$ from $\Omega(\frac{d}{n})$ to $\Omega(\frac{1}{\epsilon}\log \frac{1}{\delta}+d+\frac{\sqrt{d}}{\epsilon})$. This new lower bound comes closer to matching known upper bounds for classical PAC learning., Comment: Minor corrections. 18 pages. To appear in Quantum Information Processing. Requires: algorithm.sty, algorithmic.sty to build

We prove two lower bounds in the statistical query (SQ) learning model. The first lower bound is on weak-learning. We prove that for a concept class of SQ-dimension d, a running time of @W(d/logd) is needed. The SQ-dimension of a concept class is defined to be the maximum number of concepts that are ''uniformly correlated'', in that each of their pair has nearly the same correlation. This lower bound matches the upper bound in Blum et al. (Weakly Learning DNF and Characterizing Statistical Query Learning using Fourier Analysis, STOC 1994, pp. 253-262), up to a logarithmic factor. We prove this lower bound against an ''honest SQ-oracle'', which gives a stronger result than the ones against the more frequently used ''adversarial SQ-oracles''. The second lower bound is more general. It gives a continuous trade-off between the ''advantage'' of an algorithm in learning the target function and the number of queries it needs to make, where the advantage of an algorithm is the probability it succeeds in predicting a label minus the probability it does not. Both lower bounds extend and/or strengthen previous results, and solve an open problem left in previous papers. An earlier version of this paper [K. Yang, New lower bounds for statistical query learning, in: The Proceedings of the 15th Annual Conference on Computational Learning Theory, COLT 2002, Sydney, Australia, July 8-10, Lecture Notes in Computer Science, vol. 2375, 2002, pp. 229-243.] appeared in the proceedings of the 15th Annual Conference on Computational Learning Theory (COLT 2002).

We study heuristic learnability of classes of Boolean formulas, a model proposed by Pitt and Valiant. In this type of example-based learning of a concept class C by a hypothesis class H, the learner seeks a hypothesis h? H that agrees with all of the negative (resp. positive) examples, and a maximum number of positive (resp. negative) examples. This learning is equivalent to the problem of maximizing agreement with a training sample, with the constraint that the misclassifications be limited to examples with positive (resp. negative) labels. Several recent papers have studied the more general problem of maximizing agreements without this one-sided error constraint. We show that for many classes (though not all), the maximum agreement problem with one-sided error is more difficult than the general maximum agreement problem. We then provide lower bounds on the approximability of these one-sided error problems, for many concept classes, including Halfspaces, Decision Lists, XOR, k-term DNF, and neural nets.

Formal concept analysis has been a topic of interest for about two decades. The mathematical notion of concept has its origin in formal logic. However, the empirical notion of concept has evolved through its use in many different disciplines. In this paper, we generalize the mathematical notion of concept and investigate order-theoretic properties of concept hierarchies for the new notion of concept.

Forcing functions represent an important class of Boolean functions that have been extensively studied in the analysis of the dynamics of random Boolean networks as models of genetic regulatory systems. Several other so-called Post classes of Boolean functions are closely related to forcing functions and have been used in learning theory as well as in control systems. We develop novel spectral algorithms to test membership of a Boolean function in these classes. These algorithms are highly efficient and are essential in learning problems, especially in the context of genetic regulatory networks, where the same learning procedures are applied repeatedly.

We address the computational complexity of learning in the agnostic framework. For a variety of common concept classes we prove that, unless P=NP, there is no polynomial time approximation scheme for finding a member in the class that approximately maximizes the agreement with a given training sample. In particular our results apply to the classes of monomials, axis-aligned hyper-rectangles, closed balls and monotone monomials. For each of these classes, we prove the NP-hardness of approximating maximal agreement to within some fixed constant (independent of the sample size and of the dimensionality of the sample space). For the class of half-spaces, we prove that, for any ε>0, it is NP-hard to approximately maximize agreements to within a factor of (418/415−ε), improving on the best previously known constant for this problem, and using a simpler proof. An interesting feature of our proofs is that, for each of the classes we discuss, we find patterns of training examples that, while being hard for approximating agreement within that concept class, allow efficient agreement maximization within other concept classes. These results bring up a new aspect of the model selection problem—they imply that the choice of hypothesis class for agnostic learning from among those considered in this paper can drastically effect the computational complexity of the learning process.

Concept classes can canonically be represented by matrices with entries 1 and −1. We use the singular value decomposition of this matrix to determine the optimal margins of embeddings of the concept classes of singletons and of half intervals in homogeneous Euclidean half spaces. For these concept classes the singular value decomposition can be used to construct optimal embeddings and also to prove the corresponding best possible upper bounds on the margin. We show that the optimal margin for embedding n singletons is \frac{n}{3n-4} and that the optimal margin for half intervals over l1,…,nr is \frac{\pi}{2 \ln n} + \Theta (\frac{1}{(\ln n)^2}). For the upper bounds on the margins we generalize a bound by Forster (2001). We also determine the optimal margin of some concept classes defined by circulant matrices up to a small constant factor, and we discuss the concept classes of monomials to point out limitations of our approach.

We consider the exact learning in the query model. We deal with all types of queries introduced by Angluin: membership, equivalence, superset, subset, disjointness and exhaustiveness queries, and their weak (or restricted) versions where no counterexample is returned. For each of all possible combinations of these queries, we uniformly give complete characterizations of boolean concept classes that are learnable using a polynomial number of polynomial-sized queries. Our characterizations show the equivalence between the learnability of a concept class C using queries and the existence of a good query for any subset H of C which is guaranteed to reject a certain fraction of candidate concepts in H regardless of the answer. As a special case for equivalence queries alone, our characterizations directly correspond to the lack of the approximate fingerprint property, which is known to be a sufficient and necessary condition for the learnability using equivalence queries.

Haussler, Littlestone and Warmuth (1994) described a general-purpose algorithm for learning according to the prediction model, and proved an upper bound on the probability that their algorithm makes a mistake in terms of the number of examples seen and the Vapnik-Chervonenkis (VC) dimension of the concept class being learned. We show that their bound is within a factor of 1+o(1) of the best possible such bound for any algorithm.

A new method is presented for analyzing and reengineering class hierarchies. In our approach, a class hierarchy is processed along with a set of applications that use it, and a fine-grained analysis of the access and subtype relationships between objects, variables, and class members is performed. The result of this analysis is again a class hierarchy, which is guaranteed to be behaviorally equivalent to the original hierarchy, but in which each object only contains the members that are required. Our method is semantically well-founded in concept analysis : the new class hierarchy is a minimal and maximally factorized concept lattice that reflects the access and subtype relationships between variables, objects and class members. The method is primarily intended as a tool for finding imperfections in the design of class hierarchies, and can be used as the basis for tools that largely automate the process of reengineering such hierachies. The method can also be used as a space-optimizing source-to-source transformation that removes redundant fields from objects. A prototype implementation for Java has been constructed, and used to conduct several case studies. Our results demonstrate that the method can provide valuable insights into the usage of a class hierarchy in a specific context, and lead to useful restructuring proposals.

We show in this paper (which appeared in a preliminary form as an extended abstract in [Proceedings of the 9th International ACM--SIAM Symposium on Discrete Algorithms, ACM, 1998]) that deterministic finite automata (DFAs) with n states and input alphabet $\Sigma$ can efficiently be learned from less than $|\Sigma|n^2$ smallest counterexamples. This improves on an earlier result of Ibarra and Jiang who required $|\Sigma|n^3$ smallest counterexamples. We present a general strategy which learns a finite concept class ${\cal F}$ from $\lfloor\log{\cal F}\rfloor$ smallest counterexamples (but not necessarily efficiently). An application to DFAs with at most $n$ states shows that $(1+o(1))|\Sigma|n\log n$ smallest counterexamples are sufficient (if efficiency is not an issue). We show next that the special DFAs operating on input words of an arbitrary but fixed length (the so-called leveled DFAs) are efficiently learnable from $(1+o(1))|\Sigma|n\log n$ smallest counterexamples. This improves on an earlier result of Ibarra and Jiang who required $|\Sigma|n^2$ smallest counterexamples. Furthermore, we present a general lower bound on the number of smallest counterexamples (required by any learning algorithm). This bound can be stated in terms of a (new) combinatorial dimension associated with the target class. A computation of this dimension for leveled or arbitrary DFAs leads to a lower bound of the form $(\frac{1}{4}+o(1))|\Sigma|n\log n$. This bound matches the aforementioned upper bounds modulo a constant of approximately 4. Finally, we present a general conversion of algorithms learning from smallest counterexamples into algorithms performing self-directed learning. For the particular classes of leveled or arbitrary DFAs, this conversion leads to self-directed learners making the smallest possible number of mistakes (modulo a constant of approximately 4). A similar remark is valid for the class of multiplicity automata (MAs).

We show that 2 is the minimum VC dimension of a concept class whose k-fold union has VC dimension @W(klogk).

In this paper the decomposition formula of Walsh spectrum of boolean functions is used to construct a class of nonlinear resilient functions.

We establish some general results concerning PAC learning: We find a characterization of the property that any consistent algorithm is PAC. It is shown that the shrinking width property is equivalent to PUAC learnability. By counterexample, PAC and PUAC learning are shown to be different concepts. We find conditions ensuring that any nearly consistent algorithm is PAC or PUAC, respectively.¶The VC dimension of recurrent neural networks and folding networks is infinite. For restricted inputs, however, bounds exist. The bounds for restricted inputs are transferred to folding networks.¶We find conditions on the probability of the input space ensuring polynomial learnability: the probability of sequences or trees has to converge to zero sufficiently fast with increasing length or height.¶Finally, we find an example for a concept class that requires exponentially growing sample sizes for accurate generalization.

A pac-learning algorithm isd-space bounded, if it stores at mostd examples from the sample at any time. We characterize thed-space learnable concept classes. For this purpose we introduce the compression parameter of a concept classb and design our Trial and Error Learning Algorithm. We show: b isd-space learnable if and only if the compression parameter ofb is at mostd. This learning algorithm does not produce a hypothesis consistent with the whole sample as previous approaches e.g. by Floyd, who presents consistent space bounded learning algorithms, but has to restrict herself to very special concept classes. On the other hand our algorithm needs large samples; the compression parameter appears as exponent in the sample size. We present several examples of polynomial time space bounded learnable concept classes: We further relate the compression parameter to the VC-dimension, and discuss variants of this parameter.

Developing the ability to recognize a landmark from a visual image of a robot's current location is a fundamental problem in robotics. We consider the problem of PAC-learning the concept class of geometric patterns where the target geometric pattern is a configuration ofk points on the real line. Each instance is a configuration ofn points on the real line, where it is labeled according to whether or not it visually resembles the target pattern. To capture the notion of visual resemblance we use the Hausdorff metric. Informally, two geometric patternsP andQ resemble each other under the Hausdorff metric if every point on one pattern is “close” to some point on the other pattern. We relate the concept class of geometric patterns to the landmark matching problem and then present a polynomial-time algorithm that PAC-learns the class of one-dimensional geometric patterns. We also present some experimental results on how our algorithm performs.

Proposes a theoretical model for analysis of classification methods, in which the teacher knows the classification algorithm and chooses examples in the best way possible. The authors apply this model using the nearest-neighbor learning algorithm, and develop upper and lower bounds on sample complexity for several different concept classes. For some concept classes, the sample complexity turns out to be exponential even using this best-case model, which implies that the concept class is inherently difficult for the NN algorithm. The authors identify several geometric properties that make learning certain concepts relatively easy. Finally the authors discuss the relation of their work to helpful teacher models, its application to decision tree learning algorithms, and some of its implications for experimental work. >

In control, learning is often used to identify a single controller satisfying a particular performance measure. In certain cases, however, it is desirable to identify the set of all controllers which ensure that the controlled plant satisfies a control property such as Lyapunov stability, robust stability, or robust performance. A set of procedures identifying such sets of admissible solutions can be devised using Boolean concept learning algorithms. This type of learning procedure is applicable to computational learning. The objective of this article is to provide some examples illustrating how Boolean concept learning can be used in control systems. The first example examined in this article uses concept learning to identify the set of stabilizing controllers for certain classes of linear time-invariant plants. Another example illustrates the use of concept learning in the identification of discrete event system (DES) controllers. >