OpenRaiser/Intern-Atlas huggingface dataset:
Multiagent Learning for Competitive Opinion Optimization
Venue: arXiv cs.GT 2022
Year: 2022

From a perspective of designing or engineering for opinion formation games in social networks, the "opinion maximization (or minimization)" problem has been studied mainly for designing subset selecting algorithms. We define a two-player zero-sum Stackelberg game of competitive opinion optimization by letting the player under study as the leader minimize the sum of expressed opinions by doing so-called "internal opinion design", knowing that the other adversarial player as the follower is to maximize the same objective by also conducting her own internal opinion design. We furthermore consider multiagent learning, specifically using the Optimistic Gradient Descent Ascent, and analyze its convergence to equilibria in the simultaneous version of competitive opinion optimization.
Time-Staging Enhancement of Hybrid System Falsification
Venue: arXiv cs.SY 2022
Year: 2022

Optimization-based falsification employs stochastic optimization algorithms to search for error input of hybrid systems. In this paper we introduce a simple idea to enhance falsification, namely time staging, that allows the time-causal structure of time-dependent signals to be exploited by the optimizers. Time staging consists of running a falsification solver multiple times, from one interval to another, incrementally constructing an input signal candidate. Our experiments show that time staging can dramatically increase performance in some realistic examples. We also present theoretical results that suggest the kinds of models and specifications for which time staging is likely to be effective.
Scrambled Linear Pseudorandom Number Generators
Venue: arXiv cs.DS 2022
Year: 2022

$\mathbf F_2$-linear pseudorandom number generators are very popular due to their high speed, to the ease with which generators with a sizable state space can be created, and to their provable theoretical properties. However, they suffer from linear artifacts that show as failures in linearity-related statistical tests such as the binary-rank and the linear-complexity test. In this paper, we give two new contributions. First, we introduce two new $\mathbf F_2$-linear transformations that have been handcrafted to have good statistical properties and at the same time to be programmable very efficiently on superscalar processors, or even directly in hardware. Then, we describe some scramblers, that is, nonlinear functions applied to the state array that reduce or delete the linear artifacts, and propose combinations of linear transformations and scramblers that give extremely fast pseudorandom number generators of high quality. A novelty in our approach is that we use ideas from the theory of filtered linear-feedback shift registers to prove some properties of our scramblers, rather than relying purely on heuristics. In the end, we provide simple, extremely fast generators that use a few hundred bits of memory, have provable properties, and pass strong statistical tests.
APMEC: An Automated Provisioning Framework for Multi-access Edge Computing
Venue: arXiv cs.NI 2022
Year: 2022

Novel use cases and verticals such as connected cars and human-robot cooperation in the areas of 5G and Tactile Internet can significantly benefit from the flexibility and reduced latency provided by Network Function Virtualization (NFV) and Multi-Access Edge Computing (MEC). Existing frameworks managing and orchestrating MEC and NFV are either tightly coupled or completely separated. The former design is inflexible and increases the complexity of one framework. Whereas, the latter leads to inefficient use of computation resources because information are not shared. We introduce APMEC, a dedicated framework for MEC while enabling the collaboration with the management and orchestration (MANO) frameworks for NFV. The new design allows to reuse allocated network services, thus maximizing resource utilization. Measurement results have shown that APMEC can allocate up to 60% more number of network services. Being developed on top of OpenStack, APMEC is an open source project, available for collaboration and facilitating further research activities.
Scalable and Robust Community Detection with Randomized Sketching
Venue: arXiv cs.SI 2022
Year: 2022

