OpenRaiser/Intern-Atlas huggingface dataset:
On the Fronthaul Statistical Multiplexing Gain
Venue: arXiv cs.IT 2017
Year: 2017

Breaking the fronthaul capacity limitations is vital to make cloud radio access network (C-RAN) scalable and practical. One promising way is aggregating several remote radio units (RRUs) as a cluster to share a fronthaul link, so as to enjoy the statistical multiplexing gain brought by the spatial randomness of the traffic. In this letter, a tractable model is proposed to analyze the fronthaul statistical multiplexing gain. We first derive the user blocking probability caused by the limited fronthaul capacity, including its upper and lower bounds. We then obtain the limits of fronthaul statistical multiplexing gain when the cluster size approaches infinity. Analytical results reveal that the user blocking probability decreases exponentially with the average fronthaul capacity per RRU, and the exponent is proportional to the cluster size. Numerical results further show considerable fronthaul statistical multiplexing gain even at a small to medium cluster size.
Drug-Drug Interaction Extraction from Biomedical Text Using Long Short Term Memory Network
Venue: arXiv cs.CL 2017
Year: 2017

Simultaneous administration of multiple drugs can have synergistic or antagonistic effects as one drug can affect activities of other drugs. Synergistic effects lead to improved therapeutic outcomes, whereas, antagonistic effects can be life-threatening, may lead to increased healthcare cost, or may even cause death. Thus identification of unknown drug-drug interaction (DDI) is an important concern for efficient and effective healthcare. Although multiple resources for DDI exist, they are often unable to keep pace with rich amount of information available in fast growing biomedical texts. Most existing methods model DDI extraction from text as a classification problem and mainly rely on handcrafted features. Some of these features further depend on domain specific tools. Recently neural network models using latent features have been shown to give similar or better performance than the other existing models dependent on handcrafted features. In this paper, we present three models namely, {\it B-LSTM}, {\it AB-LSTM} and {\it Joint AB-LSTM} based on long short-term memory (LSTM) network. All three models utilize word and position embedding as latent features and thus do not rely on explicit feature engineering. Further use of bidirectional long short-term memory (Bi-LSTM) networks allow implicit feature extraction from the whole sentence. The two models, {\it AB-LSTM} and {\it Joint AB-LSTM} also use attentive pooling in the output of Bi-LSTM layer to assign weights to features. Our experimental results on the SemEval-2013 DDI extraction dataset show that the {\it Joint AB-LSTM} model outperforms all the existing methods, including those relying on handcrafted features. The other two proposed LSTM models also perform competitively with state-of-the-art methods.
Linear-time approximation schemes for planar minimum three-edge connected and three-vertex connected spanning subgraphs
Venue: arXiv cs.DS 2017
Year: 2017

We present the first polynomial-time approximation schemes, i.e., (1 + ε)-approximation algorithm for any constant ε > 0, for the minimum three-edge connected spanning subgraph problem and the minimum three-vertex connected spanning subgraph problem in undirected planar graphs. Both the approximation schemes run in linear time.
Scheduling Status Updates to Minimize Age of Information with an Energy Harvesting Sensor
Venue: arXiv cs.IT 2017
Year: 2017

