On t h e Dimension of A f f i n e A l g e b r a i c V a r i e t y ofNon‑negative M a t r i x F a c t o r i z a t i o n

(1)

静岡理工科大学紀要 41

非負値行列因子分解のアフィン代数多様体としての次元について

On t h e Dimension of A f f i n e A l g e b r a i c V a r i e t y ofNon‑negative M a t r i x F a c t o r i z a t i o n

松田健 *

Takeshi MATSUDA

A b s t r a c t : The pu

叩

o s eo f t h i s p a p e r i s t o i n v e s t i g a t e t h e s o l u t i o n s p a c e o f n o n ‑ n e g a t i v e m a t r i x f a c t o r i z a t i o n . l n t h i s p a p e r ， we w i l l d e a l w i t h s i m p l e c a s e o f n o n ‑ n e g a t i v e m a t r i x f a c t o r i z a t i o n a n d s u r v e y t h e p r o p e r t y o f a n i d e a l i n n o n ‑ n e g a t i v e m a t r i x f a c t o r i z a t i o n .

1.

はじめに

非負値行列因子分解とは，与えられた非負値の要素をもっ行列

T

を.以下のように非負値の要素をもっ

2

つの行列

A ， B

の積に分解することをいう.

T = AB (1)

ここで，

T ， A ， B

はそれぞれ以下のような

nxm

行列，

nxp

行列，

pxm

行列であるとする.

T = { (

^，^¥ ^，t，，

_~ 0

¥ '1，)1

! 1

:9_ISn，I:Sj_l:S

m

~ '1>)1

A =

{a，， ¥ ， a，，

_~ 0

¥ ' 2

，)2

/ 1 : 9 2

^壬ⁿ，

I : S

}z:S

p ' 2

，)2

(~ ~) ~ (~ ~)(~ ~)

~ (~ a~ ~)

しかしながら，このような分解の一意性が成り立たないにも関わらず，非負値行列因子分解は非負値で表現されるデータを扱う，例えば，音響信号処理1)や画像解析のといった分野で応用されており，その有用性が知られている.

非負値因子行列分解を実現するアルゴリズムは

L e e

³)らによって与えられており，このアルゴリズムを改良する多くの研究が行われている.

本研究では，非負値行列因子分解をパラメータ付きの連立多項式の解を求める問題と捉え，それから得られるアフィン代数多様体とその定義イデアルがもっ性質について調べる.本稿の構成は以下の通りである.

2

章では非負値行列因子分解を実現する際にあるアフィン代数多様体を考えていることを示し，非負値行列因子分解を実現する

2014

年

2

月

28

日受理

*

総合情報学部コンヒ。ュータシステム学科

L e e

³)らのアルゴリズムを紹介する.

3

章では単純な場合の非負値行列因子分解を実現するアフィン代数多様体の不変量がもっ性質について調べ，

4

章でまとめを行う.

2.

非負債行列因子分解のアルゴリズム

( 1

)式は，以下の連立多項式を表現するものである.

ん

^(a i

^l^'

ai 2 . ， ^， ^. ^a ⁱ ^p ^， ^b ^l ^j ^， ^b ² ^j ^" ^， ^. bp j) ⁼

^t^υ ^(2 ) ただし，

1 s i

壬

n

，

1

壬

j

豆

m

であり，

んい ⁱ ^l

^，

^ai 2 ， '

^，^.

^aip

^，

^blj' b2j ， "

^，

^bp j)

=

2 ^ai ^k ^b

^対

とおいたら

( 1 壬 i

孟

n

，

1 壬 j

孟

m )

は与えられるデータであるため，非負値因子行列の目標は(

2)

式を満足する

G

バ

i 2 ' ・ " ai p' b1 j ， b2 j ，

…

， bp j ( 1

孟

i

臼，

1

孟

j

豆

m)

を求めることになる.したがって，非負値行列因子分解を求めることは座標の値がすべて非負であるという制約をもっ実アフィン代数多様体

v(~) = ( { a izj2 ^{， ι} ^{)I~= い2} ¹² ^{20， bt313} ^{三 O}}

⁽³⁾

