OpenRaiser/Intern-Atlas huggingface dataset:
Sum-of-Squares Relaxations for Information Theory and Variational Inference
Venue: arXiv cs.IT 2023
Year: 2023

We consider extensions of the Shannon relative entropy, referred to as $f$-divergences.Three classical related computational problems are typically associated with these divergences: (a) estimation from moments, (b) computing normalizing integrals, and (c) variational inference in probabilistic models. These problems are related to one another through convex duality, and for all them, there are many applications throughout data science, and we aim for computationally tractable approximation algorithms that preserve properties of the original problem such as potential convexity or monotonicity. In order to achieve this, we derive a sequence of convex relaxations for computing these divergences from non-centered covariance matrices associated with a given feature vector: starting from the typically non-tractable optimal lower-bound, we consider an additional relaxation based on ``sums-of-squares'', which is is now computable in polynomial time as a semidefinite program. We also provide computationally more efficient relaxations based on spectral information divergences from quantum information theory. For all of the tasks above, beyond proposing new relaxations, we derive tractable convex optimization algorithms, and we present illustrations on multivariate trigonometric polynomials and functions on the Boolean hypercube.
On the Importance of Application-Grounded Experimental Design for Evaluating Explainable ML Methods
Venue: arXiv cs.LG 2023
Year: 2023

Most existing evaluations of explainable machine learning (ML) methods rely on simplifying assumptions or proxies that do not reflect real-world use cases; the handful of more robust evaluations on real-world settings have shortcomings in their design, resulting in limited conclusions of methods' real-world utility. In this work, we seek to bridge this gap by conducting a study that evaluates three popular explainable ML methods in a setting consistent with the intended deployment context. We build on a previous study on e-commerce fraud detection and make crucial modifications to its setup relaxing the simplifying assumptions made in the original work that departed from the deployment context. In doing so, we draw drastically different conclusions from the earlier work and find no evidence for the incremental utility of the tested methods in the task. Our results highlight how seemingly trivial experimental design choices can yield misleading conclusions, with lessons about the necessity of not only evaluating explainable ML methods using tasks, data, users, and metrics grounded in the intended deployment contexts but also developing methods tailored to specific applications. In addition, we believe the design of this experiment can serve as a template for future study designs evaluating explainable ML methods in other real-world contexts.
A Comprehensive Survey on Deep Gait Recognition: Algorithms, Datasets and Challenges
Venue: arXiv cs.CV 2023
Year: 2023

Gait recognition aims to identify a person at a distance, serving as a promising solution for long-distance and less-cooperation pedestrian recognition. Recently, significant advancements in gait recognition have achieved inspiring success in many challenging scenarios by utilizing deep learning techniques. Against the backdrop that deep gait recognition has achieved almost perfect performance in laboratory datasets, much recent research has introduced new challenges for gait recognition, including robust deep representation modeling, in-the-wild gait recognition, and even recognition from new visual sensors such as infrared and depth cameras. Meanwhile, the increasing performance of gait recognition might also reveal concerns about biometrics security and privacy prevention for society. We provide a comprehensive survey on recent literature using deep learning and a discussion on the privacy and security of gait biometrics. This survey reviews the existing deep gait recognition methods through a novel view based on our proposed taxonomy. The proposed taxonomy differs from the conventional taxonomy of categorizing available gait recognition methods into the model- or appearance-based methods, while our taxonomic hierarchy considers deep gait recognition from two perspectives: deep representation learning and deep network architectures, illustrating the current approaches from both micro and macro levels. We also include up-to-date reviews of datasets and performance evaluations on diverse scenarios. Finally, we introduce privacy and security concerns on gait biometrics and discuss outstanding challenges and potential directions for future research.
Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes
Venue: arXiv cs.LO 2023
Year: 2023

