OpenRaiser/Intern-Atlas huggingface dataset:
Approximating Flexible Graph Connectivity via Räcke Tree based Rounding
Venue: arXiv cs.DS 2022
Year: 2022

Flexible graph connectivity is a new network design model introduced by Adjiashvili. It has seen several recent algorithmic advances. Despite these, the approximability even in the setting of a single-pair $(s,t)$ is poorly understood. In our recent work, we raised the question of whether there is poly-logarithmic approximation for the survivable network design version (Flex-SNDP) when the connectivity requirements are fixed constants. In this paper, we adapt a powerful framework for survivable network design recently developed by Chen, Laekhanukit, Liao, and Zhang to give an affirmative answer to the question. The framework of is based on Räcke trees and group Steiner tree rounding. The algorithm and analysis also establishes an upper bound on the integrality gap of an LP relaxation for Flex-SNDP.
Improving AFL++ CmpLog: Tackling the bottlenecks
Venue: arXiv cs.CR 2022
Year: 2022

The performance of the AFL++ CmpLog feature varies considerably for specific programs under test (PUTs). In this paper it is demonstrated that the main cause of the poor performance is low seed entropy, and a lack of deduplication of magic bytes candidates. An improvement is proposed by mapping comparisons to input bytes, in order to track which comparisons are controlled by what input bytes. This mapping is then used to fuzz only the comparison values that are magic byte candidates for that input part. Second, a caching mechanism is introduced to reduce the number of redundant executions. The evaluation of the improved versions shows a significant coverage gain compared to the original AFL++ implementation of CmpLog for all PUTs, without breaking functionality. The proposed solution in this paper provides a solid basis for a redesign of CmpLog.
Collaborative and AI-aided Exam Question Generation using Wikidata in Education
Venue: arXiv cs.IR 2022
Year: 2022

