A linear time approximation of Wasserstein distance with word embedding selection
Authors: Sho Otao
Makoto Yamada
Venue: EMNLP 2023 Main (2023)
Keywords: optimal transport
group feature selection
document classification
word embedding
TL;DR: We propose a linear time approximation of Wasserstein distance with word embedding selection.

Abstract: Wasserstein distance, which can be computed by solving the optimal transport problem, is a powerful method for measuring the dissimilarity between documents. In the NLP community, it is referred to as word mover's distance (WMD). One of the key challenges of Wasserstein distance is its computational cost since it needs cubic time. Although the Sinkhorn algorithm is a powerful tool to speed up to compute the Wasserstein distance, it still requires square time. Recently, a linear time approximation of the Wasserstein distance including the sliced Wasserstein and the tree-Wasserstein distance (TWD) has been proposed. However, a linear time approximation method suffers when the dimensionality of word vectors is high. In this study, we propose a method to combine feature selection and tree approximation of Wasserstein distance to handle high-dimensional problems. More specifically, we use multiple word embeddings and automatically select useful word embeddings in a tree approximation of Wasserstein distance. To this end, we approximate Wasserstein distance for each word vector by tree approximation technique, and select the discriminative (i.e., large Wasserstein distance) word embeddings by solving an entropic regularized maximization problem. Through our experiments on document classification, our proposed method achieved high performance.

A linear time approximation of Wasserstein distance with word embedding selection
Sho Otao and Makoto Yamada²
'yyoto University, Japan "Okinawa Institute of Science and Technology. Japan sho. otw.mml.........m....... ist. i. kyoto-u. ac
jc. jp, makoto. yamadaeoist. jp
Abstract
Wasserstein distance. More specifically, given a word embedding and the frequency of the words in each document, WMD is formulated as an optimal transport problem in the word embedding space.
Wasserstein distance, which can be computed by solving the optimal transport problem, is powerful method for measuring the dissimilar- ity between documents. In the NLP commu- word mover's distance (WMD). One of the key challenges of Wasser- stein distance its computational cost since needs cubic time. Although the Sinkhorn algo- rithm is powerful tool to speed up to compute the Wasserstein distance, still requires square time. Recently, a linear time approximation of the Wasserstein distance including the sliced Wasserstein and (TWD) has been proposed. However, linear time approximation method suffers when the dimensionality of word vectors high. In this study, we propose a method to combine feature Wasser- selection and tree approximation stein distance handle high-dimensional prob- lems. More specifically, we use multiple word embeddings and automatically select useful word embeddings in Wasserstein distance. To this end, we approxi- mate Wasserstein distance for each word vector by tree approximation technique, and select the discriminative (i.e., large Wasserstein distance) word embeddings by solving an entropic reg- ularized maximization problem. Through our experiments on document classification, our proposed method achieved high performance.
Although the optimal transport problem can be solved using a linear programming algorithm, it requires cubic computational time with respect to the number of samples. Cuturi (2013) proposed to introduce the entropy regularization to the opti- mal transport problem, which be solved with a square computational time with respect to the num- ber of samples by the Sinkhorn algorithm. How- ever, the Sinkhorn algorithm is too slow for prac- tical application in tasks such as natural language processing, that involve a large number of words. The tree- wass-assennteen distance (TWD) is method to measure the distance between distributions using tree structure, which approximate Wasser- stein distance with a linear computational time with respect to the number of nodes in the tree (Indyk and Thaper, 2003; Le et al., 2019; Back- urs et al., 2020; Sato et al., 2020; Takezawa et al., 2021, 2022; Yamada et al., 2022: Chen et al., 2022). As a method for constructing tree structures, In- dyk and Thaper (2003) proposed Quadtree, which constructs tree by recursively partitioning the original space. In addition, Le al. (2019) used hierarchical clustering to construct tree. Existing approaches successfully approximate the original optimal transport problems. However, when the dimensionality of the vectors (e.g., word vectors) is high, their performance can be degraded due to the curse of dimensionality.
nity, it is referred
Wasserssnnn distance
approximation of
1 Introduction
Wasserstein distance, which is obtained by solv- ing the optimal transport problem, powerful method for measuring the distance between distri- butions and is used in natural language processing to measure dissimilarity between documents (Kus- et al., 2015; Huang et al., 2016; Yurochkin et al., 2019; Yokoi et al., 2020; Sato et al., 2022), Kus- ner al. (2015) proposed word mover's distance (WMD), which uses word vectors to compute the ground metric of the Wasserstein distance and can measure dissimilarity between documents using
To address figh-dimensional problems, robust variants of optimal transport for high-dimensional data have recently been proposed (Paty and Cu- turi, 2019; Petrovich et al.. 2022). Paty and Cuturi (2019) proposed the subspace robust Wasserstein distances (SRW), which projects data into a sub- space and considers optimal transport in the sub- space. Petrovich et al. (2022) proposed feature-

---

