OpenRaiser/Intern-Atlas huggingface dataset:
Improving spliced alignment for identification of ortholog groups and multiple CDS alignment
Venue: arXiv cs.DS 2017
Year: 2017

The Spliced Alignment Problem (SAP) that consists in finding an optimal semi-global alignment of a spliced RNA sequence on an unspliced genomic sequence has been largely considered for the prediction and the annotation of gene structures in genomes. Here, we re-visit it for the purpose of identifying CDS ortholog groups within a set of CDS from homologous genes and for computing multiple CDS alignments. We introduce a new constrained version of the spliced alignment problem together with an algorithm that exploits full information on the exon-intron structure of the input RNA and gene sequences in order to compute high-coverage accurate alignments. We show how pairwise spliced alignments between the CDS and the gene sequences of a gene family can be directly used in order to clusterize the set of CDS of the gene family into a set of ortholog groups. We also introduce an extension of the spliced alignment problem called Multiple Spliced Alignment Problem (MSAP) that consists in aligning simultaneously several RNA sequences on several genes from the same gene family. We develop a heuristic algorithmic solution for the problem. We show how to exploit multiple spliced alignments for the clustering of homologous CDS into ortholog and close paralog groups, and for the construction of multiple CDS alignments. An implementation of the method in Python is available on demande to SFA@USherbrooke.ca. Keywords: Spliced alignment, CDS ortholog groups, Multiple CDS alignment, Gene structure, Gene family.
Robustness of Neural Networks against Storage Media Errors
Venue: arXiv cs.IT 2017
Year: 2017

We study the trade-offs between storage/bandwidth and prediction accuracy of neural networks that are stored in noisy media. Conventionally, it is assumed that all parameters (e.g., weight and biases) of a trained neural network are stored as binary arrays and are error-free. This assumption is based upon the implementation of error correction codes (ECCs) that correct potential bit flips in storage media. However, ECCs add storage overhead and cause bandwidth reduction when loading the trained parameters during the inference. We study the robustness of deep neural networks when bit errors exist but ECCs are turned off for different neural network models and datasets. It is observed that more sophisticated models and datasets are more vulnerable to errors in their trained parameters. We propose a simple detection approach that can universally improve the robustness, which in some cases can be improved by orders of magnitude. We also propose an alternative binary representation of the parameters such that the distortion brought by bit flips is reduced and even theoretically vanishing when the number of bits to represent a parameter increases.
Zooming in on NYC taxi data with Portal
Venue: arXiv cs.DB 2017
Year: 2017

In this paper we develop a methodology for analyzing transportation data at different levels of temporal and geographic granularity, and apply our methodology to the TLC Trip Record Dataset, made publicly available by the NYC Taxi & Limousine Commission. This data is naturally represented by a set of trajectories, annotated with time and with additional information such as passenger count and cost. We analyze TLC data to identify hotspots, which point to lack of convenient public transportation options, and popular routes, which motivate ride-sharing solutions or addition of a bus route. Our methodology is based on using a system called Portal, which implements efficient representations and principled analysis methods for evolving graphs. Portal is implemented on top of Apache Spark, a popular distributed data processing system, is inter-operable with other Spark libraries like SparkSQL, and supports sophisticated kinds of analysis of evolving graphs efficiently. Portal is currently under development in the Data, Responsibly Lab at Drexel. We plan to release Portal in the open source in Fall 2017.
Fast Discrete Linear Canonical Transform Based on CM-CC-CM Decomposition and FFT
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, a discrete LCT (DLCT) irrelevant to the sampling periods and without oversampling operation is developed. This DLCT is based on the well-known CM-CC-CM decomposition, that is, implemented by two discrete chirp multiplications (CMs) and one discrete chirp convolution (CC). This decomposition doesn't use any scaling operation which will change the sampling period or cause the interpolation error. Compared with previous works, DLCT calculated by direct summation and DLCT based on center discrete dilated Hermite functions (CDDHFs), the proposed method implemented by FFTs has much lower computational complexity. The relation between the proposed DLCT and the continuous LCT is also derived to approximate the samples of the continuous LCT. Simulation results show that the proposed method somewhat outperforms the CDDHFs-based method in the approximation accuracy. Besides, the proposed method has approximate additivity property with error as small as the CDDHFs-based method. Most importantly, the proposed method has perfect reversibility, which doesn't hold in many existing DLCTs. With this property, it is unnecessary to develop the inverse DLCT additionally because it can be replaced by the forward DLCT.
Inter-Operator Base Station Coordination in Spectrum-Shared Millimeter Wave Cellular Networks
Venue: arXiv cs.IT 2017
Year: 2017

