OpenRaiser/Intern-Atlas huggingface dataset:
Minimum bounded chains and minimum homologous chains in embedded simplicial complexes
Venue: arXiv cs.CG 2020
Year: 2020

We study two optimization problems on simplicial complexes with homology over $\mathbb{Z}_2$, the minimum bounded chain problem: given a $d$-dimensional complex $\mathcal{K}$ embedded in $\mathbb{R}^{d+1}$ and a null-homologous $(d-1)$-cycle $C$ in $\mathcal{K}$, find the minimum $d$-chain with boundary $C$, and the minimum homologous chain problem: given a $(d+1)$-manifold $\mathcal{M}$ and a $d$-chain $D$ in $\mathcal{M}$, find the minimum $d$-chain homologous to $D$. We show strong hardness results for both problems even for small values of $d$; $d = 2$ for the former problem, and $d=1$ for the latter problem. We show that both problems are APX-hard, and hard to approximate within any constant factor assuming the unique games conjecture. On the positive side, we show that both problems are fixed parameter tractable with respect to the size of the optimal solution. Moreover, we provide an $O(\sqrt{\log β_d})$-approximation algorithm for the minimum bounded chain problem where $β_d$ is the $d$th Betti number of $\mathcal{K}$. Finally, we provide an $O(\sqrt{\log n_{d+1}})$-approximation algorithm for the minimum homologous chain problem where $n_{d+1}$ is the number of $d$-simplices in $\mathcal{M}$.
Linear time dynamic programming for the exact path of optimal models selected from a finite set
Venue: arXiv cs.LG 2020
Year: 2020

Many learning algorithms are formulated in terms of finding model parameters which minimize a data-fitting loss function plus a regularizer. When the regularizer involves the l0 pseudo-norm, the resulting regularization path consists of a finite set of models. The fastest existing algorithm for computing the breakpoints in the regularization path is quadratic in the number of models, so it scales poorly to high dimensional problems. We provide new formal proofs that a dynamic programming algorithm can be used to compute the breakpoints in linear time. Empirical results on changepoint detection problems demonstrate the improved accuracy and speed relative to grid search and the previous quadratic time algorithm.
What went wrong and when? Instance-wise Feature Importance for Time-series Models
Venue: arXiv cs.LG 2020
Year: 2020

Explanations of time series models are useful for high stakes applications like healthcare but have received little attention in machine learning literature. We propose FIT, a framework that evaluates the importance of observations for a multivariate time-series black-box model by quantifying the shift in the predictive distribution over time. FIT defines the importance of an observation based on its contribution to the distributional shift under a KL-divergence that contrasts the predictive distribution against a counterfactual where the rest of the features are unobserved. We also demonstrate the need to control for time-dependent distribution shifts. We compare with state-of-the-art baselines on simulated and real-world clinical data and demonstrate that our approach is superior in identifying important time points and observations throughout the time series.
Linear-Time Parameterized Algorithms with Limited Local Resources
Venue: arXiv cs.DS 2020
Year: 2020

We propose a new (theoretical) computational model for the study of massive data processing with limited computational resources. Our model measures the complexity of reading the very large data sets in terms of the data size N and analyzes the computational cost in terms of a parameter k that characterizes the computational power provided by limited local computing resources. We develop new algorithmic techniques that implement algorithms for solving well-known computational problems on the proposed model. In particular, we present an algorithm that finds a k-matching in a general unweighted graph in time O(N + k^{2.5}) and an algorithm that constructs a maximum weighted k-matching in a general weighted graph in time O(N + k^3 log k). Both algorithms have their space complexity bounded by O(k^2).
Segmentation of Satellite Imagery using U-Net Models for Land Cover Classification
Venue: arXiv cs.CV 2020
Year: 2020

