OpenRaiser/Intern-Atlas huggingface dataset:
Shapley Sets: Feature Attribution via Recursive Function Decomposition
Venue: arXiv cs.LG 2023
Year: 2023

Despite their ubiquitous use, Shapley value feature attributions can be misleading due to feature interaction in both model and data. We propose an alternative attribution approach, Shapley Sets, which awards value to sets of features. Shapley Sets decomposes the underlying model into non-separable variable groups using a recursive function decomposition algorithm with log linear complexity in the number of variables. Shapley Sets attributes to each non-separable variable group their combined value for a particular prediction. We show that Shapley Sets is equivalent to the Shapley value over the transformed feature set and thus benefits from the same axioms of fairness. Shapley Sets is value function agnostic and we show theoretically and experimentally how Shapley Sets avoids pitfalls associated with Shapley value based alternatives and are particularly advantageous for data types with complex dependency structure.
Faster Detours in Undirected Graphs
Venue: arXiv cs.DS 2023
Year: 2023

The $k$-Detour problem is a basic path-finding problem: given a graph $G$ on $n$ vertices, with specified nodes $s$ and $t$, and a positive integer $k$, the goal is to determine if $G$ has an $st$-path of length exactly $\text{dist}(s, t) + k$, where $\text{dist}(s, t)$ is the length of a shortest path from $s$ to $t$. The $k$-Detour problem is NP-hard when $k$ is part of the input, so researchers have sought efficient parameterized algorithms for this task, running in $f(k)\text{poly}(n)$ time, for $f$ as slow-growing as possible. We present faster algorithms for $k$-Detour in undirected graphs, running in $1.853^k \text{poly}(n)$ randomized and $4.082^k \text{poly}(n)$ deterministic time. The previous fastest algorithms for this problem took $2.746^k \text{poly}(n)$ randomized and $6.523^k \text{poly}(n)$ deterministic time [Bezáková-Curticapean-Dell-Fomin, ICALP 2017]. Our algorithms use the fact that detecting a path of a given length in an undirected graph is easier if we are promised that the path belongs to what we call a "bipartitioned" subgraph, where the nodes are split into two parts and the path must satisfy constraints on those parts. Previously, this idea was used to obtain the fastest known algorithm for finding paths of length $k$ in undirected graphs [Björklund-Husfeldt-Kaski-Koivisto, JCSS 2017]. Our work has direct implications for the $k$-Longest Detour problem: in this problem, we are given the same input as in $k$-Detour, but are now tasked with determining if $G$ has an $st$-path of length at least $\text{dist}(s, t) + k.$ Our results for k-Detour imply that we can solve $k$-Longest Detour in $3.432^k \text{poly}(n)$ randomized and $16.661^k \text{poly}(n)$ deterministic time. The previous fastest algorithms for this problem took $7.539^k \text{poly}(n)$ randomized and $42.549^k \text{poly}(n)$ deterministic time [Fomin et al., STACS 2022].
The Path to Fault- and Intrusion-Resilient Manycore Systems on a Chip
Venue: arXiv cs.CR 2023
Year: 2023

The hardware computing landscape is changing. What used to be distributed systems can now be found on a chip with highly configurable, diverse, specialized and general purpose units. Such Systems-on-a-Chip (SoC) are used to control today's cyber-physical systems, being the building blocks of critical infrastructures. They are deployed in harsh environments and are connected to the cyberspace, which makes them exposed to both accidental faults and targeted cyberattacks. This is in addition to the changing fault landscape that continued technology scaling, emerging devices and novel application scenarios will bring. In this paper, we discuss how the very features, distributed, parallelized, reconfigurable, heterogeneous, that cause many of the imminent and emerging security and resilience challenges, also open avenues for their cure though SoC replication, diversity, rejuvenation, adaptation, and hybridization. We show how to leverage these techniques at different levels across the entire SoC hardware/software stack, calling for more research on the topic.
Structural Balance and Random Walks on Complex Networks with Complex Weights
Venue: arXiv cs.SI 2023
Year: 2023

