OpenRaiser/Intern-Atlas huggingface dataset:
Social Learning with Endogenous Network Formation
Venue: arXiv cs.SI 2016
Year: 2016

I study the problem of social learning in a model where agents move sequentially. Each agent receives a private signal about the underlying state of the world, observes the past actions in a neighborhood of individuals, and chooses her action attempting to match the true state. Earlier research in this field emphasizes that herding behavior occurs with a positive probability in certain special cases; recent studies show that asymptotic learning is achievable under a more general observation structure. In particular, with unbounded private beliefs, asymptotic learning occurs if and only if agents observe a close predecessor, i.e., the action of a close predecessor reveals the true state in the limit. However, a prevailing assumption in these studies is that the observation structure in the society is exogenous. In contrast to most of the previous literature, I assume in this paper that observation is endogenous and costly. More specifically, each agent must pay a specific cost to make any observation and can strategically choose the set of actions to observe privately. I introduce the notion of maximal learning (relative to cost) as a natural extension of asymptotic learning: society achieves maximal learning when agents can learn the true state with probability 1 in the limit after paying the cost of observation. I show that observing only a close predecessor is no longer sufficient for learning the true state with unbounded private beliefs and positive costs. Instead, maximal learning occurs if and only if the size of the observations extends to infinity. I provide interesting comparative statics as to how various settings in the model affect the learning probability. For instance, the probability to learn the true state may be higher under positive costs than under zero cost; in addition, the probability to learn the true state may be higher under weaker private signals.
Faster Statistical Model Checking for Unbounded Temporal Properties
Venue: arXiv cs.LO 2016
Year: 2016

We present a new algorithm for the statistical model checking of Markov chains with respect to unbounded temporal properties, such as reachability and full linear temporal logic. The main idea is that we monitor each simulation run on the fly, in order to detect quickly if a bottom strongly connected component is entered with high probability, in which case the simulation run can be terminated early. As a result, our simulation runs are often much shorter than required by termination bounds that are computed a priori for a desired level of confidence and size of the state space. In comparison to previous algorithms for statistical model checking, for a given level of confidence, our method is not only faster in many cases but also requires less information about the system, namely, only the minimum transition probability that occurs in the Markov chain, thus enabling almost complete black-box verification. In addition, our method can be generalised to unbounded quantitative properties such as mean-payoff bounds.
Generalized Support and Formal Development of Constraint Propagators
Venue: arXiv cs.AI 2016
Year: 2016

Constraint programming is a family of techniques for solving combinatorial problems, where the problem is modelled as a set of decision variables (typically with finite domains) and a set of constraints that express relations among the decision variables. One key concept in constraint programming is propagation: reasoning on a constraint or set of constraints to derive new facts, typically to remove values from the domains of decision variables. Specialised propagation algorithms (propagators) exist for many classes of constraints. The concept of support is pervasive in the design of propagators. Traditionally, when a domain value ceases to have support, it may be removed because it takes part in no solutions. Arc-consistency algorithms such as AC2001 make use of support in the form of a single domain value. GAC algorithms such as GAC-Schema use a tuple of values to support each literal. We generalize these notions of support in two ways. First, we allow a set of tuples to act as support. Second, the supported object is generalized from a set of literals (GAC-Schema) to an entire constraint or any part of it. We design a methodology for developing correct propagators using generalized support. A constraint is expressed as a family of support properties, which may be proven correct against the formal semantics of the constraint. Using Curry-Howard isomorphism to interpret constructive proofs as programs, we show how to derive correct propagators from the constructive proofs of the support properties. The framework is carefully designed to allow efficient algorithms to be produced. Derived algorithms may make use of dynamic literal triggers or watched literals for efficiency. Finally, two case studies of deriving efficient algorithms are given.
Learning Contextualized Music Semantics from Tags via a Siamese Network
Venue: arXiv cs.LG 2016
Year: 2016

