Modelling binary classification

Abstract: In machine learning, algorithms generalise from available training data to unseen situations. The engineering practices used in the respective technologies are far from understood. Research in \emph{inductive inference} analyses concrete mathematical models for this complex subject with tools from computability theory.

We investigate models for incremental binary classification, an example for supervised online learning. Our starting point is a model for human and machine learning suggested by E.~M.~Gold.

For learning algorithms that use all of the available binary labeled training data in order to compute the current hypothesis, we observe that the distribution of the training data does not influence learnability. When approximating the concept to be learned, we obtain a strict hierarchy, depending on the error parameter. We consider different hypothesis spaces for spam problem like and symmetric classification tasks and provide the complete maps.

logic

Audience: researchers in the topic

Computability theory and applications

Series comments: Description: Computability theory, logic

The goal of this endeavor is to run a seminar on the platform Zoom on a weekly basis, perhaps with alternating time slots each of which covers at least three out of four of Europe, North America, Asia, and New Zealand/Australia. While the meetings are always scheduled for Tuesdays, the timezone varies, so please refer to the calendar on the website for details about individual seminars.