OpenRaiser/Intern-Atlas huggingface dataset:
Place recognition in gardens by learning visual representations: data set and benchmark analysis
Venue: arXiv cs.CV 2019
Year: 2019

Visual place recognition is an important component of systems for camera localization and loop closure detection. It concerns the recognition of a previously visited place based on visual cues only. Although it is a widely studied problem for indoor and urban environments, the recent use of robots for automation of agricultural and gardening tasks has created new problems, due to the challenging appearance of garden-like environments. Garden scenes predominantly contain green colors, as well as repetitive patterns and textures. The lack of available data recorded in gardens and natural environments makes the improvement of visual localization algorithms difficult. In this paper we propose an extended version of the TB-Places data set, which is designed for testing algorithms for visual place recognition. It contains images with ground truth camera pose recorded in real gardens in different seasons, with varying light conditions. We constructed and released a ground truth for all possible pairs of images, indicating whether they depict the same place or not. We present the results of a benchmark analysis of methods based on convolutional neural networks for holistic image description and place recognition. We train existing networks (i.e. ResNet, DenseNet and VGG NetVLAD) as backbone of a two-way architecture with a contrastive loss function. The results that we obtained demonstrate that learning garden-tailored representations contribute to an improvement of performance, although the generalization capabilities are limited.
Blocking dominating sets for $H$-free graphs via edge contractions
Venue: arXiv cs.DM 2019
Year: 2019

In this paper, we consider the following problem: given a connected graph $G$, can we reduce the domination number of $G$ by one by using only one edge contraction? We show that the problem is $\mathsf{NP}$-hard when restricted to $\{P_6,P_4+P_2\}$-free graphs and that it is $\mathsf{coNP}$-hard when restricted to subcubic claw-free graphs and $2P_3$-free graphs. As a consequence, we are able to establish a complexity dichotomy for the problem on $H$-free graphs when $H$ is connected.
Detecting Feedback Vertex Sets of Size $k$ in $O^\star(2.7^k)$ Time
Venue: arXiv cs.DS 2019
Year: 2019

In the Feedback Vertex Set problem, one is given an undirected graph $G$ and an integer $k$, and one needs to determine whether there exists a set of $k$ vertices that intersects all cycles of $G$ (a so-called feedback vertex set). Feedback Vertex Set is one of the most central problems in parameterized complexity: It served as an excellent test bed for many important algorithmic techniques in the field such as Iterative Compression~[Guo et al. (JCSS'06)], Randomized Branching~[Becker et al. (J. Artif. Intell. Res'00)] and Cut\&Count~[Cygan et al. (FOCS'11)]. In particular, there has been a long race for the smallest dependence $f(k)$ in run times of the type $O^\star(f(k))$, where the $O^\star$ notation omits factors polynomial in $n$. This race seemed to be run in 2011, when a randomized algorithm $O^\star(3^k)$ time algorithm based on Cut\&Count was introduced. In this work, we show the contrary and give a $O^\star(2.7^k)$ time randomized algorithm. Our algorithm combines all mentioned techniques with substantial new ideas: First, we show that, given a feedback vertex set of size $k$ of bounded average degree, a tree decomposition of width $(1-Ω(1))k$ can be found in polynomial time. Second, we give a randomized branching strategy inspired by the one from~[Becker et al. (J. Artif. Intell. Res'00)] to reduce to the aforementioned bounded average degree setting. Third, we obtain significant run time improvements by employing fast matrix multiplication.
Modeling of User Portrait Through Social Media
Venue: arXiv cs.SI 2019
Year: 2019

Nowadays, massive useful data of user information and social behavior have been accumulated on the Internet, providing a possibility of profiling user's personality traits online. In this paper, we propose a psychological modeling method based on computational linguistic features to profile Big Five personality traits of users on Sina Weibo (a Twitter-like microblogging service in China) and their correlations with user's social behaviors. To the best of our knowledge, this is the first research on investigating the potential relationship between profile information, social-network behaviors and personality traits of users on Sina Weibo. Our results demonstrate an effective modeling approach to understanding demographic and psychological portraits of users on social media without customer disruption, which is useful for commercial incorporations to provide better personalized products and services.
State-of-the-Art on Query & Transaction Processing Acceleration
Venue: arXiv cs.DC 2019
Year: 2019

The vast amount of processing power and memory bandwidth provided by modern Graphics Processing Units (GPUs) make them a platform for data-intensive applications. The database community identified GPUs as effective co-processors for data processing. In the past years, there were many approaches to make use of GPUs at different levels of a database system. In this Internal Technical Report, based on the [1] and some other research papers, we identify possible research areas at LIP6 for GPU-accelerated database management systems. We describe some key properties, typical challenges of GPU-aware database architectures, and identify major open challenges.
The Complexity of Tiling Problems
Venue: arXiv cs.CC 2019
Year: 2019

