OpenRaiser/Intern-Atlas huggingface dataset:
Update Frequently, Update Fast: Retraining Semantic Parsing Systems in a Fraction of Time
Venue: arXiv cs.CL 2021
Year: 2021

Currently used semantic parsing systems deployed in voice assistants can require weeks to train. Datasets for these models often receive small and frequent updates, data patches. Each patch requires training a new model. To reduce training time, one can fine-tune the previously trained model on each patch, but naive fine-tuning exhibits catastrophic forgetting - degradation of the model performance on the data not represented in the data patch. In this work, we propose a simple method that alleviates catastrophic forgetting and show that it is possible to match the performance of a model trained from scratch in less than 10% of a time via fine-tuning. The key to achieving this is supersampling and EWC regularization. We demonstrate the effectiveness of our method on multiple splits of the Facebook TOP and SNIPS datasets.
Window Processing of Binary Polarization Kernels
Venue: arXiv cs.IT 2021
Year: 2021

A decoding algorithm for polar (sub)codes with binary $2^t\times 2^t$ polarization kernels is presented. It is based on the window processing (WP) method, which exploits the linear relationship of the polarization kernels and the Arikan matrix. This relationship enables one to compute the kernel input symbols probabilities by computing the probabilities of several paths in Arikan successive cancellation (SC) decoder. In this paper we propose an improved version of WP, which has significantly lower arithmetic complexity and operates in log-likelihood ratios (LLRs) domain. The algorithm identifies and reuses common subexpressions arising in computation of Arikan SC path scores. The proposed algorithm is applied to kernels of size 16 and 32 with improved polarization properties. It enables polar (sub)codes with the considered kernels to simultaneously provide better performance and lower decoding complexity compared with polar (sub)codes with Arikan kernel.
Robotic Pick-and-Place With Uncertain Object Instance Segmentation and Shape Completion
Venue: arXiv cs.RO 2021
Year: 2021

We consider robotic pick-and-place of partially visible, novel objects, where goal placements are non-trivial, e.g., tightly packed into a bin. One approach is (a) use object instance segmentation and shape completion to model the objects and (b) use a regrasp planner to decide grasps and places displacing the models to their goals. However, it is critical for the planner to account for uncertainty in the perceived models, as object geometries in unobserved areas are just guesses. We account for perceptual uncertainty by incorporating it into the regrasp planner's cost function. We compare seven different costs. One of these, which uses neural networks to estimate probability of grasp and place stability, consistently outperforms uncertainty-unaware costs and evaluates faster than Monte Carlo sampling. On a real robot, the proposed cost results in successfully packing objects tightly into a bin 7.8% more often versus the commonly used minimum-number-of-grasps cost.
Multi-Resolution 3D Mapping with Explicit Free Space Representation for Fast and Accurate Mobile Robot Motion Planning
Venue: arXiv cs.RO 2021
Year: 2021

With the aim of bridging the gap between high quality reconstruction and mobile robot motion planning, we propose an efficient system that leverages the concept of adaptive-resolution volumetric mapping, which naturally integrates with the hierarchical decomposition of space in an octree data structure. Instead of a Truncated Signed Distance Function (TSDF), we adopt mapping of occupancy probabilities in log-odds representation, which allows to represent both surfaces, as well as the entire free, i.e. observed space, as opposed to unobserved space. We introduce a method for choosing resolution -- on the fly -- in real-time by means of a multi-scale max-min pooling of the input depth image. The notion of explicit free space mapping paired with the spatial hierarchy in the data structure, as well as map resolution, allows for collision queries, as needed for robot motion planning, at unprecedented speed. We quantitatively evaluate mapping accuracy, memory, runtime performance, and planning performance showing improvements over the state of the art, particularly in cases requiring high resolution maps.
Categorical Semantics of Cyber-Physical Systems Theory
Venue: arXiv cs.LO 2021
Year: 2021

