OpenRaiser/Intern-Atlas huggingface dataset:
An Input-Output Parametrization of Stabilizing Controllers: amidst Youla and System Level Synthesis
Venue: arXiv cs.SY 2020
Year: 2020

This paper proposes a novel input-output parametrization of the set of internally stabilizing output-feedback controllers for linear time-invariant (LTI) systems. Our underlying idea is to directly treat the closed-loop transfer matrices from disturbances to input and output signals as design parameters and exploit their affine relationships. This input-output perspective is particularly effective when a doubly-coprime factorization is difficult to compute, or an initial stabilizing controller is challenging to find; most previous work requires one of these pre-computation steps. Instead, our approach can bypass such pre-computations, in the sense that a stabilizing controller is computed by directly solving a linear program (LP). Furthermore, we show that the proposed input-output parametrization allows for computing norm-optimal controllers subject to quadratically invariant (QI) constraints using convex programming.
Asynchronous Federated Optimization
Venue: arXiv cs.DC 2020
Year: 2020

Federated learning enables training on a massive number of edge devices. To improve flexibility and scalability, we propose a new asynchronous federated optimization algorithm. We prove that the proposed approach has near-linear convergence to a global optimum, for both strongly convex and a restricted family of non-convex problems. Empirical results show that the proposed algorithm converges quickly and tolerates staleness in various applications.
2-Entity RANSAC for robust visual localization in changing environment
Venue: arXiv cs.RO 2020
Year: 2020

Visual localization has attracted considerable attention due to its low-cost and stable sensor, which is desired in many applications, such as autonomous driving, inspection robots and unmanned aerial vehicles. However, current visual localization methods still struggle with environmental changes across weathers and seasons, as there is significant appearance variation between the map and the query image. The crucial challenge in this situation is that the percentage of outliers, i.e. incorrect feature matches, is high. In this paper, we derive minimal closed form solutions for 3D-2D localization with the aid of inertial measurements, using only 2 pairs of point matches or 1 pair of point match and 1 pair of line match. These solutions are further utilized in the proposed 2-entity RANSAC, which is more robust to outliers as both line and point features can be used simultaneously and the number of matches required for pose calculation is reduced. Furthermore, we introduce three feature sampling strategies with different advantages, enabling an automatic selection mechanism. With the mechanism, our 2-entity RANSAC can be adaptive to the environments with different distribution of feature types in different segments. Finally, we evaluate the method on both synthetic and real-world datasets, validating its performance and effectiveness in inter-session scenarios.
Does Unit-Tested Code Crash? A Case Study of Eclipse
Venue: arXiv cs.SE 2020
Year: 2020

Context: Software development projects increasingly adopt unit testing as a way to identify and correct program faults early in the construction process. Code that is unit tested should therefore have fewer failures associated with it. Objective: Compare the number of field failures arising in unit tested code against those arising in code that has not been unit tested. Method: We retrieved 2,083,979 crash incident reports associated with the Eclipse integrated development environment project, and processed them to obtain a set of 126,026 unique program failure stack traces associated with a specific popular release. We then run the JaCoCo code test coverage analysis on the same release, obtaining results on the line, instruction, and branch-level coverage of 216,392 methods. We also extracted from the source code the classes that are linked to a corresponding test class so as to limit test code coverage results to 1,267 classes with actual tests. Finally, we correlated unit tests with failures at the level of 9,523 failing tested methods. Results: Unit-tested code does not appear to be associated with fewer failures. Conclusion: Unit testing on its own may not be a sufficient method for preventing program failures.
Structured Knowledge Distillation for Dense Prediction
Venue: arXiv cs.CV 2020
Year: 2020