In this document, we collected the most important complexity results of tilings. We also propose a definition of a so-called deterministic set of tile types, in order to capture deterministic classes without the notion of games. We also pinpoint tiling problems complete for respectively LOGSPACE and NLOGSPACE.
Fast Convolutive Nonnegative Matrix Factorization Through Coordinate and Block Coordinate Updates
Venue: arXiv cs.LG 2019
Year: 2019

Identifying recurring patterns in high-dimensional time series data is an important problem in many scientific domains. A popular model to achieve this is convolutive nonnegative matrix factorization (CNMF), which extends classic nonnegative matrix factorization (NMF) to extract short-lived temporal motifs from a long time series. Prior work has typically fit this model by multiplicative parameter updates---an approach widely considered to be suboptimal for NMF, especially in large-scale data applications. Here, we describe how to extend two popular and computationally scalable NMF algorithms---Hierarchical Alternating Least Squares (HALS) and Alternatining Nonnegative Least Squares (ANLS)---for the CNMF model. Both methods demonstrate performance advantages over multiplicative updates on large-scale synthetic and real world data.
GPT-based Generation for Classical Chinese Poetry
Venue: arXiv cs.CL 2019
Year: 2019

We present a simple yet effective method for generating high quality classical Chinese poetry with Generative Pre-trained Language Model (GPT). The method adopts a simple GPT model, without using any human crafted rules or features, or designing any additional neural components. While the proposed model learns to generate various forms of classical Chinese poems, including Jueju, Lüshi, various Cipai and Couples, the generated poems are of very high quality. We also propose and implement a method to fine-tune the model to generate acrostic poetry. To the best of our knowledge, this is the first to employ GPT in developing a poetry generation system. We have released an online mini demonstration program on Wechat to show the generation capability of the proposed method for classical Chinese poetry.
Progressive Fashion Attribute Extraction
Venue: arXiv cs.LG 2019
Year: 2019

Extracting fashion attributes from images of people wearing clothing/fashion accessories is a very hard multi-class classification problem. Most often, even catalogues of fashion do not have all the fine-grained attributes tagged due to prohibitive cost of annotation. Using images of fashion articles, running multi-class attribute extraction with a single model for all kinds of attributes (neck design detailing, sleeves detailing, etc) requires classifiers that are robust to missing and ambiguously labelled data. In this work, we propose a progressive training approach for such multi-class classification, where weights learnt from an attribute are fine tuned for another attribute of the same fashion article (say, dresses). We branch networks for each attributes from a base network progressively during training. While it may have many labels, an image doesn't need to have all possible labels for fashion articles present in it. We also compare our approach to multi-label classification, and demonstrate improvements over overall classification accuracies using our approach.
The Engineering of Software-Defined Quantum Key Distribution Networks
Venue: arXiv cs.NI 2019
Year: 2019

Quantum computers will change the cryptographic panorama. A technology once believed to lay far away into the future is increasingly closer to real world applications. Quantum computers will break the algorithms used in our public key infrastructure and in our key exchange protocols, forcing a complete retooling of the cryptography as we know it. Quantum Key distribution is a physical layer technology immune to quantum or classical computational threats. However, it requires a physical substrate, and optical fiber has been the usual choice. Most of the time used just as a point to point link for the exclusive transport of the delicate quantum signals. Its integration in a real-world shared network has not been attempted so far. Here we show how the new programmable software network architectures, together with specially designed quantum systems can be used to produce a network that integrates classical and quantum communications, including management, in a single, production-level infrastructure. The network can also incorporate new quantum-safe algorithms and use the existing security protocols, thus bridging the gap between today's network security and the quantum-safe network of the future. This can be done in an evolutionary way, without zero-day migrations and the corresponding upfront costs. We also present how the technologies have been deployed in practice using a production network.
Continual Learning for Robotics: Definition, Framework, Learning Strategies, Opportunities and Challenges
Venue: arXiv cs.LG 2019
Year: 2019