robust optimal transport (FROT), which measures distances between distributions with group feature selection when feature groups are given as prior information. Since SRW and FROT alternately solve the feature selection optimization problems and the optimal transport problem with either lin- ear programming the Sinkhorn algorithm, they do not scale to large datasets. Therefore, applying these techniques to NLP tasks such document classification that involve large amounts of data is difficult.
for n--dimensional vector with all ones, and E" for a n--dimensional probability simplex.
Related works
In this section, we introduce Wasserstein distance, tree- Wasserstein distance, and optimal transport with feature selection.
2.1 Wasserstein distance
Given two set of d-dimensional vectors in eu- clidean spaces X (X1;..,,X,,) E Rdx= Y (Y1... Ym) E Rdxm and two weights a E E b E D we consider two discrete distribu- tions = Σi= 0;0x,, V/ = 2ز=1 byyy, The p- Wasserstein distance, which measures the distance between and v, is defined as follows:
In this study, we propose the tree- Wasserstein distance with group feature selection (TWD-GFS) to combine feature selection and TWD to han- dle high-dimensional problems and scale to large datasets. We consider setting in which some distributions are given as training data to select dis- criminative feature groups in advance. TWD-GI'S first constructs tree structure for each of the given feature groups (i.e., word embeddings), and out- put is the weighted sum of the TWD calculated using each tree. The weight for each feature group can be obtained by solving an entropic regularized maximization problem using the distribution of the training data. After training, TWD-GFS can mea- sure distances with selected features much faster than SRW and FROT. Through the synthetic ex- periments, we show that our proposed method can seleet discriminative features a high-dimmenional setting with a large number of noise features. Then, through the real experiment, we consider multiple word embeddings as feature groups and confirmed the performance of TWD-GFS on word embedding- based document classification tasks with word em- bedding selection.
T
Wp(H, [)=
min NEU(A))
Tayo y3)"
where (3) is a cost between x, and y,, is the transport plan, and U(4, v) is the following set of transport plans.
(14, v) (II RRXM. III =a II 1, =b.
This optimization problem is referred to as the optimal transport problem (Villani, 2009; Peyré and Cuturi, 2019). The optimal transport problem can be solved using linear programming algorithm. however, it requires (n = m) computational time. Cuturi (2013) introduced entropy regulariza- tion into the optimal transport problem, which can be solved in ((m) computational time using the Sinkhorn algorithm.
Contributions: Our contributions are follows:
2.2 Tree- Wasserstein distance
We propose a fast TWD-based method to se- lect discriminative feature groups and measure distances between distributions.
Tree- Wasserstein distance (TWD) (Indyk and Thaper, 2003; Le et al., 2019) approximates the 1- Wassersteii distance on a tree structure in a lin- time for the number of nodes in the tree. Given T (V, E) where V and E are the sets of nodes and edges, and
Through synthetic experiments, we show that our proposed method can select discriminative features in high-dimensional setting with large number of noise features.
metric dr, the TWD between two distributions μ and supported by defined as follows:
Through real experiments with document clas- sification tasks, consider multiple word embeddings as a feature group and show our proposed method with word embedding selec- tion achieved high performance.
W (H, Σ Ewlla(((vo)) v(T(v.)). cCE'
where an edge, w. R2 is weight of the edge e, Ue a node on the far side from the root edge e, and T(v,)) is a set of nodes belonging to a
Notation: In the following sections, we write 1,,

---

subtree whose root is node Ue. Moreover, Takezawa al. (2021) proposed matrix-form formulation of TWD.
et al. (2022) proposed feature-robust optimal trans- port (FROT), which measures distances based on selected feature groups when the information of feature groups is given.
Because TWD is computed using a given tree, the tree metric must represent the metric of the orig- inal space well. The tree metric is determined by tree structure and edge weights, and several meth- ods construct them have been proposed. First, In- dyk and Thaper (2003) proposed Quadtree, which is constructed by recursively dividing an original space into 2 regions, and the edge weights are 2-!(e) where ((e) is the depth of the edge e. Sub- sequently, Le et al. (2019) proposed an algorithm based on clustering. This tree is constructed by re- cursively clustering data with farthest-point cluster- ing, and the edge weights are the distances between the cluster centers in the original space. We call this algorithm Clustertree.
3 Proposed method
In this section, we describe a problem setting con- sidered in this research, our proposed method and comparison between our approach and existing techniques.
3.1 Problem settings
We suppose that the features of x E Rd are separated by groups x (x(1) ,..., x("))"
where x(f) E R4, and 2 dj = d. Even if no prior information on feature groups is given, each feature can be considered as a single group. We write the set of N vectors used in construct- ing the tree X (X1,,.,,XN) In document classification tasks, X is set of word vectors of all words in a dataset. We can rewrite X as (1(1) ........)) (.F) )T, where X()) (x(P) ..... (f) E RdyxN, For example, x(" is a word2vec, and xx") is Glove vector when consid- cring multiple word embeddings as feature groups. In this study, we consider a setting which some distributions (i.e., documents) [ 1. are given as training data for group feature selection. M is the number of available distributions. This setting is natural for the experiments with the k-nearest neighbor method in Section 5. Note that the labels of distributions not given.
Initial values must be provided for the center point of the split in Quadtree and the cluster cen- ters in Clustertree, they involve the disadvan- tage that the randomness of these initializations can significantly change the tree structure. Tree- sliced Wasserstein distance (TSW) (Le et al., 2019), which uses multiple trees constructed based on dif- ferent initializations, is defined as follows:
IRxxN
T
TSW (M, v)
Σ
Wa Wayr (H,)).
T
where Wa Warco v) is TWD calculated on tree t, and T is the number of trees. TSW can mitigate the effects of these initialization problems.
3.2 Tree- Free-Waseerstenn distance with group feature selection
2.3 Optimal transport with feature selection
Wasserstein distance is highly dependent on cost function c. Therefore, discriminative features with large distances between points useful for cal- culating the Wasserstein distance. Based on this idea, robust variants of optimal transport for high- dimensional data, which measures distances be- tween distributions while selecting discriminative features, have been proposed in recent years (Paty and Cuturi, 2019; Petrovich et al., 2022). These methods select discriminative features that max- imize the distance of distributions and measure distances in selected feature space. Paty and Cuturi (2019) proposed subspace robust Wasser- stein distances (SRW), which projects data into a discriminative subspace and computes optimal transport problem the subspace. Also, Petrovich
For high- dinge-immnsional vectors, the performance of TWD can be degraded due to the curse of dimen- sionality. The existing feature-robust optimal trans- port methods SRW (Paty and Cuturi, 2019) and FROT (Petrovich et al., 2022) alternately solve the optimal transport problem with a high cost and the feature selection optimization problem. Hence, they cannot scale to large datasets which involve large amounts of words. Then, we propose tree- Wasserstein distance with group feature selec- tion (TWD-GFS) to combine feature selection and TWD to handle high- nigh-dimensional problems and scale large datasets.
TWD-GFS constructs trees using each feature group x() < f I F), and then outputs the weighted sum of F TWDs with learned weights

---

w' oF the distance of distributions. TWD-
Algorithm 1 Weight learning algorithm.
GFS between μ and is defined as follows:
Input: The set of points separated by feature groups X (x(1) .... ,...,, (.,'x(")) B the training index-pair set Ω the hyperparame- ter 17 E R.
Σ War, (1,2),
Output: w* E FRF
where Ty is the tree constructed by using the fea- ture group and War, (H, v) is TWD between two distributions μu, v using Ty.
I: Construct (Ti,..., TT.) by using each feature group.
2: Calculate TWD for S using each tree and make
As well as SRW (Paty and Cuturi, 2019) and FROT (Petrovich et al., 2022), we learn weights to maximize (I), distances between distributions. The learned parameter w* requires that the weight wy corresponding the discriminative feature group f be larger. We create an index-pair set from the available distributions ( and learn w by solving the following problem:
Eiene W (us. Pb)
Φn
Σ (uss)E WOTe (Ms. Mj))
(
exp
3: Set w as
(1 51 f F).
Σ ==
concave function, the constrained optimization of (3) is a concave maximization and the optimal so- lution of (3) is uniquely obtained as follows:
w w arr max
Σ
Σ 1
wy Wyrr (Uis (2)
WEEF
(We
(da))
To simplify the notation, define Φn Ie as follows:
exp
wj
(4)
F' Sk=1
(0e))
exp
Ensien War, (Mis (5))
This derivation given Appendix A. Given the points X = (X(1)) ..... X (F) T e
Φn
Eusee War (1))H)))
RdxN the index-pair set Ω and the hyperparame- ter 1) E RR we obtain w according Algorithm
where fth dimension of Φn is the sum of TWDs calculated for Ω using the tree Ty. By using dg- we can rewrite (2) as follows:
1. After learning w measure the distances of the distributions by (1) using F trees constructed during training.
w = arg max W Φn-
WEEF
3.3 Comparison with other methods
where w* is one-hot vector with a value of 1 for dimension with the largest value in Φn and some-
In this subsection, compare proposed ap- proach with existing methods from two points of view.
0 for the other dimensions. However, times want more than one useful feature group. Then, we introduce the entropic regularization H H(w) - - -f ( wy - 1) and consider the following problem such that w is no longer one-hot vector:
Optimal transport with feature selection SRW (Paty and Cuturi, 2019) and FROT (Petrovich al., 2022) do not select features in advance and instead optimize for feature selection while solving the op- timal transport problem, which increases their com- putational time. TWD-GFS selects feature groups using some distributions in advance, so no addi- tional optimization is required after training. There- fore, TWD-GFS measure distances between distributions much faster than SRW and FROT after training. The training time of TWD-GFS depends on the time required to compute TWD, so is fast and does not have a high cost. addition, TWD- GFS uses multiple distributions as training data,
w" arg max w Oo (w) WERP
(3)
s.t. w 1 1,
where 77 > hyperparameter. The smaller 7). the closer w* is to a one-hot vector, and the larger is to a vector where all values
2), the closer are 1/F. Note that (w) naturally satisfics the nonnegative constraint, Since (ww) is a strongly

---

