OpenRaiser/Intern-Atlas huggingface dataset:
On mechanisms for transfer using landmark value functions in multi-task lifelong reinforcement learning
Venue: arXiv cs.LG 2019
Year: 2019

Transfer learning across different reinforcement learning (RL) tasks is becoming an increasingly valuable area of research. We consider a goal-based multi-task RL framework and mechanisms by which previously solved tasks can reduce sample complexity and regret when the agent is faced with a new task. Specifically, we introduce two metrics on the state space that encode notions of traversibility of the state space for an agent. Using these metrics a topological covering is constructed by way of a set of landmark states in a fully self-supervised manner. We show that these landmark coverings confer theoretical advantages for transfer learning within the goal-based multi-task RL setting. Specifically, we demonstrate three mechanisms by which landmark coverings can be used for successful transfer learning. First, we extend the Landmark Options Via Reflection (LOVR) framework to this new topological covering; second, we use the landmark-centric value functions themselves as features and define a greedy zombie policy that achieves near oracle performance on a sequence of zero-shot transfer tasks; finally, motivated by the second transfer mechanism, we introduce a learned reward function that provides a more dense reward signal for goal-based RL. Our novel topological landmark covering confers beneficial theoretical results, bounding the Q values at each state-action pair. In doing so, we introduce a mechanism that performs action-pruning at infeasible actions which cannot possibly be part of an optimal policy for the current goal.
Single-Path Mobile AutoML: Efficient ConvNet Design and NAS Hyperparameter Optimization
Venue: arXiv cs.LG 2019
Year: 2019

Can we reduce the search cost of Neural Architecture Search (NAS) from days down to only few hours? NAS methods automate the design of Convolutional Networks (ConvNets) under hardware constraints and they have emerged as key components of AutoML frameworks. However, the NAS problem remains challenging due to the combinatorially large design space and the significant search time (at least 200 GPU-hours). In this work, we alleviate the NAS search cost down to less than 3 hours, while achieving state-of-the-art image classification results under mobile latency constraints. We propose a novel differentiable NAS formulation, namely Single-Path NAS, that uses one single-path over-parameterized ConvNet to encode all architectural decisions based on shared convolutional kernel parameters, hence drastically decreasing the search overhead. Single-Path NAS achieves state-of-the-art top-1 ImageNet accuracy (75.62%), hence outperforming existing mobile NAS methods in similar latency settings (~80ms). In particular, we enhance the accuracy-runtime trade-off in differentiable NAS by treating the Squeeze-and-Excitation path as a fully searchable operation with our novel single-path encoding. Our method has an overall cost of only 8 epochs (24 TPU-hours), which is up to 5,000x faster compared to prior work. Moreover, we study how different NAS formulation choices affect the performance of the designed ConvNets. Furthermore, we exploit the efficiency of our method to answer an interesting question: instead of empirically tuning the hyperparameters of the NAS solver (as in prior work), can we automatically find the hyperparameter values that yield the desired accuracy-runtime trade-off? We open-source our entire codebase at: https://github.com/dstamoulis/single-path-nas.
The Sensitivity of Counterfactual Fairness to Unmeasured Confounding
Venue: arXiv cs.LG 2019
Year: 2019

Causal approaches to fairness have seen substantial recent interest, both from the machine learning community and from wider parties interested in ethical prediction algorithms. In no small part, this has been due to the fact that causal models allow one to simultaneously leverage data and expert knowledge to remove discriminatory effects from predictions. However, one of the primary assumptions in causal modeling is that you know the causal graph. This introduces a new opportunity for bias, caused by misspecifying the causal model. One common way for misspecification to occur is via unmeasured confounding: the true causal effect between variables is partially described by unobserved quantities. In this work we design tools to assess the sensitivity of fairness measures to this confounding for the popular class of non-linear additive noise models (ANMs). Specifically, we give a procedure for computing the maximum difference between two counterfactually fair predictors, where one has become biased due to confounding. For the case of bivariate confounding our technique can be swiftly computed via a sequence of closed-form updates. For multivariate confounding we give an algorithm that can be efficiently solved via automatic differentiation. We demonstrate our new sensitivity analysis tools in real-world fairness scenarios to assess the bias arising from confounding.
Natural Language Understanding with the Quora Question Pairs Dataset
Venue: arXiv cs.CL 2019
Year: 2019

