4
$\begingroup$

Something that I often see in papers (example) about large-scale learning is that click-through rate (CTR) problems can have up to a billion of features for each example. In this Google paper the authors mention:

The features used in our system are drawn from a variety of sources, including the query, the text of the ad creative, and various ad-related metadata.

I can imagine a few thousands of features coming from this type of source, I guess through some form of feature hashing.

My question is: how does one get to a billion features? How do companies translate user behavior into features in order to reach that scale of features?

$\endgroup$
2
$\begingroup$

That really is a nice question, although once you're Facebook or Google etc., you have the opposite problem: how to reduce the number of features from many billions, to let's say, a billion or so.

There really are billions of features out there.

Imagine, that in your feature vector you have billions of possible phrases that the user could type in into search engine. Or, that you have billions of web sites a user could visit. Or millions of locations from which a user could log in to the system. Or billions of mail accounts a user could send mails to or receive mails from.

Or, to swich a bit to social networking site-like problem. Imagine that in your feature vector you have billions of users which a particular user could either know or be in some degree of separation from. You can add billions of links that user could post in his SNS feed, or millions of pages a user could 'like' (or do whatever the SNS allows him to do).

Similar problems may be found in many domains from voice and image recognition, to various branches of biology, chemistry etc. I like your question, because it's a good starting point to dive into the problems of dealing with the abundance of features. Good luck in exploring this area!

UPDATE due to your comment:

Using features other than binary is just one step further in imagining things. You could somehow cluster the searches, and count frequencies of searches for a particular cluster.

In a SNS setting you could build a vector of relations between users defined as degree of separation instead of a mere binary feature of being or not being friends.

Imagine logs that global corporations are holding on millions of their users. There's a whole lot of stuff that can be measured in a more detailed way than binary.

Things become even more complicated once we're considering an online setting. In such a case you do not have time for complicated computations and you're often left with binary features since they are cheaper.

And no, I am not saying, that the problem becomes tractable once it's reduced to a magical number of billion features. I am only saying that a billion of features is something you may end up after a lot of effort in reducing the number of dimensions.

$\endgroup$
  • $\begingroup$ So what you mean is that you create binary features for all these billions of words, web sites, friends etc.? And then the problem becomes bringing this down to a billion or so, so that the problem becomes tractable? $\endgroup$ – Bar May 5 '15 at 9:30

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.