OpenRaiser/Intern-Atlas huggingface dataset:
Opportunistic Multi-Channel Access in Heterogeneous 5G Network with Renewable Energy Supplies
Venue: arXiv cs.IT 2015
Year: 2015

A heterogeneous system, where small networks (e.g., small cell or WiFi) boost the system throughput under the umbrella of a large network (e.g., large cell), is a promising architecture for the 5G wireless communication networks, where green and sustainable communication is also a key aspect. Renewable energy based communication via energy harvesting (EH) devices is one of such green technology candidates. In this paper, we study an uplink transmission scenario under a heterogeneous network hierarchy, where each mobile user (MU) is powered by a sustainable energy supply, capable of both deterministic access to the large network via one private channel, and dynamic access to a small network with certain probability via one common channel shared by multiple MUs. Considering a general EH model, i.e., energy arrivals are time-correlated, we study an opportunistic transmission scheme and aim to maximize the average throughput for each MU, which jointly exploits the statistics and current states of the private channel, common channel, battery level, and EH rate. Applying a simple yet efficient "save-then-transmit" scheme, the throughput maximization problem is cast as a "rate-of-return" optimal stopping problem. The optimal stopping rule is proved to has a time-dependent threshold-based structure for the case with general Markovian system dynamics, and degrades to a pure threshold policy for the case with independent and identically distributed system dynamics. As performance benchmarks, the optimal power allocation scheme with conventional power supplies is also examined. Finally, numerical results are presented, and a new concept of "EH diversity" is discussed.
Online Detection of Repetitions with Backtracking
Venue: arXiv cs.DS 2015
Year: 2015

In this paper we present two algorithms for the following problem: given a string and a rational $e > 1$, detect in the online fashion the earliest occurrence of a repetition of exponent $\ge e$ in the string. 1. The first algorithm supports the backtrack operation removing the last letter of the input string. This solution runs in $O(n\log m)$ time and $O(m)$ space, where $m$ is the maximal length of a string generated during the execution of a given sequence of $n$ read and backtrack operations. 2. The second algorithm works in $O(n\logσ)$ time and $O(n)$ space, where $n$ is the length of the input string and $σ$ is the number of distinct letters. This algorithm is relatively simple and requires much less memory than the previously known solution with the same working time and space. a string generated during the execution of a given sequence of $n$ read and backtrack operations.
Stochastic Interpretation for the Arimoto Algorithm
Venue: arXiv cs.IT 2015
Year: 2015

The Arimoto algorithm computes the Gallager function $\max_Q {E}_{0}^{}(ρ,Q)$ for a given channel ${P}_{}^{}(y \,|\, x)$ and parameter $ρ$, by means of alternating maximization. Along the way, it generates a sequence of input distributions ${Q}_{1}^{}(x)$, ${Q}_{2}^{}(x)$, ... , that converges to the maximizing input ${Q}_{}^{*}(x)$. We propose a stochastic interpretation for the Arimoto algorithm. We show that for a random (i.i.d.) codebook with a distribution ${Q}_{k}^{}(x)$, the next distribution ${Q}_{k+1}^{}(x)$ in the Arimoto algorithm is equal to the type (${Q}'$) of the feasible transmitted codeword that maximizes the conditional Gallager exponent (conditioned on a specific transmitted codeword type ${Q}'$). This interpretation is a first step toward finding a stochastic mechanism for on-line channel input adaptation.
Scaling laws in human speech, decreasing emergence of new words and a generalized model
Venue: arXiv cs.CL 2015
Year: 2015

Human language, as a typical complex system, its organization and evolution is an attractive topic for both physical and cultural researchers. In this paper, we present the first exhaustive analysis of the text organization of human speech. Two important results are that: (i) the construction and organization of spoken language can be characterized as Zipf's law and Heaps' law, as observed in written texts; (ii) word frequency vs. rank distribution and the growth of distinct words with the increase of text length shows significant differences between book and speech. In speech word frequency distribution are more concentrated on higher frequency words, and the emergence of new words decreases much rapidly when the content length grows. Based on these observations, a new generalized model is proposed to explain these complex dynamical behaviors and the differences between speech and book.
Detecting Redundant CSS Rules in HTML5 Applications: A Tree-Rewriting Approach
Venue: arXiv cs.LO 2015
Year: 2015

