I'm David Thompson, and this is the third
lecture in the
series on dimensionality reduction for the
Cal Tech Big Data Summer School.
This lecture is going to be on the topic
of Feature Selection.
So in, in previous modules I talked about
local methods for pattern recognition.
And then described how those methods don't
work as
well as you move to higher dimensional
input spaces.
So this is I guess the most, the simplest,
easiest
way to reduce a high dimensional data set
to something more
manageable, and that's just by taking a
subsle, subset of the
features, and there are a bunch of ways to
do that.
We'll investigate many of them here.
All right, so the objectives of this
module are
to be able to first know that and
understand
the techniques for combinatorial feature
selection and have a
couple tools in your tool kit for finding
informative features.
There are two basic kinds of feature
selection methods.
There are wrappers and filters, and you
should
be able to know the different between
them.
And you should also be able to know
different search strategies for searching
for subsets of features.
We're going to talk mostly about forward
and backwards feature selection.
So, why are we interested in feature
selection in the first place?
Well, there are several different reasons
why you might want to perform
this as a preprocessing operation, and go
through all the trouble.
The first is, of course what I alluded to
before, that is that large
dimension, or high dimensional input
spaces can
be problematic, because they're difficult
to sample from.
They can introduce lots of challenges for,
for local methods.
And even parametric methods as well,
non-local methods.
So often we like to just reduce the,
the raw numbers of dimensions in our input
space.
Another good thing about future selection
is that it
provides a way of revealing key
relationships in the data.
That is particular attributes that
inform your classification or regression
decisions.
Right?
So this is useful from an interpretive
perspective.
Right?
If I'm trying to understand what's present
in a data
set knowing the informative features might
be intrinsically or independently useful.
Finally our goal of all of this would be
to preserve the task relevant information.
So even though we're throwing stuff away,
we're hoping that the key
relationships will still be captured by
the data set after we're done.
We're just changing the representation to
make it
more, more comfortable for our pattern
recognition methods.
All right, so every feature selection
system involves two different parts.
There's an evaluation criterion, that is
how
you answer the question whether a feature
is
good or not, or if any given set of
features is, is good or not.
How it performs.
And then there's a search routine that you
use to to explore the
space with different feature combinations,
and we'll
talk about each of those in turn.
We're going to start by discussing the
evaluation criteria [INAUDIBLE].
Given some subset of features, how do I
score
that subset with respect to my pattern
recognition strategy task?
Okay.
And there are two basic different ways of,
of doing that.
There are wrapper evaluations and filter
evaluation strategies.
So the, the wrapper strategies this is
a general class of of feature selection
routines
that use the, they, they sort of
envelope whatever core pattern recognition
engineer you're using.
So, same using a K-nearest neighbor
approach.
The wrapper would simply push the, the
candidate set
of features though that K-nearest neighbor
and evaluate the
performance with respect to the task using
whatever task
relevent metric we've chosen for our basic
pattern recognition engine.
In this case, it could be cra
cross-validation error on held out data
points.
So we get our cross-validation error for a
particular feature candidate set, and can
then use
that as a score to compare as we change
the, the subset of features that we use.
So typically, this amounts to an iterative
approach where we try different candidate
feature subsets.
Do the entire training and testing
procedure,
with all of the leave one out cross
validation, and all of the unbiased risk
guesstimation that's necessary to do real
pattern recognition.
And then we evaluate our performance with
those subsets.
And, and iterate again improving our set
of, of candidate
attributes to use and until we're finally
satisfied with our performance.
And either we've reduced the, the set of
sub, the set of, of attributes
sufficiently, right?
To the point where we can it's now
tractable or we
start to see some, the, the fall off in
our performance.
That is, we've, we've included too many
features and are starting to
hit the cursive dimensionality again, so
that's the way a wrapper works.
Filters on the other hand operate as a
pure preprocessing step.
So they have some measured performance
that's
totally different from your pattern
recognition performance, right?
It might be some measure of
informativeness with respect to class
labels.
By some, measure it by some other model.
And by applying that in advance, you can
do the iterative
juggle and figure out what the, the
optimal subset of attributes is
before you even bring it to your k nearest
neighbors classification or
whatever classification method you're
planning on
using ultimately to solve the problem.
So this is basically using the intrinsic
properties of the data or critically some
other model than the pattern recognition
engine
for, that, that describes performance on
the task.
All right so, of these two I'll talk about
error, or I'll talk about error evaluation
for wrappers first.
Like I mentioned, wrappers are a typical
error analysis with a, a wrapper
based approach would be to look at your
performance on held out data.
Leave one out cross validate.
And the advantage of the wrapper method is
that it gives
you an accurate indicator of performance
on your, your actual tasks.
So you'll know that the, the subset you
select is actually the best
performer at the, the ultimate pattern
recognition task you, you intend to solve.
however, there are some disadvantages to
the wrapper method too.
One major disadvantage is the
computational complexity.
And this is especially true if you're,
you're
pattern recognition method is really
inefficient or computationally expensive.
If your training and test procedure
involves weeks of training on a super
computer cluster, you might not be able to
try with many combinations of attributes.
It might just not be feasible to from a
time and resource
perspective, to do that training, at which
point wrappers become less desirable.
Also there's this issue of specificity.
So it could be that because these are
very,
finely tuned to the particular pattern
recognition method you're using
it could be that they don't reveal
anything intrinsic about
the data itself but are you're simply
adjusting the attributes
according to the properties of your
pattern or recognition engine
rather than the data itself so they're
very specific is
another way of saying that and if you
change the
underlying classifier you may have to
chose a new set
of attributes which involves a new.
Iterative procedure to do that.
So, so wrappers, can be very accurate
but they also come with these important
disadvantages.
So, moving now to filters.
So, if you instead use a filter or
a pre-processing approach, they're all
sorts of different criteria,
sort of generic criteria that you can use,
to
judge whether an attribute or a set of
attributes.
Gives you information about the target
class label or, ordinate for regression
problem.
And these can be the K-S Test, a
traditional, K-S Test.
The Pearson Correlation Score is, is often
used.
So you simply find, a, a subset
of features with a, a good Pearson
Correlation.
the mutual information is a method
basically
a measure from information theory that
measures
the amount of bits of information that
some subset of features provides about
your
class label or you could use the fisher
score all of these are valid
filter criteria that you could apply that
are kind of independent of your
classification model.
And advantages to using a filter approach
is basically computational.
When you can apply the full pattern
recognition method
in its entirety on multiple runs of,
through the data.
Then, you can, apply this preprocessing
step and reduce the number of
attributes at the outset right, which
saves you from the curse of
dimensionality.
The disadvantage of course is that you're
sort
of positing some new measure of
performance, then diff,
that's different from what you ultimately
want to evaluate
so it implies some new potentially
redundant model right.
So, which raises the question why are we
going through all of
this extra work of building a whole new
model for our data.
A whole new performance metric when really
what
we're interested in is our [UNKNOWN]
nearest neighbor classification.
I want to talk about one other specific
filter ap,
approach based on the conditional mutual
information because this is
sort of emblematic of, of a bunch of
useful filtering
criteria from information theory and it
seems to perform pretty well.
So this is flora at all journal and
machine research 2004 but then
again like I said it's reminiscent of lots
of mach, of information theoretic.
Measures of, of performance that are used
in, in different filtering approaches to
feature selection.
So here, we have a score that's defined on
the left-hand side of the equation.
And to, it's called the Conditional Mutual
Information which basically measures the
amount of
new information that some new attribute A
sub I provides about the class liberal Y.
Given the data that we've, or given the
attributes
already in the set, that is the attribute
set A.
And this is defined as follows on the
right side.
So we're actually looking at two different
entropies.
The entropy as here written using capital
H and the
entropy describes, it's a measure of
uncertainty about a distribution.
So we're measuring the uncertainty about
the distribution of class
labels y, given our current set a of
attributes and then
subtracting the entropy of y given the
joint, or rather
the values of the candidate feature in our
attribute set together.
And you can expand the conditional entropy
in the following way.
it's, this, these are again just
straight-up definitions from the
information theory literature.
it, and it gives us basically the number
of bits of new
information that this candidate feature
will
provide with respect to our class label.
So this is a particularly useful and high
performing filter
function that doesn't presume any
knowledge of the ultimate classification.
Method that you're going to use of course
it requires
that you're able to estimate the
probability densities so it does
require some kind of probability modeling
there but provided you can
do that then this is a fairly
straightforward approach to use
okay so now that i've talked about
different
evaluation criterion I want to describe
the search routine
you use for exploring different subsets of
attributes
different subsets of features probably the
most common one.
Is called a greedy forward search.
And this is, you can think of this like a
solid bar, where you start off
with an empty plate and just add things
one at a time according to whatever looks
best.
So formally speaking, you start with an
empty feature set.
This is A starts as an all set, which is,
A is our set of attributes here.
And We iterate adding at each step the,
the best performing feature to our data
set.
So this, this involves a bunch of nested
loops
while our performance is still improving,
we look through
all of the candidate features that we have
remaining,
that is all of the times on the salad bar.
We add, we, we try adding that candidate,
feature to our dataset.
And then evaluate our performance using
our
performance criterion that, that I
mentioned before.
Either a wrapper or a filter method, and
based
on that, we figure out which is our best
overall.
Feature to add to the data set.
And we append it to our, our feature set
and then continue iterating, looking
for the next best feature to add given the
one that we, we've already established.
So this, again, continues as long as we
want to.
Until either performance starts to suffer,
or
we start encountering the, the curse of
dimensionality.
We've grown our attribute set too high.
And the, it's called the greedy method
because of [UNKNOWN]
at, at each step we're trying to maximize
our performance gain.
So it's not always optimal.
And in particular, if there are pairs of
features that are together very
informative but independently not
that informative, we're not going to catch
that relationship
here because we're [UNKNOWN] we're just
adding the next.
Best feature at every iteration.
That said greedy forward search usually
works pretty well for most practical
problems.
And that's a good place to start.
It also has the advantage that's pretty
computationally efficient.
Because you're starting with very few
attributes right.
So those early computations that you do.
It will be pretty cheap to perform,
because, the, the attribute
factor is fairly low, you're working with
a very low dimensional problem.
Alright, and you can carry that on for as
long as you want.
So that's one example of a simple search
strategy.
Here's another search strategy you might
want to use.
the.
Obviously, if we, we're starting with
forward search, the converse of
that would be a backwards elimination,
where we start with a full
set of features, and then at each step, we
figure out
which one we want to eliminate in order to
best improve performance.
So again, this, this starts off with you
can see on the, the formal algorithm
there on the, the left side, we're
starting
off with features 1 through a sub n.
Right, so we start off with the full set.
and then if i wait one candidate at a time
eliminating
it evaluating our Sarah cross validation
arrow or our raptor metric and
then removing it from the data set now
this has some disadvantages
because obviously we are susceptible
immediately
susceptible to the curse of
dimensionality.
It is impractical for many circumstances
where it will fail utterly for the full
set of features and it will be impossible
to get any meaning full performance.
score out of that.
We will also incur all the computational
cost of working with the full attributes
sets.
So that's a major disadvantage the
backwards elimination.
But if you can do it, if you can hack it,
backwards elimination can be good because
it actually lets you capture
relationships between pairs of features
that you might miss if you're
just adding one feature at a time from an
empty set.
So their, they each have their own
advantages depending on
the computational properties of your
algorithm and the data set.
Okay.
I also want to briefly touch on some
options for non-greedy search.
There are here just a few but there are
lots more on people of proposed simulated
annealing approaches.
You can think of simulated as, annealing
as a stochastic search, where
you search randomly throughout the data
set and perturb your candidate list.
According to some temperature term that
decreases over time.
So very early on you're going to be
searching wildly,
right, and jumping through, wildly
differing, candidate sets of attributes.
And then as the temperature reduces,
you'll settle in to some
local maximum, right, where it has a good
combination of features.
And you can think of this as a non-greedy
search approach.
People have proposed branch and bound
search algr, algorithms,
as well as genetic algorithms for future
selection too.
So it's more generally just any
non-convex, communitorial, optimization
engine is a candidate for some sort of
feature selection algorithm.
And there are lots of non greedy methods
to consider.
Okay.
So in summary, every feature selection
offered them has a couple parts.
It has an evaluation criterion.
And we've talked about wrapper and filter
evaluation methods.
And it also has a search strategy.
And we talked about greedy forward and
greedy backwards
elimination as [UNKNOWN] different
searches that, that you can try.
So this gives us a, a lot of
options to choose from for our feature
selection strategy.
In the next module we'll be talking
about some other methods for
dimensionality reduction.
We'll actually use the full set of
features but still have
the end, desired result of reducing the
total dimensionality of the dataset.