The focus of this paper is using a convolutional machine learning model with a modified U-Net structure for creating land cover classification mapping based on satellite imagery. The aim of the research is to train and test convolutional models for automatic land cover mapping and to assess their usability in increasing land cover mapping accuracy and change detection. To solve these tasks, authors prepared a dataset and trained machine learning models for land cover classification and semantic segmentation from satellite images. The results were analysed on three different land classification levels. BigEarthNet satellite image archive was selected for the research as one of two main datasets. This novel and recent dataset was published in 2019 and includes Sentinel-2 satellite photos from 10 European countries made in 2017 and 2018. As a second dataset the authors composed an original set containing a Sentinel-2 image and a CORINE land cover map of Estonia. The developed classification model shows a high overall F\textsubscript{1} score of 0.749 on multiclass land cover classification with 43 possible image labels. The model also highlights noisy data in the BigEarthNet dataset, where images seem to have incorrect labels. The segmentation models offer a solution for generating automatic land cover mappings based on Sentinel-2 satellite images and show a high IoU score for land cover classes such as forests, inland waters and arable land. The models show a capability of increasing the accuracy of existing land classification maps and in land cover change detection.
Minimal spiking neuron for solving multi-label classification tasks
Venue: arXiv cs.NE 2020
Year: 2020

The Multi-Spike Tempotron (MST) is a powerful single spiking neuron model that can solve complex supervised classification tasks. While powerful, it is also internally complex, computationally expensive to evaluate, and not suitable for neuromorphic hardware. Here we aim to understand whether it is possible to simplify the MST model, while retaining its ability to learn and to process information. To this end, we introduce a family of Generalised Neuron Models (GNM) which are a special case of the Spike Response Model and much simpler and cheaper to simulate than the MST. We find that over a wide range of parameters the GNM can learn at least as well as the MST. We identify the temporal autocorrelation of the membrane potential as the single most important ingredient of the GNM which enables it to classify multiple spatio-temporal patterns. We also interpret the GNM as a chemical system, thus conceptually bridging computation by neural networks with molecular information processing. We conclude the paper by proposing alternative training approaches for the GNM including error trace learning and error backpropagation.
Cell-Free Massive MIMO With Radio Stripes and Sequential Uplink Processing
Venue: arXiv cs.IT 2020
Year: 2020

Cell-free Massive MIMO (mMIMO) is envisaged to be a next-generation technology beyond 5G with its high spectral efficiency and superior spatial diversity as compared to that of conventional MIMO technology. The main principle is that many distributed access points (APs) cooperate to simultaneously serve all the users within the network without creating cell boundaries. This paper considers the uplink of a cell-free mMIMO system utilizing the radio stripe network architecture. We propose a novel sequential processing algorithm with normalized linear minimum mean square error (N-LMMSE) combining at every. This algorithm enables interference suppression in cell-free MMO while keeping the cost and front-haul requirements low. The spectral efficiency of the proposed algorithm is computed and analyzed. We conclude that it provides an attractive trade-off between low front-haul requirements and high spectral efficiency.
Metric-Scale Truncation-Robust Heatmaps for 3D Human Pose Estimation
Venue: arXiv cs.CV 2020
Year: 2020

