Opinion Target Extraction Using Partially-Supervised Word Alignment Model

1 Introduction

In recent years, mining opinions and analyzing sentiments in online reviews becomes useful and has attracted a lot of attentions from many researchers [Hu and Liu, 2004b; Li et al., 2012; Zhang et al., 2010; Liu et al., 2012]. In opinion mining, one fundamental problem is to extract opinion targets, which are defined as the objects on which users have expressed their opinions, typically as nouns or noun phrases. This task is very important because customers are usually not satisfied with just the overall sentiment polarity of a product, but expect to find the fine-grained sentiments about an aspect or a product feature mentioned in reviews.

∗Kang Liu and Liheng Xu have equal contribution to this work

To fulfill this task, existing studies usually regarded opinion words as strong indicators [Popescu and Etzioni, 2005; Hu and Liu, 2004a; Bing et al., 2005; Qiu et al., 2011]. This strategy is based on the observation that opinion words are usually used to modify opinion targets, and there are opinion relations and associations between them. For example, "wonderful" and "fantastic" are usually used to modify "design" about cell-phone in reviews, so there are strong associations between them. If "wonderful" and "fantastic" had been known to be opinion words, "design" is likely to be an opinion target in this domain. Meanwhile the extracted opinion targets can be used to expand more opinion words. It is a mutual reinforcement procedure.

Therefore, mining opinion relations in sentences and estimating associations between opinion words and opinion tar-

methods designed some heuristic patterns based on syntactic parsing [Popescu and Etzioni, 2005; Qiu et al., 2009; 2011]. However, online reviews usually have informal writing styles including grammar mistakes, typos, improper punctuation etc., which make parsing be prone to generate mistakes. As a result, these syntax-based methods which heavily depended on the parsing performance would suffer from parsing errors and often don't work well. To resolve this problem, [Liu et al., 2012] formulate identifying opinion relations between words as an alignment process. An opinion target can find its corresponding modifier through monolingual word alignment model (WAM) without using parsing, so that the noises from parsing errors can be effectively avoided. Experimental results have reported that their method have better performance than syntax-based methods, especially for large corpora.

Nevertheless, we notice that WAM used in Liu's method are trained in a completely unsupervised manner, which makes the alignment quality still unsatisfactory. Although we can improve the alignment performance by using the supervised framework [Moore, 2005], manually labeling full alignment for sentences is still time-consuming and impractical. However, in many situations, we can easily obtain a portion of links of the full alignment in a sentence. They can be used to constrain the alignment process, which is a partiallysupervised alignment problem. We argue that it would benefit to improving the alignment performance. For example in Figure 1, "colorful" is incorrectly regarded as the modifier for "phone" if the WAM is performed in an whole unsupervised manner ((a) in Figure 1). However, we can assert "colorful" should be aligned to "screen" ((b) in Figure 1). Then the errors in (a) can be corrected by using this partial links to supervise the statistical model, as shown in (c) in Figure 1.

Thus, in this paper, we propose a novel approach to extract opinion targets by using partially-supervised word alignment model (PSWAM). We first use some high-precise-low-recall syntactic patterns to capture partial opinion relations (partial alignment links) in sentences. Although existing syntactic parsing algorithms cannot obtain the precise whole syntactic tree of the informal sentences, we believe some short or direct dependency relations between words can be still obtained precisely. Then these extracted partial alignment links would be regarded as ground truths. And an constrained EM algorithm based on hill-climbing is performed to determine all alignments in sentences, where the model will be consistent with these links as far as possible. In this way, more correct opinion relations can be mined. Our model can not only inherit the advantages of word alignment model: considering multiple factors (word co-occurrence frequencies, word positions etc.) in the global process, effectively avoiding noises from syntactic parsing errors when dealing with informal texts, but also can improve the mining performance by using partial supervision. Thus, it's reasonable to expect that PSWAM is likely to yield better performance than traditional methods.

