OpenRaiser/Intern-Atlas huggingface dataset:
SINR Outage Evaluation in Cellular Networks: Saddle Point Approximation (SPA) Using Normal Inverse Gaussian (NIG) Distribution
Venue: arXiv cs.IT 2017
Year: 2017

Signal-to-noise-plus-interference ratio (SINR) outage probability is among one of the key performance metrics of a wireless cellular network. In this paper, we propose a semi-analytical method based on saddle point approximation (SPA) technique to calculate the SINR outage of a wireless system whose SINR can be modeled in the form $\frac{\sum_{i=1}^M X_i}{\sum_{i=1}^N Y_i +1}$ where $X_i$ denotes the useful signal power, $Y_i$ denotes the power of the interference signal, and $\sum_{i=1}^M X_i$, $\sum_{i=1}^N Y_i$ are independent random variables. Both $M$ and $N$ can also be random variables. The proposed approach is based on the saddle point approximation to cumulative distribution function (CDF) as given by \tit{Wood-Booth-Butler formula}. The approach is applicable whenever the cumulant generating function (CGF) of the received signal and interference exists, and it allows us to tackle distributions with large skewness and kurtosis with higher accuracy. In this regard, we exploit a four parameter \tit{normal-inverse Gaussian} (NIG) distribution as a base distribution. Given that the skewness and kurtosis satisfy a specific condition, NIG-based SPA works reliably. When this condition is violated, we recommend SPA based on normal or symmetric NIG distribution, both special cases of NIG distribution, at the expense of reduced accuracy. For the purpose of demonstration, we apply SPA for the SINR outage evaluation of a typical user experiencing a downlink coordinated multi-point transmission (CoMP) from the base stations (BSs) that are modeled by homogeneous Poisson point process. We characterize the outage of the typical user in scenarios such as (a)~when the number and locations of interferers are random, and (b)~when the fading channels and number of interferers are random. Numerical results are presented to illustrate the accuracy of the proposed set of approximations.
Distributed Graph Layout for Scalable Small-world Network Analysis
Venue: arXiv cs.DC 2017
Year: 2017

The in-memory graph layout or organization has a considerable impact on the time and energy efficiency of distributed memory graph computations. It affects memory locality, inter-task load balance, communication time, and overall memory utilization. Graph layout could refer to partitioning or replication of vertex and edge arrays, selective replication of data structures that hold meta-data, and reordering vertex and edge identifiers. In this work, we present DGL, a fast, parallel, and memory-efficient distributed graph layout strategy that is specifically designed for small-world networks (low-diameter graphs with skewed vertex degree distributions). Label propagation-based partitioning and a scalable BFS-based ordering are the main steps in the layout strategy. We show that the DGL layout can significantly improve end-to-end performance of five challenging graph analytics workloads: PageRank, a parallel subgraph enumeration program, tuned implementations of breadth-first search and single-source shortest paths, and RDF3X-MPI, a distributed SPARQL query processing engine. Using these benchmarks, we additionally offer a comprehensive analysis on how graph layout affects the performance of graph analytics with variable computation and communication characteristics.
Bottom-Up Evaluation of Datalog: Preliminary Report
Venue: arXiv cs.DB 2017
Year: 2017

Bottom-up evaluation of Datalog has been studied for a long time, and is standard material in textbooks. However, if one actually wants to develop a deductive database system, it turns out that there are many implementation options. For instance, the sequence in which rule instances are applied is not given. In this paper, we study a method that immediately uses a derived tuple to derive more tuples (called the Push method). In this way, storage space for intermediate results can be reduced. The main contribution of our method is the way in which we minimize the copying of values at runtime, and do much work already at compile-time.
A Practical View on Renaming
Venue: arXiv cs.LO 2017
Year: 2017

We revisit variable renaming from a practitioner's point of view, presenting concepts we found useful in dealing with operational semantics of pure Prolog. A concept of relaxed core representation is introduced, upon which a concept of prenaming is built. Prenaming formalizes the intuitive practice of renaming terms by just considering the necessary bindings, where now some passive "bindings" x/x may be necessary as well. As an application, a constructive version of variant lemma for implemented Horn clause logic has been obtained. There, prenamings made it possible to incrementally handle new (local) variables.
An Extension of Proof Graphs for Disjunctive Parameterised Boolean Equation Systems
Venue: arXiv cs.LO 2017
Year: 2017

