OpenRaiser/Intern-Atlas huggingface dataset:
InceptionXML: A Lightweight Framework with Synchronized Negative Sampling for Short Text Extreme Classification
Venue: arXiv cs.CL 2024
Year: 2024

Automatic annotation of short-text data to a large number of target labels, referred to as Short Text Extreme Classification, has found numerous applications including prediction of related searches and product recommendation. In this paper, we propose a convolutional architecture InceptionXML which is light-weight, yet powerful, and robust to the inherent lack of word-order in short-text queries encountered in search and recommendation. We demonstrate the efficacy of applying convolutions by recasting the operation along the embedding dimension instead of the word dimension as applied in conventional CNNs for text classification. Towards scaling our model to datasets with millions of labels, we also propose SyncXML pipeline which improves upon the shortcomings of the recently proposed dynamic hard-negative mining technique for label short-listing by synchronizing the label-shortlister and extreme classifier. SyncXML not only reduces the inference time to half but is also an order of magnitude smaller than state-of-the-art Astec in terms of model size. Through a comprehensive empirical comparison, we show that not only can InceptionXML outperform existing approaches on benchmark datasets but also the transformer baselines requiring only 2% FLOPs. The code for InceptionXML is available at https://github.com/xmc-aalto/inceptionxml.
FUTURE-AI: Guiding Principles and Consensus Recommendations for Trustworthy Artificial Intelligence in Medical Imaging
Venue: arXiv cs.CV 2024
Year: 2024

The recent advancements in artificial intelligence (AI) combined with the extensive amount of data generated by today's clinical systems, has led to the development of imaging AI solutions across the whole value chain of medical imaging, including image reconstruction, medical image segmentation, image-based diagnosis and treatment planning. Notwithstanding the successes and future potential of AI in medical imaging, many stakeholders are concerned of the potential risks and ethical implications of imaging AI solutions, which are perceived as complex, opaque, and difficult to comprehend, utilise, and trust in critical clinical applications. Addressing these concerns and risks, the FUTURE-AI framework has been proposed, which, sourced from a global multi-domain expert consensus, comprises guiding principles for increased trust, safety, and adoption for AI in healthcare. In this paper, we transform the general FUTURE-AI healthcare principles to a concise and specific AI implementation guide tailored to the needs of the medical imaging community. To this end, we carefully assess each building block of the FUTURE-AI framework consisting of (i) Fairness, (ii) Universality, (iii) Traceability, (iv) Usability, (v) Robustness and (vi) Explainability, and respectively define concrete best practices based on accumulated AI implementation experiences from five large European projects on AI in Health Imaging. We accompany our concrete step-by-step medical imaging development guide with a practical AI solution maturity checklist, thus enabling AI development teams to design, evaluate, maintain, and deploy technically, clinically and ethically trustworthy imaging AI solutions into clinical practice.
End-to-End Dense Video Grounding via Parallel Regression
Venue: arXiv cs.CV 2024
Year: 2024

Video grounding aims to localize the corresponding video moment in an untrimmed video given a language query. Existing methods often address this task in an indirect way, by casting it as a proposal-and-match or fusion-and-detection problem. Solving these surrogate problems often requires sophisticated label assignment during training and hand-crafted removal of near-duplicate results. Meanwhile, existing works typically focus on sparse video grounding with a single sentence as input, which could result in ambiguous localization due to its unclear description. In this paper, we tackle a new problem of dense video grounding, by simultaneously localizing multiple moments with a paragraph as input. From a perspective on video grounding as language conditioned regression, we present an end-to-end parallel decoding paradigm by re-purposing a Transformer-alike architecture (PRVG). The key design in our PRVG is to use languages as queries, and directly regress the moment boundaries based on language-modulated visual representations. Thanks to its simplicity in design, our PRVG framework can be applied in different testing schemes (sparse or dense grounding) and allows for efficient inference without any post-processing technique. In addition, we devise a robust proposal-level attention loss to guide the training of PRVG, which is invariant to moment duration and contributes to model convergence. We perform experiments on two video grounding benchmarks of ActivityNet Captions and TACoS, demonstrating that our PRVG can significantly outperform previous methods. We also perform in-depth studies to investigate the effectiveness of parallel regression paradigm on video grounding.
DemiNet: Dependency-Aware Multi-Interest Network with Self-Supervised Graph Learning for Click-Through Rate Prediction
Venue: arXiv cs.IR 2024
Year: 2024

