OpenRaiser/Intern-Atlas huggingface dataset:
Experiments on Crowdsourcing Policy Assessment
Venue: arXiv cs.CY 2017
Year: 2017

Can Crowds serve as useful allies in policy design? How do non-expert Crowds perform relative to experts in the assessment of policy measures? Does the geographic location of non-expert Crowds, with relevance to the policy context, alter the performance of non-experts Crowds in the assessment of policy measures? In this work, we investigate these questions by undertaking experiments designed to replicate expert policy assessments with non-expert Crowds recruited from Virtual Labor Markets. We use a set of ninety-six climate change adaptation policy measures previously evaluated by experts in the Netherlands as our control condition to conduct experiments using two discrete sets of non-expert Crowds recruited from Virtual Labor Markets. We vary the composition of our non-expert Crowds along two conditions: participants recruited from a geographical location directly relevant to the policy context and participants recruited at-large. We discuss our research methods in detail and provide the findings of our experiments.
A "Quantal Regret" Method for Structural Econometrics in Repeated Games
Venue: arXiv cs.GT 2017
Year: 2017

We suggest a general method for inferring players' values from their actions in repeated games. The method extends and improves upon the recent suggestion of (Nekipelov et al., EC 2015) and is based on the assumption that players are more likely to exhibit sequences of actions that have lower regret. We evaluate this "quantal regret" method on two different datasets from experiments of repeated games with controlled player values: those of (Selten and Chmura, AER 2008) on a variety of two-player 2x2 games and our own experiment on ad-auctions (Noti et al., WWW 2014). We find that the quantal regret method is consistently and significantly more precise than either "classic" econometric methods that are based on Nash equilibria, or the "min-regret" method of (Nekipelov et al., EC 2015).
Okapi: Causally Consistent Geo-Replication Made Faster, Cheaper and More Available
Venue: arXiv cs.DC 2017
Year: 2017

Okapi is a new causally consistent geo-replicated key- value store. Okapi leverages two key design choices to achieve high performance. First, it relies on hybrid logical/physical clocks to achieve low latency even in the presence of clock skew. Second, Okapi achieves higher resource efficiency and better availability, at the expense of a slight increase in update visibility latency. To this end, Okapi implements a new stabilization protocol that uses a combination of vector and scalar clocks and makes a remote update visible when its delivery has been acknowledged by every data center. We evaluate Okapi with different workloads on Amazon AWS, using three geographically distributed regions and 96 nodes. We compare Okapi with two recent approaches to causal consistency, Cure and GentleRain. We show that Okapi delivers up to two orders of magnitude better performance than GentleRain and that Okapi achieves up to 3.5x lower latency and a 60% reduction of the meta-data overhead with respect to Cure.
Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Time
Venue: arXiv cs.DS 2017
Year: 2017

We give a nearly linear time randomized approximation scheme for the Held-Karp bound [Held and Karp, 1970] for metric TSP. Formally, given an undirected edge-weighted graph $G$ on $m$ edges and $ε> 0$, the algorithm outputs in $O(m \log^4n /ε^2)$ time, with high probability, a $(1+ε)$-approximation to the Held-Karp bound on the metric TSP instance induced by the shortest path metric on $G$. The algorithm can also be used to output a corresponding solution to the Subtour Elimination LP. We substantially improve upon the $O(m^2 \log^2(m)/ε^2)$ running time achieved previously by Garg and Khandekar. The LP solution can be used to obtain a fast randomized $\big(\frac{3}{2} + ε\big)$-approximation for metric TSP which improves upon the running time of previous implementations of Christofides' algorithm.
A case study on using speech-to-translation alignments for language documentation
Venue: arXiv cs.CL 2017
Year: 2017

