OpenRaiser/Intern-Atlas huggingface dataset:
Learning a Shield from Catastrophic Action Effects: Never Repeat the Same Mistake
Venue: arXiv cs.LG 2022
Year: 2022

Agents that operate in an unknown environment are bound to make mistakes while learning, including, at least occasionally, some that lead to catastrophic consequences. When humans make catastrophic mistakes, they are expected to learn never to repeat them, such as a toddler who touches a hot stove and immediately learns never to do so again. In this work we consider a novel class of POMDPs, called POMDP with Catastrophic Actions (POMDP-CA) in which pairs of states and actions are labeled as catastrophic. Agents that act in a POMDP-CA do not have a priori knowledge about which (state, action) pairs are catastrophic, thus they are sure to make mistakes when trying to learn any meaningful policy. Rather, their aim is to maximize reward while never repeating mistakes. As a first step of avoiding mistake repetition, we leverage the concept of a shield which prevents agents from executing specific actions from specific states. In particular, we store catastrophic mistakes (unsafe pairs of states and actions) that agents make in a database. Agents are then forbidden to pick actions that appear in the database. This approach is especially useful in a continual learning setting, where groups of agents perform a variety of tasks over time in the same underlying environment. In this setting, a task-agnostic shield can be constructed in a way that stores mistakes made by any agent, such that once one agent in a group makes a mistake the entire group learns to never repeat that mistake. This paper introduces a variant of the PPO algorithm that utilizes this shield, called ShieldPPO, and empirically evaluates it in a controlled environment. Results indicate that ShieldPPO outperforms PPO, as well as baseline methods from the safe reinforcement learning literature, in a range of settings.
Student Dangerous Behavior Detection in School
Venue: arXiv cs.CV 2022
Year: 2022

Video surveillance systems have been installed to ensure the student safety in schools. However, discovering dangerous behaviors, such as fighting and falling down, usually depends on untimely human observations. In this paper, we focus on detecting dangerous behaviors of students automatically, which faces numerous challenges, such as insufficient datasets, confusing postures, keyframes detection and prompt response. To address these challenges, we first build a danger behavior dataset with locations and labels from surveillance videos, and transform action recognition of long videos to an object detection task that avoids keyframes detection. Then, we propose a novel end-to-end dangerous behavior detection method, named DangerDet, that combines multi-scale body features and keypoints-based pose features. We could improve the accuracy of behavior classification due to the highly correlation between pose and behavior. On our dataset, DangerDet achieves 71.0\% mAP with about 11 FPS. It keeps a better balance between the accuracy and time cost.
Safe Control Synthesis with Uncertain Dynamics and Constraints
Venue: arXiv cs.RO 2022
Year: 2022

This paper considers safe control synthesis for dynamical systems with either probabilistic or worst-case uncertainty in both the dynamics model and the safety constraints. We formulate novel probabilistic and robust (worst-case) control Lyapunov function (CLF) and control barrier function (CBF) constraints that take into account the effect of uncertainty in either case. We show that either the probabilistic or the robust (worst-case) formulation leads to a second-order cone program (SOCP), which enables efficient safe and stable control synthesis. We evaluate our approach in PyBullet simulations of an autonomous robot navigating in unknown environments and compare the performance with a baseline CLF-CBF quadratic programming approach.
Illuminating the Space of Enemies Through MAP-Elites
Venue: arXiv cs.AI 2022
Year: 2022

Action-Adventure games have several challenges to overcome, where the most common are enemies. The enemies' goal is to hinder the players' progression by taking life points, and the way they hinder this progress is distinct for different kinds of enemies. In this context, this paper introduces an extended version of an evolutionary approach for procedurally generating enemies that target the enemy's difficulty as the goal. Our approach advances the enemy generation research by incorporating a MAP-Elites population to generate diverse enemies without losing quality. The computational experiment showed the method converged most enemies in the MAP-Elites in less than a second for most cases. Besides, we experimented with players who played an Action-Adventure game prototype with enemies we generated. This experiment showed that the players enjoyed most levels they played, and we successfully created enemies perceived as easy, medium, or hard to face.
Decision Problems in a Logic for Reasoning about Reconfigurable Distributed Systems
Venue: arXiv cs.LO 2022
Year: 2022

