Learning Implicitly with Noisy Data in Linear Arithmetic

1 Introduction

Data in the real world can be incomplete, noisy and imprecise. Approaches from the knowledge representation communities take great care to represent expert knowledge; however, this knowledge can be hard to come by, challenging to formalize for non-experts, and brittle, especially in the presence of noisy measurements. In contrast, connectionist approaches, such as neural networks, have been particularly successful in learning from real-world data. However, they represent knowledge as distributed networks of nodes, rendering it difficult to incorporate knowledge from other sources. Moreover, such methods usually do not come with any guarantees of soundness, and are also quite brittle to small shifts in the domain [Recht et al., 2019; Koh et al., 2020].

In this work, we are concerned with learning in expressive languages, such as fragments of first-order logic, where knowledge and queries are represented as logical formulas. In that regard, Valiant [2000] recognized that the challenge of learning should be integrated with deduction. In particular, he proposed a semantics to capture the quality possessed by the output of PAC-learning algorithms when formulated in a logic.

Unfortunately, many results on learning logical languages have been discouraging. For example, in agnostic learning, [Kearns et al., 1994], where one does not require examples to be fully consistent with learned sentences, efficient algorithms for learning conjunctions of formulas would yield an efficient algorithm for PAC-learning disjunctive normal forms (DNF), which current evidence suggests to be intractable [Daniely and Shalev-Shwartz, 2016].

Interestingly, Khardon and Roth [1997] and Juba [2013] observed that, by circumventing the need to produce an explicit representation, learning to reason can be effectively reduced to classical reasoning, leading to a notion of "implicit learning'.' Since reasoning in propositional logic is NP-complete, implicit learning in full propositional logic also cannot be done in polynomial time (unless P=NP), but when limited to tractable fragments of propositional logic, learning inherits the tractability guarantee. Very recently, the learnability results have been extended to first-order clauses in [Belle and Juba, 2019], and then to certain fragments of satisfiability modulo theories (SMT) in [Mocanu et al., 2020].

In this work, we extend the implicit learning approach to handle partial information given by bounds (e.g., intervals), thus capturing an even larger class of problem settings, and develop an implementation strategy for a hitherto purely theoretical framework.

1.1 Theoretical Contributions

1. Extending the PAC-Semantics framework to be able to handle noisy data.
2. Proving polynomial running time guarantees.

To model noisy and imprecise data, such as sensor readings, we represent data as sets of intervals. Previous results [Mocanu et al., 2020] only allowed for sets of assignments. We prove polynomial-time guarantees for implicitly learning any fragments of SMT with polynomial-time decision procedures, such as linear arithmetic. Since we are extending the PAC-Semantics framework, we are inheriting all of its useful features: e.g., these examples could be drawn an arbitrary distribution and are not required to be fully consistent with the learned example; nonetheless, we are able to give approximately correct answers with a tight guarantee.

1.2 Empirical Contributions

1. Realising the first implementation of the PAC-Semantics framework.
2. Showing that implicit reasoning can be much faster and more noise-resistant than explicit methods for linear programs (LPs).

We test our implementation on benchmark LP problems, where the task is to find the optimum objective value subject to the constraints of the problem. We compare the running times with an alternative approach of first creating an explicit model using IncaLP [Schede et al., 2019] and then finding the optimum objective value based on the model. Our results show significantly lower running times using the implicit approach, and this advantage becomes more pronounced as the models grow. We also demonstrate that, in the presence of noisy data, implicit learning returns a feasible, approximate solution to the true linear program, whereas IncaLP often fails to find any model at all.

2 Preliminaries

We will now briefly review concepts from logic, satisfiability, PAC-Semantics and the formal setup used in our work.

2.1 Logic

Satisfiability (SAT) is the problem of deciding whether there exists an assignment of truth values (i.e., model) to variables (propositional symbols) such that a propositional logical formula is true. SMT is a generalization to SAT for deciding satisfiability for fragments and extensions of first-order logic with equality, for which specialized decision procedures have been developed. Deciding satisfiability for these logics is done with respect to some decidable background theory [Barrett et al., 2009]. In this work, we are especially interested in the background theories of quantifier-free linear real arithmetic (QFLRA). The following formal exposition is adapted from [Barrett et al., 2009]:

