OpenRaiser/Intern-Atlas huggingface dataset:
Learning Likely Invariants to Explain Why a Program Fails
Venue: arXiv cs.SE 2016
Year: 2016

Debugging is difficult. Recent studies show that automatic bug localization techniques have limited usefulness. One of the reasons is that programmers typically have to understand why the program fails before fixing it. In this work, we aim to help programmers understand a bug by automatically generating likely invariants which are violated in the failed tests. Given a program with an initial assertion and at least one test case failing the assertion, we first generate random test cases, identify potential bug locations through bug localization, and then generate program state mutation based on active learning techniques to identify a predicate "explaining" the cause of the bug. The predicate is a classifier for the passed test cases and failed test cases. Our main contribution is the application of invariant learning for bug explanation, as well as a novel approach to overcome the problem of lack of test cases in practice. We apply our method to real-world bugs and show the generated invariants are often correlated to the actual bug fixes.
Estimation of Bandlimited Grayscale Images From the Single Bit Observations of Pixels Affected by Additive Gaussian Noise
Venue: arXiv cs.CV 2016
Year: 2016

The estimation of grayscale images using their single-bit zero mean Gaussian noise-affected pixels is presented in this paper. The images are assumed to be bandlimited in the Fourier Cosine transform (FCT) domain. The images are oversampled over their Nyquist rate in the FCT domain. We propose a non-recursive approach based on first order approximation of Cumulative Distribution Function (CDF) to estimate the image from single bit pixels which itself is based on Banach's contraction theorem. The decay rate for mean squared error of estimating such images is found to be independent of the precision of the quantizer and it varies as $O(1/N)$ where $N$ is the "effective" oversampling ratio with respect to the Nyquist rate in the FCT domain.
Anomaly Detection with the Voronoi Diagram Evolutionary Algorithm
Venue: arXiv cs.AI 2016
Year: 2016

This paper presents the Voronoi diagram-based evolutionary algorithm (VorEAl). VorEAl partitions input space in abnormal/normal subsets using Voronoi diagrams. Diagrams are evolved using a multi-objective bio-inspired approach in order to conjointly optimize classification metrics while also being able to represent areas of the data space that are not present in the training dataset. As part of the paper VorEAl is experimentally validated and contrasted with similar approaches.
Finding Largest Common Substructures of Molecules in Quadratic Time
Venue: arXiv cs.DS 2016
Year: 2016

Finding the common structural features of two molecules is a fundamental task in cheminformatics. Most drugs are small molecules, which can naturally be interpreted as graphs. Hence, the task is formalized as maximum common subgraph problem. Albeit the vast majority of molecules yields outerplanar graphs this problem remains NP-hard. We consider a variation of the problem of high practical relevance, where the rings of molecules must not be broken, i.e., the block and bridge structure of the input graphs must be retained by the common subgraph. We present an algorithm for finding a maximum common connected induced subgraph of two given outerplanar graphs subject to this constraint. Our approach runs in time $\mathcal{O}(Δn^2)$ in outerplanar graphs on $n$ vertices with maximum degree $Δ$. This leads to a quadratic time complexity in molecular graphs, which have bounded degree. The experimental comparison on synthetic and real-world datasets shows that our approach is highly efficient in practice and outperforms comparable state-of-the-art algorithms.
Volumetric Light-field Encryption at the Microscopic Scale
Venue: arXiv cs.CR 2016
Year: 2016

We report a light-field based method that allows the optical encryption of three-dimensional (3D) volumetric information at the microscopic scale in a single 2D light-field image. The system consists of a microlens array and an array of random phase/amplitude masks. The method utilizes a wave optics model to account for the dominant diffraction effect at this new scale, and the system point-spread function (PSF) serves as the key for encryption and decryption. We successfully developed and demonstrated a deconvolution algorithm to retrieve spatially multiplexed discrete and continuous volumetric data from 2D light-field images. Showing that the method is practical for data transmission and storage, we obtained a faithful reconstruction of the 3D volumetric information from a digital copy of the encrypted light-field image. The method represents a new level of optical encryption, paving the way for broad industrial and biomedical applications in processing and securing 3D data at the microscopic scale.
Single- and Multi-Task Architectures for Surgical Workflow Challenge at M2CAI 2016
Venue: arXiv cs.CV 2016
Year: 2016

