OpenRaiser/Intern-Atlas huggingface dataset:
Risk Assessment of Multi-timescale Cascading Outages based on Markovian Tree Search
Venue: arXiv cs.SY 2016
Year: 2016

In the risk assessment of cascading outages, the rationality of simulation and efficiency of computation are both of great significance. To overcome the drawback of sampling-based methods that huge computation resources are required and the shortcoming of initial contingency selection practices that the dependencies in sequences of outages are omitted, this paper proposes a novel risk assessment approach by searching on Markovian Tree. The Markovian tree model is reformulated from the quasi-dynamic multi-timescale simulation model proposed recently to ensure reasonable modeling and simulation of cascading outages. Then a tree search scheme is established to avoid duplicated simulations on same cascade paths, significantly saving computation time. To accelerate the convergence of risk assessment, a risk estimation index is proposed to guide the search for states with major contributions to the risk, and the risk assessment is realized based on the risk estimation index with a forward tree search and backward update algorithm. The effectiveness of the proposed method is illustrated on a 4-node power system, and its convergence profile as well as efficiency is demonstrated on the RTS-96 test system.
Asymptotically Optimal Distributed Channel Allocation: a Competitive Game-Theoretic Approach
Venue: arXiv cs.GT 2016
Year: 2016

In this paper we consider the problem of distributed channel allocation in large networks under the frequency-selective interference channel. Performance is measured by the weighted sum of achievable rates. First we present a natural non-cooperative game theoretic formulation for this problem. It is shown that, when interference is sufficiently strong, this game has a pure price of anarchy approaching infinity with high probability, and there is an asymptotically increasing number of equilibria with the worst performance. Then we propose a novel non-cooperative M Frequency-Selective Interference Game (M-FSIG), where users limit their utility such that it is greater than zero only for their M best channels, and equal for them. We show that the M-FSIG exhibits, with high probability, an increasing number of optimal pure Nash equilibria and no bad equilibria. Consequently, the pure price of anarchy converges to one in probability in any interference regime. In order to exploit these results algorithmically we propose a modified Fictitious Play algorithm that can be implemented distributedly. We carry out simulations that show its fast convergence to the proven pure Nash equilibria.
Construction of cyclic DNA codes over the Ring $\Z_4[u]/\langle u^2-1 \rangle $ Based on the deletion distance
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we develop the theory for constructing DNA cyclic codes of odd length over $R=\Z_4[u]/\langle u^2-1 \rangle$ based on the deletion distance. Firstly, we relate DNA pairs with a special 16 elements of ring $R$. Cyclic codes of odd length over $R$ satisfy the reverse constraint and the reverse-complement constraint are discussed in this paper. We also study the $GC$-content of these codes and their deletion distance. The paper concludes with some examples of cyclic DNA codes with $GC$-content and their respective deletion distance.
Learning Binary Codes and Binary Weights for Efficient Classification
Venue: arXiv cs.CV 2016
Year: 2016

This paper proposes a generic formulation that significantly expedites the training and deployment of image classification models, particularly under the scenarios of many image categories and high feature dimensions. As a defining property, our method represents both the images and learned classifiers using binary hash codes, which are simultaneously learned from the training data. Classifying an image thereby reduces to computing the Hamming distance between the binary codes of the image and classifiers and selecting the class with minimal Hamming distance. Conventionally, compact hash codes are primarily used for accelerating image search. Our work is first of its kind to represent classifiers using binary codes. Specifically, we formulate multi-class image classification as an optimization problem over binary variables. The optimization alternatively proceeds over the binary classifiers and image hash codes. Profiting from the special property of binary codes, we show that the sub-problems can be efficiently solved through either a binary quadratic program (BQP) or linear program. In particular, for attacking the BQP problem, we propose a novel bit-flipping procedure which enjoys high efficacy and local optimality guarantee. Our formulation supports a large family of empirical loss functions and is here instantiated by exponential / hinge losses. Comprehensive evaluations are conducted on several representative image benchmarks. The experiments consistently observe reduced complexities of model training and deployment, without sacrifice of accuracies.
Turbo-Equalization Using Partial Gaussian Approximation
Venue: arXiv cs.IT 2016
Year: 2016

