OpenRaiser/Intern-Atlas huggingface dataset:
PIC: Permutation Invariant Convolution for Recognizing Long-range Activities
Venue: arXiv cs.CV 2020
Year: 2020

Neural operations as convolutions, self-attention, and vector aggregation are the go-to choices for recognizing short-range actions. However, they have three limitations in modeling long-range activities. This paper presents PIC, Permutation Invariant Convolution, a novel neural layer to model the temporal structure of long-range activities. It has three desirable properties. i. Unlike standard convolution, PIC is invariant to the temporal permutations of features within its receptive field, qualifying it to model the weak temporal structures. ii. Different from vector aggregation, PIC respects local connectivity, enabling it to learn long-range temporal abstractions using cascaded layers. iii. In contrast to self-attention, PIC uses shared weights, making it more capable of detecting the most discriminant visual evidence across long and noisy videos. We study the three properties of PIC and demonstrate its effectiveness in recognizing the long-range activities of Charades, Breakfast, and MultiThumos.
Triplet Permutation Method for Deep Learning of Single-Shot Person Re-Identification
Venue: arXiv cs.CV 2020
Year: 2020

Solving Single-Shot Person Re-Identification (Re-Id) by training Deep Convolutional Neural Networks is a daunting challenge, due to the lack of training data, since only two images per person are available. This causes the overfitting of the models, leading to degenerated performance. This paper formulates the Triplet Permutation method to generate multiple training sets, from a certain re-id dataset. This is a novel strategy for feeding triplet networks, which reduces the overfitting of the Single-Shot Re-Id model. The improved performance has been demonstrated over one of the most challenging Re-Id datasets, PRID2011, proving the effectiveness of the method.
Tatamibari is NP-complete
Venue: arXiv cs.CC 2020
Year: 2020

In the Nikoli pencil-and-paper game Tatamibari, a puzzle consists of an $m \times n$ grid of cells, where each cell possibly contains a clue among +, -, |. The goal is to partition the grid into disjoint rectangles, where every rectangle contains exactly one clue, rectangles containing + are square, rectangles containing - are strictly longer horizontally than vertically, rectangles containing | are strictly longer vertically than horizontally, and no four rectangles share a corner. We prove this puzzle NP-complete, establishing a Nikoli gap of 16 years. Along the way, we introduce a gadget framework for proving hardness of similar puzzles involving area coverage, and show that it applies to an existing NP-hardness proof for Spiral Galaxies. We also present a mathematical puzzle font for Tatamibari.
Survey of Privacy-Preserving Collaborative Filtering
Venue: arXiv cs.CR 2020
Year: 2020

Collaborative filtering recommendation systems provide recommendations to users based on their own past preferences, as well as those of other users who share similar interests. The use of recommendation systems has grown widely in recent years, helping people choose which movies to watch, books to read, and items to buy. However, users are often concerned about their privacy when using such systems, and many users are reluctant to provide accurate information to most online services. Privacy-preserving collaborative filtering recommendation systems aim to provide users with accurate recommendations while maintaining certain guarantees about the privacy of their data. This survey examines the recent literature in privacy-preserving collaborative filtering, providing a broad perspective of the field and classifying the key contributions in the literature using two different criteria: the type of vulnerability they address and the type of approach they use to solve it.
A Dataset and an Approach for Identity Resolution of 38 Million Author IDs extracted from 2B Git Commits
Venue: arXiv cs.SE 2020
Year: 2020

The data collected from open source projects provide means to model large software ecosystems, but often suffer from data quality issues, specifically, multiple author identification strings in code commits might actually be associated with one developer. While many methods have been proposed for addressing this problem, they are either heuristics requiring manual tweaking, or require too much calculation time to do pairwise comparisons for 38M author IDs in, for example, the World of Code collection. In this paper, we propose a method that finds all author IDs belonging to a single developer in this entire dataset, and share the list of all author IDs that were found to have aliases. To do this, we first create blocks of potentially connected author IDs and then use a machine learning model to predict which of these potentially related IDs belong to the same developer. We processed around 38 million author IDs and found around 14.8 million IDs to have an alias, which belong to 5.4 million different developers, with the median number of aliases being 2 per developer. This dataset can be used to create more accurate models of developer behaviour at the entire OSS ecosystem level and can be used to provide a service to rapidly resolve new author IDs.
Distant Supervision and Noisy Label Learning for Low Resource Named Entity Recognition: A Study on Hausa and Yorùbá
Venue: arXiv cs.CL 2020
Year: 2020