Complex numbers define the relationship between entities in many situations. A canonical example would be the off-diagonal terms in a Hamiltonian matrix in quantum physics. Recent years have seen an increasing interest to extend the tools of network science when the weight of edges are complex numbers. Here, we focus on the case when the weight matrix is Hermitian, a reasonable assumption in many applications, and investigate both structural and dynamical properties of the complex-weighted networks. Building on concepts from signed graphs, we introduce a classification of complex-weighted networks based on the notion of structural balance, and illustrate the shared spectral properties within each type. We then apply the results to characterise the dynamics of random walks on complex-weighted networks, where local consensus can be achieved asymptotically when the graph is structurally balanced, while global consensus will be obtained when it is strictly unbalanced. Finally, we explore potential applications of our findings by generalising the notion of cut, and propose an associated spectral clustering algorithm. We also provide further characteristics of the magnetic Laplacian, associating directed networks to complex-weighted ones. The performance of the algorithm is verified on both synthetic and real networks.
Exploring Non-Verbal Predicates in Semantic Role Labeling: Challenges and Opportunities
Venue: arXiv cs.CL 2023
Year: 2023

Although we have witnessed impressive progress in Semantic Role Labeling (SRL), most of the research in the area is carried out assuming that the majority of predicates are verbs. Conversely, predicates can also be expressed using other parts of speech, e.g., nouns and adjectives. However, non-verbal predicates appear in the benchmarks we commonly use to measure progress in SRL less frequently than in some real-world settings -- newspaper headlines, dialogues, and tweets, among others. In this paper, we put forward a new PropBank dataset which boasts wide coverage of multiple predicate types. Thanks to it, we demonstrate empirically that standard benchmarks do not provide an accurate picture of the current situation in SRL and that state-of-the-art systems are still incapable of transferring knowledge across different predicate types. Having observed these issues, we also present a novel, manually-annotated challenge set designed to give equal importance to verbal, nominal, and adjectival predicate-argument structures. We use such dataset to investigate whether we can leverage different linguistic resources to promote knowledge transfer. In conclusion, we claim that SRL is far from "solved", and its integration with other semantic tasks might enable significant improvements in the future, especially for the long tail of non-verbal predicates, thereby facilitating further research on SRL for non-verbal predicates.
A hybrid machine learning framework for clad characteristics prediction in metal additive manufacturing
Venue: arXiv cs.LG 2023
Year: 2023

During the past decade, metal additive manufacturing (MAM) has experienced significant developments and gained much attention due to its ability to fabricate complex parts, manufacture products with functionally graded materials, minimize waste, and enable low-cost customization. Despite these advantages, predicting the impact of processing parameters on the characteristics of an MAM printed clad is challenging due to the complex nature of MAM processes. Machine learning (ML) techniques can help connect the physics underlying the process and processing parameters to the clad characteristics. In this study, we introduce a hybrid approach which involves utilizing the data provided by a calibrated multi-physics computational fluid dynamic (CFD) model and experimental research for preparing the essential big dataset, and then uses a comprehensive framework consisting of various ML models to predict and understand clad characteristics. We first compile an extensive dataset by fusing experimental data into the data generated using the developed CFD model for this study. This dataset comprises critical clad characteristics, including geometrical features such as width, height, and depth, labels identifying clad quality, and processing parameters. Second, we use two sets of processing parameters for training the ML models: machine setting parameters and physics-aware parameters, along with versatile ML models and reliable evaluation metrics to create a comprehensive and scalable learning framework for predicting clad geometry and quality. This framework can serve as a basis for clad characteristics control and process optimization. The framework resolves many challenges of conventional modeling methods in MAM by solving t the issue of data scarcity using a hybrid approach and introducing an efficient, accurate, and scalable platform for clad characteristics prediction and optimization.
Stability Analysis Framework for Particle-based Distance GANs with Wasserstein Gradient Flow
Venue: arXiv cs.LG 2023
Year: 2023