Syntax. We assume a logical signature consisting of a set of predicate symbols, and a set of functions, logical variables, and standard connectives (∧, ∨, ¬). An atomic formula is one of the form: b (a propositional symbol), pred(t1, ..., tk), t1 = t2, ⊥ (false), ⊤ (true), where t1, ..., tk are the terms of the signature, in the standard logical interpretation. A literal l is an atomic formula or its negation ¬l. A ground expression is one where all the variables are replaced by constants and in general terms of the domain of discourse.

Semantics. Formulas are given a truth value from the set {⊥,⊤} by means of first-order models. A model ρ can be seen simply as an element of Σn , which is the universe of the model in n dimensions. Throughout the paper we work with the signature of linear real arithmetic, with function symbols of the form {0, 1,+,-,≤,<,≥,>,=, ̸=}, interpreted in the usual way over the reals.

2.2 PAC-Semantics

PAC-Semantics was introduced by Valiant [2000] to capture the quality possessed by knowledge learned from independently drawn examples from some unknown distribution D. The output produced using this approach does not express validity in the traditional (Tarskian) sense. Instead, the notion of validity is then defined as follows:

Definition 1. [(1 - ϵ)-validity [Valiant, 2000]] Given a joint distribution D over Σn , we say that a Boolean function f is (1 - ϵ)-valid if Prρ∈D[f(ρ) = 1] ≥ 1 - ϵ. If ϵ = 0, we say that f is perfectly valid.

The reasoning problem of interest is deciding whether a query formula α is (1 - ϵ)-valid. Knowledge about the distribution D comes from the set of examples ρ, independently drawn from this distribution. Additional knowledge can come from a collection of axioms ∆, known as the knowledge base (KB).

In implicit learning, the query α is answered from examples directly, without creating an explicit model. This is done by means of entailment: we repeatedly ask whether ∆ ∧ ρ(k) |= α for examples ρ(k) ∈ D. If at least (1 - ϵ) of the examples entail α, we accept. The more examples we use, the more accurate our estimate is and the more confident we can be in it. The concepts of accuracy and confidence are captured by the hyper-parameters γ, δ ∈ (0, 1), where γ represents the accuracy of the examples used and δ captures the confidence of the example received. The number of examples needed will be determined from δ and γ; cf. Section 4 for a precise formulation.

Reasoning from complete examples is trivial: Hoeffding's inequality [Hoeffding, 1963] guarantees that with high probability, the proportion of times that the query formula evaluates to 'true' is a good estimate of the degree of validity of that formula. To capture the more interesting problem of learning from incomplete examples, previous works used the notion of a masking process developed by Michael [2010]. A masking process randomly replaces some of the values of variables in a formula with * before passing the examples to the learning algorithm.

Definition 2. [Masking process [Michael, 2010]] A mask is a function M : Σn → {Σ ∪ {∗}}n , with the property that for any ρ ∈ Σn , M(ρ) is consistent with ρ, i.e., whenever M(ρ)i ̸= ∗ then M(ρ)i = ρi. We refer to elements of the set (Σ∪{∗})n as partial assignments. A masking processM is a mask-valued random variable. We denote the distribution over partial examples obtained by applying the masking process as M(D).

Example 3. Assume a language with two real-valued variables x and y. Given a full assignment ρ : {x = 4, y = 5}, after applying a masking process on this assignment, we may obtain the partial assignment ρ : {x = 4, y = ∗}.

In the above example, x is not masked, and thus remains consistent with ρ, while y gets masked. A partial model will be written using the regular font as ρ vs the bold font for a full model as ρ.

Work by [Mocanu et al., 2020] showed that implicitly learning to reason can be done efficiently with partial assignments for standard fragments of arithmetic theories, which integrates a decision procedure to solve SMT formulas. They proposed a reduction from the learning to reason problem for a logic to any sound and complete solver for that fragment of logic. They showed that, as long as there is a sound and complete solver for a fragment of arithmetic, then reasoning under partial evaluation (denoted as |ρ) can be obtained.

Theorem 4.[[Mocanu et al., 2020]] Let L be a logical language such that for any α ∈ L and any partial assignment ρ for L, α|ρ ∈ L also. Let A be a sound and complete procedure for deciding entailment for L. Suppose ∆, α ∈ L, and ρ is a partial assignment for L. If ∆ |= α, then ∆|ρ |= α|ρ.

