31 Matching Results

Search Results

Advanced search parameters have been applied.

Cooperative terrain model acquisition by two point-robots in planar polygonal terrains

Description: We address the model acquisition problem for an unknown terrain by a team of two robots. The terrain may be cluttered by a finite number of polygonal obstacles with unknown shapes and positions. The robots are point-sized and equipped with visual sensors which acquire all visible parts of the terrain by scanning from their locations. The robots communicate with each other via wireless connection. The performance is measured by the number of the sensor (scan) operations which are assumed to be the most time-consuming/expensive of all the robot operations. We employ the restricted visibility graph methods in a hierarchiacal setup. For terrains with convex obstacles, the sensing time can be halved compared to a single robot implementation. For terrains with concave corners, the performance of the algorithm depends on the number of concave regions and their depths. A hierarchical decomposition of the restricted visibility graph into 2-connected components and trees is considered. Performance for the 2-robot team is expressed in terms of sizes of 2-connected components, and the sizes and diameters of the trees. The proposed algorithm and analysis can be applied to the methods based on Voronoi diagram and trapezoidal decomposition.
Date: November 29, 1994
Creator: Rao, N.S.V. & Protopopescu, V.
Partner: UNT Libraries Government Documents Department

Nadaraya-Watson estimator for sensor fusion problems

Description: The classical Nadaraya-Watson estimator is shown to solve a generic sensor fusion problem where the underlying sensor error densities are not known but a sample is available. By employing Haar kernels this estimator is shown to yield finite sample guarantees and also to be efficiently computable. Two simulation examples, and a robotics example involving the detection of a door using arrays of ultrasonic and infrared sensors, are presented to illustrate the performance.
Date: October 1, 1996
Creator: Rao, N.S.V.
Partner: UNT Libraries Government Documents Department

PAC learning algorithms for functions approximated by feedforward networks

Description: The authors present a class of efficient algorithms for PAC learning continuous functions and regressions that are approximated by feedforward networks. The algorithms are applicable to networks with unknown weights located only in the output layer and are obtained by utilizing the potential function methods of Aizerman et al. Conditions relating the sample sizes to the error bounds are derived using martingale-type inequalities. For concreteness, the discussion is presented in terms of neural networks, but the results are applicable to general feedforward networks, in particular to wavelet networks. The algorithms can be directly adapted to concept learning problems.
Date: June 1, 1996
Creator: Rao, N.S.V. & Protopopescu, V.
Partner: UNT Libraries Government Documents Department

Outsmarting neural networks: an alternative paradigm for machine learning

Description: We address three problems in machine learning, namely: (i) function learning, (ii) regression estimation, and (iii) sensor fusion, in the Probably and Approximately Correct (PAC) framework. We show that, under certain conditions, one can reduce the three problems above to the regression estimation. The latter is usually tackled with artificial neural networks (ANNs) that satisfy the PAC criteria, but have high computational complexity. We propose several computationally efficient PAC alternatives to ANNs to solve the regression estimation. Thereby we also provide efficient PAC solutions to the function learning and sensor fusion problems. The approach is based on cross-fertilizing concepts and methods from statistical estimation, nonlinear algorithms, and the theory of computational complexity, and is designed as part of a new, coherent paradigm for machine learning.
Date: October 1, 1996
Creator: Protopopescu, V. & Rao, N.S.V.
Partner: UNT Libraries Government Documents Department

Multiple sensor fusion under unknown distributions