Heatmap representations have formed the basis of 2D human pose estimation systems for many years, but their generalizations for 3D pose have only recently been considered. This includes 2.5D volumetric heatmaps, whose X and Y axes correspond to image space and the Z axis to metric depth around the subject. To obtain metric-scale predictions, these methods must include a separate, explicit post-processing step to resolve scale ambiguity. Further, they cannot encode body joint positions outside of the image boundaries, leading to incomplete pose estimates in case of image truncation. We address these limitations by proposing metric-scale truncation-robust (MeTRo) volumetric heatmaps, whose dimensions are defined in metric 3D space near the subject, instead of being aligned with image space. We train a fully-convolutional network to estimate such heatmaps from monocular RGB in an end-to-end manner. This reinterpretation of the heatmap dimensions allows us to estimate complete metric-scale poses without test-time knowledge of the focal length or person distance and without relying on anthropometric heuristics in post-processing. Furthermore, as the image space is decoupled from the heatmap space, the network can learn to reason about joints beyond the image boundary. Using ResNet-50 without any additional learned layers, we obtain state-of-the-art results on the Human3.6M and MPI-INF-3DHP benchmarks. As our method is simple and fast, it can become a useful component for real-time top-down multi-person pose estimation systems. We make our code publicly available to facilitate further research (see https://vision.rwth-aachen.de/metro-pose3d).
Weight hierarchies and weight distributions of a familiy of $p$-ary linear codes
Venue: arXiv cs.IT 2020
Year: 2020

The weight distribution and weight hierarchy of linear codes are two important research topics in coding theory. In this paper, by choosing proper defining sets from inhomogeneous quadratic functions over $\mathbb{F}_{q}^{2},$ we construct a family of $3$-weight $p$-ary linear codes and determine their weight distributions and weight hierarchies. Most of the codes can be used in secret sharing schemes.
Combining GHOST and Casper
Venue: arXiv cs.CR 2020
Year: 2020

We present "Gasper," a proof-of-stake-based consensus protocol, which is an idealized version of the proposed Ethereum 2.0 beacon chain. The protocol combines Casper FFG, a finality tool, with LMD GHOST, a fork-choice rule. We prove safety, plausible liveness, and probabilistic liveness under different sets of assumptions.
StereoNeuroBayesSLAM: A Neurobiologically Inspired Stereo Visual SLAM System Based on Direct Sparse Method
Venue: arXiv cs.RO 2020
Year: 2020

We propose a neurobiologically inspired visual simultaneous localization and mapping (SLAM) system based on direction sparse method to real-time build cognitive maps of large-scale environments from a moving stereo camera. The core SLAM system mainly comprises a Bayesian attractor network, which utilizes neural responses of head direction (HD) cells in the hippocampus and grid cells in the medial entorhinal cortex (MEC) to represent the head direction and the position of the robot in the environment, respectively. Direct sparse method is employed to accurately and robustly estimate velocity information from a stereo camera. Input rotational and translational velocities are integrated by the HD cell and grid cell networks, respectively. We demonstrated our neurobiologically inspired stereo visual SLAM system on the KITTI odometry benchmark datasets. Our proposed SLAM system is robust to real-time build a coherent semi-metric topological map from a stereo camera. Qualitative evaluation on cognitive maps shows that our proposed neurobiologically inspired stereo visual SLAM system outperforms our previous brain-inspired algorithms and the neurobiologically inspired monocular visual SLAM system both in terms of tracking accuracy and robustness, which is closer to the traditional state-of-the-art one.
Algorithms for the rainbow vertex coloring problem on graph classes
Venue: arXiv cs.DM 2020
Year: 2020

Given a vertex-colored graph, we say a path is a rainbow vertex path if all its internal vertices have distinct colors. The graph is rainbow vertex-connected if there is a rainbow vertex path between every pair of its vertices. In the Rainbow Vertex Coloring (RVC) problem we want to decide whether the vertices of a given graph can be colored with at most $k$ colors so that the graph becomes rainbow vertex-connected. This problem is known to be NP-complete even in very restricted scenarios, and very few efficient algorithms are known for it. In this work, we give polynomial-time algorithms for RVC on permutation graphs, powers of trees and split strongly chordal graphs. The algorithm for the latter class also works for the strong variant of the problem, where the rainbow vertex paths between each vertex pair must be shortest paths. We complement the polynomial-time solvability results for split strongly chordal graphs by showing that, for any fixed $p\geq 3$ both variants of the problem become NP-complete when restricted to split $(S_3,\ldots,S_p)$-free graphs, where $S_q$ denotes the $q$-sun graph.
Weight Priors for Learning Identity Relations
Venue: arXiv cs.LG 2020
Year: 2020

Learning abstract and systematic relations has been an open issue in neural network learning for over 30 years. It has been shown recently that neural networks do not learn relations based on identity and are unable to generalize well to unseen data. The Relation Based Pattern (RBP) approach has been proposed as a solution for this problem. In this work, we extend RBP by realizing it as a Bayesian prior on network weights to model the identity relations. This weight prior leads to a modified regularization term in otherwise standard network learning. In our experiments, we show that the Bayesian weight priors lead to perfect generalization when learning identity based relations and do not impede general neural network learning. We believe that the approach of creating an inductive bias with weight priors can be extended easily to other forms of relations and will be beneficial for many other learning tasks.
Is POS Tagging Necessary or Even Helpful for Neural Dependency Parsing?
Venue: arXiv cs.CL 2020
Year: 2020

In the pre deep learning era, part-of-speech tags have been considered as indispensable ingredients for feature engineering in dependency parsing. But quite a few works focus on joint tagging and parsing models to avoid error propagation. In contrast, recent studies suggest that POS tagging becomes much less important or even useless for neural parsing, especially when using character-based word representations. Yet there are not enough investigations focusing on this issue, both empirically and linguistically. To answer this, we design and compare three typical multi-task learning framework, i.e., Share-Loose, Share-Tight, and Stack, for joint tagging and parsing based on the state-of-the-art biaffine parser. Considering that it is much cheaper to annotate POS tags than parse trees, we also investigate the utilization of large-scale heterogeneous POS tag data. We conduct experiments on both English and Chinese datasets, and the results clearly show that POS tagging (both homogeneous and heterogeneous) can still significantly improve parsing performance when using the Stack joint framework. We conduct detailed analysis and gain more insights from the linguistic aspect.
Diverse and Admissible Trajectory Forecasting through Multimodal Context Understanding
Venue: arXiv cs.CV 2020
Year: 2020

Multi-agent trajectory forecasting in autonomous driving requires an agent to accurately anticipate the behaviors of the surrounding vehicles and pedestrians, for safe and reliable decision-making. Due to partial observability in these dynamical scenes, directly obtaining the posterior distribution over future agent trajectories remains a challenging problem. In realistic embodied environments, each agent's future trajectories should be both diverse since multiple plausible sequences of actions can be used to reach its intended goals, and admissible since they must obey physical constraints and stay in drivable areas. In this paper, we propose a model that synthesizes multiple input signals from the multimodal world|the environment's scene context and interactions between multiple surrounding agents|to best model all diverse and admissible trajectories. We compare our model with strong baselines and ablations across two public datasets and show a significant performance improvement over previous state-of-the-art methods. Lastly, we offer new metrics incorporating admissibility criteria to further study and evaluate the diversity of predictions. Codes are at: https://github.com/kami93/CMU-DATF.
Predicting Memory Compiler Performance Outputs using Feed-Forward Neural Networks
Venue: arXiv cs.OH 2020
Year: 2020

Typical semiconductor chips include thousands of mostly small memories. As memories contribute an estimated 25% to 40% to the overall power, performance, and area (PPA) of a chip, memories must be designed carefully to meet the system's requirements. Memory arrays are highly uniform and can be described by approximately 10 parameters depending mostly on the complexity of the periphery. Thus, to improve PPA utilization, memories are typically generated by memory compilers. A key task in the design flow of a chip is to find optimal memory compiler parametrizations which on the one hand fulfill system requirements while on the other hand optimize PPA. Although most compiler vendors also provide optimizers for this task, these are often slow or inaccurate. To enable efficient optimization in spite of long compiler run times, we propose training fully connected feed-forward neural networks to predict PPA outputs given a memory compiler parametrization. Using an exhaustive search-based optimizer framework which obtains neural network predictions, PPA-optimal parametrizations are found within seconds after chip designers have specified their requirements. Average model prediction errors of less than 3%, a decision reliability of over 99% and productive usage of the optimizer for successful, large volume chip design projects illustrate the effectiveness of the approach.
Heartbeats in the Wild: A Field Study Exploring ECG Biometrics in Everyday Life
Venue: arXiv cs.HC 2020
Year: 2020

This paper reports on an in-depth study of electrocardiogram (ECG) biometrics in everyday life. We collected ECG data from 20 people over a week, using a non-medical chest tracker. We evaluated user identification accuracy in several scenarios and observed equal error rates of 9.15% to 21.91%, heavily depending on 1) the number of days used for training, and 2) the number of heartbeats used per identification decision. We conclude that ECG biometrics can work in the wild but are less robust than expected based on the literature, highlighting that previous lab studies obtained highly optimistic results with regard to real life deployments. We explain this with noise due to changing body postures and states as well as interrupted measures. We conclude with implications for future research and the design of ECG biometrics systems for real world deployments, including critical reflections on privacy.
A Longitudinal Analysis of YouTube's Promotion of Conspiracy Videos
Venue: arXiv cs.CY 2020
Year: 2020

