14^th October 2020, 14:00
Elena Zamaraeva
Leverhulme Research Centre for Functional Materials Design

Abstract

A {0,1}-valued function f over integer d-dimensional cube {0,1,....,n-1}^d is called threshold if there exists a hyperplane that separates zeros and ones of f. A function that can be represented as a conjunction of k threshold functions is called k-threshold function. In this talk, we will consider threshold and k-threshold functions and the functions representing convex integer polytopes. We will look at the properties of the above functions in the context of Angluin's model of exact learning via membership queries. We will consider a specifying (teaching) set of a function, i.e. the set of points that identifies the given function with respect to some given class of functions. Particular attention will be given to essential points that are necessarily included in each specifying set for a given function. We will discuss the size and relation between the set of essential points and specifying sets for functions in the mentioned classes and how they affect the complexity of learning with membership queries.