Description: In a system of N sensors, the sensor {ital S{sub i}}, i = 1, 2 ..., N, outputs {ital Y}{sup (i)} {element_of} {Re}, according to an unknown probability distribution P{sub Y{sup (i)}}{vert_bar}X, corresponding to input X {element_of} {Re}. A training {ital n}-sample (X{sub 1}, Y{sub 1}), (X{sub 2},Y{sub 2}), ..., (X{sub n},Y{sub n}) is given where {ital Y{sub i}} = (Y{sub i}{sup (1)},Y{sub i}{sup (2)},...,Y{sub i}{sup (N)}) such that Y{sub i}{sup (j)} is the output of S{sub j} in response to input X{sub i}. The problem is to design a fusion rule expected square error: I({ital f}) = {integral}[X - f (Y)]{sup 2}dP{sub y{vert_bar}X}dPx, where Y=(Y{sup (1)}, Y{sup (2)},..., Y({sup N)}),is minimized over a family of functions {ital F}. Let f{sup *} minimize I(.) over {ital F}; in general, f{sup *} cannot be computed since the underlying distributions are unknown. We consider sufficient conditions based on smoothness and/or combinatorial dimensions of {ital F} to ensure that an estimator {cflx {ital f}} satisfies P[I({cflx {ital f}}) - I(f{sup *}) > {epsilon}] < {delta} for any {epsilon} > 0 and 0 < {delta} < 1. We present two methods for computing {cflx {ital f}} based on feedforward sigmoidal networks and Nadaraya-Watson estimator. Design and performance characteristics of the two methods are discussed, based both on theoretical and simulation results.
Date: October 1, 1996
Creator: Rao, N.S.V.
Partner: UNT Libraries Government Documents Department

Nearest neighbor rules PAC-approximate feedforward networks

Description: The problem of function estimation using feedforward neural networks based on an indpendently and identically generated sample is addressed. The feedforward networks with a single hidden layer of 1/(1+{epsilon}{sup -{gamma}z}) units and bounded parameters are considered. It is shown that given a sufficiently large sample, a nearest neighbor rule approximates the best neural network such that the expected error is arbitrarily bounded with an arbitrary high probability. Result is extendible to other neural networks where the hidden units satisfy a suitable Lipschitz condition. A result of practical interest is that the problem of computing a neural network that approximates (in the above sense) the best possible one is computationally difficult, whereas a nearest neighbor rule is linear-time computable in terms of the sample size.
Date: May 1, 1996
Creator: Rao, N.S.V.
Partner: UNT Libraries Government Documents Department

Projective Method for Generic Sensor Fusion Problem

Description: In a multiple sensor system, each sensor produces an output which is related to the desired feature according to a certain probability distribution. We propose a fuser that combines the sensor outputs to more accurately predict the desired feature. The fuser utilizes the lower envelope of regression curves of sensors to project the sensor with the least error at each point of the feature space. This fuser is optimal among all projective fusers and also satisfies the isolation property that ensures a performance at least as good as the best sensor. In the case the sensor distributions are not known, we show that a consistent estimator of this fuser can be computed entirely based on a training sample. Compared to linear fusers, the projective fusers provide a complementary performance. We propose two classes of metafusers that utilize both linear and projectives fusers to perform at least as good as the best sensor as well as the best fuser.
Date: August 15, 1999
Creator: Rao, N.S.V.
Partner: UNT Libraries Government Documents Department

On Optimal Projective Fusers for Function Estimators

Description: We propose a fuser that projects different function estimators in different regions of the input space based on the lower envelope of the error curves of the individual estimators. This fuser is shown to be optimal among projective fusers and also to perform at least as well as the best individual estimator. By incorporating an optimal linear fuser as another estimator, this fuser performs at least as well as the optimal linear combination. We illustrate the fuser by combining neural networks trained using different parameters for the network and/or for learning algorithms.
Date: June 22, 1999
Creator: Rao, N.S.V.
Partner: UNT Libraries Government Documents Department

Function estimation by feedforward sigmoidal networks with bounded weights

Description: The authors address the problem of PAC (probably and approximately correct) learning functions f : [0, 1]{sup d} {r_arrow} [{minus}K, K] based on iid (independently and identically distributed) sample generated according to an unknown distribution, by using feedforward sigmoidal networks. They use two basic properties of the neural networks with bounded weights, namely: (a) they form a Euclidean class, and (b) for hidden units of the form tanh ({gamma}z) they are Lipschitz functions. Either property yields sample sizes for PAC function learning under any Lipschitz cost function. The sample size based on the first property is tighter compared to the known bounds based on VC-dimension. The second estimate yields a sample size that can be conveniently adjusted by a single parameter, {gamma}, related to the hidden nodes.
Date: May 1, 1996
Creator: Rao, N.S.V.; Protopoescu, V. & Qiao, H.
Partner: UNT Libraries Government Documents Department

On PAC learning of functions with smoothness properties using feedforward sigmoidal networks

