OpenRaiser/Intern-Atlas huggingface dataset:
Ensembling improves stability and power of feature selection for deep learning models
Venue: arXiv cs.LG 2022
Year: 2022

With the growing adoption of deep learning models in different real-world domains, including computational biology, it is often necessary to understand which data features are essential for the model's decision. Despite extensive recent efforts to define different feature importance metrics for deep learning models, we identified that inherent stochasticity in the design and training of deep learning models makes commonly used feature importance scores unstable. This results in varied explanations or selections of different features across different runs of the model. We demonstrate how the signal strength of features and correlation among features directly contribute to this instability. To address this instability, we explore the ensembling of feature importance scores of models across different epochs and find that this simple approach can substantially address this issue. For example, we consider knockoff inference as they allow feature selection with statistical guarantees. We discover considerable variability in selected features in different epochs of deep learning training, and the best selection of features doesn't necessarily occur at the lowest validation loss, the conventional approach to determine the best model. As such, we present a framework to combine the feature importance of trained models across different hyperparameter settings and epochs, and instead of selecting features from one best model, we perform an ensemble of feature importance scores from numerous good models. Across the range of experiments in simulated and various real-world datasets, we demonstrate that the proposed framework consistently improves the power of feature selection.
Belief propagation generalizes backpropagation
Venue: arXiv cs.AI 2022
Year: 2022

The two most important algorithms in artificial intelligence are backpropagation and belief propagation. In spite of their importance, the connection between them is poorly characterized. We show that when an input to backpropagation is converted into an input to belief propagation so that (loopy) belief propagation can be run on it, then the result of belief propagation encodes the result of backpropagation; thus backpropagation is recovered as a special case of belief propagation. In other words, we prove for apparently the first time that belief propagation generalizes backpropagation. Our analysis is a theoretical contribution, which we motivate with the expectation that it might reconcile our understandings of each of these algorithms, and serve as a guide to engineering researchers seeking to improve the behavior of systems that use one or the other.
iCTGAN--An Attack Mitigation Technique for Random-vector Attack on Accelerometer-based Gait Authentication Systems
Venue: arXiv cs.CR 2022
Year: 2022

A recent study showed that commonly (vanilla) studied implementations of accelerometer-based gait authentication systems ($v$ABGait) are susceptible to random-vector attack. The same study proposed a beta noise-assisted implementation ($β$ABGait) to mitigate the attack. In this paper, we assess the effectiveness of the random-vector attack on both $v$ABGait and $β$ABGait using three accelerometer-based gait datasets. In addition, we propose $i$ABGait, an alternative implementation of ABGait, which uses a Conditional Tabular Generative Adversarial Network. Then we evaluate $i$ABGait's resilience against the traditional zero-effort and random-vector attacks. The results show that $i$ABGait mitigates the impact of the random-vector attack to a reasonable extent and outperforms $β$ABGait in most experimental settings.
Convex synthesis and verification of control-Lyapunov and barrier functions with input constraints
Venue: arXiv cs.RO 2022
Year: 2022

Control Lyapunov functions (CLFs) and control barrier functions (CBFs) are widely used tools for synthesizing controllers subject to stability and safety constraints. Paired with online optimization, they provide stabilizing control actions that satisfy input constraints and avoid unsafe regions of state-space. Designing CLFs and CBFs with rigorous performance guarantees is computationally challenging. To certify existence of control actions, current techniques not only design a CLF/CBF, but also a nominal controller. This can make the synthesis task more expensive, and performance estimation more conservative. In this work, we characterize polynomial CLFs/CBFs using sum-of-squares conditions, which can be directly certified using convex optimization. This yields a CLF and CBF synthesis technique that does not rely on a nominal controller. We then present algorithms for iteratively enlarging estimates of the stabilizable and safe regions. We demonstrate our algorithms on a 2D toy system, a pendulum and a quadrotor.
No Selection Lemma for Empty Triangles
Venue: arXiv cs.CG 2022
Year: 2022

