OpenRaiser/Intern-Atlas huggingface dataset:
Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, $s$-$t$ Shortest Path, and Minimum-Cost Flow
Venue: arXiv cs.DS 2023
Year: 2023

We give the first almost-linear time algorithms for several problems in incremental graphs including cycle detection, strongly connected component maintenance, $s$-$t$ shortest path, maximum flow, and minimum-cost flow. To solve these problems, we give a deterministic data structure that returns a $m^{o(1)}$-approximate minimum-ratio cycle in fully dynamic graphs in amortized $m^{o(1)}$ time per update. Combining this with the interior point method framework of Brand-Liu-Sidford (STOC 2023) gives the first almost-linear time algorithm for deciding the first update in an incremental graph after which the cost of the minimum-cost flow attains value at most some given threshold $F$. By rather direct reductions to minimum-cost flow, we are then able to solve the problems in incremental graphs mentioned above. At a high level, our algorithm dynamizes the $\ell_1$ oblivious routing of Rozhoň-Grunau-Haeupler-Zuzic-Li (STOC 2022), and develops a method to extract an approximate minimum ratio cycle from the structure of the oblivious routing. To maintain the oblivious routing, we use tools from concurrent work of Kyng-Meierhans-Probst Gutenberg which designed vertex sparsifiers for shortest paths, in order to maintain a sparse neighborhood cover in fully dynamic graphs. To find a cycle, we first show that an approximate minimum ratio cycle can be represented as a fundamental cycle on a small set of trees resulting from the oblivious routing. Then, we find a cycle whose quality is comparable to the best tree cycle. This final cycle query step involves vertex and edge sparsification procedures reminiscent of previous works, but crucially requires a more powerful dynamic spanner which can handle far more edge insertions. We build such a spanner via a construction that hearkens back to the classic greedy spanner algorithm.
Neuromorphic Incremental on-chip Learning with Hebbian Weight Consolidation
Venue: arXiv cs.ET 2023
Year: 2023

As next-generation implantable brain-machine interfaces become pervasive on edge device, incrementally learning new tasks in bio-plasticity ways is urgently demanded for Neuromorphic chips. Due to the inherent characteristics of its structure, spiking neural networks are naturally well-suited for BMI-chips. Here we propose Hebbian Weight Consolidation, as well as an on-chip learning framework. HWC selectively masks synapse modifications for previous tasks, retaining them to store new knowledge from subsequent tasks while preserving the old knowledge. Leveraging the bio-plasticity of dendritic spines, the intrinsic self-organizing nature of Hebbian Weight Consolidation aligns naturally with the incremental learning paradigm, facilitating robust learning outcomes. By reading out spikes layer by layer and performing back-propagation on the external micro-controller unit, MLoC can efficiently accomplish on-chip learning. Experiments show that our HWC algorithm up to 23.19% outperforms lower bound that without incremental learning algorithm, particularly in more challenging monkey behavior decoding scenarios. Taking into account on-chip computing on Synsense Speck 2e chip, our proposed algorithm exhibits an improvement of 11.06%. This study demonstrates the feasibility of employing incremental learning for high-performance neural signal decoding in next-generation brain-machine interfaces.
Enhanced Cross Z-Complementary Set and Its Application in Generalized Spatial Modulation
Venue: arXiv cs.IT 2023
Year: 2023

Generalized spatial modulation (GSM) is a novel multiple-antenna technique offering flexibility among spectral efficiency, energy efficiency, and the cost of RF chains. In this paper, a novel class of sequence sets, called enhanced cross Zcomplementary set (E-CZCS), is proposed for efficient training sequence design in broadband GSM systems. Specifically, an E-CZCS consists of multiple CZCSs possessing front-end and tail-end zero-correlation zones (ZCZs), whereby any two distinct CZCSs have a tail-end ZCZ when a novel type of cross-channel aperiodic correlation sums is considered. The theoretical upper bound on the ZCZ width is first derived, upon which optimal E-CZCSs with flexible parameters are constructed. For optimal channel estimation over frequency-selective channels, we introduce and evaluate a novel GSM training framework employing the proposed E-CZCSs.
Data-efficient Deep Reinforcement Learning for Vehicle Trajectory Control
Venue: arXiv cs.LG 2023
Year: 2023

