OpenRaiser/Intern-Atlas huggingface dataset:
Subsampling for Ridge Regression via Regularized Volume Sampling
Venue: arXiv cs.LG 2018
Year: 2018

Given $n$ vectors $\mathbf{x}_i\in \mathbb{R}^d$, we want to fit a linear regression model for noisy labels $y_i\in\mathbb{R}$. The ridge estimator is a classical solution to this problem. However, when labels are expensive, we are forced to select only a small subset of vectors $\mathbf{x}_i$ for which we obtain the labels $y_i$. We propose a new procedure for selecting the subset of vectors, such that the ridge estimator obtained from that subset offers strong statistical guarantees in terms of the mean squared prediction error over the entire dataset of $n$ labeled vectors. The number of labels needed is proportional to the statistical dimension of the problem which is often much smaller than $d$. Our method is an extension of a joint subsampling procedure called volume sampling. A second major contribution is that we speed up volume sampling so that it is essentially as efficient as leverage scores, which is the main i.i.d. subsampling procedure for this task. Finally, we show theoretically and experimentally that volume sampling has a clear advantage over any i.i.d. sampling when labels are expensive.
Parametric t-Distributed Stochastic Exemplar-centered Embedding
Venue: arXiv cs.LG 2018
Year: 2018

Parametric embedding methods such as parametric t-SNE (pt-SNE) have been widely adopted for data visualization and out-of-sample data embedding without further computationally expensive optimization or approximation. However, the performance of pt-SNE is highly sensitive to the hyper-parameter batch size due to conflicting optimization goals, and often produces dramatically different embeddings with different choices of user-defined perplexities. To effectively solve these issues, we present parametric t-distributed stochastic exemplar-centered embedding methods. Our strategy learns embedding parameters by comparing given data only with precomputed exemplars, resulting in a cost function with linear computational and memory complexity, which is further reduced by noise contrastive samples. Moreover, we propose a shallow embedding network with high-order feature interactions for data visualization, which is much easier to tune but produces comparable performance in contrast to a deep neural network employed by pt-SNE. We empirically demonstrate, using several benchmark datasets, that our proposed methods significantly outperform pt-SNE in terms of robustness, visual effects, and quantitative evaluations.
Microaneurysm Detection in Fundus Images Using a Two-step Convolutional Neural Networks
Venue: arXiv cs.CV 2018
Year: 2018

Diabetic Retinopathy (DR) is a prominent cause of blindness in the world. The early treatment of DR can be conducted from detection of microaneurysms (MAs) which appears as reddish spots in retinal images. An automated microaneurysm detection can be a helpful system for ophthalmologists. In this paper, deep learning, in particular convolutional neural network (CNN), is used as a powerful tool to efficiently detect MAs from fundus images. In our method a new technique is used to utilise a two-stage training process which results in an accurate detection, while decreasing computational complexity in comparison with previous works. To validate our proposed method, an experiment is conducted using Keras library to implement our proposed CNN on two standard publicly available datasets. Our results show a promising sensitivity value of about 0.8 at the average number of false positive per image greater than 6 which is a competitive value with the state-of-the-art approaches.
K-means clustering for efficient and robust registration of multi-view point sets
Venue: arXiv cs.CV 2018
Year: 2018

Generally, there are three main factors that determine the practical usability of registration, i.e., accuracy, robustness, and efficiency. In real-time applications, efficiency and robustness are more important. To promote these two abilities, we cast the multi-view registration into a clustering task. All the centroids are uniformly sampled from the initially aligned point sets involved in the multi-view registration, which makes it rather efficient and effective for the clustering. Then, each point is assigned to a single cluster and each cluster centroid is updated accordingly. Subsequently, the shape comprised by all cluster centroids is used to sequentially estimate the rigid transformation for each point set. For accuracy and stability, clustering and transformation estimation are alternately and iteratively applied to all point sets. We tested our proposed approach on several benchmark datasets and compared it with state-of-the-art approaches. Experimental results validate its efficiency and robustness for the registration of multi-view point sets.
Network Model Selection Using Task-Focused Minimum Description Length
Venue: arXiv cs.AI 2018
Year: 2018

