OpenRaiser/Intern-Atlas huggingface dataset:
A Comprehensive Approach for Learning-based Fully-Automated Inter-slice Motion Correction for Short-Axis Cine Cardiac MR Image Stacks
Venue: arXiv cs.CV 2018
Year: 2018

In the clinical routine, short axis (SA) cine cardiac MR (CMR) image stacks are acquired during multiple subsequent breath-holds. If the patient cannot consistently hold the breath at the same position, the acquired image stack will be affected by inter-slice respiratory motion and will not correctly represent the cardiac volume, introducing potential errors in the following analyses and visualisations. We propose an approach to automatically correct inter-slice respiratory motion in SA CMR image stacks. Our approach makes use of probabilistic segmentation maps (PSMs) of the left ventricular (LV) cavity generated with decision forests. PSMs are generated for each slice of the SA stack and rigidly registered in-plane to a target PSM. If long axis (LA) images are available, PSMs are generated for them and combined to create the target PSM; if not, the target PSM is produced from the same stack using a 3D model trained from motion-free stacks. The proposed approach was tested on a dataset of SA stacks acquired from 24 healthy subjects (for which anatomical 3D cardiac images were also available as reference) and compared to two techniques which use LA intensity images and LA segmentations as targets, respectively. The results show the accuracy and robustness of the proposed approach in motion compensation.
Randen - fast backtracking-resistant random generator with AES+Feistel+Reverie
Venue: arXiv cs.CR 2018
Year: 2018

Algorithms that rely on a pseudorandom number generator often lose their performance guarantees when adversaries can predict the behavior of the generator. To protect non-cryptographic applications against such attacks, we propose 'strong' pseudorandom generators characterized by two properties: computationally indistinguishable from random and backtracking-resistant. Some existing cryptographically secure generators also meet these criteria, but they are too slow to be accepted for general-purpose use. We introduce a new open-sourced generator called 'Randen' and show that it is 'strong' in addition to outperforming Mersenne Twister, PCG, ChaCha8, ISAAC and Philox in real-world benchmarks. This is made possible by hardware acceleration. Randen is an instantiation of Reverie, a recently published robust sponge-like random generator, with a new permutation built from an improved generalized Feistel structure with 16 branches. We provide new bounds on active s-boxes for up to 24 rounds of this construction, made possible by a memory-efficient search algorithm. Replacing existing generators with Randen can protect randomized algorithms such as reservoir sampling from attack. The permutation may also be useful for wide-block ciphers and hashing functions.
DER Allocation and Line Repair Scheduling for Storm-induced Failures in Distribution Networks
Venue: arXiv cs.CE 2018
Year: 2018

Electricity distribution networks (DNs) in many regions are increasingly subjected to disruptions caused by tropical storms. Distributed Energy Resources (DERs) can act as temporary supply sources to sustain "microgrids" resulting from disruptions. In this paper, we investigate the problem of suitable DER allocation to facilitate more efficient repair operations and faster recovery. First, we estimate the failure probabilities of DN components (lines) using a stochastic model of line failures which parametrically depends on the location-specific storm wind field. Next, we formulate a two-stage stochastic mixed integer program, which models the distribution utility's decision to allocate DERs in the DN (pre-storm stage); and accounts for multi-period decisions on optimal dispatch and line repair scheduling (post-storm stage). A key feature of this formulation is that it jointly optimizes electricity dispatch within the individual microgrids and the line repair schedules to minimize the sum of the cost of DER allocation and cost due to lost load. To illustrate our approach, we use the sample average approximation method to solve our problem for a small-size DN under different storm intensities and DER/crew constraints.
Correcting the bias in least squares regression with volume-rescaled sampling
Venue: arXiv cs.LG 2018
Year: 2018

