OpenRaiser/Intern-Atlas huggingface dataset:
Toward a Theory of Causation for Interpreting Neural Code Models
Venue: arXiv cs.SE 2024
Year: 2024

Neural Language Models of Code, or Neural Code Models (NCMs), are rapidly progressing from research prototypes to commercial developer tools. As such, understanding the capabilities and limitations of such models is becoming critical. However, the abilities of these models are typically measured using automated metrics that often only reveal a portion of their real-world performance. While, in general, the performance of NCMs appears promising, currently much is unknown about how such models arrive at decisions. To this end, this paper introduces $do_{code}$, a post hoc interpretability method specific to NCMs that is capable of explaining model predictions. $do_{code}$ is based upon causal inference to enable programming language-oriented explanations. While the theoretical underpinnings of $do_{code}$ are extensible to exploring different model properties, we provide a concrete instantiation that aims to mitigate the impact of spurious correlations by grounding explanations of model behavior in properties of programming languages. To demonstrate the practical benefit of $do_{code}$, we illustrate the insights that our framework can provide by performing a case study on two popular deep learning architectures and ten NCMs. The results of this case study illustrate that our studied NCMs are sensitive to changes in code syntax. All our NCMs, except for the BERT-like model, statistically learn to predict tokens related to blocks of code (\eg brackets, parenthesis, semicolon) with less confounding bias as compared to other programming language constructs. These insights demonstrate the potential of $do_{code}$ as a useful method to detect and facilitate the elimination of confounding bias in NCMs.
On the Convergence of Modified Policy Iteration in Risk Sensitive Exponential Cost Markov Decision Processes
Venue: arXiv cs.LG 2024
Year: 2024

Modified policy iteration (MPI) is a dynamic programming algorithm that combines elements of policy iteration and value iteration. The convergence of MPI has been well studied in the context of discounted and average-cost MDPs. In this work, we consider the exponential cost risk-sensitive MDP formulation, which is known to provide some robustness to model parameters. Although policy iteration and value iteration have been well studied in the context of risk sensitive MDPs, MPI is unexplored. We provide the first proof that MPI also converges for the risk-sensitive problem in the case of finite state and action spaces. Since the exponential cost formulation deals with the multiplicative Bellman equation, our main contribution is a convergence proof which is quite different than existing results for discounted and risk-neutral average-cost problems as well as risk sensitive value and policy iteration approaches. We conclude our analysis with simulation results, assessing MPI's performance relative to alternative dynamic programming methods like value iteration and policy iteration across diverse problem parameters. Our findings highlight risk-sensitive MPI's enhanced computational efficiency compared to both value and policy iteration techniques.
X-Mesh: A new approach for the simulation of two-phase flow with sharp interface
Venue: arXiv cs.CE 2024
Year: 2024

Accurate modeling of moving boundaries and interfaces is a difficulty present in many situations of computational mechanics. We use the eXtreme Mesh deformation approach (X-Mesh) to simulate the interaction between two immiscible flows using the finite element method, while maintaining an accurate and sharp description of the interface without remeshing. In this new approach, the mesh is locally deformed to conform to the interface at all times, which can result in degenerated elements. The surface tension between the two fluids is added by imposing the pressure jump condition at the interface, which, when combined with the X-Mesh framework, allows us to have an exactly sharp interface. If a numerical scheme fails to properly balance surface tension and pressure gradients, it leads to numerical artefacts called spurious or parasitic currents. The method presented here is well balanced and reduces such currents down to the level of machine precision.
Algorithmic Collective Action in Machine Learning
Venue: arXiv cs.LG 2024
Year: 2024

