On feature selection : learning with exponentially many irreverent features as training examples
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1998.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/9658 |
| _version_ | 1826210612721483776 |
|---|---|
| author | Ng, Andrew Y., 1976- |
| author2 | Michael I. Jordan. |
| author_facet | Michael I. Jordan. Ng, Andrew Y., 1976- |
| author_sort | Ng, Andrew Y., 1976- |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1998. |
| first_indexed | 2024-09-23T14:52:43Z |
| format | Thesis |
| id | mit-1721.1/9658 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T14:52:43Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/96582019-04-12T16:04:19Z On feature selection : learning with exponentially many irreverent features as training examples Ng, Andrew Y., 1976- Michael I. Jordan. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science Electrical Engineering and Computer Science Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1998. Includes bibliographical references (p. 55-57). We consider feature selection for supervised machine learning in the "wrapper" model of feature selection. This typically involves an NP-hard optimization problem that is approximated by heuristic search for a "good" feature subset. First considering the idealization where this optimization is performed exactly, we give a rigorous bound for generalization error under feature selection. The search heuristics typically used are then immediately seen as trying to achieve the error given in our bounds, and succeeding to the extent that they succeed in solving the optimization. The bound suggests that, in the presence of many "irrelevant" features, the main somce of error in wrapper model feature selection is from "overfitting" hold-out or cross-validation data. This motivates a new algorithm that, again under the idealization of performing search exactly, has sample complexity ( and error) that grows logarithmically in the number of "irrelevant" features - which means it can tolerate having a number of "irrelevant" features exponential in the number of training examples - and search heuristics are again seen to be directly trying to reach this bound. Experimental results on a problem using simulated data show the new algorithm having much higher tolerance to irrelevant features than the standard wrapper model. Lastly, we also discuss ramifications that sample complexity logarithmic in the number of irrelevant features might have for feature design in actual applications of learning. by Andrew Y. Ng. S.M. 2005-08-19T19:14:59Z 2005-08-19T19:14:59Z 1998 1998 Thesis http://hdl.handle.net/1721.1/9658 42427464 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 57 p. 5878396 bytes 5878150 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science Ng, Andrew Y., 1976- On feature selection : learning with exponentially many irreverent features as training examples |
| title | On feature selection : learning with exponentially many irreverent features as training examples |
| title_full | On feature selection : learning with exponentially many irreverent features as training examples |
| title_fullStr | On feature selection : learning with exponentially many irreverent features as training examples |
| title_full_unstemmed | On feature selection : learning with exponentially many irreverent features as training examples |
| title_short | On feature selection : learning with exponentially many irreverent features as training examples |
| title_sort | on feature selection learning with exponentially many irreverent features as training examples |
| topic | Electrical Engineering and Computer Science |
| url | http://hdl.handle.net/1721.1/9658 |
| work_keys_str_mv | AT ngandrewy1976 onfeatureselectionlearningwithexponentiallymanyirreverentfeaturesastrainingexamples |