OpenRaiser/Intern-Atlas huggingface dataset:
Gradual System F
Venue: arXiv cs.PL 2020
Year: 2020

Bringing the benefits of gradual typing to a language with parametric polymorphism like System F, while preserving relational parametricity, has proven extremely challenging: first attempts were formulated a decade ago, and several designs have been recently proposed, with varying syntax, behavior, and properties. Starting from a detailed review of the challenges and tensions that affect the design of gradual parametric languages, this work presents an extensive account of the semantics and metatheory of GSF, a gradual counterpart of System F. In doing so, we also report on the extent to which the Abstracting Gradual Typing methodology can help us derive such a language. Among gradual parametric languages that follow the syntax of System F, GSF achieves a unique combination of properties. We clearly establish the benefits and limitations of the language, and discuss several extensions of GSF towards a practical programming language.
Push-Down Trees: Optimal Self-Adjusting Complete Trees
Venue: arXiv cs.DS 2020
Year: 2020

This paper studies a fundamental algorithmic problem related to the design of demand-aware networks: networks whose topologies adjust toward the traffic patterns they serve, in an online manner. The goal is to strike a tradeoff between the benefits of such adjustments (shorter routes) and their costs (reconfigurations). In particular, we consider the problem of designing a self-adjusting tree network which serves single-source, multi-destination communication. The problem has interesting connections to self-adjusting datastructures. We present two constant-competitive online algorithms for this problem, one randomized and one deterministic. Our approach is based on a natural notion of Most Recently Used (MRU) tree, maintaining a working set. We prove that the working set is a cost lower bound for any online algorithm, and then present a randomized algorithm RANDOM-PUSH which approximates such an MRU tree at low cost, by pushing less recently used communication partners down the tree, along a random walk. Our deterministic algorithm MOVE-HALF does not directly maintain an MRU tree, but its cost is still proportional to the cost of an MRU tree, and also matches the working set lower bound.
Quantum Pontryagin Principle under Continuous Measurements and Feedback
Venue: arXiv cs.SY 2020
Year: 2020

In this note we develop the theory of the quantum Pontryagin principle for continuous measurements and feedback. The analysis is carried out under the assumption of compatible events in the output channel. The plant is a quantum system, which generally is in a mixed state, coupled to a continuous measurement channel. The Pontryagin Maximum Principle is derived in both the Schrödinger picture and Heisenberg picture, in particular in statistical moment coordinates. To avoid solving stochastic equations we derive a LQG scheme which is more suitable for control purposes.
Friend-Based Ranking
Venue: arXiv cs.SI 2020
Year: 2020

We analyze the design of a mechanism to extract a ranking of individuals according to a unidimensional characteristic, such as ability or need. Individuals, connected on a social network, only have local information about the ranking. We show that a planner can construct an ex post incentive compatible and efficient mechanism if and only if every pair of friends has a friend in common. We characterize the windmill network as the sparsest social network for which the planner can always construct a complete ranking.
Low-Resource Text Classification using Domain-Adversarial Learning
Venue: arXiv cs.CL 2020
Year: 2020

Deep learning techniques have recently shown to be successful in many natural language processing tasks forming state-of-the-art systems. They require, however, a large amount of annotated data which is often missing. This paper explores the use of domain-adversarial learning as a regularizer to avoid overfitting when training domain invariant features for deep, complex neural networks in low-resource and zero-resource settings in new target domains or languages. In case of new languages, we show that monolingual word vectors can be directly used for training without prealignment. Their projection into a common space can be learnt ad-hoc at training time reaching the final performance of pretrained multilingual word vectors.
MIDV-500: A Dataset for Identity Documents Analysis and Recognition on Mobile Devices in Video Stream
Venue: arXiv cs.CV 2020
Year: 2020