In this paper, we propose a novel model named DemiNet (short for DEpendency-Aware Multi-Interest Network) to address the above two issues. To be specific, we first consider various dependency types between item nodes and perform dependency-aware heterogeneous attention for denoising and obtaining accurate sequence item representations. Secondly, for multiple interests extraction, multi-head attention is conducted on top of the graph embedding. To filter out noisy inter-item correlations and enhance the robustness of extracted interests, self-supervised interest learning is introduced to the above two steps. Thirdly, to aggregate the multiple interests, interest experts corresponding to different interest routes give rating scores respectively, while a specialized network assigns the confidence of each score. Experimental results on three real-world datasets demonstrate that the proposed DemiNet significantly improves the overall recommendation performance over several state-of-the-art baselines. Further studies verify the efficacy and interpretability benefits brought by the fine-grained user interest modeling.
Algorithms for matrix multiplication via sampling and opportunistic matrix multiplication
Venue: arXiv cs.DS 2024
Year: 2024

Karppa & Kaski (2019) proposed a novel ``broken" or ``opportunistic" matrix multiplication algorithm, based on a variant of Strassen's algorithm, and used this to develop new algorithms for Boolean matrix multiplication, among other tasks. Their algorithm can compute Boolean matrix multiplication in $O(n^{2.778})$ time. While asymptotically faster matrix multiplication algorithms exist, most such algorithms are infeasible for practical problems. We describe an alternative way to use the broken multiplication algorithm to approximately compute matrix multiplication, either for real-valued or Boolean matrices. In brief, instead of running multiple iterations of the broken algorithm on the original input matrix, we form a new larger matrix by sampling and run a single iteration of the broken algorithm on it. Asymptotically, our algorithm has runtime $O(n^{2.763})$, a slight improvement over the Karppa-Kaski algorithm. Since the goal is to obtain new practical matrix-multiplication algorithms, we also estimate the concrete runtime for our algorithm for some large-scale sample problems. It appears that for these parameters, further optimizations are still needed to make our algorithm competitive.
Improvements for mlrose applied to the Traveling Salesperson Problem
Venue: arXiv cs.NE 2024
Year: 2024

In this paper we discuss the application of Artificial Intelligence (AI) to the exemplary industrial use case of the two-dimensional commissioning problem in a high-bay storage, which essentially can be phrased as an instance of Traveling Salesperson Problem (TSP). We investigate the mlrose library that provides an TSP optimizer based on various heuristic optimization techniques. Our focus is on two methods, namely Genetic Algorithm (GA) and Hill Climbing (HC), which are provided by mlrose. We present improvements for both methods that yield shorter tour lengths, by moderately exploiting the problem structure of TSP. That is, the proposed improvements have a generic character and are not limited to TSP only.
Transferability Estimation for Semantic Segmentation Task
Venue: arXiv cs.CV 2024
Year: 2024

Transferability estimation is a fundamental problem in transfer learning to predict how good the performance is when transferring a source model (or source task) to a target task. With the guidance of transferability score, we can efficiently select the highly transferable source models without performing the real transfer in practice. Recent analytical transferability metrics are mainly designed for image classification problem, and currently there is no specific investigation for the transferability estimation of semantic segmentation task, which is an essential problem in autonomous driving, medical image analysis, etc. Consequently, we further extend the recent analytical transferability metric OTCE (Optimal Transport based Conditional Entropy) score to the semantic segmentation task. The challenge in applying the OTCE score is the high dimensional segmentation output, which is difficult to find the optimal coupling between so many pixels under an acceptable computation cost. Thus we propose to randomly sample N pixels for computing OTCE score and take the expectation over K repetitions as the final transferability score. Experimental evaluation on Cityscapes, BDD100K and GTA5 datasets demonstrates that the OTCE score highly correlates with the transfer performance.
Adwords with Unknown Budgets and Beyond
Venue: arXiv cs.DS 2024
Year: 2024