Then we extract opinion targets in a graph-based framework based on the mined associations. All nouns (noun phrases) are regarded as opinion target candidates. A bipartite graph is constructed to model the opinion relations between words. We assume that two candidates are modified by similar opinion words, they are likely to belong to the similar category. If we have known one of them is an opinion target, the other one has high probability to be an opinion target. Thus, the opinion target confidence can propagate among vertices. A random walk algorithm can be applied to estimate the confidence of each candidate, and the candidates with higher confidence will be extracted as the opinion targets. However, in traditional random work algorithm, we observe that the higher-degree vertices are prone to collect more information from other vertices and put more impacts on other vertices. These words usually are general words and may introduce noises. For example, the opinion word "good", may be used to modify multiple objects like "good design", "good feeling" and "good things". The degree of "good" will be high in the graph. If we have know that the "design" has higher confidence to be an opinion target, it's confidence will be propagated to "feeling" and "thing" through "good". As a result, "feeling" and "thing" will probably to be given higher confidence as opinion targets. It's unreasonable. To resolve this problem, we make penalty on the higher-degree vertices to weaken the impacts of them and decrease the probability of the random walk running into the unrelated regions in the graph. In this way, errors can be effectively avoided.

The experimental results on three datasets with different sizes and languages show that our approach can achieve performance improvement over the traditional methods.

2 RelatedWork

Previous studies focused on opinion target extraction, such as [Hu and Liu, 2004b; Ding et al., 2008; Li et al., 2010; Popescu and Etzioni, 2005; Wu et al., 2009], can be divided into two main categories: supervised and unsupervised methods. In supervised approaches, the opinion target extraction task was usually regarded as a sequence labeling task [Jin and Huang, 2009; Li et al., 2010; Ma and Wan, 2010; Wu et al., 2009]. The main limitation of these methods is that labeling training data for each domain is time consuming and impracticable. In unsupervised methods, similar to ours, most approaches regarded opinion words as the important indicators for opinion targets. [Hu and Liu, 2004a] exploited an association rule mining algorithm and frequency information to extract frequent explicit product features in a bootstrapping process. [Popescu and Etzioni, 2005] designed some syntactic patterns to extract opinion targets. [Qiu et al., 2011] proposed a Double Propagation method to expand sentiment words and opinion targets iteratively, where they also exploited syntactic relations between words. The main limitation of Qiu's method is that the patterns based on dependency parsing tree may introduce many noises for the large corpora. [Zhang et al., 2010] extended Qiu's method. Besides the patterns used in Qiu's method, they adopted some other special designed patterns to increase recall. In addition they used the HITS [Kleinberg, 1999] algorithm to compute opinion target confidences to improve the precision. [Liu et al., 2012] is similar to our method, they use a completely unsupervised WTM to capture opinion relations in sentences. Then the opinion targets were extracted in a standard random walk framework where two factors were considered: opinion relevance and target importance.

3 Mining Associations between Opinion Targets and Opinion Words using Partially Supervised Word Alignment Model

As mentioned in the first section, we first need to identify potential opinion relations in sentences and estimate associations between opinion targets and opinion words. Similar to Liu's method [Liu et al., 2012], we formulate this task as a monolingual word alignment process. We assume opinion targets to be nouns or noun phrases, and opinion words may be adjectives or verbs. Every sentence is replicated to generate parallel corpus, and the word alignment algorithm is applied to the monolingual scenario to align a noun (noun phase) with its modifiers for mining opinion relations in sentences. Thus, given a sentence with n words S = {w1,w2, ...,wn}, the word alignment A = {(i, ai)|i ∈ [1, n], ai ∈ [1, n]} can be obtained as A∗ = argmax A P(A|S), where (i, ai) means that a noun (noun phrase) at position i is aligned with its modifier at position ai. For alignment model, we select IBM-3 [Brown et al., 1993] which has been proved to have better performance than other models [Liu et al., 2012]. So we have