Conspiracy theories have flourished on social media, raising concerns that such content is fueling the spread of disinformation, supporting extremist ideologies, and in some cases, leading to violence. Under increased scrutiny and pressure from legislators and the public, YouTube announced efforts to change their recommendation algorithms so that the most egregious conspiracy videos are demoted and demonetized. To verify this claim, we have developed a classifier for automatically determining if a video is conspiratorial (e.g., the moon landing was faked, the pyramids of Giza were built by aliens, end of the world prophecies, etc.). We coupled this classifier with an emulation of YouTube's watch-next algorithm on more than a thousand popular informational channels to obtain a year-long picture of the videos actively promoted by YouTube. We also obtained trends of the so-called filter-bubble effect for conspiracy theories.
Image Encryption Using Elliptic Curves and Rossby/Drift Wave Triads
Venue: arXiv cs.CR 2020
Year: 2020

We propose an image encryption scheme based on quasi-resonant Rossby/drift wave triads (related to elliptic surfaces) and Mordell elliptic curves (MECs). By defining a total order on quasi-resonant triads, at a first stage we construct quasi-resonant triads using auxiliary parameters of elliptic surfaces in order to generate pseudo-random numbers. At a second stage, we employ an MEC to construct a dynamic substitution box (S-box) for the plain image. The generated pseudo-random numbers and S-box are used to provide diffusion and confusion, respectively, in the tested image. We test the proposed scheme against well-known attacks by encrypting all gray images taken from the USC-SIPI image database. Our experimental results indicate the high security of the newly developed scheme. Finally, via extensive comparisons we show that the new scheme outperforms other popular schemes.
PoseNet3D: Learning Temporally Consistent 3D Human Pose via Knowledge Distillation
Venue: arXiv cs.CV 2020
Year: 2020

