Complex Systems Summer School Project

Evolving Ontologies from Folksonomies: Tagging as a Complex System


Abstract

How and when can a coherent classification system might emerge from categorization via distributed "tagging"? Users find it various easy to simply add "tags" (natural language terms) to resources on the Web and then use a search of these tags to access this information at a later date. This method of information organization is often viewed in conflict with traditional methods of information organization, such as the ontology-drive approach being put forward by the Semantic Web where each resource is given a classification from a taxonomic hierarchy. As the number of users tagging increases, we believe the number and kinds of tags either will converge or form some sort of (possibly chaotic) periodic relationship in order to form an emergent structure.

Introduction

The phenomena of tagging has exploded in the last few years, with thousands of Web users using "tags" (natural language terms) to organize web resources. Ranging from tagging bookmarks at deli.cio.us to tagging photographs Flickr, there are now large amounts of tagged data on the Web for people to use. For example, URIs for a web-page about with an interactive piano is tagged with "art," "music," and of course a "piano" tag on del.icio.us - and has been given over 22 different tags by 79 people.

Is there hidden structure to tagging? A number of researchers have observed, some casually, some more rigorously, that the distribution of tags applied to particular URIs in online social tagging systems such as del.icio.us and Flickr follow a power law distribution [Mahes2004]. These online tagging systems have a variety of features that are often associated with complex social systems: a large number of users, social feedback about the tags used, the possibility for interaction between users, a lack of central coordination, and non-linear patterns. Additionally important is the issue of the role of language usage in tagging systems. Cattuto, Loreto & Pietronero note that "the emergence of a folksonomy exhibits dynamical aspects also observed in human languages, such as the crystallization of naming conventions, competition between terms, takeovers by neologisms, and more" [Cattuto2006]. The central question involved is when and how a coherent classification system might emerge from distributed tagging?

This process is of interest to the computer science community since there is a lack of consensus about whether tagging or taxonomies more efficiently organize information. Another open question, of particular interest to the Semantic Web community, is whether or not coherent taxonomies can emerge from tagging over time. Of interest to the social sciences is the issue of how actors following particular rules, which may be relatively idiosyncratic, or conventions for tagging cites interact through the feedback about tags and the distribution of tags to produce relatively coordinated emergent classification systems. Classification systems, once in place, naturally shape and constrain future behavior as they guide cognition. Is there a critical point past which the emergent classification system is not substantially altered?

The Semantic Web as Taxonomy