Monadically stable and monadically NIP classes of structures were initially studied in the context of model theory and defined in logical terms. They have recently attracted attention in the area of structural graph theory, as they generalize notions such as nowhere denseness, bounded cliquewidth, and bounded twinwidth. Our main result is the - to the best of our knowledge first - purely combinatorial characterization of monadically stable classes of graphs, in terms of a property dubbed flip-flatness. A class $\mathcal{C}$ of graphs is flip-flat if for every fixed radius $r$, every sufficiently large set of vertices of a graph $G \in \mathcal{C}$ contains a large subset of vertices with mutual distance larger than $r$, where the distance is measured in some graph $G'$ that can be obtained from $G$ by performing a bounded number of flips that swap edges and non-edges within a subset of vertices. Flip-flatness generalizes the notion of uniform quasi-wideness, which characterizes nowhere dense classes and had a key impact on the combinatorial and algorithmic treatment of nowhere dense classes. To obtain this result, we develop tools that also apply to the more general monadically NIP classes, based on the notion of indiscernible sequences from model theory. We show that in monadically stable and monadically NIP classes indiscernible sequences impose a strong combinatorial structure on their definable neighborhoods. All our proofs are constructive and yield efficient algorithms.
Orthogonal Delay-Doppler Division Multiplexing Modulation
Venue: arXiv cs.IT 2023
Year: 2023

Inspired by the orthogonal time frequency space (OTFS) modulation, in this paper, we consider designing a multicarrier (MC) modulation on delay-Doppler (DD) plane, to couple the modulated signal with a doubly-selective channel having DD resolutions. A key challenge for the design of DD plane MC modulation is to investigate whether a realizable pulse orthogonal with respect to the DD plane's fine resolutions exists or not. To this end, we first indicate that a feasible DD plane MC modulation is essentially a type of staggered multitone modulation. Then, analogous to orthogonal frequency division multiplexing, we propose an orthogonal delay-Doppler division multiplexing (ODDM) modulation, and design the corresponding transmit pulse. Furthermore, we prove that the proposed transmit pulse is orthogonal with respect to the DD plane's resolutions and therefore a realizable DD plane orthogonal pulse does exist. The orthogonality of this particular pulse significantly eases the derivation of the ODDM's DD domain channel input-output relation, and yields a channel matrix with an elegant block-circulant-like structure. We demonstrate that the ODDM outperforms the OTFS in terms of out-of-band emission and bit error rate, by achieving perfect coupling between the modulated signal and the DD channel.
SImProv: Scalable Image Provenance Framework for Robust Content Attribution
Venue: arXiv cs.CV 2023
Year: 2023

We present SImProv - a scalable image provenance framework to match a query image back to a trusted database of originals and identify possible manipulations on the query. SImProv consists of three stages: a scalable search stage for retrieving top-k most similar images; a re-ranking and near-duplicated detection stage for identifying the original among the candidates; and finally a manipulation detection and visualization stage for localizing regions within the query that may have been manipulated to differ from the original. SImProv is robust to benign image transformations that commonly occur during online redistribution, such as artifacts due to noise and recompression degradation, as well as out-of-place transformations due to image padding, warping, and changes in size and shape. Robustness towards out-of-place transformations is achieved via the end-to-end training of a differentiable warping module within the comparator architecture. We demonstrate effective retrieval and manipulation detection over a dataset of 100 million images.
Model-Based Approaches to Channel Charting
Venue: arXiv cs.ET 2023
Year: 2023

We present new ways of producing a channel chart [1] employing model-based approaches. We estimate the angle of arrival theta and the distance rho between the base station and the user equipment by employing our algorithms, inverse of the root sum squares of channel coefficients (ISQ) algorithm, linear regression (LR) algorithm, and MUSIC/MUSIC (MM) algorithm. We compare these methods with the channel charting algorithms principal component analysis (PCA), Sammon's method (SM), and autoencoder (AE) [1]. We show that ISQ, LR, and MM surpass PCA, SM, and AE in performance. We also compare our algorithm MM with an algorithm from the literature that uses the MUSIC algorithm jointly on theta and rho. We call this algorithm the JM algorithm. JM performs very slightly better than MM but at a substantial increase in complexity. Finally, we introduce the rotate-and-sum (RS) algorithm which has about the same performance as the MM and JM algorithms. Unlike MUSIC, RS does not employ eigenvalue and eigenvector analysis. Thus, it is more suitable for direct register transfer logic (RTL) implementation.
Data Redaction from Pre-trained GANs
Venue: arXiv cs.LG 2023
Year: 2023

