OpenRaiser/Intern-Atlas huggingface dataset:
Using Game Theory to maximize the chance of victory in two-player sports
Venue: arXiv cs.GT 2021
Year: 2021

Game Theory concepts have been successfully applied in a wide variety of domains over the past decade. Sports and games are one of the popular areas of game theory application owing to its merits and benefits in solving complex scenarios. With recent advancements in technology, the technical and analytical assistance available to players before the match, during game-play and after the match in the form of post-match analysis for any kind of sport has improved to a great extent. In this paper, we propose three novel approaches towards the development of a tool that can assist the players by providing detailed analysis of optimal decisions so that the player is well prepared with the most appropriate strategy which would produce a favourable result for a given opponent's strategy. We also describe how the system changes when we consider real-time game-play wherein the history of the opponent's strategies in the current rally is also taken into consideration while suggesting.
Self-Supervised Graph Representation Learning via Topology Transformations
Venue: arXiv cs.LG 2021
Year: 2021

We present the Topology Transformation Equivariant Representation learning, a general paradigm of self-supervised learning for node representations of graph data to enable the wide applicability of Graph Convolutional Neural Networks (GCNNs). We formalize the proposed model from an information-theoretic perspective, by maximizing the mutual information between topology transformations and node representations before and after the transformations. We derive that maximizing such mutual information can be relaxed to minimizing the cross entropy between the applied topology transformation and its estimation from node representations. In particular, we seek to sample a subset of node pairs from the original graph and flip the edge connectivity between each pair to transform the graph topology. Then, we self-train a representation encoder to learn node representations by reconstructing the topology transformations from the feature representations of the original and transformed graphs. In experiments, we apply the proposed model to the downstream node classification, graph classification and link prediction tasks, and results show that the proposed method outperforms the state-of-the-art unsupervised approaches.
The Perturbed Prox-Preconditioned SPIDER algorithm for EM-based large scale learning
Venue: arXiv cs.LG 2021
Year: 2021

Incremental Expectation Maximization (EM) algorithms were introduced to design EM for the large scale learning framework by avoiding the full data set to be processed at each iteration. Nevertheless, these algorithms all assume that the conditional expectations of the sufficient statistics are explicit. In this paper, we propose a novel algorithm named Perturbed Prox-Preconditioned SPIDER (3P-SPIDER), which builds on the Stochastic Path Integral Differential EstimatoR EM (SPIDER-EM) algorithm. The 3P-SPIDER algorithm addresses many intractabilities of the E-step of EM; it also deals with non-smooth regularization and convex constraint set. Numerical experiments show that 3P-SPIDER outperforms other incremental EM methods and discuss the role of some design parameters.
FENXI: Deep-learning Traffic Analytics at the Edge
Venue: arXiv cs.NI 2021
Year: 2021

Live traffic analysis at the first aggregation point in the ISP network enables the implementation of complex traffic engineering policies but is limited by the scarce processing capabilities, especially for Deep Learning (DL) based analytics. The introduction of specialized hardware accelerators i.e., Tensor Processing Unit (TPU), offers the opportunity to enhance the processing capabilities of network devices at the edge. Yet, to date, no packet processing pipeline is capable of offering DL-based analysis capabilities in the data-plane, without interfering with network operations. In this paper, we present FENXI, a system to run complex analytics by leveraging TPU. The design of FENXI decouples forwarding operations and traffic analytics which operates at different granularities i.e., packet and flow levels. We conceive two independent modules that asynchronously communicate to exchange network data and analytics results, and design data structures to extract flow level statistics without impacting per-packet processing. We prototyped and evaluated FENXI on general-purpose servers considering both adversarial and realistic network conditions. Our analysis shows that FENXI can sustain 100 Gbps line rate traffic processing requiring only limited resources, while also dynamically adapting to variable network conditions.
ScalaBFS: A Scalable BFS Accelerator on HBM-Enhanced FPGAs
Venue: arXiv cs.AR 2021
Year: 2021

