OpenRaiser/Intern-Atlas huggingface dataset:
Similarity Learning with Higher-Order Graph Convolutions for Brain Network Analysis
Venue: arXiv cs.CV 2019
Year: 2019

Learning a similarity metric has gained much attention recently, where the goal is to learn a function that maps input patterns to a target space while preserving the semantic distance in the input space. While most related work focused on images, we focus instead on learning a similarity metric for neuroimages, such as fMRI and DTI images. We propose an end-to-end similarity learning framework called Higher-order Siamese GCN for multi-subject fMRI data analysis. The proposed framework learns the brain network representations via a supervised metric-based approach with siamese neural networks using two graph convolutional networks as the twin networks. Our proposed framework performs higher-order convolutions by incorporating higher-order proximity in graph convolutional networks to characterize and learn the community structure in brain connectivity networks. To the best of our knowledge, this is the first community-preserving similarity learning framework for multi-subject brain network analysis. Experimental results on four real fMRI datasets demonstrate the potential use cases of the proposed framework for multi-subject brain analysis in health and neuropsychiatric disorders. Our proposed approach achieves an average AUC gain of 75% compared to PCA, an average AUC gain of 65.5% compared to Spectral Embedding, and an average AUC gain of 24.3% compared to S-GCN across the four datasets, indicating promising application in clinical investigation and brain disease diagnosis.
CAB: Continuous Adaptive Blending Estimator for Policy Evaluation and Learning
Venue: arXiv cs.LG 2019
Year: 2019

The ability to perform offline A/B-testing and off-policy learning using logged contextual bandit feedback is highly desirable in a broad range of applications, including recommender systems, search engines, ad placement, and personalized health care. Both offline A/B-testing and off-policy learning require a counterfactual estimator that evaluates how some new policy would have performed, if it had been used instead of the logging policy. In this paper, we identify a family of counterfactual estimators which subsumes most such estimators proposed to date. Our analysis of this family identifies a new estimator - called Continuous Adaptive Blending (CAB) - which enjoys many advantageous theoretical and practical properties. In particular, it can be substantially less biased than clipped Inverse Propensity Score (IPS) weighting and the Direct Method, and it can have less variance than Doubly Robust and IPS estimators. In addition, it is sub-differentiable such that it can be used for learning, unlike the SWITCH estimator. Experimental results show that CAB provides excellent evaluation accuracy and outperforms other counterfactual estimators in terms of learning performance.
Deep Reinforcement Learning via L-BFGS Optimization
Venue: arXiv cs.LG 2019
Year: 2019

Reinforcement Learning (RL) algorithms allow artificial agents to improve their action selections so as to increase rewarding experiences in their environments. Deep Reinforcement Learning algorithms require solving a nonconvex and nonlinear unconstrained optimization problem. Methods for solving the optimization problems in deep RL are restricted to the class of first-order algorithms, such as stochastic gradient descent (SGD). The major drawback of the SGD methods is that they have the undesirable effect of not escaping saddle points and their performance can be seriously obstructed by ill-conditioning. Furthermore, SGD methods require exhaustive trial and error to fine-tune many learning parameters. Using second derivative information can result in improved convergence properties, but computing the Hessian matrix for large-scale problems is not practical. Quasi-Newton methods require only first-order gradient information, like SGD, but they can construct a low rank approximation of the Hessian matrix and result in superlinear convergence. The limited-memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS) approach is one of the most popular quasi-Newton methods that construct positive definite Hessian approximations. In this paper, we introduce an efficient optimization method, based on the limited memory BFGS quasi-Newton method using line search strategy -- as an alternative to SGD methods. Our method bridges the disparity between first order methods and second order methods by continuing to use gradient information to calculate a low-rank Hessian approximations. We provide formal convergence analysis as well as empirical results on a subset of the classic ATARI 2600 games. Our results show a robust convergence with preferred generalization characteristics, as well as fast training time and no need for the experience replaying mechanism.
Capacity Value of Interconnection Between Two Systems
Venue: arXiv cs.CE 2019
Year: 2019