Description: We consider Probably and Approximately Corrct (PAC) learning of an unknown function f: [0,1]{sup d} {r_arrow} [0,1], based on finite samples using feedforward sigmoidal networks. The unknown function f is chosen from the family F{intersection}C([0,1]{sup d}) or F{intersection}L{sup {infinity}}([0,1]{sup d}), where F has either bounded modulus of smoothness or bounded capacity or both. The learning sample is given by (X{sub 1},f(X{sub 1})),(X{sub 2},f(X{sub 2})),{hor_ellipsis},(X{sub n},f(X{sub n})), where X{sub 1},X{sub 2},{hor_ellipsis},X{sub n} are independently and identically distributed according to an unknown distribution. We consider the feedforward networks with a a single hidden layer of 1/(1 + e{sup {minus}{gamma}z})-units and bounded parameters, but the results can be extended to other neural networks where the hidden units satisfy suitable smoothness conditions. We analyze three function estimators based on nearest neighbor rule, local averaging, and Nadaraya-Watson estimator, all computed using the Haar system. It is shown that given a sufficiently large sample, each of these estimators approximates the best neural network to any given error with arbitrarily high probability. This result is crucical for establishing the essentially equivalent capabilities of neural networks and the above estimators for PAC learning from finite samples. Practical importance of this ``equivalence`` stems from the fact that computing a neural network which approximates the best possible one is computationally difficult, whereas the three estimators are linear-time computable in terms of sample size.
Date: April 1, 1996
Creator: Rao, N.S.V. & Protopopescu, V.A.
Partner: UNT Libraries Government Documents Department

Fusion rule estimation using vector space methods

Description: In a system of N sensors, the sensor S{sub j}, j = 1, 2 .... N, outputs Y{sup (j)} {element_of} {Re}, according to an unknown probability distribution P{sub (Y(j) /X)}, corresponding to input X {element_of} [0, 1]. A training n-sample (X{sub 1}, Y{sub 1}), (X{sub 2}, Y{sub 2}), ..., (X{sub n}, Y{sub n}) is given where Y{sub i} = (Y{sub i}{sup (1)}, Y{sub i}{sup (2)}, . . . , Y{sub i}{sup N}) such that Y{sub i}{sup (j)} is the output of S{sub j} in response to input X{sub i}. The problem is to estimate a fusion rule f : {Re}{sup N} {r_arrow} [0, 1], based on the sample, such that the expected square error is minimized over a family of functions Y that constitute a vector space. The function f* that minimizes the expected error cannot be computed since the underlying densities are unknown, and only an approximation f to f* is feasible. We estimate the sample size sufficient to ensure that f provides a close approximation to f* with a high probability. The advantages of vector space methods are two-fold: (a) the sample size estimate is a simple function of the dimensionality of F, and (b) the estimate f can be easily computed by well-known least square methods in polynomial time. The results are applicable to the classical potential function methods and also (to a recently proposed) special class of sigmoidal feedforward neural networks.
Date: May 1, 1997
Creator: Rao, N.S.V.
Partner: UNT Libraries Government Documents Department

Preface to foundations of information/decision fusion with applications to engineering problems

Description: In engineering design, it was shown by von Neumann that a reliable system can be built using unreliable components by employing simple majority rule fusers. If error densities are known for individual pattern recognizers then an optimal fuser was shown to be implementable as a threshold function. Many applications have been developed for distributed sensor systems, sensor-based robotics, face recognition, decision fusion, recognition of handwritten characters, and automatic target recognition. Recently, information/decision fusion has been recognized as an independently growing field with its own principles and methods. While some of the fusion problems in engineering systems could be solved by applying existing results from other domains, many others require original approaches and solutions. In turn, these new approaches would lead to new applications in other areas. There are two paradigms at the extrema of the spectrum of the information/decision methods: (i) Fusion as Problem: In certain applications, fusion is explicitly specified in the problem statement. Particularly in robotics applications, many researchers realized the fundamental limitations of single sensor systems, thereby motivating the deployment of multiple sensors. In more general engineering applications, similar sensors are employed for fault tolerance, while in several others, different sensor modalities are required to achieve the given task. In these scenarios, fusion methods have to be first designed to solve the problem at hand. (ii) Fusion as Solution: In many instances (e.g., DNA analysis), a number of different solutions to a particular problem already exist. Often these solutions can be combined to obtain solutions that outperform any individual one. The area of forecasting is a good example of such paradigm. Although fusion is not explicitly specified in these problems, it is used as an ingredient of the solution.
Date: October 1, 1996
Creator: Madan, R.N. & Rao, N.S.V.
Partner: UNT Libraries Government Documents Department