High Bandwidth Memory (HBM) provides massive aggregated memory bandwidth by exposing multiple memory channels to the processing units. To achieve high performance, an accelerator built on top of an FPGA configured with HBM (i.e., FPGA-HBM platform) needs to scale its performance according to the available memory channels. In this paper, we propose an accelerator for BFS (Breadth-First Search) algorithm, named as ScalaBFS, that builds multiple processing elements to sufficiently exploit the high bandwidth of HBM to improve efficiency. We implement the prototype system of ScalaBFS and conduct BFS in both real-world and synthetic scale-free graphs on Xilinx Alveo U280 FPGA card real hardware. The experimental results show that ScalaBFS scales its performance almost linearly according to the available memory pseudo channels (PCs) from the HBM2 subsystem of U280. By fully using the 32 PCs and building 64 processing elements (PEs) on U280, ScalaBFS achieves a performance up to 19.7 GTEPS (Giga Traversed Edges Per Second). When conducting BFS in sparse real-world graphs, ScalaBFS achieves equivalent GTEPS to Gunrock running on the state-of-art Nvidia V100 GPU that features 64-PC HBM2 (twice memory bandwidth than U280).
GAN for Vision, KG for Relation: a Two-stage Deep Network for Zero-shot Action Recognition
Venue: arXiv cs.CV 2021
Year: 2021

Zero-shot action recognition can recognize samples of unseen classes that are unavailable in training by exploring common latent semantic representation in samples. However, most methods neglected the connotative relation and extensional relation between the action classes, which leads to the poor generalization ability of the zero-shot learning. Furthermore, the learned classifier incline to predict the samples of seen class, which leads to poor classification performance. To solve the above problems, we propose a two-stage deep neural network for zero-shot action recognition, which consists of a feature generation sub-network serving as the sampling stage and a graph attention sub-network serving as the classification stage. In the sampling stage, we utilize a generative adversarial networks (GAN) trained by action features and word vectors of seen classes to synthesize the action features of unseen classes, which can balance the training sample data of seen classes and unseen classes. In the classification stage, we construct a knowledge graph (KG) based on the relationship between word vectors of action classes and related objects, and propose a graph convolution network (GCN) based on attention mechanism, which dynamically updates the relationship between action classes and objects, and enhances the generalization ability of zero-shot learning. In both stages, we all use word vectors as bridges for feature generation and classifier generalization from seen classes to unseen classes. We compare our method with state-of-the-art methods on UCF101 and HMDB51 datasets. Experimental results show that our proposed method improves the classification performance of the trained classifier and achieves higher accuracy.
Bridging the Gap Between Explainable AI and Uncertainty Quantification to Enhance Trustability
Venue: arXiv cs.AI 2021
Year: 2021

After the tremendous advances of deep learning and other AI methods, more attention is flowing into other properties of modern approaches, such as interpretability, fairness, etc. combined in frameworks like Responsible AI. Two research directions, namely Explainable AI and Uncertainty Quantification are becoming more and more important, but have been so far never combined and jointly explored. In this paper, I show how both research areas provide potential for combination, why more research should be done in this direction and how this would lead to an increase in trustability in AI systems.
Estimating Redundancy in Clinical Text
Venue: arXiv cs.CL 2021
Year: 2021

The current mode of use of Electronic Health Record (EHR) elicits text redundancy. Clinicians often populate new documents by duplicating existing notes, then updating accordingly. Data duplication can lead to a propagation of errors, inconsistencies and misreporting of care. Therefore, quantifying information redundancy can play an essential role in evaluating innovations that operate on clinical narratives. This work is a quantitative examination of information redundancy in EHR notes. We present and evaluate two strategies to measure redundancy: an information-theoretic approach and a lexicosyntactic and semantic model. We evaluate the measures by training large Transformer-based language models using clinical text from a large openly available US-based ICU dataset and a large multi-site UK based Trust. By comparing the information-theoretic content of the trained models with open-domain language models, the language models trained using clinical text have shown ~1.5x to ~3x less efficient than open-domain corpora. Manual evaluation shows a high correlation with lexicosyntactic and semantic redundancy, with averages ~43 to ~65%.
GCNBoost: Artwork Classification by Label Propagation through a Knowledge Graph
Venue: arXiv cs.LG 2021
Year: 2021

