OpenRaiser/Intern-Atlas huggingface dataset:
Depth lower bounds in Stabbing Planes for combinatorial principles
Venue: arXiv cs.CC 2024
Year: 2024

Stabbing Planes (also known as Branch and Cut) is a proof system introduced very recently which, informally speaking, extends the DPLL method by branching on integer linear inequalities instead of single variables. The techniques known so far to prove size and depth lower bounds for Stabbing Planes are generalizations of those used for the Cutting Planes proof system. For size lower bounds these are established by monotone circuit arguments, while for depth these are found via communication complexity and protection. As such these bounds apply for lifted versions of combinatorial statements. Rank lower bounds for Cutting Planes are also obtained by geometric arguments called protection lemmas. In this work we introduce two new geometric approaches to prove size/depth lower bounds in Stabbing Planes working for any formula: (1) the antichain method, relying on Sperner's Theorem and (2) the covering method which uses results on essential coverings of the boolean cube by linear polynomials, which in turn relies on Alon's combinatorial Nullenstellensatz. We demonstrate their use on classes of combinatorial principles such as the Pigeonhole principle, the Tseitin contradictions and the Linear Ordering Principle. By the first method we prove almost linear size lower bounds and optimal logarithmic depth lower bounds for the Pigeonhole principle and analogous lower bounds for the Tseitin contradictions over the complete graph and for the Linear Ordering Principle. By the covering method we obtain a superlinear size lower bound and a logarithmic depth lower bound for Stabbing Planes proof of Tseitin contradictions over a grid graph.
Decidability for Sturmian words
Venue: arXiv cs.LO 2024
Year: 2024

We show that the first-order theory of Sturmian words over Presburger arithmetic is decidable. Using a general adder recognizing addition in Ostrowski numeration systems by Baranwal, Schaeffer and Shallit, we prove that the first-order expansions of Presburger arithmetic by a single Sturmian word are uniformly $ω$-automatic, and then deduce the decidability of the theory of the class of such structures. Using an implementation of this decision algorithm called Pecan, we automatically reprove classical theorems about Sturmian words in seconds, and are able to obtain new results about antisquares and antipalindromes in characteristic Sturmian words.
Token-Modification Adversarial Attacks for Natural Language Processing: A Survey
Venue: arXiv cs.CL 2024
Year: 2024

Many adversarial attacks target natural language processing systems, most of which succeed through modifying the individual tokens of a document. Despite the apparent uniqueness of each of these attacks, fundamentally they are simply a distinct configuration of four components: a goal function, allowable transformations, a search method, and constraints. In this survey, we systematically present the different components used throughout the literature, using an attack-independent framework which allows for easy comparison and categorisation of components. Our work aims to serve as a comprehensive guide for newcomers to the field and to spark targeted research into refining the individual attack components.
CG-CNN: Self-Supervised Feature Extraction Through Contextual Guidance and Transfer Learning
Venue: arXiv cs.CV 2024
Year: 2024

Contextually Guided Convolutional Neural Networks (CG-CNNs) employ self-supervision and contextual information to develop transferable features across diverse domains, including visual, tactile, temporal, and textual data. This work showcases the adaptability of CG-CNNs through applications to various datasets such as Caltech and Brodatz textures, the VibTac-12 tactile dataset, hyperspectral images, and challenges like the XOR problem and text analysis. In text analysis, CG-CNN employs an innovative embedding strategy that utilizes the context of neighboring words for classification, while in visual and signal data, it enhances feature extraction by exploiting spatial information. CG-CNN mimics the context-guided unsupervised learning mechanisms of biological neural networks and it can be trained to learn its features on limited-size datasets. Our experimental results on natural images reveal that CG-CNN outperforms comparable first-layer features of well-known deep networks such as AlexNet, ResNet, and GoogLeNet in terms of transferability and classification accuracy. In text analysis, CG-CNN learns word embeddings that outperform traditional models like Word2Vec in tasks such as the 20 Newsgroups text classification. Furthermore, ongoing development involves training CG-CNN on outputs from another CG-CNN to explore multi-layered architectures, aiming to construct more complex and descriptive features. This scalability and adaptability to various data types underscore the potential of CG-CNN to handle a wide range of applications, making it a promising architecture for tackling diverse data representation challenges.
EmoWrite: A Sentiment Analysis-Based Thought to Text Conversion -- A Validation Study
Venue: arXiv cs.HC 2024
Year: 2024