Let $S$ be a set of $n$ points in general position in the plane. The Second Selection Lemma states that for any family of $Θ(n^3)$ triangles spanned by $S$, there exists a point of the plane that lies in a constant fraction of them. For families of $Θ(n^{3-α})$ triangles, with $0\le α\le 1$, there might not be a point in more than $Θ(n^{3-2α})$ of those triangles. An empty triangle of $S$ is a triangle spanned by $S$ not containing any point of $S$ in its interior. Bárány conjectured that there exist an edge spanned by $S$ that is incident to a super constant number of empty triangles of $S$. The number of empty triangles of $S$ might be $O(n^2)$; in such a case, on average, every edge spanned by $S$ is incident to a constant number of empty triangles. The conjecture of Bárány suggests that for the class of empty triangles the above upper bound might not hold. In this paper we show that, somewhat surprisingly, the above upper bound does in fact hold for empty triangles. Specifically, we show that for any integer $n$ and real number $0\leq α\leq 1$ there exists a point set of size $n$ with $Θ(n^{3-α})$ empty triangles such that any point of the plane is only in $O(n^{3-2α})$ empty triangles.
Automated Security Analysis of Exposure Notification Systems
Venue: arXiv cs.CR 2022
Year: 2022

We present the first formal analysis and comparison of the security of the two most widely deployed exposure notification systems, ROBERT and the Google and Apple Exposure Notification (GAEN) framework. ROBERT is the most popular instalment of the centralised approach to exposure notification, in which the risk score is computed by a central server. GAEN, in contrast, follows the decentralised approach, where the user's phone calculates the risk. The relative merits of centralised and decentralised systems have proven to be a controversial question. The majority of the previous analyses have focused on the privacy implications of these systems, ours is the first formal analysis to evaluate the security of the deployed systems -- the absence of false risk alerts. We model the French deployment of ROBERT and the most widely deployed GAEN variant, Germany's Corona-Warn-App. We isolate the precise conditions under which these systems prevent false alerts. We determine exactly how an adversary can subvert the system via network and Bluetooth sniffing, database leakage or the compromise of phones, back-end systems and health authorities. We also investigate the security of the original specification of the DP3T protocol, in order to identify gaps between the proposed scheme and its ultimate deployment. We find a total of 27 attack patterns, including many that distinguish the centralised from the decentralised approach, as well as attacks on the authorisation procedure that differentiate all three protocols. Our results suggest that ROBERT's centralised design is more vulnerable against both opportunistic and highly resourced attackers trying to perform mass-notification attacks.
Online Pen Testing
Venue: arXiv cs.DS 2022
Year: 2022

We study a "pen testing" problem, in which we are given $n$ pens with unknown amounts of ink $X_1, X_2, \ldots, X_n$, and we want to choose a pen with the maximum amount of remaining ink in it. The challenge is that we cannot access each $X_i$ directly; we only get to write with the $i$-th pen until either a certain amount of ink is used, or the pen runs out of ink. In both cases, this testing reduces the remaining ink in the pen and thus the utility of selecting it. Despite this significant lack of information, we show that it is possible to approximately maximize our utility up to an $O(\log n)$ factor. Formally, we consider two different setups: the "prophet" setting, in which each $X_i$ is independently drawn from some distribution $\mathcal{D}_i$, and the "secretary" setting, in which $(X_i)_{i=1}^n$ is a random permutation of arbitrary $a_1, a_2, \ldots, a_n$. We derive the optimal competitive ratios in both settings up to constant factors. Our algorithms are surprisingly robust: (1) In the prophet setting, we only require one sample from each $\mathcal{D}_i$, rather than a full description of the distribution; (2) In the secretary setting, the algorithm also succeeds under an arbitrary permutation, if an estimate of the maximum $a_i$ is given. Our techniques include a non-trivial online sampling scheme from a sequence with an unknown length, as well as the construction of a hard, non-uniform distribution over permutations. Both might be of independent interest. We also highlight some immediate open problems and discuss several directions for future research.
Probing of Quantitative Values in Abstractive Summarization Models
Venue: arXiv cs.CL 2022
Year: 2022

