Exploiting Special Structures in High-Dimensional Data Classification

本文的研究为高维数据分类提供了新的实用方法和算法以及理论成果。主要问题是当测量变量的数量远远超过观测值的数量时，精确估计完整的协方差矩阵是不可能的。研究者先前已经证明，在这种情况下完全忽略依赖性是一个更好的选择，但这意味着丢弃大量信息。 这个问题将通过开发新的稀疏协方差估计来解决，这些估计将只保留重要的依赖信息，并在判别分析的背景下从理论上研究它们的行为。新的实用，计算效率高的算法计算这些估计从数据将开发的聚类和graph partitioningmethods的基础上，并与现有的正则化技术。从理论上讲，渐近最优或接近最优的分类性能有望得到证明。 另一种减小问题规模并获得底层结构的方法是使用最近发展的非线性流形投影方法来降低数据维数，该方法旨在发现包含数据中包含的大部分信息的非线性低维嵌入。使用这些方法需要估计流形上的内在数据维数和邻域尺度，并提出了新的严格估计，沿着分析其统计性质。 仔细估计这两个参数将改善目前机器学习中使用的大多数启发式方法，并增加流形投影方法在高维数据分类中的适用性。该提议通过开发新的理论和实践工具来处理高维数据，特别是在一次观测的测量次数相对于观测次数较大的情况下。 本文提出了一种新的稀疏估计方法，它只包含与数据分类有关的信息。 新的估计器也可以用于任何问题，其中大的协方差矩阵需要估计从有限的数据量，因此将有一个广泛的现代应用的影响，如分类和分析的基因表达数据，分析复杂的化学和物理实验，遥感和医学成像等。

ABSTRACTProposed research develops new practical methodology and algorithms aswell as theoretical results for high-dimensional data classification. Themain issue is that when the number of measured variables exceeds by farthe number of observations, estimating the full covariance matrixaccurately is impossible. The investigator has previously shown thatignoring the dependence completely in such a situation is a better option,but it means discarding a lot of information. This problem will beresolved by developing new sparse covariance estimators which will onlyretain important dependence information, and studying their behaviortheoretically in the context of discriminant analysis. New practical,computationally efficient algorithms for computing these estimators fromdata will be developed on the basis of clustering and graph partitioningmethods and compared to existing regularization techniques. Theoretically,asymptotically optimal or near optimal classification performance isexpected to be demonstrated. Another way to reduce the size of theproblem and get to the underlying structure is to reduce the datadimension using recently developed nonlinear manifold projection methods,which aim to discover a nonlinear low-dimensional embedding preservingmost of the information contained in the data. Using these methodsrequires estimating intrinsic data dimension and neighborhood scale on amanifold, and new rigorous estimators for both are proposed, along with ananalysis of their statistical properties. Careful estimation of these twoparameters will improve on the current mostly heuristic methods used inmachine learning and increase applicability of manifold projection methodsfor high-dimensional data classification.This proposal addresses the new challenges posed by the massive amounts ofdata collected in the modern world by developing new theoretical andpractical tools for dealing with high-dimensional data, particularly withthe situation when the number of measurements taken for one observation islarge relative to the number of observations. New sparse estimators ofdependence structure in such data are developed, which only contain theinformation relevant for data classification. The new estimators can alsobe used in any problem where large covariance matrices need to beestimated from limited amount of data, and hence will have an impact on awide range of modern applications, such as classification and analysis ofgene expression data, analysis of complex chemical and physicalexperiments, remote sensing, and medical imaging, among others.