Cyber-physical systems require the construction and management of various models to assure their correct, safe, and secure operation. These various models are necessary because of the coupled physical and computational dynamics present in cyber-physical systems. However, to date the different model views of cyber-physical systems are largely related informally, which raises issues with the degree of formal consistency between those various models of requirements, system behavior, and system architecture. We present a category-theoretic framework to make different types of composition explicit in the modeling and analysis of cyber-physical systems, which could assist in verifying the system as a whole. This compositional framework for cyber-physical systems gives rise to unified system models, where system behavior is hierarchically decomposed and related to a system architecture using the systems-as-algebras paradigm. As part of this paradigm, we show that an algebra of (safety) contracts generalizes over the state of the art, providing more uniform mathematical tools for constraining the behavior over a richer set of composite cyber-physical system models, which has the potential of minimizing or eliminating hazardous behavior.
Physics-informed GANs for Coastal Flood Visualization
Venue: arXiv cs.CV 2021
Year: 2021

As climate change increases the intensity of natural disasters, society needs better tools for adaptation. Floods, for example, are the most frequent natural disaster, but during hurricanes the area is largely covered by clouds and emergency managers must rely on nonintuitive flood visualizations for mission planning. To assist these emergency managers, we have created a deep learning pipeline that generates visual satellite images of current and future coastal flooding. We advanced a state-of-the-art GAN called pix2pixHD, such that it produces imagery that is physically-consistent with the output of an expert-validated storm surge model (NOAA SLOSH). By evaluating the imagery relative to physics-based flood maps, we find that our proposed framework outperforms baseline models in both physical-consistency and photorealism. While this work focused on the visualization of coastal floods, we envision the creation of a global visualization of how climate change will shape our earth.
BALM: Bundle Adjustment for Lidar Mapping
Venue: arXiv cs.RO 2021
Year: 2021

A local Bundle Adjustment (BA) on a sliding window of keyframes has been widely used in visual SLAM and proved to be very effective in lowering the drift. But in lidar SLAM, BA method is hardly used because the sparse feature points (e.g., edge and plane) make the exact point matching impossible. In this paper, we formulate the lidar BA as minimizing the distance from a feature point to its matched edge or plane. Unlike the visual SLAM (and prior plane adjustment method in lidar SLAM) where the feature has to be co-determined along with the pose, we show that the feature can be analytically solved and removed from the BA, the resultant BA is only dependent on the scan poses. This greatly reduces the optimization scale and allows large-scale dense plane and edge features to be used. To speedup the optimization, we derive the analytical derivatives of the cost function, up to second order, in closed form. Moreover, we propose a novel adaptive voxelization method to search feature correspondence efficiently. The proposed formulations are incorporated into a LOAM back-end for map refinement. Results show that, although as a back-end, the local BA can be solved very efficiently, even in real-time at 10Hz when optimizing 20 scans of point-cloud. The local BA also considerably lowers the LOAM drift. Our implementation of the BA optimization and LOAM are open-sourced to benefit the community.
How Does Supernet Help in Neural Architecture Search?
Venue: arXiv cs.LG 2021
Year: 2021

Weight sharing, as an approach to speed up architecture performance estimation has received wide attention. Instead of training each architecture separately, weight sharing builds a supernet that assembles all the architectures as its submodels. However, there has been debate over whether the NAS process actually benefits from weight sharing, due to the gap between supernet optimization and the objective of NAS. To further understand the effect of weight sharing on NAS, we conduct a comprehensive analysis on five search spaces, including NAS-Bench-101, NAS-Bench-201, DARTS-CIFAR10, DARTS-PTB, and ProxylessNAS. We find that weight sharing works well on some search spaces but fails on others. Taking a step forward, we further identified biases accounting for such phenomenon and the capacity of weight sharing. Our work is expected to inspire future NAS researchers to better leverage the power of weight sharing.
Quantum computing approach to railway dispatching and conflict management optimization on single-track railway lines
Venue: arXiv cs.ET 2021
Year: 2021