where t(wj|waj ) models the co-occurrence information of two words in corpora. If a word modifies a noun (noun phrase) frequently, they will has higher value of t(wj|waj ). d(j|aj, n) models word position information, which describes the probability of a word in position aj aligned with a word in position j. And n(φi|wi) describes the ability of a word for "one-to-many" relation which means that a word can modify (be modified by) several words. φi denotes the number of words that are aligned with wi.

3.1 Partially-SupervisedWord Alignment Model

To improve alignment performance, we make partial supervision on the statistic model and incorporate partial alignment links into the alignment process. Here, the partial alignment links are regarded as the ground truth and the constrains for the alignment model. Given the partial alignment links ˆ A = {(i, ai)|i ∈ [1, n], ai ∈ [1, n]}, the optimal word alignment A∗ mentioned above is rewritten as follows.

Because of the lack of the labeled full alignment data, we employ constrained EM algorithm to train the model parameters. In the E-step, we collect the statistics from all possible alignments, and ignore the evidences which are inconsistent with the ground truth to guarantee that no statistic from inconsistent alignments is collected for model parameter estimation. Thus we have

where λ is the smoothing factor which means that we make soft constraints on the alignment model, and some incorrect partial alignment links generated through high-precision patterns (Section 3.2) may be revised possibly. Then, in Mstep, we make count collections and normalize to produce the model parameters for the next iteration.

In practice, we can easily perform constrained EM algorithm as Equation (3) for simpler models such as in IBM1, IBM-2, by ruling out the inconsistent evidences. However, for IBM-3 model, because of the consideration of fertility of the words, enumerating all possible alignments is NP-complete [Gao et al., 2010]. Thus GIZA++ [Och and Ney, 2003] provides a greedy hill-climbing algorithm to resolve this problem. To improve the speed of hill climbing, the search space is constrained on the "neighbor alignments" defined as the alignments that can be generated from current alignment by one of the operators: 1) Move operator mi,j, which changes aj = i; 2) Swap operator sj1,j2 , which exchanges aj1 and aj2 . Specially, two matrix respectively called Moving Matrix M and Swapping Matrix S are introduced which record all possible move and swap costs between two different alignments.

To incorporate the partial alignment links into IBM-3 model as constrains, we adopt the algorithm of [Gao et al., 2010] which includes three main steps: 1) We first train a simple alignment model (IBM-1, IBM-2, HMM etc.) for generating initial alignments for IBM-3 model; 2) Then, we update the initial alignment model to make it consistent to the partial alignment links; 3) We finally optimize the alignment under the constraints iteratively by employing operation matrix M and S, where we set the corresponding cost value of the invalid operation in M and S to be negative, so that the invalid operators will never be picked.

Moreover, to capture opinion relations in sentences, we only focus on alignment between opinion target candidats (nouns/noun phrases) and potential opinion words (adjectives/verbs). If we directly use the alignment model, a noun (noun phrase) may align with other unrelated words, like prepositions or conjunctions and so on. Thus, in our model, we introduce other constrains: 1) Nouns/noun phrases (adjectives/verbs) must be aligned with adjectives/verbs (nouns/noun phrases) or null words. Aligning to null words means that this word has no any modifier or modifies nothing; 2) Other unrelated words can only align with themselves.

From the alignment results, we can obtain a set of word pairs composed of a noun (noun phrase) and the corresponding modified words. Then the alignment probabilities between potential opinion target wt and potential opinion word wo can be estimated using P(wt|wo) = Count(wt,wo) Count(wo) , where P(wt|wo) means the alignment probabilities between two words. Similarly, we can obtain alignment probability P(wo|wt) if we change the alignment direction in the alignment process. Then, the association between an opinion target candidate and its modifier is estimated as follows.

where α is the harmonic factor to combine these two alignment probabilities, and we set α = 0.5.

3.2 Obtaining Partial Alignment Links

