Large biological data, such as medical imaging and single-cell level genomic data, are rich sources of biological information. Machine learning is a tool to extract that information into a usable form, whether it be predictions for some prediction task or insights drawn from the model. We explore three applications of machine learning to biology. One is on using deep learning to perform metastatic cancer prognosis from CT images by predicting lesion-level risks. We use the lesion-level risks to show that the model captures clinically known indicators of risk. Next, we utilize the DeepLIFT and TF-MoDISco neural network interpretation techniques to understand how DNA shape affects transcription factor binding. Overall, we find that sequence features are more important for distinguishing bound sites, but that shape features can modulate binding affinity. Finally, we the test the CellOracle and SCENIC+ gene regulatory network inference frameworks in the context of reprogramming fibroblasts to pluripotent cells, to prioritize key factors in reprogramming and recover their effects on differentiation.

The Sparse Principal Component Analysis (Sparse PCA) problem is a variant of the classical PCA problem. The goal of Sparse PCA is to achieve a trade-off between the explained variance along a normalized vector, and the number of non-zero components of that vector. Sparse PCA has a wide array of applications in machine learning and engineering. Unfortunately, this problem is also combinatorially hard and hence various sub-optimal algorithms and approximation formulations have been proposed to tackle it. In this dissertation, we first discuss convex relaxation techniques that efficiently produce good approximate solutions. We then describe several algorithms solving these relaxations as well as greedy algorithms that iteratively improve the solution quality.

The dissertation then focuses on solving the attractive formulation called DSPCA (a Direct formulation for Sparse PCA) for large-scale problems. Although Sparse PCA has apparent advantages compared to PCA, such as better interpretability, it is generally thought to be computationally much more expensive. We demonstrate the surprising fact that sparse PCA can be easier than PCA in practice, and that it can be reliably applied to very large data sets. This comes from a rigorous feature elimination pre-processing result, coupled with the favorable fact that features in real-life data typically have rapidly decreasing variances, which allows for many features to be eliminated. We introduce a fast block coordinate ascent algorithm with much better computational complexity than the existing first-order ones. We provide experimental results obtained on text corpora involving millions of documents and hundreds of thousands of features.

Another focus of the dissertation is to illustrate the utility of Sparse PCA in various applications, ranging from senate voting and finance to text mining. In particular, we apply Sparse PCA to the analysis of text data, with online news as our focus. Our experimental results on various data sets illustrate how Sparse PCA can help organize a large corpus of text data in a user-interpretable way, providing an attractive alternative approach to topic models.

Behind all supervised learning problems is an optimization problem. Solving these problems reliably and efficiently is a key step in any machine learning pipeline. This thesis looks at efficient optimization algorithms for a variety of machine learning problems (in particular, sparse learning problems). We first begin by looking at a new class of algorithms for training feedforward neural networks. We then look at an efficient algorithm for constructing knockoff features for statistical inference. Finally, we look at $\ell_0$-penalized and constrained optimization problems and a class of efficient algorithms for training these non-convex problems while providing guarantees on the quality of the solution.

In this note we discuss the system optimum dynamic traffic assignment (SO-DTA) problem in the presence of time-dependent uncertainty on the demands and link capacities. We start from the deterministic linear programming formulation of the SO-DTA problem introduced by Ziliaskopoulos in [14], and then consider a robust version of the decision problem where the total travel time must be minimized under a worst-case scenario of demand and capacity configurations. When uncertain demands and capacities are modeled as unknown-but-bounded quantities restricted in intervals, the resulting robust decision problem can still be formulated as a linear program and solved at the same computational cost as its nominal counterpart. Worst-case solutions to assignment problems appear to be useful for establishing routing policies that are resilient to possibly large variations of network parameters and for computing lower bounds on network performance in extreme situations.

Sparse machine learning has recently emerged as powerful tool to obtain models of high-dimensional data with high degree of interpretability, at low computational cost. The approach has been successfully used in many areas, such as signal and image processing. In sparse learning classification, for example, the prediction accuracy or some other classical measure of performance is not the sole concern: we also wish to be able to better understand which few features are relevant as markers for classification. Furthermore, many of sparse learning tasks in practice, including cross-validation, parameter search, or leave-one-out analysis, involve multiple instances of similar problems, each instance sharing a large part of learning data with the others. In this thesis, we introduce a robust framework for solving these multiple sparse regressions in the form of square-root LASSO problems, based on a sketch of the learning data that uses low-rank approximations. Our approach allows a dramatic reduction in computational effort, while not sacrificing—sometimes even improving—the statistical performance.

We present our technique by first studying sparse optimization with applications in different domain of interests, from text analytics to system design, and then developing theories for robust solutions for sparse regression in multi-instance setting. We also provide comparisons with other heuristics to obtain sparse models in various applications. In more detail, our central contributions from this thesis include:

- Identifying key tasks in domains of interests under real-world setting,

- Suggesting models that are suitable for these tasks along the axes of computational complexity and model understandability,

- Exploiting problem structures when working with multiple instances to robustly improve computation while maintaining high learning performance, and

