The importance of dilution in the inference of biological networks
Alejandro Lage-Castellanos, Andrea Pagnani, Martin Weigt · 2009
One of the crucial tasks in many inference problems is the extraction of an underlying sparse graphical model from a given number of high-dimensional measurements. In machine learning, this is frequently achieved using, as a penalty term, the Lpnorm of the model parameters, with p ¿ 1 for efficient dilution. Here we propose a statistical-mechanics analysis of the problem in the setting of perceptron memorization and generalization. Using a replica approach, we are able to evaluate the relative performance of naive dilution (obtained by learning without dilution, following by applying a threshold to the model parameters), L1dilution (which is frequently used in convex optimization) and L0dilution (which is optimal but computationally hard to implement). Whereas both Lpdiluted approaches clearly outperform the naive approach, we find a small region where L0works almost perfectly and strongly outperforms the simpler to implement L1dilution. In the second part we propose an efficient message-passing strategy in the simpler case of discrete classification vectors, where the norm L0norm coincides with the L1. Some examples are discussed.