OpenRaiser/Intern-Atlas huggingface dataset:
(Re)packing Equal Disks into Rectangle
Venue: arXiv cs.CG 2022
Year: 2022

The problem of packing of equal disks (or circles) into a rectangle is a fundamental geometric problem. (By a packing here we mean an arrangement of disks in a rectangle without overlapping.) We consider the following algorithmic generalization of the equal disk packing problem. In this problem, for a given packing of equal disks into a rectangle, the question is whether by changing positions of a small number of disks, we can allocate space for packing more disks. More formally, in the repacking problem, for a given set of $n$ equal disks packed into a rectangle and integers $k$ and $h$, we ask whether it is possible by changing positions of at most $h$ disks to pack $n+k$ disks. Thus the problem of packing equal disks is the special case of our problem with $n=h=0$. While the computational complexity of packing equal disks into a rectangle remains open, we prove that the repacking problem is NP-hard already for $h=0$. Our main algorithmic contribution is an algorithm that solves the repacking problem in time $(h+k)^{O(h+k)}\cdot |I|^{O(1)}$, where $I$ is the input size. That is, the problem is fixed-parameter tractable parameterized by $k$ and $h$.
Social Networks are Divulging Your Identity behind Crypto Addresses
Venue: arXiv cs.CR 2022
Year: 2022

Cryptocurrencies, such as Bitcoin and Ethereum, are becoming increasingly prevalent mainly due to their anonymity, decentralization, transparency, and security. However, the completely public ledger makes the trace and analysis of each account possible as long as the identity behind the public address is revealed. Theoretically, social networks could make that happen when addresses are posted on social network platforms using accounts containing personal information. To verify such a possibility, we have collected public data from two major platforms, i.e. Twitter and Reddit, aiming to find potential privacy leakage behind the ETH public address. In the end, an easy-to-use retrieval application is also built for a better illustration.
Minimum Path Cover in Parameterized Linear Time
Venue: arXiv cs.DS 2022
Year: 2022

A minimum path cover (MPC) of a directed acyclic graph (DAG) $G = (V,E)$ is a minimum-size set of paths that together cover all the vertices of the DAG. Computing an MPC is a basic polynomial problem, dating back to Dilworth's and Fulkerson's results in the 1950s. Since the size $k$ of an MPC (also known as the width) can be small in practical applications, research has also studied algorithms whose running time is parameterized on $k$. We obtain a new MPC parameterized algorithm for DAGs running in time $O(k^2|V| + |E|)$. Our algorithm is the first solving the problem in parameterized linear time. Additionally, we obtain an edge sparsification algorithm preserving the width of a DAG but reducing $|E|$ to less than $2|V|$. This algorithm runs in time $O(k^2|V|)$ and requires an MPC of a DAG as input, thus its total running time is the same as the running time of our MPC algorithm.
Features for the 0-1 knapsack problem based on inclusionwise maximal solutions
Venue: arXiv cs.DS 2022
Year: 2022

Decades of research on the 0-1 knapsack problem led to very efficient algorithms that are able to quickly solve large problem instances to optimality. This prompted researchers to also investigate whether relatively small problem instances exist that are hard for existing solvers and investigate which features characterize their hardness. Previously the authors proposed a new class of hard 0-1 knapsack problem instances and demonstrated that the properties of so-called inclusionwise maximal solutions (IMSs) can be important hardness indicators for this class. In the current paper, we formulate several new computationally challenging problems related to the IMSs of arbitrary 0-1 knapsack problem instances. Based on generalizations of previous work and new structural results about IMSs, we formulate polynomial and pseudopolynomial time algorithms for solving these problems. From this we derive a set of 14 computationally expensive features, which we calculate for two large datasets on a supercomputer in approximately 540 CPU-hours. We show that the proposed features contain important information related to the empirical hardness of a problem instance that was missing in earlier features from the literature by training machine learning models that can accurately predict the empirical hardness of a wide variety of 0-1 knapsack problem instances. Using the instance space analysis methodology, we also show that hard 0-1 knapsack problem instances are clustered together around a relatively dense region of the instance space and several features behave differently in the easy and hard parts of the instance space.
A Synthetic Dataset for 5G UAV Attacks Based on Observable Network Parameters
Venue: arXiv cs.NI 2022
Year: 2022