In the classic Adwords problem introduced by Mehta et al.\ (2007), we have a bipartite graph between advertisers and queries. Each advertiser has a maximum budget that is known a priori. Queries are unknown a priori and arrive sequentially. When a query arrives, advertisers make bids and we (immediately and irrevocably) decide which (if any) Ad to display based on the bids and advertiser budgets. The winning advertiser for each query pays their bid up to their remaining budget. Our goal is to maximize total budget utilized without any foreknowledge of the arrival sequence (which could be adversarial). We consider the setting where the online algorithm does not know the advertisers' budgets a priori and the budget of an advertiser is revealed to the algorithm only when it is exceeded. A naïve greedy algorithm is 0.5 competitive for this setting and finding an algorithm with better performance remained an open problem. We show that no deterministic algorithm has competitive ratio better than 0.5 and give the first (randomized) algorithm with strictly better performance guarantee. We show that the competitive ratio of our algorithm is at least 0.522 but also strictly less than $(1-1/e)$. We present novel applications of budget oblivious algorithms in search ads and beyond. In particular, we show that our algorithm achieves the best possible performance guarantee for deterministic online matching in the presence of multi-channel traffic (Manshadi et al. (2022)).
Contextual Tuning of Model Predictive Control for Autonomous Racing
Venue: arXiv cs.RO 2024
Year: 2024

Learning-based model predictive control has been widely applied in autonomous racing to improve the closed-loop behaviour of vehicles in a data-driven manner. When environmental conditions change, e.g., due to rain, often only the predictive model is adapted, but the controller parameters are kept constant. However, this can lead to suboptimal behaviour. In this paper, we address the problem of data-efficient controller tuning, adapting both the model and objective simultaneously. The key novelty of the proposed approach is that we leverage a learned dynamics model to encode the environmental condition as a so-called context. This insight allows us to employ contextual Bayesian optimization to efficiently transfer knowledge across different environmental conditions. Consequently, we require fewer data to find the optimal controller configuration for each context. The proposed framework is extensively evaluated with more than 3'000 laps driven on an experimental platform with 1:28 scale RC race cars. The results show that our approach successfully optimizes the lap time across different contexts requiring fewer data compared to other approaches based on standard Bayesian optimization.
EvadeDroid: A Practical Evasion Attack on Machine Learning for Black-box Android Malware Detection
Venue: arXiv cs.LG 2024
Year: 2024

Over the last decade, researchers have extensively explored the vulnerabilities of Android malware detectors to adversarial examples through the development of evasion attacks; however, the practicality of these attacks in real-world scenarios remains arguable. The majority of studies have assumed attackers know the details of the target classifiers used for malware detection, while in reality, malicious actors have limited access to the target classifiers. This paper introduces EvadeDroid, a problem-space adversarial attack designed to effectively evade black-box Android malware detectors in real-world scenarios. EvadeDroid constructs a collection of problem-space transformations derived from benign donors that share opcode-level similarity with malware apps by leveraging an n-gram-based approach. These transformations are then used to morph malware instances into benign ones via an iterative and incremental manipulation strategy. The proposed manipulation technique is a query-efficient optimization algorithm that can find and inject optimal sequences of transformations into malware apps. Our empirical evaluations, carried out on 1K malware apps, demonstrate the effectiveness of our approach in generating real-world adversarial examples in both soft- and hard-label settings. Our findings reveal that EvadeDroid can effectively deceive diverse malware detectors that utilize different features with various feature types. Specifically, EvadeDroid achieves evasion rates of 80%-95% against DREBIN, Sec-SVM, ADE-MA, MaMaDroid, and Opcode-SVM with only 1-9 queries. Furthermore, we show that the proposed problem-space adversarial attack is able to preserve its stealthiness against five popular commercial antiviruses with an average of 79% evasion rate, thus demonstrating its feasibility in the real world.
Meta-Learning 3D Shape Segmentation Functions
Venue: arXiv cs.CV 2024
Year: 2024

