OpenRaiser/Intern-Atlas huggingface dataset:
Utility Design for Distributed Resource Allocation -- Part I: Characterizing and Optimizing the Exact Price of Anarchy
Venue: arXiv cs.GT 2019
Year: 2019

Game theory has emerged as a fruitful paradigm for the design of networked multiagent systems. A fundamental component of this approach is the design of agents' utility functions so that their self-interested maximization results in a desirable collective behavior. In this work we focus on a well-studied class of distributed resource allocation problems where each agent is requested to select a subset of resources with the goal of optimizing a given system-level objective. Our core contribution is the development of a novel framework to tightly characterize the worst case performance of any resulting Nash equilibrium (price of anarchy) as a function of the chosen agents' utility functions. Leveraging this result, we identify how to design such utilities so as to optimize the price of anarchy through a tractable linear program. This provides us with a priori performance certificates applicable to any existing learning algorithm capable of driving the system to an equilibrium. Part II of this work specializes these results to submodular and supermodular objectives, discusses the complexity of computing Nash equilibria, and provides multiple illustrations of the theoretical findings.
Sample-Efficient Reinforcement Learning with Stochastic Ensemble Value Expansion
Venue: arXiv cs.LG 2019
Year: 2019

Integrating model-free and model-based approaches in reinforcement learning has the potential to achieve the high performance of model-free algorithms with low sample complexity. However, this is difficult because an imperfect dynamics model can degrade the performance of the learning algorithm, and in sufficiently complex environments, the dynamics model will almost always be imperfect. As a result, a key challenge is to combine model-based approaches with model-free learning in such a way that errors in the model do not degrade performance. We propose stochastic ensemble value expansion (STEVE), a novel model-based technique that addresses this issue. By dynamically interpolating between model rollouts of various horizon lengths for each individual example, STEVE ensures that the model is only utilized when doing so does not introduce significant errors. Our approach outperforms model-free baselines on challenging continuous control benchmarks with an order-of-magnitude increase in sample efficiency, and in contrast to previous model-based approaches, performance does not degrade in complex environments.
Optimizing Execution of Dynamic Goal-Directed Robot Movements with Learning Control
Venue: arXiv cs.RO 2019
Year: 2019

Highly dynamic tasks that require large accelerations and precise tracking usually rely on accurate models and/or high gain feedback. While kinematic optimization allows for efficient representation and online generation of hitting trajectories, learning to track such dynamic movements with inaccurate models remains an open problem. In particular, stability issues surrounding the learning performance, in the iteration domain, can prevent the successful implementation of model based learning approaches. To achieve accurate tracking for such tasks in a stable and efficient way, we propose a new adaptive Iterative Learning Control (ILC) algorithm that is implemented efficiently using a recursive approach. Moreover, covariance estimates of model matrices are used to exercise caution during learning. We evaluate the performance of the proposed approach in extensive simulations and in our robotic table tennis platform, where we show how the striking performance of two seven degree of freedom anthropomorphic robot arms can be optimized. Our implementation on the table tennis platform compares favorably with high-gain PD-control, model-free ILC (simple PD feedback type) and model-based ILC without cautious adaptation.
A Concept Specification and Abstraction-based Semantic Representation: Addressing the Barriers to Rule-based Machine Translation
Venue: arXiv cs.CL 2019
Year: 2019

Rule-based machine translation is more data efficient than the big data-based machine translation approaches, making it appropriate for languages with low bilingual corpus resources -- i.e., minority languages. However, the rule-based approach has declined in popularity relative to its big data cousins primarily because of the extensive training and labour required to define the language rules. To address this, we present a semantic representation that 1) treats all bits of meaning as individual concepts that 2) modify or further specify one another to build a network that relates entities in space and time. Also, the representation can 3) encapsulate propositions and thereby define concepts in terms of other concepts, supporting the abstraction of underlying linguistic and ontological details. These features afford an exact, yet intuitive semantic representation aimed at handling the great variety in language and reducing labour and training time. The proposed natural language generation, parsing, and translation strategies are also amenable to probabilistic modeling and thus to learning the necessary rules from example data.
Memory Augmented Policy Optimization for Program Synthesis and Semantic Parsing
Venue: arXiv cs.LG 2019
Year: 2019