We initiate a principled study of algorithmic collective action on digital platforms that deploy machine learning algorithms. We propose a simple theoretical model of a collective interacting with a firm's learning algorithm. The collective pools the data of participating individuals and executes an algorithmic strategy by instructing participants how to modify their own data to achieve a collective goal. We investigate the consequences of this model in three fundamental learning-theoretic settings: the case of a nonparametric optimal learning algorithm, a parametric risk minimizer, and gradient-based optimization. In each setting, we come up with coordinated algorithmic strategies and characterize natural success criteria as a function of the collective's size. Complementing our theory, we conduct systematic experiments on a skill classification task involving tens of thousands of resumes from a gig platform for freelancers. Through more than two thousand model training runs of a BERT-like language model, we see a striking correspondence emerge between our empirical observations and the predictions made by our theory. Taken together, our theory and experiments broadly support the conclusion that algorithmic collectives of exceedingly small fractional size can exert significant control over a platform's learning algorithm.
Computers as Bad Social Actors: Dark Patterns and Anti-Patterns in Interfaces that Act Socially
Venue: arXiv cs.HC 2024
Year: 2024

Technologies increasingly mimic human-like social behaviours. Beyond prototypical conversational agents like chatbots, this also applies to basic automated systems like app notifications or self-checkout machines that address or 'talk to' users in everyday situations. Whilst early evidence suggests social cues may enhance user experience, we lack a good understanding of when, and why, their use may be inappropriate. Building on a survey of English-speaking smartphone users (n=80), we conducted experience sampling, interview, and workshop studies (n=11) to elicit people's attitudes and preferences regarding how automated systems talk to them. We thematically analysed examples of phrasings/conduct participants disliked, the reasons they gave, and what they would prefer instead. One category of inappropriate behaviour we identified regards the use of social cues as tools for manipulation. We describe four unwanted tactics interfaces use: agents playing on users' emotions (e.g., guilt-tripping or coaxing them), being pushy, `mothering' users, or being passive-aggressive. Another category regards pragmatics: personal or situational factors that can make a seemingly friendly or helpful utterance come across as rude, tactless, or invasive. These include failing to account for relevant contextual particulars (e.g., embarrassing users in public); expressing obviously false personalised care; or treating a user in ways that they find inappropriate for the system's role or the nature of their relationship. We discuss these behaviours in terms of an emerging 'social' class of dark and anti-patterns. Drawing from participant recommendations, we offer suggestions for improving how interfaces treat people in interactions, including broader normative reflections on treating users respectfully.
Information Theoretic Lower Bounds for Information Theoretic Upper Bounds
Venue: arXiv cs.LG 2024
Year: 2024

We examine the relationship between the mutual information between the output model and the empirical sample and the generalization of the algorithm in the context of stochastic convex optimization. Despite increasing interest in information-theoretic generalization bounds, it is uncertain if these bounds can provide insight into the exceptional performance of various learning algorithms. Our study of stochastic convex optimization reveals that, for true risk minimization, dimension-dependent mutual information is necessary. This indicates that existing information-theoretic generalization bounds fall short in capturing the generalization capabilities of algorithms like SGD and regularized ERM, which have dimension-independent sample complexity.
Industrial and Medical Anomaly Detection Through Cycle-Consistent Adversarial Networks
Venue: arXiv cs.CV 2024
Year: 2024

In this study, a new Anomaly Detection (AD) approach for industrial and medical images is proposed. This method leverages the theoretical strengths of unsupervised learning and the data availability of both normal and abnormal classes. Indeed, the AD is often formulated as an unsupervised task, implying only normal images during training. These normal images are devoted to be reconstructed, through an autoencoder architecture for instance. However, the information contained in abnormal data, when available, is also valuable for this reconstruction. The model would be able to identify its weaknesses by better learning how to transform an abnormal (respectively normal) image into a normal (respectively abnormal) one, helping the entire model to learn better than a single normal to normal reconstruction. To address this challenge, the proposed method uses Cycle-Generative Adversarial Networks (Cycle-GAN) for (ab)normal-to-normal translation. After an input image has been reconstructed by the normal generator, an anomaly score quantifies the differences between the input and its reconstruction. Based on a threshold set to satisfy a business quality constraint, the input image is then flagged as normal or not. The proposed method is evaluated on industrial and medical datasets. The results demonstrate accurate performance with a zero false negative constraint compared to state-of-the-art methods. The code is available at https://github.com/ValDelch/CycleGANS-AnomalyDetection.
Towards Minimax Optimality of Model-based Robust Reinforcement Learning
Venue: arXiv cs.LG 2024
Year: 2024

We study the sample complexity of obtaining an $ε$-optimal policy in \emph{Robust} discounted Markov Decision Processes (RMDPs), given only access to a generative model of the nominal kernel. This problem is widely studied in the non-robust case, and it is known that any planning approach applied to an empirical MDP estimated with $\tilde{\mathcal{O}}(\frac{H^3 \mid S \mid\mid A \mid}{ε^2})$ samples provides an $ε$-optimal policy, which is minimax optimal. Results in the robust case are much more scarce. For $sa$- (resp $s$-)rectangular uncertainty sets, the best known sample complexity is $\tilde{\mathcal{O}}(\frac{H^4 \mid S \mid^2\mid A \mid}{ε^2})$ (resp. $\tilde{\mathcal{O}}(\frac{H^4 \mid S \mid^2\mid A \mid^2}{ε^2})$), for specific algorithms and when the uncertainty set is based on the total variation (TV), the KL or the Chi-square divergences. In this paper, we consider uncertainty sets defined with an $L_p$-ball (recovering the TV case), and study the sample complexity of \emph{any} planning algorithm (with high accuracy guarantee on the solution) applied to an empirical RMDP estimated using the generative model. In the general case, we prove a sample complexity of $\tilde{\mathcal{O}}(\frac{H^4 \mid S \mid\mid A \mid}{ε^2})$ for both the $sa$- and $s$-rectangular cases (improvements of $\mid S \mid$ and $\mid S \mid\mid A \mid$ respectively). When the size of the uncertainty is small enough, we improve the sample complexity to $\tilde{\mathcal{O}}(\frac{H^3 \mid S \mid\mid A \mid }{ε^2})$, recovering the lower-bound for the non-robust case for the first time and a robust lower-bound when the size of the uncertainty is small enough.
A Survey on Cyber-Resilience Approaches for Cyber-Physical Systems
Venue: arXiv cs.CR 2024
Year: 2024

Concerns for the resilience of Cyber-Physical Systems (CPS)s in critical infrastructure are growing. CPS integrate sensing, computation, control, and networking into physical objects and mission-critical services, connecting traditional infrastructure to internet technologies. While this integration increases service efficiency, it has to face the possibility of new threats posed by the new functionalities. This leads to cyber-threats, such as denial-of-service, modification of data, information leakage, spreading of malware, and many others. Cyber-resilience refers to the ability of a CPS to prepare, absorb, recover, and adapt to the adverse effects associated with cyber-threats, e.g., physical degradation of the CPS performance resulting from a cyber-attack. Cyber-resilience aims at ensuring CPS survival by keeping the core functionalities of the CPS in case of extreme events. The literature on cyber-resilience is rapidly increasing, leading to a broad variety of research works addressing this new topic. In this article, we create a systematization of knowledge about existing scientific efforts of making CPSs cyber-resilient. We systematically survey recent literature addressing cyber-resilience with a focus on techniques that may be used on CPSs. We first provide preliminaries and background on CPSs and threats, and subsequently survey state-of-the-art approaches that have been proposed by recent research work applicable to CPSs. In particular, we aim at differentiating research work from traditional risk management approaches based on the general acceptance that it is unfeasible to prevent and mitigate all possible risks threatening a CPS. We also discuss questions and research challenges, with a focus on the practical aspects of cyber-resilience, such as the use of metrics and evaluation methods as well as testing and validation environments.
Fully Dynamic Exact Edge Connectivity in Sublinear Time
Venue: arXiv cs.DS 2024
Year: 2024

Given a simple $n$-vertex, $m$-edge graph $G$ undergoing edge insertions and deletions, we give two new fully dynamic algorithms for exactly maintaining the edge connectivity of $G$ in $\tilde{O}(n)$ worst-case update time and $\tilde{O}(m^{1-1/31})$ amortized update time, respectively. Prior to our work, all dynamic edge connectivity algorithms either assumed bounded edge connectivity, guaranteed approximate solutions, or were restricted to edge insertions only. Our results provide an affirmative answer to an open question posed by Thorup [Combinatorica'07].
SCL(FOL) Revisited
Venue: arXiv cs.LO 2024
Year: 2024

This paper presents an up-to-date and refined version of the SCL calculus for first-order logic without equality. The refinement mainly consists of the following two parts: First, we incorporate a stronger notion of regularity into SCL(FOL). Our regularity definition is adapted from the SCL(T) calculus. This adapted definition guarantees non-redundant clause learning during a run of SCL. However, in contrast to the original presentation, it does not require exhaustive propagation. Second, we introduce trail and model bounding to achieve termination guarantees. In previous versions, no termination guarantees about SCL were achieved. Last, we give rigorous proofs for soundness, completeness and clause learning guarantees of SCL(FOL) and put SCL(FOL) into context of existing first-order calculi.
Online Recommendations for Agents with Discounted Adaptive Preferences
Venue: arXiv cs.LG 2024
Year: 2024

We consider a bandit recommendations problem in which an agent's preferences (representing selection probabilities over recommended items) evolve as a function of past selections, according to an unknown $\textit{preference model}$. In each round, we show a menu of $k$ items (out of $n$ total) to the agent, who then chooses a single item, and we aim to minimize regret with respect to some $\textit{target set}$ (a subset of the item simplex) for adversarial losses over the agent's choices. Extending the setting from Agarwal and Brown (2022), where uniform-memory agents were considered, here we allow for non-uniform memory in which a discount factor is applied to the agent's memory vector at each subsequent round. In the "long-term memory" regime (when the effective memory horizon scales with $T$ sublinearly), we show that efficient sublinear regret is obtainable with respect to the set of $\textit{everywhere instantaneously realizable distributions}$ (the "EIRD set", as formulated in prior work) for any $\textit{smooth}$ preference model. Further, for preferences which are bounded above and below by linear functions of memory weight (we call these "scale-bounded" preferences) we give an algorithm which obtains efficient sublinear regret with respect to nearly the $\textit{entire}$ item simplex. We show an NP-hardness result for expanding to targets beyond EIRD in general. In the "short-term memory" regime (when the memory horizon is constant), we show that scale-bounded preferences again enable efficient sublinear regret for nearly the entire simplex even without smoothness if losses do not change too frequently, yet we show an information-theoretic barrier for competing against the EIRD set under arbitrary smooth preference models even when losses are constant.
Actional Atomic-Concept Learning for Demystifying Vision-Language Navigation
Venue: arXiv cs.CV 2024
Year: 2024

Vision-Language Navigation (VLN) is a challenging task which requires an agent to align complex visual observations to language instructions to reach the goal position. Most existing VLN agents directly learn to align the raw directional features and visual features trained using one-hot labels to linguistic instruction features. However, the big semantic gap among these multi-modal inputs makes the alignment difficult and therefore limits the navigation performance. In this paper, we propose Actional Atomic-Concept Learning (AACL), which maps visual observations to actional atomic concepts for facilitating the alignment. Specifically, an actional atomic concept is a natural language phrase containing an atomic action and an object, e.g., ``go up stairs''. These actional atomic concepts, which serve as the bridge between observations and instructions, can effectively mitigate the semantic gap and simplify the alignment. AACL contains three core components: 1) a concept mapping module to map the observations to the actional atomic concept representations through the VLN environment and the recently proposed Contrastive Language-Image Pretraining (CLIP) model, 2) a concept refining adapter to encourage more instruction-oriented object concept extraction by re-ranking the predicted object concepts by CLIP, and 3) an observation co-embedding module which utilizes concept representations to regularize the observation representations. Our AACL establishes new state-of-the-art results on both fine-grained (R2R) and high-level (REVERIE and R2R-Last) VLN benchmarks. Moreover, the visualization shows that AACL significantly improves the interpretability in action decision.
Decision Problems on Copying and Shuffling
Venue: arXiv cs.FL 2024
Year: 2024

We study decision problems of the form: given a regular or linear context-free language $L$, is there a word of a given fixed form in $L$, where given fixed forms are based on word operations copy, marked copy, shuffle and their combinations.
Sneaky Spikes: Uncovering Stealthy Backdoor Attacks in Spiking Neural Networks with Neuromorphic Data
Venue: arXiv cs.CR 2024
Year: 2024

Deep neural networks (DNNs) have demonstrated remarkable performance across various tasks, including image and speech recognition. However, maximizing the effectiveness of DNNs requires meticulous optimization of numerous hyperparameters and network parameters through training. Moreover, high-performance DNNs entail many parameters, which consume significant energy during training. In order to overcome these challenges, researchers have turned to spiking neural networks (SNNs), which offer enhanced energy efficiency and biologically plausible data processing capabilities, rendering them highly suitable for sensory data tasks, particularly in neuromorphic data. Despite their advantages, SNNs, like DNNs, are susceptible to various threats, including adversarial examples and backdoor attacks. Yet, the field of SNNs still needs to be explored in terms of understanding and countering these attacks. This paper delves into backdoor attacks in SNNs using neuromorphic datasets and diverse triggers. Specifically, we explore backdoor triggers within neuromorphic data that can manipulate their position and color, providing a broader scope of possibilities than conventional triggers in domains like images. We present various attack strategies, achieving an attack success rate of up to 100% while maintaining a negligible impact on clean accuracy. Furthermore, we assess these attacks' stealthiness, revealing that our most potent attacks possess significant stealth capabilities. Lastly, we adapt several state-of-the-art defenses from the image domain, evaluating their efficacy on neuromorphic data and uncovering instances where they fall short, leading to compromised performance.
A Domain Decomposition-Based CNN-DNN Architecture for Model Parallel Training Applied to Image Recognition Problems
Venue: arXiv cs.LG 2024
Year: 2024

Deep neural networks (DNNs) and, in particular, convolutional neural networks (CNNs) have brought significant advances in a wide range of modern computer application problems. However, the increasing availability of large amounts of datasets as well as the increasing available computational power of modern computers lead to a steady growth in the complexity and size of DNN and CNN models, respectively, and thus, to longer training times. Hence, various methods and attempts have been developed to accelerate and parallelize the training of complex network architectures. In this work, a novel CNN-DNN architecture is proposed that naturally supports a model parallel training strategy and that is loosely inspired by two-level domain decomposition methods (DDM). First, local CNN models, that is, subnetworks, are defined that operate on overlapping or nonoverlapping parts of the input data, for example, sub-images. The subnetworks can be trained completely in parallel and independently of each other. Each subnetwork then outputs a local decision for the given machine learning problem which is exclusively based on the respective local input data. Subsequently, in a second step, an additional DNN model is trained which evaluates the local decisions of the local subnetworks and generates a final, global decision. In this paper, we apply the proposed architecture to image classification problems using CNNs. Experimental results for different 2D image classification problems are provided as well as a face recognition problem, and a classification problem for 3D computer tomography (CT) scans. Therefore, classical ResNet and VGG architectures are considered. The results show that the proposed approach can significantly accelerate the required training time compared to the global model and, additionally, can also help to improve the accuracy of the underlying classification problem.