Ordering Concepts Based on Common Attribute Intensity

1 Introduction

We make decisions every day by ordering two or more concepts on the basis of common knowledge or common sense to which we are privy. For example, imagine a situation in which we buy fruit juice. If we want something sweet to drink, we choose apple juice rather than lemon juice because we know that apples are generally sweeter than lemons.

The main objective of this study is to examine whether we can derive such common views on concept ordering from written text in social media, which reflect the perception of the crowd. Answering this question is not only interesting from a sociological perspective but also practically beneficial to those who want to order unfamiliar entities in terms of subjective attributes that are hard to quantify (e.g., ordering

⇤This work was done in part while the author was at the Institute of Industrial Science, the University of Tokyo.

Nobuhiro Kaji⇤

Yahoo Japan Corporation nkaji@yahoo-corp.jp

Masaru Kitsuregawa

National Institute of Informatics Institute of Industrial Science, the University of Tokyo kitsure@tkl.iis.u-tokyo.ac.jp

smartphones in terms of user-friendliness or ordering tourist areas in terms of fashionableness) in order to make a correct decision. To come up with convincing ordering, we are presently forced to spend a substantial amount of time reading massive amounts of text to sum up people's perceptions or call for votes from domain experts.

Considering these situations in mind, we propose a novel task of ordering nominal concepts in accordance with the intensity of their common attributes as specified by adjectives. A set of nominal concepts (e.g., ¶elephant, whale, dog, mouse♦) is provided in the proposed task, along with an adjective (e.g., large 1 ) that represents an attribute shared by all members of the set. Given these two inputs, our goal is to output an ordered list of the items. The expected output in this example is whale ≻ elephant ≻ dog ≻ mouse, where the whale is the largest, the elephant is the second largest, and so forth.

An issue to be addressed in performing this task is how to define a gold-standard, or goal ordering. Since a concept could refer to various instances that have different attribute intensities, and some attributes are subjective, it is inherently difficult to define an absolutely correct ordering agreed on by all. We therefore asked multiple volunteers to order a given set of concepts and then use the ordering that achieved the best average Spearman [1904]'s rank correlation coefficient, ⇢, against the human orderings as a gold-standard ordering. The resulting ordering can be seen as a representative ordering that sums up the general human perception, and is thereby meaningful as goal ordering in our task.

We present a method of ordering concepts to solve this task on the basis of textual evidence obtainable from massive amounts of social media text. The issues we address are twofold: (1) what kind of textual evidence to exploit and (2) how to integrate multiple kinds of evidence to obtain an appropriate ordering. We exploit heterogeneous textual evidence to address the first issue that indicates a possible ordering and then integrate this evidence to obtain an appropriate ordered list of the items. The types of evidence we used include noun-adjective (i.e., concept-attribute) cooccurrences, noun-adjective dependencies, similes, and comparative expressions on nouns. The first three indicate the absolute strength of the attribute intensity, while the last captures the relative strength among the attributes of concepts.

1 We provide an antonym of a given adjective (e.g., small) if any exists to reduce the ambiguity of the adjective.

We explore two approaches to integrating the heterogeneous evidence to address the second issue. The first uses a pairwise learning-to-rank framework, specifically, a ranking support vector machine (SVM) [Joachims, 2002], while the second directly estimates Spearman's ⇢ for each candidate order to output the ordering with the highest estimated Spearman's ⇢ as the most likely ordering using a support vector regression (SVR) [Drucker et al., 1997].

We performed experiments to evaluate our methods in terms of correlation between the system-generated and the gold-standard orderings for real-world concepts obtained from blog text. The results demonstrated that both our methods outperformed a co-occurrence-based baseline that was inspired by Turney [2002]'s work.

2 RelatedWork

To the best of our knowledge, there have been no attempts to order concepts on the basis of the intensity of their attributes. Related tasks are discussed in this section.