The other important problem is how to obtain partial alignment links for our PSWAM. We resort to manually labeling. But this strategy is time-consuming and isn't suitable for multiple domains. Therefore, as mentioned in the first section, we make use of some high-precision-low-recall syntactic patterns to capture the dependency relations between words for generating initial partial alignment links. Then these initial links will be feeded into the alignment model.

To guarantee the used syntactic patterns to be highprecision, we constrain that the syntactic patterns only capture direct dependency relations which is defined in [Qiu et al., 2011]. A direct dependency indicates that one word depends on the other word without any additional words in their dependency path or these two words both depend on a third word directly. As shown in the left part ((a) and (b)) of Figure 2, A directly depends on B in (a), and A and B both directly depend on C in (b). [Qiu et al., 2011] also defined some indirect dependency relations. We don't use them because introducing indirect dependency relations may decrease the precision. Specifically, we employ Minipar 1 as the sentence parser. The right part in Figure 2 shows the used syntactic patterns corresponding to two direct dependency relation types. A is potential opinion words, where {O} = {adjective, verb}. B is potential opinion target words, where {T } = {noun, nounphrase}. C is any words. Moreover, to obtain precision alignment links, we constrain the dependency relation labels in our patterns to be R1 = {mod, pnmod} and R2 = {subj}, where mod, pnmod and subj is the dependency relation labels output by Minipar.

4 Estimating Candidate Confidence

After mining the associations between words, we compute the confidence of each opinion target candidate, and the candidates with higher confidence will be extracted as the opinion targets. Here, opinion words are regarded as the important indicators. We assume that two candidates are likely to belong to the similar category, if they are modified by similar opinion words. If we have known the one of them to be an opinion target, the other one has high probability to be an opinion target. Thus, we can forward the opinion target confidences among different target candidates through opinion words, which indicates that existing graph-based algorithms are applicable.

To model the mined associations between words, we construct a bipartite graph, which is defined as a weighted undirected graph G = (V,E,W). It contains two kinds of vertex: opinion target candidates and potential opinion words, respectively denoted as vt ∈ V and vo ∈ V . As shown in Figure 3, the white vertices represent opinion target candidates and the gray vertices represent potential opinion words. An edge evt,vo ∈ E between vertices represents that there is an opinion relation, and the weight w on the edge represents the association between them, which are obtained using Eq. (4).

1 http://webdocs.cs.ualberta.ca/lindek/minipar.htm

To estimate opinion target confidence, we employ a random walk based algorithm named as Adsorption [Baluja et al., 2008; Talukdar et al., 2008] on our graph. In Adsorption, each vertex has two roles, forwarding confidences and collecting confidences. The algorithm iteratively computes the weighted average of opinion target confidences from neighboring vertices, then uses the random walk to estimate the confidences of other vertices. However, as mentioned in the first section, in the standard randomwalk process, the higherdegree vertices will usually have more impacts on other vertexes, which may introduce noises. Therefore, we make modification on Adsorption and put penalty on these higherdegree vertices in the random walk process to decrease the probability of generating errors. Specifically, when the random walk reaches a target vertex v, we believe that there are three choices: (a) continue the randomwalk to the neighbors of v; (b) abandon the random walk; (c) stop the walk and emit a confidence according to the prior knowledge. We assume the probabilities of these three events are Pcon(v), Pabnd(v) and Pinj(v) respectively. Thus we have

where Li+1 v represents the opinion target confidence estimation of v in the i + 1th iteration. And