Continual learning (CL) is a particular machine learning paradigm where the data distribution and learning objective changes through time, or where all the training data and objective criteria are never available at once. The evolution of the learning process is modeled by a sequence of learning experiences where the goal is to be able to learn new skills all along the sequence without forgetting what has been previously learned. Continual learning also aims at the same time at optimizing the memory, the computation power and the speed during the learning process. An important challenge for machine learning is not necessarily finding solutions that work in the real world but rather finding stable algorithms that can learn in real world. Hence, the ideal approach would be tackling the real world in a embodied platform: an autonomous agent. Continual learning would then be effective in an autonomous agent or robot, which would learn autonomously through time about the external world, and incrementally develop a set of complex skills and knowledge. Robotic agents have to learn to adapt and interact with their environment using a continuous stream of observations. Some recent approaches aim at tackling continual learning for robotics, but most recent papers on continual learning only experiment approaches in simulation or with static datasets. Unfortunately, the evaluation of those algorithms does not provide insights on whether their solutions may help continual learning in the context of robotics. This paper aims at reviewing the existing state of the art of continual learning, summarizing existing benchmarks and metrics, and proposing a framework for presenting and evaluating both robotics and non robotics approaches in a way that makes transfer between both fields easier.
Open-MPI over MOSIX: paralleled computing in a clustered world
Venue: arXiv cs.DC 2019
Year: 2019

Recent increased interest in Cloud computing emphasizes the need to find an adequate solution to the load-balancing problem in parallel computing -- efficiently running several jobs concurrently on a cluster of shared computers (nodes). One approach to solve this problem is by preemptive process migration -- the transfer of running processes between nodes. A possible drawback of this approach is the increased overhead between heavily communicating processes. This project presents a solution to this last problem by incorporating the process migration capability of MOSIX into Open-MPI and by reducing the resulting communication overhead. Specifically, we developed a module for direct communication (DiCOM) between migrated Open-MPI processes, to overcome the increased communication latency of TCP/IP between such processes. The outcome is reduced run-time by improved resource allocation.
Learning Where to Look While Tracking Instruments in Robot-assisted Surgery
Venue: arXiv cs.CV 2019
Year: 2019