Networks are fundamental models for data used in practically every application domain. In most instances, several implicit or explicit choices about the network definition impact the translation of underlying data to a network representation, and the subsequent question(s) about the underlying system being represented. Users of downstream network data may not even be aware of these choices or their impacts. We propose a task-focused network model selection methodology which addresses several key challenges. Our approach constructs network models from underlying data and uses minimum description length (MDL) criteria for selection. Our methodology measures efficiency, a general and comparable measure of the network's performance of a local (i.e. node-level) predictive task of interest. Selection on efficiency favors parsimonious (e.g. sparse) models to avoid overfitting and can be applied across arbitrary tasks and representations. We show stability, sensitivity, and significance testing in our methodology.
MR fingerprinting Deep RecOnstruction NEtwork (DRONE)
Venue: arXiv cs.CV 2018
Year: 2018

PURPOSE: Demonstrate a novel fast method for reconstruction of multi-dimensional MR Fingerprinting (MRF) data using Deep Learning methods. METHODS: A neural network (NN) is defined using the TensorFlow framework and trained on simulated MRF data computed using the Bloch equations. The accuracy of the NN reconstruction of noisy data is compared to conventional MRF template matching as a function of training data size, and quantified in a both simulated numerical brain phantom data and acquired data from the ISMRM/NIST phantom. The utility of the method is demonstrated in a healthy subject in vivo at 1.5 T. RESULTS: Network training required 10 minutes and once trained, data reconstruction required approximately 10 ms. Reconstruction of simulated brain data using the NN resulted in a root-mean-square error (RMSE) of 3.5 ms for T1 and 7.8 ms for T2. The RMSE for the NN trained on sparse dictionaries was approximately 6 fold lower for T1 and 2 fold lower for T2 than conventional MRF dot-product dictionary matching on the same dictionaries. Phantom measurements yielded good agreement (R2=0.99) between the T1 and T2 estimated by the NN and reference values from the ISMRM/NIST phantom. CONCLUSION: Reconstruction of MRF data with a NN is accurate, 300 fold faster and more robust to noise and undersampling than conventional MRF dictionary matching.
Blind Image Fusion for Hyperspectral Imaging with the Directional Total Variation
Venue: arXiv cs.CV 2018
Year: 2018

Hyperspectral imaging is a cutting-edge type of remote sensing used for mapping vegetation properties, rock minerals and other materials. A major drawback of hyperspectral imaging devices is their intrinsic low spatial resolution. In this paper, we propose a method for increasing the spatial resolution of a hyperspectral image by fusing it with an image of higher spatial resolution that was obtained with a different imaging modality. This is accomplished by solving a variational problem in which the regularization functional is the directional total variation. To accommodate for possible mis-registrations between the two images, we consider a non-convex blind super-resolution problem where both a fused image and the corresponding convolution kernel are estimated. Using this approach, our model can realign the given images if needed. Our experimental results indicate that the non-convexity is negligible in practice and that reliable solutions can be computed using a variety of different optimization algorithms. Numerical results on real remote sensing data from plant sciences and urban monitoring show the potential of the proposed method and suggests that it is robust with respect to the regularization parameters, mis-registration and the shape of the kernel.
Lung Cancer Screening Using Adaptive Memory-Augmented Recurrent Networks
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we investigate the effectiveness of deep learning techniques for lung nodule classification in computed tomography scans. Using less than 10,000 training examples, our deep networks perform two times better than a standard radiology software. Visualization of the networks' neurons reveals semantically meaningful features that are consistent with the clinical knowledge and radiologists' perception. Our paper also proposes a novel framework for rapidly adapting deep networks to the radiologists' feedback, or change in the data due to the shift in sensor's resolution or patient population. The classification accuracy of our approach remains above 80% while popular deep networks' accuracy is around chance. Finally, we provide in-depth analysis of our framework by asking a radiologist to examine important networks' features and perform blind re-labeling of networks' mistakes.
Dissipative analysis of linear coupled differential-difference systems with distributed delays
Venue: arXiv cs.SY 2018
Year: 2018