A lot of research has been devoted to identity documents analysis and recognition on mobile devices. However, no publicly available datasets designed for this particular problem currently exist. There are a few datasets which are useful for associated subtasks but in order to facilitate a more comprehensive scientific and technical approach to identity document recognition more specialized datasets are required. In this paper we present a Mobile Identity Document Video dataset (MIDV-500) consisting of 500 video clips for 50 different identity document types with ground truth which allows to perform research in a wide scope of document analysis problems. The paper presents characteristics of the dataset and evaluation results for existing methods of face detection, text line recognition, and document fields data extraction. Since an important feature of identity documents is their sensitiveness as they contain personal data, all source document images used in MIDV-500 are either in public domain or distributed under public copyright licenses. The main goal of this paper is to present a dataset. However, in addition and as a baseline, we present evaluation results for existing methods for face detection, text line recognition, and document data extraction, using the presented dataset. (The dataset is available for download at ftp://smartengines.com/midv-500/.)
Nash Flows over Time with Spillback and Kinematic Waves
Venue: arXiv cs.GT 2020
Year: 2020

Modeling traffic in road networks is a widely studied but challenging problem, especially under the assumption that drivers act selfishly. A common approach is the deterministic queuing model, for which the structure of dynamic equilibria has been studied extensively in the last couple of years. The basic idea is to model traffic by a continuous flow that travels over time through a network, in which the arcs are endowed with transit times and capacities. Whenever the flow rate exceeds the capacity the flow particles build up a queue. So far it was not possible to represent spillback or kinematic waves in this model. By introducing a storage capacity arcs can become full, and thus, might block preceding arcs, i.e., spillback occurs. Furthermore, we model kinematic waves by upstream moving flows over time representing the gaps between vehicles. We carry over the main results of the original model to our generalization, i.e., we characterize Nash flows over time by sequences of particular static flows, so-called spillback thin flows. Furthermore, we give a constructive proof for the existence of dynamic equilibria, which suggests an algorithm for their computation. This solves an open problem stated by [13].
On Recovery Guarantees for One-Bit Compressed Sensing on Manifolds
Venue: arXiv cs.IT 2020
Year: 2020

This paper studies the problem of recovering a signal from one-bit compressed sensing measurements under a manifold model; that is, assuming that the signal lies on or near a manifold of low intrinsic dimension. We provide a convex recovery method based on the Geometric Multi-Resolution Analysis and prove recovery guarantees with a near-optimal scaling in the intrinsic manifold dimension. Our method is the first tractable algorithm with such guarantees for this setting. The results are complemented by numerical experiments confirming the validity of our approach.
Language Preservation Problems in Parametric Timed Automata
Venue: arXiv cs.LO 2020
Year: 2020

Parametric timed automata (PTA) are a powerful formalism to model and reason about concurrent systems with some unknown timing delays. In this paper, we address the (untimed) language- and trace-preservation problems: given a reference parameter valuation, does there exist another parameter valuation with the same untimed language, or with the same set of traces? We show that these problems are undecidable both for general PTA and for the restricted class of L/U-PTA, even for integer-valued parameters, or over bounded time. On the other hand, we exhibit decidable subclasses: 1-clock PTA, and 1-parameter deterministic L-PTA and U-PTA. We also consider robust versions of these problems, where we additionally require that the language be preserved for all valuations between the reference valuation and the new valuation.
Online Label Aggregation: A Variational Bayesian Approach
Venue: arXiv cs.LG 2020
Year: 2020

Noisy labeled data is more a norm than a rarity for crowd sourced contents. It is effective to distill noise and infer correct labels through aggregation results from crowd workers. To ensure the time relevance and overcome slow responses of workers, online label aggregation is increasingly requested, calling for solutions that can incrementally infer true label distribution via subsets of data items. In this paper, we propose a novel online label aggregation framework, BiLA, which employs variational Bayesian inference method and designs a novel stochastic optimization scheme for incremental training. BiLA is flexible to accommodate any generating distribution of labels by the exact computation of its posterior distribution. We also derive the convergence bound of the proposed optimizer. We compare BiLA with the state of the art based on minimax entropy, neural networks and expectation maximization algorithms, on synthetic and real-world data sets. Our evaluation results on various online scenarios show that BiLA can effectively infer the true labels, with an error rate reduction of at least 10 to 1.5 percent points for synthetic and real-world datasets, respectively.
Efficient Probabilistic Inference in the Quest for Physics Beyond the Standard Model
Venue: arXiv cs.LG 2020
Year: 2020

We present a novel probabilistic programming framework that couples directly to existing large-scale simulators through a cross-platform probabilistic execution protocol, which allows general-purpose inference engines to record and control random number draws within simulators in a language-agnostic way. The execution of existing simulators as probabilistic programs enables highly interpretable posterior inference in the structured model defined by the simulator code base. We demonstrate the technique in particle physics, on a scientifically accurate simulation of the tau lepton decay, which is a key ingredient in establishing the properties of the Higgs boson. Inference efficiency is achieved via inference compilation where a deep recurrent neural network is trained to parameterize proposal distributions and control the stochastic simulator in a sequential importance sampling scheme, at a fraction of the computational cost of a Markov chain Monte Carlo baseline.
Towards Privacy-Preserving Visual Recognition via Adversarial Training: A Pilot Study
Venue: arXiv cs.CV 2020
Year: 2020

This paper aims to improve privacy-preserving visual recognition, an increasingly demanded feature in smart camera applications, by formulating a unique adversarial training framework. The proposed framework explicitly learns a degradation transform for the original video inputs, in order to optimize the trade-off between target task performance and the associated privacy budgets on the degraded video. A notable challenge is that the privacy budget, often defined and measured in task-driven contexts, cannot be reliably indicated using any single model performance, because a strong protection of privacy has to sustain against any possible model that tries to hack privacy information. Such an uncommon situation has motivated us to propose two strategies, i.e., budget model restarting and ensemble, to enhance the generalization of the learned degradation on protecting privacy against unseen hacker models. Novel training strategies, evaluation protocols, and result visualization methods have been designed accordingly. Two experiments on privacy-preserving action recognition, with privacy budgets defined in various ways, manifest the compelling effectiveness of the proposed framework in simultaneously maintaining high target task (action recognition) performance while suppressing the privacy breach risk.
Set Cover with Delay -- Clairvoyance is not Required
Venue: arXiv cs.DS 2020
Year: 2020

In most online problems with delay, clairvoyance (i.e. knowing the future delay of a request upon its arrival) is required for polylogarithmic competitiveness. In this paper, we show that this is not the case for set cover with delay (SCD) -- specifically, we present the first non-clairvoyant algorithm, which is $O(\log n \log m)$-competitive, where $n$ is the number of elements and $m$ is the number of sets. This matches the best known result for the classic online set cover (a special case of non-clairvoyant SCD). Moreover, clairvoyance does not allow for significant improvement - we present lower bounds of $Ω(\sqrt{\log n})$ and $Ω(\sqrt{\log m})$ for SCD which apply for the clairvoyant case. In addition, the competitiveness of our algorithm does not depend on the number of requests. Such a guarantee on the size of the universe alone was not previously known even for the clairvoyant case - the only previously-known algorithm (due to Carrasco et al.) is clairvoyant, with competitiveness that grows with the number of requests. For the special case of vertex cover with delay, we show a simpler, deterministic algorithm which is $3$-competitive (and also non-clairvoyant).
Adaptive Body Area Networks Using Kinematics and Biosignals
Venue: arXiv cs.NI 2020
Year: 2020

The increasing penetration of wearable and implantable devices necessitates energy-efficient and robust ways of connecting them to each other and to the cloud. However, the wireless channel around the human body poses unique challenges such as a high and variable path-loss caused by frequent changes in the relative node positions as well as the surrounding environment. An adaptive wireless body area network (WBAN) scheme is presented that reconfigures the network by learning from body kinematics and biosignals. It has very low overhead since these signals are already captured by the WBAN sensor nodes to support their basic functionality. Periodic channel fluctuations in activities like walking can be exploited by reusing accelerometer data and scheduling packet transmissions at optimal times. Network states can be predicted based on changes in observed biosignals to reconfigure the network parameters in real time. A realistic body channel emulator that evaluates the path-loss for everyday human activities was developed to assess the efficacy of the proposed techniques. Simulation results show up to 41% improvement in packet delivery ratio (PDR) and up to 27% reduction in power consumption by intelligent scheduling at lower transmission power levels. Moreover, experimental results on a custom test-bed demonstrate an average PDR increase of 20% and 18% when using our adaptive EMG- and heart-rate-based transmission power control methods, respectively. The channel emulator and simulation code is made publicly available at https://github.com/a-moin/wban-pathloss.
Infinite Mixture of Inverted Dirichlet Distributions
Venue: arXiv cs.LG 2020
Year: 2020

In this work, we develop a novel Bayesian estimation method for the Dirichlet process (DP) mixture of the inverted Dirichlet distributions, which has been shown to be very flexible for modeling vectors with positive elements. The recently proposed extended variational inference (EVI) framework is adopted to derive an analytically tractable solution. The convergency of the proposed algorithm is theoretically guaranteed by introducing single lower bound approximation to the original objective function in the VI framework. In principle, the proposed model can be viewed as an infinite inverted Dirichelt mixture model (InIDMM) that allows the automatic determination of the number of mixture components from data. Therefore, the problem of pre-determining the optimal number of mixing components has been overcome. Moreover, the problems of over-fitting and under-fitting are avoided by the Bayesian estimation approach. Comparing with several recently proposed DP-related methods, the good performance and effectiveness of the proposed method have been demonstrated with both synthesized data and real data evaluations.
Dropout-GAN: Learning from a Dynamic Ensemble of Discriminators
Venue: arXiv cs.LG 2020
Year: 2020

We propose to incorporate adversarial dropout in generative multi-adversarial networks, by omitting or dropping out, the feedback of each discriminator in the framework with some probability at the end of each batch. Our approach forces the single generator not to constrain its output to satisfy a single discriminator, but, instead, to satisfy a dynamic ensemble of discriminators. We show that this leads to a more generalized generator, promoting variety in the generated samples and avoiding the common mode collapse problem commonly experienced with generative adversarial networks (GANs). We further provide evidence that the proposed framework, named Dropout-GAN, promotes sample diversity both within and across epochs, eliminating mode collapse and stabilizing training.
What am I Searching for: Zero-shot Target Identity Inference in Visual Search
Venue: arXiv cs.CV 2020
Year: 2020

Can we infer intentions from a person's actions? As an example problem, here we consider how to decipher what a person is searching for by decoding their eye movement behavior. We conducted two psychophysics experiments where we monitored eye movements while subjects searched for a target object. We defined the fixations falling on non-target objects as "error fixations". Using those error fixations, we developed a model (InferNet) to infer what the target was. InferNet uses a pre-trained convolutional neural network to extract features from the error fixations and computes a similarity map between the error fixations and all locations across the search image. The model consolidates the similarity maps across layers and integrates these maps across all error fixations. InferNet successfully identifies the subject's goal and outperforms competitive null models, even without any object-specific training on the inference task.
Dirichlet Mixture Model based VQ Performance Prediction for Line Spectral Frequency
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we continue our previous work on the Dirichlet mixture model (DMM)-based VQ to derive the performance bound of the LSF VQ. The LSF parameters are transformed into the $Δ$LSF domain and the underlying distribution of the $Δ$LSF parameters are modelled by a DMM with finite number of mixture components. The quantization distortion, in terms of the mean squared error (MSE), is calculated with the high rate theory. The mapping relation between the perceptually motivated log spectral distortion (LSD) and the MSE is empirically approximated by a polynomial. With this mapping function, the minimum required bit rate for transparent coding of the LSF is estimated.
Statistical Speech Model Description with VMF Mixture Model
Venue: arXiv cs.SD 2020
Year: 2020

In this paper, we present the LSF parameters by a unit vector form, which has directional characteristics. The underlying distribution of this unit vector variable is modeled by a von Mises-Fisher mixture model (VMM). With the high rate theory, the optimal inter-component bit allocation strategy is proposed and the distortion-rate (D-R) relation is derived for the VMM based-VQ (VVQ). Experimental results show that the VVQ outperforms our recently introduced DVQ and the conventional GVQ.
Instance-Dependent PU Learning by Bayesian Optimal Relabeling
Venue: arXiv cs.LG 2020
Year: 2020

When learning from positive and unlabelled data, it is a strong assumption that the positive observations are randomly sampled from the distribution of $X$ conditional on $Y = 1$, where X stands for the feature and Y the label. Most existing algorithms are optimally designed under the assumption. However, for many real-world applications, the observed positive examples are dependent on the conditional probability $P(Y = 1|X)$ and should be sampled biasedly. In this paper, we assume that a positive example with a higher $P(Y = 1|X)$ is more likely to be labelled and propose a probabilistic-gap based PU learning algorithms. Specifically, by treating the unlabelled data as noisy negative examples, we could automatically label a group positive and negative examples whose labels are identical to the ones assigned by a Bayesian optimal classifier with a consistency guarantee. The relabelled examples have a biased domain, which is remedied by the kernel mean matching technique. The proposed algorithm is model-free and thus do not have any parameters to tune. Experimental results demonstrate that our method works well on both generated and real-world datasets.
Fair Packing and Covering on a Relative Scale
Venue: arXiv cs.DS 2020
Year: 2020

Fair resource allocation is a fundamental optimization problem with applications in operations research, networking, and economic and game theory. Research in these areas has led to the general acceptance of a class of $α$-fair utility functions parameterized by $α\in [0, \infty]$. We consider $α$-fair packing -- the problem of maximizing $α$-fair utilities under positive linear constraints -- and provide a simple first-order method for solving it with relative-error guarantees. The method has a significantly lower convergence time than the state of the art, and to analyze it, we leverage the Approximate Duality Gap Technique, which provides an intuitive interpretation of the convergence argument. Finally, we introduce a natural counterpart of $α$-fairness for minimization problems and motivate its usage in the context of fair task allocation. This generalization yields $α$-fair covering problems, for which we provide the first near-linear-time solvers with relative-error guarantees.
Coaxioms: flexible coinductive definitions by inference systems
Venue: arXiv cs.LO 2020
Year: 2020

We introduce a generalized notion of inference system to support more flexible interpretations of recursive definitions. Besides axioms and inference rules with the usual meaning, we allow also coaxioms, which are, intuitively, axioms which can only be applied "at infinite depth" in a proof tree. Coaxioms allow us to interpret recursive definitions as fixed points which are not necessarily the least, nor the greatest one, whose existence is guaranteed by a smooth extension of classical results. This notion nicely subsumes standard inference systems and their inductive and coinductive interpretation, thus allowing formal reasoning in cases where the inductive and coinductive interpretation do not provide the intended meaning, but are rather mixed together.
The Buck-Passing Game
Venue: arXiv cs.GT 2020
Year: 2020

We consider a game in which players are the vertices of a directed graph. Initially, Nature chooses one player according to some fixed distribution and gives her a buck, which represents the request to perform a chore. After completing the task, the player passes the buck to one of her out-neighbors in the graph. The procedure is repeated indefinitely and each player's cost is the asymptotic expected frequency of times that she receives the buck. We consider a deterministic and a stochastic version of the game depending on how players select the neighbor to pass the buck. In both cases we prove the existence of pure equilibria that do not depend on the initial distribution; this is achieved by showing the existence of a generalized ordinal potential. We then use the price of anarchy and price of stability to measure fairness of these equilibria. We also study a buck-holding variant of the game in which players want to maximize the frequency of times they hold the buck, which includes the PageRank game as a special case.