Concerns about system adequacy have led to the establishment of capacity mechanisms in a number of regulatory areas. Against this background, it is essential to accurately quantify the contribution to security of supply that results from interconnectors to neighbouring systems. This paper introduces a definition of capacity value for interconnection between two systems in the form of a capacity allocation curve. Four power flow policies are proposed to encompass the full range of possible market outcomes that may affect the capacity value. A convolution-based method is presented to efficiently compute and compare capacity allocation curves, and it is applied to a model system that is inspired by Great Britain's interconnection with the continental Europe. The results indicate areas of interest for the coordination of capacity mechanisms.
A Survey on Data Collection for Machine Learning: a Big Data -- AI Integration Perspective
Venue: arXiv cs.LG 2019
Year: 2019

Data collection is a major bottleneck in machine learning and an active research topic in multiple communities. There are largely two reasons data collection has recently become a critical issue. First, as machine learning is becoming more widely-used, we are seeing new applications that do not necessarily have enough labeled data. Second, unlike traditional machine learning, deep learning techniques automatically generate features, which saves feature engineering costs, but in return may require larger amounts of labeled data. Interestingly, recent research in data collection comes not only from the machine learning, natural language, and computer vision communities, but also from the data management community due to the importance of handling large amounts of data. In this survey, we perform a comprehensive study of data collection from a data management point of view. Data collection largely consists of data acquisition, data labeling, and improvement of existing data or models. We provide a research landscape of these operations, provide guidelines on which technique to use when, and identify interesting research challenges. The integration of machine learning and data management for data collection is part of a larger trend of Big data and Artificial Intelligence (AI) integration and opens many opportunities for new research.
Explainable cardiac pathology classification on cine MRI with motion characterization by semi-supervised learning of apparent flow
Venue: arXiv cs.CV 2019
Year: 2019

We propose a method to classify cardiac pathology based on a novel approach to extract image derived features to characterize the shape and motion of the heart. An original semi-supervised learning procedure, which makes efficient use of a large amount of non-segmented images and a small amount of images segmented manually by experts, is developed to generate pixel-wise apparent flow between two time points of a 2D+t cine MRI image sequence. Combining the apparent flow maps and cardiac segmentation masks, we obtain a local apparent flow corresponding to the 2D motion of myocardium and ventricular cavities. This leads to the generation of time series of the radius and thickness of myocardial segments to represent cardiac motion. These time series of motion features are reliable and explainable characteristics of pathological cardiac motion. Furthermore, they are combined with shape-related features to classify cardiac pathologies. Using only nine feature values as input, we propose an explainable, simple and flexible model for pathology classification. On ACDC training set and testing set, the model achieves 95% and 94% respectively as classification accuracy. Its performance is hence comparable to that of the state-of-the-art. Comparison with various other models is performed to outline some advantages of our model.
Disentangling Latent Factors of Variational Auto-Encoder with Whitening
Venue: arXiv cs.LG 2019
Year: 2019

After deep generative models were successfully applied to image generation tasks, learning disentangled latent variables of data has become a crucial part of deep generative model research. Many models have been proposed to learn an interpretable and factorized representation of latent variable by modifying their objective function or model architecture. To disentangle the latent variable, some models show lower quality of reconstructed images and others increase the model complexity which is hard to train. In this paper, we propose a simple disentangling method based on a traditional whitening process. The proposed method is applied to the latent variables of variational auto-encoder (VAE), although it can be applied to any generative models with latent variables. In experiment, we apply the proposed method to simple VAE models and experiment results confirm that our method finds more interpretable factors from the latent space while keeping the reconstruction error the same as the conventional VAE's error.
The ordinal generated by an ordinal grammar is computable
Venue: arXiv cs.FL 2019
Year: 2019

