High-Dimensionality Classification
Burkay Birant Orten (PhD ’11)
Prof. Prakash Ishwar, Prof. W. Clem Karl, Prof. Venkatesh Saligrama, Dr. Homer Pien (Mass. General Hospital)
Funding: U.S. Department of Homeland Security, U.S. Air Force Office of Scientific Research
Background: In many important applications, decisions must be made about the state of an object, such as diagnosing the presence or absence of a stroke in the brain from CT data, identifying abnormal activity in a sensor network from network measurements or determining whether a package is suspicious or not from video imagery. Such problems are further complicated when the object of interest is indirectly related to the observed data through a sensing process, as arises in tomographic projection data. A common approach in such situations is to first solve an inverse problem, transforming the observed data, and then to make decisions on the inverted or transformed data. Such data inversion can be extremely costly, require knowledge of the sensing model, and, if done poorly, introduce undesired artifacts into the resulting transformed data that can confound subsequent analysis. An alternative approach is to build classifiers directly in the original high-dimensional data domain. But then knowledge of the sensing process is generally treated as an unknown hidden structure and often ignored. Such sensing problems also arise in econometrics where the aim is understanding of market risk factors; in drug response studies where gene array data can predict whether a group of patients will benefit from drug therapy; and in oncology where breast cancer DNA micro-arrays demonstrate certain properties of the underlying tumor. In this work we study a third path we term “sensing-aware classification” that couples observed data with prior information concerning sensing models for data-domain classification.
Description: We’re examining how incorporation of different types of such prior information about the sensing model affects asymptotic classification performance. Our aim is to contribute to a rigorous analysis and understanding of such challenging problems. To this end, we consider an abstracted binary classification problem with the following elements:
- High dimensional observations
- A restricting sensing configuration
- Unknown statistical models of noise and object
- Estimation of class models from constrained training data
- Fixed signal-to-noise ratio (SNR) observations
We study the effects of different types of prior knowledge concerning the sensing model on classification performance relative to the naive Fisher approach assuming no knowledge and full training of the model from available data samples. We prove that asymptotically the Fisher approach is no better than guessing while incorporation of various forms of prior sensing knowledge can result in classification performance as good as if complete model information were available. In particular, we prove that certain projection-based classifiers can achieve this optimal performance under assumptions on the structure of the sensing mechanism.
Results: We considered a sensing-aware approach to classification involving high-dimensional observations coupled with constrained training data. We showed that the popular Fisher rule, which ignores the sensing structure asymptotically, performs no better than random guessing. Then we demonstrated that complete knowledge of the sensing model can be used to asymptotically obtain optimal Bayes performance in the presence of unknown object and noise models. We also investigated two methods that attempt to incorporate varying degrees of prior sensing model information to estimate linear sensing structure. We proved that using the obvious sample mean estimator fails due to its high variance. Finally, we identified a class of sensing models for which a truncation based regularization approach again yields asymptotically optimal classification performance. Performance of different methods in terms of their misclassification probability is compared in the figure below.
Publications:
Burkay Orten et al, “Sensing-Aware Classification with High-Dimensional Data,”36th International Conference on Acoustics, Speech and Signal Processing, Prague, May 22-27, 2011.