kuniga.me > NP-Incompleteness > Paper Reading - Latent Aspect Rating Analysis on Review Text Data

09 Oct 2020

In [1] Wang, Lu and Zhai present a supervised machine learning model to solve a problem they name *Latent Aspect Rating Analysis*. To explain the problem, let’s start with some context. Sites like Amazon, TripAdvisor or Audible have a review system where the user provides a rating and a review text.

The overall rating might be too vague, so it’s desirable to break down this rating per what is called *aspect*. The list of aspects depend on the use case: for logding, it could be room, cleaningless or location; for Audible it has performance and story. The model tries to infer these implicit (latent) ratings from only the overall rating and the review text.

The authors define a model that learns from training data and show promising results with test data. In this post we’ll focus on the theory presented in [1].

To solve the *Latent Aspect Rating Analysis* problem, first the authors build a correlation matrix between words and aspects by scanning all the texts from the reviews in the training dataset. This matrix is then used in tandem with both the overall and aspect ratings in the training dataset to construct a model which is then used to infer the aspect ratings for the test dataset. The inferred values are then compared to the actual values to assess the quality of the model.

We’ll have a fixed set of $k$ aspects (e.g. for hotels it could be location, cleaningness, price). We then let $A_i$ for $i \in [1, …, k]$ be the set of words associated with an aspect $i$. Note that these sets are not mutually exclusive, so for example “view” could be related to aspect “room” or “location”.

For each document $d \in D$, we have $W_d$ which is a $k \times n$ where $W_{dij}$ is the frequency of word $w_j$ for aspect $i$ normalized by the total number of the words in the text in that aspect, that is:

\(\sum_{j=1}^n W_{ijd} = 1\) for all documents $d$ and aspects $i$.

The *aspect rating* for a document $d$, denoted by $s_d$, is a $k$-dimensional vector where $s_{di} \in [r_{min}, r_{max}]$ is the rating for corresponding to aspect $i$. For example, a user might rate a hotel’s location as 4 (out of 5), but its cleaningness as 1.

The *aspect weight* for a document $d$, denoted by $\alpha_d$ is also a $k$-dimensional vector where $\alpha_{di} \in [0, 1]$ and $\sum_{i=1}^k \alpha_{di} = 1$ and represents the weight the review $d$ puts on aspect $i$. For example, a user might put more importance of location than price.

These are the two quantities the model will try to predict once it’s properly trainted. Note that for a document $d$:

\[(1) \quad r_d = \sum_{i=1}^{k} \alpha_{di} s_{di}\]We’ll gloss over the methodology for building the matrix $W_d$ and present it only at a high level. The idea is to seed each aspect with initial keywords. Then use a clustering algorithm to include more words into each of the aspects based on the reviews texts. Refer to [1] for more details.

The model defines a parameter $\beta$ representing the overall rating associated with a (word-aspect) pair. This can be thought of as the average rating a user would to aspect $i$ solely based on word $j$, so $\beta_{ij} \in [r_{min}, r_{max}]$.

Since \(\sum_{j=1}^n W_{ijd} = 1\), the model assumes that for document $d$ and aspect $i$, $s_{di}$ is a linear combination of $\beta_i$ and $W_{di}$:

\[(2) \quad s_{di} = \sum_{j=1}^n \beta_{ij} W_{dij}\]In theory $r_d$ can be obtained by (1), but to encode uncertainty and allow variance, the model assumes $r_d$ is drawn from a Gaussian distribution, with mean (1) and some variance $\delta$ which will be another parameter in the model.

\[r_{d} \sim N(\sum_{i=1}^{k} \alpha_{di} s_{di}, \delta^2)\]Exapanding $s_{di}$ using (2):

\[(3) \quad r_{d} \sim N(\sum_{i=1}^{k} \alpha_{di} \sum_{j=1}^{n} \beta_{ij} W_{dij}, \delta^2)\]The authors argue that aspect weights are not completely independent (e.g. a preference for cleaninliness is correlated with a preference for room, maybe less so for price).

