In the first part of the talk I will present recent work on learning latent variable models for content-based image retrieval. To learn a function that predicts the relevance of a database image to an image query all that we need is some form of feedback from users of the retrieval system. For example, we can obtain triplet constraints specifying that relative to some query Q, an image A should be ranked higher than an image B. When such feedback is available ranking SVMs can be used to induce the retrieval function. I will describe an extension of this framework where instead of learning a single relevance function we learn a mixture of relevance functions. Intuitively, given a query we first compute a distribution over "coarse" latent classes and then compute the relevance function for queries of that class. I will present a simple learning algorithm that induces both the latent classes and the parameters of each model. In the second part of the talk I will describe some of my current work on developing efficient learning algorithms for structure prediction with latent variables. These algorithms are based on using an algebraic representation that exploits directly the markovianity of the distribution.