OpenRaiser/Intern-Atlas huggingface dataset:
Correcting one error in channels with feedback
Venue: arXiv cs.IT 2023
Year: 2023

We address the problem of correcting a single error in an arbitrary discrete memoryless channel with error-free instantaneous feedback. For the case of a one-time feedback, we propose a method for constructing optimal transmission strategies. The obtained result allows us to prove that for a binary channel, two feedbacks are sufficient to transmit the same number of messages as in the case of complete feedback. We also apply the developed techniques to a binary asymmetric channel to construct transmission strategies for small lengths.
NODAGS-Flow: Nonlinear Cyclic Causal Structure Learning
Venue: arXiv cs.LG 2023
Year: 2023

Learning causal relationships between variables is a well-studied problem in statistics, with many important applications in science. However, modeling real-world systems remain challenging, as most existing algorithms assume that the underlying causal graph is acyclic. While this is a convenient framework for developing theoretical developments about causal reasoning and inference, the underlying modeling assumption is likely to be violated in real systems, because feedback loops are common (e.g., in biological systems). Although a few methods search for cyclic causal models, they usually rely on some form of linearity, which is also limiting, or lack a clear underlying probabilistic model. In this work, we propose a novel framework for learning nonlinear cyclic causal graphical models from interventional data, called NODAGS-Flow. We perform inference via direct likelihood optimization, employing techniques from residual normalizing flows for likelihood estimation. Through synthetic experiments and an application to single-cell high-content perturbation screening data, we show significant performance improvements with our approach compared to state-of-the-art methods with respect to structure recovery and predictive performance.
Instance-based Explanations for Gradient Boosting Machine Predictions with AXIL Weights
Venue: arXiv cs.LG 2023
Year: 2023

We show that regression predictions from linear and tree-based models can be represented as linear combinations of target instances in the training data. This also holds for models constructed as ensembles of trees, including Random Forests and Gradient Boosting Machines. The weights used in these linear combinations are measures of instance importance, complementing existing measures of feature importance, such as SHAP and LIME. We refer to these measures as AXIL weights (Additive eXplanations with Instance Loadings). Since AXIL weights are additive across instances, they offer both local and global explanations. Our work contributes to the broader effort to make machine learning predictions more interpretable and explainable.
Unsupervised High Impedance Fault Detection Using Autoencoder and Principal Component Analysis
Venue: arXiv cs.LG 2023
Year: 2023

Detection of high impedance faults (HIF) has been one of the biggest challenges in the power distribution network. The low current magnitude and diverse characteristics of HIFs make them difficult to be detected by over-current relays. Recently, data-driven methods based on machine learning models are gaining popularity in HIF detection due to their capability to learn complex patterns from data. Most machine learning-based detection methods adopt supervised learning techniques to distinguish HIFs from normal load conditions by performing classifications, which rely on a large amount of data collected during HIF. However, measurements of HIF are difficult to acquire in the real world. As a result, the reliability and generalization of the classification methods are limited when the load profiles and faults are not present in the training data. Consequently, this paper proposes an unsupervised HIF detection framework using the autoencoder and principal component analysis-based monitoring techniques. The proposed fault detection method detects the HIF by monitoring the changes in correlation structure within the current waveforms that are different from the normal loads. The performance of the proposed HIF detection method is tested using real data collected from a 4.16 kV distribution system and compared with results from a commercially available solution for HIF detection. The numerical results demonstrate that the proposed method outperforms the commercially available HIF detection technique while maintaining high security by not falsely detecting during load conditions.
Sum-Rate Maximization in Active RIS-Assisted Multi-Antenna WPCN
Venue: arXiv cs.IT 2023
Year: 2023

In this paper, we propose an active reconfigurable intelligent surface (RIS) enabled hybrid relaying scheme for a multi-antenna wireless powered communication network (WPCN), where the active RIS is employed to assist both wireless energy transfer (WET) from the power station (PS) to energy-constrained users and wireless information transmission (WIT) from users to the receiving station (RS). For further performance enhancement, we propose to employ both transmit beamforming at the PS and receive beamforming at the RS. We formulate a sum-rate maximization problem by jointly optimizing the RIS phase shifts and amplitude reflection coefficients for both the WET and the WIT, transmit and receive beamforming vectors, and network resource allocation. To solve this non-convex problem, we propose an efficient alternating optimization algorithm with linear minimum mean squared error criterion, semi-definite relaxation (SDR) and successive convex approximation techniques. Specifically, the tightness of applying the SDR is proved. Simulation results demonstrate that our proposed scheme with 10 reflecting elements (REs) and 4 antennas can achieve 17.78% and 415.48% performance gains compared to the single-antenna scheme with 10 REs and passive RIS scheme with 100 REs, respectively.
Exact and Heuristic Approaches to Speeding Up the MSM Time Series Distance Computation
Venue: arXiv cs.DS 2023
Year: 2023