The surgical workflow challenge at M2CAI 2016 consists of identifying 8 surgical phases in cholecystectomy procedures. Here, we propose to use deep architectures that are based on our previous work where we presented several architectures to perform multiple recognition tasks on laparoscopic videos. In this technical report, we present the phase recognition results using two architectures: (1) a single-task architecture designed to perform solely the surgical phase recognition task and (2) a multi-task architecture designed to perform jointly phase recognition and tool presence detection. On top of these architectures we propose to use two different approaches to enforce the temporal constraints of the surgical workflow: (1) HMM-based and (2) LSTM-based pipelines. The results show that the LSTM-based approach is able to outperform the HMM-based approach and also to properly enforce the temporal constraints into the recognition process.
A Sound, Complete and Effective Second Order Game Semantics
Venue: arXiv cs.LO 2016
Year: 2016

We define a game semantics for second order classical arithmetic PA2 (with quantifiers over predicates on integers and full comprehension axiom). Our semantics is effective: moves are described by a finite amount of information and whenever there is some winning strategy for the player defending the truth of the formula, then there is some primitive recursive winning strategy. Then we show that our game semantics is sound and complete for the truth assignment for formulas of PA2. In our game model, the value of a predicate variable is some family of "generic" games. This value is "unknown" during the play, but at the end of the play it is used by a "judge of the play" to decide who is the winner.
Tool and Phase recognition using contextual CNN features
Venue: arXiv cs.CV 2016
Year: 2016

A transfer learning method for generating features suitable for surgical tools and phase recognition from the ImageNet classification features [1] is proposed here. In addition, methods are developed for generating contextual features and combining them with time series analysis for final classification using multi-class random forest. The proposed pipeline is tested over the training and testing datasets of M2CAI16 challenges: tool and phase detection. Encouraging results are obtained by leave-one-out cross validation evaluation on the training dataset.
Logarithmic Query Complexity for Approximate Nash Computation in Large Games
Venue: arXiv cs.GT 2016
Year: 2016

We investigate the problem of equilibrium computation for "large" $n$-player games. Large games have a Lipschitz-type property that no single player's utility is greatly affected by any other individual player's actions. In this paper, we mostly focus on the case where any change of strategy by a player causes other players' payoffs to change by at most $\frac{1}{n}$. We study algorithms having query access to the game's payoff function, aiming to find $ε$-Nash equilibria. We seek algorithms that obtain $ε$ as small as possible, in time polynomial in $n$. Our main result is a randomised algorithm that achieves $ε$ approaching $\frac{1}{8}$ for 2-strategy games in a {\em completely uncoupled} setting, where each player observes her own payoff to a query, and adjusts her behaviour independently of other players' payoffs/actions. $O(\log n)$ rounds/queries are required. We also show how to obtain a slight improvement over $\frac{1}{8}$, by introducing a small amount of communication between the players. Finally, we give extension of our results to large games with more than two strategies per player, and alternative largeness parameters.
Empirical Evaluation of Effort on Composing Design Models
Venue: arXiv cs.SE 2016
Year: 2016