On routing algorithms with end-to-end delay guarantees

Description: The authors consider the transmission of a message of size r from a source to a destination with guarantees on the end-to-end delay over a computer network with n nodes and m links. There are three sources of delays: (a) propagation delays along the links, (b) delays due to bandwidth availability on the links, and (c) queuing delays at the intermediate nodes. First, the authors consider that delays on various links and nodes are given as functions of the message size. If the delay in (b) is a non-increasing function of the bandwidth, they propose O(m{sup 2} + mn log n) time algorithm to compute a path with the minimum end-to-end delay for any given message size r. They then consider that the queuing delay in (c) is a random variable correlated with the message size according to an unknown distribution. At each node, the measurements of queuing delays and message sizes are available. They propose two algorithms to compute paths whose delays are close to optimal delays with a high probability, irrespective of the distribution of the delays, and based entirely on the measurements of sufficient size.
Date: November 1, 1998
Creator: Rao, N.S.V. & Batsell, S.G.
Partner: UNT Libraries Government Documents Department

Cooperative terrain model acquisition by a team of two or three point-robots

Description: We address the model acquisition problem for an unknown planar terrain by a team of two or three robots. The terrain is cluttered by a finite number of polygonal obstacles whose shapes and positions are unknown. The robots are point-sized and equipped with visual sensors which acquire all visible parts of the terrain by scan operations executed from their locations. The robots communicate with each other via wireless connection. The performance is measured by the number of the sensor (scan) operations which are assumed to be the most time-consuming of all the robot operations. We employ the restricted visibility graph methods in a hierarchical setup. For terrains with convex obstacles and for teams of n(= 2, 3) robots, we prove that the sensing time is reduced by a factor of 1/n. For terrains with concave corners, the performance of the algorithm depends on the number of concave regions and their depths. A hierarchical decomposition of the restricted visibility graph into n-connected and (n - 1)-or-less connected components is considered. The performance for the n(= 2, 3) robot team is expressed in terms of the sizes of n-connected components, and the sizes and diameters of (n - 1)-or-less connected components.
Date: April 1, 1996
Creator: Rao, N.S.V.; Protopopescu, V. & Manickam, N.
Partner: UNT Libraries Government Documents Department

Distributed decision fusion using empirical estimation

Description: The problem of optimal data fusion in multiple detection systems is studied in the case where training examples are available, but no a priori information is available about the probability distributions of errors committed by the individual detectors. Earlier solutions to this problem require some knowledge of the error distributions of the detectors, for example, either in a parametric form or in a closed analytical form. Here the authors show that, given a sufficiently large training sample, an optimal fusion rule can be implemented with an arbitrary level of confidence. They first consider the classical cases of Bayesian rule and Neyman-Pearson test for a system of independent detectors. Then they show a general result that any test function with a suitable Lipschitz property can be implemented with arbitrary precision, based on a training sample whose size is a function of the Lipschitz constant, number of parameters, and empirical measures. The general case subsumes the cases of non-independent and correlated detectors.
Date: September 1, 1996
Creator: Rao, N.S.V.
Partner: UNT Libraries Government Documents Department

Algorithms for fusion of multiple sensors having unknown error distributions

Description: The authors presented recent results on a general sensor fusion problem, where the underlying sensor error distributions are not known, but a sample is available. They presented a general method for obtaining a fusion rule based on scale-sensitive dimension of the function class. Two computationally viable methods are reviewed based on the Nadaraya-Watson estimator, and the finite dimensional vector spaces. Several computational issues of the fusion rule estimation are open problems. It would be interesting to obtain necessary and sufficient conditions under which polynomial-time algorithms can be used to solve the fusion rule estimation problem under the criterion. Also, conditions under which the composite system is significantly better than best sensor would be extremely useful. Finally, lower bound estimates for various sample sizes will be very important in judging the optimality of sample size estimates.
Date: June 1, 1997
Creator: Rao, N. S. V.
Partner: UNT Libraries Government Documents Department