The computation of the distance of two time series is time-consuming for any elastic distance function that accounts for misalignments. Among those functions, DTW is the most prominent. However, a recent extensive evaluation has shown that the move-split merge (MSM) metric is superior to DTW regarding the analytical accuracy of the 1-NN classifier. Unfortunately, the running time of the standard dynamic programming algorithm for MSM distance computation is $Ω(n^2)$, where $n$ is the length of the longest time series. In this paper, we provide approaches to reducing the cost of MSM distance computations by using lower and upper bounds for early pruning paths in the underlying dynamic programming table. For the case of one time series being a constant, we present a linear-time algorithm. In addition, we propose new linear-time heuristics and adapt heuristics known from DTW to computing the MSM distance. One heuristic employs the metric property of MSM and the previously introduced linear-time algorithm. Our experimental studies demonstrate substantial speed-ups in our approaches compared to previous MSM algorithms. In particular, the running time for MSM is faster than a state-of-the-art DTW distance computation for a majority of the popular UCR data sets.
A Distance-Geometric Method for Recovering Robot Joint Angles From an RGB Image
Venue: arXiv cs.RO 2023
Year: 2023

Autonomous manipulation systems operating in domains where human intervention is difficult or impossible (e.g., underwater, extraterrestrial or hazardous environments) require a high degree of robustness to sensing and communication failures. Crucially, motion planning and control algorithms require a stream of accurate joint angle data provided by joint encoders, the failure of which may result in an unrecoverable loss of functionality. In this paper, we present a novel method for retrieving the joint angles of a robot manipulator using only a single RGB image of its current configuration, opening up an avenue for recovering system functionality when conventional proprioceptive sensing is unavailable. Our approach, based on a distance-geometric representation of the configuration space, exploits the knowledge of a robot's kinematic model with the goal of training a shallow neural network that performs a 2D-to-3D regression of distances associated with detected structural keypoints. It is shown that the resulting Euclidean distance matrix uniquely corresponds to the observed configuration, where joint angles can be recovered via multidimensional scaling and a simple inverse kinematics procedure. We evaluate the performance of our approach on real RGB images of a Franka Emika Panda manipulator, showing that the proposed method is efficient and exhibits solid generalization ability. Furthermore, we show that our method can be easily combined with a dense refinement technique to obtain superior results.
On the Forces of Driver Distraction: Explainable Predictions for the Visual Demand of In-Vehicle Touchscreen Interactions
Venue: arXiv cs.HC 2023
Year: 2023

With modern infotainment systems, drivers are increasingly tempted to engage in secondary tasks while driving. Since distracted driving is already one of the main causes of fatal accidents, in-vehicle touchscreen Human-Machine Interfaces (HMIs) must be as little distracting as possible. To ensure that these systems are safe to use, they undergo elaborate and expensive empirical testing, requiring fully functional prototypes. Thus, early-stage methods informing designers about the implication their design may have on driver distraction are of great value. This paper presents a machine learning method that, based on anticipated usage scenarios, predicts the visual demand of in-vehicle touchscreen interactions and provides local and global explanations of the factors influencing drivers' visual attention allocation. The approach is based on large-scale natural driving data continuously collected from production line vehicles and employs the SHapley Additive exPlanation (SHAP) method to provide explanations leveraging informed design decisions. Our approach is more accurate than related work and identifies interactions during which long glances occur with 68 % accuracy and predicts the total glance duration with a mean error of 2.4 s. Our explanations replicate the results of various recent studies and provide fast and easily accessible insights into the effect of UI elements, driving automation, and vehicle speed on driver distraction. The system can not only help designers to evaluate current designs but also help them to better anticipate and understand the implications their design decisions might have on future designs.
Anaphora Resolution in Dialogue: System Description (CODI-CRAC 2022 Shared Task)
Venue: arXiv cs.CL 2023
Year: 2023

We describe three models submitted for the CODI-CRAC 2022 shared task. To perform identity anaphora resolution, we test several combinations of the incremental clustering approach based on the Workspace Coreference System (WCS) with other coreference models. The best result is achieved by adding the ''cluster merging'' version of the coref-hoi model, which brings up to 10.33% improvement 1 over vanilla WCS clustering. Discourse deixis resolution is implemented as multi-task learning: we combine the learning objective of corefhoi with anaphor type classification. We adapt the higher-order resolution model introduced in Joshi et al. (2019) for bridging resolution given gold mentions and anaphors.
Playing hide and seek: tackling in-store picking operations while improving customer experience
Venue: arXiv cs.LG 2023
Year: 2023