Since the COVID-19 outbreak, the use of digital learning or education platforms has significantly increased. Teachers now digitally distribute homework and provide exercise questions. In both cases, teachers need to continuously develop novel and individual questions. This process can be very time-consuming and should be facilitated and accelerated both through exchange with other teachers and by using Artificial Intelligence (AI) capabilities. To address this need, we propose a multilingual Wikimedia framework that allows for collaborative worldwide teacher knowledge engineering and subsequent AI-aided question generation, test, and correction. As a proof of concept, we present >>PhysWikiQuiz<<, a physics question generation and test engine. Our system (hosted by Wikimedia at https://physwikiquiz.wmflabs.org) retrieves physics knowledge from the open community-curated database Wikidata. It can generate questions in different variations and verify answer values and units using a Computer Algebra System (CAS). We evaluate the performance on a public benchmark dataset at each stage of the system workflow. For an average formula with three variables, the system can generate and correct up to 300 questions for individual students based on a single formula concept name as input by the teacher.
A Survey on the Integration of Machine Learning with Sampling-based Motion Planning
Venue: arXiv cs.RO 2022
Year: 2022

Sampling-based methods are widely adopted solutions for robot motion planning. The methods are straightforward to implement, effective in practice for many robotic systems. It is often possible to prove that they have desirable properties, such as probabilistic completeness and asymptotic optimality. Nevertheless, they still face challenges as the complexity of the underlying planning problem increases, especially under tight computation time constraints, which impact the quality of returned solutions or given inaccurate models. This has motivated machine learning to improve the computational efficiency and applicability of Sampling-Based Motion Planners (SBMPs). This survey reviews such integrative efforts and aims to provide a classification of the alternative directions that have been explored in the literature. It first discusses how learning has been used to enhance key components of SBMPs, such as node sampling, collision detection, distance or nearest neighbor computation, local planning, and termination conditions. Then, it highlights planners that use learning to adaptively select between different implementations of such primitives in response to the underlying problem's features. It also covers emerging methods, which build complete machine learning pipelines that reflect the traditional structure of SBMPs. It also discusses how machine learning has been used to provide data-driven models of robots, which can then be used by a SBMP. Finally, it provides a comparative discussion of the advantages and disadvantages of the approaches covered, and insights on possible future directions of research. An online version of this survey can be found at: https://prx-kinodynamic.github.io/
Methodological proposal to identify the nationality of Twitter users through Random-Forests
Venue: arXiv cs.SI 2022
Year: 2022

We disclose a methodology to determine the participants in discussions and their contributions in social networks with a local relationship (e.g., nationality), providing certain levels of trust and efficiency in the process. The dynamic is a challenge that has demanded studies and some approximations to recent solutions. The study addressed the problem of identifying the nationality of users in the Twitter social network before an opinion request (of a political nature and social participation). The employed methodology classifies, via machine learning, the Twitter users' nationality to carry out opinion studies in three Central American countries. The Random Forests algorithm is used to generate classification models with small training samples, using exclusively numerical characteristics based on the number of times that different interactions among users occur. When averaging the proportions achieved by inferences of the ratio of nationals of each country, in the initial data, an average of 77.40% was calculated, compared to 91.60% averaged after applying the automatic classification model, an average increase of 14.20%. In conclusion, it can be seen that the suggested set of method provides a reasonable approach and efficiency in the face of opinion problems.
Anomaly Detection in Multiplex Dynamic Networks: from Blockchain Security to Brain Disease Prediction
Venue: arXiv cs.LG 2022
Year: 2022

The problem of identifying anomalies in dynamic networks is a fundamental task with a wide range of applications. However, it raises critical challenges due to the complex nature of anomalies, lack of ground truth knowledge, and complex and dynamic interactions in the network. Most existing approaches usually study networks with a single type of connection between vertices, while in many applications interactions between objects vary, yielding multiplex networks. We propose ANOMULY, a general, unsupervised edge anomaly detection framework for multiplex dynamic networks. In each relation type, ANOMULY sees node embeddings at different GNN layers as hierarchical node states and employs a GRU cell to capture temporal properties of the network and update node embeddings over time. We then add an attention mechanism that incorporates information across different types of relations. Our case study on brain networks shows how this approach could be employed as a new tool to understand abnormal brain activity that might reveal a brain disease or disorder. Extensive experiments on nine real-world datasets demonstrate that ANOMULY achieves state-of-the-art performance.
Empowering Language Models with Knowledge Graph Reasoning for Question Answering
Venue: arXiv cs.CL 2022
Year: 2022

Answering open-domain questions requires world knowledge about in-context entities. As pre-trained Language Models (LMs) lack the power to store all required knowledge, external knowledge sources, such as knowledge graphs, are often used to augment LMs. In this work, we propose knOwledge REasOning empowered Language Model (OREO-LM), which consists of a novel Knowledge Interaction Layer that can be flexibly plugged into existing Transformer-based LMs to interact with a differentiable Knowledge Graph Reasoning module collaboratively. In this way, LM guides KG to walk towards the desired answer, while the retrieved knowledge improves LM. By adopting OREO-LM to RoBERTa and T5, we show significant performance gain, achieving state-of-art results in the Closed-Book setting. The performance enhancement is mainly from the KG reasoning's capacity to infer missing relational facts. In addition, OREO-LM provides reasoning paths as rationales to interpret the model's decision.
Generative Long-form Question Answering: Relevance, Faithfulness and Succinctness
Venue: arXiv cs.CL 2022
Year: 2022

In this thesis, we investigated the relevance, faithfulness, and succinctness aspects of Long Form Question Answering (LFQA). LFQA aims to generate an in-depth, paragraph-length answer for a given question, to help bridge the gap between real scenarios and the existing open-domain QA models which can only extract short-span answers. LFQA is quite challenging and under-explored. Few works have been done to build an effective LFQA system. It is even more challenging to generate a good-quality long-form answer relevant to the query and faithful to facts, since a considerable amount of redundant, complementary, or contradictory information will be contained in the retrieved documents. Moreover, no prior work has been investigated to generate succinct answers. We are among the first to research the LFQA task. We pioneered the research direction to improve the answer quality in terms of 1) query-relevance, 2) answer faithfulness, and 3) answer succinctness.
On the Performance of Direct Loss Minimization for Bayesian Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