In this paper, we investigate the training process of generative networks that use a type of probability density distance named particle-based distance as the objective function, e.g. MMD GAN, Cramér GAN, EIEG GAN. However, these GANs often suffer from the problem of unstable training. In this paper, we analyze the stability of the training process of these GANs from the perspective of probability density dynamics. In our framework, we regard the discriminator $D$ in these GANs as a feature transformation mapping that maps high dimensional data into a feature space, while the generator $G$ maps random variables to samples that resemble real data in terms of feature space. This perspective enables us to perform stability analysis for the training of GANs using the Wasserstein gradient flow of the probability density function. We find that the training process of the discriminator is usually unstable due to the formulation of $\min_G \max_D E(G, D)$ in GANs. To address this issue, we add a stabilizing term in the discriminator loss function. We conduct experiments to validate our stability analysis and stabilizing method.
Transformed Protoform Reconstruction
Venue: arXiv cs.CL 2023
Year: 2023

Protoform reconstruction is the task of inferring what morphemes or words appeared like in the ancestral languages of a set of daughter languages. Meloni et al. (2021) achieved the state-of-the-art on Latin protoform reconstruction with an RNN-based encoder-decoder with attention model. We update their model with the state-of-the-art seq2seq model: the Transformer. Our model outperforms their model on a suite of different metrics on two different datasets: their Romance data of 8,000 cognates spanning 5 languages and a Chinese dataset (Hou 2004) of 800+ cognates spanning 39 varieties. We also probe our model for potential phylogenetic signal contained in the model. Our code is publicly available at https://github.com/cmu-llab/acl-2023.
Hierarchical Planning and Policy Shaping Shared Autonomy for Articulated Robots
Venue: arXiv cs.RO 2023
Year: 2023

In this work, we propose a novel shared autonomy framework to operate articulated robots. We provide strategies to design both the task-oriented hierarchical planning and policy shaping algorithms for efficient human-robot interactions in context-aware operation of articulated robots. Our framework for interplay between the human and the autonomy, as the participating agents in the system, is particularly influenced by the ideas from multi-agent systems, game theory, and theory of mind for a sliding level of autonomy. We formulate the sequential hierarchical human-in-the-loop decision making process by extending MDPs and Options framework to shared autonomy, and make use of deep RL techniques to train an uncertainty-aware shared autonomy policy. To fine-tune the formulation to a human, we use history of the system states, human actions, and their error with respect to a surrogate optimal model to encode human's internal state embeddings, beyond the designed values, by using conditional VAEs. We showcase the effectiveness of our formulation for different human skill levels and degrees of cooperativeness by using a case study of a feller-buncher machine in the challenging tasks of timber harvesting. Our framework is successful in providing a sliding level of autonomy from fully autonomous to fully manual, and is particularly successful in handling a noisy non-cooperative human agent in the loop. The proposed framework advances the state-of-the-art in shared autonomy for operating articulated robots, but can also be applied to other domains where autonomous operation is the ultimate goal.
Causal Video Summarizer for Video Exploration
Venue: arXiv cs.CV 2023
Year: 2023

Recently, video summarization has been proposed as a method to help video exploration. However, traditional video summarization models only generate a fixed video summary which is usually independent of user-specific needs and hence limits the effectiveness of video exploration. Multi-modal video summarization is one of the approaches utilized to address this issue. Multi-modal video summarization has a video input and a text-based query input. Hence, effective modeling of the interaction between a video input and text-based query is essential to multi-modal video summarization. In this work, a new causality-based method named Causal Video Summarizer (CVS) is proposed to effectively capture the interactive information between the video and query to tackle the task of multi-modal video summarization. The proposed method consists of a probabilistic encoder and a probabilistic decoder. Based on the evaluation of the existing multi-modal video summarization dataset, experimental results show that the proposed approach is effective with the increase of +5.4% in accuracy and +4.92% increase of F 1- score, compared with the state-of-the-art method.
African Union Convention on Cyber Security and Personal Data Protection: Challenges and Future Directions
Venue: arXiv cs.CR 2023
Year: 2023

