Projects per year
Abstract
In a variety of reasoning tasks, one estimates the likelihood of events by means of volumes of sets they define. Such sets need to be measurable, which is usually achieved by putting bounds, sometimes ad hoc, on them. We address the question how unbounded or unmeasurable sets can be measured nonetheless. Intuitively, we want to know how likely a randomly chosen point is to be in a given set, even in the absence of a uniform distribution over the entire space.
To address this, we follow a recently proposed approach of taking intersection of a set with balls of increasing radius, and defining the measure by means of the asymptotic behavior of the proportion of such balls taken by the set. We show that this approach works for every set definable in firstorder logic with the usual arithmetic over the reals (addition, multiplication, exponentiation, etc.), and every uniform measure over the space, of which the usual Lebesgue measure (area, volume, etc.) is an example. In fact we establish a correspondence between the good asymptotic behavior and the finiteness of the VC dimension of definable families of sets. Towards computing the measure thus defined, we show how to avoid the asymptotics and characterize it via a specific subset of the unit sphere. Using definability of this set, and known techniques for sampling from the unit sphere, we give two algorithms for estimating our measure of unbounded unmeasurable sets, with deterministic and probabilistic guarantees, the latter being more efficient. Finally we show that a discrete analog of this measure exists and is similarly wellbehaved.
To address this, we follow a recently proposed approach of taking intersection of a set with balls of increasing radius, and defining the measure by means of the asymptotic behavior of the proportion of such balls taken by the set. We show that this approach works for every set definable in firstorder logic with the usual arithmetic over the reals (addition, multiplication, exponentiation, etc.), and every uniform measure over the space, of which the usual Lebesgue measure (area, volume, etc.) is an example. In fact we establish a correspondence between the good asymptotic behavior and the finiteness of the VC dimension of definable families of sets. Towards computing the measure thus defined, we show how to avoid the asymptotics and characterize it via a specific subset of the unit sphere. Using definability of this set, and known techniques for sampling from the unit sphere, we give two algorithms for estimating our measure of unbounded unmeasurable sets, with deterministic and probabilistic guarantees, the latter being more efficient. Finally we show that a discrete analog of this measure exists and is similarly wellbehaved.
Original language  English 

Title of host publication  Proceedings of 17th International Conference on Principles of Knowledge Representation and Reasoning 
Publisher  International Joint Conferences on Artificial Intelligence Organization 
Pages  264273 
Number of pages  10 
ISBN (Electronic)  9780999241172 
DOIs  
Publication status  Published  12 Sep 2020 
Event  17th International Conference on Principles of Knowledge Representation and Reasoning  Rhodes, Greece Duration: 12 Sep 2020 → 18 Sep 2020 https://kr2020.inf.unibz.it/ 
Publication series
Name  

Publisher  IJCAI Organization 
ISSN (Electronic)  23341033 
Conference
Conference  17th International Conference on Principles of Knowledge Representation and Reasoning 

Abbreviated title  KR 2020 
Country  Greece 
City  Rhodes 
Period  12/09/20 → 18/09/20 
Internet address 
Fingerprint Dive into the research topics of 'Reasoning about Measures of Unmeasurable Sets'. Together they form a unique fingerprint.
Projects

MAGIC: MAnaGing InComplete Data  New Foundations
UK central government bodies/local authorities, health and hospital authorities
1/10/16 → 31/05/22
Project: Research

VADA: Value Added Data Systems: Principles and Architecture
Libkin, L., Buneman, P., Fan, W. & Pieris, A.
1/04/15 → 30/09/20
Project: Research