OpenRaiser/Intern-Atlas huggingface dataset:
The complexity of decomposing a graph into a matching and a bounded linear forest
Venue: arXiv cs.CC 2023
Year: 2023

Deciding whether a graph can be edge-decomposed into a matching and a $k$-bounded linear forest was recently shown by Campbell, H{ö}rsch and Moore to be NP-complete for every $k \ge 9$, and solvable in polynomial time for $k=1,2$. In the first part of this paper, we close this gap by showing that this problem is in NP-complete for every $k \ge 3$. In the second part of the paper, we show that deciding whether a graph can be edge-decomposed into a matching and a $k$-bounded star forest is polynomially solvable for any $k \in \mathbb{N} \cup \{ \infty \}$, answering another question by Campbell, H{ö}rsch and Moore from the same paper.
Magic numbers in periodic sequences
Venue: arXiv cs.FL 2023
Year: 2023

In formal languages and automata theory, the magic number problem can be formulated as follows: for a given integer n, is it possible to find a number d in the range [n,2^n] such that there is no minimal deterministic finite automaton with d states that can be simulated by an optimal nondeterministic finite automaton with exactly n states? If such a number d exists, it is called magic. In this paper, we consider the magic number problem in the framework of deterministic automata with output, which are known to characterize automatic sequences. More precisely, we investigate magic numbers for periodic sequences viewed as either automatic, regular, or constant-recursive.
That's What I Said: Fully-Controllable Talking Face Generation
Venue: arXiv cs.CV 2023
Year: 2023

The goal of this paper is to synthesise talking faces with controllable facial motions. To achieve this goal, we propose two key ideas. The first is to establish a canonical space where every face has the same motion patterns but different identities. The second is to navigate a multimodal motion space that only represents motion-related features while eliminating identity information. To disentangle identity and motion, we introduce an orthogonality constraint between the two different latent spaces. From this, our method can generate natural-looking talking faces with fully controllable facial attributes and accurate lip synchronisation. Extensive experiments demonstrate that our method achieves state-of-the-art results in terms of both visual quality and lip-sync score. To the best of our knowledge, we are the first to develop a talking face generation framework that can accurately manifest full target facial motions including lip, head pose, and eye movements in the generated video without any additional supervision beyond RGB video with audio.
SegGPT: Segmenting Everything In Context
Venue: arXiv cs.CV 2023
Year: 2023

We present SegGPT, a generalist model for segmenting everything in context. We unify various segmentation tasks into a generalist in-context learning framework that accommodates different kinds of segmentation data by transforming them into the same format of images. The training of SegGPT is formulated as an in-context coloring problem with random color mapping for each data sample. The objective is to accomplish diverse tasks according to the context, rather than relying on specific colors. After training, SegGPT can perform arbitrary segmentation tasks in images or videos via in-context inference, such as object instance, stuff, part, contour, and text. SegGPT is evaluated on a broad range of tasks, including few-shot semantic segmentation, video object segmentation, semantic segmentation, and panoptic segmentation. Our results show strong capabilities in segmenting in-domain and out-of-domain targets, either qualitatively or quantitatively.
Adaptive Feature Fusion: Enhancing Generalization in Deep Learning Models
Venue: arXiv cs.CV 2023
Year: 2023

In recent years, deep learning models have demonstrated remarkable success in various domains, such as computer vision, natural language processing, and speech recognition. However, the generalization capabilities of these models can be negatively impacted by the limitations of their feature fusion techniques. This paper introduces an innovative approach, Adaptive Feature Fusion (AFF), to enhance the generalization of deep learning models by dynamically adapting the fusion process of feature representations. The proposed AFF framework is designed to incorporate fusion layers into existing deep learning architectures, enabling seamless integration and improved performance. By leveraging a combination of data-driven and model-based fusion strategies, AFF is able to adaptively fuse features based on the underlying data characteristics and model requirements. This paper presents a detailed description of the AFF framework, including the design and implementation of fusion layers for various architectures. Extensive experiments are conducted on multiple benchmark datasets, with the results demonstrating the superiority of the AFF approach in comparison to traditional feature fusion techniques. The analysis showcases the effectiveness of AFF in enhancing generalization capabilities, leading to improved performance across different tasks and applications. Finally, the paper discusses various real-world use cases where AFF can be employed, providing insights into its practical applicability. The conclusion highlights the potential for future research directions, including the exploration of advanced fusion strategies and the extension of AFF to other machine learning paradigms.
What makes a good data augmentation for few-shot unsupervised image anomaly detection?
Venue: arXiv cs.CV 2023
Year: 2023