The evolution of the retail business presents new challenges and raises pivotal questions on how to reinvent stores and supply chains to meet the growing demand of the online channel. One of the recent measures adopted by omnichannel retailers is to address the growth of online sales using in-store picking, which allows serving online orders using existing assets. However, it comes with the downside of harming the offline customer experience. To achieve picking policies adapted to the dynamic customer flows of a retail store, we formalize a new problem called Dynamic In-store Picker Routing Problem (diPRP). In this relevant problem - diPRP - a picker tries to pick online orders while minimizing customer encounters. We model the problem as a Markov Decision Process (MDP) and solve it using a hybrid solution approach comprising mathematical programming and reinforcement learning components. Computational experiments on synthetic instances suggest that the algorithm converges to efficient policies. Furthermore, we apply our approach in the context of a large European retailer to assess the results of the proposed policies regarding the number of orders picked and customers encountered. Our work suggests that retailers should be able to scale the in-store picking of online orders without jeopardizing the experience of offline customers. The policies learned using the proposed solution approach reduced the number of customer encounters by more than 50% when compared to policies solely focused on picking orders. Thus, to pursue omnichannel strategies that adequately trade-off operational efficiency and customer experience, retailers cannot rely on actual simplistic picking strategies, such as choosing the shortest possible route.
Domain Generalization via Ensemble Stacking for Face Presentation Attack Detection
Venue: arXiv cs.CV 2023
Year: 2023

Face Presentation Attack Detection (PAD) plays a pivotal role in securing face recognition systems against spoofing attacks. Although great progress has been made in designing face PAD methods, developing a model that can generalize well to unseen test domains remains a significant challenge. Moreover, due to different types of spoofing attacks, creating a dataset with a sufficient number of samples for training deep neural networks is a laborious task. This work proposes a comprehensive solution that combines synthetic data generation and deep ensemble learning to enhance the generalization capabilities of face PAD. Specifically, synthetic data is generated by blending a static image with spatiotemporal encoded images using alpha composition and video distillation. This way, we simulate motion blur with varying alpha values, thereby generating diverse subsets of synthetic data that contribute to a more enriched training set. Furthermore, multiple base models are trained on each subset of synthetic data using stacked ensemble learning. This allows the models to learn complementary features and representations from different synthetic subsets. The meta-features generated by the base models are used as input to a new model called the meta-model. The latter combines the predictions from the base models, leveraging their complementary information to better handle unseen target domains and enhance the overall performance. Experimental results on four datasets demonstrate low half total error rates (HTERs) on three benchmark datasets: CASIA-MFSD (8.92%), MSU-MFSD (4.81%), and OULU-NPU (6.70%). The approach shows potential for advancing presentation attack detection by utilizing large-scale synthetic data and the meta-model.
Beyond spectral gap (extended): The role of the topology in decentralized learning
Venue: arXiv cs.LG 2023
Year: 2023

