Dimensionality reduction with least distance distortion

Question: Could I find a dimensionality reduction algorithm without or with minimal distance (cosine) distortion?

Background: I would like to visualize in 2D a sample of news texts for which I also apply clustering.

I present the texts as vectors (like text2vec), but it is desirable to also project the vectors to 2 dimensions. Moreover I consider apply clustering on the 2 dimensions for speedy execution.

My initial guess is using t-SNE with careful tuning of epsilon.

Are there more robust algorithms which do not distort much the distance (cosine) in multidimensional space, thus making clear pictures?

Update.

After several tries I got the following mapping (and clustering based on that):

This is a daily snapshot of Russian news by three major news agencies.

People liked the look, but what I worry about is that in the middle is a huge all-in-one cluster where all kinds of topics have been mixed. However, I know that there are many smaller topics every day that consist of maybe 3-5 news, but the meaning of them is quite specific.

I played quite some time with the parameters of t-SNE:

## rt-sne reduction

mat_dat <- data.matrix(text_centroids[, !c('message_id'), with = F])

rtsne_obj <- Rtsne(X = mat_dat
, dims = 2
, initial_dims = 100
, perplexity = 30
, theta = 0.3
, check_duplicates = FALSE
, pca = TRUE
, partial_pca = FALSE
, max_iter = 1000
, verbose = T
, is_distance = FALSE
, Y_init = NULL
, pca_center = TRUE
, pca_scale = TRUE
, normalize = TRUE
, momentum = 0.5
, final_momentum = 0.8
, eta = 200
, exaggeration_factor = 12

text_centroids[, Dim1 := rtsne_obj$$Y[,1]] text_centroids[, Dim2 := rtsne_obj$$Y[,2]]

ggplot(data = text_centroids) +
geom_point(aes(x = Dim1, y = Dim2), color = 'blue', alpha = 0.1, size = 4) +
theme_minimal()

## cluster with dbscan

clustering_dat <- rtsne_obj$Y[, 1:2] dbscan_knn <- frNN(x = clustering_dat, eps = 2, sort = TRUE, search = "kdtree", bucketSize = 10, splitRule = "suggest", approx = 0) dbscan_obj <- dbscan(x = dbscan_knn , weights = NULL , borderPoints = F ) table(dbscan_obj$cluster)


but could not get any better.

Update 2.

Measuring Pearson's correlation coefficient between the vector of Euclidean distances between full-dimensional points (right triangle of the dist matrix) and t-SNE dimensinal points yielded:

> cor.test(original_text_dist, tsne_dist)

Pearson's product-moment correlation

data:  original_text_dist and tsne_dist
t = 1095.5, df = 2388200, p-value < 2.2e-16
alternative hypothesis: true correlation is not equal to 0
95 percent confidence interval:
0.5774797 0.5791678
sample estimates:
cor
0.5783244


Hm, it looks that the distances were distorted although the distrortion was not so catastrophic.

I think I could try multidimensional scaling next.

Hmm, it looks like cmdscale in R stats:: does significantly better job at preserving the distances:

> mds <- cmdscale(original_text_dist)
> mds_dist <- dist(mds, diag = F, method = "euclidean", upper = F)
> original_text_dist <- as.vector(original_text_dist)
> mds_dist <- as.vector(mds_dist)
> cor.test(original_text_dist, mds_dist)

Pearson's product-moment correlation

data:  original_text_dist and mds_dist
t = 1834, df = 2388200, p-value < 2.2e-16
alternative hypothesis: true correlation is not equal to 0
95 percent confidence interval:
0.7641945 0.7652476
sample estimates:
cor
0.7647216


• Did you mean dimensionality reduction algorithm? I don't understand how convolution is involved. – user20160 Nov 24 '18 at 12:14
• Yes, I did. I meant convolving many features to just 2. – Alexey Burnakov Nov 24 '18 at 12:56
• Not sure I completely understand your goal, as dimensionality reduction algorithms like t-SNE typically don't involve convolutions. Were you particularly interested in something that uses the convolution operation? – user20160 Nov 25 '18 at 0:16
• (Disclamer: I didn't read the full question.) Cosine similarity is directly related to euclidean distance for normalized vectors called then chord distance. So, if you are using cosine or chord distance, you may use an iterative MDS, even its metric version. MDS is expected to "distort" your distances less than any dimensionality reduction methods. – ttnphns Nov 27 '18 at 11:47
• I won't, sorry. I'll give you a pair of local links at a wild guess, for the start. stats.stackexchange.com/a/36158/3277; stats.stackexchange.com/a/14017/3277; stats.stackexchange.com/a/31291/3277; stats.stackexchange.com/a/208238/3277 – ttnphns Nov 27 '18 at 11:56

The one possible approach could be a relatively new trimap method, based on triplets (in contrast with usual pair-wise distances). It's explicitly optimize to keep the original form (in contrast to t-sne), while making better clusters then PCA. https://github.com/eamid/trimap

First of all, my criterion of choosing any method for dimensionality reduction is visual inspection of a 2D mapping with a layer of clusters and their description. Judging by that, I like t-SNE more given it has mapped some of my texts into clear clusters (topics).

MDS and PCA that I also tried did not give a clustering look to the mapping.

Another option that I explored is a neural network designed specifically (by myself) for this task. Take a look and comment if you think it is worth it.

First, I create input vector which is a concatenation of two objects in the k-dimensonal space.

Then I build a multilayer dense network with bottleneck. The k-dimesnional input vector is being convolved to just 2 scalars.

Notice that the layers that convolve k dimensions to 2 dimensions are shared between both input vectors.

After that I include a stack of dence layers that should approximate euclidean distance (calculated between k-dimensional objects) using just 2-dimensional objects stemming from the bottleneck part.

As a result the NN leans to approximate the euclidean distance from first calculating an input of 2 + 2 scalars denoting the preojection on a 2D plane.

## build keras model for dimension reduction -------------------------

input1 <- layer_input(shape = c(dim(dat_train)[2] / 2), name = 'input1')

input2 <- layer_input(shape = c(dim(dat_train)[2] / 2), name = 'input2')

shared_layer2 <- layer_dense(units = 128, activation = "relu")
shared_layer3 <- layer_dense(units = 32, activation = "relu")
shared_layer4 <- layer_dense(units = 2, name = 'shared_layer4')

text_1_model <- input1 %>%
shared_layer2 %>%
shared_layer3 %>%
shared_layer4

text_2_model <- input2 %>%
shared_layer2 %>%
shared_layer3 %>%
shared_layer4

main_output <- layer_concatenate(c(text_1_model, text_2_model)) %>%
layer_dense(units = 32, activation = "relu") %>%
layer_dense(units = 16, activation = "relu") %>%
layer_dense(units = 1)

convolving_model <- keras_model(
inputs = c(input1, input2),
outputs = main_output
)

summary(convolving_model)

convolving_model %>% compile(
loss = "mse",
metrics = list("mean_squared_error")
)

epochs <- 500
batch_size <- dim(train.x.1)[1]

# Fit the model and store training stats

history <- convolving_model %>% fit(
x = list(train.x.1, train.x.2)
, y = train.y
, batch_size = batch_size
, epochs = epochs
, validation_split = 0.3
)

plot(history)


After the NN has converged, I take the output of a hidden layer that is the 2D plane projections of the two input vectors. Use them as your dimensionality reduction matrix of coordinates.

## get hidden representations

layer_name <- 'shared_layer4'

intermediate_layer_model1 <- keras_model(
inputs = convolving_model$input , outputs = get_output_at(shared_layer4, 1) ) intermediate_layer_model2 <- keras_model( inputs = convolving_model$input
, outputs = get_output_at(shared_layer4, 2)
)

intermediate_output1 <- as.data.table(predict(intermediate_layer_model1, list(train.x.1, train.x.2)))

intermediate_output2 <- as.data.table(predict(intermediate_layer_model2, list(train.x.1, train.x.2)))

calc_coords <- cbind(intermediate_output1, intermediate_output2)


Surprisingly, the correlation of the euclidean distances between the calculated 2D coordinates and the original k-dimensional distances is a whopping 0.85 (if the NN converged well).

colnames(calc_coords) <- c(
'x1'
, 'y1'
, 'x2'
, 'y2'
)

calc_coords[, calc_euclid := sqrt((x1 - x2)^2 + (y1 - y2)^2)]

cor.test(train.y, calc_coords[, calc_euclid])