Question answering systems extract answers to factual questions (e.g., 'What is the average temperature in Tokyo?') from text [Prager, 2007]. Similarly, some researchers have attempted to extract objects' attributes and their values from the Web [Chen et al., 2000; Yoshida et al., 2003; Auer and Lehmann, 2007; Wu and Weld, 2007; Yoshinaga and Torisawa, 2007; Takamura and Tsujii, 2015]. These studies can partly help us to perform our task, particularly when we order concepts in terms of the intensity of objective and numerical attributes (e.g., largeness, heaviness, and expensiveness).

Aspect-based sentiment analysis mines reviews or other texts for opinions on entities (e.g., products or movies) [Pang and Lee, 2008]. Some of these studies have handled statements comparing multiple items (e.g., 'car x is two feet longer than car y' [Jindal and Liu, 2006]). Kurashima et al. [2008] proposed aggregating such statements to rank products in accordance with their popularity. This sort of information is also used with our method but is integrated with other evidence to obtain orderings for concepts that are not directly compared in texts. This strategy distinguishes our method from those proposed for aspect-based sentiment analysis.

In contrast to these studies, our task is more general in that it handles not only objective attributes (with numerical intensity, e.g., size [Takamura and Tsujii, 2015]) but also subjective attributes. Further, it handles not only entities (with specific values for attributes) but also concepts (with a range of values for attributes).

There have been a range of studies on aggregating pairwise comparisons (partial orderings) to a single consensus ordering [Bradley and Terry, 1952; Volkovs and Zemel, 2012; Niu et al., 2013; Chen et al., 2013; Raman and Joachims, 2014]. These studies assume pairwise comparisons that are prepared (e.g., search aggregation in meta-search or student evaluations via peer grading) or available from crowdsourcing, while we do not assume them in our task setting to increase the applicability of the method.

F˘ag˘ar˘as,an et al. [2015] proposed a method of inducing feature norms [McRae et al., 2005] for a concept from text, which we use to perceive the concept. The features include adjectives (e.g., 'is sweet' for sugar) but exclude ordering expressions (e.g., 'is larger than a pencil' for dog) so their task is complementary to our task, which helps us to suggest possible attributes for given concepts.

3 Method

We resort to massive amounts of social media text to collect textual evidence that validates our perception on concept ordering (Section 3.1) by assuming that our common views on concept ordering implicitly or explicitly affect the text we write. We then integrate that evidence to obtain a complete order of the concepts in the framework of supervised learning (Section 3.2).

3.1 Evidence on Concept Ordering

We exploit four types of evidence in this study to enable effective concept ordering. The first three implicitly suggest the absolute intensity of the attribute that the concept has. The fourth directly indicates a order of concepts, which captures the relative attribute intensity.

All pieces of evidence are represented by contexts where one or more concepts appear with a given adjective. The evidence is language-independent and we can tailor corresponding clue expressions for our target language, although our dataset is in Japanese. The example sentences that follow are provided in English to increase the applicability of our method and help reader understanding.

Noun-adjective co-occurrence If the intensity of the attribute of a concept is strong, we are likely to mention the attribute intensity along with the concept, which results in more sentences that include both the concept (noun) and the attribute (adjective).

Noun-adjective dependency A dependency relation between a nominative concept (noun) and an attribute (adjective) directly indicates the attribute intensity.

We used J.DepP [Yoshinaga and Kitsuregawa, 2009; 2010; 2014], 2 a state-of-the-art dependency parser, to extract such dependency relations. This evidence is less frequent but provides stronger evidence than cooccurrences, since co-occurrences do not always indicate the intensity of the attribute (e.g., 'Ants are so small that elephants cannot harm them').

2 http://www.tkl.iis.u-tokyo.ac.jp/⇠ynaga/jdepp/

Simile If the intensity of the attribute of a concept is salient, we refer to the concept in a simile.

• ÷ He is as brave as a lion .

We use a couple of lexico-syntactic patterns tailored to detect similes, 'ADJ as NP' and 'ADJ like NP' ('marude NP no you ni ADJ' in Japanese).

