OpenRaiser/Intern-Atlas huggingface dataset:
Multi-Modal Deep Clustering: Unsupervised Partitioning of Images
Venue: arXiv cs.CV 2020
Year: 2020

The clustering of unlabeled raw images is a daunting task, which has recently been approached with some success by deep learning methods. Here we propose an unsupervised clustering framework, which learns a deep neural network in an end-to-end fashion, providing direct cluster assignments of images without additional processing. Multi-Modal Deep Clustering (MMDC), trains a deep network to align its image embeddings with target points sampled from a Gaussian Mixture Model distribution. The cluster assignments are then determined by mixture component association of image embeddings. Simultaneously, the same deep network is trained to solve an additional self-supervised task of predicting image rotations. This pushes the network to learn more meaningful image representations that facilitate a better clustering. Experimental results show that MMDC achieves or exceeds state-of-the-art performance on six challenging benchmarks. On natural image datasets we improve on previous results with significant margins of up to 20% absolute accuracy points, yielding an accuracy of 82% on CIFAR-10, 45% on CIFAR-100 and 69% on STL-10.
Measuring Social Bias in Knowledge Graph Embeddings
Venue: arXiv cs.CL 2020
Year: 2020

It has recently been shown that word embeddings encode social biases, with a harmful impact on downstream tasks. However, to this point there has been no similar work done in the field of graph embeddings. We present the first study on social bias in knowledge graph embeddings, and propose a new metric suitable for measuring such bias. We conduct experiments on Wikidata and Freebase, and show that, as with word embeddings, harmful social biases related to professions are encoded in the embeddings with respect to gender, religion, ethnicity and nationality. For example, graph embeddings encode the information that men are more likely to be bankers, and women more likely to be homekeepers. As graph embeddings become increasingly utilized, we suggest that it is important the existence of such biases are understood and steps taken to mitigate their impact.
Learning to Correspond Dynamical Systems
Venue: arXiv cs.LG 2020
Year: 2020

Many dynamical systems exhibit similar structure, as often captured by hand-designed simplified models that can be used for analysis and control. We develop a method for learning to correspond pairs of dynamical systems via a learned latent dynamical system. Given trajectory data from two dynamical systems, we learn a shared latent state space and a shared latent dynamics model, along with an encoder-decoder pair for each of the original systems. With the learned correspondences in place, we can use a simulation of one system to produce an imagined motion of its counterpart. We can also simulate in the learned latent dynamics and synthesize the motions of both corresponding systems, as a form of bisimulation. We demonstrate the approach using pairs of controlled bipedal walkers, as well as by pairing a walker with a controlled pendulum.
Parameterized Complexity of Partial Scheduling
Venue: arXiv cs.DS 2020
Year: 2020

We study a natural variant of scheduling that we call \emph{partial scheduling}: In this variant an instance of a scheduling problem along with an integer $k$ is given and one seeks an optimal schedule where not all, but only $k$ jobs, have to be processed. Specifically, we aim to determine the fine-grained parameterized complexity of partial scheduling problems parameterized by $k$ for all variants of scheduling problems that minimize the makespan and involve unit/arbitrary processing times, identical/unrelated parallel machines, release/due dates, and precedence constraints. That is, we investigate whether algorithms with runtimes of the type $f(k)n^{\mathcal{O}(1)}$ or $n^{\mathcal{O}(f(k))}$ exist for a function $f$ that is as small as possible. Our contribution is two-fold: First, we categorize each variant to be either in $\mathsf{P}$, $\mathsf{NP}$-complete and fixed-parameter tractable by $k$, or $\mathsf{W}[1]$-hard parameterized by $k$. Second, for many interesting cases we further investigate the run time on a finer scale and obtain run times that are (almost) optimal assuming the Exponential Time Hypothesis. As one of our main technical contributions, we give an $\mathcal{O}(8^kk(|V|+|E|))$ time algorithm to solve instances of partial scheduling problems minimizing the makespan with unit length jobs, precedence constraints and release dates, where $G=(V,E)$ is the graph with precedence constraints.
Differentially Private Synthetic Mixed-Type Data Generation For Unsupervised Learning
Venue: arXiv cs.LG 2020
Year: 2020

