The following Technical Reports are available from the International Computer Science Institute via anonymous FTP from ftp.ICSI.Berkeley.EDU. They are located in pub/techreports and are all compressed, postscript files. If you experience difficulties, send mail to ftp-info@icsi.Berkeley.EDU. ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- FIXES ------------------------------------------------------------------------------- Some of these files may fail to print LaTex imbedded graphics. If you experience that problem, it is due to an Apple System 7.0 postscript bug. To correct, you will need to pick up the file "Apple.fix.Z" from this same directory. That file includes intructions for its use. bcx 3/4/92 ------------------------------------------------------------------------------- ABSTRACTS ------------------------------------------------------------------------------- tr-89-041.ps.Z Geometric Learning Algorithms Stephen M. Omohundro TR-89-041 July 1989 Emergent computation in the form of geometric learning is central to the development of motor and perceptual systems in biological organisms and promises to have a similar impact on emerging technologies including robotics, vision, speech, and graphics. This paper examines some of the trade-offs involved in different implementation strategies, focussing on the tasks of learning discrete classifications and smooth nonlinear mappings. The trade-offs between local and global representations are discussed, a spectrum of distributed network implementations are examined, and an important source of computational inefficiency is identified. Efficient algorithms based on k-d trees and the Delaunay triangulation are presented and the relevance to biological networks is discussed. Finally, extensions of both the tasks and the implementations are given. Keywords: learning algorithms, neural networks, computational geometry, emergent computation, robotics. ------------------------------------------------------------------------------- tr-89-047.ps.Z The Transitive Closure of a Random Digraph Richard M. Karp tr-89-047 August 1989 In a random $n$-vertex digraph, each arc is present with probability $p$, independently of the presence or absence of other arcs. We investigate the structure of the strong components of a random digraph and present an algorithm for the construction of the transitive closure of a random digraph. We show that, when $n$ is large and $np$ is equal to a constant $c$ greater than 1, it is very likely that all but one of the strong components are very small, and that the unique large strong component contains about $ size 9 {\(*H} sup 2 n$ vertices, where $ size 9 {\(*H}$ is the unique root in $[0,1]$ of the equation $1~-~x~-~e sup -cx ~=~0$. Nearly all the vertices outside the large strong component lie in strong components of size 1. Provided that the expected degree of a vertex is bounded away from 1, our transitive closure algorithm runs in expected time $O(n)$. For all choices of $n$ and $p$, the expected execution time of the algorithm is $O(w(n)~(n^ log ^n) sup 4/3 )$, where $w(n)$ is an arbitrary nondecreasing unbounded function. To circumvent the fact that the size of the transitive closure may be $\(*W (n sup 2 )$ the algorithm presents the transitive closure in the compact form $(A~ times ~B)~\(cu~C$, where $A$ and $B$ are sets of vertices, and $C$ is a set of arcs. ------------------------------------------------------------------------------- tr-89-063.ps.Z Five Balltree Construction Algorithms Stephen M. Omohundro tr-89-063 November 1989 Balltrees are simple geometric data structures with a wide range of practical applications to geometric learning tasks. In this report we compare 5 different algorithms for constructing balltrees from data. We study the tradeoff between construction time and the quality of the constructed tree. Two of the algorithms are on-line, two construct the structures from the data set in a top down fashion, and one uses a bottom up approach. ------------------------------------------------------------------------------- tr-89-032.ps.Z A Connectionist Model of Unification Andreas Stolcke TR-89-032 May 1989 A general approach to encode and unify recursively nested feature structures in connectionist networks is described. The unification algorithm implemented by the net is based on iterative coarsening of equivalence classes of graph nodes. This method allows the reformulation of unification as a constraint satisfaction problem and enables the connectionist implementation to take full advantage of the potential parallelism inherent in unification, resulting in sublinear time complexity. Moreover, the method is able to process any number of feature structures in parallel, searching for possible unifications and making decisions among mutually exclusive unifications where necessary. Keywords and phrases. Unification, constraint satisfaction, connectionism, feature structures. ------------------------------------------------------------------------------- tr-90-001.ps.Z The Delaunay Triangulation and Function Learning Stephen M. Omohundro TR-90-001 January 1990 In this report we consider the use of the Delaunay triangulation for learning smooth nonlinear functions with bounded second derivatives from sets of random input output pairs. We show that if interpolation is implemented by piecewise-linear approximation over a triangulation of the input samples, then the Delaunay triangulation has a smaller worst case error at each point than any other triangulation. The argument is based on a nice connection between the Delaunay criterion and quadratic error functions. The argument also allows us to give bounds on the average number of samples needed for a given level of approximation. ------------------------------------------------------------------------------- tr-90-009.ps.Z Miniature Language Acquisition: A touchstone for cognitive science Jerome A. Feldman, George Lakoff, Andreas Stolcke, and Susan Hollbach Weber TR-90-009 March 1990 (revised April 1990) Cognitive Science, whose genesis was interdisciplinary, shows signs of reverting to a disjoint collection of fields. This paper presents a compact, theory-free task that inherently requires an integrated solution. The basic problem is learning a subset of an arbitrary natural language from picture-sentence pairs. We describe a very specific instance of this task and show how it presents fundamental (but not impossible) challenges to several areas of cognitive science including vision, language, inference and learning. ------------------------------------------------------------------------------- tr-90-010.ps.Z L0: A Testbed for Miniature Language Acquisition Susan Hollbach Weber and Andreas Stolcke TR-90-010 July 1990 L0 constitutes a recent effort in Cognitive Science to build a natural language acquisition system for a limited visual domain. As a preparatory step towards addressing the issue of learning in this domain, we have built a set of tools for rapid prototyping and experimentation in the areas of language processing, image processing, and knowledge representation. The special focus of our work was the integration of these different components into a flexible system which would allow us to better understand the domain given by L0 and experiment with alternative approaches to the problems it poses. ------------------------------------------------------------------------------- tr-90-011.ps.Z A Network for Extracting the Locations of Point Clusters Using Selective Attention Subutai Ahmad and Stephen Omohundro ahmad@icsi.berkeley.edu and om@icsi.berkeley.edu TR 90-011 This report explores the problem of dynamically computing visual relations in connectionist systems. It concentrates on the task of learning whether three clumps of points in a 256x256 image form an equilateral triangle. We argue that feed-forward networks for solving this task would not scale well to images of this size. One reason for this is that local information does not contribute to the solution: it is necessary to compute relational information such as the distances between points. Our solution implements a mechanism for dynamically extracting the locations of the point clusters. It consists of an efficient focus of attention mechanism and a cluster detection scheme. The focus of attention mechanism allows the system to select any circular portion of the image in constant time. The cluster detector directs the focus of attention to clusters in the image. These two mechanisms are used to sequentially extract the relevant coordinates. With this new representation (locations of the points) very few training examples are required to learn the correct function. The resulting network is also very compact: the number of required weights is proportional to the number of input pixels. ------------------------------------------------------------------------------- tr-90-015.ps.Z Learning Feature-based Semantics with Simple Recurrent Networks Andreas Stolcke TR-90-015 April 1990 The paper investigates the possibilities for using simple recurrent networks as transducers which map sequential natural language input into non-sequential feature-based semantics. The networks perform well on sentences containing a single main predicate (encoded by transitive verbs or prepositions) applied to multiple-feature objects (encoded as noun-phrases with adjectival modifiers), and shows robustness against ungrammatical inputs. A second set of experiments deals with sentences containing embedded structures. Here the network is able to process multiple levels of sentence-final embeddings but only one level of center-embedding. This turns out to be a consequence of the network's inability to retain information that is not reflected in the outputs over intermediate phases of processing. Two extensions to Elman's \shortcite{Elman:88} original recurrent network architecture are introduced. ------------------------------------------------------------------------------- tr-90-023.ps.Z On the Power of Randomization in Online Algorithms S. Ben-David, A. Borodin, R. Karp, G. Tardos, and A. Wigderson tr-90-023 June 1990 Against an adaptive adversary, we show that the power of randomization in online algorithms is severely limited! We prove the existence of an efficient ``simulation'' of randomized online algorithms by deterministic ones, which is best possible in general. The proof of the upper bound is existential. We deal with the issue of computing the efficient deterministic algorithm, and show that this is possible in very general cases. ------------------------------------------------------------------------------- tr-90-024.ps.Z An Introduction to Randomized Algorithms Richard M. Karp tr-92-024 Research conducted over the past fifteen years has amply demonstrated the advantages of algorithms that make random choices in the course of their execution. This paper presents a wide variety of examples intended to illustrate the range of applications of randomized algorithms, and the general principles and approaches that are of greatest use in their construction. The examples are drawn from many areas, including number theory, algebra, graph theory, pattern matching, selection, sorting, searching, computational geometry, combinatorial enumeration, and parallel and distributed computation. ------------------------------------------------------------------------------- tr-90-037.ps.Z Two Results on the List Update Problem Sandy Irani TR-90-037 August 1990 In this paper we give a randomized on-line algorithm for the list update problem. Sleator and Tarjan show a deterministic algorithm, Move-to-Front, that achieves competitive ratio of (2L-1)/L for lists of length L. Karp an Raghavan show that no deterministic algorithm can beat 2L/(L+1). We show that Move-to-Front in fact achieves an optimal competitive ratio of 2L/(L+1). We show a randomized algorithm that achieves a competitive ratio of (31 L + 1 )/16(L+1) against an oblivious adversary. This is the first randomized strategy whose competitive factor beats a constant less than 2. Keywords: Analysis of Algorithms, On-line Algorithms, Competitive Analysis, Amortized Analysis, Linear Lists. ------------------------------------------------------------------------------- tr-90-063.ps.Z A Monte-Carlo Algorithm for Estimating the Permanent N. Karmarkar, R. Karp, R. Lipton, L. Lov\'{a}sz, and M. Luby tr-90-063 November 1990 Let $A$ be an $n \times n$ matrix with 0-1 valued entries, and let $\PER(A)$ be the permanent of $A$. We describe a Monte-Carlo algorithm which produces a ``good in the relative sense'' estimate of $\PER(A)$ and has running time $\POLY(n) 2^{n/2}$, where $\POLY(n)$ denotes a function that grows polynomially with $n$. Key Words: permanent, matching, Monte-Carlo algorithm, algorithm, bipartite graph, determinant. ------------------------------------------------------------------------------- tr-91-006.ps.Z Parallel Combinatorial Computing Richard M. Karp tr-91-006 January 1991 In this article we suggest that the application of highly parallel computers to applications with a combinatorial or logical flavor will grow in importance. We briefly survey the work of theoretical computer scientists on the construction of efficient parallel algorithms for basic combinatorial problems. We then discuss a two-stage algorithm design methodology, in which an algorithm is first designed to run on a PRAM and then implemented for a distributed-memory machine. Finally, we propose the class of node expansion algorithms as a fruitful domain for the application of highly parallel computers. ------------------------------------------------------------------------------- tr-91-009.ps.Z Bumptrees for Efficient Function, Constraint, and Classification Learning Stephen M. Omohundro TR-91-009 January 1991 A new class of data structures called "bumptrees" is described. These structures are useful for efficiently implementing a number of neural network related operations. An empirical comparison with radial basis functions is presented on a robot arm mapping learning task. Applications to density estimation, classification, and constraint representation and learning are also outlined. ------------------------------------------------------------------------------- tr-91-010.ps.Z How Receptive Field Parameters Affect Neural Learning Stephen M. Omohundro and Bartlett W. Mel TR-91-010 January 1991 We identify the three principle factors affecting the performance of learning by networks with localized units: unit noise, sample density, and the structure of the target function. We then analyze the effect of unit receptive field parameters on these factors and use this analysis to propose a new learning algorithm which dynamically alters receptive field properties during learning. ------------------------------------------------------------------------------- tr-91-011.ps.Z Algorithms for Sparse Rational Interpolation Dima Grigoriev, Marek Karpinski TR-91-011 January, 1991 We present two algorithms on sparse rational interpolation. The first is the interpolation algorithm in a sense of the sparse partial fraction representation of rational functions. The second is the algorithm for computing the entier and the remainder of a rational function. The first algorithm works without apriori known bound on the degree of a rational function, the second one is in the class NC provided the degree is known. The presented algorithms complement the sparse interpolation results of [Grigoriev, Karpinski, and Singer (1990)]. Keywords: -------- Algorithms, NC-Class, Sparse Rational Interpolation, Fraction Representation. ------------------------------------------------------------------------------- tr-91-013.ps.Z Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann Hypothesis Dima Grigoriev, Marek Karpinski, Andrew M. Odlyzko TR-91-013 February, 1991 Symbolic manipulation of sparse polynomials, given as lists of exponents and nonzero coefficients, appears to be much more complicated than dealing with polynomials in dense encoding (see e.g. [GKS 90, KT 88, P 77a, P 77b]). The first results in this direction are due to Plaisted [P 77a, P 77b], who proved, in particular, the NP-completeness of divisibility of a polynomial x**n-1 by a product of sparse polynomials. On the other hand, essentially nothing nontrivial is known about the complexity of the divisibility problem of two sparse integer polynomials. (One can easily prove that it is in PSPACE with the help of [M 86].) Here we prove that nondivisibility of two sparse multivariable polynomials is in NP, provided that the Extended Riemann Hypothesis (ERH) holds (see e.g. [LO 77]). The divisibility problem is closely related to the rational interpolation problem (whose decidability and complexity bound are determined in [GKS 90]). In this setting we assume that a rational function is given by a black box for evaluating it. We prove also that the problem of deciding whether a rational function given by a black box equals a polynomial belongs to the parallel class NC, provided the ERH holds and moreover, that we know the degree of some sparse rational representation of it. Keywords: -------- Algorithms, NC-Class, Symbolic Manipulation, Nondivisibility, Short Proofs, Extended Riemann Hypothesis. ------------------------------------------------------------------------------- tr-91-014.ps.Z Computational Complexity of Learning Read-Once Formulas over Different Bases Lisa Hellerstein, Marek Karpinski TR-91-014 February, 1991 We study computational complexity of learning read-once formulas over different boolean bases. In particular we design a polynomial time algorithm for learning read-once formulas over a threshold basis. The algorithm works in time O(n**3) using O(n**3) membership queries. By the result of [Angluin, Hellerstein, Karpinski, 1989] on the corresponding unate class of boolean functions, this gives a polynomial time learning algorithm for arbitrary read-once formulas over a threshold basis with negation using membership and equivalence queries. Furthermore we study the structural notion of nondegeneracy in the threshold formulas generalizing the result of [Heiman, Newman, Wigderson, 1990] on the uniqueness of read-once formulas over different boolean bases and derive a negative result on learnability of nondegenerate read-once formulas over the basis (AND, XOR). Keywords: -------- Computational Complexity, Learning Algorithms, Read-Once Formulas, Queries. ------------------------------------------------------------------------------- tr-91-018.ps.z Computational Complexity of Sparse Rational Interpolation Dima Grigoriev, Marek Karpinski, Michael F. Singer TR-91-018 March, 1991 We analyze the computational complexity of sparse rational interpolation, and give the first genuine time (arithmetic complexity does not depend on the size of the coefficients) algorithm for this problem. Keywords: -------- Computational Complexity, Algorithms, Arithmetic Complexity, Sparse Rational Interpolation. ------------------------------------------------------------------------------- tr-91-019.ps.Z Probabilistic Recurrence Relations Richard M. Karp tr-91-019 March 1991 This paper is concerned with recurrence relations that arise frequently in the analysis of divide-and-conquer algorithms. In order to solve a problem instance of size $x$, such an algorithm invests an amount of work $a(x)$ to break the problem into subproblems of sizes $h_1(x),h_2(x),\ldots,h_k(x)$, and then proceeds to solve the subproblems. Our particular interest is in the case where the sizes $h_i(x)$ are random variables; this may occur either because of randomization within the algorithm or because the instances to be solved are assumed to be drawn from a probability distribution. When the $h_i$ are random variables the running time of the algorithm on instances of size $x$ is also a random variable $T(x)$. We give several easy-to-apply methods for obtaining fairly tight bounds on the upper tails of the probability distribution of $T(x)$, and present a number of typical applications of these bounds to the analysis of algorithms. The proofs of the bounds are based on an interesting analysis of optimal strategies in certain gambling games. ------------------------------------------------------------------------------- tr-91-027.ps.Z An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q] Dima Grigoriev, Marek Karpinski TR-91-027 April, 1991 We design the first polynomial time (for an arbitrary and fixed field GF[q]) (epsilon,delta)-approximation algorithm for the number of zeros of arbitrary polynomial f(x_1, ... ,x_n) over GF[q].It gives the first efficient method for estimating the number of zeros and nonzeros of multivariate polynomials over small finite fields other than GF[2] (like GF[3]), the case important for various circuit approximation techniques. The algorithm is based on the estimation of the number of zeros of an arbitrary polynomial f(x_1, ... ,x_n) over GF[q] in the function on the number m of its terms. The bounding ratio number is proved to be m**((q-1) log q) which is the main technical contribution of this paper and could be of independent algebraic interest. Keywords: -------- Approximation Algorithms, Counting Problems, Multivariate Polynomials, Finite Fields. ------------------------------------------------------------------------------- tr-91-030.ps.Z Probability estimation by feed-forward networks in continuous speech recognition Steve Renals, Nelson Morgan and Herve Bourlard TR-91-030 August 1991 We review the use of feed-forward networks as estimators of probability densities in hidden Markov modelling. In this paper we are mostly concerned with radial basis functions (RBF) networks. We note the isomorphism of RBF networks to tied mixture density estimators; additionally we note that RBF networks are trained to estimate posteriors rather than the likelihoods estimated by tied mixture density estimators. We show how the neural network training should be modified to resolve this mismatch. We also discuss problems with discriminative training, particularly the problem of dealing with unlabelled training data and the mismatch between model and data priors. ------------------------------------------------------------------------------- tr-91-031.ps.Z pSather monitors: Design, Tutorial, Rationale and Implementation Jerome A. Feldman, Chu-Cheow Lim and Franco Mazzanti TR-91-031 September 1989 Sather is a new object-oriented programming language under development at the International Computer Science Institute. The initial beta test release of the language was in June, 1991. From the outset, one goal of the Sather project has been the incorporation of constructs to support parallel programming. pSather is a parallel extension of Sather aimed at shared memory parallel architectures. A prototype of the language is currently being implemented on a Sequent Symmetry and on SUN Sparc-Stations. pSather monitors are one of the basic new features introduced in the language to deal with parallelism. The current design is presented and discussed in detail. ------------------------------------------------------------------------------- tr-91-032.ps.Z GAL: Networks that grow when they learn and shrink when they forget Ethem Alpaydin TR 91-032 Learning when limited to modification of some parameters has a limited scope; the capability to modify the system structure is also needed to get a wider range of the learnable. In the case of artificial neural networks, learning by iterative adjustment of synaptic weights can only succeed if the network designer predefines an appropriate network structure, i.e., number of hidden layers, units, and the size and shape of their receptive and projective fields. This paper advocates the view that the network structure should not, as usually done, be determined by trial-and-error but should be computed by the learning algorithm. Incremental learning algorithms can modify the network structure by addition and/or removal of units and/or links. A survey of current connectionist literature is given on this line of thought. ``Grow and Learn'' (GAL) is a new algorithm that learns an association at one-shot due to being incremental and using a local representation. During the so-called ``sleep'' phase, units that were previously stored but which are no longer necessary due to recent modifications are removed to minimize network complexity. The incrementally constructed network can later be finetuned off-line to improve performance. Another method proposed that greatly increases recognition accuracy is to train a number of networks and vote over their responses. The algorithm and its variants are tested on recognition of handwritten numerals and seem promising especially in terms of learning speed. This makes the algorithm attractive for on-line learning tasks, e.g., in robotics. The biological plausibility of incremental learning is also discussed briefly. Keywords Incremental learning, supervised learning, classification, pruning, destructive methods, growth, constructive methods, nearest neighbor. ------------------------------------------------------------------------------- tr-91-034.ps.Z Sather Language Design and Performance Evaluation Chu-Cheow Lim and Andreas Stolcke% TR-91-034 Sather is an object-oriented language recently designed and implemented at the International Computer Science Institute in Berkeley. It compiles into C and is intended to allow development of object-oriented, reusable software while retaining C's efficiency and portability. We investigate to what extent these goals were met through a comparative performance study and analysis of Sather and C programs on a RISC machine. Several language design decisions in Sather are motivated by the goal of efficient compilation to standard architectures. We evaluate the reasoning behind these decisions, using instruction set usage statistics, cache simulations, and other data collected by instrumented Sather-generated code. We conclude that while Sather users still pay a moderate overhead for programming convenience (in both run time and memory usage) the overall CPU and memory usage profiles of Sather programs are virtually identical to those of comparable C programs. Our analysis also shows that each of the choices made in Sather design and implementation is well justified by a distinctive performance advantage. It seems, then, that Sather proves the feasibility of its own design goal of making object-oriented programming efficient on standard architectures using a combination of judicious language design and efficient implementation. ------------------------------------------------------------------------------- tr-91-035.ps.Z HiPNeT-1 : A Highly Pipelined Architecture for Neural Network Training Krste Asanovic, Brian E. D. Kingsbury, Nelson Morgan, and John Wawrzynek TR-91-035 June 1991 Current artificial neural network (ANN) algorithms require extensive computational resources. However, they exhibit massive fine-grained parallelism and require only moderate arithmetic precision. These properties make possible custom VLSI implementations for high performance, low cost systems. This paper describes one such system, a special purpose digital VLSI architecture to implement neural network training in a speech recognition application. The network algorithm has a number of atypical features. These include: shared weights, sparse activation, binary inputs, and a serial training input stream. The architecture illustrates a number of design techniques to exploit these algorithm-specific features. The result is a highly pipelined system which sustains a learning rate of one pattern per clock cycle. At a clock rate of 20MHz each "neuron" site performs 200 million connection updates per second. Multiple such neurons can be integrated onto a modestly sized VLSI die. ------------------------------------------------------------------------------- tr-91-036.ps.Z Experimental Determination of Precision Requirements for Back-Propagation Training of Artificial Neural Networks Krste Asanovic and Nelson Morgan TR-91-036 June 1991 The impact of reduced weight and output precision on the back-propagation training algorithm is experimentally determined for a feed-forward multi-layer perceptron. In contrast with previous such studies, the network is large with over 20,000 weights, and is trained with a large, real-world data set of over 130,000 patterns to perform a difficult task, that of phoneme classification for a continuous speech recognition system. The results indicate that 16b weight values are sufficient to achieve training and classification results comparable to 32b floating point, provided that weight and bias values are scaled separately, and that rounding rather than truncation is employed to reduce the precision of intermediary values. Output precision can be reduced to 8 bits without significant effects on performance. ------------------------------------------------------------------------------- tr-91-048.ps.Z ICSIM: An Object-Oriented Connectionist Simulator Hienz W. Schmidt, Benedict Gomes TR-91-048 November 1991 ICSIM is a connectionist net simulator under development at ICSI and written in Sather. It is object-oriented to meet the requirements for flexibility and reuse of homogeneous and structured connectionist nets and to allow the user to encapsulate efficient customized implementations perhaps running on dedicated hardware. Nets are composed by combining off-the-shelf library classes and, if necessary, by specializing some of their behaviour. General user interface classes allow a uniform or customized graphic presentation of the nets being modeled. The report gives an overview of the simulator. Its main concepts, the class structure of its library and some of the design decisions are sketched and a number of example nets are used to illustrate how net structure, interconnection and behavior are defined. ------------------------------------------------------------------------------- tr-91-050.ps.Z Learning Spatial Concepts Using a Partially-Structured Connectionist Architecture Terry Regier TR-91-050 October 1991 This paper reports on the learning of spatial concepts in the L0 project. The challenge of designing an architecture capable of learning spatial concepts from any of the world's languages is first highlighted by reviewing the spatial systems of a number of languages which differ strikingly from English in this regard. A partially structured connectionist architecture is presented which has successfully learned concepts from the languages outlined. In this architecture, highly structured subnetworks, specialized for the spatial concept learning task, feed into an unstructured, fully-connected upper subnetwork. The system's success at the learning task is attributed on the one hand to the constrained search space which results from structuring, and on the other hand to the flexibility afforded by the unstructured upper subnetwork. ------------------------------------------------------------------------------- tr-91-058.ps.Z Detecting Skewed Symmetries Stefan Posch TR-91-058 October 1991 Many surfaces of objects in our world are bounded by planar bilaterally symmetric figures. When these figures are imaged under orthographic projection a skewed symmetric contour results. In this paper a new fast, local method to recover skewed symmetries from curve segments is proposed. It can be applied to complete as well as to occluded contours. Furthermore, the skewed symmetry property is employed to overcome fragmentation of a contour during segmentation. ------------------------------------------------------------------------------- tr-91-059.ps.Z Line Labeling Using Markov Random Fields Terry Regier TR-91-059 November 1991 The task of obtaining a line labeling from a greyscale image of trihedral objects presents difficulties not found in the classical line labeling problem. As originally formulated, the line labeling problem assumed that each junction was correctly pre-classified as being of a particular junction type (e.g. T, Y, arrow); the success of the algorithms proposed have depended critically upon getting this initial junction classification correct. In real images, however, junctions of different types may actually look quite similar, and this pre-classification is often difficult to achieve. This issue is addressed by recasting the line labeling problem in terms of a coupled probabilistic system which labels both lines and junctions. This results in a robust system, in which prior knowledge of acceptable configurations can serve to overcome the problem of misleading or ambiguous evidence. ------------------------------------------------------------------------------- tr-91-060.ps.Z B.Codenotti, M.Leoncini and G.Resta Oracle Computations in Parallel Numerical Linear Algebra tr-91-060 October 1991. We analyze the relative complexity of several numerical linear algebra problems, when errors in the computation occur. We show that the simple parallel complexity classes of the exact case do not seem to preserve under approximation. ------------------------------------------------------------------------------- tr-91-061.ps.Z Combinatory Differential Fields: An Algebraic Approach to Approximate Computation and Constructive Analysis Karl Aberer TR-91-061 October 1991 The algebraic structure of combinatory differential fields is constructed to provide a semantics for computations in analysis. In this setting programs, approximations, limits and operations of analysis are represented as algebraic terms. Analytic algorithms can be derived by algebraic methods. The main tool in this construction are combinatory models which are inner algebras of Engeler graph models. As an universal domain of denotational semantics the lattice structure of the graph models allows to give a striking simple semantics for computations with approximations. As models of combinatory algebra they provide all essential computational constructs, including recursion. Combinatory models are constructed as extensions of first order theories. The classical first order theory to describe analysis is the theory of differential fields. It turns out that two types of computational constructs, namely composition and piecewise definition of functions, are preferably introduced as extensions of the differential fields theory. Combinatory differential fields are then the combinatory models of these enriched differential fields. We show for basic algorithms of computational analysis how their combinatory counterparts are derived in the algebraic setting. We illustrate how these algorithms are suitable to be implemented in a computer algebra environment like mathematica. ------------------------------------------------------------------------------- tr-91-062.ps.Z Self-Testing/Correcting with Applications to Numerical Problems (Revised Version)} Manuel Blum, Michael Luby, Ronitt Rubinfeld TR-91-062 Suppose someone gives us an extremely fast program $P$ that we can call as a black box to compute a function $f$. Should we trust that $P$ works correctly? A {\em self-testing/correcting pair} for $f$ allows us to: (1) estimate the probability that $P(x) \not= f(x)$ when $x$ is randomly chosen; (2) on {\em any} input $x$, compute $f(x)$ correctly as long as $P$ is not too faulty on average. Furthermore, both (1) and (2) take time only slightly more than the original running time of $P$. We present general techniques for constructing simple to program self-testing/\-correcting pairs for a variety of numerical functions, including integer multiplication, modular multiplication, matrix multiplication, inverting matrices, computing the determinant of a matrix, computing the rank of a matrix, integer division, modular exponentiation and polynomial multiplication. ------------------------------------------------------------------------------- tr-91-064.ps.Z Distortion Accumulation in Image Transform Coding/Decoding Cascades Michael Gilge TR-91-064 December 1991 With an increasing number of applications that employ transform coding algorithms for data reduction, the effect of distortion accumulation caused by multiple coding needs to be investigated. Multiple coding occurs when more than one coding system is connected in a cascade. From the second stage on, the coding algorithm operates on data that has been previously coded/decoded. First a generic image communication system is being modelled and situations that can lead to distortion accumulation are analyzed. These results show two main reasons for distortion accumulation, which are separately and jointly investigated using a JPEG-type compression algorithm. The first situation involves geometric operations between the decoding and next coding step. Measurements show however that these spatial manipulations are the main contributors to distortion accumulation. The second reason for distortion accumulation is a misalignment of the block segmentation reference point in subsequent transform operations. A block raster detection algorithm is derived that can find the position of the block raster that was introduced in a previous coding step. If this information is used in the block segmentation of the following coding step, distortion accumulation can be avoided. Simulation results are given for an extended algorithm that registers regions of homogeneous block raster in images consisting of several subimages. ------------------------------------------------------------------------------- tr-91-065.ps.Z Motion Video Coding for Packet-Switching Networks -- An Integrated Approach Michael Gilge and Riccardo Gusella TR-91-065 December 1991 The advantages of packet video, constant image quality, service integration and statistical multiplexing, are overshadowed by packet loss, delay and jitter. By integrating network-control into the image data compression algorithm, the strong interactions between the coder and the network can be exploited and the available network bandwidth can be used best. In order to enable video transmission over today's networks without reservation or priorities and in the presence of high packet loss rates, congestion avoidance techniques need to be employed. This is achieved through rate and flow control, where feedback from the network is used to adapt coding parameters and vary the output rate. From the coding point of view the network is seen as data buffer. Analogously to constant bit rate applications, where a controller measures buffer fullness, we attempt to avoid network congestion (eq. buffer overflow) by monitoring the network and adapting the coding parameters in real-time. ------------------------------------------------------------------------------- tr-91-066.ps.Z A Graph-Theoretic Game and its Application to the k-Server Problem Noga Alon, Richard M. Karp, David Peleg, and Douglas West tr-91-066 December 1991 This paper investigates a zero-sum game played on a weighted connected graph $G$ between two players, the {\em tree player} and the {\em edge player}. At each play, the tree player chooses a spanning tree $T$ and the edge player chooses an edge $e$. The payoff to the edge player is $cost(T,e)$, defined as follows: If $e$ lies in the tree $T$ then $cost(T,e)=0$; if $e$ does not lie in the tree then $cost(T,e) = cycle(T,e)/w(e)$, where $w(e)$ is the weight of edge $e$ and $cycle(T,e)$ is the weight of the unique cycle formed when edge $e$ is added to the tree $T$. Our main result is that the value of the game on any $n$-vertex graph is bounded above by $\exp(O(\sqrt{\log n \log\log n}))$. The game arises in connection with the $k$-server problem on a {\em road network}; i.e., a metric space that can be represented as a multigraph $G$ in which each edge $e$ represents a road of length $w(e)$. We show that, if the value of the game on $G$ is $\Val(G,w)$, then there is a randomized strategy that achieves a competitive ratio of $k(1 + \Val(G,w))$ against any oblivious adversary. Thus, on any $n$-vertex road network, there is a randomized algorithm for the $k$-server problem that is $k\cdot\exp(O(\sqrt{\log n \log\log n}))$-competitive against oblivious adversaries. At the heart of our analysis of the game is an algorithm that, for any $n$-vertex weighted, connected multigraph, constructs a spanning tree $T$ such that the average, over all edges $e$, of $cost(T,e)$ is less than or equal to $\exp(O(\sqrt{\log n \log\log n}))$. This result has potential application to the design of communication networks. ------------------------------------------------------------------------------- tr-91-067.ps.Z Probabilistic Recurrence Relations for Parallel Divide-and-Conquer Algorithms Marek Karpinski, Wolf Zimmermann TR-91-067 December, 1991 We study two probabilistic recurrence relations that arise frequently in the analysis of parallel and sequential divide-and-conquer algorithms (cf. [Karp 91]). Suppose a problem of size x has to be solved. In order to solve it we divide it into subproblems of size h_1(x), ... ,h_k(x) and these subproblems are solved recursively. We assume that size(h_i(z)) are random variables. This occurs if either the break up step is randomized or the instances to be solved are drawn from a probability distribution. The running time T(z) of a parallel algorithm is therefore determined by the maximum of the running times T(h_i(z)) of the subproblems while the sequential algorithm is determined by the sum of the running times of the subproblems. We give a method for estimating tight upper bounds on the probability distribution of T(x) for these two kinds of recurrence relations, answering the open questions in [Karp 91]. Keywords: -------- Probabilistic Recurrence Relations, Devide-and-Conquer Algorithms, Prallel Algorithms, Upper Bounds on Probability Distribution. ------------------------------------------------------------------------------- tr-91-068.ps.Z Construction of a pseudo-random generator from any one-way function Johan Hastad, Russell Impagliazzo, Leonid A. Levin, Michael Luby TR-91-068 We show how to construct a pseudo-random generator from any one-way function. In contrast, previous works have constructed pseudo-random generators only from one-way functions with special structural properties. Our overall approach is different in spirit from previous work; we concentrate on extracting and smoothing entropy from a single iteration of the one-way function using universal hash functions. ------------------------------------------------------------------------------- tr-91-069.ps.Z RASTA-PLP Speech Analysis Hynek Hermansky, Nelson Morgan, Aruna Bayya, and Phil Kohn TR-91-069 December 1991 Most speech parameter estimation techniques are easily influenced by the frequency response of the communication channel. We have developed a technique that is more robust to such steady-state spectral factors in speech. The approach is conceptually simple and computationally efficient. The new method is described, and experimental results are reported, showing a significant advantage for the proposed method. ------------------------------------------------------------------------------- tr-91-070.ps.Z Connectionist Speech Recognition: Status and Prospects Steve Renals, Nelson Morgan, Herve Bourlard, Michael Cohen, Horacio Franco, Chuck Wooters and Phil Kohn. TR-91-070 December 1991 We report on recent advances in the ICSI connectionist speech recognition project. Highlights include: 1. Experimental results showing that connectionist methods can improve the performance of a context independent maximum likelihood trained HMM system, resulting in a performance close to that achieved using state of the art context dependent HMM systems of much higher complexity; 2. Mixing (context independent) connectionist probability estimates with maximum likelihood trained context dependent models to improve the performance of a state of the art system; 3. The development of a network decomposition method that allows connectionist modelling of context dependent phones efficiently and parsimoniously, with no statistical independence assumptions. ------------------------------------------------------------------------------- tr-91-071.ps.Z GDNN: A Gender-Dependent Neural Network for Continuous Speech Recognition Yochai Konig, Nelson Morgan, and Claudia Chandra TR-91-071 December 1991 Conventional speaker-independent speech recognition systems do not consider speaker-dependent parameters in the probability estimation of phonemes. These recognition systems are instead tuned to the ensemble statistics over many speakers. Most parametric representations of speech, however, are highly speaker dependent, and probability distributions suitable for a certain speaker may not perform as well for other speakers. It would be desirable to incorporate constraints on analysis that rely on the same speaker producing all the frames in an utterance. Our experiments take a first step towards this speaker consistency modeling by using a classification network to help generate gender-dependent phonetic probabilities for a statistical recognition system. Our results show a good classification rate for the gender classification net. Simple use of such a model to augment an existing larger network that estimates phonetic probabilities does not help speech recognition performance. However, when the new net is properly integrated in an HMM recognizer, it provides significant improvement in word accuracy. ------------------------------------------------------------------------------- tr-91-072.ps.Z SPERT: A VLIW/SIMD Microprocessor for Artificial Neural Network Computations Krste Asanovic, James Beck, Brian E. D. Kingsbury, Phil Kohn, Nelson Morgan, John Wawrzynek TR-91-072 December 1991 SPERT (Synthetic PERceptron Testbed) is a fully programmable single chip microprocessor designed for efficient execution of artificial neural network algorithms. The first implementation will be in a 1.2 micron CMOS technology with a 50MHz clock rate, and a prototype system is being designed to occupy a double SBus slot within a Sun Sparcstation. SPERT will sustain over 300 million connections per second during pattern classification, and around 100 million connection updates per second while running the popular error backpropagation training algorithm. This represents a speedup of around two orders of magnitude over a Sparcstation-2 for algorithms of interest. An earlier system produced by our group, the Ring Array Processor (RAP), used commercial DSP chips. Compared with a RAP multiprocessor of similar performance, SPERT represents over an order of magnitude reduction in cost for problems where fixed-point arithmetic is satisfactory. This report describes the current architecture, and gives the results of detailed simulations. The report also makes a short comparison to other high-performance digital neurocomputing chips. ------------------------------------------------------------------------------- tr-91-074.ps.Z Recent Work in VLSI Elements for Digital Implementations of Artificial Neural Networks Brian E. D. Kingsbury, Bertrand Irissou, Krste Asanovic, John Wawrzynek, Nelson Morgan TR-91-074 December 1991 A family of high-performance, area-efficient VLSI elements is being developed to simplify the design of artificial neural network processors. The libraries are designed around the MOSIS Scalable CMOS design rules, giving users the option of fabricating designs in 2.0um or 1.2um n-well processes, and greatly simplifying migration of the libraries to new MOSIS technologies. To date, libraries and generators have been created for saturating and nonsaturating adders, a two's-complement multiplier, and a triple-ported register file. The SPERT processor currently being designed at ICSI will be based upon these libraries, and is expected to run at 50 MHz when realized in a 1.2um CMOS technology. ------------------------------------------------------------------------------- tr-91-075.ps.Z C.Bernini, B.Codenotti, M.Leoncini and G.Resta Incomplete Factorizations for Certain Toeplitz matrices tr-91-075 December 1991. We propose some incomplete factorizations for banded Toeplitz matrices and we show their application to the direct and iterative solution of several special Toeplitz linear systems. ------------------------------------------------------------------------------- tr-92-001.ps.Z Real-Time Communication in an Internetwork Domenico Ferrari TR-92-001 January 1992 Can end-to-end communication performance be guaranteed by a packet-switching internetwork? This paper addresses the question by examining the feasibility of extending to an internetwork the Tenet approach to real-time communication service design. The conditions to be satisfied by an internetwork so that the approach can be extended to it are investigated. These include conditions for the scheduling discipline to be used in the nodes of the internetwork. The original Tenet approach to real-time communication applies to a network consisting of hosts, homogeneous nodes (or switches), and physical links connecting nodes and hosts in an arbitrary topology. The nodes are store-and-forward, and are scheduled by a multi-class version of the Earliest Due Date deadline-based policy. The discussion presented in this paper results in extendibility conditions that are quite broad; hence, the Tenet approach may be used to establish and run real-time channels in a vast class of internetworks. A case study is also discussed, involving a simple network, whose nodes are scheduled by FCFS-based disciplines, and the connection of such a network to an internetwork with deadline-based and hierarchical round robin scheduling. ------------------------------------------------------------------------------- tr-92-002.ps.Z Constraint Relaxation and Nonmonotonic Reasoning Gerhard Brewka, Hans Werner Guesgen, Joachim Hertzberg TR-92-002 January 1992 The purpose of this paper is to bring together the two AI areas of constraint-based and nonmonotonic reasoning. In particular, we analyze the relation between different forms of constraint relaxation and a particular approach to nonmonotonic reasoning, namely, preferred subtheories. In effect, we provide formal semantics for the respective forms of constraint relaxation. ------------------------------------------------------------------------------- tr-92-003.ps.Z Rate-Controlled Static Priority Queueing Hui Zhang and Domenico Ferrrari TR-92-003 January, 1992 We propose a new service discipline, called the Rate-Controlled Static-Priority (RCSP) queueing discipline, that can provide throughput, delay, delay jitter, and loss free guarantees in a connection-oriented packet-switching network. The proposed RCSP queueing discipline avoids problems in previous proposed solutions. It achieves flexibility in the allocation of delay and bandwidth, as well as simplicity of implementation. The key idea is to separate rate-control and delay-control functions in the design of the server. Applying this separation of functions will result in a class of service disciplines, of which RCSP is an instance. ------------------------------------------------------------------------------- tr-92-004.ps.Z Best-First Model Merging for Dynamic Learning and Recognition Stephen M. Omohundro TR-92-004 January 1992 "Best-first model merging" is a general technique for dynamically choosing the structure of a neural or related architecture while avoiding overfitting. It is applicable to both learning and recognition tasks and often generalizes significantly better than fixed structures. We demonstrate the approach applied to the tasks of choosing radial basis functions for function learning, choosing local affine models for curve and constraint surface modelling, and choosing the structure of a balltree or bumptree to maximize efficiency of access. ------------------------------------------------------------------------------- tr-92-005.ps.Z New algorithmic results for lines-in-3-space problems Leonidas J. Guibas and Marco Pellegrini TR-92-005 January 1992 In the first part of the report we consider some incidence and ordering problems for lines in 3-space. We solve the problem of detecting efficiently if a query simplex is collision-free among polyhedral obstacles. In order to solve this problem we develop new on-line data structures to detect intersections of query halfplanes with sets of lines and segments. Then, we consider the nearest-neighbor problems for lines. Given a set of$n$ lines in 3-space, the shortest vertical segment between any pair of lines is found in randomized expected time $O(n^{8/5+\epsilon})$ for every $\eps>0$. The longest connecting vertical segment is found in time $O(n^{4/3+\eps})$. The shortest connecting segment is found in time $O(n^{5/3 + \epsilon})$. Problems involving lines, points and spheres in 3-space have important applications in graphics, CAD and optimization. In the second part of the report we consider several problems of this kind. We give subquaratic algorithms to count the number of incidences between a set of lines and a set of spheres, and to find the minimum distance between a set of lines and a set of points. We show that the sphere of minimum radius intersecting every line in a set of $n$ lines can be found in optimal expected time $O(n)$. Given $m$ possibly intersecting spheres we solve ray-shooting queries in $O(\log^2 m)$ time using a data structure of size $O(m^{5+\eps})$. This technical report collects part of the second author's work at I.C.S.I. form September 1991 to January 1992. ------------------------------------------------------------------------------- tr-92-006.ps.Z The LOGIDATA+ Object Algebra Umberto Nanni, Silvio Salza, Mario Terranova TR-92-006 February 1992 In this paper we present the LOGIDATA+ Object Algebra (LOA), an algebra for complex objects which has been developed within the LOGIDATA project funded by the Italian National Research Council (CNR). LOGIDATA+ is intended to provide a rule based language on a data model with structured data types, object identity and sharing. LOA is a set-oriented manipulation language which was conceived as an internal language for a prototype system supporting such a rich environment. The algebra refers to a data model that includes structured data types and object identity, thus allowing both classes of objects and value-based relations. LOA must deal with a rule based language with possible recursive programs with limited forms of negation. LOA programs explicitly include a "fixpoint" operator over a set of algebraic equations. Figures are omitted in the ftp-able version of the paper. A complete version is available from ICSI. ------------------------------------------------------------------------------- tr-92-007.ps.Z The LOGIDATA+ Prototype System Umberto Nanni, Silvio Salza, Mario Terranova TR-92-007 February 1992 In this paper we present a prototype system developed within LOGIDATA+, a national project funded by the Italian National Research Council (CNR). The prototype supports a rule based language on a data model with structured data types, object identity and sharing. The system has an interactive user interface, with a unit of interaction consisting of a LOGIDATA+ program , to extract information from the knowledge base and/or modify the schema. A program consists of a set of rules, and of additional directives to handle the data output and/or the updates to the schema. The prototype handles a temporary (user) environment where updates are performed and a permanent one, updated on request. The system uses LOA (LOGIDATA+ Object Algebra) as an intermediate internal language (see ICSI TR-92-006). User programs are translated into LOA programs, i.e. sequences of fixpoint systems of algebraic equations. The prototype is built on the top of a relational DBMS, that handles SQL transactions and provides the basic support for the permanent storage of data as well as for concurrency control and recovery. A main memory database has been included in the architecture, to improve the performance in the evaluation of the fixpoint systems, by keeping in main memory the intermediate results. Figures are omitted in the ftp-able version of the paper. A complete version is available from ICSI. ------------------------------------------------------------------------------- tr-92-008.ps.Z Linear Time Algorithms for Liveness and Boundedness in Conflict-free Petri Nets Paola Alimonti, Esteban Feuerstain, Umberto Nanni TR-92-008 February 1992 In this paper we consider the problems of deciding the set of potentially firable transitions, the liveness and boundedness for the class of Conflict-Free Petri Nets. For these problems we propose algorithms which are linear in the size of the description of the net, dramatically improving the best previous known results for these problems. Moreover the algorithm for the first problem is incremental: it is possible to perform an arbitrary sequence of updates, introducing new transitions and increasing the initial marking of the net, and queries, asking whether any transition is firable or any place reachable. Queries are answered in constant time, and the total cost for all the modifications is still linear in the size of the final net. Our approach is based on a representation of conflict-free Petri nets by means of directed hypergraphs. Figures are omitted in the ftp-able version of the paper. A complete version is available from ICSI. ------------------------------------------------------------------------------- tr-92-009.ps.Z Fish in Schools or Fish in Cans Evolutionary Thinking and Formalization Dirk Siefkes tr-92-009 February 1992 Gregory Bateson maintains that individual development and natural evolution follow the same principles --he parallels learning and evolution. I try to establish the precise mechanism of human learning by attributing the role of genes to concepts. We develop our thoughts conceptually through selection, in the same way that living beings develop genetically. Thus, thoughts evolve in our mind like fish in a cove, thoughts yielding concepts as the genetic material from which new thoughts arise. ------------------------------------------------------------------------------- tr-92-010.ps.Z A New Algorithm for Counting Circular Arc Intersections Marco Pellegrini TR-92-010 February 1992 We discuss the following problem: given a collection $\Gamma$ of $n$ circular arcs in the plane, count all intersections between arcs of $\Gamma$. We present an algorithm whose expected running time is $O(n^{3/2+\eps})$, for every $\eps >0$. If the arcs have all the same radius the expected time bound is $O(n^{4/3+\eps})$, for every $\eps>0$. Both results improve on the time bounds of previously known asymptotically fastest algorithms. The technique we use is quite general and it is applicable to other counting problems. ------------------------------------------------------------------------------- tr-92-011.ps.Z The Weighted List Update Problem and the Lazy Adversary Fabrizio d'Amore, Alberto Marchetti-Spaccamela, Umberto Nanni TR-92-011 February 1992 The List Update Problem consists of maintaining a dictionary as an unsorted linear list. A request consists in an item to be found, and the list may be rearranged in order to minimize the cost of processing a sequence of requests. Several kind of adversaries can be considered to analyze the behavior of heuristics for this problem. It is known that the Move-To-Front (MTF) heuristics is 2-competitive against a strong adversary [Tarjan'85]. A "lazy" (offline) adversary cannot rearrange the list but still, no algorithm can be better than 2-competitive against the lazy adversary [Bentley-McGeoch'85]. In the Weighted List Update Problem (WLUP) the cost of accessing an item depends on the item itself. It is shown that MTF is not competitive by any constant factor for WLUP against a lazy adversary. Two heuristics, based on the MTF strategy, are presented for WLUP: - RMTF is randomized and uses biased coins; - CMTF is deterministic, and replaces coins with counters. Both are shown to be 2-competitive against a lazy adversary. We apply this approach for searching items in a tree (TUP), proving that any c-competitive heuristic for the weighted list update problem provides a c-competitive heuristic for this last problem. ------------------------------------------------------------------------------- tr-92-013.ps.Z Competitive On-line Algorithms for Paging and Graph Coloring Sandy Irani TR-92-013 January 1992 We analyze the competitiveness of on-line algorithms for two problems: paging and on-line graph coloring. In the first problem, we develop a refinement of competitive analysis for paging algorithms which addresses some of the areas where traditional competitive analysis fails to represent what is observed in practice. For example, traditional competitive analysis is unable to discern between LRU and FIFO, although in practice LRU performs much better than FIFO. In addition, the theoretical competitiveness of LRU is much more pessimistic than what is observed in practice. We also address the following important question: given some knowledge of a program's reference pattern, can we use it to improve paging performance on that program? We address these concerns by introducing an important practical element that underlies the philosophy behind paging: locality of reference. We devise a graph-theoretical model, the access graph, for studying locality of reference. The second problem that we consider is on-line graph coloring. In the spirit of competitiveness, we evaluate on-line graph coloring algorithms by their performance ratio which measures the number of colors the algorithm uses in comparison to the chromatic number of the graph. We consider the class of d-inductive graphs. A graph G is d-inductive if the vertices of G can be numbered so that each vertex has at most d edges to higher numbered vertices. We analyze the greedy algorithm and show that if G is d-inductive then FF uses O( d log n) colors on G. We show that this bound is tight. Since planar graphs are 5-inductive, and chordal graphs are c(G)-inductive, (where c(G) is the chromatic number of the graph G), our results yield bounds on the performance ratio of greedy on these important classes of graphs. We also examine on-line graph coloring with lookahead. An algorithm is on-line with lookahead l, if it must color vertex i after examining only the first l+i vertices. We show that for l < (n / log n) no on-line algorithm with lookahead l can perform better than First Fit on d-inductive graphs. Keywords: on-line algorithms, competitive analysis, paging, locality of reference, on-line graph coloring, lookahead. ------------------------------------------------------------------------------- tr-92-012.ps.Z Towards a Complexity Theory for Approximation Karl Aberer, Bruno Codenotti TR-92-012 This paper presents a novel approach to the analysis of numerical problems, which is closely related to the actual nature of numerical algorithms. In fact, models of computation are introduced which take into account such issues as adaptivity and error. Moreover, complexity vs error bounds and examples regarding the role of adaptivity are provided. Finally, it is shown that the overall approach fits naturally into an algebraic framework. ------------------------------------------------------------------------------- tr-92-015.ps.Z Queueing Delays in Rate Controlled Networks Anindo Banerjea and Srinivasan Keshav TR-92-015 March 1992 This paper addresses the problem of finding the worst case end-to-end delay and buffer occupancy bounds in networks of rate-controlled, non-work conserving servers. The calculations are based on a simple fluid model, but care is taken so that the computed delay and buffer occupancy values are upper bounds on actual values. A simple algorithm is presented to perform these calculations in linear time. Simulation results compare the computed worst case delays with the actual delays obtained on some simple network topologies. The algorithm is found to predict node delays well for bursty input traffic, but poorly for smooth input traffic. Buffer requirements are predicted well in both cases. ------------------------------------------------------------------------------- tr-92-016.ps.Z A Framework for the Study of Pricing in Integrated Networks. Colin J. Parris, Srinivasan Keshav, and Domenico Ferrari. TR-92-016 March 1992 Integrated networks of the near future are expected to provide a wide variety of services, which could consume widely differing resources. We present a framework for pricing services in integrated networks, and study the effect of pricing on user behavior and network performance. We first describe a network model that is simple, yet models details such as the wealth distribution in society, different classes of service, peak and off-peak traffic and call blocking due to budgetary constraints. We then perform experiments to study the effect of setup, per packet, and peak load prices on the blocking probability of two classes of calls passing through a single node enforcing admission control. Some selected results are that a) increasing prices first increases the net revenue to a provider, then causes a decrease b) peak-load pricing spreads network utilization more evenly, raising revenue while simultaneously reducing call blocking probability. Finally, we introduce a novel metric for comparing pricing schemes, and prove that for the most part, a pricing scheme involving setup prices is better than a pricing scheme with no setup cost. ------------------------------------------------------------------------------- tr-91-010.ps.Z How Receptive Field Parameters Affect Neural Learning Stephen M. Omohundro and Bartlett W. Mel TR-91-010 January 1991 We identify the three principle factors affecting the performance of learning by networks with localized units: unit noise, sample density, and the structure of the target function. We then analyze the effect of unit receptive field parameters on these factors and use this analysis to propose a new learning algorithm which dynamically alters receptive field properties during learning. ------------------------------------------------------------------------------- tr-92-018.ps.Z A Resource Based Pricing Policy for Real-Time Channels in a Packet-Switching Network. Colin J. Parris and Domenico Ferrari. TR-92-018 March 1992 In the packet switching networks of the future the need for guaranteed performance on a wide variety of traffic characteristics will be of paramount importance. The generation of revenue, to recover costs and provide profit, and the multiple type of services offered will require that new pricing policies be implemented. This paper presents a resource based pricing policy for real-time channels ( ie., channels with guaranteed performance ) in a packet switching network. The policy is based on a set of specific criteria, and the charges for any channel are based on the resources reserved for use by the channel. This reservation charge is based on the type of service requested, the time of day during which the channel exists, and the lifetime of the channel. We argue that the traditional resources are not sufficient to determine a fair reservation charge for a channel offering guaranteed delay bounds, and we introduce the notion of a delay resource in our charging formula. The type of service requested is thus characterized by the amount of the bandwidth, buffer space, CPU, and delay resources reserved. The analysis of this pricing policy is reduced to the analysis of a single node of the network, assuming a homogeneous network. This single-node characteristic increases the scalability and flexibility of the policy. An example of an implementation of this policy is provided. ------------------------------------------------------------------------------- tr-92-019.ps.Z Design of a Continuous Media Data Transport Service and Protocol Mark Moran and Bernd Wolfinger TR-92-019 April 1992 Applications with real-time data transport requirements fall into two categories: those which require transmission of data units at regular intervals, which we call continuous media (CM) clients, e.g. video conferencing, voice communication, high-quality digital sound; and those which generate data for transmission at relatively arbitrary times, which we call real-time message-oriented clients. Because CM clients are better able to characterize their future behavior than message-oriented clients, a data transport service dedicated for CM clients can use this a priori knowledge to more accurately predict their future resource demands. Therefore, a separate transport service can potentially provide a more cost-effective service along with additional functionality to support CM clients. The design of such a data transport service for CM clients and its underlying protocol (within the BLANCA gigabit testbed project) will be presented in this document. This service provides unreliable, in-sequence transfer (simplex, periodic) of so-called stream data units (STDUs) between a sending and a receiving client, with performance guarantees on loss, delay, and throughput. ------------------------------------------------------------------------------- tr-92-020.ps.Z Read-Once Threshold Formulas, Justifying Assignments, and Generic Tranformations Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein, Marek Karpinski TR-92-020 March, 1992 We present a membership query (i.e. interpolation) algorithm for exactly identifying the class of read-once formulas over the basis of boolean threshold functions. Using a generic transformation from [Angluin, Hellerstein, Karpinski 89], this gives an algorithm using membership and equivalence queries for exactly identifying the class of read-once formulas over the basis of boolean threshold functions and negation. We also present a series of generic transfor- mations that can be used to convert an algorithm in one learning model into an algorithm in a different model. Keywords: -------- Learning Algorithms, Queries, Read-Once Formulas, Treshold Functions. ------------------------------------------------------------------------------- tr-92-021.ps.Z Bruno Codenotti and Luciano Margara, Local Properties of Some NP-Complete Problems tr-92-021 April 1992. It has been shown that certain NP-complete problems, i.e. TSP, min cut, and graph partitioning, with specific notions of neighborhood, satisfy a simple difference equation. In this paper, we extend these results by proving that TSP with 2-change, 2+3-new-change, and 3-new-change notions of neighborhood satisfy such a difference equation, and we derive some properties of local search when performed with the above definitions of neighborhood. ------------------------------------------------------------------------------- tr-92-022.ps.Z Petri Net Based Software Validation; Prospects and Limitations Monika Heiner TR-92-022 March 1992 Petri net based software validation to check the synchronization structure against some data or control flow anomalies (like unboundednesss or non-liveness) has been a well-known and widely used approach for about ten years. To decrease the complexity problem and because the simpler the model, the more efficient the analysis, the validation is usually tried with the help of place transition Petri nets. However, the modelling with this Petri net class involves two important abstractions of actual software properties -- the time consumption of any action and the data dependencies among conflict decisions. Basically, this paper discusses some problems resulting from these abstractions in the models analyzed which are very often neglected and have therefore not been well understood up to now. Furthermore, discussing the pros and cons of the Petri net approach is done by offering a rough overview of the given background of dependable distributed software engineering. Suggestions for a related workstation supporting different net-based methods are outlined. ------------------------------------------------------------------------------- tr-92-023.ps.Z Quality-of-Service Negotiation in a Real-Time Communication Network Jean Ramaekers and Giorgio Ventre TR-92-023 April 1992 In the recent years new protocols and algorithms have been proposed to guarantee performance and reliability in exchanging data in real-time communication networks, and new services have been presented to allow cooperative office work, distributed conferencing, etc. Less attention has been paid to how applications and, more generally, clients of real-time communication services can interact with the network in order to specify and negotiate the quality-of-service of a connection. We believe that this problem is going to become a key issue for the success of future distributed systems, since it affects both client and network performances. In this paper we present a new mechanism for the establishment of real-time connections in a quality-of-service network developed for the Tenet real-time protocol suite. By improving the information exchanged between the network and the clients, the model allows to reduce the complexity and the time required to establish a real-time connection, and increases the network utilization. Additionally, we introduced a new class of real-time communication service to support adaptive quality-of-service, in order to enhance the possibilities of the network to face congestion situations. ------------------------------------------------------------------------------- tr-92-024.ps.Z Communicating with Low-Diffraction Lasers and Mirrors Richard Beigel TR-92-024 April 7, 1992 Optical interconnection networks, in which each processor contains a set of lasers for communication with other processors, have long been studied. In the ``regular optics'' model of Murdocca a bounded number of planar mirrors are used to redirect light beams, and each processor has a bounded number of lasers directed at a fixed set of angles, independent of the processor. It is theoretically interesting to ignore diffraction, and assume that lasers beams travel in a straight line. In the regular optical model, we present elegant layouts for processor networks including the shuffle, grids, and Margulis' expander graph. We also disprove the existence of a certain kind of 3-dimensional layout for shuffles. Using slightly more complicated optical devices, such as beam splitters, we design a ``light guide,'' which allows simultaneous broadcasts, subject only to the limitations of light sensors. In particular, the light guide can perform single broadcasts. Given accurate enough clocks, it can perform arbitrary permutations. ------------------------------------------------------------------------------- tr-92-025.ps.Z Tree Matching with Recursive Distributed Representations Andreas Stolcke and Dekai Wu TR-92-025 April 1992 We present an approach to the structure unification problem using distributed representations of hierarchical objects. Binary trees are encoded using the recursive auto-association method (RAAM), and a unification network is trained to perform the tree matching operation on the RAAM representations. It turns out that this restricted form of unification can be learned without hidden layers and producing good generalization if we allow the error signal from the unification task to modify both the unification network and the RAAM representations themselves. ------------------------------------------------------------------------------- tr-92-026.ps.Z On the Power of Discontinous Approximate Computations Karl Aberer, Bruno Codenotti TR-92-026 The set of operations S_1={+,-,*,/,>} is used in algebraic computations to avoid degeneracies (e.g., division by zero), but is also used in numerical computations to avoid huge roundoff errors (e.g., division by a small quantity). On the other hand, the classes of algorithms using operations from the set S_2={+,-,*,/} or from the set S_3={+,-,*} are the most studied in complexity theory, and are used, e.g., to obtain fast parallel algorithms for numerical problems. In this paper, we study, by using a simulation argument, the relative power of the sets S_1, S_2, and S_3 for computing with approximations. We prove that S_2 does very efficiently simulate S_1, while S_3 does not; this fact shows and measures the crucial role of division in computations introducing roundoff errors. We also show how to construct algorithms using operations {+,-,*,/} which achieve for most inputs the same error bounds as algorithms using operations {+,-,*,/,>}. To develop our simulation strategy we combine notions imported from approximation theory and topology with complexity and error bounds. More precisely, to find conditions under which this simulation can take place, we quantitatively describe the interplay between algebraic, approximation, topological, and complexity notions and we provide lower and upper bounds on the cost of simulation. ------------------------------------------------------------------------------- tr-92-029.ps.Z Efficient Computation of Spatial Joins Oliver Gunther TR-92-029 May 1992 Spatial joins are join operations that involve spatial data types and operators. Due to some basic properties of spatial data, many conventional join processing strategies suffer serious performance penalties or are not applicable at all in this case. In this paper we explore which of the join strategies known from conventional databases can be applied to spatial joins as well, and how some of these techniques can be modified to be more efficient in the context of spatial data. Furthermore, we describe a class of tree structures, called generalization trees, that can be applied efficiently to compute spatial joins in a hierarchical manner. Finally, we model the performance of the most promising strategies analytically and conduct a comparative study. ------------------------------------------------------------------------------- tr-92-034.ps.Z Ambiguities in Object Specifications in View of Data Testing Dieter Richter TR-92-034 June 1992 Checking data only relying on their specification is of importance when using neutral or standardized object models. Ambiguities arise during the tests because of specifications leaving a certain degree of freedom to the implementation. Based on an experimental background the observations and reflections about the reasons are systematically presented. It turns out that the transition (or mapping) from a specification of an object to a physical instance (or data set) has to take into consideration when defining neutral models. This transition which often has been seen as a technical question of the implementation or as the internal (hided) feature of a system appears as a particular point of the concept besides the specification of the semantics. One crucial point is the instance handling with respect to assign and comparison operations. The mapping from a specification into a database can be realized in various manners which leads to interpretation defects when testing independently. Another point is the weak scope definition in specifications. Several ambiguities are caused by it. A very frequent reason of misunderstandings is the imprecise or wrong understanding of the different relations between objects, logical and physical instances. There are approaches for more clear specifications. The last point is the representation of failures or more generally of the state of instances. A concept based on multiple inheritance seems to increase the abstraction level of state specifications on the same level as the used specification language is of. ------------------------------------------------------------------------------- tr-92-035.ps.Z Experiments with Noise Reduction Neural Networks for Robust Speech Recognition Michael Trompf trompf@rcs.sel.de TR-92-035 May, 1992 Speech recognition systems with small and medium vocabularies are used as natural human interface in a variety of real world applications. Though they work well in a laboratory environment, a significant loss in recognition performance can be observed in the presence of background noise. In order to make such a system more robust, the development of a neural network based noise reduction module is described in this paper. Based on function approximation techniques using multilayer feedforward networks (Hornik et al. 1990), this approach offers inherent nonlinear capabilities as well as easy training from pairs of corresponding noisy and noise-free signal segments. For the development of a robust nonadaptive system, information about the characteristics of the noise and speech components of the input signal and its past and future context is taken into account. Evaluation of each step is done by a word recognition task and includes experiments with changing signal parameters and sources to test the robustness of this neural network based approach. ------------------------------------------------------------------------------- tr-92-036.ps.Z Bruno Codenotti and Luciano Margara, Efficient Clustering Techniques for the Geometric Traveling Salesman Problem tr-92-036 June 1992. This paper presents some direct and iterative heuristic methods for the geometric Traveling Salesman Problem (TSP). All these methods are based on a particular notion of mass density, which can be used to construct a tour for the geometric TSP in an incremental fashion. In the iterative method, this technique is combined with the Lin-Kernighan method (LK), and this allows us to obtain better tours than those found by using LK itself. More precisely, the tour length we get is only 1.1% off the optimum. The direct method finds a solution passing through a sequence of subsolutions over progressively larger sets of points. These points are the relative maxima of the mass density obtained by using different parameter settings. The method has O(n^3) worst case running time and finds tours whose length is 9.2% off the optimal one. -------------------------------------------------------------------------------