52 迷路
お茶を飲み終わると、ソラは気合を入れて、トロワ姫に宣言する。
「では、特異値分解が最良近似を与えることの証明を始めたいと思います」
トロワ姫は、目を輝かせて、分かったのじゃ、と応えた。
ソラは、まず、証明する定理を説明する。
・サイズがm掛けるnで、実数を要素とする行列Aが対象。ただしm、nは正の整数。
・同じサイズで実数を要素とする、ランクがs以下の行列CでAを近似する。ただし、sはr未満の正の整数。rはAのランク。
・近似の良さは、A引くC、の２乗和Jで測る。要素が実数なので、Jは要素の差の２乗を全要素について足したものである。
・評価基準のJを最小にするCは、Aの特異値分解でs番目までの特異値を残したもので与えられる。
・評価基準のJを最小にするCは、必ずこの形に表される。
「さっきの主成分分析の際に述べたのは、sが1の場合です。この定理は、sがr未満の任意の正の整数に対して、同様の性質が成り立つことを主張しています」
「すごい定理なのじゃ。だが、ここでAのランクrが出てくるのはなぜじゃ」
トロワ姫の質問に、ソラは淀みなく答える。
「sがr以上の場合には、近似する行列Cとして、Aそのものを用いることができ、自明な問題になるためです」
トロワ姫は、なるほどのお、と返した。
次に、ソラは証明の段取りを述べる。
「証明は、迷路のように長いので、五つのステップに分けます」
ステップ１：２行列を掛けた形への置き換え
ステップ２：一方の行列Xについて最小化
ステップ３：Aが対角行列の場合に帰着
ステップ４：評価関数の最大化
ステップ５：解の構成
「まず、ステップ１から行きます。ここでの目標は、行列CをX掛ける、Yの転置、という２行列を掛けた形に置き換えることです。ただし、Xのサイズはm掛けるs、Yのサイズはn掛けるs。さらに、Yの転置、掛けるYは単位行列になるという条件が付きます」
ソラの説明に、トロワ姫は首をかしげた。
「置き換えるとは、なんじゃ」
「要するに、変数の置き換えです。定理は、ランクがs以下のすべての行列の中で評価基準Jの最小値を探すものです。ですから、変数を置き換えても、同じ最小化になることを保証する必要があります」
ソラは、そう説明した後、ランクがs以下の任意の行列Cは、あるX、Yに対して、X掛ける、Yの転置、と等しくなること、および、任意のX、Yに対して、X掛ける、Yの転置、はランクがs以下の行列Cになることをそれぞれ以下のように示した。
前半：Cをフルサイズの特異値分解する。ランクがs以下なので、得られた対角行列で非0の要素はs個以下である。この対角行列をs掛けるsのサイズに切り詰める。得られた二つの直交行列の左側s個の縦の列を残し、左側の行列に対角行列を掛けたものをX、右側の行列をYと置けば、X掛ける、Yの転置、はCに等しくなり、Yの転置、掛けるYは単位行列になる。
後半：Xをフルサイズの特異値分解すれば、Cは、直交行列、掛ける、対角行列、掛ける、行列の転置の形に表され、後の行列はその転置を左から掛けると単位行列になる。対角行列で非0の要素はs個以下である。後の行列を直交行列に拡張すれば、Cのランクがs以下であることが導かれる。
「従って、ランクs以下の行列Cでの最小化の代わりとして、X、Yでの最小化を用いることができます」
ソラが、ステップ１の説明を終えると、トロワ姫は、なるほどのお、と相槌を打った。
「次は、ステップ２、一方の行列Xについての最小化です。結果を要約すると、評価基準Jが、(X引く、A掛けるY)の２乗和、引く、(A掛けるY)の２乗和、足す、Aの２乗和に等しいことを利用します。つまり、Xが、A掛けるY、に等しいときに評価基準Jは最小になります」
評価基準Jは、(A引く、X掛ける、Yの転置)という行列の２乗和である。ソラは、この２乗和を横一行ごとに分けて計算し、それをすべての行に対して足し合わせることで、上記の等式を導いた。
等式の具体的な導出手順は、以下の通りである。
・Aの任意の横一行をa、Xの対応する横一行をxと置くと、評価基準Jの該当する横一行の２乗和は、(a引く、x掛ける、Yの転置)の２乗和になる
・上記の行列はサイズが1掛けるnであるので、上式は(a引く、x掛ける、Yの転置)とその転置を掛けたものに等しくなる
・上式を展開して、xについて整理すると、(x引く、a掛けるY)の２乗和、引く、(a掛けるY)の２乗和、足す、aの２乗和になる
・上式をすべての行に渡って足し合わせることで、所望の等式を得る
ソラの説明を受けて、トロワ姫は感心したように声を上げる。
「なるほどのお。Yの転置、掛けるY、が単位行列という条件があるから、xの２乗項の係数からYが消えて、式が簡単になるのか」
ソラは、ご理解の通りです、と返した。
「Xについて最小化した評価基準Jは、Aの２乗和、引くK、に等しくなります。ここで、Kは(A掛けるY)の２乗和です。評価基準Jの最小化と、評価関数Kの最大化は同じことです。そこで、以下のステップでは、評価関数Kを最大化するYを求めます。Yが求まれば、Xは、A掛けるY、で求められます」
ソラは、一息おくと、ステップ３の説明を始める。
「ステップ３に入ります。Aをフルサイズの特異値分解することで、対角行列の場合に帰着させます」
ソラは、Aの特異値分解をU掛けるΣ掛ける、Vの転置と置いた。Uはサイズがm掛けるmの直交行列、Σはサイズがm掛けるnの対角行列、Vはサイズがn掛けるnの直交行列である。Σの対角要素は、大きい順に並べられており、0でないものはr個である。
評価関数Kは、(U掛けるΣ掛ける、Vの転置、掛けるY)の２乗和に等しい。ここで、ソラは、Vの転置、掛けるYをZと置いた。Zのサイズはn掛けるsである。Vは直交行列なので、Yは、V掛けるZ、に等しい。
「Zを使うと、評価関数Kは、(U掛けるΣ掛けるZ)の２乗和になります。Zの転置、掛けるZ、は、Yの転置、掛けるY、に等しいので、単位行列になります。この条件下で、評価関数Kを最大化します」
ソラは、続けて、評価関数Kの２乗和を縦一列ごとに分けて計算し、それをすべての列に渡って足し合わせることで、評価関数Kが(Σ掛けるZ)の２乗和に等しくなることを示した。
「Σは対角行列なので、Aが対角行列の場合に帰着されたことになります。これでステップ３は終わりです」
ソラは、ここまでに示されたことを以下のようにまとめた。
・評価関数Kは、(Σ掛けるZ)の２乗和であり、以下のステップでは、これを最大にするZを求める。Σは、サイズがm掛けるnの対角行列。Zは、サイズがn掛けるsの行列で、Zの転置、掛けるZ、が単位行列。
・Zが求まれば、Yは、V掛けるZ、で求まる。Xは、A掛けるY、すなわちU掛けるΣ掛けるZ。最良近似行列Cは、X掛ける、Yの転置なので、U掛けるΣ掛けるZ掛ける、Zの転置、掛ける、Vの転置、である。
「いよいよステップ４、評価関数の最大化です」
ソラは、そう言った後、Σの対角要素である特異値と、Zの各横一行の２乗和を用いて、評価関数Kを以下の形に表した。
・第1の係数、掛ける、第1の重み、足す、第2の係数、掛ける、第2の重み、足す、……、足す、第nの係数、掛ける、第nの重み
「ここで、第1の係数は、第一特異値の２乗、第1の重みは、Zの一番上の横一行の２乗和です。第2以降も同様です。特異値は大きい順に並べられているので、係数も大きい順に並びます。第(r足す1)以降の係数は0とします」
ソラは、n個の重みが満たすべき三条件を列挙する。
・すべての重みは0以上
その理由：重みはZの横一行の２乗和
・すべての重みは1以下
その理由：Zに縦の列を追加することで、サイズがn掛けるnの直交行列に拡張できる。直交行列の横一行の２乗和は1である。
・重みをすべて足すと、sになる
その理由：Zの縦一列は単位ベクトルで列の数はs個
「そこで、まず重みを変数にして、評価関数Kを最大化します。実際に対応するZが存在することは、ステップ５で確認します」
「つまり、数理計画法の問題と見なそうということじゃな。係数が大きい順に並んでいるから、この問題は簡単じゃ。見ただけで解が分かるぞえ」
トロワ姫が見抜いたように、評価関数Kを最大にする重みは、最初のs個を1、残りを0にするものである。特異値に同じものがなければ、評価関数Kを最大にする重みはこれだけである。
評価関数Kの最大値は、特異値の２乗をs番目まで足し合わせた値になる。Aの２乗和は特異値の２乗を足し合わせたものに等しくなることが示せるので、評価基準Jの最小値は、(s足す1)番目以降の特異値の２乗を足し合わせた値になる。
「最後はステップ５、解の構成です」
ソラは、評価関数Kを最大にする重みから、対応するZを求める手順を説明する。
「Zの上から(s足す1)番目以降の横の行は、すべて0です。従って、Zの上側のサイズがs掛けるsの部分行列を抜き出してQと置くと、Qは正方行列で、Qの転置、掛ける、Q、は単位行列になります。つまり、Qは直交行列です」
ソラは、この逆も成り立つと述べた。
サイズがs掛けるsの任意の直交行列Qに対して、下側に0を詰めて膨らませたサイズがn掛けるsの行列をZと置くと、Zから構成した重みは評価関数Kを最大にする。例えば、単位行列は直交行列であるので、評価関数Kを最大にするZはつねに存在する。
「評価関数Kを最大にするZが求まりましたので、それを使って最良近似行列Cを構成します」
Z掛ける、Zの転置は、最初のs個の対角要素だけが1で、残りの要素が0の対角行列Dになる。最良近似行列Cは、U掛けるΣ掛けるD掛ける、Vの転置。よって、Aの特異値分解でs番目までの特異値を残したもので与えられる。Cのランクはsになる。
トロワ姫は、特異値分解の有用さに触れ、気持ちが高揚しつつも、一抹の違和感を覚えていた。
ソラは、やれやれ終わった、と内心つぶやきながら、証明の終わりを告げようとした。
「以上。証明おわ……」
ここで、トロワ姫は自身の違和感の正体を突き止めた。
「待つのじゃ。特異値に同じものがあるときに、最良近似行列がこの形に限ることが証明されてないぞえ」
トロワ姫の鋭い指摘に、ソラはたじろいだ。
トロワ姫は続けて言う。
「データから作った行列であれば同じ特異値が出現することは、まずないじゃろうが、単位行列のような人為的な行列に対して、定理が使われることもあるのではないかの」
ソラは観念して、答える。
「殿下のご指摘の通りです。特異値分解の闇は、まだ早いかと思い、省いておりました」
「ほう、闇と申すか」
トロワ姫は、興味深そうに応じた。
「闇というと大げさかもしれませんが、特異値分解で特異値に同じものがあるときに起こる面倒な現象のことです。殿下が指摘された単位行列を使って、まず事情を説明いたします」
ソラは、行列Aとして、サイズがn掛けるnの単位行列を取り上げる。
「単位行列の特異値分解では、U、Σ、Vをすべて単位行列に選べます。つまり特異値はすべて1です。sが1、すなわちAをランク1以下の行列Cで近似することを考えます。任意の単位列ベクトルをzとします。すると、最良近似行列Cは、z掛ける、zの転置、で与えられます」
ソラの説明を聞き、トロワ姫は不満顔になった。
「Aの特異値分解と関係ないように見えるがの」
「そうでは、ございません。zに直交する単位ベクトルを追加することで、直交行列Pに拡張できます。ここで、さっきの証明で出てきた対角行列Dを用います。sが1なので、左上要素だけが1で残りが0です。すると、z掛ける、zの転置は、P掛けるD掛ける、Pの転置、に等しいと分かります」
ソラは、続けて、P掛ける、単位行列、掛ける、Pの転置、が単位行列Aに等しいことを指摘した。
「つまり、Aの特異値分解として、UとしてP、VとしてPを用いることができます。この特異値分解において、第一特異値を残したものがさきほどの最良近似行列になります」
トロワ姫は、納得した顔をする。
「つまり、特異値に同じものがあると、特異値分解が一つに決まらないということじゃな。そして、特異値分解ごとに、それぞれ最良近似行列が決まると。特異値を並べる順番が一つに決められないのだから、やむを得ないのではないかの」
ソラは、トロワ姫の理解の早さに感心し、称賛する。
「ご慧眼、感服いたします。Aが一般の行列の場合に話を戻します。第s特異値と等しい特異値が複数存在する場合、対応するU、Vの縦の列に任意の直交行列Pを掛けたものも、Aの特異値分解になります。Pに応じて、最良近似行列Cが決まり、最良近似行列Cは必ずこの形で表されます」
ソラは、以下の二つの行列を使い、Aが一般の場合の定理の主張を詳しく述べる。
・サイズがn掛けるnの直交行列R。ただし、上記のPを掛ける縦の列以外は何もしない。すなわち、単位行列の一部をPで置き換えた行列。
・サイズがm掛けるmの直交行列L。Rと同様、上記のPを掛ける縦の列以外は何もしない。
・このとき、Aのフルサイズの特異値分解で得られるサイズがm掛けるnの対角行列Σに対して、Σ掛けるRは、L掛けるΣ、に等しくなる。
「従って、U掛けるL掛けるΣ掛ける、Rの転置、掛ける、Vの転置、もAの特異値分解になります。このとき、s番目までの特異値を残したものは、U掛けるL掛けるΣ掛けるD掛ける、Rの転置、掛ける、Vの転置、と表せます。最良近似行列Cは、この形に限ります」
定理の主張の説明が終わると、トロワ姫は納得したような顔をした。
「定理の主張は分かったぞえ。あとは、どう示すかじゃな。先の証明で、ステップ４の評価関数の最大化と、ステップ５の解の構成をうまく修正して、どんな最良近似行列Cにも、対応する直交行列Pが存在することを言えばいいのじゃな。なんかできそうな気がするのお」
ソラは、トロワ姫への宿題にすることに決めた。
「では、その証明は宿題ということで。ヒントとして、ボクが考えた証明の概略を紹介いたします」
ソラは、証明の概略を箇条書きにした。
・ステップ４で最大化する重みは、三群に分かれる。先頭g個は1、そのあとw個は足してd、それ以降は0。ただし、gは、s番目の特異値よりも真に大きい特異値の個数。wは、s番目の特異値と等しい特異値の個数。dはs引くg。
・ステップ５において、サイズがs掛けるsの直交行列Qを構成する処理は以下のように修正する。Zを一旦、直交行列に拡張することで、Zの上からg個の横の行がお互いに直交することを示し、横の行をd個追加して直交行列Qに拡張する。
・上記で構成されたQと最大値を与えるZは、上側g個の横の行しか一致しない。Z掛ける、Qの転置、をHと置き、両者の相違点を明確化する。Hはその転置を左から掛けると単位行列になる。Hの横(g足す1)行目から(g足すw)行目を調べて、サイズがw掛けるwの直交行列Pを導出する。
「あとは、最良近似行列Cが、LとRを使ったさきほどの形で表せることを示すだけです。Cのランクはやはりsになります」
ソラが、説明を終えると、トロワ姫は、分かったのじゃ、と応じた。
「では、今度こそ。以上、証明終わり」
ソラは、巨大迷路を脱出したような爽やかな表情で、証明の終わりを告げた。
その日の講義は、これで終了した。