0.8
Quadtree
Custertree
15
0.6
10
0.4
-5
-15
10
15
10
70
90
X1
the number of noise features
(a) Synthetic 10 distributions.
(b) The approximation performance of TWD with noise features.
Figure I: The approximation performance of TWD with added noise features for synthetic 10 distributions.
which has the advantage of selecting useful fea- ture groups in common across the entire dataset compared to SRW and FROT.
trix and the mean of which was randomly sampled from a uniform distribution (--200 (1-20,20 20) in each dimension. We can consider 10C2 15 pairs of distributions. Next, added some noise features sampled from U 20) equal to the data range. For example, when the number the noise features 10, the number of features is 2- = 12. We calculated two lists, including a list of distances of 15 distribution pairs computed with 1-Wasserstein distance for two-dimensional data, and list of dis- tances of 45 distribution pairs computed with TWD for the data containing noise features. In Figure 1b, show the Pearson correlation coefficient (PCC) between these lists when noise features were added, Figure 1b shows that PCC worsened as the num- ber of noise features increased for both Quadtree and Clustertree, so TWD cannot approximate 1- Wasserstein distance on an original dimension well in the noisy settings due to the curse of dimension- ality.
TWD with learning tree structures and edge weights TWD-GF'S learns only tree weights and uses Quadtree and Clustertree as trees. Several methods have been proposed to learn tree structures and edge weights (Takezawa et al., 2021; Yamada et al., 2022; Chen et al., 2022), and the problem set- ting used in these methods differs from that of our proposed approach. First, Takezawa et al. (2021) proposed method to learn task-specific tree struc- tures when the distributions and the labels of the distributions are given as training data. Because we consider the settings where the labels of the distributions are not available, this method cannot be applied in our problem setting. Subsequently, Yamada et al. (2022) and Chen et al. (2022) pro- posed the methods to learn edge weights or tree structures and approximate the 1-Wasserstein dis- tance accurately. These methods all features, making it difficult to apply them our settings in which the original data contains unnecessary fea- tures. In future research, we expect these methods to be combined with feature selection.
Selecting useful features is important in the high- dimensional setting with large number of noise features as described above. We show that our proposed method can correctly select the original two-dimensional features among all features. the following experiment, the number noise fea- tures was 20 and the total number of all features was 22, and we let Zo, I1 be the original features and .2,,.., ......,,- T21 be the noise features. Suppose that the feature groups as prior information given [0,, 1), (2, 3), (20, 21)], where two features are given as single group and the number of groups 11. We learned weights using Algorithm and checked the values of w As input to Algorithm I, the data X were all 22-dimensional points belong-
4 Synthetic experiments
In this section, we show that our proposed method can select the correct feature groups in high- dimensional settings with lot of noise features. In this experiment, we first created 10 distribu- tions in two dimensions as shown in Figure la. Each distribution contained 20 points and followed a separate multidimensional normal distribution, the covariance matrix which was an identity ma-

---

ing to 10 distributions, the index-pair set as training data was S {0, 1). (0, 2), .... (8. (| 45), which was all pairs of distributions, and the hy- perparameter was set to 0.1 in both of Quadtree and Clustertree. We chose the small hyperparame- ter because we know the true feature group in the synthetic data, and it is reasonable to expect bet- ter results with the small regularization parameter, which makes the learned weights closer one- hot vector. As a result, for both methods, the value of the weight corresponding to the feature group (0, 1) became more than 0.99, and other weight val- ues were less than 0.01. These results indicate that our proposed method correctly selected the original two-dimensional features using the training data.
degraded due to the curse of dimensionality. Hence, we can consider group feature selection with our proposed method to select important word vectors from the concatenated word vector. As a baseline method to avoid the curse of dimensionality of the concatenated word vector, we used PCA. The re- sults of this experiment showed that our proposed method with Clustertree achieved the best perfor- mance among the methods using the concatenated word vector. The results also demonstrated that our proposed method achieved high performance across all datasets.
5.2 Other feature-robust methods
We additionally compare our proposed method with other feature-robust methods. We mentioned FROT (Petrovich al., 2022) and SRW (Paty and Cuturi, 2019) feature-robust methods. However, FROT needs about 30 times and SRW needs about 800 times more than TWD-GFS as shown in Figure 5 in Appendix E. Thus, applying FROT and SRW to document classification tasks is practically diffi- cult. Therefore, we conducted experiments using FROT on BBCSPORT, TWITTER, and RECIPE, which relatively small datasets. FROT is based on group feature selection, nated word embeddings and considered five word embeddings as feature groups for FROT as well as our proposed method.
5 Real experiments
In this section, we evaluate the performance of our proposed method through word embedding- based document classification experiments on real datasets. We used five open datasets,, including BBCSPORT, TWITTER, AMAZON, CLASSIC, and RECIPE. Each dataset has five splits of train- ing and test data. The detail of the datasets given in Appendix B. We used the k-ncarest neighbor (k-NN) algorithm and evaluated its performance in terms of the average of the test error rate computed for each split. Moreover, we discuss the computa- tional time of TWD-GE GFS and other methods with optimal transport in Appendix E.
used concate-
5.3 Experimental settings
5.1 Word embeddings
As model of word embeddings, we used word2vec2 (Mikolov al., 2013), Glove? (Pen- nington et al., 2014), and fastText (Bojanowski et al., 2017: Mikolov al., 2018). These pretrained models are publicly available, including versions trained on different corpora. In this experiment, we used five different pretrained models as shown in Table 1. All of these word vectors were 300- dimensional. Derived from the model and corpus, denote the five word embeddings word2vee, Glove(crawl), Glove(wiki), fastText(crawl), and f'astext( (wiki), respectively.
The performance of document classification using optimal transport depends on word embeddings, and using the appropriate word embedding is very important. The experiments in (Kusner et al., 2015) showed that the performance of WMD each dataset differed depending different word em- bedding models and training corpora. In this study, we consider using multiple word embeddings in- stead of single word embedding to obtain good performance across all datasets. A lot of meth- ods to get a more useful word embedding from given word embeddings have been proposed (Yin and Schütze, 2016; Ghannay et al., 2016; Bolle- gala et al., 2018; Bollegala and Bao, 2018), and the concatenation of different word embeddings for each word often used as a powerful baseline method. However, given the high dimensionality of the concatenated word vector, performance may be
We denote the concatenated word vectors and the concatenated word vectors with PCA as Concat and Concat(PCA) respectively. Concat had 1500 di- mensions and we reduced Concat(PCA) from 1500 to 300 dimensions by PCA. Before using PCA, we
hhttps://code.gon gowp:///edd....ge....... com//rrchive/p/werddeees https:///Ip..saanfos pew/prooeccts//gooeee/////// 'https://fasttext. http:///tteer..cceec/////////tee
cnttps://githhe httt:p////ggituub..mmm/ssseeeere momm/mkusne///dd
html

---

Model
Corpus
Vocabulary
Vector length
word2vec
Google News
3M
300
Common Crawl
2.2M
300
Glove
Wikipedia 2014 + Gigaword 5
400K
300
TastText
Common Crawl
2M
300
(w/o subword)
Wikipedia 2017, UMBC webbase corpus and statmt.org news
1M
300
Table I: Pretrained word embeddings used in real experiment.
first standardized word vectors. We used TSW with three trees for the evaluation of baseline methods: Concat, Concat (PCA), and five word embeddings. As the hyperparameters, we decided the number of index-par -aaer-ppirr&o set Ω to 10000, and the candidate values of 1) to [0.01, 0.05, 0.1, 0.5, 1.0]. For Ω we randomly selected 10000 pairs of documents from the training dataset. Because we considered prob- lem setting in which we cannot use the labels of the distribution in training, we did not perform any validation for and instead determined the best value based on the experimental results for each
5.5 Results
The performance for different r) In Figure 2, show the test error rates of TWD-GFS for dif- ferent y in Quadtree and Clustertree on the TWIT- TER, CLASSIC, and RECIPE datasets. We show the results for other datasets in Appendix D. We concluded that the best hyperparameter across all datasets was = 1.0 for Quadtree and 0.1 for Clustertree, respectively. We show the mean of weights learned with the best on five splits for each dataset in Figure Figure 2 shows that the performance with Quadtree improved as the value of increased. This result indicates that TWD- GFS with Quadtree performed better when each word vector was equally weighted, as shown in Figure 3a. When constructing Quadtree, the re- gions to be divided increase exponentially as the dimension of the original space increases. Then, each word vector is assigned to different region, so the distance between each word on the tree is approximately equal. Therefore, the distances be- tween distributions were approximately equal for each word embedding, and group feature selection based on distances did not work. Figure 2 also shows that the performance with Clustertree for 1) 0.1 was higher than that for 1.0. Un- like Quadtree, this result indicates that selecting word embeddings with Clustertree, shown in Figure 3b, performed better than treating all word embeddings equally. In addition, the test error rate for = 0.01 was large for the four datasets ex- cept CLASSIC. The learned weights with v) = 0.01 were close to the one-hot vector, so almost only one word embedding was selected, which rendered the performance unstable due to the randomness of the initialization when constructing the tree. Moreover, Figure 3b shows that Glove(crawl) and Glove(wiki) were useful word embeddings across all datasets.
We implemented Quadtree, Clustertree, and TSW with reference to the public implementation" of Yamada et al. (2022). Also, we used the pub- lic implementation of Petrovich et al. (2022) for FROT and set all hyperparameters to the default ones of this implementation. Besides, we used the public implementation" for k-NN without valida- tion of k. We evaluated all methods using Intel Xeon CPU E5-2690 v4 (2.60GHz).
5.4 Preprocessing
In our proposed approach, the distances between points in the feature groups must be measured on the same scale. TWD-GFS learns the weights ac- cording to the magnitude of TWD calculated for each feature group and TWD is highly dependent on the scale of the distance between points, so this preprocessing step is required. In this experiment, we calculated the distances between all words and divided each word vector by the average of the distances for each word embedding. With this pre- processing, the distances between points in each word embedding have an average of I, and their scales are aligned.
We explain other preprocessing required for us- ing multiple word embeddings in Appendix C.
Comparison to the tree-based methods Next, we compared the performance TWD-GFS against the tree-based methods comprising five
hhttps: htttps://github... http://co///i/tteeeeeeee chttps://githin wtt.//too/////////e /FtT 'https: htt.tggttttttttee cow. com/mkusner/wwt

