OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic Node Embeddings from Edge Streams
Venue: arXiv cs.LG 2020
Year: 2020

Networks evolve continuously over time with the addition, deletion, and changing of links and nodes. Such temporal networks (or edge streams) consist of a sequence of timestamped edges and are seemingly ubiquitous. Despite the importance of accurately modeling the temporal information, most embedding methods ignore it entirely or approximate the temporal network using a sequence of static snapshot graphs. In this work, we propose using the notion of temporal walks for learning dynamic embeddings from temporal networks. Temporal walks capture the temporally valid interactions (e.g., flow of information, spread of disease) in the dynamic network in a lossless fashion. Based on the notion of temporal walks, we describe a general class of embeddings called continuous-time dynamic network embeddings (CTDNEs) that completely avoid the issues and problems that arise when approximating the temporal network as a sequence of static snapshot graphs. Unlike previous work, CTDNEs learn dynamic node embeddings directly from the temporal network at the finest temporal granularity and thus use only temporally valid information. As such CTDNEs naturally support online learning of the node embeddings in a streaming real-time fashion. Finally, the experiments demonstrate the effectiveness of this class of embedding methods that leverage temporal walks as it achieves an average gain in AUC of 11.9% across all methods and graphs.
Exploiting Event Log Event Attributes in RNN Based Prediction
Venue: arXiv cs.LG 2020
Year: 2020

In predictive process analytics, current and historical process data in event logs is used to predict the future, e.g., to predict the next activity or how long a process will still require to complete. Recurrent neural networks (RNN) and its subclasses have been demonstrated to be well suited for creating prediction models. Thus far, event attributes have not been fully utilized in these models. The biggest challenge in exploiting them in prediction models is the potentially large amount of event attributes and attribute values. We present a novel clustering technique that allows for trade-offs between prediction accuracy and the time needed for model training and prediction. As an additional finding, we also find that this clustering method combined with having raw event attribute values in some cases provides even better prediction accuracy at the cost of additional time required for training and prediction.
SIMCO: SIMilarity-based object COunting
Venue: arXiv cs.CV 2020
Year: 2020

We present SIMCO, the first agnostic multi-class object counting approach. SIMCO starts by detecting foreground objects through a novel Mask RCNN-based architecture trained beforehand (just once) on a brand-new synthetic 2D shape dataset, InShape; the idea is to highlight every object resembling a primitive 2D shape (circle, square, rectangle, etc.). Each object detected is described by a low-dimensional embedding, obtained from a novel similarity-based head branch; this latter implements a triplet loss, encouraging similar objects (same 2D shape + color and scale) to map close. Subsequently, SIMCO uses this embedding for clustering, so that different types of objects can emerge and be counted, making SIMCO the very first multi-class unsupervised counter. Experiments show that SIMCO provides state-of-the-art scores on counting benchmarks and that it can also help in many challenging image understanding tasks.
Optimal Placement of UAVs for Minimum Outage Probability
Venue: arXiv cs.IT 2020
Year: 2020

We consider multiple unmanned aerial vehicles (UAVs) serving a density of ground terminals (GTs) as base stations. The objective is to minimize the outage probability of GT-to-UAV transmissions. Optimal placement of UAVs under different UAV altitude constraints and GT densities is studied. First, using a random deployment argument, a general upper bound on the optimal outage probability is found for any density of GTs and any number of UAVs. A matching lower bound is also derived to show that the optimal outage probability decays exponentially with the number of UAVs. Next, the structure of optimal deployments is studied when the common altitude constraint is large. For a wide class of GT densities, it is shown that all UAVs should be placed to the same location in an optimal deployment. A design implication is that one can use a single multi-antenna UAV as opposed to multiple single-antenna UAVs without loss of optimality. This result is also extended to a practical variant of the Rician fading model recently developed by Azari et al. for UAV communications. Numerical deployment of UAVs in the centralized and practical distributed settings are carried out using the particle swarm optimization and modified gradient descent algorithms, respectively.
c-trie++: A Dynamic Trie Tailored for Fast Prefix Searches
Venue: arXiv cs.DS 2020
Year: 2020

