OpenRaiser/Intern-Atlas huggingface dataset:
On Monte Carlo Tree Search for Weighted Vertex Coloring
Venue: arXiv cs.LG 2022
Year: 2022

This work presents the first study of using the popular Monte Carlo Tree Search (MCTS) method combined with dedicated heuristics for solving the Weighted Vertex Coloring Problem. Starting with the basic MCTS algorithm, we gradually introduce a number of algorithmic variants where MCTS is extended by various simulation strategies including greedy and local search heuristics. We conduct experiments on well-known benchmark instances to assess the value of each studied combination. We also provide empirical evidence to shed light on the advantages and limits of each strategy.
Separating Rule Discovery and Global Solution Composition in a Learning Classifier System
Venue: arXiv cs.LG 2022
Year: 2022

While utilization of digital agents to support crucial decision making is increasing, trust in suggestions made by these agents is hard to achieve. However, it is essential to profit from their application, resulting in a need for explanations for both the decision making process and the model. For many systems, such as common black-box models, achieving at least some explainability requires complex post-processing, while other systems profit from being, to a reasonable extent, inherently interpretable. We propose a rule-based learning system specifically conceptualised and, thus, especially suited for these scenarios. Its models are inherently transparent and easily interpretable by design. One key innovation of our system is that the rules' conditions and which rules compose a problem's solution are evolved separately. We utilise independent rule fitnesses which allows users to specifically tailor their model structure to fit the given requirements for explainability.
DistrEdge: Speeding up Convolutional Neural Network Inference on Distributed Edge Devices
Venue: arXiv cs.DC 2022
Year: 2022

As the number of edge devices with computing resources (e.g., embedded GPUs, mobile phones, and laptops) increases, recent studies demonstrate that it can be beneficial to collaboratively run convolutional neural network (CNN) inference on more than one edge device. However, these studies make strong assumptions on the devices' conditions, and their application is far from practical. In this work, we propose a general method, called DistrEdge, to provide CNN inference distribution strategies in environments with multiple IoT edge devices. By addressing heterogeneity in devices, network conditions, and nonlinear characters of CNN computation, DistrEdge is adaptive to a wide range of cases (e.g., with different network conditions, various device types) using deep reinforcement learning technology. We utilize the latest embedded AI computing devices (e.g., NVIDIA Jetson products) to construct cases of heterogeneous devices' types in the experiment. Based on our evaluations, DistrEdge can properly adjust the distribution strategy according to the devices' computing characters and the network conditions. It achieves 1.1 to 3x speedup compared to state-of-the-art methods.
Matching of Markov Databases Under Random Column Repetitions
Venue: arXiv cs.IT 2022
Year: 2022

Matching entries of correlated shuffled databases have practical applications ranging from privacy to biology. In this paper, motivated by synchronization errors in the sampling of time-indexed databases, matching of random databases under random column repetitions and deletions is investigated. It is assumed that for each entry (row) in the database, the attributes (columns) are correlated, which is modeled as a Markov process. Column histograms are proposed as a permutation-invariant feature to detect the repetition pattern, whose asymptotic-uniqueness is proved using information-theoretic tools. Repetition detection is then followed by a typicality-based row matching scheme. Considering this overall scheme, sufficient conditions for successful matching of databases in terms of the database growth rate are derived. A modified version of Fano's inequality leads to a tight necessary condition for successful matching, establishing the matching capacity under column repetitions. This capacity is equal to the erasure bound, which assumes the repetition locations are known a-priori. Overall, our results provide insights on privacy-preserving publication of anonymized time-indexed data.
WatchAuth: User Authentication and Intent Recognition in Mobile Payments using a Smartwatch
Venue: arXiv cs.CR 2022
Year: 2022

In this paper, we show that the tap gesture, performed when a user 'taps' a smartwatch onto an NFC-enabled terminal to make a payment, is a biometric capable of implicitly authenticating the user and simultaneously recognising intent-to-pay. The proposed system can be deployed purely in software on the watch without requiring updates to payment terminals. It is agnostic to terminal type and position and the intent recognition portion does not require any training data from the user. To validate the system, we conduct a user study (n=16) to collect wrist motion data from users as they interact with payment terminals and to collect long-term data from a subset of them (n=9) as they perform daily activities. Based on this data, we identify optimum gesture parameters and develop authentication and intent recognition models, for which we achieve EERs of 0.08 and 0.04, respectively.
Technological Factors Influencing Videoconferencing and Zoom Fatigue
Venue: arXiv cs.HC 2022
Year: 2022

