OpenRaiser/Intern-Atlas huggingface dataset:
Improved Algorithms for Population Recovery from the Deletion Channel
Venue: arXiv cs.DS 2020
Year: 2020

The population recovery problem asks one to recover an unknown distribution over $n$-bit strings given access to independent noisy samples of strings drawn from the distribution. Recently, Ban et al. [BCF+19] studied the problem where the noise is induced through the deletion channel. This problem generalizes the famous trace reconstruction problem, where one wishes to learn a single string under the deletion channel. Ban et al. showed how to learn $\ell$-sparse distributions over strings using $\exp\big(n^{1/2} \cdot (\log n)^{O(\ell)}\big)$ samples. In this work, we learn the distribution using only $\exp\big(\tilde{O}(n^{1/3}) \cdot \ell^2\big)$ samples, by developing a higher-moment analog of the algorithms of [DOS17, NP17], which solve trace reconstruction in $\exp\big(\tilde{O}(n^{1/3})\big)$ samples. We also give the first algorithm with a runtime subexponential in $n$, solving population recovery in $\exp\big(\tilde{O}(n^{1/3}) \cdot \ell^3\big)$ samples and time. Notably, our dependence on $n$ nearly matches the upper bound of [DOS17, NP17] when $\ell = O(1)$, and we reduce the dependence on $\ell$ from doubly to singly exponential. Therefore, we are able to learn large mixtures of strings: while Ban et al.'s algorithm can only learn a mixture of $O(\log n/\log \log n)$ strings with a subexponential number of samples, we are able to learn a mixture of $n^{o(1)}$ strings in $\exp\big(n^{1/3 + o(1)}\big)$ samples and time.
MxPool: Multiplex Pooling for Hierarchical Graph Representation Learning
Venue: arXiv cs.LG 2020
Year: 2020

How to utilize deep learning methods for graph classification tasks has attracted considerable research attention in the past few years. Regarding graph classification tasks, the graphs to be classified may have various graph sizes (i.e., different number of nodes and edges) and have various graph properties (e.g., average node degree, diameter, and clustering coefficient). The diverse property of graphs has imposed significant challenges on existing graph learning techniques since diverse graphs have different best-fit hyperparameters. It is difficult to learn graph features from a set of diverse graphs by a unified graph neural network. This motivates us to use a multiplex structure in a diverse way and utilize a priori properties of graphs to guide the learning. In this paper, we propose MxPool, which concurrently uses multiple graph convolution/pooling networks to build a hierarchical learning structure for graph representation learning tasks. Our experiments on numerous graph classification benchmarks show that our MxPool has superiority over other state-of-the-art graph representation learning methods.
Contextual-Bandit Anomaly Detection for IoT Data in Distributed Hierarchical Edge Computing
Venue: arXiv cs.LG 2020
Year: 2020

Advances in deep neural networks (DNN) greatly bolster real-time detection of anomalous IoT data. However, IoT devices can hardly afford complex DNN models, and offloading anomaly detection tasks to the cloud incurs long delay. In this paper, we propose and build a demo for an adaptive anomaly detection approach for distributed hierarchical edge computing (HEC) systems to solve this problem, for both univariate and multivariate IoT data. First, we construct multiple anomaly detection DNN models with increasing complexity, and associate each model with a layer in HEC from bottom to top. Then, we design an adaptive scheme to select one of these models on the fly, based on the contextual information extracted from each input data. The model selection is formulated as a contextual bandit problem characterized by a single-step Markov decision process, and is solved using a reinforcement learning policy network. We build an HEC testbed, implement our proposed approach, and evaluate it using real IoT datasets. The demo shows that our proposed approach significantly reduces detection delay (e.g., by 71.4% for univariate dataset) without sacrificing accuracy, as compared to offloading detection tasks to the cloud. We also compare it with other baseline schemes and demonstrate that it achieves the best accuracy-delay tradeoff. Our demo is also available online: https://rebrand.ly/91a71
Explaining Regression Based Neural Network Model
Venue: arXiv cs.CV 2020
Year: 2020

Several methods have been proposed to explain Deep Neural Network (DNN). However, to our knowledge, only classification networks have been studied to try to determine which input dimensions motivated the decision. Furthermore, as there is no ground truth to this problem, results are only assessed qualitatively in regards to what would be meaningful for a human. In this work, we design an experimental settings where the ground truth can been established: we generate ideal signals and disrupted signals with errors and learn a neural network that determines the quality of the signals. This quality is simply a score based on the distance between the disrupted signals and the corresponding ideal signal. We then try to find out how the network estimated this score and hope to find the time-step and dimensions of the signal where errors are present. This experimental setting enables us to compare several methods for network explanation and to propose a new method, named AGRA for Accurate Gradient, based on several trainings that decrease the noise present in most state-of-the-art results. Comparative results show that the proposed method outperforms state-of-the-art methods for locating time-steps where errors occur in the signal.
Decoding algorithms of monotone codes and azinv codes and their unified view
Venue: arXiv cs.IT 2020
Year: 2020

