bugGNU Octave - Bugs: bug #62495, [octave forge] (statistics) pdist...

 
 

bug #62495: [octave forge] (statistics) pdist 'cosine' metric - internal expansion causes out of memory error

Submitter:  Nicholas Jankowski <nrjank>
Submitted:  Fri 20 May 2022 07:46:50 PM UTC
   
 
Category:  Octave Package Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Unexpected Error or Warning
Status:  Fixed Assigned to:  None
Originator Name:  Nicholas Jankowski Open/Closed:  * Closed
Release:  * other Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Sun 19 Jun 2022 11:19:30 AM UTC, comment #4: 

Closing as fixed

Nicholas Jankowski <nrjank>
Group Member
Sun 19 Jun 2022 07:29:11 AM UTC, comment #3: 

Updated the cosine metric to be memory efficient according to Michael Leitner's code. Git commit 793b731 pushed at https://github.com/gnu-octave/statistics/commit/793b731296b97fe7d1cf2bfb039dbffcbbc36ab1
Closed.

Andreas Bertsatos <pr0m1th3as>
Fri 20 May 2022 09:38:47 PM UTC, comment #2: 

Yes, there is a more efficient version: replace the cosine block by

w = sqrt (sumsq (X, 1));
y = 1 - ((X'*X)./(w.*w'))(((1:rows(x))'>(1:rows(x)))(:))';

where you wouldn't even need the Xi and Yi, or if you rather want to do it more obviously, use instead

w = sqrt (sumsq (X, 1));
y = 1 - ((X'*X)./(w.*w'))(sub2ind(rows(x)([1 1]),Xi,Yi))';


The point is that "summing the pointwise products of rows" is in effect just matrix multiplication. Admittedly, if you expand it on first sight you have only half as much to compute, because you need only the half of X'*X. But I seem to remember that the octave interpreter actually recognizes such a pattern and uses a more efficient BLAS routine, that's why I didn't write x*X.

Of course, most of the other distances have the same problem. Unfortunately "summing the square or some other function of the pointwise differences of rows" is not a primitive BLAS routine, therefore I do not see how these can be optimized. If the second dimension of x should be large (like in the problem of the OP, and only there memory can become a problem) of course you can just do a loop and sequentially treat the columns of x. But this would need heuristic tests when it is indicated to do it in a loop and lead to much more complicated code.

Michael Leitner <mleitner>
Fri 20 May 2022 07:56:59 PM UTC, comment #1: 

slight correction, the nchoosek line leading to the expansion amounts to nchoosek(1:rows(data'),2), or nchoosek(1:864,2).


Nicholas Jankowski <nrjank>
Group Member
Fri 20 May 2022 07:46:50 PM UTC, original submission:  

following a query over at stackoverflow [1], an attempt to use the 'silhouette' function was resulting in an unexpected "out of memory or dimension too large for Octave's index type" error for inputs that are well within expected memory/index length limits. Examlpe code below.

It turns out 'pdist' is called with the 'cosine' metric, and the vectorization used in that method causes an extreme expansion in an internal variable, causing the error. The test case input is 864x25333, the expected output is 864x1, but internally it attempts to create a 25333x372816 array.

test code:

pkg load statistics
data = rand(864,25333);
idx = kmeans(data,3,'Distance','cosine');
test1 = silhouette(data, idx, 'cosine');

error: out of memory or dimension too large for Octave's index type
error: called from
    pdist at line 164 column 14
    silhouette at line 125 column 16


pdist, lines 163-166 'cosine' block:

```
case "cosine"
        prod = X(:,Xi) .* X(:,Yi);
        weights = sumsq (X(:,Xi), 1) .* sumsq (X(:,Yi), 1);
        y = 1 - sum (prod, 1) ./ sqrt (weights);
```

Xi and Yi are calculated from nchoosek(data, 2), resulting in a 2x372816 array.  Thus X(:,Xi) and X(:,Yi) are each ~75GB if type double).

Testing against Matlab 2022a, the test code runs without issue in a few seconds, and memory use never spikes more than 500MB over base usage. So such an expansion seems to not be absolutely necessary for the algorithm. Would be worth determining if a more memory efficient option is available.

[1] https://stackoverflow.com/questions/72282190/octave-error-out-of-memory-or-dimension-too-large-for-octaves-index-type

Nicholas Jankowski <nrjank>
Group Member

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by pr0m1th3as (Posted a comment)
  • -email is unavailable- added by mleitner (Posted a comment)
  • -email is unavailable- added by nrjank (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 2 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2022-06-19 nrjank StatusConfirmed Fixed
        Open/ClosedOpen Closed

    Back to the top

    Powered by Savane 3.13-4448.
    Corresponding source code