A parameterised Boolean equation system (PBES) is a set of equations that defines sets as the least and/or greatest fixed-points that satisfy the equations. This system is regarded as a declarative program defining functions that take a datum and returns a Boolean value. The membership problem of PBESs is a problem to decide whether a given element is in the defined set or not, which corresponds to an execution of the program. This paper introduces reduced proof graphs, and studies a technique to solve the membership problem of PBESs, which is undecidable in general, by transforming it into a reduced proof graph. A vertex X(v) in a proof graph represents that the data v is in the set X, if the graph satisfies conditions induced from a given PBES. Proof graphs are, however, infinite in general. Thus we introduce vertices each of which stands for a set of vertices of the original ones, which possibly results in a finite graph. For a subclass of disjunctive PBESs, we clarify some conditions which reduced proof graphs should satisfy. We also show some examples having no finite proof graph except for reduced one. We further propose a reduced dependency space, which contains reduced proof graphs as sub-graphs if a proof graph exists. We provide a procedure to construct finite reduced dependency spaces, and show the soundness and completeness of the procedure.
Deterministic and Probabilistic Conditions for Finite Completability of Low-rank Multi-View Data
Venue: arXiv cs.IT 2017
Year: 2017

We consider the multi-view data completion problem, i.e., to complete a matrix $\mathbf{U}=[\mathbf{U}_1|\mathbf{U}_2]$ where the ranks of $\mathbf{U},\mathbf{U}_1$, and $\mathbf{U}_2$ are given. In particular, we investigate the fundamental conditions on the sampling pattern, i.e., locations of the sampled entries for finite completability of such a multi-view data given the corresponding rank constraints. In contrast with the existing analysis on Grassmannian manifold for a single-view matrix, i.e., conventional matrix completion, we propose a geometric analysis on the manifold structure for multi-view data to incorporate more than one rank constraint. We provide a deterministic necessary and sufficient condition on the sampling pattern for finite completability. We also give a probabilistic condition in terms of the number of samples per column that guarantees finite completability with high probability. Finally, using the developed tools, we derive the deterministic and probabilistic guarantees for unique completability.
Employing Antenna Selection to Improve Energy-Efficiency in Massive MIMO Systems
Venue: arXiv cs.IT 2017
Year: 2017

Massive MIMO systems promise high data rates by employing large number of antennas, which also increases the power usage of the system as a consequence. This creates an optimization problem which specifies how many antennas the system should employ in order to operate with maximal energy efficiency. Our main goal is to consider a base station with a fixed number of antennas, such that the system can operate with a smaller subset of antennas according to the number of active user terminals, which may vary over time. Thus, in this paper we propose an antenna selection algorithm which selects the best antennas according to the better channel conditions with respect to the users, aiming at improving the overall energy efficiency. Then, due to the complexity of the mathematical formulation, a tight approximation for the consumed power is presented, using the Wishart theorem, and it is used to find a deterministic formulation for the energy efficiency. Simulation results show that the approximation is quite tight and that there is significant improvement in terms of energy efficiency when antenna selection is employed.
Fuzzy Based Implicit Sentiment Analysis on Quantitative Sentences
Venue: arXiv cs.CL 2017
Year: 2017

With the rapid growth of social media on the web, emotional polarity computation has become a flourishing frontier in the text mining community. However, it is challenging to understand the latest trends and summarize the state or general opinions about products due to the big diversity and size of social media data and this creates the need of automated and real time opinion extraction and mining. On the other hand, the bulk of current research has been devoted to study the subjective sentences which contain opinion keywords and limited work has been reported for objective statements that imply sentiment. In this paper, fuzzy based knowledge engineering model has been developed for sentiment classification of special group of such sentences including the change or deviation from desired range or value. Drug reviews are the rich source of such statements. Therefore, in this research, some experiments were carried out on patient's reviews on several different cholesterol lowering drugs to determine their sentiment polarity. The main conclusion through this study is, in order to increase the accuracy level of existing drug opinion mining systems, objective sentences which imply opinion should be taken into account. Our experimental results demonstrate that our proposed model obtains over 72 percent F1 value.
Dense Associative Memory is Robust to Adversarial Inputs
Venue: arXiv cs.LG 2017
Year: 2017

Deep neural networks (DNN) trained in a supervised way suffer from two known problems. First, the minima of the objective function used in learning correspond to data points (also known as rubbish examples or fooling images) that lack semantic similarity with the training data. Second, a clean input can be changed by a small, and often imperceptible for human vision, perturbation, so that the resulting deformed input is misclassified by the network. These findings emphasize the differences between the ways DNN and humans classify patterns, and raise a question of designing learning algorithms that more accurately mimic human perception compared to the existing methods. Our paper examines these questions within the framework of Dense Associative Memory (DAM) models. These models are defined by the energy function, with higher order (higher than quadratic) interactions between the neurons. We show that in the limit when the power of the interaction vertex in the energy function is sufficiently large, these models have the following three properties. First, the minima of the objective function are free from rubbish images, so that each minimum is a semantically meaningful pattern. Second, artificial patterns poised precisely at the decision boundary look ambiguous to human subjects and share aspects of both classes that are separated by that decision boundary. Third, adversarial images constructed by models with small power of the interaction vertex, which are equivalent to DNN with rectified linear units (ReLU), fail to transfer to and fool the models with higher order interactions. This opens up a possibility to use higher order models for detecting and stopping malicious adversarial attacks. The presented results suggest that DAM with higher order energy functions are closer to human visual perception than DNN with ReLUs.
World Literature According to Wikipedia: Introduction to a DBpedia-Based Framework
Venue: arXiv cs.IR 2017
Year: 2017

