Computational Limits of ML

Yahoo! has extremely large datasets which are constantly growing. How do you learn from very large datasets? Although there are plenty of methods known for speeding up slow learning algorithms, speeding up fast online learning algorithms is a much harder problem. Another problem is test time computational cost, because learned predictors should be deployable in real-time systems. How do you build effective learning algorithms with very low average or maximum test time computational cost?

Label complexity reduction methods

In many situations there are also sometimes very small amounts of labeled data, because some labels cost money, or because the prediction task to solve is very specific. Despite having very few labels, these tasks might nevertheless be solvable because there is plentiful extra data from other tasks, implying semisupervised, multitask, or other ancillary data incorporation methods can work. What are the limits of multitask learning? Active learning? How do you reuse knowledge bases & ontologies in machine learning?

Nonstationary data

The standard assumption in machine learning is that data sources do not change, but that is often severely untrue at Yahoo!. How do you deal with changing data sources? Adversarial data sources? (How you develop a classifier to combat spam that is robust against spammers affecting features or labels?)

Learning to rank

Ranking problems are pervasive at Yahoo!. How do you create a policy for ranking various types of objects such as webpages, ads, images or news articles? Clicks by user provide valuable relevance feedback. How such an implicit feedback can be best leveraged to improve the ranking function? In order to compare learning to rank algorithms, we will be soon launching a ranking competition; stay tuned!

Exploration

Many learning problems at Yahoo involve user interaction. You can't rewind a user and try a different action, so you only get feedback for the chosen action, violating the idea that you have a complete label. How do you explore and use exploration data in learning with partial feedback? How do you do this in a way which allows use of logged data?

Structured Prediction Models for Information Extraction

Extracting structured data from semi-structured and unstructured web pages is extremely valuable for a number of web applications. Typically, this is accomplished using a judicious combination of structured prediction techniques such as conditional random fields or structural support vector machines. However, practical deployment of these techniques requires extending them to work with various forms of highly limited and noisy supervision (e.g., noisy databases, dictionaries, domain-specific constraints, etc.) and also to make effective use of structural commonalities within websites/webpages. It is also essential to incorporate intelligent data collection/filtering mechanisms into the prediction framework itself to achieve the desired scalability. More details at http://www.labs.yahoo.com/ksc/Information_Extraction.

Back to the Key Scientific Challenges Program