Browse Prior Art Database

# Fast Labelling by Precomputation of Inter-Prototype Distances

IP.com Disclosure Number: IPCOM000062213D
Original Publication Date: 1986-Oct-01
Included in the Prior Art Database: 2005-Mar-09
Document File: 2 page(s) / 53K

IBM

## Abstract

Speech may be considered a Euclidean space in which a spectral vector represents a segment of input speech and in which prototype vectors represent respective classes of sound or speech according to predefined characteristics. The present invention relates to methodology wherein the prototype vector that is closest to the spectral vector is determined without the need for computing a respective distance between the spectral vector and each prototype vector. In accordance with the invention, candidate prototype vectors are eliminated from consideration by using the triangle law and precomputation. Let x be a spectral vector and let y1y2 ...yk be k prototype vectors. During labelling it is required to find the y nearest to xi, i.e., an I such that: where d(x,y) denotes a distance.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 98% of the total text.

Page 1 of 2

Fast Labelling by Precomputation of Inter-Prototype Distances

Speech may be considered a Euclidean space in which a spectral vector represents a segment of input speech and in which prototype vectors represent respective classes of sound or speech according to predefined characteristics. The present invention relates to methodology wherein the prototype vector that is closest to the spectral vector is determined without the need for computing a respective distance between the spectral vector and each prototype vector. In accordance with the invention, candidate prototype vectors are eliminated from consideration by using the triangle law and precomputation. Let x be a spectral vector and let y1y2 ...yk be k prototype vectors. During labelling it is required to find the y nearest to xi, i.e., an I such that: where d(x,y) denotes a distance. Let aij be the precomputed inter- prototype distances: Then, 2d(x,yi) < aij implies that I=j is impossible. Then, each time a new d(x,yi) is computed, the following subset of prototypes is eliminated from further consideration;

(Image Omitted)

The behavior of this algorithm has been simulated using prototypes of various dimensions n and a uniform distribution in n-dimensional space. That is,

(Image Omitted)

The results are shown in the table on the preceding page. An entry in the table is the average number of distances computed divided by the maximum, i.e., the number of prototypes n.

1

Page 2 of 2

2