Author name cluster

Christoph Ries

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

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

JMLR Journal 2017 Journal Article

Preference-based Teaching

Ziyuan Gao
Christoph Ries
Hans U. Simon
Sandra Zilles

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. [abs] [ pdf ][ bib ] &copy JMLR 2017. ( edit, beta )

PDF Details