Necessary and sufficient conditions for high-dimensional salient feature subset recovery
We consider recovering the salient feature subset for distinguishing between two probability models from i.i.d. samples. Identifying the salient set improves discrimination performance and reduces complexity. The focus in this work is on the high-dimensional regime where the number of variables d, t...
| প্রধান লেখক: | , , |
|---|---|
| অন্যান্য লেখক: | |
| বিন্যাস: | প্রবন্ধ |
| ভাষা: | en_US |
| প্রকাশিত: |
Institute of Electrical and Electronics Engineers (IEEE)
2012
|
| অনলাইন ব্যবহার করুন: | http://hdl.handle.net/1721.1/73588 https://orcid.org/0000-0003-0149-5888 |
| _version_ | 1826189288851636224 |
|---|---|
| author | Tan, Vincent Yan Fu Johnson, Matthew James Willsky, Alan S. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Tan, Vincent Yan Fu Johnson, Matthew James Willsky, Alan S. |
| author_sort | Tan, Vincent Yan Fu |
| collection | MIT |
| description | We consider recovering the salient feature subset for distinguishing between two probability models from i.i.d. samples. Identifying the salient set improves discrimination performance and reduces complexity. The focus in this work is on the high-dimensional regime where the number of variables d, the number of salient variables k and the number of samples n all grow. The definition of saliency is motivated by error exponents in a binary hypothesis test and is stated in terms of relative entropies. It is shown that if n grows faster than max{ck log((d-k)/k), exp(c'k)} for constants c, c', then the error probability in selecting the salient set can be made arbitrarily small. Thus, n can be much smaller than d. The exponential rate of decay and converse theorems are also provided. An efficient and consistent algorithm is proposed when the distributions are graphical models which are Markov on trees. |
| first_indexed | 2024-09-23T08:12:46Z |
| format | Article |
| id | mit-1721.1/73588 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:12:46Z |
| publishDate | 2012 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/735882022-09-30T08:19:22Z Necessary and sufficient conditions for high-dimensional salient feature subset recovery Tan, Vincent Yan Fu Johnson, Matthew James Willsky, Alan S. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Tan, Vincent Yan Fu Johnson, Matthew James Willsky, Alan S. We consider recovering the salient feature subset for distinguishing between two probability models from i.i.d. samples. Identifying the salient set improves discrimination performance and reduces complexity. The focus in this work is on the high-dimensional regime where the number of variables d, the number of salient variables k and the number of samples n all grow. The definition of saliency is motivated by error exponents in a binary hypothesis test and is stated in terms of relative entropies. It is shown that if n grows faster than max{ck log((d-k)/k), exp(c'k)} for constants c, c', then the error probability in selecting the salient set can be made arbitrarily small. Thus, n can be much smaller than d. The exponential rate of decay and converse theorems are also provided. An efficient and consistent algorithm is proposed when the distributions are graphical models which are Markov on trees. 2012-10-04T13:32:45Z 2012-10-04T13:32:45Z 2010-07 2010-06 Article http://purl.org/eprint/type/ConferencePaper 978-1-4244-7891-0 978-1-4244-7890-3 http://hdl.handle.net/1721.1/73588 Tan, Vincent Y. F., Matthew Johnson, and Alan S. Willsky. “Necessary and Sufficient Conditions for High-dimensional Salient Feature Subset Recovery.” IEEE International Symposium on Information Theory Proceedings (ISIT), 2010. 1388–1392. ©2010 IEEE https://orcid.org/0000-0003-0149-5888 en_US http://dx.doi.org/10.1109/ISIT.2010.5513598 Proceedings of the IEEE International Symposium on Information Theory Proceedings (ISIT), 2010 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers (IEEE) IEEE |
| spellingShingle | Tan, Vincent Yan Fu Johnson, Matthew James Willsky, Alan S. Necessary and sufficient conditions for high-dimensional salient feature subset recovery |
| title | Necessary and sufficient conditions for high-dimensional salient feature subset recovery |
| title_full | Necessary and sufficient conditions for high-dimensional salient feature subset recovery |
| title_fullStr | Necessary and sufficient conditions for high-dimensional salient feature subset recovery |
| title_full_unstemmed | Necessary and sufficient conditions for high-dimensional salient feature subset recovery |
| title_short | Necessary and sufficient conditions for high-dimensional salient feature subset recovery |
| title_sort | necessary and sufficient conditions for high dimensional salient feature subset recovery |
| url | http://hdl.handle.net/1721.1/73588 https://orcid.org/0000-0003-0149-5888 |
| work_keys_str_mv | AT tanvincentyanfu necessaryandsufficientconditionsforhighdimensionalsalientfeaturesubsetrecovery AT johnsonmatthewjames necessaryandsufficientconditionsforhighdimensionalsalientfeaturesubsetrecovery AT willskyalans necessaryandsufficientconditionsforhighdimensionalsalientfeaturesubsetrecovery |