OpenRaiser/Intern-Atlas huggingface dataset:
Distributed Representations for Biological Sequence Analysis
Venue: arXiv cs.LG 2016
Year: 2016

Biological sequence comparison is a key step in inferring the relatedness of various organisms and the functional similarity of their components. Thanks to the Next Generation Sequencing efforts, an abundance of sequence data is now available to be processed for a range of bioinformatics applications. Embedding a biological sequence over a nucleotide or amino acid alphabet in a lower dimensional vector space makes the data more amenable for use by current machine learning tools, provided the quality of embedding is high and it captures the most meaningful information of the original sequences. Motivated by recent advances in the text document embedding literature, we present a new method, called seq2vec, to represent a complete biological sequence in an Euclidean space. The new representation has the potential to capture the contextual information of the original sequence necessary for sequence comparison tasks. We test our embeddings with protein sequence classification and retrieval tasks and demonstrate encouraging outcomes.
Median-Based Generation of Synthetic Speech Durations using a Non-Parametric Approach
Venue: arXiv cs.CL 2016
Year: 2016

This paper proposes a new approach to duration modelling for statistical parametric speech synthesis in which a recurrent statistical model is trained to output a phone transition probability at each timestep (acoustic frame). Unlike conventional approaches to duration modelling -- which assume that duration distributions have a particular form (e.g., a Gaussian) and use the mean of that distribution for synthesis -- our approach can in principle model any distribution supported on the non-negative integers. Generation from this model can be performed in many ways; here we consider output generation based on the median predicted duration. The median is more typical (more probable) than the conventional mean duration, is robust to training-data irregularities, and enables incremental generation. Furthermore, a frame-level approach to duration prediction is consistent with a longer-term goal of modelling durations and acoustic features together. Results indicate that the proposed method is competitive with baseline approaches in approximating the median duration of held-out natural speech.
DETOx: Towards Optimal Software-based Soft-Error Detector Configurations
Venue: arXiv cs.SE 2016
Year: 2016

Application developers often place executable assertions -- equipped with program-specific predicates -- in their system, targeting programming errors. However, these detectors can detect data errors resulting from transient hardware faults in main memory as well. But while an assertion reduces silent data corruptions (SDCs) in the program state they check, they add runtime to the target program that increases the attack surface for the remaining state. This article outlines an approach to find an optimal subset of assertions that minimizes the SDC count, without the need to run fault-injection experiments for every possible assertion subset.
Optimal Demand Side Management by Distributed and Secured Energy Commitment Framework
Venue: arXiv cs.MA 2016
Year: 2016

This paper introduces a demand-side distributed and secured energy commitment framework and operations for a Power Producer and Supplier (PPS) in deregulated environment. Due to the diversity of geographical location as well as customers' energy profile coupled with high number of customers, managing energy transactions and resulting energy exchanges are challenging for a PPS. The envisioned PPS maintains several aggregators (e.g. Microgrids), named as Sub Service Provider (SSP) that manage customers/subscribers under their domains. The SSPs act as agents that perform local energy matching (inside their domains) and distributed energy matching within SSPs to determine the energy commitment. The goal of the distributed energy matching is to reduce the involvement of External Energy Supplier (e.g. Utility) while providing a platform to demand side players to be a part of energy transaction. A distributed assignment problem is designed that requires minimum and aggregated information exchange (hence, secured) and solved by Linear Programming (LP) that provides the distributed matching decision. The communicative burden among SSPs due to the exchange of energy information is reduced by applying an adaptive coalition formation method. The simulations are conducted by implementing a synchronous distributed matching algorithm while showing the effectiveness of the proposed framework.
On Spectrum and Infrastructure Sharing in Multi-Operator Cellular Networks
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we introduce a mathematical framework for analyzing and optimizing multi-operator cellular networks that are allowed to share spectrum licenses and infrastructure elements. The proposed approach exploits stochastic geometry for modeling the locations of cellular base stations and for computing the aggregate average rate. The trade-offs that emerge from sharing spectrum frequencies and cellular base stations are quantified and discussed.
Infusing Collaborative Recommenders with Distributed Representations
Venue: arXiv cs.IR 2016
Year: 2016

Recommender systems assist users in navigating complex information spaces and focus their attention on the content most relevant to their needs. Often these systems rely on user activity or descriptions of the content. Social annotation systems, in which users collaboratively assign tags to items, provide another means to capture information about users and items. Each of these data sources provides unique benefits, capturing different relationships. In this paper, we propose leveraging multiple sources of data: ratings data as users report their affinity toward an item, tagging data as users assign annotations to items, and item data collected from an online database. Taken together, these datasets provide the opportunity to learn rich distributed representations by exploiting recent advances in neural network architectures. We first produce representations that subjectively capture interesting relationships among the data. We then empirically evaluate the utility of the representations to predict a user's rating on an item and show that it outperforms more traditional representations. Finally, we demonstrate that traditional representations can be combined with representations trained through a neural network to achieve even better results.
A PTAS for the Steiner Forest Problem in Doubling Metrics
Venue: arXiv cs.DS 2016
Year: 2016