The rise of digitization of cultural documents offers large-scale contents, opening the road for development of AI systems in order to preserve, search, and deliver cultural heritage. To organize such cultural content also means to classify them, a task that is very familiar to modern computer science. Contextual information is often the key to structure such real world data, and we propose to use it in form of a knowledge graph. Such a knowledge graph, combined with content analysis, enhances the notion of proximity between artworks so it improves the performances in classification tasks. In this paper, we propose a novel use of a knowledge graph, that is constructed on annotated data and pseudo-labeled data. With label propagation, we boost artwork classification by training a model using a graph convolutional network, relying on the relationships between entities of the knowledge graph. Following a transductive learning framework, our experiments show that relying on a knowledge graph modeling the relations between labeled data and unlabeled data allows to achieve state-of-the-art results on multiple classification tasks on a dataset of paintings, and on a dataset of Buddha statues. Additionally, we show state-of-the-art results for the difficult case of dealing with unbalanced data, with the limitation of disregarding classes with extremely low degrees in the knowledge graph.
Empirical Error Modeling Improves Robustness of Noisy Neural Sequence Labeling
Venue: arXiv cs.CL 2021
Year: 2021

Despite recent advances, standard sequence labeling systems often fail when processing noisy user-generated text or consuming the output of an Optical Character Recognition (OCR) process. In this paper, we improve the noise-aware training method by proposing an empirical error generation approach that employs a sequence-to-sequence model trained to perform translation from error-free to erroneous text. Using an OCR engine, we generated a large parallel text corpus for training and produced several real-world noisy sequence labeling benchmarks for evaluation. Moreover, to overcome the data sparsity problem that exacerbates in the case of imperfect textual input, we learned noisy language model-based embeddings. Our approach outperformed the baseline noise generation and error correction techniques on the erroneous sequence labeling data sets. To facilitate future research on robustness, we make our code, embeddings, and data conversion scripts publicly available.
Pruned Collapsed Projection-Aggregation Decoding of Reed-Muller Codes
Venue: arXiv cs.IT 2021
Year: 2021

The paper proposes to decode Reed-Muller (RM) codes by projecting onto only a few subspaces such that the number of projections is significantly reduced. It reveals that the probability that error pairs are canceled simultaneously in two different projections is determined by their intersection size. Then, correlation coefficient which indicates the intersection size of two subspaces in a collection is introduced for collecting subspaces. Simulation results show that our proposed approach with a small number of projections onto collected subspaces performs close to the original approach.
Flexible Table Recognition and Semantic Interpretation System
Venue: arXiv cs.CV 2021
Year: 2021

Table extraction is an important but still unsolved problem. In this paper, we introduce a flexible and modular table extraction system. We develop two rule-based algorithms that perform the complete table recognition process, including table detection and segmentation, and support the most frequent table formats. Moreover, to incorporate the extraction of semantic information, we develop a graph-based table interpretation method. We conduct extensive experiments on the challenging table recognition benchmarks ICDAR 2013 and ICDAR 2019, achieving results competitive with state-of-the-art approaches. Our complete information extraction system exhibited a high F1 score of 0.7380. To support future research on information extraction from documents, we make the resources (ground-truth annotations, evaluation scripts, algorithm parameters) from our table interpretation experiment publicly available.
The Complexity of Subelection Isomorphism Problems
Venue: arXiv cs.GT 2021
Year: 2021

We study extensions of the Election Isomorphism problem, focused on the existence of isomorphic subelections. Specifically, we propose the Subelection Isomorphism and the Maximum Common Subelection problems and study their computational complexity and approximability. Using our problems in experiments, we provide some insights into the nature of several statistical models of elections.
VerLoc: Verifiable Localization in Decentralized Systems
Venue: arXiv cs.CR 2021
Year: 2021