which is the weighted average confidence for vertex v in the ith iteration entirely based on its neighbors' confidence. And Iv is defined as the prior confidence of each candidate for opinion target. Similar to [Liu et al., 2012], we set Iv = tf(v)idf(v) ∑v tf(v)idf(v) , where tf(v) is the term frequency of v in the corpus, and df(v) is computed by using the Google n-gram corpus 2 . Lφ represents lack of information about the opinion target confidence of the vertex v. Pabnd(v) is used to mitigates the effect of the transition into unrelated region in the graph when reaching higher-degree vertex [Talukdar et al., 2008]. Moreover, we adopt the heuristics from [Talukdar et al., 2008] to set the random walk probabilities. Let cv = log(β) log(β+exp(H(v))) and β = 2. H(v) = - ∑u puv × log(puv) denotes the entropy of vertex v, where puv = W(u,v) ∑u W(u,v) . If v has higher degree, H(v) will be higher and cv will be lower. In this way, the contribution of higher-degree vertices will be restricted. And jv = (1 - cv) × √H(v).

zv = max(cv + jv, 1). Therefore, we can set

The algorithm is ran until convergence which is achieved when the confidence on each node ceases to change in a tolerance value. Finally, the candidates with higher confidence will be extracted as opinion targets.

2 http://books.google.com/ngrams/datasets

• Liu is the method described in [Liu et al., 2012], which used unsupervised WAM to mining the associations between words. Then a standard random walk based algorithm is exploited to estimate the candidate confidences for extracting opinion targets.

The parameter settings in these baselines are the same as the settings in original papers. The overall performance results are respectively shown in Table 1, 2 and 3, where "P" denotes precision, "R" denotes recall and "F" denotes F-measure. Ours denotes our method, in which we use partially-supervised word alignment model to identify opinion relations in sentences, and a modified graph-based algorithm to extract opinion targets. We set φmax = 2 in Eq.(1). From the experimental results, we can obtain the following observations.

1. Ours outperforms other baselines in most datasets. This indicates that our method based on PSWAM is effective for opinion target extraction.
2. The methods based on word alignment model (Ours and Liu) achieves performance improvement over other baselines, especially outperforming syntax-based methods (DP and Zhang). It indicates that the methods based on the word alignment model, which formulate identifying opinion relations as an alignment process, can effective avoid parsing errors for informal texts on the Web without using parsing. So it can mine more precise opinion relations from sentences. The similar observation is also obtained by [Liu et al., 2012].
3. Moreover, Ours outperforms Liu. We believe there are two reasons. First, Ours identifies opinion relations by performing WAM under partial supervision. We employ high-precision syntactic patterns to obtain partial alignment links and regard them as constrains for supervising alignment model. This strategy is effective for improving the precision of opinion relations identification. Second, to estimate the confidence of each candidate in the graph, we make penalty on the higher-degree vertices to decrease the probability of the random walk running into the unrelated regions. In this way, some errors can be effectively avoided, so that the precision can be improved further.
4. In Table 3, Ours makes comparable results with baselines in Customer Review Datasets, although there is a little loss in precision in some domains. We believe the reason is that the size of Customer Review Datasets is too small. As

5 Experiments

5.1 Datasets and EvaluationMetrics

We select three datasets which were already used in [Liu et al., 2012] to evaluate our approach. The first dataset is COAE2008 dataset2 3 , which contains Chinese reviews about four kinds of products including camera, car, laptop and phone. The second dataset is Large, which includes three corpora with different languages from three domains including hotel, mp3 and restaurant. The detailed statistical information of these two datasets can be found in [Liu et al., 2012]. The third dataset is Customer Review Datasets including English reviews of five products, which was also used in [Hu and Liu, 2004a; Qiu et al., 2011]. The detailed information can be found in [Hu and Liu, 2004a].

In the experiments, reviews are first segmented into sentences according to punctuation. Then sentences are tokenized, part-of-speech tagged by using Stanford NLP tool 4 , and parsed by using Minipar toolkit. The method in [Zhu et al., 2009] is used to identify noun phrases. We select precision, recall and F-measure as the evaluation metrics.

5.2 Our Methods vs. State-of-the-art Methods

For comparison, we select the following the state-of-the-art methods as baselines.

