OpenRaiser/Intern-Atlas huggingface dataset:
Multi-Dimensional Auction Mechanisms for Crowdsourced Mobile Video Streaming
Venue: arXiv cs.NI 2018
Year: 2018

Crowdsourced mobile video streaming enables nearby mobile video users to aggregate network resources to improve their video streaming performances. However, users are often selfish and may not be willing to cooperate without proper incentives. Designing an incentive mechanism for such a scenario is challenging due to the users' asynchronous downloading behaviors and their private valuations for multi-bitrate coded videos. In this work, we propose both single-object and multi-object multi-dimensional auction mechanisms, through which users sell the opportunities for downloading single and multiple video segments with multiple bitrates, respectively. Both auction mechanisms can achieves truthfulness (i.e, truthful private information revelation) and efficiency (i.e., social welfare maximization). Simulations with real traces show that crowdsourced mobile streaming facilitated by the auction mechanisms outperforms noncooperative stream ing by 48.6% (on average) in terms of social welfare. To evaluate the real-world performance, we also construct a demo system for crowdsourced mobile streaming and implement our proposed auction mechanism. Experiments over the demo system further show that those users who provide resources to others and those users who receive helps can increase their welfares by 15.5% and 35.4% (on average) via cooperation, respectively.
Network structure from rich but noisy data
Venue: arXiv cs.SI 2018
Year: 2018

Driven by growing interest in the sciences, industry, and among the broader public, a large number of empirical studies have been conducted in recent years of the structure of networks ranging from the internet and the world wide web to biological networks and social networks. The data produced by these experiments are often rich and multimodal, yet at the same time they may contain substantial measurement error. In practice, this means that the true network structure can differ greatly from naive estimates made from the raw data, and hence that conclusions drawn from those naive estimates may be significantly in error. In this paper we describe a technique that circumvents this problem and allows us to make optimal estimates of the true structure of networks in the presence of both richly textured data and significant measurement uncertainty. We give example applications to two different social networks, one derived from face-to-face interactions and one from self-reported friendships.
Incremental View Maintenance with Triple Lock Factorization Benefits
Venue: arXiv cs.DB 2018
Year: 2018

We introduce F-IVM, a unified incremental view maintenance (IVM) approach for a variety of tasks, including gradient computation for learning linear regression models over joins, matrix chain multiplication, and factorized evaluation of conjunctive queries. F-IVM is a higher-order IVM algorithm that reduces the maintenance of the given task to the maintenance of a hierarchy of increasingly simpler views. The views are functions mapping keys, which are tuples of input data values, to payloads, which are elements from a task-specific ring. Whereas the computation over the keys is the same for all tasks, the computation over the payloads depends on the task. F-IVM achieves efficiency by factorizing the computation of the keys, payloads, and updates. We implemented F-IVM as an extension of DBToaster. We show in a range of scenarios that it can outperform classical first-order IVM, DBToaster's fully recursive higher-order IVM, and plain recomputation by orders of magnitude while using less memory.
Selfish Cops and Active Robber: Multi-Player Pursuit Evasion on Graphs
Venue: arXiv cs.DM 2018
Year: 2018

We introduce and study the game of "Selfish Cops and Active Robber" (SCAR) which can be seen as an multiplayer variant of the "classic" two-player Cops and Robbers (CR) game. In classic CR all cops are controlled by a single player, who has no preference over which cop captures the robber. In SCAR, on the other hand, each of N-1 cops is controlled by a separate player, and a single robber is controlled by the N-th player; and the capturing cop player receives a higher reward than the non-capturing ones. Consequently, SCAR is an N-player pursuit game on graphs, in which each cop player has an increased motive to be the one who captures the robber. The focus of our study is the existence and properties of SCAR Nash Equilibria (NE). In particular, we prove that SCAR always has one NE in deterministic positional strategies and (for N greater than two) another in deterministic nonpositional strategies. Furthermore, we study conditions which, at equilibrium, guarantee either capture or escape of the robber and show that (because of the antagonism between the "selfish" cop players) the robber may, in certain SCAR configurations, be captured later than he would be in classic CR, or even not captured at all. Finally we define the selfish cop number of a graph and study its connection to the classic cop number.
Overcoming Catastrophic Forgetting by Incremental Moment Matching
Venue: arXiv cs.LG 2018
Year: 2018