In this work, we consider a practical railway dispatching problem: delay and conflict management on a single-track railway line. We examine the issue of train dispatching consequences caused by the arrival of an already delayed train to the segment being considered. This problem is computationally hard and often needs to be solved timely. Here, we introduce a quadratic unconstrained binary optimization (QUBO) model of the problem in question, compatible with the emerging quantum annealing technology. The model's instances can be executed on present-day quantum annealers. As a proof-of-concept, we solve selected real-life problems from the Polish railway network using D-Wave quantum annealers. As a reference, we also provide solutions calculated with classical methods, including those relevant to the community (linear integer programming) and a sophisticated algorithm based on tensor networks for solving QUBO problems.
Graph Rewriting and Relabeling with PBPO+
Venue: arXiv cs.LO 2021
Year: 2021

We extend the powerful Pullback-Pushout (PBPO) approach for graph rewriting with strong matching. Our approach, called \pbpostrong, exerts more control over the embedding of the pattern in the host graph, which is important for a large class of graph rewrite systems. In addition, we show that \pbpostrong is well-suited for rewriting labeled graphs and certain classes of attributed graphs. For this purpose, we employ a lattice structure on the label set and use order-preserving graph morphisms. We argue that our approach is simpler and more general than related relabeling approaches in the literature.
Probabilistic Surface Friction Estimation Based on Visual and Haptic Measurements
Venue: arXiv cs.RO 2021
Year: 2021

Accurately modeling local surface properties of objects is crucial to many robotic applications, from grasping to material recognition. Surface properties like friction are however difficult to estimate, as visual observation of the object does not convey enough information over these properties. In contrast, haptic exploration is time consuming as it only provides information relevant to the explored parts of the object. In this work, we propose a joint visuo-haptic object model that enables the estimation of surface friction coefficient over an entire object by exploiting the correlation of visual and haptic information, together with a limited haptic exploration by a robotic arm. We demonstrate the validity of the proposed method by showing its ability to estimate varying friction coefficients on a range of real multi-material objects. Furthermore, we illustrate how the estimated friction coefficients can improve grasping success rate by guiding a grasp planner toward high friction areas.
Minimizing Labeling Effort for Tree Skeleton Segmentation using an Automated Iterative Training Methodology
Venue: arXiv cs.CV 2021
Year: 2021

Training of convolutional neural networks for semantic segmentation requires accurate pixel-wise labeling which requires large amounts of human effort. The human-in-the-loop method reduces labeling effort; however, it requires human intervention for each image. This paper describes a general iterative training methodology for semantic segmentation, Automating-the-Loop. This aims to replicate the manual adjustments of the human-in-the-loop method with an automated process, hence, drastically reducing labeling effort. Using the application of detecting partially occluded apple tree segmentation, we compare manually labeled annotations, self-training, human-in-the-loop, and Automating-the-Loop methods in both the quality of the trained convolutional neural networks, and the effort needed to create them. The convolutional neural network (U-Net) performance is analyzed using traditional metrics and a new metric, Complete Grid Scan, which promotes connectivity and low noise. It is shown that in our application, the new Automating-the-Loop method greatly reduces the labeling effort while producing comparable performance to both human-in-the-loop and complete manual labeling methods.
Detecting Fair Queuing for Better Congestion Control
Venue: arXiv cs.NI 2021
Year: 2021

Low delay is an explicit requirement for applications such as cloud gaming and video conferencing. Delay-based congestion control can achieve the same throughput but significantly smaller delay than loss-based one and is thus ideal for these applications. However, when a delay- and a loss-based flow compete for a bottleneck, the loss-based one can monopolize all the bandwidth and starve the delay-based one. Fair queuing at the bottleneck link solves this problem by assigning an equal share of the available bandwidth to each flow. However, so far no end host based algorithm to detect fair queuing exists. Our contribution is the development of an algorithm that detects fair queuing at flow startup and chooses delay-based congestion control if there is fair queuing. Otherwise, loss-based congestion control can be used as a backup option. Results show that our algorithm reliably detects fair queuing and can achieve low delay and high throughput in case fair queuing is detected.
Improving Schroeppel and Shamir's Algorithm for Subset Sum via Orthogonal Vectors
Venue: arXiv cs.DS 2021
Year: 2021