This paper explores the task Natural Language Understanding (NLU) by looking at duplicate question detection in the Quora dataset. We conducted extensive exploration of the dataset and used various machine learning models, including linear and tree-based models. Our final finding was that a simple Continuous Bag of Words neural network model had the best performance, outdoing more complicated recurrent and attention based models. We also conducted error analysis and found some subjectivity in the labeling of the dataset.
Investigating The Piece-Wise Linearity And Benchmark Related To Koczy-Hirota Fuzzy Linear Interpolation
Venue: arXiv cs.AI 2019
Year: 2019

Fuzzy Rule Interpolation (FRI) reasoning methods have been introduced to address sparse fuzzy rule bases and reduce complexity. The first FRI method was the Koczy and Hirota (KH) proposed "Linear Interpolation". Besides, several conditions and criteria have been suggested for unifying the common requirements FRI methods have to satisfy. One of the most conditions is restricted the fuzzy set of the conclusion must preserve a Piece-Wise Linearity (PWL) if all antecedents and consequents of the fuzzy rules are preserving on PWL sets at α-cut levels. The KH FRI is one of FRI methods which cannot satisfy this condition. Therefore, the goal of this paper is to investigate equations and notations related to PWL property, which is aimed to highlight the problematic properties of the KH FRI method to prove its efficiency with PWL condition. In addition, this paper is focusing on constructing benchmark examples to be a baseline for testing other FRI methods against situations that are not satisfied with the linearity condition for KH FRI.
DeepTEGINN: Deep Learning Based Tools to Extract Graphs from Images of Neural Networks
Venue: arXiv cs.CV 2019
Year: 2019

In the brain, the structure of a network of neurons defines how these neurons implement the computations that underlie the mind and the behavior of animals and humans. Provided that we can describe the network of neurons as a graph, we can employ methods from graph theory to investigate its structure or use cellular automata to mathematically assess its function. Although, software for the analysis of graphs and cellular automata are widely available. Graph extraction from the image of networks of brain cells remains difficult. Nervous tissue is heterogeneous, and differences in anatomy may reflect relevant differences in function. Here we introduce a deep learning based toolbox to extracts graphs from images of brain tissue. This toolbox provides an easy-to-use framework allowing system neuroscientists to generate graphs based on images of brain tissue by combining methods from image processing, deep learning, and graph theory. The goals are to simplify the training and usage of deep learning methods for computer vision and facilitate its integration into graph extraction pipelines. In this way, the toolbox provides an alternative to the required laborious manual process of tracing, sorting and classifying. We expect to democratize the machine learning methods to a wider community of users beyond the computer vision experts and improve the time-efficiency of graph extraction from large brain image datasets, which may lead to further understanding of the human mind.
A Semi-Supervised Self-Organizing Map for Clustering and Classification
Venue: arXiv cs.LG 2019
Year: 2019

There has been an increasing interest in semi-supervised learning in the recent years because of the great number of datasets with a large number of unlabeled data but only a few labeled samples. Semi-supervised learning algorithms can work with both types of data, combining them to obtain better performance for both clustering and classification. Also, these datasets commonly have a high number of dimensions. This article presents a new semi-supervised method based on self-organizing maps (SOMs) for clustering and classification, called Semi-Supervised Self-Organizing Map (SS-SOM). The method can dynamically switch between supervised and unsupervised learning during the training according to the availability of the class labels for each pattern. Our results show that the SS-SOM outperforms other semi-supervised methods in conditions in which there is a low amount of labeled samples, also achieving good results when all samples are labeled.
Multi-scale Template Matching with Scalable Diversity Similarity in an Unconstrained Environment
Venue: arXiv cs.CV 2019
Year: 2019