Catastrophic forgetting is a problem of neural networks that loses the information of the first task after training the second task. Here, we propose a method, i.e. incremental moment matching (IMM), to resolve this problem. IMM incrementally matches the moment of the posterior distribution of the neural network which is trained on the first and the second task, respectively. To make the search space of posterior parameter smooth, the IMM procedure is complemented by various transfer learning techniques including weight transfer, L2-norm of the old and the new parameter, and a variant of dropout with the old parameter. We analyze our approach on a variety of datasets including the MNIST, CIFAR-10, Caltech-UCSD-Birds, and Lifelog datasets. The experimental results show that IMM achieves state-of-the-art performance by balancing the information between an old and a new network.
How Compressible are Innovation Processes?
Venue: arXiv cs.IT 2018
Year: 2018

The sparsity and compressibility of finite-dimensional signals are of great interest in fields such as compressed sensing. The notion of compressibility is also extended to infinite sequences of i.i.d. or ergodic random variables based on the observed error in their nonlinear k-term approximation. In this work, we use the entropy measure to study the compressibility of continuous-domain innovation processes (alternatively known as white noise). Specifically, we define such a measure as the entropy limit of the doubly quantized (time and amplitude) process. This provides a tool to compare the compressibility of various innovation processes. It also allows us to identify an analogue of the concept of "entropy dimension" which was originally defined by Rényi for random variables. Particular attention is given to stable and impulsive Poisson innovation processes. Here, our results recognize Poisson innovations as the more compressible ones with an entropy measure far below that of stable innovations. While this result departs from the previous knowledge regarding the compressibility of fat-tailed distributions, our entropy measure ranks stable innovations according to their tail decay.
Inverse Reinforcement Learning from Summary Data
Venue: arXiv cs.LG 2018
Year: 2018

Inverse reinforcement learning (IRL) aims to explain observed strategic behavior by fitting reinforcement learning models to behavioral data. However, traditional IRL methods are only applicable when the observations are in the form of state-action paths. This assumption may not hold in many real-world modeling settings, where only partial or summarized observations are available. In general, we may assume that there is a summarizing function $σ$, which acts as a filter between us and the true state-action paths that constitute the demonstration. Some initial approaches to extending IRL to such situations have been presented, but with very specific assumptions about the structure of $σ$, such as that only certain state observations are missing. This paper instead focuses on the most general case of the problem, where no assumptions are made about the summarizing function, except that it can be evaluated. We demonstrate that inference is still possible. The paper presents exact and approximate inference algorithms that allow full posterior inference, which is particularly important for assessing parameter uncertainty in this challenging inference situation. Empirical scalability is demonstrated to reasonably sized problems, and practical applicability is demonstrated by estimating the posterior for a cognitive science RL model based on an observed user's task completion time only.
Grouped Convolutional Neural Networks for Multivariate Time Series
Venue: arXiv cs.LG 2018
Year: 2018

Analyzing multivariate time series data is important for many applications such as automated control, fault diagnosis and anomaly detection. One of the key challenges is to learn latent features automatically from dynamically changing multivariate input. In visual recognition tasks, convolutional neural networks (CNNs) have been successful to learn generalized feature extractors with shared parameters over the spatial domain. However, when high-dimensional multivariate time series is given, designing an appropriate CNN model structure becomes challenging because the kernels may need to be extended through the full dimension of the input volume. To address this issue, we present two structure learning algorithms for deep CNN models. Our algorithms exploit the covariance structure over multiple time series to partition input volume into groups. The first algorithm learns the group CNN structures explicitly by clustering individual input sequences. The second algorithm learns the group CNN structures implicitly from the error backpropagation. In experiments with two real-world datasets, we demonstrate that our group CNNs outperform existing CNN based regression methods.
Birecurrent sets
Venue: arXiv cs.FL 2018
Year: 2018

