1

私はマトリックスを持っていX(10000, 800)ます。グラム行列 を計算したいのですがK(10000,10000)、ここでK(i,j)= exp(-(X(i,:)-X(j,:))^2).

最初に double for loop を使用しましたが、その後は永遠にハングします。それから私はこれを試しました：

[N d] = size(X);
aa = repmat(X',[1 N]);
bb = repmat(reshape(X',1,[]),[N 1]);
K = reshape((aa-bb).^2, [N*N d]);
K = reshape(sum(D,2),[N N]);

しかし、その後、余分なスペースを大量に使用し、すぐにメモリが不足します。これに効率的なベクトル化された方法はありますか。これは、多くのカーネル svm および画像処理において非常に標準的な中間ステップであるため、何かがあるに違いないと確信しています。

4

2 に答える 2

3

pdist2または pdistを使用します。Matlabのpdist2はただ遅いことに注意してください... Matlabの余弦距離が遅い

コード：

X = rand(100, 3);
K = squareform(pdist(X, 'euclidean'));
K = exp(-K.^2);

これは、 2 つの行列があり、すべての距離を見つけたいと いうより一般的なケースについて書きます。(x-y)^2 = x'x - 2x'y + y'yグラム行列を計算する場合は、差のすべての組み合わせが必要です。

X = rand(100, 3);
Y = rand(50, 3);
A = sum(X .* X, 2);
B = -2 *X * Y';
C = sum(Y .* Y, 2);
K = bsxfun(@plus, A, B);
K = bsxfun(@plus, K, C);
K = exp(-K);

編集：速度比較

コード

% http://stackoverflow.com/questions/13109826/compute-a-gramm-matrix-in-matlab-without-loops/24407122#24407122
function time_gramm()
% I have a matrix X(10000, 800). I want to compute gramm matrix K(10000,10000), where K(i,j)= exp(-(X(i,:)-X(j,:))^2).
X = rand(100, 800);

%% The straight-forward pdist solution.
tic;
K = squareform(pdist(X, 'euclidean'));
K1 = exp(-K .^2);
t1 = toc;
fprintf('pdist took \t%d seconds\n', t1);

%% The vectorized solution
tic;
A = sum(X .* X, 2);
B = -2 * X * X';
K = bsxfun(@plus, A, B);
K = bsxfun(@plus, K, A');
K2 = exp(-K);
t2 = toc;
fprintf('Vectorized solution took \t%d seconds.\n', t2);

%% The not-so-smart triple-loop solution
tic;
N = size(X, 1);
K3 = zeros(N, N);
for i=1:N
    %     fprintf('Running outer loop for i= %d\n', i);
    for j=1:N
        xij = X(i,:) - X(j,:);
        xij = norm(xij, 2);
        xij = xij ^ 2;
        K3(i,j) = -xij;
        %         d = X(i,:) - X(j,:); % Alternative way, twice as fast but still
        %         orders of magnitude slower than the other solutions.
        %         K3(i,j) = exp(-d * d');
    end
end
K3 = exp(K3);
t3 = toc;
fprintf('Triple-nested loop took \t%d seconds\n', t3);
%% Assert results are the same...
assert(all(abs(K1(:) - K2(:)) < 1e-6 ));
assert(all(abs(K1(:) - K3(:)) < 1e-6 ));
end

結果

上記のコードを N=100 で実行しました

pdist took  8.600000e-03 seconds
Vectorized solution took    3.916000e-03 seconds.
Triple-nested loop took     2.699330e-01 seconds

質問の要求されたサイズの 100 番目では、他の回答 ( O(m^2 n)) で提案されているコードのパフォーマンスが 2 桁遅くなることに注意してください。その時までに、マトリックスのサイズとして 100k を挿入しましたが、X待つよりもはるかに長い時間がかかりました。

フルサイズの問題 ( X = rand(10000, 800)) のパフォーマンスは次のとおりです。

pdist took  5.470632e+01 seconds
Vectorized solution took    1.141894e+01 seconds.

コメント

ベクトル化されたソリューションには 11 秒かかり、Matlab の pdist には 55 秒かかり、他のサンプルで提案された手動のソリューションは完了しませんでした。

于 2014-06-25T11:13:26.887 に答える
0

これに簡単な式を使用しないのはなぜですか? 要素K(i, j) = exp( sum_{k=0}^{n} (X(i, k) - X(j, k))^2. つまり、これは と の 2 つの外側ループiとjの内側ループですk。時間の計算量はO(m^2 n)で、m行とn列が にありますX。スペースの複雑さは、答えを計算するためにと行列O(1)以外のスペースを使用しないためです。XK

これを試してみましたが、本当に遅いですか？

于 2012-10-28T15:10:43.053 に答える