OpenRaiser/Intern-Atlas huggingface dataset:
Hardness Results for Minimizing the Covariance of Randomly Signed Sum of Vectors
Venue: arXiv cs.CC 2022
Year: 2022

Given vectors $\mathbb{v}_1, \ldots, \mathbb{v}_n \in \mathbb{R}^d$ with Euclidean norm at most $1$ and $\mathbb{x}_0 \in [-1,1]^n$, our goal is to sample a random signing $\mathbb{x} \in \{\pm 1\}^n$ with $\mathbb{E}[\mathbb{x}] = \mathbb{x}_0$ such that the operator norm of the covariance of the signed sum of the vectors $\sum_{i=1}^n \mathbb{x}(i) \mathbb{v}_i$ is as small as possible. This problem arises from the algorithmic discrepancy theory and its application in the design of randomized experiments. It is known that one can sample a random signing with expectation $\mathbb{x}_0$ and the covariance operator norm at most $1$. In this paper, we prove two hardness results for this problem. First, we show it is NP-hard to distinguish a list of vectors for which there exists a random signing with expectation ${\bf 0}$ such that the operator norm is $0$ from those for which any signing with expectation ${\bf 0}$ must have the operator norm $Ω(1)$. Second, we consider $\mathbb{x}_0 \in [-1,1]^n$ whose entries are all around an arbitrarily fixed $p \in [-1,1]$. We show it is NP-hard to distinguish a list of vectors for which there exists a random signing with expectation $\mathbb{x}_0$ such that the operator norm is $0$ from those for which any signing with expectation ${\bf 0}$ must have the operator norm $Ω((1-|p|)^2)$.
Lower Bounds on Retroactive Data Structures
Venue: arXiv cs.DS 2022
Year: 2022

We prove essentially optimal fine-grained lower bounds on the gap between a data structure and a partially retroactive version of the same data structure. Precisely, assuming any one of three standard conjectures, we describe a problem that has a data structure where operations run in $O(T(n,m))$ time per operation, but any partially retroactive version of that data structure requires $T(n,m) \cdot m^{1-o(1)}$ worst-case time per operation, where $n$ is the size of the data structure at any time and $m$ is the number of operations. Any data structure with operations running in $O(T(n,m))$ time per operation can be converted (via the "rollback method") into a partially retroactive data structure running in $O(T(n,m) \cdot m)$ time per operation, so our lower bound is tight up to an $m^{o(1)}$ factor common in fine-grained complexity.
A Maximum Log-Likelihood Method for Imbalanced Few-Shot Learning Tasks
Venue: arXiv cs.CV 2022
Year: 2022

Few-shot learning is a rapidly evolving area of research in machine learning where the goal is to classify unlabeled data with only one or "a few" labeled exemplary samples. Neural networks are typically trained to minimize a distance metric between labeled exemplary samples and a query set. Early few-shot approaches use an episodic training process to sub-sample the training data into few-shot batches. This training process matches the sub-sampling done on evaluation. Recently, conventional supervised training coupled with a cosine distance has achieved superior performance for few-shot. Despite the diversity of few-shot approaches over the past decade, most methods still rely on the cosine or Euclidean distance layer between the latent features of the trained network. In this work, we investigate the distributions of trained few-shot features and demonstrate that they can be roughly approximated as exponential distributions. Under this assumption of an exponential distribution, we propose a new maximum log-likelihood metric for few-shot architectures. We demonstrate that the proposed metric achieves superior performance accuracy w.r.t. conventional similarity metrics (e.g., cosine, Euclidean, etc.), and achieve state-of-the-art inductive few-shot performance. Further, additional gains can be achieved by carefully combining multiple metrics and neither of our methods require post-processing feature transformations, which are common to many algorithms. Finally, we demonstrate a novel iterative algorithm designed around our maximum log-likelihood approach that achieves state-of-the-art transductive few-shot performance when the evaluation data is imbalanced. We have made our code publicly available at https://github.com/samuelhess/MLL_FSL/.
Semantic-Aware Local-Global Vision Transformer
Venue: arXiv cs.CV 2022
Year: 2022