We introduce the DP-auto-GAN framework for synthetic data generation, which combines the low dimensional representation of autoencoders with the flexibility of Generative Adversarial Networks (GANs). This framework can be used to take in raw sensitive data and privately train a model for generating synthetic data that will satisfy similar statistical properties as the original data. This learned model can generate an arbitrary amount of synthetic data, which can then be freely shared due to the post-processing guarantee of differential privacy. Our framework is applicable to unlabeled mixed-type data, that may include binary, categorical, and real-valued data. We implement this framework on both binary data (MIMIC-III) and mixed-type data (ADULT), and compare its performance with existing private algorithms on metrics in unsupervised settings. We also introduce a new quantitative metric able to detect diversity, or lack thereof, of synthetic data.
Tools for Mathematical Ludology
Venue: arXiv cs.AI 2020
Year: 2020

We propose the study of mathematical ludology, which aims to formally interrogate questions of interest to game studies and game design in particular. The goal is to extend our mathematical understanding of complex games beyond decision-making---the typical focus of game theory and artificial intelligence efforts---to explore other aspects such as game mechanics, structure, relationships between games, and connections between game rules and user-interfaces, as well as exploring related gameplay phenomena and typical player behavior. In this paper, we build a basic foundation for this line of study by developing a hierarchy of game descriptions, mathematical formalism to compactly describe complex discrete games, and equivalence relations on the space of game systems.
Phase Portraits as Movement Primitives for Fast Humanoid Robot Control
Venue: arXiv cs.RO 2020
Year: 2020

Currently, usual approaches for fast robot control are largely reliant on solving online optimal control problems. Such methods are known to be computationally intensive and sensitive to model accuracy. On the other hand, animals plan complex motor actions not only fast but seemingly with little effort even on unseen tasks. This natural sense to infer temporal dynamics and coordination motivates us to approach robot control from a motor skill learning perspective to design fast and computationally light controllers that can be learned autonomously by the robot under mild modeling assumptions. This article introduces Phase Portrait Movement Primitives (PPMP), a primitive that predicts dynamics on a low dimensional phase space which in turn is used to govern the high dimensional kinematics of the task. The stark difference with other primitive formulations is a built-in mechanism for phase prediction in the form of coupled oscillators that replaces model-based state estimators such as Kalman filters. The policy is trained by optimizing the parameters of the oscillators whose output is connected to a kinematic distribution in the form of a phase portrait. The drastic reduction in dimensionality allows us to efficiently train and execute PPMPs on a real human-sized, dual-arm humanoid upper body on a task involving 20 degrees-of-freedom. We demonstrate PPMPs in interactions requiring fast reactions times while generating anticipative pose adaptation in both discrete and cyclic tasks.
Feature Augmentation Improves Anomalous Change Detection for Human Activity Identification in Synthetic Aperture Radar Imagery
Venue: arXiv cs.CV 2020
Year: 2020

Anomalous change detection (ACD) methods separate common, uninteresting changes from rare, significant changes in co-registered images collected at different points in time. In this paper we evaluate methods to improve the performance of ACD in detecting human activity in SAR imagery using outdoor music festivals as a target. Our results show that the low dimensionality of SAR data leads to poor performance of ACD when compared to simpler methods such as image differencing, but augmenting the dimensionality of our input feature space by incorporating local spatial information leads to enhanced performance.
Bidirectional Scene Text Recognition with a Single Decoder
Venue: arXiv cs.CV 2020
Year: 2020

Scene Text Recognition (STR) is the problem of recognizing the correct word or character sequence in a cropped word image. To obtain more robust output sequences, the notion of bidirectional STR has been introduced. So far, bidirectional STRs have been implemented by using two separate decoders; one for left-to-right decoding and one for right-to-left. Having two separate decoders for almost the same task with the same output space is undesirable from a computational and optimization point of view. We introduce the bidirectional Scene Text Transformer (Bi-STET), a novel bidirectional STR method with a single decoder for bidirectional text decoding. With its single decoder, Bi-STET outperforms methods that apply bidirectional decoding by using two separate decoders while also being more efficient than those methods, Furthermore, we achieve or beat state-of-the-art (SOTA) methods on all STR benchmarks with Bi-STET. Finally, we provide analyses and insights into the performance of Bi-STET.
Adaptive Trajectory Estimation with Power Limited Steering Model under Perturbation Compensation
Venue: arXiv cs.IT 2020
Year: 2020