This paper investigates linear-time decoding algorithms for two classes of error-correcting codes. One of the classes is monotone codes which are known as single deletion codes. The other is azinv codes which are known as single balanced adjacent deletion codes. As results, this paper proposes generalizations of Levenshtein's decoding algorithm for Levenshtein's single deletion codes. This paper points out that it is possible to unify our new two decoding algorithms.
Pilot Assignment in Cell-Free Massive MIMO based on the Hungarian Algorithm
Venue: arXiv cs.IT 2020
Year: 2020

This letter focuses on the problem of pilot assignment in cell-free massive MIMO systems. Exploiting the well-known Hungarian algorithms, two procedures are proposed, one maximizing the system throughput, and the other one maximizing the fairness across users. The algorithms operate based on the knowledge of large-scale fading coefficients as a proxy for the distances between users in the system and take into account both the uplink and downlink performance. Numerical results show that the proposed pilot assignment algorithms are effective and outperform the many competing alternatives available in the literature.
Benchmarking Unsupervised Outlier Detection with Realistic Synthetic Data
Venue: arXiv cs.LG 2020
Year: 2020

Benchmarking unsupervised outlier detection is difficult. Outliers are rare, and existing benchmark data contains outliers with various and unknown characteristics. Fully synthetic data usually consists of outliers and regular instance with clear characteristics and thus allows for a more meaningful evaluation of detection methods in principle. Nonetheless, there have only been few attempts to include synthetic data in benchmarks for outlier detection. This might be due to the imprecise notion of outliers or to the difficulty to arrive at a good coverage of different domains with synthetic data. In this work we propose a generic process for the generation of data sets for such benchmarking. The core idea is to reconstruct regular instances from existing real-world benchmark data while generating outliers so that they exhibit insightful characteristics. This allows both for a good coverage of domains and for helpful interpretations of results. We also describe three instantiations of the generic process that generate outliers with specific characteristics, like local outliers. A benchmark with state-of-the-art detection methods confirms that our generic process is indeed practical.
ActionSpotter: Deep Reinforcement Learning Framework for Temporal Action Spotting in Videos
Venue: arXiv cs.LG 2020
Year: 2020

Summarizing video content is an important task in many applications. This task can be defined as the computation of the ordered list of actions present in a video. Such a list could be extracted using action detection algorithms. However, it is not necessary to determine the temporal boundaries of actions to know their existence. Moreover, localizing precise boundaries usually requires dense video analysis to be effective. In this work, we propose to directly compute this ordered list by sparsely browsing the video and selecting one frame per action instance, task known as action spotting in literature. To do this, we propose ActionSpotter, a spotting algorithm that takes advantage of Deep Reinforcement Learning to efficiently spot actions while adapting its video browsing speed, without additional supervision. Experiments performed on datasets THUMOS14 and ActivityNet show that our framework outperforms state of the art detection methods. In particular, the spotting mean Average Precision on THUMOS14 is significantly improved from 59.7% to 65.6% while skipping 23% of video.
Ants can orienteer a thief in their robbery
Venue: arXiv cs.AI 2020
Year: 2020

The Thief Orienteering Problem (ThOP) is a multi-component problem that combines features of two classic combinatorial optimization problems: Orienteering Problem and Knapsack Problem. The ThOP is challenging due to the given time constraint and the interaction between its components. We propose an Ant Colony Optimization algorithm together with a new packing heuristic to deal individually and interactively with problem components. Our approach outperforms existing work on more than 90% of the benchmarking instances, with an average improvement of over 300%.
Computing Tropical Prevarieties with Satisfiability Modulo Theories (SMT) Solvers
Venue: arXiv cs.LO 2020
Year: 2020

A novel way to use SMT (Satisfiability Modulo Theories) solvers to compute the tropical prevariety (resp. equilibrium) of a polynomial system is presented. The new method is benchmarked against a naive approach that uses purely polyhedral methods. It turns out that the SMT approach is faster than the polyhedral approach for models that would otherwise take more than one minute to compute, in many cases by a factor of 60 or more, and in the worst case is only slower by a factor of two. Furthermore, the new approach is an anytime algorithm, thus offering a way to compute parts of the solution when the polyhedral approach is infeasible.
Hardening X.509 Certificate Issuance using Distributed Ledger Technology
Venue: arXiv cs.CR 2020
Year: 2020