We propose a novel multi-scale template matching method which is robust against both scaling and rotation in unconstrained environments. The key component behind is a similarity measure referred to as scalable diversity similarity (SDS). Specifically, SDS exploits bidirectional diversity of the nearest neighbor (NN) matches between two sets of points. To address the scale-robustness of the similarity measure, local appearance and rank information are jointly used for the NN search. Furthermore, by introducing penalty term on the scale change, and polar radius term into the similarity measure, SDS is shown to be a well-performing similarity measure against overall size and rotation changes, as well as non-rigid geometric deformations, background clutter, and occlusions. The properties of SDS are statistically justified, and experiments on both synthetic and real-world data show that SDS can significantly outperform state-of-the-art methods.
Kleene Theorems for Free Choice Nets Labelled with Distributed Alphabets
Venue: arXiv cs.FL 2019
Year: 2019

We provided (PNSE'2014) expressions for free choice nets having "distributed choice property" which makes the nets "direct product" representable. In a recent work (PNSE'2016), we gave equivalent syntax for a larger class of free choice nets obtained by dropping distributed choice property. In both these works, the classes of free choice nets were restricted by a "product condition" on the set of final markings. In this paper we do away with this restriction and give expressions for the resultant classes of nets which correspond to "free choice synchronous products and Zielonka automata". For free choice nets with distributed choice property, we give an alternative characterization using properties checkable in polynomial time. Free choice nets we consider are 1-bounded, S-coverable, and are labelled with distributed alphabets, where S-components of the associated S-cover respect the given alphabet distribution.
Conservative Q-Improvement: Reinforcement Learning for an Interpretable Decision-Tree Policy
Venue: arXiv cs.LG 2019
Year: 2019

There is a growing desire in the field of reinforcement learning (and machine learning in general) to move from black-box models toward more "interpretable AI." We improve interpretability of reinforcement learning by increasing the utility of decision tree policies learned via reinforcement learning. These policies consist of a decision tree over the state space, which requires fewer parameters to express than traditional policy representations. Existing methods for creating decision tree policies via reinforcement learning focus on accurately representing an action-value function during training, but this leads to much larger trees than would otherwise be required. To address this shortcoming, we propose a novel algorithm which only increases tree size when the estimated discounted future reward of the overall policy would increase by a sufficient amount. Through evaluation in a simulated environment, we show that its performance is comparable or superior to traditional tree-based approaches and that it yields a more succinct policy. Additionally, we discuss tuning parameters to control the tradeoff between optimizing for smaller tree size or for overall reward.
A Framework for Evaluating Snippet Generation for Dataset Search
Venue: arXiv cs.IR 2019
Year: 2019

Reusing existing datasets is of considerable significance to researchers and developers. Dataset search engines help a user find relevant datasets for reuse. They can present a snippet for each retrieved dataset to explain its relevance to the user's data needs. This emerging problem of snippet generation for dataset search has not received much research attention. To provide a basis for future research, we introduce a framework for quantitatively evaluating the quality of a dataset snippet. The proposed metrics assess the extent to which a snippet matches the query intent and covers the main content of the dataset. To establish a baseline, we adapt four state-of-the-art methods from related fields to our problem, and perform an empirical evaluation based on real-world datasets and queries. We also conduct a user study to verify our findings. The results demonstrate the effectiveness of our evaluation framework, and suggest directions for future research.
Convergence Detection of Asynchronous Iterations based on Modified Recursive Doubling
Venue: arXiv cs.DC 2019
Year: 2019

This paper addresses the distributed convergence detection problem in asynchronous iterations. A modified recursive doubling algorithm is investigated in order to adapt to the non-power-of-two case. Some convergence detection algorithms are illustrated based on the reduction operation. Finally, a concluding discussion about the implementation and the applicability is presented.
Persistent Multi-UAV Surveillance with Data Latency Constraints
Venue: arXiv cs.RO 2019
Year: 2019