A set is called recurrent if its minimal automaton is strongly connected and birecurrent if it is recurrent as well as its reversal. We prove a series of results concerning birecurrent sets. It is already known that any birecurrent set is completely reducible (that is, such that the minimal representation of its characteristic series is completely reducible). The main result of this paper characterizes completely reducible sets as linear combinations of birecurrent sets
Enter the Matrix: Safely Interruptible Autonomous Systems via Virtualization
Venue: arXiv cs.AI 2018
Year: 2018

Autonomous systems that operate around humans will likely always rely on kill switches that stop their execution and allow them to be remote-controlled for the safety of humans or to prevent damage to the system. It is theoretically possible for an autonomous system with sufficient sensor and effector capability that learn online using reinforcement learning to discover that the kill switch deprives it of long-term reward and thus learn to disable the switch or otherwise prevent a human operator from using the switch. This is referred to as the big red button problem. We present a technique that prevents a reinforcement learning agent from learning to disable the kill switch. We introduce an interruption process in which the agent's sensors and effectors are redirected to a virtual simulation where it continues to believe it is receiving reward. We illustrate our technique in a simple grid world environment.
User Interface Design Smell: Automatic Detection and Refactoring of Blob Listeners
Venue: arXiv cs.SE 2018
Year: 2018

User Interfaces (UIs) intensively rely on event-driven programming: widgets send UI events, which capture users' interactions, to dedicated objects called controllers. Controllers use several UI listeners that handle these events to produce UI commands. First, we reveal the presence of design smells in the code that describes and controls UIs. Second, we demonstrate that specific code analyses are necessary to analyze and refactor UI code, because of its coupling with the rest of the code. We conducted an empirical study on four large Java Swing and SWT open-source software systems. We study to what extent the number of UI commands that a UI listener can produce has an impact on the change- and fault-proneness of the UI listener code. We develop a static code analysis for detecting UI commands in the code. We identify a new type of design smell, called Blob Listener that characterizes UI listeners that can produce more than two UI commands. We propose a systematic static code analysis procedure that searches for Blob Listeners that we implement in InspectorGuidget. We conducted experiments on the four software systems for which we manually identified 53 instances of Blob Listener. InspectorGuidget successfully detected 52 Blob Listeners out of 53. The results exhibit a precision of 81.25% and a recall of 98.11%. We then developed a semi-automatically and behavior-preserving refactoring process to remove Blob Listeners. 49.06% of the 53 Blob Listeners were automatically refactored. Patches for JabRef, and FreeCol have been accepted and merged. Discussions with developers of the four software systems assess the relevance of the Blob Listener. This work shows that UI code also suffers from design smells that have to be identified and characterized. We argue that studies have to be conducted to find other UI design smells and tools that analyze UI code must be developed.
Parallelism, Concurrency and Distribution in Constraint Handling Rules: A Survey
Venue: arXiv cs.DC 2018
Year: 2018

Constraint Handling Rules is an effective concurrent declarative programming language and a versatile computational logic formalism. CHR programs consist of guarded reactive rules that transform multisets of constraints. One of the main features of CHR is its inherent concurrency. Intuitively, rules can be applied to parts of a multiset in parallel. In this comprehensive survey, we give an overview of concurrent and parallel as well as distributed CHR semantics, standard and more exotic, that have been proposed over the years at various levels of refinement. These semantics range from the abstract to the concrete. They are related by formal soundness results. Their correctness is established as correspondence between parallel and sequential computations. We present common concise sample CHR programs that have been widely used in experiments and benchmarks. We review parallel CHR implementations in software and hardware. The experimental results obtained show a consistent parallel speedup. Most implementations are available online. The CHR formalism can also be used to implement and reason with models for concurrency. To this end, the Software Transaction Model, the Actor Model, Colored Petri Nets and the Join-Calculus have been faithfully encoded in CHR. Under consideration in Theory and Practice of Logic Programming (TPLP).
Optimal Precoders for Tracking the AoD and AoA of a mm-Wave Path
Venue: arXiv cs.IT 2018
Year: 2018