We consider a logic used to describe sets of configurations of distributed systems, whose network topologies can be changed at runtime, by reconfiguration programs. The logic uses inductive definitions to describe networks with an unbounded number of components and interactions, written using a multiplicative conjunction, reminiscent of Bunched Implications and Separation Logic. We study the complexity of the satisfiability and entailment problems for the configuration logic under consideration. Additionally, we consider robustness properties, such as tightness (are all interactions entirely connected to components?) and degree boundedness (is every component involved in a bounded number of interactions?), the latter being an ingredient for decidability of entailments.
Navigating Conceptual Space; A new take on Artificial General Intelligence
Venue: arXiv cs.AI 2022
Year: 2022

Edward C. Tolman found reinforcement learning unsatisfactory for explaining intelligence and proposed a clear distinction between learning and behavior. Tolman's ideas on latent learning and cognitive maps eventually led to what is now known as conceptual space, a geometric representation where concepts and ideas can form points or shapes.Active navigation between ideas - reasoning - can be expressed directly as purposive navigation in conceptual space. Assimilating the theory of conceptual space from modern neuroscience, we propose autonomous navigation as a valid approach for emulated cognition. However, achieving autonomous navigation in high-dimensional Euclidean spaces is not trivial in technology. In this work, we explore whether neoRL navigation is up for the task; adopting Kaelbling's concerns for efficient robot navigation, we test whether the neoRL approach is general across navigational modalities, compositional across considerations of experience, and effective when learning in multiple Euclidean dimensions. We find neoRL learning to be more resemblant of biological learning than of RL in AI, and propose neoRL navigation of conceptual space as a plausible new path toward emulated cognition.
Accurate Prediction and Uncertainty Estimation using Decoupled Prediction Interval Networks
Venue: arXiv cs.LG 2022
Year: 2022

We propose a network architecture capable of reliably estimating uncertainty of regression based predictions without sacrificing accuracy. The current state-of-the-art uncertainty algorithms either fall short of achieving prediction accuracy comparable to the mean square error optimization or underestimate the variance of network predictions. We propose a decoupled network architecture that is capable of accomplishing both at the same time. We achieve this by breaking down the learning of prediction and prediction interval (PI) estimations into a two-stage training process. We use a custom loss function for learning a PI range around optimized mean estimation with a desired coverage of a proportion of the target labels within the PI range. We compare the proposed method with current state-of-the-art uncertainty quantification algorithms on synthetic datasets and UCI benchmarks, reducing the error in the predictions by 23 to 34% while maintaining 95% Prediction Interval Coverage Probability (PICP) for 7 out of 9 UCI benchmark datasets. We also examine the quality of our predictive uncertainty by evaluating on Active Learning and demonstrating 17 to 36% error reduction on UCI benchmarks.
Simple Genetic Operators are Universal Approximators of Probability Distributions (and other Advantages of Expressive Encodings)
Venue: arXiv cs.NE 2022
Year: 2022

This paper characterizes the inherent power of evolutionary algorithms. This power depends on the computational properties of the genetic encoding. With some encodings, two parents recombined with a simple crossover operator can sample from an arbitrary distribution of child phenotypes. Such encodings are termed \emph{expressive encodings} in this paper. Universal function approximators, including popular evolutionary substrates of genetic programming and neural networks, can be used to construct expressive encodings. Remarkably, this approach need not be applied only to domains where the phenotype is a function: Expressivity can be achieved even when optimizing static structures, such as binary vectors. Such simpler settings make it possible to characterize expressive encodings theoretically: Across a variety of test problems, expressive encodings are shown to achieve up to super-exponential convergence speed-ups over the standard direct encoding. The conclusion is that, across evolutionary computation areas as diverse as genetic programming, neuroevolution, genetic algorithms, and theory, expressive encodings can be a key to understanding and realizing the full power of evolution.
On Matrix Method of Symmetric Games
Venue: arXiv cs.GT 2022
Year: 2022

