OpenRaiser/Intern-Atlas huggingface dataset:
A robust GMRES algorithm in Tensor Train format
Venue: arXiv cs.DC 2022
Year: 2022

We consider the solution of linear systems with tensor product structure using a GMRES algorithm. In order to cope with the computational complexity in large dimension both in terms of floating point operations and memory requirement, our algorithm is based on low-rank tensor representation, namely the Tensor Train format. In a backward error analysis framework, we show how the tensor approximation affects the accuracy of the computed solution. With the bacwkward perspective, we investigate the situations where the $(d+1)$-dimensional problem to be solved results from the concatenation of a sequence of $d$-dimensional problems (like parametric linear operator or parametric right-hand side problems), we provide backward error bounds to relate the accuracy of the $(d+1)$-dimensional computed solution with the numerical quality of the sequence of $d$-dimensional solutions that can be extracted form it. This enables to prescribe convergence threshold when solving the $(d+1)$-dimensional problem that ensures the numerical quality of the $d$-dimensional solutions that will be extracted from the $(d+1)$-dimensional computed solution once the solver has converged. The above mentioned features are illustrated on a set of academic examples of varying dimensions and sizes.
Binary optimal linear codes with various hull dimensions and entanglement-assisted QECC
Venue: arXiv cs.IT 2022
Year: 2022

The hull of a linear code $C$ is the intersection of $C$ with its dual. To the best of our knowledge, there are very few constructions of binary linear codes with the hull dimension $\ge 2$ except for self-orthogonal codes. We propose a building-up construction to obtain a plenty of binary $[n+2, k+1]$ codes with hull dimension $\ell, \ell +1$, or $\ell +2$ from a given binary $[n,k]$ code with hull dimension $\ell$. In particular, with respect to hull dimensions 1 and 2, we construct all binary optimal $[n, k]$ codes of lengths up to 13. With respect to hull dimensions 3, 4, and 5, we construct all binary optimal $[n,k]$ codes of lengths up to 12 and the best possible minimum distances of $[13,k]$ codes for $3 \le k \le 10$. As an application, we apply our binary optimal codes with a given hull dimension to construct several entanglement-assisted quantum error-correcting codes(EAQECC) with the best known parameters.
Hierarchical Federated Learning with Momentum Acceleration in Multi-Tier Networks
Venue: arXiv cs.LG 2022
Year: 2022

In this paper, we propose Hierarchical Federated Learning with Momentum Acceleration (HierMo), a three-tier worker-edge-cloud federated learning algorithm that applies momentum for training acceleration. Momentum is calculated and aggregated in the three tiers. We provide convergence analysis for HierMo, showing a convergence rate of O(1/T). In the analysis, we develop a new approach to characterize model aggregation, momentum aggregation, and their interactions. Based on this result, {we prove that HierMo achieves a tighter convergence upper bound compared with HierFAVG without momentum}. We also propose HierOPT, which optimizes the aggregation periods (worker-edge and edge-cloud aggregation periods) to minimize the loss given a limited training time.
Planning with Occluded Traffic Agents using Bi-Level Variational Occlusion Models
Venue: arXiv cs.LG 2022
Year: 2022

Reasoning with occluded traffic agents is a significant open challenge for planning for autonomous vehicles. Recent deep learning models have shown impressive results for predicting occluded agents based on the behaviour of nearby visible agents; however, as we show in experiments, these models are difficult to integrate into downstream planning. To this end, we propose Bi-level Variational Occlusion Models (BiVO), a two-step generative model that first predicts likely locations of occluded agents, and then generates likely trajectories for the occluded agents. In contrast to existing methods, BiVO outputs a trajectory distribution which can then be sampled from and integrated into standard downstream planning. We evaluate the method in closed-loop replay simulation using the real-world nuScenes dataset. Our results suggest that BiVO can successfully learn to predict occluded agent trajectories, and these predictions lead to better subsequent motion plans in critical scenarios.
Environment-Aware AUV Trajectory Design and Resource Management for Multi-Tier Underwater Computing
Venue: arXiv cs.DC 2022
Year: 2022