In this work, we consider transferring the structure information from large networks to compact ones for dense prediction tasks in computer vision. Previous knowledge distillation strategies used for dense prediction tasks often directly borrow the distillation scheme for image classification and perform knowledge distillation for each pixel separately, leading to sub-optimal performance. Here we propose to distill structured knowledge from large networks to compact networks, taking into account the fact that dense prediction is a structured prediction problem. Specifically, we study two structured distillation schemes: i) pair-wise distillation that distills the pair-wise similarities by building a static graph; and ii) holistic distillation that uses adversarial training to distill holistic knowledge. The effectiveness of our knowledge distillation approaches is demonstrated by experiments on three dense prediction tasks: semantic segmentation, depth estimation and object detection. Code is available at: https://git.io/StructKD
Communication-efficient distributed SGD with Sketching
Venue: arXiv cs.LG 2020
Year: 2020

Large-scale distributed training of neural networks is often limited by network bandwidth, wherein the communication time overwhelms the local computation time. Motivated by the success of sketching methods in sub-linear/streaming algorithms, we introduce Sketched SGD, an algorithm for carrying out distributed SGD by communicating sketches instead of full gradients. We show that Sketched SGD has favorable convergence rates on several classes of functions. When considering all communication -- both of gradients and of updated model weights -- Sketched SGD reduces the amount of communication required compared to other gradient compression methods from $\mathcal{O}(d)$ or $\mathcal{O}(W)$ to $\mathcal{O}(\log d)$, where $d$ is the number of model parameters and $W$ is the number of workers participating in training. We run experiments on a transformer model, an LSTM, and a residual network, demonstrating up to a 40x reduction in total communication cost with no loss in final model performance. We also show experimentally that Sketched SGD scales to at least 256 workers without increasing communication cost or degrading model performance.
Transparency and Control in Platforms for Networked Markets
Venue: arXiv cs.GT 2020
Year: 2020

In this paper, we analyze the worst case efficiency loss of online platform designs under a networked Cournot competition model. Inspired by some of the largest platforms in operation today, the platform designs that we consider examine the trade-off between transparency and control. Our results show that open access designs incentivize increased production towards perfectly competitive levels and limit efficiency loss, while controlled allocation designs lead to producer-platform incentive misalignment, resulting in low participation and unbounded efficiency loss. We also show that discriminatory access designs balance transparency and control, achieving the best of both worlds by maintaining high participation rates while limiting efficiency loss.
Security, Privacy and Trust for Smart Mobile-Internet of Things (M-IoT): A Survey
Venue: arXiv cs.NI 2020
Year: 2020

With an enormous range of applications, Internet of Things (IoT) has magnetized industries and academicians from everywhere. IoT facilitates operations through ubiquitous connectivity by providing Internet access to all the devices with computing capabilities. With the evolution of wireless infrastructure, the focus from simple IoT has been shifted to smart, connected and mobile IoT (M-IoT) devices and platforms, which can enable low-complexity, low-cost and efficient computing through sensors, machines, and even crowdsourcing. All these devices can be grouped under a common term of M-IoT. Even though the positive impact on applications has been tremendous, security, privacy and trust are still the major concerns for such networks and an insufficient enforcement of these requirements introduces non-negligible threats to M-IoT devices and platforms. Thus, it is important to understand the range of solutions which are available for providing a secure, privacy-compliant, and trustworthy mechanism for M-IoT. There is no direct survey available, which focuses on security, privacy, trust, secure protocols, physical layer security and handover protections in M-IoT. This paper covers such requisites and presents comparisons of state-the-art solutions for IoT which are applicable to security, privacy, and trust in smart and connected M-IoT networks. Apart from these, various challenges, applications, advantages, technologies, standards, open issues, and roadmap for security, privacy and trust are also discussed in this paper.
On the Trade-off Between Controllability and Robustness in Networks of Diffusively Coupled Agents
Venue: arXiv cs.SY 2020
Year: 2020

