OpenRaiser/Intern-Atlas huggingface dataset:
Evaluation of Protein-protein Interaction Predictors with Noisy Partially Labeled Data Sets
Venue: arXiv cs.AI 2015
Year: 2015

Protein-protein interaction (PPI) prediction is an important problem in machine learning and computational biology. However, there is no data set for training or evaluation purposes, where all the instances are accurately labeled. Instead, what is available are instances of positive class (with possibly noisy labels) and no instances of negative class. The non-availability of negative class data is typically handled with the observation that randomly chosen protein-pairs have a nearly 100% chance of being negative class, as only 1 in 1,500 protein pairs expected is expected to be an interacting pair. In this paper, we focused on the problem that non-availability of accurately labeled testing data sets in the domain of protein-protein interaction (PPI) prediction may lead to biased evaluation results. We first showed that not acknowledging the inherent skew in the interactome (i.e. rare occurrence of positive instances) leads to an over-estimated accuracy of the predictor. Then we show that, with the belief that positive interactions are a rare category, sampling random pairs of proteins excluding known interacting proteins set as the negative testing data set could lead to an under-estimated evaluation result. We formalized those two problems to validate the above claim, and based on the formalization, we proposed a balancing method to cancel out the over-estimation with under-estimation. Finally, our experiments validated the theoretical aspects and showed that this balancing evaluation could evaluate the exact performance without availability of golden standard data sets.
"Oddball SGD": Novelty Driven Stochastic Gradient Descent for Training Deep Neural Networks
Venue: arXiv cs.LG 2015
Year: 2015

Stochastic Gradient Descent (SGD) is arguably the most popular of the machine learning methods applied to training deep neural networks (DNN) today. It has recently been demonstrated that SGD can be statistically biased so that certain elements of the training set are learned more rapidly than others. In this article, we place SGD into a feedback loop whereby the probability of selection is proportional to error magnitude. This provides a novelty-driven oddball SGD process that learns more rapidly than traditional SGD by prioritising those elements of the training set with the largest novelty (error). In our DNN example, oddball SGD trains some 50x faster than regular SGD.
A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
Venue: arXiv cs.DS 2015
Year: 2015

We present a dynamic algorithm for the recognition of proper circular-arc (PCA) graphs, that supports the insertion and removal of vertices (together with its incident edges). The main feature of the algorithm is that it outputs a minimally non-PCA induced subgraph when the insertion of a vertex fails. Each operation cost $O(\log n + d)$ time, where $n$ is the number vertices and $d$ is the degree of the modified vertex. When removals are disallowed, each insertion is processed in $O(d)$ time. The algorithm also provides two constant-time operations to query if the dynamic graph is proper Helly (PHCA) or proper interval (PIG). When the dynamic graph is not PHCA (resp. PIG), a minimally non-PHCA (resp. non-PIG) induced subgraph is obtained.
Using Bayesian Optimization to Guide Probing of a Flexible Environment for Simultaneous Registration and Stiffness Mapping
Venue: arXiv cs.RO 2015
Year: 2015

One of the goals of computer-aided surgery is to match intraoperative data to preoperative images of the anatomy and add complementary information that can facilitate the task of surgical navigation. In this context, mechanical palpation can reveal critical anatomical features such as arteries and cancerous lumps which are stiffer that the surrounding tissue. This work uses position and force measurements obtained during mechanical palpation for registration and stiffness mapping. Prior approaches, including our own, exhaustively palpated the entire organ to achieve this goal. To overcome the costly palpation of the entire organ, a Bayesian optimization framework is introduced to guide the end effector to palpate stiff regions while simultaneously updating the registration of the end effector to an a priori geometric model of the organ, hence enabling the fusion of ntraoperative data into the a priori model obtained through imaging. This new framework uses Gaussian processes to model the stiffness distribution and Bayesian optimization to direct where to sample next for maximum information gain. The proposed method was evaluated with experimental data obtained using a Cartesian robot interacting with a silicone organ model and an ex vivo porcine liver.
Fast and Efficient Sparse 2D Discrete Fourier Transform using Sparse-Graph Codes
Venue: arXiv cs.IT 2015
Year: 2015