In millimeter-wave channels, most of the received energy is carried by a few paths. Traditional precoders sweep the angle-of-departure (AoD) and angle-of-arrival (AoA) space with directional precoders to identify directions with largest power. Such precoders are heuristic and lead to sub-optimal AoD/AoA estimation. We derive optimal precoders, minimizing the Cramér-Rao bound (CRB) of the AoD/AoA, assuming a fully digital architecture at the transmitter and spatial filtering of a single path. The precoders are found by solving a suitable convex optimization problem. We demonstrate that the accuracy can be improved by at least a factor of two over traditional precoders, and show that there is an optimal number of distinct precoders beyond which the CRB does not improve.
Upper Bounds on the Runtime of the Univariate Marginal Distribution Algorithm on OneMax
Venue: arXiv cs.NE 2018
Year: 2018

A runtime analysis of the Univariate Marginal Distribution Algorithm (UMDA) is presented on the OneMax function for wide ranges of its parameters $μ$ and $λ$. If $μ\ge c\log n$ for some constant $c>0$ and $λ=(1+Θ(1))μ$, a general bound $O(μn)$ on the expected runtime is obtained. This bound crucially assumes that all marginal probabilities of the algorithm are confined to the interval $[1/n,1-1/n]$. If $μ\ge c' \sqrt{n}\log n$ for a constant $c'>0$ and $λ=(1+Θ(1))μ$, the behavior of the algorithm changes and the bound on the expected runtime becomes $O(μ\sqrt{n})$, which typically even holds if the borders on the marginal probabilities are omitted. The results supplement the recently derived lower bound $Ω(μ\sqrt{n}+n\log n)$ by Krejca and Witt (FOGA 2017) and turn out as tight for the two very different values $μ=c\log n$ and $μ=c'\sqrt{n}\log n$. They also improve the previously best known upper bound $O(n\log n\log\log n)$ by Dang and Lehre (GECCO 2015).
Comparison of ontology alignment systems across single matching task via the McNemar's test
Venue: arXiv cs.AI 2018
Year: 2018

Ontology alignment is widely-used to find the correspondences between different ontologies in diverse fields.After discovering the alignments,several performance scores are available to evaluate them.The scores typically require the identified alignment and a reference containing the underlying actual correspondences of the given ontologies.The current trend in the alignment evaluation is to put forward a new score(e.g., precision, weighted precision, etc.)and to compare various alignments by juxtaposing the obtained scores. However,it is substantially provocative to select one measure among others for comparison.On top of that, claiming if one system has a better performance than one another cannot be substantiated solely by comparing two scalars.In this paper,we propose the statistical procedures which enable us to theoretically favor one system over one another.The McNemar's test is the statistical means by which the comparison of two ontology alignment systems over one matching task is drawn.The test applies to a 2x2 contingency table which can be constructed in two different ways based on the alignments,each of which has their own merits/pitfalls.The ways of the contingency table construction and various apposite statistics from the McNemar's test are elaborated in minute detail.In the case of having more than two alignment systems for comparison, the family-wise error rate is expected to happen. Thus, the ways of preventing such an error are also discussed.A directed graph visualizes the outcome of the McNemar's test in the presence of multiple alignment systems.From this graph, it is readily understood if one system is better than one another or if their differences are imperceptible.The proposed statistical methodologies are applied to the systems participated in the OAEI 2016 anatomy track, and also compares several well-known similarity metrics for the same matching problem.
A Good Practice Towards Top Performance of Face Recognition: Transferred Deep Feature Fusion
Venue: arXiv cs.CV 2018
Year: 2018