We discuss surveillance with multiple unmanned aerial vehicles (UAV) that minimize idleness (the time between consecutive visits of sensing locations) and constrain latency (the time between capturing data at a sensing location and its arrival at the base station). This is important in persistent surveillance scenarios where sensing locations should not only be visited periodically, but the captured data also should reach the base station in due time even if the area is larger than the communication range. Our approach employs the concept of minimum-latency paths (MLP) to guarantee that the data reaches the base station within a predefined latency bound. To reach the bound, multiple UAVs cooperatively transport the data in a store-and-forward fashion. Additionally, MLPs specify a lower bound for any latency minimization problem where multiple mobile agents transport data in a store-and-forward fashion. We introduce three variations of a heuristic employing MLPs and compare their performance in a simulation study. The results show that extensions of the simplest of our approaches, where data is transported after each visit of a sensing location, show improved performance and the tradeoff between latency and idleness.
Logics for Reversible Regular Languages and Semigroups with Involution
Venue: arXiv cs.FL 2019
Year: 2019

We present MSO and FO logics with predicates `between' and `neighbour' that characterise various fragments of the class of regular languages that are closed under the reverse operation. The standard connections that exist between MSO and FO logics and varieties of finite semigroups extend to this setting with semigroups extended with an involution. The case is different for FO with neighbour relation where we show that one needs additional equations to characterise the class.
TedEval: A Fair Evaluation Metric for Scene Text Detectors
Venue: arXiv cs.CV 2019
Year: 2019

Despite the recent success of scene text detection methods, common evaluation metrics fail to provide a fair and reliable comparison among detectors. They have obvious drawbacks in reflecting the inherent characteristic of text detection tasks, unable to address issues such as granularity, multiline, and character incompleteness. In this paper, we propose a novel evaluation protocol called TedEval (Text detector Evaluation), which evaluates text detections by an instance-level matching and a character-level scoring. Based on a firm standard rewarding behaviors that result in successful recognition, TedEval can act as a reliable standard for comparing and quantizing the detection quality throughout all difficulty levels. In this regard, we believe that TedEval can play a key role in developing state-of-the-art scene text detectors. The code is publicly available at https://github.com/clovaai/TedEval.
A Constant-Factor Approximation Algorithm for Vertex Guarding a WV-Polygon
Venue: arXiv cs.CG 2019
Year: 2019

The problem of vertex guarding a simple polygon was first studied by Subir K. Ghosh (1987), who presented a polynomial-time $O(\log n)$-approximation algorithm for placing as few guards as possible at vertices of a simple $n$-gon $P$, such that every point in $P$ is visible to at least one of the guards. Ghosh also conjectured that this problem admits a polynomial-time algorithm with constant approximation ratio. Due to the centrality of guarding problems in the field of computational geometry, much effort has been invested throughout the years in trying to resolve this conjecture. Despite some progress (surveyed below), the conjecture remains unresolved to date. In this paper, we confirm the conjecture for the important case of weakly visible polygons, by presenting a $(2+\varepsilon)$-approximation algorithm for guarding such a polygon using vertex guards. A simple polygon $P$ is weakly visible if it has an edge $e$, such that every point in $P$ is visible from some point on $e$. We also present a $(2+\varepsilon)$-approximation algorithm for guarding a weakly visible polygon $P$, where guards may be placed anywhere on $P$'s boundary (except in the interior of the edge $e$). Finally, we present a $3c$-approximation algorithm for vertex guarding a polygon $P$ that is weakly visible from a chord, given a subset $G$ of $P$'s vertices that guards $P$'s boundary whose size is bounded by $c$ times the size of a minimum such subset. Our algorithms are based on an in-depth analysis of the geometric properties of the regions that remain unguarded after placing guards at the vertices to guard the polygon's boundary. It is plausible that our results will enable Bhattacharya et al. to complete their grand attempt to prove the original conjecture, as their approach is based on partitioning the underlying simple polygon into a hierarchy of weakly visible polygons.
Geometric Crossing-Minimization -- A Scalable Randomized Approach
Venue: arXiv cs.CG 2019
Year: 2019

