OpenRaiser/Intern-Atlas huggingface dataset:
A Holistic Representation Guided Attention Network for Scene Text Recognition
Venue: arXiv cs.CV 2021
Year: 2021

Reading irregular scene text of arbitrary shape in natural images is still a challenging problem, despite the progress made recently. Many existing approaches incorporate sophisticated network structures to handle various shapes, use extra annotations for stronger supervision, or employ hard-to-train recurrent neural networks for sequence modeling. In this work, we propose a simple yet strong approach for scene text recognition. With no need to convert input images to sequence representations, we directly connect two-dimensional CNN features to an attention-based sequence decoder which guided by holistic representation. The holistic representation can guide the attention-based decoder focus on more accurate area. As no recurrent module is adopted, our model can be trained in parallel. It achieves 1.5x to 9.4x acceleration to backward pass and 1.3x to 7.9x acceleration to forward pass, compared with the RNN counterparts. The proposed model is trained with only word-level annotations. With this simple design, our method achieves state-of-the-art or competitive recognition performance on the evaluated regular and irregular scene text benchmark datasets.
Complete Abstractions for Checking Language Inclusion
Venue: arXiv cs.FL 2021
Year: 2021

We study the language inclusion problem $L_1 \subseteq L_2$ where $L_1$ is regular or context-free. Our approach relies on abstract interpretation and checks whether an overapproximating abstraction of $L_1$, obtained by overapproximating the Kleene iterates of its least fixpoint characterization, is included in $L_2$. We show that a language inclusion problem is decidable whenever this overapproximating abstraction satisfies a completeness condition (i.e., its loss of precision causes no false alarm) and prevents infinite ascending chains (i.e., it guarantees termination of least fixpoint computations). This overapproximating abstraction of languages can be defined using quasiorder relations on words, where the abstraction gives the language of all the words "greater than or equal to" a given input word for that quasiorder. We put forward a range of such quasiorders that allow us to systematically design decision procedures for different language inclusion problems such as regular languages into regular languages or into trace sets of one-counter nets, and context-free languages into regular languages. In the case of inclusion between regular languages, some of the induced inclusion checking procedures correspond to well-known state-of-the-art algorithms like the so-called antichain algorithms. Finally, we provide an equivalent language inclusion checking algorithm based on a greatest fixpoint computation that relies on quotients of languages and, to the best of our knowledge, was not previously known.
Experimental Comparison of Open Source Visual-Inertial-Based State Estimation Algorithms in the Underwater Domain
Venue: arXiv cs.RO 2021
Year: 2021

A plethora of state estimation techniques have appeared in the last decade using visual data, and more recently with added inertial data. Datasets typically used for evaluation include indoor and urban environments, where supporting videos have shown impressive performance. However, such techniques have not been fully evaluated in challenging conditions, such as the marine domain. In this paper, we compare ten recent open-source packages to provide insights on their performance and guidelines on addressing current challenges. Specifically, we selected direct methods and tightly-coupled optimization techniques that fuse camera and Inertial Measurement Unit (IMU) data together. Experiments are conducted by testing all packages on datasets collected over the years with underwater robots in our laboratory. All the datasets are made available online.
Architectures in parametric component-based systems: Qualitative and quantitative modelling
Venue: arXiv cs.LO 2021
Year: 2021

One of the key aspects in component-based design is specifying the software architecture that characterizes the topology and the permissible interactions of the components of a system. To achieve well-founded design there is need to address both the qualitative and non-functional aspects of architectures. In this paper we study the qualitative and quantitative formal modelling of architectures applied on parametric component-based systems, that consist of an unknown number of instances of each component. Specifically, we introduce an extended propositional interaction logic and investigate its first-order level which serves as a formal language for the interactions of parametric systems. Our logics achieve to encode the execution order of interactions, which is a main feature in several important architectures, as well as to model recursive interactions. Moreover, we prove the decidability of equivalence, satisfiability, and validity of first-order extended interaction logic formulas, and provide several examples of formulas describing well-known architectures. We show the robustness of our theory by effectively extending our results for parametric weighted architectures. For this, we study the weighted counterparts of our logics over a commutative semiring, and we apply them for modelling the quantitative aspects of concrete architectures. Finally, we prove that the equivalence problem of weighted first-order extended interaction logic formulas is decidable in a large class of semirings, namely the class (of subsemirings) of skew fields.
Oceanic Games: Centralization Risks and Incentives in Blockchain Mining
Venue: arXiv cs.GT 2021
Year: 2021

