{'fraction_non_alphanumeric': 0.03200906451384463, 'fraction_numerical': 0.011826357906663833, 'mean_word_length': 4.800575066748819, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Reducing Dimensions of Tensors in Type-Driven Distributional Semantics

Compositional distributional semantics is a subfield of Computational Linguistics which investigates methods for representing the meanings of phrases and sentences. In this paper, we explore implementations of a framework based on Combinatory Categorial Grammar (CCG), in which words with certain grammatical types have meanings represented by multilinear maps (i.e. multi-dimensional arrays, or tensors). An obstacle to full implementation of the framework is the size of these tensors. We examine the performance of lower dimensional approximations of transitive verb tensors on a sentence plausibility/selectional preference task. We find that the matrices perform as well as, and sometimes even better than, full tensors, allowing a reduction in the number of parameters needed to model the framework.


Introduction
An emerging subfield of computational linguistics is concerned with learning compositional distributional representations of meaning (Mitchell and Lapata, 2008;Baroni and Zamparelli, 2010;Coecke et al., 2010;Grefenstette and Sadrzadeh, 2011;Clarke, 2012;Socher et al., 2012;Clark, 2013). The advantage of such representations lies in their potential to combine the benefits of distributional approachs to word meaning (Schütze, 1998;Turney and Pantel, 2010) with the more traditional compositional methods from formal semantics (Dowty et al., 1981). Distributional representations have the properties of robustness, learnability from data, ease of handling ambiguity, and the ability to represent gradations of meaning; whereas compositional models handle the unbounded nature of natural language, as well as providing established accounts of logical words, quantification, and inference.
One promising approach which attempts to combine elements of compositional and distributional semantics is by Coecke et al. (2010). The underlying idea is to take the type-driven approach from formal semantics -in particular the idea that the meanings of complex grammatical types should be represented as functions -and apply it to distributional representations. Since the mathematics of distributional semantics is provided by linear algebra, a natural set of functions to consider is the set of linear maps. Coecke et al. recognize that there is a natural correspondence from complex grammatical types to tensors (multi-linear maps), so that the meaning of an adjective, for example, is represented by a matrix (a 2nd-order tensor) 1 and the meaning of a transitive verb is represented by a 3rd-order tensor. Coecke et al. use the grammar of pregroups as the syntactic machinery to construct distributional meaning representations, since both pregroups and vector spaces can be seen as examples of the same abstract structure, which leads to a particularly clean mathematical description of the compositional process. However, the approach applies more generally, for example to other forms of categorial grammar, such as Combinatory Categorial Grammar (Steedman, 2000;Maillard et al., 2014), and also to phrase-structure grammars in a way that a formal linguist would recognize (Baroni et al., 2014). Clark (2013) provides a description of the tensor-based framework aimed more at computational linguists, relying only on the mathematics of multi-linear algebra rather than the category theory used in Coecke et al. (2010). Section 2 repeats some of this description.
A major open question associated with the tensor-based semantic framework is how to learn the tensors representing the meanings of words with complex types, such as verbs and adjectives. The framework is essentially a compositional framework, providing a recipe for how to combine distributional representations, but leaving open what the underlying vector spaces are and how they can be acquired. One significant challenge is an engineering one: in a wide-coverage grammar, which is able to handle naturally occurring text, there will be a) a large lexicon with many word-category pairs requiring tensor representations; and b) many higher-order tensors with large numbers of parameters which need to be learned. In this paper we take a first step towards learning such representations, by learning tensors for transitive verbs.
One feature of the tensor-based framework is that it allows the meanings of words and phrases with different basic types, for example nouns and sentences, to live in different vector spaces. This means that the sentence space is task specific, and must be defined in advance. For example, to calculate sentence similarity, we would have to learn a vector space where distances between vectors representing the meanings of sentences reflect similarity scores assigned by human annotators.
In this paper we describe an initial investigation into the learning of word meanings with complex syntactic types, together with a simple sentence space. The space we consider is the "plausibility space" described by Clark (2013), together with sentences of the form subject-verbobject. This space is defined to distinguish semantically plausible sentences (e.g. Animals eat plants) from implausible ones (e.g. Animals eat planets). Plausibility can be either represented as a single continuous variable between 0 and 1, or as a two-dimensional probability distribution over the classes plausible ( ) and implausible (⊥). Whether we consider a one-or two-dimensional sentence space depends on the architecture of the logistic regression classifier that is used to learn the verb (Section 3).
We begin with this simple plausibility sentence space to determine if, in fact, the tensor-based representation can be learned to a sufficiently useful degree. Other simple sentence spaces which can perhaps be represented using one or two variables include a "sentence space" for the sentiment analysis task (Socher et al., 2013), where one variable represents positive sentiment and the other nega-tive. We also expect that the insights gained from research on this task can be applied to more complex sentence spaces, for example a semantic similarity space which will require more than two variables.

