Integrity constraints such as functional dependencies (FD), and multi-valued dependencies (MVD)
are fundamental in database schema design. Likewise, probabilistic conditional independences (CI)
are crucial for reasoning about multivariate probability distributions. The implication problem
studies whether a set of constraints (antecedents) implies another constraint (consequent), and
has been investigated in both the database and the AI literature, under the assumption that all
constraints hold exactly. However, many applications today consider constraints that hold only
approximately. In this paper we define an approximate implication as a linear inequality between
the degree of satisfaction of the antecedents and consequent, and we study the relaxation problem:
when does an exact implication relax to an approximate implication? We use information theory
to define the degree of satisfaction, and prove several results. First, we show that any implication
from a set of data dependencies (MVDs+FDs) can be relaxed to a simple linear inequality with
a factor at most quadratic in the number of variables; when the consequent is an FD, the factor
can be reduced to 1. Second, we prove that there exists an implication between CIs that does not
admit any relaxation; however, we prove that every implication between CIs relaxes “in the limit”.
Finally, we show that the implication problem for differential constraints in market basket analysis
also admits a relaxation with a factor equal to 1. Our results recover, and sometimes extend, several
previously known results about the implication problem: implication of MVDs can be checked by
considering only 2-tuple relations, and the implication of differential constraints for frequent item
sets can be checked by considering only databases containing a single transaction.
more »
« less
Model-Free Reinforcement Learning for Lexicographic Omega-Regular Objectives
We study the problem of finding optimal strategies in Markov decision processes with lexicographic ω-regular objectives, which are ordered collections of ordinary ω-regular objectives. The goal is to compute strategies that maximise the probability of satisfaction of the first 𝜔-regular objective; subject to that, the strategy should also maximise the probability of satisfaction of the second ω-regular objective; then the third and so forth. For instance, one may want to guarantee critical requirements first, functional ones second and only then focus on the non-functional ones. We show how to harness the classic off-the-shelf model-free reinforcement learning techniques to solve this problem and evaluate their performance on four case studies.
more »
« less
- Award ID(s):
- 2009022
- NSF-PAR ID:
- 10329426
- Editor(s):
- Huisman, M.; Păsăreanu, C.; Zhan, N.
- Date Published:
- Journal Name:
- Formal Methods (FM 2021)
- Page Range / eLocation ID:
- 142-159
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
For a graph G on n vertices, naively sampling the position of a random walk of at time t requires work Ω(t). We desire local access algorithms supporting positionG(t) queries, which return the position of a random walk from some fixed start vertex s at time t, where the joint distribution of returned positions is 1/ poly(n) close to those of a uniformly random walk in ℓ1 distance. We first give an algorithm for local access to random walks on a given undirected d-regular graph with eO( 1 1−λ √ n) runtime per query, where λ is the second-largest eigenvalue of the random walk matrix of the graph in absolute value. Since random d-regular graphs G(n, d) are expanders with high probability, this gives an eO(√ n) algorithm for a graph drawn from G(n, d) whp, which improves on the naive method for small numbers of queries. We then prove that no algorithm with subconstant error given probe access to an input d-regular graph can have runtime better than Ω(√ n/ log(n)) per query in expectation when the input graph is drawn from G(n, d), obtaining a nearly matching lower bound. We further show an Ω(n1/4) runtime per query lower bound even with an oblivious adversary (i.e. when the query sequence is fixed in advance). We then show that for families of graphs with additional group theoretic structure, dramatically better results can be achieved. We give local access to walks on small-degree abelian Cayley graphs, including cycles and hypercubes, with runtime polylog(n) per query. This also allows for efficient local access to walks on polylog degree expanders. We show that our techniques apply to graphs with high degree by extending or results to graphs constructed using the tensor product (giving fast local access to walks on degree nϵ graphs for any ϵ ∈ (0, 1]) and Cartesian product.more » « less
-
Integrity constraints such as functional dependencies (FD) and multi-valueddependencies (MVD) are fundamental in database schema design. Likewise,probabilistic conditional independences (CI) are crucial for reasoning aboutmultivariate probability distributions. The implication problem studies whethera set of constraints (antecedents) implies another constraint (consequent), andhas been investigated in both the database and the AI literature, under theassumption that all constraints hold exactly. However, many applications todayconsider constraints that hold only approximately. In this paper we define anapproximate implication as a linear inequality between the degree ofsatisfaction of the antecedents and consequent, and we study the relaxationproblem: when does an exact implication relax to an approximate implication? Weuse information theory to define the degree of satisfaction, and prove severalresults. First, we show that any implication from a set of data dependencies(MVDs+FDs) can be relaxed to a simple linear inequality with a factor at mostquadratic in the number of variables; when the consequent is an FD, the factorcan be reduced to 1. Second, we prove that there exists an implication betweenCIs that does not admit any relaxation; however, we prove that everyimplication between CIs relaxes "in the limit". Then, we show that theimplication problem for differential constraints in market basket analysis alsoadmits a relaxation with a factor equal to 1. Finally, we show how some of theresults in the paper can be derived using the I-measure theory, which relatesbetween information theoretic measures and set theory. Our results recover, andsometimes extend, previously known results about the implication problem: theimplication of MVDs and FDs can be checked by considering only 2-tuplerelations.more » « less
-
With the increasing adoption of smart home devices, users rely on device automation to control their homes. This automation commonly comes in the form of smart home routines, an abstraction available via major vendors. Yet, questions remain about how a system should best handle conflicts in which different routines access the same devices simultaneously. In particular---among the myriad ways a smart home system could handle conflicts, which of them are currently utilized by existing systems, and which ones result in the highest user satisfaction? We investigate the first question via a survey of existing literature and find a set of conditions, modifications, and system strategies related to handling conflicts. We answer the second question via a scenario-based Mechanical-Turk survey of users interested in owning smart home devices and current smart home device owners (N=197). We find that: (i) there is no context-agnostic strategy that always results in high user satisfaction, and (ii) users' personal values frequently form the basis for shaping their expectations of how routines should execute.more » « less
-
Election control considers the problem of an adversary who attempts to tamper with a voting process, in order to either ensure that their favored candidate wins (constructive control) or another candidate loses (destructive control). As online social networks have become significant sources of information for potential voters, a new tool in an attacker’s arsenal is to effect control by harnessing social influence, for example, by spreading fake news and other forms of misinformation through online social media. We consider the computational problem of election control via social influence, studying the conditions under which finding good adversarial strategies is computationally feasible. We consider two objectives for the adversary in both the constructive and destructive control settings: probability and margin of victory (POV and MOV, respectively). We present several strong negative results, showing, for example, that the problem of maximizing POV is inapproximable for any constant factor. On the other hand, we present approxima- tion algorithms which provide somewhat weaker approximation guarantees, such as bicriteria approximations for the POV objective and constant-factor approximations for MOV. Finally, we present mixed integer programming formulations for these problems. Ex- perimental results show that our approximation algorithms often find near-optimal control strategies, indicating that election control through social influence is a salient threat to election integrity.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1007/978-3-030-90870-6_8
