OpenRaiser/Intern-Atlas huggingface dataset:
Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
Venue: arXiv cs.LG 2021
Year: 2021

We develop several new algorithms for learning Markov Decision Processes in an infinite-horizon average-reward setting with linear function approximation. Using the optimism principle and assuming that the MDP has a linear structure, we first propose a computationally inefficient algorithm with optimal $\widetilde{O}(\sqrt{T})$ regret and another computationally efficient variant with $\widetilde{O}(T^{3/4})$ regret, where $T$ is the number of interactions. Next, taking inspiration from adversarial linear bandits, we develop yet another efficient algorithm with $\widetilde{O}(\sqrt{T})$ regret under a different set of assumptions, improving the best existing result by Hao et al. (2020) with $\widetilde{O}(T^{2/3})$ regret. Moreover, we draw a connection between this algorithm and the Natural Policy Gradient algorithm proposed by Kakade (2002), and show that our analysis improves the sample complexity bound recently given by Agarwal et al. (2020).
IoTrace: A Flexible, Efficient, and Privacy-Preserving IoT-enabled Architecture for Contact Tracing
Venue: arXiv cs.NI 2021
Year: 2021

Contact tracing promises to help fight the spread of Covid-19 via an early detection of possible contagion events. To this end, most existing solutions share the following architecture: smartphones continuously broadcast random beacons that are intercepted by nearby devices and stored into their local contact logs. In this paper, we propose an IoT-enabled architecture for contact tracing that relaxes the smartphone-centric assumption, and provide a solution that enjoys the following features: (i) it reduces the overhead on the end-user to the bare minimum -- the mobile device only broadcasts its beacons; (ii) it provides the user with a degree of privacy not achieved by competing solutions -- even in the most privacy adverse scenario, the solution provides k-anonymity; and, (iii) it is flexible: the same architecture can be configured to support several models -- ranging from the fully decentralized to the fully centralized ones -- and the system parameters can be tuned to support the tracing of several social interaction models. We also highlight open issues and discuss a number of future research directions.
T-BFA: Targeted Bit-Flip Adversarial Weight Attack
Venue: arXiv cs.LG 2021
Year: 2021

Traditional Deep Neural Network (DNN) security is mostly related to the well-known adversarial input example attack. Recently, another dimension of adversarial attack, namely, attack on DNN weight parameters, has been shown to be very powerful. As a representative one, the Bit-Flip-based adversarial weight Attack (BFA) injects an extremely small amount of faults into weight parameters to hijack the executing DNN function. Prior works of BFA focus on un-targeted attack that can hack all inputs into a random output class by flipping a very small number of weight bits stored in computer memory. This paper proposes the first work of targeted BFA based (T-BFA) adversarial weight attack on DNNs, which can intentionally mislead selected inputs to a target output class. The objective is achieved by identifying the weight bits that are highly associated with classification of a targeted output through a class-dependent weight bit ranking algorithm. Our proposed T-BFA performance is successfully demonstrated on multiple DNN architectures for image classification tasks. For example, by merely flipping 27 out of 88 million weight bits of ResNet-18, our T-BFA can misclassify all the images from 'Hen' class into 'Goose' class (i.e., 100 % attack success rate) in ImageNet dataset, while maintaining 59.35 % validation accuracy. Moreover, we successfully demonstrate our T-BFA attack in a real computer prototype system running DNN computation, with Ivy Bridge-based Intel i7 CPU and 8GB DDR3 memory.
What and Where: Learn to Plug Adapters via NAS for Multi-Domain Learning
Venue: arXiv cs.LG 2021
Year: 2021

As an important and challenging problem, multi-domain learning (MDL) typically seeks for a set of effective lightweight domain-specific adapter modules plugged into a common domain-agnostic network. Usually, existing ways of adapter plugging and structure design are handcrafted and fixed for all domains before model learning, resulting in the learning inflexibility and computational intensiveness. With this motivation, we propose to learn a data-driven adapter plugging strategy with Neural Architecture Search (NAS), which automatically determines where to plug for those adapter modules. Furthermore, we propose a NAS-adapter module for adapter structure design in a NAS-driven learning scheme, which automatically discovers effective adapter module structures for different domains. Experimental results demonstrate the effectiveness of our MDL model against existing approaches under the conditions of comparable performance.
Algorithms for Persuasion with Limited Communication
Venue: arXiv cs.GT 2021
Year: 2021