HTML5 applications normally have a large set of CSS (Cascading Style Sheets) rules for data display. Each CSS rule consists of a node selector (given in an XPath-like query language) and a declaration block (assigning values to selected nodes' display attributes). As web applications evolve, maintaining CSS files can easily become problematic. Some CSS rules will be replaced by new ones, but these obsolete (hence redundant) CSS rules often remain in the applications. Not only does this "bloat" the applications, but it also significantly increases web browsers' processing time. Most works on detecting redundant CSS rules in HTML5 applications do not consider the dynamic behaviors of HTML5 (specified in JavaScript); in fact, the only proposed method that takes these into account is dynamic analysis (a.k.a. testing), which cannot soundly prove redundancy of CSS rules. In this paper, we introduce an abstraction of HTML5 applications based on monotonic tree-rewriting and study its "redundancy problem". We establish the precise complexity of the problem and various subproblems of practical importance (ranging from P to EXP). In particular, our algorithm relies on an efficient reduction to an analysis of symbolic pushdown systems (for which highly optimised solvers are available), which yields a fast method for checking redundancy in practice. We implemented our algorithm and demonstrated its efficacy in detecting redundant CSS rules in HTML5 applications.
Area and Perimeter of the Convex Hull of Stochastic Points
Venue: arXiv cs.CG 2015
Year: 2015

Given a set $P$ of $n$ points in the plane, we study the computation of the probability distribution function of both the area and perimeter of the convex hull of a random subset $S$ of $P$. The random subset $S$ is formed by drawing each point $p$ of $P$ independently with a given rational probability $π_p$. For both measures of the convex hull, we show that it is \#P-hard to compute the probability that the measure is at least a given bound $w$. For $\varepsilon\in(0,1)$, we provide an algorithm that runs in $O(n^{6}/\varepsilon)$ time and returns a value that is between the probability that the area is at least $w$, and the probability that the area is at least $(1-\varepsilon)w$. For the perimeter, we show a similar algorithm running in $O(n^{6}/\varepsilon)$ time. Finally, given $\varepsilon,δ\in(0,1)$ and for any measure, we show an $O(n\log n+ (n/\varepsilon^2)\log(1/δ))$-time Monte Carlo algorithm that returns a value that, with probability of success at least $1-δ$, differs at most $\varepsilon$ from the probability that the measure is at least $w$.
Permutations of context-free and indexed languages
Venue: arXiv cs.FL 2015
Year: 2015

We consider the cyclic closure of a language, and its generalisation to the operators $C^k$ introduced by Brandstädt. We prove that the cyclic closure of an indexed language is indexed, and that if $L$ is a context-free language then $C^k(L)$ is indexed.
Standing Together for Reproducibility in Large-Scale Computing: Report on reproducibility@XSEDE
Venue: arXiv cs.DC 2015
Year: 2015

This is the final report on reproducibility@xsede, a one-day workshop held in conjunction with XSEDE14, the annual conference of the Extreme Science and Engineering Discovery Environment (XSEDE). The workshop's discussion-oriented agenda focused on reproducibility in large-scale computational research. Two important themes capture the spirit of the workshop submissions and discussions: (1) organizational stakeholders, especially supercomputer centers, are in a unique position to promote, enable, and support reproducible research; and (2) individual researchers should conduct each experiment as though someone will replicate that experiment. Participants documented numerous issues, questions, technologies, practices, and potentially promising initiatives emerging from the discussion, but also highlighted four areas of particular interest to XSEDE: (1) documentation and training that promotes reproducible research; (2) system-level tools that provide build- and run-time information at the level of the individual job; (3) the need to model best practices in research collaborations involving XSEDE staff; and (4) continued work on gateways and related technologies. In addition, an intriguing question emerged from the day's interactions: would there be value in establishing an annual award for excellence in reproducible research?
An Algorithm for Online K-Means Clustering
Venue: arXiv cs.DS 2015
Year: 2015

This paper shows that one can be competitive with the k-means objective while operating online. In this model, the algorithm receives vectors v_1,...,v_n one by one in an arbitrary order. For each vector the algorithm outputs a cluster identifier before receiving the next one. Our online algorithm generates ~O(k) clusters whose k-means cost is ~O(W*). Here, W* is the optimal k-means cost using k clusters and ~O suppresses poly-logarithmic factors. We also show that, experimentally, it is not much worse than k-means++ while operating in a strictly more constrained computational model.
On Nash Equilibrium and Evolutionarily Stable States that Are Not Characterised by the Folk Theorem
Venue: arXiv cs.GT 2015
Year: 2015

In evolutionary game theory, evolutionarily stable states are characterised by the folk theorem because exact solutions to the replicator equation are difficult to obtain. It is generally assumed that the folk theorem, which is the fundamental theory for non-cooperative games, defines all Nash equilibria in infinitely repeated games. Here, we prove that Nash equilibria that are not characterised by the folk theorem do exist. By adopting specific reactive strategies, a group of players can be better off by coordinating their actions in repeated games. We call it a type-k equilibrium when a group of k players coordinate their actions and they have no incentive to deviate from their strategies simultaneously. The existence and stability of the type-k equilibrium in general games is discussed. This study shows that the sets of Nash equilibria and evolutionarily stable states have greater cardinality than classic game theory has predicted in many repeated games.
Theoretical and Numerical Analysis of Approximate Dynamic Programming with Approximation Errors
Venue: arXiv cs.SY 2015
Year: 2015

This study is aimed at answering the famous question of how the approximation errors at each iteration of Approximate Dynamic Programming (ADP) affect the quality of the final results considering the fact that errors at each iteration affect the next iteration. To this goal, convergence of Value Iteration scheme of ADP for deterministic nonlinear optimal control problems with undiscounted cost functions is investigated while considering the errors existing in approximating respective functions. The boundedness of the results around the optimal solution is obtained based on quantities which are known in a general optimal control problem and assumptions which are verifiable. Moreover, since the presence of the approximation errors leads to the deviation of the results from optimality, sufficient conditions for stability of the system operated by the result obtained after a finite number of value iterations, along with an estimation of its region of attraction, are derived in terms of a calculable upper bound of the control approximation error. Finally, the process of implementation of the method on an orbital maneuver problem is investigated through which the assumptions made in the theoretical developments are verified and the sufficient conditions are applied for guaranteeing stability and near optimality.
Data Representation using the Weyl Transform
Venue: arXiv cs.CV 2015
Year: 2015

The Weyl transform is introduced as a rich framework for data representation. Transform coefficients are connected to the Walsh-Hadamard transform of multiscale autocorrelations, and different forms of dyadic periodicity in a signal are shown to appear as different features in its Weyl coefficients. The Weyl transform has a high degree of symmetry with respect to a large group of multiscale transformations, which allows compact yet discriminative representations to be obtained by pooling coefficients. The effectiveness of the Weyl transform is demonstrated through the example of textured image classification.
Multi-Scale Stochastic Simulation for Diffusive Molecular Communication
Venue: arXiv cs.ET 2015
Year: 2015

Recently, hybrid models have emerged that combine microscopic and mesoscopic regimes in a single stochastic reaction-diffusion simulation. Microscopic simulations track every individual molecule and are generally more accurate. Mesoscopic simulations partition the environment into subvolumes, track when molecules move between adjacent subvolumes, and are generally more computationally efficient. In this paper, we present the foundation of a multi-scale stochastic simulator from the perspective of molecular communication, for both mesoscopic and hybrid models, where we emphasize simulation accuracy at the receiver and efficiency in regions that are far from the communication link. Our multi-scale models use subvolumes of different sizes, between which we derive the diffusion event transition rate. Simulation results compare the accuracy and efficiency of traditional approaches with that of a regular hybrid method and with those of our proposed multi-scale methods.
Human-Data Interaction: The Human Face of the Data-Driven Society
Venue: arXiv cs.CY 2015
Year: 2015

The increasing generation and collection of personal data has created a complex ecosystem, often collaborative but sometimes combative, around companies and individuals engaging in the use of these data. We propose that the interactions between these agents warrants a new topic of study: Human-Data Interaction (HDI). In this paper we discuss how HDI sits at the intersection of various disciplines, including computer science, statistics, sociology, psychology and behavioural economics. We expose the challenges that HDI raises, organised into three core themes of legibility, agency and negotiability, and we present the HDI agenda to open up a dialogue amongst interested parties in the personal and big data ecosystems.
Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time
Venue: arXiv cs.DS 2015
Year: 2015

We present faster algorithms for computing the 2-edge and 2-vertex strongly connected components of a directed graph, which are straightforward generalizations of strongly connected components. While in undirected graphs the 2-edge and 2-vertex connected components can be found in linear time, in directed graphs only rather simple $O(m n)$-time algorithms were known. We use a hierarchical sparsification technique to obtain algorithms that run in time $O(n^2)$. For 2-edge strongly connected components our algorithm gives the first running time improvement in 20 years. Additionally we present an $O(m^2 / \log{n})$-time algorithm for 2-edge strongly connected components, and thus improve over the $O(m n)$ running time also when $m = O(n)$. Our approach extends to k-edge and k-vertex strongly connected components for any constant k with a running time of $O(n^2 \log^2 n)$ for edges and $O(n^3)$ for vertices.
Using Neural Networks for Click Prediction of Sponsored Search
Venue: arXiv cs.LG 2015
Year: 2015

Sponsored search is a multi-billion dollar industry and makes up a major source of revenue for search engines (SE). click-through-rate (CTR) estimation plays a crucial role for ads selection, and greatly affects the SE revenue, advertiser traffic and user experience. We propose a novel architecture for solving CTR prediction problem by combining artificial neural networks (ANN) with decision trees. First we compare ANN with respect to other popular machine learning models being used for this task. Then we go on to combine ANN with MatrixNet (proprietary implementation of boosted trees) and evaluate the performance of the system as a whole. The results show that our approach provides significant improvement over existing models.
Decentralized Formation Control with A Quadratic Lyapunov Function
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, we investigate a decentralized formation control algorithm for an undirected formation control model. Unlike other formation control problems where only the shape of a configuration counts, we emphasize here also its Euclidean embedding. By following this decentralized formation control law, the agents will converge to certain equilibrium of the control system. In particular, we show that there is a quadratic Lyapunov function associated with the formation control system whose unique local (global) minimum point is the target configuration. In view of the fact that there exist multiple equilibria (in fact, a continuum of equilibria) of the formation control system, and hence there are solutions of the system which converge to some equilibria other than the target configuration, we apply simulated annealing, as a heuristic method, to the formation control law to fix this problem. Simulation results show that sample paths of the modified stochastic system approach the target configuration.
Axiomatic constraint systems for proof search modulo theories
Venue: arXiv cs.LO 2015
Year: 2015

Goal-directed proof search in first-order logic uses meta-variables to delay the choice of witnesses; substitutions for such variables are produced when closing proof-tree branches, using first-order unification or a theory-specific background reasoner. This paper investigates a generalisation of such mechanisms whereby theory-specific constraints are produced instead of substitutions. In order to design modular proof-search procedures over such mechanisms, we provide a sequent calculus with meta-variables, which manipulates such constraints abstractly. Proving soundness and completeness of the calculus leads to an axiomatisation that identifies the conditions under which abstract constraints can be generated and propagated in the same way unifiers usually are. We then extract from our abstract framework a component interface and a specification for concrete implementations of background reasoners.
Controllability of Formations over Time-varying Graphs
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, we investigate the controllability of a class of formation control systems. Given a directed graph, we assign an agent to each of its vertices and let the edges of the graph describe the information flow in the system. We relate the strongly connected components of this graph to the reachable set of the formation control system. Moreover, we show that the formation control model is approximately path-controllable over a path-connected, open dense subset as long as the graph is weakly connected and satisfies some mild assumption on the numbers of vertices of the strongly connected components.
Network Synchronization with Convexity
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, we establish a few new synchronization conditions for complex networks with nonlinear and nonidentical self-dynamics with switching directed communication graphs. In light of the recent works on distributed sub-gradient methods, we impose integral convexity for the nonlinear node self-dynamics in the sense that the self-dynamics of a given node is the gradient of some concave function corresponding to that node. The node couplings are assumed to be linear but with switching directed communication graphs. Several sufficient and/or necessary conditions are established for exact or approximate synchronization over the considered complex networks. These results show when and how nonlinear node self-dynamics may cooperate with the linear diffusive coupling, which eventually leads to network synchronization conditions under relaxed connectivity requirements.
Urban spatial-temporal activity structures: a New Approach to Inferring the Intra-urban Functional Regions via Social Media Check-In Data
Venue: arXiv cs.SI 2015
Year: 2015

Most existing literature focuses on the exterior temporal rhythm of human movement to infer the functional regions in a city, but they neglects the underlying interdependence between the functional regions and human activities which uncovers more detailed characteristics of regions. In this research, we proposed a novel model based on the low rank approximation (LRA) to detect the functional regions using the data from about 15 million check-in records during a yearlong period in Shanghai, China. We find a series of latent structures, called urban spatial-temporal activity structure (USTAS). While interpreting these structures, a series of outstanding underlying associations between the spatial and temporal activity patterns can be found. Moreover, we can not only reproduce the observed data with a lower dimensional representative but also simultaneously project both the spatial and temporal activity patterns in the same coordinate system. By utilizing the K-means clustering algorithm, five significant types of clusters which are directly annotated with a corresponding combination of temporal activities can be obtained. This provides a clear picture of how the groups of regions are associated with different activities at different time of day. Besides the commercial and transportation dominant area, we also detect two kinds of residential areas, the developed residential areas and the developing residential areas. We further verify the spatial distribution of these clusters in the view of urban form analysis. The results shows a high consistency with the government planning from the same periods, indicating our model is applicable for inferring the functional regions via social media check-in data, and can benefit a wide range of fields, such as urban planning, public services and location-based recommender systems and other purposes.
ADASECANT: Robust Adaptive Secant Method for Stochastic Gradient
Venue: arXiv cs.LG 2015
Year: 2015

Stochastic gradient algorithms have been the main focus of large-scale learning problems and they led to important successes in machine learning. The convergence of SGD depends on the careful choice of learning rate and the amount of the noise in stochastic estimates of the gradients. In this paper, we propose a new adaptive learning rate algorithm, which utilizes curvature information for automatically tuning the learning rates. The information about the element-wise curvature of the loss function is estimated from the local statistics of the stochastic first order gradients. We further propose a new variance reduction technique to speed up the convergence. In our preliminary experiments with deep neural networks, we obtained better performance compared to the popular stochastic gradient algorithms.