Large pre-trained generative models are known to occasionally output undesirable samples, which undermines their trustworthiness. The common way to mitigate this is to re-train them differently from scratch using different data or different regularization -- which uses a lot of computational resources and does not always fully address the problem. In this work, we take a different, more compute-friendly approach and investigate how to post-edit a model after training so that it ''redacts'', or refrains from outputting certain kinds of samples. We show that redaction is a fundamentally different task from data deletion, and data deletion may not always lead to redaction. We then consider Generative Adversarial Networks (GANs), and provide three different algorithms for data redaction that differ on how the samples to be redacted are described. Extensive evaluations on real-world image datasets show that our algorithms out-perform data deletion baselines, and are capable of redacting data while retaining high generation quality at a fraction of the cost of full re-training.
SRCN3D: Sparse R-CNN 3D for Compact Convolutional Multi-View 3D Object Detection and Tracking
Venue: arXiv cs.CV 2023
Year: 2023

Detection and tracking of moving objects is an essential component in environmental perception for autonomous driving. In the flourishing field of multi-view 3D camera-based detectors, different transformer-based pipelines are designed to learn queries in 3D space from 2D feature maps of perspective views, but the dominant dense BEV query mechanism is computationally inefficient. This paper proposes Sparse R-CNN 3D (SRCN3D), a novel two-stage fully-sparse detector that incorporates sparse queries, sparse attention with box-wise sampling, and sparse prediction. SRCN3D adopts a cascade structure with the twin-track update of both a fixed number of query boxes and latent query features. Our novel sparse feature sampling module only utilizes local 2D region of interest (RoI) features calculated by the projection of 3D query boxes for further box refinement, leading to a fully-convolutional and deployment-friendly pipeline. For multi-object tracking, motion features, query features and RoI features are comprehensively utilized in multi-hypotheses data association. Extensive experiments on nuScenes dataset demonstrate that SRCN3D achieves competitive performance in both 3D object detection and multi-object tracking tasks, while also exhibiting superior efficiency compared to transformer-based methods. Code and models are available at https://github.com/synsin0/SRCN3D.
Beyond neural scaling laws: beating power law scaling via data pruning
Venue: arXiv cs.LG 2023
Year: 2023

Widely observed neural scaling laws, in which error falls off as a power of the training set size, model size, or both, have driven substantial performance improvements in deep learning. However, these improvements through scaling alone require considerable costs in compute and energy. Here we focus on the scaling of error with dataset size and show how in theory we can break beyond power law scaling and potentially even reduce it to exponential scaling instead if we have access to a high-quality data pruning metric that ranks the order in which training examples should be discarded to achieve any pruned dataset size. We then test this improved scaling prediction with pruned dataset size empirically, and indeed observe better than power law scaling in practice on ResNets trained on CIFAR-10, SVHN, and ImageNet. Next, given the importance of finding high-quality pruning metrics, we perform the first large-scale benchmarking study of ten different data pruning metrics on ImageNet. We find most existing high performing metrics scale poorly to ImageNet, while the best are computationally intensive and require labels for every image. We therefore developed a new simple, cheap and scalable self-supervised pruning metric that demonstrates comparable performance to the best supervised metrics. Overall, our work suggests that the discovery of good data-pruning metrics may provide a viable path forward to substantially improved neural scaling laws, thereby reducing the resource costs of modern deep learning.
Smoothed Analysis of Social Choice, Revisited
Venue: arXiv cs.GT 2023
Year: 2023

