5
$\begingroup$

This is less of a question and more of a "here's my take let me know if you agree" (so I guess it might turn into a big-list?).

Dimensionality reduction refers to a collection of techniques that input data and return a lower-dimensional version, with some distortion. PCA and Johnson-Lindenstrauss are the most common examples.

From an algorithmic perspective, the tradeoff is clear: lower dimensionality yields faster runtimes and reduced storage space, but compromises precision. I call this the dimension-distortion tradeoff.

From a statistical/information-theoretic perspective, the situation seems less clear. It is commonly believed that dimensionality reduction (PCA in particular) has a denoising effect and thus should actually improve the performance. On the other hand, dimensionality reduction does discard information, which might cause the performance to degrade. Thus, one must address the statistical question: is the information I'm discarding noise or potentially useful (and even if useful, might the benefits of lower dimension still outweigh the losses)?

There appear to be very few formal analyses of the statistical benefits of dimensionality reduction. One that I'm aware of is in our ALT'13 paper (with Gottlieb and Krauthgramer). The setting there is fairly general -- metric spaces.

Are there other formal analyses of the statistical benefits of dimensionality reduction? Perhaps other tradeoffs besides those mentioned above?

Improve this question
$\endgroup$
7
  • $\begingroup$ I'm not sure about information-theoretic perspective, but in the (very) noisy field of information retrieval, I'm unfamiliar with a work which showed improvement in precision when using dimension reduction. $\endgroup$
    – R B
    Apr 22, 2015 at 14:50
  • $\begingroup$ the question is a bit weird wrt actual ML technology. actually dimensionality reduction itself/ alone eg PCA has been proven a very powerful ML technique (eg in line with performance with other top learning methods for some problems). winning algorithms in the netflix prize contest (for rating prediction) evoked PCA heavily. there are several papers on that. then there are other contexts where yes, it loses valuable info. dimensionality reduction is considered a fairly basic/ std "preprocessing" step for ML/ big data analysis etc & its really just a matter of "how much" to apply. $\endgroup$
    – vzn
    Apr 22, 2015 at 17:54
  • $\begingroup$ When you say "has proven", do you mean just heuristically/empirically (which is undeniable) or also rigorously? $\endgroup$
    – Aryeh
    Apr 22, 2015 at 18:44
  • $\begingroup$ ah that is in the informal sense. there are rigorous empirical/ scientific analyses. but possibly this area is largely inherently outside of proof/ theory/ abstract analysis (actually a lot of ML is like that) because its wrt a statistical property of particular datasets. some are "compressible", others are not. $\endgroup$
    – vzn
    Apr 23, 2015 at 1:27
  • 1
    $\begingroup$ It sounds like you'd want generalization bounds for the supervised equivalents of dimensionality reduction, i.e things like LDA and FDA. There are results for FDA, for example arxiv.org/pdf/1208.3030v2.pdf $\endgroup$
    – Suresh Venkat
    Apr 25, 2015 at 5:55

3 Answers 3

Reset to default
3
$\begingroup$

Information Geometry is a rigorous framework which combines statistical inference, information theory and differential geometry.

Several open problems in statistics (and geometry) have found a new formulation and solution. Specificaly the concept of dual connections and dualy-flat spaces. It has been shown that various statistical inference methods (e.g maximum likelihood, EM algorithm etc.) can be formulated in terms of dualy-flat spaces in a statistical manifold (reference "Methods of Information Geometry", Amari, Nagaoka). The new formulation allows a unified view of previously un-related methods and algorithms.

The problem of dimensionality reduction and PCA has been formulated information-geometricaly as follows (with emphasis on information):

  1. "Information-Geometric Dimensionality Reduction"
  2. "An Information Geometric Framework for Dimensionality Reduction"
  3. "The e-PCA and m-PCA: Dimension Reduction of Parameters by Information Geometry"
Improve this answer
$\endgroup$
0
$\begingroup$

You might take a look at (Hotelling, 1933) which defines PCA as a orthogonal projection into a lower dimensional subspace maximizing the variance of the projected data. (Bishop 2006) might be easier to come by and contains a derivation of PCA based on this definition in chapter 12.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Sure, it's a fortuitous and esthetic feature of PCA that maximizing the variance turns out to minimize the $\ell_2$ distortion. Still my question remains: how does PCA actually help in learning? Our ALT'13 paper shows that it doesn't harm, provided the cutoff is chosen appropriately (we show how). $\endgroup$
    – Aryeh
    Apr 24, 2015 at 14:00
-2
$\begingroup$

agreed this is not studied in general so much. part of the theoretical challenge/ difficulty is its highly dataset- and algorithm-specific (in the sense that different datasets & ML techniques are more or less sensitive to the "dimension-distortion tradeoff"). often dimensionality reduction is regarded as a tunable/ optimizable parameter along with all the other ML parameters and some quality metric intrinsic to the problem (also measuring learning success/ "generalization") is used to determine how much to apply. typically the performance of the ML algorithm declines if either too little or too much dimensionality reduction is applied.

however re "formal analysis/ tradeoffs of dimensionality reduction," newly emerging, try this large paper, which looks at how the Johnson-Lindenstrauss reduction affects datapoint proximity wrt a distance metric & lays out a more general theoretical framework. 60pp

as mentioned in the comments, one great applied case study in this type of big data problem & the relevance of PCA/ dimensionality reduction with major statistical/ scientific analysis is in the Netflix prize for movie ratings prediction. prior to the contest, PCA type approaches were somewhat rarely applied to human ratings predictions. however they were found to be extremely effective in this contest combined with careful tuning/ conditioning. the winning solutions used large "blends" of many different techniques but PCA related algorithms composed many of them.

moreover, sometimes mostly PCA alone without further learning algorithms applied on top of this data was enough as an effective/ top performing prediction algorithm. in this case one could say that most of the statistical trends in the data were apparently "identified" by PCA and what was "left over" (the "residual") was either not substantial or noisy. this contest had a $1M prize awarded to collaborating teams and eventually Netflix decided to employ many of these techniques in their live production system.

see eg

Improve this answer
$\endgroup$
2
  • $\begingroup$ Sparsity adds an additional parameter (shall we say "dimension"?) to the dimension-distortion treadeoff. Even though sparsity plays a huge role in modern statistics, I don't think the information-theoretic consideration is playing a role in that Bourgain et al. paper. $\endgroup$
    – Aryeh
    Apr 23, 2015 at 7:34
  • $\begingroup$ ok its focused on sparsity but it seems to give a overarching rationale/ framework for "why" dimensionality reduction "works". ie distances in the reduced space are roughly like distances in the unreduced space. and any general framework for dimensionality reduction probably would have to take into account sparsity, or sparsity might even play a key role... $\endgroup$
    – vzn
    Apr 23, 2015 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.