Learning Sparse Networks From Poor Data

Abstract

This paper is concerned with the learning process of a sparse interaction network, for example, a gene-protein interaction network. The advantage of the process we purpose is that there will always be a student S that fits the teacher T very well with a relatively small data set and a high number of unknown components, i.e., when the number of measurements M is significantly smaller than the system size N. To measure the efficiency of this learning process, we use the generalization error, epsilon_gen, which represents the probability that the student is a good fit to the teacher. From our experiments it follows that the quality of the fit depends on several factors: First, the ratio α = M/N of the number of measurements to the system size has a strong impact. Surprisingly, we find that a sudden identification transition occurs for value α ≈ αgen which corresponds to epsilon_gen = 1/2. From this sample size onwards the student will be a good fit to the teacher. Interestingly, the generalization threshold αgen, will always be significantly smaller than 1. Second, the quality of the fit depends on the sparsity of the network. If the number of non-zero components increases, as sparsity disappears, the efficiency of the process will gradually increase. Finally there is an impact of the noise level. The learning process is robust to noise upto a certain threshold. We see that, at this level, the impact on the noise suddenly and dramatically increases as a consequence of which the student will no longer be a good fit to the teacher.