OpenRaiser/Intern-Atlas huggingface dataset:
Saliency Enhancement using Gradient Domain Edges Merging
Venue: arXiv cs.CV 2020
Year: 2020

In recent years, there has been a rapid progress in solving the binary problems in computer vision, such as edge detection which finds the boundaries of an image and salient object detection which finds the important object in an image. This progress happened thanks to the rise of deep-learning and convolutional neural networks (CNN) which allow to extract complex and abstract features. However, edge detection and saliency are still two different fields and do not interact together, although it is intuitive for a human to detect salient objects based on its boundaries. Those features are not well merged in a CNN because edges and surfaces do not intersect since one feature represents a region while the other represents boundaries between different regions. In the current work, the main objective is to develop a method to merge the edges with the saliency maps to improve the performance of the saliency. Hence, we developed the gradient-domain merging (GDM) which can be used to quickly combine the image-domain information of salient object detection with the gradient-domain information of the edge detection. This leads to our proposed saliency enhancement using edges (SEE) with an average improvement of the F-measure of at least 3.4 times higher on the DUT-OMRON dataset and 6.6 times higher on the ECSSD dataset, when compared to competing algorithm such as denseCRF and BGOF. The SEE algorithm is split into 2 parts, SEE-Pre for preprocessing and SEE-Post pour postprocessing.
A new generalization of edge overlap to weighted networks
Venue: arXiv cs.SI 2020
Year: 2020

Finding the strength of an edge in a network has always been a big demand. In the context of social networks, it allows to estimate the relationship strength between users. The best-known method to compute edge strength is the Neighbourhood Overlap. It computes the ratio of common neighbours to all neighbours of an edge terminal nodes. This method has been initially proposed for unweighted networks and later extended for weighted ones. These two versions of the method are not mathematically equivalent: In fact, an unweighted network is commonly considered as weighted with all edge weights equal to one. Using both existent versions of Neighbourhood Overlap on such network produce completely different values. In this paper, we tackle this problem and propose a new generalization for Neighbourhood Overlap that works equally for unweighted and weighted networks. Experiment performed on networks with various parameters showed similar performance of our measure to the existing measures.
pymoo: Multi-objective Optimization in Python
Venue: arXiv cs.NE 2020
Year: 2020

Python has become the programming language of choice for research and industry projects related to data science, machine learning, and deep learning. Since optimization is an inherent part of these research fields, more optimization related frameworks have arisen in the past few years. Only a few of them support optimization of multiple conflicting objectives at a time, but do not provide comprehensive tools for a complete multi-objective optimization task. To address this issue, we have developed pymoo, a multi-objective optimization framework in Python. We provide a guide to getting started with our framework by demonstrating the implementation of an exemplary constrained multi-objective optimization scenario. Moreover, we give a high-level overview of the architecture of pymoo to show its capabilities followed by an explanation of each module and its corresponding sub-modules. The implementations in our framework are customizable and algorithms can be modified/extended by supplying custom operators. Moreover, a variety of single, multi and many-objective test problems are provided and gradients can be retrieved by automatic differentiation out of the box. Also, pymoo addresses practical needs, such as the parallelization of function evaluations, methods to visualize low and high-dimensional spaces, and tools for multi-criteria decision making. For more information about pymoo, readers are encouraged to visit: https://pymoo.org
An Optimal Algorithm for Online Multiple Knapsack
Venue: arXiv cs.DS 2020
Year: 2020

In the online multiple knapsack problem, an algorithm faces a stream of items, and each item has to be either rejected or stored irrevocably in one of $n$ bins (knapsacks) of equal size. The gain of an~algorithm is equal to the sum of sizes of accepted items and the goal is to maximize the total gain. So far, for this natural problem, the best solution was the $0.5$-competitive algorithm First Fit (the result holds for any $n \geq 2$). We present the first algorithm that beats this ratio, achieving the competitive ratio of $1/(1+\ln(2))-O(1/n) \approx 0.5906 - O(1/n)$. Our algorithm is deterministic and optimal up to lower-order terms, as the upper bound of $1/(1+\ln(2))$ for randomized solutions was given previously by Cygan et al. [TOCS 2016]. Furthermore, we show that the lower-order term is inevitable for deterministic algorithms, by improving their upper bound to $1/(1+\ln(2))-O(1/n)$.
A Survey On 3D Inner Structure Prediction from its Outer Shape
Venue: arXiv cs.CV 2020
Year: 2020