Objective- The objective of this study is to introduce EmoWrite, a novel brain-computer interface (BCI) system aimed at addressing the limitations of existing BCI-based systems. Specifically, the objective includes improving typing speed, accuracy, user convenience, emotional state capturing, and sentiment analysis within the context of BCI technology. Method- The method involves the development and implementation of EmoWrite, utilizing a user-centric Recurrent Neural Network (RNN) for thought-to-text conversion. The system incorporates visual feedback and introduces a dynamic keyboard with a contextually adaptive character appearance. Comprehensive evaluation and comparison against existing approaches are conducted, considering various metrics such as accuracy, typing speed, sentiment analysis, emotional state capturing, and user interface latency. The data required for this experiment was obtained from a total of 72 volunteers (40 male and 32 female) aged between 18 and 40 Results- EmoWrite achieves notable results, including a typing speed of 6.6 Words Per Minute (WPM) and 31.9 Characters Per Minute (CPM) with a high accuracy rate of 90.36%. It excels in capturing emotional states, with an Information Transfer Rate (ITR) of 87.55 bits/min for commands and 72.52 bits/min for letters, surpassing other systems. Additionally, it offers an intuitive user interface with low latency of 2.685 seconds. Conclusion- The introduction of EmoWrite represents a significant stride towards enhancing BCI usability and emotional integration. The findings suggest that EmoWrite holds promising potential for revolutionizing communication aids for individuals with motor disabilities.
Estimating the Expected Influence Capacities of Nodes in Complex Networks under the Susceptible-Infectious-Recovered (SIR) Model
Venue: arXiv cs.SI 2024
Year: 2024

In recent years, epidemic modeling in complex networks has found many applications, including modeling of information or gossip spread in online social networks, modeling of malware spread in communication networks, and the most recent model of the COVID-19 pandemic. If the information disseminated is accurate, for example, maximizing its distribution is desirable, whereas if it is a rumor or a virus, its spread should be minimized. In this context, it is very important to identify super-spreaders that maximize or minimize propagation. Lately, studies for detecting super-spreaders have gained momentum. Most of the studies carried out aim to distinguish the influences of nodes under a specific propagation model (such as SIR) using network centrality measures and subsequently, to rank the nodes accordingly. However, in this study, we developed an algorithm that approximates the expected influence of nodes under the popular SIR model. By considering the behavior of the SIR model and only the shortest paths between nodes, the algorithm ranks the nodes according to this approximated value. Our developed algorithm is named the Expected Value Estimation (EVE). We compared the performance of EVE, using different SIR settings on real datasets, with that of many current well-known centrality measures. The experimental studies demonstrated that the solution quality (ranking capability) of EVE is superior to that of its competitors.
NaturalConv: A Chinese Dialogue Dataset Towards Multi-turn Topic-driven Conversation
Venue: arXiv cs.CL 2024
Year: 2024

In this paper, we propose a Chinese multi-turn topic-driven conversation dataset, NaturalConv, which allows the participants to chat anything they want as long as any element from the topic is mentioned and the topic shift is smooth. Our corpus contains 19.9K conversations from six domains, and 400K utterances with an average turn number of 20.1. These conversations contain in-depth discussions on related topics or widely natural transition between multiple topics. We believe either way is normal for human conversation. To facilitate the research on this corpus, we provide results of several benchmark models. Comparative results show that for this dataset, our current models are not able to provide significant improvement by introducing background knowledge/topic. Therefore, the proposed dataset should be a good benchmark for further research to evaluate the validity and naturalness of multi-turn conversation systems. Our dataset is available at https://ailab.tencent.com/ailab/nlp/dialogue/#datasets.
Thermodynamic topology optimization for hardening materials
Venue: arXiv cs.CE 2024
Year: 2024

Topology optimization is an important basis for the design of components. Here, the optimal structure is found within a design space subject to boundary conditions. Thereby, the specific material law has a strong impact on the final design. An important kind of material behavior is hardening: then a, for instance, linear-elastic structure is not optimal if plastic deformation will be induced by the loads. Since hardening behavior has a remarkable impact on the resultant stress field, it needs to be accounted for during topology optimization. In this contribution, we present an extension of the thermodynamic topology optimization that accounts for this non-linear material behavior due to the evolution of plastic strains. For this purpose, we develop a novel surrogate model that allows to compute the plastic strain tensor corresponding to the current structure design for arbitrary hardening behavior. We show the agreement of the model with the classic plasticity model for monotonic loading. Furthermore, we demonstrate the interaction of the topology optimization for hardening material behavior results in structural changes.
The Common Intuition to Transfer Learning Can Win or Lose: Case Studies for Linear Regression
Venue: arXiv cs.LG 2024
Year: 2024