Consider linear regression where the examples are generated by an unknown distribution on $R^d\times R$. Without any assumptions on the noise, the linear least squares solution for any i.i.d. sample will typically be biased w.r.t. the least squares optimum over the entire distribution. However, we show that if an i.i.d. sample of any size k is augmented by a certain small additional sample, then the solution of the combined sample becomes unbiased. We show this when the additional sample consists of d points drawn jointly according to the input distribution that is rescaled by the squared volume spanned by the points. Furthermore, we propose algorithms to sample from this volume-rescaled distribution when the data distribution is only known through an i.i.d sample.
Prototyping Formal System Models with Active Objects
Venue: arXiv cs.DC 2018
Year: 2018

We propose active object languages as a development tool for formal system models of distributed systems. Additionally to a formalization based on a term rewriting system, we use established Software Engineering concepts, including software product lines and object orientation that come with extensive tool support. We illustrate our modeling approach by prototyping a weak memory model. The resulting executable model is modular and has clear interfaces between communicating participants through object-oriented modeling. Relaxations of the basic memory model are expressed as self-contained variants of a software product line. As a modeling language we use the formal active object language ABS which comes with an extensive tool set. This permits rapid formalization of core ideas, early validity checks in terms of formal invariant proofs, and debugging support by executing test runs. Hence, our approach supports the prototyping of formal system models with early feedback.
Unfolding of Finite Concurrent Automata
Venue: arXiv cs.FL 2018
Year: 2018

We consider recognizable trace rewriting systems with level-regular contexts (RTL). A trace language is level-regular if the set of Foata normal forms of its elements is regular. We prove that the rewriting graph of a RTL is word-automatic. Thus its first-order theory is decidable. Then, we prove that the concurrent unfolding of a finite concurrent automaton with the reachability relation is a RTL graph. It follows that the first-order theory with the reachability predicate (FO[Reach] theory) of such an unfolding is decidable. It is known that this property holds also for the ground term rewriting graphs. We provide examples of finite concurrent automata of which the concurrent unfoldings fail to be ground term rewriting graphs. The infinite grid tree (for each vertex of an infinite grid, there is an edge from this vertex to the origin of a copy of the infinite grid) is such an unfolding. We prove that the infinite grid tree is not a ground term rewriting graph. We have thus obtained a new class of graphs for with a decidable FO[Reach] theory.
Hands-Free One-Time and Continuous Authentication Using Glass Wearable Devices
Venue: arXiv cs.CR 2018
Year: 2018

Users with limited use of their hands, such as people suffering from disabilities of the arm, shoulder, and hand (DASH), face challenges when authenticating with computer terminals, specially with publicly accessible terminals such as ATMs. A new glass wearable device was recently introduced by Google and it was immediately welcomed by groups of users, such as the ones described above, as Google Glass allows them to perform actions, like taking a photo, using only verbal commands. This paper investigates whether glass wearable devices can be used to authenticate users, both to grant access (one-time) and to maintain access (continuous), in similar hands-free fashion. We do so by designing and implementing Gauth, a system that enables users to authenticate with a service simply by issuing a voice command, while facing the computer terminal they are going to use to access the service. To achieve this goal, we create a physical communication channel from the terminal to the device using machine readable visual codes, like QR codes, and utilize the device's network adapter to communicate directly with a service. More importantly, we continuously authenticate the user accessing the terminal, exploiting the fact that a user operating a terminal is most likely facing it most of the time. We periodically issue authentication challenges, which are displayed as a QR code on the terminal, that cause the glass device to re-authenticate the user with an appropriate response. We evaluate our system to determine the technical limits of our approach.
Local Stability and Performance of Simple Gradient Penalty mu-Wasserstein GAN
Venue: arXiv cs.LG 2018
Year: 2018

