OpenRaiser/Intern-Atlas huggingface dataset:
SAT Backdoors: Depth Beats Size
Venue: arXiv cs.DS 2022
Year: 2022

For several decades, much effort has been put into identifying classes of CNF formulas whose satisfiability can be decided in polynomial time. Classic results are the linear-time tractability of Horn formulas (Aspvall, Plass, and Tarjan, 1979) and Krom (i.e., 2CNF) formulas (Dowling and Gallier, 1984). Backdoors, introduced by Williams Gomes and Selman (2003), gradually extend such a tractable class to all formulas of bounded distance to the class. Backdoor size provides a natural but rather crude distance measure between a formula and a tractable class. Backdoor depth, introduced by Mählmann, Siebertz, and Vigny (2021), is a more refined distance measure, which admits the utilization of different backdoor variables in parallel. Bounded backdoor size implies bounded backdoor depth, but there are formulas of constant backdoor depth and arbitrarily large backdoor size. We propose FPT approximation algorithms to compute backdoor depth into the classes Horn and Krom. This leads to a linear-time algorithm for deciding the satisfiability of formulas of bounded backdoor depth into these classes. We base our FPT approximation algorithm on a sophisticated notion of obstructions, extending Mählmann et al.'s obstruction trees in various ways, including the addition of separator obstructions. We develop the algorithm through a new game-theoretic framework that simplifies the reasoning about backdoors. Finally, we show that bounded backdoor depth captures tractable classes of CNF formulas not captured by any known method.
A Developmentally-Inspired Examination of Shape versus Texture Bias in Machines
Venue: arXiv cs.CV 2022
Year: 2022

Early in development, children learn to extend novel category labels to objects with the same shape, a phenomenon known as the shape bias. Inspired by these findings, Geirhos et al. (2019) examined whether deep neural networks show a shape or texture bias by constructing images with conflicting shape and texture cues. They found that convolutional neural networks strongly preferred to classify familiar objects based on texture as opposed to shape, suggesting a texture bias. However, there are a number of differences between how the networks were tested in this study versus how children are typically tested. In this work, we re-examine the inductive biases of neural networks by adapting the stimuli and procedure from Geirhos et al. (2019) to more closely follow the developmental paradigm and test on a wide range of pre-trained neural networks. Across three experiments, we find that deep neural networks exhibit a preference for shape rather than texture when tested under conditions that more closely replicate the developmental procedure.
Limitations of Neural Collapse for Understanding Generalization in Deep Learning
Venue: arXiv cs.LG 2022
Year: 2022

The recent work of Papyan, Han, & Donoho (2020) presented an intriguing "Neural Collapse" phenomenon, showing a structural property of interpolating classifiers in the late stage of training. This opened a rich area of exploration studying this phenomenon. Our motivation is to study the upper limits of this research program: How far will understanding Neural Collapse take us in understanding deep learning? First, we investigate its role in generalization. We refine the Neural Collapse conjecture into two separate conjectures: collapse on the train set (an optimization property) and collapse on the test distribution (a generalization property). We find that while Neural Collapse often occurs on the train set, it does not occur on the test set. We thus conclude that Neural Collapse is primarily an optimization phenomenon, with as-yet-unclear connections to generalization. Second, we investigate the role of Neural Collapse in feature learning. We show simple, realistic experiments where training longer leads to worse last-layer features, as measured by transfer-performance on a downstream task. This suggests that neural collapse is not always desirable for representation learning, as previously claimed. Finally, we give preliminary evidence of a "cascading collapse" phenomenon, wherein some form of Neural Collapse occurs not only for the last layer, but in earlier layers as well. We hope our work encourages the community to continue the rich line of Neural Collapse research, while also considering its inherent limitations.
Shift-Memory Network for Temporal Scene Segmentation
Venue: arXiv cs.CV 2022
Year: 2022