We achieve a (randomized) polynomial-time approximation scheme (PTAS) for the Steiner Forest Problem in doubling metrics. Before our work, a PTAS is given only for the Euclidean plane in [FOCS 2008: Borradaile, Klein and Mathieu]. Our PTAS also shares similarities with the dynamic programming for sparse instances used in [STOC 2012: Bartal, Gottlieb and Krauthgamer] and [SODA 2016: Chan and Jiang]. However, extending previous approaches requires overcoming several non-trivial hurdles, and we make the following technical contributions. (1) We prove a technical lemma showing that Steiner points have to be "near" the terminals in an optimal Steiner tree. This enables us to define a heuristic to estimate the local behavior of the optimal solution, even though the Steiner points are unknown in advance. This lemma also generalizes previous results in the Euclidean plane, and may be of independent interest for related problems involving Steiner points. (2) We develop a novel algorithmic technique known as "adaptive cells" to overcome the difficulty of keeping track of multiple components in a solution. Our idea is based on but significantly different from the previously proposed "uniform cells" in the FOCS 2008 paper, whose techniques cannot be readily applied to doubling metrics.
Quantization and Feedback of Spatial Covariance Matrix for Massive MIMO Systems with Cascaded Precoding
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we investigate the quantization and the feedback of downlink spatial covariance matrix for massive multiple-input multiple-output (MIMO) systems with cascaded precoding. Massive MIMO has gained a lot of attention recently because of its ability to significantly improve the network performance. To reduce the overhead of downlink channel estimation and uplink feedback in frequency-division duplex massive MIMO systems, cascaded precoding has been proposed, where the outer precoder is implemented using traditional limited feedback while the inner precoder is determined by the spatial covariance matrix of the channels. In massive MIMO systems, it is difficult to quantize the spatial covariance matrix because of its large size caused by the huge number of antennas. In this paper, we propose a spatial spectrum based approach for the quantization and the feedback of the spatial covariance matrix. The proposed inner precoder can be viewed as modulated discrete prolate spheroidal sequences and thus achieve much smaller spatial leakage than the traditional discrete Fourier transform submatrix based precoding. Practical issues for the application of the proposed approach are also addressed in this paper.
A New Parallelization Method for K-means
Venue: arXiv cs.DC 2016
Year: 2016

K-means is a popular clustering method used in data mining area. To work with large datasets, researchers propose PKMeans, which is a parallel k-means on MapReduce. However, the existing k-means parallelization methods including PKMeans have many limitations. PKMeans can't finish all its iterations in one MapReduce job, so it has to repeat cascading MapReduce jobs in a loop until convergence. On the most popular MapReduce platform, Hadoop, every MapReduce job introduces significant I/O overheads and extra execution time at stages of job start-up and shuffling. Even worse, it has been proved that in the worst case, k-means needs $2^{Ω(n)}$ MapReduce jobs to converge, where n is the number of data instances, which means huge overheads for large datasets. Additionally, in PKMeans, at most one reducer can be assigned to and update each centroid, so PKMeans can only make use of limited number of parallel reducers. In this paper, we propose an improved parallel method for k-means, IPKMeans, which has a parallel preprocessing stage using k-d tree and can finish k-means in one single MapReduce job with much more reducers working in parallel and lower I/O overheads than PKMeans and has a fast post-processing stage generating the final result. In our method, both k-d tree and the new improved parallel k-means are implemented using MapReduce and tested on Hadoop. Our experiments show that with same dataset and initial centroids, our method has up to 2/3 lower I/O overheads and consumes less amount of time than PKMeans to get a very close clustering result.
Learning to Communicate: Channel Auto-encoders, Domain Specific Regularizers, and Attention
Venue: arXiv cs.LG 2016
Year: 2016

We address the problem of learning efficient and adaptive ways to communicate binary information over an impaired channel. We treat the problem as reconstruction optimization through impairment layers in a channel autoencoder and introduce several new domain-specific regularizing layers to emulate common channel impairments. We also apply a radio transformer network based attention model on the input of the decoder to help recover canonical signal representations. We demonstrate some promising initial capacity results from this architecture and address several remaining challenges before such a system could become practical.
Online bin packing with cardinality constraints resolved
Venue: arXiv cs.DS 2016
Year: 2016