Direct Loss Minimization (DLM) has been proposed as a pseudo-Bayesian method motivated as regularized loss minimization. Compared to variational inference, it replaces the loss term in the evidence lower bound (ELBO) with the predictive log loss, which is the same loss function used in evaluation. A number of theoretical and empirical results in prior work suggest that DLM can significantly improve over ELBO optimization for some models. However, as we point out in this paper, this is not the case for Bayesian neural networks (BNNs). The paper explores the practical performance of DLM for BNN, the reasons for its failure and its relationship to optimizing the ELBO, uncovering some interesting facts about both algorithms.
Local learning through propagation delays in spiking neural networks
Venue: arXiv cs.NE 2022
Year: 2022

We propose a novel local learning rule for spiking neural networks in which spike propagation times undergo activity-dependent plasticity. Our plasticity rule aligns pre-synaptic spike times to produce a stronger and more rapid response. Inputs are encoded by latency coding and outputs decoded by matching similar patterns of output spiking activity. We demonstrate the use of this method in a three-layer feedfoward network with inputs from a database of handwritten digits. Networks consistently improve their classification accuracy after training, and training with this method also allowed networks to generalize to an input class unseen during training. Our proposed method takes advantage of the ability of spiking neurons to support many different time-locked sequences of spikes, each of which can be activated by different input activations. The proof-of-concept shown here demonstrates the great potential for local delay learning to expand the memory capacity and generalizability of spiking neural networks.
Low Latency Conversion of Artificial Neural Network Models to Rate-encoded Spiking Neural Networks
Venue: arXiv cs.NE 2022
Year: 2022

Spiking neural networks (SNNs) are well suited for resource-constrained applications as they do not need expensive multipliers. In a typical rate-encoded SNN, a series of binary spikes within a globally fixed time window is used to fire the neurons. The maximum number of spikes in this time window is also the latency of the network in performing a single inference, as well as determines the overall energy efficiency of the model. The aim of this paper is to reduce this while maintaining accuracy when converting ANNs to their equivalent SNNs. The state-of-the-art conversion schemes yield SNNs with accuracies comparable with ANNs only for large window sizes. In this paper, we start with understanding the information loss when converting from pre-existing ANN models to standard rate-encoded SNN models. From these insights, we propose a suite of novel techniques that together mitigate the information lost in the conversion, and achieve state-of-art SNN accuracies along with very low latency. Our method achieved a Top-1 SNN accuracy of 98.73% (1 time step) on the MNIST dataset, 76.38% (8 time steps) on the CIFAR-100 dataset, and 93.71% (8 time steps) on the CIFAR-10 dataset. On ImageNet, an SNN accuracy of 75.35%/79.16% was achieved with 100/200 time steps.
Participation Interfaces for Human-Centered AI
Venue: arXiv cs.CY 2022
Year: 2022

Emerging artificial intelligence (AI) applications often balance the preferences and impacts among diverse and contentious stakeholder groups. Accommodating these stakeholder groups during system design, development, and deployment requires tools for the elicitation of disparate system interests and collaboration interfaces supporting negotiation balancing those interests. This paper introduces interactive visual "participation interfaces" for Markov Decision Processes (MDPs) and collaborative ranking problems as examples restoring a human-centered locus of control.
ABANICCO: A New Color Space for Multi-Label Pixel Classification and Color Segmentation
Venue: arXiv cs.CV 2022
Year: 2022