Advanced vehicle control is a fundamental building block in the development of autonomous driving systems. Reinforcement learning (RL) promises to achieve control performance superior to classical approaches while keeping computational demands low during deployment. However, standard RL approaches like soft-actor critic (SAC) require extensive amounts of training data to be collected and are thus impractical for real-world application. To address this issue, we apply recently developed data-efficient deep RL methods to vehicle trajectory control. Our investigation focuses on three methods, so far unexplored for vehicle control: randomized ensemble double Q-learning (REDQ), probabilistic ensembles with trajectory sampling and model predictive path integral optimizer (PETS-MPPI), and model-based policy optimization (MBPO). We find that in the case of trajectory control, the standard model-based RL formulation used in approaches like PETS-MPPI and MBPO is not suitable. We, therefore, propose a new formulation that splits dynamics prediction and vehicle localization. Our benchmark study on the CARLA simulator reveals that the three identified data-efficient deep RL approaches learn control strategies on a par with or better than SAC, yet reduce the required number of environment interactions by more than one order of magnitude.
HMAS: enabling seamless collaboration between drones, quadruped robots, and human operators with efficient spatial awareness
Venue: arXiv cs.MA 2023
Year: 2023

Heterogeneous robots equipped with multi-modal sensors (e.g., UAV, wheeled and legged terrestrial robots) provide rich and complementary functions that may help human operators to accomplish complex tasks in unknown environments. However, seamlessly integrating heterogeneous agents and making them interact and collaborate still arise challenging issues. In this paper, we define a ROS 2 based software architecture that allows to build incarnated heterogeneous multi-agent systems (HMAS) in a generic way. We showcase its effectiveness through a scenario integrating aerial drones, quadruped robots, and human operators (see https://youtu.be/iOtCCticGuk). In addition, agent spatial awareness in unknown outdoor environments is a critical step for realizing autonomous individual movements, interactions, and collaborations. Through intensive experimental measurements, RTK-GPS is shown to be a suitable solution for achieving the required locating accuracy.
On the (In)approximability of Combinatorial Contracts
Venue: arXiv cs.GT 2023
Year: 2023

We study two combinatorial contract design models -- multi-agent and multi-action -- where a principal delegates the execution of a costly project to others. In both settings, the principal cannot observe the choices of the agent(s), only the project's outcome (success or failure), and incentivizes the agent(s) using a contract, which is a payment scheme that specifies the payment to the agent(s) upon a project's success. In the multi-agent setting, the project is delegated to a team of agents, and every agent chooses whether or not to exert effort. A success probability function specifies the probability of success for every subset of agents exerting effort. For the family of submodular success probability functions, Duetting et al. [2023] established a poly-time constant-factor approximation to the optimal contract, and left open whether this problem admits a PTAS. We show that no poly-time algorithm guarantees a better than $0.7$-approximation to the optimal contract. For XOS functions, Duetting et al. [2023] give a poly-time constant approximation with value and demand queries. We show that with value queries only, one cannot get any constant approximation. In the multi-action setting, the project is delegated to a single agent, who can take any subset of a given set of actions. Here, a success probability function specifies the probability of success for any subset of actions. Duetting et al. [2021a] devised a poly-time algorithm for computing an optimal contract for gross substitutes success probability functions, and established NP-hardness with respect to submodular functions. We further strengthen this hardness result by showing that this problem does not admit any constant approximation either. For the broader class of XOS functions, we establish the hardness of obtaining a $n^{-1/2+\varepsilon}$-approximation for any $\varepsilon > 0$.
The Role of Visual Features in Text-Based CAPTCHAs: An fNIRS Study for Usable Security
Venue: arXiv cs.CR 2023
Year: 2023

To mitigate dictionary attacks or similar undesirable automated attacks to information systems, developers mostly prefer using CAPTCHA challenges as Human Interactive Proofs (HIPs) to distinguish between human users and scripts. Appropriate use of CAPTCHA requires a setup that balances between robustness and usability during the design of a challenge. The previous research reveals that most usability studies have used accuracy and response time as measurement criteria for quantitative analysis. The present study aims at applying optical neuroimaging techniques for the analysis of CAPTCHA design. The functional Near-Infrared Spectroscopy technique was used to explore the hemodynamic responses in the prefrontal cortex elicited by CAPTCHA stimulus of varying types. )e findings suggest that regions in the left and right dorsolateral and right dorsomedial prefrontal cortex respond to the degrees of line occlusion, rotation, and wave distortions present in a CAPTCHA. The systematic addition of the visual effects introduced nonlinear effects on the behavioral and prefrontal oxygenation measures, indicative of the emergence of Gestalt effects that might have influenced the perception of the overall CAPTCHA figure.
VTimeLLM: Empower LLM to Grasp Video Moments
Venue: arXiv cs.CV 2023
Year: 2023