In this paper, we demonstrate a conflicting relationship between two crucial properties---controllability and robustness---in linear dynamical networks of diffusively coupled agents. In particular, for any given number of nodes $N$ and diameter $D$, we identify networks that are maximally robust using the notion of Kirchhoff index and then analyze their strong structural controllability. For this, we compute the minimum number of leaders, which are the nodes directly receiving external control inputs, needed to make such networks controllable under all feasible coupling weights between agents. Then, for any $N$ and $D$, we obtain a sharp upper bound on the minimum number of leaders needed to design strong structurally controllable networks with $N$ nodes and diameter $D$. We also discuss that the bound is best possible for arbitrary $N$ and $D$. Moreover, we construct a family of graphs for any $N$ and $D$ such that the graphs have maximal edge sets (maximal robustness) while being strong structurally controllable with the number of leaders in the proposed sharp bound. We then analyze the robustness of this graph family. The results suggest that optimizing robustness increases the number of leaders needed for strong structural controllability. Our analysis is based on graph-theoretic methods and can be applied to exploit network structure to co-optimize robustness and controllability in networks.
Secure State Estimation with Byzantine Sensors: A Probabilistic Approach
Venue: arXiv cs.SY 2020
Year: 2020

This paper studies static state estimation in multi-sensor settings, with a caveat that an unknown subset of the sensors are compromised by an adversary, whose measurements can be manipulated arbitrarily. The attacker is able to compromise $q$ out of $m$ sensors. A new performance metric, which quantifies the asymptotic decay rate for the probability of having an estimation error larger than $δ$, is proposed. We develop an optimal estimator for the new performance metric with a fixed $δ$, which is the Chebyshev center of a union of ellipsoids. We further provide an estimator that is optimal for every $δ$, for the special case where the sensors are homogeneous. Numerical examples are given to elaborate the results.
A Functional (Monadic) Second-Order Theory of Infinite Trees
Venue: arXiv cs.LO 2020
Year: 2020

This paper presents a complete axiomatization of Monadic Second-Order Logic (MSO) over infinite trees. MSO on infinite trees is a rich system, and its decidability ("Rabin's Tree Theorem") is one of the most powerful known results concerning the decidability of logics. By a complete axiomatization we mean a complete deduction system with a polynomial-time recognizable set of axioms. By naive enumeration of formal derivations, this formally gives a proof of Rabin's Tree Theorem. The deduction system consists of the usual rules for second-order logic seen as two-sorted first-order logic, together with the natural adaptation In addition, it contains an axiom scheme expressing the (positional) determinacy of certain parity games. The main difficulty resides in the limited expressive power of the language of MSO. We actually devise an extension of MSO, called Functional (Monadic) Second-Order Logic (FSO), which allows us to uniformly manipulate (hereditarily) finite sets and corresponding labeled trees, and whose language allows for higher abstraction than that of MSO.
Enabling Spike-based Backpropagation for Training Deep Neural Network Architectures
Venue: arXiv cs.NE 2020
Year: 2020

Spiking Neural Networks (SNNs) have recently emerged as a prominent neural computing paradigm. However, the typical shallow SNN architectures have limited capacity for expressing complex representations while training deep SNNs using input spikes has not been successful so far. Diverse methods have been proposed to get around this issue such as converting off-the-shelf trained deep Artificial Neural Networks (ANNs) to SNNs. However, the ANN-SNN conversion scheme fails to capture the temporal dynamics of a spiking system. On the other hand, it is still a difficult problem to directly train deep SNNs using input spike events due to the discontinuous, non-differentiable nature of the spike generation function. To overcome this problem, we propose an approximate derivative method that accounts for the leaky behavior of LIF neurons. This method enables training deep convolutional SNNs directly (with input spike events) using spike-based backpropagation. Our experiments show the effectiveness of the proposed spike-based learning on deep networks (VGG and Residual architectures) by achieving the best classification accuracies in MNIST, SVHN and CIFAR-10 datasets compared to other SNNs trained with a spike-based learning. Moreover, we analyze sparse event-based computations to demonstrate the efficacy of the proposed SNN training method for inference operation in the spiking domain.
A Quantum Annealing Algorithm for Finding Pure Nash Equilibria in Graphical Games
Venue: arXiv cs.GT 2020
Year: 2020

