OpenRaiser/Intern-Atlas huggingface dataset:
Towards Understanding the Evolution of Vocabulary Terms in Knowledge Graphs
Venue: arXiv cs.IR 2017
Year: 2017

Vocabularies are used for modeling data in Knowledge Graphs (KG) like the Linked Open Data Cloud and Wikidata. During their lifetime, the vocabularies of the KGs are subject to changes. New terms are coined, while existing terms are modified or declared as deprecated. We first quantify the amount and frequency of changes in vocabularies. Subsequently, we investigate to which extend and when the changes are adopted in the evolution of the KGs. We conduct our experiments on three large-scale KGs for which time-stamped snapshots are available, namely the Billion Triples Challenge datasets, Dynamic Linked Data Observatory dataset, and Wikidata. Our results show that the change frequency of terms is rather low, but can have high impact when adopted on a large amount of distributed graph data on the web. Furthermore, not all coined terms are used and most of the deprecated terms are still used by data publishers. There are variations in the adoption time of terms coming from different vocabularies ranging from very fast (few days) to very slow (few years). Surprisingly, there are also adoptions we could observe even before the vocabulary changes are published. Understanding this adoption is important, since otherwise it may lead to wrong assumptions about the modeling status of data published on the web and may result in difficulties when querying the data from distributed sources.
Bayesian estimation from few samples: community detection and related problems
Venue: arXiv cs.DS 2017
Year: 2017

We propose an efficient meta-algorithm for Bayesian estimation problems that is based on low-degree polynomials, semidefinite programming, and tensor decomposition. The algorithm is inspired by recent lower bound constructions for sum-of-squares and related to the method of moments. Our focus is on sample complexity bounds that are as tight as possible (up to additive lower-order terms) and often achieve statistical thresholds or conjectured computational thresholds. Our algorithm recovers the best known bounds for community detection in the sparse stochastic block model, a widely-studied class of estimation problems for community detection in graphs. We obtain the first recovery guarantees for the mixed-membership stochastic block model (Airoldi et el.) in constant average degree graphs---up to what we conjecture to be the computational threshold for this model. We show that our algorithm exhibits a sharp computational threshold for the stochastic block model with multiple communities beyond the Kesten--Stigum bound---giving evidence that this task may require exponential time. The basic strategy of our algorithm is strikingly simple: we compute the best-possible low-degree approximation for the moments of the posterior distribution of the parameters and use a robust tensor decomposition algorithm to recover the parameters from these approximate posterior moments.
Distributed and Managed: Research Challenges and Opportunities of the Next Generation Cyber-Physical Systems
Venue: arXiv cs.DC 2017
Year: 2017