Trajectory estimation of maneuvering objects is applied in numerous tasks like navigation, path planning and visual tracking. Many previous works get impressive results in the strictly controlled condition with accurate prior statistics and dedicated dynamic model for certain object. But in challenging conditions without dedicated dynamic model and precise prior statistics, the performance of these methods significantly declines. To solve the problem, a dynamic model called the power-limited steering model (PLS) is proposed to describe the motion of non-cooperative object. It is a natural combination of instantaneous power and instantaneous angular velocity, which relies on the nonlinearity instead of the state switching probability to achieve switching of states. And the renormalization group is introduced to compensate the nonlinear effect of perturbation in PLS model. For robust and efficient trajectory estimation, an adaptive trajectory estimation (AdaTE) algorithm is proposed. By updating the statistics and truncation time online, it corrects the estimation error caused by biased prior statistics and observation drift, while reducing the computational complexity lower than O(n). The experiment of trajectory estimation demonstrates the convergence of AdaTE, and the better robust to the biased prior statistics and the observation drift compared with EKF, UKF and sparse MAP. Other experiments demonstrate through slight modification, AdaTE can also be applied to local navigation in random obstacle environment, and trajectory optimization in visual tracking.
Voxel2Mesh: 3D Mesh Model Generation from Volumetric Data
Venue: arXiv cs.CV 2020
Year: 2020

CNN-based volumetric methods that label individual voxels now dominate the field of biomedical segmentation. However, 3D surface representations are often required for proper analysis. They can be obtained by post-processing the labeled volumes which typically introduces artifacts and prevents end-to-end training. In this paper, we therefore introduce a novel architecture that goes directly from 3D image volumes to 3D surfaces without post-processing and with better accuracy than current methods. We evaluate it on Electron Microscopy and MRI brain images as well as CT liver scans. We will show that it outperforms state-of-the-art segmentation methods.
CNN-based Lidar Point Cloud De-Noising in Adverse Weather
Venue: arXiv cs.CV 2020
Year: 2020

Lidar sensors are frequently used in environment perception for autonomous vehicles and mobile robotics to complement camera, radar, and ultrasonic sensors. Adverse weather conditions are significantly impacting the performance of lidar-based scene understanding by causing undesired measurement points that in turn effect missing detections and false positives. In heavy rain or dense fog, water drops could be misinterpreted as objects in front of the vehicle which brings a mobile robot to a full stop. In this paper, we present the first CNN-based approach to understand and filter out such adverse weather effects in point cloud data. Using a large data set obtained in controlled weather environments, we demonstrate a significant performance improvement of our method over state-of-the-art involving geometric filtering. Data is available at https://github.com/rheinzler/PointCloudDeNoising.
AI2D-RST: A multimodal corpus of 1000 primary school science diagrams
Venue: arXiv cs.CL 2020
Year: 2020

This article introduces AI2D-RST, a multimodal corpus of 1000 English-language diagrams that represent topics in primary school natural sciences, such as food webs, life cycles, moon phases and human physiology. The corpus is based on the Allen Institute for Artificial Intelligence Diagrams (AI2D) dataset, a collection of diagrams with crowd-sourced descriptions, which was originally developed to support research on automatic diagram understanding and visual question answering. Building on the segmentation of diagram layouts in AI2D, the AI2D-RST corpus presents a new multi-layer annotation schema that provides a rich description of their multimodal structure. Annotated by trained experts, the layers describe (1) the grouping of diagram elements into perceptual units, (2) the connections set up by diagrammatic elements such as arrows and lines, and (3) the discourse relations between diagram elements, which are described using Rhetorical Structure Theory (RST). Each annotation layer in AI2D-RST is represented using a graph. The corpus is freely available for research and teaching.
Sequential Model Optimization for Software Process Control
Venue: arXiv cs.SE 2020
Year: 2020

