Author name cluster

Malte Darnstädt

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

TCS Journal 2018 Journal Article

Hierarchical design of fast Minimum Disagreement algorithms

Malte Darnstädt
Christoph Ries
Hans Ulrich Simon

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

Details DOI

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.

Details DOI

TCS Journal 2014 Journal Article

Supervised learning and Co-training

Malte Darnstädt
Hans Ulrich Simon
Balázs Szörényi

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.

Details DOI

TCS Journal 2011 Journal Article

Smart PAC-learners

Malte Darnstädt
Hans Ulrich Simon

The PAC-learning model is distribution-independent in the sense that the learner must reach a learning goal with a limited number of labeled random examples without any prior knowledge of the underlying domain distribution. In order to achieve this, one needs generalization error bounds that are valid uniformly for every domain distribution. These bounds are (almost) tight in the sense that there is a domain distribution which does not admit a generalization error being significantly smaller than the general bound. Note however that this leaves open the possibility to achieve the learning goal faster if the underlying distribution is “simple”. Informally speaking, we say a PAC-learner L is “smart” if, for a “vast majority” of domain distributions D, L does not require significantly more examples to reach the “learning goal” than the best learner whose strategy is specialized to D. In this paper, focusing on sample complexity and ignoring computational issues, we show that smart learners do exist. This implies (at least from an information-theoretical perspective) that full prior knowledge of the domain distribution (or access to a huge collection of unlabeled examples) does (for a vast majority of domain distributions) not significantly reduce the number of labeled examples required to achieve the learning goal.

Details DOI