US 8,805,653 B2Granted

Supervised nonnegative matrix factorization

AssigneeSeiko Epson Corporation

InventorsSeung-il Huh, Mithun Das Gupta, Jing Xiao

Life of this patent

Estimating the term…

Abstract

Graph embedding is incorporated into nonnegative matrix factorization, NMF, while using the original formulation of graph embedding. Negative values are permitted in the definition of graph embedding without violating the nonnegative requirement of NMF. The factorized matrices of NMF are found by an iterative process.

Claims18

Dependent claims

A pattern recognition method, comprising:

providing a data processing device to implement the following steps:
accessing multiple sets of training data, each set of training data having at least one of a true example of a pattern to be recognized or a false example of a pattern to be recognized;
arranging said multiple sets of data into a data matrix U in an electronic memory constituting a data store, wherein each set of training data is arranged as a separate column in data matrix U and data matrix U is defined as Uεd×n, where is the set of real numbers and d×n define the dimensions of data matrix U;
defining an intrinsic graph G to label specific features of most interest in the sets of training data, wherein G={U,W}, labels that identify favorable features that are features characteristic of the pattern to be recognized are added to the sets of training data in U, each column of U represents a vertex, W is a similarity matrix and each element of similarity matrix W measures the similarity between vertex pairs;
defining a penalty graph G to label specific features of least interest in the sets of training data, wherein G={U, W}, labels that identify unfavorable features that are features not characterisic of the pattern to be recognized are added to the sets of training data in U, W is a dissimilarity matrix, and each element of dissimilarity matrix W measures unfavorable relationships between said vertex pairs;
defining an intrinsic diagonal matrix D, wherein D=[Dij] and Dii=Σj=1nWij;
defining an intrinsic Laplacian matrix L, wherein L=D−W;
defining a penalty diagonal matrix D, wherein D=[ Dij] and Dii=Σj=1n= Wij;
defining a penalty Laplacian matrix L, wherein L= D− W;
defining a basis matrix V, wherein Vεd×r and basis matrix V is to hold basis examples of the sets of training data, the basis examples being a reduction of the sets of training data into simplified representations that highlight distinguishing characteristics of the pattern to be recognized;
defining a feature matrix X, wherein Xεr×n feature matrix X is to hold features values to construct an approximation of U from basis matrix V;
incorporating the label information of intrinsic graph G and penalty graph G into the construction of basis matrix V and features matrix X by defining a measure of the compactness of intrinsic graph G by the weighted sum of squared distances defined as Σi<jnWij∥xi−xj∥2=Tr(XLXT), wherein xi is the i-th column of X and xj is the j-th column of X;
defining a measure of the separability of penalty graph G by the weighted sum of squared distances defined as Σi<jn Wij∥xi−xj∥2=Tr(X LXT) wherein xi is the i-th column of X and xj is the j-th column of X;
defining F(1)(V,X) as an objective of NMF (nonnegative matrix factorization), F(1)(V,X) being proportional to F(1)(V,X)=½∥U−VX∥F2;
defining F(2)(X) as an objective of graph embedding, F(2)(X) being proportional to ratio
Tr
⁡
(
XLX
T
)
Tr
⁡
(
X
⁢
L
_
⁢
X
T
)
;
deriving an SNMF (supervised nonnegative matrix factorization) objective from a sum of F(1)(V,X) and F(2)(X);
populating basis matrix V and feature matrix X by solving the derived SNMF objective through iterative multiplicative updates;
and
separating recognizable patterns within the basis examples of basis matrix V into distinct pattern classifications using a data classifier, these pattern classifications of the basis examples being deemed the recognized patterns of the sets of training data;
wherein:
said pattern recognition method is a face detection method;
each of said set of training data is a distinct training image;
the favorable features labeled in intrinsic graph G identify regions within each distinct training image that are to be focused upon when defining the basis examples;
the unfavorable features labeled in intrinsic graph G identify regions within each distinct training image that are of least interest when defining the basis examples;
at least one of said distinct pattern classifications is a face pattern classification;
and
a received test image is tested for the existence of a face by determining a basis test sample from the received test image, submitting the basis test sample to the data classifier, and if the data classifier identifies the basis test sample as belonging to the face pattern classification, then deeming the received test image as having a rendition of a face.