Learning robust 3D shape segmentation functions with deep neural networks has emerged as a powerful paradigm, offering promising performance in producing a consistent part segmentation of each 3D shape. Generalizing across 3D shape segmentation functions requires robust learning of priors over the respective function space and enables consistent part segmentation of shapes in presence of significant 3D structure variations. Existing generalization methods rely on extensive training of 3D shape segmentation functions on large-scale labeled datasets. In this paper, we proposed to formalize the learning of a 3D shape segmentation function space as a meta-learning problem, aiming to predict a 3D segmentation model that can be quickly adapted to new shapes with no or limited training data. More specifically, we define each task as unsupervised learning of shape-conditioned 3D segmentation function which takes as input points in 3D space and predicts the part-segment labels. The 3D segmentation function is trained by a self-supervised 3D shape reconstruction loss without the need for part labels. Also, we introduce an auxiliary deep neural network as a meta-learner which takes as input a 3D shape and predicts the prior over the respective 3D segmentation function space. We show in experiments that our meta-learning approach, denoted as Meta-3DSeg, leads to improvements on unsupervised 3D shape segmentation over the conventional designs of deep neural networks for 3D shape segmentation functions.
Isogeny-based Group Signatures and Accountable Ring Signatures in QROM
Venue: arXiv cs.CR 2024
Year: 2024

We present the first provably secure isogeny-based group signature (GS) and accountable ring signature (ARS) in the quantum random oracle model (QROM). We do so via introducing and constructing an intermediate primitive called the openable sigma protocol and demonstrating that any such protocol gives rise to a secure GS and ARS. Furthermore, QROM security is guaranteed if an additional perfect unique-response property (which is achieved via our tailored construction) is satisfied. Previous works by Beullens et al. (Eurocrypt 2022, Asiacrypt 2020) proposed isogeny-based GS and ARS with better efficiency but were only analyzed in the classical random oracle model (CROM). It is well-known that CROM security does not generally translate to QROM security; with the growing relevance of isogeny-based constructions in post-quantum cryptography, the current state of the art is unsatisfactory. Moreover, the aforementioned existing isogeny-based signatures were recently affected by the Fiat-Shamir with aborts (FSwA) flaw discovered by Barbosa et al. and Devevey et al. (CRYPTO 2023), leaving the provable security of isogeny-based signatures open to question once again. Our constructions are not only immune to the FSwA flaw but also provide stronger QROM security. As current QROM-secure ARS and GS schemes are mostly lattice-based, we offer a robust post-quantum alternative should lattice assumptions weaken.
A Review of the Deep Sea Treasure problem as a Multi-Objective Reinforcement Learning Benchmark
Venue: arXiv cs.LG 2024
Year: 2024

In this paper, the authors investigate the Deep Sea Treasure (DST) problem as proposed by Vamplew et al. Through a number of proofs, the authors show the original DST problem to be quite basic, and not always representative of practical Multi-Objective Optimization problems. In an attempt to bring theory closer to practice, the authors propose an alternative, improved version of the DST problem, and prove that some of the properties that simplify the original DST problem no longer hold. The authors also provide a reference implementation and perform a comparison between their implementation, and other existing open-source implementations of the problem. Finally, the authors also provide a complete Pareto-front for their new DST problem.
DPGNN: Dual-Perception Graph Neural Network for Representation Learning
Venue: arXiv cs.LG 2024
Year: 2024

