OpenRaiser/Intern-Atlas huggingface dataset:
Reconstructing Perceived Images from Brain Activity by Visually-guided Cognitive Representation and Adversarial Learning
Venue: arXiv cs.CV 2019
Year: 2019

Reconstructing visual stimulus (image) only from human brain activity measured with functional Magnetic Resonance Imaging (fMRI) is a significant and meaningful task in Human-AI collaboration. However, the inconsistent distribution and representation between fMRI signals and visual images cause the heterogeneity gap. Moreover, the fMRI data is often extremely high-dimensional and contains a lot of visually-irrelevant information. Existing methods generally suffer from these issues so that a satisfactory reconstruction is still challenging. In this paper, we show that it is possible to overcome these challenges by learning visually-guided cognitive latent representations from the fMRI signals, and inversely decoding them to the image stimuli. The resulting framework is called Dual-Variational Autoencoder/ Generative Adversarial Network (D-VAE/GAN), which combines the advantages of adversarial representation learning with knowledge distillation. In addition, we introduce a novel three-stage learning approach which enables the (cognitive) encoder to gradually distill useful knowledge from the paired (visual) encoder during the learning process. Extensive experimental results on both artificial and natural images have demonstrated that our method could achieve surprisingly good results and outperform all other alternatives.
A Deep Decoder Structure Based on WordEmbedding Regression for An Encoder-Decoder Based Model for Image Captioning
Venue: arXiv cs.CV 2019
Year: 2019

Generating textual descriptions for images has been an attractive problem for the computer vision and natural language processing researchers in recent years. Dozens of models based on deep learning have been proposed to solve this problem. The existing approaches are based on neural encoder-decoder structures equipped with the attention mechanism. These methods strive to train decoders to minimize the log likelihood of the next word in a sentence given the previous ones, which results in the sparsity of the output space. In this work, we propose a new approach to train decoders to regress the word embedding of the next word with respect to the previous ones instead of minimizing the log likelihood. The proposed method is able to learn and extract long-term information and can generate longer fine-grained captions without introducing any external memory cell. Furthermore, decoders trained by the proposed technique can take the importance of the generated words into consideration while generating captions. In addition, a novel semantic attention mechanism is proposed that guides attention points through the image, taking the meaning of the previously generated word into account. We evaluate the proposed approach with the MS-COCO dataset. The proposed model outperformed the state of the art models especially in generating longer captions. It achieved a CIDEr score equal to 125.0 and a BLEU-4 score equal to 50.5, while the best scores of the state of the art models are 117.1 and 48.0, respectively.
Computing Haar Measures
Venue: arXiv cs.LO 2019
Year: 2019

According to Haar's Theorem, every compact group $G$ admits a unique (regular, right and) left-invariant Borel probability measure $μ_G$. Let the Haar integral (of $G$) denote the functional $\int_G:\mathcal{C}(G)\ni f\mapsto \int f\,dμ_G$ integrating any continuous function $f:G\to\mathbb{R}$ with respect to $μ_G$. This generalizes, and recovers for the additive group $G=[0;1)\mod 1$, the usual Riemann integral: computable (cmp. Weihrauch 2000, Theorem 6.4.1), and of computational cost characterizing complexity class #P$_1$ (cmp. Ko 1991, Theorem 5.32). We establish that in fact every computably compact computable metric group renders the Haar integral computable: once asserting computability using an elegant synthetic argument, exploiting uniqueness in a computably compact space of probability measures; and once presenting and analyzing an explicit, imperative algorithm based on 'maximum packings' with rigorous error bounds and guaranteed convergence. Regarding computational complexity, for the groups $\mathcal{SO}(3)$ and $\mathcal{SU}(2)$ we reduce the Haar integral to and from Euclidean/Riemann integration. In particular both also characterize #P$_1$. Implementation and empirical evaluation using the iRRAM C++ library for exact real computation confirms the (thus necessary) exponential runtime.
L*-Based Learning of Markov Decision Processes (Extended Version)
Venue: arXiv cs.LG 2019
Year: 2019

Automata learning techniques automatically generate system models from test observations. These techniques usually fall into two categories: passive and active. Passive learning uses a predetermined data set, e.g., system logs. In contrast, active learning actively queries the system under learning, which is considered more efficient. An influential active learning technique is Angluin's L* algorithm for regular languages which inspired several generalisations from DFAs to other automata-based modelling formalisms. In this work, we study L*-based learning of deterministic Markov decision processes, first assuming an ideal setting with perfect information. Then, we relax this assumption and present a novel learning algorithm that collects information by sampling system traces via testing. Experiments with the implementation of our sampling-based algorithm suggest that it achieves better accuracy than state-of-the-art passive learning techniques with the same amount of test data. Unlike existing learning algorithms with predefined states, our algorithm learns the complete model structure including the states.
Accurate Robotic Pouring for Serving Drinks
Venue: arXiv cs.RO 2019
Year: 2019