The security of cryptographic communication protocols that use X.509 certificates depends on the correctness of those certificates. This paper proposes a system that helps to ensure the correct operation of an X.509 certification authority and its registration authorities. We achieve this goal by enforcing a policy-defined, multi-party validation and authorization workflow of certificate signing requests. Besides, our system offers full accountability for this workflow for forensic purposes. As a foundation for our implementation, we leverage the distributed ledger and smart contract framework Hyperledger Fabric. Our implementation inherits the strong tamper-resistance of Fabric which strengthens the integrity of the computer processes that enforce the validation and authorization of the certificate signing request, and of the metadata collected during certificate issuance.
Dissecting Energy Consumption of NB-IoT Devices Empirically
Venue: arXiv cs.NI 2020
Year: 2020

3GPP has recently introduced NB-IoT, a new mobile communication standard offering a robust and energy efficient connectivity option to the rapidly expanding market of Internet of Things (IoT) devices. To unleash its full potential, end-devices are expected to work in a plug and play fashion, with zero or minimal parameters configuration, still exhibiting excellent energy efficiency. We perform the most comprehensive set of empirical measurements with commercial IoT devices and different operators to date, quantifying the impact of several parameters to energy consumption. Our campaign proves that parameters setting does impact energy consumption, so proper configuration is necessary. We shed light on this aspect by first illustrating how the nominal standard operational modes map into real current consumption patterns of NB-IoT devices. Further, we investigate which device reported metadata metrics better reflect performance and implement an algorithm to automatically identify device state in current time series logs. Then, we provide a measurement-driven analysis of the energy consumption and network performance of two popular NB-IoT boards under different parameter configurations and with two major western European operators. We observed that energy consumption is mostly affected by the paging interval in Connected state, set by the base station. However, not all operators correctly implement such settings. Furthermore, under the default configuration, energy consumption in not strongly affected by packet size nor by signal quality, unless it is extremely bad. Our observations indicate that simple modifications to the default parameters settings can yield great energy savings.
Learning Furniture Compatibility with Graph Neural Networks
Venue: arXiv cs.CV 2020
Year: 2020

We propose a graph neural network (GNN) approach to the problem of predicting the stylistic compatibility of a set of furniture items from images. While most existing results are based on siamese networks which evaluate pairwise compatibility between items, the proposed GNN architecture exploits relational information among groups of items. We present two GNN models, both of which comprise a deep CNN that extracts a feature representation for each image, a gated recurrent unit (GRU) network that models interactions between the furniture items in a set, and an aggregation function that calculates the compatibility score. In the first model, a generalized contrastive loss function that promotes the generation of clustered embeddings for items belonging to the same furniture set is introduced. Also, in the first model, the edge function between nodes in the GRU and the aggregation function are fixed in order to limit model complexity and allow training on smaller datasets; in the second model, the edge function and aggregation function are learned directly from the data. We demonstrate state-of-the art accuracy for compatibility prediction and "fill in the blank" tasks on the Bonn and Singapore furniture datasets. We further introduce a new dataset, called the Target Furniture Collections dataset, which contains over 6000 furniture items that have been hand-curated by stylists to make up 1632 compatible sets. We also demonstrate superior prediction accuracy on this dataset.
Ownership at Large -- Open Problems and Challenges in Ownership Management
Venue: arXiv cs.SE 2020
Year: 2020

Software-intensive organizations rely on large numbers of software assets of different types, e.g., source-code files, tables in the data warehouse, and software configurations. Who is the most suitable owner of a given asset changes over time, e.g., due to reorganization and individual function changes. New forms of automation can help suggest more suitable owners for any given asset at a given point in time. By such efforts on ownership health, accountability of ownership is increased. The problem of finding the most suitable owners for an asset is essentially a program comprehension problem: how do we automatically determine who would be best placed to understand, maintain, evolve (and thereby assume ownership of) a given asset. This paper introduces the Facebook Ownesty system, which uses a combination of ultra large scale data mining and machine learning and has been deployed at Facebook as part of the company's ownership management approach. Ownesty processes many millions of software assets (e.g., source-code files) and it takes into account workflow and organizational aspects. The paper sets out open problems and challenges on ownership for the research community with advances expected from the fields of software engineering, programming languages, and machine learning.
COVID-19 Antibody Test / Vaccination Certification: There's an app for that
Venue: arXiv cs.CR 2020
Year: 2020

