{'fraction_non_alphanumeric': 0.031174438687392055, 'fraction_numerical': 0.00954231433506045, 'mean_word_length': 4.628432563791009, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
GausSetExpander: A Simple Approach for Entity Set Expansion

Entity Set Expansion is an important NLP task that aims at expanding a small set of entities into a larger one with items from a large pool of candidates. In this paper, we propose GausSetExpander, an unsupervised approach based on optimal transport techniques. We propose to re-frame the problem as choosing the entity that best completes the seed set. For this, we interpret a set as an elliptical distribution with a centroid which represents the mean and a spread that is represented by the scale parameter. The best entity is the one that increases the spread of the set the least. We demonstrate the validity of our approach by comparing to state-of-the art approaches.


Introduction
The Entity Set Expansion (ESE) task aims at expanding a small seed set e.g {Paris, Berlin} to a larger set of entities that belong to the same semantic class, in this example Capitals. Loosely speaking, the goal is to find all other entities in a given corpus that complete the original set of seed entities. From a theoretical point of view, the ESE task can be seen as a problem of generalization from few examples. The steps that are necessary to successfully solve this problem are: (1) identifying the semantic class from the given seed set; (2) identifying similar examples from a large pool of items that fit the semantic class. This task is useful to several downstream applications such as question answering (Wang et al., 2008), taxonomy construction (Shen et al., 2018), relation extraction (Lang and Henderson, 2013) and query suggestion (Cao et al., 2008).
In this paper, we propose an approach to tackle the ESE task based on pretrained embedding models and optimal transport techniques. It has been vastly shown that pretrained embedding models contain semantic, syntactic and knowledge background that could facilitate transfer learning tasks.
One of the major challenges of ESE is the limited (or lack thereof) of supervision. In fact, generally the set seed is too small for fine-tuning and sometimes, the ground truth semantic class is an open set. From the literature, we can identify two main ways of solving the ESE task: a pattern-based approach and a distributional approach. The first has as an objective mining revealing textual patterns in the corpus that signal the semantic class and extracting the correct entity from this patterns. On the other hand, the distributional approach relies on the assumption that similar words appear in similar contexts. These methods operate by representing each term in the vocabulary as an embedding vector that summarizes all the contexts the term appears within a large corpus, and then look for terms with vectors that are similar to those of the seed entity. One of the main critiques to these approaches is that they consider all occurrences of a term in the corpus when calculating its representation, including many contexts that are irrelevant or non-informative to the concept which cause noise in the corpus.
We propose an algorithm that is more similar to the distributional approach, although our algorithm has some notable differences. GausSetExpander, proceeds in an iterative manner across all terms in a vocabulary V, extracted from a corpus D. Given an initial set seed S 0 , and two terms embedded with a pretrained embedding model, we aim at finding the term that completes better the original set seed S 0 . For doing this, we simply produce two different expanded sets from the simple concatenation of the previously two random terms to the seed set and we evaluate the better expansion. The evaluation of the new obtained sets relies on techniques related to optimal transport, elliptical embeddings and sets clustering, which are concepts this thesis is treating. In a nutshell, we leverage the fact that one of the most common statistics of a set S is its centroid c(S) ∈ R d , represented as: This implies that, it is possible to approximate a set of vectors to its centroid. Another key element of our approach comes from the literature of Gaussian embeddings, which has demonstrated to provide a better and richer representation for items in the latent space. In fact, a Gaussian embedding is characterized by two parameters, the mean vector which represents the location in the latent space and the covariance matrix, which encodes the dispersion around the location vector, that is to say the uncertainty of the representation. We hypothesise that given an original seed set and two candidate items to expand it, the better entity is the one that causes the less increase in the dispersion of the set. This hypothesis is the key element of GausSetExpander. Additionally, ESE is a challenging task for the lack of available labels. For this reason, the pretrained embedding is a key element, because at each iteration we produce a weak label based on the cosine similarity between the centroid of the seed set and each candidate term. Finally, we rank the scores in order to identify candidates term from the vocabulary to generated the expanded set. To summarize, in this study we propose an iterative approach based on Gaussian representation for the ESE task to expand a seed set. We conduct experiments to verify our hypotheses and show the effectiveness of GausSetExpander.

Problem Formulation
Terminology In this section, we formally introduce the concepts necessary for this study as well the Entity Set Expansion problem. An entity is a string, that can be either a word or a phrase, that corresponds to a real-world entity in designated category. This category, is better defined as a semantic class which is a set of entities that share a common characteristic, for example fruits or animals. An entity set, is a set of terms that refers to the same real-world entity. More specifically, UK and United Kingdom refers to the same entity, hence are an entity synset. It is worth mentioning that an entity synset can be a singleton. Finally, a vocabulary is a list of terms that is derived from a given corpus.

Problem Formulation
Given a text corpus D, a vocabulary V extracted from D, a seed set of size n (usually small) of terms S 0 = [e 1 , e 2 , ...e n ] from the same semantic class C, the ESE task aims at expanding S 0 with terms from the vocabulary V from the same semantic class C. In practice, the goal is to rank all available entities and said ranking must have the terms that best expand S 0 at the top of the ranking.

Approach
In this section, we first lay down the notation as well as the mathematical background used for our hypothesis. Then we describe our hypothesis and the algorithm we proposed: GausSetExpander.

Notation
S d + is the set of all positive definite matrices. In the scope of this work, we only focus on Gaussian distributions which belong to the family of parameterized probability distributions z h,a,A having a location vector a ∈ R d which represents the shift of the distribution, a scale parameter A ∈ S d + , that represents the statistical dispersion of the distribution, and a characteristic generator function h. This is the same hypothesis that have been used throughout the thesis. Specifically, for Gaussian distributions, the scale parameter coincides with the covariance matrix var(z h,a,A ) = A. From now on, we denote Gaussian distributions (or embeddings) as z (h,a,A) = N (a, A).
Finally, when stated Tr, we indicate the trace operator, that is the sum of the diagonal elements of a matrix.

Mathematical Background
We need to explicitly describe few mathematical concepts useful the understanding of our hypothesis. First, as briefly mention in Section 1, one key element in our approach is the notion of centroid of a set from eq. (1). In fact an (aggregation) function that takes as input a set must respect the property of permutation to the order of objects in the set. Good candidate functions are the sum or the average, hence the centroid is a good representation a given set. Then, we need to go from the pointvector representation of an item to a distributional representation. We choose to focus on Gaussian distributions, particularly diagonal Gaussian distributions. For doing this we propose to use a set encoder, that takes as input a vector, mainly the centroid of the set and outputs a location vector µ and the diagonal of a covariance matrix d Σ . These concepts have been fully described in ??.
Finally, we need to describe the scoring function that takes as input two Gaussian representation of sets and assess which one is the better representation. As stated earlier, the best set is the one that have the smallest dispersion. We propose to use the Tr, trace operator for scoring the sets. This is derived from the optimal transport theory, in particular the Wasserstein distance which have been fully explained in ??.
We recall the Wasserstein distance derived from the appropriate simplifications, and relying on the squared Bures metric and squared Hellinger metric:

GausSetExpander
In the following section, we present the proposed approach for the Entity Set Expansion task. We propose an iterative approach that takes as input a small seed set and two candidates term and outputs two scores that indicates the better alternative. In a nutshell, our main hypothesis is that given two candidate entity for expanding the seed set, the better hypothesis will "fit" better the input set. We choose to represent this fit by considering the dispersion that the addition of a new term will cause to an existent set. A well suited mathematical notion for representing the dispersion around a center is the covariance matrix of a Gaussian distribution. That is the first key element of GausSetExpander. Algorithm 1 describes our approach. Set Encoder Given a seed set, the first step is to encode it as a tuple of location vector and covariance matrix in order to have the the dispersion before adding the candidate terms for the expansion.
For this, we represent the element-wise embedding function φ(.) as a deep neural network, as illustrated in Figure fig. 1. This network takes as input a set, very similarly to the model proposed in ??. We again choose to only focus on diagonal covariance matrices for the sake of simplicity. A first deep encoder, namely a 2-layer MLP with Relu, φ θ (·) maps these random inputs into d-dimensional outputs. These are then aggregated to µ θ (·) and fed to produce the variance Σ θ (·), a function which is again represented with a deep forward network.
Algorithm 1: GausSetExpander Compute cosine similarity: Encode S t and S t : Compute the score: Scoring function After describing the step to obtain the Gaussian representation of the sets, we illustrate the scoring process. In practice, most of the proposed methods for solving the ESE problem return a (top-k) ranking of the vocabulary rather than a fixed set. Then the evaluation is done on the returned ranking. Ideally, all terms that belongs to the semantic class identified by the seed set should be ranked higher.
From the Wasserstein distance in eq. (2), we derive the scoring function for two given expanded sets encoded as Gaussian distributions is: This scoring function can be interpreted as pointwise mutual information between the the candidate item and the set to be expanded. We stated earlier that GausSetExpander proceeds in stages. It first encodes the seed set S 0 as a tuple of vectors µ 0 and σ 0 . Then, it appends each candidate to the seed set S 0 to obtain two new sets S and S , which are transformed in Gaussian distributions as well. It is worth mentioning, that the weights of the set encoder shared are shared among candidates. Finally, the scoring function proceeds as follows: Loss function For learning the score, we utilize the large-margin classification loss: l(i, j|S 0 ) = max(0, s(i|S 0 ) − s(j|S 0 ) + ∆(i, j)) (6) Loosely speaking, this loss function is to ensure that s(i|S 0 )) > s(j|S 0 ) + ∆(i, j) whenever i should be preferred for expanding S 0 over j.
Weak supervision Per definition, the ESE tasks is challenging for the lack of proper supervision under the form of ground truth labels. Several works in the area rely on pre-trained language models or pre-trained embedding models to deliver the semantic, syntactic and background knowledge to provide weak labels. We proceed in the same manner, and use Glove (Pennington et al., 2014) for encoding the terms extracted from the corpus. Moreover, we assume that the seed terms are part of vocabulary. In order to generate, weak labels for training the scoring function we leverage the distributional hypothesis of the language models. In fact, that hypothesis states that similar words appear in similar contexts. For this reason, given two candidates terms i and j, we extract their context as well, c i , and c j respectively. Then we use the simple cosine similarity to induce a weak label l: The function R is defined as follows: Algorithm 2: CentroidSetExpander Input :corpus D, vocabulary V , set S 0 1 for t ← 0 to |D| do 2 Get i, j, c i , c j from D Encode S t and S t as their centroids: Compute the score: score(i|S 0 ) = l 2 (c(S 0 ) − c(S t )) score(j|S 0 ) = l 2 (c(S 0 ) − c(S t )) l(i, j|S 0 ) = max(0, s(i|S 0 ) − s(j|S 0 )) 14 end for