PAC learning using Nadaraya-Watson estimator based on orthonormal systems

Description: Regression or function classes of Euclidean type with compact support and certain smoothness properties are shown to be PAC learnable by the Nadaraya-Watson estimator based on complete orthonormal systems. While requiring more smoothness properties than typical PAC formulations, this estimator is computationally efficient, easy to implement, and known to perform well in a number of practical applications. The sample sizes necessary for PAC learning of regressions or functions under sup norm cost are derived for a general orthonormal system. The result covers the widely used estimators based on Haar wavelets, trignometric functions, and Daubechies wavelets.
Date: August 1, 1997
Creator: Qiao, Hongzhu; Rao, N.S.V. & Protopopescu, V.
Partner: UNT Libraries Government Documents Department

QoS routing via multiple paths using bandwidth reservation

Description: The authors address the problem of computing a multipath, consisting of possibly overlapping paths, to transmit data from the source node s to the destination node d over a computer network while ensuring deterministic bounds on end-to-end delay or delivery rate. They consider two generic routing problems within the framework wherein bandwidth can be reserved, and guaranteed, once reserved, on various links of the communication network. The first problem requires that a message of finite length be transmitted from s to d within {tau} units of time. The second problem requires that a sequential message of r units be transmitted at a rate of {eta} such that maximum time difference between two units that are received out of order is no more than q. They propose a polynomial-time algorithm to the first problem based on an adaptation of the classical Ford-Fulkerson`s method. They present simulation results to illustrate the applicability of the proposed algorithm. They show the second problem to be NP-complete and propose a polynomial-time approximate solution.
Date: November 1, 1997
Creator: Rao, N.S.V. & Batsell, S.G.
Partner: UNT Libraries Government Documents Department

QoS routing via multiple paths using bandwidth reservation

Description: The authors address the problem of computing a multipath, consisting of possibly overlapping paths, to transmit data from the source node s to the destination node d over a computer network while ensuring deterministic bounds on end-to-end delay or delivery rate.They consider two generic routing problems within the framework wherein bandwidth can be reserved, and guaranteed, once reserved, on various links of the communication network. The first problem requires that a message of finite length be transmitted from s to d within {tau} units of time. The second problem requires that a sequential message of r units be transmitted at a rate of {eta} such that maximum time difference between two units that are received out of order is no more than q. They propose a polynomial-time algorithm to the first problem based on an adaptation of the classical Ford-Fulkerson`s method. They present simulation results to illustrate the applicability of the proposed algorithm. They show the second problem to be NP-complete, and propose a polynomial-time approximately solution.
Date: January 1, 1998
Creator: Rao, N.S.V. & Batsell, S.G.
Partner: UNT Libraries Government Documents Department

Algorithms for PAC learning of functions with smoothness properties

Description: We present three computationally efficient algorithms for Probably and Approximately Correct (PAC) learning of an unknown function f: [0, 1]{sup d} {r_arrow} [0,1], based on finite samples. The function f is chosen from the family F {intersection} C([0,1]{sup d}) or F {intersection} L{sup {infinity}} ([0,1]{sup d}), where F has either bounded modulus of smoothness or bounded capacity or both. Three function estimators based on: local averaging; nearest neighbor rule; and Nadaraya-Watson estimator, all computed using the Haar system, are analyzed. With no preprocessing of the sample, estimated function value at a given point can be computed in O(n) time. With preprocessing, the first and third estimators can be computed in O((log n){sup d}) time using a range-tree precomputed in O(dn(log n){sup d}) time.
Date: February 1, 1996
Creator: Rao, N.S.V. & Protopopescu, V.A.
Partner: UNT Libraries Government Documents Department

Fusion rule estimation in multiple sensor systems with unknown noise distributions