The analysis of the internal structure of trees is highly important for both forest experts, biological scientists, and the wood industry. Traditionally, CT-scanners are considered as the most efficient way to get an accurate inner representation of the tree. However, this method requires an important investment and reduces the cost-effectiveness of this operation. Our goal is to design neural-network-based methods to predict the internal density of the tree from its external bark shape. This paper compares different image-to-image(2D), volume-to-volume(3D) and Convolutional Long Short Term Memory based neural network architectures in the context of the prediction of the defect distribution inside trees from their external bark shape. Those models are trained on a synthetic dataset of 1800 CT-scanned look-like volumetric structures of the internal density of the trees and their corresponding external surface.
Back to Futures
Venue: arXiv cs.PL 2020
Year: 2020

Common approaches to concurrent programming begin with languages whose semantics are naturally sequential and add new constructs that provide limited access to concurrency, as exemplified by futures. This approach has been quite successful, but often does not provide a satisfactory theoretical backing for the concurrency constructs, and it can be difficult to give a good semantics that allows a programmer to use more than one of these constructs at a time. We take a different approach, starting with a concurrent language based on a Curry-Howard interpretation of adjoint logic, to which we add three atomic primitives that allow us to encode sequential composition and various forms of synchronization. The resulting language is highly expressive, allowing us to encode futures, fork/join parallelism, and monadic concurrency in the same framework. Notably, since our language is based on adjoint logic, we are able to give a formal account of linear futures, which have been used in complexity analysis by Blelloch and Reid-Miller. The uniformity of this approach means that we can similarly work with many of the other concurrency primitives in a linear fashion, and that we can mix several of these forms of concurrency in the same program to serve different purposes.
Information Freshness for Timely Detection of Status Changes
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we aim to establish the connection between Age of Information (AoI) in network theory, information uncertainty in information theory, and detection delay in time series analysis. We consider a dynamic system whose state changes at discrete time points, and a state change won't be detected until an update generated after the change point is delivered to the destination for the first time. We introduce an information theoretic metric to measure the information freshness at the destination, and name it as generalized Age of Information (GAoI). We show that under any state-independent online updating policy, if the underlying state of the system evolves according to a stationary Markov chain, the GAoI is proportional to the AoI. Besides, the accumulative GAoI and AoI are proportional to the expected accumulative detection delay of all changes points over a period of time. Thus, any (G)AoI-optimal state-independent updating policy equivalently minimizes the corresponding expected change point detection delay, which validates the fundamental role of (G)AoI in real-time status monitoring. Besides, we also investigate a Bayesian change point detection scenario where the underlying state evolution is not stationary. Although AoI is no longer related to detection delay explicitly, we show that the accumulative GAoI is still an affine function of the expected detection delay, which indicates the versatility of GAoI in capturing information freshness in dynamic systems.
fastai: A Layered API for Deep Learning
Venue: arXiv cs.LG 2020
Year: 2020

fastai is a deep learning library which provides practitioners with high-level components that can quickly and easily provide state-of-the-art results in standard deep learning domains, and provides researchers with low-level components that can be mixed and matched to build new approaches. It aims to do both things without substantial compromises in ease of use, flexibility, or performance. This is possible thanks to a carefully layered architecture, which expresses common underlying patterns of many deep learning and data processing techniques in terms of decoupled abstractions. These abstractions can be expressed concisely and clearly by leveraging the dynamism of the underlying Python language and the flexibility of the PyTorch library. fastai includes: a new type dispatch system for Python along with a semantic type hierarchy for tensors; a GPU-optimized computer vision library which can be extended in pure Python; an optimizer which refactors out the common functionality of modern optimizers into two basic pieces, allowing optimization algorithms to be implemented in 4-5 lines of code; a novel 2-way callback system that can access any part of the data, model, or optimizer and change it at any point during training; a new data block API; and much more. We have used this library to successfully create a complete deep learning course, which we were able to write more quickly than using previous approaches, and the code was more clear. The library is already in wide use in research, industry, and teaching. NB: This paper covers fastai v2, which is currently in pre-release at http://dev.fast.ai/
Two Huge Title and Keyword Generation Corpora of Research Articles
Venue: arXiv cs.CL 2020
Year: 2020

Recent developments in sequence-to-sequence learning with neural networks have considerably improved the quality of automatically generated text summaries and document keywords, stipulating the need for even bigger training corpora. Metadata of research articles are usually easy to find online and can be used to perform research on various tasks. In this paper, we introduce two huge datasets for text summarization (OAGSX) and keyword generation (OAGKX) research, containing 34 million and 23 million records, respectively. The data were retrieved from the Open Academic Graph which is a network of research profiles and publications. We carefully processed each record and also tried several extractive and abstractive methods of both tasks to create performance baselines for other researchers. We further illustrate the performance of those methods previewing their outputs. In the near future, we would like to apply topic modeling on the two sets to derive subsets of research articles from more specific disciplines.
A Single RGB Camera Based Gait Analysis with a Mobile Tele-Robot for Healthcare
Venue: arXiv cs.RO 2020
Year: 2020

