2
$\begingroup$

I'm using the MATLAB code released by Eric P. Xing, related to their NIPS 2002 paper (pdf): "Distance metric learning, with application to clustering with side-information. Eric P. Xing, Andrew Y. Ng, Michael I. Jordan and Stuart Russell".

The code is available for download (.tar.gz) at this webpage.

When using the Newton-Rhapson method (Newton.m file), it is supposed to return a diagonal matrix, and when using the projections method (opt_sphere.m file), it is supposed to return a full matrix with entries greater than or equal to zero. Please see the paper for more on this.

However, when I try this on a sample dataset (Iris dataset), sometimes I get a matrix with negative entries when using the latter method. Similarly, with the former method, I sometimes get a matrix with two zero diagonals (that results in the transformed features being collapsed to a point).

Has anyone else experienced this before? Do you know what I am doing wrong?

As an example, consider the following code snippet (I have extracted the matlab code into the directory "code_metric_online"; these pairs of rows have the same labels, hence are similar: 30th and 42nd, 78th and 83rd, 9th and 49th; these pairs of rows have different labels, hence are dissimilar: 23rd and 61st, 96th and 150th, 45th and 80th):

addpath('code_metric_online/');
clear;
load fisheriris;

[N,d] = size(meas);
data = meas;
S = sparse(N, N);
D = sparse(N, N);

%S(9,49) = 1;
S(30,42) = 1;
S(78,83) = 1;

%D(45,80) = 1;
D(23,61) = 1;
D(96,150) = 1;

A = Newton(meas, S, D, 1);
A

%A = opt_sphere(meas, S, D, 100);
%A

transformed_data = data * (A^1/2)';
figure;
scatter(transformed_data(:, 1), transformed_data(:, 2));

The resulting matrix A in the above example will have two diagonal entries equal to zero, resulting in the plot being a single point. Similarly, if you comment out the Newton method and use opt_sphere instead, you will get a matrix A with negative elements.

If however, you add two new constraints (by un-commenting S(9,49) = 1; and D(45,80) = 1;, then the plot will be a straight line.

I cannot understand this strange behavior, while in the paper, it is clearly said that A is greater than or equal to zero.

$\endgroup$
2
$\begingroup$

You mention:

Similarly, if you comment out the Newton method and use opt_sphere instead, you will get a matrix A with negative elements.

I'm not familiar with the referenced article and I've only taken a quick look at it, but it seems like the constraint on $A$ is $A \succcurlyeq 0$. This is used to denote the fact that $A$ is positive-semi definite, which is by all means not the same as saying that $A$ is a positive matrix (in that all its' entries are positive). For example, positive-semi definite matrices can have negative entries (unless they are on the diagonal).

Could this be the source for your confusion?

$\endgroup$
0
$\begingroup$

The reason why you see only a dot in the plot is because the dimensions you're plotting are actually the ones that contain the zeros you mention. The matrix A is 4x4, and the non-zero diagonal entries are in the third and fourth columns. If you use the corresponding columns from the matrix transformed_data you will see the correct data plotted.

Also, as @galoosh33 said, the opt_sphere returns a semi-definite matrix, so non-diagonal negatives are OK. If you would like to plot that out you could use 2 or 3 out of the 4 dimensions, or use PCA to further combine them:

c = [1,0,0;0,1,0;0,0,1];
scatter(transformed_data(:, 3), transformed_data(:, 4), ones(size(transformed_data,1),1)*30, c(id,:));

[~,score] = pca(transformed_data);
scatter3(score(:,1),score(:,2),score(:,3),ones(size(data,1),1)*30, c(id,:));

It is much later than the original post, so I guess the OP found a solution, but I hope this still helps somebody.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.