A canonical problem in social choice is how to aggregate ranked votes: given $n$ voters' rankings over $m$ candidates, what voting rule $f$ should we use to aggregate these votes into a single winner? One standard method for comparing voting rules is by their satisfaction of axioms - properties that we want a "reasonable" rule to satisfy. Unfortunately, this approach leads to several impossibilities: no voting rule can simultaneously satisfy all the properties we want, at least in the worst case over all possible inputs. Motivated by this, we consider a relaxation of these worst case requirements. We do so using a "smoothed" model of social choice, where votes are perturbed with small amounts of noise. If, no matter which input profile we start with, the probability (post-noise) of an axiom being satisfied is large, we will consider the axiom as good as satisfied - called "smoothed-satisfied" - even if it may be violated in the worst case. Our model is a mild restriction of Lirong Xia's, and corresponds closely to that in Spielman and Teng's original work on smoothed analysis. Much work has been done so far in several papers by Xia on axiom satisfaction under such noise. In our paper, we aim to give a more cohesive overview on when smoothed analysis of social choice is useful. Within our model, we give simple sufficient conditions for smoothed-satisfaction or smoothed-violation of several previously-unstudied axioms and paradoxes, plus many of those studied by Xia. We then observe that, in a practically important subclass of noise models, although convergence eventually occurs, known rates may require an extremely large number of voters. Motivated by this, we prove bounds specifically within a canonical noise model from this subclass - the Mallows model. Here, we present a more nuanced picture on exactly when smoothed analysis can help.
IBP Regularization for Verified Adversarial Robustness via Branch-and-Bound
Venue: arXiv cs.LG 2023
Year: 2023

Recent works have tried to increase the verifiability of adversarially trained networks by running the attacks over domains larger than the original perturbations and adding various regularization terms to the objective. However, these algorithms either underperform or require complex and expensive stage-wise training procedures, hindering their practical applicability. We present IBP-R, a novel verified training algorithm that is both simple and effective. IBP-R induces network verifiability by coupling adversarial attacks on enlarged domains with a regularization term, based on inexpensive interval bound propagation, that minimizes the gap between the non-convex verification problem and its approximations. By leveraging recent branch-and-bound frameworks, we show that IBP-R obtains state-of-the-art verified robustness-accuracy trade-offs for small perturbations on CIFAR-10 while training significantly faster than relevant previous work. Additionally, we present UPB, a novel branching strategy that, relying on a simple heuristic based on $β$-CROWN, reduces the cost of state-of-the-art branching algorithms while yielding splits of comparable quality.
A Validity Perspective on Evaluating the Justified Use of Data-driven Decision-making Algorithms
Venue: arXiv cs.LG 2023
Year: 2023

Recent research increasingly brings to question the appropriateness of using predictive tools in complex, real-world tasks. While a growing body of work has explored ways to improve value alignment in these tools, comparatively less work has centered concerns around the fundamental justifiability of using these tools. This work seeks to center validity considerations in deliberations around whether and how to build data-driven algorithms in high-stakes domains. Toward this end, we translate key concepts from validity theory to predictive algorithms. We apply the lens of validity to re-examine common challenges in problem formulation and data issues that jeopardize the justifiability of using predictive algorithms and connect these challenges to the social science discourse around validity. Our interdisciplinary exposition clarifies how these concepts apply to algorithmic decision making contexts. We demonstrate how these validity considerations could distill into a series of high-level questions intended to promote and document reflections on the legitimacy of the predictive task and the suitability of the data.
Design and Motion Planning for a Reconfigurable Robotic Base
Venue: arXiv cs.RO 2023
Year: 2023

