I want to write an optimisation problem then solve it, to get optimised weights to compute a final score using a weighted arithmetic mean.

The problem is as follows. I have an entity (an input vector $V$) that I need to match with none/some/all others entities bases on their scores. Assuming there are $N$ candidate matches for $V$, if the score from $V$ to $C_i$ $i \in \{ 1, N \}$ noted $S_i$, is higher than a certain threshold, it is considered match, otherwise it is not. Consequently, we may end-up that none/some/all candidates are matches.

$S_i$ is a final weighted score that needs to be computed based on three scores, with different weights. The three scores $S_i^1$, $S_i^2$ and $S_i^3$ are outputed by a machine learning platform, each of which represents a certain attribute:

$$S_i = W_i^1 S_i^1 + W_i^2 S_i^2 + W_i^3 S_i^3$$

So I want to model this as an optimisation problem whose decision variables are the weights. I am thinking to set the objective function as $\sum_i S_i$. Nevertheless, I am not convinced by my approach.

My question is are there any state-of-art/classical problems that I could refer to refine my modeling? How could classify this problem? It is not a 100% matching problem as I have only one entry in the left part of the bipartite graph.

Thanks in advance for any feedback.

  • $\begingroup$ Are you assuming that all $N$ candidates should be matches? Maximizing $\sum_i S_i$ would seem to imply that you want high scores for all of them. $\endgroup$ – prubin Mar 30 '20 at 23:53
  • $\begingroup$ The $N$ candidates could be ALL matches, some of them could be a match or none of them is a match. I am feeling maximising the overall score is not very approrpriate; now that I am having further thinking about it, I think maximising "the importance" of attributes scores would be more convenient, in a way that if an attribute score $S^2_i$ is relevant (match/not macth by regard attribute $2$), its weight should be higher, otherwise it is lower. $\endgroup$ – Betty Mar 31 '20 at 10:56
  • $\begingroup$ For scoring systems, I think the "typical" approach is to start with a set of test cases where you know which candidates should be considered matches and which should not. You then select weights to minimize the number of mismatches or maximize the number of correct matches or some other accuracy criterion, then use those weights to find matches for future instances. $\endgroup$ – prubin Mar 31 '20 at 20:21
  • $\begingroup$ that would become then a machine learning problem $\endgroup$ – Betty Apr 2 '20 at 13:56
  • $\begingroup$ I suppose that depends on your definition of "machine learning". Depending on sample size, you could solve the fitting problem via mixed-integer linear programming, which I don't think is traditionally considered a "machine learning" method ... but I may be wrong. $\endgroup$ – prubin Apr 2 '20 at 21:41

Your Answer

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

Browse other questions tagged or ask your own question.