Given a dynamic set $K$ of $k$ strings of total length $n$ whose characters are drawn from an alphabet of size $σ$, a keyword dictionary is a data structure built on $K$ that provides locate, prefix search, and update operations on $K$. Under the assumption that $α= w / \lg σ$ characters fit into a single machine word $w$, we propose a keyword dictionary that represents $K$ in $n \lg σ+ Θ(k \lg n)$ bits of space, supporting all operations in $O(m / α+ \lg α)$ expected time on an input string of length $m$ in the word RAM model. This data structure is underlined with an exhaustive practical evaluation, highlighting the practical usefulness of the proposed data structure, especially for prefix searches - one of the most elementary keyword dictionary operations.
Investigating Data-driven systems as digital twins: Numerical behavior of Ho-Kalman method for order estimation
Venue: arXiv cs.SY 2020
Year: 2020

System identification has been a major advancement in the evolution of engineering. As it is by default the first step towards a significant set of adaptive control techniques, it is imperative for engineers to apply it in order to practice control. Given that system identification could be useful in creating a digital twin, this work focuses on the initial stage of the procedure by discussing simplistic system order identification. Through specific numerical examples, this study constitutes an investigation on the most \natural" method for estimating the order from responses in a convenient and seamless way in time-domain. The method itself, originally proposed by Ho and Kalman and utilizing linear algebra, is an intuitive tool retrieving information out of the data themselves. Finally, with the help of the limitations of the methods, the potential future outlook is discussed, under the prism of forming a digital twin.
Multimodal Subspace Support Vector Data Description
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we propose a novel method for projecting data from multiple modalities to a new subspace optimized for one-class classification. The proposed method iteratively transforms the data from the original feature space of each modality to a new common feature space along with finding a joint compact description of data coming from all the modalities. For data in each modality, we define a separate transformation to map the data from the corresponding feature space to the new optimized subspace by exploiting the available information from the class of interest only. We also propose different regularization strategies for the proposed method and provide both linear and non-linear formulations. The proposed Multimodal Subspace Support Vector Data Description outperforms all the competing methods using data from a single modality or fusing data from all modalities in four out of five datasets.
Convolutional Neural Networks for Classification of Alzheimer's Disease: Overview and Reproducible Evaluation
Venue: arXiv cs.LG 2020
Year: 2020

Over 30 papers have proposed to use convolutional neural network (CNN) for AD classification from anatomical MRI. However, the classification performance is difficult to compare across studies due to variations in components such as participant selection, image preprocessing or validation procedure. Moreover, these studies are hardly reproducible because their frameworks are not publicly accessible and because implementation details are lacking. Lastly, some of these papers may report a biased performance due to inadequate or unclear validation or model selection procedures. In the present work, we aim to address these limitations through three main contributions. First, we performed a systematic literature review and found that more than half of the surveyed papers may have suffered from data leakage. Our second contribution is the extension of our open-source framework for classification of AD using CNN and T1-weighted MRI. Finally, we used this framework to rigorously compare different CNN architectures. The data was split into training/validation/test sets at the very beginning and only the training/validation sets were used for model selection. To avoid any overfitting, the test sets were left untouched until the end of the peer-review process. Overall, the different 3D approaches (3D-subject, 3D-ROI, 3D-patch) achieved similar performances while that of the 2D slice approach was lower. Of note, the different CNN approaches did not perform better than a SVM with voxel-based features. The different approaches generalized well to similar populations but not to datasets with different inclusion criteria or demographical characteristics.
Question Guided Modular Routing Networks for Visual Question Answering
Venue: arXiv cs.CV 2020
Year: 2020