Model composition plays a central role in many software engineering activities such as evolving models to add new features and reconciling conflicting design models developed in parallel by different development teams. As model composition is usually an error-prone and effort-consuming task, its potential benefits, such as gains in productivity can be compromised. However, there is no empirical knowledge nowadays about the effort required to compose design models. Only feedbacks of model composition evangelists are available, and they often diverge. Consequently, developers are unable to conduct any cost-effectiveness analysis as well as identify, predict, or reduce composition effort. The inability of evaluating composition effort is due to three key problems. First, the current evaluation frameworks do not consider fundamental concepts in model composition such as conflicts and inconsistencies. Second, researchers and developers do not know what factors can influence the composition effort in practice. Third, practical knowledge about how such influential factors may affect the developers' effort is severely lacking. In this context, the contributions of this thesis are threefold: (i) a quality model for supporting the evaluation of model composition effort, (ii) practical knowledge, derived from a family of quantitative and qualitative empirical studies, about model composition effort and its influential factors, and (iii) insight about how to evaluate model composition efforts and tame the side effects of such influential factors.
Broadcast Coded Modulation: Multilevel and Bit-interleaved Construction
Venue: arXiv cs.IT 2016
Year: 2016

The capacity of the AWGN broadcast channel is achieved by superposition coding, but superposition of individual coded modulations expands the modulation alphabet and distorts its configuration. Coded modulation over a broadcast channel subject to a specific channel-input modulation constraint remains an important open problem. Some progress has been made in the related area of unequal-error protection modulations which can be considered single-user broadcast transmission, but it does not approach all points on the boundary of the capacity region. This paper studies broadcast coded modulation using multilevel coding (MLC) subject to a specific channel input constellation. The conditions under which multilevel codes can achieve the constellation-constrained capacity of the AWGN broadcast channel are derived. For any given constellation, we propose a pragmatic multilevel design technique with near constellation-constrained-capacity performance where the coupling of the superposition inner and outer codes are localized to each bit-level. It is shown that this can be further relaxed to a code coupling on only one bit level, with little or no penalty under natural labeling. The rate allocation problem between the bit levels of the two users is studied and a pragmatic method is proposed, again with near-capacity performance. In further pursuit of lower complexity, a hybrid MLC-BICM is proposed, whose performance is shown to be very close to the boundary of the constellation-constrained capacity region. Simulation results show that good point-to-point LDPC codes produce excellent performance in the proposed coded modulation framework.
Recent advances in content based video copy detection
Venue: arXiv cs.CV 2016
Year: 2016

With the immense number of videos being uploaded to the video sharing sites, issue of copyright infringement arises with uploading of illicit copies or transformed versions of original video. Thus safeguarding copyright of digital media has become matter of concern. To address this concern, it is obliged to have a video copy detection system which is sufficiently robust to detect these transformed videos with ability to pinpoint location of copied segments. This paper outlines recent advancement in content based video copy detection, mainly focusing on different visual features employed by video copy detection systems. Finally we evaluate performance of existing video copy detection systems.
The Weak Convergence of TCP Bandwidth Sharing
Venue: arXiv cs.NI 2016
Year: 2016

TCP is the dominating transmission protocol in the Internet since decades. It proved its flexibility to adapt to unknown and changing network conditions. A distinguished TCP feature is the comparably fair resource sharing. Unfortunately, this abstract fairness is frequently misinterpreted as convergence towards equal sharing rates. In this paper we show in theory as well as in experiment that TCP rate convergence does not exist. Instead, the individual TCP flow rate is persistently fluctuating over a range close to one order of magnitude. The fluctuations are not short term but correlated over long intervals, so that the carried data volume converges rather slowly. The weak convergence does not negate fairness in general. Nevertheless, a particular transmission operation could deviate considerably.
Performance evaluation of explicit finite difference algorithms with varying amounts of computational and memory intensity
Venue: arXiv cs.DS 2016
Year: 2016

Future architectures designed to deliver exascale performance motivate the need for novel algorithmic changes in order to fully exploit their capabilities. In this paper, the performance of several numerical algorithms, characterised by varying degrees of memory and computational intensity, are evaluated in the context of finite difference methods for fluid dynamics problems. It is shown that, by storing some of the evaluated derivatives as single thread- or process-local variables in memory, or recomputing the derivatives on-the-fly, a speed-up of ~2 can be obtained compared to traditional algorithms that store all derivatives in global arrays.
Nested Distributed Model Predictive Control
Venue: arXiv cs.SY 2016
Year: 2016

