Catálogo de publicaciones - libros

The conference “Algorithmic Learning Theory 2006” is dedicated to studies of learning from a mathematical and algorithmic perspective. Researchers consider various abstract models of the problem of learning and investigate how the learning goal in such a setting can be formulated and achieved. These models describe ways to define – the goal of learning, – how the learner retrieves information about its environment, – how to form of the learner’s models of the world (in some cases). Retrieving information is in some models is passive where the learner just views a stream of data. In other models, the learner is more active, asking questions or learning from its actions. Besides explicit formulation of hypotheses in an abstract language with respect to some indexing system, there are also more implicit methods like making predictions according to the current hypothesis on some arguments which then are evaluated with respect to their correctness and wrong predictions (coming from wrong hypotheses) incur some loss on the learner. In the following, a more detailed introduction is given to the five invited talks and then to the regular contributions.

Linear optimization problems (LPs) with a very large or even infinite number of constraints frequently appear in many forms in machine learning. A linear program with m constraints can be written as $$ \begin{array}{lll} \min\limits_{{\mathbf{x}}\in{\mathcal{P}}^n} && {\bf c}^\top {\mathbf{x}} \\ \mbox{with} && {\bf a}_j^\top {\mathbf{x}}\leq b_j \quad \forall i=1,\ldots,m,\end{array} $$ where I assume for simplicity that the domain of x is the n dimensional probability simplex ${\mathcal{P}}^n$ . Optimization problems with an infinite number of constraints of the form ${\bf a}_j^\top {\mathbf{x}}\leq b_j$ , for all j ∈ J , are called semi-infinite , when the index set J has infinitely many elements, e.g. J =ℝ. In the finite case the constraints can be described by a matrix with m rows and n columns that can be used to directly solve the LP. In semi-infinite linear programs (SILPs) the constraints are often given in a functional form depending on j or implicitly defined, for instance by the outcome of another algorithm.

e-Science is scientific investigation performed through distributed global collaborations between scientists and their resources, and the computing infrastructure that enables this [4]. Scientific progress increasingly depends on pooling know-how and results; making connections between ideas, people, and data; and finding and reusing knowledge and resources generated by others in perhaps unintended ways. It is about harvesting and harnessing the ”collective intelligence” of the scientific community. The Semantic Web is an extension of the current Web in which information is given well-defined meaning to facilitate sharing and reuse, better enabling computers and people to work in cooperation [1]. Applying the Semantic Web paradigm to e-Science [3] has the potential to bring significant benefits to scientific discovery [2]. We identify the benefits of lightweight and heavyweight approaches, based on our experiences in the Life Sciences.

In this paper, we review some known results that relate the statistical query complexity of a concept class to the spectral norm of its correlation matrix. Since spectral norms are widely used in various other areas, we are then able to put statistical query complexity in a broader context. We briefly describe some non-trivial connections to (seemingly) different topics in learning theory, complexity theory, and cryptography. A connection to the so-called Hidden Number Problem, which plays an important role for proving bit-security of cryptographic functions, will be discussed in somewhat more detail.

Generative probabilistic models have proven to be a very useful framework for machine learning from scientific data. Key ideas that underlie the generative approach include (a) representing complex stochastic phenomena using the structured language of graphical models, (b) using latent (hidden) variables to make inferences about unobserved phenomena, and (c) leveraging Bayesian ideas for learning and prediction. This talk will begin with a brief review of learning from data with hidden variables and then discuss some exciting recent work in this area that has direct application to a broad range of scientific problems. A number of different scientific data sets will be used as examples to illustrate the application of these ideas in probabilistic learning, such as time-course microarray expression data, functional magnetic resonance imaging (fMRI) data of the human brain, text documents from the biomedical literature, and sets of cyclone trajectories.