Vision Transformers have achieved remarkable progresses, among which Swin Transformer has demonstrated the tremendous potential of Transformer for vision tasks. It surmounts the key challenge of high computational complexity by performing local self-attention within shifted windows. In this work we propose the Semantic-Aware Local-Global Vision Transformer (SALG), to further investigate two potential improvements towards Swin Transformer. First, unlike Swin Transformer that performs uniform partition to produce equal size of regular windows for local self-attention, our SALG performs semantic segmentation in an unsupervised way to explore the underlying semantic priors in the image. As a result, each segmented region can correspond to a semantically meaningful part in the image, potentially leading to more effective features within each of segmented regions. Second, instead of only performing local self-attention within local windows as Swin Transformer does, the proposed SALG performs both 1) local intra-region self-attention for learning fine-grained features within each region and 2) global inter-region feature propagation for modeling global dependencies among all regions. Consequently, our model is able to obtain the global view when learning features for each token, which is the essential advantage of Transformer. Owing to the explicit modeling of the semantic priors and the proposed local-global modeling mechanism, our SALG is particularly advantageous for small-scale models when the modeling capacity is not sufficient for other models to learn semantics implicitly. Extensive experiments across various vision tasks demonstrates the merit of our model over other vision Transformers, especially in the small-scale modeling scenarios.
Fingerprint Pore Detection: A Survey
Venue: arXiv cs.CV 2022
Year: 2022

This work presents the first survey on fingerprint pore detection. The survey provides a general overview of the field and discusses methods, datasets, and evaluation protocols. We also present a baseline method inspired on the state-of-the-art that implements a customizable Fully Convolutional Network, whose hyperparameters were tuned to achieve optimal pore detection rates. Finally, we also reimplementated three other approaches proposed in the literature for evaluation purposes. We have made the source code of (1) the baseline method, (2) the reimplemented approaches, and (3) the training and evaluation processes for two different datasets available to the public to attract more researchers to the field and to facilitate future comparisons under the same conditions. The code is available in the following repository: https://github.com/azimIbragimov/Fingerprint-Pore-Detection-A-Survey
Rectified Pessimistic-Optimistic Learning for Stochastic Continuum-armed Bandit with Constraints
Venue: arXiv cs.LG 2022
Year: 2022

This paper studies the problem of stochastic continuum-armed bandit with constraints (SCBwC), where we optimize a black-box reward function $f(x)$ subject to a black-box constraint function $g(x)\leq 0$ over a continuous space $\mathcal X$. We model reward and constraint functions via Gaussian processes (GPs) and propose a Rectified Pessimistic-Optimistic Learning framework (RPOL), a penalty-based method incorporating optimistic and pessimistic GP bandit learning for reward and constraint functions, respectively. We consider the metric of cumulative constraint violation $\sum_{t=1}^T(g(x_t))^{+},$ which is strictly stronger than the traditional long-term constraint violation $\sum_{t=1}^Tg(x_t).$ The rectified design for the penalty update and the pessimistic learning for the constraint function in RPOL guarantee the cumulative constraint violation is minimal. RPOL can achieve sublinear regret and cumulative constraint violation for SCBwC and its variants (e.g., under delayed feedback and non-stationary environment). These theoretical results match their unconstrained counterparts. Our experiments justify RPOL outperforms several existing baseline algorithms.
MNER-QG: An End-to-End MRC framework for Multimodal Named Entity Recognition with Query Grounding
Venue: arXiv cs.CV 2022
Year: 2022

