Abstract: Abstract This paper proposes an algorithm to reason on constraints expressed in terms of polynomials with integer coefficients whose variables take values from finite subsets of the integers. The proposed algorithm assumes that an initial approximation of the domains of variables is available in terms of a bounding box, and it recursively subdivides the box into disjoint boxes until a termination condition is met. The algorithm includes three termination conditions that allow using it for three related reasoning tasks: constraint satisfaction, enumeration of solutions, and hyper-arc consistency enforcement. Considered termination conditions are based on suitable lower and upper bounds for polynomial functions over boxes that are determined using new results proved in the paper. The algorithm is particularly appropriate to reason on high-degree polynomial constraints because the proposed method to determine lower and upper bounds can outperform alternative methods when high-degree polynomials in a moderate number of variables are considered. PubDate: 2019-12-05

Abstract: Abstract Recently, Mahloujifar and Mahmoody (Theory of Cryptography Conference’17) studied attacks against learning algorithms using a special case of Valiant’s malicious noise, called p-tampering, in which the adversary gets to change any training example with independent probability p but is limited to only choose ‘adversarial’ examples with correct labels. They obtained p-tampering attacks that increase the error probability in the so called ‘targeted’ poisoning model in which the adversary’s goal is to increase the loss of the trained hypothesis over a particular test example. At the heart of their attack was an efficient algorithm to bias the expected value of any bounded real-output function through p-tampering. In this work, we present new biasing attacks for increasing the expected value of bounded real-valued functions. Our improved biasing attacks, directly imply improved p-tampering attacks against learners in the targeted poisoning model. As a bonus, our attacks come with considerably simpler analysis. We also study the possibility of PAC learning under p-tampering attacks in the non-targeted (aka indiscriminate) setting where the adversary’s goal is to increase the risk of the generated hypothesis (for a random test example). We show that PAC learning is possible under p-tampering poisoning attacks essentially whenever it is possible in the realizable setting without the attacks. We further show that PAC learning under ‘no-mistake’ adversarial noise is not possible, if the adversary could choose the (still limited to only p fraction of) tampered examples that she substitutes with adversarially chosen ones. Our formal model for such ‘bounded-budget’ tampering attackers is inspired by the notions of adaptive corruption in cryptography. PubDate: 2019-12-03

Abstract: Moser and Tardos (J. ACM (JACM) 57(2), 11 2010) gave an algorithmic proof of the lopsided Lovász local lemma (LLL) in the variable framework, where each of the undesirable events is assumed to depend on a subset of a collection of independent random variables. For the proof, they define a notion of a lopsided dependency between the events suitable for this framework. In this work, we strengthen this notion, defining a novel directed notion of dependency and prove the LLL for the corresponding graph. We show that this graph can be strictly sparser (thus the sufficient condition for the LLL weaker) compared with graphs that correspond to other extant lopsided versions of dependency. Thus, in a sense, we address the problem “find other simple local conditions for the constraints (in the variable framework) that advantageously translate to some abstract lopsided condition” posed by Szegedy (2013). We also give an example where our notion of dependency graph gives better results than the classical Shearer lemma. Finally, we prove Shearer’s lemma for the dependency graph we define. For the proofs, we perform a direct probabilistic analysis that yields an exponentially small upper bound for the probability of the algorithm that searches for the desired assignment to the variables not to return a correct answer within n steps. In contrast, the method of proof that became known as the entropic method, gives an estimate of only the expectation of the number of steps until the algorithm returns a correct answer, unless the probabilities are tinkered with. PubDate: 2019-12-02

Abstract: Abstract By their very design, many robot control programs are non-terminating. This paper describes a situation calculus approach to expressing and proving properties of non-terminating programs expressed in Golog, a high level logic programming language for modeling and implementing dynamical systems. Because in this approach actions and programs are represented in classical (second-order) logic, it is natural to express and prove properties of Golog programs, including non-terminating ones, in the very same logic. This approach to program proofs has the advantage of logical uniformity and the availability of classical proof theory. PubDate: 2019-11-18

Abstract: Abstract We consider the binary classification problem when data are large and subject to unknown but bounded uncertainties. We address the problem by formulating the nonlinear support vector machine training problem with robust optimization. To do so, we analyze and propose two bounding schemes for uncertainties associated to random approximate features in low dimensional spaces. The proposed bound calculations are based on Random Fourier Features and the Nyström methods. Numerical experiments are conducted to illustrate the benefit of the technique. We also emphasize the decomposable structure of the proposed robust nonlinear formulation that allows the use of efficient stochastic approximation techniques when datasets are large. PubDate: 2019-11-15