We present Memory Augmented Policy Optimization (MAPO), a simple and novel way to leverage a memory buffer of promising trajectories to reduce the variance of policy gradient estimate. MAPO is applicable to deterministic environments with discrete actions, such as structured prediction and combinatorial optimization tasks. We express the expected return objective as a weighted sum of two terms: an expectation over the high-reward trajectories inside the memory buffer, and a separate expectation over trajectories outside the buffer. To make an efficient algorithm of MAPO, we propose: (1) memory weight clipping to accelerate and stabilize training; (2) systematic exploration to discover high-reward trajectories; (3) distributed sampling from inside and outside of the memory buffer to scale up training. MAPO improves the sample efficiency and robustness of policy gradient, especially on tasks with sparse rewards. We evaluate MAPO on weakly supervised program synthesis from natural language (semantic parsing). On the WikiTableQuestions benchmark, we improve the state-of-the-art by 2.6%, achieving an accuracy of 46.3%. On the WikiSQL benchmark, MAPO achieves an accuracy of 74.9% with only weak supervision, outperforming several strong baselines with full supervision. Our source code is available at https://github.com/crazydonkey200/neural-symbolic-machines
Blockchain as a Service: A Decentralized and Secure Computing Paradigm
Venue: arXiv cs.CR 2019
Year: 2019

Thanks to the advances in machine learning, data-driven analysis tools have become valuable solutions for various applications. However, there still remain essential challenges to develop effective data-driven methods because of the need to acquire a large amount of data and to have sufficient computing power to handle the data. In many instances these challenges are addressed by relying on a dominant cloud computing vendor, but, although commercial cloud vendors provide valuable platforms for data analytics, they can suffer from a lack of transparency, security, and privacy-perservation. Furthermore, reliance on cloud servers prevents applying big data analytics in environments where the computing power is scattered. To address these challenges, a decentralize, secure, and privacy-preserving computing paradigm is proposed to enable an asynchronized cooperative computing process amongst scattered and untrustworthy computing nodes that may have limited computing power and computing intelligence. This paradigm is designed by exploring blockchain, decentralized learning, homomorphic encryption, and software defined networking(SDN) techniques. The performance of the proposed paradigm is evaluated via different scenarios in the simulation section.
Revisiting Distillation and Incremental Classifier Learning
Venue: arXiv cs.LG 2019
Year: 2019

One of the key differences between the learning mechanism of humans and Artificial Neural Networks (ANNs) is the ability of humans to learn one task at a time. ANNs, on the other hand, can only learn multiple tasks simultaneously. Any attempts at learning new tasks incrementally cause them to completely forget about previous tasks. This lack of ability to learn incrementally, called Catastrophic Forgetting, is considered a major hurdle in building a true AI system. In this paper, our goal is to isolate the truly effective existing ideas for incremental learning from those that only work under certain conditions. To this end, we first thoroughly analyze the current state of the art (iCaRL) method for incremental learning and demonstrate that the good performance of the system is not because of the reasons presented in the existing literature. We conclude that the success of iCaRL is primarily due to knowledge distillation and recognize a key limitation of knowledge distillation, i.e, it often leads to bias in classifiers. Finally, we propose a dynamic threshold moving algorithm that is able to successfully remove this bias. We demonstrate the effectiveness of our algorithm on CIFAR100 and MNIST datasets showing near-optimal results. Our implementation is available at https://github.com/Khurramjaved96/incremental-learning.
A Formal Approach to Open Multiparty Interactions
Venue: arXiv cs.FL 2019
Year: 2019

We present a process algebra aimed at describing interactions that are multiparty, i.e. that may involve more than two processes and that are open, i.e. the number of the processes they involve is not fixed or known a priori. Here we focus on the theory of a core version of a process calculus, without message passing, called Core Network Algebra (CNA). In CNA communication actions are given not in terms of channels but in terms of chains of links that record the source and the target ends of each hop of interactions. The operational semantics of our calculus mildly extends the one of CCS. The abstract semantics is given in the style of bisimulation but requires some ingenuity. Remarkably, the abstract semantics is a congruence for all operators of CNA and also with respect to substitutions, which is not the case for strong bisimilarity in CCS. As a motivating and running example, we illustrate the model of a simple software defined network infrastructure.
Catalog of Formalized Application Integration Patterns
Venue: arXiv cs.SE 2019
Year: 2019

Enterprise application integration (EAI) solutions are the centrepiece of current enterprise IT architectures (e.g., cloud and mobile computing, business networks), however, require the formalization of their building blocks, represented by integration patterns, verification and optimization. This work serves as an instructive pattern formalization catalog that leads to the formalization of all currently known integration patterns. Therefore, we explain the classification of the underlying requirements of the pattern semantics and formalize representative patterns from the different categories, by realizing them in timed db-net. In this way, the catalog will allow for the addition of future patterns by assigning them to a category and applying the described formalism.
Streamable Regular Transductions
Venue: arXiv cs.FL 2019
Year: 2019