The paper presents a conceptual, multidimensional approach to understand the technological factors that are assumed to or even have been proven to contribute to what has been coined as Zoom Fatigue (ZF) or more generally Videoconferencing Fatigue (VCF). With the advent of the Covid-19 pandemic, the usage of VC services has drastically increased, leading to more and more reports about the ZF or VCF phenomenon. The paper is motivated by the fact that some of the media outlets initially starting the debate on what Zoom fatigue is and how it can be avoided, as well as some of the scientific papers addressing the topic, contain assumptions that are rather hypothetical and insufficiently underpinned by scientific evidence. Most of these works are acknowledge the lacking evidence and partly suggest directions for future research. This paper intends to deepen the survey of VC-technology-related literature and to provide more existing evidence, where possible, while reviewing some of the already provided support or evidence for certain causal hypotheses. The technological factors dimension and its identified sub-dimensions presented in this paper are embedded within a more holistic four-dimensional conceptual factors model describing the causes for ZF or VCF. The paper describing this overall conceptual model is written by the same group of authors and currently under revision for an Open Access Journal publication. The present paper expands on the technological factors dimension descriptions provided in the overall model paper and provides more detailed analyzes and concepts associated with how VC technology may affect users' perception, cognitive load, interaction and communication, possibly leading to stress, exhaustion and fatigue. The paper currently is a living document which will be expanded further with regard to the evidence for or against the impact of certain technological factors.
A Bibliometric Perspective of Social Science Scientific Communities of Pakistan and India
Venue: arXiv cs.DL 2022
Year: 2022

In this study, we use research publication data from the field of social science to identify collaboration networks among social science research communities of India and Pakistan. We have used Scopus database to extract information of social science journals for both countries India and Pakistan. Study of this data is significant as both countries have common social issues and many of common social values. Keywords analysis has been done to see common research areas in both communities like poverty, education, the issue of gender etc. Despite having many of the common social issues, collaboration among social science research communities of both countries is not strong.
Reasoning on the Air: An Implicit Semantic Communication Architecture
Venue: arXiv cs.NI 2022
Year: 2022

Semantic communication is a novel communication paradigm which draws inspiration from human communication focusing on the delivery of the meaning of a message to the intended users. It has attracted significant interest recently due to its potential to improve efficiency and reliability of communication, enhance users' quality-of-experience (QoE), and achieve smoother cross-protocol/domain communication. Most existing works in semantic communication focus on identifying and transmitting explicit semantic meaning, e.g., labels of objects, that can be directly identified from the source signal. This paper investigates implicit semantic communication in which the hidden information, e.g., implicit causality and reasoning mechanisms of users, that cannot be directly observed from the source signal needs to be transported and delivered to the intended users. We propose a novel implicit semantic communication (iSC) architecture for representing, communicating, and interpreting the implicit semantic meaning. In particular, we first propose a graph-inspired structure to represent implicit meaning of message based on three key components: entity, relation, and reasoning mechanism. We then propose a generative adversarial imitation learning-based reasoning mechanism learning (GAML) solution for the destination user to learn and imitate the reasoning process of the source user. We prove that, by applying GAML, the destination user can accurately imitate the reasoning process of the users to generate reasoning paths that follow the same probability distribution as the expert paths. Numerical results suggest that our proposed architecture can achieve accurate implicit meaning interpretation at the destination user.
Demystify Optimization and Generalization of Over-parameterized PAC-Bayesian Learning
Venue: arXiv cs.LG 2022
Year: 2022

PAC-Bayesian is an analysis framework where the training error can be expressed as the weighted average of the hypotheses in the posterior distribution whilst incorporating the prior knowledge. In addition to being a pure generalization bound analysis tool, PAC-Bayesian bound can also be incorporated into an objective function to train a probabilistic neural network, making them a powerful and relevant framework that can numerically provide a tight generalization bound for supervised learning. For simplicity, we call probabilistic neural network learned using training objectives derived from PAC-Bayesian bounds as {\it PAC-Bayesian learning}. Despite their empirical success, the theoretical analysis of PAC-Bayesian learning for neural networks is rarely explored. This paper proposes a new class of convergence and generalization analysis for PAC-Bayes learning when it is used to train the over-parameterized neural networks by the gradient descent method. For a wide probabilistic neural network, we show that when PAC-Bayes learning is applied, the convergence result corresponds to solving a kernel ridge regression when the probabilistic neural tangent kernel (PNTK) is used as its kernel. Based on this finding, we further characterize the uniform PAC-Bayesian generalization bound which improves over the Rademacher complexity-based bound for non-probabilistic neural network. Finally, drawing the insight from our theoretical results, we propose a proxy measure for efficient hyperparameters selection, which is proven to be time-saving.
Image-to-Image MLP-mixer for Image Reconstruction
Venue: arXiv cs.CV 2022
Year: 2022