This article explores and analyzes the unsupervised clustering of large partially observed graphs. We propose a scalable and provable randomized framework for clustering graphs generated from the stochastic block model. The clustering is first applied to a sub-matrix of the graph's adjacency matrix associated with a reduced graph sketch constructed using random sampling. Then, the clusters of the full graph are inferred based on the clusters extracted from the sketch using a correlation-based retrieval step. Uniform random node sampling is shown to improve the computational complexity over clustering of the full graph when the cluster sizes are balanced. A new random degree-based node sampling algorithm is presented which significantly improves upon the performance of the clustering algorithm even when clusters are unbalanced. This framework improves the phase transitions for matrix-decomposition-based clustering with regard to computational complexity and minimum cluster size, which are shown to be nearly dimension-free in the low inter-cluster connectivity regime. A third sampling technique is shown to improve balance by randomly sampling nodes based on spatial distribution. We provide analysis and numerical results using a convex clustering algorithm based on matrix completion.
Federated Learning with Non-IID Data
Venue: arXiv cs.LG 2022
Year: 2022

Federated learning enables resource-constrained edge compute devices, such as mobile phones and IoT devices, to learn a shared model for prediction, while keeping the training data local. This decentralized approach to train models provides privacy, security, regulatory and economic benefits. In this work, we focus on the statistical challenge of federated learning when local data is non-IID. We first show that the accuracy of federated learning reduces significantly, by up to 55% for neural networks trained for highly skewed non-IID data, where each client device trains only on a single class of data. We further show that this accuracy reduction can be explained by the weight divergence, which can be quantified by the earth mover's distance (EMD) between the distribution over classes on each device and the population distribution. As a solution, we propose a strategy to improve training on non-IID data by creating a small subset of data which is globally shared between all the edge devices. Experiments show that accuracy can be increased by 30% for the CIFAR-10 dataset with only 5% globally shared data.
Boolean-like algebras of finite dimension
Venue: arXiv cs.LO 2022
Year: 2022

We continue the investigation of Boolean-like algebras of dimension n (nBA) having n constants e1,...,en, and an (n+1)-ary operation q (a "generalised if-then-else") that induces a decomposition of the algebra into n factors through the so-called n-central elements. Varieties of nBAs share many remarkable properties with the variety of Boolean algebras and with primal varieties. Exploiting the concept of central element, we extend the notion of Boolean power to that of semiring power and we prove two representation theorems: (i) Any pure nBA is isomorphic to the algebra of n-central elements of a Boolean vector space; (ii) Any member of a variety of nBAs with one generator is isomorphic to a Boolean power of this generator. This gives a new proof of Foster's theorem on primal varieties.
Optimizing Opinions with Stubborn Agents
Venue: arXiv cs.SI 2022
Year: 2022

We consider the problem of optimizing the placement of stubborn agents in a social network in order to maximally influence the population. We assume the network contains stubborn users whose opinions do not change, and non-stubborn users who can be persuaded. We further assume the opinions in the network are in an equilibrium that is common to many opinion dynamics models, including the well-known DeGroot model. We develop a discrete optimization formulation for the problem of maximally shifting the equilibrium opinions in a network by targeting users with stubborn agents. The opinion objective functions we consider are the opinion mean, the opinion variance, and the number of individuals whose opinion exceeds a fixed threshold. We show that the mean opinion is a monotone submodular function, allowing us to find a good solution using a greedy algorithm. We find that on real social networks in Twitter consisting of tens of thousands of individuals, a small number of stubborn agents can non-trivially influence the equilibrium opinions. Furthermore, we show that our greedy algorithm outperforms several common benchmarks. We then propose an opinion dynamics model where users communicate noisy versions of their opinions, communications are random, users grow more stubborn with time, and there is heterogeneity is how users' stubbornness increases. We prove that under fairly general conditions on the stubbornness rates of the individuals, the opinions in this model converge to the same equilibrium as the DeGroot model, despite the randomness and user heterogeneity in the model.
Land-Cover Classification with High-Resolution Remote Sensing Images Using Transferable Deep Models
Venue: arXiv cs.CV 2022
Year: 2022

