Development and Validation of a Machine Learning System to Identify Reflux Events in Esophageal 24-Hour pH/Impedance Studies.

INTRODUCTION: Esophageal 24-hour pH/impedance testing is routinely performed to diagnose gastroesophageal reflux disease. Interpretation of these studies is time-intensive for expert physicians and has high inter-reader variability. There are no commercially available machine learning tools to assist with automated identification of reflux events in these studies. METHODS: A machine learning system to identify reflux events in 24-hour pH/impedance studies was developed, which included an initial signal processing step and a machine learning model. Gold-standard reflux events were defined by a group of expert physicians. Performance metrics were computed to compare the machine learning system, current automated detection software (Reflux Reader v6.1), and an expert physician reader. RESULTS: The study cohort included 45 patients (20/5/20 patients in the training/validation/test sets, respectively). The mean age was 51 (standard deviation 14.5) years, 47% of patients were male, and 78% of studies were performed off proton-pump inhibitor. Comparing the machine learning system vs current automated software vs expert physician reader, area under the curve was 0.87 (95% confidence interval [CI] 0.85-0.89) vs 0.40 (95% CI 0.37-0.42) vs 0.83 (95% CI 0.81-0.86), respectively; sensitivity was 68.7% vs 61.1% vs 79.4%, respectively; and specificity was 80.8% vs 18.6% vs 87.3%, respectively. DISCUSSION: We trained and validated a novel machine learning system to successfully identify reflux events in 24-hour pH/impedance studies. Our model performance was superior to that of existing software and comparable to that of a human reader. Machine learning tools could significantly improve automated interpretation of pH/impedance studies.

Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations.

Fast linear transforms are ubiquitous in machine learning, including the discrete Fourier transform, discrete cosine transform, and other structured transformations such as convolutions. All of these transforms can be represented by dense matrix-vector multiplication, yet each has a specialized and highly efficient (subquadratic) algorithm. We ask to what extent hand-crafting these algorithms and implementations is necessary, what structural priors they encode, and how much knowledge is required to automatically learn a fast algorithm for a provided structured transform. Motivated by a characterization of fast matrix-vector multiplication as products of sparse matrices, we introduce a parameterization of divide-and-conquer methods that is capable of representing a large class of transforms. This generic formulation can automatically learn an efficient algorithm for many important transforms; for example, it recovers the O(N log N) Cooley-Tukey FFT algorithm to machine precision, for dimensions N up to 1024. Furthermore, our method can be incorporated as a lightweight replacement of generic matrices in machine learning pipelines to learn efficient and compressible transformations. On a standard task of compressing a single hidden-layer network, our method exceeds the classification accuracy of unconstrained matrices on CIFAR-10 by 3.9 points-the first time a structured approach has done so-with 4× faster inference speed and 40× fewer parameters.

A Kernel Theory of Modern Data Augmentation.

Data augmentation, a technique in which a training set is expanded with class-preserving transformations, is ubiquitous in modern machine learning pipelines. In this paper, we seek to establish a theoretical framework for understanding data augmentation. We approach this from two directions: First, we provide a general model of augmentation as a Markov process, and show that kernels appear naturally with respect to this model, even when we do not employ kernel classification. Next, we analyze more directly the effect of augmentation on kernel classifiers, showing that data augmentation can be approximated by first-order feature averaging and second-order variance regularization components. These frameworks both serve to illustrate the ways in which data augmentation affects the downstream learning model, and the resulting analyses provide novel connections between prior work in invariant kernels, tangent propagation, and robust optimization. Finally, we provide several proof-of-concept applications showing that our theory can be useful for accelerating machine learning workflows, such as reducing the amount of computation needed to train using augmented data, and predicting the utility of a transformation prior to training.

Learning Compressed Transforms with Low Displacement Rank.

The low displacement rank (LDR) framework for structured matrices represents a matrix through two displacement operators and a low-rank residual. Existing use of LDR matrices in deep learning has applied fixed displacement operators encoding forms of shift invariance akin to convolutions. We introduce a rich class of LDR matrices with more general displacement operators, and explicitly learn over both the operators and the low-rank component. This class generalizes several previous constructions while preserving compression and efficient computation. We prove bounds on the VC dimension of multi-layer neural networks with structured weight matrices and show empirically that our compact parameterization can reduce the sample complexity of learning. When replacing weight layers in fully-connected, convolutional, and recurrent neural networks for image classification and language modeling tasks, our new classes exceed the accuracy of existing compression approaches, and on some tasks even outperform general unstructured layers while using more than 20X fewer parameters.

A two-pronged progress in structured dense matrixvector multiplication.

Matrix-vector multiplication is one of the most fundamental computing primitives. Given a matrix A ∈ F N × N and a vector b ∈ F N , it is known that in the worst case Θ(N 2) operations over F are needed to compute Ab. Many types of structured matrices do admit faster multiplication. However, even given a matrix A that is known to have this property, it is hard in general to recover a representation of A exposing the actual fast multiplication algorithm. Additionally, it is not known in general whether the inverses of such structured matrices can be computed or multiplied quickly. A broad question is thus to identify classes of structured dense matrices that can be represented with O(N) parameters, and for which matrix-vector multiplication (and ideally other operations such as solvers) can be performed in a sub-quadratic number of operations. One such class of structured matrices that admit near-linear matrix-vector multiplication are the orthogonal polynomial transforms whose rows correspond to a family of orthogonal polynomials. Other well known classes include the Toeplitz, Hankel, Vandermonde, Cauchy matrices and their extensions (e.g. confluent Cauchy-like matrices) that are all special cases of a low displacementrank property. In this paper, we make progress on two fronts: Our work unifies, generalizes, and simplifies existing state-of-the-art results in structured matrix-vector multiplication. Finally, we show how applications in areas such as multipoint evaluations of multivariate polynomials can be reduced to problems involving low recurrence width matrices.

Representation Tradeoffs for Hyperbolic Embeddings.

Hyperbolic embeddings offer excellent quality with few dimensions when embedding hierarchical data structures like synonym or type hierarchies. Given a tree, we give a combinatorial construction that embeds the tree in hyperbolic space with arbitrarily low distortion without using optimization. On WordNet, our combinatorial embedding obtains a mean-average-precision of 0.989 with only two dimensions, while Nickel et al.'s recent construction obtains 0.87 using 200 dimensions. We provide upper and lower bounds that allow us to characterize the precision-dimensionality tradeoff inherent in any hyperbolic embedding. To embed general metric spaces, we propose a hyperbolic generalization of multidimensional scaling (h-MDS). We show how to perform exact recovery of hyperbolic points from distances, provide a perturbation analysis, and give a recovery result that allows us to reduce dimensionality. The h-MDS approach offers consistently low distortion even with few dimensions across several datasets. Finally, we extract lessons from the algorithms and theory above to design a PyTorch-based implementation that can handle incomplete information and is scalable.