OpenRaiser/Intern-Atlas huggingface dataset:
Output Average Consensus Over Heterogeneous Multi-Agent Systems via Two-Level Approach
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, a novel two-level framework was proposed and applied to solve the output average consensus problem over heterogeneous multi-agent systems. This approach is mainly based on the recent technique of system abstraction. For given multi-agent systems, we first constructed their abstractions as the upper level and solved their average consensus problem by leveraging well-known results for single integrators. Then the control protocols for physical agents in the lower level were synthesized in a hierarchical way by embedding the designed law for abstractions into an interface between two levels. In this way, the complexity coming from heterogeneous dynamics of agents is totally decoupled from that of the coordination task and the communication topologies. An example was given to show its effectiveness.
Benford's law: a 'sleeping beauty' sleeping in the dirty pages of logarithmic tables
Venue: arXiv cs.DL 2017
Year: 2017

Benford's law is an empirical observation, first reported by Simon Newcomb in 1881 and then independently by Frank Benford in 1938: the first significant digits of numbers in large data are often distributed according to a logarithmically decreasing function. Being contrary to intuition, the law was forgotten as a mere curious observation. However, in the last two decades, relevant literature has grown exponentially, - an evolution typical of "Sleeping Beauties" (SBs) publications that go unnoticed (sleep) for a long time and then suddenly become center of attention (are awakened). Thus, in the present study, we show that Newcomb (1881) and Benford (1938) papers are clearly SBs. The former was in deep sleep for 110 years whereas the latter was in deep sleep for a comparatively lesser period of 31 years up to 1968, and in a state of less deep sleep for another 27 years up to 1995. Both SBs were awakened in the year 1995 by Hill (1995a). In so doing, we show that the waking prince (Hill, 1995a) is more often quoted than the SB whom he kissed, - in this Benford's law case, wondering whether this is a general effect, - to be usefully studied.
The temporalized Massey's method
Venue: arXiv cs.SI 2017
Year: 2017

We propose and throughly investigate a temporalized version of the popular Massey's technique for rating actors in sport competitions. The method can be described as a dynamic temporal process in which team ratings are updated at every match according to their performance during the match and the strength of the opponent team. Using the Italian soccer dataset, we empirically show that the method has a good foresight prediction accuracy.
A Fast and Compact Saliency Score Regression Network Based on Fully Convolutional Network
Venue: arXiv cs.CV 2017
Year: 2017

Visual saliency detection aims at identifying the most visually distinctive parts in an image, and serves as a pre-processing step for a variety of computer vision and image processing tasks. To this end, the saliency detection procedure must be as fast and compact as possible and optimally processes input images in a real time manner. It is an essential application requirement for the saliency detection task. However, contemporary detection methods often utilize some complicated procedures to pursue feeble improvements on the detection precession, which always take hundreds of milliseconds and make them not easy to be applied practically. In this paper, we tackle this problem by proposing a fast and compact saliency score regression network which employs fully convolutional network, a special deep convolutional neural network, to estimate the saliency of objects in images. It is an extremely simplified end-to-end deep neural network without any pre-processings and post-processings. When given an image, the network can directly predict a dense full-resolution saliency map (image-to-image prediction). It works like a compact pipeline which effectively simplifies the detection procedure. Our method is evaluated on six public datasets, and experimental results show that it can achieve comparable or better precision performance than the state-of-the-art methods while get a significant improvement in detection speed (35 FPS, processing in real time).
Sensitivity Analysis of Expensive Black-Box Systems Using Metamodeling
Venue: arXiv cs.OH 2017
Year: 2017

Simulations are becoming ever more common as a tool for designing complex products. Sensitivity analysis techniques can be applied to these simulations to gain insight, or to reduce the complexity of the problem at hand. However, these simulators are often expensive to evaluate and sensitivity analysis typically requires a large amount of evaluations. Metamodeling has been successfully applied in the past to reduce the amount of required evaluations for design tasks such as optimization and design space exploration. In this paper, we propose a novel sensitivity analysis algorithm for variance and derivative based indices using sequential sampling and metamodeling. Several stopping criteria are proposed and investigated to keep the total number of evaluations minimal. The results show that both variance and derivative based techniques can be accurately computed with a minimal amount of evaluations using fast metamodels and FLOLA-Voronoi or density sequential sampling algorithms.
HoNVis: Visualizing and Exploring Higher-Order Networks
Venue: arXiv cs.GR 2017
Year: 2017

