OpenRaiser/Intern-Atlas huggingface dataset:
Embeddings and labeling schemes for A*
Venue: arXiv cs.CG 2021
Year: 2021

A* is a classic and popular method for graphs search and path finding. It assumes the existence of a heuristic function $h(u,t)$ that estimates the shortest distance from any input node $u$ to the destination $t$. Traditionally, heuristics have been handcrafted by domain experts. However, over the last few years, there has been a growing interest in learning heuristic functions. Such learned heuristics estimate the distance between given nodes based on "features" of those nodes. In this paper we formalize and initiate the study of such feature-based heuristics. In particular, we consider heuristics induced by norm embeddings and distance labeling schemes, and provide lower bounds for the tradeoffs between the number of dimensions or bits used to represent each graph node, and the running time of the A* algorithm. We also show that, under natural assumptions, our lower bounds are almost optimal.
Uniform Brackets, Containers, and Combinatorial Macbeath Regions
Venue: arXiv cs.DS 2021
Year: 2021

We study the connections between three seemingly different combinatorial structures - "uniform" brackets in statistics and probability theory, "containers" in online and distributed learning theory, and "combinatorial Macbeath regions", or Mnets in discrete and computational geometry. We show that these three concepts are manifestations of a single combinatorial property that can be expressed under a unified framework along the lines of Vapnik-Chervonenkis type theory for uniform convergence. These new connections help us to bring tools from discrete and computational geometry to prove improved bounds for these objects. Our improved bounds help to get an optimal algorithm for distributed learning of halfspaces, an improved algorithm for the distributed convex set disjointness problem, and improved regret bounds for online algorithms against a smoothed adversary for a large class of semi-algebraic threshold functions.
Quantifying Cybersecurity Effectiveness of Software Diversity
Venue: arXiv cs.CR 2021
Year: 2021

The deployment of monoculture software stacks can cause a devastating damage even by a single exploit against a single vulnerability. Inspired by the resilience benefit of biological diversity, the concept of software diversity has been proposed in the security domain. Although it is intuitive that software diversity may enhance security, its effectiveness has not been quantitatively investigated. Currently, no theoretical or empirical study has been explored to measure the security effectiveness of network diversity. In this paper, we take a first step towards ultimately tackling the problem. We propose a systematic framework that can model and quantify the security effectiveness of network diversity. We conduct simulations to demonstrate the usefulness of the framework. In contrast to the intuitive belief, we show that diversity does not necessarily improve security from a whole-network perspective. The root cause of this phenomenon is that the degree of vulnerability in diversified software implementations plays a critical role in determining the security effectiveness of software diversity.
DVCFlow: Modeling Information Flow Towards Human-like Video Captioning
Venue: arXiv cs.CV 2021
Year: 2021

Dense video captioning (DVC) aims to generate multi-sentence descriptions to elucidate the multiple events in the video, which is challenging and demands visual consistency, discoursal coherence, and linguistic diversity. Existing methods mainly generate captions from individual video segments, lacking adaptation to the global visual context and progressive alignment between the fast-evolved visual content and textual descriptions, which results in redundant and spliced descriptions. In this paper, we introduce the concept of information flow to model the progressive information changing across video sequence and captions. By designing a Cross-modal Information Flow Alignment mechanism, the visual and textual information flows are captured and aligned, which endows the captioning process with richer context and dynamics on event/topic evolution. Based on the Cross-modal Information Flow Alignment module, we further put forward DVCFlow framework, which consists of a Global-local Visual Encoder to capture both global features and local features for each video segment, and a pre-trained Caption Generator to produce captions. Extensive experiments on the popular ActivityNet Captions and YouCookII datasets demonstrate that our method significantly outperforms competitive baselines, and generates more human-like text according to subject and objective tests.
HMS-OS: Improving the Human Mental Search Optimisation Algorithm by Grouping in both Search and Objective Space
Venue: arXiv cs.NE 2021
Year: 2021