This paper deals with turbo-equalization for coded data transmission over intersymbol interference (ISI) channels. We propose a message-passing algorithm that uses the expectation-propagation rule to convert messages passed from the demodulator-decoder to the equalizer and computes messages returned by the equalizer by using a partial Gaussian approximation (PGA). Results from Monte Carlo simulations show that this approach leads to a significant performance improvement compared to state-of-the-art turbo-equalizers and allows for trading performance with complexity. We exploit the specific structure of the ISI channel model to significantly reduce the complexity of the PGA compared to that considered in the initial paper proposing the method.
Top-$K$ Ranking from Pairwise Comparisons: When Spectral Ranking is Optimal
Venue: arXiv cs.LG 2016
Year: 2016

We explore the top-$K$ rank aggregation problem. Suppose a collection of items is compared in pairs repeatedly, and we aim to recover a consistent ordering that focuses on the top-$K$ ranked items based on partially revealed preference information. We investigate the Bradley-Terry-Luce model in which one ranks items according to their perceived utilities modeled as noisy observations of their underlying true utilities. Our main contributions are two-fold. First, in a general comparison model where item pairs to compare are given a priori, we attain an upper and lower bound on the sample size for reliable recovery of the top-$K$ ranked items. Second, more importantly, extending the result to a random comparison model where item pairs to compare are chosen independently with some probability, we show that in slightly restricted regimes, the gap between the derived bounds reduces to a constant factor, hence reveals that a spectral method can achieve the minimax optimality on the (order-wise) sample size required for top-$K$ ranking. That is to say, we demonstrate a spectral method alone to be sufficient to achieve the optimality and advantageous in terms of computational complexity, as it does not require an additional stage of maximum likelihood estimation that a state-of-the-art scheme employs to achieve the optimality. We corroborate our main results by numerical experiments.
Order-Invariant Types and Their Applications
Venue: arXiv cs.LO 2016
Year: 2016

Our goal is to show that the standard model-theoretic concept of types can be applied in the study of order-invariant properties, i.e., properties definable in a logic in the presence of an auxiliary order relation, but not actually dependent on that order relation. This is somewhat surprising since order-invariant properties are more of a combinatorial rather than a logical object. We provide two applications of this notion. One is a proof, from the basic principles, of a theorem by Courcelle stating that over trees, order-invariant MSO properties are expressible in MSO with counting quantifiers. The other is an analog of the Feferman-Vaught theorem for order-invariant properties.
The landscape of software failure cause models
Venue: arXiv cs.SE 2016
Year: 2016

The software engineering field has a long history of classifying software failure causes. Understanding them is paramount for fault injection, focusing testing efforts or reliability prediction. Since software fails in manifold complex ways, a broad range of software failure cause models is meanwhile published in dependability literature. We present the results of a meta-study that classifies publications containing a software failure cause model in topic clusters. Our results structure the research field and can help to identify gaps. We applied the systematic mapping methodology for performing a repeatable analysis. We identified 156 papers presenting a model of software failure causes. Their examination confirms the assumption that a large number of the publications discusses source code defects only. Models of fault-activating state conditions and error states are rare. Research seems to be driven mainly by the need for better testing methods and code-based quality improvement. Other motivations such as online error detection are less frequently given. Mostly, the IEEE definitions or orthogonal defect classification is used as base terminology. The majority of use cases comes from web, safety- and security-critical applications.
Grasping for a Purpose: Using Task Goals for Efficient Manipulation Planning
Venue: arXiv cs.RO 2016
Year: 2016

In this paper we propose an approach for efficient grasp selection for manipulation tasks of unknown objects. Even for simple tasks such as pick-and-place, a unique solution is rare to occur. Rather, multiple candidate grasps must be considered and (potentially) tested till a successful, kinematically feasible path is found. To make this process efficient, the grasps should be ordered such that those more likely to succeed are tested first. We propose to use grasp manipulability as a metric to prioritize grasps. We present results of simulation experiments which demonstrate the usefulness of our metric. Additionally, we present experiments with our physical robot performing simple manipulation tasks with a small set of different household objects.
Simple and Accurate Dependency Parsing Using Bidirectional LSTM Feature Representations
Venue: arXiv cs.CL 2016
Year: 2016

We present a simple and effective scheme for dependency parsing which is based on bidirectional-LSTMs (BiLSTMs). Each sentence token is associated with a BiLSTM vector representing the token in its sentential context, and feature vectors are constructed by concatenating a few BiLSTM vectors. The BiLSTM is trained jointly with the parser objective, resulting in very effective feature extractors for parsing. We demonstrate the effectiveness of the approach by applying it to a greedy transition-based parser as well as to a globally optimized graph-based parser. The resulting parsers have very simple architectures, and match or surpass the state-of-the-art accuracies on English and Chinese.
Symbolic Reachability Analysis of B through ProB and LTSmin
Venue: arXiv cs.SE 2016
Year: 2016

