In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.

Q: In this paper we formulate the framework of recovering a hidden orthonormal basis given access to a<lb>certain “Basis Encoding Function”. We describe the class of Basis Encoding Functions (BEF), such that<lb>their local maxima on the unit sphere are in one-to-one correspondence with the basis elements. This<lb>description relies on a certain “hidden convexity” property of these functions. A number of theoretical<lb>and practical problems of recent interest can be interpreted as recovering a hidden basis from potentially<lb>noisy observations. Specifically, we show how our simple and general framework applies to Independent<lb>Component Analysis (ICA), tensor decompositions, spectral clustering and Gaussian mixture learning.<lb>We describe a new algorithm, “gradient iteration”, for provable recovery of the hidden basis. We<lb>provide a complete theoretical analysis of Gradient Iteration both for the exact case as well as for the<lb>case when the observed function is a perturbation of the “true” underlying BEF. In both cases we show<lb>convergence and complexity bounds polynomial in dimension and other relevant parameters, such as<lb>perturbation size. Our perturbation results can be considered as a very general non-linear version of<lb>the classical Davis-Kahan theorem for eigenvectors of perturbations of symmetric matrices. In addition<lb>we show that in the exact case the algorithm converges superlinearly and give conditions relating the<lb>degree of convergence to properties of the Basis Encoding Function. Our algorithm can be viewed as a<lb>generalization of the classical power iteration method for eigenanalysis of symmetric matrices as well as<lb>a generalization of power iterations for tensors. Moreover, the Gradient Iteration algorithm can be easily<lb>and efficiently implemented in practice.

A: Learning a Hidden Basis Through Imperfect Measurements: An Algorithmic Primitive
****
Q: A crucial aspect of a knowledge base population system that extracts new facts from text corpora, is the generation of training data for its relation extractors. In this paper, we present a method that maximizes the effectiveness of newly trained relation extractors at a minimal annotation cost. Manual labeling can be significantly reduced by Distant Supervision, which is a method to construct training data automatically by aligning a large text corpus with an existing knowledge base of known facts. For example, all sentences mentioning both ‘Barack Obama’ and ‘US’ may serve as positive training instances for the relation born in(subject,object). However, distant supervision typically results in a highly noisy training set: many training sentences do not really express the intended relation. We propose to combine distant supervision with minimal manual supervision in a technique called feature labeling, to eliminate noise from the large and noisy initial training set, resulting in a significant increase of precision. We further improve on this approach by introducing the Semantic Label Propagation method, which uses the similarity between low-dimensional representations of candidate training instances, to extend the training set in order to increase recall while maintaining high precision. Our proposed strategy for generating training data is studied and evaluated on an established test collection designed for knowledge base population tasks. The experimental results show that the Semantic Label Propagation strategy leads to substantial performance gains when compared to existing approaches, while requiring an almost negligible manual annotation effort.

A: Knowledge Base Population using Semantic Label Propagation
****
Q: Despite the prevalence of collaborative filtering in recommendation systems, there has been little theoretical development on why and how well it works, especially in the “online” setting, where items are recommended to users over time. We address this theoretical gap by introducing a model for online recommendation systems, cast item recommendation under the model as a learning problem, and analyze the performance of a cosine-similarity collaborative filtering method. In our model, each of n users either likes or dislikes each of m items. We assume there to be k types of users, and all the users of a given type share a common string of probabilities determining the chance of liking each item. At each time step, we recommend an item to each user, where a key distinction from related bandit literature is that once a user consumes an item (e.g., watches a movie), then that item cannot be recommended to the same user again. The goal is to maximize the number of likable items recommended to users over time. Our main result establishes that after nearly log(km) initial learning time steps, a simple collaborative filtering algorithm achieves essentially optimal performance without knowing k. The algorithm has an exploitation step that uses cosine similarity and two types of exploration steps, one to explore the space of items (standard in the literature) and the other to explore similarity between users (novel to this work).

A:
A Latent Source Model for Online Collaborative Filtering
****