OpenRaiser/Intern-Atlas huggingface dataset:
Diff-DAC: Distributed Actor-Critic for Average Multitask Deep Reinforcement Learning
Venue: arXiv cs.LG 2020
Year: 2020

We propose a fully distributed actor-critic algorithm approximated by deep neural networks, named \textit{Diff-DAC}, with application to single-task and to average multitask reinforcement learning (MRL). Each agent has access to data from its local task only, but it aims to learn a policy that performs well on average for the whole set of tasks. During the learning process, agents communicate their value-policy parameters to their neighbors, diffusing the information across the network, so that they converge to a common policy, with no need for a central node. The method is scalable, since the computational and communication costs per agent grow with its number of neighbors. We derive Diff-DAC's from duality theory and provide novel insights into the standard actor-critic framework, showing that it is actually an instance of the dual ascent method that approximates the solution of a linear program. Experiments suggest that Diff-DAC can outperform the single previous distributed MRL approach (i.e., Dist-MTLPS) and even the centralized architecture.
The Stretch Factor of Hexagon-Delaunay Triangulations
Venue: arXiv cs.CG 2020
Year: 2020

The problem of computing the exact stretch factor (i.e., the tight bound on the worst case stretch factor) of a Delaunay triangulation is one of the longstanding open problems in computational geometry. Over the years, a series of upper and lower bounds on the exact stretch factor have been obtained but the gap between them is still large. An alternative approach to solving the problem is to develop techniques for computing the exact stretch factor of ``easier'' types of Delaunay triangulations, in particular those defined using regular-polygons instead of a circle. Tight bounds exist for Delaunay triangulations defined using an equilateral triangle and a square. In this paper, we determine the exact stretch factor of Delaunay triangulations defined using a regular hexagon: It is 2. We think that the main contribution of this paper are the two techniques we have developed to compute tight upper bounds for the stretch factor of Hexagon-Delaunay triangulations.
Rudin-Shapiro-Like Sequences with Maximum Asymptotic Merit Factor
Venue: arXiv cs.IT 2020
Year: 2020

Borwein and Mossinghoff investigated the Rudin-Shapiro-like sequences, which are infinite families of binary sequences, usually represented as polynomials. Each family of Rudin-Shapiro-like sequences is obtained from a starting sequence (which we call the seed) by a recursive construction that doubles the length of the sequence at each step, and many sequences produced in this manner have exceptionally low aperiodic autocorrelation. Borwein and Mossinghoff showed that the asymptotic autocorrelation merit factor for any such family is at most $3$, and found the seeds of length $40$ or less that produce the maximum asymptotic merit factor of $3$. The definition of Rudin-Shapiro-like sequences was generalized by Katz, Lee, and Trunov to include sequences with arbitrary complex coefficients, among which are families of low autocorrelation polyphase sequences. Katz, Lee, and Trunov proved that the maximum asymptotic merit factor is also $3$ for this larger class. Here we show that a family of such Rudin-Shapiro-like sequences achieves asymptotic merit factor $3$ if and only if the seed is either of length $1$ or is the interleaving of a pair of Golay complementary sequences. For small seed lengths where this is not possible, the optimal seeds are interleavings of pairs that are as close as possible to being complementary pairs, and the idea of an almost-complementary pair makes sense of remarkable patterns in previously unexplained data on optimal seeds for binary Rudin-Shapiro-like sequences.
Multi-antenna Interference Management for Coded Caching
Venue: arXiv cs.IT 2020
Year: 2020