Cyber-physical systems increasingly rely on distributed computing platforms where sensing, computing, actuation, and communication resources are shared by a multitude of applications. Such `cyber-physical cloud computing platforms' present novel challenges because the system is built from mobile embedded devices, is inherently distributed, and typically suffers from highly fluctuating connectivity among the modules. Architecting software for these systems raises many challenges not present in traditional cloud computing. Effective management of constrained resources and application isolation without adversely affecting performance are necessary. Autonomous fault management and real-time performance requirements must be met in a verifiable manner. It is also both critical and challenging to support multiple end-users whose diverse software applications have changing demands for computational and communication resources, while operating on different levels and in separate domains of security. The solution presented in this paper is based on a layered architecture consisting of a novel operating system, a middleware layer, and component-structured applications. The component model facilitates the construction of software applications from modular and reusable components that are deployed in the distributed system and interact only through well-defined mechanisms. The complexity of creating applications and performing system integration is mitigated through the use of a domain-specific model-driven development process that relies on a domain-specific modeling language and its accompanying graphical modeling tools, software generators for synthesizing infrastructure code, and the extensive use of model-based analysis for verification and validation.
Bounded Rationality in Scholarly Knowledge Discovery
Venue: arXiv cs.DL 2017
Year: 2017

In an information-rich world, people's time and attention must be divided among rapidly changing information sources and the diverse tasks demanded of them. How people decide which of the many sources, such as scientific articles or patents, to read and use in their own work affects dissemination of scholarly knowledge and adoption of innovation. We analyze the choices people make about what information to propagate on the citation networks of Physical Review journals, US patents and legal opinions. We observe regularities in behavior consistent with human bounded rationality: rather than evaluate all available choices, people rely on simply cognitive heuristics to decide what information to attend to. We demonstrate that these heuristics bias choices, so that people preferentially propagate information that is easier to discover, often because it is newer or more popular. However, we do not find evidence that popular sources help to amplify the spread of information beyond making it more salient. Our paper provides novel evidence of the critical role that bounded rationality plays in the decisions to allocate attention in social communication.
A Data-driven Approach Towards Human-robot Collaborative Problem Solving in a Shared Space
Venue: arXiv cs.HC 2017
Year: 2017

We are developing a system for human-robot communication that enables people to communicate with robots in a natural way and is focused on solving problems in a shared space. Our strategy for developing this system is fundamentally data-driven: we use data from multiple input sources and train key components with various machine learning techniques. We developed a web application that is collecting data on how two humans communicate to accomplish a task, as well as a mobile laboratory that is instrumented to collect data on how two humans communicate to accomplish a task in a physically shared space. The data from these systems will be used to train and fine-tune the second stage of our system, in which the robot will be simulated through software. A physical robot will be used in the final stage of our project. We describe these instruments, a test-suite and performance metrics designed to evaluate and automate the data gathering process as well as evaluate an initial data set.
A Moving-Horizon Hybrid Stochastic Game for Secure Control of Cyber-Physical Systems
Venue: arXiv cs.GT 2017
Year: 2017

In this paper, we establish a zero-sum, hybrid state stochastic game model for designing defense policies for cyber-physical systems against different types of attacks. With the increasingly integrated properties of cyber-physical systems (CPS) today, security is a challenge for critical infrastructures. Though resilient control and detecting techniques for a specific model of attack have been proposed, to analyze and design detection and defense mechanisms against multiple types of attacks for CPSs requires new system frameworks. Besides security, other requirements such as optimal control cost also need to be considered. The hybrid game model we propose in this work contains physical states that are described by the system dynamics, and a cyber state that represents the detection mode of the system composed by a set of subsystems. A strategy means selecting a subsystem by combining one controller, one estimator and one detector among a finite set of candidate components at each state. Based on the game model, we propose a suboptimal value iteration algorithm for a finite horizon game, and prove that the algorithm results an upper bound for the value of the finite horizon game. A moving-horizon approach is also developed in order to provide a scalable and real-time computation of the switching strategies. Both algorithms aims at obtaining a saddle-point equilibrium policy for balancing the system's security overhead and control cost. The paper illustrates these concepts using numerical examples, and we compare the results with previously system designs that only equipped with one type of controller.
Robust Tuning Datasets for Statistical Machine Translation
Venue: arXiv cs.CL 2017
Year: 2017

We explore the idea of automatically crafting a tuning dataset for Statistical Machine Translation (SMT) that makes the hyper-parameters of the SMT system more robust with respect to some specific deficiencies of the parameter tuning algorithms. This is an under-explored research direction, which can allow better parameter tuning. In this paper, we achieve this goal by selecting a subset of the available sentence pairs, which are more suitable for specific combinations of optimizers, objective functions, and evaluation measures. We demonstrate the potential of the idea with the pairwise ranking optimization (PRO) optimizer, which is known to yield too short translations. We show that the learning problem can be alleviated by tuning on a subset of the development set, selected based on sentence length. In particular, using the longest 50% of the tuning sentences, we achieve two-fold tuning speedup, and improvements in BLEU score that rival those of alternatives, which fix BLEU+1's smoothing instead.
Filling the citation gap: Measuring the multidimensional impact of the academic book at institutional level with PlumX
Venue: arXiv cs.DL 2017
Year: 2017

More than five years after their emergence, altmetrics are still seen as a promise to complement traditional citation-based indicators. However, no study has focused on their potential usefulness to capture the impact of scholarly books. While recent literature shows that citation indicators cannot fully capture the impact of books, other studies have suggested alternative indicators such as usage, publishers' prestige or library holdings. In this paper, we calculate 18 indicators which range from altmetrics to library holdings, views, downloads or citations to the production of monographs of a Spanish university using the bibliometric suite PlumX from EBSCO. The objective of the study is to adopt a multidimensional perspective on the analysis of books and understand the level of complementarity between these different indicators. Also, we compare the overview offered by this range of indicators when applied to monographs with the traditional bibliometric perspective focused on journal articles and citation impact. We observe a low presence of altmetric indicators for monographs, even lower than for journal articles and a predominance of library holdings, confirming this indicator as the most promising one towards the analysis of the impact of books.
libact: Pool-based Active Learning in Python
Venue: arXiv cs.LG 2017
Year: 2017

libact is a Python package designed to make active learning easier for general users. The package not only implements several popular active learning strategies, but also features the active-learning-by-learning meta-algorithm that assists the users to automatically select the best strategy on the fly. Furthermore, the package provides a unified interface for implementing more strategies, models and application-specific labelers. The package is open-source on Github, and can be easily installed from Python Package Index repository.
Data hiding in Fingerprint Minutiae Template for Privacy Protection
Venue: arXiv cs.CR 2017
Year: 2017

In this paper, we propose a novel scheme for data hiding in the fingerprint minutiae template, which is the most popular in fingerprint recognition systems. Various strategies are proposed in data embedding in order to maintain the accuracy of fingerprint recognition as well as the undetectability of data hiding. In bits replacement based data embedding, we replace the last few bits of each element of the original minutiae template with the data to be hidden. This strategy can be further improved using an optimized bits replacement based data embedding, which is able to minimize the impact of data hiding on the performance of fingerprint recognition. The third strategy is an order preserving mechanism which is proposed to reduce the detectability of data hiding. By using such a mechanism, it would be difficult for the attacker to differentiate the minutiae template with hidden data from the original minutiae templates. The experimental results show that the proposed data hiding scheme achieves sufficient capacity for hiding common personal data, where the accuracy of fingerprint recognition is acceptable after the data hiding.
Belief Dynamics in Social Networks: A Fluid-Based Analysis
Venue: arXiv cs.SI 2017
Year: 2017

The advent and proliferation of social media have led to the development of mathematical models describing the evolution of beliefs/opinions in an ecosystem composed of socially interacting users. The goal is to gain insights into collective dominant social beliefs and into the impact of different components of the system, such as users' interactions, while being able to predict users' opinions. Following this thread, in this paper we consider a fairly general dynamical model of social interactions, which captures all the main features exhibited by a social system. For such model, by embracing a mean-field approach, we derive a diffusion differential equation that represents asymptotic belief dynamics, as the number of users grows large. We then analyze the steady-state behavior as well as the time dependent (transient) behavior of the system. In particular, for the steady-state distribution, we obtain simple closed-form expressions for a relevant class of systems, while we propose efficient semi-analytical techniques in the most general cases. At last, we develop an efficient semi-analytical method to analyze the dynamics of the users' belief over time, which can be applied to a remarkably large class of systems.
The Strategy of Experts for Repeated Predictions
Venue: arXiv cs.GT 2017
Year: 2017

We investigate the behavior of experts who seek to make predictions with maximum impact on an audience. At a known future time, a certain continuous random variable will be realized. A public prediction gradually converges to the outcome, and an expert has access to a more accurate prediction. We study when the expert should reveal his information, when his reward is based on a proper scoring rule (e.g., is proportional to the change in log-likelihood of the outcome). In Azar et. al. (2016), we analyzed the case where the expert may make a single prediction. In this paper, we analyze the case where the expert is allowed to revise previous predictions. This leads to a rather different set of dilemmas for the strategic expert. We find that it is optimal for the expert to always tell the truth, and to make a new prediction whenever he has a new signal. We characterize the expert's expectation for his total reward, and show asymptotic limits
Distributed Optimization for Coordinated Beamforming in Multi-Cell Multigroup Multicast Systems: Power Minimization and SINR Balancing
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers coordinated multicast beamforming in a multi-cell multigroup multiple-input single-output system. Each base station (BS) serves multiple groups of users by forming a single beam with common information per group. We propose centralized and distributed beamforming algorithms for two different optimization targets. The first objective is to minimize the total transmission power of all the BSs while guaranteeing the user-specific minimum quality-of-service targets. The semidefinite relaxation (SDR) method is used to approximate the non-convex multicast problem as a semidefinite program (SDP), which is solvable via centralized processing. Subsequently, two alternative distributed methods are proposed. The first approach turns the SDP into a two-level optimization via primal decomposition. At the higher level, inter-cell interference powers are optimized for fixed beamformers while the lower level locally optimizes the beamformers by minimizing BS-specific transmit powers for the given inter-cell interference constraints. The second distributed solution is enabled via an alternating direction method of multipliers, where the inter-cell interference optimization is divided into a local and a global optimization by forcing the equality via consistency constraints. We further propose a centralized and a simple distributed beamforming design for the signal-to-interference-plus-noise ratio (SINR) balancing problem in which the minimum SINR among the users is maximized with given per-BS power constraints. This problem is solved via the bisection method as a series of SDP feasibility problems. The simulation results show the superiority of the proposed coordinated beamforming algorithms over traditional non-coordinated transmission schemes, and illustrate the fast convergence of the distributed methods.
Latency and Reliability-Aware Task Offloading and Resource Allocation for Mobile Edge Computing
Venue: arXiv cs.NI 2017
Year: 2017

While mobile edge computing (MEC) alleviates the computation and power limitations of mobile devices, additional latency is incurred when offloading tasks to remote MEC servers. In this work, the power-delay tradeoff in the context of task offloading is studied in a multi-user MEC scenario. In contrast with current system designs relying on average metrics (e.g., the average queue length and average latency), a novel network design is proposed in which latency and reliability constraints are taken into account. This is done by imposing a probabilistic constraint on users' task queue lengths and invoking results from extreme value theory to characterize the occurrence of low-probability events in terms of queue length (or queuing delay) violation. The problem is formulated as a computation and transmit power minimization subject to latency and reliability constraints, and solved using tools from Lyapunov stochastic optimization. Simulation results demonstrate the effectiveness of the proposed approach, while examining the power-delay tradeoff and required computational resources for various computation intensities.
Constrained Differential Privacy for Count Data
Venue: arXiv cs.DB 2017
Year: 2017

Concern about how to aggregate sensitive user data without compromising individual privacy is a major barrier to greater availability of data. The model of differential privacy has emerged as an accepted model to release sensitive information while giving a statistical guarantee for privacy. Many different algorithms are possible to address different target functions. We focus on the core problem of count queries, and seek to design mechanisms to release data associated with a group of n individuals. Prior work has focused on designing mechanisms by raw optimization of a loss function, without regard to the consequences on the results. This can leads to mechanisms with undesirable properties, such as never reporting some outputs (gaps), and overreporting others (spikes). We tame these pathological behaviors by introducing a set of desirable properties that mechanisms can obey. Any combination of these can be satisfied by solving a linear program (LP) which minimizes a cost function, with constraints enforcing the properties. We focus on a particular cost function, and provide explicit constructions that are optimal for certain combinations of properties, and show a closed form for their cost. In the end, there are only a handful of distinct optimal mechanisms to choose between: one is the well-known (truncated) geometric mechanism; the second a novel mechanism that we introduce here, and the remainder are found as the solution to particular LPs. These all avoid the bad behaviors we identify. We demonstrate in a set of experiments on real and synthetic data which is preferable in practice, for different combinations of data distributions, constraints, and privacy parameters.
Improving Spark Application Throughput Via Memory Aware Task Co-location: A Mixture of Experts Approach
Venue: arXiv cs.DC 2017
Year: 2017

Data analytic applications built upon big data processing frameworks such as Apache Spark are an important class of applications. Many of these applications are not latency-sensitive and thus can run as batch jobs in data centers. By running multiple applications on a computing host, task co-location can significantly improve the server utilization and system throughput. However, effective task co-location is a non-trivial task, as it requires an understanding of the computing resource requirement of the co-running applications, in order to determine what tasks, and how many of them, can be co-located. In this paper, we present a mixture-of-experts approach to model the memory behavior of Spark applications. We achieve this by learning, off-line, a range of specialized memory models on a range of typical applications; we then determine at runtime which of the memory models, or experts, best describes the memory behavior of the target application. We show that by accurately estimating the resource level that is needed, a co-location scheme can effectively determine how many applications can be co-located on the same host to improve the system throughput, by taking into consideration the memory and CPU requirements of co-running application tasks. Our technique is applied to a set of representative data analytic applications built upon the Apache Spark framework. We evaluated our approach for system throughput and average normalized turnaround time on a multi-core cluster. Our approach achieves over 83.9% of the performance delivered using an ideal memory predictor. We obtain, on average, 8.69x improvement on system throughput and a 49% reduction on turnaround time over executing application tasks in isolation, which translates to a 1.28x and 1.68x improvement over a state-of-the-art co-location scheme for system throughput and turnaround time respectively.
On the Parameterized Complexity of Red-Blue Points Separation
Venue: arXiv cs.CG 2017
Year: 2017

We study the following geometric separation problem: Given a set $R$ of red points and a set $B$ of blue points in the plane, find a minimum-size set of lines that separate $R$ from $B$. We show that, in its full generality, parameterized by the number of lines $k$ in the solution, the problem is unlikely to be solvable significantly faster than the brute-force $n^{O(k)}$-time algorithm, where $n$ is the total number of points. Indeed, we show that an algorithm running in time $f(k)n^{o(k/ \log k)}$, for any computable function $f$, would disprove ETH. Our reduction crucially relies on selecting lines from a set with a large number of different slopes (i.e., this number is not a function of $k$). Conjecturing that the problem variant where the lines are required to be axis-parallel is FPT in the number of lines, we show the following preliminary result. Separating $R$ from $B$ with a minimum-size set of axis-parallel lines is FPT in the size of either set, and can be solved in time $O^*(9^{|B|})$ (assuming that $B$ is the smallest set).