Data augmentation is a promising technique for unsupervised anomaly detection in industrial applications, where the availability of positive samples is often limited due to factors such as commercial competition and sample collection difficulties. In this paper, how to effectively select and apply data augmentation methods for unsupervised anomaly detection is studied. The impact of various data augmentation methods on different anomaly detection algorithms is systematically investigated through experiments. The experimental results show that the performance of different industrial image anomaly detection (termed as IAD) algorithms is not significantly affected by the specific data augmentation method employed and that combining multiple data augmentation methods does not necessarily yield further improvements in the accuracy of anomaly detection, although it can achieve excellent results on specific methods. These findings provide useful guidance on selecting appropriate data augmentation methods for different requirements in IAD.
Explainable AI And Visual Reasoning: Insights From Radiology
Venue: arXiv cs.HC 2023
Year: 2023

Why do explainable AI (XAI) explanations in radiology, despite their promise of transparency, still fail to gain human trust? Current XAI approaches provide justification for predictions, however, these do not meet practitioners' needs. These XAI explanations lack intuitive coverage of the evidentiary basis for a given classification, posing a significant barrier to adoption. We posit that XAI explanations that mirror human processes of reasoning and justification with evidence may be more useful and trustworthy than traditional visual explanations like heat maps. Using a radiology case study, we demonstrate how radiology practitioners get other practitioners to see a diagnostic conclusion's validity. Machine-learned classifications lack this evidentiary grounding and consequently fail to elicit trust and adoption by potential users. Insights from this study may generalize to guiding principles for human-centered explanation design based on human reasoning and justification of evidence.
EGA-Depth: Efficient Guided Attention for Self-Supervised Multi-Camera Depth Estimation
Venue: arXiv cs.CV 2023
Year: 2023

The ubiquitous multi-camera setup on modern autonomous vehicles provides an opportunity to construct surround-view depth. Existing methods, however, either perform independent monocular depth estimations on each camera or rely on computationally heavy self attention mechanisms. In this paper, we propose a novel guided attention architecture, EGA-Depth, which can improve both the efficiency and accuracy of self-supervised multi-camera depth estimation. More specifically, for each camera, we use its perspective view as the query to cross-reference its neighboring views to derive informative features for this camera view. This allows the model to perform attention only across views with considerable overlaps and avoid the costly computations of standard self-attention. Given its efficiency, EGA-Depth enables us to exploit higher-resolution visual features, leading to improved accuracy. Furthermore, EGA-Depth can incorporate more frames from previous time steps as it scales linearly w.r.t. the number of views and frames. Extensive experiments on two challenging autonomous driving benchmarks nuScenes and DDAD demonstrate the efficacy of our proposed EGA-Depth and show that it achieves the new state-of-the-art in self-supervised multi-camera depth estimation.
From Social Engineering to Quantum Threats: Safeguarding User Wallets with FailSafe
Venue: arXiv cs.CR 2023
Year: 2023

While cryptocurrencies have been rapidly gaining adoption, secure wallet interactions are still elusive for many users, which frequently leads to loss of funds. Here we propose an approach to securing interactions with cryptocurrency wallets for end-users. The approach called FailSafe consists of several defence-in-depth measures that can be applied near-term as well as a tool called qMig for aiding eventual quantum migration.
Exposing and Mitigating Spurious Correlations for Cross-Modal Retrieval
Venue: arXiv cs.CV 2023
Year: 2023