---

TWITTER
CLASSIC
RECIPE
31.0
5.5
44.0
30.5
Choserrzse
Custartra
Quaterres
24.5-
38.
(1.3)
Ten 20t rale (H2
00.51
(6.7)
13.0
(0.3)
(0.1)
(0.
42 87-
00.51
20.5
24.0
10.5)
10.59
0.51
10.0
18-31 16.6)
20.
00.5
204
201
0135
3.5
1.3
0111
3.55
011
09
1.0
201 4.55
01
0331
31
06
10
00.0
200
015
0L
1.3
6611
516
05
Figure 2: The error rates the k-NN of our proposed method for each 1). We write the mean of five splits and the standard deviation in parentheses.
word2vec Gooeecraww)
8 9.5
PostTextwwik)
88CSPORT
TWITTER
AMAZON
CLASSIC
RECIPE
(a) Quadtree (1) 1.0)
word2vec
0.5
Goveecrew
Goveceict)
3
festText/wile)
D0CSPORT
TWITTER
AMAZON
CLASSIC
RECIPE
(b) Clustertree (1) = 0.1)
Figure 3: The mean of weights learned five splits using proposed method.
word embeddings, Concat, and Concat(PCA). The results are shown Table 2. The performance of TWD-GFS is written only = 1.0 for Quadtree and = 0.1 for Clustertree. At first, we found that the best word embedding depends on the dataset and the method of tree construction, and that each word embedding performed best at least one item. From this result, may be expected that using these five word embeddings would perform better across the dataset. Also, we found that the performance of fasiText(wiki) with Quadtree on AMAZON is considerably worse than other combi- nations of word embeddings of datasets. On AMA- ZON, the tree does not effectively approximate the original Euclidean space due to outlier words represented using fastText(wiki), making its per- formance worse. Using multiple word embeddings may also be expected to mitigate such challenges depending on specific word embedding.
weighted. TWD-GFS with Clustertree achieved higher performance than Concat and Concat(PCA) on all datasets. These results show that our pro- posed method with Clustertree can select useful features and mitigate the curse of dimensionality better than simple dimensionality reduction. Also. TWD-GFS with Clustertree achieved the best per- formance among all word embeddings with Clus- tertree on CLASSIC and RECIPE. For the other dataset, TWD-GFS with Clustertree achieved high average performance while the performance dif- fered for each word embedding. For example with Clustertree, fastText(wiki) achieved the best per- formance on BBCSPORT, but performed poorly on AMAZON and CLASSIC. The performance of TWD-GFS slightly worse than that of fastText(wiki) in BBCSPORT, but is considerably higher on AMAZON and CLASSIC.
On the other hand, the performance of TWD- GFS with Clustertree is lower than that with Quadtree on TWITTER and CLASSIC, despite Quadtree not being effective for feature selection. These results are primarily influenced by TWD's s
TWD-GFS with Quadtree did not significantly outperform Concat and Concat(PCA) because, as already mentioned, group feature selection did not work and each word embedding is equally

---

Quakrer
Chaderteee
BBCSPORT
TWITTER
AMAZON
CLASSIC
RECIPE
BBCSPORT
TWITTER
AMAZON
CLASSIC
RECIPE
waddive
37 0.9
28,6
10.4 0.
40-+003
42.9 +11
3.3 0.7
294 + 0.5
11.1 + 0.6
5.5 1.5
42.5 D.6
(lozienn)))
4.2
106 0.3
3.9 Lu
42.7
4.0 0.
255 1.3
5.1 11::66
42.5 066
Glovetwib)
104+002
4.74-.
424
42.8.2
121:008
69:2:09
40.2
127:100
11:10
Concut
38
10.5
42.5
106--02
4.6 0.3
4.2
42.8.2:
295
11:
48:2:00
42.1 0.3
4.3.07
42.6
Table 2: Test error rates of all tree-hased methods in the k-NN. The lowest test error rate in each dataset is shown in bold. We write only 1) 1.0 for Quadtree and 17 0.1 for Clustertree.
BBCSPORT
TWITTER
RECIPE
high computational costs, TWD-GFS can scale to large datasets owing to the rapid computation TWD. TWD-GFS can select discriminative feature groups by solving the entropic regularized maxi- mization problem. Through synthetic experiments, showed that our proposed method select dis- criminative features in high-dimensional setting with large number of noise features. Through real experiments, we considered multiple word embeddings as a feature group and applied TWD- GFS to word embedding selection. We confirmed that TWD-GFS with clustering- based trees outper- formed the methods using concatenating word em- beddings and achieved high performance across all datasets.
Concat
3.8 + 0.5
29.7 0.9
42.2 + 0.3
Concat (PCA)
3.6 0,8
29.5 1.1
42.1 0.3
TWD-GFS
3.5 1.2
29.1 1.3
41.8 0.6
FROT
3.6 = 0.7
29.1 101:00 0.5
41.9 1.0
Table 3: Test error rates of FROT and three Clustertree- based methods in the k--N. The error rates of Clustertree-bssed methods are the same as in Table 2.
inherent performance characteristics rather than the effectiveness of feature selection. Prior studies TWD (Le al., 2019; Takezawa al., 2021; Ya- mada al.. 2022; Chen al., 2022) have shown that the effectiveness of Quadtree and Clustertree varies depending on datasets and tasks. In our ex- periments on TWITTER and CLASSIC, we found that Quadtree outperforms Clustertree for other baseline methods well TWD-GFS. It is impor- tant achieve higher performance than the base- line using the same tree construction method.
Limitations
Our proposed approach involves major limi- tations. First, TWD-GFS cannot perform group feature selection training data is not provided. We can apply TWD-GFS to k-NN because train- ing data is given, but cannot apply it to some tasks such as unsupervised semantic textual similarity (STS) tasks in which training data is not available. Second, the larger the number of feature groups, the more time is required to construct trees. In our real experiments, we used five word embedding. which did not require large amount of time for constructing trees. If we had used one hundred word embeddings, for example, it would take 20 times longer to construct trees. When the train- ing data is given and the number of given feature groups is not too large, TWD-GFS can be used fast and powerful tool for group feature selection and measuring the dissimilarity of documents.
Comparison to the feature-robust method Fi- nally, we checked the performance of FROT. We show the performance of FROT with the flustettree-base methods in Table 3. The per- formance of FROT is slightly higher than Concat and Concat (PCA) with Clustertree, which are our baseline methods, and comparable to TWD-GFS with Clustertree. This result shows that the effec- tiveness of the feature selection of TWD-GFS with Clustertree is equivalent to FROT. We emphasize that TWD-GFS can achieve the equivalent perfor- mance of FROT with much lower computational time.
6 Conclusion
A Acknowledgements
In this study, proposed TWD-GFS bine TWD and group feature selection to handle high-dimensional problems in the tree approxima- tion of the Wasserstein distance. Unlike existing feature-robun methods of optimal transport with
We thank Han Bao for his helpful comments. Sho Otao and Makoto Yamada were supported by MEXT KAKENHI Grant Number 21H04874.