To model this, we assume $\alpha_{d}$ is drawn from a multi-variate Gaussian distribution:

\[\alpha_{d} \sim N(\mu, \Sigma)\]where $\mu$ is a $k$ dimensional vector and $\Sigma$ a $k \times k$ variance matrix encoding the correlation between pairs of aspects.

Let’s bundle the parameters needed to compute $r_d$ into $\Theta = (\mu, \Sigma, delta^2, \beta)$. We then define the likelihood of observing $D$ (i.e. the overall and aspect ratings) as

\[p(D \mid \Theta)\]we need to find $\hat \Theta = \mbox{argmax}_\Theta \, p(D \mid \Theta)$.

We’ll use an interactive algorithm. We start with an initial estimate $\Theta_0$ for $\Theta$.

Because $\alpha_d$ is also considered a random variable, we can estimate it from $\Theta_t$. We then compute $\Theta_{t+1}$ assuming $\alpha_d$ is constant. We keep iterating until $\Theta_t$ converges.

Given a rating $r_{d}$, how can we estimate $\alpha_{d}$, that is $p(\alpha_d \mid r_d)$? In particular what is the most probable value of $\alpha_{d}$? We can use the *Maximum a Posteriori Estimate* (MAP) [2] method to find:

Which we show in *Appendix A*,

We can use a non-linear optimization such as L-BFGS to solve this, using the gradient of (4):

\[- \frac{(r_d - \alpha_d^T s_d) s_d}{\delta^2} - \Sigma^{-1} (\alpha_d - \mu)\]To estimate the $\Theta$ we’ll use *Maximum Likelihood Estimate* (MLE). Note that since there’s no constraint limiting each of $\mu$, $\Sigma$, $\beta$ and $\delta$, we can estimate them individually.

First we estimate $\mu$ and $\Sigma$ to maximize the likelihood of observing $\alpha$, $p(\alpha_1, \cdots, \alpha_D \mid \mu, \Sigma)$.

We show in *Appendix A* that if

then

\[\mu_{MLE} = \frac{1}{\mid D \mid} \sum_{d \in D} \alpha_d\]It can be shown [4] that if

\[\Sigma_{MLE} = \mbox{argmax}_{\mu} p(\alpha_1, \cdots, \alpha_D \mid \mu, \Sigma)\]then

\[\Sigma_{MLE} = \frac{1}{\mid D \mid} \sum_{d \in D} (\alpha_d - \mu_{MLE})(\alpha_d - \mu_{MLE})^{T}\]Summarizing, from a iteractive algorithm perspective, we’re given $\alpha$ computed previously and we can estimate the next iteration $\mu_{t+1}$ and $\Sigma_{t+1}$:

\[\mu_{t+1} = \frac{1}{\mid D \mid} \sum_{d = 1}^{\mid D \mid} \alpha_d\] \[\Sigma_{t+1} = \frac{1}{\mid D \mid} \sum_{d \in D} (\alpha_d - \mu_{t+1})(\alpha_d - \mu_{t+1})^{T}\]Now we estimate $\beta$ and $\delta^2$ to maximize the likelihood of observing $r$, $p(r_1, \cdots, r_D \mid \beta, \delta^2)$.

We show in *Appendix A* that if:

then

\[\delta_{MLE}^2 = \frac{r_d - \alpha_d^T s_d}{\mid D \mid}\]For $\beta$ we need to expand $\alpha_d^T s_d$ since it’s a function of $\beta$, that is $\alpha_d^T s_d = \sum_{i = 1}^{k} \alpha_{di} \beta_i^T W_{di}$. This give us:

\[\beta_{MLE} = \mbox{argmax}_{\beta} \sum_{d \in D} \log(\frac{1}{\delta \sqrt{2 \pi}}) - \frac{1}{2} (\frac{r_d - \sum_{i = 1}^{k} \alpha_{di} \beta_i^T W_{di}}{\delta})^2\]Discarding the terms independent of $\beta$:

\[\beta_{MLE} = \mbox{argmax}_{\beta} - \sum_{d \in D} (r_d - \sum_{i = 1}^{k} \alpha_{di} \beta_i^T W_{di})^2\]The authors claim the closed form of this optimization requires inverting a $n \times n$, which is costly. The proposal is to also used a non-linear optimization such as L-BFGS like we did for $\hat \alpha_{d}$. The $j$-th component of the gradient of the log-likelihood function above is:

\[\frac{\partial \mathcal{L}({\beta})}{\partial \beta_j} = \sum_{d \in D} \big( (r_d - \sum_{i = 1}^{k} \alpha_{di} \beta_i^T W_{di}) \alpha_{dj} W_{dj} \big)\]Summarizing, from a iteractive algorithm perspective, we’re given $\alpha$ computed previously and we can estimate the next iteration $\delta^2_{t+1}$ and $\beta{t+1}$:

\[\delta^2_{t+1} = \frac{r_d - \alpha_d^T s_d}{\mid D \mid}\]and

\[\beta_{t+1} = \mbox{LBFGS}(\beta_{t}, r, \alpha, s, W)\]In this post we studied the theory of the paper *Latent Aspect Rating Analysis on Review Text Data*. I also planned to work on a Python implementation but it will have to wait. It’s the first machine learning paper I can remember reading and it was interesting to see how much calculus is involved. I had past experience with linear (discrete and continuous) optimization, which involves mostly basic linear algebra.

In studying this post I had to watch many basic machine leaning math, via the mathematicakmonk channel. I also realized how rusty I am in regards to basic derivatives operations, so I’ll need a refresher.

- [1] Latent Aspect Rating Analysis on Review Text Data: A Rating Regression Approach
- [2] (ML 6.1) Maximum a posteriori (MAP) estimation - Youtube
- [3] (ML 4.1) Maximum Likelihood Estimation (MLE) - Youtube
- [4] Chapter 13 - The Multivariate Gaussian - Michael I. Jordan

Here we derive $\hat \alpha_{d}$ as a function of $\Theta$.

\[\hat \alpha_{d} = \mbox{argmax}_{\alpha_d} p(\alpha_d \mid r_d)\]Using Bayes’ Rule, we have

\[p(\alpha_d \mid r_d) = \frac{p(r_d \mid \alpha_d) p(\alpha_d)}{p(r_d)}\]Since $\log$ is a monotomic function and $p(r_d)$ does’t depend on $\alpha_{d}$, finding $\alpha_{d}$ that maximizes the above is equal to maximizing

\[\hat \alpha_{r_d} = \mbox{argmax}_{\alpha_d} \log p(r_d \mid \alpha_d) + \log p(\alpha_d)\]Let’s consider $p(r_d \mid \alpha_d)$ first. We know it’s the Gaussian with mean $\alpha_d^T s_d$ and variance $\delta^2$ (3), so by the definition of a Gaussian,

\[p(r_d \mid \alpha_d) = \frac{1}{\delta \sqrt{2 \pi}} \exp(-\frac{1}{2} (\frac{r_d - \alpha_d^T s_d}{\delta})^2)\]Applying log we get,

\[(5) \quad \log p(r_d \mid \alpha_d) = \log(\frac{1}{\delta \sqrt{2 \pi}}) - \frac{1}{2} (\frac{r_d - \alpha_d^T s_d}{\delta})^2\]The first term is independent of alpha, so we’re left with

\[\frac{(r_d - \alpha_d^T s_d)^2}{2 \delta^2}\]Let’s now look at $p(\alpha_d)$. It’a multi-variate Gaussian, so by definition:

\[(G) \quad p(\alpha_d) = \frac{\exp(-\frac{1}{2} (\alpha_d - \mu)^T \Sigma^{-1} (\alpha_d - \mu))}{\sqrt{(2 \pi)^{k} \mid \Sigma \mid}}\]Where $k$ is the dimension of $\alpha_d$, $\mu$ and $\Sigma$ ($k \times k$) and $\mid \Sigma \mid$ is the determinant of $\Sigma$. If we apply $\log$ and discard terms unrelated to $\alpha_d$ we get