The Bayesian persuasion paradigm of strategic communication models interaction between a privately-informed agent, called the sender, and an ignorant but rational agent, called the receiver. The goal is typically to design a (near-)optimal communication (or signaling) scheme for the sender. It enables the sender to disclose information to the receiver in a way as to incentivize her to take an action that is preferred by the sender. Finding the optimal signaling scheme is known to be computationally difficult in general. This hardness is further exacerbated when there is also a constraint on the size of the message space, leading to NP-hardness of approximating the optimal sender utility within any constant factor. In this paper, we show that in several natural and prominent cases the optimization problem is tractable even when the message space is limited. In particular, we study signaling under a symmetry or an independence assumption on the distribution of utility values for the actions. For symmetric distributions, we provide a novel characterization of the optimal signaling scheme. It results in a polynomial-time algorithm to compute an optimal scheme for many compactly represented symmetric distributions. In the independent case, we design a constant-factor approximation algorithm, which stands in marked contrast to the hardness of approximation in the general case.
From climate change to pandemics: decision science can help scientists have impact
Venue: arXiv cs.CY 2021
Year: 2021

Scientific knowledge and advances are a cornerstone of modern society. They improve our understanding of the world we live in and help us navigate global challenges including emerging infectious diseases, climate change and the biodiversity crisis. For any scientist, whether they work primarily in fundamental knowledge generation or in the applied sciences, it is important to understand how science fits into a decision-making framework. Decision science is a field that aims to pinpoint evidence-based management strategies. It provides a framework for scientists to directly impact decisions or to understand how their work will fit into a decision process. Decision science is more than undertaking targeted and relevant scientific research or providing tools to assist policy makers; it is an approach to problem formulation, bringing together mathematical modelling, stakeholder values and logistical constraints to support decision making. In this paper we describe decision science, its use in different contexts, and highlight current gaps in methodology and application. The COVID-19 pandemic has thrust mathematical models into the public spotlight, but it is one of innumerable examples in which modelling informs decision making. Other examples include models of storm systems (eg. cyclones, hurricanes) and climate change. Although the decision timescale in these examples differs enormously (from hours to decades), the underlying decision science approach is common across all problems. Bridging communication gaps between different groups is one of the greatest challenges for scientists. However, by better understanding and engaging with the decision-making processes, scientists will have greater impact and make stronger contributions to important societal problems.
K-Shot Contrastive Learning of Visual Features with Multiple Instance Augmentations
Venue: arXiv cs.CV 2021
Year: 2021

In this paper, we propose the $K$-Shot Contrastive Learning (KSCL) of visual features by applying multiple augmentations to investigate the sample variations within individual instances. It aims to combine the advantages of inter-instance discrimination by learning discriminative features to distinguish between different instances, as well as intra-instance variations by matching queries against the variants of augmented samples over instances. Particularly, for each instance, it constructs an instance subspace to model the configuration of how the significant factors of variations in $K$-shot augmentations can be combined to form the variants of augmentations. Given a query, the most relevant variant of instances is then retrieved by projecting the query onto their subspaces to predict the positive instance class. This generalizes the existing contrastive learning that can be viewed as a special one-shot case. An eigenvalue decomposition is performed to configure instance subspaces, and the embedding network can be trained end-to-end through the differentiable subspace configuration. Experiment results demonstrate the proposed $K$-shot contrastive learning achieves superior performances to the state-of-the-art unsupervised methods.
Covert Identification over Binary-Input Discrete Memoryless Channels
Venue: arXiv cs.IT 2021
Year: 2021

This paper considers the covert identification problem in which a sender aims to reliably convey an identification (ID) message to a set of receivers via a binary-input discrete memoryless channel (BDMC), and simultaneously to guarantee that the communication is covert with respect to a warden who monitors the communication via another independent BDMC. We prove a square-root law for the covert identification problem. This states that an ID message of size \exp(\exp(Θ(\sqrt{n}))) can be transmitted over n channel uses. We then characterize the exact pre-constant in the Θ(.) notation. This constant is referred to as the covert identification capacity. We show that it equals the recently developed covert capacity in the standard covert communication problem, and somewhat surprisingly, the covert identification capacity can be achieved without any shared key between the sender and receivers. The achievability proof relies on a random coding argument with pulse-position modulation (PPM), coupled with a second stage which performs code refinements. The converse proof relies on an expurgation argument as well as results for channel resolvability with stringent input constraints.
Karl Marx and the Blockchain
Venue: arXiv cs.CY 2021
Year: 2021