42 more elements

A pattern recognition system for processing input test data, comprising:

an electronic memory storing multiple sets of training data, each set of training data having at least one of a true example of a pattern to be recognized or a false example of a pattern to be recognized, wherein said electronic memory constitutes a data store, said multiple sets of training data are arranged into a data matrix U, each set of training data is arranged as a separate column in data matrix U, and data matrix U is defined as Uεd×n where is the set of real numbers and d×n define the dimensions of data matrix U;
a data processing device having access to said electronic memory and being configured to implement the following steps:
defining an intrinsic graph G to label specific features of most interest in the sets of training data, wherein G={U,W}, labels that identify favorable features that are features characterisic of the pattern to be recognized are added to the sets of training data in U, each column of U representing a vertex, W is a similarity matrix and each element of similarity matrix W measures the similarity between vertex pairs;
defining a penalty graph G to label specific features of least interest in the sets of training data, wherein G={U, W}, labels that identify unfavorable features that are features not characterisic of the pattern to be recognized are added to the sets of training data in U, W is a dissimilarity matrix, and each element of dissimilarity matrix W measures unfavorable relationships between said vertex pairs;
defining an intrinsic diagonal matrix D as D=[Dij] and Dii=Σj=1nWij;
defining an intrinsic Laplacian matrix L as L=D−W;
defining a penalty diagonal matrix D as D=[ Dij] and Dii=Σj=1n Wij;
defining a penalty Laplacian matrix L as L= D− W;
defining a basis matrix V as Vεd×r, wherein basis matrix V is to hold basis examples of the sets of training data, the basis examples being a reduction of the sets of training data into simplified representations that highlight distinguishing characteristics of the pattern to be recognized;
defining a feature matrix X as Xεr×n, wherein feature matrix X is to hold features values to construct an approximation of U from basis matrix V;
incorporating the label information of intrinsic graph G and penalty graph G into the construction of basis matrix V and features matrix X by defining a measure of the compactness of intrinsic graph G by the weighted sum of squared distances defined as Σi<jnWij∥xi−xj∥2=Tr(XLXT), wherein xi is the i-th column of X and xj is the j-th column of X;
defining a measure of the separability of penalty graph G by the weighted sum of squared distances defined as Σi<jn Wij∥xi−xj∥2=Tr(X LXT), wherein xi is the i-th column of X and xj is the j-th column of X;
defining F(1)(V,X) as an objective of NMF (nonnegative matrix factorization), wherein as F(1)(V,X)=½∥U−VX∥F2;
defining F(2)(X) as an objective of graph embedding, where
F
(
2
)
⁡
(
X
)
=
λ
2
⁢
Tr
⁡
(
QXLX
T
)
Tr
⁡
(
QX
⁢
L
_
⁢
X
T
)
,
λ is a multiplication factor determined by a validation technique, and
Q
=
diag
⁡
(
[

v
1

2
,

v
2

2
,
…
⁢
,

v
R

2
]
T
)
;
defining an approximation of supervised nonnegative factorization, SNMF, as
F
~
⁡
(
V
,
X
)
=
1
2
⁢

U
-
VX