Pouring is the second most frequently executed motion in cooking scenarios. In this work, we present our system of accurate pouring that generates the angular velocities of the source container using recurrent neural networks. We collected demonstrations of human pouring water. We made a physical system on which the velocities of the source container were generated at each time step and executed by a motor. We tested our system on pouring water from containers that are not used for training and achieved an error of as low as 4 milliliters. We also used the system to pour oil and syrup. The accuracy achieved with oil is slightly lower than but comparable with that of water.
Growing Action Spaces
Venue: arXiv cs.LG 2019
Year: 2019

In complex tasks, such as those with large combinatorial action spaces, random exploration may be too inefficient to achieve meaningful learning progress. In this work, we use a curriculum of progressively growing action spaces to accelerate learning. We assume the environment is out of our control, but that the agent may set an internal curriculum by initially restricting its action space. Our approach uses off-policy reinforcement learning to estimate optimal value functions for multiple action spaces simultaneously and efficiently transfers data, value estimates, and state representations from restricted action spaces to the full task. We show the efficacy of our approach in proof-of-concept control tasks and on challenging large-scale StarCraft micromanagement tasks with large, multi-agent action spaces.
Motion Prediction with Recurrent Neural Network Dynamical Models and Trajectory Optimization
Venue: arXiv cs.RO 2019
Year: 2019

Predicting human motion in unstructured and dynamic environments is difficult as humans naturally exhibit complex behaviors that can change drastically from one environment to the next. In order to alleviate this issue, we propose to encode the lower level aspects of human motion separately from the higher level geometrical aspects, which we believe will generalize better over environments. In contrast to our prior work~\cite{kratzer2018}, we encode the short-term behavior by using a state-of-the-art recurrent neural network structure instead of a Gaussian process. In order to perform longer-term behavior predictions that account for variation in tasks and environments, we propose to make use of gradient-based trajectory optimization. Preliminary experiments on real motion data demonstrate the efficacy of the approach.
RecurSIA-RRT: Recursive translatable point-set pattern discovery with removal of redundant translators
Venue: arXiv cs.LG 2019
Year: 2019

We introduce two algorithms, RECURSIA and RRT, designed to increase the compression factor achievable using point-set cover algorithms based on the SIA and SIATEC pattern discovery algorithms. SIA computes the maximal translatable patterns (MTPs) in a point set, while SIATEC computes the translational equivalence class (TEC) of every MTP in a point set, where the TEC of an MTP is the set of translationally invariant occurrences of that MTP in the point set. In its output, SIATEC encodes each MTP TEC as a pair, <P,V>, where P is the first occurrence of the MTP and V is the set of non-zero vectors that map P onto its other occurrences. RECURSIA recursively applies a TEC cover algorithm to the pattern P, in each TEC, <P,V>, that it discovers. RRT attempts to remove translators from V in each TEC without reducing the total set of points covered by the TEC. When evaluated with COSIATEC, SIATECCompress and Forth's algorithm on the JKU Patterns Development Database, using RECURSIA with or without RRT increased compression factor and recall but reduced precision. Using RRT alone increased compression factor and reduced recall and precision, but had a smaller effect than RECURSIA.
The Online Resources Shared on Twitter About the #MeToo Movement: The Pareto Principle
Venue: arXiv cs.SI 2019
Year: 2019

In this paper we examine the most influential resources shared on Twitter about the #MeToo movement. We also examine whether a small proportion of domain names and URLs (e.g. 20%) appear in a large number of tweets (e.g. 80%) that contain #MeToo (known as the 80/20 rule or Pareto principle). R and Python were used to analyze the data. Results demonstrated that the most frequently shared domains were twitter.com (47.20%), nytimes.com (4.42%) and youtube.com (3.69%). The most frequently shared content was a recent poll which indicated "men are afraid to mentor women after the #MeToo movement". In accordance with the Pareto principle, 8% of domain names accounted for 80% of the shared content on Twitter that contained #MeToo. This study provides a base for researchers who are interested in understanding what online resources people rely on when sharing information about online social movements (e.g. #MeToo).
Graph Star Net for Generalized Multi-Task Learning
Venue: arXiv cs.SI 2019
Year: 2019

In this work, we present graph star net (GraphStar), a novel and unified graph neural net architecture which utilizes message-passing relay and attention mechanism for multiple prediction tasks - node classification, graph classification and link prediction. GraphStar addresses many earlier challenges facing graph neural nets and achieves non-local representation without increasing the model depth or bearing heavy computational costs. We also propose a new method to tackle topic-specific sentiment analysis based on node classification and text classification as graph classification. Our work shows that 'star nodes' can learn effective graph-data representation and improve on current methods for the three tasks. Specifically, for graph classification and link prediction, GraphStar outperforms the current state-of-the-art models by 2-5% on several key benchmarks.
Automatic Discovery of Families of Network Generative Processes
Venue: arXiv cs.SI 2019
Year: 2019

