US 8,515,879 B2Granted

Supervised nonnegative matrix factorization

AssigneeSeiko Epson Corporation

InventorsSeung-il Huh, Mithun Das Gupta, Jing Xiao

Life of this patent

Estimating the term…

Abstract

Supervised kernel nonnegative matrix factorization generates a descriptive part-based representation of data, based on the concept of kernel nonnegative matrix factorization (kernel NMF) aided by the discriminative concept of graph embedding. An iterative procedure that optimizes suggested formulation based on Pareto optimization is presented. The present formulation removes any dependence on combined optimization schemes.

Claims18

Dependent claims

A data discrimination method for processing data within a data matrix U file, comprising:

(a) providing a data processing device implementing the following step:
(b) accessing a kernel;
(c) accessing said data matrix U from a data store, wherein data matrix U is defined as U ∈d×n, where is the set of real numbers, d×n define the dimensions of data matrix U, and data matrix U is substantially factorable into a basis matrix V and a coefficient matrix X;
(d) defining an intrinsic graph G , wherein G={U,W}, each column of U represents a vertex, W is a similarity matrix, and each element of similarity matrix W is a measure of defined favorable relationships between vertex pairs;
(e) defining a penalty graph G, wherein G={U, W}, W is a dissimilarity matrix, and each element of dissimilarity matrix W is a measure of defined unfavorable relationships between vertex pairs;
(f) defining an intrinsic diagonal matrix D, wherein D =[Dij] and
⁢
D
ii
=
∑
j
=
1
n
⁢
W
ij
;
(g) defining an intrinsic Laplacian matrix L , wherein L =D−W ;
(h) defining a penalty diagonal matrix D, wherein D=[ Dij] and
⁢
D
_
ii
=
∑
j
=
1
n
⁢
W
_
ij
;
(i) defining a penalty Laplacian matrix L, wherein L= D− W;
(j) using said kernel to transform, i.e. kernelize, data matrix U to a different dimensional matrix φ(U) by tranforming each column ui of data matrix U to a different dimensional space according to said kernel, wherein each transformed column ui defines a corresonding column φ(ui) in different dimensional matrix φ(U);
(k) defining a kernelized basis matrix φ(V) corresponding to basis matrix V transformed by said kernel, each column φ(vi) in kernalized basis matrix φ(V) corresonding to a transformed column vi in basis matrix V;
(l) defining F(1)(φV,X)=∥φ(U)−φ(V)X∥F2 as an objective of non-negative matrix factorization, i.e. NMF;
(m) defining a measure of the compactness of intrinsic graph G by the weighted sum of squared distances defined as
∑
i
<
j
n
⁢
W
ij
⁢

x
i
-
x
j

2
=
Tr
⁡
(
XLX
T
)
;
(n) defining a measure of the separability of penalty graph Gby the weighted sum of squared distances defined as
∑
i
<
j
n
⁢
W
_
ij
⁢

x
i
-
x
j

2
=
Tr
⁡
(
X
⁢
L
_
⁢
X
T
)
;
(o) defining
F
(
2
)
⁡
(
X
)
=
Tr
⁡
(
X
⁢
⁢
L
⁢
⁢
X
T
)
Tr
⁡
(
X
⁢
L
_
⁢
X
T
)
as an objective of graph embedding;
(p) defining iterative updates of basis matrix V and coefficient matrix X to solve an optimization problem define by F(1)(φV,X) assuming no graph embedding, said optimization problem having the form
min
V
,
X
⁢

ϕ
⁡
(
U
)
-
ϕ
⁡
(
V
)
⁢
X