The human mental search (HMS) algorithm is a relatively recent population-based metaheuristic algorithm, which has shown competitive performance in solving complex optimisation problems. It is based on three main operators: mental search, grouping, and movement. In the original HMS algorithm, a clustering algorithm is used to group the current population in order to identify a promising region in search space, while candidate solutions then move towards the best candidate solution in the promising region. In this paper, we propose a novel HMS algorithm, HMS-OS, which is based on clustering in both objective and search space, where clustering in objective space finds a set of best candidate solutions whose centroid is then also used in updating the population. For further improvement, HMSOS benefits from an adaptive selection of the number of mental processes in the mental search operator. Experimental results on CEC-2017 benchmark functions with dimensionalities of 50 and 100, and in comparison to other optimisation algorithms, indicate that HMS-OS yields excellent performance, superior to those of other methods.
Optimal Association Strategy of Multi-gateway Wireless Sensor Networks Against Smart Jammers
Venue: arXiv cs.GT 2021
Year: 2021

Engineers have numerous low-power wireless sensor devices in the current network setup for the Internet of Things, such as ZigBee, LoRaWAN, ANT, or Bluetooth. These low-power wireless sensors are the best candidates to transfer and collect data. But they are all vulnerable to the physical jamming attack since it is not costly for the attackers to run low power jammer sources in these networks. Having multiple gateways and providing alternative connections to sensors would help these networks to mitigate successful jamming. In this paper, we propose an analytical model to solve the problem of gateway selection and association based on a Stackelberg game, where the jammer is the follower. We first formulate the payoffs of both sensor network and attacker and then establish and prove the conditions leading to NASH equilibrium. With numerical investigation, we also present how our model can capture the performance of sensor networks under jamming with a varying number of gateways. Our results show that compared to the single gateway scenario, the network's throughput will improve by 26% and 60% when we deploy two and four gateways in the presence of a single jammer.
A Hybrid Approach for an Interpretable and Explainable Intrusion Detection System
Venue: arXiv cs.CR 2021
Year: 2021

Cybersecurity has been a concern for quite a while now. In the latest years, cyberattacks have been increasing in size and complexity, fueled by significant advances in technology. Nowadays, there is an unavoidable necessity of protecting systems and data crucial for business continuity. Hence, many intrusion detection systems have been created in an attempt to mitigate these threats and contribute to a timelier detection. This work proposes an interpretable and explainable hybrid intrusion detection system, which makes use of artificial intelligence methods to achieve better and more long-lasting security. The system combines experts' written rules and dynamic knowledge continuously generated by a decision tree algorithm as new shreds of evidence emerge from network activity.
Adversarial Deep Learning for Online Resource Allocation
Venue: arXiv cs.LG 2021
Year: 2021

Online algorithm is an important branch in algorithm design. Designing online algorithms with a bounded competitive ratio (in terms of worst-case performance) can be hard and usually relies on problem-specific assumptions. Inspired by adversarial training from Generative Adversarial Net (GAN) and the fact that competitive ratio of an online algorithm is based on worst-case input, we adopt deep neural networks to learn an online algorithm for a resource allocation and pricing problem from scratch, with the goal that the performance gap between offline optimum and the learned online algorithm can be minimized for worst-case input. Specifically, we leverage two neural networks as algorithm and adversary respectively and let them play a zero sum game, with the adversary being responsible for generating worst-case input while the algorithm learns the best strategy based on the input provided by the adversary. To ensure better convergence of the algorithm network (to the desired online algorithm), we propose a novel per-round update method to handle sequential decision making to break complex dependency among different rounds so that update can be done for every possible action, instead of only sampled actions. To the best of our knowledge, our work is the first using deep neural networks to design an online algorithm from the perspective of worst-case performance guarantee. Empirical studies show that our updating methods ensure convergence to Nash equilibrium and the learned algorithm outperforms state-of-the-art online algorithms under various settings.
Expert-Guided Symmetry Detection in Markov Decision Processes
Venue: arXiv cs.LG 2021
Year: 2021

Learning a Markov Decision Process (MDP) from a fixed batch of trajectories is a non-trivial task whose outcome's quality depends on both the amount and the diversity of the sampled regions of the state-action space. Yet, many MDPs are endowed with invariant reward and transition functions with respect to some transformations of the current state and action. Being able to detect and exploit these structures could benefit not only the learning of the MDP but also the computation of its subsequent optimal control policy. In this work we propose a paradigm, based on Density Estimation methods, that aims to detect the presence of some already supposed transformations of the state-action space for which the MDP dynamics is invariant. We tested the proposed approach in a discrete toroidal grid environment and in two notorious environments of OpenAI's Gym Learning Suite. The results demonstrate that the model distributional shift is reduced when the dataset is augmented with the data obtained by using the detected symmetries, allowing for a more thorough and data-efficient learning of the transition functions.
A privacy-aware zero interaction smart mobility system
Venue: arXiv cs.SE 2021
Year: 2021