With the increasing awareness of high-quality life, there is a growing need for health monitoring devices running robust algorithms in home environment. Health monitoring technologies enable real-time analysis of users' health status, offering long-term healthcare support and reducing hospitalization time. The purpose of this work is twofold, the software focuses on the analysis of gait, which is widely adopted for joint correction and assessing any lower limb or spinal problem. On the hardware side, we design a novel marker-less gait analysis device using a low-cost RGB camera mounted on a mobile tele-robot. As gait analysis with a single camera is much more challenging compared to previous works utilizing multi-cameras, a RGB-D camera or wearable sensors, we propose using vision-based human pose estimation approaches. More specifically, based on the output of two state-of-the-art human pose estimation models (Openpose and VNect), we devise measurements for four bespoke gait parameters: inversion/eversion, dorsiflexion/plantarflexion, ankle and foot progression angles. We thereby classify walking patterns into normal, supination, pronation and limp. We also illustrate how to run the purposed machine learning models in low-resource environments such as a single entry-level CPU. Experiments show that our single RGB camera method achieves competitive performance compared to state-of-the-art methods based on depth cameras or multi-camera motion capture system, at smaller hardware costs.
Superbloom: Bloom filter meets Transformer
Venue: arXiv cs.LG 2020
Year: 2020

We extend the idea of word pieces in natural language models to machine learning tasks on opaque ids. This is achieved by applying hash functions to map each id to multiple hash tokens in a much smaller space, similarly to a Bloom filter. We show that by applying a multi-layer Transformer to these Bloom filter digests, we are able to obtain models with high accuracy. They outperform models of a similar size without hashing and, to a large degree, models of a much larger size trained using sampled softmax with the same computational budget. Our key observation is that it is important to use a multi-layer Transformer for Bloom filter digests to remove ambiguity in the hashed input. We believe this provides an alternative method to solving problems with large vocabulary size.
ZipPhone: Protecting user location privacy from cellular service providers
Venue: arXiv cs.NI 2020
Year: 2020

Wireless service providers track the time and location of all user connections. Location inference attacks have been effective in revealing the identity of anonymous users of wireless services. In this paper, we propose ZipPhone, a solution that leverages existing cellular infrastructure to improve user privacy. Spartacus allows a community of users to strategically time their connections to remain anonymous while incurring a minimal loss of utility. We evaluate ZipPhone from the perspective of a cell service provider and a community of privacy-seeking users, and quantify the privacy/utility trade-off of ZipPhone using two datasets containing cell tower logs of hundreds of users. We present and assess a deanonymization algorithm that uses both location profiling and trajectory linking. We find that by renewing identifiers every ten minutes and remaining offline for 30 seconds, users can reduce their identifiability by up to 45%.
Efficient Training of Deep Convolutional Neural Networks by Augmentation in Embedding Space
Venue: arXiv cs.CV 2020
Year: 2020

Recent advances in the field of artificial intelligence have been made possible by deep neural networks. In applications where data are scarce, transfer learning and data augmentation techniques are commonly used to improve the generalization of deep learning models. However, fine-tuning a transfer model with data augmentation in the raw input space has a high computational cost to run the full network for every augmented input. This is particularly critical when large models are implemented on embedded devices with limited computational and energy resources. In this work, we propose a method that replaces the augmentation in the raw input space with an approximate one that acts purely in the embedding space. Our experimental results show that the proposed method drastically reduces the computation, while the accuracy of models is negligibly compromised.
Genomic Problems Involving Copy Number Profiles: Complexity and Algorithms
Venue: arXiv cs.DS 2020
Year: 2020