In recent years, large amount of high spatial-resolution remote sensing (HRRS) images are available for land-cover mapping. However, due to the complex information brought by the increased spatial resolution and the data disturbances caused by different conditions of image acquisition, it is often difficult to find an efficient method for achieving accurate land-cover classification with high-resolution and heterogeneous remote sensing images. In this paper, we propose a scheme to apply deep model obtained from labeled land-cover dataset to classify unlabeled HRRS images. The main idea is to rely on deep neural networks for presenting the contextual information contained in different types of land-covers and propose a pseudo-labeling and sample selection scheme for improving the transferability of deep models. More precisely, a deep Convolutional Neural Networks is first pre-trained with a well-annotated land-cover dataset, referred to as the source data. Then, given a target image with no labels, the pre-trained CNN model is utilized to classify the image in a patch-wise manner. The patches with high confidence are assigned with pseudo-labels and employed as the queries to retrieve related samples from the source data. The pseudo-labels confirmed with the retrieved results are regarded as supervised information for fine-tuning the pre-trained deep model. To obtain a pixel-wise land-cover classification with the target image, we rely on the fine-tuned CNN and develop a hybrid classification by combining patch-wise classification and hierarchical segmentation. In addition, we create a large-scale land-cover dataset containing 150 Gaofen-2 satellite images for CNN pre-training. Experiments on multi-source HRRS images show encouraging results and demonstrate the applicability of the proposed scheme to land-cover classification.
Learning Optimal Resource Allocations in Wireless Systems
Venue: arXiv cs.LG 2022
Year: 2022

This paper considers the design of optimal resource allocation policies in wireless communication systems which are generically modeled as a functional optimization problem with stochastic constraints. These optimization problems have the structure of a learning problem in which the statistical loss appears as a constraint, motivating the development of learning methodologies to attempt their solution. To handle stochastic constraints, training is undertaken in the dual domain. It is shown that this can be done with small loss of optimality when using near-universal learning parameterizations. In particular, since deep neural networks (DNN) are near-universal their use is advocated and explored. DNNs are trained here with a model-free primal-dual method that simultaneously learns a DNN parametrization of the resource allocation policy and optimizes the primal and dual variables. Numerical simulations demonstrate the strong performance of the proposed approach on a number of common wireless resource allocation problems.
The Theory of Traces for Systems with Nondeterminism, Probability, and Termination
Venue: arXiv cs.LO 2022
Year: 2022

This paper studies trace-based equivalences for systems combining nondeterministic and probabilistic choices. We show how trace semantics for such processes can be recovered by instantiating a coalgebraic construction known as the generalised powerset construction. We characterise and compare the resulting semantics to known definitions of trace equivalences appearing in the literature. Most of our results are based on the exciting interplay between monads and their presentations via algebraic theories.
Few Cuts Meet Many Point Sets
Venue: arXiv cs.CG 2022
Year: 2022

We study the problem of how to breakup many point sets in $\mathbb{R}^d$ into smaller parts using a few splitting (shared) hyperplanes. This problem is related to the classical Ham-Sandwich Theorem. We provide a logarithmic approximation to the optimal solution using the greedy algorithm for submodular optimization.
Almost Envy-Free Allocations with Connected Bundles
Venue: arXiv cs.GT 2022
Year: 2022

We study the existence of allocations of indivisible goods that are envy-free up to one good (EF1), under the additional constraint that each bundle needs to be connected in an underlying item graph. If the graph is a path and the utility functions are monotonic over bundles, we show the existence of EF1 allocations for at most four agents, and the existence of EF2 allocations for any number of agents; our proofs involve discrete analogues of the Stromquist's moving-knife protocol and the Su--Simmons argument based on Sperner's lemma. For identical utilities, we provide a polynomial-time algorithm that computes an EF1 allocation for any number of agents. For the case of two agents, we characterize the class of graphs that guarantee the existence of EF1 allocations as those whose biconnected components are arranged in a path; this property can be checked in linear time.
IDSGAN: Generative Adversarial Networks for Attack Generation against Intrusion Detection
Venue: arXiv cs.CR 2022
Year: 2022