In any computer vision task involving color images, a necessary step is classifying pixels according to color and segmenting the respective areas. However, the development of methods able to successfully complete this task has proven challenging, mainly due to the gap between human color perception, linguistic color terms, and digital representation. In this paper, we propose a novel method combining geometric analysis of color theory, fuzzy color spaces, and multi-label systems for the automatic classification of pixels according to 12 standard color categories (Green, Yellow, Light Orange, Deep Orange, Red, Pink, Purple, Ultramarine, Blue, Teal, Brown, and Neutral). Moreover, we present a robust, unsupervised, unbiased strategy for color naming based on statistics and color theory. ABANICCO was tested against the state of the art in color classification and with the standarized ISCC-NBS color system, providing accurate classification and a standard, easily understandable alternative for hue naming recognizable by humans and machines. We expect this solution to become the base to successfully tackle a myriad of problems in all fields of computer vision, such as region characterization, histopathology analysis, fire detection, product quality prediction, object description, and hyperspectral imaging.
On the Compositional Generalization Gap of In-Context Learning
Venue: arXiv cs.CL 2022
Year: 2022

Pretrained large generative language models have shown great performance on many tasks, but exhibit low compositional generalization abilities. Scaling such models has been shown to improve their performance on various NLP tasks even just by conditioning them on a few examples to solve the task without any fine-tuning (also known as in-context learning). In this work, we look at the gap between the in-distribution (ID) and out-of-distribution (OOD) performance of such models in semantic parsing tasks with in-context learning. In the ID settings, the demonstrations are from the same split (test or train) that the model is being evaluated on, and in the OOD settings, they are from the other split. We look at how the relative generalization gap of in-context learning evolves as models are scaled up. We evaluate four model families, OPT, BLOOM, CodeGen and Codex on three semantic parsing datasets, CFQ, SCAN and GeoQuery with different number of exemplars, and observe a trend of decreasing relative generalization gap as models are scaled up.
Virtually turning robotic manipulators into worn devices: opening new horizons for wearable assistive robotics
Venue: arXiv cs.RO 2022
Year: 2022

Robotic sensorimotor extensions (supernumerary limbs, prosthesis, handheld tools) are worn devices used to interact with the nearby environment, whether to assist the capabilities of impaired users or to enhance the dexterity of industrial operators. Despite numerous mechanical achievements, embedding these robotics devices remains critical due to their weight and discomfort. To emancipate from these mechanical constraints, we propose a new hybrid system using a virtually worn robotic arm in augmented-reality, and a real robotic manipulator servoed on such virtual representation. We aim at bringing an illusion of wearing a robotic system while its weight is fully deported, thinking that this approach could open new horizons for the study of wearable robotics without any intrinsic impairment of the human movement abilities.
Spectral Heuristics Applied to Vertex Reliability
Venue: arXiv cs.DM 2022
Year: 2022

The operability of a network concerns its ability to remain operational, despite possible failures in its links or equipment. One may model the network through a graph to evaluate and increase this operability. Its vertices and edges correspond to the users equipment and their connections, respectively. In this article, the problem addressed is identifying the topological change in the graph that leads to a greater increase in the operability of the associated network, considering the case in which failure occurs in the network equipment only. More specifically, we propose two spectral heuristics to improve the vertex reliability in graphs through a single edge insertion. The performance these heuristics and others that are usually found in the literature are evaluated by computational experiments with 22000 graphs of orders 10 up to 20, generated using the Models Erdos-Renyi, Barabasi-Albert, and Watts-Strogatz. From the experiments, it can be observed through analysis and application of statistical test, that one of the spectral heuristics presented a superior performance in relation to the others.
The wrong direction of Jensen's inequality is algorithmically right
Venue: arXiv cs.CC 2022
Year: 2022