The Internet of underwater things (IoUT) is envisioned to be an essential part of maritime activities. Given the IoUT devices' wide-area distribution and constrained transmit power, autonomous underwater vehicles (AUVs) have been widely adopted for collecting and forwarding the data sensed by IoUT devices to the surface-stations. In order to accommodate the diverse requirements of IoUT applications, it is imperative to conceive a multi-tier underwater computing (MTUC) framework by carefully harnessing both the computing and the communications as well as the storage resources of both the surface-station and of the AUVs as well as of the IoUT devices. Furthermore, to meet the stringent energy constraints of the IoUT devices and to reduce the operating cost of the MTUC framework, a joint environment-aware AUV trajectory design and resource management problem is formulated, which is a high-dimensional NP-hard problem. To tackle this challenge, we first transform the problem into a Markov decision process (MDP) and solve it with the aid of the asynchronous advantage actor-critic (A3C) algorithm. Our simulation results demonstrate the superiority of our scheme.
A new band selection approach based on information theory and support vector machine for hyperspectral images reduction and classification
Venue: arXiv cs.CV 2022
Year: 2022

The high dimensionality of hyperspectral images consisting of several bands often imposes a big computational challenge for image processing. Therefore, spectral band selection is an essential step for removing the irrelevant, noisy and redundant bands. Consequently increasing the classification accuracy. However, identification of useful bands from hundreds or even thousands of related bands is a nontrivial task. This paper aims at identifying a small set of highly discriminative bands, for improving computational speed and prediction accuracy. Hence, we proposed a new strategy based on joint mutual information to measure the statistical dependence and correlation between the selected bands and evaluate the relative utility of each one to classification. The proposed filter approach is compared to an effective reproduced filters based on mutual information. Simulations results on the hyperpectral image HSI AVIRIS 92AV3C using the SVM classifier have shown that the effective proposed algorithm outperforms the reproduced filters strategy performance. Keywords-Hyperspectral images, Classification, band Selection, Joint Mutual Information, dimensionality reduction ,correlation, SVM.
Channel-Aware Ordered Successive Relaying with Finite-Blocklength Coding
Venue: arXiv cs.IT 2022
Year: 2022

Successive relaying can improve the transmission rate by allowing the source and relays to transmit messages simultaneously, but it may cause severe inter-relay interference (IRI). IRI cancellation schemes have been proposed to mitigate IRI. However, interference cancellation methods have a high risk of error propagation, resulting in a severe transmission rate loss in finite blocklength regimes. Thus, jointly decoding for successive relaying with finite-blocklength coding (FBC) remains a challenge. In this paper, we present an optimized channel-aware ordered successive relaying protocol with finite-blocklength coding (CAO-SIR-FBC), which can recover the rate loss by carefully adapting the relay transmission order and rate. We analyze the average throughput of the CAO-SIR-FBC method, based on which a closed-form expression in a high signal-to-noise regime (SNR) is presented. Average throughput analysis and simulations show that CAO-SIR-FBC outperforms conventional two-timeslot half-duplex relaying in terms of spectral efficiency.
Autoregressive Structured Prediction with Language Models
Venue: arXiv cs.CL 2022
Year: 2022

Recent years have seen a paradigm shift in NLP towards using pretrained language models ({PLM}) for a wide range of tasks. However, there are many difficult design decisions to represent structures (e.g. tagged text, coreference chains) in a way such that they can be captured by PLMs. Prior work on structured prediction with PLMs typically flattens the structured output into a sequence, which limits the quality of structural information being learned and leads to inferior performance compared to classic discriminative models. In this work, we describe an approach to model structures as sequences of actions in an autoregressive manner with PLMs, allowing in-structure dependencies to be learned without any loss. Our approach achieves the new state-of-the-art on all the structured prediction tasks we looked at, namely, named entity recognition, end-to-end relation extraction, and coreference resolution.
ClipBot: an educational, physically impaired robot that learns to walk via genetic algorithm optimization
Venue: arXiv cs.RO 2022
Year: 2022