We characterize the rate coverage distribution for a spectrum-shared millimeter wave downlink cellular network. Each of multiple cellular operators owns separate mmWave bandwidth, but shares the spectrum amongst each other while using dynamic inter-operator base station (BS) coordination to suppress the resulting cross-operator interference. We model the BS locations of each operator as mutually independent Poisson point processes, and derive the probability density function (PDF) of the K-th strongest link power, incorporating both line-of-sight and non line-of-sight states. Leveraging the obtained PDF, we derive the rate coverage expression as a function of system parameters such as the BS density, transmit power, bandwidth, and coordination set size. We verify the analysis with extensive simulation results. A major finding is that inter-operator BS coordination is useful in spectrum sharing (i) with dense and high power operators and (ii) with fairly wide beams, e.g., 30 or higher.
Random Caching in Backhaul-Limited Multi-Antenna Networks: Analysis and Area Spectrum Efficiency Optimization
Venue: arXiv cs.IT 2017
Year: 2017

Caching at base stations is a promising technology to satisfy the increasing capacity requirements and reduce the backhaul loads in future wireless networks. Careful design of random caching can fully exploit the file popularity and achieve good performance. However, previous works on random caching scheme usually assumed single antenna at BSs and users, which is not the case in practical multi-antenna networks. In this paper, we consider the analysis and optimization in the cache-enabled multi-antenna networks with limited backhaul. We first derive a closed-form expression and a simple tight upper bound of the successful transmission probability, using tools from stochastic geometry and a gamma approximation. Based on the analytic results, we then consider the area spectrum efficiency maximization by optimizing design parameters, which is a complicated mixed-integer optimization problem. After analyzing the optimal properties, we obtain a local optimal solution with lower complexity. To further simplify the optimization, we then solve an asymptotic optimization problem in the high user density region, using the upper bound as the objective function. Numerical simulations show that the asymptotic optimal caching scheme achieves better performance over existing caching schemes. The analysis and optimization results provide insightful design guidelines for random caching in practical networks.
Sparse Markov Decision Processes with Causal Sparse Tsallis Entropy Regularization for Reinforcement Learning
Venue: arXiv cs.LG 2017
Year: 2017

In this paper, a sparse Markov decision process (MDP) with novel causal sparse Tsallis entropy regularization is proposed.The proposed policy regularization induces a sparse and multi-modal optimal policy distribution of a sparse MDP. The full mathematical analysis of the proposed sparse MDP is provided.We first analyze the optimality condition of a sparse MDP. Then, we propose a sparse value iteration method which solves a sparse MDP and then prove the convergence and optimality of sparse value iteration using the Banach fixed point theorem. The proposed sparse MDP is compared to soft MDPs which utilize causal entropy regularization. We show that the performance error of a sparse MDP has a constant bound, while the error of a soft MDP increases logarithmically with respect to the number of actions, where this performance error is caused by the introduced regularization term. In experiments, we apply sparse MDPs to reinforcement learning problems. The proposed method outperforms existing methods in terms of the convergence speed and performance.
Tilt Assembly: Algorithms for Micro-Factories That Build Objects with Uniform External Forces
Venue: arXiv cs.DS 2017
Year: 2017

We present algorithmic results for the parallel assembly of many micro-scale objects in two and three dimensions from tiny particles, which has been proposed in the context of programmable matter and self-assembly for building high-yield micro-factories. The underlying model has particles moving under the influence of uniform external forces until they hit an obstacle; particles can bond when being forced together with another appropriate particle. Due to the physical and geometric constraints, not all shapes can be built in this manner; this gives rise to the Tilt Assembly Problem (TAP) of deciding constructibility. For simply-connected polyominoes $P$ in 2D consisting of $N$ unit-squares ("tiles"), we prove that TAP can be decided in $O(N\log N)$ time. For the optimization variant MaxTAP (in which the objective is to construct a subshape of maximum possible size), we show polyAPX-hardness: unless P=NP, MaxTAP cannot be approximated within a factor of $Ω(N^{\frac{1}{3}})$; for tree-shaped structures, we give an $O(N^{\frac{1}{2}})$-approximation algorithm. For the efficiency of the assembly process itself, we show that any constructible shape allows pipelined assembly, which produces copies of $P$ in $O(1)$ amortized time, i.e., $N$ copies of $P$ in $O(N)$ time steps. These considerations can be extended to three-dimensional objects: For the class of polycubes $P$ we prove that it is NP-hard to decide whether it is possible to construct a path between two points of $P$; it is also NP-hard to decide constructibility of a polycube $P$. Moreover, it is expAPX-hard to maximize a path from a given start point.
Human Action Forecasting by Learning Task Grammars
Venue: arXiv cs.CV 2017
Year: 2017

