1
$\begingroup$

Problem: I would like to build a machine learning model that can predict the best candidate from any given set. What could be a good architecture for such a model?

Given: I have several training examples, each of which consists of:
- a set of candidates.
- a descriptor for the set as a whole.
- a label that tells which one of those candidates is the best in that set.

Details:
- I will have around 10K such sets.
- The number of candidates in every set may be different (may vary roughly from 10 to 100)
- Every set is unordered.
- The descriptor of each set is currently a fixed length one-hot vector. I'm open to add more features to it though.
- Each candidate is represented by a fixed length feature vector. (However in future, the number of features describing each candidate may also differ for every candidate).

What I tried but didn't work:
One approach I tried was a simple MLP that takes one candidate as input and outputs whether or not the candidate is the best. But since this MLP wouldn't know which set the candidate belongs to, it fails in situations where a candidate is the best in one set but the same candidate is not the best in another set.


To get into some more specifics, in my current problem, each candidate is a 2D polygon with a fixed number of line segments. Labelling on the training examples is being done manually to pick the most good looking polygon in a given set of polylines. Each polygon is described by an array of (x,y) coordinates.

One problem I face is that I don't have a natural starting point for a polygon to begin it's array of (x,y) coordinates from. Currently I'm choosing the starting point to be the one with the minimum value of x+y and going counterclockwise from there.

Currently each 2D polygon has the same number of segments. But I would soon need to support polygons with varying number of segments.

In future, I would like to extend this ML model to 3D polyhedrons too, but I don't know how to even build a feature vector to describe for 3D polyhedron yet. I guess that's a problem for another day.

$\endgroup$
8
  • $\begingroup$ Do you have labeled comparisons between polygons across sets? $\endgroup$
    – Jon Nordby
    Apr 7, 2019 at 12:34
  • $\begingroup$ Nope. I do not have any comparisons across sets. $\endgroup$
    – mak
    Apr 7, 2019 at 13:52
  • $\begingroup$ That makes it a bit hard. Key here is to be able to formulate the problem as a standard type of ML problem. You can have a look at the Ranking via Pairwise Comparisons for some inspiration, but I'm not sure if it fit entirely... $\endgroup$
    – Jon Nordby
    Apr 7, 2019 at 14:55
  • $\begingroup$ Thanks a lot for your suggestions! Even I had considered pairwise comparisons and I guess they might work, but the performance would go O(n^2). I also considered RNNs but they are meant for ordered sequences, not for unordered sets. $\endgroup$
    – mak
    Apr 7, 2019 at 15:08
  • $\begingroup$ How many polygons in each set, and how many sets? $\endgroup$
    – Jon Nordby
    Apr 7, 2019 at 15:16

1 Answer 1

1
$\begingroup$

I think it would make more sense to train a model to grade (regression) each candidate, them from candidates of a particular set you can use the best candidate from its "grade".

Also, you should try changing the information from raw cloud of points to more meaningful geometric form irfomation:

  • Number of vertices/segments
  • Segments length mean and variance
  • Skewness
  • Size and direction of major and minor axis
  • Center position
  • Moments of area (first,second,third...)

Update

To apply a regression model you will need to generate grades for the training set and that might be a challenge. For that I will propose a few heuristics to generate this:

  • Since you have about 10k samples, you could assign to every candidate the probability of been the best candidate in any set (for example, if he is the best candidate in 10 sets you can give him a grade $\frac{10}{10,000}$.

    • You could try clustering the samples and assigning a grade to every cluster as the probability of a candidate in that cluster been the best candidate by $\frac{N_{best}}{N_{cluster}}$, where $N_{best}$ is the number of best candidates in any set in that cluster and $N_{cluster}$ is the number of candidates in that cluster

    • You can assign to each best candidate a grade like $1$ if he is best candidate in every set it appears and $1-e^{-\alpha N}$ for every $N$ times it appears in a set without been the best candidate. You will have to tune the decay rate $\alpha$ like any hyperparameter.

$\endgroup$
4
  • $\begingroup$ Thanks @Pedro for your useful answer! However, in order to create a regression model, I would need to train it with grades for each candidate in the training examples. How do you suggest I generate those grades? $\endgroup$
    – mak
    Apr 8, 2019 at 6:23
  • $\begingroup$ True, I proposed a few heuristics to that and updates the answer. Sorry for forgetting that crucial point lol $\endgroup$ Apr 8, 2019 at 12:37
  • $\begingroup$ Could you return to us with a small report of the success of any of my tips? I am a computer vision researcher and geometry-related models are really useful to my field. $\endgroup$ Apr 8, 2019 at 14:59
  • $\begingroup$ Thanks @Pedro, all of your ideas are very useful. In my case though, your first idea (individual probability based) and your third idea ($1-e^{-\alpha N}$) might be a bit difficult to implement because I don't have ready information about which candidates appear in multiple sets. I can search for multiple occurrences, but that too is tricky because two candidates may be very similar but not exactly identical due to numerical noise. Your second idea (probability associated with clusters) seems like it might work for me. I'll try out and let you know. Thank you for your wonderful ideas! $\endgroup$
    – mak
    Apr 9, 2019 at 8:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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