Using Collaborative Filtering to Model Argument Selection (2021)

Abstract: This study evaluates whether model-based Collaborative Filtering (CF) algorithms, which have been extensively studied and widely used to build recommender systems, can be used to predict which common nouns a predicate can take as its complement. We find that, when trained on verb-noun co-occurrence data drawn from the Corpus of Contemporary American-English (COCA), two popular model-based CF algorithms, Singular Value Decomposition and Non-negative Matrix Factorization, perform well on this task, each achieving an AUROC of at least 0.89 and surpassing several different baselines. We then show that the embedding-vectors for verbs and nouns learned by the two CF models can be quantized (via application of k-means clustering) with minimal loss of performance on the prediction task while only using a small number of verb and noun clusters (relative to the number of distinct verbs and nouns). Finally we evaluate the alignment between the quantized embedding vectors for verbs and the Levin verb classes, finding that the alignment surpassed several randomized baselines. We conclude by discussing how model-based CF algorithms might be applied to learning restrictions on constituent selection between various lexical categories and how these (learned) models could then be used to augment a (rule-based) constituency grammar.

## introduction in learning a language, a child solves many difficult puzzles using limited input data (berwick et al., 2011; piattelli-palmarini and berwick, 2012; lasnik and lidz, 2017). one such puzzle involves the child deciding whether a given verb can take a particular noun as its complement when the child has never previously observed that verb and that noun co-occur in a sentence. to illustrate this puz-zle, let us consider an example -suppose the child learner has heard the following sentences: (a) "i lied and and said that i would not smash the windshield." (b) "the robber was not planning to smash every plate." (c) "i want to take this hammer and smash the precious vase!" (d) "they are going to shatter the windshield!" (e) "the boy who was busy staring at his phone will trip over and shatter his mother's favorite plate." (f) "did you shatter the blue vase?" (g) "she knew that susan would break her expensive new windshield." (h) "i saw the man in the red sweater break the delicate plate." now suppose that the child learner has never heard a sentence in which the verb "break" takes the noun "vase" as its complement. how should the child decide whether the following production is licit? (i) "he is going to trip over and break the vase!" one strategy that the child might employ is as follows. first the child observes that the verbs "smash" and "shatter" behave similarly by noting that both verbs can select any of the three nouns "windshield", "plate" and "vase" as a complement (see sentences (a-c) for "smash" and sentences (d-f) for "shatter"). then the child observes that the verb "break" appears to be similar to the verbs "smash" and "shatter" by noting that the three verbs can select "windshield" and "plate" as complements (see sentences (a, d, g) for "windshield" and sentences (b, e, h) for "plate"). on the basis of these observations, the child may decide that if the verb "break" really is similar (semantically) to "smash" and "shatter", then "break" should also be able to select "vase" as a complement, just as "smash" and "shatter" can. likewise, the child observes that the nouns "windshield" and "plate" behave similarly, as they can both be taken as complements by the three verbs "smash", "shatter" and "break", and that the noun "vase" appears similar to "windshield" and "plate" in so far as the three nouns can be taken as the complement by the two verbs "smash" and "shatter". this is a second line of observations that the child may use to support their conclusion that sentence (i) is a licit production. the strategy outlined above is a simplified illustration of how a collaborative filtering (cf) algorithm (reviewed in §2), which uses evidence of how related verbs and related nouns behave, can be used to infer whether a given verb can take a given noun as a complement. the goal of the present study is to evaluate whether cf algorithms, a widely used method in artificial intelligence for developing recommender systems (cacheda et al., 2011; jalili et al., 2018), can be used to accurately model argument selection based on co-occurrence data obtained from a large english corpus (see §3 for details). the results of the experiments presented in this study (see §4) suggest that model-based cf algorithms perform well on the task of recommending which nouns a given verb can or cannot select as a complement, achieving auroc of between 0.89 and 0.90 and surpassing a number of different baselines; notably, we found during model selection that the number of latent factors (and thus the size of the embedding vectors learned by these cf algorithms) was relatively small (at most 6 latent factors) as compared to the number of distinct verbs and nouns appearing in the analyzed co-occurrence data. furthermore, we found that when we used k-means clustering to quantize the (per-verb and per-noun) embedding vectors learned by these cf algorithms, using the cluster of a particular verb or noun as a proxy for the verb or noun itself (as opposed to a distinct embedding vector per verb or per noun) yielded minimal loss of performance (< 1%) even when we used a relatively small number of verb and noun clusters. (see §5 for details) finally, our results suggest that model-based cf algorithms should be considered for use in modeling the inferences a language learner makes when considering problems of argument selection (see §6 for discussion). ## a review of collaborative filtering given a (finite) set of users, a (finite) set of items, and information about the ratings assigned by users to items (encoded in a user-item rating matrix), the task of a recommender system is to predict whether a given user would select a given item, or what rating the user would assign to the given item -these predictions can then be used to generate a list of recommended items for the given user (bobadilla et al., 2013). this study takes the users to be predicates (i.e. lexical verbs) and the items to be the arguments (i.e. common nouns) that a predicate may select as its complement (i.e. object). content-based recommendation algorithms exploit similarities between the features associated with each item -e.g. a content-based recommendation algorithm would predict which arguments a given predicate can select by evaluating the semantic and syntactic features associated with the argument (balabanović and shoham, 1997; lops et al., 2011). in the case that we do not have access to features associated with the items, we may employ collaborative filtering (cf) recommendation algorithms, which consider both similarities between the users and/or similarities between the items. foot_0 cf algorithms are traditionally divided into two groups, memory-based cf algorithms and model-based cf algorithms, which we will now describe. memory-based cf algorithms assume that similar users select similar items and assign similar ratings, with two users considered to be similar if they tend to assign similar ratings to items. memory-based cf algorithms work by identifying a set of users who are similar to the target usere.g. via the k-nearest-neighbor (knn) algorithm, using the pearson correlation coefficient as a similarity measure -and then predicting the rating the target user would assign to a given item by considering the ratings assigned by similar users, respectively weighted by the degree-of-similarity of each user to the target user (schafer et al., 2007). @xcite although memory-based cf algorithms are widely used in practice, they face difficulty with respect to: (a) scaling as the sets of users and items grow, and (b) dealing with a sparse user-item interaction matrix (adomavicius and tuzhilin, 2005). model-based cf algorithms, in which a predictive model is learned, address the aforementioned difficulties of memory-based models. in particular, latent factor models such as singular value decomposition (svd) and non-negative matrix factorization (nmf) employ dimensionality-reduction in which user and item profiles (i.e. the rows and columns of the user-item rating matrix) are embedded in a lower-dimensional space in which latent relationships between users and items become more explicit (hofmann, 2004; koren et al., 2009; lü et al., 2012). in this way, latent factor models address two weaknesses of memory-based cf algorithms, scalability and sparsity, and for this reason the present study employs (latent factor) model-based cf algorithms. ## deriving a verb-noun rating matrix from corpus data this study employs an english corpus, the corpus of contemporary american english. the coca is a 385 million word corpus of (late 20th century and early 21st century) english derived from several domains including spoken language, fiction, magazines, newspapers, and academic articles (davies, 2009, 2010). the corpus was preprocessed as follows. first, we tokenized and segmented the corpus text into sentences. we then annotated the tokens in each sentence with part-of-speech (pos) tags. @xcite sentences without at least one verb and one common noun were then discarded. finally we lemmatized the tokens in each sentence using the textblob python library. after preprocessing the coca corpus, the text consisted of 75584272 words (not counting punctuation markers or numbers) segmented into 10087753 sentences, with 43429 distinct verb lemmas (derived from 60693 distinct lexical verbs) and 89541 distinct noun lemmas (derived from 105957 distinct common nouns). next, we derived a verb-noun co-occurrence matrix from the processed corpus as follows. the set of distinct (lexical) verb lemmas and the set of distinct (common) noun lemmas were indexed (using lexicographic ordering) as {v 1 , v 2 , v 3 , ..., v s } and {n 1 , n 2 , ..., n t } respectively. then the entry at row i and column j in the verb-noun co-occurrence matrix has value equal to the number of sentences in the (processed) corpus in which the (lemmatized) verb v i and the (lemmatized) noun n j co-occur, subject to the following constraints: the experiment detailed in this section addresses the question of whether model-based cf algorithms can be used to accurately predict which arguments (i.e. common nouns) a predicate (i.e. a lexical verb) may select. @xcite we evaluated two different latent factor models, svd and nmf. 9 ## analysis having seen that the two model-based cf algorithms performed well on the task of predicting which arguments a predicate is likely to select as its complement, we now turn to considering whether these cf models encode some knowledge of lexical-semantics. lexical verbs may be said to cluster together into classes, with lexical verbs in the same class sharing similar syntactic and semantic properties (see the verb-classification established in (levin, 1993)). the model-based cf algorithms that were evaluated in §4 produced distinct embedding vectors for each argument and for each predicate -this section analyzes whether these embedding vectors for verbs and nouns can be clustered into disjoint groups (of embedding vectors for verbs and nouns respectively). we will restrict our attention to the embedding vectors learned by the svd and nmf models with median performance (with respect to auroc). for each of the two trained cf models, we used the k-means algorithm (lloyd, 1982; forgey, 1965; jain, 2010) to group the embedding vectors for predicates and arguments into disjoint clusters of predicates and arguments respectively. the k-means algorithm was parameterized by the number of clusters the input (embedding) vectors should be grouped into. let k p denote the number of clusters the predicate embedding vectors are grouped into, and let k a denote the number of clusters the argument embedding vectors are grouped into. a grouping of the predicates and arguments using particular values of k p and k a respectively is referred to as a model-grouping. we ran k-means clustering to compute modelgroupings using k @xmath0, 15, 20, . . . , 55} and k @xmath1, 15, 20, . . . , 100}, with clustering run five times for each selection of k p and k a . we next evaluated how well a model-grouping could be used to predict whether a given predicate (lexical verb) selects a particular argument (common noun). given a particular model-grouping with k p predicate clusters and k a argument clusters, for a verb-cluster, α, and a noun-cluster, β, let the c α,β be the total number of co-occurrence counts for (verb, noun) pairs in (α, b) that have a high rating, and let d α,β be the total number of co-occurrence counts for (verb, noun) pairs in (α, b); next, define the average rating a α,β to be c α,β d α,β , and let us suppose that all (verb, noun) pairs in (α, β) are assigned the rating a α,β . we can then recompute the auroc for this model-grouping on the test data to evaluate the discriminatory power of the model-grouping; we refer to this metric as the clustered-model auroc. we identified model-groupings that achieved near-optimal clustered-model auroc while using as few predicate clusters and argument clusters as possible. we did this as follows. let the optimal clustered-model auroc be the maximal clustered-model auroc achieved by any modelgrouping, and let a model-grouping be called suboptimal if its clustered-model auroc is less than 99% of the optimal clustered-model auroc. then a model-grouping is called near-optimal if (i) its clustered-model auroc is within 1% of the optimal clustered-model auroc, and (ii) decreasing either k p or k a yields a sub-optimal modelgrouping. we computed the clustered-model auroc for each model-grouping and identified model-groupings that were near-optimal. we found that near optimal performance (i.e. < 1% loss of maximal clustered-model auroc) could be achieved using a relatively small number of clusters for verbs and nouns (relative to the dimensions of the verb-noun rating matrix). see given a particular model-grouping with k p verb clusters and k a noun clusters, for a verb-cluster, α, and a noun-cluster, β, the entropy for this pair of verb and noun clusters is: the entropy e (α,β) measures how much information is needed (on average) to determine whether a randomly selected (verb, noun) pair in (α, β) has a high or low rating; note that since there are only two possible ratings (high and low), 0 ≤ e (α,β) ≤ 1, and we expect a good (verb, noun) cluster-pair to have an entropy value closer to 0 than to 1, as that signifies that the members of the cluster pair are either majority high-rated or low-rated (verb, noun) pairs, which in turn suggests that these (verb, noun) pairs behave in a similar manner and are thus appropriate to cluster together. we then compute the weighted average entropy (also bounded between 0 and 1) of the model-grouping (k p , k a ) is computed as: w (ka,k b ) = α,β c β e (α,β) α,β d α,β see ## conclusion the results of this study suggest that model-based cf algorithms perform well on the task of inferring which (common) nouns a given (lexical) verb serving as a predicate can select as a complement. the two model-based cf algorithms that were evaluated on this task, svd and nmf, achieved auroc of 0.90 and 0.89 (respectively), indicating that they have good discriminatory power and surpassing the performance of several baselines. notably, these two models achieved this level of performance using at most six latent factors, yielding embedding vectors of relatively low dimensionality as compared to the dimensionality of the verb-noun rating matrix from which they were derived. we also found that the embedding vectors yielded by the svd and nmf models could each be clustered into a small number of disjoint groups with only a minuscule loss of performance (as measured by auroc). finally, we observed modest alignment of the verb clusters with the levin verb classes as compared to several baselines. we believe that the results presented in this study warrant evaluation of whether model-based cf algorithms are suitable for modeling constituent selection, thereby going beyond inferring the arguments a predicate may select as its complement; such a set of cf models for constituent selection could be used to constrain the productivity of the rules that make up a constituent grammar, thereby yielding a system for learning a grammar from noisy corpus data.