This paper provides a new version of matrix semi-tensor product method based on adjacent transpositions to test symmetric games. The advantage of using adjacent transpositions lies in the great simplification of analysis of symmetric games. By using the new method, new necessary and sufficient conditions for symmetric games are proposed, and a group of bases of a symmetric game space can be easily calculated. Moreover, the testing equations with the minimum number can be concretely determined. Finally, two examples are displayed to show the effectiveness of the proposed method.
MANet: Improving Video Denoising with a Multi-Alignment Network
Venue: arXiv cs.CV 2022
Year: 2022

In video denoising, the adjacent frames often provide very useful information, but accurate alignment is needed before such information can be harnassed. In this work, we present a multi-alignment network, which generates multiple flow proposals followed by attention-based averaging. It serves to mimic the non-local mechanism, suppressing noise by averaging multiple observations. Our approach can be applied to various state-of-the-art models that are based on flow estimation. Experiments on a large-scale video dataset demonstrate that our method improves the denoising baseline model by 0.2dB, and further reduces the parameters by 47% with model distillation. Code is available at https://github.com/IndigoPurple/MANet.
3DRM:Pair-wise relation module for 3D object detection
Venue: arXiv cs.CV 2022
Year: 2022

Context has proven to be one of the most important factors in object layout reasoning for 3D scene understanding. Existing deep contextual models either learn holistic features for context encoding or rely on pre-defined scene templates for context modeling. We argue that scene understanding benefits from object relation reasoning, which is capable of mitigating the ambiguity of 3D object detections and thus helps locate and classify the 3D objects more accurately and robustly. To achieve this, we propose a novel 3D relation module (3DRM) which reasons about object relations at pair-wise levels. The 3DRM predicts the semantic and spatial relationships between objects and extracts the object-wise relation features. We demonstrate the effects of 3DRM by plugging it into proposal-based and voting-based 3D object detection pipelines, respectively. Extensive evaluations show the effectiveness and generalization of 3DRM on 3D object detection. Our source code is available at https://github.com/lanlan96/3DRM.
PooL: Pheromone-inspired Communication Framework forLarge Scale Multi-Agent Reinforcement Learning
Venue: arXiv cs.AI 2022
Year: 2022

Being difficult to scale poses great problems in multi-agent coordination. Multi-agent Reinforcement Learning (MARL) algorithms applied in small-scale multi-agent systems are hard to extend to large-scale ones because the latter is far more dynamic and the number of interactions increases exponentially with the growing number of agents. Some swarm intelligence algorithms simulate the release and utilization mechanism of pheromones to control large-scale agent coordination. Inspired by such algorithms, \textbf{PooL}, an \textbf{p}her\textbf{o}m\textbf{o}ne-based indirect communication framework applied to large scale multi-agent reinforcement \textbf{l}earning is proposed in order to solve the large-scale multi-agent coordination problem. Pheromones released by agents of PooL are defined as outputs of most reinforcement learning algorithms, which reflect agents' views of the current environment. The pheromone update mechanism can efficiently organize the information of all agents and simplify the complex interactions among agents into low-dimensional representations. Pheromones perceived by agents can be regarded as a summary of the views of nearby agents which can better reflect the real situation of the environment. Q-Learning is taken as our base model to implement PooL and PooL is evaluated in various large-scale cooperative environments. Experiments show agents can capture effective information through PooL and achieve higher rewards than other state-of-arts methods with lower communication costs.
Overparametrization improves robustness against adversarial attacks: A replication study
Venue: arXiv cs.LG 2022
Year: 2022

Overparametrization has become a de facto standard in machine learning. Despite numerous efforts, our understanding of how and where overparametrization helps model accuracy and robustness is still limited. To this end, here we conduct an empirical investigation to systemically study and replicate previous findings in this area, in particular the study by Madry et al. Together with this study, our findings support the "universal law of robustness" recently proposed by Bubeck et al. We argue that while critical for robust perception, overparametrization may not be enough to achieve full robustness and smarter architectures e.g. the ones implemented by the human visual cortex) seem inevitable.
Visual Attention Network
Venue: arXiv cs.CV 2022
Year: 2022

