OpenRaiser/Intern-Atlas huggingface dataset:
Leveraging cross-platform data to improve automated hate speech detection
Venue: arXiv cs.CL 2021
Year: 2021

Hate speech is increasingly prevalent online, and its negative outcomes include increased prejudice, extremism, and even offline hate crime. Automatic detection of online hate speech can help us to better understand these impacts. However, while the field has recently progressed through advances in natural language processing, challenges still remain. In particular, most existing approaches for hate speech detection focus on a single social media platform in isolation. This limits both the use of these models and their validity, as the nature of language varies from platform to platform. Here we propose a new cross-platform approach to detect hate speech which leverages multiple datasets and classification models from different platforms and trains a superlearner that can combine existing and novel training data to improve detection and increase model applicability. We demonstrate how this approach outperforms existing models, and achieves good performance when tested on messages from novel social media platforms not included in the original training data.
Serverless Streaming for Emerging Media: Towards 5G Network-Driven Cost Optimization
Venue: arXiv cs.NI 2021
Year: 2021

Immersive 3D media is an emerging type of media that captures, encodes and reconstructs the 3D appearance of people and objects, with applications in tele-presence, teleconference, entertainment, gaming and other fields. In this paper, we discuss a novel concept of live 3D immersive media streaming in a serverless setting. In particular, we present a novel network-centric adaptive streaming framework which deviates from a traditional client-based adaptive streaming used in 2D video. In our framework, the decisions for the production of the transcoding profiles are taken in a centralized manner, by considering consumer metrics vs provisioning costs and inferring an expected consumer quality of experience and behaviour based on them. In addition, we demonstrate that a naive application of the serverless paradigm might be sub optimal under some common immersive 3D media scenarios.
A Generic Strategy Improvement Method for Simple Stochastic Games
Venue: arXiv cs.GT 2021
Year: 2021

We present a generic strategy iteration algorithm (GSIA) to find an optimal strategy of a simple stochastic game (SSG). We prove the correctness of GSIA, and derive a general complexity bound, which implies and improves on the results of several articles. First, we remove the assumption that the SSG is stopping, which is usually obtained by a polynomial blowup of the game. Second, we prove a tight bound on the denominator of the values associated to a strategy, and use it to prove that all strategy iteration algorithms are in fact fixed parameter tractable in the number of random vertices. All known strategy iteration algorithms can be seen as instances of GSIA, which allows to analyze the complexity of converge from below by Condon and to propose a class of algorithms generalising Gimbert and Horn's algorithm. These algorithms require less than $r!$ iterations in general and less iterations than the current best deterministic algorithm for binary SSGs given by Ibsen-Jensen and Miltersen.
A Game Theoretic Framework for Surplus Food Distribution in Smart Cities and Beyond
Venue: arXiv cs.GT 2021
Year: 2021

Food waste is a major challenge for the present world. It is the precursor to several socioeconomic problems that are plaguing the modern society. To counter the same and to, simultaneously, stand by the undernourished, surplus food redistribution has surfaced as a viable solution. Information and Communications Technology (ICT)-mediated food redistribution is a highly scalable approach and it percolates into the masses far better. Even if ICT is not brought into the picture, the presence of food surplus redistribution in developing countries like India is scarce and is limited to only a few of the major cities. The discussion of a surplus food redistribution framework under strategic settings is a less discussed topic around the globe. This paper aims at addressing a surplus food redistribution framework under strategic settings, thereby facilitating a smoother exchange of surplus food in the smart cities of developing countries, and beyond. As ICT is seamlessly available in smart cities, the paper aims to focus the framework in these cities. However, this can be extended beyond the smart cities to places with greater human involvement.
Optimal Static Mutation Strength Distributions for the $(1+λ)$ Evolutionary Algorithm on OneMax
Venue: arXiv cs.NE 2021
Year: 2021

Most evolutionary algorithms have parameters, which allow a great flexibility in controlling their behavior and adapting them to new problems. To achieve the best performance, it is often needed to control some of the parameters during optimization, which gave rise to various parameter control methods. In recent works, however, similar advantages have been shown, and even proven, for sampling parameter values from certain, often heavy-tailed, fixed distributions. This produced a family of algorithms currently known as "fast evolution strategies" and "fast genetic algorithms". However, only little is known so far about the influence of these distributions on the performance of evolutionary algorithms, and about the relationships between (dynamic) parameter control and (static) parameter sampling. We contribute to the body of knowledge by presenting, for the first time, an algorithm that computes the optimal static distributions, which describe the mutation operator used in the well-known simple $(1+λ)$ evolutionary algorithm on a classic benchmark problem OneMax. We show that, for large enough population sizes, such optimal distributions may be surprisingly complicated and counter-intuitive. We investigate certain properties of these distributions, and also evaluate the performance regrets of the $(1+λ)$ evolutionary algorithm using commonly used mutation distributions.
MISO-wiLDCosts: Multi Information Source Optimization with Location Dependent Costs
Venue: arXiv cs.LG 2021
Year: 2021