Description: A system of N sensors S{sub 1},S{sub 2},{hor_ellipsis},S{sub N} is considered; corresponding to an object with parameter x {epsilon} R{sup d}, sensor S{sub i} yields output y{sup (i)} {epsilon} R{sup d} according to an unknown probability distribution p{sub i}(y{sup (i)}{vert_bar}x). A training l-sample (x{sub 1},y{sub 1}),(x{sub 2},y{sub 2}),{hor_ellipsis},(x{sub l},y{sub l}) is given where y{sub i} = (y{sub i}{sup (1)}, y{sub i}{sup (2)},{hor_ellipsis},y{sub i}{sup (N)}) and y{sub i}{sup (j)} is the output of S{sub j} in response to input x{sub i}. The problem is to estimate a fusion rule f:R{sup Nd} {yields} R{sup d}, based on the sample, such that the expected square error I(f) = {integral}[x {minus} f(y{sup (1)},y{sup (2)}, {hor_ellipsis},y{sup (N)})]{sup 2}p(y{sup (1)},y{sup (2)}, {hor_ellipsis},y{sup (N)}{vert_bar}x)p(x)dy{sup (1)}dy{sup (2)}{hor_ellipsis}dy{sup (N)}dx is to be minimized over a family of fusion rules {Lambda} based on the given l-sample. Let f{sub *} {epsilon} {Lambda} minimize I(f); f{sub *} cannot be computed since the underlying probability distributions are unknown. Using Vapnik`s empirical risk minimization method, we show that if {Lambda} has finite capacity, then under bounded error, for sufficiently large sample, f{sub emp} can be obtained such that P[I(f{sub emp}) {minus} I(f{sub *}) > {epsilon}] < {delta} for arbitrarily specified {epsilon} > 0 and {delta}, 0 < {delta} < 1. We identify several computational methods to obtain f{sub emp} or its approximations based on neural networks, radial basis functions, wavelets, non-polynomial networks, and polynomials and splines. We then discuss linearly separable systems to identify objects from a finite class where f{sub emp} can be computed in polynomial time using quadratic programming methods.
Date: December 31, 1993
Creator: Rao, N. S. V.
Partner: UNT Libraries Government Documents Department

Finite-sample based learning algorithms for feedforward networks

Description: We discuss two classes of convergent algorithms for learning continuous functions (and also regression functions) that are represented by FeedForward Networks (FFN). The first class of algorithms, applicable to networks with unknown weights located only in the output layer, is obtained by utilizing the potential function methods of Aizerman et al. The second class, applicable to general feedforward networks, is obtained by utilizing the classical Robbins-Monro style stochastic approximation methods. Conditions relating the sample sizes to the error bounds are derived for both classes of algorithms using martingale-type inequalities. For concreteness, the discussion is presented in terms of neural networks, but the results are applicable to general feedforward networks, in particular to wavelet networks. The algorithms can also be directly applied to concept learning problems. A main distinguishing feature of the this work is that the sample sizes are based on explicit algorithms rather than information-based methods.
Date: April 1, 1995
Creator: Rao, N.S.V.; Protopopescu, V.; Mann, R.C.; Oblow, E.M. & Iyengar, S.S.
Partner: UNT Libraries Government Documents Department

Accuracy estimation for supervised learning algorithms

Description: This paper illustrates the relative merits of three methods - k-fold Cross Validation, Error Bounds, and Incremental Halting Test - to estimate the accuracy of a supervised learning algorithm. For each of the three methods we point out the problem they address, some of the important assumptions that are based on, and illustrate them through an example. Finally, we discuss the relative advantages and disadvantages of each method.
Date: April 1, 1997
Creator: Glover, C.W.; Oblow, E.M. & Rao, N.S.V.
Partner: UNT Libraries Government Documents Department

Quickest Paths for Different Network Router Mechanisms

Description: The quickest path problem deals with the transmission of a message of size {sigma} from a source to a destination with the minimum end-to-end delay over a network with bandwidth and delay constraints on the links. The authors consider four basic modes and two variations for the message delivery at the nodes reflecting the mechanisms such as circuit switching, Internet protocol, and their combinations. For each of the first three modes, they present O(m{sup 2} + mn log n) time algorithm to compute the quickest path for a given message size {sigma}. For the last mode, the quickest path can be computed in O(m + n log n) time.
Date: June 2000
Creator: Rao, N. S. V.; Grimmell, W. C.; Radhakrishnan, S. & Bang, Y. C.
Partner: UNT Libraries Government Documents Department