Cardinality constrained bin packing or bin packing with cardinality constraints is a basic bin packing problem. In the online version with the parameter k \geq 2, items having sizes in (0,1] associated with them are presented one by one to be packed into unit capacity bins, such that the capacities of bins are not exceeded, and no bin receives more than k items. We resolve the online problem in the sense that we prove a lower bound of 2 on the overall asymptotic competitive ratio. This closes this long standing open problem, since an algorithm of an absolute competitive ratio 2 is known. Additionally, we significantly improve the known lower bounds on the asymptotic competitive ratio for every specific value of k. The novelty of our constructions is based on full adaptivity that creates large gaps between item sizes. Thus, our lower bound inputs do not follow the common practice for online bin packing problems of having a known in advance input consisting of batches for which the algorithm needs to be competitive on every prefix of the input.
Geometric Interpretation of Theoretical Bounds for RSS-based Source Localization with Uncertain Anchor Positions
Venue: arXiv cs.IT 2016
Year: 2016

The Received Signal Strength based source localization can encounter severe problems originating from uncertain information about the anchor positions in practice. The anchor positions, although commonly assumed to be precisely known prior to the source localization, are usually obtained using previous estimation algorithm such as GPS. This previous estimation procedure produces anchor positions with limited accuracy that result in degradations of the source localization algorithm and topology uncertainty. We have recently addressed the problem with a joint estimation framework that jointly estimates the unknown source and uncertain anchors positions and derived the theoretical limits of the framework. This paper extends the authors previous work on the theoretical performance bounds of the joint localization framework with appropriate geometric interpretation of the overall problem exploiting the properties of semi-definiteness and symmetry of the Fisher Information Matrix and the Cram{è}r-Rao Lower Bound and using Information and Error Ellipses, respectively. The numerical results aim to illustrate and discuss the usefulness of the geometric interpretation. They provide in-depth insight into the geometrical properties of the joint localization problem underlining the various possibilities for practical design of efficient localization algorithms.
On Low-High Orders of Directed Graphs: Incremental Algorithms and Applications
Venue: arXiv cs.DS 2016
Year: 2016

A flow graph $G=(V,E,s)$ is a directed graph with a distinguished start vertex $s$. The dominator tree $D$ of $G$ is a tree rooted at $s$, such that a vertex $v$ is an ancestor of a vertex $w$ if and only if all paths from $s$ to $w$ include $v$. The dominator tree is a central tool in program optimization and code generation and has many applications in other diverse areas including constraint programming, circuit testing, biology, and in algorithms for graph connectivity problems. A low-high order of $G$ is a preorder $δ$ of $D$ that certifies the correctness of $D$ and has further applications in connectivity and path-determination problems. In this paper, we first consider how to maintain efficiently a low-high order of a flow graph incrementally under edge insertions. We present algorithms that run in $O(mn)$ total time for a sequence of $m$ edge insertions in an initially empty flow graph with $n$ vertices.These immediately provide the first incremental certifying algorithms for maintaining the dominator tree in $O(mn)$ total time, and also imply incremental algorithms for other problems. Hence, we provide a substantial improvement over the $O(m^2)$ simple-minded algorithms, which recompute the solution from scratch after each edge insertion. We also show how to apply low-high orders to obtain a linear-time $2$-approximation algorithm for the smallest $2$-vertex-connected spanning subgraph problem (2VCSS). Finally, we present efficient implementations of our new algorithms for the incremental low-high and 2VCSS problems and conduct an extensive experimental study on real-world graphs taken from a variety of application areas. The experimental results show that our algorithms perform very well in practice.
Does V-NIR based Image Enhancement Come with Better Features?
Venue: arXiv cs.CV 2016
Year: 2016

Image enhancement using the visible (V) and near-infrared (NIR) usually enhances useful image details. The enhanced images are evaluated by observers perception, instead of quantitative feature evaluation. Thus, can we say that these enhanced images using NIR information has better features in comparison to the computed features in the Red, Green, and Blue color channels directly? In this work, we present a new method to enhance the visible images using NIR information via edge-preserving filters, and also investigate which method performs best from a image features standpoint. We then show that our proposed enhancement method produces more stable features than the existing state-of-the-art methods.
Network coding in undirected graphs is either very helpful or not helpful at all
Venue: arXiv cs.IT 2016
Year: 2016

