OpenRaiser/Intern-Atlas huggingface dataset:
Search-based Kinodynamic Motion Planning for Omnidirectional Quadruped Robots
Venue: arXiv cs.RO 2021
Year: 2021

Autonomous navigation has played an increasingly significant role in quadruped robot system. However, most existing works on quadruped robots navigation using traditional search-based or sample-based methods do not consider the kinodynamic characteristics of quadruped robots, generating kinodynamically infeasible parts, that are difficult to track. In this paper, we introduce a complete navigation system considering the omnidirectional abilities of quadruped robots. First, we use kinodynamic path finding method to obtain smooth, dynamically feasible, time-optimal initial paths and add collision cost as a soft constraint to ensure safety. Then the trajectory is refined by the timed elastic band (TEB) method based on the omnidirectional model of quadruped robots. The superior performance of our work is demonstrated through simulating and real-world experiments on our quadruped robot Jueying Mini.
Generalized Load Balancing and Clustering Problems with Norm Minimization
Venue: arXiv cs.DS 2021
Year: 2021

In many fundamental combinatorial optimization problems, a feasible solution induces some real cost vectors as an intermediate result, and the optimization objective is a certain function of the vectors. For example, in the problem of makespan minimization on unrelated parallel machines, a feasible job assignment induces a vector containing the sizes of assigned jobs for each machine, and the goal is to minimize the $L_\infty$ norm of $L_1$ norms of the vectors. Another example is fault-tolerant $k$-center, where each client is connected to multiple open facilities, thus having a vector of distances to these facilities, and the goal is to minimize the $L_\infty$ norm of $L_\infty$ norms of these vectors. In this paper, we study the maximum of norm problem. Given an arbitrary symmetric monotone norm $f$, the objective is defined as the maximum ($L_\infty$ norm) of $f$-norm values of the induced cost vectors. This versatile formulation captures a wide variety of problems, including makespan minimization, fault-tolerant $k$-center and many others. We give concrete results for load balancing on unrelated parallel machines and clustering problems, including constant-factor approximation algorithms when $f$ belongs with a certain rich family of norms, and $O(\log n)$-approximations when $f$ is general and satisfies some mild assumptions. We also consider the aforementioned problems in a generalized fairness setting. As a concrete example, the insight is to prevent a scheduling algorithm from assigning too many jobs consistently on any machine in a job-recurring scenario, and causing the machine's controller to fail. Our algorithm needs to stochastically output a feasible solution minimizing the objective function, and satisfy the given marginal fairness constraints.
Self-Concordant Analysis of Generalized Linear Bandits with Forgetting
Venue: arXiv cs.LG 2021
Year: 2021

Contextual sequential decision problems with categorical or numerical observations are ubiquitous and Generalized Linear Bandits (GLB) offer a solid theoretical framework to address them. In contrast to the case of linear bandits, existing algorithms for GLB have two drawbacks undermining their applicability. First, they rely on excessively pessimistic concentration bounds due to the non-linear nature of the model. Second, they require either non-convex projection steps or burn-in phases to enforce boundedness of the estimators. Both of these issues are worsened when considering non-stationary models, in which the GLB parameter may vary with time. In this work, we focus on self-concordant GLB (which include logistic and Poisson regression) with forgetting achieved either by the use of a sliding window or exponential weights. We propose a novel confidence-based algorithm for the maximum-likehood estimator with forgetting and analyze its perfomance in abruptly changing environments. These results as well as the accompanying numerical simulations highlight the potential of the proposed approach to address non-stationarity in GLB.
The GDPR Enforcement Fines at Glance
Venue: arXiv cs.CY 2021
Year: 2021

The General Data Protection Regulation (GDPR) came into force in 2018. After this enforcement, many fines have already been imposed by national data protection authorities in Europe. This paper examines the individual GDPR articles referenced in the enforcement decisions, as well as predicts the amount of enforcement fines with available meta-data and text mining features extracted from the enforcement decision documents. According to the results, three articles related to the general principles, lawfulness, and information security have been the most frequently referenced ones. Although the amount of fines imposed vary across the articles referenced, these three particular articles do not stand out. Furthermore, a better statistical evidence is available with other meta-data features, including information about the particular European countries in which the enforcements were made. Accurate predictions are attainable even with simple machine learning techniques for regression analysis. Basic text mining features outperform the meta-data features in this regard. In addition to these results, the paper reflects the GDPR's enforcement against public administration obstacles in the European Union (EU), as well as discusses the use of automatic decision-making systems in judiciary.
Out of Control: Reducing Probabilistic Models by Control-State Elimination
Venue: arXiv cs.LO 2021
Year: 2021