Age of Information is a measure of the freshness of status updates in monitoring applications and update-based systems. We study a real-time remote sensing scenario with a sensor which is restricted by time-varying energy constraints and battery limitations. The sensor sends updates over a packet erasure channel with no feedback. The problem of finding an age-optimal threshold policy, with the transmission threshold being a function of the energy state and the estimated current age, is formulated. The average age is analyzed for the unit battery scenario under a memoryless energy arrival process. Somewhat surprisingly, for any finite arrival rate of energy, there is a positive age threshold for transmission, which corresponding to transmitting at a rate lower than that dictated by the rate of energy arrivals. A lower bound on the average age is obtained for general battery size.
Integer-Forcing Message Recovering in Interference Channels
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we propose a scheme referred to as integer-forcing message recovering (IFMR) to enable receivers to recover their desirable messages in interference channels. Compared to the state-of-the- art integer-forcing linear receiver (IFLR), our proposed IFMR approach needs to decode considerably less number of messages. In our method, each receiver recovers independent linear integer combinations of the desirable messages each from two independent equations. We propose an efficient algorithm to sequentially find the equations and integer combinations with maximum rates. We evaluate the performance of our scheme and compare the results with the minimum mean-square error (MMSE) and zero-forcing (ZF), as well as the IFLR schemes. The results indicate that our IFMR scheme outperforms the MMSE and ZF schemes, in terms of achievable rate, considerably. Also, compared to IFLR, the IFMR scheme achieves slightly less rates in moderate signal-to-noise ratios, with significantly less implementation complexity.
MSCM-LiFe: Multi-scale cross modal linear feature for horizon detection in maritime images
Venue: arXiv cs.CV 2017
Year: 2017

This paper proposes a new method for horizon detection called the multi-scale cross modal linear feature. This method integrates three different concepts related to the presence of horizon in maritime images to increase the accuracy of horizon detection. Specifically it uses the persistence of horizon in multi-scale median filtering, and its detection as a linear feature commonly detected by two different methods, namely the Hough transform of edgemap and the intensity gradient. We demonstrate the performance of the method over 13 videos comprising of more than 3000 frames and show that the proposed method detects horizon with small error in most of the cases, outperforming three state-of-the-art methods.
The HASYv2 dataset
Venue: arXiv cs.CV 2017
Year: 2017

This paper describes the HASYv2 dataset. HASY is a publicly available, free of charge dataset of single symbols similar to MNIST. It contains 168233 instances of 369 classes. HASY contains two challenges: A classification challenge with 10 pre-defined folds for 10-fold cross-validation and a verification challenge.
Decentralized Prediction Market without Arbiters
Venue: arXiv cs.CR 2017
Year: 2017

We consider a prediction market in which all aspects are controlled by market forces, in particular the correct outcomes of events are decided by the market itself rather than by trusted arbiters. This kind of a decentralized prediction market can sustain betting on events whose outcome may remain unresolved for a long or even unlimited time period, and can facilitate trades among participants who are spread across diverse geographical locations, may wish to remain anonymous and/or avoid burdensome identification procedures, and are distrustful of each other. We describe how a cryptocurrency such as Bitcoin can be enhanced to accommodate a truly decentralized prediction market, by employing an innovative variant of the Colored Coins concept. We examine the game-theoretic properties of our design, and offer extensions that enable other financial instruments as well as real-time exchange.
Riemann Tensor Polynomial Canonicalization by Graph Algebra Extension
Venue: arXiv cs.SC 2017
Year: 2017

Tensor expression simplification is an "ancient" topic in computer algebra, a representative of which is the canonicalization of Riemann tensor polynomials. Practically fast algorithms exist for monoterm canonicalization, but not for multiterm canonicalization. Targeting the multiterm difficulty, in this paper we establish the extension theory of graph algebra, and propose a canonicalization algorithm for Riemann tensor polynomials based on this theory.
Fast and Lightweight Rate Control for Onboard Predictive Coding of Hyperspectral Images
Venue: arXiv cs.IT 2017
Year: 2017

Predictive coding is attractive for compression of hyperspecral images onboard of spacecrafts in light of the excellent rate-distortion performance and low complexity of recent schemes. In this letter we propose a rate control algorithm and integrate it in a lossy extension to the CCSDS-123 lossless compression recommendation. The proposed rate algorithm overhauls our previous scheme by being orders of magnitude faster and simpler to implement, while still providing the same accuracy in terms of output rate and comparable or better image quality.
Model-Checking for Successor-Invariant First-Order Formulas on Graph Classes of Bounded Expansion
Venue: arXiv cs.LO 2017
Year: 2017