In this paper, we present a new method for the dissipativity and stability analysis of a linear coupled differential-difference system (CDDS) with general distributed delays at both state and output. More precisely, the distributed delay terms under consideration can contain any $\fL^{2}$ functions which are approximated via a class of elementary functions which includes the option of Legendre polynomials. By using this broader class of functions compared to the existing Legendre polynomials approximation approach, one can construct a Liapunov-Krasovskii functional which is parameterized by non-polynomial functions . Furthermore, a novel generalized integral inequality is also proposed to incorporate approximation error in our stability (dissipativity) conditions. Based on the proposed approximation scenario with the proposed integral inequality, sufficient conditions determining the dissipativity and stability of a CDDS are derived in terms of linear matrix inequalities. In addition, several hierarchies in terms of the feasibility of the proposed conditions are derived under certain constraints. Finally, several numerical examples are presented in this paper to show the effectiveness of our proposed methodologies.
Combinatorial Penalties: Which structures are preserved by convex relaxations?
Venue: arXiv cs.LG 2018
Year: 2018

We consider the homogeneous and the non-homogeneous convex relaxations for combinatorial penalty functions defined on support sets. Our study identifies key differences in the tightness of the resulting relaxations through the notion of the lower combinatorial envelope of a set-function along with new necessary conditions for support identification. We then propose a general adaptive estimator for convex monotone regularizers, and derive new sufficient conditions for support recovery in the asymptotic setting.
A tight Erdős-Pósa function for wheel minors
Venue: arXiv cs.DM 2018
Year: 2018

Let $W_t$ denote the wheel on $t+1$ vertices. We prove that for every integer $t \geq 3$ there is a constant $c=c(t)$ such that for every integer $k\geq 1$ and every graph $G$, either $G$ has $k$ vertex-disjoint subgraphs each containing $W_t$ as minor, or there is a subset $X$ of at most $c k \log k$ vertices such that $G-X$ has no $W_t$ minor. This is best possible, up to the value of $c$. We conjecture that the result remains true more generally if we replace $W_t$ with any fixed planar graph $H$.
Identifying Mild Traumatic Brain Injury Patients From MR Images Using Bag of Visual Words
Venue: arXiv cs.CV 2018
Year: 2018

Mild traumatic brain injury (mTBI) is a growing public health problem with an estimated incidence of one million people annually in US. Neurocognitive tests are used to both assess the patient condition and to monitor the patient progress. This work aims to directly use MR images taken shortly after injury to detect whether a patient suffers from mTBI, by incorporating machine learning and computer vision techniques to learn features suitable discriminating between mTBI and normal patients. We focus on 3 regions in brain, and extract multiple patches from them, and use bag-of-visual-word technique to represent each subject as a histogram of representative patterns derived from patches from all training subjects. After extracting the features, we use greedy forward feature selection, to choose a subset of features which achieves highest accuracy. We show through experimental studies that BoW features perform better than the simple mean value features which were used previously.
Annotating High-Level Structures of Short Stories and Personal Anecdotes
Venue: arXiv cs.CL 2018
Year: 2018

Stories are a vital form of communication in human culture; they are employed daily to persuade, to elicit sympathy, or to convey a message. Computational understanding of human narratives, especially high-level narrative structures, remain limited to date. Multiple literary theories for narrative structures exist, but operationalization of the theories has remained a challenge. We developed an annotation scheme by consolidating and extending existing narratological theories, including Labov and Waletsky's (1967) functional categorization scheme and Freytag's (1863) pyramid of dramatic tension, and present 360 annotated short stories collected from online sources. In the future, this research will support an approach that enables systems to intelligently sustain complex communications with humans.
A Primal-Dual based Distributed Approximation Algorithm for Prize-Collecting Steiner Tree
Venue: arXiv cs.DC 2018
Year: 2018

