OpenRaiser/Intern-Atlas huggingface dataset:
Polynomial Time Algorithms for Constructing Optimal Binary AIFV-$2$ Codes
Venue: arXiv cs.IT 2020
Year: 2020

Huffman Codes are optimal Instantaneous Fixed-to-Variable (FV) codes in which every source symbol can only be encoded by one codeword. Relaxing these constraints permits constructing better FV codes. More specifically, recent work has shown that AIFV-$m$ codes can beat Huffman coding. AIFV-$m$ codes construct am $m$-tuple of different coding trees between which the code alternates and are only almost instantaneous (AI). This means that decoding a word might require a delay of a finite number of bits. Current algorithms for constructing optimal AIFV-$m$ codes are iterative processes that construct progressively "better sets" of code trees. The processes have been proven to finitely converge to the optimal code but with no known bounds on the convergence rate. This paper derives a geometric interpretation of the space of binary AIFV-$2$ codes, permitting the development of the first polynomially time-bounded iterative procedures for constructing optimal AIFV codes. We first show that a simple binary search procedure can replace the current iterative process to construct optimal binary AIFV-$2$ codes. We then describe how to frame the problem as a linear programming with an exponential number of constraints but a polynomial-time separability oracle. This permits using the Grötschel, Lovász and Schrijver ellipsoid method to solve the problem in a polynomial number of steps. While more complicated, this second method has the potential to lead to a polynomial time algorithm to construct optimal AIFV-$m$ codes for general $m$.
Model-free vision-based shaping of deformable plastic materials
Venue: arXiv cs.RO 2020
Year: 2020

We address the problem of shaping deformable plastic materials using non-prehensile actions. Shaping plastic objects is challenging, since they are difficult to model and to track visually. We study this problem, by using kinetic sand, a plastic toy material which mimics the physical properties of wet sand. Inspired by a pilot study where humans shape kinetic sand, we define two types of actions: \textit{pushing} the material from the sides and \textit{tapping} from above. The chosen actions are executed with a robotic arm using image-based visual servoing. From the current and desired view of the material, we define states based on visual features such as the outer contour shape and the pixel luminosity values. These are mapped to actions, which are repeated iteratively to reduce the image error until convergence is reached. For pushing, we propose three methods for mapping the visual state to an action. These include heuristic methods and a neural network, trained from human actions. We show that it is possible to obtain simple shapes with the kinetic sand, without explicitly modeling the material. Our approach is limited in the types of shapes it can achieve. A richer set of action types and multi-step reasoning is needed to achieve more sophisticated shapes.
Image Embedded Segmentation: Uniting Supervised and Unsupervised Objectives for Segmenting Histopathological Images
Venue: arXiv cs.CV 2020
Year: 2020

This paper presents a new regularization method to train a fully convolutional network for semantic tissue segmentation in histopathological images. This method relies on the benefit of unsupervised learning, in the form of image reconstruction, for network training. To this end, it puts forward an idea of defining a new embedding that allows uniting the main supervised task of semantic segmentation and an auxiliary unsupervised task of image reconstruction into a single one and proposes to learn this united task by a single generative model. This embedding generates an output image by superimposing an input image on its segmentation map. Then, the method learns to translate the input image to this embedded output image using a conditional generative adversarial network, which is known as quite effective for image-to-image translations. This proposal is different than the existing approach that uses image reconstruction for the same regularization purpose. The existing approach considers segmentation and image reconstruction as two separate tasks in a multi-task network, defines their losses independently, and combines them in a joint loss function. However, the definition of such a function requires externally determining right contributions of the supervised and unsupervised losses that yield balanced learning between the segmentation and image reconstruction tasks. The proposed approach provides an easier solution to this problem by uniting these two tasks into a single one, which intrinsically combines their losses. We test our approach on three datasets of histopathological images. Our experiments demonstrate that it leads to better segmentation results in these datasets, compared to its counterparts.
Weakly Supervised Instance Segmentation by Deep Community Learning
Venue: arXiv cs.CV 2020
Year: 2020

We present a weakly supervised instance segmentation algorithm based on deep community learning with multiple tasks. This task is formulated as a combination of weakly supervised object detection and semantic segmentation, where individual objects of the same class are identified and segmented separately. We address this problem by designing a unified deep neural network architecture, which has a positive feedback loop of object detection with bounding box regression, instance mask generation, instance segmentation, and feature extraction. Each component of the network makes active interactions with others to improve accuracy, and the end-to-end trainability of our model makes our results more robust and reproducible. The proposed algorithm achieves state-of-the-art performance in the weakly supervised setting without any additional training such as Fast R-CNN and Mask R-CNN on the standard benchmark dataset. The implementation of our algorithm is available on the project webpage: https://cv.snu.ac.kr/research/WSIS_CL.
An Automated Framework for the Extraction of Semantic Legal Metadata from Legal Texts
Venue: arXiv cs.SE 2020
Year: 2020

