Π-CoLab

Privacy, Inference,

and Communications Laboratory

**Project 5: Feature Selection and Function
Approximation**

In this project, we propose a feature selection process based on the concept of dependency spectrum
introduced in
Project 2. At a high level, the process can be described as follows. We first start by
finding the decomposition of the decision function into its constituents based on a function transformation method
we introduced recently. Note that in most applications, the decision function is not explicitly
available, rather, a set of input and output pairs are given to us in the form of training data. As
a result, the decomposition elements need to be estimated from the training set. Next, the
constituents with *small* variances are eliminated. This reduces the set of inputs to the
function. Eliminating the constituents with the least variance insures that the output of the
decision function is altered minimally. Then, a reverse transformation is performed
to arrive at an approximation of the original decision function. As an example, we have
approximated the 5-letter logical 'OR' function using a 4-letter Boolean function. The probability
of disagreement between the original function and the approximation is shown in the figure below,
where P(X=1) is the parameter of the Bernoulli input.