We present a novel algorithm, named the 2D-FFAST, to compute a sparse 2D-Discrete Fourier Transform (2D-DFT) featuring both low sample complexity and low computational complexity. The proposed algorithm is based on mixed concepts from signal processing (sub-sampling and aliasing), coding theory (sparse-graph codes) and number theory (Chinese-remainder-theorem) and generalizes the 1D-FFAST 2 algorithm recently proposed by Pawar and Ramchandran [1] to the 2D setting. Concretely, our proposed 2D-FFAST algorithm computes a k-sparse 2D-DFT, with a uniformly random support, of size N = Nx x Ny using O(k) noiseless spatial-domain measurements in O(k log k) computational time. Our results are attractive when the sparsity is sub-linear with respect to the signal dimension, that is, when k -> infinity and k/N -> 0. For the case when the spatial-domain measurements are corrupted by additive noise, our 2D-FFAST framework extends to a noise-robust version in sub-linear time of O(k log4 N ) using O(k log3 N ) measurements. Simulation results, on synthetic images as well as real-world magnetic resonance images, are provided in Section VII and demonstrate the empirical performance of the proposed 2D-FFAST algorithm.
Group-theoretical vector space model
Venue: arXiv cs.DM 2015
Year: 2015

This paper presents a group-theoretical vector space model (VSM) that extends the VSM with a group action on a vector space of the VSM. We use group and its representation theory to represent a dynamic transformation of information objects, in which each information object is represented by a vector in a vector space of the VSM. Several groups and their matrix representations are employed for representing different kinds of dynamic transformations of information objects used in the VSM. We provide concrete examples of how a dynamic transformation of information objects is performed and discuss algebraic properties involving certain dynamic transformations of information objects used in the VSM.
Denoising without access to clean data using a partitioned autoencoder
Venue: arXiv cs.NE 2015
Year: 2015

Training a denoising autoencoder neural network requires access to truly clean data, a requirement which is often impractical. To remedy this, we introduce a method to train an autoencoder using only noisy data, having examples with and without the signal class of interest. The autoencoder learns a partitioned representation of signal and noise, learning to reconstruct each separately. We illustrate the method by denoising birdsong audio (available abundantly in uncontrolled noisy datasets) using a convolutional autoencoder.
A Parallel Framework for Parametric Maximum Flow Problems in Image Segmentation
Venue: arXiv cs.CV 2015
Year: 2015

This paper presents a framework that supports the implementation of parallel solutions for the widespread parametric maximum flow computational routines used in image segmentation algorithms. The framework is based on supergraphs, a special construction combining several image graphs into a larger one, and works on various architectures (multi-core or GPU), either locally or remotely in a cluster of computing nodes. The framework can also be used for performance evaluation of parallel implementations of maximum flow algorithms. We present the case study of a state-of-the-art image segmentation algorithm based on graph cuts, Constrained Parametric Min-Cut (CPMC), that uses the parallel framework to solve parametric maximum flow problems, based on a GPU implementation of the well-known push-relabel algorithm. Our results indicate that real-time implementations based on the proposed techniques are possible.
Image Retrieval Based on LBP Pyramidal Multiresolution using Reversible Watermarking
Venue: arXiv cs.CV 2015
Year: 2015

In the medical field, images are increasingly used to facilitate diagnosis of diseases. These images are stored in multimedia databases accompanied by doctor s prescriptions and other information related to patients.Search for medical images has become for clinical applications an essential tool to bring effective aid in diagnosis. Content Based Image Retrieval (CBIR) is one of the possible solutions to effectively manage these databases. Our contribution is to define a relevant descriptor to retrieve images based on multiresolution analysis of texture using Local Binary Pattern LBP. This descriptor once calculated and information s relating to the patient; will be placed in the image using the technique of reversible watermarking. Thereby, the image, descriptor of its contents, the BFILE locator and patientrelated information become a single entity, so even the administrator cannot have access to the patient private data.
Proving Skipping Refinement with ACL2s
Venue: arXiv cs.LO 2015
Year: 2015

We describe three case studies illustrating the use of ACL2s to prove the correctness of optimized reactive systems using skipping refinement. Reasoning about reactive systems using refinement involves defining an abstract, high-level specification system and a concrete, low-level system. Next, one shows that the behaviors of the implementation system are allowed by the specification system. Skipping refinement allows us to reason about implementation systems that can "skip" specification states due to optimizations that allow the implementation system to take several specification steps at once. Skipping refinement also allows implementation systems to, i.e., to take several steps before completing a specification step. We show how ACL2s can be used to prove skipping refinement theorems by modeling and proving the correctness of three systems: a JVM-inspired stack machine, a simple memory controller, and a scalar to vector compiler transformation.
The Utility of Clustering in Prediction Tasks
Venue: arXiv cs.LG 2015
Year: 2015

We explore the utility of clustering in reducing error in various prediction tasks. Previous work has hinted at the improvement in prediction accuracy attributed to clustering algorithms if used to pre-process the data. In this work we more deeply investigate the direct utility of using clustering to improve prediction accuracy and provide explanations for why this may be so. We look at a number of datasets, run k-means at different scales and for each scale we train predictors. This produces k sets of predictions. These predictions are then combined by a naïve ensemble. We observed that this use of a predictor in conjunction with clustering improved the prediction accuracy in most datasets. We believe this indicates the predictive utility of exploiting structure in the data and the data compression handed over by clustering. We also found that using this method improves upon the prediction of even a Random Forests predictor which suggests this method is providing a novel, and useful source of variance in the prediction process.
Level Two of the Quantifier Alternation Hierarchy over Infinite Words
Venue: arXiv cs.FL 2015
Year: 2015