The lack of labeled training data has limited the development of natural language processing tools, such as named entity recognition, for many languages spoken in developing countries. Techniques such as distant and weak supervision can be used to create labeled data in a (semi-) automatic way. Additionally, to alleviate some of the negative effects of the errors in automatic annotation, noise-handling methods can be integrated. Pretrained word embeddings are another key component of most neural named entity classifiers. With the advent of more complex contextual word embeddings, an interesting trade-off between model size and performance arises. While these techniques have been shown to work well in high-resource settings, we want to study how they perform in low-resource scenarios. In this work, we perform named entity recognition for Hausa and Yorùbá, two languages that are widely spoken in several developing countries. We evaluate different embedding approaches and show that distant supervision can be successfully leveraged in a realistic low-resource scenario where it can more than double a classifier's performance.
X-Stance: A Multilingual Multi-Target Dataset for Stance Detection
Venue: arXiv cs.CL 2020
Year: 2020

We extract a large-scale stance detection dataset from comments written by candidates of elections in Switzerland. The dataset consists of German, French and Italian text, allowing for a cross-lingual evaluation of stance detection. It contains 67 000 comments on more than 150 political issues (targets). Unlike stance detection models that have specific target issues, we use the dataset to train a single model on all the issues. To make learning across targets possible, we prepend to each instance a natural question that represents the target (e.g. "Do you support X?"). Baseline results from multilingual BERT show that zero-shot cross-lingual and cross-target transfer of stance detection is moderately successful with this approach.
Fan-Crossing Free Graphs and Their Relationship to other Beyond-Planar Graphs
Venue: arXiv cs.DM 2020
Year: 2020

A graph is \emph{fan-crossing free} if it has a drawing in the plane so that each edge is crossed by independent edges, that is the crossing edges have distinct vertices. On the other hand, it is \emph{fan-crossing} if the crossing edges have a common vertex, that is they form a fan. Both are prominent examples for beyond-planar graphs. Further well-known beyond-planar classes are the $k$-planar, $k$-gap-planar, quasi-planar, and right angle crossing graphs. We use the subdivision, node-to-circle expansion and path-addition operations to distinguish all these graph classes. In particular, we show that the 2-subdivision and the node-to-circle expansion of any graph is fan-crossing free, which does not hold for fan-crossing and $k$-(gap)-planar graphs, respectively. Thereby, we obtain graphs that are fan-crossing free and neither fan-crossing nor $k$-(gap)-planar. Finally, we show that some graphs have a unique fan-crossing free embedding, that there are thinned maximal fan-crossing free graphs, and that the recognition problem for fan-crossing free graphs is NP-complete.
Reconstructing Sinus Anatomy from Endoscopic Video -- Towards a Radiation-free Approach for Quantitative Longitudinal Assessment
Venue: arXiv cs.CV 2020
Year: 2020

Reconstructing accurate 3D surface models of sinus anatomy directly from an endoscopic video is a promising avenue for cross-sectional and longitudinal analysis to better understand the relationship between sinus anatomy and surgical outcomes. We present a patient-specific, learning-based method for 3D reconstruction of sinus surface anatomy directly and only from endoscopic videos. We demonstrate the effectiveness and accuracy of our method on in and ex vivo data where we compare to sparse reconstructions from Structure from Motion, dense reconstruction from COLMAP, and ground truth anatomy from CT. Our textured reconstructions are watertight and enable measurement of clinically relevant parameters in good agreement with CT. The source code is available at https://github.com/lppllppl920/DenseReconstruction-Pytorch.
Empirical Characterization of Mobility of Multi-Device Internet Users
Venue: arXiv cs.CY 2020
Year: 2020

Understanding the mobility of humans and their devices is a fundamental problem in mobile computing. While there has been much work on empirical analysis of human mobility using mobile device data, prior work has largely assumed devices to be independent and has not considered the implications of modern Internet users owning multiple mobile devices that exhibit correlated mobility patterns. Also, prior work has analyzed mobility at the spatial scale of the underlying mobile dataset and has not analyzed mobility characteristics at different spatial scales and its implications on system design. In this paper, we empirically analyze the mobility of modern Internet users owning multiple devices at multiple spatial scales using a large campus WiFi dataset. First, our results show that mobility of multiple devices belonging to a user needs to be analyzed and modeled as a group, rather than independently, and that there are substantial differences in the correlations exhibited by device trajectories across users that also need to be considered. Second, our analysis shows that the mobility of users shows different characteristics at different spatial scales such as within and across buildings. Third, we demonstrate the implications of these results by presenting generative models that highlight the importance of considering the spatial scale of mobility as well as multi-device mobility. More broadly, our empirical results point to the need for new modeling research to fully capture the nuances of mobility of modern multi-device users.
Evaluating Salient Object Detection in Natural Images with Multiple Objects having Multi-level Saliency
Venue: arXiv cs.CV 2020
Year: 2020