Syntactic Types to Tensors
The syntactic type of a transitive verb in English is (S \NP )/NP (using notation from Steedman (2000)), meaning that a transitive verb is a function which takes an NP argument to the right, an NP argument to the left, and results in a sentence S . Such categories with slashes are complex categories; S and NP are basic or atomic categories. Interpreting such categories under the Coecke et al. framework is straightforward. First, for each atomic category there is a corresponding vector space; in this case the sentence space S and the noun space N. 2 Hence the meaning of a noun or noun phrase, for example people, will be a vector in the noun space: −−−→ people ∈ N. In order to obtain the meaning of a transitive verb, each slash is replaced with a tensor product operator, so that the meaning of eat, for example, is a 3rd-order tensor: eat ∈ S ⊗ N ⊗ N. Just as in the syntactic case, the meaning of a transitive verb is a function (a multi-linear map) which takes two noun vectors as arguments and returns a sentence vector.
Meanings combine using tensor contraction, which can be thought of as a multi-linear generalisation of matrix multiplication (Grefenstette, 2013). Consider first the adjective-noun case, for example black cat. The syntactic type of black is N /N ; hence its meaning is a 2nd-order tensor (matrix): black ∈ N ⊗ N. In the syntax, N /N combines with N using the rule of forward application (N /N N ⇒ N ), which is an instance of function application. Function application is also used in the tensor-based semantics, which, for a matrix and vector argument, corresponds to matrix multiplication. Figure 1 shows how the syntactic types combine with a transitive verb, and the corresponding tensor-based semantic types. Note that, after the verb has combined with its object NP , the type of the verb phrase is S \NP , with a corresponding meaning tensor (matrix) in S ⊗ N. This matrix then combines with the subject vector, through people eat fish Figure 1: Syntactic reduction and tensor-based semantic types for a transitive verb sentence matrix multiplication, to give a sentence vector. In practice, using for example the widecoverage grammar from CCGbank (Hockenmaier and Steedman, 2007), there will be many types with more than 3 slashes, with corresponding higher-order tensors.
For example, a common category for a preposition is the following: ((S \NP )\(S \NP ))/NP , which would be assigned to WITH in eat WITH a fork. (The way to read the syntactic type is as follows: with requires an NP argument to the right -a fork in this example -and then a verb phrase to the left -eat with type S \NP -resulting in a verb phrase S \NP .) The corresponding meaning tensor lives in the tensor space S ⊗ N ⊗ S ⊗ N ⊗ N, i.e. a 5th-order tensor. Categories with even more slashes are not uncommon, for example ((N /N )/(N /N ))/((N /N )/(N /N )). Clearly learning parameters for such tensors is highly challenging, and it is likely that lower dimensional approximations will be required.