They provide an algorithm (a less general version of DecidePAC as we discuss later) that enables implicit learning of fragments of SMT under partial assignments. We continue this line of work and present an extension of the assignments used in DecidePAC to sets of intervals.

3 Use Case Example

Let us demonstrate the functionality of the extended PAC framework with a small example: Consider a smart fitness watch, which monitors the heart rate and blood oxygen levels of the wearer. It calculates the wearer's stress level using a formula: stress = hr -5× (ox-90), where hr is the heart rate in beats per minute and ox is the percentage of oxygen saturation in the blood.

As illustrated in Figure 1, this formula is encoded in the knowledge base of the system, ∆, along with two chosen bounds for hr and ox. The bound for ox is set between 90% and 100%, as anything lower is unnatural and a sign of hypoxemia [Mayo Clinic, 2020]. Similarly, hr can be bounded by the values 40 and 200 [American Heart Association, 2020].

The watch alerts the user if the stress level exceeds 50, which is encoded with the query α : (stress > 50). Depending on the values of the heart rate and oxygen within the boundaries set in ∆, the stress value might be below or above 50. Therefore, the explicit knowledge base alone cannot answer the query. However, the watch gets regular sensor readings in the form of intervals φ(k) , which it can use to answer the query. Since the watch might not be tight enough

Algorithm 1: DecidePAC

Input: Procedure A, query α, validity ϵ ∈ (0, 1), list

of partial intervals {φ(1) , ..., φ(m) }, knowledge base ∆ Output: Accept/Reject begin B ← ⌊ϵ × m⌋, F AILED ← 0. foreach k in 1..m do if A(α, φ(k) , ∆) returns UNSAT then Increment FAILED. if FAILED > B then return Reject;

return Accept

on the wrist, no guarantees can be made about all the sensor readings being complete. In this example, some values for oxygen are missing.

Using DecidePAC (cf. Algorithm 1), the watch answers the query by means of entailment for each of the readings received and the knowledge base: ∆ ∧ φ(m) |= α. It receives the readings φ(1) , φ(2) , φ(3) , out of which the first and third yield entailment, whereas the second does not (because {hr = 92, ox = 99} leads to stress = 47 < 50). The third set of intervals, φ(3) , triggers validity despite missing data, as the stress level is above 50 for any possible values of ox. Our validity parameter ϵ = 0.4 allows the algorithm to return acceptance with (1 - ϵ) validity of the query after seeing two out of three positive readings.

4 Extending the LearningModel

In this section, we extend the framework to deal with intervals as opposed to assignments and prove that polynomial-time guarantees are preserved. We refer to a masking process in the context of intervals φ as a blurring process, as introduced below 1 :

Definition 5. [Blurring process] Given a full assignment ρ(k) = {ρ1 ρ1 ρ1, . . . , ρn ρn ρn}, a blurring function is defined as B : Σn → {Σ ∪ {-∞, +∞}}2n , which produces a set of intervals φ(k) consistent with the assignment ρ(k) , i.e., with the property that for each ρi, B(ρ)2i-1 ≤ ρi ≤ B(ρ)2i, where B(ρ)2i-1 is a random value from (-∞, ρi] marking the lower bound of the interval and B(ρ)2i is a random value from [ρi,∞) marking the upper bound. We refer to elements of the resulting set as partial intervals, where a full assignment is bound by the lower and upper bound. A blurring process B is a blur-valued random variable (i.e. a random function). We denote the distribution over intervals obtained by applying the blurring process as B(D).

The blurring function essentially offers a generalization of the masking process in order to model uncertainty about complete assignments. For each interval, we draw one lower and one upper bound, hence the endpoints of the nth interval occupy indices 2n - 1 and 2n. Using the blurring process, we allow observations to be not only (i) unknown (masked) but also (ii) uncertain, and this degree of uncertainty is given by the width of the interval in which the real value lies.

1 We use superscript to represent the index of the assignment, and subscript to represent the index of the variable in each assignment.

Example 6. Given a full assignment ρ : {x = 4, y = 5}, after applying a blurring process on this assignment, we may obtain the intervals set φ : {(1 ≤ x), (x ≤ 6), (-∞ ≤ y), (y ≤ ∞)}.