For many low-resource or endangered languages, spoken language resources are more likely to be annotated with translations than with transcriptions. Recent work exploits such annotations to produce speech-to-translation alignments, without access to any text transcriptions. We investigate whether providing such information can aid in producing better (mismatched) crowdsourced transcriptions, which in turn could be valuable for training speech recognition systems, and show that they can indeed be beneficial through a small-scale case study as a proof-of-concept. We also present a simple phonetically aware string averaging technique that produces transcriptions of higher quality.
IoT Localization for Bistatic Passive UHF RFID Systems with 3D Radiation Pattern
Venue: arXiv cs.NI 2017
Year: 2017

Passive Radio-Frequency IDentification (RFID) systems carry critical importance for Internet of Things (IoT) applications due to their energy harvesting capabilities. RFID based position estimation, in particular, is expected to facilitate a wide array of location based services for IoT applications with low-power requirements. In this paper, considering monostatic and bistatic configurations and 3D antenna radiation pattern, we investigate the accuracy of received signal strength based wireless localization using passive ultra high frequency (UHF) RFID systems. The Cramer-Rao Lower Bound (CRLB) for the localization accuracy is derived, and is compared with the accuracy of maximum likelihood estimators for various RFID antenna configurations. Numerical results show that due to RFID tag/antenna sensitivity, and the directional antenna pattern, the localization accuracy can degrade at blind locations that remain outside of the RFID reader antennas' main beam patterns. In such cases optimizing elevation angle of antennas are shown to improve localization coverage, while using bistatic configuration improves localization accuracy significantly.
On the Discrepancy Between Kleinberg's Clustering Axioms and $k$-Means Clustering Algorithm Behavior
Venue: arXiv cs.LG 2017
Year: 2017

This paper investigates the validity of Kleinberg's axioms for clustering functions with respect to the quite popular clustering algorithm called $k$-means. While Kleinberg's axioms have been discussed heavily in the past, we concentrate here on the case predominantly relevant for $k$-means algorithm, that is behavior embedded in Euclidean space. We point at some contradictions and counter intuitiveness aspects of this axiomatic set within $\mathbb{R}^m$ that were evidently not discussed so far. Our results suggest that apparently without defining clearly what kind of clusters we expect we will not be able to construct a valid axiomatic system. In particular we look at the shape and the gaps between the clusters. Finally we demonstrate that there exist several ways to reconcile the formulation of the axioms with their intended meaning and that under this reformulation the axioms stop to be contradictory and the real-world $k$-means algorithm conforms to this axiomatic system.
Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function
Venue: arXiv cs.AI 2017
Year: 2017

The Minimum Weight Dominating Set (MWDS) problem is an important generalization of the Minimum Dominating Set (MDS) problem with extensive applications. This paper proposes a new local search algorithm for the MWDS problem, which is based on two new ideas. The first idea is a heuristic called two-level configuration checking (CC2), which is a new variant of a recent powerful configuration checking strategy (CC) for effectively avoiding the recent search paths. The second idea is a novel scoring function based on the frequency of being uncovered of vertices. Our algorithm is called CC2FS, according to the names of the two ideas. The experimental results show that, CC2FS performs much better than some state-of-the-art algorithms in terms of solution quality on a broad range of MWDS benchmarks.
Wiki-index of authors popularity
Venue: arXiv cs.DL 2017
Year: 2017

The new index of the author's popularity estimation is represented in the paper. The index is calculated on the basis of Wikipedia encyclopedia analysis (Wikipedia Index - WI). Unlike the conventional existed citation indices, the suggested mark allows to evaluate not only the popularity of the author, as it can be done by means of calculating the general citation number or by the Hirsch index, which is often used to measure the author's research rate. The index gives an opportunity to estimate the author's popularity, his/her influence within the sought-after area "knowledge area" in the Internet - in the Wikipedia. The suggested index is supposed to be calculated in frames of the subject domain, and it, on the one hand, avoids the mistaken computation of the homonyms, and on the other hand - provides the entirety of the subject area. There are proposed algorithms and the technique of the Wikipedia Index calculation through the network encyclopedia sounding, the exemplified calculations of the index for the prominent researchers, and also the methods of the information networks formation - models of the subject domains by the automatic monitoring and networks information reference resources analysis. The considered in the paper notion network corresponds the terms-heads of the Wikipedia articles.
The Rare Eclipse Problem on Tiles: Quantised Embeddings of Disjoint Convex Sets
Venue: arXiv cs.IT 2017
Year: 2017