Many methods have been proposed to estimate how much effort is required to build and maintain software. Much of that research assumes a ``classic'' waterfall-based approach rather than contemporary projects (where the developing process may be more iterative than linear in nature). Also, much of that work tries to recommend a single method-- an approach that makes the dubious assumption that one method can handle the diversity of software project data. To address these drawbacks, we apply a configuration technique called ``ROME'' (Rapid Optimizing Methods for Estimation), which uses sequential model-based optimization (SMO) to find what combination of effort estimation techniques works best for a particular data set. We test this method using data from 1161 classic waterfall projects and 120 contemporary projects (from Github). In terms of magnitude of relative error and standardized accuracy, we find that ROME achieves better performance than existing state-of-the-art methods for both classic and contemporary problems. In addition, we conclude that we should not recommend one method for estimation. Rather, it is better to search through a wide range of different methods to find what works best for local data. To the best of our knowledge, this is the largest effort estimation experiment yet attempted and the only one to test its methods on classic and contemporary projects.
A Deterministic Algorithm for the MST Problem in Constant Rounds of Congested Clique
Venue: arXiv cs.DS 2020
Year: 2020

In this paper, we show that the Minimum Spanning Tree problem can be solved \emph{deterministically}, in $\mathcal{O}(1)$ rounds of the $\mathsf{Congested}$ $\mathsf{Clique}$ model. In the $\mathsf{Congested}$ $\mathsf{Clique}$ model, there are $n$ players that perform computation in synchronous rounds. Each round consist of a phase of local computation and a phase of communication, in which each pair of players is allowed to exchange $\mathcal{O}(\log n)$ bit messages. The studies of this model began with the MST problem: in the paper by Lotker et al.[SPAA'03, SICOMP'05] that defines the $\mathsf{Congested}$ $\mathsf{Clique}$ model the authors give a deterministic $\mathcal{O}(\log \log n)$ round algorithm that improved over a trivial $\mathcal{O}(\log n)$ round adaptation of Borůvka's algorithm. There was a sequence of gradual improvements to this result: an $\mathcal{O}(\log \log \log n)$ round algorithm by Hegeman et al. [PODC'15], an $\mathcal{O}(\log^* n)$ round algorithm by Ghaffari and Parter, [PODC'16] and an $\mathcal{O}(1)$ round algorithm by Jurdziński and Nowicki, [SODA'18], but all those algorithms were randomized, which left the question about the existence of any deterministic $o(\log \log n)$ round algorithms for the Minimum Spanning Tree problem open. Our result resolves this question and establishes that $\mathcal{O}(1)$ rounds is enough to solve the MST problem in the $\mathsf{Congested}$ $\mathsf{Clique}$ model, even if we are not allowed to use any randomness. Furthermore, the amount of communication needed by the algorithm makes it applicable to some variants of the $\mathsf{MPC}$ model.
Cascaded Structure Tensor Framework for Robust Identification of Heavily Occluded Baggage Items from Multi-Vendor X-ray Scans
Venue: arXiv cs.CV 2020
Year: 2020