Neural networks are highly effective tools for image reconstruction problems such as denoising and compressive sensing. To date, neural networks for image reconstruction are almost exclusively convolutional. The most popular architecture is the U-Net, a convolutional network with a multi-resolution architecture. In this work, we show that a simple network based on the multi-layer perceptron (MLP)-mixer enables state-of-the art image reconstruction performance without convolutions and without a multi-resolution architecture, provided that the training set and the size of the network are moderately large. Similar to the original MLP-mixer, the image-to-image MLP-mixer is based exclusively on MLPs operating on linearly-transformed image patches. Contrary to the original MLP-mixer, we incorporate structure by retaining the relative positions of the image patches. This imposes an inductive bias towards natural images which enables the image-to-image MLP-mixer to learn to denoise images based on fewer examples than the original MLP-mixer. Moreover, the image-to-image MLP-mixer requires fewer parameters to achieve the same denoising performance than the U-Net and its parameters scale linearly in the image resolution instead of quadratically as for the original MLP-mixer. If trained on a moderate amount of examples for denoising, the image-to-image MLP-mixer outperforms the U-Net by a slight margin. It also outperforms the vision transformer tailored for image reconstruction and classical un-trained methods such as BM3D, making it a very effective tool for image reconstruction problems.
With a Little Help from My Friends: Transport Deniability for Instant Messaging
Venue: arXiv cs.CR 2022
Year: 2022

Traffic analysis for instant messaging (IM) applications continues to pose an important privacy challenge. In particular, transport-level data can leak unintentional information about IM -- such as who communicates with whom. Existing tools for metadata privacy have adoption obstacles, including the risks of being scrutinized for having a particular app installed, and performance overheads incompatible with mobile devices. We posit that resilience to traffic analysis must be directly supported by major IM services themselves, and must be done in a low-cost manner without breaking existing features. As a first step in this direction, we propose a hybrid messaging model that combines regular and deniable messages. We present a novel protocol for deniable instant messaging, which we call DenIM. DenIM is built on the principle that deniable messages can be made indistinguishable from regular messages with a little help from a user's friends. Deniable messages' network traffic can then be explained by a plausible cover story. DenIM achieves overhead proportional to the messages sent, as opposed to scaling with time or number of users. To show the effectiveness of DenIM, we implement a trace simulator, and show that DenIM's deniability guarantees hold against strong adversaries such as internet service providers.
Heed the Noise in Performance Evaluations in Neural Architecture Search
Venue: arXiv cs.NE 2022
Year: 2022

Neural Architecture Search (NAS) has recently become a topic of great interest. However, there is a potentially impactful issue within NAS that remains largely unrecognized: noise. Due to stochastic factors in neural network initialization, training, and the chosen train/validation dataset split, the performance evaluation of a neural network architecture, which is often based on a single learning run, is also stochastic. This may have a particularly large impact if a dataset is small. We therefore propose to reduce this noise by evaluating architectures based on average performance over multiple network training runs using different random seeds and cross-validation. We perform experiments for a combinatorial optimization formulation of NAS in which we vary noise reduction levels. We use the same computational budget for each noise level in terms of network training runs, i.e., we allow less architecture evaluations when averaging over more training runs. Multiple search algorithms are considered, including evolutionary algorithms which generally perform well for NAS. We use two publicly available datasets from the medical image segmentation domain where datasets are often limited and variability among samples is often high. Our results show that reducing noise in architecture evaluations enables finding better architectures by all considered search algorithms.
Robust Linear Regression for General Feature Distribution
Venue: arXiv cs.LG 2022
Year: 2022

We investigate robust linear regression where data may be contaminated by an oblivious adversary, i.e., an adversary than may know the data distribution but is otherwise oblivious to the realizations of the data samples. This model has been previously analyzed under strong assumptions. Concretely, $\textbf{(i)}$ all previous works assume that the covariance matrix of the features is positive definite; and $\textbf{(ii)}$ most of them assume that the features are centered (i.e. zero mean). Additionally, all previous works make additional restrictive assumption, e.g., assuming that the features are Gaussian or that the corruptions are symmetrically distributed. In this work we go beyond these assumptions and investigate robust regression under a more general set of assumptions: $\textbf{(i)}$ we allow the covariance matrix to be either positive definite or positive semi definite, $\textbf{(ii)}$ we do not necessarily assume that the features are centered, $\textbf{(iii)}$ we make no further assumption beyond boundedness (sub-Gaussianity) of features and measurement noise. Under these assumption we analyze a natural SGD variant for this problem and show that it enjoys a fast convergence rate when the covariance matrix is positive definite. In the positive semi definite case we show that there are two regimes: if the features are centered we can obtain a standard convergence rate; otherwise the adversary can cause any learner to fail arbitrarily.
Tracking Discourse Influence in Darknet Forums
Venue: arXiv cs.CL 2022
Year: 2022