Synthetic datasets are beneficial for machine learning researchers due to the possibility of experimenting with new strategies and algorithms in the training and testing phases. These datasets can easily include more scenarios that might be costly to research with real data or can complement and, in some cases, replace real data measurements, depending on the quality of the synthetic data. They can also solve the unbalanced data problem, avoid overfitting, and can be used in training while testing can be done with real data. In this paper, we present, to the best of our knowledge, the first synthetic dataset for Unmanned Aerial Vehicle (UAV) attacks in 5G and beyond networks based on the following key observable network parameters that indicate power levels: the Received Signal Strength Indicator (RSSI) and the Signal to Interference-plus-Noise Ratio (SINR). The main objective of this data is to enable deep network development for UAV communication security. Especially, for algorithm development or the analysis of time-series data applied to UAV attack recognition. Our proposed dataset provides insights into network functionality when static or moving UAV attackers target authenticated UAVs in an urban environment. The dataset also considers the presence and absence of authenticated terrestrial users in the network, which may decrease the deep networks ability to identify attacks. Furthermore, the data provides deeper comprehension of the metrics available in the 5G physical and MAC layers for machine learning and statistics research. The dataset will available at link archive-beta.ics.uci.edu
A Flexible MATLAB/Simulink Simulator for Robotic Floating-base Systems in Contact with the Ground
Venue: arXiv cs.RO 2022
Year: 2022

Physics simulators are widely used in robotics fields, from mechanical design to dynamic simulation, and controller design. This paper presents an open-source MATLAB/Simulink simulator for rigid-body articulated systems, including manipulators and floating-base robots. Thanks to MATLAB/Simulink features like MATLAB system classes and Simulink function blocks, the presented simulator combines a programmatic and block-based approach, resulting in a flexible design in the sense that different parts, including its physics engine, robot-ground interaction model, and state evolution algorithm are simply accessible and editable. Moreover, through the use of Simulink dynamic mask blocks, the proposed simulation framework supports robot models integrating open-chain and closed-chain kinematics with any desired number of links interacting with the ground. The simulator can also integrate second-order actuator dynamics. Furthermore, the simulator benefits from a one-line installation and an easy-to-use Simulink interface.
Federated Multilingual Models for Medical Transcript Analysis
Venue: arXiv cs.CL 2022
Year: 2022

Federated Learning (FL) is a novel machine learning approach that allows the model trainer to access more data samples, by training the model across multiple decentralized data sources, while data access constraints are in place. Such trained models can achieve significantly higher performance beyond what can be done when trained on a single data source. As part of FL's promises, none of the training data is ever transmitted to any central location, ensuring that sensitive data remains local and private. These characteristics make FL perfectly suited for large-scale applications in healthcare, where a variety of compliance constraints restrict how data may be handled, processed, and stored. Despite the apparent benefits of federated learning, the heterogeneity in the local data distributions pose significant challenges, and such challenges are even more pronounced in the case of multilingual data providers. In this paper we present a federated learning system for training a large-scale multi-lingual model suitable for fine-tuning on downstream tasks such as medical entity tagging. Our work represents one of the first such production-scale systems, capable of training across multiple highly heterogeneous data providers, and achieving levels of accuracy that could not be otherwise achieved by using central training with public data. Finally, we show that the global model performance can be further improved by a training step performed locally.
Deep Reinforcement Learning for IRS Phase Shift Design in Spatiotemporally Correlated Environments
Venue: arXiv cs.IT 2022
Year: 2022

The paper studies the problem of designing the Intelligent Reflecting Surface (IRS) phase shifters for Multiple Input Single Output (MISO) communication systems in spatiotemporally correlated channel environments, where the destination can move within a confined area. The objective is to maximize the expected sum of SNRs at the receiver over infinite time horizons. The problem formulation gives rise to a Markov Decision Process (MDP). We propose a deep actor-critic algorithm that accounts for channel correlations and destination motion by constructing the state representation to include the current position of the receiver and the phase shift values and receiver positions that correspond to a window of previous time steps. The channel variability induces high frequency components on the spectrum of the underlying value function. We propose the preprocessing of the critic's input with a Fourier kernel which enables stable value learning. Finally, we investigate the use of the destination SNR as a component of the designed MDP state, which is common practice in previous work. We provide empirical evidence that, when the channels are spatiotemporally correlated, the inclusion of the SNR in the state representation interacts with function approximation in ways that inhibit convergence.
Heart Abnormality Detection from Heart Sound Signals using MFCC Feature and Dual Stream Attention Based Network
Venue: arXiv cs.SD 2022
Year: 2022