A successor-invariant first-order formula is a formula that has access to an auxiliary successor relation on a structure's universe, but the model relation is independent of the particular interpretation of this relation. It is well known that successor-invariant formulas are more expressive on finite structures than plain first-order formulas without a successor relation. This naturally raises the question whether this increase in expressive power comes at an extra cost to solve the model-checking problem, that is, the problem to decide whether a given structure together with some (and hence every) successor relation is a model of a given formula. It was shown earlier that adding successor-invariance to first-order logic essentially comes at no extra cost for the model-checking problem on classes of finite structures whose underlying Gaifman graph is planar [Engelmann et al., 2012], excludes a fixed minor [Eickmeyer et al., 2013] or a fixed topological minor [Eickmeyer and Kawarabayashi, 2016; Kreutzer et al., 2016]. In this work we show that the model-checking problem for successor-invariant formulas is fixed-parameter tractable on any class of finite structures whose underlying Gaifman graphs form a class of bounded expansion. Our result generalises all earlier results and comes close to the best tractability results on nowhere dense classes of graphs currently known for plain first-order logic.
Non-Orthogonal Multiple Access Schemes in Wireless Powered Communication Networks
Venue: arXiv cs.IT 2017
Year: 2017

We characterize time and power allocations to optimize the sum-throughput of a Wireless Powered Communication Network (WPCN) with Non-Orthogonal Multiple Access (NOMA). In our setup, an Energy Rich (ER) source broadcasts wireless energy to several devices, which use it to simultaneously transmit data to an Access Point (AP) on the uplink. Differently from most prior works, in this paper we consider a generic scenario, in which the ER and AP do not coincide, i.e., are two separate entities. We study two NOMA decoding schemes, namely Low Complexity Decoding (LCD) and Successive Interference Cancellation Decoding (SICD). For each scheme, we formulate a sum-throughput optimization problem over a finite horizon. Despite the complexity of the LCD optimization problem, due to its non-convexity, we recast it into a series of geometric programs. On the other hand, we establish the convexity of the SICD optimization problem and propose an algorithm to find its optimal solution. Our numerical results demonstrate the importance of using successive interference cancellation in WPCNs with NOMA, and show how the energy should be distributed as a function of the system parameters.
Theory Plug-in for Rodin 3.x
Venue: arXiv cs.SE 2017
Year: 2017

The Theory plug-in enables modellers to extend the mathematical modelling notation for Event-B, with accompanying support for reasoning about the extended language. Previous version of the Theory plug-in has been implemented based on Rodin 2.x. This presentation outline the main improvements to the The- ory plug-in, to be compatible with Rodin 3.x, in terms of both reliability and us- ability. We will also present the changes that were needed in the Rodin core to accommodate the Theory plug-in. Finally, we identify future enhancements and research directions for the Theory plug-in.
Signal Recovery from Unlabeled Samples
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we study the recovery of a signal from a set of noisy linear projections (measurements), when such projections are unlabeled, that is, the correspondence between the measurements and the set of projection vectors (i.e., the rows of the measurement matrix) is not known a priori. We consider a special case of unlabeled sensing referred to as Unlabeled Ordered Sampling (UOS) where the ordering of the measurements is preserved. We identify a natural duality between this problem and classical Compressed Sensing (CS), where we show that the unknown support (location of nonzero elements) of a sparse signal in CS corresponds to the unknown indices of the measurements in UOS. While in CS it is possible to recover a sparse signal from an under-determined set of linear equations (less equations than the signal dimension), successful recovery in UOS requires taking more samples than the dimension of the signal. Motivated by this duality, we develop a Restricted Isometry Property (RIP) similar to that in CS. We also design a low-complexity Alternating Minimization algorithm that achieves a stable signal recovery under the established RIP. We analyze our proposed algorithm for different signal dimensions and number of measurements theoretically and investigate its performance empirically via simulations. The results are reminiscent of phase-transition similar to that occurring in CS.
Bangla Word Clustering Based on Tri-gram, 4-gram and 5-gram Language Model
Venue: arXiv cs.CL 2017
Year: 2017