Cross-modal retrieval methods are the preferred tool to search databases for the text that best matches a query image and vice versa. However, image-text retrieval models commonly learn to memorize spurious correlations in the training data, such as frequent object co-occurrence, instead of looking at the actual underlying reasons for the prediction in the image. For image-text retrieval, this manifests in retrieved sentences that mention objects that are not present in the query image. In this work, we introduce ODmAP@k, an object decorrelation metric that measures a model's robustness to spurious correlations in the training data. We use automatic image and text manipulations to control the presence of such object correlations in designated test data. Additionally, our data synthesis technique is used to tackle model biases due to spurious correlations of semantically unrelated objects in the training data. We apply our proposed pipeline, which involves the finetuning of image-text retrieval frameworks on carefully designed synthetic data, to three state-of-the-art models for image-text retrieval. This results in significant improvements for all three models, both in terms of the standard retrieval performance and in terms of our object decorrelation metric. The code is available at https://github.com/ExplainableML/Spurious_CM_Retrieval.
Personalising Digital Health Behaviour Change Interventions using Machine Learning and Domain Knowledge
Venue: arXiv cs.LG 2023
Year: 2023

We are developing a virtual coaching system that helps patients adhere to behavior change interventions (BCI). Our proposed system predicts whether a patient will perform the targeted behaviour and uses counterfactual examples with feature control to guide personalisation of BCI. We use simulated patient data with varying levels of receptivity to intervention to arrive at the study design which would enable evaluation of our system.
Deep Learning for Opinion Mining and Topic Classification of Course Reviews
Venue: arXiv cs.CL 2023
Year: 2023

Student opinions for a course are important to educators and administrators, regardless of the type of the course or the institution. Reading and manually analyzing open-ended feedback becomes infeasible for massive volumes of comments at institution level or online forums. In this paper, we collected and pre-processed a large number of course reviews publicly available online. We applied machine learning techniques with the goal to gain insight into student sentiments and topics. Specifically, we utilized current Natural Language Processing (NLP) techniques, such as word embeddings and deep neural networks, and state-of-the-art BERT (Bidirectional Encoder Representations from Transformers), RoBERTa (Robustly optimized BERT approach) and XLNet (Generalized Auto-regression Pre-training). We performed extensive experimentation to compare these techniques versus traditional approaches. This comparative study demonstrates how to apply modern machine learning approaches for sentiment polarity extraction and topic-based classification utilizing course feedback. For sentiment polarity, the top model was RoBERTa with 95.5% accuracy and 84.7% F1-macro, while for topic classification, an SVM (Support Vector Machine) was the top classifier with 79.8% accuracy and 80.6% F1-macro. We also provided an in-depth exploration of the effect of certain hyperparameters on the model performance and discussed our observations. These findings can be used by institutions and course providers as a guide for analyzing their own course feedback using NLP models towards self-evaluation and improvement.
A Comprehensive Survey of Upgradeable Smart Contract Patterns
Venue: arXiv cs.CR 2023
Year: 2023

In this work, we provide a comprehensive survey of smart contract upgradability patterns using proxies. A primary characteristic of smart contracts on the Ethereum blockchain is that they are immutable once implemented, no changes can be made. Taking human error into account, as well as technology improvements and newly discovered vulnerabilities, there has been a need to upgrade these smart contracts, which may hold enormous amounts of Ether and hence become the target of attacks. Several such attacks have caused tremendous losses in the past, as well as millions of dollars in Ether which has been locked away in broken contracts. Thus far we have collected many upgradable proxy patterns and studied their features to build a comprehensive catalog of patterns. We present a summary of these upgradable proxy patterns which we collected and studied. We scraped the source code for approximately 100000 verified contracts from Etherscan.io, the most popular block explorer for Ethereum, out of which we extracted around 64k unique files - most containing multiple contracts. We have begun to automate the analysis of these contracts using the popular static analysis tool Slither, while at the same time implementing much more robust detection of upgradable proxies using this framework. Comparing the results of the original implementation to our own, we have found that approximately 70 percent of the contracts which were initially flagged as upgradeable proxies are false positives which we have eliminated.
InstantBooth: Personalized Text-to-Image Generation without Test-Time Finetuning
Venue: arXiv cs.CV 2023
Year: 2023