In the above example, the value of x has increased in uncertainty, in the sense that we have a small range of possible values. The value of y has been extended on both sides to ∞ and denotes complete uncertainty (equivalent to the effect of a masking process). In other words, the relaxation of a fixed value/assignment to the interval directly corresponds to the uncertainty about the value.

The output of a blurring process is a list of partial intervals. In order to integrate these observations in a decision procedure, i.e., entailment, they require an additional transformation into logical formulas:

Definition 7. [Grounding ↓] Given a partial interval φ(k) = {φ1, ..., φ2n}, we define φ(k) ↓ as the ground formula corresponding to the set of intervals and represented as a set of constraints, i.e., φ(k) ↓= φ1 ∧ ... ∧ φ2n.

In the evaluation procedure, we define a formula to be witnessed to evaluate to true given partial intervals as follows:

Definition 8. [Witnessed formulas] A formula ϕ is witnessed true under partial intervals φ if (φ ↓) |= ϕ , i.e. ϕ is true under every assignment possible under φ.

In [Mocanu et al., 2020], it was shown that, if ∆ |= α, then ∆|ρ |= α|ρ, where ρ is a partial assignment. The key difference in our work is that instead of partial assignments, we use partial intervals. However, since partial intervals are well defined formulas of QFLRA, this property directly extends to our case and the proof is analogous to [Mocanu et al., 2020].

Proposition 9. For the language of QFLRA, let A be a sound and complete decision procedure. If ∆ |= α, then ∆|φ |= α|φ. Equivalently, if A(∆, α), then A(∆|φ, α|φ) iff A(∆ ∧ φ ↓, α).

We can now prove that implicit learning remains possible with our extended framework and that existing polynomialtime guarantees from the assignment setting are preserved:

Theorem 10. [Implicit learning] Let ∆ be a conjunction of constraints representing the knowledge base and α an input query. We draw at random m = 1 2γ 2 ln 1δ sets of intervals {φ(1) , φ(2) , ..., φ(m) } from B(D) for the distribution D and a blurring process B. Suppose that we have a decision procedure A. Then with probability 1 - δ:

• If (∆⇒α) is not (1- ϵ -γ) - valid with respect to the distributionD, theDecidePACalgorithm returns Reject; and
• If there exists some KB I such that ∆∧ I |= α and I is witnessed true with probability at least (1 - ϵ + γ) on B(D), then DecidePAC returns Accept.

Moreover, if A runs in polynomial-time (in the number of variables, size of the query, and size of the knowledge base), so does DecidePAC.

Proof. Consider a sound and complete decision procedure A for the language domain aforementioned and the reasoning problem of deciding ∆ |= α. By definition of soundness and completeness, ∆ |= α if and only if A(∆ ∧ ¬α) = UNSAT. Suppose we receive observations about the world as sets of blurred intervals φ and we wish to decide entailment of the aforementioned problem with respect to these blurred observations, hence calculate A(∆|φ∧¬α|φ) = UNSAT. This holds iff A(∆ ∧ φ ↓ ∧¬α) = UNSAT, iff A(∆ ∧ I ∧ φ ↓ ∧¬α) = UNSAT for any KB I that is witnessed true under φ. Now the argument becomes analogous to Juba [2013]: if ∆ ⇒ α is unsatisfied on a point drawn fromD, it is not entailed by the blurred example from B(D) either, so FAILED increments when such points are drawn, and does not increment when a suitable I is witnessed true. By Hoeffding's inequality, the returned value satisfies the given conditions with probability 1 - δ for m examples. The decision procedure will return UNSAT in polynomial time T (n) depending on the size of the knowledge base and query. Every iteration costs the time for checking feasibility which is bounded by the time complexity of the decision procedure used for deciding satisfiability. The total number of iterations is m= 1 2γ 2 log 1δ , corresponding to the number of samples drawn, which gives us the total time bound of O(T(n) · 1 γ 2 log 1δ ).

With this theorem, we have extended the previous result to deal with the more complex setting of threshold uncertainty, which is a much more realistic learning model. In QFLRA, the decision procedure is polynomial-time [Barrett et al., 2009] and blurred examples have the natural interpretation of being imprecise measurements. However, Theorem 10 is in principle applicable to any decidable fragment of SMT. Interpreting blurred examples for other domains (e.g., as noisy observations in the form of disjunctions of partial models) is certainly interesting, but will be left as a direction for the future.