Smart cities often rely on technological innovation to improve citizens' safety and quality of life. This paper presents a novel smart mobility system that aims to facilitate people accessing public mobility while preserving their privacy. The system is based on a zero interaction approach whereby a person can use public transport services without any need to perform explicit actions. Operations related to ticket purchase and validation have been fully automated. The system is also designed with the privacy-by-design paradigm in mind, to preserve user privacy as much as possible. Throughout the paper several technical details are discussed as well to describe a prototype version of the system that was implemented. The prototype has been successfully tested in the city of Imola (Emilia Romagna, Italy) in order to prove the system validity on the field.
Towards intrinsic force sensing and control in parallel soft robots
Venue: arXiv cs.RO 2021
Year: 2021

With soft robotics being increasingly employed in settings demanding high and controlled contact forces, recent research has demonstrated the use of soft robots to estimate or intrinsically sense forces without requiring external sensing mechanisms. Whilst this has mainly been shown in tendon-based continuum manipulators or deformable robots comprising of push-pull rod actuation, fluid drives still pose great challenges due to high actuation variability and nonlinear mechanical system responses. In this work we investigate the capabilities of a hydraulic, parallel soft robot to intrinsically sense and subsequently control contact forces. A comprehensive algorithm is derived for static, quasi-static and dynamic force sensing which relies on fluid volume and pressure information of the system. The algorithm is validated for a single degree-of-freedom soft fluidic actuator. Results indicate that axial forces acting on a single actuator can be estimated with an accuracy of 0.56 +- 0.66N within the validated range of 0 to 6N in a quasi-static configuration. The force sensing methodology is applied to force control in a single actuator as well as the coupled parallel robot. It can be seen that forces are accurately controllable for both systems, with the capability of controlling directional contact forces in case of the multi degree-of-freedom parallel soft robot.
Bi-Mix: Bidirectional Mixing for Domain Adaptive Nighttime Semantic Segmentation
Venue: arXiv cs.CV 2021
Year: 2021

In autonomous driving, learning a segmentation model that can adapt to various environmental conditions is crucial. In particular, copying with severe illumination changes is an impelling need, as models trained on daylight data will perform poorly at nighttime. In this paper, we study the problem of Domain Adaptive Nighttime Semantic Segmentation (DANSS), which aims to learn a discriminative nighttime model with a labeled daytime dataset and an unlabeled dataset, including coarsely aligned day-night image pairs. To this end, we propose a novel Bidirectional Mixing (Bi-Mix) framework for DANSS, which can contribute to both image translation and segmentation adaptation processes. Specifically, in the image translation stage, Bi-Mix leverages the knowledge of day-night image pairs to improve the quality of nighttime image relighting. On the other hand, in the segmentation adaptation stage, Bi-Mix effectively bridges the distribution gap between day and night domains for adapting the model to the night domain. In both processes, Bi-Mix simply operates by mixing two samples without extra hyper-parameters, thus it is easy to implement. Extensive experiments on Dark Zurich and Nighttime Driving datasets demonstrate the advantage of the proposed Bi-Mix and show that our approach obtains state-of-the-art performance in DANSS. Our code is available at https://github.com/ygjwd12345/BiMix.
Global and Local Alignment Networks for Unpaired Image-to-Image Translation
Venue: arXiv cs.CV 2021
Year: 2021

The goal of unpaired image-to-image translation is to produce an output image reflecting the target domain's style while keeping unrelated contents of the input source image unchanged. However, due to the lack of attention to the content change in existing methods, the semantic information from source images suffers from degradation during translation. In the paper, to address this issue, we introduce a novel approach, Global and Local Alignment Networks (GLA-Net). The global alignment network aims to transfer the input image from the source domain to the target domain. To effectively do so, we learn the parameters (mean and standard deviation) of multivariate Gaussian distributions as style features by using an MLP-Mixer based style encoder. To transfer the style more accurately, we employ an adaptive instance normalization layer in the encoder, with the parameters of the target multivariate Gaussian distribution as input. We also adopt regularization and likelihood losses to further reduce the domain gap and produce high-quality outputs. Additionally, we introduce a local alignment network, which employs a pretrained self-supervised model to produce an attention map via a novel local alignment loss, ensuring that the translation network focuses on relevant pixels. Extensive experiments conducted on five public datasets demonstrate that our method effectively generates sharper and more realistic images than existing approaches. Our code is available at https://github.com/ygjwd12345/GLANet.
The ComMA Dataset V0.2: Annotating Aggression and Bias in Multilingual Social Media Discourse
Venue: arXiv cs.CL 2021
Year: 2021