Salient object detection is evaluated using binary ground truth with the labels being salient object class and background. In this paper, we corroborate based on three subjective experiments on a novel image dataset that objects in natural images are inherently perceived to have varying levels of importance. Our dataset, named SalMoN (saliency in multi-object natural images), has 588 images containing multiple objects. The subjective experiments performed record spontaneous attention and perception through eye fixation duration, point clicking and rectangle drawing. As object saliency in a multi-object image is inherently multi-level, we propose that salient object detection must be evaluated for the capability to detect all multi-level salient objects apart from the salient object class detection capability. For this purpose, we generate multi-level maps as ground truth corresponding to all the dataset images using the results of the subjective experiments, with the labels being multi-level salient objects and background. We then propose the use of mean absolute error, Kendall's rank correlation and average area under precision-recall curve to evaluate existing salient object detection methods on our multi-level saliency ground truth dataset. Approaches that represent saliency detection on images as local-global hierarchical processing of a graph perform well in our dataset.
Provably Constant-time Planning and Replanning for Real-time Grasping Objects off a Conveyor Belt
Venue: arXiv cs.RO 2020
Year: 2020

In warehouse and manufacturing environments, manipulation platforms are frequently deployed at conveyor belts to perform pick and place tasks. Because objects on the conveyor belts are moving, robots have limited time to pick them up. This brings the requirement for fast and reliable motion planners that could provide provable real-time planning guarantees, which the existing algorithms do not provide. Besides the planning efficiency, the success of manipulation tasks relies heavily on the accuracy of the perception system which is often noisy, especially if the target objects are perceived from a distance. For fast moving conveyor belts, the robot cannot wait for a perfect estimate before it starts executing its motion. In order to be able to reach the object in time it must start moving early on (relying on the initial noisy estimates) and adjust its motion on-the-fly in response to the pose updates from perception. We propose an approach that meets these requirements by providing provable constant-time planning and replanning guarantees. We present it, give its analytical properties and show experimental analysis in simulation and on a real robot.
Adjust Planning Strategies to Accommodate Reinforcement Learning Agents
Venue: arXiv cs.AI 2020
Year: 2020

In agent control issues, the idea of combining reinforcement learning and planning has attracted much attention. Two methods focus on micro and macro action respectively. Their advantages would show together if there is a good cooperation between them. An essential for the cooperation is to find an appropriate boundary, assigning different functions to each method. Such boundary could be represented by parameters in a planning algorithm. In this paper, we create an optimization strategy for planning parameters, through analysis to the connection of reaction and planning; we also create a non-gradient method for accelerating the optimization. The whole algorithm can find a satisfactory setting of planning parameters, making full use of reaction capability of specific agents.
Convolutional Neural Networks for Continuous QoE Prediction in Video Streaming Services
Venue: arXiv cs.MM 2020
Year: 2020

In video streaming services, predicting the continuous user's quality of experience (QoE) plays a crucial role in delivering high quality streaming contents to the user. However, the complexity caused by the temporal dependencies in QoE data and the non-linear relationships among QoE influence factors has introduced challenges to continuous QoE prediction. To deal with that, existing studies have utilized the Long Short-Term Memory model (LSTM) to effectively capture such complex dependencies, resulting in excellent QoE prediction accuracy. However, the high computational complexity of LSTM, caused by the sequential processing characteristic in its architecture, raises a serious question about its performance on devices with limited computational power. Meanwhile, Temporal Convolutional Network (TCN), a variation of convolutional neural networks, has recently been proposed for sequence modeling tasks (e.g., speech enhancement), providing a superior prediction performance over baseline methods including LSTM in terms of prediction accuracy and computational complexity. Being inspired of that, in this paper, an improved TCN-based model, namely CNN-QoE, is proposed for continuously predicting the QoE, which poses characteristics of sequential data. The proposed model leverages the advantages of TCN to overcome the computational complexity drawbacks of LSTM-based QoE models, while at the same time introducing the improvements to its architecture to improve QoE prediction accuracy. Based on a comprehensive evaluation, we demonstrate that the proposed CNN-QoE model can reach the state-of-the-art performance on both personal computers and mobile devices, outperforming the existing approaches.
Train Scheduling with Hybrid Answer Set Programming
Venue: arXiv cs.AI 2020
Year: 2020

We present a solution to real-world train scheduling problems, involving routing, scheduling, and optimization, based on Answer Set Programming (ASP). To this end, we pursue a hybrid approach that extends ASP with difference constraints to account for a fine-grained timing. More precisely, we exemplarily show how the hybrid ASP system clingo[DL] can be used to tackle demanding planning-and-scheduling problems. In particular, we investigate how to boost performance by combining distinct ASP solving techniques, such as approximations and heuristics, with preprocessing and encoding techniques for tackling large-scale, real-world train scheduling instances. Under consideration in Theory and Practice of Logic Programming (TPLP)
Unsupervised deep learning for text line segmentation
Venue: arXiv cs.CV 2020
Year: 2020