について考えていることに他ならない.本稿ではこれを，

非負値行列因子分解を実現するアフィン代数多様体と呼ぶことにする.非負値行列因子分解を実現するアルゴリズムは，

Lee )

らや他の研究者によって与えられているが，

それらは(3)式で与えられるアフイン代数多様体

v ( λ )

を考えるのではなく，以下のようにして定義される関数を制約条件

(2)

42

Vol.22, 2 0 1 4

α ミ O . b ，， ; : : : 0

'2，}2 '3.)3

のもとで最小にする行列

A ， B

を求めている.したがって，

後者の方法で求めた非負値行列因子分解では，厳密には

( 1

)式は成立しない.

d l = Z Z ( A ‑ t u ) 2 ⁽ ⁴ ⁾

i;1

j; 1

4 剖ら ^γ

^刊^刊^一

¹

^」

⁰

^巾^吋

d ₃

=

去エ乞 i

伴立一均

f ι L ι

し一

1

^I 同

;;~J; j ^‑ f u )

( 5 )

(6 )

以下，

L ee

³)らによる

( 4)

式の最適化に対応する

M u l t i p l i c a t i v e u p d ate r u l e sと

呼ばれるアルゴリズムを紹介する.

[ Mu l t i p l i c a t i v e u p d a t e r u l e s ]

まずO

でな

い初期値

a~2; b

~J) を用雫し

，

以

下の式を

用

いて α

山

b

勿の値を更新する.

2 ; ぃ ; )

y l ) α1 = 32ii l 州

エ ^{t d} ⁺ ⁱ ⁾

b r ) l 1 S 1 4 ) b j o w l

以下，M

u l t i p l i cative u p date r u l e sの計算例

を与える.

M u l t i p l i c a t i v e upd a t e r u l e sはすべて 5 0回繰り返すこ

とにする.

¥︑

I l

l i

1 1

ノ

ハU 1

d

t I

﹁

ム

/

t

I l

l l

‑ ‑

t

¥

一一

¥

I l

l i

‑ ‑

ノ

内J‑司''‑

' h

且'h_︐

'lべ44'

・

4

︐ .

f

i

l l

‑ ‑

1 1

1

¥

一一

Ti ¥

1

1 1

ノ

J

吋J‑司

ノ白

'l

内 ︐L

' o ' h

U

' q h

/

I l l 1 1 1

¥

一一 B

¥

i

l

i l

i ‑

ノ

‑

吋J‑今

︐ 今

月

﹁月町

'l々4

0

f

l

i

l i

‑ ‑

l l

¥

d 一一

とおいて，

T=AB

を満たす行列

A ， B

を求める.

( 1 )

初期値を

4 1 ) α! = ? = 4 1 ) = a ) j ; = l

bl(~) = bl(~) = b) = b) = 1

T

勾

( i : : ; ; : : : ) ( f f ; ロ ! ^J

( 2 )

初期値を

α ) ? ! =

必

) = a f ) =

必)

= 0 . 5 b ? ! = b ) t = b ) ! j = ば ) = 0 . 5

引 ; ; ; : ; ; ) ( : : ; 7 I Z )

(3 )

