1What the method is for

Asking whether two things are similar, without deciding what counts as a feature.

Ordinarily, measuring the similarity of two objects begins with extracting features. They are turned into a sequence of numbers — word frequencies, coordinates, the presence or absence of categories — and a Euclidean or cosine distance is computed on that. The judgement of which features to choose enters at the very first step, and whatever was not chosen is lost there.

Normalized compression distance (NCD) does not take that step. Two files are handed to a compressor as they are, and only the compressed sizes are examined. Concatenate two similar files and compress, and the shared parts are detected as repetition, so the result shrinks. If they are not similar, it does not. NCD puts a number on that difference.

Onohara (2010) adopted the method because the objects to be compared were XML documents with nested structure. Following a model designed to conform to geographic information standards, the dialect information for each survey point was rendered as XML, holding latitude and longitude, the general name of a lexical item and its pronunciation in a hierarchy. Data with such complex structure, in the paper’s words, “are handled less often, because the methods of analysis available to them are limited”. NCD offers a route to a distance matrix without flattening that structure into a numerical table.

The advantage the paper cites

“One advantage of this analytical method”, the paper states, “is that, compared with general analytical methods, prior data extraction and shaping can be simplified”. Not designing features means not discarding information, and at the same time makes it harder to see what is being measured. That two-sidedness is taken up in section 6.

2Origin — replacing an uncomputable quantity with a compressor

The starting point is Kolmogorov complexity. Which cannot be computed.

Kolmogorov (1965) defined the information content of an individual object without passing through a probability distribution. The complexity \(K(x)\) of a string \(x\) is the length of the shortest program that outputs \(x\). A regular string can be written by a short program, so \(K\) is small; a random string leaves nothing but writing itself out, so \(K\) is large.

From here a separation between two objects can be defined, using the additional description length needed to produce \(y\) given \(x\). Li et al. (2004) normalized this into the normalized information distance and showed it to be optimal in a certain sense.

The difficulty is that \(K\) is uncomputable. No general procedure exists for finding the shortest program for a given string. Cilibrasi and Vitányi (2005) therefore replaced \(K(x)\) with \(C(x)\), the compressed size under a real compressor. What results is NCD: a quantity that can actually be computed, at the cost of the theoretical optimality.

This substitution determines everything about the method

A compressor is not a device that finds shortest programs. GZIP merely replaces repetitions occurring within a fixed preceding range using a dictionary, and does nothing beyond that. What NCD captures as “similar” is therefore limited to the kinds of regularity that compressor can capture. The quality of the approximation is the performance of the compressor itself, and the validity of the method rests entirely here.

The paper does not cite this lineage

Neither Kolmogorov nor Cilibrasi and Vitányi appears in the references of Onohara (2010); NCD is introduced together with its defining equation as “one of the general-purpose similarity computation techniques”. The lineage set out above has been supplied on this page in order to explain where the method stands.

3Where it falls within Perspective 5, information theory

The same word “information”, but a different object being measured.

Perspective 5 of the seven perspectives in equations gathers the position that treats a short encoding as a good explanation. The quantities set out there — entropy \(H(p)=-\sum_x p(x)\log p(x)\), Kullback–Leibler divergence, AIC — are all defined over a probability distribution. They concern an expected code length, with the premise that there is a distribution generating the data.

NCD belongs to the same information theory but on the side of algorithmic information theory. \(K(x)\) is defined not over a distribution but over a single individual object. No probability model is set up, so the question of whether the model is right never arises. In its place arises the question of whether the compressor is good enough.

Two information quantities, measuring different objects
\[ H(p) \;=\; -\sum_{x} p(x)\log p(x) \qquad \text{versus} \qquad K(x) \;=\; \min\{\,|P| \;:\; U(P)=x\,\} \]

\(H(p)\) … the average unpredictability of distribution \(p\). No value attaches to an individual \(x\)
\(K(x)\) … the description length of the object \(x\) itself. \(U\) is a universal machine, \(|P|\) a program length
What they share … both treat being writable briefly as being good

Under the same roof as AIC, but standing in a different place