We introduce Q-Nash, a quantum annealing algorithm for the NP-complete problem of Fnding pure Nash equilibria in graphical games. The algorithm consists of two phases. The first phase determines all combinations of best response strategies for each player using classical computation. The second phase finds pure Nash equilibria using a quantum annealing device by mapping the computed combinations to a quadratic unconstrained binary optimization formulation based on the Set Cover problem. We empirically evaluate Q-Nash on D-Wave's Quantum Annealer 2000Q using different graphical game topologies. The results with respect to solution quality and computing time are compared to a Brute Force algorithm and the Iterated Best Response heuristic.
EV-IMO: Motion Segmentation Dataset and Learning Pipeline for Event Cameras
Venue: arXiv cs.CV 2020
Year: 2020

We present the first event-based learning approach for motion segmentation in indoor scenes and the first event-based dataset - EV-IMO - which includes accurate pixel-wise motion masks, egomotion and ground truth depth. Our approach is based on an efficient implementation of the SfM learning pipeline using a low parameter neural network architecture on event data. In addition to camera egomotion and a dense depth map, the network estimates pixel-wise independently moving object segmentation and computes per-object 3D translational velocities for moving objects. We also train a shallow network with just 40k parameters, which is able to compute depth and egomotion. Our EV-IMO dataset features 32 minutes of indoor recording with up to 3 fast moving objects simultaneously in the camera field of view. The objects and the camera are tracked by the VICON motion capture system. By 3D scanning the room and the objects, accurate depth map ground truth and pixel-wise object masks are obtained, which are reliable even in poor lighting conditions and during fast motion. We then train and evaluate our learning pipeline on EV-IMO and demonstrate that our approach far surpasses its rivals and is well suited for scene constrained robotics applications.
Neural Networks for Lorenz Map Prediction: A Trip Through Time
Venue: arXiv cs.LG 2020
Year: 2020

In this article the Lorenz dynamical system is revived and revisited and the current state of the art results for one step ahead forecasting for the Lorenz trajectories are published. Multitask learning is shown to help learning the hard to learn z trajectory. The article is a reflection upon the evolution of neural networks with respect to the prediction performance on this canonical task.
Hybrid Approaches for our Participation to the n2c2 Challenge on Cohort Selection for Clinical Trials
Venue: arXiv cs.CL 2020
Year: 2020

Objective: Natural language processing can help minimize human intervention in identifying patients meeting eligibility criteria for clinical trials, but there is still a long way to go to obtain a general and systematic approach that is useful for researchers. We describe two methods taking a step in this direction and present their results obtained during the n2c2 challenge on cohort selection for clinical trials. Materials and Methods: The first method is a weakly supervised method using an unlabeled corpus (MIMIC) to build a silver standard, by producing semi-automatically a small and very precise set of rules to detect some samples of positive and negative patients. This silver standard is then used to train a traditional supervised model. The second method is a terminology-based approach where a medical expert selects the appropriate concepts, and a procedure is defined to search the terms and check the structural or temporal constraints. Results: On the n2c2 dataset containing annotated data about 13 selection criteria on 288 patients, we obtained an overall F1-measure of 0.8969, which is the third best result out of 45 participant teams, with no statistically significant difference with the best-ranked team. Discussion: Both approaches obtained very encouraging results and apply to different types of criteria. The weakly supervised method requires explicit descriptions of positive and negative examples in some reports. The terminology-based method is very efficient when medical concepts carry most of the relevant information. Conclusion: It is unlikely that much more annotated data will be soon available for the task of identifying a wide range of patient phenotypes. One must focus on weakly or non-supervised learning methods using both structured and unstructured data and relying on a comprehensive representation of the patients.
Querying Streaming System Monitoring Data for Enterprise System Anomaly Detection
Venue: arXiv cs.CR 2020
Year: 2020