This paper addresses black-box optimization over multiple information sources whose both fidelity and query cost change over the search space, that is they are location dependent. The approach uses: (i) an Augmented Gaussian Process, recently proposed in multi-information source optimization as a single model of the objective function over search space and sources, and (ii) a Gaussian Process to model the location-dependent cost of each source. The former is used into a Confidence Bound based acquisition function to select the next source and location to query, while the latter is used to penalize the value of the acquisition depending on the expected query cost for any source-location pair. The proposed approach is evaluated on a set of Hyperparameters Optimization tasks, consisting of two Machine Learning classifiers and three datasets of different sizes.
Radar-to-Lidar: Heterogeneous Place Recognition via Joint Learning
Venue: arXiv cs.CV 2021
Year: 2021

Place recognition is critical for both offline mapping and online localization. However, current single-sensor based place recognition still remains challenging in adverse conditions. In this paper, a heterogeneous measurements based framework is proposed for long-term place recognition, which retrieves the query radar scans from the existing lidar maps. To achieve this, a deep neural network is built with joint training in the learning stage, and then in the testing stage, shared embeddings of radar and lidar are extracted for heterogeneous place recognition. To validate the effectiveness of the proposed method, we conduct tests and generalization experiments on the multi-session public datasets compared to other competitive methods. The experimental results indicate that our model is able to perform multiple place recognitions: lidar-to-lidar, radar-to-radar and radar-to-lidar, while the learned model is trained only once. We also release the source code publicly: https://github.com/ZJUYH/radar-to-lidar-place-recognition.
Principles of Explanation in Human-AI Systems
Venue: arXiv cs.AI 2021
Year: 2021

Explainable Artificial Intelligence (XAI) has re-emerged in response to the development of modern AI and ML systems. These systems are complex and sometimes biased, but they nevertheless make decisions that impact our lives. XAI systems are frequently algorithm-focused; starting and ending with an algorithm that implements a basic untested idea about explainability. These systems are often not tested to determine whether the algorithm helps users accomplish any goals, and so their explainability remains unproven. We propose an alternative: to start with human-focused principles for the design, testing, and implementation of XAI systems, and implement algorithms to serve that purpose. In this paper, we review some of the basic concepts that have been used for user-centered XAI systems over the past 40 years of research. Based on these, we describe the "Self-Explanation Scorecard", which can help developers understand how they can empower users by enabling self-explanation. Finally, we present a set of empirically-grounded, user-centered design principles that may guide developers to create successful explainable systems.
Content Placement in Networks of Similarity Caches
Venue: arXiv cs.NI 2021
Year: 2021

Similarity caching systems have recently attracted the attention of the scientific community, as they can be profitably used in many application contexts, like multimedia retrieval, advertising, object recognition, recommender systems and online content-match applications. In such systems, a user request for an object $o$, which is not in the cache, can be (partially) satisfied by a similar stored object $o$', at the cost of a loss of user utility. In this paper we make a first step into the novel area of similarity caching networks, where requests can be forwarded along a path of caches to get the best efficiency-accuracy tradeoff. The offline problem of content placement can be easily shown to be NP-hard, while different polynomial algorithms can be devised to approach the optimal solution in discrete cases. As the content space grows large, we propose a continuous problem formulation whose solution exhibits a simple structure in a class of tree topologies. We verify our findings using synthetic and realistic request traces.
On the Power and Limitations of Branch and Cut
Venue: arXiv cs.CC 2021
Year: 2021

The Stabbing Planes proof system was introduced to model the reasoning carried out in practical mixed integer programming solvers. As a proof system, it is powerful enough to simulate Cutting Planes and to refute the Tseitin formulas -- certain unsatisfiable systems of linear equations mod 2 -- which are canonical hard examples for many algebraic proof systems. In a recent (and surprising) result, Dadush and Tiwari showed that these short refutations of the Tseitin formulas could be translated into quasi-polynomial size and depth Cutting Planes proofs, refuting a long-standing conjecture. This translation raises several interesting questions. First, whether all Stabbing Planes proofs can be efficiently simulated by Cutting Planes. This would allow for the substantial analysis done on the Cutting Planes system to be lifted to practical mixed integer programming solvers. Second, whether the quasi-polynomial depth of these proofs is inherent to Cutting Planes. In this paper we make progress towards answering both of these questions. First, we show that any Stabbing Planes proof with bounded coefficients SP* can be translated into Cutting Planes. As a consequence of the known lower bounds for Cutting Planes, this establishes the first exponential lower bounds on SP*. Using this translation, we extend the result of Dadush and Tiwari to show that Cutting Planes has short refutations of any unsatisfiable system of linear equations over a finite field. Like the Cutting Planes proofs of Dadush and Tiwari, our refutations also incur a quasi-polynomial blow-up in depth, and we conjecture that this is inherent. As a step towards this conjecture, we develop a new geometric technique for proving lower bounds on the depth of Cutting Planes proofs. This allows us to establish the first lower bounds on the depth of Semantic Cutting Planes proofs of the Tseitin formulas.
Multi-Agent Coordination in Adversarial Environments through Signal Mediated Strategies
Venue: arXiv cs.MA 2021
Year: 2021