Semantic legal metadata provides information that helps with understanding and interpreting legal provisions. Such metadata is therefore important for the systematic analysis of legal requirements. However, manually enhancing a large legal corpus with semantic metadata is prohibitively expensive. Our work is motivated by two observations: (1) the existing requirements engineering (RE) literature does not provide a harmonized view on the semantic metadata types that are useful for legal requirements analysis; (2) automated support for the extraction of semantic legal metadata is scarce, and it does not exploit the full potential of artificial intelligence technologies, notably natural language processing (NLP) and machine learning (ML). Our objective is to take steps toward overcoming these limitations. To do so, we review and reconcile the semantic legal metadata types proposed in the RE literature. Subsequently, we devise an automated extraction approach for the identified metadata types using NLP and ML. We evaluate our approach through two case studies over the Luxembourgish legislation. Our results indicate a high accuracy in the generation of metadata annotations. In particular, in the two case studies, we were able to obtain precision scores of 97.2% and 82.4% and recall scores of 94.9% and 92.4%.
RTM: Blockchain That Support Revocable Transaction Model
Venue: arXiv cs.CR 2020
Year: 2020

In many typical application scenarios, it is necessary to revoke the incorrect account operations caused by user mis-operation, financial fraud, illegal hacking, etc. Unfortunately, users often blur the lines between the concept of "transaction state revocable" and "business status revocable", which result in revocable transaction not universally supported in blockchain systems at present. In this work, we propose GateChain , a blockchain that support revocable transaction model (RTM) on distributed ledger. Specifically, based on the state-of-the-art blockchain technologies, GateChain can safely withdraw the account status change operations by leveraging an improved account model and extra designed transaction types. On that basis, GateChain exploit the characteristics of functional completeness, easy to deployment and lower complexity.
The Hidden Subgroup Problem for Universal Algebras
Venue: arXiv cs.LO 2020
Year: 2020

The Hidden Subgroup Problem (HSP) is a computational problem which includes as special cases integer factorization, the discrete logarithm problem, graph isomorphism, and the shortest vector problem. The celebrated polynomial-time quantum algorithms for factorization and the discrete logarithm are restricted versions of a generic polynomial-time quantum solution to the HSP for abelian groups, but despite focused research no full solution has yet been found. We propose a generalization of the HSP to include arbitrary algebraic structures and analyze this new problem on powers of 2-element algebras. We prove a complete classification of every such power as quantum tractable (i.e. polynomial-time), classically tractable, quantum intractable, and classically intractable. In particular, we identify a class of algebras for which the generalized HSP exhibits super-polynomial speedup on a quantum computer compared to a classical one.
A Deeper Look into Hybrid Images
Venue: arXiv cs.CV 2020
Year: 2020

$Hybrid$ $images$ was first introduced by Olivia et al., that produced static images with two interpretations such that the images changes as a function of viewing distance. Hybrid images are built by studying human processing of multiscale images and are motivated by masking studies in visual perception. The first introduction of hybrid images showed that two images can be blend together with a high pass filter and a low pass filter in such a way that when the blended image is viewed from a distance, the high pass filter fades away and the low pass filter becomes prominent. Our main aim here is to study and review the original paper by changing and tweaking certain parameters to see how they affect the quality of the blended image produced. We have used exhaustively different set of images and filters to see how they function and whether this can be used in a real time system or not.
ERA: A Dataset and Deep Learning Benchmark for Event Recognition in Aerial Videos
Venue: arXiv cs.CV 2020
Year: 2020

Along with the increasing use of unmanned aerial vehicles (UAVs), large volumes of aerial videos have been produced. It is unrealistic for humans to screen such big data and understand their contents. Hence methodological research on the automatic understanding of UAV videos is of paramount importance. In this paper, we introduce a novel problem of event recognition in unconstrained aerial videos in the remote sensing community and present a large-scale, human-annotated dataset, named ERA (Event Recognition in Aerial videos), consisting of 2,864 videos each with a label from 25 different classes corresponding to an event unfolding 5 seconds. The ERA dataset is designed to have a significant intra-class variation and inter-class similarity and captures dynamic events in various circumstances and at dramatically various scales. Moreover, to offer a benchmark for this task, we extensively validate existing deep networks. We expect that the ERA dataset will facilitate further progress in automatic aerial video comprehension. The website is https://lcmou.github.io/ERA_Dataset/
Parameter Space Factorization for Zero-Shot Learning across Tasks and Languages
Venue: arXiv cs.CL 2020
Year: 2020