This paper investigates the challenges and opportunities of implementing the African Union Convention on Cyber Security and Personal Data Protection (AUDPC) across Africa. Focusing on legal, regulatory, technical, infrastructural, capacity building, awareness, Harmonization, and cross-border cooperation challenges, the paper identifies key findings that highlight the diverse legal systems and traditions, the lack of comprehensive data protection laws, the need to balance national security and data privacy, the digital divide, cybersecurity threats, implications of emerging technologies on data privacy, limited resources for data protection authorities, and the need for capacity building in data privacy and protection. The paper also emphasizes the importance of Harmonization and cross-border cooperation in aligning data protection frameworks and collaborating with international partners and global organizations. To address these challenges and facilitate the successful implementation of the AUDPC, the paper proposes a set of recommendations, including strengthening legal and regulatory frameworks, enhancing technical and infrastructural capacities, fostering capacity-building and awareness initiatives, promoting Harmonization and cross-border cooperation, and engaging with global data protection trends and developments.
PULSAR at MEDIQA-Sum 2023: Large Language Models Augmented by Synthetic Dialogue Convert Patient Dialogues to Medical Records
Venue: arXiv cs.CL 2023
Year: 2023

This paper describes PULSAR, our system submission at the ImageClef 2023 MediQA-Sum task on summarising patient-doctor dialogues into clinical records. The proposed framework relies on domain-specific pre-training, to produce a specialised language model which is trained on task-specific natural data augmented by synthetic data generated by a black-box LLM. We find limited evidence towards the efficacy of domain-specific pre-training and data augmentation, while scaling up the language model yields the best performance gains. Our approach was ranked second and third among 13 submissions on task B of the challenge. Our code is available at https://github.com/yuping-wu/PULSAR.
NMS Threshold matters for Ego4D Moment Queries -- 2nd place solution to the Ego4D Moment Queries Challenge 2023
Venue: arXiv cs.CV 2023
Year: 2023

This report describes our submission to the Ego4D Moment Queries Challenge 2023. Our submission extends ActionFormer, a latest method for temporal action localization. Our extension combines an improved ground-truth assignment strategy during training and a refined version of SoftNMS at inference time. Our solution is ranked 2nd on the public leaderboard with 26.62% average mAP and 45.69% Recall@1x at tIoU=0.5 on the test set, significantly outperforming the strong baseline from 2023 challenge. Our code is available at https://github.com/happyharrycn/actionformer_release.
ScalOTA: Scalable Secure Over-the-Air Software Updates for Vehicles
Venue: arXiv cs.CR 2023
Year: 2023

Over-the-Air (OTA) software updates are becoming essential for electric/electronic vehicle architectures in order to reduce recalls amid the increasing software bugs and vulnerabilities. Current OTA update architectures rely heavily on direct cellular repository-to-vehicle links, which makes the repository a communication bottleneck, and increases the cellular bandwidth utilization cost as well as the software download latency. In this paper, we introduce ScalOTA, an end-to-end scalable OTA software update architecture and secure protocol for modern vehicles. For the first time, we propose using a network of update stations, as part of Electric Vehicle charging stations, to boost the download speed through these stations, and reduce the cellular bandwidth overhead significantly. Our formalized OTA update protocol ensures proven end-to-end chain-of-trust including all stakeholders: manufacturer, suppliers, update stations, and all layers of in-vehicle Electric Control Units (ECUs). The empirical evaluation shows that ScalOTA reduces the bandwidth utilization and download latency up to an order of magnitude compared with current OTA update systems.
Make A Long Image Short: Adaptive Token Length for Vision Transformers
Venue: arXiv cs.LG 2023
Year: 2023