F
2
+
λ
2
⁢
(
α
⁢
⁢
Tr
⁡
(
QXLX
T
)
-
β
⁢
⁢
Tr
⁡
(
QX
⁢
L
_
⁢
X
T
)
+
β
α
)
,
where V=Vt and X=Xt at time t,
α
=
1
Tr
⁡
(
Q
t
⁢
X
t
⁢
L
_
⁢
X
t
T
)
,
and
⁢
⁢
β
=
Tr
⁡
(
Q
t
⁢
X
t
⁢
LX
t
T
)
(
Tr
⁡
(
Q
t
⁢
X
t
⁢
L
_
⁢
X
t
T
)
)
2
;
identifying factorized matrices Xij and Vij by the following iterative multiplicative updates:
X
ij
←
X
ij
⁢
(
V
T
⁢
U
+
λ
⁢
⁢
QX
⁡
(
T
D
-
+
T
W
-
)
)
ij
(
V
T
⁢
VX
+
λ
⁢
⁢
QX
⁡
(
T
D
+
+
T
W
-
)
)
ij
where TD=αD−β D and TW=αW−β W, and
V
ij
←
V
ij
⁢
(
UX
T
+
λ
⁢
⁢
VS
-
)
ij
(
VXX
T
+
λ
⁢
⁢
VS
+
)
ij
where s=αL−β L;
and
classifying the test data according to classifications defined by Xij using a data classifier;
wherein:
the pattern recognition system is a face recognition system and the classifications defined by Xij include a face classification;
each of said set of training data is a distinct training image;
the favorable features labeled in intrinsic graph G identify regions within each distinct training image that are to be focused upon when defining the basis examples;
the unfavorable features labeled in intrinsic graph G identify regions within each distinct training image that are of least interest when defining the basis examples;
and
a received test image is tested for the existence of a face by determining a basis test sample from the received test image, submitting the basis test sample to the using a data classifier, and if the using a data classifier identifies the basis test sample as belonging to the face classification, then deeming the received test image as having a rendition of a face.

275 more elements

A pattern recognition method, comprising:

providing a data processing device to implement the following steps:
accessing multiple sets of training data, each set of training data having at least one of a true example of a pattern to be recognized or a false example of a pattern to be recognized;
arranging said multiple sets of data into a data matrix U in an electronic memory constituting a data store, wherein each set of training data is arranged as a separate column in data matrix U and data matrix U is defined as Uεd×n, where is the set of real numbers and d×n define the dimensions of data matrix U;
defining an intrinsic graph G to label specific features of most interest in the sets of training data, wherein G={U,W}, labels that identify favorable features that are features characterisic of the pattern to be recognized are added to the sets of training data in U, each column of U represents a vertex, W is a similarity matrix and each element of similarity matrix W measures the similarity between vertex pairs;
defining a penalty graph G to label specific features of least interest in the sets of training data, wherein G={U,W}, to label specific features of least interest in the sets of training data, W is a dissimilarity matrix, and each element of dissimilarity matrix W measures unfavorable relationships between said vertex pairs;
defining an intrinsic diagonal matrix D, wherein D=[Dij] and Dii=Σj=1nWij;
defining an intrinsic Laplacian matrix L, wherein L=D−W;
defining a penalty diagonal matrix D, wherein D=[ Dij] and Dii=Σj=1n Wij;
defining a penalty Laplacian matrix L, wherein L= D− W;
defining a basis matrix V, wherein Vεd×r and basis matrix V is to hold basis examples of the sets of training data, the basis examples being a reduction of the sets of training data into simplified representations that highlight distinguishing characteristics of the pattern to be recognized;
incorporating the label information of intrinsic graph G and penalty graph G into the construction of basis matrix V and features matrix X by defining a feature matrix X, where Xεr×n, wherein feature matrix X is to hold features values to construct an approximation of U from basis matrix V;
given a kernel NMF optimization problem of min½∥Uφ−VφX∥F2 wherein vφij≧0 and xij≧0 for ∀i, j, Uφ=[φ(u1), φ(u2), . . . , φ(uN)], Vφ=[φ(v1), (v2), . . . , φ(vR)], and φ:
M+→H+ is a mapping that projects an image u to a Hilbert space H, representing φ(vj) as a linear combination of φ(ui), where φ(vj)=Σi=1NHijφ(ui), and redefining said kernel NMF optimization as ½∥Uφ−UφHX∥F2;
defining favorable relationships among feature vector pairs as:
F
DIS
⁡
(
X
)
=
⁢
∑
i
<
j
N
⁢
⁢
W
ij
⁢
∑
k
=
1
R
⁢
⁢
(
x
ik
-
x
jk
)
2
⁢

(
U
ϕ
⁢
H
)
k