In this paper, we discuss the development of a multilingual dataset annotated with a hierarchical, fine-grained tagset marking different types of aggression and the "context" in which they occur. The context, here, is defined by the conversational thread in which a specific comment occurs and also the "type" of discursive role that the comment is performing with respect to the previous comment. The initial dataset, being discussed here (and made available as part of the ComMA@ICON shared task), consists of a total 15,000 annotated comments in four languages - Meitei, Bangla, Hindi, and Indian English - collected from various social media platforms such as YouTube, Facebook, Twitter and Telegram. As is usual on social media websites, a large number of these comments are multilingual, mostly code-mixed with English. The paper gives a detailed description of the tagset being used for annotation and also the process of developing a multi-label, fine-grained tagset that can be used for marking comments with aggression and bias of various kinds including gender bias, religious intolerance (called communal bias in the tagset), class/caste bias and ethnic/racial bias. We also define and discuss the tags that have been used for marking different the discursive role being performed through the comments, such as attack, defend, etc. We also present a statistical analysis of the dataset as well as results of our baseline experiments with developing an automatic aggression identification system using the dataset developed.
What Stops Learning-based 3D Registration from Working in the Real World?
Venue: arXiv cs.CV 2021
Year: 2021

Much progress has been made on the task of learning-based 3D point cloud registration, with existing methods yielding outstanding results on standard benchmarks, such as ModelNet40, even in the partial-to-partial matching scenario. Unfortunately, these methods still struggle in the presence of real data. In this work, we identify the sources of these failures, analyze the reasons behind them, and propose solutions to tackle them. We summarise our findings into a set of guidelines and demonstrate their effectiveness by applying them to different baseline methods, DCP and IDAM. In short, our guidelines improve both their training convergence and testing accuracy. Ultimately, this translates to a best-practice 3D registration network (BPNet), constituting the first learning-based method able to handle previously-unseen objects in real-world data. Despite being trained only on synthetic data, our model generalizes to real data without any fine-tuning, reaching an accuracy of up to 67% on point clouds of unseen objects obtained with a commercial sensor.
Community-Detection via Hashtag-Graphs for Semi-Supervised NMF Topic Models
Venue: arXiv cs.SI 2021
Year: 2021

Extracting topics from large collections of unstructured text-documents has become a central task in current NLP applications and algorithms like NMF, LDA as well as their generalizations are the well-established current state of the art. However, especially when it comes to short text documents like Tweets, these approaches often lead to unsatisfying results due to the sparsity of the document-feature matrices. Even though, several approaches have been proposed to overcome this sparsity by taking additional information into account, these are merely focused on the aggregation of similar documents and the estimation of word-co-occurrences. This ultimately completely neglects the fact that a lot of topical-information can be actually retrieved from so-called hashtag-graphs by applying common community detection algorithms. Therefore, this paper outlines a novel approach on how to integrate topic structures of hashtag graphs into the estimation of topic models by connecting graph-based community detection and semi-supervised NMF. By applying this approach on recently streamed Twitter data it will be seen that this procedure actually leads to more intuitive and humanly interpretable topics.
Continuation-Passing Style, Defunctionalization, Accumulations, and Associativity
Venue: arXiv cs.PL 2021
Year: 2021

Context: Reynolds showed us how to use continuation-passing style and defunctionalization to transform a recursive interpreter for a language into an abstract machine for programs in that language. The same techniques explain other programming tricks, including zippers and accumulating parameters. Inquiry: Buried within all those applications there is usually a hidden appeal to the algebraic property of associativity. Approach: Our purpose in this paper is to entice associativity out of the shadows and into the limelight. Knowledge: We revisit some well-known applications (factorial, fast reverse, tree flattening, and a compiler for a simple expression language) to spotlight their dependence on associativity. Grounding: We replay developments of these programs through a series of program transformations and data refinements, justified by equational reasoning. Importance: Understanding the crucial role played by associativity clarifies when continuation-passing style and defunctionalization can help and when they cannot, and may prompt other applications of these techniques.