Recent advances in personalized image generation allow a pre-trained text-to-image model to learn a new concept from a set of images. However, existing personalization approaches usually require heavy test-time finetuning for each concept, which is time-consuming and difficult to scale. We propose InstantBooth, a novel approach built upon pre-trained text-to-image models that enables instant text-guided image personalization without any test-time finetuning. We achieve this with several major components. First, we learn the general concept of the input images by converting them to a textual token with a learnable image encoder. Second, to keep the fine details of the identity, we learn rich visual feature representation by introducing a few adapter layers to the pre-trained model. We train our components only on text-image pairs without using paired images of the same concept. Compared to test-time finetuning-based methods like DreamBooth and Textual-Inversion, our model can generate competitive results on unseen concepts concerning language-image alignment, image fidelity, and identity preservation while being 100 times faster.
Toward Unsupervised 3D Point Cloud Anomaly Detection using Variational Autoencoder
Venue: arXiv cs.CV 2023
Year: 2023

In this paper, we present an end-to-end unsupervised anomaly detection framework for 3D point clouds. To the best of our knowledge, this is the first work to tackle the anomaly detection task on a general object represented by a 3D point cloud. We propose a deep variational autoencoder-based unsupervised anomaly detection network adapted to the 3D point cloud and an anomaly score specifically for 3D point clouds. To verify the effectiveness of the model, we conducted extensive experiments on the ShapeNet dataset. Through quantitative and qualitative evaluation, we demonstrate that the proposed method outperforms the baseline method. Our code is available at https://github.com/llien30/point_cloud_anomaly_detection.
Convex Minimization with Integer Minima in $\widetilde O(n^4)$ Time
Venue: arXiv cs.DS 2023
Year: 2023

Given a convex function $f$ on $\mathbb{R}^n$ with an integer minimizer, we show how to find an exact minimizer of $f$ using $O(n^2 \log n)$ calls to a separation oracle and $O(n^4 \log n)$ time. The previous best polynomial time algorithm for this problem given in [Jiang, SODA 2021, JACM 2022] achieves $O(n^2\log\log n/\log n)$ oracle complexity. However, the overall runtime of Jiang's algorithm is at least $\widetildeΩ(n^8)$, due to expensive sub-routines such as the Lenstra-Lenstra-Lovász (LLL) algorithm [Lenstra, Lenstra, Lovász, Math. Ann. 1982] and random walk based cutting plane method [Bertsimas, Vempala, JACM 2004]. Our significant speedup is obtained by a nontrivial combination of a faster version of the LLL algorithm due to [Neumaier, Stehlé, ISSAC 2016] that gives similar guarantees, the volumetric center cutting plane method (CPM) by [Vaidya, FOCS 1989] and its fast implementation given in [Jiang, Lee, Song, Wong, STOC 2020]. For the special case of submodular function minimization (SFM), our result implies a strongly polynomial time algorithm for this problem using $O(n^3 \log n)$ calls to an evaluation oracle and $O(n^4 \log n)$ additional arithmetic operations. Both the oracle complexity and the number of arithmetic operations of our more general algorithm are better than the previous best-known runtime algorithms for this specific problem given in [Lee, Sidford, Wong, FOCS 2015] and [Dadush, Végh, Zambelli, SODA 2018, MOR 2021].
The Rational Agent Benchmark for Data Visualization
Venue: arXiv cs.HC 2023
Year: 2023