Among the manifold takes on world literature, it is our goal to contribute to the discussion from a digital point of view by analyzing the representation of world literature in Wikipedia with its millions of articles in hundreds of languages. As a preliminary, we introduce and compare three different approaches to identify writers on Wikipedia using data from DBpedia, a community project with the goal of extracting and providing structured information from Wikipedia. Equipped with our basic set of writers, we analyze how they are represented throughout the 15 biggest Wikipedia language versions. We combine intrinsic measures (mostly examining the connectedness of articles) with extrinsic ones (analyzing how often articles are frequented by readers) and develop methods to evaluate our results. The better part of our findings seems to convey a rather conservative, old-fashioned version of world literature, but a version derived from reproducible facts revealing an implicit literary canon based on the editing and reading behavior of millions of people. While still having to solve some known issues, the introduced methods will help us build an observatory of world literature to further investigate its representativeness and biases.
A Survey on Mobile Edge Computing: The Communication Perspective
Venue: arXiv cs.IT 2017
Year: 2017

Driven by the visions of Internet of Things and 5G communications, recent years have seen a paradigm shift in mobile computing, from the centralized Mobile Cloud Computing towards Mobile Edge Computing (MEC). The main feature of MEC is to push mobile computing, network control and storage to the network edges (e.g., base stations and access points) so as to enable computation-intensive and latency-critical applications at the resource-limited mobile devices. MEC promises dramatic reduction in latency and mobile energy consumption, tackling the key challenges for materializing 5G vision. The promised gains of MEC have motivated extensive efforts in both academia and industry on developing the technology. A main thrust of MEC research is to seamlessly merge the two disciplines of wireless communications and mobile computing, resulting in a wide-range of new designs ranging from techniques for computation offloading to network architectures. This paper provides a comprehensive survey of the state-of-the-art MEC research with a focus on joint radio-and-computational resource management. We also present a research outlook consisting of a set of promising directions for MEC research, including MEC system deployment, cache-enabled MEC, mobility management for MEC, green MEC, as well as privacy-aware MEC. Advancements in these directions will facilitate the transformation of MEC from theory to practice. Finally, we introduce recent standardization efforts on MEC as well as some typical MEC application scenarios.
Textual Entailment with Structured Attentions and Composition
Venue: arXiv cs.CL 2017
Year: 2017

Deep learning techniques are increasingly popular in the textual entailment task, overcoming the fragility of traditional discrete models with hard alignments and logics. In particular, the recently proposed attention models (Rocktäschel et al., 2015; Wang and Jiang, 2015) achieves state-of-the-art accuracy by computing soft word alignments between the premise and hypothesis sentences. However, there remains a major limitation: this line of work completely ignores syntax and recursion, which is helpful in many traditional efforts. We show that it is beneficial to extend the attention model to tree nodes between premise and hypothesis. More importantly, this subtree-level attention reveals information about entailment relation. We study the recursive composition of this subtree-level entailment relation, which can be viewed as a soft version of the Natural Logic framework (MacCartney and Manning, 2009). Experiments show that our structured attention and entailment composition model can correctly identify and infer entailment relations from the bottom up, and bring significant improvements in accuracy.
Gunrock: GPU Graph Analytics
Venue: arXiv cs.DC 2017
Year: 2017

For large-scale graph analytics on the GPU, the irregularity of data access and control flow, and the complexity of programming GPUs, have presented two significant challenges to developing a programmable high-performance graph library. "Gunrock", our graph-processing system designed specifically for the GPU, uses a high-level, bulk-synchronous, data-centric abstraction focused on operations on a vertex or edge frontier. Gunrock achieves a balance between performance and expressiveness by coupling high performance GPU computing primitives and optimization strategies with a high-level programming model that allows programmers to quickly develop new graph primitives with small code size and minimal GPU programming knowledge. We characterize the performance of various optimization strategies and evaluate Gunrock's overall performance on different GPU architectures on a wide range of graph primitives that span from traversal-based algorithms and ranking algorithms, to triangle counting and bipartite-graph-based algorithms. The results show that on a single GPU, Gunrock has on average at least an order of magnitude speedup over Boost and PowerGraph, comparable performance to the fastest GPU hardwired primitives and CPU shared-memory graph libraries such as Ligra and Galois, and better performance than any other GPU high-level graph library.
Consensus as a Nash Equilibrium of a Dynamic Game
Venue: arXiv cs.SY 2017
Year: 2017

