<p><a href="http://en.wikipedia.org/wiki/Information_geometry" rel="nofollow">Information Geometry</a> is a rigorous framework which combines statistical inference, information theory and differential geometry.</p>

<p>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.</p>

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

<ol>
<li><a href="http://web.eecs.umich.edu/~hero/Preprints/carter_spsmag_igdr_rev3.pdf" rel="nofollow">"Information-Geometric Dimensionality Reduction"</a></li>
<li><a href="http://arxiv.org/pdf/0809.4866.pdf" rel="nofollow">"An Information Geometric Framework for Dimensionality Reduction"</a></li>
<li><a href="https://staff.aist.go.jp/s.akaho/papers/ijcnn-akaho.pdf" rel="nofollow">"The e-PCA and m-PCA: Dimension Reduction of Parameters by Information Geometry"</a></li>
</ol>

CC BY-SA 3.0
2015-04-27T21:36:55.653Z
2015-04-27T21:36:55.653Z
Nikos M.
<p>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. </p>

CC BY-SA 3.0
2015-04-24T14:00:51.317Z
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).
Aryeh
CC BY-SA 3.0
2015-04-24T01:12:59.840Z
2015-04-24T01:12:59.840Z
Jeremy Millar
<p>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 &amp; 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.</p>

<p>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 &amp; lays out a more general theoretical framework. 60pp</p>

<ul>
<li><a href="http://arxiv.org/pdf/1311.2542v3.pdf" rel="nofollow">TOWARD A UNIFIED THEORY OF SPARSE DIMENSIONALITY REDUCTION IN EUCLIDEAN SPACE
</a> / BOURGAIN, DIRKSEN, NELSON</li>
</ul>

<p>as mentioned in the comments, one great applied case study in this type of big data problem &amp; 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. </p>

<p>moreover, sometimes mostly PCA <em>alone</em> 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.</p>

<p>see eg</p>

<ul>
<li><p><a href="http://www.netflixprize.com/assets/GrandPrize2009_BPC_BellKor.pdf" rel="nofollow">The BellKor Solution to the Netflix Grand Prize</a> / Koren</p></li>
<li><p><a href="http://www.netflixprize.com/assets/ProgressPrize2008_BigChaos.pdf" rel="nofollow">The BigChaos Solution to the Netflix Prize 2008</a> / Toscher &amp; Jahrer</p></li>
</ul>

CC BY-SA 3.0
2015-04-23T07:34:13.500Z
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.
Aryeh
CC BY-SA 3.0
2015-04-23T15:13:01.330Z
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...
vzn
CC BY-SA 3.0
2015-04-23T02:22:43.853Z
2015-04-23T02:22:43.853Z
vzn
<p>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?).</p>

<p><em>Dimensionality reduction</em> refers to a collection of techniques that input data and return a lower-dimensional version, with some distortion. <a href="http://en.wikipedia.org/wiki/Principal_component_analysis">PCA</a> and <a href="http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma">Johnson-Lindenstrauss</a> are the most common examples.</p>

<p>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.</p>

<p>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)?</p>

<p>There appear to be very few formal analyses of the statistical benefits of dimensionality reduction. One that I'm aware of is in our 
<a href="https://dl.dropboxusercontent.com/u/3198145/dimred-tcs.pdf">ALT'13</a>
 paper (with Gottlieb and Krauthgramer). The setting there is fairly general -- metric spaces.</p>

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

CC BY-SA 3.0
2015-04-22T14:50:33.497Z
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.
R B
CC BY-SA 3.0
2015-04-22T17:54:12.010Z
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.
vzn
CC BY-SA 3.0
2015-04-22T18:44:45.980Z
When you say "has proven", do you mean just heuristically/empirically (which is undeniable) or also rigorously?
Aryeh
CC BY-SA 3.0
2015-04-23T01:27:50.653Z
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.
vzn
CC BY-SA 3.0
2015-04-25T05:55:15.583Z
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 http://arxiv.org/pdf/1208.3030v2.pdf
Suresh Venkat
CC BY-SA 3.0
2015-04-25T18:28:28.187Z
Thanks, Suresh -- this indeed seems to be along the lines I was asking!
Aryeh
CC BY-SA 3.0
2015-04-27T21:17:38.553Z
usually in optimisation or machine learning what one does is set a threshold or limit (eg 70% of information) and then after PCA discard the 30% lower subspace (meaning eignevalues and associated eigenvectors). However this is an open problem , i.e finding the optimum threshold. Furthermore there are non-linearities present whichb a linear technique like PCA cannot handle without using other transformations on the data as well
Nikos M.
<machine-learning><lg.learning>
Dimensionality reduction in machine learning
Aryeh
# Dimensionality reduction in machine learning

(Asked by: username_0 on 2015-04-22)

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](http://en.wikipedia.org/wiki/Principal_component_analysis) and [Johnson-Lindenstrauss](http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma) 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](https://dl.dropboxusercontent.com/u/3198145/dimred-tcs.pdf)
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?

**Tags:** machine-learning, lg.learning
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_0**: When you say "has proven", do you mean just heuristically/empirically (which is undeniable) or also rigorously?  
> **username_2**: 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.  
> **username_3**: 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 http://arxiv.org/pdf/1208.3030v2.pdf  
> **username_0**: Thanks, Suresh -- this indeed seems to be along the lines I was asking!  
> **username_4**: usually in optimisation or machine learning what one does is set a threshold or limit (eg 70% of information) and then after PCA discard the 30% lower subspace (meaning eignevalues and associated eigenvectors). However this is an open problem , i.e finding the optimum threshold. Furthermore there are non-linearities present whichb a linear technique like PCA cannot handle without using other transformations on the data as well  

---

## 3 answers

### Answer by username_4 on 2015-04-27. Score: 3

[Information Geometry](http://en.wikipedia.org/wiki/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"](http://web.eecs.umich.edu/~hero/Preprints/carter_spsmag_igdr_rev3.pdf)
2. ["An Information Geometric Framework for Dimensionality Reduction"](http://arxiv.org/pdf/0809.4866.pdf)
3. ["The e-PCA and m-PCA: Dimension Reduction of Parameters by Information Geometry"](https://staff.aist.go.jp/s.akaho/papers/ijcnn-akaho.pdf)


---

### Answer by username_5 on 2015-04-24. Score: 0

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.

> **Comments:**
> **username_0**: 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).  

---

### Answer by username_2 on 2015-04-23. Score: -2

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

* [TOWARD A UNIFIED THEORY OF SPARSE DIMENSIONALITY REDUCTION IN EUCLIDEAN SPACE](http://arxiv.org/pdf/1311.2542v3.pdf) / BOURGAIN, DIRKSEN, NELSON

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

* [The BellKor Solution to the Netflix Grand Prize](http://www.netflixprize.com/assets/GrandPrize2009_BPC_BellKor.pdf) / Koren
* [The BigChaos Solution to the Netflix Prize 2008](http://www.netflixprize.com/assets/ProgressPrize2008_BigChaos.pdf) / Toscher & Jahrer

> **Comments:**
> **username_0**: 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.  
> **username_2**: 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...  

---