In this paper, we describe a research method that generates Bangla word clusters on the basis of relating to meaning in language and contextual similarity. The importance of word clustering is in parts of speech (POS) tagging, word sense disambiguation, text classification, recommender system, spell checker, grammar checker, knowledge discover and for many others Natural Language Processing (NLP) applications. In the history of word clustering, English and some other languages have already implemented some methods on word clustering efficiently. But due to lack of the resources, word clustering in Bangla has not been still implemented efficiently. Presently, its implementation is in the beginning stage. In some research of word clustering in English based on preceding and next five words of a key word they found an efficient result. Now, we are trying to implement the tri-gram, 4-gram and 5-gram model of word clustering for Bangla to observe which one is the best among them. We have started our research with quite a large corpus of approximate 1 lakh Bangla words. We are using a machine learning technique in this research. We will generate word clusters and analyze the clusters by testing some different threshold values.
Document Decomposition of Bangla Printed Text
Venue: arXiv cs.CV 2017
Year: 2017

Today all kind of information is getting digitized and along with all this digitization, the huge archive of various kinds of documents is being digitized too. We know that, Optical Character Recognition is the method through which, newspapers and other paper documents convert into digital resources. But, it is a fact that this method works on texts only. As a result, if we try to process any document which contains non-textual zones, then we will get garbage texts as output. That is why; in order to digitize documents properly they should be prepossessed carefully. And while preprocessing, segmenting document in different regions according to the category properly is most important. But, the Optical Character Recognition processes available for Bangla language have no such algorithm that can categorize a newspaper/book page fully. So we worked to decompose a document into its several parts like headlines, sub headlines, columns, images etc. And if the input is skewed and rotated, then the input was also deskewed and de-rotated. To decompose any Bangla document we found out the edges of the input image. Then we find out the horizontal and vertical area of every pixel where it lies in. Later on the input image was cut according to these areas. Then we pick each and every sub image and found out their height-width ratio, line height. Then according to these values the sub images were categorized. To deskew the image we found out the skew angle and de skewed the image according to this angle. To de-rotate the image we used the line height, matra line, pixel ratio of matra line.
Memory Augmented Neural Networks with Wormhole Connections
Venue: arXiv cs.LG 2017
Year: 2017

Recent empirical results on long-term dependency tasks have shown that neural networks augmented with an external memory can learn the long-term dependency tasks more easily and achieve better generalization than vanilla recurrent neural networks (RNN). We suggest that memory augmented neural networks can reduce the effects of vanishing gradients by creating shortcut (or wormhole) connections. Based on this observation, we propose a novel memory augmented neural network model called TARDIS (Temporal Automatic Relation Discovery in Sequences). The controller of TARDIS can store a selective set of embeddings of its own previous hidden states into an external memory and revisit them as and when needed. For TARDIS, memory acts as a storage for wormhole connections to the past to propagate the gradients more effectively and it helps to learn the temporal dependencies. The memory structure of TARDIS has similarities to both Neural Turing Machines (NTM) and Dynamic Neural Turing Machines (D-NTM), but both read and write operations of TARDIS are simpler and more efficient. We use discrete addressing for read/write operations which helps to substantially to reduce the vanishing gradient problem with very long sequences. Read and write operations in TARDIS are tied with a heuristic once the memory becomes full, and this makes the learning problem simpler when compared to NTM or D-NTM type of architectures. We provide a detailed analysis on the gradient propagation in general for MANNs. We evaluate our models on different long-term dependency tasks and report competitive results in all of them.
On the Computation of the Shannon Capacity of a Discrete Channel with Noise
Venue: arXiv cs.IT 2017
Year: 2017

