KL展開
をテンプレートにして作成
home
>
サイトマップ
開始行:
RIGHT:寄稿:東條遼平
* KL展開とは [#f0d7c43f]
Karhunen-Loeve展開の略でベクトルの分布を最も良く近似する...
例えば5つの要素を持つベクトルがいくつかある場合に、出来る...
3つや4つの要素のベクトルで表そうといった手法です。圧縮や...
要するに元のデータの特徴を残し、あまり特徴と関係ないであ...
具体的には、画像であれば100×100ピクセルのグレースケールの...
10000個のデータを持っていますが、これは10000次元の1点で表...
実際には10000次元で表すとベクトルは1個になってしまいKL展...
10×10のブロックに分けて100次元のベクトルが100個ある、など...
そして次元を例えば70次元などに落とす事で圧縮することがで...
#ref(klt1.png,nolink)
次元が高いとわかりづらいので2次元を1次元に落とすと考えて...
上のようにX1-X2軸で表される3つの点があるとします。
そのとき例えば、
#ref(klt2.png,nolink)
というY軸を考えるとまったくデータを損なわずに2次元から1次...
そのためこの3つの点はX1-X2座標系で表されているときには大...
しかし、次のように、
#ref(klt3.png,nolink)
このようなY軸を考えると3つの点に違いが無くなってしまいま...
そのため次元を下げる際にはどういう軸を選ぶかが大変重要と...
実際に次元を削除するときに次元を下げてもデータが失われな...
ある基準を設け、その基準に沿ってできるだけ特徴を失わない...
ここでは分散を考え、分散が最大になるように次元を削除して...
平たくいうと散らばり具合です。つまり、他との違いが大きい...
似たり寄ったりの部分は無くなってもいいだろうという観点で...
同じ色のものが沢山あるときに色で区別しようとしないのと同...
#ref(klt4.png,nolink)
上のようにY1、Y2軸を考えたときに、Y1軸の方がY2軸よりも分...
Y1を選んだとしてもY1軸上に点が乗っているわけではないので、
データは損なわれます。しかし、分散は最大になるので、元の...
考えます。
* 理論 [#xf69a65a]
元のデータの次元をd次元とし、次元削除後の次元をd'とします。
d次元ベクトルxをd'次元ベクトルyに変換する為には、
#ref(img69.png,nolink)
とします。ここで行列Aは変換行列と呼ばれますが、行列Aを掛...
単純に5×3の行列と5次元のベクトルを掛けると3次元のベクトル...
行列が転置になっていますが、行列Aは変換後の座標系の正規直...
ベクトルを並べたもので、ベクトルは通常縦に並べて表します。
そのため掛けるときには転置にしないと計算ができません。と...
d=d'として分散を求めてみます。
ここで変換後のyベクトルの平均(平均ベクトル)m'は、変換前の
xベクトルの平均ベクトルmを使い、
#ref(img70.png,nolink)
と表すことができます。これで分散が計算できるようになりま...
ベクトルの分散も普通の分散と同じような式で計算することが...
次のような式になります。
#ref(img71.png,nolink)
各ベクトルから平均を引き、2乗して総和を取ったものを個数で...
通常の分散がベクトルに変わっただけです。ここで、
#ref(img72.png,nolink)
#ref(img73.png,nolink)
を用いて式変形すると、
#ref(img74.png,nolink)
#ref(img75.png,nolink)
#ref(img76.png,nolink)
#ref(img77.png,nolink)
#ref(img78.png,nolink)
#ref(img79.png,nolink)
紛らわしいですが、ここでΣは数学記号でいう総和ではなく、
#ref(img80.png,nolink)
で表される共分散行列といわれるものです。
ここで行列Aが何でもいいのであれば要素を大きくすればいくら...
行列Aは正規直交型のベクトルから成っています。そのため次の...
行列Iは単位行列です。
#ref(img81.png,nolink)
この式を満たした上で分散を最大にするのですが、これは変分...
この式の事を拘束条件といいます。ここで次式を考えます。
#ref(img82.png,nolink)
ここでΛはLagrange未定係数法におけるλに相当するものです。
#ref(img83.png,nolink)
#ref(img84.png,nolink)
より、J(A)を行列Aで偏微分しゼロと置くと、
#ref(img85.png,nolink)
となり、変形して、
#ref(img86.png,nolink)
となり、このことから行列Aは共分散行列を対角化する行列であ...
これを分散の式に代入すると、分散は変換後の次元の対角行列Λ...
つまりここから言えることは、d次元をd'次元に落とす場合、
行列Aをd次元の正方行列だとして共分散行列を対角化し、固有...
d'を残し、それに対応する固有ベクトルのみで作られる行列を...
固有値や固有ベクトルはJacobi法で
求めることができます。また、Jacobi法の固有値のところで書...
固有値が大きい場合、対応する固有ベクトル成分が大きくなり...
対応する固有ベクトル成分が小さくなる、つまり、大きな特徴...
* ソースコード [#v652de8c]
KL展開の関数を作るにあたっていくつか関数を作成しています。
Matrix *MultMatrix(Matrix* matrix1, Matrix* matrix2);
void TransposeMatrix(Matrix* matrix);
static Matrix* AverageVector(Matrix *matrix);
static void SortEigen(Vector *vec, Matrix *mat);
static void ExchangeColumnvector(Matrix *m, int a, int b);
static Matrix* CovarianceMatrix(Matrix *matrix);
MultMatrixは行列の掛け算をし、TransposeMatrixは転置行列を...
AverageVectorは引数の列ベクトルの平均ベクトルを返します。
SortEigenは固有値が入ったvecを降順にソートし、それに対応...
固有ベクトルを固有値に合わせてソートします。ExchangeColum...
行列mのa列とb列の列ベクトルを交換します。CovarianceMatrixは
列ベクトルの共分散行列を返します。
これらの関数についてはソースコードを見てください。
上の関数を使ってKL展開をするKLEncodeと展開後のベクトルを
元の座標系に戻すKLDecodeを作成します。上での説明は長かっ...
実装は意外と簡単です。
neweig = CreateMatrix(newdim, eigenvector->height);
cov = CovarianceMatrix(tempx);
eigennum = Jacobi(cov, eigenvector);
SortEigen(eigennum, eigenvector);
for(i=0; i<neweig->width; i++){
for(j=0; j<neweig->height; j++){
neweig->a[j*neweig->width+i] = eigenvector->...
}
}
TransposeMatrix(neweig);
*x = MultMatrix(neweig, tempx);
TransposeMatrix(neweig);
for(i=0; i<eigennum->size; i++){
if(i >= newdim){
*error += eigennum->v[i];
}
}
先ずneweigにKL展開後の変換行列を入れる領域を確保します。
その後共分散行列を作成、Jacobi法で対角化し、SortEigenで
固有値を降順にソートします。eigenvectorは次元を減らしてい...
for文内で変換後の行列neweigの領域分だけeigenvectorからコ...
変換後の次元分だけの固有ベクトルが残ります。
#ref(img69.png,nolink)
これを計算しあらたなベクトルを得るわけですが、元のベクト...
tempxの中にまとめられているため、行列のまま計算しています。
計算後は変換後のベクトルが列ベクトルとして格納されます。
最後のerrorはKL展開をすることによって失われた分散となりま...
そのため分散がゼロであれば、復元後に元に戻らなくても誤差...
これは次元を削除することで失われた固有値の和となります。
ここで上の式に左から変換行列Aを掛けると元のベクトルに戻す...
void KLDecode(Matrix** x, Matrix* eig)
{
Matrix *temp;
temp = MultMatrix(eig, *x);
FreeMatrix(*x);
*x = temp;
}
ソースコードはこのようになります。
- &ref(main.c);
- &ref(calculation.c);
- &ref(calculation.h);
終了行:
RIGHT:寄稿:東條遼平
* KL展開とは [#f0d7c43f]
Karhunen-Loeve展開の略でベクトルの分布を最も良く近似する...
例えば5つの要素を持つベクトルがいくつかある場合に、出来る...
3つや4つの要素のベクトルで表そうといった手法です。圧縮や...
要するに元のデータの特徴を残し、あまり特徴と関係ないであ...
具体的には、画像であれば100×100ピクセルのグレースケールの...
10000個のデータを持っていますが、これは10000次元の1点で表...
実際には10000次元で表すとベクトルは1個になってしまいKL展...
10×10のブロックに分けて100次元のベクトルが100個ある、など...
そして次元を例えば70次元などに落とす事で圧縮することがで...
#ref(klt1.png,nolink)
次元が高いとわかりづらいので2次元を1次元に落とすと考えて...
上のようにX1-X2軸で表される3つの点があるとします。
そのとき例えば、
#ref(klt2.png,nolink)
というY軸を考えるとまったくデータを損なわずに2次元から1次...
そのためこの3つの点はX1-X2座標系で表されているときには大...
しかし、次のように、
#ref(klt3.png,nolink)
このようなY軸を考えると3つの点に違いが無くなってしまいま...
そのため次元を下げる際にはどういう軸を選ぶかが大変重要と...
実際に次元を削除するときに次元を下げてもデータが失われな...
ある基準を設け、その基準に沿ってできるだけ特徴を失わない...
ここでは分散を考え、分散が最大になるように次元を削除して...
平たくいうと散らばり具合です。つまり、他との違いが大きい...
似たり寄ったりの部分は無くなってもいいだろうという観点で...
同じ色のものが沢山あるときに色で区別しようとしないのと同...
#ref(klt4.png,nolink)
上のようにY1、Y2軸を考えたときに、Y1軸の方がY2軸よりも分...
Y1を選んだとしてもY1軸上に点が乗っているわけではないので、
データは損なわれます。しかし、分散は最大になるので、元の...
考えます。
* 理論 [#xf69a65a]
元のデータの次元をd次元とし、次元削除後の次元をd'とします。
d次元ベクトルxをd'次元ベクトルyに変換する為には、
#ref(img69.png,nolink)
とします。ここで行列Aは変換行列と呼ばれますが、行列Aを掛...
単純に5×3の行列と5次元のベクトルを掛けると3次元のベクトル...
行列が転置になっていますが、行列Aは変換後の座標系の正規直...
ベクトルを並べたもので、ベクトルは通常縦に並べて表します。
そのため掛けるときには転置にしないと計算ができません。と...
d=d'として分散を求めてみます。
ここで変換後のyベクトルの平均(平均ベクトル)m'は、変換前の
xベクトルの平均ベクトルmを使い、
#ref(img70.png,nolink)
と表すことができます。これで分散が計算できるようになりま...
ベクトルの分散も普通の分散と同じような式で計算することが...
次のような式になります。
#ref(img71.png,nolink)
各ベクトルから平均を引き、2乗して総和を取ったものを個数で...
通常の分散がベクトルに変わっただけです。ここで、
#ref(img72.png,nolink)
#ref(img73.png,nolink)
を用いて式変形すると、
#ref(img74.png,nolink)
#ref(img75.png,nolink)
#ref(img76.png,nolink)
#ref(img77.png,nolink)
#ref(img78.png,nolink)
#ref(img79.png,nolink)
紛らわしいですが、ここでΣは数学記号でいう総和ではなく、
#ref(img80.png,nolink)
で表される共分散行列といわれるものです。
ここで行列Aが何でもいいのであれば要素を大きくすればいくら...
行列Aは正規直交型のベクトルから成っています。そのため次の...
行列Iは単位行列です。
#ref(img81.png,nolink)
この式を満たした上で分散を最大にするのですが、これは変分...
この式の事を拘束条件といいます。ここで次式を考えます。
#ref(img82.png,nolink)
ここでΛはLagrange未定係数法におけるλに相当するものです。
#ref(img83.png,nolink)
#ref(img84.png,nolink)
より、J(A)を行列Aで偏微分しゼロと置くと、
#ref(img85.png,nolink)
となり、変形して、
#ref(img86.png,nolink)
となり、このことから行列Aは共分散行列を対角化する行列であ...
これを分散の式に代入すると、分散は変換後の次元の対角行列Λ...
つまりここから言えることは、d次元をd'次元に落とす場合、
行列Aをd次元の正方行列だとして共分散行列を対角化し、固有...
d'を残し、それに対応する固有ベクトルのみで作られる行列を...
固有値や固有ベクトルはJacobi法で
求めることができます。また、Jacobi法の固有値のところで書...
固有値が大きい場合、対応する固有ベクトル成分が大きくなり...
対応する固有ベクトル成分が小さくなる、つまり、大きな特徴...
* ソースコード [#v652de8c]
KL展開の関数を作るにあたっていくつか関数を作成しています。
Matrix *MultMatrix(Matrix* matrix1, Matrix* matrix2);
void TransposeMatrix(Matrix* matrix);
static Matrix* AverageVector(Matrix *matrix);
static void SortEigen(Vector *vec, Matrix *mat);
static void ExchangeColumnvector(Matrix *m, int a, int b);
static Matrix* CovarianceMatrix(Matrix *matrix);
MultMatrixは行列の掛け算をし、TransposeMatrixは転置行列を...
AverageVectorは引数の列ベクトルの平均ベクトルを返します。
SortEigenは固有値が入ったvecを降順にソートし、それに対応...
固有ベクトルを固有値に合わせてソートします。ExchangeColum...
行列mのa列とb列の列ベクトルを交換します。CovarianceMatrixは
列ベクトルの共分散行列を返します。
これらの関数についてはソースコードを見てください。
上の関数を使ってKL展開をするKLEncodeと展開後のベクトルを
元の座標系に戻すKLDecodeを作成します。上での説明は長かっ...
実装は意外と簡単です。
neweig = CreateMatrix(newdim, eigenvector->height);
cov = CovarianceMatrix(tempx);
eigennum = Jacobi(cov, eigenvector);
SortEigen(eigennum, eigenvector);
for(i=0; i<neweig->width; i++){
for(j=0; j<neweig->height; j++){
neweig->a[j*neweig->width+i] = eigenvector->...
}
}
TransposeMatrix(neweig);
*x = MultMatrix(neweig, tempx);
TransposeMatrix(neweig);
for(i=0; i<eigennum->size; i++){
if(i >= newdim){
*error += eigennum->v[i];
}
}
先ずneweigにKL展開後の変換行列を入れる領域を確保します。
その後共分散行列を作成、Jacobi法で対角化し、SortEigenで
固有値を降順にソートします。eigenvectorは次元を減らしてい...
for文内で変換後の行列neweigの領域分だけeigenvectorからコ...
変換後の次元分だけの固有ベクトルが残ります。
#ref(img69.png,nolink)
これを計算しあらたなベクトルを得るわけですが、元のベクト...
tempxの中にまとめられているため、行列のまま計算しています。
計算後は変換後のベクトルが列ベクトルとして格納されます。
最後のerrorはKL展開をすることによって失われた分散となりま...
そのため分散がゼロであれば、復元後に元に戻らなくても誤差...
これは次元を削除することで失われた固有値の和となります。
ここで上の式に左から変換行列Aを掛けると元のベクトルに戻す...
void KLDecode(Matrix** x, Matrix* eig)
{
Matrix *temp;
temp = MultMatrix(eig, *x);
FreeMatrix(*x);
*x = temp;
}
ソースコードはこのようになります。
- &ref(main.c);
- &ref(calculation.c);
- &ref(calculation.h);
ページ名:
home
>
Modified by
物理のかぎプロジェクト
PukiWiki 1.4.5_1
Copyright © 2001-2005
PukiWiki Developers Team
. License is
GPL
.
Based on "PukiWiki" 1.3 by
yu-ji
Powered by PHP 5.3.29HTML convert time to 0.002 sec.