{"id":{"repo_id":"buffalo","oai_identifier":"oai:ubir.buffalo.edu:10477/78539"},"canonical_url":"https://search.dev.ndltd.org/etd/buffalo/oai:ubir.buffalo.edu:10477/78539","repository":{"repo_id":"buffalo","name":"Buffalo","base_url":"https://ubir.buffalo.edu/oai/request"},"display":{"title":"New Computational Geometry Methods for Some Fundamental Machine Learning Problems","abstract":"Ph.D.","abstract_html":"Ph.D.","abstract_has_math":false,"creators":["Wang, Xiangyu; 0000-0003-0575-7099"],"institution":"State University of New York at Buffalo","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Xu, Jinhui","Computer Science and Engineering"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018-10-26T02:55:03Z","date_published":"2018-10-26T02:55:03Z","updated_at":"2026-07-27T19:05:12Z","subjects":["computer science","computer engineering","artificial intelligence"],"languages":["eng"],"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."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/10477/78539","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Xu, Jinhui","Computer Science and Engineering"]},{"key":"dc:creator","label":"Author","values":["Wang, Xiangyu; 0000-0003-0575-7099"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2018-10-26T02:55:03Z","2018","2018-08-09 14:28:56"]},{"key":"dc:publisher","label":"Institution","values":["State University of New York at Buffalo"]},{"key":"dc:type","label":"Dc Type","values":["Text","Dissertation"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["computer science","computer engineering","artificial intelligence"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/10477/78539"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Ph.D.","Machine learning concerns the construction of techniques that can learn from and make predictions on data. The computational geometry can play a crucial and natural role in machine learning when exploring the data structure. In this research work, we develop several geometric algorithms to solve three fundamental but important machine learning problems. First, we propose a novel collaborative filtering approach for predicting the unobserved links in a network (or graph) with both topological and node features. Our approach improves the well-known compressed sensing based matrix completion method by introducing a new multiple-independent-Bernoulli-distribution model as the data sampling mask. It makes better link predictions since the model is more general and better matches the data distributions in many real-world networks, such as social networks like Facebook. Second, we consider the problem of clustering a set of uncertain data, where each of them consists of a point-set indicating its possible locations. The objective is to identify the representative point for each uncertain data point and group them into k clusters so as to minimize the total clustering cost. Our problem does not assume any given probability distribution for each uncertain data point, and thus needs to consider all points to determine its representative point. We propose a novel sparse Non-negative Matrix Factorization (NMF) method which measures the similarity of uncertain points by their most commonly shared features. Consequently, a divide-and-conquer approach can be adopted to dramatically improve the efficiency. A novel diagonal l0-constraint and its l1 relaxation are proposed to overcome the challenge of determining the representative points. Third, we address a fundamental re-weighted low rank approximation problem by proposing a novel accelerated Alternative Minimization (ALM) framework with momentum. In our problem, the method needs to synchronically adjust the weights according to related constraints, while factorizing the input matrix. We first eliminate the normal ALM procedures by performing an effective variable reduction on the original objective function. Then, to improve the robustness and further accelerate the ALM, we design a new intermediate acceleration stage on the weights and impose it into the existing Nesterov Accelerated Gradient Descent (NAG) scheme. Besides, our method is built for general ALM, including both convex and non-convex kernels. The outperforming convergence rate is confirmed by a solid analysis based on Kurdyka-Lojasiewicz property. The effectiveness of all the three works is fully supported by related theoretical analysis and experimental results on some benchmark datasets."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["New Computational Geometry Methods for Some Fundamental Machine Learning Problems"]}]}],"canonical_facts":{"dc:contributor":["Xu, Jinhui","Computer Science and Engineering"],"dc:creator":["Wang, Xiangyu; 0000-0003-0575-7099"],"dc:date":["2018-10-26T02:55:03Z","2018","2018-08-09 14:28:56"],"dc:description":["Ph.D.","Machine learning concerns the construction of techniques that can learn from and make predictions on data. The computational geometry can play a crucial and natural role in machine learning when exploring the data structure. In this research work, we develop several geometric algorithms to solve three fundamental but important machine learning problems. First, we propose a novel collaborative filtering approach for predicting the unobserved links in a network (or graph) with both topological and node features. Our approach improves the well-known compressed sensing based matrix completion method by introducing a new multiple-independent-Bernoulli-distribution model as the data sampling mask. It makes better link predictions since the model is more general and better matches the data distributions in many real-world networks, such as social networks like Facebook. Second, we consider the problem of clustering a set of uncertain data, where each of them consists of a point-set indicating its possible locations. The objective is to identify the representative point for each uncertain data point and group them into k clusters so as to minimize the total clustering cost. Our problem does not assume any given probability distribution for each uncertain data point, and thus needs to consider all points to determine its representative point. We propose a novel sparse Non-negative Matrix Factorization (NMF) method which measures the similarity of uncertain points by their most commonly shared features. Consequently, a divide-and-conquer approach can be adopted to dramatically improve the efficiency. A novel diagonal l0-constraint and its l1 relaxation are proposed to overcome the challenge of determining the representative points. Third, we address a fundamental re-weighted low rank approximation problem by proposing a novel accelerated Alternative Minimization (ALM) framework with momentum. In our problem, the method needs to synchronically adjust the weights according to related constraints, while factorizing the input matrix. We first eliminate the normal ALM procedures by performing an effective variable reduction on the original objective function. Then, to improve the robustness and further accelerate the ALM, we design a new intermediate acceleration stage on the weights and impose it into the existing Nesterov Accelerated Gradient Descent (NAG) scheme. Besides, our method is built for general ALM, including both convex and non-convex kernels. The outperforming convergence rate is confirmed by a solid analysis based on Kurdyka-Lojasiewicz property. The effectiveness of all the three works is fully supported by related theoretical analysis and experimental results on some benchmark datasets."],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/10477/78539"],"dc:language":["eng"],"dc:publisher":["State University of New York at Buffalo"],"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."],"dc:subject":["computer science","computer engineering","artificial intelligence"],"dc:title":["New Computational Geometry Methods for Some Fundamental Machine Learning Problems"],"dc:type":["Text","Dissertation"]},"updated_at":"2026-07-27T19:05:12Z"}