Let $\mathcal{A}$ be an algorithm with expected running time $e^X$, conditioned on the value of some random variable $X$. We construct an algorithm $\mathcal{A'}$ with expected running time $O(e^{E[X]})$, that fully executes $\mathcal{A}$. In particular, an algorithm whose running time is a random variable $T$ can be converted to one with expected running time $O(e^{E[\ln T]})$, which is never worse than $O(E[T])$. No information about the distribution of $X$ is required for the construction of $\mathcal{A}'$.
ConvFormer: Combining CNN and Transformer for Medical Image Segmentation
Venue: arXiv cs.CV 2022
Year: 2022

Convolutional neural network (CNN) based methods have achieved great successes in medical image segmentation, but their capability to learn global representations is still limited due to using small effective receptive fields of convolution operations. Transformer based methods are capable of modelling long-range dependencies of information for capturing global representations, yet their ability to model local context is lacking. Integrating CNN and Transformer to learn both local and global representations while exploring multi-scale features is instrumental in further improving medical image segmentation. In this paper, we propose a hierarchical CNN and Transformer hybrid architecture, called ConvFormer, for medical image segmentation. ConvFormer is based on several simple yet effective designs. (1) A feed forward module of Deformable Transformer (DeTrans) is re-designed to introduce local information, called Enhanced DeTrans. (2) A residual-shaped hybrid stem based on a combination of convolutions and Enhanced DeTrans is developed to capture both local and global representations to enhance representation ability. (3) Our encoder utilizes the residual-shaped hybrid stem in a hierarchical manner to generate feature maps in different scales, and an additional Enhanced DeTrans encoder with residual connections is built to exploit multi-scale features with feature maps of different scales as input. Experiments on several datasets show that our ConvFormer, trained from scratch, outperforms various CNN- or Transformer-based architectures, achieving state-of-the-art performance.
One-bit mmWave MIMO Channel Estimation using Deep Generative Networks
Venue: arXiv cs.IT 2022
Year: 2022

As future wireless systems trend towards higher carrier frequencies and large antenna arrays, receivers with one-bit analog-to-digital converters (ADCs) are being explored owing to their reduced power consumption. However, the combination of large antenna arrays and one-bit ADCs makes channel estimation challenging. In this paper, we formulate channel estimation from a limited number of one-bit quantized pilot measurements as an inverse problem and reconstruct the channel by optimizing the input vector of a pre-trained deep generative model with the objective of maximizing a novel correlation-based loss function. We observe that deep generative priors adapted to the underlying channel model significantly outperform Bernoulli-Gaussian Approximate Message Passing (BG-GAMP), while a single generative model that uses a conditional input to distinguish between Line-of-Sight (LOS) and Non-Line-of-Sight (NLOS) channel realizations outperforms BG-GAMP on LOS channels and achieves comparable performance on NLOS channels in terms of the normalized channel reconstruction error.
Cooperative Energy and Time-Optimal Lane Change Maneuvers with Minimal Highway Traffic Disruption
Venue: arXiv cs.RO 2022
Year: 2022

We derive optimal control policies for a Connected Automated Vehicle (CAV) and cooperating neighboring CAVs to carry out a lane change maneuver consisting of a longitudinal phase where the CAV properly positions itself relative to the cooperating neighbors and a lateral phase where it safely changes lanes. In contrast to prior work on this problem, where the CAV "selfishly" only seeks to minimize its maneuver time, we seek to ensure that the fast-lane traffic flow is minimally disrupted (through a properly defined metric). Additionally, when performing lane-changing maneuvers, we optimally select the cooperating vehicles from a set of feasible neighboring vehicles and experimentally show that the highway throughput is improved compared to the baseline case of human-driven vehicles changing lanes with no cooperation. When feasible solutions do not exist for a given maximal allowable disruption, we include a time relaxation method trading off a longer maneuver time with reduced disruption. Our analysis is also extended to multiple sequential maneuvers. Simulation results show the effectiveness of our controllers in terms of safety guarantees and up to 16% and 90% average throughput and maneuver time improvement respectively when compared to maneuvers with no cooperation.