Comparative This evidence directly indicates an order of a subset of a concept set. For example, the sentence below indicates elephant ≻ dog.

We use dependency relations for comparative adjectives with clues studied in the literature [Jindal and Liu, 2006] (a post particle 'yori' in Japanese).

3.2 Two Approaches to Ordering Concepts

We explore two approaches to integrating the different types of heterogeneous evidence described in Section 3.1 to order concepts. The first uses a ranking support vector machine (SVM) [Joachims, 2002] to obtain an order and then induces concept-wise features from the evidence. The second uses a support vector regression (SVR) [Drucker et al., 1997], which learns a function that directly maps a given order to Spearman's ⇢ against gold-standard ordering and induces orderwise features for candidate ordering.

Ordering Concepts with Ranking SVM

In ranking SVM, we represent each item (here, concept) with concept-wise features and perform pairwise training that generates O(n2 ) training examples (feature vectors) from all the pairs of n concepts in the gold-standard order. The ranking SVM then solves an optimization problem that involves minimizing the number of incorrect partial orderings. Testing of the ranking SVM involves the dot product between feature and weight vectors for the input n concepts, and hence only requires O(n) time.

We encode the first three types of evidence described in Section 3.1 as real-valued features so that they directly indicate the attribute intensity of the concept. Generalizing Turney [2002]'s work that used the point-wise mutual information (PMI) of a pair of a word and 'excellent' (and 'poor') to compute the semantic orientation of the word, we measure the polarity of words in terms of attributes other than 'goodness.' We compute feature value, φ(x)cooc, for the noun-adjective co-occurrence of a noun-adjective pair, x = (noun↪ adj), as:

Here, adj refers to the antonym adjective or the adjective with negation. The feature values for dependency and simile are analogously computed, using co-occurrence counts based on dependency and simile.

We then encode the comparative expressions as two realvalued features so that they directly indicate the attribute intensity of the concept. For concept c and the adjective (here, large), we examine whether a comparative expression, 'c is larger than c0 ,' can be found for any other concept c0 (6= c) in the given set of concepts. We encode the number of c0 found in the expression divided by the number of items in the given concept set to obtain one real-valued feature, which indicates the positive intensity of the attribute. We analogously compute another real-valued feature by looking at a comparative expression, 'c0 is larger than c,' to express the negative intensity of the attribute.

Ordering Concepts with SVR

In SVR, we represent each possible ordering by order-wise features and then directly map it to a real-valued measure. The SVR can incorporate the evaluation measure into the ordering process and directly optimize an ordering by outputting the ordering with the maximum estimated measure. We use Spearman's ⇢ against the gold-standard order as a target variable for regression.

An issue to be addressed here is how candidate orderings for training and testing SVR are generated. There are factorial orders of candidate orderings, n!, for a given set of n concepts. As we do not need to use all the possible orderings in training, we adopted a Monte Carlo method that randomly samples only a tractable number of orderings from all possible permutations of the given concept set. We extract the same number of candidate orderings from each concept set to obtain balanced training data, and that number is set to nmin!, where nmin is the smallest number of members of all the concept sets in the training data. There were up to eight concepts for ordering in the experiments that follow, considering the annotation cost to order concepts and a typical application scenario where users order concepts that are chosen (or narrowed down) from candidates a priori. We thus consider all possible candidate orderings in testing to understand the maximum performance of this approach. We can greedily add one remaining concept to the (ordered) list by choosing the best insertion position in accordance with the SVR value of the resulting ordering in testing with a set of a large number of concepts, starting from an empty list. This requires O(n2 ) time.

We induce real-valued features from the first three types of evidence described in Section 3.1 for the candidate ordering. We count the number 3 of ordered pairs (c, c0 ) for which the SOadj cooc (c) is larger than SOadj cooc (c0 ), of all the ordered pairs in the candidate ordering. This is used to examine the extent to which pairwise orderings in the candidate ordering conform to the ordering specified by SOadj cooc . The feature values for dependency and simile are analogously computed using cooccurrence counts based on dependency and simile.