( : ; ; : : ; ; 1031

( : : ; ; : ; ; : ) = ( l ; ; ^。 ¹ ¹

^{‑ ‑ ハ}

^U

^AUAU ^ハUAU ^ハ

^U

^¥^ノ

¹¹

¹¹¹

¹

¥

I l

l ‑

ノ

‑

1 1 2 1

ハ

υ ハ υ ハ υ

ハυハ

υ

ハ

U

とする.ことのきの結果は以下の通りである.

ベ ⁰ ₀ _. ₀ ^. ₀ ₃ ⁰ ₀ ₀ ^ω ^o _. ^川 ₀ ₀ ₀ ₂ ₎ ₄ _¥ ² ₆

^叩

₉ ₉ _. ₂ ₄ ₁ ₁ ¹ ₁ ⁰ ₁ ₉ ⁰ _. ³ ₃ ₁ ⁾

上述の計算例のように非負値行列因子分解は，その初期値の置き方によってまったく傾向のことなる計算結果が得られることが分かる.これはこの章の冒頭部分で与えた非負値行列因子分解を実現するための連立多項式の解空間に自由度が存在することに起因する.そこで本研究では，

単純な場合の非負値行列因子分解を実現するアフィン代

(3)

静岡理工科大学紀要 43

数多様体

V ( λ )

のイデアルのグレブナー基底 ⁴⁾を調べ，

非負値行列因子分解を実現する連立多項式のもつ性質を明らかにする

3 .

非負値行列因子分解のグレプナー基底

3 . 1

問題設定

非負値行列因子分解の計算は一般的に実数体上で行われるが，実際の計算はコンビュータ上で行うため，以下，

非負有理数を係数とする多項式環

S = Q ， ; ; o [ a

_l_l

， … ， a

_1m

， b

₁₁

， b

₂₁

， … ， b

_ml

， b

_m2

1

について考えることとする

.

T = ( t

_l_l

A =(α11 α 1 2 b

_l_l

b

_l₂

B= b

₂₁

b

₂₂

b

_ml

b

_m2

とし，非負値行列因子分解

T=AB

^{を考える.このとき，}

非負値行列因子分解は以下の連立多項式によって得られ

る.

メ

= L a

1k

b

_k_l‑

t

₁₁

k;1

五

= L a ¹

^ん

ただし，行ヂ

I J A ， B

の成分は非負有理数である.非負値因子行列を実現するアフイン代数多様体

V (

^{ん五 )}^に対応

する定義イデアル

I ( V (

ん五))=

{ f ε S ! f ( p )

=

O ， P ^E V (

ん五)}

については， (ん五)

1 = I ( V (

^五

， J ; ) )

^{となることから，}

一般の定義イデ、アルがもっ性質と同様に以下の結論が得られる.

[命題

1 ]

非負値行列因子分解を実現するアフィン代数多様体において(五

p... ， J n m ) = I ( V (

^五l' ^'ん))は一

般的に成り立たない.

.

これから，非負値行列因子分解を実現する際に必要となる連立多項式の解空間について調べるために，アフィン代数多様体

V (

^{ん五 )}に対応する定義イデアル

I ( V (

^ん五))

について計算するそのために，イデアル(ん五〉のグレブナー基底を考える.

3 . 2

グレプナー基底の定義と主結果

多項式環

S

における単項式を，多重指数を用いて

a a = a~1 1 1 a

~12

; '

，，2 . . . v

ba~" m 2

と表す多重指数

α=(αl α 2 α 3 m )

は非負

整数であるから，単項式全体の集合は

Z Z

^と同^一視する

ことができるただし，

Z

却は非負整数全体の集合であ

るいま，

αJεz ; f t

^{こ対して，} ^ある

i ( 1 豆 i

:S;

3 m )

が存在して，

α 1 =

s^I'..^，^.

_aH =

s^叶^{かつである}

αj‑

月と

なるときに限り

α>β

と定義することにする.このようにして定義される順序のことを多項式順序といい，以下の性質をもつことが知られている.

• z ; ;

の任意の部分集合に最小元が存在する

• a ， s ε Z Z

^{に対して，}

^α >s ， α =s ， α<β

のいずれかが成り立つ

・

^{任意の}

yεz ; ;

^{に対して}

^α>β

^{なら，}

α +y> β +r

が成り立つ

ここで，

α = ( α l ' α 2 '

，

α 3

ふ

^Y=(Y

^l^'

^Y ² ^' ^. ^. ^' ^Y ³ ^r ⁿ ⁾

^とす

ると，

α+y = ( α 1 + Y 1 ' α 2 + Y 2 ' . . ' α 3 m +

(4)

44

Vol.22, 2 0 1 4

するまた，

α = ( o ^， ^O ^， A )

のときは

a a =1

とする本稿では以下のように順序を定義することとする.

a _l _l > a ₁ ₂ > ・・・ > a _1m > b _l _l > b _l ₂ > ・・・ > b _ml > b _m2

多項式

f=LC 〆

において辞書式順序で最大となる単

立

項式を先頭項といい

， LT(f)

で表すことにするまた，

S

のイデ、アバに対して

， LT ( I ) = { L T ( g ) l g ε I }

と定義するこのとき，グレブナー基底は以下のように定義

される.

[定義

1 J

S

のイデアル

I

の生成元の集合

{ h

j>

h 2 ， . . ， ^h _k ^}

^に対して

LT( I ) ⁼ (LT(h

_l)

， LT(h 2 ) ， . . . ， LT(

ん))

が成り立つとき

， {~， h2 " ・ .， h k ^} ^を ^I ^{のグレブナー基底}

とし、う

.

一般的に，イデアル

I

の生成元の集合

H={~ ， h2' ・ .， h k ^} がグレブナ一基底になるとは限ら

ないしかし，

LT( り

と

LT( り

の最小公倍元を

ι ^CM(h; ^， ^h ^j ⁾

^{としたとき，}

S ( h ; ， h j ) =~CM(h;， h勺 LCM(h;， h ^j lh

L T ( h ; ) ， " LT(

り

を計算し，

S ( 久々 )

を

H

で割った余りを

ん

とし，これ

を集合

H

に加え

， i <j

に対して上記の作業を繰り返すことでグレブナー基底が得られることが知られている

.

本研究では，

3 . 1

で与えた非負値行列因子分解を実現するアフィン代数多様体

V ( ^{ん五 )}

^{の性質が，行列}

A

の列の個数(または行列

B

の行の個数

) m

の値から受ける影響を，アフィン代数多様体の不変量である次元を用いて調べ

た.アフィン代数多様体の次元を，定義イデ、アルのアフィンヒルベルト多項式の次数として定義するとき，以下の定理が得られる.

[定理

1 J

T ， A ， B

^{をそれぞれ}

lx2

^型^，

lxm

^型，

mx2

^型の非負

値行列とする.このとき，非負値行列因子分解を実現するアフィン代数多様体の次元は

2m‑2

である.

.

定理

1

の略証を以下に与える五

=S(

五，五)とおくと，

S ( ん五 )ε( ん五

，)

S ( ^{ん五} )ε( ん五 )

となり，多項式の集合

{刀， h ，五 }

はイデアノレ

I

のク守レブナー基底で、あ

ることが分かるまた， ( んん五 )

= I ( V ( ^ん五))

^とな

るから，

V (

^{ん五)の次元が}

2m‑2

^{であることを導くこ}

とができる

.

4 . まとめ

本研究では，非負値行列因子分解を実現するアフィン代数多様体の次元の性質を調べた.これを一般の場合に拡張することや，応用との関連について調べることが今後の課題である.

参考文献

1 )

亀岡弘和，非負値行列因子分解とその音響信号処理応用"，電子情報通信学会技術研究報告: {言学技報

1 1 2

，

347

，

( 2 0 1 2 )

，

p p . 5 3

・

58 2) D . D . Lee a n d H . S . Seung

，

L e a r n i n g t h e p a r t s o f o b j e c t s by n o n ‑ n e g a t i v e m a t r i x f a c t o r i z a t i o n "

，

N a t u r e

，

VoL 4 0 1

，

No. 6755

，

( 1 9 9 9 )

，

p p . 7 8 8 ‑ 7 9 1

3) D . D . Lee a n d H. S . Seung

，

A l g o r i t h m s f o r N o n ‑ n e g a t i v e M a t r i x F a c t o r i z a t i o n "

，

l n NIPS

，

Vo

.l

1 3

，

( 2 0 0 0 )

，

pp . 556

・

562 4) D.Cox

，

J .L

i抗l

e

，

a n d D . O ' S h e

a，

I d e a l s

，

ν ' a r i e t i e s

，

a n d

A l g o r i t h m s "

， An

I n t r o d u c t i o n t o Co mput a t i o n a l

A l g e b r a i c Geometry a n d Commutative Alg

巴

b r a

S p r i n g e r ( 1 9 9 7 )

On t h e Dimension of A f f i n e A l g e b r a i c V a r i e t y ofNon‑negative M a t r i x F a c t o r i z a t i o n