This paper studies the task of Visual Question Answering (VQA), which is topical in Multimedia community recently. Particularly, we explore two critical research problems existed in VQA: (1) efficiently fusing the visual and textual modalities; (2) enabling the visual reasoning ability of VQA models in answering complex questions. To address these challenging problems, a novel Question Guided Modular Routing Networks (QGMRN) has been proposed in this paper. Particularly, The QGMRN is composed of visual, textual and routing network. The visual and textual network serve as the backbones for the generic feature extractors of visual and textual modalities. QGMRN can fuse the visual and textual modalities at multiple semantic levels. Typically, the visual reasoning is facilitated by the routing network in a discrete and stochastic way by using Gumbel-Softmax trick for module selection. When the input reaches a certain modular layer, routing network newly proposed in this paper, dynamically selects a portion of modules from that layer to process the input depending on the question features generated by the textual network. It can also learn to reason by routing between the generic modules without additional supervision information or expert knowledge. Benefiting from the dynamic routing mechanism, QGMRN can outperform the previous classical VQA methods by a large margin and achieve the competitive results against the state-of-the-art methods. Furthermore, attention mechanism is integrated into our QGMRN model and thus can further boost the model performance. Empirically, extensive experiments on the CLEVR and CLEVR-Humans datasets validate the effectiveness of our proposed model, and the state-of-the-art performance has been achieved.
Event-based Vision: A Survey
Venue: arXiv cs.CV 2020
Year: 2020

Event cameras are bio-inspired sensors that differ from conventional frame cameras: Instead of capturing images at a fixed rate, they asynchronously measure per-pixel brightness changes, and output a stream of events that encode the time, location and sign of the brightness changes. Event cameras offer attractive properties compared to traditional cameras: high temporal resolution (in the order of microseconds), very high dynamic range (140 dB vs. 60 dB), low power consumption, and high pixel bandwidth (on the order of kHz) resulting in reduced motion blur. Hence, event cameras have a large potential for robotics and computer vision in challenging scenarios for traditional cameras, such as low-latency, high speed, and high dynamic range. However, novel methods are required to process the unconventional output of these sensors in order to unlock their potential. This paper provides a comprehensive overview of the emerging field of event-based vision, with a focus on the applications and the algorithms developed to unlock the outstanding properties of event cameras. We present event cameras from their working principle, the actual sensors that are available and the tasks that they have been used for, from low-level vision (feature detection and tracking, optic flow, etc.) to high-level vision (reconstruction, segmentation, recognition). We also discuss the techniques developed to process events, including learning-based techniques, as well as specialized processors for these novel sensors, such as spiking neural networks. Additionally, we highlight the challenges that remain to be tackled and the opportunities that lie ahead in the search for a more efficient, bio-inspired way for machines to perceive and interact with the world.
Nonlinear Observability via Koopman Analysis: Characterizing the Role of Symmetry
Venue: arXiv cs.SY 2020
Year: 2020

This paper considers the observability of nonlinear systems from a Koopman operator theoretic perspective--and in particular--the effect of symmetry on observability. We first examine an infinite-dimensional linear system (constructed using independent Koopman eigenfunctions) such that its observability is equivalent to the observability of the original nonlinear system. Next, we derive an analytic relation between symmetry and nonlinear observability; it is shown that symmetry in the nonlinear dynamics is reflected in the symmetry of the corresponding Koopman eigenfunctions, as well as presence of repeated Koopman eigenvalues. We then proceed to show that the loss of observability in symmetric nonlinear systems can be traced back to the presence of these repeated eigenvalues. In the case where we have a sufficient number of measurements, the nonlinear system remains unobservable when these functions have symmetries that mirror those of the dynamics. The proposed observability framework provides insights into the minimum number of the measurements needed to make an unobservable nonlinear system, observable. The proposed results are then applied to a network of nano-electromechanical oscillators coupled via a symmetric interaction topology.
Gotta Catch 'Em All: Using Honeypots to Catch Adversarial Attacks on Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Deep neural networks (DNN) are known to be vulnerable to adversarial attacks. Numerous efforts either try to patch weaknesses in trained models, or try to make it difficult or costly to compute adversarial examples that exploit them. In our work, we explore a new "honeypot" approach to protect DNN models. We intentionally inject trapdoors, honeypot weaknesses in the classification manifold that attract attackers searching for adversarial examples. Attackers' optimization algorithms gravitate towards trapdoors, leading them to produce attacks similar to trapdoors in the feature space. Our defense then identifies attacks by comparing neuron activation signatures of inputs to those of trapdoors. In this paper, we introduce trapdoors and describe an implementation of a trapdoor-enabled defense. First, we analytically prove that trapdoors shape the computation of adversarial attacks so that attack inputs will have feature representations very similar to those of trapdoors. Second, we experimentally show that trapdoor-protected models can detect, with high accuracy, adversarial examples generated by state-of-the-art attacks (PGD, optimization-based CW, Elastic Net, BPDA), with negligible impact on normal classification. These results generalize across classification domains, including image, facial, and traffic-sign recognition. We also present significant results measuring trapdoors' robustness against customized adaptive attacks (countermeasures).
Semi-bandit Optimization in the Dispersed Setting
Venue: arXiv cs.LG 2020
Year: 2020