A multi-antenna broadcast channel scenario is considered where a base station delivers contents to cache-enabled user terminals. A joint design of coded caching (CC) and multigroup multicast beamforming is proposed to benefit from spatial multiplexing gain, improved interference management and the global CC gain, simultaneously. The developed general content delivery strategies utilize the multiantenna multicasting opportunities provided by the CC technique while optimally balancing the detrimental impact of both noise and inter-stream interference from coded messages transmitted in parallel. Flexible resource allocation schemes for CC are introduced where the multicast beamformer design and the receiver complexity are controlled by varying the size of the subset of users served during a given time interval, and the overlap among the multicast messages transmitted in parallel, indicated by parameters $α$ and $β$, respectively. Degrees of freedom (DoF) analysis is provided showing that the DoF only depends on $α$ while it is independent of $β$. The proposed schemes are shown to provide the same degrees-of-freedom at high signal-to-noise ratio (SNR) as the state-of-art methods and, in general, to perform significantly better, especially in the finite SNR regime, than several baseline schemes.
Classical Control, Quantum Circuits and Linear Logic in Enriched Category Theory
Venue: arXiv cs.LO 2020
Year: 2020

We describe categorical models of a circuit-based (quantum) functional programming language. We show that enriched categories play a crucial role. Following earlier work on QWire by Paykin et al., we consider both a simple first-order linear language for circuits, and a more powerful host language, such that the circuit language is embedded inside the host language. Our categorical semantics for the host language is standard, and involves cartesian closed categories and monads. We interpret the circuit language not in an ordinary category, but in a category that is enriched in the host category. We show that this structure is also related to linear/non-linear models. As an extended example, we recall an earlier result that the category of W*-algebras is dcpo-enriched, and we use this model to extend the circuit language with some recursive types.
Acquiring Common Sense Spatial Knowledge through Implicit Spatial Templates
Venue: arXiv cs.AI 2020
Year: 2020

Spatial understanding is a fundamental problem with wide-reaching real-world applications. The representation of spatial knowledge is often modeled with spatial templates, i.e., regions of acceptability of two objects under an explicit spatial relationship (e.g., "on", "below", etc.). In contrast with prior work that restricts spatial templates to explicit spatial prepositions (e.g., "glass on table"), here we extend this concept to implicit spatial language, i.e., those relationships (generally actions) for which the spatial arrangement of the objects is only implicitly implied (e.g., "man riding horse"). In contrast with explicit relationships, predicting spatial arrangements from implicit spatial language requires significant common sense spatial understanding. Here, we introduce the task of predicting spatial templates for two objects under a relationship, which can be seen as a spatial question-answering task with a (2D) continuous output ("where is the man w.r.t. a horse when the man is walking the horse?"). We present two simple neural-based models that leverage annotated images and structured text to learn this task. The good performance of these models reveals that spatial locations are to a large extent predictable from implicit spatial language. Crucially, the models attain similar performance in a challenging generalized setting, where the object-relation-object combinations (e.g.,"man walking dog") have never been seen before. Next, we go one step further by presenting the models with unseen objects (e.g., "dog"). In this scenario, we show that leveraging word embeddings enables the models to output accurate spatial predictions, proving that the models acquire solid common sense spatial knowledge allowing for such generalization.
Edge Estimation with Independent Set Oracles
Venue: arXiv cs.DS 2020
Year: 2020

We study the task of estimating the number of edges in a graph with access to only an independent set oracle. Independent set queries draw motivation from group testing and have applications to the complexity of decision versus counting problems. We give two algorithms to estimate the number of edges in an $n$-vertex graph, using (i) $\mathrm{polylog}(n)$ bipartite independent set queries, or (ii) ${n}^{2/3} \cdot\mathrm{polylog}(n)$ independent set queries.
Generating Thematic Chinese Poetry using Conditional Variational Autoencoders with Hybrid Decoders
Venue: arXiv cs.CL 2020
Year: 2020

Computer poetry generation is our first step towards computer writing. Writing must have a theme. The current approaches of using sequence-to-sequence models with attention often produce non-thematic poems. We present a novel conditional variational autoencoder with a hybrid decoder adding the deconvolutional neural networks to the general recurrent neural networks to fully learn topic information via latent variables. This approach significantly improves the relevance of the generated poems by representing each line of the poem not only in a context-sensitive manner but also in a holistic way that is highly related to the given keyword and the learned topic. A proposed augmented word2vec model further improves the rhythm and symmetry. Tests show that the generated poems by our approach are mostly satisfying with regulated rules and consistent themes, and 73.42% of them receive an Overall score no less than 3 (the highest score is 5).
RUR53: an Unmanned Ground Vehicle for Navigation, Recognition and Manipulation
Venue: arXiv cs.RO 2020
Year: 2020