To participate in the distributed consensus of permissionless blockchains, prospective nodes -- or miners -- provide proof of designated, costly resources. However, in contrast to the intended decentralization, current data on blockchain mining unveils increased concentration of these resources in a few major entities, typically mining pools. To study strategic considerations in this setting, we employ the concept of Oceanic Games, Milnor and Shapley (1978). Oceanic Games have been used to analyze decision making in corporate settings with small numbers of dominant players (shareholders) and large numbers of individually insignificant players, the ocean. Unlike standard equilibrium models, they focus on measuring the value (or power) per entity and per unit of resource} in a given distribution of resources. These values are viewed as strategic components in coalition formations, mergers and resource acquisitions. Considering such issues relevant to blockchain governance and long-term sustainability, we adapt oceanic games to blockchain mining and illustrate the defined concepts via examples. The application of existing results reveals incentives for individual miners to merge in order to increase the value of their resources. This offers an alternative perspective to the observed centralization and concentration of mining power. Beyond numerical simulations, we use the model to identify issues relevant to the design of future cryptocurrencies and formulate prospective research questions.
The Fishyscapes Benchmark: Measuring Blind Spots in Semantic Segmentation
Venue: arXiv cs.CV 2021
Year: 2021

Deep learning has enabled impressive progress in the accuracy of semantic segmentation. Yet, the ability to estimate uncertainty and detect failure is key for safety-critical applications like autonomous driving. Existing uncertainty estimates have mostly been evaluated on simple tasks, and it is unclear whether these methods generalize to more complex scenarios. We present Fishyscapes, the first public benchmark for uncertainty estimation in a real-world task of semantic segmentation for urban driving. It evaluates pixel-wise uncertainty estimates towards the detection of anomalous objects in front of the vehicle. We~adapt state-of-the-art methods to recent semantic segmentation models and compare approaches based on softmax confidence, Bayesian learning, and embedding density. Our results show that anomaly detection is far from solved even for ordinary situations, while our benchmark allows measuring advancements beyond the state-of-the-art.
Optimal Communication Rates and Combinatorial Properties for Common Randomness Generation
Venue: arXiv cs.IT 2021
Year: 2021

We study common randomness generation problems where $n$ players aim to generate same sequences of random coin flips where some subsets of the players share an independent common coin which can be tossed multiple times, and there is a publicly seen blackboard through which the players communicate with each other. We provide a tight representation of the optimal communication rates via linear programming, and more importantly, propose explicit algorithms for the optimal distributed simulation for a wide class of hypergraphs. In particular, the optimal communication rate in complete hypergraphs is still achievable in sparser hypergraphs containing a path-connected cycle-free cluster of topologically connected components. Some key steps in analyzing the upper bounds rely on two different definitions of connectivity in hypergraphs, which may be of independent interest.
A Flexible, Parallel, Adaptive Geometric Multigrid method for FEM
Venue: arXiv cs.NA 2021
Year: 2021

We present the design and implementation details of a geometric multigrid method on adaptively refined meshes for massively parallel computations. The method uses local smoothing on the refined part of the mesh. Partitioning is achieved by using a space filling curve for the leaf mesh and distributing ancestors in the hierarchy based on the leaves. We present a model of the efficiency of mesh hierarchy distribution and compare its predictions to runtime measurements. The algorithm is implemented as part of the deal.II finite element library and as such available to the public.
Two-Sided Matching Markets with Correlated Random Preferences
Venue: arXiv cs.DS 2021
Year: 2021

Stable matching in a community consisting of men and women is a classical combinatorial problem that has been the subject of intense theoretical and empirical study since its introduction in 1962 in a seminal paper by Gale and Shapley, who designed the celebrated ``deferred acceptance'' algorithm for the problem. In the input, each participant ranks participants of the opposite type, so the input consists of a collection of permutations, representing the preference lists. A bipartite matching is unstable if some man-woman pair is blocking: both strictly prefer each other to their partner in the matching. Stability is an important economics concept in matching markets from the viewpoint of manipulability. The unicity of a stable matching implies non-manipulability, and near-unicity implies limited manipulability, thus these are mathematical properties related to the quality of stable matching algorithms. This paper is a theoretical study of the effect of correlations on approximate manipulability of stable matching algorithms. Our approach is to go beyond worst case, assuming that some of the input preference lists are drawn from a distribution. Our model encompasses a discrete probabilistic process inspired by a popularity model introduced by Immorlica and Mahdian, that provides a way to capture correlation between preference lists. Approximate manipulability is approached from several angles : when all stable partners of a person have approximately the same rank; or when most persons have a unique stable partner. Another quantity of interest is a person's number of stable partners. Our results aim to paint a picture of the manipulability of stable matchings in a ``beyond worst case'' setting.
Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme
Venue: arXiv cs.DS 2021
Year: 2021

