Keywords: topic models, online learning, latent variable models, unsupervised learning, determinantal point processes, latent Dirichlet allocation

A B S T R A C T

Most of current recommendation systems are based on ratings (i.e. numbers between 0 and 5) and try to suggest a content (movie, restaurant...) to a user. These systems usually allow users to provide a text review for this content in addition to ratings. It is hard to extract useful information from raw text while a rating does not contain much information on the content and the user. In this thesis, we tackle the problem of suggesting personalized readable text to users to help them make a quick decision about a content.

More specifically, we first build a topic model that predicts personalized movie description from text reviews. Our model extracts distinct qualitative (i.e., which convey opinion) and descriptive topics by combining text reviews and movie ratings in a joint probabilistic model. We evaluate our model on an IMDB dataset and illustrate its performance through comparison of topics.

We then study parameter inference in large-scale latent variable models, that include most topic models. We propose a unified treatment of online inference for latent variable models from a non-canonical exponential family, and draw explicit links between several previously proposed frequentist or Bayesian methods. We also propose a novel inference method for the frequentist estimation of parameters, that adapts MCMC methods to online inference of latent variable models with the proper use of local Gibbs sampling. For the specific latent Dirichlet allocation topic model, we provide an extensive set of experiments and comparisons with existing work, where our new approach outperforms all previously proposed methods.

Finally, we propose a new class of determinantal point processes (DPPs) which can be manipulated for inference and parameter learning in potentially sublinear time in the number of items. This class, based on a specific low-rank factorization of the marginal kernel, is particularly suited to a subclass of continuous DPPs and DPPs defined on exponentially many items. We apply this new class to modelling text documents as sampling a DPP of sentences, and propose a conditional maximum likelihood formulation to model topic proportions, which is made possible with no approximation for our class of DPPs. We present an application to document summarization with a DPP on 2 500 items, where the summaries are composed of readable sentences. keywords: topic models, online learning, latent variable models, unsupervised learning, determinantal point processes, latent Dirichlet allocation. i R É S U M É La plupart des systèmes de recommandation actuels se base sur des évaluations sous forme de notes (i.e., chiffre entre 0 et 5) pour conseiller un contenu (film, restaurant...) à un utilisateur. Ce dernier a souvent la possibilité de commenter ce contenu sous forme de texte en plus de l'évaluer. Il est difficile d'extraire de l'information d'un texte brut tandis qu'une simple note contient peu d'information sur le contenu et l'utilisateur. Dans cette thèse, nous tentons de suggérer à l'utilisateur un texte lisible personnalisé pour l'aider à se faire rapidement une opinion à propos d'un contenu.

Plus spécifiquement, nous construisons d'abord un modèle thématique prédisant une description de film personnalisée à partir de commentaires textuels. Notre modèle sépare les thèmes qualitatifs (i.e., véhiculant une opinion) des thèmes descriptifs en combinant des commentaires textuels et des notes sous forme de nombres dans un modèle probabiliste joint. Nous évaluons notre modèle sur une base de données IMDB et illustrons ses performances à travers la comparaison de thèmes.

Nous étudions ensuite l'inférence de paramètres dans des modèles à variables latentes à grande échelle, incluant la plupart des modèles thématiques. Nous proposons un traitement unifié de l'inférence en ligne pour les modèles à variables latentes à partir de familles exponentielles non-canoniques et faisons explicitement apparaître les liens existants entre plusieurs méthodes fréquentistes et Bayesiennes proposées auparavant. Nous proposons aussi une nouvelle méthode d'inférence pour l'estimation fréquentiste des paramètres qui adapte les méthodes MCMC à l'inférence en ligne des modèles à variables latentes en utilisant un échantillonnage de Gibbs local. Pour le modèle thématique d'allocation de Dirichlet latente, nous fournissons une vaste série d'expériences et de comparaisons avec des travaux existants dans laquelle notre nouvelle approche est plus performante que les méthodes proposées auparavant.

Enfin, nous proposons une nouvelle classe de processus ponctuels déterminantaux (PPD) qui peut être manipulée pour l'inférence et l'apprentissage de paramètres en un temps potentiellement sous-linéaire en le nombre d'objets. Cette classe, basée sur une factorisation spécifique de faible rang du noyau marginal, est particulièrement adaptée à une sous-classe de PPD continus et de PPD définis sur un nombre exponentiel d'objets. Nous appliquons cette classe à la modélisation de documents textuels comme échantillons d'un PPD sur les phrases et proposons une formulation du maximum de vraisemblance conditionnel pour modéliser les proportions de thèmes, ce qui est rendu possible sans aucune approximation avec notre classe de PPD. Nous présentons une application à la synthèse de documents avec un PPD sur 2 500 objets, où les résumés sont composés de phrases lisibles.

mots clés: modèles thèmatiques, apprentissage en ligne, modèles à variables latentes, apprentissage non supervisé, processus ponctuels determinantaux, allocation de Dirichlet latente.

iii A C K N O W L E D G E M E N T I am lucky enough to say that many persons have contributed directly or indirectly to this thesis and I would like to thank all of them. I both thank all the persons I have met in a professional context during my PhD and my friends. As I know most people will only read this chapter, I try to be as exhaustive as possible.

I would like to first thank my advisor, Francis Bach. Not only has he been my advisor, but he has also taught me the long process to achieve high quality research. He has always been available, has always taken the time to set a meeting when I needed despite his very busy agenda and to answer my mails despite the dozens (probably more) he receives each day. Especially during my last year, he spent a lot of time guiding me during my job search. He found the right words to reconfort me after paper rejections. He conveyed his appetite for machine learning and research to me from the MVA class until now. I am infinitely grateful to him.

I perfectly remember my first meeting with Christophe Diot, before my master's internship. I would not be writing these words without him. He conveyed his passion for research and his determination to me. Our meetings were hardly restful but always very enriching and I thank Christophe for these challenging exchanges. I also acknowledge support from Technicolor allowing me to make a CIFRE PhD and staying in contact with industry during these three years.

If I were to start all over again, it is not certain I would have met Patrick Pérez. Yet, I had this incredible chance to work and exchange with him during my PhD. I thank Patrick for all the time he devoted to this work between Paris and Rennes.

I thank the reviewers of this manuscript François Caron and Michalis Titsias for their time and their enlightening reports. I also thank the jury members Olivier Cappé and Alexandre D'Aspremont.

I would also like to thank the expermimented and smart INRIA researchers I had the chance to meet during my stay: Sylvain Arlot, Simon Lacoste-Julien, Guillaume Obozinski, Alexandre D'Aspremont, Pierre Gaillard. During the seminars and the always friendly exchanges with them, they always fully dedicate their sharp eye for machine learning to Research and it has been very pleasant to rub shoulders with them.

I acknowledge support from the CIFAR program in Learning in Machines & Brains.

I would like to thank the Dupuy family to have supported me during these years. They've always believed in me even when I have my doubts and when I hold back from talking about it. I also thank the Labonne family for their support, for all the invitations and for their always warm welcome at any sunny/rainy Sunday lunch.

From this line begins a long list of colleagues or friends (or both) I have worked or hanged out with (or both) during my PhD.

I would like to first thank all the office mates who bore my company during these years: Anton, Nastya * , Gül, Pascal, Alexandre, Mathieu. I would also to thank all the PhDs and Postdocs I got to know during my PhD: Nicolas F. * , Vincent, JB, Matthew, Qassem * , Julia, Guilhem * , Damien, Igor * , Antoine * , Aymeric, Nicolas B., Relja, Bala, Federico, Fabian I would also like to thank my friends who took the time to understand and discuss the subject of my PhD, most often around a table full with appetizing food and drinks. I particularly thank Thibaut, Isa, Lucas, Prosper, Océane, Xavier, Marion, Fred, Anne, Louis.

As I always do, I saved the best for last: I would like to thank Claire to team up with me for all these years.

Figure 1 Graphical representation of two probabilistic topic models. White nodes represent hidden variables and colored nodes represent observed variables. . . . . . . . . . . . . . . Figure 2 Graphical representation of LDA. White nodes represent hidden variables and colored nodes represent observed variables. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure 3 Graphical representation of the model LDA-R-C including reduced ratings applied on D documents. White nodes represent hidden variables and colored nodes represent observed variables. The observed rating r d is not reported for the sake of clarity. . . . . . . . . . . . . . . . . . . . . . . Figure 4 Average log-perplexity per word of the presented models on test reviews. . . . . . . . . . . . . . . . . . . . . . . . . . Figure 5 Graphical representation of the model LDA-R-C including reduced ratings applied on D documents. White nodes represent hidden variables and colored nodes represent observed variables. The observed rating r d is not reported for the sake of clarity. . . . . . . . . . . . . . . . . . . . . . . Figure 6 Perplexity on different test sets as a function of K, the number of topics inferred. Best seen in color. . . . . . . . . Figure 7 OLDA. Perplexity on different test sets as a function of K for OLDA with P = 10 (red) and P = 100 (black) internal updates. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure 8 Dataset: IMDB. Evidence Lower BOund (ELBO) computed on test sets (20 internal iterations and 1 pass over the dataset). Left: ELBO through iterations with K = 128. Right: ELBO as a function of the number of topics K. . . . Figure 9 Perplexity through iterations on different test sets with the presented methods. Best seen in color. . . . . . . . . . . . . Figure 10 Perplexity through iterations on different test sets with G-OEM and VarGibbs applied to both LDA and HDP. Best seen in color. . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure 11 G-OEM. Perplexity on different test sets as a function of the number of topics K for regular EM and boosted EM (++). We observe that for almost all datasets, there is no significant improvement when boosting the inference. Our interpretation is that each Gibbs sample is noisy and does not provide a stable boost. Best seen in color. . . . . . . . .

V-OEM. Perplexity on different test sets as a function of the number of topics K for regular EM and boosted EM (++). We observe that boosting inference improves significantly the results on all the datasets excepted on Wikipedia where V-OEM and V-OEM++ have similar performances. The variational estimation of the posterior is finer and finer through iterations. When updating the parameters at each iteration of the posterior estimation, the inference is indeed boosted. Best seen in color. . . . . . . . . . . . . . . . . . . . Figure 13 Dataset: synthetic. Perplexity on different test sets as a function of the exponent κ-the corresponding stepsize is ρ i = 1 i κ -for G-OEM with averaging (left) and without averaging (right). The number of topics inferred K goes from 5 (the lightest) to 20 (the darkest). Best seen in color. Figure 14 Evolution of perplexity on different test sets as a function of the number of documents analyzed. For OLDA, we compare the performance with different step-sizes ρ t = τ/t κ for different values of τ, κ. Solid line: κ = 1/2; Dashed line: κ = 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure 15 Evolution of perplexity on different test sets as a function of the number of documents analyzed, with error bars.

For OLDA, we compare the performance with different stepsizes ρ t = τ/t κ for different values of τ, κ. Solid line: κ = 1/2; Dashed line: κ = 1. . . . . . . . . . . . . . . . . . . . . Figure 16 Dataset: IMDB. Perplexity on different test sets as a function of the exponent κ-the corresponding stepsize is ρ i = 1 i κ -for G-OEM with averaging (left) and without averaging (right). The number of topics inferred K goes from 8 (the lightest) to 128 (the darkest). Best seen in color. . . . . . . . Figure 17 Evidence Lower BOund (ELBO) computed on different test sets. Top: ELBO through iterations, with 4 passes over each dataset and 200 internal iterations. Bottom: ELBO as a function of the number of topics K, with 20 internal iterations and 1 pass over each dataset. Best seen in color. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure 18 Dataset: Synthetic, K = 10. Perplexity on different test sets for different types of updates for α; for boosted methods, we use the same inference for α for local and global updates. NO: α is fixed and set to α true that generated the data; FP: fixed point iteration; Gam: gamma prior on α [START_REF] Sato | Deterministic single-pass algorithm for LDA[END_REF]. Best seen in color. . . . . . . . . . . . . . . . . . Figure 19 Perplexity on different test sets as a function of K, the number of topics inferred. Same as Figure 6, but with error bars. Best seen in colors. . . . . . . . . . . . . . . . . .

Perplexity through iterations on different test sets with the presented methods. Same as Figure 9, but with error bars. Best seen in colors. . . . . . . . . . . . . . . . . . . . . . . . Figure 21 Perplexity through iterations on different test sets with G-OEM and VarGibbs applied to both LDA and HDP. Best seen in color. . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure 22 Comparison of points drawn from a DPP (left) independently from uniform distribution (right). . . . . . . . . . . . Figure 23 Continuous set [0, 1] 2 . Distance (L * -L) in log-likelihood. Figure 24 Performance for ground set X = {1, . . . , V} as a function of r. (a,b) Same θ for all the observations; (c) A different θ for each observation. . . . . . . . . . . . . . . . . . . . . . . Figure 25 Performance for ground set X = {0, 1} V as a function of r with a different θ for each observation. . . . . . . . . . . . Figure 26 Comparison of K * and K t . . . . . . . . . . . . . . . . . . . . Figure 27 Picard iteration [START_REF] Mariet | Fixed-point algorithms for learning determinantal point processes[END_REF]. Evolution of the objective function (train log-likelihood) as a function of the iterations. . . . . . . . . . . . . . . . . . . . . . . . . . . . Figure 28 Performance for ground set X = {0, 1} V as a function of r. 2 Positive (left column) and negative (right column) topic inferred with LDA-R and LDA-R-C, K = 32 topics. . . . . . . Table 3 8 topics extracted with LDA-R-C, SLDA and HFT, K = 100 and the associated score for SLDA (see [START_REF] Mcauliffe | Supervised topic models[END_REF] for details). . . . . . . . . . . . . . . . . . . . . . . . . Table 4 Comparison of existing methods for LDA. . . . . . . . . . . 9 Examples of reviews with extracted summaries (of size l = 5 sentences) colored in blue. . . . . . . . . . . . . . . . . Table 10 Four embeddings (columns of U) inferred with r = 10 on restaurant reviews dataset. . . . . . . . . . . . . . . . . . . . Table 11 Ten examples of cosine similarity between words (i.e., between rows of U) with r = 10 on restaurant reviews dataset.

xi

1 I N T R O D U C T I O N
The amount of text and the number of documents available on the Internet have recently skyrocketed. The types and uses of documents are very diverse. For instance, reviews of products you may find in recommender systems (e.g., Yelp1 , Amazon2 , IMDB3 ) convey an opinion and are crowd-sourced. On the other hand, newspapers or scientific papers are neutral and written by professionals. We identify other sources of text. Websites like Quora4 or Stackoverflow5 are used as questions and answers (Q & A) platforms where users expose questions or issues they are trying to solve (e.g., math problems) while other users propose possible solutions. Search engines represent another source of text. The user makes a request-usually formulated with text-and the aim of a search engine is to suggest the most relevant content(s) to this request. The recent emergence of personal assitants (e.g., Siri6 , "Ok Google"7 , Alexa8 ) gives us a glimpse of new sources of text. These devices turn vocal commands into text requests as inputs for search engines.

A common problem for these applications is to process a huge amount of text (potentially millions or billions of documents or requests). In particular, the extraction of useful information for a given task is proving to be difficult. Note that the definition of usefulness clearly depends on the application. For recommender systems, the user intends to choose a content from a list as quickly as possible. Useful reviews could be those which help users to make a quick opinion about a content. For search engines, computing a distance between any text request and any available content would be useful. In practice, this distance is learned from examples of requests and enables the engine to suggest efficiently the closest content to the user's query.

In this context, Technicolor 9 is a worldwide leader in the media and entertainment sector. The company is specialized in movie creation, production and distribution. It delivers solutions for content management (such as creation, imaging, finishing, preparation) and offers a wide range of services for providing digital entertainment (such as movies) at home through Pay-TV operators and network service providers. Consequently, the motivations for this work were to look for new methods including text to recommend movies for users at home.

In this thesis we focus on services including crowd-sourced reviews such as Yelp, IMDB, the Fork10 , Amazon etc. For this type of service, the main issue is to help users to assess contents (restaurants, movies, products) as fast as possible. While many recommender systems are based on rating prediction [START_REF] Ricci | Introduction to recommender systems handbook[END_REF], the solution of most commercial services to this issue is to reduce the quantity of information (reviews, ratings) absorbed by the user before making a decision. We can identify various strategies of commercial services to implement this solution. While all the services propose the "Sort by" feature for reviews, they also have an additional specific feature on top of that when browsing a particular content:

• On Yelp, selected sentences are displayed based on key-words they contain.

The key-words are highlighted and correspond to specific aspects (served dishes or ingredients, location, quality of service, etc.) of the restaurant.

The platform also allows the user to characterize any existing review as useful, funny or cool. An user can then quickly assess the "quality" of a review before reading it, based on the number of useful, funny or cool already assigned to this review.

• On IMDB, the useful feature is also implemented, but through a yes or no question: Was the above review useful to you?. The reviews can be ranked in the "Sort by" feature by computing the proportion of useful assignments for each review (i.e., the score of a review is the number of "yes" answers divided by the total number of answers for this review; the reviews with maximal scores will be first displayed).

• On Amazon, the Top customer reviews (reviews with the highest rating), Top critical reviews (reviews with the lowest rating) and the Most recent customer reviews are all displayed on the first page of the product and it is easy to access to the reviews with a given rating. The useful feature is also implemented-as in Yelp-to quickly assess the quality of a review.

• On the Fork, the platform allows the user to assess a given restaurant with a global rating and several "sub-ratings" to evaluate the different aspects of the restaurants (food, service, setting, value for price among others). The user can also specify the occasion for visiting the restaurant (on your own, with friends, with family, romantic or business). As a result, the average rating of each aspect is displayed on the homepage of a given restaurant so the user has a quick overview of the aspects for this restaurant. For more details on restaurant, the user can also filter the reviews by occasion.

We remark that in any case, the selected reviews or features displayed are not personalized (i.e., do not depend on the user browsing the website) and the user usually needs to manually select and parse the particular reviews she needs to read to make her final opinion. Even if the selection process is greatly simplified by the different platforms, the effort made by the user may still be significant. Given these commercial solutions, our goal is to automate and personalized the suggestions to the users, based on the history of reviews and ratings of many different users. More precisely, the ultimate goal of this work is to build a model that would automatically suggest a personalized list of contents to the user together with a (short) personalized readable text attached to each content describing the (as accurate as possible) opinion of the user on this content. In this thesis, we build a line of work towards this ultimate goal, taking advantage of substantial existing work on information retrieval.

introduction to information retrieval

The term "information retrieval" (IR) was first used by [START_REF] Mooers | The theory of digital handling of non-numerical information and its implications to machine economics[END_REF]. It gathers all the techniques to extract information from a large corpus of text documents. The retrieved information can take the form of meta-data, latent representation (as in topic models), documents or other types of contents (as in search engines). The applications derived from IR are numerous [START_REF] Aggarwal | Mining text data[END_REF]. For instance, IR covers text classification [START_REF] Nigam | Using maximum entropy for text classification[END_REF][START_REF] Rennie | Improving multi-class text classification with naive Bayes[END_REF], document clustering [START_REF] Pereira | Distributional clustering of English words[END_REF] or semantic features extraction [START_REF] Deerwester | Indexing by latent semantic analysis[END_REF][START_REF] Dumais | Latent semantic indexing (LSI)[END_REF], Hofmann, 1999b,a]. Given our initial objective of text recommendation to users, we focus on semantic features extraction-also known as topic models. This particular field of IR covers techniques able to identify and gather words that have similar meanings from a corpus of documents. In this section, we present the document representation mostly used in topic models and the first techniques to extract semantic features from text.

Bag-of-words representation of document

The bag-of-words representation is the most widely used representation of documents and was first introduced by [START_REF] Harris | Distributional structure[END_REF]. Given a corpus of D documents C = {X 1 , . . . , X D }, we denote V the size of the vocabulary, i.e., the number of different words used in the corpus. In the bag-of-words representation, the document i of C is represented as a vector X i ∈ R V , with:

∀v ∈ 1, V , (X i ) v = n i v > 0 if word v occurs in the i-th document of C, 0 otherwise.
In this representation, n i v represents the "score" of word v in document i. A first natural approach consists in setting n i v to the frequency of word v in document i, but other more evolved scores are used in practice, such as term frequencyinverse document frequency (TF-IDF) [START_REF] Hiemstra | A probabilistic justification for using tf×idf term weighting in information retrieval[END_REF]. In this representation, neither the order of words nor the structure of the documents (e.g., sentences, punctuation, etc.) are taken into consideration. The co-occurrences of words are the only structure represented with bag-of-words, which is often enough information to extract semantics, i.e., to gather words with similar (semantic) meaning.

It is possible to model documents with more complex representations but a lot of technical obstacles arise from these representations. A 2-gram is defined as a pair of consecutive words in a larger sequence of words (i.e., a sentence or a document). In a 2-gram representation, we consider all the single words and pairs of consecutive words (i.e., the sequences of 1 or 2 consecutive words) that occur in corpus C. If we denote M the number of such sequences in corpus C, the associated representation of document i is a vector Xi ∈ R M with ( Xi ) m = n i m > 0 if the sequence m occurs in document i and 0 otherwise, with a similar definition of n i m than n i v in bag-of-words. This representation is more complete because it models all the possible pairs of words occurring in corpus C in addition to single words, but it is very complicated to manipulate in practice as M V. Another con of this representation is that even if M is large, only a small number of sequences actually conveys semantics. For instance, if we consider of corpus of long documents (e.g., newspapers with hundreds of words per documents), among the different pairs of consecutive words (i.e., 2-grams) in the corpus, only a very small portion appears more than once and among the pairs appearing more than once in the corpus, only a very few of them actually convey semantics. As a result, in a 2-gram representation, the signal to noise ratio is very low we have to make a lot more effort to extract semantics. It is even more difficult if we consider higher order n-grams (i.e., sequences of n consecutive words), with n > 2. See for instance [START_REF] Jelinek | Interpolated estimation of Markov source parameters from sparse data[END_REF], [START_REF] Katz | Estimation of probabilities from sparse data for the language model component of a speech recognizer[END_REF], [START_REF] Kneser | Improved backing-off for m-gram language modeling[END_REF].

First topic models

From the bag-of-words representations descrived above, the first IR models are algebraic models, in which documents are represented as vectors. One of the first applications is the vector space model [START_REF] Salton | A vector space model for automatic indexing[END_REF], where the bagof-words representation with TF-IDF score is used for document retrieval. The objective is similar to search engines, namely, return the (stored) document that best matches the (incoming) user's text query. The similarity between the user's query and each stored document is computed with the cosine similarity, i.e., as the (normalized) scalar product between the bag-of-words representations of the query and the document. This first approach is clearly not scalable: given a query, one needs to compute D scalar products of size V, where D is the number of stored documents and V is the size of the vocabulary. If the number of documents D is several billions and the vocabulary contains several thousands words, the time to return a document from a single query may be too long with this representation.

A first extension of this model is the latent semantic analysis (LSA) or indexing (LSI) model [START_REF] Deerwester | Indexing by latent semantic analysis[END_REF]. Given a corpus C = {X 1 , . . . , X D } where X i ∈ R V is the bag-of-words representation of document i, we consider the termdocument matrix T D ∈ R V×D , defined as follows:

T D =     X 1     • • •     X D     .
We reduce the dimension of the document representation by first computing the SVD decomposition of T D : T D = Pdiag (σ) Q , where P ∈ R V×r and Q ∈ R D×r are the singular vectors of T D and σ ∈ R r is the vector of the non-zero singular values of T D . In particular, we can represent document i of the corpus as a vector of size r using the following identity:

X i = Px i = Pdiag(σ)q i ,
where q i ∈ R r is the i-th row of Q and x i = diag(σ)q i ∈ R r is the r-dimensional representation of document i. The vector x i ∈ R r corresponds to the weights given by document i to the r left-singular vectors, i.e., the r columns of P. In other words, x i corresponds to the coordinates of X i in the vectorial space of dimension r in R V with orthonormal basis the r columns of P. As the matrix P is orthogonal, we simply compute the r-dimensional representation x i of document i from X i as follows:

x i = P X i .
This transformation corresponds to a change of basis and can thus be extended to any bag-of-words representation. Given a bag-of-words X ∈ R V , the corresponding r-dimensional transformation x is given by:

x = P X.

In particular, if we consider the transformation of the bag-of-words representation of an incoming query, the cosine similarity between this query and any (stored) document of corpus C is a scalar product of size r (instead of V above). However, as the rank r of the term-document matrix may be large (i.e., close to V), we can reduce even more the dimension of the transfomation. We first choose the K largest singular values σ K ∈ R K of T D and the corresponding K singular vectors [START_REF] Eckart | The approximation of one matrix by another of lower rank[END_REF]. We then use the following approximation to compute the K-dimensional representation of document i:

P K ∈ R V×K and Q K ∈ R D×K . The matrix TK = P K diag(σ K )(Q K ) is the best (in Frobenius norm) rank-K approximation of T D
X i = Pdiag(σ)q i ≈ P K diag(σ K )(q K ) i , where (q K ) i ∈ R K is the i-th row of Q K .
Given this approximation and given that P K is orthogonal, we obtain the transformation xi ∈ R K of X i with the following formulation: xi = (P K ) X i .

The intuition is that the complete representation of X i in the basis P is

x i ∈ R r .
With this new representation xi ∈ R K , we only consider the K coordinates with the highest importance (which is conveyed by σ) to represent X i . We use the same reasoning to extend this new transformation to any bag-of-words representation: x = (P K ) X ∈ R K . The cosine similarity between any two documents (e.g., an incoming query and a stored document) is now computed as a scalar product of size K, which is potentiatlly much smaller than r and V.

In the LSA model, the choice of the dimension K is manual and leads to a tradeoff between the precision of the approximation and the desired computational complexity. The higher the value of K, the more faithful is the representation but the higher the computational cost (both in terms of storage and similarity computation).

Another interesting aspect of the LSA model is that each term can also be represented as a vector of size K. In the term-document matrix T D , the v-th term of the vocabulary is represented by the v-th row Y v ∈ R D . We use the matrix ( TK ) and similar formulations than above applied to (T D ) to transform Y v to a K-dimensional vector:

(Y v ) = Qdiag(σ)(p v ) ≈ (Q K )diag(σ K )(p K ) v , where p v ∈ R r is the v-th row of P and (p K ) v ∈ R K is the v-th row of P K . The representation y v ∈ R K of Y v
is thus given by:

y v = (Q K ) Y v .
This additional term representation is useful for many applications (e.g., find relations between terms such as synonymy or antinomy, term clustering).

