Minimum relevant variables in linear system: Difference between revisions

Revision as of 20:15, 9 January 2019

Revision as of 04:08, 28 January 2019

Line 18:

== Applications ==

The Min-RVLS problem is important in [[machine learning]] and [[linear discriminant analysis]]. Given a set of positive and negative examples, it is required to minimize the number of features that are required to correctly classify them.<ref>{{Cite journal|last=Koehler|first=Gary J.|date=1991-11-01|title=Linear Discriminant Functions Determined by Genetic Search|url=https://pubsonline.informs.org/doi/abs/10.1287/ijoc.3.4.345|journal=ORSA Journal on Computing|volume=3|issue=4|pages=345–357|doi=10.1287/ijoc.3.4.345|issn=0899-1499}}</ref> The problem is known as the [[minimum feature set problem]]. An algorithm that approximates Min-RVLS within a factor of <math>O(\log(m))</math>could substantially reduce the number of training samples required to attain a given accuracy level. <ref>{{Cite journal|last=Van Horn|first=Kevin S.|last2=Martinez|first2=Tony R.|date=1994-03-01|title=The Minimum Feature Set Problem|url=httphttps://dx.doi.org/10.1016/0893-6080(94)90082-5|journal=Neural Netw.|volume=7|issue=3|pages=491–494|doi=10.1016/0893-6080(94)90082-5|issn=0893-6080|via=}}</ref>

The [[shortest codeword problem]] in [[coding theory]] is the same problem as Min-RVLS[=] when the coefficients are in GF(2).