We tackle the challenge of reliably determining the geo-location of nodes in decentralized networks, considering adversarial settings and without depending on any trusted landmarks. In particular, we consider active adversaries that control a subset of nodes, announce false locations and strategically manipulate measurements. To address this problem we propose, implement and evaluate VerLoc, a system that allows verifying the claimed geo-locations of network nodes in a fully decentralized manner. VerLoc securely schedules roundtrip time (RTT) measurements between randomly chosen pairs of nodes. Trilateration is then applied to the set of measurements to verify claimed geo-locations. We evaluate VerLoc both with simulations and in the wild using a prototype implementation integrated in the Nym network (currently run by thousands of nodes). We find that VerLoc can localize nodes in the wild with a median error of 60 km, and that in attack simulations it is capable of detecting and filtering out adversarial timing manipulations for network setups with up to 20 % malicious nodes.
Extending rational models of communication from beliefs to actions
Venue: arXiv cs.CL 2021
Year: 2021

Speakers communicate to influence their partner's beliefs and shape their actions. Belief- and action-based objectives have been explored independently in recent computational models, but it has been challenging to explicitly compare or integrate them. Indeed, we find that they are conflated in standard referential communication tasks. To distinguish these accounts, we introduce a new paradigm called signaling bandits, generalizing classic Lewis signaling games to a multi-armed bandit setting where all targets in the context have some relative value. We develop three speaker models: a belief-oriented speaker with a purely informative objective; an action-oriented speaker with an instrumental objective; and a combined speaker which integrates the two by inducing listener beliefs that generally lead to desirable actions. We then present a series of simulations demonstrating that grounding production choices in future listener actions results in relevance effects and flexible uses of nonliteral language. More broadly, our findings suggest that language games based on richer decision problems are a promising avenue for insight into rational communication.
Learning Generative Prior with Latent Space Sparsity Constraints
Venue: arXiv cs.LG 2021
Year: 2021

We address the problem of compressed sensing using a deep generative prior model and consider both linear and learned nonlinear sensing mechanisms, where the nonlinear one involves either a fully connected neural network or a convolutional neural network. Recently, it has been argued that the distribution of natural images do not lie in a single manifold but rather lie in a union of several submanifolds. We propose a sparsity-driven latent space sampling (SDLSS) framework and develop a proximal meta-learning (PML) algorithm to enforce sparsity in the latent space. SDLSS allows the range-space of the generator to be considered as a union-of-submanifolds. We also derive the sample complexity bounds within the SDLSS framework for the linear measurement model. The results demonstrate that for a higher degree of compression, the SDLSS method is more efficient than the state-of-the-art method. We first consider a comparison between linear and nonlinear sensing mechanisms on Fashion-MNIST dataset and show that the learned nonlinear version is superior to the linear one. Subsequent comparisons with the deep compressive sensing (DCS) framework proposed in the literature are reported. We also consider the effect of the dimension of the latent space and the sparsity factor in validating the SDLSS framework. Performance quantification is carried out by employing three objective metrics: peak signal-to-noise ratio (PSNR), structural similarity index metric (SSIM), and reconstruction error (RE).
Reservoir Computing based on Mutually Injected Phase Modulated Semiconductor Lasers as a monolithic integrated hardware accelerator
Venue: arXiv cs.ET 2021
Year: 2021