The need for countering Advanced Persistent Threat (APT) attacks has led to the solutions that ubiquitously monitor system activities in each enterprise host, and perform timely abnormal system behavior detection over the stream of monitoring data. However, existing stream-based solutions lack explicit language constructs for expressing anomaly models that capture abnormal system behaviors, thus facing challenges in incorporating expert knowledge to perform timely anomaly detection over the large-scale monitoring data. To address these limitations, we build SAQL, a novel stream-based query system that takes as input, a real-time event feed aggregated from multiple hosts in an enterprise, and provides an anomaly query engine that queries the event feed to identify abnormal behaviors based on the specified anomaly models. SAQL provides a domain-specific query language, Stream-based Anomaly Query Language (SAQL), that uniquely integrates critical primitives for expressing major types of anomaly models. In the demo, we aim to show the complete usage scenario of SAQL by (1) performing an APT attack in a controlled environment, and (2) using SAQL to detect the abnormal behaviors in real time by querying the collected stream of system monitoring data that contains the attack traces. The audience will have the option to interact with the system and detect the attack footprints in real time via issuing queries and checking the query results through a command-line UI.
Video Object Segmentation-based Visual Servo Control and Object Depth Estimation on a Mobile Robot
Venue: arXiv cs.RO 2020
Year: 2020

To be useful in everyday environments, robots must be able to identify and locate real-world objects. In recent years, video object segmentation has made significant progress on densely separating such objects from background in real and challenging videos. Building off of this progress, this paper addresses the problem of identifying generic objects and locating them in 3D using a mobile robot with an RGB camera. We achieve this by, first, introducing a video object segmentation-based approach to visual servo control and active perception and, second, developing a new Hadamard-Broyden update formulation. Our segmentation-based methods are simple but effective, and our update formulation lets a robot quickly learn the relationship between actuators and visual features without any camera calibration. We validate our approach in experiments by learning a variety of actuator-camera configurations on a mobile HSR robot, which subsequently identifies, locates, and grasps objects from the YCB dataset and tracks people and other dynamic articulated objects in real-time.
Reliability Maximization in Uncertain Graphs
Venue: arXiv cs.DB 2020
Year: 2020

Network reliability measures the probability that a target node is reachable from a source node in an uncertain graph, i.e., a graph where every edge is associated with a probability of existence. In this paper, we investigate the novel and fundamental problem of adding a small number of edges in the uncertain network for maximizing the reliability between a given pair of nodes. We study the NP-hardness and the approximation hardness of our problem, and design effective, scalable solutions. Furthermore, we consider extended versions of our problem (e.g., multiple source and target nodes can be provided as input) to support and demonstrate a wider family of queries and applications, including sensor network reliability maximization and social influence maximization. Experimental results validate the effectiveness and efficiency of the proposed algorithms.
Accelerating Gradient Boosting Machine
Venue: arXiv cs.LG 2020
Year: 2020

Gradient Boosting Machine (GBM) is an extremely powerful supervised learning algorithm that is widely used in practice. GBM routinely features as a leading algorithm in machine learning competitions such as Kaggle and the KDDCup. In this work, we propose Accelerated Gradient Boosting Machine (AGBM) by incorporating Nesterov's acceleration techniques into the design of GBM. The difficulty in accelerating GBM lies in the fact that weak (inexact) learners are commonly used, and therefore the errors can accumulate in the momentum term. To overcome it, we design a "corrected pseudo residual" and fit best weak learner to this corrected pseudo residual, in order to perform the z-update. Thus, we are able to derive novel computational guarantees for AGBM. This is the first GBM type of algorithm with theoretically-justified accelerated convergence rate. Finally we demonstrate with a number of numerical experiments the effectiveness of AGBM over conventional GBM in obtaining a model with good training and/or testing data fidelity.