Π-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.