We present a symbolic reachability analysis approach for B that can provide a significant speedup over traditional explicit state model checking. The symbolic analysis is implemented by linking ProB to LTSmin, a high-performance language independent model checker. The link is achieved via LTSmin's PINS interface, allowing ProB to benefit from LTSmin's analysis algorithms, while only writing a few hundred lines of glue-code, along with a bridge between ProB and C using ZeroMQ. ProB supports model checking of several formal specification languages such as B, Event-B, Z and TLA. Our experiments are based on a wide variety of B-Method and Event-B models to demonstrate the efficiency of the new link. Among the tested categories are state space generation and deadlock detection; but action detection and invariant checking are also feasible in principle. In many cases we observe speedups of several orders of magnitude. We also compare the results with other approaches for improving model checking, such as partial order reduction or symmetry reduction. We thus provide a new scalable, symbolic analysis algorithm for the B-Method and Event-B, along with a platform to integrate other model checking improvements via LTSmin in the future.
The Road to Popularity: The Dilution of Growing Audience on Twitter
Venue: arXiv cs.SI 2016
Year: 2016

On social media platforms, like Twitter, users are often interested in gaining more influence and popularity by growing their set of followers, aka their audience. Several studies have described the properties of users on Twitter based on static snapshots of their follower network. Other studies have analyzed the general process of link formation. Here, rather than investigating the dynamics of this process itself, we study how the characteristics of the audience and follower links change as the audience of a user grows in size on the road to user's popularity. To begin with, we find that the early followers tend to be more elite users than the late followers, i.e., they are more likely to have verified and expert accounts. Moreover, the early followers are significantly more similar to the person that they follow than the late followers. Namely, they are more likely to share time zone, language, and topics of interests with the followed user. To some extent, these phenomena are related with the growth of Twitter itself, wherein the early followers tend to be the early adopters of Twitter, while the late followers are late adopters. We isolate, however, the effect of the growth of audiences consisting of followers from the growth of Twitter's user base itself. Finally, we measure the engagement of such audiences with the content of the followed user, by measuring the probability that an early or late follower becomes a retweeter.
On the Efficiency of the Information Networks in Social Media
Venue: arXiv cs.SI 2016
Year: 2016

Social media sites are information marketplaces, where users produce and consume a wide variety of information and ideas. In these sites, users typically choose their information sources, which in turn determine what specific information they receive, how much information they receive and how quickly this information is shown to them. In this context, a natural question that arises is how efficient are social media users at selecting their information sources. In this work, we propose a computational framework to quantify users' efficiency at selecting information sources. Our framework is based on the assumption that the goal of users is to acquire a set of unique pieces of information. To quantify user's efficiency, we ask if the user could have acquired the same pieces of information from another set of sources more efficiently. We define three different notions of efficiency -- link, in-flow, and delay -- corresponding to the number of sources the user follows, the amount of (redundant) information she acquires and the delay with which she receives the information. Our definitions of efficiency are general and applicable to any social media system with an underlying information network, in which every user follows others to receive the information they produce. In our experiments, we measure the efficiency of Twitter users at acquiring different types of information. We find that Twitter users exhibit sub-optimal efficiency across the three notions of efficiency, although they tend to be more efficient at acquiring non-popular than popular pieces of information. We then show that this lack of efficiency is a consequence of the triadic closure mechanism by which users typically discover and follow other users in social media. Finally, we develop a heuristic algorithm that enables users to be significantly more efficient at acquiring the same unique pieces of information.
Particle Gaussian Mixture (PGM) Filters
Venue: arXiv cs.SY 2016
Year: 2016