Unconstrained face recognition performance evaluations have traditionally focused on Labeled Faces in the Wild (LFW) dataset for imagery and the YouTubeFaces (YTF) dataset for videos in the last couple of years. Spectacular progress in this field has resulted in saturation on verification and identification accuracies for those benchmark datasets. In this paper, we propose a unified learning framework named Transferred Deep Feature Fusion (TDFF) targeting at the new IARPA Janus Benchmark A (IJB-A) face recognition dataset released by NIST face challenge. The IJB-A dataset includes real-world unconstrained faces from 500 subjects with full pose and illumination variations which are much harder than the LFW and YTF datasets. Inspired by transfer learning, we train two advanced deep convolutional neural networks (DCNN) with two different large datasets in source domain, respectively. By exploring the complementarity of two distinct DCNNs, deep feature fusion is utilized after feature extraction in target domain. Then, template specific linear SVMs is adopted to enhance the discrimination of framework. Finally, multiple matching scores corresponding different templates are merged as the final results. This simple unified framework exhibits excellent performance on IJB-A dataset. Based on the proposed approach, we have submitted our IJB-A results to National Institute of Standards and Technology (NIST) for official evaluation. Moreover, by introducing new data and advanced neural architecture, our method outperforms the state-of-the-art by a wide margin on IJB-A dataset.
The 2017 DAVIS Challenge on Video Object Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

We present the 2017 DAVIS Challenge on Video Object Segmentation, a public dataset, benchmark, and competition specifically designed for the task of video object segmentation. Following the footsteps of other successful initiatives, such as ILSVRC and PASCAL VOC, which established the avenue of research in the fields of scene classification and semantic segmentation, the DAVIS Challenge comprises a dataset, an evaluation methodology, and a public competition with a dedicated workshop co-located with CVPR 2017. The DAVIS Challenge follows up on the recent publication of DAVIS (Densely-Annotated VIdeo Segmentation), which has fostered the development of several novel state-of-the-art video object segmentation techniques. In this paper we describe the scope of the benchmark, highlight the main characteristics of the dataset, define the evaluation metrics of the competition, and present a detailed analysis of the results of the participants to the challenge.
Proportional Approval Voting, Harmonic k-median, and Negative Association
Venue: arXiv cs.DS 2018
Year: 2018

We study a generic framework that provides a unified view on two important classes of problems: (i) extensions of the k-median problem where clients are interested in having multiple facilities in their vicinity (e.g., due to the fact that, with some small probability, the closest facility might be malfunctioning and so might not be available for using), and (ii) finding winners according to some appealing multiwinner election rules, i.e., election system aimed for choosing representatives bodies, such as parliaments, based on preferences of a population of voters over individual candidates. Each problem in our framework is associated with a vector of weights: we show that the approximability of the problem depends on structural properties of these vectors. We specifically focus on the harmonic sequence of weights for which the objective function interpreted in a multiwinner election setup reflects to the well-known Proportional Approval Voting (PAV) rule. Our main result is that, due to the specific (harmonic) structure of weights, the problem allows constant factor approximation. This is surprising since the problem can be interpreted as a variant of the k-median problem where we do not assume that the connection costs satisfy the triangle inequality. The algorithm we propose is based on dependent rounding [Srinivasan, FOCS'01] applied to the solution of a natural LP-relaxation of the problem. The rounding process is well known to produce distributions over integral solutions satisfying Negative Correlation (NC), which is usually sufficient for the analysis of approximation guarantees offered by rounding procedures. In our analysis, however, we need to use the fact that the carefully implemented rounding process satisfies a stronger property, called Negative Association (NA), which allows us to apply standard concentration bounds for conditional random variables.