OpenRaiser/Intern-Atlas huggingface dataset:
Parameterized Matroid-Constrained Maximum Coverage
Venue: arXiv cs.DS 2023
Year: 2023

In this paper, we introduce the concept of Density-Balanced Subset in a matroid, in which independent sets can be sampled so as to guarantee that (i) each element has the same probability to be sampled, and (ii) those events are negatively correlated. These Density-Balanced Subsets are subsets in the ground set of a matroid in which the traditional notion of uniform random sampling can be extended. We then provide an application of this concept to the Matroid-Constrained Maximum Coverage problem. In this problem, given a matroid $\mathcal{M} = (V, \mathcal{I})$ of rank $k$ on a ground set $V$ and a coverage function $f$ on $V$, the goal is to find an independent set $S \in \mathcal{I}$ maximizing $f(S)$. This problem is an important special case of the much-studied submodular function maximization problem subject to a matroid constraint; this is also a generalization of the maximum $k$-cover problem in a graph. In this paper, assuming that the coverage function has a bounded frequency $μ$ (i.e., any element of the underlying universe of the coverage function appears in at most $μ$ sets), we design a procedure, parameterized by some integer $ρ$, to extract in polynomial time an approximate kernel of size $ρ\cdot k$ that is guaranteed to contain a $1 - (μ- 1)/ρ$ approximation of the optimal solution. This procedure can then be used to get a Fixed-Parameter Tractable Approximation Scheme (FPT-AS) providing a $1 - \varepsilon$ approximation in time $(μ/\varepsilon)^{O(k)} \cdot |V|^{O(1)}$. This generalizes and improves the results of [Manurangsi, 2019] and [Huang and Sellier, 2022], providing the first FPT-AS working on an arbitrary matroid. Moreover, because of its simplicity, the kernel construction can be performed in the streaming setting.
Proving properties of some greedily-defined integer recurrences via automata theory
Venue: arXiv cs.DM 2023
Year: 2023

Venkatachala on the one hand, and Avdispahić & Zejnulahi on the other, both studiied integer sequences with an unusual sum property defined in a greedy way, and proved many results about them. However, their proofs were rather lengthy and required numerous cases. In this paper, I provide a different approach, via finite automata, that can prove the same results (and more) in a simple, unified way. Instead of case analysis, we use a decision procedure implemented in the free software Walnut. Using these ideas, we can prove a conjecture of Quet and find connections between Quet's sequence and the "married" functions of Hofstadter.
Digital elevation model correction in urban areas using extreme gradient boosting, land cover and terrain parameters
Venue: arXiv cs.LG 2023
Year: 2023

The accuracy of digital elevation models (DEMs) in urban areas is influenced by numerous factors including land cover and terrain irregularities. Moreover, building artifacts in global DEMs cause artificial blocking of surface flow pathways. This compromises their quality and adequacy for hydrological and environmental modelling in urban landscapes where precise and accurate terrain information is needed. In this study, the extreme gradient boosting (XGBoost) ensemble algorithm is adopted for enhancing the accuracy of two medium-resolution 30m DEMs over Cape Town, South Africa: Copernicus GLO-30 and ALOS World 3D (AW3D). XGBoost is a scalable, portable and versatile gradient boosting library that can solve many environmental modelling problems. The training datasets are comprised of eleven predictor variables including elevation, urban footprints, slope, aspect, surface roughness, topographic position index, terrain ruggedness index, terrain surface texture, vector roughness measure, forest cover and bare ground cover. The target variable (elevation error) was calculated with respect to highly accurate airborne LiDAR. After training and testing, the model was applied for correcting the DEMs at two implementation sites. The correction achieved significant accuracy gains which are competitive with other proposed methods. The root mean square error (RMSE) of Copernicus DEM improved by 46 to 53% while the RMSE of AW3D DEM improved by 72 to 73%. These results showcase the potential of gradient boosted trees for enhancing the quality of DEMs, and for improved hydrological modelling in urban catchments.
Human Behavior-based Personalized Meal Recommendation and Menu Planning Social System
Venue: arXiv cs.HC 2023
Year: 2023