We propose a distributed model predictive control approach for linear time-invariant systems coupled via dynamics. The proposed approach uses the tube MPC concept for robustness to handle the disturbances induced by mutual interactions between subsystems; however, the main novelty here is to replace the conventional linear disturbance rejection controller with a second MPC controller, as is done in tube-based nonlinear MPC. In the distributed setting, this has the advantages that the disturbance rejection controller is able to consider the plans of neighbours, and the reliance on explicit robust invariant sets is removed.
Sort well with energy-constrained comparisons
Venue: arXiv cs.DS 2016
Year: 2016

We study very simple sorting algorithms based on a probabilistic comparator model. In our model, errors in comparing two elements are due to (1) the energy or effort put in the comparison and (2) the difference between the compared elements. Such algorithms keep comparing pairs of randomly chosen elements, and they correspond to Markovian processes. The study of these Markov chains reveals an interesting phenomenon. Namely, in several cases, the algorithm which repeatedly compares only adjacent elements is better than the one making arbitrary comparisons: on the long-run, the former algorithm produces sequences that are "better sorted". The analysis of the underlying Markov chain poses new interesting questions as the latter algorithm yields a non-reversible chain and therefore its stationary distribution seems difficult to calculate explicitly.
An Application of Group Theory in Confidential Network Communications
Venue: arXiv cs.IT 2016
Year: 2016

A new proposal for group key exchange is introduced which proves to be both efficient and secure and compares favorably with state of the art protocols.
Discriminative Gaifman Models
Venue: arXiv cs.LG 2016
Year: 2016

We present discriminative Gaifman models, a novel family of relational machine learning models. Gaifman models learn feature representations bottom up from representations of locally connected and bounded-size regions of knowledge bases (KBs). Considering local and bounded-size neighborhoods of knowledge bases renders logical inference and learning tractable, mitigates the problem of overfitting, and facilitates weight sharing. Gaifman models sample neighborhoods of knowledge bases so as to make the learned relational models more robust to missing objects and relations which is a common situation in open-world KBs. We present the core ideas of Gaifman models and apply them to large-scale relational learning problems. We also discuss the ways in which Gaifman models relate to some existing relational machine learning approaches.
Programming Heterogeneous Systems from an Image Processing DSL
Venue: arXiv cs.SE 2016
Year: 2016

Specialized image processing accelerators are necessary to deliver the performance and energy efficiency required by important applications in computer vision, computational photography, and augmented reality. But creating, "programming,"and integrating this hardware into a hardware/software system is difficult. We address this problem by extending the image processing language, Halide, so users can specify which portions of their applications should become hardware accelerators, and then we provide a compiler that uses this code to automatically create the accelerator along with the "glue" code needed for the user's application to access this hardware. Starting with Halide not only provides a very high-level functional description of the hardware, but also allows our compiler to generate the complete software program including the sequential part of the workload, which accesses the hardware for acceleration. Our system also provides high-level semantics to explore different mappings of applications to a heterogeneous system, with the added flexibility of being able to map at various throughput rates. We demonstrate our approach by mapping applications to a Xilinx Zynq system. Using its FPGA with two low-power ARM cores, our design achieves up to 6x higher performance and 8x lower energy compared to the quad-core ARM CPU on an NVIDIA Tegra K1, and 3.5x higher performance with 12x lower energy compared to the K1's 192-core GPU.
On the Power of Weaker Pairwise Interaction: Fault-Tolerant Simulation of Population Protocols
Venue: arXiv cs.DC 2016
Year: 2016