Vertex connectivity a classic extensively-studied problem. Given an integer $k$, its goal is to decide if an $n$-node $m$-edge graph can be disconnected by removing $k$ vertices. Although a linear-time algorithm was postulated since 1974 [Aho, Hopcroft and Ullman], and despite its sibling problem of edge connectivity being resolved over two decades ago [Karger STOC'96], so far no vertex connectivity algorithms are faster than $O(n^2)$ time even for $k=4$ and $m=O(n)$. In the simplest case where $m=O(n)$ and $k=O(1)$, the $O(n^2)$ bound dates five decades back to [Kleitman IEEE Trans. Circuit Theory'69]. For general $k$ and $m$, the best bound is $\tilde{O}(\min(kn^2, n^ω+nk^ω))$. In this paper, we present a randomized Monte Carlo algorithm with $\tilde{O}(m+k^{7/3}n^{4/3})$ time for any $k=O(\sqrt{n})$. This gives the {\em first subquadratic time} bound for any $4\leq k \leq o(n^{2/7})$ and improves all above classic bounds for all $k\le n^{0.44}$. We also present a new randomized Monte Carlo $(1+ε)$-approximation algorithm that is strictly faster than the previous Henzinger's 2-approximation algorithm [J. Algorithms'97] and all previous exact algorithms. The key to our results is to avoid computing single-source connectivity, which was needed by all previous exact algorithms and is not known to admit $o(n^2)$ time. Instead, we design the first local algorithm for computing vertex connectivity; without reading the whole graph, our algorithm can find a separator of size at most $k$ or certify that there is no separator of size at most $k$ `near' a given seed node.
Adversarial Learning of Disentangled and Generalizable Representations for Visual Attributes
Venue: arXiv cs.CV 2021
Year: 2021

Recently, a multitude of methods for image-to-image translation have demonstrated impressive results on problems such as multi-domain or multi-attribute transfer. The vast majority of such works leverages the strengths of adversarial learning and deep convolutional autoencoders to achieve realistic results by well-capturing the target data distribution. Nevertheless, the most prominent representatives of this class of methods do not facilitate semantic structure in the latent space, and usually rely on binary domain labels for test-time transfer. This leads to rigid models, unable to capture the variance of each domain label. In this light, we propose a novel adversarial learning method that (i) facilitates the emergence of latent structure by semantically disentangling sources of variation, and (ii) encourages learning generalizable, continuous, and transferable latent codes that enable flexible attribute mixing. This is achieved by introducing a novel loss function that encourages representations to result in uniformly distributed class posteriors for disentangled attributes. In tandem with an algorithm for inducing generalizable properties, the resulting representations can be utilized for a variety of tasks such as intensity-preserving multi-attribute image translation and synthesis, without requiring labelled test data. We demonstrate the merits of the proposed method by a set of qualitative and quantitative experiments on popular databases such as MultiPIE, RaFD, and BU-3DFE, where our method outperforms other, state-of-the-art methods in tasks such as intensity-preserving multi-attribute transfer and synthesis.
Political Text Scaling Meets Computational Semantics
Venue: arXiv cs.CL 2021
Year: 2021

During the last fifteen years, automatic text scaling has become one of the key tools of the Text as Data community in political science. Prominent text scaling algorithms, however, rely on the assumption that latent positions can be captured just by leveraging the information about word frequencies in documents under study. We challenge this traditional view and present a new, semantically aware text scaling algorithm, SemScale, which combines recent developments in the area of computational linguistics with unsupervised graph-based clustering. We conduct an extensive quantitative analysis over a collection of speeches from the European Parliament in five different languages and from two different legislative terms, and show that a scaling approach relying on semantic document representations is often better at capturing known underlying political dimensions than the established frequency-based (i.e., symbolic) scaling method. We further validate our findings through a series of experiments focused on text preprocessing and feature selection, document representation, scaling of party manifestos, and a supervised extension of our algorithm. To catalyze further research on this new branch of text scaling methods, we release a Python implementation of SemScale with all included data sets and evaluation procedures.
A partial knowledge of friends of friends speeds social search
Venue: arXiv cs.SI 2021
Year: 2021

Milgram empirically showed that people knowing only connections to their friends could locate any person in the U.S. in a few steps. Later research showed that social network topology enables a node aware of its full routing to find an arbitrary target in even fewer steps. Yet, the success of people in forwarding efficiently knowing only personal connections is still not fully explained. To study this problem, we emulate it on a real location-based social network, Gowalla. It provides explicit information about friends and temporal locations of each user useful for studies of human mobility. Here, we use it to conduct a massive computational experiment to establish new necessary and sufficient conditions for achieving social search efficiency. The results demonstrate that only the distribution of friendship edges and the partial knowledge of friends of friends are essential and sufficient for the efficiency of social search. Surprisingly, the efficiency of the search using the original distribution of friendship edges is not dependent on how the nodes are distributed into space. Moreover, the effect of using a limited knowledge that each node possesses about friends of its friends is strongly nonlinear. We show that gains of such use grow statistically significantly only when this knowledge is limited to a small fraction of friends of friends.
Deep Policies for Width-Based Planning in Pixel Domains
Venue: arXiv cs.AI 2021
Year: 2021

Width-based planning has demonstrated great success in recent years due to its ability to scale independently of the size of the state space. For example, Bandres et al. (2018) introduced a rollout version of the Iterated Width algorithm whose performance compares well with humans and learning methods in the pixel setting of the Atari games suite. In this setting, planning is done on-line using the "screen" states and selecting actions by looking ahead into the future. However, this algorithm is purely exploratory and does not leverage past reward information. Furthermore, it requires the state to be factored into features that need to be pre-defined for the particular task, e.g., the B-PROST pixel features. In this work, we extend width-based planning by incorporating an explicit policy in the action selection mechanism. Our method, called $π$-IW, interleaves width-based planning and policy learning using the state-actions visited by the planner. The policy estimate takes the form of a neural network and is in turn used to guide the planning step, thus reinforcing promising paths. Surprisingly, we observe that the representation learned by the neural network can be used as a feature space for the width-based planner without degrading its performance, thus removing the requirement of pre-defined features for the planner. We compare $π$-IW with previous width-based methods and with AlphaZero, a method that also interleaves planning and learning, in simple environments, and show that $π$-IW has superior performance. We also show that $π$-IW algorithm outperforms previous width-based methods in the pixel setting of Atari games suite.
Persistence Curves: A canonical framework for summarizing persistence diagrams
Venue: arXiv cs.CG 2021
Year: 2021

Persistence diagrams are one of the main tools in the field of Topological Data Analysis (TDA). They contain fruitful information about the shape of data. The use of machine learning algorithms on the space of persistence diagrams proves to be challenging as the space lacks an inner product. For that reason, transforming these diagrams in a way that is compatible with machine learning is an important topic currently researched in TDA. In this paper, our main contribution consists of three components. First, we develop a general and unifying framework of vectorizing diagrams that we call the \textit{Persistence Curves} (PCs), and show that several well-known summaries, such as Persistence Landscapes, fall under the PC framework. Second, we propose several new summaries based on PC framework and provide a theoretical foundation for their stability analysis. Finally, we apply proposed PCs to two applications---texture classification and determining the parameters of a discrete dynamical system; their performances are competitive with other TDA methods.
Maximizing Drift is Not Optimal for Solving OneMax
Venue: arXiv cs.NE 2021
Year: 2021

It may seem very intuitive that for the maximization of the OneMax problem $\OM(x):=\sum_{i=1}^n{x_i}$ the best that an elitist unary unbiased search algorithm can do is to store a best so far solution, and to modify it with the operator that yields the best possible expected progress in function value. This assumption has been implicitly used in several empirical works. In [Doerr, Doerr, Yang: Optimal parameter choices via precise black-box analysis, TCS, 2020] it was formally proven that this approach is indeed almost optimal. In this work we prove that drift maximization is not optimal. More precisely, we show that for most fitness levels between $n/2$ and $2n/3$ the optimal mutation strengths are larger than the drift-maximizing ones. This implies that the optimal RLS is more risk-affine than the variant maximizing the step-wise expected progress. We show similar results for the mutation rates of the classic (1+1) Evolutionary Algorithm (EA) and its resampling variant, the (1+1) EA$_{>0}$. As a result of independent interest we show that the optimal mutation strengths, unlike the drift-maximizing ones, can be even.
A new approach for measuring semantic similarity of ontology concepts using dynamic programming
Venue: arXiv cs.CV 2021
Year: 2021

Today, with the emergence of semantic web technologies and increasing of information quantity, searching for information based on the semantic web has become a fertile area of research. For this reason, a large number of studies are performed based on the measure of semantic similarity. Therefore, in this paper, we propose a new method of semantic similarity measuring which uses the dynamic programming to compute the semantic distance between any two concepts defined in the same hierarchy of ontology. Then, we base on this result to compute the semantic similarity. Finally, we present an experimental comparison between our method and other methods of similarity measuring. Where we will show the limits of these methods and how we avoid them with our method. This one bases on a function of weight allocation, which allows finding different rate of semantic similarity between a given concept and two other sibling concepts which is impossible using the other methods.