The Prize-Collecting Steiner Tree (PCST) problem is a generalization of the Steiner Tree problem that has applications in network design, content distribution networks, and many more. There are a few centralized approximation algorithms \cite{DB_MG_DS_DW_1993, GW_1995, DJ_MM_SP_2000, AA_MB_MH_2011} for solving the PCST problem. However no distributed algorithm is known that solves PCST with a guaranteed approximation factor. In this work we present an asynchronous distributed $(2 - \frac{1}{n - 1})$-approximation algorithm that constructs a PCST for a given connected undirected graph with non-negative edge weights and a non-negative prize value for each node. Our algorithm is an adaptation of the centralized algorithm proposed by Goemans and Williamson \cite{GW_1995} to the distributed setting, and is based on the primal-dual method. The message complexity of the algorithm with input graph having node set $V$ and edge set $E$ is $O(|V||E|)$. Initially each node knows only its own prize value and the weight of each incident edge. The algorithm is spontaneously initiated at a special node called the \emph{root node} and when it terminates each node knows whether it is in the PCST or not. To the best of our knowledge this is the first distributed constant approximation algorithm for PCST.
Emerging from Water: Underwater Image Color Correction Based on Weakly Supervised Color Transfer
Venue: arXiv cs.CV 2018
Year: 2018

Underwater vision suffers from severe effects due to selective attenuation and scattering when light propagates through water. Such degradation not only affects the quality of underwater images but limits the ability of vision tasks. Different from existing methods which either ignore the wavelength dependency of the attenuation or assume a specific spectral profile, we tackle color distortion problem of underwater image from a new view. In this letter, we propose a weakly supervised color transfer method to correct color distortion, which relaxes the need of paired underwater images for training and allows for the underwater images unknown where were taken. Inspired by Cycle-Consistent Adversarial Networks, we design a multi-term loss function including adversarial loss, cycle consistency loss, and SSIM (Structural Similarity Index Measure) loss, which allows the content and structure of the corrected result the same as the input, but the color as if the image was taken without the water. Experiments on underwater images captured under diverse scenes show that our method produces visually pleasing results, even outperforms the art-of-the-state methods. Besides, our method can improve the performance of vision tasks.
Combining Multiple Views for Visual Speech Recognition
Venue: arXiv cs.CV 2018
Year: 2018

Visual speech recognition is a challenging research problem with a particular practical application of aiding audio speech recognition in noisy scenarios. Multiple camera setups can be beneficial for the visual speech recognition systems in terms of improved performance and robustness. In this paper, we explore this aspect and provide a comprehensive study on combining multiple views for visual speech recognition. The thorough analysis covers fusion of all possible view angle combinations both at feature level and decision level. The employed visual speech recognition system in this study extracts features through a PCA-based convolutional neural network, followed by an LSTM network. Finally, these features are processed in a tandem system, being fed into a GMM-HMM scheme. The decision fusion acts after this point by combining the Viterbi path log-likelihoods. The results show that the complementary information contained in recordings from different view angles improves the results significantly. For example, the sentence correctness on the test set is increased from 76% for the highest performing single view ($30^\circ$) to up to 83% when combining this view with the frontal and $60^\circ$ view angles.
Parallel Combining: Benefits of Explicit Synchronization
Venue: arXiv cs.DC 2018
Year: 2018

Parallel batched data structures are designed to process synchronized batches of operations in a parallel computing model. In this paper, we propose parallel combining, a technique that implements a concurrent data structure from a parallel batched one. The idea is that we explicitly synchronize concurrent operations into batches: one of the processes becomes a combiner which collects concurrent requests and initiates a parallel batched algorithm involving the owners (clients) of the collected requests. Intuitively, the cost of synchronizing the concurrent calls can be compensated by running the parallel batched algorithm. We validate the intuition via two applications of parallel combining. First, we use our technique to design a concurrent data structure optimized for read-dominated workloads, taking a dynamic graph data structure as an example. Second, we use a novel parallel batched priority queue to build a concurrent one. In both cases, we obtain performance gains with respect to the state-of-the-art algorithms.
Kernelization Lower Bounds for Finding Constant-Size Subgraphs
Venue: arXiv cs.CC 2018
Year: 2018