Many real-world scenarios involve teams of agents that have to coordinate their actions to reach a shared goal. We focus on the setting in which a team of agents faces an opponent in a zero-sum, imperfect-information game. Team members can coordinate their strategies before the beginning of the game, but are unable to communicate during the playing phase of the game. This is the case, for example, in Bridge, collusion in poker, and collusion in bidding. In this setting, model-free RL methods are oftentimes unable to capture coordination because agents' policies are executed in a decentralized fashion. Our first contribution is a game-theoretic centralized training regimen to effectively perform trajectory sampling so as to foster team coordination. When team members can observe each other actions, we show that this approach provably yields equilibrium strategies. Then, we introduce a signaling-based framework to represent team coordinated strategies given a buffer of past experiences. Each team member's policy is parametrized as a neural network whose output is conditioned on a suitable exogenous signal, drawn from a learned probability distribution. By combining these two elements, we empirically show convergence to coordinated equilibria in cases where previous state-of-the-art multi-agent RL algorithms did not.
Bounded Memory Active Learning through Enriched Queries
Venue: arXiv cs.LG 2021
Year: 2021

The explosive growth of easily-accessible unlabeled data has lead to growing interest in active learning, a paradigm in which data-hungry learning algorithms adaptively select informative examples in order to lower prohibitively expensive labeling costs. Unfortunately, in standard worst-case models of learning, the active setting often provides no improvement over non-adaptive algorithms. To combat this, a series of recent works have considered a model in which the learner may ask enriched queries beyond labels. While such models have seen success in drastically lowering label costs, they tend to come at the expense of requiring large amounts of memory. In this work, we study what families of classifiers can be learned in bounded memory. To this end, we introduce a novel streaming-variant of enriched-query active learning along with a natural combinatorial parameter called lossless sample compression that is sufficient for learning not only with bounded memory, but in a query-optimal and computationally efficient manner as well. Finally, we give three fundamental examples of classifier families with small, easy to compute lossless compression schemes when given access to basic enriched queries: axis-aligned rectangles, decision trees, and halfspaces in two dimensions.
NOELLE Offers Empowering LLVM Extensions
Venue: arXiv cs.PL 2021
Year: 2021

Modern and emerging architectures demand increasingly complex compiler analyses and transformations. As the emphasis on compiler infrastructure moves beyond support for peephole optimizations and the extraction of instruction-level parallelism, they should support custom tools designed to meet these demands with higher-level analysis-powered abstractions of wider program scope. This paper introduces NOELLE, a robust open-source domain-independent compilation layer built upon LLVM providing this support. NOELLE is modular and demand-driven, making it easy-to-extend and adaptable to custom-tool-specific needs without unduly wasting compile time and memory. This paper shows the power of NOELLE by presenting a diverse set of ten custom tools built upon it, with a 33.2% to 99.2% reduction in code size (LoC) compared to their counterparts without NOELLE.
Adversarial Perturbations Are Not So Weird: Entanglement of Robust and Non-Robust Features in Neural Network Classifiers
Venue: arXiv cs.LG 2021
Year: 2021

Neural networks trained on visual data are well-known to be vulnerable to often imperceptible adversarial perturbations. The reasons for this vulnerability are still being debated in the literature. Recently Ilyas et al. (2019) showed that this vulnerability arises, in part, because neural network classifiers rely on highly predictive but brittle "non-robust" features. In this paper we extend the work of Ilyas et al. by investigating the nature of the input patterns that give rise to these features. In particular, we hypothesize that in a neural network trained in a standard way, non-robust features respond to small, "non-semantic" patterns that are typically entangled with larger, robust patterns, known to be more human-interpretable, as opposed to solely responding to statistical artifacts in a dataset. Thus, adversarial examples can be formed via minimal perturbations to these small, entangled patterns. In addition, we demonstrate a corollary of our hypothesis: robust classifiers are more effective than standard (non-robust) ones as a source for generating transferable adversarial examples in both the untargeted and targeted settings. The results we present in this paper provide new insight into the nature of the non-robust features responsible for adversarial vulnerability of neural network classifiers.
Label Smoothed Embedding Hypothesis for Out-of-Distribution Detection
Venue: arXiv cs.LG 2021
Year: 2021