- Proposing applications of our robust solutions in high-dimensional setting.

This dissertation presents techniques for the summarization and exploration of text documents. Many approaches taken towards analysis of news media can be analogized to well-defined, well-studied problems from statistical machine learning. The problem of feature selection, for classification and dimensionality reduction tasks, is formulated to help assist with these media analysis tasks. Taking advantage of L1 regularization, convex programs can be used to efficiently solve these feature selection problems efficiently. There is a demonstrated potential to conduct media analysis at a scale commensurate with the growing volume of data available to news consumers.

There is first a presentation of an example text mining over a vector space model. Given two news articles on a related theme, a series of additional articles are pulled from a large pool of candidates to help link these two input items. The novel algorithm used is based on finding the documents whose vector representations are nearest the convex combinations of the inputs. Comparisons to competing algorithms show performance matching a state-of-the-art method, at a lower computational complexity.

Design of a relational database for typical text mining tasks is discussed. The architecture trades off the organizational and data quality advantages of normalization versus the performance boosts from replicating entity attributes across tables. The vector space model of text is implemented explicitly as a three-column table.

The predictive framework, connecting news analysis tasks to feature selection and classification problems, is then explicitly explored. The validity of this analogy is tested with a particular task: given a query term and a corpus of news articles, provide a short list of word tokens which distinguish how this word appears within the corpus. Example summary lists were produced by five algorithms, and presented to volunteer readers. Evidence suggests that an implementation of L1-regularized logistic regression model, trained over the documents with labels indicating the presence or absence of the query word, selected word-features best summarizing the query.

To contend with tasks that do not lend themselves this a predictive framework, a sparse variant of latent semantic indexing is investigated. [cont.]

Deep implicit models are very recent developments on deep learning. Traditionally, deeplearning methods rely on explicit forward feeding structures. Super deep structures are proposed to give better performance in various domains. Such approaches have posed difficulty in theoretical analysis and under perform shallower models in some domains. By introducing a recursive structure involving solution to an equilibrium equation in the forward feeding, implicit deep models capture the idea of infinitely deep neural networks while preserving simplicity in model representation, allowing theoretical analysis and better connection to previous efforts in math and control communities. Recent works on implicit models have demonstrated state-of-the-art empirical performances.

Despite great ambition, implicit models are very new and see theoretical and empiricalchallenges. From the theoretical aspect, efficient and effective training and evaluation of implicit models are still open problems. The naive training methods for implicit models are highly inefficient. Trivial initialization easily violates the validity conditions for implicit models. Robustness of implicit models are not well studied. From the empirical aspect, there are still a limited number of works on applying implicit models to solve real world problems. Such works also have not demonstrated significant performance boost over deep learning in general. Applications of implicit models in most areas are mostly unexplored even though implicit models fit in the deep learning framework easily.

In the dissertation, we introduce our theoretical and empirical contributions on deep implicitmodels. The presentation of the dissertation is split into two parts. The first part focuses on theoretical foundations for deep implicit models where we research the evaluation, training, and other topics for implicit deep learning and deep learning in general. The second part then explores the applications of deep implicit models and corresponding theories on real world machine learning applications. We show that implicit models can out-perform existing deep learning techniques in a set of tasks, thanks to the implicit structure which resembles infinitely deep neural networks.

In this thesis, we study two topics related to large-scale sparse

estimation and control. In the first topic, we describe a method to

eliminate features (variables) in $\ell_{1}$-regularized convex optimization

problems. The elimination of features leads to a potentially substantial

reduction in computational effort needed to solve such problems, especially

for large values of the penalty parameter. Our method is not heuristic:

it only eliminates features that are guaranteed to be absent after

solving the optimization problem. The feature elimination step is

easy to parallelize and can test each feature for elimination independently.

Moreover, the computational effort of our method is negligible compared

to that of solving the convex problem.

We study the case of $\ell_{1}$-regularized least-squares problem

(a.k.a. LASSO) extensively and derive a closed-form sufficient condition

for eliminating features. The sufficient condition can be evaluated

by few vector-matrix multiplications. For comparison purposes, we

present a LASSO solver that integrates SAFE with the Coordinate Descent

method. We call our method CD-SAFE, and we report the number of computations

needed for solving a LASSO problem using CD-SAFE and using the plain

Coordinate Descent method. We observe at least a $100$ fold reduction

in computational complexity for dense and sparse data-sets consisting

of millions of variables and millions of observations. Some of these

data-sets can cause memory problems when loaded, or need specialized

solvers. However, with SAFE, we can extend LASSO solvers capabilities

to treat large-scale problems, previously out of their reach. This

is possible, because SAFE eliminates variables and thus portions of

our data at the outset, before loading it into our memory.

We also show how our method can be extended to general $\ell_{1}$-regularized

convex problems. We present preliminary results for the Sparse Support

Vector Machine and Logistic Regression problems.

In the second topic of the thesis, we derive a method for open-loop

control of open channel flow, based on the Hayami model, a parabolic

partial differential equation resulting from a simplification of the