Large language models (LLMs) have shown remarkable text understanding capabilities, which have been extended as Video LLMs to handle video data for comprehending visual details. However, existing Video LLMs can only provide a coarse description of the entire video, failing to capture the precise start and end time boundary of specific events. In this paper, we solve this issue via proposing VTimeLLM, a novel Video LLM designed for fine-grained video moment understanding and reasoning with respect to time boundary. Specifically, our VTimeLLM adopts a boundary-aware three-stage training strategy, which respectively utilizes image-text pairs for feature alignment, multiple-event videos to increase temporal-boundary awareness, and high-quality video-instruction tuning to further improve temporal understanding ability as well as align with human intents. Extensive experiments demonstrate that in fine-grained time-related comprehension tasks for videos such as Temporal Video Grounding and Dense Video Captioning, VTimeLLM significantly outperforms existing Video LLMs. Besides, benefits from the fine-grained temporal understanding of the videos further enable VTimeLLM to beat existing Video LLMs in video dialogue benchmark, showing its superior cross-modal understanding and reasoning abilities.
Technical Debt Management Automation: State of the Art and Future Perspectives
Venue: arXiv cs.SE 2023
Year: 2023

Technical Debt (TD) refers to non-optimal decisions made in software projects that may lead to short-term benefits, but potentially harm the system's maintenance in the long-term. Technical debt management (TDM) refers to a set of activities that are performed to handle TD, e.g., identification. These activities can entail tasks such as code and architectural analysis, which can be time-consuming if done manually. Thus, substantial research work has focused on automating TDM tasks (e.g., automatic identification of code smells). However, there is a lack of studies that summarize current approaches in TDM automation. This can hinder practitioners in selecting optimal automation strategies to efficiently manage TD. It can also prevent researchers from understanding the research landscape and addressing the research problems that matter the most. Thus, the main objective of this study is to provide an overview of the state of the art in TDM automation, analyzing the available tools, their use, and the challenges in automating TDM. For this, we conducted a systematic mapping study (SMS), and from an initial set of 1086 primary studies, 178 were selected to answer three research questions covering different facets of TDM automation. We found 121 automation artifacts, which were classified in 4 different types (i.e., tools, plugins, scripts, and bots); the inputs/outputs and interfaces were also collected and reported. Finally, a conceptual model is proposed that synthesizes the results and allows to discuss the current state of TDM automation and related challenges. The results show that the research community has investigated to a large extent how to perform various TDM activities automatically, considering the number of studies and automation artifacts we identified. More research is needed towards fully automated TDM, specially concerning the integration of the automation artifacts.
ESG Accountability Made Easy: DocQA at Your Service
Venue: arXiv cs.CL 2023
Year: 2023

We present Deep Search DocQA. This application enables information extraction from documents via a question-answering conversational assistant. The system integrates several technologies from different AI disciplines consisting of document conversion to machine-readable format (via computer vision), finding relevant data (via natural language processing), and formulating an eloquent response (via large language models). Users can explore over 10,000 Environmental, Social, and Governance (ESG) disclosure reports from over 2000 corporations. The Deep Search platform can be accessed at: https://ds4sd.github.io.
Color-Emotion Associations in Art: Fuzzy Approach
Venue: arXiv cs.CV 2023
Year: 2023