A prefix grammar is a context-free grammar whose nonterminals generate prefix-free languages. A prefix grammar $G$ is an ordinal grammar if the language $L(G)$ is well-ordered with respect to the lexicographic ordering. It is known that from a finite system of parametric fixed point equations one can construct an ordinal grammar $G$ such that the lexicographic order of $G$ is isomorphic with the least solution of the system, if this solution is well-ordered. In this paper we show that given an ordinal grammar, one can compute (the Cantor normal form of) the order type of the lexicographic order of its language, yielding that least solutions of fixed point equation systems defining algebraic ordinals are effectively computable (and thus, their isomorphism problem is also decidable).
Analysis of Fleet Modularity in an Artificial Intelligence-Based Attacker-Defender Game
Venue: arXiv cs.AI 2019
Year: 2019

Because combat environments change over time and technology upgrades are widespread for ground vehicles, a large number of vehicles and equipment become quickly obsolete. A possible solution for the U.S. Army is to develop fleets of modular military vehicles, which are built by interchangeable substantial components also known as modules. One of the typical characteristics of module is their ease of assembly and disassembly through simple means such as plug-in/pull-out actions, which allows for real-time fleet reconfiguration to meet dynamic demands. Moreover, military demands are time-varying and highly stochastic because commanders keep reacting to enemy's actions. To capture these characteristics, we formulated an intelligent agent-based model to imitate decision making process during fleet operation, which combines real-time optimization with artificial intelligence. The agents are capable of inferring enemy's future move based on historical data and optimize dispatch/operation decisions accordingly. We implement our model to simulate an attacker-defender game between two adversarial and intelligent players, representing the commanders from modularized fleet and conventional fleet respectively. Given the same level of combat resources and intelligence, we highlight the tactical advantages of fleet modularity in terms of win rate, unpredictability and suffered damage.
Minimizing and Computing the Inverse Geodesic Length on Trees
Venue: arXiv cs.DS 2019
Year: 2019