We study a fundamental transfer learning process from source to target linear regression tasks, including overparameterized settings where there are more learned parameters than data samples. The target task learning is addressed by using its training data together with the parameters previously computed for the source task. We define a transfer learning approach to the target task as a linear regression optimization with a regularization on the distance between the to-be-learned target parameters and the already-learned source parameters. We analytically characterize the generalization performance of our transfer learning approach and demonstrate its ability to resolve the peak in generalization errors in double descent phenomena of the minimum L2-norm solution to linear regression. Moreover, we show that for sufficiently related tasks, the optimally tuned transfer learning approach can outperform the optimally tuned ridge regression method, even when the true parameter vector conforms to an isotropic Gaussian prior distribution. Namely, we demonstrate that transfer learning can beat the minimum mean square error (MMSE) solution of the independent target task. Our results emphasize the ability of transfer learning to extend the solution space to the target task and, by that, to have an improved MMSE solution. We formulate the linear MMSE solution to our transfer learning setting and point out its key differences from the common design philosophy to transfer learning.
Synthesizing Computable Functions from Rational Specifications over Infinite Words
Venue: arXiv cs.FL 2024
Year: 2024

The synthesis problem asks to automatically generate, if it exists, an algorithm from a specification of correct input-output pairs. In this paper, we consider the synthesis of computable functions of infinite words, for a classical Turing computability notion over infinite inputs. We consider specifications which are rational relations of infinite words, i.e., specifications defined non-deterministic parity transducers. We prove that the synthesis problem of computable functions from rational specifications is undecidable. We provide an incomplete but sound reduction to some parity game, such that if Eve wins the game, then the rational specification is realizable by a computable function. We prove that this function is even computable by a deterministic two-way transducer. We provide a sufficient condition under which the latter game reduction is complete. This entails the decidability of the synthesis problem of computable functions, which we prove to be ExpTime-complete, for a large subclass of rational specifications, namely deterministic rational specifications. This subclass contains the class of automatic relations over infinite words, a yardstick in reactive synthesis.
Local Interpretations for Explainable Natural Language Processing: A Survey
Venue: arXiv cs.CL 2024
Year: 2024

As the use of deep learning techniques has grown across various fields over the past decade, complaints about the opaqueness of the black-box models have increased, resulting in an increased focus on transparency in deep learning models. This work investigates various methods to improve the interpretability of deep neural networks for Natural Language Processing (NLP) tasks, including machine translation and sentiment analysis. We provide a comprehensive discussion on the definition of the term interpretability and its various aspects at the beginning of this work. The methods collected and summarised in this survey are only associated with local interpretation and are specifically divided into three categories: 1) interpreting the model's predictions through related input features; 2) interpreting through natural language explanation; 3) probing the hidden states of models and word representations.
LatentKeypointGAN: Controlling Images via Latent Keypoints
Venue: arXiv cs.CV 2024
Year: 2024

Generative adversarial networks (GANs) have attained photo-realistic quality in image generation. However, how to best control the image content remains an open challenge. We introduce LatentKeypointGAN, a two-stage GAN which is trained end-to-end on the classical GAN objective with internal conditioning on a set of space keypoints. These keypoints have associated appearance embeddings that respectively control the position and style of the generated objects and their parts. A major difficulty that we address with suitable network architectures and training schemes is disentangling the image into spatial and appearance factors without domain knowledge and supervision signals. We demonstrate that LatentKeypointGAN provides an interpretable latent space that can be used to re-arrange the generated images by re-positioning and exchanging keypoint embeddings, such as generating portraits by combining the eyes, nose, and mouth from different images. In addition, the explicit generation of keypoints and matching images enables a new, GAN-based method for unsupervised keypoint detection.
Place Bisimilarity is Decidable, Indeed!
Venue: arXiv cs.LO 2024
Year: 2024

Place bisimilarity $\sim_p$ is a behavioral equivalence for finite Petri nets, originally proposed in \cite{ABS91}, that, differently from all the other behavioral relations proposed so far, is not defined over the markings of a finite net, rather over its places, which are finitely many. Place bisimilarity $\sim_p$ was claimed decidable in \cite{ABS91}, but its decidability was not really proved. We show that it is possible to decide $\sim_p$ with a simple algorithm, which essentially scans all the place relations (which are finitely many) to check whether they are place bisimulations. We also show that $\sim_p$ does respect the intended causal semantics of Petri nets, as it is finer than causal-net bisimilarity \cite{Gor22}. Moreover, we propose a slightly coarser variant, we call d-place bisimilarity $\sim_d$, that we conjecture to be the coarsest equivalence, fully respecting causality and branching time (as it is finer than fully-concurrent bisimilarity \cite{BDKP91}), to be decidable on finite Petri nets. Finally, two even coarser variants are discussed, namely i-place and i-d-place bisimilarities, which are still decidable, do preserve the concurrent behavior of Petri nets, but do not respect causality. These results open the way towards formal verification (by equivalence checking) of distributed systems modeled by finite Petri nets.
Using Voice and Biofeedback to Predict User Engagement during Product Feedback Interviews
Venue: arXiv cs.SE 2024
Year: 2024