We then induce two real-valued features from comparative expressions by counting the number3 of ordered pairs (c, c0 ) in which c's intensity is larger (or smaller) than c0 's, in all the ordered pairs in the candidate ordering for the given adjective. Here, we assume the attribute intensity of a concept is given by the corresponding feature value in the ranking SVM. A larger feature value means that the candidate ordering satisfies (or dissatisfies) more partial orders found in the text.

3 These numbers are normalized by dividing them by the number of all the ordered pairs in the candidate ordering.

same semantic category. Next, we associated each set of concepts with one or two adjectives that represented common attributes by examining the average PMI between the adjective and each concept, ultimately obtaining 35 pairs of a set of concepts and adjective (Table 1). There were 7.0 concepts per set on average and 28 unique sets of concepts (seven sets of concepts are associated with two adjectives). The resulting dataset included general to specific concepts (or instances) in various open-domain categories, and objective to subjective attributes for ordering that varied from one category to another.

4 Experiments

We performed experiments to evaluate our methods with open-domain datasets in terms of correlation between the system-generated and gold-standard orderings. We used LIBLINEAR [Fan et al., 2008] 4 as implementations of ranking SVM and SVR (with all hyper-parameters respectively tuned by cross-validation on training data).

4.1 Data

We used around 260 million Japanese blog articles, which we have crawled since 2006, to build a dataset for evaluation and obtain the statistics for our methods. The blog articles consist of around two billion sentences written by more than a million users.

We built an evaluation dataset for this task from the blog articles to include real-world concepts that are often absent in handcrafted ontologies such as WordNet. We first applied word clustering [Brown et al., 1992] to one tenth of the blog articles in 2009 and obtained word clusters. We then looked into each cluster to manually collect nominal concepts in the We then asked seven volunteers (three graduate students, three researchers including the second author, and one system engineer) to provide an ordering for each pair of concepts and attribute. We regarded an ordering, in all permutations of concepts, that maximized the average of Spearman [1904]'s rank correlation coefficient, ⇢, 5 against the seven human orderings, to be a gold-standard ordering. The gold-standard ordering we obtained is listed in Table 1.

4 https://www.csie.ntu.edu.tw/⇠cjlin/liblinear/

5 Spearman's ⇢ measures the strength of the correlation between two ordered lists. It ranges from -1 to 1. The negative value indicates an inverse correlation.

We computed Spearman's ⇢ between an ordering created by each of the seven subjects and the gold-standard ordering for each concept set to find the agreement between each human ordering and the gold-standard ordering. The results are summarized in a box-and-whisker diagram (Figure 1). We should state that the average Spearman's ⇢ between each human ordering and the gold-standard ordering was 0▷75, which indicates a strong correlation.

We can see that the average Spearman's ⇢ between each human ordering and the gold-standard ordering is larger than 0▷4 for all the pairs of concepts and adjective, larger than 0▷6 for 30 pairs except for 'sports (entertaining),' 'mammal (clever),' 'instrument (soothing),' 'vegetable (tasty),' and 'coffee shop (likable),' and even larger than 0▷8 for 15 pairs that included subjective ones such as 'programming (easy),' 'bird (cute),' and 'temple (famous),' which confirms that the perception of the relative intensities of common attributes is largely shared by human subjects. This demonstrates that the gold-standard ordering is appropriate as a common view, shared by human volunteers, on ordering for each pair.

4.2 Results