This paper proposes RUR53: an Unmanned Ground Vehicle able to autonomously navigate through, identify, and reach areas of interest; and there recognize, localize, and manipulate work tools to perform complex manipulation tasks. The proposed contribution includes a modular software architecture where each module solves specific sub-tasks and that can be easily enlarged to satisfy new requirements. Included indoor and outdoor tests demonstrate the capability of the proposed system to autonomously detect a target object (a panel) and precisely dock in front of it while avoiding obstacles. They show it can autonomously recognize and manipulate target work tools (i.e., wrenches and valve stems) to accomplish complex tasks (i.e., use a wrench to rotate a valve stem). A specific case study is described where the proposed modular architecture lets easy switch to a semi-teleoperated mode. The paper exhaustively describes description of both the hardware and software setup of RUR53, its performance when tests at the 2017 Mohamed Bin Zayed International Robotics Challenge, and the lessons we learned when participating at this competition, where we ranked third in the Gran Challenge in collaboration with the Czech Technical University in Prague, the University of Pennsylvania, and the University of Lincoln (UK).
When are epsilon-nets small?
Venue: arXiv cs.CG 2020
Year: 2020

In many interesting situations the size of epsilon-nets depends only on $ε$ together with different complexity measures. The aim of this paper is to give a systematic treatment of such complexity measures arising in Discrete and Computational Geometry and Statistical Learning, and to bridge the gap between the results appearing in these two fields. As a byproduct, we obtain several new upper bounds on the sizes of epsilon-nets that generalize/improve the best known general guarantees. In particular, our results work with regimes when small epsilon-nets of size $o(\frac{1}ε)$ exist, which are not usually covered by standard upper bounds. Inspired by results in Statistical Learning we also give a short proof of the Haussler's upper bound on packing numbers.
Multi-class Semantic Segmentation of Skin Lesions via Fully Convolutional Networks
Venue: arXiv cs.CV 2020
Year: 2020

Melanoma is clinically difficult to distinguish from common benign skin lesions, particularly melanocytic naevus and seborrhoeic keratosis. The dermoscopic appearance of these lesions has huge intra-class variations and high inter-class visual similarities. Most current research is focusing on single-class segmentation irrespective of classes of skin lesions. In this work, we evaluate the performance of deep learning on multi-class segmentation of ISIC-2017 challenge dataset, which consists of 2,750 dermoscopic images. We propose an end-to-end solution using fully convolutional networks (FCNs) for multi-class semantic segmentation to automatically segment the melanoma, seborrhoeic keratosis and naevus. To improve the performance of FCNs, transfer learning and a hybrid loss function are used. We evaluate the performance of the deep learning segmentation methods for multi-class segmentation and lesion diagnosis (with post-processing method) on the testing set of the ISIC-2017 challenge dataset. The results showed that the two-tier level transfer learning FCN-8s achieved the overall best result with \textit{Dice} score of 78.5% in a naevus category, 65.3% in melanoma, and 55.7% in seborrhoeic keratosis in multi-class segmentation and Accuracy of 84.62% for recognition of melanoma in lesion diagnosis.
Exploration of an Interdisciplinary Scientific Landscape
Venue: arXiv cs.DL 2020
Year: 2020