Recently, due to the genomic sequence analysis in several types of cancer, the genomic data based on {\em copy number profiles} ({\em CNP} for short) are getting more and more popular. A CNP is a vector where each component is a non-negative integer representing the number of copies of a specific gene or segment of interest. In this paper, we present two streams of results. The first is the negative results on two open problems regarding the computational complexity of the Minimum Copy Number Generation (MCNG) problem posed by Qingge et al. in 2018. It was shown by Qingge et al. that the problem is NP-hard if the duplications are tandem and they left the open question of whether the problem remains NP-hard if arbitrary duplications are used. We answer this question affirmatively in this paper; in fact, we prove that it is NP-hard to even obtain a constant factor approximation. We also prove that the parameterized version is W[1]-hard, answering another open question by Qingge et al. The other result is positive and is based on a new (and more general) problem regarding CNP's. The \emph{Copy Number Profile Conforming (CNPC)} problem is formally defined as follows: given two CNP's $C_1$ and $C_2$, compute two strings $S_1$ and $S_2$ with $cnp(S_1)=C_1$ and $cnp(S_2)=C_2$ such that the distance between $S_1$ and $S_2$, $d(S_1,S_2)$, is minimized. Here, $d(S_1,S_2)$ is a very general term, which means it could be any genome rearrangement distance (like reversal, transposition, and tandem duplication, etc). We make the first step by showing that if $d(S_1,S_2)$ is measured by the breakpoint distance then the problem is polynomially solvable.
Deep Multi-Task Learning via Generalized Tensor Trace Norm
Venue: arXiv cs.LG 2020
Year: 2020

The trace norm is widely used in multi-task learning as it can discover low-rank structures among tasks in terms of model parameters. Nowadays, with the emerging of big datasets and the popularity of deep learning techniques, tensor trace norms have been used for deep multi-task models. However, existing tensor trace norms cannot discover all the low-rank structures and they require users to manually determine the importance of their components. To solve those two issues together, in this paper, we propose a Generalized Tensor Trace Norm (GTTN). The GTTN is defined as a convex combination of matrix trace norms of all possible tensor flattenings and hence it can discover all the possible low-rank structures. In the induced objective function, we will learn combination coefficients in the GTTN to automatically determine the importance. Experiments on real-world datasets demonstrate the effectiveness of the proposed GTTN.
Compressed Coding, AMP Based Decoding and Analog Spatial Coupling
Venue: arXiv cs.IT 2020
Year: 2020

This paper considers a compressed-coding scheme that combines compressed sensing with forward error control coding. Approximate message passing (AMP) is used to decode the message. Based on the state evolution analysis of AMP, we derive the performance limit of compressed-coding. We show that compressed-coding can approach Gaussian capacity at a very low compression ratio. Further, the results are extended to systems involving non-linear effects such as clipping. We show that the capacity approaching property can still be maintained when generalized AMP is used to decode the message. To approach the capacity, a low-rate underlying code should be designed according to the curve matching principle, which is complicated in practice. Instead, analog spatial-coupling is used to avoid sophisticated low-rate code design. In the end, we study the coupled scheme in a multiuser environment, where spatial-coupling can be realized in a distributive way. The overall block length can be shared by many users, which reduces block length per-user.
Computation Resource Allocation for Heterogeneous Time-Critical IoT Services in MEC
Venue: arXiv cs.NI 2020
Year: 2020

Mobile edge computing (MEC) is one of the promising solutions to process computational-intensive tasks within short latency for emerging Internet-of-Things (IoT) use cases, e.g., virtual reality (VR), augmented reality (AR), autonomous vehicle. Due to the coexistence of heterogeneous services in MEC system, the task arrival interval and required execution time can vary depending on services. It is challenging to schedule computation resource for the services with stochastic arrivals and runtime at an edge server (ES). In this paper, we propose a flexible computation offloading framework among users and ESs. Based on the framework, we propose a Lyapunov-based algorithm to dynamically allocate computation resource for heterogeneous time-critical services at the ES. The proposed algorithm minimizes the average timeout probability without any prior knowledge on task arrival process and required runtime. The numerical results show that, compared with the standard queuing models used at ES, the proposed algorithm achieves at least 35% reduction of the timeout probability, and approximated utilization efficiency of computation resource to non-cause queuing model under various scenarios.
Energy Efficiency Optimization for Downlink Massive MIMO With Statistical CSIT
Venue: arXiv cs.IT 2020
Year: 2020

We investigate energy efficiency (EE) optimization for single-cell massive multiple-input multiple-output (MIMO) downlink transmission with only statistical channel state information (CSI) available at the base station. We first show that beam domain transmission is favorable for energy efficiency in the massive MIMO downlink, by deriving a closed-form solution for the eigenvectors of the optimal transmit covariance matrix. With this conclusion, the EE optimization problem is reduced to a real-valued power allocation problem, which is much easier to tackle than the original large-dimensional complex matrix-valued precoding design problem. We further propose an iterative water-filling-structured beam domain power allocation algorithm with low complexity and guaranteed convergence, exploiting the techniques from sequential optimization, fractional optimization, and random matrix theory. Numerical results demonstrate the near-optimal performance of our proposed statistical CSI aided EE optimization approach.