Optimal sampling for estimation with constrained resources using a learning automaton-based solution for the nonlinear fractional knapsack problem

摘要

While training and estimation for Pattern Recognition (PR) have been extensively studied, the question of achieving these when the resources are both limited and constrained is relatively open. This is the focus of this paper. We consider the problem of allocating limited sampling resources in a “real-time” manner, with the explicit purpose of estimating multiple binomial proportions (the extension of these results to non-binomial proportions is, in our opinion, rather straightforward). More specifically, the user is presented with ‘n’ training sets of data points, S 1,S 2,…,S n , where the set S i has N i points drawn from two classes {ω 1,ω 2}. A random sample in set S i belongs to ω 1 with probability u i and to ω 2 with probability 1−u i , with {u i }, i=1,2,…n, being the quantities to be learnt. The problem is both interesting and non-trivial because while both n and each N i are large, the number of samples that can be drawn is bounded by a constant, c. A web-related problem which is based on this model (Snaprud et al., The Accessibility for All Conference, 2003) is intriguing because the sampling resources can only be allocated optimally if the binomial proportions are already known. Further, no non-automaton solution has ever been reported if these proportions are unknown and must be sampled.