Educational robots allow experimenting with a variety of principles from mechanics, electronics, and informatics. Here we propose ClipBot, a low-cost, do-it-yourself, robot whose skeleton is made of two paper clips. An Arduino nano microcontroller actuates two servo motors that move the paper clips. However, such mechanical configuration confers physical impairments to movement. This creates the need for and allows experimenting with artificial intelligence methods to overcome hardware limitations. We report our experience in the usage of this robot during the study week 'fascinating informatics', organized by the Swiss Foundation Schweizer Jugend Forscht (www.sjf.ch). Students at the high school level were asked to implement a genetic algorithm to optimize the movements of the robot until it learned to walk. Such a methodology allowed the robot to learn the motor actuation scheme yielding straight movement in the forward direction using less than 20 iterations.
Online TSP with Known Locations
Venue: arXiv cs.DS 2022
Year: 2022

In this paper, we consider the Online Traveling Salesperson Problem (OLTSP) where the locations of the requests are known in advance, but not their arrival times. We study both the open variant, in which the algorithm is not required to return to the origin when all the requests are served, as well as the closed variant, in which the algorithm has to return to the origin after serving all the requests. Our aim is to measure the impact of the extra knowledge of the locations on the competitiveness of the problem. We present an online 3/2-competitive algorithm for the general case and a matching lower bound for both the open and the closed variant. Then, we focus on some interesting metric spaces (ring, star, semi-line), providing both lower bounds and polynomial time online algorithms for the problem.
Monotonic segmental attention for automatic speech recognition
Venue: arXiv cs.CL 2022
Year: 2022

We introduce a novel segmental-attention model for automatic speech recognition. We restrict the decoder attention to segments to avoid quadratic runtime of global attention, better generalize to long sequences, and eventually enable streaming. We directly compare global-attention and different segmental-attention modeling variants. We develop and compare two separate time-synchronous decoders, one specifically taking the segmental nature into account, yielding further improvements. Using time-synchronous decoding for segmental models is novel and a step towards streaming applications. Our experiments show the importance of a length model to predict the segment boundaries. The final best segmental-attention model using segmental decoding performs better than global-attention, in contrast to other monotonic attention approaches in the literature. Further, we observe that the segmental model generalizes much better to long sequences of up to several minutes.
Hybrid HMM Decoder For Convolutional Codes By Joint Trellis-Like Structure and Channel Prior
Venue: arXiv cs.IT 2022
Year: 2022

The anti-interference capability of wireless links is a physical layer problem for edge computing. Although convolutional codes have inherent error correction potential due to the redundancy introduced in the data, the performance of the convolutional code is drastically degraded due to multipath effects on the channel. In this paper, we propose the use of a Hidden Markov Model (HMM) for the reconstruction of convolutional codes and decoding by the Viterbi algorithm. Furthermore, to implement soft-decision decoding, the observation of HMM is replaced by Gaussian mixture models (GMM). Our method provides superior error correction potential than the standard method because the model parameters contain channel state information (CSI). We evaluated the performance of the method compared to standard Viterbi decoding by numerical simulation. In the multipath channel, the hybrid HMM decoder can achieve a performance gain of 4.7 dB and 2 dB when using hard-decision and soft-decision decoding, respectively. The HMM decoder also achieves significant performance gains for the RSC code, suggesting that the method could be extended to turbo codes.
M$^3$ViT: Mixture-of-Experts Vision Transformer for Efficient Multi-task Learning with Model-Accelerator Co-design
Venue: arXiv cs.CV 2022
Year: 2022