The study of various decision problems for logic fragments has a long history in computer science. This paper is on the membership problem for a fragment of first-order logic over infinite words; the membership problem asks for a given language whether it is definable in some fixed fragment. The alphabetic topology was introduced as part of an effective characterization of the fragment $Σ_2$ over infinite words. Here, $Σ_2$ consists of the first-order formulas with two blocks of quantifiers, starting with an existential quantifier. Its Boolean closure is $\mathbb{B}Σ_2$. Our first main result is an effective characterization of the Boolean closure of the alphabetic topology, that is, given an $ω$-regular language $L$, it is decidable whether $L$ is a Boolean combination of open sets in the alphabetic topology. This is then used for transferring Place and Zeitoun's recent decidability result for $\mathbb{B}Σ_2$ from finite to infinite words.
Algebraic Solution for Beamforming in Two-Way Relay Systems with Analog Network Coding
Venue: arXiv cs.IT 2015
Year: 2015

We reduce the problem of optimal beamforming for two-way relay (TWR) systems with perfect channel state infomation (CSI) that use analog network coding (ANC) to a pair of algebraic equations in two variables that can be solved inexpensively using numerical methods. The solution has greatly reduced complexity compared to previous exact solutions via semidefinite programming (SDP). Together with the linearized robust solution described in (Aziz and Thron, 2014), it provides a high-performance, low-complexity robust beamforming solution for 2-way relays.
Sports highlights generation based on acoustic events detection: A rugby case study
Venue: arXiv cs.SD 2015
Year: 2015

We approach the challenging problem of generating highlights from sports broadcasts utilizing audio information only. A language-independent, multi-stage classification approach is employed for detection of key acoustic events which then act as a platform for summarization of highlight scenes. Objective results and human experience indicate that our system is highly efficient.
Efficient Reassembling of Graphs, Part 1: The Linear Case
Venue: arXiv cs.DM 2015
Year: 2015

The reassembling of a simple connected graph G = (V,E) is an abstraction of a problem arising in earlier studies of network analysis. Its simplest formulation is in two steps: (1) We cut every edge of G into two halves, thus obtaining a collection of n=|V| one-vertex components. (2) We splice the two halves of every edge together, not of all the edges at once, but in some ordering Θof the edges that minimizes two measures that depend on the edge-boundary degrees of assembled components. The edge-boundary degree of a component A (subset of V) is the number of edges in G with one endpoint in A and one endpoint in V-A. We call the maximum edge-boundary degree encountered during the reassembling process the alpha-measure of the reassembling, and the sum of all edge-boundary degrees is its beta-measure. The alpha-optimization (resp. beta-optimization) of the reassembling of G is to determine an order Θfor splicing the edges that minimizes its alpha-measure (resp. beta-measure). There are different forms of reassembling. We consider only cases satisfying the condition that if the an edge between disjoint components A and B is spliced, then all the edges between A and B are spliced at the same time. In this report, we examine the particular case of linear reassembling, which requires that the next edge to be spliced must be adjacent to an already spliced edge. We delay other forms of reassembling to follow-up reports. We prove that alpha-optimization of linear reassembling and minimum-cutwidth linear arrangment (CutWidth) are polynomially reducible to each other, and that beta-optimization of linear reassembling and minimum-cost linear arrangement (MinArr) are polynomially reducible to each other.
Downlink SINR Balancing in C-RAN under Limited Fronthaul Capacity
Venue: arXiv cs.IT 2015
Year: 2015

Cloud radio access network (C-RAN) with centralized baseband processing is envisioned as a promising candidate for the next-generation wireless communication network. However, the joint processing gain of C-RAN is fundamentally constrained by the finite-capacity fronthaul links between the central unit (CU) where joint processing is implemented and distributed access points known as remote radio heads (RRHs). In this paper, we consider the downlink communication in a C-RAN with multi-antenna RRHs and single-antenna users, and investigate the joint RRH beamforming and user-RRH association problem to maximize the minimum signal-to-interference-plus-noise ratio (SINR) of all users subject to each RRH's individual fronthaul capacity constraint. The formulated problem is in general NP-hard due to the fronthaul capacity constraints and thus is difficult to be solved optimally. In this paper, we propose a new iterative method for this problem which decouples the design of beamforming and user association, where the number of users served by each RRH is iteratively reduced until the obtained beamforming and user association solution satisfies the fronthaul capacity constraints of all RRHs. A monotonic convergence is proved for the proposed algorithm, and it is shown by simulation that the algorithm achieves significant performance improvement over other heuristic solutions.
A Compositional Explanation of the Pet Fish Phenomenon
Venue: arXiv cs.AI 2015
Year: 2015