State-of-the-art probabilistic model checkers perform verification on explicit-state Markov models defined in a high-level programming formalism like the PRISM modeling language. Typically, the low-level models resulting from such program-like specifications exhibit lots of structure such as repeating subpatterns. Established techniques like probabilistic bisimulation minimization are able to exploit these structures; however, they operate directly on the explicit-state model. On the other hand, methods for reducing structured state spaces by reasoning about the high-level program have not been investigated that much. In this paper, we present a new, simple, and fully automatic program-level technique to reduce the underlying Markov model. Our approach aims at computing the summary behavior of adjacent locations in the program's control-flow graph, thereby obtaining a program with fewer "control states". This reduction is immediately reflected in the program's operational semantics, enabling more efficient model checking. A key insight is that in principle, each (combination of) program variable(s) with finite domain can play the role of the program counter that defines the flow structure. Unlike most other reduction techniques, our approach is property-directed and naturally supports unspecified model parameters. Experiments demonstrate that our simple method yields state-space reductions of up to 80% on practically relevant benchmarks.
Information-theoretic Task Selection for Meta-Reinforcement Learning
Venue: arXiv cs.LG 2021
Year: 2021

In Meta-Reinforcement Learning (meta-RL) an agent is trained on a set of tasks to prepare for and learn faster in new, unseen, but related tasks. The training tasks are usually hand-crafted to be representative of the expected distribution of test tasks and hence all used in training. We show that given a set of training tasks, learning can be both faster and more effective (leading to better performance in the test tasks), if the training tasks are appropriately selected. We propose a task selection algorithm, Information-Theoretic Task Selection (ITTS), based on information theory, which optimizes the set of tasks used for training in meta-RL, irrespectively of how they are generated. The algorithm establishes which training tasks are both sufficiently relevant for the test tasks, and different enough from one another. We reproduce different meta-RL experiments from the literature and show that ITTS improves the final performance in all of them.
Joint Location, Bandwidth and Power Optimization for THz-enabled UAV Communications
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, the problem of unmanned aerial vehicle (UAV) deployment, power allocation, and bandwidth allocation is investigated for a UAV-assisted wireless system operating at terahertz (THz) frequencies. In the studied model, one UAV can service ground users using the THz frequency band. However, the highly uncertain THz channel will introduce new challenges to the UAV location, user power, and bandwidth allocation optimization problems. Therefore, it is necessary to design a novel framework to deploy UAVs in the THz wireless systems. This problem is formally posed as an optimization problem whose goal is to minimize the total delays of the uplink and downlink transmissions between the UAV and the ground users by jointly optimizing the deployment of the UAV, the transmit power and the bandwidth of each user. The communication delay is crucial for emergency communications. To tackle this nonconvex delay minimization problem, an alternating algorithm is proposed while iteratively solving three subproblems: location optimization subproblem, power control subproblem, and bandwidth allocation subproblem. Simulation results show that the proposed algorithm can reduce the transmission delay by up to $59.3\%$, $49.8\%$ and $75.5\%$ respectively compared to baseline algorithms that optimize only UAV location, bandwidth allocation or transmit power control.
Turning Software Engineers into AI Engineers
Venue: arXiv cs.SE 2021
Year: 2021

In industry as well as education as well as academics we see a growing need for knowledge on how to apply machine learning in software applications. With the educational programme ICT & AI at Fontys UAS we had to find an answer to the question: "How should we educate software engineers to become AI engineers?" This paper describes our educational programme, the open source tools we use, and the literature it is based on. After three years of experience, we present our lessons learned for both educational institutions and software engineers in practice.
Learning a Generative Motion Model from Image Sequences based on a Latent Motion Matrix
Venue: arXiv cs.CV 2021
Year: 2021

We propose to learn a probabilistic motion model from a sequence of images for spatio-temporal registration. Our model encodes motion in a low-dimensional probabilistic space - the motion matrix - which enables various motion analysis tasks such as simulation and interpolation of realistic motion patterns allowing for faster data acquisition and data augmentation. More precisely, the motion matrix allows to transport the recovered motion from one subject to another simulating for example a pathological motion in a healthy subject without the need for inter-subject registration. The method is based on a conditional latent variable model that is trained using amortized variational inference. This unsupervised generative model follows a novel multivariate Gaussian process prior and is applied within a temporal convolutional network which leads to a diffeomorphic motion model. Temporal consistency and generalizability is further improved by applying a temporal dropout training scheme. Applied to cardiac cine-MRI sequences, we show improved registration accuracy and spatio-temporally smoother deformations compared to three state-of-the-art registration algorithms. Besides, we demonstrate the model's applicability for motion analysis, simulation and super-resolution by an improved motion reconstruction from sequences with missing frames compared to linear and cubic interpolation.
On the Moral Justification of Statistical Parity
Venue: arXiv cs.CY 2021
Year: 2021

