今日のひとこと

Vectorは良いのか？

気になるので，Vectorを使う場合とプリミティブな配列で処理したときのパフォーマンス影響を確認してみる．たぶん，Vectorで利用される実装はDenseVectorとRandomAccessSparseVectorあたりな気がするので，これらと比較する．DenseVectorは内部的にはプリミティブ配列と同様に全次元数分の容量を確保する(内部的にはdouble配列だし)．RandomAccessSparseVectorは必要な要素だけを確保する(簡単に言うと内部的にはMapみみたいなイメージだと思う)．単純に以下のコードで比較してみた．

public void test_performance() {
int count = 100;
int dim = .../*次元数*/;
int testNum = .../*利用した要素数*/;
testDenseVector(count, dim, testNum);
sleep(5000);
testSparseVector(count, dim, testNum);
sleep(5000);
testArrayVector(count, dim, testNum);
sleep(5000);
testDenseVector(count, dim, testNum);
sleep(5000);
testSparseVector(count, dim, testNum);
sleep(5000);
testArrayVector(count, dim, testNum);
}
private void testArrayVector(int count, int dim, int testNum) {
long time = System.currentTimeMillis();
long oldHeapSize = getHeapSize();
double[][] data = new double[count][];
for (int i = 0; i < count; i++) {
data[i] = new double[dim];
for (int j = 0; j < testNum; j++) {
data[i][j] = j;
}
}
long heapSize = getHeapSize();
System.out.println("array vector: "
+ (System.currentTimeMillis() - time) + "ms, " + heapSize
+ "MB(" + (heapSize - oldHeapSize) + "MB)");
for (int i = 0; i < count; i++) {
for (int j = 0; j < testNum; j++) {
data[i][j] = j;
}
}
}
private void testDenseVector(int count, int dim, int testNum) {
long time = System.currentTimeMillis();
long oldHeapSize = getHeapSize();
DenseVector[] vectors = new DenseVector[count];
for (int i = 0; i < count; i++) {
vectors[i] = new DenseVector(dim);
for (int j = 0; j < testNum; j++) {
vectors[i].setQuick(j, j);
}
}
long heapSize = getHeapSize();
System.out.println("dense vector: "
+ (System.currentTimeMillis() - time) + "ms, " + heapSize
+ "MB(" + (heapSize - oldHeapSize) + "MB)");
for (int i = 0; i < count; i++) {
for (int j = 0; j < testNum; j++) {
vectors[i].setQuick(j, j);
}
}
}
private void testSparseVector(int count, int dim, int testNum) {
long time = System.currentTimeMillis();
long oldHeapSize = getHeapSize();
RandomAccessSparseVector[] vectors = new RandomAccessSparseVector[count];
for (int i = 0; i < count; i++) {
vectors[i] = new RandomAccessSparseVector(dim);
for (int j = 0; j < testNum; j++) {
vectors[i].setQuick(j, j);
}
}
long heapSize = getHeapSize();
System.out.println("sparse vector: "
+ (System.currentTimeMillis() - time) + "ms, " + heapSize
+ "MB(" + (heapSize - oldHeapSize) + "MB)");
for (int i = 0; i < count; i++) {
for (int j = 0; j < testNum; j++) {
vectors[i].setQuick(j, j);
}
}
}
private long getHeapSize() {
final Runtime runtime = Runtime.getRuntime();
return (runtime.totalMemory() - runtime.freeMemory()) / 1000000;
}
private void sleep(long time) {
System.gc();
try {
Thread.sleep(time);
} catch (InterruptedException e) {
}
}

GCとかの都合とかもあってスリープとかもろもろ入れておく．

まず，100,000次元で10,000要素を使った場合は

dense vector: 103ms, 80MB(80MB)
sparse vector: 133ms, 37MB(37MB)
array vector: 92ms, 80MB(80MB)

次に，100,000次元で20,000要素を使った場合は

dense vector: 113ms, 80MB(80MB)
sparse vector: 237ms, 67MB(67MB)
array vector: 99ms, 80MB(80MB)

さらに，要素数を25,000にすると

dense vector: 114ms, 80MB(80MB)
sparse vector: 388ms, 110MB(110MB)
array vector: 108ms, 80MB(80MB)

で最後に100,000要素を利用すると

dense vector: 130ms, 80MB(80MB)
sparse vector: 1469ms, 376MB(376MB)
array vector: 110ms, 80MB(80MB)

という感じだった．

というわけで，メモリ的には，次元数の20%以下の利用で済むのであれば，RandomAccessSparseVectorで，それ以上ならDenseVectorが良いかな(時間的なことを考えると，10%くらいでもよいのかも)．プリミティブ配列とDenseVectorに大きな差はないけど，若干早いような感じかね．プリミティブ配列で処理するかは，10％の速度向上をとるか，利便性をとるかのどちらが必要かを考えて判断するべきかね．

Tasteについて思うこと