Art objects can evoke certain emotions. Color is a fundamental element of visual art and plays a significant role in how art is perceived. This paper introduces a novel approach to classifying emotions in art using Fuzzy Sets. We employ a fuzzy approach because it aligns well with human judgments' imprecise and subjective nature. Extensive fuzzy colors (n=120) and a broad emotional spectrum (n=10) allow for a more human-consistent and context-aware exploration of emotions inherent in paintings. First, we introduce the fuzzy color representation model. Then, at the fuzzification stage, we process the Wiki Art Dataset of paintings tagged with emotions, extracting fuzzy dominant colors linked to specific emotions. This results in fuzzy color distributions for ten emotions. Finally, we convert them back to a crisp domain, obtaining a knowledge base of color-emotion associations in primary colors. Our findings reveal strong associations between specific emotions and colors; for instance, gratitude strongly correlates with green, brown, and orange. Other noteworthy associations include brown and anger, orange with shame, yellow with happiness, and gray with fear. Using these associations and Jaccard similarity, we can find the emotions in the arbitrary untagged image. We conducted a 2AFC experiment involving human subjects to evaluate the proposed method. The average hit rate of 0.77 indicates a significant correlation between the method's predictions and human perception. The proposed method is simple to adapt to art painting retrieval systems. The study contributes to the theoretical understanding of color-emotion associations in art, offering valuable insights for various practical applications besides art, like marketing, design, and psychology.
CrimeGraphNet: Link Prediction in Criminal Networks with Graph Convolutional Networks
Venue: arXiv cs.SI 2023
Year: 2023

In this paper, we introduce CrimeGraphNet, a novel approach for link prediction in criminal networks utilizingGraph Convolutional Networks (GCNs). Criminal networks are intricate and dynamic, with covert links that are challenging to uncover. Accurate prediction of these links can aid in proactive crime prevention and investigation. Existing methods often fail to capture the complex interconnections in such networks. They also struggle in scenarios where only limited labeled data is available for training. To address these challenges, we propose CrimeGraphNet, which leverages the power of GCNs for link prediction in these networks. The GCNmodel effectively captures topological features and node characteristics, making it well-suited for this task. We evaluate CrimeGraphNet on several real-world criminal network datasets. Our results demonstrate that CrimeGraphNet outperforms existing methods in terms of prediction accuracy, robustness, and computational efAciency. Furthermore, our approach enables the extraction of meaningful insights from the predicted links, thereby contributing to a better understanding of the underlying criminal activities. Overall, CrimeGraphNet represents a signiAcant step forward in the use of deep learning for criminal network analysis.
Decentralized Deepfake Detection Blockchain Network using Dynamic Algorithm management
Venue: arXiv cs.CR 2023
Year: 2023

Deepfake technology is a major threat to the integrity of digital media. This paper presents a comprehensive framework for a blockchain-based decentralized system designed to tackle the escalating challenge of digital content integrity. The proposed system integrates advanced deep learning algorithms with the immutable and transparent nature of blockchain technology to create a trustless environment where authenticity can be verified without relying on a single centralized authority. Furthermore, the system utilizes smart contracts for dynamic algorithm management and token-based incentives further enhances the system's effectiveness and adaptability. The decentralized architecture of the system democratizes the process of verifying digital content and introduces a novel approach to combat deepfakes. The collaborative and adjustable nature of this system sets a new benchmark for digital media integrity, offering a more robust digital media environment.
FediOS: Decoupling Orthogonal Subspaces for Personalization in Feature-skew Federated Learning
Venue: arXiv cs.LG 2023
Year: 2023