For effective human-robot interaction, it is important that a robotic assistant can forecast the next action a human will consider in a given task. Unfortunately, real-world tasks are often very long, complex, and repetitive; as a result forecasting is not trivial. In this paper, we propose a novel deep recurrent architecture that takes as input features from a two-stream Residual action recognition framework, and learns to estimate the progress of human activities from video sequences -- this surrogate progress estimation task implicitly learns a temporal task grammar with respect to which activities can be localized and forecasted. To learn the task grammar, we propose a stacked LSTM based multi-granularity progress estimation framework that uses a novel cumulative Euclidean loss as objective. To demonstrate the effectiveness of our proposed architecture, we showcase experiments on two challenging robotic assistive tasks, namely (i) assembling an Ikea table from its constituents, and (ii) changing the tires of a car. Our results demonstrate that learning task grammars offers highly discriminative cues improving the forecasting accuracy by more than 9% over the baseline two-stream forecasting model, while also outperforming other competitive schemes.
Interactive Music Generation with Positional Constraints using Anticipation-RNNs
Venue: arXiv cs.AI 2017
Year: 2017

Recurrent Neural Networks (RNNS) are now widely used on sequence generation tasks due to their ability to learn long-range dependencies and to generate sequences of arbitrary length. However, their left-to-right generation procedure only allows a limited control from a potential user which makes them unsuitable for interactive and creative usages such as interactive music generation. This paper introduces a novel architecture called Anticipation-RNN which possesses the assets of the RNN-based generative models while allowing to enforce user-defined positional constraints. We demonstrate its efficiency on the task of generating melodies satisfying positional constraints in the style of the soprano parts of the J.S. Bach chorale harmonizations. Sampling using the Anticipation-RNN is of the same order of complexity than sampling from the traditional RNN model. This fast and interactive generation of musical sequences opens ways to devise real-time systems that could be used for creative purposes.
Modeling and Control of Inverted Flight of a Variable-Pitch Quadrotor
Venue: arXiv cs.SY 2017
Year: 2017

This paper carries out the mathematical modeling, simulation, and control law design for a quadrotor with variable-pitch propellers. The use of variable-pitch propeller for thrust variation instead of RPM regulation facilitates generation of negative thrust, thereby augmenting the rate of change of thrust generation amenable for aggressive maneuvering. Blade element theory along with momentum theory is used to estimate propeller thrust and torque essential for formulating equation of motion of the vehicle. The proposed flight dynamics model is used for non-linear control design using dynamic inversion technique, which is then used to stabilize, track reference trajectory, and simulate flip maneuver. The rotor torque is an irrational function of the control input which makes the control design challenging. To address this problem, the control design employs three loops. The outer loop solves the translational dynamics to generate the thrust, pitch angle, and roll angle commands required to track the prescribed trajectory. Using the command generated in the outer loop, the inner loop simplifies the rotational dynamics to provide the desired rate of angular velocities. A control allocation loop is added to address the problem of nonlinearity associated with rotor torque. This is done by introducing the derivative of thrust coefficient as a virtual control input. These virtual inputs determine the derivatives of thrust and body moments, which in turn is used to generate the required thrust and body moments. The concept is validated by showing attitude stabilization in real flight for a variable pitch quadrotor. The performance of the proposed design is shown through simulated results for attitude stabilization and trajectory following. Reverse thrust capability of variable-pitch quadrotor is also shown by performing flip maneuver in which quadrotor roll angle changes from 0 to 180 degrees.
Language Modeling with Highway LSTM
Venue: arXiv cs.CL 2017
Year: 2017

Language models (LMs) based on Long Short Term Memory (LSTM) have shown good gains in many automatic speech recognition tasks. In this paper, we extend an LSTM by adding highway networks inside an LSTM and use the resulting Highway LSTM (HW-LSTM) model for language modeling. The added highway networks increase the depth in the time dimension. Since a typical LSTM has two internal states, a memory cell and a hidden state, we compare various types of HW-LSTM by adding highway networks onto the memory cell and/or the hidden state. Experimental results on English broadcast news and conversational telephone speech recognition show that the proposed HW-LSTM LM improves speech recognition accuracy on top of a strong LSTM LM baseline. We report 5.1% and 9.9% on the Switchboard and CallHome subsets of the Hub5 2000 evaluation, which reaches the best performance numbers reported on these tasks to date.
Human Activity Recognition Using Robust Adaptive Privileged Probabilistic Learning
Venue: arXiv cs.CV 2017
Year: 2017

In this work, a novel method based on the learning using privileged information (LUPI) paradigm for recognizing complex human activities is proposed that handles missing information during testing. We present a supervised probabilistic approach that integrates LUPI into a hidden conditional random field (HCRF) model. The proposed model is called HCRF+ and may be trained using both maximum likelihood and maximum margin approaches. It employs a self-training technique for automatic estimation of the regularization parameters of the objective functions. Moreover, the method provides robustness to outliers (such as noise or missing data) by modeling the conditional distribution of the privileged information by a Student's \textit{t}-density function, which is naturally integrated into the HCRF+ framework. Different forms of privileged information were investigated. The proposed method was evaluated using four challenging publicly available datasets and the experimental results demonstrate its effectiveness with respect to the-state-of-the-art in the LUPI framework using both hand-crafted features and features extracted from a convolutional neural network.
The geography of references in elite articles: What countries contribute to the archives of knowledge
Venue: arXiv cs.DL 2017
Year: 2017