The vision transformer is a model that breaks down each image into a sequence of tokens with a fixed length and processes them similarly to words in natural language processing. Although increasing the number of tokens typically results in better performance, it also leads to a considerable increase in computational cost. Motivated by the saying "A picture is worth a thousand words," we propose an innovative approach to accelerate the ViT model by shortening long images. Specifically, we introduce a method for adaptively assigning token length for each image at test time to accelerate inference speed. First, we train a Resizable-ViT (ReViT) model capable of processing input with diverse token lengths. Next, we extract token-length labels from ReViT that indicate the minimum number of tokens required to achieve accurate predictions. We then use these labels to train a lightweight Token-Length Assigner (TLA) that allocates the optimal token length for each image during inference. The TLA enables ReViT to process images with the minimum sufficient number of tokens, reducing token numbers in the ViT model and improving inference speed. Our approach is general and compatible with modern vision transformer architectures, significantly reducing computational costs. We verified the effectiveness of our methods on multiple representative ViT models on image classification and action recognition.
Implicit Differentiation for Hyperparameter Tuning the Weighted Graphical Lasso
Venue: arXiv cs.LG 2023
Year: 2023

We provide a framework and algorithm for tuning the hyperparameters of the Graphical Lasso via a bilevel optimization problem solved with a first-order method. In particular, we derive the Jacobian of the Graphical Lasso solution with respect to its regularization hyperparameters.
Harmonizing Feature Attributions Across Deep Learning Architectures: Enhancing Interpretability and Consistency
Venue: arXiv cs.LG 2023
Year: 2023

Ensuring the trustworthiness and interpretability of machine learning models is critical to their deployment in real-world applications. Feature attribution methods have gained significant attention, which provide local explanations of model predictions by attributing importance to individual input features. This study examines the generalization of feature attributions across various deep learning architectures, such as convolutional neural networks (CNNs) and vision transformers. We aim to assess the feasibility of utilizing a feature attribution method as a future detector and examine how these features can be harmonized across multiple models employing distinct architectures but trained on the same data distribution. By exploring this harmonization, we aim to develop a more coherent and optimistic understanding of feature attributions, enhancing the consistency of local explanations across diverse deep-learning models. Our findings highlight the potential for harmonized feature attribution methods to improve interpretability and foster trust in machine learning applications, regardless of the underlying architecture.
A Scheme to resist Fast Correlation Attack for Word Oriented LFSR based Stream Cipher
Venue: arXiv cs.CR 2023
Year: 2023

In LFSR-based stream ciphers, the knowledge of the feedback equation of the LFSR plays a critical role in most attacks. In word-based stream ciphers such as those in the SNOW series, even if the feedback configuration is hidden, knowing the characteristic polynomial of the state transition matrix of the LFSR enables the attacker to create a feedback equation over $GF(2)$. This, in turn, can be used to launch fast correlation attacks. In this work, we propose a method for hiding both the feedback equation of a word-based LFSR and the characteristic polynomial of the state transition matrix. Here, we employ a $z$-primitive $σ$-LFSR whose characteristic polynomial is randomly sampled from the distribution of primitive polynomials over $GF(2)$ of the appropriate degree. We propose an algorithm for locating $z$-primitive $σ$-LFSR configurations of a given degree. Further, an invertible matrix is generated from the key. This is then employed to generate a public parameter which is used to retrieve the feedback configuration using the key. If the key size is $n$- bits, the process of retrieving the feedback equation from the public parameter has a average time complexity $\mathbb{O}(2^{n-1})$. The proposed method has been tested on SNOW 2.0 and SNOW 3G for resistance to fast correlation attacks. We have demonstrated that the security of SNOW 2.0 and SNOW 3G increases from 128 bits to 256 bits.