The AIC of Perspective 5 measures fit by log-likelihood and penalizes by the number of parameters. It counts the complexity of a model. NCD concerns the description length of the object itself and holds no model. Both share the principle that a shorter description is better, while one stands in the world of distributions and models and the other in the world of individual objects. Placing this method under Perspective 5 is not in the former sense but because it shares the principle of measuring goodness by code length.

4The definition, and why it is normalized

How much is gained by compressing the two together.

Normalized compression distance
\[ \mathrm{NCD}(x,y) \;=\; \frac{C_{XY} - \min\{C_X,\, C_Y\}}{\max\{C_X,\, C_Y\}} \]

\(C\) … the compression algorithm
\(C_X,\, C_Y\) … the file sizes of \(x\) and \(y\) compressed separately
\(C_{XY}\) … the file size of \(y\) concatenated to \(x\) and compressed

The form of the equation is as given in the paper. It reads as follows.

The numerator is the extra needed for one, given the other

Supposing \(C_X \le C_Y\), the numerator is \(C_{XY} - C_X\). This is the amount additionally required to write \(y\) once \(x\) has already been written. If \(x\) and \(y\) are similar, much of \(y\) can be referred back to as repetition of \(x\) and the extra is small. If they are not similar at all, \(y\) has to be written out almost entirely and the extra approaches \(C_Y\).

The denominator cancels the difference in length

Used as it stands, the extra would make longer files come out at greater distance: long documents, even similar ones, carry a large absolute extra. Dividing by the larger compressed size turns it into the ratio “what fraction of writing it out whole is the extra?” The value then falls roughly within \([0,1]\), and objects of differing length can be compared on the same scale.

Nearer 0 is more similar, nearer 1 less similar. For two identical objects, concatenation barely increases the compressed size, so the numerator is close to 0.

That this is an approximation is built into the definition

Replacing \(C\) in this equation with \(K\) gives the theoretical normalized information distance. Since \(K\) cannot be computed, a real compressor is substituted. NCD is therefore always an approximation, and its value changes if the compressor changes. The paper too states plainly that “NCD depends on the compression algorithm”, noting that the version of the software used supports GZIP compression only.

5How it is used in this research

Turn dialect distribution maps into XML, and extract regions from the NCD between localities.

The object is the dialect vocabulary of Gifu Prefecture as a whole. From ten distribution maps in A Study of the Dialects of Gifu Prefecture (Okumura, 1976), the pronunciations of ten lexical items — chilli pepper, maize, ring finger, hair whorl, stilts, beanbag, non-glutinous rice, potato, silk floss and taro — were read off for 125 survey points.

  1. Extracting attributes From each distribution map, three things are taken per survey point: latitude and longitude, the general name of the lexical item, and its pronunciation in dialect. At survey point 1, for instance, chilli pepper is nanban, maize is tōna, ring finger is benisashiyubi, and silk floss and taro have no data.
  2. Designing the metamodel A “meta-metamodel”, defining a cultural phenomenon as a sequence of human actions in space and time, is placed as the superordinate concept, and a metamodel of dialect is designed beneath it. It is made to conform to the application schema (ISO 19109) of the geographic information standards, structured so that a “Dialects” class consists of a “Message” class holding relations to a “Speaker” class and a “Vocabulary” class.
  3. Instantiating as XML Following the encoding rules (ISO 19118) of the geographic information standards, one XML document is produced per survey point. The 125 documents become the objects of comparison.
  4. Computing NCD Using the NCD software “Hyakka Ichishiki Ver1.0” developed by Fujimoto, NCD is computed for every pair among the 125 documents to obtain a distance matrix. That version of the software supports GZIP compression only.
  5. Excluding points with many missing values Because the missing values written as “NULL” inside the XML affect the result as similarity, 15 points with many missing values (35, 62, 93, 96, 104, 114, 115, 116, 119, 120, 121, 122, 123, 124, 125) are removed from the analysis in advance, leaving 110.
  6. Clustering The resulting distance matrix is submitted to non-hierarchical PAM, hierarchical Ward and average linkage, the phylogenetic neighbor-joining and Neighbor-Net, and the graph clustering method DPClus, and the results compared.
  7. Validation A separate dataset is built from the same survey and checked against earlier research.

The classification obtained