Kernelization is an important tool in parameterized algorithmics. Given an input instance accompanied by a parameter, the goal is to compute in polynomial time an equivalent instance of the same problem such that the size of the reduced instance only depends on the parameter and not on the size of the original instance. In this paper, we provide a first conceptual study on limits of kernelization for several polynomial-time solvable problems. For instance, we consider the problem of finding a triangle with negative sum of edge weights parameterized by the maximum degree of the input graph. We prove that a linear-time computable strict kernel of truly subcubic size for this problem violates the popular APSP-conjecture.
Asymptotically Optimal Resource Block Allocation With Limited Feedback
Venue: arXiv cs.IT 2018
Year: 2018

Consider a channel allocation problem over a frequency-selective channel.There are K channels (frequency bands) and N users such that K=bN for some positive integer b. We want to allocate b channels (or resource blocks) to each user. Due to the nature of the frequency-selective channel, each user considers some channels to be better than others. The optimal solution to this resource allocation problem can be computed using the Hungarian algorithm. However, this requires knowledge of the numerical value of all the channel gains, which makes this approach impractical for large networks. We suggest a suboptimal approach, that only requires knowing what the M-best channels of each user are. We find the minimal value of M such that there exists an allocation where all the b channels each user gets are among his M-best. This leads to feedback of significantly less than one bit per user per channel. For a large class of fading distributions, including Rayleigh, Rician, m-Nakagami and others, this suboptimal approach leads to both an asymptotically (in K) optimal sum-rate and an asymptotically optimal minimal rate. Our non-opportunistic approach achieves (asymptotically) full multiuser diversity as well as optimal fairness, by contrast to all other limited feedback algorithms.
On the Annihilator Ideal of an Inverse Form
Venue: arXiv cs.SC 2018
Year: 2018

Let $K$ be a field. We simplify and extend work of Althaler \& Dür on finite sequences over $K$ by regarding $K[x^{-1},z^{-1}]$ as a $K[x,z]$ module, and studying forms in $K[x^{-1},z^{-1}]$ from first principles. Then we apply our results to finite sequences. First we define the annihilator ideal $I_F$ of a non-zero form $F\in K[x^{-1},z^{-1}]$, a homogeneous ideal. We inductively construct an ordered pair ($f_1$\,,\,$f_2$) of forms which generate $I_F$\,; our generators are special in that $z$ does not divide the leading grlex monomial of $f_1$ but $z$ divides $f_2$\,, and the sum of their total degrees is always $2-|F|$, where $|F|$ is the total degree of $F$. We show that $f_1,f_2$ is a maximal regular sequence for $I_F$, so that the height of $I_F$ is 2. The corresponding algorithm is $\sim |F|^2/2$. The row vector obtained by accumulating intermediate forms of the construction gives a minimal grlex Gröbner basis for $I_F$ for no extra computational cost other than storage and apply this to determining $\dim_K (K[x,z] /I_F)$\,. We show that either the form vector is reduced or a monomial of $f_1$ can be reduced by $f_2$\,. This enables us to efficiently construct the unique reduced Gröbner basis for $I_F$ from the vector extension of our algorithm. Then we specialise to the inverse form of a finite sequence, obtaining generator forms for its annihilator ideal and a corresponding algorithm which does not use the last 'length change' of Massey. We compute the intersection of two annihilator ideals using syzygies in $K[x,z]^5$. This improves a result of Althaler \& Dür. Finally, dehomogenisation induces a one-to-one correspondence ($f_1$\,,$f_2$) $\mapsto$ (minimal polynomial, auxiliary polynomial), the output of the author's variant of the Berlekamp-Massey algorithm. So we can also solve the LFSR synthesis problem via the corresponding algorithm for sequences.
Teaching Programming and Design-by-Contract
Venue: arXiv cs.SE 2018
Year: 2018

This paper summarizes the experience of teaching an introductory course to programming by using a correctness by construction approach at Innopolis University, Russian Federation. In this paper we claim that division in beginner and advanced groups improves the learning outcomes, present the discussion and the data that support the claim.