Like the previous PAC-Semantics results, implicit learning is geared for answering queries, and has been primarily a theoretical framework. In contrast, conventional methods, although not always offering learnability guarantees, provide an explicit model, making it harder to compare with the above framework and study the trade-offs. The next section shows how this is now possible.

5 Applying PAC-Semantics to Optimisation

The goal in optimisation problems is to find an optimal objective value given constraints. We propose Algorithm 2, OptimisePAC, which solves optimisation problems using DecidePAC. This allows us to compare our framework to other more traditional methods, since optimisation problems are widely studied. In particular, we will use OptimisePAC in our empirical analysis for the case of LPs. The correctness and running time are as follows:

Theorem 11. Let ∆ be a conjunction of constraints representing the knowledge base and as input preference function f. We draw at random m = O( 1 γ 2 log 1δ ) partial intervals φ(1) , ..., φ(m) fromB(D) for a distribution D and a blurring

Algorithm 2: OptimisePAC

Input: Procedure A, preference function f, validity ϵ ∈ (0, 1), accuracy a ∈ Z+, list of intervals φ = {φ(1) , φ(2) , ..., φ(m) }, goal ∈ {"max", "min"} Output: estimated optimal value w.r.t. f begin if goal = "min" then f ←-f; if DecidePAC(A, 0 ≥ f, ϵ, φ) accepts then if DecidePAC(A, -1 ≥ f, ϵ, φ) rejects then l ← -1, u ← 0 elseb ← -2 while DecidePAC(A, b ≥ f, ϵ, φ) accepts dob ← b × 2 l ← b, u ← b/2 else if DecidePAC(A, 1 ≥ f, ϵ, φ) accepts then l ← 0, u ← 1 elseb ← 2 while DecidePAC(A, b ≥ f, ϵ, φ) rejects do b ← b × 2 l ← b/2, u ← b for a iterations do if DecidePAC(A, (l + u)/2 ≥ f, ϵ, φ) accepts then u ← (l + u)/2 elsel ← (l + u)/2 if goal = "min" then return -l else return l ;

process B. Suppose that we have a decision procedure A running in time T(n). Then, the OptimisePAC algorithm will return a significant bits of a value v∗ that is attainable on I ∧∆ for all KBs I that are witnessed with probability 1-ϵ+γ, and such that for the value u∗ obtained by incrementing the ath bit, ∆ ⇒ (f ≤ u∗ ) is (1 - ϵ - γ)-valid (resp., f ≥ u∗ with the ath bit decreased if minimising) in time O(T(n) · m · a).

Proof. OptimisePAC first finds the approximate bounds of the optimal value by doubling the bound each iteration and running DecidePAC. If a lower bound b/2 and an upper bound b are found, it runs binary search to find the optimal value to the desired precision. If the decision procedure runs in time T(n), the total running time stated in the theorem follows.

To prove correctness, we will use a theorem due to Talagrand [1994] (Theorem 4.9 of [Anthony and Bartlett, 1999]):

Theorem 12. [[Anthony and Bartlett, 1999, Theorem 4.9]] There are positive constants c1, c2, c3 such that the following holds. Suppose that F is a set of functions defined on the domain X and that F has a finite VC dimension d. Let γ ∈ (0, 1) and m ∈ Z+. Then the probability that the empirical mean of any f ∈ F on m examples differs from its expectation by more than γ is at most c1cd2 e-c3γ 2m.

Thus, for m≥ c3 γ 2 (d ln c2 + ln c1 δ ), the bound is at most δ.

Recall, the VC dimension is the size of the largest set of points that can be given all labels by a class ("shattered"). Consider a fixed class of Boolean functions on the blurred samples, which is parameterized by the objective value bounds b. This function outputs the value 1 whenever ∆ ∧ φ ∧ (f(x) ≤ b) returns UNSAT, and 0 otherwise. We will show that this class has VC-dimension at most 1.