Cardiovascular diseases are one of the leading cause of death in today's world and early screening of heart condition plays a crucial role in preventing them. The heart sound signal is one of the primary indicator of heart condition and can be used to detect abnormality in the heart. The acquisition of heart sound signal is non-invasive, cost effective and requires minimum equipment. But currently the detection of heart abnormality from heart sound signal depends largely on the expertise and experience of the physician. As such an automatic detection system for heart abnormality detection from heart sound signal can be a great asset for the people living in underdeveloped areas. In this paper we propose a novel deep learning based dual stream network with attention mechanism that uses both the raw heart sound signal and the MFCC features to detect abnormality in heart condition of a patient. The deep neural network has a convolutional stream that uses the raw heart sound signal and a recurrent stream that uses the MFCC features of the signal. The features from these two streams are merged together using a novel attention network and passed through the classification network. The model is trained on the largest publicly available dataset of PCG signal and achieves an accuracy of 87.11, sensitivity of 82.41, specificty of 91.8 and a MACC of 87.12.
Data-driven Real-time Short-term Prediction of Air Quality: Comparison of ES, ARIMA, and LSTM
Venue: arXiv cs.LG 2022
Year: 2022

Air pollution is a worldwide issue that affects the lives of many people in urban areas. It is considered that the air pollution may lead to heart and lung diseases. A careful and timely forecast of the air quality could help to reduce the exposure risk for affected people. In this paper, we use a data-driven approach to predict air quality based on historical data. We compare three popular methods for time series prediction: Exponential Smoothing (ES), Auto-Regressive Integrated Moving Average (ARIMA) and Long short-term memory (LSTM). Considering prediction accuracy and time complexity, our experiments reveal that for short-term air pollution prediction ES performs better than ARIMA and LSTM.
Data-Centric Debugging: mitigating model failures via targeted data collection
Venue: arXiv cs.CV 2022
Year: 2022

Deep neural networks can be unreliable in the real world when the training set does not adequately cover all the settings where they are deployed. Focusing on image classification, we consider the setting where we have an error distribution $\mathcal{E}$ representing a deployment scenario where the model fails. We have access to a small set of samples $\mathcal{E}_{sample}$ from $\mathcal{E}$ and it can be expensive to obtain additional samples. In the traditional model development framework, mitigating failures of the model in $\mathcal{E}$ can be challenging and is often done in an ad hoc manner. In this paper, we propose a general methodology for model debugging that can systemically improve model performance on $\mathcal{E}$ while maintaining its performance on the original test set. Our key assumption is that we have access to a large pool of weakly (noisily) labeled data $\mathcal{F}$. However, naively adding $\mathcal{F}$ to the training would hurt model performance due to the large extent of label noise. Our Data-Centric Debugging (DCD) framework carefully creates a debug-train set by selecting images from $\mathcal{F}$ that are perceptually similar to the images in $\mathcal{E}_{sample}$. To do this, we use the $\ell_2$ distance in the feature space (penultimate layer activations) of various models including ResNet, Robust ResNet and DINO where we observe DINO ViTs are significantly better at discovering similar images compared to Resnets. Compared to LPIPS, we find that our method reduces compute and storage requirements by 99.58\%. Compared to the baselines that maintain model performance on the test set, we achieve significantly (+9.45\%) improved results on the debug-heldout sets.
Audio Anti-spoofing Using a Simple Attention Module and Joint Optimization Based on Additive Angular Margin Loss and Meta-learning
Venue: arXiv cs.SD 2022
Year: 2022

Automatic speaker verification systems are vulnerable to a variety of access threats, prompting research into the formulation of effective spoofing detection systems to act as a gate to filter out such spoofing attacks. This study introduces a simple attention module to infer 3-dim attention weights for the feature map in a convolutional layer, which then optimizes an energy function to determine each neuron's importance. With the advancement of both voice conversion and speech synthesis technologies, unseen spoofing attacks are constantly emerging to limit spoofing detection system performance. Here, we propose a joint optimization approach based on the weighted additive angular margin loss for binary classification, with a meta-learning training framework to develop an efficient system that is robust to a wide range of spoofing attacks for model generalization enhancement. As a result, when compared to current state-of-the-art systems, our proposed approach delivers a competitive result with a pooled EER of 0.99% and min t-DCF of 0.0289.
Learning on Health Fairness and Environmental Justice via Interactive Visualization
Venue: arXiv cs.HC 2022
Year: 2022

This paper introduces an interactive visualization interface with a machine learning consensus analysis that enables the researchers to explore the impact of atmospheric and socioeconomic factors on COVID-19 clinical severity by employing multiple Recurrent Graph Neural Networks. We designed and implemented a visualization interface that leverages coordinated multi-views to support exploratory and predictive analysis of hospitalizations and other socio-geographic variables at multiple dimensions, simultaneously. By harnessing the strength of geometric deep learning, we build a consensus machine learning model to include knowledge from county-level records and investigate the complex interrelationships between global infectious disease, environment, and social justice. Additionally, we make use of unique NASA satellite-based observations which are not broadly used in the context of climate justice applications. Our current interactive interface focus on three US states (California, Pennsylvania, and Texas) to demonstrate its scientific value and presented three case studies to make qualitative evaluations.
A Tale of Two Cities: Data and Configuration Variances in Robust Deep Learning
Venue: arXiv cs.LG 2022
Year: 2022