Unlike the conventional first-order network (FoN), the higher-order network (HoN) provides a more accurate description of transitions by creating additional nodes to encode higher-order dependencies. However, there exists no visualization and exploration tool for the HoN. For applications such as the development of strategies to control species invasion through global shipping which is known to exhibit higher-order dependencies, the existing FoN visualization tools are limited. In this paper, we present HoNVis, a novel visual analytics framework for exploring higher-order dependencies of the global ocean shipping network. Our framework leverages coordinated multiple views to reveal the network structure at three levels of detail (i.e., the global, local, and individual port levels). Users can quickly identify ports of interest at the global level and specify a port to investigate its higher-order nodes at the individual port level. Investigating a larger-scale impact is enabled through the exploration of HoN at the local level. Using the global ocean shipping network data, we demonstrate the effectiveness of our approach with a real-world use case conducted by domain experts specializing in species invasion. Finally, we discuss the generalizability of this framework to other real-world applications such as information diffusion in social networks and epidemic spreading through air transportation.
Two forms of minimality in ASPIC+
Venue: arXiv cs.AI 2017
Year: 2017

Many systems of structured argumentation explicitly require that the facts and rules that make up the argument for a conclusion be the minimal set required to derive the conclusion. ASPIC+ does not place such a requirement on arguments, instead requiring that every rule and fact that are part of an argument be used in its construction. Thus ASPIC+ arguments are minimal in the sense that removing any element of the argument would lead to a structure that is not an argument. In this brief note we discuss these two types of minimality and show how the first kind of minimality can, if desired, be recovered in ASPIC+.
Distributed Approximation Algorithms for the Multiple Knapsack Problem
Venue: arXiv cs.DS 2017
Year: 2017

We consider the distributed version of the Multiple Knapsack Problem (MKP), where $m$ items are to be distributed amongst $n$ processors, each with a knapsack. We propose different distributed approximation algorithms with a tradeoff between time and message complexities. The algorithms are based on the greedy approach of assigning the best item to the knapsack with the largest capacity. These algorithms obtain a solution with a bound of $\frac{1}{n+1}$ times the optimum solution, with either $\mathcal{O}\left(m\log n\right)$ time and $\mathcal{O}\left(m n\right)$ messages, or $\mathcal{O}\left(m\right)$ time and $\mathcal{O}\left(mn^{2}\right)$ messages.
An Introduction to Deep Learning for the Physical Layer
Venue: arXiv cs.IT 2017
Year: 2017

We present and discuss several novel applications of deep learning for the physical layer. By interpreting a communications system as an autoencoder, we develop a fundamental new way to think about communications system design as an end-to-end reconstruction task that seeks to jointly optimize transmitter and receiver components in a single process. We show how this idea can be extended to networks of multiple transmitters and receivers and present the concept of radio transformer networks as a means to incorporate expert domain knowledge in the machine learning model. Lastly, we demonstrate the application of convolutional neural networks on raw IQ samples for modulation classification which achieves competitive accuracy with respect to traditional schemes relying on expert features. The paper is concluded with a discussion of open challenges and areas for future investigation.
Guided Signal Reconstruction Theory
Venue: arXiv cs.IT 2017
Year: 2017

An axiomatic approach to signal reconstruction is formulated, involving a sample consistent set and a guiding set, describing desired reconstructions. New frame-less reconstruction methods are proposed, based on a novel concept of a reconstruction set, defined as a shortest pathway between the sample consistent set and the guiding set. Existence and uniqueness of the reconstruction set are investigated in a Hilbert space, where the guiding set is a closed subspace and the sample consistent set is a closed plane, formed by a sampling subspace. Connections to earlier known consistent, generalized, and regularized reconstructions are clarified. New stability and reconstruction error bounds are derived, using the largest nontrivial angle between the sampling and guiding subspaces. Conjugate gradient iterative reconstruction algorithms are proposed and illustrated numerically for image magnification.
Neural Feature Embedding for User Response Prediction in Real-Time Bidding (RTB)
Venue: arXiv cs.IR 2017
Year: 2017

In the area of ad-targeting, predicting user responses is essential for many applications such as Real-Time Bidding (RTB). Many of the features available in this domain are sparse categorical features. This presents a challenge especially when the user responses to be predicted are rare, because each feature will only have very few positive examples. Recently, neural embedding techniques such as word2vec which learn distributed representations of words using occurrence statistics in the corpus have been shown to be effective in many Natural Language Processing tasks. In this paper, we use real-world data set to show that a similar technique can be used to learn distributed representations of features from users' web history, and that such representations can be used to improve the accuracy of commonly used models for predicting rare user responses.
Seeded Laplaican: An Eigenfunction Solution for Scribble Based Interactive Image Segmentation
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we cast the scribble-based interactive image segmentation as a semi-supervised learning problem. Our novel approach alleviates the need to solve an expensive generalized eigenvector problem by approximating the eigenvectors using efficiently computed eigenfunctions. The smoothness operator defined on feature densities at the limit n tends to infinity recovers the exact eigenvectors of the graph Laplacian, where n is the number of nodes in the graph. To further reduce the computational complexity without scarifying our accuracy, we select pivots pixels from user annotations. In our experiments, we evaluate our approach using both human scribble and "robot user" annotations to guide the foreground/background segmentation. We developed a new unbiased collection of five annotated images datasets to standardize the evaluation procedure for any scribble-based segmentation method. We experimented with several variations, including different feature vectors, pivot count and the number of eigenvectors. Experiments are carried out on datasets that contain a wide variety of natural images. We achieve better qualitative and quantitative results compared to state-of-the-art interactive segmentation algorithms.
Structured Attention Networks
Venue: arXiv cs.CL 2017
Year: 2017