Semantic segmentation has achieved great accuracy in understanding spatial layout. For real-time tasks based on dynamic scenes, we extend semantic segmentation in temporal domain to enhance the spatial accuracy with motion. We utilize a shift-mode network over streaming input to ensure zero-latency output. For the data overlap under shifting network, this paper identifies repeated computation in fixed periods across network layers. To avoid this redundancy, we derive a Shift-Memory Network (SMN) from encoding-decoding baseline to reuse the network values without accuracy loss. Trained in patch-mode, the SMN extracts the network parameters for SMN to perform inference promptly in compact memory. We segment dynamic scenes from 1D scanning input and 2D video. The experiments of SMN achieve equivalent accuracy as shift-mode but in faster inference speeds and much smaller memory. This will facilitate semantic segmentation in real-time application on edge devices.
Emotion Recognition among Couples: A Survey
Venue: arXiv cs.HC 2022
Year: 2022

Couples' relationships affect the physical health and emotional well-being of partners. Automatically recognizing each partner's emotions could give a better understanding of their individual emotional well-being, enable interventions and provide clinical benefits. In the paper, we summarize and synthesize works that have focused on developing and evaluating systems to automatically recognize the emotions of each partner based on couples' interaction or conversation contexts. We identified 28 articles from IEEE, ACM, Web of Science, and Google Scholar that were published between 2010 and 2021. We detail the datasets, features, algorithms, evaluation, and results of each work as well as present main themes. We also discuss current challenges, research gaps and propose future research directions. In summary, most works have used audio data collected from the lab with annotations done by external experts and used supervised machine learning approaches for binary classification of positive and negative affect. Performance results leave room for improvement with significant research gaps such as no recognition using data from daily life. This survey will enable new researchers to get an overview of this field and eventually enable the development of emotion recognition systems to inform interventions to improve the emotional well-being of couples.
A Survey on Deep Reinforcement Learning-based Approaches for Adaptation and Generalization
Venue: arXiv cs.LG 2022
Year: 2022

Deep Reinforcement Learning (DRL) aims to create intelligent agents that can learn to solve complex problems efficiently in a real-world environment. Typically, two learning goals: adaptation and generalization are used for baselining DRL algorithm's performance on different tasks and domains. This paper presents a survey on the recent developments in DRL-based approaches for adaptation and generalization. We begin by formulating these goals in the context of task and domain. Then we review the recent works under those approaches and discuss future research directions through which DRL algorithms' adaptability and generalizability can be enhanced and potentially make them applicable to a broad range of real-world problems.
V2X-Sim: Multi-Agent Collaborative Perception Dataset and Benchmark for Autonomous Driving
Venue: arXiv cs.CV 2022
Year: 2022

