Back to search

Michigan State University

Faster algorithms for machine learning problems in high dimension

Abstract

dc:description

"When dealing with datasets with high dimension, the existing machine learning algorithms often do not work in practice. Actually, most of the real-world data has the nature of low intrinsic dimension. For example, data often lies on a low-dimensional manifold or has a low doubling dimension. Inspired by this phenomenon, this thesis tries to improve the time complexities of two fundamental problems in machine learning using some techniques in computational geometry. In Chapter two, we propose a bi-criteria approximation algorithm for minimum enclosing ball with outliers and extend it to the outlier recognition problem. By virtue of the "core-set" idea and the Random Gradient Descent Tree, we propose an efficient algorithm which is linear in the number of points n and the dimensionality d, and provides a probability bound. In experiments, compared with some existing outlier recognition algorithms, our method is proven to be efficient and robust to the outlier ratios. In Chapter three, we adopt the "doubling dimension" to characterize the intrinsic dimension of a point set. By the property of doubling dimension, we can approximate the geometric alignment between two point sets by executing the existing alignment algorithms on their subsets, which achieves a much smaller time complexity. More importantly, the proposed approximate method has a theoretical upper bound and can serve as the preprocessing step of any alignment algorithm."--Page ii.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ye, Mingquan
Contributors dc:contributor
  • Ding, Hu
  • Torng, Eric
  • Tong, Yiying

Subjects

dc:subject × 3

Rights

dc:rights
Statement dc:rights
  • In Copyright
Language dc:language
English

Identifiers

dc:identifier.*
Identifier
etd:47868
isbn:9781392157640
isbn:1392157641
oclc:1117774702
umi:13881042
local:Ye_grad.msu_0128N_16814

Chain of custody

source
Harvested from
Michigan State University
Base URL
d.lib.msu.edu/oai
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Ye, Mingquan. Faster algorithms for machine learning problems in high dimension. 2019. https://doi.org/doi:10.25335/y842-1318