Quantised random embeddings are an efficient dimensionality reduction technique which preserves the distances of low-complexity signals up to some controllable additive and multiplicative distortions. In this work, we instead focus on verifying when this technique preserves the separability of two disjoint closed convex sets, i.e., in a quantised view of the "rare eclipse problem" introduced by Bandeira et al. in 2014. This separability would ensure exact classification of signals in such sets from the signatures output by this non-linear dimensionality reduction. We here present a result relating the embedding's dimension, its quantiser resolution and the sets' separation, as well as some numerically testable conditions to illustrate it. Experimental evidence is then provided in the special case of two $\ell_2$-balls, tracing the phase transition curves that ensure these sets' separability in the embedded domain.
Simflowny 2: An upgraded platform for scientific modeling and simulation
Venue: arXiv cs.MS 2017
Year: 2017

Simflowny is an open platform which automatically generates parallel code of scientific dynamical models for different simulation frameworks. Here we present major upgrades on this software to support an extended set of families of models, in particular: i) a new generic family for partial differential equations, which can include spatial derivatives of any order, ii) a new family for agent based models to study complex phenomena --either on a spatial domain or on a graph--. Additionally we introduce a flexible graphical user interface (GUI) to accommodate these and future families of equations. This paper describes the new GUI architecture and summarizes the formal representation and implementation of these new families, providing several validation results.
Achievable information rates estimates in optically-amplified transmission systems using nonlinearity compensation and probabilistic shaping
Venue: arXiv cs.IT 2017
Year: 2017

Achievable information rates (AIRs) of wideband optical communication systems using ~40 nm (~5 THz) EDFA and ~100 nm (~12.5 THz) distributed Raman amplification are estimated based on a first-order perturbation analysis. The AIRs of each individual channel have been evaluated for DP-64QAM, DP-256QAM, and DP-1024QAM modulation formats. The impact of full-field nonlinear compensation (FF-NLC) and probabilistically shaped constellations using a Maxwell-Boltzmann distribution were studied and compared to electronic dispersion compensation. It is found that a probabilistically shaped DP-1024QAM constellation combined with FF-NLC yields AIRs of ~75 Tbit/s for the EDFA scheme and ~223 Tbit/s for the Raman amplification scheme over 2000 km standard single mode fibre transmission.
Current Induced Dynamics of Multiple Skyrmions with Domain Wall Pair and Skyrmion-based Majority Gate Design
Venue: arXiv cs.ET 2017
Year: 2017

As an intriguing ultra-small particle-like magnetic texture, skyrmion has attracted lots of research interests in next-generation ultra-dense and low power magnetic memory/logic designs. Previous studies have demonstrated a single skyrmion-domain wall pair collision in a specially designed magnetic racetrack junction. In this work, we investigate the dynamics of multiple skyrmions with domain wall pair in a magnetic racetrack. The numerical micromagnetic simulation results indicate that the domain wall pair could be pinned or depinned by the rectangular notch pinning site depending on both the number of skyrmions in the racetrack and the magnitude of driving current density. Such emergent dynamical property could be used to implement a threshold-tunable step function, in which the inputs are skyrmions and threshold could be tuned by the driving current density. The threshold-tunable step function is widely used in logic and neural network applications. We also present a three-input skyrmion-based majority logic gate design to demonstrate the potential application of such dynamic interaction of multiple skyrmions and domain wall pair.
Theoretical and Practical Advances on Smoothing for Extensive-Form Games
Venue: arXiv cs.GT 2017
Year: 2017