We present an $\mathcal{O}^\star(2^{0.5n})$ time and $\mathcal{O}^\star(2^{0.249999n})$ space randomized algorithm for solving worst-case Subset Sum instances with $n$ integers. This is the first improvement over the long-standing $\mathcal{O}^\star(2^{n/2})$ time and $\mathcal{O}^\star(2^{n/4})$ space algorithm due to Schroeppel and Shamir (FOCS 1979). We breach this gap in two steps: (1) We present a space efficient reduction to the Orthogonal Vectors Problem (OV), one of the most central problem in Fine-Grained Complexity. The reduction is established via an intricate combination of the method of Schroeppel and Shamir, and the representation technique introduced by Howgrave-Graham and Joux (EUROCRYPT 2010) for designing Subset Sum algorithms for the average case regime. (2) We provide an algorithm for OV that detects an orthogonal pair among $N$ given vectors in $\{0,1\}^d$ with support size $d/4$ in time $\tilde{O}(N\cdot2^d/\binom{d}{d/4})$. Our algorithm for OV is based on and refines the representative families framework developed by Fomin, Lokshtanov, Panolan and Saurabh (J. ACM 2016). Our reduction uncovers a curious tight relation between Subset Sum and OV, because any improvement of our algorithm for OV would imply an improvement over the runtime of Schroeppel and Shamir, which is also a long standing open problem.
Deep Neural Dynamic Bayesian Networks applied to EEG sleep spindles modeling
Venue: arXiv cs.LG 2021
Year: 2021

We propose a generative model for single-channel EEG that incorporates the constraints experts actively enforce during visual scoring. The framework takes the form of a dynamic Bayesian network with depth in both the latent variables and the observation likelihoods-while the hidden variables control the durations, state transitions, and robustness, the observation architectures parameterize Normal-Gamma distributions. The resulting model allows for time series segmentation into local, reoccurring dynamical regimes by exploiting probabilistic models and deep learning. Unlike typical detectors, our model takes the raw data (up to resampling) without pre-processing (e.g., filtering, windowing, thresholding) or post-processing (e.g., event merging). This not only makes the model appealing to real-time applications, but it also yields interpretable hyperparameters that are analogous to known clinical criteria. We derive algorithms for exact, tractable inference as a special case of Generalized Expectation Maximization via dynamic programming and backpropagation. We validate the model on three public datasets and provide support that more complex models are able to surpass state-of-the-art detectors while being transparent, auditable, and generalizable.
Check-N-Run: A Checkpointing System for Training Deep Learning Recommendation Models
Venue: arXiv cs.IR 2021
Year: 2021

Checkpoints play an important role in training long running machine learning (ML) models. Checkpoints take a snapshot of an ML model and store it in a non-volatile memory so that they can be used to recover from failures to ensure rapid training progress. In addition, they are used for online training to improve inference prediction accuracy with continuous learning. Given the large and ever increasing model sizes, checkpoint frequency is often bottlenecked by the storage write bandwidth and capacity. When checkpoints are maintained on remote storage, as is the case with many industrial settings, they are also bottlenecked by network bandwidth. We present Check-N-Run, a scalable checkpointing system for training large ML models at Facebook. While Check-N-Run is applicable to long running ML jobs, we focus on checkpointing recommendation models which are currently the largest ML models with Terabytes of model size. Check-N-Run uses two primary techniques to address the size and bandwidth challenges. First, it applies incremental checkpointing, which tracks and checkpoints the modified part of the model. Incremental checkpointing is particularly valuable in the context of recommendation models where only a fraction of the model (stored as embedding tables) is updated on each iteration. Second, Check-N-Run leverages quantization techniques to significantly reduce the checkpoint size, without degrading training accuracy. These techniques allow Check-N-Run to reduce the required write bandwidth by 6-17x and the required capacity by 2.5-8x on real-world models at Facebook, and thereby significantly improve checkpoint capabilities while reducing the total cost of ownership.
Locally Differentially Private Analysis of Graph Statistics
Venue: arXiv cs.CR 2021
Year: 2021