Capturing users' engagement is crucial for gathering feedback about the features of a software product. In a market-driven context, current approaches to collect and analyze users' feedback are based on techniques leveraging information extracted from product reviews and social media. These approaches are hardly applicable in bespoke software development, or in contexts in which one needs to gather information from specific users. In such cases, companies need to resort to face-to-face interviews to get feedback on their products. In this paper, we propose to utilize biometric data, in terms of physiological and voice features, to complement interviews with information about the engagement of the user on the discussed product-relevant topics. We evaluate our approach by interviewing users while gathering their physiological data (i.e., biofeedback) using an Empatica E4 wristband, and capturing their voice through the default audio-recorder of a common laptop. Our results show that we can predict users' engagement by training supervised machine learning algorithms on biometric data (F1=0.72), and that voice features alone are sufficiently effective (F1=0.71). Our work contributes with one the first studies in requirements engineering in which biometrics are used to identify emotions. This is also the first study in software engineering that considers voice analysis. The usage of voice features could be particularly helpful for emotion-aware requirements elicitation in remote communication, either performed by human analysts or voice-based chatbots, and can also be exploited to support the analysis of meetings in software engineering research.
Does the First Response Matter for Future Contributions? A Study of First Contributions
Venue: arXiv cs.SE 2024
Year: 2024

Open Source Software (OSS) projects rely on a continuous stream of new contributors for their livelihood. Recent studies reported that new contributors experience many barriers in their first contribution, with the social barrier being critical. Although a number of studies investigated the social barriers to new contributors, we hypothesize that negative first responses may cause an unpleasant feeling, and subsequently lead to the discontinuity of any future contribution. We execute protocols of a registered report to analyze 2,765,917 first contributions as Pull Requests (PRs) with 642,841 first responses. We characterize most first response as being positive, but less responsive, and exhibiting sentiments of fear, joy and love. Results also indicate that negative first responses have the literal intention to arouse emotions of being either constructive (50.71%) or criticizing (37.68%) in nature. Running different machine learning models, we find that predicting future interactions is low (F1 score of 0.6171), but relatively better than baselines. Furthermore, an analysis of these models show that interactions are positively correlated with a future contribution, with other dimensions (i.e., project, contributor, contribution) having a large effect.
UX Debt: Developers Borrow While Users Pay
Venue: arXiv cs.SE 2024
Year: 2024

Technical debt has become a well-known metaphor among software professionals, illustrating how shortcuts taken during development can accumulate and become a burden for software projects. In the traditional notion of technical debt, software developers borrow from the maintainability and extensibility of a software system for a short-term speed up in development time. In the future, they are the ones who pay the interest in form of longer development times. User experience (UX) debt, on the other hand, focuses on shortcuts taken to speed up development at the expense of subpar usability, thus mainly borrowing from user efficiency. Most research considers code-centric technical debt, focusing on the implementation. With this article, we want to build awareness for the often overlooked UX debt of software systems, shifting the focus from the source code towards users. We outline three classes of UX debt that we observed in practice: code-centric, architecture-centric, and process-centric UX debt. In an expert survey, we validated those classes, with code-centric and process-centric UX debt getting the strongest support. We discuss our participants' feedback and present recommendations on how software development teams can mitigate UX debt in their user-facing applications.
Tractability Frontiers in Multi-Robot Coordination and Geometric Reconfiguration
Venue: arXiv cs.RO 2024
Year: 2024

We study the Monotone Sliding Reconfiguration (MSR) problem, in which $\textit{labeled}$ pairwise interior-disjoint objects in a planar workspace need to be brought $\textit{one by one}$ from their initial positions to given target positions, without causing collisions. That is, at each step only one object moves to its respective target, where it stays thereafter. MSR is a natural special variant of Multi-Robot Motion Planning (MRMP) and related reconfiguration problems, many of which are known to be computationally hard. A key question is identifying the minimal mitigating assumptions that enable efficient algorithms for such problems. We first show that despite the monotonicity requirement, MSR remains a computationally hard MRMP problem. We then provide additional hardness results for MSR that rule out several natural assumptions. For example, we show that MSR remains hard without obstacles in the workspace. On the positive side, we introduce a family of MSR instances that always have a solution through a novel structural assumption pertaining to the graphs underlying the start and target configuration -- we require that these graphs are spannable by a forest of full binary trees (SFFBT). We use our assumption to obtain efficient MSR algorithms for unit discs and 2D grid settings. Notably, our assumption does not require separation between start/target positions, which is a standard requirement in efficient and complete MRMP algorithms. Instead, we (implicitly) require separation between $\textit{groups}$ of these positions, thereby pushing the boundary of efficiently solvable instances toward denser scenarios.