Attention networks have proven to be an effective approach for embedding categorical inference within a deep neural network. However, for many tasks we may want to model richer structural dependencies without abandoning end-to-end training. In this work, we experiment with incorporating richer structural distributions, encoded using graphical models, within deep networks. We show that these structured attention networks are simple extensions of the basic attention procedure, and that they allow for extending attention beyond the standard soft-selection approach, such as attending to partial segmentations or to subtrees. We experiment with two different classes of structured attention networks: a linear-chain conditional random field and a graph-based parsing model, and describe how these models can be practically implemented as neural network layers. Experiments show that this approach is effective for incorporating structural biases, and structured attention networks outperform baseline attention models on a variety of synthetic and real tasks: tree transduction, neural machine translation, question answering, and natural language inference. We further find that models trained in this way learn interesting unsupervised hidden representations that generalize simple attention.
An analysis of Bitcoin OP_RETURN metadata
Venue: arXiv cs.CR 2017
Year: 2017

The Bitcoin protocol allows to save arbitrary data on the blockchain through a special instruction of the scripting language, called OP_RETURN. A growing number of protocols exploit this feature to extend the range of applications of the Bitcoin blockchain beyond transfer of currency. A point of debate in the Bitcoin community is whether loading data through OP_RETURN can negatively affect the performance of the Bitcoin network with respect to its primary goal. This paper is an empirical study of the usage of OP_RETURN over the years. We identify several protocols based on OP_RETURN, which we classify by their application domain. We measure the evolution in time of the usage of each protocol, the distribution of OP_RETURN transactions by application domain, and their space consumption.
Semi-Supervised Spam Detection in Twitter Stream
Venue: arXiv cs.IR 2017
Year: 2017

Most existing techniques for spam detection on Twitter aim to identify and block users who post spam tweets. In this paper, we propose a Semi-Supervised Spam Detection (S3D) framework for spam detection at tweet-level. The proposed framework consists of two main modules: spam detection module operating in real-time mode, and model update module operating in batch mode. The spam detection module consists of four light-weight detectors: (i) blacklisted domain detector to label tweets containing blacklisted URLs, (ii) near-duplicate detector to label tweets that are near-duplicates of confidently pre-labeled tweets, (iii) reliable ham detector to label tweets that are posted by trusted users and that do not contain spammy words, and (iv) multi-classifier based detector labels the remaining tweets. The information required by the detection module are updated in batch mode based on the tweets that are labeled in the previous time window. Experiments on a large scale dataset show that the framework adaptively learns patterns of new spam activities and maintain good accuracy for spam detection in a tweet stream.
Polar Codes and Polar Lattices for the Heegard-Berger Problem
Venue: arXiv cs.IT 2017
Year: 2017

Explicit coding schemes are proposed to achieve the rate-distortion function of the Heegard-Berger problem using polar codes. Specifically, a nested polar code construction is employed to achieve the rate-distortion function for the doubly-symmetric binary sources when the side information may be absent. The nested structure contains two optimal polar codes for lossy source coding and channel coding, respectively. Moreover, a similar nested polar lattice construction is employed when the source and the side information are jointly Gaussian. The proposed polar lattice is constructed by nesting a quantization polar lattice and a capacity-achieving polar lattice for the additive white Gaussian noise channel.
Provably Efficient Algorithms for Joint Placement and Allocation of Virtual Network Functions
Venue: arXiv cs.NI 2017
Year: 2017

Network Function Virtualization (NFV) has the potential to significantly reduce the capital and operating expenses, shorten product release cycle, and improve service agility. In this paper, we focus on minimizing the total number of Virtual Network Function (VNF) instances to provide a specific service (possibly at different locations) to all the flows in a network. Certain network security and analytics applications may allow fractional processing of a flow at different nodes (corresponding to datacenters), giving an opportunity for greater optimization of resources. Through a reduction from the set cover problem, we show that this problem is NP-hard and cannot even be approximated within a factor of (1 - o(1)) ln(m) (where m is the number of flows) unless P=NP. Then, we design two simple greedy algorithms and prove that they achieve an approximation ratio of (1 - o(1)) ln(m) + 2, which is asymptotically optimal. For special cases where each node hosts multiple VNF instances (which is typically true in practice), we also show that our greedy algorithms have a constant approximation ratio. Further, for tree topologies we develop an optimal greedy algorithm by exploiting the inherent topological structure. Finally, we conduct extensive numerical experiments to evaluate the performance of our proposed algorithms in various scenarios.
Linking Mathematical Software in Web Archives
Venue: arXiv cs.DL 2017
Year: 2017