The main limitation of the LSA model and its extensions (e.g., the topic-based vector space model [START_REF] Becker | Topic-based vector space model[END_REF]) is its underlying assumption that words and documents follow a joint Gaussian distribution (where negative log-likelihood is a squared Frobenius norm). This assumption comes from the fact that the rank-K approximation of the term-document matrix T D computed with SVD is obtained by minimizing the Frobenius norm T D -M F over all possible rank K matrices M. Thus, as only positive integers are observed in the term-document matrix with word counts representation, Poisson and multinomial distributions are more adapted. For other scores than counts such as TF-IDF, the observed entries are positive and the Gaussian prior is still not appropriate. In the following, we present the probabilistic extensions of LSA for modelling words and documents with Poisson and multinomial distributions.

probabilistic topic models

The LSA model [START_REF] Deerwester | Indexing by latent semantic analysis[END_REF] presented above is a dimension reduction model, where we assume the words and documents are generated from at most K latent features. This constraint is set as a rank constraint on the termdocument matrix T D in LSA and the fitting is done with the Frobenius norm:

TK =    arg min M∈R V×D T D -M F s.t. rank(M) = K.
As a result, the latent features correspond to the singular vectors of the termdocument matrix. Several limitations appear in this model. First, as discussed above, the implicit Gaussian assumption of the LSA model does not match Poisson and multinomial observations. Then, if the number of documents D is large, the SVD decomposition of the term-document matrix may be intractable to compute in practice. Another issue in practice is that if D new documents are added to the training set, it is very costly to compute the SVD decomposition on the V × (D + D ) matrix and it is not straightforward to include the contribution of the D new documents to update the latent features (i.e., to update the singular vectors and singular values of the new term-document matrix).

Probabilistic topic models offer solutions to these limitations. The four main characteristics to define such models are listed below:

• As LSA and previously described models, probabilistic topic models are unsupervised. This type of models is easily transposable to different datasets as no annotation is required. Manual setting is reduced as much as possible;

• Probabilistic topic models are latent variable models. Each observation is described as a mixture of latent features. This property is particularly useful because the number of latent features is usually much smaller than the initial number of dimensions (for instance, in LSA, the initial dimension is the size of the vocabulary V and is reduced to K V in practice);

• Most of topic models are generative. Documents are generated from a mixture of latent components and any previously unseen (or test) document can still be described with the latent components learned from the training documents. In this context, the best model will be the one which has the best generative power, i.e., capable of accurately describe any unseen document coming from the same distribution-in practice, the same dataset-than the training documents;

• As induced by the name, the generative process is based on particular probability distributions. They offer flexibility of modelling. As mentionned above, they offer a solution to the limitations of LSA and the Gaussian modelling assumption.

The LSA model falls in the first two categories (unsupervised and latent variable model) but we cannot generate new documents from the learned parameters (singular vectors and singular values in LSA) and the learned paramaters are not probability distributions parameters, even if we can prove that this model best fits observations drawn from a Gaussian distributions.

Mixture of unigrams [START_REF] Nigam | Text classification from labeled and unlabeled documents using EM[END_REF] The first model example in this context is the mixture of unigrams model [START_REF] Nigam | Text classification from labeled and unlabeled documents using EM[END_REF]. The assumption is that each document d is generated by first choosing a mixture component z ∈ {1, . . . , K}, called topic, then generating the document according to the distribution p(d|z). The probabililty of document d is given by:

p(d) = K ∑ z=1 p(z)p(d|z).
In the mixture of unigrams model, the naive Bayes assumption is used in order to model p(d|z). Given the topic z of document d, the words of this document are assumed independently distributed. The probability of document d = (v 1 , v 2 , . . . , v N d ) is then, under the naive Bayes assumption:

p(d) = K ∑ z=1 p(z) N d ∏ i=1 p(v i |z).
The graphical representation of the mixture of unigrams model is presented in Figure 1a. In this particular model, the naive Bayes assumption matches the bag-ofwords representation. We denote X ∈ R V the bag-of-words representation with frequency score of document d = (v 1 , . . . , v N d ), i.e., X v = n v for v ∈ {v i } i=1,...,N d and X v = 0 otherwise, where n v is the number of occurrences of word v in document d. We then write the probability of document d as follows:

p(d) = K ∑ z=1 p(z)p(X|z),
with p(X|z) = ∏ V v=1 p(v|z) X v . This formulation suggests a multinomial distribution for the conditional p(X|z), which matches the observations. The parameters of the model are the distribution p(z), z = 1, . . . , K and the conditional p(v|z), for v = 1, . . . , V and z = 1, . . . , K, which makes K + VK parameters. In practice, the parameters are estimated by maximum likelihood of a corpus C = {d 1 , . . . , d D }, where documents are independent:

max p(z),p(v|z) L = ∏ d∈C p(d).
This maximization is done with EM algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF].

As each document is attached to a single topic z, the intuition of this model is that words occurring in the same document are associated to the same topic, represented by the hidden variable z ∈ {1, . . . , K}. Each topic z is also associated to the conditional p(v|z) for v = 1, . . . , V. We expect that words that have the highest probability p(v|z) to appear under the topic z exhibit semantic similarity.

In other words, we expect the semantics of topic z ∈ {1, . . . , K} to be conveyed within the conditional (p(v|z)) v=1,...,V .

One limitation of the mixture of unigrams model is that in practice we rather expect that a document is generated from a mixture of different topics. For instance, if we consider restaurant reviews, we expect that the topics discussed in the reviews are, for instance, related to the food, the price, the service, the atmosphere. It is not correct to assume that all the reviews only tackle one of these topics. We rather have to consider that in all the reviews, the topics are tackled with different proportions for each review. In the restaurant reviews example, some users mostly assess the food and the service in their review while other users tackle the food and the price of the meal.

Probabilistic semantic indexing [Hofmann, 1999b] A first extension of the mixture of unigrams model that considers each document is generated from a mixture of topics is the probabilistic latent semantic indexing (pLSI) model [Hofmann, 1999b], also known as the probabilistic latent semantic analysis (pLSA) model [Hofmann, 1999a]. This model is a probabilistic extension of the LSA model [START_REF] Deerwester | Indexing by latent semantic analysis[END_REF] described above and aims at fixing the (wrong) Gaussian assumption underlying the LSA model. In the pLSI model, the joint probability of word v and document d, namely p(v, d), is parameterized. The underlying generative process with pLSI is the following: 1b.

1. Select the document d in a corpus C = {d 1 , . . . ,
The parameters of the model are the document distribution p(d), the latent variables distribution for each document p(z|d) and the topic distributions p(v|z).

In the end the number of parameters is D + KD + KV = K(D + 1 + V). The maximum log-likelihood of the corpus C = {d 1 , . . . , d D } gives an estimate of these parameters: max

p(d),p(z|d),p(v|z) L = ∑ d∈C ∑ v∈d n d v log [p(v, d)] ,
where n d v is the number of occurrences of word v in document d. The EM algorithm is used for this maximization. Note that pLSI is not generative, as the probability of unseen documents p(d new ) is not known and is estimated for training documents only. The document variable d is only a document index in the corpus. In other words, given the parameters of the model, we can not generate new documents.

We can link the pLSI model to the LSA model with an alternative fomulation of the joint probability p(v, d). We use the identity p(d)p(z|d) = p(z)p(d|z) in the model to compute an equivalent formulation:

p(v, d) = K ∑ z=1 p(z)p(v|z)p(d|z).
In this formulation, the occurence of word v is independent from document d given the topic associated to word v: p(v, d|z) = p(v|z)p(d|z). If we denote T ∈ R V×D the matrix such that T vd = p(v, d), P ∈ R V×K the matrix such that P vz = p(v|z), Q ∈ R D×K the matrix such that Q dz = p(d|z) and σ ∈ R K the vector such that σ z = p(z), the joint probability model T can be written as a matrix product:

T = Pdiag( σ) Q,
which makes a clear link between pLSI and LSA. While in LSA, the K latent factors P K and Q K are orthogonal singular vectors, in pLSI the matrices P and Q are not orthogonal and correspond to conditional distributions of the model. The main difference between LSA and pLSI thus resides in the objective function.

The Frobenius norm used in LSA implicitly models the term-document coefficients with a Gaussian distribution. As a result, the approximation T K of T D with LSA is not faithful to the observations-integer word counts-and may even contain negative entries. On the contrary, pLSI properly defines a probabilistic model of the term-document co-occurrences based on multinomial sampling. The objective function is the likelihood function of the observations and we can show that the maximum likelihood computation with pLSI corresponds to the minimization of the Kullback-Leibler divergence between the empirical distribution (T D ) and the model ( T):

     arg min p(d),p(z|d),p(v|z) KL T D || T s.t. rank( T) = K.
In practice, the pLSI model is more flexible and better handles polysemy than LSA. As the latent factors are not necessarily orthogonal, pLSI model allows correlation between latent topics p(v|z), which is more realistic. In LSA, the orthogonality of latent topics typically implies that any word v of the vocabulary only falls in a single category, i.e., in the extreme case, p(v|z * ) ≈ 1 and p(v|z) ≈ 0 for z = z * . However, for polysemous words, this constraints does not hold. For instance, in a movie reviews dataset, we expect that words like shoot, mole or model appear in two different topics. The word shoot may be related to the cinematography or the action to fire a gun. The word mole may refer to the animal or an infiltrated spy. The word model may refer to a miniature object or a mannequin.

The pLSI model can be seen as a nonnegative matrix factorization (NMF) model [START_REF] Dhillon | Generalized nonnegative matrix approximations with Bregman divergences[END_REF] with specific (non Gaussian) generative assumptions on the term-document matrix. While the multinomial distributions are adapted to documents, the model may be adapted to fit any type of positive data [START_REF] Paatero | Positive matrix factorization: A non-negative factor model with optimal utilization of error estimates of data values[END_REF]Tapper, 1994, Lee and[START_REF] Lee | Learning the parts of objects by non-negative matrix factorization[END_REF].

The main limitations of the pLSI model are the number of parameters which grows linearly with the number of observed documents D and the fact that this model is not generative and has a limited predictive power on unseen documents.

In the next section, we describe the latent Dirichlet allocation model (LDA) model [START_REF] Blei | Latent Dirichlet allocation[END_REF] which intends to make the best of both mixture of unigrams and pLSI models. On the one hand, the mixture of unigrams model is generative and has a fixed number of parameters. On the other hand, with pLSI the documents are modelled as mixtures of different topics. The LDA model combines these advantages.

lda, existing extensions and applications

The latent Dirichlet allocation (LDA) model [START_REF] Blei | Latent Dirichlet allocation[END_REF]] is a generative extension of the pLSI model. In LDA, the topic distribution p(v|z) v=1,...,V is denoted

β z ∈ R V , with the constraints ∑ v β z v = 1.
The difference with pLSI is that the topic proportions vector of document d is a parameter in pLSI (denoted p(z|d) z=1,...,K above), while in LDA the topic proportions vector is a random variable, denoted θ, set with a Dirichlet prior. More formally, document d is generated as follows: The parameters of the model are the topic matrix β ∈ R V×K and the Dirichlet prior α ∈ R K on the document topic proportions, that is KV + K parameters.

The probability of document d generated with LDA is given by:

p(d|α, β) = θ p(θ|α) ∏ v∈d K ∑ z=1 p(z|θ)p(v|z, β) dθ.
This probability is intractable to compute in practice, so the EM algorithm can not be applied directly to the LDA model. The maximum likelihood is instead estimated with variational EM [START_REF] Blei | Latent Dirichlet allocation[END_REF][START_REF] Hoffman | Online learning for latent Dirichlet allocation[END_REF], Gibbs sampling [START_REF] Griffiths | A probabilistic approach to semantic representation[END_REF] or moment matching [START_REF] Podosinnikova | Rethinking LDA: moment matching for discrete ICA[END_REF]. We tackle and propose a new online inference scheme (i.e., inference from streams of documents) for intractable latent variable models in Chapter 3.

As the previous presented models, the generative process of LDA can be seen as a factorization on the bag-of-words representation X ∈ R V of document d, considered as a random variable. In the LSA model, the underlying generative process is:

X ∼ Gaussian(Px, I V ), (LSA)
where P ∈ R V×K is an orthogonal matrix and x ∈ R K is a low-dimension representation of X. In the mixture of unigrams model (MU), each document is generated from a single feature z:

X|z ∼ Multinomial( P z , N d ), (MU)
where P z ∈ R V is a topic vector P z v = p(v|z). In the pLSI model, each document d has its own factorization model:

X|d ∼ Multinomial( P x, N d ), (pLSI)
where P ∈ R V×K is a topic matrix P vz = p(v|z) and x ∈ R K is a vector of joint distribution x z = p(d|z)p(z) = p(d, z). Finally, in LDA, given the topic proportions θ, the generative process is independent of the document. In other words, the distribution X|θ does not depend on the document and is factorized as:

X|θ ∼ Multinomial(βθ, N d ), (LDA)
where β ∈ R V×K is a topic matrix β z v = p(v|z) [START_REF] Buntine | Discrete principal component analysis[END_REF]. In LDA, each document is modelled with a mixture of different topics and the number of parameters does not depend on the size of the corpus. In particular, online inference-i.e., learn the parameters from streams of data-is much more practical than with the other presented methods. The LDA model is easily enhanced by adding new variables (see next section). Even if the resulting generative process is much more sophisticated, the inference scheme for these extensions is usually very similar to the LDA inference, which explains the attractiveness of this model. As a matter of fact, the LDA model is widely popular (almost 20,000 citations; pLSI has 4000 citations), has been used for many applications and has led to many extensions.

Extensions of LDA

There exist many extensions of LDA to match particular applications or to correct a specific limitation of the model.

Topic coherence improvement.

In the LDA model, when the number of topics K is very large, some topics are "junk" topics, namely topics that are not consistent around an aspect (e.g., food or service in a restaurant reviews dataset). A solution to this issue is to automatically filter out these "junk" topics by ranking them [START_REF] Alsumait | Topic significance ranking of LDA generative models[END_REF]. Another solution is to regularize the objective function [START_REF] Newman | Improving topic coherence with regularized topic models[END_REF]. The empirical judgement of topics by users is discussed by [START_REF] Chang | Reading tea leaves: How humans interpret topic models[END_REF].

Topic structure.

The first extensions of LDA found in the litterature are related to the structure of the topic matrix. In LDA, the topics are represented by β ∈ R V×K as a list of K independent discrete distributions on the vocabulary of size V, where the number of topics K is set manually. One of the limitations of LDA is that it does not model the correlation between topics although we expect that a document about politics is more likely to also tackle elections than sport. In the correlated topic model (CTM) [START_REF] Blei | A correlated topic model of Science[END_REF] the Dirichlet prior on θ in LDA (the topic proportions of the document) is replaced by a logistic normal distribution to parameterize and learn the correlation between topics. As a result, on top of learning a topic matrix β, explicit links between the K topics are learned and we can represent the topics as a graph where an edge between two topics is set if their correlation is high enough (see [START_REF] Blei | A correlated topic model of Science[END_REF] for more details and examples of such graphs). A related model is the latent topic network model (LTN) [START_REF] Foulds | Latent topic networks: A versatile probabilistic programming framework for topic models[END_REF], where the Dirichlet prior on θ is replaced by a conditional random field (CRF). A graph of topics is thus learned with this model. Another approach to model the correlation of topics is to put a prior on the topic matrix β, parameterized as a sum of regression factors [START_REF] Paul | Factorial LDA: Sparse multi-dimensional text models[END_REF].

Non-parametric approaches.

Another limitation of the LDA model is the number of topics K which has to be set manually. Several non-parametric extensions of LDA adaptively learn the number of topics from the documents. For instance, in the hierarchical Dirichlet process (HDP) [START_REF] Teh | Hierarchical Dirichlet processes[END_REF], a list of topics is iteratively updated by adding or removing topics of the list. More complex structures than lists are also used to model the topics. Both the nested Chinese restaurant process (nCRP) [START_REF] Blei | The nested Chinese restaurant process and Bayesian nonparametric inference of topic hierarchies[END_REF] and the nested hierarchical Dirichlet process (nHDP) [START_REF] Paisley | Nested hierarchical Dirichlet processes[END_REF] learn a (non-parametric) tree of topics from documents. In this tree, the root topic is the most generic while a leaf topic is very specific (e.g., sport is the parent topic of soccer and baseball). See an efficient algorithm for such models in Chapter 3.

Multi-scale topics.

The LDA model does not consider the structure of the documents, i.e., the sentences and the order of words. In the multi-grain LDA (MG-LDA) model [START_REF] Titov | Modeling online reviews with multi-grain topic models[END_REF], two scales of topics are learned. A list of "global" topics describing a whole document and a list of "local" topics describing sentences. Consequently, this models takes into account the structure of the documents while still keeping the practical bag-of-words representation for the documents and sentences.

Dynamic topic models.

In the LDA model, the temporal order of documents is not considered. However, for large dynamic datasets such as news, the topics discussed in the news ten years ago are probably strongly different than the topics of nowadays news. In the dynamic topic model (DTM) [START_REF] Blei | Dynamic topic models[END_REF], a discrete evolution of the topic matrix is considered by grouping documents in temporal bins. The continuous time extension of the DTM model, called continuous time dynamic topic model (cDTM) [Wang et al., 2012], in which the timestamp of each document is considered. Other approaches to model the temporal evolution of text datasets represent words co-occurences as a dynamic graph over time [START_REF] Palla | Bayesian nonparametrics for sparse dynamic networks[END_REF].

Opinion mining.

In the ASUM model [START_REF] Jo | Aspect and sentiment unification model for online review analysis[END_REF], a hidden "sentiment" variable is attached to each sentence and is used to extract positive and negative topics. In the topic sentiment mixture model [START_REF] Mei | Topic sentiment mixture: modeling facets and opinions in weblogs[END_REF], each of the K latent features is divided in three topics: one neutral, one positive and one negative topic. In the restaurant reviews example, each aspect-food, service, atmosphere, price-would be attached to three topics that respectively convey neutral, positive and negative words about this aspect. In this model, the underlying generative process of a document is the following: we first choose one of the K features, then one of the three sentiment (expected to be neutral, positive or negative), finally we sample a word from the corresponding topic (e.g., topic of positive word distribution about food). These three steps are performed by sampling from multinomial distributions. In the joint sentiment/topic model (JST) [START_REF] Lin | Joint sentiment/topic model for sentiment analysis[END_REF], S lists of K topics are learned, each list corresponding to a sentiment (typically, S = 3 to model K neutral, K positive and K negative topics). The generative process for words is the following: one of the sentiment features s ∈ {1, . . . , S} is choosen, then one of the K topics of list s is sampled and finally a word from this topic is drawn. Note that in the JST model, there is not necessarily correspondance between neutral, positive and negative topics. It may happen that the price aspect only appears in the neutral list of topics while the food aspect appears in the positive and negative list of topics (but not in the neutral list).

Recommendation.

In crowd-sourced review services such as Yelp, IMDB, Amazon etc., each user assesses a particular content (e.g., a movie, a restaurant, a product) with a numerical rating together with a detailed text comment of her opinion on the different aspects of the content. A recommender system is built by combining ratings and text reviews in LDA. In the supervised LDA model [START_REF] Mcauliffe | Supervised topic models[END_REF], the rating is parameterized as a response to the corresponding text review. As a result, given an unseen text review, the model is able to predict the rating attached to this review. Each topic learned with this model is attached to a score which represents the influence of this topic on the final rating. Another solution to combine rating and text in LDA given by [START_REF] Mcauley | Hidden factors and hidden topics: understanding rating dimensions with review text[END_REF] is to explicitly parameterize the topic proportions of the review θ as a function of the rating r attached to the review. We propose in Chapter 2 an extension of LDA to combine ratings and text reviews in which we distinguish the topics that convey opinion from descriptive (neutral) topics.

Limitations

In a recommender system where we want to suggest contents together with personalized text, the main limitation of the presented topic models is the bagof-words representation. Indeed, with this representation, we can only suggest bag-of-words documents to user, i.e., lists of single words. For instance, if you are suggested the movie Batman, a topic model like LDA would probably attach the words batman, action, good, movie, robin. The issue is that this list of words may not be intuitive to make a decision about the content. It would be more intuitive to have readable sentences such as Batman is a good action movie. This requires to represent differently the documents and in particular to model the dependency between words of a document. In the next section, we discuss other approaches to represent and model documents; see also Chapter 4.

beyond lda and bag-of-words representation

As explained above, the bag-of-words representation for documents is practical but totally dismisses the structure of a document. In particular, both the order of words and sentences cutting are ignored and words are assumed to be (conditionnally) independent, which is an issue. Indeed, we expect that, if we are given the word v n in the n-th position of a document, the distribution of the preceding word p(v n-1 |v n ) is different than the distribution of the following word p(v n+1 |v n ). For instance, in a restaurant review, if we know that v n = hot, it is more likely that the preceding word is good and the following word is dog than the other way around (good hot dog is more likely to appear than dog hot good). More formally:

p(v n+1 = dog|v n = hot) p(v n+1 = good|v n = hot), p(v n-1 = dog|v n = hot) p(v n-1 = good|v n = hot).
In LDA and other topic models, this order relation is ignored.

A n-gram is defined as a sequence of n consecutive words (v 1 , v 2 , . . . , v n ). The order is important here as for instance (v 1 , v 2 ) = (v 2 , v 1 ) for n = 2. Note that in a bag-of-words representation, the pairs (v 1 , v 2 ) and (v 2 , v 1 ) are strictly equivalent. The n-gram class model [START_REF] Brown | Class-based n-gram models of natural language[END_REF] addresses the problem of predicting a word given the n -1 previous words in a sample of text. In this model, instead of directly estimating the distributions p(v|v 1 , v 2 , . . . , v n-1 ) which require V n -1 parameters, a class c ∈ {1, . . . , C} is associated to each words and the model follows the assumption:

p(v|v 1 , v 2 , . . . , v n-1 ) = p(v|c n )p(c n |c 1 , . . . , c n-1 ),
where c i is the class of the word in position i in the sequence. This assumption follows the intuition that the vocabulary may be clustered in C classes of words and words in the same class are interchangeable in a sample of text. For instance, if we have to finish the sentence "My appointment is on ___", the words Monday and Thursday are equally probable to occur. Therefore, they would be assigned the same class and the number of parameters to fill the sentence is reduced from V to C. If the size of the vocabulary V is large, this modelling assumption reduces significantly the number of parameters involved. [START_REF] Brown | Class-based n-gram models of natural language[END_REF] propose algorithms to approximate the maximum likelihood of the 2-gram class model.

However, the n-gram models are not generative as their goal is to predict the last word of a n-gram given the n -1 previous words. The bigram topic model [START_REF] Wallach | Topic modeling: beyond bag-of-words[END_REF] combines the LDA model with a 2-gram (or bigram) model. In this model, the word v t in position t is generated from the previous word v t-1 and the chosen mixture for this word z t ∈ {1, . . . , K}. The context v t-1 has an influence on the generative process. The parameters learned are the distributions p(v t |v t-1 , z t ) which correspond to V × K topics (instead of K topics in LDA). While the choice of topic z t for word t is the same than for LDA p(z t |θ), each word is now generated from the topic matrix φ ∈ R VK×V , with φ

(j,k) v = p(v t = v|v t-1 = j, z t = k).
The combination of the LDA model with a bigram model results in a generative model that takes the structure of the document (or the context) into consideration. If we extend this model to ngrams with n > 2, namely model the distributions p(v t |z t , v t-1 , v t-2 , . . . , v t-n+1 ), the number of parameters required grows exponentially with the length of the n-gram O(KV n ) with no further assumptions, which becomes computationally intractable for large vocabulary V.

Other scalable approaches have been developped to model long contexts. One recently popular approach use word embeddings. The princple is to map each word v of the vocabulary in a r-dimensional space. Given a corpus C of observed documents, the vectors (X v ∈ R r ) v=1,...,V associated to words of the vocabulary are learned from C by minimizing a cost function (or maximizing a likelihood) on the embeddings. This cost function is typically set so that words that are used in similar context (i.e., interchangeable words) have similar embeddings.

This word embeddings approach has recently gain popularity with the skipgram (or word2vec) model [Mikolov et al., 2013b]. In this model, the online inference of the embeddings is efficiently implemented and requires absolutely no supervision. The principle is to maximize the likelihood of words in a window:

L = T ∑ t=1 ∑ -c≤j≤c,j =0 log p(v t+j |v t ).
The window (v t-c , . . . , v t-1 , v t+1 , . . . , v t+c ) is the context of word v t and the window size c is manually set in practice. In the skip-gram model, the probability p(v t+j |v t ), for -c ≤ j ≤ c, is parameterized as a soft-max function of the embeddings:

p(v t+j |v t ) = exp ( X v t+j , X v t ) V ∑ w=1 exp ( X w , X v t )
. This raw skip-gram formulation is impractical as the computational cost of the gradient ∇ log p(v t+j |v t ) is proportional to the vocabulary size V, which is large for real datasets (10 4 -10 7 ). Along with this skip-gram model, Mikolov et al. [2013b] combine different tricks to efficiently maximize the likelihood L. Conse-quently, this model and other related word embeddings models have been used for many applications as word vectors are quickly computed and the comparison of two words is efficient. For instance, this type of models covers question answering [Mikolov et al., 2013a[START_REF] Bordes | Question answering with subgraph embeddings[END_REF], document classification [START_REF] Kusner | From word embeddings to document distances[END_REF][START_REF] Huang | Supervised word mover's distance[END_REF], automatic translation [START_REF] Zou | Bilingual word embeddings for phrase-based machine translation[END_REF].

Even if the word embeddings models are powerful tools to effectively parameterize the structure of documents, they only provide seperate representations for words of the vocabulary. Given the vectors associated to every words of the vocabulary, it is not straightforward to compute the representation of a full sentence or a full document as a vector. We propose in Chapter 4 a document model based on determinantal point processes (DPP). In our model, a document is represented as a list of sentences and each document is generated by selecting a subset of all the possible sentences. The probability of a subset is parameterized with a DPP. Note that with our representation, the sentences of a document are not independent. We apply our model to document summarization where we propose readable summaries of restaurant reviews.

contributions

In this thesis, given the models previously described, we make the following contributions to the problem of suggesting personalized annotated content to the users:

• Chapter 2. We first observe that topic models like LDA mostly extract descriptive words and give a very low importance to words that convey opinion. We propose a model that leverages ratings together with reviews to distinguish qualitative and descriptive words. While several existing methods include ratings in the LDA model (e.g., [START_REF] Mcauliffe | Supervised topic models[END_REF], [START_REF] Mcauley | Hidden factors and hidden topics: understanding rating dimensions with review text[END_REF]), their goal is to improve the rating prediction by adding the text information. Moreover, topics that convey opinion are not clearly identifiable with such methods. As we want to suggest text to the user, our method rather leverages ratings to improve review prediction. We run and evaluate our method on a movie reviews dataset. Not only does our model improve the overall predictive power compared to existing work but it also extracts meaningful positive and negative topics that are automatically identifiable. This work is accepted at the 13th International Conference on Machine Learning and Data Mining (MLDM) 2017.

• Chapter 3. For very large corpora or online review services, it is convenient nay necessary to process the dataset little by little. We provide a method to efficiently learn parameters from streams of data when the model posteriors are intractable to compute (which is usually the case for topic models).

There exist many online inference schemes for the LDA model but the link between these methods is not explicit. We propose a unifying frame-work to draw explicit links between these methods and propose a new online method in this framework that outperforms the previously proposed schemes. This work is under revision at JMLR.

• Chapter 4. Determinantal point processes (DPPs) are useful to model diversity for subset selection problems. These models suffer from a high computational cost when the number of items to choose from is large. We propose a new class of DPPs based on a specific low-rank factorization of the marginal kernel, which is particularly suited to DPPs defined on exponentially many items. We apply this new class to modelling text documents as sampling a DPP of sentences, and propose a conditional maximum likelihood formulation to model topic proportions, which is made possible with no approximation for our class of DPPs. More precisely, given the topic proportions, a document is generated with our model by selecting a subset of diverse sentences among all the possible sentences and the probability distribution over the subsets of sentences (i.e., over the possible documents) is formulated as a DPP. We present an application to document summarization on a restaurant reviews dataset with a DPP on 2 500 items. We observe that our model is able to generate meaningful summaries and extract word embeddings and topics that convey semantics, while keeping a reasonable computational complexity. This work is submitted to ICML 2017.

2

P E R S O N A L I Z E D R E V I E W P R E D I C T I O N W I T H L AT E N T D I R I C H L E T A L L O C AT I O N
Crowdsourced review services allow any user to assess contents (e.g., movies, restaurants, hotels) through both numerical rating and free form text. They exploit the ratings to suggest contents to users while making raw reviews available for users to get a precise opinion on a particular content. As it is tedious to extract useful information among thousands of reviews, it is more intuitive and less time consuming for users to access a personalized summary of the other users' opinions on each content. In this regard, many existing implementations either manually label each content-e.g., with the genre-or select "useful" reviews to read in order to make a quick opinion on the particular content. These existing approaches suffer from several limitations. First, the textual information-labels of contents or "useful" reviews-provided by the system is not personalized and may not be adapted to every user. The aspects decribed in the selected "useful" reviews may not be decisive in the opinion of every user and the labels of contents may be too generic to make a decision. The labelling of the movies is also a cumbersome human task.

Consequently, our goal is to suggest the user a personalized text summary of what could be her opinion on each content she visits, in order to enhance recommender systems.

In our approach, we combine both text reviews and numerical ratings to automatically predict the words a user would employ to assess an unseen content. We leverage topic models to separate descriptive information and qualitative information in distinct topics. This distinction between descriptive and qualitative information is crucial as it enables to decompose the reviews in (1) the aspects evaluated in the reviews and (2) the opinion attached to these aspects. Without this distinction, it is impossible to automatically identify the decisive aspects in the opinion of the user. We extend the LDA (latent Dirichlet allocation) model [START_REF] Blei | Latent Dirichlet allocation[END_REF] to include ratings along with texts.

Our contributions are (1) extensions of LDA in order to separate descriptive and qualitative topics in a corpus of text reviews using movie ratings and (2) their theoretical evaluation and comparison to state of the art [START_REF] Mcauley | Hidden factors and hidden topics: understanding rating dimensions with review text[END_REF]Leskovec, 2013, Mcauliffe and[START_REF] Mcauliffe | Supervised topic models[END_REF] for the task of word prediction. As a by-product (3) we show that profiling users from reviews is not possible with this method because of the diversity of movies reviewed and opinions expressed by users. Note that this work can easily be generalized to other types of content such as restaurants, hotels and products. We have indeed applied our models on a restaurant dataset with similar observations and performance. This work will be published in the proceedings of the 13th International Conference on Machine Learning and Data Mining (MLDM) 2017.

topic extraction with lda

We define a corpus as a list of documents and a document (e.g., a single user review) as a list of words. In this section we present the methodology we use to pre-process raw text reviews. We then describe two types of topic models. The first type of model only applies to text while the second type of model applies to text and ratings. Each review is generated by a user on a movie. We apply each type of model to three different corpora, depending on wether a document is (1) a single review, (2) the concatenation of reviews related to a single movie or (3) the concatenation of reviews written by a single user. These three different processes with the two types of models lead us to six different models.

Pre-processing Reviews

Many words in reviews are not relevant for our purpose as they convey neither qualitative nor descriptive information (e.g., stop words), or because they appear too frequently in reviews and are too generic (e.g., movie, film, scene in movie reviews).

We first remove the stop words using the NLTK toolbox [START_REF] Bird | Natural language processing with Python[END_REF] and words appearing in more than 20% of the reviews (for instance, movie appears in 80% of the reviews). We choose 20% as a threshold because it only filters out very frequent words. We then select from the remaining words the 10,000 most frequent words in the database. We observe that in our IMDB dataset of 97,000 reviews (we use a subset of the dataset decribed by [START_REF] Diao | Jointly modeling aspects, ratings and sentiments for movie recommendation (JMARS)[END_REF] that spreads over 5,900 movies and 2,400 users), after filtering, each word appears in at least 10 reviews, which means only words that appear in less than 10 reviews-i.e., 0.01% of the dataset-have been pruned.

LDA and Extensions

Let D be the number of documents of a corpus W = {w 1 , . . . , w D }, V = 10, 000 the number of words in the vocabulary and K the number of latent topics in the corpus. Each topic φ k corresponds to a distribution on the V words. For each document d, LDA infers a discrete distribution θ d over the K topics. In practice, the inference may be done using variational EM [START_REF] Blei | Latent Dirichlet allocation[END_REF], Gibbs sampling [START_REF] Griffiths | Finding scientific topics[END_REF] algorithm or online learning [START_REF] Hoffman | Online learning for latent Dirichlet allocation[END_REF]. As detailed in Chapter 3, LDA is a generative model applied to a corpus of text documents which assumes that the n-th word w d n of the d-th document is generated as follows:

• Choose θ d ∼ Dirichlet(α), LDA-O, 1 doc = 1 review LDA-C, 1 doc =
portance θk = 1 D ∑ d θ d k ).
• For each word

w d n ∈ w d : -Choose a topic z d n ∼ Mult(θ d ), -Choose a word w d n ∼ Mult(φ z d n ).
In a recommendation setting, each review refers to a unique (user, movie) pair. One could use this information to learn specific topics of (movies, users) pairs and get a more precise representation of the reviews. In our baseline model, noted LDA-O, we run LDA on a corpus where each document is a single review (i.e., we consider that reviews are independently generated).

We then aggregate our reviews accounting for the fact that multiple reviews either belong to a movie or to a user. We build user profiles in LDA by constraining the topic document distribution θ to be the same for all the reviews written by the same user. It is equivalent to considering a new corpus where each document is the concatenation of all the reviews written by a single user. We refer to this model as LDA-U and we refer to the topic document distributions θ u inferred with LDA-U as "topic user distributions", where u ∈ {1, . . . , N u } denotes users. The same aggregation is done to profile movies with the corpus where a document is the aggregation of all the reviews belonging to the same movie. We refer to this model as LDA-C and we refer to the topic document distributions θ c as "topic movie distributions", where c ∈ {1, . . . , N c } denotes movies.

Inferred Topics.

Topic consistency is an empirical notion that we use in the rest of the chapter. A strongly consistent topic has all its top words belonging to the same lexical field. This notion can be applied to any list of words such as a document or a corpus.

Parameter K influences the consistency of the descriptive topics. Ideally, we would like each topic to represent a movie feature, e.g. actors, genres, or sequels.

After multiple experiments with values of K between 8 and 260, we observed that for K ≤ 30, the descriptive topics mix several features. On the contrary, for K ≥ 150, each feature is spread over multiple topics and topic consistency decreases. In Table 1, K = 128 is a good compromise1 .

The first 5 topics inferred with the models LDA-O and LDA-C proposed above are presented in Table 1. As the topics extracted with LDA-U are not consistent, they are not presented. We observe that topics in LDA-O and LDA-C are very consistent around a genre, an actor, a director or a sequel. The main difference between these two methods is that there are more outliers in LDA-O topics than in LDA-C topics. These outliers are generic words appearing frequently enough in the corpus to influence the topics. These words are not frequent enough to be removed during the filtering (e.g., best, action, review). In LDA-C, the aggregation of reviews related to the same movie lowers the impact of these outliers.

The corpus used in LDA-C is consistent because reviews of the same movie share a common vocabulary, each document of this corpus brings out words associated to the movie and lowers the influence of noisy words in the topics. We also observe that topics obtained with our models are mostly descriptive and that very few qualitative information is "lost" in the middle of the topics, making it difficult to tell a user whether or not she would like a movie.

Inclusion of Ratings in the Inference Process

Given the lack of qualitative in the top words of the topics, we introduce a method to extract qualitative topics (i.e., words with a positive or negative connotation) using numerical ratings in addition to text reviews. Given a text review and the corresponding rating, we expect user's opinion to be conveyed in the text and summarized in the rating. Ideally, positive (resp. negative) words should be more likely to appear in a high (resp. low) rated review. In order to keep the model simple, we reduce first numerical ratings (initially between 1 and 10) to binary ratings {-1, +1}. Using these new ratings, we infer a positive (resp. negative) topic from +1 (resp. -1) reviews in a new generative model.

Rating Reduction.

We use a standard rating prediction technique [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF] to extract users and movie features given ratings. We denote by D the number of reviews, r d the rating of the d-th review, related to user u d ∈ {1, . . . , N u } and movie c d ∈ {1, . . . , N c } with d ∈ {1, . . . , D}. We first model the ratings to be generated as a sum of a user factor and a movie factor (ANOVA, [START_REF] Casella | Statistical inference[END_REF]):

r d = µ + a u d + b c d + , d ∈ {1, . . . , D},
with ∼ N (0, σ 2 ). We optimize (a u ), (b c ) and µ as the solution of a penalized (in L 2 norm) least-squares problem. The training ratings are reduced to -1 if the following residual is negative and to +1 if the residual is positive:

rd = +1 if r d -(a u d + µ) ≥ 0 -1 otherwise.
In the model, µ represents the average rating, b c the average deviation from µ of ratings on movie c, a u the average deviation from µ of ratings from user u. We consider here that a review is positive (r d = +1) if user u d rated movie c d with a higher score than her average rating (a u d + µ). The reduced rating rd represents the binary user opinion.

For any test review t, the user opinion rt is unknown. This quantity is then a random variable with:

Pr[r t = +1] = Pr(b c t + ≥ 0|a, b) Pr[r t = -1] = 1 -Pr[r t = +1].
During prediction of the review t, we use these probabilities to extract a mixture of positive and negative words.

Qualitative Topics Inference

We use these reduced ratings (r d ) to infer qualitative topics. We consider a corpus where each document is a single review. We denote by D the number of documents, by c d ∈ {1, . . . , N c } and rd ∈ {-1, +1} respectively the movie and reduced rating of the d-th document, d = 1, . . . , D. K is the number of descriptive topics, i.e., the number of topics extracted with LDA-C. Given K, the corresponding topic movie distributions θ c , c ∈ {1, . . . , N c } inferred with LDA-C on the D reviews and the reduced ratings (r d ), we extract a positive topic and a negative topic with the following generative model. For each word w d n of the d-th document w d :

• Draw m d n ∼ Bernoulli(p d ) • If m d n is a success (m d n = 1): -Choose w d n ∼ Multinomial(Ψ rd ), with rd ∈ {+1, -1} • Otherwise (m d n = 0): -Choose a topic z d n ∼ Multinomial(θ c d ) -Choose w d n ∼ Multinomial(φ z d n ).
In other words, if m d n is a success, w d n is qualitative otherwise w d n is descriptive. We still infer K descriptive topics with this method, represented by {φ 1 , . . . , φ K }.

The main difference with LDA-C is that we only infer φ, Ψ parameters, knowing topic document distributions θ. We also learn the proportion of qualitative/descriptive words in each document p d , embedded with a Dirichlet prior. In the following, we refer to this model as LDA-R-C. The graphical representation of LDA-R-C is presented Figure 3.

We build two additional models by replacing in LDA-R-C the topic movie distributions θ c by the topic document distributions

θ d , d = 1 . . . D-model LDA-R-or by the topic user distributions θ u , u = 1 . . . N u -model LDA-R-U.
For the three models, the inference is done with a variational EM algorithm adapted from LDA inference [START_REF] Blei | Latent Dirichlet allocation[END_REF]-see Appendix 2.A for complete derivations. We also run a full EM for learning at the same time both topics (parameters φ, Ψ) and topic distribution (parameter θ). As the algorithm is very sensitive to initialization, we observe that random initialization gives poor results while initialization with parameters resulting from LDA-O leads to a steady state. Indeed, LDA-O returns a local miminum of the full algorithm.

Inferred Topics.

As the qualitative topics extracted with LDA-R-U are not consistent, they are not presented. The qualitative topics inferred with LDA-R and LDA-R-C are presented in Table 2. In both LDA-R and LDA-R-C the average proportion 1 D ∑ d p d of qualitative words in documents is 10%. Some qualitative words appear in the top words of the opposed topic (e.g., bad comes up in the positive topic of LDA-R). In our model, each training document d is assigned to only one qualitative topic-Ψ +1 or Ψ -1 -depending on the corresponding rating rd . Consequently, if a positive word frequently appears in low rated reviews-e.g., in negation phrases-it is likely to be a top negative word and vice versa. Some neutral words also come up in these qualitative topics (e.g., suppose). These words appear in reviews of different types of movies and are then in the tail of descriptive topics. They are still used frequently enough to have an influence on the qualitative topics.

evaluation

In this section we evaluate our model for the review prediction task. Using our models, a review prediction is a discrete distribution over the V words of the

Methodology.

Given a test review w, the best predictor maximizes the likelihood P(w|W ) of the test review, P depending on the model. We then use the log-perplexity measure defined by LP =log P(w|W ) to evaluate our models. The log-perplexity is a theoretical measure of the quality of the model for the word prediction task; it is not an indicator of user satisfaction. As shown by [START_REF] Chang | Reading tea leaves: How humans interpret topic models[END_REF], the perplexity is not suited to measure user satisfaction. However, perplexity measures the precision of the prediction, which is what we need in order to compare our models to the state of the art.

For LDA-O, the likelihood is intractable to compute. We approximate P(w|W ) with the "left-to-right" evaluation algorithm [START_REF] Wallach | Evaluation methods for topic models[END_REF] applied to each test document. This algorithm is a mix of particle filtering and Gibbs sampling, easily adjustable to other graphical models. For LDA-C, as the topic distributions are learned for each movie (resp. user), the likelihood of a new review is computed for movies (resp. users) seen in the training corpus through pointwise estimation. Finally, we adapt the "left-to-right" algorithm to approximate the likelihood of LDA-R and LDA-R-C for each test document.

We compare our models to two existing approaches. In the model proposed by McAuley and [START_REF] Mcauley | Hidden factors and hidden topics: understanding rating dimensions with review text[END_REF], authors use words and ratings to predict ratings by learning a mapping function between LDA parameters and rating matrix factorization parameters. We refer to this model as HFT (which stands for "hidden factors as topics"). In the model proposed by [START_REF] Mcauliffe | Supervised topic models[END_REF], authors incorporate scores directly in LDA in order to predict the score of a new review given the words used. We refer to this model as SLDA. These two methods will be discussed in related works. Both HFT and SLDA use documents and ratings associated to each document to infer similar parameters than LDA-i.e., topics φ and topic proportions θ. While the application presented by [START_REF] Mcauliffe | Supervised topic models[END_REF] and [START_REF] Mcauley | Hidden factors and hidden topics: understanding rating dimensions with review text[END_REF] is rating prediction, we can use the parameters φ and θ inferred with these methods to predict words of new reviews.

We could not compare to the method described by [START_REF] Ling | Ratings meet reviews, a combined approach to recommend[END_REF] because of the lack of information available to implement the method accurately.

The review dataset was collected from IMDB, with a catalogue of 5,900 movies, 2,400 users and 97,000 reviews-a subset of the data described by [START_REF] Diao | Jointly modeling aspects, ratings and sentiments for movie recommendation (JMARS)[END_REF]. We apply our models to 10 random splits of train and test sets, representing respectively 90% and 10%. Each movie and each user of a testing set is seen at least once in the corresponding train reviews.

Figure 4 presents the average log-perplexity measures per word on the test sets for LDA-O, LDA-C, LDA-R, LDA-R-C, HFT and SLDA. Given the poor topic consistency observed with LDA-U and LDA-R-U and their poor performance, we do not display perplexity for these models. Evaluation.

The number of topics K is the unique input of LDA and its extensions. It represents the dimension of the latent topic document distribution θ. The Perplexity on test sets still decreases at K = 128 for LDA-C and LDA-R, which means we do not reach overfitting with K ≤ 128. LDA-O overfits the training reviews as it infers one distribution over topics (θ) by review. This method does not catch the structure of the vocabulary in the reviews as all reviews are processed separately. The predictions with LDA-O are then polluted by frequent words which appear in the inferred topics and lower the quality of the predictions. Conversely, the aggregation of reviews in LDA-C improves the consistency of the topics and generates better movie profiles (through topics movie distribution θ c ). LDA-C outperforms LDA-O.

By comparing the performance of LDA-O and LDA-R, we can observe that including reduced ratings in LDA-O improves perplexity for all values of K. Indeed, for all K, descriptive topics of LDA-R contain noisy words. The representation of the qualitative words in the training set results in an important decrease of perplexity compared with LDA-O.

The consistency of qualitative topics in LDA-R makes predictions outperform LDA-R-C. Predictions with LDA-R-C are also beaten by predictions with LDA-C. The consistency of descriptive topics of LDA-C is affected when including ratings.

With HFT the topic-document distribution θ is mapped to matrix factorization parameters. The objective being optimized can be expressed as a sum: f =(rating prediction error)-(corpus likelihood). The quality of word prediction is deteriorated as the objective is not directly the corpus likelihood. As a result, HFT is the worst predictor.

SLDA overfits at K = 32 as it infers one distribution over topics (θ) by review. This model includes ratings in LDA to infer a score along each topic. As a result, SLDA extracts descriptive and qualitative topics but they may not be automatically differentiated (score associated with a descriptive topic may be as high as the score associated with a positive/negative topic). SLDA is able to extract qualitative and descriptive information from the reviews but is outperformed by LDA-C and LDA-R for all values of K.

Even if the best predictors are LDA-R and LDA-C, the most practical model is LDA-R-C for three main reasons. Performances of LDA-R-C (in terms of perplexity) are comparable to the best models. This model is the only model combining strongly consistent descriptive topics with consistent qualitative topics. LDA-R suffers from polluted descriptive topics while LDA-C does not infer any qualitative information. The profiles of movies θ c extracted with LDA-R-C are useful to compute a distance between movies-e.g., with the Kullback-Leibler divergence. As a result, one could recommend movies to a cold start user (i.e., user with an insufficient number of reviews) with LDA-R-C.

empirical discussion

In this section, we present the 8 most significant topics out of 100 topics inferred with LDA-R-C, SLDA and HFT in Table 3. The comparison of the topics is a premise to the analysis of words prediction. Indeed, for any LDA based algorithm, the probability of occurence of word w is given by ∑ k θ k φ k w , where θ represents the topic proportions of the current review and φ the inferred topic matrix. A topic vector φ k may be seen as the probabilities of occurence of words in a review generated from a single topic i.e., θ k = 1 and ∀j = k, θ j = 0.

Note that this section is an empirical discussion and that it does not replace a formal evaluation with real users that is planned for future works due to the complexity of the task (methodologically and business-wise). Table 3: 8 topics extracted with LDA-R-C, SLDA and HFT, K = 100 and the associated score for SLDA (see [START_REF] Mcauliffe | Supervised topic models[END_REF] for details).

LDA-R-C, 1 doc = 1 movie

Both LDA-R-C and SLDA extract qualitative topics, while we could not extract qualitative topics with HFT. The descriptive topics of the three methods are consistent around genres, sequels, actors or directors. We observe that the two methods LDA-R-C and SLDA extract similar topics (Table 3, topics T1 to T5 extracted with LDA-R-C are similar to topics T3 to T7 extracted with SLDA). From topics extracted with LDA-R-C, T1 is consistent around comedy, T2 around horror, T3 around animation, T4 around family, T5 around science-fiction. We can see the same consistency for topics T3 to T7 with SLDA. We observe that topics extracted with LDA-R-C share more top words with SLDA than with HFT. Indeed, the inference schemes of LDA-R-C and SLDA are close (i.e., variational EM), leading to similar topics. For instance, in Table 3, 6 out of 10 top words of topic T1 obtained with LDA-R-C also appear in the top of SLDA's topic T3. In the same way, topics T2 to T5 extracted with LDA-R-C are respectively closer to topics T4 to T7 extracted with SLDA than topics T4 to T7 extracted with HFT.

The difference between LDA-R-C and SLDA is that with LDA-R-C we obtain two distinct sets of words. A first set of words that illustrates the rating of the userscorresponding to topics Q1 and Q2 in Table 3-and a second set of words that the user would employ to describe a movie-topics T1 to T6 in Table 3. There is no such distinction in SLDA as the output is a single list of topics associated with a score. We notice that most of the extracted topics with SLDA are descriptivee.g., topics T3 to T8 in Table 3-and qualitative topics are associated to high scores (in absolute value)-e.g., topics T1 and T2 in Table 3. However, some descriptive topics are associated with high scores-e.g., topic T8 in Table 3-which makes difficult the distinction between qualitative and descriptive topics. As our model LDA-R-C extracts two sets of topics, there is no possible confusion between descriptive and qualitative topics. SLDA extracts a single list of topics and it is difficult nay impossible to automatically classify the topics as a qualitative or a descritpive.

In HFT, the parameters of LDA are linked to rating prediction parameters. As a result, the top words of the topics are still centered around generic genres, sequels, actors, directors but also contain words related to specific movies. For instance, in Table 3, the topic T4 extracted with HFT is centered around comedy and contains the words sandler, ferrell which are specific actor names and wedding which is a specific part of a plot. In the topic T5 extracted with HFT, centered around animation movies, we find the words wall-e, nemo which are specific titles and costner which is an actor name. The top words in both LDA-R-C and SLDA topics are more generic, leading to better predictions. Indeed, it is more likely that a review about a comedy movie contains funny than wedding, as only few comedy movies are related to a wedding.

related work

Several techniques have been proposed to extract information from raw text data. LDA [START_REF] Blei | Latent Dirichlet allocation[END_REF]] is a probabilistic model that infers hidden topics given a text corpus where each document of the corpus can then be represented as topic probabilities. The assumption behind LDA is that each document is generated from a mixture of topics and the model infers the hidden topics and the topic proportions of each document. For increasing consistency of inferred topics, a regularized version of LDA is proposed by [START_REF] Newman | Improving topic coherence with regularized topic models[END_REF]. This regularized version puts structured priors on the hidden topics. The parameters of the prior are pre-computed and consist in a "covariance" matrix which captures the short-range dependencies between words. This matrix has a regularization effect on the topics. The authors compare different priors. We increase the consistency of topics even further by aggregating reviews in LDA. [START_REF] Titov | Modeling online reviews with multi-grain topic models[END_REF] present a LDA based model with two types of topics; this model infers global topics that contain the different types of movie being reviewed, while the local topics extract the specific aspects of the movies. Instead, we chose to add qualitative information in the LDA topics, similar to the model proposed by [START_REF] Lin | Joint sentiment/topic model for sentiment analysis[END_REF] where a sentiment label is inferred for each document. The difference with our method is that we leverage the ratings found in movie reviews datasets to extract qualitative and descriptive information in separate topics.

In the rating prediction area, McAuley and [START_REF] Mcauley | Hidden factors and hidden topics: understanding rating dimensions with review text[END_REF] propose a transformation between LDA parameters and collaborative filtering parameters. Numerical ratings and words are processed in two separated models. Instead, we combine scores and words in the same LDA model. The model proposed by [START_REF] Mcauliffe | Supervised topic models[END_REF] infers parameters from both a text corpus and numerical ratings. The model is then able to predict a score given a new text. We use a similar approach to predict directly a list of words instead of numerical ratings. The model proposed by [START_REF] Ling | Ratings meet reviews, a combined approach to recommend[END_REF] combines LDA with matrix factorization to predict ratings. The main difference with our approach is that we distinguish qualitative and descriptive words in the topics while the topics inferred by [START_REF] Ling | Ratings meet reviews, a combined approach to recommend[END_REF] mix qualitative and descriptive words. Their model is also suited for rating prediction while we focus on word prediction.

conclusion

We have proposed six LDA-based models for word prediction from crowdsourced reviews and ratings. We show on an IMDB dataset that our LDA-R-C model combining movie profiling and ratings performs slightly better than the state of the art. It builds a set of descriptive topics that convey the features of moviese.g., genres, actors, directors-and contain the words the user would employ to describe a movie. It also builds a set of qualitative topics that convey the opinion of users about movies and contain the words that influence-positively or negatively-the final ratings of users.

While studying our LDA-U model, we came to the conclusion that it is difficult to build a user profile as each user writes reviews about very different movies expressing very different opinions.

For now, our models only extract two qualitative topics (positive and negative). We plan to build models that would extract a wider range of qualitative topics by reducing the observed ratings to a wider range of values than {+1, -1}.

The review prediction is currently based on single words prediction, which is not intuitive for users. We plan to predict readable sentences which would facilitate evaluation by users with A/B testing. Implemented with readable reviews or tags, our model could be integrated in a recommender to provide a personalized opinion summary to users for each content. In this section, we provide the full variational derivation of our model LDA-R-C presented Figure 5. Our objective is to maximize the likelihood of the observed corpus of documents W = {w 1 , . . . , w D }:

p(W |ω, {θ c d } d , η, { rd } d ) = D ∏ d=1 p(w d |ω, θ c d , η, rd ).
As this likelihood is intractable to compute, we maximize an approximation of the likelihood L(q) = ∑ D d=1 L d (q) over a variational family of distributions. Following [START_REF] Hoffman | Online learning for latent Dirichlet allocation[END_REF], we have for any w d ∈ W:

log p(w d |ω, θ c d , η, rd ) ≥E q [log p(w d , z d , m d , p d , φ, Ψ|ω, θ c d , η, rd )] -E q [log q(z d , m d , p d , φ, Ψ)] ≡L d (q),
where q represents the variational model. We choose the variational model q to be in the meanfield variational family:

q(z d , m d , p d , φ, Ψ) = q(φ|λ)q(Ψ|Λ)q(p d |π d ) N ∏ n=1 q(z d n |α d n )q(m d n |µ d n ),
with, ∀d = 1, . . . , D:

• q(φ k |λ k ) ∼Dirichlet(λ k ) with λ k ∈ R V and k = 1, . . . , K, • q(Ψ s |Λ s ) ∼Dirichlet(Λ s ) with Λ s ∈ R V and s ∈ {+1, -1}, • q(p d |π d ) ∼Dirichlet(π d ) with π d ∈ R 2 , • q(z d n |α d n ) ∼Multinomial(α d n ) with α d n ∈ R K , ∑ k α d n,k = 1 and n = 1, . . . , N, • q(m d n |µ d n ) ∼Multinomial(µ d n ) with µ d n ∈ R 2 , µ d n,1 + µ d n,2
= 1 and n = 1, . . . , N. We also have:

p(w d , z d , m d , p d , φ, Ψ|ω, θ c d , η, rd ) =p(φ|η)p(Ψ|η)p(p d |ω) × N ∏ n=1 p(w d n |φ, Ψ, z d n , r d , m d n )p(z d n |θ c d )p(m d n |p d ),
with, ∀d = 1, . . . , D:

• p(φ k |η) ∼Dirichlet(η1) with η ∈ R and k = 1, . . . , K,

• p(Ψ s |η) ∼Dirichlet(η1) with η ∈ R and s ∈ {+1, -1},

• p(p d |ω) ∼Dirichlet(ω) with ω ∈ R 2 , • p(z d n |θ c d ) ∼Multinomial(θ c d ) with θ c d ∈ R K , ∑ k θ c d k = 1 and n = 1, . . . , N, • p(m d n |p d ) ∼Multinomial(p d ) with p d ∈ R 2 , p d 1 + p d 2 = 1 and n = 1, . . . , N, • p(w d n |φ, Ψ, z d n , r d , m d n ) ∼Multinomial φ z d n 1[m d n = 0] + Ψ r d 1[m d n = 1] .
We then maximize L(q) by iteratively maximizing L(q) with respect to variational parameters λ, Λ, π, α, µ (E-step) then maximizing L(q) with respect to hyperparameters ω, η (M-step).

2.A.1 Variational E-step

For the E-step, we maximize L(q) with respect to variational parameters λ, Λ, π, α, µ by alternatively setting the gradient of L(q) with respect to each paramater to zero. It gives the following updates for the variational parameters, for n = 1, . . . , N, k = 1, . . . , K, i = 1, 2 and s ∈ {-1, +1}:

                                       α d n,k ∝ θ c d k exp µ d n,1 ψ(λ k w d n ) -ψ(∑ j λ k j ) , π d i = ω i + ∑ N n=1 µ d n,i , µ d n,1 ∝ exp ψ(π d 1 ) + ∑ K k=1 ψ(λ k w d n ) -ψ(∑ j λ k j ) , µ d n,2 ∝ exp ψ(π d 2 ) + ∑ s∈{-1,+1} ψ(Λ s w d n ) -ψ(∑ j Λ s j ) , λ k v = η + D ∑ d=1 ∑ N d n=1 µ d n,1 α d n,k 1[w d n = v], Λ s v = η + ∑ d:r d =s ∑ N d n=1 µ d n,2 1[w d n = v].
ψ is the digamma function: ψ(x) = d dx ln Γ(x).

2.A.2 Variational M-step

For the M-step, we maximize L(q) with respect to the hyperparameters ω, η. We use the Newton method for each parameter, using the same scheme than in LDA [START_REF] Blei | Latent Dirichlet allocation[END_REF]. We have the following derivatives for ω:

       ∂ ∂ω i L(q) = D ψ(∑ j ω j ) -ψ(ω i ) + ∑ D d=1 ψ(π d i ), -ψ(∑ j π d j ) ∂ 2 ∂ω i ∂ω j L(q) = Dψ (∑ l ω l ) -1[i = j]Dψ (ω i ).
We have the following derivatives for η

                     ∂ ∂η L(q) = (K + 2)V (ψ(Vη) -ψ(η)) + V ∑ v=1 K ∑ k=1 ψ(λ k v ) + ∑ s∈{-1,+1} ψ(Λ s v ) -V K ∑ k=1 ψ( V ∑ v=1 λ k v ) + ∑ s∈{-1,+1} ψ( V ∑ v=1 Λ s v ) , ∂ 2 ∂η 2 L(q) = (K + 2)V (Vψ (Vη) -ψ (η)) .
We maximize L(q) with respect to ω by doing iterations of Newton steps until convergence:

ω (t+1) = ω (t) -H -1 ∇ ω (t) L(q),
where H is the Hessian H = ∇ 2 ω (t) L(q). We then maximize L(q) with respect to η by again doing iterations of Newton steps until convergence:

η (t+1) = η (t) - ∂ 2 (∂η (t) ) 2 L(q) -1 ∂ ∂η (t) L(q) . 3 O N L I N E B U T A C C U R AT E I N F E R E N C E F O R L AT E N T VA R I A B L E M O D E L S W I T H L O C A L G I B B S S A M P L I N G
Probabilistic graphical models provide general modelling tools for complex data, where it is natural to include assumptions on the data generating process by adding latent variables in the model. Such latent variable models are adapted to a wide variety of unsupervised learning tasks [START_REF] Koller | Probabilistic graphical models: principles and techniques[END_REF]Friedman, 2009, Murphy, 2012]. In this chapter, we focus on parameter inference in such latent variable models where the main operation needed for the standard expectationmaximization (EM) algorithm is intractable, namely dealing with conditional distributions over latent variables given the observed variables; latent Dirichlet allocation (LDA) [START_REF] Blei | Latent Dirichlet allocation[END_REF] is our motivating example, but many hierarchical models exhibit this behavior, e.g., ICA with heavy-tailed priors. For such models, there exist two main classes of methods to deal efficiently with intractable exact inference in large-scale situations: sampling methods or variational methods.

Sampling methods can handle arbitrary distributions and lead to simple inference algorithms while converging to exact inference. However it may be slow to converge and non scalable to big datasets in practice. In particular, although efficient implementations have been developed, for example for LDA [START_REF] Zhao | SAME but different: Fast and high-quality Gibbs parameter estimation[END_REF][START_REF] Yan | Parallel inference for latent Dirichlet allocation on graphics processing units[END_REF], MCMC methods may not deal efficiently yet with continuous streams of data for our general class of models.

On the other hand, variational inference builds an approximate model for the posterior distribution over latent variables-called variational-and infer parameters of the true model through this approximation. The fitting of this variational distribution is formulated as an optimization problem where efficient (deterministic) iterative techniques such as gradient or coordinate ascent methods apply. This approach leads to scalable inference schemes [START_REF] Hoffman | Online learning for latent Dirichlet allocation[END_REF], but due to approximations, there always remains a gap between the variational posterior and the true posterior distribution, inherent to algorithm design, and that will not vanish when the number of samples and the number of iterations increase.

Beyond the choice of approximate inference techniques for latent variables, parameter inference may be treated either from the frequentist point of view, e.g., using maximum likelihood inference, or a Bayesian point of view, where the posterior distribution of the parameter given the observed data is approximated. With massive numbers of observations, this posterior distribution is typically peaked around the maximum likelihood estimate, and the two inference frameworks should not differ much [ [START_REF] Van Der | Asymptotic Statistics[END_REF].

In this chapter, we focus on methods that make a single pass over the data to estimate parameters. We make the following contributions:

1. We review and compare existing methods for online inference for latent variable models from a non-canonical exponential family in Section 3.1, and draw explicit links between several previously proposed frequentist or Bayesian methods. Given the large number of existing methods, our unifying framework allows one to understand differences and similarities between all of them.

2. We propose in Section 3.2 a novel inference method for the frequentist estimation of parameters, that adapts MCMC methods to online inference of latent variable models with the proper use of "local" Gibbs sampling.

In our online scheme, we apply Gibbs sampling to the current observation, which is "local", as opposed to "global" batch schemes where Gibbs sampling is applied to the entire dataset.

3. After formulating LDA as a non-canonical exponential family in Section 3.3, we provide an extensive set of experiments in Section 3.5, where our new approach outperforms all previously proposed methods. In particular, using Gibbs sampling for latent variable inference is superior to variational inference in terms of test log-likelihoods. Moreover, Bayesian inference through variational methods perform poorly, sometimes leading to worse fits with latent variables of higher dimensionality.

This work is under revision at JMLR.

online em

We consider an exponential family model on random variables (X, h) with parameter η ∈ E ⊆ R d and with density [START_REF] Lehmann | Theory of point estimation[END_REF]]:

p(X, h|η) = a(X, h) exp φ(η), S(X, h) -ψ(η) . (1)
We assume that h is hidden and X is observed. The vector φ(η) ∈ R d represents the natural parameter, S(X, h) ∈ R d is the vector of sufficient statistics, ψ(η) is the log-normalizer, and a(X, h) is the underlying base measure. We consider a non-canonical family as in many models (such as LDA), the natural parameter φ(η) does not coincide with the model parameter η, that is, φ(η) ≡ η; we however assume that φ is injective. We consider N i.i.d. observations (X i ) i=1,...,N from a distribution t(X), which may be of the form P(X|η * ) = h p(X, h|η * )dh for our model above and a certain η * ∈ E (well-specified model) or not (misspecified model). Our goal is to obtain a predictive density r(X) built from the data and using the model defined in (1), with the maximal expected log-likelihood E t(X) log r(X).

Maximum likelihood estimation

In the frequentist perpective, the predictive distribution r(X) is of the form p(X| η), for a well-defined estimator η ∈ E . The most common method is the EM algorithm [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF], which is an algorithm that aims at maximizing the likelihood of the observed data, that is,

max η∈E N ∑ i=1 log p(X i |η).
(2)

More precisely, the EM algorithm is an iterative process to find the maximum likelihood (ML) estimate given observations (X i ) i=1,...,N associated to hidden variables (h i ) i=1,...,N . It may be seen as the iterative construction of lower bounds of the log-likelihood function [START_REF] Bishop | Pattern Recognition and Machine Learning[END_REF]. In the exponential family setting (1), we have, by Jensen's inequality, given the model defined by η ∈ E from the previous iteration, and for any parameter η ∈ E :

log p(X i |η) = log p(X i , h i |η)dh i ≥ p(h i |X i , η ) log p(X i , h i |η) p(h i |X i , η ) dh i = p(h i |X i , η ) ( φ(η), S(X i , h i ) -ψ(η)) dh i -C i (η ) = φ(η), E p(h i |X i ,η ) [S(X i , h i )] -ψ(η) -C i (η ),
for a certain constant C i (η ), with equality if η = η. Thus, EM-type algorithms build locally tight lower bounds of the log-likelihood in (2), which are equal to φ(η), ∑ N i=1 s i -Nψ(η) + cst, for appropriate values of s i ∈ R d obtained by computing conditional expectations with the distribution of h i given X i for the current model defined by η (E-step), i.e.,

s i = E p(h i |X i ,η ) [S(X i , h i )].
Then this function of η is maximized to obtain the next iterate (M-step). In standard EM applications, these two steps are assumed tractable. In Section 3.2, we will only assume that the M-step is tractable while the E-step is intractable.

Standard EM will consider

s i = E p(h i |X i ,η ) [S(X i , h)]
for the previous value of the parameter η for all i, and hence, at every iteration, all observations X i , i = 1, . . . , N are considered for latent variable inference, leading to a slow "batch" algorithm for large N.

Incremental EM [START_REF] Neal | A view of the EM algorithm that justifies incremental, sparse, and other variants[END_REF]] will only update a single element s i coming from a single observation X i and update the corresponding part of the sum ∑ N j=1 s j without changing other elements. In the extreme case where a single pass over the data is made, then the M-step at iteration i maximizes

φ(η), i ∑ j=1 E p(h j |X j ,η j-1 ) S(X j , h j ) -iψ(η),
with respect to η. In the next section, we provide a (known) other interpretation of this algorithm.

Stochastic approximation

Given our frequentist objective E t(X) log p(X|η) to maximize defined as an expectation, we may consider two forms of stochastic approximation [START_REF] Kushner | Stochastic approximation and recursive algorithms and applications[END_REF], where observations X i sampled from t(X) are processed only once. The first one is stochastic gradient ascent, of the form

η i = η i-1 + ρ i ∂ log p(X i |η) ∂η ,
or appropriately renormalized version thereof, i.e.,

η i = η i-1 + ρ i H -1 ∂ log p(X i |η)
∂η , with several possibilities for the d × d matrix H, such as the negative Hessian of the partial or the full log-likelihood, or the negative covariance matrix of gradients, which can be seen as versions of natural gradient-see [START_REF] Titterington | Recursive parameter estimation using incomplete data[END_REF], [START_REF] Delyon | Convergence of a stochastic approximation version of the EM algorithm[END_REF], [START_REF] Cappé | Online EM algorithm for latent data models[END_REF]. This either leads to slow convergence (without H) or expensive iterations (with H), with the added difficulty of choosing a proper scale and decay for the step-size ρ i .

A key insight of [START_REF] Delyon | Convergence of a stochastic approximation version of the EM algorithm[END_REF], [START_REF] Cappé | Online EM algorithm for latent data models[END_REF] is to use a different formulation of stochastic approximation, not explicitly based on stochastic gradient ascent. They consider the stationary equation E t(X)

∂ log p(X|η) ∂η
= 0 and expand it using the exponential family model (1) as follows:

∂ log p(X|η) ∂η = ∂ log p(X, h|η)dh ∂η = φ (η)E p(h|X,η) [S(X, h)] -ψ (η).
Given standard properties of the exponential family, namely

ψ (η) = φ (η)E p(h,X|η) [S(X, h)] 1 ,
and assuming invertibility of φ (η), this leads to the following stationary equation:

E t(X) E p(h|X,η) [S(X, h)] = E p(h,X|η) [S(X, h)] . 1 Proof: Given (1), X,h p(X, h|η)d(X, h) = 1 ⇒ ψ(η) = log X,h a(X, h)e φ(η),S(X,h) d(X, h) .
We then derive this identity with respect to η, which gives:

ψ (η) = X,h φ (η)S(X, h)a(X, h)e φ(η),S(X,h) d(X, h) X,h a(X, h)e φ(η),S(X,h) d(X, h) = φ (η) X,h S(X, h)a(X, h)e φ(η),S(X,h) d(X, h) e ψ(η) = φ (η) X,h S(X, h)p(X, h|η)d(X, h) = φ (η)E p(h,X|η) [S(X, h)] .
This stationary equation states that at optimality the sufficient statitics have the same expectation for the full model p(h, X|η) and the joint "model/data" distribution t(X)p(h|X, η).

Another important insight of [START_REF] Delyon | Convergence of a stochastic approximation version of the EM algorithm[END_REF], [START_REF] Cappé | Online EM algorithm for latent data models[END_REF] is to consider the change of variable s(η) = E p(h,X|η) [S(X, h)] on sufficient statis- tics, which is equivalent to

η = η * (s) ∈ arg max φ(η), s -ψ(η),
(which is the usual M-step update). See [START_REF] Cappé | Online EM algorithm for latent data models[END_REF] for detailed assumptions allowing this inversion. We may then rewrite the equation above as

E t(X) E p(h|X,η * (s)) [S(X, h)] = s.
This is a non-linear equation in s ∈ R d , with an expectation with respect to t(X) which is only accessed through i.i.d. samples X i , and thus a good candidate for the Robbins-Monro algorithm to solve stationary equations (and not to minimize functions) [START_REF] Kushner | Stochastic approximation and recursive algorithms and applications[END_REF], which takes the simple form:

s i = s i-1 -ρ i s i-1 -E p(h i |X i ,η * (s i-1 )) [S(X i , h i )] ,
with a step-size ρ i . It may be rewritten as

s i = (1 -ρ i )s i-1 + ρ i E p(h i |X i ,η i-1 ) [S(X i , h i )] η i = η * (s i ), (3)
which has a particularly simple interpretation: instead of computing the expectation for all observations as in full EM, this stochastic version keeps tracks of old sufficient statistics through the variable s i-1 which is updated towards the current value

E p(h i |X i ,η i-1 ) [S(X i , h i )]
. The parameter η is then updated to the value η * (s i ). [START_REF] Cappé | Online EM algorithm for latent data models[END_REF] show that this update is asymptotically equivalent to the natural gradient update with three main improvements: (a) no matrix inversion is needed, (b) the algorithm may be accelerated through Polyak-Ruppert averaging [START_REF] Polyak | Acceleration of stochastic approximation by averaging[END_REF], i.e., using the average ηN of all η i instead of the last iterate η N , and (c) the step-size is particularly simple to set, as we are taking convex combinations of sufficient statistics, and hence only the decay rate of ρ i has to be chosen, i.e., of the form ρ i = i -κ , for κ ∈ (0, 1], without any multiplicative constant.

incremental view. For the specific stepsize ρ i = 1/i, the online EM algorithm (3) corresponds exactly to the incremental EM presented above [START_REF] Neal | A view of the EM algorithm that justifies incremental, sparse, and other variants[END_REF]], as then

s i = 1 i i ∑ j=1 E p(h j |X j ,η j-1 ) [S(X j , h j )].
See [START_REF]Incremental majorization-minimization optimization with application to large-scale machine learning[END_REF] for a detailed convergence analysis of incremental algorithms, in particular showing that step-sizes larger than 1/i are preferable (we observe this in practice in Section 3.5).

monte carlo methods. There exist alternative methods to the EM algorithm based on Monte Carlo sampling to compute the maximum likelihood. For instance, the Monte Carlo EM method (MCEM) [START_REF] Wei | A Monte Carlo implementation of the EM algorithm and the poor man's data augmentation algorithms[END_REF]] is a general Bayesian approach (i.e., η is a random variable) to approximate the maximizer of the posterior distribution p(η|X, h) with Monte Carlo sampling. More precisely, in the MCEM method, similarly to EM, a surrogate function of the log-likelihood is used, given by:

Q(η, η t ) = h log[p(η|X, h)]p(h|X, η t )dh.
The function Q is approximated by sampling the latent variables h from the current conditional p(h|X, η t ):

Q(η, η t ) = P ∑ i=1 log p(η|X, h i ),
where (h i ) i=1,...,P are the samples drawn from the conditional p(h|X, η t ). The approximation Q is then maximized with respect to η. Note that this method is a bacth method, namely, samples are drawn over all the dataset. Other sequential Monte Carlo methods (SMC) apply particle methods to the approximation of the posterior p(η|X, h) [START_REF] Kantas | On particle methods for parameter estimation in state-space models[END_REF].

The two Monte Carlo methods mentionned above also consist in sufficient statistics updates for the class of models considered here.

online em with intractable models

The online EM updates in (3) lead to a scalable algorithm for optimization when the local E-step is tractable. However, in many latent variable models-e.g., LDA, hierarchical Dirichlet processes [START_REF] Teh | Hierarchical Dirichlet processes[END_REF], or ICA [START_REF] Hyvärinen | Independent component analysis[END_REF]-it is intractable to compute the conditional expectation E p(h|X,η) [S(X, h)].

Following [START_REF] Rohde | Online maximum-likelihood estimation for latent factor models[END_REF], we propose to leverage the scalability of online EM updates (3) and locally approximate the conditional distribution p(h|X, η) in the case this distribution is intractable to compute. We will however consider different approximate methods, namely Gibbs sampling or variational inference. Our method is thus restricted to models where the hidden variable h may naturally be splitted in two or more groups of simple random variables. Our algorithm is described in Algorithm 1 and may be instantiated with two approximate inference schemes which we now describe.

Algorithm 1 Gibbs / Variational online EM

Input: η 0 , s 0 , κ ∈ (0, 1]. for i = 1, . . . , N do • Collect observation X i , • Estimate p(h i |X i , η i-1
) with sampling (G-OEM) or variational inference (V-OEM),

• Apply (3) to sufficient statistics s i and parameter η i with ρ i = 1/i κ , end for Output: ηN = 1 N ∑ N i=1 η i or η N .

Variational inference: V-OEM

While variational inference had been considered before for online estimation of latent variable models, in particular for LDA for incremental EM [START_REF] Sato | Deterministic single-pass algorithm for LDA[END_REF], using it for online EM (which is empirically faster) had not been proposed and allows us to use bigger step-sizes (e.g., κ = 1/2). These methods are based on maximizing the negative variational "free-energy"

E q(h|η) log p(X, h|η) q(h|η) , (4)
with respect to q(h|η) having a certain factorized form adapted to the model at hand, so that efficient coordinate ascent may be used. See, e.g., [START_REF] Hoffman | Online learning for latent Dirichlet allocation[END_REF]. We now denote online EM with variational approximation of the conditional distribution p(h|X, η) as V-OEM.

Sampling methods: G-OEM

MCMC methods to approximate the conditional distribution of latent variables with online EM have been considered by [START_REF] Rohde | Online maximum-likelihood estimation for latent factor models[END_REF], who apply locally the Metropolis-Hasting (M-H) algorithm [START_REF] Metropolis | Equation of state calculations by fast computing machines[END_REF][START_REF] Hastings | Monte Carlo sampling methods using Markov chains and their applications[END_REF], and show results on simple synthetic datasets. While Gibbs sampling is widely used for many models such as LDA due to its simplicity and lack of external parameters, M-H requires a proper proposal distribution with frequent acceptance and fast mixing, which may be hard to find in high dimensions. We provide a different simpler local scheme based on Gibbs sampling (thus adapted to a wide variety of models), and propose a thorough favorable comparison on synthetic and real datasets with existing methods. The Gibbs sampler is used to estimate posterior distributions by alternatively sampling parts of the variables given the other ones [see Casella and George, 1992, for details], and is standard and easy to use in many common latent variable models. In the following, the online EM method with Gibbs estimation of the conditional distribution p(h|X, η) is denoted G-OEM.

As mentioned above, the online EM updates correspond to a stochastic approximation algorithm and thus are robust to random noise in the local E-step. As a result, our sampling method is particularly adapted as it is a random estimate of the E-step-see a theoretical analysis by [START_REF] Rohde | Online maximum-likelihood estimation for latent factor models[END_REF], and thus we only need to compute a few Gibbs samples for the estimation of p(h|X i , η i-1 ). A key contribution of our work is to reuse sampling techniques that have proved competitive in the batch set-up and to compare them to existing variational approaches.

"Boosted" inference

As the variational and MCMC estimations of p(h|X i , η i-1 ) are done with iterative methods, we can boost the inference of Algorithm 1 by applying the update in the parameter η in (3) after each iteration of the estimation of p(h|X i , η i-1 ). In the context of LDA, this was proposed by [START_REF] Sato | Deterministic single-pass algorithm for LDA[END_REF] for incremental EM and we extend it to all versions of online EM. With this boost, we expect that the global parameters η converge faster, as they are updated more often. In the following, we denote by G-OEM++ (resp. V-OEM++) the method G-OEM (resp. V-OEM) augmented with this boost.

Variational Bayesian estimation

In the Bayesian perspective where η is seen as a random variable, we either consider a distribution based on model averaging, e.g., r(X) = p(X|η)q(η)dη where q(η) ∝ ∏ N i=1 p(X i |η)p(η) is the posterior distribution, or

r(X) = p(X| η),
where η is the summary (e.g., the mean) of the posterior distribution q(η), or of an approximation, which is usually done in practice [see, e.g., [START_REF] Hoffman | Structured stochastic variational inference[END_REF] and is asymptotically equivalent when N tends to infinity.

The main problem is that, even when the conditional distribution of latent variables is tractable, it is intractable to manipulate the joint posterior distribution over the latent variables h 1 , . . . , h N , and the parameter η. Variational inference techniques consider an approximation where hidden variables are independent of the parameter η, i.e., such that

p(η, h 1 , . . . , h N |X 1 , . . . , X N ) ≈ q(η) N ∏ i=1 q(h i ),
which corresponds to the maximization of the following lower bound-called Evidence Lower BOund (ELBO)-on the log-likelihood log p(X 1 , . . . , X n ) [START_REF] Bishop | Pattern Recognition and Machine Learning[END_REF]:

q(η) N ∏ i=1 q(h i ) log p(η) ∏ n i=1 p(X i , h i |η) q(η) ∏ N i=1 q(h i ) dηdh 1 • • • dh N .
The key insight from [START_REF] Hoffman | Online learning for latent Dirichlet allocation[END_REF], [START_REF] Broderick | Streaming variational Bayes[END_REF] is to consider the variational distribution q(η) as the global parameter, and the cost function above as a sum of local functions that depend on the data X i and the variational distribution q(h i ). Once the local variational distribution q(h i ) is maximized out, the sum structure may be leveraged in similar ways than for frequentist estimation, either by direct (natural) stochastic gradient [START_REF] Hoffman | Online learning for latent Dirichlet allocation[END_REF] or incremental techniques that accumulate sufficient statistics [START_REF] Broderick | Streaming variational Bayes[END_REF]. A nice feature of these techniques is that they extend directly to models with intractable latent variable inference, by making additional assumptions on q(h i ) (see for example the LDA situation in Section 3.3).

In terms of actual updates, they are similar to online EM in Section 3.2.1, with a few changes, but which turn out to lead to significant differences in practice. The similarity comes from the expansion of the ELBO as

E q(η) N ∑ i=1 E q(h i ) log p(X i , h i |η) q(h i ) + E q(η) log p(η) q(η) .
The left hand side has the same structure than the variational EM update in (4), thus leading to similar updates, while the right hand side corresponds to the "Bayesian layer", and the maximization with respect to q(η) is similar to the M-step of EM (where η is seen as a parameter).

Like online EM techniques presented in Section 3.2, approximate inference for latent variable is used, but, when using Bayesian stochastic variational inference techniques, there are two additional sources of inefficiencies: (a) extra assumptions regarding the independence of η and h 1 , . . . , h N , and (b) the lack of explicit formulation as the minimization of an expectation, which prevents the simple use of the most efficient stochastic approximation techniques (together with their guarantees). While (b) can simply slow down the algorithm, (a) may lead to results which are far away from exact inference, even for large numbers of samples (see examples in Section 3.5).

Beyond variational inference, Gibbs sampling has been recently considered by [START_REF] Gao | Streaming Gibbs sampling for LDA model[END_REF]: their method consists in sampling hidden variables for the current document given current parameters, but (a) only some of the new parameters are updated by incrementally aggregating the samples of the current document with current parameters, and (b) the method is slower than G-OEM (see Section 3.5).

application to lda

LDA [START_REF] Blei | Latent Dirichlet allocation[END_REF]] is a probabilistic model that infers hidden topics given a text corpus where each document of the corpus can be represented as topic probabilities. In particular, the assumption behind LDA is that each document is generated from a mixture of topics and the model infers the hidden topics and the topic proportions of each document. In practice, inference is done using Bayesian variational EM [START_REF] Blei | Latent Dirichlet allocation[END_REF], Gibbs sampling [Griffiths andSteyvers, 2004, Wallach, 2006] or stochastic variational inference [START_REF] Hoffman | Online learning for latent Dirichlet allocation[END_REF][START_REF] Broderick | Streaming variational Bayes[END_REF][START_REF] Sato | Deterministic single-pass algorithm for LDA[END_REF]. hierarchical probabilistic model. Let C = {X 1 , . . . , X D } be a corpus of D documents, V the number of words in our vocabulary and K the number of latent topics in the corpus. Each topic β k corresponds to a discrete distribution on the V words (that is an element of the simplex in V dimensions). A hidden discrete distribution θ i over the K topics (that is an element of the simplex in K dimensions) is attached to each document X i . As detailed in Chapter 1, LDA is a generative model applied to a corpus of text documents which assumes that each word of the i th document X i is generated as follows:

