An aphabet-size bound for the information bottleneck function
Hirche, Christoph (Technical University of Munich. Zentrum Mathematik)
Winter, Andreas (Universitat Autònoma de Barcelona. Departament de Física)

Date:	2020
Abstract:	The information bottleneck function gives a measure of optimal preservation of correlation between some random variable X and some side information Y while compressing X into a new random variable W with bounded remaining correlation to X. As such, the information bottleneck has found many natural applications in machine learning, coding and video compression. The main objective in order to calculate the information bottleneck is to find the optimal representation on W. This could in principle be arbitrarily complicated, but fortunately it is known that the cardinality of W can be restricted as |W| ≤ |X |+1 which makes the calculation possible for finite |X|. Now, for many practical applications, e. g. in machine learning, X represents a potentially very large data space, while Y is from a comparably small set of labels. This raises the question whether the known cardinality bound can be improved in such situations. We show that the information bottleneck function can always be approximated up to an error δ(ε, |Y|) with a cardinality |W| ≤ f(ε, |Y|), for explicitly given functions δ and f of an approximation parameter c> 0 and the cardinality of Y. Finally, we generalize the known cardinality bounds to the case were some of the random variables represent quantum information.
Grants:	Ministerio de Economía y Competitividad FIS2016-86681-P Agència de Gestió d'Ajuts Universitaris i de Recerca 2014/SGR-966
Rights:	Tots els drets reservats.
Language:	Anglès
Document:	Comunicació de congrés
Subject:	Approximation theory ; Computational complexity ; Data compression ; Learning (artificial intelligence) ; Set theory
Published in:	IEEE International Symposium on Information Theory. Los Angeles, CA, USA, 21-26 June 2020, p. 2383-2388

DOI: 10.1109/ISIT44484.2020.9174416

Postprint 7 p, 227.0 KB

The record appears in these collections:
Contributions to meetings and congresses > Papers and communications > UAB papers and communications