Recursive estimation of nonlinear dynamical systems is an important problem that arises in several engineering applications. Consistent and accurate propagation of uncertainties is important to ensuring good estimation performance. It is well known that the posterior state estimates in nonlinear problems may assume non-Gaussian multimodal densities. In the past, Gaussian mixture filters and particle filters were introduced to handle non-Gaussianity and nonlinearity. However, these methods have seen only limited success as most mixture filters attempt to fix the number of mixture modes during estimation process, and the particle filters suffer from the curse of dimensionality. In this paper, we propose a particle based Gaussian mixture filtering approach for the general nonlinear estimation problem that is free of the particle depletion problem inherent to most particle filters. We employ an ensemble of randomly sampled states for the propagation of state probability density. A Gaussian mixture model of the propagated uncertainty is then recovered by clustering the ensemble. The posterior density is obtained subsequently through a Kalman measurement update of the mixture modes. We prove the weak convergence of the PGM density to the true filter density assuming exponential forgetting of initial conditions by the true filter. The estimation performance of the proposed filtering approach is demonstrated through several test cases.
Effects of human factor on the success of Information technology outsourcing
Venue: arXiv cs.HC 2016
Year: 2016

Information technology outsourcing is one of the factors affecting the improvement of flexibility and dynamics of enterprises in the competitive environment. Also the study of the factors affecting its success has been always considered by business owners and the area of research. Professional experiences and research results consider that the success of IT "Information technology" outsourcing projects relates to the effective knowledge transfer and human factors. The human factors are influenced by the cultural and environmental context of the inside and outside of the organization. Hence, it is necessary to study the effectiveness of these variables in different cultural environments. This study investigates the effect of human factors including the customer motivation and vendor willingness on the success of IT outsourcing projects. For this purpose, the research hypotheses were developed and analyzed by the structural equation method. The result of a field study among 94 companies and organizations show the difference of the findings of this study with earlier findings in other countries. Based on the findings, the client motivation does not affect the knowledge transfer but the vendor willingness affects the customer motivation to knowledge transfer. This result can help the business owners to take appropriate approaches for achieving success in IT outsourcing projects.
Generalized threshold-based epidemics in random graphs: the power of extreme values
Venue: arXiv cs.SI 2016
Year: 2016

Bootstrap percolation is a well-known activation process in a graph, in which a node becomes active when it has at least $r$ active neighbors. Such process, originally studied on regular structures, has been recently investigated also in the context of random graphs, where it can serve as a simple model for a wide variety of cascades, such as the spreading of ideas, trends, viral contents, etc. over large social networks. In particular, it has been shown that in $G(n,p)$ the final active set can exhibit a phase transition for a sub-linear number of seeds. In this paper, we propose a unique framework to study similar sub-linear phase transitions for a much broader class of graph models and epidemic processes. Specifically, we consider i) a generalized version of bootstrap percolation in $G(n,p)$ with random activation thresholds and random node-to-node influences; ii) different random graph models, including graphs with given degree sequence and graphs with community structure (block model). The common thread of our work is to show the surprising sensitivity of the critical seed set size to extreme values of distributions, which makes some systems dramatically vulnerable to large-scale outbreaks. We validate our results running simulation on both synthetic and real graphs.
Cooperative Device-to-Device Communications With Caching
Venue: arXiv cs.IT 2016
Year: 2016

Device-to-Device (D2D) communications can increase the throughput of cellular networks significantly, where the interference among D2D links should be properly managed. In this paper, we propose an opportunistic cooperative D2D transmission strategy by exploiting the caching capability at the users to deal with the interference among D2D links. To increase the cooperative opportunity and improve spatial reuse gain, we divide the D2D users into clusters and cache different popular files at the users within a cluster, and then find the optimal cluster size. To maximize the network throughput, we assign different frequency bands to cooperative and non-cooperative D2D links and optimize the bandwidth partition. Simulation results demonstrate that the proposed strategy can provide 500%-600% throughput gain over existing cache-enabled D2D communications when the popularity distribution is skewed, and can provide 40%-80% gain even when the popularity distribution is uniform.
Efficient Global Point Cloud Alignment using Bayesian Nonparametric Mixtures
Venue: arXiv cs.CV 2016
Year: 2016

Point cloud alignment is a common problem in computer vision and robotics, with applications ranging from 3D object recognition to reconstruction. We propose a novel approach to the alignment problem that utilizes Bayesian nonparametrics to describe the point cloud and surface normal densities, and branch and bound (BB) optimization to recover the relative transformation. BB uses a novel, refinable, near-uniform tessellation of rotation space using 4D tetrahedra, leading to more efficient optimization compared to the common axis-angle tessellation. We provide objective function bounds for pruning given the proposed tessellation, and prove that BB converges to the optimum of the cost function along with providing its computational complexity. Finally, we empirically demonstrate the efficiency of the proposed approach as well as its robustness to real-world conditions such as missing data and partial overlap.