Multi-task learning (MTL) encapsulates multiple learned tasks in a single model and often lets those tasks learn better jointly. However, when deploying MTL onto those real-world systems that are often resource-constrained or latency-sensitive, two prominent challenges arise: (i) during training, simultaneously optimizing all tasks is often difficult due to gradient conflicts across tasks; (ii) at inference, current MTL regimes have to activate nearly the entire model even to just execute a single task. Yet most real systems demand only one or two tasks at each moment, and switch between tasks as needed: therefore such all tasks activated inference is also highly inefficient and non-scalable. In this paper, we present a model-accelerator co-design framework to enable efficient on-device MTL. Our framework, dubbed M$^3$ViT, customizes mixture-of-experts (MoE) layers into a vision transformer (ViT) backbone for MTL, and sparsely activates task-specific experts during training. Then at inference with any task of interest, the same design allows for activating only the task-corresponding sparse expert pathway, instead of the full model. Our new model design is further enhanced by hardware-level innovations, in particular, a novel computation reordering scheme tailored for memory-constrained MTL that achieves zero-overhead switching between tasks and can scale to any number of experts. When executing single-task inference, M$^{3}$ViT achieves higher accuracies than encoder-focused MTL methods, while significantly reducing 88% inference FLOPs. When implemented on a hardware platform of one Xilinx ZCU104 FPGA, our co-design framework reduces the memory requirement by 2.4 times, while achieving energy efficiency up to 9.23 times higher than a comparable FPGA baseline. Code is available at: https://github.com/VITA-Group/M3ViT.
Search for Concepts: Discovering Visual Concepts Using Direct Optimization
Venue: arXiv cs.CV 2022
Year: 2022

Finding an unsupervised decomposition of an image into individual objects is a key step to leverage compositionality and to perform symbolic reasoning. Traditionally, this problem is solved using amortized inference, which does not generalize beyond the scope of the training data, may sometimes miss correct decompositions, and requires large amounts of training data. We propose finding a decomposition using direct, unamortized optimization, via a combination of a gradient-based optimization for differentiable object properties and global search for non-differentiable properties. We show that using direct optimization is more generalizable, misses fewer correct decompositions, and typically requires less data than methods based on amortized inference. This highlights a weakness of the current prevalent practice of using amortized inference that can potentially be improved by integrating more direct optimization elements.
A Bioinspired Stiffness Tunable Sucker for Passive Adaptation and Firm Attachment to Angular Substrates
Venue: arXiv cs.RO 2022
Year: 2022

The ability to adapt and conform to angular and uneven surfaces improves the suction cup's performance in grasping and manipulation. However, in most cases, the adaptation costs lack of required stiffness for manipulation after surface attachment; thus, the ideal scenario is to have compliance during adaptation and stiffness after attachment to the surface. Nevertheless, most stiffness modulation techniques in suction cups require additional actuation. This article presents a new stiffness tunable suction cup that adapts to steep angular surfaces. Using granular jamming as a vacuum driven stiffness modulation provides a sensorless for activating the mechanism. Thus, the design is composed of a conventional active suction pad connected to a granular stalk, emulating a hinge behavior that is compliant during adaptation and has high stiffness after attachment is ensured. During the experiment, the suction cup can adapt to angles up to 85 degrees with force lower than 0.5 N. We also investigated the effect of granular stalk's length on the adaptation and how this design performs compared to passive adaptation without stiffness modulation.
A Nonlinear Sum of Squares Search for CAZAC Sequences
Venue: arXiv cs.IT 2022
Year: 2022

We report on a search for CAZAC sequences by using nonlinear sum of squares optimization. Up to equivalence, we found all length 7 CAZAC sequences. We obtained evidence suggesting there are finitely many length 10 CAZAC sequences with a total of 3040 sequences. Last, we compute longer sequences and compare their aperiodic autocorrelation properties to known sequences. The code and results of this search are publicly available through GitHub.
Continuum Robot State Estimation Using Gaussian Process Regression on $SE(3)$
Venue: arXiv cs.RO 2022
Year: 2022