The goal of data-driven algorithm design is to obtain high-performing algorithms for specific application domains using machine learning and data. Across many fields in AI, science, and engineering, practitioners will often fix a family of parameterized algorithms and then optimize those parameters to obtain good performance on example instances from the application domain. In the online setting, we must choose algorithm parameters for each instance as they arrive, and our goal is to be competitive with the best fixed algorithm in hindsight. There are two major challenges in online data-driven algorithm design. First, it can be computationally expensive to evaluate the loss functions that map algorithm parameters to performance, which often require the learner to run a combinatorial algorithm to measure its performance. Second, the losses can be extremely volatile and have sharp discontinuities. However, we show that in many applications, evaluating the loss function for one algorithm choice can sometimes reveal the loss for a range of similar algorithms, essentially for free. We develop online optimization algorithms capable of using this kind of extra information by working in the semi-bandit feedback setting. Our algorithms achieve regret bounds that are essentially as good as algorithms under full-information feedback and are significantly more computationally efficient. We apply our semi-bandit results to obtain the first provable guarantees for data-driven algorithm design for linkage-based clustering and we improve the best regret bounds for designing greedy knapsack algorithms.
Feature Fusion for Online Mutual Knowledge Distillation
Venue: arXiv cs.CV 2020
Year: 2020

We propose a learning framework named Feature Fusion Learning (FFL) that efficiently trains a powerful classifier through a fusion module which combines the feature maps generated from parallel neural networks. Specifically, we train a number of parallel neural networks as sub-networks, then we combine the feature maps from each sub-network using a fusion module to create a more meaningful feature map. The fused feature map is passed into the fused classifier for overall classification. Unlike existing feature fusion methods, in our framework, an ensemble of sub-network classifiers transfers its knowledge to the fused classifier and then the fused classifier delivers its knowledge back to each sub-network, mutually teaching one another in an online-knowledge distillation manner. This mutually teaching system not only improves the performance of the fused classifier but also obtains performance gain in each sub-network. Moreover, our model is more beneficial because different types of network can be used for each sub-network. We have performed a variety of experiments on multiple datasets such as CIFAR-10, CIFAR-100 and ImageNet and proved that our method is more effective than other alternative methods in terms of performance of both sub-networks and the fused classifier.
Learning Manipulation Skills Via Hierarchical Spatial Attention
Venue: arXiv cs.RO 2020
Year: 2020

Learning generalizable skills in robotic manipulation has long been challenging due to real-world sized observation and action spaces. One method for addressing this problem is attention focus -- the robot learns where to attend its sensors and irrelevant details are ignored. However, these methods have largely not caught on due to the difficulty of learning a good attention policy and the added partial observability induced by a narrowed window of focus. This article addresses the first issue by constraining gazes to a spatial hierarchy. For the second issue, we identify a case where the partial observability induced by attention does not prevent Q-learning from finding an optimal policy. We conclude with real-robot experiments on challenging pick-place tasks demonstrating the applicability of the approach.
Reliable Multi-label Classification: Prediction with Partial Abstention
Venue: arXiv cs.LG 2020
Year: 2020