Multimodal named entity recognition (MNER) is a critical step in information extraction, which aims to detect entity spans and classify them to corresponding entity types given a sentence-image pair. Existing methods either (1) obtain named entities with coarse-grained visual clues from attention mechanisms, or (2) first detect fine-grained visual regions with toolkits and then recognize named entities. However, they suffer from improper alignment between entity types and visual regions or error propagation in the two-stage manner, which finally imports irrelevant visual information into texts. In this paper, we propose a novel end-to-end framework named MNER-QG that can simultaneously perform MRC-based multimodal named entity recognition and query grounding. Specifically, with the assistance of queries, MNER-QG can provide prior knowledge of entity types and visual regions, and further enhance representations of both texts and images. To conduct the query grounding task, we provide manual annotations and weak supervisions that are obtained via training a highly flexible visual grounding model with transfer learning. We conduct extensive experiments on two public MNER datasets, Twitter2015 and Twitter2017. Experimental results show that MNER-QG outperforms the current state-of-the-art models on the MNER task, and also improves the query grounding performance.
Searching for Uncollected Litter with Computer Vision
Venue: arXiv cs.CV 2022
Year: 2022

This study combines photo metadata and computer vision to quantify where uncollected litter is present. Images from the Trash Annotations in Context (TACO) dataset were used to teach an algorithm to detect 10 categories of garbage. Although it worked well with smartphone photos, it struggled when trying to process images from vehicle mounted cameras. However, increasing the variety of perspectives and backgrounds in the dataset will help it improve in unfamiliar situations. These data are plotted onto a map which, as accuracy improves, could be used for measuring waste management strategies and quantifying trends.
Puffy: A Step-by-step Guide to Craft Bio-inspired Artifacts with Interactive Materiality
Venue: arXiv cs.HC 2022
Year: 2022

A rising number of HCI scholars have begun to use materiality as a starting point for exploring the design's potential and restrictions. Despite the theoretical flourishing, the practical design process and instruction for beginner practitioners are still in scarcity. We leveraged the pictorial format to illustrate our crafting process of Puffy, a bio-inspired artifact that features a cilia-mimetic surface expressing anthropomorphic qualities through shape changes. Our approach consists of three key activities (i.e., analysis, synthesis, and detailing) interlaced recursively throughout the journey. Using this approach, we analyzed different input sources, synthesized peers' critiques and self-reflection, and detailed the designed experience with iterative prototypes. Building on a reflective analysis of our approach, we concluded with a set of practical implications and design recommendations to inform other practitioners to initiate their investigations in interactive materiality.
Latent SHAP: Toward Practical Human-Interpretable Explanations
Venue: arXiv cs.LG 2022
Year: 2022

Model agnostic feature attribution algorithms (such as SHAP and LIME) are ubiquitous techniques for explaining the decisions of complex classification models, such as deep neural networks. However, since complex classification models produce superior performance when trained on low-level (or encoded) features, in many cases, the explanations generated by these algorithms are neither interpretable nor usable by humans. Methods proposed in recent studies that support the generation of human-interpretable explanations are impractical, because they require a fully invertible transformation function that maps the model's input features to the human-interpretable features. In this work, we introduce Latent SHAP, a black-box feature attribution framework that provides human-interpretable explanations, without the requirement for a fully invertible transformation function. We demonstrate Latent SHAP's effectiveness using (1) a controlled experiment where invertible transformation functions are available, which enables robust quantitative evaluation of our method, and (2) celebrity attractiveness classification (using the CelebA dataset) where invertible transformation functions are not available, which enables thorough qualitative evaluation of our method.
Rethinking Data Augmentation for Single-source Domain Generalization in Medical Image Segmentation
Venue: arXiv cs.CV 2022
Year: 2022