While originally designed for natural language processing tasks, the self-attention mechanism has recently taken various computer vision areas by storm. However, the 2D nature of images brings three challenges for applying self-attention in computer vision. (1) Treating images as 1D sequences neglects their 2D structures. (2) The quadratic complexity is too expensive for high-resolution images. (3) It only captures spatial adaptability but ignores channel adaptability. In this paper, we propose a novel linear attention named large kernel attention (LKA) to enable self-adaptive and long-range correlations in self-attention while avoiding its shortcomings. Furthermore, we present a neural network based on LKA, namely Visual Attention Network (VAN). While extremely simple, VAN surpasses similar size vision transformers(ViTs) and convolutional neural networks(CNNs) in various tasks, including image classification, object detection, semantic segmentation, panoptic segmentation, pose estimation, etc. For example, VAN-B6 achieves 87.8% accuracy on ImageNet benchmark and set new state-of-the-art performance (58.2 PQ) for panoptic segmentation. Besides, VAN-B2 surpasses Swin-T 4% mIoU (50.1 vs. 46.1) for semantic segmentation on ADE20K benchmark, 2.6% AP (48.8 vs. 46.2) for object detection on COCO dataset. It provides a novel method and a simple yet strong baseline for the community. Code is available at https://github.com/Visual-Attention-Network.
Multi-dimensional Network Security Game: How do attacker and defender battle on parallel targets?
Venue: arXiv cs.GT 2022
Year: 2022

In this paper, we consider a new network security game wherein an attacker and a defender are battling over "multiple" targets. This type of game is appropriate to model many current network security conflicts such as Internet phishing, mobile malware or network intrusions. In such attacks, the attacker and the defender need to decide how to allocate resources on each target so as to maximize his utility within his resource limit. We model such a multi-dimensional network security game as a constrained non-zero sum game. Two security breaching models, the product-form and the proportion-form, are considered. For each breaching model, we prove the existence of a unique Nash equilibrium (NE) based on Rosen's theorem and propose efficient algorithms to find the NE when the games are strictly concave. Furthermore, we show the existence of multiple NEs in the product-form breaching model when the strict concavity does not hold. Our study sheds light on the strategic behaviors of the attacker and the defender, in particular, on how they allocate resources to the targets which have different weights, and how their utilities as well as strategies are influenced by the resource constraints.
Context-aware adaptation of mobile video decoding resolution
Venue: arXiv cs.MM 2022
Year: 2022

While the evolution of mobile computing is experiencing a considerable growth, it is at the same time seriously threatened by the limitations of the battery technology, which does not keep pace with the evergrowing increase in energy requirements of mobile applications. A novel approach for reducing the energy appetite of mobile apps comes from the approximate computing field, which proposes techniques that in a controlled manner sacrifice computation accuracy for higher energy savings. Building on this philosophy we propose a context-aware mobile video quality adaptation that reduces the energy needed for video playback, while ensuring that a user's quality expectations with respect to the mobile video are met. We confirm that the decoding resolution can play a significant role in reducing the overall power consumption of a mobile device and conduct two user studies to investigate how the context in which a video is played, its content, and the user's personality, modulate a user's quality expectations. We discover that a user's physical activity, the spatial/temporal properties of the video, and the user's personality traits interact and jointly influence the minimal acceptable playback resolution, paving the way for context-adaptable approximate mobile computing.
Clustering by the Probability Distributions from Extreme Value Theory
Venue: arXiv cs.LG 2022
Year: 2022

