On the convergence of validity interval analysis

Validity interval analysis (VIA) is a generic tool for analyzing the input- output behavior of feedforward neural networks. VIA is a rule extraction te chnique that relies on a rule refinement algorithm, The rules are of the fo rm R-i --> R-o which reads if the input of the neural network is in the reg ion R-i, then its output is in the region R-o, where regions are axis paral lel hypercubes. VIA conjectures, then refines and checks rules for inconsis tency. This process can be computationally expensive, and the rule refineme nt phase becomes critical. Hence, the importance of knowing the complexity of these rule refinement algorithms. In this paper, we show that the rule refinement part of VIA always converge s in one run for single-weight-layer networks, and has an exponential avera ge rate of convergence for multilayer networks. We also discuss some variat ions of the standard VIA formulae.