Single-source domain generalization (SDG) in medical image segmentation is a challenging yet essential task as domain shifts are quite common among clinical image datasets. Previous attempts most conduct global-only/random augmentation. Their augmented samples are usually insufficient in diversity and informativeness, thus failing to cover the possible target domain distribution. In this paper, we rethink the data augmentation strategy for SDG in medical image segmentation. Motivated by the class-level representation invariance and style mutability of medical images, we hypothesize that unseen target data can be sampled from a linear combination of $C$ (the class number) random variables, where each variable follows a location-scale distribution at the class level. Accordingly, data augmented can be readily made by sampling the random variables through a general form. On the empirical front, we implement such strategy with constrained B$\acute{\rm e}$zier transformation on both global and local (i.e. class-level) regions, which can largely increase the augmentation diversity. A Saliency-balancing Fusion mechanism is further proposed to enrich the informativeness by engaging the gradient information, guiding augmentation with proper orientation and magnitude. As an important contribution, we prove theoretically that our proposed augmentation can lead to an upper bound of the generalization risk on the unseen target domain, thus confirming our hypothesis. Combining the two strategies, our Saliency-balancing Location-scale Augmentation (SLAug) exceeds the state-of-the-art works by a large margin in two challenging SDG tasks. Code is available at https://github.com/Kaiseem/SLAug .
Universal convex covering problems under translation and discrete rotations
Venue: arXiv cs.CG 2022
Year: 2022

We consider the smallest-area universal covering of planar objects of perimeter 2 (or equivalently closed curves of length 2) allowing translation and discrete rotations. In particular, we show that the solution is an equilateral triangle of height 1 when translation and discrete rotation of $π$ are allowed. Our proof is purely geometric and elementary. We also give convex coverings of closed curves of length 2 under translation and discrete rotations of multiples of $π/2$ and $2π/3$. We show a minimality of the covering for discrete rotation of multiples of $π/2$, which is an equilateral triangle of height smaller than 1, and conjecture that the covering is the smallest-area convex covering. Finally, we give the smallest-area convex coverings of all unit segments under translation and discrete rotations $2π/k$ for all integers $k\ge 3$.
Adjustable Method Based on Body Parts for Improving the Accuracy of 3D Reconstruction in Visually Important Body Parts from Silhouettes
Venue: arXiv cs.CV 2022
Year: 2022

This research proposes a novel adjustable algorithm for reconstructing 3D body shapes from front and side silhouettes. Most recent silhouette-based approaches use a deep neural network trained by silhouettes and key points to estimate the shape parameters but cannot accurately fit the model to the body contours and consequently are struggling to cover detailed body geometry, especially in the torso. In addition, in most of these cases, body parts have the same accuracy priority, making the optimization harder and avoiding reaching the optimum possible result in essential body parts, like the torso, which is visually important in most applications, such as virtual garment fitting. In the proposed method, we can adjust the expected accuracy for each body part based on our purpose by assigning coefficients for the distance of each body part between the projected 3D body and 2D silhouettes. To measure this distance, we first recognize the correspondent body parts using body segmentation in both views. Then, we align individual body parts by 2D rigid registration and match them using pairwise matching. The objective function tries to minimize the distance cost for the individual body parts in both views based on distances and coefficients by optimizing the statistical model parameters. We also handle the slight variation in the degree of arms and limbs by matching the pose. We evaluate the proposed method with synthetic body meshes from the normalized S-SCAPE. The result shows that the algorithm can more accurately reconstruct visually important body parts with high coefficients.
Spatially Sparse Precoding in Wideband Hybrid Terahertz Massive MIMO Systems
Venue: arXiv cs.IT 2022
Year: 2022

In terahertz (THz) massive multiple-input multiple-output (MIMO) systems, the combination of huge bandwidth and massive antennas results in severe beam split, thus making the conventional phase-shifter based hybrid precoding architecture ineffective. With the incorporation of true-time-delay (TTD) lines in the hardware implementation of the analog precoders, delay-phase precoding (DPP) emerges as a promising architecture to effectively overcome beam split. However, existing DPP approaches suffer from poor performance, high complexity, and weak robustness in practical THz channels. In this paper, we propose a novel DPP approach in wideband THz massive MIMO systems. First, the optimization problem is converted into a compressive sensing (CS) form, which can be solved by the extended spatially sparse precoding (SSP) algorithm. To compensate for beam split, frequency-dependent measurement matrices are introduced, which can be approximately realized by feasible phase and delay codebooks. Then, several efficient atom selection techniques are developed to further reduce the complexity of extended SSP. In simulation, the proposed DPP approach achieves superior performance, complexity, and robustness by using it alone or in combination with existing DPP approaches.
Machine Learning for Smart and Energy-Efficient Buildings
Venue: arXiv cs.LG 2022
Year: 2022