Designing plausible network models typically requires scholars to form a priori intuitions on the key drivers of network formation. Oftentimes, these intuitions are supported by the statistical estimation of a selection of network evolution processes which will form the basis of the model to be developed. Machine learning techniques have lately been introduced to assist the automatic discovery of generative models. These approaches may more broadly be described as "symbolic regression", where fundamental network dynamic functions, rather than just parameters, are evolved through genetic programming. This chapter first aims at reviewing the principles, efforts and the emerging literature in this direction, which is very much aligned with the idea of creating artificial scientists. Our contribution then aims more specifically at building upon an approach recently developed by us [Menezes \& Roth, 2014] in order to demonstrate the existence of families of networks that may be described by similar generative processes. In other words, symbolic regression may be used to group networks according to their inferred genotype (in terms of generative processes) rather than their observed phenotype (in terms of statistical/topological features). Our empirical case is based on an original data set of 238 anonymized ego-centered networks of Facebook friends, further yielding insights on the formation of sociability networks.
On Reducing Negative Jacobian Determinant of the Deformation Predicted by Deep Registration Networks
Venue: arXiv cs.CV 2019
Year: 2019

Image registration is a fundamental step in medical image analysis. Ideally, the transformation that registers one image to another should be a diffeomorphism that is both invertible and smooth. Traditional methods like geodesic shooting approach the problem via differential geometry, with theoretical guarantees that the resulting transformation will be smooth and invertible. Most previous research using unsupervised deep neural networks for registration have used a local smoothness constraint (typically, a spatial variation loss) to address the smoothness issue. These networks usually produce non-invertible transformations with ``folding'' in multiple voxel locations, indicated by a negative determinant of the Jacobian matrix of the transformation. While using a loss function that specifically penalizes the folding is a straightforward solution, this usually requires carefully tuning the regularization strength, especially when there are also other losses. In this paper we address this problem from a different angle, by investigating possible training mechanisms that will help the network avoid negative Jacobians and produce smoother deformations. We contribute two independent ideas in this direction. Both ideas greatly reduce the number of folding locations in the predicted deformation, without making changes to the hyperparameters or the architecture used in the existing baseline registration network.
Planting Trees for scalable and efficient Canonical Hub Labeling
Venue: arXiv cs.DC 2019
Year: 2019

Point-to-Point Shortest Distance (PPSD) query is a crucial primitive in graph database applications. Hub labeling algorithms compute a labeling that converts a PPSD query into a list intersection problem (over a pre-computed indexing) enabling swift query response. However, constructing hub labeling is computationally challenging. Even state-of-the-art parallel algorithms based on Pruned Landmark Labeling (PLL) [3], are plagued by large label size, violation of given network hierarchy, poor scalability and inability to process large graphs. In this paper, we develop novel parallel shared-memory and distributed-memory algorithms for constructing the Canonical Hub Labeling (CHL) that is minimal in size for a given network hierarchy. To the best of our knowledge, none of the existing parallel algorithms guarantee canonical labeling. Our key contribution, the PLaNT algorithm, scales well beyond the limits of current practice by completely avoiding inter-node communication. PLaNT also enables the design of a collaborative label partitioning scheme across multiple nodes for completely in-memory processing of massive graphs whose labels cannot fit on a single machine. Compared to the sequential PLL, we empirically demonstrate upto 47.4x speedup on a 72 thread shared-memory platform. On a 64-node cluster, PLaNT achieves an average 42x speedup over single node execution. Finally, we show how our approach demonstrates superior scalability - we can process 14x larger graphs (in terms of label size) and construct hub labeling orders of magnitude faster compared to state-of-the-art distributed paraPLL algorithm.
The CUED's Grammatical Error Correction Systems for BEA-2019
Venue: arXiv cs.CL 2019
Year: 2019

We describe two entries from the Cambridge University Engineering Department to the BEA 2019 Shared Task on grammatical error correction. Our submission to the low-resource track is based on prior work on using finite state transducers together with strong neural language models. Our system for the restricted track is a purely neural system consisting of neural language models and neural machine translation models trained with back-translation and a combination of checkpoint averaging and fine-tuning -- without the help of any additional tools like spell checkers. The latter system has been used inside a separate system combination entry in cooperation with the Cambridge University Computer Lab.
Music Performance Analysis: A Survey
Venue: arXiv cs.IR 2019
Year: 2019