Detecting out-of-distribution (OOD) examples is critical in many applications. We propose an unsupervised method to detect OOD samples using a $k$-NN density estimate with respect to a classification model's intermediate activations on in-distribution samples. We leverage a recent insight about label smoothing, which we call the \emph{Label Smoothed Embedding Hypothesis}, and show that one of the implications is that the $k$-NN density estimator performs better as an OOD detection method both theoretically and empirically when the model is trained with label smoothing. Finally, we show that our proposal outperforms many OOD baselines and also provide new finite-sample high-probability statistical results for $k$-NN density estimation's ability to detect OOD examples.
Toward Safe and Efficient Human-Robot Interaction via Behavior-Driven Danger Signaling
Venue: arXiv cs.RO 2021
Year: 2021

This paper introduces the notion of danger awareness in the context of Human-Robot Interaction (HRI), which decodes whether a human is aware of the existence of the robot, and illuminates whether the human is willing to engage in enforcing the safety. This paper also proposes a method to quantify this notion as a single binary variable, so-called danger awareness coefficient. By analyzing the effect of this coefficient on the human's actions, an online Bayesian learning method is proposed to update the belief about the value of the coefficient. It is shown that based upon the danger awareness coefficient and the proposed learning method, the robot can build a predictive human model to anticipate the human's future actions. In order to create a communication channel between the human and the robot, to enrich the observations and get informative data about the human, and to improve the efficiency of the robot, the robot is equipped with a danger signaling system. A predictive planning scheme, coupled with the predictive human model, is also proposed to provide an efficient and Probabilistically safe plan for the robot. The effectiveness of the proposed scheme is demonstrated through simulation studies on an interaction between a self-driving car and a pedestrian.
Deterministic Tree Embeddings with Copies for Algorithms Against Adaptive Adversaries
Venue: arXiv cs.DS 2021
Year: 2021

Embeddings of graphs into distributions of trees that preserve distances in expectation are a cornerstone of many optimization algorithms. Unfortunately, online or dynamic algorithms which use these embeddings seem inherently randomized and ill-suited against adaptive adversaries. In this paper we provide a new tree embedding which addresses these issues by deterministically embedding a graph into a single tree containing $O(\log n)$ copies of each vertex while preserving the connectivity structure of every subgraph and $O(\log^2 n)$-approximating the cost of every subgraph. Using this embedding we obtain several new algorithmic results: We reduce an open question of Alon et al. [SODA 2004] -- the existence of a deterministic poly-log-competitive algorithm for online group Steiner tree on a general graph -- to its tree case. We give a poly-log-competitive deterministic algorithm for a closely related problem -- online partial group Steiner tree -- which, roughly, is a bicriteria version of online group Steiner tree. Lastly, we give the first poly-log approximations for demand-robust Steiner forest, group Steiner tree and group Steiner forest.
Transfer learning based few-shot classification using optimal transport mapping from preprocessed latent space of backbone neural network
Venue: arXiv cs.LG 2021
Year: 2021

MetaDL Challenge 2020 focused on image classification tasks in few-shot settings. This paper describes second best submission in the competition. Our meta learning approach modifies the distribution of classes in a latent space produced by a backbone network for each class in order to better follow the Gaussian distribution. After this operation which we call Latent Space Transform algorithm, centers of classes are further aligned in an iterative fashion of the Expectation Maximisation algorithm to utilize information in unlabeled data that are often provided on top of few labelled instances. For this task, we utilize optimal transport mapping using the Sinkhorn algorithm. Our experiments show that this approach outperforms previous works as well as other variants of the algorithm, using K-Nearest Neighbour algorithm, Gaussian Mixture Models, etc.
DHLink: A Microservice Platform supporting Rapid Application Development and Secure Real-time Data Sharing in Digital Health
Venue: arXiv cs.DC 2021
Year: 2021

Digital health applications that leverage multiple sources of patient data for insights to patients' behaviours or disease symptoms as well as remote patient monitoring, nudging and treatments are becoming increasingly popular in various medical practices and research. One common issue among these applications is that they are generally based on project-specific solutions and developed from scratch. Such application development fashion results in large amounts of repetitive effort, for example, in building study specific websites and mobile frontends, deploying customised infrastructures, and collecting data that may have already been collected in other studies and projects. What is worse, the data collected, and functions built cannot be easily reused by other applications. In this paper, we present an event-driven microservice platform, namely DHLink, to address this issue. DHLink securely links existing digital health applications of different projects, facilitates real-time data sharing, and supports rapid application development by reusing data and functions of existing digital health applications. In addition, comes with DHLink, a set of highly generic and reusable microservices is provided, which allows developers to rapidly create a typical above-mentioned digital health application by only developing the core algorithms. Two use cases outlined in this paper have shown the use of DHLink and the set of microservices for application collaboration and new application development to be efficient and practical.