As an essential tool in security, the intrusion detection system bears the responsibility of the defense to network attacks performed by malicious traffic. Nowadays, with the help of machine learning algorithms, intrusion detection systems develop rapidly. However, the robustness of this system is questionable when it faces adversarial attacks. For the robustness of detection systems, more potential attack approaches are under research. In this paper, a framework of the generative adversarial networks, called IDSGAN, is proposed to generate the adversarial malicious traffic records aiming to attack intrusion detection systems by deceiving and evading the detection. Given that the internal structure and parameters of the detection system are unknown to attackers, the adversarial attack examples perform the black-box attacks against the detection system. IDSGAN leverages a generator to transform original malicious traffic records into adversarial malicious ones. A discriminator classifies traffic examples and dynamically learns the real-time black-box detection system. More significantly, the restricted modification mechanism is designed for the adversarial generation to preserve original attack functionalities of adversarial traffic records. The effectiveness of the model is indicated by attacking multiple algorithm-based detection models with different attack categories. The robustness is verified by changing the number of the modified features. A comparative experiment with adversarial attack baselines demonstrates the superiority of our model.
Reviews Matter: How Distributed Mentoring Predicts Lexical Diversity on Fanfiction.net
Venue: arXiv cs.SI 2022
Year: 2022

Fanfiction.net provides an informal learning space for young writers through distributed mentoring, networked giving and receiving of feedback. In this paper, we quantify the cumulative effect of feedback on lexical diversity for 1.5 million authors.
Adding Neural Network Controllers to Behavior Trees without Destroying Performance Guarantees
Venue: arXiv cs.RO 2022
Year: 2022

In this paper, we show how Behavior Trees that have performance guarantees, in terms of safety and goal convergence, can be extended with components that were designed using machine learning, without destroying those performance guarantees. Machine learning approaches such as reinforcement learning or learning from demonstration can be very appealing to AI designers that want efficient and realistic behaviors in their agents. However, those algorithms seldom provide guarantees for solving the given task in all different situations while keeping the agent safe. Instead, such guarantees are often easier to find for manually designed model-based approaches. In this paper we exploit the modularity of behavior trees to extend a given design with an efficient, but possibly unreliable, machine learning component in a way that preserves the guarantees. The approach is illustrated with an inverted pendulum example.
Efficient Non-parametric Bayesian Hawkes Processes
Venue: arXiv cs.LG 2022
Year: 2022

In this paper, we develop an efficient nonparametric Bayesian estimation of the kernel function of Hawkes processes. The non-parametric Bayesian approach is important because it provides flexible Hawkes kernels and quantifies their uncertainty. Our method is based on the cluster representation of Hawkes processes. Utilizing the finite support assumption of the Hawkes process, we efficiently sample random branching structures and thus, we split the Hawkes process into clusters of Poisson processes. We derive two algorithms -- a block Gibbs sampler and a maximum a posteriori estimator based on expectation maximization -- and we show that our methods have a linear time complexity, both theoretically and empirically. On synthetic data, we show our methods to be able to infer flexible Hawkes triggering kernels. On two large-scale Twitter diffusion datasets, we show that our methods outperform the current state-of-the-art in goodness-of-fit and that the time complexity is linear in the size of the dataset. We also observe that on diffusions related to online videos, the learned kernels reflect the perceived longevity for different content types such as music or pets videos.
The existence of perfect codes in Doob graphs
Venue: arXiv cs.IT 2022
Year: 2022

We solve the problem of existence of perfect codes in the Doob graph. It is shown that 1-perfect codes in the Doob graph D(m,n) exist if and only if 6m+3n+1 is a power of 2; that is, if the size of a 1-ball divides the number of vertices. Keywords: perfect codes, distance-regular graphs, Doob graphs, Eisenstein-Jacobi integers.
Cross-Modal Distillation for RGB-Depth Person Re-Identification
Venue: arXiv cs.CV 2022
Year: 2022