This study is intended to find an answer for the question on which national "shoulders" the worldwide top-level research stands. Traditionally, national scientific standings are evaluated in terms of the number of citations to their papers. We raise a different question: instead of analyzing the citations to the countries' articles (the forward view), we examine referenced publications from specific countries cited in the most elite publications (the backward-citing-view). "Elite publications" are operationalized as the top-1% most-highly cited articles. Using the articles published during the years 2004 to 2013, we examine the research referenced in these works. Our results confirm the well-known fact that China has emerged to become a major player in science. However, China still belongs to the low contributors when countries are ranked as contributors to the cited references in top-1% articles. Using this perspective, the results do not point to a decreasing trend for the USA; in fact, the USA exceeds expectations (compared to its publication share) in terms of contributions to cited references in the top-1% articles. Switzerland, Sweden, and the Netherlands also are shown at the top of the list. However, the results for Germany are lower than statistically expected.
Getting Virtualized Wireless Sensor Networks IaaS Ready for PaaS
Venue: arXiv cs.NI 2017
Year: 2017

With the recent advances in sensor hardware and software, architectures for virtualized Wireless Sensor Networks (vWSNs) are now emerging. Through node- and network-level virtualization, vWSNs can be offered as Infrastructure-as-a-Service (IaaS) which can aid in realizing the true potential of Internet-of-Things (IoT). Cloud computing offers elastic provisioning of large-scale infrastructures to multiple concurrent users where Platform-as-a-Service (PaaS) interacts with IaaS in order to efficiently host and execute applications over these infrastructures. Amalgamating IoT with cloud computing potentially allows rapid application and service provisioning in an efficient, scalable and robust manner. However, interactions between vWSNs and PaaS are largely an unexplored area. Indeed, existing vWSN IaaS are not yet ready for PaaS. This paper proposes a vWSN IaaS architecture which is ready for interactions with PaaS. The proposed architecture is based on our previous works and is rooted in the fundamental differences between traditional IaaS and vWSN IaaS. We built a prototype using Java Sunspot as the WSN tool kit and made early performance measurements.
Learning to update Auto-associative Memory in Recurrent Neural Networks for Improving Sequence Memorization
Venue: arXiv cs.AI 2017
Year: 2017

Learning to remember long sequences remains a challenging task for recurrent neural networks. Register memory and attention mechanisms were both proposed to resolve the issue with either high computational cost to retain memory differentiability, or by discounting the RNN representation learning towards encoding shorter local contexts than encouraging long sequence encoding. Associative memory, which studies the compression of multiple patterns in a fixed size memory, were rarely considered in recent years. Although some recent work tries to introduce associative memory in RNN and mimic the energy decay process in Hopfield nets, it inherits the shortcoming of rule-based memory updates, and the memory capacity is limited. This paper proposes a method to learn the memory update rule jointly with task objective to improve memory capacity for remembering long sequences. Also, we propose an architecture that uses multiple such associative memory for more complex input encoding. We observed some interesting facts when compared to other RNN architectures on some well-studied sequence learning tasks.
Secure and Trustable Electronic Medical Records Sharing using Blockchain
Venue: arXiv cs.CY 2017
Year: 2017

Electronic medical records (EMRs) are critical, highly sensitive private information in healthcare, and need to be frequently shared among peers. Blockchain provides a shared, immutable and transparent history of all the transactions to build applications with trust, accountability and transparency. This provides a unique opportunity to develop a secure and trustable EMR data management and sharing system using blockchain. In this paper, we present our perspectives on blockchain based healthcare data management, in particular, for EMR data sharing between healthcare providers and for research studies. We propose a framework on managing and sharing EMR data for cancer patient care. In collaboration with Stony Brook University Hospital, we implemented our framework in a prototype that ensures privacy, security, availability, and fine-grained access control over EMR data. The proposed work can significantly reduce the turnaround time for EMR sharing, improve decision making for medical care, and reduce the overall cost
Parameterization of configuration space obstacles in three-dimensional rotational motion planning
Venue: arXiv cs.CG 2017
Year: 2017

This study investigates the exact geometry of the configuration space in three-dimensional rotational motion planning. A parameterization of configuration space obstacles is derived for a given triangulated or ball-approximated scene with an object rotating around a given point. The results obtained are an important step towards a complete description of the rich structure of a configuration space in three-dimensional rotational motion planning.