Goal: As the Coronavirus Pandemic of 2019/2020 unfolds, a COVID-19 'Immunity Passport' has been mooted as a way to enable individuals to return back to work. While the quality of antibody testing, the availability of vaccines, and the likelihood of even attaining COVID-19 immunity continue to be researched, we address the issues involved in providing tamper-proof and privacy-preserving certification for test results and vaccinations. Methods: We developed a prototype mobile phone app and requisite decentralized server architecture that facilitates instant verification of tamper-proof test results. Personally identifiable information is only stored at the user's discretion, and the app allows the end-user selectively to present only the specific test result with no other personal information revealed. The architecture, designed for scalability, relies upon (a) the 2019 World Wide Web Consortium standard called 'Verifiable Credentials', (b) Tim Berners-Lee's decentralized personal data platform 'Solid', and (c) a Consortium Ethereum-based blockchain. Results: Our mobile phone app and decentralized server architecture enable the mixture of verifiability and privacy in a manner derived from public/private key pairs and digital signatures, generalized to avoid restrictive ownership of sensitive digital keys and/or data. Benchmark performance tests show it to scale linearly in the worst case, as significant processing is done locally on each app. For the test certificate Holder, Issuer (e.g. healthcare staff, pharmacy) and Verifier (e.g. employer), it is 'just another app' which takes only minutes to use. Conclusions: The app and decentralized server architecture offer a prototype proof of concept that is readily scalable, applicable generically, and in effect 'waiting in the wings' for the biological issues, plus key ethical issues raised in the discussion section, to be resolved.
Generalized Shortest Path-based Superpixels for Accurate Segmentation of Spherical Images
Venue: arXiv cs.CV 2020
Year: 2020

Most of existing superpixel methods are designed to segment standard planar images as pre-processing for computer vision pipelines. Nevertheless, the increasing number of applications based on wide angle capture devices, mainly generating 360° spherical images, have enforced the need for dedicated superpixel approaches. In this paper, we introduce a new superpixel method for spherical images called SphSPS (for Spherical Shortest Path-based Superpixels). Our approach respects the spherical geometry and generalizes the notion of shortest path between a pixel and a superpixel center on the 3D spherical acquisition space. We show that the feature information on such path can be efficiently integrated into our clustering framework and jointly improves the respect of object contours and the shape regularity. To relevantly evaluate this last aspect in the spherical space, we also generalize a planar global regularity metric. Finally, the proposed SphSPS method obtains significantly better performance than both planar and recent spherical superpixel approaches on the reference 360° spherical panorama segmentation dataset.
Single upper limb pose estimation method based on improved stacked hourglass network
Venue: arXiv cs.CV 2020
Year: 2020

At present, most high-accuracy single-person pose estimation methods have high computational complexity and insufficient real-time performance due to the complex structure of the network model. However, a single-person pose estimation method with high real-time performance also needs to improve its accuracy due to the simple structure of the network model. It is currently difficult to achieve both high accuracy and real-time performance in single-person pose estimation. For use in human-machine cooperative operations, this paper proposes a single-person upper limb pose estimation method based on an end-to-end approach for accurate and real-time limb pose estimation. Using the stacked hourglass network model, a single-person upper limb skeleton key point detection model was designed.Deconvolution was employed to replace the up-sampling operation of the hourglass module in the original model, solving the problem of rough feature maps. Integral regression was used to calculate the position coordinates of key points of the skeleton, reducing quantization errors and calculations. Experiments showed that the developed single-person upper limb skeleton key point detection model achieves high accuracy and that the pose estimation method based on the end-to-end approach provides high accuracy and real-time performance.
PICK: Processing Key Information Extraction from Documents using Improved Graph Learning-Convolutional Networks
Venue: arXiv cs.CV 2020
Year: 2020

Computer vision with state-of-the-art deep learning models has achieved huge success in the field of Optical Character Recognition (OCR) including text detection and recognition tasks recently. However, Key Information Extraction (KIE) from documents as the downstream task of OCR, having a large number of use scenarios in real-world, remains a challenge because documents not only have textual features extracting from OCR systems but also have semantic visual features that are not fully exploited and play a critical role in KIE. Too little work has been devoted to efficiently make full use of both textual and visual features of the documents. In this paper, we introduce PICK, a framework that is effective and robust in handling complex documents layout for KIE by combining graph learning with graph convolution operation, yielding a richer semantic representation containing the textual and visual features and global layout without ambiguity. Extensive experiments on real-world datasets have been conducted to show that our method outperforms baselines methods by significant margins. Our code is available at https://github.com/wenwenyu/PICK-pytorch.
Refined Mean Field Analysis of the Gossip Shuffle Protocol -- extended version --
Venue: arXiv cs.PF 2020
Year: 2020

Gossip protocols form the basis of many smart collective adaptive systems. They are a class of fully decentralised, simple but robust protocols for the distribution of information throughout large scale networks with hundreds or thousands of nodes. Mean field analysis methods have made it possible to approximate and analyse performance aspects of such large scale protocols in an efficient way. Taking the gossip shuffle protocol as a benchmark, we evaluate a recently developed refined mean field approach. We illustrate the gain in accuracy this can provide for the analysis of medium size models analysing two key performance measures. We also show that refined mean field analysis requires special attention to correctly capture the coordination aspects of the gossip shuffle protocol.