Abstractive text summarization has recently become a popular approach, but data hallucination remains a serious problem, including with quantitative data. We propose a set of probing tests to evaluate the efficacy of abstract summarization models' modeling of quantitative values found in the input text. Our results show that in most cases, the encoders of recent SOTA-performing models struggle to provide embeddings that adequately represent quantitative values in the input compared to baselines, and in particular, they outperform random representations in some, but surprisingly not all, cases. Under our assumptions, this suggests that the encoder's performance contributes to the quantity hallucination problem. One model type in particular, DistilBART-CDM, was observed to underperform randomly initialized representations for several experiments, and performance versus BERT suggests that standard pretraining and fine-tuning approaches for the summarization task may play a role in underperformance for some encoders.
Evolution is Still Good: Theoretical Analysis of Evolutionary Algorithms on General Cover Problems
Venue: arXiv cs.NE 2022
Year: 2022

Theoretical studies on evolutionary algorithms have developed vigorously in recent years. Many such algorithms have theoretical guarantees in both running time and approximation ratio. Some approximation mechanism seems to be inherently embedded in many evolutionary algorithms. In this paper, we identify such a relation by proposing a unified analysis framework for a generalized simple multi-objective evolutionary algorithm (GSEMO), and apply it on a minimum weight general cover problem. For a wide range of problems (including the the minimum submodular cover problem in which the submodular function is real-valued, and the minimum connected dominating set problem for which the potential function is non-submodular), GSEMO yields asymptotically tight approximation ratios in expected polynomial time.
Multipod Convolutional Network
Venue: arXiv cs.CV 2022
Year: 2022

In this paper, we introduce a convolutional network which we call MultiPodNet consisting of a combination of two or more convolutional networks which process the input image in parallel to achieve the same goal. Output feature maps of parallel convolutional networks are fused at the fully connected layer of the network. We experimentally observed that three parallel pod networks (TripodNet) produce the best results in commonly used object recognition datasets. Baseline pod networks can be of any type. In this paper, we use ResNets as baseline networks and their inputs are augmented image patches. The number of parameters of the TripodNet is about three times that of a single ResNet. We train the TripodNet using the standard backpropagation type algorithms. In each individual ResNet, parameters are initialized with different random numbers during training. The TripodNet achieved state-of-the-art performance on CIFAR-10 and ImageNet datasets. For example, it improved the accuracy of a single ResNet from 91.66% to 92.47% under the same training process on the CIFAR-10 dataset.
Combined Dynamic Virtual Spatiotemporal Graph Mapping for Traffic Prediction
Venue: arXiv cs.LG 2022
Year: 2022