Person re-identification is a key challenge for surveillance across multiple sensors. Prompted by the advent of powerful deep learning models for visual recognition, and inexpensive RGB-D cameras and sensor-rich mobile robotic platforms, e.g. self-driving vehicles, we investigate the relatively unexplored problem of cross-modal re-identification of persons between RGB (color) and depth images. The considerable divergence in data distributions across different sensor modalities introduces additional challenges to the typical difficulties like distinct viewpoints, occlusions, and pose and illumination variation. While some work has investigated re-identification across RGB and infrared, we take inspiration from successes in transfer learning from RGB to depth in object detection tasks. Our main contribution is a novel method for cross-modal distillation for robust person re-identification, which learns a shared feature representation space of person's appearance in both RGB and depth images. In addition, we propose a cross-modal attention mechanism where the gating signal from one modality can dynamically activate the most discriminant CNN filters of the other modality. The proposed distillation method is compared to conventional and deep learning approaches proposed for other cross-domain re-identification tasks. Results obtained on the public BIWI and RobotPKU datasets indicate that the proposed method can significantly outperform the state-of-the-art approaches by up to 16.1% in mean Average Precision (mAP), demonstrating the benefit of the distillation paradigm. The experimental results also indicate that using cross-modal attention allows to improve recognition accuracy considerably with respect to the proposed distillation method and relevant state-of-the-art approaches.
Multimodal Machine Learning for Automated ICD Coding
Venue: arXiv cs.LG 2022
Year: 2022

This study presents a multimodal machine learning model to predict ICD-10 diagnostic codes. We developed separate machine learning models that can handle data from different modalities, including unstructured text, semi-structured text and structured tabular data. We further employed an ensemble method to integrate all modality-specific models to generate ICD-10 codes. Key evidence was also extracted to make our prediction more convincing and explainable. We used the Medical Information Mart for Intensive Care III (MIMIC -III) dataset to validate our approach. For ICD code prediction, our best-performing model (micro-F1 = 0.7633, micro-AUC = 0.9541) significantly outperforms other baseline models including TF-IDF (micro-F1 = 0.6721, micro-AUC = 0.7879) and Text-CNN model (micro-F1 = 0.6569, micro-AUC = 0.9235). For interpretability, our approach achieves a Jaccard Similarity Coefficient (JSC) of 0.1806 on text data and 0.3105 on tabular data, where well-trained physicians achieve 0.2780 and 0.5002 respectively.
Online Exploration of an Unknown Region of Interest with a Team of Aerial Robots
Venue: arXiv cs.RO 2022
Year: 2022

In this paper, we study the problem of exploring an unknown Region Of Interest (ROI) with a team of aerial robots. The size and shape of the ROI are unknown to the robots. The objective is to find a tour for each robot such that each point in the ROI must be visible from the field-of-view of some robot along its tour. In conventional exploration using ground robots, the ROI boundary is typically also as an obstacle and robots are naturally constrained to the interior of this ROI. Instead, we study the case where aerial robots are not restricted to flying inside the ROI (and can fly over the boundary of the ROI). We propose a recursive depth-first search-based algorithm that yields a constant competitive ratio for the exploration problem. Our analysis also extends to the case where the ROI is translating, \eg, in the case of marine plumes. In the simpler version of the problem where the ROI is modeled as a 2D grid, the competitive ratio is $\frac{2(S_r+S_p)(R+\lfloor\log{R}\rfloor)}{(S_r-S_p)(1+\lfloor\log{R}\rfloor)}$ where $R$ is the number of robots, and $S_r$ and $S_p$ are the robot speed and the ROI speed, respectively. We also consider a more realistic scenario where the ROI shape is not restricted to grid cells but an arbitrary shape. We show our algorithm has $\frac{2(S_r+S_p)(18R+\lfloor\log{R}\rfloor)}{(S_r-S_p)(1+\lfloor\log{R}\rfloor)}$ competitive ratio under some conditions. We empirically verify our algorithm using simulations as well as a proof-of-concept experiment mapping a 2D ROI using an aerial robot with a downwards-facing camera.