Continuum robots have the potential to enable new applications in medicine, inspection, and countless other areas due to their unique shape, compliance, and size. Excellent progess has been made in the mechanical design and dynamic modelling of continuum robots, to the point that there are some canonical designs, although new concepts continue to be explored. In this paper, we turn to the problem of state estimation for continuum robots that can been modelled with the common Cosserat rod model. Sensing for continuum robots might comprise external camera observations, embedded tracking coils or strain gauges. We repurpose a Gaussian process (GP) regression approach to state estimation, initially developed for continuous-time trajectory estimation in $SE(3)$. In our case, the continuous variable is not time but arclength and we show how to estimate the continuous shape (and strain) of the robot (along with associated uncertainties) given discrete, noisy measurements of both pose and strain along the length. We demonstrate our approach quantitatively through simulations as well as through experiments. Our evaluations show that accurate and continuous estimates of a continuum robot's shape can be achieved, resulting in average end-effector errors between the estimated and ground truth shape as low as 3.5mm and 0.016$^\circ$ in simulation or 3.3mm and 0.035$^\circ$ for unloaded configurations and 6.2mm and 0.041$^\circ$ for loaded ones during experiments, when using discrete pose measurements.
ProVe: A Pipeline for Automated Provenance Verification of Knowledge Graphs against Textual Sources
Venue: arXiv cs.CL 2022
Year: 2022

Knowledge Graphs are repositories of information that gather data from a multitude of domains and sources in the form of semantic triples, serving as a source of structured data for various crucial applications in the modern web landscape, from Wikipedia infoboxes to search engines. Such graphs mainly serve as secondary sources of information and depend on well-documented and verifiable provenance to ensure their trustworthiness and usability. However, their ability to systematically assess and assure the quality of this provenance, most crucially whether it properly supports the graph's information, relies mainly on manual processes that do not scale with size. ProVe aims at remedying this, consisting of a pipelined approach that automatically verifies whether a Knowledge Graph triple is supported by text extracted from its documented provenance. ProVe is intended to assist information curators and consists of four main steps involving rule-based methods and machine learning models: text extraction, triple verbalisation, sentence selection, and claim verification. ProVe is evaluated on a Wikidata dataset, achieving promising results overall and excellent performance on the binary classification task of detecting support from provenance, with 87.5% accuracy and 82.9% F1-macro on text-rich sources. The evaluation data and scripts used in this paper are available on GitHub and Figshare.
The Information Bottleneck Principle in Corporate Hierarchies
Venue: arXiv cs.SI 2022
Year: 2022

The hierarchical nature of corporate information processing is a topic of great interest in economic and management literature. Firms are characterised by a need to make complex decisions, often aggregating partial and uncertain information, which greatly exceeds the attention capacity of constituent individuals. However, the efficient transmission of these signals is still not fully understood. Recently, the information bottleneck principle has emerged as a powerful tool for understanding the transmission of relevant information through intermediate levels in a hierarchical structure. In this paper we note that the information bottleneck principle may similarly be applied directly to corporate hierarchies. In doing so we provide a bridge between organisation theory and that of rapidly expanding work in deep neural networks (DNNs), including the use of skip connections as a means of more efficient transmission of information in hierarchical organisations.
A Decision Framework for Blockchain Adoption
Venue: arXiv cs.CR 2022
Year: 2022

Blockchain and distributed ledger technologies are gaining the interest of the academy, companies, and institutions. Nonetheless, the path toward blockchain adoption is not straightforward, as blockchain is a complex technology that requires revisiting the standard way of addressing problems and tackling them from a decentralized perspective. Thus, decision-makers adopt blockchain technology for the wrong reasons or prefer it to more suitable ones. This work presents a decision framework for blockchain adoption to help decision-makers decide whether blockchain is applicable, valuable, and preferable to other technologies. In particular, The decision framework is composed of a small set of questions that can be answered from a managerial standpoint and that do not require a deep technical knowledge of blockchain-related topics.