A robotic platform for mobile manipulation needs to satisfy two contradicting requirements for many real-world applications: A compact base is required to navigate through cluttered indoor environments, while the support needs to be large enough to prevent tumbling or tip over, especially during fast manipulation operations with heavy payloads or forceful interaction with the environment. This paper proposes a novel robot design that fulfills both requirements through a versatile footprint. It can reconfigure its footprint to a narrow configuration when navigating through tight spaces and to a wide stance when manipulating heavy objects. Furthermore, its triangular configuration allows for high-precision tasks on uneven ground by preventing support switches. A model predictive control strategy is presented that unifies planning and control for simultaneous navigation, reconfiguration, and manipulation. It converts task-space goals into whole-body motion plans for the new robot. The proposed design has been tested extensively with a hardware prototype. The footprint reconfiguration allows to almost completely remove manipulation-induced vibrations. The control strategy proves effective in both lab experiment and during a real-world construction task.
Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
Venue: arXiv cs.DM 2023
Year: 2023

For a graph $G$, a subset $S \subseteq V(G)$ is called a \emph{resolving set} if for any two vertices $u,v \in V(G)$, there exists a vertex $w \in S$ such that $d(w,u) \neq d(w,v)$. The {\sc Metric Dimension} problem takes as input a graph $G$ and a positive integer $k$, and asks whether there exists a resolving set of size at most $k$. This problem was introduced in the 1970s and is known to be \NP-hard~[GT~61 in Garey and Johnson's book]. In the realm of parameterized complexity, Hartung and Nichterlein~[CCC~2013] proved that the problem is \W[2]-hard when parameterized by the natural parameter $k$. They also observed that it is \FPT\ when parameterized by the vertex cover number and asked about its complexity under \emph{smaller} parameters, in particular the feedback vertex set number. We answer this question by proving that {\sc Metric Dimension} is \W[1]-hard when parameterized by the combined parameter feedback vertex set number plus pathwidth. This also improves the result of Bonnet and Purohit~[IPEC 2019] which states that the problem is \W[1]-hard parameterized by the pathwidth. On the positive side, we show that {\sc Metric Dimension} is \FPT\ when parameterized by either the distance to cluster or the distance to co-cluster, both of which are smaller parameters than the vertex cover number.
Watch and Match: Supercharging Imitation with Regularized Optimal Transport
Venue: arXiv cs.RO 2023
Year: 2023

Imitation learning holds tremendous promise in learning policies efficiently for complex decision making problems. Current state-of-the-art algorithms often use inverse reinforcement learning (IRL), where given a set of expert demonstrations, an agent alternatively infers a reward function and the associated optimal policy. However, such IRL approaches often require substantial online interactions for complex control problems. In this work, we present Regularized Optimal Transport (ROT), a new imitation learning algorithm that builds on recent advances in optimal transport based trajectory-matching. Our key technical insight is that adaptively combining trajectory-matching rewards with behavior cloning can significantly accelerate imitation even with only a few demonstrations. Our experiments on 20 visual control tasks across the DeepMind Control Suite, the OpenAI Robotics Suite, and the Meta-World Benchmark demonstrate an average of 7.8X faster imitation to reach 90% of expert performance compared to prior state-of-the-art methods. On real-world robotic manipulation, with just one demonstration and an hour of online training, ROT achieves an average success rate of 90.1% across 14 tasks.
VL-CheckList: Evaluating Pre-trained Vision-Language Models with Objects, Attributes and Relations
Venue: arXiv cs.CV 2023
Year: 2023

Vision-Language Pretraining (VLP) models have recently successfully facilitated many cross-modal downstream tasks. Most existing works evaluated their systems by comparing the fine-tuned downstream task performance. However, only average downstream task accuracy provides little information about the pros and cons of each VLP method, let alone provides insights on how the community can improve the systems in the future. Inspired by the CheckList for testing natural language processing, we exploit VL-CheckList, a novel framework to understand the capabilities of VLP models. The proposed method divides the image-texting ability of a VLP model into three categories: objects, attributes, and relations, and uses a novel taxonomy to further break down these three aspects. We conduct comprehensive studies to analyze seven recently popular VLP models via the proposed framework. Results confirm the effectiveness of the proposed method by revealing fine-grained differences among the compared models that were not visible from downstream task-only evaluation. Further results show promising research direction in building better VLP models. Our data and code are available at: https://github.com/om-ai-lab/VL-CheckList.