While it is known that using network coding can significantly improve the throughput of directed networks, it is a notorious open problem whether coding yields any advantage over the multicommodity flow (MCF) rate in undirected networks. It was conjectured by Li and Li (2004) that the answer is "no". In this paper we show that even a small advantage over MCF can be amplified to yield a near-maximum possible gap. We prove that any undirected network with $k$ source-sink pairs that exhibits a $(1+\varepsilon)$ gap between its MCF rate and its network coding rate can be used to construct a family of graphs $G'$ whose gap is $\log(|G'|)^c$ for some constant $c < 1$. The resulting gap is close to the best currently known upper bound, $\log(|G'|)$, which follows from the connection between MCF and sparsest cuts. Our construction relies on a gap-amplifying graph tensor product that, given two graphs $G_1,G_2$ with small gaps, creates another graph $G$ with a gap that is equal to the product of the previous two, at the cost of increasing the size of the graph. We iterate this process to obtain a gap of $\log(|G'|)^c$ from any initial gap.
High-Quality Synthesis Against Stochastic Environments
Venue: arXiv cs.LO 2016
Year: 2016

In the classical synthesis problem, we are given an LTL formula psi over sets of input and output signals, and we synthesize a transducer that realizes psi. One weakness of automated synthesis in practice is that it pays no attention to the quality of the synthesized system. Indeed, the classical setting is Boolean: a computation satisfies a specification or does not satisfy it. Accordingly, while the synthesized system is correct, there is no guarantee about its quality. In recent years, researchers have considered extensions of the classical Boolean setting to a quantitative one. The logic LTL[F] is a multi-valued logic that augments LTL with quality operators. The satisfaction value of an LTL[F] formula is a real value in [0,1], where the higher the value is, the higher is the quality in which the computation satisfies the specification. Decision problems for LTL become search or optimization problems for LFL[F]. In particular, in the synthesis problem, the goal is to generate a transducer that satisfies the specification in the highest possible quality. Previous work considered the worst-case setting, where the goal is to maximize the quality of the computation with the minimal quality. We introduce and solve the stochastic setting, where the goal is to generate a transducer that maximizes the expected quality of a computation, subject to a given distribution of the input signals. Thus, rather than being hostile, the environment is assumed to be probabilistic, which corresponds to many realistic settings. We show that the problem is 2EXPTIME-complete, like classical LTL synthesis, and remains so in two extensions we consider: one that maximizes the expected quality while guaranteeing that the minimal quality is, with probability $1$, above a given threshold, and one that allows assumptions on the environment.
Synergistic Sorting, MultiSelection and Deferred Data Structures on MultiSets
Venue: arXiv cs.DS 2016
Year: 2016

Karp et al. (1988) described Deferred Data Structures for Multisets as "lazy" data structures which partially sort data to support online rank and select queries, with the minimum amount of work in the worst case over instances of size $n$ and number of queries $q$ fixed (i.e., the query size). Barbay et al. (2016) refined this approach to take advantage of the gaps between the positions hit by the queries (i.e., the structure in the queries). We develop new techniques in order to further refine this approach and to take advantage all at once of the structure (i.e., the multiplicities of the elements), the local order (i.e., the number and sizes of runs) and the global order (i.e., the number and positions of existing pivots) in the input; and of the structure and order in the sequence of queries. Our main result is a synergistic deferred data structure which performs much better on large classes of instances, while performing always asymptotically as good as previous solutions. As intermediate results, we describe two new synergistic sorting algorithms, which take advantage of the structure and order (local and global) in the input, improving upon previous results which take advantage only of the structure (Munro and Spira 1979) or of the local order (Takaoka 1997) in the input; and one new multiselection algorithm which takes advantage of not only the order and structure in the input, but also of the structure in the queries. We described two compressed data structures to represent a multiset taking advantage of both the local order and structure, while supporting the operators rank and select on the multiset.
Future Network: End-to-End Slicing and Hop-On (a Slice)
Venue: arXiv cs.NI 2016
Year: 2016

The concept of network slice, i.e.,a service customized virtual network (VN) is attracting more and more attentions in the telecommunication industry. A slice is a set of network resources which fits the service attributes and requirements of customer services. The network resources consist of cloud resources and communication link resources. A slice can serve one or more customer services which share the similar service attributes and requirements. To define, create and manage a slice (VN) is one aspect of future networks. Another aspect is the slice operation, i.e., the provisioning of services to customers using created slices. In this paper, the focus is put on the configuration of slices and the operation of slices. In this paper, the detailed description of slice (VN) configuration is provided. A new concept of hop-on (a slice) is described. Given a well defined and configured end-to-end slice (VN), the realtime data traffic delivery over a slice is governed by network operation control entities, which are also pre-configured. Therefore, the procedure of customer traffic delivery over a slice is just like a traveler hopping on tourist bus and then the traffic control officers at key intersections directing the traveler to go through pre-designed routes until the destination is reached.