Motivated by real-time monitoring and data processing applications, we develop a formal theory of quantitative queries for streaming data that can be evaluated efficiently. We consider the model of unambiguous Cost Register Automata (CRAs), which are machines that combine finite-state control (for identifying regular patterns) with a finite set of data registers (for computing numerical aggregates). The definition of CRAs is parameterized by the collection of numerical operations that can be applied to the registers. These machines give rise to the class of streamable regular transductions (SR), and to the class of streamable linear regular transductions (SLR) when the register updates are copyless, i.e. every register appears at most once the right-hand-side expressions of the updates. We give a logical characterization of the class SR (resp., SLR) using MSO-definable transformations from strings to DAGs (resp., trees) without backward edges. Additionally, we establish that the two classes SR and SLR are closed under operations that are relevant for designing query languages. Finally, we study the relationship with weighted automata (WA), and show that CRAs over a suitably chosen set of operations correspond to WA, thus establishing that WA are a special case of CRAs.
Sequential Voting with Confirmation Network
Venue: arXiv cs.GT 2019
Year: 2019

We discuss voting scenarios in which the set of voters (agents) and the set of alternatives are the same; that is, voters select a single representative from among themselves. Such a scenario happens, for instance, when a committee selects a chairperson, or when peer researchers select a prize winner. Our model assumes that each voter either renders worthy (confirms) or unworthy any other agent. We further assume that the prime goal of each agent is to be selected himself. Only if that is not feasible, will he try to get one of those that he confirms selected. In this paper, we investigate the open-sequential voting system in the above model. We consider both plurality (where each voter has one vote) and approval (where a voter may vote for any subset). Our results show that it is possible to find scenarios in which the selected agent is much less popular than the optimal (most popular) agent. We prove, however, that in the case of approval voting, the ratio between their popularity is always bounded from above by 2. In the case of plurality voting, we show that there are cases in which some of the equilibria give an unbounded ratio, but there always exists at least one equilibrium with ratio 2 at most.
Perception of Image Features in Post-Mortem Iris Recognition: Humans vs Machines
Venue: arXiv cs.CV 2019
Year: 2019

Post-mortem iris recognition can offer an additional forensic method of personal identification. However, in contrary to already well-established human examination of fingerprints, making iris recognition human-interpretable is harder, and therefore it has never been applied in forensic proceedings. There is no strong consensus among biometric experts which iris features, especially those in iris images acquired post-mortem, are the most important for human experts solving an iris recognition task. This paper explores two ways of broadening this knowledge: (a) with an eye tracker, the salient features used by humans comparing iris images on a screen are extracted, and (b) class-activation maps produced by the convolutional neural network solving the iris recognition task are analyzed. Both humans and deep learning-based solutions were examined with the same set of iris image pairs. This made it possible to compare the attention maps and conclude that (a) deep learning-based method can offer human-interpretable decisions backed by visual explanations pointing a human examiner to salient regions, and (b) in many cases humans and a machine used different features, what means that a deep learning-based method can offer a complementary support to human experts. This paper offers the first known to us human-interpretable comparison of machine-based and human-based post-mortem iris recognition, and the trained models annotating salient iris image regions.
With Friends Like These, Who Needs Adversaries?
Venue: arXiv cs.CV 2019
Year: 2019

The vulnerability of deep image classification networks to adversarial attack is now well known, but less well understood. Via a novel experimental analysis, we illustrate some facts about deep convolutional networks for image classification that shed new light on their behaviour and how it connects to the problem of adversaries. In short, the celebrated performance of these networks and their vulnerability to adversarial attack are simply two sides of the same coin: the input image-space directions along which the networks are most vulnerable to attack are the same directions which they use to achieve their classification performance in the first place. We develop this result in two main steps. The first uncovers the fact that classes tend to be associated with specific image-space directions. This is shown by an examination of the class-score outputs of nets as functions of 1D movements along these directions. This provides a novel perspective on the existence of universal adversarial perturbations. The second is a clear demonstration of the tight coupling between classification performance and vulnerability to adversarial attack within the spaces spanned by these directions. Thus, our analysis resolves the apparent contradiction between accuracy and vulnerability. It provides a new perspective on much of the prior art and reveals profound implications for efforts to construct neural nets that are both accurate and robust to adversarial attack.
Tracking the Evolution of Words with Time-reflective Text Representations
Venue: arXiv cs.CL 2019
Year: 2019