Abstract: Abstract This article presents a novel, nonlinear, data-driven signal processing method, which can help neuroscience researchers visualize and understand complex dynamical patterns in both time and space. Specifically, we present applications of a Koopman operator approach for eigendecomposition of electrophysiological signals into orthogonal, coherent components and examine their associated spatiotemporal dynamics. This approach thus provides enhanced capabilities over conventional computational neuroscience tools restricted to analyzing signals in either the time or space domains. This is achieved via machine learning and kernel methods for data-driven approximation of skew-product dynamical systems. The approximations successfully converge to theoretical values in the limit of long embedding windows. First, we describe the method, then using electrocorticographic (ECoG) data from a mismatch negativity experiment, we extract time-separable frequencies without bandpass filtering or prior selection of wavelet features. Finally, we discuss in detail two of the extracted components, Beta (\( \sim \) 13 Hz) and high Gamma (\( \sim \) 50 Hz) frequencies, and explore the spatiotemporal dynamics of high- and low- frequency components. PubDate: 2019-11-11

Abstract: Abstract Graph transformation theory uses rules to perform a graph transformation. However, there is no a way to choose between such different transformations in the case where several of them are applicable. A way to get the choice is suggested here based on the comparing of the values of implications which correspond to different transformation variants. The relationship between the topos of bundles, and the set of graphs with the same vertices, is introduced to include logic into graph transformation theory. Thus, one can use the special type of implication and the truth-values set of such a topos to estimate different variants of graph transformations. In this approach, the maximal part of the initial graph towards the terminal one is conserved in the chosen variant. Analysis of self-adaptive systems uses some graph grammars. Self-adaptive systems autonomously perform an adaptation to changes both in user needs and in their operational environments, while still maintaining some desired properties. The suggested way to choose such graph transformation variants may be used to make a choice between different graph grammars in such systems modeling. This approach is illustrated in a model of some business processes, that result in the automated choice of the business process adaptation under the assumption that the process changes are minimal towards the terminal state. PubDate: 2019-11-02

Abstract: Abstract This paper is about the statics and dynamics of belief states that are represented by pairs consisting of an agent’s credences (represented by a subjective probability measure) and her categorical beliefs (represented by a set of possible worlds). Regarding the static side, we argue that the latter proposition should be coherent with respect to the probability measure and that its probability should reach a certain threshold value. On the dynamic side, we advocate Jeffrey conditionalisation as the principal mode of changing one’s belief state. This updating method fits the idea of the Lockean Thesis better than plain Bayesian conditionalisation, and it affords a flexible method for adding and withdrawing categorical beliefs. We show that it fails to satisfy the traditional principles of Inclusion and Preservation for belief revision and the principle of Recovery for belief withdrawals, as well as the Levi and Harper identities. We take this to be a problem for the latter principles rather than for the idea of coherent belief change. PubDate: 2019-11-01

Abstract: Abstract Values are at the heart of human decision-making. They are used to decide whether something or some state of affairs is good or not, and they are also used to address the moral dilemma of the right thing to do under given circumstances. Both uses are present in several everyday situations, from the design of a public policy to the negotiation of employee benefit packages. Both uses of values are specially relevant when one intends to design or validate that artificial intelligent systems behave in a morally correct way. In real life, the choice of policy components or the agreed upon benefit package are processes that involve argumentation. Likewise, the design and deployment of value-driven artificial entities may be well served by embedding practical reasoning capabilities in these entities or using argumentation for their design and certification processes. In this paper, we propose a formal framework to support the choice of actions of a value-driven agent and arrange them into plans that reflect the agent’s preferences. The framework is based on defeasible argumentation. It presumes that agent values are partially ordered in a hierarchy that is used to resolve conflicts between incommensurable values. PubDate: 2019-11-01

Abstract: Abstract This work explores formal aspects of model repair, i.e., how to rationally modify Kripke models representing the behavior of a system in order to satisfy a desired property. We investigate the problem in the light of Alchourrón, Gärdenfors, and Makinson’s work on belief revision. We propose two AGM-style characterizations of model repair: one based on belief sets and the other based on structural changes. In the first characterization, we define a set of rationality postulates over formulas with a close correspondence to those in the classical belief revision theory. We show that the proposed set of postulates fully characterizes the expected rationality of modifications in the model repair problem. In the second characterization, we propose a new set of rationality postulates based on structural modifications on models. These postulates have a close correspondence to the classical approach of model repair, while preserving the same rationality of the first characterization. We provide two representation results and the connection between them. PubDate: 2019-11-01

Abstract: Abstract Three seemingly weak and plausible conditions on an operation of contraction on belief sets are shown to be logically incompatible: (1) there is at least one sentence that can be successfully removed by the operation, (2) both the original belief set and the outcome of the operation have finite representations, and (3) a non-tautologous sentence can be removed without loss of all its non-tautologous logical consequences. PubDate: 2019-11-01

Abstract: Abstract This is a survey of some recent results relating Dung-style semantics for different types of logical argumentation frameworks and several forms of reasoning with maximally consistent sets (MCS) of premises. The related formalsims are also examined with respect to some rationality postulates and are carried on to corresponding proof systems for non-monotonic reasoning. PubDate: 2019-11-01