Graph neural networks (GNNs) have drawn increasing attention in recent years and achieved remarkable performance in many graph-based tasks, especially in semi-supervised learning on graphs. However, most existing GNNs are based on the message-passing paradigm to iteratively aggregate neighborhood information in a single topology space. Despite their success, the expressive power of GNNs is limited by some drawbacks, such as inflexibility of message source expansion, negligence of node-level message output discrepancy, and restriction of single message space. To address these drawbacks, we present a novel message-passing paradigm, based on the properties of multi-step message source, node-specific message output, and multi-space message interaction. To verify its validity, we instantiate the new message-passing paradigm as a Dual-Perception Graph Neural Network (DPGNN), which applies a node-to-step attention mechanism to aggregate node-specific multi-step neighborhood information adaptively. Our proposed DPGNN can capture the structural neighborhood information and the feature-related information simultaneously for graph representation learning. Experimental results on six benchmark datasets with different topological structures demonstrate that our method outperforms the latest state-of-the-art models, which proves the superiority and versatility of our method. To our knowledge, we are the first to consider node-specific message passing in the GNNs.
Improving overlay maps of science: combining overview and detail
Venue: arXiv cs.DL 2024
Year: 2024

Overlay maps of science are global base maps over which subsets of publications can be projected. Such maps can be used to monitor, explore, and study research through its publication output. Most maps of science, including overlay maps, are flat in the sense that they visualize research fields at one single level. Such maps generally fail to provide both overview and detail about the research being analyzed. The aim of this study is to improve overlay maps of science to provide both features in a single visualization. I created a map based on a hierarchical classification of publications, including broad disciplines for overview and more granular levels to incorporate detailed information. The classification was obtained by clustering articles in a citation network of about 17 million publication records in PubMed from 1995 onwards. The map emphasizes the hierarchical structure of the classification by visualizing both disciplines and the underlying specialties. To show how the visualization methodology can help getting both overview of research and detailed information about its topical structure, I projected two overlay maps onto the base map: (1) open access publishing and (2) coronavirus/Covid-19 research.
Understanding Multimodal Procedural Knowledge by Sequencing Multimodal Instructional Manuals
Venue: arXiv cs.CL 2024
Year: 2024

The ability to sequence unordered events is an essential skill to comprehend and reason about real world task procedures, which often requires thorough understanding of temporal common sense and multimodal information, as these procedures are often communicated through a combination of texts and images. Such capability is essential for applications such as sequential task planning and multi-source instruction summarization. While humans are capable of reasoning about and sequencing unordered multimodal procedural instructions, whether current machine learning models have such essential capability is still an open question. In this work, we benchmark models' capability of reasoning over and sequencing unordered multimodal instructions by curating datasets from popular online instructional manuals and collecting comprehensive human annotations. We find models not only perform significantly worse than humans but also seem incapable of efficiently utilizing the multimodal information. To improve machines' performance on multimodal event sequencing, we propose sequentiality-aware pretraining techniques that exploit the sequential alignment properties of both texts and images, resulting in > 5% significant improvements.
Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs
Venue: arXiv cs.LG 2024
Year: 2024

We study episodic reinforcement learning (RL) in non-stationary linear kernel Markov decision processes (MDPs). In this setting, both the reward function and the transition kernel are linear with respect to the given feature maps and are allowed to vary over time, as long as their respective parameter variations do not exceed certain variation budgets. We propose the \underline{p}eriodically \underline{r}estarted \underline{o}ptimistic \underline{p}olicy \underline{o}ptimization algorithm (PROPO), which is an optimistic policy optimization algorithm with linear function approximation. PROPO features two mechanisms: sliding-window-based policy evaluation and periodic-restart-based policy improvement, which are tailored for policy optimization in a non-stationary environment. In addition, only utilizing the technique of sliding window, we propose a value-iteration algorithm. We establish dynamic upper bounds for the proposed methods and a minimax lower bound which shows the (near-) optimality of the proposed methods. To our best knowledge, PROPO is the first provably efficient policy optimization algorithm that handles non-stationarity.