Most combinations of NLP tasks and language varieties lack in-domain examples for supervised training because of the paucity of annotated data. How can neural models make sample-efficient generalizations from task-language combinations with available data to low-resource ones? In this work, we propose a Bayesian generative model for the space of neural parameters. We assume that this space can be factorized into latent variables for each language and each task. We infer the posteriors over such latent variables based on data from seen task-language combinations through variational inference. This enables zero-shot classification on unseen combinations at prediction time. For instance, given training data for named entity recognition (NER) in Vietnamese and for part-of-speech (POS) tagging in Wolof, our model can perform accurate predictions for NER in Wolof. In particular, we experiment with a typologically diverse sample of 33 languages from 4 continents and 11 families, and show that our model yields comparable or better results than state-of-the-art, zero-shot cross-lingual transfer methods. Moreover, we demonstrate that approximate Bayesian model averaging results in smoother predictive distributions, whose entropy inversely correlates with accuracy. Hence, the proposed framework also offers robust estimates of prediction uncertainty. Our code is located at github.com/cambridgeltl/parameter-factorization
Peregrine: Network Localization and Navigation with Scalable Inference and Efficient Operation
Venue: arXiv cs.IT 2020
Year: 2020

Location-aware networks will enable new services and applications in fields such as autonomous driving, smart cities, and the Internet-of-Things. One promising solution for ubiquitous localization is network localization and navigation (NLN), where devices form a network that cooperatively localizes itself, reducing the infrastructure needed for accurate localization. This paper introduces a real-time NLN system named Peregrine, which combines distributed NLN algorithms with commercially available ultra-wideband (UWB) sensing and communication technology. The Peregrine software application, for the first time, integrates three NLN algorithms to jointly perform the tasks of localization and network operation in a technology agnostic manner, leveraging both spatial and temporal cooperation. Peregrine hardware is composed of low-cost, compact devices that comprise a microprocessor and a commercial UWB radio. This paper presents the design of the Peregrine system and characterizes the performance impact of each algorithmic component. Indoor experiments validate that our approach to realizing NLN is both reliable and scalable, and maintains sub-meter-level accuracy even in challenging indoor scenarios.
Who Should Google Scholar Update More Often?
Venue: arXiv cs.IT 2020
Year: 2020

We consider a resource-constrained updater, such as Google Scholar, which wishes to update the citation records of a group of researchers, who have different mean citation rates (and optionally, different importance coefficients), in such a way to keep the overall citation index as up to date as possible. The updater is resource-constrained and cannot update citations of all researchers all the time. In particular, it is subject to a total update rate constraint that it needs to distribute among individual researchers. We use a metric similar to the age of information: the long-term average difference between the actual citation numbers and the citation numbers according to the latest updates. We show that, in order to minimize this difference metric, the updater should allocate its total update capacity to researchers proportional to the $square$ $roots$ of their mean citation rates. That is, more prolific researchers should be updated more often, but there are diminishing returns due to the concavity of the square root function. More generally, our paper addresses the problem of optimal operation of a resource-constrained sampler that wishes to track multiple independent counting processes in a way that is as up to date as possible.
Theoretical Model and Practical Considerations for Data Lineage Reconstruction
Venue: arXiv cs.DB 2020
Year: 2020

We live in a world driven by data. The amount of it outgrows anyone's ability to oversee it or even observe its scope. Along with all the advances in the space of data management, there is still a significant lack of formalism and standardization around defining data ecosystems and processes occurring within those. In order to address the issue we propose a notation for data flow modeling and evaluate some of the most common applications of it based on real-world use cases. To facilitate future work, we provide detailed reference of the data model we defined and consider potential programming paradigms.
Adversarial Code Learning for Image Generation
Venue: arXiv cs.CV 2020
Year: 2020

We introduce the "adversarial code learning" (ACL) module that improves overall image generation performance to several types of deep models. Instead of performing a posterior distribution modeling in the pixel spaces of generators, ACLs aim to jointly learn a latent code with another image encoder/inference net, with a prior noise as its input. We conduct the learning in an adversarial learning process, which bears a close resemblance to the original GAN but again shifts the learning from image spaces to prior and latent code spaces. ACL is a portable module that brings up much more flexibility and possibilities in generative model designs. First, it allows flexibility to convert non-generative models like Autoencoders and standard classification models to decent generative models. Second, it enhances existing GANs' performance by generating meaningful codes and images from any part of the prior. We have incorporated our ACL module with the aforementioned frameworks and have performed experiments on synthetic, MNIST, CIFAR-10, and CelebA datasets. Our models have achieved significant improvements which demonstrated the generality for image generation tasks.
Tiny noise, big mistakes: Adversarial perturbations induce errors in Brain-Computer Interface spellers
Venue: arXiv cs.HC 2020
Year: 2020