Methods
In this paper we compare five different methods for modelling the type-driven semantic representation of subject-verb-object sentences. The tensor is a function that encodes the meaning of a verb. It takes two vectors from the K-dimensional noun space as input, and produces a representation of the sentence in the S-dimensional sentence space. In this paper, we consider a plausibility space where S is either a single variable or a twodimensional space over two classes: plausible ( ) and implausible (⊥).
The first method (Tensor) follows Krishnamurthy and Mitchell (2013) by learning a tensor as parameters in a softmax classifier. We introduce three related methods (2Mat, SKMat, KKMat), all of which model the verb as a matrix or a pair of matrices ( Figure 2). Table 1 gives the number of parameters for each method. Tensor, 2Mat, and SKMat all have a two-dimensional S space, while KKMat produces a scalar value. In all of these learning-based methods the derivatives were obtained via the chain rule with respect to each set of parameters and gradient descent was performed using the Adagrad algorithm (Duchi et al., 2011). We also reimplement a distributional method (DMat), which was previously used in SVO experiments with the type-driven framework (Grefenstette and Sadrzadeh, 2011). While the other methods are trained as plausibility classifiers, in DMat we estimate the class boundary from cosine similarity via training data (see explanation below).
Tensor If subject (n s ) and object (n o ) nouns are K-dimensional vectors and the plausibility vector is S-dimensional with S = 2, we can learn the values of the K × K × S tensor representing the verb as parameters (V) of a regression algorithm. To represent this space as a distribution over two classes ( ,⊥) we apply a sigmoid function (σ) to restrict the output to the [0,1] range and the softmax activation function (g) to balance the class probabilities. The full parameter set which needs to be optimised for is B = {V, Θ}, where Θ = {θ , θ ⊥ } are the softmax parameters for the two classes. For each verb we optimise the KL-divergence L between the training labels t i and classifier predictions using the following regularised objective: where n i s and n i o are the subject and object of the training instance i ∈ N , and h V n i s , where the verb tensor parameters are drawn as a cube with the subject and object noun vectors as operands on either side. The output is a two-dimensional vector which is then transformed using the sigmoid and softmax functions. The gold-standard distribution over training labels is defined as (1, 0) or (0, 1), depending on whether the training instance is a positive (plausible) or negative (implausible) example. Tensor contraction is implemented using the Matlab Tensor Toolbox (Bader et al., 2012).
2Mat An alternative approach is to decouple the interaction between the object and subject by learning a pair of S × K (S = 2) matrices (V s , V o ) for each of the input noun vectors (one matrix for the subject slot of the verb and one for the object slot). The resulting S-vectors are concatenated, after the subject and object nouns have been combined with their matrices, and combined with the softmax component to produce the output distribution. Therefore the objective function is the same as in Equation 1, but h V is defined as: where || represents vector concatenation. The intention is to test whether we can learn the verb without directly multiplying subject and object features, n i s and n j o . The function h V is shown in Figure 2-(b), where the verb tensor parameters are drawn as two 2 × K matrices, one of which interacts with the subject and the other with the object noun vector. The output is a four-dimensional vector whose values are then restricted to [0,1] using the sigmoid function and then transformed into a two-dimensional distribution over the classes using the softmax function.
SKMat A third option for generating a sentence vector with S = 2 dimensions is to consider the verb as an S × K matrix. If we transform the object vector into a K × K matrix with the noun on the diagonal and zeroes elsewhere, we can combine the verb and object to produce a new S × K matrix, which is encoding the meaning of the verb phrase. We can then complete the sentence reduction by multiplying the subject vector with this verb phrase vector to produce an S-dimensional sentence vector. Formally, we define SKMat as: T and use it in Equation 1. The function h V is described in Figure 2-(c), where the verb tensor parameters are drawn as a matrix, the subject as a vector, and the object as a diagonal ma-trix. The graphic demonstrates the two-step combination and the intermediate S × K verb phrase matrix, as well as the the noun vector product that results in a two-dimensional vector which is then transformed using the sigmoid and softmax functions. Whilst the tensor method captures the interactions between all pairs of context features (n si · n oj ), SKMat only captures the interactions between matching features (n si · n oi ).
KKMat Given a two-class problem, such as plausibility classification, the softmax implementation is overparameterised because the class membership can be estimated with a single variable. To produce a scalar output, we can learn the parameters for a single K × K matrix (V) using standard logistic regression with the mean squared error cost function: This function is shown in Figure 2-(d), where the verb parameters are shown as a matrix, while the subject and object are vectors. The output is a single scalar, which is then transformed with the sigmoid function. Values over 0.5 are considered plausible.
DMat The final method produces a scalar as in KKMat, but is distributional and based on corpus counts rather than regression-based. Grefenstette and Sadrzadeh (2011) introduced a corpus-based approach for generating a K × K matrix for each verb from an average of Kronecker products of the subject and object vectors from the positively labelled subset of the training data. The intuition is that, for example, the matrix for eat may have a high value for the contextual topic pair describing animate subjects and edible objects. To determine the plausibility of a new subject-object pair for a particular verb, we calculate the Kronecker product of the subject and object noun vectors for this pair, and compare the resulting matrix with the average verb matrix using cosine similarity.
For label prediction, we calculate the similarity between each of the training data pairs and the learned average matrix. Unlike for KKmat, the class cutoff is estimated at the break-even point of the receiver operator characteristic (ROC) generated by comparing the training labels with this cosine similarity value. The break-even point is when the true positive rate is equal to the false positive rate. In practice it would be more accurate to estimate the cutoff on a validation dataset, but some of the verbs have so few training instances that this was not possible.

