2
$\begingroup$

In our company, we have a problem where we need to predict which user/vendor is likely to login at a particular time.

We have lots of data about which user logs in at which time. The problem is we have about 30K users, and each user is identified by a code, of say 32 digits.

I understand that simple classification will not work well as there are just too many classes over which the prediction is to be done. Also, I can't really make it as a regression problem as there is no ordering of prediction values.

What can I do in such situation?

Even in ImageNet they had only 1000 classes I guess, so my problem is just severe or I am not aware of the technique to handle such problems.

Please suggest any ways to tackle this problem.

Improve this question
$\endgroup$
13
  • 2
    $\begingroup$ Is there benefit in restating your required goal - what happens after one predicts the time at which a user logs in? A simplistic approach would simply maintain historic logs of when a user logs in, and assign each hour of a day a probability based on his/her history. So you aren't really predicting in the strict sense of using a model. $\endgroup$
    – Arun Jose
    May 25, 2017 at 8:52
  • 1
    $\begingroup$ This is a common problem in training word vectors, where the classification target is the entire vocabulary. You can use hierarchical softmax (1) or negative sampling loss functions (1 2), which is a specialized version of "noise-contrastive estimation". Both techniques were originally conceived as computational improvements, but I think they might also be helpful in the case of having very little data in each class. $\endgroup$
    – shadowtalker
    May 23 at 14:17
  • 1
    $\begingroup$ Essentially duplicate question from the DS site: datascience.stackexchange.com/q/20505/1156. For more, search for negative sampling and hierarchical softmax on both CV and DS.SE. $\endgroup$
    – shadowtalker
    May 23 at 14:21
  • 2
    $\begingroup$ "I understand that simple classification will not work well as there are just too many classes over which the prediction is to be done." How do these classes enter the problem? Are you like considering each minute of the week that a user can login as a separate class? How do you get from predicting login times to a classification problem? $\endgroup$
    – Sextus Empiricus
    May 23 at 14:44
  • 3
    $\begingroup$ @shadowtalker you have added a bounty to this question but the formulation is not very clear. How is the prediction of login times converted into a classification problem and how is that classification problem problematic because of too many classes? $\endgroup$
    – Sextus Empiricus
    May 23 at 15:46

3 Answers 3

Reset to default
3
+500
$\begingroup$

I think it makes sense to look at the concept of Extreme Classification (XC) where we deal with thousands of labels; "The Extreme Classification Repository" has a lot of good examples.

A key difference to "standard classification" is that when working in these extreme (and often multi-label) classification use cases, we are moving towards a "metric at top $k$" approach; we compute our metric of interest using the top $k$ labels predicted (usually ranked by predicted scores). Metrics like precision@k and nDCG@k are the obvious choices and that is because we are needing to have a more "lenient" while still relevant metric - a bit like going from FWER to FDR view in hypothesis testing. Aside from these two, there are also some more specialised metrics like propensity-scored prediction at $k$ which are also relevant and potentially helpful as they can be more easily associated with misclassification costs.

Another point to mention are what are called classifier chains. In this methodology we usually build a series for classifiers to predict the presence or absence of a particular class in addition to the classes predicted by the previous classifiers in the chain. This is usually employed in multi-label classification but it generalises reasonably to XC too, as we partition our output space such that we have a more compact output space to deal with in each "link" of the chain. This plays in the general idea of reducing the output space either by standard dimensionality reduction techniques (e.g. random projections, or word embeddings). Read et al. (2021) Classifier Chains: A Review and Perspectives is a nice read on this. A final point is that sometimes we need specialised database infrastructure to perform XC as scalability in real-time setting might be an issue. (but this is primarily a data engineering point)

Most applications are unsurprisingly associated with online advertising and/or product recommendations; XC problems are often overlapping with multi-label learning so their literature also overlaps. A reasonably well-cited source in this niche area of ML is Parabel: Partitioned Label Trees for Extreme Classification with Application to Dynamic Search Advertising (2018) by Prabhu et al. if you want to read more on this. Lie et al. (2021) The Emerging Trends of Multi-Label Learning seems also good and gives out a very nice hierarchy too.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ This answer deserves the bounty IMO because it points to a collection of literature and provides several techniques and search terms that people can use in their own work, even if their problem does not closely match the OP. I certainly didn't know about the name "Extreme Classification", or that there was a repository of examples, or that there was actually quite a large body of literature on the subject. I've even worked on problems like this myself, but I was always in the dark about prior art. $\endgroup$
    – shadowtalker
    May 30 at 13:44
  • 1
    $\begingroup$ Thank you! I also learned about "Extreme Classification" literature almost by accident; initially, I thought it was a bit gimmicky as none of my standard textbooks I refer to (ESEL, PRML, ProbML, etc.) alluded to it but there are definitely learnings to be had. $\endgroup$
    – usεr11852
    May 30 at 14:29
2
$\begingroup$

If you have many instances of each outcome categroy, then as Nike says, "Just do it." The usual methods will gives predictions just like they always do.

If your concern is that the $32$-digit code has to be predicted, that comes later. Start by making a prediction about which user will log in. Once you have that, you can map it to the $32$-digit code that has meaning for your firm. For instance, use the model to classify the outcome as user $19$, and then use a few more lines of code to map that to $32$-digit ID code $14159265358979323846264338327950$. This could be as simple as a dictionary-type of object.

Improve this answer
$\endgroup$
0
$\begingroup$

You could reformulate the problem into a binary classification. Build a classification model that predicts if a user is going to log in. Then, use the probabilities returned by the model to flag the users who have a high chance of logging in as "positive" cases. The downside is that in such a case the "categories" are not necessarily mutually exclusive (two users can have similar probabilities), but I guess this is not what you needed in the first place.

Improve this answer
$\endgroup$

Your Answer

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

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