---

References
François-Piers Paty and Marco Cuturi. 2019. Subspace robust Wasserstein distances. In International Con- ference on Machine Learning.
Arturs Backurs, Yihe Dong, Piotr Indyk, Ilya Razen- shteyn, and Tal Wagner. 2020. Scalable nearest neigh- bor search for optimal transport. In International Conference on Machine Learning.
Jeffrey Pennington, Richard Socher, and Christopher Manning. 2014. GloVe: Global vectors for word representation. In Conference Empirical Methods in Natural Language Processing.
Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov. 2017. Enriching word vectors with subword information. Transactions of the Associa- tion for Computational Linguistics, 5:135- 146.
Mathis Petrovich, Chao Liang, Ryoma Sato, Yan- bin Liu, Yao-Hung Hubert Tsai, Linchao Zhu, Yi Yang. Ruslan Salakhutdinov, and Makoto Ya- mada. 2022. Feature-robust optimal transport for nigh-dimensional data. In European Conference Machine Learning and Principles and Practice of Knowledge Discovery in Databases.
Danushka Bollegala and Cong Bao. 2018. Learning word embeedinns by autoencoding. In Interna- tional Conference on Computational Linguistics.
Danushka Bollegala, Kohei Hayashi, and Ken ichi Kawarabayashi. 2018. Think globally, embed lo- cally - locally linear meta-embedding of words. In International Joint Conference on Artificial Intelli- gence.
Gabriel Peyré and Marco Cuturi. 2019. Computational optimal transport: With applications to data science. Foundations and Trendy0 in Machine Learning, I (1(5- 6):355 607.
Samantha Chen, Puoya Tabaghi, and Yusu Wang. 2022. Learning ultrametric trees for optimal transport re- gression. arXiv preprint arXiv:2210. 12.1:222.0.1228..
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. 2020. Fast unbalanced optimal transport tree. In Advances in Neural Information Processing Systems.
Marco Cuturi. 2013. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. 2022. Re-evaluating word mover's distance. In Inter- national Conference on Machine Learning.
Sahar Ghannay, Benoit Favre, Yannick Estève, and Nathalie Camelin. 2016. Word embedding evalu- ation and combination. International Conference on Language Resources and Evaluation.
Yuki Takezawa, Ryoma Sato, Zornitsa Kozareva, Sujith Ravi, and Makoto Yamada. 2022. Fixed support tree-sliced wasserstein barycenter. In International Conference on Artificial Intelligence and Statistics.
Gao Huang, Chuan Guo, Matt Kusner, Yu Sun, Fei Sha, and Kilian Q Weinberger. 2016. Supervised word mover's distance. In Advances in Neural Information Processing Systems.
Yuki Takezawa, Ryoma Sato, and Makoto Yamada. 2021. Supervised tree-wasserstein distance. In Inter- national Conference on Machine Learning.
Piotr Indyk and Nitin Thaper. 2003. Fast image retrieval via embeddings. In International Workshop Sta- tistical and Computational Theories of Vision
Cédric Villani. 2009. Optimal transport: old and new, volume 338. Springer.
Matt Kusner, Yu Sun, Nicholas Kolkin, and Kilian Wein- berger. 2015. From word embeddings to document distances. In International Conference on Machine Learning.
Makoto Yamada, Yuki Takezawa, Ryoma Sato, Han Bao, 7ornitsa Kozareva, and Sujith Ravi. 2022. Ap- proximating I-wasserstein distance with trees. Trans- actions on Machine Learning Research.
Tam Le, Makoto Yamada, Kenji Fukumizu, and Marco Cuturi. 2019. Tree-sliced variants of wasserstein distances. In Advances in Neural Information Pro- cessing Systems.
Wenpeng Yin and Hinrich Schütze. 2016. Learning word meta-embeddings. In Annual Meeting of the Association for Computational Linguistics.
Tomas Mikolov, Edouard Grave, Piotr Bojanowski, Christian Puhrsch, and Armand Joulin. 2018. Ad- vances in pre-training distributed word representa- tions. In International Conference on Language Re- sources and Evaluation.
Sho Yokoi, Ryo Takahashi, Reina Akama, Jun Suzuki, and Kentaro Inui. 2020. Word rotator's s distance. In Conference on Empirical Methods in Natural Lan- guage Processing.
Tomas Mikolov, llya Sutskever, Kai Chen, Greg S Cor- rado, and Jeff Dean. 2013. Distributed representa- tions of words and phrases and their compositionality. Advances Neural Information Processing Sys- lems.
Mikhail Yurochkin, Sebastian Claici, Edward Chien, Farzaneh Mirzazadeh, and Justin M Solomon. 2019. Hierarchical optimal transport for document repre- sentation. Advances Neural Information Pro- cessing Systems.

---

A The optimal solution of (3)
B Dataset details
this section, we prove that the optimal solution of the constrained concave maximization problem (3) becomes (4).
Table shows the dataset details that include the number of documents, the number of unique words (bag-of-worde dimension), and the average number of unique words in one document.
Proof. We define À R as the lagrange multiplier and define L(w) follows:
name
BOW dim.
avg words
I(w)= = w Φn + (H(W) + A(w 1p-1) 1)
BBCSPORT
737
13243
117
TWITTER
3108
6344
9.9
F
wwT Pn " Σ
wy(log w 1)
AMAZON
8000
42063
45,0
CLASSIC
7093
24277
38.6
f=1
RECIPE
4370
5708
48.5
+ A(w 1) 1).
Table 4: The datasets used for real experiments.
Taking the derivative of L(w) with wy, we get
@T((w) ( 17ll w + + Owy
C Preprocessing for using multiple word embeddings
aL(w) O, we get
Setting
In this section, explain two preprocessing for using multiple word embeddings in the experiments of document classification.
dhi
uloguy wy = (Ra)s + A.
First, because the number of words in the vocab- ulary covered by each word embedding is different, deleted words that were not covered by each word embedding and performed document classi- fication with the deleted vocabulary. In Coneat, Concat(PCA), and our proposed method, we used only the common part of the vocabulary covered by the five word embeddings and removed the other words. This preprocessing tends to disadvantage the word embeddings with a small vocabulary and our proposed method, but we confirmed that this preprocessing did not affect performance the document classification tasks.
Solving for wy. we get
( 1)
wy exp
exp
From w T 1F 1, we get
exp ()) - exp (102)))
Σ
From the above results, the optimal solution wi becomes as follows:
(0n)) 77
exp
Second, we deleted apostrophes in a word for the word embeddings other than word2vec. The four word embeddings other than word2vec cover few words containing apostrophes. However, they cover the words with upostrophes removed in many cases, For example, "we've". contraction of "we have", not covered by four word embeddings other than word2vee, but "weve" without the apos- trophe is covered by all word embeddings. There- fore, we deleted apostrophes in a word for the word embeddings other than word2vec to increase the available vocabulary.
w
1=1 exp
Therefore, this is equal to (4).
D Additional experimental results
We show additional experimental results docu- ment classification Figure 4.

---