• Choose θ i ∼ Dirichlet(α),
• For each word x n ∈ X i = x 1 , . . . , x N X i :

-Choose a topic z n ∼ Multinomial(θ i ),

-Choose a word x n ∼ Multinomial(β z n ).

In our settings, an observation is a document

X i = (x 1 , . . . , x N X i ) where for all 1 ≤ n ≤ N X i , x n ∈ {0, 1} V and ∑ V v=1 x nv = 1. Each observation X i is associated with the hidden variables h i , with h i ≡ (Z i = (z 1 , . . . , z N X i
), θ i ). The vector θ i represents the topic proportions of document X i and Z i is the vector of topic assignments of each word of X i . The variable h i is local, i.e., attached to one observation X i . The parameters of the model are global, represented by η ≡ (β, α), where β represents the topic matrix and α represents the Dirichlet prior on topic proportions.

We derive the LDA model in Section 3.3.1 to find φ, S, ψ and a such that the joint probability p(Z, θ|X, α, β) is in a non-canonical exponential family (1).

We may then readily apply all algorithms from Section 3.2 by estimating the conditional expectation E Z,θ|X,α,β [S(X, Z, θ)] with either variational inference (V-OEM) or Gibbs sampling (G-OEM). See Sections 3.3.2 and 3.3.3 for online EM derivations. Note that the key difficulty of LDA is the presence of two interacting hidden variables Z and θ.

LDA and exponential families

An observation X is a document of length N X , where X = (x 1 , . . . , x N X ), each word is represented by x n ∈ {0, 1} V with ∑ V v=1 x nv = 1. Our corpus C is a set of D observations C = (X 1 , . . . , X D ). For each document X i a hidden variable θ i is associated, corresponding to the topic distribution of document X i . For each word x n of document X i a hidden variable z n ∈ {0, 1} K is attached, corresponding to the topic assignment of word x n . We want to find φ, S, ψ and a such that, the joint probability is in the exponential family (1):

p(X, Z, θ|β, α) = a(X, Z, θ) exp [ φ(β, α), S(X, Z, θ) -ψ(β, α)] ,
given an observation X and hidden variables Z and θ. For the LDA model, we have:

p(X, Z, θ|β, α) = N X ∏ n=1 p(x n |z n , β)p(z n |θ)p(θ|α) = N X ∏ n=1 K ∏ k=1 V ∏ v=1 (β k v ) x nv θ k z nk p(θ|α),
which we can expand as:

p(X, Z, θ|β, α) = exp N X ∑ n=1 K ∑ k=1 z nk log θ k × exp N X ∑ n=1 K ∑ k=1 V ∑ v=1 x nv z nk log β k v × exp K ∑ k=1 (α k -1) log θ k + B(α) , with B(α) = log Γ ∑ K i=1 α i -∑ K i=1 log[Γ(α i )],
where Γ is the gamma function. We deduce the non-canonical exponential family setting φ, S, ψ a:

S(X, Z, θ) =     S 1 kv ≡ N X ∑ n=1 z nk x nv kv S 2 k ≡ [log θ k ] k     , (5)
φ(β, α) =   φ 1 kv ≡ log β k v kv φ 2 k ≡ [α k ] k   , (6)
with

S 1 , φ 1 ∈ R K×V and S 2 , φ 2 ∈ R K , ψ(β, α) = K ∑ i=1 log[Γ(α i )] -log Γ K ∑ i=1 α i , (7)
and

a(X, Z, θ) = exp K ∑ k=1 N X ∑ n=1 z nk -1 log θ k .
The one-to one mapping between the sufficient statistics s = ( s 1 s 2 ) and (β, α) is defined by:

(β, α) * [s] =      arg max β≥0,α≥0 φ(β, α), s -ψ(β, α) s.t. β 1 = 1,
where 1 denotes the vector whose all entries equal 1. The objective function above φ(β, α), sψ(β, α) is concave in β from the concavity of log and concave in any α k for α ≥ 0 as the function B(α) is concave as the negative log-partition of the Dirichlet distribution. We use the Lagrangian method for β:

L(β, λ) = K ∑ k=1 V ∑ v=1 s 1 kv log β k v + λ (β 1 -1),
with λ ∈ R K . The derivative of L is set to zero when:

∀(k, v), s 1 kv β k v + λ k = 0 ⇒ λ k = - V ∑ v=1 s 1 kv , as ∑ V v=1 β k v = 1.
We then have (β * (s)) kv = s 1 kv /∑ j s 1 kj . This mapping satisfies the constraint β ≥ 0 because for any observation X and hidden variable Z, we have S 1 (X, Z) kv ≥ 0. This comes from ( 5) and the fact that ∀(n, k, v), (x nv , z nk ) ∈ {0, 1} 2 . We find the condition on α by setting the derivatives to 0, which gives ∀k ∈ 1, K :

s 2 k -Ψ([α * (s)] k ) + Ψ K ∑ i=1 [α * (s)] i = 0, where Ψ : x → ∂ ∂x [log Γ](x) is the digamma function. Finally, (α * (s), β * (s)) satis- fies ∀(k, v):        (β * (s)) kv ≡ s 1 kv ∑ j s 1 kj kv Ψ([α * (s)] k ) -Ψ K ∑ i=1 [α * (s)] i = s 2 k . ( 8
)
The parameter α * is usually estimated with gradient ascent [START_REF] Blei | Latent Dirichlet allocation[END_REF][START_REF] Hoffman | Online learning for latent Dirichlet allocation[END_REF]. We can also estimate α with the fixed point iteration [START_REF] Minka | Estimating a Dirichlet distribution[END_REF] which consists in repeating the following update until convergence:

α new k = Ψ -1 Ψ ∑ K i=1 α old i + s 2 k .
We use the fixed point iteration to estimate α * as it is more stable in practice. We study different updates for α in Appendix 3.8.

We can now apply Algorithm 1 to LDA. The only missing step is the estimation of the conditional expectation E Z,θ|X,α t ,β t [S(X, Z, θ)], with X = (x 1 , . . . , x N X ) and Z = (z 1 , . . . , z N X ). We explain how to approximate this expectation with variational inference and Gibbs sampling.

Variational online EM applied to LDA (V-OEM)

In this section we explain how to approximate E Z,θ|X,α t ,β t [S(X, Z, θ)] with variational inference, in the frequentist setting. See [START_REF] Hoffman | Online learning for latent Dirichlet allocation[END_REF] for detailed derivations of variational inference for LDA in the Bayesian setting (from which the updates in the frequentist setting may be easily obtained). The idea behind variational inference is to maximize the Evidence Lower BOund (ELBO), a lower bound on the probability of the observations: p(X) ≥ ELBO(X, p, q), where q represents the variational model. In the case of LDA, the variational model is often set with a Dirichlet(γ) prior on θ and a multinomial prior on Z [START_REF] Hoffman | Online learning for latent Dirichlet allocation[END_REF]:

q(Z, θ) = q(θ|γ) N X ∏ n=1 q(z n |ζ n ). ( 9
)
We then maximize the ELBO with respect to γ and ζ, which is equivalent to minimizing the Kullback-Leibler (KL) divergence between the variational posterior and the true posterior:

max γ,ζ ELBO(X, p, q) ⇔ min γ,ζ KL[p(Z, θ|X)||q(θ, Z)]. (10)
We solve this problem with block coordinate descent, which leads to iteratively updating γ and ζ as follows:

ζ nk ∝ V ∏ v=1 β k v x nv exp [Ψ(γ k )] , (11)
γ k = α k + ∑ N X n=1 ζ nk . ( 12
)
We then approximate E Z,θ|X,α t ,β t [S(X, Z, θ)] with the variational posterior. Given (5) and ( 9), we have:

E p(Z,θ|X) [S(X, Z, θ)] ≈ E q(Z,θ) [S(X, Z, θ)] =      ∑ N X t+1 n=1 ζ nk x nv kv Ψ(γ k ) -Ψ ∑ K j=1 γ j k      . ( 13
)
The variational approximation of E p(Z,θ|X) [S(X, Z, θ)] is then done in two steps:

1. Iteratively update ζ with (11) and γ with (12),

2. E p(Z,θ|X) [S(X, Z, θ)] ← E q(Z,θ|γ,ζ) [S(X, Z, θ)] with equation (13).
As γ and ζ are set to minimize the distance between the variational posterior and the true posterior (10) we expect that this approximation is close to the true expectation. However, as the variational model is a simplified version of the true model, there always remains a gap between the true posterior and the variational posterior.

Gibbs online EM applied to LDA (G-OEM)

In this section we explain how to approximate E Z,θ|X,α t ,β t [S(X, Z, θ)] with Gibbs sampling.

expectation of S 1 . Given (5), we have ∀k ∈ 1, K , ∀v ∈ 1, V :

E Z,θ|X,α,β (S 1 (X, Z)) kv = E Z,θ|X,α,β N X ∑ n=1 z nk x nv = N X ∑ n=1 Z,θ z nk x nv p(z n , θ|X, β, α)dθdz = N X ∑ n=1
x nv p(z nk = 1|X, β, α).

We see that we only need the probability of z, and can thus use collapsed Gibbs sampling [START_REF] Griffiths | Finding scientific topics[END_REF]. We have, following Bayes rule:

p(z nk = 1|z -n , X, β, α) ∝ p(x n |z nk = 1, β)p(z nk = 1|z -n , α),
where z -n is the topic assignments except index n. In the LDA model, each word x n is drawn from a multinomial with parameter β z n , which gives:

p(x n |z nk = 1, β) = V ∑ v=1 x nv β k v .
In the following, we use the notation β k x n ≡ ∑ V v=1 x nv β k v for the sake of simplicty. We then use the fact that the topic proportions θ has a Dirichlet(α) prior, which implies that Z|α follows a Dirichlet-multinomial distribution (or multivariate Pólya distribution). As a result, the conditional distribution is:

p(z nk = 1|z -n , α) = N -n,k + α k (N X -1) + ∑ j α j ,
with N -n,k the number of words assigned to topic k in the current document, except index n. Finally, we have the following relation [START_REF] Griffiths | Finding scientific topics[END_REF]:

p(z nk = 1|z -n , X, β, α) ∝ β k x n × N -n,k + α k (N X -1) + ∑ j α j . ( 14
)
We estimate p(z nk = 1|X, β, α) with Gibbs sampling by iteratively sampling topic assignments z n for each word, as detailed in Algorithm 2. We average over the last quarter of samples to reduce noise in the final output. We then incorporate the output in Algorithm 1.

expectation of S 2 . Given (5), we also have ∀k ∈ 1, K , ∀v ∈ 1, V :

E Z,θ|X,α,β [(S 2 (X, Z)) k ] = E Z,θ|X,α,β [log θ k ].
On the one hand, we have:

p(Z, θ|X, β, α) = p(Z|θ, X, β, α)p(θ|X, β, α) = C(α) K ∏ k=1 θ ∑ N X n=1 z nk +α k -1 k , with C(α) = Γ(∑ K i=1 α i ) ∏ K i=1 Γ(α i )
. On the other hand:

p(Z, θ|X, β, α) ∝ p(θ|Z, α)p(Z|X, β).
We deduce from the two identities:

p(θ|Z, α) ∝ K ∏ k=1 θ ∑ N X n=1 z nk +α k -1 k ⇒ θ|Z, α ∼ Dirichlet α + ∑ N X n=1 z n .
Finally, the expectation is:

E Z,θ|X,α,β [(S 2 (X, Z)) k ] =E Z,θ|X,α,β [log θ k ] =E Z|X,β,α E θ|Z,α [log θ k ] =E Z|X,β,α Ψ [α(s)] k + N X ∑ n=1 z nk -Ψ K ∑ i=1 [α(s)] i + N X , as the distribution of θ|Z, α is Dirichlet α + N X ∑ n=1 z n .
We use the values of z sampled with Algorithm 2 to estimate this expectation. More precisely, keeping notations of Algorithm 2:

E Z|X,β,α Ψ [α(s)] k + ∑ N X n=1 z nk ≈ 1 P P ∑ t=1 Ψ [α(s)] k + ∑ N X n=1 z t nk .

Bayesian Approach

In a Bayesian setting, we consider β as a random variable, with β ∼ Dirichlet(b1), with b ∈ R and 1 ∈ R V denotes the vector whose all entries equal 1. The variational distribution of the global parameter

β is set to q(β k |λ k ) = Dirichlet(λ k ), with λ k ∈ R V ∀k = 1, . . . , K.
The main difference with the frequentist methods above (G-OEM and V-OEM) is to optimize the ELBO with respect to the variational parameters (λ k ) k . In practice, it is equivalent to replace β k v by exp E q [log β k v ] in all the updates above (i.e., in Equation ( 11) for V-OEM and in Equation ( 14) for G-OEM). The variational parmater λ k ∈ R V is updated with stochastic gradient on the ELBO, which gives, at iteration t:

λ k (t + 1) = ρ t λ k (t) + (1 -ρ t ) λk , ( 15
) with λk ∈ R V , λk v = b + DE q S 1
kv , where D is the total number of documents in the dataset and b is the prior on β k [START_REF] Hoffman | Online learning for latent Dirichlet allocation[END_REF].

Algorithm 2 Gibbs sampling scheme to approximate p(z nk = 1|X, β, α)

Input: β, α, X.

Initialization: Z 0 n ∼ Mult([ βk x n ] k=1,...,K ), with βk x n = β k x n ∑ j β j x n ∀n ∈ 1, N X .
for t = 1, 2, . . . , P do Compute random permutation σ t on 1, N X , for n = 0, 1, . . . , N X do

• Set Z t -n = (z t σ t (i) ) 1≤i<n , (z t-1 σ t (i) ) n<i≤N X , • Compute ∀k, p(z σ t (n)k = 1|Z t
-n , X, β, α) with Equation ( 14),

• Sample z t σ t (n) ∼ Mult p(z σ t (n) |Z t -n , X, β, α) , end for end for for n = 0, 1, . . . , N X do Set Z t -n = (z t i ) 1≤i<n , (z t i ) n<i≤N X for t ≥ 3 4 P, p(z nk = 1|X, β, α) ← 4 P P ∑ t= 3 4 P p(z nk = 1|Z t -n , X, β, α)
end for Output: ∀k, ∀n: (z t n ) t=1,...,P , p(z nk = 1|X, β, α).

application to hierarchical dirichlet process (hdp)

The HDP model [START_REF] Teh | Hierarchical Dirichlet processes[END_REF] is a generative process to model documents from an infinite set of topics β k , k = 1, 2, 3, . . .. Each topic is a discrete distribution of size V, the size of the vocabulary. Each topic is associated to a weight π k ∈ [0, 1], representing the importance of the topic in the corpus. For each document d, the (infinite) topic proportions ν d are drawn from ν d ∼ Dirichlet(bπ).

We then generate words with a similar scheme to LDA scheme. More formally a corpus is generated as follows:

1. Draw an infinite number of topics β k ∼ Dirichlet(η), for k ∈ {1, 2, 3, . . .};

2. Draw corpus breaking proportions πk ∼ Beta(1, α), for k = 1, 2, 3, . . .; with ii. Draw word w n ∼ Multinomial(β z dn ).

π k = σ k ( π);
In practice, we set the initial number of topics to T = 2. We then increase the number of topics used in the corpus using Gibbs sampling and the formula p(z dn > T|X, η) ∝ b(1 -∑ T i=1 π i ). See Section 3.4.2 for details.

HDP and Exponential Families

We consider an exponential family model on random variables (X, h) with parameter η ∈ E ⊆ R d and with density:

p(X, h|η) = a(X, h) exp [ φ(η), S(X, h) -Ψ(η)] .
In the case of HDP, an observation X is a document of length N X , where (as for LDA) X = (x 1 , . . . , x N X ), x n ∈ {0, 1} V and ∑ V v=1 x nv = 1. In the frequentist approach, the parameters of the model are global, represented by η ≡ (β, π), where β represents the corpus topics, π represents the corpus breaking proportions. Our corpus C is a set of D observations C = (X 1 , . . . , X D ). For each document X d , the associated hidden variables are ν d ∈ [0, 1] K corresponding to document-level topic proportions. For each word x n of document X d , a hidden variable z n ∈ {0, 1} T is attached, corresponding to the topic assignment of word x n .

We want to find φ, S, ψ and a such that, the joint probability is in the exponential family:

p(X, Z, ν|β, π) = a(X, Z, ν) exp [ φ(β, π), S(X, Z, ν) -ψ(β, π)] ,
given an observation X and hidden variables Z and ν. For the HDP model, we have:

p(X, Z, ν|β, π) =p(ν|π) N X ∏ n=1 p(x n |z n , β)p(z n |ν) =W(π) ∏ k∈N * (ν k ) bπ k -1 N X ∏ n=1 ∏ k (ν k ) z nk ∏ v (β k,v ) x nv z nk = exp [-ψ(π)] exp ∑ k log ν k N X ∑ n=1 z nk -1 × exp ∑ k (bπ k ) log ν k × exp ∑ k,v log β k,v N X ∑ n=1 x nv z nk , with ψ(π) = ∑ k log Γ(bπ k ) -log Γ(b).
We deduce the exponential family setting φ, S, a:

S(X, Z, ν) =     S 1 k ≡ [log ν k ] k S 2 kv ≡ N X ∑ n=1 z nk x nv kv     , ( 16
) φ(β, π) =   φ 1 k ≡ [bπ k ] k φ 2 kv ≡ [log β k,v ] kv   , ( 17
) with a(X, Z, ν) = exp ∑ k log ν k N X ∑ n=1 z nk -1 .
The one-to one mapping between the sufficient statistics s = (s 1 , s 2 ) and (β, π) is defined by:

(β, π) * [s] =      arg max β≥0,1≥π≥0 φ(β, π), s -ψ(β, π) s.t. β 1 = 1,
where 1 denotes the vector whose all entries equal 1.

With the same computation than LDA, β * (s

) kv ≡ s 2 kv ∑ j s 2 kj
. We find π * (s) by solving:

π * (s) = arg max 1≥π≥0 K ∑ k=1 bπ k s 1 k -log Γ(bπ k ) + log Γ(b ∑ k π k ),
which gives:

Ψ(bπ * (s) k ) -Ψ b ∑ i π * (s) i = s 1 k .
where

Ψ : x → ∂ ∂x [log Γ] (x)
is the digamma function. We estimate (bπ) * with the fixed point iteration which consists in repeating the following update until convergence:

(bπ) new k = Ψ -1 Ψ ∑ i (bπ i ) old + s 1 k . Finally, (β, π) * [s] satisfies ∀(k, v):      (β * (s)) kv = s 2 kv ∑ j s 2 kj Ψ(bπ * (s) k ) -Ψ (b ∑ i π * (s) i ) = s 1 k .

Inference with online EM

In this section, we explain how to approximate E Z,ν|X,η [S(X, Z, ν)] with Gibbs sampling from a frequentist and a Bayesian perspective. In particular, as the total number of topics is infinite, we need to keep track of the previously used topics and iteratively extend the number of topics considered.

Gibbs online EM (G-OEM)

In our frequentist G-OEM approach, η is a parameter. The Gibbs sampling scheme to approximate E Z,ν|X,η [S(X, Z, ν)] is different from LDA and a probability of adding a new topic to the current list is computed at each iteration, as explained below.

expectation of S 1 . We have:

E Z,ν|X,η [S 1 (X, Z, ν)] k = E Z,ν|X,η [log ν k ] = E Z|X,η Ψ bπ k + N X ∑ n=1 z nk -Ψ b ∑ i π i + N X ,
and we use the values of z sampled with Gibbs sampling to compute:

E Z|X,η Ψ bπ k + N X ∑ n=1 z nk ≈ 1 P P ∑ t=1 Ψ bπ k + N X ∑ n=1 z t nk .
expectation of S 2 . We have:

E Z,ν|X,η [S 2 (X, ν)] kv = E Z,ν|X,η N X ∑ n=1 z nk x nv = N X ∑ n=1 x nv p(z nk = 1|X, η)
sampling z|X, η. If T is the current number of topics, we have:

∀k ∈ {1, . . . , T}, p(z nk = 1|z -n , X, η) ∝ (N -n k + bπ k ) × p(x n |z ni = 1, c ik = 1, η) ∝ (N -n k + bπ k ) × β k,x n ,
and the probability of sampling a new topic is given by:

p(z n > T|z -n , X, η) ∝ b 1 - T ∑ t=1 π k /V.
When a new topic is generated, we initialize π T+1 with πT+1 ∼ Beta(1, α) and

π T+1 = πT+1 ∏ T t=1 (1 -πt ).
Bayesian approach: VarGibbs [Wang and Blei, 2012] In a Bayesian settings where

β k ∼ Dirichlet(η); q(β k |λ) = Dirichlet(λ k ) and π k ∼ Beta(1, a); q(π k |a k , b k ) = Beta(a k , b k )
, the sampling scheme is different as we also sample π and an auxiliary variable s dk corresponding to the number of "tables" serving "dish" k in "restaurant" d (in the fomulation of HDP as a Chinese restaurant process; see Wang and Blei [2012] for details). Sampling z:

p(z nk = 1|z -n , λ, π) ∝ (N -n dk + bπ k ) N -n kx n + λ kx n N -n k + ∑ v λ kv . Sampling s: p(s dk |N dk , bπ k ) = Γ(bπ k ) Γ(bπ k + N dk ) S(N dk , s dk ) (bπ k ) s dk ,
with S(n, m) are unsigned Stirling number of the first kind. Sampling π:

p( πk ) ∝ πa k -1+∑ d∈S s dk k (1 -πk ) b k -α+∑ d∈S ∑ ∞ j=k+1 s dj
We then set:

                 λkv = η + D N X ∑ n=1 z nk x nv âk = 1 + Ds dk bk = α + D ∞ ∑ j=k+1 s dj (18)
and

λ t+1 = (1 -ρ t )λ t + ρ t λ; a t+1 = (1 -ρ t )a t + ρ t â; b t+1 = (1 -ρ t )b t + ρ t b.
In practice, for each document we sample the hidden variables z for each word and compute the topic counts N dk for topic k in document d, then we sample the variable s. Finally, we perform the online EM algorithm by making the approximation E p(h|X,η) [S(X, h)] ≈ E q(h) [S(X, h)], which corresponds to equation ( 18). Note that in this Bayesian approach, the parameters (λ, a, b) represent the distribution parameters of the random variables β and π.

evaluation

We evaluate our method by computing the likelihood on held-out documents, that is p(X|β, α) for any test document X. For LDA, the likelihood is intractable to compute. We approximate p(X|β, α) with the "left-to-right" evaluation algorithm [START_REF] Wallach | Evaluation methods for topic models[END_REF] applied to each test document. This algorithm is a mix of particle filtering and Gibbs sampling. On any experiments, this leads essentially to the same log-likelihood than Gibbs sampling with sufficiently enough samples-e.g., 200. In the following, we present results in terms of logperplexity, defined as the opposite of the log-likelihoodlog p(X|η). The lower the log-perplexity, the better the corresponding model. In our experiments, we compute the average test log-perplexity on N t documents. We compare eight different methods:

• G-OEM (our main algorithm): Gibbs online EM. Online EM algorithm with Gibbs estimation of the conditional distribution p(h|X, η) (Algorithm 2).

Frequentist approach and step-size

ρ i = 1/ √ i;
• V-OEM++: variational online EM (also a new algorithm). Online EM algorithm with variational estimation of the conditional distribution p(h|X, η), augmented with inference boosting from Section 3.2.3. Frequentist approach and step-size ρ i = 1/ √ i;

• OLDA: online LDA [START_REF] Hoffman | Online learning for latent Dirichlet allocation[END_REF]. Bayesian approach which maximizes the ELBO from Section 3.2.4, with natural stochastic gradient ascent and a step-size ρ i = 1/ √ i;

• VarGibbs: Sparse stochastic inference for LDA [START_REF] Mimno | Sparse stochastic inference for latent Dirichlet allocation[END_REF]. This method also maximizes the ELBO but estimates the variational expectations q(Z, θ) with Gibbs sampling instead of iterative maximization of variational parameters -see Section 3.3.2;

• SVB: streaming variational Bayes [START_REF] Broderick | Streaming variational Bayes[END_REF]. A variational Bayesian equivalent of V-OEM with step-size ρ i = 1/i;

• SPLDA: single pass LDA [START_REF] Sato | Deterministic single-pass algorithm for LDA[END_REF]. The difference with V-OEM++ is that ρ i = 1/i and the updates in α done with a Gamma prior (see Appendix 3.8);

• SGS: streaming Gibbs sampling [START_REF] Gao | Streaming Gibbs sampling for LDA model[END_REF]. This method is related to G-OEM with ρ i = 1/i. In this method, α is not optimized and set to a constant C α . For comparison purposes, for each dataset, we set C α to be the averaged final parameter α obtained with G-OEM on the same dataset:

C α = 1 K ∑ k αk .
For each observation, only the last Gibbs sample is considered, leading to extra noise in the output;

• LDS: Stochastic gradient Riemannian Langevin dynamics sampler [START_REF] Patterson | Stochastic gradient Riemannian Langevin dynamics on the probability simplex[END_REF]. The authors use the Langevin Monte Carlo methods on probability simplex and apply their online algorithm to LDA. For this method and only this method, we set to P = 200 the number of internal updates.

For existing variational methods-OLDA, SVB, SPLDA-β is a random variable with prior q(β). We estimate the likelihood p(X| β, α) with the "left-to-right" algorithm by setting β = E q [β] for Bayesian methods. For simplicity, we only present our results obtained with G-OEM and V-OEM++. Indeed, the inference boost presented in Section 3.3 is only beneficial for V-OEM. A detailed analysis is presented in Appendix 3.6.1.

Explicit links for LDA

In this section, we propose to make the links between the methods listed above explicit, using the framework described in Section 3.3 for the particular LDA model. We present in Table 4 a summary of the compared method.

category: In the frequentist approach, β is a parameter and is updated with Equation ( 8), as the "M-step" in online EM. In a Bayesian setting, β is a random variable with prior β ∼ Dirichlet(b1), with b ∈ R and 1 ∈ R V denotes the vector whose all entries equal 1. The variational distribution of the global parameter β is then set to q(β k |λ k ) = Dirichlet(λ k ), with λ k ∈ R V ∀k = 1, . . . , K. The variational parameter λ k is updated by maximizing the ELBO with stochastic gradient ascent (Equation ( 15)). can either be estimated with Gibbs sampling-Equation ( 14)-or with variational approximation-Equation ( 10).

step-size: Some of the methods listed above (SVB,SPLDA and SGS) are incremental, which means the sufficient statistics are incrementally aggregated

s t = s t-1 + E Z t |X t ,η [S(X t , Z t )]
. For LDA, it exactly corresponds to a step-size ρ t = 1/t in the online EM setting, even though the link is not explicit in the corresponding papers.

For the other listed methods, the step-size exponent κ is chosen arbitrarily in [0.5, 1), with ρ t = 1/t κ . However, results are mostly presented with κ = 1/2 and ρ t = 1/ √ t.

General settings

initialization. We initialize randomly η ≡ (β, α). For a given experiment, we initialize all the methods with the same values of (β, α) for fair comparison, except SPLDA that has its own initilization scheme-see [START_REF] Sato | Deterministic single-pass algorithm for LDA[END_REF] for more details.

minibatch. We consider minibatches of size 100 documents for each update in order to reduce noise [START_REF] Liang | Online EM for unsupervised models[END_REF]. In the case of online EM in Equation ( 3), we estimate an expectation for each observation of the minibatch. We update the new sufficient statistics s towards the average of the expectations over the minibatch. We do the same averaging for all the presented methods.

number of local updates. For all the presented methods, we set the number of passes through each minibatch to P = 20. For G-OEM, this means that we perform 20 Gibbs sampling for each word of the minibatch. All other methods access each document 20 times (e.g., 20 iterations of variational inference on datasets. We apply the methods on six differents datasets, summarized in Table 5 (N X is the average length of documents). Following [START_REF] Blei | Latent Dirichlet allocation[END_REF], the synthetic dataset has been generated from 10 topics and the length of each document drawn from a Poisson(60). The 10 topics are inferred with online LDA [START_REF] Hoffman | Online learning for latent Dirichlet allocation[END_REF] from 50,000 reviews of the IMDB dataset with a vocabulary size of 10,000. We only consider the entries of the 1,000 most frequent words of this dataset that we normalize to satisfy the constraint ∑ v β k v = 1. The words in the datasets IMDB, Wikipedia, New York Times, Pubmed and Amazon movies are filtered by removing the stop-words and we select the most frequent words of the datasets. For the synthetic dataset, IMDB, Pubmed and Amazon movies, the size of the test sets is N t = 5,000 documents. For Wikipedia and New York Times, the test sets contain N t = 2,000 documents. We run the methods on 11 differents train/test splits of each dataset. For all the presented results, we plot the median from the 11 experiments as a line-solid or dashed. For the sake of readability, we only present the same plots with error bars between the third and the seventh decile in Appendix 3.A and Appendix 3.B. computation time. For each presented method and dataset, the computational time is reported in Table 6. Although all methods have the same runningtime complexities, coded in Python, sampling methods (G-OEM, VarGibbs and SGS) need an actual loop over all documents while variational methods (OLDA, SVB, SPLDA and V-OEM++) may use vector operations, and may thus be up to twice faster. This could be mitigated by using efficient implementations of Gibbs sampling on minibatches [START_REF] Yan | Parallel inference for latent Dirichlet allocation on graphics processing units[END_REF][START_REF] Zhao | SAME but different: Fast and high-quality Gibbs parameter estimation[END_REF][START_REF] Gao | Streaming Gibbs sampling for LDA model[END_REF]. Note also that to attain a given log-likelihood, our method G-OEM is significantly faster 1 Code available from [START_REF] Hoffman | Online learning for latent Dirichlet allocation[END_REF] 2 Dataset described in [START_REF] Diao | Jointly modeling aspects, ratings and sentiments for movie recommendation (JMARS)[END_REF] 3 Data from [START_REF] Leskovec | SNAP Datasets: Stanford large network dataset collection[END_REF] 4 UCI dataset [START_REF] Lichman | UCI machine learning repository[END_REF] and often attains log-likelihoods not attainable by other methods (e.g., for the dataset New York Times).

step-size. In the following, we compare the results of our methods G-OEM and V-OEM++ with κ = 1/2, i.e., the step-size ρ t = 1/ √ t, without averaging. Detailed analysis of different settings of our method can be found in Appendix 3.6.

In particular, we compare different step-sizes and the effect of averaging over all iterates. We also compare the performance of OLDA with different step-sizes in Appendix 3.6.2 and observe that results are very similar for all the step-sizes that we try. Note that for incremental methods (SVB, SPLDA, SGS), the step-size is fixed to ρ t = 1/t. For LDS, we run the method with parameters as close as possible to our method for fair comparison.

Results on LDA

Results obtained with the presented methods applied to LDA on different text datasets for different values of the number K of topics are presented in Figure 6. Performance through iterations (i.e., as the number of documents increases) is presented in Figure 9. We first observe that for all experiments, our new method G-OEM performs better-often significantly-than all existing methods. In particular, it is highly robust to diversity of datasets.

influence of the number of topics K. As shown in Figure 6, for synthetic data in plot (a), although the true number of topics is K * = 10, SPLDA, OLDA, VarGibbs and SGS perform slightly better with K = 20, while G-OEM has the better fit for the correct value of K; moreover, SVB has very similar performances for any value of K, which highlights the fact that this method does not capture more information with a higher value of K. LDS performs very poorly on this dataset-for any value of K the log-perplexity is around 400-and is not displayed in Figure 6 (a) for clarity.

On non-synthetic datasets in plots (b)-(f), while the log-perplexity of frequentist methods-G-OEM, V-OEM++ and SPLDA-decreases with K, the log-perplexity of variational Bayesian methods-OLDA and SVB-does not decrease significantly with K. As explained below, our interpretation is that the actual maximization of the ELBO does not lead to an improvement in log-likelihood. The hybrid Bayesian method VarGibbs-which uses Gibbs sampling for local updates (θ, z) and variational updates for global parameters (β, α)-performs much better than the variational Bayesian methods. Our interpretation is that the objective function maximized with VarGibbs is a much better approximation of the log-likelihood than the ELBO.

In terms of robustness, G-OEM and LDS are the only methods that do not display overfitting on any dataset. However, LDS is only competitive for the highest values of K-K ≥ 500. performance through iterations. As shown in Figure 9, for synthetic data in plot (a), after only few dozens of iterations-few thousands of documents seen-G-OEM, V-OEM++ and VarGibbs outperform the other presented methods. Variational Bayesian methods again do converge but to a worse parameter value. On real datasets in plots (b)-(f), G-OEM and VarGibbs are significantly faster; we can indeed still observe that after around 100 iterations-10,000 documents seen-G-OEM and VarGibbs perform better than other methods on all the datasets except Pubmed, where the performances of G-OEM, V-OEM++, VarGibbs and SPLDA are similar. variational vs. sampling. Our method G-OEM directly optimizes the likelihood with a consistent approximation, and performs better than its variational counterparts SPLDA and V-OEM++ in all experiments. The hybrid method VarGibbs is less robust than G-OEM as it performs either similarly to G-OEM-for the datasets Wikipedia, New York Times and Pubmed-or worse than G-OEM and its variational counterparts SPLDA and V-OEM++-for the datasets IMDB and Amazon. frequentist vs. bayesian. In all our experiments we observe that frequentist methods-G-OEM, V-OEM++ and SPLDA-outperform variational Bayesian methods-OLDA and SVB. As described in Section 3.2.4, variational Bayesian methods maximize the ELBO, which makes additional strong independence assumptions and here leads to poor results. For example, as the number K of topics increases, the log-likelihood goes down for some datasets. In order to investigate if this is an issue of slow convergence, we show on Figure 7 (dotted black line) that running P = 100 internal updates in OLDA to get a finer estimate of the ELBO for each document may deteriorate the performance. Moreover, Figure 8 presents the evolution of the ELBO, which does always increase when K increases, showing that the online methods do optimize correctly the ELBO (while not improving the true log-likelihood). See Appendix 3.7 for additional results on the convergence of the ELBO. The results are mitigated for the hybrid Bayesian method VarGibbs. The performance of this method is either similar to G-OEM and V-OEM++ or significantly worse than both G-OEM and V-OEM++.

small step-sizes vs. large step-sizes. SPLDA is a variational method which is equivalent to V-OEM++, but with a step-size 1/i, which is often slower than bigger step-sizes [START_REF]Incremental majorization-minimization optimization with application to large-scale machine learning[END_REF], which we do observe-see Appendix 3.6.2 for a further analysis on the effect of the choice of step-sizes as 1/i κ on G-OEM.

Note that we run all the methods on a fixed (finite) number of observations. If we were to extend to infinite datasets, the difference between the step-sizes should be the speed of convergence. However, even if the number of observations is large, the gap between the step-sizes is still significant to justify the use of 1/ √ t for the step-size. Indeed, when considering large datasets, the contribution of each iteration at the end of the pass over the data is squeezed by the step-size in 1/t. When the number of observations is large enough to prevent the use of batch algorithms but still insufficient for an online algorithm to converge in one pass, a possible solution could be to consider constant step-sizes in order to converge even faster to a local maxima. As proposed, we do not have any guarantee for our methods to converge with constant step-sizes, but previous works have shown the benefits of using constant step-sizes under certain assumptions (e.g., [START_REF] Bach | Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)[END_REF])

Empirical analysis

In this section we provide a qualitative empirical analysis on the topics extracted with the different methods. We note this is clearly a subjective analysis but it stresses the benefits of a "better" inference mechanism in terms of log-likelihood [ [START_REF] Chang | Reading tea leaves: How humans interpret topic models[END_REF]. Examples of eight topics extracted with G-OEM and OLDA on the IMDB dataset of movie reviews are presented in Table 7 page 65.

We first compute the KL divergence between the K = 128 topics extracted with G-OEM and the K = 128 topics extracted with OLDA. We run the Hungarian algorithm on the resulting distance matrix to assign each topic extracted with G-OEM to a single topic of OLDA. We choose manually eight topics extracted with G-OEM that are representative of the usual behavior, and display the eight corresponding topics of OLDA assigned with the above method.

We observe that the topics extracted with G-OEM are more consistent than topics extracted with OLDA: topics of G-OEM precisely describe only one aspect of the reviews while the topics of OLDA tend to mix several aspects in each topic. For instance, the words of topic 1 extracted with G-OEM are related to horror movies. The words of the corresponding topic extracted with OLDA mix horror moviese.g., horror, scary -and ghost movies -e.g., ghost, haunt. In this OLDA topic 1, we can also observe less relevant words, like effective, mysterious, which are not directly linked with horror and ghost vocabularies. We can make the same remarks with topic 2 and topic 3, respectively related to comedy movies and romantic comedy movies. In topic 2 extracted with G-OEM, the least related words to comedy are names of characters/actors -i.e., steve and seth -while the words not related to comedy in topic 25 of OLDA are more general, belonging to a different lexical field -e.g., sport, site, progress, brave, definition. In topic 3 of G-OEM, all the presented words are related to romantic comedy while in topic 3 of OLDA, the words old, hard and review are not related to this genre.

We also observe that G-OEM extracts strongly "qualitative" topics -topic 4 and topic 5 -which is not done with OLDA. Indeed, it is difficult to group the top words of topic 4 or topic 5 of OLDA in the same lexical field. Except dialogue and suppose, all the top words of topic 4 of G-OEM are negative words. These two words may appear in a lot of negative sentences, leading to a high weight in this topic. In topic 5 of G-OEM, the words absolutely and visual are non strictly positive words while the thirteen other words in this topic convey a positive opinion. The word absolutely is an adverb much more employed in positive sentences than negative or neutral sentences, which can explain its high weight in topic 5.

The topic 6 of both G-OEM and OLDA can be considered as a "junk" topic, as for both method, most of its top words are contractions of modal verbs or frequent words -e.g., didn't, isn't, wait, bad. The contractions are not filtered when removing the stop words as they are not included in the list of words removed1 .

For both G-OEM and OLDA, the top words of topic 7 are general words about movies. These words are usually employed to describe a movie as a wholee.g., narrative, filmmaker.

Finally, the top words of topic 8 of G-OEM are related to the situation of the scenes. We could not find such topic in the other presented methods and we can see that the top words of topic 8 of OLDA -supposedly close to topic 8 of G-OEM -are related to family movies. Each word of topic 8 of G-OEM -except group and beautiful -are related to a spatial location, and may help answer the question "where does the scene take place?". For the HDP model, we compare our G-OEM method to the Bayesian VarGibbs [Wang and Blei, 2012] method. We set the initial number of topics to T = 2. We present in Figure 10

gibbs/variational online em analysis

In this section we evaluate the proposed methods G-OEM and V-OEM with different settings in terms of step-sizes, averaging outputs and boosting internal updates.

Effect of inference boosting on G-OEM and V-OEM

The effect of the inference boost as described in Section 3.2.3 on G-OEM and V-OEM with synthetic and IMDB datasets is presented in Figure 11 and in Figure 12. It leads to a minor improvement for G-OEM++ and a significant one for V-OEM++. Figure 11: G-OEM. Perplexity on different test sets as a function of the number of topics K for regular EM and boosted EM (++). We observe that for almost all datasets, there is no significant improvement when boosting the inference. Our interpretation is that each Gibbs sample is noisy and does not provide a stable boost. Best seen in color. Figure 12: V-OEM. Perplexity on different test sets as a function of the number of topics K for regular EM and boosted EM (++). We observe that boosting inference improves significantly the results on all the datasets excepted on Wikipedia where V-OEM and V-OEM++ have similar performances. The variational estimation of the posterior is finer and finer through iterations. When updating the parameters at each iteration of the posterior estimation, the inference is indeed boosted. Best seen in color.

Step-sizes and averaging

We apply G-OEM with different stepsizes ρ i = 1 i κ . Note that because we average sufficient statistics, there is no needed proportionality constants. We first compare the performance of the last iterate η N (without averaging) and the average of the iterates ηN = 1 N ∑ N i=0 η i (with averaging) for different values of κ.

Results are presented in Figure 13 on the synthetic data and in Figure 16 on the IMDB dataset. For κ ∈ 0, 1 2 , averaging improves the performance while for κ ∈ 1 2 , 1 , averaging deteriorates the performance. For κ = 1 2 , averaging is only slightly beneficial on IMDB dataset. For constant stepsizes κ = 0 the averaging improves significantly the performance, as the iterates do not converge and tend to oscillate around a local optimum [START_REF] Bach | Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)[END_REF]. We can expect the same effect for κ ∈ 0, 1 2 as the function n → 1 n κ deacreases slowly for such values of κ. For κ ∈ 1 2 , 1 , the stochastic gradient ascent scheme is guaranteed to converge to a local optimum [START_REF] Bottou | Online learning and stochastic approximations[END_REF]. The averaging then deteriorates the performance as it incorporates the first iterates, which gets the last iterate away from local optimum. However, the stepsize 1/i (κ = 1) is not competitive. The performance with κ = 0.75 is only slightly better on IMDB dataset. The setting κ = 1 2 represents a good balance between first and last iterates. For this stepsize, performances with or without averaging are similar but results without averaging seem to be more stable, hence our choice for all our other simulations.

We also apply OLDA with different step-sizes ρ t = τ/t κ for different values of τ, κ. Results are presented in Figure 14

K =8 K =16 K =32 K =64 K =128 (
K =8 K =16 K =32 K =64 K =128 (b) Without averaging
Figure 16: Dataset: IMDB. Perplexity on different test sets as a function of the exponent κ-the corresponding stepsize is ρ i = 1 i κ -for G-OEM with averaging (left) and without averaging (right). The number of topics inferred K goes from 8 (the lightest) to 128 (the darkest). Best seen in color.

evolution of the elbo

Figure 17 presents the evolution of the ELBO for online LDA (OLDA) and SVB on different test sets. We compute the ELBO on test documents as described by [START_REF] Hoffman | Online learning for latent Dirichlet allocation[END_REF]. This plot helps us to observe that even if the ELBO reaches a local maximum (i.e., it stabilizes), the quality of the model in terms of perplexity is not controllable. We can also see in Figure 17 that the ELBO is much better optimized with K = 128 than with other values of K for both SVB and OLDA, that is, as expected, latent variables of higher dimensionality lead to better fits for the cost function which is optimized. However, for several datasets the performance in terms of perplexity is better with low values of K (K = 8 or K = 16) than with high dimensional variables (K = 64 or K = 128). In order to check if more internal iterations could help variational Bayesian methods, we present in Table 8 the values of perplexity reached by OLDA when running 4 passes over each dataset with P = 200 internal iterations 1 pass over each dataset with P = 20 internal iterations. We observe that the ELBO converges quickly to a local optimum and doing ten times more internal iterations does not change significantly the final performance.

updates in α

In this section we compare the different types of updates for α. Figure 18 presents results obtained on synthetic dataset for fixed point iteration algorithm [START_REF] Minka | Estimating a Dirichlet distribution[END_REF] and by putting a gamma prior on α [START_REF] Sato | Deterministic single-pass algorithm for LDA[END_REF]. We observe that the fixed point method leads to better performance for G-OEM and G-OEM++. For V-OEM, the gamma updates better perform for κ = 1 2 . The performances of the gamma updates and the fixed point method are very similar for V-OEM++. Note that the algorithm V-OEM++ with κ = 1 and gamma updates on α is exactly equivalent to SPLDA [START_REF] Sato | Deterministic single-pass algorithm for LDA[END_REF]. The performance of this method can be improved by setting κ = 1 2 with any update on α. We also observe that fixing α to α true that generated the data does not necessarily lead to better performance. [START_REF] Sato | Deterministic single-pass algorithm for LDA[END_REF]. Best seen in color.

conclusion

We have developed an online inference scheme to handle intractable conditional distributions of latent variables, with a proper use of local Gibbs sampling within A P P E N D I X 3.a performance with different K, with error bars

The performance of the presented methods for different values of K on the different datasets is presented in Figure 19. We plot the median from the 11 experiments as a line-solid or dashed-and a shaded region between the third and the seventh decile.

3.b performance through iterations, with error bars

The performance through iterations of the presented methods on the different datasets is presented in Figure 20. We plot the median from the 11 experiments as a line-solid or dashed-and a shaded region between the third and the seventh decile.

3.c results on hdp, with error bars

The performance through iterations of the G-OEM and VarGibss applied to both LDA and HDP is presented in Figure 21. We plot the median from the 11 experiments as a line-solid or dashed-and a shaded region between the third and the seventh decile. Determinantal point processes (DPPs) show lots of promises for modelling diversity in combinatorial problems, e.g., in recommender systems or text processing [START_REF] Kulesza | k-DPPs: Fixed-size determinantal point processes[END_REF], Gillenwater et al., 2012a[START_REF]Incremental majorization-minimization optimization with application to large-scale machine learning[END_REF], with algorithms for sampling [START_REF] Kang | Fast determinantal point process sampling with application to clustering[END_REF][START_REF] Affandi | Approximate inference in continuous determinantal processes[END_REF], Li et al., 2016a,b] and likelihood computations based on linear algebra [START_REF] Mariet | Fixed-point algorithms for learning determinantal point processes[END_REF][START_REF] Gartrell | Low-rank factorization of determinantal point processes for recommendation[END_REF], Kulesza and Taskar, 2012]. While most of these algorithms have polynomial-time complexity, determinantal point processes are too slow in practice for large numbers N of items to choose a subset from. Simplest algorithms have cubic running-time complexity and do not scale well to more than N = 1000. Some progress has been made recently to reach quadratic or linear time complexity in N when imposing lowrank constraints, for both learning and inference [Mariet andSra, 2016, Gartrell et al., 2016]. This is not enough, in particular for applications in continuous DPPs where the base set is infinite, and for modelling documents as a subset of all possible sentences: the number of sentences, even taken with a bag-of-word assumption, scales exponentially with the vocabulary size. Our goal in this chapter is to design a class of DPPs which can be manipulated (for inference and parameter learning) in potentially sublinear time in the number of items N.

In order to circumvent even linear-time complexity, we consider a novel class of DPPs which relies on a particular low-rank decomposition of the associated positive definite matrices. This corresponds to an embedding of the N potential items in a Euclidean space of dimension V. In order to allow efficient inference and learning, it turns out that a single operation on this embedding is needed, namely the computation of a second-order moment matrix, which would take time (at least) proportional to N if done naively, but may be available in closed form in several situations. This computational trick makes a striking parallel with positive definite kernel methods [START_REF] Scholkopf | Learning with kernels: support vector machines, regularization, optimization, and beyond[END_REF]Smola, 2001, Shawe-Taylor and[START_REF] Shawe-Taylor | Kernel methods for pattern analysis[END_REF], which use the "kernel trick" to work in very high dimension at the cost of computations in a smaller dimension.

In this chapter we make the following contributions:

-We propose in Section 4.2 a new class of determinantal point processes (DPPs) which is based on a particular low-rank factorization of the marginal kernel. Through the availability of a particular second-moment matrix, the complexity for inference and learning tasks is polynomial in the rank of the factorization and thus often sublinear in the total number of items (with exact likelihood computations).

-As shown in Section 4.3, these new DPPs are particularly suited to a subclass of continuous DPPs (infinite number of items), such as on [0, 1] m , and DPPs defined on the V-dimensional hypercube, which has 2 V elements.

-We propose in Section 4.4 a model of documents as sampling a DPP of sentences, and propose a conditional maximum likelihood formulation to model topic proportions. We present an application to document summarization with a DPP on 2 500 items.

This work is under submission at ICML 2017.

review of determinantal point processes

In this chapter, for simplicity, we consider a very large finite set X , with cardinality |X | = N, following [START_REF] Kulesza | Determinantal point processes for machine learning[END_REF]. In several places, we will consider an infinite set (see, e.g., Section 4.2.4) [START_REF] Affandi | Approximate inference in continuous determinantal processes[END_REF][START_REF] Lavancier | Determinantal point process models and statistical inference[END_REF].

A determinantal point process (DPP) on a set X is a probability measure on 2 X , the set of all subsets of X . It can either be represented by an L-ensemble [START_REF] Borodin | Eynard-Mehta theorem, Schur process, and their Pfaffian analogs[END_REF]] L(x, y), for x, y ∈ X or by its marginal kernel K(x, y), which we refer to as the "K-representation" and the "L-representation". In this chapter, K and L will be N × N matrices, with elements K(x, y) and L(x, y) for x, y ∈ X . Both L and K are potentially large matrices, as they are indexed by elements of X .

A sample X drawn from a DPP on X is a subset of X , namely X ⊆ X . In the "K-representation" of a DPP, for any set A ⊂ X , we have:

P(A ⊆ X) = det K A ,
where K A is the matrix of size |A| × |A| composed of pairwise evaluations of K(x, y) for x, y ∈ A. If we denote by " " the positive semidefinite order on symmetric matrices (i.e., A B ⇔ (B -A) is positive semidefinite), the constraint on K is 0 K I so that the DPP is a probability measure.

In the "L-representation", for any set A ⊂ X , we have

P(X = A) = det L A det(I + L) . ( 19
)
The constraint on L is L 0. Given a DPP and its two representations L and K, we can go from L to K as K = I -(I + L) -1 and vice-versa as L = K(I -K) -1 . The L-representation only exists when K ≺ I, where "≺" denotes the positive definite order of symmetric matrices (i.e., A ≺ B ⇔ (B -A) is positive definite). We denote by DPP(K, L) the DPP defined by the matrices (K, L) such that L = K(I -K) -1 .

Several tasks can be solved, e.g., marginalization, conditioning, etc., that are either easy in the L-representation or in the K-representation. For instance, (conditional) maximum likelihood when observing sets is easier in the L-representation, as the likelihood of an observed set A ⊆ X is directly obtained with L through Eq. ( 19). Conversely, the expected number of selected items, E[|X|] for a DPP defined by L, K is easily computed with K as E[|X|] = tr K [START_REF] Kulesza | Determinantal point processes for machine learning[END_REF].

The DPPs model aversion between items. For instance, if X is drawn from a DPP(K, L), the probability that items i and j are together included in X is

P({i, j} ⊆ X) = K ii K jj -(K ij ) 2 .
This probability then decreases with similarity K ij between item i and item j. This key aversion property makes DPPs useful to document summarization (see Section 4.4) where we want to select sentences that covers the most the document while avoiding redundancy. approximate computations. In practice, the key difficulty is to deal with the cubic complexity in |X | of the main operations -determinant and computations of inverses. In their work, [START_REF] Kulesza | Determinantal point processes for machine learning[END_REF] propose a lowrank model for the DPP matrix L, namely L(x, y) = q(x) φ(x), φ(y) q(y), where q(x) ∈ R + corresponds to a "quality" measure of x and φ(x) ∈ R r , φ(x) = 1 corresponds to the "diversity" feature (or embedding) of x. In matrix notations, we have L = Diag(q)ΦΦ Diag(q). In particular, they show that most of the computations are based on the matrix C = Φ Diag(q 2 )Φ ∈ R r×r . As Φ ∈ R N×r , they achieve an overall complexity O(Nr 2 ). In their application to document summarization, they only parameterize and learn the "quality" vector q, fixing the diversity features Φ, whereas we also parameterize and learn Φ.