Personalized federated learning (pFL) enables collaborative training among multiple clients to enhance the capability of customized local models. In pFL, clients may have heterogeneous (also known as non-IID) data, which poses a key challenge in how to decouple the data knowledge into generic knowledge for global sharing and personalized knowledge for preserving local personalization. A typical way of pFL focuses on label distribution skew, and they adopt a decoupling scheme where the model is split into a common feature extractor and two prediction heads (generic and personalized). However, such a decoupling scheme cannot solve the essential problem of feature skew heterogeneity, because a common feature extractor cannot decouple the generic and personalized features. Therefore, in this paper, we rethink the architecture decoupling design for feature-skew pFL and propose an effective pFL method called FediOS. In FediOS, we reformulate the decoupling into two feature extractors (generic and personalized) and one shared prediction head. Orthogonal projections are used for clients to map the generic features into one common subspace and scatter the personalized features into different subspaces to achieve decoupling for them. In addition, a shared prediction head is trained to balance the importance of generic and personalized features during inference. Extensive experiments on four vision datasets demonstrate our method reaches state-of-the-art pFL performances under feature skew heterogeneity.
Anatomy and Physiology of Artificial Intelligence in PET Imaging
Venue: arXiv cs.CV 2023
Year: 2023

The influence of artificial intelligence (AI) within the field of nuclear medicine has been rapidly growing. Many researchers and clinicians are seeking to apply AI within PET, and clinicians will soon find themselves engaging with AI-based applications all along the chain of molecular imaging, from image reconstruction to enhanced reporting. This expanding presence of AI in PET imaging will result in greater demand for educational resources for those unfamiliar with AI. The objective of this article to is provide an illustrated guide to the core principles of modern AI, with specific focus on aspects that are most likely to be encountered in PET imaging. We describe convolutional neural networks, algorithm training, and explain the components of the commonly used U-Net for segmentation and image synthesis.
A Lightweight Clustering Framework for Unsupervised Semantic Segmentation
Venue: arXiv cs.CV 2023
Year: 2023

Unsupervised semantic segmentation aims to categorize each pixel in an image into a corresponding class without the use of annotated data. It is a widely researched area as obtaining labeled datasets is expensive. While previous works in the field have demonstrated a gradual improvement in model accuracy, most required neural network training. This made segmentation equally expensive, especially when dealing with large-scale datasets. We thus propose a lightweight clustering framework for unsupervised semantic segmentation. We discovered that attention features of the self-supervised Vision Transformer exhibit strong foreground-background differentiability. Therefore, clustering can be employed to effectively separate foreground and background image patches. In our framework, we first perform multilevel clustering across the Dataset-level, Category-level, and Image-level, and maintain consistency throughout. Then, the binary patch-level pseudo-masks extracted are upsampled, refined and finally labeled. Furthermore, we provide a comprehensive analysis of the self-supervised Vision Transformer features and a detailed comparison between DINO and DINOv2 to justify our claims. Our framework demonstrates great promise in unsupervised semantic segmentation and achieves state-of-the-art results on PASCAL VOC and MS COCO datasets.
CrimeGAT: Leveraging Graph Attention Networks for Enhanced Predictive Policing in Criminal Networks
Venue: arXiv cs.SI 2023
Year: 2023

In this paper, we present CrimeGAT, a novel application of Graph Attention Networks (GATs) for predictive policing in criminal networks. Criminal networks pose unique challenges for predictive analytics due to their complex structure, multi-relational links, and dynamic behavior. Traditional methods often fail to capture these complexities, leading to suboptimal predictions. To address these challenges, we propose the use of GATs, which can effectively leverage both node features and graph structure to make predictions. Our proposed CrimeGAT model integrates attention mechanisms to weigh the importance of a node's neighbors, thereby capturing the local and global structures of criminal networks. We formulate the problem as learning a function that maps node features and graph structure to a prediction of future criminal activity. The experimental results on real-world datasets demonstrate that CrimeGAT out-performs conventional methods in predicting criminal activities, thereby providing a powerful tool for law enforcement agencies to proactively deploy resources. Furthermore, the interpretable nature of the attentionmechanism inGATs offers insights into the key players and relationships in criminal networks. This research opens new avenues for applying deep learning techniques in the Aeld of predictive policing and criminal network analysis.