We present an unsupervised deep learning method for text line segmentation that is inspired by the relative variance between text lines and spaces among text lines. Handwritten text line segmentation is important for the efficiency of further processing. A common method is to train a deep learning network for embedding the document image into an image of blob lines that are tracing the text lines. Previous methods learned such embedding in a supervised manner, requiring the annotation of many document images. This paper presents an unsupervised embedding of document image patches without a need for annotations. The number of foreground pixels over the text lines is relatively different from the number of foreground pixels over the spaces among text lines. Generating similar and different pairs relying on this principle definitely leads to outliers. However, as the results show, the outliers do not harm the convergence and the network learns to discriminate the text lines from the spaces between text lines. Remarkably, with a challenging Arabic handwritten text line segmentation dataset, VML-AHTE, we achieved superior performance over the supervised methods. Additionally, the proposed method was evaluated on the ICDAR 2017 and ICFHR 2010 handwritten text line segmentation datasets.
A Soft Cancellation Decoder for Parity-Check Polar Codes
Venue: arXiv cs.IT 2020
Year: 2020

Polar codes has been selected as the channel coding scheme for 5G new radio (NR) control channel. Specifically, a special type of parity-check polar (PC-Polar) codes was adopted in uplink control information (UCI). In this paper, we propose a parity-check soft-cancellation (PC-SCAN) algorithm and its simplified version to decode PC-Polar codes. The potential benefits are two-fold. First, PC-SCAN can provide soft output for PC-Polar codes, which is essential for advanced turbo receivers. Second, the decoding performance is better than that of successive cancellation (SC). This is due to the fact that parity-check constraints can be exploited by PC-SCAN to enhance the reliability of other information bits over the iterations. Moreover, we describe a cyclic-shift-register (CSR) based implementation "CSR-SCAN" to reduce both hardware cost and latency with minimum performance loss.
LoRa in the Field: Insights from Networking the Smart City Hamburg with RIOT
Venue: arXiv cs.NI 2020
Year: 2020

Inter-connected sensors and actuators have scaled down to small embedded devices such as wearables, and at the same time meet a massive deployment at the Internet edge: the Internet of Things (IoT). Many of these IoT devices run on low-power batteries and are forced to operate on very constrained resources, namely slow CPUs, tiny memories, and low-power radios. Establishing a network infrastructure that is energy efficient, wireless, and still covers a wide area is a larger challenge in this regime. LoRa is a low complexity long range radio technology, which tries to meet these challenges.With LoRaWAN a network model for widespread deployment has been established, which enjoys open public LoRaWAN dissemination such as with the infrastructure of TheThingsNetwork. In this paper, we report about our experiences with developing and deploying LoRa-based smart city applications as part of the MONICA project in Hamburg. Our contributions are twofold. First, we describe the design and implementation of end-to-end IoT applications based on the friendly IoT operating system RIOT. Second, we report on measurements and evaluations of our large field trials during several public events in the city of Hamburg. Our results show that LoRaWAN provides a suitable communication layer for a variety of Smart City use-cases and IoT applications, but also identifies its limitations and weaknesses.
IROF: a low resource evaluation metric for explanation methods
Venue: arXiv cs.CV 2020
Year: 2020

The adoption of machine learning in health care hinges on the transparency of the used algorithms, necessitating the need for explanation methods. However, despite a growing literature on explaining neural networks, no consensus has been reached on how to evaluate those explanation methods. We propose IROF, a new approach to evaluating explanation methods that circumvents the need for manual evaluation. Compared to other recent work, our approach requires several orders of magnitude less computational resources and no human input, making it accessible to lower resource groups and robust to human bias.
Dense Crowds Detection and Surveillance with Drones using Density Maps
Venue: arXiv cs.CV 2020
Year: 2020

Detecting and Counting people in a human crowd from a moving drone present challenging problems that arisefrom the constant changing in the image perspective andcamera angle. In this paper, we test two different state-of-the-art approaches, density map generation with VGG19 trainedwith the Bayes loss function and detect-then-count with FasterRCNN with ResNet50-FPN as backbone, in order to comparetheir precision for counting and detecting people in differentreal scenarios taken from a drone flight. We show empiricallythat both proposed methodologies perform especially well fordetecting and counting people in sparse crowds when thedrone is near the ground. Nevertheless, VGG19 provides betterprecision on both tasks while also being lighter than FasterRCNN. Furthermore, VGG19 outperforms Faster RCNN whendealing with dense crowds, proving to be more robust toscale variations and strong occlusions, being more suitable forsurveillance applications using drones