Patterns of interdisciplinarity in science can be quantified through diverse complementary dimensions. This paper studies as a case study the scientific environment of a generalist journal in Geography, Cybergeo, in order to introduce a novel methodology combining citation network analysis and semantic analysis. We collect a large corpus of around 200,000 articles with their abstracts and the corresponding citation network that provides a first citation classification. Relevant keywords are extracted for each article through text-mining, allowing us to construct a semantic classification. We study the qualitative patterns of relations between endogenous disciplines within each classification, and finally show the complementarity of classifications and of their associated interdisciplinarity measures. The tools we develop accordingly are open and reusable for similar large scale studies of scientific environments.
On Capacity-Achieving Distributions for Complex AWGN Channels Under Nonlinear Power Constraints and their Applications to SWIPT
Venue: arXiv cs.IT 2020
Year: 2020

The capacity of a complex and discrete-time memoryless additive white Gaussian noise (AWGN) channel under three constraints, namely, input average power, input amplitude and output delivered power is studied. The output delivered power constraint is modelled as the average of linear combination of even moments of the channel input being larger than a threshold. It is shown that the capacity of an AWGN channel under transmit average power and receiver delivered power constraints is the same as the capacity of an AWGN channel under an average power constraint. However, depending on the two constraints, the capacity can be either achieved by a Gaussian distribution or arbitrarily approached by using time-sharing between a Gaussian distribution and On-Off Keying. As an application, a simultaneous wireless information and power transfer (SWIPT) problem is studied, where an experimentally-validated nonlinear model of the harvester is used. It is shown that the delivered power depends on higher order moments of the channel input. Two inner bounds, one based on complex Gaussian inputs and the other based on further restricting the delivered power are obtained for the Rate-Power (RP) region. For Gaussian inputs, the optimal inputs are zero mean and a tradeoff between transmitted information and delivered power is recognized by considering asymmetric power allocations between inphase and quadrature subchannels. Through numerical algorithms, it is observed that input distributions (obtained by restricting the delivered power) attain larger RP region compared to Gaussian input counterparts.
DeepCache: Principled Cache for Mobile Deep Vision
Venue: arXiv cs.CV 2020
Year: 2020

We present DeepCache, a principled cache design for deep learning inference in continuous mobile vision. DeepCache benefits model execution efficiency by exploiting temporal locality in input video streams. It addresses a key challenge raised by mobile vision: the cache must operate under video scene variation, while trading off among cacheability, overhead, and loss in model accuracy. At the input of a model, DeepCache discovers video temporal locality by exploiting the video's internal structure, for which it borrows proven heuristics from video compression; into the model, DeepCache propagates regions of reusable results by exploiting the model's internal structure. Notably, DeepCache eschews applying video heuristics to model internals which are not pixels but high-dimensional, difficult-to-interpret data. Our implementation of DeepCache works with unmodified deep learning models, requires zero developer's manual effort, and is therefore immediately deployable on off-the-shelf mobile devices. Our experiments show that DeepCache saves inference execution time by 18% on average and up to 47%. DeepCache reduces system energy consumption by 20% on average.
Selective-Candidate Framework with Similarity Selection Rule for Evolutionary Optimization
Venue: arXiv cs.NE 2020
Year: 2020

Achieving better exploitation and exploration capabilities (EEC) have always been an important yet challenging issue in the design of evolutionary optimization algorithm (EOA). The difficulties lie in obtaining a good balance in EEC, which is determined cooperatively by operations and parameters in an EOA. When deficiencies in exploitation or exploration are observed, most existing works consider a piecemeal approach, either by designing new operations or by altering the parameters. Unfortunately, when different situations are encountered, these proposals may fail to be the winner. To address these problems, this paper proposes an explicit EEC control method named selective-candidate framework with similarity selection rule (SCSS). M (M > 1) candidates are first generated from each current solution with independent operations and parameters to enrich the search. Then, a similarity selection rule is designed to determine the final candidate by considering the fitness ranking of the current solution and its Euclidian distance to each of these M candidates. Superior current solutions will prefer the closest candidates for efficient local exploitation while inferior ones will favor the farthest for exploration purpose. In this way, the rule could synthesize exploitation and exploration, making the evolution more effective. When applied to three classic, four state-of-the-art and four up-to-date EOAs from branches of differential evolution, evolution strategy and particle swarm optimization, significant enhancement in performance is achieved.
Time-Space Trade-Offs for Computing Euclidean Minimum Spanning Trees
Venue: arXiv cs.CG 2020
Year: 2020