\[-\frac{1}{2} (\alpha_d - \mu)^T \Sigma^{-1} (\alpha_d - \mu)\]Putting everything together, we want to find

\[(4) \quad \hat \alpha_{d} = \mbox{argmax}_{\alpha_d} \bigg[ - \frac{(r_d - \alpha_d^T s_d)^2}{2 \delta^2} -\frac{1}{2} (\alpha_d - \mu)^T \Sigma^{-1} (\alpha_d - \mu) \bigg]\]We have that

\(\mu_{MLE} = \mbox{argmax}_{\mu} p(\alpha_1, \cdots, \alpha_D \mid \mu, \Sigma) = \prod_{d \in D} p(\alpha_d \mid \mu, \Sigma)\).

Recalling $\alpha_d$ is sampled from a multi-variate Gaussian. Sing $\log$ is a monotonically increasing function, we can take the $\log$ on the right side of the equation:

\[\quad \mu_{MLE} = \mbox{argmax}_{\mu} -\sum_{d \in D} (\alpha_d - \mu)^T \Sigma^{-1} (\alpha_d - \mu)\]We can take the derivative of with respect to $\mu$ to obtain the gradient:

\[\sum_{d \in D} (\alpha_d - \mu) \Sigma^{-1}\]and set the gradient to 0 for which $\mu$ is optimal, and multiply both sides by $\Sigma$ to obtain:

\[0 = \sum_{d \in D} (\alpha_d - \mu)\]which implies

\[\sum_{d \in D} \mu = D \mu = \sum_{d \in D} \alpha_d\]so

\[\mu_{MLE} = \frac{1}{\mid D \mid} \sum_{d \in D} \alpha_d\]We have that

\[\delta_{MLE}^2 = \mbox{argmax}_{\delta^2} p(r_1, \cdots, r_D \mid \beta, \delta^2) = \prod_{d \in D} p(r_d \mid \beta, \delta^2)\]Since $\log$ is a monotomic function, we have,

\[\delta_{MLE}^2 = \mbox{argmax}_{\delta^2} \sum_{d \in D} \log p(r_d \mid \beta, \delta^2)\]Recalling $r_d$ is sampled from a univariate Gaussian (3) with some a mean that is a function of $\beta$ (say $f(\beta)$) and variance $\delta^2$ (3), so by the definition of a Gaussian,

\[p(r_d \mid \beta, \delta^2) = \frac{1}{\delta \sqrt{2 \pi}} \exp(-\frac{1}{2} (\frac{r_d - f(\beta)}{\delta})^2)\]Applying log,

\[\log p(r_d \mid \beta, \delta^2) = \log(\frac{1}{\delta \sqrt{2 \pi}}) - \frac{1}{2} (\frac{r_d - f(\beta)}{\delta})^2\]Putting it back in the original sum:

\[\delta_{MLE}^2 = \mbox{argmax}_{\delta^2} \mid D \mid \log(\frac{1}{\delta \sqrt{2 \pi}}) - \frac{1}{2\delta^2} \sum_{d \in D} (r_d - f(\beta))^2\]If we set $y = x^2$, $a = \mid D \mid$, $b = \sqrt(2\pi)$ and $c = \sum_{d \in D} (r_d - f(\beta))^2$ we can put it in a form that is easier to derive:

\[a \log(\frac{1}{\sqrt(y) b}) - \frac{c}{2y}\]If we derive on $y$,

\[- \frac{a}{2y} + \frac{c}{2y^2}\]Setting to 0, we can solve for $y$ to get:

\[y = \frac{c}{a}\]Replacing the terms back:

\[\delta_{MLE}^2 = \frac{\sum_{d \in D} (r_d - f(\beta))^2}{\mid D \mid}\]