Computing document similarity in large corpus

Standard

Since early this year, I was asked by many people how to compute document (or feature) similarity in large corpus. They said their functions stops because the lack of space in RAM:

Error in .local(x, y, ...) : 
  Cholmod error 'problem too large' at file ../Core/cholmod_sparse.c, line 92 

This happened in our textstat_simil(margn = "documents") too because matrix multiplication in the function produces dense matrix with (ndoc(x) ^ 2) / 2 elements: the number of cells in the matrix is 5,000,000,000 if your corpus has 100,000 documents!

A solution to this problem is not recording values that is less than a certain threshold. You might be only interested in documents with cosine similarity larger than 0.9 when you study document reuse, for example. We upgraded our functions for document similarity computation, which is used in textstat_simil() and textstat_dist(), to achieve this in the latest Github version of quanteda. We also parallelized the computation in C++ to make it faster.

The new function is called textstat_proxy(). It is still experimental but has two new arguments, min_proxy and rank, to reduced the number of values to save storage. If you set the min_proxy, the function records only values larger than that; if you use rank, it records only top-n largest values for each document (or features).

Benchmarking on my Core i7 laptop showed that the new function is twice as fast as the old one. If either min_proxy or rank is used, it becomes 4 times faster.

library(quanteda)
mt <- readRDS("data_corpus_guardian_2016-2017.RDS") %>% 
      dfm(remove_punct = TRUE, remove = stopwords()) %>% 
      dfm_trim(min_termfreq = 10)
dim(mt)
# [1] 84599 83573 # 84599 documents

# subset the corpus because the it is too large for the old function
mt_sub <- dfm_sample(mt, 10000) 
dim(mt_sub)
# [1] 10000 83573 # 10000 documents

quanteda_options(threads = 8)
microbenchmark::microbenchmark(
    old = textstat_simil_old(mt_sub, method = "cosine"),  
    new = textstat_simil(mt_sub, method = "cosine"),  
    new_min = textstat_proxy(mt_sub, method = "cosine", min_proxy = 0.9),
    new_rank = textstat_proxy(mt_sub, method = "cosine", rank = 10),
    times = 10
)
# Unit: seconds
#      expr       min        lq      mean    median        uq       max neval
#       old 22.426574 22.641949 22.788590 22.745563 22.960467 23.160844    10
#       new 13.376352 13.417328 13.641411 13.638641 13.699010 14.226246    10
#   new_min  4.977046  5.010795  5.119516  5.114965  5.201249  5.314574    10
#  new_rank  5.303440  5.322976  5.411015  5.385124  5.482439  5.583506    10

More importantly, we can compute the document similarity between all the 84599 documents in the corpus without problems, if min_proxy is used. It took only 15 minutes on my laptop and the resulting object is as small as 12MB.

new_min <- textstat_proxy(mt, method = "cosine", min_proxy = 0.9)
print(object.size(new_min), units = "Mb")
# 12.4 Mb

If you want to know which documents are similar to which, you can make a simple conversion function and run.

matrix2list <- function(x) {
  names(x@x) <- rownames(x)[x@i + 1]
  split(x@x, factor(x@j + 1, levels = seq(ncol(x)), labels = colnames(x)))
}
simil <- matrix2list(new_min)
head(simil[lengths(simil) > 1])
# $text119559
# text119554 text119559 
#  0.9929825  1.0000000 
# 
# $text119561
# text119553 text119561 
#   0.994557   1.000000 
# 
# $text119562
# text119557 text119562 
#  0.9975438  1.0000000 
# 
# $text119564
# text119553 text119561 text119564 
#  0.9854428  0.9908825  1.0000000 
# 
# $text119568
# text119555 text119568 
#  0.9963637  1.0000000 
# 
# $text119570
# text119551 text119570 
#  0.9586148  1.0000000

textstat_proxy() has a great potential but it is still experimental, because we are not sure what the best format of the resulting objects. If you have any opinion, please post a comment on the GitHub page.

日本語の量的テキスト分析

Standard

より多くの日本人の研究者に量的テキスト分析について関心を持ってもらうために、『日本語の量的分析』という論文をニューヨーク大学のエイミー・カタリナックと一緒に書きました。これまでのところ、Twitterで多くの方からポジティブな反応を頂いています。

本稿は、欧米の政治学者の間で近年人気を集めている量的テキスト分析(quantitative text analysis)と呼ばれる手法の日本語における利用について論ずる。まず、量的テキスト分析が登場した背景を述べたうえで、欧米の政治学においてどのように利用されているかを説明する。次に、読者が量的テキスト分析を研究で利用できるように、日本語の分析において注意すべき点に言及しながら、作業の流れを具体的に説明する。最後に、欧米で利用されている統計分析モデルを紹介した上で、それらが日本語の文書の分析にも利用できることを研究事例を用いて示す。本稿は、近年の技術的および方法論な発展によって、日本語の量的テキスト分析が十分に可能になったことを主張するが、この手法が日本の政治学において広く普及するためには、データの整備など制度的な問題に対処していく必要性があることにも触れる。