With PAM, five clusters were taken, and four classes — excluding one cluster of outliers — judged appropriate. Among methods of classification from the NCD matrix, however, Neighbor-Net, based on the neighbor-joining algorithm, reproduced the findings of earlier research most faithfully. Specifically, the isolation of the Tonyū district of Tokuyama Village (survey point 28) and the east–west accent contrast between Ōgaki City (point 63) and Tarui Town (point 51) both appear in the figure. Both have long been known in dialectology.

Validation used different data and a different distance

To confirm that NCD properly reflects similarity of pronunciation, two further matrices were built from the same survey. One takes survey items as columns and survey points as rows, with each pronunciation replaced by a single-character symbol. The other takes all pronunciations of the survey items as columns and survey points as rows, coding 1 where the item exists and 0 where it does not. Gower distance was used, and the Jaccard coefficient for the binary data; the same clustering methods as for NCD were tried.

DataDistanceClassification reproducing earlier research best
XML documentsNCD (GZIP)Neighbor-Net
Pronunciations coded as symbolsGower— (the row below was best)
Presence–absence of items (binary)JaccardDPClus (distance < 0.85, density = 0.95, minimum cluster size = 4)

All analyses on 110 points. Comparing the two sets of results, the paper states that “there is no difference in the core constituent points of each group, and the effectiveness of the analysis by NCD was demonstrated”. It adds that although the data used concern similarity of lexical distribution, it is also worth noting that there is no discrepancy with the findings of earlier research based on accent distribution.

The regions obtained as a conclusion

The survey points can be classified into seven or eight clusters, of which three to four have no geographical coherence. Seen from a spatial point of view, the conclusion drawn is that Gifu Prefecture divides broadly into four groups. The paper notes that one of the boundaries among these four groups lies around the city of Gifu, and that the same tendency is pointed out in Fujimoto’s (2010) analysis using Jōmon pottery.

6Limits

What governs the value is not the objects alone.

Change the compressor and the distance changes

NCD being an approximation of \(K\), which compressor is used bears directly on the result. Only GZIP was used in this study. GZIP replaces repetitions occurring within a fixed preceding width (the window) using a dictionary, so repetitions lying beyond the window cannot be captured. As the concatenated file grows longer, a region arises in which the correspondence between the first and second halves becomes invisible.

Cebrián et al. (2005) show that compressors are not idempotent — that placing two copies of the same content side by side can yield nearly twice the compressed size of one — and report that NCD is distorted by the size of the objects relative to the window size, with the consequence that the identity \(\mathrm{NCD}(x,x)=0\) breaks down. The paper itself mentions the dependence on the compression algorithm, but does not examine the effect of window size.

XML documents from the same schema are similar to begin with

All 125 XML documents being compared were generated from the same metamodel. Their tag structure is therefore identical throughout. Strings such as <dataset>, <communication>, <message> and <pronunciation> line up in the same way even between points whose pronunciations are entirely different. Concatenate and compress, and this shared portion shrinks together.

The values of the distance matrix may consequently be biased as a whole toward similarity, compressing the differences between points. The greater the redundancy of the tags, the smaller the relative contribution of the pronunciation information that is actually of interest. The paper does not address this point. It is raised here because it is a property common to any NCD analysis taking XML as input.

Passed to phylogenetic estimation without strictly satisfying the metric axioms

As noted above, NCD with a real compressor does not strictly satisfy identity, and the triangle inequality is not guaranteed either. Yet in this study the resulting matrix is passed to PAM, Ward, average linkage, neighbor-joining, Neighbor-Net and DPClus. Neighbor-joining and Neighbor-Net in particular build their branches on the premise that the distance is additive, that is, expressible as a sum of branch lengths.

NCD values are not constructed to satisfy that premise. That earlier findings were nevertheless reproduced is empirical evidence of the method’s robustness, but it is not a theoretical justification. The branch lengths of the resulting network cannot be read as divergence dates in a phylogeny.

The criterion for exclusion is not given

Fifteen points were excluded as having “many missing values”, but the paper does not state how many counts as many. The reason for exclusion itself — that the string “NULL” inside the XML is shared, making documents similar irrespective of content — is sound, and is another manifestation of the same tag-redundancy problem described above.

Exclusion, however, reduces the material under analysis, and those points become blanks on the map. The paper marks excluded points on its figures with small brown circles and points not assigned to any cluster in grey, noting that “this does not indicate that the grey survey points form a single cluster among themselves”. That a caution about how to read the figure is made explicit is appropriate practice.