Saint-Venant equations. The open-loop control is represented as infinite

series using differential flatness, for which convergence is assessed.

Numerical simulations show the effectiveness of the approach by applying

the open-loop controller to irrigation canals modeled by the full

Saint-Venant equations.

We experiment with our controller on the Gignac Canal, located northwest

of Montpellier, in southern France. The experiments show that it is

possible to achieve a desired water flow at the downstream of a canal

using the Hayami model as an approximation of the real-system. However,

our observations of the measured water flow at the upstream controlled

gate made us realize some actuator limitations. For example, deadband

in the gate opening and unmodeled disturbances such as friction in

the gate-opening mechanism, only allow us to deliver piece-wise constant

control inputs. This fact made us investigate a way to compute a controller

that respects the actuator limitations. We use the CD-SAFE algorithm,

to compute such open-loop control for the upstream water flow. We

compare the computational effort needed to obtain an open-loop control

with certain dynamics using the CD-SAFE algorithm and the plain Coordinate

Descent algoirthm. We show that with CD-SAFE we are able to obain

an open-loop control signal with cheaper computations.

The phosphorelay is a ubiquitous biological module that plays a fundamental role in signal transduction and stress response coordination in organisms ranging from bacteria to plants. Despite their central role, the manner in which they integrate information is poorly understood. Furthermore, naturally occurring systems have a number of key architectural variations whose purpose remains mysterious. These variations include the number of stages in the relay, the number of proteins from which the relay is built, and the set of stages which are targeted by phosphatases and kinases.

In this work, I create a unified framework for understanding the function of phosphorelays and their architectural variations. Central to this investigation are a pair of models for the phosphorelay, one of which is an Ordinary Differential Equations based model, and the other of which is a Chemical Master Equation based model. The ODE based model is used to rigorously demonstrate that a phosphorelay is monotone, and thus converges to some steady state. In turn, the steady state output is elucidated in terms of the parameters that determine the net influx and net efflux at each stage as well as the growth rate.

This steady state output function provides an elaboration on a prior hypothesis which suggests that a long phosphorelay provides additional phosphoregulation targets. Specifically, we find that the output of a phosphorelay is proportional to the net influx rate divided by the sum of various products of efflux signals. In the large efflux signal limit, effluxes are effectively multiplied to generate the final output. In this way, the activity of phosphatases which act on multiple stages in the relay are multiplied, allowing the phosphorelay to act as an analog computation device for this specific function.

Growth is shown to have an unexpectedly powerful effect on relay output. In the most extreme cases, the phosphorelay output is shown to obey a power law with respect to growth, with an exponent which can be as large as the length of the relay, and which is also mediated by other key architectural variations. Thus, the phosphorelay can be utilized as a device which allows an organism to select behavior by comparing its growth rate to a threshold, where the level and sharpness of this threshold can be controlled by architectural and parametric changes. These results also provide design laws for building phosphorelays which are robust to growth rate variation.

Phosphorelays are also known to have a substantial effect on growth rate, and thus the relay and growth rate form a cross inhibitory loop. We show that under reasonable parametric conditions, a phosphorelay can thus be used as a hysteretic growth switch, and discuss the implications of this idea. Many of these ideas are then supported through numerical simulation of the ODE outside of the parametric conditions which allowed these ideas to be derived. They are further supported through investigation of a CME based model, and biological experiments are suggested that could validate these ideas. Finally, we discuss these results in the context of the Bacillus subtilis phosphorelay, whose output is known to affect the production of every relay protein but one. We hypothesize that this single feedback is missing in order to preserve the analog computation function.

Recently there have been vast interests in introducing robotic systems such as autonomous cars and UAVs into the real world. Ensuring the safety of these systems when they are deployed is thus a highly crucial and urgent problem. Safety problems can arise from various different settings such as when there are multiple vehicles or human-operated vehicles in the environment. Different safety-critical settings often require different approaches for addressing the safety of vehicles. In this dissertation, we contribute novel methods for safety problems that arise from three different scenarios.

First, we have seen a surge of interests in deploying autonomous vehicles into the everyday lives of people. Developing accurate and generalizable algorithms for modeling and predicting human behavior thus becomes important. We present a method for generating the probabilistic forward reachable set of a human-controlled vehicle in an environment where a robot is operating in close proximity to the human-controlled vehicle.

Second, motivated by the recent advances in deploying unmanned aerial vehicles into the airspace, we tackle the problem of multi-vehicle safety. We first contribute a planning and control strategy for guaranteeing safety of multiple vehicles while vehicles complete their objectives. We also present an initialization strategy based on machine learning to enhance the safety of multi-vehicle systems when they adopt least-restrictive safety-aware algorithms. Finally, machine learning has emerged as a promising tool to enable robots to accomplish challenging tasks under uncertainty in the dynamics of the robots or the environment. However, the safety of the robot while it's learning online is often not taken into account, which could lead to unsafe behavior of the robot. We present an online learning framework that enables a robot to learn about its dynamics, accomplish a task, and update its safe set simultaneously online.