The `pet fish' phenomenon is often cited as a paradigm example of the `non-compositionality' of human concept use. We show here how this phenomenon is naturally accommodated within a compositional distributional model of meaning. This model describes the meaning of a composite concept by accounting for interaction between its constituents via their grammatical roles. We give two illustrative examples to show how the qualitative phenomena are exhibited. We go on to apply the model to experimental data, and finally discuss extensions of the formalism.
Global results on reset-induced periodic trajectories of planar systems
Venue: arXiv cs.SY 2015
Year: 2015

We study the existence of asymptotically stable periodic trajectories induced by reset feedback. The analysis is developed for a planar system. Casting the problem into the hybrid setting, we show that a periodic orbit arises from the balance between the energy dissipated during flows and the energy restored by resets, at jumps. The stability of the periodic orbit is studied with hybrid Lyapunov tools. The satisfaction of the so-called hybrid basic conditions ensures the robustness of the asymptotic stability. Extensions of the approach to more general mechanical systems are discussed.
Universal Outlying sequence detection For Continuous Observations
Venue: arXiv cs.IT 2015
Year: 2015

The following detection problem is studied, in which there are $M$ sequences of samples out of which one outlier sequence needs to be detected. Each typical sequence contains $n$ independent and identically distributed (i.i.d.) continuous observations from a known distribution $π$, and the outlier sequence contains $n$ i.i.d. observations from an outlier distribution $μ$, which is distinct from $π$, but otherwise unknown. A universal test based on KL divergence is built to approximate the maximum likelihood test, with known $π$ and unknown $μ$. A data-dependent partitions based KL divergence estimator is employed. Such a KL divergence estimator is further shown to converge to its true value exponentially fast when the density ratio satisfies $0<K_1\leq \frac{dμ}{dπ}\leq K_2$, where $K_1$ and $K_2$ are positive constants, and this further implies that the test is exponentially consistent. The performance of the test is compared with that of a recently introduced test for this problem based on the machine learning approach of maximum mean discrepancy (MMD). We identify regimes in which the KL divergence based test is better than the MMD based test.
Practical Concurrent Priority Queues
Venue: arXiv cs.DS 2015
Year: 2015

Priority queues are abstract data structures which store a set of key/value pairs and allow efficient access to the item with the minimal (maximal) key. Such queues are an important element in various areas of computer science such as algorithmics (i.e. Dijkstra's shortest path algorithm) and operating system (i.e. priority schedulers). The recent trend towards multiprocessor computing requires new implementations of basic data structures which are able to be used concurrently and scale well to a large number of threads. In particular, lock-free structures promise superior scalability by avoiding the use of blocking synchronization primitives. Concurrent priority queues have been extensively researched over the past decades. In this paper, we discuss three major ideas within the field: fine-grained locking employs multiple locks to avoid a single bottleneck within the queue; SkipLists are search structures which use randomization and therefore do not require elaborate reorganization schemes; and relaxed data structures trade semantic guarantees for improved scalability.
A Novel Pre-processing Scheme to Improve the Prediction of Sand Fraction from Seismic Attributes using Neural Networks
Venue: arXiv cs.CE 2015
Year: 2015

This paper presents a novel pre-processing scheme to improve the prediction of sand fraction from multiple seismic attributes such as seismic impedance, amplitude and frequency using machine learning and information filtering. The available well logs along with the 3-D seismic data have been used to benchmark the proposed pre-processing stage using a methodology which primarily consists of three steps: pre-processing, training and post-processing. An Artificial Neural Network (ANN) with conjugate-gradient learning algorithm has been used to model the sand fraction. The available sand fraction data from the high resolution well logs has far more information content than the low resolution seismic attributes. Therefore, regularization schemes based on Fourier Transform (FT), Wavelet Decomposition (WD) and Empirical Mode Decomposition (EMD) have been proposed to shape the high resolution sand fraction data for effective machine learning. The input data sets have been segregated into training, testing and validation sets. The test results are primarily used to check different network structures and activation function performances. Once the network passes the testing phase with an acceptable performance in terms of the selected evaluators, the validation phase follows. In the validation stage, the prediction model is tested against unseen data. The network yielding satisfactory performance in the validation stage is used to predict lithological properties from seismic attributes throughout a given volume. Finally, a post-processing scheme using 3-D spatial filtering is implemented for smoothing the sand fraction in the volume. Prediction of lithological properties using this framework is helpful for Reservoir Characterization.