More recently, [START_REF] Gartrell | Low-rank factorization of determinantal point processes for recommendation[END_REF] use a low rank factorization of L (L = UU , with U ∈ R N×r ) and apply accelerated stochastic gradient ascent on the loglikelihood of observed sets for learning U. They achieve a linear complexity in N: O(Nr 2 ). [START_REF] Mariet | Kronecker determinantal point processes[END_REF] propose a Kronecker factorization of L: L = L 1 ⊗ L 2 where ⊗ is the Kronecker product, L i ∈ R N i ×N i and N = N 1 N 2 . They use a fixed point method (with the Picard iteration) to maximize the likelihood, that consists in alternatively updating L 1 and L 2 with a computational complexity O(N 3/2 ) if N 1 ≈ N 2 ≈ √ N. However, when the set X is very large (e.g., exponential) or infinite, even linear operations in N = |X | are intractable. In the next sections, we provide a representation of the matrices L and K together with an optimization scheme that makes the optimization of the likelihood tractable even when the set X is too large to perform linear operations in N = |X |.

a tractable family of kernels

We consider the family of matrices decomposed as a sum of the identity matrix plus a specific low-rank term, where the column-space of the low-rank term is fixed. We show that if K is in the family (with its additional constraint that K ≺ I), so is L, and vice-versa.

Low-rank family

We consider a feature map φ : X → R V , a probability mass function p : X → R + , a scalar σ ∈ R + and a symmetric matrix B ∈ R V×V . The kernel K(x, y) is constrained to be of the form:

K(x, y) = σ1 x=y + p(x) 1/2 φ(x) Bφ(y)p(y) 1/2 . ( 20
)
In matrix notation, this corresponds to with α ∈ R + and A ∈ R V×V . The following proposition is a direct consequence of the Woodbury matrix identity:

K = σI + Diag(p) 1/2 ΦBΦ Diag(p)
Proposition 1 The kernel K defined in Eq. (20) is a valid DPP if (a) σ ∈ [0, 1], (b) 0 B (1 -σ)(Φ Diag(p)Φ) -1 .
It corresponds to the matrix L defined in Eq. ( 21) with σ = α α+1 and

B = 1 (α + 1) 2 A -1 + 1 α + 1 Φ Diag(p)Φ -1 .
Moreover, we may use the matrix determinant lemma to obtain

det(L + I) = det[(α + 1)I] det[A] × det A -1 + 1 α + 1 Φ Diag(p)Φ ,
which is expressed through the determinant of a V × V matrix (instead of N × N).

We may also go from L to K as α = σ 1-σ and

A = 1 (1 -σ) 2 B -1 - 1 1 -σ Φ Diag(p)Φ -1 .

Tractability

From the identities above, we see that a sufficient condition for being able to perform the computation of L and its determinant is the availability of the matrix

Σ = Φ Diag(p)Φ = ∑ x∈X p(x)φ(x)φ(x) ∈ R V×V .
In the general case, computing such an expectation would be (at least) linear time in N, but throughout this chapter, we assume this is available in polynomial time in V (and not in N). As shown in Section 4.3, many standard distributions satisfy this property. Note that this resembles the kernel trick, as we are able to work implicitly in a Euclidean space of dimension N while paying a cost proportional to V. In our document modelling example, we will have N = 2 V , and hence we achieve sublinear time.

We can compute other statistics of the DPP when K, L belong to the presented family of matrices. For instance, the expected size of a set X drawn from the DPP represented by K, L is:

E[|X|] = tr K = σ|X | + tr (BΣ) . ( 22
)
Given φ(x), the parameters are the distribution p(x) on X , A ∈ R V×V and α ∈ R + . If X is very large, it is hard to learn p(x) from observations and p(x) is thus assumed fixed. We also have to assume that α is proportional to 1/|X | or zero when X is infinite as the first term of E[|X|] in Eq. ( 22), α α+1 |X |, must be finite.

Additional low-rank approximation

If V is large, we use a low-rank representation for A:

A = γI + U Diag(θ)U , (23)
with γ ∈ R + , θ ∈ R r + and U ∈ R V×r . All the exact operations on L are then linear in V, i.e., as O(Vr 2 ). See details in Appendix 4.D. Moreover, the parameter θ can either be global or different for each observation, which gives flexibility to the model in the case where observations come from different but related DPPs on X . For instance, in a corpus of documents, the distance between words (conveyed by U) may be different from one document to another (e.g., field and goal may be close in a sport context, not necessary in other contexts). This can be modelled through θ as topic proportions of a given document (see Section 4.4).

Note that the additional low-rank assumption (23) corresponds to an embedding x ∈ X → U φ(x) ∈ R r , where φ(x) is fixed and U is learned. When V N, the gain in complexity compared to O(Nr 2 ) [START_REF] Gartrell | Low-rank factorization of determinantal point processes for recommendation[END_REF] or O(N 3/2 ) [START_REF] Mariet | Kronecker determinantal point processes[END_REF] is significant. For instance, if we consider the ground set X = {0, 1} V , we have V = log 2 (N). The operations on L with our formulation are then sublinear in N = 2 V , i.e., as O log 2 (N)r 2 . This complexity allows us to treat much larger problems i.e., V 20 for X = {0, 1} V that are intractable with previously achieved complexities.

Infinite X

Although we avoid dealing rigorously with continuous-state DPPs in this work [START_REF] Affandi | Approximate inference in continuous determinantal processes[END_REF][START_REF]Incremental majorization-minimization optimization with application to large-scale machine learning[END_REF][START_REF] Bardenet | Inference for determinantal point processes without spectral knowledge[END_REF], we note that when dealing the 1 norm and U 1,2 = ∑ r i=1 u i 2 , where . 2 is the 2 norm and u i is the i-th column of U. The group sparsity norm . 2 1,2 allows to set columns of U to zero and thus learn the number of columns. This is a non non-convex problem made non smooth by the group norm. Following [START_REF] Lewis | Nonsmooth optimization via quasi-Newton methods[END_REF], we use BFGS to reach a local optimum of our objective function.

examples

In this section, we review our three main motivating examples: (a) orthonormal basis based expansions applicable to continuous space DPPs; (b) standard orthonomal embedding with X = {1, . . . , N} and (c) exponential set X = {0, 1} V for applications to document modelling based on sentences in Section 4.4.

Orthonormal basis based expansions

We consider a fixed probability distribution p(x) on X and an orthonormal basis of the Euclidean space of square integrable (with respect to p) functions on X . We consider φ(x) i as the value at x of the i-th basis function. Note that this extends to any X , even not finite by going to Hilbert spaces.

We consider A = Diag(a) and B = Diag(b) two diagonal matrices in R V×V . Since φ(x) is an orthonormal basis, we have:

Σ = ∑ x∈X p(x)φ(x)φ(x) = I,
with a similar result for any subsampling of φ(x) (that is keeping a subset of the basis vectors).

For example, for X = [0, 1], p(x) the uniform distribution, α = 0 and φ(x) the cosine/sine basis, we obtain the matrix L(x, y) = φ(x) Diag(a)φ(y) which is a 1-periodic function of xy, and we can thus model any of these functions. This extends to X = [0, 1] m by tensor products, and hyperspheres by using spherical harmonics [START_REF] Atkinson | Spherical Harmonics and Approximations on the Unit Sphere: an Introduction[END_REF]. truncated fourier basis. In practice, we consider the truncated Fourier orthonormal basis of R y) is a 1-periodic function of xy, with only the first d frequencies, which allows us to learn covariance functions which are invariant by translation in the cube. We could also use the K-representation K(x, y) = φ(x) Bφ(y), with B = Diag(b) diagonal in [0, 1], but the log-likelihood maximization is easier in the L-representation.

V with V = 2d + 1, i.e., φ 1 (x) = 1, φ 2i (x) = √ 2 cos(2πix) and φ 2i+1 = √ 2 sin(2πix), for i ∈ {1, . . . , d} and x ∈ X . If A = Diag(a) is diag- onal, then L(x, y) = φ(x) Diag(a)φ(
We use this truncated basis to optimize the log-likelihood L(L) on finite observations [Eq. ( 24)] , i.e., X i ⊆ X and |X i | < ∞. In particular, the normaliza-tion constant is computed efficiently with this representation of L as we have det(L + I) = ∏ V i=1 (a i + 1).

non-parametric estimation of the stationary covariance function. We may learn any 1-periodic function of xy for L(x, y) or K(x, y) and we do so by choosing the truncated Fourier basis of size V, we could also use positive definite kernel techniques to perform non-parametric estimation.

running time complexity. For general continuous ground set X = [0, 1] m , with m ≥ 1, the running time complexity is still controlled by V = (2d + 1) m , d corresponding to the number of selected frequencies in each dimension of the Fourier basis (with a ∈ R V ). The value of d may be adjusted to fit the complexity in O(Vκ 3 ) or O(d m κ 3 ), where κ is the size of the biggest observation (i.e., the largest cardinality of all observed sets).

Standard orthonormal embeddings

In this section, we consider DPPs on the set X = {1, . . . , V} (i.e., N = V). We choose the standard orthonormal embedding, that is Φ = I which gives the expression L = αI + U Diag(θ)U , taking γ = 0 in Eq. ( 23). For this particular model, the complete embedding ΦU = U is learned and the distribution p(x) is included in U. This is only possible when V is small. This model is suited to item selection, where groups of items are observed (e.g., shopping baskets) and we want to learn underlying embeddings of these items (through parameter U). Again, the size of the catalog V may be very large. Note that unlike existing methods leveraging low-rank representations of DPPs [Mariet andSra, 2016, Gartrell et al., 2016], the parameter θ in our representation can be different for each observation, which makes our model more flexible.

4.3.3 X = {0, 1} V
In this section, we consider DPPs on the set X = {0, 1} V . For large values of V, direct operations on matrices L, K may be impossible as X is exponential, |X | = 2 V . In particular, we consider the model where φ(x) = x, i.e., Φ ∈ R 2 V ×V (in other words we simply embed {0, 1} V in R V ).

As mentioned above, the tractability of the DPP(L, K) on X = {0, 1} V depends on the expectation Σ = ∑ x∈X p(x)xx . For particular distributions p(x), Σ can be computed in closed form. For instance, if p(x) corresponds to V independent Bernouillis, i.e., p(x) = ∏ V i=1 π

x i i (1π i ) 1-x i , the expectation quantity is Σ = Diag(π(1π)) + ππ . If the independent Bernoullis are exchangeable, i.e., all π's are equal, we have Σ = π(1π)I + π 2 11 . Note that we can use the real numbers π i as prior information, for instance by setting them to empirical frequencies of each word.

The tractability of our model is extended to the case X = N V with Poisson variables. Indeed, if p

(x) = ∏ V i=1 e -λ i λ x i i x i ! for x ∈ N V , the expectation of xx over X is Σ = Diag(λ) + λλ .
Note that the tractability of the model is not restricted to these two examples of p(x) (Bernouilli and Poisson) and can be easily extended to other distributions p(x) (e.g., Gaussian) combined with other features φ(x). The distribution p(x) corresponds to a prior knowledge on the considered items.

Given these examples, we assume in the following that:

Σ = ∑ x∈X p(x)xx = Diag(ν) + µµ .
The complexity of operations on the matrix L with this structure is O(Vr 2 )instead of O(2 V r 2 ) if working directly with L; see Appendix 4.D for details. If we use the factorization of Σ above:

tr K = α α + 1 2 V + 1 (α + 1) 2 tr Diag(ν) + µµ × 1 α + 1 (Diag(ν) + µµ ) + A -1 -1 .
This identity suggests that we replace α by α2 -V in order to select a finite set X ⊆ X . For large values of V, α = 0 is the key choice to avoid infinite number of selected items.

dpp for document summarization

We apply our DPP model to document summarization. Each document X is represented by its sentences, X = (x 1 , . . . , x |X| ) with x i ∈ X = {0, 1} V . The variable V represents the size of the vocabulary, i.e., the number of possible words. A sentence is then represented by the set of words it contains, ignoring their exact count and the order of the words. We want to extract the summary of each document as a subset of observed sentences. We use the structure described in Section 4.2.1 to build a generative model of documents. Let K ∈ R 2 V ×2 V be the marginal kernel of a DPP on the possible sentences X . We consider that the summary Y ⊆ X of document X is generated from the DPP(K, L) as follows:

1. Draw sentences X = (x 1 , . . . , x |X| ) from DPP represented by L, 2. Draw summary Y ⊆ X from DPP represented by L X .

In practice, we observe a set of documents and we want to infer the word embeddings U and the topic proportions θ for each document. In the following we consider that α and γ are fixed. We also denote by L(U, θ) ≡ L(L) the log-likelihood of observations [Eq. ( 24)] for simplicity as our DPP matrix L is encoded by U and θ. We run experiments on synthetic datasets generated from the different types of DPPs described above. For all the datasets, we generate the observations using the sampling method described by [START_REF] Kulesza | Determinantal point processes for machine learning[END_REF] (Algorithm 1 page 16) and perform the evaluation for 10 different datasets. This method draws exact samples from a DPP matrix L and its eigendecomposition (which requires N to be less than 1000). For the evaluation figures, the mean and the variance over the 10 datasets are respectively displayed as a line and a shaded area around the mean.

continuous set [0, 1] m . We describe in Section 4.3.1 a method to learn from subsets drawn from a DPP on a continuous set X . As sampling from continuous DPPs is not straightforward and approximate [START_REF] Affandi | Approximate inference in continuous determinantal processes[END_REF], we consider a discretization of the set [0, 1] 2 into the discrete set {0, 1/N, . . . , (N -1)/N} 2 . Note that this discretization only affects the sampling scheme. We generate a dataset from the ground set X = {0, 1/N, . . . , (N -1)/N} 2 with the DPP rep- resented by L(x, y) = φ(x) Diag(a)φ(y) , with embedding φ(x) ∈ R N 2 the dis- crete Fourier basis of (R N ) 2 , i.e., for (i,

j) ∈ {1, . . . , N} 2 , φ(x) i,j = ψ(x 1 ) i ψ(x 2 ) j with functions ψ(z) 1 = 1, ψ(z) 2k = √ 2 cos(2πkz) and ψ(z) 2k+1 = √ 2 sin(2πkz), for k = 1, . . . , (N -1)/2. With notations of Section 4.3.1 we have V = N 2 . For (i, j) ∈ {0, . . . , N -1} 2 , we set a (i,j) = C i C j ãi ãj , with C 0 = 1, ã0 = 1 and C i = 1/ √ 2, ãi = 1/i β for i ≥ 1.
We choose N = 33 (i.e., V = N 2 = 1069) and β = 2 for the experiments. We present in Figure 22 two samples: a sample drawn from the DPP described above and a set of points that are i.i.d. samples from the uniform distribution on X . We observe aversion between points of the DPP sample that are distributed more uniformly than points of the i.i.d. samples. items set. We generate observations from the ground set X = {1, . . . , V}, which corresponds to the matrix L = αI + U Diag(θ)U . For these observations, we set V = 100, r = 5, α = 10 -5 . For each dataset, we generate U and θ randomly with different seeds accross the datasets. exponential set. We generate observations from the set X = {0, 1} V with φ(x) = x. In this case, we set V = 10, r = 2, α = 10 -5 , γ = 1/V. As we need the eigendecomposition of L ∈ R 2 V ×2 V for sampling, we could not generate exact samples with higher orders of magnitude for V. However, we can still optimize the likelihood for ground sets with large values of V and we run experiments on real document datasets, where the size of the vocabulary is V = 500 (i.e., |X | = 2 500 ≈ 10 150 ).

For both ground sets X = {1, . . . V} and X = {0, 1} N , we consider two types of datasets: one dataset where all the observations are generated with the same DPP matrix L and another dataset where observations are generated with a ) for each observation. For the second type of dataset, the embedding U is common to all the observations while the variable θ i differs from one observation to another.

real dataset. We consider a dataset of 100,000 restaurant reviews and minimize the objective function F(U, θ) mentioned above. We first remove the stopwords using the NLTK toolbox [START_REF] Bird | Natural language processing with Python[END_REF]. Among the remaining words, we only keep the V = 500 most frequent words of the dataset. After filtering, the average number of sentences per review is 10.5 and each sentence contains on average 4.5 words. We use the proposed DPP structure to (1) learn word embedding U from observations and (2) extract a summary for each review using the model of Section 4.4. Given a document X, the inferred parameters U and θ(X) and the corresponding DPP matrix L, we extract the l sentences summarizing the document X by solving the following maximization:

Y * ∈ arg max Y⊆X, |Y|=l det(L Y ) det(L X + I)
.

In practice we use the greedy MAP algorithm [Gillenwater et al., 2012b] to extract the summary Y of document X, as an approximation of the MAP Y * with the usual submodular maximization approximation guarantee [START_REF] Krause | Submodular function maximization[END_REF].

Evaluation

We evaluate our optimization scheme with two metrics. First, we compare the log-likelihood on the test set obtained with the inferred model L to the test loglikelihood with the model that generated the data L * . We use this metric when the data is generated with a single set of parameters over the dataset (i.e., the same DPP matrix L is used to generate all the observations) as in such case the difference of test log-likelihood between two models (L * -L) is an estimation of the Kullback-Leibler divergence between the two models.

We also consider a distance between the inferred embedding U and the embedding that generated the data U * . As the performance is invariant to any permutation of column in the matrix U (together with indices of θ) and to a scaling factor -both (U, θ) and ( 1 √ γ U, γθ) correspond to the same DPP matrix L -we consider the following distance that compares the linear space produced with U ∈ R V×r and U * ∈ R V×r * :

D(U, U * ) = U(U U) -1 U U * -U * F / U * F ,
where . F is the Frobenius norm. This distance is invariant to scaling and rotation and is equal to zero when U and U * span the same space in R V . In particular, if we generate randomly the r columns of Z ∈ R V×r , the expectation of the distance to U * is E Z [D(Z, U * )] = 1 -r V . We display this quantity as "chance" in the following. As the number of columns in U ∈ R V×r and U ∈ R V×r * is dif- ferent, we can not use losses similar to what is used in independent component analysis [START_REF] Hyvärinen | Independent component analysis[END_REF]. The distance D(U, U * ) seems appropriate here as it measures if we recover the correct subspace for a sufficiently small rank and allows us to compare matrices of different shapes.

continuous set [0, 1] 2 . We compare our inference method to the best diagonal DPP L η * = η * I, where η * ∈ R maximizes the log-likelihood. items set, X = {1, . . . , V}. We compare our inference method to the Picard iteration on full matrices proposed by [START_REF] Mariet | Fixed-point algorithms for learning determinantal point processes[END_REF]. As they only consider the scenario where all the observations are drawn from the same DPP, we only compare to our method in that case.

Synthetic datasets

continuous set [0, 1] 2 . We present the difference in log-likelihood between the inferred model and the model that generates the data as a function of the iterations in Figure 23. The comparison between the resulting kernel and the kernel that generates the data is presented in Appendix 4.A. We observe that our model performs significantly better than the η * I kernel and converges to the the true log-likelihood. items set & exponential set. We present the difference in log-likelihood and the distance of embeddings U between the inferred model and the model that generates the data as a function of the rank r of the representation in Figure 24 for the ground set X = {1, . . . , V} and in Figure 25 for the ground set X = {0, 1} V . For set X = {0, 1} V , results for observations generated from the same DPP (i.e., with a single θ for the whole dataset) are presented in Appendix 4.D as we recover the parameter U * with the same precision for any regularization coefficient λ. We observe that the penalization may deteriorate the performance in terms of log-likelihood but significantly improves the quality of the recovered parameters. In practice, as our penalization R induces sparsity we recover sparse θ when r > r * . For both ground sets, the parameter U * that generated the data is recovered for r * < r < V. In matrix factorization, increasing the size of the factors leads to fewer or no local minima [START_REF] Haeffele | Structured low-rank matrix factorization: Optimality, algorithm, and applications to image processing[END_REF], which is consistent with the fact that we only recover U * for r > r * .

For the items set X = {1, . . . , V}, while the datasets are generated with r * = 5, we observe the parameter U * is only recovered when we optimize with r ≥ 30. We also observe that our method performs better than the Picard iteration of [START_REF] Mariet | Fixed-point algorithms for learning determinantal point processes[END_REF] in terms of log-likelihood. The Picard iteration updates the full matrix L and there is no tradeoff between the rank and the closeness of spanned subspaces, conveyed by D(U, U * ).

For the exponential set X = {0, 1} V , r * = 2 and the parameter U * is recovered for r ≥ 6.

Real dataset.

Summaries with l = 5 sentences of two reviews are presented in Table 9. The corresponding embeddings U are presented in Table 10 andTable 11. We observe that our method is able to extract sentences that describes the opinion of the user on the restaurant. In particular, the sentences extracted with our method convey commitment of the user to aspects (food, service,...) while other sentences of the reviews only describe the context of the meal.

Columns of U

We present four embeddings (i.e., columns of U ∈ R V×r ) out of r = 10 learned on a restaurant reviews dataset with our DPP structure in Table 10 below. We display the 20 words with the highest absolute values for each column of U. We observe that our embeddings extract qualitative words (e.g., good, great, friendly). Even if the embeddings are not as consistent as topics extracted with topic models (e.g., LDA), we can distinguish different aspects of restaurants with the em-beddings. For instance, words with positive values in embedding 1 are related to the food (e.g., cream, love, crispy, tomato); words with positive values in embedding 2 are associated to the service aspect (with service, friendly, staff, attentive). Moreover, they already lead to good summaries.

4.d summary as a subsampleparameter learning

We assume that ∑ x∈X p(x)φ(x)φ(x) = Diag(ν) + µµ . The log-likelihood of an observed document X is expressed as (X|L) = log det L Xlog det(L + I).

The computation of the second term, log det(L + I), is untractable to compute in reasonable time for any L when V ≥ 20, since L ∈ R 2 V ×2 V . We can still compute this value for structured L. When L = αI + Diag(p) 1/2 ΦAΦ Diag(p) 1/2 , we have, using the matrix determinant lemma and Woodbury identity:

det(L + I) = det[(α + 1)I] det A det A -1 + 1 α + 1 Φ Diag(p)Φ .
We then have, if ρ = 1 α+1 : log det A -1 + ρ Diag(ν) + ρµµ = log 1 + ρµ A -1 + ρ Diag(ν) In the end, the computation of log det(L + I) only needs matrix products of size V and inversions of size r.

C O N C L U S I O N

The ultimate goal of this work is to suggest any user a personalized list of contents with a short readable text attached to each content, where this short text conveys the opinion the user may form about the corresponding content. We proposed a line of work towards this goal. In particular, we present new topic models and new inference schemes for these models to help the users quickly assess previously unseen contents. Given the work developped in this thesis, the possible future directions are the following:

• Througout this thesis, we evaluate the performance of the presented methods with predictive likelihood (e.g., following [START_REF] Wallach | Evaluation methods for topic models[END_REF] for LDA). In particular, we only use empirical results-such as topics extracted with our methods-to illustrate the models when applied to real datasets. Following a heavy line of work on the evaluation of topic coherence such as [START_REF] Newman | Automatic evaluation of topic coherence[END_REF], [START_REF] Mimno | Optimizing semantic coherence in topic models[END_REF], [START_REF] Lau | Machine reading tea leaves: Automatically evaluating topic coherence and topic model quality[END_REF], [START_REF] Röder | Exploring the space of topic coherence measures[END_REF], it would be interesting to measure the impact of our methods on topic coherence. It would also be interesting to include the presented models in a recommender systems and measure the impact of the model on the speed of choice and the satisfaction of the user.

• We could study topic models in decentralized networks [START_REF] Colin | Decentralized topic modelling with latent Dirichlet allocation[END_REF], i.e., networks with limited communication between nodes. In such networks, it is typically impossible to efficiently centralize data or to globally aggregate intermediate results: agents can only communicate with their immediate neighbors, often in a completely asynchronous fashion. It would be interesting to build an inference scheme for topic models suited to such networks and investigate empirical differences between topics extracted in a decentralized settings compared to online inference proposed in Chapter 3.

• Following [START_REF] Brunel | Maximum likelihood estimation of determinantal point processes[END_REF] and [START_REF] Urschel | Learning determinantal point processes with moments and cycles[END_REF], it would be intereseting to investigate the theoretical convergence guarantees for the maximum likelihood estimator of DPP as presented in Chapter 4. More specifically, as we propose a specific low-rank factorization of the marginal kernel, we would like to look for guarantees on the maximum likelihood estimator for such low-rank matrices.

• Moreover, we apply the DPP model presented in Chapter 4 to text summarization, where we are able to summarize a single review with readable sentences. It would be interesting to build a model able to summarize a full corpus of documents. This kind of model would be for instance useful in crowd-sourced review services (such as Yelp or IMDB) where we could automatically suggest the user the most relevant sentences among all the previous reviews. In particular, it would be interesting to enhance the DPP model with other information than text only (e.g., the ratings, the useful score, content class such that genre for movies of type of food for restaurants) in order to personalize the recommendation and get closer to the ultimate goal presented at the beginning of this thesis. While we are able to extract word embeddings with our formulation of DPPs, it would be interesting to extract other embeddings, for instance on the genres of movies or the types of products, in order to compute distances between these genres or types of products.

• We also would like to apply the DPP model of Chapter 4 to computer vision. More specifically, we would like to tackle the problem of diversity of the outputs proposed by computer vision models. For instance, let us consider the problem of multi-class segmentation. The goal is to accurately assign a single class to every pixel among K possible classes. While existing models cast this problem as an optimization problem, there has recently been an interest in extracting diverse quality outputs from the model [START_REF] Kirillov | Inferring m-best diverse labelings in a single one[END_REF][START_REF] Batra | Diverse m-best solutions in Markov random fields[END_REF][START_REF] Dey | Predicting multiple structured visual interpretations[END_REF]. In this problem of mutli-class segmentation, if you select the M segmentations with the best values for the objective function, it is very likely that these M outputs only differ from only few pixels. The motivations for diverse outputs resides in the fact that computer vision tasks are often addressed by a series of modules (e.g., layers in a neural network) where each module generates several hypotheses as input to the next module. A good practice in this structure is to consider diverse options at each module in order to avoid premature commitment to a low quality feature that would destroy the quality of the final output [START_REF] Viola | Rapid object detection using a boosted cascade of simple features[END_REF]Jones, 2001, Felzenszwalb and[START_REF] Felzenszwalb | The generalized A* architecture[END_REF]. In this context, the DPPs are perfectly suited as a model to generate diverse outputs. In the particular case of the multi-class segmentation problem, it would be interesting to learn a distance between the K possible classes (through class embeddings) from examples of such segmentations and to have the possibility to sample diverse segmentations. Another computer vision problem is the estimation of the pose of persons in an image where it is very unlikely that two persons stands at the same place in a picture. In this case, the DPP could promote spaced pose estimations with a higher probability.