More than 80% of today's data is unstructured in nature, and these unstructured datasets evolve over time. A large part of these datasets are text documents generated by media outlets, scholarly articles in digital libraries, findings from scientific and professional communities, and social media. Vector space models were developed to analyze text data using data mining and machine learning algorithms. While ample vector space models exist for text data, the evolutionary aspect of ever-changing text corpora is still missing in vector-based representations. The advent of word embeddings has enabled us to create a contextual vector space, but the embeddings fail to consider the temporal aspects of the feature space successfully. This paper presents an approach to include temporal aspects in feature spaces. The inclusion of the time aspect in the feature space provides vectors for every natural language element, such as words or entities, at every timestamp. Such temporal word vectors allow us to track how the meaning of a word changes over time, by studying the changes in its neighborhood. Moreover, a time-reflective text representation will pave the way to a new set of text analytic abilities involving time series for text collections. In this paper, we present a time-reflective vector space model for temporal text data that is able to capture short and long-term changes in the meaning of words. We compare our approach with the limited literature on dynamic embeddings. We present qualitative and quantitative evaluations using the tracking of semantic evolution as the target application.
Hydranet: Data Augmentation for Regression Neural Networks
Venue: arXiv cs.CV 2019
Year: 2019

Deep learning techniques are often criticized to heavily depend on a large quantity of labeled data. This problem is even more challenging in medical image analysis where the annotator expertise is often scarce. We propose a novel data-augmentation method to regularize neural network regressors that learn from a single global label per image. The principle of the method is to create new samples by recombining existing ones. We demonstrate the performance of our algorithm on two tasks: estimation of the number of enlarged perivascular spaces in the basal ganglia, and estimation of white matter hyperintensities volume. We show that the proposed method improves the performance over more basic data augmentation. The proposed method reached an intraclass correlation coefficient between ground truth and network predictions of 0.73 on the first task and 0.84 on the second task, only using between 25 and 30 scans with a single global label per scan for training. With the same number of training scans, more conventional data augmentation methods could only reach intraclass correlation coefficients of 0.68 on the first task, and 0.79 on the second task.
An Approximate Message Passing Framework for Side Information
Venue: arXiv cs.IT 2019
Year: 2019

Approximate message passing (AMP) methods have gained recent traction in sparse signal recovery. Additional information about the signal, or \emph{side information} (SI), is commonly available and can aid in efficient signal recovery. This work presents an AMP-based framework that exploits SI and can be readily implemented in various settings for which the SI results in separable distributions. To illustrate the simplicity and applicability of our approach, this framework is applied to a Bernoulli-Gaussian (BG) model and a time-varying birth-death-drift (BDD) signal model, motivated by applications in channel estimation. We develop a suite of algorithms, called AMP-SI, and derive denoisers for the BDD and BG models. Numerical evidence demonstrating the advantages of our approach are presented alongside empirical evidence of the accuracy of a proposed state evolution.
On the Complexity of Value Iteration
Venue: arXiv cs.FL 2019
Year: 2019

Value iteration is a fundamental algorithm for solving Markov Decision Processes (MDPs). It computes the maximal $n$-step payoff by iterating $n$ times a recurrence equation which is naturally associated to the MDP. At the same time, value iteration provides a policy for the MDP that is optimal on a given finite horizon $n$. In this paper, we settle the computational complexity of value iteration. We show that, given a horizon $n$ in binary and an MDP, computing an optimal policy is EXP-complete, thus resolving an open problem that goes back to the seminal 1987 paper on the complexity of MDPs by Papadimitriou and Tsitsiklis. As a stepping stone, we show that it is EXP-complete to compute the $n$-fold iteration (with $n$ in binary) of a function given by a straight-line program over the integers with $\max$ and $+$ as operators.
Heuristics as conceptual lens for understanding and studying the usage of bibliometrics in research evaluation
Venue: arXiv cs.DL 2019
Year: 2019

While bibliometrics are widely used for research evaluation purposes, a common theoretical framework for conceptually understanding, empirically studying, and effectively teaching its usage is lacking. In this paper, we outline such a framework: the fast-and-frugal heuristics research program, proposed originally in the context of the cognitive and decision sciences, lends itself particularly well for understanding and investigating the usage of bibliometrics in research evaluations. Such evaluations represent judgments under uncertainty in which typically not all possible options, their consequences, and those consequences' probabilities of occurring may be known. In these situations of incomplete information, candidate descriptive and prescriptive models of human behavior are heuristics. Heuristics are simple strategies that, by exploiting the structure of environments, can aid people to make smart decisions. Relying on heuristics does not mean trading off accuracy against effort: while reducing complexity, heuristics can yield better decisions than more information-greedy procedures in many decision environments. The prescriptive power of heuristics is documented in a cross-disciplinary literature, cutting across medicine, crime, business, sports, and other domains. We outline the fast-and-frugal heuristics research program, provide examples of past empirical work on heuristics outside the field of bibliometrics, explain why heuristics may be especially suitable for studying the usage of bibliometrics, and propose a corresponding conceptual framework.