BBCSPORT
AMAZON
4.6
Clustertree
Quantree
22
(9.5)
20.9
Clustertree
Quadtree
test rate (%)
test error rate (%)
1.2
3.9
(1.0)
3.8
3.8
3.8
16
3.6
3.7
(1.2)
(1.2)
(1.2)
(1.0)
14
3.5 3.5
(4.2)
(0.9)
(1.2) (1.3)
(1.2)
3.4
10.8
(0.7)
(0.6)
10.5 (0.3)
10
3.0
8
0.01
0.1
Figure 4: The test error rates in the k-NN of our proposed method for each y. We write the mean of five splits and the standard deviation in parentheses.
E
Computational time
We show the average computational time to com- pare 500 documents with one document for all datasets in Figure 5. We randomly sampled pairs of one document and 500 documents 50 times and measured the average computational time. We wrote time relative to TWD-GFS with Quadtree above each bar. We show the same results sepa- rately for each method in Figure facilitate un- derstanding the differences for datasets each method. Figure shows that the computational time of TWD-GFS almost the same whether Quadtree or Clustertree is used and faster than other methods on all datasets. FROT and SRW much slower than TWD-GFS, that applying existing feature-robust methods with the Sinkhorn algorithm large dataset difficult. In particular, SRW very slow because uses an cigenvalue dccomposition as its inner solver for dimensionality reduction. Figure 6 shows there are slight differences in the computational time depend- ing on datasets in each method. The computational time of TWD-GFS depends on the number of all unique words (BOW) in each dataset and that of the other methods depends on the number of unique words in a document. We confirmed the similar ten- dency Figure For example, because RECIPE has the smallest BOW dimension and many words in one document, TWD-GFS on RECIPE requires low computational time and the other methods on it require a relatively high computational time.
In this section, we discuss the computational time of TWD-GFS in terms of inference and training.
E.1 Inference time
First, we discuss the computational time of mea- suring between distributions. We compared TWD- GFS (Quadtree and Clustertree) with Wasserstein distance solved by the Sinkhorn algorithm (Cuturi, 2013) and existing feature-robust methods that in- clude FROT (Petrovich et al., 2022) and SRW (Paty and Cuturi, 2019). We used matrix-form formula- tion proposed in (Takezawa et al., 2021) for TWD and implemented Quadtree and Clustertree with reference the public implementation of Yamada al. (2022). We used the Python optimal transport (POT) package² for the Sinkhorn algorithm. We used the public implementation of Petrovich et al. (2022) for 1R and Paty and Cuturi (2019) for SRW'I, Both SRW and FROT alternately solve optimal transport problems and feature selection optimization problems, and used the Sinkhorn algorithm their inner solver of optimal trans- port problems. As a word embedding, we used 1500-dimensional vectors concatenating five word embeddings as well as used in document classifi- cation tasks. We gave five word embeddings as feature groups to TWD-GFS and FROT and set subspace dimension of SRW to 300. We evaluated all methods on NVIDIA RTX A6000 GPU.
confirmed
E.2 Training time
"https://gittee httpib..coo//iii/ com//iit/tree0T
Second, we discuss the computational time of construction and training (calculating TWD) for TWD-GFS. We call Step of Algorithm as tree construction, and Step as training. We used the
"httpss:/pythooot. thub. ww/iiddxx.htt
http://:///gggtuuuu.o///a//taaia SudspacceRcbusttaassertete

---

same experimental settings in Section and recorded the computational time on one of the five splits of training and test data. The results of Quadtree and Clustertree are shown in Table 5 and Table 6, respectively. The computational time for training is small because the calculation of TWD is fast. On the other hand, the computational time for tree construction seems large first glance, but it is reasonable because trees for inference while we need to make cost matrix for every inference in other methods.
constructed
NexI, we discuss how the computational time tree construction and training scales different datasets and feature groups. As shown in Table 5 and Table 6, the whole training time is reason- able even when dealing with large datasets, such as AMAZON. Though the cost of tree construction, which is large part of the whole training time, de- pends on the BOW dimension of the dataset, can apply our proposed approach to large datasets in practical scenarios. On the other hand, the compu- tational time for tree construction is proportionate to the number of feature groups. Therefore, TWD- GFS may face difficulties when confronted with an extensive number of feature groups, highlighted in the Limitations section. Exploring alternative depen-
approaches for constructing trees that dent on the number of feature groups is identified as a potential avenue for future research.

---

(tllader)
Sinthorn
FROT
SRW
seconds
10"1
10.9
x1100:11
X1O01
10
BBCSPORT
TWITTER
AMAZON
CLASSIC
RECIPE
Figure 5: The average computational time to compare 500 documents with one document. The time relative to TWD-GFS with Quadtree is written above each bar.
TWD-GFS (Quad)
TWD-GFS (Cluster)
Sinchom
34x12
33
335
32x12
22
32K18"
226
315
232
ASAZON
EWITIE
4.15
2."
935
AMNTON ALAIC
ARCAPOTT TWITICK
Figure 6: The average computational time compare 500 documents with document separately for each method. The values are the same as in Figure 5,
BBCSPORT
TWITTER
AMAZON
CLASSIC
RECIPE
Tree construction
82.0
32,7
293.1
144.0
36.5
Training
4.4
1.8
3.1
2.6
3.0
Tree const. Training
86.4
34.5
296.2
146.6
39.5
Table 5: The computational time [seconds] for tree construction and training for Quadtree.
BBCSPORT
TWITTER
AMAZON
CLASSIC
RECIPE
Tree construction
48.4
23.4
139.3
84.2
25.1
Training
4.6
1.8
3.1
2.6
2.7
Tree const. + Training
53.0
25.2
142.4
86.8
27.8
Table The computational time [seconds] for tree construction and training for Clustertree.