F
2
⁢
⁢
s
.
t
.
⁢
V
ik
≥
0
⁢
⁢
and
⁢
⁢
X
kj
≥
0
⁢
∀
i
,
j
,
and
⁢
⁢
k
and said iterative updates having the form Vij←Vij multiplied by (η) and Xij←Xij multiplied by(Tij(1)) , where and η and Tij(1)represent solution formulations for the system with no graph embedding;
(q) defining λ=F(2)(X);
(r) defining
T
ij
(
2
)
=
(
X
⁡
(
L
-
λ
⁢
⁢
L
_
)
-
)
ij
(
X
⁡
(
L
-
λ
⁢
⁢
L
_
)
+
)
ij
;
and
(s) applying the following iterative multiplicative updates until a Pareto optimal is reached
Vij←Vij·(η) and Xij←Xij·h(Tij(1),Tij(2))
where
⁢
⁢
h
⁡
(
T
ij
(
1
)
,
T
ij
(
2
)
)
=
{
min
⁡
(
T
ij
(
1
)
,
T
ij
(
2
)
)
if
⁢
⁢
T
ij
(
1
)
>
1
⁢
⁢
and
⁢
⁢
T
ij
(
2
)
>
1
max
⁡
(
T
ij
(
1
)
,
T
ij
(
2
)
)
if
⁢
⁢
T
ij
(
1
)
<
1
⁢
⁢
and
⁢
⁢
T
ij
(
2
)
<
1
1
otherwise
and wherein:
Vij←Vij·(η)is a first objective;
Xij←Xij·h(Tij(1),Tij(2)) is a second objective;
said Pareto optimal is the iterative status where no further Pareto improvement can be obtained, and a Pareto improvement is defined as an iterative update that improves at least one of said first and second objectives without orsenin the other.

325 more elements

Dependencies are inferred from the claim text.

Facts

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

Classification6 codes

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.…
G06V 10/7715
Processing image or video features in feature spaces; using data integration or data reduction, e.g. principal component analysis [PCA] or…:…
G06V 40/16
Human or animal bodies, e.g. vehicle occupants or pedestrians; Body parts, e.g. hands: human faces, e.g. facial parts, sketches or expressions

Family

US 2012/0041906 A1Pre-grant publication · published 16 Feb 2012
US 8,515,879 B2This patent

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

Timeline

Citations

Open elsewhere

patentgrep

Loading patent…

Abstract

A data discrimination method for processing data within a data matrix U file, comprising:

(a) providing a data processing device implementing the following step:
(b) accessing a kernel;
(c) accessing said data matrix U from a data store, wherein data matrix U is defined as U ∈d×n, where is the set of real numbers, d×n define the dimensions of data matrix U, and data matrix U is substantially factorable into a basis matrix V and a coefficient matrix X;
(d) defining an intrinsic graph G , wherein G={U,W}, each column of U represents a vertex, W is a similarity matrix, and each element of similarity matrix W is a measure of defined favorable relationships between vertex pairs;
(e) defining a penalty graph G, wherein G={U, W}, W is a dissimilarity matrix, and each element of dissimilarity matrix W is a measure of defined unfavorable relationships between vertex pairs;
(f) defining an intrinsic diagonal matrix D, wherein D =[Dij] and
⁢
D
ii
=
∑
j
=
1
n
⁢
W
ij
;
(g) defining an intrinsic Laplacian matrix L , wherein L =D−W ;
(h) defining a penalty diagonal matrix D, wherein D=[ Dij] and
⁢
D
_
ii
=
∑
j
=
1
n
⁢
W
_
ij
;
(i) defining a penalty Laplacian matrix L, wherein L= D− W;
(j) using said kernel to transform, i.e. kernelize, data matrix U to a different dimensional matrix φ(U) by tranforming each column ui of data matrix U to a different dimensional space according to said kernel, wherein each transformed column ui defines a corresonding column φ(ui) in different dimensional matrix φ(U);
(k) defining a kernelized basis matrix φ(V) corresponding to basis matrix V transformed by said kernel, each column φ(vi) in kernalized basis matrix φ(V) corresonding to a transformed column vi in basis matrix V;
(l) defining F(1)(φV,X)=∥φ(U)−φ(V)X∥F2 as an objective of non-negative matrix factorization, i.e. NMF;
(m) defining a measure of the compactness of intrinsic graph G by the weighted sum of squared distances defined as
∑
i
<
j
n
⁢
W
ij
⁢

x
i
-
x
j

2
=
Tr
⁡
(
XLX
T
)
;
(n) defining a measure of the separability of penalty graph Gby the weighted sum of squared distances defined as
∑
i
<
j
n
⁢
W
_
ij
⁢

x
i
-
x
j

2
=
Tr
⁡
(
X
⁢
L
_
⁢
X
T
)
;
(o) defining
F
(
2
)
⁡
(
X
)
=
Tr
⁡
(
X
⁢
⁢
L
⁢
⁢
X
T
)
Tr
⁡
(
X
⁢
L
_
⁢
X
T
)
as an objective of graph embedding;
(p) defining iterative updates of basis matrix V and coefficient matrix X to solve an optimization problem define by F(1)(φV,X) assuming no graph embedding, said optimization problem having the form
min
V
,
X
⁢

ϕ
⁡
(
U
)
-
ϕ
⁡
(
V
)
⁢
X

F
2
⁢
⁢
s
.
t
.
⁢
V
ik
≥
0
⁢
⁢
and
⁢
⁢
X
kj
≥
0
⁢
∀
i
,
j
,
and
⁢
⁢
k
and said iterative updates having the form Vij←Vij multiplied by (η) and Xij←Xij multiplied by(Tij(1)) , where and η and Tij(1)represent solution formulations for the system with no graph embedding;
(q) defining λ=F(2)(X);
(r) defining
T
ij
(
2
)
=
(
X
⁡
(
L
-
λ
⁢
⁢
L
_
)
-
)
ij
(
X
⁡
(
L
-
λ
⁢
⁢
L
_
)
+
)
ij
;
and
(s) applying the following iterative multiplicative updates until a Pareto optimal is reached
Vij←Vij·(η) and Xij←Xij·h(Tij(1),Tij(2))
where
⁢
⁢
h
⁡
(
T
ij
(
1
)
,
T
ij
(
2
)
)
=
{
min
⁡
(
T
ij
(
1
)
,
T
ij
(
2
)
)
if
⁢
⁢
T
ij
(
1
)
>
1
⁢
⁢
and
⁢
⁢
T
ij
(
2
)
>
1
max
⁡
(
T
ij
(
1
)
,
T
ij
(
2
)
)
if
⁢
⁢
T
ij
(
1
)
<
1
⁢
⁢
and
⁢
⁢
T
ij
(
2
)
<
1
1
otherwise
and wherein:
Vij←Vij·(η)is a first objective;
Xij←Xij·h(Tij(1),Tij(2)) is a second objective;
said Pareto optimal is the iterative status where no further Pareto improvement can be obtained, and a Pareto improvement is defined as an iterative update that improves at least one of said first and second objectives without orsenin the other.

325 more elements

Facts

Application

12/854,776Filed 11 Aug 2010

Published

US 2012/0041906 A116 Feb 2012

Granted

20 Aug 2013

Term ends

Not estimatedThe source records don’t support an estimate.

Classification6 codes

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.…
G06V 10/7715
Processing image or video features in feature spaces; using data integration or data reduction, e.g. principal component analysis [PCA] or…:…
G06V 40/16
Human or animal bodies, e.g. vehicle occupants or pedestrians; Body parts, e.g. hands: human faces, e.g. facial parts, sketches or expressions