Recovering 3D human pose from 2D joints is a highly unconstrained problem. We propose a novel neural network framework, PoseNet3D, that takes 2D joints as input and outputs 3D skeletons and SMPL body model parameters. By casting our learning approach in a student-teacher framework, we avoid using any 3D data such as paired/unpaired 3D data, motion capture sequences, depth images or multi-view images during training. We first train a teacher network that outputs 3D skeletons, using only 2D poses for training. The teacher network distills its knowledge to a student network that predicts 3D pose in SMPL representation. Finally, both the teacher and the student networks are jointly fine-tuned in an end-to-end manner using temporal, self-consistency and adversarial losses, improving the accuracy of each individual network. Results on Human3.6M dataset for 3D human pose estimation demonstrate that our approach reduces the 3D joint prediction error by 18% compared to previous unsupervised methods. Qualitative results on in-the-wild datasets show that the recovered 3D poses and meshes are natural, realistic, and flow smoothly over consecutive frames.
Machine Learning based Anomaly Detection for 5G Networks
Venue: arXiv cs.CR 2020
Year: 2020

Protecting the networks of tomorrow is set to be a challenging domain due to increasing cyber security threats and widening attack surfaces created by the Internet of Things (IoT), increased network heterogeneity, increased use of virtualisation technologies and distributed architectures. This paper proposes SDS (Software Defined Security) as a means to provide an automated, flexible and scalable network defence system. SDS will harness current advances in machine learning to design a CNN (Convolutional Neural Network) using NAS (Neural Architecture Search) to detect anomalous network traffic. SDS can be applied to an intrusion detection system to create a more proactive and end-to-end defence for a 5G network. To test this assumption, normal and anomalous network flows from a simulated environment have been collected and analyzed with a CNN. The results from this method are promising as the model has identified benign traffic with a 100% accuracy rate and anomalous traffic with a 96.4% detection rate. This demonstrates the effectiveness of network flow analysis for a variety of common malicious attacks and also provides a viable option for detection of encrypted malicious network traffic.