Reviews:
[{"review_id": "AdEl4x5i3C", "reviewer": "Reviewer_ybsA", "summary": "", "questions": "A. Line 407: Why were these values of eta chosen for synthetic data? The values appear to be opposite to the optimal ones for real data.\nB. Figure 3: Why is the performance of fastText(wiki) on Twitter considerably worse than all other embedding/dataset combinations?\nC. Lines 569-480: Do you have any intuition for the reasons behind these results?\nD. Line 791: Why not compare tree-construction and training time for TWD-GFS with cost matrix calculation time for other methods? How did that scale for different datasets and feature groups?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable questions and comments.\n\n> A. Line 407: Why were these values of eta chosen for synthetic data? The values appear to be opposite to the optimal ones for real data.\n\n$\\eta$ can control how soft the feature weights are. If we set the regularization smaller, a few features are used for Wasserstein computation, while the large number of features can be used if we set the large regularization parameter. \n\nIn the synthetic data, we know the true feature set, while we do not know the true feature set for real-world data. Thus, it is natural to get better results with the small regularization parameter for synthetic data, while we may get good performance with the large regularization parameter for real-world data. In our experiment, we set $\\eta$ to $1.0$ in Clustertree, because we observed that $\\eta=1.0$ makes the feature weight vector to a one-hot vector. It does not change the result even if we use $\\eta = 0.1$. In the final version, to avoid confusion, we will change the result with $\\eta=0.1$.\n\n\n> B. Figure 3: Why is the performance of fastText(wiki) on Twitter considerably worse than all other embedding/dataset combinations?\n\nIt seems that you might be referring to Table 2 instead of Figure 3, and AMAZON instead of TWITTER.\nIn AMAZON, the tree does not effectively approximate the original Euclidean space due to outlier words represented using fastText(wiki), making its performance worse. Using multiple word embeddings can help mitigate such challenges depending on a specific word embedding.\n\n> C. Lines 569-480: Do you have any intuition for the reasons behind these results?\n\nIt has been reported that using multiple word embeddings improves the average performance for many datasets in many NLP tasks [1, 2, 3, 4]. So, it is natural that TWD with multiple word embeddings can get high performance. Moreover, TWD-GFS can achieve higher accuracy because it can avoid the curse of dimensionality thanks to the feature selection. \n\n> D. Line 791: Why not compare tree-construction and training time for TWD-GFS with cost matrix calculation time for other methods?\n\nThank you for pointing this out. In this paper, we focus more on the computation in inference time. Overall, the computation of the training time for Quadtree and Clustertree are reasonable as summarized in the following tables. Note that we need to construct trees only once and can reuse for inference time while we need to make a cost matrix for every inference in other methods. Moreover, the inference time for the proposed method is much smaller than that of Sinkhorn, FROT and SRW as shown in Figure 6 of the appendix.\n\n|   Quadtree  [seconds]       | BBCSPORT | TWITTER | AMAZON | CLASSIC | RECIPE |\n|-----------------------------|----------|---------|--------|---------|---------|\n| Tree construction ($T=5$)   | 82.0     | 32.7    | 293.1  | 144.0   | 36.5    |\n| Training (\\|$\\Omega$\\|=10000) | 4.4      | 1.8     | 3.1    | 2.6     | 3.0     |\n| Tree const. + Training      | 86.4     | 34.5    | 296.2  | 146.6   | 39.5    |\n\n|   Clustertree  [seconds]    | BBCSPORT | TWITTER | AMAZON | CLASSIC | RECIPE |\n|-----------------------------|----------|---------|--------|---------|---------|\n| Tree construction ($T=5$)   | 48.4     | 23.4    | 139.3  | 84.2    | 25.1    |\n| Training (\\|$\\Omega$\\|=10000) | 4.6      | 1.8     | 3.1    | 2.6     | 2.7     |\n| Tree const. + Training      | 53.0     | 25.2    | 142.4  | 86.8    | 27.8    |\n\n>  How did that scale for different dataset and feature groups?\n\nAs shown in the above table, the training time of TWD-GFS is reasonable even when dealing with large datasets, such as AMAZON. \nThough the cost of tree-construction, which is a large part of training time, depends on the BOW dimension of dataset, we can apply our proposed approach to large datasets in practical scenarios.\n\nOn the other hand, the computational time for tree construction is proportionate to the number of feature groups. So, TWD-GFS may face difficulties when confronted with an extensive number of feature groups, as highlighted in the Limitations section. Exploring alternative approaches for constructing trees that are not solely dependent on the number of feature groups is identified as a potential avenue for future research.\n\nWe will include the discussion in the final version.\n\n\n\n> Figure 7: Y-axes should have the same scale for direct comparison.\n\nWe have already reported the results with the same time scale in Figure 6.\n\n## References\n\n[1] Wenpeng Yin and Hinrich Schütze. 2016. Learning word meta-embeddings. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics.\n\n[2] Sahar Ghannay, Benoit Favre, Yannick Estève, and Nathalie Camelin. 2016. Word embedding evaluation and combination. In Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC’16)\n\n[3] Danushka Bollegala, Kohei Hayashi, and Ken-ichi Kawarabayashi. 2018. Think globally, embed locally—locally linear meta-embedding of words. In IJCAI.\n\n[4] Danushka Bollegala and Cong Bao. 2018. Learning word meta-embeddings by autoencoding. In Proceedings of the 27th International Conference on Computational Linguistics.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "Calculating the word-mover's distance is a useful metric for comparing the similarity of text documents, and this paper presents a way to speed up these comparisons when working with large sets of documents. The performance gain over prior approaches is substantial.", "reasons_to_reject": "No strong reasons to reject. The approach appears to work well primarily for a select range of training data size and feature group numbers, as is addressed in the limitations section.", "questions_to_authors": "A. Line 407: Why were these values of eta chosen for synthetic data? The values appear to be opposite to the optimal ones for real data.\nB. Figure 3: Why is the performance of fastText(wiki) on Twitter considerably worse than all other embedding/dataset combinations?\nC. Lines 569-480: Do you have any intuition for the reasons behind these results?\nD. Line 791: Why not compare tree-construction and training time for TWD-GFS with cost matrix calculation time for other methods? How did that scale for different datasets and feature groups?", "paper_topic_and_main_contributions": "This paper studies the calculation of the word-mover's distance with word embeddings and proposes an approximation-based approach to improve performance. It presents a tree-based method to measure inter-distribution distances which can select discriminative features in a high-dimensional and noisy setting and manage to achieve good performance.", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "Line 406: Remove extra space before comma.\nLine 418: Remove extra space before footnote.\nLine 807: Missing word? “As a word embedding, we used 1500-dimensionnal vectors concatenating five word embeddings as well as used in document classification tasks.”\nLine 465: Should be “... on different corpora”.\nFigure 7: Y-axes should have the same scale for direct comparison."}}, {"review_id": "s5qIxnLgPc", "reviewer": "Reviewer_yRiE", "summary": "", "questions": "1. In the synthetic experiments, how do we set up feature groups?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable questions and comments.\n\n> 1. The technical contribution is limited. The key idea of this feature selection is to identify a soft maximum of tree Wasserstein distances conditional on groups. It relies on a pre-defined group. So this restricts the application methods in such a specific case where multiple feature groups are available.\n\nWe respectfully disagree with this comment. In feature selection literatures, having a pre-defined group is a common setting and useful in practice. For example, the group Lasso [1], which is a widely used statistics method, assumes to have a pre-defined feature group. Moreover, we can use the proposed method for a standard feature selection setup if we do not have prior information; each group consists of a feature. \n\nTree-Wasserstein distance is renowned for its speed and performance in document distance style application, relying heavily on word embeddings. Furthermore, leveraging multiple embeddings enhances performance across diverse NLP tasks [2, 3, 4, 5]. However, integrating multiple word embeddings can introduce the curse of dimensionality due to their high dimensionality. Our proposed approach effectively addresses this challenge.\n\n\n> 2. There are still gaps between the performance of the targeting task and the feature selection problem. If this method is proposed for document distance style application, it is not clear why a better feature selection yields better performance of document distance.\n\nIn general, since the tree-Wasserstein distance computation heavily depends on word embeddings as compared in Table 2, the document classification performance can be improved by selecting a good word embedding for the task. Thus, if we can automatically select useful word embeddings, we can improve the classification accuracy of document classification tasks.\n\nWe assume that the reviewer wonder why we can have performance improvement by an unsupervised feature selection approach without document labels over the document classification tasks. In our proposed method, we assume that the tree-Wasserstein distances that has larger value are more informative. FROT and SRW also assume this assumption. Note that, as an extreme case, if the tree-Wasserstein distance has exact same value for all documents, the classification accuracy is zero. Thus, selecting a feature maximizing the tree-Wasserstein distance is a reasonable approach for unsupervised tasks, and this assumption is well supported from the experiments.\n\n\n> 3. The baseline is lacking, especially for the dimensional reduction methods in optimal transport estimation. For example, SRW and FROT, as mentioned in this paper, should be included as baselines.\n\nFROT needs about $30$ times and SRW needs about $800$ times more than TWD-GFS as shown in Figure 6, so it is practically difficult to apply them to document classification tasks with large datasets. Thus, we could not include those results in the submission.\n\nAs a reference, we conducted new document classification experiments using FROT for BBCSPORT, TWITTER, RECIPE and show their results in the following table. We used concatenated word embeddings and considered five word embeddings as feature groups as well as TWD-GFS. The performance of FROT is slightly higher than our baseline, Concat and Concat with PCA, and comparable to TWD-GFS with Clustertree, which is our most important results. We emphasize that TWD-GFS can achieve the equivalent performance with FROT with much lower computation time than FROT. We will include these results in the final version.\n\n|   the error rate [%]              | BBCSPORT      | TWITTER        | RECIPE        |\n|-----------------------------------|---------------|----------------|----------------|\n| Concat (Clustertree)              | $3.8 \\pm 0.5$ | $29.7 \\pm 0.9$ | $42.2 \\pm 0.3$ |\n| Concat with PCA (Clustertree)     | $3.6 \\pm 0.8$ | $29.5 \\pm 1.1$ | $42.1 \\pm 0.3$ |\n| TWD-GFS (Clustertree, $\\eta=0.1$) | $3.5 \\pm 1.2$ | $29.1 \\pm 1.3$ | $41.8 \\pm 0.6$ |\n| FROT                              | $3.6 \\pm 0.7$ | $29.1 \\pm 0.5$ | $41.9 \\pm 1.0$ |\n\n> 1. In the synthetic experiments, how do we set up feature groups?\n\nIn our synthetic experiments, we crafted 22-dimensional synthetic data, denoted as $\\mathbf{x}=(x_0, x_1, ..., x_{21})$. Within this setup, $x_0$ and $x_1$ are the correct features, while $x_2, ..., x_{21}$ are the noise features.\n\nTo evaluate the efficacy of TWD-GFS in selecting the appropriate feature groups, we segmented the features into \"correct\" and \"noise\" groups. This enabled us to assess TWD-GFS's capacity to identify the correct feature groups effectively. The simplest case involved two groups, namely $(0, 1)$ for correct features and $(2, 3, ..., 21)$ for noise features. In our synthetic experiments, we introduced a slightly more complex scenario, encompassing multiple noise feature groups, defined as $(0, 1), (2, 3), ..., (20, 21)$.\n\n## References\n\n[1] Ming Yuan and Yi Lin. Model selection and estimation in regression with grouped variables. 2006. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 68(1):49–67\n\n[2] Wenpeng Yin and Hinrich Schütze. 2016. Learning word meta-embeddings. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics.\n\n[3] Sahar Ghannay, Benoit Favre, Yannick Estève, and Nathalie Camelin. 2016. Word embedding evaluation and combination. In Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC’16)\n\n[4] Danushka Bollegala, Kohei Hayashi, and Ken-ichi Kawarabayashi. 2018. Think globally, embed locally—locally linear meta-embedding of words. In IJCAI.\n\n[5] Danushka Bollegala and Cong Bao. 2018. Learning word meta-embeddings by autoencoding. In Proceedings of the 27th International Conference on Computational Linguistics.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. The goal of this paper is necessary when the TWD losses its approximation property gradually in high dimensional space. An entropy algorithm is proposed ", "reasons_to_reject": "1. The technical contribution is limited. The key idea of this feature selection is to identify a soft maximum of tree Wasserstein distances conditional on groups. It relies on a pre-defined group. So this restricts the application methods in such a specific case where multiple feature groups are available.\n2. There are still gaps between the performance of the targeting task and the feature selection problem. If this method is proposed for document distance style application, it is not clear why a better feature selection yields better performance of document distance.\n3. The baseline is lacking, especially for the dimensional reduction methods in optimal transport estimation. For example, SRW and FROT, as mentioned in this paper, should be included as baselines.", "questions_to_authors": "1. In the synthetic experiments, how do we set up feature groups?", "paper_topic_and_main_contributions": "This paper proposes to apply dimensional reduction techniques on the tree-Wasserstein metric in the application of document distance. The key technique is to softly select the best-performing feature group based on the observed training data.", "excitement": 3, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "oi6Y99V2YN", "reviewer": "Reviewer_2jWw", "summary": "", "questions": "Question A: Why different baselines are used in the effectiveness and efficiency testing? It is better to list the performance of FROT and SRW in Table 2.\n\nQuestion B: Explain why TWD-GFS with Clustertree performs worse than TWD-GFS with Quadtree?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable questions and comments.\n\n> Question A: Why different baselines are used in the effectiveness and efficiency testing? It is better to list the performance of FROT and SRW in Table 2.\n\nFROT needs about $30$ times and SRW needs about $800$ times more than TWD-GFS as shown in Figure 6, so it is practically difficult to apply them to document classification tasks with large datasets. Thus, we could not include those results in the submission.\n\nAs a reference, we conducted new document classification experiments using FROT for BBCSPORT, TWITTER, RECIPE and show their results in the following table. We used concatenated word embeddings and considered five word embeddings as feature groups as well as TWD-GFS. The performance of FROT is slightly higher than our baseline, Concat and Concat with PCA, and comparable to TWD-GFS with Clustertree, which is our most important results. We emphasize that TWD-GFS can achieve the equivalent performance with FROT with much lower computation time than FROT. We will include these results in the final version.\n\n|   the error rate [%]              | BBCSPORT      | TWITTER        | RECIPE        |\n|-----------------------------------|---------------|----------------|----------------|\n| Concat (Clustertree)              | $3.8 \\pm 0.5$ | $29.7 \\pm 0.9$ | $42.2 \\pm 0.3$ |\n| Concat with PCA (Clustertree)     | $3.6 \\pm 0.8$ | $29.5 \\pm 1.1$ | $42.1 \\pm 0.3$ |\n| TWD-GFS (Clustertree, $\\eta=0.1$) | $3.5 \\pm 1.2$ | $29.1 \\pm 1.3$ | $41.8 \\pm 0.6$ |\n| FROT                              | $3.6 \\pm 0.7$ | $29.1 \\pm 0.5$ | $41.9 \\pm 1.0$ |\n\n> Question B: Explain why TWD-GFS with Clustertree performs worse than TWD-GFS with Quadtree?\n\nThese results are influenced by TWD's inherent performance characteristics, rather than our method itself. Prior studies on TWD [1, 2, 3, 4] illustrate that Quadtree or Clustertree's effectiveness varies based on dataset and task dynamics. This TWD trait significantly shapes our experiments. For instance, Quadtree is more effective than Clustertree in TWITTER and CLASSIC datasets with TWD-GFS as well as other baselines. Consequently, TWD-GFS's performance with Clustertree lags behind that with Quadtree, despite optimal feature group selection. It is important to achieve higher performance than the baseline using the same tree-construction method.\n\nThese answers can also address the concern you mentioned in the \"Reasons To Reject\" section.\n\n## References\n\n[1] Tam Le, Makoto Yamada, Kenji Fukumizu, and Marco Cuturi. 2019. Tree-sliced variants of wasserstein distances. In NeurIPS.\n\n[2] Yuki Takezawa, Ryoma Sato, and Makoto Yamada. 2021. Supervised tree-wasserstein distance. In ICML.\n\n[3] Makoto Yamada, Yuki Takezawa, Ryoma Sato, Han Bao, Zornitsa Kozareva, and Sujith Ravi. 2022. Approximating 1-wasserstein distance with trees. Transactions on Machine Learning Research.\n\n[4] Samantha Chen, Puoya Tabaghi, and Yusu Wang. 2022. Learning ultrametric trees for optimal transport regression. arXiv preprint arXiv:2210.12288.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The TWD-based method solves the discriminative feature group selection problem during a tree approximation of Wasserstein distance, and the proposed method has been proved be effective and efficient.", "reasons_to_reject": "The experimental result is not very convincing. \n\n1)\tDifferent baselines are used in the effectiveness and efficiency testing. For the effectiveness testing, Concat and Concat (PCA) are used. For the efficiency testing, FROT, SRW, and Sinkhorn are chosen. \n\n2)\tAs shown in Table 2, although TWD-GFS with Clustertree significantly outperform Concat and Concat(PCA), the overall performance of TWD-GFS with Clustertree is worse than TWD-GFS with Quadtree. This indicates TWD-GFS is applied effectively only to some tree approximation methods.", "questions_to_authors": "Question A: Why different baselines are used in the effectiveness and efficiency testing? It is better to list the performance of FROT and SRW in Table 2.\n\nQuestion B: Explain why TWD-GFS with Clustertree performs worse than TWD-GFS with Quadtree?", "paper_topic_and_main_contributions": "This paper presents a TWD-based method which automatically selects useful word embeddins during a tree approximation of Wasserstein distance.", "excitement": 4, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Wasserstein distance is an attractive method for comparing probability distributions because it can easily be applied in NLP for tasks involving comparing documents (eg, classification). Its computational cost remains a bottleneck and various methods have been proposed to accelerate it. This paper proposes an improvement over one of those methods (tree Wasserstein distance), which is beneficial when applied to high-dimensional problems (as is normally the case in NLP).

Reviewers pointed out the originality of the approach as well as the empirical results (gains are substantial) as strengths. There were lingering questions around some experimental decisions, in particular regarding the use of different baselines for different datasets and the relative performance of some proposed combinations. The authors addressed those questions - their presence highlighted by various reviewers seem to indicate that those are point that should be clarified in the manuscript.
Decision: Accept-Main