• Hu is the method described in [Hu and Liu, 2004a], which extracted frequent opinion target words based on association mining rules.
• DP is the method proposed by [Qiu et al., 2011], which used syntax-based patterns to capture opinion relations in sentences, and used Double Propagation algorithm to extract the opinion targets.
• Zhang is the method proposed by [Zhang et al., 2010], which is an extension of DP. They extracted opinion targets candidates using syntactic patterns and other specific patterns. Then HITS [Kleinberg, 1999] algorithm combined with candidate frequency is employed to rank the results for opinion target extraction.

3 http://ir-china.org.cn/coae2008.html

4 http://nlp.stanford.edu/software/tagger.shtml

a result, word alignment model may suffer from data sparseness for association estimation. Nevertheless, the average recall is improved. Moreover, compared the results in Table 1 with the results in Table 2, we can observe that Ours may obtains larger improvements with the increase of the data size, which indicates the proposed method is more appropriate for larger corpora.

5.3 Effect of Partially-SupervisedWord Alignment Model

In this subsection, we aim to prove the effectiveness of our PSWAM for capturing opinion relations in sentences. For comparison, we design two baselines, named as Syntax and WAM. They respectively use syntactic patterns used in Section 3.2 and unsupervised WAM of [Liu et al., 2012] to identify opinion relations in sentences. Then the same method Eq.4) is used to estimate associations between opinion targets and opinion words. At last the same graph-based algorithm proposed in Section 4 is used to extract opinion targets. Due to the limitation of the space, the experimental results only on COAE2008 dataset2 and Large are shown in Figure 4.

In Figure 4, we observe that Syntax has better precision but worse recall than other two methods based on word alignment model (Ours and WAM). It's because that Syntax exploiting high-precision-low-recall syntactic patterns can only capture the part of opinion relations in sentences, which may lose many potential opinion targets. On the other side, (Ours and WAM) can capture more opinion relations by using word alignment model, so that they have better recall. Moreover, Ours outperforms WAM. It's because that alignment performance is improved under the partially supervised framework, which uses high-precision partial alignment links as the constrains. Thus, it can not only make significant improvements on recall, but obtain competitive performance on precision compared with Syntax, which proves the effectiveness of our PSWAM.

5.4 Effect of Our Graph-basedMethod

In this experiment, we aim to prove the effectiveness of our graph-based method for opinion target extraction. We design two baselines, named as PSWAM HITS and PSWAM RW. Both of them also use PSWAM to mine associations between opinion targets and opinion words. Then, PSWAM HITS uses the HITS algorithm used in [Zhang et al., 2010] to extract opinion targets. PSWAM RWuses the the randomwalk algorithm used in [Liu et al., 2012] to extract opinion targets. Figure 5 gives the experimental results on COAE2008 dataset2 and Large. In Figure 5, we can observe that our graph-based algorithm outperforms other approaches. We believe the main reason is that we make penalty on the higherdegree vertices in the graph according to the vertex entropy to decrease the probability of the random walk running into the unrelated regions. Some errors introduced by general words can be filtered, so that the performance can be improved.

6 Conclusions and FutureWork

This paper proposes a novel approach to extract opinion targets by using PSWAM. Compared with previous syntaxbased methods, PSWAM can effectively avoid parsing errors when dealing with informal sentences in online reviews. And, compared with the methods using unsupervised alignment model, PSWAM can capture opinion relations more precisely under the constrains of partial alignment links. The experimental results proves the effectiveness of our method. In future work, we wouldn't extract opinion targets only using opinion relations. Other semantic relations, such as topical assocations, can be employed, which is expected to benefit for performance improvement.

Acknowledgement

This work was supported by the National Natural Science Foundation of China (No. 61070106, No. 61272332 and No. 61202329), the National High Technology Development 863 Program of China (No. 2012AA011102), the National Basic Research Program of China (No. 2012CB316300), Tsinghua National Laboratory for Information Science and Technology (TNList) Cross-discipline Foundation and the Opening Project of Beijing Key Laboratory of Internet Culture and Digital Dissemination Research (ICDD201201).