ここ数カ月くらい、研究の実験でMahoutのTasteを結構使ってみました。個人的な感想ですが、フレームワークとしては使えるけど、富豪(?)でない人が利用するのは厳しい気がしました。ここでいう富豪とは最新のPCを数十や数百台とか使って問題解決できる人のことを指してます。最新のPCを数台とかで計算するようなときにはTasteの中身の実装は非効率と感じています(富豪でもコストパフォーマンスを気にする人は微妙かもな)。機械学習みたいな、科学技術計算的な問題を解こうとすると、基本は激しいループ処理なのでその中でnew ～とかでインスタンスを作ったり、インスタンスの配列やListやMapなどで何かしだすと終わりません…。MahoutのVectorもベクトルの計算するには便利なのですけど、富豪でないとちょっと厳しい気がしてきています。Javaだと、インスタンスの破棄をGCに期待することになり、メモリは消費されるし、GCスレッドも負荷が高くなるし、とかなりやられました(パラレルGC、CMS、G1とかも試したけど、CMSが一番良かった気がする)。そんなわけで、始めはTasteに乗っかって作っていましたが、最終的にはインターフェースは同じ感じだけど、中身の実装は作りこんでいった感じ(Mahoutが実装したKDDCupDataModelだと10G以上のメモリが必要っぽいけど，実装しなおすと6Gくらいでさくっと扱えるようになったりします)。改善して行った点は、インスタンスの生成やListとかMapの利用とかもできる限りやめて、基本はプリミティブな値やその配列とかでやる感じにしました(Javaっぽくないけど)。そんな感じの改善をしていくことで、数十～数百倍くらいのパフォーマンスが改善できた気がしてます。というわけで、富豪でない私みたいな人用に、プリミティブな配列とかでベクトルや行列の計算ができるようなものを作る必要があるのかな、と考え始めてます…。

混合多項分布

私自身の混合多項分布の理解度はまだいまいちな気もするけど、とりあえず、ここにあったPythonのコードをJavaで書き直してみた。

public class MultinomialMixture {
double[][] dataset;
int num;
int dim;
int mNum;
double[][] c;
double[][] q;
public MultinomialMixture(double[][] dataset, int k) {
this.dataset = dataset;
num = dataset.length;
dim = dataset[0].length;
mNum = k;
q = new double[mNum][dim];
c = new double[num][mNum];
Random random = new Random(1);
for (int i = 0; i < mNum; i++) {
for (int j = 0; j < dim; j++) {
q[i][j] = random.nextDouble();
}
q[i] = normalize(q[i]);
}
}
public void execute(int loop) {
for (int i = 0; i < loop; i++) {
stepE();
stepM();
}
}
double[] normalize(double[] value) {
double[] ret = new double[value.length];
double sum = 0;
for (int i = 0; i < value.length; i++) {
sum += value[i];
}
for (int i = 0; i < value.length; i++) {
ret[i] = value[i] / sum;
}
return ret;
}
double multi(double[] u, double[] x) {
//    return prod([q[w] ** d[w] for w in range(W)])
double value = 1;
for (int i = 0; i < u.length; i++) {
value *= Math.pow(u[i], x[i]);
}
return value;
}
void stepE() {
//	    for n in range(N):
//       C[n] = normalize([multi(D[n], Q[k]) for k in range(K)])
for (int i = 0; i < num; i++) {
double[] dn = dataset[i];
for (int j = 0; j < mNum; j++) {
c[i][j] = multi(q[j], dn);
}
c[i] = normalize(c[i]);
}
}
void stepM() {
//	    for k in range(K):
//	        Q[k] = normalize([sum([C[n][k] * D[n][w] for n in range(N)]) for w in range(W)])
for (int i = 0; i < mNum; i++) {
double[] value = new double[dim];
for (int j = 0; j < dim; j++) {
value[j] = 0;
for (int k = 0; k < num; k++) {
value[j] += c[k][i] * dataset[k][j];
}
}
value = normalize(value);
q[i] = value;
}
}
double logLikelihood() {
//	    L = 0
//	    for n in range(N):
//	        p = [C[n][k] * multinomial(D[n], Q[k]) for k in range(K)]
//	        L += log(sum(p))
double l = 0;
for (int i = 0; i < num; i++) {
double sum = 0;
for (int j = 0; j < mNum; j++) {
sum += c[i][j] * multinomial(dataset[i], q[j]);
}
l += Math.log(sum);
}
return l;
}
double multinomial(double[] d, double[] q) {
//	    return factorial(sum(d)) / prod([factorial(d[w]) for w in range(W)]) * multi(d,q)
double prod = 1;
for (int i = 0; i < dim; i++) {
prod *= factorial(d[i]);
}
return factorial(sum(d)) / prod * multi(q, d);
}
double factorial(double x) {
//	    if x == 0: return 1
//	    return reduce(mul, xrange(1, x+1))
double prod = 1;
for (int i = 1; i < x + 1; i++) {
prod *= i;
}
return prod;
}
double sum(double[] v) {
double sum = 0;
for (int i = 0; i < v.length; i++) {
sum += v[i];
}
return sum;
}
public void print() {
System.out.println("L=" + logLikelihood());
//		c = new double[num][mNum];
StringBuilder buf = new StringBuilder();
buf.append("C=[");
for (int i = 0; i < num; i++) {
buf.append('[');
for (int j = 0; j < mNum; j++) {
buf.append(c[i][j]);
if (j != mNum - 1) {
buf.append(',');
}
}
buf.append(']');
if (i != num - 1) {
buf.append(',');
}
}
buf.append(']');
System.out.println(buf.toString());
//		q = new double[mNum][dim];
buf = new StringBuilder();
buf.append("Q=[");
for (int i = 0; i < mNum; i++) {
buf.append('[');
for (int j = 0; j < dim; j++) {
buf.append(q[i][j]);
if (j != dim - 1) {
buf.append(',');
}
}
buf.append(']');
if (i != mNum - 1) {
buf.append(',');
}
}
buf.append(']');
System.out.println(buf.toString());
}
}

使うときは以下の感じ。

int k = 2;
MultinomialMixture mm = new MultinomialMixture(dataset, k);
mm.execute(10);
mm.print();

かなり勢いで書いたから、細かいことは後で直すとして、Pythonのやつと同じ感じの結果だったからとりあえず、よしとする。