Understanding how helpful a visualization is from experimental results is difficult because the observed performance is confounded with aspects of the study design, such as how useful the information that is visualized is for the task. We develop a rational agent framework for designing and interpreting visualization experiments. Our framework conceives two experiments with the same setup: one with behavioral agents (human subjects), and the other one with a hypothetical rational agent. A visualization is evaluated by comparing the expected performance of behavioral agents to that of a rational agent under different assumptions. Using recent visualization decision studies from the literature, we demonstrate how the framework can be used to pre-experimentally evaluate the experiment design by bounding the expected improvement in performance from having access to visualizations, and post-experimentally to deconfound errors of information extraction from errors of optimization, among other analyses.
Opinion Mining from YouTube Captions Using ChatGPT: A Case Study of Street Interviews Polling the 2023 Turkish Elections
Venue: arXiv cs.SI 2023
Year: 2023

Opinion mining plays a critical role in understanding public sentiment and preferences, particularly in the context of political elections. Traditional polling methods, while useful, can be expensive and less scalable. Social media offers an alternative source of data for opinion mining but presents challenges such as noise, biases, and platform limitations in data collection. In this paper, we propose a novel approach for opinion mining, utilizing YouTube's auto-generated captions from public interviews as a data source, specifically focusing on the 2023 Turkish elections as a case study. We introduce an opinion mining framework using ChatGPT to mass-annotate voting intentions and motivations that represent the stance and frames prior to the election. We report that ChatGPT can predict the preferred candidate with 97\% accuracy and identify the correct voting motivation out of 13 possible choices with 71\% accuracy based on the data collected from 325 interviews. We conclude by discussing the robustness of our approach, accounting for factors such as captions quality, interview length, and channels. This new method will offer a less noisy and cost-effective alternative for opinion mining using social media data.
Supervised Contrastive Learning with Heterogeneous Similarity for Distribution Shifts
Venue: arXiv cs.LG 2023
Year: 2023

Distribution shifts are problems where the distribution of data changes between training and testing, which can significantly degrade the performance of a model deployed in the real world. Recent studies suggest that one reason for the degradation is a type of overfitting, and that proper regularization can mitigate the degradation, especially when using highly representative models such as neural networks. In this paper, we propose a new regularization using the supervised contrastive learning to prevent such overfitting and to train models that do not degrade their performance under the distribution shifts. We extend the cosine similarity in contrastive loss to a more general similarity measure and propose to use different parameters in the measure when comparing a sample to a positive or negative example, which is analytically shown to act as a kind of margin in contrastive loss. Experiments on benchmark datasets that emulate distribution shifts, including subpopulation shift and domain generalization, demonstrate the advantage of the proposed method over existing regularization methods.
Rethinking Evaluation Protocols of Visual Representations Learned via Self-supervised Learning
Venue: arXiv cs.CV 2023
Year: 2023

Linear probing (LP) (and $k$-NN) on the upstream dataset with labels (e.g., ImageNet) and transfer learning (TL) to various downstream datasets are commonly employed to evaluate the quality of visual representations learned via self-supervised learning (SSL). Although existing SSL methods have shown good performances under those evaluation protocols, we observe that the performances are very sensitive to the hyperparameters involved in LP and TL. We argue that this is an undesirable behavior since truly generic representations should be easily adapted to any other visual recognition task, i.e., the learned representations should be robust to the settings of LP and TL hyperparameters. In this work, we try to figure out the cause of performance sensitivity by conducting extensive experiments with state-of-the-art SSL methods. First, we find that input normalization for LP is crucial to eliminate performance variations according to the hyperparameters. Specifically, batch normalization before feeding inputs to a linear classifier considerably improves the stability of evaluation, and also resolves inconsistency of $k$-NN and LP metrics. Second, for TL, we demonstrate that a weight decay parameter in SSL significantly affects the transferability of learned representations, which cannot be identified by LP or $k$-NN evaluations on the upstream dataset. We believe that the findings of this study will be beneficial for the community by drawing attention to the shortcomings in the current SSL evaluation schemes and underscoring the need to reconsider them.