A crucial but often neglected aspect of algorithmic fairness is the question of how we justify enforcing a certain fairness metric from a moral perspective. When fairness metrics are proposed, they are typically argued for by highlighting their mathematical properties. Rarely are the moral assumptions beneath the metric explained. Our aim in this paper is to consider the moral aspects associated with the statistical fairness criterion of independence (statistical parity). To this end, we consider previous work, which discusses the two worldviews "What You See Is What You Get" (WYSIWYG) and "We're All Equal" (WAE) and by doing so provides some guidance for clarifying the possible assumptions in the design of algorithms. We present an extension of this work, which centers on morality. The most natural moral extension is that independence needs to be fulfilled if and only if differences in predictive features (e.g. high school grades and standardized test scores are predictive of performance at university) between socio-demographic groups are caused by unjust social disparities or measurement errors. Through two counterexamples, we demonstrate that this extension is not universally true. This means that the question of whether independence should be used or not cannot be satisfactorily answered by only considering the justness of differences in the predictive features.
New Ideas for Brain Modelling 7
Venue: arXiv cs.AI 2021
Year: 2021

This paper updates the cognitive model, firstly by creating two systems and then unifying them over the same structure. It represents information at the semantic level only, where labelled patterns are aggregated into a 'type-set-match' form. It is described that the aggregations can be used to match across regions with potentially different functionality and therefore give the structure a required amount of flexibility. The theory is that if the model stores information which can be transposed in consistent ways, then that will result in knowledge and some level of intelligence. As part of the design, patterns have to become distinct and that is realised by unique paths through shared aggregated structures. An ensemble-hierarchy relation also helps to define uniqueness through local feedback that may even be an action potential. The earlier models are still consistent in terms of their proposed functionality, but some of the architecture boundaries have been moved to match them up more closely. After pattern optimisation and tree-like aggregations, the two main models differ only in their upper, more intelligent level. One provides a propositional logic for mutually inclusive or exclusive pattern groups and sequences, while the other provides a behaviour script that is constructed from node types. It can be seen that these two views are complimentary and would allow some control over behaviours, as well as memories, that might get selected.
Cooperative Multi-Beam Routing for Multi-IRS Aided Massive MIMO
Venue: arXiv cs.IT 2021
Year: 2021

Intelligent reflecting surface (IRS) is envisioned to play a significant role in future wireless communication systems thanks to its powerful capability of enabling smart and reconfigurable radio environment. In this paper, we study the multi-IRS aided downlink communication in a massive multiple-input multiple-output (MIMO) system, where a multi-antenna BS simultaneously serves multiple remote single-antenna users with orthogonal beams reflected by multiple IRSs. By exploiting the line-of-sight (LoS) link between each pair of selected IRSs, a multi-hop cascaded LoS link can be established between the BS and each user via their cooperative beam routing. Under this setup, we optimize the selected IRSs and their beam routing path for each user, along with the BS/IRS active/passive beamforming such that the minimum received signal power among all users is maximized, subject to a new multi-beam routing path separation constraint for avoiding the inter-user/route interference. To tackle this problem, we first derive the optimal BS/IRS active/passive beamforming in closed-form for any given beam routes and show the beam routing optimization is NP-complete by recasting it as an equivalent graph-optimization problem. To solve this challenging problem, we then propose an efficient recursive algorithm to partially enumerate the feasible solutions, which effectively balances the performance-complexity trade-off by tuning its design parameter. Numerical results demonstrate that the proposed algorithm can achieve near-optimal performance with low enumeration complexity and also outperform other benchmark schemes.
Approximating the discrete time-cost tradeoff problem with bounded depth
Venue: arXiv cs.DS 2021
Year: 2021