Music information retrieval faces a challenge in modeling contextualized musical concepts formulated by a set of co-occurring tags. In this paper, we investigate the suitability of our recently proposed approach based on a Siamese neural network in fighting off this challenge. By means of tag features and probabilistic topic models, the network captures contextualized semantics from tags via unsupervised learning. This leads to a distributed semantics space and a potential solution to the out of vocabulary problem which has yet to be sufficiently addressed. We explore the nature of the resultant music-based semantics and address computational needs. We conduct experiments on three public music tag collections -namely, CAL500, MagTag5K and Million Song Dataset- and compare our approach to a number of state-of-the-art semantics learning approaches. Comparative results suggest that this approach outperforms previous approaches in terms of semantic priming and music tag completion.
Principal Patterns on Graphs: Discovering Coherent Structures in Datasets
Venue: arXiv cs.SI 2016
Year: 2016

Graphs are now ubiquitous in almost every field of research. Recently, new research areas devoted to the analysis of graphs and data associated to their vertices have emerged. Focusing on dynamical processes, we propose a fast, robust and scalable framework for retrieving and analyzing recurring patterns of activity on graphs. Our method relies on a novel type of multilayer graph that encodes the spreading or propagation of events between successive time steps. We demonstrate the versatility of our method by applying it on three different real-world examples. Firstly, we study how rumor spreads on a social network. Secondly, we reveal congestion patterns of pedestrians in a train station. Finally, we show how patterns of audio playlists can be used in a recommender system. In each example, relevant information previously hidden in the data is extracted in a very efficient manner, emphasizing the scalability of our method. With a parallel implementation scaling linearly with the size of the dataset, our framework easily handles millions of nodes on a single commodity server.
Deterministic Sampling-Based Motion Planning: Optimality, Complexity, and Performance
Venue: arXiv cs.RO 2016
Year: 2016

Probabilistic sampling-based algorithms, such as the probabilistic roadmap (PRM) and the rapidly-exploring random tree (RRT) algorithms, represent one of the most successful approaches to robotic motion planning, due to their strong theoretical properties (in terms of probabilistic completeness or even asymptotic optimality) and remarkable practical performance. Such algorithms are probabilistic in that they compute a path by connecting independently and identically distributed random points in the configuration space. Their randomization aspect, however, makes several tasks challenging, including certification for safety-critical applications and use of offline computation to improve real-time execution. Hence, an important open question is whether similar (or better) theoretical guarantees and practical performance could be obtained by considering deterministic, as opposed to random sampling sequences. The objective of this paper is to provide a rigorous answer to this question. Specifically, we first show that PRM, for a certain selection of tuning parameters and deterministic low-dispersion sampling sequences, is deterministically asymptotically optimal. Second, we characterize the convergence rate, and we find that the factor of sub-optimality can be very explicitly upper-bounded in terms of the l2-dispersion of the sampling sequence and the connection radius of PRM. Third, we show that an asymptotically optimal version of PRM exists with computational and space complexity arbitrarily close to O(n) (the theoretical lower bound), where n is the number of points in the sequence. This is in stark contrast to the O(n logn) complexity results for existing asymptotically-optimal probabilistic planners. Finally, through numerical experiments, we show that planning with deterministic low-dispersion sampling generally provides superior performance in terms of path cost and success rate.
Do they agree? Bibliometric evaluation vs informed peer review in the Italian research assessment exercise
Venue: arXiv cs.DL 2016
Year: 2016