2
=
Tr
⁢
(
Q
ϕ
⁢
XLX
T
)
,
⁢
⁢
where
⁢
Q
ϕ
=
diag
⁡
(
[
(
H
T
⁢
KH
)
11
,
(
H
T
⁢
KH
)
22
,
…
⁢
,
(
H
T
⁢
KH
)
RR
]
T
)
,
⁢
⁢
where
⁢
K
=
⌊
K
ij
⌋
=
⌊
φ
⁡
(
u
i
)
·
φ
⁡
(
u
j
)
⌋
;
defining unfavorable relationships between features vector pairs as:
F
_
DIS
⁡
(
X
)
=
⁢
∑
i
<
j
N
⁢
⁢
W
_
ij
⁢
∑
k
=
1
R
⁢
⁢
(
x
ik
-
x
jk
)
2
⁢

(
U
ϕ
⁢
H
)
k

2
=
Tr
⁢
(
Q
ϕ
⁢
X
⁢
L
_
⁢
X
T
)
;
defining an SNMF (supervised nonnegative matrix factorization) objective function as
F
⁡
(
H
,
X
)
=
1
2
⁢

U
ϕ
-
U
ϕ
⁢
HX

F
2
+
λ
2
⁢
Tr
⁡
(
Q
ϕ
⁢
XLX
T
)
Tr
⁡
(
Q
ϕ
⁢
X
⁢
L
_
⁢
X
T
)
⁢
;
and
populating basis matrix V and feature matrix X by applying the following iteratively multiplicative updates to achieve said SNMF objective function:
X
ij
←
X
ij
⁢
(
H
T
⁢
K
+
λ
⁢
⁢
QX
⁡
(
T
D
-
+
T
W
-
)
)
ij
(
H
T
⁢
KHX
+
λ
⁢
⁢
QX
⁡
(
T
D
+
+
T
W
-
)
)
ij
and
H
ij
←
H
ij
⁢
(
KX
T
+
λ
⁢
⁢
KHS
-
)
ij
(
KHXX
T
+
λ
⁢
⁢
KHS
+
)
ij
;
separating recognizable patterns within the basis examples of basis matrix V into distinct pattern classifications using a data classifier, these pattern classifications of the basis examples being deemed the recognized patterns of the sets of training data;
wherein:
said pattern recognition method is a face detection method;
each of said set of training data is a distinct training image;
the favorable features labeled in intrinsic graph G identify regions within each distinct training image that are to be focused upon when defining the basis examples;
the unfavorable features labeled in intrinsic graph G identify regions within each distinct training image that are of least interest when defining the basis examples;
at least one of said distinct pattern classifications is a face pattern classification;
and
a received test image is tested for the existence of a face by determining a basis test sample from the received test image, submitting the basis test sample to the data classifier, and if the data classifier identifies the basis test sample as belonging to the face pattern classification, then deeming the received test image as having a rendition of a face.

340 more elements

Dependencies are inferred from the claim text.

Facts

Application: 12/854,781Filed 11 Aug 2010
Published: US 2012/0041725 A116 Feb 2012
Granted: 12 Aug 2014
Term ends: Not estimatedThe source records don’t support an estimate.

Classification10 codes

G06V 40/168
Human faces, e.g. facial parts, sketches or expressions: feature extraction; Face representation
G06F 17/16
Complex mathematical operations: matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization
G06F 18/2133
Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods: based on naturality criteria, e.g.…
G06F 18/21375
Based on criteria of topology preservation, e.g. multidimensional scaling or self-organising maps: involving differential geometry, e.g. embedding…

Family

US 2012/0041725 A1Pre-grant publication · published 16 Feb 2012
US 8,805,653 B2This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

patentgrep

Loading patent…

Abstract

A pattern recognition method, comprising:

providing a data processing device to implement the following steps:
accessing multiple sets of training data, each set of training data having at least one of a true example of a pattern to be recognized or a false example of a pattern to be recognized;
arranging said multiple sets of data into a data matrix U in an electronic memory constituting a data store, wherein each set of training data is arranged as a separate column in data matrix U and data matrix U is defined as Uεd×n, where is the set of real numbers and d×n define the dimensions of data matrix U;
defining an intrinsic graph G to label specific features of most interest in the sets of training data, wherein G={U,W}, labels that identify favorable features that are features characteristic of the pattern to be recognized are added to the sets of training data in U, each column of U represents a vertex, W is a similarity matrix and each element of similarity matrix W measures the similarity between vertex pairs;
defining a penalty graph G to label specific features of least interest in the sets of training data, wherein G={U, W}, labels that identify unfavorable features that are features not characterisic of the pattern to be recognized are added to the sets of training data in U, W is a dissimilarity matrix, and each element of dissimilarity matrix W measures unfavorable relationships between said vertex pairs;
defining an intrinsic diagonal matrix D, wherein D=[Dij] and Dii=Σj=1nWij;
defining an intrinsic Laplacian matrix L, wherein L=D−W;
defining a penalty diagonal matrix D, wherein D=[ Dij] and Dii=Σj=1n= Wij;
defining a penalty Laplacian matrix L, wherein L= D− W;
defining a basis matrix V, wherein Vεd×r and basis matrix V is to hold basis examples of the sets of training data, the basis examples being a reduction of the sets of training data into simplified representations that highlight distinguishing characteristics of the pattern to be recognized;
defining a feature matrix X, wherein Xεr×n feature matrix X is to hold features values to construct an approximation of U from basis matrix V;
incorporating the label information of intrinsic graph G and penalty graph G into the construction of basis matrix V and features matrix X by defining a measure of the compactness of intrinsic graph G by the weighted sum of squared distances defined as Σi<jnWij∥xi−xj∥2=Tr(XLXT), wherein xi is the i-th column of X and xj is the j-th column of X;
defining a measure of the separability of penalty graph G by the weighted sum of squared distances defined as Σi<jn Wij∥xi−xj∥2=Tr(X LXT) wherein xi is the i-th column of X and xj is the j-th column of X;
defining F(1)(V,X) as an objective of NMF (nonnegative matrix factorization), F(1)(V,X) being proportional to F(1)(V,X)=½∥U−VX∥F2;
defining F(2)(X) as an objective of graph embedding, F(2)(X) being proportional to ratio
Tr
⁡
(
XLX
T
)
Tr
⁡
(
X
⁢
L
_
⁢
X
T
)
;
deriving an SNMF (supervised nonnegative matrix factorization) objective from a sum of F(1)(V,X) and F(2)(X);
populating basis matrix V and feature matrix X by solving the derived SNMF objective through iterative multiplicative updates;
and
separating recognizable patterns within the basis examples of basis matrix V into distinct pattern classifications using a data classifier, these pattern classifications of the basis examples being deemed the recognized patterns of the sets of training data;
wherein:
said pattern recognition method is a face detection method;
each of said set of training data is a distinct training image;
the favorable features labeled in intrinsic graph G identify regions within each distinct training image that are to be focused upon when defining the basis examples;
the unfavorable features labeled in intrinsic graph G identify regions within each distinct training image that are of least interest when defining the basis examples;
at least one of said distinct pattern classifications is a face pattern classification;
and
a received test image is tested for the existence of a face by determining a basis test sample from the received test image, submitting the basis test sample to the data classifier, and if the data classifier identifies the basis test sample as belonging to the face pattern classification, then deeming the received test image as having a rendition of a face.

42 more elements

Facts

Application

12/854,781Filed 11 Aug 2010

Published

US 2012/0041725 A116 Feb 2012

Granted

12 Aug 2014

Term ends

Not estimatedThe source records don’t support an estimate.

Classification10 codes

G06V 40/168
Human faces, e.g. facial parts, sketches or expressions: feature extraction; Face representation
G06F 17/16
Complex mathematical operations: matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization
G06F 18/2133
Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods: based on naturality criteria, e.g.…
G06F 18/21375
Based on criteria of topology preservation, e.g. multidimensional scaling or self-organising maps: involving differential geometry, e.g. embedding…