Deep neural networks (DNNs), are widely used in many industries such as image recognition, supply chain, medical diagnosis, and autonomous driving. However, prior work has shown the high accuracy of a DNN model does not imply high robustness (i.e., consistent performances on new and future datasets) because the input data and external environment (e.g., software and model configurations) for a deployed model are constantly changing. Hence, ensuring the robustness of deep learning is not an option but a priority to enhance business and consumer confidence. Previous studies mostly focus on the data aspect of model variance. In this article, we systematically summarize DNN robustness issues and formulate them in a holistic view through two important aspects, i.e., data and software configuration variances in DNNs. We also provide a predictive framework to generate representative variances (counterexamples) by considering both data and configurations for robust learning through the lens of search-based optimization.
Listing 4-Cycles
Venue: arXiv cs.DS 2022
Year: 2022

In this note we present an algorithm that lists all $4$-cycles in a graph in time $\tilde{O}(\min(n^2,m^{4/3})+t)$ where $t$ is their number. Notably, this separates $4$-cycle listing from triangle-listing, since the latter has a $(\min(n^3,m^{3/2})+t)^{1-o(1)}$ lower bound under the $3$-SUM Conjecture. Our upper bound is conditionally tight because (1) $O(n^2,m^{4/3})$ is the best known bound for detecting if the graph has any $4$-cycle, and (2) it matches a recent $(\min(n^3,m^{3/2})+t)^{1-o(1)}$ $3$-SUM lower bound for enumeration algorithms. The latter lower bound was proved very recently by Abboud, Bringmann, and Fischer [arXiv, 2022] and independently by Jin and Xu [arXiv, 2022]. In an independent work, Jin and Xu [arXiv, 2022] also present an algorithm with the same time bound.
Clustering based opcode graph generation for malware variant detection
Venue: arXiv cs.CR 2022
Year: 2022

Malwares are the key means leveraged by threat actors in the cyber space for their attacks. There is a large array of commercial solutions in the market and significant scientific research to tackle the challenge of the detection and defense against malwares. At the same time, attackers also advance their capabilities in creating polymorphic and metamorphic malwares to make it increasingly challenging for existing solutions. To tackle this issue, we propose a methodology to perform malware detection and family attribution. The proposed methodology first performs the extraction of opcodes from malwares in each family and constructs their respective opcode graphs. We explore the use of clustering algorithms on the opcode graphs to detect clusters of malwares within the same malware family. Such clusters can be seen as belonging to different sub-family groups. Opcode graph signatures are built from each detected cluster. Hence, for each malware family, a group of signatures is generated to represent the family. These signatures are used to classify an unknown sample as benign or belonging to one the malware families. We evaluate our methodology by performing experiments on a dataset consisting of both benign files and malware samples belonging to a number of different malware families and comparing the results to existing approach.
$α$ DARTS Once More: Enhancing Differentiable Architecture Search by Masked Image Modeling
Venue: arXiv cs.CV 2022
Year: 2022

Differentiable architecture search (DARTS) has been a mainstream direction in automatic machine learning. Since the discovery that original DARTS will inevitably converge to poor architectures, recent works alleviate this by either designing rule-based architecture selection techniques or incorporating complex regularization techniques, abandoning the simplicity of the original DARTS that selects architectures based on the largest parametric value, namely $α$. Moreover, we find that all the previous attempts only rely on classification labels, hence learning only single modal information and limiting the representation power of the shared network. To this end, we propose to additionally inject semantic information by formulating a patch recovery approach. Specifically, we exploit the recent trending masked image modeling and do not abandon the guidance from the downstream tasks during the search phase. Our method surpasses all previous DARTS variants and achieves state-of-the-art results on CIFAR-10, CIFAR-100, and ImageNet without complex manual-designed strategies.
Language-Conditioned Reinforcement Learning to Solve Misunderstandings with Action Corrections
Venue: arXiv cs.LG 2022
Year: 2022

Human-to-human conversation is not just talking and listening. It is an incremental process where participants continually establish a common understanding to rule out misunderstandings. Current language understanding methods for intelligent robots do not consider this. There exist numerous approaches considering non-understandings, but they ignore the incremental process of resolving misunderstandings. In this article, we present a first formalization and experimental validation of incremental action-repair for robotic instruction-following based on reinforcement learning. To evaluate our approach, we propose a collection of benchmark environments for action correction in language-conditioned reinforcement learning, utilizing a synthetic instructor to generate language goals and their corresponding corrections. We show that a reinforcement learning agent can successfully learn to understand incremental corrections of misunderstood instructions.