We present time-space trade-offs for computing the Euclidean minimum spanning tree of a set $S$ of $n$ point-sites in the plane. More precisely, we assume that $S$ resides in a random-access memory that can only be read. The edges of the Euclidean minimum spanning tree $\text{EMST}(S)$ have to be reported sequentially, and they cannot be accessed or modified afterwards. There is a parameter $s \in \{1, \dots, n\}$ so that the algorithm may use $O(s)$ cells of read-write memory (called the workspace) for its computations. Our goal is to find an algorithm that has the best possible running time for any given $s$ between $1$ and $n$. We show how to compute $\text{EMST}(S)$ in $O\big((n^3/s^2)\log s \big)$ time with $O(s)$ cells of workspace, giving a smooth trade-off between the two best known bounds $O(n^3)$ for $s = 1$ and $O(n \log n)$ for $s = n$. For this, we run Kruskal's algorithm on the relative neighborhood graph (RNG) of $S$. It is a classic fact that the minimum spanning tree of $\text{RNG}(S)$ is exactly $\text{EMST}(S)$. To implement Kruskal's algorithm with $O(s)$ cells of workspace, we define $s$-nets, a compact representation of planar graphs. This allows us to efficiently maintain and update the components of the current minimum spanning forest as the edges are being inserted.
Towards a More Complete Object-Orientation in Design Grammars
Venue: arXiv cs.SE 2020
Year: 2020

The ongoing digital transformation in industry applies to all product life cycle's stages. The design decisions and dimensioning carried out in the early conceptual design stages determine a huge part of the product's life cycle costs (LCC). The automation of the conceptual design phase promises therefore huge gains in terms of LCC. Design grammars encode design processes in production systems made up of rule sequences which automatically create an abstract central product model (central data model) from given requirements. Graph-based design languages use the Unified-Modeling-Language (UML) to define the product entities (classes) supporting object-oriented inheritance. Graphical rules instantiate the classes and iteratively assemble the central model. This paper proposes to extend the design languages by introducing methods (operations). This allows the use of object-oriented design patterns and interface mechanisms as object-oriented principles are then fully implemented. A graphical mechanism to model the method calls is presented which integrates seamlessly into the graph-based design language's graphical rule specification. The object oriented design grammar enables modularization and reusability of engineering knowledge. The integration of engineering domains is enhanced and multistakeholder collaboration with access control (information security) becomes feasible.
Automaton Semigroups and Groups: On the Undecidability of Problems Related to Freeness and Finiteness
Venue: arXiv cs.FL 2020
Year: 2020

In this paper, we study algorithmic problems for automaton semigroups and automaton groups related to freeness and finiteness. In the course of this study, we also exhibit some connections between the algebraic structure of automaton (semi)groups and their dynamics on the boundary. First, we show that it is undecidable to check whether the group generated by a given invertible automaton has a positive relation, i.e. a relation p = 1 such that p only contains positive generators. Besides its obvious relation to the freeness of the group, the absence of positive relations has previously been studied and is connected to the triviality of some stabilizers of the boundary. We show that the emptiness of the set of positive relations is equivalent to the dynamical property that all (directed positive) orbital graphs centered at non-singular points are acyclic. Gillibert showed that the finiteness problem for automaton semigroups is undecidable. In the second part of the paper, we show that this undecidability result also holds if the input is restricted to be bi-reversible and invertible (but, in general, not complete). As an immediate consequence, we obtain that the finiteness problem for automaton subsemigroups of semigroups generated by invertible, yet partial automata, so called automaton-inverse semigroups, is also undecidable. Erratum: Contrary to a statement in a previous version of the paper, our approach does not show that that the freeness problem for automaton semigroups is undecidable. We discuss this in an erratum at the end of the paper.