The Web is our primary source of all kinds of information today. This includes information about software as well as associated materials, like source code, documentation, related publications and change logs. Such data is of particular importance in research in order to conduct, comprehend and reconstruct scientific experiments that involve software. swMATH, a mathematical software directory, attempts to identify software mentions in scientific articles and provides additional information as well as links to the Web. However, just like software itself, the Web is dynamic and most likely the information on the Web has changed since it was referenced in a scientific publication. Therefore, it is crucial to preserve the resources of a software on the Web to capture its states over time. We found that around 40% of the websites in swMATH are already included in an existing Web archive. Out of these, 60% of contain some kind of documentation and around 45% even provide downloads of software artifacts. Hence, already today links can be established based on the publication dates of corresponding articles. The contained data enable enriching existing information with a temporal dimension. In the future, specialized infrastructure will improve the coverage of software resources and allow explicit references in scientific publications.
An Analysis of 1-to-First Matching in Iris Recognition
Venue: arXiv cs.CV 2017
Year: 2017

Iris recognition systems are a mature technology that is widely used throughout the world. In identification (as opposed to verification) mode, an iris to be recognized is typically matched against all N enrolled irises. This is the classic "1-to-N search". In order to improve the speed of large-scale identification, a modified "1-to-First" search has been used in some operational systems. A 1-to-First search terminates with the first below-threshold match that is found, whereas a 1-to-N search always finds the best match across all enrollments. We know of no previous studies that evaluate how the accuracy of 1-to-First search differs from that of 1-to-N search. Using a dataset of over 50,000 iris images from 2,800 different irises, we perform experiments to evaluate the relative accuracy of 1-to-First and 1-to-N search. We evaluate how the accuracy difference changes with larger numbers of enrolled irises, and with larger ranges of rotational difference allowed between iris images. We find that False Match error rate for 1-to-First is higher than for 1-to-N, and the the difference grows with larger number of enrolled irises and with larger range of rotation.
Sensing and Modeling Human Behavior Using Social Media and Mobile Data
Venue: arXiv cs.CY 2017
Year: 2017

In the past years we have witnessed the emergence of the new discipline of computational social science, which promotes a new data-driven and computation-based approach to social sciences. In this article we discuss how the availability of new technologies such as online social media and mobile smartphones has allowed researchers to passively collect human behavioral data at a scale and a level of granularity that were just unthinkable some years ago. We also discuss how these digital traces can then be used to prove (or disprove) existing theories and develop new models of human behavior.
Fuzzy Clustering Data Given on the Ordinal Scale Based on Membership and Likelihood Functions Sharing
Venue: arXiv cs.LG 2017
Year: 2017

A task of clustering data given in the ordinal scale under conditions of overlapping clusters has been considered. It's proposed to use an approach based on memberhsip and likelihood functions sharing. A number of performed experiments proved effectiveness of the proposed method. The proposed method is characterized by robustness to outliers due to a way of ordering values while constructing membership functions.
Geometric Biplane Graphs II: Graph Augmentation
Venue: arXiv cs.CG 2017
Year: 2017

We study biplane graphs drawn on a finite point set $S$ in the plane in general position. This is the family of geometric graphs whose vertex set is $S$ and which can be decomposed into two plane graphs. We show that every sufficiently large point set admits a 5-connected biplane graph and that there are arbitrarily large point sets that do not admit any 6-connected biplane graph. Furthermore, we show that every plane graph (other than a wheel or a fan) can be augmented into a 4-connected biplane graph. However, there are arbitrarily large plane graphs that cannot be augmented to a 5-connected biplane graph by adding pairwise noncrossing edges.
On a Relationship between the Correct Probability of Estimation from Correlated Data and Mutual Information
Venue: arXiv cs.IT 2017
Year: 2017

Let $X$, $Y$ be two correlated discrete random variables. We consider an estimation of $X$ from encoded data $φ(Y)$ of $Y$ by some encoder function $φ(Y)$. We derive an inequality describing a relation of the correct probability of estimation and the mutual information between $X$ and $φ(Y)$. This inequality may be useful for the secure analysis of crypto system when we use the success probability of estimating secret data as a security criterion. It also provides an intuitive meaning of the secrecy exponent in the strong secrecy criterion.