Muroga [M52] showed how to express the Shannon channel capacity of a discrete channel with noise [S49] as an explicit function of the transition probabilities. His method accommodates channels with any finite number of input symbols, any finite number of output symbols and any transition probability matrix. Silverman [S55] carried out Muroga's method in the special case of a binary channel (and went on to analyse "cascades" of several such binary channels). This article is a note on the resulting formula for the capacity C(a, c) of a single binary channel. We aim to clarify some of the arguments and correct a small error. In service of this aim, we first formulate several of Shannon's definitions and proofs in terms of discrete measure-theoretic probability theory. We provide an alternate proof to Silverman's, of the feasibility of the optimal input distribution for a binary channel. For convenience, we also express C(a, c) in a single expression explicitly dependent on a and c only, which Silverman stopped short of doing.
Real-Time Control for Autonomous Racing Based on Viability Theory
Venue: arXiv cs.SY 2017
Year: 2017

In this paper we consider autonomous driving of miniature race cars. The viability kernel is used to efficiently generate finite look-ahead trajectories that maximize progress while remaining recursively feasible with respect to static obstacles (e.g., stay inside the track). Together with a low-level model predictive controller, this method makes real-time autonomous racing possible. The viability kernel computation is based on space discretization. To make the calculation robust against discretization errors, we propose a novel numerical scheme based on game theoretical methods, in particular the discriminating kernel. We show that the resulting algorithm provides an inner approximation of the viability kernel and guarantees that, for all states in the cell surrounding a viable grid point, there exists a control that keeps the system within the kernel. The performance of the proposed control method is studied in simulation where we determine the effects of various design choices and parameters and in experiments on an autonomous racing set-up maintained at the Automatic Control Laboratory of ETH Zurich. Both simulation and experimental results suggest that the more conservative approximation using the discriminating kernel results in safer driving style at the cost of a small increase in lap time.
Contraction of Cyclic Codes Over Finite Chain Rings
Venue: arXiv cs.IT 2017
Year: 2017

Let $\texttt{R}$ be a commutative finite chain ring of invariants $(q,s)$ and $Γ(\texttt{R})$ the Teichmüller's set of $\texttt{R}.$ In this paper, the trace representation cyclic $\texttt{R}$-linear codes of length $\ell,$ is presented, when $\texttt{gcd}(\ell, q) = 1.$ We will show that the contractions of some cyclic $\texttt{R}$-linear codes of length $u\ell$ are $γ$-constacyclic $\texttt{R}$-linear codes of length $\ell,$ where $γ\inΓ(\texttt{R})$ and the multiplicative order of is $u.$
Universal Tree Source Coding Using Grammar-Based Compression
Venue: arXiv cs.IT 2017
Year: 2017

We apply so-called tree straight-line programs to the problem of lossless compression of binary trees. We derive upper bound on the maximal pointwise redundancy (or worst-case redundancy) that improve previous bounds obtained by Zhang, Yang, and Kieffer using directed acyclic graphs. Using this, we obtain universal codes for new classes of structered tree sources.
Vulnerability of Clustering under Node Failure in Complex Networks
Venue: arXiv cs.SI 2017
Year: 2017

Robustness in response to unexpected events is always desirable for real-world networks. To improve the robustness of any networked system, it is important to analyze vulnerability to external perturbation such as random failures or adversarial attacks occurring to elements of the network. In this paper, we study an emerging problem in assessing the robustness of complex networks: the vulnerability of the clustering of the network to the failure of network elements. Specifically, we identify vertices whose failures will critically damage the network by degrading its clustering, evaluated through the average clustering coefficient. This problem is important because any significant change made to the clustering, resulting from element-wise failures, could degrade network performance such as the ability for information to propagate in a social network. We formulate this vulnerability analysis as an optimization problem, prove its NP-completeness and non-monotonicity, and we offer two algorithms to identify the vertices most important to clustering. Finally, we conduct comprehensive experiments in synthesized social networks generated by various well-known models as well as traces of real social networks. The empirical results over other competitive strategies show the efficacy of our proposed algorithms.