## Measuring the likelihood of numerical constraints

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

Open

### Documents

https://www.ijcai.org/proceedings/2019/229
Original language English Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2019 August 10-16, 2019, Macao International Joint Conferences on Artificial Intelligence Organization 1654-1660 7 978-0-9992411-4-1 https://doi.org/10.24963/ijcai.2019/229 Published - 31 Aug 2019 28th International Joint Conference on Artificial Intelligence - Convention Center of the Venetian Macao Hotel Resort, Macao, ChinaDuration: 10 Aug 2019 → 16 Aug 2019Conference number: 28https://www.ijcai19.org/

### Conference

Conference 28th International Joint Conference on Artificial Intelligence IJCAI-19 China Macao 10/08/19 → 16/08/19 https://www.ijcai19.org/

### 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.

## 28th International Joint Conference on Artificial Intelligence

10/08/1916/08/19

Macao, China

Event: Conference