The continuous expansion of the urban construction scale has recently contributed to the demand for the dynamics of traffic intersections that are managed, making adaptive modellings become a hot topic. Existing deep learning methods are powerful to fit complex heterogeneous graphs. However, they still have drawbacks, which can be roughly classified into two categories, 1) spatiotemporal async-modelling approaches separately consider temporal and spatial dependencies, resulting in weak generalization and large instability while aggregating; 2) spatiotemporal sync-modelling is hard to capture long-term temporal dependencies because of the local receptive field. In order to overcome above challenges, a \textbf{C}ombined \textbf{D}ynamic \textbf{V}irtual spatiotemporal \textbf{G}raph \textbf{M}apping \textbf{(CDVGM)} is proposed in this work. The contributions are the following: 1) a dynamic virtual graph Laplacian ($DVGL$) is designed, which considers both the spatial signal passing and the temporal features simultaneously; 2) the Long-term Temporal Strengthen model ($LT^2S$) for improving the stability of time series forecasting; Extensive experiments demonstrate that CDVGM has excellent performances of fast convergence speed and low resource consumption and achieves the current SOTA effect in terms of both accuracy and generalization. The code is available at \hyperlink{https://github.com/Dandelionym/CDVGM.}{https://github.com/Dandelionym/CDVGM.}
Deep Spatial Domain Generalization
Venue: arXiv cs.LG 2022
Year: 2022

Spatial autocorrelation and spatial heterogeneity widely exist in spatial data, which make the traditional machine learning model perform badly. Spatial domain generalization is a spatial extension of domain generalization, which can generalize to unseen spatial domains in continuous 2D space. Specifically, it learns a model under varying data distributions that generalizes to unseen domains. Although tremendous success has been achieved in domain generalization, there exist very few works on spatial domain generalization. The advancement of this area is challenged by: 1) Difficulty in characterizing spatial heterogeneity, and 2) Difficulty in obtaining predictive models for unseen locations without training data. To address these challenges, this paper proposes a generic framework for spatial domain generalization. Specifically, We develop the spatial interpolation graph neural network that handles spatial data as a graph and learns the spatial embedding on each node and their relationships. The spatial interpolation graph neural network infers the spatial embedding of an unseen location during the test phase. Then the spatial embedding of the target location is used to decode the parameters of the downstream-task model directly on the target location. Finally, extensive experiments on thirteen real-world datasets demonstrate the proposed method's strength.
ScrollTest: Evaluating Scrolling Speed and Accuracy
Venue: arXiv cs.HC 2022
Year: 2022

Scrolling is an essential interaction technique enabling users to display previously off-screen content. Existing evaluation models for scrolling are often entangled with the selection of content, e.g., when scrolling on the phone for reading. Furthermore, some evaluation models overlook whether the user knows the target position. We have developed ScrollTest, a general-purpose evaluation tool for scrolling speed and accuracy that avoids the need for selection. We tested it across four dimensions: 11 different scrolling techniques/devices, 5 frame heights, 13 scrolling distances, and 2 scrolling conditions (i.e., with or without knowing the target position). The results show that flicking and two-finger scrolling are the fastest; flicking is also relatively precise for scrolling to targets already onscreen, but pressing arrow buttons on the scrollbar is the most accurate for scrolling to nearby targets. Mathematical models of scrolling are highly linear when the target position is unknown but like Fitts' law when known.
Dual Gradient Descent EMF-Aware MU-MIMO Beamforming in RIS-Aided 6G Networks
Venue: arXiv cs.IT 2022
Year: 2022

Reconfigurable Intelligent Surface (RIS) is one of the key technologies for the upcoming 6th Generation (6G) communications, which can improve the signal strength at the receivers by adding artificial propagation paths. In the context of Downlink (DL) Multi-User Multiple-Input Multiple-Output (MU-MIMO) communications, designing an appropriate Beamforming (BF) scheme to take full advantage of this reconfigured propagation environment and improve the network capacity is a major challenge. Due to the spatial dimension provided by MIMO systems, independent data streams can be transmitted to multiple users simultaneously on the same radio resources. It is important to note that serving the same subset of users over a period of time may lead to undesired areas where the average Electromagnetic Field Exposure (EMFE) exceeds regulatory limits. To address this challenge, in this paper, we propose a Dual Gradient Descent (Dual-GD)-based Electromagnetic Field (EMF)-aware MU-MIMO BF scheme that aims to optimize the overall capacity under EMFE constraints in RIS-aided 6G cellular networks.
Hierarchical reinforcement learning for in-hand robotic manipulation using Davenport chained rotations
Venue: arXiv cs.RO 2022
Year: 2022

