New Geometric Approaches for Several Machine Learning Problems

Computational geometry has found applications in many different real world problems– both theoretical and applicational ones. In this dissertation, we apply geometric techniques to multiple problems, including traditional machine learning problems, deep learning related problems, and a biological problem that can be modeled as a graph matching problem. Distributed SVM and Online SVM. Support Vector Machine (SVM) is an effective classification technique widely used in various machine learning applications. While having a theoretically guaranteed good classification accuracy, training an SVM can be challenging when the size of the training set is large, which is often the case in the big data era. For instance, a huge amount of data might be obtained in distributed sites and communication between different sites could be expensive. Thus a distributed SVM algorithm with low communication cost is desired. It is also possible that the size of the training set might be too large to ft into RAM. Thus an online SVM algorithm with low space complexity is expected. Clustering in the Presence of Large Amount of Sparse Noise. We consider the problem of clustering with a heavy amount of sparse background noise (over 80% of the data). We propose a practical density based clustering method, combining with the strength of Minimum Spanning Tree based clustering, Locality Sensitive Hashing and Deep Neural Networks. Our algorithm first uses MST based clustering for high confidence label initialization, and then learns a mapping from the original data space to a relatively low dimensional latent space as a deep neural network, based on the labels obtained from the MST clustering. In the latent space, data are clustered based on local density, following the assumption that a point is more likely to belong to a cluster if its distance to the nearest neighbor in that cluster is small. We use locality sensitive hashing as the nearest neighbor search engine to handle the possibly high dimensional data. Experiments on both synthetic and real world datasets (with added noise) suggest that our method is capable of handling heavy noise and significantly outperforms popular existing methods. Alignment of Protein-Protein-Interaction (PPI) Network. In biology, two proteins within a cell are said to be interacting if they are close to each other geometrically. Thus the PPI network is an undirected node-edge graph with some extra biological information stored at each node. Studying the alignment of two PPI networks are promising in discovering new functionality of different proteins. Since the alignment of PPI network can be treated as a generalized graph isomorphism problem which is NP-hard and notoriously challenging, current research has focused on finding algorithms with good practical performance. We developed a geometry based alignment algorithm for the global alignment of two PPI networks, which consists of a geometric step of embedding the network into a low dimensional Euclidean space and using geometric matching methods to find a matching, and a min-cost-max-fow step to handle the sequence similarity in-formation stored in each node. Unlike other popular alignment algorithms which are either greedy or incremental, our algorithm globally optimizes the problem to yield an alignment with better quality.

Grantor dc:publisher

State University of New York at Buffalo

Year dc:date.issued

2018

Author dc:creator

• Liu, Yangwei

Contributors dc:contributor

• Xu, Jinhui
• Computer Science and Engineering

• computer science

Statement dc:rights

• Users of works found in University at Buffalo Institutional Repository (UBIR) are responsible for identifying and contacting the copyright owner for permission to reuse. University at Buffalo Libraries do not manage rights for copyright-protected works and cannot assist with permissions.
• Copyright retained by author.

Language dc:language

eng

Handle dc:identifier

http://hdl.handle.net/10477/77976

OAI record oai:identifier

https://ubir.buffalo.edu/oai/request?verb=GetRecord&metadataPrefix=qdc&identifier=oai%3Aubir.buffalo.edu%3A10477%2F77976