High-dimensional data representation is an important problem in many different areas of science. Nowadays, it is becoming crucial to interpret the data of varying dimensionality correctly. Dimensionality reduction methods process the data in order to help visualize the data, reduce its complexity, or find latent representation of the original problem. The algorithms of nonlinear dimensionality reduction (also known as manifold learning) are used to decrease the dimensionality of the problem while preserving the general structure of the data. Both spectral methods (such as Laplacian Eigenmaps or ISOMAP) and nonlinear embedding algorithms (NLE, such as t-SNE or Elastic Embedding) have shown to provide very good nonlinear embedding of high-dimensional data sets. However, those methods are notorious for very slow optimization, practically preventing them from being used when a data set is bigger than few thousand points.

In my thesis we investigate several techniques to improve different stages of nonlinear dimensionally algorithms. First, we analyze the entropic affinities as a better way to build a similarity matrix. We explore its properties and propose a nearly-optimal algorithm to construct them. Second, we present a novel faster method to optimize NLE by using second-order information during the optimization. Third, for spectral methods, we investigate landmark-based optimization that cleverly substitutes original large-scale problem with a much smaller easy-to-solve subproblem. Finally, we apply Fast Multipole Methods approximation that allows fast computation of the gradient and the objective function of NLE and reduces their computational complexity from O(N^2) to O(N).

Each of the proposed methods accelerate the optimization dramatically by one or two orders of magnitude compared to the existing techniques, effectively allowing corresponding methods to run on a dataset with millions of points.

Is it possible to recover movements of the vocal tract shape of the subject from arbitrary but normal speech acoustics? This problem is formally known as acoustic-to-articulatory mapping or articulatory inversion. A successful solution to this long standing and unsolved problem can facilitate useful applications in vocal tract visualization, language learning, speech therapy, and improve state-of-art recognition, speech synthesis, speech coding. It is known as the signature problem in articulatory speech processing, which aims to integrate explicitly human speech production knowledge into acoustics based speech technologies--Abstract.

Modern high dimensional data poses serious difficulties for various learning tasks. However, most high dimensional problems exhibit manifold structure, i.e., there exist only a few degrees of freedom that matter for the task at hand. Exploring such intrinsic structure is the key to designing accurate and efficient learning algorithms. In this thesis, we demonstrate the use of mean-shift, a popular mode-finding and clustering algorithm, for learning problems involving manifold structure. In particular, we propose several new algorithms based on the mean-shift update for the tasks of manifold denoising, matrix completion, and centroid-based clustering.

The first algorithm, manifold blurring mean-shift (MBMS), is an algorithm of the predictor-corrector type. It alternates a predictor, blurring mean-shift step that acts as an isotropic low-pass filter and a corrector, projection step that removes the shrinkage of data along the manifold, where the manifold structure is estimated by local PCA. The algorithm achieves anisotropic denoising, can be used as a pre-processing step for dimension reduction and classification, and significantly improves over previous manifold denoising algorithms. Furthermore, we apply MBMS to matrix completion/missing value problems by iteratively denoising the whole dataset and filling in the observed entries. In contrast to the popular low-rank approaches based on a globally linear assumption, our algorithm preserves locally linear structure instead when the data is globally nonlinear. This simple approach provides a fresh view of the matrix completion problem, and greatly improves over several previous approaches.

We also propose two new, mode-based algorithms for clustering. The first one, which we call the K-modes algorithm, partitions a dataset into a pre-specified number of clusters, and provides a representative centroid of each cluster. Each centroid is the mode of the kernel density estimate defined by each cluster and is thus located in a high-density area. The algorithm is computationally inexpensive and more robust than K-means and mean-shift. We then provide a continuous relaxation for the hard partition rule of K-modes and impose a Laplacian smoothing penalty so that similar input samples receive similar assignments. The new algorithm, which we call the Laplacian K-modes algorithm, is able to handle non-convex, complex-shaped clusters, has an efficient optimization procedure, and shares nice properties with many well-known clustering algorithms.

The proposed mean-shift algorithms are simple and very easy to implement, yet they have superior performance on the tasks of consideration compared to previous approaches. We demonstrate them on various high dimensional datasets from different domains.

Decision trees (DT) are considered to be one of the oldest machine learning models which received a lot of attention from practitioners and research community. Although their roots are in the 1950s, they became popular in the early 1980s with developing popular methods, such as CART and C4.5. They are conceptually simple yet powerful. State-of-the-art frameworks, such as XGBoost or LightGBM, rely on them as base learners, but they have been used as well as standalone predictors.