In this paper we propose and numerically study a neuromorphic computing scheme that applies delay-based reservoir computing in a laser system consisting of two mutually coupled phase modulated lasers. The scheme can be monolithic integrated in a straightforward manner and alleviates the need for external optical injection, as the data can be directly applied on the on-chip phase modulator placed between the two lasers. The scheme also offers the benefit of increasing the nodes compared to a reservoir computing system using either one laser under feedback or laser under feedback and optical injection. Numerical simulations assess the performance of the integrated reservoir computing system in dispersion compensation tasks in short-reach optical communication systems. We numerically demonstrate that the proposed platform can recover severely distorted 25 Gbaud PAM-4 signals for transmission distances exceeding 50km and outperform other competing delay-based reservoir computing systems relying on optical feedback. The proposed scheme, thanks to its compactness and simplicity, can play the role of a monolithic integrated hardware accelerator in a wide range of application requiring high speed real time processing.
Team NimbRo's UGV Solution for Autonomous Wall Building and Fire Fighting at MBZIRC 2020
Venue: arXiv cs.RO 2021
Year: 2021

Autonomous robotic systems for various applications including transport, mobile manipulation, and disaster response are becoming more and more complex. Evaluating and analyzing such systems is challenging. Robotic competitions are designed to benchmark complete robotic systems on complex state-of-the-art tasks. Participants compete in defined scenarios under equal conditions. We present our UGV solution developed for the Mohamed Bin Zayed International Robotics Challenge 2020. Our hard- and software components to address the challenge tasks of wall building and fire fighting are integrated into a fully autonomous system. The robot consists of a wheeled omnidirectional base, a 6 DoF manipulator arm equipped with a magnetic gripper, a highly efficient storage system to transport box-shaped objects, and a water spraying system to fight fires. The robot perceives its environment using 3D LiDAR as well as RGB and thermal camera-based perception modules, is capable of picking box-shaped objects and constructing a pre-defined wall structure, as well as detecting and localizing heat sources in order to extinguish potential fires. A high-level planner solves the challenge tasks using the robot skills. We analyze and discuss our successful participation during the MBZIRC 2020 finals, present further experiments, and provide insights to our lessons learned.
On the extension complexity of polytopes separating subsets of the Boolean cube
Venue: arXiv cs.CG 2021
Year: 2021

We show that 1. for every $A\subseteq \{0, 1\}^n$, there exists a polytope $P\subseteq \mathbb{R}^n$ with $P \cap \{0, 1\}^n = A$ and extension complexity $O(2^{n/2})$, 2. there exists an $A\subseteq \{0, 1\}^n$ such that the extension complexity of any $P$ with $P\cap \{0, 1\}^n = A$ must be at least $2^{\frac{n}{3}(1-o(1))}$. We also remark that the extension complexity of any 0/1-polytope in $\mathbb{R}^n$ is at most $O(2^n/n)$ and pose the problem whether the upper bound can be improved to $O(2^{cn})$, for $c<1$.
Information algebras of coherent sets of gambles in general possibility spaces
Venue: arXiv cs.AI 2021
Year: 2021

In this paper, we show that coherent sets of gambles can be embedded into the algebraic structure of information algebra. This leads firstly, to a new perspective of the algebraic and logical structure of desirability and secondly, it connects desirability, hence imprecise probabilities, to other formalism in computer science sharing the same underlying structure. Both the domain-free and the labeled view of the information algebra of coherent sets of gambles are presented, considering general possibility spaces.
Evolutionary Algorithms for Designing Reversible Cellular Automata
Venue: arXiv cs.NE 2021
Year: 2021

Reversible Cellular Automata (RCA) are a particular kind of shift-invariant transformations characterized by a dynamics composed only of disjoint cycles. They have many applications in the simulation of physical systems, cryptography and reversible computing. In this work, we formulate the search of a specific class of RCA -- namely, those whose local update rules are defined by conserved landscapes -- as an optimization problem to be tackled with Genetic Algorithms (GA) and Genetic Programming (GP). In particular, our experimental investigation revolves around three different research questions, which we address through a single-objective, a multi-objective, and a lexicographic approach. The results obtained from our experiments corroborate the previous findings and shed new light on 1) the difficulty of the associated optimization problem for GA and GP, 2) the relevance of conserved landscape CA in the domain of cryptography and reversible computing, and 3) the relationship between the reversibility property and the Hamming weight.