During the Italian research assessment exercise, the national agency ANVUR performed an experiment to assess agreement between grades attributed to journal articles by informed peer review (IR) and by bibliometrics. A sample of articles was evaluated by using both methods and agreement was analyzed by weighted Cohen's kappas. ANVUR presented results as indicating an overall 'good' or 'more than adequate' agreement. This paper re-examines the experiment results according to the available statistical guidelines for interpreting kappa values, by showing that the degree of agreement, always in the range 0.09-0.42 has to be interpreted, for all research fields, as unacceptable, poor or, in a few cases, as, at most, fair. The only notable exception, confirmed also by a statistical meta-analysis, was a moderate agreement for economics and statistics (Area 13) and its sub-fields. We show that the experiment protocol adopted in Area 13 was substantially modified with respect to all the other research fields, to the point that results for economics and statistics have to be considered as fatally flawed. The evidence of a poor agreement supports the conclusion that IR and bibliometrics do not produce similar results, and that the adoption of both methods in the Italian research assessment possibly introduced systematic and unknown biases in its final results. The conclusion reached by ANVUR must be reversed: the available evidence does not justify at all the joint use of IR and bibliometrics within the same research assessment exercise.
Deploying Dense Networks for Maximal Energy Efficiency: Small Cells Meet Massive MIMO
Venue: arXiv cs.IT 2016
Year: 2016

How would a cellular network designed for maximal energy efficiency look like? To answer this fundamental question, tools from stochastic geometry are used in this paper to model future cellular networks and obtain a new lower bound on the average uplink spectral efficiency. This enables us to formulate a tractable uplink energy efficiency (EE) maximization problem and solve it analytically with respect to the density of base stations (BSs), the transmit power levels, the number of BS antennas and users per cell, and the pilot reuse factor. The closed-form expressions obtained from this general EE maximization framework provide valuable insights on the interplay between the optimization variables, hardware characteristics, and propagation environment. Small cells are proved to give high EE, but the EE improvement saturates quickly with the BS density. Interestingly, the maximal EE is achieved by also equipping the BSs with multiple antennas and operate in a "massive MIMO" fashion, where the array gain from coherent detection mitigates interference and the multiplexing of many users reduces the energy cost per user.
Multi-mode Unrolled Architectures for Polar Decoders
Venue: arXiv cs.AR 2016
Year: 2016

In this work, we present a family of architectures for polar decoders using a reduced-complexity successive-cancellation decoding algorithm that employs unrolling to achieve extremely high throughput values while retaining moderate implementation complexity. The resulting fully-unrolled, deeply-pipelined architecture is capable of achieving a coded throughput in excess of 1 Tbps on a 65 nm ASIC at 500 MHz---three orders of magnitude greater than current state-of-the-art polar decoders. However, unrolled decoders are built for a specific, fixed code. Therefore we also present a new method to enable the use of multiple code lengths and rates in a fully-unrolled polar decoder architecture. This method leads to a length- and rate-flexible decoder while retaining the very high speed typical to unrolled decoders. The resulting decoders can decode a master polar code of a given rate and length, and several shorter codes of different rates and lengths. We present results for two versions of a multi-mode decoder supporting eight and ten different polar codes, respectively. Both are capable of a peak throughput of 25.6 Gbps. For each decoder, the energy efficiency for the longest supported polar code is shown to be of 14.8 pJ/bit at 250 MHz and of 8.8 pJ/bit at 500 MHz.
On Asymptotic Gate Complexity and Depth of Reversible Circuits With Additional Memory
Venue: arXiv cs.CC 2016
Year: 2016

The reversible logic can be used in various research areas, e.g. quantum computation, cryptography and signal processing. In the paper we study reversible logic circuits with additional inputs, which consist of NOT, CNOT and C\textsuperscript{2}NOT gates. We consider a set $F(n,q)$ of all transformations $\mathbb B^n \to \mathbb B^n$ that can be realized by reversible circuits with $(n+q)$ inputs. An analogue of Lupanov's method for the synthesis of reversible logic circuits with additional inputs is described. We prove upper asymptotic bounds for the Shannon gate complexity function $L(n,q)$ and the depth function $D(n,q)$ in case of $q > 0$: $L(n,q_0) \lesssim 2^n$ if $q_0 \sim n 2^{n-o(n)}$ and $D(n,q_1) \lesssim 3n$ if $q_1 \sim 2^n$.
Cloud for Gaming
Venue: arXiv cs.DC 2016
Year: 2016