Wasserstein GAN(WGAN) is a model that minimizes the Wasserstein distance between a data distribution and sample distribution. Recent studies have proposed stabilizing the training process for the WGAN and implementing the Lipschitz constraint. In this study, we prove the local stability of optimizing the simple gradient penalty $μ$-WGAN(SGP $μ$-WGAN) under suitable assumptions regarding the equilibrium and penalty measure $μ$. The measure valued differentiation concept is employed to deal with the derivative of the penalty terms, which is helpful for handling abstract singular measures with lower dimensional support. Based on this analysis, we claim that penalizing the data manifold or sample manifold is the key to regularizing the original WGAN with a gradient penalty. Experimental results obtained with unintuitive penalty measures that satisfy our assumptions are also provided to support our theoretical results.
Randomized Consensus based Distributed Kalman Filtering over Wireless Sensor Networks
Venue: arXiv cs.SY 2018
Year: 2018

This paper is concerned with developing a novel distributed Kalman filtering algorithm over wireless sensor networks based on randomized consensus strategy. Compared with the centralized algorithm, distributed filtering techniques require less computation per sensor and lead to more robust estimation since they simply use the information from the neighboring nodes in the network. However, poor local sensor estimation caused by limited observability and network topology changes which interfere the global consensus are challenging issues. Motivated by this observation, we propose a novel randomized gossip-based distributed Kalman filtering algorithm. Information exchange and computation in the proposed algorithm can be carried out in an arbitrarily connected network of nodes. In addition, the computational burden can be distributed for a sensor which communicates with a stochastically selected neighbor at each clock step under schemes of gossip algorithm. In this case, the error covariance matrix changes stochastically at every clock step, thus the convergence is considered in a probabilistic sense. We provide the mean square convergence analysis of the proposed algorithm. Under a sufficient condition, we show that the proposed algorithm is quite appealing as it achieves better mean square error performance theoretically than the noncooperative decentralized Kalman filtering algorithm. Besides, considering the limited computation, communication, and energy resources in the wireless sensor networks, we propose an optimization problem which minimizes the average expected state estimation error based on the proposed algorithm. To solve the proposed problem efficiently, we transform it into a convex optimization problem. And a sub-optimal solution is attained. Examples and simulations are provided to illustrate the theoretical results.
Automated Fix Detection Given Flaky Tests
Venue: arXiv cs.SE 2018
Year: 2018

Research Proposal in Automated Fix Detection
Computing the Nucleolus of Weighted Voting Games in Pseudo-polynomial Time
Venue: arXiv cs.GT 2018
Year: 2018

We provide an algorithm for computing the nucleolus for an instance of a weighted voting game in pseudo-polynomial time. This resolves an open question posed by Elkind. et.al. 2007.
Local Interpretable Model-agnostic Explanations of Bayesian Predictive Models via Kullback-Leibler Projections
Venue: arXiv cs.LG 2018
Year: 2018

We introduce a method, KL-LIME, for explaining predictions of Bayesian predictive models by projecting the information in the predictive distribution locally to a simpler, interpretable explanation model. The proposed approach combines the recent Local Interpretable Model-agnostic Explanations (LIME) method with ideas from Bayesian projection predictive variable selection methods. The information theoretic basis helps in navigating the trade-off between explanation fidelity and complexity. We demonstrate the method in explaining MNIST digit classifications made by a Bayesian deep convolutional neural network.
Hows and Whys of Artificial Intelligence for Public Sector Decisions: Explanation and Evaluation
Venue: arXiv cs.CY 2018
Year: 2018

Evaluation has always been a key challenge in the development of artificial intelligence (AI) based software, due to the technical complexity of the software artifact and, often, its embedding in complex sociotechnical processes. Recent advances in machine learning (ML) enabled by deep neural networks has exacerbated the challenge of evaluating such software due to the opaque nature of these ML-based artifacts. A key related issue is the (in)ability of such systems to generate useful explanations of their outputs, and we argue that the explanation and evaluation problems are closely linked. The paper models the elements of a ML-based AI system in the context of public sector decision (PSD) applications involving both artificial and human intelligence, and maps these elements against issues in both evaluation and explanation, showing how the two are related. We consider a number of common PSD application patterns in the light of our model, and identify a set of key issues connected to explanation and evaluation in each case. Finally, we propose multiple strategies to promote wider adoption of AI/ML technologies in PSD, where each is distinguished by a focus on different elements of our model, allowing PSD policy makers to adopt an approach that best fits their context and concerns.
Optimizing groups of colluding strong attackers in mobile urban communication networks with evolutionary algorithms
Venue: arXiv cs.NE 2018
Year: 2018