In data-parallel optimization of machine learning models, workers collaborate to improve their estimates of the model: more accurate gradients allow them to use larger learning rates and optimize faster. In the decentralized setting, in which workers communicate over a sparse graph, current theory fails to capture important aspects of real-world behavior. First, the `spectral gap' of the communication graph is not predictive of its empirical performance in (deep) learning. Second, current theory does not explain that collaboration enables larger learning rates than training alone. In fact, it prescribes smaller learning rates, which further decrease as graphs become larger, failing to explain convergence dynamics in infinite graphs. This paper aims to paint an accurate picture of sparsely-connected distributed optimization. We quantify how the graph topology influences convergence in a quadratic toy problem and provide theoretical results for general smooth and (strongly) convex objectives. Our theory matches empirical observations in deep learning, and accurately describes the relative merits of different graph topologies. This paper is an extension of the conference paper by Vogels et. al. (2022). Code: https://github.com/epfml/topology-in-decentralized-learning.
Representable and diagonally representable weakening relation algebras
Venue: arXiv cs.LO 2023
Year: 2023

A binary relation defined on a poset is a weakening relation if the partial order acts as a both-sided compositional identity. This is motivated by the weakening rule in sequent calculi and closely related to models of relevance logic. For a fixed poset the collection of weakening relations is a subreduct of the full relation algebra on the underlying set of the poset. We present a two-player game for the class of representable weakening relation algebras akin to that for the class of representable relation algebras. This enables us to define classes of abstract weakening relation algebras that approximate the quasivariety of representable weakening relation algebras. We give explicit finite axiomatisations for some of these classes. We define the class of diagonally representable weakening relation algebras and prove that it is a discriminator variety. We also provide explicit representations for several small weakening relation algebras.
CA$^2$T-Net: Category-Agnostic 3D Articulation Transfer from Single Image
Venue: arXiv cs.CV 2023
Year: 2023

We present a neural network approach to transfer the motion from a single image of an articulated object to a rest-state (i.e., unarticulated) 3D model. Our network learns to predict the object's pose, part segmentation, and corresponding motion parameters to reproduce the articulation shown in the input image. The network is composed of three distinct branches that take a shared joint image-shape embedding and is trained end-to-end. Unlike previous methods, our approach is independent of the topology of the object and can work with objects from arbitrary categories. Our method, trained with only synthetic data, can be used to automatically animate a mesh, infer motion from real images, and transfer articulation to functionally similar but geometrically distinct 3D models at test time.
Skip-Attention: Improving Vision Transformers by Paying Less Attention
Venue: arXiv cs.CV 2023
Year: 2023

This work aims to improve the efficiency of vision transformers (ViT). While ViTs use computationally expensive self-attention operations in every layer, we identify that these operations are highly correlated across layers -- a key redundancy that causes unnecessary computations. Based on this observation, we propose SkipAt, a method to reuse self-attention computation from preceding layers to approximate attention at one or more subsequent layers. To ensure that reusing self-attention blocks across layers does not degrade the performance, we introduce a simple parametric function, which outperforms the baseline transformer's performance while running computationally faster. We show the effectiveness of our method in image classification and self-supervised learning on ImageNet-1K, semantic segmentation on ADE20K, image denoising on SIDD, and video denoising on DAVIS. We achieve improved throughput at the same-or-higher accuracy levels in all these tasks.
A compositional game to fairly divide homogeneous cake
Venue: arXiv cs.GT 2023
Year: 2023

The central question in the game theory of cake-cutting is how to fairly distribute a finite resource among multiple players. Most research has focused on how to do this for a heterogeneous cake in a situation where the players do not have access to each other's valuation function, but I argue that even sharing homogeneous cake can have interesting mechanism design. Here, I introduce a new game, based on the compositional structure of iterated cake-cutting, that in the case of a homogeneous cake has a Nash equilibrium where each of $n$ players gets $1/n$ of the cake. Furthermore, the equilibrium distribution is the result of just $n-1$ cuts, so each player gets a contiguous piece of cake. Naive composition of the `I cut you choose' rule leads to an exponentially unfair cake distribution with a Gini-coefficient that approaches 1, and suffers from a high Price of Anarchy. This cost is completely eliminated by the proposed \textit{Biggest Player} rule for composition which achieves decentralised and asynchronous fairness at linear Robertson-Webb complexity. After introducing the game, proving the fairness of the equilibrium, and analysing the incentive structure, the game is implemented in Haskell and the Open Game engine to make the compositional structure explicit.
Giving life to robotic skins
Venue: arXiv cs.RO 2023
Year: 2023

The skin of humanoid robots often lacks human tactility and the inherent self-repair capability of biological tissues. Recently, researchers have grown a living, self-healing skin on a robot finger by subsequent culturing of human dermal and epidermal cells. Here, we highlight the significance of this study alongside challenges toward developing biohybrid robots equipped with sensate and adaptive living robotic skins.
Improving Self-Consistency in Underwater Mapping Through Laser-Based Loop Closure (Extended)
Venue: arXiv cs.RO 2023
Year: 2023

Accurate, self-consistent bathymetric maps are needed to monitor changes in subsea environments and infrastructure. These maps are increasingly collected by underwater vehicles, and mapping requires an accurate vehicle navigation solution. Commercial off-the-shelf (COTS) navigation solutions for underwater vehicles often rely on external acoustic sensors for localization, however survey-grade acoustic sensors are expensive to deploy and limit the range of the vehicle. Techniques from the field of simultaneous localization and mapping, particularly loop closures, can improve the quality of the navigation solution over dead-reckoning, but are difficult to integrate into COTS navigation systems. This work presents a method to improve the self-consistency of bathymetric maps by smoothly integrating loop-closure measurements into the state estimate produced by a commercial subsea navigation system. Integration is done using a white-noise-on-acceleration motion prior, without access to raw sensor measurements or proprietary models. Improvements in map self-consistency are shown for both simulated and experimental datasets, including a 3D scan of an underwater shipwreck in Wiarton, Ontario, Canada.
Sequentially Controlled Text Generation
Venue: arXiv cs.CL 2023
Year: 2023

While GPT-2 generates sentences that are remarkably human-like, longer documents can ramble and do not follow human-like writing structure. We study the problem of imposing structure on long-range text. We propose a novel controlled text generation task, sequentially controlled text generation, and identify a dataset, NewsDiscourse as a starting point for this task. We develop a sequential controlled text generation pipeline with generation and editing. We test different degrees of structural awareness and show that, in general, more structural awareness results in higher control-accuracy, grammaticality, coherency and topicality, approaching human-level writing performance.