Clustering is an essential task to unsupervised learning. It tries to automatically separate instances into coherent subsets. As one of the most well-known clustering algorithms, k-means assigns sample points at the boundary to a unique cluster, while it does not utilize the information of sample distribution or density. Comparably, it would potentially be more beneficial to consider the probability of each sample in a possible cluster. To this end, this paper generalizes k-means to model the distribution of clusters. Our novel clustering algorithm thus models the distributions of distances to centroids over a threshold by Generalized Pareto Distribution (GPD) in Extreme Value Theory (EVT). Notably, we propose the concept of centroid margin distance, use GPD to establish a probability model for each cluster, and perform a clustering algorithm based on the covering probability function derived from GPD. Such a GPD k-means thus enables the clustering algorithm from the probabilistic perspective. Correspondingly, we also introduce a naive baseline, dubbed as Generalized Extreme Value (GEV) k-means. GEV fits the distribution of the block maxima. In contrast, the GPD fits the distribution of distance to the centroid exceeding a sufficiently large threshold, leading to a more stable performance of GPD k-means. Notably, GEV k-means can also estimate cluster structure and thus perform reasonably well over classical k-means. Thus, extensive experiments on synthetic datasets and real datasets demonstrate that GPD k-means outperforms competitors. The github codes are released in https://github.com/sixiaozheng/EVT-K-means.
Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings
Venue: arXiv cs.DS 2022
Year: 2022

We consider the following oblivious sketching problem: given $ε\in (0,1/3)$ and $n \geq d/ε^2$, design a distribution $\mathcal{D}$ over $\mathbb{R}^{k \times nd}$ and a function $f: \mathbb{R}^k \times \mathbb{R}^{nd} \rightarrow \mathbb{R}$, so that for any $n \times d$ matrix $A$, $$\Pr_{S \sim \mathcal{D}} [(1-ε) \|A\|_{op} \leq f(S(A),S) \leq (1+ε)\|A\|_{op}] \geq 2/3,$$ where $\|A\|_{op}$ is the operator norm of $A$ and $S(A)$ denotes $S \cdot A$, interpreting $A$ as a vector in $\mathbb{R}^{nd}$. We show a tight lower bound of $k = Ω(d^2/ε^2)$ for this problem. Our result considerably strengthens the result of Nelson and Nguyen (ICALP, 2014), as it (1) applies only to estimating the operator norm, which can be estimated given any OSE, and (2) applies to distributions over general linear operators $S$ which treat $A$ as a vector and compute $S(A)$, rather than the restricted class of linear operators corresponding to matrix multiplication. Our technique also implies the first tight bounds for approximating the Schatten $p$-norm for even integers $p$ via general linear sketches, improving the previous lower bound from $k = Ω(n^{2-6/p})$ [Regev, 2014] to $k = Ω(n^{2-4/p})$. Importantly, for sketching the operator norm up to a factor of $α$, where $α- 1 = Ω(1)$, we obtain a tight $k = Ω(n^2/α^4)$ bound, matching the upper bound of Andoni and Nguyen (SODA, 2013), and improving the previous $k = Ω(n^2/α^6)$ lower bound. Finally, we also obtain the first lower bounds for approximating Ky Fan norms.
UX Research on Conversational Human-AI Interaction: A Literature Review of the ACM Digital Library
Venue: arXiv cs.HC 2022
Year: 2022

Early conversational agents (CAs) focused on dyadic human-AI interaction between humans and the CAs, followed by the increasing popularity of polyadic human-AI interaction, in which CAs are designed to mediate human-human interactions. CAs for polyadic interactions are unique because they encompass hybrid social interactions, i.e., human-CA, human-to-human, and human-to-group behaviors. However, research on polyadic CAs is scattered across different fields, making it challenging to identify, compare, and accumulate existing knowledge. To promote the future design of CA systems, we conducted a literature review of ACM publications and identified a set of works that conducted UX (user experience) research. We qualitatively synthesized the effects of polyadic CAs into four aspects of human-human interactions, i.e., communication, engagement, connection, and relationship maintenance. Through a mixed-method analysis of the selected polyadic and dyadic CA studies, we developed a suite of evaluation measurements on the effects. Our findings show that designing with social boundaries, such as privacy, disclosure, and identification, is crucial for ethical polyadic CAs. Future research should also advance usability testing methods and trust-building guidelines for conversational AI.