Cloud for Gaming refers to the use of cloud computing technologies to build large-scale gaming infrastructures, with the goal of improving scalability and responsiveness, improve the user's experience and enable new business models.
Multi-scale Volumes for Deep Object Detection and Localization
Venue: arXiv cs.CV 2016
Year: 2016

This study aims to analyze the benefits of improved multi-scale reasoning for object detection and localization with deep convolutional neural networks. To that end, an efficient and general object detection framework which operates on scale volumes of a deep feature pyramid is proposed. In contrast to the proposed approach, most current state-of-the-art object detectors operate on a single-scale in training, while testing involves independent evaluation across scales. One benefit of the proposed approach is in better capturing of multi-scale contextual information, resulting in significant gains in both detection performance and localization quality of objects on the PASCAL VOC dataset and a multi-view highway vehicles dataset. The joint detection and localization scale-specific models are shown to especially benefit detection of challenging object categories which exhibit large scale variation as well as detection of small objects.
Robust Visual Knowledge Transfer via EDA
Venue: arXiv cs.CV 2016
Year: 2016

We address the problem of visual knowledge adaptation by leveraging labeled patterns from source domain and a very limited number of labeled instances in target domain to learn a robust classifier for visual categorization. This paper proposes a new extreme learning machine based cross-domain network learning framework, that is called Extreme Learning Machine (ELM) based Domain Adaptation (EDA). It allows us to learn a category transformation and an ELM classifier with random projection by minimizing the l_(2,1)-norm of the network output weights and the learning error simultaneously. The unlabeled target data, as useful knowledge, is also integrated as a fidelity term to guarantee the stability during cross domain learning. It minimizes the matching error between the learned classifier and a base classifier, such that many existing classifiers can be readily incorporated as base classifiers. The network output weights cannot only be analytically determined, but also transferrable. Additionally, a manifold regularization with Laplacian graph is incorporated, such that it is beneficial to semi-supervised learning. Extensively, we also propose a model of multiple views, referred as MvEDA. Experiments on benchmark visual datasets for video event recognition and object recognition, demonstrate that our EDA methods outperform existing cross-domain learning methods.
Plane Formation by Synchronous Mobile Robots in the Three Dimensional Euclidean Space
Venue: arXiv cs.DC 2016
Year: 2016

Creating a swarm of mobile computing entities frequently called robots, agents or sensor nodes, with self-organization ability is a contemporary challenge in distributed computing. Motivated by this, we investigate the plane formation problem that requires a swarm of robots moving in the three dimensional Euclidean space to land on a common plane. The robots are fully synchronous and endowed with visual perception. But they do not have identifiers, nor access to the global coordinate system, nor any means of explicit communication with each other. Though there are plenty of results on the agreement problem for robots in the two dimensional plane, for example, the point formation problem, the pattern formation problem, and so on, this is the first result for robots in the three dimensional space. This paper presents a necessary and sufficient condition for fully-synchronous robots to solve the plane formation problem that does not depend on obliviousness i.e., the availability of local memory at robots. An implication of the result is somewhat counter-intuitive: The robots cannot form a plane from most of the semi-regular polyhedra, while they can form a plane from every regular polyhedron (except a regular icosahedron), whose symmetry is usually considered to be higher than any semi-regular polyhedrdon.
A Canonical Password Strength Measure
Venue: arXiv cs.CR 2016
Year: 2016

We notice that the "password security" discourse is missing the most fundamental notion of the "password strength" -- it was never properly defined. We propose a canonical definition of the "password strength", based on the assessment of the efficiency of a set of possible guessing attack. Unlike naive password strength assessments our metric takes into account the attacker's strategy, and we demonstrate the necessity of that feature. This paper does NOT advise you to include "at least three capital letters", seven underscores, and a number thirteen in your password.
Submodular Function Maximization over Distributive and Integer Lattices
Venue: arXiv cs.DM 2016
Year: 2016