In novel forms of the Social Internet of Things, any mobile user within communication range may help routing messages for another user in the network. The resulting message delivery rate depends both on the users' mobility patterns and the message load in the network. This new type of configuration, however, poses new challenges to security, amongst them, assessing the effect that a group of colluding malicious participants can have on the global message delivery rate in such a network is far from trivial. In this work, after modeling such a question as an optimization problem, we are able to find quite interesting results by coupling a network simulator with an evolutionary algorithm. The chosen algorithm is specifically designed to solve problems whose solutions can be decomposed into parts sharing the same structure. We demonstrate the effectiveness of the proposed approach on two medium-sized Delay-Tolerant Networks, realistically simulated in the urban contexts of two cities with very different route topology: Venice and San Francisco. In all experiments, our methodology produces attack patterns that greatly lower network performance with respect to previous studies on the subject, as the evolutionary core is able to exploit the specific weaknesses of each target configuration.
Human Indignity: From Legal AI Personhood to Selfish Memes
Venue: arXiv cs.GL 2018
Year: 2018

It is possible to rely on current corporate law to grant legal personhood to Artificially Intelligent (AI) agents. In this paper, after introducing pathways to AI personhood, we analyze consequences of such AI empowerment on human dignity, human safety and AI rights. We emphasize possibility of creating selfish memes and legal system hacking in the context of artificial entities. Finally, we consider some potential solutions for addressing described problems.
Improved Inapproximability of Rainbow Coloring
Venue: arXiv cs.CC 2018
Year: 2018

A rainbow $q$-coloring of a $k$-uniform hypergraph is a $q$-coloring of the vertex set such that every hyperedge contains all $q$ colors. We prove that given a rainbow $(k - 2\lfloor \sqrt{k}\rfloor)$-colorable $k$-uniform hypergraph, it is NP-hard to find a normal $2$-coloring. Previously, this was only known for rainbow $\lfloor k/2 \rfloor$-colorable hypergraphs (Guruswami and Lee, SODA 2015). We also study a generalization which we call rainbow $(q, p)$-coloring, defined as a coloring using $q$ colors such that every hyperedge contains at least $p$ colors. We prove that given a rainbow $(k - \lfloor \sqrt{kc} \rfloor, k- \lfloor3\sqrt{kc} \rfloor)$-colorable $k$ uniform hypergraph, it is NP-hard to find a normal $c$-coloring for any $c = o(k)$. The proof of our second result relies on two combinatorial theorems. One of the theorems was proved by Sarkaria (J. Comb. Theory. 1990) using topological methods and the other theorem we prove using a generalized Borsuk-Ulam theorem.
Fault-Tolerant Consensus with an Abstract MAC Layer
Venue: arXiv cs.DC 2018
Year: 2018

In this paper, we study fault-tolerant distributed consensus in wireless systems. In more detail, we produce two new randomized algorithms that solve this problem in the abstract MAC layer model, which captures the basic interface and communication guarantees provided by most wireless MAC layers. Our algorithms work for any number of failures, require no advance knowledge of the network participants or network size, and guarantee termination with high probability after a number of broadcasts that are polynomial in the network size. Our first algorithm satisfies the standard agreement property, while our second trades a faster termination guarantee in exchange for a looser agreement property in which most nodes agree on the same value. These are the first known fault-tolerant consensus algorithms for this model. In addition to our main upper bound results, we explore the gap between the abstract MAC layer and the standard asynchronous message passing model by proving fault-tolerant consensus is impossible in the latter in the absence of information regarding the network participants, even if we assume no faults, allow randomized solutions, and provide the algorithm a constant-factor approximation of the network size.
A New Method for the Semantic Integration of Multiple OWL Ontologies using Alignments
Venue: arXiv cs.AI 2018
Year: 2018