In the last two decades, luggage scanning has globally become one of the prime aviation security concerns. Manual screening of the baggage items is a cumbersome, subjective and inefficient process. Hence, many researchers have developed Xray imagery-based autonomous systems to address these shortcomings. However, to the best of our knowledge, there is no framework, up to now, that can recognize heavily occluded and cluttered baggage items from multi-vendor X-ray scans. This paper presents a cascaded structure tensor framework which can automatically extract and recognize suspicious items irrespective of their position and orientation in the multi-vendor X-ray scans. The proposed framework is unique, as it intelligently extracts each object by iteratively picking contour based transitional information from different orientations and uses only a single feedforward convolutional neural network for the recognition. The proposed framework has been rigorously tested on publicly available GDXray and SIXray datasets containing a total of 1,067,381 X-ray scans where it significantly outperformed the state-of-the-art solutions by achieving the mean average precision score of 0.9343 and 0.9595 for extracting and recognizing suspicious items from GDXray and SIXray scans, respectively. Furthermore, the proposed framework has achieved 15.78% better time
An Empirical Study on Position of the Batch Normalization Layer in Convolutional Neural Networks
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we have studied how the training of the convolutional neural networks (CNNs) can be affected by changing the position of the batch normalization (BN) layer. Three different convolutional neural networks have been chosen for our experiments. These networks are AlexNet, VGG-16, and ResNet- 20. We show that the speed up in training provided by the BN algorithm can be improved by using other positions for the BN layer than the one suggested by its original paper. Also, we discuss how the BN layer in a certain position can aid the training of one network but not the other. Three different positions for the BN layer have been studied in this research. These positions are: the BN layer between the convolution layer and the non-linear activation function, the BN layer after the non-linear activation function and finally, the BN layer before each of the convolutional layers.
Toward Personalized XAI: A Case Study in Intelligent Tutoring Systems
Venue: arXiv cs.AI 2020
Year: 2020

Our research is a step toward ascertaining the need for personalization, in XAI, and we do so in the context of investigating the value of explanations of AI-driven hints and feedback are useful in Intelligent Tutoring Systems (ITS). We added an explanation functionality for the adaptive hints provided by the Adaptive CSP (ACSP) applet, an interactive simulation that helps students learn an algorithm for constraint satisfaction problems by providing AI-driven hints adapted to their predicted level of learning. We present the design of the explanation functionality and the results of a controlled study to evaluate its impact on students' learning and perception of the ACPS hints. The study includes an analysis of how these outcomes are modulated by several user characteristics such as personality traits and cognitive abilities, to asses if explanations should be personalized to these characteristics. Our results indicate that providing explanations increase students' trust in the ACPS hints, perceived usefulness of the hints, and intention to use them again. In addition, we show that students' access of the explanation and learning gains are modulated by user characteristics, providing insights toward designing personalized Explainable AI (XAI) for ITS.
SoccerDB: A Large-Scale Database for Comprehensive Video Understanding
Venue: arXiv cs.CV 2020
Year: 2020

Soccer videos can serve as a perfect research object for video understanding because soccer games are played under well-defined rules while complex and intriguing enough for researchers to study. In this paper, we propose a new soccer video database named SoccerDB, comprising 171,191 video segments from 346 high-quality soccer games. The database contains 702,096 bounding boxes, 37,709 essential event labels with time boundary and 17,115 highlight annotations for object detection, action recognition, temporal action localization, and highlight detection tasks. To our knowledge, it is the largest database for comprehensive sports video understanding on various aspects. We further survey a collection of strong baselines on SoccerDB, which have demonstrated state-of-the-art performances on independent tasks. Our evaluation suggests that we can benefit significantly when jointly considering the inner correlations among those tasks. We believe the release of SoccerDB will tremendously advance researches around comprehensive video understanding. {\itshape Our dataset and code published on https://github.com/newsdata/SoccerDB.}
On the Complexity of Modulo-q Arguments and the Chevalley-Warning Theorem
Venue: arXiv cs.CC 2020
Year: 2020

We study the search problem class $\mathrm{PPA}_q$ defined as a modulo-$q$ analog of the well-known $\textit{polynomial parity argument}$ class $\mathrm{PPA}$ introduced by Papadimitriou '94. Our first result shows that this class can be characterized in terms of $\mathrm{PPA}_p$ for prime $p$. Our main result is to establish that an $\textit{explicit}$ version of a search problem associated to the Chevalley--Warning theorem is complete for $\mathrm{PPA}_p$ for prime $p$. This problem is $\textit{natural}$ in that it does not explicitly involve circuits as part of the input. It is the first such complete problem for $\mathrm{PPA}_p$ when $p \ge 3$. Finally we discuss connections between Chevalley-Warning theorem and the well-studied $\textit{short integer solution}$ problem and survey the structural properties of $\mathrm{PPA}_q$.