Differentially private analysis of graphs is widely used for releasing statistics from sensitive graphs while still preserving user privacy. Most existing algorithms however are in a centralized privacy model, where a trusted data curator holds the entire graph. As this model raises a number of privacy and security issues -- such as, the trustworthiness of the curator and the possibility of data breaches, it is desirable to consider algorithms in a more decentralized local model where no server holds the entire graph. In this work, we consider a local model, and present algorithms for counting subgraphs -- a fundamental task for analyzing the connection patterns in a graph -- with LDP (Local Differential Privacy). For triangle counts, we present algorithms that use one and two rounds of interaction, and show that an additional round can significantly improve the utility. For $k$-star counts, we present an algorithm that achieves an order optimal estimation error in the non-interactive local model. We provide new lower-bounds on the estimation error for general graph statistics including triangle counts and $k$-star counts. Finally, we perform extensive experiments on two real datasets, and show that it is indeed possible to accurately estimate subgraph counts in the local differential privacy model.
Towards Compact Neural Networks via End-to-End Training: A Bayesian Tensor Approach with Automatic Rank Determination
Venue: arXiv cs.LG 2021
Year: 2021

While post-training model compression can greatly reduce the inference cost of a deep neural network, uncompressed training still consumes a huge amount of hardware resources, run-time and energy. It is highly desirable to directly train a compact neural network from scratch with low memory and low computational cost. Low-rank tensor decomposition is one of the most effective approaches to reduce the memory and computing requirements of large-size neural networks. However, directly training a low-rank tensorized neural network is a very challenging task because it is hard to determine a proper tensor rank {\it a priori}, which controls the model complexity and compression ratio in the training process. This paper presents a novel end-to-end framework for low-rank tensorized training of neural networks. We first develop a flexible Bayesian model that can handle various low-rank tensor formats (e.g., CP, Tucker, tensor train and tensor-train matrix) that compress neural network parameters in training. This model can automatically determine the tensor ranks inside a nonlinear forward model, which is beyond the capability of existing Bayesian tensor methods. We further develop a scalable stochastic variational inference solver to estimate the posterior density of large-scale problems in training. Our work provides the first general-purpose rank-adaptive framework for end-to-end tensorized training. Our numerical results on various neural network architectures show orders-of-magnitude parameter reduction and little accuracy loss (or even better accuracy) in the training process. Specifically, on a very large deep learning recommendation system with over $4.2\times 10^9$ model parameters, our method can reduce the variables to only $1.6\times 10^5$ automatically in the training process (i.e., by $2.6\times 10^4$ times) while achieving almost the same accuracy.
Threats and Corrective Measures for IoT Security with Observance of Cybercrime: A Survey
Venue: arXiv cs.NI 2021
Year: 2021

Internet of Things (IoT) is the utmost assuring framework to facilitate human life with quality and comfort. IoT has contributed significantly to numerous application areas. The stormy expansion of smart devices and their credence for data transfer using wireless mechanics boosts their susceptibility to cyber-attacks. Consequently, the rate of cybercrime is increasing day by day. Hence, the study of IoT security threats and possible corrective measures can benefit the researchers to identify appropriate solutions to deal with various challenges in cybercrime investigation. IoT forensics plays a vital role in cybercrime investigations. This review paper presents an overview of the IoT framework consisting of IoT architecture, protocols, and technologies. Various security issues at each layer and corrective measures are also discussed in detail. This paper also presents the role of IoT forensics in cybercrime investigation in various domains like smart homes, smart cities, automated vehicles, healthcare, etc. Along with the role of advanced technologies like Artificial Intelligence, Machine Learning, Cloud computing, Edge computing, Fog computing, and Blockchain technology in cybercrime investigation are also discussed. At last, various open research challenges in IoT to assist cybercrime investigation are explained, which provide a new direction for further research.