The Semantic Web, an idea had by the inventor of the Web, is to create a "web of meaning" that is "an extension of the current Web in which information is given well-defined meaning, enabling computers and people to work in better cooperation" [BernersLee2001]. Berners-Lee correctly notes that users are having more and more difficulty navigating through the overload of information available in human-readable form by the Web, and believed that created machine-readable meta-data to classify web-pages was the correct solution. The original Semantic Web vocabulary RDF (Resource Description Framework) gave users an extensible way to create and record meta-data in triples (subject, predicate, object) form, where each member of the triple is guaranteed uniqueness on a Web-scale by being a URI, such that the fact that the web-page is about a piano can be expressed as (http://xmlns.com/foaf/0.1/primaryTopic, http://www.example.org/#piano). The next level above this, OWL (The Web Ontology Language) has strengthened RDF considerably by making it a full scale ontology language, where given a URI and a list of facts about that URI, the URI can be precisely classified into a hierarchical taxonomy, and so we can express constraints such as "Every jaguar is a cat with exactly four legs."

OWL transforms the Semantic Web from a simple meta-data scheme to a decentralized classification scheme, where any given URI can have facts stated about it and be placed in a hierarchy. While it is capable of expressing complex relations and has a formal semantics that is easily understood by machines, it suffers from a number of severe problems. First, the URIs used in the ontology itself may not change, so all knowledge on the Semantic Web is monotonic. Second, it does not allow disagreement between ontologies. As put by Jacobs, the Semantic Web assumes an "immutable conception of reality" where "past and future won't change" and external features that are objectively possessed by each member of the class, so that every member can be precisely and absolutely classified [Jacob2004]. Despite having the technology standardized for years, the Semantic Web has not been adopted by users.

An Alternative to Taxonomy

In contrast to the Semantic Web, computers based on collaborative "tagging" have taken off. Shirky explains it as "If you've got a large, ill-defined corpus, if you've got naive users, if your cataloguers aren't expert, if there's no one to say authoritatively what's going on, then ontology is going to be a bad strategy" [Shirky2005]. Ontologies in the traditional sense are usually created by to classify a domain, and when the domain (such as the Web) is absolutely gigantic and constantly changing, the use of a taxonomic classification scheme created in OWL by an expert is simply premature optimization. One important fact about tagging is that it is "post-hoc" categorization, not pre-optimized classification, and so is more likely to optimally characterize the data. tagging represents a fundamental shift in the way the world is viewed from the expert-designed ontology. While ontologies classify data, tagging categorizes data. "Categorization divides the world of experience into groups or categories whose members share some perceptible similarity within a given context," and so as opposed to the precise boundaries of classification, the fuzzy and ever shifting boundaries of categorization is better attuned to the needs of individual users and to a ontologically indeterminate world."[Jacob2004]. These emergent categories are often called "folksonomies" as opposed to ontologies.

Advantages of Tagging

Tagged data is usually for that data to be retrieved later and found by others, and so the scheme used to classify the data is essentially a convention that is given a social meaning, and one fact that falls out Lewis's famous game-theoretic analysis of convention is that "People will in general use the minimum amount of convention to solve their co-ordination problem. This rule-of-thumb might explain the slowness of the Web community to embrace model-theoretic semantics." [Halpin2006]. Tagging is more popular than Semantic Web taxonomies precisely because it uses a minimal amount of convention: "Groups of users do not have to agree on a hierarchy of tags or detailed taxonomy, they only need to agree, in a general sense, on the "meaning" of a tag enough to label similar material with terms for there to be cooperation and shared value." [Mahes2006]. The low cognitive load of using tagging in comparison with ontologies is one reason for its success, since "picking topics from a pull-down menu is arduous, the topics we currently employ are not sufficient, and updating the tool with new topics is too time consuming" [Merholz2004]. This lead tagging to have a high cost-benefit analysis in terms of being able to retrieve the data and share it in comparison with the time consumed classifying it: "Free typing loose associations is just a lot easier than making a decision about the degree of match to a pre-defined category (especially hierarchical ones). It's like 90% of the value of a proper taxonomy but 10 times simpler." [Butterfield2004].

Disadvantages of Tagging

While no-one argues that tagging is harder to use than Semantic Web ontologies, there are severe problems with tagging. The first is due to the natural language nature of tags themselves. Tags are not normalized for synonymity, morphology, or even just different manners of specifying the exact same meaning, such that "if you want to find all references to New York City on Del.icio.us, you'll have to look through nyc, newyork, and newyorkcity [Merholz2004]. Second, heteronymity runs rampant on tagging systems, with users employing " the same term for disparate concepts" such that words like "flow" can mean either "optimal experience" or the movement of liquids like rivers [Merholz2004]. The lack of an explicit hierarchy makes many of tags redundant, such that a web-page about pianos must be labelled both as about pianos and about music, despite the fact that every piano is about music. Any sort of structured data becomes impossible, yet certain kinds of data lead inevitably towards structure. For example, the concept of a "date" or "time-stamp" of a URI makes no sense without the actual date, such as "February 18th 2006." The fact that often data comes with a natural structure, as given by frame or facet-based systems, is handled easily by the Semantic Web. It is also impossible to express complex relationships using only tags. For example, a web-page may inform the results of an election, but it can not distinguish by its tags alone who won the election and by what margin. Unlike Semantic Web ontologies, collaborative folksonomies that use tags alone cannot in general be shared across collaborative tagging systems to another without the use of at least an ontological layer to resolve the "tags" to URIs and even then the problems cited above still make it impossible [Gruber2005]. In that regard, each tagging system is stranded from interaction with the greater Web, and the data itself is usually held hostage behind firewalls.

The Emergent Semantic Web

One powerful metaphor for tagging is "desire lines" that "are the foot-worn paths that sometimes appear in a landscape over time" such that "a smart landscape designer will let wanderers create paths through use, and then pave the emerging walkways, ensuring optimal utility" [Merholz2004]. This metaphor points towards a way of development for Semantic Web ontologies that maintains both the advantages of taxonomic classification with collaborative tagging. Only after users have explored the space of possibilities and discovered some optimum categorization, should an ontology be formalized for classification purposes. Avoiding pre-optimization, a user-optimized ontology would take advantage of the often unexpected ways users categorize data, yet provide the amount of classificatory power provided by a smaller set of terms that can then be mapped to a Semantic Web ontology capable of expressing structured data facets, complex relationships, and capable of scaling to a Web-level. After all, the minimum amount of convention to share data across the Web effectively is simply higher than just tagging. It is possible in order to share data effectively, users naturally and without external compulsion restrict their vocabulary, and settle to tagging each URI with a fairly small set of semantically distinct tags. The question is then whether or not such a classification structure, even a taxonomy, can emerge from tagging-based categorization and be detected. While some have claimed that it cannot since the the responsiveness and flexibility" of user categorization "effectively prohibit the establishment of meaningful relationships" due to their being "fleeing and ephemeral," there are a number of other cases where complex structure emerges from simply behavior [Jacob2004]. The ideal case is language itself, where "One of the key questions to understand [is] how a communication system can arise...how distributed agents without a central authority and without prior specification can nevertheless arrive at a sufficiently shared language conventions to make communication possible" [Steels2004].

Is Collaborative Tagging a Complex System?

The study of complex systems specializes in the detection of such "hidden order" from the aggregate behavior of simple agents. Each human tagger is an agent, whose task is to maximize both their ability to find their data easily in the future and to share that data with others while minimizing the amount of time they spend tagging the data. The only action of agents is to place one or more tags on given URI, and possibly to change it later. However, how does the tagger know whether or not their tagged data is being shared? Luckily, with tagging systems "feedback is immediate. As soon as you assign a tag to an item, you see the cluster of items carrying the same tag. If that's not what you expected, you're given incentive to change the tag or add another" [Udell, 2004]. For a given tag chosen from one of the four popular tags on deli.cio.us, a power-law distribution between the number of tags and co-occurring tags has been shown [Catutto2006], as predicted since "the most used tags are more likely to be used by other users since they are more likely to be seen" [Mahes2004]. Empirical work has shown that most URIs are given three tags by a given user, and usually at most five. Further empirical work has shown that despite their wide choice taggers themselves settle down to an average of less than 100 tags in their total collection of tagged URIs while the maximum amount of tags tends to be around 200 [Marlow2006]. The user is responding to constraints on their memory, since the more tags they use the less likely they are to consistently use a given tag for recall.

Data Collection

Our experiment will use a web-spider to collect two data-sets from the popular social bookmark manager del.ici.us. Del.icio.us was chosen over sites such as Flickr since users of del.icio.us are likely to equally optimize their tagging for sharing as opposed to primarily for personal browsing. The first data-set will just be the most popular 100 tagged URIs, and follow the course of their development over a week, checking four times a day for any changes. Question: Should we do the 1000 most recent as well, which would be a random sample as opposed to the most popular?

In summary our data will contain tags (x), URIs (u), frequencies of tags of a given URI (fx), as well as the time of tagging (t), as well as the URIs of users (z) who tagged the tags. Since at this time we are interested not in individual users but in the stability of the tags, we will ignore z, and so our dataset will be a set, which we call the tag-set of time-stamped URIs (ut) having one or more tags and frequencies ut(x, fx)+.

Proposed Analysis

This project intends to use data collected from these online tagging sites to analyze the dynamics of these systems, in particular looking for any emergent order over time that may make the tags amendable to being used for the construction of Semantic Web ontologies.

Dynamics of Tagging

There must be selection pressure on the tags since there are large number of users in tight feedback cycles with each other without no central authority who are trying to communicate and retrieve data while minimizing time and effort. A tag would be more "fit" if it allowed the user to communicate quickly, and this feedback would be positive if the other users were using a similar tag. However, there is also value in choosing tags that successfully discriminate categorizations that may have not been noticed by other users. The first taggers can choose any word in the language as their tag and will likely make the most blunt categorizations. Over a time, other taggers may make more fine-grained distinctions or may agree with their predecessors. There are three hypotheses as regards the behavior of the tag-sets over time:

  1. Tag convergence, so that after a certain amount of time the number of tags given to a resource, tag-set stabilizes as the relevant categorizations are made and the most common words for those categorizations become the majority.
  2. Tag divergence would then be that tag-sets never converge to a smaller group of more stable tags, and the tag distribution continually changes.
  3. Tag periodicity, where after one group of taggers settles to some local optimal tag-set, another group uses a divergent set and so perturbs the original optimal set, and after a period of time the new group's set becomes the new local optimal tag-set. This process may repeat and so lead to convergence after a period of instability, or it may repeat ad infinitum and so act like a chaotic attractor.

Detection

This project is clearly a timeseries in a multi-dimensional state space. As such, some of the material from Bradley's lectures may be the most relevant. One problem will be the state-space itself, since if the state-space is (tags, URIs, frequencies, time) then for any given time you will have only a sparse matrix of tags and frequencies. For convergence, we would expect the matrix to stabilize at a set number of tags and the frequency of those tags to increase as time increases, while divergence would show the oppositve behavior. In order to shrink the state-space, we could cluster our URIs over the tag-dimension, which would make the state-space matrix much less sparse. Ideally, we'd see some sort of phase transition past which the tags all stabilize, so material from Cris Moore might be useful as well. Since we are trying to detect certain types of processes, we imagine Cybenko's lectures would be useful as well.

Transforming Folksonomies into Ontologies

Assuming that tag convergence can be reached (or the tags in a periodic system can be "frozen" at one of their , then one is left with a small group of stable tags. Another question is given these tags, can any structure be discerned from them? There are the following three hypotheses, which could easily be given a pretty good definition using information-theory, but the details are fuzzy. Tom Carter could help with information-theoretic measures, as could Lafferty with machine-learning these structures.
  1. Super-Class Relationships Tags that co-occur with other tags often are thought to be more general than more specific-tags that co-occur with other tags less often. For example, "music" co-occurs with both "piano" and "guitar", and as such can be suspected being a super-class of both. On the other hand, "piano" probably does not co-occur with more possible tags than "music" and usually co-occurs with "music" and so it likely is a subclass.
  2. Synonym Relationships Detecting synonyms is actually counter-intuitive, since I believe that the same user will not tag a URI both "computer" and "PC," but will probably only pick one of those. However, groups of users will use different synonyms, and over time most of the convergence will come from synonyms being merged.
  3. Facet Relationships Tags that co-occur often might have a facet, or structured relationship. These may be dyads or trids. For example, "book" and "author" and "Mark Twain" is a triadic ("triple" on the Semantic Web) relationship, and if these co-occur quite often they are probably a facet. In fact, one would suspect that most co-occurences are dyads, like "author" and "Zadie Smith," or "book" and "Mark Twain," and making these work with the Semantic Web would be slightly more difficult.

References

[BernersLee2001]
Tim Berners-Lee, Jim Hendler, and Ora Lassila The Semantic Web Scientific American, 2001
[Butterfield2004]
Stuart Butterfield Sylloge. August4th,2004.
[Cattuto2006]
Ciro Cattuto, Vittorio Loreto, and Luciano Petronero Semiotic Dynamics and Collaborative Tagging. 2006.
[Golder2006]
Scott Golder and Bernardo A. Huberman Usage Patterns of Collaborative Tagging Systems 2006. Usage Patterns of Collaborative Tagging Systems. Journal of Information Science, 32(2). 198-208.
[Gruber2005]
Tom Gruber Ontology of Folksonomy: A Mash-up of Apples and Oranges.2005.
[Halpin2006]
Harry Halpin Identity, Reference, Meaning, and the Web. Proceedings of the Identity, Reference, and the Web (IRW2006) Workshop at the World Wide Web Conference (WWW 2006). May, 2006. Edinburgh, Scotland.
[Jacob 2004]
Elin K. Jacob Classification and categorization: a difference that makes a difference Library Trends, Winter 2004
[Mahes2004]
Adam Mahes Folksonomies - Cooperative Classification and Communication Through Shared Metadata. December 2004
[Marlow2006]
Cameron Marlow, Mor Naaman, Danah Boyd, Marc Davis Tagging, Taxonomy, Flickr, Article, ToRead. Collaborative Tagging Workshop at the World Wide Web Conference (WWW 2006). May, 2006. Edinburgh, Scotland.
[Merholz2004]
Peter Merholz Metadata for the Masses.October19,2004.
[Shirky2005]
Clay Shirky Ontology is Over-rated.March, 2005.
[Steels 2004]
Luc Steels The Evolution of Communication Systems by Adaptive Agents 2004 In: Alonso, E., D. Kudenko and D. Kazakov (eds.) Adaptive Agents and Multi-Agent Systems. LNAI 2636. Springer Verlag: Berlin. 125-140.
[Udell2004]
Jon Udell Collaborative knowledge gardening. Infoworld.August20,2004.
[Wu2006]
Xian Wu, Lei Zhang, Yong Yu Exploring Social Annotations for the Semantic Web. Proceedings of the World Wide Web Conference (WWW 2006). May, 2006. Edinburgh, Scotland.
[Xu2006]
Zhichen Yu, Yun Fu, Jianchaing Mao, and Difu Su Towards the Semantic Web: Collaborative Tag Suggestions. Proceedings of the Collaborative Tagging Workshop at the World Wide Web Conference (WWW 2006). May, 2006. Edinburgh, Scotland.