We will show that for any two blurred examples φ1 and φ2, it is not possible to get all the labellings {(1, 1), (1, 0), (0, 1), (0, 0)} by varying b. Suppose there is some b∗ for which φ1 gives the label 1 and φ2 gives 0, meaning that for φ1 the bound f ≤ b∗ does not hold and for φ2 it does. Since f ≤ b∗ holds for φ2, then for any b > b∗ , the decision procedure will return 0 for φ2. On the other hand, the bound f ≤ b∗ will not hold for φ1 for all values b < b∗ . Thus, in either direction, one of the labels for one of the two remains the same. So, it is not possible to get all possible labellings of φ1 and φ2 and so the VC-dimension is ≤ 1.

Therefore, by Talagrand's bound, given m examples, with probability 1-δ, DecidePAC answers correctly for all queries made by OptimisePAC. In particular, we note that the algorithm maintains the invariant that l is the largest value for which l ≥ f was rejected by DecidePAC. Since it was not accepted, we see that for any I that is witnessed with probability ≥ 1 - ϵ + γ, there must exist some x satisfying I ∧ ∆ with f(x) > l (resp., f(x) < l if minimising). Since DecidePAC does not reject with u, ∆ ⇒ f(x) ≤ u is (1 - ϵ - γ)-valid, where u and l only differ by the value of the ath most significant bit. Thus l is as needed.

6 Empirical Analysis

Implicit learning in PAC-Semantics has been described rigorously on a theoretical level. However, to the best of our knowledge, the framework has never been analysed in practice. In this section, we present the first implementation of the PAC-Semantics framework. 2 We will use it to empirically study the differences between an implicit and explicit approach for LP problems. LP is an optimisation technique for a linear objective function. The problem consists of an optimisation function f(⃗x), where ⃗x ∈ Rn , and feasibility region expressed as the set of constraints A · ⃗x ≤ b. We chose LPs as the domain, as they can be represented in QFLRA, and are thus polynomial-time. It also allows us to directly evaluate our framework using existing benchmarks. We will analyse the following four points: running time, accuracy of objective value estimates, noise and outlier resistance.

6.1 Implementation Setup

The implementation is written in Python and uses the Z3 Theorem Solver [de Moura and Bjørner, 2008] for SMT queries. The explicit solver we compare it to is IncaLP(SMT), an algorithm that learns linear arithmetic SMT formulas from data [Schede et al., 2019]. In this paper, we refer to IncaLP(SMT) simply as IncaLP.

2 The code can be found at https://github.com/APRader/pac-smt-arithmetic

simplexn running times

We use the following benchmark LP problems for our analysis: simplexn, cuben, pollution and police [Hillier and Lieberman, 1995]. All these problems consist of a set of hard constraints, which define the feasible region or the boundaries of the shape and a set of soft constraints in the form of a linear objective function, which can be either maximised or minimised. The goal is to find the optimum objective value within the hard constraints. For example, the feasible region in simplexn is an intersection of 1 2 n(n-1) uniform triangular prisms and the objective function for pollution represents the amount of pollution and has to be minimised.

The implicit PAC approach and the explicit IncaLP approach differ in how they reach this goal: in the PAC model, we directly compute the optimal objective value from positive examples using OptimisePAC. In contrast, the IncaLP approach first creates an SMT model from positive and negative examples. Using standard MaxSMT techniques, we can then find the optimal objective value within the model.

We ran tests on all four problems. For each test, we had 20 independent runs on increasing sample sizes from 50 to 500 and increasing dimensions from 2 to 4, if applicable. We used 50% positive and 50% negative samples. A timeout of 30 minutes was set for each run. To ensure reproducibility, we ran each test with the seed 1613 (a numerical encoding of "PAC"). The hardware we used was an Intel Core i7-6700 3.40GHz, with 16 GB of RAM running Ubuntu 20.04.

As for parameter settings, we chose the SelectDT heuristic for the IncaLP approach, as it is the most appropriate according to their paper. We also ran our experiments using the same initial configurations as their released code. We set the accuracy for OptimisePAC to 60, which is the number of times our intervals are divided by 2. The reason being that we can match the accuracy of double precision floating-point values, which is about 2-53 .

6.2 Results

On the theoretical front, one of the advantages of implicit learning is argued to be efficiency, since you can skip the step of creating an explicit model. As shown in Figure 2, this effect is significant in practice for linear programs. PAC is able to get similarly good objective value estimates at significantly lower running times for simplexn. The larger the sample size and the higher the dimensionality, the bigger the gap between running times. (For all of our graphs, the sample standard deviation is shown.)