Experiments
In this section we describe our experimental setting as well as the main results obtained.
Dataset We used English Wikipedia as the corpus. Following, (Kushilevitz et al., 2020), we use for evaluation 7 datasets of closed sets. These sets are the are National football league teams (NFL, size:32), Major league baseball teams (MLB, size:30), US states (US, size:50), Countries (Cntrs,size:195), European countries (Euro, size:44) Capital cities (Caps,size:195) and Presidents of the USA (Pres, size:44) and one open class set: Music Genres (Genre).
(a) The expanded set S has a small increase in the dispersion after adding the entity i to the seed set s0.
(b) The expanded set S has a greater increase in the dispersion after adding the entity j to the seed set s0. Figure 2: Illustration of the hypothesis under GausSetExpander. Given two candidate entity for the seed set S 0 , the better candidate is the one that will induce the least increase in the dispersion of the generated set.

Setup and Evaluation
We rely on 300dimensional Glove for obtaining the pre-trained embedding. Moreover, we fix the maximum number of terms to 200,000 most frequent terms. Our approach has also a learning module, for which we need to define the following hyperparameters l r = 1e − 3 as the learning rate, batch size 512, h = 64 as the hidden size. Following other works in the literature, we chose the Mean Average Precision (MAP) at different positions k for evaluating our approach: where AP (S exp , S gt ) is the average precision at position k given the ranked expanded set S exp and the ground-truth set S gt . The training and the evaluation is done with random set seeds of cardinality 3 and the results presented are averaged over random seeds. We follow the recommendation of the authors of the datasets used for evaluation and fixed the size of the expanded set to 200 for smaller sets and to 350 for bigger sets that have size > 100. The open set of music genre is evaluate with MAP 70 .
Baseline methods We compare our approach to the following corpus based ESE approaches: Set-Expander (Mamou et al., 2018), a method based on entity ranking based on multi-context entity similarity defined on multiple embeddings, Category Builder (Mamou et al., 2018). Both this approaches are distributional, which is the category to which our method belongs to. For the sake of gaining a better insight of our hypothesis, we add a natural comparison approach which consists in our same architecture but the encoding of the sets remain the centroid representation. This comparison will act as an ablation experiment which we perform to assess the benefit or lack thereof of the Gaussian representation of the sets. We call this last baseline, Centroid-SetExpander and we described it in algorithm 2.

