Edinburgh Research Explorer

Measuring the likelihood of numerical constraints

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Related Edinburgh Organisations

Open Access permissions

Open

Documents

https://www.ijcai.org/proceedings/2019/229
Original languageEnglish
Title of host publicationProceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2019
Subtitle of host publicationAugust 10-16, 2019, Macao
PublisherInternational Joint Conferences on Artificial Intelligence Organization
Pages1654-1660
Number of pages7
ISBN (Electronic)978-0-9992411-4-1
DOIs
Publication statusPublished - 31 Aug 2019
Event28th International Joint Conference on Artificial Intelligence - Convention Center of the Venetian Macao Hotel Resort, Macao, China
Duration: 10 Aug 201916 Aug 2019
Conference number: 28
https://www.ijcai19.org/

Conference

Conference28th International Joint Conference on Artificial Intelligence
Abbreviated titleIJCAI-19
CountryChina
CityMacao
Period10/08/1916/08/19
Internet address

Abstract

Our goal is to measure the likelihood of the satisfaction of numerical constraints in the absence of any prior information. Intuitively, the likelihood of x>y is 0.5, if we know nothing about x and y. We study expressive constraints, involving arithmetic and complex numerical functions, and even quantification over numbers. Such problems arise in processing incomplete data, or estimating the likelihood of conditions in programs without a priori bounds on variables.We show that for constraints on n variables, the proper way to define such a measure is as the limit of the part of the n-dimensional ball that consists of points satisfying the constraints, when the radius of the ball increases. We prove that the existence of such a limit is closely related to the notion of o-minimality from model theory. For example, for constraints definable with the usual arithmetic and exponentiation, the likelihood is well defined, but adding trigonometric functions is problematic. We then look at computing and approximating such likelihoods for order and linear constraints. We prove an impossibility result for approximating with multiplicative error, even for order constraints. However, as the likelihood is a number between 0 and 1, an approximation scheme with additive error is acceptable, and we give such a scheme for arbitrary linear constraints.

Event

28th International Joint Conference on Artificial Intelligence

10/08/1916/08/19

Macao, China

Event: Conference

Download statistics

No data available

ID: 93478437