Despite the rich history of decision trees and existence of numerous methods, their applicability beyond traditional supervised learning has been explored in limited extent. For instance, various fast growing ML subfields, such as semi-supervised and self-supervised learning, nonlinear dimensionality reduction (e.g. nonlinear embeddings), etc. have been barely used with trees. What is common to most of these tasks is that the objective function takes a certain form, which involves manifold regularization to exploit the geometry of the underlying data distribution. For example, a common assumption is that similar instances have similar predictions. However, incorporating this type of regularization is non-trivial with decision trees. The main reason is that the learning decision trees from data (even in supervised learning setup) is still an open research problem because it involves solving non-trivial combinatorial optimization problem. In fact, finding an optimal decision tree or even constant-factor approximation is NP-hard in most formulations of the problem. Adding manifold regularization term into an overall objective makes the problem even harder to solve.

In this dissertation, we study decision trees and, more generally, tree-based models under above-mentioned settings, i.e., involving manifold regularization. We argue that these type of problems carry a great practical importance but directly solving them is intractable (for decision trees). Using semi-supervised learning and nonlinear dimensionality reduction as examples, we derive a generic algorithm to solve such optimization problems. It is based on a reformulation of the problem which requires iteratively solving two simpler problems. One problem always involves supervised learning of a tree, which we solve by the Tree Alternating Optimization algorithm. The second one depends on a particular problem type and can be one of the following: solving a linear system, optimizing non-linear embeddings or something else. We also show that the algorithm is scalable and highly effective on number of practical tasks.

Neural networks have gained widespread use in many machine learning tasks due to their state-of-the-art performance. However, the cost of this progress lies in the ever-increasing sizes and computational demands of the resulting models. As such, the neural network compression, the process of reducing the size, power consumption, or any other cost of interest of the model, has become an important practical step when deploying the trained models to perform inference tasks.

In this dissertation, we explore a particular compression mechanism --- the low-rank decomposition --- and its extensions for the purposes of neural network compression. We study important aspects of the low-rank compression: how to select the decomposition ranks across the layers, how to choose best decomposition shapes for non-matrix weights among a number of options, and how to adapt the low-rank scheme to target the inference speed. Computationally, these are hard problems involving integer variables (ranks, decomposition shapes) and continuous variables (weights), as well as nonlinear loss and constraints.

As we show over the course of this dissertation, all these problems admit suitable formulations that can be efficiently solved using the recently proposed \emph{learning-compression algorithm}. The algorithm relies on the alternation of two optimization steps: the step over the neural network parameters, the L step, and the step over the compression parameters, the C step. Once we formulate the compression problems, we show how the L and C steps are derived. Each step can be solved efficiently: the L step is solved by stochastic gradient descent, and the C step relies on singular value decomposition. We demonstrate the effectiveness of the proposed compression schemes and the corresponding algorithms on multiple networks and datasets.

Finally, we discuss the resulting general neural network compression toolkit that encompasses all compression schemes presented in this dissertation and many others. The toolkit is designed to be flexible and extensible, and is released under the open-source license.

Practical deployment of deep neural networks has become widespread in the last decade due to their ability to provide simple, intelligent, and automated processing of the tasks that up to now were hard for other machine learning models. There is an enormous financial and societal interest in deep neural networks as a viable solution for many practical problems such as computer vision, language processing, financial fraud detection, and many more. At the same time, some concerns regarding the safety and ethical use of these models have arisen as well. One of the main concerns is interpretability, i.e., explaining how the model makes a decision for an input. Interpretability is one of the most important problems to address for building trust and accountability as the adoption of deep neural networks has increased significantly in sensitive areas like medicine, security, and finance.This dissertation proposes two novel approaches to interpreting deep neural networks. The first approach focuses on understanding what information is retained by the neurons of a deep net. We propose an approach to characterize the region of input space that excites a given neuron to a certain level. Inspection of these regions by a human can reveal regularities that help to understand the neuron. In the second approach, we provide a systematic way to understand what group of neurons in a deep net are responsible for a particular class. This allows us to study the relation between deep net features (neuron’s activation) and output classes; and how different classes are distributed in the latent space. We also show that out of thousands of neurons in the deep net, only a small subset of neurons is associated with a specific class. Finally, we demonstrate that the latter approach can also be used to interpret large datasets. This is achieved by applying the second approach directly over the input features. This allows us to understand what input features are related to a specific class and what set of features differentiates between a group of classes or even sub-groups within a given class.