Results
We assess the set expansion performance by comparing our approach to the baselines methods. Table 1 presents the quantitative evaluation of our model. We can notice that GausSetExpander achieves comparable performance with current state-of-the-art methods. This demonstrates the validity of our hypothesis. When doing a fine grained analysis, we notice that GausSetExpander performs particularly poorly in the semantic class corresponding to the "Presidents". When investigating the results retrieved, we hypothesize that our algorithm probably fails in recognising the acronyms. In fact, a typical synset for the class "Presidents" will be "John_Fitzgerald_Kennedy, John_F._Kennedy, John_F_Kennedy, John_Kennedy, Kennedy, JFK". We hypothesize that probably a better encoding of the entities and tokens could resolve this problem.
An emblematic example could be that, among the top retrieved entity for the class "Presidents" we can find "Hillary" or "Barack" or even Presidents of other nations which were not present among the ground-truths. This let us think that the results might not be as bad as the numerical evaluation lead to think. Table 2 showcases few examples of top ranked entities but rejected.
One reason for this phenomenon could be the fact that the weak label is generated from a very noisy procedure. In fact, it is the result of the cosine similarity between the centroid of the set seed and the contexts of the 2 candidates entities. We hypothesize that a better method for generating a weak label than the naive cosine similarity could be beneficial. This leads to a a second point that it is worth mentioning which is that, our algorithm is very sensible to the amount of data. In fact, after a threshold which we empirically estimated around 50,000 articles, with a vocabulary of around 500,000 terms, we notice that the labels become extremely noisy and the overall performance degrades rapidly.
Finally, we compare GausSetExpander to Cen-troidSetExpander. We notice that the performance of the latter is worse in all datasets, and it declines even further for the semantic class "Presidents". This confirms that our initial hypothesis of considering the Wasserstein Distance between the sets is effective for the task of Entity Set Expansion.