With the extension we introduced in this paper, PAC can now handle noisy data using intervals. If we add Gaussian noise with a standard deviation σ to each data point, we can represent it using intervals of width 4 log d · σ, where d is the dimensionality. This interval covers about 95% of the density, which is why we set a validity of 95% for DecidePAC. The noise and intervals were capped at the domain boundaries. We adjusted the noise to the dimensionality, meaning that for a noise value of n, the std of the Gaussian σ = n √d . We also tested robustness against outliers. For our purposes, an outlier is a point within the domain with a wrong label.

Figure 3 shows how PAC compares to IncaLP. In cases where IncaLP does find a model, it gives an estimate that is pollution objective value estimates closer to the true objective value in noisy cases. However, it failed to find a model 25%, 59% and 68% of the time for a noise of 0.1, 0.25 and outliers of 0.01, respectively. Moreover, the PAC estimate is pessimistic on purpose. This results in values farther away from the optimum but ensures that they are reachable. PAC always finds feasible objective values, while IncaLP undershoots the minimum for pollution almost always. 3

It is also worth noting these results do not mean that IncaLP, on the whole, is inferior to our PAC implementation. IncaLP creates a model, while PAC answers queries implicitly. For some problems, such as objective value optimisation, it is possible to skip the model making process. As we have shown, doing that comes with advantages in speed and noise resistance. However, in some contexts, having an explicit model is desirable, in which case the implicit learning paradigm might be harder to work with. Put simply, OptimisePAC is not a replacement for IncaLP.

7 RelatedWork

We identify two threads of related research. On the theoretical side, the problem of dealing with missing information in learning settings was recognized early on in the literature. For example, to analyze how incomplete data affects predictions, [Schuurmans and Greiner, 1994] look at various ways of altering the input data, according to a product distribution or via masking. In [Kearns and Schapire, 2001], a framework is proposed that uses incomplete observations to predict a hypothesis function and never output a "don't know" answer. These and related approaches, however, focus on a discrete model and do not cover continuous-valued domains. There is, of course, also a large body of work on techniques like imputation, but these are far afield from our goals.

Conceptually, it is perhaps also interesting to contrast this line of work with inductive logic programming (ILP) [Muggleton and de Raedt, 1994]: the latter searches for a hypothesis H that is consistent with the examples by appealing to entailment. Like IncaLP, it does not, however, seek to analyze the degree to which the resulting formulas capture an unknown, ground-truth process that produced the examples.

3 The empirical behavior is similar across the four problems. All graphs are included in the extended report [Rader et al., 2020].

For more discussions on how implicit learning via the PACSemantics differs from such hypothesis generation methodologies, including probabilistic structure learning schemes, see [Juba, 2013; Belle and Juba, 2019].

On the empirical side, many methods for inducing linear constraints from data use greedy or approximate learning schemes, e.g., [Kantchelian et al., 2014]. To overcome the problems of overfitting, local optima or noise-robustness, approaches like syntax-guided learning [Alur et al., 2013] have been proposed, in which the learning problem is reduced to an optimisation problem. See [Schede et al., 2019] for a comprehensive discussion. Similar to IncaLP, work by [Pawlak and Krawiec, 2017] proposes an approach of approximating the set of constraints from feasible and infeasible examples, which focuses on mixed integer linear programs, but without any theoretical guarantees.

8 Conclusion

In this work, we proposed a general framework for learning implicitly in linear arithmetic from noisy examples. By then considering a novel optimisation variant, we were able to empirically compare and outperform an explicit approach in terms of running time and resistance to noise and outliers for LP problems. A natural direction for the future is to consider whether this implementation strategy extends to other classes of formulas in first-order logic and/or SMT. In particular, it is worth conducting empirical investigations into polynomial-time fragments of SMT other than LPs.

Acknowledgements

We would like to thank our reviewers for their helpful suggestions. Alexander Rader conducted this work while at the University of Edinburgh. Ionela Georgiana Mocanu was supported by the Engineering and Physical Sciences Research Council (EPSRC) Centre for Doctoral Training in Pervasive Parallelism (grant EP/L01503X/1) at the University of Edinburgh, School of Informatics. Vaishak Belle was supported by a Royal Society University Research Fellowship. Brendan Juba was supported by NSF/Amazon award IIS-1939677.