This work is done as part of a master's thesis project. The goal is to integrate two or more ontologies (of the same or close domains) in a new consistent and coherent OWL ontology to insure semantic interoperability between them. To do this, we have chosen to create a bridge ontology that includes all source ontologies and their bridging axioms in a customized way. In addition, we introduced a new criterion for obtaining an ontology of better quality (having the minimum of semantic/logical conflicts). We have also proposed new terminology and definitions that clarify the unclear and misplaced "integration" and "merging" notions that are randomly used in state-of-the-art works. Finally, we tested and evaluated our OIA2R tool using ontologies and reference alignments of the OAEI campaign. It turned out that it is generic, efficient and powerful enough.
Computer Security Risks of Distant Relative Matching in Consumer Genetic Databases
Venue: arXiv cs.CR 2018
Year: 2018

Consumer genetic testing has become immensely popular in recent years and has lead to the creation of large scale genetic databases containing millions of dense autosomal genotype profiles. One of the most used features offered by genetic databases is the ability to find distant relatives using a technique called relative matching (or DNA matching). Recently, novel uses of relative matching were discovered that combined matching results with genealogical information to solve criminal cold cases. New estimates suggest that relative matching, combined with simple demographic information, could be used to re-identify a significant percentage of US Caucasian individuals. In this work we attempt to systematize computer security and privacy risks from relative matching and describe new security problems that can occur if an attacker uploads manipulated or forged genetic profiles. For example, forged profiles can be used by criminals to misdirect investigations, con-artists to defraud victims, or political operatives to blackmail opponents. We discuss solutions to mitigate these threats, including existing proposals to use digital signatures, and encourage the consumer genetics community to consider the broader security implications of relative matching now that it is becoming so prominent.
Memento: Making Sliding Windows Efficient for Heavy Hitters
Venue: arXiv cs.NI 2018
Year: 2018

Cloud operators require real-time identification of Heavy Hitters (HH) and Hierarchical Heavy Hitters (HHH) for applications such as load balancing, traffic engineering, and attack mitigation. However, existing techniques are slow in detecting new heavy hitters. In this paper, we make the case for identifying heavy hitters through \textit{sliding windows}. Sliding windows detect heavy hitters quicker and more accurately than current methods, but to date had no practical algorithms. Accordingly, we introduce, design and analyze the \textit{Memento} family of sliding window algorithms for the HH and HHH problems in the single-device and network-wide settings. Using extensive evaluations, we show that our single-device solutions attain similar accuracy and are by up to $273\times$ faster than existing window-based techniques. Furthermore, we exemplify our network-wide HHH detection capabilities on a realistic testbed. To that end, we implemented Memento as an open-source extension to the popular HAProxy cloud load-balancer. In our evaluations, using an HTTP flood by 50 subnets, our network-wide approach detected the new subnets faster, and reduced the number of undetected flood requests by up to $37\times$ compared to the alternatives.
Sifaka: Text Mining Above a Search API
Venue: arXiv cs.IR 2018
Year: 2018

Text mining and analytics software has become popular, but little attention has been paid to the software architectures of such systems. Often they are built from scratch using special-purpose software and data structures, which increases their cost and complexity. This demo paper describes Sifaka, a new open-source text mining application constructed above a standard search engine index using existing application programmer interface (API) calls. Indexing integrates popular annotation software libraries to augment the full-text index with noun phrase and named-entities; n-grams are also provided. Sifaka enables a person to quickly explore and analyze large text collections using search, frequency analysis, and co-occurrence analysis; and import existing document labels or interactively construct document sets that are positive or negative examples of new concepts, perform feature selection, and export feature vectors compatible with popular machine learning software. Sifaka demonstrates that search engines are good platforms for text mining applications while also making common IR text mining capabilities accessible to researchers in disciplines where programming skills are less common.