Arrow Research search

Author name cluster

Klaus-Uwe Höffgen

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.

2 papers
1 author row

Possible papers

2

I&C Journal 2002 Journal Article

Exploiting Random Walks for Learning

  • Peter L. Bartlett
  • Paul Fischer
  • Klaus-Uwe Höffgen

In this paper we consider an approach to passive learning. In contrast to the classical PAC model we do not assume that the examples are independently drawn according to an underlying distribution, but that they are generated by a time-driven process. We define deterministic and probabilistic learning models of this sort and investigate the relationships between them and with other models. The fact that successive examples are related can often be used to gain additional information similar to the information gained by membership queries. We show how this can be used to design on-line prediction algorithms. In particular, we present efficient algorithms for exactly identifying Boolean threshold functions and 2-term RSE, and for learning 2-term-DNF, when the examples are generated by a random walk on {0, 1} n.

Details DOI

TCS Journal 1997 Journal Article

PAC-learning from general examples

  • Paul Fischer
  • Klaus-Uwe Höffgen
  • Hanno Lefmann

In this paper we study a new view on the PAC-learning model in which the examples are more complicated than in the standard model. There, an example usually is an element of the learning domain and its label indicates whether it belongs to the target concept. Here, the examples can be subsets and their labels indicate some relation to the target concept, e. g. , whether they intersect it or not. We show how this setting can be easily transformed into the standard PAC-model however, for an analysis it is much more natural to stick to the original formulation. Then the central notion is that of the relative dimension of a target class with respect to a sample class which replaces the Vapnik-Chervonenkis dimension. The investigation of structural aspects of the relative dimension is followed by its applications to learning environments. It turns out that computing or bounding the relative dimension leads to interesting combinatorial problems even for simple target and sample classes. Sometimes the analysis is easier if one represents the concepts as unions or intersections of simpler ones. We present sharp bounds on the relative and the Vapnik-Chervonenkis dimension of the complicated class in terms of the simpler one.

Details DOI
v2026.09.13