-
Thomas G. Dietterich and Ryszard S. Michalski.
Learning to Predict Sequences.
In Ryszard S. Michalsky,
Jaime G. Carbonell,
and Tom M. Mitchell, editors,Machine Learning -- An Artificial Intelligence Approach,
volume 2,
pages 63--106.
1986.
Keywords:
Sequential/Temporal Data.
| Abstract: |
This chapter considers the problem of discovering a rule characterizing a given sequence of events (objects) and able to predict continuations of the sequence. This prediction is nondeterministic because the rule doesn't necessarily tell exactly which events must appear next in the sequence but rather determines a set of plausible next events. It is assumed that the individual events in the sequence are characterized by a set of attributes and that the next event depends solely on the values of the attributes for the previous events in the sequence. The attributes are either initially given or derived from the initial ones through a chain of inferences. Three basic rule models are employed to guide the search for a sequence-generating rule: decomposition, periodic, and disjunctive normal form (DNF). The search process involves simultaneously transforming the initial sequencs to {\sl derived} sequences and instantiating general rule models to find the best match between the instantiated model and the derived sequence. A program called SPARC/E is described that implements most of the methodology as applied to discovering sequence-generating rules in the card game Eleusis. This game, which attempts to model the process of scientific discovery, is used as a source of examples illustrating the performance of SPARC/E. |
-
Haruo Asada and Michael Brady.
The Curvature Primal Sketch.
TPAMI,
8(1):2--14,
1986.
Keywords:
Multiscale Analysis,
Image Data.
| Abstract: |
In this paper we introduce a novel representation of the significant changes in curvature along the bounding contour of planar shape. We call the representation the {\sl Curvature Primal Sketch} because of the close analogy to the primal sketch representation advocated by Marr for describing significant intensity changes. We define a set of primitive parameterized curvature discontinuities, and derive expressions for their convolutions with the first and second derivatives of a Gaussian. We describe an implemented algorithm that computes the Curvature Primal Sketch by matching the multiscale convolutions of a shape, and illustrate its performance on a set of tool shapes. Several applications of the represntation are sketched. |
-
Jean Babaud,
Andrew P. Witkin,
Michel Baudin,
and Richard O. Duda.
Uniqueness of the Gaussian Kernel for Scale-Space Filtering.
TPAMI,
8(1):26--33,
1986.
Keywords:
Multiscale Analysis,
Sequential/Temporal Data,
Image Data.
| Abstract: |
Scale-space filtering constructs hierarchic symbolic signal descriptions by transforming the signal into a continuum of versions of the original signal convolved with a kernel containing a scale or bandwidth parameter. It is shown that the Gaussian probability density function is the only kernel in a broad class for which first-order maxima and minima, respectively, increase and decrease when the bandwidth of the filter is increased. The consequences of this result are explored when the signal -- or its image by a linear differential operator -- is analyzed in terms of zero-crossing contours of the transform in scale-space. |
-
Robert L. Cannon,
Jitendra V. Dave,
and James C. Bezdek.
Efficient implementation of the fuzzy c-means clustering algorithms.
TPAMI,
8(2):248--255,
1986.
Keywords:
Clustering,
Fuzzy c-Means,
Image Data,
Speed-up Issues.
| Abstract: |
This paper reports the results of a numerical comparison of two versions of the fuzzy c-means (FCM) clustering algorithms. In particular, we propose and exemplify an approximate fuzzy c-means (AFCM) implementation based upon replacing the necessary ``exact'' variates in the FCM equation with integer-valued or real-valued estimates. This approximation enables AFCM to explot a lookup table approach for computing Euclidean distances and for exponentiation. The net effect of the proposed implementation is that CPU time during each iteration is reduced to approximately a sixth of the time required for a literal implementation of the algorithm, while apparently preserving the overall quality of terminal clusters produced. The two implementations are tested numerically on a nine-band digital image, and a pseudocode subroutine is given for the convenience of applications-oriented readers. Our results suggest that AFCM may be used to accelerate FCM processing whenever the feature space is comprised of tuples having a finite number of integer-valued coordinates. |
-
James George Dunham.
Optimum Uniform Piecewise Linear Approximation of Planar Curves.
TPAMI,
8(1):67--75,
1986.
Keywords:
Piecewise Linear Representations.
| Abstract: |
Two-dimensional digital curves are often uniformly approximated by polygons or piecewise linear curves. Several algorithms have been proposed in the literature to find such curves. We present an algorithm that finds a piecewise linear curve with the minimal number of segments required to approximate a curve within a uniform error with fixed initial and final points. We compare our optimal algorithm to several suboptimal algorithms with respect to the number of linear segments required in the approximation and the execution time of the algorithm. |
-
Martin A. Fischler and Robert C. Bolles.
Perceptual Organization and Curve Partitioning.
TPAMI,
8(1):100--105,
1986.
| Abstract: |
In this paper we offer a critical evaluation of the partitioning (perceptual organization) problem, noting the extent to which it has distinct formulations and parameterizations. We show that most partitioning techniques can be characterized as variations of four distinct paradigms, and argue that any effective technique must satisfy two general principles. We give concrete substance to our general discussion by introducing new partitioning techniques for planar geometric curves, and present experimental results demonstrating their effectiveness. |
-
Hiroshi Imai and Masao Iri.
An Optimal Algorithm for Approximating a Piecewise Linear Function.
JIP,
9(3):159--162,
1986.
Keywords:
Piecewise Linear Representations.
| Abstract: |
It is shown that the problem of approximating a given piecewise linear function with $n$ nondifferentiable points by another piecewise linear function such that the absolute value of the difference between the two functions be bounded by a given constant and that the number of nondifferentiable points of the latter function be minimum can be solved in $O(n)$. |
-
John Ross Quinlan.
Induction of Decision Trees.
ML,
1:81--106,
1986.
Keywords:
Decision Trees,
Artificial Intelligence.
| Abstract: |
The technology for building knowledge-based systems by inductive inference from examples has been demonstrated successfully in several practical applications. This paper summarizes an approach to synthesizing decision trees that has been used in a variety of systems, and it describes one such system, ID3, in detail. Results from recent studies show ways in which the methodology can be modified to deal with information that is noisy and/or incomplete. A reported shortcoming of the basic algorithm is discussed and two means of overcoming it are compared. The paper concludes with illustrations of current research directions. |
-
L.R. Rabiner and B.H. Juang.
An Introduction to hidden Markov models.
ASSP,
3:4--16,
1986.
| Abstract: |
The basic theory of Markov chains has been known to mathematicians and engineers for close to 80 years, but it is only in the past decade that it has been applied explicitly to problems in speech processing. One of the major reasons why speech models, based on Markov chains, have not been developid until recently was the lack of a method for optimizing the parameters of the Markov model to match observed signal patterns. Such a method was proposed in the late 1960's and was immediately applied to speech processing in several reseach institutions. Continued refinement in the theory and implementation of Markov modelling techniques have greatly enhanced this method, leading to a wide range of applications of these models. It is the purpose of this tutorial paper to give an introduction to the theory of Markov models, and to illustrate how they have been applied to the problems in speech recognition. |
-
Shokri Z. Selim and M. A. Ismail.
On the Local Optimality of the Fuzzy Isodata Clustering Algorithm.
TPAMI,
8(2):284--288,
1986.
Keywords:
Clustering.
| Abstract: |
The convergence of the fuzzy ISODATA clustering algorithm was proved by Bezdek. Two sets of conditions were derived and it was conjectured that they are necessary and sufficient for a local minimum point. In this paper, we address this conjecture and explore the properties of the underlying optimization problem. The notions of reduced objective function and improving and feasible directions are used to examine this conjecture. Finally, based on the derived properties of the problem, a new stopping criterion for the fuzzy ISODATA algorithm is proposed. |
-
E. Skordalakis.
Syntactic ECG Processing: A Review.
PR,
19(4):305--313,
1986.
Keywords:
Medical Applications.
| Abstract: |
The work which has been made so far in the field of syntactic electrocardiogram (ECG) processing is reviewed in this paper. Although syntactic methods seem suitable to the analysis of waveforms, not much progress has been made in the area of ECG waveforms. The reason for this are given together with directions on how the difficulties could be overcome. |
|