Sparse iterative methods, in particular first-order methods, are known to be among the most effective in solving large-scale two-player zero-sum extensive-form games. The convergence rates of these methods depend heavily on the properties of the distance-generating function that they are based on. We investigate the acceleration of first-order methods for solving extensive-form games through better design of the dilated entropy function---a class of distance-generating functions related to the domains associated with the extensive-form games. By introducing a new weighting scheme for the dilated entropy function, we develop the first distance-generating function for the strategy spaces of sequential games that has no dependence on the branching factor of the player. This result improves the convergence rate of several first-order methods by a factor of $Ω(b^dd)$, where $b$ is the branching factor of the player, and $d$ is the depth of the game tree. Thus far, counterfactual regret minimization methods have been faster in practice, and more popular, than first-order methods despite their theoretically inferior convergence rates. Using our new weighting scheme and practical tuning we show that, for the first time, the excessive gap technique can be made faster than the fastest counterfactual regret minimization algorithm, CFR+, in practice.
Polar codes with a stepped boundary
Venue: arXiv cs.IT 2017
Year: 2017

We consider explicit polar constructions of blocklength $n\rightarrow\infty$ for the two extreme cases of code rates $R\rightarrow1$ and $R\rightarrow0.$ For code rates $R\rightarrow1,$ we design codes with complexity order of $n\log n$ in code construction, encoding, and decoding. These codes achieve the vanishing output bit error rates on the binary symmetric channels with any transition error probability $p\rightarrow 0$ and perform this task with a substantially smaller redundancy $(1-R)n$ than do other known high-rate codes, such as BCH codes or Reed-Muller (RM). We then extend our design to the low-rate codes that achieve the vanishing output error rates with the same complexity order of $n\log n$ and an asymptotically optimal code rate $R\rightarrow0$ for the case of $p\rightarrow1/2.$
Compressed sensing in Hilbert spaces
Venue: arXiv cs.IT 2017
Year: 2017

In many linear inverse problems, we want to estimate an unknown vector belonging to a high-dimensional (or infinite-dimensional) space from few linear measurements. To overcome the ill-posed nature of such problems, we use a low-dimension assumption on the unknown vector: it belongs to a low-dimensional model set. The question of whether it is possible to recover such an unknown vector from few measurements then arises. If the answer is yes, it is also important to be able to describe a way to perform such a recovery. We describe a general framework where appropriately chosen random measurements guarantee that recovery is possible. We further describe a way to study the performance of recovery methods that consist in the minimization of a regularization function under a data-fit constraint.
A Framework for Interactive Teaching of Virtual Borders to Mobile Robots
Venue: arXiv cs.RO 2017
Year: 2017

The increasing number of robots in home environments leads to an emerging coexistence between humans and robots. Robots undertake common tasks and support the residents in their everyday life. People appreciate the presence of robots in their environment as long as they keep the control over them. One important aspect is the control of a robot's workspace. Therefore, we introduce virtual borders to precisely and flexibly define the workspace of mobile robots. First, we propose a novel framework that allows a person to interactively restrict a mobile robot's workspace. To show the validity of this framework, a concrete implementation based on visual markers is implemented. Afterwards, the mobile robot is capable of performing its tasks while respecting the new virtual borders. The approach is accurate, flexible and less time consuming than explicit robot programming. Hence, even non-experts are able to teach virtual borders to their robots which is especially interesting in domains like vacuuming or service robots in home environments.
Understanding International Migration using Tensor Factorization
Venue: arXiv cs.SI 2017
Year: 2017

Understanding human migration is of great interest to demographers and social scientists. User generated digital data has made it easier to study such patterns at a global scale. Geo coded Twitter data, in particular, has been shown to be a promising source to analyse large scale human migration. But given the scale of these datasets, a lot of manual effort has to be put into processing and getting actionable insights from this data. In this paper, we explore feasibility of using a new tool, tensor decomposition, to understand trends in global human migration. We model human migration as a three mode tensor, consisting of (origin country, destination country, time of migration) and apply CP decomposition to get meaningful low dimensional factors. Our experiments on a large Twitter dataset spanning 5 years and over 100M tweets show that we can extract meaningful migration patterns.
Unbiased Online Recurrent Optimization
Venue: arXiv cs.NE 2017
Year: 2017

