License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-6296
URL: http://drops.dagstuhl.de/opus/volltexte/2006/629/
Go to the corresponding Portal


Cilibrasi, Rudi ; Vitanyi, Paul M.B.

Automatic Meaning Discovery Using Google

pdf-format:
Document 1.pdf (246 KB)


Abstract

We survey a new area of parameter-free similarity distance measures useful in data-mining, pattern recognition, learning and automatic semantics extraction. Given a family of distances on a set of objects, a distance is universal up to a certain precision for that family if it minorizes every distance in the family between every two objects in the set, up to the stated precision (we do not require the universal distance to be an element of the family). We consider similarity distances for two types of objects: literal objects that as such contain all of their meaning, like genomes or books, and names for objects. The latter may have literal embodyments like the first type, but may also be abstract like ``red'' or ``christianity.'' For the first type we consider a family of computable distance measures corresponding to parameters expressing similarity according to particular features between pairs of literal objects. For the second type we consider similarity distances generated by web users corresponding to particular semantic relations between the (names for) the designated objects. For both families we give universal similarity distance measures, incorporating all particular distance measures in the family. In the first case the universal distance is based on compression and in the second case it is based on Google page counts related to search terms. In both cases experiments on a massive scale give evidence of the viability of the approaches.

BibTeX - Entry

@InProceedings{cilibrasi_et_al:DSP:2006:629,
  author =	{Rudi Cilibrasi and Paul M.B. Vitanyi},
  title =	{Automatic Meaning Discovery Using Google},
  booktitle =	{Kolmogorov Complexity and Applications},
  year =	{2006},
  editor =	{Marcus Hutter  and Wolfgang Merkle and Paul M.B. Vitanyi},
  number =	{06051},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2006/629},
  annote =	{Keywords: Normalized Compression Distance, Clustering, Clasification, Relative Semantics of Terms, Google, World-Wide-Web, Kolmogorov complexity}
}

Keywords: Normalized Compression Distance, Clustering, Clasification, Relative Semantics of Terms, Google, World-Wide-Web, Kolmogorov complexity
Seminar: 06051 - Kolmogorov Complexity and Applications
Issue Date: 2006
Date of publication: 31.07.2006


DROPS-Home | Fulltext Search | Imprint Published by LZI