Vehicle-to-everything (V2X) communication techniques enable the collaboration between vehicles and many other entities in the neighboring environment, which could fundamentally improve the perception system for autonomous driving. However, the lack of a public dataset significantly restricts the research progress of collaborative perception. To fill this gap, we present V2X-Sim, a comprehensive simulated multi-agent perception dataset for V2X-aided autonomous driving. V2X-Sim provides: (1) \hl{multi-agent} sensor recordings from the road-side unit (RSU) and multiple vehicles that enable collaborative perception, (2) multi-modality sensor streams that facilitate multi-modality perception, and (3) diverse ground truths that support various perception tasks. Meanwhile, we build an open-source testbed and provide a benchmark for the state-of-the-art collaborative perception algorithms on three tasks, including detection, tracking and segmentation. V2X-Sim seeks to stimulate collaborative perception research for autonomous driving before realistic datasets become widely available. Our dataset and code are available at \url{https://ai4ce.github.io/V2X-Sim/}.
Online Scheduling of Time-Critical Tasks to Minimize the Number of Calibrations
Venue: arXiv cs.DS 2022
Year: 2022

We study the online scheduling problem where the machines need to be calibrated before processing any jobs. To calibrate a machine, it will take $λ$ time steps as the activation time, and then the machine will remain calibrated status for $T$ time steps. The job can only be processed by the machine that is in calibrated status. Given a set of jobs arriving online, each of the jobs is characterized by a release time, a processing time, and a deadline. We assume that there is an infinite number of machines for usage. The objective is to minimize the total number of calibrations while feasibly scheduling all jobs. For the case that all jobs have unit processing times, we propose an $\mathcal{O}(λ)$-competitive algorithm, which is asymptotically optimal. When $λ=0$, the problem is degraded to rent minimization, where our algorithm achieves a competitive ratio of $3e+7(\approx 15.16)$ which improves upon the previous results for such problems.
Predict the Rover Mobility over Soft Terrain using Articulated Wheeled Bevameter
Venue: arXiv cs.RO 2022
Year: 2022

Robot mobility is critical for mission success, especially in soft or deformable terrains, where the complex wheel-soil interaction mechanics often leads to excessive wheel slip and sinkage, causing the eventual mission failure. To improve the success rate, online mobility prediction using vision, infrared imaging, or model-based stochastic methods have been used in the literature. This paper proposes an on-board mobility prediction approach using an articulated wheeled bevameter that consists of a force-controlled arm and an instrumented bevameter (with force and vision sensors) as its end-effector. The proposed bevameter, which emulates the traditional terramechanics tests such as pressure-sinkage and shear experiments, can measure contact parameters ahead of the rover's body in real-time, and predict the slip and sinkage of supporting wheels over the probed region. Based on the predicted mobility, the rover can select a safer path in order to avoid dangerous regions such as those covered with quicksand. Compared to the literature, our proposed method can avoid the complicated terramechanics modeling and time-consuming stochastic prediction; it can also mitigate the inaccuracy issues arising in non-contact vision-based methods. We also conduct multiple experiments to validate the proposed approach.
CSCNet: Contextual Semantic Consistency Network for Trajectory Prediction in Crowded Spaces
Venue: arXiv cs.CV 2022
Year: 2022

Trajectory prediction aims to predict the movement trend of the agents like pedestrians, bikers, vehicles. It is helpful to analyze and understand human activities in crowded spaces and widely applied in many areas such as surveillance video analysis and autonomous driving systems. Thanks to the success of deep learning, trajectory prediction has made significant progress. The current methods are dedicated to studying the agents' future trajectories under the social interaction and the sceneries' physical constraints. Moreover, how to deal with these factors still catches researchers' attention. However, they ignore the \textbf{Semantic Shift Phenomenon} when modeling these interactions in various prediction sceneries. There exist several kinds of semantic deviations inner or between social and physical interactions, which we call the "\textbf{Gap}". In this paper, we propose a \textbf{C}ontextual \textbf{S}emantic \textbf{C}onsistency \textbf{Net}work (\textbf{CSCNet}) to predict agents' future activities with powerful and efficient context constraints. We utilize a well-designed context-aware transfer to obtain the intermediate representations from the scene images and trajectories. Then we eliminate the differences between social and physical interactions by aligning activity semantics and scene semantics to cross the Gap. Experiments demonstrate that CSCNet performs better than most of the current methods quantitatively and qualitatively.
TAFNet: A Three-Stream Adaptive Fusion Network for RGB-T Crowd Counting
Venue: arXiv cs.CV 2022
Year: 2022

In this paper, we propose a three-stream adaptive fusion network named TAFNet, which uses paired RGB and thermal images for crowd counting. Specifically, TAFNet is divided into one main stream and two auxiliary streams. We combine a pair of RGB and thermal images to constitute the input of main stream. Two auxiliary streams respectively exploit RGB image and thermal image to extract modality-specific features. Besides, we propose an Information Improvement Module (IIM) to fuse the modality-specific features into the main stream adaptively. Experiment results on RGBT-CC dataset show that our method achieves more than 20% improvement on mean average error and root mean squared error compared with state-of-the-art method. The source code will be publicly available at https://github.com/TANGHAIHAN/TAFNet.
Point Cloud Generation with Continuous Conditioning
Venue: arXiv cs.CV 2022
Year: 2022

Generative models can be used to synthesize 3D objects of high quality and diversity. However, there is typically no control over the properties of the generated object.This paper proposes a novel generative adversarial network (GAN) setup that generates 3D point cloud shapes conditioned on a continuous parameter. In an exemplary application, we use this to guide the generative process to create a 3D object with a custom-fit shape. We formulate this generation process in a multi-task setting by using the concept of auxiliary classifier GANs. Further, we propose to sample the generator label input for training from a kernel density estimation (KDE) of the dataset. Our ablations show that this leads to significant performance increase in regions with few samples. Extensive quantitative and qualitative experiments show that we gain explicit control over the object dimensions while maintaining good generation quality and diversity.
Information Theory with Kernel Methods
Venue: arXiv cs.IT 2022
Year: 2022

We consider the analysis of probability distributions through their associated covariance operators from reproducing kernel Hilbert spaces. We show that the von Neumann entropy and relative entropy of these operators are intimately related to the usual notions of Shannon entropy and relative entropy, and share many of their properties. They come together with efficient estimation algorithms from various oracles on the probability distributions. We also consider product spaces and show that for tensor product kernels, we can define notions of mutual information and joint entropies, which can then characterize independence perfectly, but only partially conditional independence. We finally show how these new notions of relative entropy lead to new upper-bounds on log partition functions, that can be used together with convex optimization within variational inference methods, providing a new family of probabilistic inference methods.
Domain Randomization for Object Counting
Venue: arXiv cs.CV 2022
Year: 2022

Recently, the use of synthetic datasets based on game engines has been shown to improve the performance of several tasks in computer vision. However, these datasets are typically only appropriate for the specific domains depicted in computer games, such as urban scenes involving vehicles and people. In this paper, we present an approach to generate synthetic datasets for object counting for any domain without the need for photo-realistic techniques manually generated by expensive teams of 3D artists. We introduce a domain randomization approach for object counting based on synthetic datasets that are quick and inexpensive to generate. We deliberately avoid photorealism and drastically increase the variability of the dataset, producing images with random textures and 3D transformations, which improves generalization. Experiments show that our method facilitates good performance on various real word object counting datasets for multiple domains: people, vehicles, penguins, and fruit. The source code is available at: https://github.com/enric1994/dr4oc
Measuring Trustworthiness or Automating Physiognomy? A Comment on Safra, Chevallier, Grèzes, and Baumard (2020)
Venue: arXiv cs.LG 2022
Year: 2022

Interpersonal trust - a shared display of confidence and vulnerability toward other individuals - can be seen as instrumental in the development of human societies. Safra, Chevallier, Grèzes, and Baumard (2020) studied the historical progression of interpersonal trust by training a machine learning (ML) algorithm to generate trustworthiness ratings of historical portraits, based on facial features. They reported that trustworthiness ratings of portraits dated between 1500--2000CE increased with time, claiming that this evidenced a broader increase in interpersonal trust coinciding with several metrics of societal progress. We argue that these claims are confounded by several methodological and analytical issues and highlight troubling parallels between Safra et al.'s algorithm and the pseudoscience of physiognomy. We discuss the implications and potential real-world consequences of these issues in further detail.
Conscious Commerce -- Digital Nudging and Sustainable E-commerce Purchase Decisions
Venue: arXiv cs.SI 2022
Year: 2022

So-called 'fast fashion' consumption, amplified through cost-effective e-commerce, constitutes a major factor negatively impacting climate change. A recently noted strategy to motivate consumers to more sustainable decisions is digital nudging. This paper explores the capability of digital nudging in the context of green fashion e-commerce. To do so, digital default and social norm nudges are tested in an experimental setting of green fashion purchases. An online experiment (n=320) was conducted, simulating an online retail scenario. Results failed to show statistically significant relationships between nudging strategies and purchase decisions. However, explorative analyses show a backfiring effect for the combination of nudges and thus, reveal a hitherto neglected impact of participants' identification on the effectiveness of the digital nudging strategies. Consequently, this study contributes to digital nudging literature and informs practice with new insights on effective choice architectures in e-commerce.
A Bi-Criteria FPTAS for Scheduling with Memory Constraints on Graph with Bounded Tree-width
Venue: arXiv cs.DS 2022
Year: 2022

In this paper we study a scheduling problem arising from executing numerical simulations on HPC architectures. With a constant number of parallel machines, the objective is to minimize the makespan under memory constraints for the machines. Those constraints come from a neighborhood graph G for the jobs. Motivated by a previous result on graphs G with bounded path-width, our focus is on the case when the neighborhood graph G has bounded tree-width. Our result is a bi-criteria fully polynomial time approximation algorithm based on a dynamic programming algorithm. It allows to find a solution within a factor of 1 + epsilon of the optimal makespan, where the memory capacity of the machines may be exceeded by a factor at most 1 + epsilon. This result relies on the use of a nice tree decomposition of G and its traversal in a specific way which may be useful on its own. The case of unrelated machines is also tractable with minor modifications.
Algorithmic Fair Allocation of Indivisible Items: A Survey and New Questions
Venue: arXiv cs.GT 2022
Year: 2022

The theory of algorithmic fair allocation is within the center of multi-agent systems and economics in the last decade due to its industrial and social importance. At a high level, the problem is to assign a set of items that are either goods or chores to a set of agents so that every agent is happy with what she obtains. Particularly, in this survey, we focus on indivisible items, for which absolute fairness such as envy-freeness and proportionality cannot be guaranteed. One main theme in the recent research agenda is about designing algorithms that approximately achieve the fairness criteria. We aim at presenting a comprehensive survey of recent progresses through the prism of algorithms, highlighting the ways to relax fairness notions and common techniques to design algorithms, as well as the most interesting questions for future research.
A Completeness Result for Inequational Reasoning in a Full Higher-Order Setting
Venue: arXiv cs.LO 2022
Year: 2022

This paper obtains a completeness result for inequational reasoning with applicative terms without variables in a setting where the intended semantic models are the full structures, the full type hierarchies over preorders for the base types. The syntax allows for the specification that a given symbol be interpreted as a monotone function, or an antitone function, or both. There is a natural set of five rules for inequational reasoning. One can add variables and also add a substitution rule, but we observe that this logic would be incomplete for full structures. This is why the completeness result in this paper pertains to terms without variables. Since the completeness is already known for the class of general (Henkin) structures, we are interested in full structures. We present a completeness theorem. Our result is not optimal because we restrict to base preorders which have a weak completeness property: every pair of elements has an upper bound and a lower bound. To compensate we add several rules to the logic. We also present extensions and variations of our completeness result.
Finding a Battleship of Uncertain Shape
Venue: arXiv cs.DM 2022
Year: 2022

Motivated by a game of Battleship, we consider the problem of efficiently hitting a ship of an uncertain shape within a large playing board. Formally, we fix a dimension $d\in\{1,2\}$. A ship is a subset of $\mathbb{Z}^d$. Given a family $F$ of ships, we say that an infinite subset $X\subset\mathbb{Z}^d$ of the cells pierces $F$, if it intersects each translate of each ship in $F$ (by a vector in $\mathbb{Z}^d$). In this work, we study the lowest possible (asymptotic) density $π(F)$ of such a piercing subset. To our knowledge, this problem has previously been studied only in the special case $|F|=1$ (a single ship). As our main contribution, we present a formula for $π(F)$ when $F$ consists of 2 ships of size 2 each, and we identify the toughest families in several other cases. We also implement an algorithm for finding $π(F)$ in 1D.