Related Work
Entity Set Expansion Entity Set Expansion is a task that can be seen as a intermediate step form many problems and applications such as question answering or literature search. It was common for entity set expansion systems such as Google Sets (Tong and Dean, 2008) and SEAL (Wang et al., 2008) to submit a query made of seed entities to a general-domain search engine and then extract new entities from retrieved web pages. Web-based methods for set expansion  extract entities from documents retrieved by a search engine. The documents are chosen with respect to the query obtained from seed entities. However, this type of approaches demand an external search engine adapted to seed-oriented data, which could be costly. In fact, such methods impose significant run-time overhead and they make the assumption that top-ranked web pages contain other entities of the set, which might not necessarily exact.
As a solution, more recent works propose to expand the seed set processing a corpus offline without the need to prompt an online search engine. These corpus-based set expansion methods can be categorized into two general approaches: (1) entity ranking which calculates entity similarities and ranks all entities (Mamou et al., 2018;Pantel et al., 2009;Kushilevitz et al., 2020), and (2) iterative bootstrapping whose goal is to bootstrap the seed entity set by iteratively selecting context features and ranking new entities (Shen et al., 2017;Huang et al., 2020;Rong et al., 2016) with respect to the original seed set. The approach proposed in this paper belongs to the first category.
Pre-training Early works in computer vision on ImageNet (Russakovsky et al., 2015) have shown the advantages of pretrained models (Huang et al., 2017;He et al., 2017). In Natural Language Processing, pretrained embeddings such as Glove (Pennington et al., 2014) or Word2Vec (Mikolov et al., 2013) have also proven to be highly effective in several tasks. In addition to the embeddings, the pretrained language models are currently vastly used such as BERT (Devlin et al., 2019).
Set encoding Machine learning on sets can be divided into different subgroups depending on the nature of the input and output (e.g vector-to-set, set-to-set, set-to-sequence). Our work falls under the category of vector-to-set such as (Zhang et al., , 2019a. Notable works in vector-to-set literature are suited to tasks such as object detection, taking as input a feature representation of an images and producing set of coordinates for the bounding boxes. Loosely related are also methods like (Zhang et al., 2019b) that learn a permutation matrix for sets of items. Once the permutation matrix is learned, it is applied to the input set in order to turn the set into an (ordered) sequence. Once again, our method differs because the output set is not ordered, hence not a sequence.
Probabilistic Embeddings The work of Vilnis and McCallum (2015) established a new trend in the representation learning field by proposing to embed data points, in this case words, as probability distributions in R d . Representing objects in  the latent space as probability distributions allows more flexibility in the representation and even express multi-modality. In fact, point embeddings can be considered as a special case of probabilistic embeddings, namely a Dirac distribution, where the uncertainty is collapsed in a single point. In the above-mentioned work Vilnis and McCallum (2015), the metric used is KL divergence. However, this metric has a drawback: when variances of the probabilistic embedding collapse, the measure does not coincide with the Euclidean metric between point embeddings. Loosely speaking, the KL divergence and the 2 distance between two probability measures diverge to infinity when the variances become too small. In addition, the KL divergence does not behave well when the two compared distributions have little or no overlap. It has been shown by Muzellec and Cuturi (2018) that the Wasserstein metric is a better metric to compare probabilistic embeddings.

Conclusion
We introduce an iterative and distributional approach for the task of Entity Set Expansion. Our method is based on encoding sets of vectors as Gaussian distributions. These probabilistic representations are learned from the centroid of the sets and are useful because they allow to represents the sets as a tuple of location and dispersion. In fact, our main hypothesis states that given to ncandidates entities for a set, the best candidate will be the entity that will cause the least increase in the dispersion, represented as the covariance matrix. Finally, we use a scoring function based on the Wasserstein distance. The quantitative evaluation on benchmark datasets demonstrate the effectiveness of our approach.