Music Information Retrieval (MIR) tends to focus on the analysis of audio signals. Often, a single music recording is used as representative of a "song" even though different performances of the same song may reveal different properties. A performance is distinct in many ways from a (arguably more abstract) representation of a "song," "piece," or musical score. The characteristics of the (recorded) performance -- as opposed to the score or musical idea -- can have a major impact on how a listener perceives music. The analysis of music performance, however, has been traditionally only a peripheral topic for the MIR research community. This paper surveys the field of Music Performance Analysis (MPA) from various perspectives, discusses its significance to the field of MIR, and points out opportunities for future research in this field.
Robust Linear Discriminant Analysis Using Ratio Minimization of L1,2-Norms
Venue: arXiv cs.LG 2019
Year: 2019

As one of the most popular linear subspace learning methods, the Linear Discriminant Analysis (LDA) method has been widely studied in machine learning community and applied to many scientific applications. Traditional LDA minimizes the ratio of squared L2-norms, which is sensitive to outliers. In recent research, many L1-norm based robust Principle Component Analysis methods were proposed to improve the robustness to outliers. However, due to the difficulty of L1-norm ratio optimization, so far there is no existing work to utilize sparsity-inducing norms for LDA objective. In this paper, we propose a novel robust linear discriminant analysis method based on the L1,2-norm ratio minimization. Minimizing the L1,2-norm ratio is a much more challenging problem than the traditional methods, and there is no existing optimization algorithm to solve such non-smooth terms ratio problem. We derive a new efficient algorithm to solve this challenging problem, and provide a theoretical analysis on the convergence of our algorithm. The proposed algorithm is easy to implement, and converges fast in practice. Extensive experiments on both synthetic data and nine real benchmark data sets show the effectiveness of the proposed robust LDA method.
Non-destructive three-dimensional measurement of hand vein based on self-supervised network
Venue: arXiv cs.CV 2019
Year: 2019

At present, supervised stereo methods based on deep neural network have achieved impressive results. However, in some scenarios, accurate three-dimensional labels are inaccessible for supervised training. In this paper, a self-supervised network is proposed for binocular disparity matching (SDMNet), which computes dense disparity maps from stereo image pairs without disparity labels: In the self-supervised training, we match the stereo images densely to approximate the disparity maps and use them to warp the left and right images to estimate the right and left images; we build the loss function between estimated images and original images for self-supervised training, which adopts perceptual loss to help improve the quality of disparity maps in both detail and structure. Then, we use SDMNet to obtain disparities of hand vein. SDMNet has achieved excellent results on KITTI 2012, KITTI 2015, simulated vein dataset and real vein dataset, outperforming many state-of-the-art supervised matching methods.
On Asymmetric Unification for the Theory of XOR with a Homomorphism
Venue: arXiv cs.CC 2019
Year: 2019

Asymmetric unification, or unification with irreducibility constraints, is a newly developed paradigm that arose out of the automated analysis of cryptographic protocols. However, there are still relatively few asymmetric unification algorithms. In this paper we address this lack by exploring the application of automata-based unification methods. We examine the theory of xor with a homomorphism, ACUNh, from the point of view of asymmetric unification, and develop a new automata-based decision procedure. Then, we adapt a recently developed asymmetric combination procedure to produce a general asymmetric- ACUNh decision procedure. Finally, we present a new approach for obtaining a solution-generating asymmetric-ACUNh unification automaton. We also compare our approach to the most commonly used form of asymmetric unification available today, variant unification.
Streaming Quantiles Algorithms with Small Space and Update Time
Venue: arXiv cs.DS 2019
Year: 2019

Approximating quantiles and distributions over streaming data has been studied for roughly two decades now. Recently, Karnin, Lang, and Liberty proposed the first asymptotically optimal algorithm for doing so. This manuscript complements their theoretical result by providing a practical variants of their algorithm with improved constants. For a given sketch size, our techniques provably reduce the upper bound on the sketch error by a factor of two. These improvements are verified experimentally. Our modified quantile sketch improves the latency as well by reducing the worst case update time from $O(1/\varepsilon)$ down to $O(\log (1/\varepsilon))$. We also suggest two algorithms for weighted item streams which offer improved asymptotic update times compared to naïve extensions. Finally, we provide a specialized data structure for these sketches which reduces both their memory footprints and update times.
Ludii and XCSP: Playing and Solving Logic Puzzles
Venue: arXiv cs.AI 2019
Year: 2019

Many of the famous single-player games, commonly called puzzles, can be shown to be NP-Complete. Indeed, this class of complexity contains hundreds of puzzles, since people particularly appreciate completing an intractable puzzle, such as Sudoku, but also enjoy the ability to check their solution easily once it's done. For this reason, using constraint programming is naturally suited to solve them. In this paper, we focus on logic puzzles described in the Ludii general game system and we propose using the XCSP formalism in order to solve them with any CSP solver.