We conducted leave-one-out cross-validation using the evaluation dataset described in Section 4.1. The appropriateness of the system-generated orderings was then measured by computing Spearman's ⇢ between the system-generated and goldstandard orderings. The experimental results are listed in Table 2. Here, HUMAN refers to the average Spearman's ⇢ between each human ordering and the gold-standard ordering, while BASELINE refers to a method that scores each concept by using the PMIs of noun-adjective co-occurrences for the given adjective and its antonym (SOadj cooc , i.e., Eq. 1), as was done in Turney [2002]'s work. SVM and SVR refers to our methods based on ranking SVM and SVR (Section 3.2), respectively. The results revealed that our methods overwhelmed the baseline, which indicated the effectiveness of integrating heterogeneous evidence in a supervised manner. Ranking SVM achieved the best average performance and indicated a positive correlation for all pairs other than 'country (safe),' 'automaker (healthy),' and 'browser (friendly).'

Table 3 shows an ablation test that evaluates the impact of individual pieces of evidence in ranking SVM. All the ev-

-comparative

Table 3: Ablation test for ranking SVM.

idence contributed to improving the correlation against the gold-standard orderings. The simile most significantly affects the performance, followed by noun-adjective co-occurrences and dependencies. This conforms to our expectation since similes are useful for finding concepts with strongest (or weakest) attribute intensity, which greatly contributed to the improvement of Spearman's ⇢ against the gold-standard orderings. The comparative expressions are rarely observed in the text, so that had the least impact.

We manually investigated the system-generated orderings to identify which evidence had contributed to the orderings. Table 4 lists examples of system-generated orderings. Nounadjective dependencies between concept (noun) and famous in the ordering of 'MLB team (famous)' raised the ordering of SEA and NYY, so the resulting orderings of our systems correlated with the gold-standard ordering. Similes in the ordering of 'fruit (small)' greatly contributed to improving the ordering of cherry (to top-1), which again increased the performance of our systems. Comparative expressions in the ordering of 'programming (easy)' contributed to raising the ordering of Java, which again increased the performance of our systems. These changes suggest that the use of heterogeneous evidence increases the chances of reaching ordering that has a higher correlation with the gold-standard ordering, which justifies our approach to integrating the pieces of evidence in a supervised manner.

The low correlation in 'country (safe)' and 'automaker (healthy)' was caused by their status changes over our timeseries text. As for 'browser (friendly),' similes and comparative expressions were not observed, and this data sparseness reduced the correlation. There were also some difficult cases in gathering reliable evidence. For example, we sometimes mention unusual and surprising things such as "The mice around here are large," which have a negative impact on ordering concepts.

5 Conclusion

We have initiated a novel task of ordering concepts on the basis of the intensity of their common attributes and proposed methods of ordering a given set of concepts by aggregating heterogeneous pieces of evidence obtained from massive amounts of social media text. As the experimental results obtained from real-world concepts revealed a strong correlation between the system-generated and gold-standard orderings, we could induce common views on ordering concepts from texts written by the crowd. These results are not only interesting from the sociological perspective but are also beneficial in practice since they would help us make decisions from among alternative concepts in daily life.

This research has involved various directions for productive future research. First, we plan to support more specific and diverse attributes that are described by phrases other than adjectives (e.g., easy to cook) to order concepts (e.g., recipes). Since supporting more specific attributes makes the data sparseness problem more serious, we are going to incorporate correlations between attribute intensities (e.g., heavier concepts are likely to be larger, or more expensive concepts are likely to have better quality). Next, we intend to apply our method to text written in different periods (in 2014 vs. in 2015), in different geographical areas (Japan vs. UK), or by different demographics (people in their 30's vs. 50's or males vs. females), to observe changes in common views over time or place, or by different demographics.

We will release the evaluation dataset (Table 1) with human orderings and the experimental codes for the academic and industrial communities at http://www.tkl.iis.u-tokyo.ac. jp/⇠nari/ijcai-16/ to facilitate the reproducibility of our results and their use in various application contexts.

Acknowledgments

This work was partially supported by JSPS KAKENHI Grant Number 25280111, 16K16109 and 16H02905. The authors wish to thank the volunteers for their hard work. The authors also thank the anonymous reviewers for their valuable comments.