Experiments
In order to examine the quality of learning we run several experiments where we compare the different methods. In these experiments we consider the DMat method as the baseline. Some of the experiments employ cross-validation, in particular five repetitions of 2-fold cross validation (5x2cv), which has been shown to be statistically more robust than the traditional 10-fold cross validation (Alpaydin, 1999;Ulaş et al., 2012). The results of 5x2cv experiments can be compared using the regular paired t-test, but the specially designed 5x2cv F-test has been proven to produce fewer statistical errors (Ulaş et al., 2012).
The performance was evaluated using the area under the ROC (AUC) and the F 1 measure (based on precision and recall over the plausible class). The AUC evaluates whether a method is ranking positive examples above negative ones, regardless of the class cutoff value. F 1 shows how accurately a method assigns the correct class label. Another way to interpret the results is to consider the AUC as the measure of the quality of the parameters in the verb matrix or tensor, while the F-score indicates how well the softmax, the sigmoid, and the DMat cutoff algorithm are estimating class participation.
Ex-1. In the first experiment, we compare the different transitive verb representations by running 5x2cv experiments on ten verbs chosen to cover a range of concreteness and frequency values (Section 4.2).
Ex-2. In the initial experiments we found that some models had low performance, so we applied the column normalisation technique, which is often used with regression learning to standardise the numerical range of features: This preserves the relative values of features between training samples, while moving the values to the [0,1] range.
Ex-3. There are varying numbers of training examples for each of the verbs, so we repeated the 5x2cv with datasets of 52 training points for each verb, since this is the size of the smallest dataset of the verb CENSOR. The points were randomly sampled from the datasets used in the first experiment. Finally, the four verbs with the largest datasets were used to examine how the performance of the methods changes as the amount of training data increases. The 4,000 training samples were randomised and half were used for testing. We sampled between 10 and 1000 training triples from the other half (Figure 4).

Noun vectors
Distributional semantic models (Turney and Pantel, 2010) encode word meaning in a vector format by counting co-occurrences with other words within a specified context window. We constructed the vectors from the October 2013 dump of Wikipedia articles, which was tokenised using the Stanford NLP tools 3 , lemmatised with the Morpha lemmatiser (Minnen et al., 2001), and parsed with the C&C parser (Clark and Curran, 2007). In this paper we use sentence boundaries to define context windows and the top 10,000 most frequent lemmatised words in the whole corpus (excluding stopwords) as context words. The raw co-occurrence counts are re-weighted using the standard tTest weighting scheme (Curran, 2004), where f w i c j is the number of times target noun w i occurs with context word c j : Using all 10,000 context words would result in a large number of parameters for each verb tensor, and so we apply singular value decomposition (SVD) (Turney and Pantel, 2010) with 40 latent dimensions to the target-context word matrix. We use context selection (with N = 140) and row normalisation as described in Polajnar and Clark (2014) to markedly improve the performance of SVD on smaller dimensions (K) and enable us to train the verb tensors using very low-dimensional 3 http://nlp.stanford.edu/software/index.shtml  noun vectors. Performance of the noun vectors was measured on standard word similarity datasets and the results were comparable to those reported by Polajnar and Clark (2014).

Training data
In order to generate training data we made use of two large corpora: the Google Syntactic Ngrams (GSN) (Goldberg and Orwant, 2013) and the Wikipedia October 2013 dump. We first chose ten transitive verbs with different concreteness scores (Brysbaert et al., 2013) and frequencies, in order to obtain a variety of verb types. Then the positive (plausible) SVO examples were extracted from the GSN corpus. More precisely, we collected all distinct syntactic trigrams of the form nsubj ROOT dobj, where the root of the phrase was one of our target verbs. We lemmatised the words using the NLTK 4 lemmatiser and filtered these examples to retain only the ones that contain nouns that also occur in Wikipedia, obtaining the counts reported in Table 2. For every positive training example, we constructed a negative (implausible) one by replacing both the subject and the object with a confounder, using a standard technique from the selectional preference literature (Chambers and Jurafsky, 2010). A confounder was generated by choosing a random noun from the same frequency bucket as the original noun. 5 Frequency buckets of size 10 were constructed by collecting noun frequency counts from the Wikipedia corpus. For ex-  ample, for the plausible triple animal EAT plant, we generate the implausible triple mountain EAT product. Some verbs were well represented in the corpus, so we used up to the top 2,000 most frequent triples for training.
Tensor Tensor* SKMat SKMat* Figure 3: The effect of column normalisation (*) on Tensor and SKMat. Top table shows AUC and the bottom F 1 -score, while the error bars indicate standard deviation.