An electroencephalogram (EEG) based brain-computer interface (BCI) speller allows a user to input text to a computer by thought. It is particularly useful to severely disabled individuals, e.g., amyotrophic lateral sclerosis patients, who have no other effective means of communication with another person or a computer. Most studies so far focused on making EEG-based BCI spellers faster and more reliable; however, few have considered their security. This study, for the first time, shows that P300 and steady-state visual evoked potential BCI spellers are very vulnerable, i.e., they can be severely attacked by adversarial perturbations, which are too tiny to be noticed when added to EEG signals, but can mislead the spellers to spell anything the attacker wants. The consequence could range from merely user frustration to severe misdiagnosis in clinical applications. We hope our research can attract more attention to the security of EEG-based BCI spellers, and more broadly, EEG-based BCIs, which has received little attention before.
Concentration Inequalities for Multinoulli Random Variables
Venue: arXiv cs.LG 2020
Year: 2020

We investigate concentration inequalities for Dirichlet and Multinomial random variables.
C-DLinkNet: considering multi-level semantic features for human parsing
Venue: arXiv cs.CV 2020
Year: 2020

Human parsing is an essential branch of semantic segmentation, which is a fine-grained semantic segmentation task to identify the constituent parts of human. The challenge of human parsing is to extract effective semantic features to resolve deformation and multi-scale variations. In this work, we proposed an end-to-end model called C-DLinkNet based on LinkNet, which contains a new module named Smooth Module to combine the multi-level features in Decoder part. C-DLinkNet is capable of producing competitive parsing performance compared with the state-of-the-art methods with smaller input sizes and no additional information, i.e., achiving mIoU=53.05 on the validation set of LIP dataset.
Pseudo-Bidirectional Decoding for Local Sequence Transduction
Venue: arXiv cs.CL 2020
Year: 2020

Local sequence transduction (LST) tasks are sequence transduction tasks where there exists massive overlapping between the source and target sequences, such as Grammatical Error Correction (GEC) and spell or OCR correction. Previous work generally tackles LST tasks with standard sequence-to-sequence (seq2seq) models that generate output tokens from left to right and suffer from the issue of unbalanced outputs. Motivated by the characteristic of LST tasks, in this paper, we propose a simple but versatile approach named Pseudo-Bidirectional Decoding (PBD) for LST tasks. PBD copies the corresponding representation of source tokens to the decoder as pseudo future context to enable the decoder to attends to its bi-directional context. In addition, the bidirectional decoding scheme and the characteristic of LST tasks motivate us to share the encoder and the decoder of seq2seq models. The proposed PBD approach provides right side context information for the decoder and models the inductive bias of LST tasks, reducing the number of parameters by half and providing good regularization effects. Experimental results on several benchmark datasets show that our approach consistently improves the performance of standard seq2seq models on LST tasks.
Locally Private Distributed Reinforcement Learning
Venue: arXiv cs.LG 2020
Year: 2020

We study locally differentially private algorithms for reinforcement learning to obtain a robust policy that performs well across distributed private environments. Our algorithm protects the information of local agents' models from being exploited by adversarial reverse engineering. Since a local policy is strongly being affected by the individual environment, the output of the agent may release the private information unconsciously. In our proposed algorithm, local agents update the model in their environments and report noisy gradients designed to satisfy local differential privacy (LDP) that gives a rigorous local privacy guarantee. By utilizing a set of reported noisy gradients, a central aggregator updates its model and delivers it to different local agents. In our empirical evaluation, we demonstrate how our method performs well under LDP. To the best of our knowledge, this is the first work that actualizes distributed reinforcement learning under LDP. This work enables us to obtain a robust agent that performs well across distributed private environments.
On the binomial equivalence classes of finite words
Venue: arXiv cs.FL 2020
Year: 2020

Two finite words $u$ and $v$ are $k$-binomially equivalent if, for each word $x$ of length at most $k$, $x$ appears the same number of times as a subsequence (i.e., as a scattered subword) of both $u$ and $v$. This notion generalizes abelian equivalence. In this paper, we study the equivalence classes induced by the $k$-binomial equivalence with a special focus on the cardinalities of the classes. We provide an algorithm generating the $2$-binomial equivalence class of a word. For $k \geq 2$ and alphabet of $3$ or more symbols, the language made of lexicographically least elements of every $k$-binomial equivalence class and the language of singletons, i.e., the words whose $k$-binomial equivalence class is restricted to a single element, are shown to be non context-free. As a consequence of our discussions, we also prove that the submonoid generated by the generators of the free nil-$2$ group on $m$ generators is isomorphic to the quotient of the free monoid $\{ 1, \ldots , m\}^{*}$ by the $2$-binomial equivalence.