The problem of maximizing non-negative submodular functions has been studied extensively in the last few years. However, most papers consider submodular set functions. Recently, several advances have been made for the more general case of submodular functions on the integer lattice. In this paper, we present a deterministic $\frac{1}{3}$-approximation for maximizing a submodular function on a bounded integer lattice $\{0, \ldots, C\}^n$ using a Double Greedy framework. Moreover, we show that the analysis is tight and that other ideas used for approximating set functions cannot easily be extended. In contrast to set functions, submodularity on the integer lattice does not imply the so-called diminishing returns property. Assuming this property, it was shown that many results for set functions can also be obtained for the integer lattice. In this paper, we consider a further generalization. Instead of the integer lattice, we consider a distributive lattice as the function domain and assume the diminishing returns (DR) property. On the one hand, we show that some approximation algorithms match the set functions setting. In particular, we can obtain a $\frac{1}{2}$-approximation for unconstrained maximization, a $(1-\frac{1}{e})$-approximation for monotone functions under a cardinality constraint and a $\frac{1}{2}$-approximation for a poset matroid constraint. On the other hand, for a knapsack constraint, the problem becomes significantly harder: even for monotone DR-submodular functions, we show that there is no $2^{(\log (n^{1/2} - 1))^δ- 1}$-approximation for every $δ> 0$ under the assumption that $3-SAT$ cannot be solved in time $2^{n^{3/4 + ε}}$.
Optimizing the Information Retrieval Trade-off in Data Visualization Using $α$-Divergence
Venue: arXiv cs.IR 2016
Year: 2016

Data visualization is one of the major applications of nonlinear dimensionality reduction. From the information retrieval perspective, the quality of a visualization can be evaluated by considering the extent that the neighborhood relation of each data point is maintained while the number of unrelated points that are retrieved is minimized. This property can be quantified as a trade-off between the mean precision and mean recall of the visualization. While there have been some approaches to formulate the visualization objective directly as a weighted sum of the precision and recall, there is no systematic way to determine the optimal trade-off between these two nor a clear interpretation of the optimal value. In this paper, we investigate the properties of $α$-divergence for information visualization, focusing our attention on a particular range of $α$ values. We show that the minimization of the new cost function corresponds to maximizing a geometric mean between precision and recall, parameterized by $α$. Contrary to some earlier methods, no hand-tuning is needed, but we can rigorously estimate the optimal value of $α$ for a given input data. For this, we provide a statistical framework using a novel distribution called Exponential Divergence with Augmentation (EDA). By the extensive set of experiments, we show that the optimal value of $α$, obtained by EDA corresponds to the optimal trade-off between the precision and recall for a given data distribution.
The complexity of approximately counting in 2-spin systems on $k$-uniform bounded-degree hypergraphs
Venue: arXiv cs.CC 2016
Year: 2016

One of the most important recent developments in the complexity of approximate counting is the classification of the complexity of approximating the partition functions of antiferromagnetic 2-spin systems on bounded-degree graphs. This classification is based on a beautiful connection to the so-called uniqueness phase transition from statistical physics on the infinite $Δ$-regular tree. Our objective is to study the impact of this classification on unweighted 2-spin models on $k$-uniform hypergraphs. As has already been indicated by Yin and Zhao, the connection between the uniqueness phase transition and the complexity of approximate counting breaks down in the hypergraph setting. Nevertheless, we show that for every non-trivial symmetric $k$-ary Boolean function $f$ there exists a degree bound $Δ_0$ so that for all $Δ\geq Δ_0$ the following problem is NP-hard: given a $k$-uniform hypergraph with maximum degree at most $Δ$, approximate the partition function of the hypergraph 2-spin model associated with $f$. It is NP-hard to approximate this partition function even within an exponential factor. By contrast, if $f$ is a trivial symmetric Boolean function (e.g., any function $f$ that is excluded from our result), then the partition function of the corresponding hypergraph 2-spin model can be computed exactly in polynomial time.