Many robotic control problems, such as autonomous helicopter flight, legged robot locomotion, and autonomous driving, remain challenging even for modern reinforcement learning algorithms. Some of the reasons for these problems being challenging are (i) It can be hard to write down, in closed form, a formal specification of the control task (for example, what is the cost function for “driving well”?), (ii) It is often difficult to learn a good model of the robot’s dynamics, (iii) Even given a complete specification of the problem, it is often computationally difficult to find good closed-loop controller for a high-dimensional, stochastic, control task. However, when we are allowed to learn from a human demonstration of a task—in other words, if we are in the apprenticeship learning setting—then a number of efficient algorithms can be used to address each of these problems.

We consider the problem of learning unions of rectangles over the domain [ b ]^ n , in the uniform distribution membership query learning setting, where both b and n are “large”. We obtain poly( n , log b )-time algorithms for the following classes: – poly ( n log b )- Majority of $O(\frac{\log(n \log b)} {\log \log(n \log b)})$ -dimensional rectangles. –Unions of poly(log( n log b )) many rectangles with dimension $O(\frac{\log^2 (n \log b)} {(\log \log(n \log b) \log \log \log (n \log b))^2})$ . – poly ( n log b )- Majority of poly ( n log b )- Or of disjoint rectangles with dimension $O(\frac{\log(n \log b)} {\log \log(n \log b)})$ Our main algorithmic tool is an extension of Jackson’s boosting- and Fourier-based Harmonic Sieve algorithm [13] to the domain [ b ]^ n , building on work of Akavia et al. [1]. Other ingredients used to obtain the results stated above are techniques from exact learning [4] and ideas from recent work on learning augmented AC ^ 0 circuits [14] and on representing Boolean functions as thresholds of parities [16].

We study exact learning of halfspaces from equivalence queries. The algorithm uses an oracle RCH that returns a random consistent hypothesis to the counterexamples received from the equivalence query oracle. We use the RCH oracle to give a new polynomial time algorithm for exact learning halfspaces from majority of halfspaces and show that its query complexity is less (by some constant factor) than the best known algorithm that learns halfspaces from halfspaces.

Most of the existing active learning algorithms are based on the realizability assumption: The learner’s hypothesis class is assumed to contain a target function that perfectly classifies all training and test examples. This assumption can hardly ever be justified in practice. In this paper, we study how relaxing the realizability assumption affects the sample complexity of active learning. First, we extend existing results on query learning to show that any active learning algorithm for the realizable case can be transformed to tolerate random bounded rate class noise. Thus, bounded rate class noise adds little extra complications to active learning, and in particular exponential label complexity savings over passive learning are still possible. However, it is questionable whether this noise model is any more realistic in practice than assuming no noise at all. Our second result shows that if we move to the truly non-realizable model of statistical learning theory, then the label complexity of active learning has the same dependence Ω(1/ ε ^2) on the accuracy parameter ε as the passive learning label complexity. More specifically, we show that under the assumption that the best classifier in the learner’s hypothesis class has generalization error at most β >0, the label complexity of active learning is Ω( β ^2/ ε ^2log(1/ δ )), where the accuracy parameter ε measures how close to optimal within the hypothesis class the active learner has to get and δ is the confidence parameter. The implication of this lower bound is that exponential savings should not be expected in realistic models of active learning, and thus the label complexity goals in active learning should be refined.

This paper introduces a framework for quantum exact learning via queries, the so-called quantum protocol. It is shown that usual protocols in the classical learning setting have quantum counterparts. A combinatorial notion, the general halving dimension, is also introduced. Given a quantum protocol and a target concept class, the general halving dimension provides lower and upper bounds on the number of queries that a quantum algorithm needs to learn. For usual protocols, the lower bound is also valid even if only involution oracle teachers are considered. Under some protocols, the quantum upper bound improves the classical one. The general halving dimension also approximates the query complexity of ordinary randomized learners. From these bounds we conclude that quantum devices can allow moderate improvements on the query complexity. However, any quantum polynomially query learnable concept class must be also polynomially learnable in the classical setting.