We revisit the deadline version of the discrete time-cost tradeoff problem for the special case of bounded depth. Such instances occur for example in VLSI design. The depth of an instance is the number of jobs in a longest chain and is denoted by $d$. We prove new upper and lower bounds on the approximability. First we observe that the problem can be regarded as a special case of finding a minimum-weight vertex cover in a $d$-partite hypergraph. Next, we study the natural LP relaxation, which can be solved in polynomial time for fixed $d$ and -- for time-cost tradeoff instances -- up to an arbitrarily small error in general. Improving on prior work of Lovász and of Aharoni, Holzman and Krivelevich, we describe a deterministic algorithm with approximation ratio slightly less than $\frac{d}{2}$ for minimum-weight vertex cover in $d$-partite hypergraphs for fixed $d$ and given $d$-partition. This is tight and yields also a $\frac{d}{2}$-approximation algorithm for general time-cost tradeoff instances. We also study the inapproximability and show that no better approximation ratio than $\frac{d+2}{4}$ is possible, assuming the Unique Games Conjecture and $\text{P}\neq\text{NP}$. This strengthens a result of Svensson, who showed that under the same assumptions no constant-factor approximation algorithm exists for general time-cost tradeoff instances (of unbounded depth). Previously, only APX-hardness was known for bounded depth.
Center-wise Local Image Mixture For Contrastive Representation Learning
Venue: arXiv cs.CV 2021
Year: 2021

Contrastive learning based on instance discrimination trains model to discriminate different transformations of the anchor sample from other samples, which does not consider the semantic similarity among samples. This paper proposes a new kind of contrastive learning method, named CLIM, which uses positives from other samples in the dataset. This is achieved by searching local similar samples of the anchor, and selecting samples that are closer to the corresponding cluster center, which we denote as center-wise local image selection. The selected samples are instantiated via an data mixture strategy, which performs as a smoothing regularization. As a result, CLIM encourages both local similarity and global aggregation in a robust way, which we find is beneficial for feature representation. Besides, we introduce \emph{multi-resolution} augmentation, which enables the representation to be scale invariant. We reach 75.5% top-1 accuracy with linear evaluation over ResNet-50, and 59.3% top-1 accuracy when fine-tuned with only 1% labels.
Robust Unsupervised Video Anomaly Detection by Multi-Path Frame Prediction
Venue: arXiv cs.CV 2021
Year: 2021

Video anomaly detection is commonly used in many applications such as security surveillance and is very challenging.A majority of recent video anomaly detection approaches utilize deep reconstruction models, but their performance is often suboptimal because of insufficient reconstruction error differences between normal and abnormal video frames in practice. Meanwhile, frame prediction-based anomaly detection methods have shown promising performance. In this paper, we propose a novel and robust unsupervised video anomaly detection method by frame prediction with proper design which is more in line with the characteristics of surveillance videos. The proposed method is equipped with a multi-path ConvGRU-based frame prediction network that can better handle semantically informative objects and areas of different scales and capture spatial-temporal dependencies in normal videos. A noise tolerance loss is introduced during training to mitigate the interference caused by background noise. Extensive experiments have been conducted on the CUHK Avenue, ShanghaiTech Campus, and UCSD Pedestrian datasets, and the results show that our proposed method outperforms existing state-of-the-art approaches. Remarkably, our proposed method obtains the frame-level AUROC score of 88.3% on the CUHK Avenue dataset.
Applying a Legendre collocation method based on domain decomposition to calculate underwater sound propagation in a horizontally stratified environment
Venue: arXiv cs.CE 2021
Year: 2021

The propagation of sound waves in a horizontally stratified environment, a classic problem in ocean acoustics, has traditionally been calculated using normal modes. Most programs based on the normal mode model are discretized using the finite difference method (FDM). In this paper, a Legendre collocation method (LCM) based on domain decomposition is proposed to solve this problem. A set of collocation points cannot penetrate multiple layers of media, thus necessitating domain decomposition and the use of multiple sets of collocation points. The solution process of this method proceeds entirely in physical space, requiring that the original differential equation be strictly established at the collocation points; thus, a dense matrix eigenvalue system is formed, from which the solution for the horizontal wavenumbers and modes can be directly obtained. Numerical experiments are presented to demonstrate the validity and applicability of this method. A comparison with other methods shows that the LCM proposed in this article is more accurate than the FDM and offers roughly the same accuracy as but a faster calculation speed than other types of spectral methods.
An SMT-Based Approach for Verifying Binarized Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

Deep learning has emerged as an effective approach for creating modern software systems, with neural networks often surpassing hand-crafted systems. Unfortunately, neural networks are known to suffer from various safety and security issues. Formal verification is a promising avenue for tackling this difficulty, by formally certifying that networks are correct. We propose an SMT-based technique for verifying Binarized Neural Networks - a popular kind of neural network, where some weights have been binarized in order to render the neural network more memory and energy efficient, and quicker to evaluate. One novelty of our technique is that it allows the verification of neural networks that include both binarized and non-binarized components. Neural network verification is computationally very difficult, and so we propose here various optimizations, integrated into our SMT procedure as deduction steps, as well as an approach for parallelizing verification queries. We implement our technique as an extension to the Marabou framework, and use it to evaluate the approach on popular binarized neural network architectures.