The traditional dietary recommendation systems are basically nutrition or health-aware where the human feelings on food are ignored. Human affects vary when it comes to food cravings, and not all foods are appealing in all moods. A questionnaire-based and preference-aware meal recommendation system can be a solution. However, automated recognition of social affects on different foods and planning the menu considering nutritional demand and social-affect has some significant benefits of the questionnaire-based and preference-aware meal recommendations. A patient with severe illness, a person in a coma, or patients with locked-in syndrome and amyotrophic lateral sclerosis (ALS) cannot express their meal preferences. Therefore, the proposed framework includes a social-affective computing module to recognize the affects of different meals where the person's affect is detected using electroencephalography signals. EEG allows to capture the brain signals and analyze them to anticipate affective toward a food. In this study, we have used a 14-channel wireless Emotive Epoc+ to measure affectivity for different food items. A hierarchical ensemble method is applied to predict affectivity upon multiple feature extraction methods and TOPSIS (Technique for Order of Preference by Similarity to Ideal Solution) is used to generate a food list based on the predicted affectivity. In addition to the meal recommendation, an automated menu planning approach is also proposed considering a person's energy intake requirement, affectivity, and nutritional values of the different menus. The bin-packing algorithm is used for the personalized menu planning of breakfast, lunch, dinner, and snacks. The experimental findings reveal that the suggested affective computing, meal recommendation, and menu planning algorithms perform well across a variety of assessment parameters.
Decentralised Service Allocation using Blockchain
Venue: arXiv cs.DC 2023
Year: 2023

The growing demand for short-term property renting has led to the boom of a new category called PropTech (Property + Technology). Such a rise in demand attracted many entrepreneurs and investors leading to the inception of powerful and centralised players in the category (like Airbnb). Unfortunately, some big players are controlling the entire industry in a centralised way in turn, performing anti-competitive practices which leave no room for the small players. Such an ecosystem can be made more transparent and decentralised by executing transactions and order-fulfilment on a blockchain. To extend the functionality of the system, we can also perform the renting of small services and appliances via the integration of IoT. Implementing such a system will make the process more transparent, robust and decentralised.
Contrastive Learning for Cross-modal Artist Retrieval
Venue: arXiv cs.IR 2023
Year: 2023