The number of clusters varies with how far earlier research is to be reproduced

Grasping the outline by multidimensional scaling showed that dividing all survey points into four groups was appropriate. At the same time, the paper states, it also became clear that in order to see the regional differences established through earlier research, seven or eight clusters are needed under any of the cluster analyses.

The number of clusters, in other words, was not fixed by the data alone but chosen according to what was to be seen. The final conclusion that “Gifu Prefecture divides broadly into four” was reached by way of the observation that three or four of the seven or eight clusters lack geographical coherence, and that route is set out in the paper. Agreement with earlier research is corroborating evidence of validity, and at the same time involves the circularity of having chosen the number of clusters so as to see the structure earlier research indicates.

The reservation the paper itself states

In its conclusion, on the estimation of the direction of lexical change and the analysis of relations with areas outside Gifu Prefecture using “archetype” data, the paper states that “it became clear that more careful data construction and scrutiny of the data of earlier research are required in order to interpret the strict parts”. Having judged the extraction of regions by NCD itself to be effective, it asks for caution in the interpretation that follows from it.

7Sources and data

This page is based on presentation material dated November 2010. The affiliation at the time of writing was the Graduate School of Culture and Information Science, Doshisha University (master’s programme), and the research forms part of the results of the CITMAS project (principal investigator: Yū Fujimoto).

References on the method

The four entries below have been supplied on this page to explain the theoretical placement of NCD; they are not in the paper’s reference list. Only Huson and Bryant is cited by the paper.

  • Kolmogorov, A. N. (1965) Three approaches to the quantitative definition of information. Problems of Information Transmission, 1(1).
  • Li, M., Chen, X., Li, X., Ma, B. & Vitányi, P. M. B. (2004) The similarity metric. IEEE Transactions on Information Theory, 50(12), 3250–3264.
  • Cilibrasi, R. & Vitányi, P. M. B. (2005) Clustering by compression. IEEE Transactions on Information Theory, 51(4), 1523–1545. doi:10.1109/TIT.2005.844059
  • Cebrián, M., Alfonseca, M. & Ortega, A. (2005) Common pitfalls using the normalized compression distance: What to watch out for in a compressor. Communications in Information and Systems, 5(4), 367–384.
  • Huson, D. H. & Bryant, D. (2006) Application of phylogenetic networks in evolutionary studies. Molecular Biology and Evolution, 23(2), 254–267.

Earlier research checked against (as cited by the paper)

  • 服部四郎 (1930)「近畿アクセントと東方アクセントとの境界線」『音聲の研究』第三輯, 文學社, pp.131–144.
  • 柴田武 (1950)「揖斐川上流のアクセント」『文字と言葉』刀江書院.
  • 山田達也 (1978)「揖斐川上流域における基礎語彙について」『名古屋市立大学教養部紀要 人文社会研究』22, pp.33–66.
  • 徳山村の歴史を語る会 (1984)『徳山村のあけぼのを求めて ―岐阜県揖斐郡徳山村遺跡分布調査中間報告―』
  • 藤本悠 (2010)『文化情報学および理念型モデル化分析法に関する基礎的研究 ―文化情報学における諸概念と方法について―』同志社大学大学院文化情報学研究科 博士論文.

Which perspective this method belongs to

NCD stands on the principle of measuring the goodness or the nearness of an object by code length. If it can be written briefly, there is regularity in it. It shares that principle with the entropy and AIC treated under Perspective 5 (information theory) in the seven perspectives in equations, differing in that those are defined over a probability distribution while NCD is defined over the individual object itself. Because no probability model is set up, the question of a model’s fit gives way to the question of the compressor’s performance.
In this study the resulting distance matrix is passed to Neighbor-Net (Perspective 1) to draw the genealogical structure — an instance of methods connecting across perspectives.

This page sets out, for readers in the same field, a method Onohara uses in her own research. All figures and results are quoted from what is recorded in the presentation material; no estimates or approximations have been added. Bibliographic details have been confirmed independently of the paper’s own reference list.
The overall placement of methods is in the seven perspectives in equations, and which course sessions fall under which perspective is in Methods & Mathematics.