The novel Unbiased Online Recurrent Optimization (UORO) algorithm allows for online learning of general recurrent computational graphs such as recurrent network models. It works in a streaming fashion and avoids backtracking through past activations and inputs. UORO is computationally as costly as Truncated Backpropagation Through Time (truncated BPTT), a widespread algorithm for online learning of recurrent networks. UORO is a modification of NoBackTrack that bypasses the need for model sparsity and makes implementation easy in current deep learning frameworks, even for complex models. Like NoBackTrack, UORO provides unbiased gradient estimates; unbiasedness is the core hypothesis in stochastic gradient descent theory, without which convergence to a local optimum is not guaranteed. On the contrary, truncated BPTT does not provide this property, leading to possible divergence. On synthetic tasks where truncated BPTT is shown to diverge, UORO converges. For instance, when a parameter has a positive short-term but negative long-term influence, truncated BPTT diverges unless the truncation span is very significantly longer than the intrinsic temporal range of the interactions, while UORO performs well thanks to the unbiasedness of its gradients.
Addressing the Data Sparsity Issue in Neural AMR Parsing
Venue: arXiv cs.CL 2017
Year: 2017

Neural attention models have achieved great success in different NLP tasks. How- ever, they have not fulfilled their promise on the AMR parsing task due to the data sparsity issue. In this paper, we de- scribe a sequence-to-sequence model for AMR parsing and present different ways to tackle the data sparsity problem. We show that our methods achieve significant improvement over a baseline neural atten- tion model and our results are also compet- itive against state-of-the-art systems that do not use extra linguistic resources.
OntoMath Digital Ecosystem: Ontologies, Mathematical Knowledge Analytics and Management
Venue: arXiv cs.DL 2017
Year: 2017

In this article we consider the basic ideas, approaches and results of developing of mathematical knowledge management technologies based on ontologies. These solutions form the basis of a specialized digital ecosystem OntoMath which consists of the ontology of the logical structure of mathematical documents Mocassin and ontology of mathematical knowledge OntoMathPRO, tools of text analysis, recommender system and other applications to manage mathematical knowledge. The studies are in according to the ideas of creating a distributed system of interconnected repositories of digitized versions of mathematical documents and project to create a World Digital Mathematical Library.
Evolutionary prisoner's dilemma games coevolving on adaptive networks
Venue: arXiv cs.SI 2017
Year: 2017

We study a model for switching strategies in the Prisoner's Dilemma game on adaptive networks of player pairings that coevolve as players attempt to maximize their return. We use a node-based strategy model wherein each player follows one strategy at a time (cooperate or defect) across all of its neighbors, changing that strategy and possibly changing partners in response to local changes in the network of player pairing and in the strategies used by connected partners. We compare and contrast numerical simulations with existing pair approximation differential equations for describing this system, as well as more accurate equations developed here using the framework of approximate master equations. We explore the parameter space of the model, demonstrating the relatively high accuracy of the approximate master equations for describing the system observations made from simulations. We study two variations of this partner-switching model to investigate the system evolution, predict stationary states, and compare the total utilities and other qualitative differences between these two model variants.
Blockchain-oriented Software Engineering: Challenges and New Directions
Venue: arXiv cs.SE 2017
Year: 2017

The Blockchain technology is reshaping finance, economy, money to the extent that its disruptive power is compared to that of the Internet and the Web in their early days. As a result, all the software development revolving around the Blockchain technology is growing at a staggering rate. In this paper, we acknowledge the need for software engineers to devise specialized tools and techniques for blockchain-oriented software development. From current challenges concerning the definition of new professional roles, demanding testing activities and novel tools for software architecture, we take a step forward by proposing new directions on the basis of a curate corpus of blockchain-oriented software repositories, detected by exploiting the information enclosed in the 2016 Moody's Blockchain Report and teh market capitalization of cryptocurrencies. Ensuring effective testing activities, enhancing collaboration in large teams, and facilitating the development of smart contracts all appear as key factors in the future of blockchain-oriented software development.