Blockchain is often presented as a technological development; however, clearly it is not only that: the `Blockchain buzz' exists in the context of current social and political developments. In this essay, we analyse blockchain technology and its social and political context from a perspective of Marxist economic theory. Since arguably the last great inflection point in society and technology was analysed by Marx in terms of labour and capital and since we seem to be experiencing a shift in the balance between these forces today, it makes sense to revisit the Marxist ideas and apply them to the current situation, to see how well they still apply and if necessary to update them for current events.
Automated Verification of Reactive and Concurrent Programs by Calculation
Venue: arXiv cs.LO 2021
Year: 2021

Reactive programs combine traditional sequential programming constructs with primitives to allow communication with other concurrent agents. They are ubiquitous in modern applications, ranging from components systems and web services, to cyber-physical systems and autonomous robots. In this paper, we present an algebraic verification strategy for concurrent reactive programs, with a large or infinite state space. We define novel operators to characterise interactions and state updates, and an associated equational theory. With this we can calculate a reactive program's denotational semantics, and thereby facilitate automated proof. Of note is our reasoning support for iterative programs with reactive invariants, based on Kleene algebra, and for parallel composition. We illustrate our strategy by verifying a reactive buffer. Our laws and strategy are mechanised in Isabelle/UTP, our implementation of Hoare and He's Unifying Theories of Programming (UTP) framework, to provide soundness guarantees and practical verification support.
Information Behavior During the Covid-19 Crisis in German-Speaking Countries
Venue: arXiv cs.CY 2021
Year: 2021

This paper explores the impact of the Covid-19 crisis at the level of individual information behavior, based on an online survey among 308 participants from the German-speaking countries Austria, Germany and Switzerland in April and May 2020. The results show first that the Covid-19 crisis has led to an increased demand for reliable information. This goes alongside a significant increased use of public broadcasting, newspapers and information provided by public organizations. Second, the majority (84%) of the participants reported being satisfied with the information supply during the Covid-19 crisis. Participants who were less satisfied with the information supply used reliable sources significantly less frequently, specifically public television, national newspapers and information provided by public organizations. Third, the amount of Covid-19-related information led some participants to a feeling of information overload, which resulted in a reduction of information seeking and media use.
GLIMG: Global and Local Item Graphs for Top-N Recommender Systems
Venue: arXiv cs.IR 2021
Year: 2021

Graph-based recommendation models work well for top-N recommender systems due to their capability to capture the potential relationships between entities. However, most of the existing methods only construct a single global item graph shared by all the users and regrettably ignore the diverse tastes between different user groups. Inspired by the success of local models for recommendation, this paper provides the first attempt to investigate multiple local item graphs along with a global item graph for graph-based recommendation models. We argue that recommendation on global and local graphs outperforms that on a single global graph or multiple local graphs. Specifically, we propose a novel graph-based recommendation model named GLIMG (Global and Local IteM Graphs), which simultaneously captures both the global and local user tastes. By integrating the global and local graphs into an adapted semi-supervised learning model, users' preferences on items are propagated globally and locally. Extensive experimental results on real-world datasets show that our proposed method consistently outperforms the state-of-the art counterparts on the top-N recommendation task.
The Tractability of SHAP-Score-Based Explanations over Deterministic and Decomposable Boolean Circuits
Venue: arXiv cs.AI 2021
Year: 2021

Scores based on Shapley values are widely used for providing explanations to classification results over machine learning models. A prime example of this is the influential SHAP-score, a version of the Shapley value that can help explain the result of a learned model on a specific entity by assigning a score to every feature. While in general computing Shapley values is a computationally intractable problem, it has recently been claimed that the SHAP-score can be computed in polynomial time over the class of decision trees. In this paper, we provide a proof of a stronger result over Boolean models: the SHAP-score can be computed in polynomial time over deterministic and decomposable Boolean circuits. Such circuits, also known as tractable Boolean circuits, generalize a wide range of Boolean circuits and binary decision diagrams classes, including binary decision trees, Ordered Binary Decision Diagrams (OBDDs) and Free Binary Decision Diagrams (FBDDs). We also establish the computational limits of the notion of SHAP-score by observing that, under a mild condition, computing it over a class of Boolean models is always polynomially as hard as the model counting problem for that class. This implies that both determinism and decomposability are essential properties for the circuits that we consider, as removing one or the other renders the problem of computing the SHAP-score intractable (namely, #P-hard).
A Progressive Approach to Scalar Field Topology
Venue: arXiv cs.GR 2021
Year: 2021

This paper introduces progressive algorithms for the topological analysis of scalar data. Our approach is based on a hierarchical representation of the input data and the fast identification of topologically invariant vertices, which are vertices that have no impact on the topological description of the data and for which we show that no computation is required as they are introduced in the hierarchy. This enables the definition of efficient coarse-to-fine topological algorithms, which leverage fast update mechanisms for ordinary vertices and avoid computation for the topologically invariant ones. We demonstrate our approach with two examples of topological algorithms (critical point extraction and persistence diagram computation), which generate interpretable outputs upon interruption requests and which progressively refine them otherwise. Experiments on real-life datasets illustrate that our progressive strategy, in addition to the continuous visual feedback it provides, even improves run time performance with regard to non-progressive algorithms and we describe further accelerations with shared-memory parallelism. We illustrate the utility of our approach in batch-mode and interactive setups, where it respectively enables the control of the execution time of complete topological pipelines as well as previews of the topological features found in a dataset, with progressive updates delivered within interactive times.
Robust Template Matching via Hierarchical Convolutional Features from a Shape Biased CNN
Venue: arXiv cs.CV 2021
Year: 2021

Finding a template in a search image is an important task underlying many computer vision applications. Recent approaches perform template matching in a deep feature-space, produced by a convolutional neural network (CNN), which is found to provide more tolerance to changes in appearance. In this article we investigate if enhancing the CNN's encoding of shape information can produce more distinguishable features that improve the performance of template matching. This investigation results in a new template matching method that produces state-of-the-art results on a standard benchmark. To confirm these results we also create a new benchmark and show that the proposed method also outperforms existing techniques on this new dataset. Our code and dataset is available at: https://github.com/iminfine/Deep-DIM.
Topology Density Map for Urban Data Visualization and Analysis
Venue: arXiv cs.HC 2021
Year: 2021

Density map is an effective visualization technique for depicting the scalar field distribution in 2D space. Conventional methods for constructing density maps are mainly based on Euclidean distance, limiting their applicability in urban analysis that shall consider road network and urban traffic. In this work, we propose a new method named Topology Density Map, targeting for accurate and intuitive density maps in the context of urban environment. Based on the various constraints of road connections and traffic conditions, the method first constructs a directed acyclic graph (DAG) that propagates nonlinear scalar fields along 1D road networks. Next, the method extends the scalar fields to a 2D space by identifying key intersecting points in the DAG, dividing the underlying territory into planar regions using a weighted Voronoi diagram, and calculating the scalar fields for every point. Two case studies demonstrate that the Topology Density Map supplies accurate information to users and provides an intuitive visualization for decision making. An interview with domain experts demonstrates the feasibility, usability, and effectiveness of our method.
Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization
Venue: arXiv cs.DS 2021
Year: 2021

We study the problem of estimating the mean of a distribution in high dimensions when either the samples are adversarially corrupted or the distribution is heavy-tailed. Recent developments in robust statistics have established efficient and (near) optimal procedures for both settings. However, the algorithms developed on each side tend to be sophisticated and do not directly transfer to the other, with many of them having ad-hoc or complicated analyses. In this paper, we provide a meta-problem and a duality theorem that lead to a new unified view on robust and heavy-tailed mean estimation in high dimensions. We show that the meta-problem can be solved either by a variant of the Filter algorithm from the recent literature on robust estimation or by the quantum entropy scoring scheme (QUE), due to Dong, Hopkins and Li (NeurIPS '19). By leveraging our duality theorem, these results translate into simple and efficient algorithms for both robust and heavy-tailed settings. Furthermore, the QUE-based procedure has run-time that matches the fastest known algorithms on both fronts. Our analysis of Filter is through the classic regret bound of the multiplicative weights update method. This connection allows us to avoid the technical complications in previous works and improve upon the run-time analysis of a gradient-descent-based algorithm for robust mean estimation by Cheng, Diakonikolas, Ge and Soltanolkotabi (ICML '20).
Orientation-Preserving Vectorized Distance Between Curves
Venue: arXiv cs.CG 2021
Year: 2021

We introduce an orientation-preserving landmark-based distance for continuous curves, which can be viewed as an alternative to the \Frechet or Dynamic Time Warping distances. This measure retains many of the properties of those measures, and we prove some relations, but can be interpreted as a Euclidean distance in a particular vector space. Hence it is significantly easier to use, faster for general nearest neighbor queries, and allows easier access to classification results than those measures. It is based on the \emph{signed} distance function to the curves or other objects from a fixed set of landmark points. We also prove new stability properties with respect to the choice of landmark points, and along the way introduce a concept called signed local feature size (slfs) which parameterizes these notions. Slfs explains the complexity of shapes such as non-closed curves where the notion of local orientation is in dispute -- but is more general than the well-known concept of (unsigned) local feature size, and is for instance infinite for closed simple curves. Altogether, this work provides a novel, simple, and powerful method for oriented shape similarity and analysis.