UC Davis

Geometry plays a crucial role in machine learning. We study the geometric properties of machine learning problems and use that information to develop new algorithms that are accurate and efficient. We present three works that lie at the intersection of machine learning and geometry, and we hope to promote more research on geometry-inspired machine learning methods.

We first introduce \textit{geometric policy iteration}~(GPI), a new dynamic programming approach for finite Markov decision process. Recently discovered polyhedral structures of the value function for finite discounted Markov decision processes (MDP) shed light on understanding the success of reinforcement learning. We investigate the value function polytope in greater detail and characterize the polytope boundary using a hyperplane arrangement. We further show that the value space is a union of finitely many cells of the same hyperplane arrangement, and relate it to the polytope of the classical linear programming formulation for MDPs. Inspired by these geometric properties, we propose GPI to solve discounted MDPs. GPI updates the policy of a single state by switching to an action that is mapped to the boundary of the value function polytope, followed by an immediate update of the value function. This new update rule aims at a faster value improvement without compromising computational efficiency. Moreover, our algorithm allows asynchronous updates of state values which is more flexible and advantageous compared to traditional policy iteration when the state set is large. We prove that the complexity of GPI achieves the best known bound $\bigO{\frac{|\actions|}{1 - \gamma}\log \frac{1}{1-\gamma}}$ of policy iteration and empirically demonstrate the strength of GPI on MDPs of various sizes.

In the second project, we consider the \emph{integer feasibility problem}, the challenge of deciding whether a system of linear equations and inequalities has a solution with integer values. This is a famous NP-complete problem with applications in many areas of Mathematics and Computer Science. We show that the integer feasibility problem can be transformed into a 3-D tensor game which we call the \textit{Feasibility Game}~(FG). To win the game the player must find a path between the initial state and a final terminal winning state, if one exists. Finding such a winning state is equivalent to solving the integer feasibility problem. The key algebraic ingredient is a Gr\"obner basis of the toric ideal for the underlying axial transportation polyhedron. The Gr\"obner basis can be seen as a set of connecting moves (actions) of the game. We then propose a novel RL approach that trains an agent to predict moves in continuous space to cope with the large size of action space. The continuous move is then projected onto the set of legal moves so that the path always leads to valid states. As a proof of concept we demonstrate in experiments that our agent can play well the simplest version of our game for 2-way tables. Our work highlights the potential to train agents to solve non-trivial mathematical queries through contemporary machine learning methods used to train agents to play games.

% In the third project, we applied persistence-based clustering for microglia segmentation which is a critical problem in biology and immunology. Light microscopy methods have continued to advance allowing for unprecedented analysis of various cell types in tissues including the brain. Although the functional state of some cell types such as microglia can be determined by morphometric analysis, techniques to perform robust, quick, and accurate measurements have not kept pace with the amount of imaging data that can now be generated. Here we present PrestoCell, a novel use of persistence-based clustering to segment cells in light microscopy images, as a customized Python-based tool that leverages the free visualization tool Napari. In evaluating and comparing PrestoCell to several existing tools, including a commercial machine-learning implementation, we demonstrate that PrestoCell produces image segmentations that rival or exceed existing solutions. In particular, our use of cell nuclei information resulted in the ability to correctly segment individual cells that were interacting with one another, increasing the accuracy of the segmentation. These benefits are in addition to the simplified graphically based user refinement of cell masks that does not require expensive commercial software licenses. We further demonstrate that PrestoCell can complete image segmentation in large samples from light sheet microscopy, allowing quantitative analysis of these large datasets. As an open-source program that leverages freely available visualization software, with minimum computer requirements, we believe that PrestoCell can significantly increase the ability of users without data or computer science expertise to perform complex image analysis.

In the third work, we develop \textit{PrestoCell} which is a Python-based topological framework for segmenting objects with complex shapes. The main contribution of this work is the use of persistence-based clustering~(PBC) to generate segmentations that are topologically correct. Specifically, we use PBC to segment microglia whose 0-d homology is 1 (one connected component), and higher-order homology is 0. PBC, as an unsupervised method, is able to generate high-quality clusters that can be easily improved by some post-processing steps. Our framework is able to take as input very large 3D light microscopy imaging data where a single input volume can contain hundreds of microglia and nuclei. We use PBC to quickly generate candidate microglia clusters which are later refined by the coupled nuclei information. We present the machine-generated segmentation in the free visualization tool Napari. In evaluating and comparing PrestoCell to several existing tools, including a commercial machine-learning implementation, we demonstrate that PrestoCell produces image segmentations that rival or exceed existing solutions. In particular, our use of cell nuclei information resulted in the ability to correctly segment individual cells that were interacting with one another, increasing the accuracy of the segmentation. These benefits are in addition to the simplified graphically based user refinement of cell masks that does not require expensive commercial software licenses. We further demonstrate that PrestoCell can complete image segmentation in large samples from light sheet microscopy, allowing quantitative analysis of these large datasets. As an open-source program that leverages freely available visualization software, with minimum computer requirements, we believe that PrestoCell can significantly increase the ability of users without data or computer science expertise to perform complex image analysis.