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.
-------------------------------------------------------------------------------