matchpairs function input parameter costUnmatched

How to choose proper value of parameter costUnmatched (matchpairs function) to get requested number of matches.

Especially in a case, when I need maximum number of possible matches min(M,N), where [M,N] = size(Cost), Cost is (M x N) matrix.

Is there at least some clue for a suitable choice of costUnmatched for given cost matrix?

[Adam]

I don't fully understand the first paragraph and have never used this function, but looking at the help and what the function does it seems perfectly natural that M is empty.

You told it to match pairs, but told it the cost of not matching a row or column is 0, so the best cost it can achieve is 0 by not matching anything, hence M, the list of matched pairs is empty and uR and uC, the lists of unmatched rows and columns contains every row and every column. Unless there were a row and column containing identical values any matching would have a cost > 0.

When you gave an actual cost for not matching then in some cases actually finding a match was lower cost than that fixed value.

As for finding a value for costUnmatched, it depends entirely what you want. As with anything that uses thresholds it is often trial and error or based on knowledge of the actual inputs you have, which presumably are not just matrices of random numbers in your actual usage?

But if they were random numbers then you can use probabilities to determine a costUnmatched that would, on average match a certain percentage of pairs, it all depends what you want as a final result.

[Michal]

@Adam ... I rephrase my question to be more clear and simple.

[EmielH]

you could just use a 100 times the max value of cost or something like that.

costUnmatched = 100*max(max(Cost));

That way it's always more benificial to connect a row and column. Where 100 is just arbritatry as long as it's bigger then 1.

[Michal]

I need to find proper definition of costUnmatched without any other free parameters (like "100").

What about?

costUnmatched = max(size(Cost)) * max(Cost,[],'all')

[Michal]

There is another problem with matchpairs function:

function M = matches(costUnmatched)
M = 10; N = 3; P = 2;
rng('default')
s = rand(M,P);
x = rand(N,P);
Cost = pdist2(s,x);
M = matchpairs(Cost,costUnmatched);
end

For different increasing values I had always same matches M ... which is OK !!!!

M = matches(1e3)
M =
     8     1
     3     2
     9     3

M = matches(1e13)
M =
     8     1
     3     2
     9     3

But costUnmatched = 1e20 I have got changed matches, which are wrong!!!

M = matches(1e20)
M =
     8     1
     3     2
     1     3

Some problem with accuracy of matchpairs algorithm???

[Steven Lord]

x = 1e20;
y = x + 10;
y == x % true

I suspect what's happening is that the penalty for leaving something unmatched is so large relatively speaking that it doesn't really matter what gets matched as long as you match something.

It's like in an action movie where the hero is on the edge of a cliff, looking down at a river far below. If a lava flow is coming towards them, prepared to engulf the little spit of land they're on, they're going to jump. The fall and landing in the river almost has to be a better option than being burned alive by lava.

Experiment with unmatched costs where the cost of the matches that switch are around eps of the unmatched cost.

[Adam]

Please don't delete large parts of the question when rephrasing, just improve the phrasing of it if that is what you are doing. It makes comments mostly irrelevant if you then delete most of what they are referring to.

[Michal]

@Adam this is the main reason why I wrote the comment: "@Adam ... I rephrase my question to be more clear and simple." mostly as a apology.

If you are not comfortable with your comment in a new context ... you can delete it.

[Adam]

It's more a case of having wasted my time writing it in the first place if everything it refers to is subsequently deleted. It's not a big issue, but it discourages people from spending their time in the future.

[Michal]

Once again ... sorry!!!

Answer 1

[Michal]

I propose the following costUnmatched input parameter estimation for given Cost matrix:

costUnmatched = max(size(Cost)) * max(Cost,[],'all')

then

M = matchpairs(Cost,costUnmatched)

and the following accuracy check:

CostAssigned = sum(Cost(sub2ind(size(Cost), M(:,1), M(:,2))));
CostUnassigned = costUnmatched*(sum(size(Cost))-2*size(M,1));
TotalCost = CostAssigned + CostUnassigned;
if TotalCost - CostUnassigned == 0
    error('matchpairs: Input parameter costUnmatched is very high  ... possible loss of accuracy');
end

[Michal]

I think the above mentioned accuracy check should be added to MATLAB matchpairs function as a workaround to avoid accuracy problem for extremely high values of costUnmatched input parameter.

[Steven Lord]

You can suggest that as an enhancement request with Technical Support ... but IMO there's some sense in requiring the user to use what they know about their specific problem to choose an unmatched cost. Different problems have different levels of consequence for the unmatched entities.

If you're using matchpairs to choose lab partners for a high school science class where there are an odd number of students (and you will assign the student who was not paired to make a group of three), the unmatched cost is probably not super important. The consequences of not matching aren't that serious.

If you're trying to match patients who need an organ transplant with replacement organs to try to maximize the chances of successful transplants (minimize the chance of rejection) the unmatched cost probably should be very large unless the unmatched patients can survive for long enough for a new set of replacement organs (one of which may better match them and so have a lower chance of rejection) to become available.

[Michal]

So, what do you propose in the case of matchpairs function accuracy loss? I think user should be, at least, warned that something is wrong.

[Steven Lord]

If I'm right about what's going on in this situation, should the second line in the following example warn as well? After all, users might think that "something is wrong" when y turns out to be equal to x.

x = 1e20;
y = x + 1;

If this should issue a warning, every single call to plus would need to check if it needs to issue a warning. How much of a slowdown would you be okay with imposing on every user of the plus function or + operator for that check? It might only be a tiny slowdown, but how many times does the MATLAB code you run use the plus function or + operator? A tiny slowdown occurring thousands or millions of times over the course of running your program can add up to a substantial delay.

>> minutes(1e6*seconds(0.001))
ans =
   16.6667

Lest you think this is a hypothetical concern ... there used to be a function called intwarning. [It started issuing a warning about its removal in release R2010a and started throwing an error in release R2010b.] Looking at its documentation from one of the releases where it existed (I chose release R2009b):

"Caution Enabling the MATLAB:intMathOverflow warning slows down integer arithmetic. It is recommended that you enable this particular warning only when you need to diagnose unusual behavior in your code, and disable it during normal program operation. The other integer warnings listed here do not affect program performance."

Warning can impact performance.

[Michal]

@Steven Lord My motivattion how and why I propose to modify the matchpairs function is based only on the fact, that in a case of

TotalCost - CostUnassigned == 0

the resulting matches M are incorrect. So, from my point view, should be good idea to warn user that (in this specific case, only!!!) is something wrong. That is all.