Directing of the task-specific attention while tracking instrument in surgery holds great potential in robot-assisted intervention. For this purpose, we propose an end-to-end trainable multitask learning (MTL) model for real-time surgical instrument segmentation and attention prediction. Our model is designed with a weight-shared encoder and two task-oriented decoders and optimized for the joint tasks. We introduce batch-Wasserstein (bW) loss and construct a soft attention module to refine the distinctive visual region for efficient saliency learning. For multitask optimization, it is always challenging to obtain convergence of both tasks in the same epoch. We deal with this problem by adopting `poly' loss weight and two phases of training. We further propose a novel way to generate task-aware saliency map and scanpath of the instruments on MICCAI robotic instrument segmentation dataset. Compared to the state of the art segmentation and saliency models, our model outperforms most of the evaluation metrics.
Quadrilateral Mesh Generation II : Meromorphic Quartic Differentials and Abel-Jacobi Condition
Venue: arXiv cs.CG 2019
Year: 2019

This work discovers the equivalence relation between quadrilateral meshes and meromorphic quartic. Each quad-mesh induces a conformal structure of the surface, and a meromorphic differential, where the configuration of singular vertices correspond to the configurations the poles and zeros (divisor) of the meroromorphic differential. Due to Riemann surface theory, the configuration of singularities of a quad-mesh satisfies the Abel-Jacobi condition. Inversely, if a satisfies the Abel-Jacobi condition, then there exists a meromorphic quartic differential whose equals to the given one. Furthermore, if the meromorphic quadric differential is with finite, then it also induces a a quad-mesh, the poles and zeros of the meromorphic differential to the singular vertices of the quad-mesh. Besides the theoretic proofs, the computational algorithm for verification of Abel-Jacobi condition is explained in details. Furthermore, constructive algorithm of meromorphic quartic differential on zero surfaces is proposed, which is based on the global algebraic representation of meromorphic. Our experimental results demonstrate the efficiency and efficacy of the algorithm. This opens up a direction for quad-mesh generation using algebraic geometric approach.
Predicting Social Perception from Faces: A Deep Learning Approach
Venue: arXiv cs.CV 2019
Year: 2019

Warmth and competence represent the fundamental traits in social judgment that determine emotional reactions and behavioral intentions towards social targets. This research investigates whether an algorithm can learn visual representations of social categorization and accurately predict human perceivers' impressions of warmth and competence in face images. In addition, this research unravels which areas of a face are important for the classification of warmth and competence. We use Deep Convolutional Neural Networks to extract features from face images and the Gradient-weighted Class Activation Mapping (Grad CAM) method to understand the importance of face regions for the classification. Given a single face image the trained algorithm could correctly predict warmth impressions with an accuracy of about 90% and competence impressions with an accuracy of about 80%. The findings have implications for the automated processing of faces and the design of artificial characters.
Isomorphism problems for tensors, groups, and cubic forms: completeness and reductions
Venue: arXiv cs.CC 2019
Year: 2019

In this paper we consider the problems of testing isomorphism of tensors, $p$-groups, cubic forms, algebras, and more, which arise from a variety of areas, including machine learning, group theory, and cryptography. These problems can all be cast as orbit problems on multi-way arrays under different group actions. Our first two main results are: 1. All the aforementioned isomorphism problems are equivalent under polynomial-time reductions, in conjunction with the recent results of Futorny-Grochow-Sergeichuk (Lin. Alg. Appl., 2019). 2. Isomorphism of $d$-tensors reduces to isomorphism of 3-tensors, for any $d \geq 3$. Our results suggest that these isomorphism problems form a rich and robust equivalence class, which we call Tensor Isomorphism-complete, or TI-complete. We then leverage the techniques used in the above results to prove two first-of-their-kind results for Group Isomorphism (GpI): 3. We give a reduction from GpI for $p$-groups of exponent $p$ and small class ($c < p$) to GpI for $p$-groups of exponent $p$ and class 2. The latter are widely believed to be the hardest cases of GpI, but as far as we know, this is the first reduction from any more general class of groups to this class. 4. We give a search-to-decision reduction for isomorphism of $p$-groups of exponent $p$ and class 2 in time $|G|^{O(\log \log |G|)}$. While search-to-decision reductions for Graph Isomorphism (GI) have been known for more than 40 years, as far as we know this is the first non-trivial search-to-decision reduction in the context of GpI. Our main technique for (1), (3), and (4) is a linear-algebraic analogue of the classical graph coloring gadget, which was used to obtain the search-to-decision reduction for GI. This gadget construction may be of independent interest and utility. The technique for (2) gives a method for encoding an arbitrary tensor into an algebra.
Visual Space Optimization for Zero-shot Learning
Venue: arXiv cs.CV 2019
Year: 2019

Zero-shot learning, which aims to recognize new categories that are not included in the training set, has gained popularity owing to its potential ability in the real-word applications. Zero-shot learning models rely on learning an embedding space, where both semantic descriptions of classes and visual features of instances can be embedded for nearest neighbor search. Recently, most of the existing works consider the visual space formulated by deep visual features as an ideal choice of the embedding space. However, the discrete distribution of instances in the visual space makes the data structure unremarkable. We argue that optimizing the visual space is crucial as it allows semantic vectors to be embedded into the visual space more effectively. In this work, we propose two strategies to accomplish this purpose. One is the visual prototype based method, which learns a visual prototype for each visual class, so that, in the visual space, a class can be represented by a prototype feature instead of a series of discrete visual features. The other is to optimize the visual feature structure in an intermediate embedding space, and in this method we successfully devise a multilayer perceptron framework based algorithm that is able to learn the common intermediate embedding space and meanwhile to make the visual data structure more distinctive. Through extensive experimental evaluation on four benchmark datasets, we demonstrate that optimizing visual space is beneficial for zero-shot learning. Besides, the proposed prototype based method achieves the new state-of-the-art performance.
Reinforcement Learning for Robotic Time-optimal Path Tracking Using Prior Knowledge
Venue: arXiv cs.RO 2019
Year: 2019

Time-optimal path tracking, as a significant tool for industrial robots, has attracted the attention of numerous researchers. In most time-optimal path tracking problems, the actuator torque constraints are assumed to be conservative, which ignores the motor characteristic; i.e., the actuator torque constraints are velocity-dependent, and the relationship between torque and velocity is piecewise linear. However, considering that the motor characteristics increase the solving difficulty, in this study, an improved Q-learning algorithm for robotic time-optimal path tracking using prior knowledge is proposed. After considering the limitations of the Q-learning algorithm, an improved action-value function is proposed to improve the convergence rate. The proposed algorithms use the idea of reward and penalty, rewarding the actions that satisfy constraint conditions and penalizing the actions that break constraint conditions, to finally obtain a time-optimal trajectory that satisfies the constraint conditions. The effectiveness of the algorithms is verified by experiments.
Typed lambda-calculi and superclasses of regular functions
Venue: arXiv cs.LO 2019
Year: 2019

We propose to use Church encodings in typed lambda-calculi as the basis for an automata-theoretic counterpart of implicit computational complexity, in the same way that monadic second-order logic provides a counterpart to descriptive complexity. Specifically, we look at transductions i.e. string-to-string (or tree-to-tree) functions - in particular those with superlinear growth, such as polyregular functions, HDT0L transductions and Sénizergues's "k-computable mappings". Our first results towards this aim consist showing the inclusion of some transduction classes in some classes defined by lambda-calculi. In particular, this sheds light on a basic open question on the expressivity of the simply typed lambda-calculus. We also encode regular functions (and, by changing the type of programs considered, we get a larger subclass of polyregular functions) in the elementary affine lambda-calculus, a variant of linear logic originally designed for implicit computational complexity.