End-to-end reinforcement learning techniques are among the most successful methods for robotic manipulation tasks. However, the training time required to find a good policy capable of solving complex tasks is prohibitively large. Therefore, depending on the computing resources available, it might not be feasible to use such techniques. The use of domain knowledge to decompose manipulation tasks into primitive skills, to be performed in sequence, could reduce the overall complexity of the learning problem, and hence reduce the amount of training required to achieve dexterity. In this paper, we propose the use of Davenport chained rotations to decompose complex 3D rotation goals into a concatenation of a smaller set of more simple rotation skills. State-of-the-art reinforcement-learning-based methods can then be trained using less overall simulated experience. We compare its performance with the popular Hindsight Experience Replay method, trained in an end-to-end fashion using the same amount of experience in a simulated robotic hand environment. Despite a general decrease in performance of the primitive skills when being sequentially executed, we find that decomposing arbitrary 3D rotations into elementary rotations is beneficial when computing resources are limited, obtaining increases of success rates of approximately 10% on the most complex 3D rotations with respect to the success rates obtained by HER trained in an end-to-end fashion, and increases of success rates between 20% and 40% on the most simple rotations.
Dancing with the Unexpected and Beyond: The Use of AI Assistance in Design Fiction Creation
Venue: arXiv cs.HC 2022
Year: 2022

The creation process of design fiction is going participatory and inclusive with non experts. Recognizing the potential of artificial intelligence in creativity support, we explore the use of AI assistance in creating design fiction. This investigation is based on a workshop on future work in 2040 with Chinese youth. We look into fiction quality, participants experiences with the AI agent, and their ways of incorporating those texts into writing. Our findings show that human writers while responding to messy and unexpected AI-generated texts, can elevate the richness and creativity in writing and initiate joyful and inspirational interactions. Furthermore, for the design of AI assistance in creativity support, we suggest two implications of enhancing interactional quality between human and AI and prompt programming. Our study indicates the potential of applying design fiction outside the design context using a more inclusive approach for future speculation with critical reflection on technology.
Concepts and Experiments on Psychoanalysis Driven Computing
Venue: arXiv cs.CL 2022
Year: 2022

This research investigates the effective incorporation of the human factor and user perception in text-based interactive media. In such contexts, the reliability of user texts is often compromised by behavioural and emotional dimensions. To this end, several attempts have been made in the state of the art, to introduce psychological approaches in such systems, including computational psycholinguistics, personality traits and cognitive psychology methods. In contrast, our method is fundamentally different since we employ a psychoanalysis-based approach; in particular, we use the notion of Lacanian discourse types, to capture and deeply understand real (possibly elusive) characteristics, qualities and contents of texts, and evaluate their reliability. As far as we know, this is the first time computational methods are systematically combined with psychoanalysis. We believe such psychoanalytic framework is fundamentally more effective than standard methods, since it addresses deeper, quite primitive elements of human personality, behaviour and expression which usually escape methods functioning at "higher", conscious layers. In fact, this research is a first attempt to form a new paradigm of psychoanalysis-driven interactive technologies, with broader impact and diverse applications. To exemplify this generic approach, we apply it to the case-study of fake news detection; we first demonstrate certain limitations of the well-known Myers-Briggs Type Indicator (MBTI) personality type method, and then propose and evaluate our new method of analysing user texts and detecting fake news based on the Lacanian discourses psychoanalytic approach.
Information Removal at the bottleneck in Deep Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

Deep learning models are nowadays broadly deployed to solve an incredibly large variety of tasks. Commonly, leveraging over the availability of "big data", deep neural networks are trained as black-boxes, minimizing an objective function at its output. This however does not allow control over the propagation of some specific features through the model, like gender or race, for solving some an uncorrelated task. This raises issues either in the privacy domain (considering the propagation of unwanted information) and of bias (considering that these features are potentially used to solve the given task). In this work we propose IRENE, a method to achieve information removal at the bottleneck of deep neural networks, which explicitly minimizes the estimated mutual information between the features to be kept ``private'' and the target. Experiments on a synthetic dataset and on CelebA validate the effectiveness of the proposed approach, and open the road towards the development of approaches guaranteeing information removal in deep neural networks.