Résumé

La plupart des systèmes de recommandation actuels se base sur des évaluations sous forme de notes (i.e., chiffre entre 0 et 5) pour conseiller un contenu (film, restaurant...) à un utilisateur. Ce dernier a souvent la possibilité de commenter ce contenu sous forme de texte en plus de l'évaluer.

Abstract

Most of current recommendation systems are based on ratings (i.e. numbers between 0 and 5) and try to suggest a content (movie, restaurant...) to a user. These systems usually allow users to provide a text review for this content in addition to ratings. It is hard to extract useful information from raw text while a rating does not contain much information on the content and the user. In this thesis, we tackle the problem of suggesting personalized readable text to users to help them make a quick decision about a content.

More specifically, we first build a topic model that predicts personalized movie description from text reviews. Our model extracts distinct qualitative (i.e., which convey opinion) and descriptive topics by combining text reviews and movie ratings in a joint probabilistic model. We evaluate our model on an IMDB dataset and illustrate its performance through comparison of topics.

We then study parameter inference in large-scale latent variable models, which include most topic models. We propose a unified treatment of online inference for latent variable models from a non-canonical exponential family, and draw explicit links between several previously proposed frequentist or Bayesian methods. We also propose a novel inference method for the frequentist estimation of parameters, which adapts MCMC methods to online inference of latent variable models with the proper use of local Gibbs sampling. For the specific latent Dirichlet allocation topic model, we provide an extensive set of experiments and comparisons with existing work, where our new approach outperforms all previously proposed methods.

Finally, we propose a new class of determinantal point processes (DPPs) which can be manipulated for inference and parameter learning in potentially sublinear time in the number of items. This class, based on a specific low-rank factorization of the marginal kernel, is particularly suited to a subclass of continuous DPPs and DPPs defined on exponentially many items. We apply this new class to modelling text documents as sampling a DPP of sentences, and propose a conditional maximum likelihood formulation to model topic proportions, which is made possible with no approximation for our class of DPPs. We present an application to document summarization with a DPP on 2 500 items, where the summaries are composed of readable sentences.

  (a,b) Same θ for all the observations; (c) A different θ for each observation. . . . . . . . . . . . . . . . . . . . Top 5 topics extracted with LDA-O and LDA-C, K = 128 (ordered by importance θk = 1 D ∑ d θ d k ). . . . . . . . . . . . . Table

Figure 1 :

 1 Figure 1: Graphical representation of two probabilistic topic models. White nodes represent hidden variables and colored nodes represent observed variables.

Figure 2 :

 2 Figure 2: Graphical representation of LDA. White nodes represent hidden variables and colored nodes represent observed variables.

Figure 3 :

 3 Figure 3: Graphical representation of the model LDA-R-C including reduced ratings applied on D documents. White nodes represent hidden variables and colored nodes represent observed variables. The observed rating r d is not reported for the sake of clarity.

Figure 4 :

 4 Figure 4: Average log-perplexity per word of the presented models on test reviews.

AFigure 5 :

 5 Figure 5: Graphical representation of the model LDA-R-C including reduced ratings applied on D documents. White nodes represent hidden variables and colored nodes represent observed variables. The observed rating r d is not reported for the sake of clarity.

3.

  For each document d: a) Draw document-level topic proportions: ν d ∼ Dirichlet(bπ); b) For each word n in d: i. Draw topic assignment z dn ∼ Multinomial(ν d );

Figure 6 :

 6 Figure 6: Perplexity on different test sets as a function of K, the number of topics inferred. Best seen in color.

Figure 7 :

 7 Figure 7: OLDA. Perplexity on different test sets as a function of K for OLDA with P = 10 (red) and P = 100 (black) internal updates.

Figure 8 :

 8 Figure 8: Dataset: IMDB. Evidence Lower BOund (ELBO) computed on test sets (20 internal iterations and 1 pass over the dataset). Left: ELBO through iterations with K = 128. Right: ELBO as a function of the number of topics K.

Figure 9 :

 9 Figure 9: Perplexity through iterations on different test sets with the presented methods. Best seen in color.

Table 7 :

 7 fight

Figure 10 :

 10 Figure 10: Perplexity through iterations on different test sets with G-OEM and VarGibbs applied to both LDA and HDP. Best seen in color.

Figure 13 :

 13 Figure13: Dataset: synthetic. Perplexity on different test sets as a function of the exponent κ-the corresponding stepsize is ρ i = 1 i κ -for G-OEM with averaging (left) and without averaging (right). The number of topics inferred K goes from 5 (the lightest) to 20 (the darkest). Best seen in color.

Figure 14 :

 14 Figure 14: Evolution of perplexity on different test sets as a function of the number of documents analyzed. For OLDA, we compare the performance with different step-sizes ρ t = τ/t κ for different values of τ, κ. Solid line: κ = 1/2; Dashed line: κ = 1.

Figure 15 :

 15 Figure 15: Evolution of perplexity on different test sets as a function of the number of documents analyzed, with error bars. For OLDA, we compare the performance with different step-sizes ρ t = τ/t κ for different values of τ, κ. Solid line: κ = 1/2; Dashed line: κ = 1.

Figure 18 :

 18 Figure 18: Dataset: Synthetic, K = 10. Perplexity on different test sets for different types of updates for α; for boosted methods, we use the same inference for α for local and global updates. NO: α is fixed and set to α true that generated the data; FP: fixed point iteration; Gam: gamma prior on α [Sato et al., 2010]. Best seen in color.

Figure 19 :Figure 20 :Figure 21 :

 192021 Figure 19: Perplexity on different test sets as a function of K, the number of topics inferred. Same as Figure 6, but with error bars. Best seen in colors.

Figure 23 :

 23 Figure 23: Continuous set [0, 1] 2 . Distance (L * -L) in log-likelihood.

Figure 24 :

 24 Figure 24: Performance for ground set X = {1, . . . , V} as a function of r. (a,b) Same θ for all the observations; (c) A different θ for each observation.

Figure 25 :

 25 Figure 25: Performance for ground set X = {0, 1} V as a function of r with a different θ for each observation.

Figure 27 :

 27 Figure 27: Picard iteration [Mariet and Sra, 2015]. Evolution of the objective function (train log-likelihood) as a function of the iterations.

  Distance between U and U * .

Figure 28 :

 28 Figure 28: Performance for ground set X = {0, 1} V as a function of r. (a,b) Same θ for all the observations; (c) A different θ for each observation.

+(

  log det(A -1 + ρ Diag(ν)) (matrix determinant lemma)= log 1 + µ Diag(1/ν) -Diag(1/ν)(ρA + Diag(1/ν)) -1 Diag(1/ν) µ + log det(A -1 + ρ Diag(ν)) (Woodbury identity).If we consider A = γI + U Diag(θ)U , we have:(ρA + Diag(1/ν)) -1 = (ργI + ρU Diag(θ)U + Diag(1/ν) Woodbury identity on A -1 ) = log det Diag(γ/θ) + U U -1 γ U Diag γ 1 + νγρ U log det(Diag(γ/θ) + U U) + log det( I γ + ρ Diag(ν)) = log det Diag(γ/θ) + U Diag νγρ 1 + νγρ U log det(Diag(γ/θ) + U U) + log det( I γ + ρ Diag(ν)), log det(A) = log det(Diag(1/θ) + 1 γ U U) + ∑ k log θ k + V log γ.

Table 5

 5 Datasets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Table 6

 6 Average computational time (in hours) for each method -

K = 128. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Table 7 Comparison of topics extracted on IMDB dataset, K = 128 -15 top words of eight topics extracted with G-OEM and OLDA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Table 8 Comparison of log-perplexity levels reached with OLDA and SVB on IMDB dataset. . . . . . . . . . . . . . . . . . . . Table

  d D } with probability p(d);Note that in this model, one latent variable (or topic) z ∈ {1, . . . , K} is attached to each word v of document d (i.e., N d hidden variables in document d), while in the mixture of unigrams model only one topic z is attached to each document. Another distinction is the probability p(z|d) which depends on the document d in the pLSI model while p(z) is indepedent to the documents in the mixture of unigrams model. The graphical representation of the pLSI model is presented in Figure

	2. For each of the N d words of document d:
	a) Choose a latent topic z ∈ {1, . . . , K} with p(z|d);
	b) Choose a word v ∈ {1, . . . , V} with probability p(v|z).
	More formally, the joint probability model on (v, d) is:
		K
	p(v, d) = p(d)p(v|d), with p(v|d) =	z=1 ∑	p(v|z)p(z|d).

Table 1 :

 1 Top 5 topics extracted with LDA-O and LDA-C, K = 128 (ordered by im-

	1 movie

Table 2 :

 2 Positive (left column) and negative (right column) topic inferred with LDA-R and LDA-R-C, K = 32 topics. vocabulary given a set of training reviews W and a test couple (u t , c t ) of user, movie. The evaluation of such prediction is done by splitting the review dataset in a training set and a testing set. The parameters of the model are learned on the training set and evaluated on the test set.

		LDA-R	LDA-R-C
	great	bad	great	bad
	best	worst	bad	great
	nice	boring	love	boring
	bad	waste	best	worst
	entertaining stupid	original	stupid
	original	terrible entertaining totally
	love	suppose definitely	waste

Table 4 :

 4 Comparison of existing methods for LDA.

		Category	E Z|X,η [S(X, Z)] Step-size ρ t	Update for α
	G-OEM	frequentist Gibbs sampling	free	fixed point
	V-OEM	frequentist	variational	free	fixed point
	OLDA	Bayesian	variational	free	gradient ascent
	VarGibbs	Bayesian	Gibbs sampling	free	α fixed
	SVB	Bayesian	variational	fixed: 1/t gradient ascent
	SPLDA	Bayesian	variational	fixed: 1/t	Gamma prior
	SGS	frequentist Gibbs sampling fixed: 1/t	α fixed
	estimation of E

Z|X,η [S(X, Z)]: For LDA, the expectation E Z|X,η [S(X, Z)]

Table 5 :

 5 Datasets. For G-OEM, inference with larger values for P (e.g., P = 50 or P = 100) leads to very similar results.

	Dataset	#documents N X #words
	Synthetic	1,000,000	60	1,000
	Wikipedia 1	1,010,000	162.3	7702
	IMDB 2	614,589	82.2	10,000
	Amazon movies 3	338,565	75.4	10,000
	New York Times 4	299,877	287.4 44,228
	Pubmed 4	2,100,000	82.0 113,568
	each document).

Table 6 :

 6 Average computational time (in hours) for each method -K = 128.

		IMDB Wikipedia NYT Pubmed
	G-OEM	13h	55h	30h	58h
	V-OEM++	9h	37h	20h	54h
	OLDA	7h	33h	8h	30h
	VarGibbs	12h	50h	28h	54h
	SVB	7h	34h	9h	30h
	SPLDA	9h	37h	20h	54h
	SGS	11h	48h	27h	50h
	LDS	7h	17h	12h	40h

Table 8 :

 8 Comparison of log-perplexity levels reached with OLDA and SVB on IMDB dataset.

		P = 200, 4 passes P = 20, 1 pass
	OLDA	682.6±3.7	681.9±3.9
	SVB	683.8±3.8	684.5±3.8

  1/2 , with Φ ∈ R |X |×V and B ∈ R V×V . With additional constraints detailed below, this defines a valid DPP, for which the L-representation can be easily derived in

	the form
	L(x, y) = α1 x=y + p(x) 1/2 φ(x) Aφ(y)p(y) 1/2 ,	(21)

Table 9 :

 9 Examples of reviews with extracted summaries (of size l = 5 sentences) colored in blue. Potatoes and asparagus. Came back for Mother's Day brunch. Â Excellent booth table at the window, so we could watch our valeted car. Pretty good service. Good food. No complaints. Review 2 This will be my 19 month old's first bar. :D I came here with a good friend and my little guy. We shared the double pork chop and the Mac n Cheese. [

	Review 1
	Ate here once each for dinner and Sunday brunch. [Dinner was great.] [We
	got a good booth seat and had some tasty food.] I ordered just an entree since
	I wasn't too hungry. The guys ordered appetizers and salad and I couldn't
	resist trying some. The risotto with rabbit meatballs was so good. [Corn
	soup, good.] [And my duck breast, also good.] I was happy. [The sides were
	good too.]

The double pork chop was delicious.....] [Huge portions and beautifully prepared vegetables.] [What a wonderful selection of butternut squash, spinach, cauliflower and mashed potato

.] We were very impressed with the chop, meat was tender and full of flavor. [The mac n cheese, was okay.] I would definitely go back for the pork chop... might want to try the fried mushrooms too. [Place surprisingly was pretty kid friendly.] The bathroom actually had a bench I could change my little guy! different matrix L(θ i

Table 10 :

 10 Four embeddings (columns of U) inferred with r = 10 on restaurant reviews dataset.

	Embed. 1 U w,1	Embed. 2	U w,2	Embed. 3 U w,3	Embed. 4	U w,4
	love	0.19	service	0.74	great	0.99	place	0.75
	could	0.11	friendly	0.36	food	0.8	great	0.41
	large	0.11	nice	0.33	service	0.4	good	0.35
	cream	0.1	good	0.24	star	0.32	really	0.28
	crispy	0.1	pretty	0.24	worth	0.26	love	0.21
	tomato	0.09	staff	0.24	place	0.26	nice	0.16
	meat	0.09	price	0.15	price	0.25	service	0.16
	ice	0.08	experience 0.14	back	0.21	atmosphere 0.14
	sauce	0.08	well	0.14	wait	0.2	get	0.14
	mouth	0.08	attentive	0.13	definitely 0.18	friendly	0.13
	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
	back	-0.48	would	-0.26	also	-0.27	could	-0.21
	sushi	-0.51	think	-0.27	tasty	-0.28	dinner	-0.21
	place	-0.51	try	-0.28	fresh	-0.31	menu	-0.25
	pretty	-0.53	restaurant -0.28	salad	-0.32	restaurant	-0.27
	really	-0.58	one	-0.3	delicious	-0.36	well	-0.28
	come	-0.64	amazing	-0.33	really	-0.4	come	-0.37
	great	-0.73	like	-0.57	nice	-0.43	eat	-0.38
	service	-0.79	get	-0.64	like	-0.44	food	-0.39
	food	-1.08	love	-0.73	chicken	-0.45	time	-0.4
	good	-2.08	place	-1.05	order	-0.59	price	-0.4

Table 11 :

 11 Ten examples of cosine similarity between words (i.e., between rows of U) with r = 10 on restaurant reviews dataset.

	food	Cos	service	Cos	decor	Cos	atmosphereCos
	solid	0.97	slow	0.93	unique	1.0	cool	0.94
	delivery 0.91	friendly	0.91	vibe	0.95	unique	0.88
	average	0.9	fast	0.9	warm	0.87	view	0.85
	indian	0.9	quick	0.88	date	0.87	wonderful 0.85
	decent	0.88	delivery 0.87	atmosphere0.85	decor	0.85
	overall	0.86	extremely 0.85	damn	0.82	fun	0.82
	expensive 0.85	staff	0.83	cool	0.81	vibe	0.82
	quality	0.83	experience 0.8	beach	0.79	date	0.81
	italian	0.83	average	0.77	broth	0.76	kind	0.79
	sunday	0.82	good	0.75	run	0.73	pancake 0.78
	meal	Cos	good	Cos	tender	Cos	tasty	Cos
	cheap	0.97	location	0.98	juicy	0.96	awesome 0.99
	drink	0.97	look	0.96	hard	0.95	fresh	0.97
	sunday	0.96	hit	0.93	flavorful 0.93	delicious 0.96
	though	0.96	bad	0.9	light	0.93	people	0.95
	sushi	0.94	ever	0.9	gnocchi	0.89	course	0.92
	city	0.93	quick	0.87	shrimp	0.89	beer	0.92
	overall	0.92	okay	0.87	sausage	0.89	fill	0.92
	visit	0.91	pretty	0.86	real	0.88	fish	0.91
	well	0.91	sure	0.85	water	0.88	nice	0.9
	bad	0.91	city	0.85	main	0.87	server	0.9
			dry	Cos	time	Cos
			light	0.93	late	0.97
			inside	0.93	day	0.97
			ingredient 0.92	open	0.97
			salty	0.91	first	0.96
			potato	0.9	saturday 0.93
			sausage	0.89	far	0.92
			meat	0.89	visit	0.91
			put	0.88	last	0.9
			tender	0.85	though	0.89
			kinda	0.85	price	0.88

  Il est difficile d'extraire de l'information d'un texte brut tandis qu'une simple note contient peu d'information sur le contenu et l'utilisateur. Dans cette thèse, nous tentons de suggérer à l'utilisateur un texte lisible personnalisé pour l'aider à se faire rapidement une opinion à propos d'un contenu.Plus spécifiquement, nous construisons d'abord un modèle thématique prédisant une description de film personnalisée à partir de commentaires textuels. Notre modèle sépare les thèmes qualitatifs (i.e., véhiculant une opinion) des thèmes descriptifs en combinant des commentaires textuels et des notes sous forme de nombres dans un modèle probabiliste joint. Nous évaluons notre modèle sur une base de données IMDB et illustrons ses performances à travers la comparaison de thèmes.Nous étudions ensuite l'inférence de paramètres dans des modèles à variables latentes à grande échelle, incluant la plupart des modèles thématiques. Nous proposons un traitement unifié de l'inférence en ligne pour les modèles à variables latentes à partir de familles exponentielles non-canoniques et faisons explicitement apparaître les liens existants entre plusieurs méthodes fréquentistes et Bayesiennes proposées auparavant. Nous proposons aussi une nouvelle méthode d'inférence pour l'estimation fréquentiste des paramètres qui adapte les méthodes MCMC à l'inférence en ligne des modèles à variables latentes en utilisant proprement un échantillonnage de Gibbs local. Pour le modèle thématique d'allocation de Dirichlet latente, nous fournissons une vaste série d'expériences et de comparaisons avec des travaux existants dans laquelle notre nouvelle approche est plus performante que les méthodes proposées auparavant.Enfin, nous proposons une nouvelle classe de processus ponctuels déterminantaux (PPD) qui peut être manipulée pour l'inférence et l'apprentissage de paramètres en un temps potentiellement sous-linéaire en le nombre d'objets. Cette classe, basée sur une factorisation spécifique de faible rang du noyau marginal, est particulièrement adaptée à une sous-classe de PPD continus et de PPD définis sur un nombre exponentiel d'objets. Nous appliquons cette classe à la modélisation de documents textuels comme échantillons d'un PPD sur les phrases et proposons une formulation du maximum de vraisemblance conditionnel pour modéliser les proportions de thèmes, ce qui est rendu possible sans aucune approximation avec notre classe de PPD. Nous présentons une application à la synthèse de documents avec un PPD sur 2 500 objets, où les résumés sont composés de phrases lisibles.

http://www.yelp.com

http://www.amazon.com

http://www.imdb.com

http://www.quora.com

http://stackoverflow.com/

http://www.apple.com/ios/siri/

http://madeby.google.com/home/

http://www.amazon.com/echo

http://www.technicolor.com/

http://www.thefork.com

For restaurants, the number of features is smaller and the optimal value of K is around 60.

See NLTK toolbox[Bird et al.,

2009] for the exhaustive list of stop words.

modèles thèmatiques, apprentissage en ligne, modèles à variables latentes, apprentissage non supervisé, processus ponctuels determinantaux, allocation de Dirichlet latente.

online EM, that leads to significant improvements over variational methods and Bayesian estimation procedures. Note that all methods for the same problem are similar (in fact a few characters of code away from each other); ours is based on a proper stochastic approximation maximum likelihood framework and is empirically the most robust. It would be interesting to explore distributed large-scale settings [START_REF] Broderick | Streaming variational Bayes[END_REF][START_REF] Yan | Parallel inference for latent Dirichlet allocation on graphics processing units[END_REF][START_REF] Gao | Streaming Gibbs sampling for LDA model[END_REF] and potentially larger (e.g., constant) step-sizes that have proved efficient in supervised learning [START_REF] Bach | Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)[END_REF].

with exponentially large finite sets X or infinite sets, we need to set σ = α = 0 to avoid infinite (or too large) expectations for the numbers of sampled elements (which we use in experiments for N = 2 V ).

Note moreover, that in this situation, the kernel K is formulated as

the rank of the matrix K is thus at most V, which implies that the number of sampled elements has to be less than V. This is not an issue in our experiments as V corresponds to the vocabulary size and we do not encounter documents with more than V sentences. We can sample from the very large DPP as soon as we can sample from a distribution on X with density proportional to p(x)φ(x) Aφ(x). Indeed, one can sample from a DPP by first selecting the eigenvectors of L, each with probability λ i /(λ i + 1)-where the λ i 's are the eigenvalues of L-and then projecting the canonical basis vectors-one per item-on this subset of eigenvectors. The density for selecting the first item is proportional to the squared norm of the latter projection (see Algorithm 1 of [START_REF] Kulesza | Determinantal point processes for machine learning[END_REF] for more details). Given our fomula for L, all the required densities can be expressed as being proportional to p(x)φ(x) Aφ(x). In our simulations, we use instead a discretized scheme.

Learning parameters with maximum likelihood

In this section, we present how to learn the parameters of the model, corresponding to the matrix A.

We have access to the likelihood through observations. We denote the observations by X 1 , . . . , X M , with X i ⊆ X , drawn from a density µ(X). Each set X i is a set of elements X i = {x i 1 , . . . , x i |X i | }, with x i j ∈ X . We denote by (X|L) the log-likelihood of a set X given a DPP matrix L. Our goal is to maximize the expected log-likelihood under µ, i.e., E µ(X) [ (X|L)]. As we only have access to µ through observations, we maximize an estimation of

As the log-likelihood of a set X ⊆ X is given by (X|L) = log det L Xlog det(L + I), our objective function becomes:

In the following, we assume p fixed and we only learn A in its form (23).

In practice we minimize a penalized objective, that is, for our parameterization of A in Eq. ( 23),

where L is the log-likelihood of a train set of observations [Eq. ( 24)] and R is a penalty function. We choose the penalty R(U, θ) = θ 1 + U 2 1,2 where . 1 is The intuition behind this generative model is that the sentences of a document cover a particular topic (the topic proportions are conveyed by the variable θ) and it is very unlikely to find sentences that have the same meaning in the same document. In this sense, we want to model aversion between sentences of a document.

parameter learning. As explained in Section 4.3.3, we assume that Σ is available in closed form, with Σ = Diag(ν) + µµ . The log-likelihood of an observed document X is (X|L) = log det L Xlog det(L + I). The computation of the second term, log det(L + I), is untractable to compute in reasonable time for any L when V ≥ 20, since L ∈ R 2 V ×2 V . We can still compute this value exactly for structured L coming from our model with complexity O(Vr 2 ) (see Appendix 4.D for details).

We infer the parameters U and θ by optimizing our regularized objective function F(U, θ) = -L(U, θ) + λR(U, θ) with respect to U and θ alternatively. In practice, we perform 100 iterations of L-BFGS for the function U → F(U, θ) and 100 iterations of L-BFGS for each function θ i → F(U, θ), for i = 1, . . . , M. The optimization in U can also be done with stochastic gradient descent (SGD) [START_REF] Bottou | Online learning and stochastic approximations[END_REF], using a mini-batch D t of observations at iteration t: U ← Uρ t G t (U), with G t (U) the unbiased gradient:

Rows of U

From the embeddings U, we can also compute similarity between words using the rows of U. We use the cosine similarity, i.e., for words v, w ∈ {1, . . . , V}:

where U v ∈ R r is the v th row of U. We present ten examples of words with their closest words for cosine similarity in Table 11. We observe that our word embeddings also capture context from the sentences. For instance, the closest words to food are mostly adjective applicable to food (e.g., solid, average, decent, expensive). We observe the same characteristic for the words of the top row in Table 11. For adjectives of the bottom row in Table 11 (i.e., good, tender, tasty and dry), the closest words are either synonnyms/antonyms or nouns that may have the characteristic conveyed by the corresponding adjective. For instance, among the closest words to tender, the words juicy and flavorful have similar meaning than tender, hard is an antonym while gnocchi, shrimp, sausage may be characterized as tender. Finally, the closest words to time are mostly words that convey temporal meaning (e.g., late, day, open, saturday)

conclusion

In this chapter, we propose a new class of determinantal point processes that can be run on a huge number of items because of a specific low-rank decomposition. This allowed parameter learning for continuous DPPs and new applications such as document modelling and summarization. We apply our model on exponential set X = {0, 1} V to model documents, it would be interesting to apply our inference to the infinite ground set X = N V as suggested in this chapter. We would also like to study the inference in continous exponential set X = R V using our decomposition.

While we focused primarily on DPPs to model diversity, it would also be interesting to consider other approaches based on submodularity [Djolonga andKrause, 2014, Djolonga et al., 2016] and study the tractability of these models for exponantially large numbers of items.

We acknowledge support from the CIFAR program in Learning in Machines & Brains. In this section, we present a comparison between the true marginal kernel (that generates the data) K * and the inferred marginal kernel K t . More precisely, X = [0, 1] 2 and we compute the induced distance from the center point q = ( 1 2 , 1 2 ) to any point x ∈ X , i.e., K(x, q). We show in Figure 26 a comparison between the true distance K * (x, q) and the inferred distance K t (x, q) after t = 100 iterations.

4.b picard iteration

We apply the Picard iteration of [START_REF] Mariet | Fixed-point algorithms for learning determinantal point processes[END_REF] on the synthetic "items" datasets (i.e., observations are generated from L = αI + U Diag(θ)U ) with N = 100 items. We present the evolution of the objective function through the iterations with the Picard iteration in Figure 27. We observe a similar evolution than presented in the original paper [START_REF] Mariet | Fixed-point algorithms for learning determinantal point processes[END_REF]. This however led in Figure 24 to a lower likelihood than L-BFGS on U.

4.c exponential set X = {0, 1} V

We present the difference in log-likelihood and the distance if embeddings U between the inferred model and the model that generates data as a function of the rank r of the representation in Figure 28.