Energy consumption in buildings, both residential and commercial, accounts for approximately 40% of all energy usage in the U.S., and similar numbers are being reported from countries around the world. This significant amount of energy is used to maintain a comfortable, secure, and productive environment for the occupants. So, it is crucial that the energy consumption in buildings must be optimized, all the while maintaining satisfactory levels of occupant comfort, health, and safety. Recently, Machine Learning has been proven to be an invaluable tool in deriving important insights from data and optimizing various systems. In this work, we review the ways in which machine learning has been leveraged to make buildings smart and energy-efficient. For the convenience of readers, we provide a brief introduction of several machine learning paradigms and the components and functioning of each smart building system we cover. Finally, we discuss challenges faced while implementing machine learning algorithms in smart buildings and provide future avenues for research at the intersection of smart buildings and machine learning.
3inGAN: Learning a 3D Generative Model from Images of a Self-similar Scene
Venue: arXiv cs.CV 2022
Year: 2022

We introduce 3inGAN, an unconditional 3D generative model trained from 2D images of a single self-similar 3D scene. Such a model can be used to produce 3D "remixes" of a given scene, by mapping spatial latent codes into a 3D volumetric representation, which can subsequently be rendered from arbitrary views using physically based volume rendering. By construction, the generated scenes remain view-consistent across arbitrary camera configurations, without any flickering or spatio-temporal artifacts. During training, we employ a combination of 2D, obtained through differentiable volume tracing, and 3D Generative Adversarial Network (GAN) losses, across multiple scales, enforcing realism on both its 3D structure and the 2D renderings. We show results on semi-stochastic scenes of varying scale and complexity, obtained from real and synthetic sources. We demonstrate, for the first time, the feasibility of learning plausible view-consistent 3D scene variations from a single exemplar scene and provide qualitative and quantitative comparisons against recent related methods.
Adversarial Rademacher Complexity of Deep Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

Deep neural networks are vulnerable to adversarial attacks. Ideally, a robust model shall perform well on both the perturbed training data and the unseen perturbed test data. It is found empirically that fitting perturbed training data is not hard, but generalizing to perturbed test data is quite difficult. To better understand adversarial generalization, it is of great interest to study the adversarial Rademacher complexity (ARC) of deep neural networks. However, how to bound ARC in multi-layers cases is largely unclear due to the difficulty of analyzing adversarial loss in the definition of ARC. There have been two types of attempts of ARC. One is to provide the upper bound of ARC in linear and one-hidden layer cases. However, these approaches seem hard to extend to multi-layer cases. Another is to modify the adversarial loss and provide upper bounds of Rademacher complexity on such surrogate loss in multi-layer cases. However, such variants of Rademacher complexity are not guaranteed to be bounds for meaningful robust generalization gaps (RGG). In this paper, we provide a solution to this unsolved problem. Specifically, we provide the first bound of adversarial Rademacher complexity of deep neural networks. Our approach is based on covering numbers. We provide a method to handle the robustify function classes of DNNs such that we can calculate the covering numbers. Finally, we provide experiments to study the empirical implication of our bounds and provide an analysis of poor adversarial generalization.
CoMMA Protocol: Towards Complete Mitigation of Maximal Extractable Value (MEV) Attacks
Venue: arXiv cs.CR 2022
Year: 2022

MEV attacks have been an omnipresent evil in the blockchain world, an implicit tax that uninformed users pay for using the service. The problem arises from the miners' ability to reorder and insert arbitrary transactions in the blocks they mine. This paper proposes a 2-phased transaction protocol to eliminate MEV attacks. The user requests an interaction token from the on-chain counter-party. This token serves as a blind preemption for the counter-party and prevents the reordering of transactions at lower levels in the blockchain framework. We prove the correctness of the CoMMA protocol and demonstrate its efficacy against MEV attacks.