Abstract: Abstract Deep Learning methods have been rising in popularity in the past few years, and are now used as a fundamental component in various application domains such as computer vision, natural language processing, bioinformatics. Supervised learning with Convolutional Neural Networks has become the state of the art approach in many image related works. However, despite the great success of deep learning methods in other areas they remain relatively unexplored in the brain imaging field. In this paper we make an overview of recent achievements of Deep Learning to automatically extract features from brain signals that enable building Brain-Machine Interfaces (BMI). Major challenge in the BMI research is to find common subject-independent neural signatures due to the high brain data variability across multiple subjects. To address this problem we propose a Deep Neural Autoencoder with sparsity constraint as a promising approach to extract hidden features from Electroencephalogram data (in-dept feature learning) and build a subject-independent noninvasive BMI in the affective neuro computing framework. Future direction for research are also outlined. PubDate: 2019-10-02

Abstract: Abstract For any query language \(\mathcal {F}\) , we consider three natural families of boolean queries. Nonemptiness queries are expressed as e ≠ ∅ with e an \(\mathcal {F}\) expression. Emptiness queries are expressed as e = ∅. Containment queries are expressed as e1 ⊆ e2. We refer to syntactic constructions of boolean queries as modalities. In first order logic, the emptiness, nonemptiness and containment modalities have exactly the same expressive power. For other classes of queries, e.g., expressed in weaker query languages, the modalities may differ in expressiveness. We propose a framework for studying the expressive power of boolean query modalities. Along one dimension, one may work within a fixed query language and compare the three modalities. Here, we identify crucial query features that enable us to go from one modality to another. Furthermore, we identify semantical properties that reflect the lack of these query features to establish separations. Along a second dimension, one may fix a modality and compare different query languages. This second dimension is the one that has already received quite some attention in the literature, whereas in this paper we emphasize the first dimension. Combining both dimensions, it is interesting to compare the expressive power of a weak query language using a strong modality, against that of a seemingly stronger query language but perhaps using a weaker modality. We present some initial results within this theme. The two main query languages to which we apply our framework are the algebra of binary relations, and the language of conjunctive queries. PubDate: 2019-10-01

Abstract: Abstract Description logics have been extended in a number of ways to support defeasible reasoning in the KLM tradition. Such features include preferential or rational defeasible concept inclusion, and defeasible roles in complex concept descriptions. Semantically, defeasible subsumption is obtained by means of a preference order on objects, while defeasible roles are obtained by adding a preference order to role interpretations. In this paper, we address an important limitation in defeasible extensions of description logics, namely the restriction in the semantics of defeasible concept inclusion to a single preference order on objects. We do this by inducing a modular preference order on objects from each modular preference order on roles, and using these to relativise defeasible subsumption. This yields a notion of contextualised rational defeasible subsumption, with contexts described by roles. We also provide a semantic construction for rational closure and a method for its computation, and present a correspondence result between the two. PubDate: 2019-10-01

Abstract: Abstract Several different semantics have been proposed for conditional knowledge bases \(\mathcal {R}\) containing qualitative conditionals of the form “If A, then usually B”, leading to different nonmonotonic inference relations induced by \(\mathcal {R}\) . For the notion of c-representations which are a subclass of all ranking functions accepting \(\mathcal {R}\) , a skeptical inference relation, called c-inference and taking all c-representations of \(\mathcal {R}\) into account, has been suggested. In this article, we develop a 3-phase compilation scheme for both knowledge bases and skeptical queries to constraint satisfaction problems. In addition to skeptical c-inference, we show how also credulous and weakly skeptical c-inference can be modelled as constraint satisfaction problems, and that the compilation scheme can be extended to such queries. We further extend the compilation approach to knowledge bases evolving over time. The compiled form of \(\mathcal {R}\) is reused for incrementally compiling extensions, contractions, and updates of \(\mathcal {R}\) . For each compilation step, we prove its soundness and completeness, and demonstrate significant efficiency benefits when querying the compiled version of \(\mathcal {R}\) . These findings are also supported by experiments with the software system InfOCF that employs the proposed compilation scheme. PubDate: 2019-08-30

Abstract: Abstract The transmission of own and partly confidential data to another agent comes along with the risk of enabling the receiver to infer information he is not entitled to learn. We consider a specific countermeasure against unwanted inferences about associations between data values whose combination of attributes are declared to be sensitive. This countermeasure fragments a relation instance into attribute-disjoint and duplicate-preserving projections such that no sensitive attribute combination is contained in any projection. Unfortunately, the intended goal of inference-proofness will not always be accomplished. Inferences might be based on combinatorial reasoning, since duplicate-preservation implies that the frequencies of value associations in visible fragments equals those in the original relation instance. In addition, the receiver might exploit entailment reasoning about functional dependencies, numerical dependencies and tuple-generating dependencies, as presumably known from the underlying database schema. We investigate possible interferences of combinatorial reasoning and entailment reasoning and identify basic conditions for a fragmentation to violate inference-proofness. Moreover, we outline a comprehensive method to effectively check the inference-proofness of a given fragmentation and we experimentally evaluate the computational efficiency of a partial prototype implementation. PubDate: 2019-08-09