Music retrieval and recommendation applications often rely on content features encoded as embeddings, which provide vector representations of items in a music dataset. Numerous complementary embeddings can be derived from processing items originally represented in several modalities, e.g., audio signals, user interaction data, or editorial data. However, data of any given modality might not be available for all items in any music dataset. In this work, we propose a method based on contrastive learning to combine embeddings from multiple modalities and explore the impact of the presence or absence of embeddings from diverse modalities in an artist similarity task. Experiments on two datasets suggest that our contrastive method outperforms single-modality embeddings and baseline algorithms for combining modalities, both in terms of artist retrieval accuracy and coverage. Improvements with respect to other methods are particularly significant for less popular query artists. We demonstrate our method successfully combines complementary information from diverse modalities, and is more robust to missing modality data (i.e., it better handles the retrieval of artists with different modality embeddings than the query artist's).
"Zero Cost'' Majority Attacks on Permissionless Blockchains
Venue: arXiv cs.CR 2023
Year: 2023

The core premise of permissionless blockchains is their reliable and secure operation without the need to trust any individual agent. At the heart of blockchain consensus mechanisms is an explicit cost (whether work or stake) for participation in the network and the opportunity to add blocks to the blockchain. A key rationale for that cost is to make attacks on the network, which could be theoretically carried out if a majority of nodes were controlled by a single entity, too expensive to be worthwhile. We demonstrate that a majority attacker can successfully attack with a {\em negative cost}, which shows that the protocol mechanisms are insufficient to create a secure network, and emphasizes the importance of socially driven mechanisms external to the protocol. At the same time, negative cost enables a new type of majority attack that is more likely to elude external scrutiny.
On the Interplay of Convolutional Padding and Adversarial Robustness
Venue: arXiv cs.CV 2023
Year: 2023

It is common practice to apply padding prior to convolution operations to preserve the resolution of feature-maps in Convolutional Neural Networks (CNN). While many alternatives exist, this is often achieved by adding a border of zeros around the inputs. In this work, we show that adversarial attacks often result in perturbation anomalies at the image boundaries, which are the areas where padding is used. Consequently, we aim to provide an analysis of the interplay between padding and adversarial attacks and seek an answer to the question of how different padding modes (or their absence) affect adversarial robustness in various scenarios.
PQC-HA: A Framework for Prototyping and In-Hardware Evaluation of Post-Quantum Cryptography Hardware Accelerators
Venue: arXiv cs.CR 2023
Year: 2023

In the third round of the NIST Post-Quantum Cryptography standardization project, the focus is on optimizing software and hardware implementations of candidate schemes. The winning schemes are CRYSTALS Kyber and CRYSTALS Dilithium, which serve as a Key Encapsulation Mechanism (KEM) and Digital Signature Algorithm (DSA), respectively. This study utilizes the TaPaSCo open-source framework to create hardware building blocks for both schemes using High-level Synthesis (HLS) from minimally modified ANSI C software reference implementations across all security levels. Additionally, a generic TaPaSCo host runtime application is developed in Rust to verify their functionality through the standard NIST interface, utilizing the corresponding Known Answer Test mechanism on actual hardware. Building on this foundation, the communication overhead for TaPaSCo hardware accelerators on PCIe-connected FPGA devices is evaluated and compared with previous work and optimized AVX2 software reference implementations. The results demonstrate the feasibility of verifying and evaluating the performance of Post-Quantum Cryptography accelerators on real hardware using TaPaSCo. Furthermore, the off-chip accelerator communication overhead of the NIST standard interface is measured, which, on its own, outweighs the execution wall clock time of the optimized software reference implementation of Kyber at Security Level 1.
Energy-Efficient Deadline-Aware Edge Computing: Bandit Learning with Partial Observations in Multi-Channel Systems
Venue: arXiv cs.NI 2023
Year: 2023

In this paper, we consider a task offloading problem in a multi-access edge computing (MEC) network, in which edge users can either use their local processing unit to compute their tasks or offload their tasks to a nearby edge server through multiple communication channels each with different characteristics. The main objective is to maximize the energy efficiency of the edge users while meeting computing tasks deadlines. In the multi-user multi-channel offloading scenario, users are distributed with partial observations of the system states. We formulate this problem as a stochastic optimization problem and leverage \emph{contextual neural multi-armed bandit} models to develop an energy-efficient deadline-aware solution, dubbed E2DA. The proposed E2DA framework only relies on partial state information (i.e., computation task features) to make offloading decisions. Through extensive numerical analysis, we demonstrate that the E2DA algorithm can efficiently learn an offloading policy and achieve close-to-optimal performance in comparison with several baseline policies that optimize energy consumption and/or response time. Furthermore, we provide a comprehensive set of results on the MEC system performance for various applications such as augmented reality (AR) and virtual reality (VR).
Video Captioning with Aggregated Features Based on Dual Graphs and Gated Fusion
Venue: arXiv cs.CV 2023
Year: 2023

The application of video captioning models aims at translating the content of videos by using accurate natural language. Due to the complex nature inbetween object interaction in the video, the comprehensive understanding of spatio-temporal relations of objects remains a challenging task. Existing methods often fail in generating sufficient feature representations of video content. In this paper, we propose a video captioning model based on dual graphs and gated fusion: we adapt two types of graphs to generate feature representations of video content and utilize gated fusion to further understand these different levels of information. Using a dual-graphs model to generate appearance features and motion features respectively can utilize the content correlation in frames to generate various features from multiple perspectives. Among them, dual-graphs reasoning can enhance the content correlation in frame sequences to generate advanced semantic features; The gated fusion, on the other hand, aggregates the information in multiple feature representations for comprehensive video content understanding. The experiments conducted on worldly used datasets MSVD and MSR-VTT demonstrate state-of-the-art performance of our proposed approach.
MACO: A Modality Adversarial and Contrastive Framework for Modality-missing Multi-modal Knowledge Graph Completion
Venue: arXiv cs.CL 2023
Year: 2023

Recent years have seen significant advancements in multi-modal knowledge graph completion (MMKGC). MMKGC enhances knowledge graph completion (KGC) by integrating multi-modal entity information, thereby facilitating the discovery of unobserved triples in the large-scale knowledge graphs (KGs). Nevertheless, existing methods emphasize the design of elegant KGC models to facilitate modality interaction, neglecting the real-life problem of missing modalities in KGs. The missing modality information impedes modal interaction, consequently undermining the model's performance. In this paper, we propose a modality adversarial and contrastive framework (MACO) to solve the modality-missing problem in MMKGC. MACO trains a generator and discriminator adversarially to generate missing modality features that can be incorporated into the MMKGC model. Meanwhile, we design a cross-modal contrastive loss to improve the performance of the generator. Experiments on public benchmarks with further explorations demonstrate that MACO could achieve state-of-the-art results and serve as a versatile framework to bolster various MMKGC models. Our code and benchmark data are available at https://github.com/zjukg/MACO.
Understanding the robustness difference between stochastic gradient descent and adaptive gradient methods
Venue: arXiv cs.LG 2023
Year: 2023

Stochastic gradient descent (SGD) and adaptive gradient methods, such as Adam and RMSProp, have been widely used in training deep neural networks. We empirically show that while the difference between the standard generalization performance of models trained using these methods is small, those trained using SGD exhibit far greater robustness under input perturbations. Notably, our investigation demonstrates the presence of irrelevant frequencies in natural datasets, where alterations do not affect models' generalization performance. However, models trained with adaptive methods show sensitivity to these changes, suggesting that their use of irrelevant frequencies can lead to solutions sensitive to perturbations. To better understand this difference, we study the learning dynamics of gradient descent (GD) and sign gradient descent (signGD) on a synthetic dataset that mirrors natural signals. With a three-dimensional input space, the models optimized with GD and signGD have standard risks close to zero but vary in their adversarial risks. Our result shows that linear models' robustness to $\ell_2$-norm bounded changes is inversely proportional to the model parameters' weight norm: a smaller weight norm implies better robustness. In the context of deep learning, our experiments show that SGD-trained neural networks have smaller Lipschitz constants, explaining the better robustness to input perturbations than those trained with adaptive gradient methods.
Estimating and Incentivizing Imperfect-Knowledge Agents with Hidden Rewards
Venue: arXiv cs.LG 2023
Year: 2023

In practice, incentive providers (i.e., principals) often cannot observe the reward realizations of incentivized agents, which is in contrast to many principal-agent models that have been previously studied. This information asymmetry challenges the principal to consistently estimate the agent's unknown rewards by solely watching the agent's decisions, which becomes even more challenging when the agent has to learn its own rewards. This complex setting is observed in various real-life scenarios ranging from renewable energy storage contracts to personalized healthcare incentives. Hence, it offers not only interesting theoretical questions but also wide practical relevance. This paper explores a repeated adverse selection game between a self-interested learning agent and a learning principal. The agent tackles a multi-armed bandit (MAB) problem to maximize their expected reward plus incentive. On top of the agent's learning, the principal trains a parallel algorithm and faces a trade-off between consistently estimating the agent's unknown rewards and maximizing their own utility by offering adaptive incentives to lead the agent. For a non-parametric model, we introduce an estimator whose only input is the history of principal's incentives and agent's choices. We unite this estimator with a proposed data-driven incentive policy within a MAB framework. Without restricting the type of the agent's algorithm, we prove finite-sample consistency of the estimator and a rigorous regret bound for the principal by considering the sequential externality imposed by the agent. Lastly, our theoretical results are reinforced by simulations justifying applicability of our framework to green energy aggregator contracts.
IP-Adapter: Text Compatible Image Prompt Adapter for Text-to-Image Diffusion Models
Venue: arXiv cs.CV 2023
Year: 2023

Recent years have witnessed the strong power of large text-to-image diffusion models for the impressive generative capability to create high-fidelity images. However, it is very tricky to generate desired images using only text prompt as it often involves complex prompt engineering. An alternative to text prompt is image prompt, as the saying goes: "an image is worth a thousand words". Although existing methods of direct fine-tuning from pretrained models are effective, they require large computing resources and are not compatible with other base models, text prompt, and structural controls. In this paper, we present IP-Adapter, an effective and lightweight adapter to achieve image prompt capability for the pretrained text-to-image diffusion models. The key design of our IP-Adapter is decoupled cross-attention mechanism that separates cross-attention layers for text features and image features. Despite the simplicity of our method, an IP-Adapter with only 22M parameters can achieve comparable or even better performance to a fully fine-tuned image prompt model. As we freeze the pretrained diffusion model, the proposed IP-Adapter can be generalized not only to other custom models fine-tuned from the same base model, but also to controllable generation using existing controllable tools. With the benefit of the decoupled cross-attention strategy, the image prompt can also work well with the text prompt to achieve multimodal image generation. The project page is available at \url{https://ip-adapter.github.io}.
UD-MAC: Delay Tolerant Multiple Access Control Protocol for Unmanned Aerial Vehicle Networks
Venue: arXiv cs.NI 2023
Year: 2023

In unmanned aerial vehicle (UAV) networks, high-capacity data transmission is of utmost importance for applications such as intelligent transportation, smart cities, and forest monitoring, which rely on the mobility of UAVs to collect and transmit large amount of data, including video and image data. Due to the short flight time of UAVs, the network capacity will be reduced when they return to the ground unit for charging. Hence, we suggest that UAVs can apply a store-carry-and-forward (SCF) transmission mode to carry packets on their way back to the ground unit for improving network throughput. In this paper, we propose a novel protocol, named UAV delay-tolerant multiple access control (UD-MAC), which can support different transmission modes in UAV networks. We set a higher priority for SCF transmission and analyze the probability of being in SCF mode to derive network throughput. The simulation results show that the network throughput of UD-MAC is improved by 57% to 83% compared to VeMAC.
Model Predictive Contouring Control for Vehicle Obstacle Avoidance at the Limit of Handling
Venue: arXiv cs.RO 2023
Year: 2023

This paper proposes a non-linear Model Predictive Contouring Control (MPCC) for obstacle avoidance in automated vehicles driven at the limit of handling. The proposed controller integrates motion planning, path tracking and vehicle stability objectives, prioritising obstacle avoidance in emergencies. The controller's prediction model is a non-linear single-track vehicle model with the Fiala tyre to capture the vehicle's non-linear behaviour. The MPCC computes the optimal steering angle and brake torques to minimise tracking error in safe situations and maximise the vehicle-to-obstacle distance in emergencies. Furthermore, the MPCC is extended with the tyre friction circle to fully exploit the vehicle's manoeuvrability and stability. The MPCC controller is tested using real-time rapid prototyping hardware to prove its real-time capability. The performance is compared with a state-of-the-art Model Predictive Control (MPC) in a high-fidelity simulation environment. The double lane change scenario results demonstrate a significant improvement in successfully avoiding obstacles and maintaining vehicle stability.