In this paper we investigate the computational power of Population Protocols (PP) under some unreliable and/or weaker interaction models. More precisely, we focus on two features related to the power of interactions: omission failures and one-way communications. An omission failure, a notion that this paper introduces for the first time in the context of PP, is the loss by one or both parties of the information transmitted in an interaction. The failure may or may not be detected by either party. On the other hand, in one-way models, communication happens only in one direction: only one of the two agents can change its state depending on both agents' states, and the other agent may or may not be aware of the interaction. These notions can be combined, obtaining one-way protocols with (possibly detectable) omission failures. A general question is what additional power is necessary and sufficient to completely overcome the weakness of one-way protocols and enable them to simulate two-way protocols, with and without omission failures. As a basic feature, a simulator needs to implement an atomic communication of states between two agents; this task is further complicated by the anonymity of the agents, their lack of knowledge of the system, and the limited amount of memory that they may have. We provide the first answers to these questions by presenting and analyzing several simulators, i.e., wrapper protocols converting any protocol for the standard two-way model into one running on a weaker one.
From Simplicity to Complexity Based on Consensus: A Case Study
Venue: arXiv cs.SY 2016
Year: 2016

Distributed consensus has been intensively studied in recent years as a means to mitigate state differences among dynamic nodes on a graph. It has been successfully employed in various applications, e.g., formation control of multi-robots, load balancing, clock synchronization. However, almost all existing applications cast an impression of consensus as a simple process to iteratively reach agreement, without any clue on possibility to generate advanced complexity, say shortest path planning, which has been proved to be NP-hard. Counter-intuitively, we show for the first time that the complexity of shortest path planning can emerge from a perturbed version of min-consensus protocol, which as a case study may shed lights to researchers in the field of distributed control to re-think the nature of complexity and the distance between control and intelligence. Besides, we rigorously prove the convergence of graph dynamics and its equivalence to shortest path solutions. An illustrative simulation on a small scale graph is provided to show the convergence of the biased min-consensus dynamics to shortest path solution over the graph. To demonstrate the scalability to large scale problems, a graph with 43826 nodes, which corresponds to a map of a maze in 2D, is considered in the simulation study. Apart from possible applications in robot path planning, the result is further extended to robot complete coverage, showing its potential in real practice such as cleaning robots.
Machine learning methods for accurate delineation of tumors in PET images
Venue: arXiv cs.CV 2016
Year: 2016

In oncology, Positron Emission Tomography imaging is widely used in diagnostics of cancer metastases, in monitoring of progress in course of the cancer treatment, and in planning radiotherapeutic interventions. Accurate and reproducible delineation of the tumor in the Positron Emission Tomography scans remains a difficult task, despite being crucial for delivering appropriate radiation dose, minimizing adverse side-effects of the therapy, and reliable evaluation of treatment. In this piece of research we attempt to solve the problem of automated delineation of the tumor using 3d implementations of the spatial distance weighted fuzzy c-means, the deep convolutional neural network and a dictionary model. The methods, in diverse ways, combine intensity and spatial information.
Efficient Entity Resolution on Heterogeneous Records
Venue: arXiv cs.DB 2016
Year: 2016

Entity resolution (ER) is the problem of identifying and merging records that refer to the same real-world entity. In many scenarios, raw records are stored under heterogeneous environment. Specifically, the schemas of records may differ from each other. To leverage such records better, most existing work assume that schema matching and data exchange have been done to convert records under different schemas to those under a predefined schema. However, we observe that schema matching would lose information in some cases, which could be useful or even crucial to ER. To leverage sufficient information from heterogeneous sources, in this paper, we address several challenges of ER on heterogeneous records and show that none of existing similarity metrics or their transformations could be applied to find similar records under heterogeneous settings. Motivated by this, we design the similarity function and propose a novel framework to iteratively find records which refer to the same entity. Regarding efficiency, we build an index to generate candidates and accelerate similarity computation. Evaluations on real-world datasets show the effectiveness and efficiency of our methods.