SYSTEM FOR PATTERN RECOGNITION WITH Q-METRICS

• US 20080101705A1
• Filed: 10/31/2006
• Published: 05/01/2008
• Est. Priority Date: 10/31/2006
• Status: Abandoned Application

• Current Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Xiao, Weimin, Mohamed, Magdi A.
• Application Number:
  US11/554,643
• Publication Number:
  US 20080101705A1
• Time in Patent Office: Days
• US Class Current: 382/224
• CPC Class Codes: G06F 18/24137 Distances to cluster centroïds
• CPC Class Codes: G06V 40/10 Human or animal bodies, e.g. vehicle occupants or pedestrians; Body parts, e.g. hands

Abstract

A pattern recognition system (100, 900, 1202, 1300) includes a configurable distance metric evaluator (112, 600, 1204). The configurable distance metric evaluator (112, 600, 1204) is adaptable, via a configuration parameter to better match distributions of feature vectors within classifications and clusters and moreover to better match boundaries between feature vector subspaces associated with different classifications or clusters, and therefore provides for reduced pattern recognition errors.

Claims

1. A pattern recognition system comprising:

a configurable feature vector metric computer adapted to;

receive a configuration parameter according to which said configurable feature vector metric computer is configured;

receive a plurality of feature vectors representing measured subjects;

compute one or more distances between said feature vectors using the configurable feature vector metric; and

to output said one or more computed distances.

2. The pattern recognition system according to claim 1 wherein:

for values of said configuration parameter in a domain [−

1,0), operation of said configurable feature vector metric computer to compute said one or more computed distances from said plurality of feature vectors is described by an equation;

$d_{\mathrm{\lambda <br><br>},n}<br><br>\left(x,y\right)=\left[\underset{i=1}{\overset{n}{\prod <br><br>}}<br><br><br><br>\left(1+\mathrm{\lambda <br><br>}<br><br><br><br>x_i-y_i<br><br>\right)-1\right]/\mathrm{\lambda <br><br>}$

where λ

is said configuration parameter;

x_i ∈

[0,1] is an i^th component of a first n-dimensional feature vector denoted x

y_i ∈

[0,1] is an i^th component of a second n-dimensional feature vector denoted y

d_λ

(x,y) ∈

[0,n] is a computed distance between the first feature vector and the second feature vector.

3. The pattern recognition system according to claim 2 wherein:

said configurable feature vector metric computer is adapted to compute said one or more computed distances from said plurality of feature vectors by evaluating a recursive function;

ψ

_i=|x_i−

y_i|+ψ

<sub>i−

1</sub>+λ

|x_i−

y_i|ψ

<sub>i−

1</sub>, i=1, . . . , n;

starting with;

ψ

₀=0

4. The pattern recognition system according to claim 1 comprising:

a neural network pattern recognition system including a plurality of nodes, each of which operates on one or more inputs and produces an output, and wherein one or more of said plurality of nodes is adapted to use said configurable feature vector metric computer to compute said output from said one or more inputs.

5. The pattern recognition system according to claim 4 wherein:

each i^th node is adapted to operate on input in order to produce an output by a process that is described by an equation;