Consensus formation in a social network is modeled by a dynamic game of a prescribed duration played by members of the network. Each member independently minimizes a cost function that represents his/her motive. An integral cost function penalizes a member's differences of opinion from the others as well as from his/her own initial opinion, weighted by influence and stubbornness parameters. Each member uses its rate of change of opinion as a control input. This defines a dynamic non-cooperative game that turns out to have a unique Nash equilibrium. Analytic explicit expressions are derived for the opinion trajectory of each member for two representative cases obtained by suitable assumptions on the graph topology of the network. These trajectories are then examined under different assumptions on the relative sizes of the influence and stubbornness parameters that appear in the cost functions.
Subpopulation Diversity Based Selecting Migration Moment in Distributed Evolutionary Algorithms
Venue: arXiv cs.NE 2017
Year: 2017

In distributed evolutionary algorithms, migration interval is used to decide migration moments. Nevertheless, migration moments predetermined by intervals cannot match the dynamic situation of evolution. In this paper, a scheme of setting the success rate of migration based on subpopulation diversity at each interval is proposed. With the scheme, migration still occurs at intervals, but the probability of immigrants entering the target subpopulation will be determined by the diversity of this subpopulation according to a proposed formula. An analysis shows that the time consumption of our scheme is acceptable. In our experiments, the basement of parallelism is an evolutionary algorithm for the traveling salesman problem. Under different value combinations of parameters for the formula, outcomes for eight benchmark instances of the distributed evolutionary algorithm with the proposed scheme are compared with those of a traditional one, respectively. Results show that the distributed evolutionary algorithm based on our scheme has a significant advantage on solutions especially for high difficulty instances. Moreover, it can be seen that the algorithm with the scheme has the most outstanding performance under three value combinations of above-mentioned parameters for the formula.
Twisted Reed-Solomon Codes
Venue: arXiv cs.IT 2017
Year: 2017

We present a new general construction of MDS codes over a finite field $\mathbb{F}_q$. We describe two explicit subclasses which contain new MDS codes of length at least $q/2$ for all values of $q \ge 11$. Moreover, we show that most of the new codes are not equivalent to a Reed-Solomon code.
Higher Order Context Transformations
Venue: arXiv cs.IT 2017
Year: 2017

The context transformation and generalized context transformation methods, we introduced recently, were able to reduce zero order entropy by exchanging digrams, and as a consequence, they were removing mutual information between consecutive symbols of the input message. These transformations were intended to be used as a preprocessor for zero-order entropy coding algorithms like Arithmetic or Huffman coding, since we know, that especially Arithmetic coding can achieve a compression rate almost of the size of Shannon's entropy. This paper introduces a novel algorithm based on the concept of generalized context transformation, that allows transformation of words longer than simple digrams. The higher order contexts are exploited using recursive form of a generalized context transformation. It is shown that the zero order entropy of transformed data drops significantly, but on the other hand, the overhead given by a description of individual transformations increases and it has become a limiting factor in a successful transformation of smaller files.
Generating Focussed Molecule Libraries for Drug Discovery with Recurrent Neural Networks
Venue: arXiv cs.NE 2017
Year: 2017

In de novo drug design, computational strategies are used to generate novel molecules with good affinity to the desired biological target. In this work, we show that recurrent neural networks can be trained as generative models for molecular structures, similar to statistical language models in natural language processing. We demonstrate that the properties of the generated molecules correlate very well with the properties of the molecules used to train the model. In order to enrich libraries with molecules active towards a given biological target, we propose to fine-tune the model with small sets of molecules, which are known to be active against that target. Against Staphylococcus aureus, the model reproduced 14% of 6051 hold-out test molecules that medicinal chemists designed, whereas against Plasmodium falciparum (Malaria) it reproduced 28% of 1240 test molecules. When coupled with a scoring function, our model can perform the complete de novo drug design cycle to generate large sets of novel molecules for drug discovery.
A High-Resolution Finite Volume Seismic Model to Generate Seafloor Deformation for Tsunami Modeling
Venue: arXiv cs.CE 2017
Year: 2017

A high-resolution finite volume method approach to incorporating time-dependent slip across rectangular subfaults when modeling general fault geometry is presented. The fault slip is induced by a modification of the Riemann problem to the linear elasticity equations across cell interfaces aligned with the subfaults. This is illustrated in the context of the high-resolution wave-propagation algorithms that are implemented in the open source Clawpack software (www.clawpack.org), but this approach could be easily incorporated into other Riemann solver based numerical methods. Surface deformation results are obtained in both two and three dimensions and compared to those given by the steady-state, homogeneous half-space Okada solution.