For any fixed measure $H$ that maps graphs to real numbers, the MinH problem is defined as follows: given a graph $G$, an integer $k$, and a target $τ$, is there a set $S$ of $k$ vertices that can be deleted, so that $H(G - S)$ is at most $τ$? In this paper, we consider the MinH problem on trees. We call $H$ "balanced on trees" if, whenever $G$ is a tree, there is an optimal choice of $S$ such that the components of $G-S$ have sizes bounded by a polynomial in $n/k$. We show that MinH on trees is FPT for parameter $n/k$, and furthermore, can be solved in subexponential time, and polynomial space, if $H$ is additive, balanced on trees, and computable in polynomial time. A measure of interest is the Inverse Geodesic Length (IGL), which is used to gauge the connectedness of a graph. It is defined as the sum of inverse distances between every two vertices: $IGL(G)=\sum_{\{u,v\} \subseteq V} \frac{1}{d_G(u,v)}$. While MinIGL is W[1]-hard for parameter treewidth, and cannot be solved in $2^{o(k+n+m)}$ time, even on bipartite graphs with $n$ vertices and $m$ edges, the complexity status of the problem remains open on trees. We show that IGL is balanced on trees, to give a $2^{O((n\log n)^{5/6})}$ time, polynomial space algorithm. The distance distribution of $G$ is the sequence $\{a_i\}$ describing the number of vertex pairs distance $i$ apart in $G$: $a_i=|\{\{u, v\}: d_G(u, v)=i\}|$. We show that the distance distribution of a tree can be computed in $O(n\log^2 n)$ time by reduction to polynomial multiplication. We extend our result to graphs with small treewidth by showing that the first $p$ values of the distance distribution can be computed in $2^{O(tw(G))} n^{1+\varepsilon} \sqrt{p}$ time, and the entire distance distribution can be computed in $2^{O(tw(G))} n^{1+\varepsilon}$ time, when the diameter of $G$ is $O(n^{\varepsilon'})$ for every $\varepsilon'>0$.
Cross and Learn: Cross-Modal Self-Supervision
Venue: arXiv cs.CV 2019
Year: 2019

In this paper we present a self-supervised method for representation learning utilizing two different modalities. Based on the observation that cross-modal information has a high semantic meaning we propose a method to effectively exploit this signal. For our approach we utilize video data since it is available on a large scale and provides easily accessible modalities given by RGB and optical flow. We demonstrate state-of-the-art performance on highly contested action recognition datasets in the context of self-supervised learning. We show that our feature representation also transfers to other tasks and conduct extensive ablation studies to validate our core contributions. Code and model can be found at https://github.com/nawidsayed/Cross-and-Learn.
Fast On-the-fly Retraining-free Sparsification of Convolutional Neural Networks
Venue: arXiv cs.CV 2019
Year: 2019

Modern Convolutional Neural Networks (CNNs) are complex, encompassing millions of parameters. Their deployment exerts computational, storage and energy demands, particularly on embedded platforms. Existing approaches to prune or sparsify CNNs require retraining to maintain inference accuracy. Such retraining is not feasible in some contexts. In this paper, we explore the sparsification of CNNs by proposing three model-independent methods. Our methods are applied on-the-fly and require no retraining. We show that the state-of-the-art models' weights can be reduced by up to 73% (compression factor of 3.7x) without incurring more than 5% loss in Top-5 accuracy. Additional fine-tuning gains only 8% in sparsity, which indicates that our fast on-the-fly methods are effective.
Tractability of Konig Edge Deletion Problems
Venue: arXiv cs.DS 2019
Year: 2019

A graph is said to be a Konig graph if the size of its maximum matching is equal to the size of its minimum vertex cover. The Konig Edge Deletion problem asks if in a given graph there exists a set of at most k edges whose deletion results in a Konig graph. While the vertex version of the problem (Konig vertex deletion) has been shown to be fixed-parameter tractable more than a decade ago, the fixed-parameter-tractability of the Konig Edge Deletion problem has been open since then, and has been conjectured to be W[1]-hard in several papers. In this paper, we settle the conjecture by proving it W[1]-hard. We prove that a variant of this problem, where we are given a graph G and a maximum matching M and we want a k-sized Konig edge deletion set that is disjoint from M, is fixed-parameter-tractable.
MR-RePair: Grammar Compression based on Maximal Repeats
Venue: arXiv cs.DS 2019
Year: 2019

We analyze the grammar generation algorithm of the RePair compression algorithm and show the relation between a grammar generated by RePair and maximal repeats. We reveal that RePair replaces step by step the most frequent pairs within the corresponding most frequent maximal repeats. Then, we design a novel variant of RePair, called MR-RePair, which substitutes the most frequent maximal repeats at once instead of substituting the most frequent pairs consecutively. We implemented MR-RePair and compared the size of the grammar generated by MR-RePair to that by RePair on several text corpus. Our experiments show that MR-RePair generates more compact grammars than RePair does, especially for highly repetitive texts.
Fine-tuning of Language Models with Discriminator
Venue: arXiv cs.CL 2019
Year: 2019

Cross-entropy loss is a common choice when it comes to multiclass classification tasks and language modeling in particular. Minimizing this loss results in language models of very good quality. We show that it is possible to fine-tune these models and make them perform even better if they are fine-tuned with sum of cross-entropy loss and reverse Kullback-Leibler divergence. The latter is estimated using discriminator network that we train in advance. During fine-tuning probabilities of rare words that are usually underestimated by language models become bigger. The novel approach that we propose allows us to reach state-of-the-art quality on Penn Treebank: perplexity decreases from 52.4 to 52.1. Our fine-tuning algorithm is rather fast, scales well to different architectures and datasets and requires almost no hyperparameter tuning: the only hyperparameter that needs to be tuned is learning rate.
Mutual Information of Wireless Channels and Block-Jacobi Ergodic Operators
Venue: arXiv cs.IT 2019
Year: 2019

Shannon's mutual information of a random multiple antenna and multipath channel is studied in the general case where the channel impulse response is an ergodic and stationary process which is assumed to be available at the receiver. From this viewpoint, the channel is represented by an ergodic self-adjoint block-Jacobi operator, which is close in many aspects to a block version of a random Schrödinger operator. The mutual information is then related to the so-called density of states of this operator. In this paper, it is shown that under the weakest assumptions on the channel, the mutual information can be expressed in terms of a matrix-valued stochastic process coupled with the channel process. This allows numerical approximations of the mutual information in this general setting. Moreover, assuming further that the channel impulse response is a Markov process, a representation for the mutual information offset in the large Signal to Noise Ratio regime is obtained in terms of another related Markov process. This generalizes previous results from Levy~\emph{et.al.}. It is also illustrated how the mutual information expressions that are closely related to those predicted by the random matrix theory can be recovered in the large dimensional regime.
On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties
Venue: arXiv cs.DM 2019
Year: 2019

The $k$-dimensional Weisfeiler-Leman algorithm ($k$-WL) is a fruitful approach to the Graph Isomorphism problem. 2-WL corresponds to the original algorithm suggested by Weisfeiler and Leman over 50 years ago. 1-WL is the classical color refinement routine. Indistinguishability by $k$-WL is an equivalence relation on graphs that is of fundamental importance for isomorphism testing, descriptive complexity theory, and graph similarity testing which is also of some relevance in artificial intelligence. Focusing on dimensions $k=1,2$, we investigate subgraph patterns whose counts are $k$-WL invariant, and whose occurrence is $k$-WL invariant. We achieve a complete description of all such patterns for dimension $k=1$ and considerably extend the previous results known for $k=2$.
Potential Game-Based Non-Myopic Sensor Network Planning for Multi-Target Tracking
Venue: arXiv cs.SY 2019
Year: 2019

This paper presents a potential game-based method for non-myopic planning of mobile sensor networks in the context of target tracking. The planning objective is to select the sequence of sensing points over more than one future time steps to maximize information about the target states. This multi-step lookahead scheme is studied to overcome getting trapped at local information maximum when there are gaps in sensing coverage due to constraints on the sensor platform mobility or limitations in sensing capabilities. However, the long-term planning becomes computationally intractable as the length of planing horizon increases. This work develops a gametheoretic approach to address the computational challenges. The main contributions of this paper are twofold: (a) to formulate a non-myopic planning problem for tracking multiple targets into a potential game, the size of which linearly increases as the number of planning steps (b) to design a learning algorithm exploiting the joint strategy fictitious play and dynamic programming, which overcomes the gaps in sensing coverage. Numerical examples of multi-target tracking demonstrate that the proposed method gives better estimation performance than myopic planning and is computationally tractable.
Bayesian Data Analysis in Empirical Software Engineering Research
Venue: arXiv cs.SE 2019
Year: 2019

Statistics comes in two main flavors: frequentist and Bayesian. For historical and technical reasons, frequentist statistics have traditionally dominated empirical data analysis, and certainly remain prevalent in empirical software engineering. This situation is unfortunate because frequentist statistics suffer from a number of shortcomings---such as lack of flexibility and results that are unintuitive and hard to interpret---that curtail their effectiveness when dealing with the heterogeneous data that is increasingly available for empirical analysis of software engineering practice. In this paper, we pinpoint these shortcomings, and present Bayesian data analysis techniques that provide tangible benefits---as they can provide clearer results that are simultaneously robust and nuanced. After a short, high-level introduction to the basic tools of Bayesian statistics, we present the reanalysis of two empirical studies on the effectiveness of automatically generated tests and the performance of programming languages. By contrasting the original frequentist analyses with our new Bayesian analyses, we demonstrate the concrete advantages of the latter. To conclude we advocate a more prominent role for Bayesian statistical techniques in empirical software engineering research and practice.