We consider the minimization of edge-crossings in geometric drawings of graphs $G=(V, E)$, i.e., in drawings where each edge is depicted as a line segment. The respective decision problem is NP-hard [Bienstock, '91]. In contrast to theory and the topological setting, the geometric setting did not receive a lot of attention in practice. Prior work [Radermacher et al., ALENEX'18] is limited to the crossing-minimization in geometric graphs with less than $200$ edges. The described heuristics base on the primitive operation of moving a single vertex $v$ to its crossing-minimal position, i.e., the position in $\mathbb{R}^2$ that minimizes the number of crossings on edges incident to $v$. In this paper, we introduce a technique to speed-up the computation by a factor of $20$. This is necessary but not sufficient to cope with graphs with a few thousand edges. In order to handle larger graphs, we drop the condition that each vertex $v$ has to be moved to its crossing-minimal position and compute a position that is only optimal with respect to a small random subset of the edges. In our theoretical contribution, we consider drawings that contain for each edge $uv \in E$ and each position $p \in \mathbb{R}^2$ for $v$ $o(|E|)$ crossings. In this case, we prove that with a random subset of the edges of size $Θ(k \log k)$ the co-crossing number of a degree-$k$ vertex $v$, i.e., the number of edge pairs $uv \in E, e \in E$ that do not cross, can be approximated by an arbitrary but fixed factor $δ$ with high probability. In our experimental evaluation, we show that the randomized approach reduces the number of crossings in graphs with up to $13\,000$ edges considerably. The evaluation suggests that depending on the degree-distribution different strategies result in the fewest number of crossings.
Semi-Bagging Based Deep Neural Architecture to Extract Text from High Entropy Images
Venue: arXiv cs.CV 2019
Year: 2019

Extracting texts of various size and shape from images containing multiple objects is an important problem in many contexts, especially, in connection to e-commerce, augmented reality assistance system in natural scene, etc. The existing works (based on only CNN) often perform sub-optimally when the image contains regions of high entropy having multiple objects. This paper presents an end-to-end text detection strategy combining a segmentation algorithm and an ensemble of multiple text detectors of different types to detect text in every individual image segments independently. The proposed strategy involves a super-pixel based image segmenter which splits an image into multiple regions. A convolutional deep neural architecture is developed which works on each of the segments and detects texts of multiple shapes, sizes, and structures. It outperforms the competing methods in terms of coverage in detecting texts in images especially the ones where the text of various types and sizes are compacted in a small region along with various other objects. Furthermore, the proposed text detection method along with a text recognizer outperforms the existing state-of-the-art approaches in extracting text from high entropy images. We validate the results on a dataset consisting of product images on an e-commerce website.
Service-based Routing at the Edge
Venue: arXiv cs.NI 2019
Year: 2019

Future scenarios, such as AR/VR, pose challenging latency and bandwidth requirements in 5G. This need is complemented by the adoption of cloud principles for providing services, particularly for virtualizing service components with which virtualized instances can appear rapidly at different execution points in the network. While providing service endpoints close to the end user appears straightforward, this early service break-out is currently limited to routing requests to Point-of-Presence (POP) nodes provided by a few global CDN players deep in the customer network. In this paper, we propose instead to turn the edge of the Internet into a rich service-based routing infrastructure with services being provided through edge compute nodes, without needing indirect routing. Our approach interprets every IP-based service as a named service over a (L2 or similar) transport network, requiring no per-flow state in the network, while natively supporting both unicast and multicast delivery. The solution allows route adjustments in time scales of few tens of milliseconds, enabling rapid failure recovery, extremely responsive load balancing, efficient mobility support, and more. We implemented our solution on standard SDN-based infrastructure and in mobile terminals in a backwards-compatible manner, enabling a performance evaluation that shows significant improvements in network utilization as well as flow setup times.