{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T07:37:26Z","timestamp":1723016246900},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,7]]},"abstract":"<jats:p>In a variety of reasoning tasks, one estimates the likelihood of\nevents by means of volumes of sets they define. Such sets need to be\nmeasurable, which is usually achieved by putting bounds, sometimes ad\nhoc, on them. We address the question how unbounded or unmeasurable\nsets can be measured nonetheless. Intuitively, we want to know\nhow likely a randomly chosen point is to be in a given set, even in the\nabsence of a uniform   distribution over the entire space. \nTo address this, we follow a recently proposed approach of taking\nintersection of a set with balls of increasing radius, and defining\nthe measure by means of the asymptotic behavior of the proportion of\nsuch balls taken by the set. We show that this approach works for\nevery set definable in first-order logic with the usual arithmetic\nover the reals (addition, multiplication, exponentiation, etc.), and\nevery uniform measure over the space, of which the usual Lebesgue\nmeasure (area, volume, etc.) is an example. In fact we establish a\ncorrespondence between the good asymptotic behavior and the finiteness\nof the VC dimension of definable families of sets. Towards computing\nthe measure thus defined, we show how to avoid the asymptotics and\ncharacterize it via a specific subset of the unit sphere. Using\ndefinability of this set, and known techniques for sampling from the\nunit sphere, we give two algorithms for estimating our measure of\nunbounded unmeasurable sets, with deterministic and probabilistic\nguarantees, the latter being more efficient. Finally we show that a\ndiscrete analog of this measure exists and is similarly well-behaved.<\/jats:p>","DOI":"10.24963\/kr.2020\/27","type":"proceedings-article","created":{"date-parts":[[2020,8,20]],"date-time":"2020-08-20T04:39:16Z","timestamp":1597898356000},"page":"264-273","source":"Crossref","is-referenced-by-count":0,"title":["Reasoning about Measures of Unmeasurable Sets"],"prefix":"10.24963","author":[{"given":"Marco","family":"Console","sequence":"first","affiliation":[{"name":"University of Edinburgh"}]},{"given":"Matthias","family":"Hofer","sequence":"additional","affiliation":[{"name":"University of Edinburgh"}]},{"given":"Leonid","family":"Libkin","sequence":"additional","affiliation":[{"name":"University of Edinburgh"},{"name":"ENS Paris\/PSL"},{"name":"Neo4j"}]}],"member":"10584","event":{"number":"17","sponsor":["Artificial Intelligence Journal","Principles of Knowledge Representation and Reasoning Inc.","Association for Logic Programming","Center for Perspicuous Computing","European Association for Artificial Intelligence","Ontopic - The Virtual Knowledge Graph Company"],"acronym":"KR-2020","name":"17th International Conference on Principles of Knowledge Representation and Reasoning {KR-2020}","start":{"date-parts":[[2020,9,12]]},"theme":"Artificial Intelligence","location":"Rhodes, Greece","end":{"date-parts":[[2020,9,18]]}},"container-title":["Proceedings of the Seventeenth International Conference on Principles of Knowledge Representation and Reasoning"],"original-title":[],"deposited":{"date-parts":[[2020,11,5]],"date-time":"2020-11-05T21:18:34Z","timestamp":1604611114000},"score":1,"resource":{"primary":{"URL":"https:\/\/proceedings.kr.org\/2020\/27"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2020,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/kr.2020\/27","relation":{},"subject":[],"published":{"date-parts":[[2020,7]]}}}