This technical report documents our efforts in addressing the tasks set forth by the 2021 AMoC (Advanced Modelling of Cyber Criminal Careers) Hackathon. Our main contribution is a joint visualisation of semantic and temporal features, generating insight into the supplied data on darknet cybercrime through the aspects of novelty, transience, and resonance, which describe the potential impact a message might have on the overall discourse in darknet communities. All code and data produced by us as part of this hackathon is publicly available.
About Code Equivalence -- a Geometric Approach
Venue: arXiv cs.DM 2022
Year: 2022

The equivalence test is a main part in any classification problem. It helps to prove bounds for the main parameters of the considered combinatorial structures and to study their properties. In this paper, we present algorithms for equivalence of linear codes, based on their relation to multisets of points in a projective geometry.
Incorporating Distributed DRL into Storage Resource Optimization of Space-Air-Ground Integrated Wireless Communication Network
Venue: arXiv cs.NI 2022
Year: 2022

Space-air-ground integrated network (SAGIN) is a new type of wireless network mode. The effective management of SAGIN resources is a prerequisite for high-reliability communication. However, the storage capacity of space-air network segment is extremely limited. The air servers also do not have sufficient storage resources to centrally accommodate the information uploaded by each edge server. So the problem of how to coordinate the storage resources of SAGIN has arisen. This paper proposes a SAGIN storage resource management algorithm based on distributed deep reinforcement learning (DRL). The resource management process is modeled as a Markov decision model. In each edge physical domain, we extract the network attributes represented by storage resources for the agent to build a training environment, so as to realize the distributed training. In addition, we propose a SAGIN resource management framework based on distributed DRL. Simulation results show that the agent has an ideal training effect. Compared with other algorithms, the resource allocation revenue and user request acceptance rate of the proposed algorithm are increased by about 18.15\% and 8.35\% respectively. Besides, the proposed algorithm has good flexibility in dealing with the changes of resource conditions.
Generative Modeling of Complex Data
Venue: arXiv cs.LG 2022
Year: 2022

In recent years, several models have improved the capacity to generate synthetic tabular datasets. However, such models focus on synthesizing simple columnar tables and are not useable on real-life data with complex structures. This paper puts forward a generic framework to synthesize more complex data structures with composite and nested types. It then proposes one practical implementation, built with causal transformers, for struct (mappings of types) and lists (repeated instances of a type). The results on standard benchmark datasets show that such implementation consistently outperforms current state-of-the-art models both in terms of machine learning utility and statistical similarity. Moreover, it shows very strong results on two complex hierarchical datasets with multiple nesting and sparse data, that were previously out of reach.
Group invariant machine learning by fundamental domain projections
Venue: arXiv cs.LG 2022
Year: 2022

We approach the well-studied problem of supervised group invariant and equivariant machine learning from the point of view of geometric topology. We propose a novel approach using a pre-processing step, which involves projecting the input data into a geometric space which parametrises the orbits of the symmetry group. This new data can then be the input for an arbitrary machine learning model (neural network, random forest, support-vector machine etc). We give an algorithm to compute the geometric projection, which is efficient to implement, and we illustrate our approach on some example machine learning problems (including the well-studied problem of predicting Hodge numbers of CICY matrices), in each case finding an improvement in accuracy versus others in the literature. The geometric topology viewpoint also allows us to give a unified description of so-called intrinsic approaches to group equivariant machine learning, which encompasses many other approaches in the literature.
NeAT: Neural Adaptive Tomography
Venue: arXiv cs.CV 2022
Year: 2022

In this paper, we present Neural Adaptive Tomography (NeAT), the first adaptive, hierarchical neural rendering pipeline for multi-view inverse rendering. Through a combination of neural features with an adaptive explicit representation, we achieve reconstruction times far superior to existing neural inverse rendering methods. The adaptive explicit representation improves efficiency by facilitating empty space culling and concentrating samples in complex regions, while the neural features act as a neural regularizer for the 3D reconstruction. The NeAT framework is designed specifically for the tomographic setting, which consists only of semi-transparent volumetric scenes instead of opaque objects. In this setting, NeAT outperforms the quality of existing optimization-based tomography solvers while being substantially faster.
Feature-Style Encoder for Style-Based GAN Inversion
Venue: arXiv cs.CV 2022
Year: 2022

We propose a novel architecture for GAN inversion, which we call Feature-Style encoder. The style encoder is key for the manipulation of the obtained latent codes, while the feature encoder is crucial for optimal image reconstruction. Our model achieves accurate inversion of real images from the latent space of a pre-trained style-based GAN model, obtaining better perceptual quality and lower reconstruction error than existing methods. Thanks to its encoder structure, the model allows fast and accurate image editing. Additionally, we demonstrate that the proposed encoder is especially well-suited for inversion and editing on videos. We conduct extensive experiments for several style-based generators pre-trained on different data domains. Our proposed method yields state-of-the-art results for style-based GAN inversion, significantly outperforming competing approaches. Source codes are available at https://github.com/InterDigitalInc/FeatureStyleEncoder .