OpenRaiser/Intern-Atlas huggingface dataset:
Study of Parameterized-Chain networks
Venue: arXiv cs.FL 2016
Year: 2016

In areas such as computer software and hardware, manufacturing systems, and transportation, engineers encounter networks with arbitrarily large numbers of isomorphic subprocesses. Parameterized systems provide a framework for modeling such networks. The analysis of parameterized systems is a challenge as some key properties such as nonblocking and deadlock-freedom are undecidable even for the case of a parameterized system with ring topology. In this paper, we introduce \textit{Parameterized-Chain Networks} (PCN) for modeling of networks containing several linear parameterized segments. Since deadlock analysis is undecidable, to achieve a tractable subproblem we limit the behavior of subprocesses of the network using our previously developed mathematical notion `weak invariant simulation.' We develop a dependency graph for analysis of PCN and show that partial and total deadlocks of the proposed PCN are characterized by full, consistent subgraphs of the dependency graph. We investigate deadlock in a traffic network as an illustrative example. This document contains all the details and proofs of the study.
Analysis of Exact and Approximated Epidemic Models over Complex Networks
Venue: arXiv cs.SI 2016
Year: 2016

We study the spread of discrete-time epidemics over arbitrary networks for well-known propagation models, namely SIS (susceptible-infected-susceptible), SIR (susceptible-infected-recovered), SIRS (susceptible-infected-recovered-susceptible) and SIV (susceptible-infected-vaccinated). Such epidemics are described by $2^n$- or $3^n$-state Markov chains. Ostensibly, because analyzing such Markov chains is too complicated, their $O(n)$-dimensional nonlinear "mean-field" approximation, and its linearization, are often studied instead. We provide a complete global analysis of the epidemic dynamics of the nonlinear mean-field approximation. In particular, we show that depending on the largest eigenvalue of the underlying graph adjacency matrix and the rates of infection, recovery, and vaccination, the global dynamics takes on one of two forms: either the epidemic dies out, or it converges to another unique fixed point (the so-called endemic state where a constant fraction of the nodes remain infected). A similar result has also been shown in the continuous-time case. We tie in these results with the "true" underlying Markov chain model by showing that the linear model is the tightest upper-bound on the true probabilities of infection that involves only marginals, and that, even though the nonlinear model is not an upper-bound on the true probabilities in general, it does provide an upper-bound on the probability of the chain not being absorbed. As a consequence, we also show that when the disease-free fixed point is globally stable for the mean-field model, the Markov chain has an $O(\log n)$ mixing time, which means the epidemic dies out quickly. We compare and summarize the results on different propagation models.
A Near-Quadratic Lower Bound for the Size of Quantum Circuits of Constant Treewidth
Venue: arXiv cs.CC 2016
Year: 2016

We show that any quantum circuit of treewidth $t$, built from $r$-qubit gates, requires at least $Ω(\frac{n^{2}}{2^{O(r\cdot t)}\cdot \log^4 n})$ gates to compute the element distinctness function. Our result generalizes a near-quadratic lower bound for quantum formula size obtained by Roychowdhury and Vatan [SIAM J. on Computing, 2001]. The proof of our lower bound follows by an extension of Nečiporuk's method to the context of quantum circuits of constant treewidth. This extension is made via a combination of techniques from structural graph theory, tensor-network theory, and the connected-component counting method, which is a classic tool in algebraic geometry.
On Identification of Sparse Multivariable ARX Model: A Sparse Bayesian Learning Approach
Venue: arXiv cs.SY 2016
Year: 2016

This paper begins with considering the identification of sparse linear time-invariant networks described by multivariable ARX models. Such models possess relatively simple structure thus used as a benchmark to promote further research. With identifiability of the network guaranteed, this paper presents an identification method that infers both the Boolean structure of the network and the internal dynamics between nodes. Identification is performed directly from data without any prior knowledge of the system, including its order. The proposed method solves the identification problem using Maximum a posteriori estimation (MAP) but with inseparable penalties for complexity, both in terms of element (order of nonzero connections) and group sparsity (network topology). Such an approach is widely applied in Compressive Sensing (CS) and known as Sparse Bayesian Learning (SBL). We then propose a novel scheme that combines sparse Bayesian and group sparse Bayesian to efficiently solve the problem. The resulted algorithm has a similar form of the standard Sparse Group Lasso (SGL) while with known noise variance, it simplifies to exact re-weighted SGL. The method and the developed toolbox can be applied to infer networks from a wide range of fields, including systems biology applications such as signaling and genetic regulatory networks.
Soft Cache Hits and the Impact of Alternative Content Recommendations on Mobile Edge Caching
Venue: arXiv cs.NI 2016
Year: 2016

Caching popular content at the edge of future mobile networks has been widely considered in order to alleviate the impact of the data tsunami on both the access and backhaul networks. A number of interesting techniques have been proposed, including femto-caching and "delayed" or opportunistic cache access. Nevertheless, the majority of these approaches suffer from the rather limited storage capacity of the edge caches, compared to the tremendous and rapidly increasing size of the Internet content catalog. We propose to depart from the assumption of hard cache misses, common in most existing works, and consider "soft" cache misses, where if the original content is not available, an alternative content that is locally cached can be recommended. Given that Internet content consumption is increasingly entertainment-oriented, we believe that a related content could often lead to complete or at least partial user satisfaction, without the need to retrieve the original content over expensive links. In this paper, we formulate the problem of optimal edge caching with soft cache hits, in the context of delayed access, and analyze the expected gains. We then show using synthetic and real datasets of related video contents that promising caching gains could be achieved in practice.
Training a Feedback Loop for Hand Pose Estimation
Venue: arXiv cs.CV 2016
Year: 2016

We propose an entirely data-driven approach to estimating the 3D pose of a hand given a depth image. We show that we can correct the mistakes made by a Convolutional Neural Network trained to predict an estimate of the 3D pose by using a feedback loop. The components of this feedback loop are also Deep Networks, optimized using training data. They remove the need for fitting a 3D model to the input data, which requires both a carefully designed fitting function and algorithm. We show that our approach outperforms state-of-the-art methods, and is efficient as our implementation runs at over 400 fps on a single GPU.
Jolie Community on the Rise
Venue: arXiv cs.PL 2016
Year: 2016

Jolie is a programming language that follows the microservices paradigm. As an open source project, it has built a community of developers worldwide - both in the industry as well as in academia - taken care of the development, continuously improved its usability, and therefore broadened the adoption. In this paper, we present some of the most recent results and work in progress that has been made within our research team.
Graphs, Ideal Flow, and the Transportation Network
Venue: arXiv cs.DM 2016
Year: 2016

This lecture discusses the mathematical relationship between network structure and network utilization of transportation network. Network structure means the graph itself. Network utilization represent the aggregation of trajectories of agents in using the network graph. I show the similarity and relationship between the structural pattern of the network and network utilization.
The multi-stripe travelling salesman problem
Venue: arXiv cs.DM 2016
Year: 2016

In the classical Travelling Salesman Problem (TSP), the objective function sums the costs for travelling from one city to the next city along the tour. In the q-stripe TSP with q larger than 1, the objective function sums the costs for travelling from one city to each of the next q cities along the tour. The resulting q-stripe TSP generalizes the TSP and forms a special case of the quadratic assignment problem. We analyze the computational complexity of the q-stripe TSP for various classes of specially structured distance matrices. We derive NP-hardness results as well as polyomially solvable cases. One of our main results generalizes a well-known theorem of Kalmanson from the classical TSP to the q-stripe TSP.
Very Deep Convolutional Neural Networks for Raw Waveforms
Venue: arXiv cs.SD 2016
Year: 2016

Learning acoustic models directly from the raw waveform data with minimal processing is challenging. Current waveform-based models have generally used very few (~2) convolutional layers, which might be insufficient for building high-level discriminative features. In this work, we propose very deep convolutional neural networks (CNNs) that directly use time-domain waveforms as inputs. Our CNNs, with up to 34 weight layers, are efficient to optimize over very long sequences (e.g., vector of size 32000), necessary for processing acoustic waveforms. This is achieved through batch normalization, residual learning, and a careful design of down-sampling in the initial layers. Our networks are fully convolutional, without the use of fully connected layers and dropout, to maximize representation learning. We use a large receptive field in the first convolutional layer to mimic bandpass filters, but very small receptive fields subsequently to control the model capacity. We demonstrate the performance gains with the deeper models. Our evaluation shows that the CNN with 18 weight layers outperform the CNN with 3 weight layers by over 15% in absolute accuracy for an environmental sound recognition task and matches the performance of models using log-mel features.
Improving Comparison Shopping Agents' Competence through Selective Price Disclosure
Venue: arXiv cs.GT 2016
Year: 2016

The plethora of comparison shopping agents (CSAs) in today's markets enables buyers to query more than a single CSA when shopping, and an inter-CSAs competition naturally arises. We suggest a new approach, termed "selective price disclosure", which improves the attractiveness of a CSA by removing some of the prices in the outputted list. The underlying idea behind this approach is to affect the buyer's beliefs regarding the chance of obtaining more attractive prices. The paper presents two methods, which are suitable for fully-rational buyers, for deciding which prices among those known to the CSA should be disclosed. The effectiveness and efficiency of the methods are evaluated using real data collected from five CSAs. The methods are also evaluated with human subjects, showing that selective price disclosure can be highly effective in this case as well, however, the disclosed subset of prices should be extracted in a different (simplistic) manner.
Sentiment Analysis on Bangla and Romanized Bangla Text (BRBT) using Deep Recurrent models
Venue: arXiv cs.CL 2016
Year: 2016

Sentiment Analysis (SA) is an action research area in the digital age. With rapid and constant growth of online social media sites and services, and the increasing amount of textual data such as - statuses, comments, reviews etc. available in them, application of automatic SA is on the rise. However, most of the research works on SA in natural language processing (NLP) are based on English language. Despite being the sixth most widely spoken language in the world, Bangla still does not have a large and standard dataset. Because of this, recent research works in Bangla have failed to produce results that can be both comparable to works done by others and reusable as stepping stones for future researchers to progress in this field. Therefore, we first tried to provide a textual dataset - that includes not just Bangla, but Romanized Bangla texts as well, is substantial, post-processed and multiple validated, ready to be used in SA experiments. We tested this dataset in Deep Recurrent model, specifically, Long Short Term Memory (LSTM), using two types of loss functions - binary crossentropy and categorical crossentropy, and also did some experimental pre-training by using data from one validation to pre-train the other and vice versa. Lastly, we documented the results along with some analysis on them, which were promising.
End-to-End Radio Traffic Sequence Recognition with Deep Recurrent Neural Networks
Venue: arXiv cs.LG 2016
Year: 2016

We investigate sequence machine learning techniques on raw radio signal time-series data. By applying deep recurrent neural networks we learn to discriminate between several application layer traffic types on top of a constant envelope modulation without using an expert demodulation algorithm. We show that complex protocol sequences can be learned and used for both classification and generation tasks using this approach.
Quantifying Urban Traffic Anomalies
Venue: arXiv cs.LG 2016
Year: 2016

Detecting and quantifying anomalies in urban traffic is critical for real-time alerting or re-routing in the short run and urban planning in the long run. We describe a two-step framework that achieves these two goals in a robust, fast, online, and unsupervised manner. First, we adapt stable principal component pursuit to detect anomalies for each road segment. This allows us to pinpoint traffic anomalies early and precisely in space. Then we group the road-level anomalies across time and space into meaningful anomaly events using a simple graph expansion procedure. These events can be easily clustered, visualized, and analyzed by urban planners. We demonstrate the effectiveness of our system using 7 weeks of anonymized and aggregated cellular location data in Dallas-Fort Worth. We suggest potential opportunities for urban planners and policy makers to use our methodology to make informed changes. These applications include real-time re-routing of traffic in response to abnormally high traffic, or identifying candidates for high-impact infrastructure projects.
CDSFA Stochastic Frontier Analysis Approach to Revenue Modeling in Large Cloud Data Centers
Venue: arXiv cs.DC 2016
Year: 2016

Enterprises are investing heavily in cloud data centers to meet the ever surging business demand. Data Center is a facility, which houses computer systems and associated components, such as telecommunications and storage systems. It generally includes power supply equipment, communication connections and cooling equipment. A large data center can use as much electricity as a small town. Due to the emergence of data center based computing services, it has become necessary to examine how the costs associated with data centers evolve over time, mainly in view of efficiency issues. We have presented a quasi form of Cobb Douglas model, which addresses revenue and profit issues in running large data centers. The stochastic form has been introduced and explored along with the quasi Cobb Douglas model to understand the behavior of the model in depth. Harrod neutrality and Solow neutrality are incorporated in the model to identify the technological progress in cloud data centers. This allows us to shed light on the stochastic uncertainty of cloud data center operations. A general approach to optimizing the revenue cost of data centers using Cobb Douglas Stochastic Frontier Analysis,CDSFA is presented. Next, we develop the optimization model for large data centers. The mathematical basis of CDSFA has been utilized for cost optimization and profit maximization in data centers. The results are found to be quite useful in view of production reorganization in large data centers around the world.
Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updates
Venue: arXiv cs.RO 2016
Year: 2016

Reinforcement learning holds the promise of enabling autonomous robots to learn large repertoires of behavioral skills with minimal human intervention. However, robotic applications of reinforcement learning often compromise the autonomy of the learning process in favor of achieving training times that are practical for real physical systems. This typically involves introducing hand-engineered policy representations and human-supplied demonstrations. Deep reinforcement learning alleviates this limitation by training general-purpose neural network policies, but applications of direct deep reinforcement learning algorithms have so far been restricted to simulated settings and relatively simple tasks, due to their apparent high sample complexity. In this paper, we demonstrate that a recent deep reinforcement learning algorithm based on off-policy training of deep Q-functions can scale to complex 3D manipulation tasks and can learn deep neural network policies efficiently enough to train on real physical robots. We demonstrate that the training times can be further reduced by parallelizing the algorithm across multiple robots which pool their policy updates asynchronously. Our experimental evaluation shows that our method can learn a variety of 3D manipulation skills in simulation and a complex door opening skill on real robots without any prior demonstrations or manually designed representations.
Darwini: Generating realistic large-scale social graphs
Venue: arXiv cs.SI 2016
Year: 2016

Synthetic graph generators facilitate research in graph algorithms and processing systems by providing access to data, for instance, graphs resembling social networks, while circumventing privacy and security concerns. Nevertheless, their practical value lies in their ability to capture important metrics of real graphs, such as degree distribution and clustering properties. Graph generators must also be able to produce such graphs at the scale of real-world industry graphs, that is, hundreds of billions or trillions of edges. In this paper, we propose Darwini, a graph generator that captures a number of core characteristics of real graphs. Importantly, given a source graph, it can reproduce the degree distribution and, unlike existing approaches, the local clustering coefficient and joint-degree distributions. Furthermore, Darwini maintains metrics such node PageRank, eigenvalues and the K-core decomposition of a source graph. Comparing Darwini with state-of-the-art generative models, we show that it can reproduce these characteristics more accurately. Finally, we provide an open source implementation of our approach on the vertex-centric Apache Giraph model that allows us to create synthetic graphs with one trillion edges.
Collective Robot Reinforcement Learning with Distributed Asynchronous Guided Policy Search
Venue: arXiv cs.LG 2016
Year: 2016

In principle, reinforcement learning and policy search methods can enable robots to learn highly complex and general skills that may allow them to function amid the complexity and diversity of the real world. However, training a policy that generalizes well across a wide range of real-world conditions requires far greater quantity and diversity of experience than is practical to collect with a single robot. Fortunately, it is possible for multiple robots to share their experience with one another, and thereby, learn a policy collectively. In this work, we explore distributed and asynchronous policy learning as a means to achieve generalization and improved training times on challenging, real-world manipulation tasks. We propose a distributed and asynchronous version of Guided Policy Search and use it to demonstrate collective policy learning on a vision-based door opening task using four robots. We show that it achieves better generalization, utilization, and training times than the single robot alternative.
Phase-Mapper: An AI Platform to Accelerate High Throughput Materials Discovery
Venue: arXiv cs.AI 2016
Year: 2016

High-Throughput materials discovery involves the rapid synthesis, measurement, and characterization of many different but structurally-related materials. A key problem in materials discovery, the phase map identification problem, involves the determination of the crystal phase diagram from the materials' composition and structural characterization data. We present Phase-Mapper, a novel AI platform to solve the phase map identification problem that allows humans to interact with both the data and products of AI algorithms, including the incorporation of human feedback to constrain or initialize solutions. Phase-Mapper affords incorporation of any spectral demixing algorithm, including our novel solver, AgileFD, which is based on a convolutive non-negative matrix factorization algorithm. AgileFD can incorporate constraints to capture the physics of the materials as well as human feedback. We compare three solver variants with previously proposed methods in a large-scale experiment involving 20 synthetic systems, demonstrating the efficacy of imposing physical constrains using AgileFD. Phase-Mapper has also been used by materials scientists to solve a wide variety of phase diagrams, including the previously unsolved Nb-Mn-V oxide system, which is provided here as an illustrative example.
Adaptive Neuron Apoptosis for Accelerating Deep Learning on Large Scale Systems
Venue: arXiv cs.NE 2016
Year: 2016

We present novel techniques to accelerate the convergence of Deep Learning algorithms by conducting low overhead removal of redundant neurons -- apoptosis of neurons -- which do not contribute to model learning, during the training phase itself. We provide in-depth theoretical underpinnings of our heuristics (bounding accuracy loss and handling apoptosis of several neuron types), and present the methods to conduct adaptive neuron apoptosis. Specifically, we are able to improve the training time for several datasets by 2-3x, while reducing the number of parameters by up to 30x (4-5x on average) on datasets such as ImageNet classification. For the Higgs Boson dataset, our implementation improves the accuracy (measured by Area Under Curve (AUC)) for classification from 0.88/1 to 0.94/1, while reducing the number of parameters by 3x in comparison to existing literature. The proposed methods achieve a 2.44x speedup in comparison to the default (no apoptosis) algorithm.
Economical Energy Efficiency E3: An Advanced Performance Metric for 5G Systems
Venue: arXiv cs.IT 2016
Year: 2016

The performances of the fifth generation (5G) wireless communication systems are significantly affected by edge cache and transport network. These emerging components bring substantial costs of the placement and utilization, and the evaluation of the cost impact is beyond the capability of traditional performance metrics, including spectral efficiency (SE) and energy efficiency (EE). In this article, economical energy efficiency (E3) is proposed, whose core idea is to take SE/EE and cost into account to evaluate comprehensive gains when different kinds of advanced technologies are used in 5G systems. The E3results are shown when the transport network and edge cache are separately or jointly used. Open issues in terms of modeling the cost, E3optimization based radio resource allocation, and E3optimization for internet of things, are identified as well.