In contrast to conventional (single-label) classification, the setting of multilabel classification (MLC) allows an instance to belong to several classes simultaneously. Thus, instead of selecting a single class label, predictions take the form of a subset of all labels. In this paper, we study an extension of the setting of MLC, in which the learner is allowed to partially abstain from a prediction, that is, to deliver predictions on some but not necessarily all class labels. We propose a formalization of MLC with abstention in terms of a generalized loss minimization problem and present first results for the case of the Hamming loss, rank loss, and F-measure, both theoretical and experimental.
Constructive Polynomial Partitioning for Algebraic Curves in $\mathbb{R}^3$ with Applications
Venue: arXiv cs.CG 2020
Year: 2020

In 2015, Guth proved that for any set of $k$-dimensional bounded complexity varieties in $\mathbb{R}^d$ and for any positive integer $D$, there exists a polynomial of degree at most $D$ whose zero set divides $\mathbb{R}^d$ into open connected sets, so that only a small fraction of the given varieties intersect each of these sets. Guth's result generalized an earlier result of Guth and Katz for points. Guth's proof relies on a variant of the Borsuk-Ulam theorem, and for $k>0$, it is unknown how to obtain an explicit representation of such a partitioning polynomial and how to construct it efficiently. In particular, it is unknown how to effectively construct such a polynomial for bounded-degree algebraic curves (or even lines) in $\mathbb{R}^3$. We present an efficient algorithmic construction for this setting. Given a set of $n$ input algebraic curves and a positive integer $D$, we efficiently construct a decomposition of space into $O(D^3\log^3{D})$ open "cells," each of which meets $O(n/D^2)$ curves from the input. The construction time is $O(n^2)$. For the case of lines in $3$-space we present an improved implementation, whose running time is $O(n^{4/3} \log^{O(1)} n)$. The constant of proportionality in both time bounds depends on $D$ and the maximum degree of the polynomials defining the input curves. As an application, we revisit the problem of eliminating depth cycles among non-vertical lines in $3$-space, recently studied by Aronov and Sharir (2018), and show an algorithm that cuts $n$ such lines into $O(n^{3/2+ε})$ pieces that are depth-cycle free, for any $ε> 0$. The algorithm runs in $O(n^{3/2+ε})$ time, which is a considerable improvement over the previously known algorithms.
Sublinear-Time Non-Adaptive Group Testing with $O(k \log n)$ Tests via Bit-Mixing Coding
Venue: arXiv cs.IT 2020
Year: 2020

The group testing problem consists of determining a small set of defective items from a larger set of items based on tests on groups of items, and is relevant in applications such as medical testing, communication protocols, pattern matching, and many more. While rigorous group testing algorithms have long been known with runtime at least linear in the number of items, a recent line of works has sought to reduce the runtime to ${\rm poly}(k \log n)$, where $n$ is the number of items and $k$ is the number of defectives. In this paper, we present such an algorithm for non-adaptive probabilistic group testing termed {\em bit mixing coding} (BMC), which builds on techniques that encode item indices in the test matrix, while incorporating novel ideas based on erasure-correction coding. We show that BMC achieves asymptotically vanishing error probability with $O(k \log n)$ tests and $O(k^2 \cdot \log k \cdot \log n)$ runtime, in the limit as $n \to \infty$ (with $k$ having an arbitrary dependence on $n$). This closes a recently-proposed open problem of simultaneously achieving ${\rm poly}(k \log n)$ decoding time using $O(k \log n)$ tests without any assumptions on $k$. In addition, we show that the same scaling laws can be attained in a commonly-considered noisy setting, in which each test outcome is flipped with constant probability.