Results
The results from Ex-1 are summarised in Table 3. We can see that linear regression can lead to models that are able to distinguish between plausible and implausible SVO triples. The Tensor method outperforms DMat, which was previously shown to produce reasonable verb representations in related experiments (Grefenstette and Sadrzadeh, 2011). 2Mat and KKMat, in turn, outperform Tensor demonstrating that it is possible to learn lower dimensional approximations of the tensor-based framework. 2Mat is an appropriate approximation for functions with two inputs and a sentence space of any dimensionality, while KKMat is only appropriate for a single valued sentence space, such as the plausibility or sentiment space. Due to method variance and dataset size there are very few AUC results that are significantly better than DMat and even fewer that outperform Tensor. All methods perform poorly on the verb IDEALIZE, probably because it has the lowest concreteness value and is in one of the smallest datasets. This verb is also particularly difficult because it does not select strongly for either its subject or object, and so some of the pseudonegative examples are in fact somewhat plausible (e.g. town IDEALIZE authority or child IDEALIZE racehorse). In general, this would indicate that more concrete verbs are easier to learn, as they have a clearer pattern of preferred property types, but there is no distinct correlation.
The results of the normalisation experiments (Ex-2) are shown in Table 4. We can see that the SKMat method, which performed poorly in Ex-1 notably improves with normalisation. Tensor AUC scores also improve through normalisation, but the F-scores decrease. The rest of the methods, and in particular DMat are negatively affected by column normalisation. The results from Ex-1 and Ex-2 for SKMat and Tensor are summarised in   . This figure also shows that AUC values have much lower variance, but that high variance in F-score leads to results that are not statistically significant.
When considering the size of the datasets (Ex-3), it would seem from Table 5 that 2Mat is able to learn from less data than DMat or Tensor. While this may be true over a 5x2cv experiment on small data, Figure 4 shows that this view may be overly simplistic and that different training examples can influence learning. Analysis of errors shows that the baseline method mostly generates false negative errors (i.e. predicting implausible when the gold standard label is plausible). In contrast, Tensor produces almost equal numbers of false positives and false negatives, but sometimes produces false negatives with low frequency nouns (e.g. bourgeoisie IDEALIZE work), presumably because there is not enough information in the noun vector to decide on the correct class. It also produces some false positive errors when either of the nouns is plausible (but the triple is implausible), which would suggest results may be improved by training with data where only one noun is confounded or by treating negative data as possibly positive (Lee and Liu, 2003).

Discussion
Current methods which derive distributed representations for phrases, for example the work of Socher et al. (2012), typically use only matrix representations, and also assume that words, phrases and sentences all live in the same vector space. The tensor-based semantic framework is more flexible, in that it allows different spaces for different grammatical types, which results from it be-  ing tied more closely to a type-driven syntactic description; however, this flexibility comes at a cost, since there are many more paramaters to learn. Various communities are beginning to recognize the additional power that tensor representations can provide, through the capturing of interactions that are difficult to represent with vectors and matrices (see e.g. (Ranzato et al., 2010;Sutskever et al., 2009;Van de Cruys et al., 2012)). Hierarchical recursive structures in language potentially represent a large number of such interactions -the obvious example for this paper being the interaction between a transitive verb's subject and object -and present a significant challenge for machine learning.
This paper is a practical extension of the work in Krishnamurthy and Mitchell (2013), which introduced learning of CCG-based function tensors with logistic regression on a compositional semantics task, but was implemented as a proof-ofconcept with vectors of length 2 and on small, manually created datasets based on propositional logic examples. Here, we go beyond this by learning tensors using corpus data and by deriving several different matrix representations for the verb in the subject-verb-object (SVO) sentence.
This work can also be thought of as applying neural network learning techniques to the classic problem of selectional preference acquisition, since the design of the pseudo-disambiguation experiments is taken from the literature on selectional preferences (Clark and Weir, 2002;Chambers and Jurafsky, 2010). We do not compare directly with methods from this literature, e.g. those based on WordNet (Resnik, 1996;Clark and Weir, 2002) or topic modelling techniques (Seaghdha, 2010), since our goal in this paper is not to extend the state-of-the-art in that area, but rather to use selectional preference acquisition as a test bed for the tensor-based semantic framework.

Conclusion
In this paper we introduced three dimensionally reduced representations of the transitive verb tensor defined in the type-driven framework for compositional distributional semantics (Coecke et al., 2010). In a comprehensive experiment on ten different verbs we find no significant difference between the full tensor representation and the reduced representations. The SKMat and 2Mat rep-resentations have the lowest number of parameters and offer a promising avenue of research for more complex sentence structures and sentence spaces. KKMat and DMat also had high scores on some verbs, but these representations are applicable only in spaces where a single-value output is appropriate.
In experiments where we varied the amount of training data, we found that in general more concrete verbs can learn from less data. Low concreteness verbs require particular care with dataset design, since some of the seemingly random examples can be plausible. This problem may be circumvented by using semi-supervised learning techniques.