$y_i=\{\begin{array}{cc}\frac{\underset{j=1}{\overset{n}{\prod <br><br>}}<br><br><br><br>\left(1+{\mathrm{\lambda <br><br>}}_i<br><br>w_j<br><br><br><br>x_j-c_{\mathrm{ij}}<br><br>\right)-1}{\mathrm{\lambda <br><br>}}& {\mathrm{\lambda <br><br>}}_i\in <br><br>\left[-1,0\right)\\ \underset{j=1}{\overset{n}{\sum <br><br>}}<br><br>w_j<br><br><br><br>x_j-c_{\mathrm{ij}}<br><br>& {\mathrm{\lambda <br><br>}}_i=0\end{array}$

where, λ

_i ∈

[−

1,0] is a configuration parameter used by the i^th node;

y_i ∈

[0,n] is the output of the i^th node;

w_ij ∈

[0,1] is weight defining a coupling between a j^th node in a layer preceding the i^th node and the i^th node;

x_i ∈

[0,1] is an i^th component of an n-dimensional input feature vector denoted x; and

c_ij ∈

[0,1] is a j^th coordinate of an i^th feature vector space center that is associated with the i^th node.

6. The pattern recognition system according to claim 1 comprising:

a nearest prototype program executing computer wherein said nearest prototype program computes said one or more computed distances between input feature vectors and prototype feature vectors using said configurable feature vector metric computer.

7. A machine learning system comprising the:

the pattern recognition system according to claim 1;

a training supervisor system adapted to optimize said configuration parameter in order to reduce recognition errors.

8. The machine learning system according to claim 7 wherein said training supervisor system is adapted to optimize said configuration parameter separately for each of a plurality of classifications that are recognizable by said pattern recognition system.

9. The pattern recognition system according to claim 1 wherein said configurable feature vector metric computer comprises:

a subtracter comprising;

a first input for receiving a first feature vector;

a second input for receiving a second feature vector; and

an output;

wherein, said subtracter is adapted to compute a vector difference between said first feature vector and said second feature vector;

a magnitude computer comprising;

an input coupled to said output of said subtracter; and

an output;

wherein, said magnitude computer is adapted to compute an absolute value of each element of said vector difference;

at least one memory for storing said configuration parameter;

a first multiplier coupled to said at least one memory, said first multiplier comprising;

a first input for receiving said configuration parameter;

a second input for sequentially receiving a sequence of quantities each including one of said absolute value of said element of said vector difference; and

an output for outputting a product of said configuration parameter and each absolute value of said element of said vector difference;

a second multiplier comprising;

a first input coupled to said output of said first multiplier;

a second input; and

an output;

a first adder comprising;

a first input coupled to said output of said second multiplier;

a second input coupled to said at least one memory, for sequentially receiving said absolute value of each element of said vector difference; and

an output;

a second adder comprising;

a first input coupled to said output of said first adder;

a second input; and

an output for outputting a function value, which after a number of cycles of operations of the configurable feature vector metric computer equal to a dimension of the said first feature vector and said second feature vector is equal to said configurable feature metric;

a shift register comprising;

an input coupled to said output of said second adder; and

an output coupled to said second input of said second multiplier and coupled to said second input of said second adder.

10. The pattern recognition system according to claim 1 comprising an unsupervised classification system comprising a computer configured by at least one program to:

until a closest cluster center for each of a set of feature vectors, as measured by said configurable feature vector metric computer stabilizes;

find a closest cluster center among a set of cluster centers for each of said set of feature vectors;

optimize cluster center coordinates of said set of cluster centers and the configuration parameter for each cluster center of said set of cluster centers, in order to minimize a sum of distances from each particular cluster center to feature vectors that are closest to the particular cluster center.

11. The pattern recognition system according to claim 10 wherein:

for values of said configuration parameter in a domain [−

1,0), operation of said configurable feature vector metric computer to compute said one or more computed distances from said plurality of feature vectors is modeled by an equation;

$d_{\mathrm{\lambda <br><br>},n}<br><br>\left(x,y\right)=\left[\underset{j=1}{\overset{n}{\prod <br><br>}}<br><br><br><br>\left(1+\mathrm{\lambda <br><br>}<br><br><br><br>x_i-y_i<br><br>\right)-1\right]/\mathrm{\lambda <br><br>}$

where λ

is said configuration parameter;

x_i ∈

[0,1] is an i^th component of a first n-dimensional feature vector denoted x

y_i ∈

[0,1]is an i^th component of a second n-dimensional feature vector denoted y

d_λ

(x,y)∈

[0,n] is a computed distance between the first feature vector and the second feature vector.

12. The pattern recognition system according to claim 1 comprising a supervised nearest prototype pattern recognition training system comprising a computer configured by at least one program to:

read a set of class labeled training feature vectors;

read a specified number of clusters;

numerically optimizing, at least, a set of clusters centers for said specified number of clusters, and a set of values of said configuration parameter for said specified number of clusters in order to minimize sharing of nearest cluster centers by class labeled training vectors of different classes.

13. The pattern recognition system according to claim 12, wherein in numerically optimizing, said computer is configured by said at least one program to:

generate an initial population of arrays of numerical parameters, wherein each array includes a cluster center for each of the specified number of clusters, and a value of said configuration parameter for each of the specified number of clusters;

for each of a succession of generations of said population of arrays; and

for each array;

assign each class labeled training feature vector to a said cluster center that is nearest to each class labeled training feature vector;

calculate a classification confusion matrix; and

calculate a fitness measure from said classification confusion matrix;

check if a stopping criteria has been met, and if said stopping criteria has not been met;

replicating arrays for a next generation based on said fitness measure;

perform evolutionary operations on said next generation.

14. The pattern recognition system according to claim 13 wherein each array also includes at least one set of dimension weights.

15. The pattern recognition system according to claim 14 wherein each array includes a set of dimension weights for each of the specified number of clusters.

16. The pattern recognition system according to claim 13, wherein in calculate said fitness measure, said computer is configured by said at least one program to:

multiply the classification confusion matrix by a transpose of the classification confusion matrix to obtain a confusion matrix;

subtract the confusion matrix from an identity matrix to obtain a difference matrix; and

sum squares of elements of the difference matrix.